Venue: ICLR 2018 conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This is a theory paper. The authors consider networks with single hidden layer. They assume gaussian input and binary labels. Compared to some of the existing literature, they study a more realistic model that allows for mild overparametrization and approximately speaking d_0=d_1=sqrt(N). The main result is that volume of suboptimal local minima exponentially decreases in comparison to global minima.

In my opinion, paper has multiple drawbacks.
1) Lack of surprise factor: There are already multiple papers essentially saying similar things. I am not sure if this contributes substantially on top of existing literature.
2) Lack of algorithmic results: While the volume of suboptimal DLM being small is an interesting result, it doesn't provide substantial algorithmic insight. Recent literature contains results that states not only all locals are global but also gradient descent provably converges to the global with a good rate. See Soltanolkotabi et al.
3) Mean squared error for classification problem (discrete labels) does not sound reasonable to me. I believe there are already some zero error results for continuous labels. Logistic loss would have made a more compelling story.

Minor comments:
i) Results are limited to single hidden layer whereas the title states multilayer. While single hidden layer is multilayer, stating single hidden layer upfront might be more informative for the reader.
ii) Theorem 10 and Theorem 6 essentially has the same bound on the right hand side but Theorem 10 additionally divides local volume by global which decreases by exp(-2Nlog N). So it appears to me that Thm 10 is missing an additional exp(2Nlog N) factor on the right hand side.

Revision (response to authors): I appreciate the authors' response and clarification. I do agree that my comparison to Soltanolkotabi missed the fact that his result only applies to quadratic activations for global convergence (also many thanks to Jason for clarification). Additionally, this paper appeared earlier on arXiv. In this sense, this paper has novel technical contribution compared to prior literature. On the other hand, I still think the main message is mostly covered by existing works. I do agree that squared-loss can be used for classification but it makes the setup less realistic. Finally, while introduction discusses the "last two layers", I don't see a technical result proving that the results extends to the last two layers of a deeper network. At least one of the assumptions require Gaussian data and the input to the last two layers will not be Gaussian even if all previous layers are fixed. Consequently, the "multilayer" title is somewhat misleading.
review_title: Not very surprising. Marginal insight on top of prior literature.

final_score: rating: 6: Marginally above acceptance threshold
review_content: ## Summary
This paper aims to tackle the question: "why does standard SGD based algorithms on neural network converge to 'good' solutions?" 

Pros: 
Authors ask the question of convergence of optimization (ignoring generalization error): how "likely" is that an over-parameterized (d1d0 > N) single hidden layer binary classifier "find" a good (possibly over-fitted) local minimum. They make a set of assumptions (A1-A3) which are weaker (d1 > N^{1/2}) than the ones used earlier works. Previous works needed a wide hidden layer (d1 > N).

Assumptions (d0=input dim, d1=hidden dim, N=n of datapoints, X=datapoints matrix):
A1. Datapoints X come from a Gaussian distribution 
A2. N^{1/2} < d0 =< N
A3. N polylog(N) < d0d1 (approximate n of. parameters)  and d1 =< N

This paper proves that total "angular volume" of "regions" (defined with respect to the piecewise linear regions of neuron activations) with differentiable bad-local minima are exponentially small when compared with to the total "angular volume" of "regions" containing only differentiable global-minimal. The proof boils down to counting arguments and concentration inequality.

Cons: 
Non-differentiable stationary points are left as a challenging future work on this paper. Non-differentiability aside, authors show a possible way by which shallow neural networks might be over-fitting the data. But this is only half the story and does not completely answer the question. First, exponentially vanishing (in N) volume of the "regions" containing bad-local minima doesn't mean that the number of bad local minima are exponentially small when compared to number global minima. 
Secondly, as the authors aptly pointed out in the discussion section, this results doesn't mean neural networks will converge to good local minima because these bad local minimas can have a large basins of attraction.
Lastly, appropriate comparisons with the existing literature is lacking. It is hinted that this paper is more general as the assumptions are more realistic. However, it comes at a cost of losing sharpness in the theoretical results. It is not well motivated why one should study the angular volume of the global and local minima. 

## Questions and comments
1. How critical is Gaussian-datapoints assumption (A1)? Which part of the proof fails to generalize?  
2. Can the proof be extended to scalar regression?  It seems hard to generalize to vector output neural networks. What about deep neural networks? 
3. Can you relate the results to other more recent works like: https://arxiv.org/pdf/1707.04926.pdf.
4. Piecewise linear and positively homogeneous (https://arxiv.org/pdf/1506.07540.pdf) activation seem to be important assumption of the paper. It should probably be mentioned explicitly.
5. In the experiments section, it is mentioned that "...inputs to the hidden neurons converge to a distinctly non-zero value. This indicates we converged to DLMs." How can you guarantee that it is a local minimum and not a saddle point?

review_title: Assumptions are more realistic, but the main results are less motivated.

final_score: rating: 7: Good paper, accept
review_content: This paper studies the question: Why does SGD on deep network is often successful, despite the fact that the objective induces bad local minima?
The approach in this paper is to study a standard MNN with one hidden layer. They show that in an overparametrized regime, where the number of parameters is logarithmically larger than the number of parameters in the input, the ratio between the number of (bad) local minima to the number of global minima decays exponentially. They show this for a piecewise linear activation function, and input drawn from a standard Normal distribution. Their improvement over previous work is that the required overparameterization is fairly moderate, and that the network that they considered is similar to ones used in practice. 

This result seems interesting, although it is clearly not sufficient to explain even the success on the setting studied in this paper, since the number of minima of a certain type does not correspond to the probability of the SGD ending in one: to estimate the latter, the size of each basin of attraction should be taken into account. The authors are aware of this point and mention it as a disadvantage. However, since this question in general is a difficult one, any progress might be considered interesting. Hopefully, in future work it would be possible to also bound the probability of starting in one of the basins of attraction of bad local minima.

The paper is well written and well presented, and the limitations of the approach, as well as its advantages over previous work, are clearly explained. As I am not an expert on the previous works in this field, my judgment relies mostly on this work and its representation of previous work. I did not verify the proofs in the appendix. 

review_title: Interesting result despite clear limitations

Meta-review: The paper analyzes neural network with hidden layer of piecewise linear units, a single output, and a quadratic loss. The reviewers find the results incremental and not "surprising", and also complained about comparison with previous work. I think the topic is very pertinent, and definitely more relevant compared to studying multi-layer linear networks. Hence, I recommend the paper be presented in the workshop track.
Decision: Invite to Workshop Track