Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper fits into an important line of work studying implicit bias of neural networks. In order to address the question of what do neural networks learn, the paper develops a "theory of data" -- it identifies a geometric property of data that allows neural networks to provably learn with gradient descent. This property is that the data lies on two disjoint one-dimensional curves -- the label is +1 on one of the curves, and -1 on the other curve. Guarantees on learning are given in terms of the separation Delta of these curves, and their curvature kappa. 

main_review: Overall impression
The result is presented clearly and is easy to follow. As far as I know, the result is new.

The result is based on the framework of the recent paper "DEEP NETWORKS AND THE MULTIPLE MANIFOLD PROBLEM" by Buchanan et al. That paper reduces learning in the neural tangent kernel regime to proving that there is a "certificate" for the data. The certificate problem amounts to finding low-norm approximate solution to a certain linear system involving the neural tangent kernel. 

However, Buchanan et al. paper does not prove the existence of a certificate. This is the main new technical element in this paper: a constructive proof of the certificate problem for a setting with a nonlinear data. The proof uses the fact that as the depth of the network increases the kernel localizes.

I am on the fence about this paper, but recommend acceptance, since I found the results illuminating about the power of deep networks in the NTK regime. Nevertheless, a substantial counterargument against acceptance could be that the learning proved in this paper can just as simply be achieved by classical kernel methods with kernels that are sufficiently local -- instead of deep neural nets.

In any case, this paper opens some interesting future directions:
(A) trying to extend this result to scenarios in which data lies on d-dimensional submanifolds, for d > 1. This would be substantially more convincing, and would match practice more closely. It seems that the current technique to find a certificate has an exponential dependence on the dimension d. What extra assumptions could be placed on the geometric structure of the data in order to avoid such an exponential dependence?
(B) does high depth provably help in the NTK regime? E.g., can the nonlinear data learned in this paper be provably learned with a depth-2 NTK?

Minor comments
— Line 139-140: “In particular, with bounded step size tau < lambda_1”. Why isn’t it tau < 1 / (lambda_1)?

— Lines 149-151: when you introduce the certificate problem, it could be helpful to the reader to refer to the result in https://arxiv.org/pdf/2008.11245.pdf.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the problem of classifying data drawn from two disjoint smooth curves on the unit sphere using a deep fully-connected neural network. The work proves that certificates can exist as long as the network depth is sufficiently large. The main tool used in the paper is NTK and the author claims that this is the first generalization guarantee for deep networks with nonlinear data that depends only on intrinsic data properties.
main_review: Strengths:
1. The paper solves the open problem left by [55], which is the existence of the certificate in multiple manifold problems. The significance and the originality of the paper are fairly high.
2. The paper is generally well-written, with sufficient analysis after each theorem and also figure demonstrations.
3. The proof is highly technical. The idea to localize NTK and then to use harmonic analysis to prove its invertibility may be of independent interest in the theory community.

Weaknesses:
1. The paper can enhance its readability by providing more preliminary introduction on NTK on manifold problems. The current version seems too dense and difficult to follow when I first read it.
2. In both theorem 3.1 and 3.2, the lower bound of depth $L$  is negatively correlated to the clover number. However the clover number is usually very small, so this will make the lower bound of $L$ extremely large?

=================

After reading the rebuttal and other reviewers' comments, I decide to maintain my score.
limitations_and_societal_impact: The paper seems not to address the limitations and potential negative social impact. Personally, I suggest the author to provide some numerical experiments to validate their results, despite considering it is a theoretical paper.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper studies using neural network to classify two disjoint low-dimensional submanifolds. Following the idea from Deep Networks and the Multiple Manifold Problem (Sam Buchanan, Dar Gilboa, and John Wright, 2021), the authors considered the certificate problem and provided some sufficient conditions for the existence of such a certificate.
main_review: The paper studies the classification of two disjoint low-dimensional submanifolds. It closely follows the previous work Deep Networks and the Multiple Manifold Problem (Sam Buchanan, Dar Gilboa, and John Wright, 2021). The authors reduced to consider the certificate problem.

Overall, the paper is not good enough for acceptance. The major contribution lies in Theorem 3.1 and 3.2, which gives some sufficient conditions for the existence of such a certificate. However, the authors didn't provide any comments and discussion on these sufficient conditions. A careful discussion of the dependence of the network depth L on the parameters related to the target manifolds is necessary. In addition, based on the lower bound on the network depth L, the theorem suggests a very strong requirement on the network depth. The authors should consider some simple examples to give a quantitative sense on these parameters of the curves and further the depth L. Some simulations and real data examples are also needed to support the main theorems.

The paper also has some typos. To name a few, line 122, the domain and range of f*; line 166, the range of sigma. Also the paper has some syntax mistakes. The authors need a careful modification.





limitations_and_societal_impact: The paper lacks careful discussion on the dependence of the network depth L from both theoretical and practical perspective. Some toy examples are recommended to illustrate the main idea of the theorems.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper considers the problem of binary classification where the data from the two classes lie on two disjoint nonlinear curves in the unit sphere. They show that given a sufficiently overparameterized deep neural network, gradient descent from a random initialization converges to a classifier which separates the two classes. They show a reduction to the certificate problem in Buchanan et al. and similarly utilize the NTK regime to prove convergence.
main_review: Overall, I find this paper to be an excellent theoretical contribution. It relies heavily on the work by Buchanan et al. but nevertheless, it is a significant contribution. These are some of the first generalization bounds I have seen concerning data which is not necessarily linearly-separable and though they are probably not tight, they are powerful results.

- Originality: The work relies heavily on the paper by Buchanan et al. and resolves some of the open problems asked there while extending their results.

- Clarity: The paper is extremely well written. Despite being an extremely technical result, the main paper provides good intuition and proof sketches relegating the technical details to the appendix.

- Significance: I think this is a good result that takes us in the right direction towards understanding generalization and deep learning but I have some questions:
    1. I see that this result assumes that the gradients are exact i.e, the optimization algorithm is full gradient descent. Does a similar result hold for Stochastic Gradient Descent? In practice, it seems that the randomness is an important element. Perhaps the low-dimensional structure is what helps you avoid local minima?
    2. The result shows that GD eventually reaches a solution that separates the classifier when one uses MSE. However, this would require sufficiently dense sampling (as is mentioned in the paper). Does the analysis provide any insight into whether it would eventually reach a max-margin classififier if one used hinge-loss, say?
    3. This is perhaps an oversight on my part, but I found the usage of the one-dimensional setting very subtle and tricky to identify even in the theorem statements. Is there a significant benefit to assuming the data to lie in a high dimensional space if it comes from a 1-dimensional submanifold?


limitations_and_societal_impact: Yes. Since the results are theoretical, I don't think they need to consider the societal impact.
However, they have addressed their limitations. I would also like them to include a more detailed discussion on "Closing the gap to real networks and data" including some of my questions above, if possible.
review_title: null

Meta-review: This paper analyzes the generalization of deep neural networks for data on curves. There is some disagreement among reviewers. One reviewer raised concerns regarding the clarity and novelty of the presented results and missing supporting experiments. The results are a bit difficult to decipher, and also some polynomial terms are of very high orders, and some critical regularity conditions are insufficiently explained. The paper could be strengthened if these concerns could be addressed.
Decision: Accept (Poster)