Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: The paper aims to provide theoretical justification for a "spectral bias" that is observed in training of neural networks: a phenomenon recorded in literature (Rahaman et al.), where lower frequency components of a signal are fit faster than higher frequency ones. The contributions of the paper are as follows:
1. Proves an upper bound on the rate of convergence on the residual error projected on top few eigenfunctions (of a certain integral operator). The upper bound is in terms of the eigenvalues of the corresponding eigenfunctions and is distribution independent.
2. Provides an upper bound on the decay of eigenvalues in the case of depth-2 ReLU networks and also a exact characterization of the eigenfunctions. While such upper bounds and the characterization of eigenfunctions existed in literature earlier, it is argued that the new bounds are better.
3. Combining the above two results, a justification is obtained for the "spectral bias" phenomenon that is recorded in literature.
4. Some toy experiments are provided to exhibit the spectral bias phenomenon.

Recommendation:
I recommend "weak acceptance". The paper takes a step towards explaining the phenomenon of spectral bias in deep learning. While concrete progress is made in the context of depth-2 ReLU networks (even though in NTK regime), perhaps the ideas could be extended to deeper networks.

Technical comments:
- It is argued that the new bound of $O(\mathrm{min}(k^{-d-1}, d^{-k+1}))$ is better than the bound of $O(k^{-d-1})$ from the previous work of Bietti and Mairal, in the regime where $d \gg k$. I think there is a typo here. In the regime of $d \gg k$, the bound $k^{-d-1}$ is the smaller one so both bounds are comparable. It is argued that $d \gg k$ is the more relevant regime, but then there isn't any improvement here.
- The proof of spectral analysis is said to follow a similar outline as compared to the prior work of Bietti-Mairal, but it is not clear to me where this new proof deviates and improves on prior techniques? Or is it just a more careful analysis of the prior techniques?
- The proof operates in the "Neural Tangent Kernel" regime, by considering hugely overparameterized networks. This can be viewed as a negative thing, but then, most results in literature also operate in this regime and it is a major challenge for the field to prove results in the mildly overparameterized / non-NTK regime!

Potential suggestions for improvement:
- In Section 4: the y-axis of the graph is labeled "error's coefficient" which is non-informative. Is it $|a_k - \hat{a}_k|$ ? I also had a question here about the proposed Nystrom method: Why is it okay to use the training points in the Nystrom method. Ideally, we should use freshly sampled points. Is there a justification for using the training points? If not, perhaps it is best to go with freshly sampled points.
- I felt the proofs in the Appendix are very opaque and it is hard to pinpoint what the new insight is (at least for a reader, like me, who does not have an in-depth familiarity with these convergence proofs).

review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: I must qualify my review by stating that I am not an expert in kernel methods, and the mathematics in the proof is more advanced than I typically use. So it is possible that there are technical flaws to this work that I did not notice.

That being said, I found this to be quite an interesting paper. It provides a concise explanation for the types of features learned by ANNs: those that correspond to the largest eigenvalues of the kernel function. Because these typically correspond to the lowest-frequency components, this means that the ANNs tend to first learn the low frequency components of their target functions. This provides a nice explanation for how ANNs can both: a) have enough capacity to memorize random data; yet b) generalize fairly well in many tasks with structured input data. In the case of structured data, there are low frequency components that correspond to successfully generalized solutions.

I have a few questions about the generality of this result, and its application to make better machine learning systems:

1) As far as I can tell, the proof applies strictly vanilla SGD (algorithm 1). Would it be possible to extend this proof to other optimizers (say, ADAM)? That extension would help to connect this theory to the practical side of the field.

2)  Given that the kernel depends on the loss function, and it's the eigenspectrum of the kernel's integrator operator that determines the convergence properties, can this work be applied to engineering better loss functions for practical applications? 

review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: This paper studies the training of overparametrized neural networks by gradient descent. More precisely, the authors consider the neural tangent regime (NTK regime). That is, the weights are chosen sufficiently large and the neural network is sufficiently overparametrized. It has been observed that in this scenario, the neural network behaves approximately like a linear function of its weights.

In this regime, the authors show that, the directions corresponding to larger eigenvalues of the neural tangent kernel are learned first. As this corresponds to learning lower-degree polynomials first, the authors claim that this explains the "spectral bias" observed in previous papers.

-I think that from a mathematical point of view, the main result of this paper is what one would expect intuitively: 
When performing gradient descent with quadratic loss where the function to be learnt is linear, it is common knowledge that convergence is faster on directions corresponding to larger singular values. Since in the NTK regime, the neural network can be approximated by a linear function around the initialization one expects the behavior predicted by the main results. From a theoretical perspective, I see the main contribution of the paper as making this statement precise.

-I am skeptical about some of the implications for practitioners, which are given by the authors: 
For example, on p.5 the authors write "Therefore, Theorem 3.2 theoretically explains the empirical observations given in Rahaman et al. (2018), and demonstrates that the difficulty of a function to be learned by neural network should be studied in the eigenspace of neural tangent kernel." To the best of my knowledge, it is unclear whether practitioners train neural networks in the NTK regime (see, e.g., [1]). Moreover, I am wondering whether some of the assumptions of their theorem are really met in practice. For example, the required sample size for higher order polynomials grows exponentially fast with the order and the required step size goes to zero exponentially fast. Does this really correspond to what is observed in practice? (Or is this a mere artifact of training in the NTK regime?)  Is this what one observes in the experiments by Ramahan?

I think the paper is not yet ready for being published.
 1. There are many typos. Here is an (very incomplete) list.
    -p. 2: "Su and Yang (2019)" improves the convergence..."
    -p. 2: "This theorem gives finer-grained control on error term's"
    -p. 2: "We present a more general results"
    -p. 4: "The variance follows the principal..."
    -p. 4: "...we will present Mercer decomposition in (the) next section."
2. I think that the presentation can be polished and many statements are somewhat unclear. For example, on p. 7 the authors write "the convergence rates [...] are exactly predicted by our theory in a qualitative sense."
    The meaning of this sentence is unclear to me. Does that mean in a quantitative sense? To be honest, only considering Fig. 1 I am not able to assess whether the convergence rates of the different components are truly linear. 

I decided for my rating of the paper because of the following reasons:
-I think that for a theory paper the results obtained by the authors are not enough, as they are rather direct consequences of the "near-linearity" of the neural network around the initialization.
-In my view, there is a huge gap between current theoretical results for deep learning and practice. For this reason, it is not problematic for me that it is unclear, what the results in this paper mean for practitioners. (Apart from that, results for the NTK regime are interesting in its own right.) However, in my view, one should explain the limitations of the theory more carefully.
-The presentation of the paper needs to be improved.

References:
[1] A note on lazy training in supervised differentiable programming. L Chizat, F Bach - arXiv preprint arXiv:1812.07956, 2018 



-----------------------------

I highly appreciate the authors' detailed response. However, I feel that the paper does not contain enough novelty to justify acceptance.

------
"Equation (8) in Arora et al., (2019b) only provides a bound on the whole residual vector, i.e., , and therefore cannot show different convergence rates along different directions."

When going through Section 4 , I think that it is implicitly stated that one has different convergence along different directions.
-----
For this reason, I am not going to change my score.

review_title: Official Blind Review #2

Meta-review: The authors propose to understand spectral bias during training of neural networks from the perspective of the NTK. While reviewers appreciated aspects of the work, the general consensus was that the current version is not ready for publication; some concerns stem from whether the the NTK model and finite neural networks are sufficiently similar that we should be able to gain real practical insights into the behaviour of finite models. This is partly an empirical question, and stronger experiments are required to have a better sense of the answer. Nonetheless, the authors are encouraged to persist with this work, taking into account reviewer comments in future revisions.


Decision: Reject