Deep Learning without Poor Local Minima
In this paper, we prove a conjecture published in 1989 and also partially address an open problem announced at the Conference on Learning Theory (COLT) 2015.
With no unrealistic assumption, we first prove the following statements for the squared loss function of deep linear neural networks with any depth and any widths: 1) the function is non-convex and non-concave, 2) every local minimum is a global minimum, 3) every critical point that is not a global minimum is a saddle point, and 4) there exist "bad" saddle points (where the Hessian has no negative eigenvalue) for the deeper networks (with more than three layers), whereas there is no bad saddle point for the shallow networks (with three layers). Moreover, for deep nonlinear neural networks, we prove the same four statements via a reduction to a deep linear model under the independence assumption adopted from recent work. As a result, we present an instance, for which we can answer the following question: how difficult is it to directly train a deep model in theory? It is more difficult than the classical machine learning models (because of the non-convexity), but not too difficult (because of the nonexistence of poor local minima). Furthermore, the mathematically proven existence of bad saddle points for deeper models would suggest a possible open problem. We note that even though we have advanced the theoretical foundations of deep learning and non-convex optimization, there is still a gap between theory and practice.
The paper proves two theorems: one unconditional result about the loss landscape of deep linear networks (a chain of matrices) and one assumption-based calculation for deep relu networks.  Both answer questions raised in previous work: the first is a strengthening of a conjecture and the second uses fewer assumptions than a previous result.  The results provide excellent intuition towards the robustness of neural network optimization.  Although the proofs are a fairly technical calculation, the theorems themselves are extremely intuitive.  The paper is likely to benefit researchers trying to understand why simple algorithms (SGD) suffices for technically NP-hard optimization problems, and may lead to further strengthenings or similar results. 
 The paper makes a significant dent in the central mystery of deep learning: why are neural networks so easy to optimize?  The precision of the linear result is quite impressive!  The nonlinear result still makes a implausible assumption, but is stronger than previous work and the implausibility is carefully discussed.  The paper itself was a delight to read, though I will admit that the full proofs were a bit of a slog.  My main question is whether the proofs could be simplified.  Two approaches come to mind: use random perturbation tricks to avoid some of the length devoted to singularity, and constructing a monotonic descent path from any point to the global minimum.  Here's a sketch of how to construct a descent path.  First, I claim that the global minimum is    min_{rank W = p} 1/2 || Y - W X ||^2  This is clearly at least as good as the global minimum, and can be achieved by decomposing the above optimal W as     W = U D V' = Ue 1 ... 1 De 1 ... 1 Ve' = W_{H+1} ... W_1  where U D V' is the SVD of W, Ue/De/Ve are zero extended versions of U/D/V, and the 1's are rectangular extended identity matrices.  Now consider an arbitrary point W = W_{H+1} ... W_1, and decompose each factor via SVD.  Given a matrix decomposition D U V (resp. U V D) for diagonal D and orthogonal U/V, there is a smooth path to a decomposition of the form D 1 V (resp. U 1 D) that does not change the value of the product.  Similarly, D U E for diagonal D/E can be transformed into the form 1 U E without changing the product.  Using a series of these transforms chained together (which will be continuous if not smooth), we can find a path ending in the form    Ue 1 ... 1 De 1 ... 1 Ve'  A final path changing Ue/De/Ve' can be constructed to reach the global minimum, where the loss decreases monotonically.  Note that the path can also be made to increase after staying constant.  If correct, this is a much simpler proof of 2.3(i) and (ii).  The above shows that every point W can be monotonically decreased to a global minimum.  However, I believe the above proof can be extended to show that every nonglobal minimum is a saddle point, essentially by rearranging the path construction to change singular values immediately.  This would prove 2.3(iii).  I am not sure if there is a similarly easy proof of 2.3(iv).  Additional comments:  1. Does Theorem 2.3 need a size > 0 condition to ensure (i)?  2. "scaler" to "scalar" in the proof of Lemma 4.6.  3. It's good that A.7 avoids discussing the other direction, since it is false. For example, if $A = 0 \kronecker 0$ then all matrices are $A^-$, but only some matrices are Kronecker products.