PASHA: Efficient HPO and NAS with Progressive Resource Allocation
Authors: Ondrej Bohdal
Lukas Balles
Martin Wistuba
Beyza Ermis
Cedric Archambeau
Giovanni Zappella
Venue: ICLR 2023 poster (2023)
Keywords: Neural architecture search
Hyperparameter optimization
Large datasets
Computational efficiency
Cost

Abstract: Hyperparameter optimization (HPO) and neural architecture search (NAS) are methods of choice to obtain the best-in-class machine learning models, but in practice they can be costly to run. When models are trained on large datasets, tuning them with HPO or NAS rapidly becomes prohibitively expensive for practitioners, even when efficient multi-fidelity methods are employed. We propose an approach to tackle the challenge of tuning machine learning models trained on large datasets with limited computational resources. Our approach, named PASHA, extends ASHA and is able to dynamically allocate maximum resources for the tuning procedure depending on the need. The experimental comparison shows that PASHA identifies well-performing hyperparameter configurations and architectures while consuming significantly fewer computational resources than ASHA.

Published as a conference paper at ICLR 2023
PASHA: EFFICIENT HPO AND NAS WITH PROGRESSIVE RESOURCE ALLOCATION
Ondrej Bohdal's Lukas Balles?, Martin Wistuba², Beyza Ermis Cédric Archambeau', Giovanni Zappella²
'The University of Edinburgh 2AWS, Berlin CCohere for Al londrej. woh.bbohaaaooooo... @ed. ac uk @beyzal cchere. com "[balleslb, marwistu, cedrica, zappella| waw.eelaaaaamma..ccommm
ABSTRACT
Hyperparameter optimization (HPO) and neural architecture search (NAS) are methods of choice to obtain the best-in-class machine learning models, but in practice they can be costly to run. When models are trained on large datasets, tuning them with HPO or NAS rapidly becomes prohibitively expensive for practitioners, even when efficient multi-fided culli--iielity methods are employed. We propose an approach to tackle the challenge of tuning machine learning models trained on large datasets with limited computational resources. Our approach, named PASHA, extends ASHA and is able to dynamically allocate maximum resources for the tuning procedure depending the need. The experimental comparison shows that PASHA identifies well-performing hyperparameter configurations and architectures while consuming significantly fewer computational resources than ASHA.
INTRODUCTION
Hyperparameter optimization (HPO) and neural architecture search (NAS) yield state-of-the-ar models, but often are very costly endeavor, especially when working with large datasets and models. For example, using the results of (Sharir al.] 2020) we can estimate that evaluating 50 configurations for a 340-million-ppraacee corpora would cost around $500,000. To make HPO and NAS more efficient, researchers explored how we can learn from cheaper evaluations (e.g. resources only to promising configurations. This created a family methods often described as multi- fidelity methods. Two well-known algorithms in this family are Successive Halving (SH) (Jamieson & Talwalkar 2016 Karnin et al., 2013) and Hyperband (HB) (Li al. 2018).
BERT model (Devlin et al., 2019) on the 15GB Wikipedia and Book
subset of the data) to later allocate more
Multi-fidell methods significantly lower the cost of the tuning. Li et al. 2018 reported speedups up to 30x compared to standard Bayesian Optimization (BO) and up to 70x compared to random search. Unfortunately, the cost of current multi-fidelity methods is still too high for many practitioners, also because of the large datasets used for training the models. As a workaround, they need to design heuristics which can select set of hyperparameters or an architecture with a cost comparable to training a single configuration, for example, by training the model with multiple configurations for single epoch and then selecting the best-performing candidate.
On one hand, such heuristics lack robustness and need to be adapted to the specific use-cases in order to provide good results. On the other hand, they build on an extensive amount of practical experience suggesting that multi-fidelity methods are often not sufficiently aggressive in leveraging early performance measurements and that identifying the best performing set of hyperparameters (or the best architecture) does not require training model until convergence. For example, Boonschhin ct al. (020) show that it is possible to find the best hyperparameter number of channels in ResNet- 101 architecture (He et al. 2015) for ImageNet (Deng et al. 2009) using only tenth of the data. However, is not known beforehand that one tenth of data is sufficient for the task.
Our aim is to design method that consumes fewer resources than standard multi- multiifidelity algorithms such as Hyperband (Li et al. 2018) or ASHA (Li al. 2020), and yet is able to identify configurations
Work done AWS, Berlin.

---

Published as a conference paper at ICLR 2023
that produce models with similar predictive performance after full retraining from scratch. Models are commonly retrained on a combination of training and validation sets to obtain the best performance after optimizing the hyperparameters. To achieve the speedup, we propose variant of ASHA, called Progressive ASHA (PASHA), that starts with a small amount of initial maximum resources and gradually increases them as needed. ASHA in contrast has fixed amount of maximum resources, which is a hyperparameter defined by the user and is difficult to select. Our empirical evaluation shows PASHA can save a significant amount of resources while finding similarly perfforrnn configurations as conventional ASHA, reducing the entry barrier to do HPO and NAS.
To summarize, our contributions are as follows: 1) We introduce a new approach called PASHA that dynamically selects the amount of maximum resources to allocate for HPO or NAS (up to a certain budget), 2) Our empirical evaluation shows the approach significantly speeds up HPO and NAS without sacrificing the performance, and 3) We show the approach can be successfully combined with sample-efficient strategies based on Bayesian Optimization, highlighting the generality of our approach. Our implementation is based on the Syne Tune library (Salinas et al. (022).
2 RELATED WORK
Real woold machine learning systems often rely on a large number of hyperparameters and require testing many combinations to identify suitable values. This makes data-inefficient techniques such as Grid Search or Random Search (Bergstra & Bengio (012) very expensive in most practical scenarios. Various approaches have been proposed to find good parameters more quickly, and they can be classified into two main families: 1) Bayesian Optimization: evaluates the most promising configurations by modelling their performance. The methods are sample-efficient but often designed for environments with limited amount of parallelism; 2) Multi-fidelity sequentially allocates more resources to configurations with better performance and allows high level of parallelism during the tuning. Multi-fidelity methods have typically been faster when run at scale and will be the focus of this work. Ideas from these two families can also be combined together, for example as done in BOHB by Falkner et al. (2018), and we will test a similar method in our experiments.
Successive Halving (SH) (Karnin et al. 2013 Jamieson & Talwalkar 2016) is conceptually the simplest multi-fidelity method. Its key idea is to run all configurations using a small amount of resources and then successively promote only a fraction of the most promising configurations to be trained using more resources. Another popular multi-fidelity method, called Hyperband (Li et al., 2018), performs SH with different early schedules and number of candidate configurations. ASHA (Li et al. 2020) extends the simple and very efficient idea of successive halving by introducing asynchronous evaluation of different configurations, which leads to further practical speedups thanks to better utilisation of workers in a parallel setting.
Related to the problem of efficiency in HPO, cost-aware HPO explicitly accounts for the cost of the evaluations of different configurations. Previous work on cost-aware HPO for multi-fidelity algorithms such CAHB (Ivkin et al. 2021) keeps a tight control on the budget spent during the HPO process. This is different from our work, as we reduce the budget spent by terminating the HPO procedure early instead of allocating the compute budget in its entirety. Moreover, PASHA could be combined with CAHB to leverage the cost-based resources allocation.
Recently, researchers considered dataset subsampling speedup HPO and NAS, Shim et al. (2021) have combined coresets with PC-DARTS (Xu et al., 2020) and showed that they can find well- performing architectures using only 10% of the data and 8.8x less search time. Similarly, Visalpara et al. (202T) have combined subset selection methods with the Tree-structured Parzen Estimator (TPE) for HPO (Bergstra et al. 2011]) With 5% subset they obtained between an 8x 10x speedup compared to standard TPE. However, in both cases it is difficult to say in advance what subsampling ratio to use. For example, the 10% ratio in (Shim al. 202T) incurs no decrease in accuracy, while reducing further to 2% leads to a substantial (2.6%) drop in accuracy. In practice, it is difficult to find a trade-off between the time required for tuning (proportional to the subset size) and the loss of performance for the final model because these change, sometimes wildly, between datasets. Further, Zhou et al. (2020) have observed that for a fixed number of iterations, rank consistency is better if we use more training samples and fewer epochs rather than fewer training samples and more epochs. This observation gives further motivation for using the whole dataset for HPÓ/NAS and design new approaches, like PASHA, to save computational resources.
2

---

Published as a conference paper at ICLR 2023
3 PROBLEM SETUP
The problem of selecting the best configuration of a machine learning algorithm to be trained is formalized in (Jamieson & Talwalkar 2016) as non-stochastic bandit problem. In this setting the learner (the hyperparameter optimizer) receives N hyperparameter configurations and it has to identify the best performing one with the constraint of not spending more than fixed amount of resources R (e.g. total number of training epochs) on a specific configuration. R is considered given, but in practice users do not have a good way for selecting it, which can have undesirable consequences: if the value is too small, the model performance will be sub-optimal, while if the budget is too large, the user will incur a significant cost without any practical return. This leads users to overestimate R. setting it to a large amount of resources in order to guarantee the convergence of the model. We maintain the concept of maximum amount of resources in our algorithm but we prefer to interpret R "safety net", cost not to be surpassed (e.g. in case error prevents normal behaviour of the algorithm), instead of the exact amount of resources spent for the optimization.
This setting could be extended with additional assumptions, based empirical observation, removing some extreme cases and leading to a more practical setup. In particular, when working with large datasets we observe that the curve of the loss for configurations (called arms in the bandit literature) continuously decreases (in expectation). Moreover, "crossing points" between the curves are rare (excluding noise). and they are almost always the very initial part of the training procedure. Viering & Loog [202T); Mohr & van Rijn (2022) provide an analysis of learning curves and note that in practice most learning curves are well-behaved, with Bornschein et al. (2020); Domhan et al. (0055) reporting similar findings.
More formally, let us define R as the maximum number of resources needed to train an MI. algorithm to convergence. Given Tm (i) the ranking of configuration i after using m resources for training, there exists minimum R" much smaller than R such that for all amounts of resources r larger than R the rankings of configurations trained with resources remain the same: 3R < R Vi E (configurations] Vr > R" ge (i) = (1). The existence of such a quantity, limited to the best performing configuration, is also assumed by Jamieson & Talwalkar (2016), and it is leveraged to quantify the budget required to identify the best performing confi configuration. If we knew R², it would be sufficient
all configurations with exactly that amount of resources to identify the best one and then just train the model from scratch with all the data using that configuration. Unfortunately that quantity unknown and can only be estimated during the optimization procedure. Note that in practice there is noise involved in training of neural networks, so similarly performing configurations will repeatedly swap their ranks.
4 METHOD
PASHA is an extension of ASHA (Li et al., 2020) inspired by the "doubling trick" (Auer et al. 1995). PASHA targets improvements for hyperparameter tuning large datasets by hinging on the assumptions made about the crossing points of the learning curves in Section 3 The algorithm starts with a small initial amount of resources and progressively increases them if the ranking of the configurations in the top two rungs (rounds of promotion) has not stabilized. The ability of our approach to stop early automatically is the key benefit. We illustrate the approach in Figure showing how we stop evaluating configurations for additional rungs if rankings are stable.
Given v, hyperparameter used both in ASHA and PASHA to control the fraction of configurations to prune, PASHA sets the current maximum resources R₂ be used for evaluating configuration using the reduction factor n and the minimum amount of resources to be used (K, is the current maximum rung). The approach increases the maximum number of resources allocated to promising configurations each time the ranking of configurations in the top two rungs becomes inconsistent. For example, if we can currently train configurations up to rung and the ranking of configurations in rung I and rung 2 is not consistent, then we allow training part of the configurations up to rung 3, i.e. one additional rung.
We describe the details of our proposed approach in Algorithm T
The minimum amount of resources r is a hyperparameter to be set by the user. It is significantly easier to set compared to R as is the minimum amount of resources required to a meaningful difference in the performance of the models, and it can be easily estimated empirically by running a few small-scale experiments.
3

