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

Abstract

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.

References in corpus (12)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A Universal Catalyst for First-Order Optimization
• A Lyapunov Analysis of Momentum Methods in Optimization
• Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
• A geometric alternative to Nesterov's accelerated gradient descent
• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
• Generalizing the optimized gradient method for smooth convex minimization
• On Symplectic Optimization
• Integration Methods and Accelerated Optimization Algorithms
• Accelerated Proximal Point Method for Maximally Monotone Operators
• Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities

Cited by in corpus (5)

• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
• Extragradient Method: $O(1/K)$ Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity
• Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums
• A Geometric Structure of Acceleration and Its Role in Making Gradients Small Fast
• Optimal First-Order Algorithms as a Function of Inequalities