Title: G-SGD: OPTIMIZING RELU NEURAL NETWORKS IN ITS POSITIVELY SCALE-INVARIANT SPACE

Abstract: It is well known that neural networks with rectified linear units (ReLU) activation functions are positively scale-invariant. Conventional algorithms like stochastic gradient descent optimize the neural networks in the vector space of weights, which is, however, not positively scale-invariant. This mismatch may lead to problems during the optimization process. Then, a natural question is: can we construct a new vector space that is positively scale-invariant and sufficient to represent ReLU neural networks so as to better facilitate the optimization process ? In this paper, we provide our positive answer to this question. First, we conduct a formal study on the positive scaling operators which forms a transformation group, denoted as G. We show that the value of a path (i.e. the product of the weights along the path) in the neural network is invariant to positive scaling and prove that the value vector of all the paths is sufficient to represent the neural networks under mild conditions. Second, we show that one can identify some basis paths out of all the paths and prove that the linear span of their value vectors (denoted as G-space) is an invariant space with lower dimension under the positive scaling group. Finally, we design stochastic gradient descent algorithm in G-space (abbreviated as G-SGD) to optimize the value vector of the basis paths of neural networks with little extra cost by leveraging back-propagation. Our experiments show that G-SGD significantly outperforms the conventional SGD algorithm in optimizing ReLU networks on benchmark datasets.

1. INTRODUCTION:

Over the past ten years, neural networks with rectified linear hidden units (ReLU) (Hahnloser et al., 2000) as activation functions have demonstrated the power in many important applications, such as information system (Cheng et al., 2016; Wang et al., 2017) , image classification (He et al., 2016a; Huang et al., 2017 ), text understanding (Vaswani et al., 2017) , etc. These networks are usually trained with Stochastic Gradient Descent (SGD), where the gradient of loss function with respect to the weights can be efficiently computed via back propagation method (Rumelhart et al., 1986) .

Recent studies (Neyshabur et al., 2015; LeCun et al., 2015) show that ReLU networks have positively scale-invariant property, i.e., if the incoming weights of a hidden node with ReLU activation are multiplied by a positive constant c and the outgoing weights are divided by c, the neural network with the new weights will generate exactly the same output as the old one for an arbitrary input. Conventional SGD optimizes ReLU neural networks in weight space. However, it is clear that weight vector is not positively scale-invariant. This mismatch may lead to problems during the optimization process (Neyshabur et al., 2015) .

Then, a natural question is: can we construct a new vector space that is positively scale-invariant and sufficient to represent ReLU neural networks so as to better facilitate the optimization process ? In this paper, we provide positive answer to this question.

We investigate the positively scale-invariant space to sufficiently represent ReLU neural networks by the following four steps. Firstly, we define the positive scaling operators and show that they form a transformation group (denoted as G). The transformation group G will induce an equivalence relationship called positive scaling equivalence. Then, We found that the values of the paths are invariant to positive scaling operators. Furthermore, we prove that two weight vectors are positively scale-equivalent if and only if the values of the paths in one neural network equal to those in the other neural network, given the signs of some weights unchanged. That is to say, the values of all the paths can sufficiently represent a ReLU neural network. After that, we show that the path vectors are linearly dependent. 1 We define the maximal group of paths which are linearly independent as basis path, which corresponds to the basis of the structure matrix constituted by the path vectors. Thus, the values of the basis paths are also positively scale-invariant and can sufficiently to represent the ReLU neural networks. We denote the vector whose coordinations are composed by values of basis paths as basis path value vector and call the vector space composed by basis path value vector as G-space.

In addition, we prove that the dimension of G-space is "H" smaller comparing to the weight space, where H is the total number of hidden units in a multi-layer perceptron (MLP) or feature maps in a convolutional networks (CNN).

To sum up, we find G-space constituted by the values of the basis paths, which is positively scaleinvariant, can sufficiently represent the ReLU neural networks, and has a smaller dimension than the vector space of weights. Therefore, we propose to optimize the ReLU neural networks in its positively scale-invariant space, i.e., G-space. We design a novel stochastic gradient descent algorithm in G-space (abbreviated as G-SGD) to optimize the ReLU neural networks utilizing the gradient with respect to the values of the basis paths. First, we design skeleton method to construct one group of the basis paths. Then, we develop inverse-chain rule and weight allocation to efficiently compute the gradient of the values of the basis paths by leveraging the back-propagation method. Please note that by using these techniques, there is very little additional computation overhead for G-SGD in comparison with the conventional SGD.

We conduct experiments to show the effectiveness of G-SGD. First, we evaluate G-SGD of training deep convolutional networks on benchmark datasets and demonstrate that G-SGD achieves clearly better performance than baseline optimization algorithms. Second, we empirically test the performance of G-SGD with different degrees of positive scale-invariance. The experimental results show that the higher the positive scale-invariance is, the larger the performance improvement of G-SGD over SGD. This is consistent with that, the positive scale-invariance in weight space will negatively influence the optimization and our proposed G-SGD algorithm can effectively solve this problem.

2. BACKGROUNDS:



2.1. RELATED WORKS:

There have been some prior works that study the positively scale-invariant property of ReLU networks and design algorithms that are positively scale-invariant. For example, Badrinarayanan et al. (2015) notice the positive scale-invariance in ReLU netowrks, and inspired by this, they design algorithms to normalize gradients by layer-wise weight norm. Du et al. (2018) study the gradient flow in MLP or CNN models with linear, ReLU or Leaky ReLU activation, and prove the squared norms of gradient across different layers are automatically balanced and remained invariant in gradient descent with infinitesimal step size. In our work, we do not care whether the models are balanced or not. Besides, many other optimization algorithms also have positively scale-invariant property such as Newton's method and natural gradient descent. The most related work is Path-SGD (Neyshabur et al., 2015) , which also considers the geometry inspired by path norm. This work is different from ours: 1) they regularize the gradient in weight space by path norm while we optimize the loss function directly in a positively scale-invariant space; 2) they do not consider the dependency between paths and it's hard for them to compute the exactly path-regularized gradients. Different from the previous works, we propose to directly optimize the ReLU networks in its positively scale-invariant space, instead of optimizing in the weight space which is not positive scale-invariant. To the best of our knowledge, at the first time, we solve this mismatch by theoretical analysis and an effective and efficient algorithm.

2.2. RELU NEURAL NETWORKS:

Let Nw(x) : X → Y denote a L-layer multi-layer perceptron (MLP) with weight w ∈ W ⊂ R m , the input space X ⊂ R d and the output space Y ⊂ R K . In the l-th layer (l = 0, • • • , L), there are h l nodes. It is clear that, h 0 = d, h L = K. We denote the i l -th node and its value as O l i l and o l i l , respectively. We use w l to denote the weight matrix between layer l-1 and layer l, and use w l (i l-1 , i l ) to denote the weight connecting nodes O l-1 i l-1 and O l i l . The values of the nodes are propagated as

o l = σ((w l ) T o l-1 ), where σ(•) = max(•, 0) is the ReLU activation function. We use (i0, • • • , iL) to denote the path starting from input feature node O 0 i0 to output node O L i L passing though hidden nodes O 1 i 1 , • • • , O L-1 i L-1 .

We can also regard the network structure as a directed graph (O, E), where

O = {O 1 , • • • , O H+d+K }

is the set of nodes where H denotes the number of hidden nodes and E = {e ij } denote the set of edges in a network where e ij denotes the edge pointing to O j from nodes O i . We use w e , e ∈ E to denote the weight on edge e. If |E| = m, the weights compose a vector w = (w 1 , • • • , w m ) T . We define a path as a vector p = (p 1 , • • • , p m ) T and if the edge e is contained in path p, p e = 1; otherwise p e = 0. Because a path crosses L edges for an L-layer MLP, there are L elements with value 1 and others elements with value 0. Using these notations, the value of path p can be calculated as v p (w) = m i=1 w pi i and the activation status of path p can be calculated as a p (x; w) = j:pe ij =1 I(o j (x; w) > 0). We denote the set composed by all paths as P and the set composed by paths which contain edge connecting the i 0 -th input node and the k-th output node as P i0,k . Thus, the output can be computed as follows:

EQUATION

3. POSITIVELY SCALE-INVARIANT SPACE OF RELU NETWORKS:

In this section, we first define positive scaling transformation group and the equivalence class induced by this group. Then we study the invariant space under positive scaling transformation group of ReLU networks and study its dimension.

3.1. POSITIVE SCALING TRANSFORMATION GROUP:

We formally define the positive scaling operator. We first define a node positive scaling operator gc,O(w) : W → W with constant c > 0 and one hidden node O as

w = g c,O l i l (w),

where

wl (i l-1 , i l ) = c • w l (i l-1 , i l ) for i l-1 = 1, • • • , h l-1 ; wl+1 (i l , i l+1 ) = 1 c • w l+1 (i l , i l+1 ) for i l+1 = 1, • • • , h l+1 ;

and values of other elements of w are the same with w. Definition 3.1 (positive scaling operator) Suppose that {O1, • • • , OH } is the set of all the hidden nodes in the network where H denotes the number of hidden nodes. A positive scaling operator

g (c 1 ,••• ,c H ) (•) : W → W with c1, • • • , cH ∈ R + is defined as g (c 1 ,••• ,c H ) (•) := gc 1 ,O 1 • gc 2 ,O 2 • • • • • gc H ,O H (•),

where • denotes function composition.

We then collect all the

g (c 1 ,••• ,c H ) (•) together to form a set G := {g (c 1 ,••• ,c H ) (•) : c1, • • • , cH ∈ R + }.

It is easy to check that G together with the operation "•" is a group which is called positive scaling transformation group, and we call the group action of G on W as G-action. (Please refer to Section 8 in Appendix.) Clearly, if there exists an operator g ∈ G to make w = g(w ), ReLU networks N w and N w will generate the same output for any fixed input x. We define the positive scaling equivalence induced by G-action. Definition 3.2 Consider two ReLU networks with weights w, w ∈ W and the positive scaling transformation group G. We say w and w are positively scale-equivalent if ∃g ∈ G such that w = g(w ), denote as w ∼ G w .

Given G-action on W, the equivalence relation "∼ G " partitions W into G-equivalent classes. The following theorem shows that the sufficient and necessary condition for ReLU networks in the same equivalent class is that they have the same values and activation status of paths. Theorem 3.3 Consider two ReLU neural networks with weights w, w ∈ W. We have that w ∼ G w iff for ∀ path p ∈ P and any fixed input x ∈ X , we have vp(w) = vp(w ) and ap(x; w) = ap(x; w).

Invariant variables for a group action are important and widely studied in group theory and geometry. We say a function f :

W → R is invariant variable of G-action if f (w) = f (g(w)), ∀g ∈ G.

Based on Theorem 3.3, a direct corollary is that values and activation status of paths are invariant variables under G-action. Considering that 1) values of paths are G-invariant variables while the weights aren't; 2) values of paths together with the activation status determines an positive scale-equivalent class, and are sufficient to determine the loss, we propose to optimize the values of paths instead of weights. . A is the structure matrix of this example.

3.2. POSITIVELY SCALE-INVARIANT SPACE AND ITS DIMENSION:

Although Theorem 3.3 shows the values of paths are invariant variables under G-action, we find that the paths have inner-dependency and therefore their values and activation statuses are not independent. Let us consider the example in Figure 1 . The values of paths have the relationship

v p 4 (w) = v p 2 (w)•v p 3 (w) v p 1 (w)

. Using the vector representation of paths that is described in section 2.2, we find that their path vectors follow the relationship p 4 = p 2 + p 3 -p 1 , which means that they are not linearly independent.

For a feedforward ReLU neural network, we suppose that P ⊂ {0, 1} m is the set composed by all path vectors. We denote the matrix composed by all paths as A and call it structure matrix of ReLU networks. The size of A is m × n where n is the number of paths. We observe that the paths in matrix A are not linearly independent. Then we study the rank of matrix A and find a maximal linearly independent group of paths.

Theorem 3.4 If A is the structure matrix for a ReLU network, then we have rank(A) = m -H, where m is the dimension of weight vector w and H is the total number of hidden nodes for MLP (or feature maps for CNN models) with ReLU respectively. Definition 3.5 (basis path) A set of paths

P 0 = {p 1 , • • • , p m-H } which is a subset of P is called a set of basis paths if p 1 , • • • , p m-H

compose a maximal linearly independent group of column vectors in structure matrix A.

We design an algorithm called skeleton method to identify basis paths efficiently, which will be introduced in Section 4. For given values of basis paths and structure matrix, the values of w can not be determined unless the values of free variables are fixed (Lay (1997)). Assume w s1 , • • • , w s H are selected to be the free variables which are called free skeleton weights, we prove that the activation status can be uniquely determined by the values of basis paths if signs of free skeleton weights are fixed. Thus, we have the following theorem which is a modification of Theorem 3.3. Theorem 3.6 Consider two ReLU neural networks with weights w, w ∈ W with the same signs of skeleton weights. We have that w ∼ G w iff for ∀p ∈ P 0 , we have vp(w) = vp(w ).

The detailed proof of Theorem 3.4 and Theorem 3.6 are both depends on Lemma 9.1 in Appendix. In the following context, we always suppose that ∀w ∈ W have the same signs of free skeleton weights.

According to Theorem 3.6 and the linear dependency between values of paths, the loss function can be calculated using values of basis paths if signs of free skeleton weights are fixed. We denote the the loss at training instance (x, y) as l(v; x, y) and propose to optimize the values of basis paths. Considering that values of basis paths are obtained through structure matrix A, the dimension of the space composed by values of basis paths should be equal to rank(A). Then we define the following space.

Definition 3.7 (G-space) The G-space is defined as

V := {v = (v p 1 , • • • , v p m-H ) : v ∈ (R/{0}) m-H }.

We call the space composed by the values of basis paths G-space, which is invariant under transformation group G, i.e., it is composed by invariant variables under G-action. Immediately, we can get the following corollary according to Theorem 3.6.

Corollary 3.8 The dimension of G-space is m -H, where m is the number of weights and H is the total number of hidden nodes for MLP or the total number of feature maps for CNN.

We measure the reduction of the dimension for positively scale-invariant space using the invariant ratio H/m, thus we can empirically test how severe this equivalence will influence the optimization in weight space. In this section, we will introduce the G-SGD that optimizes ReLU neural network models in the G-space. This novel algorithm makes use of three methods, named Skeleton Method, Inverse-Chain-Rule (ICR) and Weight-Allocation (WA), respectively, to calculate the gradients w.r.t. basis path vector and project the updates back to weights efficiently (with little extra computation in comparison with standard SGD).

4. ALGORITHM: G-SGD:



4.1. SKELETON METHOD:

Before the calculation of gradients in G-space, we first design an algorithm called skeleton method to construct skeleton weights and basis paths for MLP whose depth is L and width is h.

1. Construct skeleton weights: for weight matrix w 2 , • • • , w L-1 , we select diagonal elements to be the skeleton weights. For weight matrix w 1 , we select the element w 1 (i 1 mod d, i 1 ) for column i 1 with i 1 = 1, • • • , h 1 to be the skeleton weights. For weight matrix w L , we select the element

w L (i L-1 , i L-1 mod K) for row i L-1 with i L-1 = 1, • • • , h L-1

to be the skeleton weights. We call the rest weights non-skeleton weights. Figure 2 gives an illustration for skeleton weights in a MLP network.

2.. Construct basis paths::

A path which contains at most one non-skeleton weights is a basis path. The proof of this statement could be found in Appendix. For example, in Figure 2 , the paths in red color and the paths with only one black weight are basis paths. Beyond that, the paths are non-basis paths.

Once we have basis paths, we can calculate the gradients w.r.t. basis path vector v p i , and iteratively update the model by

EQUATION

where S t is the mini-batch training data in iteration t. For the calculation of the gradients w.r.t. basis path vector, we introduce inverse-chain-rule method in next section.

4.2. INVERSE-CHAIN-RULE (ICR) METHOD:

The basic idea of the Inverse-Chain-Rule method is to connect the gradients w.r.t. weight vector and those w.r.t. basis path vector by exploring the chain rules in both directions. That is, we have,

( ∂l(w; x, y) ∂w1 , • • • , ∂l(w; x, y) ∂wm ) = ( ∂l(v; x, y) ∂v p 1 , • • • , ∂l(v; x, y) ∂v p m-H ) •    ∂v p 1 ∂w 1 • • • ∂v p 1 ∂wm • • • ∂v p m-H ∂w 1 • • • ∂v p m-H ∂wm    (3)

We first compute the gradients w.r.t. weights, i.e., ∂l(w;x,y) ∂w i for i = 1, • • • , m using standard back propagation. Then we solve Eqn.(3) to obtain the gradients w.r.t. basis paths, i.e., ∂l(v;x,y) ∂v j for j = 1, • • • , m -H. We denote matrix at the right side of Eqn.(3) as G. Given the following facts:

(1) ∂vp ∂we = vp we if the edge e is contained in path p, otherwise 0; (2) according to the skeleton method, each non-skeleton weight will be contained in only one basis path, which means there is only one non-zero element in each column corresponding to non-skeleton weights in G, G is sparse and thus the solution of Eqn.( 3) is easy to obtain.

4.3. WEIGHT-ALLOCATION (WA) METHOD:

After the values of basis paths are updated by SGD, in a new iteration, we employ ICR again by leveraging BP with the new weight. Thus, we need to project the updates on basis paths back to the updates of weights.

We define the path-ratio of p j at iteration t as R t (p j ) := v t p j /v t-1 p j and the weight-ratio of w i at iteration t as r t (wi) := w t i /w t-1 i . Assume that we have already obtained the path-ratio for all the basis paths R t+1 (p j ) according to ICR method and the SGD update rule. Then we want to project the path-ratios onto the weight-ratios. We use the notation to denote the operation w p j = m i=1 w

p j i i

Because we have v p j (w) = w p j , the weight-ratios obtained after the projection should satisfy the following relationship: R t (p j ) = r t (w) p j . Generalize the operator from vectors to matrices 2 , we have the following relationship:

EQUATION

where the matrix A = (p 1 , • • • , p m-H ). According to this relationship, we design Weight-Allocation Method to project the path-ratio to weight-ratio as described below. Suppose that w 1 , • • • , w H are the free skeleton weights. We first add H elements with value 1 at the beginning in vector

(R t (p 1 ), • • • , R t (p m-H ))

to get a new m-dimensional vector. Then we append H columns in matrix A to get a new matrix Ã as Ã = [B, A ] with B = [I, 0] T where I is an H × H identity matrix with diagonal elements 1 and 0 is an H × m zero matrix with all elements 0. Then it is easy to prove that rank( Ã) = m and we have the following relationship:

EQUATION

We can get the weight-ratio by Ã-1 on both sides of Eq.( 5).

Because we have

EQUATION

)

After the projection, we can see that weight-ratios of free skeleton weights equal 1 which means that free skeleton weights will not be changed during the training process. According to the skeleton method again, Ã is a sparse matrix and it is easy to calculate its inverse.

Actually, the projection method is not unique. Although we choose one special projection which fixed values of free skeleton weights in the Weight-Allocation method, we prove that different projection methods will results in the same updates in G-space if they don't change the signs of free skeleton weights.

Theorem 4.1 Suppose that there are two different projections T 1 and T 2 that project the path-ratio to weight-ratio. If the projection will not change the signs of free skeleton weights, the values of basis paths will keep the same at every iteration for two G-SGD processes that are initialized with the same values of basis paths and use different projections T 1 and T 2 in WA method respectively.

Algorithm 1 G-SGD Require: initialization w 0 , learning rate η t , training data set D.

1. Construct skeleton weights using skeleton method and construct Ã-1 according to skeleton method and WA method.

for t = 1, • • • , T do 2.

Implement feed forward process and back propagation process to get ∂l(w;S t ) ∂w i w=w t . 3. Calculate ∂l(v;x,y) ∂v p j for j = 1, • • • , m -H according to Eqn.(3).

4. Using SGD to update the values of basis paths: v t+1 p j = v t p j -ηt • ∂l(v;x,y) ∂v p j .

5. Calculate path-ratios: R t (p j ) = v t+1 p j /v t p j . 6. Calculate weight-ratio r t (w i ) using Ã-1 according to Eqn.(6). 7. Update the weights as

w t+1 i = w t i • r t+1 (w i ). end for Ensure: w T .

Please note by combining the ICR and WA methods, we can obtain the explicit update rule for G-SGD, which is concluded in Algorithm 1. In this way, we obtain the correct gradients. The extra computational complexity of the ICR and WA methods are far lower than that of forward and backward propagation, and can therefore be neglected in practice.

5. EXPERIMENTS:

In this section, we first evaluate the performance of G-SGD on training deep convolutional networks and verify that if our proposed algorithm outperforms other baseline methods. Then we investigate the influence of positive scaling invariance on the optimization in weight space, and examine whether optimization in G space brings performance gain. At last, we compare G-SGD with Path-SGD (Neyshabur et al., 2015) and show the necessity of considering the dependency between paths. All experiments are averaged over 5 independent trials if without explicit note.

5.1. DEEP CONVOLUTIONAL NETWORK:

In this section, we apply our G-SGD to image classification tasks and conduct experiments on CIFAR-10 and CIFAR-100 (Krizhevsky & Hinton, 2009) . In our experiments, we employ the original ResNet architecture described in (He et al., 2016a) . Specifically, there is no positive scaling invariance across residual blocks since the residual connections break down the structure matrix described in Section 3.2, we target the invariance in each residual block. For better comparison, we also conduct our studies on a stacked deep CNN described in He et al. (2016a) (refer to PlainNet), and target the positive scaling invariance across all layers. We train 34 layers ResNet and PlainNet models on the datasets following the training strategies in the original paper, and compare the performance between G-SGD3 and vanilla SGD algorithm. The detailed training strategies could be found in Appendix. In this section, we focus on the performance of different optimization algorithms, and will discuss the combination of G-SGD and regularization in Appendix. As shown in Figure 3 and ResNet-34 with G-SGD on both datasets, which indicates that G-SGD indeed helps the optimization of ResNet model; 2) Since G-SGD can eliminate the influence of positive scaling invariance across all layers of PlainNet, we observe the performance gain on PlainNet is larger than that on ResNet. For PlainNet model, G-SGD surprisingly improves the accuracy numbers by 0.8 and 5.7 for CIFAR-10 and CIFAR-100, respectively, which verifies both the improper influence of positive scaling invariance for optimization in weight space and the benefit of optimization in G space. Moreover, Plain-34 trained by G-SGD achieves even better accuracy than ResNet-34 trained by SGD on CIFAR-10, which shows the influence of invariance on optimization in weight space as well.

