Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
Itay Safran Ohad Shamir
cs.LG stat.ML


Complexes of dipolar excitons in layered quasi-two-dimensional nanostructures
    Maria R. Vladimirova
    December 30, 2023
=============================================================================


	We consider the optimization problem associated with training simple ReLU 
	neural networks of the form ↦∑_i=1^kmax{0,_i^⊤} with respect to the squared loss. We provide a computer-assisted 
	proof that even if the input distribution is standard Gaussian, even if the 
	dimension is arbitrarily large, and even if the target values are generated by 
	such a network, with orthonormal parameter vectors, the problem can 
	still have spurious local minima once 6≤ k≤ 20. By a concentration of measure argument, 
	this implies that in high input dimensions, nearly all target networks of 
	the relevant sizes lead to spurious local minima. Moreover, 
	we conduct experiments which show that the probability of hitting such 
	local minima is quite high, and increasing with the network size. On the 
	positive side, mild over-parameterization appears to drastically reduce 
	such local minima, indicating that an over-parameterization assumption is 
	necessary to get a positive result in this setting. 




§ 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., 
<cit.>). 
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

    ↦∑_i=1^k[_i^⊤]_+

for some k> 1, where [z]_+=max{0,z} is the ReLU function,  is a 
vector in ^d, and _1,…,_k are parameter 
vectors. We consider directly optimizing the expected squared loss, where the 
input is standard Gaussian, and in the realizable case – namely, that the 
target values are generated 
by a network of a similar architecture:

    min__1,…,_k_∼(0,I)[1/2(∑_i=1^k[_i^⊤]_+
    -∑_i=1^k[_i^⊤]_+)^2 ] .

Note that here, the choice _i=_σ(i) (for all i=1,…,k and 
any permutation σ) 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 (<ref>) indeed has spurious local minima once 6≤ k≤20. Moreover, this is true even if the dimension is unrestricted, and even if 
we assume that _1,…,_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 (<ref>), in 
high enough dimension 
(with respect to, say, a Gaussian distribution over _1,…,_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 (<ref>) 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 (<ref>). 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 0); 
approximate stationary (gradient norm very close to 0); and with a strictly 
positive definite Hessian (with minimal eigenvalue significantly larger than 
0). 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 (<ref>), 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 (<ref>) with

    min__1,…,_k_∼(0,I)[1/2(∑_i=1^n[_i^⊤]_+
    -∑_i=1^k[_i^⊤]_+)^2 ] ,

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≥ k+2 
(although those might still 
exist for larger values of k,n than those we tried). Thus, although 
(<ref>) has local minima, we conjecture that (<ref>) 
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:main. 
sec:experiments 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:proofs. 









 §.§ Related Work


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 (<ref>)), there are many spurious local minima 
(e.g., <cit.>). Moreover, the 
probability of starting at a basin of such local minima is 
exponentially high in the dimension <cit.>. 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 
<cit.>.
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., 
<cit.>),
but using a network architecture different than ours, or focusing on 
 algorithms rather than the geometry of the optimization problem. Finally, 
 <cit.> 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 (<ref>), 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 _i vectors are in general position or orthogonal 
