1
$\begingroup$

Take a continuous function $f:[-1,1]\to\mathbb{R}$ and a sequence of independent random variables $X_1,X_2,\ldots$ uniformly distributed in $[-1,1]$.

Define $Y_n=\max\{f(X_1),f(X_2),\ldots,f(X_n)\}$. Then almost surely (that's a joke, I'm unaware if this is actually true) there is a theorem which would give us almost sure convergence $Y_n\to \max_{x\in[-1,1]}f(x)$. This would model the process of finding the maximum value of $f$ by evaluating it at random points and keeping the largest value found.

  1. Is there a better sequence of $X_k$ which gives faster convergence for "most functions"? Like say the $X_k$ are supported near Chebyshev nodes somehow (wild guess)? Maybe we drop the independence assumption in some way and adapt our $X_k$ so that we disfavor testing points near points we have already tested.
  2. Are there known estimates for rates of convergence of something like this? Has someone already looked into this?
$\endgroup$
5
  • 1
    $\begingroup$ There is a huge field of stochastic algorithms which can be formulated in this form, such as simulated annealing, genetic algorithms,... Each of these is almost always better than the algorithm (random choice) above.. $\endgroup$ Oct 14, 2020 at 8:38
  • 2
    $\begingroup$ I think an estimate on the rate of convergence is in terms of the modulus of continuity of $f$. Say if the interval is divided in equal sub-intervals of length $\delta$, in which the oscillation of $f$ is less than $\epsilon$, then as soon as one $X_n$ drops into one of these, one has $Y_m\ge \max f -\epsilon$ for $m\ge n$; this way the almost sure convergence should together follow with estimates. $\endgroup$ Oct 14, 2020 at 8:42
  • $\begingroup$ @DieterKadelka Is that an empirical observation or a proven fact that these algorithms are better? $\endgroup$
    – Dirk
    Oct 14, 2020 at 9:41
  • $\begingroup$ First: It cannot be proved that these algorithms always are better, since this is not always true. Random choice ensure almost sure convergence to the maximum, but the speed is usually (not always) worse than for most of the "improved" search algorithm. I started my lesson about this topic usually with the function $f(x) = x^2 \cdot (1+0.99 \cdot sin(x^2)$ (actually with a 2-dimensional variant of it). You can play with it. Using the keywords "genetic algorithm", "evolutionary optimization" or "simulated annealing" you will find much more about this topic. $\endgroup$ Oct 14, 2020 at 9:58
  • $\begingroup$ So let's say we have a regularity condition on $f$ like $C^{n,\alpha}$ or some decay condition on its Fourier coefficients. Is there a 'preferred' set of $X_k$ which gives provably faster convergence for such a general class of functions? 'Faster' would mean in comparison to the completely random search I describe in the original question, measured by how fast $P[\max(f)-Y_n>\epsilon]\to 0$. $\endgroup$ Oct 14, 2020 at 16:53

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.