Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Performance estimation is an important point to speed up the search process in NAS.
This paper proposes a simple method for estimating the generalisation performance of neural architectures via training speed measured by the training loss, which is theoretically motivated by the relation between training speed and generalisation of neural networks.
Experiments demonstrate the effectiveness of the proposed TSE (training speed estimators) compared to other commonly used estimators. Further, it can be incorporated into existing NAS algorithms and make improvements.
main_review: The proposed TSE is a simple yet effective estimator for performance prediction.
The metric is easy to compute during the training and correlates with the generalisation of neural architectures.
Below are some problems/questions:
1. In line 201, E=1 performs well and implies that more recent training steps is better for TSE. Then what if you limit the minibatches used to calculate the TSE, rather than the B batches in an epoch?
2. In line 268, you choose different N_s values to identify the best T_o. Does this mean that for other practitioners applying your TSE on their task, they can use N_s = 10 to identify the overfit point T_o?
3. In Figure 4, why T=200 is worse than T=10 across all the experiments? This is not reasonable.
4. In line 299, what is the additional cost of training B additional mini-batches?
5. In Figure 1, why does SoVL not appear in d-h, LcSVR not in h, SNIP not in d-h, and JacCov not in d-h ?

Typos and grammar mistakes:
1. Line 28, trainin -> training
2. In Table 1, N_{total} appears in the caption but not in the table, and N_{T} appears in the table rather in the caption.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes a simple yet reliable estimator for fully trained network performance inspired by the PAC-Bayes bounds. Based on the observation in previous work that networks that train faster have better generalization performance, they propose that small areas under the training loss curve early in training correlate with better final performance. They propose several variations of this estimator with varying methods of weighting more recent epochs more than early epochs. They demonstrate the effectiveness of their estimators to provide good ranking correlation performance with the final accuracy with limited training on several search spaces/datasets such as NB-201-cifar10/cifar100/imagenet16 and Resnet/Resnext-cifar10. They also demonstrate that their estimator provides better rankings and find better performing networks compared to using the validation accuracy when applied to the problem of selecting a final architecture from a trained super-network for one-shot NAS. They also demonstrate that it can more efficiently find high performing networks compared to validation accuracy when applied to Regularized Evolution NAS and Bayesian Optimization NAS.
main_review: This paper tackles the problem of finding estimators that can better predict final network performances with few epochs of training. Their proposed estimator based on the area under the training curve is simple and very efficient to calculate and they demonstrate that it is robust with thorough experiments with multiple use cases, multiple search spaces, and multiple datasets. I strongly recommend this paper to be accepted. While the method is not incredibly novel and there is previous work on early stopping, their paper has significance due to the simplicity of the method and the range of experimental evidence they provide to demonstrate their algorithm

Strengths:
A large strength of this paper is in its simplicity. It target's an important area of model-free accuracy prediction from a single training run. Performance predictors are a very important field of work for NAS and this method has strong performance utilizing only the training loss compared to weight-sharing proxies and model-based performance estimators which requires you start with a relatively large number of trained models.

The submission is well supported by their diverse experimental results. They demonstrate their simple metric works well to rank architectures on CIFAR10, CIFAR100, Imagenet16, Flower102. They show that it can speed up Regularized Evolution, Bayesian Optimization, and one-shot NAS. They also show that it can rank architectures well in the NB201 search space, RandWiredNN search space, and ResNet/ResNeXT search space. The paper is easy to understand and follow. It tackles an important problem that can increase efficiency for a variety of NAS methods.

One of the most interesting general indications from the experimental results thoroughly show that early validation loss is a significantly worse measure of later performance compared to early training loss. Their measure seems to only be beat by validation accuracy quite late in training 
 
Weaknesses:

This paper would benefit from better positioning of the work in relation to related work on performance prediction. While work is well positioned with respect to LcSVR and early validation accuracy in experiments and related work, it would still benefit from additional comparisons to recent work such as tree-based and graph functions like LGBoost[1], XGBoost[2], GIN[3] which were examined as performance predictors in Nasbench-301[4]. LGBoost[1] and XGBoost[2] were also analyzed more thoroughly in [5].

One area it would actually be very beneficial to test would be comparing your TSE metrics with simply using the training loss as a strong baseline for your proposed variations.

