Title: ACCELERATING NEURAL ARCHITECTURE SEARCH US-ING PERFORMANCE PREDICTION

Abstract: Methods for neural network hyperparameter optimization and architecture search are computationally expensive due to the need to train a large number of model configurations. In this paper, we show that simple regression models can predict the final performance of partially trained model configurations using features based on network architectures, hyperparameters, and time-series validation performance data. We empirically show that our performance prediction models are much more accurate than prominent Bayesian counterparts, are simpler to implement, and are faster to train. Our models can predict final performance in both visual classification and language modeling domains, are effective for predicting performance of drastically varying model architectures, and can even generalize between model classes. Using these prediction models, we also implement an early stopping method for hyperparameter optimization and architecture search, which obtains a speedup of a factor up to 6x in both hyperparameter optimization and architecture search. Finally, we empirically show that our early stopping method can be seamlessly incorporated into both reinforcement learning-based architecture selection algorithms and bandit based search methods. Through extensive experimentation, we empirically show our performance prediction models and early stopping algorithm are state-of-the-art in terms of prediction accuracy and speedup achieved while still identifying the optimal model configurations.

1. INTRODUCTION:

Significant human expertise and labor is required for designing high-performing neural network architectures and successfully training them for different applications. Ongoing research in two areas-architecture search and hyperparameter optimization-attempts to reduce the amount of human intervention required for these tasks. Hyperparameter optimization methods (e.g., Hutter et al. (2011) ; Snoek et al. (2015) ; Li et al. (2017) ) focus primarily on obtaining good optimization hyperparameter configurations for training human-designed networks, whereas architecture search algorithms (Bergstra et al., 2013; Verbancsics & Harguess, 2013; Baker et al., 2017; Zoph & Le, 2017) aim to design neural network architectures from scratch. Both sets of algorithms require training a large number of neural network configurations for identifying the right set of hyperparameters or the right network architecture and are hence computationally expensive.

When sampling many different model configurations, it is likely that many subpar configurations will be explored. Human experts are quite adept at recognizing and terminating suboptimal model configurations by inspecting their partial learning curves. In this paper we seek to emulate this behavior and automatically identify and terminate subpar model configurations in order to speedup both architecture search and hyperparameter optimization methods. Our method parameterizes learning curve trajectories with simple features derived from model architectures, training hyperparameters, and early time-series measurements from the learning curve. We use these features to train a set of simple regression models that predict the final validation performance of partially trained neural network configurations using a small training set of fully trained curves, and we empirically validate our

2. RELATED WORK:

Neural Network Performance Prediction: There has been limited work on predicting neural network performance during training. Domhan et al. (2015) introduce a weighted probabilistic model for learning curves and utilize this model for speeding up hyperparameter search in small convolutional neural networks (CNNs) and fully-connected networks (FCNs). Building on Domhan et al. (2015) , Klein et al. (2017) train Bayesian neural networks for predicting unobserved learning curves using a training set of fully and partially observed learning curves. Both methods rely on expensive Markov chain Monte Carlo (MCMC) sampling procedures and handcrafted learning curve basis functions. We also note that Swersky et al. (2014) develop a Gaussian Process kernel for predicting individual learning curves, which they use to automatically stop and restart configurations.

Architecture Search: We define architecture search as an algorithmic approach for designing neural network architectures from scratch. The earliest architecture search approaches were based on genetic algorithms (Schaffer et al., 1992; Stanley & Miikkulainen, 2002; Verbancsics & Harguess, 2013) or Bayesian optimization (Bergstra et al., 2013; Shahriari et al., 2016) . More recently, reinforcement learning methods have become popular. Baker et al. (2017) use Q-learning to design competitive CNNs for image classification. Zoph & Le (2017) use policy gradients to design state-of-the-art CNNs and recurrent cell architectures. Several methods for architecture search (Cortes et al., 2017; Negrinho & Gordon, 2017; Zoph et al., 2017; Brock et al., 2017; Suganuma et al., 2017) have been proposed this year since the publication of Baker et al. (2017) and Zoph & Le (2017) .

Hyperparameter Optimization: We define hyperparameter optimization as an algorithmic approach for finding optimal values of architecture independent hyperparameters such as learning rate and batch size, along with a limited search through the network design space. Bayesian hyperparameter optimization methods include those based on sequential model-based optimization (SMAC) (Hutter et al., 2011) , Gaussian processes (GP) (Snoek et al., 2012) , TPE (Bergstra et al., 2013) , and neural networks Snoek et al. (2015) . However, random search or grid search is most commonly used in practical settings (Bergstra & Bengio, 2012) . Recently, Li et al. (2017) introduced Hyperband, a multiarmed bandit-based efficient random search technique that outperforms state-of-the-art Bayesian optimization methods.

3. NEURAL NETWORK PERFORMANCE PREDICTION:

We first describe our model for neural network performance prediction, followed by a description of the datasets used to evaluate our model, and finally present experimental results.

3.1. MODELING LEARNING CURVES:

Our goal is to model the validation performance y T of a neural network configuration x ∈ X ⊂ R d at epoch T ∈ Z + using previous performance observations y(t). For each configuration x trained for T epochs, we record a time-series y(T ) = y 1 , y 2 , . . . , y T of validation performances. We train a population of n configurations, obtaining a set S = {(x 1 , y 1 (T )), (x 2 , y 2 (T )), . . . , (x n , y n (T ))}. This problem formulation is very similar to Klein et al. (2017) . Note that most architecture and hyperparameter search methods naturally collect S.

We propose to use a set of features u x , derived from the neural network configuration x, along with a subset of time-series performances y(τ ) = (y t ) t=1,2,...,τ (where 1 ≤ τ < T ) from S to train a regression model for estimating y T . We use models without natural support for variable size input, so we train T -1 regression models, where each successive model uses one more point of the time-series validation data. As we shall see in subsequent sections, this use of sequential regression models (SRM) is more computationally efficient and more precise than methods that train a single model.

Features::

We use features based on time-series (TS) validation performances, architecture parameters (AP), and hyperparameters (HP). ( 1) TS: Assume we are training the τ th model in the SRM. TS features include the validation performances y(τ ) = (y t ) t=1,2,...,τ , the first-order differences of validation performances, i.e. y t = (y t -y t-1 ), the second-order differences of validation performances, i.e. y t = (y t -y t-1 ), and mean and standard deviation of performances. (2) AP: These include total number of weights and number of layers. (3) HP: These include all hyperparameters used for training the neural networks, e.g. initial learning rate and learning rate decay (full list in Appendix Table 4 ).

3.2. DATASETS AND TRAINING PROCEDURES:

Figure 1 shows example learning curves from three of the datasets considered in our experiments. We provide brief summary of the datasets below. Please see Appendix Section A for further details on the search space, preprocessing, hyperparameters and training settings of all datasets.

DATASETS WITH VARYING ARCHITECTURES::

Deep Resnets (TinyImageNet): We sample 500 ResNet architectures and train them on the TinyIm-ageNet * dataset (containing 200 classes with 500 training images of 32 × 32 pixels) for 140 epochs. We vary depths, filter sizes and number of convolutional filter block outputs. The network depths vary between 14 and 110.

Deep Resnets (CIFAR-10): We sample 500 39-layer ResNet architectures from a search space similar to Zoph & Le (2017) , varying kernel width, kernel height, and number of kernels. We train these models for 50 epochs on CIFAR-10.

MetaQNN CNNs (CIFAR-10 and SVHN)::

We sample 1,000 model architectures from the search space detailed by Baker et al. (2017) , which allows for varying the numbers and orderings of convolution, pooling, and fully connected layers. The models are between 1 and 12 layers for the SVHN experiment and between 1 and 18 layers for the CIFAR-10 experiment. Each architecture is trained on SVHN and CIFAR-10 datasets for 20 epochs.

LSTM (PTB)::

We sample 300 LSTM models and train them on the Penn Treebank dataset for 60 epochs, evaluating perplexity on the validation set. We vary number of LSTM cells and hidden layer inputs between 10-1400.

DATASETS WITH VARYING HYPERPARAMETERS::

Cuda-Convnet (CIFAR-10 and SVHN): We train Cuda-Convnet architecture (Krizhevsky, 2012) with varying values of initial learning rate, learning rate reduction step size, weight decay for convolutional and fully connected layers, and scale and power of local response normalization layers. We train models with CIFAR-10 for 60 epochs and with SVHN for 12 epochs. 

3.3. PREDICTION PERFORMANCE:

Choice of Regression Method: We now describe our results for predicting final neural network performance. For all experiments, we train our SRMs on 100 randomly sampled neural network configurations. We obtain the best performing method using random hyperparameter search over 3-fold cross-validation. We then compute the regression performance over the remainder of the dataset using the coefficient of determination R 2 . We repeat each experiment 10 times and report the results with standard errors. We experiment with a few simple regression models, including ordinary least squares (OLS), random forests (RF), Bayesian linear regression (BLR), and ν-support vector machine regression (ν-SVR). For both OLS and ν-SVR, we choose between the linear and RBF kernels based on prediction performance-after hyperparameter search, in case of ν-SVR. We chose 100 as the number of sampled configurations somewhat arbitrarily, though we found that prediction performance was quite poor below 50 and improves steadily after. As seen in Table 1 , ν-SVR performs the best on most datasets, though not by a large margin. For the rest of this paper, we use ν-SVR unless otherwise specified.

Ablation Study on Feature Sets: In Table 2 , we compare the predictive ability of different feature sets, training SVR with time-series (TS) features obtained from 25% of the learning curve, along with features of architecture parameters (AP), and hyperparameters (HP). TS features explain the largest fraction of the variance in all cases and found that in general AP are more important that HP. AP features almost match TS on the ResNet (TinyImageNet) dataset, indicating that choice of architecture has a large influence on accuracy for ResNets. Figure 2 shows the true vs. predicted performance for all test points in three datasets, trained with TS, AP, and HP features.

Generalization To Out Of Distribution Configurations::

We also test to see whether our SRMs can accurately predict the performance of out-of-distribution neural networks. For instance, if we train a ν-SVR model on the Deep Resnet (TinyImagenet) dataset at 25% of the learning curve observed on configurations below median depth (60 layers), we can achieve R 2 = 0.86 on configurations above median depth. The corresponding number for prediction below median depth is 0.89. We repeated this experiment all datasets with different hyperparameter values below/above the median and found that SRMs generally showed consistent performance across such splits. Full results can be found in Appendix Section H. 25% of learning curve used for models including TS features.

3.3.1. COMPARISON WITH EXISTING METHODS::

We now compare the neural network performance prediction ability of SRMs with three existing learning curve prediction methods: (1) Bayesian Neural Network (BNN) (Klein et al., 2017) , ( 2) the learning curve extrapolation (LCE) method (Domhan et al., 2015) , and (3) the last seen value (LastSeenValue) heuristic (Li et al., 2017) . When training the BNN, we not only present it with the subset of fully observed learning curves but also all other partially observed learning curves from the training set. While we do not present the partially observed curves to the SRMs for training, we felt this was a fair comparison as an SRM uses the entire partially observed learning curve during inference. Methods ( 2) and ( 3) do not incorporate prior learning curves during training. Figure 3 shows the R 2 obtained by each method for predicting the final performance versus the percent of the learning curve used for training the model. We see that in all neural network configuration spaces and across all datasets, ν-SVR outperform the competing methods. Bayesian linear regression (BLR) also performs comparably well to ν-SVR and better than the more complex Bayesian methods (BNN and LCE). The LastSeenValue heuristic only becomes viable when the configurations are near convergence, and its performance is worse than an SRM for very deep models. We also find that the SRMs outperform the LCE method in all experiments, even after we remove a few extreme prediction outliers produced by LCE. Finally, while BNN outperforms the LastSeenValue and LCE methods when only a few iterations have been observed, it does worse than our proposed method. In summary, we show that our simple SRMs outperforms existing Bayesian approaches on predicting neural network performance on modern, very deep models in computer vision and language modeling tasks.

Since most of our experiments perform stepwise learning rate decay; it is conceivable that the performance gap between SRMs and both LCE and BNN results from a lack of sharp jumps in their basis functions. For completeness, we also experimented with exponential learning rate decay (ELRD), which the basis functions in LCE are designed for. We trained 630 random nets with ELRD, from the 1000 MetaQNN-CIFAR10 nets. Predicting from 25% of the learning curve, the R 2 is 0.95 for ν-SVR, 0.48 for LCE (with extreme outlier removal, negative without), and 0.31 for BNN. This comparison illuminates another benefit of our method: we do not require handcrafted basis functions to model new learning curve types.

Moreover, SRMs are faster to train and do inference in than LCE and BNN. On 1 core of a Intel 6700k CPU, an ν-SVR with 100 training points trains in 0.006 seconds, and each inference takes 0.00006 seconds. In comparison, the LCE code takes 60 seconds and BNN code takes 0.024 seconds on the same hardware for each inference.

4. APPLYING PERFORMANCE PREDICTION FOR EARLY STOPPING:

To speed up hyperparameter optimization and architecture search methods, we develop an algorithm to determine whether to continue training a partially trained model configuration using our sequential regression models. This approach follows the idea proposed by Domhan et al. (2015) and further expanded on by Klein et al. (2017) We plot the performance of each method versus the percent of learning curve observed. For BNN and ν-SVR, we sample 10 different training sets, plot the mean R 2 , and shade the corresponding standard error. We compare our method against BNN (Klein et al., 2017) , LCE (Domhan et al., 2015) , and a "last seen value" heuristic (Li et al., 2017) . Absent results for a model indicate that it did not achieve a positive R 2 . The results for Cuda-Convnet on the SVHN dataset are shown in Appendix Figure 11 .

configurations, we begin by sampling and training n N configurations to create a training set S. We then train a model f (x f ), where in our case f is an SRM with T -1 individual models, to predict y T . Now, given the current best performance observed y BEST , we would like to terminate training a new configuration x NEW at iteration τ given its partial learning curve y NEW (τ ) if f (x NEW f ) = ŷT ≤ y BEST so as to not waste computational resources exploring a suboptimal configuration.

However, in the case f has poor out-of-sample generalization, we may mistakenly terminate the optimal configuration. If we assume that our estimate can be modeled as a Gaussian perturbation of the true value ŷT ∼ N (y T , σ(x, τ )), then we can find the probability p(ŷ T ≤ y BEST |σ(x, τ )) = Φ(y BEST ; y T , σ), where Φ(•; µ, σ) is the CDF of N (µ, σ). Note that in general the uncertainty will depend on both the configuration and τ , the number of points observed from the learning curve. Because frequentist models do not admit a natural estimate of uncertainty, we assume that σ is independent of x yet still dependent on τ and estimate it via Leave One Out Cross Validation (LOOCV). In addition, we show results using a Bayesian linear regression SRM, which has natural uncertainty estimates, removing the need for LOOCV. Now that we can estimate the model uncertainty, given a new configuration x NEW and an observed learning curve y NEW (τ ), we may set our termination criteria to be p(ŷ T ≤ y BEST ) ≥ ∆. ∆ balances the trade-off between increased speedups and risk of prematurely terminating good configurations. In many cases, one may want several configurations that are close to optimal, for the purpose of ensembling. We offer two modifications in this case. First, one may relax the termination criterion to p(ŷ T ≤ y BEST -δ) ≥ ∆, which will allow configurations within δ of optimal performance to complete training. One can alternatively set the criterion based on the n th best configuration observed, guaranteeing that with high probability the top n configurations will be fully trained. Baker et al. (2017) train a Q-learning agent to design convolutional neural networks. In this method, the agent samples architectures from a large, finite space by traversing a path from input layer to termination layer. However, the MetaQNN method uses 100 GPU-days to train 2700 neural architectures and the similar experiment by Zoph & Le (2017) utilized 10,000 GPU-days to train 12,800 models on CIFAR-10. The amount of computing resources required for these approaches makes them prohibitively expensive for large datasets (e.g., Imagenet) and larger search spaces. The main computational expense of reinforcement learning-based architecture search methods is training the neural network configuration to T epochs (where T is typically a large number at which the network stabilizes to peak accuracy).

4.1. EARLY STOPPING FOR ARCHITECTURE SEARCH:

We now detail the performance of ν-SVR and BLR SRMs in speeding up architecture search. First, we take 1,000 random models from the MetaQNN (Baker et al., 2017) search space. We simulate the MetaQNN algorithm by taking 10 random orderings of each set and running our early stopping algorithm. We compare against the LCE early stopping algorithm (Domhan et al., 2015) as a baseline, which has a similar probability threshold termination criterion. Our SRM trains off of the first 100 fully observed curves, while the LCE model trains from each individual partial curve and can begin early termination immediately. Despite this "burn in" time needed by an SRM, it is still able to outperform the LCE model (Figure 4 ). In addition, fitting the LCE model to a learning curve takes between 1-3 minutes on a modern CPU due to expensive MCMC sampling, and it is necessary to fit a new LCE model each time a new point on the learning curve is observed. However, the difference in computing time between the methods is not as important as the difference in prediction accuracies. We also plot the cumulative best, top 5, and top 15 performance to show that the agent continues to find better architectures.

We furthermore simulate early stopping for ResNets trained on CIFAR-10. We found that only the probability threshold ∆ = 0.99 resulted in recovering the top model consistently. However, even with such a conservative threshold, the search was sped up by a factor of 3.4 over the baseline. While we do not have the computational resources to run the full experiment from Zoph & Le (2017), our method could provide similar gains in large scale architecture searches.

It is not enough, however, to simply simulate the speedup because architecture search algorithms typically use the observed performance in order to update an acquisition function to inform future sampling. In the reinforcement learning setting, the performance is given to the agent as a reward, so we also empirically verify that substituting ŷT for y T does not cause the MetaQNN agent to converge to a subpar policy.

Replicating the MetaQNN experiment on CIFAR-10 (see Figure 5 ), we find that integrating early stopping with the Q-learning procedure does not disrupt learning and resulted in a speedup of 3.8x with ∆ = 0.99.

After training the top models to 300 epochs, we also 0 50000 100000150000200000250000300000350000

Total SGD Iterations find that the resulting performance (just under 93%) is on par with original results of Baker et al. (2017) .

4.2. EARLY STOPPING FOR HYPERPARAMETER OPTIMIZATION:

Recently, Li et al. (2017) introduced Hyperband, a random search technique based on multi-armed bandits that obtains state-of-the-art performance in hyperparameter optimization in a variety of settings. The Hyperband algorithm trains a population of models with different hyperparameter configurations and iteratively discards models below a certain percentile in performance among the population until the computational budget is exhausted or satisfactory results are obtained. Among previous work, Klein et al. (2017) have improved Hyperband by algorithmically choosing the next models to evaluate.

4.2.1. FAST HYPERBAND:

We present a Fast Hyperband (f-Hyperband) algorithm based on our early stopping scheme. During each iteration of successive halving, Hyperband trains n i configurations to r i epochs. In f-Hyperband, we train an SRM to predict y ri and do early stopping within each iteration of successive halving. We initialize f-Hyperband in exactly the same way as vanilla Hyperband, except once we have trained 100 models to r i iterations, we begin early stopping for all future successive halving iterations that train to r i iterations. By doing this, we exhibit no computational overhead over Hyperband other than training the SRMs, which we have shown to be cheap. We also introduce a parameter κ which denotes the proportion of the n i models in each iteration that must be trained to the full r i iterations. This is similar to setting the criterion based on the n th best model in the previous section. See Appendix section C for the full algorithmic representation of f-Hyperband.

We empirically evaluate f-Hyperband using Cuda-Convnet trained on CIFAR-10 and SVHN datasets. Figure 6 shows that f-Hyperband evaluates the same number of unique configurations as Hyperband within half the compute time, while achieving the same final accuracy within standard error. Moreover, when we run f-Hyperband for the same amount of time as Hyperband, f-Hyperband with a ν-SVR SRM outperforms f-Hyperband. When reinitializing hyperparameter searches, one can use previouslytrained set of SRMs to achieve even larger speedups. Figure 12 in Appendix shows that one can safely achieve up to a 4x speedup in such cases.

5. CONCLUSION:

In this paper we introduce a simple, fast, and accurate model for predicting future neural network performance using features derived from network architectures, hyperparameters, and time-series performance data. We show that the performance of drastically different network architectures can be jointly learned and predicted on both image classification and language models. Using our simple algorithm, we can speedup hyperparameter search techniques with complex acquisition functions, such as a Q-learning agent, by a factor of 3x to 6x and Hyperband-a state-of-the-art hyperparameter search method-by a factor of 2x, without disturbing the search procedure. We outperform all competing methods for performance prediction in terms of accuracy, train and test time, and speedups obtained on hyperparameter search methods. We hope that the simplicity and success of our method will allow it to be easily incorporated into current hyperparameter optimization pipelines for deep neural networks. With the advent of large scale automated architecture search (Baker et al., 2017; Zoph & Le, 2017) , methods such as ours will be vital in exploring even larger and more complex search spaces.

APPENDIX A DATASETS AND ARCHITECTURES:

Deep Resnets (TinyImageNet): We sample 500 ResNet architectures and train them on the TinyIm-ageNet † dataset (containing 200 classes with 500 training images of 32 × 32 pixels) for 140 epochs. We vary depths, filter sizes and number of convolutional filter block outputs. Filter sizes are sampled from {3, 5, 7} and number of filters is sampled from {2, 3, 4, ..., 22}. Each ResNet block is composed of three convolutional layers followed by batch normalization and summation layers. We vary the number of blocks from 2 to 18, giving us networks with depths varying between 14 and 110. Each network is trained for 140 epochs, using Nesterov optimizer. The learning rate is set to 0.1 and learning rate reduction and momentum are set to 0.1 and 0.9 respectively.

Deep Resnets (CIFAR-10)::

We sample 500 39-layer ResNet architectures from a search space similar to Zoph & Le (2017) , varying kernel width, kernel height, and number of kernels. We train these models for 50 epochs on CIFAR-10. Each architecture consists of 39 layers: 12 conv, a 2x2 max pool, 9 conv, a 2x2 max pool, 15 conv, and softmax. Each conv layer is followed by batch normalization and a ReLU nonlinearity. Each block of 3 conv layers are densely connected via residual connections and also share the same kernel width, kernel height, and number of learnable kernels. Kernel height and width are independently sampled from {1, 3, 5, 7} and number of kernels is sampled from {6, 12, 24, 36}. Finally, we randomly sample residual connections between each block of conv layers. Each network is trained for 50 epochs using the RMSProp optimizer, with weight decay 10 -4 , initial learning rate 0.001, and a learning rate reduction to 10 -5 at epoch 30 on the CIFAR-10 dataset.

We sample 1,000 model architectures from the search space detailed by Baker et al. (2017) , which allows for varying the numbers and orderings of convolution, pooling, and fully connected layers. The models are between 1 and 12 layers for the SVHN experiment and between 1 and 18 layers for the CIFAR-10 experiment. Each architecture is trained on SVHN and CIFAR-10 datasets for 20 epochs. 

