Abstract
Driven by the need for parallelizable hyperparameter optimization methods, this paper studies open loop search methods: sequences that are predetermined and can be generated before a single configuration is evaluated. Examples include grid search, uniform random search, low discrepancy sequences, and other sampling distributions. In particular, we propose the use of $k$-determinantal point processes in hyperparameter optimization via random search. Compared to conventional uniform random search where hyperparameter settings are sampled independently, a $k$-DPP promotes diversity. We describe an approach that transforms hyperparameter search spaces for efficient use with a $k$-DPP. In addition, we introduce a novel Metropolis-Hastings algorithm which can sample from $k$-DPPs defined over any space from which uniform samples can be drawn, including spaces with a mixture of discrete and continuous dimensions or tree structure. Our experiments show significant benefits in realistic scenarios with a limited budget for training supervised learners, whether in serial or parallel.
Introduction
Hyperparameter optimization (HPO) is often the bottleneck in developing effective machine learning models. Traditionally, this is approached via closed-loop sequential methods like Bayesian Optimization (BO), which use past results to inform future trials. While efficient, these are difficult to parallelize. Conversely, open-loop methods like Grid Search or Random Search are "embarrassingly parallel" but often inefficient, leading to redundant sampling or poor coverage of the search space.
As training deep learning models becomes more resource-intensive, there is a growing need for "smarter" open-loop methods that can leverage massive parallelism without sacrificing the efficiency of sequential search. This paper proposes using $k$-determinantal point processes ($k$-DPPs) to bridge this gap.
Methodology: Diversifying Search with $k$-DPPs
The core innovation is the application of $k$-DPPs to select hyperparameter configurations. Unlike standard random search, where configurations are sampled independently, a $k$-DPP explicitly promotes diversity. The probability of selecting a set of points is proportional to the determinant of a similarity matrix; essentially, the process "repels" similar points, ensuring a more even coverage of the search space.
Technical Contributions
- MCMC Sampling for Mixed Spaces: The authors introduce a novel Metropolis-Hastings algorithm that allows $k$-DPP sampling across continuous, discrete, and tree-structured spaces.
- Feature Encoding: A framework is provided to transform diverse hyperparameter types into a unified feature space for effective similarity calculation.
- Dispersion vs. Discrepancy: The paper argues that dispersion (the size of the largest "hole" in search coverage) is a more relevant metric for optimization than the standard "discrepancy" used in integration.
Experimental Results
The method was evaluated on synthetic benchmarks and a real-world NLP task: tuning a Convolutional Neural Network (CNN) for sentiment analysis on the Stanford Sentiment Treebank (SST).
Accuracy and Efficiency
The $k$-DPP approach consistently outperformed uniform random search and rivaled sophisticated sequential methods. In "hard" search spaces—where the optimal region is small—$k$-DPP even outperformed BO-TPE, likely because it avoids the local optima that can trap sequential optimizers early on.
Furthermore, the wall-clock time efficiency is significant. While a sequential optimizer like Spearmint might take hours to generate points one by one, $k$-DPP generates the entire batch in seconds, enabling immediate parallel execution.
Conclusion and Future Work
$k$-DPPs offer a powerful tool for parallel hyperparameter optimization by formalizing the intuition that diversity is a proxy for intelligence in open-loop settings. Future work includes developing "hybrid" approaches that incorporate performance feedback to update quality scores within the DPP framework and automating the selection of kernel parameters like the RBF length-scale.
Summary updated