Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation
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_ | 1866915553813200896 |
|---|---|
| author | Butyrin, Bogdan Moulines, Eric Naumov, Alexey Samsonov, Sergey Shao, Qi-Man Zhang, Zhuo-Song |
| author_facet | Butyrin, Bogdan Moulines, Eric Naumov, Alexey Samsonov, Sergey Shao, Qi-Man Zhang, Zhuo-Song |
| contents | In this paper, we refine the Berry-Esseen bounds for the multivariate normal approximation of Polyak-Ruppert averaged iterates arising from the linear stochastic approximation (LSA) algorithm with decreasing step size. We consider the normal approximation by the Gaussian distribution with covariance matrix predicted by the Polyak-Juditsky central limit theorem and establish the rate up to order $n^{-1/3}$ in convex distance, where $n$ is the number of samples used in the algorithm. We also prove a non-asymptotic validity of the multiplier bootstrap procedure for approximating the distribution of the rescaled error of the averaged LSA estimator. We establish approximation rates of order up to $1/\sqrt{n}$ for the latter distribution, which significantly improves upon the previous results obtained by Samsonov et al. (2024). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_12375 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation Butyrin, Bogdan Moulines, Eric Naumov, Alexey Samsonov, Sergey Shao, Qi-Man Zhang, Zhuo-Song Machine Learning Optimization and Control Probability Statistics Theory 60F05, 62L20, 62E20 In this paper, we refine the Berry-Esseen bounds for the multivariate normal approximation of Polyak-Ruppert averaged iterates arising from the linear stochastic approximation (LSA) algorithm with decreasing step size. We consider the normal approximation by the Gaussian distribution with covariance matrix predicted by the Polyak-Juditsky central limit theorem and establish the rate up to order $n^{-1/3}$ in convex distance, where $n$ is the number of samples used in the algorithm. We also prove a non-asymptotic validity of the multiplier bootstrap procedure for approximating the distribution of the rescaled error of the averaged LSA estimator. We establish approximation rates of order up to $1/\sqrt{n}$ for the latter distribution, which significantly improves upon the previous results obtained by Samsonov et al. (2024). |
| title | Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation |
| topic | Machine Learning Optimization and Control Probability Statistics Theory 60F05, 62L20, 62E20 |
| url | https://arxiv.org/abs/2510.12375 |