---
kind: concept
slug: successive-halving
title: Successive halving
summary: >-
  Budget allocation that starts many candidates on a small budget, keeps the best 1/eta each round and multiplies the survivors' budget by eta. Covers its use in Auto-sklearn 2.0, its pairing with Bayesian optimization, and when it did or did not beat full-budget training. Author-reported, one paper.
tags: [budget-allocation, automl, early-stopping, hyperparameter-optimization]
papers: ["2007.04074"]
related: [automated-machine-learning, algorithm-selection, hyperparameter-optimization, bayesian-optimization, meta-learning]
status: draft
updated_at: 2026-10-31
---

## Overview

Successive halving (SH) is a rule for spending a training budget over many
candidate pipelines. Every candidate starts at the smallest budget. The best
`1/eta` of them survive, their budget is multiplied by `eta`, and the loop
repeats until one candidate is left or the largest budget is spent
[arxiv:2007.04074 §3.2.1]. The point is to stop spending full budget on
candidates that look weak early. The paper calls SH a bandit strategy and
cites earlier work for it [arxiv:2007.04074 §3.2].

The alternative the paper compares against is full budget (FB): every
candidate is trained to the largest budget [arxiv:2007.04074 §3.2.1]. Both
options are paired with a model selection strategy, such as holdout or k-fold
cross-validation [arxiv:2007.04074 §4]. The paper's budget is a number of
training iterations per pipeline [arxiv:2007.04074 app. D.3].

Only one paper card uses this slug, so everything below comes from that
paper. Its results are author-reported on 39 AutoML benchmark datasets.

## Variants

### Successive halving that replaces full-budget holdout (Auto-sklearn 2.0)

In this paper SH replaces the standard holdout procedure, in which every
pipeline is trained for the full budget [arxiv:2007.04074 §3.2.1]. The
candidates come from a warm-start portfolio of 32 pipelines
[arxiv:2007.04074 §3.5.1]. The paper uses `eta = 4` for all
experiments [arxiv:2007.04074 app. D.3]. Budgets are 32 to 512 iterations for
tree models and 64 to 1024 iterations for SGD and the passive-aggressive
model [arxiv:2007.04074 app. D.3]. The paper does not state how many pipelines
start in the first round. The released experiment code fixes 16, which
gives brackets of 16, 4 and 1 pipelines; see the card's Paper vs code section
[Auto-Sklearn 2.0](/papers/2007.04074).

### Successive halving with Bayesian optimization proposals

The paper combines SH with Bayesian optimization (BO), following Falkner et
al. BO proposes pipelines, and each one is evaluated at the lowest budget
until a fixed number of them has been evaluated. Then SH runs as above
[arxiv:2007.04074 §3.2.1]. The surrogate is fitted on the highest budget that
has enough data points. The paper defines "enough" as `n/2`, where `n` is the
number of hyperparameters, instead of the `n+1` that the original method
needs [arxiv:2007.04074 §3.2.1]. The number of BO proposals before SH starts
is not given [arxiv:2007.04074 §3.2.1]. The authors state that SH with BO has
no performance guarantee [arxiv:2007.04074 §7].

Falkner et al. proposed Hyperband together with BO. The paper uses only SH,
because it expects SH to work better when time is very short, since SH cuts
the budget per pipeline more aggressively [arxiv:2007.04074 §3.2.1, footnote].

### Successive halving as one policy among eight

Part II of the paper treats SH as one of two budget allocation strategies,
crossed with four model selection strategies: 3-fold, 5-fold and 10-fold
cross-validation, and holdout [arxiv:2007.04074 §4]. A learned selector picks
one of these eight policies for each dataset from two meta-features: the
number of datapoints and the number of features [arxiv:2007.04074 §4.1.1].
When no meta-dataset is at least as large on both features, the selector
falls back to holdout with SH [arxiv:2007.04074 §4.1.1]. Details of the
selector are in the card [Auto-Sklearn 2.0](/papers/2007.04074).

## When to use which

The paper's results do not favour SH on every setting. The table uses the
paper's own numbers, which are normalized balanced error, lower is better
[arxiv:2007.04074 tab. 2].

