Sample complexity bounds for the Jensen-Shannon divergence

Technical Summary: Sample Complexity Bounds for the Jensen-Shannon Divergence

Problem Statement
The Jensen-Shannon divergence (JSD) is a widely used, symmetric, and bounded measure of dissimilarity between two probability distributions $P$ and $Q$. While JSD is a standard tool in statistics, information theory, and machine learning, its "operational" meaning—specifically, how a given JSD value translates into the number of samples required to distinguish between the two distributions—remains often implicit. Although bounds exist for classification error based on a single observation, the relationship between JSD and sample complexity for distinguishing distributions from multiple independent and identically distributed (i.i.d.) samples requires further clarification. This paper addresses the question: How many i.i.d. samples are sufficient for a classifier to identify the source distribution ($P$ or $Q$) at a desired error rate $\epsilon$, given the JSD value $d$?

Methodology
The authors analyze the sample complexity of binary hypothesis testing under two distinct classification regimes:

1. Optimal Log-Likelihood-Ratio (LLR) Classifier: A global classifier that processes the entire sequence of $N$ samples simultaneously using the likelihood ratio test.
2. Majority-Vote Classifier: A distributed classifier where $N$ independent single-sample decisions are made first, and the final decision is determined by a majority vote. This represents a scenario where evidence is "hard-quantized" to a single bit per sample before aggregation.

The analysis relies on deriving explicit bounds connecting the JSD to the sample size $N$ required to achieve a target error rate $\epsilon$.

• For the LLR classifier, the authors bound the Bayes probability of error using Chernoff information. They establish a chain of inequalities linking Chernoff information to the Bhattacharyya distance, then to the squared Hellinger distance, and finally to the JSD.
• For the majority-vote classifier, the authors model the classification errors as a sum of Bernoulli random variables. They apply Hoeffding's inequality to bound the probability that the majority of single-sample decisions are incorrect, utilizing a known bound on the single-sample error rate in terms of JSD.

Key Contributions and Results

1. Sample Complexity of the Optimal LLR Classifier:
   The paper proves that for the optimal log-likelihood-ratio classifier, the sample size $N$ required to achieve an error rate $\epsilon$ scales inversely with the JSD ($d$). Specifically, Theorem 1 states that if $N \geq \frac{\log(1/\epsilon)}{d \log(2)}$, the Bayes error is bounded by $\epsilon$.

   • Derivation: The proof demonstrates that the Chernoff information $C(P,Q)$, which governs the exponential decay of the error rate, is lower-bounded by $\log(2) \cdot D_{JS}(P,Q)$. This establishes that $N \propto 1/d$.

2. Sample Complexity of the Majority-Vote Classifier:
   The paper derives a bound for a classifier that aggregates independent single-sample decisions. Theorem 2 shows that for this regime, the sufficient sample size scales with the squared inverse of the JSD. Specifically, if $N \geq \frac{2 \log(1/\epsilon)}{d^2}$, the error rate is bounded by $\epsilon$.

   • Derivation: By bounding the single-sample error rate $p_e$ using the relation $p_e \leq \frac{1}{2}(1-d)$ and applying Hoeffding's inequality, the authors show that the error probability decays as $(1-d^2)^{N/2}$. The resulting sample complexity is $N \propto 1/d^2$.

3. Comparison of Scalings:
   The central finding is the qualitative difference in scaling: the optimal global classifier requires $O(1/d)$ samples, while the distributed majority-vote classifier requires $O(1/d^2)$ samples.

Significance and Claims
The paper claims to provide "operational readings" of JSD values, translating abstract divergence measures into concrete data requirements for distinguishability.

• Interpretation of Scalings: The contrast between $1/d$ and $1/d^2$ highlights the cost of discarding the magnitude of evidence. The optimal LLR classifier accumulates the full log-likelihood ratio of every observation, whereas the majority-vote rule discards the strength of per-sample evidence by hard-quantizing each sample to a single bit before aggregation. The extra factor of $1/d$ in the majority-vote regime represents the "price of locality."
• Contextual Relevance: The authors position these two classifiers as bracketing a spectrum of strategies. The LLR test represents the theoretical lower bound for sample complexity ($1/d$), while the majority vote represents the extreme of coarse local decisions ($1/d^2$). The paper suggests that intermediate strategies (e.g., soft-quantization or transmitting confidence bits) would interpolate between these regimes.
• Applications: The results are framed as relevant for settings involving distributed sensing, federated estimation, or biological signaling, where samples must be compressed, communicated under a bit budget, or committed to independently. In such contexts, the $1/d^2$ penalty quantifies the information loss incurred by locality constraints.

The authors maintain a modest tone, presenting these bounds as a direct, self-contained derivation that complements existing theoretical understanding of JSD, rather than proposing new experimental applications or future algorithmic developments beyond the scope of the derived bounds.