Title: NO SPURIOUS LOCAL MINIMA IN A TWO HIDDEN UNIT RELU NETWORK Anonymous

Abstract: Deep learning models can be efficiently optimized via stochastic gradient descent, but there is little theoretical evidence to support this. A key question in optimization is to understand when the optimization landscape of a neural network is amenable to gradient-based optimization. We focus on a simple neural network: RELU network with one hidden layer consisting of two RELU units, and show that all local minimizers are global. This combined with recent work of Lee et al. (2017) ; Lee et al. (2016) show that gradient descent converges to the global minimizer.

1. INTRODUCTION:

Deep learning has been used to achieve state-of-art performance on a wide variety of problems in machine learning, artificial intelligence, computer vision, and natural language processing. In all these applications, deep models often use hundreds of millions of parameters and are trained with stochastic gradient descent (or other gradient-based methods such as Adagrad (Duchi et al., 2011) , Adam (Kingma and Ba, 2014) ), a surprisingly simple method, and yet finds solutions with both low train and test error.

Despite the empirical success, the mathematical justification for gradient-based methods is not well-understood. Zhang et al. (2016a) empirically demonstrated that sufficiently over-parametrized networks can be efficiently optimized to near global optimality with stochastic gradient. For a two-layer network with leaky ReLU activation, Soudry and Carmon (2016) showed that gradient descent on a modified loss function can obtain a global minimum of the modified loss function; however, this does not imply reaching a global minimum of the original loss function. Under the same setting, Xie et al. (2016) showed that critical points with large "diversity" are nearly globally optimal. Choromanska et al. (2015) used several assumptions to simplify the loss function to a polynomial with i.i.d. Gaussian coefficients. They then showed that every local minima of the simplified loss has objective value comparable to the global minima. Kawaguchi (2016) used similar assumptions to show that all local minimum are global minimum in a nonlinear network. However the assumptions of Choromanska et al. (2015) ; Kawaguchi (2016) require independent activations, meaning that the activations of the hidden units are independent of the input and/or mutually independent, which is violated in practice.

Multiple works have been proposed to circumvent this assumption when dealing with the two-layer ReLU network F (x; W ) = K j=1 σ(w T j x), where σ = max(0, x) is the ReLU activation function. Under the realizable setting (i.e. the labels are generated from a network with "teaching" parameters w * ) and isotropic Gaussian input, Tian (2017) shows that when there is only a single ReLU node gradient descent converges to the global optimum. For K = 2, he conjectured that there are no spurious local minima, and provided a partial characterization of the critical point structure. With the same assumptions, Brutzkus and Globerson (2017) proved, for a two-layer ReLU network with a single non-overlapping convolutional filter, all local minimizers are global. Zhang et al. (2017a) show that for two-layer networks with non-standard activation functions that gradient descent converges to global minimizers.

In this paper, we focus on the case when K = 2 and prove that every local minimum is global. As in previous works (Brutzkus and Globerson, 2017; Tian, 2017; Hardt and Ma, 2016) , we focus on the population loss. The ReLU function is positive homogeneous, so we can rewrite the function as F (x; W ) = v 1 σ(w T 1 x) + v 2 σ(w T 2 x) where w 1 and w 2 are unit vectors; for simplicity, we will assume that v 1 = v 2 = 1. Using these assumptions and an additional orthogonality assumption, we prove that all local minima of the loss surface are global. Although the setting is a simplification of practical neural networks, this is a meaningful step towards understanding the success of gradientbased methods in deep learning and other non-convex optimization problems. For the non-orthogonal case, we provide a partial characterization of the critical point structure.

The paper is organized as follows: Section 2 discusses related works, and Section 3 introduces the notation and definitions. Section 4 shows our main result that all local minima are global and gives a proof sketch and the formal proofs are in Section 5. Section 6 provides some extensions to the non-orthogonal case. Section 7 presents the result of the experiments, and finally, Section 8 concludes the paper.

2. RELATED WORK:

Single Hidden Node Networks: For a neural network with a single hidden unit and monotone activation function σ, numerous authors (Mei et al., 2016; Hazan et al., 2015; Kakade et al., 2011; Kalai and Sastry, 2009; Soltanolkotabi, 2017; Tian, 2017) have shown that gradient-based methods converge to the true parameter w * . In the case of a single hidden unit, the loss function is weakly quasi-convex, meaning that the gradient points in the direction of w * , which explains the success of gradient-based methods. For K > 1 hidden units, the loss function is no longer quasi-convex, so this analysis does not easily generalize. In fact, our analysis for K = 2 is considerably more involved, and requires analyzing the gradient and hessian simultaneously.

Improper Learning: On the improper learning side, Shalev-Shwartz et al. ( 2011) pioneered a kernel-based approach that can be used for learning a single halfspace or smoothed ReLU. This was generalized to fully-connected deep neural networks in Zhang et al. (2016b) using the recursive kernel method. Goel et al. (2016) designed a new smoothed ReLU function that is a better approximation to the ReLU. Instead of learning a neural network, these methods learn a function in a RKHS, hence improper learning. Zhang et al. (2017b) improved upon this by learning a neural network, instead of a kernel machine, via a boosting approach, and with much lower sample complexity. The disadvantages of improper learning are two-fold: 1) the sample complexity for these methods is exponentially larger than the Rademacher complexity of the network, and 2) the practical success of deep learning is intricately tied to using gradient-based training procedures, and the learnability of these networks using improper learning does not explain the success of gradient-based methods. On a related line of work, Janzamin et al. (2015) propose a method of moments estimator using tensor decomposition.

Over-Parametrization There have been several works on studying the effect of over-parametrization on the training of neural networks (Poston et al., 1991; Haeffele and Vidal, 2015) . These results require the width of a hidden layer to be greater than the number of training samples, which is not the case for commonly used networks. Finally, Zhang et al. (2016a) empirically demonstrated that commonly used over-parametrized networks can be efficiently optimized to near global optimality with stochastic gradient descent.

Non-Convex Optimization: Since the loss function of neural networks is non-convex, the theory of training neural networks is closely related to the theory of non-convex optimization. Recently, there is considerable progress on convergence guarantees of first-order and second-order methods, including some applications in machine learning problems. Lee et al. (2016) and Lee et al. (2017) show gradient descent and other first-order methods converge only to local minima, and not saddle points. Jin et al. (2017) and Ge et al. (2015) show that variants of stochastic gradient method converge to local minimizers in polynomial time. Ge et al. (2016) and Ge et al. (2017) show there is no spurious local minima in matrix completion problem and non-convex low rank problems. For the phase retrieval problem, Sun et al. (2016) show that there is no spurious local minimum.

3. PRELIMINARIES:

We study a simple two RELU hidden node network with output function

F (x; w) = σ(w T 1 x) + σ(w T 2 x).

For the duration of this paper, we will assume that x is standard normal in R n and all expectations are with respect to the standard normal. The population loss function is:

EQUATION

Define

EQUATION

so the loss can be rewritten as (ignoring additive constants, then multiplied by 4):

EQUATION

