线性回归短视贝叶斯主动学习风险的近似比

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

线性回归短视贝叶斯主动学习风险的近似比

https://arxiv.org/pdf/2607.06642

摘要：

主动学习研究一个基本问题：我们应该选择什么数据来观察？最优实验设计中的贪心算法是一种常见的启发式方法，并且也等价于线性回归的短视贝叶斯主动学习，这是一种用单步最优选择代替长期规划的通用框架。在这项工作中，我们证明了贪心算法风险的同类首个近似比，该近似比在相差一个绝对常数的意义下是紧的。该近似比与最大初始杠杆得分（MILS）呈线性关系，MILS是一个新发现的量，对贪心算法的性能至关重要。最后，我们用简单的数值模拟来说明这些结果。

1 引言

最优实验设计和主动学习是在预算约束下选择信息数据的两种密切相关的范式。两者都提出了同一个基本问题：在可以从候选输入池中进行选择的自由下，我们应该观察哪些输入，以最小化模型参数估计误差或未来预测误差？在实验设计中，选择通常是离线做出的，而在主动学习中，它们是在观察到新标签时自适应地做出的。然而，对于本工作所考虑的模型贝叶斯线性回归，观测值不会影响估计或预测风险，因此离线和自适应设置是等价的。因此，该任务是一个特定的集合优化函数（A/V-最优设计），其搜索空间大小为，这排除了在任何现实设置中使用暴力方法的可能性。

虽然精确优化是NP难的[Li, 2025]，但已经开发了近似算法。在这项工作中，我们专注于贪心算法。贪心算法从空集开始，并重复添加能产生最大即时风险减少的点，直到选出k个点。贪心算法不仅是离线设置中的实用选择，而且更重要的是，它解决了自适应设置中的一个基本问题。在自适应设置中，为了避免规划的难处理性，最常见的贝叶斯主动学习算法[MacKay, 1992, Gal et al., 2017, Smith et al., 2023]依赖于一种短视方法：选择能最优地减少风险的观测，就好像它是最后一步一样。“单步最优”和“多步最优”之间的联系是文献中研究很少的一个空白。我们通过分析等价的贪心算法来关注这一联系。

关于贪心算法与该问题的最优策略相比如何，令人惊讶地知之甚少。现有的保证[Bian et al., 2017, Chamon and Ribeiro, 2017]对估计或预测风险（A/V-最优设计）的减少量给出了界。通过证明风险减少是单调的且近似次模的，这些工作表明贪心算法达到了最优减少量的一个常数比例。然而，对于减少量的常数因子近似因子通常是空洞的。据我们所知，贪心算法是否对风险本身实现了常数因子近似，仍然是一个未解决的问题。

我们通过以下贡献填补了这一空白：

• 常数因子风险保证。 我们证明了贝叶斯线性回归的倒数风险（reciprocal risk）在 Das and Kempe [2018] 的意义下是近似次模的（approximately submodular）。将这一点与现有的关于近似次模性下贪心算法的分析相结合，得出了贪心算法所实现风险的首个常数因子近似保证。该常数是依赖于问题的量——最大初始杠杆得分（MILS）。
• 显示紧性的参数化难例。 我们构造了一族问题，在这些问题上，贪心算法的风险被证明是最优风险的 MILS 倍（即比最优风险大一个 MILS 因子），这与我们的上界相匹配。这表明我们保证中的问题依赖因子是必要的，而非分析的伪影（artifact）。
• 数值模拟。 我们使用数值模拟来说明之前已知的界以及我们的界，并确认在我们构造的例子中贪心算法的糟糕表现。

我们在第 2 节提供了精确的问题陈述，在第 3 节涵盖了必要的背景和相关工作，在第 4 节和第 5 节提供了我们的上界和下界，然后在第 6 节展示了一个说明性示例。

2 问题陈述

确切地说，我们的问题陈述如下：

2.1贪婪算法

需要注意的是，在出现并列（ties）的情况下存在非确定性。当我们证明贪心算法的某个结果时，我们要求该定理对任何打破并列（tie-breaking）的选择都成立。

对于离线问题，该算法因其简单性和计算效率而具有吸引力。贪心算法的运行时间为。在线性回归的主动学习中，贪心算法等价于短视（myopic）算法，该算法因其免去了规划的需要而具有吸引力。

3 背景与相关工作

3.1 主动学习

主动学习研究的是存在大量未标记数据和有限标注预算的场景。主动学习算法为了获得最佳的测试性能，会自适应地选择接下来要标注哪些点。几种最近的方法研究了短视贝叶斯（myopic Bayesian）设置 [Gal et al., 2017, Kirsch et al., 2019, Mussmann et al., 2022, Smith et al., 2023]，其中通过最小化期望成本（例如，损失、熵）来选择下一个点或一批点。鉴于规划的计算开销（原文此处写作 computational planning of planning，疑似笔误，意指计算成本或复杂性），这些方法仅最小化单步之后的成本，类似于贪心算法。

3.2 贝叶斯线性回归

值得注意的是，在这种情况下，由于目标函数值不依赖于观测值，而仅依赖于其被观测这一事实，因此自适应性不起作用。因此，该设置下的主动学习等价于集合优化，从而消除了算法分析的一个复杂性来源。

3.3 最优实验设计

3.4子模性、近似子模性和曲率

3.5 次模性与 A/V-最优设计

据我们所知，应用于 A-最优设计的贪心算法现有的唯一近似保证见于 Bian 等人 [2017] 和 Chamon 与 Ribeiro [2017] 的工作中。在这两种情况下，分析的对象是减少量（reduction）

4 上界

4.1 近似次模性的紧性

在本节中，我们证明我们要关于 γ γ 的界是紧的，且曲率任意接近 1。注意近似次模性和曲率不依赖于预算 k k，因此我们在以下陈述中省略它们。

4.2 引理 1 的证明

5 下界

我们现在构造一个具体的问题，以表明该上界在常数范围内是紧的。

6 说明性数值示例

7 讨论

本工作的结果不仅为常见的贪心启发式算法提供了首个 A/V-最优性准则的近似比保证（针对的是风险本身而非风险减少量），而且解决了主动学习中的一个更基本的问题。几乎所有的主动学习算法都通过仅关注当前的数据标注迭代，从而避免了跨越多个数据标注迭代的规划。据我们所知，目前尚无针对短视算法的测试损失近似比的现有保证。在此，对于贝叶斯逻辑回归，[结果表明] 短视数据标注几乎与完全规划的数据标注相匹配，至少当 MILS（最大初始杠杆得分）较小时是这样。我们希望这项工作能为未来对其他模型的分析奠定基础，特别是那些自适应选择不等价于离线选择的模型。

原文链接： https://arxiv.org/pdf/2607.06642