{"id":"arxiv/2608.15966","url":"https://arxiv.org/abs/2608.15966","tags":["cs.LG","math.OC"],"score":0,"title":"A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Maps","domain":"cs.LG","source":"arxiv","authors":["Ege C. Kaya","Arda Fazla","M. Berk Sahin","Abolfazl Hashemi"],"reviews":0,"subject":"cs.LG","summary":"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})$…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-16","reactions":{}}