Path Space for Recurrent Neural Networks with ReLU Activations
Authors: Yue Wang
Qi Meng
Wei Chen
Yuting Liu
Zhi-Ming Ma
Tie-Yan Liu
Venue:  (2020)
Keywords: optimization
neural network
positively scale-invariant
path space
deep learning
RNN

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 whose paths 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 \emph{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 significantly more effective RNN models in this way than using optimization methods in the weight space. 

Under review as a conference paper at ICLR 2020
PATH SPACE FOR RECURRENT NEURAL NETWORKS WITH RELU ACTIVATIONS
Anonymous authors Paper under double-blind review
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, 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 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 sufficient representation of the RNN with ReL.U 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 obtain more effective RNN models in this way than using optimization methods in the weight space.
complex neural networks, like Recurrent
INTRODUCTION
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., 201 1; 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). Thcoretical studies on the MLP and CNN with ReLU activations, particularly on its positively ocale-invariant (PSI) property have also been conducted (Neyshabur et al., 2016; 2015a; Dinh 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 positive scalar c, and the outgoing weights of this hidden node (or the feature map) are divided by 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 during the optimization process (Neyshabur et al., 2015a; Meng 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.
This mismatch may lead to problems
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 input node, successively crosses hidden node at every layer, and finally ends at an output node. Obviously, the value of a path is positively scale-invariant Thus, 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 sufficient calculate the output of the MLP and CNN with ReL.U activations.

---

Under review as a conference paper at ICLR 2020
In 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 ReLUU 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 mooellnng(Mikolov et al., 2010; Jozefowiez et al., 2016), machine translation (Bahdanau traansatiionBahddnnau 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, 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 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 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 # (riggtts)#(hhideee 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 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 ReL.U RNN and propose using reduction graph 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.
tool to handle the difficulty when identifying the
2 BACKGROUND
In this section, we briefly review the path representation of recurrent neural networks with ReLU activations and the related works in this direction.
2.1 PATH REPRESENTATION OF RELU RNN
As shown in Figure 1, the network structure of RNN can be regarded as a directed graph G(N,E), where N U.V' denotes the set of nodes and & denotes the set of edges, where
2

---

Under review as a conference paper at ICLR 2020
V = [NV .N2 _ No N442 ,.... NN No.00 N44h42 < denotes the set of nodes at the f-th time-step, the superscripts H. O means the input, hidden and output node, respectively. Here, d, h, K denote the dimension of imput. hidden nodes and output, respectively, and the super- script t denotes the time-step. In the graph G(N,E) E), there must be an edge between an input node and hidden node that are at the same time step, a hidden node and output node that same time-step, and two hidden nodes whose time-steps are adjacent. A Path on the G(N,E) is defined in Definition I.
...
the
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 imput node NI. to one output node (o.tt)))) with 8 z 0 by successively crossing hidden nodes. Specifically, path can be expressed as N2110) - -N - ... + io41
NO,(tts), and there must be an edge between the x.H.((++) - 2,42
adjacent nodes, where i, is the index of node along the path.
For example, the red line in Figure shows an example of the paths. For simplicity, we omit the explicit expression of paths and use 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 eą E E, we use wy. to denote the weight on edge eg. then the value of path is Up- - Ileppp W'k-
N
N
Ny
NA
Ny w
N
Time- Time-step&ee e 1,
Using W W and V to denote three weight matrices, use (:(1) to denote the input and use n n,,,( 0t to denote the corresponding hidden and output values at nodes N=,(()) and NO.0), recurrent neural network computes the output vector n 0.00 at f-th time-step by recurrent formulation as:
Figure I: DAG of RNN
n H.(0) = (" W n (,((-1),
(1)
n 0,11) = w'n (7(0))
(2)
If the activation o(.) is ReLU, ie.. o(2) max 0), can get n.00 = w (W +
W" (T"nh.(t-2)) diag(T(n) (.()) > O).... I(m H,04 0)) by combining Eq.(1) and (2) Accord-
ing 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,
(x) ΣΣ Σ Up ap x) xi
(3)
PEPT.A...
where the set Pr, consists of the paths that connects the k-th output at time-step T and the i-th input at time-step with length T' + 1 - t, Up is the value of path p, and ap(w; II No Ep I(n H,(0) (w: > 0) is the activation status of path p.
2.2 RELATED WORKS
In recent years. researchers have started to conduct theoretical studies on optimization and generaliza- tion 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 parh (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) 8) proposes G-SGD) algorithm to optimize the ReL.U MI.P and CNN directly by updating the values of paths according to the gradient of loss w.r. 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 In this paper, we will investigate the path space for RNN so that we can apply G-SGD to RNN.
Here, diag(a1," --. .a) denotes diagonal matrix whose diagonal elements are "1:".' ah.
3

---

Under review as a conference paper at ICLR 2020
3 PATH SPACE FOR RELU RNN
In this section, we investigate the path space, 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 tool define the path space for ReLU RNN.
3.1 DEFINITION OF BASIS PATHS FOR RNN
As stated in the introduction, it has been shown in (Neyshabur et al., 2016) (cf. Theorem I and Figure 1) that the output of RNN is positively scale-invarian (PST) i.e., if all the incoming weightsg the shared weights) of a hidden node are multiplied by a positive scalar e 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 (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 to show an example. For simplicity, we denote the weight of the edge that connects node i and node j as way. We denote the red path in Figure I as No - .1: + N/ + NoO.22) whose value is Upp W23 W33 Was. We can show that the value of path p1 can be calculated by the values of following four paths through multiplication and division.
P2: ..) - NM + No.(")
Upp W23
Ps N (.1) + N3 N + NN NO
U/3 W13 W33 W3,5
P4 ( + (N + (..11
Up4 W13
-136
ps N (.) + N.H.0)) + NO.11)
Ups W/3 1135-
It is easy to verify that
Up Ups
Upp
Up1
(4)
(Ups)
Because Up, can be calculated using Up ... Ups we only need know " Ups and the relation in (4) when to represent the output of RNN.
For any given recurrent neural network, we need first investigate and decouple the correlation among their values so that we can identify 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 Po are called basis paths if they satisfy the following properties: (1) for any path p E PP/Pb, there exists non-zero coefficient vector a = (a1,,... ax2) to make (w) = IIyer, ( for any w E W. where 2 denotes the cardinal number of Ps. i.e., z iPol: (2) among all the sets that satisfy property (1), Ps 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.
3.2 DEFINING PATH SPACE FOR RELU RNN THROUGH REDUCTION GRAPH
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.
"The weights are shared for all time-steps, so we don't 't use the subscript of time-step in the weight matrices.
4

---

Under review as a conference paper at ICLR 2020
N
Definition (Reduction Graph). Given directed graph of RNN, we use G" (N ET) " denote its corresponding reduction graph, where N (Nf, No N s+1; N2-.. 2--.".... N2-h+1, N2+h+2 N d+ denotes the set of nodes and e" denotes the set of edges. There must be an edge between input node and hidden node, hidden node and an output node and two hidden nodes, respectively. We call the edges that connect two hidden nodes as recurrent edges.
w
W
N
W
Ni
Figure 2: Reduction Graph of RNN
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 an output node of the reduction graph; (2) 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 No N NN2 contain one recurrent edge denoted as No + N + N + No.- Hence, the paths in reduction graph is not related to the time-steps. That means, graph is fixed. The next theorem shows that the values of paths in the reduction graph are sufficient to represent RNN.
matter how long the sequence length of the input, the number of paths in reduction
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 - Wi, -... Wm. and represent each path using m-dimensional vector C = (Cpl. ... Cpms where ep satisfy U = -I wfri 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, P. to denote the set constituted by paths in reduction graph and Pd to denote the set constituted by basis paths of RNN. According to Definition 2 and Theorem 1, we have Pe C P. 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 (3)(3) and item (1) in the definition of basis paths, we only need 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 for each column in matrix W with dimension K x h we randomly select one element whose sign is pre- pre-given and fixed.
Using the basis paths, we can construct new vector space, called path space, for ReLU RNN
V = (v (UpLy" ... :pp.): vE (R/{0)))*
(5)
where ps, 1, 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.
OPTIMIZATION ALGORITHM IN PATH SPACE FOR RNN
In this section, 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.
5

---

Under review as a conference paper at ICLR 2020
N
N
0g
Feedforward Part
Recurrent Edges Part
P.
Piu Piu
Pa
W3
W4
04
Rasis
W2
Wa
N
N2
(a)
(b)
Figure 3: (a) An example of reduction graph.
(b) An example of Skeleton Method
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-ske oon-skeleton edges.
(2) The paths that contain at most one non-skeleton edges in the feedforward part are selected into set Pby
(3) The paths containing only skeleton edges and one recurrent edge are selected into set Pig.
(4) The final selected path set is Pb, U Pbg.
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 Ps, and the last one is in Poz. For the paths in Po., we further denote the set constituted by paths only contain skeleton edges as P, and the set constituted by paths contain one non-skeleton edges as Pas.
In the following theorem, we prove that the paths selected by Skeleton Method are basis paths.
Theorem 3. The set of paths Ph, UP,, 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 optimize the loss function L(v) by following the negative direction of the gradients of loss w.r.t basis paths below,
aL(v)
Upp
7pp
D0p:
(6)
PL
where p 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 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.I. or (4) and (5) in (Meng et al., 2018).
First, we construct mask matrices to distinguish the skeleton edge and non-skelo non-skeleton edge according to step (1) in skeleton method. As shown in Alg. it generates mask matrices M' M which have the same size with W and W respectively, and using elements and 0 in the mask matrices to denote skeleton and non non-skeleton edge, respectively. Second, G-SGD calculates the gradient w.n.t basis path by using the fact that the value of basis path is multiplication of weights on this path. So 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 Gp., Gpe. and Gp.. where footnotesizep, E P.. Phs Pns.P'r. E Po, (Line Alg.2). This step called Inverse-Chain Rule. Third, after updating the basis paths according to (6) it calculates the ratio R. up. 1+4 /vf, for ps E P.. 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 iteration Detailed derivation can be referred to Appendix B.I.
Operations such as shope(-), sero_like, hik.olikk...smmfff.. sum(0) in Alg. 1 and 2 is similar to the function in the numpy packages of python language. The exact definition listed in Appendix B.2.

---

Under review as a conference paper at ICLR 2020
Algorithm 1:
Input: weight matrices of RNN model W W M' zeros )ike(W"),
M ceros_iik((W")
out = shape(W"") [0] m. sha)e
for j 1 to out do
M Mil % n.in 1= end
n_out ww
niin =_inn
for j = to n_in do
Mijllj n out |=1]
end
Output: Mask Matrix M1, M
Algorithm 2: G-SGD for RNN
Input: RNN model FRNN W Wo), data X, Y, loss function loss_func, learning rate
M .M Maasi-Mariix-- Matria- Constructor W
2 repeat
3 Sample batch of data x, compute the loss function loss = (oss
Using Back Poek-Prrppgation to compute the gradient w.r. the weight:
Gws, Gw-, Gw = P(loss, W W", W
### Using (W" (y""CGrr (0) - -Gy (0w))(0)
to obtain the gradient w.r.t basis paths:
Gp, Gwy
Gys, Gur
Gps.
Gwr
(W seum(()
7 #*# Calculate the Update Ratio: R 2011- 11 M sumn
### Weight-Allocation and update weight matrices
W = W diag( R + (W T Gw:)
M));
10 W W M + W
(1 Mº): W w Pig
dsagtR)
dieg.R) R)
until stopping criterion met; Output: Weights of RNN model W WT, W
Computational Cost Analysis. (1)The
1) only run once 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 that we only need calculate the ratio R for basis paths in P. 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(Tabe 4),
Chain-hhhll and Calculate the update ratio(Line 5-7). Please note
The skeleton method and the update rule of G-SGD can be generalized stack RNN and recurrent convolutional neural networks (RCNN), which can be referred to Appendix. Besides, according 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.
Remark:
5 EXPERIMENT
In this section, we verify the effectiveness of the optimization algorithms in path space for ReLU RNN. We train ReLU RNN several tasks and show that can obtain significantly more effective RNN models in path space than using conventional optimization methods in the weight space. Specifically, take vanilla SGD and Path-SGI (Neyshabur et al., 2016) be baselines.
5.1 SEQUENTIAL MNIST
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 sequence, turning the digit classification task into sequence classification task
7

---

Under review as a conference paper at ICLR 2020
with long-term dependencies. To make the task even harder, also use fixed random permutation on the pixels of the MNIST digits.
MNIST dataset is download from the official site (LeCun). The sequence length is set 28 and 98. The hidden nodes size of ReLU RNN are 100. We search the best learning rate a reasonable range. The size of minibatch is 64. More detailed experimental settings
refer the Appendix A.1.
Every experiment is run 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 significantly lower than that of Path-SGD and SGD. It indicates that optimizing RNN with ReLU activations in the path space consistently obtain more effective RNN models for all settings.
Table I: Averaged testing classification error rate(%) of the sequential MNIST experiment.
G-SGD
SGD
Path-SGD
S.NIST-28
1,50 = 0.03
1,59 0.06
1.75# 0.03
Non-Perman PenPutemttaionn
sMNIST-98
2.70 +: 0.09
3.07 1007:00 0.18
2.9911 0.08
S.NIST-28
3.80 0.09
4.19= 0.13
4.12 : 0.24
Permutation
MMNIST-98
5,42 0.05
5.70= 0.16
5,47= 0.03
5.2 LANGUAGE MODELING
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 (Mareus 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 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- per-character (BPC) metric for the character level datasets. The detailed experiment settings including the description of the datasets and syype--paaamtent are put into the Appendix A.2.
The results are shown in Figure 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- phr-cccrrrreeer metric of G-SGD algorithm on the PTB-C and enwik8 data sets are significantly lower than that of Path-SGD and SGD. 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.
PTB
Wikitext-2
enwiks
104
1.3
perplesiy
92
perpieaa
164
164
68
22
300
Pall XMD
3330)a0
1.71
100
Pelk (.NR))A)))))
(a)
(b)
(c)
(d)
Figure 4: Test metric for language tasks. The number means PPL in PTB and Wikitext-2 datascts. The number means BPC PTB-c and enwik8 datasets.
5.3 RECURRENT CONVOLUTIONAL NEURAL NETWORK
In this section, we optimize the Recurrent CNN(RCNN) for the image classification tasks(Liang & Hu, 2015). The model structure similar to the RNN. The main difference that the full connection in RNN is replaced by convolution layer."
We evaluate the algorithms on three benchmark image classification datasets, MNIST(LeCun & Cortes, 2010), CIFAR-10 and 100 (Krizhevsky & Hinton, 2009). For CIFAR-10 and CI-
Sat algorithm is not implemented to CNN in its original papers (Neyshabur al., 2015a; 2016), and it is not clear how extend it CNN. Thus we do not use Path-SGD baseline for experiments RCNN.
8

