2022/06/06 by Ankit Pensia, Pensia, Ankit, Varun Jog +3 · 2 citations
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Statistics Theory (math.ST) #Wireless Communication Security Techniques
paper · pdf · doi:10.48550/arxiv.2206.02765
openalex publication_date 2022/06/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Ω(M) sample complexity even for adaptive algorithms.