Year: 2019

Abstract:
It is well known that neural networks with rectified linear units (ReLU) activation functions are positively scale-invariant (i.e., the neural network is invariant to positive rescaling of weights). Optimization algorithms like stochastic gradient descent that optimize the neural networks in the vector space of weights, which are not positively scale-invariant. To solve this mismatch, a new parameter space, called path space, has been proposed for feedforward and convolutional neural networks. The path space is positively scale-invariant and optimization algorithms operating in path space have been shown to be superior than that in the original weight space. However, the theory of path space and the corresponding optimization algorithm cannot be naturally extended to more complex neural networks, like Recurrent Neural Networks (RNN) due to the recurrent structure and the parameter sharing scheme over time. In this work, we aim to construct path space for RNN with ReLU activations so that we can employ optimization algorithms in path space. To achieve the goal, we propose leveraging the reduction graph of RNN which removes the influence of time-steps, and prove that all the values of paths in the reduction graph can serve as a sufficient representation of the RNN with ReLU activations. We then prove that the path space for RNN is composed by the basis paths in reduction graph, and design a Skeleton Method to identify the basis paths efficiently. With the identified basis paths, we develop the optimization algorithm in path space for RNN models. Our experiments on several benchmark datasets show that we can obtain more effective RNN models in this way than using optimization methods in the weight space.

heading: 1 INTRODUCTION
text: Over the past ten years, ReLU activations have become increasingly popular in various types of neural networks such as Multilayer Perceptron(MLP) (Nair & Hinton, 2010; Glorot et al., 2011; Neyshabur et al., 2015a) , Convolutional Neural Networks (CNN) ((Krizhevsky et al., 2012; He et al., 2016)) and Recurrent Neural Networks (RNN) (Le et al., 2015; Neyshabur et al., 2016). Theoretical studies on the MLP and CNN with ReLU activations, particularly on its positively scale-invariant (PSI) property have also been conducted (Neyshabur et al., 2016; 2015a; Dinh et al., 2017; Meng et al., 2018). Specifically, PSI property means if the incoming weights of a hidden node (or a feature map for CNN) are multiplied by a positive scalar c, and the outgoing weights of this hidden node (or the feature map) are divided by c, the output for arbitrary input will keep unchanged. However, conventional algorithms like stochastic gradient descent optimize the neural networks in the vector space of weights, which are not positively scale-invariant. This mismatch may lead to problems during the optimization process (Neyshabur et al., 2015a; Meng et al., 2018), e.g., in an unbalanced network (i.e., the norm of incoming weights to different units have relatively large differences), the training process of vanilla stochastic gradient descent will be significantly slowed down.
To solve the above mismatch, some recent studies have been conducted on paths of ReLU neural networks (Neyshabur et al., 2015a; Meng et al., 2018). The value of a path is defined as the multiplication of weights along the path which starts from an input node, successively crosses a hidden node at every layer, and finally ends at an output node. Obviously, the value of a path is positively scale-invariant. Thus, a new parameter space, called path space, for MLP and CNN have been proposed. Path space is a vector space constituted by the values of given paths called basis paths, whose values are sufficient to calculate the output of the MLP and CNN with ReLU activations.
In a word, path space is a PSI parameter space and can sufficiently represent MLP and CNN with ReLU activation. In the work (Meng et al., 2018), an algorithm is designed to identify the basis paths for MLP and CNN. Efficient optimization algorithms in path space have also been proposed, which iteratively update the values of basis paths according to the gradient of loss with respect to basis paths. Optimizing MLP or CNN with ReLU activations in this way can achieve better performances compared with traditional optimization methods in the weight space.
However, the studies of path space especially the identification of basis paths depend on the network structure, so it cannot be naturally extended to more complex network structures, like recurrent neural network (RNN). RNN is a powerful neural network model to process sequential data and show excellent performance in various domains such as language modeling(Mikolov et al., 2010; Jozefowicz et al., 2016), machine translation(Bahdanau et al., 2014) and speech recognition (Graves et al., 2013; Miao et al., 2015). RNN with ReLU activations (abbrev. ReLU RNN) is also positively scale-invariant (Neyshabur et al., 2016). Considering the superiority of optimizing MLP or CNN with ReLU activations in their path space, the path space for RNN is worth studying.
In this work, we aim to construct path space for ReLU RNN so that we can employ the optimization algorithm in path space. Due to the recurrent structure, the paths in RNN depend on the time-steps. That means, if the sequence length of the input is not pre-given, the number of paths in RNN cannot be determined. It makes the identification of basis paths from the undetermined number of paths difficult. To handle this, we propose leveraging the reduction graph of RNN to remove the influence of time-steps and theoretically develop path space for RNN in the following three steps. First, we define paths on reduction graph, whose number is fixed and not influenced by the sequence length. Second, we prove that the paths on reduction graph can serve as a sufficient representation of the RNN with ReLU activations. Third, we define path space for RNN which is composed by the values of basis paths in the reduction graph.
Next, we design Skeleton Method to identify basis paths in reduction graph of RNN efficiently. Compared with MLP and CNN, the skeleton method for RNN needs extra steps to handle the recurrent weights. Specifically, the skeleton method for RNN contains two steps: it first identifies the basis paths in the reduction graph of RNN without recurrent weights; then it constructs the basis paths that contain recurrent weight. We prove that paths selected by Skeleton Method are basis paths, and the number of basis paths which is also the dimension of the path space is #(weights)−#(hidden nodes) in the reduction graph of RNN.
Finally, with the identified basis paths, we employ optimization algorithm in path space for RNN models, which operates update on basis paths according to the gradient of loss w.r.t basis paths. Our experiments on several benchmark datasets show that we can obtain significantly more effective RNN models in this way than using optimization methods in the weight space. It indicates that optimizing ReLU RNN in path space can solve the optimization problem brought by positively scale-invariant property and can indeed help optimization. To the best of our knowledge, our work is the first to construct the new parameter space, path space, for the RNN model and the first to optimize RNN in its path space.
The paper is organized as follows: in Section 2, we introduce the background about the path representation of ReLU RNN and related works; in Section 3, we formally define the basis path for ReLU RNN and propose using reduction graph as a tool to handle the difficulty when identifying the basis paths in ReLU RNN; in Section 4, we present our the basis path identification algorithm and the optimization algorithm in the path space; in Section 5, we show the experiment results to verify the effectiveness of our proposed algorithm; finally, we conclude this paper in Section 6.

