On the Tightness and Computational Tractability of Higher-Dimensional Confidence Sequences¶

会议: NeurIPS 2026
arXiv: 2610.03727
代码: https://github.com/fdenoodt/portfolio-confidence-sequences
领域: 学习理论
关键词: 置信序列, 随时有效推断, 投资组合财富过程, 外近似超椭球, 多目标序贯检验

一句话总结¶

本文系统研究了基于对赌财富过程的一维置信序列向高维有界向量均值的拓展范式，证明了投资组合置信集在保持紧致性上最优但计算不可行，进而提出了包围盒、$\ell_p$ 超椭球及其交集三种具备闭式解或线性复杂度的外近似区域，在严谨保持随时统计有效性的同时实现了高效的多指标序贯监控与早期停止。

研究背景与动机¶

现代数据驱动决策场景普遍具有连续监控和随时停止（Optional Stopping）的本质需求。例如在企业级 A/B 测试中，实验者希望同时追踪停留时间、点击率、加购率等多个核心业务指标；在机器学习模型上线对比中，需要持续监测总体准确率、Brier 分数以及多个敏感子群体的公平性表现，一旦累积证据足够充分便立即做出上线或回滚决策。传统的固定样本量假设检验在这种连续观察并随时停止的机制下面临严重的假阳性膨胀（Peeking Problem）。置信序列（Confidence Sequences, CSs）通过超鞅理论与 Ville 不等式，构建出随时间收缩且在任意停止时刻均能以不低于 $1-\alpha$ 概率覆盖真实均值的置信集合序列，成为随时有效统计推断的核心工具。

然而，现有多维有界向量均值的置信序列在紧致性与计算可行性之间存在尖锐矛盾。一方面，以 Ryu & Wornell (ICML 2024) 为代表的非参数对赌置信集虽然紧致，但区域缺乏闭式几何表达，每个时间步验证候选点从属关系的计算复杂度高达 $\mathcal{O}(t^{D+1})$，高维下几乎无法运行；另一方面，以 Banach Sphere 或 Conf Sphere 为代表的闭式置信球虽然计算极快，但在所有坐标方向上等径膨胀收缩，无法适应各坐标轴方差的异质性，导致置信体积过度保守。针对有界随机向量，若仅简单使用坐标级的一维对赌置信区间配合 Bonferroni 乘法修正，其构成的超矩形会随着维度 $D$ 增长而急剧松弛，严重阻碍多指标场景的快速决策。

为了打破“紧致但不实用”与“实用但太保守”的困境，本文从一维对赌财富过程（Hedged Capital Process）出发，深入探讨其向高维拓展的理论极限。核心 idea：将多维坐标财富过程加权聚合为投资组合财富过程作为紧致基准，进而推导计算复杂度关于维度呈线性的三种外近似置信区域（包围盒、$\ell_p$ 超椭球及其交集），并从理论上提供网格间下界保护机制，确保算法落地后仍具备严格的随时统计有效性。

方法详解¶

整体框架¶

本文构建了一套从一维对赌财富过程到高维紧致且可计算置信序列的完整外近似方法论。系统的输入为流式到达的有界随机向量序列 $\mathbf{y}_t \in [0,1]^D$（满足条件期望 $\mathbb{E}[\mathbf{y}_t \mid \mathcal{F}_{t-1}] = \boldsymbol{\mu}$），用户设定的名义错误率 $\alpha \in (0,1]$，以及坐标权重向量 $\mathbf{w} \in \Delta^D$。系统首先在各坐标轴上维护独立的对撞资本过程 $k_t^d(x_d)$，然后通过理论分析揭示加权投资组合区域 $\mathcal{C}^{\mathrm{port}}$、最大值区域 $\mathcal{C}^{\max}$、加权 Bonferroni 超矩形 $\mathcal{C}^{\text{bonf}}$ 之间的偏序与等价关系。为解决 $\mathcal{C}^{\mathrm{port}}$ 缺乏闭式几何表达且体积不可算的难题，算法模块化地构建了三种外近似：基于全局极小值估计的坐标投影包围盒 $\mathcal{C}^{\text{bbox}}$、基于两接触点解析拟合的 $\ell_p$ 超椭球 $\mathcal{C}^{\ell_p}$（及带网格间安全性证明的 $\mathcal{C}^{\ell_p\mathrm{safe}}$），以及两者的几何交集 $\mathcal{C}^{\text{bbox }\cap~\ell_p}$。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["流式有界观测序列 yt ∈ [0,1]^D<br/>指定置信水平 1-α 与权重 w"] --> B["坐标独立对撞资本过程<br/>kt^d(xd) = max(θ kt^+, (1-θ) kt^-)"]
    B --> C["不可行紧致基准：投资组合过程<br/>Kport(m) = ∑ wd kt^d(md) ≤ 1/α"]
    C --> D["包围盒外近似：1. 全局极小值保守估计与二分投影<br/>求解各轴 wd kt^d(xd) ≤ 1/α - ∑_{j≠d} wj k★^j"]
    C --> E["超椭球外近似：2. 双接触点解析拟合与网格安全修正<br/>k~^d(x) = |x-ad|^p / bd^p - cd 拟合与平移安全下界"]
    D --> F["交集外近似：3. 紧致外边界蒙特卡洛抽样<br/>C_bbox ∩ C_lp 提供最小有效置信超集"]
    E --> F
    F --> G["随时有效决策输出<br/>坐标显著性判别 / 置信体积收缩提前停止"]

