Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: This work studied an interesting topic of training-free Neural Architecture Search (NAS). It utilizes two training-free indicators to measure the performance of a network without training it. The experiments show the proposed approach has improvement in searching time. 

However,  as the main contribution, the two measurements of the training-free indicators (trainability and expressivity) already be proposed by previous works. The rest contributions of this work are the proposed NAS networks, Instead of using the original loss function to guide the search process, this work simply combined those two measurements as a new ranking identifier of candidate architectures. The contributions not strong enough.

Advantages:
1. The writing quality of the paper is good enough
2. The paper has good descriptions of the related work.

Key weakness:
1. The major contributions of this work, the two network measurement methods, were proposed by previous works.
The first indicator:
    Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems 31. 2018a.
    Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha SohlDickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in neural information processing systems, pp. 8572–8583, 2019.
    Yeonjong Shin and George Em Karniadakis. Trainability of relu networks and data-dependent initialization. Journal of Machine Learning for Modeling and Computing, 1(1), 2020.
    Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. 2019.

The seconde indicator:
    Huan Xiong, Lei Huang, Mengyang Yu, Li Liu, Fan Zhu, and Ling Shao. On the number of linear regions of convolutional neural networks. arXiv preprint arXiv:2006.00978, 2020.

2. The differences between the proposed pruning-based NAS and previous work are not clear. What is the key novelty of the proposed pruning strategy? 
3. According to Table 3, it seems that the TE-NAS couldn’t find the optimal neural architecture like P-DARTS and PC-DARTS, which confirms the limitation of this training-free search framework.


review_title: Review Comment

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper introduces a searching framework of neural architectures ranking the candidates with two different metrics: the spectrum of NTK and the number of linear regions in the input space. These two metrics do not require the training of neural networks lightening the computational burdensome. Authors support their method by providing results from CIFAR-10, ImageNet, and NAS-Bench-201 benchmark (Dong & Yang).

Overall, this paper proposes new metrics that can be used in the NAS search. Despite the paper well written, the performance of their methodology is incremental improvements (or par) among various existing NAS algorithms. I would recommend a marginally above acceptance threshold for now.

Strength
1. The author provides two new different metrics: a condition number of NTK and cardinality of linear regions to select good architectures besides the validation loss. 
2. Experiments not only on CIFAR10, ImageNet, but also NAS-Bench 201
3. Free from the training allows their method to free from computational burdensome allowing to stack an equivalent number of cells for both the search and evaluation phase. 

Weakness
1. The experiment results are par (or worse) to the existing NAS algorithms. By listing the recently published NAS literatures on CIFAR-10: P-DARTs: 2.50%, DATA: 2.59%, SGAS: 2.66%, PC-DARTs: 2.57%, RandomNAS-NSAS: 2.64%. Especially, SGAS and PC-DARTs require 0.25 and 0.1 GPU days respectively. (However, NAS-BENCH-201 results are competitive.)
2. While no training has a benefit in the computational budget, the performance could be worse than the method with training (less information) as listed in Weakness 1. 

Questions
1. According to Definition 1, the number of linear regions depends on the fixed set of parameters $\theta$. How much the number of linear regions affected by the $\theta$? What happens you use the trained $\theta$ or draw the network parameters with other initializing methods such as Ha initialization or Xavier initialization?
2. Figure 5 shows the pruning trajectory based on the author's method. Intuitively randomly pruning the operation will also reduce the $\kappa$ and the linear regions. Can you support the pruning efficiency based on the proposed metrics by comparing it with the random pruning?
3. Have you tried weight sum loss such as $\alpha \Delta \kappa + (1-\alpha) \Delta R$ where $\alpha \in (0, 1)$ be a hyperparameter? Table 4 seems $R$ plays more significant role than $\kappa$. 

Reference:
1. Xu, Y et al. (2019, September). PC-DARTS: Partial Channel Connections for Memory-Efficient Architecture Search. ICLR2020
2. Chen, X et al. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. ICCV2019
3. Chang, J et al. DATA: Differentiable ArchiTecture Approximation. Neurips2019
4. Li, G et al. SGAS: Sequential Greedy Architecture Search. CVPR2020
5. Zhang, M et al. Overcoming Multi-Model Forgetting in One-Shot NAS with Diversity Maximization. CVPR2020
6. Dong & Yang. NAS-Bench-201: Extending the Scope of Reproducible Neural Architecture Search. ICLR 2020



 



review_title: Well written paper but incremental improvements.

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Summary: Training-free NAS is a promising direction. This work demonstrates that two theoretically inspired indicators: the spectrum of NTK and number of linear regions, strongly correlate with the network’s performance, and can be leveraged to reduce the search cost and decouple the analysis of the network’s trainability and expressivity. The authors thus proposed TE-NAS to rank architectures by analyzing the two indicators. Without involving any training, TE-NAS can achieve competitive NAS performance within minimum search time. 

Pros:

+ This work bridges between the advances in deep learning theory and the practice of NAS. I think it can become an important starting point towards theoretically inspired NAS and can motivate the discovery of more practically viable deep network performance indicators.

+ The authors made efforts to add interpretability to their method and to understand the search process, e.g. Figure 4 and section 3.2.1. It is very interesting to see that the supernet first is pruned by quickly increasing the network’s trainability, and then fine-tuning the expressivity in a small range. 

+ On NAS-Bench-201 and DARTS search spaces, the propose method’s results are extremely promising. For the latter space, the proposed method can search within 30 minutes (on CIFAR-10) and 4 hours (on ImageNet), while the search models’ accuracy remain among the most competitive few. 

Cons:

- I remain skeptical how much the initial stage expressiveness/trainability would last and be preserved until end of training. Also, the two do not represent the full spectrum of desirable model characteristics. The ultimate goal of NAS is to seek a model of best generalization ability, which cannot be merely or easily from its expressiveness (fitting ability, i.e., achievable training error) and trainability (optimization difficulty). 

- Although the authors claimed that the two chosen indicators are strongly correlated with the network’s test accuracies, I’m not sure how true that actually is. In fact, probing the generalization from a trained model is already challenging, not to say from an untrained one. The authors might need to discuss more or to tone down further.

- Figures 1 & 2 leave me with impression that both indicators can filter out some bad outlier architectures; but for many relatively good accuracy architectures, the correlations between the two and the true accuracy are not necessarily high (overall Kendall-tau magnitudes are between 0.4 and 0.5).

- The authors also didn’t specify the computational complexity of computing the two indicators (average per architecture), except just saying they’re very fast. 


- More NAS works are related to the manuscript, for example [1][2][3].
[1]SGAS: Sequential Greedy Architecture Search
[2] GP-NAS: Gaussian Process Based Neural Architecture Search
[3] HourNAS: Extremely Fast Neural Architecture Search Through an Hourglass Lens

- (minor) The writing quality is in general good; some occasional typos:
training-free AS framework: “AS” -> “NAS”;
no only -> not only

review_title: Paper 2426 Review

final_score: rating: 6: Marginally above acceptance threshold
review_content: # Summary
This paper aims to speed up NAS with a training-free performance estimation strategy, i.e., estimate the performance of an architecture at initialization without training (not necessarily the absolute performance, but the relative ranking of architectures).

The proposed strategy estimates an architecture’s performance from two perspectives: (1) trainability, and (2) expressivity. The metrics to measure trainability and expressivity are inspired by recent progress on deep learning theory. Specifically, The trainability of an architecture is evaluated by the spectrum of its NTKs, and the expressivity is evaluated by the number of linear regions in its input space.

The authors also propose a pruning-based search algorithm that relies on the proposed performance estimation strategy. Experiments on two search spaces NAS-Bench-210 and DARTS show that the proposed method can find architectures with reasonable performance while being much faster.

# Strong points
1. Training-free NAS is conceptually novel and an interesting direction. This could make NAS more accessible and useful in practice if training-free methods can work.
2. The authors draw inspiration from recent deep learning theory to design the training-free performance estimation metric.
3. The proposed NAS method can complete the search much faster than previous NAS methods.

# Weak points
1. The metrics for trainability and expressivity seem to be the direct application/extension of recent deep learning theories (NTK, linear region). This makes the novelty of this work a bit weak.
2. It’s unclear how the number of linear regions is computed. The authors gave a definition in Equation 4 but didn’t mention how exactly the number of linear regions is computed.
3. The Kendall tau correlation between NTK/linear region and the test accuracy is actually weak based on the reported value (-0.42 / 0.5). Why would this weak correlation lead to an architecture with good performance? Also, the final method uses a combined relative ranking. What’s the Kendall tau for this combined relative ranking metric?
4. The most interesting part in this work is the proposed training-free metric. It is important to compare this training-free metric with the typical metric (e.g., validation accuracy after training a limited number of epochs), while keeping other factors unchanged. What will the performance/search efficiency be if we combine the proposed metric with existing search algorithms (e.g., random search, reinforcement learning)? It will be helpful to compare the proposed metric and the typical metric using the same search algorithm and the same number of samples.
5. It’s unclear how important the pruning mechanism is for the final performance/search efficiency. Having the above analysis/results will also help answer this question.
6. The absolute performance on ImageNet in DARTS search space is not very strong. Also, for experiments on NAS-Bench-201, the authors only compare to some relatively weak baselines. As shown in Table 5 in the original NAS-Bench-201 paper, random search/REINFORCE perform on par or better than the proposed method, especially on ImageNet-16-120.

# Justification of rating
The proposed metric is interesting. My main concern is the lack of analysis as mentioned above. Without those analyses, it’s hard to convince people that this metric is empirically useful. Also, the novelty is a bit limited as the metric seems to be a direct application/extension of recent deep learning theories.



# Additional feedback

“Training a supernet till convergence is extremely slow” - This sentence is not very accurate. Training a supernet is usually similar to training one architecture on the dataset. Although it’s more expensive than training-free, it’s practically acceptable. The drawback of supernet is more about its inaccurate performance estimation.

“What to select” sounds more like the search space definition in NAS. The objective of NAS is always clear (best accuracy under certain FLOPS/params). I suggest the authors rephrase the text.

Figure 5. The two figures have some overlappings.

# After rebuttal
I would like to thank the authors for their extensive efforts during the rebuttal. My main concerns are resolved, so I change the rating to borderline accept. I encourage the authors to update the paper with the results provided in the rebuttal, especially the explanation of the novelty and the results for "Proposed metric with existing search algorithms".

review_title: Interesting idea, but more analysis is needed to justify the idea

Meta-review: The authors propose training-free neural architecture search using two theoretically inspired heuristics: the condition number of the Neural Tangent Kernel (to measure "trainability" of the architecture), and the number of linear regions in the input space (to measure "expressivity"). These two heuristics are negatively and positively correlated with test accuracy, respectively, allowing for fast, training-free Neural Architecture Search. It is certainly not the first training-free NAS proposal, but achieves competitive results with much more expensive NAS methods.

A few reviewers mentioned limited novelty of the method, a claim with which I agree. The contribution of the paper, however, is something different than how it was presented. The core message seems to be that the two proposed heuristics can greatly speed up NAS, and should be a baseline method against which more expensive methods should test.

I feel like this is a borderline paper, but may be of interest to researchers in the field.
Decision: Accept (Poster)