We study the landscape of squared loss in neural networks with one-hidden layer and ReLU activation functions. Let m and d be the widths of hidden and input layers, respectively. We show that there exist poor local minima with positive curvature for some training sets of size n ≥ m + 2d − 2. By positive curvature of a local minimum, we mean that within a small neighborhood the loss function is strictly increasing in all directions. Consequently, for such training sets, there are initialization of weights from which there is no descent path to global optima. It is known that for n ≤ m, there always exist descent paths to global optima from all initial weights. In this perspective, our results provide a somewhat sharp characterization of the over-parameterization required for "existence of descent paths" in the loss landscape.
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