mlsanityData to 7 Oct 2026

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

arXiv 2101.12101 ↗First posted 28 Jan 2021math.OC cs.DS cs.LGcited by 4

Not on the map. Why?

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.

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

Builds on

30 of 57 references.

References · 30

  1. 2015A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insightscited by 203
  2. 2017Lower Bounds for Finding Stationary Points Icited by 125
  3. 2016A Variational Perspective on Accelerated Methods in Optimizationcited by 108
  4. 2014Analysis and Design of Optimization Algorithms via Integral Quadratic Constraintscited by 105
  5. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 75
  6. 2018Understanding the Acceleration Phenomenon via High-Resolution Differential Equationscited by 68
  7. 2017A First Order Method for Solving Convex Bi-Level Optimization Problemscited by 67
  8. 2020Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitiescited by 60
  9. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 59
  10. 2014Linear Coupling: An Ultimate Unification of Gradient and Mirror Descentcited by 58
  11. 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 55
  12. 2015A Universal Catalyst for First-Order Optimizationcited by 54
18 more
  1. 2016A Lyapunov Analysis of Momentum Methods in Optimizationcited by 28
  2. 2017The Approximate Duality Gap Technique: A Unified Theory of First-Order Methodscited by 27
  3. 2019First-order optimization algorithms via inertial systems with Hessian driven dampingcited by 22
  4. 2015A geometric alternative to Nesterov's accelerated gradient descentcited by 21
  5. 2018Direct Runge-Kutta Discretization Achieves Accelerationcited by 21
  6. 2015Exact Worst-case Performance of First-order Methods for Composite Convex Optimizationcited by 16
  7. 2018Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functionscited by 14
  8. 2018Primal-dual accelerated gradient methods with small-dimensional relaxation oraclecited by 14
  9. 2019Generalized Momentum-Based Methods: A Hamiltonian Perspectivecited by 12
  10. 2016On the Iteration Complexity of Oblivious First-Order Optimization Algorithmscited by 9
  11. 2017Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3cited by 9
  12. 2017Control Interpretations for First-Order Optimization Methodscited by 8
  13. 2017Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Methodcited by 8
  14. 2017Integration Methods and Accelerated Optimization Algorithmscited by 6
  15. 2016An optimal first order method based on optimal quadratic averagingcited by 5
  16. 2016Generalizing the optimized gradient method for smooth convex minimizationcited by 5
  17. 2019Nearly optimal first-order methods for convex optimization under gradient norm measure: An adaptive regularization approachcited by 4
  18. 2019Accelerated Proximal Point Method for Maximally Monotone Operatorscited by 2

Built on by

Cited by year

Citing papers per year: 2021: 3; 2022: 1.

4 papers.

  1. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 44
  2. 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
  3. 2022Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusionscited by 17
  4. 2021Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sumscited by 4