Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functions
arXiv:1803.06600
Abstract
This paper optimizes the step coefficients of first-order methods for smooth convex minimization in terms of the worst-case convergence bound (i.e., efficiency) of the decrease in the gradient norm. This work is based on the performance estimation problem approach. The worst-case gradient bound of the resulting method is optimal up to a constant for large-dimensional smooth convex minimization problems, under the initial bounded condition on the cost function value. This paper then illustrates that the proposed method has a computationally efficient form that is similar to the optimized gradient method.
References in corpus (5)
- Optimized first-order methods for smooth convex minimization
- Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)
- Generalizing the optimized gradient method for smooth convex minimization
- How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD
- On the convergence analysis of the optimized gradient method
Cited by in corpus (6)
- Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
- 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
- Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities
- Nearly optimal first-order methods for convex optimization under gradient norm measure: An adaptive regularization approach