# Perturbed Fenchel duality and first-order methods

arXiv: https://arxiv.org/abs/1812.10198 · HTML: https://mlsanity.com/paper/1812.10198/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Dec 2018.

## Built on by (most cited first, 3 of 3)

- [No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization](https://mlsanity.com/paper/2111.11309/) (2021)
- [Local convexity of the TAP free energy and AMP convergence for Z2-synchronization](https://mlsanity.com/paper/2106.11428/) (2021)
- [Some Primal-Dual Theory for Subgradient Methods for Strongly Convex Optimization](https://mlsanity.com/paper/2305.17323/) (2023)

## Abstract (arXiv)

We show that the iterates generated by a generic first-order meta-algorithm satisfy a canonical perturbed Fenchel duality inequality. The latter in turn readily yields a unified derivation of the best known convergence rates for various popular first-order algorithms including the conditional gradient method as well as the main kinds of Bregman proximal methods: subgradient, gradient, fast gradient, and universal gradient methods.