Communication lower bounds for statistical estimation problems via a distributed data processing inequality

DOI10.1145/2897518.2897582zbMath1373.68235arXiv1506.07216OpenAlexW2963422939MaRDI QIDQ5361898

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

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.07216

zbMATH Keywords

information complexitycommunication complexitystatistical estimation

Mathematics Subject Classification ID

Estimation in multivariate analysis (62H12) Point estimation (62F10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (20)

Discussion on the paper ‘A review of distributed statistical inference’ ⋮ A selective review of statistical methods using calibration information from similar studies ⋮ Distributed nonparametric function estimation: optimal rate of convergence and cost of adaptation ⋮ WONDER: Weighted one-shot distributed ridge regression in high dimensions ⋮ Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems ⋮ Distributed Sparse Composite Quantile Regression in Ultrahigh Dimensions ⋮ Optimal high-dimensional and nonparametric distributed testing under communication constraints ⋮ Distributed Decoding From Heterogeneous 1-Bit Compressive Measurements ⋮ Statistical-computational trade-offs in tensor PCA and related problems via communication complexity ⋮ Communication and information complexity ⋮ Distributed function estimation: adaptation using minimal communication ⋮ Quantum divergences with \(p\)-power means ⋮ Unnamed Item ⋮ Distributed linear regression by averaging ⋮ Two Party Distribution Testing: Communication and Security ⋮ Communication-Efficient Distributed Statistical Inference ⋮ Unnamed Item ⋮ Distributed adaptive Gaussian mean estimation with unknown variance: interactive protocol helps adaptation ⋮ Unnamed Item ⋮ Topics and Techniques in Distribution Testing: A Biased but Representative Sample

This page was built for publication: Communication lower bounds for statistical estimation problems via a distributed data processing inequality