heading: 2 BACKGROUND
text: In this section, we briefly review the path representation of recurrent neural networks with ReLU activations and the related works in this direction.

heading: 2.1 PATH REPRESENTATION OF RELU RNN
text: As shown in Figure 1, the network structure of RNN can be regarded as a directed graph G(N , E), where N = ∪tN t denotes the set of nodes and E denotes the set of edges, where
N t = {NI,(t)1 , N I,(t) 2 · · · , N H,(t) d+1 , N H,(t) d+2 , · · · , N O,(t) d+h+1, N O,(t) d+h+2 · · ·N O,(t) d+h+K} denotes the set of nodes at the t-th time-step, the superscripts I,H,O means the input, hidden and output node, respectively. Here, d, h,K denote the dimension of input, hidden nodes and output, respectively, and the superscript t denotes the time-step. In the graph G(N , E), there must be an edge between an input node and a hidden node that are at the same time step, a hidden node and an output node that are at the same time-step, and two hidden nodes whose time-steps are adjacent. A Path on the G(N , E) is defined in Definition 1. Definition 1 (Paths in RNN). A path in the recurrent neural network is defined as a list of nodes and the corresponding edges between adjacent nodes, which starts from an input node NI,(t)i0 to one output node NO,(t+s)is+1 with s ≥ 0 by successively crossing hidden nodes. Specifically, a path can be expressed as NI,(t)i0 → N H,(t) i1 → · · · → NH,(t+s)is+1 → N O,(t+s) is+2
, and there must be an edge between the adjacent nodes, where i. is the index of node along the path.
For example, the red line in Figure 1 shows an example of the paths. For simplicity, we omit the explicit expression of paths and use p to denote the index of paths in the following context. The value of a path is defined as the multiplication of the values of weights on edges contained in the path. Specifically, for an edge ek ∈ E , we use wk to denote the weight on edge ek, then the value of path p is vp = ∏ ek∈p wk.
Using W i,W o and W r to denote three weight matrices, use x(t) to denote the input and use nH,(t), nO,(t) to denote the corresponding
hidden and output values at nodes NH,(t) and NO,(t), recurrent neural network computes the output vector nO,(t) at t-th time-step by a recurrent formulation as:
nH,(t) = σ(W ix(t) +W rnH,(t−1)), (1)
nO,(t) =W onH,(t). (2)
If the activation σ(·) is ReLU, i.e., σ(z) = max(z, 0), we can get nO,(t) = W o · (W ix(t) + W rnH,(t−1)) · diag(I(nH,(t)1 > 0), · · · , I(n H,(t) h > 0)) by combining Eq.(1) and Eq.(2).
1 According to the definition of value of a path, the output of ReLU RNN can be calculated using the values of paths and its activation status as follows,
n O,(T ) k (x) = d∑ i=1 T∑ t=1 ∑ p∈PT,k,i,t vp · ap(w;x) · x(t)i , (3)
where the set PT,k,i,t consists of the paths that connects the k-th output at time-step T and the i-th input at time-step t with length T + 1 − t, vp is the value of path p, and ap(w;x) =∏ N
H,(t) i ∈p
I(nH,(t)i (w;x) > 0) is the activation status of path p.

heading: 2.2 RELATED WORKS
text: In recent years, researchers have started to conduct theoretical studies on optimization and generalization of ReLU neural network by leveraging paths instead of weights. In the aspect of generalization, the works (Neyshabur et al., 2015b; 2017; Zheng et al., 2018) show that the generalization error of feedforward ReLU network is related to the path-norm. The work (Weinan et al., 2019) also leverages the path representation to analyze the generalization error of ReLU neural networks. Except for the generalization analysis, optimization algorithms based on paths are also designed. Neyshabur, et al. propose Path-SGD algorithm, which optimizes the loss function regularized by path-norm (Neyshabur et al., 2015a; 2016). Path-SGD algorithm does not directly optimize ReLU RNN using the loss function composed by the path-represented output but optimizes the regularized loss defined in the original weight space. The work (Meng et al., 2018) proposes G-SGD algorithm to optimize the ReLU MLP and CNN directly by updating the values of paths according to the gradient of loss w.r.t basis paths. However, G-SGD is only designed for MLP and CNN. To the best of our knowledge, the path space constituted by basis paths for ReLU RNN has not been studied yet.In this paper, we will investigate the path space for RNN so that we can apply G-SGD to RNN.
1Here, diag(a1, · · · , ah) denotes a diagonal matrix whose diagonal elements are a1, · · · , ah.

heading: 3 PATH SPACE FOR RELU RNN
text: In this section, we investigate the path space, a vector space constituted by values of basis paths for ReLU RNN. We first formally define the basis paths for ReLU RNN. Then we propose using reduction graph as a tool to define the path space for ReLU RNN.