Pooling (P) i ∼ Layer depth (f, ) ∼ (Receptive field size, Strides) n ∼ Representation size < 12 Square. ∈ (5, 3), (3, 2), (2, 2) ∈ {(∞, 8], (8, 4] and (4, 1]} Fully Connected (FC) i ∼ Layer depth n ∼ # consecutive FC layers d ∼ # neurons < 12 < 3 ∈ {512, 256, 128} Termination State s ∼ Previous State t ∼ Type Global Avg. Pooling/Softmax

Table 3 : Experimental State Space For MetaQNN. For each layer type, we list the relevant parameters and the values each parameter is allowed to take. The networks are sampled beginning from the starting layer. Convolutional layers are allowed to transition to any other layer. Pooling layers are allowed to transition to any layer other than pooling layers. Fully connected layers are only allowed to transition to fully connected or softmax layers. A convolutional or pooling layer may only go to a fully connected layer if the current image representation size is below 8. We use this space to both randomly sample and simulate the behavior of a MetaQNN run as well as directly run the MetaQNN with early stopping.

We sample 300 LSTM models and train them on the Penn Treebank dataset for 60 epochs. Number of hidden layer inputs and lstm cells was varied from 10 to 1400 in steps of 20. Each network was trained for 60 epochs with batch size of 50 and trained the models using stochastic Klein et al. (2017) , it is possible to use our simple models as an acquisition function for Hyperband. As shown in Table 2 , our models have reasonable performance with only AP and HP features used, meaning we can use these models to rank hyperparameter settings before training the configurations. In particular, for each Hyperband iteration, we randomly select 10,000 configurations, weight them by their predicted performance and sample from this weighted distribution. In Figure 7 , we compare f-Hyperband with this ν-SVR acquisition function to f-Hyperband with the standard uniform acquisition function and also to vanilla Hyperband. It seems that the acquisition function could help slightly, but it does not improve performance across all experiments, and where it does improve performance it does so only slightly. We compare f-Hyperband with an SVR acquisition function to f-Hyperband with the uniform acquisition function (this is the standard version described in the main text) and to vanilla Hyperband. The results shown are inconclusive; it seems that there could be some benefit of incorporating the SVR acquisition function, but it isn't significant enough to make a strong statement.

s max = log η (R) B = (s max + 1)R 1 for s ∈ {s max , . . . , 0} do 2 n = B R η s s+1 , r = Rη -s 3 // begin SUCCESSIVEHALVING with (n, r) inner loop 4 T = get_hyperparameter_configuration(n) 5 for i ∈ {0, . . . , s} do 6 n i = nη -i , r i = rη i 7 n next = ni η if i! = s else 1 8 L = run_then_return_validation_loss(T, r i , n next , D, M ) 9 T = top_k(T,

: L = [] 1 for t ∈ T do 2 = [] 3 for i ∈ {0, . . . , r -1} do 4 i = run_one_epoch_return_validation_loss(t) 5 .append( i ) 6 if M [r][i].trained() then 7 ŷr , σ = M [r][i].predict( ) 8 if Φ(max_k(L, κn) -δ; ŷr , σ) ≥ ∆ then

E GAUSSIAN ERROR ASSUMPTION:

In order to have uncertainty estimates with frequentist models, we estimated the mean and variance of the error from leave-one-out cross validation and assumed that the error was Gaussian. In Figure 8 we compare example error distributions between training and validation from a ν-SVR SRM. Visually one can see that the assumption holds very well for both visual classification tasks and holds slightly less well for the language modeling task. In Figure 9 , we show the mean log likelihood of held out prediction errors being drawn from a Gaussian parameterized by the mean and variance of the error on the training set is very close to the mean log likelihood of samples drawn from the same distribution, which shows that our Gaussian error assumption is relatively strong.

F ANALYZING IMPORTANCE OF FEATURES IN THE PREDICTION MODEL:

We used a linear ν-SVR model to compare the weights of all features, which are normalized before training. Figure 10 shows the weight trends for time-series features, and Tables 5, 6 , and 7 compare weights of some architecture features and hyperparameter features to statistics of time-series features for the MetaQNN (CIFAR-10), LSTMs (Penn Treebank), and Deep Resnets (TinyImagenet) experiments, respectively. We found the following main insights across datasets:

• The time-series (TS) features are on average have higher weights than HP and AP features (which is confirmed by our ablation studies in Table 2 as well). The original validation accuracies (y t ) have higher weights on average than the first-order differences (y t ) and second-order differences (y t ).

• In general, later epochs in y t have higher weights. In other words, the latest performance of the model available for prediction is much more important for performance prediction than initial 

G ADDITIONAL PLOTS:

Figure 11 shows the performance prediction results for the Cuda Convnet SVHN experiment. The instability of BLR with low percentage of learning curve observed may be what caused suboptimal performance of BLR f-Hyperband shown in Figure 6 . Figure 12 shows the relative speedup of f-Hyperband over vanilla Hyperband for each consecutive iteration of Hyperband. However, Figure 13 , which shows results for f-Hyperband with pretrained ν-SVR SRMs, shows that more aggressive settings of f-Hyperband result in suboptimal performance. We see that we can safely get a 3-4x speedup over vanilla Hyperband with pretrained SRMs.

0%:

20% 40% 60% 80% 100% For BNN, ν-SVR, and BLR we sample 10 different training sets, plot the mean R 2 , and shade the corresponding standard error. We compare our method against BNN (Klein et al., 2017) , LCE (Domhan et al., 2015) , and a "last seen value" heuristic (Li et al., 2017) . Absent results for a model indicate that it did not achieve a positive R 2 . 

:

* https://tiny-imagenet.herokuapp.com/

† https://tiny-imagenet.herokuapp.com/

Figures and Tables:

Figure 2: Predicted vs True Values of Final Performance: We show the shape of the predictive distribution on three experiments: MetaQNN models, Deep Resnets, and LSTMs. Each ν-SVR model is trained with 100 configurations with data from 25% of the learning curve. We predict validation set classification accuracy for MetaQNN and Deep ResNets, and perplexity for LSTMs.

