Potential-function proofs for gradient methods

Nikhil Bansal, Anupam Gupta

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Article number4
JournalTheory of Computing
StatePublished - Sep 2019

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics


Dive into the research topics of 'Potential-function proofs for gradient methods'. Together they form a unique fingerprint.

Cite this