Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper first theoretically reveal how some specific gradient properties impact the convergence rate of neural networks. Based on their theoretical analysis, they propose a new zero-shot proxy, *ZiCo*, the first train-free proxy that works consistently better than #Params.

strength_and_weaknesses: 
Strength:

The authors theoretically reveal how the mean value and standard deviation of gradients impact the convergence of neural networks. And based on their theoretical analysis, they propose a new train-freet proxy, ZiCo.  Experiment results have shown that ZiCo works better than previous zero-shot NAS proxies on multiple popular NAS-Benchmarks (NASBench101, NATSBench-SSS/TSS) for multiple datasets (CIFAR10/100, ImageNet16-120). 

Weaknesses:

Several concerns in  **Clarity, Quality, Novelty, Reproducibility**. 
clarity,_quality,_novelty_and_reproducibility: 
Question about the theorem 3.1 and theorem 3.3:

1.Theorem 3.1 and Theorem 3.3 tell us that the network with low training loss should have high absolute mean values and low standard deviation values for the gradient. So why not just use the training loss item as a proxy?

2.The validation experiment of the theorem 3.1 and theorem 3.3 focus on the training loss. I think it is more convincing to explore the correlation between them and the real accuracy on the validation set.

3.It seems that the caption of Figure 1 draws the wrong opposite conclusion.

Question about the evaluation on NAS benchmark and Imagenet:

1.I think the recent zero-cost/zero-shot literatures should be considered and compared. E.g., the zero-cost PT showing a best architecture of 2.43 top1 error on CIFAR-10, while only using 0.018 hours search cost.

**2.Why only show the result of Zen-score partly, ignoring its better results of 83.6% under the 1000M FLOPS constraint?**

3.How about the results without distillation of Efficient-B3?

4.Since the proxy ZiCo is defined from the absolute mean values and standard deviation values, it will be interesting to explore their individual contribution.



[a] Zero-Cost Proxies Meet Differentiable Architecture Search, Xiang et al. 

summary_of_the_review: 
The authors theoretically reveal how the mean value and standard deviation of gradients impact the training loss of neural networks. And based on their theoretical analysis, they propose a new train-free proxy, ZiCo, which achieves better correlation scores with the real test accuracy. But there are still several concerns need to be addressed.

# Update after reading response

I think all my previous concerns are well addressed. Thanks the author for their effort. I raise my score as promised.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new zero-cost proxy (called ZiCo) for neural architecture search motivated by theoretical insights about the relationship of statistics of gradient across different input samples (absolute mean and standard deviation) and a network's converge speed.
The proposed proxy is evaluated by investigating ranking correlation on NATSBench-TSS, NATSBench-SSS and NASBench101, as well as by end-to-end NAS performance (guiding an evolutionary algorithm) using MobileNetv2 search space on ImageNet.
Additionally, experiments designed to validate theoretical claims and ablations, including investigation of ZiCo's correlation to accuracy on NATSBench-TSS with varying number of batches and batch size, are also presented.
strength_and_weaknesses: **Strengths:**

- a novel zero-cost proxy for NAS grounded in theory is always a nice thing to see
- overall good writing and organization of the paper
- good performance of the proposed method (although see below)

**Weaknesses:**

I haven't actually found anything that I would confidently consider a major weakness. I would have a series of suggestions how to improve writing in certain places, as well as possibly extending evaluation, but these are minor things.
More importantly, I have two questions to the authors which might turn out to be major weaknesses, but it is hard to conclude that just from reading a paper and therefore I would like to give the authors a chance to explain these things.

1. Theoretical contributions in Section 3 are concluded with a statement that "(...) network with high training convergence speed should
have high absolute mean values and low standard deviation values for the gradient (...)", which is used to motivate design of ZiCo.
I wouldn't say that this statement is incorrect (although, admittedly, the analysis from Section 3 it's not my primary area of expertise), however I have some doubts regarding applicability of this statement to NAS.
Specifically, it is a common pattern observed in practice that networks that converge faster usually converge to worse local minima - one of the most representatives examples could be two networks with significantly different number of parameters, usually a smaller network would converge much faster but to much worse results, whereas it takes longer to optimize networks with significantly more parameters but they tend to achieve better results.
How is the analysis provided helpful in those situations? Does it provide us with means to correctly identify such cases?
Additional bonus question: doesn't the assumption about $g_i~\mathcal{N}(0,\sigma)$ in Theorem 3.2 undermine applicability of Theorem 3.1? If I am not mistaken, under this assumption $\mu_j$ in Eq. 5 is going to be 0, and Remark 3.1 is not really helpful.


