Title: PURE AND SPURIOUS CRITICAL POINTS: A GEOMETRIC STUDY OF LINEAR NETWORKS

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.

1. INTRODUCTION:

A fundamental goal in the theory of deep learning is to explain why the optimization of the nonconvex loss function of a neural network does not seem to be affected by the presence of nonglobal local minima. Many papers have addressed this issue by studying the landscape of the loss function (Baldi & Hornik, 1989; Choromanska et al., 2015; Kawaguchi, 2016; Venturi et al., 2018) . These papers have shown that, in certain situations, any local minimum for the loss is in fact always a global minimum. Unfortunately, it is also known that this property does not apply in more general realistic settings (Yun et al., 2018; Venturi et al., 2018) . More recently, researchers have begun to search for explanations based on the dynamics of 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 to 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, we view the loss as a composition {parameter space} µ → {functional space} → R.

In this setting, the function is almost always convex, however the composition L = • µ is not. Critical points for L 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, as pure and spurious. 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 a 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, we 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, we 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., a (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 of very special geometric properties of determinantal varieties that we discuss.

Related Work. Baldi & Hornik (1989) first proved the absence of non-global ("bad") local minima for linear networks with one hidden layer (autoencoders). Their result was generalized to the case of deep linear networks by Kawaguchi (2016) . Many papers have since then studied the loss landscape of linear networks under different assumptions (Hardt & Ma, 2016; Yun et al., 2017; Zhou & Liang, 2017; Laurent & von Brecht, 2017; Lu & Kawaguchi, 2017; Zhang, 2019) . 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 (2017) and Zhang (2019) argued that "depth does not create local minima", meaning that the absence of local minima of deep linear networks 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 a unified way. The optimization dynamics of linear networks are also an active area of research (Arora et al., 2019; 2018) , 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 (Draisma et al., 2013; Ottaviani et al., 2013) . Finally, we mention other recent works that study neural networks using algebraic-geometric tools (Mehta et al., 2018; Kileel et al., 2019; Jaffali & Oeding, 2019) .

Main contributions.

• We introduce a natural distinction between "pure" and "spurious" critical points for the loss function of networks. These notions provide an intuitive and useful language for studying a central aspect in the theory of neural networks, namely the (over)parameterization of the functional space and its effect on the optimization landscape. While most of the paper focuses on 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 1 .

Figure 1 : Pure and spurious critical points: θ 1 is a pure critical point, while θ 2 is a spurious critical point (the level curves on the manifold M Φ describe the landscape in functional space). Note that θ 3 is mapped to the same function as θ 2 , but it is not a critical point.

• We provide a precise description of the number of 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.

Differential notation. Our functional spaces will be manifolds with singularities, so we will make use of elementary notions from differential geometry. If M and N are manifolds and g : M → N is a smooth map, then we write dg(x) for the differential of g at the point x. This means that dg(x) :

T x M → T g(x)

N is the first order linear approximation of g at the point x ∈ M. If M and N have singularities, then the same definitions apply if we restrict g 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 ⊂ R m and N ⊂ R n , so we can view the tangent spaces T x M and T g(x) N as also embedded in R m and R n . When N = R, the critical locus of a map g : M → R is defined as

Crit(g) = {x ∈ Smooth(M) | dg(x) = 0}.

2. PRELIMINARIES:



2.1. PURE AND SPURIOUS CRITICAL POINTS:

A neural network (or any general "parametric learning model") is defined by a continuous mapping Φ : R d θ × R dx → R dy that associates an input vector x ∈ R dx and a set of parameters θ ∈ R d θ to an output vector y = Φ(θ, x) ∈ R dy . In other words, Φ determines a family of continuous functions parameterized by θ ∈ R d θ :

M Φ = {f θ : R dx → R dy | f θ = Φ(θ, •)} ⊂ C(R dx , R dy ).

Even though M Φ is naturally embedded in an infinite-dimensional functional space, it is itself finite dimensional. In fact, if the mapping Φ is smooth, then M Φ is a finite-dimensional manifold with singularities, and its intrinsic dimension is upper bounded by d θ . It is also important to note that neural networks are often non-identifiable models, which means that different parameters can represent the same function (i.e., f θ = f θ does not imply θ = θ ). The manifold M Φ is sometimes known as a neuromanifold (Amari, 2016) . We now consider a general loss function of the form L = • µ, where µ : R d θ → M Φ is the (over)parameterization of M Φ by θ and is a functional defined on a subset of

C(R dx , R dy ) containing M Φ : 1 L : R d θ µ -→ M Φ | M Φ -→ R. (1) Definition 1. A critical point θ * ∈ Crit(L) is a pure critical point if µ(θ * ) is a critical point for the restriction | MΦ (note that this implicitly requires µ(θ * ) to be a smooth point of M Φ ). If θ * ∈ Crit(L) but µ(θ * ) ∈ Crit( | MΦ ), we say that θ * is a spurious critical point.

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 θ * ∈ Crit(L) is a spurious critical point, then it may be possible to find another parameter θ that represents the same function f θ * = f θ and is not a critical point for L (see Figure 1 ). In contrast, if θ * is a pure critical point, then all parameters θ such that µ(θ ) = µ(θ * ) are automatically in Crit(L), simply because dL(θ

) = d | MΦ (µ(θ )) • dµ(θ ).

This will motivate us to study the fiber {θ | µ(θ) = f } of all parameters mapped to the same function f (particularly when the function f is a critical point of | MΦ ).

We note that a sufficient condition for θ * ∈ Crit(L) to be a pure critical point is that the differential dµ(θ * ) at θ * has maximal rank (namely dim M Φ ), i.e., that µ is locally a submersion at θ * . Indeed, we have in this case

0 = dL(θ * ) = d | MΦ (µ(θ * )) • dµ(θ * ) ⇒ d | MΦ (µ(θ * )) = 0, so µ(θ *

) is critical for the restriction of to M Φ . We also point out a special situation when M Φ is a convex set (as a subset of C(R dx , R dy )) and is a smooth convex functional. In this case, the only critical points of | MΦ are global minima, so we deduce that any critical point of L = • µ is either 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 or local maxima). Lemma 2. Let θ * ∈ Crit(L) be a (necessarily spurious) critical point with the following property: for any open neighborhood U of θ, there exists θ in U such that µ(θ ) = µ(θ) and θ ∈ Crit(L).

Then θ * is a saddle for L.

Proof. Assume that θ * is a local minimum (the reasoning is analogous if θ * is a local maximum). This means that there exists a neighborhood U of θ * such that L(θ) ≥ L(θ * ) for all θ ∈ U . In particular, if θ ∈ U is such that µ(θ ) = µ(θ), then θ must also be a local minimum. This contradicts θ ∈ Crit(L).

This general discussion on pure and spurious critical points applies to any smooth network map Φ (with possible extensions to the case of piece-wise smooth mappings), and we believe that the distinction can be a 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 M Φ can be embedded in a finite dimensional ambient space, namely the space of all linear maps R dx → R dy . Furthermore, M Φ is 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 Φ : R

EQUATION

where

W i ∈ R di×di-1 are matrices (so d 0 = d x , d h = d y , and d θ = d 0 d 1 + d 1 d 2 + . . . + d h-1 d h ).

The functional space is in this case a subset of the space of all linear maps R d0 → R d h . As in (1), we can decompose a loss function L for a linear network Φ as

R d h ×d h-1 × . . . × R d1×d0 µ d -→ R d h ×d0 -→ R (W h , . . . , W 1 ) -→ W = W h . . . W 1 -→ (W ).

(3)

Here µ d is the matrix multiplication map for the sequence of widths d = (d h , . . . , d 0 ), and is a functional on the space of (d h × d 0 )-matrices. In practice, it is typically a functional that depends on the training data, e.g. (W ) = W X -Y 2 for fixed matrices X, Y . 2 Note that even if is a convex functional, the set M Φ will often not be a convex set. In fact, it is easy to see that the image of µ d is the space M r of (d h × d 0 )-matrices of rank at most r = min{d 0 , . . . , d h }. If r < min(d 0 , d h ), this set is known as a determinantal variety, a classical object of study in algebraic geometry (Harris, 1995) . It is in 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) × (r + 1)-minors), and it is well known that the dimension of M r is r(m + n -r). Furthermore, for r > 0, the variety M r has many singularities: its singular locus is exactly M r-1 ⊂ M r , the set of all matrices with rank strictly smaller than r.

