Lazy Paired Hyper-Parameter Tuning

1 Introduction

Supervised machine learning techniques are increasingly being used as black-box components by engineers who expect them to produce high-accuracy predictions automatically. A key obstacle to this is the sensitivity of learning algorithms to hyper-parameter settings, also known as the model selection problem. To maximize accuracy on a particular dataset, one typically needs to identify optimal, domain-specific values for some set of algorithm-specific variables. Learning rates, regularization coefficients and pre-processing options are all examples of parameters that have significant impact on accuracy, and hence must be tuned by practitioners by performing repeated experiments on validation sets.

However, the variance inherent in machine learning experiments present a challenge to efficient hyper-parameter search. Due to the stochastic nature of training and testing on finite datasets, each candidate hyper-parameter configuration must be evaluated on multiple samples from the source distribution in order to identify a statistically meaningful optimum. Cross-validation and bootstrap are the most popular sampling-based approaches for estimating statistical significance. These methodologies inevitably increase the computational cost of experiments, amplifying the number of evaluations for each considered hyper-parameter configuration. This amplification persists with any of the many techniques for global optimization that can be employed to intelligently search the space of potential configurations, such as sequential model-based (e.g., Bayesian) optimization, and directed, random or evolutionary search methods. Hence, all of these approaches can benefit from eliminating unnecessary resampled evaluations at every candidate point.

Two lines of prior research are relevant for developing solutions for this problem when there is a finite set of candidate hyper-parameter configurations. Maron and Moore [1994] proposed Hoeffding Races for early elimination of underperforming candidates in a leave-one-out validation setting. An alternative approach has been pursued by multi-armed bandit algorithms, where upper bounds are employed to favor promising candidates and account for confidence in accuracy estimates from repeated evaluations [Lai and Robbins, 1985; Auer et al., 2002a; 2002b; Gittins et al., 2011].

However, these approaches assume that each sample for every configuration is constructed either independently or adversarially. In the context of hyper-parameter optimization, such rigid assumptions are unnecessary if samples chosen for cross-validation or bootstrap folds are consistent across configurations. Then, evaluation results can be compared using stronger statistical tests for matched samples, leading to significant efficiency improvements.

We demonstrate that these improvements can be reaped by incorporating paired hypothesis tests with hyper-parameter search techniques for both discrete and continuous parameter spaces. For the discrete case, we show that paired tests allow us to identify winners much more efficiently than the standard racing or multi-armed bandit strategies that do not take matched-pairing into account. For continuous hyperparameter spaces, paired tests can be organically integrated inside search techniques such as Nelder-Mead, a classic simplex-search algorithm, resulting in reaching the optimum with much fewer evaluations than full cross-validation, and actually improving convergence of the overall algorithm. The efficiency gains achieved with our algorithm are illustrated by experimental results on real and synthetic datasets.

2 ProblemDefinition

Hyper-parameter tuning for machine learning is a stochastic optimization problem. The stochasticity arises from the fact that train and test sets are finite samples (typically assumed to be i.i.d.) from an underlying joint distribution of data points and prediction targets, as well as from possible randomness in the learning algorithm itself. Let θ denote the hyper-parameters of the learning algorithm, X a random variable representing the source(s) of stochasticity, and g(·) a performance metric chosen by the user for the prediction task at hand. For binary classification, g(·) may be the area under ROC curve (AUC), and for regression g(·) may be the negative mean squared loss. The problem of hyper-parameter tuning can then be defined as:

For the moment, assume that the only source of stochasticity is the data itself, so that X represents simply the data distribution. Since the true mean for this unknown distribution cannot be computed directly, the empirical mean is optimized over random samples {X(1) , . . . ,X(n) }, an approach known as sample average approximation [Srebro and Tewari, 2010]:

In the hyper-parameter tuning process, the i-th sample X(i) can be made identical for all candidate values of θ. For example, this is true in the case of cross-validation or bootstrap starting from the same initial random seed, generating the same sequence of training and validation datasets from an initial training set. In this work, we demonstrate that such tying of evaluation subsets enables lazy hyper-parameter tuning, where the optimal θ∗ can be found without performing all n evaluations for every candidate, resulting in significant computational savings.

