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

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

cs.LGAug 16, 2026

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

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

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

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.

Figures & tables

Figure 1: Normalized fixed-point residual at common transition budgets. The top row evaluates the Hilbert method on policy evaluation, and the bottom row evaluates the Banach method on average-reward control. Each PAGE method is compared with the block method on the same realized trajectories. Lines show medians over twenty trajectories and shaded regions interquartile ranges.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Problem	Mixing	Method	$\epsilon=0.20$	$\epsilon=0.10$	$\epsilon=0.05$
Evaluation	Fast	Block Halpern	$585$	$1{,}238$	$8{,}839$
	Fast	Hilbert PAGE-Halpern	$4{,}567$	$9{,}001$	$14{,}684$
	Slow	Block Halpern	$68{,}885$	$1{,}923{,}959$	$>2{,}048{,}000\ (0/20)$
	Slow	Hilbert PAGE-Halpern	$25{,}705$	$62{,}611$	$107{,}374$
Control	Fast	Block Halpern	$6{,}205$	$21{,}021$	$63{,}081$
	Fast	Banach PAGE-Halpern	$3{,}302$	$8{,}606$	$20{,}749$

Appendix

Table 1: Median number of observed transitions required to reach a common residual target. The counts in parentheses give the number of repetitions that reach the target when fewer than twenty do so. The notation

>2{,}048{,}000

means that the median transition count exceeds the available budget.

Stochastic Approximation

Stochastic approximation studies iterative algorithms that solve optimization, root-finding, and fixed-point problems using noisy data.

See all 76 papers

Solving Stochastic Fixed-Point Equations with High Probability
Jul 10, 2026Jelena DiakonikolasStochastic Approximation Stochastic Optimization Convergence
Department of Computer Sciences University of Wisconsin-Madison
Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity
Sep 22, 2026Tong Yang, Tao Jiang, Yuejie Chi +2Last-Iterate Convergence Stochastic Approximation
Department of Electrical and Computer Engineering, Carnegie Mellon University · Fundamental AI Research (FAIR), Meta Superintelligence Labs · Department of Statistics and Data Science, Yale University +1
Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps
Sep 8, 2026Jelena Diakonikolas, Cristóbal Guzmán, David Martínez-RubioOracle Complexity Stochastic Approximation
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

Jul 10, 2026J/K move · Enter open · S save

Solving Stochastic Fixed-Point Equations with High Probability

Jelena Diakonikolas

Department of Computer Sciences University of Wisconsin-Madison

Stochastic Approximation Stochastic Optimization Convergence Variance Reduction

Open paper AskPDF arXiv

We study stochastic fixed-point equations

\mathbf{T}(\mathbf{x}) = \mathbf{x}

over normed spaces

(\mathcal{E}, \|\cdot\|)

, where the operator

\mathbf{T}

is nonexpansive or contractive and is accessed only through unbiased stochastic evaluations with bounded second central moment. Given

ε> 0, δ\in (0, 1)

, the goal is to output

\mathbf{x} \in \mathcal{E}

such that

\|\mathbf{T}(\mathbf{x}) - \mathbf{x}\| \leq ε

with probability at least

1-δ

. We introduce VR-GHAL, a variance-reduced gradual Halpern method for quadratically smoothable Banach spaces. The key algorithmic ingredient is a recursive stochastic estimator based on clipped differences of oracle evaluations: instead of clipping

τ(\mathbf{x}; ξ)

itself, we clip stochastic differences at the Lipschitz scale

γ\|\mathbf{x} - \mathbf{y}\|

. This makes the estimator pathwise Lipschitz along the algorithmic trajectory while permitting martingale concentration under finite second moments in the native norm. Our main theorem gives an anytime high-probability residual bound: on a single event of probability at least

1 - δ

, the residual decreases nearly geometrically across epochs, up to lower-order logarithmic factors. Under only bounded variance, displaying only the dependence on the target error

ε

and Lipschitz constant

γ\in (0, 1]

\mathbf{T}

, the resulting oracle complexity is

\min\{ε^{-5}, (1-γ)^{-3}ε^{-2}\}

. Under a Lipschitz-in-expectation oracle, the dependence improves to the corresponding

ε^{-3}

nonexpansive rate (i.e., for

γ= 1

), and under samplewise nonexpansiveness to

ε^{-2}

Abstract

Stochastic Approximation

Explore similar work

Solving Stochastic Fixed-Point Equations with High Probability

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

Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps