Perturbed Fenchel duality and first-order methods

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.

Recommended citation: Gutman, D. H., & Peña, J. F. (2023). Perturbed Fenchel duality and first-order methods. Mathematical Programming, 198, 443–469. https://doi.org/10.1007/s10107-022-01779-7