Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation
stat.ML, cs.LG, math.OC
Submitted: 2026-05-19
Updated: 2026-10-29
Comments: The bootstrap validity theorem in the previous version was incorrect: it omitted a heterogeneity term of the same order as the leading fluctuation term. To address this issue, we now use the same bootstrap variables across clients, at the cost of losing the $N^{-1}$ factor in the leading term
Code: https://github.com/levensons/FedLSA_NormApprox
License: http://creativecommons.org/licenses/by/4.0/
The gist: In this paper, we establish Berry-Esseen-type bounds for federated linear stochastic approximation (LSA).
Terminology
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.
Sources
- Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation
- Online Statistical Inference for Contextual Bandits via Stochastic Gradient Descent
- The total variation distance between high-dimensional Gaussians with the same mean
- Local Stochastic Approximation: A Unified View of Federated Learning and Distributed Multi-Task Reinforcement Learning Algorithms
- Central Limit Theorems for Asynchronous Averaged Q-Learning
- Revisiting LocalSGD and SCAFFOLD: Improved Rates and Missing Analysis
- Statistical inference for Linear Stochastic Approximation with Markovian Noise
- Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent
- Local SGD Converges Fast and Communicates Little
- Statistical Inference for Policy Evaluation with Temporal Difference Learning
- Uncertainty quantification for Markov chain induced martingales with application to temporal difference learning
- Online Bootstrap Inference with Nonconvex Stochastic Gradient Descent Estimator
- Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling
Related papers
- Uniform-in-Time Weak Propagation-of-Chaos in Shallow Neural Networks
- Diffusion Models Observe Only Gradients: A Geometric Perspective on Score Matching Errors
- Quantifying Error Propagation and Model Collapse in Diffusion Models
- Behavior of prediction performance metrics with rare events
- Statistical Inference and Learning for Shapley Additive Explanations (SHAP)
- Control Variate Design for Score-Function Gradient Estimators in Importance-Weighted Variational Inference