Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: The paper under review studies the question of whether gradient descent can solve the problem of calibrating a deep neural network for separating two submanifolds of the sphere. The problem studied in the paper is very interesting and as been the subject of recent increasing interest in the machine learning community. The contribution is restricted to a simple set up and addresses the question in the finite sample regime. The framework of the analysis hinges on the Neural Tangent Kernel approximation of Jacot et al. 

This extremely technical paper is indimidating and I wonder how many readers will actually read the proofs. Moreover, one may wonder if the NTK approach precludes a deeper understanding of the actual performance of the network under consideration.  

 
review_title: Review of "Deep Networks and the Multiple Manifold Problem"

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper analyzes deep networks in terms of multiple manifold problems. However, it needs easier explanations for a wider audience.  Moreover, I think the article was written as a book rather than a conference paper, considering 245 pages. 

What would be the actual benefits of the analysis? 

The paper talks about one-dimensional cases, and I was wondering if the multiple manifold problem in one-dimension is enough. If I understand correctly, this one-dimension manifold is supposed to represent one class in the last layer. 

Some notations are hard to follow, especially in Section 3.1. Actually, some of them are used without the description.)
review_title: hard to follow and too long

final_score: rating: 7: Good paper, accept
review_content: The paper studies the conditions for a deep fully-connected network to separate low-dimensional data classes. A binary classification setting is considered, where the two classes are modelled as two different manifolds. The manifolds are assumed to be one-dimensional for the ease of analysis. It is shown that the network depth should be sufficiently large so as to adapt to the geometrical properties of data (e.g. the manifold curvature); the network width should increase polynomially with the network depth; and the number of data samples should also scale at a polynomial rate with the network depth. The authors show that if these conditions are met, with high probability a randomly initialized network converges to a classifier that separates the two class manifolds. The proof technique relies on conditioning the network parameters of the l-th layer on the parameters of the previous layers using a Martingale model, which gives sharp concentration guarantees. 

The paper is rigorous and well-written, and very detailed proofs have been provided for the presented results. The authors may still find it useful to address the following issues:

1. The separation Delta between the two manifolds seems to be a critical parameter in the proposed performance bounds. However, the definition of Delta in Section 3.1 is not very clear. In particular, what does the notation \angle(x, x') mean? Does this mean Euclidean distance, or angle as the notation suggests? If this means an angle, please explain whether this refers to the angle of points on the sphere, or the angle measured on the tangent space of the Riemannian manifold, etc.

2. Although I like very much the analysis proposed by the authors, some of the main assumptions regarding the studied setting may be too restrictive in practice: 

a. The proposed bounds apply only when the separation parameter Delta is positive. In a practical application, the manifolds representing different classes may be (asymptotically) intersecting due to the degeneracy of image transformations/articulations in some manifold regions - e.g. extreme illumination conditions, scale changes, etc.

b. The assumption that the data samples lie exactly on a Riemannian manifold also seems to be restrictive. A probabilistic model for the data samples, e.g. involving a noise model capturing the deviations of the points from the manifold, would have been more realistic. Would the theoretical analysis be completely intractable under such extensions, or could that be a potential future direction of the study? 

It would be nice if the authors could comment on such issues. 
review_title: Rigorous and well-written paper

final_score: rating: 6: Marginally above acceptance threshold
review_content: The authors consider a binary classification task. As a model the authors use a deep fully-connected neural network and train it to separate the submanifolds, representing different classes. They assume that sub-manifolds belong to the unit sphere. Also, the authors restrict their analysis to a one-dimensional case. The main claim is that by increasing depth we can improve model generalization of a network, trained by SGD.

The proved result seems to be imporant for understanding the generalization ability of deep neural networks. While proving it the authors used various imporant tools from martingale concentration approach.

However, the paper is not well suited for such venue as ICLR. Moreover, I am sure that the proof itself contains some parts that are of separate interest for the community. I would propose to divide the paper into several parts, so that some of them contain general results about approaches to prove concentration inequalities, which are of general interest and can be used somewhere else. Also, I would expect more comments on which tools, used for proving the main results, are completely new and how they can be used to establish similar results for other network architectures. 
Also, I would expect some comments how in principle the restriction that the submanifolds belong to the unit sphere can be removed. Some more discussion how the proposed setup is related to the setup, considered in the paper of Goldt (2019), are needed.

========

After reading authors comments.

In principle, I tried to understand the main steps of the proof, they looks OK. Although, I can not verify the details of the proof.
I still think that ICLR venue is not OK for such long submissions. 
In principle, I am OK to increase the grade for one point.
review_title: Important result, difficult to verify the proof, possibly ICLR is not a proper venue

Meta-review: This paper introduces the multiple manifold problem - in a simple setting there are two data manifolds representing the positive and negative samples, and the goal is to train a neural network (or any predictor) that separates these two manifolds. The paper showed that this is possible to do with a deep neural network under certain assumptions - notably on the shape of the manifold and also on the ability of the neural network to represent certain functions (which is harder to verify, and only verified for a 1-d case in the paper). The optimization of neural network falls in the NTK regime but requires new techniques. Overall the question seems very natural and the results are reasonable first steps. There are some concerns about clarity that the authors should address in the paper.
Decision: Accept (Poster)