Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints

Abstract

We consider parameter estimation in distributed networks, where each sensor in the network observes an independent sample from an underlying distribution and has $k$ bits to communicate its sample to a centralized processor which computes an estimate of a desired parameter. We develop lower bounds for the minimax risk of estimating the underlying parameter for a large class of losses and distributions. Our results show that under mild regularity conditions, the communication constraint reduces the effective sample size by a factor of $d$ when $k$ is small, where $d$ is the dimension of the estimated parameter. Furthermore, this penalty reduces at most exponentially with increasing $k$, which is the case for some models, e.g., estimating high-dimensional distributions. For other models however, we show that the sample size reduction is re-mediated only linearly with increasing $k$, e.g. when some sub-Gaussian structure is available. We apply our results to the distributed setting with product Bernoulli model, multinomial model, Gaussian location models, and logistic regression which recover or strengthen existing results. Our approach significantly deviates from existing approaches for developing information-theoretic lower bounds for communication-efficient estimation. We circumvent the need for strong data processing inequalities used in prior work and develop a geometric approach which builds on a new representation of the communication constraint. This approach allows us to strengthen and generalize existing results with simpler and more transparent proofs.

This version (v4) added a new corollary on logistic regression, as well as more discussions on sparse Gaussian mean estimation, compared to v3

Cited by in corpus (14)

• Lower Bounds for Locally Private Estimation via Communication Complexity
• Distributed Simulation and Distributed Inference
• Mean Estimation from One-Bit Measurements
• Robust Testing and Estimation under Manipulation Attacks
• Optimal Communication Rates and Combinatorial Properties for Common Randomness Generation
• A Few Interactions Improve Distributed Nonparametric Estimation, Optimally
• Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation
• Optimal distributed composite testing in high-dimensional Gaussian models with 1-bit communication
• Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit
• Minimax Bounds for Distributed Logistic Regression
• Communication and Memory Efficient Testing of Discrete Distributions
• Sequential Estimation under Multiple Resources: a Bandit Point of View
• Pointwise Bounds for Distribution Estimation under Communication Constraints
• Estimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints