When Does Feedback Help One-Bit Sensors Test Composite Hypotheses?

Picture a sensor network where each sensor may send the central server only one bit per observation. If the server is deciding between two fully known explanations of the data, a recent result says feedback barely matters. Each sensor can fix a cutoff on its likelihood ratio (how much more probable its reading is under one explanation than the other), and letting sensors listen to earlier messages saves at most a factor of four in samples (The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints). Real detection problems are rarely that clean. "Is there a signal?" usually means "is there a signal of some unknown strength, sign, direction, or support?" That is a composite alternative. In that setting the best cutoff for a sensor depends on the very quantity the server does not know. A single-sensor study of a two-sided normal mean found that one round of server feedback, telling the sensor which of three cutoff rules to switch to, cut Bayes risk from 0.465 (best fixed rule) to 0.204 (Decentralized two-sided sequential tests for A normal mean). So the factor-of-four ceiling breaks somewhere between simple and composite testing. Nobody has said where.

This note proposes a single computable quantity that predicts how much feedback can help, and a protocol that achieves the gain. Each candidate alternative has its own best one-bit cutoff. The quantity, a quantizer-mismatch ratio, measures how badly any fixed assignment of cutoffs across sensors serves the worst-case alternative, compared with a cutoff tailored to it. When the ratio is near one, feedback is useless and the factor-four result carries over to composite testing. When it is large, a two-phase protocol wins by roughly that ratio, minus a logarithmic cost for locating the alternative. In the first phase the network coarsely locates the alternative with one-bit messages. In the second, the server broadcasts a short instruction that retunes every sensor's cutoff.

Core Claim

Let $\Theta_1$ be the set of alternatives. For a one-bit threshold rule $q$ applied to the likelihood ratio, let $\rho(\theta,q)$ be the squared Hellinger distance between the distributions of the transmitted bit under the null and under alternative $\theta$. This is a per-sample measure of how much evidence one bit carries. A non-interactive network assigns cutoff rules to sensors according to some allocation $\pi$, which is a fraction of sensors per rule. Each sensor's rule is still deterministic, so this does not conflict with the result that randomized local rules are suboptimal (On optimal quantization rules for sequential decision problems). An interactive network could ideally give every sensor the best rule for the true $\theta$. The mismatch ratio is

$$M = \frac{\min_{\theta\in\Theta_1}\max_q \rho(\theta,q)}{\max_{\pi}\min_{\theta\in\Theta_1}\mathbb{E}_{q\sim\pi}\,\rho(\theta,q)} \ \ge 1 .$$

The denominator is linear in $\pi$, so the minimax theorem rewrites it as a game against a least-favorable prior over alternatives. This makes $M$ computable by a small linear program over a discretized set of candidate cutoffs.

The conjecture is that the sample complexities of the best non-interactive and best sequentially interactive one-bit protocols satisfy

$$\frac{n_{\text{non-int}}}{n_{\text{int}}} \asymp \frac{M}{1 + L/n_{\text{int}}},$$

up to universal constants. Here $L$ is the number of samples the interactive protocol spends locating the alternative, roughly the logarithm of how many distinguishable cutoff rules matter. The form comes from two pieces. Evidence from independent bits adds up, so sample complexity scales inversely with per-sample Hellinger distance. The localization overhead is additive, as in the noisy binary search of Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity.

The claim makes concrete, falsifiable predictions on cases already in the literature. For detecting a Gaussian of unknown power, the optimal symmetric cutoff (about $1.4821\sigma_0$) does not depend on the unknown power (One-Bit Quantization and Distributed Detection with an Unknown Scale Parameter). There $M=1$, and feedback should buy nothing beyond a constant. For the two-sided mean, $M>1$, which matches the gain seen by Katz et al. For an $s$-sparse mean shift in $d$ dimensions with unknown support, the best scalar likelihood ratio depends on the support. $M$ should then grow with roughly $d/s$, while localization costs only about $\log\binom{d}{s}$ samples, so feedback should give large gains.