---

Published as a conference paper at ICLR 2023
Rung
inrratoons
Rung
Rung
Figure 1: Illustration of how PASHA stops early if the ranking of configurations has stabilized. Left: the ranking the configurations (displayed inside the circles) has stabilized, so we can select the best configuration and stop the search. Right: the ranking has not stabilized, continue.
Algorithm Progressive Asynchronous Successive Halving (PASHA)
input minimum resource v, reduction factor
2:
function PASHA()
3: = 0, Ho Ty, Ko = (Ho/rr)
4:
while desired do
5:
for each free worker do
6:
(0, k) get job()
7:
8:
end
9:
completed joh (0, k) with loss
10:
Update configuration @ rung k with loss if h 2 K₁ then
11:
12:
Ty configuration raw.iing(
end if
14:
if
Ki and Tu & Tx- then
15:
t = +
16:
R. Ro
K. logg, (R,/r))
end if
19: end for
20: end while
21:
end function
22:
function get-job()
23:
// Check if there is a promotable config
24: for k 1,,
25:
candidates k k, rung k: /n) promotable {c candidates
26:
promoted]
promotable| > then return promotable ++1
28:
29:
end if
30:
// not, grow bottom rung
31:
Draw random configuration 0
32:
return 0,0
33:
end for
34:
end function
We also set maximum amount of resources R so that PASHA can default to ASHA if needed and avoid increasing the resources indefinitely. While not generally reached, it provides safety net.
4.1 SOFT RANKING
Due to the noise present the training process, negligible differences in the measured predictive performance of different configurations lead to significantly different rankings. For these reasons we adopt what we call "soft ranking". In soft ranking, configurations are still sorted by predictive performance but considered equivalent if the performance difference is smaller
4

---

