PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yue Yu, Moulinath Banerjee, Ya'acov Ritov

arXiv:2508.17591v1math.STstat.MEstat.TH

TL;DR

Root-finding methods can have difficult asymptotics when the regression function's slope is small, vanishes, or the function is discontinuous at the root. The paper introduces SPRB and establishes guarantees across these settings, including minimal asymptotic variance, faster convergence in several regimes, and automatically generated confidence sequences.

  • Problem

    When the derivative at the root is small or absent, limiting distributions for existing stochastic-approximation methods are often intractable, leaving open whether adaptivity and valid confidence intervals are possible without knowing the local regime.

    Source: §1 · p. 2

  • Method

    The paper introduces sequential probability ratio bisection (SPRB), a root-finding algorithm intended to adapt to different local behaviors of the regression function.

    Source: §1 · p. 2, §6 · p. 20

  • Results

    SPRB achieves minimal asymptotic variance when f′(θ)>0, exponential convergence at discontinuities, and nearly optimal rates for higher-order roots.

    Source: §1 · p. 2, §6 · p. 20

  • Takeaways & Limitations

    SPRB automatically provides anytime-valid confidence intervals without requiring additional procedures to estimate asymptotic variance.

    Source: §1 · p. 2

    The paper leaves two described corner-case scenarios outside Table 1 and the rest of its analysis.

    Source: §1 · p. 4

Abstract

from arXiv · show

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.

1 Introduction

The introduction asks whether root-finding can adapt to the function's local behavior while providing valid confidence intervals without prior knowledge of that behavior. It introduces SPRB and presents theoretical results across smooth, discontinuous, and higher-order root settings.

1 Introduction

  • The paper asks whether root-finding can adapt to local behavior around the root while constructing valid confidence intervals without prior knowledge of the local regime.When f′(θ) is small or absent, limiting distributions are often intractable and have received comparatively little attention.Source: §1 · p. 2
  • The authors introduce sequential probability ratio bisection (SPRB) as a root-finding algorithm that goes beyond Robbins–Monro and its variants.They state that their theoretical findings provide a positive answer to the question of greater adaptivity with valid confidence intervals.Source: §1 · p. 2
  • SPRB attains n^-1/2 asymptotic normality with minimal variance for f′(θ)>0, exponential convergence at discontinuities, and nearly optimal n^-1/(2γ)+δ rates for higher-order roots.The higher-order comparison is with Robbins–Monro, which converges at the logarithmic rate (log n)^(1/(1−γ)).Source: §1 · p. 2
  • SPRB automatically produces anytime-valid confidence intervals, avoiding additional procedures to estimate asymptotic variance.The authors motivate this approach by noting that Wald-type inference can be unfavorable when the limiting distribution is intractable or derivative estimates converge slowly.Source: §1 · p. 2
  • The analysis derives non-asymptotic bounds for SPRB-related quantities and generalized asymptotic expansions for boundary-crossing problems.The expansions build on work by [Anscombe, 1949, 1953, Woodroofe and Keener, 1987].Source: §1 · p. 3

1.1 Notation

  • The notation section defines stochastic-order and asymptotic-equivalence conventions, convergence notation, and symbols for one-sided limits, sign, minimum, and maximum.It uses oP and OP for convergence in probability and boundedness in probability, respectively.Source: §1.1 · p. 4

2 Related work

Prior work established consistency and asymptotic distributions for Robbins–Monro stochastic approximation, including step-size choices that yield parametric rates under differentiability and a positive derivative. Adaptive methods estimate the local slope, but their performance depends on that estimate and they do not accommodate vanishing derivatives or discontinuities.

Stochastic approximation

  • Robbins–Monro research includes strong-consistency and asymptotic-normality results, with Chung [1954] studying the sequence {X_n − θ} [Robbins and Monro, 1951; Blum, 1954; Chung, 1954].Later work studied asymptotic distributions and step-size choices, including Sacks [1958].Source: §2 · p. 5

