Random Search for Hyperparameters using Determinantal Point Processes

Jesse Dodge, Catrìona Anderson, Noah A. Smith

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: The HPO Dilemma

Hyperparameter optimization (HPO) is critical for the success of machine learning models, yet it often presents a trade-off between efficiency and parallelizability.

  1. Closed Loop (Sequential): Methods like Bayesian Optimization (BO) use past results to inform the next sample. While sample-efficient, they are difficult to parallelize because each step depends on the completion of previous evaluations.
  2. Open Loop (Parallel): Methods like Grid Search or Uniform Random Search pick all configurations in advance. These are "embarrassingly parallel," allowing thousands of models to run simultaneously. However, uniform random search often "clumps" points together, wasting resources on redundant configurations.

This paper bridges the gap by introducing an open-loop method that is as parallelizable as random search but as efficient at covering the search space as sequential methods.

Methodology: Diversity through k-DPPs

The core innovation is the application of $k$-Determinantal Point Processes ($k$-DPPs) for sampling. Unlike uniform random search, where each point is chosen independently, a $k$-DPP selects a set of $k$ points that are "repelled" by one another. If two hyperparameter configurations are very similar, the $k$-DPP is unlikely to pick both, thus explicitly promoting diversity.

To handle the complexities of real-world HPO, the authors introduced:

  • Similarity Kernels: An RBF kernel defines "similarity" across continuous, categorical, and ordinal hyperparameters.
  • A New MCMC Algorithm: A novel Metropolis-Hastings algorithm allows sampling from complex search spaces, including those with hierarchical "tree structures" (e.g., tuning a parameter only if a specific flag is enabled).

Spatial Coverage and Dispersion

A key metric for HPO is dispersion—the size of the largest "hole" in the search space coverage. While low-discrepancy sequences like Sobol are popular, they often suffer from "plateaus" where adding more points fails to improve coverage for several iterations. $k$-DPPs provide a smoother, more consistent improvement in coverage.

Dispersion comparison for d=1 and d=2

As shown in the synthetic benchmarks above, $k$-DPP samples consistently achieve lower average dispersion and lower variance compared to both uniform random sampling and Sobol sequences in 1D and 2D spaces.

Empirical Results: Accuracy and Efficiency

The authors evaluated the method on the Stanford Sentiment Treebank (SST) task using a Convolutional Neural Network (CNN). The $k$-DPP approach was compared against uniform random search and the popular Tree-structured Parzen Estimator (TPE).

Performance on SST task across learning rate difficulties

In the "Hard" learning rate scenario, $k$-DPP significantly outperformed both TPE and Uniform search, finding better models in fewer iterations. Notably, when compared to Spearmint (a Bayesian Optimization package), the $k$-DPP method reached a high-quality result ten times faster in terms of wall-clock time due to its ability to run all trials in parallel.

Insights and Limitations

  • Biasing the Corners: $k$-DPPs tend to push samples toward the edges of the search hypercube. This is often beneficial, as practitioners frequently set search bounds too conservatively, and optimal settings are often found at the boundaries.
  • Kernel Sensitivity: The performance depends on the kernel's length-scale ($\sigma$). If $\sigma$ is too small, the method reverts to random search; if too large, it pushes points too aggressively to the corners.
  • Future Work: The authors suggest a "hybrid" loop where the quality of points is updated based on early results, combining the diversity of $k$-DPPs with the adaptive nature of sequential optimization.

Conclusion

By replacing independent sampling with $k$-DPPs, researchers can significantly improve the efficiency of parallel hyperparameter search. This method provides the coverage benefits of sophisticated sequential algorithms while remaining fully compatible with modern, massively parallel cloud computing environments.

Summary updated

Abstract

Driven by the need for parallelizable hyperparameter optimization methods, this paper studies \emph{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.
BibTeX
@misc{dodge2017random,
  author = {Jesse Dodge and Catrìona Anderson and Noah A. Smith},
  title = {{Random Search for Hyperparameters using Determinantal Point Processes}},
  year = {2017},
  eprint = {1706.01566},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1706.01566},
}
Figure