TY - JOUR
T1 - Perturbed Fenchel duality and first-order methods
AU - Gutman, David H.
AU - Peña, Javier F.
N1 - Publisher Copyright:
© 2022, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.
PY - 2023/3
Y1 - 2023/3
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85124122379&partnerID=8YFLogxK
U2 - 10.1007/s10107-022-01779-7
DO - 10.1007/s10107-022-01779-7
M3 - Article
AN - SCOPUS:85124122379
SN - 0025-5610
VL - 198
SP - 443
EP - 469
JO - Mathematical Programming
JF - Mathematical Programming
IS - 1
ER -