CS Paper Radar

Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity

Tong Yang, Tao Jiang, Yuejie Chi, Ashok Cutkosky, Lin Xiao

cs.LG stat.MLmath.OC ·submitted 2026-09-22 23:57 UTC · v1
theory

Abstract

We analyze a simple stochastic inertial Krasnosel'skii--Mann (iKM) method for finding a fixed point of a nonexpansive operator in a real Hilbert space. Our method is obtained simply by adding two inertial extrapolations to stochastic KM [Bravo and Cominetti, 2024], and it retains one call to a possibly biased stochastic oracle per update and achieves sharp rates in both the stochastic and deterministic regimes. Specifically, with our proposed parameter schedule, we prove the following last-iterate fixed-point residual bound: \[ {O}\!\left(\frac{1}{K} +\frac{σ\log K}{\sqrt K} +\frac{B_K\log K}{K}\right), \] where $K$ is the horizon, $σ$ is the noise level and $B_K$ is the accumulated root-mean-square bias. When $B_K=O(\sqrt K)$, this yields $\widetilde O(ε^{-2})$ sample complexity that matches, up to a logarithmic factor, the stochastic-oracle lower bound given under the unbiased subclass of our model [Foster et al., 2019, Theorem 2]. It also improves the best-known $O(ε^{-4})$ random-iterate guarantee for stochastic KM [Bravo and Cominetti, 2024, Corollary 5.4]. To our knowledge, this is the first single-loop method for general nonexpansive fixed-point problems to attain this near-optimal sample complexity without variance reduction or batching. When the oracle is exact, the same method attains the worst-case-optimal $O(K^{-1})$ last-iterate residual rate [Park and Ryu, 2022, Theorem 4.6], improving the $O(K^{-1/2})$ rate of classical KM [Cominetti et al., 2014; Bravo and Cominetti, 2018].

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Last-Iterate Bounds for Nonexpansive Stochastic Approximation

cs.LG math.OCeess.SY ·2026-11-10 ·Ramanan Tamizholi, Siddharth Chandak, Rahul Singh
similarity 0.76
Abstract · 23 pages

We establish last-iterate mean-square residual bounds for nonexpansive stochastic approximation (SA), or stochastic Krasnoselskii-Mann (KM) iterations. In particular, we consider fixed-point mappings that are nonexpansive with respect to the Euclidean norm, and focus on polynomially decaying stepsizes. We study three conditions on the conditional second moment of the noise, and obtain bounds that are optimal up to logarithmic factors in each case. When it scales linearly with the squared residual, the best rate is $O(1/k^{1-ε})$ for any $ε>0$. In this case, for all considered stepsizes, our bounds match those of the noiseless KM iteration. When it is bounded by a constant, the best rate is $O(\log^2 k/\sqrt{k})$. When it scales affinely with the squared norm of the iterate, the best rate is $O(1/k^{1/2-ε})$, and the mean-square residual can diverge if the stepsizes are not square-summable. Thus, unlike for contractive SA, square-summable stepsizes are necessary for nonexpansive SA. We demonstrate how various algorithms with cocoercive maps, such as stochastic gradient descent, linear SA, and learning in cocoercive games, fit into our framework, and how the different noise conditions arise in each of them.

0.08

Adaptivity, Anchoring, and the Exact Oracle Complexity of Stochastic Fixed-Point Iterations

cs.IT math.OC ·2026-09-26 ·Yekini Shehu
theory similarity 0.68
Abstract · 55 pages, 5 figures