<cit.>. 
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 
(<ref>) has been made in <cit.>, and more 
recently in <cit.>. Moreover,  <cit.> 
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  such that inf_F()<F()≤ F(') for all 
' in some open neighborhood of ). 

Our basic result is the following:

	Consider the optimization problem 
	
    min__1,…,_n∈^k_∼(0,I)[1/2(∑_i=1^n[_i^⊤]_+
    		-∑_i=1^k[_i^⊤]_+)^2 ] ,

	where _1,…,_k are orthogonal unit vectors in ^k. 
	Then for n=k∈{6,7,…,20}, as well 
	as (k,n)∈{8,9, 10,11, 11,12, …, 19,20}, the objective 
	function above has spurious local minima.


 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≤ 20, the result strongly suggests that there are local minima for 
larger values as well. See sec:experiments for some examples of the 
local minima found. 


The theorem assumes a fixed input dimension, and a particular choice of 
_1,…,_k. However, these assumptions are not necessary and can be 
relaxed, as demonstrated by the following corollary:


	thm:main also applies if the space ^k is replaced by 
	^d for any d>k (with  distributed as a standard Gaussian 
	in that space). Moreover, if _1,…,_k are 
	chosen i.i.d. from a Gaussian distribution (0,cI) (for any 
	c>0), the theorem still 
	holds with probability at least 1-exp(-Ω(d)). 



The corollary is not specific to a Gaussian distribution over 
_1,…,_k, and can be generalized to any distribution for which 
_1,…,_k are approximately orthogonal and of the same norm in high 
dimensions (see below for details).


We now turn to explain how these results are derived, starting with 
thm:main. In what follows, we let 
=(_1,…,_n)∈^kn be the vector of parameters, and let 
F() be the 
objective function defined in thm:main (assuming k,n are fixed). 
We will also assume that F is thrice-differentiable in a neighborhood of  (which will be shown to be true as part of our proofs), with a gradient ∇ F(·) and a Hessian ∇^2 F(·).

Clearly, a global minimum of F is obtained by _i=_i for all 
i=1,…,k (and _i=0 otherwise), in which case F attains a 
global minimum of 0. Thus, to prove thm:main, it 
is sufficient to find a point ∈^kn such that ∇ F()=0,  
∇^2 F()≽ 0, and F()>0. The major difficulty is showing the 
existence of points where the first condition is fulfilled: Gradient descent 
allows us to find points where ∇ F()≈ 0, but it is very 
unlikely to return a point where ∇ F()=0 exactly. Instead, we use a 
Taylor-expansion argument (detailed below), to show that if we found a point 
such that ∇ F() is sufficiently close to 0, as well as ∇^2 
F()≻ 0 and F()>0, then  must 
be close to a local minimum. 

The second-order Taylor expansion of a multivariate, thrice-differentiable 
function F about a 
point ∈^kn, in a direction given by a unit vector ∈^kn and using a Lagrange remainder term, is given by

    F+t=F +    t∑_i_1∂/∂_1,i_1^nFu_i_1+ 
    	1/2t^2∑_i_1,i_2∂^2/∂_1,i_1^n∂_1,i_2^nFu_i_1u_i_2
     +   1/6t^3∑_i_1,i_2,i_3∂^3/∂_1,i_1^n∂_1,i_2^n∂_1,i_3^nF+ξu_i_1u_i_2u_i_3,


for some ξ∈0,t, and where _1,i^n denotes the i-th coordinate of .
Denoting the remainder term as R_,,t, we have

    F+t = F + t∇ F^⊤ + 
    	1/2t^2^⊤∇^2F + 1/6t^3R_,,t .


Now, suppose that the point  we obtain by gradient descent satisfies 
∇ F()≤ϵ, ∇^2F()≽λ_min· I and 
|R_,,t|≤ B_t (for some positive λ_min,ϵ,B_t), uniformly 
for all unit vectors . Fix some α>0 and let B=sup_t∈[0,α]B_t. By the Taylor 
expansion above, this implies that for any t∈[0,α] and all unit ,

    F(+t)    ≥  F()-t∇
    F()·+t^2/2λ_min^2-t^3/6B
       = F()-ϵ t+λ_mint^2/2-Bt^3/6
       = F()+t(λ_min/2t-B/6t^2-ϵ).

An elementary calculation reveals that the term 
t(λ_min/2t-B/6t^2-ϵ) is strictly 
positive for any 

    t ∈ (3λ_min-√(9λ_min^2-24Bϵ)/2B , 3λ_min+√(9λ_min^2-24Bϵ)/2B) ,

(and in particular, in the closed interval of 
3λ_min±√(9λ_min^2-25Bϵ)/2B). Letting r3λ_min-√(9λ_min^2-25Bϵ)/2B, and assuming r<α, we get that there is some small closed ball B̅_r of radius r centered 
at  (and with boundary S), such that

    F() < min_∈ S F().

Moreover, since F is continuous, it is minimized over B̅_r at some 
point . But then

    F()=min_∈B̅_rF()≤ F() < min_∈ S F(),

so  must reside in the interior of 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 ϵ,B,α>0, it holds that ∇ F≤ϵ and 
    sup_t∈ [0,α]
    :=1R_,,t≤ B,
 let λ_min>0 denote the smallest 
	eigenvalue of ∇^2F, and let
	
    r3λ_min-√(9λ_min^2-25Bϵ)/2B.

	If 9λ_min^2- 25Bϵ≥ 0 and r<α then the function F contains a local minimum, within a distance of at most	r from . 


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() is much larger than 0, the neighboring local minimum can't 
have a value of 0, and hence cannot be global:

	Under the conditions of lem:key, if it also holds that
	
    F > r^21/2 +nn-1max_i 
    		_i+r/2πmin_i _i-r+1/2 + 
    		nk ·max_i _i/2πmin_i _i-r + 
    		rϵ,

	then the local minimum is non-global.

The formal proof of this lemma appears in 
subsec:objective_lipschitzness. 

Most of the technical proof of thm:main consists in rigorously 
verifying the conditions of lem:key and lem:key2. 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 λ_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 lem:key in an elementary manner. 

Finally, we turn to discuss how Corollary <ref> is proven, given 
thm:main (see subsec:cor_proof for a more formal 
derivation). 
The proof idea is that the objective does not have any “non-trivial” 
structure outside the span of _1,…,_k. Therefore, if we take a 
local minima for ^k, and pad it 
with d-k zeros, we get a point in ^d for which the gradient's norm is 
unchanged, the Hessian has the same spectrum for any d≥ k+1, and the third derivatives 
are still bounded. Hence, that point is a local minimum in the 
higher-dimensional problem as well. As to the second part of the corollary, the 
only property of the Gaussian distribution we need is that in high dimensions, 
if we sample _1,…,_k, then we are overwhelmingly likely to get 
approximately orthogonal vectors with approximately the same norm. Hence, up to 
rotation and scaling, we get a small perturbation F̃ of the objective 
F considered in thm:main. Moreover, for large enough d, we can 
make the perturbation arbitrarily small, uniformly in some compact domain. Now, 
recall that we prove the existence of some local minimum , by 
showing that F()<min_∈ S F() in some 
small sphere S enclosing . If the perturbations are small enough, 
we also have F̃()<min_∈ SF̃(), which by arguments similar to 
before, imply that  is close to a local minimum of F̃. 



§ EXPERIMENTS


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

For each value of k,n, where k∈20 and n∈k,…,20, 
we ran 1000 instantiations of gradient descent on the objective in 
(<ref>), each starting from a different random 
initialization[We used standard Xavier initialization: Each weight 
vector _i was samples i.i.d. from a Gaussian distribution in ^k, 
with zero mean and covariance 1/kI.]. Each instantiation was ran with 
a fixed step size of 0.1, until reaching a candidate stationary point / local 
minima (the stopping criterion was that the gradient norm w.r.t. any _i is at most 10^-9). Points 
obtaining objective values less than 10^-3 were ignored as those are 
likely to be close to a global minimum. Interestingly, no points with value 
between 10^-3 and 10^-2 were found. For all remaining candidate 
points, we verified that the conditions in Lemmas <ref> and 
<ref> are met[
	Since running our algorithm for all suspicious points found on all 
	architectures is time consuming, we instead identified points that are 
	equivalent up to permutations on the order of neurons and of the data 
	coordinates, since the objective is invariant under such permutations. By 
	bounding the maximal Euclidean distance between these points and using the 
	Lipschitzness of the objective and its Hessian (see thm:F_bound 
	and lem:hess_lipschitz), this allowed us to run the algorithm on a 
	single representative from a family of equivalent points and speed up the 
	running time drastically. Also, the objective was tested to be 
	thrice-differentiable in all enclosing balls of radii returned by the 
	algorithm. Specifically, we ensured that no two such balls intersect (which 
	results in two identical neurons, where the objective is not 
	thrice-differentiable) and that no ball contains the origin (which results 
	in a neuron with weight 0, where again the objective is not 
	thrice-differentiable).]
 to conclude that these points are indeed close to 
spurious local minima (in all cases, the distance turned out to be less than 
2· 10^-6). Our verification process included verifying thrice-differentiability in the enclosing balls containing the minimum by asserting they contain no singular points, hence the objective is an analytical expression when restricted to these balls where differentiability follows.

In Tables <ref> and <ref>, 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 k,n∈15,16,17,18,20,20, 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 instantiations[Since 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· 10^-9. Also, the minimal eigenvalues vary by at most 5.7·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≈ k. However, on a positive note, mild 
over-parameterization seems to remedy this, as no local minima were found for n≥ k+2 where n≤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:obj_val_cdf, 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 <ref> and <ref> 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≠ 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· 10^-8), and have the following form:
	
    _1^6=[ -0.6015  0.3080  0.3080  0.3080  0.3080  0.3080;  0.2245  0.9867 -0.0504 -0.0504 -0.0504 -0.0504;  0.2245 -0.0504  0.9867 -0.0504 -0.0504 -0.0504;  0.2245 -0.0504 -0.0504  0.9867 -0.0504 -0.0504;  0.2245 -0.0504 -0.0504 -0.0504  0.9867 -0.0504;  0.2245 -0.0504 -0.0504 -0.0504 -0.0504  0.9867 ],

	where the parameter vector of each of the 6 neurons corresponds to a 
	column of _1^6.
	The Hessian of the objective at _1^6, ∇^2F_1^6, was confirmed to have minimal eigenvalue λ_min∇^2F_1^6≥ 0.004699. This implied 
	that all three suspicious points found for n=k=6 are of distance at 
	most r=1.12·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 _1^9, is given below:
	
    _1^9=[  0.9841 -0.0298 -0.0298 -0.0298 -0.0298 -0.0298 -0.0298  0.1263  0.0687; -0.0298  0.9841 -0.0298 -0.0298 -0.0298 -0.0298 -0.0298  0.1263  0.0687; -0.0298 -0.0298  0.9841 -0.0298 -0.0298 -0.0298 -0.0298  0.1263  0.0687; -0.0298 -0.0298 -0.0298  0.9841 -0.0298 -0.0298 -0.0298  0.1263  0.0687; -0.0298 -0.0298 -0.0298 -0.0298  0.9841 -0.0298 -0.0298  0.1263  0.0687; -0.0298 -0.0298 -0.0298 -0.0298 -0.0298  0.9841 -0.0298  0.1263  0.0687; -0.0298 -0.0298 -0.0298 -0.0298 -0.0298 -0.0298  0.9841  0.1263  0.0687;  0.2301  0.2301  0.2301  0.2301  0.2301  0.2301  0.2301 -0.1890 -0.4862 ],

	where the parameter vector of each of the 9 neurons corresponds to a 
	column of _1^9.
	The Hessian of the objective at _1^9, ∇^2F_1^9, was confirmed to have minimal eigenvalue λ_min∇^2F_1^9≥ 0.005944. This implied 
	that _1^9 is of distance at most r=7.8·10^-8 from a 
	local minimum with objective value at least 0.02056.


It is interesting to note that the points found in examples <ref> and <ref>, 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., ) to denote 
vectors, barred bold-faced letters (e.g., ) 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 1,…,k. Given a 
matrix M, M denotes its spectral norm. We will also make use of 
the following version of Weyl's inequality, stated below for completeness.


	Suppose A, B, P∈^d× d are real symmetric matrices such 
	that A-B=P. Assume that A,B have eigenvalues α_1≥…≥α_d, β_1≥…≥β_d respectively, 
	and that P≤ϵ. Then
	
    α_i-β_i≤ϵ   ∀ i∈d.





 §.§ Proof of thm:main


