Statistical Estimation and Online Inference via Local SGD

Xiang Li, Jiadong Liang, Xiangyu Chang, Zhihua Zhang
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:1613-1661, 2022.

Abstract

We analyze the novel Local SGD in federated Learning, a multi-round estimation procedure that uses intermittent communication to improve communication efficiency. Under a $2{+}\delta$ moment condition on stochastic gradients, we first establish a {\it functional central limit theorem} that shows the averaged iterates of Local SGD converge weakly to a rescaled Brownian motion. We next provide two iterative inference methods: the {\it plug-in} and the {\it random scaling}. Random scaling constructs an asymptotically pivotal statistic for inference by using the information along the whole Local SGD path. Both the methods are communication efficient and applicable to online data. Our results show that Local SGD simultaneously achieves both statistical efficiency and communication efficiency.

Cite this Paper


BibTeX
@InProceedings{pmlr-v178-li22b, title = {Statistical Estimation and Online Inference via Local SGD}, author = {Li, Xiang and Liang, Jiadong and Chang, Xiangyu and Zhang, Zhihua}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {1613--1661}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/li22b/li22b.pdf}, url = {https://proceedings.mlr.press/v178/li22b.html}, abstract = {We analyze the novel Local SGD in federated Learning, a multi-round estimation procedure that uses intermittent communication to improve communication efficiency. Under a $2{+}\delta$ moment condition on stochastic gradients, we first establish a {\it functional central limit theorem} that shows the averaged iterates of Local SGD converge weakly to a rescaled Brownian motion. We next provide two iterative inference methods: the {\it plug-in} and the {\it random scaling}. Random scaling constructs an asymptotically pivotal statistic for inference by using the information along the whole Local SGD path. Both the methods are communication efficient and applicable to online data. Our results show that Local SGD simultaneously achieves both statistical efficiency and communication efficiency.} }
Endnote
%0 Conference Paper %T Statistical Estimation and Online Inference via Local SGD %A Xiang Li %A Jiadong Liang %A Xiangyu Chang %A Zhihua Zhang %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-li22b %I PMLR %P 1613--1661 %U https://proceedings.mlr.press/v178/li22b.html %V 178 %X We analyze the novel Local SGD in federated Learning, a multi-round estimation procedure that uses intermittent communication to improve communication efficiency. Under a $2{+}\delta$ moment condition on stochastic gradients, we first establish a {\it functional central limit theorem} that shows the averaged iterates of Local SGD converge weakly to a rescaled Brownian motion. We next provide two iterative inference methods: the {\it plug-in} and the {\it random scaling}. Random scaling constructs an asymptotically pivotal statistic for inference by using the information along the whole Local SGD path. Both the methods are communication efficient and applicable to online data. Our results show that Local SGD simultaneously achieves both statistical efficiency and communication efficiency.
APA
Li, X., Liang, J., Chang, X. & Zhang, Z.. (2022). Statistical Estimation and Online Inference via Local SGD. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:1613-1661 Available from https://proceedings.mlr.press/v178/li22b.html.

Related Material