mlsanityData to 7 Oct 2026

Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums

arXiv 2105.12062 ↗First posted 25 May 2021math.OC cs.LG stat.MLcited by 4

Not on the map. Why?

Abstract (arXiv)

In convex optimization, the problem of finding near-stationary points has not been adequately studied yet, unlike other optimality measures such as the function value. Even in the deterministic case, the optimal method (OGM-G, due to Kim and Fessler (2021)) has just been discovered recently. In this work, we conduct a systematic study of algorithmic techniques for finding near-stationary points of convex finite-sums. Our main contributions are several algorithmic discoveries: (1) we discover a memory-saving variant of OGM-G based on the performance estimation problem approach (Drori and Teboulle, 2014); (2) we design a new accelerated SVRG variant that can simultaneously achieve fast rates for minimizing both the gradient norm and function value; (3) we propose an adaptively regularized accelerated SVRG variant, which does not require the knowledge of some unknown initial constants and achieves near-optimal complexities. We put an emphasis on the simplicity and practicality of the new schemes, which could facilitate future work.

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

Builds on

44 of 71 references.

References · 44

  1. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  2. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  3. 2017How to Escape Saddle Points Efficientlycited by 284
  4. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  5. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  6. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  7. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  8. 2014A Proximal Stochastic Gradient Method with Progressive Variance Reductioncited by 78
  9. 2013Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programmingcited by 74
  10. 2019Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loopcited by 68
  11. 2018Stochastic Nested Variance Reduction for Nonconvex Optimizationcited by 63
  12. 2014Linear Coupling: An Ultimate Unification of Gradient and Mirror Descentcited by 58
32 more
  1. 2017Lower Bounds for Finding Stationary Points II: First-Order Methodscited by 55
  2. 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 55
  3. 2021Acceleration Methodscited by 48
  4. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 47
  5. 2015Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectivescited by 38
  6. 2019ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimizationcited by 37
  7. 2015Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methodscited by 36
  8. 2019The Complexity of Making the Gradient Small in Stochastic Convex Optimizationcited by 33
  9. 2019A unified variance-reduced accelerated gradient method for convex optimizationcited by 23
  10. 2014Optimized first-order methods for smooth convex minimizationcited by 18
  11. 2020Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimizationcited by 18
  12. 2018Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functionscited by 14
  13. 2018Primal-dual accelerated gradient methods with small-dimensional relaxation oraclecited by 14
  14. 2019Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functionscited by 12
  15. 2018A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Ratescited by 11
  16. 2017Much Faster Algorithms for Matrix Scalingcited by 10
  17. 2019On the Convergence of SARAH and Beyondcited by 10
  18. 2019Accelerating Variance-Reduced Stochastic Gradient Methodscited by 10
  19. 2017Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methodscited by 9
  20. 2018Direct Acceleration of SAGA using Sampled Negative Momentumcited by 9
  21. 2021Complementary Composite Minimization, Small Gradients in General Norms, and Applicationscited by 9
  22. 2021ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Methodcited by 9
  23. 2021On the oracle complexity of smooth strongly convex minimizationcited by 7
  24. 2021An optimal gradient method for smooth strongly convex minimizationcited by 7
  25. 2018On the Curved Geometry of Accelerated Optimizationcited by 6
  26. 2016Generalizing the optimized gradient method for smooth convex minimizationcited by 5
  27. 2016The exact information-based complexity of smooth convex minimizationcited by 4
  28. 2018Complexity of finding near-stationary points of convex functions stochasticallycited by 4
  29. 2019Nearly optimal first-order methods for convex optimization under gradient norm measure: An adaptive regularization approachcited by 4
  30. 2020Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Ratescited by 4
  31. 2021Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimizationcited by 4
  32. 2016Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)cited by 2

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 0; 2023: 3.

4 papers.

  1. 2023Accelerating Value Iteration with Anchoringcited by 10
  2. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 10
  3. 2023Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviationcited by 4
  4. 2021Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimizationcited by 0