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

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 Õ(ε⁻⁵) 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(ε⁻³) 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 Õ(ε⁻³) sample complexity. We also establish a high-probability guarantee with the same leading accuracy dependence by measuring the estimator in an auxiliary smooth norm.

Optimal Oracle Complexity of Dual Halpern Iteration in Normed Spaces
Jongmin Lee
arXiv19 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Weak and Strong Convergence of an Implicit Iteration for Hemi-Contractive Semigroups in Banach Spaces
Ferit Gürbüz
arXiv17 Oct 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv
An Accurate Zeroth-Order Perturbation Theory for Solving Power-Law Potentials within the Framework of the Asymptotic Iteration Method
A. J. Sous, Ibsal Assi, Nasser Saad
arXiv17 Oct 2026PreprintCC0Full textMathematical physicsarXiv
Finite-Sample Theory for Fitted Q-Iteration When Actions Are Functions
Gefei Lin, Rui Miao, Xiaoke Zhang
arXiv28 Sep 2026PreprintarXiv licenceFull textStatisticsarXiv
A Sharp Finite-Iteration Theory for Asynchronous Categorical Distributional Temporal-Difference Learning
Ege C. Kaya, Abolfazl Hashemi
arXiv6 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{kaya2026banachspace,
  title = {{A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Maps}},
  author = {Ege C. Kaya and Arda Fazla and M. Berk Sahin and Abolfazl Hashemi},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2608.15966},
  eprint = {2608.15966},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.15966},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Maps
AU  - Ege C. Kaya
AU  - Arda Fazla
AU  - M. Berk Sahin
AU  - Abolfazl Hashemi
PY  - 2026
DA  - 2026/09/25
PB  - arXiv
DO  - 10.48550/arxiv.2608.15966
UR  - https://arxiv.org/abs/2608.15966
AB  - 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 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 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.
ER  -

Abstract

Related

Cite