---

Under review as a conference paper at ICLR 2020
FARI00, (96, (t.1128.660 feature maps. Since MNIST is much easier, (32, 64, 96) feature maps. general, We follow the experiment setup in (Liang & Hu, 2015). Most of the hyper-parameters is same 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 outperforms the conventional optimization algorithms SGD that in weight space consistently.
that optimizing RCNN in path space
Table 2: Classification emror rate(%) of experiments recurrent convolutional neural networks.
RCNN-32
RCNN-64
RCNN-16
RCNN-96
RCNN-128
RCNN-160
RCNN-96
RCNN-128
RCNN-160
G-SGD
(our method)
0.36
0.31
0.31
7.38
6.61
6.52
31.52
29.64
28.78
SGD 0.38
0.37
0.39
7.47
7.53
7.54
33.34
31.51
29.67
6 CONCLUSION
In this paper, construct parameter space, called path space, for the RNN with ReLU activations and employ optimization algorithms in path space on benchmark experiments. To achieve this, propose reduction graph method 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 verify that
obtain significantly more effective RNN models in path space than using conventional optimization methods in the weight space. We would like 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-invaree the PSI property of the output of ReLU RNN. Moreover, the number of basis paths is even less than number of weights of the recurrent neural network.
which match
(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.
REFERENCES
Martín Arjovsky, Amar Shah, and Yoshua Bengio. Unitary evolution recurrent neural networks, In ICML, 2015.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint 1xX.v:440.0077 2014.
Shaojie Bai, J. Zico Kolter, and Vladlen Koltun. Trellis networks for sequence modeling. In International Conference Learning Representations 2019.
2019.
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. arXiv preprint arXiv:1703.049.. 2017.
Github. Recurrent convolutional neural network for object recognition, 2018. URL https://github. com/iimLLee5330RCNN
Github. Recurrent convolutional neural network for object recognition, 2019. URL https://github. comn/Suukamotshuuc//RCCNN,
Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp- 315-323, 1.
Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton. Speech recognition with deep recurrent neural networks, In 2013 IEEE international conference on acoustics, speech and signal processing, pp. 6645-6649 IEBE, 2013.

---

Under review as a conference paper at ICLR 2020
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Mareus Hutter. The human knowledge compression contest, 2012. URL http://prize.hhtterr .net/.
Rafal Jozefowicz, Oriol Vinyals, Mike Schuster, Noam Shazeer, and Yonghui Wu. Exploring the limits of language modeling. arXiv preprint arXiv:1602.08 024100, 2016.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. CIFAR, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convolu- tional neural networks. Advances neural information processing systems, pp. 1097-1105, 2012.
Quoc V Le, Navdeep Jaitly, and Geoffrey E Hinton. A simple way to initialize recurrent networks of rectified linear units. arXiv preprint
2015.
Yann LeCun. The mnist database of handwritten digits. URL http://yamm.eeuu..cm/exbmmmmsss
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mmist// 1998.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL http://yann.lecun. com/exdb/mnist/.
Ming Liang and Xiaolin Hu. Recurrent convolutional neural network for object recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3367-3375, 2015.
Mitchell Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. Building large annotated corpus of english: The penn treebank. Computational linguistics, 19(2):313-330, 1993.
Qi Meng, Shuxin Zheng, Huishuai Zhang, Wei Chen, Zhi-Ming Ma, and Tie- Yan Liu. G-sgd: Opti- mizing relu neural networks its positively scale-invariant space. In IC19'2019 072.v:180..03713. 2018.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. arXiv preprint 1eXXvv1609.0700 2016.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and Optimizing LSTM Language Models. arXiv preprint 11X.::/708..218222 2017.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. An Analysis of Neural Language Modeling at Multiple Scales. arXiv preprint arXiv:1803.084444 000440000000,...0 2018
Yajie Miao, Mohammad Gowayyed, and Florian Metze. Besen: End-to-end speech recognition using deep rmn models and wast-based decoding. In 2015 IEEE Workshop on Automatic Speech Recognition and Understanding (ASRU), pp. 167-174. IEBE, 2015.
Tomáš Mikolov, Martin Karafíát, Lukáš Burget, Jan Černocký, and Sanjeev Khudanpur. Recurrent neural network based language model. Eleventh annual conference of the international speech communication association, 2010.
Vinod Nair and Geoffrey E. Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th international conference on machine learning (ICML-10), pp. 807-814, 2010.
Behnam Neyshabur. Path-sgd: Path-normalized optimization in deep neural networks, 2019. URI http:://tthhbb.oommeeeebbbbbpppp
Behnam Neyshabur, Ruslan R Salakhutdinov, and Nati Srebro. Path-sgd: Path nath-normalized opti- mization in deep neural networks. Advances Neural Information Processing Systems, pp. 2422-2430. 2015a.
10

---

Under review as a conference paper at ICLR 2020
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401, 2015b.
Behnam Neyshabur, Yuhuai Wu, Ruslan R Salakhutdinov, and Nati Srebro. Path-normalized opti- mization of recurrent neural networks with relu activations. In Advances in Neural Information Processing Systems, pp. 3477-3485, 2016.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization deep learning. In Advances in Neural Information Processing Systems, pp. 5947-5956,
2017.
Pytorch. Word-level language modeling rnn, 2019. URL htthh////ggghhhbboooo/yyyyycccee master/word langguug language.mood model.
salesforce. Lstm and qrnn language model toolkit, 2019. URL http:://galuub.co///alseooorrr awd-lstm-lm.
Weinan, Chao Ma, and Lei Wu, priori estimates for two-layer neural networks. In arXiv preprint arXiv:1810.06699, 2018, 2019.
Shuxin Zheng. Qi Meng, Huishuai Zhang, Wei Chen, Nenghai Yu, and Tie- Yan Liu. Capacity control of relu neural networks by basis basis-path norm. arXiv preprint arXiv:/809 0800100000002...... 2018.

---

Under review as a conference paper at ICLR 2020
APPENDIX
A EXPERIMENT SETTINGS
All the experiments implemented by the Pytorch framework. And all the experiments run in the Nvidia GPU.
A.1 SEQUENTIAL MNIST EXPERIMENT
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 bode-base. The permutation dataset constructed by generating a random permutation of the index of each pixel(from 784) before the preprocessing procedure and then fix the random permutation during the train and test phases.
In the experiments, we 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.
single-layer RNN with ReLU activation. The number of the hidden
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)).
A.2 LANGUAGE MODELING EXPERIMENT
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 501 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. J. The weight decay is turned in the range { 1e-5, 1e-6, 1e-7 }. According to the (Merity et al. (2018; 2017)), we 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 enough for the convergence of all experiments. We identify the basis path for the RNN modules of the model and optimize the RNN modules 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
Hyperparameter Dropouts
Value
0.4
Layer numbers
Embedding size
400
Hidden size
1550
Batch size
40/128
Gradient clip
0.25
Dropoute
0.1
Dropouth*
0.2
Dropouti*
0.4
Wdrop'
0.1
Table 3: Hyperparameters for the language modeling experiments. The batch size is 40 for the word level datasets and 128 for the character level datasets. The last four hyperparameters with is corresponding to the implementation of the Salesforce Language Model Toolkit and the details can be find in salesforce (2019)
12

---

Under review as a conference paper at ICLR 2020
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 code of this experiment adapted from the Salesforce Language Model Toosfi(ssalesforce (2019)).
The implementation is based on the Salesforce Language Model Toolkitsalesforce (2019) and we only change the optimizer.
A.3 RECURRENT CNN EXPERIMENT
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.
Table 4: Classification error ra) of experiments on recurrent convolutional neural networks.
MNIST
CIFAR-10
CHEAR-100
RCNN.32
KCNN.96
5-SGD
(our method)
0.36
0.31
0.31
7.38
6.61
6.52
32,02
29.64
28.78
SGD
Liang(2015)
0.42
0.32
0.31
7.37
7.24
7.09
34.18
32.59
31.75
SGD
0.38
0.37
0.39
7.47
7.53
7.54
33.34
31.51
29.67
(our implementation)
B ALGORITHMS
B. DERIVATION OF THE ALGORITHM
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 Whs and the skeleton weight as Wg. We select the skeleton weight in the first layer as special skeleton weights and denote Wap and the non-skeleton weight this layer is denoted as Unao- Denote all the basis path set as Py, 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 Ws, Psp Note that there is 1-1 mapping between non-skeleton weights and the basis paths set Pas. Similarly, there is also 1-1 mapping between skeleton weights wso and the basis paths in set PP,.- Here, for simplicity, we can view recurrent weight non-skeleton weight Wne- Thus Pb, Pne.
Inverse-chain-une calculates the gradient with respect to basis paths according to the following equation:
Sups
aL
aL
0L
(7)
Own
Fwn
Dips
Dip
Ovam- Owr
By solving this equation, the gradients w.r.t basis paths can be derived as:
For Up.. we have:
aL
ØL Oupes
Dopna
Jwan
Owns
13

