Title: SYMMETRY-BREAKING CONVERGENCE ANALYSIS OF CERTAIN TWO-LAYERED NEURAL NETWORKS WITH RELU NONLINEARITY

Abstract: In this paper, we use dynamical system to analyze the nonlinear weight dynamics of two-layered bias-free networks in the form of g(x; w) = K j=1 σ(w j x), where σ(•) is ReLU nonlinearity. We assume that the input x follow Gaussian distribution. The network is trained using gradient descent to mimic the output of a teacher network of the same size with fixed parameters w * using l 2 loss. We first show that when K = 1, the nonlinear dynamics can be written in close form, and converges to w * with at least (1 -)/2 probability, if random weight initializations of proper standard derivation (∼ 1/ √ d) is used, verifying empirical practice [Glorot & Bengio (2010); He et al. (2015); LeCun et al. ( 2012)]. For networks with many ReLU nodes (K ≥ 2), we apply our close form dynamics and prove that when the teacher parameters {w * j } K j=1 forms orthonormal bases, (1) a symmetric weight initialization yields a convergence to a saddle point and (2) a certain symmetry-breaking weight initialization yields global convergence to w * without local minima. To our knowledge, this is the first proof that shows global convergence in nonlinear neural network without unrealistic assumptions on the independence of ReLU activations. In addition, we also give a concise gradient update formulation for a multilayer ReLU network when it follows a teacher of the same size with l 2 loss. Simulations verify our theoretical analysis.

1. INTRODUCTION:

Deep learning has made substantial progress in many applications, including Computer Vision [He et al. (2016) ; Simonyan & Zisserman (2015) ; Szegedy et al. (2015) ; Krizhevsky et al. (2012) ], Natural Language Processing [Sutskever et al. (2014) ] and Speech Recognition [Hinton et al. (2012) ]. However, till now, how and why it works remains elusive due to a lack of theoretical understanding. First, how simple approaches like gradient descent can solve a very complicated non-convex optimization effectively. Second, how the deep models, especially deep convolutional models, achieve generalization power despite massive parameters.

In this paper, we focus on the first problem and use dynamical system to analyze the nonlinear gradient descent dynamics of certain two-layered nonlinear network in the following form:

EQUATION

where σ(x) = max(x, 0) is the ReLU nonlinearity. We consider the following setting: a student network learns the parameters that minimize the l 2 distance between its prediction and the supervision provided by the teacher network of the same size with a fixed set of parameters w * . We assume all inputs x to follow Gaussian distribution and thus the network is bias-free. Eqn. 1 is highly nonconvex and could contain exponential number of symmetrically equivalent solutions.

To analyze this, we first derive novel and concise gradient update rules for multilayer ReLU networks (See Lemma 2.1) in the teacher-student setting under l 2 loss. Then for K = 1, we prove that the nonlinear gradient dynamics of Eqn. 1 has a close form and converges to w * with at least (1 - )/2 probability, if initialized randomly with standard derivation on the order of 1/ √ d, verifying commonly used initialization techniques [Glorot & Bengio (2010) ; He et al. (2015) ; LeCun et al. (2012) ],. When K ≥ 2, we prove that when the teacher parameters {w j } K j=1 form orthonormal bases, (1) a symmetric initialization of a student network gets stuck at a saddle point and (2) under a certain symmetric breaking weight initialization, the dynamics converges to w * , without getting stuck into any local minima. Note that in both cases, the initialization can be arbitrarily close to the origin for a fixed w * , showing that such a convergence behavior is beyond the local convex structure at w * . To our knowledge, this is the first proof of its kind.

Previous works also use dynamical system to analyze deep neural networks. [Saxe et al. (2013) ] analyzes the dynamics of multilayer linear network, and [Kawaguchi (2016) ] shows every local minima is global for multilinear network. Very little theoretical work has been done to analyze the dynamics of nonlinear networks, especially deep ones. [Mei et al. (2016) ] shows the global convergence when K = 1 with activation function σ(x) when its derivatives σ , σ , σ are bounded and σ > 0. Similar to our approach, [Saad & Solla (1996) ] also uses the student-teacher setting and analyzes the dynamics of student network when the teacher's parameters w * forms a orthonomal bases; however, it uses σ(x) = erf(x) as the nonlinearity and only analyzes the local behaviors of the two critical points (the saddle point in symmetric initializations, and w * ). In contrast, we prove the global convergence behavior in certain symmetry-breaking cases.

Many previous works analyze nonlinear network based on the assumption of independent activations: the activations of ReLU (or other nonlinear) nodes are independent of the input and/or mutually independent. For example, [Choromanska et al. (2015a; b) ] relate the nonlinear ReLU network with spin-glass models when several assumptions hold, including the assumption of independent activations (A1p and A5u). [Kawaguchi (2016) ] proves that every local minimum in nonlinear network is global based on similar assumptions. [Soudry & Carmon (2016) ] shows the global optimality of the local minimum in a two-layered ReLU network, by assuming small sample size and applying independent multiplicative Bernoulli noise on the activations. In practice, the activations are highly dependent due to their common input. Ignoring such dependency also misses important behaviors, and may lead to misleading conclusions. In this paper, no assumption of independent activation is made. For sigmoid activation, [Fukumizu & Amari (2000) ] gives quite complicated conditions for a local minimum to be global when adding a new node to a two-layered network. [Janzamin et al. (2015) ] gives guarantees on recovering the parameters of a 2-layered neural network learnt with tensor decomposition. In comparison, we analyze ReLU networks trained with gradient descent, which is a more popular setting in practice.

The paper is organized as follows. Sec. 2 introduces the basic formulation and some interesting novel properties of ReLU in multilayered ReLU networks. Sec. 3 and Sec. 4 then analyze the twolayered model Eqn. 1 for K = 1 and K ≥ 2, respectively. Sec. 5 shows that simulation results are consistent with theoretical analysis. Finally Sec. 7 gives detailed proofs for all theorems.

2. PRELIMINARY:

2.1 NOTATION Denote X as a N -by-d input data matrix and w * is the parameter of the teacher network with desired N -by-1 output u = g(X; w * ). Now suppose we have an estimator w and the estimated output v = g(X; w). We want to know with l 2 loss E(w) = 1 2 uv 2 = 1 2 u -g(X; w) 2 , whether gradient descent will converge to the desired solution w * .

The gradient descent update is w (t+1) = w (t) + η∆w (t) , where ∆w (t) ≡ -∇E(w (t) ). If we let η → 0, then the update rule becomes a first-order differential equation dw/dt = -∇E(w), or more concisely, ẇ = -∇E(w). In this case, Ė = ∇E(w) ẇ = -∇E(w) 2 ≤ 0, i.e., the function value E is nonincreasing over time. The key is to check whether there exist other critical points w = w * so that ∇E(w) = 0.

In our analysis, we assume entries of input X follow Gaussian distribution. In this situation, the gradient is a random variable and ∆w = -E [∇E(w)]. The expected E [E(w)] is also nonincreasing no matter whether we follow the expected gradient or the gradient itself, because

E Ė = -E [∇E(w) ∇E(w)] ≤ -E [∇E(w)] E [∇E(w)] ≤ 0 (2)

Therefore, we analyze the behavior of expected gradient E [∇E(w)] rather than ∇E(w).

2.2. PROPERTIES OF RELU:

In this paper, we discover a few useful properties of ReLU that make our analysis much simpler. Denote D = D(w) = diag(Xw > 0) as a N -by-N diagonal matrix. The l-th diagnonal element of D is a binary variable showing whether the neuron is on for sample l. Using this notation, we could write σ(Xw) = DXw. Note that D only depends on the direction of w but not its magnitude.

Note that for ReLU, D is also "tranparent" on derivatives. For example, the Jacobian J w [σ(Xw)] = σ (Xw)X = DX at differentiable regions. This gives a very concise rule for gradient descent in ReLU network: suppose we have negative gradient inflow vector g (of dimension N -by-1) on the current ReLU node with weights w, then we can simply write the update ∆w as:

EQUATION

This can be easily applied to multilayer ReLU network. Denote j ∈ [c] if node j is in layer c, d c as the width of layer c, and u j and v j as the output of teacher network and student network, respectively. A simple deduction yields the following lemma:

Lemma 2.1 For neural network with ReLU nonlinearity and using l 2 loss to match with a teacher network of the same size, the negative gradient inflow g j for node j at layer c has the following form:

EQUATION

where L j and L * j are N -by-N diagonal matrices. For any k ∈ [c + 1], L k = j∈[c] w jk D j L j and similarly for L * k . For the first layer, L = L * = I.

The intuition here is to start from g = uv (true for l 2 loss) at the top layer and use induction.

With this formulation, we could write the finite dynamics for w c (all parameters in layer c). Denote the N -by-

d c+1 d c matrix R c = [L j D j ] j∈[c] X c and R * c = [L * j D * j ] j∈[c] X * c .

Using gradient descent rules:

EQUATION

Therefore we have:

∆w c = R c (R * c w * c -R c w c ) (7)

3. SINGLE RELU CASE:

Let's start with the simplest case where there is only one ReLU node, K = 1. At iteration t, following Eqn. 3, the gradient update rule is:

EQUATION

Note here how the notation of D (t) comes into play (and D (t) D (t) = D (t) ). Indeed, when the neuron is cut off at sample l, then (D (t) ) ll is zero and will block the corresponding gradient component.

Linear case. In this situation D (t) = D * = I (no gating in either forward or backward propagation) and:

w (t+1) = w (t) + η N X X(w * -w (t) ) (9)

where η/N is the learning rate. When it is sufficiently small so that the spectral radius ρ(Iη N X X) < 1, w (t+1) will converge to w * when t → +∞. Note that this convergence is guaranteed for any initial condition w (1) , if X X is full rank with suitable η. This is consistent with its convex nature. If entries of X follow i.i.d Gaussian distribution, then E 1 N X X = I and the condition satisfies.

Nonlinear (ReLU) case. In this case, ∆w = X D(D * Xw * -DXw) in which D is a function of w. Intuitively, this term goes to zero when w → w * , and should be approximated to be N 2 (w *w) in the i.i.d Gaussian case, since roughly half of the samples are blocked. However, once we make such approximation, we lost the nonlinear behavior of the network and would draw the wrong conclusion of global convergence.

Then how should we analyze it? Notice that in ∆w, both of the two terms have the form

F (e, w) = X D(e)D(w)Xw. Using this form, E [∆w] = E [F (w/ w , w * )] -E [F (w/ w , w)].

Here e is a unit vector called the "projected" weight. In the following, we will show that E [F (e, w)] has the following close form under i.i.d Gaussian assumption on X:

Lemma 3.1 Denote F (e, w) = X D(e)D(w)Xw where e is a unit vector, X = [x 1 , x 2 , • • • , x N ] is N -by-d sample matrix and D(w) = diag(Xw > 0) is a binary diagonal matrix. If x i ∼ N (0, I)

and are i.i.d (and thus bias-free), then:

EQUATION

where θ = ∠(e, w) ∈ [0, π] is the angle between e and w.

Note that the expectation analysis smooths out the non-differentiable property of ReLU, leaving only one singularity at e = 0. The intuition is that expectation analysis involves an integration over the data distribution. With simple algebraic manipulation, E [∆w] takes the following closed form:

EQUATION

where α = w * / w and θ ∈ [0, π] is the angle between w and w * . The first term is expected while the last two terms show the nonlinear behavior. Using Lyapunov's method, we show that the dynamics (if treated continuously) converges to w * when w (1) ∈ Ω = {w : ww * < w * }:

Lemma 3.2 When w (1) ∈ Ω = {w : ww * < w * }, following the dynamics of Eqn. 11, the Lyapunov function V (w) = 1 2 ww * 2 has V < 0 and the system is asymptotically stable and thus w (t) → w * when t → +∞.

See Appendix for the proof. The intuition is to represent V as a 2-by-2 bilinear form of vector [ w , w * ], and the bilinear coefficient matrix is positive definite. One question arises: will the same approach show the dynamics converges when the initial conditions lie outside the region Ω, in particular for any region that includes the origin? The answer is probably no. Note that w = 0 is a singularity in which ∆w is not continuous (if approaching from different directions towards w = 0, ∆w is different). It is due to the fact that ReLU function is not differentiable at the origin. We could remove this singularity by "smoothing out" ReLU around the origin. This will yield ∆w → 0 when w → 0. In this case, V (0) = 0 so Lyapunov method could only tell that the dynamics is stable but not convergent. Note that for ReLU activation, σ (x) = 0 for certain negative x even after a local smoothing, so the global convergence claim in [Mei et al. (2016) ] for l 2 loss does not apply.

Random Initialization. Then we study how to sample w (1) so that w (1) ∈ Ω. We would like to sample within Ω, but we don't know where is w * . Sampling around origin with big radius r ≥ 2 w * is inefficient in particular in high-dimensional space. This is because when the sample is uniform, the probability of hitting the ball is proportional to (r/ w * ) d ≤ 2 -d , which is exponentially small. A better idea is to sample around the origin with very small radius (but not at w = 0), so that the convergent hypersphere behaves like a hyperplane near the origin, and thus almost half of the samples is useful (Fig. 2 The intution here is to lower-bound the probability of the shaded area (Fig. 2(b) ). From the proof, the conclusion could be made stronger to show r ∼ 1/ √ d, consistent with common initialization techniques [Glorot & Bengio (2010) ; He et al. (2015) ; LeCun et al. (2012) ]. Fig. 2 (c) shows an example in the 2D case, in which there is a singularity at the origin, and sampling towards w * yields the convergence. This is consistent with the analysis above.

