跳转至

On the Sample Complexity of Robust Binary Hypothesis Testing

作者: Shankar Vallinayagam, Ankit Pensia, Varun Jog
主题: 数理统计 / 假设检验
相关性: 8/10
链接: https://arxiv.org/abs/2605.24741

一、核心问题与贡献

①研究了在Huber（加性）、减性与总变差（TV）三种标准污染模型下，稳健二元假设检验的样本复杂度如何依赖于污染参数\(\varepsilon\)以及不同模型间的复杂度折算关系。②核心工具是基于最不利分布（LFD）的显式构造与Hellinger距离的精细渐近分析。③主要结论是：三种模型的样本复杂度对\(\varepsilon\)均呈现多项式级不稳定性（\(o(\varepsilon)\)的扰动可导致样本复杂度多项式级跳跃），但三种模型在\(\varepsilon\)的常数倍重标度下样本复杂度是等价的（如\(n^*_{\text{Hub}}(\varepsilon) \lesssim n^*_{\text{TV}}(\varepsilon) \lesssim n^*_{\text{Hub}}(2\varepsilon)\)），且低估\(\varepsilon\)会导致检验完全崩溃。

二、基础设定

  • 核心概念与符号：
  • \(p, q\)：离散有限样本空间\(\mathcal{X}\)上的两个概率分布。
  • \(n^*_{\text{Hub}}(\varepsilon), n^*_{\text{Sub}}(\varepsilon), n^*_{\text{TV}}(\varepsilon)\)：分别为Huber、减性、TV污染下，使最差情况I/II类错误之和\(\le 1/10\)所需的最小样本量。
  • \(\mathcal{P}_{\text{Hub}}(p, \varepsilon), \mathcal{P}_{\text{TV}}(p, \varepsilon), \mathcal{P}_{\text{Sub}}(p, \varepsilon)\)：三种污染模型下的不确定性集合。
  • \(p^*, q^*\)：最不利分布，样本复杂度满足\(n^* \asymp 1/d_{\text{hel}}^2(p^*, q^*)\)。
  • \(c', c''\)：似然比截断下界与上界（clips），由不动点方程隐式定义。
  • 关键假设：
  • 离散有限样本空间：\(\mathcal{X}\)是有限集。含义：保证了LFD的存在性及Hellinger距离的良定义，避免了测度论的技术细节。放宽：对连续分布需引入额外的正则条件。
  • 不确定性集合凸性：Huber/TV/减性集合均为凸集。含义：使得minimax检验可归结为LFD间的简单假设检验。
  • 非退化条件：\(d_{\text{TV}}(p, q) > \varepsilon/(1+\varepsilon)\)（减性）或类似界。含义：保证两类不确定性集合不相交，检验问题非退化。
  • 问题背景：已有文献（Huber 1965, Huber & Strassen 1973）对Huber和TV污染给出了LFD的隐式解，但样本复杂度对\(\varepsilon\)的依赖一直不清晰；减性污染的LFD理论更是缺失。与最相关文献的区别：1) Huber (1965)：仅给出Huber/TV的LFD隐式解，本文补全了减性污染的显式LFD公式；2) Pensia et al. (2023)：仅证明小\(\varepsilon\)（\(\varepsilon \lesssim d_{\text{hel}}^2\)）时样本复杂度稳定，本文揭示了超出此范围后的极端不稳定性；3) Chen et al. (2023)/Buhai et al. (2025)：关注自适应与遗忘敌手的计算复杂度差异，本文聚焦统计样本复杂度在模型间的常数因子等价性。

三、主要定理 / 核心结果

  1. 定理3.4（减性污染的LFD显式解）
  2. 原文陈述：对于减性污染，LFD存在且具有与Huber/TV类似的截断似然比结构，截断点\(c', c''\)由方程\(p(H)-c''q(H)=\varepsilon/(1+\varepsilon)\)及\(q(L)-p(L)/c'=\varepsilon/(1+\varepsilon)\)决定。当\(p\)在似然比无穷大处质量过大时，上截断不存在，LFD退化为直接扣除质量。
  3. 直观解释：减性污染等价于以概率\(\ge 1/(1+\varepsilon)\)对事件做条件化（选择性删失）。LFD的构造表明，敌手的最优策略是在似然比极端处最大化删失

Maintained by 陈星宇 · Homepage · Source on GitHub

评论