PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2608.15966v1cs.LGmath.OC

TL;DR

The paper addresses stochastic fixed-point approximation for non-expansive operators under Markovian sampling, where direct block methods require O~(ε^-5) samples. It introduces variance-reduced PAGE-Halpern analysis and obtains O~(ε^-3) accuracy dependence in finite-dimensional Banach spaces, with high-probability guarantees in smoothed norms.

  • Problem

    Markovian stochastic approximation for non-expansive operators lacks strict contraction drift and requires improved sample complexity beyond direct block methods’ O~(ε^-5) dependence.

  • Method

    The paper combines Halpern displacement bounds with PAGE recursive variance reduction using refresh and same-state difference blocks analyzed through the Poisson equation.

  • Results

    O~(ε^-3) sample complexity is achieved in a general finite-dimensional Banach space, with high-probability guarantees for nonsmooth sup and block-sup applications via smooth auxiliary norms.

  • Takeaways & Limitations

    Within the stated model, Halpern anchoring and same-state variance reduction provide last-iterate guarantees in Banach geometries relevant to reinforcement learning.

  • Takeaways & Limitations

    The analysis assumes a non-expansive mean operator with fixed points and seeks an approximate fixed point under those assumptions.

Abstract

from arXiv · show

We study stochastic approximation of fixed points of a non-expansive operator 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 in the original non-expansiveness norm. We also establish a high-probability guarantee with the same leading accuracy dependence by measuring the estimator in an auxiliary smooth norm. Non-smooth sup and block-sup geometries are covered through norm smoothing.

1 Introduction

The paper develops Markovian stochastic Halpern methods for non-expansive fixed-point problems, addressing dependent samples and conditional block bias. It replaces Hilbert-specific cocoercivity arguments with displacement-level Banach-space analysis and variance reduction.

  • Motivation: Non-expansive stochastic fixed-point problems lack the contraction-based finite-iteration guarantees available for contractive operators.Halpern iteration is presented as a natural method for this regime, with an O(1/N) last-iterate residual in Hilbert spaces.
  • Markovian setting: Continuing Markovian sampling creates dependent blocks whose oracle errors can have conditional bias at block boundaries.The analysis must preserve the online trajectory while accounting for both martingale error and boundary-conditioned bias.
  • Baseline complexity: Ordinary minibatching requires blocks of order n^4 samples, yielding an overall complexity of ˜O(ϵ−5).The inexact Halpern bound requires the nth estimation error to be order n−2, while a kn-sample average has variance decreasing only at rate 1/kn.
  • Variance reduction: PAGE variance reduction tracks operator changes using two query points evaluated from a single Markov state instead of reconstructing each operator value.This mechanism motivates refresh and same-state difference blocks for the Markovian method.
  • Banach-space analysis: The Banach-space approach recursively estimates T and controls increments of the Halpern displacement directly, avoiding cocoercivity unavailable in sup and block-sup norms.The resulting argument operates in the norm where the operator is known to be non-expansive.
  • Contributions: The contributions include perturbation-level and displacement-level inexact Halpern bounds, plus a Markovian block baseline with expected last-iterate residual O(log N/N) and sample complexity ˜O(ϵ−5).The displacement-level bound uses scaled-error increments and enables recursive variance estimation.

2 Related work

