Venue: NeurIPS 2022 Conference

Reviews:

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 paper theoretically and empirically analyzes the link between connectivity patterns of deep networks and their convergence. Based on this analysis, the authors propose a couple of training-free metrics (effective width and effective depth) and use them to do training-free NAS. The paper presents a thorough link between gradient descent convergence and structural properties of deep networks by proving a link between number of unique paths, number of incoming paths at certain nodes in the network and the least eigenvalue of a Neural Network Gaussian Process (NNGP) variance. Essentially, the authors look at how the NNGP variance changes as the data propagates through the model and relate it to how many unique paths it goes through and how many incoming edges land at the last layer (in the DAG topology used to formulate this problem). These principles are then baked into their “effective depth” and “effective width” metrics that do not require any training or forward/backward passes to compute. Some empirical results are shown for this convergence. The remaining paper looks at training-free NAS by cutting down the search space. Results are shown on CIFAR-10/100, ImageNet-16-120, and ImageNet.
strengths_and_weaknesses: The paper has following strengths:

1. This is a principled approach to study an important problem, i.e., understanding how deep network architecture topologies and connectivity patterns relate to training convergence. Knowing this is obviously very valuable because (a) we can design better models directly without a long, time-consuming search, (b) in future, better understanding of how architectures impact accuracy can enable us to create even more novel models. Indeed, it is a hard problem, so coming up with an intuitive method for this problem is very hard.

2. The proof seems very intuitive and the resulting metrics (effective depth and effective width) are very simple to compute and do not require any training or even forward/backward passes. One can just look at the architecture connectivity and tell with reasonable confidence if it is a good or bad architecture.

3. Empirical results for training convergence and NAS-bench architectures, etc., present some interesting insights (although, they also bring up some questions, see below).

4. Authors have shown experiments all the way to ImageNet which is nice.

Despite the strengths, there are some weaknesses and questions. Addressing these would likely make the paper much stronger:

1. The empirical validation of the theory (section 5.1) is done using only three architecture topologies. This is not that expensive (particularly for MNIST and CIFAR-10). Can the authors look at many different deep nets with different connectivity patterns and somehow present more data on convergence?

2. Experiments section could in general be stronger. For instance, the ImageNet result on TE-NAS is not good enough. We see some accuracy improvement, but we also see model size increase compared to vanilla TE-NAS. Moreover, since the training-free NAS itself is very cheap, further improvements in search time do not make a significant difference. In Figure 5, each point represents a subset of models that achieved a similar accuracy. Were there any interesting patterns in terms of their number of parameters/MACs? Example: did the white/black circles contain models of a certain size in terms of parameter counts? Were the models deeper but narrower within a circle? Or shallower but wider?

3. The very first paper that pioneered the creation of such connectivity-based metrics was reference [R1] cited by the authors. This paper needs to be discussed in much more detail in Section 2.2/2.3 as there are many interesting synergies. For instance, [R1] showed the link between connectivity patterns and training convergence too. [R1] showed very concrete training convergence curves and showed that their proposed metric correlated very well with convergence. The metric proposed by [R1] is also training-free. Indeed, the present study is much more fine-grained, more theoretical, and is more generally applicable than [R1]. 

4. Other weaknesses involve things like there is no characterization of differences in kernel sizes, etc., but this is not critical and can be a good future work.

5. Proof for equation (14) in appendix B has a typo? K_{ii}^{l} should have a square on \sigma (right below “Proof of Lemma 3.2”)? Honestly, this paper could be much stronger if there was a bit more focus on empirical results for justifying the theory (e.g., if section 5.1 was much stronger).

[R1] Bhardwaj, Kartikeya, Guihong Li, and Radu Marculescu. "How does topology influence gradient propagation and model performance of deep networks with DenseNet-type skip connections?." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2021.

questions: Please see the weaknesses section above (particularly points 2 and 3).
limitations: Authors could comment on role of kernel sizes, etc., and how the connectivity alone does not take this into account in the present study.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors proposed a formal analysis framework to estimate the the upper bound of training loss convergence for DAGs with variety of network topologies. Based on that, they proposed a plug-and-play method to speech up previously reported NAS methods by apply a filtration. The results demonstrate the proposed method to search better networks and faster. 
strengths_and_weaknesses: + To my best knowledge, this is perhaps the first theoretical study directly focusing on the fine-grained NN topological connectivity rather than a general NN function, despite some prior works exploring part of that, e.g., [50] for NN width/depth, [69] for skip connection. It is an important yet understudied direction, and this work appears to lay a good foundation. 

