The Approximation Ratio for the Risk of Myopic Bayesian Active Learning for Linear Regression

技术摘要：关于近视贝叶斯主动学习在回归问题中风险近似比的研究

问题陈述
本研究探讨了在预算约束下，贝叶斯线性回归中最优数据选择的基本问题。具体而言，给定由 $n$ 个候选输入向量组成的集合 $V = \{v_i\}_{i=1}^n \subset \mathbb{R}^d$ 以及先验精度矩阵 $\Lambda$，目标是选择一个大小为 $k$ 的子集 $S$，以最小化后验参数估计风险。风险定义为后验协方差矩阵的迹：
$$f(S) := \text{tr}\left( \left( \Lambda + \sum_{i \in S} v_i v_i^\top \right)^{-1} \right)$$
在主动学习的语境下，这对应于“近视”（myopic）设置，即算法通过选择下一个能使即时风险降幅最大的点来进行决策，从而有效地用一步最优选择取代了长期规划。虽然该集合函数的精确优化是 NP-hard 的，但贪心算法是标准的启发式方法，它通过迭代添加能产生最大即时风险降幅的点来构建集合。

方法论与理论框架
本文通过将分析重点从“风险降幅”（此前研究的主题）转向风险函数的“倒数” $F_{\text{reciprocal}}(S) = 1/f(S)$，来分析贪心算法的性能。

1. 近似次模性（Approximate Submodularity）： 作者证明了 $F_{\text{reciprocal}}$ 是近似次模的。他们利用了 Das 和 Kempe [2018] 引入的“次模性比例”（submodularity ratio, $\gamma$) 概念。不同于以往研究侧重于界定风险降幅的次模性（这可能导致对最终风险的界限变得无意义），本研究推导出了倒数风险的次模性比例的下界。
2. 关键参数（MILS）： 本文的一个核心贡献是确定了一个与问题相关的参数——最大初始杠杆得分（Maximum Initial Leverage Score, MILS），定义为：
   $$h_{\max} = \max_{i \in [n]} v_i^\top \Lambda^{-1} v_i$$
   作者证明，倒数风险的次模性比例被限制在 $(1 + h_{\max})^{-1}$ 之内。
3. 近似保证： 通过结合推导出的次模性比例与现有的关于近似次模函数贪心最大化的理论结果，作者推导出了贪心算法相对于最优风险的近似比的上界。

主要贡献与结果

• 首个常数因子风险保证： 本文提供了第一个针对 A-最优（A-optimal）和 V-最优（V-optimal）实验设计中，贪心算法所实现的风险本身（而非风险降幅）的常数因子近似保证。其近似比被证明为：
  $$\frac{f(S_{\text{greedy}})}{f(S^*)} \leq h_{\max} + \frac{1}{1 - 1/e} \approx h_{\max} + 1.582$$
  该结果表明，贪心算法的性能随最大初始杠杆得分呈线性缩放。

• 界的紧致性（Tightness of the Bound）： 作者利用哈达玛矩阵（Hadamard matrices）构建了一系列显式问题实例，以证明所推导的界在绝对常数因子意义上是紧致的。他们展示了存在某些实例，其中贪心算法的风险大约是最优风险的 $h_{\max}$ 倍。这证实了对 $h_{\max}$ 的依赖是必要的，而非分析过程中的人为产物。

• 先前界的局限性： 通过数值模拟，本文说明了基于风险降幅的现有近似保证（例如 Bian 等人 [2017], Chamon 和 Ribeiro [2017]）即使在预算较小时也可能变得失效（无法提供有意义的最优风险下界），尤其是在初始风险 $f(\emptyset)$ 较大时。相比之下，本文提出的新界限始终保持有效。

意义与主张
本文声称填补了关于近视主动学习理论理解方面的重大空白。虽然众所周知，贪心算法可以实现风险降幅的常数比例，但此前尚不清楚它们是否能实现最终风险本身的常数因子近似。

作者认为，这一结果对于主动学习至关重要，因为几乎所有实际的贝叶斯主动学习算法都依赖于近视（一步）规划，以规避多步规划的复杂性。这项工作首次提供了理论保障，证明对于贝叶斯线性回归，只要最大初始杠杆得分较小，这类近视策略的表现几乎可以媲美完全规划的策略。作者将此项工作定位为未来分析其他模型的基石，特别是那些自适应选择与离线选择不等价的模型。