2. How much ImageNet results depend on distillation from EfficientNet-B3?
Personally, I consider it cheating when a NAS methods shows that it can discover "better" architectures but compares them using a different training scheme.
It is a well-known fact that even old architectures can benefit greatly from utilizing state-of-the-art training scheme (e.g., see "ResNet strikes back" by R. Wightman et al.), and it seems that the paper currently contains comparisons between ZiCo and other NAS methods where ZiCo might have unfair advantage of an improved training scheme.
For example, the paper makes direct comments about results such as: "Moreover, if the FLOPs is 600M, ZiCo achieves 2.6% higher Top-1 Accuracy than the latest one-shot NAS method (MAGIC-AT) with a 3× reduction in terms of search time" - not only is MAGIC-AT not the best Zero-Cost method for 600M FLOPs in Table 3, the authors of MAGIC-AT specifically write in their paper: "For stand-alone model training, to be consistent with the previous works, we follow the same strategy as ProxylessNAS5 and do not employ tricks like cutout or mixup", while ZiCo not only includes all these tricks, it also employs distillation from much more accuracy EfficientNet-B3!
On the other hand, ZenNAS, which roughly follows the same training procedure, achieves much closer results to the proposed method, up to the point that it might very well lie within randomness of each method.
To adequately address this issue, I would suggest the authors to at least limit their comparison to methods that use the same search space and training scheme, but ideally also include NAS results in a different setting, as presenting end-to-end results only on a single search space is, in general, considered rather limited. How about performance of the proposed method on a significantly different search space like DARTS?
Also, how about comparison with other zero-cost methods?
In general, my current impression is that the choice of baselines and retraining scheme was a bit cherry-picked to present the proposed method in a favourable way.
I am happy to be convinced it is not the case, though.

