VR-SGD: A Simple Stochastic Variance Reduction Method for Machine Learning
arXiv:1802.09932
Abstract
In this paper, we propose a simple variant of the original SVRG, called variance reduced stochastic gradient descent (VR-SGD). Unlike the choices of snapshot and starting points in SVRG and its proximal variant, Prox-SVRG, the two vectors of VR-SGD are set to the average and last iterate of the previous epoch, respectively. The settings allow us to use much larger learning rates, and also make our convergence analysis more challenging. We also design two different update rules for smooth and non-smooth objective functions, respectively, which means that VR-SGD can tackle non-smooth and/or non-strongly convex problems directly without any reduction techniques. Moreover, we analyze the convergence properties of VR-SGD for strongly convex problems, which show that VR-SGD attains linear convergence. Different from its counterparts that have no convergence guarantees for non-strongly convex problems, we also provide the convergence guarantees of VR-SGD for this case, and empirically verify that VR-SGD with varying learning rates achieves similar performance to its momentum accelerated variant that has the optimal convergence rate . Finally, we apply VR-SGD to solve various machine learning problems, such as convex and non-convex empirical risk minimization, and leading eigenvalue computation. Experimental results show that VR-SGD converges significantly faster than SVRG and Prox-SVRG, and usually outperforms state-of-the-art accelerated methods, e.g., Katyusha.
arXiv comment46 pages, 25 figures. IEEE Transactions on Knowledge and Data Engineering, accepted in October, 2018. arXiv admin note: substantial text overlap with arXiv:1704.04966
References in corpus (14)
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
- A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
- Adding Gradient Noise Improves Learning for Very Deep Networks
- Variance Reduction for Faster Non-Convex Optimization
- On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
- Variance-Reduced and Projection-Free Stochastic Optimization
- Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
- Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction
- Accelerated Variance Reduced Stochastic ADMM
- Stochastic Methods for Composite and Weakly Convex Optimization Problems
- Stochastic Zeroth-order Optimization via Variance Reduction method
- Variance Reduced methods for Non-convex Composition Optimization
- Stochastically Controlled Stochastic Gradient for the Convex and Non-convex Composition problem