On the Convergence of SARAH and Beyond
arXiv:1906.02351
Abstract
The main theme of this work is a unifying algorithm, \textbf{L}oop\textbf{L}ess \textbf{S}ARAH (L2S) for problems formulated as summation of individual loss functions. L2S broadens a recently developed variance reduction method known as SARAH. To find an -accurate solution, L2S enjoys a complexity of for strongly convex problems. For convex problems, when adopting an -dependent step size, the complexity of L2S is ; while for more frequently adopted -independent step size, the complexity is . Distinct from SARAH, our theoretical findings support an -independent step size in convex problems without extra assumptions. For nonconvex problems, the complexity of L2S is . Our numerical tests on neural networks suggest that L2S can have better generalization properties than SARAH. Along with L2S, our side results include the linear convergence of the last iteration for SARAH in strongly convex problems.
References in corpus (18)
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
- A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
- SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
- Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
- Barzilai-Borwein Step Size for Stochastic Gradient Descent
- Non-convex Finite-Sum Optimization Via SCSG Methods
- Optimization with First-Order Surrogate Functions
- Stochastic Nested Variance Reduction for Nonconvex Optimization
- A Lower Bound for the Optimization of Finite Sums
- Fast Incremental Method for Nonconvex Optimization
- On the Adaptivity of Stochastic Gradient-Based Optimization
- R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate
- Estimate Sequences for Variance-Reduced Stochastic Composite Optimization
- Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
- On the Ineffectiveness of Variance Reduced Optimization for Deep Learning
- L-SVRG and L-Katyusha with Arbitrary Sampling
- Almost Tune-Free Variance Reduction