Is the Skip Connection Provable to Reform the Neural Network Loss Landscape?

1 Introduction

Although deep learning has achieved great success in almost all the fields of machine learning, understanding the abilities of deep learning theoretically is still a hard problem. A neural network with a large number of hidden nodes has been proved to have strong expressive powers [Barron and A.R., 1993], but the non-convexity makes the model hard to be learned. The pioneering work in [Krizhevsky et al., 2012] utilized ReLU to improve the performance of deep networks, but ReLU is insufficient to train very deep ones. Resnet [He et al., 2016a; He et al., 2016b] is the most efficient structure after Alexnet, which utilizes skip connections to let the performance not get worse as the number of the layers increasing, yet due to the non-convexity of the loss function, a rigorous analysis of this property is not easy. There are lots of questions about the effect of this structure. For example, will the skip connections eliminate bad local minima created by the nonlinearity in residual blocks?

∗Coresponding Author

Figure 1: The loss surfaces of ResNet-56 projected into 3d with/without skip connections. 1

The problem of local minima is one of the most important questions in the theoretical study of neural networks. Gradient descent based algorithms will stop near the area of saddle points and local minima. By adding noise, it is possible to escape strictly saddle points and shallow local minima [Zhang et al., 2017], but distinguishing a bad but deep local minimum from a global one can be very hard [Jin et al., 2018]. If the loss of the suboptimal local minima created by the nonlinearity and multi-layer structures is very large, the performance of such networks may be very bad. However it has been shown that bad local minima are common in the nonover-parameterized two-layer networks [Safran and Shamir, 2018], so that it is generally hard to guarantee there is no bad local minima. Thus two questions arise naturally:

1.Since the loss in deep learning is not convex, what does the loss landscape of the deep neural network look like?

2.Since the residual network is now very successful, is the deep neural network with skip connections provably good such that more layers will not create more bad local minima?

There are some important works on these two questions. In the study of the landscape of the neural network, one of the most important properties is the "mode connectivity"[Kuditipudi et al., 2019] of networks, which has been proved in theory in [Freeman and Bruna, 2016], and shown by experiments in [Garipov et al., 2018; Draxler et al., 2018]. In these works, they showed that the sub-level sets of the loss function are nearly connecting, and the local minima found by gradient descent can be connected by some continuous paths in the parameter space and the loss on the path is almost const, such that the landscape has very good properties. One can guess these properties are true for any neural network, but it is only proved for two-layer ReLU networks in [Freeman and Bruna, 2016], and it's hard to go beyond this case.

1 This figure is plotted using ParaView and the visualization method in [Li et al., 2018]. Their code is available at https://github. com/tomgoldstein/loss- landscape.

Another important step is taken by the work in [Shamir, 2018], where the author compares the two models:

It is obvious that (1) has stronger expressive powers than (2). Surprisingly, the work in [Shamir, 2018] shows that all the local minima(with MSE loss) created by g(q , x) in (1) are provably no worse than the global minimum of convex model (2). However, their method is heavily dependent on the convexity of (2), thus it is hard to be generalized to more general cases. For an arbitrary neural network with skip connections, whether the skip connections can eliminate bad local minimum worse than shallower networks is still a open problem.

In the empirical aspect, the work in [Li et al., 2018] proposed a visualization method and showed that the skip connection does make the landscape smoother, and the loss landscape has nearly convex behaviors. We plot the loss surface of Resnet-56 with and without skip connections in Figure 1, then we can see the ResNet-56 with skip connections does have smoother and better loss landscape. On the other hand, it is shown in [Veit et al., 2016] that after removing the nonlinear parts in residual layer leaving the skip connection only, the performance will not drop too much. Thus one may guess that residual paths have ensemble-like behaviors. However, due to the non-convexity of the neural network, the principle is hard to be analyzed rigorously in theory.

In this work, we study these problems in the perspective of the sub-level sets of the loss landscape as in [Freeman and Bruna, 2016] to estimate the "depth" of local minima. In [Freeman and Bruna, 2016], the authors studied the two-layer ReLU network, and proved that the "Energy Gap" e satisfies e ≈ O(m- 1 n ) where m is the width and n is the dimension of the input data, therefore in the large width case, the landscape of the two-layer ReLU network has nearly convex behaviors. Following this line, in this paper, we compare the two networks (We use x to denote the parameters of the network, and s is the ReLU activation function):

