Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper studies the landscape properties of over-parameterized two-layer neural networks, and proposes a network width lower bound for guaranteed existence of descent paths that is tighter than existing results. In particular, the authors prove that if the network width m \leq n - 2d, then there exist training data sets and initial weights such that the square loss on the neural network has no descent path connecting the initial weights and global minima.

Overall, I think this paper is of good quality. The presentation is clear and the logic is easy to follow. I did some high-level check and the theoretical analysis seems reasonable. However, I have the following questions:

1. As is stated in Corollary 1 and discussed below Theorem 1, the training sample sets that lead to suboptimal capped minima are not of measure-zero. However, it seems that no rigorous proof is provided for this result. Perhaps I have missed something, but is Corollary 1 straight forward given Theorem 1 and Lemma 1? How large is the probability? It would be better if the authors could provide a more rigorous proof.

2. A recent line of work has shown convergence of gradient-based algorithms for over-parameterized neural networks. It would be interesting if the authors could provide more comparison between this paper and the results of these works:

- Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, Xiyu Zhai, Gradient Descent Finds Global Minima of Deep Neural Networks
- Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song, A Convergence Theory for Deep Learning via Over-Parameterization
- Difan Zou, Yuan Cao, Dongruo Zhou, Quanquan Gu, Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks

review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: This paper analyzes the existence of descent paths from any initial point to the global minimum for the two-layer ReLU network and gives a better characterization of the network width that guarantees the descent path property. Concretely, the paper shows that there exists poor local minima under the case of $n > m+2d-2$ by constructing concrete examples of datasets.

To show the global convergence property of the optimization method, this kind of landscape analysis is very important. Basically, I like this paper and I think it makes a certain contribution to this line of researches. However, I did not verify the proof.

A few questions:
- I am not sure why the authors say that "it was not known whether the descent path property holds for $m \in (2n/d, n)$" by citing [Soudry and Hoffer(2017)]. I think [Soudry and Hoffer(2017)] does not mention the descent path property. Is this my misunderstanding?
- The theory is limited to 2-layer ReLU. Can it be extended to deep networks?
- The datasets producing poor local minima seem quite artificial. Does this theory hold for a more natural setting (e.g., assume a true distribution or function having preferable properties)?

Typos:
- In abstruct: exit -> exist
- Section 1.2: $m < n - 2d$ -> $m < n - 2d + 2$.
- After Corollary 1: Note that 1 does not ... -> Note that Corollary 1 does not 

-----
Update:
I thank the authors for the response. My concerns have been well addressed and my review stands. I would like to keep the score.
review_title: Official Blind Review #1

Meta-review: This article investigates the optimization landscape of shallow ReLU networks, showing that for sufficiently narrow networks there are data sets for which there is no descent paths to the global minimiser. The topic and the nature of the results is very interesting. The reviewers found that this article makes important contributions in a relevant line of investigation and had generally positive ratings. The authors' responses addressed questions from the initial reviews, and the discussion helped identifying questions for future study departing from the present contribution.  
Decision: Accept (Poster)