{"ID":2840234,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.14915","arxiv_id":"2511.14915","title":"H-invariance theory: A complete characterization of minimax optimal fixed-point algorithms","abstract":"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.","short_abstract":"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 dis...","url_abs":"https://arxiv.org/abs/2511.14915","url_pdf":"https://arxiv.org/pdf/2511.14915v1","authors":"[\"TaeHo Yoon\",\"Ernest K. Ryu\",\"Benjamin Grimmer\"]","published":"2025-11-18T21:12:49Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}