Communication Complexity of Estimating Correlations

We characterize the communication complexity of the following distributed estimation problem. Alice and Bob observe infinitely many iid copies of ρ-correlated unit-variance (Gaussian or ±1 binary) random variables, with unknown ρ∈[-1,1]. By interactively exchanging k bits, Bob wants to produce an estimate hatρ of ρ. We show that the best possible performance (optimized over interaction protocol Pi and estimator hat ρ) satisfies infPi hatρsupρ mathbbE [|ρ-hatρ|2] = tfrac1k (frac12 ln 2 + o(1)). Curiously, the number of samples in our achievability scheme is exponential in k; by contrast, a naive scheme exchanging k samples achieves the same Omega(1/k) rate but with a suboptimal prefactor. Our protocol achieving optimal performance is one-way (non-interactive). We also prove the Omega(1/k) bound even when ρ is restricted to any small open sub-interval of [-1,1] (i.e. a local minimax lower bound). Our proof techniques rely on symmetric strong data-processing inequalities and various tensorization techniques from information-theoretic interactive common-randomness extraction. Our results also imply an Omega(n) lower bound on the information complexity of the Gap-Hamming problem, for which we show a direct information-theoretic proof.