First-order methods for convex optimization
From MaRDI portal
Publication:6169988
Abstract: First-order methods for solving convex optimization problems have been at the forefront of mathematical optimization in the last 20 years. The rapid development of this important class of algorithms is motivated by the success stories reported in various applications, including most importantly machine learning, signal processing, imaging and control theory. First-order methods have the potential to provide low accuracy solutions at low computational complexity which makes them an attractive set of tools in large-scale optimization problems. In this survey we cover a number of key developments in gradient-based optimization methods. This includes non-Euclidean extensions of the classical proximal gradient method, and its accelerated versions. Additionally we survey recent developments within the class of projection-free methods, and proximal versions of primal-dual schemes. We give complete proofs for various key results, and highlight the unifying aspects of several optimization algorithms.
Recommendations
- First-order methods in optimization
- Optimized first-order methods for smooth convex minimization
- Incremental proximal methods for large scale convex optimization
- A simplified view of first order methods for optimization
- Accelerated first-order methods for large-scale convex optimization: nearly optimal complexity under strong convexity
Cites work
- A conditional gradient method with linear rate of convergence for solving convex linear systems
- A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications
- A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A first-order primal-dual algorithm for convex problems with applications to imaging
- A first-order primal-dual algorithm with linesearch
- A Linearly Convergent Variant of the Conditional Gradient Algorithm under Strong Convexity, with Applications to Online and Stochastic Optimization
- A New Class of Alternating Proximal Minimization Algorithms with Costs-to-Move
- A simplified view of first order methods for optimization
- A smooth primal-dual optimization framework for nonsmooth composite convex minimization
- A Stochastic Approximation Method
- A Tight Upper Bound on the Rate of Convergence of Frank-Wolfe Algorithm
- A variational perspective on accelerated methods in optimization
- Accelerated Bregman proximal gradient methods for relatively smooth convex optimization
- Accelerated directional search with non-Euclidean prox-structure
- Accelerated gradient-free optimization methods with a non-Euclidean proximal operator
- Accelerated primal-dual gradient descent with linesearch for convex, nonconvex, and nonsmooth optimization problems
- Accelerated, parallel, and proximal coordinate descent
- Accelerating the cubic regularization of Newton's method on convex problems
- Adaptive subgradient methods for online learning and stochastic optimization
- Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing
- Alternating direction method for covariance selection models
- Alternating proximal algorithms for linearly constrained variational inequalities: application to domain decomposition for PDE's
- An accelerated directional derivative method for smooth stochastic convex optimization
- An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods
- An accelerated method for derivative-free smooth stochastic convex optimization
- An adaptive primal-dual framework for nonsmooth convex minimization
- An extension of the frank and Wolfe method of feasible directions
- An Interior Proximal Algorithm and the Exponential Multiplier Method for Semidefinite Programming
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
- An optimal method for stochastic composite optimization
- Applications of a Splitting Algorithm to Decomposition in Convex Programming and Variational Inequalities
- Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
- Barrier Operators and Associated Gradient-Like Dynamical Systems for Constrained Minimization Problems
- Bregman forward-backward operator splitting
- Bregman Monotone Optimization Algorithms
- Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization
- Complexity bounds for primal-dual methods minimizing the model of objective function
- Compressed sensing
- Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system
- Conditional gradient sliding for convex optimization
- Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
- Convex optimization: algorithms and complexity
- Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Dual approaches to the minimization of strongly convex functionals with a simple structure under affine constraints
- Dual extrapolation and its applications to solving variational inequalities and related problems
- Dual subgradient algorithms for large-scale nonsmooth learning problems
- Duality between subgradient and conditional gradient methods
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Efficiency of the accelerated coordinate descent method on structured optimization problems
- Entropic Proximal Mappings with Applications to Nonlinear Programming
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- Exact augmented Lagrangian duality for mixed integer linear programming
- Excessive Gap Technique in Nonsmooth Convex Minimization
- Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity
- Fast gradient descent for convex minimization problems with an oracle producing a ( , L)-model of function at the requested point
- Fast primal-dual gradient method for strongly convex minimization problems with linear constraints
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- First-order and stochastic optimization methods for machine learning
- First-order methods in optimization
- First-order methods of smooth convex optimization with inexact oracle
- Fixing and extending some recent results on the ADMM algorithm
- FOM -- a MATLAB toolbox of first-order methods for solving convex optimization problems
- Forward-backward splitting with Bregman distances
- From error bounds to the complexity of first-order descent methods for convex functions
- From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
- Generalized equations and their solutions, part II: Applications to nonlinear programming
- Generalized self-concordant analysis of Frank-Wolfe algorithms
- Generalized uniformly optimal methods for nonlinear programming
- Gradient methods for minimizing composite functions
- Gradient methods for problems with inexact model of the objective
- Gradient-based algorithms with applications to signal-recovery problems
- Hessian barrier algorithms for linearly constrained optimization problems
- Hessian Riemannian Gradient Flows in Convex Programming
- scientific article; zbMATH DE number 1667417 (Why is no real title available?)
- scientific article; zbMATH DE number 3148887 (Why is no real title available?)
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 3878095 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 45081 (Why is no real title available?)
- scientific article; zbMATH DE number 48727 (Why is no real title available?)
- scientific article; zbMATH DE number 3526459 (Why is no real title available?)
- scientific article; zbMATH DE number 1324524 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 1489799 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 7246283 (Why is no real title available?)
- scientific article; zbMATH DE number 3293978 (Why is no real title available?)
- scientific article; zbMATH DE number 3320765 (Why is no real title available?)
- scientific article; zbMATH DE number 3341597 (Why is no real title available?)
- Hyperfast second-order local solvers for efficient statistically preconditioned distributed optimization
- Implementable tensor methods in unconstrained convex optimization
- Interior Gradient and Proximal Methods for Convex and Conic Optimization
- Katyusha: the first direct acceleration of stochastic gradient methods
- Lectures on convex optimization
- Lectures on Stochastic Programming
- Linear convergence of a modified Frank–Wolfe algorithm for computing minimum-volume enclosing ellipsoids
- Linear convergence of first order methods for non-strongly convex optimization
- Linearly constrained non-Lipschitz optimization for image restoration
- Linearly convergent away-step conditional gradient for non-strongly convex functions
- Minimum-volume ellipsoids. Theory and algorithms
- Mirror descent and convex optimization problems with non-smooth inequality constraints
- Mirror descent and nonlinear projected subgradient methods for convex optimization.
- Monotone Operators and the Proximal Point Algorithm
- New analysis and results for the Frank-Wolfe method
- Non-convex optimization for machine learning
- On the convergence of gradient-like flows with noisy gradient input
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- Optimal methods of smooth convex minimization
- Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework
- Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization. II: Shrinking procedures and optimal algorithms
- Optimization methods for large-scale machine learning
- Prediction, Learning, and Games
- Primal-dual subgradient methods for convex problems
- Projected subgradient methods with non-Euclidean distances for non-differentiable convex minimization and variational inequalities
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Proximal minimization algorithm with \(D\)-functions
- Proximal splitting methods in signal processing
- Proximité et dualité dans un espace hilbertien
- Random gradient-free minimization of convex functions
- Randomized first order algorithms with applications to \(\ell _{1}\)-minimization
- Rate of Convergence Analysis of Decomposition Methods Based on the Proximal Method of Multipliers for Convex Minimization
- Rates of Convergence for Conditional Gradient Algorithms Near Singular and Nonsingular Extremals
- Recursive aggregation of estimators by the mirror descent algorithm with averaging
- Recursive algorithms, urn processes and chaining number of chain recurrent sets
- Regularized Lotka-Volterra dynamical system as continuous proximal-like method in optimization.
- Relatively smooth convex optimization by first-order methods, and applications
- Restarting algorithms: sometimes there is free lunch
- Restarting the accelerated coordinate descent method with a rough strong convexity estimate
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Signal Recovery by Proximal Forward-Backward Splitting
- Simplicial decomposition in nonlinear programming algorithms
- Singular Riemannian barrier methods and gradient-projection dynamical systems for constrained optimization
- Smooth minimization of non-smooth functions
- Smooth Optimization with Approximate Gradient
- Smoothing and first order methods: a unified framework
- Some comments on Wolfe's ‘away step’
- Some methods of speeding up the convergence of iteration methods
- Statistics for high-dimensional data. Methods, theory and applications.
- Stochastic intermediate gradient method for convex optimization problems
- Stochastic intermediate gradient method for convex problems with stochastic inexact oracle
- Stochastic Methods for Composite and Weakly Convex Optimization Problems
- Stochastic mirror descent dynamics and their convergence in monotone variational inequalities
- Stochastic subgradient method converges on tame functions
- The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
- The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
- The ordered subsets mirror descent optimization method with applications to tomography
- Universal gradient methods for convex optimization problems
- Universal method for stochastic composite optimization problems
- Universal method of searching for equilibria and stochastic equilibria in transportation networks
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Variational Analysis
- Weak convergence of the sequence of successive approximations for nonexpansive mappings
Cited in
(30)- A simplified view of first order methods for optimization
- New computational guarantees for solving convex optimization problems with first order methods, via a function growth condition measure
- Oracle complexity separation in convex optimization
- Proportional-integral projected gradient method for conic optimization
- First-order and stochastic optimization methods for machine learning
- Runge-Kutta-like scaling techniques for first-order methods in convex optimization
- Linear convergence of first order methods for non-strongly convex optimization
- Generalized self-concordant analysis of Frank-Wolfe algorithms
- A first-order multigrid method for bound-constrained convex optimization
- Search direction correction with normalized gradient makes first-order methods faster
- Fast first-order methods for composite convex optimization with backtracking
- First-order methods in optimization
- A New First-Order Algorithmic Framework for Optimization Problems with Orthogonality Constraints
- The approximate duality gap technique: a unified theory of first-order methods
- Linear coupling: an ultimate unification of gradient and mirror descent
- FOM -- a MATLAB toolbox of first-order methods for solving convex optimization problems
- Projection-free accelerated method for convex optimization
- Large-scale convex optimization. Algorithms \& analyses via monotone operators
- First-Order Methods for Nonconvex Quadratic Minimization
- Potential-function proofs for gradient methods
- On first-order algorithms for \(\ell_{1}/\)nuclear norm minimization
- A new randomized primal-dual algorithm for convex optimization with fast last iterate convergence rates
- Accelerated gradient methods with absolute and relative noise in the gradient
- Hyperfast second-order local solvers for efficient statistically preconditioned distributed optimization
- Recent Theoretical Advances in Non-Convex Optimization
- Subsampled first-order optimization methods with applications in imaging
- Several kinds of acceleration techniques for unconstrained optimization first-order algorithms
- Hypodifferentials of nonsmooth convex functions and their applications to nonsmooth convex optimization
- On the convergence rates of iterative regularization algorithms for composite bilevel optimization
- First order solutions in conic programming
This page was built for publication: First-order methods for convex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6169988)
