Depth creates no more spurious local minima in linear networks
Authors: Li Zhang
Venue:  (2020)
Keywords: local minimum
deep linear network

Abstract: We show that for any convex differentiable loss,  a deep linear network has no spurious local minima as long as it is true for the two layer case.  This reduction greatly simplifies the study on the existence of spurious local minima in deep linear networks. When applied to the quadratic loss, our result immediately implies the powerful result by Kawaguchi (2016). Further, with the recent work by Zhou& Liang (2018), we can remove all the assumptions in (Kawaguchi, 2016).  This property  holds  for  more  general  “multi-tower”  linear  networks  too.  Our  proof builds on the work in (Laurent & von Brecht, 2018) and develops a new perturbation argument to show that any spurious local minimum must have full rank, a structural property which can be useful more generally

Under review as a conference paper at ICLR 2020
DEPTH CREATES NO MORE SPURIOUS LOCAL MINIMA IN LINEAR NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We show that for any convex differentiable loss, deep linear network has no spurious local minima as long it is true for the two layer case. This reduction greatly simplifies the study on the existence spurious local minima in deep lin- ear networks. When applied to the quadratic loss, our result immediately implies the powerful result by Kawaguchi (2016). Further, with the recent work by Zhou & Liang (2018), we can remove all the assumptions in (Kawaguchi, 2016). This property holds for more general "multi-tower" linear networks too. Our proof builds the work in (Laurent & von Brecht, 2018) and develops bation argument to show that any spurious local minimum must have full rank, a structural property which can be useful more generally.
pertur-
INTRODUCTION
One major mystery in deep learning is that deep neural networks do not seem suffer from spurious local minima. Understanding this mystery has become one of the most important topics in the machine learning theory. This problem turns be quite challenging. Even for the subcase of the deep linear network, much still remains unknown despite long line of studies on this subject.
In this paper, we prove useful structural property about the deep linear networks. We show that for any convex differentiable loss function, any spurious local minima in a deep linear network should already present in a two layer linear network. Hence, depth does not create more spurious local minima in linear networks. This reduction greatly simplifies the study about the existence of spurious local minima in deep linear networks. When applied to the quadratic loss, leads to the first unconditional proof that there is no local minima in deep linear networks.
Baldi Hornik (1989) started the investigation on the existence of spurious local minima in linear networks. They showed that, under mild assumptions, for quadratic loss, two layer linear networks do not have spurious local minima. They also conjectured it is true for deep linear networks. This conjecture is only proved recently by Kawaguchi (2016). For the special case of linear residual networks, Hardt & Ma (2017) showed that there are no spurious local minima through a simpler argument.
While most existing work have been on quadratic loss functions, Laurent & von Brecht (2018) showed a surprisingly general result for any convex differentiable loss. In (Laurent & Brecht, 2018), the authors consider the special linear networks which have no bottlenecks, i.e. when the narrowest layer is on the either end. They showed that for any convex differential loss function, there is no spurious local minima in such networks. In addition to its generality, the proof in (Laurent & von Brecht, 2018) is quite intuitive through novel perturbation argument. However, their special cases excludes networks with bottleneck layers, commonly used in the practice and studied in the literature (Baldi & Hornik, 1989; Kawaguchi. 2016).
We build on the work in (Laurent & von Brecht, 2018) and further develop the technique to show that for general deep linear networks, whether there are spurious local minima is reduced to the two layer case.
Theorem 1. Given any convex differentiable function f : Mx + R. For any l 2 2, let [M M&) fMM.... Md) where M. E dd for 1 < k with dy and B pdxn Then L
dn = n. Let minogisk d.. Define Lz(A, = (AB) for A E Rm has spurious local minima iff L has no spurious local minima.

---

Under review as a conference paper at ICLR 2020
We emphasize that in the above theorem, f depends on both the data and the loss function. Hence the reduction is instance specific and does not depend on the global property of a family of loss functions.
To prove Theorem I, we show a non-degeneracy property of local minima, namely, any spurious local minimum must have rank same the width of the bottleneck. This property can be useful for the two layer case too - it implies that each layer in a spurious local minimum cannot be rank- deficient, hence covering subcases which may otherwise require onerous analysis (Baldi & Homnik, 1989; Zhou & Liang, 2018).
Theorem 2. With the same notation as in Theorem 1, if A, B a spurious local minimum of Log, then both A, B must have full rank.
As an application of Theorem I, for quadratic loss, Theorem 1, together with (Baldi & Hornik, 1989), immediately implies the main result in (Kawaguchi, 2016). We can further remove all the assumptions needed in (Baldi & Hornik, 1989; Kawaguchi, 2016), using the recent result by Zhou & Liang (2018) (Theorem 2(1)), hence providing the first unconditional proof of the non-existence of spurious local minima in deep linear networks for quadratic loss functions. Below || || denotes the Frobenius norm.
Corollary 1. For any X E Io "oeix" E Rdexn, let L(M Ms) = M| ... M, - YlI.. Then L has no spurious local minima.
Theorem 1 can be further generalized to "multi-tower linear networks. Define a multi- lin- ear network as the sum of multiple deep linear networks (towers), i.e. MIk ... M11 + ... Msk, ... Ma where Mij E RRd., with di,,; m and d: = n. For 1 S i S 8, let b, = min, ds.j denote the bottleneck size each tower i. Write b = Σ,
Corollary 2. For any differentiable convex loss f. multi-tower linear network has spurious local minima iff the linear network AB, where A E Remxb B E Rexx,, has no spurious local minima. Moreover, b 2 m, n, there is no spurious local minima in this network.
There are two main technical ideas in our proof. First, we show a reduction of any local minimum of the multi-layer network to a critical point of two-layer network. Secondly, we generalize the local perturbation argument in (Laurent & von Brecht, 2018) to weaker critical conditions. Besides the conceptual importance of our results, these technical contributions might be useful for understanding deep networks too.
1.1 RELATED WORK
In Baldi & Hornik (1989), it is shown that, under mild assumptions on data, two layer linear network with quadratic loss has no spurious local minima. This is probably the first positive result on this long line of investigation. Kawaguchi (2016) showed that it holds for deep linear network too. The tour de force proof in (Kawaguchi, 2016) works by examining the Hessian using powerful tools from the matrix theory. There have been much subsequent work to simplify and generalize the result. For example, Lu & Kawaguchi (2017) came up with different argument. Yun et al. (2018; 2019) showed simpler arguments for special cases and considered more general non-linear networks. Hardt & Ma (2017) showed that under certain assumptions, there might not even be stationary point in the deep linear residual network. Venturi et al. (2018) defined a notion of spurious valleys and showed that for quadratic losses, there is no spurious valley in deep linear networks. Venturi et al. (2018) was able to remove all the assumption in (Baldi & Hornik, 1989) under this weaker notion. The mild assumption in Baldi & Hornik (1989), which was also needed in Kawaguchi's proof, was removed by Zhou & Liang (2018), which leads to our Corollary 1.
Laurent von Brecht (2018) considers the special case of linear networks with the narrowest layer on the either end. It uses novel perturbation argument to show that for any convex differentiable loss, there is no spurious local minimum in such network. However, the special case considered in (Laurent & von Brecht, 2018) excludes networks through low rank approximation such auto- encoders. But it is really the intuitive yet powerful result in (Laurent & von Brecht, 2018) that motivated this work.
There have been recent studies on the gradient descent convergence on the deep linear net- works (Arora al., 2018; Bartlett et al., 2018; Arora et al., 2019). It has been shown by Arora
2

---

Under review as a conference paper at ICLR 2020
al. (2018) that, under certain conditions, increasing the depth of linear networks speed up the convergence, which is another positive property of deep linear networks.
There have been much work (Soltanolkotabi et al., 2018; Li & Liang, 2018; Allen-Zhu et al., 201 Ba;;; Du et al., 2018a; Zou et al., 2018; Du et al., 2018b) recently on studying the optimiza- tion landscape and convergence of non-linear networks. They focus mostly shallow networks with over- paeemeaaraeter wide layers.
PRELIMINARIES
We define notations used through the paper. We state some simple facts and the main theorem from Laurent & von Brecht (2018) which need in proof.
Deep linear networks. Denote by Rmxn all the matrices with m rows and n columns. For 1 S
i < k, let M2 _d For 2 j. denote by M, .-- -M the matrix product of -..-..... -M.. A (deep) linear network with parameters MI, MM is defined as 4(x) M₁ MM-... MM We call the depth of the network and dg. the input and the output dimensions, respectively. Define d = minogisk de be the narrowest width. We say a network has bottleneck if both do > d and dN > d. A multi-tower linear network defined as the sum of multiple linear networks (towers) with the same input and output dimensions.
Empirical loss. Given training data D which consist of examples of pairs of x, where the input feature vector Rd and the label in some arbitrary set, we wish to minimize the total loss:
L(M, Ma; D)
Σ fx()())) (aN))D
Σ
fy(M2 -,,)
(Z,9)ED
Define f(A) = Eawee fy (Ar). Then L(M My; D) = f(Mx M1). If fy's are all convex differentiable functions'. then clearly f convex differentiable too. Below we omit D and consider the loss function L Rd x xda- + R where L(M MM) f(M ... M.) for some f IRd xdo + R.
Derivative. Denote by aL the matrix form the partial derivative L with respect to M. L 8M7 has only one variable M, we write L' aL aM For simplicity, we sometimes abuse the notation by
using the same symbol for the variable and the value and omit the value. If L(X, Y) = S(XY), by at the chain rule, 8x J'(XY) and By X (XY)..
Local minimum. For any loss function L. MI,..., Mr is local minimum of L if there ex- ists an open ball B, in Frobenius norm, centered at MI...., Mr such that L(Mi,.... .Ma) < L(M, M,) for any (M, not a global minimum. If L is differentiable, then any local minimum a critical point of L. In particular, if L(M M&) f(M ... Mi), then MI, Mr satisfy that at GM,
.M) E B. A local minimum is called spurious if it is
(M4 f'M ... -M) ... -TM =0
We need the following theorem from Laurent & von Brecht (2018):
Theorem 3. Let Tx(M M₁) [(M.... ... M1) where f Rd xdo - R. a couvex differen- tiable function. If there is no bottleneck, i.e. do or dy = minogiss d, then any local minimum of Lg is a global minimum of f.
PROOFS
With the above preparation, we will now prove Theorem 1. bottleneck, i.e. d = d, or = do. then Theorem 3 immediately implies that all the local minima
the network we consider has no
In practice fy are typically convex. They usually differentiahle, and if not, can be smoothly approx- imated. For example the hinge loss he approximated by the modified Huber loss (Zhang, 2004).
3

---

Under review as a conference paper at ICLR 2020
for L3 global minima of f so the statement is vacuously true. Below we consider the case when = d, for some 0 j < k. Let A = My... M,+1 and B =M
My ...... M1. The following is the main
technical claim of the paper.
Lemma 1. If Mi:.... M₁ is local minimum, then either (' 0 or A, B both have rank d.
We first show that the above lemma implies Theorem 1.
Proof. (Theorem 1) If Le has spurious local minima, then L& has too. Since d, minos ist di for any A E gdaxd and B E _dd can easily construct matrices M, [ddixd;-1 for 1 S S k such that M₂ ... M = A, and My... ... M1 = B. If A, B is spurious local minimum L2, then clearly M,, MM. is spurious local minimum of Lg-
The other direction is implied by Lemma This implication has been used before multiple times by Kawaguchi (2016); Lu & Kawaguchi (2017); Yun et al. (2018). Here we include the easy proof for completeness. Suppose that M1;- .... MM is a local minimum of Lg. Then by Lemma 1, either (A = 0 or A, B both have rank d. If (AAB) of f because f is convex. Hence M M2 is a global minimum of L too.
then AB My M1 is global minimum
In the other case, A and B both have full rank d. We show that any local perturbation A (resp. B) can be performed by local perturbation to M₁ (resp. M1). If A = M2 ... M,+1 has rank d, then A1 = M M E 1 xd has rank d too because d S dR-1. Then for any D E IR xd there exists D1 E IRd xde-1 such that D1 = D. Hence (M₃ + DD))AI = Mr + DDA1 = D. This implies any local perturbation to A can be done through local perturbation to M, More precisely, there exists a constant
O, such that for any D E Rd there exists D1 E R xd, with |Dill I D|| and D1A; D. Same true for B. This implies that if Lg (M1...... My) is minimum in an open ball of radius 5 centered at M1,... Mr., then L2 (A, B) is minimum in an open ball of radius 6/c centered at A, Hence if M1 M1,... Mr is local minimum of Lak, then A, B is a local minimum of 222 If T22 has no spurious local minima, A, B, hence MI...., M3. is global minimum.
In the above proof, we actually showed that if Mi...., Mr is spurious local minimum of Lg, then A MM-- ... M1+1; B My Mj 1 is spurious local minimum of L2. That is, every spurious local minima of Lt can be directly mapped to spurious local minimum of L2, hence the title of the paper.
Lemmal 1 directly implies Theorem 2.
Proof. (Theorem 2) Consider the case of k 2 and j 1. Then we have A M2 Rd and = M1 E Rdxdd xdo with dj < min(dy, d2). If A, B is a spurious local minimum of L2, then ('(AB) # because otherwise they would have been global minimum of f. By Lemma have that both A, B are of rank d1, i.e. they both have full rank because di < do, d2-
To prove Lemma we first observe that Lemma 2. If M1,..., Mg is local minimum of T.g, then öLg DA (A, B) 0, 0L. (A, B) 0.
Proof. Define (X L2(X, B) = J)X Clearly gB is convex and differentiable too. Let Lp M,) = On(M, ... -M If M,,..., M₁ is a local minimum L,, then M,-1...., M2 must be a local minimum of LB. In addition, d, minosica de minjsiga di so there is no bottleneck in MM+1..... Mg. We apply Theorem 3 to get that A = M2 ... ..MM5+ is global minimum of gn. hence 8Lg
0B 24 (A, B) = O. Similarly 8Lg (A, B) =0 0.
Now we prove the key technical claim of Lemma 1.
Proof. (Lemma 1)
We just need to show that if (AB) + 0, then A, B must be of rank d. Below we assume ('A)) +
O. We will show that A has rank d. For B, apply the same argument to g(X) = f(X)).
4

---

Under review as a conference paper at ICLR 2020
Let denote the rank of A. We will derive contradiction by assuming an argument by Laurent & von Brecht (2018) to construct family of local minima. Since A M₁. -.MM is of rank < d. for any 2 < S 1. Mg... M, has rank at most Since d I d,-1, there exists nonzero w Rd such that Ma ... M, 0. Then for any Ui-1 E R24-2, we have
d. We first use
Mr M...-M,(M,111 + Wi 1 M M,-1.
Now for any 01 U2, ... ,, where os 12d1-1, we claim that
M M + m5of)) (Mi + wivo) = M ..... M1.
(1)
This can be shown inductively for j. 1.
Ms- M1+1 + wruf) ... (M; + m,uuf) M M2
Since M = (M,,..., M&) a local minimum, it is the minimum in an open neighborhood of M. If set [|e/l's small enough that M (M1 + wref, .M wyyy, M M&3) is in
a smaller neighborhood, then M is a local minimum too since La (M) = (x()). See Claim in (Laurent & von Brecht, 2018) for rigorous proof.
Let B My MM. Then by Lemma 2. 8La Since AB AAB, we have that for any Mi.... Mj constructed above,
od (A, B) O, ie ff(A 04
(A, B) ('AB) 0.
F(ABB) =
(2)
For any matrix M E Rmi denote by M E R= the f-th row vector of M, and by R(M) all the row vectors of M. Consider the linear subspace
= fu R ('(AB) =
Then (2) implies that R(B) C V. We now show that we can choose v,'s for 1 < S such that B = My... M1 contains a row vector which is not in to reach a contradiction.
Let 1" min(i R(M. M)) S v). If 1. choose sufficienlly small non-zero vector en E V. This can be done by our assumption that ('(AB) * Set M₁ = M1 + wr Since
W1 * 0. there exists l such that wie * 0. Then Mf = Mf + w1eV1. By M E V, v1 & V,w1e # O, have Mf & V since V is linear subspace. Now assuming 1" 1. Suppose that have constructed M,,..., M1. for some 2 1" 2 1, such that R M, ... M2) & V. We show the construction for + 1. If R(M+++ M .. M,) & V. then we can simply set M,+1 M Assume below that R(M M, ... M1) C V. By inductive hypothesis R(M, ... M1) g V, thus there exists say the h-th row vector of M, ......M.. M2 not in V. Set u++1 as the L-th basis vector in Rd, so that Ui M, M.... N....., UT. Now let M, M + W:410 Then
M ... Mi M4t M, M1 w/ o 1 M, M,
M,+1M, M1 woi1e.
Since R(M+11M.-.. M2) C V but V and w++1 # 0, by the same argument as for i" 1, there must exist a row vector in M M, which not in V. We have inductively constructed B = My... ... M, such that R( & V. contradicting to (2). Hence A must have rank d. This concludes the proof.
Corollary immediately follows from Theorem and Theorem 2(1) in (Zhou & Liang, 2018). In the following, we prove Corollary 2.
5

---

Under review as a conference paper at ICLR 2020
Proof. (Corollary 2) If some tower has bottleneck, tower, we can then apply Theorem 1 to show that any local minimum a global minimum. Hence the statement holds. Below we assume that each tower has bottleneck with width 6;-
fix all the parameters but this
Suppose that we have a spurious local minimum M = (M11.... Mikes... Ma ......... M ). Similar the proof of Theorem 1, the bottleneck layer. Write M = => A, Similarly we can show that either f'(M) = 0 or all the A,, B ss have full rank. Since M a spurious local minimum, it must be the second case, i.e. all the
break each tower A, E RRmb,, B; E R x at
B1
A, B; have full rank. Now let A = (A A.) and B =
Then A E Rmxb B E R
B
where b bj +... +...+ by. By the same argument in the proof of Theorem 1, any perturbation of A, B can be done through perturbation of M, hence A, B is spurious local minimum for the single tower two layer network AB, If b 2 m, n, then Theorem 3 implies that any local minimum is global minimum of f.
4 CONCLUSION
We have shown a non-degeneracy property of local minima in deep linear networks for general con- vex differentiable loss. This property allows us reduce the existence of spurious local minima in a deep (with depth 2 3) linear network to the two layer linear network, and, for two layer networks, to simplify analysis by removing the rank-deficient case. We show the application to quadratic loss functions and the generalization multi-tower deep linear networks. Our proof uses novel perturbation argument and does not require any heavy mathematical machinery.
It would be interesting to study when there is no spurious local minima beyond the quadratic loss. By our result, we only need to consider the two layer case. Another interesting question is whether similar phenomenon exists for non-linear networks.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang Learning and generalization in overparameter- ized neural networks, going beyond two layers. arXiv preprint arXiv: 1.04918, 2018a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. arXiv preprint 1...0 2018b.
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. arXiv, 2018.
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient de- scent for deep linear neural networks. In International Conference on Learning Representations, 2019. URL https: wwwp//weneee...e/////p/.. net form/formmmm/mmm http://ooommmm.sk/0gggggg//a
Pierre Baldi and Kurt Hornik. Neural networks and principal component analysis: Learning from examples without local minima. Neural networks, 2(1):53-58, 1989.
Peter Bartlett Dave Helmbold, and Phil Long. Gradient descent with identity initialization effi ciently learns positive definite linear transformations. In ICMI, 2018.
Simon S Du, Jason D Lee, Liwei Wang Haochuan Li and, and Xiyu Zhai. Gradient descent finds global minima deep neural networks. arXiv preprint arXiv: 181 1.03804, 2018a.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. arXiv preprint arXiv: I811 1811.0380,, .3800, 2018b.
Mortiz Hardt and Tengyu Ma. Identiy matters in deep learning. In International Conference Learning Representations, 2017.
Kenji Kawaguchi. Deep learning without poor local minima. In Advances in Neural Information Processing Systems, pp. 586-594, 2016.

---

Under review as a conference paper at ICLR 2020
Thomas Laurent and James von Brecht. Deep linear networks with arbitrary loss: All local minima are global. In International Conference on Machine Learning, pp. 2908-29133 2018.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent structured data. NeurIPS, 2018.
Haihao Lu and Kenji Kawaguchi. Depth creates no bad local minima. arXiv preprint arXiv:/702.08850, 2017.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over-parameterized shallow neural networks. IEEE Transactions on Information Theory, 2018.
Luca Venturi, Afonso S Bandeira, and Joan Bruna. Spurious valleys in two-layer neural network optimization landscapes. arXiv preprint arXiv:1802.06384, 2018.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Global optimality conditions for deep neural networks. In International Conference on Learning Representations, 2018.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small nonlinearities in activation functions create bad local minima in neural networks. In International Conference Learning Representations, 2019.
Tong Zhang. Solving large scale linear prediction problems using stochastic gradient descent algo- rithms. In ICML, 2004.
Yi Zhou and Yingbin Liang. Critical points of linear neural networks: Analytical forms and land- scape properties. In International Conference on Learning Representations, 2018.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv preprint arXiv:1811.08888. 2018.


Reviews:
[{"review_id": "ryxmC2kpFB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper shows an interesting result: deep linear NN has introduced no more spurious local minima than two layer NN and provides an intuitive and short proof for the results, which improve and generalize the previous results under milder assumptions. Overall, the paper is well written and clear in comparison and explanation. \n\nThe weakness is that the main theoretical contribution seems to be merely Lemma 1, and all other theorems are a direct corollary. Also, it would be of great interest to see concrete results on non-linear neural networks, since that is exactly what is used in common practice.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SylpH0iMqH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The motivation of this paper is training deep neural network seems to not suffer from local minima, and it tries to explain this phenomenon by showing that all local minima of deep neural network is global minima. The paper shows that for any convex differentiable loss function, a deep linear neural network has no so called spurious local minima, which to be specific, are local minima that are not global minima, as long as it is true for two-layer Neural Network. The motivation is that combining with existing result that no spurious local minima exists for quadratic loss in two-layer Neural Network, this relation connecting between two-layer and deeper linear neural network immediately implies an existing result that all local minima are global minima, removing all assumptions. The result also holds for general “multi-tower” linear networks. \n\nOverall, this paper could be an improvement of existing results. It is well written and the proof step is clear in general. However, there’re some weakness need clarifications on the results, especially on the novelty. Given reasonable clarifications in response, I would be willing to change my score.\n\nFor novelty, it is unclear if the results from Lemma 1 to Theorem 1 and 2 are both being stated as novel results. The first part of proof of Theorem 1 is obvious and straightforward, and the other direction has been used before for multiple times as claimed in the paper, what is your novelty exactly here? For the key technical claim of Lemma 1, it looks like this perturbation technique already exists in (Laurent & Brecht, 2018), why do you claim it as a novel argument? \n\nBesides novelty, there are also some other unclear pieces in this paper needs clarification:\n1)\tIs the main result which is “no spurious local minima for deep neural network” holds for any differentiable convex loss other than quadratic loss? How will Theorem 1 help us understand the mystery of neural network? \n2)\tHow does the result help us understand non-linear deep neural network, which is commonly use in practice?\n3)\tThe paper should give some explanations about why the results help training neural networks.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "B1gk7EgVYr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \n\nThe paper shows a deep linear network has no spurious local minima as long as it is true for the two layer case for any convex differentiable loss. \n\nComments: \n\n1) I understand that there exists some work on deep linear network recently. However, they seem to be only for theoretical purpose. Most of the current practical problems do not consider this kind of network for training. If it has high impact in practice, then people are starting to use it. Could you please provide more reasons why we need to care about this impractical network? \n\n2) It is still unclear about the contributions of the paper. Why “deep linear network has no spurious local minima as long as it is true for the two layer case” is important? And what we can take any advantage from here? What if there exist some spurious local minima for the two layer case (which is widely true)? \n\n3) The paper looks like a technical report and seems not to be ready. \n\nThe results are quite incremental from the existing ones. The contributions of this work to the deep learning community are still ambiguous. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Paper shows that the question of linear deep networks having spurious local minima under benign conditions on the loss function can be reduced to the two layer case. This paper is motivated by and builds upon works that are proven for specific cases. Reviewers found the techniques used to prove the result not very novel in light of existing techniques. Novelty of technique is of particular importance to this area because these results have little practical value in linear networks on their own; the goal is to extend these techniques to the more interesting non-linear case. 
Decision: Reject