An optimal gradient method for smooth strongly convex minimization
From MaRDI portal
Abstract: We present an optimal gradient method for smooth strongly convex optimization. The method is optimal in the sense that its worst-case bound on the distance to an optimal point 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. In addition, we provide a constructive recipe for obtaining the algorithmic parameters of the method and illustrate that it can be used for deriving methods for other optimality criteria as well.
Recommendations
- Generalizing the optimized gradient method for smooth convex minimization
- On the convergence analysis of the optimized gradient method
- Universal gradient methods for convex optimization problems
- Optimized first-order methods for smooth convex minimization
- Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions
Cites work
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A Lyapunov analysis of accelerated methods in optimization
- Analysis and design of optimization algorithms via integral quadratic constraints
- Efficient first-order methods for convex minimization: a constructive approach
- Exact worst-case performance of first-order methods for composite convex optimization
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 3892457 (Why is no real title available?)
- Information-based complexity of linear operator equations
- Introductory lectures on convex optimization. A basic course.
- On the convergence analysis of the optimized gradient method
- On the oracle complexity of smooth strongly convex minimization
- On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions
- Optimized first-order methods for smooth convex minimization
- Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions
- Performance of first-order methods for smooth convex minimization: a novel approach
- Potential-function proofs for gradient methods
- Smooth strongly convex interpolation and exact worst-case performance of first-order methods
- The exact information-based complexity of smooth convex minimization
- Universal method for stochastic composite optimization problems
Cited in
(38)- A recovered gradient method applied to smooth optimal shape problems
- On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions
- Nearly optimal first-order methods for convex optimization under gradient norm measure: an adaptive regularization approach
- Fast and safe: accelerated gradient methods with optimality certificates and underestimate sequences
- On the oracle complexity of smooth strongly convex minimization
- Optimal complexity and certification of Bregman first-order methods
- Efficient first-order methods for convex minimization: a constructive approach
- Oracle complexity of second-order methods for smooth convex optimization
- Explicit stabilised gradient descent for faster strongly convex optimisation
- Fast gradient methods for uniformly convex and weakly smooth problems
- On lower and upper bounds in smooth and strongly convex optimization
- New results on subgradient methods for strongly convex optimization problems with a unified analysis
- Smooth Optimization with Approximate Gradient
- Optimal methods of smooth convex minimization
- scientific article; zbMATH DE number 4041186 (Why is no real title available?)
- Generalizing the optimized gradient method for smooth convex minimization
- An optimal first order method based on optimal quadratic averaging
- Relatively smooth convex optimization by first-order methods, and applications
- A first order method for finding minimal norm-like solutions of convex optimization problems
- Universal gradient methods for convex optimization problems
- Gradient methods with memory
- Potential Function-Based Framework for Minimizing Gradients in Convex and Min-Max Optimization
- Optimal Affine-Invariant Smooth Minimization Algorithms
- An acceleration procedure for optimal first-order methods
- Robust accelerated gradient methods for smooth strongly convex functions
- Factor-\(\sqrt{2}\) acceleration of accelerated gradient methods
- Branch-and-bound performance estimation programming: a unified methodology for constructing optimal optimization methods
- An elementary approach to tight worst case complexity analysis of gradient based methods
- Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022
- Provably faster gradient descent via long steps
- Interpolation conditions for linear operators and applications to performance estimation problems
- PEPIT: computer-assisted worst-case analyses of first-order optimization methods in python
- Accelerated minimax algorithms flock together
- Dynamic smoothness parameter for fast gradient methods
- Intermediate gradient methods with relative inexactness
- Nesterov acceleration for ensemble Kalman inversion and variants
- Nesterov's acceleration at the limit: first-order schemes
- Heavy-ball differential equation achieves \(O(\varepsilon^{-7/4})\) convergence for nonconvex functions
This page was built for publication: An optimal gradient method for smooth strongly convex minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038652)
