Potential-Function Proofs for First-Order Methods

2017/12/13 by Nikhil Bansal, Anupam Gupta, Bansal, Nikhil +1 · 5 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Advanced Optimization Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques #cs.DS #cs.LG #math.OC

paper · pdf · doi:10.48550/arxiv.1712.04581

openalex publication_date 2017/12/13 · arxiv created 2019/06/02 · arxiv updated 2019/06/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

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.

Citations

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

Cited by

• A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications
• A Practical Adaptive Subgame Perfect Gradient Method
• Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions
• Potential-based analyses of first-order methods for constrained and composite optimization
• Improved Regret Guarantees for Online Mirror Descent using a Portfolio of Mirror Maps

Related

• On Fundamental Proof Structures in First-Order Optimization
• Potential-based analyses of first-order methods for constrained and composite optimization
• Accelerated First-Order Methods: Differential Equations and Lyapunov Functions
• Optimal First-Order Algorithms as a Function of Inequalities
• Lower Bounds for Finding Stationary Points II: First-Order Methods