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.
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.
Even 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.
First,  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. 
Second, 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.
Third, 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.
Lastly, 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]. 
I 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.