5.2. THE INFLUENCE OF INVARIANCE:

In this section, we study the influence of invariance on the optimization for ReLU Networks. As proved in Section 3, the dimension of weight space is larger than G-space by H, where H is the total number of the hidden nodes in a MLP or the feature maps in a CNN. We define the invariant ratio as H/m. We train several 2-hidden-layer MLP models on Fasion-MNIST (Xiao et al., 2017) with different number of hidden nodes in each layer, and analyze the performance gap ∆ between the models optimized by G-SGD and SGD. The detailed training strategies and network structures could be found in Appendix. From Figure 4 , we can see that, 1) for each number of H, G-SGD clearly outperforms SGD on both training loss and test error, which verifies our claim that optimization loss function in G space is a better choice; 2) as H increases, the invariant ratio decreases (because m also increases for MLP) and ∆ gradually decreases as well, which provides the evidence for that the positive scaling invariance in weight space indeed improperly influences the optimization.

5.3. COMPARISON WITH PATH-SGD:

In this section, we compare the performance of Path-SGD and that of G-SGD. As described in Section As shown in Figure 5 , while Path-SGD achieves better or equally good test accuracy and training loss than SGD for both MNIST and CIFAR10 datasets, G-SGD achieves even better performance than Path-SGD, which is consistent with our theoretical analysis that considering the dependency between the paths and optimizing in G-space bring benefit.

6. CONCLUSION:

In this paper, we study the G-space for ReLU neural networks and propose a novel optimization algorithm called G-SGD. We study the positive scaling operators which forms a transformation group G and prove that the value vector of all the paths is sufficient to represent the neural networks. Then we show that one can identify basis paths and prove that the linear span of their value vectors (denoted as G-space) is an invariant space with lower dimension under the positive scaling group. We design G-SGD algorithm in G-space by leveraging back-propagation. We conduct extensive experiments to verify the empirical effectiveness of our proposed approach. In the future, we will examine the performance of G-SGD on more large-scale tasks.

APPENDIX: G-SGD: OPTIMIZING RELU NEURAL NETWORKS IN ITS POSITIVELY SCALE-INVARIANT SPACE:

The Appendix document is composed of examples of skeleton weights and basis paths for different MLP structures, proofs of propositions, lemmas and theorems and the additional information about the experiments in the paper Optimization of ReLU Neural Networks using G-Stochastic Gradient Descent . weight vector with m = L l=1 h l-1 h l for MLP w l weight matrix at layer l with size h l-1 × h l for MLP w l (i l-1 , i l )

7. NOTATIONS:

weight element in matrix w l at position 

(i l-1 , i l ) O l i l the i l -th hidden node at layer l E = {eij} the set of edges in neural network model Table 3: Index Index Range Object l {1, • • • , L} index of layer i l {1, • • • , h l } index of hidden nodes at l-layer (iL, iL-1, • • • , i0) i l ∈ [h l ], l ∈ [L] explicit index of path p P path p i {p 1 , • • • , p m-H = P0 basis path sj {s1, • • • , sH } ⊂ {1, • • • , m} free skeleton weight

, g 2 , g 3 ∈ G, it has (g 1 • g 2 ) • g 3 = g 1 • (g 2 • g 3 );

3) (unit element) there exists unit element e ∈ G, so that for any element g ∈ G, there is g • e = g; 4) (inverse element) for any element g ∈ G, there exists an inverse element g -1 ∈ G of g such that g • g -1 = e. Then, G together with the operation "•" is called a transformation group. 

[wij]i=1,••• ,m;j=1••• ,s with wij ∈ (R/{0}) as: W A =   s j=1 sgn(w 1j ) • |w 1j | aj1 • • • s j=1 sgn(w 1j ) • |w 1j | ajn • • • • • • • • • s j=1 sgn(w mj ) • |w mj | aj1 • • • s j=1 sgn(w mj ) • |w mj | ajn   ,

where

A s×n = [a jk ] i=1,••• ,s;k=1,••• ,n is a matrix with a ij ∈ R.

According to the definition, we can prove that W A A -1 = W if A is a square matrix. We use

A -1 = [ã kz ] k=1,••• ,s;z=1,••• ,s .

Then the element at the b-th row and c-th column of W A A -1 is calculated as 6) in the main paper is established.

s j=1 sgn(w bj ) • s k=1 ( s j=1 •|w bj | a jk ) ãkc = s j=1 sgn(w bj ) • s j=1 •|w bj | s k=1 a jk ãkc . When j = c,

9. PROOFS OF THEORETICAL RESULTS:

In this section, we will provide proofs of the lemma and theorems in Section 3 of the main paper. 9.1 PROOF OF THEOREM 3.3 Theorem 3.3: Consider two ReLU neural networks with weights w, w ∈ W. We have that w ∼ w iff for ∀ path p and ∀ input x ∈ X , we have vp(w) = vp(w ) and ap(w, x) = ap(w , x).

Proof: For the necessity, if w ∼ w , then there exist a positive scaling operator g(•) to make g(w ) = w. We use i l to denote the node index of nodes in layer-l and

i l ∈ [h l ]. Then we have w l (i l-1 , i l ) = 1 c l-1 i l-1 • c l i l • w l (i l-1 , i l ) for l = 2, • • • , L -1,

because each weight may be modified by the operators of its connected two nodes

