Source-linked AI summary
Freeze-Thaw Bayesian Optimization
Kevin Swersky, Jasper Snoek, Ryan Prescott Adams
TL;DR
Hyperparameter search is expensive when models must be fully trained before their settings can be assessed. The paper develops freeze-thaw Bayesian optimization, combining training-curve priors, temporal Gaussian processes, and information-theoretic decisions to pause, resume, or start runs. Experiments report that it finds good settings in considerably less time than ordinary Bayesian optimization.
Problem
Bayesian optimization for machine learning traditionally requires fully training each model before evaluating its hyperparameters, limiting use of partial training information.
Method
The method forecasts exponentially decaying training curves with a novel kernel and efficient temporal Gaussian process, then uses an information-theoretic framework to pause, resume, or start training runs.
Results
The method finds good hyperparameter settings for many models in considerably less time than ordinary Bayesian optimization.
Takeaways & Limitations
Partial training information can guide dynamic allocation of epochs across new and previously started models during hyperparameter optimization.
Takeaways & Limitations
The approach assumes training curves roughly follow exponential decay; when this does not hold, more flexible priors may be needed.
Abstract
from arXiv · showhide
In this paper we develop a dynamic form of Bayesian optimization for machine learning models with the goal of rapidly finding good hyperparameter settings. Our method uses the partial information gained during the training of a machine learning model in order to decide whether to pause training and start a new model, or resume the training of a previously-considered model. We specifically tailor our method to machine learning problems by developing a novel positive-definite covariance kernel to capture a variety of training curves. Furthermore, we develop a Gaussian process prior that scales gracefully with additional temporal observations. Finally, we provide an information-theoretic framework to automate the decision process. Experiments on several common machine learning models show that our approach is extremely effective in practice.
1. Introduction
Hyperparameter optimization is costly because candidate settings are often evaluated only after full model training. Freeze-thaw Bayesian optimization uses partial training information to pause, resume, or replace models, with training-curve forecasts guiding the search.
- Bayesian optimization seeks good hyperparameter settings with as few expensive model evaluations as possible.It uses a probabilistic model of uncertainty to choose promising settings.
- Fully training each model before assessing its hyperparameters prevents earlier pruning of likely low-quality candidates.Human experts can often judge eventual usefulness from partially completed training, motivating earlier decisions.
- Freeze-thaw Bayesian optimization decides whether to pause one model, start another, or resume a previously considered model.The algorithm maintains frozen, partially completed models and selects which to thaw using an information-theoretic criterion.
- The method models training curves with an infinite mixture of exponentially decaying basis functions and an efficient temporal Gaussian process prior.These components forecast final results from partial curves during Bayesian optimization.
- Experiments show that freeze-thaw Bayesian optimization finds good hyperparameter settings in considerably less time than ordinary Bayesian optimization.
2. Background
The paper reviews Gaussian processes as uncertainty-aware function priors and Bayesian optimization as probabilistic search over expensive objectives. It introduces expected improvement and entropy search as acquisition strategies for choosing evaluations.
- Gaussian Processes: A Gaussian process is a probability distribution over functions, specified by a kernel and a mean function.Its input space can be any domain admitting a positive definite kernel.
- Gaussian Processes: Gaussian-process prediction requires O(N^3) computation because it involves inverting the Gram matrix.
- Bayesian Optimization: Bayesian optimization searches globally over expensive, noisy functions on a bounded domain by fitting a probabilistic surrogate and selecting promising evaluations.The paper considers the unit hypercube [0, 1]^D as the domain without loss of generality.
- Bayesian Optimization: An acquisition function balances exploration of uncertain regions against exploitation of regions likely to produce good results.The next point is chosen by maximizing the acquisition function.
- Training-Curve Priors: Figure 1 progresses from exponential-decay basis functions to Gaussian-process samples and conditioned curves resembling natural training curves.The conditioned samples add an Ornstein-Uhlenbeck kernel and start from a positive value.
- Acquisition Functions: Expected improvement uses the posterior mean and variance to quantify improvement relative to the best observed output.The criterion is presented as a popular and effective acquisition function.
- Acquisition Functions: Entropy search chooses evaluations that maximize expected information gain about the location of the minimum.The method estimates the minimum's distribution with Monte Carlo simulation on a discrete grid of high-EI points.
3. A Kernel for Training Curves
The paper introduces a positive-definite kernel for iterative optimization curves by integrating infinitely many exponentially decaying basis functions. A gamma mixing measure makes the covariance analytically tractable and supports Gaussian-process modeling of noisy training curves.
- The kernel is designed to model iterative optimization curves using exponentially decaying functions of the form e^-λt.
- Instead of a finite fixed basis, the covariance integrates basis functions parameterized by λ over [0, ∞) with a weighting measure.
- A gamma mixing measure with α, β > 0 gives the covariance an analytic solution.
- Figure 2 represents each learning curve with an independent GP conditioned on a jointly modeled mean, then predicts its eventual asymptote.
- The resulting model uses this kernel as the covariance over time steps for iterative optimization procedures.
4. Efficient Gaussian Processes for Iterative Training Procedures
The efficient GP models each training curve independently around a shared GP mean over hyperparameter settings, enabling asymptotic predictions from partial observations. Its structured covariance and matrix identities reduce computation compared with a naive GP over every time-stamped observation.
- Computational challenge: A naive GP over N hyperparameter settings and T training iterations would require O(N^3T^3) computation.
- GP specification: The model assumes each training curve is a separate GP conditioned on a global GP that supplies its mean across hyperparameter settings.
- GP specification: The training curves asymptotically converge to the latent function f away from observed points, supporting predictions of final performance.
- Efficient representation: Block-diagonal time and observation matrices represent the separate curves and their corresponding time-based covariances.
- Efficient inference: The Woodbury matrix identity and matrix determinant lemma provide efficient inversions and normalization terms for the marginal likelihood.
- Efficient inference: Independent inversion of K_x and K_t yields total complexity O(N^3 + T^3 + NT^2).The paper notes that T is typically 10–100 or can be reduced through coarser curve sampling.
5. Bayesian Optimization for Iterative Training Procedures
Freeze-thaw Bayesian optimization chooses whether to continue old models, pause them, or start new ones while targeting the best asymptotic model. It uses asymptotic expected improvement to form a candidate basket and entropy search to select the next run.
- Objective: The optimization target is the hyperparameter setting whose fully trained model has the lowest asymptotic error.
- Candidate selection: The strategy maintains a basket of B = B_old + B_new candidates, using B_old = 10 previously trained and B_new = 3 new models in practice.
- Candidate selection: The basket is rebuilt after each new observation using candidates with maximum expected improvement at the asymptote.
- Acquisition strategy: Algorithm 1 estimates the probability of the minimum through Monte Carlo simulation after fantasizing observations for old and new candidates.
- Acquisition strategy: Entropy search selects which candidate to run because naive expected improvement would always favor new models over additional iterations of old ones.
6. Empirical Analysis
The empirical analysis compares the proposed method with Warped GP EI MCMC across three machine learning tasks and shows how it allocates training dynamically. Across experiments, the method reaches better loss with fewer wasted training epochs by stopping, resuming, and extending promising curves.
- Experimental setup: The method is compared with Warped GP EI MCMC on Online LDA, Logistic Regression, and Probabilistic Matrix Factorization.Each experiment was run five times, reporting mean loss as a function of cumulative training epochs.
- Experimental setup: The experiments cover five-hyperparameter Online LDA, five-hyperparameter Logistic Regression, and three-hyperparameter PMF tasks.The tasks use Wikipedia documents, MNIST, and MovieLens ratings, respectively.
- Results: In each experiment, the proposed method significantly outperforms the state-of-the-art by dynamically stopping and restarting experiments.The improvement is especially prominent for online LDA, where the authors hypothesize that curve shapes are predictable from few observed epochs.
- Practical cost: The additional computational effort for explicitly modeling epochs is eclipsed by reaching a better loss more rapidly.The analysis assumes the optimized models are sufficiently expensive that Gaussian-process fitting costs are negligible.
- Optimization behavior: The method initially explores many settings with few epochs, then runs promising curves longer and revisits existing curves in short extensions.This progression is visualized for the PMF problem in Figure 4.
7. Conclusion
The paper presents Bayesian optimization that uses partial training information to forecast training curves and dynamically manage model runs. Its key scope boundary is the assumption that training curves approximately follow exponential decay, motivating more flexible priors when that assumption fails.
- Contribution: The algorithm exploits partial information obtained during iterative model training to improve hyperparameter tuning.Hyperparameter tuning can substantially affect model performance.
- Method: An infinite mixture of exponentially decaying basis functions and an efficient temporal Gaussian process prior forecast training curves.The approach is designed to model a variety of machine learning training curves.
- Method: An information-theoretic decision framework dynamically pauses, resumes, or creates training runs to rapidly find good hyperparameter settings.The framework uses the forecasts during Bayesian optimization.
- Scope and limitation: The method assumes training curves tend to follow exponential decay, and more flexible priors may be needed when this does not hold.The paper mentions separable spatio-temporal Gaussian processes as one possible alternative.
B.1. Inference Derivations
The inference derivations specify posterior and posterior predictive distributions for both new hyperparameter settings and new points within training curves. They also describe prediction without observations using the mean and variance from Equation 19.
- Posterior inference: The posterior distribution is expressed using the Gaussian conditioning property given observed outputs and input locations.
- Posterior prediction: For a new hyperparameter setting x∗, the derivations define its posterior predictive distribution conditioned on the observed data.
- Posterior prediction: The posterior predictive distribution for a new point in a training curve, yn∗, is given over the predicted temporal grid.The experiments use a regularly spaced grid, so dependence on t is omitted for brevity.
- Prior prediction: Without observations, the posterior predictive distribution uses mean µ∗ and variance Σ∗∗ from Equation 19.
APPENDIX C: IMPLEMENTATION DETAILS
The implementation follows the conventions of prior work while modifying the accompanying Spearmint package for the Gaussian-process model.
- Implementation: The experiments modify the Spearmint package while following implementation conventions from reference [4].Further Gaussian-process implementation details are provided in the appendix.
C.1. Kernels and GP Hyperparameters
The model uses separate kernel and prior choices for hyperparameters and training epochs. Hyperparameter warping, custom temporal covariance, and specified priors define the Gaussian-process model.
- Hyperparameter kernel: A Matérn-5/2 kernel models the function over hyperparameters, combined with a warping technique.
- Hyperparameter kernel: Each hyperparameter x is warped as wd(x) = BetaCDF(x, ad, bd), where BetaCDF is the beta-distribution cumulative distribution.
- Gaussian-process priors: The model places log-normal priors on θ0, ad, and bd, and a uniform prior on θd.
- Temporal kernel: Across epochs, the covariance uses a custom exponential decay kernel with an additive noise kernel.
- Gaussian-process priors: The temporal-kernel hyperparameters α and β receive lognormal priors, while σ2 receives a horseshoe prior.
- Gaussian-process priors: A constant prior mean m uses a uniform hyperprior and is constrained not to exceed the observation bounds.