Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: Summary :
1. Classification task with shallow Relu and logistic loss.
2. Showing fast global convergence rate with polylog width for both training and generalization error under appropriate assumptions

Overall, this paper is very exciting and surprising. At some point, I was trying to prove such results, but couldn’t get it. This paper should be accepted as an oral presentation in ICLR. If the authors can address some of the questions in the comments, I will be happy to increase the score.

Advantages:
1. Better results for classification task with shallow Relu in terms of global convergence rate and network width
2. Showing the essence of the power of over-parameterization that the weights don’t change much
3. Clear logic and proof
4. Also discuss the stochastic GD/generalization error? (I didn’t read that part)



Disadvantages:
1.Bug in proving Theorem 2.2, a larger lambda is needed (but won’t influence the polylog result). See the below for a fix.
2.In the proving sketch, why ||W_t-W_0||_F=O(ln t)? In the proof, it looks like ||W_t-W_0||^2_F=O(t), as in the third equation on page 12. More explanation about proof sketch is needed.
3.Typo
a.The \odot operation in Equation 5.1 is not defined. According to later computation, this operation seems to be the hadamard product between two vectors. But this notation is not widely used and some brief introduction will be benefinitial.
b.On page 1, “… and standard Rademacher tools but exploiting how little the….”, “but” seems to be a typo.
c.On page 2, “also suffices via a smoothness-based generalization bound”, “suffices” should be “suffice”.
d.Last formula in page 11 missing a “>0” in the indicator function.
4.(optional) why using ||W_t-W_0||_F instead of ||w_r(t)-w_r(0)||_2, which used in previous work for square loss, for the analysis? Is there any benefit or restriction here? 
5.(optional) Give more insights about intermediate quantities such as \hat R^(t), \bar{W}, etc.

Comments:
1. More arguments for polylog width in last section needed. E.g., give a specific case where the gamma in Assumption 2.1 is constant, or comparable to the smallest eigenvalue of NTK; otherwise in the worst case, gamma can be as bad as  the smallest eigenvalue of NTK over n, which ruins the polylog results. To be more specific, we can always set q to be the uniform distribution over [n], then \|q\odot y\|_2 is indeed 1/\sqrt{n}, hence \gamma_1\leq \sqrt{\lambda_{max}(K_1)/n}. If K_1 has constant spectral norm(which is the case if all the data points are orthogonal to each other), then \gamma_1 will depend on 1/n.
2. For the over-parameterization theory, more references are needed. https://arxiv.org/abs/1902.01028 [Allen-Zhu, Li] is about generalization bound for the over-parametrized networks, https://arxiv.org/abs/1810.12065 [Allen-Zhu, Li, Song] and https://arxiv.org/abs/1905.10337 [Allen-Zhu, Li] are about the over-parameterization bound for more than two-layer networks. https://arxiv.org/abs/1906.03593 [Song, Yang] obtains a better width bound for two-layer neural networks under the framework of https://arxiv.org/abs/1810.02054 [Du, Zhai, Poczos, Singh].
3. Theorem 2.2 shows that the average loss converges. Does this imply after training for T steps, we obtain good weights with small logistic loss? Can you get results showing the loss is decaying, like Theorem 4.1 in https://arxiv.org/abs/1810.02054 [Du, Zhai, Poczos, Singh]?
4. On page 8, the lower bound of \lambda_0 is given as \delta/n^2. Is this bound tight? Is this lower bound achievable? 
5. Under what assumptions can we prove o(log n), say poly(log log n) width?
6. What is the role of logistic loss in the proof? In general, if we replace logistic loss with square loss, will this make it harder to train neural networks?


The original analysis might has some flaw/bug:

In the proof of Theorem 2.2, top of page 12, to show \hat R^{(t)}(\bar W)<= \epsilon/4, the term y_i <\nabla f_i (W_t) - \nabla f_i (W_0) , W_0> seems to be forgotten to consider.

This could be a fix.

