2019-09-12
Potential-function proofs for gradient methods
Publication
Publication
Theory of Computing , Volume 15 p. 4
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.
| Additional Metadata | |
|---|---|
| , , | |
| doi.org/10.4086/toc.2019.v015a004 | |
| Theory of Computing | |
| Continuous Methods in Discrete Optimization | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Bansal, N., & Gupta, A. (2019). Potential-function proofs for gradient methods. Theory of Computing, 15. doi:10.4086/toc.2019.v015a004 |
|
