# Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities

arXiv: https://arxiv.org/abs/2206.02765 · HTML: https://mlsanity.com/paper/2206.02765/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 85 references that are in the map.
- First posted on arXiv 6 Jun 2022.

## Builds on (most cited first, 17 of 17)

- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality](https://mlsanity.com/paper/1506.07216/) (2015)
- [Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints](https://mlsanity.com/paper/1802.08417/) (2018)
- [Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction](https://mlsanity.com/paper/1812.11476/) (2018)
- [A General Characterization of the Statistical Query Complexity](https://mlsanity.com/paper/1608.02198/) (2016)
- [The Structure of Optimal Private Tests for Simple Hypotheses](https://mlsanity.com/paper/1811.11148/) (2018)
- [Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation](https://mlsanity.com/paper/1311.3494/) (2013)
- [Inference under Information Constraints II: Communication Constraints and Shared Randomness](https://mlsanity.com/paper/1905.08302/) (2019)
- [Streaming Algorithms for High-Dimensional Robust Statistics](https://mlsanity.com/paper/2204.12399/) (2022)
- [Extractor-Based Time-Space Lower Bounds for Learning](https://mlsanity.com/paper/1708.02639/) (2017)
- [Detecting Correlations with Little Memory and Communication](https://mlsanity.com/paper/1803.01420/) (2018)
- [Locally Private Hypothesis Selection](https://mlsanity.com/paper/2002.09465/) (2020)
- [Interactive Inference under Information Constraints](https://mlsanity.com/paper/2007.10976/) (2020)
- [On the Complexity of Random Satisfiability Problems with Planted Solutions](https://mlsanity.com/paper/1311.4821/) (2013)
- [Optimality guarantees for distributed statistical estimation](https://mlsanity.com/paper/1405.0782/) (2014)
- [Communication and Memory Efficient Testing of Discrete Distributions](https://mlsanity.com/paper/1906.04709/) (2019)
- [Robust hypothesis testing and distribution estimation in Hellinger distance](https://mlsanity.com/paper/2011.01848/) (2020)

## Built on by (most cited first, 11 of 11)

- [Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints](https://mlsanity.com/paper/2301.03566/) (2023)
- [The Sample Complexity of Simple Binary Hypothesis Testing](https://mlsanity.com/paper/2403.16981/) (2024)
- [Contraction of Private Quantum Channels and Private Quantum Hypothesis Testing](https://mlsanity.com/paper/2406.18651/) (2024)
- [An invitation to the sample complexity of quantum hypothesis testing](https://mlsanity.com/paper/2403.17868/) (2024)
- [Attainability of Two-Point Testing Rates for Finite-Sample Location Estimation](https://mlsanity.com/paper/2502.05730/) (2025)
- [Statistical Inference with Limited Memory: A Survey](https://mlsanity.com/paper/2312.15225/) (2023)
- [Instance-Optimal Uniformity Testing and Tracking](https://mlsanity.com/paper/2508.02637/) (2025)
- [The Critical Horizon: Inspection Design Principles for Multi-Stage Operations and Deep Reasoning](https://mlsanity.com/paper/2602.09394/) (2026)
- [Density estimation for Hellinger via minimum-distance estimators: mixtures of Gaussians, log-concave, and more](https://mlsanity.com/paper/2606.11469/) (2026)
- [Tight Information Complexity of the Coin Problem in the Broadcast Model](https://mlsanity.com/paper/2608.02776/) (2026)
- [Instance-Optimal Adaptive Location Estimation via Multiscale Mid-Summaries](https://mlsanity.com/paper/2609.20749/) (2026)

## Abstract (arXiv)

We study hypothesis testing under communication constraints, where each sample is quantized before being revealed to a statistician. Without communication constraints, it is well known that the sample complexity of simple binary hypothesis testing is characterized by the Hellinger distance between the distributions. We show that the sample complexity of simple binary hypothesis testing under communication constraints is at most a logarithmic factor larger than in the unconstrained setting and this bound is tight. We develop a polynomial-time algorithm that achieves the aforementioned sample complexity. Our framework extends to robust hypothesis testing, where the distributions are corrupted in the total variation distance. Our proofs rely on a new reverse data processing inequality and a reverse Markov inequality, which may be of independent interest. For simple M-ary hypothesis testing, the sample complexity in the absence of communication constraints has a logarithmic dependence on M. We show that communication constraints can cause an exponential blow-up leading to Omega(M) sample complexity even for adaptive algorithms.