Published as a conference paper at ICLR 2023
than value (or equal it). Instead of producing sorted list of configuration, this provides a list lists where for every position of the ranking there is a list of equivalent configurations. The concept is explained graphically in Figure 2 and also provide formal definition. For a set of n configurations C1, C2, Gi, ......... On and performance metric f (e.g. accuracy) with (c.), soft rank position i is defined as
f(a) & f(22) S... f(G)
soft rank; = {ez E configurations If(()) - f(e))l <
When deciding if increase the resources, go through the ranked list of configurations in the top rung and check if the current configuration at the given rank was in the list of configurations for that rank in the previous rung. If there configuration which does not satisfy the condition, increase resources.
B
Rank
Configurations [A, B)
Accuracy
1
I
C
2
[B,
3
(C)
# iterations
Figure 2: Illustration of soft ranking. There three lists with the first containing two items because the scores of the two configurations are closer to each other than e.
4.2 AUTOMATIC ESTIMATION OF BY MEASURING NOISE IN RANKINGS
Every operation involving randomization gives slightly different results when repeated, the training process and the measurement of performance the validation set are exception. In ideal world, we could repeat the process multiple times to compute empirical mean and variance to make a better decision. Unfortunately this is not possible in our case since the repeating portions of the training process will defeat the purpose of our work: speeding the tuning process. Understanding when the differences between the performance measured for different configurations for ranking them correctly. We devise method to estimate a threshold below which differences are meaningless. Our intuition is that configurations with different performance maintain their relative ranking over time. On the other hand, configurations that repeatedly swap their rankings perform similarly well and the performance difference in the current epoch or rung is simply due noise. We want measure this noise and use it to automatically estimate the threshold value to be used in the soft-ranking described above.
"significant" is crucial
Formally we can define set of pairs of configurations that perform similarly well by the following:
S (c,c)c (Tr, (c) > nTy (c') A Tre (c) < T.ą. (c') A n. (c) > nr, (c') V (Tr, (c) < nr, (c') A Tra (c) Tri (c') A n (c) < _., (c)))
(1)
for resource levels (e.g. epochs - not rungs) rg Fk Tı, using the same notation as earlier to refer to resources. In practice we have per-epoch validation performance statistics and use these to find resource levels T3, Tk. Tı that have configurations with the criss-crossing behaviour (there be several epochs between such resource levels). We only consider configurations (c, c') that made it to the latest rung, so ryyx, K,-1 2 rÿ > rn Kg However, we allow for the criss-crossing to then be calculated the N-th percentile of
happen across epochs from any rungs. The value of distances between the performances of configurations in S:
PN..cee)ssss fr, (c) (c)).
The exact value of ry depends the considered pair of configurations (c, c'). To uniquely define frys we take the maximum resources currently available for both configurations in the consid- ered pair c') Let us consider the following example setup: the top rung has 8 epochs and
5

---

Published as a conference paper at ICLR 2023
the next one has 4 epochs, there are three configurations Ca, Co ce that made it to the top rung and were trained for 8, 8 and epochs so far respectively. Assuming there was criss-crossing within each pair (ca, Ca), (Cas Cc) and (ca, C.), the set of distances between configurations in S is ([s((aa) (c(c)), (Ca(Ca) - fe(())),
(fo(cs) I receive new information about the performances of configurations. Initially the value of is set to 0, which means that we check for exact ranking if we cannot yet calculate the value of e.
fa(ca)]}- }. The value of is recalculated every time
EXPERIMENTS
In this section we empirically evaluate the performance of PASHA. Its goal is not to provide a model with a higher accuracy, but to identify the best configuration in shorter amount of time so that we can then re-train the model from scratch. Overall, we target a significantly faster tuning time and on-par predictive performance when comparing with the models identified by wate-of-theear optimizers like ASHA. Re-training after HPO or NAS is important because HPO and NAS in general require to reserve a significant part of the data (often around 20 30%) to be used as validation set. Training with fewer data is not desirable because in practice it is observed that training a model on the union of training and validation sets provides better results.
We tested our method on two different sets of experiments. The first set evaluates the algorithm on NAS problems and uses NASBench201 (Dong & Yang 2020), while the second set focuses HPO and was run on two large-scale tasks from PD1 benchmark (Wang et al., 2021
5.1 SETUP
Our experimental setup consists of two phases: 1) run the hyperparameter optimizer until N = 256 candidate configurations are evaluated; and 2) use the best configuration identified in the first phase to re-train the model from scratch. For the purpose of these experiments we re-train all the models using only the training set. This avoids introducing an arbitrary choice on the validation set size and allows to leverage standard benchmarks such NASBench201. In real-world applications the model can be trained on both training and validation sets. All our results report only the time invested since the re-training time is comparable for all optimizers. All
in identifying the best configuratio results are averaged over multiple repetitions, with the details specified for each set experiments separately. We use N 90-th percentile when calculating the value of e.
We use 4 workers to perform parallel and asynchronous evaluations. The choice of It is sensitive for ASHA as it can make the optimizer consume too many resources and penalize the performance. For fair comparison, we make R dataset- the considered benchmarks. is also dataset-dependent and r7. the halving factor, is set to unless otherwise specified. The same values are used for both ASHA and PASHA. Runtime reported is the time spent on HPO (without retraining), including the time for computing validation set performance.
taking the maximum amount of resources in
We compare PASHA with ASHA (Li et al. 2020). a widely-adopter approach for multi-fidelity HPO, and other relevant baselines. In particular, we consider "one-epoch baseline" that trains all configurations for one epoch (the minimum available resources) and then selects the most promising configuration, and "random baseline" that randomly selects the configuration without any training. For both one-epoch and random baselines and seeds as for PASHA and ASHA. All reported accuracies are after retraining for R = 200 epochs. In addition, two, three and five-epoch baselines are evaluated in Appendix A
sample N 256 configurations, using the same scheduler
5.2 NAS EXPERIMENTS
For our NAS experiments we leverage the well-known NASBench201 (Dong & Yang 2020) bench- mark. The task is to identify the network structure providing the best accuracy on three different datasets (CIFAR-IO, 10, CIFAR-100 and ImageNet16-1200 independently. We use r = 1 epoch and R = 200 epochs. We repeat the experiments using 5 random seeds for the scheduler and 3 random seeds for NASBench201 (all that are available), resulting in 15 repetitions. Some configurations in NASBench201 do not have all seeds available, seeds. To measure the predictive performance we report the best accuracy on the combined validation and test set provided by the creators of the benchmark.
impute them by averaging over the available

---

Published as a conference paper at ICLR 2023
Table 1: NASBench201 results. PASHA leads large improvements in runtime, while achieving similar accuracy as ASHA.
Dataset
Approach
Accuracy (%)
Runtime
Speedup factor
Max
ASHA
93.85
0.25
3.0h 0.6h
1.0x
200.0 0.0
PASHA
93.57
0.75
1,3h +: 0.6h
2.3x
36,1 = 50.0
CIFAR-10
Onc-epoch baseline
03.30 = 0.61
0.3h +: 0.0h
8.5x
1.0 0.0
Random baseline
72.88
19.20
0.0h
N/A
= 0.0
71.69
3.2h 0.9h
0.01
PASHA
71.84
1.41
0.9h +: 0.4h
3.4x
20.5 48.3
CIFAR-100
One-epoch baseline
65.57 = 5,53
0.3h 0: 0.0h
9.2x
1.0 0.0
Random baseline
42.83
18.20
0.0h
0.0
ASHA
45.63
2.2h
0.01
PASHA
45.13
1.51
2.9h = 1.7h
3.1x
21.3 = 48.1
ImageNet16-11
One-epoch baseline
41.42
4.98
1.0h + 0.0h
8.8x
1.0 0.0
Random baseline
20.75
9.97
0.0h 0.0h
N/A
0.0 0.0
The results in Table [ suggest PASHA consistently leads to strong improvements in runtime, while achieving similar accuracy values as ASHA. The one-epoch baseline has noticeably worse accuracies than ASHA or PASHA, suggesting that PASHA does a good job of deciding when to continue increasing the resources epoch baseline, so there is value in performing NAS. We also report the maximum resources used to find how early the ranking becomes stable in PASHA. The large variances are caused by stopping HPO at different rung levels for different seeds (e.g. 27 and 81 epochs). Note that the time required to train a model is about 1.3h for CIFAR-10 and CIFAR-I00, 100, and about 4. 1h for ImageNet16-120, making the total tuning time of PASHA comparable faster than the training time.
does not stop too early. Random baseline a lot worse than the one-
We also ran additional experiments testing PASHA with a reduction factor 7) = and rj = 4 instead of 7 3. the usage of PASHA scheduler in MOBSTER (Klein et al. 2020) and alternative ranking functions. These experiments provided similar findings as the above and are described next.
5.2.1 REDUCTION FACTOR
An important parameter for the performance of multi multi-fidelity algorithms like ASHA is the reduction factor. This hyperparameter controls the fraction pruned candidates at every rung. The optimal theoretical value is and it is typically set to 2 or 3. In Table 2 we report the results of the different algorithms ran with 7 = 2 and r) = 4 on CIFAR- 1-0 (the full set of results is in appendix[B) The gains are consistent also for 77 2 and 17 4, with larger speedup when using 1) that allows PASHA to make more decisions and identify earlier that can stop the search.
Table 2: NASBench201 CIFAR-100 100 results with various reduction factors The speedup is large for both 77 and 17 and accuracy similar ASHA is retained,
Dataset
Reduction factor
Appreach
Accuracy (%)
Runtime
Specdup factor
Max resources
ASHA
71.67 + 0.84
3.8h 1.0h
1.0x
200.0 + 0.0
PASHA
71.65 + 1.42
0.9h -: 0.1h
4.2x
5.9 1 2.0
CIFAR- 100
ASHA
71.43 1 1.13
2.7h 1: 0.9h
1.0x
200.0 1: 0.0
PASHA
72.09 1.22
1.h 1 0.4h
2.8x
4 49.0
5.2.2 BAYESIAN OPTIMIZATION
Bayesian Optimization combined with multi multi--idelity methods such as Successive Halving can improve the predictive performance of the final model (Klein et al. 2020 In this set of experiments, verify PASHA can speedup also these kinds methods. Our results are reported in Table where can clearly see PASHA obtains similar accuracy result ASHA with significant speedup.
7

---

Published as a conference paper at ICLR 2023
Table 3: NASBench201 results for ASHA with Bayesian Optimization searcher MOBSTER (Klein et al. 2020) and similarly extended version of PASHA. The results show PASHA can be successfully combined with a smarter configuration selection strategy.
Dutaset
Approach
Accuracy (%)
Runtime
Speedup facter
Max resources
MOBSTER
94.21 + 0.28
5.0h + 1.1h
1.0k
200.0 =: 0.0
CIFAR-I0
PASHA BO
94.00 + 0.20
2.6h 1.8h
2.0x
70.7 :: 81.6
MOBSTER
72.79
0.68
5.7h 1.4h
1.0x
200.0 0.0
CIFAR-100
PASHA BO
72.16 1.07
1.6h 0.5h
3.7x
13.0 8.7
MOBSTER
46.21 0.70
15.1h
4.0h
1.0x
200.0 0.0
ImageNet16-120
PASHA BO
45.36 + 1.06
3.9h 1.2h
3.9x
11.8 7.9
5.2.3 ALTERNATIVE RANKING FUNCTIONS
We have considered variety of alternative ranking functions in addition to the soft ranking function that automatically estimates the value by measuring noise in rankings. These include simple ranking (equivalent to soft ranking with 0.0), soft ranking with fixed values of obtained using various heuristics (for example based on the standard deviation of objective values in the previous rung), Rank Biased Overlap (RBO) (Webber al., 201O), and (RRR) that considers the objective values of configurations. Details of the ranking functions and additional results are in Appendix
reciprocal rank regret metric
Table 4 shows a selection of the results on CIFAR-100 with full results in the appendix. We can there are also other ranking functions that work well and that simple ranking is not sufficiently robust -oosttsoome some benevolence is needed. However, the ranking function that estimates the value of by measuring noise rankings (to which we refer simply as PASHA) remains the easiest to use, is well-motivated and offers both excellent performance and large speedup.
Table 4: NASBench201 - CIFAR-100 results for a variety ranking functions, showing there are also other well perl-perrorming options, even though those are harder to use and less interpretable.
Approach
Accuracy (%)
Runtime (s)
Speedup factor
Max resources
ASHA
71.69
1.05
3.2h = 0.9h
1.0x
200.0 + 0.0
PASHA
71.84
1.41
0.9h + 0.4h
3.4x
20.5 48.3
PASHA direct ranking
71.69 = 1.05
2.8h + 0.7h
1.1x
200.0 0.0
PASHA soft ranking 2.5%
71.41
1.15
1,5h + 0.7h
2.1x
88.3 +: 74.4
PASHA soft ranking
2a
71.14
0.97
0.7h
1.7x
136.4
PASHA RBO
71.51
0.93
0.7h
1.3x
180.5 50.6
PASHA RRR
71.42
1.51
1.2h 1 0.5h
2.6x
39.3 51.4
One-epoch baseline
65.57
5.53
0.3h
+ 0.0h
9.2x
1.0 0.0
Random buseline
42.83
18:20
0.0h +: 0.0h
N/A
0.0 0.0
5.3 HPO EXPERIMENTS
We further utilize the PD1 HPO benchmark (Wang et 2021) to show the usefulness of PASHA in large-scale settings. In particular, we take WMT15 German- English (Bojar et al. 2013) and ImageNet (Deng et al., 2009) datasets that use xformer (Lefaudeux et al. 2021) and ResNet50 (He al. 2015) models. Both of them are datasets with a large amount of training examples, in particular WMTT5 Gnngas-E has about 4.5M examples, while ImageNet has about 1.3M examples.
In PD1 we optimize four hyperparameters: base learning rate 7) E [10-5, 10.0] (log scale), momen- tum 1 3 [10-3, 1.0] (log scale), polynomial learning rate decay schedule power p E [0.1, 2.0) (linear scale) and decay steps fraction X E [0.01, 0.99) (linear scale). The minibatch size used for WMT experiments is 64, while the minibatch size for ImageNet experiments 512. There are 1414 epochs available for WMT and 251 for ImageNet. There are also other datasets in PD1, but these only have a small number of epuchs with epoch being the minimum amount of resources. As a result there would not be enough rungs benefits of the early stopping provided by PASHA.
8

---

Published as a conference paper at ICLR 2023
If resources could be defined in terms of fractions of epochs. PASHA could be beneficial there too. Most public benchmarks have resources defined in terms of epochs, but in practice it is possible to define resources also in alternative ways. We use 1-NN surrogate model for the PD1 benchmark. We repeat our experiments using 5 random seeds and there is only one dataset seed available.
The results in Sable that PASHA leads to large speedups both WMT and ImageNet datasets. The speedup is particularly impressive for the significantly larger WMT dataset where it is about 15.5x, highlighting how PASHA can significantly accelerate the HPO search on datasets with millions of training examples (WMT has about 4.5M training examples). The one-epoch baseline obtains similar accuracy as ASHA and PASHA for WMT, but performs significantly worse on ImageNet dataset. This result suggests that simple approaches such as the one-epoch baseline are not robust and solutions such as PASHA are needed (which we also saw on NASBench201). Selecting the hyperparameters randomly leads to significantly worse performance than any of the other approaches.
Table 5: Results of the HPO experiments on WMT and ImageNet tasks from the PD1 benchmark. Mean and std of the best validation accuracy (or its equivalent given in the PDI benchmark).
Dataset
Approach
Accuracy (%)
Runtime
Speedup factor
Max resources
ASHA
62.72
1.41
43.7h 37.2h
1357.4 80.4
PASHA
62.04 + 2,05
2.8h + 0.6h
15.5x
37.8 + 21.6
WMT
One epoch haseline
62.36
1.40
0.6h + 0.0h
67.3x
1.0
Random baseline
21.96
0.0h + 0.0h
N/A
0.0
ASHA
75.10 2.03
7.3h + 1.2h
1.0s
251.0 0.0
PASHA
73.37 + 2.71
3.8h + 1.0h
1.9x
45.0 30.1
ImageNet
epoch haseline
63.40
9.91
Random baseline
36.94 : 31.05
0.0h + 0.0h
N/A
0.0 0.0
6 LIMITATIONS
PASHA is designed to speed up finding the best configuration, making HPO and NAS more accessible. To do so, PASHA interrupts the tuning process when it considers the ranking of configurations to be sufficiently stable, not spending resources on evaluating configurations in later rungs. However, the benefits such mechanism will be small in some circumstances. When the number of rungs is small, there will be few opportunities for PASHA to interrupt the tuning and provide large speedups. This phenomenon is demonstrated in Appendix D on the LCBench benchmark (Zimmer et al. 2021).
Public benchmarks usually fix the minimum resources to one epoch, while the maximum is conchmark-dependee (e.g. 200 epochs for NASBench201 and 50 for LCBench), leaving little control for algorithms like PASHA in some cases. Appendix E analyses the impact of these choices.
For practical usage, we recommend having a maximum amount of resources at least 100 times larger than the minimum amount of resources when using r) = 33 (default). This can be achieved by measuring resources with higher granularity (e.g. in terms of gradient updates) if needed.
CONCLUSIONS
In this work have introduced a new variant of Successive Halving called PASHA. Despite its simplicity, PASHA leads to strong improvements in the tuning time. For example, in many cases it reduces the time needed about one third compared ASHA without noticeable impact on the quality of the found configuration. For benchmarks with a small number of rungs (I (I.CBench), PASHA provides more modest speedups but this limitation can be mitigated practice by adopting a more granular unit of measure for resources. Further work could investigate the definition of rungs and resource levels, with the aim understanding how they impact the decisions the algorithm. More broadly this applies not only to PASHA but also to multi- fidelity algorithms in general.
PASHA can also be successfully combined with more advanced search strategies based on Bayesian Optimization to obtain improvements in accuracy at fraction of the time. In the future, would like to test combinations of PASHA with transfer-learming techniques for multi multi-fidelity such as RUSH (Zappella et al. 2021) to further decrease the tuning time.

---

Published as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
We include the code for our approach as part of the supplementary material, including details for how run the experiments. We use pre-computed benchmarks that make possible run the NAS and HPO experiments even without large computational resources. In addition, PASHA is available as part of the Syne Tune library (Salinas et al. 2022).
ACKNOWLEDGEMENTS
We would like to thank the Syne Tune developers for providing us with a library to easily extend and use in our experiments. We would like to thank Aaron Klein, Matthias Seeger and David Salinas for their support on questions regarding Syne Tune and hyperparameter optimization more broadly. We would also like thank Valerio Perrone, Sanyam Kapoor and Aditya Rawal for insightful discussions when working on the project. Further, we are thankful to the anonymous reviewers for helping us improve our paper.
REFERENCES
Peter Auer, Nicoló Desa-Bianchi, Yoav Freund, and Robert E. Schapire. Gambling in rigged casino: The adversarial multi-armed bandit problem. In Annual Foundations of Computer Science, 1995.
James Bergstra and Yoshua Bengio. Random search for hyper- parameter optimization. JMLR, 2012.
James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hlyeer-paammnn optimization. In NIPS, 2011.
Ondfej Bojar, Rajen Chatterjee, Christian Federmann, Barry Haddow, Matthias Huck, Chris Hokamp, Philipp Koehn, Varvara Logacheva, Christof Monz. Matteo Negri, Matt Post, Carolina Scarton, Lucia Specia, and Marco Turchi. Findings the 2015 workshop on statistical machine translation. In Proceedings of the Tenth Workshop on Statistical Machine Translation, 2015.
Jorg Bornschein, Francesco Visin Visin, and Simon Osindero. Small data, big decisions: Model selection in the small-data regime. In ICMI., 2020.
Jia Deng, Wei Dong, Richard Socher, Li-jia Li, Kai Li, and Fei-fei. Imagenet: A large-scale hierarchical image database, 2009.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova, BERT: Pre-training of deep bidirectional transformers for language understanding. In ACL, 2019.
Tobias Domhan, Jost Tobias Springenberg, and Frank Hutter. Speeding up automatic hyperparameter optimization of deep neural networks by extrapolation of learning curves. In IJCAI, 2015.
Xuanyi Dong and Yi Yang. Nas-bench- Extending the scope of reproducible neural architecture search. In ICLR, 2020.
Stefan Falkner, Aaron Klein, and Frank Hutter. BOHB: Robust and efficient hyperparameter opti- mization at scale. In ICML, 2018.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2015.
Nikita Ivkin, Zohar Karnin, Valerio Perrone, and Giovanni Zappella. Cost-aware adversarial best arm identification. In ICLR NAS Workshop, 2021.
Kevin Jamieson and Ameet Talwalkar. Non-stochastic best arm identification and hyperparameter optimization. In AISTATS, 2016.
Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in aumti-armed bandits. In ICMI, 2013.
10

---

Published as a conference paper at ICLR 2023
Aaron Klein, Louis C. Tiao, Thibaut Lienart, Cedric Archambeau, and Matthias Seeger. Model-based asynchronous hyperparameter and neural architecture search. In arXiv, 2020.
Benjamin Lefaudeux, Francisco Massa, Diana Liskovich, Wenhan Xiong, Vittorio Caggiano, Sean Naren, Min Xu, Jieru Hu, Marta Tintore, and Susan Zhang. xformers: modular and hackable transformer modelling library, 2021.
Liam Li, Kevin Jamieson, Afshin Rostamizadeh, Ekaterina Gonina, Moritz Hardt Hardt, Benjamin Recht, and Ameet Talwalkar. system for massively parallel hyperparameter tuning. In MLSys, 2020.
Lisha Li, Kevin G. Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyper- band: A novel bandit-based approach to hyperparameter optimization. JMLR, 2018.
Felix Mohr and Jan N. van Rijn. Learning curves for decision making in supervised machine learning survey, In arXiv, 2022.
David Salinas, Matthias Seeger, Aaron Klein, Valerio Perrone, Martin Wistuba, and Cedric Archam- beau. Syne tune: A library for large scale hyperparameter tuning and reproducible research. In First Conference on Automated Machine Learning (Main Track), 2022.
Or Sharir, Barak Peleg, and Yoav Shoham. The cost training nlp models: A concise overview. In arXiv,, 2020.
Jae-hun Shim, Kyeongbo Kong, and Suk-Ju Kang. Core-set sampling for efficient neural architecture search. In ICML Workshop on Subset Selection in ML, 2021.
Tom Viering and Marco Loog. The shape of learning curves: review. In arXiv, 2021.
Savan Visalpara, Krishnateja Killamsetty, and Rishabh Iyer. A data subset selection framework for efficient hyper- parameee tuning and automatic machine learning. ICML Workshop on Subset Selection in MI., 2021.
Zi Wang, George E. Dahl, Kevin Swersky, Chansoo Lee, Zelda Mariet, Zachary Nado, Justin Gilmer, Jasper Snock, and Zoubin Ghahramani. Pre-trained Gaussian processes for Bayesian Optimization. In arXiv, 2021.
William Webber, Alistair Moffat, and Justin Zobel. similarity measure for indefinite rankings. In ACM Transactions on Information Systems, 2010.
Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong. PC-DARTS: Partial channel connections for memory-effiiient architecture search. In ICLR, 2020.
Giovanni Zappella, David Salinas, and Cédric Archambeau. A resource-efficient method for repeated HPO and NAS problems. In ICML AutoML Workshop, 2021.
Dongzhan Zhou, Xinchi Zhou, Wenwei Zhang, Chen Change Loy, Shuai Yi, Xuesen Zhang, and Wanli Ouyang. EcoNAS: Finding proxies for economical neural architecture search. In CVPR, 2020.
Lucas Zimmer, Marius Lindauer, and Frank Hutter. Auto-PyTorch Tabular: Multi-fidelity metalearn- ing for efficient and robust AutoDI.. TPAMI, 2021.
11

---

Published as a conference paper at ICLR 2023
A ADDITIONAL BASELINES
We consider additional baselines that evaluate how good two, three and five-epoch baselines compared to PASHA. From Tad we see that while these usually get closer to the performance of ASHA and PASHA than the one-epoch baseline, they are still relatively far compared to PASHA. Moreover, it is crucial to observe that such baselines cannot dynamically allocate resources and decide when to stop, and as result PASHA can outperform them both in terms of speedup and the quality of the found configuration.
Table 6: NASBench201 results. PASHA leads to large improvements runtime, while achieving similar accuracy ASHA.
Dataset
Approach
Accuracy (%)
Runtime
Speedup factor
Max resources
ASHA
93.85 = 0.25
3.0h + 0.6h
1.0x
200.0 = 0.0
PASHA
93.57 + 0.75
1.3h + 0.6h
2.3x
36.1 + 50.0
One-epoch baseline
93.30 + 0.61
0.3h +: 0.0h
8.5x
1.0 0.0
CIFAR-10
Two epoch baseline
92.75
0.7h
2.0 0.0
Three epoch baseline
93.47
0.71
1.0h 0.0h
2.8x
3.0 0.0
Five epoch haseline
93.38
0.90
1.7h + 0.0h
1.7x
5.0 0.0
Random buseline
72.88 1: 19.20
0.0h 1: 0.0h
N/A
0.0 0.0
ASHA PASHA
71.69 = 1.05
3.2h -:
1.0x
200.0 0.0
71.84 = 1.41
0.9h 0.4h
3.4x
20.5 48.3
One-epoch bascline
65.57 = 5.53
0.3h 0.0h
9.2x
1.0 0.0
CIFAR-100
Two-epoch baseline
68.28 = 4.25
0.7h
4.6X
20 0.0
Threc-epoct baseline
70.47
1.hh 0.0h
3.1X
30 0.0
Five-epoch baseline
70.95 0.95
1.7h
1.8x
5.0 0.0
Random haseline
42.83 + 18.20
0.0h + 0.0h
N/A
0.0 0.0
ASHA
45.63 = 0.81
8.8h + 2.2h
1.0%
200.0 0.0
PASHA
45.13 = 1.51
2.9h + 1.7h
3.1x
21.3 +.3++00 48.1
One-epoch baseline
41.42 4.98
1.0h + 0.0h
8.8x
+.0 0.0
ImageNet16-12)
Two-epoch baseline
2.0h
4,4%
2. 0.0
Three-epoch buseline
44.65
0.95
3.0h
2.9x
3,0 0.0
Five-epoch haseline
44.75
1.03
5.0h + 0.1h
1.8x
5.0 0.0
Random buseline
20.75 1:
9.97
0.0h 1: 0.0h
N/A
0.0 1 0.0
Table 7: Results of the HPO experiments on WMT and ImageNet tasks from the PD1 benchmark. Mean and std of the best validation accuracy (or equivalent as given the PD1 benchmark).
Dataset
Approach
Accuracy (%)
Runtime
Speedup factor
Max
ASHA
62.72 + 1.41
43.7h + 37.2h
1.0x
1357.4 + 80,4
PASHA
62.04 t 2.05
2.8h + 0.6h
15.5x
37.8 : 21.6
One-epoch baseline
62.36 + 1.40
0.6h + 0.0h
67.3x
1.0 0.0
WMT
Two-epoch baseline
60.16 + 3.58
1.1h + 0.0h
39.1x
2.0 0.0
Three-epoch baseline
61.12 + 3.47
1.6h + 0.0h
27.6x
3,0 0.0
Five-epoch baseline
57.89 + 5.33
2.5h
0.0h
17.3x
5.0 0.0
Random baseline
33.93 21.96
0.0h
0.0h
N/A
0.0
ASHA
75.10 + 2.03
7.3h + 1.2h
1.0x
251.0 0.0
PASHA
73.37 + 2.71
3.8h + 1.0h
1.9x
45.0 30.1
One-epoch baseline
63.40 + 9.91
1.th + 0.0h
6.7x
1.0 0.0
ImageNet
Two-epoch baseline
64.61 + 10.81
1.7h + 0.0h
4.2x
2.0 0.0
Three-epoch baseline
68.74 3.79
2.3h
0.1h
3.2x
3.0 0.0
Five-epoch baseline
65.91 + 3.99
3.7h
0.1h
2.0x
5.0 0.0
Random baseline
36.94 + 31.05
0.0h
0.0h
N/A
0.0 0.0
B REDUCTION FACTOR
Table TableBshows shows the full set of results for our experiments with different reduction factors. The behaviour the same across all cases.
12

---

Published as a conference paper at ICLR 2023
Table 8: NASBench201 results with various reduction factors 7/-
Dataset
Reduction factor
Approach
Accuracy (%)
Runtime
Speedup factor
Max resources
ASHA
93.88 + 0.27
3.6h + 1.1h
1.0x
200.0 0.0
PASHA
93.53 1: 0.76
1.0h 1: 0.3h
3,5x
9.1 8.1
CIFAR-10
ASHA
93.75 + 0.28
2.4h + 0.6h
1.0x
200.0 0.0
PASHA
93.65 + 0.65
1.1h # 0.5h
2.3x
32.3 = 50.2
ASHA
71.67 0.84
3.8h + 1.0h
1.0x
200.0 0.0
PASHA
71.65 + 1.42
0.9h + 0.
4.2x
5.9 2.0
CIFAR-100
ASHA
71.43 + 1.13
2.7h
+ 0.9h
1.0x
200.0 = 0.0
PASHA
72.09 1. 1.22
1.0h 1 0.4h
2.8x
25.1 49.0
ASHA
46.09 +: 0.68
11.9h + 4.0h
1.0x
200.0 0.0
PASHA
45.35 + 1.52
2.8h +: 0.6h
4,2x
9.3 7.1
ImageNet16-122
ASHA
45.43 + 0.98
7.9h + 3.0h
1.0x
200.0 = 0.0
PASHA
45,52 1 1.30
2.9h 1 1.1h
2.8x
18.4 18.7
C EXPERIMENTS WITH ALTERNATIVE RANKING FUNCTIONS
C.I DESCRIPTION
PASHA employs ranking function whose choice is completely arbitrary. In our main set of experiments we used soft ranking that automatically estimates the value of by measuring noise in rankings. this set of experiments would like evaluate different criteria to define the ranking of the candidates. We describe the functions considered next.
C.1.1 DIRECT RANKING
As baseline, we study if we can use the simple ranking of configurations by predictive performance (e.g., sorting from the ones with the highest aceuracy the ones with the lowest). If any of the configurations change their order, we consider the ranking unstable and increase the resources.
C.1.2 SOFT RANKING VARIATIONS
We consider several variations of soft ranking. The first variation is to fix the value of the parameter. We have considered values 0.01, 0.02, 0.025, 0.03, 0.05. The second set of variations aim estimate the value of automatically, using various heuristics. The heuristics we have evaluated include:
Standard deviation: calculate the standard deviation of the considered performance measure (e.g. accuracy) of the configurations the previous rung and multiple of it as the value of E we tried multiples 1, and 3.
Mean distance: value of e is set as the mean distance between the score of the configurations in the previous rung.
Median distance: similar to the mean distance, but using the median distance.
There are various benefits for estimating the value of by measuring noise in rankings, as presented our paper:
There is no need set the value of manually.
Estimation of has an intuitive motivation that makes sense.
The value of can dynamically adapt to the different stages of hyperparameter optimization.
The approach works well in practice.
C.1.3 RANK BIASED OVERLAP (RBO) (WEBBER AL.. 2010)
score that can broadly interpreted as weighted correlation between rankings. We can specify how much want prioritize the top of the ranking using parameter p that is between 0.0 and 1.0,
13

---

Published as a conference paper at ICLR 2023
with smaller value giving priority to the top of the ranking. The best value is 1.0, while it gives value of 0.0 for rankings that are completely the opposite. We compute the RBO value and then compare it to the selected threshold t, increasing the resources if the value is less than the threshold.
C.1.4 RECIPROCAL RANK REGRET (RRR)
A key insight is that configurations can be very similar to each other and differences in their rankings will not affect the quality of the found solution significantly. To account for this we look at the objective values of the configurations (e.g. accuracy) and compute the relative regret that we would pay at the current rung we would have assumed the ranking at the previous rung correct.
We define reciprocal rank regret (RRR)
(Ji - RRR Σ 1=0
f
where I represents the ordered scores in the top rung, represents the reordered scores from the top rung according to the second rung, is the number of configurations the top rung and p is the parameter that says how much attention give the top of the ranking. The weights wy sum and can be selected in different ways to c.g. give more priority to the top of the ranking. For example, we could use the following weights:
The metric has an intuitive interpretation: it is the average relative regret with priority on top of the ranking. The best value of RRR is 0.0, while the worst possible value is 1.0.
We also consider version of RRR which considers the absolute values of the differences in the objectives- Absolute RRR (ARRR).
We have evaluated these additional ranking functions using NASBench201 benchmark.
C.2 RESULTS
We report the results in Table 9 10 and We there also several other variations that achieve strong results across variety of datasets within NASBench201, most notably soft ranking 20 and variations based on RRR. In these shorter time. We additionally also give a similar analysis in Table [2] (analogous to Table 4 where we analyse a selection of the most interesting ranking functions for the PD1 benchmark.
obtain similar performance as ASHA, but at significantly
14

---

Published as a conference paper at ICLR 2023
Table 9: NASBench201 CIFAR-10 results for a variety of ranking functions.
Approach
Accuracy (%)
Runtime
Speedup factor
Max resources
ASHA
93.85 + 0.25
3.0h + 0.6h
1.0x
200.0 = 0.0
PASHA
93.57 + 0.75
1.3h =: 0.6h
2.3x
36.1 50.0
PASHA direct ranking
93.79 0.26
0.6h
1.1x
198.4 6.0
PASHA soft ranking = 0.01
93.79 + 0.26
2.6h + 0.5h
1.1x
194.3 = 21.2
PASHA soft ranking 0.02
93.78 + 0.31
2.4h - 0.Sh
1.2x
152.4 = 58.3
PASHA soft ranking 0.025
93.78 + 0.31
2.3h 0.5h
1.3x
144.5 = 59.4
PASHA soft ranking 0.03
93.78 0.32
2.2h 1.66
1.3x
128.6 58.3
PASHA soft ranking 0.05
93.79 0.49
18hh 0.7h
1.6x
76.0 66.0
PASHA soft ranking la
93.75 + 0.32
2.4h + 0.5h
1.2x
186.4 = 35.2
PASHA soft ranking 2n
93.88 + 0.28
1.9h + 0.5h
1.5x
132.7 = 68.7
PASHA soft ranking 30
93.56 + 0.69
0.9h + 0.3h
3.1x
16.2 = 19,9
PASHA soft ranking mean distance
93.73 + 0.52
2.3h + 0.4h
1.3x
184.1 = 40.5
PASHA soft ranking median distance
93.82 + 0.26
2.3h + 0.5h
1.3x
169.2 51.2
PASHA RBO p=1.0, 1=0.5
93.49 0.78
0.1h
4.2x
= 6.0
PASHA RBO
p=0.5, t=0.5
93.77 + 0.35
2.2h + 0.6h
1.3x
144.0 = 71.2
PASHA RRR p=1.0, (=0.05
93.49 + 0.78
0.7h + 0.0h
4,4x
3,0 0.0
PASHA RRR p=0.5, t=0.55
93.76 + 0.31
2.1h + 0.6h
1.4x
140.9 69.7
PASHA ARRR p=1.0 t0005
93.71 0.35
2.4h 0.4h
1.2x
179.0 42.9
PASHA ARRR p=0.5, t=0.55
93.81 0.30
0.4h
1.2x
181.0
40.9
One- One-epoch baseline
93.30 + 0.61
0.3h + 0.0h
8.5x
1.0 0.0
Random baseline
72.88 + 19.20
0.0h + 0.0h
N/A
0.0 = 0.0
Table 10: NASBench201 CIFAR-100 results for variety of ranking functions.
Approach
Accuracy (%)
Runtime (s)
Speedup factor
Max
ASHA
71.69 + 1.05
3.2h + 0.9h
1.0x
200.0 = 0.0
PASHA
71.84 + 1,41
0.9h + 0.4h
3.4x
20.5 = 48.3
PASHA direct ranking
71.69
1.05
0.7h
1.1x
200.0 = 0.0
PASHA soft ranking = 0.01
71.55 + 1.04
2.5h + 0.7h
1.3x
198.3 - 6.5
PASHA soft ranking
0.02
70.94 + 0.85
2.0h + 0.5h
1.6x
160.5 = 62.9
PASHA soft ranking 0.025
71.41 + 1.15
1.Sh + 0.7h
2.1x
88.3 = 74.4
PASHA soft ranking 0.03
71.00 1.38
1.0h 0.5h
3.2x
39.4 63.4
PASHA soft ranking 0.05
70.71 = 1.66
0.7h + 0.0h
4.9x
3.0 = 0.0
PASHA soft ranking lo
71.56
1.03
2,5h 0.6h
1.3x
184.1 = 40.5
PASHA soft ranking 2o
71.14
0.97
1.9h + 0.7h
1.7x
136.4 = 75.8
PASHA soft ranking 3o
71.63 + 1.60
1.0h + 0.3h
3.3x
20.2 = 25.3
PASHA soft ranking mean distance
71.51 + 0.99
2,4h + 0.5h
1,4x
189,8 30.3
PASHA soft ranking median distance
71.52
0.98
2.4h + 0.6h
1.3x
189.5 30.6
PASHA RBO p=1.0, 1=0.5
70.69
1.67
0.7h + 0.1h
4.6x
2.0
PASHA RBO p=0.5, t=0.5
71.51
0.93
2.4h + 0.7h
1.3x
180.5 50.6
PASHA RRR p=1.0, t=0.55
70.71 + 1.66
0.7h + 0.0h
4.9x
3.0 = 0.0
PASHA RRR 0=0.5, t=0.5
71.42 + 1.51
1.2h + 0.5h
2.6x
39.3 = 51.4
PASHA ARRR p=1.0. 1=0.55
70.80
1.70
0.8h 0.4h
3.8x
22.9 51.3
PASHA ARRR p=0.5, t=0.55
71.41 1.05
1.8h + 0.6h
1.7x
110.0 68.7
One-epoch haseline
65.57 + 5.53
0.3h + 0.0h
9.2x
1.0 - 0.0
Random baseline
42.83 + 18.20
0.0h + 0.0h
N/A
0.0 = 0.0
15

---

Published as a conference paper at ICLR 2023
Table 11: NASBench201 ImageNer16-122 results for a variety of ranking functions.
Approach
Accuracy (%)
Runtime (s)
Speedup factor
Max resources
ASHA
45.63 + 0.81
8.8h + 2.2h
1.0x
200.0 = 0.0
PASHA
45.13 + 1.51
2.9h + 1.7h
3.1x
21.3 = 48.1
PASHA direct ranking
45.63 0.81
8,3h + 2.5h
1.1x
200.0 = 0.0
PASHA soft ranking 0..11
45.52 + 0.89
+ 1.5h
1.3x
185.7 = 36.1
PASHA soft ranking 0.02
45.79 + 1.16
4.4h + 1.4h
2.0x
71.4 50.8
PASHA soft ranking 0.025
46.01 + 1.00
3,2h + 1.0h
2.8x
28.6 = 27.7
PASHA solt ranking 0.03
45.62 + 1.48
2.4h = 0.7h
3.6x
11.0 = 10.0
PASHA soft ranking 0.05
44.90 = 1,42
1,8h + 0.0h
5.0x
3.0 = 0.0
PASHA soft ranking
45.63
1.3h
177.1 = 44.2
PASHA soft ranking
45.39
1.4h
91.2 = 58.0
PASHA soft ranking 30
44.90
1.42
1.8h + 0.0h
5.0x
- 0.0
PASHA soft ranking mean distance
45.50 + 1.12
6.2h + 1.5h
1.4x
157.7 = 54.7
PASHA solt ranking median distance
45.67 + 0.95
6.3h + 1.6h
1.4x
156.3 = $2.2
PASHA RBO p=1.0, t=0.5
44.90 1.42
1.8h + 0.0h
5,0x
3.0 = 0.0
PASHA RBO p=0.5, t=0.5
45.24 1.13
6.4h 1.3h
1.4x
148.3 56.9
PASHA RRR p=1.0,
1.0, t=0.05
44.90 + 1.42
1.8h + 0.0h
5.0x
3.0 = 0.0
PASHA RRR p=
t=0.5
44.90 + 1.42
1.8h + 0.0h
5.0x
3.0 = 0.0
PASHA ARRR p=1.0, t=0.55
44.90 + 1.42
1,8h + 0.0h
5,0x
3.0 = 0.0
PASHA ARRR p=0.5, t=0.55
44.90 1.42
1.8h + 0.0h
5.0x
3.0 = 0.0
Oue-epoch baseline
41.42
4.98
0.0h
8.8x
= 0.0
Random haseline
20.75
9.97
0.0h + 0.0h
- 0.0
Table 12: Results of the HPO experiments WMT and ImageNet tasks from the PD1 benchmark. using a selection of the most interesting candidates for ranking functions. Mean and std of the best validation accuracy (or its equivalent given in the PD1 benchmark).
Datasel
Approach
Accuracy (%)
Runtime
Speedup factor
Max resourves
ASHA
62.72 +:2 1.41
43.7h ::: 37.2h
1.0x
1357.4 = 80.4
PASHA
62.04 + 2.05
2.8h = 0.6h
15.5x
37.8 = 21.6
PASHA dircet ranking
62.16 + 1.75
39.3h 38.3h
1.1x
1024.0 466.6
PASHA ranking 2.5%
62.09
2.04
1.3h 0.4h
33.4x
4.2
2.4
WMT
PASHA soft ranking 2n
62.52 + 2.18
1.1h 0.1h
38.8x
3.0
0.0
PASHA RBO p=0.5, t=0.5
61.44 + 1.23
6.7h = 7.8h
6.5x
147.6 = 113.2
PASHA RRR p=0.5, t=0.05
62,52 + 2.18
1.1h + 0.1h
38.8x
3.0 + 0.0
One-epoch baseline
62.36 +: 1.40
0.6h + 0.0h
67.3x
1.0 + 0.0
Random baseline
33,93 1 21.96
N/A
0.0
0.0
ASHA PASHA
75.10 + 2.03
7.3h 1.hh
L.0x
251.0
0.0
73.37 1: 2.71
1.0h
30.1
PASHA direct ranking
75.10 1: 2.03
6.8h
0.7h
1.1X
247.8
3.9
PASHA soft ranking 2.5%
74.73 + 1.99
4.3h = 2.5h
1.7x
140.4
112.8
ImageNet
PASHA soft ranking 2g
75.82 + 0.82
5.0h + 1.hh
1.5%
133.0 = 96.8
PASHA RBO p=0.5, t=0.5
74.80 + 2.19
4.4h + 2.1h
117.4 = 109.4
PASHA RRR p=0.5, t=0.05
+ 2.12
1.6h 0.0h
4.7x
3.0
0.0
One-epoch bascline
63,40 + 9,91
1.bh
6.7%
1.0 0.0
Random baseline
36.94 + 31.05
0.0h - 0.0h
N/A
0.0 = 0.0
16

---

Published as a conference paper at ICLR 2023
D ADDITIONAL RESULTS ON LCBENCH
We additionally evaluate PASHA on the LCBench benchmark (Zimeer et al. 2021 where only modest speedups can be expected due small number of epochs (and hence rungs) available. LCBench limits the maximum amount of resources per configuration to 50 epochs, so when using and setting minimum resource level to epoch, a challenging testbed for an algorithm like PASHA. The hyperparameters optimized include number of layers E [1, 5]. max. number of units [64, 1024] (log scale), batch size E [16, 512] (log scale), learning rate E [10- -0-1 weight decay E [10-5, 10- momentum E [0.1, 0.99) and max. value of dropout E [0.0, 1.0]. Similarly as in our other experiments, we use and stop after sampling 256 candidates.
10-1] (log scale),
Overall, the results in Table 13 confirm accuracy level on-par with ASHA. While, expected, the speedup is reduced compared to the experiments on NASBench, in several cases PASHA achieves a 20+% speedup with peaks around 40%.
only a small number of epochs is sufficient for training the model on the given dataset, then HPO be performed sub-epoch basis, e.g. defining the rung levels in terms of iterations instead of epochs. PASHA would then be able to give large speedup even in cases with smaller numbers of epochs example of which is LCBench.
Table 13: Results of the HPO experiments on the I.Bench benchmark. Mean and std of the test accuracy across five random seeds. PASHA achieves similar accuracies as ASHA, but gives only modest speedups because of the limited number of rung levels and opportunities to stop the HPO early. To enable large speedup from PASHA, could redefine the rung levels in terms of neural network weights updates rather than epochs.
Dataset
ASHA accuracy (%)
PASHA accuracy (%)
PASHA speedup
APSFailure
97.52 + 0,92
97.01 + 0.75
1.3x
Amazon_ene _employee_acoess
94.01 0.40
94.21 + 0.00
1.1x
Australian
83.35 = 0.33
83.35 + 0.51
1.1x
MushT
86.70 1.87
86.34 1.32
1.1x
KDDCup09 juppetency
98.22 0.00
98.22 - 0.00
1.1x
MiniBooNE
86.13 1.57
86.24 1.62
1.4x
Adult
79.14 0.85
79.14
1.2x
Airlines
59.57 1.32
59.22 0.76 0.76
1.4x
Alhert
64.31 0.99
64.23 0.61
1,2x
Bank-marketing
88.34 0.07
88.38 0.00
1.2x
79.92 0.20
76.99 -
1.1x
Car
6.41
86.60 - 6.41
1.1x
Christine
71.05 1.17
70.15 + 1.85
1.2x
Cnae-9
94.10 + 0.31
94.44 0.11
1.0x
Connect-4
62.28 + 6.87
65.69 - 0.04
1.2x
Covertype
59.76 = 3.24
61.64 + 1.64
1.2x
Credit-g
70.30 = 0.84
70.79 + 0.68
1.1x
Dionis
64.58 9.89
64.58 + 9.89
1.1x
Fabert
56.11 10.89
53.47 + 9.75
1.1x
Helena
19.16 3.20
19.16 + 3.20
1.1x
Higgs
66.48 3.16
66.48 + 3.16
1.1x
Jannis
58.92 2.38
59.63 + 2.81
1.4x
Jasmine
75.85 0.36
75.55 - 0.68
1,0x
Jungle_chess,2pes, raw
www.eeeeeeeaaeeeeaaaeeeee lenggame candgame_comjjn complete
72.86 4.69
74.94 + 7.84
1.3x
Kel
80.32 4.37
80.86 -: 3.37
1.2x
Kr-vs-kp
92.50 3,93
90.95 4.70
Mfeat-factors
98.21 0.15
98.15
Nomao
94.12 + 0.60
94.25 + 0.64
1.1x
Numerai28.6
52.03 0.55
52.30 - 0.24
1.3x
Phoneme
76.65 2.65
75.42 - 2.87
1.1x
Segment
83.15 + 2.54
83.15 + 2.54
1.0x
Sylvine
90.57 + 1.87
90.89 + 24
1.0x
Vehicle
71.76 2.57
71.76 + 2.57
1.1x
Volkert
50.72 1.91
50.72 + 1.91
1.1x
17

---

Published as a conference paper at ICLR 2023
E INVESTIGATION WITH VARIABLE MAXIMUM RESOURCES
We analyse the impact of variable maximum resources (number epochs) on how large speedup PASHA provides over ASHA. More specifically, we change the maximum resources available for ASHA and also the upper boundary on maximum resources for PASHA. We utilize NASBench201 benchmark for these experiments and set the number of epochs to 200 (default) or 50 (other details are the same as earlier). The results in Table [4] confirm that PASHA leads to larger speedups when there are more epochs (and rung levels) available. This analysis also explains the modest speedups on ICBench analysed earlier.
the model trained for small number of epochs, is worth redesigning the HPO so that there are more rung levels available, enabling PASHA to give larger speedups. This can be achieved by using sub-epoch resource levels - specifying the rung levels and the minimum resources terms of the number of iterations (neural network weights updates), Based on the results observed across various benchmarks, we would recommend having at least rung levels in ASHA, with more rung levels leading to larger speedups from PASHA over ASHA.
Table 14: NASBench201 results. more epochs.
PASHA leads to larger speedups if the models trained with
Dataset
Number epochs
Approach
Accuracy (5))
Runtime
Speedup factor
Max
ASHA
93.85 1: 0.25
3.0h :: 0.6h
1.0k
200.0 + 0.0
200
PASHA
93.57 : 0.75
1.3h + 0.6h
2.3x
36.1 = 50.0
CIFAR-10
ASHA
93.78 1: 0.39
1.8h 1: 0.2h
1.0x
50.0 : 0.0
PASHA
93.58 : 0.75
1.2h = 0.4h
1.5x
22.0 = 1688
ASHA
71.69 = 1.05
3.2h + 0.9h
1.0x
200.0
200
PASHA
71.84 1.41
0.9h :: 0.4h
3.4x
20.5 = 48.3
CIFAR-100
50
ASHA
7
1.8h + 0.3h
1.0x
$0.0 0.0
PASHA
0.9h 0.3h
2.0x
10.5 12.1
ASHA
45.63 1: 0.81
8.8h 2.2h
1.0x
200.0 +: 0.0
ImageNett6-111
PASHA
45.13 4: 1.51
2.9h 1.7h
3.1x
21.3 48.1
ASHA
45.97 0.99
= 0.7h
1.0x
50.0
50
PASHA
45.09 1.52
2.7h + 1.0h
1.9%
11.3 11.7
F ANALYSIS OF LEARNING CURVES
We analyse the NASBench201 learning curves in Figure 3 and and easier to grasp, we first sample a random subset of 256 configurations, similarly as do for our NAS experiments. Figure 3 shows the learning curves of the top three configurations (selected in terms of their final performance). We see that these learning curves are very close to each other and frequently cross due to noise in the training, allowing to estimate meaningful value of parameter (configurations that repeatedly swap their order are very likely to be similarly good, so we select any of them because the goal is to find strong configuration quickly rather than the very best one). Figure shows all learning curves from the same random sample of 256 configurations. In this case can that the learning curves relatively well-behaved (especially the ones the top), and any exceptions are rare.
To make the analysis realistic and
18

---

Published as a conference paper at ICLR 2023
Vildeaion accurary (N)
CIFAR-10
CIFAR-100
Volidaation accuracy (A4
ImageNee15-120
18.
Voltdation accurary
12
78.
8.
18.
3
Epoch
Epoch
Epoch
Figure 3: Analysis of how the learning of the top three configurations (in terms of final validation accuracy; from random sample of 256 configurations) evolve across epochs. We see that such similar confi configurations frequently change their ranks, enabling us calculate a meaningful value of e parameter.
CIFAR-10
CIFAR-100
ImageNat16-120
Velidation accuracy
62-
Validation accuracy
60.
Validation
20-
Figure 4: Analysis of what the learning curves look like for random sample of 256 configurations. We see that the learning curves are relatively well-behaved (especially the ones at the top), and any exceptions are rare.
G INVESTIGATION OF HOW VALUE EVOLVES
We analyse how the value of that is used for calculating soft ranking develops during the HPO process. We show the results in F for the three different datasets available in NASBench201 (taking seed). The results show the obtained values of are relatively small.
CIFAR-10
CIFAR-100
ImageNet16-120
nus
Value ofF
Value of
Velue
0.31
0.0
0.30
0.55
0.0
0.82
0.2
307
1207
220
600
952
300
Number of updates received
Number of updetes received
Number of updates received
Figure 5: Analysis of how the value of e evolves receive additional updates about the perfor- mances of candidate configurations. Note that most of the updates are obtained the top rung due to how multi-fidelii methods work.
19

---

Published as a conference paper at ICLR 2023
H INVESTIGATION OF PERCENTILE VALUE N
We investigate the impact of using various percentile values N used for estimating the value of in Table [5] The intuition is that distance in case there are some outliers. We see that the results are relatively stable, even though larger value of N can lead to further speedups. However, from the point view of practitioner would still take N = 90 in case there are any outliers in the specific new use-case.
take some value on the top end rather than the maximum
Table 15: NASBench201 results. PASHA leads to large improvements in runtime, while achieving similar accuracy ASHA. Investigation of various percentile values (N) to use for calculating parameter 6.
Dataset
Approach
Accuracy (%)
Runtime
Speedup factor
Max resources
ASHA
93.85
0.25
3.0h = 0.6h
1.xx
200.0 0.0
PASILA N 100%
93.70
0.61
1.0h 1 0.4h
3.0x
13.8 19.5
PASHA
95%
93.64
1.0h 0.4h
2.8x
15.4 1
CIFAR-IO
PASHA N 90%
93.57
1.3h 0.6h
2.3x
PASIIA N 80%
93.86
0.53
1.5h 0.6h
1.9x
60.9 60.7
One-epoch baseline
93.30
0.61
0.3h = 0.0h
8.5x
1.0 0.0
Random baseline
72.88
19.20
0.0h + 0.0h
N/A
0.0 + 0.0
ASHA
71.69 + 1.05
3.2h = 0.9h
1.0x
200,0 = 0.0
PASHA N = 100%
71.84 + 1.41
0.8h + 0.
3.9x
6.6 + 2.9
PASHA N 95%
71.84 + 1.41
0.8h = 0.1h
3,9x
6.6 2.9
CIFAR-100
PASIIA N 90%
71.91 1 1.32
0.9h 1 0.3h
3.5x
12.6 19.2
PASHA N 80%
71.78
1,2h 0.6h
2.6x
76.2
One-epoch baseline
65.57
0.3h 0.0h
9.2x
1.0
Random baseline
42.83
18.20
0.0h 0.0h
N/A
0.0 0.0
ASHA
45.63
0.81
8.8h 2.2h
200.0 0.0
PASHA N 100%
45.09
1.61
2.3h 0.4h
3.7%
7.0 + 2.8
PASHA N 95%
45.26 + 1.58
2.4h = 0.4h
3.7x
7.4 2.7
ImageNet 16-12
PASHA N = 90%
45.13 + 1.51
2.9h + 1.7h
3.1x
21.3 48.1
PASHA N = 80%
45.36
1.38
3.6h = 1.2h
2.5x
40.5 4 47.7
One-cpoch baseline
41.42 + 4.98
1,0h = 0.0h
1.0 0.0
Random baseline
20.75
0.0h
0.0
20


Reviews:
[{"review_id": "xxchXgJ4PT", "reviewer": "Reviewer_KgTC", "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": "This paper presents a new approach that extends the multi-fidelity optimization approach Asynchronous Successive Halving (ASHA) to Progresive ASHA by iteratively increasing the maximal budgets that are allocated to the candidates configurations. Specifically, the optimization process ends if the ranking of the candidate configurations stabilizes in successive two rungs (rounds of promotion). Experiments show that PASHA can significantly reduce the amount of optimization time while still identifying the optimal configuration\n", "summary_of_the_review": "This paper provides a simple yet efficient multi-fidelity optimization approach Progresive ASHA (PASHA) that yields a great speed up while maintaining similar performances when doing multi-fidelity optimization. However, some details are missing or not well supported by the experiments. Therefore, I tend to believe that this paper is not ready to be published at the current stage; maybe nevertheless, if the authors can clarify all of the above points, I would be willing to improve my final score.\n", "strength_and_weaknesses": "The authors propose a simple (which is a good characteristic in general) and efficient method based on the assumption that most “cross points” of learning curves occur in the very initial part of the training procedure.  In fact, for users, it is not an easy task to determine the budget steps correctly. So, a contribution to automate this will be highly appreciated and is very timely.\n\nOverall this paper is well-motivated and clearly written. This paper will address the known issue of multi-fidelity optimization: determining the maximal budgets for SHA is hard. Additionally, given the empirical observations of the related work, the authors then propose their own approach in a clear manner and well address the potential issues that appear in their approach.  \n\nHowever, some details are missing or not clear enough for me to understand the paper. Additionally, as this paper presents a heuristic idea, I would like to see a thorough ablation study on PAHSA and a fair comparison with other baselines (see my below comments for details)\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "w3tAENUGVd", "reviewer": "Reviewer_ZU68", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper proposes a new HPO algorithm named PASHA. It is an extension of ASHA which was itself an asynchronous extension of Successive Halving. PASHA leverages the idea that learning curves rarely \"cross\" to derive a novel early stopping rule: PASHA stops allocating resources to configurations at the highest rungs when their relative rankings did not change from the previous rung. They show empirically that PASHA's found best configurations achieve comparative test accuracy to ASHA's while achieving significant speedup.", "summary_of_the_review": "PASHA's empirical performance is impressive throughout the comprehensive test settings and compared to suitable baselines. The core technical idea is novel and grounded in reasonable assumptions. The paper is well written.", "strength_and_weaknesses": "Strengths:\n1. The approach is elegant and the primary assumption that learning curves rarely \"cross\" is supported by previous work.\n2. The experiments section is comprehensive and the results are impressive.\n\nWeaknesses:\n1. Algorithm 1 is somewhat hard to parse. Some additional comments explaining that $R_t$ and $K_t$ are the current maximum budget and maximum rung might be useful. Also, while Figure 1 is useful for getting the main idea across, a simple sample trajectory of PASHA in the appendix would have been very useful in understanding the finer details of how PASHA handles asynchronicity and growing the bottom rung while still testing higher rungs. \n\n2. Is $N$ (the percentile of distances for the automatic estimation of $\\epsilon$) a hyperparameter and if so, should it be an input to Algorithm 1?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "b5ay66SqTc", "reviewer": "Reviewer_oH7E", "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": "This paper studies the problem of efficient resource allocation by identifying the well-performing configurations for hyperparameter optimization and neural architecture search. The goal is to find the best (or close to the best) configurations while using as few computational resources as possible, leading to a faster algorithm.\n\n\nThe authors propose an algorithm named PASHA (Adaptive ASHA), a variant of the existing state-of-the-art algorithm ASHA for the same problem. Compared to a fixed amount of maximum resources for each iteration in ASHA, PASHA initially starts with a small amount of maximum resources and then gradually increases as needed. The authors have empirically validated that the PASHA is faster than ASHA while incurring a minimal penalty on the final model's accuracy on HPO and NAS datasets.", "summary_of_the_review": "This paper has some overlap with my current work. My recent work was focused on closely related topics and I am knowledgeable about most of the topics covered by the paper.", "strength_and_weaknesses": "**Strengths of paper:**\n1. The problem studied in the paper is interesting and has many real-life applications, as some of them (HPO and NAS) are mentioned in this paper.\n\n2. The authors empirically show that their proposed algorithm speeds up on HPO and NAS datasets while only having minimal performance degradation.\n\n\n**Weaknesses of paper:**\n1. Main weakness of the paper is its novelty, as it is an extension of existing work (algorithm ASHA). \n\n2. The word 'efficient' is used in the title, which signifies that their algorithm achieves the best performance. However, apart from empirical results, there is no principled way to say that their algorithms in indeed efficient.  \n\n3. No theoretical guarantee: There is no theoretical guarantee of how far (in terms of accuracy) the final model is after using PASHA from the best possible model.\n\n4. It is unclear how to choose the value of $\\epsilon$ principled way. This choice is important as choosing very small or large $\\epsilon$ adversely affects the performance.\n\n**Question and other comments.** \n\nPlease address the above weakness. I have a few more questions/comments:\n1. Can PASHA exploit the estimated function values (like BO) to choose the next configurations?  \n2. In conclusion: Mention the dataset name instead 'the largest dataset with millions of training examples.'\n\nI am open to changing my score based on the authors' responses.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_hn8uN6kZk", "reviewer": "Reviewer_tjkb", "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": "The paper identifies the problem of high practical costs even in parallelizable, efficient, multi-fidelity hyperparameter optimization (HPO) methods when it comes to modern, large, deep learning models. The primary contribution is a modification of the popular Asynchronous Successive Halving (ASHA) method that can dynamically choose if a configuration should be evaluated longer to keep making decisions on the best-found configuration. \n\nThe proposed algorithm, Progressive-ASHA (PASHA), is a rather simple and intuitive extension to ASHA where a noise measure is dynamically tracked based on the set of partial learning curves seen that criss-cross each other. A soft ranking measure is used for the tournament in the ASHA rungs, where multiple configurations can share a rank if their performances at the highest recorded epoch is within the noise calculated. If only such rankings are ever changed in the top two consecutive rungs, a new higher rung is added based on ASHA. Thus, the maximum resource ($R$) hyperparameter to ASHA is not a strict requirement for PASHA and only is the upper bound of epochs for any configuration. The method appears to offer impressive speedups over ASHA. Not necessarily in superior performance, but generally reaches ballpark performance much quicker. Therefore, PASHA could be seen as an alternative to ASHA to be quicker, or be seen as an improvement to ASHA altogether. \n", "summary_of_the_review": "The paper is a nicely motivated, well-written work of a simple and intuitive idea that was put together effectively in working code. The scope is one of an important need to the community and on practical grounds, the algorithm PASHA offers itself as a potential candidate to be used in place of ASHA. Thus, in practice, there is evidence to suggest that PASHA can be a viable, practical and efficient option. However, in terms of a manuscript that researchers can cite to base newer algorithms on PASHA, just as PASHA does with ASHA, it falls short. The experiment setup is not 100\\% clear and coherent after a few passes of the paper (have not seen the code). The empirical evidence thus feels inadequate. Moreover, given the strong assumptions on learning curves that PASHA is based on, the entire experiment setup, benchmarks, LCs are all very black-box and don't help convince the use of PASHA as a general HPO algorithm for an unknown task.", "strength_and_weaknesses": "Strengths:\n\n* Relevant and well-placed motivation and problem statement.\n* Takes an existing, popular algorithm to potentially improve it and lower computational costs in achieving similar results.\n* Simplicity of the approach and seemingly easy-to-implement changes to ASHA.\n* Relaxes the need for one of the 2 important ASHA hyperparameters (assuming  $\\eta=3$ is standard).\n* Incorporates the possibility of LCs crisscrossing, unlike vanilla ASHA.\n* Implementation integrated into an existing library SyneTune.\n\nWeaknesses:\n\nA) Incoherency stems when reading more of the paper.\n  1. It is not clear what *training from scratch* means on Page 1 given the setup of the problem. When the algorithm proposed is designed where the user is not expected to design or choose the max resource $R$, does training from scratch implies training till convergence? This means the training can be till $<R$, $=R$ or  $>R$. And thus it seemed that the tables reported are for this number. \n  2. Similarly, for Random Search (RS) as mentioned at the end of Section 5.1, it is not clear what *look up* means in the cost of a benchmark where a learning curve can be queried anywhere. One would presume, RS is the performance of a configuration at the $R$ available for NAS-201. If so, the table is further confusing. Given RS uses the same seeds as PASHA and ASHA and samples 10x more times, it should recover the configs found by PASHA and ASHA. Both of these will likely select different incumbents. When reporting the performance of training from scratch, the incumbent performance is taken to be the best till convergence (*epochs* $\\in[r, R]$). However, RS reports the performance for those incumbents at a (potentially) higher epoch $R$. It is a bit confusing.\n  3. The introduction highlights the example of one of the large language models from 2019 and its associated cost. We have much larger models and potentially more expensive ones. However, the strong assumptions made about the shape of LCs seem to be from literature not to do with this problem scope. It is not that the citations are misplaced but rather the expectation set for the reader was a bit different in the beginning. However, this relates to the only Transformer based benchmarks in the experiments in Section 5.3, and PASHA is underwhelming there.\n\nB) Strong assumptions that go into the design of the algorithm and the experiments.\n  1. The existence of crossing points only at the beginning of training is a strong one. Given the subtleties of incumbent selection and promotion of configurations involved. The literature cited as reference points to LCs over data subsets and other well-behaved parametric forms of learning curves. \n  2. One argument is that ASHA doesn't even consider this so PASHA is doing better there. However, Hyperband's sampling at different rungs was shown to be crucial in handling crisscrossing LCs. One could cite that as a possible reason for Mobster being better than PASHA in terms of performance. \n  3. Though PASHA could argue that it prevents unnecessary evaluations at higher fidelities/rungs, there is not enough motivation to not be sampling directly at the rungs already allowed for (L32 in Algorithm 1 returns the base rung).\n  4. This is especially important to understand given that PASHA makes assumptions on the performance correlation across rungs in its dynamic heuristic. Especially looking at the RS numbers in the experiments, one wonders what the shapes of the LCs are in the benchmarks as they suggest heavy divergence with more budget. This intuitively may not be the case for the recent large models. \n  5. Section 4.2 is entirely dependent on this assumption and is one of the key points in the paper. Looking at the conjunction in the definition of set $S$, at least 3 rungs are required for PASHA to work and find config pairs with crisscrossing. The inequalities over the disjunction suggest that a pair of configurations need to criss-cross at least twice. This seems to be linked to the earlier assumption, ''configurations that repeatedly swap their rankings...''. Again, a fair but strong assumption on which to base the primary contribution. Empirical evidence to support this is also weak. For example, visualizing LCs from the tabular benchmarks could be a great start to untangling this. \n  6. For large architectural spaces, the LCs could offer different convergence rates and might have just one crossing point. Based on the notation, this pairing will not be considered as part of noise calculation. Which sounds completely fine. However, quite clear that one of the improving LCs can never be promoted. Given PASHA has a view over this already by feature, one wonders if PASHA could tackle it. One defence for PASHA could be that look, ASHA too will fail here.\n\nC) Uclear or points which raise questions.\n  1. If 3 rungs are at least required for PASHA to be effective, does that mean the user should always go with the lowest possible minimum resource better than random, such that enough rungs can be found with the $log_{\\eta}(R/r)$ calculation? If so, this must be called out more clearly.\n  2. When set $S$ is constructed, pairs are collected based on the 3 highest rungs. After that, the noise $\\epsilon$ is calculated based only on the performance difference at the highest rung only. Soft ranking across rungs use this same $\\epsilon$. Given that the previous rung is $\\eta$ iterations earlier, I wonder if the noise estimated at different epochs/rungs should be done per rung. That is, not sure if the soft-ranking computation using $\\epsilon$ from noise at a higher rung is applicable to the lower rung. Also, given the earlier assumption of crisscrossing, isn't the noise in the higher rung to be lesser?\n  3. This further intrigues the evolution of $\\epsilon$ over a PASHA run. Especially to relate to the ablation with fixed $\\epsilon$. That is, does $\\epsilon$ shrink to zero as we go higher and thus naturally switch to ASHA? Or does the $\\epsilon$ stabilize and PASHA thus converges to a fixed ranking and never add a rung?\n  4. It is not at all clear how the incumbents are selected if no high-budget rungs are ever added. Since the top rank can be shared by multiple configurations, as they differ by the current $\\epsilon$. However, it seems that the incumbent $x^*$ is selected as the top-1 at a rung, going by L25 of Algorithm 1. Given the assumptions, not sure if this is the right thing to report and could potentially explain the underperforming of PASHA in many experiments. \n  5. This further raises the question of somehow the soft ranking should be used for the top-k calculation itself when selecting for promotions. If PASHA trusts the noise measure to declare that all performances within the $\\epsilon$ bound are similar so it is safe to stop early, it is counter-intuitive to do an $argmax$ within that $\\epsilon$ bound. \n  6. In Section 5.2 for the NAS-201 experiments, it is said that the predictive performance over both the validation+test sets are reported. This is confusing given the earlier problem setup of retraining over the full training set (training+validation). My current belief is that the incumbent was chosen over the performance of the validation set alone. The chosen incumbent's performance over both valid+test is shown in the table. However, I am not at all sure.\n  7. In Section 5.2 there's an impressive statement there regarding PASHA's total running time, which if true, should be highlighted more. However, what do the model training times mentioned there (1.3h & 4.1h) mean? Training a model for $R$ or *till convergence which could be $>R$. Not clear to me.\n\nD) One clear pathology that is not explored.\n  1. As I understand, PASHA will create 3 rungs to enable the noise calculation and soft ranking. There might be this one case that the ranking in the top-2 rungs never changes. In that case, I don't see how PASHA creates a new higher rung. I wonder if the low max resources in PASHA, reported in the tables, have anything to do with this. Pair that with the cases with comparable performances of 1-epoch baselines, it is tough to pinpoint if PASHA avoids this pathology. Or if this pathology is something to have when tackling a general, unknown HPO problem.\n\nOther comments:\n\n0. The Tables are difficult to parse, especially the ablations. Some guides to the reader could be provided with bolds, underlines, colours, etc.\n1. In Related Work, it is said that ASHA does better resource allocation than SH. I think given the use of *resource* in the paper, it should be called out that ASHA showed a better utilisation of *workers* in a parallel setting. In a synchronous single-worker case, it can be expected that SH's wider rung selections do better than ASHA in the beginning.\n2. Page 5, for example in the last paragraph might have a typo. If not, it was quite confusing to follow. If the top rung has 8 epochs and the previous rung had 4 (more likely than 6 with $\\eta=\\{2,3,4\\}$), it is said that config $c_c$ is at 6 epochs. That is one source of confusion. Secondly, the set of distances considered is across the rungs too. Whereas, in the previous paras it is said that only $(c, c')$ which have made it to the last rung are considered in the set $S$.\n3. Parsing of all results has been a bit of a swing from understanding to not being sure and back and forth, simply due to the lack of clarity I have on the evaluation protocol. Even for the one-epoch baseline, are we evaluating at $R$ for the table? Or is it the performances at 1-epoch? Since RS must recover this same configuration and evaluate at $R$. Does then the tables suggest that the selection procedure at 1-epoch is more reliable than $R$? Again, from the current paper draft, this is difficult to disentangle. \n4. Looking at the performance tables, it would be interesting to see ASHA's performances and speedups given the max resources a run of PASHA explores. That would create different rungs and budget spacing for ASHA but would still give an insight into what provides the occasional gains for PASHA. Especially when linked with the evolution of $\\epsilon$. Is then the main question (quite rightly) the allocation of budgets and the overall budget for exploration at lower rungs?\n5. Two points that come up from the previous statement\n    * Can we perform Hyperband in $[r, R*]$ and sample at the explored rungs directly? Can that do better than PASHA? How might that affect $\\epsilon$ calculation over 3 rungs?\n    * Given that PASHA offers speed-ups, can it switch or slowly move to ASHA to allow for higher rung evaluations? A dynamic heuristic that could respond to unchanging rankings over time, or to a width limit for a rung (inspired by Hyperband) could avoid the pathology mentioned earlier too. While not affecting the overall speed gains over ASHA.\n6. Mobster results on PD1 would be good to see.\n7. Elucidating on the choice of 1-NN surrogate for PD1 should be explained more along with the distance measure used for. Given that log-scaled parameters exists and the deep learning HPO landscape could be irregular, a cross-validated surrogate performance analysis (or equivalent) should be a good addition to the appendix.\n8. Ablation studies on PD1, especially for Table 7 would be nice to have.\n9. Table 7 is fascinating but also raises the question as to why any of the other ranking methods were not selected. There are also methods which are comparable to PASHA and offer more speedups using even lesser max resources. This again begs two more questions:\n    * How much of this is a contribution of the noise band calculation with respect to the learning curves being optimized?\n    * What are the learning curves like? (And what is the evaluation protocol for ASHA, PASHA, and baselines)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "DVRiu8fWta_", "reviewer": "Reviewer_p4YZ", "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": "This paper studies multi-fidelity AutoML algorithms and proposes an improvement over ASHA.\n\nInspired by the observation that there might exist a cross-over point of the learning curves of different configurations where their ranking swaps, the author propose to leverage this instability of ranking to progressively allocate more resources. Further, a soft-ranking technique is proposed for smoothing out potential noise, with a threshold parameter that can be automatically decided rather than tuned.\n\nEmpirical evaluations are conducted on NAS-Bench-201 and PD1 HPO Bench. Compared with ASHA, the proposed method achieves a 2-10 times reduction in run-time while sometimes falling short of the final performance.", "summary_of_the_review": "I find the presented method intuitive and relevant. My main concern is with experimental results, i.e. while PASHA successfully reduces the run-time, it often also performs worse than ASHA as well. It would be great if the author could also assess the run-time reduction by matching the final performance with ASHA on these datasets and benchmarks.", "strength_and_weaknesses": "Strength:\n\n- This paper presents a relevant technique for speeding up multi-fidelity AutoML algorithms.\n- The presentation of this paper is clear and straight to the point.\n- The proposed algorithm is well motivated, intuitive, simple yet empirically effective.\n- Extensive ablations are conducted on the proposed algorithm.\n\nWeakness:\n\n- Clarity:\n    - While the beginning of section 4 is crystal clear, I find the narrative of Section 4.1 looks a bit detached. It seems to be the first time that “soft-ranking” has been mentioned in the paper. So I would expect some motivations for it at the beginning rather than going straight into explaining its computation.\n- Empirical results:\n    - While the run-time reduction is significant, in several cases PASHA produces worse final accuracy than ASHA. For instance, Table 1 CIFAR-10 and TinyImageNet, and all of Table 3 and 5. I wonder what would be the run-time reduction if the authors aligned the performance with ASHA?\n- Evaluation metrics:\n    - For the experimental section, the author mainly uses the final performance of the selected configurations as the evaluation metric (additionally regret in the appendix). For ranking-based search algorithms, it might also be worthwhile to evaluate the global and top-K ranking correlations. I am aware that the soft-ranking technique would make it a bit tricky to compute these metrics. But maybe you can simply switch to hard ranking when computing this metric. I feel the proposed method could produce a better or comparable correlation than ASHA or SHA.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster