How to speed up hyperparameter optimization?

Question

For my application, I am classifying sensor signals. I wrote a 'Rapid Prototyping' script to quickly build machine learning models and return their cross validation performance.

My pipeline is the following: feature computation, feature selection, training a model, compute cross-validation score.

So far the tunable hyperparameters include: parameters for the classifier, parameters for the feature selection algorithm (how many features to keep and k for kNN in relief algorithm), and a window length (from which the feature vector is computed).

In total I have 8 hyperparameters maximum, so the the maximum number of parameter combinations is bounded by $B^8$.
($B$ is maximum number of possible parameters for a hyperparameter type).

The major problem is, it takes 15 minuntes to build a model. Even for small $B$, it is way to slow.
Is there some way to speed up this process ?

Answer 1

Here are some general techniques to speed up hyperparameter optimization.

If you have a large dataset, use a simple validation set instead of cross validation. This will increase the speed by a factor of ~k, compared to k-fold cross validation. This won't work well if you don't have enough data.

Parallelize the problem across multiple machines. Each machine can fit models with different choices of hyperparameters. This will increase the speed by a factor of ~m for m machines.

Avoid redundant computations. Pre-compute or cache the results of computations that can be reused for subsequent model fits (or iteratively updated with less work than computing from scratch). A couple simple examples: if the model needs a pairwise distance matrix, compute all distances at the beginning, rather than re-computing them each time a model is fit. If the model needs a mean and covariance matrix, iteratively update them depending on the points in each training set, rather than computing from scratch.

If using grid search, decrease the number of hyperparameter values you're willing to consider (i.e. use a coarser grid). This can give potentially large speedups because the total number of combinations scales multiplicatively. The risk is that, if the grid becomes too coarse, you may miss the optimal values. You can compensate for this by performing an initial, coarse search, then performing a finer search in the neighborhood of the best initial values. This is safer than the first strategy, but there's still some risk that the initial, coarse search could end up in a suboptimal neighborhood from which the finer search can't escape.

Use random search. Bergstra and Bengio (2012) describe this strategy, and show that it can give large speedups compared to grid search. The reason is that model performance may be much more sensitive to some hyperparameters than others, and the important ones aren't known a priori. Grid search can waste iterations by trying many different values for non-influential hyperparameters while holding the influential ones fixed. Random search samples random hyperparameter values from some simple distribution, so all hyperparameters change on every iteration. Changing non-influential hyperparameters has little effect (so nothing is lost), and changing the influential ones gives more chance for improvement.

Whether using grid search or random search, make sure that the spacing between values is appropriate for each hyperparameter (in grid search, this is the grid spacing; in random search, it's related to the distribution from which hyperparameter values are sampled). For example, it makes sense to try linearly spaced values for some hyperparameters, and logarithmically spaced values for others. Using inappropriate spacing can either lead to poor coverage (increasing the risk of missing the optimal value) or require overly dense coverage to compensate (wasting computation time).

Use Bayesian optimization. This is a much more complicated approach, and is an active topic of research. In the context of hyperparameter optimization, it tries to learn a model of the loss function over hyperparameters, and use this model to adaptively choose the next hyperparameter values to try. The value of the loss function for the new hyperparameters is used in turn to update the model.

References:

Bergstra and Bengio (2012). Random search for hyper-parameter optimization.

Answer 2

The primary approach is allow to perform evaluations on sub-sets of your data or for a limited number of iterations or for a limited amount of time (if your algorithm is anytime algorithm). Then, you can exploit it by a hyperparameter optimization algorithm which supports multifidelity evaluations, i.e., can exploit low-fidelity objective function evaluations (e.g., obtained on a sub-set of your data or after a small number of iterations) to adaptively gain insights about high-fidelity objective function evaluations in order to substantially speedup the search process.

Only use random search if your budget of function evaluations is way below 10x the number of variables and/or your problem is very noisy. Otherwise, almost certainly there are better algorithms to use for your case.

Answer 3

Take a look at the optimiser built in to dlib. The technique it uses is "mathematically [proven to be] better than random search in a number of non-trivial situations".