Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality

Mark Braverman; Ankit Garg; Tengyu Ma; Huy L. Nguyen; David P. Woodruff

Source-linked AI summary

Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality

Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff

arXiv:1506.07216v3Jun 24, 2015cs.LGcs.CCcs.ITstat.ML

TL;DR

The paper studies communication–accuracy tradeoffs in distributed high-dimensional statistical estimation, focusing on sparse Gaussian mean estimation and its implications for sparse linear regression. It proves distributed data processing inequalities, derives communication lower bounds, and gives a one-round communication-optimal protocol for dense mean estimation.

Problem
Distributed statistical estimation faces communication bottlenecks, raising the question of how communication constrains accuracy in high dimensions.
Method
The paper proves a distributed data processing inequality and applies it to sparse Gaussian mean estimation, with a simultaneous protocol for dense mean estimation.
Results
The sparse Gaussian mean problem requires ambient-dimension-scale communication for minimax error, implies an Ω(min{n, d}) per-machine lower bound for sparse linear regression, and admits a one-round communication-optimal dense protocol.
Takeaways & Limitations
Communication cannot generally be reduced to sparsity while preserving minimax accuracy, whereas dense Gaussian mean estimation can achieve optimal communication in one simultaneous round.
Takeaways & Limitations
The inequality’s tightness alone does not yield a distributed detection protocol with O(β^-1) communication, and the construction has only small minimum information cost rather than small information cost.

Abstract

from arXiv · show