From Brutzkus and Globerson (2017) we get

EQUATION

and

EQUATION

In this paper, we study the landscape of f over the manifold R = { w 1 = w 2 = 1}. The manifold gradient descent algorithm is:

x k+1 = P R (x k -α∇ R f (x k )),

where P R is the orthogonal projector onto the manifold R, and ∇ R is the manifold gradient of f .

4. MAIN RESULT AND PROOF SKETCH:

In order to analyze the global convergence of manifold gradient descent, we need a characterization of all critical points. We show that f (W ) have no spurious local minimizer on the manifold R. Theorem 4.1. Assume w * 1 = w * 2 = 1 and w * T 1 w * 2 = 0, then there is no spurious local minimizer of the objective function (3) on the manifold R = { w 1 = w 2 = 1}. Furthermore, every saddle point or local maximizer has a direction of negative curvature.

The next theorem shows that manifold gradient descent with random initialization converges to the global minimizer Theorem 4.2. With probability one, manifold gradient descent will converge to the global minimizers.

Proof. The objective function f is infinitely differentiable on manifold R. Using Corollary 6 of Lee et al. (2017) , manifold gradient descent will converge to a local minimizer with probability one. Since the only local minima for function f are w 1 = w * 1 , w 2 = w * 2 and w 1 = w * 2 , w 2 = w * 1 , manifold gradient descent converges to the true solutions.

Proof of Theorem 4.1. The proof of the main result is complicated, so let's start with a simpler case, in which both w 1 and w 2 are in span{w

* 1 , w * 2 }. Proposition 4.3. Assume w * 1 = w * 2 = 1, w * T 1 w * 2 = 0 and w 1 , w 2 ∈ span{w * 1 , w * 2 }

, then there is no spurious local minimizer of the objective function (3) on the manifold R = { w 1 = w 2 = 1}. Furthermore, every saddle point or local maximizer has a direction of negative curvature.

The complete proof is given in Appendix B and C, so here we just give a proof sketch.

To prove this, we need some observations. The first important observation is that we are always on manifold { w 1 = w 2 = 1}, and for each vector in the plane with fixed norm, there is only one degree of freedom, which means we can express each vector with only one variable. Thus, we can express the vectors in polar coordinates, where θ 1 and θ 2 are the angles for w 1 and w 2 .

The second observation is we only need to compute the gradient on the manifold and check whether it's zero. Define m(w 1 ) = sin θ 1 ∂f ∂w11 -cos θ 1 ∂f ∂w12 and m(w 2 ) = sin θ 2 ∂f ∂w21 -cos θ 2 ∂f ∂w22 . Then for w 1 and w 2 , the norm of the manifold gradients are |m(w 1 )| and |m(w 2 )|. Thus, we only need to check whether the value of function m is 0 and get rid of the absolute value sign.

Then we apply the polar coordinates onto the manifold gradients, and obtain:

EQUATION

)

The last observation we need for this theorem is that we must divide this problem into several cases because each angle in (300) is a piecewise linear function. If we discuss each case independently, the resulting functions are linear in the angles. The details are in Appendix B. After the calculation of all cases, we found the positions of all the critical points: WLOG assume θ 1 ≤ θ 2 , then there are four critical points in the 2D case: (θ 1 , θ 2 ) = (0, π 2 ), ( π 4 , π 4 ), ( π 4 , 5π 4 ) and ( 5π 4 , 5π 4 ). After finding all the critical points, we compute the manifold Hessian matrix for those points and show that there is a direction of negative curvature. The details can be found in Appendix C. The next step is to reduce it to a three dimensional problem. As stated in the two-dimensional case, the gradient is in span{w 1 , w 2 , w * 1 , w * 2 }, which is four-dimensional. However, using the following lemma, we can reduce it to three dimensions and simplify the whole problem.

Lemma 4.4. If (w 1 , w 2 ) is a critical point, then there exists a set of standard orthogonal basis (e 1 , e 2 , e 3 ) such that e 1 = w * 1 , e 2 = w * 2 and w 1 , w 2 lies in span{e 1 , e 2 , e 3 }.

Even if we simplify the problem into three dimensional case, it still seems to be impossible to identify all critical points explicitly. Our method to analyze the landscape of the loss surface is to find the properties of critical points and then show all saddle points and local maximizers have a direction of negative curvature.

The following two lemmas captures the main geometrical properties of the critical points in three dimensional case. More detailed properties are given is Section 5. 

The ratio in Lemma 4.5 captures an important property of all critical points. For simplicity, based on D.5, we define

EQUATION

)

.

Then from the properties of θ 1 , θ 2 and upper bound the value of k 0 we get Lemma 4.6. θ 1 = θ 2 .

That lemma shows that w 1 and w 2 must be on a plane whose projection onto span{w * 1 , w * 2 } is the bisector of w * 1 and w * 2 . Combining this with the computation of Hessian, we conclude that we have found negative curvature for all possible critical points, which leads to the following proposition.

Proposition 4.7. Assume w * 1 = w * 2 = 1, w * T 1 w * 2 = 0 and ∃i ∈ [2], w i / ∈ span{w * 1 , w * 2 }

, then there is no spurious local minimizer of the objective function (3) on the manifold { w 1 = w 2 = 1}. Furthermore, every saddle point or local maximizer has a direction of negative curvature.

Combining both Propositions 4.3 and 4.7, we have proved Theorem 4.1, which is the main result of this paper.

5. PROOFS:

Here we provide some detailed proofs which are important for the understanding of the main theorem.

5.1. WHY WE ONLY NEED 3 DIMENSION:

In general case, the following lemma shows we only need three dimension. Lemma 5.1. If (w 1 , w 2 ) is a critical point, then there exists a set of standard orthogonal basis (e 1 , e 2 , e 3 ) such that e 1 = w * 1 , e 2 = w * 2 and w 1 , w 2 lies in span{e 1 , e 2 , e 3 }.

Proof. If (w 1 , w 2 ) is a critical point, then

EQUATION

)

where matrix (I -w 1 w T 1 ) projects a vector onto the tangent space of w 1 . Since

EQUATION

we get

EQUATION

which means that (π -θ w1,w2 )w 2 -(π -θ w1,w * 1 )w * 1 -(π -θ w1,w * 2 )w * 2 lies in the direction of w 1 . If θ w1,w2 = π, i.e., w 1 = -w 2 , then of course the four vectors have rank at most 3, so we can find the proper basis. If θ w1,w2 < π, then we know that there exists a real number r such that

EQUATION

)

Since θ w1,w2 < π, we know that the four vectors w 1 , w 2 , w * 1 and w * 2 are linear dependent. Thus, they have rank at most 3 and we can find the proper basis.

5.2. SOME PROPERTIES OF CRITICAL POINTS:

