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

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.

heading: 1 INTRODUCTION
text: 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. ∗The notation ∗ denotes equal contribution. †This work was done when the author was visiting Microsoft Research Asia.
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.

heading: 2 BACKGROUNDS

heading: 2.1 RELATED WORKS
text: 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
1A 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.
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.

heading: 2.2 RELU NEURAL NETWORKS
text: Let Nw(x) : X → Y denote a L-layer multi-layer perceptron (MLP) with weight w ∈ W ⊂ Rm, the input space X ⊂ Rd and the output space Y ⊂ RK . In the l-th layer (l = 0, · · · , L), there are hl nodes. It is clear that, h0 = d, hL = K. We denote the il-th node and its value as Olil and o l il
, respectively. We usewl to denote the weight matrix between layer l−1 and layer l, and use wl(il−1, il) to denote the weight connecting nodes Ol−1il−1 and O l il
. The values of the nodes are propagated as ol = σ((wl)T ol−1), where σ(·) = max(·, 0) is the ReLU activation function. We use (i0, · · · , iL) to denote the path starting from input feature node O0i0 to output node O L iL
passing though hidden nodes O1i1 , · · · , O L−1 iL−1 .
We can also regard the network structure as a directed graph (O, E), whereO = {O1, · · · , OH+d+K} is the set of nodes where H denotes the number of hidden nodes and E = {eij} denote the set of edges in a network where eij denotes the edge pointing to Oj from nodes Oi. We use we, e ∈ E to denote the weight on edge e. If |E| = m, the weights compose a vector w = (w1, · · · , wm)T . We define a path as a vector p = (p1, · · · , pm)T and if the edge e is contained in path p, pe = 1; otherwise pe = 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 vp(w) = ∏m i=1 w pi i and the activation status of path p can be calculated as ap(x;w) =∏
j:peij=1 I(oj(x;w) > 0). We denote the set composed by all paths as P and the set composed by paths which contain edge connecting the i0-th input node and the k-th output node as Pi0,k. Thus, the output can be computed as follows:
Nkw(x) = d∑ i0=1 ∑ p∈Pi0,k vp(w) · ap(x;w) · xi0 . (1)

heading: 3 POSITIVELY SCALE-INVARIANT SPACE OF RELU NETWORKS
text: 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.

heading: 3.1 POSITIVE SCALING TRANSFORMATION GROUP
text: 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̃ = gc,Olil (w),
where w̃l(il−1, il) = c · wl(il−1, il) for il−1 = 1, · · · , hl−1; w̃l+1(il, il+1) = 1c · w l+1(il, il+1) for il+1 = 1, · · · , hl+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(c1,··· ,cH )(·) :W →W with c1, · · · , cH ∈ R + is defined as
g(c1,··· ,cH )(·) := gc1,O1 ◦ gc2,O2 ◦ · · · ◦ gcH ,OH (·),
where ◦ denotes function composition.
We then collect all the g(c1,··· ,cH )(·) together to form a set G := {g(c1,··· ,cH )(·) : 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 onW 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 Nw and Nw′ 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 onW , the equivalence relation "∼G" partitionsW 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.

heading: 3.2 POSITIVELY SCALE-INVARIANT SPACE AND ITS DIMENSION
text: v p1
(w)
. A is the structure matrix of this
example.
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 vp4(w) = v p2 (w)·v p3 (w)
v p1
(w) .
Using the vector representation of paths that is described in section 2.2, we find that their path vectors follow the relationship p4 = p2 + p3 − p1, 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 P0 = {p1, · · · , pm−H} which is a subset of P is called a set of basis paths if p1, · · · , pm−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 ws1 , · · · , wsH 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 ∈ P0, 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 = (vp1 , · · · , vpm−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.
4 ALGORITHM: G-SGD
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 WeightAllocation (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).

heading: 4.1 SKELETON METHOD
text: 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 w2, · · · , wL−1, we select diagonal elements to be the skeleton weights. For weight matrix w1, we select the element w1(i1 mod d, i1) for column i1 with i1 = 1, · · · , h1 to be the skeleton weights. For weight matrix wL, we select the element wL(iL−1, iL−1 mod K) for row iL−1 with iL−1 = 1, · · · , hL−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 vpi , and iteratively update the model by
vt+1 pj = vtpj − ηt ∂l(v;St)
∂vpj
∣∣∣ v=vt , j = 1, · · · ,m−H, (2)
where St 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.

heading: 4.2 INVERSE-CHAIN-RULE (ICR) METHOD
text: 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) ∂vp1 , · · · , ∂l(v;x, y) ∂vpm−H ) ·
 ∂v p1 ∂w1 · · ·
