Improved Distribution Estimation in $\ell_\infty$

技术摘要：改进的 $\ell_\infty$ 分布估计

问题陈述
本文解决了从 $n$ 个独立同分布（i.i.d.）样本中估计未知离散概率分布 $p$ 的经典问题。虽然在 $\ell_1$ 和 $\ell_2$ 损失方面已有广泛的理论研究，但作者专注于 $\ell_\infty$（上确界范数）损失，定义为 $\|\hat{p} - p\|_\infty = \sup_{i \ge 1} |\hat{p}_i - p_i|$。该指标对于现代应用至关重要，例如均匀校准、异常检测以及拟合优度检验，在这些应用中，最大的坐标级差异会触发响应。

核心挑战在于，尽管对于所有离散分布，一致的 $O(1/\sqrt{n})$ 风险衰减成立，但获得尖锐的、依赖于分布的速率以及完全经验化的界（即那些不需要了解未知 $p$ 的泛函的界）仍然困难。这种难度不仅取决于支持集的大小，还受制于未知的 $p$ 的尾部剖面（tail profile）。这项工作建立在并扩展了 Kontorovich 和 Painsky (2025) 发起的非渐近研究基础上，特别解决了关于完全经验置信界以及识别最差情况（最不利）分布的开放性问题。

方法论与框架
作者分析了极大似然估计量（MLE），记作 $\hat{p}$，其中 $\hat{p}_i$ 是符号 $i$ 的经验频率。分析依赖于两个主要的理论框架：

1. 复杂度代理（Complexity Proxies）： 本工作利用了 Kontorovich 和 Painsky (2025) 引入的依赖于分布的复杂度度量，具体为 $v^*(p) = \sup_i p_i(1-p_i)$ 和 $V^*(p) = \sup_i p^\downarrow_i(1-p^\downarrow_i)\log(i+1)$，其中 $p^\downarrow$ 是 $p$ 的非增排列。
2. 局部 Glivenko–Cantelli (LGC) 理论： 为了精细化对依赖于分布行为的理解，论文结合了尖锐的局部 Glivenko–Cantelli 界。这涉及分析两个新的泛函 $S(p)$ 和 $M(p)$，它们捕捉了分布尾部行为和方差结构的不同方面。
3. 解耦与归约（Decoupling and Reduction）： 在进行极小极大（minimax）分析时，作者利用解耦不等式将相关的多项分布采样模型归约为独立的伯努利模型，从而能够应用适用于独立变量的尖锐特征化方法 (Blanchard and Voráček, 2024)。
4. 经验插值（Empirical Plug-ins）： 为了实现完全经验化的界，作者使用其经验对应物（例如 $\hat{v}^*$ 和 $\hat{V}^*$）替换未知的总体泛函，并利用集中不等式来限制经验泛函与真实泛函之间的偏差。

主要贡献与结果

• 极小极大速率与最不利分布：
  论文解决了最差情况期望 $\ell_\infty$ 风险的结构问题。它确立了极小极大速率按 $\Theta(n^{-1/2})$ 缩放。至关重要的是，它识别出一个简单的、固定的最不利分布 $p^\star = (1/2, 1/2, 0, \dots)$，该分布在达到最差风险时仅差常数因子。这一结果回答了一个开放性问题，即证明了 $\ell_\infty$ 估计的最难实例存在于二点字母表上，且不需要与 $n$ 相关的有效支持集大小。

• 完全经验化高概率界：
  作者推导出了一个关于 $\|\hat{p} - p\|_\infty$ 的高概率偏差不等式，该不等式是完全经验化的。该界仅依赖于可观测的插值统计量（$\hat{v}^*$ 和 $\hat{V}^*$），不需要了解未知的泛函 $v^*(p)$ 或 $V^*(p)$。该界能自动适应 $p$ 未知的尾部剖面，同时在最坏情况下保留正确的 $\sqrt{\log(1/\delta)/n}$ 行为。

• 精细的依赖于分布的机制：
  利用 LGC 泛函，论文提供了对估计误差更细致的观察。它引入了 $S(p) = \sup_j p^\downarrow_j \log(j+1)$ 和 $M(p) = \sup_j \frac{\log(j+1)}{\log(2 + \frac{\log(j+1)}{n p^\downarrow_j})}$。

  • $S(p)$ 代表“亚高斯”（sub-Gaussian）部分，当一组坐标承载了足够的质量，使得方差波动成为主要误差来源时，该项占主导地位。
  • $M(p)$ 代表“亚伽马”（sub-gamma）或泊松（Poissonian）部分，捕捉了在样本量为 $n$ 时可见的许多低概率符号的影响。
    论文证明了估计误差受这两个项的最大值（经缩放后）控制，从而展示了三种定性的不同机制：方差主导、尾部主导，以及两者机制均产生较小误差的高度分散剖面。

• 下界：
  论文在 $V^*(p)$ 受约束的情况下给出了一个极小极大下界，表明对于任何估计量，都存在一个满足 $V^*(p) \le V'$ 的分布，使得其期望误差至少为 $c\sqrt{V'/n}$。

意义与主张
论文声称在三个特定方向上深化并扩展了现有的 $\ell_\infty$ 分布估计理论：

1. 理论解决： 它解决了关于最不利分布的问题，证明其是一个简单的二点分布，且与 $n$ 无关，而非复杂的、依赖于 $n$ 的结构。
2. 实际应用性： 通过提供完全经验化的置信界，这项工作使得构建数据驱动的保证成为可能，而无需预先了解分布的尾部剖面。
3. 细致的理解： $S(p)$ 和 $M(p)$ 泛函的引入提供了一个“机制图景”，解释了何时以及为何不同的尾部行为会主导估计误差，从而超越了全局极小极大速率，捕捉到了方差与尾部衰减之间的相互作用。

作者报告了令人鼓舞的经验结果，证明这些界在有限样本中是具有信息量的，尽管其主要贡献仍在于对边界的理论精细化以及对极值分布的识别。