Computing the Variance of Shuffling Stochastic Gradient Algorithms via Power Spectral Density Analysis
When solving finite-sum minimization problems, two common alternatives to
stochastic gradient descent (SGD) with theoretical benefits are random
reshuffling (SGD-RR) and shuffle-once (SGD-SO), in which functions are sampled
in cycles without replacement. Under a convenient stochastic noise
approximation which holds experimentally, we study the stationary variances of
the iterates of SGD, SGD-RR and SGD-SO, whose leading terms decrease in this
order, and obtain simple approximations. To obtain our results, we study the
power spectral density of the stochastic gradient noise sequences. Our analysis
extends beyond SGD to SGD with momentum and to the stochastic Nesterov's
accelerated gradient method. We perform experiments on quadratic objective
functions to test the validity of our approximation and the correctness of our
findings.