# Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization

arXiv: https://arxiv.org/abs/2101.12101 · HTML: https://mlsanity.com/paper/2101.12101/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 57 references that are in the map.
- First posted on arXiv 28 Jan 2021.

## Builds on (most cited first, 30 of 30)

- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [A Variational Perspective on Accelerated Methods in Optimization](https://mlsanity.com/paper/1603.04245/) (2016)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Understanding the Acceleration Phenomenon via High-Resolution Differential Equations](https://mlsanity.com/paper/1810.08907/) (2018)
- [A First Order Method for Solving Convex Bi-Level Optimization Problems](https://mlsanity.com/paper/1702.03999/) (2017)
- [Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities](https://mlsanity.com/paper/2002.08872/) (2020)
- [Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2002.00057/) (2020)
- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [A Lyapunov Analysis of Momentum Methods in Optimization](https://mlsanity.com/paper/1611.02635/) (2016)
- [The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods](https://mlsanity.com/paper/1712.02485/) (2017)
- [A geometric alternative to Nesterov's accelerated gradient descent](https://mlsanity.com/paper/1506.08187/) (2015)
- [First-order optimization algorithms via inertial systems with Hessian driven damping](https://mlsanity.com/paper/1907.10536/) (2019)
- [Direct Runge-Kutta Discretization Achieves Acceleration](https://mlsanity.com/paper/1805.00521/) (2018)
- [Exact Worst-case Performance of First-order Methods for Composite Convex Optimization](https://mlsanity.com/paper/1512.07516/) (2015)
- [Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functions](https://mlsanity.com/paper/1803.06600/) (2018)
- [Primal-dual accelerated gradient methods with small-dimensional relaxation oracle](https://mlsanity.com/paper/1809.05895/) (2018)
- [Generalized Momentum-Based Methods: A Hamiltonian Perspective](https://mlsanity.com/paper/1906.00436/) (2019)
- [On the Iteration Complexity of Oblivious First-Order Optimization Algorithms](https://mlsanity.com/paper/1605.03529/) (2016)
- [Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3](https://mlsanity.com/paper/1706.05671/) (2017)
- [Control Interpretations for First-Order Optimization Methods](https://mlsanity.com/paper/1703.01670/) (2017)
- [Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method](https://mlsanity.com/paper/1706.04680/) (2017)
- [Integration Methods and Accelerated Optimization Algorithms](https://mlsanity.com/paper/1702.06751/) (2017)
- [An optimal first order method based on optimal quadratic averaging](https://mlsanity.com/paper/1604.06543/) (2016)
- [Generalizing the optimized gradient method for smooth convex minimization](https://mlsanity.com/paper/1607.06764/) (2016)
- [Nearly optimal first-order methods for convex optimization under gradient norm measure: An adaptive regularization approach](https://mlsanity.com/paper/1912.12004/) (2019)
- [Accelerated Proximal Point Method for Maximally Monotone Operators](https://mlsanity.com/paper/1905.05149/) (2019)

## Built on by (most cited first, 4 of 4)

- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity](https://mlsanity.com/paper/2110.04261/) (2021)
- [Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions](https://mlsanity.com/paper/2203.09436/) (2022)
- [Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums](https://mlsanity.com/paper/2105.12062/) (2021)

## Abstract (arXiv)

Making the gradients small is a fundamental optimization problem that has eluded unifying and simple convergence arguments in first-order optimization, so far primarily reserved for other convergence criteria, such as reducing the optimality gap. We introduce a novel potential function-based framework to study the convergence of standard methods for making the gradients small in smooth convex optimization and convex-concave min-max optimization. Our framework is intuitive and it provides a lens for viewing algorithms that make the gradients small as being driven by a trade-off between reducing either the gradient norm or a certain notion of an optimality gap. On the lower bounds side, we discuss tightness of the obtained convergence results for the convex setup and provide a new lower bound for minimizing norm of cocoercive operators that allows us to argue about optimality of methods in the min-max setup.