Adrien Taylor, Yoel Drori
Published 2021-01-24Version 1
We present an optimal gradient method for smooth (possibly strongly) convex optimization. The method is optimal in the sense that its worst-case bound exactly matches the lower bound on the oracle complexity for the class of problems, meaning that no black-box first-order method can have a better worst-case guarantee without further assumptions on the class of problems at hand. The method is in some sense a generalization of the Optimized Gradient Method of Kim and Fessler (2016), and asymptotically corresponds to the Triple Momentum Method (Van Scoy et al., 2017), in the presence of strong convexity. Furthermore, the method is numerically stable to arbitrarily large condition numbers and admits a conceptually very simple proof, which involves a Lyapunov argument and a sum of two inequalities. Finally, we provide a numerical recipe for obtaining the algorithmic parameters of the method, using semidefinite programming, and illustrate that it can be used for developing other methods as well.
Comments: Codes available at https://github.com/AdrienTaylor/Optimal-Gradient-Method (symbolic verifications and numerical experiments)
Gradient methods for convex minimization: better rates under weaker conditions
Proximal Activation of Smooth Functions in Splitting Algorithms for Convex Minimization
Fast dual proximal gradient algorithms with rate $O(1/k^{1.5})$ for convex minimization
![QR code for arXiv:2101.09741 [math.OC]](http://oss.arxitics.com/images/favicon.svg)