With the increasing interest in deeper understanding of the loss surface of many non-convex deep models, this paper presents a unifying framework to study the local/global optima equivalence of the optimization problems arising from training of such non-convex models. Using the local openness property of the underlying training models, we provide simple sufficient conditions under which any local optimum of the resulting optimization problem is globally optimal. We first completely characterize the local openness of matrix multiplication mapping in its range. Then we use our characterization to: 1) show that every local optimum of two layer linear networks is globally optimal. Unlike many existing results in the literature, our result requires no assumption on the target data matrix Y , and input data matrix X. 2) develop almost complete characterization of the local/global optima equivalence of multi-layer linear neural networks. We provide various counterexamples to show the necessity of each of our assumptions. 3) show global/local optima equivalence of non-linear deep models having certain pyramidal structure. Unlike some existing works, our result requires no assumption on the differentiability of the activation functions and can go beyond "full-rank" cases.
Summary: The paper focuses on the characterization of the landscape of deep neural networks; i.e., when and why local minima are global, what are the conditions for saddle critical points, etc. The paper covers a somewhat wide range of deep nets (from shallow with linear activation to deeper with non-linear activation); it focuces only on feed forward neural networks.
As the authors state, this paper provides a unifying perspective to the subject (it justifies the results of others through this unifying theory, but also provides new results; e.g., there are results that do not depend on assumptions on the target data matrix Y).
Originality: The paper provides similar results to previous work, while removing some of the assumptions made in previous work. In that sense, the originality of the results is weak, but definitely there is some novelty in the methodology used to get to these results. Thus, I would say original.
Importance: The paper deals with the important problem of when and why training algorithms might get to global/local/saddle critical points. While there are no direct connections with generalization properties, characterizing the landscape of neural networks is an important topic to make further steps into better understanding of deep learning. It will attract some attention at the conference.
Clarity: The paper is well-written - some parts need improvement, but overall I'm satisfied with the current version.
Comments:
1. If problem (4) is not considered at all in this paper (in its full generality that considers matrix completion and matrix sensing as special cases), then the authors could just start with the model in (5).
2. Remark 1 has a nice example - could this example be shown with Y not being the all-zeros vector?
3. In section 5, the authors make a connection with the work of Ge et al. 2016. They state that the problems in (10)-(11) constitute generalizations of the symmetric matrix completion case, considered in Ge et al. 2016. However, in that work, the main difficulty of proving global optimality comes from the randomness of the sampling mask operator (which introduces the notion of incoherence and requires results in expectation). It is not clear, and maybe it is an overstatement, that the results in section 5 generalize that work. If that is the case, could the authors describe this a bit further?