We give a simple, fast algorithm for hyperparameter optimization inspired by techniques from the analysis of Boolean functions.   We focus on the high-dimensional regime where the canonical example is training a neural network with a large number of hyperparameters. The algorithm --- an iterative application of compressed sensing techniques for orthogonal polynomials --- requires only uniform sampling of the hyperparameters and is thus easily parallelizable.
 
 Experiments for training deep neural networks on Cifar-10 show that compared to state-of-the-art tools (e.g., Hyperband and Spearmint), our algorithm finds significantly improved solutions, in some cases better than what is attainable by hand-tuning.   In terms of overall running time (i.e., time required to sample various settings of hyperparameters plus additional computation time), we are at least an order of magnitude faster than Hyperband and Bayesian Optimization.   We also outperform Random Search $8\times$.
   
Our method is inspired by provably-efficient algorithms for learning decision trees using the discrete Fourier transform.   We obtain improved sample-complexty bounds for learning decision trees while matching state-of-the-art bounds on running time (polynomial and quasipolynomial, respectively). Large scale machine learning and optimization systems usually involve a large number of free parameters for the user to fix according to their application. A timely example is the training of deep neural networks for a signal processing application: the ML specialist needs to decide on an architecture, depth of the network, choice of connectivity per layer (convolutional, fully-connected, etc.), choice of optimization algorithm and recursively choice of parameters inside the optimization library itself (learning rate, momentum, etc.).Given a set of hyperparameters and their potential assignments, the naive practice is to search through the entire grid of parameter assignments and pick the one that performed the best, a.k.a. "grid search". As the number of hyperparameters increases, the number of possible assignments increases exponentially and a grid search becomes quickly infeasible. It is thus crucial to find a method for automatic tuning of these parameters.This auto-tuning, or finding a good setting of these parameters, is now referred to as hyperparameter optimization (HPO), or simply automatic machine learning (auto-ML). For continuous hyperparameters, gradient descent is usually the method of choice BID25 BID24 BID9 . Discrete parameters , however, such as choice of architecture, number of layers, connectivity and so forth are significantly more challenging. More formally, let DISPLAYFORM0 be a function mapping hyperparameter choices to test error of our model. That is, each dimension corresponds to a certain hyperparameter (number of layers, connectivity, etc.), and for simplicity of illustration we encode the choices for each parameter as binary numbers {−1, 1}. The goal of HPO is to approximate the minimizer x * = arg min x∈{0,1} n f (x) in the following setting:1. Oracle model: evaluation of f for a given choice of hyperparameters is assumed to be very expensive. Such is the case of training a given architecture of a huge dataset.2. Parallelism is crucial: testing several model hyperparameters in parallel is entirely possible in cloud architecture, and dramatically reduces overall optimization time.3. f is structured.The third point is very important since clearly HPO is information-theoretically hard and 2 n evaluations of the function are necessary in the worst case. Different works have considered exploiting one or more of the properties above. The approach of Bayesian optimization BID32 addresses the structure of f , and assumes that a useful prior distribution over the structure of f is known in advance. Multi-armed bandit algorithms BID22 , and Random Search BID2 , exploit computational parallelism very well, but do not exploit any particular structure of f 1 . These approaches are surveyed in more detail later .
A hyperparameter tuning algorithm using discrete Fourier analysis and compressed sensing Investigates problem of optimizing hyperparameters under the assumption that the unknown function can be approximated, showing that the approximate minimization can be performed over the boolean hypercube. The paper explores hyperparameter optimization by assuming structure in the unknown function mapping hyperparameters to classification accuracy