Spurious Valleys in Two-layer Neural Network Optimization Landscapes

Introduction

Modern machine learning applications involve datasets of increasing dimensionality, complexity and size, which in turn motivate the use of high-dimensional, non-linear models, as illustrated in many deep learning algorithms across computer vision, speech and natural language understanding. The prevalent strategy for learning is to rely on Stochastic Gradient Descent (SGD) methods, that typically operate on non-convex objectives. In this context, an outstanding goal is to provide a theoretical framework that explains under what conditions – relating input data distribution, choice of architecture and choice of optimization scheme – this setup will be successful.

Whereas there is a growing literature in analyzing the behavior of SGD on non-convex objectives (Soudry et al., 2017; Ji and Telgarsky, 2018; Gunasekar et al., 2018; Wilson et al., 2017), we focus here on properties of the optimization problem above that are algorithm independent. A common factor shared in the above cited works (and in common practice) is that overparametrisation of the model class (i.e. $P\gg 1$) often leads to improved performance, despite the potential increase in generalization error.

Our analysis focuses mostly on the class of one-hidden-layer neural networks, with a hidden layer of size $p$, and covers both empirical and population risk landscapes. More specifically, we look at presence (or absence) of spurious valleys, defined as connected components of the sub-level sets that do not contain a global minima. We define two quantities depending on the functional space spanned by neural networks of different widths: the upper intrinsic dimension, defined as the dimension of this linear space, and the lower intrinsic dimension, defined as the minimum number of hidden units to describe any element of the functional space. Upper and lower intrinsic dimensions define only two scenarios: either (i) they are both finite, enabling positive results; or (ii) they are both infinite, implying the negative results.

For Empirical Risk Minimization or polynomial activations, spurious valleys do not occur as long as the network is sufficiently over-parametrised. For the case of linear and quadratic activations, our results are (up to a constant factor) tight.

For non-polynomial non-negative activations, for any hidden width, we construct data distributions which yield spurious valleys with positive measure, whose value is arbitrarily far from the one of the global.

Finally, drawing on connections with random features expansions, we show that, even if spurious valleys may appear in general, their measure decreases as the width increases. This holds up to a low energy threshold, which approaches the global minimum at a rate inversely proportional to the hidden layer size (up to log factors).

A considerable amount of literature has attempted to characterize the landscape of the loss function (1) by studying its critical points. Global optimality results have been obtained for NN architectures with linear activations (Hardt and Ma, 2016; Kawaguchi, 2016; Yun et al., 2018), quadratic activations (Soltanolkotabi et al., 2017; Du and Lee, 2018) and some more general non-linear activations, under appropriate regularity assumptions (Soudry and Carmon, 2016; Nguyen and Hein, 2017; Feizi et al., 2017). Some other insights have been obtained by leveraging tools for complexity analysis of spin glasses (Choromanska et al., 2015) and random matrix theory (Pennington and Bahri, 2017). Other analysis involved studying goodness of the initialization of the parameter values ${\boldsymbol{\theta}}_{0}$ (Daniely et al., 2016; Safran and Shamir, 2016; Du et al., 2017) or other topological properties of the loss (1), such as connectivity of sub-level sets (Draxler et al., 2018; Freeman and Bruna, 2017).

Several other type of analysis of the convergence of NNs gradient-based optimization algorithms have been considered in the literature. For example, (Ge et al., 2017b) proved convergence of GD on a modified loss; (Shamir, 2018) compared optimization properties of residual networks with respect to linear models; in (Dauphin et al., 2014) it is argued that the issues arising in the optimization of NN architectures are due to the presence of saddle points in the loss function rather than spurious local minima. Optimization landscapes have also been studied in other contexts than from NNs training, such as non-convex low rank problems (Ge et al., 2017a), matrix completion (Ge et al., 2016), problems arising in semidefinite programming (Boumal et al., 2016; Bandeira et al., 2016) and implicit generative modeling (Bottou et al., 2017).

The rest of the paper is structured as follows. Section 2 formally introduces the notion of spurious valleys and explains why this is a relevant concept from the optimization point of view. It also defines the intrinsic dimensions of a network (Section 2.2). In Section 3 we state our main positive results (Theorem 8) and we discuss two settings where they bear fruit: polynomial activation functions and empirical risk minimization. Section 4 is dedicated to constructions of worst case scenarios for activation with infinite lower intrinsic dimension. We then show, in Section 5, that, even if spurious valleys may exist, they tend to be confined to regimes of low risk. Some conclusive discussion is reported in Section 6.

1 Notation

Preliminaries

The loss function $L({\boldsymbol{\theta}})$ is (in general) a non-convex object; it may present spurious (i.e. non global) local minima. In this work, we characterize $L({\boldsymbol{\theta}})$ by determining absence or presence of spurious valleys, as defined below.

Since, in practice, the loss (2) is minimized with a gradient descent based algorithm, then absence of spurious valleys is a desirable property, if we wish the algorithm to converge to an optimal parameter. It is easy to see that $L({\boldsymbol{\theta}})$ not having spurious valleys is implied by the following property:

${\boldsymbol{\theta}}_{1}\in\arg\min_{{\boldsymbol{\theta}}\in\Theta}L({\boldsymbol{\theta}})$

The function $t\in\mapsto L({\boldsymbol{\theta}}_{t})$ is non-increasing

As pointed out in (Freeman and Bruna, 2017), this implies that $L$ has no strict spurious (i.e. non global) local minima. The absence of generic (i.e. non-strict) spurious local minima is guaranteed if the path ${\boldsymbol{\theta}}_{t}$ is such that the function $L({\boldsymbol{\theta}}_{t})$ is strictly decreasing. For sake of clarity, we review these properties in the following lemma (the proof is reported in the Appendix E).

Be ${\boldsymbol{\theta}}\mapsto L({\boldsymbol{\theta}})$ a continuous function. Then, property P.1 implies absence of spurious valleys. In particular, this implies absence of strict spurious minima, and of (generally non-strict) spurious minima if property P.1 holds with strictly decreasing paths $t\mapsto L({\boldsymbol{\theta}}_{t})$. Conversely, presence of spurious valleys implies existence of spurious minima.

In the following, we prove absence of spurious valleys by proving that property P.1 holds. Intuitively, we should think about spurious valleys as regions of the parameter space from which it is impossible to ‘escape’ without ‘up-climbing’ the loss value.

Notice that for many activation functions used in practice (such as the ReLU $\sigma(z)=z_{+}$), the parameter ${\boldsymbol{\theta}}$ determining the function ${\boldsymbol{\Phi}}(\cdot;{\boldsymbol{\theta}})$ is determined up to the action of a symmetry group (e.g., in the case of the ReLU, $\sigma$ is a positive homogeneous function). This already prevents strict minima: for any value of the parameter ${\boldsymbol{\theta}}\in\Theta$ there exists a (often large) manifold $\mathcal{U}_{\boldsymbol{\theta}}\subset\Theta$ intersecting ${\boldsymbol{\theta}}$ along which the loss function is constant.

In the following, we consider the loss (2) defined for a generic distribution $({\mathbf{X}},{\mathbf{Y}})$. In case of a distribution with a finite number of atoms, this corresponds to empirical risk minimization (ERM), which is (usually) the regime where machine learning algorithms perform optimization. On the other hand, for a generic data distribution, this loss is what is called population loss, and corresponds to the actual objective that machine learning algorithms aim to minimize. In our work we are interested in analyzing not only the ERM case, but more general population losses. While we in fact focus on highly over-parametrised neural networks, we aim to provide results which apply to the regime where number of data points goes to infinity before the number of parameters.

2 Intrinsic dimension of a network

The main result of this work is to exploit that the property of absence of spurious valleys is related to the complexity of the functional space $V_{\sigma}=\{f=\Phi_{\boldsymbol{\theta}}\operatorname*{\,:\,}{\boldsymbol{\theta}}\in\Theta\}$ defined by the network architecture. We therefore define two measures of such complexity which we will use to show, respectively, positive and negative results in this regard.

$V_{\sigma,p}$ represents the space of (one-dimensional output) functions modeled by the network architecture and $\mathcal{R}_{2}(\sigma,n)$ to be the space of ($n$-dimensional) input data distributions for which the filter functions have finite second moment. We finally define

The $n$ level upper intrinsic dimension $\dim^{*}(\sigma,n)$ is defined as the dimension of the functional linear space $V_{\sigma}$. We note that if ${\mathbf{X}}\in\mathcal{R}_{2}(\sigma,n)$ is a r.v. with almost surely (a.s.) positive density w.r.t. the Lebesgue measure $dx$, then $\dim^{*}(\sigma,n)=\dim^{*}(\sigma,{\mathbf{X}})$.

The following lemma exhausts all the cases when the upper intrinsic dimension is not infinite.

Let $\sigma$ be a continuous activation function and ${\mathbf{X}}\in\mathcal{R}_{2}(\sigma,n)$ such that $\dim\left(L^{2}_{\mathbf{X}}\right)=\infty$. If $\sigma(z)=\sum_{k=0}^{d}a_{k}z^{k}$ is a polynomial, then

Otherwise (i.e. if $\sigma$ is not a polynomial) it holds $\dim^{*}(\sigma,{\mathbf{X}})=\infty$.

The proof of the above lemma is based on the universal approximation theorem (Leshno et al., 1993). We then define the lower intrinsic dimension, which corresponds to the concept of ‘how many hidden neurons are needed to represent a generic function of $V_{\sigma}$’.

Let $\sigma$ be a continuous activation function and ${\mathbf{X}}\in\mathcal{R}_{2}(\sigma,n)$ a r.v. We defineFor any subsets $V,W\subseteq L^{2}_{\mathbf{X}}$, we say that $V\subsetneq_{L^{2}_{\mathbf{X}}}W$ if $V\subsetneq W$ as subsets of $L^{2}_{\mathbf{X}}$ (and similar with other inclusions or equalities).

If $\dim_{*}(\sigma,{\mathbf{X}})$ is finite, then it corresponds to the minimum number of hidden neurons which are needed to represent any function of $V_{\sigma}$ with the NN architecture (3). Clearly, this implies that

for every continuous activation function $\sigma$ and any ${\mathbf{X}}\in\mathcal{R}_{2}(\sigma,n)$. As with the upper instrinsic dimension, we note that if ${\mathbf{X}}\in\mathcal{R}_{2}(\sigma,n)$ is a r.v. with a.s. positive density w.r.t. the Lebesgue measure $dx$, then $\dim_{*}(\sigma,n)=\dim_{*}(\sigma,{\mathbf{X}})$.

In the case of homogeneus polynomial activations $\sigma(z)=z^{k}$ with $k\geq 1$ integer, the level $n$ lower dimension of $\sigma$ coincides with the notion of (maximal) symmetric tensor rank.