Figure3: Performance Prediction Results: We plot the performance of each method versus the percent of learning curve observed. For BNN and ν-SVR, we sample 10 different training sets, plot the mean R 2 , and shade the corresponding standard error. We compare our method against BNN(Klein et al., 2017), LCE(Domhan et al., 2015), and a "last seen value" heuristic(Li et al., 2017). Absent results for a model indicate that it did not achieve a positive R 2 . The results for Cuda-Convnet on the SVHN dataset are shown in Appendix Figure11.

Figure4: Simulated Speedup in MetaQNN Search Space: We compare the three variants of the early stopping algorithm presented in Section 4 for both a ν-SVR and BLR SRM. Each SRM is trained using the first 100 learning curves, and each algorithm is tested on 10 independent orderings of the model configurations. Triangles indicate an algorithm that successfully recovered the optimal model for more than half of the 10 orderings, and X's indicate those that did not.

Figure 5: MetaQNN on CIFAR-10 with Early Stopping: A full run of the MetaQNN algorithm(Baker et al., 2017) on the CIFAR-10 dataset with early stopping. We use the ν-SVR SRM with a probability threshold ∆ = 0.99. Light blue bars indicate the average model accuracy per decrease in , which represents the shift to a more greedy policy. We also plot the cumulative best, top 5, and top 15 performance to show that the agent continues to find better architectures.

Figure 6: Simulated Max Accuracy vs SGD Iterations for Hyperband: We show the trajectories of the maximum performance so far versus total computational resources used for 40 consecutive Hyperband runs with η = 4.0 and ∆ = 0.95. Small vertical lines indicate the point at which each f-Hyperband run has searched over the same number of models as vanilla Hyperband. On Cifar-10, both BLR and ν-SVR f-Hyperbands outperform vanilla Hyperband, but on SVHN only ν-SVR f-Hyperbands do. Each triangle marks the completion of full Hyperband algorithm.

models to train) initialize :D = dict() M = dict()

D[r][0]) < d and length( ) == r then 18 {D[r][i].append({ [0, . . . , i], [r]}): i ∈ {0, . . . , r -1}} 19 if notM [r][i].trained() then 20 M [r][i].train(D[r][i])

Figure7: f-Hyperband with SVR Acquisition Function: We compare f-Hyperband with an SVR acquisition function to f-Hyperband with the uniform acquisition function (this is the standard version described in the main text) and to vanilla Hyperband. The results shown are inconclusive; it seems that there could be some benefit of incorporating the SVR acquisition function, but it isn't significant enough to make a strong statement.

Figure11: Cuda Convnet SVHN Performance Prediction Results: We plot the performance of each method versus the percent of learning curve observed for the Cuda Convnet SVHN experiment. For BNN, ν-SVR, and BLR we sample 10 different training sets, plot the mean R 2 , and shade the corresponding standard error. We compare our method against BNN(Klein et al., 2017), LCE(Domhan et al., 2015), and a "last seen value" heuristic(Li et al., 2017). Absent results for a model indicate that it did not achieve a positive R 2 .

Figure 12: Simulated Speedup on Hyperband vs Hyperband Iteration: We show the speedup using the f-Hyperband algorithm over Hyperband on 40 consecutive runs with η = 4.0 and ∆ = 0.95.The major jump in speedup comes at iteration 10, where we have trained more than 100 models to the full R iterations.

Figure13: Simulated f-Hyperband with Pretrained SRMs: Each f-Hyperband model is initialized with a pretrained SRM, which simulates the case where one reinitializes an experiment. Every triangle indicates a full run of Hyperband, and small vertical lines indicate the point at which the f-Hyperband runs have completed the same number of full Hyperband runs as shown for vanilla Hyperband. Top 1 indicates only training the best model to r i iterations, and δ represents an offset off the threshold used for early stopping (See Section 4).More aggressive f-Hyperband settings lead to suboptimal performance, indicating that there is a limit to how much speedup f-Hyperband can achieve.

Performance Prediction Model Comparison: We report the coefficient of determination R 2 * 100 for four standard methods. Each model is trained with 100 samples on 25% of the learning curve. We find that ν-SVR works best on average, though not by a large margin.

Table content: <table><tr><td colspan="2">Dataset</td><td colspan="2">ν-SVR</td><td>OLS</td><td>BLR</td><td>RF</td></tr><tr><td colspan="5">MetaQNN (CIFAR-10) 97.22 ± 0.31 97.04 ± 0.42</td><td colspan="2">97.11 ± 0.32 94.50 ± 0.78</td></tr><tr><td colspan="5">Resnet (TinyImageNet) 87.12 ± 4.65 88.41 ± 3.76</td><td colspan="2">82.40 ± 1.65 86.39 ± 3.58</td></tr><tr><td colspan="7">LSTM (Penn Treebank) 98.03 ± 1.46 87.83 ± 21.53 97.99 ± 1.90 57.28 ± 24.98</td></tr><tr><td/><td colspan="2">MetaQNN CNNs -CIFAR10</td><td colspan="3">Deep ResNets -TinyImagenet</td><td>LSTMs -Penn Treebank</td></tr><tr><td>Predicted Performance</td><td>0.2 0.3 0.4 0.5 0.6 0.7 0.8</td><td>0.2 True Performance 0.4 0.6 0.8 R 2 = 0.969</td><td>0.0 0.1 0.2 0.3 0.4 0.5</td><td>0.2 0.3 0.4 0.5 True Performance R 2 = 0.902</td><td colspan="2">80 True Performance 100 110 R 2 = 0.973 70 80 90 100</td></tr></table>

Ablation Study on Feature Sets: We report the R 2 * 100 metric for different combinations of features. Time-series features (TS) refers to the partially observed learning curves, architecture parameters (AP) refer to the number of layers and number of weights in a deep model, and hyperparameters (HP) refer to the optimization parameters such as learning rate. All results are with ν-SVR.

