Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent

Marina Sheshukova, Sergey Samsonov, Denis Belomestny, Eric Moulines, Qi-Man Shao, Zhuo-Song Zhang, Alexey Naumov
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:1378-1386, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-sheshukova26a, title = { Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent }, author = {Sheshukova, Marina and Samsonov, Sergey and Belomestny, Denis and Moulines, Eric and Shao, Qi-Man and Zhang, Zhuo-Song and Naumov, Alexey}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {1378--1386}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/sheshukova26a/sheshukova26a.pdf}, url = {https://proceedings.mlr.press/v300/sheshukova26a.html}, abstract = { 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. } }
Endnote
%0 Conference Paper %T Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent %A Marina Sheshukova %A Sergey Samsonov %A Denis Belomestny %A Eric Moulines %A Qi-Man Shao %A Zhuo-Song Zhang %A Alexey Naumov %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-sheshukova26a %I PMLR %P 1378--1386 %U https://proceedings.mlr.press/v300/sheshukova26a.html %V 300 %X 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.
APA
Sheshukova, M., Samsonov, S., Belomestny, D., Moulines, E., Shao, Q., Zhang, Z. & Naumov, A.. (2026). Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:1378-1386 Available from https://proceedings.mlr.press/v300/sheshukova26a.html.

Related Material