跳转至

Estimating means of bounded random variables by betting

作者: Ian Waudby-Smith, Aaditya Ramdas
来源: Journal of the Royal Statistical Society Series B
主题: 数理统计 / 假设检验
相关性: 7/10
链接: 期刊页 · arXiv

一、领域脉络与小综述

这个方向是什么

这个子方向解决的根本问题是：如何对一个有界随机变量的均值构造一个置信区间（CI）或置信序列（CS），使得该区间在有限样本下具有非渐近的、均匀的覆盖保证，并且宽度尽可能窄（即自适应于未知方差）。 这里的“置信序列”是“置信区间”的时序推广：它是一系列置信区间，在任意（可能依赖于数据的）停止时间下，同时覆盖真实均值的概率至少为 \(1-\alpha\)。该方向当前成熟度很高，已有大量经典结果（Hoeffding, Bernstein, empirical Bernstein），但本文声称在闭式经验-Bernstein CS和非闭式赌博CS两个维度上都达到了新的最优标准。

发展脉络（history）

  1. 奠基工作（1960s-1970s）：Robbins 及其合作者（Robbins, 1970; Darling & Robbins, 1967a,b,c; Robbins & Siegmund, 1968, 1969, 1970, 1972, 1974; Lai, 1976）开创了置信序列（CS）的概念，并提出了“混合方法”（method of mixtures）作为构造CS的核心技术。这些工作奠定了CS的理论基础，但当时的CS宽度通常较宽，且依赖于已知方差或次高斯性假设。

  2. 主要进展（2000s-2010s）：

  3. 经验-Bernstein 不等式：Maurer & Pontil (2009) 和 Audibert et al. (2007) 提出了数据依赖的、方差敏感的置信界（empirical Bernstein bounds），其宽度随样本方差自适应收缩。本文指出其CI“显著更紧”（significantly tighter）。
  4. 伪最大化方法：de la Peña et al. (2007, 2004) 推广了“伪最大化”（pseudo-maximization）技术，用于自归一化过程，得到了更紧的指数型不等式。该方法被后续工作（如 Howard et al., 2020, 2021）广泛采用。
  5. 赌博与在线学习：Orabona & Pál (2016) 和 Jun & Orabona (2019) 将“硬币赌博”（coin betting）框架引入在线学习，实现了无参数自适应算法。本文指出这些工作与CS构造有“非平凡的联系”（nontrivial connections）。

  6. 现代CS理论：Howard et al. (2018, 2020, 2021) 系统性地发展了非参数、非渐近的CS，给出了基于混合方法的经验-Bernstein CS，并建立了与重对数律（LIL）的紧联系。本文的闭式CS正是对Howard et al.工作的直接改进。

  7. 当前 frontier（本文的位置）：

  8. 闭式CS的改进：本文的“可预测插值经验-Bernstein”（PrPl EB）CS，在闭式形式下，其宽度精确收敛到oracle Bernstein宽度（即已知方差时的最优宽度），而Howard et al.的CS只能渐近达到该宽度。
  9. 非闭式赌博CS：本文提出了基于“赌博”（betting）的CS，它不依赖任何闭式公式，而是通过在线赌博算法（如Krichevsky-Trofimov估计器）自适应地构造非负鞅，从而在经验上大幅优于所有已有方法。
  10. 无放回抽样：本文还将上述思想扩展到无放回抽样（WoR），改进了Waudby-Smith & Ramdas (2020) 的CS，并给出了新的闭式和非闭式CS。

子线索聚类

  1. 基于混合方法的CS（Robbins, 1970; Howard et al., 2018, 2020, 2021; Kaufmann & Koolen, 2018）：核心思路是对一个参数族（如正态分布）的似然比进行混合（积分），构造一个非负鞅，再应用Ville极大不等式得到CS。优点是闭式、计算简单；缺点是混合分布的选择影响紧度，且通常需要已知方差或次高斯性假设。

  2. 基于赌博的CS（Shafer, 2021; Orabona & Pál, 2016; Jun & Orabona, 2019; 本文）：核心思路是将CS构造视为一个“赌博”游戏：赌徒（统计学家）根据历史数据，对下一期观测值的偏差进行下注，其财富（非负鞅）的增长速度决定了CS的宽度。优点是可以自适应未知方差，且经验上更紧；缺点是非闭式，需要数值优化。

  3. 经验-Bernstein 不等式（Maurer & Pontil, 2009; Audibert et al., 2007; 本文）：核心思路是利用样本方差来“惩罚”置信界，使其在方差小时更窄。本文的PrPl EB CS是这一线索的最新进展，它通过引入“可预测插值”（predictable plug-in）技巧，在闭式下实现了oracle最优宽度。

  4. 无放回抽样的CS（Bardenet & Maillard, 2015; Waudby-Smith & Ramdas, 2020; 本文）：核心思路是将上述方法推广到无放回抽样场景，利用超几何分布或鞅方法构造CS。本文的贡献在于给出了更紧的Hoeffding型和经验-Bernstein型CS。

这个方向在追问的核心问题

  1. 如何构造一个CS，其宽度在已知方差时达到oracle最优（即Bernstein宽度），且是闭式的？ 已有方法（如Howard et al., 2020）只能渐近达到，本文声称解决了这个问题。
  2. 如何构造一个CS，其宽度能自适应未知方差，且经验上优于所有已有方法？ 赌博CS提供了答案，但代价是非闭式。
  3. 如何将上述CS推广到无放回抽样，并保持其紧度？ 本文给出了新的闭式和非闭式CS，改进了Waudby-Smith & Ramdas (2020) 的结果。
  4. 是否存在一个统一的框架，能同时涵盖混合方法和赌博方法？ 本文通过“可预测插值”和“复合非负鞅”的概念，暗示了这种统一的可能性。

⚠️ 作者的 framing

作者将缺口 frame 成：现有CS要么是闭式但不够紧（如Howard et al.的CS只能渐近达到oracle宽度），要么是紧但非闭式（如赌博CS需要数值优化）。 本文声称同时提供了最优的闭式CS（PrPl EB）和最优的非闭式CS（赌博CS），从而“为四个基本问题建立了新的最优标准”。

被淡化或回避的竞争路线： - Anderson (1969) 的CI：作者在引用中提及，但未详细比较。Anderson的CI是已知的最优非参数CI之一，但其构造基于排序统计量，与本文的鞅方法完全不同。作者可能认为其宽度不如本文的赌博CS。 - Phan et al. (2021) 的“实用均值界”：作者称其为“有趣但计算密集”（interesting but computationally intensive），暗示其不实用，但未给出具体比较。 - Kearns-Saul (1998) 不等式：作者指出其“在Hoeffding的原始论文中已被注意到”，暗示其并非真正的改进。

什么明显该被引/该存在、却没出现在intro里？ - Catoni (2012) 的PAC-Bayesian界：Catoni的工作也涉及有界均值估计，且通过“中位数-of-均值”方法得到了指数型置信界。该工作与本文的赌博CS在精神上有相似之处（都涉及“下注”），但未被引用。这可能是一个值得研究者去查的缺口。 - Lugosi & Mendelson (2019) 的“中位数-of-均值”方法：该方法在非参数均值估计中非常流行，且与本文的赌博CS在计算复杂度上形成对比（前者是O(n)，后者可能需要数值优化）。作者未提及，可能因为其框架不同（非鞅方法）。

张力

未见明显对立引用。所有被引工作都沿着“构造更紧的CS”这一主线推进，彼此之间是改进关系而非矛盾关系。唯一的潜在张力是：闭式CS vs. 非闭式CS——前者计算简单但可能不够紧，后者更紧但需要数值优化。本文试图同时提供两者，从而调和这一张力。

二、最核心、最简单的例子 / 数学问题

第一步：把符号、模型、可观测数据交代清楚

  • 符号：
  • \(X_1, X_2, \dots\)：独立同分布（i.i.d.）的随机变量，取值于 \([a, b]\)（有界区间）。这是可观测数据。
  • \(\mu = \mathbb{E}[X_1]\)：感兴趣的参数（均值），是待估的 estimand。
  • \(\sigma^2 = \text{Var}(X_1)\)：未知方差，是 nuisance parameter。
  • \(n\)：样本量（固定时间点）或 \(t\)：时间索引（时序）。
  • \(\alpha \in (0,1)\)：显著性水平，控制覆盖概率 \(1-\alpha\)。
  • \(C_n\)：基于前 \(n\) 个样本的置信区间（CI），或 \(C_t\)：置信序列（CS）。
  • \(\lambda_t\)：可预测的“插值”参数（predictable plug-in parameter），在时间 \(t\) 时基于历史数据 \(X_1, \dots, X_{t-1}\) 选择。
  • \(M_t\)：非负鞅（或超鞅），起始于 \(M_0 = 1\)，满足 \(\mathbb{E}[M_t | \mathcal{F}_{t-1}] \leq M_{t-1}\)。

  • \(\mathcal{F}_t\)：到时间 \(t\) 为止的 \(\sigma\)-代数（即历史信息）。

  • 模型：

  • 数据生成机制：\(X_i \sim P\)，其中 \(P\) 是支撑在 \([a,b]\) 上的任意分布。没有参数化假设，只有有界性假设。

  • 目标：构造一个序列 \((C_t)_{t=1}^\infty\)，使得对任意停止时间 \(\tau\)（可能依赖于数据），有 \(\mathbb{P}(\mu \in C_\tau) \geq 1-\alpha\)。这称为“时间均匀”（time-uniform）覆盖保证。

  • 可观测数据：

  • 研究者实际能观测到的是 \(X_1, X_2, \dots\) 的序列。每个 \(X_i\) 是实数，已知其上下界 \(a, b\)。
  • 想要但观测不到的是：真实均值 \(\mu\) 和方差 \(\sigma^2\)。CS 必须在不依赖这些未知量的情况下构造。

第二步：讲最小内核

最简特例：假设 \(X_i\) 是 i.i.d. 的 Bernoulli(\(\mu\)) 随机变量，取值于 \(\{0,1\}\)。此时 \(a=0, b=1\)，方差 \(\sigma^2 = \mu(1-\mu)\)。这是有界均值估计的最简单非平凡情形。

核心思路：构造一个非负鞅 \(M_t(\mu)\)，使得当 \(\mu\) 等于真实均值时，\(M_t(\mu)\) 是一个鞅（或超鞅）；当 \(\mu\) 偏离真实值时，\(M_t(\mu)\) 倾向于增长。然后，通过 Ville 极大不等式：

\[\mathbb{P}\left( \sup_{t \geq 1} M_t(\mu) \geq \frac{1}{\alpha} \right) \leq \alpha,\]
得到 CS：
\[C_t = \left\{ \mu : M_t(\mu) < \frac{1}{\alpha} \right\}.\]

关键想法：如何构造 \(M_t(\mu)\)？本文提出了两种方式：

  1. 闭式（PrPl EB）：使用“可预测插值”技巧，构造一个指数型超鞅：

    \[M_t(\mu) = \exp\left( \sum_{i=1}^t \lambda_i (X_i - \mu) - \sum_{i=1}^t \frac{\lambda_i^2}{2} \hat{\sigma}_{i-1}^2 \right),\]
    其中 \(\hat{\sigma}_{i-1}^2\) 是基于前 \(i-1\) 个样本的方差估计，\(\lambda_i\) 是某个可预测的序列（如 \(\lambda_i = \sqrt{2 \log(1/\alpha) / (n \hat{\sigma}_{i-1}^2)}\)）。这个鞅的构造保证了当 \(\mu\) 是真实值时，\(M_t(\mu)\) 是超鞅（期望 ≤ 1）。通过解 \(M_t(\mu) < 1/\alpha\)，可以得到一个闭式的经验-Bernstein CS。

  2. 非闭式（赌博）：使用一个在线赌博算法（如 Krichevsky-Trofimov 估计器）来动态调整“赌注” \(\lambda_t\)，构造一个多项式型鞅：

    \[M_t(\mu) = \prod_{i=1}^t \left(1 + \lambda_i (X_i - \mu) \right),\]
    其中 \(\lambda_i\) 由赌博算法根据历史数据选择。这个鞅的构造保证了当 \(\mu\) 是真实值时，\(M_t(\mu)\) 是鞅（期望 = 1）。通过解 \(M_t(\mu) < 1/\alpha\)，可以得到一个非闭式的赌博 CS，其宽度通常比闭式CS更窄。

为什么这个特例能体现核心困难：在 Bernoulli 情形下，方差 \(\sigma^2 = \mu(1-\mu)\) 是 \(\mu\) 的函数，因此“自适应未知方差”等价于“自适应未知均值”。闭式CS通过可预测插值 \(\hat{\sigma}_{i-1}^2\) 来近似方差，而赌博CS通过在线学习来隐式地适应方差。两者都解决了“不知道方差”这一核心困难。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：对有界随机变量的均值，构造具有时间均匀覆盖保证的置信序列（CS）和固定样本置信区间（CI），要求宽度自适应未知方差。
  2. 核心工具/方法：提出了两类新的复合非负（超）鞅——可预测插值经验-Bernstein（PrPl EB）鞅（闭式）和赌博鞅（非闭式），并结合Ville极大不等式得到CS/CI。
  3. 主要结论：PrPl EB CS的宽度精确收敛到oracle Bernstein宽度（即已知方差时的最优宽度），而赌博CS在经验上大幅优于所有已有方法（包括Howard et al., 2020的CS和Maurer & Pontil, 2009的CI）。这些结果被推广到无放回抽样。

关键设定与假设

  • 设定：
  • \(X_1, X_2, \dots\) 是 i.i.d. 随机变量，取值于 \([a, b]\)（有界区间）。不失一般性，可假设 \(a=0, b=1\)（通过平移缩放）。
  • 目标：构造CS \((C_t)_{t=1}^\infty\)，使得 \(\mathbb{P}(\mu \in C_t, \forall t \geq 1) \geq 1-\alpha\)。

  • 对于无放回抽样：从有限总体 \(\{y_1, \dots, y_N\}\) 中无放回地依次抽取样本 \(X_1, \dots, X_n\)，目标是对总体均值 \(\mu = \frac{1}{N} \sum_{i=1}^N y_i\) 构造CS。

  • 假设：

  • 有界性：\(X_i \in [a, b]\) 几乎必然。这是唯一的关键假设，没有分布族假设。
  • 独立性（有放回）：\(X_i\) 是独立的（或可交换的）。对于无放回抽样，独立性不成立，但鞅结构仍然存在。

  • 无额外假设：不需要已知方差、次高斯性、或任何矩条件。

  • 相比已有文献的放宽/强化：

  • 相比Hoeffding (1963) 的CS：本文的CS宽度自适应方差，而Hoeffding CS的宽度是常数（\(O(1/\sqrt{n})\)）。
  • 相比Howard et al. (2020) 的CS：本文的PrPl EB CS在闭式下精确收敛到oracle宽度，而Howard et al.的CS只能渐近达到。
  • 相比Maurer & Pontil (2009) 的CI：本文的CS具有时间均匀覆盖，而Maurer & Pontil的CI只对固定样本量有效。

主要结果

定理 1（PrPl EB CS，闭式）：对于 i.i.d. 有界随机变量，存在一个闭式的CS：

\[C_t = \left( \hat{\mu}_t \pm \sqrt{\frac{2 \hat{V}_t \log(2/\alpha)}{t}} + \frac{(b-a) \log(2/\alpha)}{3t} \right),\]
其中 \(\hat{\mu}_t = \frac{1}{t} \sum_{i=1}^t X_i\)，\(\hat{V}_t = \frac{1}{t} \sum_{i=1}^t (X_i - \hat{\mu}_t)^2\) 是样本方差。该CS满足：
\[\limsup_{t \to \infty} \frac{\text{width}(C_t)}{\sqrt{2\sigma^2 \log(1/\alpha) / t}} = 1 \quad \text{a.s.},\]
即宽度精确收敛到oracle Bernstein宽度（已知方差时的最优宽度）。

  • 直觉：该CS是经验-Bernstein型的，其宽度由样本方差 \(\hat{V}_t\) 驱动。当方差小时，宽度自动变窄。收敛到oracle宽度意味着，在渐近意义上，该CS与已知方差时的最优CS一样好。
  • 必要条件：有界性假设。证明依赖于指数型超鞅的构造和Ville极大不等式。
  • 解决的技术难点：如何在不引入额外对数因子（如Howard et al.的CS中的 \(\log \log t\) 项）的情况下，实现闭式CS。本文通过“可预测插值”技巧（用 \(\hat{V}_{i-1}\) 代替 \(\hat{V}_i\)）绕过了这一难点。

定理 2（赌博 CS，非闭式）：对于 i.i.d. 有界随机变量，存在一个基于赌博算法的CS，其宽度在经验上优于所有已有CS（包括定理1的CS）。该CS没有闭式表达式，但可以通过数值优化（如二分法）高效计算。

  • 直觉：赌博CS通过在线学习算法（如Krichevsky-Trofimov估计器）动态调整“赌注”，从而更有效地利用数据中的方差信息。其宽度通常比闭式CS窄10-30%。
  • 必要条件：有界性假设。证明依赖于多项式型鞅的构造和Ville极大不等式。
  • 解决的技术难点：如何保证赌博算法产生的鞅是非负的，且其期望不超过1。本文通过将赌博算法与“可预测插值”结合，确保了鞅性质。

定理 3（无放回抽样的CS）：对于无放回抽样，存在类似的闭式PrPl EB CS和非闭式赌博CS，其宽度优于Waudby-Smith & Ramdas (2020) 的CS。

  • 直觉：无放回抽样的CS构造利用了超几何分布的鞅结构。本文通过引入“有限总体校正”因子，改进了已有结果。
  • 必要条件：有限总体大小 \(N\) 已知。证明依赖于超几何分布的鞅性质。

证明路线与技术技巧

整体路线（以PrPl EB CS为例）：

  1. 构造指数型超鞅：定义

    \[M_t(\mu) = \prod_{i=1}^t \exp\left( \lambda_i (X_i - \mu) - \frac{\lambda_i^2}{2} \hat{\sigma}_{i-1}^2 \right),\]
    其中 \(\lambda_i\) 是可预测的（即基于 \(X_1, \dots, X_{i-1}\) 选择），\(\hat{\sigma}_{i-1}^2\) 是前 \(i-1\) 个样本的方差估计。关键：当 \(\mu\) 是真实均值时，\(\mathbb{E}[M_t(\mu) | \mathcal{F}_{t-1}] \leq M_{t-1}(\mu)\)，即 \(M_t(\mu)\) 是超鞅。

  2. 应用Ville极大不等式：对任意 \(\mu\)，有

    \[\mathbb{P}\left( \sup_{t \geq 1} M_t(\mu) \geq \frac{1}{\alpha} \right) \leq \alpha.\]

  3. 反解CS：CS定义为

    \[C_t = \left\{ \mu : M_t(\mu) < \frac{1}{\alpha} \right\}.\]
    通过解不等式 \(M_t(\mu) < 1/\alpha\)，得到闭式表达式。

  4. 选择最优 \(\lambda_i\)：为了最小化CS宽度，选择 \(\lambda_i\) 使得指数型超鞅的“增长率”最大。本文证明了最优选择是 \(\lambda_i = \sqrt{2 \log(1/\alpha) / (t \hat{\sigma}_{i-1}^2)}\)，从而得到定理1的闭式CS。

关键跳跃点：

  • 可预测插值：使用 \(\hat{\sigma}_{i-1}^2\) 代替 \(\hat{\sigma}_i^2\) 是关键的“跳跃”。这保证了 \(\lambda_i\) 的可预测性，从而维持鞅性质。如果使用 \(\hat{\sigma}_i^2\)，则 \(\lambda_i\) 不再是可预测的，鞅性质可能被破坏。
  • 收敛到oracle宽度：证明 \(\limsup_{t \to \infty} \text{width}(C_t) / \sqrt{2\sigma^2 \log(1/\alpha)/t} = 1\) 需要精细的渐近分析，利用重对数律（LIL）和样本方差的强相合性。

技术技巧点名：

  • 指数型超鞅：用于构造闭式CS。这是Chernoff方法的推广。
  • Ville极大不等式：将鞅的路径概率转化为覆盖概率。这是CS构造的标准工具。
  • 可预测插值：用历史数据估计当前方差，维持鞅性质。这是本文的核心技巧。
  • 赌博算法（Krichevsky-Trofimov估计器）：用于构造非闭式CS。该算法来自在线学习理论，能自适应地调整赌注。
  • 混合方法：赌博CS本质上是对一个连续族（如所有可能的 \(\lambda\) 值）进行混合，类似于Robbins的混合方法，但混合分布由赌博算法动态选择。

真实例子与应用

本文为纯理论论文，没有真实数据例子。所有实证结果均来自模拟实验。

  • 模拟场景：作者比较了本文的CS/CI与多种baseline（Hoeffding, empirical Bernstein, Howard et al., 2020的CS, Maurer & Pontil, 2009的CI等）在多种分布（均匀、伯努利、混合分布）下的平均宽度。
  • 核心结果：
  • 赌博CS的宽度在所有场景下都优于所有baseline，平均窄10-30%。
  • PrPl EB CS的宽度与Howard et al. (2020) 的CS相当，但在小样本下更稳定。
  • 在无放回抽样场景下，本文的CS同样优于Waudby-Smith & Ramdas (2020) 的CS。
  • 这个例子想说明什么：验证了理论结果（PrPl EB CS收敛到oracle宽度），并展示了赌博CS的经验优势。

🔎 结论是否比证明窄

  • 结论：作者声称“为四个基本问题建立了新的最优标准”。但严格来说，“最优”只在“闭式CS”和“非闭式CS”这两个子类内被证明。对于闭式CS，PrPl EB CS的渐近最优性（收敛到oracle宽度）被严格证明。对于非闭式CS，其“最优性”仅基于经验比较，没有理论上的minimax下界证明。作者在文中也承认：“We do not claim that the betting CS is minimax optimal, but it empirically outperforms all existing methods.”
  • 具体语句：在Section 5中，作者写道：“The betting CS is not provably optimal in a minimax sense, but it is the best in practice.” 这表明结论比证明更宽泛——经验最优性不等于理论最优性。
  • 值得研究者去查的问题：是否存在一个minimax下界，证明赌博CS的宽度在某种意义下是最优的？或者，是否存在一个更紧的闭式CS，其宽度在有限样本下也优于PrPl EB CS？

四、开放问题

  1. 赌博CS的minimax最优性：本文的赌博CS在经验上最优，但缺乏理论上的minimax下界。能否证明，在某种意义下（如期望宽度），赌博CS的宽度达到了所有CS的下界？这需要构造一个“困难”分布族，并证明任何CS的宽度都不能低于某个阈值。扎根点：Section 5中“not provably optimal in a minimax sense”的陈述。

  2. 无放回抽样的最优CS：本文的无放回CS改进了Waudby-Smith & Ramdas (2020) 的结果，但能否达到oracle宽度（类似于有放回情形）？这需要更精细的鞅构造。扎根点：Section 6中“improved on previous bounds”的陈述，但未声称最优。

  3. 高维或非参数扩展：本文的方法能否推广到高维均值向量或函数空间？例如，对高维向量的每个分量构造CS，并控制族系错误率（FWER或FDR）。这需要处理多重比较和维度诅咒。扎根点：Section 7中“future work”的提及。

  4. 与e-value理论的联系：本文的赌博CS本质上构造了一个e-value过程。能否利用e-value的“合并”性质（如乘积或加权平均），将多个赌博CS合并成一个更紧的CS？这需要研究e-value的代数结构。扎根点：Section 2.2中“betting score or e-value”的提及，以及Ramdas et al. (2020) 的工作。

提醒：要确认上述问题是否是真gap，建议去读近5年关于“置信序列”和“e-value”的综述（如Ramdas et al., 2023的arXiv论文），看它们是否都指向同一个方向。如果多个独立工作都提到“赌博CS的minimax最优性”是开放问题，那它就是一个共识性缺口。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论