The Price of Not Knowing the Alternative in Bit-Limited Hypothesis Testing

Picture many sensors, each seeing one noisy sample and allowed to send only a few bits to a central decision-maker. When the sensor knows exactly what the "signal present" distribution looks like, the best thing it can do is simple. It computes how much more likely its sample is under "signal" than under "no signal" (the likelihood ratio), then reports which of a few intervals that number falls in. Recent theory shows this costs almost nothing: the number of sensors needed grows by at most a logarithmic factor over the unconstrained case. In practice, though, the alternative is rarely known exactly. The signal may be positive or negative, it may point in an unknown direction, or its noise level may be unknown. Each possible alternative then calls for a different ranking of the same observations, so no single fixed set of intervals serves all of them. This note proposes to measure exactly how much that ambiguity costs. The tool is an inequality that guarantees a fixed fraction of the statistical distinguishability survives compression simultaneously for every alternative. The proposal also tests whether one round of feedback from the center removes that cost.

The opportunity is that two existing lines of work almost meet but do not touch. One line proves that deterministic likelihood-ratio thresholds are near-optimal for simple tests, where both hypotheses are fully known. The other line uses strong data processing inequalities, which state that a noisy or compressing channel shrinks information by a factor strictly below one, to prove lower bounds for bit-limited estimation. Composite testing, where the alternative is a whole family of distributions, is explicitly left open by the first line. It also sits exactly where the second line's lower-bound tools should be decisive.

Core Claim

Our claim is that for composite binary testing under a $D$-message constraint, the communication penalty is governed by one quantity: how well a single $D$-cell partition of the observation space can serve all alternatives at once. Define

$$\kappa_D(P,\Theta_1) = \max_{W} \; \min_{\theta \in \Theta_1} \frac{H^2(PW,\, Q_\theta W)}{H^2(P,\, Q_\theta)},$$

where $P$ is the null distribution, $Q_\theta$ for $\theta \in \Theta_1$ are the alternatives, $W$ ranges over deterministic maps from observations to $D$ messages, $PW$ denotes the distribution of the message, and $H^2$ is squared Hellinger distance. We use Hellinger because the sample complexity of a simple test scales as $1/H^2$ and Hellinger tensorizes cleanly over independent samples. For a simple test, prior reverse data processing results imply $\kappa_D \gtrsim \min(1, D/\log n^*)$. For composite families whose alternatives rank observations in conflicting orders, $\kappa_D$ can be much smaller.

We conjecture three things, and aim to prove them. First, non-interactive protocols need roughly $\max_\theta n^*_\theta / \kappa_D$ samples, where $n^*_\theta$ is the unconstrained sample complexity against alternative $\theta$, and a matching lower bound follows from a contraction argument applied to the worst alternative. Second, a two-stage protocol that first coarsely identifies which alternative is active and then switches to that alternative's likelihood-ratio thresholds needs only $n_{\text{loc}} + \max_\theta n^*_\theta \max(1, \log n^*_\theta / D)$ samples. Third, the localization cost $n_{\text{loc}}$ is lower-bounded by a strong data processing argument on an $M$-ary identification problem, where $M$ is the number of classes of conflicting likelihood-ratio orderings. The upshot is a clean dichotomy: compositeness turns the additive cost of adaptivity into a multiplicative cost for non-adaptive schemes, but only when $M$ is small enough that localization is cheap.

This contrasts sharply with the simple case. There, The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints proves that sequential interaction helps by at most a factor of 4.

Relation to Prior Work

Two papers supply the method we generalize. Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities proves a reverse data processing inequality for simple tests: some likelihood-ratio binning preserves a quantifiable fraction of divergence. It also gives a polynomial-time algorithm for those bins. The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints proves the $n^* \max(1, \log n^*/D)$ rate and the factor-4 limit on interaction, and names composite testing as open. Both papers fix a single likelihood ratio. Our $\kappa_D$ replaces "preserve divergence to $Q$" with "preserve divergence to every $Q_\theta$ with one partition." That is a max–min problem their arguments do not address.

