提出改进的随机迭代方法，高效求解非扩张算子不动点问题。
A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Maps
- 基于泊松方程分析马尔可夫轨迹中的方差缩减策略
- 在有限维巴拿赫空间中实现 $\tilde O(ε^{-3})$ 的样本复杂度
- 适用于非光滑空间，且提供高概率收敛保证
研究当查询样本来自持续马尔可夫轨迹时，非扩张算子不动点的随机逼近问题。直接块小批量实现的哈尔珀恩迭代期望末次迭代残差为 $O(\log N/N)$，但需 $\tilde O(ε^{-5})$ 次马尔可夫样本。为此，提出方差缩减的马尔可夫 PAGE-Halpern 方法，其刷新与同状态差分块通过泊松方程分析。在希尔伯特空间中，$I-T$ 的共强制性带来 $O(ε^{-3})$ 样本复杂度。主要结果将此构造扩展至一般有限维巴拿赫空间。以位移水平的哈尔珀恩界替代希尔伯特空间势函数，在原始非扩张范数下获得 $\tilde O(ε^{-3})$ 样本复杂度。通过辅助光滑范数测量估计器，建立相同主导精度依赖的高概率保证。非光滑上确界与块上确界几何通过范数平滑覆盖。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。