EQUATION

Next we need to prove that a p (w, x) = a p (w , x) is also satisfied. Because the value of the activation is determined by the sign of o l , l = {1, • • • , L -1}, we just need to prove that

[o l w,1 (x), • • • , o l w,h l (x)] = [c l 1 • o l w ,1 (x), • • • , c l h l • o l w ,h l (x)],

where

c l i l , i l ∈ [h l ], l ∈ [L -1] are positive numbers.

We prove it by induction. (1) For o 1 of a L-layer MLP (L > 2): Suppose that σ(•) is a ReLU activation function. For the i 1 -th hidden node, we have

EQUATION

(2) For o l of the L-layer MLP (l > 2): Suppose that

[o j w,1 (x), • • • , o j w,h j (x)] = [c j 1 • o j w ,1 (x), • • • , c j h j • o j w ,h j (x)], j = {1, • • • , l -1}.

Then we have

o l w,i l = σ   h l-1 i l-1 =1 w l (i l-1 , i l )o l-1 w,i l-1 (x)   = σ   h l-1 i l-1 =1 1 c l-1 i l-1 • c l i l • w l (i l-1 , i l ) • c l-1 i l-1 • o l-1 w ,i l-1 (x)   = c l i l • o l w ,i l .

Thus we finish the proof of necessity.

For the sufficiency, we need to prove that if vp(w) = vp(w ) and ap(w, x) = ap(w , x) for ∀ path p and ∀ input x ∈ X , there exists g ∈ G to make w = g(w). First, for hidden node O 1 i1 in layer-1, we claim that their incoming weights satisfy the following relationship:

w 1 (i 0 , i 1 ) = c 1 i1 • w 1 (i 0 , i 1 ), ∀i 0 ∈ [h 0 ]. Because there exist path p z1 , • • • , p z h 0 ∈ P to make v p z 1 (w) : v p z 2 (w) : • • • : v p z h 0 (w) = w 1 (1, i 1 ) : w 1 (2, i 1 ) : • • • : w 1 (h 0 , i 1 ),

and v p (w) = v p (w ) for any p, we have

w 1 (1, i 1 ) : w 1 (2, i 1 ) : • • • : w 1 (h 0 , i 1 ) = w 1 (1, i 1 ) : w 1 (2, i 1 ) : • • • : w 1 (h 0 , i 1 ).

Then the claim is established. Then we prove each

c 1 i1 is positive. If there exist a constant c 1 i1 is negative, then o 1 i1 (w, x) = o 1 i1 (w , x). If o l i l (w, x) > 0, we have o l i l (w , x) = 0.

Here we assume that x ∈ X where X is a compact set to make that a p (w,

x) = a p (w , x), ∀p, ∀x is equivalent to sgn(o l i l (w, x)) = sgn(o l i l (w , x)), ∀x, ∀l = 1, • • • , L. Thus all the c 1 i1 for i 1 = 1, • • • , h 1 are positive. Then we use the operator g c 1 1 ,O 1 1 • • • • • g c 1 h 1 ,O 1 h 1

(w) to make the two networks with the same weights at layer 1. Then based on the networks with the same weights at layer 1, we gradually deal with the weights in other layers from layer 2 to the last layer using similar techniques as layer 1. We can finally construct g ∈ G. Thus we finish the proof of the sufficiency. 9.2 PROOF OF THEOREM 3.4 AND THEOREM 3.6

In order to prove Theorem 3.4 and Theorem 3.6, we need to prove that there exist a group of paths which are independent and can represent other paths, and the activation status can be calculated using values of basis paths and signs of free skeleton weights. In order to simplify the proof, we leverage the basis paths constructed by skeleton method. We only show the proof of the following lemma, from which we can easily get Theorem 3.4 and Theorem 3.6.

Lemma 9.1 The paths selected by skeleton method are basis paths and a p (w, x) can be calculated using signs of free skeleton weights and the values of basis paths in a recursive way.

Proof sketch: Let us consider the matrix A = (p 1 , • • • , p m-H ) composed by basis paths constructed by skeleton method:

EQUATION

There is an identity matrix with size z × z where z is the number of skip skeleton paths. This identity matrix means that w i is a non-skeleton weight and is contained in p i , i ≤ z. Thus, through the row transformation of the matrix, B 1 can be transformed to zero matrix. According to skeleton method, column vectors in B 2 are independent because skeleton weight will only appear in one all-basis path. Thus the independent property has been proved. Furthermore, by leveraging the structure of matrix A , it is easily to check that for a non-skeleton path p, it can be calculated as p = z i=1 α i p im-H j=z+1 α j p j where α i = 0 or 1 and

α j = 0, 1, 2 • • • , L -1. More specifically, if p contains w i , i ≤ z, then α i = 1; otherwise, α i = 0.

For the second statement, because the activation status is determined by all the o l i l (x), we just need to prove the sign of o l i l (x) is determined by the value of basis path vector v. For each hidden node O l i l , there exist only one basis path which passes it and only contain skeleton weights (We call the basis path which contains only skeleton weights all-basis path). We denote the value of all-basis path which passes

O l i l as v p a (O l i l ) = w 1 (O l i l ) • L j=2 w j (O l i l )

, where w j (O l i l ) denotes the skeleton weight of p a (O l i l ) at the j-th layer which is also an skeleton outgoing weight for one hidden node. We will prove o l i l (x) can be calculated as

EQUATION

where F l i l (v; x) is a function which is determined by v and the input x. If Eqn( 11) is satisfied, the sign of o l i l (x) can be determined as following:

EQUATION

Next we prove Eqn(11) by induction.

(1) For l = 1,

o 1 i 1 (x) = h 0 i 0 =1 w1(i0, i1)) • xi 0 = h 0 i 0 =1

