Generalizing the optimized gradient method for smooth convex minimization

Abstract

This paper generalizes the optimized gradient method (OGM) that achieves the optimal worst-case cost function bound of first-order methods for smooth convex minimization. Specifically, this paper studies a generalized formulation of OGM and analyzes its worst-case rates in terms of both the function value and the norm of the function gradient. This paper also develops a new algorithm called OGM-OG that is in the generalized family of OGM and that has the best known analytical worst-case bound with rate $O(1/N^{1.5})$ on the decrease of the gradient norm among fixed-step first-order methods. This paper also proves that Nesterov's fast gradient method has an $O(1/N^{1.5})$ worst-case gradient norm rate but with constant larger than OGM-OG. The proof is based on the worst-case analysis called Performance Estimation Problem.

References in corpus (3)

• Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
• Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)
• On the convergence analysis of the optimized gradient method

Cited by in corpus (17)

• Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)
• Acceleration Methods
• SPULTRA: Low-Dose CT Image Reconstruction with Joint Statistical and Learned Image Models
• Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functions
• Accelerated Proximal Point Method for Maximally Monotone Operators
• Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization
• Optimal Nonergodic Sublinear Convergence Rate of Proximal Point Algorithm for Maximal Monotone Inclusion Problems
• On the Optimal Ergodic Sublinear Convergence Rate of the Relaxed Proximal Point Algorithm for Variational Inequalities
• Fast Gradient Methods for Uniformly Convex and Weakly Smooth Problems
• Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums
• Optimal First-Order Algorithms as a Function of Inequalities
• A Geometric Structure of Acceleration and Its Role in Making Gradients Small Fast
• SUPER Learning: A Supervised-Unsupervised Framework for Low-Dose CT Image Reconstruction
• Nearly optimal first-order methods for convex optimization under gradient norm measure: An adaptive regularization approach
• New reconstruction and data processing methods for regression and interpolation analysis of multidimensional big data
• Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates
• A New Class of Composite Objective Multi-step Estimating-sequence Techniques (COMET)