SGORNN: COMBINING SCALAR GATES
Year: 2021

Abstract:
Recurrent Neural Network (RNN) models have been applied in different domains, producing high accuracies on time-dependent data. However, RNNs have long suffered from exploding gradients during training, mainly due to their recurrent process. In this context, we propose a variant of the scalar gated FastRNN architecture, called Scalar Gated Orthogonal Recurrent Neural Networks (SGORNN). SGORNN utilizes orthogonal linear transformations at the recurrent step. In our experiments, SGORNN forms its recurrent weights through a strategy inspired by Volume Preserving RNNs (VPRNN), though our architecture allows the use of any orthogonal constraint mechanism. We present a simple constraint on the scalar gates of SGORNN, which is easily enforced at training time to provide a theoretical generalization ability for SGORNN similar to that of FastRNN. Next, we provide bounds on the gradients of SGORNN, to show the impossibility of (exponentially) exploding gradients. Our experimental results on the addition problem confirm that our combination of orthogonal and scalar gated RNNs are able to outperform both predecessor models on long sequences using only a single RNN cell, and outperforms LSTM. We further evaluate SGORNN on the HAR-2 classification task, where it improves upon the accuracy of FastRNN, VPRNN, and LSTM using far fewer parameters than FastRNN or LSTM. Finally, we evaluate SGORNN on the Penn Treebank word-level language modelling task, where it again outperforms its predecessor architectures and shows comparable performance to LSTM using far less parameters. Overall, this architecture shows higher representation capacity than VPRNN, suffers from less overfitting than the other two models in our experiments, benefits from a decrease in parameter count, and alleviates exploding gradients when compared with FastRNN on the addition problem.

heading: 1 INTRODUCTION
text: Recurrent Neural Networks (RNN) are models for sequence processing that have found applications in many areas, such as statistical machine translation (Cho et al., 2014), credit score calculation (Babaev et al., 2019), vehicle mobility prediction (Liu & Shoji, 2019), and music generation (Agarwala et al., 2017). Despite their wide applicability, RNNs have long suffered from exploding gradients, mainly due to the repeated application of the network’s hidden weights matrix during gradient computation (Hochreiter & Schmidhuber, 1997). Several strategies have been proposed to solve this problem, including models with orthogonal/unitary constraints on the hidden weights (Taylor-Melanson et al., 2021; Casado & Martı́nez-Rubio, 2019; Zhang et al., 2018; Vorontsov et al., 2017; Arjovsky et al., 2016; Jing et al., 2016). Such orthogonal models usually have fewer parameters than standard RNN architectures, which reduces the representation capacity and leads to less accurate models. Specifically, Taylor-Melanson et al. (2021) noted that a stack of two RNN cells is required to accurately model the addition problem for RNNs using the orthogonal VPRNN architecture when sequences become very long, and Rusch & Mishra (2020) noted that the EXPRNN architecture (Casado & Martı́nez-Rubio, 2019) fails to converge on the addition problem for very long sequences. To combat the problem of reduced representation capacity, Jing et al. (2019) proposed an LSTM-based architecture called the gated orthogonal recurrent unit (GORU)
which was experimented with using the EURNN orthogonal parametrization (Jing et al., 2016). While the GORU architecture is a very useful and novel orthogonal RNN construction, it adds many parameters when compared to typical orthogonal RNNs, and thus may not be suited for embedded or mobile applications.
Recently, Kusupati et al. (2019) proposed the FastRNN architecture, which adds a residual connection to a standard recurrent network using a scalar gating mechanism. FastRNN outperforms several well-known unitary RNN models on many classification tasks. These scalar gated RNN models have a generalization error gap which scales with the product of the length of the sequences being processed and the non-residual scalar gate, which is established through constraints introduced on the scalar gates of the network that are generally not enforced while training. Because of this, the assumptions required to prove the generalization of FastRNN cannot be guaranteed to be satisfied in practice under the original formulation of the architecture.
Although the VPRNN architecture and many other RNNs alleviate exploding gradients by utilizing orthogonal constraints, the problem of increasing representation capacity for orthogonal RNNs without greatly increasing parameter counts still remains. Moreover, even with the benefit from the weighted residual connection, FastRNN can still suffer from exploding gradients when applied to long sequences as shown in Section 3.1, and Rusch & Mishra (2020) noted that FastRNN fails to converge when training on long sequences for the RNN addition problem. In order to solve these problems, we propose the Scalar Gated Orthogonal Recurrent Neural Network (SGORNN), which is a variant of FastRNN that uses orthogonal linear transformations at the recurrent step.
The constraints on the scalar gates of FastRNN required for generalization are dependent on bounds of the Frobenius norm of the hidden weights matrix, and of the sequence length of the data being processed. Both of these quantities may not be well-defined in practice, making it difficult to ensure generalization. In contrast with FastRNN constraints, we present a constraint that relies only on the scalar gates of the SGORNN model, which is feasible to be employed in practice and results in a generalization gap with similar growth to that of FastRNN. Our theoretical results also confirm that SGORNN is immune to the (exponentially) exploding gradients so often seen when training RNN models.
In summary, SGORNN can ensure its theoretical generalization by applying the constraints we provide, which also alleviates exploding gradients. Our addition problem experiment shows that SGORNN converges for long sequences with a single RNN cell, outperforming both predecessor architectures despite having far fewer parameters than FastRNN. Using real-world data, SGORNN shows superior generalization to its predecessor models and comparable performance to LSTM models with far more parameters.
The remaining sections of this paper are organized as follows. In Section 2, we describe the proposed SGORNN architecture, followed by the theoretical formulation on generalization and exploding gradients. Experiments are presented and discussed in Section 3. In Section 4, we present the conclusions obtained from the experiments and formulation, as well as proposed future work. Finally, Appendix A contains detailed information on the mathematical formulation used to provide the generalization bound for SGORNN, as well as the alleviation of exploding gradients.