The same communication-constrained paper also constrains us. Its result that $M$-ary testing requires $\Omega(M)$ samples is what makes the localization stage potentially expensive. We read it as a prediction: adaptivity should stop helping once the number of ordering classes grows. We do not treat it as an obstacle to argue around.

Two papers motivate the gap. Decentralized two-sided sequential tests for A normal mean shows, asymptotically and only for the Gaussian two-sided mean, that thresholding the sign and then switching after feedback to interval quantizers is Bayes-optimal. Its reported Bayes risk is 0.204 against 0.949 and 0.465 for static alternatives at cost $c=0.01$. That paper gives no non-asymptotic or contraction-based explanation, and no extension beyond the Gaussian case. Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity proves that adaptivity reduces range dependence from multiplicative to an additive $\log(\lambda/\sigma)$ term in estimation. Our conjecture is the testing analogue for the "which alternative" ambiguity.

The lower-bound side reuses contraction techniques from Converses for distributed estimation via strong data processing inequalities, which chains quantization and noise as contracting kernels, and from Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction. We must address the latter head on, because it already treats a composite problem: identity testing against everything far in total variation, with $\Theta(k)$ versus $\Theta(k^{3/2})$ samples for public- versus private-coin 1-bit protocols. That work is minimax over large nonparametric alternative sets and uses randomized channels. We instead target instance-dependent rates for low-dimensional parametric families, deterministic threshold channels, and the specific role of one feedback round. Where our hard instances resemble theirs, for example an unknown direction on a sphere, we expect to recover their scaling as a consistency check.

Research Program

The theoretical work proceeds in three steps.

The first step proves a simultaneous reverse data processing inequality. We will give upper and lower bounds on $\kappa_D$ in terms of the geometry of the likelihood-ratio orderings across $\Theta_1$. A natural candidate is the minimal number of cells needed so that within each cell every $\log(dQ_\theta/dP)$ varies by at most a constant. This reduces to the simple-test bound when all alternatives share one ordering, which happens for families with monotone likelihood ratio.

The second step proves the non-interactive lower bound. We fix any channel and apply a strong data processing argument to the worst alternative. The binary-input extremality result in Strong data processing constant is achieved by binary inputs suggests that the worst case can be reduced to a pair of alternatives, and we will test whether this holds.

The third step analyzes the two-stage protocol and the matching localization lower bound. We will work out three families in full: the two-sided Gaussian mean, the Gaussian mean with unknown variance (the nuisance case left open in Distributed Gaussian Mean Estimation under Communication Constraints: Optimal Rates and Communication-Efficient Algorithms), and a $d$-dimensional mean with unknown direction. The two-sided Gaussian mean is instructive because a symmetric interval quantizer already reconciles both alternatives, so $\kappa_D$ should be near its simple-test value. This makes it a negative control where adaptivity should not help much. Computationally, we will extend the poly($k$, $D$) threshold algorithm from the communication-constrained paper to the max–min objective over finite alphabets, and compare it against exhaustive search on small instances.

Baselines

The naive reference point is the centralized, unconstrained test, the generalized likelihood ratio test on raw samples. All sample complexities are reported as multiples of its $n^*$, in the same way Distributed Detection of Sparse Stochastic Signals via Fusion of 1-bit Local Likelihood Ratios reports that its improved 1-bit detector needs about $1.53Q$ sensors against the centralized detector's $Q$. A second weak reference is direct observation thresholding, where each sensor sends the sign of its raw sample against a fixed level. The same paper reports this needs about $3.3Q$ sensors in its setting.

The strongest existing competitor depends on the family. For the two-sided Gaussian mean it is the feedback-then-interval-quantizer test of Decentralized two-sided sequential tests for A normal mean, with reported Bayes risk 0.204 at $c=0.01$. We will reproduce that number before comparing anything. For the other two families, the strongest competitor is the simple-test threshold algorithm from Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities, applied to a single least-favorable alternative, or alternatively to the prior-averaged alternative. No reported result was found on Lacuna for that algorithm on composite families.

