---
kind: concept
slug: algorithm-selection
title: Algorithm selection
summary: >-
  Choosing which search policy or starting pipeline to run on a new dataset, using results from earlier datasets. Auto-Sklearn 2.0 picks one of eight policies per dataset with a pairwise random-forest selector on two meta-features, plus a fallback. Its gain over the single best policy is small and changes sign across settings; the selector clearly beats random choice. One paper so far.
tags: [algorithm-selection, automl, meta-learning, portfolio]
papers: ["2007.04074"]
related: [meta-learning, hyperparameter-optimization, bayesian-optimization]
status: draft
updated_at: 2026-10-31
---

## Overview

A time-limited search has to decide how to run itself before it starts: how to
estimate error, how to spend budget across candidates, and which candidates to
try first. The paper's point is that the best choice depends on the dataset and
on the time horizon, and that no single choice wins everywhere [arxiv:2007.04074
§1] [arxiv:2007.04074 §4] [arxiv:2007.04074 fig. 4]. The approach is to record
how each option performed on many earlier datasets, then map a cheap description
of a new dataset to one option [arxiv:2007.04074 §4.1]. The selection happens
once, before the run on the new training split; the test split is used only at
the end [arxiv:2007.04074 §4.1].

This page covers one paper so far, so the variants below are all from
Auto-Sklearn 2.0 [arxiv:2007.04074].

## Variants

### Fixed policy chosen on average (single best)

The simplest option is one policy for every dataset: the one that does best on
average over the meta-datasets. The paper uses this as its baseline and calls
it per-set algorithm selection [arxiv:2007.04074 §4.1.1]. Results: with the
portfolio in place it scores 3.69 at 10 minutes and 2.44 at 60 minutes, against
3.58 and 2.47 for the selector [arxiv:2007.04074 tab. 8]. Card:
[Auto-Sklearn 2.0](/papers/2007.04074).

### Per-dataset pairwise selector

The main method. The eight policies are the combinations of four ways to
estimate error (3-, 5- and 10-fold cross-validation, and holdout) with two budget
rules (successive halving or full budget) [arxiv:2007.04074 §4] [arxiv:2007.04074
§4.1]. For each pair of policies, a random forest predicts which one wins on a
dataset with the two meta-features, number of datapoints and number of features
[arxiv:2007.04074 §4.1.1]. The pairwise votes are normalised into a distribution
over the policies. The pair models are trained on the meta-datasets and weighted
by the loss difference between the two policies [arxiv:2007.04074 §4.1.1].
Seven hyperparameters of this selector are tuned by Bayesian optimization on
meta-data cross-validation error [arxiv:2007.04074 §4.1.1] [arxiv:2007.04074
tab. 4].

Reported at 10 and 60 minutes: 3.58 ± 0.23 and 2.47 ± 0.18 normalised balanced
error on 39 datasets, against 4.11 and 3.19 for PoSH Auto-sklearn and 16.21 and
7.17 for Auto-sklearn 1.0 [arxiv:2007.04074 tab. 5]. The selector was trained on
the portfolio performance table, Bayesian-optimization runs and ensembles
combined, which is the configuration behind those numbers
[arxiv:2007.04074 tab. 6].

### Backup for datasets outside the meta-data

When no meta-dataset has at least as many datapoints and at least as many
features as the new dataset, the selector is not trusted. The paper falls back
to holdout with successive halving, which it describes as the cheapest and most
aggressive policy [arxiv:2007.04074 §4.1.1]. Without this fallback the selector
is much worse: 4.79 instead of 3.58 at 10 minutes and 5.43 instead of 2.47 at 60
minutes, with ensembles in the meta-data [arxiv:2007.04074 tab. 6]. The authors
say the two-feature selector can be read as learning the manual fallbacks from
their first part [arxiv:2007.04074 §4.1.1].

### Warm-start portfolio of starting pipelines

A separate mechanism that also chooses options, this time which pipelines to
try first. A greedy algorithm picks 32 candidates from a performance table
built on the meta-datasets, and the online search runs these first, then
switches to Bayesian optimization [arxiv:2007.04074 §3.1] [arxiv:2007.04074
§3.2.1] [arxiv:2007.04074 alg. 1]. In every setting of the portfolio table,
starting from the portfolio beats starting from Bayesian optimization or the
earlier k-nearest-dataset warm start [arxiv:2007.04074 tab. 2]. Without the
portfolio the selector scores 5.63 at 10 minutes and 3.42 at 60 minutes, against
3.58 and 2.47 with it [arxiv:2007.04074 tab. 8].

### Reference points: random and oracle