Adaptive Stochastic Approximation

  • Adaptive stochastic approximation attains the parametric rate and asymptotic normality when the derivative is positive and 0 < α < 2β, with variance σ²/[α(2β−α)] [Lai and Robbins, 1979, Theorem 2].Its adaptivity comes from sequentially estimating the slope around the root.Source: §2 · p. 5
  • The adaptive method's practical efficacy depends on its ordinary least-squares slope estimator, whose convergence rate is √log n [Lai and Robbins, 1981, Theorem 5].The design faces a trade-off between sampling near the root and maintaining enough dispersion to estimate the slope.Source: §2 · p. 5
  • When the derivative vanishes or the regression function is discontinuous, adaptive stochastic approximation cannot reliably extract first-order derivative information [Lai and Robbins, 1979, 1981].The method updates its step size using a least-squares procedure intended to capture the derivative.Source: §2 · p. 5

3 The SPRB procedure: An overview

SPRB allocates samples sequentially at successive locations and updates an interval around the root using bisection and a weighted-section rule. Its stagewise stopping and updates support sign-based interval inference, with the full procedure also covering vanishing first derivatives.

Sequential sampling

  • The moving boundary is chosen to grow faster than σ√(2j log log j) but slower than j, supporting false-sign control and finite stopping when f(X) ≠ 0.The paper restricts its discussion to a specified moving-boundary form and assumes known noise level, while noting sequential estimation for homoskedastic unknown noise.Source: §3 · p. 6
  • StageSampling determines each location’s sample size by a moving-boundary stopping rule, using accumulated observations to identify the sign and estimate the magnitude of the regression function.Its expected sample size scales with the signal magnitude and confidence level; an appropriate boundary yields minimal expected sample size.Source: §3 · pp. 6–7

Update and algorithm

  • For a noiseless linear regression function with positive slope, the weighted-section formula exactly recovers the root.The update uses endpoint estimates and may collect additional samples at the opposite endpoint to reduce estimator variance.Source: §3 · pp. 7–8
  • The interval update preserves the root with high probability when it is inside the current interval and can recover it when it lies in the preceding interval.The update selects a new sampling point within the current interval; the figure describes the two interval-transition scenarios.Source: §3 · pp. 7–8
  • The full SPRB version is adaptive when the first derivative vanishes, while SPRB-Basic has identical asymptotic behavior under Assumption 2 or Assumption 3.The interval is bisected initially, then uses the weighted-section update once its width is below the threshold δ.Source: §3 · pp. 7–8

Inference

  • For valid inference, SPRB’s interval procedure does not rely on a limiting distribution or calibration based on the convergence rate.The error-control parameter α regulates interval validity, and the stated asymptotic results hold for any choice of α.Source: §3 · p. 8

Convergence

  • Using only bisection gives exponential convergence in the number of stages, but SPRB’s superexponential convergence is necessary for √n-consistency in the described setting.The comparison concerns the differentiable, positive-derivative setting described in the surrounding analysis.Source: §3 · p. 9

Sampling budget

  • The procedure uses random stopping times at each stage, and any apparent sample-use inefficiency from exhausting a preset budget does not affect its asymptotic behavior.SPRB terminates when the budget is exhausted or all k stages are complete.Source: §3 · pp. 5, 9

4 Asymptotic theory

This section develops SPRB’s asymptotic theory for differentiable, discontinuous, and higher-order-vanishing regression functions, as well as for randomly stopped averages. It also constructs time-uniform confidence sequences without explicit convergence-rate calibration, although their width still depends on the convergence rate.

4.1 Randomly stopped average

  • For all t ≥ K, c_μtδ_t log(δ_t + 1) < EN_t < C_μtδ_t log(δ_t + 1); if μ_t → 0 almost surely as t → ∞, the sequences can be chosen with both constants tending to 1.Source: §4.1 · p. 10
  • Randomly stopped, normalized sums converge to the same limit as sums with deterministic sample size as the number of stages grows, extending the triangular-array result of.Although the random sample size can affect the distribution at fixed stage counts, this effect vanishes in the limit.Source: §4.1 · pp. 10–11

4.2 Differentiable regression function

  • SPRB attains the parametric rate and asymptotic variance σ^2/β^2, matching the information lower bound and avoiding Robbins–Monro’s slowdown when 0 < f′(θ) ≤ 1/(2α).The paper also relates this adaptivity to adaptive stochastic approximation methods under Assumption 2 [Lai and Robbins 1979, 1981]; the Robbins–Monro slowdown comparison cites Major and Révész [1973].Source: §4.2 · pp. 11–12
  • Under Assumption 1, SPRB-Basic is strongly consistent, and SPRB consistency is established for any regression function satisfying that assumption.The differentiable-function asymptotic results additionally assume a positive first derivative at the root.Source: §4.2 · p. 11