| Situation | Use | Why |
|---|---|---|
| Very short time limit, many candidates, each costly to train | SH with a small starting budget | The paper expects SH to be better here, since it cuts budget aggressively [arxiv:2007.04074 §3.2.1, footnote]. Its own holdout result contradicts this at 10 minutes (see Contradictions). |
| Large datasets, where a small budget already gives a usable error estimate | SH | The paper expects SH to work best here [arxiv:2007.04074 §3.2.1]. This page has no per-dataset breakdown to test it. |
| Small or slow-converging models, where early error does not predict final error | FB | SH can cut candidates that would do best with more budget [arxiv:2007.04074 §3.2.1]. |
| Holdout, portfolio warm start, 10 or 60 minutes | Measure both on your data | With the portfolio, FB with holdout beat SH with holdout at both horizons: 3.70 vs 4.11 at 10 min and 3.08 vs 3.19 at 60 min [arxiv:2007.04074 tab. 2]. |
| Cross-validation, portfolio warm start | Measure both on your data | Results switch by horizon. With 3-fold and 5-fold CV SH is better at 10 min (6.16 vs 6.90; 7.05 vs 7.93), and FB is better at 60 min (4.96 vs 5.17; 5.05 vs 5.40). 10-fold CV reverses the pattern [arxiv:2007.04074 tab. 2]. |
| You need a guarantee on the search itself | Not available for SH with BO | The authors state no guarantee for SH with BO [arxiv:2007.04074 §7]. |
| You cannot pick the budget scheme by hand | Per-dataset selector over both schemes | The selector and the single best policy are close: 3.58 vs 3.69 at 10 min and 2.47 vs 2.44 at 60 min. The gaps are within the reported standard deviations [arxiv:2007.04074 tab. 8]. |

Within the selector results, the subsets that offer only SH or only FB
differ by less than one standard deviation at both horizons: at 10 min 3.63
(SH) against 3.50 (FB), and at 60 min 2.44 against 2.39 [arxiv:2007.04074
tab. 7].

## Implementation sketch

The loop below follows the paper's description of SH. The paper does not
say how to round `len(survivors) / eta` when it is not an integer
[arxiv:2007.04074 §3.2.1]. The BO variant wraps this loop: BO proposes the
candidates, and only then does SH run.

```pseudocode
# Successive halving over candidate pipelines  [arxiv:2007.04074 §3.2.1]
# Input:  candidates, smallest budget b_min, largest budget b_max, factor eta
# Output: one or more surviving pipelines

def successive_halving(candidates, b_min, b_max, eta):
    # Every candidate starts at the smallest budget  [§3.2.1]
    budget = b_min
    survivors = candidates
    while True:
        # Train and score each survivor at the current budget  [§3.2.1]
        errors = [train_and_score(p, budget) for p in survivors]
        # Stop when one is left or the largest budget is reached  [§3.2.1]
        if len(survivors) == 1 or budget >= b_max:
            return survivors
        # Keep the best 1/eta; rounding is not stated  [§3.2.1]
        survivors = keep_best(survivors, errors, len(survivors) / eta)
        # Survivors get eta times the budget  [§3.2.1]
        budget = budget * eta
```

## Contradictions

Within the one paper, the authors' reading and their tables disagree.

- The text says that, with the portfolio, the average results are
  "inconclusive" about whether SH was the right choice over plain holdout
  [arxiv:2007.04074 §3.5.2]. Table 2 shows FB with holdout ahead of SH with
  holdout at both horizons [arxiv:2007.04074 tab. 2]. Both are the paper's
  statements; this page does not resolve them.
- The paper's expectation that SH works best on large datasets
  [arxiv:2007.04074 §3.2.1] is stated as expectation. The summary tables
  here are averages over datasets, so they do not test it directly.

Across papers: none known, since only one card uses this slug.

## Papers

- [Auto-Sklearn 2.0: Hands-free AutoML via Meta-Learning](/papers/2007.04074): uses SH as a budget allocation strategy in an AutoML system, with a portfolio warm start and a per-dataset policy selector. Author-reported results on 39 datasets.