Next we will focus on the properties of critical points. Assume (w 1 , w 2 ) is one of the critical points, from lemma D.1 we can find a set of standard orthogonal basis (e 1 , e 2 , e 3 ) such that e 1 = w * 1 , e 2 = w * 2 and w 1 , w 2 lies in span{e 1 , e 2 , e 3 }. Furthermore, assume w 1 = w 11 e 1 + w 12 e 2 + w 13 e 3 and w 2 = w 21 e 1 + w 22 e 2 + w 23 e 3 , i.e., w 1 = (w 11 , w 12 , w 13 ) and w 2 = (w 21 , w 22 , w 23 ). Since we have already found out all the critical points when w 13 = w 23 = 0, in the following we assume w 2 13 + w 2 23 = 0. First, we give the fundamental equation in our analysis. Lemma 5.2.

EQUATION

)

Proof. Adapting from the proof of lemma D.4 and we know that

EQUATION

Similarly, we have

EQUATION

)

Taking the first component of ( 217) and ( 218) gives us

EQUATION

EQUATION

Thus,

EQUATION

Similarly, we get

EQUATION

EQUATION

)

Using this equation, we obtain several properties of critical points. The following two lemmas show the basic properties of critical points in three dimensional case. Completed proofs are given in Appendix B and C. Lemma 5.3. θ w1,w2 < π. Lemma 5.4. w 13 * w 23 < 0.

These two lemmas restrict the position of critical points in some specific domains.

Then we construct a new function F in order to get more precise analysis. Define

EQUATION

From the properties of that particular function and upper bound the value of k 0 we get Lemma 5.5.

θ 1 = θ 2 .

That lemma shows that w 1 and w 2 must be on a plane whose projection onto span{w * 1 , w * 2 } is the bisector of w * 1 and w * 2 . Although we cannot identify the critical points explicitly, we will show these geometric properties already capture the direction of negative curvature.

6. ANALYSIS OF CRITICAL POINTS FOR NON-ORTHOGONAL W *:

In this section, we partially characterize the structure of the critical points when w * 1 , w * 2 are nonorthogonal, but form an acute angle. In other words, the angle between w * 1 and w * 2 is α ∈ (0, π 2 ). Let us first consider the 2D cases, i.e., both w 1 and w 2 are in the span of w * 1 and w * 2 . Similar to the original problem, after the technique of changing variables(i.e., using polar coordinates and assume θ 1 and θ 2 are the angles of w 1 and w 2 in polar coordinates), we divide the whole plane into 4 parts, which are the angle in [0, α], [α, π], [π, π + α] and [π + α, 2π). We have the following lemma: Lemma

6.1. Assume w * 1 = w * 2 = 1, w * T 1 w * 2 > 0 and w 1 , w 2 ∈ span{w * 1 , w * 2 }.

When w 1 and w 2 are in the same part(one of four parts), the only critical points except the global minima are those when both w 1 and w 2 are on the bisector of w * 1 and w * 2 .

Proof. The complete proof is given in appendix E, the techniques are nearly the same as things in the original problem and a bit harder, so to be brief, we omit the proof details here.

For the three-dimensional cases cases of this new problem, it's interesting that the first few lemmatas are still true. Specifically, Lemma D.1(restated as Lemma 4.4) to Lemma D.5(restated as Lemma 4.5) are still correct. The proof is very similar to the proofs of those lemmas, except we need modification to the coefficients of terms in the expressions of the manifold gradients. 

7. EXPERIMENTS:

We did experiments to verify the theoretical results. Since our results are restricted to the case of K = 2 hidden units, it is also natural to investigate whether general two-layer ReLU networks also have the property that all local minima are global minima. Unfortunately as we show via numerical simulation, this is not the case. We consider the cases of K from 2 to 11 hidden units and we set the dimension d = K. For each K, the true parameters are orthogonal to each other. For each K, we run projected gradient descent with 300 different random initializations, and count the number of local minimum (critical points where the manifold Hessian is positive definite) with non-zero training error. If we reach a sub-optimal local minimum, we can conclude the loss surface exhibits spurious local minima. The bar plot showing the number of times gradient descent converged to spurious local minima is in Figure 1 . From the plot, we see there is no spurious local minima from K = 2 to K = 6. However for K ≥ 7, we observe a clear trend that there are more spurious local minima when there are more hidden units.

8. CONCLUSION AND FUTURE WORK:

In this paper, we provided recovery guarantee of stochastic gradient descent with random initialization for learning a two-layer neural network with two hidden nodes, unit-norm weights, ReLU activation functions and Gaussian inputs. Experiments are also done to verify our results. For future work, here we list some possible directions.

8.1. GENERAL CASE OF NETWORKS:

This paper focused on a ReLU network with only two hidden units, . And the teaching weights must be orthogonal. Those are many conditions, in which we think there are some conditions that are not quite essential, e.g., the orthogonal assumption. In experiments we have already seen that even if they are not orthogonal, it still has some good properties such as the positions of critical points. Therefore, in the future we can further relax or abandon some of the assumptions of this paper and preserve or improve the result we have.

8.2. BAD LOCAL MINIMA:

The neural network we discussed in this paper is in some sense very simple and far from practice, although it is already the most complex model when we want to analyze the whole loss surface. By experiments we have found that when it comes to seven hidden nodes with orthogonal true parameters, there will be some bad local minima, i.e., there are some local minima that are not global. We believe that research in this paper can capture the characteristics of the whole loss surface and can help analyze the loss surface when there are three or even more hidden units, which may give some bounds on the performance of bad local minima and help us understand the specific non-convexity of loss surfaces.

A PRELIMINARIES:

Consider a neural network with 2 hidden nodes and ReLU as the activation function:

EQUATION

)

where σ(x) = max(0, x) is the ReLU function.

First we study the 2-D case, i.e., the input and all parameters are two dimensional. Assume that the input follows standard normal distribution.

The loss function is population loss:

EQUATION

EQUATION

then from Brutzkus and Globerson (2017) we get

EQUATION

Thus,

EQUATION

Moreover, from (26) we get

EQUATION

Assume w * 1 = w * 2 and w * T 1 w * 2 = 0. WLOG, let e 1 = w * 1 and e 2 = w * 2 . Then we know that ∀i, j ∈ [2], g(w * i , w * j ) is a constant number. Thus, define the objective function(which equals to 4l(W ) up to an additive constant)

EQUATION

)

Similarly, for w 2 , the gradient is

EQUATION

)

Assume that w 1 = (w 11 , w 12 ) and w 2 = (w 21 , w 22 ), then the gradient can be expressed in this form:

∂f ∂w 11 = w 11 + 1 π w 2 w 1 w 11 sin θ w1,w2 + 1 π (π -θ w1,w2 )w 21 (41) - 1 π w 11 w 1 sin θ w1,w * 1 - 1 π (π -θ w1,w * 1 ) (42) - 1 π w 11 w 1 sin θ w1,w * 2 (43)

and

EQUATION

)

Because of symmetry, for w 2 , the gradient is

∂f ∂w 21 = w 21 + 1 π w 1 w 2 w 21 sin θ w1,w2 + 1 π (π -θ w1,w2 )w 11 (47) - 1 π w 21 w 2 sin θ w2,w * 1 - 1 π (π -θ w2,w * 1 ) (48) - 1 π w 21 w 2 sin θ w2,w * 2 (49)