4. MULTIPLE RELUS CASE:

Now we are ready to analyze the network g(x) = K j=1 σ(w j x) for K ≥ 2 (Fig. 1(c) ). Theoretical analysis of such networks is also the main topic in many previous works [Saad & Solla (1996) ; Soudry & Carmon (2016) ; Fukumizu & Amari (2000) ]. In this case, L j = L * j = I for 1 ≤ j ≤ K. Then we have the following nonlinear dynamics from Eqn. 7:

EQUATION

where f = F (w j / w j , w * j ) -F (w j / w j , w j ). Therefore, using Eqn. 10, its expectation is:

2π N E f (w j , w j , w * j ) = (π -θ * j j )w * j -(π -θ j j )w j + w * j w j sin θ * j j - w j w j sin θ j j w j

(13) where θ * j j ≡ ∠(w j , w * j ) and θ j j ≡ ∠(w j , w j ). Eqn. 12 (and its expected version) gives very complicated nonlinear dynamics and could be hard to solve in general. Unlike K = 1, a similar approach with Lyaponov function does not yield a decisive conclusion. However, if we consider the symmetric case: w j = P j w and w * j = P j w * where P j is a cyclic permutation matrix that maps index j + 1 to (j + j mod K) + 1 (and P 1 is the identity matrix), then RHS of the expected version of Eqn. 12 can be simplified as follows:

E [∆w j ] = j E f (w j , w j , w * j ) = j E [f (P j w, P j w, P j w * )]

= j E [f (P j w, P j P j w, P j P j w * )] ({P j } K j=1 is a group)

EQUATION

which means that if all w j and w * j are symmetric under the action of cyclic group, so does their expected gradient. Therefore, the trajectory {w (t) } keeps such cyclic structure. Instead of solving a system of K equations, we only need to solve one:

EQUATION

Surprisingly, there is another layer of symmetry in Eqn. 15 when {w * j } forms an orthonomal basis (w * j w * j = δ jj ). In this case, if we start with w (1) = xw * + y j =1 P j w * then we could show that the trajectory keeps this structure and Eqn. 15 can be further reduced into the following 2D nonlinear dynamics:

EQUATION

Here the symmetrical factor (α ≡ w * j / w j , θ ≡ θ * j j , φ ≡ θ j j , φ * ≡ θ * j j ) are defined as follows:

α = (x 2 + (K -1)y 2 ) -1/2 , cos θ = αx, cos φ * = αy, cos φ = α 2 (2xy + (K -2)y 2 ) (17)

For this 2D dynamics, we thus have the following theorem: Theorem 4.1 For any K ≥ 2, the 2D dynamics (Eqn. 16) shows the following behaviors:

(1) Symmetric case. If the initial condition x (1) = y (1) ∈ (0, 1], then the dynamics reduces to 1D and converges to a saddle point

x = y = 1 πK ( √ K -1 -arccos(1/ √ K) + π).

(2) Symmetry-Breaking. If (x (1) , y (1) ) ∈ Ω = {x ∈ (0, 1], y ∈ [0, 1], x > y}, then dynamics always converges to (x, y) = (1, 0).

From (x (t) , y (t) ) we could recover w (t) j = x (t) w * j + y (t) j =j w * j . Obviously, a convergence of Eqn. 16 to (1, 0) means Eqn. 12 converges to {w * j }, i.e, the teacher parameters are recovered:

Corollary 4.2 For a bias-free two-layered ReLU network g(x; w) = j σ(w j x) that takes Gaussian i.i.d inputs (Fig. 1 ), if the teacher's parameters {w * j } form orthogonal bases, then when the student parameters is initialized in the form of w

(1) j = x (1) w * j + y (1) j =j w * j where (x (1) , y (1) ) ∈ Ω = {x ∈ (0, 1], y ∈ [0, 1], x > y}, then the dynamics (Eqn. 12) converges to {w * j } without being trapped into local minima.

