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.
Original language | English (US) |
---|---|
Article number | 4 |
Journal | Theory of Computing |
Volume | 15 |
DOIs | |
State | Published - Sep 2019 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Computational Theory and Mathematics