A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
This addresses the bottleneck of slow convergence in stochastic gradient methods for finite training sets in machine learning, offering a significant speed-up for practitioners.
The paper tackles the problem of optimizing the sum of a finite set of smooth, strongly convex functions by proposing a new stochastic gradient method that achieves a linear convergence rate, whereas standard methods converge sublinearly. Numerical experiments show it dramatically outperforms standard algorithms in optimizing training error and reducing test error quickly.
We propose a new stochastic gradient method for optimizing the sum of a finite set of smooth functions, where the sum is strongly convex. While standard stochastic gradient methods converge at sublinear rates for this problem, the proposed method incorporates a memory of previous gradient values in order to achieve a linear convergence rate. In a machine learning context, numerical experiments indicate that the new algorithm can dramatically outperform standard algorithms, both in terms of optimizing the training error and reducing the test error quickly.