Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums
arXiv:2105.12062
Abstract
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.
arXiv comment29 pages, 4 figures
References in corpus (12)
- SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
- Optimized first-order methods for smooth convex minimization
- Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)
- A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates
- Generalizing the optimized gradient method for smooth convex minimization
- How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD
- A unified variance-reduced accelerated gradient method for convex optimization
- Direct Acceleration of SAGA using Sampled Negative Momentum
- Complexity of finding near-stationary points of convex functions stochastically
- Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization
- ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method
- Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization