# Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation

arXiv: https://arxiv.org/abs/2605.19629 · HTML: https://mlsanity.com/paper/2605.19629/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 61 references that are in the map.
- First posted on arXiv 19 May 2026.

## Builds on (most cited first, 12 of 12)

- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Statistical Inference for Policy Evaluation with Temporal Difference Learning](https://mlsanity.com/paper/2410.16106/) (2024)
- [Online Bootstrap Inference with Nonconvex Stochastic Gradient Descent Estimator](https://mlsanity.com/paper/2306.02205/) (2023)
- [Statistical inference for Linear Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2505.19102/) (2025)
- [Uncertainty quantification for Markov chain induced martingales with application to temporal difference learning](https://mlsanity.com/paper/2502.13822/) (2025)
- [Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent](https://mlsanity.com/paper/2502.06719/) (2025)
- [Online Statistical Inference for Contextual Bandits via Stochastic Gradient Descent](https://mlsanity.com/paper/2212.14883/) (2022)
- [Local Stochastic Approximation: A Unified View of Federated Learning and Distributed Multi-Task Reinforcement Learning Algorithms](https://mlsanity.com/paper/2006.13460/) (2020)
- [Revisiting LocalSGD and SCAFFOLD: Improved Rates and Missing Analysis](https://mlsanity.com/paper/2501.04443/) (2025)
- [Central Limit Theorems for Asynchronous Averaged Q-Learning](https://mlsanity.com/paper/2509.18964/) (2025)
- [Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation](https://mlsanity.com/paper/2510.12375/) (2025)
- [Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling](https://mlsanity.com/paper/2504.11645/) (2025)

## Abstract (arXiv)

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.