We study stochastic fixed-point iterations $x_{n+1}=θ_nx_0+(1-θ_n)\widehat T(x_n)$ for nonexpansive and contractive operators on Hilbert spaces, with a single-point unbiased oracle of bounded variance. Deterministically, every anchor schedule $θ_n=c_n/(n+2)$ whose density $c_n\in(0,1]$ does not oscillate between scales is either polynomially suboptimal on contractions or super-polynomially slow on rotations; for constant densities $θ_n=c/(n+2)$ the tradeoff is exact, with $\norm{x_n}\asympΓ(c+1)(n\varphi)^{-c}$ on rotations by angle $\varphi$ ($\varphi\to0$, $n\varphi\to\infty$) and, for the classical schedule, $\norm{x_n}=\frac{2|\sin(n\varphi/2)|}{n\varphi}+O(\frac1n)$. The dichotomy fails exactly under lacunary anchor concentration: an explicit $γ$-oblivious schedule, one per target accuracy, is simultaneously contraction-optimal and rotation-polynomial with exponent $1/α_0$, $α_0=\log_2(3/2)$, and, for each fixed target accuracy, the matching lower bound holds for Lebesgue-a.e.\ angle. For stochastic contractions, the minimax rate is $Θ(σ^2\eps^{-2}(1-γ)^{-2})$ on affine maps, and within the anchored class $Θ(σ^2\eps^{-2}(1-γ)^{-2}+(1-γ)^{-1}\ln(D/\eps))$ for known modulus via geometric batching; without a certified modulus bound no sound distance certificate exists, and a certified ceiling is the exact boundary. For nonexpansive maps we prove $O(Kσ^2D^2\eps^{-4})$ in every $2$-uniformly smooth Banach space and the Hilbert rate $\tildeΘ(σ^2\eps^{-2}+D\eps^{-1})$ by reduction to monotone inclusions. Numerical experiments are consistent with every scaling prediction.

0.40

Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding

cs.LG math.OC ·2026-09-28 ·TaeHo Yoon, Nicolas Loizou
similarity 0.67
Abstract

Among distinct optimal acceleration mechanisms for deterministic monotone root-finding problems and fixed-point problems, dual-anchoring has recently been shown to admit a more robust direct stochastic extension than standard anchor acceleration. However, without additional strong monotonicity, the existing stochastic dual-anchoring guarantee has two limitations: first, it requires cocoercivity in expectation, and second, it attains only $O(ε^{-3})$ oracle complexity, leaving a gap to the near-optimal $\tilde{O}(ε^{-2})$ complexity achieved by other methods. In this work, we address both of these limitations by combining dual-anchoring with stochastic resolvent approximation and optimized variance control. For unbiased stochastic oracles with variance bounded by $σ^2$, where sample operators are monotone and uniformly $L$-Lipschitz, our algorithm finds a point with $ε$-residual with a near-optimal oracle complexity of $O ( (LD / ε) \ell + (σ^2 / ε^2) \ell^2)$, where $\ell = \log (1 + LD / ε)$ and $D$ is the initial distance to a solution. This result improves the best known oracle complexity in the noise-dominated regime under these samplewise assumptions, reducing the poly-logarithmic factor from cubic to quadratic.

0.26

A Contraction Framework for Stochastic Operators with Bootstrapping: Application to TD Learning

cs.LG eess.SPmath.OC ·2026-09-24 ·Ids van der Werf, Sergio Rozada, Antonio G. Marques
similarity 0.64
Abstract · 5 pages, 1 figure

Many iterative algorithms rely on bootstrapping. A variable is updated using a second, frozen copy as a target, which is periodically replaced with the updated variable. Majorize-minimize and inexact proximal-point methods share this structure, as does temporal-difference (TD) learning. However, existing convergence guarantees for scenarios that combine sampled updates with targets refreshed only every $K$ steps rely on the specific structure of the update, such as linear approximation or gradient-based inner steps, and on uniformly bounded sampling error. We instead model the sampled update as a stochastic operator on the parameter space, which reduces the analysis to a contraction argument that needs no gradient structure and allows the sampling error to grow with the iterates. Within this framework, we derive a finite-time bound for i.i.d. samples and any target-update period $K$. We show that the iterates converge geometrically in root mean square to a ball around the fixed point, provided the sensitivity to the frozen target is smaller than the contraction slack of the inner map. Existing deterministic frozen-target contraction and stochastic-gradient-type bounds follow as special cases of our framework, and simulations of TD learning reproduce the predicted contraction rate and scaling of the error floor with the step size.

0.21

A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise

cs.CC math.OCcs.LG ·2026-08-10 ·Jikai Jin
theory similarity 0.64
Abstract

We prove a sharp lower bound for smooth nonconvex stochastic optimization with uniformly bounded gradient noise. In the \(K=1\) fresh-sample model, every randomized adaptive algorithm requires $$Ω\left( \frac{ΔL}{ε^2} + \frac{ΔLσ^2}{ε^4} \right)$$ queries to find a point with expected gradient norm at most \(ε\). This matches the standard upper bound and, to the best of our knowledge, resolves the question raised by [Arjevani et al. 2023] of whether almost-surely bounded oracle error permits a better rate than bounded variance. The proof was independently generated with GPT-5.6 Sol in Codex's Ultra mode during a two-hour session. The human author supplied the prompt and was responsible only forchecking the proof and revising and polishing the manuscript.

