A central question in distributed statistics is the following. Many sensors each see some data and may send only a few bits to a central decision-maker. That center must then decide between two fully specified hypotheses. It is known how much extra data this bit limit costs when each sensor holds a single observation. The cost is surprisingly mild: a factor that grows only logarithmically in the problem's difficulty and shrinks as more bits are allowed. It is not known what happens in the setting that describes most real deployments, where each sensor holds a batch of many observations before it speaks. Examples are a network monitor that sees a window of connections, or a phone that holds a week of logs.
This note proposes to answer that question with a specific mechanism. Each sensor adds up the log-likelihood ratios of its batch. This is one number that tells how much more plausible its data is under one hypothesis than the other, and it is the sensor's sufficient statistic. The sensor then cuts that single number into $2^D$ intervals and reports which interval it landed in. The claim is twofold. First, this scheme is near-optimal for every batch size. Second, the optimal cut points, and the resulting cost of the bit limit, move in a predictable way as batch size grows. The communication penalty should shrink from a $\log n^*$ factor at batch size one toward no penalty once batches are large. Mapping exactly how that transition happens is the main scientific goal.
Core Claim
Setup: $N$ sensors each observe $m$ independent samples from $P$ or from $Q$. Each sensor sends $D$ bits once, and nobody interacts. Let $n^*$ be the number of samples a centralized tester needs. The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints shows that at $m=1$ the required number of sensors is $n^* \max(1, \log n^* / D)$, and that thresholding the likelihood ratio achieves this. We conjecture that with batches the total sample count $Nm$ obeys
$$ Nm \;\approx\; n^* \cdot \max\!\left(1, \frac{\log (n^*/m)}{D}\right), $$
and that interval quantization of the batch log-likelihood ratio achieves this rate.
The heuristic behind the formula runs as follows. At $m=1$ the logarithmic penalty comes from rare, highly informative outcomes whose probability can be as small as $1/n^*$. Resolving them requires spending bits across about $\log n^*$ scales of the likelihood ratio. A batch of size $m$ meets such an outcome with probability about $m/n^*$, which compresses the range of relevant scales to $\log(n^*/m)$.
This conjecture is a hypothesis, not a result. There is a competing possibility, and deciding between the two is the first deliverable. The competitor is a sharp phase transition, analogous to the one Distributed Estimation with Multiple Samples per User: Sharp Rates and Phase Transition found for learning a distribution over $k$ symbols. There, the value of extra bits drops from exponential to polynomial once $m \ge k/2^\ell$.
What is new is the regime rather than the form of the quantizer. The quantizer itself is a likelihood-ratio threshold rule, already known to be optimal for single observations. Every existing threshold-optimality result is either a single-sample result or an asymptotic one:
- Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints proves that the extreme points of the achievable channel set are interval partitions of the likelihood ratio. It computes the best one in time polynomial in the alphabet size, for one sample per node.
- Decentralized Data Reduction With Quantization Constraints shows that quantizing the local sufficient statistic loses nothing when observations are conditionally independent. That result licenses reducing each batch to its scalar log-likelihood-ratio sum, but it gives no rates.
- Optimal Private and Communication Constraint Distributed Goodness-of-Fit Testing for Discrete Distributions in the Large Sample Regime finds that the communication "super-efficiency" disappears when local samples are large. That is consistent with our endpoint, but the result holds only where a Gaussian approximation is valid ($md\log d/\sqrt{n}\to 0$). It says nothing about the rare-event regime where the penalty lives.
Research Program
Reduction to one dimension. Because each batch reduces to one scalar, the batch channel is again an interval partition of the batch log-likelihood ratio. The support of that ratio is the set of sums over types of $m$-sample batches, which for a finite alphabet has polynomial size in $m$. So the instance-optimal $D$-bit quantizer is the solution of a one-dimensional placement of $2^D-1$ cut points. It can be found exactly by dynamic programming over the sorted support. This extends the single-sample algorithm of Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints to batches. It also removes the need for particle-swarm or grid searches:
- Distributed Detection of Sparse Stochastic Signals via Fusion of 1-bit Local Likelihood Ratios uses particle-swarm search to set 1-bit likelihood-ratio thresholds that maximize Fisher information.
- A Decentralized Bayesian Attack Detection Algorithm for Network Security uses brute-force grid search over thresholds on network-traffic features.
Upper bound. We will analyze the rate achieved when the cut points are placed at dyadic scales of the batch-ratio tail, plus a bulk quantizer near the median.
Lower bound. We will apply the one-shot Bayes-error bound and the reverse data-processing inequalities of The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints to the batch channel. The natural hard instances are the "rare informative symbol" family behind their $\log n^*$ term.
Fusion. Fusion is always the likelihood-ratio test on the counts of each message. As A Decentralized Bayesian Attack Detection Algorithm for Network Security showed for heterogeneous sensors, weighting messages by their reliability matters. Majority voting would conflate the effect of quantization with the effect of poor fusion.
Scope. We deliberately stay with simple, non-interactive hypotheses. The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints bounds sequential interaction to a factor of four at $m=1$, so interaction is a secondary question here. Composite testing, which needs shared randomness above the dimension threshold according to Optimal Distributed Composite Testing in High-Dimensional Gaussian Models With 1-Bit Communication, is also out of scope. We would run it only as a follow-up if the simple case turns out clean.
Baselines
Naive reference: decide locally, then count. Each sensor runs its own Neyman–Pearson test on its batch and sends one bit. The center thresholds the count of "Q" votes. This is what an engineer would deploy. Its gap to optimal is the headroom the whole project must justify.
Per-sample reuse of the single-sample optimum. The optimal $m=1$ threshold channel from Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints is applied to individual samples. When $D<m$, a random subset of $D$ samples each sends one bit; when $D \ge m$, the $D$ bits are split across samples. This is the strongest existing method, because it is provably optimal at $m=1$ and is what one gets by ignoring the batch structure. The file reports no numbers for it on batched simple testing (no reported result found on Lacuna for batched distributed simple binary testing). The comparison will therefore be run here, on identical instances with identical $(N, m, D)$ and exact error computation.
Uniform quantizer on the batch log-likelihood ratio. Equal-width cells are placed over the central range of the batch ratio. This is the cheapest version of our scheme. It isolates whether optimized, tail-aware cut points are the key ingredient or whether sufficiency alone does the work.
Estimate-then-compress. The sensor quantizes its empirical type, meaning its histogram of symbols, to $D$ bits using the rate-optimal estimation scheme implied by Distributed Estimation with Multiple Samples per User: Sharp Rates and Phase Transition. The center then tests on the reconstructed histogram.
Fair comparison. All methods use the optimal count-based fusion rule, receive the same total bits, and are scored by exact Bayes error. Any tunable threshold, such as the local decision threshold in the naive baseline or the range in the uniform quantizer, gets the same grid-search budget as our dynamic program's cut points.
What counts as beating a baseline. "Beating" means a strictly smaller total sample count $Nm$ to reach Bayes error 0.05. On rare-event instances we expect the improvement over per-sample reuse and over the uniform quantizer to grow with $\log(n^*/m)$. If the improvement stays a constant factor as $n^*$ grows, the conjecture is wrong.
Why not just…?
Why not just quantize the batch log-likelihood ratio uniformly? This is the real threat. On well-behaved instances, such as a Bernoulli pair or a discretized Gaussian shift, the batch ratio is nearly Gaussian for moderate $m$, and uniform cells may match optimized ones to within a few percent. We expect the advantage of optimized cut points to be concentrated on instances where informative outcomes are rare. That is exactly where the $\log n^*$ penalty of The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints originates. The ablation separates the two cases. If uniform quantization is as good on the rare-event family too, the algorithmic contribution shrinks to "sufficiency plus any reasonable quantizer," and the rate characterization becomes the whole contribution. We will report it that way.
Why not just send one bit per sample with the known single-sample optimum? This protocol ignores that $m$ samples can be merged into one sufficient number before spending bits. When $D<m$ it must throw samples away. A structural fact already favors merging: Distributed Detection of Sparse Stochastic Signals via Fusion of 1-bit Local Likelihood Ratios reports that quantizing the local likelihood ratio needs $1.53Q$ sensors to match a centralized detector with $Q$ sensors, versus $3.3Q$ for quantizing raw observations. The per-sample baseline directly measures how much of that gain survives, or grows, with batching.
Why not just estimate locally and compress the histogram? Estimation spends bits describing the whole distribution, while testing only needs the direction separating $P$ from $Q$. The testing–learning separation in Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction predicts a penalty that grows with alphabet size. Our instances vary alphabet size at fixed $n^*$ to show this. If the penalty stays flat, estimate-then-compress is a viable simpler protocol for small alphabets.
Proposed Experiments
Synthetic instances. The core experiments use finite-alphabet instances where the error of every protocol is computed exactly, from multinomial distributions over message counts, with no Monte Carlo noise. There are three families:
- Bernoulli pairs, where only the bulk of the distribution matters.
- Discretized Gaussian shifts, which also include the $m=1$ sparse-signal setting of Distributed Detection of Sparse Stochastic Signals via Fusion of 1-bit Local Likelihood Ratios as a sanity check. We should recover its roughly $1.482\sigma_w$ threshold and its $1.53Q$ sensor count.
- A rare-informative-symbol family, where $Q$ puts mass $\epsilon \approx 1/n^*$ on a symbol that $P$ almost never produces, with $n^*$ swept over three orders of magnitude.
For each instance, $m$ is swept from 1 to $n^*$ and $D$ from 1 to 6.
Real-data check. We use KDD Cup 1999 Smurf versus normal traffic on the five features used by A Decentralized Bayesian Attack Detection Algorithm for Network Security. The heavy-tailed src_bytes feature is a natural rare-event case. Each sensor holds a window of $m$ connections and sends $D$ bits. At $m=1$, $D=1$ we must reproduce that paper's training minimum error of $9.3369\times10^{-4}$ and its attack-file misdetection rate of $0.0013$. We then ask how much the bit budget can be reduced as windows grow. Probability tables are estimated on the training split and evaluated on held-out files.
Decisive checks. There are three, and all must pass for the core claim to stand:
- On the rare-event family, the measured penalty factor $Nm/n^*$ must track $\log(n^*/m)/D$. If it instead drops sharply at a threshold in $m$, the phase-transition alternative wins, and we will locate that threshold as a function of $D$.
- The derived lower bound must match the dynamic-programming upper bound up to constants across the sweep.
- The optimized batch quantizer must beat per-sample reuse and uniform batch quantization by a margin that grows with $n^*$ on rare-event instances. It must not merely match them.
References
- The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints
- Distributed Estimation with Multiple Samples per User: Sharp Rates and Phase Transition
- Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints
- Decentralized Data Reduction with Quantization Constraints
- Optimal Private and Communication Constraint Distributed Goodness-of-Fit Testing for Discrete Distributions in the Large Sample Regime
- Distributed Detection of Sparse Stochastic Signals via Fusion of 1-bit Local Likelihood Ratios
- A Decentralized Bayesian Attack Detection Algorithm for Network Security
- Optimal Distributed Composite Testing in High-Dimensional Gaussian Models With 1-Bit Communication
- Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction