Metraipolis › archive › dc_7807117acb06

A Unified Theory of H-Duality in First-Order Methods — arXiv:2609.03281

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.03281
License (as archived)
CC0-1.0
Archived
2026-10-17T02:26:45.861Z
SHA-256 of the archived text
ddb82852e09713865da41ad132fdc194971865b515915b5f3e0905fc6d89b8b9
Stable URL of this page
https://metraipolis.com/documento/dc_7807117acb06

How to cite

A Unified Theory of H-Duality in First-Order Methods — arXiv:2609.03281 — arXiv (en), https://arxiv.org/abs/2609.03281 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7807117acb06 (Metraipolis archive dc_7807117acb06, sha256 ddb82852e09713865da41ad132fdc194971865b515915b5f3e0905fc6d89b8b9)
BibTeX
@misc{dc7807117acb06,
  title = {A Unified Theory of H-Duality in First-Order Methods — arXiv:2609.03281},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.03281},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7807117acb06; sha256 ddb82852e09713865da41ad132fdc194971865b515915b5f3e0905fc6d89b8b9},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.03281. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We provide two complementary explanations of H-duality in smooth strongly convex optimization and contractive fixed-point problems. H-duality refers to the phenomenon where the worst-case performance of many fixed-step first-order methods (FSFOMs) for a given performance setup are exactly equal to the worst-case performance of their "time-reversed" counterparts and a paired performance setup. This concept gained interest as a mechanism for automatically converting an algorithm with guarantees on the final suboptimality to algorithms with guarantees on the final gradient norm. Since its initial discovery, additional H-dual performance setup pairings have been discovered empirically, yet a general explanation for these phenomena remained elusive. Our first explanation of H-duality shows that, on a class of instances with extremal curvature properties, FSFOMs produce a final iterate that is a scalar multiple of the initial iterate, and that this scalar is invariant under the time reversal of the underlying FSFOM. This, together with the empirical observation that many FSFOMs have such an instance with extremal curvature as their worst case, gives one explanation for why H-duality often occurs. The second explanation is complementary and uses the notion of a performance estimation certificate of the convergence rate of a FSFOM. We exhibit an explicit transformation of such certificates that preserves many of the properties that define such a certificate, and we show that in many numerical and analytical examples, this transformation in fact transforms certificates of the convergence rate of an algorithm into certificates for its time-reversal. As an application, we prove a convergence guarantee for the H-dual of ITEM matching the conjectured optimal gradient-to-gradient guarantee.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-04 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.03281 — 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-17T02:07:43.331Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-04?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).