Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization
This work addresses a fundamental gap in first-order optimization theory for researchers and practitioners, offering a novel framework to analyze gradient reduction, though it appears incremental in extending existing convergence criteria.
The paper tackles the problem of making gradients small in convex and min-max optimization, which lacks unifying convergence arguments, by introducing a potential function-based framework that provides intuitive convergence analysis and discusses tightness of results, including a new lower bound for cocoercive operators.
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.