Potential-Function Proofs for First-Order Methods

Abstract

This note discusses proofs for convergence of 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.

References in corpus (1)

• A single potential governing convergence of conjugate gradient, accelerated gradient and geometric descent

Cited by in corpus (8)

• The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
• Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization
• Efficient Algorithms for Smooth Minimax Optimization
• Tight Analyses for Non-Smooth Stochastic Gradient Descent
• Tight last-iterate convergence rates for no-regret learning in multi-player games
• Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method
• A Study of Condition Numbers for First-Order Optimization
• Potential-based analyses of first-order methods for constrained and composite optimization