Metraipolis › archive › dc_dcb38ccb42e0

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2508.17591
License (as archived)
CC0-1.0
Archived
2026-10-07T23:02:46.686Z
SHA-256 of the archived text
6f4e438b0a951efb5710e423d0726ba9cbe43d2d3e0c2ea4aa4977ad35b0491a
Stable URL of this page
https://metraipolis.com/documento/dc_dcb38ccb42e0

How to cite

The Root Finding Problem Revisited: Beyond the Robbins-Monro procedure — arXiv:2508.17591 — arXiv (en), https://arxiv.org/abs/2508.17591 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dcb38ccb42e0 (Metraipolis archive dc_dcb38ccb42e0, sha256 6f4e438b0a951efb5710e423d0726ba9cbe43d2d3e0c2ea4aa4977ad35b0491a)
BibTeX
@misc{dcdcb38ccb42e0,
  title = {The Root Finding Problem Revisited: Beyond the Robbins-Monro procedure — arXiv:2508.17591},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2508.17591},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dcb38ccb42e0; sha256 6f4e438b0a951efb5710e423d0726ba9cbe43d2d3e0c2ea4aa4977ad35b0491a},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2508.17591. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We introduce Sequential Probability Ratio Bisection (SPRB), a novel stochastic approximation algorithm that adapts to the local behavior of the (regression) function of interest around its root. We establish theoretical guarantees for SPRB's asymptotic performance, showing that it achieves the optimal convergence rate and minimal asymptotic variance even when the target function's derivative at the root is small (at most half the step size), a regime where the classical Robbins-Monro procedure typically suffers reduced convergence rates. Further, we show that if the regression function is discontinuous at the root, Robbins-Monro converges at a rate of $1/n$ whilst SPRB attains exponential convergence. If the regression function has vanishing first-order derivative, SPRB attains a faster rate of convergence compared to stochastic approximation. As part of our analysis, we derive a nonasymptotic bound on the expected sample size and establish a generalized Central Limit Theorem under random stopping times. Remarkably, SPRB automatically provides nonasymptotic time-uniform confidence sequences that do not explicitly require knowledge of the convergence rate. We demonstrate the practical effectiveness of SPRB through simulation results.

Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-09-29 in stat.ML).
Categorie arXiv: Statistics Theory (math.ST) ; Methodology (stat.ME); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2508.17591 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T22:41:13.186Z dalla pagina https://arxiv.org/catchup/stat.ML/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).