∂v p1
∂wm · · ·
∂v pm−H ∂w1 · · · ∂v pm−H ∂wm  (3) We first compute the gradients w.r.t. weights, i.e., ∂l(w;x,y)
∂wi 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) ∂vj 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.

heading: 4.3 WEIGHT-ALLOCATION (WA) METHOD
text: 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 pj at iteration t as Rt(pj) := vtpj/v t−1 pj and the weight-ratio of wi at iteration t as rt(wi) := wti/wt−1i . Assume that we have already obtained the path-ratio for all the basis paths Rt+1(pj) 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 pj = ∏m i=1 w pji i Because we have vpj (w) = w pj , the weight-ratios obtained after the projection should satisfy the following relationship: Rt(pj) = rt(w) pj . Generalize the operator from vectors to matrices 2, we have the following relationship:
(Rt(p1), · · · , Rt(pm−H)) = (rt(w1), · · · , rt(wm)) A′, (4)
where the matrix A′ = (p1, · · · , pm−H). According to this relationship, we design Weight-Allocation Method to project the path-ratio to weight-ratio as described below. Suppose that w1, · · · , wH are the free skeleton weights. We first add H elements with value 1 at the beginning in vector (Rt(p1), · · · , Rt(pm−H)) to get a new m-dimensional vector. Then we append H columns in matrix A′ to get a new matrix Ã as Ã = [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(Ã) = m and we have the following relationship:
(1, · · · , 1, Rt(p1), · · · , Rt(pm−H)) = (rt(w1), · · · , rt(wm)) Ã. (5)
We can get the weight-ratio by Ã−1 on both sides of Eq.(5). Because we have (rt(w1), · · · , rt(wm)) Ã Ã−1 = (rt(w1), · · · , rt(wm)) (refer to Section 8 in Appendix), we have
(rt(w1), · · · , rt(wm)) = (1, · · · , 1, Rt(p1), · · · , Rt(pm−H)) Ã−1. (6)
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, Ã 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 T1 and T2 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 T1 and T2 in WA method respectively.
Algorithm 1 G-SGD Require: initialization w0, learning rate ηt, training data set D.
1. Construct skeleton weights using skeleton method and construct Ã−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)
∂wi ∣∣ w=wt
. 3. Calculate ∂l(v;x,y)
∂v pj for j = 1, · · · ,m−H according to Eqn.(3). 4. Using SGD to update the values of basis paths: vt+1
pj = vtpj − ηt · ∂l(v;x,y) ∂v pj .
5. Calculate path-ratios: Rt(pj) = vt+1 pj /vtpj . 6. Calculate weight-ratio rt(wi) using Ã−1 according to Eqn.(6). 7. Update the weights as wt+1i = w t i · rt+1(wi).
end for Ensure: wT .
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.

heading: 5 EXPERIMENTS
text: 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.

heading: 5.1 DEEP CONVOLUTIONAL NETWORK
text: In this section, we apply our G-SGD to image classification tasks and conduct experiments on CIFAR10 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 Table 1, our G-SGD clearly outperforms SGD on each network and each dataset. To be specific, 1) both the lowest training loss and best test accuracy are achieved by
2For strict description of operation " ", please refer to Section 8 in Appendix. 3Batch normalization is widely used in modern CNN models. Please refer to Appendix for the combination
of G-SGD and batch normalization.
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.