An interesting additional area to explore may be how the training loss compares to the training accuracy as a metric.

One area which the paper could be extended to show further robustness of this finding would be testing out a task other than classification such as object detection or regression to see if maybe this is a property limited to simple classification cross entropy loss. If any results could be shown on full sized Imagenet, it would demonstrate that the methodology works also with larger datasets.

It would also be useful to show the robustness of this general method for performance estimation if you could analyze if this can be extended to other hyperparameter search problems as you mentioned.
 
[1] G. Ke, Q. Meng, T. Finley, T. Wang, W. Chen, W. Ma, Q. Ye, and T. Liu. Lightgbm: A highly efficient gradient boosting decision tree. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 3146–3154. Curran Associates, Inc., 2017.
[2] Julien Siems, Lucas Zimmer, Arber Zela, Jovita Lukasik, Margret Keuper, and Frank Hutter. Nas-bench-301 and the case for surrogate benchmarks for neural architecture search. arXiv preprint arXiv:2008.09777, 2020.
[3] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019a.
[4] Siems, Julien, et al. "NAS-Bench-301 and the case for surrogate benchmarks for neural architecture search." arXiv preprint arXiv:2008.09777 (2020).
[5] White, Colin, et al. "How Powerful are Performance Predictors in Neural Architecture Search?." arXiv preprint arXiv:2104.01177 (2021).

limitations_and_societal_impact: I believe that limitations and societal impacts are sufficiently addressed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work proposes that the summing of training losses may be a better indicator than validation accuracy especially at the early phase of architecture search. Author[s] provides experimental results on various model-free speedy estimators, zero-cost estimators, model-based extrapolators; and shows that TSE-E and TSE-EMA are the most effective two among them. 
main_review: Merits:
1. Good motivation. The paper starts with the generalization bound based on the properties of the training trajectory, hypothesizing that training speed may be a less noisy measure of generalization compared to the validation accuracy in the view of NAS, where the search budget is usually limited. 

2. Solid experiments. The paper conducted experiments on NAS201, RandWire, NDS, DARTS to evaluate the ranking correlation preserving the capability of these performance estimators, as well as on NAS201,  NAS301 (DARTS) to evaluate the NAS performance of both query-based (where they evaluate three subroutines RS, RE, BO) and weight-sharing (where they evaluate four subroutines RandNAS, FairNAS, MultiPahs, Bi-level). In all these experiments, they show that TSE-E and TSE-EMA can better preserve the ranking correlation than SoVL and VAccES; and much better than zero-cost estimators when training progresses (though it is a little bit unfair since zero-cost is designed for epoch 0, depending on how many budgets you have).  They also show its speed-up performance under query-based NAS as well as better search performance under weight-sharing NAS. 

3. Simple and effective. Figure 5 in Appendix C.4 looks surprisingly consistent across different datasets and search spaces in terms of rank correlation performance of TSE-E computed over E most recent epochs. If it holds true, in practice it means we can simply query the training loss API in existing NAS benchmarks at each epoch and directly use it as the feedback signal.  

4. Code is provided. 


Improvement suggestions:
1. In Line 98, you mentioned measuring training speed solely based on the epochs is likely to suffer overfitting on training data thus cause degraded model selection performance. However, in the experiments the minimum T you choose is 1, meaning that at least all mini-batches within a most recent epoch are used to compute the sum of training losses. I admit that currently NAS benchmarks only provide epoch-level statistics, which may restrict the experimental setup. Nevertheless, could you provide some discussion/results on TSE results based on mini-batch beyond discretized epochs? e.g. conduct some ablations on the actual search space instead of benchmarks so you can run TSE within an epoch. 

2. Figure 2 in Appendix C.2 validates the motivation by showing that validation loss may negatively correlate with validation accuracy as training progresses. I don't quite understand why the discrepancy between validation loss and training loss is very large on CIFAR-100 since it is assumed to be i.i.d.

