Spurious Local Minima are Common in Two-Layer ReLU Neural Networks

Introduction

One of the biggest mysteries of deep learning is why neural networks are successfully trained in practice using gradient-based methods, despite the inherent non-convexity of the associated optimization problem. For example, non-convex problems can have poor local minima, which will cause any local search method (and in particular, gradient-based ones) to fail. Thus, it is natural to ask what types of assumptions, in the context of training neural networks, might mitigate such problems. For example, recent work has shown that other non-convex learning problems, such as phase retrieval, matrix completion, dictionary learning, and tensor decomposition, do not have spurious local minima under suitable assumptions, in which case local search methods have a chance of succeeding (e.g., (Ge et al., 2015; Sun et al., 2015; Ge et al., 2016; Bhojanapalli et al., 2016)). Is it possible to prove similar positive results for neural networks?

In this paper, we focus on perhaps the simplest non-trivial ReLU neural networks, namely predictors of the form

Note that here, the choice $\mathbf{w}_{i}=\mathbf{v}_{\sigma(i)}$ (for all $i=1,\ldots,k$ and any permutation $\sigma$) is a global minimum with zero expected loss. Several recent papers analyzed such objectives, in the hope of showing that it does not suffer from spurious local minima (see related work below for more details).

Our main contribution is to prove that unfortunately, this conjecture is false, and that Eq. (1) indeed has spurious local minima once $6\leq k\leq 20$. Moreover, this is true even if the dimension is unrestricted, and even if we assume that $\mathbf{v}_{1},\ldots,\mathbf{v}_{k}$ are orthonormal vectors. In fact, since in high dimensions randomly-chosen vectors are approximately orthogonal, and the landscape of the objective function is robust to small perturbations, we can show that spurious local minima exist for nearly all neural network problems as in Eq. (1), in high enough dimension (with respect to, say, a Gaussian distribution over $\mathbf{v}_{1},\ldots,\mathbf{v}_{k}$). Moreover, we show experimentally that these local minima are not pathological, and that standard gradient descent can easily get trapped in them, with a probability which seems to increase towards $1$ with the network size.

Our proof technique is a bit unorthodox. Although it is possible to write down the gradient of Eq. (1) in closed form (without the expectation), it is not clear how to get analytical expressions for its roots, and hence characterize the stationary points of Eq. (1). As far as we know, an analytical expression for the roots might not even exist. Instead, we employed the following strategy: We ran standard gradient descent with random initialization on the objective function, until we reached a point which is both suboptimal (function value being significantly higher than ); approximate stationary (gradient norm very close to ); and with a strictly positive definite Hessian (with minimal eigenvalue significantly larger than ). We use a computer to verify these conditions in a formal manner, avoiding floating-point arithmetic and the possibility of rounding errors. Relying on these numbers, we employ a Taylor expansion argument, to show that we must have arrived at a point very close to a local (non-global) minimum of Eq. (1), hence establishing the existence of such minima.

On the more positive side, we show that an additional over-parameterization assumption appears to be very effective in mitigating these local minima issues: Namely, we use a network larger than that needed with unbounded computational power, and replace Eq. (1) with

where $n>k$. In our experiments with $k,n$ up to size $20$, we observe that whereas $n=k$ leads to plenty of local minima, $n=k+1$ leads to much fewer local minima, whereas no local minima were encountered once $n\geq k+2$ (although those might still exist for larger values of $k,n$ than those we tried). Thus, although Eq. (1) has local minima, we conjecture that Eq. (2) might still be proven to have no bad local minima, but this would necessarily require $n$ to be sufficiently larger than $k$.

The paper is structured as follows: After surveying related work below, we provide our main results and proof ideas in Sec. 2. Sec. 3 provide additional experimental details about the local minima found, as well empirical evidence about the likelihood of reaching them using gradient descent. Detailed proofs are in Sec. 4.

There is a large and rapidly increasing literature on the optimization theory of neural networks, surveying all of which is well outside our scope. Thus, in this subsection, we only briefly survey the works most relevant to ours.