heading: 5.2 THE INFLUENCE OF INVARIANCE
text: 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.

heading: 5.3 COMPARISON WITH PATH-SGD
text: In this section, we compare the performance of Path-SGD and that of G-SGD. As described in Section 2.1, Path-SGD also consider the positive scaling invariance, but 1) instead of optimizing the loss function in G-space, Path-SGD regularizes optimization by path norm; 2) Path-SGD ignores the dependency among the paths. We extend the experiments in Neyshabur et al. (2015) to G-SGD
without unbalance initialization, and conduct our studies on MNIST and CIFAR-10 datasets. The detailed training strategies and description of network structure can be found in Appendix.
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.

heading: 6 CONCLUSION
text: 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.

heading: ACKNOWLEDGMENTS
text: This work is partially supported by National Center for Mathematics and Interdisciplinary Sciences (NCMIS).

heading: 8 SOME CONCEPTS IN ABSTRACT ALGEBRA
text: Definition 8.1 (Transformation group) 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 g1, g2 ∈ G, it has g1 ◦ g2 ∈ G; 2) (associativity) for any three elements g1, g2, g3 ∈ G, it has (g1 ◦ g2) ◦ g3 = g1 ◦ (g2 ◦ g3); 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.
Definition 8.2 (Group action) If G is a group andW is a set, then a (left) group action φG,W of G onW 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 = [wij ]i=1,··· ,m;j=1··· ,s with wij ∈ (R/{0}) as:
W A =  ∏sj=1 sgn(w1j) · |w1j |aj1 · · · ∏sj=1 sgn(w1j) · |w1j |ajn· · · · · · · · ·∏s j=1 sgn(wmj) · |wmj |aj1 · · · ∏s j=1 sgn(wmj) · |wmj |ajn , where As×n = [ajk]i=1,··· ,s;k=1,··· ,n is a matrix with aij ∈ R.
According to the definition, we can prove that W A A−1 = W if A is a square matrix. We use A−1 = [ã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 ∏s j=1 sgn(wbj) · ∏s k=1( ∏s j=1 ·|wbj | ajk )ãkc = ∏s j=1 sgn(wbj) · ∏s j=1 ·|wbj | ∑s k=1 ajkãkc .
When j = c, ∑s k=1 ajkãkc = 1; otherwise, ∑s k=1 ajkãkc = 0. Thus we have ∏s j=1 sgn(wbj) ·∏s
k=1( ∏s j=1 ·|wbj |
ajk )ãkc = wbc). Thus we have prove the claim: W A A−1 = W . Thus Eq.(6) in the main paper is established.

heading: 9 PROOFS OF THEORETICAL RESULTS
text: In this section, we will provide proofs of the lemma and theorems in Section 3 of the main paper.

