Memory Constrained Adversarial Hypothesis Testing

技术摘要：内存受限的对抗性假设检验

问题陈述
本研究探讨了在内存限制和对抗性样本生成这两个同时存在的约束下的二元假设检验问题。检测器被建模为一个具有有限状态空间 $S$ 的时间不变随机有限状态机（FSM）。与样本来自固定分布且独立同分布（i.i.d.）的经典设定不同，该问题考虑的是复合假设设定，其中底层分布属于闭凸集 $\mathcal{P}_0$ 和 $\mathcal{P}_1$。

至关重要的是，该设定具有对抗性。对手知晓真实假设（$H=0$ 或 $H=1$），并从相应的集合（$\mathcal{P}_0$ 或 $\mathcal{P}_1$）中为每个样本 $X_n$ 选择分布。对手的选择是动态的，取决于过去样本的历史以及检测器内部状态的完整历史。目标是最小化渐近平均错误概率，该概率定义为所有可能对抗策略下的最坏情况错误，并作为状态数 $S$ 的函数。

方法论与途径
作者建立在 Hellman 和 Cover 的基础工作之上，他们研究了简单假设（单一分布）下的内存受限假设检验。虽然 Hellman 和 Cover 利用了一种“可饱和计数器”FSM，其转换基于最大化似然比的特定字母，但本文将这种方法推广以处理复合和对抗性设定。

1. 广义 FSM 设计：与其依赖为一种假设相对于另一种假设提供最强证据的固定字母 $x^+$ 和 $x^-$（在对抗性设定中，这些字母可能不存在或不一致），所提出的 FSM 利用定义在字母表 $\mathcal{X}$ 上的非负函数 $f_+$ 和 $f_-$。从状态 $s$ 到 $s+1$ 或 $s-1$ 的转换概率分别由 $f_+(x)$ 和 $f_-(x)$ 决定，且需满足 $f_+(x) + f_-(x) \leq 1$。
2. 鞅分析：对 FSM 的标准分析通常依赖于平稳分布。然而，自适应对手的存在可能破坏遍历性，使得平稳分布分析失效。为克服这一困难，作者采用了基于鞅的分析。他们构建了特定的下鞅和上鞅（通过用势函数 $V(s)$ 调整原始状态计数），以限制 FSM 在决定决策的边界状态与内部状态之间所花费的时间。
3. 极小极大优化：性能界限是通过对函数 $f_+$ 和 $f_-$ 的选择进行优化推导得出的。作者定义了一个广义指数 $\gamma$，涉及对这些函数的上确界以及对对抗性分布的最小值。

主要贡献与结果
本文建立了给定状态数 $S$ 下的极小极大渐近错误概率 $P^*_e(S)$ 的紧确上下界。

• 错误界限：作者证明了：
  $$P^*_e(S) \geq \frac{1}{1 + \sqrt{\gamma}^{S-1}}$$
  $$P^*_e(S) \leq \frac{1}{1 + \sqrt{C\gamma^{S-2}}}$$
  其中 $\gamma$ 和 $C$ 是通过函数 $f_+, f_-$ 的极小极大优化从集合 $\mathcal{P}_0$ 和 $\mathcal{P}_1$ 导出的常数。
• 指数行为：两个界限在 $S$ 中表现出相同的指数行为。因此，错误指数 $\Gamma$ 被精确表征为：
  $$\Gamma = \frac{1}{2} \log \gamma$$
• 弱最不利分布（LFD）：本文引入了“弱 LFD 对”$(p^*, q^*)$ 的概念。如果存在这样的对，错误指数简化为在这些特定分布上计算的 Hellman-Cover 指数：$\gamma = \gamma_{HC}(p^*, q^*)$。这推广了经典结果，即复合检验中的最坏情况错误由“最不利”分布决定。
• 非指示函数的最优性：通过一个具体示例，作者证明了最优函数 $f_+$ 和 $f_-$ 不一定是指示函数（这将对应于选择特定字母）。在某些情况下，字母的线性组合（由非二元函数表示）比任何局限于字母表固定子集的策略产生严格更好的错误指数。
• 极小极大定理的应用：一项重要的技术贡献是证明了尽管函数在标准意义上不是联合拟凸/拟凹的，但在 $\gamma$ 的定义中，最小化（关于分布）和最大化（关于函数）的顺序可以互换。这是通过分解问题并迭代应用 Sion 极小极大定理实现的。

意义
本文严谨地刻画了当内存受限且数据源具有主动对抗性时，统计推断的基本极限。它将经典的 Hellman-Cover 框架扩展到一个更稳健和现实的设定，其中分布未知且可能被操纵。这项工作强调，在对抗性环境中，基于单个符号的简单“硬”决策是次优的；相反，必须基于观测值的加权组合进行随机转换，才能实现最优错误指数。结果提供了对在最坏情况下，内存状态数 $S$ 如何随假设检验问题的难度进行缩放的精确理解。