Convergence Analysis of the Random Bisection Method
This work provides theoretical insights into randomized optimization methods, but it is incremental as it generalizes an existing bisection approach.
The authors tackled the problem of analyzing convergence rates for a random bisection method where the cutting point is chosen randomly, and they derived expected convergence rates that depend only on the expectation of the cut parameter, validated through numerical simulations.
We propose a generalized version of the bisection method where the cutting point between the two subintervals is chosen at random following an arbitrary distribution. We compute expected convergence rates with respect to any arbitrary a priori distribution for the position of the root in the initial interval and proved that it depends only on the the expectation $\mathbb{E}[c(1-c)]$ of the cut $c$. We also provide a generalization of the method for $K$ random cuts and study its convergence properties. Most probabilistic derivations are kept fairly simple for the ease of understanding of a larger audience. Our theoretical results are then validated numerically using statistical simulation.