Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors study gradient flow on the empirical squared loss. More specifically, they consider the evolution in function space of the residuals and show that it can be written as the sum of 1) the residual obtained by training with the NTK operator (infinite width and samples, no training of the kernel), and 2) damped deviations between time dependent kernel matrix and the NTK operator. Based on this decomposition and a uniform deviation bound on the NTK, they show that 1) in the underparametrized regime, GD at the beginning of the dynamics learn eigenfunctions of NTK at rates proportional to the corresponding eigenvalues; 2) in the overparametrized regime, they derive new bounds for the `kernel regime’ to appear; 3) in the overparametrized regime, if we further assume that the target function is aligned with the top eigenvectors of the NTK, then a milder overparametrization is required.
main_review: The paper is well-written and somehow clear and easy to follow. As far as I checked, it is technically sound (I did not go through all the appendices). The authors added plenty of discussions and comparison with previous work. I particularly appreciated the residual evolution equation with the damped deviations, which is quite simple, giving good intuition on the dynamics, and is new as far as I can tell. However I have a few concerns:

I am not convinced about the novelty of the contributions in this paper. The uniform Lipschitzness of the Kernel function + a bound on the change of the weights were obtained in several papers (e.g., 'On the linearity of large non-linear models: when and why the tangent kernel is constant', Liu et al.), which are the main ingredients of the uniform NTK concentration. Considering the change of the residuals (admittedly, only on the empirical data) along the eigenvectors of the NTK was already considered in 'Towards Understanding the Spectral Bias of Deep Learning’, Cao et al. While there is value in working out the technical details, I think the results in this paper are quite expected and not much surprising. At the start of the dynamics, the weights are close enough to initialization for the evolution to follow the NTK and be biased toward the top eigenvectors.  

There has been a lot of works that are studying the NTK regime. Here, the authors consider the change of the function along the data-independent eigendirections of the NTK (the fact that we are using early stopping is another clue that we are not escaping the NTK regime). Several works have showed convincingly that the interesting question is to study how GD escape the RKHS and learn functions that are not aligned with NTK, which I am not convinced can be done with these techniques. Furthermore, the spectral bias is well understood  for linear models and kernel methods, which is approximately the behavior of models at the beginning of GD so that we don’t need much overparametrization in order to still be able to get NTK-like behavior.

If the point is to study the underparametrized regime, other work like 'Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration’ (Mei et al.) showed that training only the second layer (random features model), $\min(n,m) \geq d^{\delta} / \sigma_k$ is enough to learn perfectly the top $k$ eigenvectors, which is much tighter than the results in Corollary 3.6. I am not sure that developing more techniques to study the NTK regime is interesting or helpful, especially if they are not tight with respect to the dependency on the different parameters.
summary_of_the_review: I am not convinced that the current paper is bringing anything new to what is already known about the `spectral bias’ in the NTK regime, even though I believe the technical contribution to be non-trivial. For that reason, my recommendation is marginally below the acceptance threshold. If the authors can convince me that this damped equation can be used in more interesting ways (take target function in a different RKHS or use $K^\infty$ that is not the NTK etc.) or that I misunderstood or missed some important conceptual/technical contributions, I will raise my recommendation!
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work studies the implicit bias of optimizing underparametrized neural networks with MSE loss function and establishes upper-bounds on the training error. One of the takeaways of the paper is that under-parametrized neural networks first learn the most important eigenfunctions associated with the NTK integral operator. This is what the work posits as the implicit bias of gradient-descent in this setting. A key tool developed in the paper is the concept of damped deviations, where in the evolution of MSe w.r.t to one kernel is related to that of another kernel and the damped "distance" between these kernels. As a byproduct, the paper uses this tool to extend certain results in the literature in the over-parametrized setting.
main_review: Strengths
----
- The work provides an original treatment of neural networks in under-parametrized regime. A number of new results are established.
- The paper is well-written and easy to follow.
- The paper appears to be technically correct. The theoretical setting of the paper is clearly stated.
- The tecniques developed in this paper are powerful enough to recover and extend previous works even in the over-parametrized regime.

Limitations
---
- My main critic is that the ssumptions of the paper exclude nonsmooth activation functions,  for example (perhaps) the most important activation function known to both practitioners and theoreticians alike: the ReLU. Which part aspect of the proofs needs smoothness of the activation function ?
- The analysis in this paper is for continuous time gradient-descent (i.e gradient-flow). Which aspects of the results would continue to hold after time discretization ?
- There have been other contributions on the function-space view of neural gradient descent on neural networks (for example Ongie et al. "A FUNCTION SPACE VIEW OF BOUNDED NORM INFINITE WIDTH RELU NETS: THE MULTIVARIATE CASE", ICLR 2020). Is there any comparison to be made here ?

Questions
---
- All the results in this paper appear to be about training error. Can anything be said about generalization error, i.e $\mathbb E_{x \sim \rho}[r_t(x)^2]$ ?