Related work spans classical and stochastic Halpern/Krasnosel’skiı–Mann methods, Markovian stochastic approximation via Poisson equations, recursive variance reduction, Banach-space concentration, and continuing-trajectory policy evaluation.

  • Classical fixed-point iterations: Classical Krasnosel’skiı–Mann methods underpin non-expansive fixed-point iterations, while Halpern iteration adds an anchor and can strongly converge under standard weight conditions.Bauschke and Combettes (2020) provide a modern connection to monotone operators and splitting methods.
  • Stochastic non-expansive methods: O(ϵ−5) complexity is achieved by an explicit minibatch stochastic Halpern construction under i.i.d. oracle access, compared with an Ω(ϵ−3) lower bound for a broad single-point linear-span oracle model.Related work also studies stochastic Krasnosel’skiı–Mann iterations under martingale noise and recursive variance reduction under independent sampling.
  • Markovian stochastic approximation: Poisson-equation and ODE approaches provide a foundation for Markovian stochastic approximation, with finite-time analyses covering linear approximation, temporal-difference learning, contractive operators, and unbounded Markovian noise.Blaser and Zhang (2026) study Markovian stochastic Krasnosel’skiı–Mann recursion; the present blocks preserve one continuing trajectory and use predictable stopping-time boundaries.
  • Recursive variance reduction: Recursive variance-reduction methods including SVRG, SARAH, SPIDER, and PAGE use same-sample differences whose second moments decrease as successive query points become close.Related constructions extend to monotone variational inequalities and stochastic Halpern iteration under independent sampling.
  • Banach geometry and applications: Banach-space analyses draw on smooth Lyapunov functions and vector-valued martingale concentration, while continuing-trajectory policy evaluation motivates applications involving differential values and relative-value Bellman recursions.The expected Banach result instead avoids smoothing the fixed-point residual, and average-reward control studies Bellman maps modulo additive constants.

3 Preliminaries

The preliminaries formulate approximate fixed-point search for a mean operator induced by a finite-state Markov chain in a finite-dimensional normed space. The framework assumes non-expansiveness with existing fixed points, finite-chain ergodicity, finite pointwise oracle variance, and iterate stability.

  • 3 Preliminaries: The setting is a finite-dimensional normed space, with Euclidean norm notation and a norm-equivalence constant.The supplied passage introduces (R^d, ∥·∥) and ∥·∥_2.
  • 3 Preliminaries: A finite-state Markov chain with transition matrix P and stationary distribution π defines the mean operator through a measurable oracle map H.The chain is denoted (Y_t) and the oracle map H maps R^d × Y to R^d.
  • 3 Preliminaries: The target operator T is assumed non-expansive and to have a nonempty fixed-point set.These are stated in Assumption 3.1 and the accompanying fixed-point condition.
  • 3 Preliminaries: The Markov chain is assumed irreducible and aperiodic, yielding finite-state mixing constants C_mix and ρ.The passage specifies C_mix ≥ 1 and ρ ∈ (0, 1).
  • 3 Preliminaries: The stochastic oracle has pointwise finite variance, while the generated iterates satisfy a stability condition around the anchor.Assumptions 3.3 and 3.4 impose these controls, with stability constants R_q for q ∈ {1, 2}.

4 Inexact Halpern residual bounds

Section 4 develops two inexact Halpern residual bounds that leave the perturbations model-independent: one controls perturbation magnitudes, while the other controls scaled perturbation increments. The first supports Markovian block averages, and the second supports PAGE’s recursive variance reduction.

  • Model-independent residual analysis: The analysis treats the perturbation sequence abstractly, allowing later specialization to i.i.d. sampling, Markovian blocks, or PAGE.This separates the deterministic residual analysis from the sampling model.
  • Perturbation-level bound: The perturbation-level reduction controls the fixed-point residual using perturbation magnitudes and is used for naive Markovian-block averages.Block lengths are chosen sufficiently large to make the perturbations small.
  • Displacement-level bound: The displacement-level reduction instead controls the residual through scaled increments ∆n = βnUn − βn−1Un−1, which PAGE is designed to keep small.This remains useful when raw estimation errors are not small enough for the perturbation-level bound.
  • Displacement-level bound: Theorem 4.4 establishes a displacement-level inexact Halpern residual bound under the same non-expansiveness and stability assumptions, with Jensen’s inequality yielding the remaining statements.Its proof uses a telescoping recursion after multiplying the one-step inequality by n.
  • Method specialization: The perturbation-level bound is paired with Markovian block averages, whereas the displacement-level bound is paired with PAGE.This is the section’s reduction from residual analysis to the two sampling methods studied later.

5 The Markovian block baseline