heading: 3.1 DEFINITION OF BASIS PATHS FOR RNN
text: As stated in the introduction, it has been shown in (Neyshabur et al., 2016) (cf. Theorem 1 and Figure 1) that the output of RNN is positively scale-invariant (PSI) i.e., if all the incoming weights(including the shared weights) of a hidden node are multiplied by a positive scalar c and all the outgoing weight (including the shared weights) of this hidden node are multiplied by 1/c, ReLU RNN will generate the same output for arbitrary input. Because the values of paths are also positively scale-invariant, which matches the PSI property of ReLU RNN, we are motivated to directly represent and optimize the RNN model according to the path representation (Eq.(3)).
However, we cannot directly optimize the values of all the paths by regarding each of them to be an independent parameter, because they are correlated with each other. We use Figure 1 to show an example. For simplicity, we denote the weight of the edge that connects node i and node j as wij .2 We denote the red path in Figure 1 as p1 : N I,(1) 2 → N H,(1) 3 → N H,(2) 3 → N O,(2) 6 whose value is vp1 = w23 · w33 · w36. We can show that the value of path p1 can be calculated by the values of following four paths through multiplication and division.
p2 : N I,(1) 2 → N H,(1) 3 → N O,(1) 5 vp2 = w23 · w35
p3 : N I,(1) 1 → N H,(1) 3 → N H,(2) 3 → N O,(1) 5 vp3 = w13 · w33 · w3,5
p4 : N I,(1) 1 → N H,(1) 3 → N O,(1) 6 vp4 = w13 · w36
p5 : N I,(1) 1 → N H,(1) 3 → N O,(1) 5 vp5 = w13 · w35.
It is easy to verify that
vp1 = vp2 · vp3 · vp4
(vp5) 2 . (4)
Because vp1 can be calculated using vp2 , · · · , vp5 , we only need to know vp2 , · · · , vp5 and the relation in Eq.(4) when to represent the output of RNN.
For any given recurrent neural network, we need to first investigate and decouple the correlation among their values so that we can identify a subset of paths whose values can be directly optimized. Motivated by the example, we formally define basis paths as follows.
Definition 2 (Basis Paths). A set of paths Pb are called basis paths if they satisfy the following properties: (1) for any path p ∈ P/Pb, there exists non-zero coefficient vector α = (α1, · · · , αz) to make vp(w) = ∏ j∈Pb vj(w)
αj for any w ∈ W , where z denotes the cardinal number of Pb, i.e., z = |Pb|; (2) among all the sets that satisfy property (1), Pb has the smallest cardinal number.
The first item in the definition ensures the sufficiency to use basis paths to calculate the values of other paths, and the second item ensures that the values of basis paths are independent, i.e., the values of basis paths cannot be calculated by each other. In the work (Meng et al., 2018), basis paths have been defined for MLP, however, it is no longer suitable for RNN. Here, the definition 2 for basis paths is more general and can be generalized to many kinds of network structures.

heading: 3.2 DEFINING PATH SPACE FOR RELU RNN THROUGH REDUCTION GRAPH
text: Although basis paths have been defined in the previous section, given an RNN, it is difficult to identify the basis paths because: (1) the number of paths exponentially depends on the time-steps, which is very large in general; (2) if the sequence length of input is not pre-given, the exact number of paths in RNN cannot be determined. To handle this, we study the paths in reduction graph of ReLU RNN.
Here, we give the definition of the reduction graph for RNN and show an example in the Figure 2. 2The weights are shared for all time-steps, so we don’t use the subscript of time-step t in the weight matrices.
Definition 3 (Reduction Graph). Given a directed graph of RNN, we use Gr(N r, Er) to denote its corresponding reduction graph, where N r = {NI1 , NI2 · · · , NHd+1, NHd+2, · · · , NOd+h+1, NOd+h+2 · · ·NOd+h+K} denotes the set of nodes and Er denotes the set of edges. There must be an edge between an input node and a hidden node, a hidden node and an output node and two hidden nodes, respectively. We call the edges that connect two hidden nodes as recurrent edges.
Definition 4 (Path in Reduction Graph). A path in the reduction graph for RNN is a list of nodes that satisfies the following conditions: (1) it starts from an input node and end at an output node of the reduction graph; (2) it can at most cross one recurrent edge.
According to the definition, the paths in reduction graph are classified into two categories: the paths does not contain recurrent edge denoted as NIi0 → N H i1 → N O i2 ; contain one recurrent edge denoted as NIi0 → N H i1 → N H i2 → N O i3 . Hence, the paths in reduction graph is not related to the time-steps. That means, no matter how long the sequence length of the input, the number of paths in reduction graph is fixed. The next theorem shows that the values of paths in the reduction graph are sufficient to represent RNN. Theorem 1. All the values of paths in directed graph of RNN can be calculated using the values of paths in the reduction graph of RNN through multiplication and division operators.
We put the proof of Theorem 1 in Appendix and only deliver the techniques used in the proof here. We index the trained weights as w1, · · · , wi, · · · , wm, and represent each path using an m-dimensional vector cp = (cp1, · · · , cpm) where cp satisfy vp = ∏m i=1 w cpi i . We prove that the vectors of all paths can be calculated through linear combinations of vectors of paths in reduction graph. Thus, we can get the result in Theorem 1.
We use P to denote the set constituted by all paths of RNN, Pr to denote the set constituted by paths in reduction graph and Pb to denote the set constituted by basis paths of RNN. According to Definition 2 and Theorem 1, we have Pb ⊂ Pr ⊂ P. Thus, the basis paths in the reduction graph of RNN is the basis paths of RNN model. Paths in reduction graph of RNN is totally determined by the model and not influenced by the time-steps, and as well as the basis paths.
Next, we show that basis paths are sufficient to represent the output of ReLU RNN. According to Eq.(3) and item (1) in the definition of basis paths, we only need to prove that the activation status of paths can also be determined by the values of basis paths. Theorem 2. The activation status of the paths in ReLU RNN can be calculated using the values of basis paths and the signs of the selected elements in W o if for each column in matrix W o with dimension K × h, we randomly select one element whose sign is pre-given and fixed.
Using the basis paths, we can construct a new vector space, called path space, for ReLU RNN as :
V := {v = (vp1 , · · · , vpz ) : v ∈ (R/{0}) z}, (5)
where pi, i = 1, · · · , z are the basis paths for RNN. Till now, we have defined path space for ReLU RNN and proved that path space is sufficient to represent ReLU RNN in Theorem 2. In next section, we will introduce how to optimize ReLU RNN in its path space including that how to identify basis paths for given reduction graph.