4.3 Discontinuous regression function

  • SPRB’s jump-discontinuity convergence rate is O(exp(−√n)), up to a logarithmic factor, versus Robbins–Monro’s O(n^−1) rate [Lim 2011].The paper attributes the gap from O(e^−n) to adaptivity; a faster boundary choice does not yield satisfactory convergence in the other cases discussed in Sections 4.2 and 4.4.Source: §4.3 · p. 15

4.4 Higher order regression function

  • When the regression function’s first nonzero derivative at the root is higher-order, full SPRB’s bisection/weight-section hybrid accelerates convergence and achieves an almost-optimal rate beyond the usual Robbins–Monro logarithmic-order rate.The hybrid accelerates convergence when the function is differentiable with vanishing first-order derivative while preserving asymptotic properties in other cases.Source: §4.4 · pp. 15–16

4.5 Confidence sequence

  • For any ∆ in (0, 1/2), setting α = ∆/3 yields SPRB intervals [Xℓk, Xrk] that are nonasymptotically ∆-time-uniform confidence sequences at every stage.Their construction avoids explicit calibration of the convergence rate or limiting distribution.Source: §4.5 · pp. 16–17
  • The section establishes Type-1 error control, but confidence-interval width—and thus sequential-test power—depends on the convergence rate of Xk.Source: §4.5 · p. 17

5 Simulation Study

Across the simulated settings, SPRB is competitive when derivatives are positive and performs better than the compared stochastic-approximation methods in vanishing-derivative and discontinuous settings. The study also reports that SPRB’s trajectories are more stable in the two illustrated scenarios.

5 Simulation Study

  • The simulation study examines convergence behavior and interval performance, including Type-I error and average interval width.Table 2 reports mean absolute estimation errors over 100 Monte Carlo replications at a maximum of five stages; methods are compared columnwise at equal response counts.Source: §5 · p. 18, Table 2 · p. 18
  • At β = 1, SPRB, ASA, and oracle SA perform virtually identically and all outperform classical Robbins–Monro; as β decreases, SA deteriorates markedly.SPRB and ASA remain competitive as the slope decreases.Source: §5 · p. 18
  • In the vanishing-derivative scenario f(x) = 100(x − θ)^3, SPRB outperforms standard SA and ASA in finite samples.The setting has f′(θ) = 0 and corroborates Theorem 18.Source: §5 · pp. 18–19
  • For a discontinuous regression function, SPRB outperforms the competitors by a substantial margin.Figure 3 reports rapid convergence and stability for SPRB, versus persistent oscillations for the Robbins–Monro variants and adaptive SA.Source: §5 · pp. 19–20, Figure 3 · p. 20
  • In the differentiable illustration, SPRB’s terminal estimate has the smallest error, with only oracle SA achieving comparable precision.The oracle uses knowledge of f′(θ), which the passage says is rarely available in practice.Source: Figure 2 · p. 19, §5 · p. 20

6 Concluding discussion

The paper concludes that SPRB adapts across local root behavior, with faster convergence in discontinuous and higher-order settings. It identifies bootstrap inference and multivariate root-finding as directions for future work.

6 Concluding discussion

  • SPRB is presented as an adaptive root-finding algorithm with optimal rates and minimal asymptotic variance when the derivative at the root is small, and faster convergence for discontinuities or higher-order behavior.These are the paper’s stated conclusions across the local conditions considered.Source: §6 · p. 20

6.1 Resampling techniques

  • Bootstrap resampling for adaptive root-finding inference remains an unresolved research challenge, though the authors conjecture compatibility with SPRB’s i.i.d. stage sampling and randomly stopped-average CLT.They identify improved power while preserving anytime validity as a potential future direction.Source: §6.1 · pp. 20–21

6.2 Multivariate root-finding problem

  • Extending SPRB to multivariate root-finding remains future work because higher dimensions lack the real-line total ordering that makes bracketing unambiguous.The authors identify noisy sign aggregation, preserving the true solution set during contraction, and sequential testing error as issues.Source: §6.2 · p. 21

A Auxiliary results

