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: This paper provides an NTK analysis for a class of residual networks with a mixture of activation functions at different layers. The authors derive bounds on the minimum eigenvalue for both finite and infinite width settings. They also give a generalization bound for this class of network architecture.
strengths_and_weaknesses: The main contribution of this work, in my opinion, is a non-trivial derivation of lower and upper bounds on the minimum and for residual networks with a mixture of activation functions. However, analysis and proof techniques are mainly taken from the well-established NTK literature, such as Huang et al., 2020, Oymak and Soltanolkotabi, 2020… Similar generalization bounds are established by Cao and Gu, 2019, and Arora et al., 2019a.

There is an interesting connection to NAS that the authors observe empirically where NAS always picks up RELU and/or Leaky RELU in the optimal search. That coincides with the fact that RELU and LeakyRELU imply larger minimum eigenvalue in the NTK sense. However, deep neural networks in practice do not generally operate in the NTK regime. 

In short, I see this work purely as an NTK analysis rather than an “unifying framework” for NAS. I don’t see how the work studies “optimization and generalization of NAS” or how the derived results guide NAS.

In terms of the presentation, the paper is well-written and easy to follow. One thing I would suggest is to instantiate Theorem 1 with a few special cases, such as the standard 2-layer networks with ReLU activation. Illustrating the Hermite coefficients of such cases would help the readers to compare with existing results, e.g., Oymak and Soltanolkotabi, 2020.
questions: What is the data used in the simulation of minimum eigenvalues of NTK for different activations and architectures?
limitations: N/A
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 extends the Neural Tangent Kernel limit to different (and mixed) activations functions, as well as a varying proportion of skip-connections. Then this paper is able to bound the minimum eigenvalue of the neural tangent kernel matrix, and to link this value to the generalization capability of the model. This allows to guide Neural Architecture search without training.

The authors validate their methods numerically by first showing that the derived bounds match empirical results, and that using their bounds to guide NAS improves NAS performances.


strengths_and_weaknesses: # Originality

While I am not very familiar with the field, this is to my knowledge the first time that an NTK approximation was derived for various and mixed activations functions.

# Quality

The paper contributions seems sounds, though the empirical validation could be more convincing: how well does the criterion rank different architectures?

# Clarity

The paper is clearly written. The title and the abstract, while quite clear, appear to be a little misleading: I don't think this paper helps understanding NAS (for instance NAS convergence), rather than providing a criterion which can help guide NAS.

# Significance

While the empirical results don't show a huge improvement, being able to guide NAS across different activation functions and skip-connections proportions seems useful. The result would be much more significant if it applied to CNN and Transformers, but this is an interesting progress.
I wish the authors had tested their approach on more challenging tasks, and with more competitive activation functions.
questions: Can this framework be used to guide NAS through choices more meaningful than choosing between a ReLu and a Sigmoid?

Could the authors investigate how reliable is their criterion to guide NAS? Maybe something like how often their criterion would rank two models in the correct order?
limitations: The authors clearly state that a big limitation of their work is that it only works for FC networks, and not more common CNN or Transformers.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper provides the theoretical analysis of a fully-connected neural network with mixed activation functions in both infinite and finite width schemes. Furthermore, the authors provide analysis on both lower and upper bounds of minimum eigenvalues of NTK and generalization error bounds in SGD. Finally, the authors provide empirical experiments to support their theoretical claims on NAS problems. 
strengths_and_weaknesses: Strengths
1. Building upon Cao et al. and Nguyen et al.'s proof framework, the author provides the theoretical analysis of the minimal eigenvalue of NTK and generalization error on mixed activation neural networks.

