Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper proposes new (data dependent) generalization guarantees based on the Jacobian of the model. The authors suggest that if the desired outputs lie into the information space (the subspace spanned by the largest eigenvectors of the NTK), the model will train faster and better generalization will be achieved.

The faster convergence of the model in the information space is not surprising and was observed by Jacot 2018. The authors make improvements over this result:
 - They present a generalization result, whereas Jacot 2018 focuses only on the convergence on the training set. It is also formulated as a classification problem instead of a regression one.
- It doesn’t need JJ^t to stay constant during the training.

However, the setting considered by the authors to derive their theoretical contributions is too restrictive. The model exposed in section 1 is extremely simplified, as only W can be learned and V is fixed. As a result, the model is in essence completely linear: the goal is, for a given V, to learn a “good” hidden layer using a linear model and the loss L : h -> ||V phi(h) - y ||. 

The experiment on cifar10 is interesting, especially the section regarding label corruption. A more extensive empirical investigation is this direction would be of great value. The results uncovered are not surprising and predicted by Jacot 2018 (granted, it is interesting to see that the result holds for finite width and non-continuous gradient flow).

I think this paper in its current state is not good enough for two reasons. First, the major contribution is a generalization bound that is derived for a model that is too simple (even simpler than a standard one hidden layer network). Beside this result, the rest of the paper is  incremental, as the link between convergence rate and the projection of the desired outputs on the information space was already made in Jacot 2018

NB: I did not check the derivation of the results in annexes.

Nitpick:

Page 2: “our results may shed light on the generalization capabilities of networks initialized with pre-trained models commonly used in meta/transfer learning” seems like a bit of a stretch. While I agree that theories that requires random initialization won’t work for transfer learning, the results presented by the authors don’t really leverage anything particular about pre-training.

review_title: Official Blind Review #4

final_score: rating: 3: Weak Reject
review_content: The authors use the empirically supported assumption of the low-rank nature of the neural network Jacobian to provide new elements of data-dependent optimization and generalization theory. By modelling the data as a low-rank object itself, they analytically study the evolution of the train and test errors. The paper divides the space of weights and biases into the “information” and “nuisance” subspaces, spanned by the top largest and the remaining singular vectors of the Jacobian respectively. They use this division and its alignment with the low-rank structure of the data to talk about convergence speed. Finally, they provide numerical experiments to back their claims.

I enjoyed the paper, however, there were many points where I was unclear on the precise nature of the assumptions used / the strength of the results.

Disclaimer: I didn’t manage to read through the proofs in the appendix and cannot therefore vouch for its correctness.

-- Point 1 --
Leveraging the data structure

I am unclear on how exactly you were modelling the structure of the data. From your proofs, it seems that you have been dealing with the matrix X comprising the concatenated flatted vectors of the raw input features (e.g. pixels) of the input data [x1,x2,...,x_datasetsize]^T. In particular, the only place where I see data explicitly enter is in Definition 2.1, where you look at the X X^T and fi’(w X) fi’(w X)^T.

If the data is linearly separable in the raw input space on its own, then I see that the matrix X X^T will be low-rank (related to the number of classes). I also see your point about the connection of the y to the relevant (semantic) clusters. The same argument could by applied to fi’(w X) fi’(w X)^T -- provided that the features produced are again linearly separable, we will observe this object to have a low (number of classes - 1) rank. 

What is unclear to me is whether these assumptions are warranted. I understand that some simple datasets, e.g. MNIST, are essentially linearly separable in the raw pixels, and therefore the X X^T indeed is low rank. However, I doubt anything like that is true for big datasets, such as ImageNet. For deep networks that are used on these big datasets, such a modelling assumptions would likely not be true. I wonder how this relates to your results, since the low-rank nature of the Hessian is observed even for those networks, which is in turn related to the low rank nature of the Jacobian.

-- Point 2 --
Data implicitly present in the Jacobian tensor.

I wonder how you modelled the Jacobian tensor that you started using on page 3. Since the Jacobian -- the derivative of the output logits with respect to the weights, has to be evaluated at a particular input X, the assumptions you make on the data are in turn having an effect on the Jacobian, and vice versa.

I am unclear on exactly what assumptions you make about the object, and whether you are actually saying that its low rank structure comes from the data, is empirical observed and therefore assumed, or due to the network regardless of the data.

I recently saw a new arXiv submission that seems to be looking into this on real networks: https://arxiv.org/pdf/1910.05929.pdf Their model explicitly assumes that logit gradients cluster in the weight space in a particular way.