heading: 9.1 PROOF OF THEOREM 3.3
text: 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 il to denote the node index of nodes in layer-l and il ∈ [hl]. Then we have wl(il−1, il) = 1
cl−1il−1
· clil ·w ′ l(il−1, il) for l = 2, · · · , L− 1, because each weight may be modified by
the operators of its connected two nodes gcl−1il−1 ,O l−1 il−1 and gclil ,O l il
. Thus vp(w) = vp(w′) is satisfied
because
vp(w ′) = L∏ l=1 w′l(il−1, il) = c 1 i1w ′ 1(i0, i1) · ( L−1∏ l=2 1 cl−1il−1 · clilw ′ l(il−1, il)· ) · 1 cL−1iL−1 w′L(iL−1, iL) (7)
= L∏ l=1 wl(il−1, il) = vp(w). (8)
Next we need to prove that ap(w, x) = ap(w′, x) is also satisfied. Because the value of the activation is determined by the sign of ol, l = {1, · · · , L− 1}, we just need to prove that
[olw,1(x), · · · , olw,hl(x)] = [c l 1 · olw′,1(x), · · · , clhl · o l w′,hl(x)],
where clil , il ∈ [hl], l ∈ [L− 1] are positive numbers. We prove it by induction.
(1) For o1 of a L-layer MLP (L > 2): Suppose that σ(·) is a ReLU activation function. For the i1-th hidden node, we have
o1w,i1 = σ ( h0∑ i0=1 w1(i0, i1)xi0 ) = σ ( h0∑ i0=1 c1i1 · w ′ 1(i0, i1)xi0 ) = c1i1 · σ ( h0∑ i0=1 w′1(i0, i1)xi0 ) = c1i1 · o 1 w′,i1 .
(9)
(2) For ol of the L-layer MLP (l > 2): Suppose that
[ojw,1(x), · · · , o j w,hj (x)] = [cj1 · o j w′,1(x), · · · , c j hj · ojw′,hj (x)], j = {1, · · · , l − 1}.
Then we have
olw,il = σ  hl−1∑ il−1=1 wl(il−1, il)o l−1 w,il−1(x)  = σ  hl−1∑ il−1=1 1 cl−1il−1 · clil · w ′ l(il−1, il) · cl−1il−1 · o l−1 w′,il−1 (x)  = clil · o l w′,il .
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 O1i1 in layer-1, we claim that their incoming weights satisfy the following relationship:
w′1(i0, i1) = c 1 i1 · w1(i0, i1),∀i0 ∈ [h0].
Because there exist path pz1 , · · · , pzh0 ∈ P to make vpz1 (w) : vpz2 (w) : · · · : vpzh0 (w) = w1(1, i1) : w1(2, i1) : · · · : w1(h0, i1),
and vp(w) = vp(w′) for any p, we have
w1(1, i1) : w1(2, i1) : · · · : w1(h0, i1) = w′1(1, i1) : w′1(2, i1) : · · · : w′1(h0, i1). Then the claim is established. Then we prove each c1i1 is positive. If there exist a constant c 1 i1
is negative, then o1i1(w, x) 6= o 1 i1 (w′, x). If olil(w, x) > 0, we have o l il
(w′, x) = 0. Here we assume that x ∈ X where X is a compact set to make that ap(w, x) = ap(w′, x),∀p,∀x is equivalent to sgn(olil(w, x)) = sgn(o l il
(w′, x)),∀x, ∀l = 1, · · · , L. Thus all the c1i1 for i1 = 1, · · · , h1 are positive. Then we use the operator gc11,O11 ◦ · · · ◦ gc1h1 ,O1h1 (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.

heading: 9.2 PROOF OF THEOREM 3.4 AND THEOREM 3.6
text: 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 ap(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′ = (p1, · · · , pm−H) composed by basis paths constructed by skeleton method:
A′ = ( I 0 B1 B2 ) (10)
There is an identity matrix with size z × z where z is the number of skip skeleton paths. This identity matrix means that wi is a non-skeleton weight and is contained in pi, i ≤ z. Thus, through the row transformation of the matrix, B1 can be transformed to zero matrix. According to skeleton method, column vectors in B2 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 αip i − ∑m−H j=z+1 αjp
j where αi = 0 or 1 and αj = 0, 1, 2 · · · , L− 1. More specifically, if p contains wi, i ≤ z, then αi = 1; otherwise, αi = 0.
For the second statement, because the activation status is determined by all the olil(x), we just need to prove the sign of olil(x) is determined by the value of basis path vector v. For each hidden node Olil , 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 Olil as vpa(O l il ) = w1(O l il ) · ∏L j=2 wj(O l il
), where wj(Olil) denotes the skeleton weight of pa(Olil) at the j-th layer which is also an skeleton outgoing weight for one hidden node. We will prove olil(x) can be calculated as
olil(x) = 1∏L
j=l+1 wj(O l il ) · F lil(v;x), (11)
where F lil(v;x) is a function which is determined by v and the input x. If Eqn(11) is satisfied, the sign of olil(x) can be determined as following:
sgn(olil(x)) = sgn(wl+1(O l il)) · · · sgn(wL(O l il)) · sgn(F l il(v;x)). (12)
Next we prove Eqn(11) by induction.
(1) For l = 1,
o1i1(x) = h0∑ i0=1 w1(i0, i1)) · xi0 = h0∑ i0=1 vps(w1(i0, i1))∏L j=2 wj(O 1 i1 ) · xi0 = 1∏L j=2 wj(O 1 i1 ) h0∑ i0=1 ps(w1(i0, i1))) · xi0 ,
(13)
where vps(w1(i0, i1))) is the value of basis path which contains w1(i0, i1) and wj(O1i1) is the outgoing skeleton weight (free skeleton weight) of O1i1 . It means that Eqn(11) is satisfied with F 1i1(v;x) = ∑h0 i0=1 vps(w1(i0, i1))) · xi0 . (2) For l > 1, suppose that ol−1il−1(x) = 1∏L
j=l wj(O l−1 il−1
) · F l−1il−1(v;x),
olil(x) = hl−1∑ il−1=1 wl(il−1, il) · ol−1il−1 (14)
= hl−1∑ il−1=1 vps(wl(il−1, il))∏ j=l+1 wj(O l il ) · ol−1il−1 (15)
= hl−1∑ il−1=1 vps(wl(il−1, il))∏L j=l+1 wj(O l il ) · w1(Ol−1il−1) · ∏l−1 j=1 wj(O l−1 il−1 ) · 1∏L j=l wj(O l−1 il−1 ) · F l−1il−1(v;x) (16)
= 1∏L
j=l+1 wj(O l il ) hl−1∑ il−1=1
vps(wl(il−1, il))
w1(O l−1 il−1 ) · ∏l−1 j=1 wj(O l−1 il−1 ) · 1∏L j=l wj(O l−1 il−1 ) · F l−1il−1(v;x) (17)
= 1∏L
j=l+1 wj(O l il ) hl−1∑ il−1=1 vps(wl(il−1, il)) vpa(O l−1 il−1 ) · F l−1il−1(v;x) (18)
= 1∏L
j=l+1 wj(O l il ) · F lil(v;x). (19)
Thus we have finished the proof the second statement.

