Pure and Spurious Critical Points: a Geometric Study of Linear Networks
Authors: Matthew Trager
Kathlén Kohn
Joan Bruna
Venue:  (2020)
Keywords: Loss landscape
linear networks
algebraic geometry

Abstract: The critical locus of the loss function of a neural network is determined by the geometry of the functional space and by the parameterization of this space by the network's weights. We introduce a natural distinction between pure critical points, which only depend on the functional space, and spurious critical points, which arise from the parameterization. We apply this perspective to revisit and extend the literature on the loss function of linear neural networks. For this type of network, the functional space is either the set of all linear maps from input to output space, or a determinantal variety, i.e., a set of linear maps with bounded rank. We use geometric properties of determinantal varieties to derive new results on the landscape of linear networks with different loss functions and different parameterizations. Our analysis clearly illustrates that the absence of "bad" local minima in the loss landscape of linear networks is due to two distinct phenomena that apply in different settings: it is true for arbitrary smooth convex losses in the case of architectures that can express all linear maps ("filling architectures") but it holds only for the quadratic loss when the functional space is a determinantal variety ("non-filling architectures"). Without any assumption on the architecture, smooth convex losses may lead to landscapes with many bad minima.

Published as a conference paper at ICLR 2020
PURE AND SPURIOUS CRITICAL POINTS: A GEOMETRIC STUDY OF LINEAR NETWORKS
Matthew Trager* New York University
Kathlén Kohn" KTH Stockholm
Joan Bruna
New York University
ABSTRACT
The critical locus of the loss function of neural network is determined by the geometry of the functional space and by the parameterization of this space by the network's weights. We introduce a natural distinction between pure critical points, which only depend on the functional space, and spurious critical points, which arise from the parameterization. We apply this perspective to revisit and extend the literature on the loss function of linear neural networks. For this type of network, the functional space is either the set of all linear maps from input output space, or a determinantal variety, i.e., a set of linear maps with bounded rank. We use geometric properties of determinantal varieties derive new results on the landscape of linear networks with different loss functions and different parameterizations. Our analysis clearly illustrates that the absence of "bad" local minima in the loss landscape of linear networks is due to two distinct phenomena that apply in different settings: case of architectures that can express all linear maps ("filling architectures") but it holds only for the quadratic loss when the functional space a determinantal variety ("non-filling architectures"), Without any assumption the architecture, smooth convex losses may lead to landscapes with many bad minima.
true for arbitrary smooth convex losses in the
INTRODUCTION
fundamental goal in the theory of deep learning is to explain why the optimization of the non- convex loss function of neural network does not seem to be affected by the presence of non- global local minima. Many papers have addressed this issue by studying the landscape of the loss function (allii& & Hornik 1989 Choromanska et al. 2015 Kawaguchi 2016 Venturi al. 2018). These papers have shown that, in certain situations, any local minimum for the loss is in fact always global minimum. Unfortunately, it is also known that this property does not apply more general realistic settings (Yun et al.) [0188 Venturi et al.) 2018). More recently, researchers have begun to search for explanations based on the dynamics optimization. For example, in certain limit situations, the gradient flow of over parameterized networks will avoid local minimizers (Chizat & Bach, 2018 Mei et al.) 2018). We believe however that the study of the static properties of the loss function (the structure of its critical locus) is not settled. Even in the case of linear networks, the existing literature paints a purely analytical picture of the loss, and provides no sort of explanation as to "why" such architectures exhibit no bad local minima. A complete understanding of the critical locus should be a prerequisite for investigating the dynamics of the optimization.
The goal of this paper is revisit the loss function of neural networks from a geometric perspective, focusing on the relationship between the functional space of the network and its parameterization. In particular, view the loss as composition
(parameter space] 1, (functional space] 4 R.
In this setting, the function is almost always convex, however the composition I. o not. Critical points for T, can in fact arise for two distinct reasons: either because we are applying é to a non-convex functional space, or because the parameterizing map μ is locally degenerate. We distinguish these two types of critical points by referring to them, respectively, pure and spurious.
"Equal contribution.

---

Published as a conference paper at ICLR 2020
Table 1: Bad local minima in loss landscapes for linear networks
quadratic loss
other smooth convex loss no had minima bad minina exist
no bad minima non-filling no bad minima
filling
convex optimization over vector space
special property of determinantal varieties
Intuitively, pure critical points actually reflect the geometry of the functional space associated with the network, while spurious critical points arise as "artifacts" from the parameterization. After defining pure and critical points for arbitrary networks, we investigate in detail the classification of critical points in the case of linear networks. The functional space for such networks can be identified with family of linear maps, and we can describe its geometry using algebraic tools. Many of our statements rely on a careful analysis of the differential of the matrix multiplication map. In particular, prove that non-global local minima are necessarily pure critical points for convex losses, which means that many properties of the loss landscape can be read from the functional space. On the other hand, emphasize that even for linear networks it is possible to find many smooth convex losses with non-global local minima. This happens when the functional space is a determinantal variety, i.e., (non-smooth and non-convex) family of matrices with bounded rank. In this setting, the absence of non-global minima actually holds in the particular case of the quadratic loss, because very special geometric properties of determinantal varieties that we discuss.
Related Work. Baldi & Hornik 1989) first proved the absence of non-global ("bad"") local min- ima for linear networks with one hidden layer (autoencoders). Their result was generalized the case of deep linear networks by Kawaguchi (016)) Many papers have since then studied the loss landscape of linear networks under different assumptions (Hardt & Ma 2016] Yun et al. 2017 ZZhou & Liang 2017, Laurent & von Brecht, 2017 Lu & Kawaguchi] 2017 Zhang (019)). In particular, Laurent von Brecht (2017) showed that linear networks with "no bottlenecks" have no bad local minima for arbitrary smooth loss functions. Lu & Kawaguchi (017)) and Zhang (2019) argued that "depth does not create local minima", ", meaning that the absence of local minima of deep linear net- works is implied by the same property of shallow linear networks. Our study of pure and spurious critical points can be used as a framework for explaining all these results in unified way. The opti- mization dynamics of linear networks are also active and our analysis of the landscape in function space sets the stage for studying gradient dynamics on determinantal varieties, as in Bah et al. (2019). Our work is also closely related to objects of study in applied algebraic geometry, particularly determinantal varieties and ED discriminants (Draismal al. 20113 Ottaviani et al., 2013). Finally, we mention other recent works that study neural net- works using algebraic-geometric tools (Mehta et al. 2018
of research (Arora et al.) 2019 2018),
Kileel et al. 2019
Jaffali & Oeding
2019)
Main contributions.
We introduce natural distinction between "pure" and "spurious" critical points for the loss func- tion of networks. These notions provide an intuitive and useful language for studying a central aspect in the theory of neural networks, namely the (over)parameterizzaion of the functional space and its effect on the optimization landscape. While most of the paper focuses linear networks, this viewpoint applies to more general settings as well (see also our discussion in Appendix A..3..
We study the pure and critical locus for linear networks and arbitrary loss functions. We show that non-global local minima are always pure for convex losses, unifying many known properties on the landscape of linear networks.
We explain that the absence of "bad" local minima in the loss landscape of linear networks is due to two distinct phenomena and does not hold in general: it is true for arbitrary smooth convex losses in the case of architectures that can express all linear maps ("filling architectures") and it holds for the quadratic loss when the functional space is a determinantal variety ("non-filling architectures"), ) Without any assumption on the architecture, smooth convex losses may lead to many local minima. See Table
2

---