summary_of_the_review: A new function-space view of gradient-flow on neural networks. Establishes that in function space, dynamics of training (when projected along the most important eigendirections of the associated kernel integral operator, is very similary to NTK dynamics, even in under-parametrized regime.


After authors' response
---

My concerns have been fully addressed by the reviewers. I'm raising my score from 6 to 8, and therefore strongly recommending the paper for acceptance.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In the paper under review, the authors study the behaviour of gradient flow in the kernel regime of one hidden layer neural networks. More precisely, they show deviations bounds on the test error  w.r.t. the true NTK gradient flow in the underparametrized regime and train error bounds in the overparametrized regime.
main_review: First, I would like to say that I am nor an expert neither a contributor of the abundant NTK literature. Hence, even if I know well the phenomenon as well as kernel methods, I might under-appreciate the novelty of the bounds presented in the paper under review.

That being said, I have to say that the *story of the paper* is clearly written with a nice introduction that makes the reader eager to discover what is really in it. The question: « to what extent is the NTK informative outside the NTK regime ?» could be of primal importance and introduces nicely the paper. *However*, when it comes to the paper itself, I have to say that I was a bit disappointed. 

First, the two last paragraphs of the related work are a bit fuzzy comparing bounds with previous papers that are not so much in the exact setting, and furthermore not explaining why it is interesting to have improved these bounds, or considered another setting. That made me think: *what is the actual message of the paper ?* This impression is reinforced by the fact that the title indicates that the focus will be on the implicit bias of neural networks whereas it is really on the NTK regime and hence on the implicit bias of kernel methods.

Going further, my main problem on this paper comes with the second disappointment: in my opinion, the paper does not really study neural nets outside the NTK regime as either it compares to the NTK itself for the test error (Theorem 3.5) or either show convergence to 0 of the train error (Theorems 3.7 and 3.8). In other words, the authors suggest that their damped deviation analysis could be the first stone towards getting a bit out of the NTK regime, but under the current form, I am not very convinced by the argument.  On the one side, I understand that obviously this is not the aim of Theorems 3.7 and 3.8 that could be nice technical contributions of their own (once again I lack some knowledge in this specific domain and do not know how impactful these results are). On the other side, in my opinion, Theorem 3.5 and Corollary 3.6 really describe regimes (underparametrized with large $m$ and $n$) under which the trajectory of the gradient flow remains in the vicinity of the trajectory of the true NTK gradient flow. Then the fact that the estimator given by the flow learns first eigenfunctions of the integral operator related to large eigenvalues in usual in kernel methods. In my opinion getting outside of the NTK regime requires other analysis than the one given in Theorem 3.4: that is I cannot consider new an analysis that presents systematically deviations from the Neural Tangent Kernel.

**In conclusion**, I am not saying that the results are not interesting, but in my opinion they are quite *expected* and are not conceptual novelties but rather technical ones. To what extend these are new, I do not know. 




Minor Typos:

- page 2, 3rd paragraph : « generalizeation » 
- page 2, 4th paragraph : « is is smaller by… » 
- page4, authors may precise that $L^2$ is in fact $L^2_\rho$, precise also that $\kappa$ is finite under mild assumptions on the model but not always the case
- page4, lemma 2.1, put a « and » before $G_s$ 
summary_of_the_review: As a non-specialist of the NTK regime, I may underestimate the technical contribution of the present paper, but I was not surprised by the results and see the submission as a detailed and nice technical improvement of known results in the NTK regime. Hence, I am between neutral and unsatisfied by the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers the gradient flow training of 2-layer neural network (both layers are trained) and provides a theoretical tool termed “damped deviations” for improved NTK analysis. One outcome is a characterization of how a neural network deviates, when in an underparameterized regime, from learning the eigenfunctions of the integral operator associated with infinite width NTK at rates proportional to the corresponding eigenvalues.
main_review: This is an interesting theoretical work. The main technique of analysis, if I understood correctly, is to use the infinite width NTK dynamics, which is linear, as an auxiliary term to add and subtract from the actual dynamics, and leverage Duhamel’s principle to study the finite width situations. This is not a completely new trick, as it is often used in the mathematical literature for differential equations; nevertheless, I still think it is remarkable to actually execute the idea (well) for the important problem of neural networks, even if it’s just deterministic gradient flow and 2-layer. I therefore gave a positive rating. Still, there are a few things that I’d like to understand better, hence the followings.

One of my questions is, quantitatively, what regime is exactly the underparameterized regime considered in Theorem 3.5? I’m confused because I didn’t find any assumption on n (number of data). Is it implicitly assumed that Theorem 3.5 applies when $n>m$? Why is the lower bound of $m$ in Theorem 3.5 independent of $n$?

Another question about Theorem 3.5 is, are $\Gamma$ and $T$ really just any numbers that satisfy $\Gamma>1$ and $T>0$? If yes, why not optimize over them to get the best bound?

One more question is, did I understand right about Theorem 3.5 that $exp(-T_K t)r_0$ is decreasing but the bound on its difference from $r_t$ is growing quadratically in t? Wouldn’t this produce a low “signal-to-error” ratio?

I’m also wondering about the gap between the underparameterized regime in Section 3.2 and the overparameterized regime in Section 3.3. If 3.2 really requires $n>m$ (see above), the gap is rather large. What can happen there? Some explanations in the main paper would be very helpful.

I also found the comparison with [Arora et al. 2019] and [Su & Yang 2019] helpful. I understand that this work trains both layers and there are many other important differences (well stated in the paper and thus omitted here), but these are mostly in terms of the results. Could the authors also comment about the differences (and similarities) in terms of the analysis techniques?

A couple of minor observations:

* Section 1.1 Related work, reference Weinan E (2020) should be [E et al. 2020]

* Lemma 2.1 “… semidefinite matrix $G_s$ the time dependent …” probably means “… semidefinite matrix and $G_s$ be the time dependent …”

* No empirical results are provided. This is probably okay, but of course if the tightness of the theoretical results could be supported by empirical evidence, it would be fantastic.

summary_of_the_review: I found this work very interesting. The proposed theoretical tool of “damped deviations” is useful, and the outcome (the “characterization”, see Summary of The Paper) is a nontrivial step for the important task of going beyond infinite overparameterization.
review_title: null

Meta-review: There was a healthy discussion with all the reviewers with a consensus that the results are somewhat expected and unlikely to shed light beyond the ntk  regime, yet within the confine of ntk there is a solid and nicely written technical contribution.
Decision: Accept (Poster)