0.38

Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds

cs.LG stat.ML ·2026-09-24 ·Wei Biao Wu
theory similarity 0.63
Abstract

Uniform noise-moment bounds exclude stochastic gradients whose variability increases with the iterate. We study ordinary, single-sample stochastic gradient descent for smooth, lower-bounded, possibly nonconvex objectives under distance-dependent conditional moments. Under second moments alone, a direct descent--displacement argument yields $T^{-1/3}$ expected average squared-gradient stationarity with a horizon-dependent stepsize. An explicit oracle-complexity corollary matches the known smooth Blum--Gladyshev (BG-0) lower bound, including the $Lb_2Δ^3\varepsilon^{-6}$ and $LΔσ^2\varepsilon^{-4}$ stochastic terms, where $Δ$ is the initial objective gap and $σ^2+b_2\|x-x_1\|^2$ bounds the variance. Thus unchanged SGD attains the minimax stochastic complexity in this second-moment class. For $p>2$, predictable localization and a Hilbert-space Fuk--Nagaev inequality yield a high-probability bound separating logarithmic variance and polynomial rare-shock contributions. The localization radius is derived from the recursion: no bounded-iterate assumption, clipping, normalization, momentum, or increasing batch size is needed. We also give increasing-confidence rates, an objective-gap-growth refinement recovering root-$T$ stationarity, and stochastic $L^p$-Lipschitz examples. The broad BG-0 optimality statement is distinguished from the smaller mean-square-smooth class, in which additional oracle structure permits faster algorithms.

0.21

A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Maps

cs.LG math.OC ·2026-08-16 ·Ege C. Kaya, Arda Fazla, M. Berk Sahin, Abolfazl Hashemi
similarity 0.62
Abstract · 36 pages, 1 figure

We study stochastic approximation of fixed points of a non-expansive operator $T$ when the oracle samples originate from a continuing Markovian trajectory. A direct block-minibatch implementation of Halpern iteration attains an expected last-iterate residual of order $O(\log N/N)$, but accrues a substantive complexity of $\tilde O(ε^{-5})$ Markovian samples. We therefore introduce a variance-reduced Markovian PAGE-Halpern method whose refresh and same-state difference blocks are analyzed through the Poisson equation. In Hilbert spaces, the cocoercivity of $I-T$ results in an $O(ε^{-3})$ sample complexity. Our main result extends this construction to a general finite-dimensional Banach space. A displacement-level Halpern bound replaces the Hilbert-space potential and yields $\tilde O(ε^{-3})$ sample complexity. We also establish a high-probability guarantee with the same leading accuracy dependence by measuring the estimator in an auxiliary smooth norm.

0.47

Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps

cs.DS math.OCcs.LGstat.ML ·2026-09-08 ·Jelena Diakonikolas, Cristóbal Guzmán, David Martínez-Rubio
theory similarity 0.62
Abstract

We study the oracle complexity of computing a point with small fixed-point residual $\|T(x)-x\| \leq ε$, for a general norm $\|\cdot\|$ and a self-map $T$ of a compact convex set. We study this problem in the setting where $T$ is nonexpansive with respect to the same norm $\|\cdot\|$ and accessed via an unbiased stochastic oracle with bounded variance $σ^2$. We provide an algorithm that solves such instances for any norm with a weak Rademacher type $q > 1$, with high probability. The algorithm is based on a recursive anchoring technique. For type-$2$ spaces, such as $\ell_p$-spaces for $p \in [2, \infty]$, our algorithm attains stochastic oracle complexity $\tilde O(σ^2 ε^{-3} + ε^{-1})$. We further prove a near-matching lower bound (i.e., matching up to poly-log factors) for such $\ell_{\infty}$-norm instances in high dimensions. Our lower bound holds against any randomized algorithm that succeeds with constant probability. It further extends to settings with ``sparse'' noise, where variance measured with respect to any $\ell_p$ norm is of the same order, ruling out the possibility of improving oracle complexity as a function of $\varepsilon$ by measuring variance in a non-matching $\ell_p$ norm.

0.53