We begin by noting that when minimizing the average loss over some arbitrary finite dataset, it is easy to construct problems where even for a single neuron ($k=1$ in Eq. (1)), there are many spurious local minima (e.g., (Auer et al., 1996; Swirszcz et al., 2016)). Moreover, the probability of starting at a basin of such local minima is exponentially high in the dimension (Safran and Shamir, 2016). On the other hand, it is known that if the network is over-parameterized, and large enough compared to the data size, then there are no local minima (Poston et al., 1991; Livni et al., 2014; Haeffele and Vidal, 2015; Zhang et al., 2016; Soudry and Carmon, 2016; Soltanolkotabi et al., 2017; Nguyen and Hein, 2017; Boob and Lan, 2017). In any case, neither these positive nor negative results apply here, as we are interested in the expected (population) loss with respect to the Gaussian distribution, which is of course non-discrete. Also, several recent works have studied learning neural networks under a Gaussian distribution assumption (e.g., Janzamin et al. (2015); Brutzkus and Globerson (2017); Du et al. (2017); Li and Yuan (2017); Feizi et al. (2017); Zhang et al. (2017); Ge et al. (2017)), but using a network architecture different than ours, or focusing on algorithms rather than the geometry of the optimization problem. Finally, Shamir (2016) provide hardness results for training neural networks even under distributional assumptions, but these do not apply when making strong assumptions on both the input distribution and the network generating the data, as we do here.

For Eq. (1), a few works have shown that there are no spurious local minima, or that gradient descent will succeed in reaching a global minimum, provided the $\mathbf{v}_{i}$ vectors are in general position or orthogonal (Zhong et al., 2017; Soltanolkotabi et al., 2017; Tian, 2017). However, these results either apply only to $k=1$, assume the algorithm is initialized close to a global optimum, or analyze the geometry of the problem only on some restricted subset of the parameter space.

The empirical observation that gradient-based methods may not work well on Eq. (1) has been made in Livni et al. (2014), and more recently in Ge et al. (2017). Moreover, Livni et al. (2014) empirically observed that over-parameterization seems to help. However, our focus here is to prove the existence of such local minima, as well as more precisely quantify their behavior as a function of the network sizes.

Main Result and Proof Technique

Before we begin, a small note on terminology: When referring to local minima of a function $F$ on Euclidean space, we always mean spurious local minima (i.e., points $\mathbf{w}$ such that $\inf_{\mathbf{w}}F(\mathbf{w})<F(\mathbf{w})\leq F(\mathbf{w}^{\prime})$ for all $\mathbf{w}^{\prime}$ in some open neighborhood of $\mathbf{w}$).

For $k,n$ smaller than $6$, we were unable to find local minima using our proof technique, since gradient descent always seemed to converge to a global minimum. Also, although we have verified the theorem only up to $k,n\leq 20$, the result strongly suggests that there are local minima for larger values as well. See Sec. 3 for some examples of the local minima found.

The theorem assumes a fixed input dimension, and a particular choice of $\mathbf{v}_{1},\ldots,\mathbf{v}_{k}$. However, these assumptions are not necessary and can be relaxed, as demonstrated by the following corollary:

The corollary is not specific to a Gaussian distribution over $\mathbf{v}_{1},\ldots,\mathbf{v}_{k}$, and can be generalized to any distribution for which $\mathbf{v}_{1},\ldots,\mathbf{v}_{k}$ are approximately orthogonal and of the same norm in high dimensions (see below for details).

for some $\xi\in\left(0,t\right)$, and where $\mathbf{w}_{1,i}^{n}$ denotes the $i$-th coordinate of $\mathbf{w}_{1}^{n}$. Denoting the remainder term as $R_{\mathbf{w}_{1}^{n},\mathbf{u},t}$, we have

Now, suppose that the point $\mathbf{w}_{1}^{n}$ we obtain by gradient descent satisfies $\left|\left|\nabla F(\mathbf{w}_{1}^{n})\right|\right|\leq\epsilon$, $\nabla^{2}F(\mathbf{w}_{1}^{n})\succeq\lambda_{\min}\cdot I$ and $|R_{\mathbf{w}_{1}^{n},\mathbf{u},t}|\leq B_{t}$ (for some positive $\lambda_{\min},\epsilon,B_{t}$), uniformly for all unit vectors $\mathbf{u}$. Fix some $\alpha>0$ and let $B=\sup_{t\in[0,\alpha]}B_{t}$. By the Taylor expansion above, this implies that for any $t\in[0,\alpha]$ and all unit $\mathbf{u}$,