and

EQUATION

) B CRITICAL POINTS IN 2D CASES B.1 2D PRELIMINARIES

In 2D cases, we can translate W to polar coordinates and fix w 1 = w 2 = 1, so there are two variables left: θ 1 and θ 2 , i.e., w 1 = (cos θ 1 , sin θ 1 ) and w 2 = (cos θ 2 , sin θ 2 ).

For manifold gradient, we only need to consider its norm and check whether it's zero. For w 1 and w 2 , the (directed) norm of manifold gradients(expressed by m) are m(w 1 ) = sin θ

1 ∂f ∂w11 -cos θ 1 ∂f ∂w12 and m(w 2 ) = sin θ 2 ∂f ∂w21 -cos θ 2 ∂f ∂w22 .

To make life easier, it's better to simplify the m functions a bit using w 1 = (cos θ 1 , sin θ 1 ) and w 2 = (cos θ 2 , sin θ 2 ):

EQUATION

Similarly,

EQUATION

Then we can divide them into several cases and analyze them one by one to specify the positions and properties of the critical points.

WLOG, assume

θ 1 ≤ θ 2 . B.2 0 ≤ θ 1 ≤ θ 2 ≤ π 2

The norm of the manifold gradient w.r.t.

EQUATION

Similarly, the norm of m(w 2 ) is

EQUATION

)

Define

EQUATION

EQUATION

and

EQUATION

Thus,

EQUATION

)

Also note that

EQUATION

EQUATION

and the inequality becomes equality only then θ = 0 or θ = π 4 .

Proof.

EQUATION

≥ 0.

(88) Note that ( 84) is because cos(2θ) -cos θ is always non-positive when 0 ≤ θ ≤ π 4 . From (81), the inequality becomes an equality only when θ cos(2θ) = 0, which means that the only possibilities are θ = 0 or θ = π 4 . After plugging in those two possibilities in (78), we know that h(θ) = Using the above lemma, we conclude that m(w 1 ) = 0 iff θ 1 + θ 2 = π 2 and θ = 0 or π 4 , i.e., m(w

EQUATION

). In a word, there are two critical points in this case: (θ 1 , θ 2 ) = (0, π 2 ) and (θ 1 , θ 2 ) = ( π 4 , π 4 ).

B.3 π 2 ≤ θ 1 ≤ θ 2 ≤ π

The norm of the manifold gradient w.r.t.

EQUATION

Similarly,

EQUATION

)

Define

EQUATION

EQUATION

)

and the inequality becomes equality only then θ = π 2 or θ = π.

EQUATION

)

Note that the inequality becomes equality only when θ cos θ = 0 and θ π -1 2 sin θ = 0, i.e., θ = π 2 or θ = π.

If m(w 1 ) = m(w 2 ) = 0, then

EQUATION

and

EQUATION

Thus,

EQUATION

However, we know that h 2 (θ 1 ) < 0 and h 2 (θ 1 ) < 0, which makes a contradiction.

In a word, there is no critical point in this case.

B.4 π ≤ θ 1 ≤ θ 2 ≤ 3π 2

The norm of the manifold gradient w.r.t. w 1 is

EQUATION

Similarly, the norm of m(w 2 ) is

EQUATION

Define 112) and we get

EQUATION

) Let θ = θ + π, then h 3 (θ) = h 3 (θ + π) (116) = cos(θ + π) -sin(θ + π) (117) + 1 π (π -θ ) sin(θ + π) -θ + π 2 cos(θ + π) (118) = -cos θ + sin θ + 1 π (π -θ )(-sin θ ) -π + θ - π 2 (-cos θ ) (119) = -cos θ + sin θ + 1 π -π sin θ + θ sin θ + π cos θ + θ - π 2 cos θ (120) = -cos θ + sin θ -sin θ + cos θ + 1 π θ sin θ - π 2 -θ cos θ (121) = 1 π θ sin θ - π 2 -θ cos θ (122) = h 1 (θ ) -cos θ + sin θ . (123) Moreover, ∀θ ∈ [π, 3π 2 ], h 3 (θ) + h 3 ( 5π 2 -θ) = h 1 (θ -π) -cos(θ -π) + sin(θ -π) (124) + h 1 ( 5π 2 -θ -π) -cos( 5π 2 -θ -π) + sin( 5π 2 -θ -π) (125) = h 1 (θ -π) + cos θ -sin θ + h 1 ( 3π 2 -θ) + sin θ -cos θ (126) = h 1 (θ -π) + h 1 ( 3π 2 -θ) (127) = 0. (128) Also, when θ ∈ [π, 3π 2 ], h 3 (θ) = π -θ -1 π cos θ + θ -3π 2 -1 π sin θ > 0, (129) so h 3 is an increasing function when θ ∈ [π, 3π 2 ]. Thus, if m(w 1 ) = m(w 2 ) = 0, then θ 1 + θ 2 = 5π 2 . From θ 1 ≤ θ 2 we know that θ 1 ≤ 5π 4 . Plug θ 2 = 5π 2 -θ 1 in (

EQUATION

From Lemma B.1,

EQUATION

)

Note that (132) becomes equality only when θ 1 = π or θ 1 = 5π 4 , and (134) becomes equality only when θ 1 = 5π 4 . Therefore, in this case, m(w 1 ) = 0 if and only if θ 1 = 5π 4 . In a word, the only critical point in this case is (θ 1 , θ 2 ) = ( 5π 4 , 5π 4 ).

B.5 3π 2 ≤ θ 1 ≤ θ 2 ≤ 2π

Actually, this is symmetric to the B.3, so in this part I would like to specify this kind of symmetry.

We have already assumed that θ 1 ≤ θ 2 without loss of generality, and under this assumption, we can find another symmetry: From w 1 and w 2 , using line y = x as symmetry axis, we can get two new vectors w 1 and w 2 . w 1 is not necessarily the image of w 1 because we need to preserve the assumption that θ 1 ≤ θ 2 , but there exists one and only one mapping such that θ 1 ≤ θ 2 . In this kind of symmetry, the angles, including θ w1,w2 and θ wi,w * j where i, j ∈ [2], are the same, so the two symmetric cases share the same gradients, thus the symmetric critical points.

We use (i, j) ,where i, j ∈ [4], to represent the case that θ 1 is in the ith quadrant and θ 2 is in the jth one. Using this kind of symmetry, we conclude that (1, 2) is equivalent to (1, 4) and (2, 3) is equivalent to (3, 4), so there are 4 cases left which are (1, 2), (1, 3), (2, 3) and (2, 4).

EQUATION

)

Using previous definitions, we conclude that

EQUATION

and

EQUATION

If m(w 1 ) = m(w 2 ) = 0, then m ( w 1 ) + m(w 2 ) = 0, i.e.,

EQUATION

From ( 99) we know that

EQUATION

Thus, using lemma B.2,

EQUATION

)

That means the only case that h 1 (θ 1 ) + h 2 (θ 2 ) = 0 is when the inequality (143) becomes equality, which means that cos θ 1 = 1 and h 2 (θ 1 + π 2 ) = h 2 (θ 2 ) = -1 2 . Thus, we must have θ 1 = 0, and θ 2 = π 2 or θ 2 = π. Plugging them back in ( 136) and ( 138), we can verify that the first one is a critical point while the other is not. Since (θ 1 , θ 2 ) = (0, π 2 ) has been counted in case 1, there are no new critical points in this case.

B.7 0 ≤ θ 1 ≤ π 2 , π ≤ θ 2 ≤ 3π 2 Similar to previous cases, m(w 1 ) = 1 π (π -θ w1,w2 ) sin(θ 1 -θ 2 ) + cos θ 1 -sin θ 1 (144) + 1 π θ 1 sin θ 1 - π 2 -θ 1 cos θ 1 (145)

and

EQUATION

)

Thus, using previous definitions

EQUATION

and

EQUATION

EQUATION

EQUATION

)

Then we have the following lemma:

EQUATION

)

When 0 ≤ θ ≤ π 4 , since sin θ is a concave function for θ, we know that

EQUATION

Thus,

EQUATION

)

To make H(θ) = 0, we must have

EQUATION

Thus, H(θ) = -H( π 2 -θ) ≥ 0. And to make H(θ) = 0, the only possibility is θ = π 2 , which ends the proof.

Remember that if m(w 1 ) = m(w 2 ) = 0, then we have h 3 (θ 2 ) = -h 1 (θ 1 ).

If h 1 (θ 1 ) > 0, i.e., 0 ≤ θ 1 < π 4 , then from lemma B.3, H(θ 1 ) ≤ 0, which means that

EQUATION

)

Since h 3 is a strictly increasing function, we know that if h 3 (θ 2 ) = -h 1 (θ 1 ), then θ 2 ≥ θ 1 + π, so sin(θ 1 -θ 2 ) ≥ 0, and that means

EQUATION

)

The last possibility is h 1 (θ 1 ) = 0, i.e., θ 1 = π 4 . Plugging it into (150) and we know that h 3 (θ 2 ) = 0, so θ 2 = 5π 4 . And that is indeed a critical point. In a word, the only critical point in this case is (θ 1 , θ 2 ) = ( π 4 , 5π 4 ).

EQUATION

and

EQUATION

)

If m(w 1 ) = m(w 2 ) = 0, then m ( w 1 ) + m(w 2 ) = 0, i.e.,

EQUATION

)

Let θ = θ 2 -π, then from ( 99) and ( 123), we know that

EQUATION

)

Thus, from lemma B.2,

EQUATION

)

Therefore, in order to achieve h 2 (θ 1 ) + h 3 (θ 2 ) = 0, the only way is let (176) becomes equality, which means that θ 2 = 3π 2 and θ 1 = π 2 or π. Plugging them into ( 169) and ( 170) we conclude that both of them are not critical points.

In a word, there is no critical point in this case.

B.9 π 2 ≤ θ 1 ≤ π, 3π 2 ≤ θ 2 < 2π

Similar to previous cases,

EQUATION

and

EQUATION

EQUATION

)

When 1 π (π -θ w1,w2 ) sin(θ 1 -θ 2 ) = 1 2 , we must have θ w1,w2 = π 2 , so it must be true that

EQUATION

2 ). However, when

EQUATION

)

Therefore, using lemma B.2,

EQUATION

)

In a word, there is no critical point in this case.

B.10 CONCLUSION:

In conclusion, based on the assumption that θ 1 ≤ θ 2 there are four critical points in the 2D case:

EQUATION

) and ( 5π 4 , 5π 4 ).

C HESSIAN FOR 2D CASES:

There are 4 critical points: ( π 4 , π 4 ), ( π 4 , 5π 4 ), ( 5π 4 , 5π 4 ), (0, π 2 ). Obviously, the point (0, π 2 ) is a global minima. Next we want to compute the Hessian on other 3 points.

Assume the manifold is R = {(w 1 , w 2 ) : w 1 2 = w 2 2 = 1}, then the Hessian on the manifold is

EQUATION

and

EQUATION

)

Then we can get when w 1 = w 2 and w 1 = -w 2 ,

∂ 2 f ∂w 1 ∂w T 1 = I + ||w 2 || π sin θ w1,w2 w 1 I - sin θ w1,w2 w 1 3 w 1 w T 1 - cos θ w1,w2 w 1 1 1 -( w T 1 w2 w1 w2 ) 2 w 1 w T 2 w 1 w 2 - w T 1 w 2 w 1 3 w 2 w 1 w T 1 + 1 π 1 -( w T 1 w2 w1 w2 ) 2 w 2 w T 2 z 1 = 1 + sin θ w1,w2 π + 1 π 1 -w T 1 w 2 2 z T 1 w 2 2 - sin θ w1,w * 1 π - 1 π 1 -w T 1 w * 1 2 z T 1 w * 1 2 - sin θ w1,w * 2 π - 1 π 1 -w T 1 w * 2 2 z T 1 w * 2 2

Similarly,

z T 2 ∂ 2 f ∂w 2 ∂w T 2 z 2 = 1 + sin θ w1,w2 π + 1 π 1 -w T 1 w 2 2 z T 2 w 1 2 - sin θ w2,w * 1 π - 1 π 1 -w T 2 w * 1 2 z T 2 w * 1 2 - sin θ w2,w * 2 π - 1 π 1 -w T 2 w * 2 2 z T 2 w * 2 2 Next, ∂ 2 f ∂w 1 ∂w T 2 = sin θ w1,w2 π w 1 w 2 w 1 w T 2 - w 2 cos θ w1,w2 π w 1 1 1 -( w T 1 w2 w1 w2 ) 2 1 w 1 w 2 w 1 w T 1 - w T 1 w 2 w 1 w 2 3 w 1 w T 2 + 1 π 1 -( w T 1 w2 w1 w2 ) 2 1 w 1 w 2 w 2 w T 1 - w T 1 w 2 w 1 w 2 3 w 2 w T 2 + 1 π (π -θ w1,w2 )I and z T 1 ∂ 2 f ∂w 1 ∂w T 2 z 2 = 1 π 1 -w T 1 w 2 2 z T 1 w 2 w T 1 z 2 + 1 π (π -θ w1,w2 )z T 1 z 2

In conclusion,

z T ∇ 2 R f z = 1 π 1 -w T 1 w 2 2 z T 1 w 2 2 - 1 π 1 -w T 1 w * 1 2 z T 1 w * 1 2 - 1 π 1 -w T 1 w * 2 2 z T 1 w * 2 2 + 1 π 1 -w T 1 w 2 2 z T 2 w 1 2 - 1 π 1 -w T 2 w * 1 2 z T 2 w * 1 2 - 1 π 1 -w T 2 w * 2 2 z T 2 w * 2 2 + 2 π 1 -w T 1 w 2 2 z T 1 w 2 w T 1 z 2 + 2 π (π -θ w1,w2 )z T 1 z 2 - 1 π (π -θ w1,w2 )w T 1 w 2 - 1 π (π -θ w1,w * 1 )w T 1 w * 1 - 1 π (π -θ w1,w * 2 )w T 1 w * 2 - 1 π (π -θ w1,w2 )w T 2 w 1 - 1 π (π -θ w2,w * 1 )w T 2 w * 1 - 1 π (π -θ w2,w * 2 )w T 2 w * 2 .

When w 1 = w 2 or w 1 = -w 2 , we should consider the limit of the Hessian.

First, let's compute the limit of some functions that we will use later. For simplicity, we just consider the case when w 1 → w 2 . The case w 1 → -w 2 will be the same.

Claim:

lim w2→w1 z T 1 w2 2 1-w T 1 w2 2 = 0

Proof: WLOG, we assume w 1 = (1, 0), w 2 = (cos θ, sin θ), θ → 0. Otherwise, we can do a rotation which doesn't affect the inner product. Since z T 1 w 1 = 0 , z 1 = (0, 1). Then

lim w2→w1 z T 1 w 2 2 1 -w T 1 w 2 2 = lim θ→0 sin 2 θ √ 1 -cos 2 θ = lim θ→0 | sin θ| = 0

Similarly, we have the following claims.

Claim:

lim w2→w1 z T 2 w1 2 1-w T 1 w2 2 = 0 Claim: lim w2→w1 z T 1 w2w T 1 z2 1-w T 1 w2 2 = 0

Using these claims, we can computet the Hessian when w 1 = w 2 .

lim w2→w1 z T 1 ∂ 2 f ∂w 1 ∂w T 1 z 1 = 1 - sin θ w1,w * 1 π - 1 π 1 -w T 1 w * 1 2 z T 1 w * 1 2 - sin θ w1,w * 2 π - 1 π 1 -w T 1 w * 2 2 z T 1 w * 2 2 lim w2→w1 z T 2 ∂ 2 f ∂w 2 ∂w T 2 z 2 = 1 - sin θ w1,w * 1 π - 1 π 1 -w T 1 w * 1 2 z T 1 w * 1 2 - sin θ w1,w * 2 π - 1 π 1 -w T 1 w * 2 2 z T 1 w * 2 2 lim w2→w1 z T 1 ∂ 2 f ∂w 1 ∂w T 2 z 2 = z T 1 z 2

Now, we can compute the hessian on critical points. For simplicity we just consider the case that k = 1.

C.1 ( π 4 , π 4 ) On the direction z = (z 1 , z 2 ) = √ 2 2 , - √ 2 2 , √ 2 2 , - √ 2 2 , w T 1 ∂f ∂w 1 = 2 - √ 2 π - 3 √ 2 4 w T 2 ∂f ∂w 2 = 2 - √ 2 π - 3 √ 2 4 So z T ∇ 2 R f z = z T ∇ 2 f z -(w T 1 ∂f ∂w 1 ) z 1 2 -(w T 2 ∂f ∂w 2 ) z 2 2 = z T 1 ∂ 2 f ∂w 1 ∂w T 1 z 1 + z T 2 ∂ 2 f ∂w 2 ∂w T 2 z 2 + 2z T 1 ∂ 2 f ∂w 1 ∂w T 2 z 2 -4 + 2 √ 2 π + 3 √ 2 2 = 3 √ 2 2 - 2 √ 2 π > 0 On the direction z = (z 1 , z 2 ) = √ 2 2 , - √ 2 2 , - √ 2 2 , √ 2 2 , z T ∇ 2 R f z = z T ∇ 2 f z -(w T 1 ∂f ∂w 1 ) z 1 2 -(w T 2 ∂f ∂w 2 ) z 2 2 = z T 1 ∂ 2 f ∂w 1 ∂w T 1 z 1 + z T 2 ∂ 2 f ∂w 2 ∂w T 2 z 2 + 2z T 1 ∂ 2 f ∂w 1 ∂w T 2 z 2 -4 + 2 √ 2 π + 3 √ 2 2 = 1 - 2 √ 2 π + 1 - 2 √ 2 π -2 -4 + 2 √ 2 π + 3 √ 2 2 = 3 √ 2 2 - 2 √ 2 π -4 < 0

So this point is a saddle point.

C.2 ( 5π 4 , 5π 4 )

On the direction z = (z 1 , z 2 ) = √ 2 2 , - √ 2 2 , √ 2 2 , - √ 2 2 , w T 1 ∂f ∂w 1 = 2 - √ 2 π - √ 2 4 w T 2 ∂f ∂w 2 = 2 - √ 2 π - √ 2 4 z T ∇ 2 R f z = z T ∇ 2 f z -(w T 1 ∂f ∂w 1 ) z 1 2 -(w T 2 ∂f ∂w 2 ) z 2 2 = z T 1 ∂ 2 f ∂w 1 ∂w T 1 z 1 + z T 2 ∂ 2 f ∂w 2 ∂w T 2 z 2 + 2z T 1 ∂ 2 f ∂w 1 ∂w T 2 z 2 -4 + 2 √ 2 π + √ 2 2 = 1 + 1 + 2 -4 + 2 √ 2 π + √ 2 2 = 2 √ 2 π + √ 2 2 > 0 On the direction z = (z 1 , z 2 ) = √ 2 2 , - √ 2 2 , - √ 2 2 , √ 2 2 , z T ∇ 2 R f z = z T 1 ∂ 2 f ∂w 1 ∂w T 1 z 1 + z T 2 ∂ 2 f ∂w 2 ∂w T 2 z 2 + 2z T 1 ∂ 2 f ∂w 1 ∂w T 2 z 2 -4 + 2 √ 2 π + √ 2 2 = 1 - 2 √ 2 π + 1 - 2 √ 2 π -2 -4 + 2 √ 2 π + √ 2 2 = √ 2 2 - 2 √ 2 π -4 < 0

So this point is a saddle point.

C.3 ( π 4 , 5π 4 )

On the direction z = (z 1 , z 2 ) = √ 2 2 , - √ 2 2 , √ 2 2 , - √ 2 2 , w T 1 ∂f ∂w 1 = 1 - √ 2 π - 3 √ 2 4 w T 2 ∂f ∂w 2 = 1 - √ 2 π - √ 2 4 z T ∇ 2 R f z = z T ∇ 2 f z -(w T 1 ∂f ∂w 1 ) z 1 2 -(w T 2 ∂f ∂w 2 ) z 2 2 = z T 1 ∂ 2 f ∂w 1 ∂w T 1 z 1 + z T 2 ∂ 2 f ∂w 2 ∂w T 2 z 2 + 2z T 1 ∂ 2 f ∂w 1 ∂w T 2 z 2 -2 + 2 √ 2 π + √ 2 = 1 + 1 + 2 -2 + 2 √ 2 π + √ 2 = 2 + 2 √ 2 π + √ 2 > 0 On the direction z = (z 1 , z 2 ) = √ 2 2 , - √ 2 2 , - √ 2 2 , √ 2 2 , z T ∇ 2 R f z = z T 1 ∂ 2 f ∂w 1 ∂w T 1 z 1 + z T 2 ∂ 2 f ∂w 2 ∂w T 2 z 2 + 2z T 1 ∂ 2 f ∂w 1 ∂w T 2 z 2 -2 + 2 √ 2 π + √ 2 = 1 - 2 √ 2 π + 1 - 2 √ 2 π -2 -2 + 2 √ 2 π + √ 2 = √ 2 - 2 √ 2 π -2 < 0