We refer the reader to Appendix A.1 for more details on determinantal varieties.

3. MAIN RESULTS:

In this section, we investigate the critical locus Crit(L) of general functions L : R d θ → R of the form L = • µ d where : R d h ×d0 → R is a (often convex) smooth map, and µ d is the matrix multiplication map introduced in (3). By studying the differential of µ d , we will characterize pure and spurious critical points of L. As previously noted, the image of µ d is M r ⊂ R d h ×d0 where r = min{d i }. In particular, we distinguish between two cases:

• We say that the map µ d is filling if r = min{d 0 , d h }, so M r = R d h ×d0

. In this case, the functional space is smooth and convex.

• We say that the map µ d is non-filling if r < min{d 0 , d h }, so M r R d h ×d0 is a determinantal variety. In this case, the functional space is non-smooth and non-convex.

3.1. PROPERTIES OF THE MATRIX MULTIPLICATION MAP:

We present some general results on the matrix multiplication map µ d , 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 µ d can be written explicitly as

EQUATION

)

Given a matrix M ∈ R m×n , we denote by Row(M ) ⊂ R n and Col(M ) ⊂ R m the vector spaces spanned by the rows and columns of M , respectively. Writing

EQUATION

From this expression, we deduce the following useful fact.

Lemma 3. The dimension of the image of the differential dµ d at θ = (W h , . . . , W 1 ) is given by

rk(dµ d (θ)) = h i=1 rk(W >i ) • rk(W <i ) - h-1 i=1 rk(W >i ) • rk(W <i+1 ),

where we use the convention that W <1 = I d0 , W >h = I d h are the identity matrices of size d 0 , d h .

We can use Lemma 3 to characterize all cases when the differential dµ d at θ = (W h , . . . , W 1 ) has full rank (i.e., when the matrix multiplication map is a local submersion onto M r ).

Theorem 4. Let r = min{d i }, θ = (W h , . . . , W 1 ), and W = µ d (θ). Furthermore, in both situations, if rk(W ) = e < r, then the image of dµ d (θ) always contains the tangent space T W M e of M e ⊂ M r at W .

We note that dµ d (θ) has always maximal rank when rk(W ) = r = min{d i }, however in the filling case it is possible to obtain a local submersion even when rk(W ) < r (see Example 19 in appendix).

We next describe the fiber of the matrix multiplication map, that is, the set

µ -1 d (W ) = {(W h , . . . , W 1 ) | W = W h . . . W 1 , W i ∈ R di×di-1 }.

It will be convenient to refer to µ -1 d (W ) as the set of d-factorizations of W . We are interested in understanding the structure of µ -1 d (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 µ -1 d (W ).

Theorem 5. Let r = min{d i }. If rk(W ) = r, then the set of d-factorizations µ -1 d (W ) of W has exactly 2 b path-connected components, where b = #{i | d i = r, 0 < i < h}. If rk(W ) < r, then µ -1 d (W ) is always path-connected.

3.2. APPLICATION TO LINEAR NETWORKS:

We now apply the general results from the previous subsection to study the critical locus Crit(L) 

with L = • µ d ,

Proposition 7. If θ ∈ Crit(L) with rk(W ) = e ≤ r, then W ∈ Crit( | Me ).

In other words, if rk(W ) < r, then θ ∈ Crit(L) implies that W is a critical point for the restriction of to a smaller determinantal variety M e (which is in the singular locus of the functional space M r in the non-filling case).

Note that if d h = 1, then either W = 0 or rk(W ) = 1, and in the latter case Proposition 7 implies that

W ∈ Crit( | R d 0 \{0}

). If is convex, we immediately obtain that all critical points (not just local minima, as in Laurent & von Brecht (2017) ) below a certain energy level are global minima. Corollary 8. Assume that is a smooth convex function and that

d h = 1. If θ ∈ Crit(L), then either W = µ d (θ) = 0 or θ is global minimum for L.

Proposition 7 shows that critical points for L such that rk(W ) < r correspond to critical points for restricted to a smaller determinantal variety. Using Lemma 2, it is possible to show that these points are essentially always saddles for L. Proposition 9. Let θ ∈ Crit(L) be such that rk(W ) < r, and assume that d (W ) = 0. Then, for any neighborhood U of θ, there exists θ in U such that µ d (θ ) = W but θ ∈ Crit(L). In particular, θ is a saddle point.

Proposition 10. Let be any smooth convex function, and let

L = • µ d . If θ is a non-global local minimum for L, then necessarily rk(W ) = r (so θ is a pure critical point).

In particular, L has non-global minima if and only if | Mr has non-global minima.

This statement succinctly explains many known facts on the landscape of linear networks. For example, we recover the main result from (Laurent & von Brecht, 2017) , which states that when is a smooth convex function and µ d is filling (r = min{d h , d 0 }), then all local minima for L are global minima: indeed, this is because M r = R d h ×d0 is a linear space, so | Mr does not have non-global minima. On the other hand, when µ d is not filling, the functional space is not convex, and multiple local minima may exist even when is a convex function. We will in fact present many examples of smooth convex functions such that L = • µ d has non-global local minima (see Figure 3 ). In the special case that is a quadratic loss (for any data distribution), then it is a remarkable fact that there are no non-global local minima even when µ d is 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 (2017) , the authors observe that their "structural hypothesis" (i.e., for us, the fact that the network is filling) is a necessary assumption for their main result, as otherwise critical points of 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 are no local bad minima despite the fact M r R d h ×d0 .

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 completely trivial. In particular, there is always a large positive-dimensional set of critical parameters associated with a critical linear function W (all possible d-factorizations of W ). More interestingly, this set may be topologically disconnected into a large number of components that are all functionally 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 :

R dy×dx → R is of the form (W ) = W X -Y 2

, where X ∈ R dx×s and Y ∈ R dy×s are fixed data matrices. As mentioned above, it is known that L = • µ d has no non-global local minima, even when µ d 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 a determinantal variety (or, equivalently, to the problem low-rank matrix approximation). Indeed, we know from Proposition 10 that L has non-global local minima if and only if the same is true for | Mr . Furthermore, assuming that XX T has full rank, we use its square root P = (XX T ) 1 /2 as a positive definite matrix to derive

W X -Y 2 = W X, W X F -2 W X, Y F + Y, Y F = W P, W P F -2 W P, Y X T P -1 F + Y, Y F = W P -Q 0 2 + const.,

where Q 0 = Y X T P -1 and "const." only depends on the data matrices X and Y . Hence, minimizing (W ) is equivalent to minimizing W P -Q 0 2 . Since the bijection M r → M r , W → W P is also a bijective on the tangent spaces, it provides a one-to-one correspondence from the critical points of min W ∈Mr W P -Q 0 2 to the critical points of min W ∈Mr W -Q 0 2 . All in all, studying the critical points of | Mr is equivalent to studying the critical points of the function

h Q0 (W ) = W -Q 0 2

where W is restricted to the determinantal variety M r .

The function h Q0 (W ) is described by following generalization of the classical Eckart-Young Theorem. 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 a fixed matrix Q 0 ∈ R dy×dx and a singular value decomposition (SVD) 

Q 0 = U ΣV T ,

Q I = U Σ I V T with #(I) = r.

Moreover, its unique local and global minimum is Q {1,...,r} . More precisely, the index of Q I as a critical point of h Q0 | Mr (i.e., the number of negative eigenvalues of the Hessian matrix for any local parameterization) is

index(Q I ) = #{(j, i) ∈ I × I c | j > i},

where I c = {1, . . . , m} \ I.

In the appendix we present a more general version of this statement without the assumption that the singular values of Q 0 are pairwise distinct and positive. The surprising aspect of this result is that the structure of the critical points is the same for almost all choices of Q 0 . 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. For all determinantal varieties, the situation is similar to the description in Example 13. More generally, given an algebraic variety V ⊂ R n and a point u ∈ R n , the number of (real) critical points of the distance function h u (p) = p -u 2 restricted to 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 the case of determinantal varieties with the standard Euclidean distance, this caustic hypersurface (more precisely its real locus) degenerates to 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 2 . 2 and Experiment 1).

3.4. USING DIFFERENT PARAMETERIZATIONS: NORMALIZED NETWORKS:

In the simple linear network model (2), the functional space M r ⊂ R d h ×d0 is parameterized using the matrix multiplication map µ d . 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 subsection, we take a look at a model for normalized linear networks: these are maps of the form

EQUATION

where W i ∈ R di×di-1 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

ν d : Ω → R d h ×d0 , (W h , . . . , W 1 ) → W = W h W h-1 W h-1 . . . W 1 W 1 ,

where

Ω = {(W h , . . . , W 1 ) | W i = 0, i = 1, . . . , h -1} ⊂ R d θ .

According to our definitions, if L = •µ d and L = •ν d 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 a priori the spurious critical loci induced by the two parameterizations may be different. In 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. If L = • ν d and L = • µ d , then the critical locus Crit(L ) is in "correspon- dence" with Crit(L) ∩ Ω, meaning that {ν d (θ ) | θ ∈ Crit(L )} = {µ d (θ) | θ ∈ Crit(L) ∩ Ω}.

4. CONCLUSIONS:

We have introduced the notions of pure and spurious critical points as general tools for a geometric investigation of the landscape of neural networks. In particular, they provide a basic language for describing the interplay between a convex loss function and an overparameterized, non-convex functional space. In this paper, we have focused on the landscape of linear networks. This simple model is 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 is a rather general property when the architecture is "filling", while in the "non-filling" setting it is a 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 an 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., d θ = dim(M Φ )), however there is still an interesting stratification of singular loci, as explained for example in (Amari, 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, it is clear that ReLU networks behave as linear networks when restricted to appropriate regions of input space: this suggests that our study of ranks of differentials may be a useful building block for pursuing in this important direction.

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 r < min(m, n), the r-th determinantal variety M r ⊂ R m×n is defined as the set of matrices with rank at most r:

M r = {P ∈ R m×n | rk(P ) ≤ r} ⊂ R m×n .

As mentioned in the main part of the paper, M r is an algebraic variety of dimension r(m + n -r), that can be described as the zero-set of all (r + 1) × (r + 1) minors. For r > 0, the the singular locus of M r is exactly M r-1 ⊂ M r . Some of our proofs will rely on the following explicit characterization of tangent space of determinantal varieties: given a a matrix P ∈ R m×n of rank exactly r (so P is a smooth point on M r ) we have that

T P M r = R m ⊗ Row(P ) + Col(P ) ⊗ R n ⊂ R m×n .

We will also make use of the normal space to the tangent space T P M r at P , with respect to the Frobenius inner product. This is given by

(T P M r ) ⊥ = Col(P ) ⊥ ⊗ Row(P ) ⊥ ,

where Col(P ) ⊥ and Row(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 ⊂ R n and a point u ∈ R n , the number of real critical points of the distance function h u (p) = p -u 2 restricted to V is only locally constant as u 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 in 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 (u 1 , u 2 ) ∈ C 2 is on the ED discriminant if and only if u 2 1 + u 2 2 = 0. This defines a curve in the complex plane whose real locus is a point (see right side of Figure 2 ). By the Eckart-Young Theorem (Theorem 12), the ED discriminant of the determinantal variety M r is the locus of all matrices Q 0 with at least two coinciding singular values, so it is defined by the discriminant of Q 0 Q T 0 . As in the case of the circle, the ED discriminant of M r has codimension two in R dy×dx .

Over the complex numbers, the number of critical points of the distance function h u restricted to V is actually the same for every point u ∈ C n 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 an ellipse has ED degree four (on the left side of Figure 2 , points u outside of the caustic curve yield two real critical points and two imaginary critical points). The Eckart-Young Theorem (Theorem 12) tells us that the ED degree of the determinantal variety M r ⊂ R dy×dx is m r where m = min(d x , d y ). 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 a linear change of coordinates. For an algebraic variety V ⊂ C n , a linear change of coordinates is given by an automorphism ϕ :

C n → C n .

For almost all such automorphisms (i.e., for all ϕ except those lying in some subvariety of GL(n, C)) the ED degree of ϕ(V) is the same; see Theorem 5.4 in Draisma et al. (2013) . This quantity is known as 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 perturbed the variety. Alternatively, we can fix the variety and change the standard Euclidean distance

• to dist ϕ = ϕ(•) . The new distance function h ϕ,u (p) = dist ϕ (p -u) 2 from u satisfies h ϕ(u) (ϕ(p)) = h id,ϕ(u) (ϕ(p)) = h ϕ,u (p).

Hence, the ED degree of ϕ(V) with respect to the standard Euclidean distance dist id = • equals the ED degree of V with respect to the perturbed Euclidean distance dist ϕ . In particular, the general ED degree of V can be obtained by computing 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 circle, the general ED degree of the determinantal variety M r is not equal to the ED degree of M r . Furthermore, there is no known closed formula for the general ED degree of M r only involving the parameters d x , d y and r. In the special case of rank-one matrices, one can derive a closed expression from the Catanese-Trifogli formula (Theorem 7.8 in Draisma et al. (2013) ): the general ED degree of M 1 is dx+dy s=0

(-1) s (2 dx+dy+1-s -1)(d x + d y -s)!     i+j=s i≤dx, j≤dy dx+1 i dy+1 j (d x -i)!(d y -j)!     .

This expression yields 39 for d x = d y = 3, as mentioned in Example 13. For general r, formulas for the general ED degree of M r involving Chern and polar classes can be found in Ottaviani et al. (2013) ; Draisma et al. (2013) . A short algorithm to compute the general ED degree of M r is given in Example 7.11 of Draisma et al. (2013) ; it uses a package for advanced intersection theory in the algebro-geometric software Macaulay2 (Grayson & Stillman, 2019).

This discussion shows that the Eckart-Young Theorem is indeed very special. The intrinsic reason for this is that the determinantal variety M r intersects the "isotropic quadric" associated with the standard Euclidean distance (i.e., zero locus of X 2 1,1 + . . . + X 2 dx,dy in C dx×dy ) in a particular way (i.e., non-transversely). Performing a random linear change of coordinates on either M r or the isotropic quadric makes the intersection transverse. So the ED degree after the linear change of coordinates is the general ED degree of M r , and the Eckart-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 a 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 situation 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 n that are separated by the ED discriminant of a variety V ⊂ R n . Finding the "typical" number of real critical points for the distance function h u 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 a perturbed Euclidean distance, we performed computational experiments with Macaulay2 (Grayson & Stillman, 2019) in the situation of Example 13. We fixed the determinantal variety M 1 ⊆ R 3×3 of rank-one (3 × 3)-matrices. In each iteration of the experiment, we picked a random automorphism ϕ : R 3×3 → R 3×3 and a random matrix Q 0 ∈ R 3×3 . We first verified that the number of complex critical points of the perturbed quadratic distance function h ϕ,Q0 restricted to M 1 is 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 is 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.

Implementation details: We note that our computations of real critical points and local minima involved numerical methods and might thus be affected by numerical errors. In our implementation we used several basic tests to rule out numerically bad iterations, so that we can report our results with high confidence. The entries of the random matrix Q 0 are independently and uniformly chosen among the integers in Z = {-10, -9, . . . , 9, 10}. The random automorphism ϕ is given by a matrix in Z 9×9 whose entries are also chosen independently and uniformly at random.

A.3 PURE AND SPURIOUS CRITICAL POINTS IN PREDICTOR SPACE:

We illustrate a variation of our functional setting where the notions of pure and spurious can also be naturally applied. We consider a training sample x 1 , . . . , x N ∈ R dx , y 1 , . . . , y N ∈ R (for notational simplicity we use d y = 1 but this is not necessary). We then write an empirical risk of the form

L(θ) = g( Ŷ (θ), Y ),

where Ŷ (θ) = (Φ(θ, x 1 ), . . . , Φ(θ, x N )) ∈ R N , Y = (y 1 , . . . , y N ) ∈ R N and g : R N ×R N → R is a convex function. As θ varies, Ŷ (θ) defines a "predictor manifold" Y ⊂ R N , which depends only on the input data x 1 , . . . , x N , but not on θ. The function L(θ) can be naturally seen as a composition

R d θ η → Y g → R,

where η(θ) = Ŷ (θ) ∈ Y. We may now distinguish again between "pure" and "spurious" critical points for L. In an underparameterized regime d θ < N , or if the input data x 1 , . . . , x N is in some way special, then Y R N is a submanifold (with singularities), and critical points may arise because we are restricting g to Y (pure), or because of the parameterization map η (spurious). In a highly overparameterized regime d θ N (which is usually the case in practice), we expect Y = R N . This can be viewed as analogous to 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 g| Y = g is convex.

A.4 PROOF OF THEOREM 4:

We first show Lemma 3 with help of the following general observation:

Proposition 15. Let V + 1 ⊆ V + 2 ⊆ . . . ⊆ V + h and V - 1 ⊇ V - 2 ⊇ . . . ⊇ V - h be vector spaces with dimensions r + i := dim(V + i ) and r - i := dim(V - i ) for i = 1, . . . , h. Then we have dim V + 1 ⊗ V - 1 + V + 2 ⊗ V - 2 + . . . + V + h ⊗ V - h = h i=1 r + i r - i - h-1 i=1 r + i r - i+1 .

Proof. We prove this assertion by induction on h. The base case (h = 1) is clear:

dim(V + 1 ⊗ V - 1 ) = r + 1 r - 1 .

For the induction step, we set

V := (V + 1 ⊗ V - 1 ) + . . . + (V + h-1 ⊗ V - h-1 ).

The key observation is that the inclusions

V + 1 ⊆ V + 2 ⊆ . . . ⊆ V + h and V - 1 ⊇ V - 2 ⊇ . . . ⊇ V - h imply that V ∩ (V + h ⊗ V - h ) = V + h-1 ⊗ V - h .

Hence, applying the induction hypothesis to V , we derive

dim V + V + h ⊗ V - h = dim(V ) + dim(V + h ⊗ V - h ) -dim(V + h-1 ⊗ V - h ) = h-1 i=1 r + i r - i - h-2 i=1 r + i r - i+1 + r + h r - h -r + h-1 r - h = h i=1 r + i r - i - h-1 i=1 r + i r - i+1 .

Lemma 3. The dimension of the image of the differential dµ d at θ = (W h , . . . , W 1 ) is given by

rk(dµ d (θ)) = h i=1 rk(W >i ) • rk(W <i ) - h-1 i=1 rk(W >i ) • rk(W <i+1 ),

where we use the convention that W <1 I d0 , W >h = I d h are the identity matrices of size d 0 , d h .

Proof. The image of the differential dµ d (θ) is given in ( 5). Due to

EQUATION

we can apply Proposition 15, which concludes the proof. Proof. Due to (7) the image (5) of dµ d (θ) always contains

R d h ⊗ Row(W ) + Col(W ) ⊗ R d0 = T W M e .

Furthermore, there always exists (W h , . . . , W 1 ) ∈ µ -1 d (W ) such that each W i has rank exactly r and the containments in ( 7) are all equalities. For example, one way to achieve this is to consider any decomposition W = U V T where U ∈ R d h ×r and V = R d0×r and then set

W 1 = [V | 0] T , W h = [U | 0], and W i = I r 0 0 0 for 2 ≤ i ≤ h -1

, where I r is the (r × r)-identity matrix and the zeros fill in the dimensions

(d i × d i-1 ) of W i .

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 i } and θ = (W h , . . . , W 1 ). In the non-filling case (i.e., if r < min{d h , d 0 }) we have that rk(dµ d (θ)) < dim M r if and only if rk(µ d (θ)) < r.

Proof. If rk(µ d (θ)) = r, then Proposition 16 implies that the image of the differential dµ d (θ) is the whole tangent space of M r at µ d (θ). To prove the other direction of the assertion, we assume that rk(µ d (θ)) < r. Since r < min{d h , d 0 }, there is some i ∈ {1, . . . , h -1} such that d i = r. We view µ d as the following concatenation of the matrix multiplication maps:

EQUATION

) where µ i,1 = µ (d h ,...,di) × µ (di,...,d0) and µ i,2 = µ (d h ,di,d0) . Since rk(µ d (θ)) < r, we have that rk(W >i ) < r or rk(W <i+1 ) < r. Without loss of generality, we may assume the latter. So applying Lemma 3 to µ i,2 and θ := µ i,1 (θ) yields rk(dµ

d (θ)) ≤ rk(dµ i,2 (θ )) = rk(W <i+1 ) (d h -rk(W >i )) + rk(W >i )d 0 < r (d h -rk(W >i )) + rk(W >i )d 0 = rk(W >i ) (d 0 -r) + r d h ≤ r (d 0 -r) + r d h = dim (M r ) .