where g(q , x) is a deep neural network with ReLU activation function. The form of f1 is similar to the "pre-activation" Resnet in [He et al., 2016b]. The structure of these two networks are showed in Figure 3.

We summarize our main results in the following theorem:

Theorem 1. (informal)Supposing X,Y are bounded random variables, L(x) is a convex function and R(x) is the regularization term, and f1 is defined as in (3), W1 ∈ Rm×n , W2 ∈ RdY×m , 0 < h < 1, l ≤ m h , ||W||0 is the number of non-zero column vectors in W,

for every strict local minimum F ∗ of F1 with F ∗ ≥ e(l), the depth of it is at most O(m h-1 n ).

This result shows that for a suitable loss function, although f1 is a multi-layer nonlinear network, by virtue of the skip connection, roughly all the local minima worse than the global minimum of the two-layer network f2 are very "shallow". The depths of these local minima are controlled by e = O(m h-1 n ), so that if m is very large, there is almost no bad strict local minima worse than e(l). From the well known universal approximation theorem, the expressive power of the two-layer network with ReLU is very strong(this can be easily poved using Hahn-Banach theorem), such that ||W∗2 s(W∗1 X)-Y ||2 → 0 as l →¥ for any functon Y = f (X) under very mild conditions. So this result in fact describes the depth of nearly all the local minima if m is very large.

2 RelatedWork

The global geometry of the deep neural network loss surfaces has been widely concerned for a long time. The characteristics of deep learning are high dimension and non-convex, which make the model hard to be analyzed. The loss surface for deep linear networks was firstly studied in [Kawaguchi, 2016]. It is shown that all the local minima are global, and all the saddle points are strict. Although the expressive power of the deep linear network is the same as the single-layer one, the loss of the deep linear network is still non-convex. This work pointed out that the linear product of matrices will generally only create saddle points rather than bad local minima. The first rigorous and positive works on non-linear networks are in [Tian, 2017] and [Du et al., 2018]. In these works, it is shown that, for a single-hidden-node ReLU network, under a very mild assumption on the input distribution, the loss is one point convex in a very large area. However, for the networks with multi-hidden nodes, the authors in [Safran and Shamir, 2018] pointed out that spurious local minima are common and indicated that an over-parameterization (the number of hidden nodes should be large) assumption is necessary. The loss surface of the two-layer over-parameterized network was studied in [Du and Lee, 2018] and [Mahdi et al., 2018]. They showed that the over-parameterization helps two-layer networks to eliminate all the bad local minima, yet their methods required the unrealistic quadratic activation function (By using Hahn-Banach theorem, it is easy to show there are some functions which cannot be approximated by such networks). A different way to consider the landscape is in [Freeman and Bruna, 2016], which studied neural networks with ReLU and required the number of hidden nodes increases exponentially with the dimension of the input. They showed that if the number of the hidden nodes is large enough, the sub-level sets of the loss will be nearly connected.

The loss landscape of nonlinear skip connection networks was studied in [Shamir, 2018; Kawaguchi and Bengio, 2019; Yun et al., 2019]. In these papers, it is shown that all the local minima created by the nonlinearity in the residual layer will never be worse than the linear model, yet their methods heavily rely on the convexity of l(Wx) hence very hard to be generalized to more general residual networks. In our work, we focus on more realistic network structure f =W2[s(W1x)+V1g(q,V2s(W1x))], and give a similar result as [Shamir, 2018] and extend the work on skip connection network [Shamir, 2018; Kawaguchi and Bengio, 2019] to more general non-linear cases. The structure we study is similar to the work in [Allenzhu and Li, 2019], but we focus on the global geometry of the loss rather than the gradient descent behaviors near neural tangent kernels area. The techniques we use are closely related with the theorems in [Freeman and Bruna, 2016] and our results are much stronger to apply to arbitrarily multilayered residual units with ReLU activation function and a large class of convex functions.

3 Preliminaries: Connectedness of Sub-level Sets and the Depth of Local Minima

