The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
We present a general technique for the analysis of first-order methods. The technique relies on the construction of a duality gap for an appropriate approximation of the objective function, where the function approximation improves as the algorithm converges. We show that in continuous time the enforcement of an invariant, which …