---

Under review as a conference paper at ICLR 2020
For Up., have:
aL
aL
EpePs/Pao
Owns
ab
Was
Dpp.
Swss
Wag
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 Cos is
the production of weights in path Pep except for Ws. Specifically, Up W*o Ceo Notation Dns the production of weights in path Pns except for Was. Specifically, u Das
We have:
81
++1 C++1
200
Pio. & R(v
(8)
o Peg
w C
Pro
aL
Pnu
Duf
141 Pan
R(v
whe D w D
(9)
11
Pnn
Solving this equation, the update rule for weight can be derived as:
Wap
1+1
= w
R(UpPn))
(10)
w¹
/
To Julpns
Was
141
R(ub.0)
(11)
OL
Wnso
when
Owhee
(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:
0L
Σ
ØL
Oup.
aL Otpas
(13)
Dwns
Oup
Own.
Dpp.s
Dwns
PEP
ØL
aL
Oup
aL
Supa
0L
00p
(14)
Dw
Oup
Sw
Oup.
Dwen
Oup
Dwee
PEP
pE PEPp/p
According to the skeleton method, each non-skeleton weight uns can only exists in one basis path
Pns- Besides, if wns not in p. Du'n the basis path as:
Ou.
Thus Eq. (13) is right Thus, we can derive the gradient of
ØL
0L Dupee
(15)
Opp..
Owas
Owns
aL
aL
Σ
aL
Oup Dwso
@0pea Jw'so
(16)
Dupro
Dwio
Dup
PEP/Pro
Let [Woo] = =p Pag
aL Oep
Oun.
We can then calculate the update ratio for the basis paths as:
Jwan
Upon
def
OL
n(vp.n))
- m/( DwL,
s[waol)/(
(17)
Duoto
BL
B(yppe)
Upnz
[+1
Det Pus
Uht Dwhs
aL
/(
Ougne
Owhs
vigne)
(18)
(19)
14

---

Under review as a conference paper at ICLR 2020
Above equation is right according to the gradient decent update rule of the path value oit1! o/
al Beg
?)
Finally, we project the new basis path value into the weight. Notation Csp is the production of weights in path Pso except for Wap Specifically, Uppg- = Wso Cr. Notation Dns is the production weights in path Pns except for Whe Specifically, Upns Wns" Dns.
++1
[+1
Pro
(20)
w
C%
1/200
C
1+1
R(ugen)) ). who
(21)
C
Was
++1
D
(22)
w
D
D D
wos
R(
was
(23)
Eq. (20) and (2 ) is the definition of the basis path. Note that we only update the skeleton weight the special layer ws. and the non-skeleton weight Wns- Therefore, non-skeleton weight in the special layer, D.
Cr
1. For the
CIT
D = 1. For the non non-skeleton weight not in the special
D layer, D 1/R(rp
B.2 NOTATIONS EXPLANATION IN THE ALGORITHM
Table Notations
notation zeros like(w)
object
Return all-zero matrix whose size is the same as
%
Modulus operator
shape(w)
Return the size of matrix
(0s
Return sum of the matrix w along axis O. If w is weight matrix of NN this operation sums the weight that connect to the same input and returns the vector with the same size as input node size.
B.3 COMPUTATIONAL COST
Here, provide the training time per epoch of our algorithm and the baselines in Table 6. We implement all experiments on a single GPU, shows that the real training time of G-SGD is also comparable with that of plain SGD.
Table 6: Training Time of epoch (seconds) in different experiments
PTB
Wikatest-2 902
PTB-c
enwak8
M-NNIST288
-NISST998
CIO-RCNN96
CID-RCNNI2S
CIO-RCNNIGO
Path-SGD
79.8
1407
10.2
13.3
SGD
31.4
66.0
61.5
1054
8.5
10.9
$6.0
74.0
125.5
G-SGD
63.8
9.2
60.9
Extra time
2,5
2.8
2.3
49
0.7
0.6
4.9
5,8
time cost increase rate
8.0%
4.2%
3.7%
4.6%
8.2%
3,5%
8.7%
7.8%
7.3%
B.4 STACK RNN AND CONVOLUTIONAL LAYER
For stack RNN, there are multiple layers of hidden nodes. Specifically, there are more than one W and W Note that the skeleton method is also held. Thus the Mask-Matrix Mattrix-Construtto algorithms can also be applied by generating mask matrix for all the weight matrix Wh according to the skeleton method.
15

---

Under review as a conference paper at ICLR 2020
For convolutional layer, we view feature map hidden node in MLP structure. So select one of the edges in the convolutional kernel that connect two feature mäps in two layers as the skeleton weights. Thus the Mask-Matrix Matrix-Construetu algorithms construct the mask matrix by selecting one element in one convolutional weight matrix that connects one input feature maps and one output feature maps 1.
C PROOF OF THEOREMS
C.I PROOF OF THEOREM 1
To ease the presentation the proof, we give the path a vector representation as follows. We index the edges in the reduction graph of neural network 61, fi...... , ...... Cm- We define the counting vector for a path either in the directed graph or in the reduction graph as Cp = (Cpe, > Cpen where Ope, equal the times that path p passes the edge ex. Please note that, if path p is in the directed graph, Cpe; may be larger than for some because of weight sharing. Theorem is proved if we show the counting vector of any path in the directed graph is linear combination of the counting vectors of the paths in the reduction graph.
Consider an arbitrary path in the directed graph with counting vector C₂ (Cp1, Cpm ). For each edge c₃. we choose path in reduction graph that contains this edge, which is denoted as p(i) and its counting vector Cp()). We claim that the term Ee,ep Cpi Cp(1) - Cp equals to the linear combination of counting vectors of paths in reduction graph. Without loss of generality, we suppose that contains nodes and edges Nf 4 N 3. .... 3 No+1. where e is the edge connecting an input node and a hidden node and ex is the edge connecting a hidden node and an output node, and other edges are recurrent edges. For edge e,, = 3. 3.
k - 1, we choose a path
NiJ 3 3-1 $ No 3 No that contains ej. where i, 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 that contains éj-1- layer,
ej. For edge Ej-1, choose a path N 225 N2-2 "1 N "25 NO 51-1
Furthermore, for the edge é1, we select an edge connecting with é1 at the hidden-to-ond denoted as c2 And for the edge ek. we select an edge connecting with eg at the input-to-hidee layer, denoted as eig. We claim that the edge e;, and edge Ex,-1 compose path in reduction graph because they both connect node N This claim is right for all j 2,... k. Thus the linear combination of the paths that contain Ci2 and C25-1 equals to Eesep Cpi Cp()) Cy-
No
No
NH
W
W2
W3
W
W2
N
N
Figure 5: An example of reduction graph of RNN
Here, we use the example in Figure to illustrate the above formulation. There are five weights
in Figure 5, denoted as (wi, W2, W3, W4, uts). Consider the path Nf.(1) -> H. + N (2.
(.. + No (. - (4.(() whose counting vector is C, = (1, 1). can be calculated as C = 1. (1,0,0, 1, + (1, 1, + 1 (1,0,0, 1, 4- 01,0, 0, 1, 1),,, where 01,0,0,1,00 and (1, 0, 1, 0) are paths in the reduction graph.
C.2 PROOF OF THEOREM 2
Recall the definition of the activation status (w x) = L IIN H1 (w;x) > 0), We will first prove that every indicator function of the node 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.
16

---

Under review as a conference paper at ICLR 2020
Denote the weights connect the node with index and the node with index j as Wij, consider the hidden node N. we define the value of the node as the sum of all incoming value before the activation and denote it using lower case letter of H.(() Formally, the value of the hidden node is
H,(0) Σ W
Σ
Hill W o " "(000011
where nr{*) the input node of stme-step and of (.((111 is the pre-activated hidden output of time-step
t - 1. The corresponding weights W and W is in the W and W" respectively the same as the notations in preliminaries. For simplicity, we denote the activation status of nodes as H.00 ((o, & I1(0 > 0) where is the indicator function. We use notation sign(-) to denote the sign (unntion(sign(() = 1 if a >> O and sign(a) a
We prove the theorem by using the induction method. Specifically, we will prove that the value of hidden node 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 which we call it outgoing skeleton weight and denote it as W..
H.00) = F(x, Up, sign(w.))
(24)
W
where F(x, Up, sign(w,)) is function that only related on the input z, values of paths Up and the signs of outgoing skeleton weights w.s Wo; is also an outgoing skeleton weight that connect to the hidden node of and o-
Firstly, we prove Equation 24 is satisfied in time-step 1. For an arbitrary hidden node with index j
of
H.0)
Σ
W (1)
1
W
W
Wr,
W
I
NN
kj
F(s,, up)
WC;
=((x; Up sws))
Wg
Then, using induction method, the induction assumpution is that 0:-1 can be represented by the function of path value divided by the weights on the skeleton edges,
1.(1-1) Flx,, up sign(ws)) oy
Woy
Then, get:
H.00) j
Wh,
Σ (i Σ Wf 11 alo Hll
Wo
Σ s( - " x00) Σ
Why W o 11 a( (.10-11)))
W
W
Σ s/ (1)
W F(z,, up, sign(ws))a(o H.l--11)
U1 (1 -
Wo
Wey
5'
1
F(z, Up (w.)( + Σ
F(x, Up sig (sigg F(z, sign(w.)))
Wo
F(z, Up sign(w:))
Wo
17

---

Under review as a conference paper at ICLR 2020
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(z, Up, sign(w))), W WELWT, Why F Fxx Up, sign(ws)) also a function 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 W And an arbitrary value of path in RNN multiplies the weight on the recurrent edge is also the value of a path.
So prove that if the equation 24 is satisfied in time-step 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: (p(w;; x> = Tx. Ep I[ H.1 (w; x:) > 0).
By using Equation (24), we can know that the sign of oz H.(() 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.
C.3 PROOF THEOREM 3
As mentioned, the structure of ReLU RNN can be decomposed into feedforward part and the recurrent edges part. For the feedforward part, the number of basis paths has been proved to be (iveiighs)##(hiddee
nodes) in Meng et al. (2018). According to Skeleton Method for RNN, each recurrent weight can only be contained one basis paths. Thus, the total number recurrent #
neural networks is #(weights of MLP)+ #recurrent weights) (100)(#(hhn (hidden nodes). Thus, finish the proof.
D TESTING ACCURACY CURVES FOR VISION TASKS
D.I
SEQUENTIAL MNIST
Permutation 37M15T-
Permuietion a7MI5T-28
parage
3.5
Epocle
E200
2.0
Mon Permatation 139157-902
5.0
Non Permutation 299357-22
3.0
8207
62074
(c)
(d)
Figure 6: Test Error Rate for Sequential MNIST experiments. x axis is the epoch index, axis is the Error Rate(%)
D.2 RECURRENT CNN
ADDITIONAL. G-ADAM V.S. ADAM EXPERIMENT RESULTS ON SEQUENTIAL. MNIST EXPERIMENTS
18

---

Under review as a conference paper at ICLR 2020
MOAST RCAN-12
VNIST SCN9-66
NM6T RCW0-46
(a)
(b)
CRARID RONOU56
CHAKIO ROWN $29
CEARIO ROM.
34
22-
Onner
(d)
(c)
Engr Bane
10
10
(g)
(h)
(i)
Figure 7: Test Error Rate for Recurrent CNN experiments on 3 datasets. x axis the epoch index, axis is the Error Rate(%)
Table 7: Averaged testing classification error rate(%) of the sequential MNIST experiment.
G-ADAM
ADAM
SMNIST-28
1,50 + 0.07
1.72 + 0.07
Con-Permutation
sMNIST-98
2.49 1 0.08
$1000.10
sMNIST-28
3.734 0.05
4.06 0.1
Permutation
sMNIST-98
5.42.t 0.1
5.574 0.09
19


Reviews:
[{"review_id": "ryxFe1MT9B", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\nThe G-SGD approach used in this work is not new and has been initially applied by Meng et al., 2018.\nMeng et al., 2018 have primarily introduced G-space for neural networks and designed SGD in G-space (G-SGD) to optimise the value vector of the basis paths of neural networks.  The main difference between this manuscript and previous works (Meng et al., 2018 and Neyshabur et al., 2016.) is that the authors apply G-SGD to RNNs instead of MLPs/CNNs.\nThe reviewer is not sure if this marginal difference is sufficient to get the paper accepted in ICLR. The structure, the methodology, and the content of this paper is highly similar to the work published by Meng et al., 2018.  \nThis paper claims to obtain significantly more effective RNN models than using optimization methods in the weight space without providing any statistically significant measures.\nThe authors could have added a visual performance comparison (e.g., training loss/epoch curve and test error/epoch curve) between the RNN G-SGD and other state-of-the-art approaches.\nThe theorems and their proofs are fine (similar to Meng et al. (2018)).\n ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "Skg8bjXTFH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nEven though the paper has some original contribution, due to issues with the delivery, clarity and execution of the paper I would lean to reject it at this point. I would be willing to change my decision if the authors made significant changes to the paper in aspects detailed below. The paper also has many grammatical and typographical mistakes that hinders the reader in understanding key ideas.\n\nFirst,  Section 2 could be much better explained. It seems like the notation introduced for a node and its value are used interchangeably, the edges are not clearly defined and Definition 1 is extremely confusing (what is s’ an arbitrary time step or all time steps between t and t+s, where is the list of weights mentioned in the first sentence and so on).  The definition for a key concept in the paper, the value of the path, is also not clear due to the lack of sufficient definition of the graph itself. \n\nSecond, in Section 3 the definition of the reduction graph and how it is obtained from the directed graph is not clear, which is problematic since it is one of the key ideas in the paper. Clear explanation of a recurrent edge is also missing.\n\nThird, in Section 4 terms such as ‘without recurrent edges parts’  that are used in defining the Skeleton method are very lax and needs to be defined more rigorously. It is hard to understand what the boxed steps are saying. Moreover,  in Algorithm 2 division by a matrix occurs at several points. Does this mean entry-wise division? What does the function BP(.) do? I couldn’t find it defined anywhere.\n\nLastly, in Section 5 it would be fair to make a comparison with adaptive optimization methods such as Adam or AdaGrad as it is done in [Neyshabur et al.: Path SGD]. \n\nI would like to provide some additional feedback that do not impact my decision, but could potentially improve the paper. In Section 2: I cannot find an explanation what an ‘unfold directed graph’ means. In eq. (3) x is used without any prior explanation/definition. In Section 3, the message around eq. (4) is not clear, how we pick p2…p5? Moreover, in the definition of basis paths P is used without explaining what it denotes.  Comments on Appendix: in Table 4 it is confusing to highlight the results corresponding to the papers method, because it suggests that these are the best results across the table, however there is a lower value in the second row. In B.1. taking derivative w.r.t p doesn’t seem to make sense, it should probably be v_p (this holds for the whole derivation). In Table 6, it would be a clearer to present relative (%) results than absolute time cost.  Comment on the proofs: they are extremely verbose and could potentially be explained with more math and less words. It is difficult to follow what is going on. There is also some notation not introduced before in eq. (28). In general, I would recommend only numbering equations that are referred to in the text. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJgnP_s15B", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Motivation: The authors motivate their work with the observation that neural networks with ReLU activations are positively scale invariant. Recent works have proposed parameter space called path space to leverage this insight for feedforward as well as CNNs, but this is not really the case for Recurrent Neural Networks (due to the recurrent structure and the parameter sharing). \n\nContribution:  The authors  construct path space for RNN to employ optimization algorithms in path space. The intuition is to leverage the reduction graph of RNN to removes the influence of time-steps. Reduction graph only contains information about the weight connectivity patterns and not about the time steps. Hence,  the number of paths in reduction graph is fixed (i.e independent of number of time steps.\n\nClarity: The clarity of the paper can be improved a bit. It might be useful to give a \"top-down\" introduction somewhat at the end of introduction. \n\nExperimental Results: In order to validate the proposed method, the authors conduct experiment on sequential MNIST tasks, as well as language modelling task. The results are a bit weak in general, and improvements are very minor over the vanilla RNN baseline. It might be interesting to compare to other baselines as in PathSGD paper.\n\n\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The scores of the reviewers are just far to low to warrant an acceptance recommendation from the AC.
Decision: Reject