mlsanityData to 7 Oct 2026

First-Order Methods for Convex Optimization

arXiv 2101.00935 ↗First posted 4 Jan 2021math.OC cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 89 of its 240 references that are in the map. First posted on arXiv 4 Jan 2021.

Builds on

89 of 240 references.

References · 89

  1. 2019Advances and Open Problems in Federated Learningcited by 3,021
  2. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  3. 2014Convex Optimization: Algorithms and Complexitycited by 569
  4. 2015A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insightscited by 203
  5. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  6. 2017Non-convex Optimization for Machine Learningcited by 132
  7. 2018Stochastic subgradient method converges on tame functionscited by 120
  8. 2018Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithmcited by 111
  9. 2016A Variational Perspective on Accelerated Methods in Optimizationcited by 108
  10. 2016Relatively-Smooth Convex Optimization by First-Order Methods, and Applicationscited by 108
  11. 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
  12. 2020Variance-Reduced Methods for Machine Learningcited by 79
38 more
  1. 2015On the Global Linear Convergence of Frank-Wolfe Optimization Variantscited by 76
  2. 2019Optimization for deep learning: theory and algorithmscited by 70
  3. 2019Learning deep linear neural networks: Riemannian gradient flows and convergence to global minimizerscited by 61
  4. 2019On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithmscited by 60
  5. 2015A Universal Catalyst for First-Order Optimizationcited by 54
  6. 2018Online Adaptive Methods, Universality and Accelerationcited by 51
  7. 2017Stochastic Methods for Composite and Weakly Convex Optimization Problemscited by 48
  8. 2014Faster Rates for the Frank-Wolfe Method over Strongly-Convex Setscited by 42
  9. 2015From error bounds to the complexity of first-order descent methods for convex functionscited by 42
  10. 2015An optimal randomized incremental gradient methodcited by 32
  11. 2014Accelerated Schemes For A Class of Variational Inequalitiescited by 30
  12. 2014Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimizationcited by 30
  13. 2020Adaptive extra-gradient methods for min-max optimization and gamescited by 30
  14. 2020Recent Theoretical Advances in Non-Convex Optimizationcited by 30
  15. 2020Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithmcited by 29
  16. 2020Statistically Preconditioned Accelerated Gradient Method for Distributed Optimizationcited by 29
  17. 2013The Complexity of Large-scale Convex Programming under a Linear Optimization Oraclecited by 27
  18. 2019Acceleration via Symplectic Discretization of High-Resolution Differential Equationscited by 27
  19. 2019On the Complexity of Approximating Multimarginal Optimal Transportcited by 27
  20. 2019A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noisecited by 26
  21. 2013Accelerated, Parallel and Proximal Coordinate Descentcited by 25
  22. 2018Hessian Riemannian gradient flows in convex programmingcited by 25
  23. 2015Even Faster Accelerated Coordinate Descent Using Non-Uniform Samplingcited by 23
  24. 2019First-order optimization algorithms via inertial systems with Hessian driven dampingcited by 22
  25. 2015Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimizationcited by 21
  26. 2016Optimal Black-Box Reductions Between Optimization Objectivescited by 21
  27. 2018Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenterscited by 21
  28. 2018On Acceleration with Noise-Corrupted Gradientscited by 20
  29. 2018Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimizationcited by 20
  30. 2013Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimizationcited by 19
  31. 2019On a Combination of Alternating Minimization and Nesterov's Momentumcited by 18
  32. 2020Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Accelerationcited by 18
  33. 2013New Analysis and Results for the Frank-Wolfe Methodcited by 17
  34. 2019Optimal Complexity and Certification of Bregman First-Order Methodscited by 16
  35. 2013Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systemscited by 14
  36. 2018Primal-dual accelerated gradient methods with small-dimensional relaxation oraclecited by 14
  37. 2018Linearly Convergent Frank-Wolfe with Backtracking Line-Searchcited by 13
  38. 2015Linearly Convergent Away-Step Conditional Gradient for Non-strongly Convex Functionscited by 12

50 most cited of 89 All 89 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 0; 2024: 1; 2025: 1; 2026: 1.

4 papers.

  1. 2025Analysis of Schedule-Free Nonconvex Optimizationcited by 1
  2. 2026Stochastic variance reduced extragradient methods for solving hierarchical variational inequalitiescited by 1
  3. 2022A conditional gradient homotopy method with applications to Semidefinite Programmingcited by 0
  4. 2024Revisiting Trace Norm Minimization for Tensor Tucker Completion: A Direct Multilinear Rank Learning Approachcited by 0