关键设计¶

1. 全局极小值保守估计与坐标投影包围盒：同复杂度下严格占优 Bonferroni 投资组合置信集 $\mathcal{C}^{\mathrm{port}} = \{\mathbf{m} \in [0,1]^D \mid \sum_{d=1}^D w_d k^d(m_d) \le 1/\alpha\}$ 难以直接获得显式边界。为了给出各维度的边界，将其他所有维度的资本过程松弛为其在定义域内的全局极小值 $k_\star^j = \min_{x \in [0,1]} k^j(x)$，从而将第 $d$ 维约束孤立为 $w_d k^d(x_d) \le 1/\alpha - \sum_{j \neq d} w_j k_\star^j$。针对对撞资本过程 $k(x) = \max\{\theta k^+(x), (1-\theta) k^-(x)\}$，本文证明了单调函数差值 $h(x) = (1-\theta)k^-(x) - \theta k^+(x)$ 的零点必为 $k(x)$ 的全局极小点，并提出了二分估计算法（Algorithm 1），可以在预设精度下给出严格的理论下界 $\underline{k_\star} \le k_\star$。利用下界代入求解各轴端点 $[l_d, u_d]$，不仅严格保证了 $\mathcal{C}^{\mathrm{port}} \subseteq \mathcal{C}^{\text{bbox}}$，而且理论证明其恒满足 $\mathcal{C}^{\text{bbox}} \subseteq \mathcal{C}^{\max} = \mathcal{C}^{\text{bonf}}$。这意味着包围盒仅需 $3D$ 次二分搜索（时间复杂度 $\mathcal{O}(D C_{\text{eval}} \log(1/\varepsilon))$），计算量与传统 Bonferroni 完全一致，却能利用各坐标轴的非零基础财富产生实质上更紧致的矩形区域。

