Kometo：无需平滑假设的自适应多保真度优化新标杆

TL;DR

在黑盒优化（Black-box Optimization）领域，多保真度（Multi-fidelity）方法通过在低精度（低成本）评估与高精度（高成本）评估之间做权衡，试图在有限预算 $\Lambda$ 下找到最优解。本文提出的 Kometo 算法打破了以往需要预知函数平滑度或偏差模型的桎梏，通过巧妙的 Zipf 采样 与 Rank-based 比较，在理论和实战中均达到了 SOTA 性能。

痛点深挖：偏差函数 $\zeta$ 的不可知性

在自动机器学习（AutoML）中，训练 10 个 Epoch 的模型性能是训练 100 个 Epoch 的“保真近似”。

• 先前工作的弊端：如 MFPDOO 等方法，必须假设你提前知道“10 个 Epoch 离收敛到底差多少”（即偏置函数 $\zeta$）。但这在逻辑上是悖论：如果你已经理解了收敛曲线，优化问题也就解决了一半。
• 数学直觉：作者意识到，我们不需要知道偏置的确切数值，只需要知道在同一保真度下，方案 A 是否优于方案 B。这种从“量值”到“秩（Rank）”的升华，是 Kometo 鲁棒性的关键。

核心机制：分层划分与 Zipf 采样

Kometo 的运作流程可以看作是在一棵潜力树（Potential Tree）上进行有预算限制的搜索。

1. 架构解析

Kometo 将搜索空间 $X$ 进行分层划分（Hierarchical Partitioning）。在每一个深度 $h$，算法决定探索多少个单元，以及用什么样的保真度去评估它们。

(上图展示了 Kometo 在多个基准测试上的收敛曲线，可见其在大多数任务中比 MFPDOO 更快触达低遗憾区域。)

2. Zipf 采样策略

为了在“深度（局部精细搜索）”和“广度（全局探索）”间平衡，Kometo 规定：

• 在浅层（小 $h$）开辟大量单元，使用低保真度。
• 在深层（大 $h$）开辟少量单元，使用高保真度。 这种设计确保了算法不会在一条没有前途的路径上浪费过多的高保真预算。

理论成就：首次给出的下限证明

本文不仅提出了算法，还填补了该领域的理论空白——证明了多保真度优化的简单遗憾下限（Lower Bound）。

• 多项式成本假设：若保真度提升与成本成幂律关系，遗憾下限为 ${\Lambda }^{-\frac{1}{d+1/\alpha }}$。
• 指数成本假设：遗憾随预算呈指数级衰减。 Kometo 在无需参数输入的情况下，匹配了上述所有理论下限（仅差对数因子）。

实验与战绩

作者在合成函数（Branin, Hartman 等）和真实的 SVM 超参数调节任务上进行了测试。

(实验显示：Kometo 除了在极个别高维函数上略逊于 SequOOL，在大多数真实场景下表现出了极强的韧性，尤其是在 SVM 文本分类调优中，其准确率提升速度显著领先。)

深度洞察

Kometo 的成功在于其**“完全自适应”**的特性。在工业界，我们面对的往往是未知的“冷启动”优化任务，Kometo 这种不依赖平滑参数 $(u,\rho )$ 的设计，使其成为了比贝叶斯优化更易用的备选方案。

局限性：

1. 确定性假设：目前主要针对确定性反馈，在极高噪声环境下的表现仍有待进一步理论支撑。
2. 计算复杂度：虽然采样效率高，但在超高维空间（$d$ 很大）中，任何分层划分方法都会面临“维度灾难”。

总结

这篇论文是典型的“理论指导实践”的佳作。它告诉我们：要在多保真度优化中做到最优，不需要去拟合复杂的偏差公式，只需要保持“乐观”，并在对的时间点选择对的评估精度。