Weighted Sampling for Combined Model Selection and Hyperparameter Tuning

Dimitrios Sarigiannis, Thomas P. Parnell, Haris Pozidis

TL;DR

This paper tackles the challenge of efficiently searching vast hyperparameter spaces in automated machine learning (AutoML). They introduce a novel "weighted sampling" strategy that theoretically outperforms uniform random sampling for finding optimal model configurations, and empirically demonstrate its benefits across various AutoML algorithms and datasets.

What Problem Does This Paper Address?

Building effective machine learning models often involves two complex, intertwined tasks: selecting the right algorithm (e.g., Random Forest vs. XGBoost) and then tuning its numerous hyperparameters. This combined problem, known as Combined Algorithm Selection and Hyperparameter Tuning (CASH), is notoriously difficult due to the enormous, hierarchical search spaces involved. Many popular AutoML methods, particularly "model-free" ones, rely on randomly sampling configurations. However, when these methods lack prior knowledge or meta-data, they typically resort to a uniform sampling distribution. This paper argues that this uniform approach is suboptimal and proposes a more intelligent sampling strategy to improve the efficiency and effectiveness of these AutoML systems. A secondary problem addressed is the lack of standardized statistical methods for comparing AutoML algorithms in the literature, leading to inconsistent and potentially unreliable conclusions.

Methods

The core contribution of this paper is a weighted sampling distribution for model-free CASH optimization. Instead of sampling models and their hyperparameters uniformly, their proposed distribution favors models with fewer hyperparameters. The intuition is that models with more hyperparameters require exponentially more effort to tune effectively, so a uniform approach is less likely to find their optimal configurations. They provide a theoretical proof showing that this weighted sampling scheme offers a better chance of finding the optimal configuration in a worst-case scenario compared to uniform sampling.

Beyond the sampling strategy, the paper also addresses the crucial aspect of rigorous statistical comparison of AutoML methods. They review existing practices in the literature, highlight their shortcomings, and propose a systematic approach based on established statistical methods (Wilcoxon signed-rank tests, Friedman tests, and Finner correction) for comparing multiple algorithms across a collection of datasets.

The paper then evaluates three popular model-free CASH algorithms: Random Search (RS), Successive Halving (SH), and Hyperband. These algorithms are tested with both their proposed weighted sampling and the standard uniform sampling.

Datasets

The authors evaluated their methods on 67 datasets obtained from the OpenML platform. These datasets are described as binary classification problems. The paper provides a list of the specific OpenML IDs used in Appendix A and details the preprocessing steps in Appendix B. No new benchmark datasets were introduced.

Key Insights and Ideas

  • The curse of dimensionality in hyperparameter spaces: Models with more hyperparameters are inherently harder to optimize. A uniform sampling strategy doesn't account for this, leading to wasted effort on complex models that are unlikely to be optimal.
  • Weighted sampling as a theoretical advantage: The proposed weighted sampling distribution, which favors models with fewer hyperparameters, is theoretically proven to outperform uniform sampling in worst-case scenarios for CASH.
  • The importance of statistical rigor: The paper highlights a significant lack of standardized statistical methods for comparing AutoML algorithms, leading to unreliable conclusions. Their proposed framework provides a more robust way to assess performance.
  • Exploration vs. Exploitation in AutoML: The study investigates the trade-off between exploring many configurations with limited resources (explorative) and focusing on fewer configurations with full resources (exploitative). They find that more explorative schedules (like SH2) tend to perform better.
  • Synergy between weighted sampling and Hyperband: While weighted sampling improves all tested algorithms, it particularly boosts the performance of Hyperband. This is because weighted sampling helps Hyperband's brackets to produce more balanced winning configurations, making its automated exploration-exploitation strategy more effective.

Key Results

  • The proposed weighted sampling distribution consistently improves the performance of Random Search, Successive Halving, and Hyperband across all tested datasets, both in terms of validation and generalization loss.
  • More explorative Successive Halving schedules (e.g., SH2) generally outperform more exploitative ones (e.g., SH0).
  • When using weighted sampling, Hyperband performs comparably to or better than the most explorative Successive Halving schedule (SH2), demonstrating its ability to effectively automate the exploration-exploitation trade-off.
  • Statistical analysis using the proposed framework confirmed significant differences in performance between the tested schemes across the 67 datasets.

Limitations and Future Work

  • Approximation in weighted sampling: The paper notes that their proposed weighted sampling distribution (equation 5) is an approximation that doesn't explicitly account for the actual ranges of hyperparameters. While they show it works well in practice, future work could explore more sophisticated distributions that incorporate this information.
  • Worst-case scenario focus: The theoretical proof is based on a worst-case scenario. While empirically validated, further investigation into performance under different assumptions or in average-case scenarios could be beneficial.
  • Limited model pool: The experiments used a pool of 11 models. Evaluating the proposed sampling strategy with a larger and more diverse set of models could provide broader insights.
  • Future work: The authors suggest exploring more efficient parallel and distributed implementations of Successive Halving and Hyperband, and investigating how their weighted sampling approach can be integrated with other advanced AutoML techniques.

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 Haris 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