The loss surface of the model is closely related to the solvability of the optimization problem, and the sub-level set method is a very important tool to study the loss landscape. We consider the risk minimization of the loss:

The sub-level set of F(x) is defined as:

In the case that F is a convex function, we know that for any xA,xB, if x(t) = (1-t)xA +txB, we have F(x(t)) ≤ max(F(xA),F(xB)), so the sub-level sets for all l are connected. If F is a function such that all the local minima are global(not need to be convex), for any xA,xB we can find a continuous path x1(t), x2(t) with F(x1(t)), F(x2(t)) decreasing, then x1(0) = xA, x1(1) = x ∗ , x2(0) = xB, x2(1) = x ∗ , so that we can produce a path x(t) with F(x(t)) ≤ max(F(xA),F(xB)) by splicing the two paths together. Conversely, if the sub-level sets are connected, we can get some information about the strict local minima of the loss function:

Theorem 2. (Proposition 2.1[Freeman and Bruna, 2016]) Supposing WF(l) is connected for all l, any strict local minimum x ∗ , i.e. satisfying that there is a small disk D = dist(x ∗ , ·) ≤ e such that for all all the points x ′ ∈ D, F(x ′ ) > F(x ∗ ), is a global minimum.

Note that this theorem cannot exclude the existence of bad non-strict local minima. Figure 4 is an example that all the sub-level sets are connected, but bad non-strict local minima exist.

In the case not all the sub-level sets are connected, sublevel sets still help us to understand the local minima. In fact we have:

Theorem 3. Supposing WF(l) is connected for all l ≥ l0, all the strict local minima x ∗ satisfy F(x ∗ ) ≤l0

The theorem can be proved by showing that there is a decreasing path from any xA to x ∗ where F(x ∗ ) = l0. From the condition of this theorem, there is a continuous path x (t) from any xA to x ∗ with F(x (t)) ≤ F(xA) and F(x ∗ ) = l0. Supposing there is a t0 > 0 such that on the path F(x(t)), the part 0 ≤ t ≤ t0 is decreasing, due to the fact WF(F(x(t0))) is connected, there must be a new path x1(t) such that F(x1(t)), 0 ≤ t ≤ t0 +e0 is decreasing, and this process can be extended continuously in this way.

There is also a theorem about the depth of local minima:

Theorem 4. Suppose for any xA,xB ∈ WF(l), there is a smallest constant e > 0 (the depth) and a continuous path x (t) connecting xA to xB such that F(x(t)) ≤ l +e. Then for any strict local minimum x ∗ , we have a value l1 and a continuous path x1(t) such that x1(t) connects it to a point x ′ , with x ′ not belonging to the same connected component as x ∗ in WF (l1) and maxt (F(x1(t )) - F(x ∗ )) = e .

This theorem can be proved by directly constructing such a path as in Theorem 3 from the conditions of this theorem. It is easy to see that if there is sub-level set WF(l1) such that qA,qB are not in the same connected component, there is no decreasing path connecting the two points, so that e is the depth, which measures the difficulty to jump out a local minimum.

Remark 3.1. As in [Freeman and Bruna, 2016], the sub-level set is defined to be a closed, thus compact set. Under this definition, completely flat areas (c.f. Figure 4 ) will not influence the connectedness of such sub-level sets. And when we consider the connectedness of loss sub-level sets, it is sufficient to construct a path outside a zero-measure set. In fact, suppose there is a zero-measure set S. By adding small perturbation, there is a continuous path g(t) with g(t) ∈Q\S for almost all t, where Q\S is the parameter space outside S. We suppose F(g(t)) ≤l +e for almost all t and e can be arbitrarily small. Due to the continuity of the F and ⋂i(-¥, l +ei] = (-¥, l ] where ei is a monotone decreasing sequence to 0, we have F(g(t)) ≤l for all t and g(t) connects xA and xB.

In the two-layer ReLU network case, the depth of the local minima is given in [Freeman and Bruna, 2016]:

Theorem 5. (Theorem 2.4 in [Freeman and Bruna, 2016]) Consider the loss function F(W1,W2) =EX,Y∼P|Y - W2s(W1X)|2 , where X ∈ Rn ,Y ∈ R,W1 ∈ Rm×n ,W2 ∈ R1×m , and s is the ReLU activation function. For any xA,xB ∈ WF(l), there is a continuous path x(t) connecting xA and xB with F(x (t)) ≤ max(l , e) +O(a), where