Weaknesses
1. A considerable gap exists between theoretical analysis and the actual NAS problem. Their theoretical results only provide the minimum eigenvalue of NTK and generalization error of a fully-connected neural network with mixed activation functions. I will elaborate on this in more detail in the Question section.
2. NAS-Bench-201 results in Table 2 are not compelling enough. Latest methods such as $\beta$-DARTS [3] or DrNAS [4] find the optimal architecture in NAS-Bench-201.
3. General NAS problems contain a larger degree of freedom in choosing the components of a neural network, not only just activation functions and skip connections. Similar to the first point, there is a considerable discrepancy between the analysis and practice. 
questions: 1. Why does the theoretical analysis of mixed activation neural networks help the understanding of the NAS problem? NAS algorithms such as DARTS or random search WS have two phases: search and evaluation. The authors show just an analysis of the evaluation phase in the paper, which corresponds to the final architecture. In other words, the paper seems to study NTK and generalization bounds on a particular family of the neural network, which has mixed activation functions. 
2. Continuing from the Q1, how do we know architecture found from DARTS or random search RS are optimal architecture as stated in the line 147? 
3. In lines 295-296, the author mentions that DARTS results coincide with the theoretical results. However, a long line of NAS research has shown DARTS's problems ([3, 4, 5, 6, 7]), especially the overfitting. Will other latest algorithms such as $\beta$-DARTS or DRNAS find the same results as DARTS? 
4. In Table 2, Eigen-NAS on CIFAR-10 with $k=20$ seems to converge to sub-optimal architecture with a very small standard deviation of 0.01. Since the optimal architecture achieves $94.37\%$, can we conclude that Eigen-NAS only can find sub-optimal architecture? From 15,625 architecture candidates in NAS-Bench-201, what is the ranking of the architecture Eigen-NAS found? 
5. Can you also verify the numerical results on DARTS Search Space with Eigen-NAS?
limitations: The author provides a thorough theoretical analysis of the minimum eigenvalue on NTK and generalization bounds on a neural network with mixed activation functions. However, the analysis is only for a particular family of neural networks (with mixed activation functions and selective skip-connections). Furthermore, the neural network analysis is on the final architecture, assuming that existing NAS algorithms, such as DARTS,  random search WS, or Eigen-NAS, can find the optimal architecture from their search phase. 

Overall, I see the authors' theoretical analysis is not closely correlated to understanding the actual NAS problem. Furthermore, the empirical performance is far lower than existing state-of-the-art in NAS literature. Therefore, I give a reject. 

1. Cao, Yuan, and Quanquan Gu. "Generalization bounds of stochastic gradient descent for wide and deep neural networks." Advances in neural information processing systems 32 (2019).
2. Nguyen, Quynh, Marco Mondelli, and Guido F. Montufar. "Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep relu networks." International Conference on Machine Learning. PMLR, 2021.
3. Ye, Peng, et al. "b-DARTS: Beta-Decay Regularization for Differentiable Architecture Search." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022.
4. Chen, Xiangning, et al. "Drnas: Dirichlet neural architecture search." arXiv preprint arXiv:2006.10355 (2020).
5. Liang, Hanwen, et al. "Darts+: Improved differentiable architecture search with early stopping." arXiv preprint arXiv:1909.06035 (2019).
6. Dong, Xuanyi, and Yi Yang. "Nas-bench-201: Extending the scope of reproducible neural architecture search." arXiv preprint arXiv:2001.00326 (2020).
7. Yang, Antoine, Pedro M. Esperança, and Fabio M. Carlucci. "NAS evaluation is frustratingly hard." arXiv preprint arXiv:1912.12522 (2019).
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 presents theoretical analyses on Neural Architecture Search using the recent theory of NTK. Especially, it has provided the lower and upper bounds of the minimum eigenvalue of the NTK matrix as well as the generalization bound induced by the NTK matrix for the architectures in their pre-defined search space. Finally, based on these theoretical analyses, this paper develops a training-free NAS algorithm, namely Eigen-NAS. Eigen-NAS has shown its competitive performance in training-free NAS, which in turn also supports the theoretical analyses in this paper.
strengths_and_weaknesses: *Strengths*

1. This paper has provided non-trivial theoretical analyses on NAS using the recent theory of NTK, which may inspire more theoretical studies on NAS in the NAS area.
2. The Eigen-NAS inspired by their theoretical results shows competitive performance on different NAS benchmarks.