Let $\sigma(z)=z^{k}$, with $k$ positive integer. Then

Finally, the next lemma implies that for most non-polynomial activation functions practical interest, the lower intrinsic dimension $\dim_{*}(\sigma,n)$ is infinite.

The proof of the above Lemma is based on Hermite decomposition and on the correspondence between one-hidden-layer nets and symmetric tensors (Mondelli and Montanari, 2018).

Finite intrinsic dimension and absence of spurious valleys

In this section we provide our positive results. Essentially they state that if the width of the network matches the dimension of the functional space $V_{\sigma}$ spanned by its filter functions, then no spurious valleys exist. We first provide the main result (Theorem 8) in a general form, which allows a straight-forward derivation of two cases of interest: empirical risk minimization (Corollary 9) and polynomial activations (Corollary 10).

The proof consists of showing that we can construct a descent path verifying property P.1 starting from any parameters ${\boldsymbol{\theta}}$. The construction can be articulated in two main parts. First, we show that we can map the starting parameter ${\boldsymbol{\theta}}_{0}=({\mathbf{U}}_{0},{\mathbf{W}}_{0})$ to another parameter ${\boldsymbol{\theta}}_{1/2}=({\mathbf{U}}_{1/2},{\mathbf{W}}_{1/2})$ such that the functions $\left\{{\mathbf{x}}\mapsto\sigma(\langle{\mathbf{w}}_{1/2,i},{\mathbf{x}}\rangle)\right\}_{i\in[p]}$ form a basis of $V_{\sigma}$. It follows that there exists a minimal function ${\mathbf{f}}\in V_{\sigma}^{m}\doteq\left\{(f_{1},\dots,f_{m})\operatorname*{\,:\,}f_{i}\in V_{\sigma}\right\}$, i.e.

which can be represented as ${\mathbf{f}}={\boldsymbol{\Phi}}(\cdot;{\boldsymbol{\theta}}_{1}=({\mathbf{U}}_{1},{\mathbf{W}}_{1/2}))$ for some ${\mathbf{U}}_{1}$. The second part of the path can be thus taken as $t\mapsto(1-t){\mathbf{U}}_{1/2}+t{\mathbf{U}}_{1}$: as the loss function is convex, this is descent path.

The above result can be interpreted as follows: if the network is such that any of its output units $\Phi_{i}$ can be chosen from the whole linear space spanned by its filter functions $V_{\sigma}$, then the associated optimization problem is such that there always exists a descent path to an optimal solution, for any initialization of the parameters.

Applying the observations in Section 2.2 describing the cases of finite intrinsic dimension, we immediately get the following corollaries.

admits no spurious valleys in the over-parametrized regime $p\geq N$.

This results was already shown in (Livni et al., 2014). The only difference with our result is that we allow for rank degeneracy in the matrix $\sigma\left({\mathbf{W}}\left[{\mathbf{x}}_{1}|\cdots|{\mathbf{x}}_{N}\right]\right)$. However, its proof illustrates the danger of studying empirical risk minimization landscapes in over-parametrised regimes, since it bypasses all the geometric and algebraic properties needed in the population risk setting - which may be more relevant to understand the generalization properties of the model.

Under the hypothesis of Corollary 10 with $p=O(n^{d})$, a generic function of $V_{\sigma}$, ${\boldsymbol{\Phi}}({\mathbf{x}};{\boldsymbol{\theta}})={\mathbf{u}}^{T}\sigma({\mathbf{W}}{\mathbf{x}})$, can be also represented, for some ${\boldsymbol{\gamma}}={\boldsymbol{\gamma}}({\boldsymbol{\theta}})$, in the generalized linear form

with ${\boldsymbol{\varphi}}({\mathbf{x}})=(x_{k_{1}}\cdots x_{k_{j}})_{\{1\leq k_{1}\leq\dots\leq k_{j}\leq n,j\in[d]\}}$. The parameters ${\boldsymbol{\theta}}$ and ${\boldsymbol{\gamma}}$ differ for their dimensions:

One would therefore like Corollary 10 to hold also (at least) for $p\geq O(n^{d-1})$. In the next section we address this problem for the linear activation $\sigma(z)=z$ and the quadratic activation $\sigma(z)=z^{2}$.

1 Improved over-parametrization bounds for homogeneous polynomial activations

The over-parametrization bounds obtained in Corollary 10 are quite non-desiderable in practical applications. We show that they can indeed be improved, for the case of linear and quadratic networks.

Linear networks have been considered as a first order approximation of feed-forward multi-layers networks (Kawaguchi, 2016). It was shown, in several works (Kawaguchi, 2016; Freeman and Bruna, 2017; Yun et al., 2018), that, for linear networks of any depth

1.2 Quadratic networks case

Quadratic activations $\sigma(z)=z^{2}$ have been considered in the literature (Livni et al., 2014; Du and Lee, 2018; Soltanolkotabi et al., 2017) as second order approximation of general non-linear activations. Corollary 10 says that, if $p\geq n(n+1)/2$, the loss function (2) admits no spurious valleys. In the following theorem we relax the over-parametrisation requirement and show that $p>2n$ is sufficient for the statement to hold, in the case of square loss functions and one dimensional output ($m=1$).