l = m h ,a = m h-1 n ,h < 1, e(l) is the minimum approximation error using l hidden nodes, dW1 (m- l,a,m) ∼ O(a), dW1 (m, 0, m) ≤ l .

In the two-layer ReLU case, this shows the depth of all the local minima worse than e(l) is at most O(m- 1 n ).

4 Warm up: One-layer Case

In this section, we consider the loss landscape in the linear case:

where x ∈ Rdx ,W∈ Rdy×dx ,g(q,x) ∈ Rdz ,V ∈ Rdx×dz . with loss

In the case y is a scalar and l is the MSE loss function, this has been studied in [Shamir, 2018]. The result is improved in [Kawaguchi and Bengio, 2019]. And under a weaker condition, we have a new theorem about the sub-level sets:

Theorem 6. Supposing w→Ex,y L(wx,y) is a function such that the sub-level sets are connected for all w∈Rdy×dx+dz and {x ∈ Rdx+dz , y ∈ Rdy }, consider the input {x ∈ Rdx , y} and two models:

Let F1 = Ex,y∼P L( f1(x), y), F2 = Ex,y∼P L( f2(x), y). Assuming dy ≤ min{dx,dz}, for any parameter qA,qB and l ∈ R with F(q{A,B}) ≤ l, there exists a continuous path g(t) such that g(0) = qA, g(1) = qB, and

where

Proof. From lemma 7, all the sub-level sets of f (W,V) are connected. So there is a path connecting it to (W∗ ,V= 0,q) with the loss bounded by the endpoints. Note that F ∗ w = infW F2(W ) = W∗ (x + 0g(q , x)), our claim follows.

Lemma 7. For any distribution {x ∈ Rdx+dz ,y ∈ Rdy } ∼ P and dy ≤min{dx,dz}, supposing all the sub-level sets of function F(Z) =Ex,y L(Zx,y) are connected, the sub-level sets of function F(W,V) = Ex,y L([W,WV]x, y) are also connected.

Proof. Let F(Z) = Ex,y L(Zx,y). For any Z1,Z2, since the sub-level sets are connected, there is a continuous path Z(t) ∈ Rdy×(dx+dz) such that Z(0) = Z1 and Z(1) = Z2, with F(Z(t)) ≤ max(F(Z1),F(Z2)). To prove the theorem, we need a path with Z(0) = [W1,W1V1],Z(1) = [W2,W2V2] and Z(t) = [W(t),W(t)V(t)].

Note that dy ≤ min{dx,dz} so the sets rank(W(t)) ̸= dy have zero measure(since they are closed in Zariski topology). Following the discussion in Remark 3.1, we only need to prove in the case rank(W(t)) = dy. Let Zb(t) be the last dz columns of Z(t). We set V(t) =W+(t)Zb(t), where W+(t) is the Moore-Penrose pseudoinverse of W(t), then V(t) is continuous andW(t),V(t) is the required path.

Remark 4.1. In the case dy >min{dx,dz}, WV will always be a low rank matrix, so this proof is invalid. However, if the loss function is convex and the eigenvalues of the Hessian matrix are bounded by a and b with a b -1 small, the sublevel sets will still be connected. This can be proved using the methods in [Barber and Ha, 2018; Ha et al., 2018]. Since this is not the main target in this paper, we omit it.

5 Main Results

5.1 Assumptions and Preliminary Lemmas

Assumption 1. L(w,y) is a convex function for w, (x,y) ∼P are bounded, and R(x) is the regularization term. There is a constant C such that all the strict local minima of the loss

satisfying

where w2,i, v2,i are the ith column vector of W2 and V2, w1,i is the ith row vector of W1.

Assumption 2. L is locally Lipschitzian:

when ||x1||F , ||x2||F ≤C.

An example satisfying these assumptions is the MSE loss. In fact we have:

Theorem 8. Suppose g(q,x) is an arbitrary multi-layer ReLU network, with the loss

For any points with �F = 0, there is a constant C such that these assumptions are satisfied.