heading: 4 OPTIMIZATION ALGORITHM IN PATH SPACE FOR RNN
text: In this section, we design Skeleton Method to identify the basis paths in reduction graph of RNN efficiently. Then, we introduce the update rule of optimization algorithm in path space for RNN.
We decompose the reduction graph of recurrent neural network into two parts: the feedforward part and the recurrent edges part. The feedforward part contains all nodes in reduction graph and the non-recurrent edges, and the recurrent edges part contains only the recurrent edges.
In Skeleton Method, we first define the skeleton edges in the feedforward part and then use the skeleton edges to construct the basis paths. We prove that the paths that contains at most one non-skeleton edges are basis path.
The Skeleton Method for RNN is described in the following box.
Skeleton Method (1) For each hidden node in the feedforward part, we randomly select one edge that pointing to this hidden node and randomly select one edge that starts from this hidden node. Putting the selected edges of all hidden nodes together, all the selected edges are called skeleton edges. All other edges are called non-skeleton edges. (2) The paths that contain at most one non-skeleton edges in the feedforward part are selected into set Pb1 . (3) The paths containing only skeleton edges and one recurrent edge are selected into set Pb2 . (4) The final selected path set is Pb1 ∪ Pb2 .
We illustrate the Skeleton Method in Figure 3(b). The red edges are the skeleton edges selected in step (1). Left three basis paths are in Pb1 and the last one is in Pb2 . For the paths in Pb1 , we further denote the set constituted by paths only contain skeleton edges as Ps and the set constituted by paths contain one non-skeleton edges as Pns. In the following theorem, we prove that the paths selected by Skeleton Method are basis paths. Theorem 3. The set of paths Pb1 ∪Pb2 selected by the Skeleton Method are basis paths. The number of basis paths (or equivalently the dimension of the path space) for recurrent neural networks is #(weights)−#(hidden nodes), where “#” means “the number of”.
After identifying the basis path using Skeleton Method, we aim to optimize the loss function L(v) by following the negative direction of the gradients of loss w.r.t basis paths as below,
vt+1pi = v t pi − ηt ·
∂L(v)
∂vpi ∣∣ v=vtpi , (6)
where pi is the index of the basis paths. G-SGD algorithm has been designed in work (Meng et al., 2018), which can efficiently implement the above update rule in path space for MLP. Here, we apply G-SGD to RNNs. Due to space limitation, we only introduce the high-level idea as below and the update rule in Alg. 2. For more details about its derivation, please refer to the Appendix B.1. or Eq.(4) and Eq.(5) in (Meng et al., 2018).
First, we construct mask matrices to distinguish the skeleton edge and non-skeleton edge according to step (1) in skeleton method. As shown in Alg.1, it generates mask matrices M i,Mo which have the same size with W i and W o, respectively, and using elements 1 and 0 in the mask matrices to denote skeleton and non-skeleton edge, respectively. Second, G-SGD calculates the gradient w.r.t basis path by using the fact that the value of basis path is multiplication of weights on this path. So it first calculates the gradient w.r.t weights (Line 3-4 in Alg.2) and then using the relation between paths and weights to obtain the gradients w.r.t basis paths Gps , Gpons and Gprns where footnotesizeps ∈ Ps, pons ∈ Pns, prns ∈ Pb2 (Line 6 in Alg.2). This step is called Inverse-Chain-Rule. Third, after updating the basis paths according to Eq.(6), it calculates the ratio Ri = vt+1pi /v t pi for pi ∈ Ps. Fourth, it allocates the ratio to weights to obtain new weights (Line 9-10 in Alg.2) in order to implement forward process in next iteration3. Detailed derivation can be referred to Appendix B.1.
3Operations such as shape(·), zero like, .sum(0) in Alg. 1 and 2 is similar to the function in the numpy packages of python language. The exact definition are listed in Appendix B.2.
Algorithm 1: Mask-Matrix-Constructor Input: weight matrices of RNN model W i,W o M i = zeros like(W i), Mo = zeros like(W o) ; n out = shape(W i)[0] ; n in = shape(W i)[1] ; for j = 1 to n out do
M i[j][j % n in ] = 1 ; end n out = shape(W o)[0] ; n in = shape(W o)[1] ; for j = 1 to n in do
Mo[j][j % n out ] = 1 ; end Output: Mask Matrix M i,Mo
Algorithm 2: G-SGD for RNN Input: RNN model FRNN (W i,W r,W o), data X,Y , loss function loss func, learning rate η
1 M i,Mo = Mask-Matrix-Constructor(W i,W o ) ; 2 repeat 3 Sample a batch of data x, y, compute the loss function loss = loss func(FRNN (x), y) ; 4 Using Back-Propagation to compute the gradient w.r.t the weight:
GW i , GWr , GWo = BP (loss,W i,W r,W o) ;
5 ### Using Inverse-Chain-Rule to obtain the gradient w.r.t basis paths: 6 Gps = GW i − (Wr·GWr ).sum(0)+(Wo·GWo ).sum(0) (W i·Mi).sum(0) ; Gpons = GWo Wo ; Gprns = GWr Wr ; 7 ### Calculate the Update Ratio: R = 1− η · Gps (W i·Mi).sum(0) ; 8 ### Weight-Allocation and update weight matrices as: 9 W i =W i · diag(R) + (W i − η ·GW i) · (1−M i);
10 W o =W o ·Mo + Wo−η·
Gpons Wi
diag(R) · (1−Mo); W r =
Wr−η· Gprns Wi
diag(R)
11 until stopping criterion is met; Output: Weights of RNN model W i,W r,W o
Computational Cost Analysis. (1)The Mask-Matrix-Calculator(Algorithm 1) only run once at the beginning. So the extra cost can be ignored. (2)As shown in the Algorithm 2, the forward and backward phase in G-SGD for RNN is the same as traditional SGD algorithm (Line 3- 4). The extra computational cost is in Inverse-Chain-Rule and Calculate the update ratio(Line 5-7). Please note that we only need to calculate the ratio R for basis paths in Ps whose number equals to the number of hidden nodes, which is small compared with the number of weights. Thus the computational cost of step 5-10 is much less than the backward process. In realistic experiments, the extra time cost is less than 10% compared to vanilla SGD. We list the running time of each algorithm in Appendix(Tab. 4).
Remark: The skeleton method and the update rule of G-SGD can be generalized to stack RNN and recurrent convolutional neural networks (RCNN), which can be referred to Appendix. Besides, according to Definition 2, the selection of basis paths is not unique. Every selection can serve as a sufficient representation of the model. Skeleton Method only provides one selection of them. In this work, we employ G-SGD based on this fixed selection. For other selections, the update rule of G-SGD can also be derived similarly.

heading: 5 EXPERIMENT
text: In this section, we verify the effectiveness of the optimization algorithms in path space for ReLU RNN. We train ReLU RNN on several tasks and show that we can obtain significantly more effective RNN models in path space than using conventional optimization methods in the weight space. Specifically, we take vanilla SGD and Path-SGD (Neyshabur et al., 2016) to be our baselines.