Research Program

The theoretical work has three parts. The lower bound applies the reverse data-processing argument of Kazemi et al. alternative by alternative. Their factor-four bound then gives $n_{\text{int}} \gtrsim \max_\theta 1/\max_q\rho(\theta,q)$. Combined with a minimax argument on the non-interactive side, this yields the $M$ separation. The upper bound is a protocol we call locate-then-retune. In phase one, sensors send bits from a fixed, coarse family of cutoffs. The server forms a generalized likelihood ratio estimate $\hat\theta$, restricted to a finite cover of $\Theta_1$. It then broadcasts the index of $\hat\theta$, which costs $\log$(cover size) bits once rather than per sample. In phase two, sensors switch to the likelihood-ratio cutoff that maximizes $\rho(\hat\theta,\cdot)$, with the server fusing bits with alternative-specific weights. This generalizes the single-sensor scheme of Katz et al. to many sensors, finite samples, and structured alternative sets. The third part asks when $M$ is bounded by constants, so that feedback can be skipped. We expect the answer to involve invariance: if a group acting on $\Theta_1$ leaves the optimal cutoff fixed, as scale does for the He et al. problem, then $M$ is bounded.

On the algorithmic side, computing $M$ and the phase-two cutoffs reuses the polynomial-time threshold-channel search of Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints for each alternative. It replaces the particle-swarm search used by Distributed Detection of Sparse Stochastic Signals via Fusion of 1-bit Local Likelihood Ratios with this exact per-alternative search. We deliberately keep observations conditionally independent given the hypothesis. Decentralized Data Reduction With Quantization Constraints shows that local likelihood-ratio reduction can be strictly suboptimal under dependence, so that regime would confound the question. It is left for follow-up work.

Relation to Prior Work

Two lines of work motivate this proposal. The first is the simple-hypothesis ceiling of Kazemi et al.; they explicitly leave composite testing open. The second consists of interaction gains in estimation, which shows the ceiling does not hold in general. Examples include removing a $\log d$ factor (Unified Lower Bounds for Interactive High-dimensional Estimation under Information Constraints), dimension-free sparse estimation via interactive prefix search (Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraints), and two-round support voting for regression (Distributed Sparse Linear Regression under Communication Constraints). These estimation results do not concern testing thresholds. Our contribution is to explain the contrast through one quantity, $M$, rather than treat each problem case by case.

Katz et al. is the closest work. It treats one sensor, three hypotheses, and the asymptotic regime as observation cost goes to zero. We treat many sensors, general finite $\Theta_1$ and its covers, and finite-sample rates, and we add a criterion for when the method is pointless. Recursive Distributed Detection for Composite Hypothesis Testing: Nonlinear Observation Models in Additive Gaussian Noise runs a composite likelihood ratio test over peer-to-peer consensus, but its messages are full-precision real vectors. We impose one bit per sample and a star network. Collaborative Distributed Hypothesis Testing with General Hypotheses studies error exponents for two nodes under a rate budget, not one-bit cutoff design for many sensors.

Baselines

The naive reference point quantizes raw observations with one fixed cutoff and fuses by unweighted majority vote. Majority voting is known to be suboptimal for heterogeneous sensors (A Decentralized Bayesian Attack Detection Algorithm for Network Security). This baseline sets the floor.

The strongest non-interactive competitor is the optimized cutoff allocation. It uses the same likelihood-ratio cutoffs our protocol uses, but assigns them across sensors by solving the denominator of $M$ exactly. Fusion is by the full generalized likelihood ratio over the bits. It is the strongest competitor because it is precisely what our theory says feedback must beat. If it matches locate-then-retune, the proposal fails. In the sparse-signal setting, the published non-interactive likelihood-ratio detector needs 1.53 times as many sensors as an unquantized centralized detector (153 vs. 100). The raw-observation one-bit detector needs 3.3 times as many (Distributed Detection of Sparse Stochastic Signals via Fusion of 1-bit Local Likelihood Ratios). On the two-sided normal mean, the reported Bayes risks at cost $c=0.01$ are 0.204 for the feedback test, 0.465 for the best invariant test, and 0.949 for the intuitive rule $I(|X|\le0.5)$ (Decentralized two-sided sequential tests for A normal mean). We reproduce all of these before extending.

