Venue: NeurIPS 2022 Conference

Reviews:

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 paper focuses on escaping the NTK regime for gradient descent and provided a comprehensive theoretic analysis toward understanding how a two-layer neural network could escape the NTK regime. Via eigendecomposition of the covariance matrix, the parameter space is partitioned into large, medium (bad) and small (good) directions. With the theoretical guide toward “good” directions, the authors develop a regularizer to encourage parameters moving in these directions. They also demonstrate that the linear and quadratic terms of the Taylor expansion can be used together to fit target functions and leverages from both NTK and QuadNTK to achieve provable improved sample complexity.
strengths_and_weaknesses: Strengths:
1. The paper is well motivated and presented, with detailed explanations of the current limitations of NTK and QuadNTK and clear illustrations of why the focus of this paper raises interest. The structure and logic of the paper are easy to follow and the proof sketch is coherent and helpful for understanding. Generally, the writing of the paper is excellent.
2. The contributions of this paper are well supported by solid evidence both theoretically and empirically. The theoretical proofs are solid as far as I read into, and the codes for the empirical results are available and runnable.

Weakness:
1. The introduced regularizer also introduces many hyperparameters $(\lambda_1,\lambda_2,\lambda_3,\lambda_4)$, which are not fully discussed in the paper. Does this bring limitations to the regularizer as there are many hyperparameters to attend to? In the experiments, there are ablation studies done on varying values of $\lambda_3$ and in the Appendix there are ablation studies on $\lambda_1$. What about the other hyperparameters $(\lambda_2,\lambda_4)$? 

Minor Issues:
1. The legend for figure 1 is a bit unclear since the paper earlier defined $\lambda = (\lambda_1,\lambda_2,\lambda_3,\lambda_4)$, but the experiment is on varying values of $\lambda_3$. It could be clearer by changing $\lambda$ to $\lambda_3$ in the figure. Similarly in Appendix G figure 2, $\lambda$ -> $\lambda_1$.
2. The following work is closely related to the interest of this paper on NTK analysis. The authors may find it valuable to be included in the discussion of related works: Chen et al. "A generalized neural network tangent kernel analysis for two-layer neural networks." Advances in Neural Information Processing Systems 33 (2020).
questions: See weakness and minor issues above.
limitations: The authors discussed the limitations of their work with regard to the assumptions made for their main theorem and the discussion is intact and reasonable to me.
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 authors investigate very wide 2 layer neural networks and their learning dynamics on a special class of target distributions given by sparse polynomials. It has been established that neural networks in the NTK regime exhibit suboptimal sample complexities on such distributions, while QuadNTK, which incorporates a second order term, can improve said complexity. On the other hand, QuadNTK suffers from worse complexities on dense polynomials, compared to the NTK and is hence also not completely satisfactory. The authors show that combining NTK and QuadNTK together with specially designed regularizers can unite the best aspects of the two worlds, enabling the model to efficiently learn a combination of sparse and dense polynomials. The same cannot be achieved with neither NTK nor QuadNTK in isolation. The regularizers are specifically crafted such that weights only move within certain subspaces associated with big and small eigenvalues but ignoring mid-sized ones. While the large eigenspace allows to preserve the benefits from the NTK regime, the small eigenvalues enable large movement of neurons and thus feature learning.
strengths_and_weaknesses: **Strengths:**
1. The paper is very well-written and nicely structured, making it easy to read. 
2. The differences between the lazy learning regime and the “actual” regime in which neural networks usually operate in practice are still not well-understood and making progress in this area would be very helpful to the community. The paper definitely takes steps towards this direction and identifies benefits of operating outside of the kernel regime.
3. The idea of dividing the spectrum into three categories, the large part where the NTK reduces the test error, the middle part responsible for overfitting and the small part where the quadratic term reduces the test error, is very appealing and intuitively makes sense.