Proposition 18. Let r = min{d i } and θ = (W h , . . . , W 1 ). In the filling case (i.e., if r = min{d h , d 0 }) we have that rk(dµ d (θ)) < d h d 0 if and only if there is some i ∈ {1, . . . , h -1} with rk(W >i ) < d h and rk(W <i+1 ) < d 0 .

Proof. Let us first assume that rk(W >i ) < d h and rk(W <i+1 ) < d 0 for some i ∈ {1, . . . , h -1}.

We view µ d as the concatenation of the matrix multiplication maps in (8). Applying Lemma 3 to µ i,2 and θ := µ i,1 (θ) yields

rk(dµ d (θ)) ≤ rk(dµ i,2 (θ )) = rk(W <i+1 ) (d h -rk(W >i )) + rk(W >i )d 0 < d 0 (d h -rk(W >i )) + rk(W >i )d 0 = d h d 0 .

Secondly, we assume the contrary, i.e., that every i ∈ {1, . . . , h -1} satisfies rk(W >i ) = d h or rk(W <i+1 ) = d 0 . We observe the following 2 key properties which hold for all i ∈ {1, . . . , h -1}:

EQUATION

)

We consider the index set

I := {i ∈ {1, . . . , h -1} | rk(W <i+1 ) = d 0 }. If I = ∅,

our assumption implies that rk(W >i ) = d h for every i ∈ {1, . . . , h}. So due to Lemma 3 we have

rk(dµ d (θ)) = d h h i=1 rk(W <i ) -d h h-1 i=1 rk(W <i+1 ) = d h rk(W <1 ) = d h d 0 .

If I = ∅, we define k := max I. So for every i ∈ {k + 1, . . . , h -1} we have rk(W <i+1 ) < d 0 , and thus rk(W >i ) = d h by our assumption. Moreover, due to (9), every j ∈ {0, . . . , k} satisfies rk(W <j+1 ) = d 0 . Hence, Lemma 3 yields

rk(dµ d (θ)) = k j=1 rk(W >j )d 0 + d h d 0 + h i=k+2 d h rk(W <i ) - k j=1 rk(W >j )d 0 - h-1 i=k+1 d h rk(W <i+1 ) = d h d 0 .

Example 19. According to Proposition 18, the differential of the matrix multiplication map is surjective whenever rk(W ) = r, but also for certain θ when rk(W ) < r. For example, let us consider the map µ (2,2,2) : R 2×2 × R 2×2 → R 2×2 and the two factorizations θ = ([

1 1 1 1 ] , [ 1 0 0 1 ]) and θ = ([ 1 0 1 0 ] , [ 1 1 0 0 ]) of the rank-one matrix [ 1 1 1 1 ].

According to Proposition 18, the differential dµ (2,2,2) (θ) has maximal rank 4. So it is surjective, whereas dµ (2,2,2) (θ ) is not. In fact, by Lemma 3, we have rk(dµ (2,2,2) (θ )) = 3. Theorem 4. Let r = min{d i }, θ = (W h , . . . , W 1 ), and W = µ d (θ).

• (Filling case) If r = min{d h , d 0 }, the differential dµ d (θ) has maximal rank equal to dim M r = d h d 0 if and only if, for every i ∈ {1, 2, . . . , h -1}, either rk(W >i ) = d h or rk(W <i+1 ) = d 0 holds. • (Non-filling case) If r < min{d h , d 0 }, the differential dµ d (θ) has maximal rank equal to dim M r = r(d h + d 0 -r) if and only if rk(W ) = r.

Furthermore, in both situations, if rk(W ) = e < r, then the image of dµ d (θ) always contains the tangent space T W M e of M e ⊂ M r at W .

Proof. This is an amalgamation of Propositions 16, 17 and 18.

A.5 PROOF OF THEOREM 5

In the following we use the notation from Theorem 5:

Theorem 5. Let r = min{d i }. If rk(W ) = r, then the set of d-factorizations µ -1 d (W ) of W has exactly 2 b path-connected components, where b = #{i | d i = r, 0 < i < h}. If rk(W ) < r, then µ -1 d (W ) is always path-connected.

We also write GL + (r) for the set of matrices in GL(r) with positive determinant. Analogously, we set GL -(r) := {G ∈ GL(r) | det(G) < 0}.

