Talks.cam

Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities - Dr Varun Jog, University of Cambridge
2022-10-19 13:00 - 14:00 UTC | MR5, CMS Pavilion A
In this talk, we discuss hypothesis testing under communication constraints, where each sample is quantized before being revealed to a statistician. 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 proofs rely on a new reverse data processing inequality and a reverse Markov inequality, which may be of independent interest.
