Perturbed Fenchel duality and first-order methods

2018/12/26 by Gutman, David H., Peña, Javier F. · 1 citation
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1812.10198

Abstract

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.

Cited by

• First-order and interior-point methods for entanglement detection

Related

• Perturbed Fenchel Duality and Primal-Dual Convergence of First-Order Methods
• Potential-Function Proofs for First-Order Methods
• Optimal First-Order Algorithms as a Function of Inequalities
• Tight Convergence Rate in Subgradient Norm of the Proximal Point Algorithm
• General Holder Smooth Convergence Rates Follow From Specialized Rates Assuming Growth Bounds