3. I would suggest author[s] take a look at another line of speed-up NAS in the related work. e.g. https://arxiv.org/pdf/2006.06936.pdf, https://arxiv.org/pdf/2102.07108.pdf, https://arxiv.org/pdf/2007.04965.pdf, https://arxiv.org/pdf/2105.06369.pdf. The idea is to design a better neighborhood-aware encoding/representation to build a flatter performance landscape and improve downstream subroutines in the scope of both query-based and weight-sharing based. In practice, architecture parameters could be further combined with partial learning curves to boost the KT and NAS performance, see this for a take https://cvpr21-nas.com/resources/upload/0894f613d1c1/file/1624351763247.pdf. 
limitations_and_societal_impact: This is solid work. Experiments have been conducted in a comprehensive way in my opinion. In addition to the improvement suggestions as pointed above, there is not too much I can think of now. If time is allowed, author[s] may provide experimental results compared to SOTA NAS results on DARTS search space with the same training protocol as used in DARTS original code. In Line 226, LcSVR (or in general, model-based predictor) can be optimized in an active learning way with the updated pool instead of using a large initial population for a one-time fit to save the computational resources, as used in many recent works such as MLPs in BANANAS, GCN with BLR in BONAS, and DNGO in arch2vec and CATE. This work does not contain any potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a simple yet effective model-free performance evaluation metric for architectures with partial training. To briefly summarize, the proposed method uses the (weighted) average of training loss over multiple mini-batches. Intuitively speaking, this metric measures the variance of gradients across mini-batches to some extent, which is related to the ease of convergence. Extensive empirical evaluations are conducted across different spaces and the results show that the proposed metric consistently outperforms existing ones; The theoretical aspect of this paper includes a connection of TSE to PAC bound. This work has its value as an add-on to many existing NAS algorithms. For these reasons, I vote for acceptance. I do have a few questions for the author, which I will explain in the detailed comment. And I might adjust my opinion of the paper depending on the responses.
main_review: Strength:
1. The author demonstrates that the proposed method can be used as a simple add-on to improve many existing NAS methods.
2. Solid experiments, the author studies on a wide range of spaces (e.g. NB201, NB301, DARTS, Randomly wired spaces, ResNeXT space, e.t.c.) and demonstrated consistent results.
3. ranking among the top 1% architectures on some spaces is also reported, which is an important measure of the effectiveness of the proposed method, especially for NAS.
4. sufficient discussion/experiments are provided for the hyperparameter of the proposed metric (i.e. window size and decay ratio). A procedure to decide the training budget is also provided.

Weakness:
1. It seems that the author tests the ranking correlation on larger scale search spaces like DARTS Space, but does not report and compare the final results. Perhaps turning the proposed metric into a full search algorithm (by combining it with random sampling or some other existing method) and evaluating on DARTS Space might make the paper stronger. Like those experiments in Figure 5. But this is not a major point.
2. Please refer to the questions in the Detailed Comment Section.

Detailed Comments:
1. The paper mentioned that the training speed is related to generalization. However, in NAS, people generally believe that architectures that are easier to train (e.g. with more parameter-free operations) might stand out in the beginning but plateau quickly and therefore falls behind eventually [2]. These two conclusions seem a bit contradictory at first sight. I would like to hear the author's comment on this matter.

2. It is interesting to see that using training loss works better than the valid loss in TSE. I wonder if the same result can be observed in early stopping: Could you also show the curves of early stopping + training loss and early stopping + valid loss in Figure 1 (a-c would be sufficient)?

3. For DrNAS in Figure 5a: this curve seems different from their original paper [1] (Figure 1). From your curve, it seems that the performance of DrNAS drops to ~50% on 201 (which is basically an architecture full of skip/none) in the middle run. But in Figure 1 of the original paper, the solid line - the test accuracy of the best architecture derived by argmax of the concentration parameter - seems pretty stable. Do you have any idea about the difference?

Minors:
1. You might want to move Figure 1 up to page 3/4, as it is cued twice there.

[1] Chen et al. DrNAS: Dirichlet Neural Architecture Search (ICLR2021)\
[2] Zhou et al. Theory-Inspired Path-Regularized Differential Network Architecture Search (NIPS2020)
limitations_and_societal_impact: Yes, it is addressed in the appendix.
review_title: null

Meta-review: This is a strong paper in a somewhat crowded research area, performance prediction for NAS. Even within such a crowded area, this paper stands out for the thoughtfulness of its experiments and the grounding of the approach proposed. The reviewers asked for more depth in the related work section and for some additional experiments, but overall have no remaining concerns regarding the paper. 
Decision: Accept (Spotlight)