+ I have gone over the details of the derivation for the convergence analysis of DNN regarding the connectivity patterns, and it seems sound. For the bound estimation, the authors chose a simplified theoretical model of DAGs + MSE loss, using NNGP kernel. The key step is to estimate the flow of NNGP variance and mean through unidirectional information paths in the specific topology. The theoretical results are examined by a series of simulations in Sec 5.1 and Sec 5.2.

+ The notions of ‘effective depth’ and ‘effective width’ are clearly defined, and the authors also gave clear guidelines how to use them in NAS. It is shown to accelerate two latest NAS methods and outperform more, across multiple benchmarks. The experiments validate the effectiveness of the proposed method. 

In general, I think this is a cool and well-polished paper. One question is the authors demonstrated their down-selection technique to two training-free NAS approaches (NAS-WOT and TE-NAS), which are already very fast and therefore show only non-significant reduction of search time. I wonder why not trying the proposed approach on more costly and accurate search methods, and see if the accuracy-search efficiency gain is still favorable.

questions: See above.
limitations: Current discussion is sufficient.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studied how a wide network’s NNGP kernel can depict the optimization dynamics of a particular DNN topology, by propagating the NNGP kernel spectrum and showing the topology to affect the bound of convergence rate. Based on this observation, the authors created two notions of “efficient depth” and “effective width”, that can be plugged-in existing NAS methods to filter out “unpromising” connectivity patterns for speedup. 
strengths_and_weaknesses: Strength:
This is an important new piece of work towards connecting deep learning theory and NAS. Prior arts already adapted theoretical properties of general DNNs, but never established their correlations with the concrete NN architecture topology, except some empirical correlation observations. This paper is the first to theoretically justify the optimization implication of general DNN topology, which is likely to become a milestone for future work in this frontier.
Throughout the paper, the theory and application aspects are tightly coupled, and the story is coherent. Their claim is theoretically sound (a non-surprising, yet nice adaptation of NNGP proofs). In the experiments, multiple benchmarks are reported, with error bars. 

Section 5.3 is very helpful in understanding how the effective width/depth principles are used to improve NAS in a plug-in fashion. I especially like how the authors can choose d and m in a principled justified way, not ad-hoc.

Overall the writing is very good, clear and easy to follow. It’s a mature paper.

Weakness: 
NNGP is a rough characterization of optimization dynamics, hence its preciseness in comparing architectures is limited. More importantly, as mentioned on lines 280, “Although our d and m are only inspired from the optimization perspective, not the complexity or generalization, our method mainly filters out bad architectures at a coarse level, but does not promote elites in a fine-grained way.” I was not sure whether this optimization-only selection bias will lead us to missing architectures that are excellent in complexity/generalization (hence offsetting their perhaps mediocre optimization behavior). 
The authors applied their principles to accelerating TE-NAS and NAS-WOT. Those are two earliest training-free NAS approaches. Could the authors also try more recent ones and see improvements, e.g., Zen-NAS or zero-cost proxy NAS? Moreover, how about non-training-free NAS methods, can they be accelerated by such pre-filtering too?

In Tables 1 and 2, the FLOPS of searched architectures could be included too.
questions: See above
limitations: No particular negative impact. Limitation was discussed by authors.
review_title: null

Meta-review: metareview: This paper studies the relationship between connectivity of a deep network and its convergence, both theoretically and empirically. The paper also studies simpler metrics such as effective depth and width to guide the architecture search. Overall this is an impressive theoretical paper supported by empirical evidences. 

All the three reviewers find the paper a valuable contribution to an important theoretical problem in deep learning. After reading the rebuttals, Reviewer rAbP recommended to accept this paper in its current form. Reviewer D7qw felt that all the concerns had been well addressed, and increased the score by one. Reviewer 6D9f agreed with the authors' response. 
confidence: Certain
Decision: Accept