H-invariance theory: a complete characterization of minimax optimal fixed-point algorithms

• 成果类型: Article; Early Access
• 署名作者: Yoon, TaeHo; Ryu, Ernest K.; Grimmer, Benjamin
• 署名单位: Johns Hopkins University; University of California System; University of California Los Angeles
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02414-5
• 发表日期: 2026-08-21
• 关键词: Fixed-point problems; monotone operators; acceleration; Rates Of Convergence; Minimax Optimality; performance

摘要

For nonexpansive fixed-point problems, Halpern's method with optimal parameters, its so-called H-dual algorithm, and in fact, an infinite family of algorithms containing them, all exhibit the exact minimax optimal convergence rate. In this work, we provide a characterization of the complete, exhaustive family of distinct algorithms using predetermined step-sizes, represented as lower triangular H-matrices, which attain the same optimal convergence rate. The characterization is based on polynomials in the entries of the H-matrix that we call H-invariants, whose values stay constant over all optimal H-matrices, together with H-certificates, the nonnegativity of which precisely specifies the region of optimality within the common level set of H-invariants. The H-invariance theory we present offers a novel view of optimal acceleration in first-order optimization as a mathematical study of carefully selected invariants, certificates, and structures induced by them.