Published as a conference paper at ICLR 2020
Figure I: Pure and spurious critical points: 81 is pure critical point, while 82 is a spurious critical point (the level curves on the manifold Ma describe the landscape in functional space). Note that 0g is mapped to the same function as 02, but it is not a critical point.
We provide a precise description of the number topologically connected components of the set of global minima. This relates to recent work on "mode connectivity" in loss landscapes of neural networks (Garipov et al. 2018).
We spell out connections between the loss landscape and classical geometric objects such as caustics and ED discriminants. We believe that these concepts may be useful in the study of more general functional spaces.
will make use of elementary notions from differential geometry. If M and A are manifolds and : M + W is smooth map, then write dg(x) for the differential of g at the point This means that dg(x): T.M + T - is the first order linear approximation of at the point E M. If .M and N have singularities, then the same definitions apply if restrict y to smooth points in M whose image is also smooth in N. For most of our analysis, manifolds will be embedded in Euclidean spaces, say M C Rn and A C R" so we can view the tangent spaces T&M and Ta as also embedded in Ihm and IR.. When . = IR. the critical locus of a map g M - IR is defined as Crit(g) = {i E Smooth(M)) dg(x)) 0}.
Differential notation. Our functional spaces will be manifolds with singularities,
2
PRELIMINARIES
2. PURE AND SPURIOUS CRITICAL POINTS
A neural network (or any general "parametric learning model") is defined by continuous mapping Rd Rd, Rdd that associates input vector & E Rdz and set of parameters 0 Rddo to
an output vector y = 4(0, x) E Rdy, In other words, & determines family of continuous functions parameterized by E Ry:
Ma (fe Rd + Rd fo = ((0,)) c. C(RL=, Rx)).
Even though Ma is naturally embedded in an dimensional. In fact, if the mapping & is smooth, then Ma is a finite dimen--imeniional manifold with singularities, and its intrinsic dimension is upper bounded by de. It is also important to note that neural networks are often non-identifiable models, which means that different parameters can rep- resent the same function (i.e., fo for does not imply 0 0'). The manifold M₁ is sometimes known as a neuromanifold (Amari 2016). We now consider a general loss function of the form
functional space, it is itself finite
L = l μt, where μ dd Mo is the (over)paraetterizztion of Mo by and is functional defined on subset of C(Rd= RR,)) containing Me!
L : de M4 Ma
E R.
(I)
Definition 1. A critical point 6* E Crit(L) is pure critical point if u((*) is critical point for the restriction Ls (note that this implicitly requires u(0*) to be smooth point of M2). If 0r Crit(T.) but ((0") & Crit(f) we say that 0r is a spurious critical point.
"This setting applies to both the empirical loss and the population loss.
3

---

Published as a conference paper at ICLR 2020
It is clear from this definition that pure critical points reflect the geometry of the functional space, while spurious critical points do not have an intrinsic functional interpretation. For example, if 8 E CL) is spurious critical point, then it may be possible to find another parameter O' that represents the same function fo- = for and is not a critical point for I. (see Figure In contrast, if lt is pure critical point, then all parameters I' such that ju(6") = nu(0)) are automatically in Cr) simply because dL((0)= = dll Ma (u((0)) dp(0"). This will motivate us to study the fiber {0) p())= = f} of all parameters mapped to the same function f (particularly when the function is a critical point of ).
We note that a sufficient condition for 0 E Crit(L) be a pure critical point is that the differential dp(0") ) at 0 has maximal rank (namely dim M2), i.e., that p is locally a submersion at 0" Indeed, we have in this case
0 0=
(u(0))) dp(00) - de (u(O0)) = 0,
so p(00) is critical for the restriction of to Ma. We also point out special situation when Mg is a convex set (as a subset of C(TTR,, )) and é is a smooth convex functional... In this case, the only critical points of L, are global minima, a global minimum or a spurious critical point. The following simple observation gives a sufficient condition for critical points to be saddles (i.e., they are not local minima local maxima).
deduce that any critical point of L = l o fa is either
Lemma 2. Let l' E Crit(L) be a (necessarily spurious) critical point with the following property: for any open neighborhood U of 0, there exists 8' in U such that (u((') = m(() and 0' & Crit(L). Then O* is a saddle for L.
Proof. Assume that 0* is a local minimum (the reasoning is analogous if 0" is local maximum). This means that there exists a neighborhood U of 0" such that L(0) 2 L(0") for all 0 E U. In particular, if O' U is such that uu0') p(0), then O' must also be local minimum. This contradicts 0' & Cril(D).
This general discussion on pure and spurious critical points applies to any smooth network map & (with possible extensions the case of piece-wise smooth mappings), and we believe that the dis- tinction can be useful tool in the study of the optimization landscape of general networks. In the remaining part of the paper, we use this perspective for an in-depth study of the critical points of linear networks. For this type of network, the functional set Ma can be embedded in finite di- mensional ambient space, namely the space of all linear maps TR - RRd, Furthermore, Ma an algebraic variety (a manifold that can have singularities and that can be described by algebraic equations). We will use basic tools from algebraic geometry to provide a complete description of pure and spurious critical points, and to prove new results on the landscape of linear networks.
2.2 LINEAR NETWORKS AND DETERMINANTAL VARIETIES
A linear network is a map +. d x Rd + R. of the form
( x) = WT. WII, 0 0= (Wn. W1) Rdo
(2)
where W. E 2 are matrices (so do das dn = dy. and do dodi + d1d2 + ... + d
The functional space is in this case subset of the space of all linear maps R.do - RRd As in we can decompose a loss function I. for linear network as
dd xda-1 X X... X RR Xd
pd X W, W1
R ((W)
3
(Wh..... Wi)
W
Here pdd is the matrix multiplication map for the sequence of widths d = (dp...., do). and is a functional on the space of (d,, x mmtticcss In practice, it is typically a functional that depends on the training data, e.g. E(W)= = || X Y|2 for fixed matrices X, Y E Note that even if & is a convex functional, the set Ma will often not be a convex set. In fact, it is easy to see that the image of pa is the space M, of (d, x do) matrices of rank at most min(dn- ... ). If < min do. dr), this
Our setting can also be applied when includes a regularizer term defined in function space, e.g., E(W) = XX-- X 21 AR(W).
4

---

Published as a conference paper at ICLR 2020
set is known determinantal variety, classical object of study in algebraic geometry (Harris 1995). It is fact an algebraic variety, i.e., it is described by polynomial equations in the matrix entries (namely, it is the zero-set of all (r + 1) x (r + - and it is well known that the dimension of M, is r(m + n r). Furthermore, for r > 0, the variety M, has many singularities: its singular locus is exactly M,-1 M,, the of all matrices with rank strictly smaller than r. We refer the reader to Appendix A.1 for more details on determinantal varieties.
MAIN RESULTS
In this section, we investigate the critical locus Crit(L) of general functions Rd - R of the form I, l o pd where f IR xda R is (often convex) smooth map, and pa is the matrix multiplication map introduced in (3) By studying the differential of fa we will characterize pure and spurious critical points of L. As previously noted, the image of pd is M, C [d xdo where r min d. In particular, we distinguish between two cases:
We say that the map pa is filling if r min d so M, = Rd xdo In this case, the functional space is smooth and convex.
We say that the map pa is non-filling i < min d so M, ç xdd is a determi- nantal variety. In this case, the functional space is non-smooth and non-comve.
3.1 PROPERTIES OF THE MATRIX MULTIPLICATION MAP
We present some general results on the matrix multiplication map /aa, which we will apply to linear networks in the next subsection. These facts may also be useful in other settings, for example, to study the piece-wise linear behavior of ReLU networks.
We begin by noting that the differential map of pa can be written explicitly
dpa(0)(Wn,..... Wi) = W.W. W, + W.W. Wi +.... W.... W2W,
(4)
Given matrix M Rmxn denote by Row(M) C R" and Col(M) C IRM the vector spaces spanned by the rows and columns of M, respectively. Wer Wi-iWi-1--. ... W1, the image of dua(O) in Writing W>; = W W and
dd @ Row(Wel) cn) +... Col(Ws.) @ Row (W .... Col(W &O Rd.
(5)
From this expression, we deduce following useful fact.
Lemma 3. The dimension of the image of the differential dua at (Wn,..., ".,...,,)))) is given by
A-1
(0) Σ rk(W rk(We.) Σ
rk(W>)) rk(We++1),
where we use the convention that W=1 Ido: W>h = Lds are the identity matrices of size do- da-
We can use Lemma 3 to characterize all cases when the differential dua at 0 = (Wn...., W1) has full rank (i.e., when the matrix multiplication map is local submersion onto M,).
Theorem 4. Letr (, (W....., W1). and W (a))).
(Filling case) If r min (r, do). the differential dpa(O) has maximal rank equal to dim M, dr if and only if. for every E (1,2,...,,h 1}, either rk(W>.) dr. rk(W<ct))) = do holds.
(Non-filling case) Ifr < min, do the differential (pa has maximal rank equal to dim M, = rdd, + do - r) if and only if rk(W) =T.
Furthermore, in both situations, if rk)))) = r, then the image of dpa(() always contains the langent space Me of Me M, at W.
5

---

Published as a conference paper at ICLR 2020
We note that (f) has always maximal rank when rk( = minfd,), however in the filling case it is possible obtain a local submersion even when rk(W) < r (see Example in appendix). We next describe the fiber of the matrix multiplication map, that is, the set
Nd (W) - {(Wn,.... Wi) W = W.... WT, W; E R_xxd-1..
will be convenient to refer to Hd (W) as the set of difactorizations of W. We are interested in understanding the structure of Ha *+'(W) since, as argued in Section 2.1 pure critical loci consist of fibers of "critical functions". The following result completely describes the connectivity of Ha (W). then the set of d-factorizations pd (W) of W has exactly 2' path-connected components, where # d; = r; 0<k << h3. If (k((W) r, then P' (W) is always path-connected.
Theorem 5. Let min(d.). If ffr((W)
3.2 APPLICATION TO LINEAR NETWORKS
We now apply the general results from the previous subsection to study the critical locus Crit(L) (L) with I, o jid, where l any smooth function. In the following, we always use r = min (ra) and W = =a(0). The next two facts follow almost immediately from Theorem 4
Proposition 6. If 0 is such that (0) has maximal rank (see Theorem F.. then 0 E Crit(L) if and only W E Cri)(()M.), and 0 is a minimum (resp., saddle, maximum) for L if and only is is minimum (resp., saddle, maximum) for El.. rk()) = (which implies that dpa(O) has maximal rank) and 0 E Crit(L), then all d-factorizations of W also belong to Crit(L).
Proposition If E Crit(L) with rk(W) = S T, then W Crit(l)M.). other words, rk(w)) r, then 0 Crit(L) implies that W critical point for the restriction of to smaller determinantal variety Me (which is in the singular locus of the functional space Mr in the non-fillin case).
Note that if da 1, then either W 0 or rk(W) 1, and in the latter case Proposition 7 implies that W E Crit(Aludd tat). If l is convex, we immediately obtain that all critical points (not just local minima, as in Laurent & von (recht((2017) below certain energy level are global minima.
Corollary 8. Assume that l is smooth convex function and that da If 0 Crit(T.). then either W ma((f) 0 0 is global minimum for L.
Proposition 7 shows that critical points for L such that rk(W) correspond critical points for E restricted to a smaller determinantal variety. Using Lemmal are essentially always saddles for L.
2
it is possible to show that these points
Proposition 9. Let 0 E Cril(L) be such that rk(W) < r, and assume that d((W) + O. Then, for any neighborhood U of 0, there exists 6' in U such that pa((0") = =W but 0' & Crit(L). In particular, is a saddle point.
Proposition 10. Let be any smooth convex function, and let L= pa. If 9 is non-global local minimum for L,, then necessarily rk(W) = (so 0 is a pure critical point). In particular, L, has non-global minima if and only if fl,, has non-global minima.
This statement succinetly explains many known facts the landscape of linear networks. For example, we recover the main result from (Laurent & von Brecht (017), which states that when e is smooth convex function and ja is filling (r min d, then all local minima for I. are global minima: indeed, this is because M, = d xdo a linear space, so L does not have non-global minima. On the other hand, when μa not filling, the functional space not convex, and multiple local minima may exist even when is convex function. We will in fact present many examples of smooth convex functions such that L fo Pdd has non-global local minima (see Figure 33. In the special case that É is quadratic loss (for any data distribution), then it is remarkable fact that there are no non-glohal local minima even when pa not filling (Baldi & Hornik, 1989 Kawaguchi] 2016). In the next section, we will provide an intrinsic geometric justification for this property.
Remark 11. In Laurent & von Brecht (201)) the authors observe that their "structural hypothesis" (i.e., for us, the fact that the network is filling) is necessary assumption for their main result,

---

Published as a conference paper at ICLR 2020
otherwise critical points of E might not lie in the functional space of the network. This last observation however does not imply the necessity of the filling assumption, and indeed in the case of the quadratic loss there no local bad minima despite the fact M, & Rd
Finally, we conclude this section by pointing out that although the pure critical locus is determined by the geometry of the functional space, the "lift" from function space to parameter space is not com- -inttie-dimensinnall set of critical parameters
pletely trivial. In particular, there is always a large associated with critical linear function W (all possible d-factorizations of W.. More interestingly, this set may be topologically disconnected into large number of components that are all function- ally equivalent (see Theorem 5 This observation agrees with the folklore knowledge that neural networks can have many disconnected valleys where the loss function achieves the same value.
3.3 THE QUADRATIC LOSS
We now assume that : Rdyxdd + R is of the form <(W) = II - YI where X E Rd and Y E Rd, are fixed data matrices. As mentioned above, is known that L pa has no non-global local minima, even when Ha is non-filling (Baldi & Hornik 1989; Kawaguchi 2016). In this section, we discuss the intrinsic geometric reasons for this special behavior.
It is easy to relate the landscape of L with the Euclidean distance function from determinantal variety (or, equivalently, to the problem low-rank matrix approximation.. Indeed, we know from Proposition that L has non-global local minima if and only if the same is true for f),,. Further- more, assuming that X has full rank, we use its square root P = (XX77)/> as positive definite matrix to derive
I[X - 211 = (WX, WX), 2 (Y,Y)
(Y,Y)r
IWP WWP-Qol 2o12 const.,
where Qo Y--p-1 and "const." only depends on the data matrices X and Y. Hence, minimiz- ing E(W) is equivalent to minimizing IWP -PQ221 1o Since the bijection M, + M,, W + WP also a bijective on the tangent spaces. it provides a one-to-one correspondence from the crit- ical points of minweM. ||WP- - Qoll to the critical points of minweM. I|W Qoll.. All in all, studying the critical points of M, is equivalent to studying the critical points of the function hao (W) ||W - Qoll where W is restricted to the determinantal variety M,
The function (W) is described by following generalization of the classical Eckart- Young The- orem. The formulation we prove is an extension of Example 2.3 in Draisma & Horobet (2014) and Theorem 2.9 in Ottaviani et al. (2013). We consider fixed matrix Qo E Xd, and singular value decomposition (SVD) Qo = U.VT where we assume Σ E By Xdz has decreasing diagonal entries 01,.... Oms with m = min(dy, dz). For any C {1, m} we write Σn E RRd, xd, for the diagonal matrix with entries aI.1. JI.m where TI,; o; if E I and σI, = 0 otherwise.
Theorem 12. If the singular values of Qo are pairwise distinct and positive, hqulM, has exactly (T)) critical points, namely the matrices Qz = U'rV'' with # (Z) r. Moreover, its unique local and global minimum is Q.1....... More precisely, the index of QI as a critical point of h MM. (i.e., the number of negative eigenvalues of the Hessian matrix for any local parameterization)
index((2)
1j>1}.
where Ie = (l,..., m} \I. I.
In the appendix we present a more general version of this statement without the assumption that the singular values of Qo are pairwise distinct and positive. The surprising aspect of this result that the structure of the critical points is the same for almost all choices of Qn- We want to emphasize that this is a special behavior of determinantal varieties with respect to the Euclidean distance, and the situation changes drastically if we apply even infinitesimal changes to the quadratic loss function. More precisely, any linear perturbation of the Euclidean norm will result in totally different landscape, as the following example shows (more details are given in Appendix AA.)).
Example 13. Let us consider the variety Mi S 3333 of rank-one for almost all Qo, the function houl Mr has three (real) critical points. Applying a linear change of coordinates dd xd= 2 Rddddz yields different quadratic loss hq.- Using tools from algebraic
By Theorem 12
7

---

Published as a conference paper at ICLR 2020
Figure 2: Left: I C R is an ellipse, the distance function (p) = llp ulI2 generally has 2 or 4 real critical points, depending whether u lies inside or outside the diamond- shaped region bounded by the caustic curve. Right: If V C RR² is a circle, then the caustic curve degenerates point and the distance function generically has always 2 real critical points.
restricted to
geometry, it is possible to show that for almost all linear coordinate changes (an open dense set), the function hio lM, has 39 critical points over the complex numbers The number of real critical points however varies, depending on whether Qo belongs to different open regions separated by caustic hypersurface in g Furthermore, the number of local minima varies as well; particular, it is no longer true that all Qo admit a unique local minimum. Figure 3 presents some simple computational experiments illustrating this behavior.
For all determinantal varieties. the situation is similar to the description in Example More generally, given an algebraic variety V IR" and point u E R", the number of (real) critical points of the distance function (p) Ip u||2 restricted V is usually not constant as u varies: the behavior changes when u crosses the caustic hypersurface, or ED (Euclidean distance) discriminant, of V: see Figure 2 In case of determinantal varieties with the standard Euclidean distance, this caustic hypersurface (more precisely its real locus) degenerates a set of codimension 2, which does not partition the space into different regions. This is analogous to the case of the circle in Figure
11
number local minima
Figure 3: Real critical points and local minima for random choices of hqo lM, as defined in Exam- ple 13 The size of each disk is proportional to the number of instances we found with that number of critical points and local minima. This shows that linear networks with a convex loss may indeed have multiple non-global local minima. More details in Appendix A.2 (Table 2 and Experiment I
3.4 USING DIFFERENT PARAMETERIZATTINSS NORMALIZED NETWORKS
In the simple linear network model (2). the functional space M, C Rd is parameterized using the matrix multiplication map Pa- On the other hand, one can envision many variations of this model that are network architectures with the same functional space but parameterized differently. Examples include linear networks with skip connections, or convolutional linear networks. In this
This means that the algehraic equations corresponding to the vanishing of the differential have exactly 39 complex solutions.
8

---

Published as a conference paper at ICLR 2020
subsection, take a look at model for normalized linear networks: these maps of the form
WA-1
W1 [W 2, 8 (Wn....,
( x)) Wh
(6)
where W; E RRd:xd-- as before. This is a simple model for different types of weight normalization schemes often used in practice. It is easy to see that the difference between (6) and our previous linear network lies only in the parameterization of linear maps, since for normalized networks the matrix multiplication map is replaced by
WA-1 (W W...... Wi) + W Wh IW,
W1
Va : - ddd
[
where = [(W,, ...,..... Wi) W; + 0, 1,..., 13 C Rd. According to our definitions, L = Eotil and L' lova are losses respectively for linear networks and normalized linear networks, then the pure critical loci of L and L' will correspond to each other (since these only depend on the functional space), but priori the spurious critical loci induced by the two parameterizations may be different. this particular setting, however, we show that this is not the case: the new paramerization effectively does not introduce different critical points, and in fact makes the critical locus slightly smaller.
Proposition 14. I' = l a and L = l pd. then the critical locus Crit(L') is in "correspon- dence" " with Cr) n St meaning that
(ual0') 10' CCrilL))) (ma(0) Cril(L)
4 CONCLUSIONS
We have introduced the notions of pure and spurious critical points as general tools for a geomet- ric investigation of the landscape of neural networks. In particular, they provide a basic language for describing the interplay between convex loss function and an overparameterizee, non-comvex functional space. In this paper. we have focused on the landscape of linear networks. This simple model useful for illustrating our geometric perspective, but also exhibits several interesting (and surprisingly subtle) features. For example, the absence of non-global minima in the loss landscape rather general property when the architecture is "filling", while in the mnn-fillingg setting special property that holds for the quadratic loss. Furthermore, we have observed that even in this simple framework global minima can have (possibly exponentially) many disconnected components.
In the future, we hope to extend our analysis to different network models. For example, we can use our framework to study networks with polynomial activations (Kileel et al., 2019), which are a direct generalization of the linear model. We expect that analysis of pure and spurious critical points in this context can be used to address a conjecture in Venturi et al. (2018) regarding the gap between "upper" and "lower" dimensions in functional space. A geometric investigation of networks with smooth non-polynomial activations is also possible; in that setting, the parameter space and the functional space are usually of the same dimension (i.e., de dim(Ma.)), however there is still an interesting stratification of singular loci, as explained for example in (Amaril 2016), Section 12.2.2). General "discriminant hypersurfaces" can also be used to describe qualitative changes in the landscape as the data distribution varies. Finally, extending our analysis to networks with ReLU activations will require some care because of the non-differentiable setting. On the other hand, is clear that ReLU networks behave linear networks when restricted to appropriate regions of input space: this suggests that our study of ranks differentials may be a useful building block for pursuing in this important direction.
Acknowledgements. We thank James Mathews for many helpful discussions in the beginning of this project. We are gratuful ICERM (NSF DMS-1439786 and the Simons Foundation grant 507536) for the hospitality during the academic year 201 2018/2019 where many ideas for this project were developed. MT and JB were partially supported by the Alfred P. Sloan Foundation. NSF RI- 1816753, NSF CAREER CIF 1845360, and Samsung Electronics. KK was partially supported by the Knut and Alice Wallenbergs Foundation within their WASP AI/Math initiative.

---

Published as a conference paper at ICLR 2020
REFERENCES
Shun-ichi Amari. Information Geometry and Its Applications, volume 194 of Applied Mathematical
Sciences. Springer Japan, Tokyo, 2016. ISBN 978-4-43--55977-1 978-4-431-55978-8 doi:
010007/978-4441-555579
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. convergence analysis of gradient descent for deep linear neural networks. arXiv preprint arXiv/8810002281, 2018.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. arXiv preprint arXiv:190..3666 2019.
Bubacarr Bah, Holger Rauhut, Ulrich Terstiege, and Michael Westdickenberg. Learning deep linear neural networks: Riemannian gradient flows and convergence to global minimizers. arXiv:1910.05505 [cs, mathJ, November 2019.
Pierre Baldi and Kurt Hornik. Neural networks and principal component analysis: Learning from examples without local minima. Neural Networks, 2(1):53-58, January 1989. ISSN 08936080.
doi: 1010016/8993-0000099999001
Lenaic Chizat and Francis Bach. On the Global Convergence of Gradient Descent for Over- parameterized Models using Optimal Transport. arXiv; 1805.000009954 09545 [cs, math, stat], May 2018.
Anna Choromanska, Mikael Henaff, Michaël Mathieu, Gérard Ben Arous, and Yann LeCun. The Loss Surfaces of Multilayer Networks. In Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2015, San Diego, California, USA, May 9-12, 2015, 2015.
Jan Draisma and Emil Horobet. The average number of critical rank-one approximations tensor. 1408. [math], August 2014.
Jan Draisma, Emil Horobet, Giorgio Ottaviani, Bernd Sturnfels, and Rekha R. Thomas. The Eu- clidean distance degree of an algebraic variety. arXiv:/309.004 [math], August 2013.
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry Vetrov, and Andrew Gordon Wilson. Loss Surfaces, Mode Connectivity, and Fast Ensembling of DNNs. /802. [cs, stat), October 2018.
Daniel R. Grayson and Michael E. Stillman. Macaulay2, a software system for research algebraic geometry. Available at httht:::/www.... hwtp:///w/ww.t..././///mmmam uiuc. www.eaeaulaal2.... 2019.
Moritz Hardt and Tengyu Ma. Identity Matters in Deep Learning. arXiv:1611.0423) [cs, stat], November 2016.
Joe Harris. Algebraic Geometry: First Course. Number 133 in Graduate Texts in Mathematics. Springer, New York, corr. 3rd print edition, 1995. ISBN 978-0-387-97716-4,
Hamza Jaffali and Luke Oeding. Learning algebraic models of quantum entanglement. arXiv preprint arXiv:1908. 10247, 2019.
Kenji Kawaguchi. Deep Learning without Poor Local Minima. CoRR, abs/1605... 10s//6055.01110 10, 2016.
Joe Kileel, Matthew Trager, and Joan Bruna. On the expressive power of deep polynomial neural networks. arXiv preprint 1905v 12207, 2019.
Thomas Laurent and James von Brecht. Deep linear neural networks with arbitrary loss: All local minima are global. 172.4:171 [cs, stat), December 2017.
John M. Lee. Introduction to Smooth Manifolds. Number 218 in Graduate Texts in Mathematics. Springer, New York, 2003. ISBN 978-0-387-95495.5 978-0-387-95448-4
Haihao Lu and Kenji Kawaguchi. Depth Creates No Bad Local Minima. arXiv: [cs, math, stat), February 2017.
10

---

Published as a conference paper at ICLR 2020
Dhagash Mehta, Tianran Chen, Tingting Tang, and Jonathan D. Hauenstein. The loss surface of
deep linear networks viewed through the algebraic geometry lens. arXiv:1810.07716, 2018. URL
http://arxiv org/ /tt.s//111.0021.1
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A Mean Field View of the Landscape of Two-Layers Neural Networks. arXiv:1804.0653 [cond-mat, stat), April 2018.
Giorgio Ottaviani, Pierre-Jean Spaeniehauer, and Bemn Sturmfels. Exact Solutions in Structured Low-Rank Approximation. arXiv:1311.2376 [cs, math, stat]. November 2013.
Luca Venturi, Afonso S Bandcira, 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.
arXiv preprint arXiv: 1.XXiv/707.0000 0.04444, 2017.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small nonlinearities in activation functions create bad local minima in neural networks. arXiv preprint arXiv: 0802003887..... 2018.
Li Zhang. Depth creates no more spurious local minima. arXiv preprint
2019. Yi Zhou and Yingbin Liang. Critical Points of Neural Networks: Analytical Forms and Landscape Properties. 17Xiv:1710.111 1205 [es, stat], October 2017.
A APPENDIX
A.1 DETERMINANTAL VARIETIES
We present some additional properties of determinantal varieties. For proofs and more details, we refer the reader to Harris 1995). Given < min(m, n), the r-th determinantal variety M, C mR defined as the set of matrices with rank at most r:
M, (P RR
rk(P) sr) Rm
As mentioned in the main part of the paper, M,, is an algebraic variety of dimension r(m + n r), that can be described as the zero-set of all (r + 1) x (r + 1) minors. For r > O, the the singular locus of M, is exactly M,-1 C M,. Some of our proofs will rely on the following explicit characterization of tangent space of determinantal varieties: given a a matrix P E R of rank exactly (so P is smooth point M,) we have that
TpM, = R @ Row(P) + Col & R C R
We will also make use of the normal space to the tangent space TpM, at P. with respect to the Frobenius inner product. This is given by
(TpM,)* = Co)(P)) LP)
where (P) and Row (P)(P) are the orthogonal spaces to Col(P) and Row(P), respectively.
A.2 EUCLIDEAN DISTANCE DEGREES AND DISCRIMINANTS
In this section, we informally discuss some algebraic notions related to ED (Euclidean distance) degrees and discriminants. A detailed presentation can be found in Draisma et al. (2013). Given an algebraic variety V с 1. and a point u E R", the number of real critical points of the distance function (p) = 1pp ul|2 restricted to only locally constant as varies. In general, the behavior changes when u crosses the caustic hypersurface, or ED (Euclidean distance) discriminant, of V. The ED discriminant can be defined over the complex numbers, and this setting it is indeed always a hypersurface (i.e., it has codimension one), however it can have higher codimension over the real numbers. For instance, for a circle in the complex plane with the origin as its center, a point (ui, U2) C² is the ED discriminant if and only if u + uz 0. This defines curve in the complex plane whose real locus a point (see right side of Figure 2) By the Eckart- Young Theorem
(Theorem 12), the ED discriminant of the determinantal variety M, is the locus of all matrices Qo

---

Published as a conference paper at ICLR 2020
with at least two coinciding singular values, so it is defined by the discriminant of QoQ8 As in the case of the circle, the ED discriminant of M, has codimension two in R4, xd.
Over the complex numbers, the number of critical points of the distance function h, restricted to V is actually the same for every point u E C not on the ED discriminant of V. This quantity is known as the ED degree of the variety V. For instance, a circle has ED degree two whereas ellipse has ED degree four (on the left side of Figure points u outside of the caustic curve yield two real critical points and two imaginary critical points). The Eickart-Young Theorem (Theorem 12 tells us that the ED degree of the deterninantal variety Mr C R24xxd is (*)) where m min dz. dy). As argued in the main part of the paper. this does not hold any longer after perturbing either the determinantal variety or the Euclidean distance slightly. even using only linear change of coordinates. For an algebraic variety V C C", linear change of coordinates is given by an automorphism yp C -> C² For almost all such automorphisms (i.e. for all except those lying in some subvariety of GI(n,, C)) the ED degree of ((V) the same; see Theorem 5.4 in Draisma et al. (2013). This quantity is known the general ED degree of V. For instance, almost all linear coordinate changes will deform a circle into an ellipse, such that the general ED degree of the circle is four.
In the above definition of the general ED degree, we fixed the standard Euclidean distance and per- turbed the variety. Alternatively, we can fix the variety and change the standard Euclidean distance dist. u)² from u satisfies
|| to dist.p [|)(())]. The new distance function h. het (pp(p) = ((n) (p(p)) = (p). Hence, the ED degree of (VV) with respect to the stan- dard Euclidean distance distia = -I equals the ED degree of V with respect to the perturbed Euclidean distance dist.p In particular, the general ED degree of V can be obtained by comput- ing the ED degree after applying a sufficiently random linear change of coordinates on either the Euclidean distance or the variety V itself.
As in the case of a cirele, the general ED degree of the determinantal variety M, is not equal to the ED degree of M,, Furthermore, there is known closed formula for the general ED degree of M, only involving the parameters dz dy and r. In the special case of rank-one matrices, one can derive a closed expression from the Gatanese-Trifogl formula (Theorem 7.8 in Draisma et al. (2013): the general ED degree of Mi is
du+dy
(1et))
(-1))(24+td,t1-2 1)(dz + dy - s)!
Σ itj=s iSdei J.dd
(dz i)y - j)!
This expression yields 39 for d₂ d,y = 3, as mentioned in Example 13 for the general ED degree of M, involving Chern and polar classes can be found in Ottaviani et al.) (2013): Draisma et al. (203). A short algorithm to compute the general ED degree of M, is given in Example 7.11 of Draisma et al. (2013); it uses package for advanced intersection theory in the algebro-geometric software aocculay? (Grayson & Stillman 2019).
For general r, formulas
This discussion shows that the Eckart- Eckart-Young Theorem is indeed very special. The intrinsic reason for this is that the determinantal variety M, intersects the "isotropic quadric" associated with the standard Euclidean distance (i.e., zero locus of X2,1 +... + X3 dg,d, in (dy) in particular way (i.e., non-transe non-transversel).. Performing random linear change of coordinates on either M, or the isotropic quadric makes the intersection transverse. So the ED degree after the linear change of coordinates is the general ED degree of Mr, and the Fckart-Young Theorem does not apply.
In summary, we have observed that the degeneration from an ellipse to a circle is analogous to the degeneration from determinantal variety with a perturbed Euclidean distance to the determinantal variety with the standard Euclidean distance: in both cases, the ED degree drops because the situa- tion becomes degenerate. Moreover, the ED discriminant drops dimension, which causes the special phenomenon that the number of real critical points is almost everywhere the same.
Experiment 1. In general, it is very difficult to describe the open regions in R. that are separated by the ED discriminant of a variety V/ C R". Finding the "typical" number of real critical points for the distance function h, restricted to V. requires the computation of the volumes of these open regions. In the current state of the art in real algebraic geometry. this is only possible for very particular varieties V. For these reasons, and to get more insights on the typical number of real critical points of determinantal varieties with perturbed Euclidean distance, we performed computational exper- iments with Ma Macuula 2y2 (Grayson & Stillman 2019) in the situation of Example 13 We fixed the
12

---

Published as a conference paper at ICLR 2020
Table 2: Number of critical points (columns) and number of minima (rows) in experiments
#(critical points)
1
3
5
9
11
13
0
476
120
0
0
0
#(local minima)
2
0
0
805
190
10
0
0
0
0
228
116
21
4
0
0
0
16
12
5
determinantal variety Mi C R3x3 of rank-one (3 x 3)-matrices. In each iteration of the experi- ment, we picked random automorphism o R333 -> 3x3 and random matrix Qo R We first verified that the number of complex critical points of the perturbed quadratic distance function he.Q0 restricted
M₁ the expected number 39. After that, we computed the number of real critical points and the number of local minima among them. Our results for 2000 iterations can be found in Table 2 and Figure 3 Although this a very rudimentary experiment in an extremely simple setting, it provides clear evidence that the number of local minima of the perturbed distance function is generally not one.
We note that computations of real critical points and local minima involved numerical methods and might thus be affected by numerical errors. In our implementation used several basic tests rule numerically bad iterations, that can report our results with high confidence. The entries of the random matrix Qo are independently and uniformly chosen among the integers Z {-10, - ... : 10). The random automorphism yp given by matrix in zax whose entries are also chosen independently and uniformly at random.
Implementation details:
A.3 PURE AND SPURIOUS CRITICAL POINTS IN PREDICTOR SPACE
We illustrate a variation of our functional setting where the notions pure and spurious can also be naturally applied. We consider training sample I1,--.. E Rds Vı,..., yN E R (for notational simplicity we use dy = 1 but this is not necessary). We then write an empirical risk of the form
L = (f),
where Ý()) - (4(0, x1), ((0,zN) E RN (yI, UNN E R and RR X + R is convex function. As 0 varies, (0) defines "predictor manifold" y c R.W.V which depends only on the input data 21...., N. but not on O. The function (0)) can be naturally seen as a composition
d 2 y 4 IR,
where ry(0) = Y (0) E V. We may now distinguish again between "pure" and "spurious" critical points for L. In underparameterizee regime de N, or if the input data Ti, ri,..., UN is in some way special, then y S RN is a submanifold (with singularities), and critical points may arise because are restricting Y (pure), because of the parameterization map v) (spurious). In a highly overparameterized regime dg >> N (which is usually the case in practice), we expect y R. This can be viewed analogous the "filling" situation described for linear networks in this paper. In particular, all critical points that are not global minima for L are necessarily spurious, since gly g convex.
A.4 PROOF OF THBOREM 4
We first show Lemma 3 with help of the following general observation:
Proposition 15. Let V C Va+ c...
... S V and V1 2 Vg- 2... V, be vector spaces with
dimensions r = (V++) and == dV for = o,..., ,hh Then we have
h
h-1
dim ((V+ & V + (Vt VV + + (V++ 8 vVr) = Σ
rtr Σ
rtrar
im1
13

---

Published as a conference paper at ICLR 2020
Proof. We prove this assertion by induction on h. The base case (h- 1) is clear: dim & V r For the induction step, set V := (V1* @ VTT + +.... ... + (VK=1 @ Vi-)). The key observation is that the inclusions V/* - V/2" - .... S Vi and V 2V3 2 ... 2 Vi imply that
Dn (V/ & Vi² = V s Vi= Hence, applying the induction hypothesis V, we derive
dim (V + (V₂+ & )) dim + dim(V K
@ VVr) dim(V @ V%
1-2
M
Σ
r,t - - r
h-1
Lemma 3. The dimension of the image of the differential dya at = (Wn..... Wi) is given by
rk(dpa(0)) = NA(Ws)).rkWW) Σ
rk(W>.) rk(WW<+Hi) (+)))
==1
where we use the convention that W<1 = Ido. W>h = Idn are the identity matrices of size du da-
Proof. The image of the differential (0) is given in ( Due to
Col(W)& S Col(W>>) C Cool( = Col(WW),
Row S Row( <n) .... S Row(W (22)) = RW1,
we can apply Proposition 15 which concludes the proof.
Now we provide proof for Theorem 4 starting from a refinement of the last statement. Proposition 16. Let r min(d,), 0 (Wn...., W1), W Ha(l), and = rkW. The image of the differential dpa at 0 contains the tangent space M, of M. at W. Furthermore, for every W E Me MM-1 there exists 0' such that pa(00) = W and the image of duaa(")) is exactly Tw-Me.
Proof. Due to 7 the image (5) of dua(l) always contains Ed @ Row(W) + Col(W) & Rdo Tw. Furthermore, there always exists (W,,..., Wi) E p such that each W; has rank exactly and the containments in (7) are all equalities. For example, one way achieve this is to consider any decomposition W = UVT where U E Rd and V Rdoxr and then set
T,
for 2 Siss 1, where I, is the (r x (rxr)-identity matrix and the zeros fill in the dimensions (d4 1 of W,
W1 = = [v= oj"" W,, = [U 0j], and W, =
0
The next two propositions discuss the first part of Theorem 4 which distinguishes between the filling and the non-filling case.
Proposition 17. Let r = min(d; ] and 0 = (Wh...,, W1). In the non-filling case (i.c., if < min (da, d we have that (k)))a(0)) < dim M, if and only if (k((pa(()) < r.
Proof. If (O))
then Proposition 16 implies that the image of the differential dua(() is the whole tangent space of M, at (f) To prove the other direction of the assertion, we assume that
rk)) < Since min (dr, ) there is some ie E {1...., h 1} such that d, We view Pa as the following concatenation of the matrix multiplication maps:
(8) where P4.1 P(dy.....d M(d......oo) and μ4.2 didd,d Since rk(Ha(0)) < we have that
du .... x 1d xd M pdaxd; xd, dd P:3 pduxdo
rk(W>,. );) < r or rk(W < r. Without loss of generality, we may assume the latter. So applying Lemma to n4,2 and 06 = p4,1 (0) yields
rk(dua(()) < rk rk(dpu,, = rk((W 1) (dn - rk(W rk(W
< r (d,, - rk(W,.)) + rk(W = rk(W,,) (do r) + r dn.
(do r) rd, dim (Mr).
14

---

Published as a conference paper at ICLR 2020
Proposition 18. Let = minfd;} and 0 (Wh...., W1). In the filling case (i.e., if min(dh, H we have that rk(d)a(0)) < dndo if and only if there is some i E fl....,h with rk( (i)) d, and rk(W ci+1) do-
Proof. Let us first assume that rkss).) < dn and rk (WWc++1) < do for some E (l,...,h, We view pa as the concatenation of the matrix multiplication maps in (8). Applying Lemma g to 24,2 and 0' = (0) yields
rk(dua(O)) rk(duu,,(0') = rk(W ci+1) (dn - rk(W + rk(Ws:)do < do (dn, rk(W rk( dj.do
Secondly, we assume the contrary, ie., that every i E (1.....h h - }} satisfies rk(W>i) = dn or ik(W<e+1) dg. We observe the following 2 key properties which hold for all f1....,h 1}:
rk( = dn =
Vj 2 i: rk( = dh
(9)
rk(Wei+1) do + Vj rk(W <j+1) do-
We consider the index set I = fie (1.....h h 1) rk(WW<it <i+1) dol. If 0, our assumption implies that rk( = dú for every E E(1, [l,...,, So due to Lemma we have
h1.
rk(dja((0) dn Σ rk(Wei) cx) dn Σ
rk(W <-- d, d,rk(W<1)) dddo-
I + 0, we define t: == max I. So for every E + II.,,.,,, h we have (k(We4+) < do. and thus rk(Ws.) dy by our assumption. Moreover, due to (9). every j E {O....,k) .k satisfies rk(W>)+1) = dg. Hence, 3
rk(d)a((0) Σ rk(W + do +
Σ dnrk(Wes)
2m242
h-1
Σ
rk(W>))dd
Σ
dark(W<sti)) = d/
1mk+1
Example 19. According to Proposition the differential of the matrix multiplication map sur- jective whenever rk(W) = but also for certain 0 when rk(W) r. For example, let us con- sider the map (22,2.2)
R222 x R2x2 > R2x2 and the two factorizations and 0' [[] 01 [d ul) of the rank-one matrix [] According Proposition [8| the differen- tial 2.22) ()) has maximal rank 4. So it is surjective, whereas 222 (f') is not. In fact, by
([1 []] 1 ?
Lemma we have rk(d(((22222) (f')) 3.
Theorem 4. Lerr = min(d.). = (Wn...., W1), and W = (a(().
(Filling case) If r = min (dn, do}, the differential dua(l) has maximal rank equal to dim M, = dg if and only if. for every E (1,2,..., 1}, either rk(W>.) dr. rk(W dg holds.
(Non-filling case) I < min min(dr, do). the differential (0) has maximal rank equal to dim M, = r(d, + dg - r) if and only if rW) =r.
Furthermore, in both situations, rkW = < then the image of dpa(l) always contains the tangent space Mw of M C M, at W.
Proof.
This is an amalgamation of Propositions 16 and
A.5 PROOF OF THROREM S
In the following the notation from Theorem
5
15

---

Published as a conference paper at ICLR 2020
Theorem 3. Letr min(d:). If Ifr = then the set of d-factorizations Hd (W) of W has exactly 2 path-connected components, where # d r; < h). (W) then
Ma (W) is always path-connected
We also write GL* (rr for the set of matrices in GL(r) with positive determinant. Analogously, we set GL (r) = {G e GL(()) det(G) < 0).
We first prove Theorem in the case that b case, we show the following stronger assertion: given two matrices W and W of arbitrary rank and factorizations E !'d (W) and 0' E Ue (W"), each path in the codomain of pa from W to W can be lifted to a path in the domain of jia from 9 to f'.
To show that v (W) path-connected in this
Proposition 20 (Path Lifting Property). b= = O, then for every W, W E R4,xd, every 0 E 1d2 (W), every 0' E pda (W") and every continuous function f [0 + Rdyxds with f(0) = W and f(1) W there is a continuous function F: :1-1,2] + R2, X ... x Rdixd, such that W' for every / E [1
F(-1) = 0, (2) = 0', (a(F(()) W for every / E [-1,0), (a(F(()))))))) W and pa (()) = [() for every L [0,
Proof. Without loss of generality, we may assume that dy S dg. Then the assumption b = means that d, > dy for all = ...... 1.
We prove the assertion by induction on h. For the induction beginning, we consider the cases = and h = 2. If / 1, then Md is the identity and Proposition 20 is trivial. For ht 2, we construct explicit lifts of the given paths. We first show that there is a path in Pd (W) from f = (W2, Wi) to some (B2, B1) such that B2 has full rank.
2, W E Rdd, Xds and (W2, Wi) E Ma (W). Then there is (B2, E Mu (W) with rk (B2) dy and a continuous function g [0, 1] + Ma (W) such that g(0) = (W2, W1 and g(1) = (B2, B1).
Claim Let
Proof. If rk())) = dy. we have nothing to show. So we assume that : rk(W2) < dy Without loss of generality, we may further assume that the first s rows of W2 have rank 8. As 8 < d1, we find
=[ 0. where L. E xx is the identity matrix and M e Rddy-s)xx Since GL (d:) is path-connected, there is continuous function gi [0, + GL + (dz) with gf (0) Ia, and gí (1) = G. Concatenation with GL(dd) + Ha (W). H + (W,H, WW)
matrix G GL (d1) such that W2G = [
yields a continuous path 9i Ma (W) from (W2, W1) to (W2G, W-)
Since (W2)) W1) W. we see that G- = |'*>> where W(s) E Raxd2 is the first s rows of W and N E (dd,-s)x Replacing N by an arbitrary matrix N' still yields that W. Hence, we find continuous path 92 in p (W) from (W2G, WT) to (W2G, B = W
[
W&G W N'
Finally, we can replace the 0-columns in W2G by arbitrary matrices M2 E R and M2 E ()d,-s)x((1-2 such that
B1 = W still holds. In particular, we can pick M1 = 0 and 0 has full rank dy. and find continuous path ga in M2 [ay- o] such that B2 = JM Ma
1, Mj
M M2
Me 1 (W) from (W2G, B1) to (B2, B1). Putting 91, 92 and g3 together yields a path as desired in Claim I
As B2 has full rank, we find matrix H E Gd+) such that B2H [Ia, 0). As in the proof of Claim 1 we construct continuous path in pa (W) from (B2, B1) to (B,H, - B1)- Since - B, [1 for some N e R(d xx) we also find continuous path in Na (W) [W from (B2H, H B1) to (B2H, (W1) I). All in all, we have constructed a continuous path F1 in
pd (W) from (W2, W1) (1,, 0] [ 1. (... Analogously, we find a continuous path F3 in p. (W') between (WZ, W() and (L o], W" }). Finally, we define F2 [0, 1] + xd 1d xd,
t t+ ([L,, 0]. [(O]] such that putting Fi, F2 and F3 together yields a path F as desired in Propo- sition 20
16

---

Published as a conference paper at ICLR 2020
For the induction step, view pa as the concatenation of the following two matrix multiplication maps:
Rdy xd x .... x Rdd Xds (o xid
Rdyxd x Rddddd
xd, Midyydayd Rdyxd.
Wf). as well as W>1 Wh. W2 and W W/ ... W.z Given path f: [0, 1] + Rd xd= from W W> W W = W Wi, we apply the induction beginning (h- 2) to d.,,) to get a path F2 [-0.5, 1.5] + 12 x R xd, such that F2(-0.5) = (W>1, W1), (2.5) (W2)1 W1D. dd.) ((2 (t)) = W for all f E [-0.5, 0], ((d,
We consider 0 (W,, h..... W1) and 6' (W)
(F2 d.)
= W" for all E [.5] and pidd, di d, d,), (P2(() - (() for all l [0, 1]. Now we apply the induction hypothesis on ((d).....d11) and the path from W>1 to W given by the first factor of F2. This yields a path F1 : 1, 2] + RR xdx-1 X... x Rdxx with (i(-1)
(W..... W2), d.)
(2) (W,,... h.... W2), ((da.....dd))) d,) (4)) W forall E [-1, d.) (Pi(())= W
for all t E [1.5, 2] and (() (Fi (t)) is the first factor of (t) for all t E [-0.5, 1.5]. This
R Xdh-1 X ... x R add from 0 to H by setting F F(t) = (Fi (t). W1) for all t E 1-1.-0.5 F(t) = (Fi (t), W7) for all t E [1.5, 2| and for
allows us to define a continuous path F [122]
all t [-1, 00.5] we let F(t) consist of (t) and the second factor of (t).).
Corollary 21. If b O, then Fa (W) is path-connected for each W E R4xd,
Proof. Apply Proposition 20 to the constant function f + Rd, Xdz t W.
Now we study the case b > 0. We write 0 < i < < is < h for those indices i; such that d, r. Then view Me as the concatenation of the following two matrix multiplication maps:
Rd,xdn= X ... x xddx Mi, pd, Rd Xd X Rdd, xdz H2g Rd xdz
(10)
Mid, and μ2 - P(dy. ... di dal- Applying the path lifting property described above to the map ft, will show in Proposition 26 that uo (W) and pd (W) have the same number of (path-)connected components. So it remains to study the connected components of p22" (W). We can shortly write the map #2 as
where 11 Pids.....d X
Hg : Rr xr (ReX)) b-1 x R
Rdyxds
In the case that rk(W) r, we use the following natural action of GL(r)* on 11 (W):
GL(r)* x uz (W) - u2 (W), GG.. G1), (Abt1,..., A1)) - (As+ Go. G. A,G G A1)
(11)
In fact, we show now that 21 (W) is the orbit of any element under this action if rw( = r. From
this we will deduce in Corollaries 23 and 24 that uzz (W) homeomorphic to GI.(r)* and thus has 2 (path-)connese conneeced components if the matrix W has maximal rank r.
Proposition 22. Let b O and 0 (Ab41,...,,A) At) E Rd, x (Rexryh-1 x Rrxd, such that
-1 W (0) has maximal rank Then p2 (W) is the orbit of 0 under the action defined in ie.,
M2 (w) = (Ab+ A A.Goo.......C .T
GI...., G. (GG()))
Proof. One inclusion, namely "2", , is trivial. We prove the other inclusion "C" by induction on b. For the induction beginning (b = 1), we write W = [Wai Waa generality, we may assume that rWWn))
Waa where Wn E Rrxr, Without loss of
Similarly, we write A2
and A = [AA A12 Aaz
Azi
where Ag R for i 1,2. For (A2, A1) 1,, (W), write analogously A/2 A/n
A'
and A/ [4 ]. Due to rk(W11) r, we have that rk(A21) = rk(A2)). Hence, there is a matrix G E GL(r) such that A/ = An1 G. This implics that A₂i GA = Wn = A An,
so A/ = G-1 Due to Az = W12 A we get that 1 G-1 A Finally,
17

---

Published as a conference paper at ICLR 2020
rk(Wi1) = implies that rk(A11) r, A22A11 W21 -A2 A11 shows A42 A22G. Thus we have shown that A2 = A2G and Ai = =G -G-AA1 A1.
For the induction step (b > 1), we consider (Ap+1 A1)
E (2) and As1 Ab+1. ... A2, A4,11 = Ab+1 ... A2 E Rdyxr, Now we can apply the induction beginning to find G1 E GL(r) such that A'21 As1G1 and Ai GT As A's has rank and Ab41 '.-A2 = =A'1 = Ab+1 (A2G1), we can apply the induction hypothesis on the map which multiplies the left-most matrices, This yields Gb,... G2 E GL(r) such that A/41
A/ G3 AgG2, A/2 G5 (A2G1)
Corollary 23. If b > and W xgdyxd= has maximal rank r, then ptz 1 (W) homeomorphic to GL(r)*.
Proof. We fix 0- = (Ab+1 A1) E 15 (W). The map GL(r)* + kr'(WW (W) given by the action III on 0 is continuous. We now construct its inverse. As rk(W) = we have that rk(A,)
r for all i b,..., 1. Without loss of generality, we may assume that the first rows of A&+1 have rank r. We write æ Rd + Rex for the projection which for- gets the last dy
E P2 (W), Proposi- tion 22 shows that O' ((G....., G1) for some (Gb,..., G1) E GL(r)'. So we have that Ga T (Ab+1) - T (4/ Gb-1
rows of a given matrix. For 6' = -4p+1 (A/+1....,
AB A5 GrAp Gi A2 G2A2 which defines map
vi 12 1 (W) - GL(r),
(Ab+1..... Ai) - (G(Ab+1); G A, A A ..2))))))))))
where 1(44+1) == (Abb-1)--TAA,, By construction, & is the inverse of p. Since & is contin- uous, it is a homeomorphism between μzz (W) and GL(()).
Corollary 24. If 0 and W E
xdyxdz has maximal rank r, then piy (W) has 2 connected components, Each of these components is path-connected.
Proof. The group GL(r) has two connected components, namely GL (r) and GL (r). Both com- ponents are path-connected. Hence, GL(r)' has 2 connected components, each of them path- connected. By Corollary 23 the same holds for p1, (W).
To complete our understanding of the connected components of μ12" 1 (W), we consider the case that the matrix W E xd, does not have maximal rank r. In that case, it turns out that μ1 ((W) is path- connected, which we show by constructing explicit paths between any two elements of p5 (W).
Proposition 25. Let W E Rd,,d, If 0 and rk(W) then p5 (W) is path-commected.
Proof. We write W =
W. W.
where W E Rrxd, and denote by e the rank of W. If Ifrk(W,) = e,
then W₂ = MW for some M E (R -r)xr_
Claim 2. If b 1, (A2, A1) E u2 (W), rk(W,) = e and W. MW, 1. then there is a continuous function ʃ [0, 1] + 1z (W) with f(0)- = (A2, and f(1) = ([h, W.).
Proof. Since rk rk) r. we have that rk(A2) < or rk(A) < r. If rk(A2) r, we proceed as in the proof of Claim to find path in paz (W) from (A2, A1) to (A/, A1) such that rk(A))
This implies that rk rk(Ai) = e. So K = ker(A]] (Af())) C R We write Ag A where A21 E Rr and denote by r2 the rank of Ag1. So the rowspace R C IR' of Ag1 has dimension T2. We now show that K + R = Rr. To may assume that the first rows of
Hence, we may assume that rk(A2)
has positive dimension
this set == dim K R). Without loss of generality, W, are linearly independent. Then the first rows of A21 must also be linearly independent, might further assume that the first r2 rows of AgI are linearly independent. We denote by Agn and Wi, the matrices formed by the first r2 rows of A2i and Wi, respectively. In particular, we have
18

---

Published as a conference paper at ICLR 2020
that A211A1 W11- 11. Now choose basis (bı...., .,,)) for R such that (b)... (b1...., ......,,b). is a basis for K n R. Since R is the rowspace of A211, there is some G E GL(r2) such that the i-th row of GA221 is by So the first å rows of GW 11 = G1211A1 are zero, which shows that e = rk(GW 11) S r2 - 6.
Thus, dim(K + R) = (r e) r2 6 2 r, which proves that K + R R".
If 12 <
we now show that there is a path in M2 (W) from (A2,A1) to (A =
A A1)
A2a
such that (4)1) = r. We may assume again that the first 12 rows .1,-..,, Org of A21 are linearly independent, i.e., that they form basis for R. Since K+R = R", we can extend this basis to basis (a)...., a,) for IK" such that a, E K for all i > 72. We define AWi1 such that its first r2 rows are a1...... ar and such that its i-th row, for r2 <is r, is the sum of ag E K and the i-th row of A21- Then A/- A% satisfies A² W. Moreover, the straight line from (Az, A1) to (AZ, A1) is A2a
path in Mb (W). Since the last r - r2 rows of A21 are contained in the linear span of the first 72 rows of 221, the linearity of the determinant implies that deu(A del(( a. + 0.
Thus, we may assume that 12 = r. If (et( < O, we now construct a path in 22 (W) from (A2, A1) to (A%' = Ag
A2a .A1) such that det(A") > O. For this, we pick a vector o E K \ {0}-
Since the rows of A21 form a basis for I², there is an index i E {I....,r) such that the matrix D E grxr obtained from A21 by replacing its i-th row with v has full rank. We pick μ E E such that (A2) + μ det(() D) > 0 and define A3i to be the matrix obtained from A21 by adding pe to its i-th row. Then det(AW) (ct((A2) + det D) > O and A/"
<55 satisfies AW A1 = W.
A2a
Moreover, the straight line from (A2, A1) to (AK" A1) is a path in μ12 (W).
Therefore, we may assume that det (A21) > 0, so G == Agi E Gr) Any path in GL+((r) (r) from 4, to G yields path in pz (W) from A1) to (AgG, A1) = A[1g W1). Since (Ang))W1 W₂ = MW1, 1, the straight line from (1 ([ W1) to ([hr] W1) is a path in 1 (W).
Claim 3. If 8 (Ab+1,..., A1) E 15 (W), rk(W1) = and W2 = MW 1, then there is a continuous function F: [0, 1] + 122 ( with F(O)- = 0 and F(1) = [[1r]] II...... L, WT).
Proof: Ase e < r, at least one of the A, has rank smaller than r. We k: == minfi E (1,.... b 1) rk(A.) < r.. k < b + 1, we first show that there is path in μz (W) from @ to (A/+1 A() such that minfi E {l....,b b + 1} rk(A) < r} = b + 1. Since rk(AA) < r, the rank of W' = A&+1 As is smaller than r. We write W' W: W: where W', has r columns. Without loss of generality, we may assume that rk(w)) = rk(W)) Then there is a matrix N such that W² W,N. Hence, we can apply the transposed version of Claim 2 which yields a path from (Ax+1, Au) to (W', 1, [ N x) in the set of factorizations W', Defining AR+1 := W1, As == [1. N) and A := A, for all i E {l....,b b + 13 (k, k + 1}. extends this path to a path in 22 (W) from 0 to (As+1,..., Åi) such that minfi E {l....,d b + 13 rk(Á.) < r k + 1. We note that this construction increased the number kt So we can repeat the construction until we reach (Ab.)...., A1) as desired.
Hence, we may assume that & = + 1. Since rk(A)+1) < r. the rank of W" = Ab+1 is W smaller than r. We write W" = W
where W" has r rows. Since W, 1 = W" A ... A1
and the matrices A6-1...., An have rank r, we have that rk(w)) = rk ( = e. Analogously, rk(W") = e. So there is matrix M' such that W" = MWW". 1. Applying Claim 2 yields a path from (Ab+1,Ab) to (1 fr W") in the set of factorizations of W". Thii path can be extended to
path in p.z (WW) from 0 to 0r := ([ fr wW", Ab-1,..., A1). Applying the same construction on W" = W" yields a path in M22 (W) from 0' to 0" := ([ [r Ir. W' "A.
We
repeat the contruction until ([trr] ] Jr..... Jr, W1) is reached. Since MW, = W, = =MW, 1. the straight line from ([ /. I Try.... Tr, Wn) ([ [r] Ir...., . Ir W1) is path in 112" (W).
19

---

Published as a conference paper at ICLR 2020
Now finally show that M22 (W) is path-connected. Without loss of generality, may assume that rk(W.) e, and we write We MW1. For 0,0' f2 (W), there are paths in Hz (W) from I resp. I' to (1 Ar : .r...... I, W1), so there is a path from @ to 0' in H1 (W).
To settle the proof of Theorem it is left to show that μ 1 (W) and Ma (W) have indeed the same number of (path-)connecteed components, as we promised earlier.
Proposition 26. Let b 0 and W Rdyxds, Then Ha (W) and μa (W) have the same number of connected components. Moreover, each of these components is path-connected.
Proof. Let us denote the connected components of (W) be CI,...,Ck: By Corollary 24 and Proposition 25 each of these components is path-connected. Using the notation in (10) we have
that 1dd (W) U (i (C:). Since the (CI) (C PI (Ck) are pairwise disconnected, see that Ma (W) has least disconnected components. It is left to show that each /T (C;) is path-connected. For this, let 0,0' E PT (C:)
(C:) and o == |1 (0), == (1") E C.. As C. is
path-connected,, there is a path in C; from a to a'. The map /un is direct product of b + matrix
multiplication maps. To each factor we can apply Proposition 20 which yields path in Pi (C.) from / to 0'
O
Corollary 27. Let b > O and W E Rd,xd=, If rk) then Pd (W) has 2 connected
components, and each of these components is path-connected. If rk(W) T, then Pa (W) is path-comnected.
Proof. Combine Corollary 24 and Propositions 25 and 26
Proof of Theorem
Theorem 5 is an amalgamation of Corollaries 21 and 27
A.6 PROOFS OF PROPOSITIONS 6
10 AND 14
Proposition 6. If is such that ()a(() has maximal rank (see Theorem Fy. then 0 E Crit(L) if and only if WW& E (r.)) and 0 is a minimum ( (resp., saddle, maximum for L. if and only if is minimum (resp., saddle, maximum) for E. rk(() = (which implies that (pa has maximal rank) and 0 E Crit(L), then all d-factorizations of W also belong to Crit(L).
Proof. If pa is local submersion at 0 onto MM. then there exists open neighborhood U of W in M, and an open neighborhood V of B with the property that μa acts as a projection from V onto U (see, e.g., (Lee) 2003] Theorem 7.3)). From this,
easily deduce that 0 is minimum (resp- saddle, maximum) for I. and only if W = (a(()) is a minimum (resp. saddle, maximum) for ( Finally, if rk(W)- = r, then df)( has maximal rank for all A E uaa (W) by Theorem 4
Proposition 7. If 0 E Crit(L) with rk(W) e S r, then W Crit((lm.). In other words, if rk(W) r. then 0 Crit(L) implies that W is critical point for the restriction of to smaller determinantal variety Me (which is in the singular locus of the functional space Mr in the non-filling case).
Proof. According to Theorem 4 if (0) = W with rk(W) e, then Im(dua(O)) 5 Tw-Me- This means that 0 E Crit(L) implies that W is critical for El...
Let E Cril(L) be such that rk(W) < r, and assume that de(W) + O. Then, for any neighborhood of 0, there exists 6' in U such that pa(0') = W but 0' & Crit(T). In particular, 0 is a saddle point.
Proposition
Proof. Our proof is a modification of an argument used in Zhang 2019). Let us first consider the case that pa is filling, so r min min, do Without loss of generality, we assume dg. Recall that the image of dfa((f) is given by
dd 30 Row(W <h) + ....+ Col(W so Rono(We) +... Col(W>)) to Rdo
20

---

Published as a conference paper at ICLR 2020
We first note that Row (We) * Rd for otherwise dua(O) would be surjective, implying that dl( O. We define i max (Row(W>)) [. so 1 S i < h (writing W<1 ld.). We have that
de(W)
Row(W<:)) <:)) = de( (W)l @ Rd) 0.
(12)
Since Row(W (i+1)) S Rd, we may find w, Rd,, wi # 0 such that w W =i=0 We now fix > 0 and U/41 E R44 arbitrarily, and define W4+1 WH11 + c(u,11 w)). Clearly, we have that W4+1 W W1 We+1 W.... W1. If (W W411, W....., Wt) is also critical point of L, then
..... W.-1) @ Rd) = =0. 13 we have that
(13)
Combining 122 and
de
(442(1411 00 wx)) @0 RR)) = 0.
If this were true for all 1 then it would imply
(e (Col((CC W.-2) @ )=) =0
(14)
Hence, we have either found an arbitrarily small perturbation 8' of as required in Proposition
or (14) must hold. In the latter case, we reapply the same argument for Wi+2 = W4+2 + c(14+2 X
Wi+1) where Wi+11 # O and w We+1 W1 = O. Again, we can either construct an arbitrarily small perturbation 6' of 0 as required in Proposition 9 0. Proceeding this way eventually arrive at (L) (R @ Rd
have (Col (++)))++)>)))))) @ R
so (W) = O. which
contradicts the hypothesis. Thus, at some point we must find an arbitrarily small perturbation O' of as required in Proposition | which concludes the proof in the case that jla is filling.
We now consider the case that jaa is not filling. We pick E {1....,h 1} such that d, = r. and
write for simplicity A Wa ... W and B = Wi... W1. The assumption rk(W) < r implics
that rk(A) < rk( B)) r, and assume without loss of generality that rk(A) < r. We define
the map LWW,, 1)+ = ((W,,.. "..,...W. 1 B). We also introduce the map E (A') = (A and the matrix multiplication map μdd, where d (dr...., dd,1), so that LB = LB o udd. If is a critical point for L, then Oa- = (Wr..., W;+
must be a critical point for LB. We are thus in the position to apply the analysis carried out in the filling case. In particular, we have that either A can be perturbed A such that pda (0a) Hdd (0x) but 0 & Crit(LB) or (A) = 0. In the former case, we have that 0' = A0 A. B)) is not critical point for L, and we are done. instead dl n (A) = O, then we have that
de de(W)
Row (B)) =0,
because the image of the differential of the map A' + A'B is given by Rdh & Row(B). (B). We now proceed in a similar manner as before. We have that Col(W>..) & Rdda, because we assumed that W>;- = A had rank less than S de. Thus, We fix > and v; arbitrarily, and define W. Wi+e(Wi41 @v;). We have that Wn. ... W W; = Wh... W++1 Wg. If for all choices of Us we have that (W W...., W....., Wi) is still a critical point for L., then we can deduce that
may find Wi+1 E Rd. Wi+1 # 0 such that
Wn. W1+11441
(l) & Row(W. Wi)) 0.
Repeating this reasoning, we obtain our result as before.
Proposition 10. Let be any smooth convex function, and let L= pa. If is non-global local minimumm for L. then necessarily rk(W) = (so 0 is a pure critical point). In particular, L has non-global minima if and only E,,, has non-global minima.
Proof. The first statement follows immediately from Proposition 9 if Crit(L.) is non-global local minimum, then necessarily de( * and conclude that rk(W) r. For the second statement, we observe that if is a convex function, then 0 is local minimum for if and only W ()( is local minimum for f|,..- Indeed, if W = pa)(0) is local minimum for f[,, then it is always true that any 0 E Pd (W) is local minimum. Conversely, if 0 is a local minimum,
21

---

Published as a conference paper at ICLR 2020
then from Proposition 9 we see that either de(W) = O, in which case W is (global) minimum because E is convex, or W must have maximal rank. In the latter case, (ua would be surjective (by Theorem 4 so W would also be a local minimum for d,,, (see Proposition 6 Finally, it is clear that 0 is also global minimum for L if and only if W is a global minimum for El... O
Proposition 14. If L' = fo va and L = lo paa then the critical locus Crit(L') is in "correspon- dence" " with Crit(L) n St meaning that
(va(O') 10' E (Cril(T))) (ma(0)] 0 Crit(L)
Proof. Let us define
p: +R Re (W,, h....... ..... W1) + Wh. W
W1
[[W
II
WA-1
Wi
9: Ω + Rd (Wh. ..... W1) +
WillWh--l ... [|ail.
[
[Will
The image of both of these maps is N ((Wh...., Wi) [W]]] = =1, 1-ii= b....,h. h 13. In fact, both maps are submersions onto N. Since va = pa o and pa q = Pala va q. it is enough to show the following two assertions: 1) E Crit(L') if and only if p(0') E Crit(L); and 2) 0 Crit(L) n if and only if (() Crit(L').
For 1), we deduce from L' = L a p that dL' (0') = dl(p((()) o dp(0") = O dl(p((')) = 0, but this also holds conversely: if dL' (f") = O, then Im(dp((")) is contained in Ker Ker(dL(p(("))) Since o p = p and both maps and q are submersions, we have that (m(p((0)) = T [ (n)((((()))) ()))). Now it follows from o q = Lia that dL() = dL(p((") dg(p((")) = 0. For 2), we argue analogously, exchanging the roles of L and L' as well as p and g.
A.7 PROOF OF THROREM 12
We consider a fixed matrix Qo E RR,, xd, and singular value decomposition (SVD) Qo = UXVT
Here U E xdy and V E RRd xdz are orthogonal and Σ E Rd, is diagonal with decreasing di- agonal entries 01, ,2...,, F' where and denote by [m], the set of all subsets of [m]] of cardinality r. For E [m]r. we define Dn E Rdy to be the diagonal matrix with entries 02,1, 01,21-.. TIm where TI,, a; if E I and
min(dz, dy). We also write shortly [m] 21, ..... m)
TT, = 0 otherwise. These matrices yield the critical points of the function hao (P) = PP Qol restricted the determinantal variety M,.
Theorem 28. If Qo & Mr, the critical points of houlM, are all matrices of the form UE, VT where Qo UEVT is SVD and [m]y. The local minima are the critical points with I = [r]. They are all global minima.
Proof. A matrix P E M, is a critical point if and only if (Qo- P) TpM- = Co)(P)+ &
(ow(P)+ If P Ex= (u( @ of) and Qo - P Σÿ= (ul @ vnr) are SVD decompositions with of # and o. + O, the column spaces of P and Qo - P are spanned by the uf and v² respectively. Similarly, the row spaces of and Qo - P are spanned by the if and v².. respectively. So P is a critical point if and only if the vectors u/, ul and v/ vi are orthonormal, i.e., if
Qo = P+ - P) =
df ( + Σ d'ff
3=1
is a SVD of Qo- This proves that the critical points are of the form UE2 where Qo = UEVT is SVD and I E [m]r-
Since he. (UΣrVT) = I1'S (M) |||m] Eigz of we see that the global minima are exactly the critical points selecting of the largest singular values of Qu. i.e., with I = [r]. is left to show that there are other local minima. For this, we consider critical point P UE such that at least one selected singular value o, for i E I is strictly smaller than o,., We will show now that P cannot be local minimum. Since o; < Fr, there is some j E [r] such that I. As
22

---

Published as a conference paper at ICLR 2020
above, write ug and Uy for the columns of U and V such that Qu Σ Th (1x)))) and P ΣNEI (22 & tk). We consider rotations in the planes spanned by u4 uj and vi 2y respectively: for a E [0,2] 2), we set u/a) cos(a)u, + sin(a)u; and vla) = cos(a));; + sin(a))3. Note that (0))= u, and ut() uj; analogously for ola), Next define x(a) cos2(a)) (a)o; + sin ( and
Pa =
Σ (EZ(()
oul @ vk) + tala) (ula) & vla)) E Mr
We note that Po P and P4 = US (ENNNG VT are both critical points of hg It remains to show that (Pa) as a function in is strictly decreasing on the interval [0, ž) From
(Pa) = Σ
onlux up) + to @ 04) ol ( 2 (()
K
and u(a) @ v(a) cos?(a)(u; @ v,) + cos(a) sin()((;; @ us + uy 8 v²) + sin (a)((() 8 U2), we deduce that
of + 0. - (()) cos? (a)) 2 2 (0(0) cos(() sin(a))) (o, -a(a) sin an?(a))
ho)(Pa)=
E
Σ kg
o + of + 22 - σi) cos cos - (o= - o.)² cos (a).
=
The graph of the function (x) = of + 20, 20,(0jz -0:00:10 0z)xz (aj-o; - [0;=o,)_=0 o,) for x E R. is parabola with unique local and global maximum at wo 0,-0: Since To 2 1, the function f is strictly increasing on the interval [0. 1]. Hence, h1o (P.) EkeI,Kaj of + [cos" (a:) is strictly decreasing on [0, 3).
which concludes the proof.
If the singular values of Qo are pairwise distinct and positive, the singular vectors of Qo are unique up to sign. So for each index set I E [m], the matrix Qr U'2/'' is the unique critical point of he.lm. whose singular values are the o, for i E I. Hence, Theorem 28 implies immediately the following:
Corollary 29. If the singular values of Qu are pairwise distinct and positive, hqulm, has exactly ("") critical points, namely the QI UE+VT for I E [m]p- Moreover, its unique local and global minimum is (r))
We can strengthen this result by explicitly calculating the index of each critical point, ie., the number of negative eigenvalues of the Hessian matrix.
Theorem 30. If the singular values of Qo are pairwise distinct and positive, the index of QI critical point of hq. M,, is
(Qde ((..) (mm) 12)
To prove this assertion, we may assume without loss of generality that dy S dr so m dy. We may further assume that Qo a diagonal matrix, so Qo = Σ. Let P(dy.rdd)) xr Rrxd, + Rd, be the matrix multiplication map, and = hy o ((d)) For (A, B) E r.d,. (Ez), Theorem implies that the condition Σn Crit(hxzlM,.) is equivalent to dL(A, B) = 0. Morcover, the number of negative eigenvalues of the Hessian of at any such factorization (A, B) of Ex is the same. This number is the index of Σz. So we can compute it by fixing one specific factorization (A, B3 of Σz
To compute the Hessian of L at (A, B), we compute the partial derivatives of first and second order of L:
aL dai
aL Jbi
2 [AB
-E J
= 2 (AB -2)] E)],,''
23

---

Published as a conference paper at ICLR 2020
ifiik k -ifi=k k
(15)
aai dam
2[BB*] Ia
0 L
ii
(16)
2(A Alik : _if
8
2aaby (aaby + [AB EJa)
ifj ifj=
(17)
Daijabul
To assemble these second order partial derivatives into a matrix, we choose the following order of the entries of (A, B):
01l.--.; Cir: 021:-.., 02:: ...y Odyl:---; b115--., bp1 012.-.., b,.: bidas.... brda-
We denote by H the Hessian matrix of L with respect to this ordering the following specifically chosen matrices (Ao, Bo): denoting by 11,12..... ir the entries of I in decreasing order, we pick the j-th column of Ag to be the i,-th standard basis vector R& and the j-th row of Bo to be the
oe multippe of the iy-th standard basis vector in Rd, Note that Bo = Σx, AB Ao = I, is the r x r-identity matrix, and By is the r x r-diagonal matrix with entries o/, o? ...,.......... of.- We write
D
M 1. where D E IRy Xrd,, .N E Rrd, Xrd, M E Id, xrds N
H
MT
Our first observation is that N, whose entries are described by (6), is twice the identity matrix, so N 2Iyd, Similarly, we see from (15) that D diagonal matrix. According to our fixed ordering, the entries of D are indexed by pairs (ij, kl) of integers i, k E [dy] and j. E [r]. With this, the diagonal entries of D are Dig.a3 = 20?, Analogously, the entries of M are indexed by pairs (ij, kl) of integers E [dy] j, k E [r] and l E [dz].
Lemma 31. Let i E [dy] and j E [r]. The ij-th row of M has exactly one non-zero entry. If I, is and the non-zero entry is Mij.ki, 20 Otherwise, if I, 20
there is some k E [r] with
the non-zero entry is Mij.jt
Proof. The entries of M are given by (17). We first observe that (Ao) (Bo))) is non-zero if and only if i = is and I = iy. Moreover, we have that (Au)i, de ((B)jj, di.- Similarly, [o E) non-zero if and only
& I. For & I we have that [A E]st -0
Now we fix i and j and consider the ij-th row of M. We apply our observations above to the following three cases.
If j = ij. then Mijai is non-zero if and only if k = j and = i. In that case, Mūjji 20,
If i E I, but i * iy. then there is some n + j such that i = i,. Now Mij.K1 is non-zero if and only if k = n and 1 = ij. In that case, Mij.ki, = 20:
Finally, if i & I, then Mij.Kt is non-zero if and only if is j and I i. In that case, we have that Mijai -0
Corollary 32. The square matrix A = MMT E xrd, is a diagonal matrix. For i E [dy] and j E [r], its ij-th diagonal entry is Aij.ij = 4of, if I and Aijaj = 4o if I
Proof. The computation of the diagonal entries follows directly from Lemma 31 To see that all other entries Å are zero, we need to show that no column of has more than one non-zero entry. So let us assume for contradiction that the kl-th column of M has non-zero entries in the ij-th row and in the 1y-th row for (i,j) # (1,
If 1 E I, then Lemma 31 limplies
i and i, = 1 i, which contradicts (i.j) * (2,7). If i $ I, we see from Lemma 31 that j = k = j and = = ō, which contradicts (t.j) * (7.
Finally, i I and & I. then Lemma 31 yields that 7 = ig I; contradiction.
Corollary 33. The characteristic polynomial of H is (t 22rlda -dyl _²"" II (1 2( +1)) KEI
II II (12 ( +1) + - -o?) (18)
S [EIm]IJJE
24

---

Published as a conference paper at ICLR 2020
Proof. Using Schur complements, compute the characteristic polynomial of H as follows:
Xu (t) = det (tIr(d, H)
det (tlyd, 21rds) ) det ((tlrd, -D) M(trrd 21rdd)
- >
= (t - 2)rdz det ((tlrd, - D) - (t (6-2))1A)
(1 1--))(dd-a0 del ((1- 2)( D) -)
By Corollary
32 the matrix (t - ()drrd - D) - A is diagonal matrix whose ij-th diagonal entry
is (t - () D (, - Aij.j. We write shortly dij A.j. and use the identity Dij,ús 20 to
further derive
dy
X=(()= (1-2) de)
(1 (1- 2) - -)( 813)
=1
(t- -t-2) 2)r((s=
t 21 + + (Aot, -5,))
i=1j=1
= (t - 2))(da
IIIII (1 2(0 ((0, +1)) i=I
II II (2 21 (E(4,)\IJ-
+ + 21 4 of
The latter equality was derived by substituting specific values into the 6,j according Corollary 32 Rearranging the terms of this last expression of (1) yields (8)).
Lemma 34. Let x, y > The polynomial f(t) = f² - 21(x + 1) 4(x (a- y) has two real roots and at least one of them is positive. Moreover, f(t) has negative root if and only if < y.
4(x
Proof. The roots of f(t) are x ++11 /(x + 4(r y) x discriminant is positive and f(() has two real roots. Clearly. one of these is positive. The other one is negative if and only if z + +1 v(x 1)2 + 4y, which is equivalent (x + 1)2 (x 1)2 + 4y and thus to x < y.
v(x 1)2 4y So the
Proof of Theorem 30 is left count the number of negative roots of the univariate polyno-
mial (88) All the linear factors of (18) have non-negative roots. The ij-th quadratic factor of (88)
for E [dy] I and j I, has at most one negative root due to Lemma Moreover, has exactly one negative root if and only of < of, which is equivalent to j Hence, the polynomial (18) has exactly # (). I x [dy] \ I
i} many negative roots.
Theorem 12. If the singular values of Qo are pairwise distinct and positive, hiu M, has exactly (") critical points, namely the matrices Q1= = UE,V with # #(I) = r. Moreover, its unique local and global minimum is Q......... More precisely, the index of QI as critical point of he M, (i.e., the number of negative eigenvalues of the Hessian matrix for any local parameterization)
index(Q7) 10
1j i}
where I (I,..., .....,,,].... AZ.
Proof. This is an amalgamation of Corollary 29 and Theorem
30
25


Reviews:
[{"review_id": "ryeoxyAntS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 authors use tools from algebraic geometry to study the critical points that arise in linear neural networks under a variety of loss functions.  In particular, they study linear maps that are parameterized (or overparameterized) as the product of multiple matrices.  The authors introduce a distinction between two types of critical points (for the linear function composed with a provided loss): there are those that are due to the actual manifold of functions that are provided to the loss (pure critical points), and there are those that are due to parameterizations of this manifold (spurious critical points).  The authors show that in the case that the linear function has maximal rank (is \"filling\"), then there are no non-global minima in the loss landscape.  In the case of lower rank (\"nonfilling\") linear functions, this property does not hold generally, but does hold for quadratic losses.   The authors show that for this framework, there can be exponentially many disconnected components in parameter space corresponding to global minima.  \n\nThis paper provides important insight into the loss landscape of neural networks, and it exhibits nuanced observations even in the linear case.  Naturally, there are many important follow-up studies that can be done in the case of non-linear networks.  It is vital to have a thorough understanding before that work can be satisfactorily undertaken.\n\nIt would benefit the authors to provide more summary/commentary in the main results section.  Currently, that section comes across as a list of lemmas, theorems, propositions, and corollaries, with relatively little narration in between.  It was challenging for me to identify which of these items were the main results, as summarized on in the first paragraph of the conclusions section.  I recommend that any theorem/corollary/proposition that is the primary basis for a claim made in the conclusion should receive significantly more commentary in Section 3.\n\nMinor comment:\nIn the first paragraph of the conclusion, it says that \"... the absence of ... is a rather general property ...\".  The word \"rather\" should be clarified.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "S1lfYa-IcH", "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": "This paper studied the landscape of linear neural networks using algebraic geometry tools. They introduced a distinction between \"pure\" and \"spurious\" critical points. They showed that for quadratic loss, there are no spurious local minimum in both the filling and non-filling case. For other convex loss, there are no spurious local minimum in the filling case, but there are spurious local minimum in the non-filling case. They gave a precise description of the number of topologically connected components of the variety of global minima. \n\nMy concern to this paper is that the landscape of linear neural networks, which is the subject of this paper, has already been analyzed in the literature. The final results of this paper, though derived using a different approach, are not new. Another limitation of this paper is, the approach of algebraic geometry used in the analysis seems hard to be generalized to non-linear multi-layers neural networks. \n\nA contribution of this paper is that the viewpoint of pure and spurious critical points made the landscape results of linear neural networks more intuitive. However, I don't have the expertise to assess whether this viewpoint was implicitly contained in the proof of previous results. Given this, I am not sure the contribution of this paper is enough for ICLR. \n\nI don't hold a strong opinion, since there could potentially be great ideas inside the algebraic geometry tools. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJe-Pb7RKS", "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": "This paper studies the critical locus of loss functions of deep linear networks. More specifically, this paper introduces a distinction between pure critical points and spurious critical points. The authors prove that all non-global local minima are always pure for convex losses and provide a precise description of the number of topologically connected components of the global minima.\n\nGenerally speaking, this paper is well written. However, it is a little bit messy in Section 3.2, where the authors present 4 propositions, one corollary and one remark in less than one page.\n\nMy main concern is the contribution and importance of this paper as the landscape of the training loss function of deep linear networks has been well studied. This paper indeed provides some new techniques and insights in this research direction, but the authors do not discuss the possible extension to a more complicated and practical case. I would like to raise my score if the authors can provide some reasonable and convincing discussions regarding the extension to the nonlinear case.\n\nBesides, there is no comparison with the existing results. The properties of critical points of deep linear networks have been studied in many literatures, the authors should provide detailed comparison and discussion between the derived results and these related work in the surrounding text of theorems. \n\n Another question is whether this analysis can be generalized to more practical settings, such as deep nonlinear networks. Besides, I believe that the critical points of general deep linear network can have an exact mapping to the critical points of normalized deep linear networks. Again, it is more interesting to explore the benefit of reparameterization for nonlinear networks. \n\nThe last question is whether the landscape analysis in this paper can shed some light on the training dynamics. This paper gives some results regarding the connected/disconnected components of global minima. Is it possible to show which global minima are more likely to be found by optimization algorithms?\n\n\n", "extra_scores": {"experience_assessment": "I have published one or two 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": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the landscape of linear networks and its critical point. The authors utilize geometric properties of determinantal varieties to derive interesting results on the landscape of linear networks. The reviewers raised some concerns about the fact that many of the results stated here can already be achieved using other techniques and therefore had some concerns about the novelty of these results. The authors provided a detailed response addressing these concerns. One reviewer however still had some concerns about the novelty. My own understanding of the paper is that while some of these results can be obtained using other approaches the proof techniques (brining ideas from algebraic geometry) is novel and could be rather useful. While at this point it is not clear that the techniques generalize to the nonlinear case I think algebraic geometry perspective have a good potential and provide some diversity in the theoretical techniques. As a result I recommend acceptance if possible.
Decision: Accept (Poster)