When symmetry is broken, since the closure of Ω includes the origin, there exists a path starting at arbitrarily small neighborhood of origin to w * , regardless of how large w * is. In contrast to traditional convex analysis that only gives the local parameter-dependent convergence basin around w * j , here we obtain a convergence basin that is parameter-independent. In comparison, [Saad & Solla (1996) ] uses a different activation function (σ(x) = erf(x)) and only analyzes local behaviors near the two fixed points (the symmetric saddle point and the teacher's weights w * ), leaving symmetry breaking an empirical procedure. Here we show that it is possible to give global convergence analysis on certain symmetry breaking cases for two-layered ReLU network.

By symmetry, Corollary 4.1 immediately suggests that when w (1) = y (1) K j=1 w * j + (x (1)y (1) )w * j , then the dynamics will converge to P j w * . Since x > y but can be arbitrarily close, a slighest preturbation on the symmetric solution x = y leads to a different fixed point, which is a permutation of w * . This is very similar to Spontaneously Symmetric-Breaking (SSB) procedure in physics, in which a high energy state with full symmetry goes to a low energy state and only retains part of the symmetry. In this case, the energy is the objective function E, the high energy state is the initialization that is almost symmetrical but with small fluctuation, and the low energy state is the fixed point the dynamics converges into. From the simulation shown in Fig. 4 , we could see that gradient descent takes a detour to reach the desired solution w * , even when the initialization is aligned with w * . This is because in the first stage, all ReLU nodes receive the residue and try to explain the data in the same way (both x and y increases); when the "obvious" component has been explained away, then the residue changes its direction and pushes some ReLU nodes to explain other components as well (x increases but y decreases).

Empirically this path also converges to w * under noise. We leave it a conjecture that the system converges in the presence of reasonably large noise. If this conjecture is true, then with high probability a random initialization stays in the convergence basin and converges to a permutation of w * . The reason is that a random initialization almost never gives ties. Without a tie, there exists one leading component which will dominate the convergence. Conjecture 4.3 When the initialization w (1) = x (1) w * j + y (1) j =j w * j + , where is Gaussian noise and (x (1) , y (1) ) ∈ Ω, then the dynamics Eqn. 12 also converges to w * without trapped into local minima.

5. SIMULATION:



5.1. CLOSE FORM SOLUTION FOR ONE RELU NODE:

We verify our close form expression of E [F (e, w)] = E [X D(e)D(w)Xw] (Eqn. 10) with simulation. We randomly pick e and w so that their angle ∠(e, w) is uniformly distributed in [0, π]. We prepare the input data X with standard Gaussian distribution and compare the close form solution E [F (e, w)] with F (e, w), the actual data term in gradient descent without expectation. We use relative RMS error: err = E [F (e, w)] -F (e, w) / F (e, w) . As shown in Fig. 3(a) , The error distribution on angles shows the properties of the close-form solution. For small θ, D(w) and Here the top weights a j is fixed at different numbers (rather than 1). Large positive a j correponds to fast convergence. When a j has positive/negative components, the network does not converge to w * . D(e) overlaps sufficiently, giving a reliable estimation for the gradient. When θ → π, D(w) and D(e) tend not to overlap, leaving very few data involved in the gradient computation. As a result, the variance grows. Note that all our analysis operate on θ ∈ [0, π/2] and is not affected by this behavior. In the following, angles are sampled from [0, π/2].

Fig. 3 (a) shows that the close form expression becomes more accurate with more samples. We also examine other zero-mean distributions of X, e.g., uniform distribution in [-1/2, 1/2]. As shown in Fig. 3(d) , the close form expression still works for large d, showing that it could be quite general. Note that the error is computed up to a scaling constant, due to the difference in normalization constants among different distributions. We leave it to the future work to prove its usability for broader distributions.

5.2. CONVERGENCE FOR MULTIPLE RELU NODES:

Fig. 4 (a) and (b) shows the 2D vector field given by the 2D dynamics (Eqn. 16) and Fig. 4(c) shows the 2D trajectory towards convergence to the teacher's parameters w * . Interestingly, even when we initialize the weights as (10 -3 , 0), aligning with w * , the gradient descent takes detours to reach the destination. One explanation is, at the beginning all nodes move similar direction trying to explain the data, once the data have been explained partly, specialization follows (y decreases). Fig. 5 shows empirical convergence for K ≥ 2, when the initialization deviates from symmetric initialization in Thm. 4.1. Unless the deviation is large, gradient descent converges to w * . We also check the convergence of a more general network g 2 (x) = K j=1 a j σ(w j x). When a j > 0 convergence follows; however, when some a j is negative, the network does not converge to w * , even that the student network already knows the ground truth value of {a j } K j=1 .

6. CONCLUSION AND FUTURE WORK:

In this paper, we analyze the nonlinear dynamical behavior of certain two-layered bias-free ReLU networks in the form of g(x; w) = K j=1 σ(w j x), where σ = max(x, 0) is the ReLU node. We assume that the input x follows Gaussian distribution and the output is generated by a teacher network with parameters w * . In K = 1 we show a close-form nonlinear dynamics can be obtained and its convergence to w * can be proven, if we sample the initialization properly. Such initialization is consistent with common practice [Glorot & Bengio (2010) ; He et al. (2015) ] and is independent of the value of w * . For K ≥ 2, when the teacher parameters {w * j } form a orthonormal bases, we prove that the trajectory from symmetric initialization is trapped into a saddle point, while certain symmetric breaking initialization converges to w * without trapped into any local minima. Future work includes analysis of general cases (or symmetric case plus noise) for K ≥ 2, and a generalization to multilayer ReLU (or other nonlinear) networks. 

7. APPENDIX:

Here we list all detailed proof for all the theorems.

7.1 PROPERTIES OF RELU NETWORKS Lemma 7.1 For neural network with ReLU nonlinearity and using l 2 loss to match with a teacher network of the same size, the negative gradient g j for node j at layer c has the following form:

EQUATION

where L j and L * j are N -by-N diagonal matrices. For any k ∈ [c + 1], L k = j∈[c] w jk D j L j and similarly for L * k .

Proof We prove by induction on layer. For the first layer, there is only one node with g = uv, therefore L j = L j = I. Suppose the condition holds for all node j ∈ [c]. Then for node k ∈ [c+1],

we have:

g k = j w jk D j g j = j w jk D j L j   j L * j u j - j L j v j   = j w jk D j L j   j L * j k D * j w * jk u k - j L j k D j w jk v k   = j w jk D j L j j L * j D * j k w * jk u k - j w jk D j L j j L j D j k w jk v k = k   j w jk D j L j     j L * j D * j w * jk   u k - k   j w jk D j L j     j L j D j w jk   v k

Setting L k = j w jk D j L j and L * k = j w * jk D * j L * j (both are diagonal matrices), we thus have: 

g k = k L k L * k u k -L k L k v k = L k k L * k u k -L k v k (19)

where θ ∈ [0, π] is the angle between e and w.

Proof Note that F can be written in the following form:

F (e, w) = i:x i e≥0,x i w≥0

x i x i w (21)

where x i are samples so that

X = [x 1 , x 2 , • • • , x n ]

. We set up the axes related to e and w as in Fig. 6 , while the rest of the axis are prependicular to the plane. In this coordinate system, any vector x = [r sin φ, r cos φ, x 3 , . . . , x d ]. We have an orthonomal set of bases: e, e ⊥ = -e-w/ w cos θ sin θ

(and any set of bases that span the rest of the space). Under the basis, the representation for e and w is [1, 0 d-1 ] and [ w cos θ, -w sin θ, 0 d-2 ]. Note that here θ ∈ (-π, π]. The angle θ is positive when e "chases after" w, and is otherwise negative. Now we consider the quality R(φ 0 ) = E 1 N i:φi∈[0,φ0] x i x i . If we take the expectation and use polar coordinate only in the first two dimensions, we have: r 2 p(r)rdr = 2). Any off-diagonal element except for the first 2-by-2 block is zero due to symmetric property of i.i.d Gaussian variables. Any diagonal element outside the first 2-by-2 block will be P [φ i ∈ [0, φ 0 ]] = φ 0 /2π. Finally, we have:

R(φ 0 ) = E   1 N i:φi∈[0,φ0] x i x i   = E [x i x i |φ i ∈ [0, φ 0 ]] P [φ i ∈ [0, φ 0 ]] = +∞ 0 +∞ -∞ φ0 0    r sin φ r cos φ . . . x d    [

EQUATION

With this equation, we could then compute E [F (e, w)]. When θ ≥ 0, the condition {i :

x i e ≥ 0, x i w ≥ 0} is equivalent to {i : φ i ∈ [θ, π]} (Fig. 6(a)). Using w = [ w cos θ, -w sin θ, 0 d-2 ]

and we have:

EQUATION

For θ < 0, the condition {i :

x i e ≥ 0, x i w ≥ 0} is equivalent to {i : φ i ∈ [0, π + θ]} (Fig. 6(b))

, and similarly we get

EQUATION

where

EQUATION

From Gautschi's Inequality

EQUATION

with s = 1/2 and x = d/2 we have:

EQUATION

Therefore, it suffices to have

EQUATION

Note that this upper bound is tight when δ → 0 and d → +∞, since all inequality involved asymptotically becomes equal.

7.3. TWO LAYER CASE:

Lemma 7.5 For φ * , θ and φ defined in Eqn. 17:

EQUATION

we have the following relations in the triangular region Ω 0 = {(x, y) : x ≥ 0, y ≥ 0, x ≥ y + 0 } (Fig. 6 (c)):

(1) φ, φ * ∈ [0, π/2] and θ ∈ [0, θ 0 ) where θ 0 = arccos 1 √ K .

(2) cos φ = 1 -α 2 (x -y) 2 and sin φ = α(x -y) 2 -α 2 (x -y) 2 .

(3) φ * ≥ φ (equality holds only when y = 0) and φ * > θ.

Proof Propositions (1) and ( 2) are computed by direct calculations. In particular, note that since cos θ = αx = 1/ 1 + (K -1)(y/x) 2 and x > y ≥ 0, we have cos θ ∈ (1/ √ K, 1] and θ ∈ [0, θ 0 ). For Preposition (3), φ * = arccos αy > θ = arccos αx because x > y. Finally, for x > y > 0, we have

cos φ cos φ * = α 2 (2xy + (K -2)y 2 ) αy = α(2x + (K -2)y) > α(x + (K -1)y) > 1 (48)

The final inequality is because K ≥ 2, x, y > 0 and thus

(x + (K -1)y) 2 > x 2 + (K -1) 2 y 2 > x 2 + (K -1)y 2 = α -2 . Therefore φ * > φ. If y = 0 then φ * = φ.

Theorem 7.6 For the dynamics defined in Eqn. 16, there exists 0 > 0 so that the trianglar region Ω 0 = {(x, y) : x ≥ 0, y ≥ 0, x ≥ y + 0 } (Fig. 6(c )) is a convergent region. That is, the flow goes inwards for all three edges and any trajectory starting in Ω 0 stays.

Proof We discuss the three boundaries as follows:

Case 1: y = 0, 0 ≤ x ≤ 1, horizontal line. In this case, θ = 0, φ = π/2 and φ * = π/2. The y component of the dynamics in this line is:

EQUATION

To prove Eqn. 59, first we notice that K cos θ = Kαx = β + (K -1)β 2 . Therefore, we have (K cos θ -β) 2 -(K -1) 2 β 2 2 = 0, which gives β 2 -2β cos θ + 1 -K sin 2 θ = 0. Solving this quadratic equation and notice that β ≥ 1, θ ∈ [0, π/2] and we get:

β = cos θ + cos 2 θ + K sin 2 θ -1 = cos θ + √ K -1 sin θ (61)

Lemma 7.8 After reparametrization (Eqn. 58), f 3 (β, ) ≥ 0 for ∈ (0, β 2 /β]. Furthermore, the equality is true only if (β, ) = (1, 1) or (y, ) = (0, 1).

Proof Applying the parametrization (Eqn. 58) to Eqn. 56 and notice that α = β 2 = β 2 (β), we could write f 3 = h 1 (β) -(φ + (K -1) sin φ) (62) When β is fixed, f 3 now is a monotonously decreasing function with respect to > 0. Therefore, f 3 (β, ) ≥ f 3 (β, ) for 0 < ≤ ≡ β 2 /β. If we could prove f 3 (β, ) ≥ 0 and only attain zero at known critical point (β, ) = (1, 1), the proof is complete.

Denote f 3 (β, ) = f 31 + f 32 where f 31 (β, ) = φ * -θ -φ + α sin θ (63) f 32 (β, ) = (K -1)(α sin φ * -sin φ) (64)

For f 32 it suffices to prove that (α sin φ * -sin φ) = β 2 sin φ * -β2 β sin φ ≥ 0, which is equivalent to sin φ * -sin φ/β ≥ 0. But this is trivially true since φ * ≥ φ and β ≥ 1. Therefore, f 32 ≥ 0. Note that the equality only holds when φ * = φ and β = 1, which corresponds to the horizontal line x ∈ (0, 1], y = 0.

For f 31 , since φ * ≥ φ, φ * > θ and ∈ (0, 1], we have the following:

EQUATION

And it reduces to showing whether β sin θ -θ is nonnegative. Using Eqn. 59, we have:

EQUATION

Note that f 33 = cos 2θ + √ K -1 sin 2θ -1 = √ K cos(2θ -θ 0 ) -1, where θ 0 = arccos 1 √ K . By Prepositions 1 in Lemma 7.5, θ ∈ [0, θ 0 ). Therefore, f 33 ≥ 0 and since f 33 (0) = 0, f 33 ≥ 0. Again the equity holds when θ = 0, φ * = φ and = 1, which is the critical point (β, ) = (1, 1) or (y, ) = (0, 1). Theorem 7.9 For the dynamics defined in Eqn. 16, the only critical point (∆x = 0 and ∆y = 0) within Ω is (y, ) = (0, 1).

Proof We prove by contradiction. Suppose (β, ) is a critical point other than w * . A necessary condition for this to hold is f 3 = 0 (Eqn. 56). By Lemma 7.8, > = β 2 /β > 0 and

EQUATION

So -1 + Ky is strictly greater than zero. On the other hand, the condition f 3 = 0 implies that 

:



Figures and Tables:

Figure 1: (a) We consider the student and teacher network as nonlinear neural networks with ReLU nonlinearity. The student network updates its weight w from the output of the teacher, whose weights w * are fixed. (b)-(c) The network structure we consider in K = 1 and K ≥ 2 cases. (d) Notations used in multilayer ReLU gradient update rule (Sec. 2.2)

Figure 2: (a) Sampling strategy to maximize the probability of convergence. (b) Relationship between sampling range r and desired probability of success (1 -)/2. (c) Geometry of K = 1 2D case. There is a singularity at the origin. Initialization with random weights around the origin has decent probability to converge to w * .

(a)), as shown in the following theorem: Theorem 3.3 The dynamics in Eqn. 11 converges to w * with probability at least (1 -)/2, if the initial value w (1) is sampled uniformly from B r = {w : w ≤ r} with r ≤ 2π d+1 w * .

Figure 3: (a) Distribution of relative RMS error with respect to θ = ∠(w, e). (b) Relative RMS error decreases with sample size, showing the asympototic behavior of the close form expression Eqn. 10. (c) Eqn. 10 also works well when the input data X are generated by other zero-mean distribution X, e.g., uniform distribution in [-1/2, 1/2].Vector eld in (x, y) plane (K = 2)Vector eld in (x, y) plane (K = 5)

Figure5: Top row: Convergence when the initial weights deviates from symmetric initialization: w (1) = 10 -3 w * + . Here ∼ N (0, 10 -3 * noise). The 2-layered network converges to w * until very large noise is present. Both teacher and student networks use g(x) = K j=1 σ(w j x). Each experiment has 8 runs. Bottom row: Convergence when we use g 2 (x) = K j=1 a j σ(w j x). Here the top weights a j is fixed at different numbers (rather than 1). Large positive a j correponds to fast convergence. When a j has positive/negative components, the network does not converge to w * .

Figure 6: (a)-(b) Two cases in Lemma 7.2. (c) Convergence analysis in the symmetric two-layered case.

Suppose F (e, w) = X D(e)D(w)Xw where e is a unit vector and X= [x 1 , x 2 , • • • , x N ] is N -by-d sample matrix. If x i ∼ N (0, I) and are i.i.d, then: E [F (e, w)] = N 2π ((π -θ)w + w sin θe)

