Optimality guarantees for distributed statistical estimation

By John C. Duchi, Michael I. Jordan, Martin J. Wainwright, Yuchen Zhang. 2014

67 citations recorded by the source corpus.

Large data sets often require performing distributed statistical estimation, with a full data set split across multiple machines and limited communication between machines. To study such scenarios, we define and study some refinements of the classical minimax risk that apply to distributed settings, comparing to the performance of estimators with access to the entire data. Lower bounds on these quantities provide a precise characterization of the minimum amount of communication required to achieve the centralized minimax risk. We study two classes of distributed protocols: one in which machines send messages independently over channels without feedback, and a second allowing for interactive communication, in which a central server broadcasts the messages from a given machine to all other machines. We establish lower bounds for a variety of problems, including location estimation in several families and parameter estimation in different types of regression models. Our results include a novel class of quantitative data-processing inequalities used to characterize the effects of limited communication.

Subfields: Artificial Intelligence, Computer Networks and Communications, 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 Artificial Intelligence

In Computer Networks and Communications

In Statistics and Probability

Citations in the corpus

Communication trade-offs for synchronized distributed SGD with large step size (2019, background): “Similar bounds have also been provided for the generally easier statistical estimation setting in Duchi et al. (2014); Braverman et al. (2015); Zhang et al. (2013).”
Distributed Statistical Estimation and Rates of Convergence in Normal Approximation (2017, background): “The following generalization of Berry-Esseen bound (Berry, 1941), (Esseen, 1942) is due to Petrov (1995).”
Limits on Gradient Compression for Stochastic Optimization (2020, background): “The first one is based on Bernoulli product distribution and yields the lower bound using a strong data processing inequality from [9].”
Communication-efficient sparse regression: a one-shot approach (2015, background): “In other words, they establish the minimum communication C needed to obtain `(2)2 risk R , where ‖β̂− β‖(2)2 ≤ R (Duchi et al., 2014; Garg, Ma and Nguyen, 2014).”
Communication-Efficient Distributed Learning of Discrete Probability Distributions (2017, background): “Recent works [40, 21, 24, 5] study the communication cost of mean estimation problems of structured, parametrized distributions.”
Efficient Distributed Learning with Sparsity (2016, unknown): “See for example, (Dekel et al., 2012; Duchi et al., 2012, 2014; Zhang et al., 2013b; Zinkevich et al., 2010; Boyd et al., 2011; Balcan et al., 2012; Yang, 2013; Jaggi et al., 2014; Ma et al., 2015; Shamir and Srebro, 2014; Zhang and Xiao, 2015; Lee et al., 2015a; Arjevani and Shamir, 2015) and…”
Communication-Efficient Distributed Statistical Inference (2016, background): “Color versions of one or more of the ﬁgures in the article can be found online at www.tandfonline.com/r/JASA .”
Communication-efficient Sparse Regression (2017, unknown): “In other words, they establish the minimum communication C needed to obtain `(2)2 risk R , where ‖β̂ − β‖(2)2 ≤ R (Duchi et al., 2014; Garg et al., 2014).”