Weighted Sampling for Combined Model Selection and Hyperparameter Tuning

Dimitrios Sarigiannis, Thomas P. Parnell, Haralampos Pozidis

Abstract

The combined algorithm selection and hyperparameter tuning (CASH) problem is characterized by large hierarchical hyperparameter spaces. Model-free hyperparameter tuning methods can explore such large spaces efficiently since they are highly parallelizable. When no prior knowledge exists, these methods commonly sample random configurations following a uniform distribution. In this work, we propose a novel sampling distribution as an alternative to uniform sampling and prove theoretically that it has a better chance of finding the best configuration in a worst-case setting. We evaluate three popular model-free solutions—Random Search, Successive Halving, and Hyperband—with both uniform and the proposed weighted sampling scheme across 67 datasets from OpenML. We verify empirically that the proposed sampling distribution improves performance in all cases and provide a rigorous statistical framework for comparing these AutoML methods.

The CASH Problem and Hierarchical Search Spaces

Automated Machine Learning (AutoML) aims to automate the end-to-end process of applying machine learning to real-world problems. A central challenge is the CASH problem: simultaneously selecting the best algorithm and its optimal hyperparameters.

The search space for CASH is inherently hierarchical. Choosing a specific model (e.g., Logistic Regression) opens up a sub-space of hyperparameters specific to that model (e.g., regularization type, penalty). This structure is illustrated in Figure 1.

The hierarchical search space of the CASH problem, showing different models and their associated hyperparameters.

Traditional model-free methods like Random Search or Hyperband typically use uniform sampling, where each model is chosen with equal probability. However, this ignores the "complexity tax": complex models with many hyperparameters have a much larger search volume than simpler ones. A uniform sampler is statistically less likely to find a near-optimal configuration for a high-dimensional model than for a low-dimensional one.

A Weighted Sampling Approach

To address this imbalance, we propose a weighted sampling distribution that prioritizes models based on their hyperparameter count. Specifically, we define the probability $p_\lambda$ of sampling model $\lambda$ as: $$p_\lambda \propto 2^{N_\lambda}$$ where $N_\lambda$ is the number of hyperparameters for model $\lambda$. This heuristic assumes that as the number of hyperparameters increases linearly, the budget required to explore the space effectively increases exponentially.

We provide a theoretical proof demonstrating that in a worst-case scenario—where the optimal configuration is distributed uniformly across the entire space—this weighted scheme strictly reduces the probability of failing to find the best configuration compared to uniform sampling.

Experimental Setup and Statistical Rigor

We evaluated the proposed sampling scheme across 67 binary classification datasets from the OpenML platform. Our model pool included 11 classifiers, ranging from simple Naive Bayes to complex ensemble methods like XGBoost and Random Forest.

A significant contribution of this work is the standardization of statistical evaluation in AutoML. We observed a lack of consensus in the literature regarding how to compare different frameworks. We propose a pipeline consisting of:

  1. Omnibus Friedman test to detect any overall differences between methods.
  2. Pairwise Wilcoxon signed-rank tests for direct comparisons.
  3. Finner correction to adjust p-values for multiple hypothesis testing.

Key Results and Discussion

Our empirical results consistently show that weighted sampling improves the performance of all three baseline algorithms: Random Search (RS), Successive Halving (SH), and Hyperband.

Critical Difference (CD) diagram comparing Random Search (RS), Successive Halving (SH), and Hyperband with uniform and weighted (.W) sampling. Lower rank is better.

As shown in Figure 4, methods using weighted sampling (denoted with .W) consistently achieve better average ranks. Notably, HYPERBAND.W and SH.W emerge as the top-performing methods. The statistical testing confirms that these improvements are significant ($p < 0.05$) in most pairwise comparisons.

We also investigated the trade-off between exploration and exploitation. In Successive Halving, more "explorative" schedules (starting with many configurations on small data subsets) generally outperformed more "exploitative" ones. Weighted sampling was found to be particularly effective at boosting Hyperband's performance by equalizing the effectiveness of its different brackets.

Conclusion

Weighted sampling offers a simple yet powerful heuristic for improving model-free AutoML. By accounting for the complexity of the hyperparameter space, it ensures that high-potential, complex models receive the exploration budget they require. Combined with a rigorous statistical evaluation framework, this approach provides a more robust foundation for automated machine learning in practice.

Summary updated

Abstract

The combined algorithm selection and hyperparameter tuning (CASH) problem is characterized by large hierarchical hyperparameter spaces. Model-free hyperparameter tuning methods can explore such large spaces efficiently since they are highly parallelizable across multiple machines. When no prior knowledge or meta-data exists to boost their performance, these methods commonly sample random configurations following a uniform distribution. In this work, we propose a novel sampling distribution as an alternative to uniform sampling and prove theoretically that it has a better chance of finding the best configuration in a worst-case setting. In order to compare competing methods rigorously in an experimental setting, one must perform statistical hypothesis testing. We show that there is little-to-no agreement in the automated machine learning literature regarding which methods should be used. We contrast this disparity with the methods recommended by the broader statistics literature, and identify a suitable approach. We then select three popular model-free solutions to CASH and evaluate their performance, with uniform sampling as well as the proposed sampling scheme, across 67 datasets from the OpenML platform. We investigate the trade-off between exploration and exploitation across the three algorithms, and verify empirically that the proposed sampling distribution improves performance in all cases.
BibTeX
@inproceedings{sarigiannis2020weighted,
  author = {Dimitrios Sarigiannis and Thomas P. Parnell and Haralampos Pozidis},
  title = {{Weighted Sampling for Combined Model Selection and Hyperparameter Tuning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=sT9sj64MAwL},
}
Figure