heading: 2 SGORNN
text: The proposed Scalar Gated Orthogonal Recurrent Neural Network (SGORNN) uses orthogonal linear transformations at the recurrent step. Given an input sequence {xt}Tt=1 ⊂ Rn of length T > 0, we define the hidden states ht ∈ Rh of a SGORNN at time t as:
ht = ασ(Wxt + φ(Θ)ht−1 + b) + βht−1. (1)
where Θ holds the recurrent parameters of the architecture, φ is a mapping from recurrent parameters into the orthogonal matrices, W ∈ Rh×n and U = φ(Θ) ∈ Rh×h are matrices, b ∈ Rh is a bias vector, and σ is a nonlinear activation function, such as rectified linear unit (ReLU). We use the notation U = φ(Θ) for consistency with Kusupati et al. (2019) during analysis. As with FastRNN, the parameters α, β ∈ (0, 1) are set by the sigmoid function. For simplicity, we assume h0 is a vector of zeros, though, in theory, it can be made to be a trainable value as well.
For the sake of experimentation, we choose φ(Θ) to be defined as the hidden weights matrix of the VPRNN architecture (Taylor-Melanson et al., 2021), a recently developed orthogonal RNN which is known to outperform several other unitary/orthogonal RNNs on classification tasks. It is worth mentioning that, although we use the VPRNN mapping in our experiments with SGORNN, an alternative orthogonal constraint such as that of EXPRNN (Casado & Martı́nez-Rubio, 2019) (with φ = exp) can also be applied to the proposed architecture. Following from Taylor-Melanson et al. (2021), the recurrent matrix is defined as:
φ(Θ) = R1Q1 . . .Rk−1Qk−1RkQk, (2)
which is a case of SGORNN with dom(φ) = Rn/2×k, such that Rj performs pairwise 2D rotations of the input vector using parameters from the jth column of Θ, and Qj is a fixed permutation matrix. This formulation is inspired by a feed-forward predecessor (MacDonald et al., 2021). It should be noted that, in the publicly available implementation of the VPNN layers from MacDonald et al. (2021) written in Keras (Chollet et al., 2015) that we require to implement SGORNN1, a modification to the permutation structure of U is present in the code.2 This detail is ignored to simplify notation, but is justified in the supplementary material for the sake of proving Corollary 1.
The constraint we propose for the scalar gates of SGORNN to ensure generalization takes the following form:
β ≤ 1− 2α. (3)
At first glance, this constraint may seem to limit the representation capacity of the model as FastRNN takes β = 1 − α > 1 − 2α by assumption during theoretical analysis. However, typically α 1, in which case β + 2α ≈ β + α, showing that an approximation to the standard formulation of the scalar gates remains. This constraint is empirically justified in later sections.
Because our proposed constraints on α and β are independent of all other parameters (or bounds), they are very simply enforced at training time by applying Equation 3. In practice, the parameter β is clipped after applying the sigmoid function, so that it lies in the half-open interval (0, 1− 2α].

heading: 2.1 GENERALIZATION BOUND
text: Initially, we state the constraint required for the generalization of FastRNN, to contrast with the constraints we require to guarantee the generalization of SGORNN and avoid exploding gradients. It is assumed for FastRNN that ‖U‖F ≤ RU for some RU > 0, and the required constraint takes the form:
α ≤ min (
1
4T |D ‖U‖2 − 1| ,
1
4TRU ,
1
T | ‖U‖2 − 1|
) . (4)
In the above equation, D is a real number derived from the parameters and activation function of the model. From this, Kusupati et al. (2019) established an O(αT ) generalization bound for FastRNN which becomes independent of T since α = O(1/T ). However, establishing this constraint in practice is difficult for several reasons. First, the constraint is dependent on the sequence length T of the model, which may be ill-defined in real-world scenarios, and can lead to vanishing α for very long sequences. Second, it relies on restricting the function space to those RNNs with ‖U‖F ≤ RU, so that RU is well-defined for use in Equation 4. In addition, in many cases, choosing such an RU before starting the training may decrease representation capacity drastically or, again, lead to vanishing α. Finally, the constraint becomes undefined for orthogonal matrices (‖U‖2 = 1). These issues motivate the use of our constraint from Equation 3 for SGORNN, which depends only on the use of the scalar gates α and β, and can be enforced at training time through a simple clipping operation without any prior assumptions about the sequence length or other parameters of the RNN. We define the class FT of SGORNN networks with ReLU activations as follows. Given bounds
1The implementation of SGORNN and experiment code is provided in a supplementary ZIP archive 2See the VPNN Python implementation at https://github.com/wtaylor17/keras-vpnn
RW, Rx > 0, any fixed α, β ∈ (0, 1) with β ≤ 1− 2α, a mapping φ from parameters to orthogonal matrices, and an input space X of sequences {xt}Tt=1 where ‖xt‖2 ≤ Rx, the SGORNN function class is defined as:
FT = {(xT ,hT−1) 7→ ασ(WxT + φ(Θ)hT−1) + βhT−1 : ‖W‖F ≤ RW,Θ ∈ dom(φ)}. (5)
It is implicit in the definition of the SGORNN function class that bias vectors are omitted or absorbed into the weights matrix, σ is the ReLU activation, and that the dimensions of hT−1,xT , and W are appropriate. The Rademacher complexity of this function class FT leads to the following theorem, which describes the generalization ability of SGORNN models with ReLU activation functions and with a single output neuron using any 1-Lipschitz activation function. This provides the equivalent of the FastRNN generalization gap result for our new proposed architecture:
Theorem 1 Let hT denote the final hidden state of a SGORNN model from the function class FT for predetermined bounds RW, Rx. For any vector v ∈ Rh with ‖v‖2 ≤ Rv, and any 1-Lipschitz activation function σy , denote f ∈ σy ◦ v ◦ FT as a single-neuron output model such that f(X) = σy(v
>hT ). Then, denoting L : R × R → [0, BL] as any bounded 1-Lipschitz loss function for some BL > 0, we have with probability at least 1 − δ over the draw of an i.i.d. sample S = {(X(i), y(i))}mi=1 from any input-output distribution, the following generalization gap holds:
E[L(y, f(X))] ≤ 1 m m∑ i=1 L(y(i), f(X(i))) + 4C αT√ m + 3BL
√ log 2/δ
m (6)
where C = RxRWRv represents the boundedness of the model parameters and input data, as in the analysis of FastRNN (Kusupati et al., 2019), and the expectation is taken over the input-output distribution.
The presented theoretical result for SGORNN shows that the generalization of the model is independent of U and Θ, which were not used to compute the bounds on α and β and do not appear in the definition of C. This is because the spectral norm for matrices is consistent with the Euclidean vector norm and ‖U‖2 = 1 for SGORNN. Further, the constraints on the scalar gates from Equation 3 do not depend on the sequence length T of the model. A proof of Theorem 1 is provided in Appendix A.1.

