Successive Halving

Successive halving is an algorithm for allocating a fixed computational budget across many candidate configurations in optimization or best-arm identification. Starting from a pool of n candidates, it evaluates all of them for a fixed increment of resource (training iterations or compute budget), discards the bottom half by observed performance, doubles the resource given to each survivor, and repeats until one configuration remains. Zohar Karnin, Tomer Koren, and Oren Somekh originally proposed it for the stochastic best-arm identification problem in 2013.

Kevin Jamieson and Ameet Talwalkar's "Non-stochastic Best Arm Identification and Hyperparameter Optimization" (AISTATS 2016) reanalyzed the algorithm for the non-stochastic setting, framing hyperparameter tuning of iterative learning algorithms as a best-arm identification problem. They showed it found good hyperparameters roughly an order of magnitude faster than uniform allocation across configurations. Successive halving requires a manual choice of how many configurations to try versus how much budget to give each one. Li et al.'s Hyperband (2016/2018) later wrapped it in an outer loop that sweeps this tradeoff automatically.

Successive halving is a standard baseline and building block in hyperparameter-optimization libraries, and it gets applied to problems beyond its original setting. Recent continual-learning research on long-horizon memorization (arXiv:2609.06986) adapts the same discard-the-worst-half logic to rank candidate methods over an increasing number of sequential tasks, rather than increasing training iterations, calling the adaptation "task-level successive halving."