Surrogate-Based Hyperparameter Optimization for KNN

Comparing three hyperparameter optimization strategies for K-Nearest Neighbors — Sequential Model-Based Optimization, Successive Halving, and Random Search — under fixed evaluation budgets. Because evaluating a real configuration is expensive, all three optimise against a Random Forest surrogate trained on the Learning Curve Database, so the comparison isolates search strategy from training cost.

The result runs against the obvious expectation. SMBO, the model-guided method, does not clearly beat Random Search: both drop quickly and then plateau at comparable error. Successive Halving, the least sophisticated of the three, reaches the lowest final error by spending its budget differently — screening many configurations cheaply and promoting only the survivors.

Full write-up: report.pdf

Setup

Search space — KNN hyperparameters plus the training-set size:

Parameter	Range
n_neighbors	1–50 (integer)
leaf_size	10–100 (integer)
p	1 (Manhattan) or 2 (Euclidean)
weights	uniform or distance
anchor_size	100–1600 (integer)

anchor_size is what makes multi-fidelity optimization possible: it is the training-set size, so a configuration can be evaluated cheaply at a small anchor and expensively at a large one. Successive Halving exists to exploit exactly this.

Surrogate — a Random Forest predicting KNN error (1 − accuracy) from the configuration and anchor size. Numerical features get mean imputation and standard scaling, categoricals get constant imputation and one-hot encoding. Validated on an 80/20 split, then refitted on the full data.

Methods

• Random Search — the baseline, 500 surrogate evaluations
• SMBO — Gaussian Process surrogate with a constant + RBF kernel, seeded with 10 random configurations, then Expected Improvement to pick each next point. 500 evaluations.
• Successive Halving — evaluates many configurations at low anchor sizes and keeps the top 1/η at each rung (η = 2) until one remains

Three OpenML datasets: letter recognition (ID 6), balance scale (ID 11), and Amazon commerce reviews (ID 1457).

Results

The surrogate is accurate enough to trust

Spearman correlation between predicted and true error: 0.9998 (ID 6), 0.9983 (ID 11), 0.9915 (ID 1457). Since all three optimizers search against this surrogate, this had to hold before any comparison between them meant anything.

SMBO does not beat Random Search

On dataset 6, SMBO drops to its plateau within a handful of iterations while Random Search takes around 300 to get there. So SMBO is faster early — but both settle at effectively the same error, and the gap closes well before the 500 evaluation budget is spent. Successive Halving reaches roughly 0.037 on the same dataset, below where either lands.

Dataset 1457 shows the same shape at a different scale: both methods fall to about 0.1 within the first 100 iterations and stay there, while Successive Halving continues past them to below 0.01.

Dataset 11 (plot_compare_id11.png) follows the same pattern.

Why Successive Halving wins here

The three methods are not really doing the same thing. SMBO and Random Search both evaluate full-budget configurations and differ only in how they choose the next one. Successive Halving changes what an evaluation costs — most of its configurations are killed at small anchor sizes, so it can screen far more candidates for the same total work and concentrate the remaining budget on the survivors.

That makes it the better choice when the search space is large and evaluation cost scales with a controllable fidelity parameter. Where no such parameter exists, the comparison would look different, and SMBO's early-iteration speed would matter more.

Running it

pip install -r requirements.txt

python surrogate_model_experiment.py   # trains and validates the surrogate
python optimization_experiment.py      # runs all three optimizers

Datasets and parameters are hardcoded; no arguments needed. The scripts write the plots embedded above.

config_performances_dataset-{6,11,1457}.csv hold the LCDB performance data, and lcdb_config_space_knn.json defines the search space.

Files

File	Purpose
surrogate_model.py	Random Forest surrogate for KNN error
surrogate_model_experiment.py	surrogate training and Spearman validation
smbo.py	Gaussian Process SMBO with Expected Improvement
successive_halving.py	multi-fidelity Successive Halving
random_search.py	Random Search baseline
optimization_experiment.py	runs all optimizers across the datasets
example_run_experiment.py	minimal usage example

Limitations

• Each method was run once per dataset with a fixed seed, so the comparison has no variance estimate. SMBO and Random Search plateau close enough together that repeated runs could plausibly reorder them.
• Successive Halving is compared on final error, not on equal total surrogate calls, so the "wins" claim is about quality under its own budget rather than a strictly matched-cost comparison.
• Only KNN, and only three datasets. The conclusion that multi-fidelity beats model-based search may not transfer to algorithms where anchor size affects performance differently.
• All optimization runs against the surrogate rather than real KNN training. The surrogate is accurate (ρ > 0.99), but it is still a model of the objective, not the objective.

Contributions

• Nallathambi Vethiappan
• Federico Cucinotta