An elementary calculation reveals that the term $t\left(\frac{\lambda_{\min}}{2}t-\frac{B}{6}t^{2}-\epsilon\right)$ is strictly positive for any

(and in particular, in the closed interval of $\frac{3\lambda_{\min}\pm\sqrt{9\lambda_{\min}^{2}-25B\epsilon}}{2B}$). Letting $r\coloneqq\frac{3\lambda_{\min}-\sqrt{9\lambda_{\min}^{2}-25B\epsilon}}{2B}$, and assuming $r<\alpha$, we get that there is some small closed ball $\bar{B}_{r}$ of radius $r$ centered at $\mathbf{w}_{1}^{n}$ (and with boundary $S$), such that

Moreover, since $F$ is continuous, it is minimized over $\bar{B}_{r}$ at some point $\mathbf{w}_{1}^{*n}$. But then

so $\mathbf{w}_{1}^{*n}$ must reside in the interior of $\bar{B}_{r}$. Thus, it is minimal in an open neighborhood containing it, hence it is a local minimum. Overall, we have arrived at the following key lemma:

Assume that for some $\epsilon,B,\alpha>0$, it holds that $\left|\left|\nabla F\left(\mathbf{w}_{1}^{n}\right)\right|\right|\leq\epsilon$ and

let $\lambda_{\min}>0$ denote the smallest eigenvalue of $\nabla^{2}F\left(\mathbf{w}_{1}^{n}\right)$, and let

If $9\lambda_{\min}^{2}-25B\epsilon\geq 0$ and $r<\alpha$ then the function $F$ contains a local minimum, within a distance of at most $r$ from $\mathbf{w}_{1}^{n}$.

The only missing element is that the local minimum might be a global minimum. To rule this out, one can simply use the fact that $F$ is a Lipschitz function, so that if $F(\mathbf{w}_{1}^{n})$ is much larger than , the neighboring local minimum can’t have a value of , and hence cannot be global:

Under the conditions of Lemma 1, if it also holds that

The formal proof of this lemma appears in Subsection 4.1.4.

Most of the technical proof of Thm. 1 consists in rigorously verifying the conditions of Lemma 1 and Lemma 2. A major hurdle is that floating-point calculations are not guaranteed to be accurate (due to the possibility of round-off and other errors), so for a formal proof, one needs to use software that comes with guaranteed numerical accuracy. In our work, we chose to use variable precision arithmetic (VPA), a standard package of MATLAB which is based on symbolic arithmetic, and allows performing elementary numerical computations with an arbitrary number of guaranteed digits of precision. The main technical issue we faced is that some calculations are not easily done with a few elementary arithmetical operations (in particular, the standard way to compute $\lambda_{\min}$ would be via a spectral decomposition of the Hessian matrix). The bulk of the proof consists of showing how we bound the quantities relevant to Lemma 1 in an elementary manner.

Experiments

So far, our technique proves the existence of local minima for the objective function in Eq. (2). However, this does not say anything about the likelihood of gradient descent to reach them. We now turn to study this question empirically.

In Tables 2 and 2, we summarize the percentage of instantiations which were verified to converge close to a spurious local minimum, as a function of $k,n$. We note that among candidate points found, only a tiny fraction could not be verified to be local minima (this only occured for network sizes $\left(k,n\right)\in\left\{\left(15,16\right),\left(17,18\right),\left(20,20\right)\right\}$, and consist only $0.1\%,2.4\%,0.9\%$ of the instantiations respectively). In the tables, we also provide the minimal eigenvalue of the Hessian of the objective, and the objective value (or equivalently, the optimization error) at the points found, averaged over the instantiationsSince all points are extremely close to a local minimum, the objective at the minimum is essentially the same, up to a deviation on order less than $1.1\cdot 10^{-9}$. Also, the minimal eigenvalues vary by at most $5.7\cdot 10^{-4}$.. Note that since the minimal eigenvalue is strictly positive and varies slightly inside the enclosing ball, this indicates that these are in fact strict local minima. As the tables demonstrate, the probability of converging to a spurious local minimum increases rapidly with $k,n$, and suggests that it eventually become overwhelming as long as $n\approx k$. However, on a positive note, mild over-parameterization seems to remedy this, as no local minima were found for $n\geq k+2$ where $n\leq 20$, and local minima for $n=k+1$ are much more scarce than for $n=k$. We leave the investigation of local minima for larger values of $k,n$ to future work.

In Fig. 1, we show the distribution of the objective values obtained in the points found, over the 1000 instantiations of several architectures. The figure clearly indicates that apart from a higher chance of converging to local minima, larger architectures also tend to have worse values attained on these minima.

Finally, in examples 1 and 2 below, we present some specific local minima found for $n=k=6$ and $k=8,n=9$, and discuss their properties. We note that these are the smallest networks (with $n=k$ and $n\neq k$ respectively) for which we were able to find such points.

Out of 1000 gradient descent instantiations for $n=k=6$, three converged close to a local minimum. All three were verified to be essentially identical (after permuting the neurons and up to an Euclidean distance of $1.2\cdot 10^{-8}$), and have the following form:

where the parameter vector of each of the $6$ neurons corresponds to a column of $\mathbf{w}_{1}^{6}$. The Hessian of the objective at $\mathbf{w}_{1}^{6}$, $\nabla^{2}F\left(\mathbf{w}_{1}^{6}\right)$, was confirmed to have minimal eigenvalue $\lambda_{\min}\left(\nabla^{2}F\left(\mathbf{w}_{1}^{6}\right)\right)\geq 0.004699$. This implied that all three suspicious points found for $n=k=6$ are of distance at most $r=1.12\cdot 10^{-7}$ from a local minimum with objective value at least $0.02508$.

Out of 1000 gradient descent initializations for $k=8,n=9$, one converged to a local minimum. The point found, denoted $\mathbf{w}_{1}^{9}$, is given below:

where the parameter vector of each of the $9$ neurons corresponds to a column of $\mathbf{w}_{1}^{9}$. The Hessian of the objective at $\mathbf{w}_{1}^{9}$, $\nabla^{2}F\left(\mathbf{w}_{1}^{9}\right)$, was confirmed to have minimal eigenvalue $\lambda_{\min}\left(\nabla^{2}F\left(\mathbf{w}_{1}^{9}\right)\right)\geq 0.005944$. This implied that $\mathbf{w}_{1}^{9}$ is of distance at most $r=7.8\cdot 10^{-8}$ from a local minimum with objective value at least $0.02056$.

It is interesting to note that the points found in examples 1 and 2, as well as all other local minima detected, have a nice symmetric structure: We see that most of the trained neurons are very close to the target neurons in most of the dimensions. Also, many of the entries appear to be the same. Surprisingly, although such constructions might seem brittle, these are indeed strict local minima. Moreover, the probability of converging to such points becomes very large as the network size increases as demonstrated by our experiments.

Proofs

In the proofs, we use bold-faced letters (e.g., $\mathbf{w}$) to denote vectors, barred bold-faced letters (e.g., $\bar{\mathbf{w}}$) to denote vectors normalized to unit Euclidean norm, and capital letters to generally denote matrices. Given a natural number $k$, we let $[k]$ be shorthand for $\left\{1,\dots,k\right\}$. Given a matrix $M$, $\left|\left|M\right|\right|_{\text{sp}}$ denotes its spectral norm. We will also make use of the following version of Weyl’s inequality, stated below for completeness.

As we show in Subsection 4.1.1 below, the objective function in Eq. (2) can be written in an explicit form (without the expectation term), as well as its gradients and Hessians. We first ran standard gradient descent, starting from random initialization and using a fixed step size of $0.1$, till we reached a point $\mathbf{w}_{1}^{n}$, such that the gradient norm w.r.t. any $\mathbf{w}_{i}$ is at most $10^{-9}$. Given this point, we use Lemma 1 and Lemma 2 to prove that it is close to a local minimum. Specifically, we built code which does the following:

Provide a rigorous upper bound on the norm of the gradient at a given point $\mathbf{w}_{1}^{n}$ (since we have a closed-form expression for the gradient, this only requires elementary calculations).