We notice that $\Phi(\cdot;{\boldsymbol{\theta}})$ can also be represented by a NN $\Phi(\cdot;\hat{{\boldsymbol{\theta}}})$ with $n$ hidden units; indeed, if $\sum_{i=1}^{n}\sigma_{i}{\mathbf{v}}_{i}{\mathbf{v}}_{i}^{T}$ is the SVD of $\sum_{i=1}^{p}u_{i}{\mathbf{w}}_{i}{\mathbf{w}}_{i}^{T}$, then $\Phi({\mathbf{x}};{\boldsymbol{\theta}})=\langle\sum_{i=1}^{n}\sigma_{i}{\mathbf{v}}_{i}{\mathbf{v}}_{i}^{T},{\mathbf{x}}{\mathbf{x}}^{T}\rangle_{F}$. Therefore $p\geq n$ is sufficient to describe any element in $V_{\sigma}$. A path to the symmetric matrix defining the optimal network is then constructed by mapping the above decomposition defined by the standard form of the network.

The factor $2$ in the statement is due to some technicalities in the proof, but a more involved proof should be able to extend the result to the regime $p\geq n$. The extension of such mechanism for higher order tensors (appearing as a result of multiple layers or high-order polynomial activations) using tensor decomposition also seems possible and is left for future work.

The same optimization landscape has been considered in the works (Soltanolkotabi et al., 2017) and (Du and Lee, 2018). In the first work, the authors show absence of spurious minima for the case of $p\geq 2n$ and of ERM (loss evaluated on $N$ data points), but for fixed output layer weights; under some assumption on the output layer weights, the result is shown to still hold for $p\geq n$, if $n\leq N\leq O(n^{2})$. This last condition can be removed by considering the regularized loss with non-zero weight decay, as shown in (Du and Lee, 2018); in the same work, the authors also proved absence of spurious minima in the case $p<n$ and $p(p+1)\geq 2N$ for a randomly regularized loss (with high probability).

By relaxing the statement to absence of spurious valleys, we showed that this holds for the square loss (both in population and ERM setting) and the optimisation problem over both layer weights if $p>2n$.

1.3 Lower to upper intrinsic dimension gap

Infinite intrinsic dimension and presence of spurious valleys

This section is devoted to the construction of worst-case scenarios for non-over parametrised networks. The main result (Theorem 13) essentially states that, for networks with width smaller than the lower intrinsic dimension defined above, spurious valleys can be created by choosing adversarial data distributions. We then show how this implies negative results for under-parametrized polynomial architectures and a large variety of architectures used in practice.

and any path ${\boldsymbol{\theta}}:\to\Theta$ such that ${\boldsymbol{\theta}}_{0}\in\Omega$ and ${\boldsymbol{\theta}}_{1}$ is a global minima verifies

Equation (5) in Theorem 13 says that any local descent algorithm, if initialized in ${\boldsymbol{\theta}}_{0}\in\Omega$, at its best it will only be able to produce a final parameter value which is at least $M$ far from optimality. Equation (6) implies that any path starting from parameter belonging to $\Omega$ must ‘up-climb’ at least $M/2$ in the loss value. In the following we refer to such property, as stated in Theorem 13, by saying that the loss function has arbitrarily bad spurious valleys. Note that this result ensures that spurious valleys have positive Lebesgue measure, so there is a positive probability that gradient descent methods initialized with a measure that is absolutely continuous with respect to Lebesgue will get stuck in a bad local minima.

Applying the observations describing the values of the lower intrinsic dimension for different activation functions, we get the following corollaries.

Consider the case of activation $\sigma(z)=z^{2k}$ with $k\geq 1$ integer. For one-hidden-layer NNs ${\boldsymbol{\Phi}}({\mathbf{x}};{\boldsymbol{\theta}})={\mathbf{U}}\sigma({\mathbf{W}}{\mathbf{x}})$, if $n\geq 2$ and the hidden layer width satisfies

The ReLU activation function $\sigma(z)=z_{+}$ and some relaxations of it, such as softplus activation functions $\sigma(z)=\beta^{-1}\log\left(1+e^{\beta z}\right)$, with $\beta>0$;

The sigmoid activation function $\sigma(z)=(1+e^{-z})^{-1}$ and the approximating erf function $\sigma(z)=2/\pi\int_{0}^{z}e^{-u}\,du$, which represents an approximation to the sigmoid function.

Several works showed existence of spurious minima: (Safran and Shamir, 2017) showed counterexamples under Gaussian input distributions, for $p=n-1\in\{8,\dots,19\}$, using a computer-assisted proof; (Swirszcz et al., 2016) and (Zhou and Liang, 2017) provided a few numerical examples; (Yun et al., 2018) showed existence of spurious minima for ReLU-like activations under non-realizability, and provided counterexamples for smooth activations. For any number of hidden neurons $p$, we give a (constructive) proof of existence of a data distribution which creates spurious valleys, under the only assumption of non-negative continuous activation function. We also remark that while in the above works the authors proved existence of spurious local minima, we prove that, in fact, arbitrarily bad spurious valleys can exist, which is a stronger negative characterization.

The results of this section can be interpreted as worst-case scenarios for the problem of optimizing (2). We showed that, even for simple one-hidden-layer neural network architectures with non-linear activation functions used in practice (such as ReLU), global optimality results can not hold, unless we make some assumptions on the data distributions.

Typical spurious valleys and low-energy barriers

In the previous section it was shown that whenever the number of hidden units $p$ is below the lower intrinsic dimension, then one can show worst-case data distributions that yield a landscape with arbitrarily bad spurious valleys. A natural follow-up question is thus to consider the complexity of the energy landscape in a typical scenario, defined in terms of both parameter initialisation (how likely are descent algorithms to fall into a spurious valley?) and energy value (how deep are typical spurious valleys?).