heading: 2.2 EXPLODING GRADIENTS
text: Next, we analyze the gradients ∂L∂W and ∂L ∂Θ of a loss function L, which is assumed to be 1-Lipschitz. As W and U are the only parameter matrices interacting with the loss through temporal layers, we study the maximum entry norm ‖·‖max of the loss function with respect to these parameters to show that SGORNN does not suffer from exploding gradients through time when applying a weaker constraint on α and β than the one from Equation 3. This analysis leads to our second theorem:
Theorem 2 Let f ∈ σy ◦ v ◦ FT be a SGORNN model with ReLU activation functions (as in Theorem 1) with a trivialization mapping φ satisfying ∥∥∥∂φ(Θ)∂Θij ∥∥∥max ≤ Mφ for all indices i, j, and with β ≤ 1− α. Then, the maximum parameter gradients of a 1-Lipschitz loss L satisfy:∥∥∥∥ ∂L∂Θ ∥∥∥∥ max ≤ CMφh(αT )2, (7)
∥∥∥∥ ∂L∂W ∥∥∥∥ max ≤ CαT √ h RW . (8)

heading: Where C and RW are defined as in Theorem 1.
text: From such a theorem, we obtain the following corollary concerning our chosen implementation of SGORNN:
Corollary 1 The VPRNN trivialization satisfies Theorem 2 with Mφ = 4 √ h log2(h), and so the gradients of the parameters Θ satisfy:∥∥∥∥ ∂L∂Θ ∥∥∥∥ max ≤ 4Ch3/2 log2(h)(αT )2. (9)
The theoretical bounds on the gradients above follow from the gradient computations provided in FastRNN (Kusupati et al., 2019) combined with knowledge of the VPRNN architecture (TaylorMelanson et al., 2021). The proof of Theorem 2 is provided in Appendix A.2, while the details of Corollary 1 are in Appendix A.3.
It should be noted that the above bounds differ from the findings of Arjovsky et al. (2016), who provided gradient bounds on general unitary RNN models independent of T . This is because the gradient computation of FastRNN (and consequently SGORNN) is greatly influenced by the residual connection through α and β. Regardless of this complication, we have shown that SGORNN does not suffer from the exponentially exploding gradients often seen when training RNNs.

heading: 3 EXPERIMENTS