Proof. It is trivial that Assumption 2 is satisfied. We only need to prove Assumption 1. In this case, all the activation functions in this network are ReLU, so that we can write all the matrix parameter W as W= tWEW. where ||EW||1 = 1 and tW = ||W||1, s(tWEW) = tWs(EW). We fix all EW and the loss has the form (We only need to consider the case dy = 1 since if dy > 1, it can be reduced to �i |yi -xi|2 ):

where t,w,qi are the corresponding variables. We have:

Note that |tw|+|tv1|+|tv2| > 0, Ex [(t +tv1v2�i qi)wxy][(t +tv1v2 �i qi)wx] < 0 We have E [(t +tv1v2 �i qi)wx]2 ≤ E |[(t +tv1v2�i qi)wx]y| so k(|tw|+|tv1|+|tv2|) ∼ E |(t + tv1v2�i qi)wx| ∼ O(E|y|). This proof also applies to other variables, so our claim follows.

Before proving the main theorem, we need two key lemmas from [Freeman and Bruna, 2016]:

Lemma 9. Considering a matrix W ∈ Rm×n , which is equal to give m vectors, and 0 < h ≤ 1, there is a a collection Qm of at last m h vectors such that for any v1,v2 ∈Qm, ∠v1,v2 ≤ 2em,h = 2m h-1 n .

Lemma 10. Given w1, w2 with ||w1|| = ||w2|| = 1, ∠w1,w2 ≤ a, and s is the ReLU activation function, we have Ex||s(w1x)-s(w2x)||2 ≤ 4||Sx||a 2 , where SX = EX∼P XX T ∈Rn×n

These lemmas are from the proof of corollary 2.5 and proposition 2.3 in [Freeman and Bruna, 2016] respectively.

5.2 Main Theorem

Theorem 11. Consider a distribution {x ∈ Rn , y ∈ Rdy } ∼ P, s the ReLU activation function, and a neural network with a skip connection:

with L a function satisfying assumption 1 and 2. Assume g(q,x) is a neural network with ReLU activation functions and R(x ) is the regular term with R(x ) = �i ||w2,i||1||w1,i||2 + �i ||v2,i||1||w1,i||2+||W2V1||1+�i ||qi||F. Let

then we have: For any h < 1, l < m h , xA, xB and l ∈ R satisfying F(x{A,B}) ≤ l , there exists a continuous path g(t) such that g(0) = xA, g(1) = xB, and

where m is the dimension of W1 ∈ R m×n and

Remark 5.1. Our regularization term is chosen to be compatible with the loss function, and it is also compatible with the two-layer linear network. It can be replaced by using good initialization [Glorot and Bengio, 2010] or if we only consider a specific bounded area.

Proof. Supposing W1 ∈ Rm×n ,W2 ∈ Rdy×m,V2 ∈ Rdg×m,V1 ∈ Rn×do , we need to construct a path g(t) from (W1,A,W2,A,V1,A,V2,A,qA) to (W1,B,W2,B,V1,B,V2,B,qB). Note that we only need to construct a path g1(t) from any (W1,A,W2,A,V1,A,V2,A,qA) to (W∗1 ,W∗2 ,V∗1 ,V∗2 ,q ∗ ) with F(W∗1 ,W∗2 ,V∗1 ,V∗2 ,q ∗ ) = F ∗ and show that F(g1(t)) ≤ max(F(g1(0)),F ∗ ) + O(m h-1 n ) because the second half of the path g(t) is the inverse of the first half. So we need to construct the following parts:

1.(W1,A,W2,A, V1,A, V2,A, qA) to (W1,l ,W2,l , V1,l , V2,l , ql ). On this path, the norms of all matrices are reduced without increasing the loss in virtue of the regularization term, such that the g(q,x) and ||W2V1|| are bounded.

2. (W1,l ,W2,l ,V1,l ,V2,l ,ql) to (W1,l ,W2,s,V1,s,V2,s,ql). On this path, W2,s is a (m - l)-term approximation using perturbed atoms to minimize Ex||W2s s(W1,lx) - W2,ls(W1,lx)||F, and V2,s is a (m-l)-term approximation to minimize Ex||V2,ss(W1,lx)-V2,ls(W1,lx)||2 F . The loss increasing along this path is roughly bounded by O(m h-1 n ).