These auxiliary results support the paper’s main theory with bounds on stagewise sampling and results about sign decisions. They also establish ingredients used in the randomly stopped central limit theorem.

A Auxiliary results

  • The auxiliary expected-sample-size result plays a crucial role in proving the randomly stopped central limit theorem.Source: A Auxiliary results · p. 21
  • For sufficiently large t, E N_t is bounded above and below by constants times δ_t log(δ_t + 1); when μ_t → 0, the constants can approach 1.The proposition gives the two-sided expected-sample-size bound and the limiting behavior of its constants.Source: A Auxiliary results · p. 22
  • The appendix establishes exponentially decreasing probability of a false sign decision.The stated result applies at each k and to either endpoint, ℓ or r.Source: A Auxiliary results · p. 25
  • Under Assumption 1, the estimated signs eventually agree almost surely with the signs of the regression function at the stage points.The result asserts that there is a finite random index after which the agreement holds.Source: A Auxiliary results · p. 27

B Auxiliary Results

The appendix supplies auxiliary results for the main theory, including almost-sure finiteness of stage stopping times and an information-based argument about rates under higher-order smoothness.

B.1 Finiteness of stopping time

  • For any stage point X_t ≠ θ, the stopping time N_t is almost surely finite.The proof uses the law of the iterated logarithm.Source: §B.1 · p. 28

B.2 Optimality of root-finding problem under higher order smoothness

  • Under Assumptions 1 and (4), for γ > 1, an informal information-bound argument using a local Cramér–Rao lower bound supports the conjectured optimal root-finding convergence rate n^-1/(2γ).Source: §B.2 · p. 28

C Proof of Theorem 9

The proof of Theorem 9 decomposes the target probability into two terms, showing that one converges to a Gaussian distribution and the other is negligible. It also treats positive and negative values of µk by symmetry.

C Proof of Theorem 9

  • For negative µk, the proof is analogous to the positive case after adding a minus sign.Source: C Proof of Theorem 9 · p. 29
  • T1 converges to Φσ(z) while T2 is o(1), yielding the desired asymptotic normality when the remainder term is o(1).The proof identifies Φσ(z) as the distribution function of a mean-zero Gaussian random variable with variance σ².Source: C Proof of Theorem 9 · pp. 29, 31
  • The proof establishes that the second term T2 is negligible, using a term that converges to zero by Proposition 7.Source: C Proof of Theorem 9 · p. 30

D Proof of Theorem 13

The proof establishes an asymptotic linear expansion for the next SPRB estimate under Assumptions 1 and 2. It also analyzes normalized endpoint errors and random sample sizes.

D Proof of Theorem 13

  • The argument defines normalized errors at interval endpoints and shows a negligible term completes the expansion proof.Source: D Proof of Theorem 13 · pp. 32–33
  • Under Assumptions 1 and 2, the next estimator Xk+1 admits an asymptotic linear expansion.The proof reduces one case to updating the left endpoint and notes that the other endpoint case works analogously.Source: D Proof of Theorem 13 · p. 32
  • A lemma’s convergence claim is reduced to showing ρk tends to zero in probability; the proof gives a high-probability bound on successive sample sizes.The stated bound is log(k + 1)Nk/Nk+1 < C′/k with probability 1 − o(1).Source: D Proof of Theorem 13 · pp. 33–34

E Proof of Theorem 16

The proof of Theorem 16 treats expected sample growth and endpoint behavior under different assumptions. It uses endpoint divergence and a high-probability argument to establish an exponential error bound.

E Proof of Theorem 16

Proof of Theorem 16.

  • With high probability the interval [Xℓk, Xrk] contains θ, and the proof uses this with Lemma 37 to derive an exponential error bound involving κ.The proof identifies κ as a quantity in (0, 1) and gives a universal-constant bound.Source: Proof of Theorem 16 · p. 36

F Proof of Theorem 18

The proof of Theorem 18 bounds the estimator’s error using the number of selected stages, which grows on the order of k/log k. It also introduces a lemma about random sample sizes.

F Proof of Theorem 18

G Additional simulation experiments for Section 5

The simulations compare four root-finding procedures and show that reducing the regression slope amplifies variance in gradient-based methods, while SPRB’s behavior remains essentially unchanged.

G Additional simulation experiments for Section 5

Loading 2508.17591v1…