The Markovian block baseline uses a Poisson-equation decomposition to control block errors without requiring burn-in, while affine-growth variance and trajectory stability support finite-sample guarantees. Its resulting O(ε^-5) sample complexity matches the i.i.d. non-expansive stochastic Halpern rate up to logarithmic terms but leaves an ε^-2 gap to the known Ω(ε^-3) lower bound.

  • Markovian block control: Poisson-equation decomposition makes conditional bias a boundary term of order k^-1 and conditional second moment of order k^-1, allowing blocks to start immediately.The method avoids discarding a burn-in segment before each block.
  • Variance condition: Affine-growth variance, combined with trajectory stability, quantitatively controls oracle variances at the algorithm’s random query points.Uniformly bounded variance is recovered when σ1 = 0, while affine growth is motivated by TD and distributional TD updates.
  • Sample accounting: O(N^5) total Markovian samples arise because retained block lengths contribute O(N^5), while the allowed burn-in schedule contributes O(N log N).Each iteration uses exactly b_n + k_n Markovian samples.
  • Lower-bound comparison: O(ε^-5) matches the Bravo and Contreras (2026) i.i.d. non-expansive stochastic Halpern rate up to logarithmic terms, but Ω(ε^-3) is a lower bound for the considered algorithm class.Because i.i.d. sampling is a special case of Markovian sampling, the same lower bound applies to the Markovian class up to logarithmic terms.

6 Markovian PAGE-Halpern in Hilbert spaces

The Hilbert-space PAGE-Halpern method exploits same-state differences from a continuing Markov trajectory and analyzes them via the Poisson equation. Under the PAGE-compatible oracle condition, it improves the leading accuracy dependence of Markovian sample complexity from O(ε^-5) to O(ε^-3).

  • Motivation: O(ε^-5) sample complexity arises for the baseline method because block averages must use sizes k_n of order n^4 to control accumulated perturbations.Ordinary averaging reduces standard deviation only as k^-1/2, while the nth block error must be of order n^-2.
  • Variance reduction: Same-state difference access enables a recursive PAGE estimator that reuses observed Markov samples at nearby query points.The estimator requires stationary second-moment control and same-sample difference second-moment control under Condition 6.1.
  • Hilbert-space geometry: Cocoercivity of F = I − T in Hilbert spaces provides the residual control needed to combine the PAGE estimator with Halpern iteration.For non-expansive T, F is monotone and 1/2-cocoercive, and the fixed-point residual equals the operator norm of F(x).
  • Algorithm: The recursion uses refresh blocks with probability p_n and same-state difference blocks otherwise, with block lengths selected after the branch but before observing states within the block.The estimator is updated along one continuing Markov trajectory, and the block choices are measurable before the next Markovian block starts.
  • Analysis: The Poisson-equation decomposition recovers a martingale-difference component for Markovian block averages while adding conditional boundary-term bias of order S^-1.The random component retains the usual S^-1 second-moment scaling.
  • Main result: O(ε^-3) is the leading target-accuracy dependence of the expected Markovian sample complexity under the stated assumptions and block-size schedules.The guarantee applies to the continuing trajectory when Assumptions 3.1, 3.2 and Condition 6.1 hold.

7 Markovian PAGE-Halpern in Banach spaces

This section develops a Markovian PAGE-Halpern method for estimating Tx directly under a Banach-space oracle condition. The resulting method achieves leading target-accuracy dependence of ˜O(ϵ−3), while accommodating non-Euclidean geometries through norm comparison.

  • Oracle and estimator: The recursive estimator targets Tx rather than F(x), requiring a PAGE-compatible Markovian oracle condition on the stochastic operator H.The condition permits multi-point access, evaluating H(x,Y) and H(z,Y) after observing the same state Y.
  • Algorithm: The algorithm uses refresh blocks and same-state difference blocks along one continuing Markovian trajectory, producing a recursive PAGE estimator of Tx.At iteration n, a refresh estimator is selected with probability p_n, while the difference estimator is selected with probability 1−p_n.
  • Main guarantee: Theorem 7.4 establishes Markovian PAGE-Halpern guarantees in the non-expansiveness norm under the stated assumptions and oracle condition.The theorem uses the block-size schedules from Lemma 7.3 and the stability constant κ := κ_2.
  • Complexity: ˜O(ϵ−3) is the leading dependence on the target accuracy for the expected Markovian sample complexity.Samples are generated by the continuing trajectory, with refresh and difference-block costs combined in the theorem’s total complexity bound.
  • Norm dependence: Norm-comparison constants enter when Euclidean estimator bounds are converted to the working norm, and for ℓ∞ and block-sup norms satisfy µ∥·∥≤1.For the span seminorm, the comparison factor is bounded by µ∥·∥≤2 before quotient normalization.

