The Root Finding Problem Revisited: Beyond the Robbins-Monro procedure

원문 초록

We study the sequential root-finding problem with repeated noisy measurements. We propose sequential-test bisection STB, which uses a nonparametric sequential sign test to determine when to move to a new design point. Compared with variants of stochastic approximation, STB offers broader adaptivity and faster convergence. When the regression function satisfies $|f(x)|\geq \textsf{c}_0|x-\theta|^\gamma$ in a neighborhood of $\theta$ for constants $\textsf{c}_0,\gamma>0$ where $\theta$ is the root, i.e. $f(\theta) = 0$, we establish non-asymptotic guarantees showing that STB, without using the knowledge of $\gamma$, achieves the minimax adaptive optimal convergence rate $\widetilde{O}(n^{-1/(2\gamma)})$, outperforming Robbins--Monro and related stochastic-approximation methods in convergence rate. Under sub-Gaussian noise, STB provides finite-sample confidence sequences for the root $\theta$ without estimating a derivative. In the positive-slope model, we augment STB with {randomized weighted-section and a line fitted to all observations}, leading to asymptotic normality and consistent variance estimation. We formalize the efficiency by a convolution theorem of H\'ajek-Le Cam type. Furthermore, when the regression function is discontinuous at the root, we show that Robbins--Monro converges at rate $1/n$, whereas STB converges super-polynomially. We extend this construction to multivariate nonparametric level-set estimation by sampling along rays. As a technical byproduct, we establish a new central limit theorem under random stopping, with proof techniques that may be of independent interest.