**Weaknesses:**
1. Only investigating a polynomial regression setting seems like a very particular restriction and I wonder how much of these theoretical findings translate to real-world problems such as image classification. Is it a good idea (empirically speaking) to ignore the mid-sized eigenvalues for practical tasks (does such a clear clustering of eigenvalues even emerge for non-uniform inputs over the sphere?) or do those regularizers only make sense in the context of polynomial regression? The authors only evaluate their method on polynomial regression tasks but no other benchmark such as CIFAR10 or MNIST. Again, for these distributions the formulation might not even make sense but this would hence pose a significant limitation. I would appreciate if the authors could comment on this.
2. Finding particular distributions where the NTK provably performs worse than standard neural networks is a very sensible thing to do. To my understanding, the polynomial regression task has been already identified as being suboptimally learnt by NTK while the QuadNTK can improve over it in sparse settings. This makes the contribution of this work less clear to me. The fact that QuadNTK is suboptimal for dense polynomials is interesting but I am not sure what is the significance of developping another (somewhat artificially-designed) approach that fixes this particular issue, other than enabling better polynomial regression. Especially if point 1. holds and the approach doesn’t easily extend to more realistic setups with empirical improvements, I am not sure what we can learn from these results.
3. This brings me to my next point/question. The goal (as stated in the introduction) is to understand why NTK might perform suboptimal compared to realistic, finite-width networks. In this work (and the QuadNTK work), it is shown that higher order approximations, together with special regularizers and specific initialization schemes can outperform the NTK in terms of sample complexity. This however somehow does not answer the original question yet, do these new approaches also mimic better what is actually happening in finite networks? This is not entirely obvious to me, given the somewhat unintuitive form of the regularizers, exotic initialization schemes, perturbed SGD instead of SGD etc. For instance, if you were to train finite-width networks on these polynomial tasks, would they be able to efficiently learn both sparse and dense polynomials? Are there similar, bad directions in parameter space where we should not move? Would your regularisers also make sense and lead to performance boosts in this setting? As far as I understood, experiments only concern the newly developed approaches yet no standard setup. Experiments with standard neural networks would really complete the picture in my opinion.
questions: See section above.
limitations: As mentioned above, the relevancy of these results beyond the setting of polynomial regression is not clear and not addressed in the main text.
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 builds on a solid theory for the optimization and generalization of two-layer neural networks fitting polynomials. In particular, they jointly utilize the power of NTK and QuadNTK to fit target functions consisting of a dense low-degree term and a sparse high-degree term, demonstrating its sample complexity is superior to either NTK and QuadNTK.
strengths_and_weaknesses: **Strengths:**
* This paper improves upon the previous QuadNTK, showing that a special form of NN can avoid the kernel regime and achieve better sample complexity than any rotationally invariant kernels while fitting target functions consisting of a dense low-degree term and a sparse high-degree term. Compared to QuadNTK, it benefits from the linear term, providing its power to fit the dense polynomials.
* The paper is well-structured and provides a clear proof sketch. 
**Weaknesses:**
* As mentioned by the author self, some assumptions, i.e., smoothness and nonzero Hermite/Gegenbauer coefficients of the activation function, boundedness of the loss function, sphere distribution of the inputs. These assumptions are mainly technical, but some of them seem to be crucial for the proof techniques, like nonzero Hermite/Gegenbauer coefficients, which might prevent the general impact and application of the proposed methods. 
* The analysis of this paper heavily relies on the regularizers. Hence, my question is about the role of these regularizers. Are they just for the proof simplicity or necessary since we consider the quadratic approximation of the NN. If the answer is the latter, then it seems that there is something different from the model considered in this work might not reflect the practical success of general NNs.
* This paper provides great intuition about how to avoid the blowup of the training loss and population and the usage of the four regularizers. However, it would be great if the authors can provide the intuition why the sample complexity can be reduced from $\Omega(d^{k+1})$ to $O(d^k)$.
* This paper fixed the second layer parameters, which also limits the general impact of this work.
* (typo) The sign in line 273 is wrong. 
questions: Please see the Weaknesses part.
limitations: Please see the Weaknesses part.
review_title: null

Meta-review: metareview: This paper studies the learning dynamics of two-layer neural networks beyond the NTK regime for learning low-degree plus sparse polynomials. The author response and discussion have addressed most of the reviewers’ questions and concerns. While some reviewers think the polynomial regression setting is a bit limited, all the reviewers agree that the results are interesting and significant.  Therefore, I recommend acceptance.
confidence: Certain
Decision: Accept