Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper studies the training of over-parameterized two layer neural networks with smooth activation functions. In particular, this paper establishes convergence guarantee as well as generalization error bounds under an assumption that the data can be separated by a neural tangent model. The authors also show that the network width requirement in this paper is milder than the existing results for ReLU networks.

In terms of significance, I think this paper is slightly incremental. As is discussed in the paper, results on both convergence and generalization have already been established in earlier works even for deep networks. The major contribution of this paper is probably the weaker requirement of network width, as is shown in Table 1. However, all other results in Table 1 are for ReLU networks, and it has been discussed in Oymak & Soltanolkotabi, 2019 that the over-parameterization condition for smooth activation functions are naturally weaker than that for ReLU networks. Although Oymak & Soltanolkotabi, 2019 did not study generalization, based on their discussion, the result in this paper is not surprising. Moreover, the authors should probably add comparison to Cao & Gu, 2019b in Table 1.

Moreover, the results in this paper is restricted to two-layer networks with fixed second layer weights. This seems to be a much simpler setting than many existing results. The definition of neural tangent kernel in equation (5), as a result, seems to be over simplified, compared to the original definition given in Jacot et al., 2018. The improvement of requirement in network width, which is the major contribution of this paper, might not be very meaningful if it only works for shallow networks.

review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: This paper studied the generalization performance of gradient descent for training over-parameterized two-layer neural networks on classification problems. The authors proved that under a neural tangent based separability assumption, as long as the neural network width is $\Omega(\epsilon^{-1})$, the number of training examples is $\tilde\Omega(\epsilon^{-4})$, within $O(\epsilon^{-2})$ iterations GD can achieve expected $\epsilon$-classification error.

Overall this paper is well written and easy to follow. The theoretical results on the neural network width and iteration complexity are interesting. 

My major concern is that the comparison with Allen-Zhu et al and Cao & Gu seem somewhat unfair. First, Allen-Zhu et al and Cao & Gu both studied the generalization performance of GD for training multi-layer neural networks, which is fundamentally more difficult than two-layer networks. Second, they use ReLU activation functions, which brings in the nonsmoothness along the optimization trajectory. This would also make the condition on the neural network width become worse. Therefore, when claiming the advantage of the derived guarantees, the authors should clearly clarify such differences.

Another concern is that whether the derived theoretical results can be generalized to ReLU network?

When proving the generalization result, this paper takes advantage of margin-based generalization error bound. However, the generalization results in Cao & Gu are proved via applying standard empirical Rademacher complexity based generalization error bound. I would wonder which technique can give a tighter bound?

Can you provide some examples regarding which type of data can satisfy Assumption (A.4) with constant margin $\rho$?

 The authors would like to briefly discuss another data separation assumption adopted in the following papers (although this assumption is typically made for regression problem).

[1] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via overparameterization. arXiv preprint arXiv:1811.03962, 2018b.
[2] Allen-Zhu, Z., Li, Y. and Song, Z. (2018c). On the convergence rate of training recurrent neural networks. arXiv preprint arXiv:1810.12065 .
[3] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv preprint arXiv:1811.08888, 2018.
[4] Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterization: global convergence guarantees for training shallow neural networks. arXiv preprint arXiv:1902.04674, 2019.
[5] Difan Zou and Quanquan Gu. An improved analysis of training over-parameterized deep neural networks. arXiv preprint arXiv:1906.04688, 2019.

review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: The authors study the problem of binary logistic regression in a two-layer network with a smooth activation function.  They introduce a separability assumption on the dataset using the neural tangent model.  This separability assumption is weaker than the more Neural Tangent Kernel assumption that has been extensively studied in the regression literature.  In that case, a certain Gram-matrix must be nonnegative.  In the current work, the authors observe that the structure of the logistic loss in the binary classification problem restricts the functional gradients to lie in a particular space, meaning that nonnegative of the Gram-matrix is only needed on a subspace.  This is the underlying theoretical reason for why they can get improvement over those methods in the setting they study.  Under the separability assumption, the authors prove convergent gradient descent and generalization of the ensuring net, while assuming the two-layer networks are less overparameterized than what would have been possible under the Gram-matrix perspective.  

This paper appears to be a significant contribution to the field of convergent gradient descent algorithms because of the introduction of a weaker condition that guarantees convergence.  While the work only applies to smooth activations and to logistic loss classification problems, it can inspire additional work both in rigorous guarantees for training neural nets in regression and classification.  As a result, I recommend the paper be accepted for ICLR.

Minor comments:

(1) The abstract, title, and introduction emphasize the aspect of being "less overparameterized" than other methods.  It would be helpful to readers to have an absolute claim instead of a relative claim.
(2) The abstract claims the separability assumption is "more reasonable" than the positivity condition.  This claim is overly vague and should be clarified.
(3) There is a stray \forall in the third line of Theorem 2.
review_title: Official Blind Review #3

Meta-review: This article studies gradient optimization for classification problems with shallow networks with smooth activations, obtaining convergence and generalisation results under a separability assumption on the data. The results are obtained under much less stringent requirements on the width of the network than other related recent works. However, with results on convergence and generalisation having been established in other previous works, the reviewers found the contribution incremental. The responses clarified some of the distinctive challenges with the logistic loss compared with the squared loss that has been considered in other works, and provided examples for the separability assumption. Overall, the article makes important contributions in the case of classification problems. However, with many recent works addressing challenging problems in a similar direction, the bar has been set quite high. As pointed out by some of the reviewers, the contribution could gain substantially in relevance and make a more convincing case by addressing extensions to non smooth activations and deep models. 
Decision: Reject