heading: 9.3 PROOF OF COROLLARY 3.8
text: 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 .

heading: 9.4 PROOF OF THEOREM 4.1
text: Theorem 4.1: Suppose that there are two different projections T1 and T2 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 T1 and T2 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., v0(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 v1(1) = v 1 (2). Then all the path ratios are also the same, i.e., R0(1)(p i) = R0(2)(p
i) for every basis path pi. Then we use T1 and T2 to project the path ratios to weight ratios. Although T1(R0(1)(p i)) 6= T2(R0(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 pi with i = 1, · · · , z is the basis path containing one non-skeleton weight (denoted as wi), and pj with j = z + 1, · · · ,m −H is the basis path containing skeleton weights only, wj is its skeleton weights at layer 1, and wk 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,
vt+1i = v t i − ηt
δtwi · w t i
vti (20)
vt+1j = v t j − ηt
wtj · (δtwj − ∑ pi:wj δtvi · vti wtj )
vtj (21)
Combined with the weight allocation method, we can get the update rule of G-SGD as follows:
wt+1j = w t j − ηt ·
δtwj · (w t j) 2 − wtj · ∑ pi:wj δwti · w t i
(vtj) 2
(22)
wt+1i = wti − ηt ·
δtwi ·(wti) 2
(vti) 2
rt(wj : pi) , (23)
wt+1k = w t k, wk 6= wi, wj (24)
where rt(wj : pi) is ratio of the skeleton weight wj at layer 1 which is contained in basis path pi.
If the free skeleton weights wk are initialized as 1, then vtj = w t j . Thus we can first calculate the path-ratio for all-basis paths:
Rt(pj) = vt+1j vtj = 1− ηt wtj · (δtwj −
∑ pi:wj δtvi · vti wtj ) (vtj) 2 = 1− ηt δtwj − ∑ pi:wj δtvi · vti wtj wtj . (25)
According to the WA method, rt(wj : pi) = Rt(pj). Then the update rule for different kinds of weights can be classified into the following three types
wt+1j = w t j ·Rt(pj) (26)
wt+1i = wti − ηt ·
δtwi ·(wti) 2
(vti) 2
rt(wj : pi) , (27)
wt+1k = w t k, wk 6= wi, wj (28)
where rt(wj : pi) is ratio of the skeleton weight wj at layer 1 which is contained in basis path pi, wj denotes the skeleton weight at layer 1, wi denotes the non-skeleton weight and wk 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
BT time. Comparing with SGD, the extra computation is the calculation of Rt(pj), which the time complexity is independent with the mini-batch and is equal to the update step in SGD. Thus the time complexity of G-SGD is upper bound by O((B + 1)T ). Please see the training throughput of our experiments on GPU server in Section 11.1.

heading: 10.2 SKELETON METHOD FOR RESNET AND ICR METHOD FOR BATCH NORMALIZATION
text: For ResNet, we implement the skeleton method to construct skeleton weights and basis paths in each residual block. Because of the skip-connection, there is an identity weight which doesn’t change during the optimization. Thus, if the skip-connected weight connects node O, there isn’t a positive scaling operator gO,c ∈ G to make w ∼ gO,c(w). So we can’t construct basis paths for the whole network. The invariance of ResNet only exists in each residual block. In this sense, the equivalence of invariance is less severe than other neural network structure.
Because of the existence of the batch-normalization layers, the output of neural network with BN is ôij l = olij−µj√ σ2j+ , where olij means the j-th output in layer-l which is calculated using the i-th
sample, µj = 1b ∑b i0=1 olij is the expectation of oij , i = 1, · · · , b and σ2j = 1b ∑b i=1(o l ij − µj)2 is the variance. Assume that olij = w l jo l−1 i and the inputs o l−1 i has expectation 0 and variance 1 (It can be roughly satisfied for neural networks with BN.), we have σ2j ≈ ‖wlj‖2. If we define the value of a path as vw(p) = ∏L l=1 wl(il−1,il)
‖wlil‖ where wlil denotes the incoming weight vector of node O l il . Thus
the loss function of the NN with BN layers can be approximately represented as l(v;x, y).
Thus inverse-chain-rule for NN with BN layer can be approximated by the following equations. If w is an incoming weight of node O, we have
∂l(w;x, y)
∂wl(il−1, il) ≈ z1∑ i=1 ∂l(v;x, y) ∂vi · ∂vi ∂wl(il−1, il) · 1 ‖wlil‖ , (29)
which results in
∂l(w;x, y)
∂wl(il−1, il) · ‖wlil‖ ≈ z1∑ i=1 ∂l(v;x, y) ∂vi · ∂vi ∂wl(il−1, il) . (30)
Then we use the above equation in the ICR methods.

heading: 11 APPENDIX INFORMATION OF THE EXPERIMENTS
text: 11.1 TRAINING THROUGHPUT OF G-SGD
We implement our G-SGD using the Pytorch framework with v0.31 stable release, and conduct our experiments comparing with Pytorch built-in SGD optimizer. Our experiments are conducted on a
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.

heading: 11.2 INITIALIZATION METHOD OF SKELETON WEIGHTS
text: 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 Table 5, 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).

heading: 11.4 DETAILED TRAINING STRATEGIES IN SECTION 5.1 AND 11.2
text: In previous experiment section, we extend our G-SGD to deep convolutional networks. CIFAR10 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
(He et al., 2016a), specifically, the initial learning rates of vanilla SGD and G-SGD are set to 1.0 and then divided by 10 after 32k and 48k iterations. The ResNet implementation can be found in https://github.com/pytorch/vision/ and the models are initialized by the default methods in PyTorch.
11.5 THE COMBINATION OF G-SGD AND REGULARIZATION
The optimization algorithms achieve better generalization performance on test dataset by combining with proper regularization methods. In the previous experiments, we focus on the difference performance of optimization algorithms. In this section, we conduct the experiments to investigate the combination of G-SGD and regularization. In weight space, weight norm is widely used as regularization for ReLU networks (He et al., 2016a; Huang et al., 2017). Recently, (Zheng et al., 2018) propose the basis path norm in G-space. In this section, we reproduce the experiments in (He et al., 2016a; Zheng et al., 2018) on SGD regularized by weight norm (SGD+WD) and G-SGD regularized by basis path norm (G-SGD+BPR), and extend them on CIFAR-100 dataset. The learning rate of 1.0 is widely used to train ResNet model and its variants on CIFAR dataset, hence we employ it in our experiment as well. We do a wide range grid search for the hyper-parameter λ for weight decay and basis path regularization from {0.1, 0.2, 0.5} × 10−α, where α ∈ {3, 4, 5, 6}, and report the best performance based on the CIFAR-10 validation set. We use the same hyper-parameter on CIFAR-100 dataset.

heading: 11.6 DETAILED TRAINING STRATEGIES IN SECTION 5.2
text: In this section, our aim is to verify the influence of invariance to optimization in weight space. We train several 2-hidden-layer MLP models with different invariant ratio (i.e. H/m) on Fasion dataset. The original size of input image is 28 × 28. We normliazed the input data, and to reduce the dimensions of input feature, we downsample the image to 7× 7 by using average pooling. The network structue is followed by [49:h:h:10] where h is the number of hidden nodes in each layer. The detailed model properties are shown in table 6. All models are initialized by (He et al., 2015) except the skeleton weights which is mentioned in Section 4 without explicit note. We use the learning rate of 0.01 and mini-batch size of 64 for vanilla SGD and G-SGD, and train each model for 100 epochs.
As shown in Figure 8 and 9, the G-SGD achieves clearly better performance than SGD with combining regularization method on all models and all datasets. To be specific, the test accuracy of 94.29% is gained by ResNet-34 trained by SGD and weight decay on CIFAR-10 dataset (the number reported in (He et al., 2016a) is 91.25%), while G-SGD with basis path regularization improves the test accuracy to 94.67%. On CIFAR-100 dataset, the test accuracy of ResNet-34 trained by SGD and weight decay is 74.39% (the ResNet-34 result on CIFAR-100 hasn’t been reported in He et al. (2016a), a result of ResNet-110 with similar training strategy on this dataset is reported in Zagoruyko & Komodakis (2016) which is 74.84%), while G-SGD with basis path regularization improves the test accuracy to 75.20%. The experimental results verify our analysis again that optimization in G-space is a better choice.

heading: 11.7 DETAILED TRAINING STRATEGIES IN SECTION 5.3
text: 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].

Review summaries:
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.

In prior deep learning papers it has been observed that ReLU networks are positively scale invariant due to the non-negative homogeneity property of the max(0, x) function. The present paper proposes to change the optimization procedure so that it is done in a space where this invariance is preserved (in contrast to the weight space, where it is not). To do so, the authors define the group G of positive scaling operators, and note that the "value of path" (product of weights along the path) is G-invariant and together with "activation status of paths" allows for the definition of an equivalence class. They then build a G-space which has fewer dimensions than the weight space, and proposed g-SGD to optimize the network in this space. In g-SGD gradients are computed normally, then projected to G-space via a sparse matrix in order to update the values of paths. The weights are then updated based on a "weight allocation method" that involves the inverse projection.