Computing the Variance of Shuffling Stochastic Gradient Algorithms via Power Spectral Density Analysis
From MaRDI portal
Publication:6400841
arXiv2206.00632MaRDI QIDQ6400841FDOQ6400841
Carles Domingo-Enrich
Publication date: 1 June 2022
Abstract: 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.
Has companion code repository: https://github.com/cdenrich/sgd_shuffling
This page was built for publication: Computing the Variance of Shuffling Stochastic Gradient Algorithms via Power Spectral Density Analysis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6400841)