3. (W1,l ,W2,s,V1,s,V2,s,ql) to (W∗1 ,W∗2 ,0,0,0).

On this path, (W∗1 ,W∗2 ) are the parameters of l-term approximation:

W2,s is m-l sparse with l zero columns andW∗2 has no-zero values only on these l columns. The loss along that path will be upper bounded by l and e(l).

The construction of these path is described as follow: Step 1: Consider the loss:

Since the Assumption 1 is satisfied, there is a constant C independent of m and a continuous path without increasing the loss such that

and ∀i, ||w1,i||2 = 1 where w1,i is the ith row vector of W1. Thus ||g(q,x)||F will be G0 Lipschitzian for x. Then fix W1, q and V2, and consider the path W2(t),V1(t) to the nearest local minimum. The loss will not increase on this path.

Step 2: The m-l spare parameter matrix W2,s and V2,s are constructed as follow: Find a set Qm of row vectors in W1,l as in Lemma 9 and select a vector v at the jth row such that for any vi ∈ Qm at the ith row of W1, ∠vi,v ≤ 2em,h. W2,s is constrcuted by setting the rows corresponding to the vectors in Qm to be zero, and for the corresponding column of W2,s,i = 0,W2,s, j = �iW2,l,i +W2,l, j . The construction of V2,s is similar. Consider the paths W2(t),V2(t) constructed as follow:

where i1, i2... are the indexes corresponding to the rows of vectors in Qm and ¯aj, ¯ bj are the ones corresponding to the rows of vectors in the jth row. We have ¯ai1 = (1-t)ai1 , ¯ bi1 =(1-t)bi1 and ˜ aj =aj +�k taik , ˜ bj =bj +�k tbik . This process will not increase the regularization loss.

For i ∈Qm, j ∈Q2, let s(W1,lx)i =s(W1,lx) j +ni.

Let V1(t) = W+2 (t)W2(0)V1(0), where W+2 (t) is the Moore-Penrose pseudoinverse. Note that the set rank W2 ̸= dy has zero measure. We only need to consider the case

Step 3: W2,s and V2,s are m- l sparse, so changing the l rows in W1,l will not influence the loss. We consider a path to change these l rows to be same as W∗1 and the loss on this path is constant. The second step is to construct a path (W2(t),W1(t),V1(t)) with W2(0) =W2,s,W2(1) = W∗2 , W2(1)V1(1) = 0. As the proof of Lemma 7, since the loss is convex for the final layer, the loss on this path is bounded by the two endpoints, and note that:

The properties are satisfied.

5.3 Discussion

Theorem 11 is a generalization of Theorem 5 in [Freeman and Bruna, 2016] and the linear case Theorem 6. As pointed out in section 3, this shows that for all local minima worse than the global minimum F ∗ of two-layer networks with l = m h hidden nodes, the depth is bounded by O(m h-1 n ), so that as m→¥, WF(l) is nearly connected if l > F ∗ . Benefitting from the strong expressiveness of the two-layer ReLU network, for almost all the learning problem, F ∗ in this theorem will be much better than that in the linear case Theorem 6.

6 Conclusion

In this paper, we studied the loss landscape of the multi-layer nonlinear neural network with a skip connection and consider the connectedness of sub-level sets by constructing a path and estimating the loss on this path. The main theorem reveals that by virtue of the skip connection, under mild conditions all the local minima worse than the global minimum of the two-layer ReLU network will be very shallow, such that the "depths" of these local minima are at most O(m h-1 n ), where h < 1, m is the number of the hidden nodes in the first layer, and n is the dimension of the input data. This result shows that despite the non-convexity of the non-linear networks, skip connections provably help to reform the loss landscape, and in the over-parametrization(m→¥) case, nearly all the strict local minima are no worse than the global minimum of the two-layer ones. Our results provide a theoretical explanation of the effectiveness of the skip connections and take a step to understand the mysterious effectiveness of deep learning networks.

Acknowledgments

The authors thank Wenyu Zhang for his great help. This research was funded by the National Key Research and Development Program of China, grant number 2018YFC0831300.