Theory of Computing
-------------------
Title     : Potential-Function Proofs for Gradient Methods
Authors   : Nikhil Bansal and Anupam Gupta
Volume    : 15
Number    : 4
Pages     : 1-32
URL       : https://theoryofcomputing.org/articles/v015a004

Abstract
--------

This note discusses proofs of convergence for gradient methods (also
called "first-order methods") based on simple potential-function
arguments.  We cover methods like gradient descent (for both smooth
and non-smooth settings), mirror descent, and some accelerated
variants. We hope the structure and presentation of these
amortized-analysis proofs will be useful as a guiding principle
in learning and using these proofs.