🤖 AI

Functional multi-armed bandit and the best function identification problems

本文引入了函数式多臂老虎机和最佳函数识别问题类，以应对如竞争性大语言模型训练等现实场景，并提出了一种新颖的 F-LCB 归约方案，该方案基于非线性优化收敛率构建了具有可证明遗憾界的 UCB 类算法。

原作者： Yuriy Dorn, Aleksandr Katrutsa, Ilgam Latypov, Anastasiia Soboleva

发布于 2026-06-23

📖 1 分钟阅读☕ 轻松阅读

原作者： Yuriy Dorn, Aleksandr Katrutsa, Ilgam Latypov, Anastasiia Soboleva

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一位正在试图从一百个候选食谱中选出唯一最佳食谱来供应盛大宴会的厨师。你拥有的时间（预算）和食材（预算）都是有限的。

在过去的方法（传统方法）中，你可能会尝试把每种蛋糕都稍微烤一点，然后品尝它们，最后再做决定。或者，你会把一个蛋糕一直烤到最后，然后再开始下一个，接着下一个。这两种方法都既慢又浪费。如果你有100个蛋糕，你可能还没烤完前几个，时间就用完了。

这篇论文介绍了一种更聪明的方法来解决这个问题，作者称之为函数式多臂老虎机 (Functional Multi-Armed Bandit, FMAB) 和 最佳函数识别 (Best Function Identification, BFI) 问题。

以下是他们想法的简单类比拆解：

1. 问题所在：“黑盒”蛋糕大赛

通常，当计算机尝试挑选最佳模型（例如 AI 中的神经网络）时，它们将每个模型视为一个“黑盒”。它们不知道蛋糕是如何膨胀的，也不知道食材是如何混合的；它们只品尝最终的结果。

挑战： 训练现代 AI 模型就像烤一个巨大且复杂的蛋糕。这需要耗费数天时间，并花费巨额的电费。你无法承担把每一个候选食谱都烤到最后才去观察结果的代价。
目标： 你需要找到那个误差最低（口感最好）的食谱，并尽可能快地停止在那些糟糕的食谱上浪费时间。

2. 新思路：“智能品尝” (F-LCB)

作者提出了一种名为 F-LCB 的新算法。你可以把它想象成一位非常聪明的副厨，他不仅品尝蛋糕，还理解烘焙的“物理学”。

F-LCB 不再将每个食谱视为一个谜团，而是将其视为一个具有已知速率限制的过程。

类比： 想象你知道“食谱 A”（一种简单的海绵蛋糕）通常每分钟会膨胀一倍。而“食谱 B”（一种密实的果脯蛋糕）每分钟只增长 1%。
F-LCB 的工作原理：
1. 它先让所有食谱都进行微量的烘焙。
2. 它观察“置信下界”（Lower Confidence Bound, LCB）。这是一种高级说法，意思是：“基于这个蛋糕应该膨胀的速度，其最终口感的最坏情况是什么？”
3. 如果一个蛋糕的膨胀速度相对于其潜力而言过慢，算法就会判定：“这个可能是一个失败者”，并停止烘焙它。
4. 它将剩余的所有时间和食材投入到那些展现出最多潜力的食谱中。

3. 为什么这比旧方法更好？

论文将该方法与两个著名的竞争对手进行了对比：连续减半法 (Successive Halving) 和 Hyperband。

竞争对手： 这些像是每轮都会削减一半预算的厨师。他们让每个人都烤一会儿，淘汰掉表现最差的 50%，让剩下的继续烤一会儿，再次淘汰掉表现最差的 50%，以此类推。这种方法很高效，但有点僵化。它们并不关心蛋糕是如何上升的，只关心当前的口味。
F-LCB（作者的方法）： 这位厨师观察的是轨迹。如果一个蛋糕正在快速膨胀，F-LCB 知道它很快就会变得很棒，因此会专注于它。如果一个蛋糕上升缓慢，它知道它永远也赶不上。
结果： 在他们的实验中（在计算机上烘焙“数字蛋糕”），F-LCB 比竞争对手更快、更省计算资源地找到了最佳模型，尤其是在预算紧张的情况下。

4. 他们证明了什么？

作者不仅仅是猜测这行得通；他们通过数学证明了这一点。