So this point is a saddle point.

C.4 CONCLUSION:

In conclusion, we have four critical points: one is global maximal, the other three are saddle points. Proof. If (w 1 , w 2 ) is a critical point, then

D 3D CASES:

EQUATION

where matrix (I -w 1 w T 1 ) projects a vector onto the tangent space of w 1 . Since

EQUATION

we get

EQUATION

which means that (π -θ w1,w2 )w 2 -(π -θ w1,w * 1 )w * 1 -(π -θ w1,w * 2 )w * 2 lies in the direction of w 1 . If θ w1,w2 = π, i.e., w 1 = -w 2 , then of course the four vectors have rank at most 3, so we can find the proper basis. If θ w1,w2 < π, then we know that there exists a real number r such that

EQUATION

)

Since θ w1,w2 < π, we know that the four vectors w 1 , w 2 , w * 1 and w * 2 are linear dependent. Thus, they have rank at most 3 and we can find the proper basis.

D.2 SOME PROPERTIES OF CRITICAL POINTS:

Next we will focus on the properties of critical points. Assume (w 1 , w 2 ) is one of the critical points, from lemma D.1 we can find a set of standard orthogonal basis (e 1 , e 2 , e 3 ) such that e 1 = w * 1 , e 2 = w * 2 and w 1 , w 2 lies in span{e 1 , e 2 , e 3 }. Furthermore, assume w 1 = w 11 e 1 + w 12 e 2 + w 13 e 3 and w 2 = w 21 e 1 + w 22 e 2 + w 23 e 3 , i.e., w 1 = (w 11 , w 12 , w 13 ) and w 2 = (w 21 , w 22 , w 23 ). Since we have already found out all the critical points when w 13 = w 23 = 0, in the following we assume w 2 13 + w 2 23 = 0. Lemma D.2. θ w1,w2 < π.

Proof. If θ w1,w2 = π, then w 1 = -w 2 , so w 2 is in the direction of w 1 . We have already known from ( 196) that (π -θ w1,w2 )w 2 -(π -θ w1,w * 1 )w * 1 -(π -θ w1,w * 2 )w * 2 lies in the direction of w 1 , so further we know (π -θ w1,w * 1 )w * 1 + (π -θ w1,w * 2 )w * 2 lies in the direction of w 1 . However, (π -θ w1,w * 1 )w * 1 -(π -θ w1,w * 2 )w * 2 lies in span{e 1 , e 2 }, so w 1 ∈ span{e 1 , e 2 } and w 2 ∈ span{e 1 , e 2 }. Thus, w 13 = w 23 = 0 and that contradicts with the assumption.

In a word, θ w1,w2 < π.

Lemma D.3. w 13 * w 23 = 0.

Proof. We have already known from ( 196) that (π -θ w1,w2 )w 2 -(π -θ w1,w * 1 )w * 1 -(π -θ w1,w * 2 )w * 2 lies in the direction of w 1 . Writing it in each dimension and we know that there exists a real number r 0 such that

EQUATION

From lemma D.2 we know that θ w1,w2 < π, so we can define

EQUATION

Then the equations become

EQUATION

EQUATION

Similarly, we have

EQUATION

Since w 2 13 + w 2 23 = 0, at least one of those two variables cannot be 0. WLOG, we assume that w 13 = 0. If w 23 = 0, then from (207) we know that w 13 = 0, which contradicts the assumption. Thus, w 23 = 0, which means that w 13 * w 23 = 0. Lemma D.4. w 13 * w 23 < 0.

Proof. Adapting from the proof of lemma D.3, we know that

EQUATION

and

EQUATION

Furthermore, kk = w23 w13 • w13 w23 = 1, so k = 1 k .

From lemma D.2 we know that θ w1,w2 < π, and from lemma D.3 we know that both w 1 and w 2 are outside span{w * 1 , w * 2 }, so ∀i, j ∈ [2], θ wi,w * j < π. Thus, ∀i, j ∈ [2],

π-θ w i ,w * j π-θw 1 ,w 2 > 0. Therefore, we have

EQUATION

That means k < 0, so w23 w13 > 0. In a word, w 13 * w 23 < 0. 

Proof. Adapting from the proof of lemma D.4 and we know that

EQUATION

Similarly, we have

EQUATION

Taking the first component of ( 217) and ( 218) gives us 

EQUATION

EQUATION

For simplicity, based on D.5, we define k

EQUATION

WLOG, assume k 0 ≥ 1, otherwise we can switch w 1 and w 2 .

Thus,

EQUATION

Similarly, if we apply the change of variables onto the second component of ( 217), we will get

EQUATION

Thus,

EQUATION

Lemma D.9. ∃θ 0 ∈ [ π 2k0 , 3π 4k0 ), s.t.,

EQUATION

) Proof. Note that when θ ∈ [0, π k0 ], -k 0 θ is always non-positive. Define G(θ) = k 0 cos(k 0 θ) + cos(θ), then G(θ) is a strict decreasing function w.r.t. θ. Note that G(0) = k 0 + 1 > 0 and G π k0

= cos π k0 -k 0 < 0, so there must be an θ 0 ∈ (0, π k0 ) such that G(θ 0 ) = 0. Thus, when 0 ≤ θ < θ 0 , G(θ) > 0, and when θ 0 ≤ π k0 , G(θ) < 0. Thus,

EQUATION

Then the only thing we need to prove is 

EQUATION

Therefore, π 2k0 ≤ θ 0 < 3π 4k0 , which completes the proof. Lemma D.10. F (θ) is either strictly decreasing or first decrease and then increase when θ ∈ (θ 0 , π k0 ].

Proof.

EQUATION

)

Define H(θ) = k 0 cos(k 0 θ)+cos θ+k 2 0 θ sin(k 0 θ)+θ sin θ(θ ∈ (θ 0 , π k0 ]), then H(θ)•F (θ) < 0(i.e., when H(θ) is positive, F (θ) is decreasing, otherwise F (θ) is increasing), and we know that

EQUATION

Note that (251) holds because θ > θ 0 ≥ π 2k0 . Thus, H(θ) is a strictly decreasing function when θ ∈ (θ 0 , π k0 ]. We can see that

EQUATION

Thus, if H( π k0 ) ≥ 0, then F (θ) is monotonically decreasing when θ ∈ (θ 0 , π k0 ]. Otherwise, F (θ) first decrease and then increase when θ ∈ (θ 0 , π k0 ].

Lemma D.11. ∀θ ∈ ( 3π 4k0 , π k0 ], F (θ) < F 3π 4k0 .

