Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation
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).
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Sharp Gaussian approximations for Decentralized Federated Learning
Federated Learning has gained traction in privacy-sensitive collaborative environments, with local SGD emerging as a key optimization method in decentralized settings. While its convergence properties are well-studied, a…
Federated LearningvalidLimit Theorems for Factor Models
The paper establishes the central limit theorems and proposes how to perform valid inference in factor models. We consider a setting where many counties/regions/assets are observed for many time periods, and when estimat…
Time SeriesTime Series AnalysisvalidJointly Exchangeable Collective Risk Models: Interaction, Structure, and Limit Theorems
We introduce a framework for systemic risk modeling in insurance portfolios using jointly exchangeable arrays, extending classical collective risk models to account for interactions. We establish central limit theorems t…
A Note on the Prediction-Powered Bootstrap
We introduce PPBoot: a bootstrap-based method for prediction-powered inference. PPBoot is applicable to arbitrary estimation problems and is very simple to implement, essentially only requiring one application of the boo…
PredictionGaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent
In this paper, we establish non-asymptotic convergence rates in the central limit theorem for Polyak-Ruppert-averaged iterates of stochastic gradient descent (SGD). Our analysis builds on the result of the Gaussian appro…