Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper introduces novel results on the optimization and generalization of three-layer networks, optimized with a variant of gradient-descent. The goal of the analysis introduced in the paper is to obtain bounds that improve over the bounds obtained using the well-studied NTK framework. Namely, the aim is to go beyond the "lazy training" regime to allow for better bounds on learning more complex functions/distributions.
main_review: The motivation of the paper is very clear and convincing. The analysis of neural networks using the NTK is known to have its limits, and the effort to provide generalization and optimization results beyond this regime is one of the main challenges of the theoretical machine learning community when studying deep learning. Furthermore, the techniques used in the paper can be of independent interest, and can benefit others trying to study optimization of neural networks. However, I have a few concerns regarding the results introduced in the paper.

The paper suggests three possible improvements on NTK analysis:
1. Faster rates, with 1/n dependence on the number of examples instead of 1/sqrt(n) as in e.g. Arora et al. 2019.
2. Relaxation of the realizability assumption that is sometimes made in NTK results, allowing for generalization bounds in the presence of noise.
3. A better complexity measure of the data/target, that allows the rate to be adaptive to some data-dependent complexity.

It seems to me that the first two improvements can be achieved by a more careful analysis of the NTK case (specifically, the authors acknowledge that using a smoothed loss the same fast-rate can be achieved in Arora et al 2019a). So, the main reason to go through the effort of analyzing the network beyond the NTK regime (and also analyzing a somewhat non-standard version of SGD), is to get the third point. Namely, the main contribution of the paper is in presenting a complexity measure that gives generalization bounds that are better than those that can be obtained by the complexity measure of the NTK (the RKHS norm of the NTK).

However, it is not clear to me why the new complexity measure offered in the paper improves over the NTK. Indeed, the authors show that it is upper bounded by the NTK-based complexity, but showing that this measure is "better" requires some case where the error of NTK can be lower-bounded, to show a gap between the two methods. In other words, can you show some example of data/function/distribution where your method yields an upper bound on the loss that is significantly smaller than the best possible bound obtained by the NTK? or even better, by any kernel method? If so, this should be emphasised in the paper.

Related to this point, I believe that the discussion on adaptivity of the kernel is a little misleading. The authors claim that the difference between their analysis and the NTK analysis is that in the later the kernel is fixed while in the former the kernel can be chosen depending on the data. However, the kernel cannot be chosen freely, but from some restricted family of kernels. But it is not clear exactly how this family of kernels is restricted, and whether this does not end up being equivalent to learning with some fixed kernel that is different from the NTK. So, please clarify whether this adaptivity truly goes beyond the regime of learning with kernels, or just improves by using a "better" (but fixed) kernel.

Another point that could be improved is the technical introduction of the complexity measure. I found it hard to follow all the different kernels that were introduced, and how these were derived from the architecture. I think that working with some concrete example of a function (possibly some function that is "beyond the NTK regime") and calculating its complexity, will make it easier to understand the exact notion of complexity.

Overall, I believe the paper makes worthy contributions, and I am willing to raise my score if my concerns are answered.

===========================================================

After discussion with the authors, I still believe the results could be much stronger if the authors would show a clear gap between NTK and their analysis. However, the paper does offer new bounds and novel analysis techniques which are important contributions, and therefore I am raising my score.
summary_of_the_review: The paper provides novel results analyzing optimization and generalization of three-layer neural networks. However, my main concern is that the paper does not provide theoretical evidence that the bounds are indeed strictly and significantly stronger than what can be obtained by learning with the NTK, or more generally using kernels. I am willing to raise my score if my concerns are answered.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper makes contributions into two main category:

1. Algorithmically, it propose a projected SGD algorithm that can, in polynomial number of iteration, reaches a solution that generalizes.
2. In terms of generalization, it proposes a new generalization bound with data-dependent complexity measure that goes beyond NTK regime. Another generalization bound, based on a new function norm (minimum RKHS norm w.r.t. a family of kernels) is proposed. The proposed bound shows *adaptivity* nature of the generalization results. 


main_review: Main review:
1. Strength:
    1. The results obtained here, especially on the proposed function norm (minimum RKHS norm) is interesting. It would be better if the authors can provide further comments on the key difference between the data-dependent complexity measure bound and the function-norm based bound. 
    2. The paper is well written. I appreciate the author’s efforts in making the presentation clear, consider the paper itself is fairly technical in nature. 
    3. The discussion with related work is sufficient and difference with prior work are pointed out clearly, as section 3.3 and 3.4 the authors discuss in details how the results differs with kernel learning and NTK regime results.
