{"id":"44dcf2ca-51e4-43eb-94e1-806020111e1e","arxiv_id":"2608.12043","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A dual-anchor stochastic root-finding algorithm achieves O(epsilon^{-3}) oracle complexity with constant mini-batching and no variance reduction for cocoercive operators.","lead":"This paper introduces a stochastic acceleration method for root-finding that keeps a constant batch size and reaches an epsilon-accurate solution with O(1/epsilon^3) noisy operator evaluations, without variance reduction. It works by using a fixed-horizon dual-anchor update, which, unlike standard Halpern acceleration, does not accumulate stochastic errors.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the proof is internally consistent and the restrictive Assumption 3.2 is explicitly acknowledged.","rationale":"The reader accepted with high confidence and identified Assumption 3.2 as the weakest assumption. My stress-test pass agrees: the assumption is restrictive but explicitly scoped, and the proof chain from Lemma 4.2 through Lemma A.2 is internally consistent. I checked the telescoping algebra in Lemma A.2, the error decomposition in Lemma 4.3, and the leave-one-out argument in Lemma 4.4; no hidden dependence on N appears in the noise term. Since the central claim is conditional on the stated assumptions and the limitations are acknowledged, the ACCEPT verdict stands unchanged.","tokens_in":21025,"tokens_out":27907,"duration_ms":245173,"concrete_test":"Verification worth running: implement S-Dual-OHM with N=200, alpha=1, B=1 on a linear finite-sum cocoercive operator (as in Experiment 2), and over 10^4 seeds measure E||F(x_{N-1})||^2 along with the excess over 4||x0-x*||^2/N^2; then repeat with N=400 and N=800 at fixed B=1. The theorem predicts the excess stays bounded by 6 sigma^2 independently of N, so any systematic growth of the excess with N would signal a flaw in the leave-one-out argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After checking the main argument, I find no load-bearing flaw in the central claim. The theorem's result is conditional on Assumption 3.2 (cocoercivity in expectation), which is genuinely stronger than unbiasedness plus bounded variance: it requires a same-\\xi coupling of two-point evaluations and excludes state-dependent noise. This is exactly the assumption that makes Lemma A.2's leave-one-out bound E||x_{N-1}-x^{(s)}_{N-1}||^2 <= alpha^2 sigma^2/B true, and that bound is what prevents noise accumulation in Lemma 4.4; so the O(epsilon^-3) complexity genuinely rests on it. However, the paper states this limitation explicitly, notes the monotone-Lipschitz extension as an open question, and the derivations of Lemmas 4.2, 4.3, 4.4, A.1, and A.2 are algebraically consistent under the stated assumptions. The strong-monotone result (Theorem 4.5) uses only Assumption 3.1 plus contractivity. I therefore do not see an internal inconsistency or an overclaim relative to the assumptions.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies stochastic root-finding for cocoercive operators under an unbiased stochastic oracle. It proposes S-Dual-OHM, a mini-batch stochastic version of the dual-anchor Dual-OHM algorithm, and proves that under an additional cocoercivity-in-expectation assumption (Assumption 3.2), constant step size and constant batch size give E[||F(x_{N-1})||]^2 <= 4||x_0-x^*||^2/(alpha^2 N^2) + 6 sigma^2/B, which yields O(epsilon^{-3}) oracle complexity with a last-iterate guarantee and no variance reduction or double-loop regularization (Theorem 4.1). For strongly monotone cocoercive operators, the same algorithm is shown to achieve E[||F(x_k)||] <= epsilon in O((L/mu) log(1/epsilon)) iterations, giving eO(epsilon^{-2}) complexity under only Assumption 3.1 (Theorem 4.5). The appendix contains the algebraic identity, the error-propagation lemmas, the leave-one-out stability bound, and the contractive-case proofs, and the experiments compare S-Dual-OHM with anchor-based, variance-reduced, and regularized baselines.","tokens_in":21051,"tokens_out":5673,"duration_ms":55569,"significance":"If the result holds, it is a meaningful conceptual contribution: it shows that the choice of acceleration mechanism matters in the stochastic setting, and that the dual-anchor mechanism avoids the error accumulation that plagues stochastic Halpern-type methods. The proof is self-contained and the appendix is complete: Lemma 4.2 is a purely algebraic identity, Lemma A.2 is the key leave-one-out stability estimate, and Lemmas 4.3 and 4.4 correctly propagate the noise terms. The paper is also honest about the main restriction: Assumption 3.2 is genuinely stronger than unbiasedness with bounded variance, and the manuscript explicitly states that state-dependent noise and general monotone-Lipschitz sample operators are not covered. The strong-monotone result is a useful addition and uses only Assumption 3.1. The numerical study is careful, including a controlled comparison in Appendix B where S-OHM receives its own tuning. I find no load-bearing error in the central argument.","major_comments":[],"minor_comments":[{"comment":"The 'ghost batch' B_{N-1} is informal; since the proof ultimately sets G_N = F(x_{N-1}), the identity is correct, but the exposition should state explicitly that this is only a bookkeeping device and not an additional stochastic oracle call.","section":"Appendix A.1, proof of Lemma 4.2"},{"comment":"The phrase 'for k=0,...,N-1' is slightly confusing because y_{N-1} is a fixed terminal point; I recommend writing 'for every fixed horizon N and every k in {0,...,N-1}' to avoid reading y_{N-1} as an iterate indexed by k.","section":"Section 4.2, Theorem 4.5"},{"comment":"The vertical axis labels (1, 2 x 10^2, 3 x 10^2, 4 x 10^2, 6 x 10^2) use a nonstandard scale; a conventional log scale or linear ticks would improve readability.","section":"Section 5, Figure 2 (right panel)"},{"comment":"The derivation of the final bound would be easier to follow if the text explicitly wrote the step E[N alpha^2/4 ||F||^2 + alpha/2 <F,x^*-x_0>] - 3(N-1)alpha^2 sigma^2/(4B), since the Young and cocoercivity steps are otherwise compressed into the two displayed lines.","section":"Section 4.1, after Lemma 4.4"}],"recommendation":"accept","confidential_remarks":"I see no circularity or overclaim relative to the stated assumptions. The deterministic Dual-OHM rate is used as an independently established building block, and the stochastic analysis is self-contained. The strength of Assumption 3.2 is an acknowledged limitation rather than a hidden flaw. The paper fits the scope of math.OC and I recommend acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a real result. S-Dual-OHM gets E[||F(x_{N-1})||] <= eps with N = Theta(1/eps) and B = Theta(1/eps^2), so O(eps^-3) oracle calls, no variance reduction, no double loop, single loop, constant batch. That beats naive stochastic Halpern and matches the best prior complexity that required variance reduction, achieved more cleanly. The new idea is that the dual-anchor mechanism makes the error-accumulation weights sum to O(N) instead of O(N^2), and the leave-one-out stability argument in Lemma A.2 is the technical heart. I checked the appendix: the algebraic identity in Lemma 4.2 is correct, the error propagation in Lemmas 4.3-4.4 is consistent, and the leave-one-out bound E||x_{N-1}-x^{(s)}_{N-1}||^2 <= alpha^2 sigma^2/B holds under the stated assumptions. The central proof is not handwavy.\n\nThe soft spot is exactly the one the authors flag: Assumption 3.2, cocoercivity in expectation. It requires a same-xi coupling of two-point evaluations and fails for state-dependent noise and for general monotone Lipschitz sample operators. The O(eps^-3) claim genuinely rests on it — Lemma 4.3 uses it to control the quadratic error terms, and Lemma A.2 uses it for square-nonexpansivity in expectation. So the paper does not solve stochastic monotone inclusion in the broad sense; it solves the cocoercive-in-expectation case. But the authors state that openly and list the monotone-Lipschitz extension as an open problem. I do not see an overclaim.\n\nMinor quibbles: the ghost batch in Lemma 4.2 is informal, though you can read it as a notational device since the proof does not need an actual extra batch. The strong-monotone result (Theorem 4.5) gives O-tilde(eps^-2) but with suboptimal condition-number dependence, which they acknowledge. The experiments support the main narrative — S-Dual-OHM beats constant-batch S-OHM, and the tuned-batch comparison in Appendix B closes the obvious experimental gap. Batch sizes are tuned by grid search, but that is standard practice, not fitted theory.\n\nCitation pattern: the deterministic Dual-OHM rate comes from the authors' own prior work, but that rate is independently established and used as a building block, not as a conclusion. No circularity.\n\nThis paper is for people working on stochastic fixed-point and monotone inclusion methods, and for anyone interested in how acceleration behaves under stochastic noise. It deserves a serious referee. My recommendation: send it out. The main referee question will be how much Assumption 3.2 buys and whether the monotone-Lipschitz case can be handled, but the paper as written is sound.","headline":"Solid, honest stochastic acceleration result; the O(epsilon^-3) claim holds under cocoercivity in expectation, and the authors say clearly where the assumption is doing the work.","tokens_in":21739,"tokens_out":1823,"would_cite":true,"duration_ms":15869,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65K10","49J40","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"A dual-anchor update carries acceleration into stochastic root-finding at O(ε⁻³) complexity, with constant batch size and no variance reduction.","keywords":["stochastic root-finding","dual-anchor acceleration","Halpern iteration","cocoercivity in expectation","oracle complexity","monotone operators","fixed-point methods","mini-batching"],"falsifier":"Run S-Dual-OHM on the affine worst-case cocoercive operator with additive Gaussian noise, taking $N=1/\\epsilon$ and $B=1/\\epsilon^2$; if $\\mathbb{E}[\\|\\mathbb{F}(x_{N-1})\\|]$ does not decrease as $O(\\epsilon)$ along a sequence $\\epsilon\\to0$, the main theorem is false. A sharper check is to compute $\\mathbb{E}[\\langle e_{j-1},\\mathbb{T}x_{N-1}\\rangle]$ for a moderately large $N$ and compare it with $\\alpha\\sigma^2/B$; if this inner product grows with $N$, the leave-one-out bound in Lemma 4.4 fails.","tokens_in":1880,"feed_emoji":"🎯","tokens_out":3439,"duration_ms":90159,"temperature":0.7,"pith_summary":"This paper claims that acceleration for root-finding can survive stochastic noise when the right acceleration mechanism is used. The authors propose Stochastic Dual-OHM, a mini-batched version of the dual-anchor (dual-Halpern) update, and prove that for cocoercive operators it drives the expected squared residual to $4\\|x_0-x^*\\|^2/(\\alpha^2 N^2) + 6\\sigma^2/B$ after $N$ steps. Choosing $N=\\Theta(1/\\epsilon)$ and $B=\\Theta(1/\\epsilon^2)$ gives $\\mathbb{E}[\\|\\mathbb{F}(x_{N-1})\\|]\\le\\epsilon$ with $O(\\epsilon^{-3})$ oracle evaluations, using constant batch size and no variance reduction or double-loop regularization. A sharper $\\widetilde{O}(\\epsilon^{-2})$ bound follows when the operator is strongly monotone. If true, stochastic acceleration is not inherently fragile; the choice of deterministic acceleration decides whether noise accumulates.","feed_headline":"Dual-anchor update beats noise in stochastic root-finding","feed_subtitle":"Reaches residual ε in O(1/ε³) calls with constant mini-batches, no variance reduction.","key_machinery":"The load-bearing object is the finite-horizon Dual-OHM update with weights $a_k=(N-k-1)/(N-k)$, which replaces the anchor-based convex combination by a telescoping correction between consecutive operator evaluations. The analysis rests on the exact algebraic identity of Lemma 4.2, expressing zero as a combination of the terminal residual, a cross term with the initial point, and weighted terms $Q_{N,j}$; while those terms are nonnegative in the deterministic case, in the stochastic case the paper controls their expected contribution by Lemmas 4.3 and 4.4. The crucial structural fact is that the total weight $\\sum_{j=1}^{N-1}\\lambda_{N,j}=\\alpha(N-1)/2=O(N)$, whereas the analogous weight sum for stochastic OHM is $\\Theta(N^2)$; this difference is what keeps the noise term bounded rather than $N$-dependent. Lemma A.2 provides the leave-one-out coupling that makes Lemma 4.4 hold under square-nonexpansivity in expectation.","core_discovery":"The core discovery is that the dual-anchor update, defined for a fixed horizon $N$ by $x_{k+1}=x_k+\\frac{N-k-1}{N-k}(\\mathbb{T}_{B_k}(x_k)-\\mathbb{T}_{B_{k-1}}(x_{k-1}))$, does not accumulate oracle error the way anchor-based Halpern methods do. Theorem 4.1 shows that under cocoercivity in expectation, S-Dual-OHM with step size $\\alpha\\in(0,2/L]$ and constant batch size $B$ satisfies $\\mathbb{E}[\\|\\mathbb{F}(x_{N-1})\\|]^2\\le \\mathbb{E}[\\|\\mathbb{F}(x_{N-1})\\|^2]\\le 4\\|x_0-x^*\\|^2/(\\alpha^2 N^2) + 6\\sigma^2/B$, so $O(\\epsilon^{-3})$ oracle evaluations suffice for an $\\epsilon$-accurate last iterate. The proof isolates the noise contribution through Lemma 4.4, whose key step is a leave-one-out stability bound showing that the error from one mini-batch propagates to the terminal iterate with size at most $\\alpha\\sigma^2/B$. For strongly monotone operators, early stopping yields a near-optimal $\\widetilde{O}(\\epsilon^{-2})$ oracle complexity.","pith_inferences":["Editorial inference: The same \"sum of proof weights\" diagnostic could screen other members of the H-invariant family of optimal fixed-point algorithms for stochastic noise robustness before running any simulation.","Editorial inference: With a restart or batch-size schedule, the $O(\\epsilon^{-3})$ result may be pushed toward the $\\widetilde{O}(\\epsilon^{-2})$ lower bound in the non-strongly-monotone case, since the present bottleneck is the variance term $6\\sigma^2/B$.","Editorial inference: For finite-sum problems with per-component cocoercivity, the algorithm inherits a variance bound that may permit a finite-sum improvement analogous to what variance-reduced Halpern methods achieved for finite sums."],"forward_implications":["Constant mini-batching with $B=\\Theta(\\epsilon^{-2})$ and $N=\\Theta(\\epsilon^{-1})$ reaches $\\mathbb{E}[\\|\\mathbb{F}(x_{N-1})\\|]\\le\\epsilon$ in $O(\\epsilon^{-3})$ oracle evaluations for cocoercive-in-expectation operators, without variance reduction or double-loop regularization.","The same single-loop algorithm, early-stopped after $k=O((L/\\mu)\\log\\epsilon^{-1})$ iterations, attains $\\widetilde{O}(\\epsilon^{-2})$ oracle complexity for strongly monotone operators, which is near-optimal in its $\\epsilon$-dependence.","The guarantee is for the last iterate, not an averaged, best, or uniformly random iterate.","The finite-horizon dual-anchor update is optimized for its terminal iterate, whereas anytime anchor-based methods accumulate error weights of size $\\Theta(N^2)$, which explains why the stochastic extension works for the former and not the latter."],"supporting_citations":[{"why":"It supplies the deterministic Dual-OHM update whose stochastic version is analyzed in this paper.","marker":"[55]"},{"why":"It provides the optimal Halpern coefficient and the $O(1/k^2)$ baseline that the dual-anchor mechanism matches deterministically.","marker":"[29]"},{"why":"It establishes the accelerated proximal-point / Halpern rate used as the deterministic comparison benchmark.","marker":"[22]"},{"why":"It shows that stochastic anchor-based Halpern iteration requires variance reduction, serving as the key comparison that this paper avoids.","marker":"[9]"},{"why":"It supplies the near-optimal $\\widetilde{O}(\\epsilon^{-2})$ algorithm and lower bound relevant to the strongly monotone case.","marker":"[12]"},{"why":"It provides the exact optimal complexity lower bound and the worst-case operator used in the numerical experiments.","marker":"[40]"},{"why":"It supplies the cocoercivity and strong-monotonicity facts for minimax saddle operators used to instantiate the assumptions.","marker":"[17]"}],"fun_headline_variants":["Dual-anchor tames stochastic root-finding noise","No variance reduction: dual-anchor accelerates stochastic root-finding","Dual-anchor achieves near-optimal stochastic root-finding rates","Constant batch size, no variance reduction: dual-anchor succeeds","Dual-anchor method sidesteps variance reduction in stochastic root-finding"],"cache_read_input_tokens":23808,"weakest_assumption_plain":"The proof needs the noisy oracle to be cocoercive on average: the expected squared gap between two noisy evaluations must be majorized by $L$ times the deterministic operator's monotonicity gap, a condition that holds for additive noise or per-sample cocoercive sums but fails for state-dependent noise and general monotone Lipschitz sample operators.","fun_headline_variants_meta":{"raw":{"variants":["Dual-anchor tames stochastic root-finding noise","No variance reduction: dual-anchor accelerates stochastic root-finding","Dual-anchor achieves near-optimal stochastic root-finding rates","Constant batch size, no variance reduction: dual-anchor succeeds","Dual-anchor method sidesteps variance reduction in stochastic root-finding"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000733,"raw_usage":{"total_tokens":3307,"prompt_tokens":1000,"completion_tokens":2307,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":616,"completion_tokens_details":{"reasoning_tokens":2218}},"tokens_in":616,"tokens_out":2307,"duration_ms":17775,"temperature":1.0,"reasoning_tokens":2218,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T00:19:12.287666+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run S-Dual-OHM on the affine worst-case cocoercive operator with additive Gaussian noise, taking $N=1/\\epsilon$ and $B=1/\\epsilon^2$; if $\\mathbb{E}[\\|\\mathbb{F}(x_{N-1})\\|]$ does not decrease as $O(\\epsilon)$ along a sequence $\\epsilon\\to0$, the main theorem is false. A sharper check is to compute $\\mathbb{E}[\\langle e_{j-1},\\mathbb{T}x_{N-1}\\rangle]$ for a moderately large $N$ and compare it with $\\alpha\\sigma^2/B$; if this inner product grows with $N$, the leave-one-out bound in Lemma 4.4 fails.","supporting_citations":[{"cited_title":"Suh, and Ernest K","cited_arxiv_id":null,"evidence_quote":"It supplies the deterministic Dual-OHM update whose stochastic version is analyzed in this paper."},{"cited_title":"Accelerated proximal point method for maximally monotone operators.Mathe- matical Programming, 190(1–2):57–87, 2021","cited_arxiv_id":null,"evidence_quote":"It establishes the accelerated proximal-point / Halpern rate used as the deterministic comparison benchmark."},{"cited_title":"Near-optimal algorithms for making the gradient small in stochastic minimax optimization.Journal of Machine Learning Research, 25(387):1–44, 2024","cited_arxiv_id":null,"evidence_quote":"It supplies the near-optimal $\\widetilde{O}(\\epsilon^{-2})$ algorithm and lower bound relevant to the strongly monotone case."},{"cited_title":"Springer-Verlag, 2003","cited_arxiv_id":null,"evidence_quote":"It supplies the cocoercivity and strong-monotonicity facts for minimax saddle operators used to instantiate the assumptions."}],"review_version":1}