Minimizing Finite Sums with the Stochastic Average Gradient
This addresses optimization efficiency for machine learning and data analysis tasks involving large datasets, representing a significant advancement over existing methods.
The paper tackles the problem of optimizing finite sums of smooth convex functions by proposing the Stochastic Average Gradient (SAG) method, which achieves faster convergence rates than stochastic gradient methods, improving from O(1/k^{1/2}) to O(1/k) in general and to linear O(p^k) for strongly-convex sums.
We propose the stochastic average gradient (SAG) method for optimizing the sum of a finite number of smooth convex functions. Like stochastic gradient (SG) methods, the SAG method's iteration cost is independent of the number of terms in the sum. However, by incorporating a memory of previous gradient values the SAG method achieves a faster convergence rate than black-box SG methods. The convergence rate is improved from O(1/k^{1/2}) to O(1/k) in general, and when the sum is strongly-convex the convergence rate is improved from the sub-linear O(1/k) to a linear convergence rate of the form O(p^k) for p \textless{} 1. Further, in many cases the convergence rate of the new method is also faster than black-box deterministic gradient methods, in terms of the number of gradient evaluations. Numerical experiments indicate that the new algorithm often dramatically outperforms existing SG and deterministic gradient methods, and that the performance may be further improved through the use of non-uniform sampling strategies.