We study the tradeoff between the statistical error and communication cost of distributed statistical estimation problems in high dimensions. In the distributed sparse Gaussian mean estimation problem, each of the $m$ machines receives $n$ data points from a $d$-dimensional Gaussian distribution with unknown mean $θ$ which is promised to be $k$-sparse. The machines communicate by message passing and aim to estimate the mean $θ$. We provide a tight (up to logarithmic factors) tradeoff between the estimation error and the number of bits communicated between the machines. This directly leads to a lower bound for the distributed \textit{sparse linear regression} problem: to achieve the statistical minimax error, the total communication is at least $Ω(\min\{n,d\}m)$, where $n$ is the number of observations that each machine receives and $d$ is the ambient dimension. These lower results improve upon [Sha14,SD'14] by allowing multi-round iterative communication model. We also give the first optimal simultaneous protocol in the dense case for mean estimation. As our main technique, we prove a \textit{distributed data processing inequality}, as a generalization of usual data processing inequalities, which might be of independent interest and useful for other problems.

1 Introduction

The paper studies communication–statistical-error tradeoffs in high-dimensional distributed estimation and develops lower bounds that remain valid under interactive communication. Its central tool is a distributed data processing inequality, complemented by a one-round protocol for dense mean estimation.

Motivation: Communication can become the main bottleneck when statistical learning is distributed across machines and high-dimensional data must be exchanged.The paper frames communication as a resource alongside statistical accuracy.
Sparse estimation lower bounds: Sparse structure does not generally reduce communication: achieving statistical minimax error for sparse Gaussian mean estimation requires communication scaling with ambient dimension.If communication scales only with sparsity, the statistical error instead scales with ambient dimension.
Sparse estimation lower bounds: For sparse linear regression with Gaussian design, achieving statistical minimax error requires communication cost per machine of Ω(min{n, d}).This lower bound does not depend on sparsity and applies in a stronger model allowing multi-round iterative communication.
Dense estimation protocol: In the dense case, a simultaneous protocol reduces the number of communication rounds from O(log m) to 1 while retaining communication optimality.The construction combines bits from Gaussian samples with one-bit roundings of fractional parts.
Distributed data processing inequality: When a transcript permits reliable detection, the inequality yields an Ω(β^-1) lower bound on information and expected communication.For unbiased priors, squared Hellinger distance is within a constant factor of mutual information, and source coding converts information into communication cost.
Distributed data processing inequality: The paper proves a distributed data processing inequality that transfers a single-machine SDPI constant to the multi-machine setting under a bounded-likelihood-ratio condition.The inequality relates transcript Hellinger distance to the minimum conditional mutual information from the machines’ inputs.
Distributed data processing inequality: The distributed inequality is tight up to a constant factor for some protocol, but tightness alone does not guarantee a protocol that solves distributed detection with O(β^-1) communication.A solving protocol must also make transcript Hellinger distance Ω(1).

2 Problem Setup, Notations and Preliminaries

This section formalizes distributed estimation and detection problems, their communication and information costs, and the Gaussian mean and sparse linear regression instances. It also introduces the public-blackboard transcript model and protocol factorization used in later lower bounds.

Distributed estimation: Each of m machines receives n i.i.d. samples from an unknown distribution in a parameterized family and contributes to estimating θ.The estimator is produced from the communicated transcript, and accuracy is measured by mean-squared loss.
Communication model: Machines communicate through a publicly visible blackboard, so the model captures both point-to-point and broadcast communication.All written messages form a bit transcript Π, whose length defines communication cost.
Costs and accuracy: Communication is measured by the expected transcript length, while information cost is measured by mutual information between the transcript and the data.The formal protocol definition constrains information cost, communication cost, and mean-squared loss simultaneously.
Concrete problems: The Gaussian mean estimation problem uses distributions N(θ, σ^2I_d), with the sparse variant restricting θ to vectors satisfying |θ|_0 ≤ k.The same setup includes Gaussian mean detection as a two-distribution special case and sparse linear regression with Gaussian design and noise.
Protocol structure: For a fixed transcript, the protocol distribution factors across machines, and product-distribution inputs preserve a corresponding factorization through marginalization.This factorization yields the cut-paste property later used in the lower-bound proofs.

3 Distributed Strong Data Processing Inequalities

This section proves a distributed strong data processing inequality by combining single-machine SDPI bounds with tensorization across machines. The resulting inequality relates transcript Hellinger distance to conditional information cost.

Main inequality: The main theorem bounds transcript Hellinger distance between the two parameter cases by conditional mutual information scaled by the SDPI constant.Under µ1 ≤ c·µ0, the bound is h^2(Π|V=0, Π|V=1) ≤ K(c + 1)β·I(X; Π | V = 0), where K is absolute.
Proof strategy: The proof tensorizes the target inequality across machines and proves each resulting component using the single-machine SDPI.The right-hand information term decomposes into per-machine contributions because the inputs are conditionally independent.
Single-machine reduction: A thought experiment replaces one machine’s input distribution according to a uniform Bernoulli variable, turning the protocol transcript into a single-machine channel.This constructs the Markov chain needed to apply the single-machine inequality to each machine.
Distance comparison: Data processing and Hellinger lower bounds connect information terms to distances between transcript distributions under neighboring inputs.The proof compares Π0 and Πei and uses the protocol’s conditional distributions to transfer the bound across cases.

4 Applications to Parameter Estimation Problems

The paper applies its distributed data processing framework to Gaussian mean estimation and sparse linear regression, establishing communication–error tradeoffs and a one-round dense protocol. The results include ambient-dimension lower bounds despite sparsity and tight tradeoffs up to logarithmic factors.

Distributed Gaussian mean detection: O(δ^2/σ^2) bounds the SDPI constant for Gaussian distributions, supporting communication lower bounds for distributed Gaussian mean detection.The proof uses truncated Gaussian distributions because arbitrary Gaussian densities need not be within a constant factor pointwise.
Distributed Gaussian mean detection: δ ≤ σ/√n yields Gaussian mean detection lower bounds on communication and minimum information cost, even though one machine can distinguish the distributions locally.The proof truncates the sample support while retaining probability at least 0.95, then transfers the bound to the true Gaussian setting.
Sparse Gaussian mean estimation: C scales inverse linearly with target error R between the statistical minimax error and the infinite-communication benchmark, with tightness up to logarithmic factors.The lower bound uses the Gaussian mean result and a direct-sum reduction for sparse parameters.
Dense Gaussian mean estimation: One communication round achieves dense Gaussian mean estimation with cost C = αdm and mean-squared loss R = O(...), improving on the previous Ω(log m)-round optimal protocol.The protocol combines a few truncated Gaussian values with randomized bit roundings of many samples.
Signal-strength extension: For strong nonzero-coordinate signals, the paper gives tight rate–communication lower bounds, with different terms dominating according to η^2 relative to 16R/k.When η^2 ≥ 16R/k, the first term dominates; otherwise, the second term is inherited from the sparse Gaussian mean lower bound.
Sparse linear regression: Ω(m·min{n,d}) bits are required for sparse linear regression to achieve statistical minimax error, independently of sparsity k.In the regime d/n → c, this matches the cited upper bound up to a logarithmic factor.

5 Direct-sum Theorem for Sparse Parameters

The direct-sum reduction embeds a randomly selected sparse coordinate into otherwise simulated data, converting a sparse estimation protocol into a distributed detection protocol. This shows that the protocol’s information cost is diluted across ambient coordinates while detection remains accurate.

Reduction: The reduction publicly samples k coordinates and embeds the unknown bit in the first coordinate while privately simulating the remaining coordinates.The machines run the original protocol on the constructed k-sparse input.
Detection: With probability at least 3/4, the derived protocol correctly distinguishes the hidden bit.The decision rule thresholds the estimated first coordinate at δ/2.
Reduction: The constructed data have the same distribution as valid k-sparse Gaussian-mean inputs, so the original protocol retains its loss and information guarantees.The reduction therefore applies the protocol to a legitimate sparse instance.
Information bound: The proof separately establishes small information cost under the zero-bit case, completing the reduction’s detection and information analyses.This is formalized in Proposition 5.2.
Information bound: The reduction bounds the derived protocol’s information cost by distributing the original cost across the d−k+1 coordinates outside the fixed support.Conditioning on the other selected coordinates makes the first coordinate uniform among the remaining ambient coordinates.

6 Data Processing Inequality for Truncated Gaussian

The paper derives its distributed data-processing inequality from single-machine strong data processing, transportation inequalities, and concentration properties of truncated log-concave distributions. These ingredients yield the inequality needed for Gaussian estimation lower bounds.

Distributed SDPI: The distributed inequality generalizes strong data processing from one machine to multiple machines without worsening the SDPI constant beyond a constant factor.The approach uses a prior-free multi-machine formulation with the same single-machine parameter β.
Distributed SDPI: A reverse channel from observations to the hidden Bernoulli variable connects transcript distinguishability to a bound on the strong data-processing coefficient.The proof controls the relevant divergence through transportation inequalities.
Transportation inequalities: For log-concave measures, Wasserstein distance is controlled by KL divergence through a transportation inequality.The paper establishes this for measures supported on a finite interval under curvature assumptions.
Concentration: Concentration for Lipschitz functions is obtained from log-Sobolev and entropy inequalities, then transferred to finite-support distributions by approximation.The approximation uses smooth extensions whose measures converge in total variation.
Application to truncated Gaussians: For truncated Gaussian mixtures, the posterior probabilities are Lipschitz, allowing the preceding concentration and transportation results to prove the target SDPI.The proof combines the mixture’s log-concavity with the Lipschitz bound on fv.

A Proofs of Results in Section 4

The appendix proves the sparse linear-regression lower bound by reducing sparse Gaussian mean estimation to regression with Gaussian design matrices. Applying the mean-estimation lower bound then yields the communication requirement.

Reduction: The proof constructs regression inputs from each machine’s Gaussian-mean samples and an independent Gaussian noise term.The resulting observations are compatible with the sparse linear regression model.
Reduction: The machines run the sparse regression protocol on the constructed data, thereby obtaining a protocol for sparse Gaussian mean estimation with the same communication and loss.This is the reduction used before invoking Theorem 4.5.
Lower-bound transfer: Theorem 4.5 transfers its Gaussian-mean lower bound to sparse linear regression through this construction.The appendix states that the resulting protocol inherits the lower-bound consequence.

B Tight Upper Bound with One-way Communication

The paper gives simultaneous one-way protocols for dense Gaussian mean estimation, achieving optimal communication in the bounded-mean setting and extending to general bounded coordinates with a small overhead.

Bounded-mean protocol: The bounded-mean protocol uses exactly one bit per machine in one dimension and applies independently across d coordinates.Using only the first αm machines yields the stated communication tradeoff.
Bounded-mean protocol: The protocol’s m-bit communication achieves the mean-squared loss stated in Theorem B.1.The theorem supplies the correctness guarantee for Protocol 2.
Protocol mechanism: Each machine’s one-bit message is based on randomized rounding of Gaussian samples and a transformation involving the inverse Gauss error function.The inverse error function is used to recover the normalized mean from aggregated bits.
General bounded coordinates: For general bounded coordinates, the one-dimensional protocol uses O(m + log^2(mdn/σ)) bits and runs independently across coordinates.The total communication is O(md + d log^2(mdn/σ)) bits.
General bounded coordinates: The extended protocol uses initial machines to transmit precision bits, while later machines send randomized fractional-part information simultaneously.The construction combines coarse estimation with rounded fractional samples.

3. Returns

The paper develops a simultaneous distributed protocol for estimating a normal mean, combining coarse median information with bit messages encoding fractional Gaussian samples. Its coordinator reconstructs the estimate with overall communication O(m + log^2(mdn/σ)).

Protocol: O(log(mdn/σ)) bits from each of the first r machines let the coordinator compute a median γ of averaged Gaussian inputs.Here r = O(log(mdn/σ)), and the averaged inputs X_i are distributed as N(θ̄, 1).
Correctness: 1 − 1/(mdn/σ)^α is the probability that γ is within an additive 1/100 of θ̄.The exponent α can be any sufficiently large constant depending on r.
Protocol: m − r machines send one-bit messages based on fractional parts of their Gaussian inputs and shifted inputs.Each machine forms R_i and R′_i, then sends bits B_i and B′_i; the coordinator uses one of the two bit collections according to γ.
Communication: O(m + log^2(mdn/σ)) is the protocol’s overall communication.The coordinator’s output description states this bound after accounting for the communicated bits and auxiliary information.
Estimator: The coordinator estimates θ̄ by combining an integer estimate Z with a function of the aggregated bit information.If no candidate passes the check, it outputs γ; otherwise it outputs Z + g(B), or the analogous shifted estimate using B′.
Additional application: Ω(k) information is required for distributed gap majority, and strong data processing inequalities provide an alternative proof of this linear lower bound.For a k-party protocol solving gap majority, the transcript has conditional mutual information at least Ω(k).

D.1 Proof of Lemma 5

The proof of Lemma 5 analyzes the curvature of a log-density formed from two component distributions through direct differentiation and algebraic inequalities.

Derivative calculation: u′′(x) is obtained by differentiating the log-density defined from exp(−u_0(x)) and exp(−u_1(x)).The proof introduces h = exp(−u_0(x)) + exp(−u_1(x)) to simplify the calculation.
Derivative calculation: The resulting expression combines u′_0, u′_1, u′′_0, and u′′_1 weighted by exponentials of the component potentials.The cross term depends on the squared difference between the first derivatives.
Curvature bound: A lower bound on h′′ is transformed into an algebraic condition using AM-GM and the assumed derivative separation bound.The argument considers t no larger than the minimum of the component curvature terms.

D.2 Proof of Lemma 8

The proof of Lemma 8 shows that conditioning on the sum of observations removes the dependence of their joint density on the binary parameter.

Conditional density: Conditioned on X_1 + ··· + X_n = l and V = v, the joint density is proportional to a product of Gaussian factors centered at vδ.The conditioning fixes the sum l, which is used in simplifying the exponent.
Conclusion: The conditional density is independent of v, proving the lemma.The proof explicitly notes that the identity follows after using the constraint Σ_i x_i = l.

D.3 Proof of Lemma 7

These lemmas assemble information-theoretic and analytic tools used in the paper’s lower-bound arguments, including distribution comparisons, Hellinger relations, and cut-paste reductions.

Distance comparisons: Lemma 9 relates Hellinger distance and total variation for any two distributions.The passage introduces this as a folklore comparison used later in the proofs.
Information bounds: Lemma 10 bounds mutual information for a random choice between two distributions when the associated random variables are conditionally independent of the choice.Its proof uses KL divergence bounded by χ² distance and a quadratic inequality.
Cut-paste tools: Theorem E.1 applies to distribution families satisfying a cut-paste property and relates Hellinger distances involving all-zero, all-one, and unit vectors.The proof extends the stated stronger result from powers of two by partitioning coordinates into small subsets.
Distribution comparison: Lemma 11 transfers mutual-information bounds between distributions when one distribution dominates another by a factor c.The resulting inequality compares I(X; Π(X)) with c times the corresponding information under the dominated distribution.