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. Hyperparameter values-regularization strength, model family choices like depth of a neural network or which nonlinear functions to use, procedural elements like dropout rates, stochastic gradient descent step sizes, and data preprocessing choices-can make the difference between a successful application of machine learning and a wasted effort. To search among many hyperparameter values requires repeated execution of often-expensive learning algorithms, creating a major obstacle for practitioners and researchers alike.In general, on iteration (evaluation) k, a hyperparameter searcher suggests a d-dimensional hyperparameter configuration x k ∈ X (e.g., X = R d but could also include discrete dimensions), a worker trains a model using x k , and returns a validation loss of y k ∈ R computed on a hold out set. In this work we say a hyperparameter searcher is open loop if x k depends only on {x i } k−1 i=1 ; examples include choosing x k uniformly at random BID3 , or x k coming from a low-discrepancy sequence (c.f., BID13 ). We say a searcher is closed loop if x k depends on both the past configurations and validation losses {(x i , y i )} k−1 i=1 ; examples include Bayesian optimization BID23 and reinforcement learning methods BID30 . Note that open loop methods can draw an infinite sequence of configurations before training a single model, whereas closed loop methods rely on validation loss feedback in order to make suggestions.While sophisticated closed loop selection methods have been shown to empirically identify good hyperparameter configurations faster (i.e., with fewer iterations) than open loop methods like random search, two trends have rekindled interest in embarrassingly parallel open loop methods: 1) modern deep learning model are taking longer to train, sometimes up to days or weeks, and 2) the rise of cloud resources available to anyone that charge not by the number of machines, but by the number of CPU-hours used so that 10 machines for 100 hours costs the same as 1000 machines for 1 hour. This paper explores the landscape of open loop methods, identifying tradeoffs that are rarely considered, if at all acknowledged. While random search is arguably the most popular open loop method and chooses each x k independently of {x i } k−1 i=1 , it is by no means the only choice. In many ways uniform random search is the least interesting of the methods we will discuss because we will advocate for methods where x k depends on {x i } k−1 i=1 to promote diversity. In particular, we will focus on k i=1 from a k-determinantal point process (DPP) BID18 . We introduce a sampling algorithm which allows DPPs to support real, integer, and categorical dimensions, any of which may have a tree structure, and we describe connections between DPPs and Gaussian processes (GPs).In synthetic experiments, we find our diversity-promoting open-loop method outperforms other open loop methods. In practical hyperparameter optimization experiments, we find that it significantly outperforms other approaches in cases where the hyperparameter values have a large effect on performance. Finally , we compare against a closed loop Bayesian optimization method, and find that sequential Bayesian optimization takes, on average, more than ten times as long to find a good result, for a gain of only 0.15 percent accuracy on a particular hyperparameter optimization task.Open source implementations of both our hyperparameter optimization algorithm (as an extension to the hyperopt package BID4 ) and the MCMC algorithm introduced in Algorithm 2 are available. 1 2 RELATED WORK While this work focuses on open loop methods, the vast majority of recent work on hyperparameter tuning has been on closed loop methods, which we briefly review. We have explored open loop hyperparameter optimization built on sampling from a k-DPP. We described how to define a k-DPP over hyperparameter search spaces, and showed that k-DPPs retain the attractive parallelization capabilities of random search. In synthetic experiments, we showed k-DPP samples perform well on a number of important metrics, even for large values of k. In hyperprameter optimization experiments, we see k-DPP-RBF outperform other open loop methods. Additionally, we see that sequential methods, even when using more than ten times as much wall clock time, gain less than 0.16 percent accuracy on a particular hyperparameter optimization problem. An open-source implementation of our method is available. A STAR DISCREPANCY DISPLAYFORM0 It is well-known that a sequence chosen uniformly at random from [0, 1] d has an expected star discrepancy of at least 1 k (and is no greater than DISPLAYFORM1 ) BID22 whereas sequences are known to exist with star discrepancy less than BID24 , where both bounds depend on absolute constants. DISPLAYFORM2 Comparing the star discrepancy of sampling uniformly and Sobol, the bounds suggest that as d grows large relative to k, Sobol starts to suffer. Indeed, BID2 notes that the Sobol rate is not even valid until k = Ω(2 d ) which motivates them to study a formulation of a DPP that has a star discrepancy between Sobol and random and holds for all k, small and large. They primarily approached this problem from a theoretical perspective, and didn't include experimental results. Their work, in part, motivates us to look at DPPs as a solution for hyperparameter optimization.B KOKSMA-HLAWKA INEQUALITY Let B be the d-dimensional unit cube, and let f have bounded Hardy and Krause variation V ar HK (f ) on B. Let x = (x 1 , x 2 , . . . , x k ) be a set of points in B at which the function f will be evaluated to approximate an integral. The Koksma-Hlawka inequality bounds the numerical integration error by the product of the star discrepancy and the variation: DISPLAYFORM3 We can see that for a given f , finding x with low star discrepancy can improve numerical integration approximations.
We address fully parallel hyperparameter optimization with Determinantal Point Processes. 
{"src": "scitldr-AIC_train", "paper_id": "SJf_XhCqKm"}