heading: 3.1 ADDITION PROBLEM
text: As a proof of concept, the first experiment considered was the addition problem for RNNs, which was first proposed by Hochreiter & Schmidhuber (1997). This problem takes the form of a regression task, typically on the output vector hT of a recurrent network. The input sequence xt is a 2D sequence xt = (ut ct)
>, with ut being uniformly distributed in [0, 1] (i.i.d.) and ct representing a binary sequence. This binary sequence is mostly filled with 0s, having only two elements at positions i and j set as 1, in which i is chosen uniformly in [1, T/2] and j chosen uniformly in (T/2, T ]. Intuitively, the addition problem gives the sum of two random target positions in the sequence, that the RNN model must recognize and maintain (remember) over time.
The addition problem has been used as a benchmark for many RNN models which aim to process long sequences, as the randomly generated data introduces long-term dependencies (Li et al., 2018; Taylor-Melanson et al., 2021; Hochreiter & Schmidhuber, 1997; Arjovsky et al., 2016). A model applied on the addition problem is considered converged if it can consistently and considerably beat the baseline (MSE) error of approximately 0.167 on unseen data (Taylor-Melanson et al., 2021; Li et al., 2018), which is the error when the mean of the target (y = 1) is always predicted. In our experiments, all data is randomly generated as performed in the recent literature (Taylor-Melanson et al., 2021; Li et al., 2018). The regression target y over the sequence is the sum of the two random numbers as indicated by the indices i, j, defined mathematically as:
y(X) = T∑ t=1 utct = ui + uj . (10)
We compared the proposed SGORNN with VPRNN, FastRNN, and LSTM using the same model configuration and batch size for all architectures. In this experiment, all models had a hidden state dimension of 128, and the SGORNN and VPRNN used k = 14 rotational sublayers, which is the maximum number allowed based on the constraint from VPRNN architecture (Taylor-Melanson et al., 2021). Every model consisted of just one RNN layer with ReLU as the activation function. The constraint from Equation 3 was imposed on the SGORNN model so that the model satisfies Theorem 1. The RMSprop optimizer (Tieleman & Hinton, 2012) was used, in which the learning rate was decayed linearly to zero during training. Similarly to experiments conducted by Taylor-Melanson et al. (2021), models were trained with a batch size of 64 for a maximum of 20, 000 training steps, and 10 batches of unseen data were used to record validation MSE after every 100 training steps. We note that all models trained by Li et al. (2018) that converged on the addition problem did so within 20, 000 training steps, motivating our choice of cutoff for measuring convergence.
The goal of this experiment was to show which of the models tested are able to converge on different sequence lengths. For this reason, initial learning rates of each model were first set to 10−2, and were
decreased by a factor of 10 each time a model could not converge. For example, if a model could not converge with the initial learning rate of 10−2 it was retrained with an initial learning rate of 10−3. This was allowed to be done twice for each model, so that all initial learning rates came from the set {10−2, 10−3, 10−4}. In this way, we performed a basic search for the maximum learning rate to allow the convergence of the models. However, due to issues such as exploding gradients, some models could not converge for this task. In the case of partial convergence (e.g. VPRNN with T = 1000, see Figure 2), a learning rate decrease was performed to ensure better convergence could not be obtained. For such a scenario, the result for the best learning rate was reported. Figures 1, 2, and 3 present the validation error obtained for each model using the sequence lengths 500, 1000, and 5000 respectively.
For the shortest sequence length, T = 500, all three models were able to converge using the largest initial learning rate of 10−2, though FastRNN and SGORNN provided the most efficient convergence. In the case of sequences of length T = 1000, VPRNN failed to converge with learning rates of 10−2 and 10−4, though it achieved partial convergence with a learning rate of 10−3. Also with T = 1000, SGORNN converged efficiently with the largest learning rate of 10−2. FastRNN suffered from exploding gradients and divergent loss using all learning rates, even with the smallest learning rate of 10−4. FastRNN also achieved partial convergence for T = 1000 as shown in Figure 2, but was unable to reach an efficient solution before exploding gradients occurred. Lastly, for the largest sequence length of T = 5000, we observed that FastRNN suffered from exploding gradients and consequently a divergent MSE loss for all initial learning rates. VPRNN also failed to converge for T = 5000 regardless of the initial learning rate chosen, though it did not suffer from exploding gradients. In contrast to this result, SGORNN still converged efficiently using the largest initial learning rate of 10−2 and did not suffer from exploding gradients. The LSTM model failed for all sequence lengths greater than T = 500 regardless of the chosen learning rate.

heading: 3.2 HAR-2 CLASSIFICATION
text: The HAR-2 classification task is a binary classification task derived from a human movement data set collected using smartphones (Anguita et al., 2013). The data set consists of 9-dimensional sequences of length T = 128, having 7, 352 training instances and 2, 947 testing instances. We used this dataset to train and evaluate SGORNN, FastRNN, VPRNN, and LSTM models, conducting a performance comparison between them. All models were single-layer RNNs with 128 hidden units, except for the LSTM which was chosen to have 64 hidden units to roughly match the number of parameters of the FastRNN, similar to how hidden state sizes were chosen for a language modelling task in GORU (Jing et al., 2019). The SGORNN and VPRNN models had k = 14 rotational sublayers, which is the maximum allowed following from the constraint presented by Taylor-Melanson et al. (2021). We used an RMSprop optimizer (Tieleman & Hinton, 2012) with an initial learning rate of 10−3. Models were trained for 300 epochs using a batch size of 100, and the learning rate was decreased by a factor of 10 after 200 epochs. This strategy is similar to the one employed for FastRNN (Kusupati et al., 2019) with the main difference being our lack of hyperparameter tuning. We trained each model 10 times using different random seeds.3 The constraint from Equation 3 was imposed on the SGORNN model to ensure good generalization based on Theorem 1. This experiment shows that our proposed constraint from Equation 3 can be applied in practice using a real-world data set.
As shown in Table 2, SGORNN achieved the highest mean test accuracy among the three models trained. Although this accuracy is not drastically above that of FastRNN or LSTM, across the 10 training runs, the standard deviation of the test accuracies measured was the lowest for SGORNN. This suggests that SGORNN had both greater performance and more stable training than the other models, while requiring far fewer parameters than FastRNN or LSTM.
We use the difference between the training and test performance (for both accuracy and loss) to estimate the degree of overfitting of the models trained on this task. Plots of these estimates of overfitting are illustrated in Figure 4. Interestingly, VPRNN has the largest gap between training and testing accuracy, although this gap does not significantly differ from that of FastRNN or LSTM.
3To simplify reproducibility, the seed for run i was made to be the integer i ∈ {1, 2, . . . , 10}.
Further, the accuracy gap for both FastRNN, VPRNN, and LSTM seems to increase as training goes on, while the gap for SGORNN seems to decrease and eventually converge to a stationary value between 3% and 4% (Figure 4a). Even more interesting is the degree of overfitting of FastRNN with respect to the entropy loss, where the decrease in learning rate after 200 epochs caused the gap to grow much faster. VPRNN, FastRNN, and LSTM have an entropy gap growing with the number of epochs, while the SGORNN model loss gap remains nearly constant and has a very small variance (Figure 4b). This behavior suggests that, as training goes on, the degree of overfitting of SGORNN decreases or remains constant while it increases for all other models.

