Stealthy hyperuniform sampling for hyperparameter optimisation

Abstract

Hyperparameter optimization is one example of a broad class of multivariate minimization problems with a complex landscape and often many local minima. As a result, gradient descent typically performs poorly, and easily parallelizable sampling methods are most commonly used, which often require the set of trial points to be chosen in advance. In most practical tuning problems, the loss depends strongly only on a few hyperparameters or their combinations, yet which ones matter is rarely known before the search begins. A sampling strategy must therefore be efficient regardless of which directions turn out to be important. Although a grid is the most intuitive way to sample the full space, it has been shown that in practice, selecting trials randomly outperforms a grid search in the typical case in which the variables are of widely differing importance, since a grid contains the same point multiple times when projected to lower dimension. However, random search is also suboptimal, as selected points can be either nearly identical or leave large gaps. Here, a new method is proposed based on disordered stealthy hyperuniform point distributions, which have smaller density fluctuations than random distributions while simultaneously performing well in projection. On a set of benchmark hyperparameter optimization and simple minimization problems, it is demonstrated that this strategy provides an improvement over grid and random search. While low-discrepancy sequences such as Sobol and Halton are competitive when the most “natural” axes coincide with the coordinate axes, we show that applying random rotations to the benchmark functions removes their advantage, while leaving the stealthy hyperuniform patterns virtually unaffected. Since the relevant directions are rarely known in advance and are generally not axis-aligned, this rotation-invariance is a key practical advantage of the proposed method.