Provide a rigorous lower bound on the minimal eigenvalue of $\nabla^{2}F(\mathbf{w}_{1}^{n})$: This is the technically most demanding part, and the derivation of the algorithm is presented in Subsection 4.1.2.

Provide a rigorous upper bound $B$ on the remainder term $R_{\mathbf{w}_{1}^{n},\mathbf{u}}$ (see Subsection 4.1.3 for the relevant calculations).

Provide a rigorous Lipschitz bound on the objective $F\left(\mathbf{w}_{1}^{n}\right)$, establishing Lemma 2 (see Subsection 4.1.4 for the relevant calculations).

We used MATLAB (version 2017b) to perform all floating-point computations, and its associated MATLAB VPA package to perform the exact symbolic computations. The code we used is freely available at https://github.com/ItaySafran/OneLayerGDconvergence.git. For any candidate local minimum, the verification took from less than a minute up to a few hours, depending on the size of $k,n$, when running on Intel Xeon E5 processors (ranging from E5-2430 to E5-2660).

For convenience, we will now state closed-form expressions (without an expectation) for the objective function $F$ in Eq. (2), its gradient and its Hessian. These are also the expressions used in the code we built to verify the conditions of Lemma 1 and Lemma 2. First, we have that

and $\theta_{\mathbf{w},\mathbf{v}}:=\cos^{-1}\left(\frac{\mathbf{w}^{\top}\mathbf{v}}{\left|\left|\mathbf{w}\right|\right|\cdot\left|\left|\mathbf{v}\right|\right|}\right)$ is the angle between two vectors $\mathbf{w},\mathbf{v}$. The latter equality in Eq. (7) was shown in Cho and Saul (2009, section 2).

Using the above representation, Brutzkus and Globerson (2017) compute the gradient of $f\left(\mathbf{w},\mathbf{v}\right)$ with respect to $\mathbf{w}$, given by

Which implies that $\nabla F\left(\mathbf{w}_{1}^{n}\right)$, the gradient of the objective with respect to $\mathbf{w}_{1}^{n}$, equals

We wish to verify that the Hessian of a point returned by the gradient descent algorithm is positive definite, as well as provide a lower bound for its smallest eigenvalue, avoiding the possibility of errors due to floating-point computations.

Since the Hessians we encounter have relatively small entries and are well-conditioned, it turns out that computing the spectral decomposition in floating-point arithmetic provides a very good approximation of the true spectrum of the matrix. Therefore, instead of performing spectral decomposition symbolically from scratch, our algorithmic approach is to use the floating-point decomposition, and merely bound its error, using simple quantities which are easy to compute symbolically. Specifically, given the (floating-point, possibly approximate) decomposition $UDU^{\top}$ of a matrix $A$, we bound the error using the distance of $UDU^{\top}$ from $A$, as well as the distance of $U$ from its projection on the subspace of orthogonal matrices given by $\bar{U}\coloneqq U\left(U^{\top}U\right)^{-0.5}$. Formally, we use the following algorithm (where numerical computations refer to operations in floating-point arithmetic):

Algorithm analysis: For the purpose of analyzing the algorithm, the following two lemmas will be used.

Clearly, for any $\left|x\right|<1$ we have

Using the generalized binomial theorem, we have for any $\left|x\right|<1$

Consider the $k$-th coefficient in the expansion of the square of Eq. (12), which is well defined as the sum converges absolutely for any $\left|x\right|<1$. From Eq. (11), these coefficients are all $1$. However, these are also given by the expansion of the square of Eq. (12). Specifically, the $k$-th coefficient in the square is given as the sum of all $x^{k}$ coefficients in the expansion of the root, that is, it is a convolution of the coefficients in Eq. (12) with index $\leq k$, thus we have

Let $U^{\top}U$ be a diagonally dominant matrix, let $E=\mathbf{I}-U^{\top}U$ satisfying $\left|\left|E\right|\right|_{\text{sp}}\leq C<1$. Then $\left(U^{\top}U\right)^{-0.5}=\sum_{n=0}^{\infty}\binom{2n}{n}4^{-n}E^{n}$. Moreover, $E^{\prime}\coloneqq\sum_{n=1}^{\infty}\binom{2n}{n}4^{-n}E^{n}$ satisfies $\left|\left|E^{\prime}\right|\right|_{\text{sp}}\leq\left(\frac{1}{\sqrt{1-C}}-1\right)$.

Consider the series given by the partial sums

where the second equality is due to Lemma 3, and holds for some $\beta_{k}\in\left(0,1\right)$, $k\in\left\{n+1,\dots,2n\right\}$. Now, since

we have that Eq. (4.1.2) reduces to $\mathbf{I}$ as $n\to\infty$, concluding the proof of the lemma. ∎

We now upper bound $\left|\left|A^{\prime\prime}-\bar{A}\right|\right|_{\text{sp}}$, where $\bar{A}=\bar{U}D\bar{U}^{\top}$ and therefore its spectrum is given to us explicitly as the diagonal entries of $D$, $\text{diag}\left(D\right)$. Compute

Estimating the spectrum $\text{diag}\left(D\right)$ of $A$ using the spectrum of $\bar{A}$ yields an approximation error of

where in the last inequality we used the fact that the Frobenius norm upper bounds the spectral norm, which also proves that $C$ is an upper bound on $\left|\left|E^{\prime}\right|\right|_{\text{sp}}$. Verifying the upper bound given by $B$, we compute

Whenever $U$ is close to unity, this provides a sharper upper bound than taking $C=\left|\left|U\right|\right|_{F}$.

Finally, applying Weyl’s inequality (Thm. 2) to $A$ and $\bar{A}$, we have that the spectra of the two cannot deviate by more than $\epsilon_{1}+\epsilon_{2}+\epsilon_{3}$, concluding the proof of the algorithm.

In a nutshell, to derive an upper bound $L$ on the third order term in Eq. (3), we show that the second order term in any direction is $L$-Lipschitz. Recalling that the purpose of this upper bound is to provide the radius of the ball enclosing a minimum in the vicinity of $\mathbf{w}_{1}^{n}$ (see Lemma 1), we observe, however, that Lemma 9 suggests $L$ depends on the norm each neuron attains inside the ball, and therefore also on the radius of the ball enclosing the minimum. To circumvent this circular dependence between the radius and the third order bound, we first fixed the radius around $\mathbf{w}_{1}^{n}$ where we bound the third order termspecifically, the radius was chosen to be a $10^{-3}$ fraction of $\max_{i\in\left[n\right]}\left|\left|\mathbf{w}_{i}\right|\right|_{2}$. Testing this value, we observed that restricting the radius further only slightly improved the bound, and then checked whether the resulting radius enclosing the ball is smaller than the one used for the bound, thus validating the result.

That is, $\mathbf{w}_{\min}$ and $\mathbf{w}_{\max}$ are the neurons with minimal and maximal norm among all possible network weights in the set $A$, respectively. Similarly, defining $\mathbf{v}_{\max}$ to be the target parameter vector with maximal $2$-norm, the necessary bound is now given by the following theorem:

To prove the theorem, we will first need the following two lemmas.

$h_{1}\left(\mathbf{w},\mathbf{v}\right)$ is $\frac{\left|\left|\mathbf{v}_{\max}\right|\right|}{\pi\left|\left|\mathbf{w}_{\min}\right|\right|^{2}}$ Lipschitz in $\mathbf{w}$ on $A$.

$h_{1}\left(\mathbf{w}_{1},\mathbf{w}_{2}\right)$ is $\frac{\sqrt{2}\left|\left|\mathbf{w}_{\max}\right|\right|}{\pi\left|\left|\mathbf{w}_{\min}\right|\right|^{2}}$ Lipschitz in $\left(\mathbf{w}_{1},\mathbf{w}_{2}\right)$ on $A$.

$h_{2}\left(\mathbf{w}_{1},\mathbf{w}_{2}\right)$ is $\frac{\sqrt{2}}{\pi\left|\left|\mathbf{w}_{\min}\right|\right|}$ Lipschitz in $\left(\mathbf{w}_{1},\mathbf{w}_{2}\right)$ on $A$.

We begin with computing some useful derivatives:

Now, differentiating the spectral norms of $h_{1}$ and $h_{2}$ using Lemma 9 yields

Next, differentiating with respect to $\mathbf{v}$ gives

