Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2511.14915 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917090331459584 |
|---|---|
| author | Yoon, TaeHo Ryu, Ernest K. Grimmer, Benjamin |
| author_facet | Yoon, TaeHo Ryu, Ernest K. Grimmer, Benjamin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_14915 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | H-invariance theory: A complete characterization of minimax optimal fixed-point algorithms Yoon, TaeHo Ryu, Ernest K. Grimmer, Benjamin Optimization and Control 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. |
| title | H-invariance theory: A complete characterization of minimax optimal fixed-point algorithms |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2511.14915 |