Distributed Statistical Estimation and Rates of Convergence in Normal Approximation

By Stanislav Minsker, Nate Strawn. 2017

74 citations recorded by the source corpus.

This paper presents a class of new algorithms for distributed statistical estimation that exploit divide-and-conquer approach. We show that one of the key benefits of the divide-and-conquer strategy is robustness, an important characteristic for large distributed systems. We establish connections between performance of these distributed algorithms and the rates of convergence in normal approximation, and prove non-asymptotic deviations guarantees, as well as limit theorems, for the resulting estimators. Our techniques are illustrated through several examples: in particular, we obtain new results for the median-of-means estimator, as well as provide performance guarantees for distributed maximum likelihood estimation.

Subfields: Computer Networks and Communications, Management Science and Operations Research, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

1. Kannan Ramchandran
2. Dong Yin
3. Cong Xie
4. Peter L. Bartlett
5. Yudong Chen
6. Oluwasanmi Koyejo
7. Indranil Gupta
8. Martin Jaggi

In Management Science and Operations Research

1. Kannan Ramchandran
2. Peter L. Bartlett
3. Dong Yin
4. Yudong Chen
5. J. Urgen Schmidhuber
6. Vladimir Koltchinskii
7. Sham M. Kakade
8. Amir-massoud Farahmand

In Statistics and Probability

1. Kannan Ramchandran
2. Dong Yin
3. Peter L. Bartlett
4. Yudong Chen
5. Vladimir Koltchinskii
6. Lili Su
7. Steve Hanneke
8. Martin J. Wainwright

Citations in the corpus

• Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, background): “In a very recent work, Minsker and Strawn (2017) provide a new analysis of median-of-means using a normal approximation.”
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning (2018, methodology): “The coordinate-wise median aggregation subroutine that we consider is related to the median-of-means estimator [52, 31], which has been applied to various robust inference problems [51, 47, 50].”
• Decentralized Federated Learning: Fundamentals, State of the Art, Frameworks, Trends, and Challenges (2022, unknown): “[133].”
• Mean Estimation and Regression Under Heavy-Tailed Distributions: A Survey (2019, unknown): “Minsker and Strawn [68] also prove that, when k = o(√n), then, under the assumptions of Theorem 4, √ n (μ̂n − μ) is asymptotically normal with mean zero and variance σ 2π/2.”