Metraipolis › archive › dc_8b266b2cabe4
On Minimax Optimality and Uniqueness of Fixed-Step First-Order Methods for Smooth Convex Optimization — arXiv:2609.07671
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.07671
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T14:29:40.278Z
- SHA-256 of the archived text
c74d05c8e83f35066cf47526b978479376f177ab9320341c408abb659ad12dcc- Stable URL of this page
https://metraipolis.com/documento/dc_8b266b2cabe4
How to cite
On Minimax Optimality and Uniqueness of Fixed-Step First-Order Methods for Smooth Convex Optimization — arXiv:2609.07671 — arXiv (en), https://arxiv.org/abs/2609.07671 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8b266b2cabe4 (Metraipolis archive dc_8b266b2cabe4, sha256 c74d05c8e83f35066cf47526b978479376f177ab9320341c408abb659ad12dcc)
BibTeX
@misc{dc8b266b2cabe4,
title = {On Minimax Optimality and Uniqueness of Fixed-Step First-Order Methods for Smooth Convex Optimization — arXiv:2609.07671},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.07671},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8b266b2cabe4; sha256 c74d05c8e83f35066cf47526b978479376f177ab9320341c408abb659ad12dcc},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.07671. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
This paper considers the design of optimal fixed-step first-order methods for high-dimensional minimization of $L$-smooth convex functions. For optimizing worst-case performance measured via suboptimality of the final function value (relative to the initial squared distance to a minimizer), we provide an algebraic proof of the optimality of the optimized gradient method (OGM) and establish its uniqueness among all fixed-step first-order methods. For the alternative measure of final squared gradient norm (relative to initial suboptimality), we prove the OGM-G method is optimal and uniquely so among fixed-step first-order methods. Finally, for the setting measuring the final squared gradient norm (relative to the initial squared distance to a minimizer), we show the recently proposed Lemniscate method is optimal and uniquely so. Our proofs rely on algebraic reductions for lower bound arguments rather than traditional information-theoretic bounds, which were previously only able to establish OGM's optimality but not uniqueness. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in math.OC). Categorie arXiv: Optimization and Control (math.OC). Pagina del lavoro: https://arxiv.org/abs/2609.07671 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T14:09:21.693Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).