Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913083918647296 |
|---|---|
| author | Sheshukova, Marina Samsonov, Sergey Belomestny, Denis Moulines, Eric Shao, Qi-Man Zhang, Zhuo-Song Naumov, Alexey |
| author_facet | Sheshukova, Marina Samsonov, Sergey Belomestny, Denis Moulines, Eric Shao, Qi-Man Zhang, Zhuo-Song Naumov, Alexey |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_06719 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent Sheshukova, Marina Samsonov, Sergey Belomestny, Denis Moulines, Eric Shao, Qi-Man Zhang, Zhuo-Song Naumov, Alexey Machine Learning Optimization and Control Probability Statistics Theory 60F05, 62L20, 93E35 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. |
| title | Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent |
| topic | Machine Learning Optimization and Control Probability Statistics Theory 60F05, 62L20, 93E35 |
| url | https://arxiv.org/abs/2502.06719 |