**Minor suggestions and questions:**

 - within your computational capabilities, please try to run experiments multiple times and report avg. + std. (or whatever other 
confidence metric)
 - is there a point in highlighting "key questions" and "major contributions" in Introduction? Is is there to make sure the reader understands that the contributions are major or that the following bullet points are in fact contributions?
 - "We demonstrate that, compared to all existing proxies (...)" - results in the paper hardly demonstrate comparison with "_all_ existing proxies"... I would expect more linguistic rigour from a math-heavy paper like this; examples of published proxies that are not included in the comparison: NASWOT (Mellor et al., ICLM'21), TE-NAS (Chen et al., ICLR'21), KNAS (Xu et al., ICML'21), NASI (Shu et al., ICLR'22), GradSign (Zhang and Jia, ICLR'22).
 - NATSBench-TSS is not NASBench201, as suggested by the header in Table 1
 - how would you explain the fact that correlation of ZiCo degrades with more batches? Shouldn't more batches result in better estimates of mean and variance, resulting in better performance of the proxy?
 - I am not exactly sure if highlighting that the proposed method works consistently better than #Params on benchmarks where #Params happens to be highly correlated with performance is really important for the paper... To be clear, it is worth mentioning that the proposed method works the best, etc., but specifically highlighting superiority w.r.t. the #Params baseline is a bit too narrow in my opinion - what about cases when #Params is not a good proxy? (the comment is specifically related to contribution 2)
 
clarity,_quality,_novelty_and_reproducibility: Clearly written and contributes novel ideas. Overall good quality, should be easily reproducible with the provided code.
summary_of_the_review: I like the paper and the presented attempt at designing a theoretically-grounded zero-cost proxy for NAS.
Overall, I am leaning towards accepting the paper even with a high score. However, since I am not sure about some important aspects of the paper, I am leaving a lowered score for now and hope that the authors will be able to adequately address my concerns.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: While existing training-free proxies can usually achieve compelling search results, they typically can not work consistently better than #Params in practice (White et al., 2022). So, this paper aims to improve such a state of affairs. Specifically, this paper firstly theoretically proves that the convergence of DNNs is highly correlated to the mean and variance of the gradient at initialization with respect to different input samples. Inspired by such a finding, this paper then proposes to use the inverse coefficient of variation on gradients as the zero-shot proxy for training-free NAS. Empirical results show that the proposed method in this paper can improve over other zero-shot proxies.
strength_and_weaknesses: Strengths:
1. Overall, this paper is well-written and well-motivated.
2. The proposed method in this paper is motivated by the theoretical convergence of linear models and DNNs.
3. Extensive results in this paper have validated the effectiveness and efficiency of the proposed method.

Weaknesses:
1. While this paper is motivated by the inconsistent performance of existing zero-shot proxies, the reason why the proposed method is able to tackle this problem has not been well explained either from the empirical perspective or the theoretical perspective.
2. There is a gap between the derived theoretical convergence and the proposed zero-shot proxy in eq.14. Firstly, Theorem 3.1 and 3.2 are the bounds for step t during the model training with SGD. This means that the convergences of linear models and DNNs are related to not only the initialization but also the model parameters during training and hence can not be simply determined by initialization according to the theorems in this paper. So, without further justification, simply using eq.14 alone may not characterize the convergence of DNNs well theoretically. Secondly, it seems that the mathematical form of eq.14 can not be directly derived from Theorem 3.1 and 3.2, i.e., the form of coefficient of variation doesn't appear anywhere in these theorems. So, the motivation for using the form of eq.14 is kind of weak to me. Thirdly, Theorem 3.1 and 3.2 can only characterize the convergence of models whereas we need to characterize the generalization performance of architectures in NAS. So, is there any other justification that authors can provide to support why characterizing convergence is already enough?
3. This paper misses the comparison with other training-free NAS works [1,2] in their experiments.
4. While this paper is motivated by the inconsistent performance of existing zero-shot proxies, I recommend more search results on other diverse tasks (e.g., the ones mentioned in (White et al., 2022)) to support the improved consistency achieved by ZiCo.

[1] GradSign: Model Performance Inference with Theoretical Insights
[2] NASI: Label- and Data-agnostic Neural Architecture Search at Initialization
clarity,_quality,_novelty_and_reproducibility: In general, this paper is well-written and easy to follow. Meanwhile, the theoretical perspective is new for the NAS area.
summary_of_the_review: Overall, my major concerns lie in the theoretical part and the empirical comparison of this paper. I hope the authors can address my concerns during the rebuttal period.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies train-free metrics for NAS.

The performance of existing train-free metrics is often inconsistent across different search spaces, less consistent than even simply counting parameters.

This paper presents a new train-free metric based on a theoretical analysis on the correlation of gradient statistics to network convergence.

Extensive empirical results are provided on a wide range of popular benchmarks and also importantly on MobileNet space and ImageNet.

While the results do not always outperform existing train-free metrics, it is much more stable across different search spaces, which is far more important.
strength_and_weaknesses: Strength:

- The proposed method is theoretically inspired. The author provides an extensive principled analysis of how gradient statistics contribute to the convergence of the network.
- The author provides extensive evaluations of the proposed metrics across popular benchmarks and also on MobileNet space. Empirical results are strong and consistent.

Weakness:

- [minor] Though extensive analysis, the theoretical findings are not too surprising: i.e. stabler and non-vanishing gradients help with network training.
- While the paper presents detailed theoretical results on how gradient statistics affect convergence, it might not necessarily lead to better generalization. It is often the case that there are networks that converge fast but plateau quickly [1]. I’d like to hear the author’s take on potential ways to connect the current results with generalization errors.

Question:

- For ImageNet results, it is sometimes hard to make sense of the improvement since different methods could be using drastically different search spaces and training protocols. I wonder which specific training protocol the author uses to achieve the reported accuracy. Also, whether the search space is identical to some previous works or modified?

[1] Zhou et al. Theory-Inspired Path-Regularized Differential Network Architecture Search. NeurIPS 2020
clarity,_quality,_novelty_and_reproducibility: Clarity and Quality:
The paper is well-written and easy to follow.

Novelty:
While the theoretical findings are not surprising, the resulting metric and algorithm are intuitively sound and empirically strong and consistent.

Reproducibility:
The source code is provided in the supp material.
summary_of_the_review: The paper is solving an important and relevant problem of train-free NAS metrics: their consistency issue across different search spaces.
The proposed method is simple yet theoretically grounded. I vote for acceptance.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: 
This paper introduces a new zero-cost proxy for neural architecture search (NAS), called ZiCo, motivated by insights on the relationship between gradient statistics, convergence speed and generalization. The proposed proxy is evaluated on NATSBench-TSS, NATSBench-SSS, and NASBench101, and the performance of end-to-end NAS using a MobileNetv2 search space on ImageNet is also evaluated. The authors conduct experiments to validate theoretical claims and conduct ablation studies, such as examining the correlation between ZiCo and accuracy on NATSBench-TSS with varying batch sizes and numbers of batches.

The interaction between the authors and reviewers led to clarifications and improvements to the paper's results and presentation. The additional theoretical analysis added by the authored further motivated the proposed proxy. 
I encourage the authors to accommodate the reviewers' comments in the revised version. Moreover, some parts, such as the statement in Section 4 (networks with higher ZiCo tend to have better convergence rates and are therefore better) should be revised in accordance to the reviewers comments.

justification_for_why_not_higher_score: This is a nice result but not at the level of an oral presentation
justification_for_why_not_lower_score: The paper proposes one of the best proxies for zero shot NAS
Decision: Accept: notable-top-25%