Two baselines randomize. One is dithered quantization, with thresholds drawn at random as in the refinement stage of Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity. The other is group splitting, where agents are divided into one group per ordering class and each group uses that class's thresholds.

Every method gets the same $D$, the same total number of agents, and the same samples. Every method also gets the same tuning budget: a fixed number of threshold evaluations, including for the particle swarm search used in the sparse-signal paper. The key ablation keeps our two-stage protocol but forces the second stage to use the max–min non-adaptive partition, which isolates the value of feedback. The mirror ablation removes the max–min design from the non-adaptive protocol. We count the proposal as winning on a family if two things hold. The two-stage protocol must reach a target Bayes error with a sample count whose ratio to $n^*$ stays bounded as $\kappa_D$ shrinks, while the best non-adaptive baseline's ratio grows like $1/\kappa_D$. And the predicted crossover point in $M$ must match the empirical crossover to within the constants of the bounds.

Why not just…?

Why not just design thresholds for the least-favorable alternative? For families with monotone likelihood ratio, this works, and the composite problem collapses to the simple one. We will say so and use those families as controls. When orderings conflict, as with an unknown sign in a non-symmetric family or an unknown direction, thresholds tuned to one alternative carry almost no information about an alternative that ranks observations in the opposite order. The unknown-direction experiment is designed to show this directly. If least-favorable design matches our method there, the core claim is wrong.

Why not just quantize raw observations and skip likelihood ratios? Raw thresholding needs no model knowledge and is robust, and Decentralized Data Reduction With Quantization Constraints shows it can beat sufficient-statistic reduction under correlated observations. Our setting assumes independent samples, where the same line of work and the $1.53Q$ versus $3.3Q$ comparison favor likelihood ratios. We will still report raw thresholding everywhere. In the unknown-variance family, raw sign thresholding is variance-free and is a real threat, and that comparison will settle whether likelihood-based design is worth its model dependence.

Why not just randomize the thresholds? Randomization averages over alternatives and so hedges against ambiguity. That is exactly why it is a serious competitor here, even though On Optimal Quantization Rules for Some Problems in Sequential Decentralized Detection proves deterministic rules are optimal for simple sequential tests. Quasiconcavity need not survive a min over $\theta$, because a minimum of quasiconcave functions can have interior optima. So we treat this as open and compute the best randomized max–min channel alongside the best deterministic one on small finite alphabets. If randomization strictly wins, $\kappa_D$ must be redefined over randomized channels, and we will report that.

Why not just use non-interactive protocols, given the factor-4 result? That result covers simple tests only. The Gaussian two-sided risk gap (0.204 versus 0.465 at the same cost) already suggests feedback matters once the alternative is unknown. Our ablation measures exactly how much.

Proposed Experiments

The main experiments are synthetic, matching the benchmarks in the file. The first reproduces the Gaussian two-sided sequential setting and its reported risks, then sweeps $D \in \{2, 4, 8\}$ and the number of agents. The second covers the unknown-variance Gaussian mean. The third covers a $d$-dimensional mean with unknown direction for $d$ up to 64, where $M$ grows with $d$ and the $\Omega(M)$ localization bound should eventually erase the benefit of adaptivity.

The decisive check is quantitative. Plotting empirical sample complexity divided by $n^*$ against our computed $1/\kappa_D$ should give a line for non-adaptive methods and a flat curve for the two-stage method, until $M$ passes the predicted crossover. A secondary real-data check uses KDD'99 Smurf detection with an unknown attack intensity treated as a composite alternative. Training thresholds there are compared against the reported known-model training error $P_e = 9.3369 \times 10^{-4}$ from A Decentralized Bayesian Attack Detection Algorithm for Network Security. That figure is a known-alternative reference, not a like-for-like target.