Optimized first-order methods for smooth convex minimization

Abstract

We introduce new optimized first-order methods for smooth unconstrained convex minimization. Drori and Teboulle recently described a numerical method for computing the $N$-iteration optimal step coefficients in a class of first-order algorithms that includes gradient methods, heavy-ball methods, and Nesterov's fast gradient methods. However, Drori and Teboulle's numerical method is computationally expensive for large $N$, and the corresponding numerically optimized first-order algorithm requires impractical memory and computation for large-scale optimization problems. In this paper, we propose optimized first-order algorithms that achieve a convergence bound that is two times smaller than for Nesterov's fast gradient methods; our bound is found analytically and refines the numerical bound. Furthermore, the proposed optimized first-order methods have efficient recursive forms that are remarkably similar to Nesterov's fast gradient methods.

References in corpus (3)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• Optimized first-order methods for smooth convex minimization
• Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods

Cited by in corpus (48)

• The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than $1/k^2$
• Optimized first-order methods for smooth convex minimization
• Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
• Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)
• Acceleration Methods
• Relaxed Linearized Algorithms for Faster X-Ray CT Image Reconstruction
• Generalizing the optimized gradient method for smooth convex minimization
• Adaptive Restart of the Optimized Gradient Method for Convex Optimization
• On the convergence analysis of the optimized gradient method
• Optimal Complexity and Certification of Bregman First-Order Methods
• Efficient First-order Methods for Convex Minimization: a Constructive Approach
• Universal gradient descent
• Data-driven nonsmooth optimization
• Adaptive Gradient Descent without Descent
• Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functions
• From Nesterov's Estimate Sequence to Riemannian Acceleration
• Optimization methods for MR image reconstruction (long version)
• Potential-Function Proofs for First-Order Methods
• Optimal Deterministic Algorithm Generation
• On-line Non-Convex Constrained Optimization
• Accelerated Proximal Point Method for Maximally Monotone Operators
• Bounds for the tracking error of first-order online optimization methods
• Accelerated Additive Schwarz Methods for Convex Optimization with Adaptive Restart
• Automatic Performance Estimation for Decentralized Optimization
• Automated Worst-Case Performance Analysis of Decentralized Gradient Descent
• 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
• Automated Performance Estimation for Decentralized Optimization via Network Size Independent Problems
• A Unifying Framework of Accelerated First-Order Approach to Strongly Monotone Variational Inequalities
• On the Optimal Ergodic Sublinear Convergence Rate of the Relaxed Proximal Point Algorithm for Variational Inequalities
• Variational phase recovering without phase unwrapping in phase-shifting interferometry
• Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operators
• Fast Gradient Methods for Uniformly Convex and Weakly Smooth Problems
• Accelerated Minimax Algorithms Flock Together
• Incorporating the Barzilai-Borwein Adaptive Step Size into Sugradient Methods for Deep Network Training
• Exact worst-case convergence rates of the proximal gradient method for composite convex minimization
• Computer-Assisted Design of Accelerated Composite Optimization Methods: OptISTA
• Proximal bundle algorithms for nonsmooth convex optimization via fast gradient smooth methods
• Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods
• Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums
• Optimal First-Order Algorithms as a Function of Inequalities
• A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip
• Dual Optimization for Kolmogorov Model Learning Using Enhanced Gradient Descent
• Convex optimization
• An optimal variant of Kelley's cutting-plane method
• A Continuized View on Nesterov Acceleration
• 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)