Concluding the derivation for the spectral norm of the gradient of $h_{1}$ we get

For the gradient with respect to $\mathbf{v}$ we have

Concluding the derivation for the spectral norm of the gradient of $h_{2}$ we get

Finally, since a differentiable function is $L$-Lipschitz if and only if its gradient’s $2$-norm is bounded by $L$, the lemma follows from substituting $\mathbf{w}_{\min},\mathbf{w}_{\max},\mathbf{v}_{\max}$ in Eq. (14) and Eq. (4.1.3). ∎

In this subsection, we turn to proving a Lipschitz bound on the objective in Eq. (6), implying Lemma 2 and showing that the local minimum identified in Eq. (1) is necessarily non-global. A straightforward approach would be to globally upper bound $\left|\left|\nabla F\left(\mathbf{w}_{1}^{n}\right)\right|\right|$ (excluding the neighborhood of some singular points). However, this approach is quite loose, since it does not take advantage of the fact that the gradients $\nabla F\left(\mathbf{w}_{1}^{n}\right)$ close to our points of interest are very small. Instead, we first derive a Lipschitz bound on $\nabla^{2}F\left(\mathbf{w}_{1}^{n}\right)$, implying that $\nabla F\left(\mathbf{w}_{1}^{n}\right)$ does not vary too greatly, and therefore remains small for any $\mathbf{w}_{1}^{\prime n}$ in the ball enclosing $\mathbf{w}_{1}^{n}$, providing a stronger bound than the more naive approach.

To prove the theorem, we will need the following lemma:

Since $F$ is thrice-differentiable, we have from the mean value theorem that there exists some $t_{\mathbf{u}}$ such that

Taking $\mathbf{u}=\nabla F\left(\mathbf{w}_{1}^{\prime n}\right)+\nabla F\left(\mathbf{w}_{1}^{n}\right)$ and recalling that from Lemma 7 we have that $\sup_{\mathbf{w}_{1}^{\prime n}\in A}\left|\left|\nabla^{2}F\left(\mathbf{w}_{1}^{\prime n}\right)\right|\right|_{\text{sp}}$ is bounded by $LH$, we get

Dividing by $\left|\left|\nabla F\left(\mathbf{w}_{1}^{\prime n}\right)\right|\right|_{2}+\left|\left|\nabla F\left(\mathbf{w}_{1}^{n}\right)\right|\right|_{2}$ and rearranging yields

That is, the target function $F$ is $\left(LH\left|\left|\mathbf{w}_{1}^{\prime n}-\mathbf{w}_{1}^{n}\right|\right|_{2}+\left|\left|\nabla F\left(\mathbf{w}_{1}^{n}\right)\right|\right|_{2}\right)$-Lipschitz on $A$, thus

For $A$ which is a ball of radius $r$ centered at $\mathbf{w}_{1}^{n}=\left(\mathbf{w}_{1},\dots,\mathbf{w}_{n}\right)$, we have that $\left|\left|\mathbf{w}_{\max}\right|\right|=\max_{i}\left|\left|\mathbf{w}_{i}\right|\right|+r$ as well as $\left|\left|\mathbf{w}_{\min}\right|\right|=\min_{i}\left|\left|\mathbf{w}_{i}\right|\right|-r$. Plugging this in Thm. 4 and substituting $\left|\left|\mathbf{w}_{1}^{\prime n}-\mathbf{w}_{1}^{n}\right|\right|_{2}\leq r$ completes the proof of the lemma. ∎

2 Proof of Corollary 1

To show the first part of Corollary 1, we will use the following lemma:

For the second part of the corollary, we note that if $\mathbf{v}_{1},\ldots,\mathbf{v}_{k}$ are chosen i.i.d. from $\mathcal{N}(\mathbf{0},cI)$, then by standard concentration arguments, for any $\epsilon>0$ and high enough dimension $d$ (depending on $k,\epsilon$), it holds with probability at least $1-\exp(-\Omega(d))$ that $|\frac{1}{\sqrt{cd}}\left|\left|\mathbf{v}_{i}\right|\right|-1|\leq\epsilon$ and $|\frac{1}{cd}\mathbf{v}_{i}^{\top}\mathbf{v}_{i^{\prime}}|\leq\epsilon$ for all $i,i^{\prime}\in\{1,\ldots,k\}$ (see Ledoux (2005)). Therefore, regardless of which distribution we are considering, with probability at least $1-\exp(-\Omega(d))$, we can find a scalar $a>0$ and an orthogonal matrix $M$, such that $\left|\left|aM\mathbf{v}_{i}-\mathbf{e}_{i}\right|\right|\leq\epsilon$ for all $i$, where $\mathbf{e}_{i}$ is the $i$-th standard basis vector.

