{"id":"cb09aa71-697c-4998-8582-debe32cede24","arxiv_id":"2508.17591","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"SPRB is a stochastic root-finding algorithm that attains parametric-rate, minimal-variance estimation for small derivatives at the root, exponential convergence for discontinuities, and near-minimax rates for vanishing derivatives, with nonasymptotic anytime-valid confidence sequences.","lead":"The paper introduces SPRB, a stochastic root-finding algorithm that repeatedly samples at chosen points until it can reliably tell which side of the root it is on, then narrows a bracketing interval. It proves that SPRB achieves the best possible accuracy in smooth cases, exponential speed for jump discontinuities, and fast rates when the function is flat at the root, along with anytime-valid confidence intervals.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 25's false-sign bound is proven only for k≥K, so the claimed nonasymptotic anytime-valid confidence sequence (Theorem 25) lacks coverage control for early stages.","rationale":"The reader's weakest assumption is exactly the point I would stress: the nonasymptotic anytime-valid confidence sequence is a central advertised feature, and its only proof route runs through Lemma 25 at every stage. The all-k gap is more than cosmetic because Theorem 25 promises a nonasymptotic bound with no large-K caveat. I nevertheless keep the verdict unchanged rather than rejecting: the gap is localized and likely patchable (possibly K=1 for the allowed α range), the asymptotic rate results can proceed with only eventual sign correctness, and the remaining concerns—deferred proof details, assumed known σ, and simulations without code or error bars—already justify a CONDITIONAL verdict. I do not see an internal contradiction that destroys the main construction as stated; the paper simply needs to supply the missing early-stage verification or adjust the theorem to absorb a finite correction.","tokens_in":37988,"tokens_out":16165,"duration_ms":169912,"concrete_test":"Check the boundary inequality analytically: prove or disprove that for α=∆/3 (hence α_k=α2^{-k}≤1/6), for every n≥1 and every k≥1, −2 log α_k · n log(n+1) ≥ n(log log(2n)+0.72 log(5.2/α_k)). If it holds, replace the 'k≥K' qualification in Lemma 25 by k≥1 and Theorem 25's proof closes immediately; if it fails at some small k, compute or bound P(f̂_k f_k<0) for those stages and recompute the total coverage error in Eq. (4.24).","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 25 (Appendix A) claims for every k∈N+ the false-sign bounds P(f̂_k f_k<0)<α_k and P(f♯_{·,k} f_{·,k}<0)<2α_k. Its proof, however, invokes the boundary inequality −2 log α_k · n log n ≥ n(log log(2n)+0.72 log(5.2/α_k)) only for k≥K for a universal K, and the LIL-based probability bound is applied only there. Theorem 25's proof sums these bounds over all k≥2 through the union bound, so the claimed coverage P(∃k: I_k∌θ)≤∆ in Eq. (4.24) requires the α_k-level control at every stage, including the finitely many k<K. The asymptotic theorems can tolerate finitely many early sign errors via Borel-Cantelli, but the nonasymptotic anytime-valid claim cannot. As written, Lemma 25 does not establish the stated all-k bounds; if the omitted early stages have false-sign probabilities larger than α_k, the union bound gains an uncontrolled additive constant and the claimed ∆ coverage is not proven. This is a proof gap rather than a demonstrated counterexample; the inequality may in fact hold for all k for α=∆/3, but the paper does not verify it.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes SPRB (Sequential Probability Ratio Bisection), a multi-stage stochastic approximation algorithm for root finding under noisy evaluations. At each stage t the method repeatedly samples a current design point X_t until a moving-boundary stopping time N_t is crossed, forming a randomly stopped average whose sign is used to update a bracketing interval, first by bisection and later by a weighted-section update. The advertised contributions are: (i) under differentiability with positive derivative, √n(X_{k+1}-θ) → N(0, σ²/β²) with n the total sample size, so SPRB attains the parametric rate and the minimal asymptotic variance even when 0 < f'(θ) ≤ 1/(2α), a regime where Robbins-Monro slows down; (ii) exponential convergence for discontinuous regression functions; (iii) a rate n^{-1/(2γ)+δ} for vanishing derivatives of order γ; and (iv) nonasymptotic anytime-valid confidence intervals I_k = [X_{ℓk}, X_{rk}] satisfying P(∃k∈N⁺: I_k ∌ θ) ≤ Δ with the choice α = Δ/3. Supporting results include nonasymptotic bounds on the expected stopping time, a generalized CLT for randomly stopped sums, and sign-correctness lemmas.","tokens_in":38238,"tokens_out":8154,"duration_ms":90024,"significance":"If the results hold, this is a substantial contribution to stochastic approximation. The method is genuinely adaptive across regimes that are usually treated separately: positive slope, small slope, vanishing higher-order derivatives, and jump discontinuities. The claimed confidence-sequence property is notable because it avoids estimating the convergence rate or the asymptotic variance. Strengths of the paper include the detailed main-text and Appendix D development of the differentiable case, including the expansion of X_{k+1}-θ and the proof that n/N_k → 1; the nonasymptotic expected-stopping-time bounds of Proposition 7; and simulation comparisons that support the stated qualitative conclusions. The proofs are not circular: the asymptotic rates and the confidence-sequence error are derived from the algorithm's own stopping rule using external concentration inequalities and CLTs, and α, δ, Δ are design hyperparameters rather than fitted constants. However, the anytime-valid theorem currently rests on a proof gap in Lemma 25, and the discontinuous and higher-order cases are only sketched in the appendices as submitted.","major_comments":[{"comment":"Lemma 25 states P(f̂_k f_k < 0) < α_k and P(f^♯_{·,k} f_{·,k} < 0) < 2α_k for every k ∈ N⁺, but its proof establishes the controlling inequality −2 log α_k · n log n ≥ n(log log(2n) + 0.72 log(5.2/α_k)) only for k ≥ K for a universal K, and the LIL-based concentration bound is applied only there. Thus the all-k statement is not proved as written. Since Theorem 25 sums these bounds over all k ≥ 2 through the union bound, the claimed Δ-time-uniform coverage in Eq. (4.24) is not established: early-stage false-sign probabilities above the α_k levels would contribute an unaccounted additive constant. The asymptotic theorems can tolerate finitely many early failures by Borel-Cantelli, but the nonasymptotic anytime-valid claim cannot. The authors should either prove the early-stage bounds, restate the theorem with an explicit finite-stage correction term, or restrict the confidence sequence to k ≥ K with the error level adjusted accordingly. Additionally, the derivation of inequality (A.10) for the extra endpoint samples is sketched and appears to mix the stopping time at the original update stage with the mean f_{·,k} at the endpoint; this part of the lemma needs a complete proof as well.","section":"§4.5 (Theorem 25) and Appendix A (Lemma 25)"},{"comment":"The rate n^{-1/(2γ)+δ} for regression functions with vanishing first-order derivatives is one of the paper's central claims, but the proof in Appendix F is a sketch: Lemma 40 is stated with 'the argument parallels that of Lemma 34 and is therefore omitted,' and the final display relies on unstated high-probability events and on Lemma 39 in a compressed way. If the supplemental material contains the complete proof, the manuscript should point to the specific supplement locations; as submitted, the main text and Appendix F do not contain enough detail to verify this advertised result.","section":"§4.4 / Theorem 18 and Appendix F"},{"comment":"The exponential convergence claim for discontinuous regression functions is likewise only sketched. The proof relies on Corollary 32, Lemma 37, and a Cesàro summation argument, but the key inequalities (E.4)-(E.5) are asserted with 'with probability 1-o(1)' without the full event decomposition needed to control the remainder in the product over stages. Since exponential convergence in this regime is a distinctive advertised improvement over Robbins-Monro's n^{-1} rate, the proof should be completed in the text or the supplement should be made available with full details.","section":"§4.3 / Theorem 16 and Appendix E"}],"minor_comments":[{"comment":"The abstract's phrase 'derivative at the root is small (at most half the step size)' is imprecise; the condition is 2α f'(θ) ≤ 1, i.e. f'(θ) ≤ 1/(2α). Please rephrase to avoid confusion between the step-size α and the inverse step size.","section":"Abstract and §1"},{"comment":"The manuscript contains numerous typos and grammatical slips, e.g. 'varinace', 'substracting', 'neglible', 'constistutes', 'the the', and 'terminate SPRB either when...'. A careful proofreading pass is needed.","section":"Throughout"},{"comment":"The algorithm boxes are not explicitly labeled in the text (the main SPRB procedure and the simplified variant are referenced informally). Adding numbered algorithm environments would improve readability and make the comparison between the simplified and full versions easier to follow.","section":"Section 3 and Algorithm descriptions"},{"comment":"Equation (4.9) writes o(|X−θ|^ν) with an uppercase X; this should be o(|x−θ|^ν) to match the function argument. The same uppercase/lowercase slip appears in a few other Taylor-expansion displays.","section":"Assumption 2, Eq. (4.9)"},{"comment":"In the submitted arXiv rendering, large portions of Section 1 and parts of Section 2 appear as mojibake/replacement characters, making the introduction's stated question and several remarks unreadable. The authors should regenerate the source so that the manuscript is fully readable.","section":"arXiv rendering, Sections 1-2"}],"recommendation":"major_revision","confidential_remarks":"This is a promising paper with a potentially important algorithmic contribution. The main reason for a major revision rather than acceptance is the unproved early-stage control in Lemma 25, which directly undermines the advertised anytime-valid confidence-sequence theorem, plus the sketch-level proofs for the discontinuous and higher-order cases. These issues appear fixable rather than fatal; if the authors supply a complete proof of Lemma 25 for all k (or a correctly amended Theorem 25) and make the supplemental proofs of Theorems 16 and 18 available, I would be inclined to accept."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read the paper. The short version: SPRB is a real algorithmic contribution and the asymptotic results are substantial, but the nonasymptotic anytime-valid confidence sequence claim in Theorem 25 has a proof gap at early stages. The reader's conditional verdict is about right.\n\nWhat is new and good: The algorithm combines power-one sequential testing at each design point with bisection and weighted-section updates. That combination looks genuinely new. The theoretical rates in Table 1 fill gaps that the literature leaves open for ASA in the small-slope, higher-order, and discontinuous regimes. Theorem 13's minimal variance result for 0<f'(θ)≤1/(2α) is the headline, and the differentiable-case proof is developed in detail. The generalized CLT under random stopping is a useful standalone tool. Discontinuous and higher-order results are sketched but plausible; the exponential rate for discontinuities is striking.\n\nSoft spots: The stress-test note is correct and it matters for the anytime-valid claim. Lemma 25 claims false-sign bounds for every k∈N+, but the proof's boundary inequality is verified only for k≥K. Theorem 25 sums those bounds over all k, so the nonasymptotic coverage P(∃k: I_k∌θ)≤Δ is not established as written. The asymptotic rate and consistency theorems survive: a finite number of early sign errors is harmless by Borel-Cantelli. But the anytime-valid sequence loses its unconditional guarantee. This is a proof gap, not a demonstrated counterexample; the inequality may hold, but the paper needs to verify the early stages or adjust the claim.\n\nOther issues are minor: σ is assumed known; the simulations report no error bars and no code; several proofs are in the supplement. All fixable.\n\nBottom line: this is a serious paper that deserves a proper referee. The asymptotic contributions are likely solid, and the anytime-valid claim is a targeted fix away. I'd bring it to a reading group if anyone works on stochastic approximation, and I'd cite it if I worked on adaptive root-finding.\n\nRecommendation: send to peer review; ask the authors to close the Lemma 25 gap in revision.","headline":"SPRB is a genuinely new adaptive root-finding method with strong asymptotic results, but the nonasymptotic anytime-valid confidence sequence has a real proof gap at early stages.","tokens_in":38783,"tokens_out":2368,"would_cite":true,"duration_ms":22720,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L20","62L10","62F12"],"pacs":[],"model":"deepseek-v4-flash","headline":"SPRB root-finding reaches the parametric rate where Robbins–Monro stalls.","keywords":["Sequential Probability Ratio Bisection","stochastic approximation","root finding","anytime-valid confidence sequence","Robbins-Monro procedure","random stopping times","asymptotic variance"],"falsifier":"Run SPRB with $\\alpha=\\Delta/3$ on a linear function $f(x)=\\beta(x-\\theta)$, and record over many replications the first stage at which $\\theta$ leaves $I_k$; if the empirical frequency of violations before the $K$ in Lemma 25 exceeds the per-stage budget $\\alpha_k$ (or the overall $\\Delta$), the nonasymptotic coverage claim fails as stated. Equivalently, exhibit any small $n,k$ with $-2\\log\\alpha_k\\, n\\log n < n(\\log\\log 2n + 0.72\\log(5.2/\\alpha_k))$, which contradicts the boundary inequality used in the proof of Lemma 25.","tokens_in":37772,"feed_emoji":"🎯","tokens_out":9497,"duration_ms":84679,"temperature":0.7,"pith_summary":"This paper introduces Sequential Probability Ratio Bisection (SPRB), a sequential algorithm for finding the root $\\theta$ of a regression function $f$ observed with noise. The paper's central claim is that SPRB attains the parametric convergence rate and the minimal asymptotic variance $\\sigma^2/\\beta^2$ for stochastic approximation even when the derivative $f'(\\theta)$ is positive but no larger than $1/(2\\alpha)$, the regime in which the classical Robbins–Monro procedure slows down. It further claims exponential convergence when $f$ jumps at $\\theta$, and rates near $n^{-1/(2\\gamma)}$ when the first $\\gamma-1$ derivatives vanish. Because the intervals produced at every stage are nonasymptotic anytime-valid confidence sequences, a user gets valid error control without estimating the convergence rate or asymptotic variance.","feed_headline":"Root-finding hits the parametric rate where Robbins–Monro stalls","feed_subtitle":"SPRB reaches the minimal variance and its intervals stay valid at every step, with no rate knowledge.","key_machinery":"The machinery is Sequential Probability Ratio Bisection. At each stage $t$, the procedure repeatedly samples the current location $X_t$ until the partial sum of responses crosses the moving boundary $T(j,\\alpha_t)=\\sigma\\sqrt{-2j\\log(j+1)\\log\\alpha_t}$, with $\\alpha_t=\\alpha 2^{-t}$; the stopped average $\\hat f_t$ then carries both sign and magnitude information about $f(X_t)$. A bracketing interval $[X_{\\ell t},X_{rt}]$ is updated with plain bisection until its width falls below $\\delta$, then by the weighted-section update $X_{t+1}=(\\hat f_{\\ell t}X_{rt}-\\hat f_{rt}X_{\\ell t})/(\\hat f_{\\ell t}-\\hat f_{rt})$, which recovers $\\theta$ exactly in the noiseless linear case. Extra samples at the opposite endpoint reduce the variance of the endpoint estimates. The load-bearing analytic tools are the nonasymptotic false-sign bounds of Lemma 25, the expected-sample-size bounds of Proposition 7, and a generalized CLT for randomly stopped averages (Theorem 9), which together turn the sequential test nested inside SPRB into rate and coverage guarantees.","core_discovery":"The core discovery is that a root-finding procedure can avoid the phase transition that slows Robbins–Monro down. Under Assumption 2, if $f$ has derivative $\\beta=f'(\\theta)>0$ at the root, the SPRB estimator $X_{k+1}$ after $k$ stages obeys $\\sqrt{n}(X_{k+1}-\\theta) \\to N(0,\\sigma^2/\\beta^2)$ in distribution, where $n$ is the total sample size; this holds for every $0<\\beta\\le 1/(2\\alpha)$, not only for $\\beta>1/(2\\alpha)$. Since $\\sigma^2/\\beta^2$ is the minimal asymptotic variance achievable by stochastic approximation, SPRB is efficient without knowing $\\beta$ or tuning the step size. The same interval construction gives $P(\\exists k\\in\\mathbb{N}^+: I_k\\not\\ni\\theta)\\le \\Delta$ when $\\alpha=\\Delta/3$, a nonasymptotic anytime-valid confidence sequence requiring no rate calibration. In addition, for discontinuous $f$, SPRB converges at the rate $\\exp(-\\kappa\\sigma^{-1}\\sqrt{n}/(\\log n)^\\eta)$, against $O(n^{-1})$ for Robbins–Monro; for $f$ of order $\\gamma$ it attains $n^{-1/(2\\gamma)+\\delta}$, against $(\\log n)^{1/(1-\\gamma)}$.","pith_inferences":["Inference: Because the proof of Lemma 25 establishes its boundary inequality only for stages $k\\ge K$, the anytime-valid coverage theorem as stated relies on unproved early-stage control; users of the confidence sequence from stage one should check whether the bound holds for $k<K$ or inflate $\\alpha$ for early stages.","Inference: The boundary rule uses only sign and magnitude of $f(X_t)$, so SPRB should tolerate heavier-tailed noise if the boundary is built from a corresponding concentration inequality; the paper develops the sub-Gaussian case only.","Inference: The weighted-section update behaves like a one-dimensional bracketing root finder, and the paper itself names the multivariate problem as the open sequel; any such extension must decide how to aggregate sign information across orthants.","Inference: The cheapest test of Theorem 25 is empirical: run SPRB with $\\alpha=\\Delta/3$, record the first time $\\theta$ leaves $I_k$, and check whether early-stage violations respect the per-stage $\\alpha_k$ budget."],"forward_implications":["In the regime $0<\\beta\\le 1/(2\\alpha)$, SPRB achieves $\\sqrt{n}$ convergence and variance $\\sigma^2/\\beta^2$ where Robbins–Monro's rate degrades, and it does so without knowing $\\beta$ or calibrating the step size.","The intervals $I_k=[X_{\\ell k},X_{rk}]$ form a $\\Delta$-time-uniform confidence sequence for every $k$, so inference may stop at any data-dependent time without losing coverage.","For discontinuous regression functions, SPRB converges exponentially rather than at the $O(n^{-1})$ rate of Robbins–Monro.","For $f(x)=\\operatorname{sign}(x-\\theta)\\beta|x-\\theta|^\\gamma(1+o(1))$, $\\gamma\\ge 1$, SPRB converges at $n^{-1/(2\\gamma)+\\delta}$ for any $\\delta>0$, beating the logarithmic rate of classical stochastic approximation.","The randomly stopped average CLT and the boundary-crossing expansions are stand-alone tools for sequential analysis beyond root finding."],"supporting_citations":[{"why":"It defines the classical stochastic approximation recursion whose slowing-down regime SPRB is designed to fix.","marker":"Robbins and Monro [1951]"},{"why":"It supplies the asymptotic normality result for Robbins–Monro with step size $\\alpha/n$ and the variance benchmark SPRB is compared against.","marker":"Chung [1954]"},{"why":"It establishes the parametric-rate behavior and minimal-variance target for adaptive stochastic approximation that SPRB matches.","marker":"Lai and Robbins [1979]"},{"why":"It provides the large-sample theory of sequential estimation that the paper's randomly stopped CLT generalizes.","marker":"Anscombe [1949]"},{"why":"It provides the power-one sequential tests whose expected sample size and false-sign probabilities the SPRB stopping rule builds on.","marker":"Lai [1977]"},{"why":"It introduces confidence sequences, the concept whose nonasymptotic anytime-valid version SPRB automatically produces.","marker":"Darling and Robbins [1967a]"},{"why":"It supplies the time-uniform concentration inequality used to bound false-sign probabilities in the confidence-sequence proof.","marker":"Howard et al. [2021]"},{"why":"It provides the nonasymptotic law of the iterated logarithm used to control the boundary-crossing events.","marker":"Schreuder et al. [2020]"}],"fun_headline_variants":["SPRB: optimal root-finding without tuning step sizes","Root-finder hits optimal variance even with tiny derivatives","SPRB: the root-finder that outpaces Robbins–Monro","When derivatives vanish, SPRB still converges at optimal rate","One root-finding algorithm to rule them all: SPRB"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the false-sign probability bounds of Lemma 25 hold from the very first stage; the proof as written establishes the key boundary inequality only for $k\\ge K$ for a universal $K$, so the anytime-valid coverage of the earliest intervals is not established as stated.","fun_headline_variants_meta":{"raw":{"variants":["SPRB: optimal root-finding without tuning step sizes","Root-finder hits optimal variance even with tiny derivatives","SPRB: the root-finder that outpaces Robbins–Monro","When derivatives vanish, SPRB still converges at optimal rate","One root-finding algorithm to rule them all: SPRB"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000765,"raw_usage":{"total_tokens":3437,"prompt_tokens":1034,"completion_tokens":2403,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":650,"completion_tokens_details":{"reasoning_tokens":2319}},"tokens_in":650,"tokens_out":2403,"duration_ms":20773,"temperature":1.0,"reasoning_tokens":2319,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T17:04:57.096043+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run SPRB with $\\alpha=\\Delta/3$ on a linear function $f(x)=\\beta(x-\\theta)$, and record over many replications the first stage at which $\\theta$ leaves $I_k$; if the empirical frequency of violations before the $K$ in Lemma 25 exceeds the per-stage budget $\\alpha_k$ (or the overall $\\Delta$), the nonasymptotic coverage claim fails as stated. Equivalently, exhibit any small $n,k$ with $-2\\log\\alpha_k\\, n\\log n < n(\\log\\log 2n + 0.72\\log(5.2/\\alpha_k))$, which contradicts the boundary inequality used in the proof of Lemma 25.","supporting_citations":[],"review_version":1}