heading: 3.3 PENN TREEBANK LANGUAGE MODELLING
text: The Penn Treebank (PTB) data set is an annotated corpus for natural language processing tasks (Marcus et al., 1993). The word-level version of the data set consists of approximately 929, 000 training tokens, 74, 000 validation tokens, and 83, 000 testing tokens. The most common 10, 000 tokens are used, with the rest of the tokens replaced by <unk> tokens. Newline characters are replaced with <eos> tokens. We use this data set to evaluate our models on a language modelling task, where the output of the RNN at time t is a probability distribution over the token to be observed at time t+ 1 calculated using a softmax activation function on a fully-connected output layer.
We take our sequence length and model architecture from FastRNN (Kusupati et al., 2019), processing sequences of length 300 and fixing the dimension of the trainable embeddings of each model to be the same as that of the hidden states of the RNN being trained. Our models were all single-cell RNNs with 256 hidden units. Because the classification layer of these language models accounts for such a large proportion of the overall parameters, the LSTM model was allowed to remain at 256 hidden units (unlike in the previous HAR-2 task). The SGORNN and VPRNN models had k = 16 rotational sublayers. The constraint from Equation 3 was enforced on SGORNN to ensure generalization according to Theorem 1. We used the RMSprop optimizer (Tieleman & Hinton, 2012), with the same number of epochs and learning rate decay scheme as with the HAR-2 experiment
(Section 3.2). As an attempt to prevent overfitting in all models, we applied dropout of 0.3 to the embeddings given as input to the RNN cells. The metric used to evaluate models is the test perplexity, which measures the level of uncertainty of the language models (lower is better). It is seen in Table 3 that SGORNN outperforms both of its predecessor models, and shows comparable performance to LSTM despite having only a small fraction of the number of parameters within its RNN cell.

heading: 4 CONCLUSIONS
text: This paper has presented a new RNN architecture which combines orthogonal constraints with a scalar gating mechanism. This new RNN, which we call SGORNN, was implemented for the purpose of experimentation using an orthogonal transformation scheme from recent literature called VPRNN. However, as only Corollary 1 relies directly on the structure of the VPRNN mapping, our main theoretical results from Theorems 1 and 2 can be applied with different mapping strategies, such as the EXPRNN mapping (Casado & Martı́nez-Rubio, 2019).
Our theoretical analysis presented both bounds on the gradients of SGORNN and a generalization gap bound for Lipschitz loss functions. The gradient bound for SGORNN shows that gradients do not explode exponentially through time, but instead areO((αT )2) in the worst case when α ≤ 1−β. This constraint to control gradients is weaker than the one required for generalization of our architecture, in that enforcing the generalization constraint also enforces the gradient bound constraint. In theory, through further controlling bounds on α, we can fully control the upper gradient bound presented. The constraint on α (Equation 3) depends only on the other scalar gate β, rather than the α = O(1/T ) constraint required for generalization of a FastRNN, which depends on bounds constructed for other trainable parameters. Because of this dependence, our constraint for generalization was easily enforced through a clipping operation for the three tasks in our experiments.
In our experiments, we first trained models on the addition problem, where SGORNN was able to converge on sequences of length T = 5000 using less than 1, 500 parameters, while FastRNN suffered from exploding gradients and both VPRNN and LSTM failed to converge outright. This is the smallest number of parameters that was found in the literature for RNNs able to process such long sequences on the addition problem. Further, it shows that SGORNN may require just one RNN cell to perform accurately on tasks where other architectures with a reduced number of parameters such as IndRNN (Li et al., 2018) and VPRNN (Taylor-Melanson et al., 2021) have been noted to require two stacked cells. On the HAR-2 classification task, the SGORNN model had both the highest accuracy and suffered from the least amount of overfitting of all models considered. On the PTB word-level language modelling task, SGORNN outperformed both VPRNN and FastRNN in terms of test perplexity, and shows comparable performance to our LSTM. It is worth noting that our test perplexity for FastRNN is higher than that reported by Kusupati et al. (2019), which may be attributed to differences in hyperparameters. Based on the experiments, we conclude that the SGORNN architecture brings enforceable generalization and well-controlled gradients to the FastRNN architecture, and brings increased representation capacity to orthogonal RNN architectures such as VPRNN, reinforcing our theoretical results.
Future work on SGORNN will include further investigation of generalization ability, as well as investigation of alternative constraints on the scalar gates. Additional architectures such as SGORNN models with standard gating mechanisms may also be investigated. Finally, convergence analysis of SGORNN and the investigation of mappings to orthogonal matrices other than that of VPRNN will also be the topic of future work.

heading: A PROOFS OF STATED THEOREMS AND DETAILS OF COROLLARIES
text: In the following proofs, we follow notation similar to (Kusupati et al., 2019). This is different from that of (Taylor-Melanson et al., 2021) who denote the recurrent weights matrix by V rather than U. We choose to denote the empirical Rademacher complexity of a function class F by Rm(F), to indicate that the average is taken over a random sample of size m. This differs slightly from both (Kusupati et al., 2019) and (Bousquet et al., 2003) who use n instead of m to denote the size of the random sample, since we use n to describe the input data dimension in Section 2.