We first prove Theorem 5 in the case that b = 0. To show that µ -1 d (W ) is path-connected in this case, we show the following stronger assertion: given two matrices W and W of arbitrary rank and factorizations θ ∈ µ -1 d (W ) and θ ∈ µ -1 d (W ), each path in the codomain of µ d from W to W can be lifted to a path in the domain of µ d from θ to θ . Proposition 20 (Path Lifting Property).

If b = 0, then for every W, W ∈ R dy×dx , every θ ∈ µ -1 d (W ), every θ ∈ µ -1 d (W ) and every continuous function f : [0, 1] → R dy×dx with f (0) = W and f (1) = W , there is a continuous function F : [-1, 2] → R dy×d h-1 × . . . × R d1×dx such that F (-1) = θ, F (2) = θ , µ d (F (t)) = W for every t ∈ [-1, 0], µ d (F (t)) = W for every t ∈ [1, 2] and µ d (F (t)) = f (t) for every t ∈ [0, 1].

Proof. Without loss of generality, we may assume that d y ≤ d x . Then the assumption b = 0 means that d i > d y for all i = 1, . . . , h -1.

We prove the assertion by induction on h. For the induction beginning, we consider the cases h = 1 and h = 2. If h = 1, then µ d is the identity and Proposition 20 is trivial. For h = 2, we construct explicit lifts of the given paths. We first show that there is a path in µ

-1 d (W ) from θ = (W 2 , W 1 ) to some (B 2 , B 1 ) such that B 2 has full rank. Claim 1. Let h = 2, W ∈ R dy×dx and (W 2 , W 1 ) ∈ µ -1 d (W ). Then there is (B 2 , B 1 ) ∈ µ -1 d (W ) with rk(B 2 ) = d y and a continuous function g : [0, 1] → µ -1 d (W ) such that g(0) = (W 2 , W 1 ) and g(1) = (B 2 , B 1 ).

Proof. If rk(W 2 ) = d y , we have nothing to show. So we assume that s := rk(W 2 ) < d y . Without loss of generality, we may further assume that the first s rows of W 2 have rank s. As s < d 1 , we find a matrix G ∈ GL + (d 1 ) such that W 2 G = Is 0 M 0 , where I s ∈ R s×s is the identity matrix and M ∈ R (dy-s)×s . Since GL + (d 1 ) is path-connected, there is a continuous function g

1 : [0, 1] → GL + (d 1 ) with g 1 (0) = I d1 and g 1 (1) = G. Concatenation with GL(d 1 ) → µ -1 d (W ), H → (W 2 H, H -1 W 1 ) yields a continuous path g 1 in µ -1 d (W ) from (W 2 , W 1 ) to (W 2 G, G -1 W 1 ). Since (W 2 G)(G -1 W 1 ) = W , we see that G -1 W 1 = W (s)

N:

, where W (s) ∈ R s×dx is the first s rows of W and N ∈ R (dy-s)×dx . Replacing N by an arbitrary matrix N still yields that

W 2 G W (s) N = W . Hence, we find a continuous path g 2 in µ -1 d (W ) from (W 2 G, G -1 W 1 ) to (W 2 G, B 1 := W (s) 0 ).

Finally, we can replace the 0-columns in W 2 G by arbitrary matrices M 1 ∈ R s×(d1-s) and M 2 ∈ R (dy-s)×(d1-s) such that Is M1 M M2 B 1 = W still holds. In particular, we can pick M 1 = 0 and M 2 = [ I dy -s 0 ] such that B 2 := Is 0 M M2 has full rank d y , and we find a continuous path

g 3 in µ -1 d (W ) from (W 2 G, B 1 ) to (B 2 , B 1

). Putting g 1 , g 2 and g 3 together yields a path g as desired in Claim 1. ♦

As B 2 has full rank, we find a matrix

H ∈ GL + (d 1 ) such that B 2 H = [ I dy 0 ]. As in the proof of Claim 1, we construct a continuous path in µ -1 d (W ) from (B 2 , B 1 ) to (B 2 H, H -1 B 1 ). Since H -1 B 1 = [ W N ] for some N ∈ R (d1-dy)×dx , we also find a continuous path in µ -1 d (W ) from (B 2 H, H -1 B 1 ) to (B 2 H, [ W 0 ]).

All in all, we have constructed a continuous path

F 1 in µ -1 d (W ) from (W 2 , W 1 ) to ([ I dy 0 ] , [ W 0 ]

). Analogously, we find a continuous path

F 3 in µ -1 d (W ) between (W 2 , W 1 ) and ([ I dy 0 ] , W 0 ). Finally, we define F 2 : [0, 1] → R dy×d1 × R d1×dx , t → ([ I dy 0 ] , f (t) 0

) such that putting F 1 , F 2 and F 3 together yields a path F as desired in Proposition 20.

For the induction step, we view µ d as the concatenation of the following two matrix multiplication maps:

R dy×d h-1 × . . . × R d1×dx µ (d h ,...,d 1 ) ×id -→ R dy×d1 × R d1×dx µ (dy ,d 1 ,dx) -→ R dy×dx .

We consider θ = (W h , . . . , W 1 ) and θ = (W h , . . . , W 1 ), as well as

W >1 = W h • • • W 2 and W >1 = W h • • • W 2 . Given a path f : [0, 1] → R dy×dx from W = W >1 W 1 to W = W >1 W 1 , we apply the induction beginning (h = 2) to µ (dy,d1,dx) to get a path F 2 : [-0.5, 1.5] → R dy×d1 × R d1×dx such that F 2 (-0.5) = (W >1 , W 1 ), F 2 (1.5) = (W >1 , W 1 ), µ (dy,d1,dx) (F 2 (t)) = W for all t ∈ [-0.5, 0], µ (dy,d1,dx) (F 2 (t)) = W for all t ∈ [1, 1

.5] and µ (dy,d1,dx) (F 2 (t)) = f (t) for all t ∈ [0, 1]. Now we apply the induction hypothesis on µ (d h ,...,d1) and the path from W >1 to W >1 given by the first factor of F 2 . This yields a path

F 1 : [-1, 2] → R dy×d h-1 × . . . × R d2×d1 with F 1 (-1) = (W h , . . . W 2 ), F 1 (2) = (W h , . . . W 2 ), µ (d h ,...,d1) (F 1 (t)) = W >1 for all t ∈ [-1, -0.5], µ (d h ,...,d1) (F 1 (t)) = W >1 for all t ∈ [1.5, 2] and µ (d h ,...,d1) (F 1 (t))

is the first factor of F 2 (t) for all t ∈ [-0.5, 1.5]. This allows us to define a continuous path

F : [-1, 2] → R dy×d h-1 × . . . × R d1×dx from θ to θ by setting F (t) = (F 1 (t), W 1 ) for all t ∈ [-1, -0.5], F (t) = (F 1 (t), W 1 ) for all t ∈ [1.5, 2

] and for all t ∈ [-1, -0.5] we let F (t) consist of F 1 (t) and the second factor of F 2 (t).

Corollary 21. If b = 0, then µ -1 d (W ) is path-connected for each W ∈ R dy×dx .

Proof. Apply Proposition 20 to the constant function f

: [0, 1] → R dy×dx , t → W .

Now we study the case b > 0. We write 0 < i 1 < . . . < i b < h for those indices i j such that d ij = r. Then we view µ d as the concatenation of the following two matrix multiplication maps:

EQUATION

where µ 1 = µ (d h ,...,di b ) ×µ (di b ,...,di b-1 ) ×. . .×µ (di 1 ,...,d0) and µ 2 = µ (dy,di b ,...,di 1 ,dx) . Applying the path lifting property described above to the map µ 1 , we will show in Proposition 26 that µ -1 2 (W ) and µ -1 d (W ) have the same number of (path-)connected components. So it remains to study the connected components of µ -1 2 (W ). We can shortly write the map µ 2 as

µ 2 : R dy×r × R r×r b-1 × R r×dx -→ R dy×dx .

In the case that rk(W ) = r, we use the following natural action of GL(r) b on µ -1 2 (W ):

EQUATION

In fact, we show now that µ -1 2 (W ) is the orbit of any element under this action if rk(W ) = r. From this we will deduce in Corollaries 23 and 24 that µ -1 2 (W ) is homeomorphic to GL(r) b and thus has 2 b (path-)connected components if the matrix W has maximal rank r.

