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).