To prove thm:main for some (k,n), it is enough to consider some 
particular choice of orthogonal _1,…,_k, since any other choice 
amounts to rotating or reflecting the same objective function (which of course 
does not 
change the existence or non-existence of its local minima). In particular, we 
chose these vectors to simply be the standard basis vectors in ^k. 

As we show in subsec:closedform below, the objective function in 
(<ref>) 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 , such that the gradient norm w.r.t. any _i is 
at most 10^-9. Given this point, we use lem:key and 
lem:key2 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  (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 
	∇^2F(): This is the technically most demanding part, and the derivation 
	of the algorithm is presented in subsec:pdalg.
	
  * Provide a rigorous upper bound B on the remainder term R_, 
	(see sec:remainder_bound for the relevant calculations).
	
  * Provide a rigorous Lipschitz bound on the objective F, establishing lem:key2 (see 
	subsec:objective_lipschitzness 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).







  §.§.§ Closed-form Expressions for F,∇ F and ∇^2 F



For convenience, we will now state closed-form expressions (without an 
expectation)
for the objective function F in (<ref>), its gradient and its 
Hessian. These are also the expressions used in the code we built to verify the 
conditions of lem:key and lem:key2. First, we have that

    F = 1/2∑_i,j=1^n f_i,_j - 
    ∑_i∈n
    j∈k f_i,_j + 
    1/2∑_i,j=1^k f_i,_j,

where

    f,   := _∼(0,I)[^⊤^⊤]
       = 1/2πsinθ_,+π-θ_,cosθ_,,

and 
θ_,:=cos^-1(^⊤/·)
	is the angle between two vectors ,. 
The latter equality in (<ref>) was shown in <cit.>.

Using the above representation, <cit.> compute the gradient of f, with respect to , given by

    g,∂/∂f, = 1/2πsinθ_, + π-θ_,.

Which implies that ∇ F, the gradient of the objective with respect to , equals

    ∇ F = 1/2 + ∑_i,j=1
    i≠ j^n g̃_i,_j - ∑_i∈n
    j∈kg̃_i,_j,

where g̃_i,∈^kn equals g_i,∈^k on entries k(i-1)+1 through ki, and zero elsewhere.
We now provide the Hessian of (<ref>) based on the computation of the gradient in (<ref>) (see sec:hessian_derivation for the full derivation)

    h_1,∂^2/∂^2f,
    	=sinθ_,/2π-^⊤+_,_,^⊤,


    h_2,∂^2/∂∂f, = 1/2ππ-θ_,+_,^⊤+_,^⊤,

where

    _, = -cosθ_,,   _, = _,/_,.

To formally define the Hessian of F (a kn× kn matrix), we partition it 
into n× n blocks, each of size k× k. Define h̃_1_i,∈^kn× kn to equal h_1_i, on the i-th d× d diagonal block and zero elsewhere. For _i,_j define h̃_2_i,_j∈^kn× kn to 
equal h_2_i,_j on the i,j-th k× k block and zero 
elsewhere. We now have that the Hessian is given by

    ∇^2F = 1/2 + ∑_i,j=1
    i≠ j^nh̃_1_i,_j - ∑_i∈n
    j∈kh̃_1_i,_j + ∑_i,j=1
    i≠ j^nh̃_2_i,_j.




  §.§.§ Lower bound on λ_min


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^⊤ of a matrix 
A, we bound the error using the distance of UDU^⊤ from A, as well as 
the distance of U from its projection on the subspace of orthogonal matrices 
given by U̅ UU^⊤U^-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.

	For any natural n≥0 we have
	
    4^-n∑_k=0^n2kk2n-2kn-k=1.




	Clearly, for any x<1 we have
	
    1/1-x=∑_k=0^∞x^k.

	Using the generalized binomial theorem, we have for any x<1
	
    1/√(1-x)   = ∑_k=0^∞k-0.5kx^k 
    		= ∑_k=0^∞∏_i=0^k-1k-i-0.5/k!x^k 
    		
       = ∑_k=0^∞∏_i=0^k-12k-2i-1/2^kk!x^k 
    		
    		= 
    		∑_k=0^∞2^kk!∏_i=0^k-12k-2i-1/4^kk!^2x^k
    		 
       = 
    		∑_k=0^∞∏_i=0^k-12k-2i∏_i=0^k-12k-2i-1/4^kk!^2x^k
    		= ∑_k=0^∞2k!/4^kk!^2x^k 
       = ∑_k=0^∞2kk4^-kx^k.

	Consider the k-th coefficient in the expansion of the square of (<ref>), which is well defined as the sum converges absolutely for any x<1. From (<ref>), these coefficients are all 1. However, these are also given by the expansion of the square of (<ref>). 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 (<ref>) with index ≤ k, thus we have
	
    4^-n∑_k=0^n2kk2n-2kn-k=1.




	Let U^⊤U be a diagonally dominant matrix, let E = -U^⊤U satisfying E≤ C<1. Then U^⊤U^-0.5 = ∑_n=0^∞2nn4^-nE^n. Moreover, E^'∑_n=1^∞2nn4^-nE^n satisfies E^'≤1/√(1-C)-1.



	Consider the series given by the partial sums
	
    S_n=∑_k=0^n2kk4^-kE^k,

	and observe that
	
    U^⊤US_n^2    = -E∑_k=0^n2kk4^-kE^k^2 
       = -E∑_k=0^nE^k+∑_k=n+1^2nβ_kE^k
       = -E^n+1+-EE^n+1∑_k=0^n-1β_n+k+1E^k,

	where the second equality is due to lem:central_binom_id, and holds for some β_k∈0,1, k∈n+1,…,2n. Now, since
	
    lim_n→∞-EE^n+1∑_k=0^n-1β_n+k+1E^k
    ≤   lim_n→∞-EE^n+1∑_k=0^n-1β_n+k+1E^k
    ≤   lim_n→∞-EE^n+1∑_k=0^n-1β_n+k+1E^k
    ≤   lim_n→∞-EE^n+1∑_k=0^n-1C^k
    ≤   lim_n→∞-EE^n+11-C^-1
    
    		=   0,

	we have that (<ref>) reduces to  as n→∞, concluding the proof of the lemma.

Turning back to the algorithm analysis, we wish to numerically compute the eigenvalues of A and bound their deviation due to roundoff errors. Other than the inaccuracy in computing A^''≈ A^', another obstacle is that U is not exactly orthogonal, however it is very close to orthogonal in the sense that E=I-U^⊤U has a small norm.
Let U̅=UU^⊤U^-0.5 be the projection of U onto the space of orthogonal matrices in ^d× d. Clearly, U^⊤U^-0.5 is well defined if U^⊤U is diagonally-dominant, hence positive-definite, which can be easily verified. Also,

    U̅^⊤U̅   =UU^⊤U^-0.5UU^⊤U^-0.5^⊤
       = UU^⊤U^-0.5U^⊤U^-0.5U^⊤
       = UU^⊤U^-1U^⊤
       = UU^-1U^⊤^-1U^⊤
       = 𝐈.

We now upper bound A^''-A̅, where A̅=U̅DU̅^⊤ and therefore its spectrum is given to us explicitly as the diagonal entries of D, diagD.
Compute

    A^''-A̅   = UDU^⊤-U̅DU̅^⊤
       = UDU^⊤-UU^⊤U^-0.5DUU^⊤U^-0.5^⊤
       = UD-U^⊤U^-0.5DU^⊤U^-0.5U^⊤
       = UD-I+E^'DI+E^'U^⊤
       = UE^'D+DE^'+E^'2U^⊤
       ≤U^2E^'D+DE^'+E^'2
       ≤U^22DE^'+E^'^2
       ≤ B^22λ_max1/√(1-C)-1+1/√(1-C)-1^2
       =ϵ_3.

Estimating the spectrum diagD of A using the spectrum of A̅ yields an approximation error of

    A-A̅   = A-A^'+A^'-A^''+A^''-A̅
       ≤A-A^'+A^'-A^''+A^''-A̅
       ≤ϵ_1 + ϵ_2 + ϵ_3,

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 E^'.
Verifying the upper bound given by B, we compute

    U = U-I+I≤U-I+I≤ 1+U-I_F.

Whenever U is close to unity, this provides a sharper upper bound than taking C=U_F.

Finally, applying Weyl's inequality (thm:weyl) to A and A̅, we have that the spectra of the two cannot deviate by more than ϵ_1+ϵ_2+ϵ_3, concluding the proof of the algorithm.




  §.§.§ Upper Bound on Remainder Term R_,


In a nutshell, to derive an upper bound L on the third order term in 
(<ref>), 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  (see 
lem:key), we observe, however, that lem:hess_sp_norm_bound 
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  where we bound the third order 
term[specifically, the radius was chosen to be a 10^-3 fraction 
of max_i∈n_i_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.

In what follows, the ball where the third order bound is derived on is referred to as some compact subset of the weight space A⊆^kn. We now define some notation that will be used throughout the rest of this section. Given A, define

    _min=min_∈ Amin_i∈n_i_2,


    _max=max_∈ Amax_i∈n_i_2.

That is, _min and _max are the neurons with minimal and maximal norm among all possible network weights in the set A, respectively. Similarly, defining _max to be the target parameter vector with maximal 2-norm, the necessary bound is now given by the following theorem:










	Suppose ∇^2 F· is differentiable on A⊆^kn. Then
	
    sup_∈ A
    :_2=1∑_i_1,i_2,i_3∂^3/∂ w_i_1∂ w_i_2∂ w_i_3Fu_i_1u_i_2u_i_3≤ L_A,

	where
	
    L_An/π_min^2√(2)n-1_max+_min + k_max.


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


	Suppose ∇^2F· is differentiable on A⊆^kn. Then
	
		
  * h_1, is _max/π_min^2 Lipschitz in  on A.
		
  * h_1_1,_2 is √(2)_max/π_min^2 Lipschitz in _1,_2 on A.
		
  * h_2_1,_2 is √(2)/π_min Lipschitz in _1,_2 on A.
	



	We begin with computing some useful derivatives:
	
    ∂/∂cosθ_,
    	= ∂/∂^⊤/ 
    	= / - 
    	/^2^⊤/ 
    	= _,/ .

	
	
    ∂/∂sinθ_,   = ∂/∂√(1-^⊤/^2) 
    	= 
    	-^⊤//√(1-^⊤/^2)_,/
       = 
    	-cosθ_,/sinθ_,_,
    	= -cosθ_,/_,.

	
	
    ∂/∂θ_,   = ∂/∂arccos^⊤/ 
    	= -1/√(1-^⊤/^2)_,/ 
    	= -_,/.

	Now, differentiating the spectral norms of h_1 and h_2 using lem:hess_sp_norm_bound yields
	
    ∂/∂h_1,   = ∂/∂sinθ_,/π
       = -cosθ_,/π^2_, + sinθ_,/π^2
       = /π^2sinθ_, - cosθ_,_,,

	therefore
	
    ∂/∂h_1,_2 
    
    	=   /π^2sinθ_, - cosθ_,_,_2 
    
    	=   /π^2√(sinθ_, - cosθ_,_,^⊤sinθ_, - cosθ_,_,)
    
    	=   /π^2√(sin^2θ_,^2 + cos^2θ_,_,^2)
    
    	=   /π^2.

	Next, differentiating with respect to  gives
	
    ∂/∂h_1,   = ∂/∂sinθ_,/π
       = -cosθ_,/π_, + sinθ_,/π
       = 1/πsinθ_, - cosθ_,_,,

	so
	
    ∂/∂h_1,_2
    	= 1/πsinθ_, - cosθ_,_,
    	= 1/π.

	Concluding the derivation for the spectral norm of the gradient of h_1 we get
	
    ∂/∂,h_1,_2
    	= √(1/π^2 + /π^2^2)
    	= 1/π^2√(^2+^2).

	Similarly, for h_2 we have
	
    ∂/∂h_2,   = ∂/∂1/2ππ-θ_,+sinθ_,
       = 1/2π_,/ - cosθ_,/_,
       = 1-cosθ_,/2π_,,

	thus
	
    ∂/∂h_2,_2
    	   = 
    	1-cosθ_,/2π_,_2
    	= 1-cosθ_,/2π≤1/π.

	For the gradient with respect to  we have
	
    ∂/∂h_2,   = ∂/∂1/2ππ-θ_,+sinθ_,
       = 1/2π_,/ - cosθ_,/_,
       = 1-cosθ_,/2π_,,

	which implies
	
    ∂/∂h_2,_2
    	= 
    	1-cosθ_,/2π_,_2
    	 
    
    	= 1-cosθ_,/2π.

	Concluding the derivation for the spectral norm of the gradient of h_2 we get
	
    ∂/∂,h_2,_2
    	   = √(1-cosθ_,/2π^2+1-cosθ_,/2π^2)
       ≤1/π√(1/^2+1/^2).

	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 _min,_max,_max in (<ref>) and (<ref>).



	Suppose ∇^2 F· is differentiable on A⊆^kn. Then ∇^2 F· is L_A-Lipschitz in  on A.



	Since lem:h1h2_lipschitz implies the Lipschitzness of the spectral norms of h̃_1,h̃_2 in ∈^kn, we let =_1,…,_n, =_1^',…,_n^'∈ A, then compute
	
    ∇^2 F - ∇^2 F
              = ||1/2 + ∑_i,j=1
    i≠ j^nh̃_1_i,_j - ∑_i=1,…,n
    j=1,…,kh̃_1_i,_j + ∑_i,j=1
    i≠ 
    	j^nh̃_2_i,_j.. 
                       - ..1/2 + 
    	∑_i,j=1
    i≠ 
    	j^nh̃_1_i^',_j^' - 
    	∑_i=1,…,n
    j=1,…,kh̃_1_i^',_j + ∑_i,j=1
    i≠ 
    	j^nh̃_2_i^',_j^'||_sp
              = ||∑_i,j=1
    i≠ j^nh̃_1_i,_j - 
    	h̃_1_i^',_j^' + 
    	∑_i=1,…,n
    j=1,…,kh̃_1_i,_j - 
    	h̃_1_i^',_j.. 
                       + ..∑_i,j=1
    i≠ j^nh̃_2_i,_j - 
    	h̃_2_i^',_j^'||_sp
              ≤∑_i,j=1
    i≠ j^nh̃_1_i,_j - 
    	h̃_1_i^',_j^' + 
    	∑_i=1,…,n
    j=1,…,kh̃_1_i,_j - h̃_1_i^',_j
                       + ∑_i,j=1
    i≠ j^nh̃_2_i,_j - 
    	h̃_2_i^',_j^'
              ≤∑_i,j=1
    i≠ j^n√(2)_max/π_min^2-_2
    	 + ∑_i=1,…,n
    j=1,…,k_max/π_min^2-_2 + 
    	∑_i,j=1
    i≠ j^n√(2)/π_min-_2 
              = nn-1√(2)_max/π_min^2 + nk 
    	_max/π_min^2 + nn-1√(2)/π_min-_2 
              = n/π_min^2√(2)n-1_max+_min + 
    	k_max-_2.




	Let ,∈ A. For any ∈^kn with _2=1 we have using lem:hess_lipschitz
	
    ^⊤∇^2 F - ^⊤∇^2 F
    
    	=   ^⊤∇^2 F - ∇^2 F
    ≤   ∇^2 F - ∇^2 F
    ≤    L_A-_2,

	therefore the differentiable on A, ^kn→ function ↦^⊤∇^2 F+t is L_A-Lipschitz for any ∈^kn, =1, and any t satisfying +t∈ A, hence its derivative on A is upper bounded by L_A. Namely, we have that
	
    sup_∈ A
    :_2=1∑_i_1,i_2,i_3∂^3/∂ w_i_1∂ w_i_2∂ w_i_3Fu_i_1u_i_2u_i_3≤ L_A.

	




  §.§.§ Lipschitzness of F and Proof of 
lem:key2
 


In this subsection, we turn to proving a Lipschitz bound on the objective in 
(<ref>), implying lem:key2 and showing that the 
local minimum identified in 
(<ref>) is necessarily non-global. A 
straightforward approach would be to globally upper bound ∇ 
F (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 ∇ F close to our points of interest are very 
small. Instead, we first derive a Lipschitz bound on ∇^2F, implying that ∇ F does not vary too greatly, and 
therefore remains small for any  in the ball enclosing , providing a stronger bound than the more naive approach.






	Suppose F is thrice-differentiable on A⊆^kn. Then for any ,
	∈ A, 
    F-F≤-_2LH 
    	-_2 + ∇ F_2,
 
	where
	
    LH 1/2 +nn-1_max/2π_min+1/2 + nk_max/2π_min.


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


	Suppose F is thrice-differentiable on A⊆^kn. Then
	
    sup_∈ A∇^2F≤1/2 +nn-1_max/2π_min+1/2 + nk_max/2π_min.




	Recall the Hessian of the objective as defined in (<ref>). 
	Using lem:hess_sp_norm_bound, the fact that the spectral norms of 
	h_1,h_2 and h̃_1,h̃_2 are identical, and the fact 
	that sinx≤ x for any x>0, we have for any ∈ A 
	
    ∇^2F   = 1/2 + ∑_i,j=1
    i≠ j^nh̃_1_i,_j - ∑_i=1,…,n
    j=1,…,kh̃_1_i,_j + ∑_i,j=1
    i≠ j^nh̃_2_i,_j
       ≤1/2 +∑_i,j=1
    i≠ j^nh̃_1_i,_j + ∑_i=1,…,n
    j=1,…,kh̃_1_i,_j + ∑_i,j=1
    i≠ j^nh̃_2_i,_j
       ≤1/2 +∑_i,j=1
    i≠ j^nsinθ__i,_j_j/2π_i + ∑_i=1,…,n
    j=1,…,ksinθ__i,_j_j/2π_i
              + ∑_i,j=1
    i≠ j^n1/2ππ-θ__i,_j+sinθ__i,_j
       ≤1/2 +∑_i,j=1
    i≠ j^n_max/2π_min + ∑_i=1,…,n
    j=1,…,k_max/2π_min
    	+ ∑_i,j=1
    i≠ j^n1/2ππ
       ≤1/2 +nn-1_max/2π_min+1/2 + nk_max/2π_min.




	For some ∈^kn, consider the function g_t=^⊤∇ F + 
	t-
	
	Since F is thrice-differentiable, we have from the mean value theorem that there exists some t_ such that 
	
    ^⊤∇ F - ∇ F   = g_1-g_0/1-0
       = g^'_t_
       = ^⊤∇^2F + t_--.

	Taking =∇ F + ∇ F and recalling that from lem:hess_bounded we have that sup_∈ A∇^2F is bounded by LH, we get
	
    ∇ F_2^2 - ∇ F_2^2 
    
    	=   ∇ F + ∇ F^⊤∇ F - ∇ F
    
    	=   ∇ F + ∇ F^⊤∇^2F + t_--
    ≤   ∇ F + ∇ F_2 ∇^2F + t_--_2 
    ≤   ∇ F_2 + ∇ F_2 LH -_2.

	Dividing by ∇ F_2 + ∇ F_2 and rearranging yields
	
    ∇ F_2 ≤ LH -_2 + ∇ F_2.

	That is, the target function F is LH -_2 + ∇ F_2-Lipschitz on A, thus
	
    F-F≤-_2LH -_2 + ∇ F_2.



	For A which is a ball of radius r centered at =_1,…,_n, we have that _max = max_i_i + r as well as _min = min_i_i - r. Plugging this in thm:F_bound and substituting -_2 ≤ r completes the proof of the lemma.




 §.§ Proof of Corollary <ref>

	
To show the first part of Corollary <ref>, we will use the following lemma:

	Let =_1,…,_n, V=_1,…,_k where _i,_j∈^k for all i∈n,j∈k. Denote for any natural m≥0, m = _1,…,_n, _i = _i, 0∈^k+m, Ṽ_m = _1,…,_k, _i = _i, 0∈^k+m and let M∈^n× n be the matrix with entries  
    M_ij =  1/2 + ∑_l=1 
     l≠ i^nsinθ__i,_l_l/2π_i - ∑_l=1^k sinθ__i,_l_l/2π_i,     i=j 
    1/2ππ - θ__i,_j,     i≠ j
    		.

	Then the spectrum of ∇^2 Fm is comprised of the spectrum of ∇^2 F and the spectrum of M with multiplicity m. In particular, if ∇^2 F1≽λ_min· then ∇^2 Fm≽λ_min·, for any m>1.



	A straightforward substitution of m and Ṽ_m in (<ref>), and a permutation of the rows and columns of the resulting matrix reveals that
	
    ∇^2 Fm=
    		[ ∇^2 F     0     0     ⋯     0;     0     M     0     ⋯     0;     0     0     M     ⋯     0;     ⋮     ⋮     ⋮     ⋱     ⋮;     0     0     0     ⋯     M ].

	Now, diagonalizing the block diagonal ∇^2 Fm completes the proof of the lemma.



	Back to the first part of Corollary <ref>, we have from 
	lem:same_spectrum that the lower bound on the smallest eigenvalue 
	of ∇^2 F1 holds for ∇^2 
	Fm for any m≥1. Furthermore, since _2=m_2 for any m≥0 we have that 
	the upper bound on the third order derivatives from 
	sec:remainder_bound and the Lipschitz bound on the objective 
	from subsec:objective_lipschitzness still hold, as well as the 
	bound on the norm of the gradient. Therefore by running the simulations in sec:experiments on 1 instead of , the 
	results apply in any optimization space ^nk+m, for 
	natural m≥0, since the conditions for invoking lem:key and 
	lem:key2 are met with the same exact constants[Note that for m=0 the eigenvalue lower bound constant may change, since the spectrum of M has no impact on the spectrum of ∇^2 F0. This, however, can only result in a stronger lower bound and does not affect the validity on the results obtained when running the experiments in sec:experiments with m=1.], completing the first part of the corollary.
	
	For the second part of the corollary, we note that if _1,…,_k 
	are chosen i.i.d. from (0,cI), then by standard 
	concentration arguments, for any ϵ>0 and high enough dimension d 
	(depending on k,ϵ), it holds with probability at least 
	1-exp(-Ω(d)) that 
	|1/√(cd)_i-1|≤ϵ and 
	|1/cd_i^⊤_i'|≤ϵ for all 
	i,i'∈{1,…,k} (see 
	<cit.>). Therefore, regardless of which 
	distribution we are considering, with probability at least 
	1-exp(-Ω(d)), we can find a scalar a>0 and an orthogonal matrix 
	M, such that aM_i-_i≤ϵ for all i, where 
	_i is the i-th standard basis vector. 
	
	Letting F be our objective function (w.r.t. the randomly chosen 
	_1,…,_k), and using the rotational 
	symmetry of the Gaussian distribution and the positive-homogeneity of the 
	ReLU function, we have
	
    F()    = 1/2_∼(0,I)[ (∑_i=1^n[_i^⊤]_+
    	-∑_i=1^k[_i^⊤]_+)^2 ]
       =
    	1/2_∼(0,I)[ (∑_i=1^n[_i^⊤(M^⊤)]_+
    	-∑_i=1^k[_i^⊤(M^⊤)]_+)^2 ]
       =
    	1/2a^2·_∼(0,I)[ (∑_i=1^n[(aM_i)^⊤]_+
    	-∑_i=1^k[(aM_i)^⊤]_+)^2 ] .

	It follows that F has the same local minima as 
	
    F̃()  := 1/2_∼(0,I)[ (∑_i=1^n[_i^⊤]_+
    	-∑_i=1^k[(aM_i)^⊤]_+)^2 ],

	since they are equivalent after scaling and rotation
	(F̃() = a^2 F(1/aM^⊤)). Thus, it is enough to prove 
	existence of local minima for F̃. 
	
	By the argument above, we can rewrite F̃() as
	
    F̃() := F̃__1,…,_k() = 1/2_∼(0,I)[ (∑_i=1^n[_i^⊤]_+
    	-∑_i=1^k[_i^⊤]_+)^2 ],
	
	where (with high probability) each _i is ϵ-close to 
	the standard basis vector 
	_i. If _i=_̃ĩ, we have already shown that there is some 
	local minimum , which is in the interior of a sphere S such that 
	F()<min_∈ SF(), and moreover, the ball B enclosed by S does 
	not contain global minima (see (<ref>))
	since thm:F_bound and the condition in (<ref>) imply that the minimal value in the ball enclosing  is strictly positive. In 
	particular, let ϵ_0>0 be such that 
	F()<min_∈ SF()-ϵ_0 and min_∈ 
	BF()>inf_F()+ϵ_0. It is easily verified that by 
	setting ϵ small enough (depending only on ,B,ϵ_0 which 
	are all fixed), we can ensure that
	
    max_∈ B|F̃__1,…,_k()
    	-F̃__1,…,_k()| ≤ϵ_0/3,

	and therefore
	
    F̃__1,…,_k()<
    	min_∈ SF̃__1,…,_k(),

	as well as
	
    min_∈ 
    	BF̃__1,…,_k()>
    inf_F̃__1,…,_k(),

	which implies that any minimizer of 
	F̃__1,…,_k over B must be a local 
	(non-global) minimum.
	


 §.§ Technical Proofs




  §.§.§ Derivation of ∇^2F



	The Hessian of F at point = _1,…,_n with respect to target values _1,…,_k is given on the main diagonals 
	
    ∂^2F/∂_i^2 = 1/2𝐈 + ∑_j=1
    j≠ i^n h_1_i,_j - ∑_j=1^k h_1_i,_j,

	and on the off-diagonals by
	
    ∂^2F/∂_i∂_j=h_2_i,_j,

	where
	
    h_1,
    	=sinθ_,/2π𝐈-^⊤+_,_,^⊤,

	and
	
    h_2,= 1/2ππ-θ_,+_,^⊤+_,^⊤.




	By a straightforward calculation, we have
	
    ∂^2 f,/∂ w_i^2   =1/2π(1/-w_i^2/^3sinθ_,-w_i/^⊤//√(1-^⊤/^2)v_i/-w_i/^2^⊤/. 
               + .v_i/√(1-^⊤/^2)v_i/-w_i/^2^⊤/)
       = 1/2π/sinθ_,+w_i^2cos2θ_,/^3sinθ_,-2w_iv_icosθ_,/^2sinθ_,+v_i^21/sinθ_,

	
	
    ∂^2 f,/∂ w_iw_j   =1/2π(-w_iw_j/^3sinθ_,-w_i/^⊤//√(1-^⊤/^2)v_j/-w_j/^2^⊤/. 
               + .v_i/√(1-^⊤/^2)v_j/-w_j/^2^⊤/)
       = 1/2πw_iw_jcos2θ_,/^3sinθ_,-w_iv_j+w_jv_icosθ_,/^2sinθ_,+v_iv_j1/sinθ_,

	
	Hence
	
	
    ∂^2 f,/∂^2   = 1/2π(/sinθ_,+cos2θ_,/^3sinθ_,^⊤.
               .- cosθ_,/^2sinθ_,^⊤+^⊤+1/sinθ_,^⊤)
       = /2πsinθ_,𝐈+cos2θ_,/sinθ_,^⊤-cosθ_,/sinθ_,^⊤+^⊤+1/sinθ_,^⊤
       = /2πsinθ_,sin^2θ_,𝐈-^⊤+-cosθ_,-cosθ_,^⊤.

	Recall the definition of  in (<ref>), we have that
	
    ^2    = -cosθ_,^⊤-cosθ_,
       = ^⊤-2cosθ_,^⊤ + cos^2θ_,^⊤
       = 1-cos^2θ_,
       = sin^2θ_,.

	Therefore (<ref>) can be written as
	
    ∂^2 f,/∂^2
    	=sinθ_,/2π𝐈-^⊤+_,_,^⊤.

	Differentiating with respect to different individual parameter vectors, we 
	have
	
    ∂^2 f,/∂ w_i∂ v_i   =1/2π(w_i/v_i/sinθ_,-^⊤//√(1-^⊤/^2)w_i/-v_i/^2^⊤/.
               + .π-θ_,+v_i/√(1-^⊤/^2)w_i/-v_i/^2^⊤/)
       = 1/2π(-w_i^2cosθ_,/^2sinθ_,+w_iv_i1/sinθ_,+1/sinθ_,+cos^2θ_,/sinθ_,.
       .-v_i^2cosθ_,/^2sinθ_,+π-θ_,)
       = 1/2π(-w_i^2cosθ_,/^2sinθ_,+w_iv_i2/sinθ_,-v_i^2cosθ_,/^2sinθ_,+π-θ_,)

	
	
    ∂^2 f,/∂ w_i∂ v_j   =1/2π(w_i/v_j/sinθ_,-^⊤//√(1-^⊤/^2)w_j/-v_j/^2^⊤/.
               + .v_i/√(1-^⊤/^2)w_j/-v_j/^2^⊤/)
       = 1/2π(-w_iw_jcosθ_,/^2sinθ_,+w_iv_j1/sinθ_,+cos^2θ_,/sinθ_,.
       .        +w_jv_i1/sinθ_,-v_iv_jcosθ_,/^2sinθ_,)
       = -1/2π(w_iw_jcosθ_,/^2sinθ_,-w_iv_j1/sinθ_,.
       .        -w_jv_i1/sinθ_,+v_iv_jcosθ_,/^2sinθ_,).

	Hence
	
    ∂^2 f,/∂∂   = π-θ_,/2π𝐈+1/2πsinθ_,++^⊤-1+cosθ_,^⊤+^⊤
       = π-θ_,/2π𝐈+1/2πsinθ_,^⊤+^⊤-cosθ_,^⊤-cosθ_,^⊤
       = π-θ_,/2π𝐈+1/2πsinθ_,-cosθ_,^⊤+-cosθ_,^⊤
       =
    	1/2ππ-θ_,+_,^⊤+_,^⊤.

	Recall the objective in (<ref>), we have that its Hessian is comprised of n× n blocks of size d× d each. On the main diagonal we therefore have
	
    ∂^2F/∂_i^2   =∂^2/∂_i^21/2f_i,_i + ∑_j=1
    j≠ i^nf_i,_j + ∑_j=1^kf_i,_j
       =1/2 + ∑_j=1
    j≠ i^n h_1_i,_j - ∑_j=1^k h_1_i,_j,

	and on the off diagonal we have
	
    ∂^2F/∂_i∂_j=h_2_i,_j.


	


  §.§.§ The Spectral Norm of h_1 and h_2



	We have that
	
		
  * h_1, = 
		sinθ_,/π.
		
  * h_2, = 1/2ππ - θ_, + 
		sinθ_,.
	



	To find the spectral norm, we compute the spectra of h_1, h_2.
	
		
  * Clearly, for any ∈^d orthogonal to both ,_, we have
		
    h_1, = sinθ_,/2π-^⊤+_,_,^⊤ = sinθ_,/2π.
 
		Thus sinθ_,/2π is an eigenvalue of h_1 with multiplicity at least d-2. Since ,_, are orthogonal, their corresponding eigenvalues comprise the rest of the spectrum of h_1. Compute
		
    h_1,   = sinθ_,/2π-^⊤+_,_,^⊤
       = sinθ_,/2π-^2
       = 0.

		Hence 0 is the eigenvalue of .
		Also,
		
    h_1,_,   = sinθ_,/2π-^⊤+_,_,^⊤_,
       = sinθ_,/2π_,+_,_,^2
       = sinθ_,/π_,.

		Therefore sinθ_,/π is the largest eigenvalue of h_1.
		
  * Once again, for any ∈^d orthogonal to both , we have
		
    h_2, = 1/2ππ-θ_,+_,^⊤+_,^⊤ = 1/2ππ-θ_,.

		Thus 1/2ππ-θ_, is an eigenvalue of h_2 with multiplicity at least d-2. We now show the remaining two eigenvalues correspond to the eigenvectors _, + _, and _, - _,.
		
    h_2,_, - _,
    
    		=   1/2ππ-θ_,+_,^⊤+_,^⊤_, - _,
    
    		=   1/2ππ-θ_,_, - _,+_,^⊤_,-_,^⊤_,
    
    		=   1/2ππ-θ_,_, - _,+_,^⊤-cosθ_,/sinθ_,-_,^⊤-cosθ_,/sinθ_,
    
    		=   1/2ππ-θ_,_, - _,+_,1-cos^2θ_,/sinθ_,-_,1-cos^2θ_,/sinθ_,
    
    		=   1/2ππ-θ_,_, - _,-sinθ_,_, - _,
    
    		=   1/2ππ-θ_,-sinθ_,_, - _,.

		Hence 1/2ππ-θ_,-sinθ_, is an eigenvalue of h_2. Similarly, we have
		
    h_2,_, + _,
    
    		=   1/2ππ-θ_,+_,^⊤+_,^⊤_, + _,
    
    		=   1/2ππ-θ_,_, + _,+_,^⊤_,+_,^⊤_,
    
    		=   1/2ππ-θ_,_, + _,+_,^⊤-cosθ_,/sinθ_,+_,^⊤-cosθ_,/sinθ_,
    
    		=   1/2ππ-θ_,_, + _,+_,1-cos^2θ_,/sinθ_,+_,1-cos^2θ_,/sinθ_,
    
    		=   1/2ππ-θ_,_, + _,+sinθ_,_, + _,
    
    		=   1/2ππ-θ_,+sinθ_,_, + _,.

		Therefore 1/2ππ-θ_,+sinθ_, is the largest eigenvalue of h_2.
	


abbrvnat



