Optimality guarantees for distributed statistical estimation

Abstract

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.

34 pages, 1 figure. Preliminary version appearing in Neural Information Processing Systems 2013 (http://papers.nips.cc/paper/4902-information-theoretic-lower-bounds-for-distributed-statistical-estimation-with-communication-constraints)

References in corpus (3)

• Optimal Distributed Online Prediction using Mini-Batches
• Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates
• Distance-based and continuum Fano inequalities with applications to statistical estimation

Cited by in corpus (15)

• A review of distributed statistical inference
• Communication-efficient sparse regression: a one-shot approach
• Efficient Distributed Learning with Sparsity
• Communication-Efficient Distributed Statistical Inference
• Communication trade-offs for synchronized distributed SGD with large step size
• Distributed linear regression by averaging
• Gaussian Approximation of Quantization Error for Estimation from Compressed Data
• Mean Estimation from One-Bit Measurements
• WONDER: Weighted one-shot distributed ridge regression in high dimensions
• Learning of Tree-Structured Gaussian Graphical Models on Distributed Data under Communication Constraints
• On Fundamental Limits of Robust Learning
• Efficient Estimation for Generalized Linear Models on a Distributed System with Nonrandomly Distributed Data
• Graph Balancing for Distributed Subgradient Methods over Directed Graphs
• Universal Consistency and Robustness of Localized Support Vector Machines
• A selective review on calibration information from similar studies based on parametric likelihood or empirical likelihood