Sample complexity bounds for the Jensen-Shannon divergence

技术摘要：Jensen-Shannon 散度的样本复杂度界限

问题陈述
Jensen-Shannon 散度（JSD）是一种广泛使用的、对称且有界的概率分布差异度量，用于衡量 $P$ 与 $Q$ 之间的差异。尽管 JSD 是统计学、信息论和机器学习中的标准工具，但其“操作性”含义——即给定的 JSD 值如何转化为区分这两个分布所需的样本数量——通常仍处于隐性状态。虽然存在基于单次观测的分类误差界限，但关于利用多个独立同分布（i.i.d.）样本来区分分布的 JSD 与样本复杂度之间的关系，仍需进一步澄清。本文旨在解决以下问题：在给定的 JSD 值 $d$ 下，分类器需要多少个 i.i.d. 样本才能以期望的误差率 $\epsilon$ 识别出源分布？

方法论
作者分析了两种不同分类机制下的二元假设检验样本复杂度：

1. 最优对数似然比（LLR）分类器： 一种全局分类器，通过似然比检验同时处理整个序列的 $N$ 个样本。
2. 多数票决（Majority-Vote）分类器： 一种分布式分类器，首先对 $N$ 个独立的单样本决策进行处理，最终决策由多数票决定。这代表了一种场景，即在聚合之前，证据被“硬量化”为每个样本一个比特。

分析依赖于推导连接 JSD 与达到目标误差率 $\epsilon$ 所需样本量 $N$ 的显式界限。

• 对于 LLR 分类器，作者利用 Chernoff 信息量对 Bayes 错误概率进行了界定。他们建立了一条将 Chernoff 信息量与 Bhattacharyya 距离、平方 Hellinger 距离以及 JSD 联系起来的不等式链。
• 对于 多数票决分类器，作者将分类误差建模为伯努利随机变量之和。他们应用 Hoeffding 不等式来界定单样本决策错误的概率，其中使用了关于 JSD 的已知单样本误差率界限。

核心贡献与结果

1. 最优 LLR 分类器的样本复杂度：
   本文证明了对于最优对数似然比分类器，实现误差率 $\epsilon$ 所需的样本量 $N$ 与 JSD ($d$) 成反比。具体而言，定理 1 指出，若 $N \geq \frac{\log(1/\epsilon)}{d \log(2)}$，则 Bayes 误差被限制在 $\epsilon$ 以内。

   • 推导： 证明过程表明，控制误差率指数衰减的 Chernoff 信息量 $C(P,Q)$ 被 $\log(2) \cdot D_{JS}(P,Q)$ 所下界约束。这确立了 $N \propto 1/d$。

2. 多数票决分类器的样本复杂度：
   本文推导了一个聚合独立单样本决策的分类器界限。定理 2 表明，在这种机制下，充分的样本量与 JSD 的平方成反比。具体而言，若 $N \geq \frac{2 \log(1/\epsilon)}{d^2}$，则误差率被限制在 $\epsilon$ 以内。

   • 推导： 通过使用关系式 $p_e \leq \frac{1}{2}(1-d)$ 来界定单样本误差率 $p_e$，并应用 Hoeffding 不等式，作者展示了误差概率以 $(1-d^2)^{N/2}$ 的速度衰减。由此得出的样本复杂度为 $N \propto 1/d^2$。

3. 标度对比：
   核心发现是两者在标度上的定性差异：最优全局分类器需要 $O(1/d)$ 个样本，而分布式多数票决分类器需要 $O(1/d^2)$ 个样本。

意义与主张
本文声称提供了 JSD 值的“操作性解读”，将抽象的散度度量转化为具体的、可操作的数据需求。

• 对标度的解释： $1/d$ 与 $1/d^2$ 的对比凸显了丢弃证据强度的代价。最优 LLR 分类器累积了每一次观测的完整对数似然比，而多数票决规则通过将每个样本硬量化为单个比特，丢弃了单样本证据的强度。多数票决机制中额外的 $1/d$ 因子代表了“局部性的代价”。
• 上下文相关性： 作者将这两种分类器定位为涵盖一个策略光谱的两端。LLR 测试代表了样本复杂度的理论下界 ($1/d$)，而多数票决则代表了粗糙局部决策的极端情况 ($1/d^2$)。本文指出，中间策略（例如软量化或传输置信度比特）将会在这些机制之间进行插值。
• 应用： 研究结果被认为适用于涉及分布式传感、联邦估计或生物信号传递等场景，在这些场景中，样本必须经过压缩、在比特预算限制下进行通信或独立做出决策。在这些背景下，$1/d^2$ 的惩罚量化了由于局部性约束所导致的的信息损失。

作者保持了谦逊的基调，将这些界限视为对 JSD 现有理论理解的直接、自洽的推导补充，而非提出超出其界限范围的新实验应用或未来算法开发。