Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper came up with the lower bound of generalization error for several gradient based training-free nas methods. They were able to relate training-free metrics such as $M_{Grad}$, $M_{SNIP}$,  $M_{Grasp}$ with the trace of the the NTK-Matrix. The generalization bound for the scenarios where training error is not zero is proportional k/M where $k$ is the ratio of the largest and the smallest eigen values of the NTK matrik and $M$ is the training-free metric. So they came up with a formulation for generalization error based on $k$ and $M$ involving hyperparameters $\mu$ and $v$

Further they devised a BO-based NAS algorithm, that searches the hyper parameters for the above formulation. The architecture minimizing the generalization error formulation is found and is trained to obtain its validation performance. The BO's surrogate model is then updated with the validation performance. This is continued and the architecture with the best validation accuracy is returned
strengths_and_weaknesses: Strengths
This is the first paper that is able to relate several gradient based training-free metrics and formulate a generalization bound.
The experiments also show that $M_{Grad}$, $M_{SNIP}$ and  $M_{Grasp}$ are highly correlated with $M_{Trace}$
Their search algorithm is sample-efficient and is only searching for 2 hyper parameters rather than the entire architecture. 
questions: Instead of training-free and training based hybrid NAS, can we come up with a completely training-free algorithm based on what we know so far? for example what if we just use k/$M_{Trace}$ as the metric?
limitations: None
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper theoretically derives the connections among existing gradient-based metrics for training-free neural architecture search, and then develops a generalization bound based on these metrics, which explains why these metrics are correlated with model performance in a rigorous way. Two cases (zero and non-zero training error) are further analyzed. Based on the theoretical results, a unified objective and its corresponding BO-based search algorithm (HNAS) are proposed. Experiments on popular NAS benchmarks are conducted to show the validity of the theoretical results and the proposed algorithm. 
strengths_and_weaknesses: This paper is well organized and has a clear presentation. 
The theoretical perspective is very interesting. The generalization bound offers a unified view to inspect and interpret current training-free NAS metrics. I mainly have the following concerns:

1.	The term O(k/M) plays the role of generalization gap. In M_{trace}, the trace norm of neural tangent kernel is highly correlated with gradient norm. The eigenvalues of neural tangent kernel matrix also affect gradient norm. So, are k and M correlated? How to ensure that decreasing k while increasing M would not cause optimization conflict?

2.	The details of the proposed algorithm, HNAS, are not clear enough. How to calculate neural tangent kernel matrix and its eigenvalues efficiently has been a problem due to the large parameter dimension and the large number of samples in a dataset. So, the detailed process of solving Eq. (7) should be described. Besides, the BO step to optimize \mu and \nu is also unclear. Is the validation performance differentiable to BO? Detailed description should be offered. 

3.	The authors should compare their proposed NAS algorithm with simply using the metrics. For example, replace Eq. (7) with \max M_{grad}, M_{snip}, M_{grasp}, or M_{Trace}, to show the effectiveness of the upper bound in Corollary 2, and the importance of BO. Besides, more recent NAS methods, such as [1], should be compared with. 

[1] Zhang et al., GradSign: Model Performance Inference with Theoretical Insights, ICLR 2022.


questions: See the weakness concerns listed in the last section. 
limitations: I do not see an explicit discussion about the limitations of the method in this paper. 

There is no concern about negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper aims to understand the training-free NAS metrics from a theoretical perspective and build a unified theoretical framework to analyze the relationships of gradient-based training-free NAS metrics. Based on the theoretical results, the authors further propose a hybrid NAS (HNAS) method which can enjoy the advantages of both training-free (i.e., superior search efficiency) and training-based (i.e., remarkable search effectiveness) NAS. Experimental results demonstrate the effectiveness of the proposed method.
strengths_and_weaknesses: ++The proposed HNAS is well-motivated, technical sound, and theoretically guaranteed. The paper is well-written and easy to follow.

--The experimental results are a bit weak since the authors only conduct experiments on NAS-Bench-201. For better evaluation, results on ImageNet would be more convincing.
questions: 1. In Table 3, could the authors also provide the comparison of query numbers (query of training-free metrics and training-based metrics) of different methods, rather than only the total search costs of GPU time?. In addition, more SOTA methods on NAS-Bench-201 such as DrNAS (DrNAS: Dirichlet Neural Architecture Search, ICLR 2021) are recommended to be included in Table 3. These help to evaluate the proposed HNAS more thoroughly.

2. Could the authors provide the Spearman/K’Tau results between the unified objective in Equation (7)/(6) and Ground truth accuracies? which helps to further show the superiority of HNAS. If this is suitable for evaluating HNAS?
limitations: No limitations.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The submission aims to put a stronger theoretical foundation under a set of surrogate metrics that are used in training-free network architecture search and then derive a new method with theoretical and empirical improvement over prior art. "Surrogate"  in this context means "not using data, but only initialized weight parameters", where an increase in the metric is demonstrated empirically to correlate with better model performance. The authors observe that prior art lacks a common explanation of why these metrics work well in practice and they endeavor to provide a common, explanatory model and subsequently a theoretical and empirical improvement motivated from the proposed explanatory model.