2. Weakness: 
    1. The training objective in (1) is clearly not the standard loss in practice, considering the additional $W^{(0)}, V^{(0)}, W^s$ that  are not optimized during training, the authors should comment more on why this additional terms are introduced and what’s their implication for analysis.
    2. The proposed algorithm has an additional projection step that makes $V_j’ \perp \phi^{(0)}(x_i)$, it is unclear to me why this projection step is necessary (is it essential in establishing convergence beyond NTK regime?). This technical requirement is not sufficiently motivated in the current version. 


summary_of_the_review: Summary of Review:
1. The paper makes a fairly interesting technical contribution: the proposed generalization bound poses adaptive nature, it improves the current kernel based bound (NTK) by selecting the best kernel that tradeoff data fitting and complexity.
2. The presentation is mostly clear, and the author clearly make efforts to compliment technical results with rich discussions. However, some technical conditions imposed in the loss and algorithm are not sufficiently motivated or explained.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper presents a theoretical analysis of a 3 layer neural network with ReLU activations. The main result is introduction of adaptive generalization bounds that are defined for a modified SGD algorithm. These bounds are robust to noise and data dependent. 

The idea is to define a product kernel for the second layer of the form $K^{\infty}\odot G$, where $$K^{\infty}$ is fixed and $G$ is adaptive and can be modified so that $g_k$ has minimum possible norms. This leads to a definition of a complexity measure that together with a simple modification to the SGD algorithm defines a bound on the population risk.
main_review: The paper present quite an interesting analysis and packs a lot of material in 9 page of main text and 101 pages of Appendix material. While it is generally well written, it is not very accessible for a casual ICLR reader with no background in theoretical computer science. Since I'm not an expert in this, I'll defer to the other reviewers to check the significance and correctness of this paper. Below I provide only some superficial comments that hopefully help authors improve the paper a little.

$K^{\infty}$, $\tilde K^{\infty}$ is never properly defined and can be implied only from the context. Generally, the paper defines _quite a lot_ of notation during its length, I think it would benefit a lot from proper definition of the terms being used, at least in the Appendix

Features $g_k$ in section 2 appear without definition and it is not clear its relation with $G$. When it is used in eq.9 it is not clear what is the number of intermediate features and how it is defined.
nit: some of the acronyms might not be familiar to a typical ICLR reader
- a.s. 
- ' symbols are used as vars (e.g. \phi'), but are confusing as they have same notation as a partial derivatives. This can be easily avoid by ~ or \hat symbols.
- population risk
summary_of_the_review: Theoretical paper defining a a novel bound for a 3-layer network. Since I'm not an expert in this field, I can provide only superficial comments to the paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the behavior of a three-layer neural network trained by a projected SGD algorithm. The authors theoretically show that, in this setting the neural network has more complicated behavior than in the NTK regime. Instead of sticking at one kernel, now the neural network explores different kernels decided by the features learned by the first layer. Therefore, the generalization error is bounded by a minimum of many RKHS norms, and is proven to be smaller than the single NTK norm. The proposed generalization error bound outperforms the NTK bound. For target functions in the NTK, the proposed bound is no bigger than the NTK bound. The model and the algorithm are close to commonly used ones, while there are components specially designed for the theoretical analysis. 
main_review: The theory of NTK provides a beautiful theoretical tools to analyze the convergence of generalization of neural network models in highly over-parameterized regime. Yet, essentially a linear analysis, NTK cannot characterize feature learning of neural networks, and practice neural networks work out of the NTK regime. Hence, theoretical study of neural network dynamics beyond the NTK regime is crucial for the understanding of the success of neural networks. This work tries to explore the beyond-NTK regime in a special case. Though both the model and the algorithm are specifically designed for theoretical analysis, the work done in this paper is still meaningful, because it provides an approach to analyze the feature learning effect of neural networks. 

The major comment from the reviewer is about the comparison of the setting with NTK. The reviewer hope the authors can make it clearer why the studied setting is different from NTK. Is it because the neural network is less wide than required by NTK, or because the network structure makes go beyond NTK, or because the project SGD algorithm prevent the network from entering the NTK regime? 
summary_of_the_review: The paper studies the optimization and generalization of a three-layer neural network trained by a projected SGD algorithm. In this setting, the network runs beyond the NTK regime. Hence, it can achieve feature learning, and better generalization performance than NTK. Specifically, the generalization error is bounded by a complexity depending on the minimum of a family of RKHS norms. This paper explores the behavior of neural networks out of the NTK regime, which is important due to 1) the existence of feature learning, and 2) closer settings to practice.
review_title: null

Meta-review: This paper goes beyond the NTK setting in analyzing optimization and generalization in ReLU networks. It nicely generalizes NTK by showing that generalization depends on a family of kernels rather than the single NTK. The reviewers appreciated the results. One thing that is missing is a clear separation between NTK results and the ones proposed here. Although it is ok to defer this to future work, a discussion of this point in the paper would be helpful.
Decision: Accept (Poster)