*Weaknesses*

1. This paper does not really study the convergence or optimization of NAS as what has been claimed in its title or abstract. Instead, it is mainly focusing on the generalization property of its restricted search space (i.e., a small search space compared with the standard NAS search space).
2. The motivation for why the minimum eigenvalue of NTK needs to be studied and how it is explicitly related to the generalization bound (i.e., Theorem 3) have not been well clarified. As a result, the study of the minimum eigenvalue of NTK in this paper may be less related. Using the minimum eigenvalue of NTK to bound the generalization performance of DNN in Theorem 3 will make the theoretical results in this paper more coherent.
3. This paper does not provide a clear or explicit interpretation of how the theoretical results in this paper can help us understand NAS (shown in the title). Instead, from my own perspective, this paper has mainly developed a generalization bound for NAS and then proposed a training-free NAS algorithm (i.e., Eigen-NAS) inspired by their theoretical results. And such a training-free NAS algorithm is similar to the one in [R1] using the trace norm of the NTK matrix.
questions: 1. This paper focuses on the theoretical study of NAS with only skip connection and activation function search mainly due to the non-trivial analysis of other general structures. Interestingly, both [R2] and Shu et al. [2020] have empirically shown that topology will be more important than diverse operations in NAS, and NAS with only topology search can also provide competitive performance compared with standard NAS. I suppose that these results may also serve as a good motivation to support why the theoretical study on only skip connection and activation function will still be attractive in the literature.
2. In line 98, to my best knowledge, Du et al. [2019] and Nguyen [2021] are studying the convergence of GD instead of SGD.
3. In the problem setting section of this paper, an explicit representation of the classification task (i.e., the binary classification task) and the possible value of $y$ (i.e., $y \in \\{-1,1\\}$) will be more helpful for the readers to understand this section. Similarly, the “cross-entropy loss” in line 111 can more specific, e.g., the cross-entropy loss with a sigmoid function to represent the probability of $y=1$.
4. In line 134, I suppose it should be “we conduct the skip connection search and activation function search independently”. Besides, I am curious about why skip connection search and activation function search can not be conducted jointly.
5. The lemma 1 and therefore the results based on Lemma 1 actually do not match the initialization applied in this paper (i.e., the Gaussian initialization with the variance of $1/m$ instead of $2/m$ in Tirer et al. [2021], Huang et al. [2020], Belfer et al. [2021].).
6. The claim about depth $L$ in line 208 may not be true because whether the minimum eigenvalue will increase or not with larger $L$ highly depends on the activation functions as shown in Figure 3,4. Moreover, I am curious about why the minimum eigenvalue of Tanh does not increase with an increasing $L$ especially when it achieves larger $\beta_1$ and $\beta_2$ and hence a larger upper bound of the minimum eigenvalue than ReLU and Sigmoid? 
7. One of the comments about Table 2 is that the search cost can also be included to verify the improved efficiency of Eigen-NAS over KNAS. Another one is that the recent training-free NAS paper [R1] should also be included in the comparison or discussion. Because [R1] exploits the trace norm of the NTK matrix to indicate the performance of different architectures while this paper exploits the Frobious norm in its Eigen-NAS algorithm (line 324). They are similar.
8. An empirical study of how the number of skip connections layers (i.e., the topology) will affect the performance of neural architectures will be more interesting and related to the NAS area, which can also further verify the impact of the skip connection on the minimum eigenvalue of NTK (Theorem 1, 2) and also the generalization performance of candidate architecture (Theorem 3).

[R1] NASI: Label-and Data-agnostic Neural Architecture Search at Initialization

[R2] Exploring randomly wired neural networks for image recognition
limitations: This paper has provided a valuable discussion about limitations and future works.
review_title: null

Meta-review: metareview: This work relates NAS to the conditioning of a DNN through the NTK framework. This work is well supported theoretically and empirically, and making this connexion is surprising. Given the potential interest for the NAS community, I recommend accepting this paper.
confidence: Certain
Decision: Accept