Table content: <table><tr><td>Feature Set</td><td>MetaQNN</td><td>ResNets</td><td>LSTM</td><td>Cuda-Convnet</td></tr><tr><td/><td>(CIFAR-10)</td><td colspan="3">(TinyImageNet) (Penn Treebank) (CIFAR-10)</td></tr><tr><td>HP</td><td colspan="2">-2.96 ± 2.71 0.48 ± 7.24</td><td>-1.72 ± 1.62</td><td>0.48 ± 7.24</td></tr><tr><td>AP</td><td>15.38 ± 4.66</td><td>67.66 ± 9.08</td><td>13.76 ± 12.08</td><td>67.66 ± 9.08</td></tr><tr><td>TS</td><td>97.00 ± 0.52</td><td>82.71 ± 4.31</td><td>97.38 ± 1.49</td><td>82.71 ± 4.31</td></tr><tr><td>AP+HP</td><td>14.89 ± 5.12</td><td>70.25 ± 6.42</td><td>13.76 ± 12.08</td><td>70.25 ± 6.42</td></tr><tr><td>TS+HP</td><td>97.02 ± 0.52</td><td>82.67 ± 6.81</td><td>97.38 ± 1.49</td><td>82.67 ± 6.81</td></tr><tr><td>TS+AP</td><td>97.12 ± 0.37</td><td>87.36 ± 4.23</td><td>97.87 ± 1.68</td><td>87.36 ± 4.23</td></tr><tr><td colspan="2">TS+AP+HP 97.15 ± 0.48</td><td>86.05 ± 8.24</td><td>97.87 ± 1.68</td><td>86.05 ± 8.24</td></tr></table>

Table 3 displays the state space of the MetaQNN algorithm.

Table content: <table><tr><td>Layer Type</td><td>Layer Parameters</td><td>Parameter Values</td></tr><tr><td/><td>i ∼ Layer depth</td><td>&lt; 12</td></tr><tr><td/><td>f ∼ Receptive field size</td><td>Square. ∈ {1, 3, 5}</td></tr><tr><td>Convolution (C)</td><td>∼ Stride</td><td>Square. Always equal to 1</td></tr><tr><td/><td>d ∼ # receptive fields</td><td>∈ {64, 128, 256, 512}</td></tr><tr><td/><td>n ∼ Representation size</td><td>∈ {(∞, 8], (8, 4], (4, 1]}</td></tr></table>

• Among AP and HP features, the total number of parameters and depth have non-zero weight for the CNNs, and they are assigned weights comparable or higher than late epoch accuracies (y t ). However, they have much lower weight in the LSTM experiment. The number of filters in each convolutional layer also has a high positive weight for CNNs. In general, architectural features are much more important for CNNs as compared to LSTMs. Hyperparameters like initial learning rate and step size were generally not as important as the architectural features, which is corroborated by the ablation study in Table1in the main text. Time Series Weights: We show the trends for weights for time-series features, along with first-and second-order differences. Summary of weights for a linear kernel ν-SVR SRM trained on configurations from MetaQNN (CIFAR-10).

Table content: <table><tr><td/><td>0.025</td><td>MetaQNN Cifar-10</td><td>6 LSTM Penn Treebank</td><td colspan="4">0.010 Deep Resnets Tiny Imagenet</td></tr><tr><td>Raw Performance Weights</td><td>0.005 0.010 0.015 0.020</td><td/><td>0 1 2 3 4 5</td><td>0.004 0.002 0.000 0.002 0.004 0.006 0.008</td><td/><td/></tr><tr><td/><td colspan="2">0% 10%20%30%40%50%60%70%80%90% 0.000</td><td>0% 10%20%30%40%50%60%70%80%90% 1</td><td colspan="4">0% 10%20%30%40%50%60%70%80%90% 0.006</td></tr><tr><td/><td>0.030</td><td/><td>8</td><td>0.006</td><td/><td/></tr><tr><td>First Order Diffs Weights</td><td>0.005 0.010 0.015 0.020 0.025</td><td/><td>0 1 2 3 4 5 6 7</td><td>0.002 0.001 0.000 0.001 0.002 0.003 0.004 0.005</td><td/><td/></tr><tr><td/><td colspan="2">0% 10%20%30%40%50%60%70%80%90% 0.000</td><td>0% 10%20%30%40%50%60%70%80%90% 1</td><td colspan="4">0% 10%20%30%40%50%60%70%80%90% 0.003</td></tr><tr><td>Second Order Diffs Weights</td><td>0.000 0.005 0.010 0.015</td><td/><td>0.5 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5</td><td>0.003 0.002 0.001 0.000 0.001 0.002 0.003 0.004</td><td>10% 20% 30%</td><td>40% 50% 60%</td><td>70% 80% 90%</td></tr><tr><td/><td colspan="2">0% 10%20%30%40%50%60%70%80%90% Percent Learning Curve Observed 0.005</td><td>0% 10%20%30%40%50%60%70%80%90% Percent Learning Curve Observed 1.0</td><td colspan="4">Percent Learning Curve Observed 0% 10%20%30%40%50%60%70%80%90% 0.004</td></tr><tr><td colspan="2">Figure 10:</td><td/><td/><td/><td/><td/></tr></table>

Summary of weights for a linear kernel ν-SVR SRM trained on configurations from LSTMs (Penn Treebank).

