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

arXiv:2608.15966v1 Announce Type: new Abstract: 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 ilde 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 ilde O(epsilon^{-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.

Source: arXiv cs.LG | 2026-08-18