r sin φ r cos φ . . . x d ] p(r)p(θ) d k=3 p(x k )rdrdφdx 3 . . . dx d where p(r) = e -r 2 /2 and p(θ) = 1/2π. Note that R(φ 0 ) is a d-by-d matrix. The first 2-by-2 block can be computed in close form (note that +∞ 0

(K -1)(α sin φ * -sin φ) + α sin θ) = -1 (φ * -θ) + φ (68)Using φ ∈ [0, π/2], φ * ≥ φ and φ * > θ, we have:2π N ∆y = -(π -φ)( -1 + Ky) -(φ * -φ) -φy + ((K -1)(α sin φ * -sin φ) + α sin θ) y = -(π -φ)( -1 + Ky) -(φ * -φ) -1 (φ * -θ)y < 0 (69)So the current point (β, ) cannot be a critical point.

Peer review (iclr2017):
The paper proposes a convergence analysis of some two-layer NNs with ReLUs. It is not the first such analysis, but maybe it is novel on the assumptions used in the analysis, and the focus on ReLU nonlinearity that is pretty popular in practice. The paper is quite hard to read, with many English mistakes and typos. Nevertheless, the analysis seems to be generally correct. The novelty and the key insights are however not always well motivated or presented. And the argument that the work uses realistic assumptions (Gaussian inputs for example) as opposed to other works, is quite debatable actually. Overall, the paper looks like a correct analysis work, but its form is really suboptimal in terms of writing/presentation, and the novelty and relevance of the results are not always very clear, unfortunately. The main results and intuition should be more clearly presented, and details could be moved to appendices for example - that could only help to improve the visibility and impact of these interesting results.