Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation
Abstract
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 step size regime and (ii) decreasing step size with an increasing number of local iterations, recovering the recent rates of Bonnerjee et al. [2025] as a special case. As a primary application of our results, we develop an online multiplier bootstrap procedure for inference on the last iterate, which avoids explicit estimation of the asymptotic covariance matrix, and obtain non-asymptotic validity guarantees for this procedure.
Related
- Analysis and Approximation of Stochastic Multiscale Subdiffusion Driven by Fractional Gaussian Noise
- Moment-Accurate Gaussian Mixtures for Constant-Step Stochastic Approximation
- Gaussian Approximation in Wasserstein-p: Markovian Martingale Differences and Stochastic Approximation
- Two Gaussians, Too Many: A bootstrap-based approach to assess identifiability in non-Gaussian structural vector autoregressions
- Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost
BibTeX
@misc{levin2026gaussian,
title = {{Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation}},
author = {Ilya Levin and Maksim Shuklin and Eric Moulines and Paul Mangold and Sergey Samsonov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.19629},
eprint = {2605.19629},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.19629},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation
AU - Ilya Levin
AU - Maksim Shuklin
AU - Eric Moulines
AU - Paul Mangold
AU - Sergey Samsonov
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2605.19629
UR - https://arxiv.org/abs/2605.19629
AB - 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 step size regime and (ii) decreasing step size with an increasing number of local iterations, recovering the recent rates of Bonnerjee et al. [2025] as a special case. As a primary application of our results, we develop an online multiplier bootstrap procedure for inference on the last iterate, which avoids explicit estimation of the asymptotic covariance matrix, and obtain non-asymptotic validity guarantees for this procedure.
ER -