In this section, we study the energy landscape under generic data distributions in case of homogeneous activation, and show that, although spurious valleys may appear, they tend do so below a certain energy level, controlled by the decay of the spectral decomposition of the kernel defined by the activation function and by the amount of parametrisation $p$. This offers a first glimpse at the empirical success of local descent algorithms in conditions where $p$ is indeed below the intrinsic dimension.

We consider oracle square loss functions of the form

If $f^{*}$ can be written as a one-hidden-layer neural network with an arbitrary number of hidden units, that is

for some measure $\mu$ and weight function $\rho$, then a possible approach to find a proper approximation of $f^{*}$ is through random features sampling (Rahimi and Recht, 2008). Applying some recent results (Bach, 2017b) relating random features expansions with kernel quadrature rules, we show that this implies the following statement: as the network width increases, spurious valleys tend to be confined to decreasingly low loss value. In this regime, large loss barriers are therefore avoided with high probability over initialization of the parameters. The statement is made more rigorous in the following:

with probability greater or equal then $1-\delta$, for every $\lambda,\delta\in(0,1)$.

with probability greater or equal then $1-e^{-O(p^{\delta})}$ for every $\delta\in(0,1)$.

Assume that $f^{*}$ admits the representation

for some density $\rho$. If ${\mathbf{w}}_{i}\sim d\tau$, $i\in[p]$, are drawn i.i.d., we have

Many recent works leveraged arguments based on random features to explain the empirical success of local descent algorithms to train neural networks (see e.g. (Jacot et al., 2018; Allen-Zhu et al., 2018; Oymak and Soltanolkotabi, 2019; Yehudai and Shamir, 2019; Ma et al., 2019; Du et al., 2018)). In Theorem 16, we used this type of technique to show properties of the optimization landscape. The main limitation shared by our and the cited results is the gap between the regimes in which the apply (high over-parametrized NNs) and the regimes attained in practice. A current important direction is to understand the dynamics of neural networks training over kernel approximation and to extend such results to moderatly over-parametrized architectures.

Future directions

We considered the problem of characterizing the loss surface of neural networks from the perspective of optimization, with the goal of deriving weak certificates that enable - or prevent - the existence of descent paths towards global minima.

The topological properties studied in this paper, however, do not yet capture fundamental aspects that are necessary to explain the empirical success of deep learning methods. We identify a number of different directions that deserve further attention.

The positive results presented above rely on being able to reduce the network to the case when (convex) optimization over the output layer is sufficient to reach optimal weight values. A better understanding of first layer dynamics needs to be carried out. Moreover, in such positive results we only proved non-existence of (high) energy barriers. While this is an interesting property from the optimization point of view, it is also not sufficient to guarantee convergence of local descent algorithms. Another informative property of the loss function that should be addressed in future works is the existence of local descents in non optimal points: for every ${\boldsymbol{\theta}}_{0}\in\Theta$ non optimal and any neighborhood $\mathcal{U}\subseteq\Theta$ of ${\boldsymbol{\theta}}_{0}$, there exists ${\boldsymbol{\theta}}\in\mathcal{U}$ such that $L({\boldsymbol{\theta}})<L({\boldsymbol{\theta}}_{0})$. More generally, our present work is not informative on the performance of gradient descent in the regimes with no spurious valley.

The other very important point to be addressed in future is how to extend the above results to architectures of more practical interest. Depth and the specific linear structure of Convolutional Neural Networks, critical to explain the excellent empirical performance of deep learning in computer vision, text or speech, need to be exploited, as well as specific design choices such as Residual connections and several normalization strategies – as done recently in (Shamir, 2018) and (Santurkar et al., 2018) respectively. This also requires making specific assumptions on the data distribution, and is left for future work.

We would like to thank Gérard Ben Arous and Léon Bottou for fruitful discussions, and Jean Ponce for valuable comments and corrections of the original version of this manuscript. LV would also like to thank Jumageldi Charyyev for fruitful discussions on the proofs of several propositions and Andrea Ottolini for valuable comments on a previous version of this manuscript. LV was partially supported by NSF grant DMS-1719545. ASB was partially supported by NSF grants DMS-1712730 and DMS-1719545, and by a grant from the Sloan Foundation. JB acknowledges the partial support by the Alfred P. Sloan Foundation, NSF RI-1816753, NSF CAREER CIF 1845360, and Samsung Electronics.

References

A Proofs of Section 3

A.1 Proof of Theorem 8

Proof For sake of simplicity, in the following we write $\psi_{\mathbf{w}}$ for $\psi_{\sigma,{\mathbf{w}}}$ and $V$ for $V_{\sigma,{\mathbf{X}}}$. Let ${\boldsymbol{\psi}}_{{\mathbf{w}}_{1}},\dots,{\boldsymbol{\psi}}_{{\mathbf{w}}_{q}}$ be a basis of $V$. If ${\boldsymbol{\psi}}_{\mathbf{w}}=\sum_{i=1}^{q}\alpha_{i}{\boldsymbol{\psi}}_{{\mathbf{w}}_{i}}$ and $\psi_{\mathbf{v}}=\sum_{j=1}^{q}\beta_{j}{\boldsymbol{\psi}}_{{\mathbf{w}}_{j}}$, then we can define a scalar product on $V$ as

