Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper examined the spectrum of NNGP and NTK kernels and answer several questions about deep networks using both analytical results and experimental evidence:
* Are randomly initialized and trained deep networks biased to simple functions?
* How does this change with depth, activation function, and initialization?

All studies are conducted on a space of inputs that is a boolean cube. The input distribution is assumed to be uniform. Though it is argued in Section 3 that the results also generalize to uniform distributions on spheres and isotropic Gaussian distributions. Although this boolean cube setting is followed from previous works on the same topic, it does limit the scope of the paper. Discussions on how this assumption relates to practical problems are missing from the paper.

Putting aside the limitations of restricting the input distributions on boolean cubes (and other similar choices), I really like the paper, which demonstrates the powerfulness of spectral analysis. I also found that many analytical results (e.g., computing eigenvalues of a kernel operator with respect to uniform distributions on a boolean cube) in the paper are highly nontrivial to derive, which adds to the value of the paper. These results might seem restricted in terms of deep network theory because of the assumptions on input distributions, but I do believe the methods used can be of interest to a wider audience.

Some questions:
* In Figure 1, the 10^4 boolean function samples are sorted according to frequency (rank). What precisely is the frequency (rank) here? It shouldn't be the frequency that corresponds to the eigendecomposition because each function sample could always have multiple components with different frequencies.
* In Figure 1b, the y-axis is described as normalized eigenvalues, which seems different from degree k fractional variance defined in the next section. The degree k fractional variance is the sum of all normalized eigenvalues for degree k eigenfunctions. Is this difference intended or it is a mistake?
* Is the ground truth degree k polynomial used in experiments defined somewhere in the paper?

On writing and clarity. Overall I find this paper well-written and a pleasure to read. Some minor issues are
* The definition of "neural kernels" seems unnecessary and a bit sudden. It would be helpful to include the definition of Phi just after Eq. (2) for CK and NTK.
* For introducing boolean analysis and Fourier series, it might be better to include the formula that explicit shows the expansion f(x) = \sum_{S} f^p(S) X_S(x) before introducing Theorem 3.1.

review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: Aiming to resolve the question whether and why deep networks are biased towards simple functions, this paper gives a spectral analysis on neural networks' conjugate kernel(CK) and neural tangent kernel(NTK) on boolean cube. The eigenfunctions are identified and the eigenvalues are shown computable in polynomial time. Another main contribution of this paper is showing that the simplicity bias exists at least in a weak sense.

I believe that this paper should be weakly rejected because it made more claims than what it can show in that the analysis doesn't work in real space, and the authors did not really show the simplicity bias. The following are my detailed comments.

First, the whole analysis is based on boolean cube. Although the paper has shown empirically that in high dimension the uniform binary distribution is close enough to the uniform sphere distribution, it doesn't suffice to substitute boolean cube for sphere in real space. The spectral analysis in this paper is heavily due to working on boolean cube. The boolean cube is finite, which guarantees any inner-product kernel function $K(x,y) = \Phi (<x,y>)$ can be diagonalized by finite many monomial functions, And there are only O(d) different eigenvalues, which enables efficient computation. These techniques are not easy to be transferred to real space. The experiment shows that the first five eigenvalues in boolean cube, sphere, gaussian is close, but key problems here are first, in practive the dimension $d$ could be smaller and second, sphere and gaussian have infinitely many eigenvalues while boolean cube has $2^d$ eigenvalues. The experiment cannot really justify that all eigenvalues are close (only first several are shown), not to mention the tail eigenvalues over the first $2^d$-th.

Even if we assume that boolean cube is a reasonable choice, we should notice the goal of computing eigenvalues is to eventually show the inductive bias toward 'simple functions'. However, the authors failed to show it at least from the following perspectives:
1) This paper did not show the trend of eigenvalues, but only the weak version of, for example, $\mu_{2k-2} > \mu_{2k}$. In the limiting case, it is more reasonable to fix dimension $d$ rather than the degree $k$.
2) Working on boolean cube leads to limited complexity. The most complicated base function is restricted to $\mathcal{X}_S$ where $S = \{1, 2, \dots, d\}$. So the weak simplicity bias theorem actually only describes the relation among finite $d$ eigenvalues.
3) No optimization arguments appear in this paper. Based on the spectral analysis, it is not rigorous enough to claim the networks are biased to simple functions, given that the target function consists of simple multilinear monomial functions. 

