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

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

stat.MLSep 22, 2026

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

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

Organizations: Department of Electrical and Computer Engineering, Carnegie Mellon University · Fundamental AI Research (FAIR), Meta Superintelligence Labs · Department of Statistics and Data Science, Yale University · Fundamental AI Research (FAIR), Meta Superintelligence Labs; Department of Electrical and Computer Engineering, Boston University

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].

Figures & tables

Figure 1: The auxiliary softplus sequence from ( 10 ) and iKM parameters from ( 12 ) for

K=10^{6}

and

a\in\{1/2,1,2,3\}

. The horizontal axis is the normalized iteration

k/K

. The isolated values

\alpha_{1}=\beta_{1}=0

are marked separately. The

\omega_{k}

and

\lambda_{k}

panels use logarithmic vertical scales.

Last-Iterate Convergence

Last-iterate convergence studies whether an algorithm’s final update approaches an optimizer or equilibrium, rather than only its average.

See all 41 papers

Aug 16, 2026

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

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.

Ege C. Kaya, Arda Fazla, M. Berk Sahin +1

Elmore Family School of Electrical and Computer Engineering Purdue University West Lafayette, IN 47907, USA

Stochastic Approximation Last-Iterate Convergence Variance Reduction

Ask PDF

Jul 15, 2026

Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration

Non-expansive two-time-scale stochastic approximation is governed by a slow stochastic Krasnoselskii--Mann fixed-point iteration rather than by contraction to a unique equilibrium. We study this regime under a contractive fast map and a non-expansive reduced slow map. We first prove a finite-horizon lower bound showing that, for any prescribed slow stepsize schedule

(β_k)

, the classical KM residual scale

(\sum_{i<N}β_i(1-β_i))^{-1}

is worst-case sharp for the corresponding unregularized KM update. Combined with the raw fast-tracking leakage scale, this explains the previously observed

k^{-1/4+o(1)}

last-iterate mean-square residual exponent. We then introduce a residual-preconditioned slow oracle that cancels the first-order dependence on the fast tracking error. In a nested Tikhonov-KM algorithm, the uncorrected oracle yields total-sample rate

T^{-1/4+o(1)}

, while the corrected oracle yields

T^{-1/3+o(1)}

. This improvement comes from changing the slow-oracle bias from first order to second order in the fast error after all inner-loop samples are counted. Finally, we show that the repeated inner-loop cost of the nested method can be avoided in a smooth derivative-oracle model. A single-loop algorithm that tracks both the fast equilibrium and the leakage preconditioner online achieves

T^{-1/2+o(1)}

with

O(1)

primitive samples per iteration.

Dhruv Sarkar, Vaneet Aggarwal

Indian Institute of Technology Kharagpur · Mohamed bin Zayed University of Artificial Intelligence · Purdue University

Last-Iterate Convergence Stochastic Approximation Two-Timescale Stochastic Approximation

Ask PDF

Sep 8, 2026

Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps

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.

Jelena Diakonikolas, Cristóbal Guzmán, David Martínez-Rubio

Department of Computer Sciences, University of Wisconsin-Madison · Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Católica de Chile, Santiago, Chile · IMDEA Software Institute, Madrid, Spain

Oracle Complexity Stochastic Approximation Information-Theoretic Lower Bounds

Ask PDF

Abstract

Last-Iterate Convergence

Explore similar work

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

Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration

Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps