An iterated-logarithm price of anytime validity for log-optimal e-processes¶
作者: Adrien Corenflos
主题: 数理统计 / 假设检验
相关性: 6/10
链接: https://arxiv.org/abs/2611.11874
一、领域脉络与小综述¶
-
这个方向是什么:本文属于"任意时点有效推断"(anytime-valid inference)这一子方向。其根本问题是:在数据持续累积、决策者可在任意时刻停止并做出推断的场景下,如何构造统计证据(e-process)使其在所有停止时间下都保持有效性(即对零假设的期望不超过 1),同时尽可能保持统计功效(即对数最优性)。该方向的核心张力在于:有效性要求越严格(任意时点),功效损失越大。本文聚焦于量化这一损失——即"任意时点有效性"相对于"固定时点最优性"的 minimax regret 代价。
-
发展脉络(history):
- 奠基工作:Vovk & Wang (2021) 系统定义了 e-value 与 e-process,确立了其作为赌注/证据度量的基本框架;Grünwald et al. (2024, "Safe Testing") 提出 s-value(即 e-value)理论,建立了 e-value 与贝叶斯因子、赌注策略之间的深层联系,并引入"安全检验"(safe testing)范式。这两篇奠定了 e-process 作为任意时点有效推断核心工具的地位。
- 主要进展:Larsson, Ramdas & Ruf (2025) 证明了 numéraire(对数最优 e-variable)的存在性,并建立了其与逆信息投影(reverse information projection, RIPr) 的深刻联系——这是本文的理论基石。Koolen & Grünwald (2022) 提出"对数最优任意时点 e-value"(log-optimal anytime-valid e-values)概念,并建立了 primal-dual 等价性,为 minimax regret 分析提供了工具。Pérez-Ortiz et al. (2024) 将 e-variable 理论推广到群不变(group-invariant)问题,证明最大不变统计量的似然比在单一时点达到 minimax regret——这是本文的关键对比对象。
- 当前 frontier:Hao & Grünwald (2026) 系统分析了指数族下的 RIPr e-variable 与条件 e-variable(COND),并猜想条件 e-variable"几乎"构成 e-process(即 regret 有界)。本文直接回应此猜想。Waudby-Smith et al. (2026) 与 Ram & Ramdas (2026) 建立了渐近增长率的刻画,但作者明确指出"渐近增长率最优性无法区分有界 regret 与 log log T 增长的 regret"——这正是本文的切入点。Koning & van Meer (2026) 声称"任意时点有效性是免费的"(即固定时点最优检验可诱导任意时点有效检验),本文通过构造反例(regret 无界增长)直接反驳了这一论断的适用范围。
-
本文位置:本文是这一脉络的精确化与否定性结果——它证明了在特定但核心的高斯位置模型中,"免费午餐"不存在,任意时点有效性确实需要付出 iterated-logarithm 级别的代价。
-
子线索聚类:被引文献大致落在三条子线索上:
- e-value/e-process 理论基础(Vovk & Wang 2021; Grünwald et al. 2024; Ramdas et al. 2023; Ramdas & Wang 2025):定义、性质、操作意义。
- 最优性与 minimax regret(Larsson et al. 2025; Koolen & Grünwald 2022; Pérez-Ortiz et al. 2024; Grünwald & Koolen 2026; Hao & Grünwald 2026):numéraire、RIPr、群不变方法、条件 e-variable。
-
停止时间与复杂度下界(Farrell 1964; Agrawal et al. 2026; Kirichenko & Grünwald 2021):iterated logarithm 在停止时间下界中的角色,以及无固定样本量假设下的 minimax 率。
-
这个方向在追问的核心问题:
- 何时存在"免费午餐"? 即固定时点最优 e-variable 何时能构成(或近似构成)e-process?Koning & van Meer (2026) 给出了一般性构造,但本文证明其代价可能无界。
- regret 的精确增长率:若无法做到有界 regret,其随 horizon T 增长的最优速率是多少?本文给出 log log T 的精确答案。
-
群不变性 vs 数据流形:Pérez-Ortiz et al. (2024) 的群不变方法在单一时点最优,但本文证明其无法同时满足任意时点有效性——这揭示了群不变性与任意时点有效性之间的根本冲突。
-
⚠️ 作者的 framing(这是作者的说法):作者将缺口 frame 成"任意时点有效性的价格"(price of anytime validity)问题——即从固定时点最优到任意时点有效,regret 的 minimax 代价是多少。他声称:(i) 此代价在最坏情况下为 (1−s²)log log T,且 (ii) 存在单一 e-process 在所有时点达到此速率。作者淡化了 Koning & van Meer (2026) 的"免费午餐"定理——他将其限定为"在固定时点 T 的检验诱导出任意时点有效检验",但指出该构造的 regret 可能无界增长。作者也回避了 Hao & Grünwald (2026) 猜想中"几乎"一词的模糊性——他将其解释为"有界 regret",而本文证明这在高斯位置模型中不成立。
-
张力:被引工作之间存在一个直接矛盾:Koning & van Meer (2026) 声称任意时点有效性"免费",而本文证明其代价为 log log T。这一矛盾的根源在于有效性定义的范围:Koning & van Meer 的构造保证的是固定时点 T 的检验在任意停止时间下有效,但本文考虑的 regret 是相对于每个时点的 numéraire 的损失——后者要求 e-process 在每个时点都接近最优,这是一个更强的要求。此外,Pérez-Ortiz et al. (2024) 的群不变方法在单一时点达到 minimax regret,但本文 Proposition S2 证明其不构成 e-process——这揭示了群不变最优性与任意时点有效性的不可兼得。
二、最核心、最简单的例子 / 数学问题¶
第一步:符号、模型、可观测数据
- 观测数据:\(X_1, X_2, \ldots\) 为独立同分布实值随机变量序列。\(X^t = (X_1, \ldots, X_t)\) 为截至时刻 \(t\) 的观测,\((\mathcal{F}_t)_{t \ge 0}\) 为数据流(\(\mathcal{F}_0\) 平凡)。
- 零假设:\(\mathcal{P} = \{P_\theta = N(\theta, 1)^{\otimes \infty} : \theta \in \mathbb{R}\}\),即方差为 1、均值未知的高斯分布族。
- 备择假设:\(\mathcal{Q} = \{Q_\mu = N(\mu, s^2)^{\otimes \infty} : \mu \in \mathbb{R}\}\),其中 \(s \in (0,1)\) 固定。备择方差 \(s^2\) 严格小于零假设方差 1。
- e-variable(时点 \(t\)):\(\mathcal{F}_t\)-可测、取值 \([0, \infty]\)、且满足 \(\sup_{P \in \mathcal{P}} E_P[E] \le 1\) 的随机变量 \(E\)。
- e-process:过程 \((E_t)_{t \ge 0}\),对每个停止时间 \(\tau\) 满足 \(\sup_{P \in \mathcal{P}} E_P[E_\tau] \le 1\)。
- numéraire(时点 \(t\)):\(E_t^* = dQ_t / dP_t^*\),其中 \(P_t^*\) 是 \(Q_t\) 在零假设凸包上的逆信息投影(RIPr)。它是时点 \(t\) 上对数最优的 e-variable,即 \(E_{Q_t}[\log E_t^*] = \sup_{E \in \mathcal{E}_t} E_{Q_t}[\log E]\)。
- regret:\(R_t(E_t) = E_Q[\log(E_t^*/E_t)]\),衡量 e-process 在时点 \(t\) 相对最优 e-variable 的对数损失。
- minimax regret:\(\Gamma_T = \inf_{(E_t) \text{ e-process}} \max_{0 \le t \le T} R_t(E_t)\),其中 infimum 取遍所有 e-process。
第二步:最小内核
核心问题:是否存在一个 e-process,使得对每个时点 \(t\),其 regret \(R_t(E_t)\) 有界(不随 \(t\) 增长)?如果不行,\(\Gamma_T\) 随 \(T\) 增长的最优速率是多少?
关键观察:在时点 \(t\),numéraire 的显式形式为
为什么 \(E_t^*\) 本身不是 e-process? 关键在于 \(E_t^*\) 对数据流 \((\mathcal{F}_t)\) 是鞅,但对停止时间不一定是 e-process。事实上,存在一个停止时间 \(\tau\)(依赖于 \(X_1\) 与零假设均值 \(\theta\) 的距离),使得 \(E_P[E_\tau^*] > 1\)。直观上,\(E_t^*\) 的构造使用了 \(Y_i\)(逐次残差),而 \(Y_i\) 的分布在零假设下不依赖于 \(\theta\),但 \(X_1\) 携带了 \(\theta\) 的信息——停止时间可以利用 \(X_1\) 来"探测" \(\theta\),从而在 \(E_t^*\) 尚未积累足够证据时停止,破坏 e-process 性质。
为什么 regret 必须增长? 假设存在 e-process \((E_t)\) 使得 \(R_t(E_t) \le C\) 对所有 \(t\) 成立。则 \(E_t \ge e^{-C} E_t^*\)。但 \(E_t^*\) 在零假设下是鞅,而 \(E_t\) 必须在所有停止时间下期望 \(\le 1\)。利用 \(X_1\) 的信息,可以构造一个停止时间 \(\tau\),使得在 \(P_\theta\) 下 \(E_P[E_\tau^*] \approx \exp\{(1-s^2) \log \log T\}\)(由重对数律,\(\sup_{t \le T} t^{1/2}|\bar{X}_t - \theta|\) 的量级为 \(\sqrt{2 \log \log T}\))。因此 \(E_P[E_\tau] \ge e^{-C} E_P[E_\tau^*] > 1\),矛盾。这正是本文的核心技术贡献:将重对数律嵌入 e-process 的 minimax regret 分析,证明 \(\Gamma_T\) 必须至少为 \((1-s^2)\log \log T\) 量级。
为什么上界可达? 本文构造的 e-process 是
三、这篇论文做了什么¶
三句话: 1. 研究了什么问题:在高斯位置零假设 \(\{N(\theta,1)^{\otimes\infty}\}\) 与方差更小、位置未知的复合备择 \(\{N(\mu,s^2)^{\otimes\infty}\}\)(\(s<1\))下,e-process 相对各时点 numéraire 的 minimax regret \(\Gamma_T\) 的精确增长率。 2. 核心工具/方法:将 e-process 的 minimax regret 问题转化为停止时间下的最优停止问题,利用重对数律(law of the iterated logarithm)刻画 numéraire 在零假设下被停止时的最大期望 \(\eta_T\),并构造显式的加权平均 e-process 达到最优速率。 3. 主要结论:\(\Gamma_T / \log \log T \to 1 - s^2\)(当 \(T \to \infty\)),且存在单一 e-process 在所有时点达到此速率。这否定了"有界 regret"猜想,并精确刻画了任意时点有效性的代价。
关键设定与假设: - 零假设:\(\mathcal{P} = \{N(\theta,1)^{\otimes\infty} : \theta \in \mathbb{R}\}\),方差固定为 1,均值未知。 - 备择:\(\mathcal{Q} = \{N(\mu,s^2)^{\otimes\infty} : \mu \in \mathbb{R}\}\),\(s \in (0,1)\) 固定。备择方差严格小于零假设方差。 - 关键假设:\(\rho^2 \ge 1 - s^2\)(混合方差非负性),其中 \(\rho\) 是备择位置上先验的标准差。这一假设保证 numéraire 的逆信息投影存在且为合法概率测度。 - 与已有文献的对比:相比 Pérez-Ortiz et al. (2024) 的群不变方法(要求紧致群作用),本文不要求任何群结构;相比 Hao & Grünwald (2026) 的条件 e-variable(要求充分统计量的条件分布可计算),本文的构造仅依赖逐次残差 \(Y_i\) 的独立性。
主要结果: - 定理 1(核心):对 \(s \in (0,1)\) 和 \(\rho^2 \ge 1-s^2\),\(\Gamma_T / \log \log T \to 1 - s^2\)。证明分上下界两部分: - 上界:构造显式 e-process(Proposition 3(ii)),在几何时点 \(T_j = \lceil \exp(e^j) \rceil\) 处截断 numéraire 并加权平均,证明其 regret 不超过 \((1-s^2)\log \log T + O(\log \log \log T)\)。 - 下界:利用 Lemma 1(对偶下界)和 Lemma 2(测度变换),将任意 e-process 的 regret 下界转化为一个最优停止问题,再用重对数律证明该下界至少为 \((1-s^2)\log \log T + o(\log \log T)\)。 - 命题 1(基本界):\(\Gamma_T \le \log(T+1)\)(均匀加权),且 \(\Gamma_T \le \log \eta_T\)(最优归一化)。后者是上界构造的基础。 - 命题 2(numéraire 显式形式):在高斯位置模型中,numéraire 为 \(E_t^* = \prod_{i=2}^t \ell(Y_i)\),其中 \(Y_i\) 是逐次残差,\(\ell\) 是似然比。该形式在零假设下是鞅,在备择下对数增长率为 \((t-1)\kappa\)。 - 命题 3(最优速率):\(\log \eta_T / \log \log T \to 1 - s^2\),且构造的 e-process 满足 \(\limsup_{t \to \infty} R_t(E_t)/\log \log t = 1 - s^2\)。 - 命题 4(方差更大情形):若 \(s \ge 1\),则 \(\Gamma_T \le \log s\) 有界。这刻画了"免费午餐"成立的边界条件。
证明路线与技术技巧: - 整体路线(5 步): 1. 对偶转化(Lemma 1):利用 Donsker-Varadhan 变分公式,将 e-process 的 minimax regret 下界转化为 KL 散度的 infimum 问题,其中 infimum 取遍"停止的零假设混合分布"。 2. 测度变换(Lemma 2):将 numéraire 的停止期望 \(\eta_T\) 转化为一个高斯随机游走的最优停止问题,即 \(\eta_T = \sup_\tau E[\exp\{(1-s^2) S_\tau^2/(2\tau)\}]\),其中 \(S_t\) 是标准随机游走。 3. 重对数律(Lemma 3):用 Doob 极大不等式和重对数律证明 \(\log \eta_T \le (1-s^2)\log \log T + O(1)\),并给出下界。 4. 上界构造(Proposition 3(ii)):在几何时点 \(T_j\) 处截断 numéraire,用权重 \(1/\{j(j+1)u_j\}\) 加权平均,证明其构成 e-process 且 regret 达到最优速率。 5. 下界论证(Proposition 3(i) 下界部分):构造一个特定的停止时间(基于 \(X_1\) 与运行均值),利用重对数律证明任意 e-process 的 regret 至少为 \((1-s^2)\log \log T\)。 - 关键技术技巧: - 逆信息投影(RIPr):用于构造 numéraire 的显式形式,并证明其最优性。 - 重对数律:这是本文的核心工具,用于刻画 \(\eta_T\) 的精确增长率。作者将重对数律从"几乎必然"提升为"期望"层面的控制,这是技术上的关键一步。 - 几何时点截断:上界构造的核心技巧,将连续时间的 e-process 问题离散化为可计算的加权平均。 - 对偶下界:将 minimax regret 下界转化为 KL 散度问题,避免了直接构造最优 e-process 的困难。
真实例子与应用: - 数值实验(Section 3):对 \(s = 0.3, 0.5, 0.7\) 计算 \(\log \eta_T\) 的上下界,验证了 \((1-s^2)\log \log T\) 的速率。在 \(T = 10^5\) 时,上下界差异不超过 0.051 nats。 - Bernoulli 例子(Example 1):Koolen & Grünwald (2022) 的经典例子,本文用其验证对偶下界(Lemma 1)的紧性。 - Lean 形式化验证(Section 5):作者将所有定理在 Lean 证明助手中形式化,并指出形式化过程改进了三处证明(包括 Proposition 1(ii) 的证明从有限样本空间推广到一般样本空间)。
🔎 结论是否比证明窄: - 是的,存在明显差距。具体表现在: 1. 定理 1 的证明依赖 \(\rho^2 \ge 1-s^2\) 条件,但结论的陈述并未明确此条件。作者在 Section 4.1 中说明此条件保证混合方差非负,但未讨论 \(\rho^2 < 1-s^2\) 时结论是否成立。这是证明比结论窄的典型例子。 2. 上界构造(Proposition 3(ii))的 regret 上界为 \(\log u_j + \log\{j(j+1)\}\),其中 \(u_j\) 的估计依赖 Lemma 3 的常数。作者在 Section 3 中承认这些常数不是最优的,但定理 1 的陈述是渐近精确的 \((1-s^2)\)。这意味着证明给出的常数可能比结论声称的更大。 3. 下界证明中构造的停止时间依赖于 \(X_1\) 与运行均值,但作者在 Section 4.2 中承认,对于 \(s \ge 1\) 的情形,该构造不适用,需要不同的论证(Proposition 4)。结论的适用范围(\(s<1\))比证明技巧的适用范围更广。 4. 作者在 Section 5 中明确提到,Lean 形式化过程发现 Proposition 1(ii) 的原始证明需要有限样本空间假设,而形式化版本推广到了一般样本空间。这说明原始证明确实比结论窄。
四、开放问题¶
-
\(s \ge 1\) 时 \(\Gamma_T\) 的精确值:Proposition 4 仅给出 \(\Gamma_T \le \log s\) 的上界,但未证明下界。作者在 Section 4.3 中猜测 \(\Gamma_T\) 可能趋于 \(\log s\),但未给出证明。扎根于 Proposition 4 的陈述。
-
一般指数族下的推广:本文的证明强烈依赖高斯分布的特殊结构(逐次残差 \(Y_i\) 的独立性、重对数律的显式常数)。对于一般指数族,\(\eta_T\) 的增长率是否仍为 \(\log \log T\) 量级?作者在 Section 5 中推测"我们期望在更大的模型类中也有类似结果",但未给出具体猜想。扎根于 Section 5 的讨论。
-
有界 regret 的充分条件:本文证明高斯位置模型中 regret 无界,但 Hao & Grünwald (2026) 的定理 3 表明某些指数族(如 Bernoulli)的 regret 有界。这两类模型的结构差异是什么?是否存在一个统一的刻画?扎根于 Hao & Grünwald (2026) 的定理 3 与本文定理 1 的对比。
-
调整函数(adjuster)的最优性:Choe & Ramdas (2026) 的 adjuster 应用于 numéraire 后,regret 增长为 \(2\log t\)(Section 3),远慢于本文的 \(\log \log t\) 最优速率。是否存在更优的 adjuster 能达到 \(\log \log t\) 速率?扎根于 Section 3 的数值比较。
-
多维参数与高维推广:本文仅处理一维位置参数。对于高维高斯位置检验,\(\Gamma_T\) 的增长率是否仍为 \(d(1-s^2)\log \log T\)(其中 \(d\) 为维度)?重对数律在高维下的推广(如 Darling-Erdős 定理)可能给出不同速率。这是作者未提及但自然延伸的问题。
提示:要确认上述问题是否为真 gap,建议阅读近期(2024-2026)关于 e-process minimax regret 的文献(如 Ramdas et al. 2025 的综述、Wang & Ramdas 2025 的群不变方法),看是否有工作已解决或部分解决这些问题。若多篇近期论文都指向同一问题,则可能是共识性 gap;若互相矛盾,则可能是机会。
Maintained by 陈星宇 · Homepage · Source on GitHub