下界 (The Lower Bound)： 他们证明了无论你多么聪明，要找到最好的蛋糕，都必须花费最低限度的时长。
上界 (The Upper Bound)： 他们证明了他们的 F-LCB 算法能非常接近那个最短的时间极限。它的效率在数学上是尽可能高的（仅存在微小的误差范围）。

5. 现实世界测试

他们在三种场景下进行了测试：

平滑蛋糕： 标准的、表现良好的数学函数。F-LCB 迅速找到了最佳函数。
粗糙蛋糕： 崎岖不平且难以优化的函数。F-LCB 依然表现良好。
神经网络： 他们使用它来为图像分类任务（识别图片中的物体）挑选最佳的 AI 架构。F-LCB 使用比其他方法更少的训练步骤识别出了最佳模型。

总结

论文的核心观点是：“不要盲目猜测。利用你优化过程的已知速度来预测哪些模型会获胜，并停止在那些注定失败的模型上浪费金钱。”

他们创造了一个名为 F-LCB 的工具，它扮演着智能管理者的角色，不断检查每个候选者的进度，过早地切断那些进展缓慢的选项，并将所有资源投入到赢家身上，从而在过程中节省了大量的成本和时间。

技术摘要：泛函多臂老虎机与最优函数识别

1. 问题陈述

本文研究了在计算预算有限（如竞争性神经网络训练）场景下的模型选择问题。核心挑战是从 $K$ 个候选参数化函数 $\{f_1, \dots, f_K\}$ 中识别出最优函数（例如，最佳的神经网络架构或超参数设置），其中每个函数 $f_i$ 都定义在一个凸决策集 $X_i$ 上。

作者将这两个问题形式化为两个新的问题设定，它们推广了经典的多臂老虎机（MAB）和最佳臂识别（BAI）：

泛函多臂老虎机 (Functional Multi-Armed Bandit, FMAB)： 智能体在每个时间步 $t$ 选择一个索引 $i_t$ 和一个决策向量 $x_{t, i_t} \in X_{i_t}$ 。目标是最小化累积遗憾 $R_O(T) = \sum_{t=1}^T [f_{i_t}(x_{t, i_t}) - f^*]$ ，其中 $f^* = \min_{i} \min_{x \in X_i} f_i(x)$ 。与每个臂都是随机变量的标准 MAB 不同，这里的每个臂都是一个通过黑盒算子（例如梯度）进行优化的未知函数。
最佳函数识别 (Best Function Identification, BFI)： 智能体旨在 $T$ 轮之后识别出单个最佳函数 $J_T$ ，使得最终遗憾 $R_B(T) = \min_{x \in X_{J_T}} f_{J_T}(x) - f^*$ 最小。

论文指出，由于决策空间是连续的，将这些问题简化为标准 MAB（将每个点 $x$ 视为一个臂）会导致不可行的计算成本。因此，所提出的框架利用了底层优化算法的内部动力学。

2. 方法论：F-LCB 算法

为了解决 FMAB 和 BFI，作者提出了 F-LCB (Functional Lower Confidence Bound) 算法。这是一种 UCB 类算法，它不是基于随机变量的统计集中性，而是基于底层基础优化算法的收敛速率来构建置信区间。

核心机制

基础优化器 (Base Optimizers)： 每个候选函数 $f_i$ 都关联一个已知具有特定收敛速率 $g_i(k, \delta)$ 的基础优化算法 $A_i$ （例如，投影梯度下降、加速梯度下降）。
置信下界 (Lower Confidence Bound, LCB)： 在每一步，算法为每个函数 $i$ 维护一个 LCB：
$LCB_i(k_i, \delta) = f_i(x_{i, k_i}) - g_i(k_i, \delta)$
这里， $k_i$ 是分配给函数 $i$ 的迭代次数， $g_i(k_i, \delta)$ 代表在 $k_i$ 步后次优差距（sub-optimality gap）的理论上界。
选择规则： 算法选择具有最小 LCB 值的臂 $i$ 。
更新： 执行基础优化器 $A_{i_t}$ 的一次迭代，更新函数值，并重新计算 LCB。
停止准则（针对 BFI）： 当当前最佳估计值与 LCB 之间的差距低于阈值 $\epsilon$ 时，过程停止，从而确保识别出的函数在 $\epsilon$ 范围内接近全局最优。