vps (w1(i0, i1))

EQUATION

where v p s (w 1 (i 0 , i 1 ))) is the value of basis path which contains w 1 (i 0 , i 1 ) and w j (O 1 i1 ) is the outgoing skeleton weight (free skeleton weight) of O 1 i1 . It means that Eqn( 11) is satisfied with

F 1 i1 (v; x) = h0 i0=1 v p s (w 1 (i 0 , i 1 ))) • x i0 .

(

EQUATION

Thus we have finished the proof the second statement. 9.3 PROOF OF COROLLARY 3.8

Corollary 3.8 The dimension of G-space is m -H, where m is the number of weights and H is the total number of hidden nodes for MLP or the total number of feature maps for CNN.

Proof: The dimension of a mathematical space (or object) means that the minimum number of coordinates needed to specify any point within it. When the signs of free variables are fixed, the number of the variables which are used to represent the output of ReLU neural networks is m -H according to Theorem 3.4. Thus the dimension of G-space is m -H. 9.4 PROOF OF THEOREM 4.1

Theorem 4.1: Suppose that there are two different projections T 1 and T 2 that project the path-ratio to weight-ratio. If the projection will not change the signs of free skeleton weights, the values of basis paths will keep the same at every iteration for two G-SGD processes that are initialized with the same values of basis paths and use different projections T 1 and T 2 in WA method respectively.

Proof: In fact, the gradients of basis paths only depends on the values of basis paths and are independent with how the weights distribute.

Specifically, suppose that the two training processes start from the same initial point, i.e., v 0 (1) = v 0 (2) . Because the values of paths and the activation status can be calculated using values of basis paths when the signs of free skeleton weights are fixed, the loss functions can be represented using the values of basis paths. Then the neural network with equal values of basis paths will produce the same gradient of basis paths.

After one step of SGD, we have v 1

(1) = v 1 2) . Then all the path ratios are also the same, i.e., R 0

(1) (p i ) = R 0 (2) (p i ) for every basis path p i . Then we use T 1 and T 2 to project the path ratios to weight ratios. Although T

1 (R 0 (1) (p i )) = T 2 (R 0 (2) (p i ))

, the two networks are still have equal values of basis paths after the projection, which means they are still in the same equivalent class. Again, the neural network with equal values of basis paths will produce the same gradient of basis paths. So the values of basis paths will always keep the same during the G-SGD process.

10 APPENDIX INFORMATION OF THE G-SGD ALGORITHM 10.1 UPDATE RULE AND TIME COMPLEXITY OF G-SGD Suppose that p i with i = 1, • • • , z is the basis path containing one non-skeleton weight (denoted as w i ), and p j with j = z + 1, • • • , m -H is the basis path containing skeleton weights only, w j is its skeleton weights at layer 1, and w k is the free skeleton weights that are not updated.

First, according to the ICR Method, we can get the update rule of value of skeleton paths as below,

EQUATION

Combined with the weight allocation method, we can get the update rule of G-SGD as follows:

EQUATION

EQUATION

EQUATION

where r t (w j : p i ) is ratio of the skeleton weight w j at layer 1 which is contained in basis path p i .

If the free skeleton weights w k are initialized as 1, then v t j = w t j . Thus we can first calculate the path-ratio for all-basis paths:

EQUATION

According to the WA method, r t (w j : p i ) = R t (p j ). Then the update rule for different kinds of weights can be classified into the following three types

EQUATION

EQUATION

EQUATION

where r t (w j : p i ) is ratio of the skeleton weight w j at layer 1 which is contained in basis path p i , w j denotes the skeleton weight at layer 1, w i denotes the non-skeleton weight and w k denotes the free skeleton weights (the skeleton weights that not in layer 1).

The forward and backward propagation take the dominating time in both mini-batch SGD and G-SGD.

To be specific, if the mini-batch size is B, the forward and backward propagation would both take GPU server with 4 NVIDIA GTX Titan Xp GPUs and PCI switch. We show the training throughput (processing images per second) on CIFAR-10 dataset with SGD and G-SGD optimizer on different network architectures. The multi-GPU training is done by Pytorch built-in multiple GPU module torch.nn.parallel.DataParallel based on NCCL. As shown in Figure 6 , when the mini-batch size is set to 128, the training throughput of G-SGD is slightly lower than vanilla SGD by about 7%, which indicates that our implementation of G-SGD is indeed efficient.

11.2. INITIALIZATION METHOD OF SKELETON WEIGHTS:

According to our analysis in the main paper, only the signs of skeleton weights matter the optimization. Thus we need to determine the signs of skeleton weights before training process. For the absolute value of skeleton weights, we can see from section 10.1 that different absolute value of skeleton weights well determine different scale of learning rate. Although our theoretical results show that the absolute value of skeleton weights can be randomly set, we choose them to be 1 for easier learning rate tuning and robustness.

In order to verify how signs of skeleton weights influence the performance. We test the performance for various combination of signs for them on image classification task (see section 5.2). Results shows that there are no differences for them. A intuitive explanation is that the selected network model is over-parameterized and the approximation ability will not be influenced by signs of skeleton weights. For simplicity, we initialize the value of skeleton weights as 1.

11.3. OPTIMIZING 110-LAYER RESNET WITH G-SGD:

In this section, we study the optimization performance of G-SGD on deeper ResNet model with 110 layers. We employ the same training strategies on both model structures, which are detailed described in next subsection. As we can see in the Figure 7 and In previous experiment section, we extend our G-SGD to deep convolutional networks. CIFAR-10 and CIFAR-100 have been used in the experiment. We apply random crop to the input image by size of 32 with padding 4, and normalize each pixel value to [0,1]. We then apply random horizontal flipping to the image. The mini-batch size of 128 is used in this experiment. The training is conducted for 64k iterations. We follow the learning rate schedule strategy in the original paper SECTION 5.3 Path-SGD (Neyshabur et al., 2015) also notice the positive scale invariance in neural networks with linear or ReLU activation. Instead of optimizing the loss function in G-space, they use path norm as regularizer to the gradient in weight space. Meanwhile, the dependency among all paths hasn't been noted, which leads to the computation overhead of the gradient of path norm is very high. In section 5.3, we extend the experiments in (Neyshabur et al., 2015) to G-SGD on MNIST and CIFAR-10 dataset. A 5-hidden-layer MLP model is used in this experiment with 64 units in each layer. We do grid search for the learning rate of each algorithm from 1.0 × 10 -α , where α is an integer between 0 to 10. We report the best result for each algorithm. The mini-batch size of 64 is used, and the input images of gray scale are normalized to [0, 1].

:

A path vector is represented by one element in {0, 1} m , where m is the number of weights. Please check the details in Section

2.2.

For strict description of operation " ", please refer to Section 8 in Appendix.

Batch normalization is widely used in modern CNN models. Please refer to Appendix for the combination of G-SGD and batch normalization.

Figures and Tables:

Figure 1: This is a simple ReLU network with one hidden node. Suppose path values are v p 1 (w) = w1w3, v p 2 (w) = w1w4, v p 3 (w) = w2w3, v p 4 (w) = w2w4, we can see the innerdependency between them, i.e., v p 4 (w) = v p 2 (w)•v p 3 (w) v p 1 (w)

Figure 2: The weights with red color are skeleton weights.

Figure 3: Training loss and test accuracy w.r.t. the number of effective passes on PlainNet and ResNet.

Figure 4: Training loss and test error on MLPs. The invariant ratio decreases as H increases.

Figure 5: Performance of MLP models with Path-SGD and G-SGD.

Group action) If G is a group and W is a set, then a (left) group action φ G,W of G on W is a function φ G,W : G × W → W that satisfies the following two axioms (where we denote φ(g, w) as g • w): 1) (identity) e • w = w; 2) (compatibility) (g • h) • w = g • (h • w) for all g, h ∈ G and all w ∈ W. Definition 8.3 (Operation ) We define as a right group action for matrix Wm×s =

k=1 a jk ãkc = 1; otherwise, s k=1 a jk ãkc = 0. Thus we have s j=1 sgn(w bj ) • s k=1 ( s j=1 •|w bj | a jk ) ãkc = w bc ). Thus we have prove the claim: W A A -1 = W . Thus Eq.(

Figure 7: Training loss and test accuracy on 110-layer ResNet network w.r.t. the number of effective passes on CIFAR-10 and CIFAR-100 dataset.

Figure 8: Training loss and test accuracy w.r.t. the number of effective passes on CIFAR-10 dataset.

Classification error rate (%) on image classification task.

Table content: <table><tr><td/><td>C10</td><td>C100</td></tr><tr><td>Plain-34</td><td colspan="2">SGD 7.76 (±0.17) 36.41(±0.54) G-SGD 7.00 (±0.10) 30.74 (±0.29)</td></tr><tr><td>ResNet-34</td><td colspan="2">SGD 7.13 (±0.22) 28.60(±0.51) G-SGD 6.66 (±0.13) 27.74 (±0.24)</td></tr></table>



Table content: <table/>

Notations

Table content: <table><tr><td>Notations</td><td>Object</td></tr><tr><td>m</td><td>dimension of weight space</td></tr><tr><td>H</td><td>total number of hidden nodes or feature maps</td></tr><tr><td>n</td><td>total number of paths</td></tr><tr><td>m -H</td><td>total number of basis paths and dimension of G-space</td></tr><tr><td>W ⊂ R m</td><td>weight vector space</td></tr><tr><td>w = (w1, • • • , wm)</td><td/></tr></table>

Mathematical Notations Suppose that G is a set of transformations, and • is an operation defined between the elements of G. If G satisfies the following conditions: 1) (operational closure) for any two elements g 1 , g 2 ∈ G, it has g 1 • g 2 ∈ G; 2) (associativity) for any three elements g 1

Table content: <table><tr><td>Notation</td><td>Meaning</td></tr><tr><td>#</td><td>the number of</td></tr><tr><td>/</td><td>division</td></tr><tr><td>•</td><td>function composition</td></tr><tr><td colspan="2">8 SOME CONCEPTS IN ABSTRACT ALGEBRA</td></tr><tr><td>Definition 8.1 (Transformation group)</td><td/></tr></table>

, our G-SGD clearly outperforms SGD on both shallow and deep ResNet model. The best test accuracy on ResNet-110 are achieved with G-SGD on both dataset, which meets the same conclusions in Section 5.1.Please note that deeper ResNet doesn't significantly outperform shallow ResNet on CIFAR-100 dataset, which also be observed in the original ResNet paper He et al. (2016a) and the authors propose a new ResNet architecture to solve this problem in He et al. (2016b).

Table content: <table/>

Peer review (iclr2019):
 The paper proposes SGD for ReLU networks. The authors focuses on positive scale invariance of ReLU which can not be incorporated by naive SGD. To overcome this issue, a positively scale-invariant space is first introduced. The authors show the SGD procedure in that space, which is based on three component techniques: skeleton method, inverse-chain rule, and weight allocation. The basic idea, directly optimizing weight in scale invariant space, is reasonable and would be novel, and experiments verify the claim. Readability might be low slightly. Analysis about invariance group (e.g., theorem 3.6) is interesting and informative. Combining with other optimization algorithms (other than simple SGD) method would be valuable.