EUVIMEDEUVIMED entdecken
Crossref

Communication-Constrained Hypothesis Testing: Optimality, Robustness, and Reverse Data Processing Inequalities

Ankit Pensia, Varun Jog, Po-Ling Loh

IEEE Transactions on Information Theory · 2024-01 · 70 (1) · 389-414

DOI: 10.1109/tit.2023.3334024 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2024-01. Verfasst von Ankit Pensia und 2 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 54 Literaturangaben. Gefördert von: NSF, Department of Pure Mathematics and Mathematical Statistics, University of Cambridge.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 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.

Förderung

  • NSF
  • Department of Pure Mathematics and Mathematical Statistics, University of Cambridge

Zitieren

APA

Pensia, A., Jog, V., & Loh, P. (2024). Communication-Constrained Hypothesis Testing: Optimality, Robustness, and Reverse Data Processing Inequalities. IEEE Transactions on Information Theory, 70(1), 389-414. https://doi.org/10.1109/tit.2023.3334024

Vancouver

Pensia A, Jog V, Loh P. Communication-Constrained Hypothesis Testing: Optimality, Robustness, and Reverse Data Processing Inequalities. IEEE Transactions on Information Theory. 2024;70(1):389-414. doi:10.1109/tit.2023.3334024

BibTeX
@article{Pensia2024,
  author = {Pensia, Ankit and Jog, Varun and Loh, Po-Ling},
  title = {Communication-Constrained Hypothesis Testing: Optimality, Robustness, and Reverse Data Processing Inequalities},
  journal = {IEEE Transactions on Information Theory},
  year = {2024},
  volume = {70},
  number = {1},
  pages = {389--414},
  doi = {10.1109/tit.2023.3334024}
}
Kostenlos starten →