The non-trivial fact captured by Theorem 8 is the following: when the capacity of network is large enough to match a generalized linear model, but still finite, then the problem of optimizing the loss function (2), which is in general a highly non-convex object, satisfies an interesting optimization property in view of the local descent algorithms which are used in practice to solve it.

If we define ${\mathbf{U}}_{1}$ such that (denoting ${\mathbf{u}}_{1,i}$ the $i$-th row of ${\mathbf{U}}_{1}$)

This shows that property P.1 holds and therefore it proves the theorem.

A.2 Proof of Theorem 11

where ${\mathbf{M}}$ is a PSD matrix and, for every matrix ${\mathbf{W}}$, ${\mathbf{P}}_{{\mathbf{W}}}$ denotes the orthogonal projection on the rows of ${\mathbf{W}}$, that is ${\mathbf{P}}_{{\mathbf{W}}}={\mathbf{W}}^{\dagger}{\mathbf{W}}$ (see Lemma 28). Therefore it is equivalent for the path ${\boldsymbol{\theta}}_{t}=({\mathbf{q}}({\mathbf{W}}_{t}),{\mathbf{W}}_{t})$ to be such that the function

Proof While it is geometrically intuitive that the results should hold, we derive a constructive proof. We start by noticing that if $[{\mathbf{W}}]\in G(p,n)$ and ${\mathbf{w}}_{1},\dots,{\mathbf{w}}_{p}$ is an orthonormal basis of $[{\mathbf{W}}]$, then

Moreover, if ${\mathbf{M}}=\sum_{j=1}^{n}\sigma_{i}{\mathbf{v}}_{j}{\mathbf{v}}_{j}^{T}$ is the SVD of ${\mathbf{M}}$, where $\sigma_{1}\geq\dots\geq\sigma_{n}\geq 0$, then (11) can be written as

where ${\mathbf{w}}_{1}^{j}={\mathbf{v}}_{1},\dots,{\mathbf{w}}_{j}^{j}={\mathbf{v}}_{j},{\mathbf{w}}_{j+1}^{j},\dots,{\mathbf{w}}_{p}^{j}$ is an orthonormal basis of $[{\mathbf{W}}^{j}]$, for $j\in[0,p]$. Moreover, the paths $[{\mathbf{W}}^{i}_{t}]$ are such that the functions $t\in\mapsto f[{\mathbf{W}}^{i}_{t}]$ are non-decreasing. Such paths are defined as follows. Let $i\in[0,p-1]$ and consider

Then we complete ${\mathbf{v}}_{1},\dots,{\mathbf{v}}_{i},{\mathbf{u}}_{i+1}^{i}$ to an orthonormal basis of $[{\mathbf{W}}^{i}]$:

We call ${\mathbf{w}}^{i+1}_{j}={\mathbf{u}}_{j}^{i}$ for $j\in[i+2,p]$ and we define

for $\mu_{i+1}=\langle{\mathbf{u}}_{i+1}^{i},{\mathbf{v}}_{i+1}\rangle$. The fact that the function $t\in\mapsto f[{\mathbf{W}}^{i+1}_{t}]$ is non-decreasing can be proved by noticing that

and by showing that the derivative of the RHS is greater or equal than . This concludes the proof of the lemma.

Lemma 20 holds even if we drop the assumption ${\boldsymbol{\Sigma}}_{\mathbf{X}}={\mathbf{I}}$.

Proof [Proof of Theorem 11] Consider a linear network ${\boldsymbol{\Phi}}({\mathbf{x}};{\boldsymbol{\theta}})$ as in (12), where

We select $p_{s}=\min_{i\in[K]}p_{k}$. Then the network can be written as

in a continuous way. Since $p_{s}$ was to chosen as the minimum, it also holds that

Therefore this is a suitable path and this concludes the proof of the theorem.

A.3 Proof of Theorem 12

This shows that property P.1 holds and so it concludes the proof of Theorem 12.

To conclude the proof we just need to prove the following lemmas.

Let ${\boldsymbol{\theta}}=({\mathbf{u}},{\mathbf{W}})$ be an initial parameter and ${\boldsymbol{\theta}}^{*}=({\mathbf{u}}^{*},{\mathbf{W}}^{*})$ be as in step 1 of the proof of Theorem 12. Then there exists a continuous path ${\boldsymbol{\theta}}_{t}$ from ${\boldsymbol{\theta}}$ to ${\boldsymbol{\theta}}^{*}$ such that the loss $L({\boldsymbol{\theta}}_{t})$ is constant (as a function of $t$).

Proof Notice that we can assume ${\mathbf{u}}\in\{-1,0,1\}^{p}$. This can be done simply scaling (continuously) each row ${\mathbf{w}}_{k}$ of ${\mathbf{W}}$ by $\sqrt{|u_{k}|}$. Assume first that ${\mathbf{u}}\in\{\pm 1\}^{p}$. The general case ($u_{k}=0$ for some $k$) is addressed in Remark 26. The sought path ${\boldsymbol{\theta}}_{t}$ can be constructed by iterating two steps (a finite amount of times). First we select a row ${\mathbf{w}}_{k}$ and construct a continuous path that maps this row to one of the ${\mathbf{w}}^{*}_{i}$; then we orthogonalize (w.r.t. such ${\mathbf{w}}^{*}_{i}$) the rest of rows ${\mathbf{w}}_{j}$, $j\neq k$. These two steps are constructed so that ${\mathbf{A}}$ never changes and therefore the loss is constant. The first step is described in Lemma 24, while the second is detailed in Lemma 25. At this point the parameter ${\boldsymbol{\theta}}=({\mathbf{u}},{\mathbf{W}})$ verifies $u_{i}=u_{i}^{*}$, ${\mathbf{w}}_{i}={\mathbf{w}}_{i}^{*}$ and ${\mathbf{w}}_{j}\in\langle\{{\mathbf{w}}_{i}^{*}\}\rangle^{\perp}$ for $j\neq k$. In particular it holds