heading: A.1 PROOF OF THEOREM 1
text: We first begin with a description of the one-sided Rademacher complexity bound framework used. For any probability distribution D over input-output pairs z = (X, y) ∈ Z , any bound BL > 0, and any loss function L : Z × Ŷ → [0, BL] taking in a training instance and a prediction ŷ ∈ Ŷ , define a class of functions over any class of predictors F taking values in Ŷ as:
L ◦ F = {`f = (X, y) 7→ L(y, f(X)) : f ∈ F}, (11)
so that if `f ∈ L◦F then `f : Z → [0, BL] is a mapping from input-output pairs to loss values. The empirical Rademacher complexity of this class of functions is defined as in (Bousquet et al., 2003) on a sample S = {z(1), . . . , z(m)} drawn i.i.d. from D as:
Rm(L ◦ F) = E [ sup
`f∈L◦F
1
m m∑ i=1 i`f (z (i))
] (12)
The main result we require to prove the generalization of SGORNN is the one-sided Rademacher complexity bound from Bartlett & Mendelson (2002), which is also used by FastRNN (Kusupati et al., 2019). It states that, for all δ > 0, with probability at least 1 − δ over the draw of S, for any `f ∈ L ◦ F and distribution D over Z:
Ez∼D[`f (z)] ≤ 1
m m∑ i=1 `f (z (i)) + 2Rm(L ◦ F) + 3BL
√ log 2/δ
2m (13)
Theorem 1 Let hT denote the final hidden state of a SGORNN model from the function class FT for predetermined bounds RW, Rx. For any vector v ∈ Rh with ‖v‖2 ≤ Rv, and any 1-Lipschitz activation function σy , denote f ∈ σy ◦ v ◦ FT as a single-neuron output model such that f(X) = σy(v
>hT ). Then, denoting L : R × R → [0, BL] as any bounded 1-Lipschitz loss function for some BL > 0, we have with probability at least 1 − δ over the draw of an i.i.d. sample S = {(X(i), y(i))}mi=1 from any input-output distribution, the following generalization gap holds:
E[L(y, f(X))] ≤ 1 m m∑ i=1 L(y(i), f(X(i))) + 4C αT√ m + 3BL
√ log 2/δ
m (14)
where C = RxRWRv represents the boundedness of the model parameters and input data, as in the analysis of FastRNN (Kusupati et al., 2019), and the expectation is taken over the input-output distribution.
It just remains to establish a bound onRm(L ◦F). As before, denote f(X(i)) = σy(v>h(i)T ) as the output of the model on a given input sequence X(i) = (x(i)1 , . . . ,x (i) T ), where h (i) T denotes the final hidden state of the SGORNN on the given input. Denote the class of SGORNN networks (outputting hT ) as FT , so that F = σy ◦ v ◦ FT is the overall class of hypothesis functions. Because both L and σy are assumed to be 1-Lipschitz, we have by the Ledoux-Talagrand contraction (the needed version of which has a proof in (Mohri & Medina, 2014)) that:
Rm(L ◦ F) ≤ Rm(F) = Rm(σy ◦ v ◦ FT ) ≤ Rm(v ◦ FT ). (15)
By definition of the empirical Rademacher complexity, we then have that:
Rm(v ◦ FT ) = E [ sup
v,W,Θ
1
m m∑ i=1 iv >h (i) T
] . (16)
Next, recall that ‖v‖2 ≤ Rv and ‖W‖F ≤ RW. There is no explicit restriction placed on Θ as in the definition of FT . Note that:
Rm(v ◦ FT ) = E [ sup
v,W,Θ
1 m v> m∑ i=1 ih (i) T
] (17)
≤ E [ sup
v,W,Θ
1 m ‖v‖2 ∥∥∥∥∥ m∑ i=1 ih (i) T ∥∥∥∥∥ 2 ] (18)
≤ RvE [ sup W,Θ 1 m ∥∥∥∥∥ m∑ i=1 ih (i) T ∥∥∥∥∥ 2 ] . (19)
Now, we follow a similar strategy employed for FastRNN (Kusupati et al., 2019). Denoting Rm(FT ) as the above expected value, we have modified the notation of an inequality forRm(FT ), provided by Kusupati et al. (2019), to capture the supremum over recurrent parameters Θ:
Rm(FT ) ≤ βRm(FT−1) + 2α
m
( E [ sup W ∥∥∥∥∥ m∑ i=1 iWx (i) T ∥∥∥∥∥ 2 ] + E [ sup W,Θ ∥∥∥∥∥ m∑ i=1 iUh (i) T−1 ∥∥∥∥∥ 2 ]) .
(20)
Equation 20 relies on an analog of the Ledoux-Talagrand contraction to remove dependence on the activation function σ. The first expected value in this equation is bounded by RWRx √ m using the same argument as Kusupati et al. (2019). Because U is orthogonal, the second expected value in Equation 20 is:
E [ sup W,Θ ∥∥∥∥∥ m∑ i=1 iUh (i) T−1 ∥∥∥∥∥ 2 ] = E [ sup W,Θ ∥∥∥∥∥U m∑ i=1 ih (i) T−1 ∥∥∥∥∥ 2 ]
= E [ sup W,Θ ∥∥∥∥∥ m∑ i=1 ih (i) T−1 ∥∥∥∥∥ 2 ] = mRm(FT−1)
So that, by substituting the bounds on the expected values, Equation 20 becomes:
Rm(FT ) ≤ (β + 2α)Rm(FT−1) + 2αRWRX√
m (21)
Now, using the fact that β ≤ 1 − 2α, the coefficient of Rm(FT−1) in the above recurrence is at most 1. Assuming h(i)0 = 0 for all i, we get thatRm(F0) = 0 and consequently:
Rm(FT ) ≤ 2αT RWRx√
m . (22)
Setting C = RvRWRx, combining Equation 19 and Equation 22 gives a bound on the Rademacher complexity of L ◦ F of:
Rm(L ◦ F) ≤ 2C αT√ m , (23)
and finally, the desired bound holding with probability at least 1 − δ comes from combining Equations 13 and 23:
Ez∼D[`f (z)] ≤ 1
m m∑ i=1 `f (z (i)) + 4C αT√ m + 3BL
√ log 2/δ
2m , (24)
which is equivalent to the original statement of the theorem, as `f (z) is simply shorthand for L(y, f(X)).

heading: A.2 PROOF OF THEOREM 2
text: The proof relies on the two following formulas, taken from the formulation presented by Kusupati et al. (2019):
∂L ∂U = α T∑ t=1 Dt ( T−1∏ k=t (αU>Dk+1 + βI) ) (∇hTL)h>t−1, (25)
∂L
∂W = α T∑ t=1 Dt ( T−1∏ k=t (αU>Dk+1 + βI) ) (∇hTL)x>t , (26)
where Dk = diag(σ′(Wxk + Uhk−1)) is the Jacobian matrix of the pointwise activation function σ. Note that for ReLU, Dk is a diagonal matrix with a binary vector on the diagonal.
Theorem 2 Let f ∈ σy ◦ v ◦ FT be a SGORNN model with ReLU activation functions (as in Theorem 1) with a trivialization mapping φ satisfying ∥∥∥∂φ(Θ)∂Θij ∥∥∥max ≤ Mφ for all indices i, j, and with β ≤ 1− α. Then, the maximum parameter gradients of a 1-Lipschitz loss L satisfy:∥∥∥∥ ∂L∂Θ
∥∥∥∥ max ≤ CMφh(αT )2, (27)∥∥∥∥ ∂L∂W ∥∥∥∥ max ≤ CαT √ h RW . (28)

heading: Where C and RW are defined as in Theorem 1.
text: We begin by establishing the first bound involving Θ. Note that by the chain rule:
∂L ∂Θij = ∑ τ,µ ∂L ∂Uτµ ∂Uτµ ∂Θij . (29)
Note also that we simply denoted U = φ(Θ), so:
∂L ∂Θij = ∑ τ,µ ∂L ∂Uτµ ∂φ(Θ)τµ ∂Θij . (30)
Thus, since ∣∣∣∂φ(Θ)τµ∂Θij ∣∣∣ ≤Mφ:
∣∣∣∣ ∂L∂Θij ∣∣∣∣ ≤Mφ∑
τ,µ
∣∣∣∣ ∂L∂Uτµ ∣∣∣∣ = Mφ ∥∥∥∥ ∂L∂U ∥∥∥∥ 1,1 ≤Mφh ∥∥∥∥ ∂L∂U ∥∥∥∥ 2 , (31)
where we use the fact that ‖X‖1,1 ≤ √ h ‖X‖F and ‖X‖F ≤ √ h ‖X‖2 for any h × h matrix X. Next, we use the subadditivity and submultiplicativity of the spectral norm applied to Eq. 25:
∥∥∥∥ ∂L∂U ∥∥∥∥
2 ≤ α T∑ t=1 ‖Dt‖2 ( T−1∏ k=t (α ∥∥U>∥∥ 2 ‖Dk+1‖2 + β ‖I‖2) )∥∥(∇hTL)h>t−1∥∥2. Because ReLU is 1-Lipschitz, ‖Dk‖2 ≤ 1 for any k. Further, ∥∥U>∥∥ 2
= ‖I‖2 = 1. Thus, the product in the formula has an upper bound of (α+β)T−t ≤ 1. We also have that ∥∥(∇hTL)h>t−1∥∥2 ≤ ‖∇hTL‖2 ‖ht−1‖2. Thus:
∥∥∥∥ ∂L∂U ∥∥∥∥
2 ≤ α ‖∇hTL‖2 T∑ t=1 ‖ht−1‖2.
It is then left to bound ‖∇hTL‖2 and ‖ht−1‖2. First, for the hidden state:
‖ht−1‖2 ≤ ‖ασ(Wxt−1 + Uht−2) + βht−2‖2 ≤ α ‖σ(Wxt−1 + Uht−2)‖2 + β ‖ht−2‖2 ≤ α ‖Wxt−1 + Uht−2‖2 + β ‖ht−2‖2 ≤ α(RWRx + ‖Uht−2‖2) + β ‖ht−2‖2 ≤ αRWRx + (α+ β) ‖ht−2‖2 ≤ αRWRx + ‖ht−2‖2 .
Solving the above recurrence gives ‖ht−1‖2 ≤ αTRWRx. Next for the gradient, assuming a 1- Lipschitz loss, we get that:∣∣∣∣ ∂L∂(hT )j ∣∣∣∣ = ∣∣∣∣∂L∂ŷ ∂ŷ∂(hT )j ∣∣∣∣ = ∣∣∣∣∣∂L∂ŷ σ′y(v>hT )∂ ( v>hT ) ∂(hT )j
∣∣∣∣∣ ≤ |vj |. (32) So that ‖∇hTL‖2 ≤ Rv. Plugging these back in gives:
∥∥∥∥ ∂L∂U ∥∥∥∥
2
≤ RWRxRv(αT )2 = C(αT )2,
and consequently the gradient bound:
∣∣∣∣ ∂L∂Θij ∣∣∣∣ ≤ CMφh(αT )2 (33)
as desired (the statement regarding the max norm follows since we chose arbitrary i, j). Moving on to the bound on the gradient for W, we get using the same strategy that:
∥∥∥∥ ∂L∂W ∥∥∥∥ max ≤ ∥∥∥∥ ∂L∂W ∥∥∥∥ F ≤ √ h ∥∥∥∥ ∂L∂W ∥∥∥∥ 2
≤ √ hα ‖∇hTL‖2 T∑ t=1 ‖xt‖2 ≤ αTRvRx √ h = CαT √ h
RW
as desired.

heading: A.3 DETAILS OF COROLLARY 1
text: Taylor-Melanson et al. (2021) showed that using the VPRNN trivialization, for any Θ and ∆Θ:
‖φ(Θ)− φ(Θ + ∆Θ)‖2 ≤ k ‖∆Θ‖2 , (34)
where k = 2dlog2 he. Note that k ≤ 4 log2 h for h ≥ 2 which can be safely assumed. Now, consider a perturbation ∆Θ with zero entries everywhere but the i, jth entry, so that:∣∣∣∣∂φ(Θ)τµ∂Θij
∣∣∣∣ = lim∆Θij→0 |φ(Θ)τµ − φ(Θ + ∆Θ)τµ||∆Θij | . (35) The numerator has the upper bound:
|φ(Θ)τµ − φ(Θ + ∆Θ)τµ| ≤ ‖φ(Θ)− φ(Θ + ∆Θ)‖F ≤ √ h ‖φ(Θ)− φ(Θ + ∆Θ)‖2 ,
while the denominator has the lower bound (since ∆Θ has only one nonzero entry):
|∆Θij | = ‖∆Θ‖F ≥ ‖∆Θ‖2 .
Therefore, assuming the gradient of φ is defined, and the limit exists, it must satisfy:
∣∣∣∣∂φ(Θ)τµ∂Θij ∣∣∣∣ ≤ sup ∆Θij 6=0 √ h ‖φ(Θ)− φ(Θ + ∆Θ)‖2 ‖∆Θ‖2 ≤ k √ h ≤ 4 √ h log2 h, (36)
by the derivations presented for VPRNN (Taylor-Melanson et al., 2021). This completes the derivation of the Mφ bound for the VPRNN trivialization mapping.

heading: A.4 JUSTIFICATION OF CODE IMPLEMENTATION
text: The public code implementation of the VPRNN layer we required for our experiments adds some additional permutations to the matrix decomposition of U = φ(Θ). Regardless of how many it adds, we can define the mapping φ̃ of the implementation as φ̃ = Q̃1φQ̃2 for permutation matrices Q̃1, Q̃2, where φ is a typical VPRNN mapping using suitable permutation matrices. This definition is due to the fact that the product of two permutation matrices is also a permutation matrix. Using the spectral norm ‖·‖2, we get the following inequality since Q̃1, Q̃2 are orthogonal:
∥∥∥φ̃(Θ + ∆Θ)− φ̃(Θ)∥∥∥ 2 = ∥∥∥Q̃1φ(Θ + ∆Θ)Q̃2 − Q̃1φ(Θ)Q̃2∥∥∥ 2
≤ ∥∥∥φ(Θ + ∆Θ)Q̃2 − φ(Θ)Q̃2∥∥∥
2
≤ ‖φ(Θ + ∆Θ)− φ(Θ)‖2 ≤ k ‖∆Θ‖2 .
So, the result required for Corollary 1 holds for the implementation provided and the extra permutations can be ignored.

Review summaries:
Authors demonstrate a new RNN-based architecture that avoids exploding gradients via careful selection of primitives and hyperparameters. The authors motivate their selections with gradient magnitude bounds and show proofs for them. Finally, the authors demonstrate their model's superior performance against several RNN-based baselines directly relevant to their architecture.

In this paper, the authors propose an RNN architecture named SGORNN. The high-level idea is to add a residual connection between hidden states, and to parametrize the weight matrix by the product of a series of rotation and permutation matrices so that the weight matrix is orthogonal. The proposed model can be seen as an extension of the FastRNN model, the theoretical analyses of which also apply as a result. The proposed model is evaluated on a few tasks including the addition problem, HAR-2 classification, and PTB.

This paper proposed a novel recurrent network architecture called Scalar Gated Orthogonal Recurrent Neural Networks (SGORNN). The model is a combination of (1) orthogonal transition matrix and (2) fixed residual connection as in FastRNN (Kusupati et al., 2019). The authors theoretically studied the generation bound and gradient exploding condition of the model.  Lastly, experiment results show that the proposed model outperforms standard FastRNN and a version of vanilla orthogonal RNN on three tasks: (1) synthetic adding problem, (2) HAR-2 classification, (3) Penn Treebank word-level language modeling.  

This work proposes to approach and partially solve (under certain constraints) the exploding gradient problem of RNN. In practice, the authors combined two existing methods (residual connection + unitary RNNs) in a single novel model. Demonstrations are given for the exploding issue and for the motivation of parameter constraints. The new model, called SGORNN, is then tested on two toy tasks and on a largish one (language modelling). SGORNN outperform models that are based either on residual connection or unitary recurrent connections only.