Proposition 22. Let b > 0 and θ = (A b+1 , . . . , A 1 ) ∈ R dy×r × (R r×r ) b-1 × R r×dx such that W = µ 2 (θ) has maximal rank r. Then µ -1 2 (W )

is the orbit of θ under the action defined in (11), i.e., µ -1

2 (W ) = A b+1 G b , G -1 b A b G b-1 , . . . , G -1 1 A 1 | G 1 , . . . , G b ∈ GL(r) .

Proof. One inclusion, namely "⊇", is trivial. We prove the other inclusion "⊆" by induction on b.

For the induction beginning (b = 1), we write W = W11 W12 W21 W22 where W 11 ∈ R r×r . Without loss of generality, we may assume that rk(W 11 ) = r. Similarly, we write A 2 = A21 A22 and A 1 = [ A11 A12 ] where A i1 ∈ R r×r for i = 1, 2. For (A 2 , A 1 ) ∈ µ -1 2 (W ), we write analogously A 2 = For the induction step (b > 1), we consider (A b+1 , . . . , A 1 ) ∈ µ -1 2 (W ) and

A >1 = A b+1 • • • A 2 , A >1 = A b+1 • • • A 2 ∈ R dy×r . Now we can apply the induction beginning to find G 1 ∈ GL(r) such that A >1 = A >1 G 1 and A 1 = G -1 1 A 1 . As A >1 has rank r and A b+1 • • • A 2 = A >1 = A b+1 • • • (A 2 G 1 )

, we can apply the induction hypothesis on the map which multiplies the left-most b matrices. This yields G b , . . . G 2 ∈ GL(r) such that

A b+1 = A b+1 G b , . . . , A 3 = G -1 3 A 3 G 2 , A 2 = G -1 2 (A 2 G 1 ).

Corollary 23. If b > 0 and W ∈ R dy×dx has maximal rank r, then µ -1 2 (W ) is homeomorphic to GL(r) b .

Proof. We fix θ = (A b+1 , . . . , A 1 ) ∈ µ -1 2 (W ). The map ϕ : GL(r) b → µ -1 2 (W ) given by the action (11) on θ is continuous. We now construct its inverse. As rk(W ) = r, we have that rk(A i ) = r for all i = 1, . . . , b + 1. Without loss of generality, we may assume that the first r rows of A b+1 have rank r. We write π : R dy×r → R r×r for the projection which forgets the last d y -r rows of a given matrix. For θ = (A b+1 , . . . , A 1 ) ∈ µ -1 2 (W ), Proposition 22 shows that θ = ϕ(G b , . . . , G 1 ) for some (G b , . . . , G 1 ) ∈ GL(r) b . So we have that

G b = π(A b+1 ) -1 π(A b+1 ), G b-1 = A -1 b G b A b , . . . , G 1 = A -1 2 G 2 A 2 , which defines a map ψ : µ -1 2 (W ) -→ GL(r) b , A b+1 , . . . , A 1 -→ G(A b+1 ), A -1 b G(A b+1 )A b , . . . , A -1 2 • • • A -1 b G(A b+1 )A b • • • A 2 ,

where G(A b+1 ) := π(A b+1 ) -1 π(A b+1 ). By construction, ψ is the inverse of ϕ. Since ψ is continuous, it is a homeomorphism between µ -1 2 (W ) and GL(r) b .

Corollary 24. If b > 0 and W ∈ R dy×dx has maximal rank r, then µ -1 2 (W ) has 2 b 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 components are path-connected. Hence, GL(r) b has 2 b connected components, each of them pathconnected. By Corollary 23, the same holds for µ -1 2 (W ).

To complete our understanding of the connected components of µ -1 2 (W ), we consider the case that the matrix W ∈ R dy×dx does not have maximal rank r. In that case, it turns out that µ -1 2 (W ) is pathconnected, which we show by constructing explicit paths between any two elements of µ -1 2 (W ). Proposition 25. Let W ∈ R dy×dx . If b > 0 and rk(W ) < r, then µ -1 2 (W ) is path-connected.

Proof. We write

W = W 1 W 2

where W 1 ∈ R r×dx , and denote by e the rank of W . If rk(W 1 ) = e,

then W 2 = M W 1 for some M ∈ R (dy-r)×r . Claim 2. If b = 1, (A 2 , A 1 ) ∈ µ -1 2 (W ), rk(W 1 ) = e and W 2 = M W 1 , then there is a continuous function f : [0, 1] → µ -1 2 (W ) with f (0) = (A 2 , A 1 ) and f (1) = ( Ir M , W 1 ).

Proof. Since rk(W ) < r, we have that rk(A 2 ) < r or rk(A 1 ) < r. If rk(A 2 ) < r, we proceed as in the proof of Claim 1 to find a path in µ -1 2 (W ) from (A 2 , A 1 ) to (A 2 , A 1 ) such that rk(A 2 ) = r. Hence, we may assume that rk(A 2 ) = r. This implies that rk(A 1 ) = e. So K := ker(A T 1 ) ⊆ R r has positive dimension r -e. We write A 2 = A21 A22 where A 21 ∈ R r×r , and denote by r 2 the rank of A 21 . So the rowspace R ⊆ R r of A 21 has dimension r 2 . We now show that K + R = R r . To see this we set δ := dim(K ∩ R). Without loss of generality, we may assume that the first e rows of W 1 are linearly independent. Then the first e rows of A 21 must also be linearly independent, so we might further assume that the first r 2 rows of A 21 are linearly independent. We denote by A 211 and W 11 the matrices formed by the first r 2 rows of A 21 and W 1 , respectively. In particular, we have We first note that Row(W <h ) = R d0 , for otherwise dµ d (θ) would be surjective, implying that d (W ) = 0. We define i = max{j | Row(W <j ) = R d0 }, so 1 ≤ i < h (writing W <1 = I d0 ). We have that

EQUATION

Since Row(W <i+1 ) R d0 , we may find w i ∈ R di , w i = 0 such that w T i W i . . . W 1 = 0. We now fix > 0 and v i+1 ∈ R di+1 arbitrarily, and define Wi+1 = W i+1 + (v i+1 ⊗ w i ). Clearly, we have that

EQUATION

Combining ( 12) and ( 13), we have that

d (W )(Col(W h , . . . , W i+2 (v i+1 ⊗ w i )) ⊗ R d0 ) = 0.

If this were true for all v i+1 , then it would imply

EQUATION

Hence, we have either found an arbitrarily small perturbation θ of θ as required in Proposition 9, or ( 14) must hold. In the latter case, we reapply the same argument for Wi+2 = W i+2 + (v i+2 ⊗ w i+1 ) where w i+1 = 0 and w T i+1 W i+1 . . . W 1 = 0. Again, we can either construct an arbitrarily small perturbation θ of θ as required in Proposition 9, or we have d (W )(Col(W >i+2 ) ⊗ R d0 ) = 0. Proceeding this way we eventually arrive at d (W )(R d h ⊗ R d0 ) = 0 so d (W ) = 0, which contradicts the hypothesis. Thus, at some point we must find an arbitrarily small perturbation θ of θ as required in Proposition 9, which concludes the proof in the case that µ d is filling.

We now consider the case that µ d is not filling. We pick i ∈ {1, . . . , h -1} such that d i = r, and write for simplicity A = W h . . . W i+1 and B = W i . . . W 1 . The assumption rk(W ) < r implies that rk(A) < r or rk(B) < r, and we assume without loss of generality that rk(A) < r. We define the map L B (W h , . . . , W i+1 ) = (W h . . . W i+1 B). We also introduce the map B (A ) = (A B) and the matrix multiplication map µ d A where d A = (d h , . . . , d i+1 ), so that L B = B • µ d A . If θ is a critical point for L, then θ A = (W h , . . . , W i+1 ) must be a critical point for L B . 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 to θA such that µ d A (θ A ) = µ d A ( θA ) but θA / ∈ Crit(L B ), or d B (A) = 0. In the former case, we have that θ = ( θA , θ B ) is not a critical point for L, and we are done. If instead d B (A) = 0, then we have that

d (W )(R d h ⊗ Row(B)) = 0,

because the image of the differential of the map A → A B is given by R d h ⊗ Row(B). We now proceed in a similar manner as before. We have that Col(W >i ) R d h , because we assumed that W >i = A had rank less than r ≤ d h . Thus, we may find w i+1 ∈ R di , w i+1 = 0 such that W h . . . W i+1 w i+1 = 0. We fix > 0 and v i arbitrarily, and define Wi = W i + (w i+1 ⊗v i ). We have that W h . . . W i+1 Wi = W h . . . W i+1 W i . If for all choices of v i we have that (W h , . . . , Wi , . . . , W 1 ) is still a critical point for L, then we can deduce that

