Successive halving

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 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 2007.04074 §3.2.

The alternative the paper compares against is full budget (FB): every candidate is trained to the largest budget 2007.04074 §3.2.1. Both options are paired with a model selection strategy, such as holdout or k-fold cross-validation 2007.04074 §4. The paper's budget is a number of training iterations per pipeline 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 2007.04074 §3.2.1. The candidates come from a warm-start portfolio of 32 pipelines 2007.04074 §3.5.1. The paper uses eta = 4 for all experiments 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 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.

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 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 2007.04074 §3.2.1. The number of BO proposals before SH starts is not given 2007.04074 §3.2.1. The authors state that SH with BO has no performance guarantee 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 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 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 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 2007.04074 §4.1.1. Details of the selector are in the card Auto-Sklearn 2.0.

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 2007.04074 tab. 2.

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 2007.04074 §3.2.1. The BO variant wraps this loop: BO proposes the candidates, and only then does SH run.

# 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 2007.04074 §3.5.2. Table 2 shows FB with holdout ahead of SH with holdout at both horizons 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 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: 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.