Optimized first-order methods for smooth convex minimization
From MaRDI portal
Abstract: We introduce new optimized first-order methods for smooth unconstrained convex minimization. Drori and Teboulle recently described a numerical method for computing the -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 , 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.
Recommendations
- Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions
- On the convergence analysis of the optimized gradient method
- Optimizing first-order methods for smooth convex minimization of gradient Q-linearly convergence
- Generalizing the optimized gradient method for smooth convex minimization
- Efficient first-order methods for convex minimization: a constructive approach
Cites work
- A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- Adaptive restart for accelerated gradient schemes
- Approximation accuracy, gradient methods, and error bound for structured convex optimization
- Gradient methods for minimizing composite functions
- Graph implementations for nonsmooth convex programs
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- Linear coupling: an ultimate unification of gradient and mirror descent
- Optimized first-order methods for smooth convex minimization
- Performance of first-order methods for smooth convex minimization: a novel approach
- Smooth minimization of non-smooth functions
- Smooth strongly convex interpolation and exact worst-case performance of first-order methods
- Some methods of speeding up the convergence of iteration methods
Cited in
(only showing first 100 items - show all)- New computational guarantees for solving convex optimization problems with first order methods, via a function growth condition measure
- Optimal deterministic algorithm generation
- Adaptive restart of the optimized gradient method for convex optimization
- Exact worst-case convergence rates of the proximal gradient method for composite convex minimization
- Inertial forward-backward algorithms with perturbations: application to Tikhonov regularization
- Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operators
- Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions
- Nearly optimal first-order methods for convex optimization under gradient norm measure: an adaptive regularization approach
- Bounds for the tracking error of first-order online optimization methods
- Decentralized and parallel primal and dual accelerated methods for stochastic convex programming problems
- Analysis of optimization algorithms via sum-of-squares
- Generalized Nesterov's accelerated proximal gradient algorithms with convergence rate of order o(1/k^2)
- From differential equation solvers to accelerated first-order methods for convex optimization
- Optimal complexity and certification of Bregman first-order methods
- A frequency-domain analysis of inexact gradient methods
- Convergence rate of inertial proximal algorithms with general extrapolation and proximal coefficients
- Efficient first-order methods for convex minimization: a constructive approach
- Properties of the sign gradient descent algorithms
- Accelerated proximal point method for maximally monotone operators
- Performance of first-order methods for smooth convex minimization: a novel approach
- Convergence rate of inertial forward-backward algorithm beyond Nesterov's rule
- New analysis of linear convergence of gradient-type methods via unifying error bound conditions
- Convergence of a relaxed inertial forward-backward algorithm for structured monotone inclusions
- Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity
- Fast proximal algorithms for nonsmooth convex optimization
- Accelerated additive Schwarz methods for convex optimization with adaptive restart
- An engineering interpretation of Nesterov's convex minimization algorithm and time integration: application to optimal fiber orientation
- Fast gradient methods for uniformly convex and weakly smooth problems
- A first-order multigrid method for bound-constrained convex optimization
- The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1/k^2
- On lower and upper bounds in smooth and strongly convex optimization
- On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization
- First-order and second-order optimality conditions for nonsmooth constrained problems via convolution smoothing
- Improved algorithms for convex minimization in relative scale
- Optimized first-order methods for smooth convex minimization
- Tight sublinear convergence rate of the proximal point algorithm for maximal monotone inclusion problems
- Search direction correction with normalized gradient makes first-order methods faster
- Smooth Optimization with Approximate Gradient
- An optimal variant of Kelley's cutting-plane method
- Fast first-order methods for composite convex optimization with backtracking
- Generalizing the optimized gradient method for smooth convex minimization
- Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)
- An optimal first order method based on optimal quadratic averaging
- Relatively smooth convex optimization by first-order methods, and applications
- Convergence rates of inertial forward-backward algorithms
- Effects of dominance on operation policies in a two-stage supply chain in which market demands follow the Bass diffusion model
- Analysis of optimization algorithms via integral quadratic constraints: nonstrongly convex problems
- On the complexity analysis of the primal solutions for the accelerated randomized dual coordinate ascent
- Accelerated extra-gradient descent: a novel accelerated first-order method
- scientific article; zbMATH DE number 7363383 (Why is no real title available?)
- A Lyapunov analysis of accelerated methods in optimization
- Variational phase recovering without phase unwrapping in phase-shifting interferometry
- Smooth strongly convex interpolation and exact worst-case performance of first-order methods
- From the ravine method to the Nesterov method and vice versa: a dynamical system perspective
- Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3
- Convergence rate of a relaxed inertial proximal algorithm for convex minimization
- The exact information-based complexity of smooth convex minimization
- First-Order Methods for Nonconvex Quadratic Minimization
- Worst-case convergence analysis of inexact gradient and Newton methods through semidefinite programming performance estimation
- On the convergence analysis of the optimized gradient method
- Operator splitting performance estimation: tight contraction factors and optimal parameter selection
- Fast first-order methods for minimizing convex composite functions
- Optimizing the efficiency of first-order methods for the distance to an optimal solution of smooth convex functions
- Optimizing first-order methods for smooth convex minimization of gradient Q-linearly convergence
- Data-driven nonsmooth optimization
- Solving inverse problems using data-driven models
- Exact worst-case performance of first-order methods for composite convex optimization
- Optimal Affine-Invariant Smooth Minimization Algorithms
- An acceleration procedure for optimal first-order methods
- Robust inference for skewed data in health sciences
- An optimal gradient method for smooth strongly convex minimization
- Convergence of iterates for first-order optimization algorithms with inertia and Hessian driven damping
- Factor-\(\sqrt{2}\) acceleration of accelerated gradient methods
- Branch-and-bound performance estimation programming: a unified methodology for constructing optimal optimization methods
- Principled analyses and design of first-order methods with inexact proximal operators
- First-order methods for convex optimization
- Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022
- From Halpern's fixed-point iterations to Nesterov's accelerated interpretations for root-finding problems
- On optimal universal first-order methods for minimizing heterogeneous sums
- Provably faster gradient descent via long steps
- Tight ergodic sublinear convergence rate of the relaxed proximal point algorithm for monotone variational inequalities
- Interpolation conditions for linear operators and applications to performance estimation problems
- The exact worst-case convergence rate of the alternating direction method of multipliers
- PEPIT: computer-assisted worst-case analyses of first-order optimization methods in python
- A distributed accelerated algorithm based on a unified momentum method
- Accelerated minimax algorithms flock together
- Several kinds of acceleration techniques for unconstrained optimization first-order algorithms
- Accelerated forward-backward algorithms with subgradient corrections
- An optimal lower bound for smooth convex functions
- Convex-concave interpolation and application of PEP to the bilinear-coupled saddle point problem
- Hypodifferentials of nonsmooth convex functions and their applications to nonsmooth convex optimization
- Nesterov's acceleration at the limit: first-order schemes
- Restarts subject to approximate sharpness: a parameter-free and optimal scheme for first-order methods
- Heavy-ball differential equation achieves \(O(\varepsilon^{-7/4})\) convergence for nonconvex functions
- Accelerated gradient descent by concatenation of stepsize schedules
- Fast proximal algorithms based on Chebychev centers for nonsmooth optimization
- Error estimates between SGD with momentum and underdamped Langevin diffusion
- On the o(1/k^2) convergence rate analysis for general inertial gradient type method
- Computer-assisted design of accelerated composite optimization methods: OptISTA
- Comparative analysis of accelerated gradient algorithms for convex optimization: high and super resolution ODE approach
This page was built for publication: Optimized first-order methods for smooth convex minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q312663)
