Research map / Optimization / Nonconvex and smooth optimization

Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularization

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Stochastic variance reduction · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that the dual-anchor (Dual-OHM) acceleration extends to stochastic root-finding and fixed-point problems, achieving O(eps^-3) oracle complexity with constant batch size and no variance reduction or double-loop regularization.

Problem

Accelerated last-iterate residual reduction for stochastic root-finding under cocoercivity in expectation (or square-nonexpansivity for fixed-point problems); anchor-based Halpern acceleration accumulates oracle errors and needs variance reduction or increasing batch sizes.

Approach

Replace the anchor-based Halpern update with the dual-anchor (Dual-OHM) update, whose stochastic error propagation to the final iterate is bounded by a constant independent of N, so constant mini-batches suffice; under strong monotonicity, early stopping gives O~(eps^-2).

Key results

• S-Dual-OHM achieves E||F(x_{N-1})||^2 <= 4||x0-x*||^2/(alpha^2 N^2) + 6sigma^2/B, giving O(eps^-3) total oracle complexity with constant batch size B = O(eps^-2).
• Under strong monotonicity, early stopping gives O~(eps^-2) oracle complexity, nearly matching the Omega(eps^-2) lower bound in eps.
• In the worst-case nonexpansive experiment, S-OHM with constant batch diverges while S-Dual-OHM reaches the smallest last-iterate residual among compared methods.

Surprising findings

• Dual-OHM is not anytime, so intermediate residuals can be worse than baselines even though its final residual is best.
• Naive stochastic extension of anchor-based OHM (S-OHM) with constant batch size fails to converge and its residual diverges.

Limitations

• Cocoercivity-in-expectation assumption excludes general monotone Lipschitz operators and state-dependent noise.
• Dependence on condition number in strongly monotone case remains suboptimal.
• Experiments are small-scale synthetic problems with a fixed sample budget.

Experimental setup

Benchmarks: worst-case nonexpansive operator (Experiment 1) finite-sum cocoercive operator (Experiment 2) SCSC Huber-type minimax (Experiment 3)

Metrics: residual norm ||F(x_k)|| sample complexity

Baselines: SGDA SEG S-OHM Halpern-PAGE Halpern-VR-Finite RAIN

Builds on: Halpern iteration Optimal Halpern Method (OHM) Dual-OHM PAGE RAIN

Closest papers by meaning

• Nonlinear Acceleration of Stochastic Algorithms (NeurIPS 2017 · similarity 0.87)
• The Complexity of Finding Stationary Points with Stochastic Gradient Descent (ICML 2020 · similarity 0.87)
• Optimal Acceleration for Minimax and Fixed-Point Problems is Not Unique (ICML 2024 · similarity 0.87)
• A Universally Optimal Multistage Accelerated Stochastic Gradient Method (NeurIPS 2019 · similarity 0.86)
• Universality of AdaGrad Stepsizes for Stochastic Optimization: Inexact Oracle, Acceleration and Variance Reduction (NeurIPS 2024 · similarity 0.85)
• SGD with memory: fundamental properties and stochastic acceleration (ICLR 2025 · similarity 0.85)