Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 

The 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. 

strength_and_weaknesses: Strengths:

* Relevant and well-placed motivation and problem statement.
* Takes an existing, popular algorithm to potentially improve it and lower computational costs in achieving similar results.
* Simplicity of the approach and seemingly easy-to-implement changes to ASHA.
* Relaxes the need for one of the 2 important ASHA hyperparameters (assuming  $\eta=3$ is standard).
* Incorporates the possibility of LCs crisscrossing, unlike vanilla ASHA.
* Implementation integrated into an existing library SyneTune.

Weaknesses:

A) Incoherency stems when reading more of the paper.
  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. 
  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.
  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.

B) Strong assumptions that go into the design of the algorithm and the experiments.
  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. 
  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. 
  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).
  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. 
  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. 
  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.

C) Uclear or points which raise questions.
  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.
  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?
  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?
  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. 
  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. 
  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.
  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.

D) One clear pathology that is not explored.
  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.

Other comments:

0. The Tables are difficult to parse, especially the ablations. Some guides to the reader could be provided with bolds, underlines, colours, etc.
1. 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.
2. 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$.
3. 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. 
4. 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?
5. Two points that come up from the previous statement
    * 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?
    * 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.
6. Mobster results on PD1 would be good to see.
7. 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.
8. Ablation studies on PD1, especially for Table 7 would be nice to have.
9. 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:
    * How much of this is a contribution of the noise band calculation with respect to the learning curves being optimized?
    * What are the learning curves like? (And what is the evaluation protocol for ASHA, PASHA, and baselines)
clarity,_quality,_novelty_and_reproducibility: The writing is overall clear. Sections 4.2 and 6 stood out as sore thumbs to me given the rest was a smooth read. Some details on the experiments could be elaborated more. 

The motivation of the work is well founded and an important problem in making HPO more accessible to the community and lowering down costs required for practical HPO. The paper identifies a possible direction for it and presents it well. A popular algorithm is taken as the baseline and is appended with a feature to address a potential flaw in it. The motivation, setup, and presentation of the work is a classic example of empirical research and does well at that. However, the content and presentation of the empirical data could be improved and more convincing.
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.


The 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.
strength_and_weaknesses: **Strengths of paper:**
1. 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.

2. The authors empirically show that their proposed algorithm speeds up on HPO and NAS datasets while only having minimal performance degradation.


**Weaknesses of paper:**
1. Main weakness of the paper is its novelty, as it is an extension of existing work (algorithm ASHA). 

2. 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.  

3. 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.

4. 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.

**Question and other comments.** 

Please address the above weakness. I have a few more questions/comments:
1. Can PASHA exploit the estimated function values (like BO) to choose the next configurations?  
2. In conclusion: Mention the dataset name instead 'the largest dataset with millions of training examples.'

I am open to changing my score based on the authors' responses.
clarity,_quality,_novelty_and_reproducibility: **Clarity:**
The paper is well-organized and clearly written.

**Quality:** 
The paper appears to be technically sound. The experimental evaluation is adequate, and the results convincingly support the main claims.

**Novelty:** 
The paper contributes some new ideas or represents incremental advances.

**Reproducibility:** 
The code is available, and the experimental setup is comprehensively described. Any competent researchers can easily reproduce the main results.
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies multi-fidelity AutoML algorithms and proposes an improvement over ASHA.

Inspired 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.

Empirical 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.
strength_and_weaknesses: Strength:

- This paper presents a relevant technique for speeding up multi-fidelity AutoML algorithms.
- The presentation of this paper is clear and straight to the point.
- The proposed algorithm is well motivated, intuitive, simple yet empirically effective.
- Extensive ablations are conducted on the proposed algorithm.

Weakness:

- Clarity:
    - 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.
- Empirical results:
    - 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?
- Evaluation metrics:
    - 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.
clarity,_quality,_novelty_and_reproducibility: Clarity:
- The paper is overall clear and easy to understand, with the exception mentioned in the weakness section.

Quality:
- The paper is well written, and the visual illustrations (e.g. Figure 2) really help with understanding.

Novelty:
- The proposed algorithm is an improvement over ASHA, yet the modifications seem novel.

Reproducibility:
- Detailed code is provided in the supp file.


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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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

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.

Overall 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.  

However, 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)

clarity,_quality,_novelty_and_reproducibility: ###Novelty: 

The paper addresses an important and timely problem that was stopping HPO methods from being easily applicable. Nevertheless, it is in fact not the very first paper addressing the problem; but I have to admit that I like the overall idea because of its simplicity and robustness.