Since the boolean spectra is not a reliable measure, the further experiments under such a measure is therefore put under doubt.

To summarize, this paper definitely contains some rigorous analysis which I appreciate, but it made some claims that are not verified. More importantly, the boolean cube is not the appropriate domain which is hard to generalize to real space and the simplicity bias theorem in this paper is to some extent weak. Therefore, I suggest rejecting this paper in its current form.
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: Updates:

Thanks for the updates. 

I find the new theoretical results interesting and potentially useful,  which shows, in the large $d$ setting, spectrums of CKs/NTKs  for boolean cube, sphere and isotropic Gaussian are closed to each other in some sense. Thus, I raise my score to weakly accepted but lower down my confidence level since I am not that familiar with Boolean cube literature. 


------------------------------------------------------
The study of extremely over-parameterized networks (i.e. infinitely width networks) has become one of the most active research directions in theory deep learning. The key objects in understanding such networks are the conjugate kernel [1, 2] (CK defined in the paper) and the Neural tangent kernels [3] (NTK). The CK characterizes how the network looks like at initialization (connection to Gaussian processes as well) and the NTK is very useful to characterize the gradient descent training dynamics of large width networks in the kernel regime. Understanding properties of such kernels, in particular, their spectra distribution and eigenspace, could be potentially an important step towards a finer-gained understanding of generalization in neural networks.   

The main contribution of this paper is the development of the spectral theory of CK and NTK on boolean cube (similar or weaker results on uniform distribution in spheres and Gaussian distribution in R^n). More precisely, the authors show that, over the space of boolean cube, the CK/NTK could be diagonalized using the Fourier basis and the eigenvalues depend only on the frequency (i.e. the degree of the monomials); Thm 3.1. The authors also develop some computation tools to compute the spectra; Lemma 3.2.   Using the tools developed in this paper, the authors are able to clarify some of the interesting observations found by other researchers. Most noticeably, the authors show that the observation in [4] 'neural network is biased towards simple functions' is NOT universal. Whether this statement is correct or not depends heavily on the choice of activation function (e.g. Relu v.s. Erf) and hyper-parameters (e.g. weight variance, depths).  There are also some other interesting empirical findings: the optimal depth of a neural network depends on the complexity (i.e. degree in the boolean cube setting) of the function to learn, CK (i.e. training only the last layer) tends to be more useful for learning less complex functions, etc. 

Overall, this is a nice paper. I am leaning for a weakly accept. 


[1] Amit Daniely, Roy Frostig, and Yoram Singer. Toward Deeper Understanding of Neural Networks:
The Power of Initialization and a Dual View on Expressivity. arXiv:1602.05897 [cs, stat], February
2016.
[2] Jaehoon Lee, Yasaman Bahri, Roman Novak, Sam Schoenholz, Jeffrey Pennington, and Jascha
Sohl-dickstein. Deep Neural Networks as Gaussian Processes. In International Conference on
Learning Representations, 2018.
[3] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural Tangent Kernel: Convergence and
Generalization in Neural Networks. arXiv:1806.07572 [cs, math, stat], June 2018. 00000
[4] Guillermo Valle-Pérez, Chico Q. Camargo, and Ard A. Louis. Deep learning generalizes because
the parameter-function map is biased towards simple functions. arXiv:1805.08522 [cs, stat], May
2018.

review_title: Official Blind Review #2

Meta-review: The authors develop a spectral analysis on the boolean cube for the neural "conjugate kernel" (CK) and "tangent kernel" (NTK). The analysis sheds light into inductive biases of neural networks, such as whether they are biased to simple functions.  

This work contains rigorous analysis and theory which is useful for further discussions. However, the theory and insights do not feel complete. One important drawback is that the analysis is limited by the boolean cube setting; this also means that it is more difficult to link theory to practical scenarios. This has been discussed a lot during the rebuttal and among reviewers. Empirical validation has attempted to deal with these concerns, but it would be useful to have this validation coming from theory, or at least have further relevant theoretical insights. This could happen by further building on the theorem provided in the rebuttal for eigenvalue behavior when d is large.
Decision: Reject