Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent

?

Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent

P. 1378–1386.

Sheshukova M., Samsonov S., Belomestny D., Moulines E., Shao Q., Zhang Z., Naumov A.

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 PolyakRuppert SGD iterates, which allows us to derive approximation rates in convex distance of order up to 1/ √ 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 nonasymptotic 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.

Language: English

Full text

Text on another site

Publication based on the results of:

Development of theoretical foundations and methods of generative artificial intelligence and their application to heterogeneous domain area (2025)

In book

Volume 300: International Conference on Artificial Intelligence and Statistics, 2-5 May 2026, Hilton Tangier Al Houara Hotel, Morocco

Vol. 300. , PMLR, 2026.

On the rate of Gaussian approximation for online linear regression problems

Sheshukova M., Durmus A., Khusainov M. et al., Statistics 2026 P. 1–25

In this paper, we consider the problem of Gaussian approximation for the online linear regression task. We derive the corresponding rates for the setting of a constant stepsize and study the explicit dependence of the convergence rate on the problem dimension d and quantities related to the design matrix. When the number of iterations n is known in advance, ...

Added: September 4, 2026

Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation

Levin I., Shuklin M., Moulines E. et al., , in: Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence (UAI), PMLR Volume 337: Conference on Uncertainty in Artificial Intelligence, 17-21 August 2026, KIT, Amsterdam, the NetherlandsVol. 337.: MLResearchPress, 2026. Ch. 134 P. 3487–3545.

In this paper, we establish Berry-Esseen-type bounds for federated linear stochastic approximation (LSA). Our results provide the first federated {Gaussian} approximations for LSA that explicitly capture communication-computation trade-offs and heterogeneity-aware error terms, quantifying the effects of local step size, number of local updates, and heterogeneity on convergence rates. We present results for both (i) constant ...

Added: September 4, 2026

Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning

Samsonov S., Moulines E., Shao Q. et al., , in: 38th Conference on Neural Information Processing Systems (NeurIPS 2024).: [б.и.], 2024. P. 12408–12460.

In this paper, we obtain the Berry–Esseen bound for multivariate normal approximation for the Polyak-Ruppert averaged iterates of the linear stochastic approximation (LSA) algorithm with decreasing step size. Our findings reveal that the fastest rate of normal approximation is achieved when setting the most aggressive step size αk ≍ k −1/2 . Moreover, we prove ...

Added: February 7, 2025