Note that above term equals y_i/m \sum_{r=1}^m ( 1_{[< w_{r, t}, x_i> >= 0]} - 1_{[< w_{r, 0}, x_i> >= 0]} ) < w_{r, 0}, x_i >. We can use concentration to bound <w_{r, 0}, x_i>, such that with high probability, it will be no larger than polylog(n). Correspondingly, we know this term won’t be too small. Adding this extra polylog factor into lambda, we can fix the proof.

review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: In this paper, the author shows that for a two-layer ReLU network,  it only requires a network width that is poly-logarithmic in the sample size n to get good optimization and generalization error bounds, which is better than prior results. 

Overall, the paper is well written and easy to follow. However I still have some questions about this paper.

One of my major concerns is that there might be an important error in the proof of the main theorem. Specifically, in the proof of Theorem 2.2 (page 12), it says that due to lemma 2.5, $\hat R^{(t)}(\bar W)\leq \varepsilon$. However, Lemma 2.5 only shows that $|f(x_i,W_0,a)|$ is small, and the reason $\hat R^{(t)}(\bar W)$ can also be small is not explained in this paper at all. Based on Lemma 2.5, I can roughly get that $\hat R^{(0)}(\bar W) $ can be small, but the reason why $\hat R^{(0)}(\bar W) $ is small is unclear to me, especially when the network width m is only polylogarithmic in n and \varepsilon. Without a clear explanation on this issue, the theoretical results in this paper might be flawed, and the polylog claim might not be correct.

Moreover, this paper does not provide sufficient comparison with existing work. For example, Assumption 2.1 looks very similar to the assumption made in Cao & Gu (2019a). The definition of $\hat Q(W)$ has also been introduced in Cao & Gu (2019a). However these similarities are not mentioned in the paper at all. Moreover, the result of Lemma 2.6, which is also one of the selling points of this paper, is actually very similar to Fact D.4 and Claim D.6 in the following paper:
Allen-Zhu, Zeyuan, and Yuanzhi Li. "What Can ResNet Learn Efficiently, Going Beyond Kernels?." arXiv preprint arXiv:1905.10337 (2019).

Finally, the authors’ claim in the title that the width of the network is poly-logarithmic with the sample size n might be misleading. In fact, in Section 5, it has been discussed that in certain settings about the data distribution, $\frac 1\gamma$ is polynomial of n. However, the width is polynomial with $\frac 1\gamma$, which means the width is poly of n in these settings. 
review_title: Official Blind Review #3

final_score: rating: 8: Accept
review_content: Summary and Decision 

The authors of this paper studied the optimization and generalization properties of shallow ReLU networks. In particular, the authors were able to show a width dependence that is polylogarithmic on the number of samples, probability or failure, error tolerance, and a margin parameter. This work is unique in that the authors showed how to bound many key quantities in terms of the margin parameter, and drew a connection with the neural tangent kernel's maximum margin. Furthermore, the overall reading experience was very smooth, although I do have some minor comments later. 

The main concern from me is on the implicit dependence of the margin parameter \gamma, most notably this can lead to the width dependence to be polynomial in terms of the number of samples and the minimum separation distance. While this concern warrants a careful discussion (below), I believe the paper still offers a nice analysis of shallow networks. 

Overall, I would recommend accept for this paper. 


Background 

There has been a large number of works studying very wide networks, showing both optimization and generalization results. While there has been great progress, most of these existing results require the width of both deep (and shallow) networks to be very large. For example, even by being polynomial in the number of samples, the networks are already unrealizable in practice. Therefore, guarantees with much better dependence is highly desirable. 


Discussion of Contributions

As the title may suggest, it is a bit surprising that we can show that polylog width is sufficient. Intuitively, we can imagine that the classification margin can grow exponentially more complex as the number of samples increase. I believe the nice result can be attributed to a careful analysis of key quantities such as \| W_t - W_0 \|_F in terms of the margin parameter from Assumption 2.1. 

Some nice examples of the analysis in this paper include the introduction of the weight matrix \overline{U} and \overline{W} as an intermediate between W_0 and W_t, and observing that the activations of the ReLU \xi_{i,t} do not change very much during training. The tricks together led to a very tight bound on the change in weights \| W_t - W_0 \|_F in terms of the margin parameter \gamma. As the authors mentioned on page 6, this tight control was used to bound the Rademacher complexity later. 