2. 双接触点解析拟合与网格间安全修正：闭式体积可控的 $\ell_p$ 超椭球 当投资组合集合呈现非轴对齐的倾斜或圆润形态时，超矩形会带来显著的空间浪费。为此，本文设计了单轴替代函数 $\tilde{k}^d(x) := \frac{|x-a_d|^p}{b_d^p} - c_d$，将外近似区域转化为对称 $\ell_p$ 超椭球 $\sum_{d=1}^D \frac{|x_d-a_d|^p}{(b'_d)^p} \le 1$。其中半轴长度为 $b'_d := \frac{b_d \sqrt[p]{1/\alpha + \sum_j w_j c_j}}{\sqrt[p]{w_d}}$，其几何体积具有严格的解析闭式解： $$ V(\mathcal{C}^{\ell_p}) = 2^D \left(\prod_{d=1}^D b'_d\right) \frac{\Gamma(1+1/p)^D}{\Gamma(1+D/p)}. $$ 为了使替代函数满足 $\tilde{k}^d(x) \le k^d(x)$，算法选取目标水位 $\gamma_d = \sqrt[p]{w_d}/\alpha$ 处的两个接触点 $x_{L,d}^{\text{touch}}$ 与 $x_{R,d}^{\text{touch}}$，使中心点 $a_d = (x_{L,d}^{\text{touch}} + x_{R,d}^{\text{touch}})/2$ 与偏置 $c_d$ 获得完全解析表达，仅需在离散网格上单遍扫描比值函数 $R(x) = \frac{|x-a|^p - |x_L-a|^p}{k(x)-\gamma}$ 即可确定 $b_d^p$ 的可行区间。针对实际离散化可能在网格点之间发生微小上穿违反下界约束的风险，本文通过准凸函数的单调性推导了网格间最坏误差界 $L_i^d$，并构造出单步平移安全序列 $k_i^s$（Proposition F.1），从理论上彻底消除了网格间正向误差（$\epsilon_{\max} \le 0$），构建出统计完全有效的 $\mathcal{C}^{\ell_p\mathrm{safe}}$。

3. 紧致外边界蒙特卡洛抽样：交集外近似的高效体积估计 集合交集 $\mathcal{C}^{\text{bbox }\cap~\ell_p} := \mathcal{C}^{\text{bbox}} \cap \mathcal{C}^{\ell_p}$ 构成了本文三套近似中理论体积最小的紧超集。由于该交集不再具有解析体积公式，必须借助蒙特卡洛积分进行估计。直接在高维全空间 $[0,1]^D$ 中均匀投点会导致接受率随维度指数级衰减至零（维度灾难）。本文的关键设计在于将第一步构造的 $\mathcal{C}^{\text{bbox}}$ 直接作为蒙特卡洛采样的紧边界支撑集，由于 $\mathcal{C}^{\text{bbox}}$ 紧密贴合目标区域，抽样接受率大幅提升数个数量级。例如在 $D=20$ 的伯努利混合分布下，包围盒内抽样接受率高达 $35.9\%$，仅需常规样本量即可在可控标准误下精确确定交集区域的体积；在判别点是否属于置信集时，无需重新计算高昂的一维对撞财富，直接在此几何交集上执行低成本代数判别。

损失函数 / 训练策略¶

作为免训练的序贯非参数推断框架，本文算法不涉及神经网络的反向传播，其性能核心取决于每一步各坐标轴对赌“下注比例（Stakes）”的在线自适应更新策略。沿用 Waudby-Smith & Ramdas (2024) 的经验 Bernstein 赌资分配思想，在每个时间步 $t$，根据历史观测的递推均值 $\widehat{\mu}_t$ 与样本方差 $\widehat{\sigma}_t^2$ 自适应调整下注力度： $$ \widetilde{\lambda}t = \sqrt{\frac{2\log(2/\alpha)}{\widehat{\sigma}\right). $$ 其中截断常数设为 }^2 \, t \log(t+1)}}, \quad \lambda_t^+(m) = \min\left(\widetilde{\lambda}_t, \frac{c}{m}\right), \quad \lambda_t^-(m) = \min\left(\widetilde{\lambda}_t, \frac{c}{1-m$c=0.75$，混合权重设为 $\theta=0.5$。该设定保证了财富过程在远离真实值处以指数级速度累积发散，促使置信区域在各维度上根据其固有方差迅速收缩。

实验关键数据¶

主实验¶

论文在合成高维有界数据（单位球分布与伯努利混合分布）、十指标模拟电商 A/B 测试、以及 Adult 人口普查多指标公平性模型评估上进行了全面对比。

在十指标（$D=10$）序贯 A/B 测试中，对比各方法在存在处理效应（With effect）和无处理效应（No effect）时的平均决策停止时间步 $t_{\text{stop}}$ 及决策准确性：

方法	有效应时停止步数 ($t_{\text{stop}}$)	决策结论	无效应时停止步数 ($t_{\text{stop}}$)	决策结论
ConfSphere (Chugg et al., 2023)	10,000 (上限)	无决策 (超时)	10,000 (上限)	无决策 (超时)
BanachSphere (Martinez-Taboada et al., 2024)	5,018	显著差异	8,052	无实质差异
Sub-$\psi$ Ellipsoid (Whitehouse et al., 2023)	5,198	显著差异	6,650	无实质差异
$\mathcal{C}^{\text{bonf}}$ (Bonferroni 基线)	178	显著差异	399	无实质差异
$\mathcal{C}^{\text{bbox}}$ (本文包围盒)	178	显著差异	398	无实质差异
$\mathcal{C}^{\ell_p\mathrm{safe}}$ (本文安全椭球)	178	显著差异	356	无实质差异
$\mathcal{C}^{\text{bbox }\cap~\ell_p\mathrm{safe}}$ (本文安全交集)	178	显著差异	356	无实质差异

在计算复杂度层面，统计在 $t=100$ 时计算置信体积所需的标量财富过程 $k_t^d(\cdot)$ 调用次数随维度 $D$ 的变化：

维度 $D$	$\mathcal{C}^{\text{bbox}}$ (本文)	$\mathcal{C}^{\text{bonf}}$	$\mathcal{C}^{\ell_p\mathrm{safe}}$ (本文)	$\mathcal{C}^{\text{bbox }\cap~\ell_p\mathrm{safe}}$ (本文)	$\mathcal{C}^{\mathrm{port}}$ (精确网格搜索)
$D=2$	$5.01 \times 10^2$	$5.05 \times 10^2$	$1.60 \times 10^5$	$1.61 \times 10^5$	$8.00 \times 10^6$
$D=3$	$7.78 \times 10^2$	$7.78 \times 10^2$	$2.40 \times 10^5$	$2.41 \times 10^5$	$2.40 \times 10^{10}$
$D=5$	$1.30 \times 10^3$	$1.30 \times 10^3$	$4.00 \times 10^5$	$4.01 \times 10^5$	$1.61 \times 10^{17}$
$D=10$	$2.68 \times 10^3$	$2.68 \times 10^3$	$8.03 \times 10^5$	$8.06 \times 10^5$	$1.03 \times 10^{34}$
渐近复杂度	$\mathcal{O}(D C_{\text{eval}} \log(1/\varepsilon))$	$\mathcal{O}(D C_{\text{eval}} \log(1/\varepsilon))$	$\mathcal{O}(D N_p N (\log(L/\text{tol}) + C_{\text{eval}}))$	同左加包围盒二分	$\mathcal{O}(D C_{\text{eval}} N^D)$

消融实验¶

针对超椭球阶数 $p$、接触水位 $\gamma_d$、网格尺度 $N$ 以及安全平移约束对置信体积的影响进行了详尽消融：

配置 / 变体	考察维度 / 条件	表现与体积变化趋势	理论解释与结论
安全变体 vs 非安全变体 ($\mathcal{C}^{\ell_p\mathrm{safe}}$ vs $\mathcal{C}^{\ell_p}$)	$D=2 \sim 10$ 范围对比	体积曲线近乎完全重合，计算耗时仅增加约 $30\%$	安全平移边界修正严格消除了网格间违反风险，且未牺牲几何紧致性
超椭球指数 $p \in \{6, \dots, 16\}$	固定 $D=5$	$p \in [8, 12]$ 时体积取得最小值；过大时数值收敛趋于平缓	较传统 $p=2$（常规二次椭球），高阶 $p$ 更能逼近超矩形平坦拐角
接触水位 $\gamma_d = \sqrt[p]{w_d}/\alpha$	偏离默认比例扫描	在建议设定 $\gamma_d$ 处体积平滑收敛，过高过低会导致半轴拟合松弛	证实了与维度和错误率相关的闭式水位选择公式是优选解
蒙特卡洛抽样基底选择	$D=20, 50, 100$	包围盒基底在 $D=20$ 下接受率 $35.9\%$；全超立方体基底接受率直接趋向于 0	证实了依托包围盒作为采样候选区域是高维交集体积计算的可行支撑

关键发现¶

决策样本量呈数量级削减：在电商多指标 A/B 测试中，本文方法仅需 178 个批次即可检测出关键指标显著提升，而传统置信球基线（Banach Sphere）需要 5,018 批次，ConfSphere 在 10,000 步内完全无法做出判断；所需受试用户数从 400 万以上骤降至 14 万左右，节约了超 $96\%$ 的样本采集成本。
真实场景下的多指标与子群公平性监控：在 Adult 数据集上的模型对比任务中，本文方法在 356 个批次即以统计显著性确认新模型在总体准确率上有 $0.6\% \sim 3.7\%$ 的增益；同时，依靠各坐标轴的联合覆盖性质，精准捕捉到新模型在女性子群准确率上存在高达 $4\%$ 的性能滑坡风险，而所有外在基线在耗尽 509 个批次后依然处于无法判别的未决状态。

亮点与洞察¶

严格证明了最大值财富过程与 Bonferroni 的几何等价性：论文通过鞅论证明了 $\mathcal{C}^{\max} \equiv \mathcal{C}^{\text{bonf}}$，揭示了经典多重假设检验校正本质上对应于最大值财富过程的水平集，为后续将其严格包含在包围盒内提供了扎实的数学基石。
无痛平替传统 Bonferroni 超矩形：$\mathcal{C}^{\text{bbox}}$ 与 Bonferroni 拥有完全相同的 $\mathcal{O}(D)$ 计算复杂度，但通过利用各坐标最小资本下界抵消了部分阈值，实现了在数学上永远不松于 Bonferroni 的稳定收益。
离散网格拟合的理论安全闭环：传统函数数值拟合通常面临“网格点处满足但网格点之间被穿透”的有效性缺陷，本文通过对撞资本函数的准凸连续性构造出严密的区间逐段下界 $L_i$，并以一步网格平移构造出无需稠密网格也能严谨保持超集关系的 Safe 修正。

局限与展望¶

高维交集蒙特卡洛积分的维度瓶颈：尽管包围盒采样将有效接受率延长至 20 维左右，但当维度进一步攀升至 50 或 100 维时，交集超椭球在矩形盒内的体积占比依然发生指数级塌缩，使得交集体积的估计方差增大，需要更具针对性的重要性抽样机制。
未充分挖掘坐标间复杂协方差结构：当前投资组合过程采用独立的坐标财富函数加权聚合，虽然下注参数具备方差自适应性，但尚未显式建模跨指标的非对角协方差旋转特征，未来可探索向多元鞅差和旋转坐标系扩展。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次系统研究了基于对赌的多维置信序列紧致性与可计算性权衡，提出了完备的几何外近似理论。
实验充分度: ⭐⭐⭐⭐⭐ 涵盖理论包含关系证明、不同维度计算代价测试、消融实验、模拟 A/B 测试与真实公平性分类评测。
写作质量: ⭐⭐⭐⭐⭐ 理论推导清晰完备，从一维鞅到高维几何投影逻辑环环相扣，附录证明极其详尽规范。
价值: ⭐⭐⭐⭐⭐ 彻底解决了多指标在线监控与早停推断长期缺乏兼具紧致与快速计算工具的工业界与统计学痛点。

维度 \(D\)	\(\mathcal{C}^{\text{bbox}}\) (本文)	\(\mathcal{C}^{\text{bonf}}\)	\(\mathcal{C}^{\ell_p\mathrm{safe}}\) (本文)	\(\mathcal{C}^{\text{bbox }\cap~\ell_p\mathrm{safe}}\) (本文)	\(\mathcal{C}^{\mathrm{port}}\) (精确网格搜索)
\(D=2\)	\(5.01 \times 10^2\)	\(5.05 \times 10^2\)	\(1.60 \times 10^5\)	\(1.61 \times 10^5\)	\(8.00 \times 10^6\)
\(D=3\)	\(7.78 \times 10^2\)	\(7.78 \times 10^2\)	\(2.40 \times 10^5\)	\(2.41 \times 10^5\)	\(2.40 \times 10^{10}\)
\(D=5\)	\(1.30 \times 10^3\)	\(1.30 \times 10^3\)	\(4.00 \times 10^5\)	\(4.01 \times 10^5\)	\(1.61 \times 10^{17}\)
\(D=10\)	\(2.68 \times 10^3\)	\(2.68 \times 10^3\)	\(8.03 \times 10^5\)	\(8.06 \times 10^5\)	\(1.03 \times 10^{34}\)
渐近复杂度	\(\mathcal{O}(D C_{\text{eval}} \log(1/\varepsilon))\)	\(\mathcal{O}(D C_{\text{eval}} \log(1/\varepsilon))\)	\(\mathcal{O}(D N_p N (\log(L/\text{tol}) + C_{\text{eval}}))\)	同左加包围盒二分	\(\mathcal{O}(D C_{\text{eval}} N^D)\)

配置 / 变体	考察维度 / 条件	表现与体积变化趋势	理论解释与结论
安全变体 vs 非安全变体 (\(\mathcal{C}^{\ell_p\mathrm{safe}}\) vs \(\mathcal{C}^{\ell_p}\))	\(D=2 \sim 10\) 范围对比	体积曲线近乎完全重合，计算耗时仅增加约 \(30\%\)	安全平移边界修正严格消除了网格间违反风险，且未牺牲几何紧致性
超椭球指数 \(p \in \{6, \dots, 16\}\)	固定 \(D=5\)	\(p \in [8, 12]\) 时体积取得最小值；过大时数值收敛趋于平缓	较传统 \(p=2\)（常规二次椭球），高阶 \(p\) 更能逼近超矩形平坦拐角
接触水位 \(\gamma_d = \sqrt[p]{w_d}/\alpha\)	偏离默认比例扫描	在建议设定 \(\gamma_d\) 处体积平滑收敛，过高过低会导致半轴拟合松弛	证实了与维度和错误率相关的闭式水位选择公式是优选解
蒙特卡洛抽样基底选择	\(D=20, 50, 100\)	包围盒基底在 \(D=20\) 下接受率 \(35.9\%\)；全超立方体基底接受率直接趋向于 0	证实了依托包围盒作为采样候选区域是高维交集体积计算的可行支撑