
EC
Ege C. Kaya, Arda Fazla, M. Berk Sahin, Abolfazl Hashemi
· 1 min read
ResearcharXiv cs.LG
A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Maps
arXiv:2608.15966v2 Announce Type: replace
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(\epsilon^{-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(\epsilon^{-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(\epsilon^{-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.
Original source
This story was published by arXiv cs.LG and written by Ege C. Kaya, Arda Fazla, M. Berk Sahin, Abolfazl Hashemi. SyncAI.news shows a preview; the complete article is on the publisher's site.
Read the full story on arxiv.org


