Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop

Abstract

The stochastic variance-reduced gradient method (SVRG) and its accelerated variant (Katyusha) have attracted enormous attention in the machine learning community in the last few years due to their superior theoretical properties and empirical behaviour on training supervised machine learning models via the empirical risk minimization paradigm. A key structural element in both of these methods is the inclusion of an outer loop at the beginning of which a full pass over the training data is made in order to compute the exact gradient, which is then used to construct a variance-reduced estimator of the gradient. In this work we design {\em loopless variants} of both of these methods. In particular, we remove the outer loop and replace its function by a coin flip performed in each iteration designed to trigger, with a small probability, the computation of the gradient. We prove that the new methods enjoy the same superior theoretical convergence properties as the original methods. However, we demonstrate through numerical experiments that our methods have substantially superior practical behavior.

arXiv comment14 pages, 2 algorithms, 9 lemmas, 2 theorems, 4 figures

References in corpus (9)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates
• SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
• SDCA without Duality, Regularization, and Individual Convexity
• Stochastic Dual Coordinate Ascent with Adaptive Probabilities
• Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
• Improving SAGA via a Probabilistic Interpolation with Gradient Descent

Cited by in corpus (5)

• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization
• A Generic Acceleration Framework for Stochastic Composite Optimization
• Local SGD: Unified Theory and New Efficient Methods
• Almost Tune-Free Variance Reduction
• Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learning