We note that the evaluation of g(·) is carried out in two steps. First, the learning algorithm determines the model parameters (let's call them λ) via a modeling objective function f(·) evaluated on the trainig data XT . The learned model is then evaluated on a validation set XV under the metric g(·).

Here, XT , XV , as well as the optimization of Eq. (3) may all be stochastic. Hence the empirical average of g(·) should be computed over samples of all three. In practice, people often forgo cross-validation inside the grid search loop because it is computationally expensive. This may be justifiable if the variance of the evaluations is low-a possibility when the validation or hold-out set is large, g(·) is itself an empirical average over the validation set, and there is no stochasticity within the learning procedure (Eq. (3)). In general, however, one should perform cross-validation or bootstrapping to account for the variance of the estimates of g(·).

Another notable challenge in this optimization problem is that there is no gradient information: f(·) and g(·) represent black-box learning procedure whose output cannot be expressed as a closed-form function of hyper-parameters. Hence, existing approaches to hyper-parameter optimization are "gradient-free" algorithms that either approximate the uphill direction via simplex search (e.g., Nelder-Mead), or model the evaluation (response) surface with a surrogate function (e.g., Gaussian Process optimization) [Conn et al., 2009]. Thus, finite-difference variants of stochastic gradient methods are not competitive for this problem, as they require many iterations to converge due to noise in the gradient approximations.

3 Lazy Paired Hyper-Parameter Tuning (LaPPT)

In this section, we demonstrate that performing full crossvalidation on all X(i) 's is not necessary if hypothesis testing is embedded in the search algorithm, so that the only evaluations performed are those that are statistically necessary to identify leading configurations.

3.1 Background: Statistical Hypothesis Testing

The classic example of an application for statistical hypothesis testing is the two-sample location test, where one observes two samples X and Y , each of size n and drawn from two distributions from the same family with possibly different locations (medians or means). Let μX and μY denote the true means and τ = μX - μY their difference. The null hypothesis H0 may assert that τ = 0, while the alternative hypothesis H1 may test for τ > 0, τ < 0, or τ ̸= 0 . If the distributions are Gaussian and the samples are matched, i.e., X and Y contain the same individuals under two different "treatments," then the matched-pairs t-test can decide whether to accept or reject the null hypothesis while guaranteeing a false positive rate. The test computes the t-statistic TX-Y = ˆμX-Y ˆσX-Y /√n , where ˆμX-Y = ∑i (xi - yi)/n and ˆσ2X-Y = ∑i ((xi -yi) - ˆμX-Y )2 /(n - 1) are, respectively, the sample mean and variance of the matched differences. Under the null hypothesis, TX-Y follows the Student's tdistribution with n - 1 degrees of freedom. Let Tn-1 denote the cdf of this distribution.

The statistical hypothesis testing procedure [Lehmann and Romano, 2005] explicitly controls for the probability of false positives (Type I error): it would only reject the null hypothesis when the probability of observing the statistic falls below a given threshold α (the significance level). Let tα denote the α-th quantile of the Student's t-distribution, i.e., T(tα) = α. If the alternate hypothesis is {τ > 0}, then we would reject H0 and accept H1 if TX-Y > t1-α.

The false negative probability (Type II error) can be controlled by increasing the number of evaluations at each point in a procedure known as power analysis. The power of a statistical test is the probability that it correctly rejects H0 when H1 is true. Suppose H1 = {τ > 0}. Then the power of the matched-pairs t-test may be written as:

P (Reject H0 | H1 is true) = P (TX-Y > t1-α | τ > 0)

Let β denote the acceptable false negative rate. Given β and a value for τ, we can compute the necessary sample size to guarantee that the probability of a false negative is below β when the test accepts the null hypothesis. This can be used to determine how many additional evaluations to make at each hyper-parameter configuration.

3.2 Lazy Paired Tuning for Discrete Hyper-parameters

Algorithm 1: Finite Lazy Paired Parameter Tuning

Input: C = {θ1 . . . θm}: Set of candidate hyper-parameter configurations Input: α: Significance level Input: β: False negative rate Input: no: Number of initial evaluations Input: (XT1 ,XV1 ), . . . , (XTn ,XVn ): Sequence of training and validation sets Output: θ∗ : Best configuration for i = 1 . . .m do for ℓ = 1 . . . n0 do Riℓ = g(θi , XTℓ , XVℓ ) while |C| > 1 do for θi ∈ C do for θj ̸= θi ∈ C do result = LazyPairedTCompare(Ri, Rj , α, β) if result < 0 then C = C\θi else if result > 0 then C = C\θj return C

For hyper-parameter spaces that are discreet and hence have no structure to exploit directly, selecting the best configuration can be viewed as a race over a sequence of rounds corresponding to fold evaluations [Maron and Moore, 1994]. In each round, some candidates are eliminated, and further evaluations are scheduled for the others. At the beginning of a round, all current candidates are compared pairwise. If a test accepts the alternate hypothesis that candidate i performs worse than j, then i is eliminated. 1 Conversely, if the test accept the null hypothesis of equal performance, we compute the number of evaluations needed to guarantee that they are indeed equal under an acceptable false negative rate β. 2 At the end of the round, inferior configurations are eliminated, and more evaluations are scheduled in batch for the remaining candidates. Alternatively, evaluations can be added in minibatches, with re-testing done at the end of every mini-batch. Alg. 1 contains an outline of the batch evaluation procedure.

1 Since we are performing multiple hypothesis tests simultaneously, one may be concerned with the false discovery rate inherent in multiple testing. One possible remedy is to apply the standard Bonferroni correction [Shaffer, 1995] or one of its derivatives. This controls the number of false rejections of the null hypothesis, making it less likely that we eliminate promising candidates early on.

Algorithm 2: LazyPairedTCompare

Input: X, Y : Paired observations

Input: α: Significance level

Input: β: False negative rate

Input: MaxN: Maximum number of observations

tα/2 := α/2-th quantile of Student's T distribution

t1-α/2 := (1α/2)-th quantile of Student's T distribution

Algorithm 3: Lazy Paired Nelder-Mead (LaPPT-NM)

Input: Initial simplex {θ0, θ1, . . . , θd}, objective function g(θ), evaluations {g(θ0), g(θ1), . . . , g(θd)} Output: A local maximum of g(·)

Define all comparisons of g(θ) using LazyPairedTCompare Run Nelder-Mead algorithm

3.3 Lazy Paired Tuning for Infinite Hyper-parameters in Nelder-Mead Optimization

When the hyperparameter space is metric and continuous, we can combine lazy paired tuning with a global optimization routine such as direct search [Conn et al., 2009]. As an illustration, we demonstrate such an integration with the Nelder-Mead algorithm [Nelder and Mead, 1965], a classic direct simplex search technique that continues to enjoy wide popularity for hyper-parameter tuning (e.g., see [Dror et al., 2011]).

2 The power analysis in Eq. (5) requires having an estimate of τ, the expected difference in performance. We use the observed difference in the current round.

Nelder-Mead (NM) operates sequentially, starting out with a simplex of d + 1 initialization points (for d parameters). Let {θ0, θ1, . . . , θd} represent the simplex vertices, ranked from worst to best by their value on the response surface, g(θ0), . . . , g(θd). At each step, NM tries to move θ0, the worst performing point, toward or beyond the rest of the simplex. It does so via line search from θ0 towards θc = ∑di=1 θi/d, the centroid of the rest of the simplex.

We incorporate lazy tuning into classic Nelder-Mead by replacing all the comparison steps with the LAZYPAIREDTCOMPARE algorithm detailed in Alg. 2. Evaluations are added until the test decision can guarantee the desired false positive and false negative probabilities.

4 RelatedWork

A number of methods have been proposed to address the search aspect of the hyper-parameter tuning problem as efficient alternatives to exhaustive grid search (which unfortunately continues to be routinely employed in practice). Representative technique families include random search [Bergstra and Bengio, 2012], sequential model-based optimization [Brochu et al., 2010; Hutter et al., 2011], direct search [Luersen et al., 2004], evolutionary search [Hansen and Ostermeier, 1996] and structured search [Yang and Rahimi, 2011]. Use of these techniques assumes standard resampled evaluations at each potential configuration in the search space. Hence, all of these methods can benefit from eliminating unnecessary resampling steps. Conn et al.; Brochu et al.; Spall [2009; 2010; 2003] all present comprehensive overviews of solutions from adjacent communities that studied the problem. More generally, the problem of searching for optima of a function with probabilistic output falls under the category of stochastic optimization, where previously proposed approaches include, e.g., probabilistic hill climbing [Greiner, 1992].

On the cost-saving front, Krueger et al. [2012] proposed to speed up cross-validation by sequentially evaluating the hyper-parameter candidates on a growing sequence of datasets. At each step, a set of sub-optimal performers are eliminated. The statistical elimination tests are in the same spirit as our setup. But they approach the problem from the angle of fast evaluation on smaller datasets, and hence have to contend with the possibility of losing track of the true optimum configuration when starting from very small datasets.

Hoeffding Racing [Heidrich-Meisner and Igel, 2009; Maron and Moore, 1994] tackles the problem of model selection on a finite grid by comparing confidence intervals around the sample means of model performance. The race utilizes the Hoeffding or Bernstein inequalities to provide concentration bounds around the means. More performance samples are added until the bounds tighten to the point where a clear winner emerges. However, it is well-known that these concentration bound can be quite loose, hence many evaluations may be required before one hyperparameter setting may be declared the winner. The advantage of these bounds is that they are uniform against all alternatives, which is useful when each parameter setting much be compared against all other settings. This is applicable in the discrete hyper-parameter space setting, where Hoeffding Racing may be combined with grid search or random search methods.

The discrete parameter space setting is also closely related to the multi-armed bandits problem [Lai and Robbins, 1985; Auer et al., 2002a; 2002b; Gittins et al., 2011]. A variety of sampling strategies exist with different assumptions on the structure of the payoffs and relationship between the arms. We compare against two classic heuristics: UCB and EXP3. Recent work on dueling bandits [Yue et al., 2012] examines the setting where the bandits are pitched against one another, a pair at a time. This similates the testing scenario of production machine learning systems such as a search engine ranker, but does not fit as well to the hyper-parameter tuning and cross-validation setting.

Strens and Moore [2002] proposed using paired comparisons in policy search for reinforcement learning. The search procedure evaluates a number of candidate policies where paired samples may be obtained by, for example, fixing the random number sequence of the simulations. While closely related to the scenario of hyper-parameter search, they do not take advantage of power analysis to determine the number of necessary evaluations.

5 Evaluation

In this section, we evaluate the efficiency of LaPPT on real and synthetic problems in both discrete and continuous hyperparameter spaces.

5.1 Discrete hyper-parameter spaces

We compare LaPPT to standard approaches for discrete-space search: Hoeffding Racing and most popular multi-armed bandit strategies, UCB1 and EXP3. In this section, we shift to terminology used in multi-armed bandit literature: each hyper-parameter configuration corresponds to an arm, pulling which is synonymous with evaluating the learner on the next fold. Let the random varaible R ∈ [0, 1] denote reward (the learner's predictive performance), and ˆRn its empirical mean after n observations.

Random: select an arm uniformly at random at each pull.

Hoeffding Race: The Hoeffding inequality states that P ( ˆRn - E [R] > ϵ) < exp (-2ϵ2 /n), implying that, with probability greater than 1 -ϵ, the true mean of the learner's performance lies in the interval ˆRn ± √- log(ϵ)/2n. At each round, the race eliminates candidates whose performance upper bound is below another candidate's lower bound. Each of the remaining candidates obtains another evaluation, and the best configuration for the round is taken to be the one yielding the highest empirical mean. In our experiments, ϵ = 0.01.

UCB1: The classic UCB1 policy evaluates the configuration with the maximum Hoeffding upper bound, where ϵ is set to decrease over time. Namely, at time t, UCB1 plays the arm argmaxk ˆRk,t-1 + √ρ log t/nk,t-1, where Rk,t-1 denotes the empirical average reward for the kth arm at time t - 1, nk,t-1 the number of times this arm has been played thus far, and ρ is a parameter set to 0.2 in our experiments. This corresponds to setting ϵt = O(1/t4 ) in the Hoeffding inequality. Unlike the Hoeffding Race, UCB does not eliminate candidates, thereby reducing the risk of falsely eliminating a good candidate.

EXP3: The EXP3 policymaintains a probability distribution based on the cumulative reward accrued at each arm. At time t, it pulls the k-th arm with probability proportional to pk,t = exp (ηSi,t-1), where Si,t-1 := ∑t-1 j=1 Ri,j is the cumulative reward for the i-th arm up to time t - 1 and η is a free parameter set to 0.2 in our experiments. The estimated reward ˜Ri,j is taken to be 1 if the i-th arm is pulled on round j, and 1 - 1-Ri,j pi,j otherwise (an unbiased estimate of the unobserved reward).

For all experiments on finite space tuning, we set α = 0.1 and β = 0.6 for the paired-T testing and power analysis.

We first perform a sanity check using Bernoulli bandits. We construct 100 bandits, each generating binary rewards with success probability θk sampled uniformly from (0, 1). To simulate the matched-pairs evaluation setting, the rewards of the bandits are tied so that the random seed for the i-th pull is the same across all arms. Formally, the reward for the i-th pull of the k-th arm is 1(ri < θk), with ri being sampled uniformly at random and held to be the same across all k. We repeat the trial 100 times, each time going up to a maximum of 3000 total evaluations/arm-pulls. Our primary performance measure is simple regret:

where θt is the (true) expected reward of the chosen arm at time t, and θ∗ is the expected reward of the best arm.

Results of racing on Bernoulli bandits are shown in Fig. 2. Not surprisingly, the random strategy does not learn over time: the arm it chooses after 3000 evaluations is no more likely to be the best arm. UCB is the second-to-worst performer, bested by Hoeffding Racing, EXP3 and LaPPT. EXP3 and LaPPT are the overall winners with closely matching results. An in-depth inspection of the results reveals that EXP3 selects a non-optimal arm 5 times out of 100 trials, whereas LaPPT is only wrong once, but selects a wrong arm whose true reward is worse than the those of EXP3's mistakes. So LaPPT has larger mean and variance in terms of average regret, but is wrong fewer times.

Another notable trend is that both Hoeffding Racing and LaPPT are much more aggressive than EXP3 at the beginning of the game, starting with much lower average regret given very few arm pulls. This is due to our greedy startgame strategy: we give all arms 3 evaluations to start with, before eliminating any candidates. During the initial phase, we select the arm with the best empirical average reward so far to compare against the optimal arm. This is the same as the simple strategy of performing 1, 2, or 3 evaluations of each configuration and selecting the empirical best.

Next, we evaluate the performance of the algorithms for actual hyper-parameter tuning. We utilize three popular UCI datasets chosen to span a variety of data characteristics and learning tasks, with corresponding predictive accuracy metrics: Adult Census (binary classification, AUC), Housing (regression, L1 error), and Waveform (multiclass classification, cross-entropy). Learning is performed with task-appropriate variants of gradient tree boosting [Friedman, 2001], varying four key hyper-parameters: gradient boosting learning rate, number of trees, maximum number of leaves per tree, and minimum number of instances per leaf. We also experimented with Logistic Regression as the base learner and observed analogous results, hence omitted.

To simulate the setting of the discrete hyper-parameter space, we randomly sample 100 parameter configurations corresponding to 100 arms, and perform 50-fold crossvalidation at each configuration. We use the negative L1 error rate and cross-entropy, and we rescale all metrics to the [0, 1] range, so that accuracy on the i-th fold corresponds to the reward from the i-th pull of an arm. The reward is only revealed when the configuration is selected for evaluation. If a selected configuration has no more remaining unevaluated cross-validation folds, we re-calculate the best arm using the current set of evaluations.

As shown in Fig. 3, the reward distributions on real experiments are very different from that of Bernoulli bandits. For Bernoulli bandits, the expected reward p is uniformly sampled from (0, 1) with variance equal to p(1 - p). Fig. 3(a) shows the sorted true rewards, the empirical means, and the standard deviation envelope. The elliptical shape of the envelope demonstrates that the variance is smallest for extreme values of p. As designed, the rewards are uniformly distributed between 0 and 1. In contrast, for cross-validation results from real learning experiments, a significant portion of settings produced accuracy that are close to optimal (i.e., about half of the configurations for Adult Census are within 5% of the optimal configuration). In addition, reward distribution over evaluations at each arm is more Gaussian than Bernoulli. As we shall see, the difference in reward distributions results in very different behaviors of the algorithms.

Hyper-parameter tuning results on cross-validation evaluations are presented in Fig. 1, with log-scale y-axis highlighting differences between the algorithms' final solutions. The performances are similar on all three datasets, and below we use the numbers from the Adult Census dataset when discussing the specifics. As before, the Random strategy does not learn. EXP3 behaves very differently from before and is now the second slowest learner, only better than Random. It starts out with a lot of explorations, presumably because there are a large number of close-to-optimal configurations.

After about 200 evaluations, EXP3 starts to get closer to optimal, but much more slowly than the other strategies. UCB starts out with one evaluation per configuration (which we do not count when evaluating regret), and thereafter performs on-par with Hoeffding Racing, both reaching an average regret of 0.002 by the end. LaPPT and Hoeffding Racing uses the same selection strategy during the initial warm-up phase, hence are indistinguishable from each other at the beginning. After 300 evaluations (3 per configuration), LaPPT starts to compare the candidates using matched pairs t-tests and discards the statistical losers. It does so very quickly and is able to find the best configuration in 90 out of 100 trials, taking on average fewer than 425 evaluations. In all but 6 trials, LaPPT narrows down to only one candidate. In comparison, Hoeffding Racing is unable to eliminate any candidate within 700 evaluations. This is due to the looseness of the Hoeffding bound and the fact that the mean rewards are closely clustered together. We note that when we run the experiments beyond 700 evaluations, Hoeffding Racing and UCB do eventually obtain the optimal candidate, and LaPPT sometimes pays the price for aggressive elimination when it eliminates the wrong one. However, given that evaluation of learning algorithms could be expensive, such long evaluation horizon is often not practical, and it is really the regret one achieves with few evaluations that is important. To that end, the greedy strategy of evaluating each arm once or twice and picking the one with the best empirical average is a reasonable strategy. But as we can see, the more sophisticated strategies do provide a gain when fine tuning is important.

5.2 Continuous hyper-parameter space

To investigate the predictive and computational performance of LaPPT in combination with Nelder-Mead, we demonstrate their use on Adult Census with the same four hyperparameters: number of trees, learning rate, maximum number of leaves per tree, and minimum number of instances per leaf. Area under ROC curve (AUC) is the metric to optimize, and we report results on running experiments with bootstrap.

The central conjecture of the proposed approach is that lazy evaluation improves the efficiency of the Nelder-Mead algorithm for stochastic functions while maintaining predictive accuracy. To test it, we first compare the optimization quality of classic Nelder-Mead (with 20 bootstrap rounds) with that of LaPPT Nelder-Mead (with up to 20 bootstrap rounds, evaluated only if required). Fig. 4 shows a heatmap of the optimal true AUC over the learning rate and the number of leaves. (The AUC value at each point is the maximum over the other hyper-parameters.) The figure overlays the locations of optima found in 20 runs of LaPPT Nelder-Mead and classic Nelder-Mead, demonstrating that LaPPT-NM can find the same optima as NM, but, as we shall see, much faster.

In Fig. 5, we compare the total number of train-test evaluations, the number of iterations of Nelder-Mead, and the accuracy at the final optimum for Nelder-Mead and LaPPT Nelder-Mead with varying test power β. These results demonstrate that LaPPT Nelder-Mead significantly improves the efficiency of hyper-parameter search while still identifying the optimal hyper-parameter settings. Furthermore, we note that the algorithm not only reduce the number of evaluations, but, more importantly, also results in faster convergence due to faster onset of the inside contraction and shrinkage iterations, which occurs when the test is able to judge minor variations in g(·) to be statistically insignificant. Note that these results directly imply that LaPPT-NM is faster than NM in wall-clock run-time.

6 Conclusions

In this paper, we present a simple and general technique for improving the efficiency of hyper-parameter search in supervised machine learning. Tying train-test resampling during bootstrap or cross-validation allows utilizing paired hypothesis tests and power analysis to limit the number of resampled evaluations. The approach is shown to be effective empirically on discrete hyper-parameter spaces where it outperforms bandit-based methods, and on continuous hyperparameter spaces where it can be easily integrated with methods such as Nelder-Mead, improving their speed of convergence in addition to reducing the number of train-test evaluations.