EUVIMEDEUVIMED entdecken
Crossref

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

TaeHo Yoon, Ernest K. Ryu, Benjamin Grimmer

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →