An acceleration procedure for optimal first-order methods
From MaRDI portal
Abstract: We introduce in this paper an optimal first-order method that allows an easy and cheap evaluation of the local Lipschitz constant of the objective's gradient. This constant must ideally be chosen at every iteration as small as possible, while serving in an indispensable upper bound for the value of the objective function. In the previously existing variants of optimal first-order methods, this upper bound inequality was constructed from points computed during the current iteration. It was thus not possible to select the optimal value for this Lipschitz constant at the beginning of the iteration. In our variant, the upper bound inequality is constructed from points available before the current iteration, offering us the possibility to set the Lipschitz constant to its optimal value at once. This procedure, even if efficient in practice, presents a higher worse-case complexity than standard optimal first-order methods. We propose an alternative strategy that retains the practical efficiency of this procedure, while having an optimal worse-case complexity. We show how our generic scheme can be adapted for smoothing techniques, and perform numerical experiments on large scale eigenvalue minimization problems. As compared with standard optimal first-order methods, our schemes allows us to divide computation times by two to three orders of magnitude for the largest problems we considered.
Recommendations
- Optimized first-order methods for smooth convex minimization
- An optimal first order method based on optimal quadratic averaging
- Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions
- Optimizing first-order methods for smooth convex minimization of gradient Q-linearly convergence
- An optimal gradient method for smooth strongly convex minimization
Cites work
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A Spectral Bundle Method for Semidefinite Programming
- Convex optimization methods for dimension reduction and coefficient estimation in multivariate linear regression
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Gradient methods for minimizing composite functions
- Primal-dual subgradient methods for convex problems
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Robust Stochastic Approximation Approach to Stochastic Programming
- Smooth minimization of non-smooth functions
- Smooth Optimization with Approximate Gradient
- Smoothing technique and its applications in semidefinite optimization
- Subgradient methods for huge-scale optimization problems
- Templates for convex cone problems with applications to sparse signal recovery
Cited in
(3)
This page was built for publication: An acceleration procedure for optimal first-order methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5746718)
