CS Paper Radar

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

Ege C. Kaya, Arda Fazla, M. Berk Sahin, Abolfazl Hashemi

cs.LG math.OC ·submitted 2026-08-16 23:41 UTC · v2

Abstract

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.

Comment
36 pages, 1 figure

Closest papers

Nearest neighbours by meaning across the whole index.

$O(1/n)$ Convergence Rate for RVI $Q$-Learning

cs.LG ·2026-11-05 ·Avik Kar, Siddharth Chandak, Rahul Singh, Shalabh Bhatnagar
similarity 0.65
Abstract · 24 pages

We establish finite-time convergence guarantee for synchronous relative value iteration (RVI) $Q$-learning for finite weakly communicating Markov decision processes (MDPs). For stochastic Krasnosel'skiĭ--Mann iterations driven by a non-expansive, linearly regular map on a finite-dimensional normed space, we establish last-iterate mean-squared residual bounds under martingale-difference noise whose conditional second moment grows at most linearly with the squared residual. Suitable polynomial stepsizes of order $n^{-a}$ yield an $O(n^{-a})$ rate for $0<a\leq1$. We verify linear regularity and the noise condition for the centered Bellman operator for finite weakly communicating MDPs. Applying the general result gives an $O(n^{-1})$ bound on the mean-squared Bellman span residual of RVI $Q$-learning iterates when a suitable stepsize sequence is used. The positive gap between optimal and suboptimal stationary deterministic policies then yields an $O(n^{-1})$ bound on the expected suboptimality of the greedy policy. Consequently, $O(ε^{-1})$ synchronous iterations suffice for an $ε$-optimal policy in expectation. These guarantees are instance-dependent, with constants that depend on the hitting-time parameters and the suboptimality gap of the second-best policy.

0.17

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

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

cs.LG stat.MLmath.OC ·2026-09-22 ·Tong Yang, Tao Jiang, Yuejie Chi, Ashok Cutkosky, Lin Xiao
theory similarity 0.62
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].

0.48

Non-Ergodic Markovian Mirror Descent with Unbounded Noise

cs.LG math.OCmath.PR ·2026-10-25 ·Yunus Alp Biyikoglu, R. Srikant
similarity 0.62
Abstract · 32 pages

We analyze stochastic mirror descent for minimizing a convex objective expressed as an expectation under the stationary distribution of a Markov chain, using noisy subgradient observations along a single sample path. Through Poisson's equation, we decompose the Markovian noise and control its contribution under regularity and moment conditions that allow the stochastic subgradients and the Poisson solution to be unbounded across the state space. We establish an $O(T^{-1/2})$ bound on the expected suboptimality gap of the weighted-average iterate for an appropriately chosen step size. The analysis does not require aperiodicity or convergence of the chain's marginal distributions to stationarity. For irreducible finite-state chains, we verify the required conditions on the Poisson solution and derive explicit bounds that quantify the effect of periodicity. For irreducible countable-state chains, we verify the required regularity and moment conditions under a geometric Lyapunov drift condition and suitable growth bounds on the stochastic subgradients.

0.20

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

cs.LG math.OC ·2026-08-12 ·TaeHo Yoon, Nicolas Loizou
theoryhighly cited similarity 0.60
Abstract

Acceleration for deterministic root-finding problems has been extensively studied in recent years; specifically, the anchor-based, or Halpern-type methods achieve optimal convergence rates with respect to the operator norm. However, acceleration via these methods does not directly carry over to stochastic setting due to accumulation of errors, unless one enforces diminishing variance via increasing batch sizes or variance reduction techniques. In this work, we show that another class of acceleration, namely the dual-anchor mechanism, extends to the stochastic setting without such error accumulation, in contrast to anchor-based algorithms. Consequently, we cleanly achieve $O(ε^{-3})$ complexity with iteration-independent batch size, without any variance reduction or double-loop recursive regularization, for stochastic root-finding (resp. fixed-point) problems with cocoercivity (resp. square-nonexpansivity) in expectation. For strongly monotone operators, the same algorithm attains a sharper $\widetilde{O} (ε^{-2})$ complexity, nearly matching the lower bound in terms of $ε$-dependence.

0.42

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

cs.IT math.OC ·2026-09-26 ·Yekini Shehu
theory similarity 0.60
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

Optimal Last-Iterate Bounds for Nonexpansive Stochastic Approximation

cs.LG math.OCeess.SY ·2026-11-10 ·Ramanan Tamizholi, Siddharth Chandak, Rahul Singh
similarity 0.59
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

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