### Quality and Clarity: 

Overall, the quality of the paper is high and the paper is well written. Nevertheless, I have some doubts and open questions listed below.
In Algorithm1, $R_0$ = $\eta^2r$. Which allows for 3 rungs (r, $\eta r$ and $\eta^2 r$), is that intended? (Only 2 rungs suffice for early-stopping PASHA)

Algorithm 1,  the stopping criterion is missing. 

The last paragraph of Section 5.1, “We compare PASHA with ASHA, a state-of-the-art approach for hyperparameter optimization”, should this be “multi-fidelity optimization”?

Given the stopping criterion of PASHA, there is a very important baseline that is missing: training all configurations for 2 epochs. Since PASHA stops early only if the ranking of configurations stabilized in the top 2 rungs, i.e., 2 rungs are the minimal resources that are required by PASHA. Then if we have N configurations, this would take $N \times r $ + $N / \eta \times r \eta$ = $2 \times N r$. Therefore, training all configurations for 2 epochs should be considered as another baseline. (If $R_0$ = $\eta^2r$, then this value should be 3, see the previous comment) For the revision, I would like to ask the authors to add this.

It would be interesting to see if the ranking actually stabilizes if the authors continue to run PASHA until the maximal budget. 
Do the authors consider dataset size as another budget type? In their related work, the authors mentioned subset selection and showed that “Further, Zhou et al. 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”

### Reproducibility: 

There are several details in the experimental setup that are unclear to me and need clarification. Additionally, code is not provided in the paper.

On Page 5, the authors claim that “Note that resources r_j, r_k, r_l do not need to differ by 1 epoch- there can be e.g. several epochs in between”. However, it is unclear how these values are set in their experiments and unclear the impact of these values.
How do you determine the 90-th percentile of distances to compute the tolerance value $\epsilon$? How does this value influence the performance of PASHA?

Does the random baseline randomly select one configuration from 2560 configurations, if I understand correctly?

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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
strength_and_weaknesses: Strengths:
1. The approach is elegant and the primary assumption that learning curves rarely "cross" is supported by previous work.
2. The experiments section is comprehensive and the results are impressive.

Weaknesses:
1. 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. 

2. 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?
clarity,_quality,_novelty_and_reproducibility: Quality:
The paper is written well. The algorithm is extensively tested and compared to suitable baselines and as such their claims are empirically well-supported.

Clarity:
The paper is generally written clearly, and the figures are useful for understanding the main points. The clarity could be further improved as per my comments in the previous section.

Originality:
The work is novel. While PASHA is an extension of previous work, the core idea of early stopping based on whether rankings have changed between rungs is original to the best of my knowledge.
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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper introduces PASHA, a simple heuristic resource allocation method that avoids allocating higher resources to compare sets of configurations whose ranking has stabilized with lower amounts of resources. After a lot of interaction between reviewers and authors, during which the authors added substantial new evidence, all reviewers increased their scores to lie above the acceptance threshold. A key concern in the decision process was the current setup of the experiments section, which are designed to show the strong performance of PASHA in a horse race on a few benchmarks, hand-picked as those where PASHA works well: 2 datasets from PD1 (with the authors specifically acknowledging that PASHA wouldn't work well on other PD1 datasets) and the 3 datasets from NAS bench 201. There are a lot of other benchmarks available (e.g. other NAS benchmarks, LC-Bench, FCNet, HPO-Bench, TaskSet, YAHPO gym, learning curves by Mohr & van Rijn, etc), and a better goal for the experiments would have been a comprehensive evaluation that scientifically studies cases where PASHA works well and cases where it does not work well. This is computationally cheap since all of these benchmarks are surrogate benchmarks. Asked about this, the authors added experiments on LC-Bench on short notice that do indeed show much more modest speedups (only around 20%). 
Overall, I recommend acceptance due to the method's simplicity, intuitiveness, and good results in some cases, which can make this a very useful building block of future HPO algorithms. It is not at all clear, though, whether this approach by itself constitutes a robust HPO method. I strongly encourage the authors to add more comprehensive experiments (including any negative results), to scientifically study the benefits and disadvantages of the method.
justification_for_why_not_higher_score: The authors only showed results on hand-selected benchmarks where their method performs well and did not show the (known) cases where it does not lead to large speedups / yields worse results.
justification_for_why_not_lower_score: The method is intuitive and simple and yields good results when learning curves don't cross much (which is the case in many but not all benchmarks).
Decision: Accept: poster