Learning to Optimize

Hyperparameter optimization is one of the most difficult problems in machine learning. How many layers should my neural network be? How many kernels should each layer have? What type of activation function should I use? What value should I set as my learning rate?

In the month of August, I became obsessed with this problem – how to optimize hyper-parameters. I started creating an open-source tool called Hypermax, available for free through Python’s “pip install” command, or directly from the latest source code on Github (Hypermax GitHub). Initially, the tool was just there to do some surrounding non-core stuff, such as monitor the execution time and RAM usage of models, and to generate graphs based on the results of the trials. The core algorithm was not my own – it was simply the TPE algorithm, as implemented in the Hyperopt library. Originally, Hypermax was just intended to make optimization more convenient.

But I quickly became obsessed with this idea of how to make a better optimizer. TPE was an industry leading algorithm. Although invented in 2012-2013, it was still being cited as recently as 2018 as one of the best algorithms for hyperparameter optimization. In most cases, it was the leading algorithm, but more recently there have been a few new approaches, like SMAC, which can do just as well in general, but not clearly better in all cases. Even more recently (July 2018), there has been work on this algorithm called Hyperband, and its evolved version, BOHB. However, TPE is still an industry leading algorithm, with top-notch general case performance across a wide variety of optimization problems.

We started our research by testing various ways that TPE can be manipulated in order to improve its results, and various ways that we could gather data in order to know what works. This formed the basis of the first version of our Adaptive-TPE algorithm. This first research was great and validated that we were onto something, both in terms of our approach to researching a better TPE and in the specific techniques that we used.

Levers for Improving TPE

TPE (Tree of Parzen Estimators) has a few hyper-parameters that we can try to tune. Additionally, there are algorithmic things we can do to improve the algorithm.

We can think of TPE as being an algorithm which takes a history of trials, and predicts the best trial to test next. TPE itself has a single primary hyper-parameter, gamma. We can manipulate the data it uses as input in several ways:

  • Provide weights to the trials inside the TPE algorithm.
  • Change our loss function, which might alter the way that TPE behaves.
  • Force TPE to spend more time exploring certain hyper-parameters by ‘locking in’ values for others.
  • Have separate TPE distributions for separate hyper-parameters.

So overall, our landscape for improving the TPE algorithm looks like this:

In our first round of ATPE research, we tested 7 techniques for improving TPE:

  • Pass loss through math equation before optimization (failed)
  • Number of random trials before TPE (success)
  • Tuning Gamma (success)
  • Tuning n_EI_candidates (success)
  • Tuning prior_weight (failure)
  • Modelling hyper-parameters in separate distributions (failed)
  • Locking in certain hyperparameters at current best value (success)

Because of the success of the parameter locking (also called Bagged Optimization in our original paper), we wanted to expand upon the ways that parameters could be locked:

  1. Expand the algorithm to allow locking parameters to top performing results or to a random value from anywhere in that parameter's range.
  2. Allow locking to any result within the top K percentile of results.
  3. Choose cutoff points for which parameters to lock, by altering the distribution of correlations.
  4. Lock either high correlated parameters or low correlated when selecting the cutoff point.
  5. Allow the probability to vary from a 50-50 chance for locking a parameter.

So ultimately, our ATPE algorithm looks roughly like the following:

  1. Compute Spearman correlations for each hyperparameter.
  2. Determine a cutoff point between correlated and uncorrelated parameters based on cumulative correlation.
  3. Parameters chosen for potential locking have a random chance of being locked in that round.
  4. Assign locked values based on the mode ATPE is in.
  5. Create an alternative result history filtered out randomly according to the filtering mode.
  6. Use the TPE algorithm to predict the parameters that have not been locked.

The algorithm appears to have a lot of potential, but implementing it introduces a new problem: How do you choose ATPE’s own parameters at each round? The parameters include:

  • resultFilteringMode: Age, LossRank, Random, or None
  • resultFilteringAgeMultiplier: Multiplier applied to results position in history for Age filtering.
  • resultFilteringLossRankMultiplier: Multiplier applied to rank of results sorted by loss for Loss filtering.
  • resultFilteringRandomProbability: Probability for Random filtering.
  • secondaryCorrelationExponent: Exponent that correlations are raised by when determining which parameters to lock.
  • secondaryCutoff: Cumulative correlation cutoff point for locking parameters.
  • secondaryLockingMode: Either Top or Random, determining exploration strategy.
  • secondaryProbabilityMode: Either Fixed or Correlation, determining locking probability.
  • secondaryTopLockingPercentile: Percentile for top-locking mode.
  • secondaryFixedProbability: Fixed probability that a given parameter will be locked.
  • secondaryCorrelationMultiplier: Multiplier for probability in Correlation probability mode.
  • nEICandidates: Parameter to be passed into TPE algorithm.
  • gamma: Gamma parameter to be passed into TPE algorithm.

In the first phase of our research, we used grid-searching to find the possible values for the parameters of ATPE. Our problem with this new approach is twofold. First, there are way too many parameters for grid-searching to be effective. Additionally, because the parameters have a lot of potential to interact, a simple linear equation wasn’t going to help us predict.

The Dataset

Obtaining the dataset is the biggest challenge in training the ATPE algorithm. The following steps outline the data gathering:

  1. Train and test a primary model, M, which takes 2 hours.
  2. Optimizing M with algorithm O takes around 100 trials.
  3. Run algorithm O multiple times due to stochastic nature.
  4. Research on many models M representing diverse problems.
  5. Minimum of 1000 trials to gather a dataset on algorithm O’s parameters.

It becomes clear – researching optimization is hard. Our solution to this problem was discovered in the original ATPE paper, discussed in the “Simulated Hyperparameter Spaces” section.

Simulated Hyperparameter Spaces

Our “Simulated Hyperparameter Spaces” are systems of math equations designed to respond similarly to hyperparameters of real-world models. They are randomly generated with different parameters and interactions.