Proof. From lemma D.10 we have already known that F (θ) is either strictly decreasing or first decrease and then increase when θ ∈ (θ 0 , π k0 ], so the maximum of the function value on an interval can only be at the endpoints of that interval, which means that we only need to prove F ( 3π 4k0 ) > F ( π k0 ). Note that 

EQUATION

EQUATION

which means that F ( 3π 4k0 ) > F ( π k0 ).

Thus, ∀θ ∈ ( 3π 4k0 , π k0 ], F (θ) < F 3π 4k0 .

Lemma D.12. θ 1 = θ 2 .

Proof. From the proof of lemma D.8 we get F (θ 1 ) = π -θ w1,w2 = F (θ 2 ).

Thus, F (θ 1 ), F (θ 2 ) ∈ [0, π].

Using lemma D.9, θ 1 , θ 2 > θ 0 ≥ π 2k0 , so that k 0 θ 1 , k 0 θ 2 ∈ ( π 2 , π].

From (232), we know that k 0 (θ 1 + θ 2 ) ≤ 3π 2 , which means that at least one of θ 1 and θ 2 are less than or equal to 3π 4k0 , w.l.o.g. we assume θ 1 ≤ 3π 4k0 . Note that lemma D.11 tells us that F ( 3π 4k0 ) > F ( π k0 ), so at the point θ = 3π 4k0 , the function cannot be increasing, which combining with lemma D.10 shows that F (θ) is strictly decreasing when θ ∈ (θ 0 , 3π 4k0 ].

If θ 2 > 3π 4k0 , then we know that F (θ 1 ) ≥ F 3π 4k0 > F (θ 2 ), which contradicts F (θ 1 ) = F (θ 2 ).

Thus, θ 1 , θ 2 (θ 0 , 3π 4k0 ]. Since F (θ) is monotonically decreasing when θ ∈ (θ 0 , 3π 4k0 ], we can conclude that θ 1 = θ 2 . 

D.3 NEGATIVE CURVATURE:

Lemma D.14. For every critical point (w 1 , w 2 ) outside span{w * 1 , w * 2 }, there is negative curvature.

Proof. We select z 1 = (-

EQUATION

2 , 0) and z 2 = (

EQUATION

From lemma D.7 we know that 1 ≤ k 0 ≤ 3.

EQUATION

If 2 < k 0 ≤ 3, from (232) and lemma D.12 we get 2 cos 2 (k 0 θ 1 ) ≤ 1, so k 0 θ 1 ≤ 3π 4 , which means that

EQUATION

Thus,

EQUATION

Besides, from (233) and lemma D.12 we know that 2 cos 2 θ 1 ≤ 1, so θ 1 ≥ π 4 , which means that

EQUATION

)

Using ( 289) and ( 291), w 11 = w 12 = -cos(k 0 θ 1 ) > 0 (292) w 21 = w 22 = -cos θ 1 < 0.

(293) From lemma D.4, we conclude that w 1 , w 2 = w 11 • w 21 + w 12 • w 22 + w 13 • w 23 < 0, (294) which means that θ w1,w2 > π 2 .

(295) Thus,

EQUATION

)

In a word, for every critical point (w 1 , w 2 ) outside span{w * 1 , w * 2 }, there is negative curvature.

:



Figures and Tables:

Figure 1: Spurious Local Minima for K ≥ 2 ReLU Network.

) holds when θ = 0 or θ = π 4 .

∀i, j ∈ [2], π -θ wi,w * j = arccos(-θ wij ), we know that arccos(

means k 0 = 3 and k 0 = 1, which makes a contradiction. Thus,

(x) is decreasing in [ π 3 , 4π7 ] and increasing in [ 4π 7 , π]. However, we know that h( π 3 so h(x) is negative when x ∈ [ π 3 , π]. Therefore,

we compute the Hessian matrix:If z = (tz 1 , z 2 ), ||z 1 || = ||z 2 || = 1 and w T 1 z 1 = w T 2 z 2 = 0, 13. For every critical point (w 1 , w 2 ) outside span{w * 1 , w * 2 }, 1 π (π -θ w1,w2 )w T 1 w 2 -In lemma D.3, we have three equations, and we write them again for convenience:(π -θ w1,w2 )w 21 -(π -θ w1,w * 1 ) = r 0 • w 11 (274) (π -θ w1,w2 )w 22 -(π -θ w1,w * 2 ) = r 0 • w 12 (275) (π -θ w1,w2 )w 23 = r 0 • w 13 . (276) Multiply 274 by w 11 , 275 by w 12 , 276 by w 13 , we get (π -θ w1,w2 )w 21 w 11 -(π -θ w1,w * 1 )w 11 = r 0 • w 2 11 (277) (π -θ w1,w2 )w 22 w 12 -(π -θ w1,w * 2 )w 12 = r 0 • w 2 12 (278)(π -θ w1,w2 )w 23 w 13 = r 0 • w 2 13 . θ w1,w2 ).

D.1 WHY WE ONLY NEED 3 DIMENSION Lemma D.1. If (w 1 , w 2 ) is a critical point, then there exists a set of standard orthogonal basis (e 1 , e 2 , e 3 ) such that e 1 = w * 1 , e 2 = w * 2 and w 1 , w 2 lies in span{e 1 , e 2 , e 3 }.

Table content: <table/>

Peer review (iclr2018):
 Summary: The paper considers the problem of a single hidden layer neural network, with 2 RELU units (this is what I got from the paper - as I describe below, it was not clear at all the setting of the problem - if I*m mistaken, I will also wait for the rest of the reviews to have a more complete picture of the problem). Given this architecture, the authors focus on characterizing the objective landscape of such a problem. The techniques used depend on previous work. According to the authors, this paper extends(?) previous results on a NN with a single layer with a single unit. Originality: The paper heavily depends on the approach followed by Brutzkus and Globerson, 2017. To this end, slighly novel. Importance: Understanding the landscape (local vs global minima vs saddle points) is an important direction in order to further understand when and why deep neural networks work. I would say that the topic is an important one. Presentation/Clarity: To the best of my understanding, the paper has some misconceptions. The title is not clear whether the paper considers a two layer RELU network or a single layer with with two RELU units. In the abstract the authors state that it has to do with a two-layer RELU network with two hidden units (per layer? in total?). Later on, in Section 3, the expression at the bottom of page 2 seems to consider a single-layer RELU network, with two units. These are crucial for understanding the contribution of the paper; while reading the paper, I assumed that the authors consider the case of a single hidden unit with K = 2 RELU activations (however, that complicated my understanding on how it compares with state of the art). Another issue is the fact that, on my humble opinion, the main text looks like a long proof. It would be great to have more intuitions. Comments: 1. The paper mainly focuses on a specific problem instance, where the weight vectors are unit-normed and orthogonal to each other. While the authors already identify that this might be a restriction, it still does not lessen the fact that the configuration considered is a really specific one. 2. The paper reads like a collection of lemmas, with no verbose connection. It was hard to read and understand their value, just because mostly the text was structured as one lemma after the other. 3. It is not clear from the text whether the setting is already considered in Brutzkus and Globerson, 2017. Please clarify how your work is different/new from previous works.