Random picks a policy at random. The oracle picks the best policy for each test
dataset and is not achievable in practice. They bracket the selector: 8.32 and
6.18 for random, and 2.33 and 1.22 for the oracle, at 10 and 60 minutes
[arxiv:2007.04074 tab. 6]. The gap to the oracle is large, so the selector
leaves room to improve.

## When to use which

The paper's setting is 208 meta-training datasets and 39 test datasets
[arxiv:2007.04074 §3.4.1]. Its results support the following reading.

| Situation | Use | Why |
|---|---|---|
| You have no collection of past results to learn from | A single fixed policy, chosen on your own benchmark | At 10 and 60 minutes the single best policy is within about 0.1 of the selector in the authors' ablation [arxiv:2007.04074 tab. 6] |
| You have past results on many datasets and want the best reported result | Pairwise selector with the portfolio and the fallback | Lowest reported error among the systems compared, at both horizons [arxiv:2007.04074 tab. 5] |
| New datasets may be larger than any past dataset | Keep the fallback rule | Without it the selector degrades sharply on large datasets [arxiv:2007.04074 tab. 6] [arxiv:2007.04074 §4.3.1] |
| Short horizon (about 10 minutes) | Warm-start portfolio, whatever selector is used | Removing it raises the selector's error from 3.58 to 5.63 [arxiv:2007.04074 tab. 8] |
| Only a few options are on the table | Check a restricted set before adding more | Restricting to full-budget policies gave 3.50 against 3.58 at 10 minutes, within one standard deviation [arxiv:2007.04074 tab. 7] |

The selector does not win in every setting. Without the portfolio, the single
best policy beats it at 10 minutes (5.37 against 5.63), while the selector wins
at 60 minutes (3.42 against 3.61) [arxiv:2007.04074 tab. 8]. With the portfolio
the order flips at 60 minutes (2.44 against 2.47). Differences of this size
are close to the standard deviations the paper reports, so the choice between a
selector and a single policy should be checked on your own data.

The paper also reports that building the selector's training data is expensive,
and that the cheap portfolio-only table gives the weakest selector variant at 60
minutes [arxiv:2007.04074 §4.3.1] [arxiv:2007.04074 tab. 6].

Among the Auto-Sklearn system comparisons, the authors report the lowest mean
rank and the most best-on-dataset results across 39 datasets, with a sign test
against H2O AutoML of p = .053, which is not significant at 0.05
[arxiv:2007.04074 tab. 9]. These are author-reported results and have not been
reproduced here.

## Implementation sketch

The core of the selector is a pairwise vote over policies, guarded by the
fallback. Variants differ in the meta-features, the pair model and the
fallback; the paper's choices are noted in the comments.

```pseudocode
# Pick a search policy for a new dataset  [arxiv:2007.04074 §4.1.1]
# Input:  n_rows, n_cols of the new dataset; pair models; meta-datasets
# Output: one weight per policy, summing to 1

def choose_policy(n_rows, n_cols, meta_data, pair_models):
    # Backup if no meta-dataset is at least this large  [§4.1.1]
    covered = any(m.rows >= n_rows and m.cols >= n_cols
                  for m in meta_data)
    if not covered:
        return backup_policy  # holdout with successive halving  [§4.1.1]
    wins = zeros(num_policies)
    # Each pair model predicts that policy a beats policy b  [§4.1.1]
    for a, b in policy_pairs:
        # Soft voting: use the probability (hard voting is also tuned)  [tab. 4]
        p_a = pair_models[a, b].predict_proba([n_rows, n_cols])
        wins[a] += p_a
        wins[b] += 1 - p_a
    # Normalise the win counts into a distribution  [§4.1.1]
    return wins / wins.sum()
```

The released experiment scripts differ from the text in places, for example in
how the backup is applied. The
[paper card](/papers/2007.04074) lists these differences. Check them before you
copy the rule.

## Contradictions

- **Selection of the portfolio.** The greedy construction and its guarantees use
  test-split losses, but the paper's equation for the same quantity is written
  on validation losses [arxiv:2007.04074 eq. 9] [arxiv:2007.04074 §3.1.1]
  [arxiv:2007.04074 §3.1.2]. The authors say test losses are acceptable when the
  new datasets are kept separate, and they show that choosing on validation
  breaks the guarantees [arxiv:2007.04074 app. C.3] [arxiv:2007.04074 app. C.4].
  Implementing the written equation literally therefore changes the result.

## Papers

- [Auto-Sklearn 2.0: Hands-free AutoML via Meta-Learning](/papers/2007.04074):
  a per-dataset selector over eight policies, a warm-start portfolio and
  successive halving, evaluated on 39 AutoML benchmark datasets.