Venue: ICLR 2018 conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper mainly focuses on the square loss function of linear networks. It provides the sufficient and necessary characterization for the forms of critical points of one-hidden-layer linear networks. Based on this characterization, the authors are able to discuss different types of non-global-optimal critical points and show that every local minimum is a global minimum for one-hidden-layer linear networks. As an extension, the manuscript also characterizes the analytical forms for the critical points of deep linear networks and deep ReLU networks, although only a subset of non-global-optimal critical points are discussed. In general, this manuscript is well written.   

Pros:
1. This manuscript provides the sufficient and necessary characterization of critical points for deep networks. 
2. Compared to previous work, the current analysis for one-hidden-layer linear networks doesn’t require assumptions on parameter dimensions and data matrices. The novel analyses, especially the technique to characterize critical points and the proof of item 2 in Proposition 3, will probably be interesting to the community.
3. It provides an example when a local minimum is not global for a one-hidden-layer neural network with ReLU activation.

Cons:
1. I'm concerned that the contribution of this manuscript is a little incremental. The equivalence of global minima and local minima for linear networks is not surprising based on existing works e.g. Hardt & Ma (2017) and Kawaguchi (2016).  
2. Unlike one-hidden-layer linear networks, the characterizations of critical points for deep linear networks and deep ReLU networks seem to be hard to be interpreted. This manuscript doesn't show that every local minimum of these two types of deep networks is a global minimum, which actually has been shown by existing works like Kawaguchi (2016) with some assumptions. The behaviors of linear networks and practical (deep and nonlinear) networks are very different. Under such circumstance, the results about one-hidden-layer linear networks are less interesting to the deep learning community.

Minors:
There are some mixed-up notations: tilde{A_i} => A_i , and rank(A_2) => rank(A)_2 in Proposition 3.
review_title: An interesting work on the characterization of critical points of neural networks

final_score: rating: 7: Good paper, accept
review_content: This paper studies the critical points of shallow and deep linear networks. The authors give a (necessary and sufficient) characterization of the form of critical points and use this to derive necessary and sufficient conditions for which critical points are global optima. Essentially this paper revisits a classic paper by Baldi and Hornik (1989) and relaxes a few requires assumptions on the matrices. I have not checked the proofs in detail but the general strategy seems sound. While the exposition of the paper can be improved in my view this is a neat and concise result and merits publication in ICLR. The authors also study the analytic form of critical points of a single-hidden layer ReLU network. However, given the form of the necessary and sufficient conditions the usefulness of of these results is less clear.


Detailed comments:

- I think in the title/abstract/intro the use of Neural nets is somewhat misleading as neural nets are typically nonlinear. This paper is mostly about linear networks. While a result has been stated for single-hidden ReLU networks. In my view this particular result is an immediate corollary of the result for linear networks. As I explain further below given the combinatorial form of the result, the usefulness of this particular extension to ReLU network is not very clear. I would suggest rewording title/abstract/intro

- Theorem 1 is neat, well done!

- Page 4 p_i’s in proposition 1
From my understanding the p_i have been introduced in Theorem 1 but given their prominent role in this proposition they merit a separate definition (and ideally in terms of the A_i directly). 

- Theorems 1, prop 1, prop 2, prop 3, Theorem 3, prop 4 and 5
	Are these characterizations computable i.e. given X and Y can one run an algorithm to find all the critical points or at least the parameters used in the characterization p_i, V_i etc?

- Theorems 1, prop 1, prop 2, prop 3, Theorem 3, prop 4 and 5
	Would recommend a better exposition why these theorems are useful. What insights do you gain by knowing these theorems etc. Are less sufficient conditions that is more intuitive or useful. (an insightful sufficient condition in some cases is much more valuable than an unintuitive necessary and sufficient one).

- Page 5 Theorem 2
	Does this theorem have any computational implications? Does it imply that the global optima can be found efficiently, e.g. are saddles strict with a quantifiable bound?

- Page 7 proposition 6 seems like an immediate consequence of Theorem 1 however given the combinatorial nature of the K_{I,J} it is not clear why this theorem is useful. e.g . back to my earlier comment w.r.t. Linear networks given Y and X can you find the parameters of this characterization with a computationally efficient algorithm? 

review_title: This paper studies the critical points of shallow and deep linear networks. The authors give a (necessary and sufficient) characterization of the form of critical points and use this to derive necessary and sufficient conditions for which critical points are global optima. While the exposition of the paper can be improved in my view this is a neat and concise result and merits publication in ICLR.

final_score: rating: 7: Good paper, accept
review_content: Authors of this paper provided full characterization of the analytical forms of the critical points for the square loss function of three types of neural networks: shallow linear networks, deep linear networks and shallow ReLU nonlinear networks. The analytical forms of the critical points have direct implications on the values of the corresponding loss functions, achievement of global minimum, and various landscape properties around these critical points.

The paper is well organized and well written. Authors exploited the analytical forms of the critical points to provide a new proof for characterizing the landscape around the critical points. This technique generalizes existing work under full relaxation of assumptions. In the linear network with one hidden layer, it generalizes the work Baldi & Hornik (1989) with arbitrary network parameter dimensions and any data matrices; In the deep linear networks, it generalizes the result in Kawaguchi (2016) under no assumptions on the network parameters and data matrices. Moreover, it also provides new characterization for shallow ReLU nonlinear networks, which is not discussed in previous work.

The results obtained from the analytical forms of the critical points are interesting, but one problem is that how to obtain the proper solution of equation (3)? In the Example 1, authors gave a concrete example to demonstrate both local minimum and local maximum do exist in the shallow ReLU nonlinear networks by properly choosing these matrices satisfying (12). It will be interesting to see how to choose these matrices for all the studied networks with some concrete examples.
review_title: Authors of this paper provided full characterization of the analytical forms of the critical points for the square loss function of three types of neural networks: shallow linear networks, deep linear networks and shallow ReLU nonlinear networks.

Meta-review: I recommend acceptance based on the positive reviews. The paper analyzes critical points for linear neural networks and shallow ReLU networks. Getting characterization of critical points for shallow ReLU networks is a great first step.
Decision: Accept (Poster)