Therefore, an induction step applied on the reduced parameter values

The first step described in the Proof of Lemma 23 can be performed when $p>2n$.

Proof Let $E_{+}=\{k\in[p]\operatorname*{\,:\,}u_{k}=1\}$, $E_{-}=\{k\in[p]\operatorname*{\,:\,}u_{k}=-1\}$ and $p_{+}=\lvert E_{+}\rvert$, $p_{-}=\lvert E_{-}\rvert$. Accordingly we define

The main step of the proof is to observe that ${\mathbf{A}}$ (and therefore the loss) is invariant to the action of orthogonal matrices ${\mathbf{Q}}_{+}\in SO(p_{+})$ and ${\mathbf{Q}}_{-}\in SO(p_{-})$. So, if ${\mathbf{Q}}_{+}(t)$ (resp. ${\mathbf{Q}}_{-}(t)$) is a continuous paths in $SO(p_{+})$ (resp. in $SO(p_{-})$) starting at the identity, acting on ${\mathbf{W}}$ as

Assume that after the step in Lemma 24, the first row of ${\mathbf{W}}_{+}$ (resp. ${\mathbf{W}}_{-}$) is given by ${\mathbf{w}}_{i}^{*}$. Then we can map all the other rows of ${\mathbf{W}}$ to be orthogonal to ${\mathbf{w}}_{i}^{*}$, while keeping ${\mathbf{A}}$ constant.

Proof To simplify the notation we assume (w.l.o.g.) that ${\mathbf{w}}_{i}^{*}={\mathbf{w}}_{1}^{*}$ and that

such that ${\mathbf{w}}_{2,1},\dots,{\mathbf{w}}_{p,1}\in\langle\{{\mathbf{w}}_{1}^{*}\}\rangle^{\perp}$. To do this we simply take

If ${\mathbf{A}}_{t}=\sum_{k=1}^{p}u_{k,t}{\mathbf{w}}_{k,t}{\mathbf{w}}_{k,t}^{T}$, we can show that there exists a choice of $u_{1,t}$ such that ${\mathbf{A}}_{t}={\mathbf{A}}$ for all $t\in$. It holds that

Therefore, ${\mathbf{A}}_{t}={\mathbf{A}}$ constant. This concludes the proof of the lemma.

In the proof of Lemma 23, we assumed that (after rescaling) ${\mathbf{u}}\in\{\pm 1\}^{p}$. In general, it could be that $u_{k}=0$ for some $k$. In this case we can first map the corresponding vectors ${\mathbf{w}}_{k}$ to ${\mathbf{0}}$ and the map such $u_{k}$ to $1$, without affecting the loss.

B Proofs of Section 4

(see the remark at the end of the proof). The r.v. $Y$ is taken to be $Y=g_{1}({\mathbf{X}})-g_{2}({\mathbf{X}})$, where $g_{2}=\beta\psi_{\sigma,{\mathbf{v}}}\in V_{\sigma,1}^{+}$, $\beta>0$, ${\mathbf{v}}={\mathbf{e}}_{n}$, and $g_{1}=\sum_{i=1}^{p}\alpha_{i}\psi_{\sigma,{\mathbf{v}}_{i}}\in V_{\sigma,p}^{+}$, ${\boldsymbol{\alpha}}\in(0,\infty)^{p}$, ${\mathbf{v}}_{i}\in\langle\{{\mathbf{e}}_{n}\}\rangle^{\perp}$, $i\in[p]$, is such that

Notice that, for every path ${\boldsymbol{\theta}}:t\in\mapsto{\boldsymbol{\theta}}_{t}\in\Theta$ such that $\Phi(\cdot;{\boldsymbol{\theta}}_{0})\in V_{\sigma,p}^{+}$ and $\Phi(\cdot;{\boldsymbol{\theta}}_{1})\in V_{\sigma,(p-1,1)}$, there exists $t_{0}\in(0,1)$ such that $\Phi(\cdot;{\boldsymbol{\theta}}_{t_{0}})\in V_{\sigma,p-1}^{+}$. Consider the lifted square loss function $L:V_{\sigma,p}\to[0,\infty)$ defined as

Given $M>0$, up to multiply $g_{1}$ by a positive constant, it holds that

To finish the proof, consider $\mathcal{U}=\{{\boldsymbol{\theta}}=({\mathbf{u}},{\mathbf{W}})\in\Theta\operatorname*{\,:\,}{\mathbf{u}}\in(0,\infty)^{p}\}$ and ${\boldsymbol{\theta}}^{*}\in\mathcal{U}$ such that

Then, (by continuity of $L$) there exists a neighborhood ${\boldsymbol{\theta}}^{*}\in\Omega\subset\mathcal{U}$ such that $\sup_{{\boldsymbol{\theta}}\in\Omega}L({\boldsymbol{\theta}})\leq L({\boldsymbol{\theta}}^{*})+M/2$. The set $\Omega$ then verifies the statement of the theorem.

