On the convergence analysis of the optimized gradient method

Abstract

This paper considers the problem of unconstrained minimization of smooth convex functions having Lipschitz continuous gradients with known Lipschitz constant. We recently proposed an optimized gradient method (OGM) for this problem and showed that it has a worst-case convergence bound for the cost function decrease that is twice as small as that of Nesterov's fast gradient method (FGM), yet has a similarly efficient practical implementation. Drori showed recently that OGM has optimal complexity over the general class of first-order methods. This optimality makes it important to study fully the convergence properties of OGM. The previous worst-case convergence bound for OGM was derived for only the last iterate of a secondary sequence. This paper provides an analytic convergence bound for the primary sequence generated by OGM. We then discuss additional convergence properties of OGM, including the interesting fact that OGM has two types of worst-case functions: a piecewise affine-quadratic function and a quadratic function. These results help complete the theory of optimal first-order methods for smooth convex minimization.

References in corpus (2)

• Convex Optimization for Big Data
• Exact Worst-case Performance of First-order Methods for Composite Convex Optimization

Cited by in corpus (14)

• Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
• Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)
• Acceleration Methods
• Generalizing the optimized gradient method for smooth convex minimization
• Adaptive Restart of the Optimized Gradient Method for Convex Optimization
• The Practicality of Stochastic Optimization in Imaging Inverse Problems
• Bilevel methods for image reconstruction
• Efficient First-order Methods for Convex Minimization: a Constructive Approach
• Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functions
• Optimal Nonergodic Sublinear Convergence Rate of Proximal Point Algorithm for Maximal Monotone Inclusion Problems
• Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule
• On the Optimal Ergodic Sublinear Convergence Rate of the Relaxed Proximal Point Algorithm for Variational Inequalities
• Computer-Assisted Design of Accelerated Composite Optimization Methods: OptISTA
• A piecewise conservative method for unconstrained convex optimization