Potential Function-Based Framework for Minimizing Gradients in Convex and Min-Max Optimization
From MaRDI portal
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.
Recommendations
- Optimization methods for computing global minima of nonconvex potential energy functions
- Potential-function proofs for gradient methods
- scientific article; zbMATH DE number 703004
- scientific article; zbMATH DE number 679860
- Minimizing convex functions by continuous descent methods
- scientific article; zbMATH DE number 1421262
- Generalizing the optimized gradient method for smooth convex minimization
- An optimal gradient method for smooth strongly convex minimization
- Functional optimization through semilocal approximate minimization
- Minimisation de fonctionnelles dans un ensemble de fonctions convexes
Cites work
- A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
- A first order method for solving convex bilevel optimization problems
- A modification of the Arrow-Hurwicz method for search of saddle points
- A variational perspective on accelerated methods in optimization
- Accelerated extra-gradient descent: a novel accelerated first-order method
- An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods
- An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization
- An optimal first order method based on optimal quadratic averaging
- Analysis and design of optimization algorithms via integral quadratic constraints
- Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
- Convex analysis and monotone operator theory in Hilbert spaces
- Dual extrapolation and its applications to solving variational inequalities and related problems
- Exact worst-case performance of first-order methods for composite convex optimization
- First-order optimization algorithms via inertial systems with Hessian driven damping
- Fixed points of nonexpanding maps
- Generalized momentum-based methods: a Hamiltonian perspective
- Generalizing the optimized gradient method for smooth convex minimization
- Gradient methods for minimizing composite functions
- scientific article; zbMATH DE number 1807400 (Why is no real title available?)
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 1487987 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- scientific article; zbMATH DE number 3371284 (Why is no real title available?)
- scientific article; zbMATH DE number 3376275 (Why is no real title available?)
- scientific article; zbMATH DE number 3381034 (Why is no real title available?)
- scientific article; zbMATH DE number 3108780 (Why is no real title available?)
- Information-based complexity of linear operator equations
- Lectures on convex optimization
- Linear coupling: an ultimate unification of gradient and mirror descent
- Lower bounds for finding stationary points I
- Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
- Mean Value Methods in Iteration
- Nearly optimal first-order methods for convex optimization under gradient norm measure: an adaptive regularization approach
- On lower and upper bounds in smooth and strongly convex optimization
- On optimality of Krylov's information when solving linear operator equations
- On the convergence rate of the Halpern-iteration
- Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions
- Performance of first-order methods for smooth convex minimization: a novel approach
- Potential-function proofs for gradient methods
- Primal-dual accelerated gradient methods with small-dimensional relaxation oracle
- Produits infinis de resolvantes
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3
- Smooth strongly convex interpolation and exact worst-case performance of first-order methods
- The approximate duality gap technique: a unified theory of first-order methods
- The exact information-based complexity of smooth convex minimization
- THE HEAVY BALL WITH FRICTION METHOD, I. THE CONTINUOUS DYNAMICAL SYSTEM: GLOBAL EXPLORATION OF THE LOCAL MINIMA OF A REAL-VALUED FUNCTION BY ASYMPTOTIC ANALYSIS OF A DISSIPATIVE DYNAMICAL SYSTEM
- Tight sublinear convergence rate of the proximal point algorithm for maximal monotone inclusion problems
- Unified acceleration of high-order algorithms under general Hölder continuity
- Worst-case convergence analysis of inexact gradient and Newton methods through semidefinite programming performance estimation
Cited in
(5)- Potential-function proofs for gradient methods
- Smooth monotone stochastic variational inequalities and saddle point problems: a survey
- On the convergence of broadcast incremental algorithms with applications
- Accelerated minimax algorithms flock together
- An inexact Halpern iteration with application to distributionally robust optimization
This page was built for publication: Potential Function-Based Framework for Minimizing Gradients in Convex and Min-Max Optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5093649)
