Venue: ICLR 2018 conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper studies the theoretical properties of the two-layer neural networks. 

To summarize the result, let's use the theta to denote the layer closer to the label, and W to denote the layer closer to the data. 

The paper shows that 
a) if W is fixed, then with respect to the randomness of the data, with prob. 1, the Jacobian matrix of the model is full rank
b) suppose that we run an algorithm with fresh samples, then with respect to the randomness of the k-th sample, we have that with prob. 1, W_k is full rank, and the Jacobian of the model is full rank. 

It's know (essentially from the proof of Carmon and Soudry) that if the Jacobian of the model is full rank for any matrix W w.r.t the randomness of the data, then all stationary points are global. But the paper cannot establish such a result. 

The paper is not very clear, and after figuring out what it's doing, I don't feel it really provides many new things beyond C-S and Xie et al.

The paper argues that it works for activation beyond relu but result a) is much much weaker than the one with for all quantifier for W. result b) is very sensitive to the exactness of the events (such as W is exactly full rank) --- the events that the paper talks just naturally never happen as long as the density of the random variables doesn't degenerate.  

As the author admitted, the results don't provide any formal guarantees for the convergence to a global minimum. It's also a bit hard for me to find the techniques here provide new ideas that would potentially lead to resolving this question. 

--------------------

additional review after seeing the author's response: 

The author's response pointed out some of the limitation of Soudry and Carmon, and Xie et al's which I agree. However, none of this limitation is addressed by this paper (or addressed in a misleading way to some extent.)  The key technical limitation is the dependency of the local minima on the weight parameters. Soudry and Carmon addresses this in a partial way by using the random dropout, which is a super cool idea. Xie et al couldn't address this globally but show that the Jacobian is well conditioned for a class of weights. The paper here doesn't have either and only shows that for a single fixed weight matrix, the Jacobian is well-conditioned. 

I don't also see the value of extension to other activation function. To some extent this is not consistent with the empirical observation that relu is very important for deep learning. 

Regarding the effect of randomness, since the paper only shows the convergence to a first-order optimal solution, I don't see why randomness is necessary. Gradient descent can converge to a first order optimal solution. (Indeed I have a typo in my previous review regarding "w.r.t. k-th sample", which should be "w.r.t. k-th update". ) Moreover, to justify the effect of the randomness, the paper should have empirical experiments. 

I think the writing of the paper is also misleading in several places. 

review_title: review

final_score: rating: 7: Good paper, accept
review_content: This paper aims to study some of the theoretical properties of the global optima of single-hidden layer neural networks and also the convergence to such a solution. I think there are some interesting arguments made in the paper e.g. Lemmas 4.1, 5.1, 5.2, and 5.3. However, as I started reading beyond intro I increasingly got the sense that this paper is somewhat incomplete e.g. while certain claims are made (abstract/intro) the theoretical justification are rather far from these claims. Of course there is a chance that I might be misunderstanding some things and happy to adjust my score based on the discussions here.

Detailed comments:
1) My main concern is that the abstract and intro claims things that are never proven (or even stated) in the rest of the paper
Example 1 from abstract: 
“We show that for a wide class of differentiable activation functions (this class involved “almost” all functions which are not piecewise linear), we have that first-order optimal solutions satisfy global optimality provided the hidden layer is non-singular.”

This is certainly not proven and in fact not formally stated anywhere in the paper. Closest result to this is Lemma 4.1 however, because the optimal solution is data dependent this lemma can not be used to conclude this. 

Example 2 from intro when comparing with other results on page 2:
The authors essentially state that they have less restrictive assumptions in the form of the network or assumptions on the data (e.g. do not require Gaussianity). However as explained above the final conclusions are also significantly weaker than this prior literature so it’s a bit of apples vs oranges comparison.

2) Page 2 minor typos
We study training problem -->we study the training problem
In the regime training objective--> in the regime the training objective

3) the basic idea argument and derivative calculations in section 3 is identical to section 4 of Soltan...et al

4) Lemma 4.1 is nice, well done! That being said it does not seem easy to make it (1) quantifiable (2) apply to all W. It would also be nice to compare with Soudry et. al.

5) Argument on top of page 6 is incorrect as the global optima is data dependent and hence lemma 4.1 (which is for a fixed matrix) does not apply

6) Section 5 on page 6. Again the stated conclusion here that the iterates do not lead to singular W is much weaker than the claims made early on.
 
7) I haven’t had time yet to verify correctness of Lemmas 5.1, 5.2, and Lemma 5.3 in detail but if this holds is a neat argument to side step invertibility w.r.t. W, Nicely done!

8) What is the difference between Lemma 5.4 and Lemma 6.12 of Soltan...et al 

9) Theorem 5.9. Given that the arguments in this paper do not show asymptotic convergence to a point where gradient vanishes and W is invertible why is the proposed algorithm better than a simple approach in which gradient descent is applied but a small amount of independent Gaussian noise is injected in every iteration over W. By adjusting the noise variance across time one can ensure a result of the kind in Theorem 5.9 (Of course in the absence of a quantifiable version of Lemma 4.1 which can apply to all W that result will also suffer from the same issues).

review_title: This paper aims to study some of the theoretical properties of the global optima of single-hidden layer neural networks and also the convergence to such a solution. I think there are some interesting arguments made in the paper. However, as I started reading beyond intro I increasingly got the sense that this paper is somewhat incomplete e.g. while certain claims are made (abstract/intro) the theoretical justification are rather far from these claims.

final_score: rating: 7: Good paper, accept
review_content: I only got access to the paper after the review deadline; and did not have a chance to read it until now. Hence the lateness and brevity.

The paper tackles an important theoretical question; and it offers results that are complementary to existing results (e.g., Soudry et al). However, the paper does not properly relate their results, assumptions in the context of the existing literature. Much explanation is needed in the author reply in order to clear these questions.

The work should not be evaluated from a practical perspective as it is of a theoretical nature.

I agree with most of the criticism raised by other reviewers. However, I also believe the authors managed to clear essentially of the criticism in they reply. The paper lacks in clarity as currently written. 

The results are interesting, but more explanation is needed for the main message to be conveyed more clearly. I suggest 7, but the paper has a potential to become 8 in my eyes in a future resubmission.

review_title: Good paper - but important clarifications are missing in the text

final_score: rating: null
review_content: What's the order of the quantifier in Corollary 4.2? It seems that the samples are sampled after W is fixed? Then the result doesn't seem to be useful, because the whole point of previous work such as SC, XLS is to prove the uniform result so that W can be chosen after samples are fixed.  
review_title: order of quantifier

Meta-review: Understanding the quality of the solutions found by gradient descent for optimizing deep nets is certainly an important area of research. The reviewers found several intermediate results to be interesting.  At the same time, the reviewers unanimously have pointed out various technical aspects of the paper that are unclear, particularly new contributions relative to recent prior work. As such, at this time, the paper is not ready for ICLR-2018 acceptance.
Decision: Reject