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

arXiv: https://arxiv.org/abs/2105.12062 · HTML: https://mlsanity.com/paper/2105.12062/

## Key facts

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

## Builds on (most cited first, 30 of 44)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming](https://mlsanity.com/paper/1310.3787/) (2013)
- [Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop](https://mlsanity.com/paper/1901.08689/) (2019)
- [Stochastic Nested Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1806.07811/) (2018)
- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [Lower Bounds for Finding Stationary Points II: First-Order Methods](https://mlsanity.com/paper/1711.00841/) (2017)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [Tight Complexity Bounds for Optimizing Composite Objectives](https://mlsanity.com/paper/1605.08003/) (2016)
- [Acceleration Methods](https://mlsanity.com/paper/2101.09545/) (2021)
- [Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives](https://mlsanity.com/paper/1506.01972/) (2015)
- [Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods](https://mlsanity.com/paper/1502.05666/) (2015)
- [ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1902.05679/) (2019)
- [The Complexity of Making the Gradient Small in Stochastic Convex Optimization](https://mlsanity.com/paper/1902.04686/) (2019)
- [A unified variance-reduced accelerated gradient method for convex optimization](https://mlsanity.com/paper/1905.12412/) (2019)
- [Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization](https://mlsanity.com/paper/2006.10281/) (2020)
- [Optimized first-order methods for smooth convex minimization](https://mlsanity.com/paper/1406.5468/) (2014)
- [Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functions](https://mlsanity.com/paper/1803.06600/) (2018)
- [Primal-dual accelerated gradient methods with small-dimensional relaxation oracle](https://mlsanity.com/paper/1809.05895/) (2018)
- [Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions](https://mlsanity.com/paper/1902.00947/) (2019)
- [A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates](https://mlsanity.com/paper/1806.11027/) (2018)
- [Much Faster Algorithms for Matrix Scaling](https://mlsanity.com/paper/1704.02315/) (2017)
- [On the Convergence of SARAH and Beyond](https://mlsanity.com/paper/1906.02351/) (2019)
- [Accelerating Variance-Reduced Stochastic Gradient Methods](https://mlsanity.com/paper/1910.09494/) (2019)

## Built on by (most cited first, 4 of 4)

- [Accelerating Value Iteration with Anchoring](https://mlsanity.com/paper/2305.16569/) (2023)
- [Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2310.02987/) (2023)
- [Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviation](https://mlsanity.com/paper/2301.03125/) (2023)
- [Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization](https://mlsanity.com/paper/2109.15292/) (2021)

## 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.