逐次减半

定义

逐次减半是一种用于超参数优化的迭代筛选方法，按轮次分配计算预算。它接收一组候选配置与一个总预算，在每一轮给所有仍存活的候选分配相同数量的资源，评估后只保留性能排名靠前的 1/η 进入下一轮，并让这些候选在下一轮使用 η 倍于上一轮的资源，直到候选只剩一个为止^[5][1]。当 η 取 2 时，每一轮淘汰一半候选，「逐次减半」的名称即由此而来^[2]。在 scikit-learn 的实现中，这个比例由参数 factor 控制^[6]。

在超参数优化里，每个待评估的配置相当于多臂老虎机问题中的一个臂，损失函数是模型在给定资源量下于验证集上的误差；算法假定投入的资源越多，观测到的损失越接近该配置训练到底时的表现^[7][8]。据此，逐次减半被归入多保真度优化方法：用低保真度的快速评估筛掉大部分候选，再用高保真度评估在少数候选之间做最终比较^[8]。

原理

典型实现需要几个输入：初始候选数 n、单个候选可用的最小资源 r_min 与最大资源 r_max、淘汰比例 η^[5]。算法先随机采样 n 个配置并各分配 r_min 的资源，评估后丢弃表现最差的 1/η，其余配置晋升到下一阶段并获得更大的预算^[5][2]。以 η 取 2、r_min 取 1、r_max 取 8 为例，4 个阶段的候选数依次为 8、4、2、1，单个候选的资源依次为 1、2、4、8^[5]。若事先不知道合适的预算，可用「加倍」策略：先以预算 B=n 完整运行一遍，再把预算翻倍重跑，从而在不知道所需预算的情况下找到最佳配置，最坏情况下多花一倍预算。

第 k 个阶段保留的候选数为 $n_k = n/\eta^{k}$，分配给每个候选的资源为 $r_k = r_{\min}\eta^{k}$^[1]。候选数量随轮次成倍减少，而单个候选的资源成倍增加，因此各阶段消耗的总预算大致相当，整个算法的开销为 $O(B\log_{\eta} n)$；作为对照，用完整预算逐一评估所有配置的网格搜索开销为 $NB$，其中 N 为配置数、B 为单个配置训练到收敛所需的预算^[9]。Jamieson 与 Talwalkar 的分析表明，在损失随资源增加收敛到极限值、且各配置收敛速度未知的假设下，算法能以很高概率保留最优或接近最优的配置^[9]。

流程可示意如下：

flowchart LR

A[采样 n 个配置] --> B[分配资源并评估]

B --> C[按性能排序]

C --> D[保留前 1/η]

D --> E{只剩 1 个配置}

E -->|否| F[资源乘以 η]

F --> B

E -->|是| G[输出最佳配置]

发展历程

逐次减半的算法原型来自多臂老虎机领域。2013 年，Karnin、Koren 与 Somekh 在第 30 届国际机器学习会议（ICML）发表论文，提出用于固定预算下随机最好臂识别问题的 Sequential Halving^[3][10]。

2015 年 2 月，Jamieson 与 Talwalkar 在预印本中把超参数优化刻画为非随机最好臂识别问题，并指出逐次减半虽是为随机设定设计的，却适合这一新框架，同时给出了相应分析^[4]。该工作于 2016 年发表于 AISTATS 会议，实验显示按表现动态分配资源通常比均匀分配快一个数量级达到相近的测试精度^[11][4]。2026 年，这篇论文获得 AISTATS 的 Test of Time 奖^[10]。

2018 年，Li、Jamieson、DeSalvo、Rostamizadeh 与 Talwalkar 在《Journal of Machine Learning Research》发表 Hyperband，通过在多个不同起始预算下反复调用逐次减半，缓解了「第一次淘汰应在何时进行」需要人工设定的问题^[12][10]。2020 年，Li 等人在 MLSys 发表面向大规模并行调参的系统，提出异步逐次减半（ASHA），不再等待整轮评估结束即可把表现较好的候选晋升到下一轮^[5][1]。scikit-learn 在 0.24 版本中引入 HalvingGridSearchCV 与 HalvingRandomSearchCV，把逐次减半作为实验性功能提供给用户^[13]。

应用

scikit-learn 提供的 HalvingGridSearchCV 与 HalvingRandomSearchCV 可直接替代 GridSearchCV 与 RandomizedSearchCV：第 1 轮只用少量资源评估候选，只有一部分候选进入资源更多的下一轮，最后一轮得分最高的候选被选为结果^[13]。被逐轮放大的资源通常是训练样本数，也可以是随机森林中树的数量这类接受正整数的参数^[13][6]。官方示例在支持向量机分类任务上比较了两种搜索，逐次减半找到的参数组合精度与网格搜索相当，耗时则明显更少^[14]。

在 R 语言的 mlr3 生态中，mlr3hyperband 包同时提供逐次减半与 Hyperband，并改进了调度与配置评估的并行化^[15]。在机器翻译与大语言模型的调参中，逐次减半被用作多保真度方法，以在有限算力下筛选配置，研究者还为此整理了应用建议^[8]。有实现把能耗纳入考量，例如 SM2 通过低能耗的探索性预训练提前筛掉低效配置^[16]。Ray Tune、Optuna、Keras Tuner 等调参工具也把这类算法用作提早终止效果不佳试验的默认策略^[10]。

局限

逐次减半的判断依据是带噪声的早期评估，其有效性依赖早期表现与最终表现高度相关这一假设；当相关性不成立时，有潜力的配置可能在最初几轮就被淘汰^[8]。它还假定用部分资源做出的评估能无偏地反映最终性能，而训练动态复杂的模型未必满足这一点^[9]。

淘汰比例 η 的取值同样影响结果：η 越大筛选越快，但过早丢弃有潜力配置的风险也越高^[9]。算法需要使用者事先给出与目标精度相称的总预算，而合适的预算并不容易确定，预算过小会让任何配置都得不到足够的训练资源^[17][9]。作为其扩展的 Hyperband 对延迟见效的配置通常更稳健，逐次减半自身的渐进收敛速度则略逊于这类自适应方法^[9]。

参见

• Hyperband —— 通过在多个不同起始预算下反复运行逐次减半来平衡探索与利用的超参数优化方法。

• 异步逐次减半 —— 逐次减半的异步并行版本，不需要等整轮评估结束就晋升候选。

• 多臂老虎机 —— 逐次减半的理论来源，最好臂识别问题的基本框架。

• 超参数优化 —— 逐次减半最主要的应用场景。

• 多保真度优化 —— 把低成本近似评估与高成本精确评估结合的一类方法。

• 网格搜索 —— 逐次减半常与之比较计算开销的穷举式调参方法。