8 High-probability guarantees

The section develops high-probability guarantees for Banach-space PAGE-Halpern by measuring recursive estimator concentration in an auxiliary smooth norm. It derives concentration for Markovian refresh and difference blocks, then combines these with pathwise displacement bounds to control the final residual and sample usage.

  • Estimator concentration: High-probability analysis measures the recursive estimator in an auxiliary smooth norm because general-norm martingale concentration requires norm smoothness.The working fixed-point geometry is preserved, including through smoothing for non-smooth sup, block-sup, and ℓ1 norms.
  • Estimator concentration: With probability at least 1 −η, smooth-norm Markovian block tails yield simultaneous high-probability estimates for refresh and same-state difference blocks.The estimates apply conditionally to measurable stopping times, query points, and block lengths, using the Poisson equation and martingale concentration.
  • PAGE-Halpern recursion: With probability at least 1 −η, the prescribed PAGE-Halpern block schedules provide uniform recursive-estimator control through horizon N and the associated weighted refresh-frequency bounds.The proof obtains a simultaneous block event by conditional estimates and a union bound, then controls accumulated difference and refresh contributions.
  • Final guarantee: Under pathwise stability, the high-probability Markovian PAGE-Halpern theorem ensures ∥x_N − T x_N∥ ≤ ϵ with probability at least 1 −η.The same event also bounds the number of Markovian samples used through time N.

9 Experiments

Experiments compare block Halpern with Hilbert and Banach PAGE methods on shared Markovian trajectories, using linear Euclidean and nonlinear sup-norm control problems with computable residuals. PAGE improves transition efficiency in both geometries, especially under demanding targets or slower mixing.

  • Experimental design: Two eight-state examples share the same Markov chain and transition noise, enabling direct comparison between a linear Euclidean problem and a nonlinear sup-norm problem.The second example adds actions and maximization without changing the state process, while exact solutions allow residuals to be computed without numerical approximation.
  • Overall findings: Both PAGE constructions operate on one continuing trajectory and improve transition efficiency in their respective geometries, with same-state differences increasingly useful for demanding targets or slower mixing.The experiments compare methods both at fixed transition budgets and at fixed residual targets.
  • Experimental design: The Hilbert problem uses a Bellman operator that is non-expansive in the Euclidean norm, while the control operator is non-expansive in the sup norm but not any inner-product norm.This places the two experiments within the respective Hilbert and Banach theories.
  • Policy evaluation: At B = 128,000, median Hilbert PAGE residual is 0.00515 versus 0.0290 for block Halpern on policy evaluation.On the slower chain, Hilbert PAGE reaches residuals 0.20, 0.10, and 0.05 after median budgets of 25,705, 62,611, and 107,374.
  • Control: At B = 128,000, median Banach PAGE and block Halpern residuals are 0.0123 and 0.0364 on the faster control chain.On the slower control chain, Banach PAGE reaches residual 0.05 after a median of 80,000 transitions in every repetition.

10 Conclusion

The conclusion summarizes finite-sample guarantees for Markovian Halpern iteration, including improved accuracy dependence from recursive variance estimation in Hilbert and finite-dimensional Banach spaces. It also identifies the stability, Poisson-equation, and same-state reuse requirements underlying implementable online procedures.

  • Conclusion: O(log N/N) expected last-iterate residual is achieved by the direct block method with ~O(ε^-5) Markovian samples.This is the baseline finite-sample guarantee for stochastic Halpern iteration driven by one continuing Markovian trajectory.
  • Conclusion: O(ε^-3) accuracy dependence in Hilbert space and ~O(ε^-3) in finite-dimensional Banach space result from recursive variance estimation under same-state mean-square regularity.The Banach proof tracks anchored Halpern displacement increments in the norm where T is non-expansive, avoiding hidden inner-product geometry.
  • Conclusion: Stability, the Poisson equation, and reuse of one sampled Markov state at two query points define the information structure for implementable online procedures.The average-reward experiments support this implementation-oriented interpretation rather than a stationary-oracle abstraction.
Loading 2608.15966v1…