H-invariance theory: a complete characterization of minimax optimal fixed-point algorithms
Mathematical Programming · 21.08.2026
DOI: 10.1007/s10107-026-02414-5 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematical Programming, online erschienen am 21.08.2026. Verfasst von TaeHo Yoon und 2 weiteren Autor:innen. Die Arbeit nennt 32 Literaturangaben. Gefördert von: Air Force Office of Scientific Research, Alfred P. Sloan Foundation.
Abstract (Originalsprache)
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 exactly minimax optimal convergence rates. 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, of which nonnegativity 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.
Förderung
- Air Force Office of Scientific Research
- Alfred P. Sloan Foundation
Zitieren
APA
Yoon, T., Ryu, E. K., & Grimmer, B. (2026). H-invariance theory: a complete characterization of minimax optimal fixed-point algorithms. Mathematical Programming. https://doi.org/10.1007/s10107-026-02414-5
Vancouver
Yoon T, Ryu EK, Grimmer B. H-invariance theory: a complete characterization of minimax optimal fixed-point algorithms. Mathematical Programming. 2026. doi:10.1007/s10107-026-02414-5
BibTeX
@article{Yoon2026,
author = {Yoon, TaeHo and Ryu, Ernest K. and Grimmer, Benjamin},
title = {H-invariance theory: a complete characterization of minimax optimal fixed-point algorithms},
journal = {Mathematical Programming},
year = {2026},
doi = {10.1007/s10107-026-02414-5}
}
EUVIMED