The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints
Hadi Kazemi, Ankit Pensia, Varun Jog · 2025
Read The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints by Hadi Kazemi, Ankit Pensia, Varun Jog (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-13686.txt.
Introduction
Hadi Kazemi, Ankit Pensia, and Varun Jog settle two open questions about testing hypotheses with limited communication, in this 2025 paper. Many sensors may each hold data about one of two possible states of the world. Limits on bits or privacy cap how much each can share, raising the samples needed.
The first question asked whether back-and-forth interaction lowers that sample cost. It does not, the authors prove. The second asked for sharper cost bounds in the communication-limited case, and they derive bounds that cannot be improved. Their tools include a one-shot error bound with a handy splitting property. A reversed data-processing inequality for a family of divergences also appears.
Catalog record
| CREATOR | Hadi Kazemi, Ankit Pensia, Varun Jog |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-13686
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints Hadi Kazemi, Ankit Pensia, Varun Jog Abstract This paper resolves two open problems from a recent paper [ PJL24 ] concerning the sample complexity of distributed simple binary hypothesis testing under information constraints. The first open problem asks whether interaction reduces the sample complexity of distributed simple binary hypothesis testing. In this paper, we show that sequential interaction does not help. The second problem suggests tightening existing sample complexity bounds for communication-constrained simple binary hypothesis testing. We derive optimally tight bounds for this setting and resolve this problem. Our main technical contributions are: (i) a one-shot lower bound on the Bayes error in simple binary hypothesis testing that satisfies a crucial tensorisation property; (ii) a streamlined proof of the formula for the sample complexity of simple binary hypothesis testing without constraints, first established in [ PJL24 ] ; and (iii) a reverse data-processing inequality for Hellinger- λ \lambda divergences, generalising the results from [ BNOP21 ] and [ PJL23 ] . 1 1 1 A 1-page extended abstract of this paper, titled “The Sample Complexity of Simple Binary Hypothesis Testing: Tight Bounds with Sequential Interactivity and Information Constraints,” appears in the Proceedings of the Conference on Learning Theory, 2025. Keywords Sample complexity, hypothesis testing, data-processing inequality 1 Introduction Hypothesis testing is one of the central problems in statistics that concerns testing different hypotheses based on observed data. The most basic version of this problem is simple binary hypothesis testing, where we wish to decide between two hypotheses H_{0} and H_{1} . Under hypothesis H_{0} (resp. H_{1} ) we observe i.i.d. samples from distribution Q (resp. P ), where P and Q are known. The Bayes formulation of simple binary hypothesis testing, which is the focus of this paper, assumes that the true hypothesis is chosen randomly according to a prior Bernoulli distribution \mathrm{Ber}(\pi) . This is a classical problem that has been studied for over a century, and we highlight some important results. • Optimal algorithm: The maximum a posteriori-rule (MAP-rule) minimises the error probability. In the prior-free setting, threshold tests are optimal [ NP33 ] . • Asymptotic error probability: The error probability decays exponentially, with the exponents characterised by information-theoretic measures such as the Kullback–Leibler divergence or Chernoff information [ PW25 , Chapter 16] . • Sample complexity: The sample-size needed to achieve an error of \delta was notably unaddressed until recently, when [ PJL24 ] derived a formula for all \delta\leq\min(\pi,1-\pi)/4 . In addition to identifying the sample complexity, [ PJL24 ] also noted the implications of their result to the setting of distributed simple binary hypothesis testing under information constraints, such as communication (or quantisation) or local differential privacy. These had been studied in prior work [ PJL23 , PAJL24 ] but only for the restricted setting of constant \pi and \delta (specifically, \pi=0.5 and \delta=0.1 ). This paper addresses two open problems noted in [ PJL24 ] : tightening the existing sample complexity bounds for information-constrained hypothesis testing, and examining whether interaction helps reduce the sample complexity. In what follows, we describe the problem setting for distributed information-constrained hypothesis testing in more detail. Hypothesis testing under information constraints: Suppose each of n agents, denoted by s_{1},\dots,s_{n} , receives a single sample denoted by X_{i} for agent s_{i} . Agent s_{i} transmits Y_{i} to a central server, and the central server performs a hypothesis test using Y_{1},\dots,Y_{n} . The transformation of X_{i} to Y_{i} is subject to information constraints that are captured by a set of channels \mathcal{T} (Markov kernels) from \mathcal{X} , the support of the X_{i} s, to \mathcal{Y} , the support of the Y_{i} s. i.e., the agent s_{i} must pick a communication channel T^{i}\in\mathcal{T} . For example, \mathcal{T} could be the set of channels with output size D , denoted by \mathcal{T}_{D} , or the set of all \epsilon -differentially private channels, denoted by \mathcal{T}_{\epsilon\text{-LDP}} . We assume agents have access to private randomness as well as public randomness. The assumption of private randomness is equivalent to assuming the convexity of \mathcal{T} , since each agent can choose any convex mixture of the channels available to use. It turns out that public randomness is of no use in this problem. To see this, suppose all agents observe a public random variable U which they may use to coordinate their choices of channels. The resulting algorithm (either in the identical, non-identical, or sequential settings described below) may be thought of as a mixture of private-randomness-only algorithms depending on the realisations of U . It is easy to see that if the Bayes error is at most \delta after averaging over U , then there must be a particular realisation of U that makes the error at most \delta . This shows that there exists a private-randomness-only algorithm that is as good as any public-and-private randomness algorithm. Hence, in what follows, we disregard the public and private random variables and focus on deterministic algorithms with a convex set \mathcal{T} . The different settings of interest based on how the agents select their channels are described in 1 . Definition 1 (Information-Constrained Simple Binary Hypothesis Testing) . Let P and Q be a pair of distributions on a discrete set \mathcal{X} . Let \pi\in(0,0.5] and \Theta\sim\mathrm{Ber}(\pi) . When \Theta=0 (resp. \Theta=1 ) we have X_{i}\overset{i.i.d.}{\sim}Q (respectively X_{i}\overset{i.i.d.}{\sim}P ). Let \delta\in(0,1) and \mathcal{T} a convex set of channels with input space \mathcal{X} and output space \mathcal{Y} . Consider the channel and estimator pair (T,\hat{\theta}) where \mathbf{T}=(T^{1},T^{2},\dots,T^{n}) is a sequence of n channels where all channels have the same output space \mathcal{Y} , and \hat{\theta}:\mathcal{Y}^{n}\rightarrow\{0,1\} is the tester. 1. (Unconstrained) We denote the problem of simple binary hypothesis testing without constraints between two distributions P and Q , with prior \pi and error probability \delta as \mathcal{B}_{B}(P,Q,\pi,\delta) . The sample complexity of simple binary hypothesis testing, denoted by n^{*}(P,Q,\pi,\delta) , is the smallest number of samples n for which there exists a test \hat{\theta} satisfying \pi\cdot\mathbb{P}_{X\sim P^{\otimes n}}[\hat{\theta}(X)\neq 1]+\bar{\pi}\cdot\mathbb{P}_{X\sim Q^{\otimes n}}[\hat{\theta}(X)\neq 0]\leq\delta, (1) where we use the shorthand X=(X_{1},\dots,X_{n}) . 2. (Identical) \mathbf{T}=(T,T,\dots,T) where T\in\mathcal{T} . We say that the pair (T,\hat{\theta}) solves the information constraint hypothesis testing problem in identical channel setting with n samples with prior \pi and error probability \delta if \pi\cdot\mathbb{P}_{X\sim P^{\otimes n}}[\hat{\theta}(Y)\neq 1]+\bar{\pi}\cdot\mathbb{P}_{X\sim Q^{\otimes n}}[\hat{\theta}(Y)\neq 0]\leq\delta\,. (2) In the above, we denote (X_{1},X_{2},\dots,X_{n}) by X and (Y_{1},Y_{2},\dots,Y_{n}) by Y . Also, we assume that we have Y_{i}=T(X_{i}) . The sample complexity n^{*}_{\mathrm{id}}(P,Q,\pi,\delta,\mathcal{T}) of information-constrained hypothesis testing with identical channels is the smallest n for which there exists a pair of channel and tester (T,\hat{\theta}) that solves the problem with n samples. 3. (Non-identical and non-interactive) \mathbf{T}=(T^{1},T^{2},\dots,T^{n}) where T^{i}\in\mathcal{T} . We say that the pair (\mathbf{T},\hat{\theta}) solves the information-constrained hypothesis testing with non-identical (and non-interactive) channels if they satisfy Eq. 2 where Y_{i}=T^{i}(X_{i}) . The sample complexity is denoted by n^{*}_{\mathrm{non\text{-}id}}(P,Q,\pi,\delta,\mathcal{T}) . 4. (Sequentially interactive) \mathbf{T}=(T^{1},T^{2},\dots,T^{n}) and each T^{i} is a channel from \mathcal{X}\times\mathcal{Y}^{i-1} to \mathcal{Y} , such that for any fixed (y_{1},y_{2},\dots,y_{i-1}) , the stochastic map (X_{i},y_{1},y_{2},\dots,y_{i-1})\mapsto Y_{i} is in \mathcal{T} . We say that the pair (\mathbf{T},\hat{\theta}) solves this problem if they satisfy Eq. 2 where Y_{i}=T^{i}(X_{i},Y_{1},Y_{2},\dots,Y_{i-1}) . We