heading: 5.1 SEQUENTIAL MNIST
text: In this section, we optimize the ReLU RNN for the Sequential MNIST (LeCun, 1998; Neyshabur et al., 2016; Le et al., 2015; Arjovsky et al., 2015; Bai et al., 2019). In Sequential MNIST, each digit image is reshaped into a sequence, turning the digit classification task into a sequence classification task
with long-term dependencies. To make the task even harder, we also use a fixed random permutation on the pixels of the MNIST digits.
MNIST dataset is download from the official site (LeCun). The sequence length is set to 28 and 98. The hidden nodes size of ReLU RNN are 100. We search the best learning rate in a reasonable range. The size of minibatch is 64. More detailed experimental settings can refer to the Appendix A.1.
Every experiment is run 3 times with different random seeds. The averaged test accuracy is shown in the Table 1. It can be observed that the classification error rates of G-SGD algorithm on the tasks are significantly lower than that of Path-SGD and SGD. It indicates that optimizing RNN with ReLU activations in the path space can consistently obtain more effective RNN models for all settings.

heading: 5.2 LANGUAGE MODELING
text: In this section, we optimize the stacked ReLU RNN for the language modeling tasks (Merity et al., 2018) with four datasets: word-level Penn Treebank(PTB) dataset (Marcus et al., 1993), Wikitext-2 dataset (Merity et al., 2016), character-level Penn Treebank(PTBc) dataset (Merity et al., 2016) and Hutter Prize(enwik8) dataset (Hutter, 2012). The first two datasets are word level and the last two datasets are character level. For all tasks, we train a stacked ReLU RNN with 4 layers. The learning rate is turned in the range {10, 7.5, 5, 2.5, 1, 0.75, 0.5, 0.1}. Performance is evaluated using the perplexity (PPL) metric for the word level datasets and bits-per-character (BPC) metric for the character level datasets. The detailed experiment settings including the description of the datasets and hyper-parameters are put into the Appendix A.2.
The results are shown in Figure 4. The perplexity of G-SGD algorithm on the PTB and Wikitext-2 datasets are lower than that of Path-SGD and SGD. The bits-per-character metric of G-SGD algorithm on the PTB-c and enwik8 data sets are significantly lower than that of Path-SGD and SGD. It means that G-SGD are more effective than Path-SGD and SGD, which shows the superiority of optimization RNN with ReLU activations in the path space.

heading: 5.3 RECURRENT CONVOLUTIONAL NEURAL NETWORK
text: In this section, we optimize the Recurrent CNN(RCNN) for the image classification tasks(Liang & Hu, 2015). The model structure is similar to the RNN. The main difference is that the full connection in RNN is replaced by convolution layer. 4
We evaluate the algorithms on three benchmark image classification datasets, MNIST(LeCun & Cortes, 2010), CIFAR-10 and CIFAR-100 (Krizhevsky & Hinton, 2009). For CIFAR-10 and CI-
4Path-SGD algorithm is not implemented to CNN in its original papers (Neyshabur et al., 2015a; 2016), and it is not clear how to extend it to CNN. Thus we do not use Path-SGD as a baseline for experiments on RCNN.
FAR100, we use (96,128,160) feature maps. Since MNIST is much easier, we use (32, 64, 96) feature maps. In general, We follow the experiment setup in (Liang & Hu, 2015). Most of the hyper-parameters is same as previous work such as the network structure, weight decay, scheduling of learning rate, etc . The detailed experiment setting is put in Appendix A.3.
Table 2 shows the test classification error rate. We can see that optimizing RCNN in path space outperforms the conventional optimization algorithms SGD that in weight space consistently.

heading: 6 CONCLUSION
text: In this paper, we construct a new parameter space, called path space, for the RNN with ReLU activations and employ optimization algorithms in path space on benchmark experiments. To achieve this, we propose reduction graph method to deal with the difficulty brought by the parameter-sharing scheme, and propose a new Skeleton Method to identify the basis path for RNN in reduction graph efficiently. We conduct several experiments to verify that we can obtain significantly more effective RNN models in path space than using conventional optimization methods in the weight space. We would like to highlight the following conclusions: (1) Basis paths are crucial in the ReLU RNN. We have proved that the values of basis paths serve as a sufficient representation of ReLU RNN. Compared with the weights, the values of basis paths are positively rescaling-invariant, which match the PSI property of the output of ReLU RNN. Moreover, the number of basis paths is even less than the number of weights of the recurrent neural network. (2) Reduction graph is a powerful tool. Reduction graph and its paths are introduced to simplify the identification of basis paths in ReLU RNN. It is a novel technique specially designed for RNN models. (3) Optimizing ReLU RNN in path space is efficient. The algorithm G-SGD can achieve better performances than SGD with only a little extra computational cost. In the future, we will investigate the power of path view on other neural network structures such as LSTM and Transformer.

heading: APPENDIX

heading: A EXPERIMENT SETTINGS
text: All the experiments are implemented by the Pytorch framework. And all the experiments run in the Nvidia GPU.

heading: A.1 SEQUENTIAL MNIST EXPERIMENT
text: The MNIST dataset is downloaded from the official site and then normalized by subtracting the mean value and then dividing the standard deviation of the training set. The procedure is standard and the same as many code-base. The permutation dataset is constructed by generating a random permutation of the index of each pixel(from 1 to 784) before the preprocessing procedure and then fix the random permutation during the train and test phases.
In the experiments, we use a single-layer RNN with ReLU activation. The number of the hidden node is set to 100. The size of minibatch is 64. We search the best learning rate in the range of {0.1, 0.05, 0.01, 0.05, 0.001, 0.005, 0.0001, 0.0005, 0.00001}. Each experiment runs for 400 epoch. We do not use any regularization term.
The code of this experiment is based on pytorch RNN official examples(Pytorch (2019)). The implementation of Path-SGD is adapted from the code released by the author(Neyshabur (2019)).

