Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent
This provides a fully non-asymptotic bound for bootstrap approximations in SGD, addressing uncertainty quantification for practitioners in machine learning and statistics, though it is incremental as it builds on existing Gaussian approximation theory.
The paper tackles the problem of constructing confidence sets for Stochastic Gradient Descent (SGD) by establishing the non-asymptotic validity of a multiplier bootstrap procedure, achieving approximation rates of up to $1/\sqrt{n}$ in convex distance, which can be faster than rates from the Polyak-Juditsky central limit theorem.
In this paper, we establish the non-asymptotic validity of the multiplier bootstrap procedure for constructing the confidence sets using the Stochastic Gradient Descent (SGD) algorithm. Under appropriate regularity conditions, our approach avoids the need to approximate the limiting covariance of Polyak-Ruppert SGD iterates, which allows us to derive approximation rates in convex distance of order up to $1/\sqrt{n}$. Notably, this rate can be faster than the one that can be proven in the Polyak-Juditsky central limit theorem. To our knowledge, this provides the first fully non-asymptotic bound on the accuracy of bootstrap approximations in SGD algorithms. Our analysis builds on the Gaussian approximation results for nonlinear statistics of independent random variables.