A Complexity Measure for Active Learning in Multi-group Mean Estimation

技术摘要：多组均值估计中主动学习的复杂度度量

问题表述

本文研究了在 $d$-臂老虎机（$d$-armed bandit）设定下，多组均值估计中的主动学习问题。学习者的任务是在固定的预算 $T$ 内，自适应地在 $d$ 个组（臂）之间分配样本，以最小化最差情况不确定性指数（worst-case uncertainty index）。具体而言，目标是最小化所有臂中最大的方差与样本量之比：
$$\max_{k \in [d]} \frac{\sigma_k^2}{n_k}$$
其中 $\sigma_k$ 是第 $k$ 组分布的标准差，$n_k$ 是第 $k$ 组被采样的次数。这些分布属于一个已知的具有有限方差的假设类 $\mathcal{H}$，尽管具体的实例（即分布的元组及其方差）是未知的。

性能通过归一化遗憾（normalized regret）来衡量，该指标定义为已实现风险与最优基准风险（即已知方差并进行最优分配时可实现的风险）的比值减去 1。作者认为归一化遗憾是一个合适的度量，因为它具有尺度不变性，并且能够隔离学习方差的难度，而不像标准遗憾那样，即使在分配极差的情况下，也会随着 $T \to \infty$ 而平凡地趋于零。

方法论与框架

本文引入了一个局部极小极大框架（local minimax framework）来推导信息论下界。不同于依赖加性遗憾结构（例如累积遗憾或最佳臂识别）的经典多臂老虎机（MAB）下界，这项工作处理的是一个非加性的、最大值型（max-type）目标。

该方法论依赖于两个新颖的技术要素：

1. 损失诱导的 $\ell_1$ 几何（Loss-Induced $\ell_1$ Geometry）： 作者指出，该问题的决策空间几何结构并非欧几里得几何（如加性遗憾设定中那样），而是受 $\ell_1$ 几何支配。这是从归一化超额风险的非线性采样计数结构中推导出来的。
2. 基于表示的实例生成器（Representation-Based Instance Generator）： 作者没有通过猜测特定的对抗性族，而是开发了一种系统化的方法来构建困难实例。他们通过涉及超立方体编码和线性映射的表示映射来参数化局部困难族。这使得将下界构造简化为显式的随机矩阵计算，从而能够处理该问题中固有的各向异性和精细的异方差性。

该框架定义了一个围绕基准标准差向量 $\sigma$ 的局部实例类 $\mathcal{H}_\rho(\sigma)$，由局部半径 $\rho$ 和容差 $\tau$ 控制。目标是界定局部极小极大值 $V_{\rho,\tau}(\sigma)$。

核心贡献与结果

1. 方差局部曲率 (VLC)
核心理论贡献是定义了一个新的复杂度度量，称为方差局部曲率（Variance Local Curvature, VLC），记作 $\text{VLC}_\rho(\sigma \mid \mathcal{H})$。该度量捕捉了在假设类 $\mathcal{H}$ 内，局部方差变化所产生的（以 KL 散度衡量的）信息量。

• 对于平滑类，VLC 被证明是方差-费舍尔信息量（variance-Fisher information）的一种重参数化。
• 本文提供了常见族（如高斯、拉普拉斯、指数、伽马分布）的 VLC 闭式解。

2. 通用局部极小极大下界
作者证明了一个关于归一化遗憾的通用下界，将问题的难度分解为三个正交因子：
$$\text{Regret} \gtrsim \sqrt{\frac{\|\sigma\|_0}{T}} \cdot \sqrt{\sum_{k=1}^d \frac{\text{Het}_k(\sigma)}{\text{VLC}_\rho(\sigma_k \mid \mathcal{H})}}$$
其中：

• 预算项（Budget Term）： $\sqrt{\|\sigma\|_0/T}$，其中 $\|\sigma\|_0$ 代表有效维度（非零方差臂的数量）。
• 异方差指数（Heteroscedasticity Index, $\text{Het}_k$）： 一个衡量不确定性分布是否均匀的项。它惩罚那些不确定性集中在少数臂上的实例（使问题实际上变得低维），对比之下，分散的不确定性则较易处理。
• 模型曲率（Model Curvature, $1/\sqrt{\text{VLC}}$）： 一个反映在假设类 $\mathcal{H}$ 内区分方差水平之内在难度的结构项。较低的曲率意味着一个“更丰富”的类别，其中方差的变化产生的 KL 信号微弱，从而使学习变得更加困难。

3. 锐度与基准测试
本文将此下界与目前最强的通用上界（Aznag 等人，2025）进行了基准测试。

• 近优性（Near-Optimality）： 在广泛的区间内，该下界在忽略对数因子（$\tilde{O}$）的情况下与上界匹配。
• 系统性差距： 作者指出了在高度异方差实例中的系统性差距。现有的上界使用权重项 $\text{Het}^+_k(\sigma) = \sigma_k^2 / \|\sigma\|_2^2$（即 Oracle Neyman 权重），而下界则利用了一个精细化的项 $\text{Het}_k(\sigma)$，该项考虑了某一臂的方差与实例其余部分的相互作用。这种差距源于现有的上界未能充分考虑到：在“尖峰”情形下（即某一臂占主导地位时），识别最优分配的难度会比标准界限所暗示的消失得更快。

意义与主张

本文声称提供了针对此类特定最大风险目标的最早的、适用于任何有限方差假设类的通用下界。其意义在于：

• 统一性： 它提供了一个统一的框架，将预算、实例的异方差性以及模型的结构复杂度分离开来。
• 几何洞察： 它修正了非加性老虎机目标的几何直觉，确立了 $\ell_1$ 几何作为此类场景下决策分离的正确度量。
• 算法指导： 通过识别下界与当前上界之间的差距（特别是关于异方差性的处理），本文为未来的算法改进提供了具体的指导。它表明，未来的上界分析应不再使用统一的置信预算，而是利用能够快速消除方差趋于零的臂的实例加权度量。

作者总结道，其结果表征了非退化情形下的局部极小极大难度，并指出其证明技术（经过调整的几何结构和基于表示的实例生成）同样适用于其他标准老虎机模板失效的非加性分配问题。