The new model essentially comes in two steps: (a) deriving an upper bound for the model generalization error as sum of the training error and a function that is related to the inverse ratio of any such surrogate metric (the latter term being a form of generalization gap and the inverse ratio conforming with the empirical observation that larger surrogate metrics correlate with better model performance), and (b) replacing the training error (first term in the upper bound) by an upper bound as function of only the surrogate metric and the number of samples (but not the samples themselves). These two steps lead to an upper bound of the generalization error that is not a function of the samples themselves, but only the surrogate metric (which is assumed to be a function not of the samples itself) and a set of nuisance parameters (some relating to the initialized model weights). Finally, the paper suggest to aggregate the free nuisance parameters (ones that are not a function of the model/weight) into two generic hyperparameters, reducing the upper bound on the generalization error to a function of only two variables and the model structure and weights. The paper goes on to propose optimizing these hyperparameters via Bayesian optimization using Gaussian processes in an iterative two-step process, where the first step is training-free and optimizes the chosen training free metric over the set of possible networks, and the second step updates the Bayesian optimization with the true validation loss of the chosen network.

The submission exposes several further theoretical connections: (a) demonstrating that one specific metric is an upper bound to the others, (b) relating the condition number of the initial neural tangent kernel to depth and width of networks (under simplifying assumptions), resulting in interpretations that are consistent with earlier empirical results.


strengths_and_weaknesses: The paper addresses an interesting problem (improved bounds and methods for metrics in training-free architecture search). The authors highlight their contributions and put them in the context of prior work reasonably well. I appreciate the novel combination of training free metrics and training-derived performance, both from a theoretical as well as practical perspective.

It appears that the main contribution of the paper lies in deriving Corollary 2 and subsequently the practical procedure in Sec 5.1. This result appears to generalize several prior art (unified view on training-free metric) as well as bound the generalization performance more tightly than previous models (by making the more realistic assumption of a non-zero achievable training error). To my knowledge this is a substantial, original result and including the subsequent optimization scheme appears to demonstrate favorable results. The empirical results (mainly Table 3) when taken out of context of the theoretical foundation could be seen as not sufficiently convincing: the achieved accuracy is generally slightly better than the compared methods, but the runtime is significantly worse when compared to some. Admittedly, the acceptable tradeoff between run-time and accuracy may be domain-specific ("train fast or well"), thus both priorities have their value. The slight accuracy improvement, most prominent on the IN-16 dataset, is consistent with the presented theoretical perspective and thus good substantiation of the former. From an empirical perspective, it may perhaps be insightful to test the method in a NAS regimen where the current state of the art is still far worse than the true best accuracy to highlight a different, valuable trade off between accuracy and training time.

I had some issues with the clarity and coherence of the paper:
- There are two parts that on first reading appear disjoint with the rest of the paper. First, the relation between the metrics in theorem 1 does not appear to have a bearing on the subsequent deductions. Only after following the proof in appendix A3 the importance becomes clearer. This is a minor point and could be improved by explicitly stating the relation of Theorem 1 to Corollary 2 in the main paper. Secondly, and also very minor by itself, Section 4.4 does not seem to serve a purpose in the main paper except for highlighting speculative connections based on assuming models of simple topologies (deep vs. wide). I feel that the paper would benefit from either omitting or expanding this section.
- More importantly, there appear to be details missing that I would find significant: (a) how is the Bayesian optimization implemented, and (b) how is (7) solved for in Algorithm 1.

Originality: The paper is an extension of previous work that adds original thought and explorations.
Quality: The paper is written well, it puts the presented work in context well and combines theoretic with empirical results.
Significance: The main significance as it is exposed appears to me in Corollary 2 and the subsequent derivations of a practical optimization scheme for training-free/hybrid NAS. The significance of this result would be more empirically evident if the empirical results would show achievable trade-offs between accuracy and training time more differentiated from the state of the art as it does now.
questions: Summarizing the above points that would help clarify the exposure better:

1. How is (7) solved in Algorithm 1?
2. How many iterations K in Algorithm 1 do the presented experiment require? I understand that this is the number of times that an actual training on data is performed in the hybrid setting.
3. Could you please share more details on the BO in section 5.2? The presented material leaves questions open: What are the open parameters in this optimization, how do the choices influence the optimizations? I feel that this part is important to gauge the overall quality and significance of the paper and it is a bit glanced over.

As it is I am rating the paper as borderline accept, primarily as I feel that some of the aspects in the questions (1), and (3) are missing to value the full contribution of the submission.

[Update post-rebuttal] I feel that my questions from the review have been addressed well and I am increasing my soundness score (to "good") as well as the rating (to "weak accept") respectively.
limitations: The submission highlights limitations sufficiently.
review_title: null

Meta-review: metareview: The paper is the first to theoretically analyze gradient-based training-free NAS, and come up with a generalization bound. The authors further present a hybrid unified framework to benefit from both training-free and training-based algorithms. The paper is clearly written and technically sound. The reviewers raised several questions about the details of the algorithm and experiments, and the authors addressed them in the response precisely. It is suggested that the authors include those discussions in the revision.  
confidence: Certain
Decision: Accept