Optimal Oracle Complexity of Dual Halpern Iteration in Normed Spaces
Abstract
In this work, we study the convergence and error bounds of dual Halpern iteration for nonexpansive operators in normed spaces. First, we show that dual Halpern iteration exhibits the same optimal residual rate as Halpern iteration in the deterministic setting through a direct convergence analysis. With inexact operator evaluations, we also conduct a convergence analysis in normed spaces and derive the robust error bound of inexact dual Halpern iteration. Based on this robustness result, we study the oracle complexity of stochastic dual Halpern iteration in (ℛd,|·|p) for p∈(1,∞], using an unbiased stochastic oracle with bounded variance σ2. Notably, for p∈[2,∞], our method achieves an oracle complexity of O(ε−1+σ2ε−3) in its dependence on ε and σ, which matches the lower bound for the case p=∞ without a logarithmic gap in the dependence on ε.
Related
- Optimal Oracle Complexity for Finite-Sum Monotone Inclusions
- A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Maps
- On the Optimal Linear Minimization Oracle Complexity of Active-Hull Methods for Minimizing Convex Hölder Smooth Functions
- Optimal Deterministic First-Order Oracle Complexity for Nonconvex-Concave Minimax Optimization
- Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity
BibTeX
@misc{lee2026optimal,
title = {{Optimal Oracle Complexity of Dual Halpern Iteration in Normed Spaces}},
author = {Jongmin Lee},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26484},
eprint = {2610.26484},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26484},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal Oracle Complexity of Dual Halpern Iteration in Normed Spaces
AU - Jongmin Lee
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.26484
UR - https://arxiv.org/abs/2610.26484
AB - In this work, we study the convergence and error bounds of dual Halpern iteration for nonexpansive operators in normed spaces. First, we show that dual Halpern iteration exhibits the same optimal residual rate as Halpern iteration in the deterministic setting through a direct convergence analysis. With inexact operator evaluations, we also conduct a convergence analysis in normed spaces and derive the robust error bound of inexact dual Halpern iteration. Based on this robustness result, we study the oracle complexity of stochastic dual Halpern iteration in (ℛ^d,|·|_p) for p∈(1,∞], using an unbiased stochastic oracle with bounded variance σ^2. Notably, for p∈[2,∞], our method achieves an oracle complexity of O(ε^−1+σ^2ε^−3) in its dependence on ε and σ, which matches the lower bound for the case p=∞ without a logarithmic gap in the dependence on ε.
ER -