Letting $F$ be our objective function (w.r.t. the randomly chosen $\mathbf{v}_{1},\ldots,\mathbf{v}_{k}$), and using the rotational symmetry of the Gaussian distribution and the positive-homogeneity of the ReLU function, we have

It follows that $F$ has the same local minima as

3 Technical Proofs

The Hessian of $F$ at point $\mathbf{w}_{1}^{n}=\left(\mathbf{w}_{1},\dots,\mathbf{w}_{n}\right)$ with respect to target values $\left(\mathbf{v}_{1},\dots,\mathbf{v}_{k}\right)$ is given on the main diagonals

By a straightforward calculation, we have

Recall the definition of $\mathbf{n}$ in Eq. (9), we have that

Differentiating with respect to different individual parameter vectors, we have

Recall the objective in Eq. (6), we have that its Hessian is comprised of $n\times n$ blocks of size $d\times d$ each. On the main diagonal we therefore have

$\left|\left|h_{1}\left(\mathbf{w},\mathbf{v}\right)\right|\right|_{\text{sp}}=\frac{\sin\left(\theta_{\mathbf{w},\mathbf{v}}\right)\left|\left|\mathbf{v}\right|\right|}{\pi\left|\left|\mathbf{w}\right|\right|}.$

$\left|\left|h_{2}\left(\mathbf{w},\mathbf{v}\right)\right|\right|_{\text{sp}}=\frac{1}{2\pi}\left(\pi-\theta_{\mathbf{w},\mathbf{v}}+\sin\left(\theta_{\mathbf{w},\mathbf{v}}\right)\right).$

To find the spectral norm, we compute the spectra of $h_{1},h_{2}$.

Thus $\frac{\sin\left(\theta_{\mathbf{w},\mathbf{v}}\right)\left|\left|\mathbf{v}\right|\right|}{2\pi\left|\left|\mathbf{w}\right|\right|}$ is an eigenvalue of $h_{1}$ with multiplicity at least $d-2$. Since $\bar{\mathbf{w}},\bar{\mathbf{n}}_{\mathbf{v},\mathbf{w}}$ are orthogonal, their corresponding eigenvalues comprise the rest of the spectrum of $h_{1}$. Compute

Hence is the eigenvalue of $\bar{\mathbf{w}}$. Also,

Therefore $\frac{\sin\left(\theta_{\mathbf{w},\mathbf{v}}\right)\left|\left|\mathbf{v}\right|\right|}{\pi\left|\left|\mathbf{w}\right|\right|}$ is the largest eigenvalue of $h_{1}$.

Thus $\frac{1}{2\pi}\left(\pi-\theta_{\mathbf{w},\mathbf{v}}\right)$ is an eigenvalue of $h_{2}$ with multiplicity at least $d-2$. We now show the remaining two eigenvalues correspond to the eigenvectors $\bar{\mathbf{n}}_{\mathbf{w},\mathbf{v}}+\bar{\mathbf{n}}_{\mathbf{v},\mathbf{w}}$ and $\bar{\mathbf{n}}_{\mathbf{w},\mathbf{v}}-\bar{\mathbf{n}}_{\mathbf{v},\mathbf{w}}$.

Hence $\frac{1}{2\pi}\left(\pi-\theta_{\mathbf{w},\mathbf{v}}-\sin\left(\theta_{\mathbf{w},\mathbf{v}}\right)\right)$ is an eigenvalue of $h_{2}$. Similarly, we have

Therefore $\frac{1}{2\pi}\left(\pi-\theta_{\mathbf{w},\mathbf{v}}+\sin\left(\theta_{\mathbf{w},\mathbf{v}}\right)\right)$ is the largest eigenvalue of $h_{2}$.

References