The unquantized centralized test is the ceiling, and sensor-count overhead is reported relative to it. Two ablations isolate the key ingredient, informed retuning. The first keeps both phases but broadcasts a random alternative index instead of $\hat\theta$. The second skips phase one and spends all samples on the optimized allocation; this checks that the gain is not just sample reallocation.

Fairness rules apply to every comparison. All methods get the same sensors, samples, and total bit budget, and the broadcast and phase-one bits count against locate-then-retune. All methods get the same grid of candidate cutoffs, and every method's free parameters are tuned on the same held-out simulation seeds. Beating the strongest baseline means matching its detection power, at equal false-alarm rate, with measurably fewer sensors or samples in the regimes where computed $M>1.5$. It also means not beating it, within noise, where $M\approx1$.

Why not just…?

Why not just optimize a fixed non-interactive allocation of cutoffs? This is the real threat, and it is the denominator of $M$ itself. For scale-type problems, He et al. suggest it is already optimal. The proposal handles this threat by predicting where this alternative wins and testing that prediction. If, on two-sided and sparse alternatives, the optimized allocation comes within a constant of locate-then-retune even though $M$ is large, the conjecture is false and we would report it.

Why not just spend the feedback bits on two-bit messages instead? A two-bit one-shot quantizer can encode several cutoffs at once, so it partially hedges across alternatives. We compare at equal total bits. Feedback costs $\log$(cover size) bits once, while a second bit per sample costs $n$ bits. So the comparison favors feedback when $n$ is large. The experiment sweeps $n$ to find where the advantage changes sides.

Why not just estimate $\theta$ first and then plug it into a fixed test, with no retuning? That is the random-index ablation's sibling: phase one is kept, but phase-two cutoffs stay fixed and only the fusion weights adapt. If adapting the fusion rule alone recovers the gain, the cutoff geometry is not the mechanism. In that case we would narrow the claim to adaptive fusion.

Why not just tolerate latency-free one-shot protocols because interaction is slow? Locate-then-retune needs exactly one broadcast, so its latency cost is a single round trip. We report rounds alongside samples.

Proposed Experiments

Synthetic experiments come first. We reproduce the Katz et al. normal mean benchmark, then extend it to $K$ sensors and to $K>3$ alternatives on a grid of signed means. We run the unknown-scale benchmark of He et al. as a negative control where $M=1$. We run the sparse stochastic signal benchmark of Li et al. with supports drawn uniformly from $\binom{d}{s}$, for $d$ from 10 to 1000, plotting measured sample ratio against computed $M$. The decisive check is whether that ratio tracks $M$ across all three families on one plot, with the scale family sitting at one.

For real traffic we use KDD Cup 1999 with five features (duration, src_bytes, dst_bytes, count, srv_count), as in Nguyen et al. Their test is single-attack: they report minimum training error $9.3369\times10^{-4}$, misdetection 0.0013 on Smurf, and mixed-traffic error "well below 1%". We turn this into a composite test, normal traffic against any of several attack types, which they left open. Here the best cutoffs differ by attack type, and both $M$ and the gain can be measured empirically from estimated conditional distributions. As a robustness check we use the Kyoto-2006+ IID/NEAR/FAR splits from AnoShift: A Distribution Shift Benchmark for Unsupervised Anomaly Detection. On those splits LOF falls from 91.50 to 34.96 ROC-AUC. The robustness question is whether retuning on recent data, the analogue of phase one, slows that decline compared with fixed cutoffs. No reported result was found on Lacuna for one-bit distributed detection on Kyoto-2006+, so that comparison is new rather than against a published number.