Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation

Ilya Levin, Maksim Shuklin, Eric Moulines, Paul Mangold, Sergey Samsonov
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:3487-3545, 2026.

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. [2026] 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-levin26a, title = {{Gaussian} Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation}, author = {Levin, Ilya and Shuklin, Maksim and Moulines, Eric and Mangold, Paul and Samsonov, Sergey}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {3487--3545}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/levin26a/levin26a.pdf}, url = {https://proceedings.mlr.press/v337/levin26a.html}, 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. [2026] 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.} }
Endnote
%0 Conference Paper %T Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation %A Ilya Levin %A Maksim Shuklin %A Eric Moulines %A Paul Mangold %A Sergey Samsonov %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-levin26a %I PMLR %P 3487--3545 %U https://proceedings.mlr.press/v337/levin26a.html %V 337 %X 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. [2026] 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.
APA
Levin, I., Shuklin, M., Moulines, E., Mangold, P. & Samsonov, S.. (2026). Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:3487-3545 Available from https://proceedings.mlr.press/v337/levin26a.html.

Related Material