Table content: <table><tr><td>Percent</td><td>Mean</td><td>Std Dev</td><td>Mean 1st</td><td colspan="2">Mean 2nd Depth</td><td># Params</td><td>Kernel</td></tr><tr><td colspan="2">Observed Perf</td><td>Perf</td><td colspan="2">Order Diff Order Diff</td><td/><td/><td>Size</td></tr><tr><td>10</td><td colspan="3">0.008486 0.008576 0.001861</td><td>0.001502</td><td colspan="2">0.005985 0.010987</td><td>0.000267</td></tr><tr><td>20</td><td colspan="3">0.004723 0.004851 0.001092</td><td>0.000996</td><td colspan="2">0.001709 0.005239</td><td>0.002484</td></tr><tr><td>30</td><td colspan="3">0.003229 0.002848 0.000789</td><td>0.000619</td><td colspan="2">0.004533 0.002553</td><td>-0.001138</td></tr><tr><td>40</td><td colspan="3">0.002394 0.002985 0.000660</td><td>0.000557</td><td colspan="2">0.003443 0.001092</td><td>-0.000302</td></tr><tr><td>50</td><td colspan="3">0.001754 0.001993 0.000461</td><td>0.000396</td><td colspan="2">0.001318 0.001081</td><td>0.000072</td></tr><tr><td>60</td><td colspan="3">0.001456 0.001946 0.000370</td><td>0.000309</td><td colspan="2">0.000968 0.000559</td><td>0.000036</td></tr><tr><td>70</td><td colspan="3">0.001428 0.002678 0.000499</td><td>0.000344</td><td colspan="3">0.001161 -0.000590 -0.000971</td></tr><tr><td>80</td><td colspan="3">0.001168 0.001895 0.000352</td><td>0.000256</td><td colspan="2">0.000455 0.000131</td><td>-0.001092</td></tr><tr><td>90</td><td colspan="3">0.001015 0.001640 0.000285</td><td>0.000215</td><td colspan="3">0.000208 -0.000091 -0.000958</td></tr></table>

Summary of weights for a linear kernel ν-SVR SRM trained on configurations from Deep Resnets (TinyImagenet).

Table content: <table/>

shows that SRMs are relatively robust when training below or above the median of a specific architecture or training hyperparameter and testing on the other split.

Table content: <table><tr><td colspan="4">Cuda Convnet (CIFAR-10) Learning Rate WeightDecay LRN Scale</td><td>LRN Power</td></tr><tr><td>Test &lt; Median</td><td>93.06 ± 0.18</td><td colspan="3">95.93 ± 0.21 97.27 ± 0.0068 96.96 ± 0.13</td></tr><tr><td>Test &gt; Median</td><td>81.97 ± 1.26</td><td colspan="3">96.19 ± 0.13 93.37 ± 0.23</td><td>95.05 ± 0.19</td></tr><tr><td colspan="4">LSTMs (Penn Treebank) Number of Nodes Depth</td></tr><tr><td>Test &lt; Median</td><td/><td>98.08 ± 0.26</td><td colspan="2">98.58 ± 0.04</td></tr><tr><td>Test &gt; Median</td><td/><td>22.83 ± 5.55</td><td colspan="2">96.96 ± 0.91</td></tr><tr><td colspan="2">Deep Resnets (TinyImagenet) Depth</td><td colspan="3">Number of Kernels Kernel Size</td></tr><tr><td>Test &lt; Median</td><td colspan="3">89.49 ± 1.84 85.12 ± 2.24</td><td>81.83 ± 0.59</td></tr><tr><td>Test &gt; Median</td><td colspan="3">85.92 ± 1.78 62.37 ± 0.82</td><td>89.61 ± 0.31</td></tr><tr><td colspan="3">MetaQNN (CIFAR-10) Depth</td><td/></tr><tr><td colspan="2">Test &lt; Median</td><td colspan="2">96.69 ± 0.16</td></tr><tr><td colspan="2">Test &gt; Median</td><td colspan="2">79.31 ± 5.66</td></tr></table>

Accuracy when splitting test and train set based on median values for hyperparameters for different datasets.

Table content: <table/>

Peer review (iclr2018):
 This paper explores the use of simple models for predicting the final validation performance of a neural network, from intermediate values during training. It uses support vector regression to show that a relatively small number of samples of hyperparameters, architectures, and validation time series can lead to reasonable predictions of eventual performance. The paper performs a modest evaluation of such simple models and shows surprisingly good r-squared values. The resulting simple prediction framework is then used for early stopping, in particular within the Hyperband hyperparameter search algorithm. There*s a lot that I like about this paper, in particular the ablation study to examine which pieces matter, and the evaluation of a couple of simple models. Ultimately, however, I felt like the paper was somewhat unsatisfying as it left open a large number of obvious questions and comparisons: - The use of the time series is the main novelty. In the AP, HP and AP+HP cases of Table 2, it is essentially the same predictive setup of SMAC, BO, and other approaches that are trying to model the map from these choices to out-of-sample performance. Doesn*t the good performance without TS on, e.g., ResNets in Table 2 imply that the Deep ResNets subfigure in Figure 3 should start out at 80+? - In light of the time series aspect being the main contribution, a really obvious question is: what does it learn about the time series? The linear models do very well, which means it should be possible to look at the magnitude of the weights. Are there any surprising long-range dependencies? The fact that LastSeenValue doesn*t do as well as a linear model on TS alone would seem to indicate that there are higher order autoregressive coefficients. That*s surprising and the kind of thing that a scientific investigation here should try to uncover; it*s a shame to just put up a table of numbers and not offer any analysis of why this works. - In Table 1 the linear SVM uniformly outperforms the RBF SVM, so why use the RBF version? - Given that the paper seeks to use uncertainty in estimates and the entire regression setup could be trivially made Bayesian with no significant computational cost over a kernelized SVM or OLS, especially if you*re doing LOOCV to estimate uncertainty in the frequentist models. Why not include Bayesian linear regression and Gaussian process regression as baselines? - Since the model gets information from the AP and HP before doing any iterations, why not go on and use that to help select candidates? - I don*t understand how speedup is being computed in Figure 4. - I*d like a more explicit accounting of whether 0.00006 seconds vs 0.024 seconds is something we should care about in this kind of work, when the steps can take minutes or hours on a GPU. - How useful is r-squared as a measure of performance in this setting? My experience has been that most of the search space has very poor performance and the objective is to find the small regions that work well. Minor things: - y* (prime) gets overloaded in Section 3.1 as a derivative and then in Section 4 as a partial learning curve. - "... is more computationally and ..." - "... our results for performing final ..."