d (W )(R d h ⊗ Row(W i-1 . . . W 1 )) = 0.

Repeating this reasoning, we obtain our result as before.

Proposition 10. Let be any smooth convex function, and let L = • µ d . If θ is a non-global local minimum for L, then necessarily rk(W ) = r (so θ is a pure critical point). In particular, L has non-global minima if and only if | Mr has non-global minima.

Proof. The first statement follows immediately from Proposition 9: if θ ∈ Crit(L) is a non-global local minimum, then necessarily d (W ) = 0, and we conclude that rk(W ) = r. For the second statement, we observe that if is a convex function, then θ is a local minimum for L if and only if 

W = µ d (θ) is a local minimum for | Mr . Indeed, if W = µ d (θ) is a local minimum for | Mr , then it is always true that any θ ∈ µ -1 d (W )

{ν d (θ ) | θ ∈ Crit(L )} = {µ d (θ) | θ ∈ Crit(L) ∩ Ω}.

Proof. Let us define

p : Ω → R d θ , (W h , . . . , W 1 ) → W h , W h-1 W h-1 , . . . , W 1 W 1 , q : Ω → R d θ , (W h , . . . , W 1 ) → W h W h-1 . . . W 1 , W h-1 W h-1 , . . . , W 1 W 1 .

The image of both of these maps is

N = {(W h , . . . , W 1 ) | W i = 1, i = 1, . . . , h -1}. In fact, both maps are submersions onto N . Since ν d = µ d • p and µ d • q = µ d | Ω = ν d • q, it

is enough to show the following two assertions: 1) θ ∈ Crit(L ) if and only if p(θ ) ∈ Crit(L); and 2) θ ∈ Crit(L) ∩ Ω if and only if q(θ) ∈ Crit(L ).

For 1), we deduce from

L = L • p that dL (θ ) = dL(p(θ )) • dp(θ ) = 0 if dL(p(θ )) = 0, but this also holds conversely: if dL (θ ) = 0, then Im(dp(θ )) is contained in Ker(dL(p(θ ))).

Since q • p = p and both maps p and q are submersions, we have that Im(dp(θ

)) = T p(θ ) N = Im(dq(p(θ ))). Now it follows from L • q = L| Ω that dL(p(θ )) = dL(p(θ )) • dq(p(θ )) = 0.

For 2), we can argue analogously, exchanging the roles of L and L as well as p and q.

A.7 PROOF OF THEOREM 12

We consider a fixed matrix Q 0 ∈ R dy×dx and a singular value decomposition (SVD) Q 0 = U ΣV T .

Here U ∈ R dy×dy and V ∈ R dx×dx are orthogonal and Σ ∈ R dy×dx is diagonal with decreasing diagonal entries σ 1 , σ 2 , . . . , σ m where m = min(d x , d y ). We also write shortly 

(Q 0 -P ) ∈ T P M ⊥ r = Col(P ) ⊥ ⊗ Row(P ) ⊥ . If P = r i=1 σ i (u i ⊗ v i ) and Q 0 -P = e j=1 σ j (u j ⊗ v j

) are SVD decompositions with σ i = 0 and σ j = 0, the column spaces of P and Q 0 -P are spanned by the u i and u j , respectively. Similarly, the row spaces of P and Q 0 -P are spanned by the v i and v j , respectively. So P is a critical point if and only if the vectors u i , u j and v i , v j are orthonormal, i.e., if

Q 0 = P + (Q 0 -P ) = r i=1 σ i (u i ⊗ v i ) + e j=1 σ j (u j ⊗ v j )

is a SVD of Q 0 . This proves that the critical points are of the form U Σ I V T where Q

0 = U ΣV T is a SVD and I ∈ [m] r . Since h Q0 (U Σ I V T ) = U Σ [m]\I V T 2 = Σ [m]\I 2 = i /

∈I σ 2 i , we see that the global minima are exactly the critical points selecting r of the largest singular values of Q 0 , i.e., with I = [r]. It is left to show that there are no other local minima. For this, we consider a critical point P = U Σ I V T such that at least one selected singular value σ i for i ∈ I is strictly smaller than σ r . We will show now that P cannot be a local minimum. Since σ i < σ r , there is some j ∈ [r] such that j / ∈ I. As above, we write u k and v k for the columns of U and V T such that Q 0 = m k=1 σ k (u k ⊗v k ) and P = k∈I σ k (u k ⊗ v k ). We consider rotations in the planes spanned by u i , u j and v i , v j , respectively: for a ∈ [0, π 2 ], we set u (α) = cos(α)u i + sin(α)u j and v (α) = cos(α)v i + sin(α)v j . Note that u (0) = u i and u ( π 2 ) = u j ; analogously for v (α) . Next we define σ (α) = cos 2 (α)σ i + sin 2 (α)σ j and

P α = k∈I\{i} σ k (u k ⊗ v k ) + σ (α) u (α) ⊗ v (α) ∈ M r .

We note that P 0 = P and P π 2 = U Σ I\{i}∪{j} V T are both critical points of h Q0 | Mr . It remains to show that h Q0 (P α ) as a function in α is strictly decreasing on the interval [0, π 2 ]. From

h Q0 (P α ) = k / ∈I σ k (u k ⊗ v k ) + σ i (u i ⊗ v i ) -σ (α) (u (α) ⊗ v (α) ) 2

and u (α) ⊗ v (α) = cos 2 (α)(u i ⊗ v i ) + cos(α) sin(α)(u i ⊗ v j + u j ⊗ v i ) + sin 2 (α)(u j ⊗ v j ), we deduce that

h Q0 (P α ) = k / ∈I,k =j σ 2 k + σ i -σ (α) cos 2 (α) 2 + 2 σ (α) cos(α) sin(α) 2 + σ j -σ (α) sin 2 (α) 2 = k / ∈I,k =j σ 2 k + σ 2 i + 2σ j (σ j -σ i ) cos 2 (α) -(σ j -σ i ) 2 cos 4 (α).

The graph of the function f (x) = σ 2 i +2σ j (σ j -σ i )x-(σ j -σ i ) 2 x 2 , for x ∈ R, is a parabola with a unique local and global maximum at x 0 = We can strengthen this result by explicitly calculating the index of each critical point, i.e., the number of negative eigenvalues of the Hessian matrix. To prove this assertion, we may assume without loss of generality that d y ≤ d x , so m = d y . We may further assume that Q 0 is a diagonal matrix, so Q 0 = Σ. Let µ (dy,r,dx) : R dy×r × R r×dx → R dy×dx be the matrix multiplication map, and L = h Σ • µ (dy,r,dx) . For (A, B) ∈ µ -1 (dy,r,dx) (Σ I ), Theorem 4 implies that the condition Σ I ∈ Crit(h Σ | Mr ) is equivalent to dL(A, B) = 0. Moreover, the number of negative eigenvalues of the Hessian of L at any such factorization (A, B) of Σ I is the same. This number is the index of Σ I . So we can compute it by fixing one specific factorization (A, B) of Σ I .

To compute the Hessian of L at (A, B), we compute the partial derivatives of first and second order of L:

∂L ∂a ij = 2 (AB -Σ)B T ij , ∂L ∂b ij = 2 A T (AB -Σ) ij ,

Proof. Using Schur complements, we can compute the characteristic polynomial of H as follows:

χ H (t) = det tI r(dx+dy) -H = det (tI rdx -2I rdx ) det (tI rdy -D) -M (tI rdx -2I rdx ) -1 M T = (t -2) rdx det (tI rdy -D) -(t -2) -1 ∆ = (t -2) r(dx-dy) det (t -2)(tI rdy -D) -∆ .

By Corollary 32, the matrix (t -2)(tI rdy -D) -∆ is a diagonal matrix whose ij-th diagonal entry is (t -2)(t -D ij,ij ) -∆ ij,ij . We write shortly δ ij := ∆ ij,ij and use the identity D ij,ij = 2σ 2 ij to further derive χ H (t) = (t -2) r(dx-dy) The latter equality was derived by substituting specific values into the δ ij according to Corollary 32.

Rearranging the terms of this last expression of χ H (t) yields (18).