The connection drawn between the margin assumption and neural tangent kernel (Proposition 5.1) is also interesting on its own. The authors intended this result to serve as a justification of the margin assumption (2.1). 


Discussion of the Margin Parameter

Let me start by saying I'm not completely certain on how to interpret this margin parameter \gamma in Assumption 2.1. Perhaps I'm missing some obvious ideas here, but I would still like the authors respond with some more details. At the same time, I don't believe this is a sufficient criticism to reject this paper, as I believe the analysis in terms of \gamma is still valuable. 

On one hand, if we were to assume the margin condition holds for all possible data points (i.e. Assumption 3.1), then there is no concern about polynomial dependence on the number of samples, and this is certainly a reasonable assumption in some applications. 

On the other hand, many of the previous analysis on wide networks were in terms of a minimum separation distance, i.e. assume there exists a \delta > 0 such that for all i \neq j, we have 
	\| x_i - x_j \| \geq \delta . 
The authors have provided a discussion in section 5, including both a worst case bound of 
	\gamma \geq \delta / (100 n^2),
by Oymak and Soltanokotabi (2019) and an example where the margin is O( n^{-1/2} ) with high probability. 

Using either bounds on \gamma, we will have a width with polynomial dependence in terms of the number of samples and minimum separation distance. Therefore if we were to compare against previous works in the same benchmark, i.e. using a minimum separation assumption instead, then arguably this work did not achieve a width that is only polylog in terms of the number of samples. 

That being said, I don't believe the authors were intentionally trying to hide sample dependence inside an assumption. The paper is presented in a very transparent way, and the authors were being honest in chapter 5 about the worst case dependence on the number of samples. 

To summarize, it is unclear to me whether the paper truly achieved a width dependence that is polylog in terms of the number of samples, but the analysis in terms of \gamma remains a valuable contribution. I welcome the authors and the other reviewers to provide additional comments on whether the title and claims of this paper is appropriate. 


Minor Comments 

For the sake of improving readability, I also have some minor comments that do not contribute towards the decision. 

 - On page 5, the first observation bullet point in section 2.2, it is written here that by triangle inequality 
     \| \nabla \widehat{R}(W) \|_F \leq \widehat{Q}(W) , 
    I thought you needed an absolute value on the right hand side, perhaps you should mention that \ell is strictly decreasing. 

 - On page 6, in the statement of Corollary 3.3, you are missing \eta \leq 1, and perhaps the \tilde on \Omega and O should be defined. 
 - On the same note, while it is obvious that Theorem 3.2 implies this corollary, it is still worth writing up a proof to compute the constants. 

 - On page 7, the notation \Delta_n and \odot are not defined, I had to infer definition from the proof. 

 - On page 12, just below the second equation, it wasn't immediately clear how \widehat{R}( \overline{W} ) \leq \epsilon / 4. I believe it's worth expanding the definitions a bit, and explicitly plug in Lemma 2.5. 

 - On page 12, in the second last equation, I'm actually not sure where this inequality comes from 
      \| W_t - \overline{W} \|_F \geq \langle W_t - \overline {W} , \overline{U} \rangle
    Perhaps it's obvious, but I currently don't see it. 

review_title: Official Blind Review #1

Meta-review: This paper studies how much overparameterization is required to achieve zero training error via gradient descent in one hidden layer neural nets. In particular the paper studies the effect of margin in data on the required amount of overparameterization. While the paper does not improve in the worse case in the presence of margin the paper shows that sometimes even logarithmic width is sufficient. The reviewers all seem to agree that this is a nice paper but had a few mostly technical concerns. These concerns were sufficiently addressed in the response. Based on my own reading I also find the paper to be interesting, well written with clever proofs. So I recommend acceptance. I would like to make a suggestion that the authors do clarify in the abstract intro that this improvement can not be achieved in the worst case as a shallow reading of the manuscript may cause some confusion (that logarithmic width suffices in general).
Decision: Accept (Poster)