Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency through Shuffling
This work addresses the problem of high computational cost in training large-scale machine learning models, offering a more efficient approach for practitioners, though it is incremental as it builds on existing variance reduction methods.
The paper tackles the computational inefficiency of variance reduction methods like SVRG and SARAH, which require full gradient computations, by introducing variants that eliminate this need through shuffling and SAG/SAGA techniques, resulting in improved convergence estimates for strongly convex functions and matching performance for non-convex ones.
In today's world, machine learning is hard to imagine without large training datasets and models. This has led to the use of stochastic methods for training, such as stochastic gradient descent (SGD). SGD provides weak theoretical guarantees of convergence, but there are modifications, such as Stochastic Variance Reduced Gradient (SVRG) and StochAstic Recursive grAdient algoritHm (SARAH), that can reduce the variance. These methods require the computation of the full gradient occasionally, which can be time consuming. In this paper, we explore variants of variance reduction algorithms that eliminate the need for full gradient computations. To make our approach memory-efficient and avoid full gradient computations, we use two key techniques: the shuffling heuristic and idea of SAG/SAGA methods. As a result, we improve existing estimates for variance reduction algorithms without the full gradient computations. Additionally, for the non-convex objective function, our estimate matches that of classic shuffling methods, while for the strongly convex one, it is an improvement. We conduct comprehensive theoretical analysis and provide extensive experimental results to validate the efficiency and practicality of our methods for large-scale machine learning problems.