该算法通过在观察到某条臂的 LCB 变得不再最优时立即做出反应，有效地平衡了探索（向具有高不确定性或有潜力前景的函数分配预算）与利用（细化当前最佳候选者）。

3. 核心贡献

理论贡献

问题形式化： 论文引入了 FMAB 和 BFI 框架，通过将臂建模为具有已知收敛性质的优化任务，将其与经典 MAB 进行了明确区分。
下界 (Lower Bounds)： 作者为确定性设定下的 FMAB 和 BFI 建立了极小极大下界（minimax lower bounds）。这些界限取决于函数类的复杂度（例如，凸 $M$ $M$ -Lipschitz、 $L$ $L$ -smooth、 $\mu$ $μ$ -strongly convex）。
- 例如，对于凸 $M$ -Lipschitz 函数，下界为 $\Omega(MR\sqrt{T})$ 。
- 对于 $\mu$ -strongly convex 且 $L$ -smooth 的函数，界限为 $\Omega(R^2)$ 。
遗憾上界 (Regret Upper Bounds)： 论文证明了 F-LCB 算法实现的遗憾上界在对数因子范围内与推导出的下界相匹配。
- 在确定性情况下，遗憾取决于基础优化器的收敛速率 $r$ （例如，当 $r=1/2$ 时，为 $O(\sqrt{T})$ ）。
- 在随机情况（不精确算子）下，上界包含了噪声参数，并以高概率成立。

算法贡献

F-LCB 算法： 一种新颖的归约方案，它将优化收敛速率集成到 bandit 选择过程中。它将臂选择步骤与当前最优近似值的更新统一起来。
灵活性： 该框架允许为不同的臂使用不同的基础优化器，只要其收敛速率已知即可。

4. 实验结果

作者通过在合成数据集和真实世界数据集上的数值实验验证了 F-LCB：

合成凸函数：
- 光滑凸函数 (Smooth Convex)： F-LCB 成功识别了三个候选者中的全局最小值函数，并在识别出次优函数后停止了对其更新。
- 非光滑凸函数 (Non-Smooth Convex)： 使用分段线性函数和次梯度法，F-LBC 展示了向最优函数收敛的过程，其累积遗憾与理论界限一致。
- 不精确算子 (Inexact Oracles)： 在存在梯度噪声的情况下，F-LCB 仍能识别出最佳函数，尽管其收敛曲线不如确定性情况下那样清晰。
神经网络选择 (BFI)：
- 设置： 该算法被应用于 CIFAR-100 图像分类任务，从 10 个模型（包括 MobileNet、ShuffleNet 和 ResNet 变体）中选择参数量少于 5M 的最佳架构。
- 对比： F-LCB 与 Successive Halving (SH) 和 Hyperband 进行了比较。
- 结果： 在低预算场景下（例如 $T=50, 100$ ），F-LCB 优于上述基准方法，实现了更低的被选模型平均排名。与 Hyperband（通过在多个 SH 运行中拆分预算）不同，F-LCB 不会永久丢弃模型，而是动态分配资源。在较大预算（ $T \ge 350$ ）下，F-LCB 的表现与 SH 相当，并能稳定识别出最佳模型。

5. 意义与主张

论文声称 F-LCB 为启发式 AutoML 方法（如 Successive Halving 和 Hyperband）以及纯黑盒方法（如贝叶斯优化）提供了一个具有理论依据的替代方案。

理论保证： 与启发式方法不同，F-LCB 利用已知的优化程序收敛速率来推导正式的遗憾保证和识别界限。
效率： 该方法在计算预算紧缺时特别有效，因为它避免了将优化问题视为具有无限个臂的标准 MAB 所带来的亚指数级成本。
适用性： 该框架适用于任何候选模型通过已知收敛性质的迭代优化进行求解的情景（例如，凸松弛、特定优化方法的选择）。

作者承认的局限性

论文明确指出，该方法需要预先了解目标的函数类以及基础算法的收敛速率 $g(k, \delta)$ 。对于深度学习而言，这是一个显著的约束，因为在严格符合算法定义要求的意义下，非凸神经网络训练的收敛速率尚未得到明确定义。因此，虽然该方法适用于凸问题和特定的优化任务，但其在通用神经网络训练中的应用依赖于对 $g(k)$ 的启发式近似。