Model-based Asynchronous Hyperparameter and Neural Architecture Search
Authors: Aaron Klein
Louis Chi-Chun Tiao
Thibaut Lienart
Cedric Archambeau
Matthias Seeger
Venue:  (2021)
Keywords: Bayesian Optimization
AutoML
Hyperparameter Optimization
Neural Architecture Search

Abstract: We introduce a model-based asynchronous multi-fidelity method for hyperparameter and neural architecture search that combines the strengths of asynchronous Successive Halving and Gaussian process-based Bayesian optimization. At the heart of our method is a probabilistic model that can simultaneously reason across hyperparameters and resource levels, and supports decision-making in the presence of pending evaluations. We demonstrate the effectiveness of our method on a wide range of challenging benchmarks, for tabular data, image classification and language modelling, and report substantial speed-ups over current state-of-the-art methods. Our new methods, along with asynchronous baselines, are implemented in a distributed framework which will be open sourced along with this publication.

Under review as a conference paper at ICLR 2021
MODEL-BASED ASYNCHRONOUS HYPERPARAMETER AND NEURAL ARCHITECTURE SEARCH
Anonymous authors Paper under double-blind review
ABSTRACT
We introduce an asynchronous multi-fidelity method for model-based hyperparame- and neural architecture search that combines the strengths of asynchronous Suc- cessive Halving and Gaussian process- Bayesian optimization. Our method relies on probabilistic model that can simultaneously reason across hyperparame- ters and resource levels, and supports decision- makion in the presence of pending evaluations. We demonstrate the effectiveness of our method on wide range challenging benchmarks, for tabular data, image classification and language mod- elling, and report substantial speed-ups over current state-of-the-art methods. Our new method, along with asynchronous baselines, are implemented in distributed framework which will be open sourced along with this publication.
INTRODUCTION
The goal of hyperparameter and neural architecture search (HNAS) is to automate the process of finding the right architecture or hyperparameters x, E arg min J [ax of a deep neural network by minimizing the validation loss f()), observed through noise: 3/s = f(x; + G4 4 ~N (
I. n. Bayesian optimization (BO) is effective model-based approach for solving expensive black-box optimization problems (Jones et al. 1998 (Shahriari et al. (2016). It constructs a probabilis- tic surrogate model of the loss function p(J D) based on previous evaluations D { )=)) Searching for the global minimum of f is then driven by trading off exploration in regions of uncer- tainty and exploitation in regions where the global optimum is likely reside. However, for HNAS problems, standard BO needs to be augmented in order to remain competitive. For example, training runs for unpromising configurations æ can be stopped early, but serve as low-fidelity approximations of f (ax (Swersky et al. 2014| Domhan et al. 2015 Klein et al. 2017b). Further, evaluations of can be executed in parallel to reduce the wall-clock time required for finding good solution. Several methods for multi-fidelity and/or distributed BO have been proposed (Kandasamy et al. 2017 2016
Takeno et al. 2020), but they rely on rather complicated approximations to either select the fidelity level or to compute information theoretic acquisition function to determine the next candidate. In this work we aim to adopt the desiderata of Falkner et al. (201). namely, that of simplicity, which often leads more robust methods in practice.
A simple, easily parallelizable cultii-iideityy scheduling algorithm is successive halving (SH) (Karnin al. 20133] Jamieson & Talwalkar (0166). which iteratively eliminates poorly performing neural networks over time. Hyperband (Li et al. 2017) iterates over multiple rounds of SH with varying ratios between the number of configurations and the minimum amount of resources spent per configuration. Falkner et al. (2018) introduced a hybrid model, called BOHB, that uses a probabilistic model to guide the search while retaining the efficient any-time performance of Hyperband. However, both SH and BOHB can be bottlenecked due to their synchronous nature: stopping decisions are done only after synchronizing all training jobs at certain resource levels (called rungs). This approach is wasteful when the evaluation of some configuration take longer than others, it is often the case when training neural networks (Ying et al. 2019), and can substantially delay progress towards high-performing configurations (see example shown in Figure I).
Recently, Li et al. (0188) proposed ASHA, which adapts successive halving to the asynchronous parallel case. Even though ASHA only relies the random sampling of new configurations, it has been shown to outperform synchronous SH and BOHB. In this work, we augment ASHA with a Gaussian process (GP) surrogate, which jointly models the performance across configurations and

---

Under review as a conference paper at ICLR 2021
Figure 1: Evolution of synchronous (left) and asynchronous (right) SH for optimization the hy- perparameters of MLP. æ-axis: wall-clock time (150 secs), y-axis: training epochs done (log scale). Coloured lines trace training jobs for HP configurations, with marker size proportional to validation error (smaller is better). Lines reaching the maximum number of authorized epochs (27) are stopped early. For synchronous SH, rungs (epochs 1, 3, 9) need to be filled completely before any configuration can promoted, and each synchronization results in some idle time. In asychronous SH, configurations proceed to higher epochs faster. Without synchronization overhead, more configurations are promoted to the highest rung in the same wall-clock time (figure best seen in colours).
rungs to improve the already strong performance of ASHA. The asynchronous nature further requires handle pending evaluations in principled way to obtain efficient model-based searcher.
1.1 CONTRIBUTIONS
Dealing with hyperparameter optimization (HPO) in general, and HNAS for neural networks in particular, we would like to make the most efficient use of given parallel computation budget (e.g.. number of compute instances) in order find high-accuracy solutions in the shortest wall-clock time possible. Besides exploiting low-fidelity approximations, scheduling is decisive factor in cost-efficient search. We further handle pending evaluations through fantasizing (Snoek et al. 2012), which is critical for asynchronous searchers. Our novel combination of asynchronous SH with culti--ideeity BO, dubbed MOdel Based aSynchronous mulTi fidelity optimizER (MoBSTER) substantially outperforms either of them in isolation. More specifically:
demonstrate that asynchronous parallel
We clarify differences between existing asynchronous SH extensions: ASHA, as described by Li et al. (2018) and an arguably simpler stopping rule variant, related to the median rule (Golovin al. (017) and first implemented Ray Tune (Liaw et al. 2018). Although their difference seem subtle, they lead to substantially different behaviour in practice.
We present an extensive ablation study, comparing and analysing different components for asynchronous HNAS. While these individual components are not novel, one of our main contributions is to show that, by systematically combining them to form MORS we obtain reliable and more efficient method than other recently proposed approaches. Due to limited space, we present detailed description of the technical nuances and complexities of model-based asynchronous multi-fidel multi-fidelity HNAS in Appendix A.3
On variety of neural network benchmarks, show that MOBSTER is efficient in terms wall-clock time than other state-of-the-art algorithms. Unlike BOHB, it does not suffer from substantial synchronization overheads when evaluations are expensive. As result, we can achieve the same performance in the same amount of wall-clock time but with often just half the computational resources compared random- saamliing based ASHA.
Next, we relate our work to approaches recently published in the literature. Section we review synchronous SH, as well two asynchronous extensions. Our novel method is presented Section 3 We present empirical evaluations for the HNAS of various neural architecture types in Section and finish with conclusions and future work in Section 5
2

---

Under review as a conference paper at ICLR 2021
1.2 RELATED WORK
range of prior Gaussian process (GP) based BO work exploits multiple fidelities of the objec-
tive (Kennedy & O' H'Hagan 2000; Klein et al., 2017a; Poloczek et al. 20188: Cutajar et al. 2018).
joint GP model across configurations and tasks was used by [Swessky
(2013), allowing
for trade-offs between cheap auxiliaries and the expensive target. Klein et al. (201 7a) presented
continuous multi-fidelity BO method, where training set size is an input. It relies on a complicated
and expensive acquisition function, and experiments with asynchronous scheduling are not provided.
Kandasamy et al. (2017) presented BOCA, a Bayesian optimization method that exploits general continuous fidelities of the objective function. While BOCA uses model similar to ours, they employ a different strategy to select the fidelity, which appears to work less efficiently in practice, as we show in our experiments. The "freeze-thaw" approach (Swersky et al.) (2014) allows for asynchronous parallel evaluations, yet its scheduling is quite different from asynchronous SH. They propose an exponential decay kernel, refinement of which we use here. No results for deep neural network tuning were presented, and no implementation is publicly available. Previous work on asynchronous BO has demonstrated performance gains over synchronous BO methods (Alvin et al.. 2019; Kandasamy et al.) 2016), yet this work did not exploit multiple fidelities of the objective. Concurrently to our work. Takeno et al. (2020) proposed an asynchronous multi-fidelit BO method. However, it is based on an information- theorretc acquisition function that is substantially more complex than our method. Since no implementation is publicly available omitted from our comparisons.
Falkner et al. (2018) combine synchronous Hyperband with TPE (Bergstra et al., 2011 as model. Their method, called BOHB, combines early speed-ups of Hyperband with fast convergence later on, and shows competitive performance for NAS (Ying et al. 2019 Dong & Yang 2020). However, compared to our approach, it fits independent kernel density estimator at each rung level, which prevents the interpolation to higher rung levels. Apart from this, kernel density estimators do not permit fantasizing the potential outcome of a pending configuration, which makes it unclear how to extend BOHB to the asynchronous setting, and are notoriously sensitive to their bandwidth parameters.
2 SYNCHRONOUS AND ASYNCHRONOUS MULTI-FIDELITY SCHEDULING
Multi-fidelity HNAS considers an objective f(xx, r), indexed by the resource level r E [Tmin...., Tmax J. The target function of interest is f(x) f(x while evaluations of f(x, r) for r < Tmax are cheaper, nower-fidelity evaluations that may be correlated with f(æ). Here, we consider the number of training epochs (i.e., full sweeps over the data) as the resource r, though other choices are possible, such as training subset ratios (Klein et al. 2017a).
Two kinds of decisions made in multi- fultiifidelity HNAS: choosing the configurations to evaluate and scheduling their evaluations. In this work, configurations are chosen non-uniformly based on the GP surrogate model that accounts for pending and actual evaluations. Scheduling decisions are stop/go decisions that happen at certain resource levels called rungs. We make use of successive halving (SH) for its simplicity and strong empirical performance (Jamieson & Talwalkar 2016 Li al. 2018 Let E {2, 3, 4} be the halving constant, 7 Timx and Tiin the maximum and minimum resource level for an evaluation. We assume, for simplicity, that Tmax/ /'in = , where K E N. The full set of rungs is R = (riin k = O. K). In the sequel, the term "rung" will be overloaded, denoting both the resource level at which stop/go decisions are made and the list of configurations that reached it.
In synchronous SH, each rung has an a priori fixed size (i.e., number of slots for configurations evaluated until the rung level), the size ratio between successive rungs being 7 (e.g., (r) = /imx/r for R). A round of the algorithm starts with evaluating r((min) configurations to the lowest rung r = Tmin, making use of parallel computation available. Once all of them finish, the v7 fraction of top performing configuratio configurations rung is a synchronization point for many training tasks: has to be populated entirely before any configuration can be promoted (see Figure T left for visualization).
promoted to the next rung while the others are terminated. Each
Synchronous scheduling makes less efficient use of parallel computation than asynchronous schedul- ing. Configurations in the same rung may require quite different compute times, for example, if we
3

---

Under review as a conference paper at ICLR 2021
search over hyperparameters that control the network size. Hence, some workers may just be idle at synchronization point. Evaluations at larger resource levels are observed earlier with asynchronous scheduling. However, the risk is to continue mediocre configurations because they were selected earlier. Figure ToureeTillan Dillsstrates the differences between asynchronous and synchronous scheduling.
We distinguish two variants of asynchronous SH proposed in prior work. During the optimization process, for any hyperparameter and architecture configuration æ E X' that is currently being evaluated, a decision needs to be made once it reaches the next rung r R. Given the new observed data point y at level r. the binary predicate cont inue (2r, r, y) evaluates to true iff y is in the top 17 fraction of records at the rung.
This is a simple extension of the median stopping rule (Golovin et al. 2017). which is implemented in Ray Tune (Liaw et al. 2018). As soon as a job for reaches a rung r, cent i in (ar r, y) is true, it continues towards the next rung level. Otherwise, it is stopped, and the worker becomes free to pick up a novel evaluation. As long as fewer than 1) configurations have reached a rung, the job is always continued.
Stopping variant.
Promotion variant. This variant of asynchronous SH was presented by Li et al. (018 and called ASHA. Note that, in the remaining text, we will refer to general asynchronous SH as ASHA and indicate the both variants with promotion or stopping based ASHA. Once a job for some æ reaches rung r, it is paused there, and the worker is released. The evaluation of æ can be promoted (i.e., continued to the next rung) later on. When a worker becomes available, rungs are scanned in descending order, rumning job to promote the first paused for which continueza; r) is true. When no such paused configuration exists, a new configuration evaluation is started. With fewer than " metries recorded a rung, no promotions happen there.
The stopping and promotion variants can exhibit rather different behaviour (see Figure 2 also demonstrated in our experiments. Initially, the stopping variant gives most configurations the benefit of doubt, while the promotion variant pauses evaluations until they can be compared against a sufficient number of competitors.
eadgg
6505
promotion
coddg
validativn enre
1.125
i 100+
stopping
Finally, note that asynchronous SH can be gener- alized to asynchronous Hyperband in much the same way as in the synchronous case, as shown by Li al. 2018)) 8). However, it was reported that asynchronous SH typically outperforms the Hy- perband for expensive tuning problems, which we also show in our experiments in Section|4. After some initial exploration, both with random and model-based variants, we confirmed this ob- servation. In the following, we will thus restrict our attention to SH scheduling.
0020-
n.025
zung
level
Figure 2: This cartoon on toy data shows the differ- ence between the promotion and stopping variants of SH. The three curves correspond to the evalu- ations of three configs. The blue curve reaches the smallest rung level first, which triggers the scheduling process. While the stopping variant would continue the evaluation (shaded blue curve), the promotion variant would stop, and proceed with new configuration (shaded red curve). The evaluation of blue would only be continued once enough datapoints at this rung level have been ob- served. As shown in the experiments, the stopping variant achieves often better performance in early iterations, whereas the promotion variant obtains usually a better final performance.
3 MODEL-BASED ASYNCHRONOUS MULTI-FIDELITY OPTIMIZER
We now describe our new model-based method that is able to make asynchronous decisions across different fidelities of the objective func- tion and in presence of pending evaluations. Mo- tivated by the fact that in standard sequential set- tings, Gaussian process (GP) based BO outperforms random search (Shahriari et al. 2016), we equip asynchronous SH with decisions based on a GP surrogate model. Following a range prior work on non-nonnnee mon-parallel multi-fidelity BO (Swersky et al. 2013) Klein et al. 2017a Poloczek et al.) 2018 Swersky et al. 2014). we place a GP prior over f(x, r) to jointly model not only the corre-oorllltion within each fidelity, but also the cross-correlations between fidelities,
4

---

Under review as a conference paper at ICLR 2021
f(z, r) ~ GP(p(a, r), k((2, r), (a),r'))).
This is in contrast to synchronous BOHB (Falkner et al. 2018), which just employs an independent TPE (Bergstra et al. 2011) model over for each rung level R. preventing it from transfering information from lower to higher rungs.
Pending evaluations and fantasizing. Since multiple configurations evaluated in parallel, we have to deal with pending evaluations (for which results have not yet been obtained) when proposing new configurations. Failing to do so runs the risk of choosing the same (or very similar) configurations over and over, which would result in poor sampling efficiency. We do so by fantasizing the outcomes of pending evaluations, as proposed by /nook al. (201). In nutshell, we marginalize the acquisition function over the GP predictive posterior for pending configurations. In practice, we approximate this by averaging the acquisition function over sampled function values.
In the context of synchronous scheduling, dealing with pending evaluations is also known as batch HPO, problem which has seen a lot of prior attention (Ginsbourger et al., 2010 Desautels et al. 2014, González et al.) 2016 Alvin et al. 2019). Surprisingly, most of these works ignore fantasizing, claiming it is too expensive to do (Ginsbourger et al. (011], I, and propose heuristics like local penalties or artificial randomization by Thompson sampling (Hernandez-Lobato al. 2017: Kandasamy et al., 2016). Quite in contrast to such claims, we find that, as long as kernel hyperparameters remain constant, fantasizing comes almost for free. For GP regression, the posterior covariance matrix does not depend on the function values (only on the inputs), which means that fantasizing does not require additional cubic-complexity computations. Details given in Appendix A.I
Lastly, it is important to underscore the unique challenges posed by pending evaluations and fanta- sizing in the asynchronous SH case, in particular, those not encountered in the synchronous case. We elaborate on these challenges in Appendix A.3 and summarize our asynchronous algorithm for overcoming them in concise pseudocode.
Kernel choice. We implemented and compared a range of different surrogate models for f(x r): a joint Matérn 5/2 kernel with automatic relevance determination (ARD) (Snoek al. 2012) over r), with and without warping of r; the additive exponential decay model of Swerssk et al. (2014); a novel non-additive extension of the latter, relaxing underlying assumptions which may not hold in practice. In all cases, the base kernel on a: alone is Matérn 5/2 ARD. Details for our new surrogate model are provided in Appendix A.2
Acquisition strategy. We follow synchronous BOHB (Falkner et al. 2018) in choosing æ by optimizing the expected improvement (EI) acquisition function (Shahriari et al., 2016) over the posterior on (aay) where racg is fixed for each decision. We choose Tacq E R as the largest rung for which at least metric values have been observed, where L is typically set to the input dimensionality (i.e., number of hyperparameters). After some initial period, Tacq eventually converges to Tmux- This strategy does not take into account that the choice of æ may have different downstream stopping or promotion consequences, interacting with currently pending evaluations. We leave the exploration of alternative acquisition strategies as an important direction for future work.
EXPERIMENTS
We compare MOBSTER to a range of state-of-the-arr algorithms. For synchronous Hyperband and BOHB, we used the HpBandSter package which uses a simple mechanism to reduce the amount of idling workers: if there are more free workers than slots the rung, left-over workers are used to immediately start the next bracket. There is no open-source implementation of (SSwesky et al. (2014) and Takeno et al. (2020) for which the implementation complexity is considerable, which why we omitted them here.
We implemented MOBSTER, as well as all other asynchronous techniques, AutoGl uon which will all be open-sourced along with this paper. A number of worker nodes run training jobs, publishing metrics after each epoch. One of the workers doubles as master, concurrently running the HP optimization and scheduling.
https:///gitthbb..cm/////ww
5

---

Under review as a conference paper at ICLR 2021
We also compare against Dragonfly (Kandasamy et al. 2019). While Autonluon allows to paral- lelize both across instances and processes on a single instacee, Dragonfly only supports the latter. Hence, for a fair comparison, we run our method only Dragonfly. For all other experiments we parallelize across multiple instances.
single instance if we compare against
For all methods using SH the halving rate was 1 3. We report the immediate regret Pt yt y+ after wall-clock time t, where y, is the best observed validation error across all methods, runs and time steps on this dataset. Using the regret instead of just the validation error gives a more detailed picture of progress towards the global optimum. For all classification datasets we cap the regret at lower bound of 10 which corresponds to a 0.1% difference in classification accuracy to the global optimum. We consider lower values to be not significant in practice and attributed them to the intrinsic noise of the objective function. For each method we report mean and the standard error of the mean across multiple runs with different seeds of the random number generator.
We run experiments on the following set of benchmarks (for further details regarding the search spaces see Appendix B All experiments were conducted on AWS EC2, using m4 xllare instances for CPU- and g4dn. xlarge instances for GPU-based computations, respectively.
Tabular Datasets:
First, we optimized the hyperparameters of multi-layer perceptron (MLP) on the tabular classification dataset electricity gathered from OpenMI. (Vanschoren et al. 2014). The MLP has two hidden layers with ReLU activations. We tuned 9 hyperparameters: the learning rate of ADAM (Kingma & Ba 2013), batch size, weight decay, and, for each layer, dropout rate, number of units and the scale of uniform distribution initialize weights. The number of epochs varies between min = 1 and mmax = 81.
Neural Architecture Search: To evaluate our approach in a NAS setting, we used the NASBench201 datasets from Dong & Yang (2020) which consists of a offline evaluated grid of neural network architectures for three different datasets: CIFAR-10, CIFAR-100 (Krizhevsky) 2009) and Ima- genet16 16 (Chrabaszzz et al. (017). Categorical hyperparameters were one-hot encoded. The minimum and maximum number of epochs were Tmio and max 200. To simulate realistic dynamics of asynchronous NAS, we put each worker to sleep for the time per epoch each real evaluation took. This does not speed up experiments, but decreases cost, since no GPU instances are required. Compared to the other benchmarks which contains integer and continuous hyperparameters, this benchmark is purely discrete.
Image Classification: Next, we tuned ResNet (He et al. 2016) on the image classification dataset CIFAR-10 (Krizhevsky) 2009), the batch size, weight decay, initial learning rate and momentum. We used 40000 images for training. 10000 for validation, and applied standard data augmentation (cropping; horizontal flips). SGD is used for training, the learning rate multiplied by 0.1 after 25 epochs. We used mmin = 1 and Timx = 27. As our goal is to evaluate our approach, omitted additional tfecks-ff-the-raas required to obtain state-of- satte-of-the-ree art accuracy (Yang et al. 2020).
Lastly, considered LSTM (Hochreiter & Schmidhuber 1997), ap- plied to language modelling on the WikiTexx-2 dataset (Merity et al. (017) with the default train- ing/validationn/est split. We optimized the initial learning rate of SGD, batch size, dropout rate, gradient clipping range, and decay factor multiplied to the learning rate if the validation error has not improved upon the previous epoch. The LSTM consisted of two layers with 1500 hidden units each. For the word embeddings, we also used 1500 hidden units and tied them with the output. Epochs vary between miin and Fmax 81.
Language Modelling:
4.1 ABLATION STUDY
We start with an in-depth analysis of our proposed method. If not explicitly stated otherwise, we report the immediate regret over wall-clock time of the MI.P benchmark on the electricity dataset for 4 workers and the NASBench201 CIFAR- 10 dataset for 8 workers. These two benchmarks cover continuous as well as discrete hyperparameter optimization problems.
Successive Halving vs Hyperband: First, we compare asynchronous scheduling based on SH versus Hyperband. We run different instances of SH, where we vary the minimum rung level Tmin in the same way as Hyperband. Figure 3 shows the results for both promotion and stopping based scheduling, combined with sampling from our model or random. Similar to results reported by Li et al. (2018), the performance of SH is decaying with an increasing T'án both for our model-based

---

Under review as a conference paper at ICLR 2021
(857)
Hekl (852)
Proadas (MIP)
tha Demeara
ChirkE
Mollomh Cliill)
Cleit))
1oocl (N Chall
200 100
1000
Figure 3: Comparison of asynchronous Hyperband and SH (stopping / promotion scheduling variants and sampling from model / random) on the MLP benchmark (top) and NASBench201 (bottom). SH with the most aggressive bracket works as well and often better than Hyperband across all variants. As comparison we also include asynchronous random search (RS).
Ment
250
mx Arc lore Jaice by
All
PAB-- & (oood
rabobak cad (sooad))
Effect of the kernel choice on the MLP benchmark (left, left middle) and NAS- Bench201 (right middle, right). We also include ASHA (random choices) for comparison. There is not a consistent trend across the difference kernels (note the standard error of the mean). Bottom: Comparison of ASHA and MOBSTER (stopping and promotion variant). Left: MLP on electricity (4 workers). Left Middle: NASBench201 on CIFAR-10 (8 workers). Right Middle: scaling with the number of workers of ASHA (dashed line) and MOBSTER (solid line) for stopping (left) and promotion (right)
Figure 4: Top:
and random sampling. Also, the most aggressive bracket, where Tmin epoch, works as good or even better than Hyperband, most distinctly for the promotion based scheduling. For the remaining experiments we therefore use SH with a minimum rung level of Tmin- epoch.
We analyse the influence of the choice of kernel and mean function for f(x, r) on the performance of the stopping and promotion variant of asynchronous BOHB. We compare different variants of the exponential decay model (see Appendix A.2 for more details): fixing ô = 0 as in Swersky et al. 2014),
Kernels:
1, or learning with the other GP hyperparameters. We use a Matérn5/2 ARD kernel for the xx model between configurations x SnSok et al. (2012). As an additional baseline, we use a Matérn3/2 ARD kernel and constant mean function on inputs (x.
In Figure| we compare the various types of kernel. Maybe somewhat surprisingly, there is no significant difference between the surrogate models and the precise model for inter- or extrapolation along seems less important. For the remaining experiments, use the exponential decay kernel with learned 8 as the most flexible choice which also obtains slightly better performance.
MOBSTER vs ASHA: Next, we show the benefit of sampling from our model instead of uniformly at random for both scheduling variants (see Figure 4). Initially, MOBSTER (stopping / promotion) per- forms similar its random-based counterpart ASHA (stopping/ / promotion). However, with enough datapoints, it rapidly approaches the global optimum, which is in line with typical improvements of BO over random search (Falkner al. 2018).
7

---

Under review as a conference paper at ICLR 2021
KAST AO0 Chiil
Hilker
Dreery
Figure 5: Comparison to various baselines across multiple processes on a single instance (left) and across instances (right) for the MLP and NASBench201 benchmarks. We performed 20 runs for each method. See main text for an analysis.
Scaling with the number of workers: As seen in Figure 3 right, the substantial speed-ups of MOBSTER over ASHA are observed consistently with 2, 4, 8, and 16 workers on the MLP benchmark. In fact, in most cases MOBSTER converges to high-accuracy solution in about the same time as ASHA needs with twice the number of workers: using a joint surrogate model can save half the resources compared random search.
Stopping versus promotion scheduling:. Next, we focus on the two variants of asynchronous scheduling (stopping and promotion) described in Section The stopping rule achieves good per- formance faster than the promotion variant (Figure [3 right) up to 4000 seconds on the NASBemch201 benchmark and up 500 seconds on the MLP benchmark. Recall from Section 2 that for the stop- ping rule, the initial 1) configurations are not stopped, while the promotion variant pauses all initial configurations at the lowest rung level of their bracket. However, least for the MLP benchmark, after this initial phase the promotion- scheduling achieves slightly better performance.
4.2 COMPARISON TO
METHODS
Wikitext2 (8 workers)
ResNet Cifar10 (4 workers)
10
skopis, unqraing nOBT
MoBater stopping
10
ASHA stopping
valdsttinn regret
Paliditioon regrett
10-1
S-BOHB
10.
S-HB
10'-
20-
10
10 1
10000
20000
30000
43000
500000
1000
6000
8000
100000
wall-clock time (scconds)
wall-clock time (sccondss
Figure 6: Left: Results of the LSTM benchmark. Right: Results for the ResNet benchmark.
We now compare MOBSTER against range of state-of-the-art algorithms: ASHA (Li et al.
2018).
asynchronous BO (Snoek et af.) 2012) (A-BO), asynchronous random search (Bergstra et al. 2011
(A-RS), synchronous BOHB [Falkner et 2018) (S-BOHB), synchronous Hyperband (Li al. 2017) (S-HB), asynchronous BO with Thompson Sampling (Kandasamy et al. 20166) (Dragonfly) and BOCA (Kandasamy et al. 2017) (Dragonfly-MIF.
MLP and NASBench201 Figure provides results for the MLP and the NASBench201 benchmark, both for the single-instance (left) and multi-instance setting (right) (see Appendix for results on the other two NASBench201 benchmarks). MOBSTER outperforms both Dragonfly and Dragonfly- Thereby, parallelizing across instances provides an additional speed-up compared to the single- instance setting. Somewhat surprisingly Dragonfly-MF is slower in terms of convergence than Dragonfly on the NASBench201 benchmark, which indicates that it cannot model the performance across fidelities well. For the multi-instance scenario, ASHA (stopping and promotion) performs better than synchronous Hyperband and BOHB on the discrete NASBench201 benchmarks. But, due to its random sampling, it often does not converge to sensible performance on the continuous MLP problem. We attributed S- S-BOHB poor performance on the NASBench201 datasets to its kernel density estimator which seems to struggle with discrete spaces. As described above, the stopping
8

---

Under review as a conference paper at ICLR 2021
variant of MOBSTER works better in the beginning, but the promotion variant achieves a better final performance. However, both variants MoBSTER outperform all other baselines.
ResNet on CIFAR-10. Based the previous results we limit our comparison to ASHA as well as S-HB and S-BOHB. MOBSTER achieves consistently a lower regret than all three baselines.
LSTM on WikiText-2. Figure 6 left shows results for LSTM tuning the WikiText-2 dataset. To save computations, we limited the comparison to MOBSTER, ASHA, and S-BOHB. Note that a single run (out of 5 per method) takes roughly 5 GPU days. Training single neural network for the full 81 epochs takes roughly 12 hours, and S-BOHB is only able to execute single bracket in the allocated time budget. Due limited data, it cannot fit surrogate model the highest resource level Tmaz. which may explain its overall poor performance. Because of its asynchronous scheduling, both MOBSTER and ASHA perform substantially better. After around 7000 seconds, MOBSTER'S model kicks in, allowing it to approach the optimum much faster than random- based ASHA.
5 CONCLUSIONS
We present a novel method, that combines asynchronous scheduling with multi-fidelity BO. Instead of sampling new configurations random, they are chosen based on a joint Gaussian process surrogate model over resouree levels, and asynchronous scheduling is accommodated by fantasizing outcome of pending candidates. On range of challenging benchmarks, we compare our proposal to prior synchronous and asynchronous HNAS state-of-the-art. MOBSTER significantly outperforms synchronous BOHB and ASHA. The former is slowed down by synchronization overhead, using its parallel resources inefficiently at higher resource levels. ASHA the other hand does not suffer from synchronization points, but compared to MOBSTER, we often find it to plateau before solutions with slate-of-the-ee performance are found.

---

Under review as a conference paper at ICLR 2021
REFERENCES
A. Alvin, B. Ru, J. P. Calliess, S. Roberts, and M. A. Osborne. Asynchronous batch Bayesian optimisation with improved local penalisation. In Proceedings of the 36th International Conference on Machine Learning (ICML' 2019.
J. Bergstra, R. Bardenet, Y. Bengio, and B. Kegl. Algorithms for hyperparameter optimization. In Shawe-Taylor, R. Zemel, P. Bartlett, Pereira, and K. Weinberger (eds.), )) Advances in Neural Information Processing Systems 24, pp. 2546-2554. Curran Associates, 2011.
Chrabaszez, Loshchilov, and Hutter. downsampled variant of ImageNet as an alternative to the CIFAR datasets. arXiv: [cs.CV], 2017.
K. Cutajar, M. Pullin, A. Damianou, N. Lawrence, and J. Gonzáles. Deep Gaussian processes for multi-fidelity modeling. Technical report, NeurlPS Workshop on Bayesian Deep Learning, 2018.
T. Desautels, A. Krause, and J. Burdick. Parallelizing sxploration-exploiiaei tradeoff's in Gaussian process bandit optimization. Journal of Machine Learning Research, 15(1):3873-3933, 2014.
T. Domhan, J. T. Springenberg, and F. Hutter. Speeding up automatic hyperparameter optimization of deep neural networks by extrapolation of learning curves. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI15), 2015.
X. Dong and Y. Yang. Nas-bench-201: Extending the scope of reproducible neural architecture search. arXiv:2001.00322 CV], 2020.
S. Falkner, A. Klein, and Hutter. BOHB: Robust and efficient hyperparameter optimization at scale. In Proceedings of the 35th International Conference Machine Learning (ICML (ICML2018), 2018.
D. Ginsbourger, Le Riche, and L.. Carraro. Kriging well-suited to parallelize optimization. In Computational Intelligence in Expensive Optimization Problems, pp. 131-162. Springer, 2010.
D. Ginshourger, J. Janusevskis, and R. Le Riche. Dealing with asynchronicity in parallel Gaus- sian process based global optimization. In 4th International Conference of the ERCIM WG on Computing and Statistics, 2011.
D. Golovin, B. Solnik, S. Moitra, G. Kochanski, Karro, and D. Sculley. Google vizier: A service for black-box optimization. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2017.
J. González, Z. Dai, P. Hennig, and N. Lawrence. Batch Bayesian optimization via local penalization. In Gretton & Robert (2016). pp. 648-657.
A. Gretton and C. Robert (eds.). Workshop on Artificial Intelligence and Statistics 19, 2016.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR' 16). 2016.
J. Hernandez-Lobato, J. Requeima, E. Pyzer-Knapp. and A. Aspuru- Guzik. Parallel and distributed Thompson sampling for large-scale accelerated exploration of chemical space. In D. Precup and Y. W. Teh (eds.), International Conference on Machine Learning 34, pp. 1470-1479. JMLR.org. 2017.
Hochreiter and J. Schmidhuber. Long short-term memory. Neural computation, 1997.
K. Jamieson and A. Talwalkar. Non-stochastic best arm identification and hyperparameter optimiza- tion. In Proceedings of the 17th International Conference Artificial Intelligence and Statisties (AISTATS' 16), 2016.
D. Jones, M. Schonlau, and W. Welch. Efficient global optimization of expensive black box functions. Journal of Global Optimization, 1998.
K. Kandasamy, A. Krishnamurthy, J. Schneider, and B. Poczos. Parallelised Bayesian optimisation via Thompson sampling. In Gretton & Robert 2016), pp. 133-142.
10

---

Under review as a conference paper at ICLR 2021
K. Kandasamy, G. Dasarathy, J. Schneider, and B. Póczos. Multi-fidelii Bayesian optimisation with continuous approximations. In Proceedings of the 34th International Conference on Machine Learning (ICML'I7) 2017.
K. Kandasamy, K. R. Vysyaraju, W. Neiswanger, B. Paria, C. Collins, J. Schneider, B. Poczos, and E. P. Xing. Tuning hyperparameters without grad students: Scalable and robust Bayesian optimisation with Dragonfly. In Journal of Machine Learning Research 2020, Special Issue on Bayesian Optimization, 2019.
Z. Karnin, T. Koren, and O. Somekh. Almost optimal exploration in multi-armed bandits. In In Proceedings of the 30th International Conference on Machine Learning (ICML' 13), 2013.
M. Kennedy and A. O'Hagan. Predicting the output from complex computer code when fast approximations available. Biometrika, 87(1):1-13, 2000.
D. Kingma and J. Ba. Adam: method for stochastic optimization. International Conference on Learning Representations (ICLR'I5) 2015.
A. Klein, S. Falkner, S. Bartels, P. Hennig, and F. Hutter. Fast Bayesian hyperparameter optimization on large datasets. Electronic Journal of Statistics, 11, 2017a.
A. Klein, S. Falkner, J. T. Springenberg, and F. Hutter. Learning curve prediction with Bayesian neural networks. In International Conference on Learning Representations (ICLR'I7), 2017b.
A. Krizhevsky, Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
L. Li, K. Jamieson, G. DeSalvo, A. Rostamizadeh, and A. Talwalkar. Hyperband: Bandit-based configuration evaluation for hyperparameter optiiiiiaaoooiii In International Conference on Learning Representations (ICLR' 17), 2017.
L. Li, K. Jamieson, A. Rostamizadeh, Gonina, M. Hardt, B. Recht, and Talwalkar. Massively parallel hyperparameter tuning. arXiv:/810.05934 [cs.LG], 2018.
R. Liaw, E. Liang, R. Nishihara, P. Moritz, J. E. Gonzalez, and I. Stoica. Tune: A research platform for distributed model selection and training. arXiv preprint arXiv:1807.05112 2018.
S. Merity, N. S. Keskar, and R. Socher. Regularizing and optimizing LSTM language models. arXiv: 1708. 121 Jes.CL. 2017.
M. Poloczek, J. Wang, and Frazier. Multi Mulli-information source optimization. In S. Bengio, H. Wal- lach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, Curran Associates, 2018
B. Shahriari, K. Swersky, Z. Wang, R. Adams, and N. de Freitas. Taking the human out of the loop: A review of Bayesian optimization. Proceedings of the IEEE, 2016.
Snoek, H. Larochelle, and R. Adams. Practical Bayesian optimization of machine learning algorithms. In P. Bartlett, F.C.N. Pereira, C.J.C. Burges, L. Bottou, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems 25, pp. 2951-2959. Curran Associates, 2012.
K. Swersky, J. Snoek, and R. Adams. Multi-task Bayesian optimization. C.J.C. Burges, L. Bot- tou, M. Welling. Z. Ghahramani, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems 26. Curran Associates, 2013.
K. Swersky, J. Snoek, and R. Adams. Freeze-thaw Bayesian optimization. Technical Report 1rXiv:1406.3899 ML], ArXiv, 2014. URL http::tttt///tttt
org/ hargg//bs//446..
Takeno, H. Fukuoka, Y. Tsukada, T. Koyama, M. Shiga, Takeuchi, and M. Karasuyama. Multi- fidelity bayesian optimization with max-value entropy search and its parallelization. In Proceedings of the 37th International Conference on Machine Learning (ICML'20) 2020.
Vanschoren, J. van Rijn, B. Bischl, and L. Torgo OpenML: Networked science in machine learning. SIGKDD Explorations, 2014.
11

---

Under review as a conference paper at ICLR 2021
A. Yang, P. M. Esperança, and F. M. Carlucci. NAS valuation is frustratingly hard. In International Conference on Learning Representations (ICLR 20), 2020.
C. Ying, A. Klein, E. Real, E. Christiansen, K. Murphy, and F. Hutter. NAS-Bench-101: Towards reproducible neural architecture search, arXiv:1902.09635 20,L),
12

---

Under review as a conference paper at ICLR 2021
A FURTHER DETAILS ABOUT THE MODEL
Here, we provide some additional details in order to support the main text.
A.1 POSTERIOR REPRESENTATION FANTASIZING
We employ a standard representation of the Gaussian process posterior. Say that k(x,, a²) is the kernel function, (x) the mean function, and the dataset DD is given by X E Raxdd E RR. For notational simplicity, æ contains the resource attribute here. The representation maintains L and p, where
=
p p= p=
p(X)).
Here, K (k æt)] ]] Rax" is the kernel matrix over the training inputs X, o² is the noise variance, and L is the Cholesky factor (lower triangular, positive diagonal).
fantasizing (Snoek et al., 2012) to deal with pending feedback. For M fantasy samples, we now have target matrix Y E RTx" For any observed configuration z,, the corre- sponding row in Y y/ 1 Now, L remains the same, and P == L -YY (()) Importantly, the dominating computation of L is independent of the number M of fantasy samples. Predictions on test points result M different posterior means, but common posterior variances.
Recall that
In practice, the surrogate model (kernel and mean function) comes with hyperparameters (e.g., noise variance o², length scales and variance of kernel kx, a. 3, 5), which have to be adjusted. All in all, recomputing the posterior representation involves (a) optimizing the hyperparameters on the observed dataset only, and (b) drawing fantasy targets, then computing the representation on the extended dataset, which includes pending configurations. Here, (a) is substantially more expensive than (b), as it involves computing the representation many times during the optimization.
delay computations of the posterior representation until the next configu- ration has to be chosen. Our algorithm is later formalized by concise pseudocode in inpppendix A.4 Note that if rumning tasks report metric values, they are inserted into the dataset, replacing pending configurations entered previously. Our implementation offers a number of strategies to skip the expensive part (a) of the computation. Here, (a) is not skipped initially, until the dataset size passes threshold. After that, we can skip (a) for all but every k-th update. Another strategy is to skip (a) as long as the number of full resource datapoints (æx, r; Tmax) does not grow. This ensures that do not spend more time on surrogate model updates in the multi-fidelit case than in standard BO with full resource evaluations only.
In our implementation,
A.2 EXPONENTIAL. DECAY SURROGATE MODEL.
The model proposed by Swersky al. (2014) is based on the assumption f(x,r) r) f(x) + - where À ~ p()) is drawn from a Gamma prior, and the asymptote fxx (i.e., f(x, r) as r + 20) from GP prior. They end up using zero-mean GP prior with kernel function ((x,)), (æ', rr)) kx Exx x') )+++ + (x(r,, r') and
kR(r,r") = /- -- >r' p(A) dA x(r+r),
ga
<(u)
0,3>0 > 0.
B)
This proposal has several shortcomings. First, f(x f(x) + 1 as 0, independent of what metric is used. Second, the random function e - assumption implies non-zero mean function, and kernel taking this into account. A better assumption would be f(x,r) r) = f(x) + -e Arr y > which implies a mean function p(æ, (x + 7x(r) and a covariance function
k((x,)) r), (x', r()) To (r. r') = x(r + r') --))((()'))))))
xx x²) "x((rr)))
(I)
One advantage of this additive model structure is that implied conditional independence relation can be exploited in order to speed up inference computations (Swersky et al.) 2014). However, this model implies r( f(x) 7 O: the metric for training at all depends æ in the
13

---

Under review as a conference paper at ICLR 2021
same way the asymptote. A more sensible assumption would be f(x,r) Y as 0, since without training, predictions should be random (e.g., 7 = for binary classification). We present a novel surrogate model which can incorporate this assumption. is based on
f(x r) 7 Ar f(x) (1 (1- de -r) de [0.
Some algebra (provided below) gives
,|x, r) = (m(() + (1xxx) 5m(()),
k((x,)) (,, (x',
(7 (xxx _ux(('))
+ (xx x ((x(r)))))) + xx(r)
- -
For 8 = O, we recover the additive model of Eq. D while for d = 1, we have that f(æ, r) = as r -> O, independent of æ. This model comes with hyperparameters a, 3, > 0 and 5 E [0, 1]. We
provide empirical analysis of this model in Section 4.1 of the main paper.
DERIVATION OF EXPONENTIAL DECAY SURROGATE MODEL
Recall that our novel surrogate model k((æ, r), (a',r')) and p(x, r) is based on the random function assumption (2) Since Ele >r] = x(r), it is clear that [If r)] = (x(r) + ux(x)(1 5x(())
(z) + (? (x)(()))<(r). Moreover,
k((2, r), (x', (x',,')) r')) = ([f(x, r((e',
(y ōpp (r, (xxx(x))) hx (z,
E [11 dc xr) (1 50
50 -x )} (7 6x)((x))
kR(T, (') - 6xx(xx)) ()=))))+ + 1x
(1 (1- 8(s(() + +x(r') 5ns(r + +r))),,
kr((r,")) x(r+r() ((())((F)).
A.3 FANTASIZING, SYNCHRONOUS VS. ASYNCHRONOUS
Here we underscore the unique challenges posed by pending evaluations and fantasizing in the asynchronous SH case, in particular, those not encountered in the synchronous case. Specifically, in the asynchronous case, we are offered far fewer guarantees about the algorithmic state at a given point in time, not least when decision needs to be made about what configuration to propose. This exacerbated by the fact that concurrent state updates are now possible, making it challenging to incorporate the most up-to-date information in the pocision-making process.
In short, to combine asynchronous SH and GP-based BO with fantasizing, there are many more moving parts to contend with than in the synchronous counterpart, and appreciable amount of care and attention toward bookkeeping is required to make it work efficiently. We illustrate this with concrete example. Consider instantiation of SH with Tmin 1, mmxx 27 with rj = 3. Further, assume there are total of 5 workers.
Synchronous. A snapshot of the algorithmic state is illustrated in Figure 7 showing the base rung of the first bracket being filled: so far 6 configurations have been proposed and have been evaluated (æ1, 23), while are still pending (Iz, 3t, Ts. Zg). This means there now worker idle, namely, worker 5. Since synchronous SH dictates that we need to completely evaluate 27 configurations at this rung before deciding which to promote to the next rung, we still have 21 configurations to
propose and evaluate. Hence, the scheduler will assign worker to evaluate new configuration at the base rung.
Proposing the new configuration in the presence of these pending evaluations is straightforward. One a) updates the GP model with all completed evaluations, and then b) sample fantasy outcomes for the pending evaluations. Note that need only extrapolate the current rung level, so little to bookkeeping required. Thereafter, one simply c) optimizes the acquisition function, conditioned on observed and fantasized evaluations.
14

---

Under review as a conference paper at ICLR 2021
33
32
jayon
3
4
1
30
observed
pending
3
5
6
26
27
next
Figure Synchronous. Base rung of the bracket has yet to be filled (6/27). Therefore, the idle worker will be assigned to evaluate new configuration at this rung. Proposing this new configuration with GP-BO is straightforward, even in the presence of pending evaluations, since they are all pending at the same rung.
33
G Janeon
32
2 Woteer
y Mayeen
Jeyyon
31
30
1
2
21
22
23
24
25
26
27
Figure 8: Synchronous, edge case. Base rung of the bracket is soon to be filled (23/27). With workers assigned to evaluate the last configurations necessary to fill this rung, the idle worker will be assigned to evaluating a new configuration at the base rung of the next bracket. Again, all pending evaluations are pending at the same rung.
In the edge case where the configurations necessary to fill the base rung have already been proposed but some are still pending evaluation, a situation might arise where a worker becomes idle but cannot begin evaluations at the next rung until all evaluations example of this is illustrated in Figure g total of 23 configurations have been evaluated and only 4 configurations implementation might utilize idle workers to begin filling the base rung of subsequent brackets. Even in this case, proposing new configurations in the presence of these pending evaluations in previous brackets is still relatively straightforward, since they are all pending at the same rung level.
complete at the current rung. An
still pending (#722, 2224, 325, 2227). This leaves 1 worker idle. A thoughtful
Asynchronous.
contrast, in the asynchronous paradigm, there are guarantees concerning the rungs at which configurations will be pending evaluation.
Furthermore, in an asynchronous computing environment, is possible that during the scheduling procedure, i.c. deciding whether promote an existing configuration to the next rung or to propose new configuration to fill the base rung (which would then invoke configuration proposal procedure). it is possible for important events to take place concurrently, not least of which being the completion of evaluations. To simply ignore such events would be reckless, as this could risk wasting resources on evaluating suboptimal configurations proposed with stale data.
snapshot an example algorithmic state is illustrated in Figure This snapshot has captured situation where there is I idle worker, and the scheduler has decided to utilize it to evaluate new configuration in order to fill the base rung. Now it needs to invoke the configuration proposal procedure.
Unlike before, this procedure needs to account for evaluations that have been observed, now across every rung, and deal with evaluations that are still pending, now also possible every rung. Added to these complexities the fact that additional evaluations have completed since the scheduling procedure began, namely, those of configurations æa and Dg rungs and 2, respectively.
15

---

Under review as a conference paper at ICLR 2021
Workee
33
4 Cookel
3
6 Sewlow
3
observed
abservediee
30
pending
1
2
4
6
9
10
nexi
Figure 9: Asynchronous.
To respond to these added complexities and nuances, additional needs be taken with algorithmic bookkeeping. In Inlappendix A.4, we describe the space of possible algorithmic states and formalize our asynchronous algorithm for dealing with these added complexities in concise pseudocode.
A.4 ALGORITHM
First, we formalize some concepts. A task is unit of work for evaluating the blackbox function at a configuration æ to some specified rung т. Then, it is the responsibility of the workers to asynchronously execute these units of work. Each task contains contextual information that includes hyperparameter configuration æ, the rung r, the target value y and a status flag indicating the status of the target value. Specifically, the status flag
status E {observed, observed pending, pendinng fantasized]
indicates whether an actual evaluation has been completed, in which case,
if has already been incorporated in updating the surrogate model, then status observed, otherwise, status observed
If the evaluation is currently pending, in which case
y may have fantasized value, and status = fantasized, or
no value at all, and status = pending.
Note that, in general, each hyperparameter configuration æ will have one or more associated tasks, each with different rungs Let D denote the dataset consisting of all the observed data,
Dt ((task.ar, task.r, task.y) task
Tasks task.status observed),
and D denote the extended dataset consisting of both observed and fantasized data,
D {taskk.r, task.r, task.y) task Tasks task.status {observed, fantasized)).
Our method is summarized in algorithm
16

---

Under review as a conference paper at ICLR 2021
Algorithm 1: MOBSTER
while under budger do
if Fworker Workers worker.status idle then task +- CreateTask ()
// determines the task's configuration and rung // initialize target value
task.y < NIL
task.status + pending
asyne call Execute (task)
end end
Function CreateTask ():
Provided in [Li et al. 2020; Algorithm 2] as function get (). MOBSTER overrides the line "Draw random configuration" with call to ProposeCandidatte ()
end
12
Function Execute (task); :
task.y < [task.. task.r)
evaluate f resource
tssk.status c- obs
14
15
end
Function ProposeCandidate (arguments):
Result: candidate 2
/" there new observations, need update the surrogate model and invalidate existing fantasy values
10
Itssk Tasks task.stabus observednew then
for task E Tasks do
20
task.status = observed then
#f mark as incorporated
task.status observed
22
else if task.status = fantasized then
I/ invalidate all fantasy values reset target value
task.y NII.
24
task.status + pending end end
25
26
1" maximize surrogate model hyperparameters condilioned observed data ID
0. + arg ming L(0; Di)
end
30
for task E Tasks do
impute fantasy values for all pending candidates
if task.status pending then
32
1' sample from the posterior predictive, conditioned on observed data D
task.y + y. where ÿ ~ p(y) task.æ. task.r; 0., Dt)
33
34
task.status fantasized
35
end
end
37
1" maximizo acquisition function, conditioned on both observed and fantasized data, D
x, f arg max a(x; Faoqi 0_, D1)
38
39
end
B CONFIGURATION SPACES
Table I shows the configuration space for the MLP benchmark, Table for the residual network benchmark, for NASBench201 and Tor the LSTM benchmark. If we exponential notation than we optimized the corresponding hyperparameter hot encoding for all categorical hyperparameters and an integer encoding for ordinal hyperparameters.
logarithmic scale. We used one-
C ADDITIONAL NASBENCH201 EXPERIMENTS
17

---

Under review as a conference paper at ICLR 2021
Table The hyperparameters and architecture choices for the fully connected networks.
Hyperparameter
Range
learning rate
[0 6.
batch size
[2
weight decay
[10-8.1]
dropout layer
99.
dropout layer
(0.
units layer
[2,,200
units layer 2
[27,210]
scale layer
[10 [10-3 10]
scale layer
[10-3, 10
Table 2: The configuration space for the residual neural network benchmark.
Hyperparameter learning rate batch size
Range [1-3 1-
[8.256]
weight decay momentum
[10 5.05.100 0,9
Table 3: The configuration space for the LSTM benchmark.
Hyperparameter
Range
learning rate
[1, 50
batch size
23 27
dropout
00, 0.99
gradient clipping
[0.1.2]
learning rate factor
[1, 100
Table The configuration space for NASBench201.
Hyperparameter
Range
edge 0
none, skip-coneipc nor-conv-Irl, nor-conv-33,
aug-pool-323]
edge 1
none, skip-connect, 11o-coom-lll,,omr-o0-333--131
edge
(none, skip-conned,, no0-ccono--lll ounp::
edge 3
[none, htw.://c..............ooooooaaaa
edge
(none, hto. o0
edge 5
none, hww.::/iwr..aucooooooooooooooooo
18

---

Under review as a conference paper at ICLR 2021
NASBench201 Cifar10
NASBench201 Cifar1 (8 worker)
10
10'
MoBater (insturess)
Dragarily
MoBeer stepping
30
validation regres
MoBater (throdds)
Dragonfly-M
validotion regret
ASHA stapping
promusiac
88
10-1
10-1
XSIIA yrumotion
5-IB
10-1
10-2
8000
10000
6000
8000
wall-clock time (seconds)
wall-clock time (seconds)
NASBench201 Cifar100 (8 worker)
NASBench201 CEar100
10
107
MoRess steppng
80
MolBen (insanee)
Bugguly
ASUA stooping
RS
(thoads)
BraguulyMM
mibiattonn regret.
MoBeer promosion.
WaEdarion righee
10-1_
XSHA promottion
S-HB
10
10-1
10
20.0
4009
10000
14000
7500
10000
12500
15000
time (scconds)
Wall-clock time (seconds)
NASBeuch201 ImageNes166120 (8 worker)
N4SBemd:201 ImsgeNe(16-131
validation regret
110
valdakoo magnd
10-1
10-2
MoBeter stopping
BO
1
ASHA stopping
MuBatie promiinn
S-B0HB IIB
Dragondy Deagontb-30
ASIA prumction
Modiser (tlccdds)
10
1r
300n
1000
19000
2000
5000
10000
15600
20000
25000
(secands)
wall-clock time (seconds)
Figure 10: Comparison to various baselines across multiple processes on single instance (left) and across instances (right) for the three different NASBench201 benchmarks. See main for an analysis.
19


Reviews:
[{"review_id": "zMx4bJLK-EW", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n-------\n\nAlgorithms for hyperparameter optimization either do not maintain a\nmodel over configurations or are synchronous. This work proposes an\nextension of the asynchronous successive halving algorithm by\nintroducing a Gaussian Process model which maintains a distribution over\nconfigurations and resource levels (referred to as rungs). Their\nalgorithm, MOBSTER, is evaluated thoroughly against many baselines and\ndatasets.\n\nDecision\n--------\n\nOverall, I am leaning towards marginally below acceptance threshold for\nthis paper. I do not have much confidence, due to my unfamiliarity with\nthis area. Your experiments section seems comprehensive and MOBSTER\ngenerally outperforms commonly used algorithms for hyperparameter\noptimization. Despite connections to ASHA and the median rule, there is\nlimited novelty and extension of prior work.\n\nOriginality\n-----------\n\nThe way the work is presented suggests that the proposed approach is not\nvery novel. Your paper does not note novelty of the proposed approach as\na contribution (i.e. in Section 1.1). For someone unfamiliar with this\narea, it would be good to discuss why this approach has not been\nexplored before despite its lack of novelty.\n\nQuality and Clarity\n-------------------\n\nThe paper is generally well-written. Some statements are vague or have\ntypos, and these can be found in the detailed/minor comments.\n\nStrengths\n---------\n\n-   As someone not familiar with this literature, I think you do a good\n    job at explaining previous work and your proposed approach. Section\n    2 in particular, helps situate your work in the literature discussed\n    in Section 1.2.\n-   The experimental results are thorough and convincing. Although some\n    choices remain unexplained, such as reporting regret and truncating\n    performance, you include many baselines and evaluate performance on\n    a wide variety of tasks. Some of the experiments on the larger\n    models (LSTM, ResNet) seem inconclusive, but it's good to include\n    them.\n\nWeaknesses\n----------\n\n-   There is limited novelty in the proposed approach. This is not an\n    issue on its own, but I think that the immediate challenges or\n    drawbacks of the proposed approach are not adequately addressed.\n    Perhaps it is not immediately straightforward to use a GP in\n    combination with successive halving, but the challenges are not\n    clear in Section 3. If it is straightforward, then it would be good\n    to discuss the reasons why it wasn't done before.\n-   Although it is noted that a main contribution is clarifying\n    differences between ASHA and median rule, there is overall limited\n    new insight. For example, much of Section 3 (on page 5) include\n    statements on design choices for the experiments. These do not seem\n    to be motivated from the proposed method, and generate little new\n    insight and seem to be better suited to the experiment section.\n\nDetailed Comments\n-----------------\n\n-   Abstract: \"simultaneously reason across hyperparameters and resource\n    levels, and supports decision-making in the presence of pending\n    evaluations.\"\n\n    This statement is confusing and doesn't convey what your approach\n    is, or how it differs from existing methods.\n\n-   Section 1: \" \\$**x**<sub>**\\***</sub> ∈ arg\n    min<sub>x∈\\ mathcal{X}</sub> f(x)\"\n\n    You're discussing architecture and hyperparameters here, but this\n    mathematical expression seems out of place. It is unclear if\n    $\\mathbf{x}$ is the hyperparameter or the input, because $f$ is\n    defined later as a mapping for inputs $x$\n    ($y_i = f(x_i) + \\epsilon_i$) not hyperparameters.\n\n-   Figure 2: I find the dashed lines fairly difficult to see. I\n    appreciate the effort to label the difference between stopping and\n    promotion, but I think the figure is actually not informative at all\n    of what is going on. All of my understanding from this figure is\n    from the caption.\n\n-   Section 4: \"We report the immediate regret…\"\n\n    The reasoning for this makes sense intuitively. However, can the\n    results in the paper be directly compared to results of other\n    papers? For example, under what conditions will the best performing\n    algorithm with respect to immediate regret also correspond to the\n    best performing algorithm with respect to validation error?\n\n-   \"For all classification datasets we cap the regret at a lower bound\n    of 10−3, which corresponds to a 0.1% difference in classification\n    accuracy to the global optimum.\"\n\n    This seems like a bold choice. Are there similar decisions in other\n    literature that can further justify this?\n\n-   Figure 6: \"After around 7000 seconds, MOBSTER’s model \\[approaches\n    the optimum\\] much faster than ASHA\"\n\n    Is this accurate? Both methods seem to reach the optimum around the\n    same time.\n\nMinor Comments\n--------------\n\n-   Section 2, footnote: \" Supporting pause-and-resume by checkpointing\n    is difficult in the multi-node distributed context. It is simpler to\n    start training from scratch whenever a configuration is promoted.\n    This is done in our implementation\"\n\n    You should be clear here that pause-and-resume is done in your\n    implementation. \"This is done in our implementation\" suggests that\n    you do in fact start training from scratch whenever a configuration\n    is promoted.\n\n-   Section 4: \"(for which the complexity considerable), which is why\n    omitted them here.\"\n\n    There seems to be some missing words here.\n\n-   Scrolling and zooming in on the figures on pages 6/7/8 is very\n    taxing on my relatively powerful desktop. I am not sure how the\n    figures are embedded, but maybe these can be rasterized.\n\n-   Figure 3: I assume RS is random search, but this is not said\n    anywhere in the paper.\n\n-   Figure 6: Why are the symbols (circle, diamond, squared) on the line\n    plot missing in the figures here?\n\nPost Discussion\n--------------\nAfter discussion, i have raised my score from 5 to 6.", "extra_scores": {}, "extra_text": {}}, {"review_id": "taKZBVIoanJ", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper \"Model-based Asynchronous Hyperparameter and Neural Architecture Search\" combines asynchronous parallelism with GP-based BO for HNAS applications. In general, I don't see any strong novelty in this paper (see below), however, a few different techniques have been combined together to solve the important HNAS problem, which is relevant to the ICLR audience. The experimental section is valuable because it combines a number of well-thought benchmarks and a variety of SOTA algorithms are compared. \n\nThis paper may be better placed in a journal venue as a consolidation of techniques and through experimental evidence.\n\nThere is one main algorithmic contribution in this paper and an extensive and well-thought experimental section. The contribution is the use of GPs instead of TPE in BOHB. This is achieved using a classic multi-fidelity approach where the kernel is augmented with the fidelity r, which is, an incremental algorithmic improvement to a well-established algorithm. However, from a practitioner's perspective, it is interesting to see confirmation that this works well as expected. Once that the GP probabilistic model is introduced then it is possible to combine that with fantasies for batch BO and use two known approaches for asynchronicity. \n\nContribution 1 in the text (end of the first section) is not a contribution, I would suggest that the authors remove it from the contribution list. It is just a background section. \n\nThe paper is pretty hard to follow (even for a reader that is fairly acquainted with the topic). The writing feels rushed, there are several typos and imprecision in reporting the results, see my minor remarks at the end. The text should be reworked and made clearer, with smoother transitions between the subtopics, and paying a great deal of attention to giving enough background on the combination of techniques used. \n\nThe authors define the immediate regret. But aren't the authors using simple regret in all the result plots? \n\nThe authors say: \" For all classification datasets we cap the regret at a lower bound of 10−3 , which corresponds to a 0.1% difference in classification accuracy to the global optimum\". It is my understanding that this is incorrect because the global optimum is unknown. Instead, since the authors are computing the immediate regret this corresponds to a 0.1% difference in classification accuracy to the best-observed validation error across all methods, runs, and time steps on this dataset.\n\nMinor remarks: \n- Page 1: this sentence is badly constructed \"Although their difference is subtle, they lead to substantially behaviours in practice\".\n- Page 3: K is used without being introduced.\n- Page 4: in figure 2 the authors can add a legend for the 3 configurations (and the 3 different colors).\n- Page 5: \"Appendix B.All experiments\" -> \"Appendix B. All experiments\"\n- Page 7: formatting of the titles of the different paragraphs is off, e.g., use of \":\", \".\". \n- Page 7: figure 4 bottom right middle and right is missing in the legend which one is ASHA and which one is Mobster.\n- Page 8: why is BOHB being called BOHB in one figure and S-BOHB in another? Better using the same notation. \n- Page 8: Figure 5, the names of the benchmarks on the top of the figures are confusing. Isn't the same benchmark evaluated twice for the multi-instance and mono-instance cases? \n- Figure 1:\n1) the left side doesn't depict BOHB, it represents one bracket in BOHB. So, the name on the top of the figure should be representative of that. \n2) the task legend on the right side of the two figures is somewhat confusing. If I understand correctly that means that you are running 30 evaluations and that the colors say about the number of the evaluation. \n3) I guess at this point in the text the authors are not interested in giving actual results. However, it would be better if the authors state if the data is fake; if this is not the case, what is the dataset that they are using? \n- Since this is an implementation paper, it is a pity that checkpointing is not implemented because \"is difficult in the multi-node distributed context\". That would save some compute and give a slightly faster convergence. \n- The text in figures 3, 4, and 5 is too small. Figure 3 should include the name of the benchmark inside the figure not just in the caption. \n- It would be useful to clarify what the authors mean by multi-instance settings for people that are less familiar with cloud services. Is it a distributed setting where the workers are independent instances (VMs) and they are assigned a computation by a master instance? \n- How are ordinal variables encoded in the search space (e.g., batch size in the tabular dataset)?\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "pbZnorcNFiW", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "After rebuttal: First of all, I would like to thank the authors for all their effort on the rebuttal and the revised paper and I really appreciate that. After carefull discussion with AC and other reviewers, I would, however, have to decrease my score to 6 due the lack of significant technical novelty. \n\n-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n\nOverview: This paper proposes to combine GP to SH/random sampling for asynchronous hyper-parameter optimization, and it proposes to use scheduling schemes like in ASHA for example (promotion scheduling) to handle the idle workers. The GP is placed over the function f(x, r), thus takes into account the cross-correlations between different fidelities. Ablation studies are provided to show how to choose the minimum rung level, the kernel hyper-parameters, as well as the impact of different number of workers and different scheduling scheme. The benefits of the new algorithm is then proved by extensive experiments to compare the proposed algorithm MobSter against the state-of-the-art algorithms.\n\nReasons for the score:\nI am pretty satisfied with the whole structure and pretty enjoyed reading the paper. The idea of replacing the random sampling in ASHA by a GP looks quite natural and is shown to be promising with thorough ablation studies and extensive comparisons to SOTA algorithms. Therefore, I would like to vote for accept. The only potential default is maybe the fact that all techniques used to form MobSter are not novel individually, which is also recognized by the authors. But I do think the paper is an useful work for the AutoML community.\n\nGeneral questions and remarks: As I said, I'm generally satisfied, and only have a few small remarks.\n- I think it would probably be better that the authors put a bit more effort on explaining the notion of rung and bracket (in Section 2). I'm not sure if it is that clear for those who are not familiar with the litterature.\n- One thing that I'm not quite convinced is the NAS part. Have the authors considered of comparing MobSter to other NAS-specific algorithms?\n\nMinor comments:\n- Section 1.1: one of our main contribution -> contributions.\n- Section 4, paragraph 1: for which the complexity considerable -> for which the complexity is considerable.\n- Section 4, paragraph 1: which is why omitted them here -> I would rather say 'which is why they are omitted here' probably?\n- Section 4, paragraph 4: immediate regret -> I would probably call it dynamic immediate regret, but it's not important. Btw, I'm not sure that I'm fully convinced by the claim \"Using the regret instead of just the validation error gives a more detailed picture of progress towards the global optimum.\".", "extra_scores": {}, "extra_text": {}}, {"review_id": "8Xkn8gKSrGe", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\nThe paper proposes a model-based asynchronous multi-fidelity method to optimize hyperparameters and perform a neural architecture search (NAS). The paper begins by addressing the differences between synchronous and asynchronous scheduling in Successive Halvining (SH) and its variants. It also analyzes the different stopping rule criteria. Based on these insights, the paper proposes a unified approach called BOBSTER that combines asynchronous scheduling and multi-fidelity Bayesian optimization. The authors empirically demonstrate that BOBSTER can find the optimal hyperparameters (architecture) more efficiently in terms of wall-clock time than other state-of-the-art algorithms on NAS, image classification task, and language modelling task.\n\n##########################################################################\n\nPros:\n1. The paper presents a simple strategy to speed up hyperparameter optimization / NAS that gives good empirical results. The work is certainly relevant to this venue.\n2. The paper is well written and motivated. The release of the codebase can potentially help the research community.\n3. The empirical results are convincing and support the claims made in the paper. The experiment protocols and choice of baselines are appropriate.\n\n##########################################################################\n\nCons:\nThe key concern about the paper is the lack of novelty. The paper does not bring additional insights. Both asynchronous scheduling and non-parallel multi-fidelity BO were studied before, and the work is an extension of these approaches. The method proposed in the paper looks more like engineering work. Moreover, although the justification is the appendix looks correct, it could be written more precisely (in terms of notations and explanation). \n\n##########################################################################\n\nQuestions:\n1. What are some limitations of using asynchronous scheduling (e.g. memory?). It would be helpful to discuss these in the manuscript.\n2. How accurate is approximating the marginal acquisition function by averaging the acquisition function over sampled function values? How does this affect the model?\n3. How does not considering that the choice of x may have different downstream stopping or promotion consequences affect the performance?\n4. In figure 4, the results don't show how ASHA changes as a function of the number of workers, but the main text describes it.\n5. It seems like validation regret is still decreasing in figures 5 and 6. What happens if it trains longer?\n6. What are meta-parameters to BOBSTER, and how sensitive are they? It would be helpful to have a sensitivity study. Also, how does the BOBSTER scale to the number of hyperparameters compared to the baselines? It will be helpful if the paper discusses these points.\n\nMinor notes:\n* In figure 1 caption, x, y --> $x$, $y$.\n* On page 2, \"they lead to substantially behaviours in practice\" --> \"they lead to substantially different behaviours in practice\"? Also, please re-write the previous sentence.\n* On page 2, the last bullet point, does the random sampling refer to BOHB? Also, are half the computational resources consistent throughout all experiments?\n* On page 3, K is not defined.\n* Figure 2 is difficult to understand at a glance. One suggestion is to use a side-by-side comparison between promotion and stopping instead of combining them in the same plot. \n* On page 5, how many random seeds are used when reporting the mean and standard error?\n* On page 6, \".All\" --> \". All\"; missing space.\n* Many figures in the paper do not show low validation regret; it cuts the curves. Are there any reasons for cutting them?\n* On page 6, \"no GPU instances are required\" --> doesn't the evaluation stage also requires GPU?\n* Labels in figures are small and hard to read (especially figure 5).\n* If these ASHA type methods are used for tuning optimization hyperparameter, do they suffer from short-horizon bias (Wu et al., 2018)?\n\n##########################################################################\n\nI thank the authors for their responses. I carefully read them (revised manuscript) and also read other reviewers' feedback. The reviewers clarified some of my misunderstandings. However, I would like to remain at the current rating because my original concern about the novelty remains the same. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "0QosHVhpiP6", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper has proposed to exploit a GP model to represent the correlation between configuration-rung tuples (as is typical in multi-fidelity BO) in asynchronous successive halving (ASHA) (Li et al. 2018), which has resulted in performance improvement over the state of the art, as shown in the experimental results. The experimental results are extensive and compelling. Introducing a GP to model the correlation between configuration-rung tuples in the existing ASHA work offers minimal technical merit though. Can the authors elaborate on whether there is any nontrivial, novel technical challenge with such an integration? This question does not seem to be adequately addressed in the paper.\n\nSection 3 is missing an algorithm showing the exact technical details of how to tie all the various components mentioned in the paper together. In its present state, it is an amalgamation of several bits and pieces describing the components in words.\n\nPage 1: The authors say that \"they rely on rather complicated mechanisms to select either the fidelity level or the next candidate. In this work we aim to adopt the desiderata of Falkner et al. (2018), namely, that of simplicity, which often leads to more robust methods in practice.\" Can the authors clarify whether they are claiming that multi-fidelity BO or BO with early stopping algorithms (including the references below for which codes are provided for empirical comparison) are less robust due to their complicated mechanisms? If so, can the authors support this claim?\n\nBayesian optimization meets Bayesian optimal stopping. In ICML 2019.\n\nInformation-based multi-fidelity Bayesian optimization. In NeurIPS Workshop on Bayesian Optimization 2017.\n\nBayesian optimization with binary auxiliary information. In UAI 2020.\n\nThe authors say that \"This is in contrast to synchronous BOHB (Falkner et al., 2018), which just employs an independent TPE (Bergstra et al., 2011b) model over x for each rung level, which prevents it to transfer information from lower to higher rungs.\" Can't it be simply extended to cover all rungs?\n\nThe authors say that \"For each method we report mean and the standard error of the mean across multiple runs with different seeds of the random number generator.\" Exactly how many runs would that be?\n\n\n\nMinor issues\n\nThe title, which includes neural architecture search, may not be appropriate, considering that the methodology in Section 3 is not about NAS. A more general title ought to be considered since the proposed methodology is applicable to general BO problems, as seen in the experiments section.\n\nPage 2. substantially behaviours?\n\nPage 3. I would prefer that the authors do not overload the term \"rung\" to have two very different meanings, considering that it is already not easy to remember what it meant originally.\n\nPage 8. AHSA\n\nPage 9. The following re4ference appears twice: K. Kandasamy, A. Krishnamurthy, J. Schneider, and B. Poczos. Parallelised Bayesian optimisation via Thompson sampling. In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS'18).", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is solid. It is correct, the text and author response demonstrate good knowledge of the area, the results are significant and solid, the experiments are strengthened by many independent runs (refreshing to see), the ablation study is well done, and the proposed distributed hyper-parameter and NAS alg is simple and practical. The paper is well written and reasonably polished.

The main drawback of the work in the eyes of the reviewers is that the paper is well described as a combination of existing ideas and a significant engineering effort with good but not stellar results. The reviewers found they did not gain any substantial technical insights from the work. As a result no reviewer was willing to champion the paper. However, the discussion, reviews, and author response made it clear that (1) the paper is enjoyable to read and informative, (2) the method is actually useful and performant, and (3) the combination of implementation details and methods is worth documenting. In balance, the paper is just below the bar. The program was extremely competitive this year.   
Decision: Reject