In the proof of Theorem 13 we used the fact that, if $p\geq 1$ verifies $p\leq\frac{1}{2}\dim_{*}(\sigma,n)$, then there exist ${\mathbf{X}}\in\mathcal{R}_{2}(\sigma,n)$ such that $\overline{V_{\sigma,p-1}^{+}}\neq V_{\sigma,p}^{+}$ (in the $L^{2}_{\mathbf{X}}$ metric). Assume ${\mathbf{X}}$ is a $n$-dimensional standard Gaussian variable. Consider first the case $\sigma(z)=z^{k}$. If $k=2$, then

C Proof of Theorem 16

Proof If we denote by $d\mu$ the probability distribution of ${\mathbf{X}}$, the continuous function

By convexity of $L$, the function $t\in\mapsto L({\boldsymbol{\theta}}_{t})$ is non-increasing and it holds that

Applying Proposition 1 from Bach (Bach, 2017b), it holds that

with probability greater or equal than $1-\delta$, where

for every $\varepsilon\geq\sqrt{v(p)}$, with $v(p)=C^{2}/p$. The result follows by taking $\varepsilon=v(p)^{1/2}+p^{\delta/2-1/2}$.

D Proofs of Section 2.2

and a sequence of functions $\{h_{m}\}_{m\geq 1}\subset V_{\sigma}$ such that

(see Lemma 1 from (Mondelli and Montanari, 2018)). Since $\sigma$ is not polynomial and $n>1$, $V_{\sigma,p}\neq V_{\sigma,p+1}$, where

E Proofs of Additional Lemmas

Be ${\boldsymbol{\theta}}\mapsto L({\boldsymbol{\theta}})$ a continuous function. Then, property P.1 implies absence of spurious valleys. In particular, this implies absence of strict spurious minima, and of (generally non-strict) spurious minima if property P.1 holds with strictly decreasing paths $t\mapsto L({\boldsymbol{\theta}}_{t})$. Conversely, presence of spurious valleys implies existence of spurious minima.

Proof Assume that property P.1 holds. Consider any value $c>0$ such that $\Omega_{L}(c)$ is non-empty and let $\mathcal{U}$ be a connected component of $\Omega_{L}(c)$. Given a point ${\boldsymbol{\theta}}\in\mathcal{U}$ there exists a path from ${\boldsymbol{\theta}}$ satisfying property P.1. This means that $\mathcal{U}$ contains a global minima, and therefore it can not be a spurious valley. Similarly, assume that property P.1 holds with strictly decreasing paths and that the function $L$ admits a strict local minima. This means that there exists a point ${\boldsymbol{\theta}}_{0}$ such that $\min_{\boldsymbol{\theta}}L({\boldsymbol{\theta}})<L({\boldsymbol{\theta}}_{0})<L({\boldsymbol{\theta}})$ for all ${\boldsymbol{\theta}}$ in $B_{\epsilon}({\boldsymbol{\theta}})$, for some $\epsilon>0$. But this implies that for any path $t\in\mapsto{\boldsymbol{\theta}}_{t}$ if holds $L({\boldsymbol{\theta}}_{t})>L({\boldsymbol{\theta}}_{0})$ for some $t>0$ sufficiently small, a contradiction. To see the last point, assume that there exist spurious valleys and consider $\mathcal{U}$ a connected component of $\Omega_{L}(c)$ for some $c>0$. Then ${\boldsymbol{\theta}}^{*}\in\operatorname*{arg\,min}_{\boldsymbol{\theta}}L({\boldsymbol{\theta}})$ is a spurious minima.

Similarly, one solution to the optimization problem

where ${\mathbf{K}}=({\boldsymbol{\Sigma}}_{\mathbf{X}})^{1/2}$ and ${\mathbf{M}}={\mathbf{K}}^{-1}{\boldsymbol{\Sigma}}_{{\mathbf{X}}{\mathbf{Y}}}{\boldsymbol{\Sigma}}_{{\mathbf{Y}}{\mathbf{X}}}{\mathbf{K}}^{-1}$. If ${\mathbf{M}}=\sum_{i=1}^{n}\lambda_{i}{\mathbf{v}}_{i}{\mathbf{v}}_{i}^{T}$ is the SVD of ${\mathbf{M}}$, the quantity (22) is minimized over ${\mathbf{W}}$ for $({\mathbf{W}}{\mathbf{K}})^{\dagger}({\mathbf{W}}{\mathbf{K}})=\sum_{i=1}^{p\wedge n}{\mathbf{v}}_{i}{\mathbf{v}}_{i}^{T}$.

Proof The first part of the lemma can be shown by writing problem (19) as

Now assume that ${\boldsymbol{\Sigma}}_{\mathbf{X}}$ is invertible; let ${\mathbf{K}}=({\boldsymbol{\Sigma}}_{\mathbf{X}})^{1/2}$ and ${\mathbf{M}}={\mathbf{K}}^{-1}{\boldsymbol{\Sigma}}_{{\mathbf{X}}{\mathbf{Y}}}{\boldsymbol{\Sigma}}_{{\mathbf{Y}}{\mathbf{X}}}{\mathbf{K}}^{-1}$. Then it holds

Let $X_{1},\dots,X_{n}$ be independent zero-mean r.v.’s taking values in a separable Hilbert space such that $\lVert X_{i}\rVert\leq c_{i}$ with probability one and denote $v=\sum_{i=1}^{n}c^{2}_{i}$. Then, for all $t\geq v$, it holds

Proof The proof can be found in (Boucheron et al., 2013), Example 6.3.