heading: A.2 LANGUAGE MODELING EXPERIMENT
text: The first two datasets are word level. The PTB dataset consists of 929K training words, 73K validation words, and 82K test words. It has 10k words in its vocabulary. Wikitext-2 is roughly twice the size of PTB dataset, with 2 million training words, 218k validation words, 245k test words and a vocab size of 33k. The last two datasets are character level. The PTBc dataset consists of 5017k training character, 393k validation character, and 442k test character. It has 50 alphabets in its vocabulary. The enwik8 dataset has 100M characters from Wikipedia with an alphabet size of 27. We split 90M characters for training set, 5M characters for validation set and 5M test set.
For all tasks, we train a stacked ReLU RNN with 4 layers. The embedding size is 400 and the hidden size is 1550. The learning rate is turned in the range {10, 7.5, 5, 2.5, 1, 0.75, 0.5, 0.1}. The weight decay is turned in the range { 1e-5, 1e-6, 1e-7 }. According to the (Merity et al. (2018; 2017)), we use dropouts for the input, hidden and output layer. Also, we employ weight drops. We run 750 epochs for PTB, Wikitext-2 and PTB-c experiments and run 100 epochs for enwik8 experiment which is enough for the convergence of all experiments. We identify the basis path for the RNN modules of the model and optimize the RNN modules in its PSI-space using G-SGD algorithms. Similarly, Path-SGD is also implemented in the RNN modules. Other parameters are optimized using traditional SGD algorithms. Hyperparameters are list in the Table 3
Performance is evaluated using the perplexity (PPL) metric for the word level datasets and bits-percharacter (BPC) metric for the character level datasets. The code of this experiment is adapted from the Salesforce Language Model Toolkit(salesforce (2019)).
The implementation is based on the Salesforce Language Model Toolkitsalesforce (2019) and we only change the optimizer.

heading: A.3 RECURRENT CNN EXPERIMENT
text: The CIFAR-10, CIFAR-100 and MNIST datasets are downloaded from the official site and then normalized by subtracting the mean value and dividing the standard deviation of the training set. The code of this experiment is based on this repository (Github, 2019) which is consistent with the previous paperLiang & Hu (2015).
The RCNN network has 5 layers. There is one RCNN block in each layer and each RCNN block unfolds 3 times. As many recent code-base suggested, we using BN hear instead of LRN(Github, 2019; 2018) and removing dropout layers except the last linear layer (Github, 2019). We show all the testing error rate in the table 4.
The initial learning rate of both baseline and our method is searched in then range { 0.5, 0.2, 0.1, 0.07, 0.05, 0.01 } and then divided by 10 after 1/2, 3/4 and 7/8 epoch of all epochs. Momentum parameter is set to 0.9. Weight decay is set to 0.0001. Dropout rate is set to 0.5. Batch size is 64. Each experiment is run for 200 epoch and the test accuracy of the last epoch is reported.

heading: B ALGORITHMS

heading: B.1 DERIVATION OF THE ALGORITHM
text: In this section, we review the process of Inverse-Chain-Rule and Weight-Allocation designed in the work Meng et al. (2018) and apply it to RNN.
Denote the non-skeleton weight as wns and the skeleton weight as ws. We select the skeleton weight in the first layer as special skeleton weights and denote as ws0 and the non-skeleton weight in this layer is denoted as wns0 . Denote all the basis path set as Pb. Denote the basis path that pass the non-skeleton weight wns as pns and the basis path that compose by all-skeleton weight and pass the skeleton weight ws0 as ps0 . Note that there is a 1-1 mapping between non-skeleton weights and the basis paths in set Pns. Similarly, there is also a 1-1 mapping between skeleton weights ws0 and the basis paths in set Ps0 . Here, for simplicity, we can view recurrent weight as a non-skeleton weight wns. Thus Pb2 ∈ Pns. Inverse-chain-rule calculates the gradient with respect to basis paths according to the following equation:
( ∂L
∂w1 , · · · , ∂L ∂wm
) = ( ∂L
∂vp1 · · · ∂L ∂vpm−H
) ·  ∂vp1 ∂w1 · · · ∂vp1∂wm ... . . . ...
∂vpm−H ∂w1 · · · ∂vpm−H∂wm  (7) By solving this equation, the gradients w.r.t basis paths can be derived as:
For vpns we have: ∂L
∂vpns =
∂L ∂wns / ∂vpns ∂wns .
For vps0 we have:
∂L
∂vps0 =
∂L
∂ws0 −
∑ p∈Pb/ps0 ∂L ∂wns wns
ws0 .
We write the result into matrix manipulation forms and we can derive line 6 in Algorithm 2 in the main paper. The detailed derivation is put at the end of this section for clarity.
Weight-Allocation projects the update on basis paths back to the update of weight. Notation Cs0 is the production of weights in path ps0 except for ws0 . Specifically, vps0 = ws0 ·Cs0 . Notation Dns is the production of weights in path pns except for wns. Specifically, vpns=wns·Dns . We have:
vtps0 − η ∂L
∂vtps0 vtps0 = vt+1ps0 vtps0 , R(vtps0 ) = wt+1s0 · C t+1 s0 wts0 · Cts0 (8)
vtpns − η ∂L
∂vtpns vtpns = vt+1pns vtpns , R(vtpns) = wt+1ns ·Dt+1ns wtns ·Dtns
(9)
Solving this equation, the update rule for weight can be derived as:
wt+1s0 = w t s0 ·R(v t ps0 ) (10)
wt+1ns = wt − ηt · ∂L∂vtpns /v t ps0
R(vtps0 ) (11)
wt+1ns0 = w t ns0 − ηt ·
∂L
∂wtns0 (12)
We write the result into matrix manipulation forms and we can derive line 9-10 in Algorithm 2 in the main paper. The detailed derivation is put at the end of this section for clarity.
We give the derivation details in the following:
According to the chain rule, we have:
∂L ∂wns = ∑ p∈Pb ∂L ∂vp · ∂vp ∂wns = ∂L ∂vpns · ∂vpns ∂wns
(13)
∂L ∂ws0 = ∑ p∈Pb ∂L ∂vp · ∂vp ∂ws0 = ∂L ∂vps · ∂vps ∂ws0 + ∑ p∈Pb/ps ∂L ∂vp · ∂vp ∂ws0
(14)
According to the skeleton method, each non-skeleton weight wns can only exists in one basis path pns. Besides, if wns not in p,
∂vp ∂wns = 0 Thus Eq. (13) is right Thus, we can derive the gradient of the basis path as:
∂L
∂vpns =
∂L ∂wns / ∂vpns ∂wns
(15)
∂L
∂vps0 =  ∂L ∂ws0 − ∑
p∈P/ps0
∂L ∂vp · ∂vp ∂ws0  /∂vps0 ∂ws0
(16)
Let s[ws0 ] = ∑ p∈P/ps0 ∂L ∂vp · ∂vp∂ws0 . We can then calculate the update ratio for the basis paths as:
R(vtps0 ) , vt+1ps0 vtps0 = 1− ηt
∂L ∂vtps0 vtps0 = 1− ηt( ∂L ∂wts0 − s[ws0 ])/( ∂vtps0 ∂wts0 · vtps0 ) (17)
R(vtpns) , vt+1pns vtpns = 1− ηt ∂L ∂vtpns vtpns = 1− ηt ∂L ∂wtns /( ∂vtpns ∂wtns · vtpns) (18)
(19)
Above equation is right according to the gradient decent update rule of the path value vt+1p = vtp − ηt · ∂L∂vtp Finally, we project the new basis path value into the weight. Notation Cs0 is the production of weights in path ps0 except for ws0 . Specifically, vps0 = ws0 ·Cs0 . Notation Dns is the production of weights in path pns except for wns . Specifically, vpns = wns ·Dns.
wt+1s0 wts0 · Ct+1s0 Cts0 = vt+1ps0 vtps0
(20)
wt+1s = R(v t ps0 ) · wts0 · Cts0 Ct+1s0
(21)
wt+1ns wtns · D t+1 ns Dtns = vt+1pns vtpns
(22)
wt+1ns = R(v t pns) · w t ns · Dtns Dt+1ns
(23)
Eq. (20) and ( 22 ) is the definition of the basis path. Note that we only update the skeleton weight in the special layer ws0 and the non-skeleton weight wns. Therefore, Cts0 Ct+1s0 = 1. For the non-skeleton weight in the special layer, D t ns
Dt+1ns = 1. For the non-skeleton weight not in the special
layer, D t ns
Dt+1ns = 1/R(vtps0 ).

heading: B.2 NOTATIONS EXPLANATION IN THE ALGORITHM

heading: B.3 COMPUTATIONAL COST
text: Here, we provide the training time per epoch of our algorithm and the baselines in Table 6. We implement all experiments on a single GPU. It shows that the real training time of G-SGD is also comparable with that of plain SGD.

heading: B.4 STACK RNN AND CONVOLUTIONAL LAYER
text: For stack RNN, there are multiple layers of hidden nodes. Specifically, there are more than one Wh and W r. Note that the skeleton method is also held. Thus the Mask-Matrix-Constructor algorithms can also be applied by generating mask matrix for all the weight matrix Wh according to the skeleton method.
For convolutional layer, we view one feature map as a hidden node as in MLP structure. So we select one of the edges in the convolutional kernel that connect two feature maps in two layers as the skeleton weights. Thus the Mask-Matrix-Constructor algorithms can construct the mask matrix by selecting one element in one convolutional weight matrix that connects one input feature maps and one output feature maps as 1.

heading: C PROOF OF THEOREMS

heading: C.1 PROOF OF THEOREM 1
text: To ease the presentation of the proof, we give the path a vector representation as follows. We index the edges in the reduction graph of neural network as e1, · · · , ei, · · · , em. We define the counting vector for a path p either in the directed graph or in the reduction graph as Cp = (cpe1 , · · · , cpem ), where cpei is equal to the times that path p passes the edge ei. Please note that, if path p is in the directed graph, cpei may be larger than 1 for some i because of weight sharing. Theorem 1 is proved if we show the counting vector of any path in the directed graph is a linear combination of the counting vectors of the paths in the reduction graph.
Consider an arbitrary path in the directed graph with counting vector Cp = (cp1, · · · , cpm). For each edge ei, we choose a path in reduction graph that contains this edge, which is denoted as p(i) and its counting vector is Cp(i). We claim that the term ∑ ei∈p cpi · Cp(i) − Cp equals to the linear combination of counting vectors of paths in reduction graph. Without loss of generality, we suppose that p contains nodes and edges N I1 e1→ NH2 e2→ · · · ek→ NOk+1, where e1 is the edge connecting an input node and a hidden node and ek is the edge connecting a hidden node and an output node, and other edges are recurrent edges. For edge ej , j = 3, · · · , k − 1, we choose a path N Iij eij→ NHj−1 ej→ NHj
ezj→ NOzj that contains ej , where ij denotes the index of selected edge in the input-to-hidden layer for ej and zj denote the index of selected edge in the hidden-to-output layer for ej . For edge ej−1, we choose a path N Iij−1 eij−1→ NHj−2 ej−1→ NHj−1 ezj−1→ NOzj−1 that contains ej−1. Furthermore, for the edge e1, we select an edge connecting with e1 at the hidden-to-output layer, denoted as ez1 . And for the edge ek, we select an edge connecting with ek at the input-to-hidden layer, denoted as eik . We claim that the edge eij and edge ezj−1 compose a path in reduction graph because they both connect node NHj−1. This claim is right for all j = 2, · · · , k. Thus the linear combination of the paths that contain eij and ezj−1 equals to ∑ ei∈p cpi · Cp(i) − Cp.
Here, we use the example in Figure 5 to illustrate the above formulation. There are five weights in Figure 5, denoted as (w1, w2, w3, w4, w5). Consider the path N I,(1) 1 → N H,(1) 3 → N H,(2) 3 → N H,(3) 3 → N H,(4) 3 → N O,(4) 4 whose counting vector is Cp = (1, 0, 3, 1, 0). It can be calculated as Cp = 1 · (1, 0, 0, 1, 0) + 3 · (1, 0, 1, 1, 0) + 1 · (1, 0, 0, 1, 0) − 4 · (1, 0, 0, 1, 0), where (1, 0, 0, 1, 0) and (1, 0, 1, 1, 0) are paths in the reduction graph.

heading: C.2 PROOF OF THEOREM 2
text: Recall the definition of the activation status ap(w;x) = ∏ NH,ti ∈p
I(NH,ti (w;x) > 0), We will first prove that every indicator function of the node can be calculated by the values of paths. Then using the definition of the basis paths we can know that the values of paths can be calculated using the values of basis paths. Combine the conclusion above, we can prove the theorem.
Denote the weights connect the node with index i and the node with index j as W iij , consider the hidden node NH,(t)j , we define the value of the node as the sum of all incoming value before the activation and denote it using lower case letter oH,(t)j . Formally, the value of the hidden node is
o H,(t) j = ∑ i W ijix (t) i + ∑ j′ W rjj′o H,(t−1) j′ I(o H,(t−1) j′ > 0)
where x(t)i is the input node of time-step t and o H,(t−1) j′ is the pre-activated hidden output of time-step t − 1. The corresponding weights W iji and W rjj′ is in the W i and W r respectively the same as the notations in preliminaries. For simplicity, we denote the activation status of nodes as a(o
H,(t) j ) , I(o H,(t) j > 0) where I is the indicator function. We use notation sign(·) to denote the sign function(sign(a) = 1 if a > 0 and sign(a) = −1 if a < 0) We prove the theorem by using the induction method. Specifically, we will prove that the value of hidden node can be expressed by the following formulation. And thus the activation of the hidden node can be calculated by the value of path and the sign of skeleton weights in matrices W o, which we call it outgoing skeleton weight and denote it as ws.
o H,(t) j = F (x, vp, sign(ws)) ·
1
W okj , (24)
where F (x, vp, sign(ws)) is a function that only related on the input x, values of paths vp and the signs of outgoing skeleton weights ws. W okj is also an outgoing skeleton weight that connect to the hidden node oHj and o O k .
Firstly, we prove Equation 24 is satisfied in time-step 1. For an arbitrary hidden node with index j
o H,(1) j = ∑ i W ijix (1) i = 1 W okj W okj ∑ i W ijix (1) i
= 1
W okj ∑ i x (1) i · vNI,(1)i →NH,(1)j →NO,(1)k
= F (x, vp) · 1
W okj
= F (x, vp, sign(ws)) · 1
W okj
Then, using induction method, the induction assumpution is that ot−1 can be represented by the function of path value divided by the weights on the skeleton edges,
o H,(t−1) j′ = F (x, vp, sign(ws)) ·
1
W ok′j′
Then, we can get:
o H,(t) j =
1
W okj W okj · ∑ i W ijix (t) i + ∑ j′ W rjj′o H,(t−1) j′ a(o H,(t−1) j′ )  = 1
W okj ∑ i x (t) i · vNI,(t)i →NH,(t)j →NO,(t)k + ∑ j′ W okjW r jj′o H,(t−1) j′ a(o H,(t−1) j′ )  = 1
W okj ∑ i x (t) i · vp N I,(t) i →NH,(t) j →NO,(t) k + ∑ j′ W okj W ok′j′ W rjj′F (x, vp, sign(ws))a(o H,(t−1) j′ )  = 1
W okj
( F (x, vp, sign(ws)) +
∑ j′ F (x, vp, sign(ws))I ( sign(W okj) · F (x, vp, sign(ws))
))
= 1
W okj F (x, vp, sign(ws))
The second term in third equality is from the induction assumption. The fourth equality is the definition of activation function. It is obvious that for arbitrary functions F (x, vp, sign(ws)), W okj W o
k′j′ W rjj′F (x, vp, sign(ws)) is also a function of input, value of paths and the sign of weight on skeleton edges. The reason is that the paths in function F both contain the weight WOk′j′ . And an arbitrary value of path in RNN multiplies the weight on the recurrent edge is also the value of a path.
So we prove that if the equation 24 is satisfied in time-step t− 1, it will also be satisfied in time-step t. And the equation is proved through the induction method.
Next, recall the definition of the activation status of paths: ap(w;x) = ∏ NH,ti ∈p I(oH,ti (w;x) > 0). By using Equation (24), we can know that the sign of oH,(t)j can be calculated using the value of basis paths given the sign of weights on skeleton edges. Combine it with that the value of path can be calculated by the value of basis path, we can easily prove the theorem.

heading: C.3 PROOF OF THEOREM 3
text: As we mentioned, the structure of ReLU RNN can be decomposed into a feedforward part and the recurrent edges part. For the feedforward part, the number of basis paths has been proved to be #(weights)−#(hidden nodes) in Meng et al. (2018). According to our Skeleton Method for RNN, each recurrent weight can only be contained in one basis paths. Thus, the total number of recurrent neural networks is #(weights of MLP)+#(recurrent weights)−#(hidden nodes). Thus, we finish the proof.

heading: D TESTING ACCURACY CURVES FOR VISION TASKS
text: D.1 SEQUENTIAL MNIST

heading: D.2 RECURRENT CNN
text: E ADDITIONAL G-ADAM V.S. ADAM EXPERIMENT RESULTS ON SEQUENTIAL MNIST EXPERIMENTS

Review summaries:
This paper aims to improve the training of recurrent neural networks (RNN) with ReLU activations by optimizing in the path space instead of the weight space. Studies on multi-layered perceptrons (MLP) and convolutional neural networks (CNN) have shown that these architectures are positively scale invariant (PSI), however traditional SGD optimizes in the weight space that does not have this property. It has been shown in prior work that this mismatch can slow down the optimization process for SGD and it has been demonstrated that optimizing in the so called path space, which has the PSI property, can be faster and more efficient.  The authors of this paper aim to extend an existing path-space framework (G-SGD) that is used for ReLU networks to facilitate RNNs.  To tackle the challenge posed by the time-dependency of RNNs, they use a static representation, called reduction graph, to define the path space. First, they prove that any path in the original RNN graph can be easily obtained from paths in its reduction graph by simple operations. Then, they define the basis for the path space in the reduction graph, and show that basis paths are sufficient to represent the output of the RNN. They propose a method (Skeleton method) to generate a basis path in the reduction graph and specify an equivalent of the G-SGD algorithm for RNNs.  Through numerical simulations they demonstrate that (1) G-SGD for RNNs has a fairly low additional computational cost compared to SGD and (2) G-SGD for RNNs achieves better test accuracy compared with SGD and an additional path space based approach.

This paper proposes a parameter space, called path space for RNNs with ReLU activation. For the construction of the path space, this paper utilises a reduction graph approach to minimise the difficulty brought by the parameter-sharing scheme in RNNs. Furthermore, the authors propose a Skeleton method for the efficient identification of basis path for RNNs in reduction graph.