Lemma 34. Let x, y > 0. The polynomial f (t) = t 2 -2t(x + 1) + 4(x -y) has two real roots and at least one of them is positive. Moreover, f (t) has a negative root if and only if x < y.

Proof. The roots of f (t) are x + 1 ± (x + 1) 2 -4(x -y) = x + 1 ± (x -1) 2 + 4y. So the discriminant is positive f (t) has two real roots. Clearly, one of these is positive. The other one is negative if and only if x + 1 < (x -1) 2 + 4y, which is equivalent to (x + 1) 2 < (x -1) 2 + 4y and thus to x < y.

Proof of Theorem 30. It is left to count the number of negative roots of the univariate polynomial (18). All the linear factors of (18) have non-negative roots. The ij-th quadratic factor of (18), for i ∈ [d y ] \ I and j ∈ I, has at most one negative root due to Lemma 34. Moreover, it has exactly one negative root if and only if σ 2 j < σ 2 i , which is equivalent to j > i. Hence, the polynomial (18) has exactly #{(j, i) ∈ I × [d y ] \ I | j > i} many negative roots. Proof. This is an amalgamation of Corollary 29 and Theorem 30.

:

This setting applies to both the empirical loss and the population loss.

Our setting can also be applied when includes a regularizer term defined in function space, e.g., (W ) = W X -Y 2 + λR(W ).

This means that the algebraic equations corresponding to the vanishing of the differential have exactly 39 complex solutions.

Figures and Tables:

where we assume Σ ∈ R dy×dx has decreasing diagonal entries σ 1 , . . . , σ m , with m = min(d y , d x ). For any I ⊂ {1, 2, . . . , m} we write Σ I ∈ R dy×dx for the diagonal matrix with entries σ I,1 , . . . , σ I,m where σ I,i = σ i if i ∈ I and σ I,i = 0 otherwise. Theorem 12. If the singular values of Q 0 are pairwise distinct and positive, h Q0 | Mr has exactly m r critical points, namely the matrices

Figure3: Real critical points and local minima for random choices of hQ0 | M1 as defined in Example 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 (Table2 and Experiment 1).

Now we provide a proof for Theorem 4, starting from a refinement of the last statement.Proposition 16. Let r = min{d i }, θ = (W h , . . . , W 1 ), W = µ d (θ), and e = rkW . The image of the differential dµ d at θ contains the tangent space T W M e of M e at W . Furthermore, for every W ∈ M e \M e-1 there exists θ such that µ d (θ ) = W and the image of dµ d (θ ) is exactly T W M e .

A 21 A 22 and A 1 = [ A 11 A 12 ]. Due to rk(W 11 ) = r, we have that rk(A 21 ) = r = rk(A 21 ). Hence, there is a matrix G ∈ GL(r) such that A 21 = A 21 G. This implies that A 21 GA 11 = W 11 = A 21 A 11 , so A 11 = G -1 A 11 . Due to A 21 A 12 = W 12 = A 21 GA 12 , we get that A 12 = G -1 A 12 . Finally, rk(W 11 ) = r implies that rk(A 11 ) = r, so A 22 A 11 = W 21 = A 22 G -1 A 11 shows A 22 = A 22 G.Thus we have shown that A 2 = A 2 G and A 1 = G -1 A 1 .

[m] = {1, 2, . . . , m} and denote by [m] r the set of all subsets of [m] of cardinality r. For I ∈ [m] r , we define Σ I ∈ R dy×dx to be the diagonal matrix with entries σ I,1 , σ I,2 , . . . , σ I,m where σ I,i = σ i if i ∈ I and σ I,i = 0 otherwise. These matrices yield the critical points of the function h Q0 (P ) = P -Q 0 2 restricted to the determinantal variety M r . Theorem 28. If Q 0 / ∈ M r , the critical points of h Q0 | Mr are all matrices of the form U Σ I V T where Q 0 = U ΣV T is a SVD and I ∈ [m] r . The local minima are the critical points with I = [r]. They are all global minima. Proof. A matrix P ∈ M r is a critical point if and only if

σj σj -σi . Since x 0 ≥ 1, the function f is strictly increasing on the interval [0, 1]. Hence, h Q0 (P α ) = k / ∈I,k =j σ 2 k +f (cos 2 (α)) is strictly decreasing on [0, π2], which concludes the proof. If the singular values of Q 0 are pairwise distinct and positive, the singular vectors of Q 0 are unique up to sign. So for each index set I ∈ [m] r the matrix Q I = U Σ I V T is the unique critical point of h Q0 | Mr whose singular values are the σ i for i ∈ I. Hence, Theorem 28 implies immediately the following: Corollary 29. If the singular values of Q 0 are pairwise distinct and positive, h Q0 | Mr has exactly m r critical points, namely the Q I = U Σ I V T for I ∈ [m] r . Moreover, its unique local and global minimum is Q [r] .

If the singular values of Q 0 are pairwise distinct and positive, the index ofQ I as a critical point of h Q0 | Mr is index(Q I ) = #{(j, i) ∈ I × ([m] \ I) | j > i}.

If the singular values of Q 0 are pairwise distinct and positive, h Q0 | Mr has exactly m r critical points, namely the matrices Q I = U Σ I V T with #(I) = r. Moreover, its unique local and global minimum is Q {1,...,r} . More precisely, the index of Q I as a critical point of h Q0 | Mr (i.e., the number of negative eigenvalues of the Hessian matrix for any local parameterization) is index(Q I ) = #{(j, i) ∈ I × I c | j > i},where I c = {1, . . . , m} \ I.

Bad local minima in loss landscapes for linear networks

Table content: <table><tr><td>←-</td><td>convex optimization over vector space</td></tr></table>

where is any smooth function. In the following, we always use r = min{r i } and W = µ d (θ). The next two facts follow almost immediately from Theorem 4. Proposition 6. If θ is such that dµ d (θ) has maximal rank (see Theorem 4), then θ ∈ Crit(L) if and only if W ∈ Crit( | Mr ), and θ is a minimum (resp., saddle, maximum) for L if and only if W is a minimum (resp., saddle, maximum) for | Mr . If rk(W ) = r (which implies that dµ

Table content: <table/>

If V ⊂ R 2 is an ellipse, the distance function h u (p) = p -u 2 restricted to V generally has 2 or 4 real critical points, depending on whether u lies inside or outside the diamondshaped region bounded by the caustic curve. Right: If V ⊂ R 2 is a circle, then the caustic curve degenerates to a point and the distance function generically has always 2 real critical points. geometry, it is possible to show that for almost all linear coordinate changes (an open dense set), the function hQ0 | M1 has 39 critical points over the complex numbers.3 The number of real critical points however varies, depending on whether Q 0 belongs to different open regions separated by a caustic hypersurface in R 3×3 . Furthermore, the number of local minima varies as well; in particular, it is no longer true that all Q 0 admit a unique local minimum. Figure3presents some simple computational experiments illustrating this behavior.

Table content: <table/>

Number of critical points (columns) and number of minima (rows) in our experiments

Table content: <table><tr><td/><td/><td/><td colspan="3">#(critical points)</td></tr><tr><td/><td>1</td><td>3</td><td>5</td><td>7</td><td>9</td><td>11 13</td></tr><tr><td/><td colspan="3">1 0 476 120</td><td>1</td><td>0</td><td>0</td><td>0</td></tr><tr><td>#(local</td><td>2 0</td><td>0</td><td colspan="3">805 190 10</td><td>0</td><td>0</td></tr><tr><td colspan="2">minima) 3 0</td><td>0</td><td>0</td><td colspan="3">228 116 21 0</td></tr><tr><td/><td>4 0</td><td>0</td><td>0</td><td>0</td><td colspan="2">16 12 5</td></tr></table>

is a local minimum. Conversely, if θ is a local minimum, then from Proposition 9 we see that either d (W ) = 0, in which case W is a (global) minimum because is convex, or W must have maximal rank. In the latter case, dµ d (θ) would be surjective (by Theorem 4), so W would also be a local minimum for | Mr (see Proposition 6). Finally, it is clear that θ is also a global minimum for L if and only if W is a global minimum for | Mr .Proposition 14. If L = • ν d and L = • µ d , then the critical locus Crit(L ) is in "correspondence" with Crit(L) ∩ Ω, meaning that

Table content: <table/>

Peer review (iclr2020):
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. Generally 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. My 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. Besides, 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. 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. The 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?