-- Point 3 --
Square loss vs softmax

You are using the square loss |f(X) - y|^2 throughout your work. Many of the empirical low-rank observations of the Hessian (related to the JJ^T) are performed on real networks with the cross-entropy loss. While the Hessian with the square loss is of the form JJ^T + terms, the softmax in the cross-entropy loss introduces an additional cross-term (let us call it P for now), which in turn makes it JP(PJ)^T + terms. Do you know how this relates to your results?

More generally, does the square loss you use make the results significantly different from what we would get for a softmax?

-- Point 4 --
Neural Tangent Kernel (NTK) -- assumptions

Under the NTK assumption, you still need to model the derivatives of each logit with respect to each weight on each input in order to obtain the Jacobian matrix and in turn JJ^T. I am therefore very confused by “Based on our simulations the M-NTK indeed haslow-rank structure with a few large eigenvalues and many smaller ones. “ on page 5. What assumptions exactly do you use in your model?

-- Point 5 --
Neural Tangent Kernel (NTK) -- validity

By assuming the NTK holding, do you limit the validity of your results? I think it is believed that NTK might not, generally speaking, be enough to capture the complexity of DNNs, and therefore assuming it might limit the range of applicability of any results derived assuming it.

-- Conclusion --
In general, my points of confusion often stem from being unsure as to what parts of the argument were assumed and based on what empirical / theoretical evidence, and what parts were generically true. While the paper seems interesting, I am not sure what its novel contribution is and how broad the claims made actually are in their applicability.

Appendix: I was not able to judge the proofs in the appendix.

review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: Note: The template used in this paper is of ICLR 2019, not ICLR 2020.

This paper identifies the information space and nuisance space by thresholding the singular values of the network's jacobian and shows that generally the residuals projected to the information space can be effectively optimized to zero, thus leading to efficient optimization and good generalization.

I believe this paper should be rejected because its motivation and technical framework are not novel enough in that 1) the motivation of decomposition along gradient matrix is already well-founded by a series of paper related to neural tangent kernel 2) the techniques used here also fall in a similar framework. The following is the detailed comments.

First, this paper's motivation is to employ the singular decomposition of the jacobian. Actually, the motivation is essentially the same as (Arora et al. 2019) and many other works. The neural tangent kernel matrix defined there is exactly the inner product of two jacobian (or gradient) described here and to employ the singular decomposition is actually corresponding to employing the eigendecomposition of the neural tangent kernel, which appears first in (Arora et al. 2019). The logic behind dividing the singular space into information space and nuisance space is that gradient descending along different directions has different speeds, determined by the eigenvalues.

The framework presented in this paper is based on the assumption that the parameters will not be far away from the starting point. Such an assumption further guarantees the trajectory won't be far away from the linearized trajectory, leading to an optimization guarantee. This approach is widely used by many works, and well-known for a considerably long time. Also, the paper's proof is complicated and lengthy which hinders its clarity.

To summarize, this paper definitely contains some rigorous analysis which I appreciate, but it doesn't provide new insights into optimization and generalization for deep nets. The motivation and logic behind are not novel enough, the main theorem neither. So I suggest a weak rejection to this paper in its current form.

[1] Arora, Sanjeev, et al. "Fine-grained analysis of optimization and generalization for over-parameterized two-layer neural networks." arXiv preprint arXiv:1901.08584 (2019).

****** Post-rebuttal response ******

Thanks to the authors' response. I have read the rebuttal and unfortunately, I feel it is still not strong enough to  justify this paper's novelty issue and I will keep my rating unchanged.
review_title: Official Blind Review #3

Meta-review: This submission investigates the properties of the Jacobian matrix in deep learning setup. Specifically, it splits the spectrum of the matrix into information (large singulars) and ``nuisance (small singulars) spaces. The paper shows that over the information space learning is fast and achieves zero loss. It also shows that generalization relates to how well labels are aligned with the information space.

While the submission certainly has encouraging analysis/results, reviewers find these contributions limited and it is not clear how some of the claims in the paper can be extended to more general settings. For example, while the authors claim that low-rank structure is suggested by theory, the support of this claim is limited to a case study on mixture of Gaussians. In addition, the provided analysis only studies two-layer networks. As elaborated by R4, extending these arguments to more than two layers does not seem straighforward using the tools used in the submission. While all reviewers appreciated author's response, they were not convinced and maintained their original ratings.

Decision: Reject