RNNs Incrementally Evolving on an Equilibrium Manifold: A Panacea for Vanishing and Exploding Gradients?
Authors: Anil Kag
Ziming Zhang
Venkatesh Saligrama
Venue:  (2020)
Keywords: novel recurrent neural architectures
learning representations of outputs or states

Abstract: Recurrent neural networks (RNNs) are particularly well-suited for modeling long-term dependencies in sequential data, but are notoriously hard to train because the error backpropagated in time either vanishes or explodes at an exponential rate. While a number of works attempt to mitigate this effect through gated recurrent units, skip-connections, parametric constraints and design choices, we propose a novel incremental RNN (iRNN), where hidden state vectors keep track of incremental changes, and as such approximate state-vector increments of Rosenblatt's (1962) continuous-time RNNs. iRNN exhibits identity gradients and is able to account for long-term dependencies (LTD). We show that our method is computationally efficient overcoming overheads of many existing methods that attempt to improve RNN training, while suffering no performance degradation. We demonstrate the utility of our approach with extensive experiments and show competitive performance against standard LSTMs on LTD and other non-LTD tasks.


Published as a conference paper at ICLR 2020
RNNS INCREMENTALLY EVOLVING ON AN EQUILIBRIUM MANIFOLD: A PANACEA FOR VANISHING AND EXPLODING GRADIENTS?
Anil Kag
Ziming Zhang
Venkatesh Saligrama ECE Department Boston University Boston, MA 02215, USA S srv@bu.edu
ECE Department
ECE Department
Boston University Boston, MA 02215, USA ani kaa.kukabb.... edu edu
Worcester Polytechnic Institute
Worcester, MA 01609, USA 2 zzhang15ewp 50wpl. edu
ABSTRACT
Recurrent neural networks (RNNs) are particularly well-suited for modeling long- term dependencies in sequential data, but are notoriously hard to train because the error backpropagated in time either vanishes or explodes an exponential rate. While a number of works attempt to mitigate this effect through gated recurrent units, skip-connections, parametric constraints and design choices, we propose a novel incremental RNN (iRNN), where hidden state vectors keep track of incre- mental changes, and such approximate state-vector increments of Rosenblatt's (1962) continuous-ting time RNNs. iRNN exhibits identity gradients and is able to account for long-term dependencies (LTD). We show that our method is computa- tionally efficient overcoming overheads of many existing methods that attempt improve RNN training, while suffering no performance degradation. We demon- strate the utility of our approach with extensive experiments and show competitive performance against standard LSTMs on LTD and other non-LTD tasks.
INTRODUCTION
Recurrent neural networks (RNNs) each round store a hidden state vector, hm E R.,, and upon receiving the input vector, Fm+11 E Rd, linearly transform the tuple (hm,)m+11) and pass it through a memoryless non-linearity to update the state over rounds. Subsequently, RNNs output an affine function of the hidden states as its prediction. The model parameters (state/input/predictionn parameters) are learnt by minimizing an empirical loss. This scemingly simple update rule has had significant success in learning complex patterns for sequential input data.
Nevertheless, that training RNNs can be challenging, and that performance can be uneven on tasks that require long- long-term-ooe -eeendeenyy (LTD), was first noted by HHchreiter [1991). [Beniio et al. (1994) and later by other researchers. Pascanu et al. (203b) attributed this to the fact that the error gradient back- mack-propagated in time (BPTT), for the time-step m, dominated by product of partials of hidden- state vectors, 11 0h and these products typically exhibit exponentially vanishing decay or ah, explosion, resulting in incorrect credit assignment during training and test-time.
Rosenblatt 1962). on whose work we draw inspiration from, introduced continuous-time RNN (CTRNN) to mimic activation propagation in neural circuitry. CTRNN dynamics evolves as follows:
Tÿ(l) oog(() + ((Ug(t) + Wx(() + b), 2 to-
Here, xtt) E Rd is the input signal, g(t) R is the hidden state vector of D neurons, (t(() is the rate of change of the i-th state component; т, a E R* referred to as the post-synaptic time-constant, impacts the rate of a neuron's 's response to the instantaneous activation @(Ug(t) W zxt) + b); and E IR DDD W E Dxd, b E R are model parameters. In passing, note that recent RNN works that draw inspiration from ODE's (Chang et al. 2019) are special cases of CTRNN (7 1, a 0).

---

Published as a conference paper at ICLR 2020
Vanishing Gradients. The qualitative aspects of the CTRNN dynamics is transparent in its integral form:
s(() = t-to g((o) + 1 [ e (8) + Wx(s) + b)ds
This integral form reveals that the partials of hidden-state vector with respect to the initial condition, Bg(())
Bg[to)) gets attenuated rapidly (first term in RHS), and so we face a vanishing gradient problem. We will address this issue later but we note that this is not an artifact of CTRNN but exhibited by ODEs that have motivated other RNNs (see Sec. 2
Shannon-Nyquist Sampling. A key property of CTRNN is that the time-constant r together with the first term -((,, is in effect low-pass filter with bandwidth or suppressing high frequency components of the activation signal, (((g)s))) + (Wx(s)) + b). This is good, because, by virtue of the Shannon- Ghannon-Nyquist sampling theorem, can maintain fidelity of discrete samples with respect to continuous time dynamics, in contrast to conventional ODEs (a = 0). Additionally, since tigh-frequencies already suppressed, in effect we may assume that the input signal s=tt) is slowly varying relative to the post-synaptic time constant T.
The combination of low pass filtering and slowly time varying input has significant bearing. The state vector as well as the discrete samples evolve close to the equilibrium state, i.e., g(t) = (UUg(t) + Wx(t)= + b) under general conditions (Sec. 3
Equilibrium.
Incremental Updates. Whether or not system is in equilibrium, the integral form in Eq. 2 points to gradient attenuation a fundamental issue. To overcome this situation, we store and process increments rather than the cumulative values gt) and propase dynamic evolution in terms of in- crements. Let us denote hidden state sequence as hm E R D and input sequence I' E Rd For m 1, ,,...,T, and a suitable 3 >> 0
Tg(t) = aa(((t) + hm- + (o(() + hm-1) + Wam + +), 9(0) = 0, 220 (3)
hm h 2 9(B
Intuitively, say system is in equilibrium and -a(u(Zm:
1m- W am +b) 0.
We note state transitions are marginal changes from previous states, namely, hn = / (Tim: Nm 1)
1m Now for fixed input Imm as to which equilibrium is reached depends on hm but are
nevertheless finitely many. So encoding marginal changes as states leads to "identity" gradient.
Incremental RNN (iRNN) achieves Identity Gradient. We propose to discretize Eq. 3 to realize iRNN (see Sec.
3p. At time m, it takes the previous state hm E DR and input Tm IRd and outputs h. E IR after simulating the CTRNN evolution in discrete-time, for suitable number of discrete steps. We show that the proposed RNN approximates the continuous dynamics and solves the vanishing/exploding gradient issue by ensuring identity gradientIn general, we consider two options, SiRNN, whose state is updated with a single CTRNN sample, similar to vanilla RNNs, and, iRNN, with many intermediate samples. SiRNN is well-suited for slowly varying inputs.
Contributions. To summarize, we list our main contributions:
(A) iRNN converges to equilibrium for typical activation functions. The partial gradients of hidden- state vectors for iRNNs converge to identity, thus solving vanishing/exploding gradient problem!
(B) iRNN converges rapidly, an exponential rate in the number of discrete samplings of Eq. SiRNN, the single-step iRNN, is efficient and can be leveraged for slowly varying input sequences. It exhibits fast training time, has fewer parameters and better accuracy relative standard LSTMs.
(C) Extensive experiments on LTD datasets show that we improve upon standard L.TT accuracy as well as other recent proposals that are based on designing transition matrices and/or skip connections.
iRNNs/SiRNNs are robust to time-series distortions such as noise paddings
(D) While our method extends directly (see Appendix I to Deep RNNs, we deem these extensions complementary, and focus single-layer to highlight our incremental perspective.
2 RELATED WORK
Gated Architectures. Long short-term memory (LSTM) (Hochreiter & Schmidhuber 1997) is widely used in RNNs to model long- long-term dependency in sequential data. Gated recurrent unit (GRU) (Cho et al. 2014) is another gating mechanism that has been demonstrated to achieve similar
2

---

Published as a conference paper at ICLR 2020
performance of LSTM with fewer parameters. Some recent gated RNNs include UGRNN (Collins et al.] 2016), and FastGRNN (Kusupati et al., 2018). While mitigating vanishing/exploding gradients, they do not eliminate it. Often, these models incur icreassd inference, training costs, and model size.
Unitary RNNs. Arjovsky et al. 2 Jing et al. 2017); Zhang et al. (2018); Mhammedi et al. (2016) focus on designing well-conditioned state transition matrices, attempting to enforce ppooprty.....y........ during training. Unitary property does not generally circumvent vanishing gradient (Pennington et al.
(2017) ). Also, it limits expressive power and prediction accuracy while also increasing training time.
Deep RNNs These are nonlinear transition functions incorporated into RNNS for performance improvement. For instance, Pascanu et al. (2013a) empirically analyzed the problem of how to construct deep RNNs. Zilly et al. (2017) proposed extending the LSTM architecture to allow step-to- step transition depths larger than one. Mujika et al. (017)) proposed incorporating the strengths of both multiscale RNNs and deep transition RNNs to learn complex transition functions. While Deep RNNs offer richer representations relative to single-layers, is complementary to iRNNs.
Residual/Skip Connections. Jaeger et al. (207)) Bengio et al. (2013) Chang et al. (017): Campos et al. (017)); Kusupati et al. (2018) feea-forward state vectors to induce skip or residual connections, to serve as a middle ground between feed-forward and recurrent models, and to mitigate gradient decay. Nevertheless, these connections, cannot entirely eliminate gradient explosion/decay. For instance, Kusupati et al. (2018) suggest h.m. am Am-1 + 8m + Wxm + b). and learn parameters so that Ctm, Rs and Bm R O. Evidently, this setting can lead to identity gradient, observe that setting 3.. = 0, implies little contribution from the inputs and can conflict with good accuracy, as also observed in our experiments.
Linear RNNs. (Bradbury al.] [016)] Lei et al. 2018; Balduzzi & Ghifary 2016) focus on speeding up RNNs by replacing recurrent connections, such as hidden-to-hidder interactions, with light weight linear components. This reduces training time, but results in significantly increased model size. For example, Lei et al. (2018) requires twice the number of cells for LSTM level performance.
ODE//ynamiees Perspective. Few ODE inspired architectures attempt to address stability, but do not end up eliminating vanishing/exploding gradients. Talathi & Vartak (2015) proposed modified weight initialization strategy based on dynamical system perspective on weight initialization process to successfully train RNNs composed of ReLUs. NNu et al. (2019) analyzed RNN architectures using numerical methods of ODE and propose family of ODE-RNNs. [hang et al. (2019), propose Antisymmetric-RNN. Their key idea is to express the transition matrix in Eq. for the special case a = 0, r = 1, as a difference: U = - VT and note that the eigenspectrum is imaginary. Nevertheless, Euler discretization, in this context leads to instability, necessitating damping of the system. As such vanishing gradient cannot be completely climinated. Its behavior is analogous to FastRNN Kusupati FKstRNNNKusupatii et al. (2018), in that, identity gradient conflicts with high accuracy. In summary, we are the first to propose evolution over the equilibrium manifold, and demonstrating identity gradients. Neural ODEs (Chen et al.) 2018 Rubanova et al., 2019) have also been proposed for time-series prediction to deal with irregularly sampled inputs. They parameterize the derivative of the hidden-state in terms of autonomous differential equation and let the ODE evolve in continuous time until the next input arrives. As such, this is not our goal. our ODE explicitly depends on the input, and evolves until equilibrium for that input is reached. We introduce incremental updates to bypass vanishing/exploding gradient issues, which is not of specific concern for these works.
3 METHOD
We use Euler's 's method to discretize Eq. 3 in steps 8 = np. Denoting the kth step as g = g(kō)
Dh gh a(t + hm + @U (1k-1 + hm-1) + Wam + b), k E [K]
(4)
8
Rearranging terms we get compact form for iRNN (see Fig. D. In addition we introduce a learnable parameter wtt and let be a function of time m and the recursion-step ks
9k = 9k-1 + Th (OKU(g -1 + hm- 1) + Wx,, + b) ag + 1)), ls E [K] (5)
k gK
We run the recursion for l E [K] with some suitable initial condition. This could be gn = 0 or initialized to the previous state, i.e., go hm-1 at time m.
3

---

Published as a conference paper at ICLR 2020
go hm-1
Q
Q
P
Sk
17
1
1 K
X m
Figure iRNN depicted by unfolding into recursions for one transition from Go = hm-1 to hm = 9K- Here, sp(r,, 9, h) (UV h) Wx + b) - a(g + ht) See Sec. A.2. for implementation and pseudo-code. This resembles Graves (2016), who propose to vary K with m as way attend to important input transitions. However, the transition functions used are gated units, unlike our conventional ungated functions. As such, while this not their concern, equilibrium may not even exist and identity gradients are not guaranteed in their setup.
In many of our examples, we find the input sequence is slowly varying, and K = can also realize good empirical performance. We refer to this munglessep-iiccemennte
(SiRNN).
h 9o + 7m ( + hm + Wm + b) a(hm- + go))
(6)
For both iRNN and SiRNN we drop the superscript whenever is clear from the context.
Root Finding and Transitions. The two indices k and m should not be confused. The index m [T] refers to the time index, and indexes input, I'm and hidden state h. over time horizon T. The index & [K] is a fixed-point recursion for converging to the equilibrium solution at each time m, given input xm and the hidden state hm-1- We iterate over so that at = K, 9K satisfies,
((U( + 7m 1) + Wm + b) aggx + hm-1) R0
The recursion (Eq. (5) at time runs for K rounds, terminates, and recursion is reset for the new input, Tm+11 Indeed, Eq. i is standard root-finding recursion, with gk-1 serving as the previous solution, plus correction term, which is the error, ((U( + hm-1) + Wxm + b) - a(9k-1 + hmm-1). If the sequence converges, the resulting solution the equilibrium point. Proposition guarantees geometric rate of convergence.
Identity Gradient. We will informally (see Theorem I show here that partial gradients are identity. Say we have for sufficiently large K, hm 9K is the equilibrium solution. It follows that,
@hm hm-1) Wam + b) athm hm--1))
Taking derivatives, have,
3lm
Ohm + +1)=0
Ohin
Vo(-)U
1)
1 ahm-1
- = (VV(-UU - -al)
+1 (7)
Ihm-1
Jhm-1
Thus if the matrix (VΦ(-UU - aI) is not singular, follows that (
abm ab.
+ +1 =0
SiRNN vs. iRNN. SiRNN approximates iRNN. In particular, say 2m is constant in the segment, E [mo, ma + K]. then SiRNN trajectory of hidden states, denoted as h is equal to the iRNN hidden state h h when both SiRNN and iRNN are initialized with go hm-1- Thus, for slowly time-varying inputs we can expect SiRNN to closely approximate iRNN.
Residual Connections vs. iRNN/SIRNN. As such, our architecture is special case of skip/residual connections. Nevertheless, unlike skip connections, our connections are structured, and the dynamics driven by the error term ensures that the hidden state is associated with equilibrium and leads to identity gradient. No such guarantees are possible with unstructured skip connections. Note that for slowly varying inputs, after a certain transition-time period, we should expect SiRNN be close to equilibrium well. Without this imposed structure, general residual architectures can learn patterns that can be dramatically different (see Fig. 2).
3.1 IDENTITY GRADIENT PROPERTY AND CONVERGENCE GUARANTEES.
Let us now collect few properties of Eq. and Eq. First, denote the equilibrium solutions for an arbirary input x E Rd, arbitrary state-vector u E R in an arbitrary round:
(o) {p R a< v) sU (4 Wa + b)}
4

---

Published as a conference paper at ICLR 2020
Whenever the equilibrium set is singleton, denote it function (eg v). For simplicity, assume below that fij is positive constant independent of k and i.
Proposition 1. Suppose, o(-) is a 1 I-Lipsitzz function in the norm induced by || and ||O||| < a, then for any Zm R' and hm-1 E RD, follows that Meg(z,)) v) singleton and as K - oc, the iRNN recursions converge to this solution, namely, hm = --lmm - 9K (Tm, hmm-1)
Wam Proof. Define T T:R + Rd, with T(g) =1 (1-raag 7 hm-1) + W am + b) hm-1). follows that T() is contraction:
([T(g) Il S(1 ng)ll9 - g'll + (U + hm-1) + Wm + b) <(U(g' hm- + Wzm am + b)ll
s (1 (1-nj na + ||U||])] 9'1l < |1g g'll.
We now invoke the Banach fixed point theorem, which asserts that contractive operator on complete metric space converges to a unique fixed point, namely, T (g) + 9.. Upon substitution, we see that this point 9- must be such that, @(U + hm--1) W Im + 6) (g- + + 0. Thus equilibrium point exists and is unique. Result follows by setting h. - heg (Zm, hm-
Handling ||U|| S In experiments, set 1, and do not enforce ||l'|| constraint. Instead, we initialize U as a Gaussian matrix with IID mean zero, small variance components. As such, the matrix norm is smaller than 1. Evidently, the resulting learnt U matrix does not violate this condition.
Next we show for rj > 0, iRNN converges at a linear rate, which follows directly from Proposition Proposition 2. Under the selup in Proposition 7 it follows that,
||A K (eg(Im. 1m-11)l 19gk - (eeg(Tm Am- 1)l S (1 - on + n||U))> (192 - heg 1
m
Remark. Proposition I accounts for typical activation functions ReLU, tanh, sigmoids as well as deep RNNs (appendix A.I).
In passing we point out that, in our experiments, we learn parameters n and a result that accounts for this case is desirable. We describe this case in Appendix A.3] A fundamental result we describe below that partials of hidden-state vectors, on the equilibrium surface unity. For technical simplicity, we assume a continuously differentiable activation, which appears to exclude ReLU activations. Nevertheless, we can overcome this issue, but requires more technical arguments. The main difficulty stems from ensuring that derivatives along the equilibrium surface exist, and this can be realized by invoking the implicit function theorem (IFT). IFT requires continuous differentiability. which ReLUs violate. Nevertheless, recent results suggests that can state implicit function theorem for everywhere differentiable functions, which includes ReLUs.
Theorem 1. Suppose ob.) is a continuously differentiable, I I-Lipshitz Bi.m Oheg (immmmm
with ||U|| < a. Then -I Furthermore, as K -> Do the partial gradients over
as K + x., Thm-1 arbitrary number of rounds for iRNN is identity.
Ohm-1
Ohr Oh,
Ohm 0hm-1
Oh, Oh,
II
(-1)--
= 1.
r2m58
Proof. Define, (gg. hm- Φ(U(g + hm-1) W 3m + b) a(g + Am-1)). We overload notation (2rm hm--1). Invoking
and view the equilibrium point function of hm-1, i.e., Ia (hm standard results" in ODE's, it follows that ga (hm-1) ) is smooth function, long the Jacobian, Vgthgg.. hm--1) with respect to the first coordinate, 9a, is non nonnsingular. Upon computation, we see al, is non-singular, since [/Vogee, 1ammhmmm-)) 1) < [|U]] It follows that we can take partials of the state-vectors. By taking the partial derivatives w.r.f hm-1 dg. + I in Eq. 5 at the equilibrium points we have [Vo(g,, Am 1 al]. ah...
that, Vg 1) Vø(ge, 1Im
0 (see Eq. 7 The
rest of the proof follows by observing that the first term is non songula.
fau. wwwprrawwtttttttooooeoeeeetooooe shortversioon_dal..o
5

---

Published as a conference paper at ICLR 2020
State Space on 1D, Random, Walk JRNN vs. JANS
Remark. We notice that replacing hm-1 with
15
-hm-1 Eq. 12 will lead Ohoy Bhm I, which
20
also has no impact on magnitudes of gradients. As result, both choices are suitable for circumventing vanishing or exploding gradients during training, but still may converge to different local minima and thus result in different test-time performance. Fur- thermore, notice that the norm preserving property is somewhat insensitive to choices of a, so long as the non-singular condition is satisfied.
0204
Tew-erajetoryy
10 Figure 2: Phase-space trajectory with tanh activa- tion of RNN. FastRNN, iRNN, X-axis denotes 1st dimension, and Y-axis 2nd dimension of 2D hidden state subject to random walk input with variance 10 for 1000 time-steps, Parameters U, W, b are domly initialized. RNN states are scaled fit plot since FastRNN not required to the cube.
15
3.2 IRNN DESIGN IMPLICATIONS: LOW-RANK MODEL PARAMETRIZATION
Fig. 2 depicts phase portrait and illustrates salient differences between RNN, FastRNN (RNN with skip connection), and iRNN (K=5). RNN and Fas- IRNN exhibit complex trajectories, while iRNN trajectory smooth. projecting initial point (black circle) onto the equilibrium surface (blue) and moving within it (green). This suggests that iRNN trajectory belongs
-ww-dimeniional manifold.
Variation of Equilibrium w.r.f. Input. As before, heg be an equilibrium solution for some tuple (him 1, J. It follows that,
(aI (aI- Vo(U( -m-1))++ Wxm + b)U) Vo(U(heg + hm- 1) + a. + b) Ox,,
This suggests that, whenever the input undergoes slow variation, we expect that the equilibrium point moves in such a way that Ußhee must lie in a transformed span of W. Now W E R Pxd with < D, which implies that (aI Vo(U((ee + hm-1) + W z. b)U is rank-deficient.
Low Rank Matrix Parameterization. For typical activation functions, note that whenever the argument is in the unsaturated regime, Veb(.) I. We then approximately get span(ol U) s span(W). We can express these constraints as U of + VV with low-rank matrices V e IR Dxdi, H E RdixD, and further map both Uhm and xm onto shared space. Since our experiments the signal vectors we encounter are low-dimensional, and sequential inputs vary slowly over time, we enforce this restriction in all our experiments. In particular, we consider,
Φ (hmm + 11--1) + Wxn. Fm + b)) (hum + hm-1) = 0.
The parameter matrix P E PxD maps the contributions from input and hidden states onto the same space. To decrease model-size we let P = U = (I VH) learn these parameters.
4 EXPERIMENTS
We organize this section as follows. First, the experimental setup, competing algorithms will be described. Then we present an ablative analysis to highlight salient aspects of iRNN and justify some of our experimental choices. We then plot and tabulate experimental results on benchmark datasets.
4.1 EXPERIMENTAL SETUP AND BASELINES
We choose competing methods based the following criteria: (a) methods that are devoid of additional application or dataset-specific heuristics, (b) methods that leverage only single cell/block/layer, and (c) methods without the benefit of complementary add-ons (such as gating, advanced regularization, model compression, etc.). Requiring (a) is not controversial since our goal is methodological. Conditions (C) are justifiable since we could also leverage these add-ons and are not germane to any particular method") We benchmark iRNN against standard RNN, LSTM (Hochreiter Schmidhuber 1997), (ungated) AntisymmetricRNN (Chang et al. 2019). (ungated) FastRNN (Kusupati et al. 2018).
Choice of Competing Methods:
TTheee conditions climinate some potential haselines. We provide specific justifications in the appendix A.S

---

Published as a conference paper at ICLR 2020
Scquance longth
Sequence length 200
0.43
0:33
io con)
2:23
Aeciorntppo (1Le00.01))
(AARIC-1)
(1081105)
2.22
2.5-
2.02
269
120
Traiting Stops
400
sco
1003
230
Training
900
(a)
(b)
Figure 3: Exploratory experiments for the Add task (a) Convergence with varying K: (b) Ratio || BhT
||/||
ahr
illustrates Vanishing/Exploding gradient (ll ohz and loss gradients are omitted but displayed in A.7.8 For
iRNN (a) and (b) together show strong correlation of gradient with accuracy in contrast to other methods.
Unitary RNN Variants. Results for methods based on unitary transitions (such as Arjovsky et al. (011)) Wisdom et al. (2016); Vorontsov et al. (2017); Zhang et al. (2018) are not reported in the main paper (when available reported in appendix) for the following reasons: (a) They are substantially more expensive, and requiring large model sizes; (b) Apart from the benchmark copy and add tasks, results tabulated by FastRNN and Antisymmetric authors (see Zhang et al. (2018); Chang et al. (2019) show that they are well below SOTA; (c) iRNN dominates unitary-RNN variants on add-task (see Sec. 4.:.Tp: (d) On copy task, while unitary invariants are superior. Vorontsov et al. (2017) attributes it to L or leaky ReLU activations. Leaky ReLUs allow for linear transitions, and copy task being a memory task benefits from it. With hard non-linear activation, unitary RNN variants can take up to 1000's of epochs for even 100-length sequences (Vorontsov et al. (2017)).
Implementation. For all our experiments, we used the parametrized update formulation in Eq. for iRNN. We used tensorflow framework for our experiments. For most competing methods apart from AntisymmetricRNN, which we implemented, code is publicly available. All the experiments were run on an Nvidia GTX 1080 GPU with CUDA and cuDNN 7.0 a machine with Intel Xeon 2.60 GHz CPU with 20 cores.
Datasets. Pre-processing and feature extraction details for all publicly available datasets are in the appendix A.44 We replicate benchmark test/train split with 20% of training data for validation to tune hyperparameters. Reported results are based on the full training set, and performance achieved on the publicly available test set. Table (Appendix) and A.4 details for all the data sets.
Hyper Parameters We used grid search and fine-grained validation wherever possible set the hyper-parametee parameters of each algorithm, or according to the settings published in (Kusupati et al.) 20188 Arjovsky et al. (016) (e.g. number of hidden states). Both the learning rate and 1/'s s were initialized to 10- The batch size of 128 seems to work well across all the data sets. We used ReLUU as the non-linearity and Adam (Kingma & Ba )2015) as the optimizer for all the experiments.
4.2 ABLATIVE ANALYSIS
We perform ablative analysis on the benchmark add-task (Sec 4 for sequence length 200 for 1000 iterations and explore mean-squared error as metric. Fig. 3 depicts salient results.
(a) Identity Gradients & Accuracy: iRNN accuracy is correlated with identity gradients. Increasing
K improves gradients, and correlates with increased accuracy (Fig. 3. While other models h,
adı- + 3U 7h) + W 2z), can realize identity gradients for suitable choices; linear (a 1,3 1,7 0, = 0), FastRNN (a x 1, 3 = 0, 7 0) and Antisymmetric (a 3 V VT | I 7), this goal may not be correlated with improved test accuracy. FastRNN() = 0.001), Ántisymmetric (7 = 0.01, e = 0.001) have good gradients but poorer test accuracy relative to FastRNN(n 0.01), Antisymmetric(y 0.01, e 0.1), with poorer gradients.
Identity gradient, whenever effective, must be capable of assigning credit to the informative parts, which in turn results in larger loss gradients, and significantly faster convergence with number of iterations. This is borne out in figure 3(a. a). iRNN for larger K is closer to identity gradient with fewer (unstable) spikes (K 1, 10). With K 10. iRNN converges within 300 iterations while competing methods take about twice this time (other baselines not included here exhibited poorer performance than the once plotted).
(b) Identity gradient implics faster convergence:
7

---

Published as a conference paper at ICLR 2020
Sequence length - 200
Sequencce length - 500
0.24
18.18
LSTH
0.30
Artuymmmnns FamilN
Artbymmans
0.25
0:30
PartBiiN
0.25
0.06
0:30
0.04
0.00
2035
6900
4000
10030
0.00
1050
8000
Toa Stroe
Thaining
(a)
(b)
Secuence longtth
Sequence langth 720
BCM
LSTH
LSTM
Aut syroortk
0.20
0.55
0.10
0.10
0.55
0.88
0.30
230
750
2003
1250
1990
1750
2000
250
500
150
1800
12ke
3500
3753
2005
Stpp
(c)
(d)
Figure 4: Following Arjovsky
Frrjowing/Ajjovsky et al. (016)) display average Cross Entropy for the Copy Task (Sequence
Length (with baseline memory strategy)): (a) 200 (0.09) (b) 500 (0.039). Mcan Squared Error for the Add Task, baseline performance is 0.167 (Sequence Length): : (c) 200 (d) 750. For both tasks, iRNN rums K = 5.
(c) SiRNN (iRNN with K 1 delivers good performane in some cases. Fig. a) illustrates that iRNN K = f5. 10} achieves faster convergence than SiRNN, but the computational overhead per iteration roughly doubles or triples in comparison. SiRNN is faster relative to competitors. For this reason, we sometimes tabulate only SiRNN, whenever is SOTA in benchmark experiments, since accuracy improves with K but requires higher overhead.
4.3 LONG-TERM DEPENDENCY AND OTHER TASKS
We list five types of datasets, all of which in some way require effective gradient propagation: (1) Conventional Benchmark LTD tasks (Add & Copy tasks) that illustrate that iRNN can rapidly learn long-term dependence; (2) Benchmark vision tasks (pixel MNIST, perm-MNIST) that may not require long-term, but nevertheless, demonstrates that iRNN achieves SOTA for short term dependencies but with less resources. (3) Noise Padded (LTD) Vision tasks (Noisy MNIST, Noisy CIFAR), where large noise time segment separates information segments and the terminal state, and so the learner must extract information parts while rejecting the noisy parts; (4) short duration activity embedded in a larger time- window (HAR-2, Google-30 in Appendix Table Table many others A.7). that usually arise in the context of smart 1oT applications and require a small model-size footprint. [Chang et al. (2019) further justify (3) and (4) as LTD, because for these datasets where only a smaller unknown segment(s) of a longer sequence informative. (5) Sequence- sequence prediction tasks (PTB language modeling) that are different from terminal prediction (reported in appendix A.7
4.3.1 STANDARD BENCHMARK LTD TASKS ADDITION & COPY MEMORY
Addition and Copy tasks (Hochreiter & Schmidhuber 1997) have long been used benchmarks in the literature to evaluate LTD (Hori et al., 2017] Zhang et al. 2018 Arjovsky et al., 2016)] Martens & Sutskever 2011). We follow the setup described in Arjovsky et al. (2016) create the adding and copying tasks. See appendix A.4 for detailed description. For both tasks we run iRNN with K = 5.
Figure 4 show the average performance of various methods on these tasks. For the copying task we observe that iRNN converges rapidly to the naive baseline and is the only method to achieve zero average cross entropy. For the addition task, both FastRNN and iRNN solves the addition task but FastRNN takes twice the number of iterations to reach desired O MSE. g In both the tasks,
Note that STM solves the addition problem in Arjovsky et al. 2016 only with more than 10k iterations.
We only use 2h iterations in our experiments demonstrate the effectiveness of our method.
8

---

Published as a conference paper at ICLR 2020
iRNN performance is much more stable across number of online training samples. In contrast, other methods either takes a lot of samples to match iRNN 's performance or depict high variance in the evaluation metric. This shows that iRNN converges faster than the baselines (to the desired error). These results demonstrate that iRNN easily and quickly learns the long term dependencies. We omitted reporting unitary RNN variants for Add and Copy task. See Sec. [4.] copy task. On Add-task we point out that our performance is superior. In particular, for the longer T 750 length, Arjovsky al. (2016), points out that MSE does not reach zero, and uRNN is noisy. Others either (Wisdom et al. 2016) do not report add-task or report only for shorter lengths (Zhang et al., 2018).
Table 1: Results for Pixel-by-Piie Pixel MNIST and Permuted MNIST datasets. K denotes pre-defined recursions embedded in graph reach equilibrium.
Accuracy (%)
Train Time (hr)
Data set
Algorithm
#Params
MixeI-MNIST
FastRNN
96.44
15.10
33k
RNN
94.10
45.56
14k
LSTM
97.81
26.57
53k
Antisymmetric
98.01
8.61
14k
iRNN (K=1)
97.73
2.83
4k
iRNN (K=3)
98.13
2.93
4k
Permute-MNISS
FastRNN
92.68
9.32
8.75k
LSTM
92.61
19.31
35k
Antisymmetric
93.59
4.75
14k
iRNN (K=1)
95.62
2,41
8k
4.3.2 NON LTD VISION TASKS: PIXEL MNIST, PERMUTE MNIST
Next, we perform experiments on the sequential vision tasks: (a) classification of MNIST images on pixel-by-pixee sequence; (b) fixed random permuted MNIST sequence (Lecun et al., 1998). These tasks typically do not fall the LTD categories (Chang et al. 2019). but are useful to demonstrate faster training, which can be attributed to better gradients.
For the pixel-MNIST task, Kusupati er (20T8) reports that takes significantly longer time for existing (LSTMs, Unitary, Gated, Spectral) RNNs converge to reasonable performance. In contrast, FastRNN trains at least 2x faster than LSTMs. Our results (table I for iRNN shows a 9r speedup relative LSTMs, and 2x speedup in comparison Antisymmetric. In terms of test accuracy, iRNN matches the performance of Antisymmetric, but with at least 3r fewer parameters. We did not gain much with increased K values For the permuted version of this task, we seem outperform the existing baselines [ In both tasks, iRNN trained at least 2r faster than the strongest baselines. These results demonstrate that iRNN converges much faster than the buselines with fewer parameters.
4.3.3 NOISE PADDING TASKS: NOISY-MNIST, NOISY-CIFAR
Additionally, as in Chang et al. (0119), we induce LTD by padding CIFAR-10 with noise exactly replicating their setup, resulting in Noisy-CIFAR. We extend this setting to MNIST dataset resulting in Noisy-MNIST. Intuitively we expect our model to resilient to such perturbations. We attribute iRNN's superior performance to the fact that it is capable of suppressing noise. For example, say noise is padded at > t and this results in W Wx, being zero on average. For iRNN the resulting states ceases be updated. So iRNV recalls last informative state hy (modulo const) unlike RNNs/variants! Thus information from signal component is possibly better preserved.
Results for Noisy-MNIST and Noisy- NoiSy-CIFAR shown in Table 2 Note that almost all timesteps contain noise in these datasets. LSTMs perform poorly on these tasks due to vanishing gradients. This
For some existing comparisons LSTM have achieved roughly 98.9 with dataset specific heuristics (Coiij comparison (and so have many others like (Kusupati al. 2018 /Zhan et al. 2018 Arjovsky et al. (0166).
al. (016)) hut could not achieve this performance
NNte that there's 8 no standard permutation the literature. This may be the main reason could not
replicate CChan 2019) performance on the permute MNIST task.

---

Published as a conference paper at ICLR 2020
Table 2: Results for Noise Padded CIFAR- 10 and MNIST datasets. Since the equilibrium surface smooth and resilient small perturbations, IRNN achieves better performance than the baselines with faster convergence.
Accuracy
Train
Data set
Algorithm
#Params
(%)
Time (hr)
Noisy-MNII
FastRNN
98.12
8.93
11k
LSTM
10.31
19.43
44k
Antisymmetric
97.76
5.21
10k
iRNN (K=1)
98.48
2.39
6k
Noisy-CIFAR
FastRNN
45.76
11.61
16k
LSTM
11.60
23.47
64k
Antisymmetric
48.63
5.81
16k
iRNN (K=1)
54.50
2.47
11.5k
is consistent with the earlier observations (Chang et al. 2019). iRNN outperforms the baselines very comprehensively on CIFAR-10, 10, while on MNIST the gains are smaller, as it's relatively easier task. These results show that iRNN is more resilient to noise and can account for longer dependencies.
Table 3: Results for Activity Recognition Datasets. iRNN outperforms the baselines on all metrics even with
K' = 1. Its worth noticing that although K = 5 increases test time, it's well within L.TM's numbers, the overall train time and resulting performance better than K
Accuracy (%)
Train Time (hr)
Test
Data set
Algorithm
#Params
Time (ms)
HAR-2
FastRNN
94.50
0.063
7.5k
0.01
RNN
91.31
0.114
7.5k
0.01
LSTM
93.65
0.183
16k
0.04
Antisymmetric
93.15
0.087
7.5k
0.01
iRNN (K=1)
95.32
0.061
4k
0.01
iRNN (K=5)
96.30
0.018
4k
0.03
Google-30
FastRNN
91.60
1.30
18k
0.01
RNN
80.05
2.13
12k
0.01
LSTM
90.31
2.63
41k
0.05
Antisymmetric
90.91
0.54
12k
0.01
iRNN (K=1)
93.77
0.44
8.5k
0.01
iRNN (K=5)
94.23
0.44
8.5k
0.05
4.3.4 SHORT DURATION EMBEDDED ACTIVITY RECOGNITION TASKS: HAR-2, GOOGLE-30
We interested in detecting activity embedded in longer sequence with small footprint RNNs (Kusupati et al. (2018): (a) Google-30 |Warden 2018), i.e. detection of utterances 30 commands plus background noise and silence, and (b) HAR-2 2 (Anguita et al. 2012). i.e. Human Activity Recognition from an accelerometer and gyroscope on a Samsung Galaxy S3 smartphone.
Table shows accuracy, training time, number of parameters and prediction time. Even with K 1. we compare well against competing methods, and iRNN accuracy improves with larger K. Interestingly, higher K yields faster training as well moderate prediction time, despite the overhead of additional recursions. These results show that iRNN outperforms baselines on activity recognition tasks, and fits within IoT/edge-dete device budgets.
5 CONCLUSION
Drawing inspiration from Rosenblatts Continuous RNNs, we developed discrete time incremental RNN (iRNN). Leveraging equilibrium properties of CTRNN, iRNN solves selloding/vanishing gradient problem. We show that iRNN improved gradients are directly correlated with improved test accuracy. A number of experiments demonstrate iRNNs responsiveness to long-term dependency tasks. In addition, due to its smooth fow-dimensional trajectories, it has a lightweight footprint that can be leveraged for IoT applications.
10

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGMENTS
The authors would like thank the Area Chair and the reviewers for their constructive comments. This work was supported partly by the National Science Foundation Grant 1527618, the Office of Naval Research Grant 90014-18-1-221 and by gift from ARM corporation.
REFERENCES
Kerem Altun, Billur Barshan, and Orkun Tunçel. Comparative study classifying human activities with miniature inertial and magnetic sensors. Pattern Recogn., 43010))3605-3620, October 2010. ISSN 0031-3203. doi: 10.1016/j. patcog.2010.00...0000 URL httphtt::2 /xxp www. wtt.d.oooooor//11111111.
0. patcco.... 201000000000 019
Davide Anguita, Alessandro Ghio, Luca Oneto, Xavier Parra, and Jorge L. Reyes-Ortiz. Human activity recognition on smartphones using a multiclass hardware-friendly support vector ma- chine. In Proceedings of the 4th International Conference on Ambient Assisted Living and Home Care. IWAAL'1 12, pp. 216 216-223, Berlin, Heidelberg, 2012. Springer- Apringer-Verlag. ISBN 978-3-642- 35394-9. doi: 10.
URL http:/ dx. oog.
978 378-3-642-2 35395-55355555 30]
Martin Arjovsky, Amar Shah, and Yoshua Bengio. Unitary evolution recurrent neural networks. In International Conference on Machine Learning. pp. 1120-1128 2016.
David Balduzzi and Muhammad Ghifary. Strongly-typed recurrent neural networks. In Proceedings of The 33rd International Conference on Machine Learning, pp. 1292-1300, 2016.
Y. Bengio, P. Simard, and P. Frasconi. Learning long-term dependencies with gradient descent is difficult. Trans, Newr Netw., 5(2:15566) March I 1994, ISSN 1045-9227. doi: 10. (0.1109/72.77118.
URL http:ttp:///x doi http:///wx...i..ogg111111111311 wtt.:/...oo1111111/22....0
Yoshua Bengio, Nicolas Boulanger-Lewwaddowsk and Razvan Pascanu. Advances in optimiz- ing recurrent networks. 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 8624-8628, 2013.
James Bradbury, Stephen Merity, Caiming Xiong, and Richard Socher. Quasi-recurrent neural networks. CoRR, /t////111015577 2016. URL
01576
Víctor Campos, Brendan Jou, Xavier Giró-i Nieto, Jordi Torres, and Shih-Fu Chang. Skip rnn: Learning to skip state updates in recurrent neural networks. arXiv preprint 1rXiv:1708.06834 2017.
Bo Chang, Minmin Chen, Eldad Haber, and Ed Chi. AntisymmetricNN: A dynamical system view recurrent neural networks. In International Conference Learning Represeniations, 2019. URL BRR[sttps://ppezeviiee
n wtt..ete/orua.aaa.yeeoollooooooo
Shiyu Chang, Yang Zhang, Wei Han, Mo Yu, Xiaoxiao Guo, Wei Tan, Xiaodong Cui, Michael Witbrock, Mark A Hasegawa-Johnson, and Thomas S Huang. Dilated recurrent neural networks. In Advances in Neural Information Processing Systems, pp. 77-87, 2017.
Tian Qi Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary dif- ferential equations. In Advances in Neural Information Processing Systems, pp. 6571-6583, 2018.
Kyunghyun Cho, Bart Van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. On the properties of neural machine translation: Encoder-decoder approaches. arXiv preprint arXiv: arXiv:1409, 4409. /259, 2014.
Jasmine Collins, Jascha Sohl-Dickstein, and David Sussillo. Capacity and Trainability in Recurrent Neural Networks. arXiv e-prints, art. MeXXiv:1611.. 1.09913, November 2016.
Tim Cooijmans, Nicolas Ballas, César Laurent, Çağlar Gülçehre, and Aaron Courville. Recurrent batch normalization. arXiv preprint arXiv:1603, 09025, 2016.
Ron Dembo, Stanley Eisenstat, and Trond Steihaug. Inexact newton methods. SIAM Journal on Numerical analysis, 19(2):400-405 1982.
11

---

Published as a conference paper at ICLR 2020
Chengyue Gong, Di He, Xu Tan, Tao Qin, Liwei Wang, and Tie- Yan Liu. Frage: frequency-agnostt word representation. In Advances in Neural Information Processing Systems, pp. 1334-1344 1345, 2018.
Alex Graves. Adaptive computation time for recurrent neural networks. CoRR, abs/ abs/1603.08953
2016. URLp:t/://axxi wrg. haag//ab//// htt///aa//11.... 1603. 1t1.//113300111333
Michiel Hermans and Benjamin Schrauwen. Training and analysing deep recurrent neu- ral networks. In C. J. C. Burges, L. Bottou, M. Welling. Z. Ghahramani, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 26, pp. 190-198. Curran Associates, Inc., 2013. URL htttp://papers....... http:/ppprrs.iss...... nips. wwwpscccppppprr haw.a/g-uuuc-naalll.eoeeeeeee-e-
Josef zen. SeppHochreiter 9ww.11999hhhhiiii werrdvissrSshhmicc www.orsschhicuuberr.... chuber. wwt.diaaaaa....aaaaaeeeeee
Hochreiter.
Untersuchungen
dynamischen neuronalen net-
1991.
URL http: /ttp::/eepppp..e..m
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural compulation, 9(8):
1735-1780, 1997.
Chiori Hori, Takaaki Hori, Teng- Yok Lee, Ziming Zhang, Bret Harsham, John Hershey, Tim K Marks, and Kazuhiko Sumi. Attention-based multimodal fusion for video description. In ICCV, pp. 4203-4212, 2017.
Herbert Jaeger, Mantas Lukosevicius, Dan Popovici, and Udo Siewert. Optimization and applications of echo state networks with leaky-integrator neurons. Neural networks the official journal of the International Neural Network Society, 20:335-52, 05 2007. doi: 10. ne.1016)..euumee20077 2007.04.076
Li Jing, Yichen Shen, Tena Dubcek, John Peurifoy, Scott Skirlo, Yann LeCun, Max Tegmark, and Marin Soljačíé. Tunable efficient unitary neural networks (eunn) and their application to mns. In International Conference on Machine Learning, pp. 1p..1733... 1733-1741, 2017.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICML, 2015.
Aditya Kusupati, Manish Singh, Kush Bhatia, Ashish Kumar, Prateek Jain, and Manik Varma. Fastgrnn: A fast, accurate, stable and tiny kilobyte sized gated recurrent neural network. In Advances in Neural Information Processing Systems, 2018.
Yann Lecun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. In Proceedings of the IEEE, pp. 2278-2324, 1998.
Tao Lei, Yu Zhang, Sida I. Wang, Hui Dai, and Yoav Artzi. Simple recurrent units for highly parallelizable recurrence. In Empirical Methods in Natural Language Processing (EMNLP), 2018.
James Martens and Ilya Sutskever. Learning recurrent neural networks with hessian optimization. In Proceedings of the 28th International Conference on Machine Learning (ICML-I1), pp. 1033- 1040, 2011.
Zakaria Mhammedi, Andrew D. Hellicar, Ashfaqur Rahman, and James Bailey. Efficient orthogonal parametrisation of recurrent neural networks using householder reflections. CoRR, 10000, 2016. URL
org
Asier Mujika, Florian Meier, and Angelika Steger. Fast-slow recurrent neural networks. In Advances in Neural Information Processing Systems, pp. 5915-5924, 2017.
Murphy Yuezhen Niu, Lior Horesh, and Isaac Chuang. Recurrent neural networks in the eye of differential equations. arXiv preprint arXiv: /904. 12933, 2019.
Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, and Yoshua Bengio. How to construct deep recurrent neural networks. arXiv preprini arXiv:1312.6033 2013a.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International Conference on Machine Learning, pp. 1310-1318, 2013b.
Razvan Pascanu, Çaglar Gülçehre, Kyunghyun Cho, and Yoshua Bengio. How to construct deep recurrent neural networks. CoRR, abs/1311.6022. 2013c.
12

---

Published as a conference paper at ICLR 2020
Jeffrey Pennington, Samuel Schoenholz, and Surya Ganguli. Resurrecting the sigmoid in deep learning through dynamical isometry: theory and practice. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus. S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 4785-4795. 2017.
Rosenblatt. Principles of neurodynamics. Spartan Books, Washington, D.C., 1962.
Yulia Rubanova, Ricky T. Q. Chen, and David Duvenaud. Latent odes for inegularty-ssampled time series. CoRR, abs/1907 abs/1907.03307,, 2019. URL Bt..pttp::/aaxxw..or////// 03907
Sachin S Talathi and Aniket Vartak. Improving performance of recurrent neural network with relu nonlinearity. arXiv preprint /rXiv:/511.0377 2015.
Eugene Vorontsov, Chiheb Trabelsi, Samuel Kadoury, and Chris Pal. On orthogonality and learning recurrent networks with long dependencies. In ICML, pp. 3570-3578, 2017. http
//proceedings ml press / 2070//oronttso/ 7a (tt.mmlllll
Pete Warden. Speech Commands: A Dataset for Limited- Vocaluulryy Speech Recognition. arXiv e-prints, art, arXiv: 804,03209, April 2018.
Scott Wisdom, Thomas Powers, John Hershey, Jonathan Le Roux, and Les Atlas. Full- capacity unitary recurrent neural networks. In D. D. Lee, M. Sugiyama, U. V. Luxburg, Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29. pp. 4880 4888. Curran Associates, Inc., 2016. hRL.http://poot 6327-
Inc. Yelp. Yelp dataset challenge. 2017. URL https://wwwt http:eeppp.cmmamseeeeeeeee
chal lenge
Jiong Zhang, Qi Lei, and Inderjit S. Dhillon. Stabilizing gradients for deep neural networks via efficient svd parameterization. In ICMI., 2018
Jiong Zhang, Lei, and Inderjit S Dhillon. Stabilizing gradients for deep neural networks via 093227, 2018.
efficient SVD parameterization. arXiv preprint
Julian Georg Zilly, Rupesh Kumar Srivastava, Jan Koutník, and Jürgen Schmidhuber. Recurrent highway networks. ICML, pp. 4189-4198. JMLR. org, 2017.
A APPENDIX
A.I MULTI-LAYER DEEP RNN NETWORKS.
We point out in passing that our framework readily admits deep multi-layered networks within single time-step. Indeed our setup is general; it applies to shallow and deep nets; small and large time steps. As a case in point, the Deep Transition RNN Pascanu al. (001cc):
hm+11 Sn (hm; (m+
(. W (Uhm + W Wxm+1))
readily accounted by Theorem in an implicit form:
hm+1 (hm + hm Im+1) - hm-
So is Deep-RNN Hermans & Schrauwen (2013). The trick is to transform hm hy hm+ and hm+1 - fim + hm++1- As such, all we need is smoothness of fh. which has no restriction on # layers. On the other hand, that we do not have to limit the number of time steps is the point of Theorem which asserts that the partial differential of hidden states (which is primarily why vanishing/exploding gradient arises Pascanu al. (2013b) the first place) is identity!!
A.2 PSEUDO CODE AND IMPLEMENTATION
Given input sequence and iRNN model parameters, the hidden states be generated with the help of subroutine [ This routine can be plugged into standard deep learning frameworks such as Tensorflow/PyTTon learn the model parameters via back-propagation.
13

---

Published as a conference paper at ICLR 2020
Algorithm 1: Pseudo Code for computing iRNN hidden states for one input sequence
Data: Input sequence {Tm )
Require: Number of recursion steps K, Model parameters (U, W, a, (mm))t
Initial hidden state ho = for to T do Initialize go to zero or hm-1
for k 1 to K do
9h 1 + m/ (Ø(U(gh-1 + hm-1) + Wam - a(gg-11 hm-1))
hmm OK
Output: hidden states {mm T
m==1
Table 4: Dataset Statistics & Long Term Dependence
Avg. Activity
Input Time
Sequence Ratio
Dataset
#Train
#Fts
#Steps
#Test
Time
Google-30
25ms
1000ms
3/99
51,088
32
99
6,835
HAR-2
256ms
2560ms
13/128
7,352
128
2,947
Noisy-MNIST
28
1000
7/250
60,000
28
1000
10,000
Noisy-CIFAR
32
1000
4/125
60,000
96
1000
10,000
Pixei-MNIST
60,000
784
10,000
Permuted-MNIS:
60,000
784
10,000
A.3 CONVERGENCE GUARANTEES FOR GENERAL LEARNING RATES.
Theorem (Local Convergence with Linear Rate). Assume that the function F(g.) & ((U h2-1) + wa + b) - (g, + hx-1) and the parameter Ti in Eq. satisfies
(5)
[nk 112 (FF()) + 2n F(g.) F( VVF(g))(()) Vk,
(10)
Then there exists > such that if llgo- - hegll S e where heg denotes the fixed point, the sequence gi generated by the Euler method converges to the equilibrium solution in Megg (hx-1, locally with linear rate.
The proof is based on drawing a connection between the Euler method and inexact Newton methods, and leverages Thm. 2.3 in Dembo et al. (1982). See appendix Sec. A.8.1 Thm. and Sec. A.7.5 (for proof, empirical verification).
Corollary 1. I Thk V()))l 1, Vi, the forward propagation (Eq. 139 is stable and the sequence }g converges locally at a linear rate.
The proof is based on Thm. 2.3 in Dembo et al. 19822. Thm. and Prop. 2 in Chang et al. 2019).
See appendix A.8. I Corollary
A.4 DATASET DETAILS
Table table 6 lists the statistics of all the datasets described below.
Google-12 Google-30: Google Speech Commands dataset contains second long utterances of 30 short words (30 classes) sampled at 16KHz. Standard log del-filter-bakk featurization with 32 filters over a window size of 25ms and stride of 10ms gave 99 timesteps of 32 filter responses for 1-second audio clip. For the 12 class version, 10 classes used in Kaggle's Tensorflow Speech Recognition challengd were used and remaining two classes were noise and background sounds (taken randomly from remaining 20 short word utterances). Both the datasets were zero mean unit variance normalized during training and prediction.
recognition-challenge
14

---

Published as a conference paper at ICLR 2020
Human Activity Recognition (HAR) dataset was collected from accelerometer and gyroscope on a Samsung Galaxy S3 smartphone. The features available on the repository were directly used for experiments. The 6 activities were merged to get the binarized version. The classes Sitting, Laying, Walking_ Walking_Upstairs and Standing, Walking, Walking_Downstaiin were merged to obtain the two classes. The dataset was zero mean unit variance normalized during training and prediction.
HAR-1
Penn Treebank: 300 length word sequences were used for word level language modeling task using Penn Treebank (PTB) corpus, The vocabulary consisted of 10,000 words and the size of trainable word embeddings was kept the same as the number of hidden units of architecture. This is the setup used in (Kusupati et al. 2018 Zhang et al. 2018).
PiXel-MNIST:
Pixel-by-pixel version of the standard MNIST-10 dataset The dataset was zero mean- unit variance normalized during training and prediction.
This is similar to PixeI-MNIST, except its made harder by shuffling the pixels with fixed permutation. We keep the random seed as 42 to generate the permutation of 784 pixels.
Permuted-MNIST:
Noisy-MNIST: To introduce more long-range dependencies to the Pixel-MNISS task, we define a more challenging task called the Noisy-MNIST, inspired by the noise padded experiments in Chang et al.] (209).. Instead of feeding in one pixel at one time, we input each row of MNIST image at every time step. After the first 28 time steps, we input independent standard Gaussian noise for the remaining time steps, Since a MNIST image is of size 28 with RGB channels, the input dimension is m 28. The total number of time steps is set to T = 1000. In other words, only the first 28 time steps of input contain salient information, all remaining 972 time steps are merely random noise. For model to correctly classify imput image, it has to remember the information from long time ago. This task is conceptually more difficult than the pixel-by-pixel MNIST, although the total amount of signal in the input sequence is the same.
Noisy-CIFAR This is exactly replica of the noise paded CIFAR task mentioned in Chang et al. (2019). Instead of feeding in one pixel one time, we input each row of CIFAR-10 image at every time step. After the first 32 time steps, we input independent standard Gaussian noise for the remaining time steps. Since a CIFAR-10 image of size 32 with three RGB channels, the input dimension is m = 96. The total number of time steps is set to T = 1000. In other words, only the first 32 time steps of input contain salient information, all remaining 968 time steps are merely random noise. For model to correctly classify an input image, it has to remember the information from long time ago. This task is conceptually more difficult than the pixel-by-pin -iieeel CIFAR-10, although the total amount of signal in the input sequence is the same.
Addition Task: We closely follow the adding problem defined in (Arjovsky et al. 2016 Hochreiter
& Schmidhuber 1997) to explain the task at hand. Each input consists of two sequences of length T.
The first sequence, which we denote v, consists of numbers sampled uniformly at random 24 1]. The second sequence is an indicator sequence consisting of exactly two entries of 1 and remaining entries O. The first entry is located uniformly at random in the first half of the sequence, whilst the second 1 entry is located uniformly random in the second half. The output is the sum of the two entries of the first sequence, corresponding to where the entries are located in the second sequence. naive strategy of predicting as the output regardless of the input sequence gives an expected mean squared error of 0.167, the variance of the sum of two independent uniform distributions.
Copying Task: Following a similar setup to (Arjovsky et al., 2016 Hochreiter & Schmidhuber 1997), we outline the copy memory task. Consider 10 categories, {a: The input takes the form of T + 20 length vector of categories, where we test over a range of values of T. The first 10 entries are sampled uniformly, independently and with replacement from {a:) and represent the sequence which will need to be remembered. The next T entries are set to ag which can be thought of as the 'blank' category. The next single entry is ag. which represents delimiter, which should indicate to the algorithm that it is now required to reproduce the initial 10 categories in the output. The remaining 10 entries are set to ag. The required output sequence consists of T + 10 repeated entries of ag, followed by the first 10 categories of the input sequence in exactly the same order. The goal is to minimize the average cross entropy of category predictions at each time step of
shttps//archivv.iessuuii www.iicc...ccuuuuoecu wttpa//c.cccc.cccaaaaooooooooarr smartphones
http:///yan.llcum. com/exdh/mnist/
15

---

Published as a conference paper at ICLR 2020
the sequence. The task amounts having to remember categorical sequence of length 10, for T time steps.
A simple baseline be established by considering an optimal strategy when memory is available. which we deem the memoryless strategy. The memoryless strategy would be to predict ag for T+ + 10 entries and then predict each of the final 10 categories from the set [o:)?_n i=0 independently and uniformly at random. The categorical cross entropy of this strategy 10log(8)
7+20
DSA-19
This dataset is based on Daily and Sports Activity (DSA) detection from a resource- constrained IoT wearable device with Xsens MTx sensors having accelerometers, gyroscopes and magnetometers on the torso and four limbs. The features available on the repository were used for experiments. The dataset was zero mean unit variance normalized during training and prediction.
Yelp-5: Sentiment Classification dataset based the text reviews 1T The data consists of 500,000 train points and 500,000 test points from the first million reviews. Each review was clipped or padded to be 300 words long. The vocabulary consisted of 20000 words and 128 dimensional word embeddings were jointly trained with the network.
A.5 BASELINE JUSTIFICATION
In our experiments section, we stated that some of the potential baselines were removed due to experimental conditions enforced in the setup. Here clearly justify our choice. Mostly the reasoning is to avoid comparing complementary add-ons and compare the bare-bone cells.
Cooijmans et al. (0016) is removed since its an add-on and can be applied to any method. Besides its pixel-min mnist results involve dataset specific heuristics.
Gong et al.
2018 also an add-on and hence can be applied any method.
Zilly al.
(2017) Pascanu et al. (2013);; Mujika al. (2017) denote deep transitioning methods. They are add-ons for any single recurrent block and hence can be applied to any recurrent cell.
Gating variants of single recurrent cells (Chang et al. 2019 Kusupati et al. 2018 have also been removed. Since iRNN can be extended to a gating variant and hence its just an add-on.
Table 5: Various haper-parameters reproduce results
Dataset
Hidden Units
Google-30
80
HAR-2
80
Pixel-MNIST
128
Permuted-MNIIS
128
Noisy-MNIST -NIITT
128
Noisy-CIFAR
128
Addition Task
128
Copying Task
128
PTB
256
A.6 HYPER-PARAMER PARAMETERS FOR REPRODUCIBILITY
We report various sypeeeparameters earlier we mainly use 'ReLU' as the -oneariyyy and Adam as the optimizer. Apart from this, other hyper-parameters mentioned in table
in experiments for reproduciblity. As mentioned
16

---

Published as a conference paper at ICLR 2020
Table 6: Other Dataset Statistics & Long Term Dependence
Avg. Acitivity
Input
Sequence Ratio
Dataset
#Train
#Fts
#Steps
#Test
Time
Time
Google-12 12
25ms
1000ms
3/99
22,246
32
99
3,081
DSA-19
500ms
5000ms
13/125
4,560
45
125
4,560
Yelp-5
20
300
1/15
500,000
128
300
500,000
PTB
929,589
300
300
82,430
Scouence length
Seauance longth
0.43
0.40
6.33
1STM4
0.35
LSTH
0.30
6:15
0:15
0.0
0.20
250
500
150
10:00
1250
1500
1750
2000
250
500
1000
1250
3506
1750
2000
(a)
(b)
Figure 5: Mean Squared Error shown for the Add Task (Sequence Length): (c) 100 (d) 400
A.7 ADDITIONAL EXPERIMENTS
A.7.1 COPYING AND ADDITION TASKS
Figure 5 shows the results for remaining experiments for the addition task for length 100, 400.
Table Results for Pixel-by- bixeix MNIST and Permuted MNIST datasets. K denotes pre-defined
recursions embedded in graph to reach equillibrium.
Accuracy (%)
Train Time (hr)
Data set
Algorithm
#Params
Pixel-MNIST
FastRNN
96.44
15.10
33k
FastGRNN-LSQ
98.72
12.57
14k
RNN
94.10
45.56
14k
SpectraIRNN
97.7
6k
LSTM
97.81
26.57
53k
URNN
95.1
16k
Antisymmetric
98.01
8.61
14k
iRNN (K=1)
97.73
2.83
4k
iRNN (K=2)
98.13
3.11
4k
iRNN (K=3)
98.13
2.93
4k
-NIIT
FastRNN
92.68
9.32
8.75k
SpectraIRNN
92.7
8.5k
LSTM
92.61
19.31
35k
URNN
91.4
12k
Antisymmetric
93.59
4.75
14k
iRNN (K=1)
95.62
2.41
8k
17

---

Published as a conference paper at ICLR 2020
A.7.2 TRADITIONAL DATASETS
Table shows the results including left out baselines for Pixel-MNIST and permute-MNIST task. Here also include rating prediction scale of to 5 of Yelp reviews Yelp (017)) Table shows the results for this dataset.
Table 8: Results for Yelp Dataset.
Accuracy
Model Size (KB)
Train Time (hr)
Test Time (ms)
Data Algorithm
#Params
(%)
Yelp-5
FastRNN
55.38
130
3.61
0.4
32.5k
FasIGRNN-LSQ
59.51
130
3.91
0.7
32.5k
FastGRNN
59.43
8
4.62
RNN
47.59
130
3.33
0.4
32.5k
SpectraIRNN
56.56
89
4.92
0.3
22k
EURNN
59.01
122
72.00
LSTM
59.49
516
8.61
1.2
129k
GRU
59.02
388
8.12
0.8
97k
Antisymmetric
54.14
130
2.61
0.4
32.5k
UGRNN
58.67
258
4.34
iRNN (K=1)
58.16
97.67
0.31
0.4
25k
iRNN (K=2)
59.01
98.84
0.31
0.7
25k
iRNN (K=3)
59.34
100
1.16
1.0
25k
A.7.3 ACTIVITY RECOGNITION DATASETS
We also include activity recognition tasks: (a)Google-12 Warden (2018) i.e. detection utterances of 10 commands plus background noise and silence and (b) DSA-19 al. (2010), Daily and Sports Activity (DSA) detection from a resource-constraine loT wearable device with 5 Xsens MTx sensors having accelerometers, gyroscopes and magnetometers the torso and four limbs. Table 9 shows results for these activities along with some other baselines for activity recognition tasks mentioned in Sec. and described in Sec. A.4
A.7.4 PTB LANGUAGE MODELLING
We follow (Kusupati et al. 2018 Zhang et al. 2018) to setup our PTB experiments. We only pursue one layer language modelling. but with more difficult sequence length (300). Table 10 all the evaluation metrics for the PTB Language modelling task with layer as setup by Kusupati et al. (2018), including test time and number of parameters (which omitted from the main paper due lack of space).
A.7.5 LINEAR RATE OF CONVERGENCE TO FIXED PoI
Empirically verify the local convergence fixed point with linear rate by comparing the Euclidean distance
between the approximate solutions, ha(²) using Eq. 11 with 9o = and the fixed points, h, computed using initial- ized suitably and then fixed. We illustrate our results Fig. 6 which clearly demonstrates that the approximate solutions tend to converge with linear rate.
0.039
0.038
FSOLVE from SCIPY. The learnable parameters
0.037
0.038
Figure 6: Linear convergence iRNN
= 9t-1 + + h--1) + Wa, + b) a(gi-1 h+-1))
(11)
b 9K
18

---

Published as a conference paper at ICLR 2020
A.7.6
THEORETICAL VERIFICATION
Here include some experiments show that our theoretical assumptions hold true.
1e7
2.5
2.0
1.5
1.0
0.5
0.0
-100
-80
-60
-40
-20
0
Figure 7: Histogram of the eigenvalues of VoU I for IRNN HAR-2 2 dataset.
Non-Singularity of the matrix D For our iRNN parametrization to satisfy the conditions having equillibrium points be locally asymptotically stable, the eigen values of the matrix D (Vo(-)U 7T) should be negative. We plot a histogram the eigenvalues /) for all the points in the HAR-2 dataset. As illustrated in the figure all the eigenvalues are negative.
A.7.7 IDENTITY GRADIENT COMPARISON iRNN vs RNN
To verify Theorem. empiriially, train RNN and iRNN the HAR-2 data set (see more details in Sec. respectively, and plot in Fig. the magnitude of gradient of the last layer hy W.E.f. the first
-1
RMN ERKY
-50
30000
Batchees
(a)
Figure Comparison between RNN and iRNN on the magnitudes of gradients.
19

---

Published as a conference paper at ICLR 2020
layer h1 in log scale confirm that our approach leads to vanishing exploding gradients when the error is back-propagated through time. We also conducted experiments to verify that the gradient of iRNN is norm preserving (see Sec. A.7.8 and Figure -3). As
clearly, RNN suffers from serious vanishing gradient issue training, while iRNN's backpropagated gradients is close to 1, and the variance arises mainly our approximation of fixed points and stochastic behavior in training networks, demonstrating much better training stability of iRNN.
A.7.8 GRADIENT NORM W.R.T. LOSS
In addition to the gradient ratio we plot in Sec captured in earlier works (Arjovsky et al. 2016; Zhang et al. 2018). Le. the gradient norm w.r..
4.2
we also show in figure 9 the more popular quantity
loss 0L ||- We emphasize that this quantity alone is misleading in the context of resolving the 8h,
issue of vanishing/exploding gradients. Since
Shg =
āhr
* akr ||. The long term component |l could become zero by the virtue
controlling the gradients is || 0hr Il. but the other component, ll aL that the loss is nearly zero. This happens in our addition task experiment, because MSE is close to zero, we experience nearly 0 value for this quantity. But this is clearly because the MSE is O. Also note that none of graphs have log scale, which is not the case in earlier works. The conclusion that can be drawn from the loss-gradient is that is somewhat stable, and can inform us about quality of convergence.
abrr
We also plot |l الجلج in figure in order show that indeed iRNN achieves identity gradients
everywhere in the time horizon, since fig. had shown that the ratio of for iRNN.
0hr
and
8br
lquuals 1
dh,
0br-1
A.7.9 DIFFERENT ACTIVATION FUNCTION
We also performed some experiments for sigmoid activation on HAR-2 dataset. The results for this variant also follow similar pattern as we saw ReLU variant.
A.8
PROOFS
A.8.1
LOCAL CONVERGENCE WITH LINEAR RATE
Recall that we rewrite the fixed-pun seed-pointtoo constraints in iRNN as the following ODE:
(1) F(g.) def ((i + hx-1) + Wa + b) (gi + hx-1);; s(0) 0.
(12)
Then based on the Euler method, we have the following update rule for solving fxed-pointe
9i+1 91 + 1k (1) F(g))
(13)
(4) = 94 + 1k (Q + h2-1) + Wxx + 6) (g. + 1xx-1)]-
(14)
Inexact Newton methods Dembo al. (1922) refer a family of algorithms that aim solve the equation system F(z) = 0 approximately at each iteration using the following rule:
1;+1 = 2, + 8,, ri = F(z:) + V F(:))s;
(15)
where F denotes the (sub)gradient of function F, and r, denotes the error the i-th iteration between F(z;) and 0.
By drawing the connection between Eq. 13 and Eq. 15
set = 9: and s; 7% (3)
F(g:). Then
based on Eq. 15 we have
F(g.) + Th 4
VF(g))F(().
(16)
Lemma (Thm. 2.3 in Dembo et al. (1922). ). Assume that
|rill
<T<,
(17)
F())]]
where || denotes arbitrary norm and the induced operator norm. There exists >> 0 such that, if F| 2.11 S E, then the sequence of inexact Newton iterates {2+} converges to 2,. Moreoven, the
convergence is linear in the sense that [|
2.l1. I T||2 2.|1., where ||y||_ || F(.))))l
20

---

Published as a conference paper at ICLR 2020
Sequence length = 200
5
LSTM
FastR\NN(eta=0.01)
4
FastRWW(tta=0.001)
Antésmm(==0.0.e=00.1
aaL an
Artisymm(g=0001.e=000001
Gradient norm
iRNN(K=1)
iRNN(K=5)
iRNN(K= 10)
1
-1
0
200
400
600
800
1000
Training Steps
(a)
Sequence length 200
3.0
LSTM
FastRNN(eta=0.01)
2.5
FastRNW(eta=0.001)
Antisym(g=0.00.e=0011
-1
Gradient norm ahr
2.0
Antisymf(==0.01.==00001]
iRNN(K=1)
iRNN(K=5)
1.5
iRNN(K=10)
1.0
0.5
0.0
200
400
600
800
1000
Training Steps
bb)
Figure 9: Exploratory experiments for the Add task (a) Gradient norms w.r.t. loss |1 ||. (b)
Gradient norms 3kr-, |]. This together with Figure 3 shows that the gradients are identity everywhere
Ahr
for 10
21

---

Published as a conference paper at ICLR 2020
Theorem (Local Convergence with Linear Rate), Assune that the function F in Eq. 12 and the (8)
parameter Ti Eq.
satisfy
Mk
(s) (
2n
O, Vk.
(18)
Then there exists O such that if l1go heg S where heg denotes the fixed point, the sequence {g:} generated by the Euler method converges to the equilibrium solution in Mag (hg- TK) locally
with linear rate.
Proof. By substituting Eq. into Eq. 17
to prove local convergence we need to guarantee
(g:))
+ M ((.))) < <
(6)
(19)
By taking the square of both sides in Eq. we can show that Eq. 19 equivalent Eq. then complete our proof.
18 We
Corollary 2. Assume that || Tik V F(:))l 1i,i, Vk holds. Then the forward propagation using Eg. 13 is stable and our sequence {gi) converges locally with linear rate.
Proof. By substituting Eq. 16 into Eq. and based on the assumption in the corollary, we have
|rrll
(g.)).) + 7p
(8) VF()))(())
[F()))]
[1(9))
[ 1k
V ((g)) (1
< 1.
(20)
[()))
Further based Prop. in Chang et al. (2019) and Thm. 2 we then complete our proof.
22

---

Published as a conference paper at ICLR 2020
Table 9:
Results for Activity Recoginition Datasets.
Accuracy
Model
Train
Test Time (ms)
Data set
Algorithm
#Params
(%)
Size (KB)
Time (hr)
HAR-2
FastRNN
94.50
29
0.063
0.01
7.5k
FastGRNN-LSQ
95.38
29
0.081
0.03
7.5k
FasIGRNN
95.59
3
0.10
RNN
91.31
29
0.114
0.01
7.5k
SpectraIRNN
95.48
525
0.730
0.04
134k
EURNN
93.11
12
0.740
LSTM
93.65
74
0.183
0.04
16k
GRU
93.62
0.130
0.02
16k
Antisymmetric
93.15
29
0.087
0.01
7.5k
UGRNN
94.53
37
0.120
iRNN (K=1)
95.32
17
0.061
0.01
4k
iRNN (K=3)
95.52
17
0.081
0.02
4k
iRNN (K=5)
96.30
18
0.018
0.03
4k
DSA-19
FastRNN
84.14
97
0.032
0.01
17.5k
FastGRNN-LSQ
85.00
208
0.036
0.03
35k
FasIGRNN
83.73
3.25
2.10m
RNN
71.68
20
0.019
0.01
3.5k
SpectralRNN
80.37
50
0.038
0.02
8.8k
LSTM
84.84
526
0.043
0.06
92k
GRU
84.84
270
0.039
0,03
47k
Antisymmetric
85.37
32
0.031
0.01
8.3k
UGRNN
84.74
399
0.039
iRNN (K=1)
88.11
19
0.015
0.01
3.5k
iRNN (K=3)
85.20
19
0.020
0.02
3.5k
iRNN (K=5)
87.37
20
0.005
0.03
3.5k
Google-12
FastRNN
92.21
56
0.61
0.01
12k
FastGRNN-LSQ
93.18
57
0.63
0.03
12k
FasIGRNN
92.10
5.5
0.75
RNN
73.25
56
1.11
0.01
12k
SpectraIRNN
91.59
228
19.0
0.05
49k
EURNN
76.79
210
120.00
LSTM
92.30
212
1.36
0.05
45k
GRU
93.15
248
1.23
0.05
53k
Antisymmetric
89.91
57
0.71
0.01
12k
UGRNN
92.63
75
0.78
iRNN (K=1)
93.93
36
0,20
0.01
8.1k
iRNN (K=3)
94.16
37
0.33
0.03
8.1k
iRNN (K=5)
94.71
38
0.17
0.05
8.1k
Google-30
FastRNN
91.60
96
1.30
0.01
18k
FastGRNN-LSQ
92.03
45
1.41
0.01
8.5k
FastGRNN
90.78
6.25
1.77
RNN
80.05
63
2.13
0.01
12k
SpectraIRNN
88.73
128
11.0
0.03
24k
BURNN
56.35
135
19.00
LSTM
90.31
219
2.63
0.05
41k
GRU
91.41
257
2.70
0.05
48.5k
Antisymmetric
90.91
64
0.54
0.01
12k
UGRNN
90.54
260
2.11
iRNN (K=1)
93.77
44
0.44
0.01
8.5k
iRNN (K=3)
91.30
44
0.44
0.03
8.5k
iRNN (K=5)
94.23
45
0.44
0.05
8.5k
23

---

Published as a conference paper at ICLR 2020
Model Size (KB)
Train
Test Time (ms)
Algorithm
Test Perplexity
#Params
Time (min)
FastRNN
127.76
513
11.20
1.2
52.5k
FastGRNN-LSQ
115.92
513
12.53
1.5
52.5k
FastGRNN
116.11
39
13.75
RNN
144.71
129
9.11
0.3
13.2k
SpectraIRNN
130.20
242
0.6
24.8k
LSTM
117.41
2052
13.52
4.8
210k
UGRNN
119.71
256
11.12
0.6
26.3k
iRNN (K=1)
115.71
288
7.11
0.6
29.5k
Table 10: PTB Language Modeling: Layer. To be consistent with our other experiments we used low-dim U; For this size our results did not significantly improve with K. This is the dataset of Kusupati et al. (2018) which uses sequence length 300 as opposed to 30 in the conventional PTB.
Accuracy (%)
Model Size (KB)
Train Time (hr)
Data set
Algorithm
Activation
#Params
HAR-2
RNN (K=1)
95.32
17
0.061
ReLU
4k
iRNN (K=3)
95.52
17
0.081
ReLU
4k
iRNN (K=5)
96.30
18
0.018
ReLU
4k
iRNN (K=1)
92.16
17
0.065
Sigmoid
4k
iRNN (K=3)
93.35
17
0.078
Sigmoid
4k
iRNN (K=5)
95.30
18
0.020
Sigmoid
4k
Table 11: HAR-2 dataset (Sigmoid, ReLU activations): K denotes pre-defined recursions embedded graph to reach equillibrium.
24


Reviews:
[{"review_id": "SyeP2jSaYH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "In this paper, the authors propose the incremental RNN (iRNN), which is inspired by the continuous-time RNN (CTRNN). Theoretically, the equilibrium point of iRNN exists and is unique. Furthermore, the norm of the Jacobian between two hidden states is always one, provided that the Euler iterations converge. The authors proved this property as well as the exponential convergence rate of the Euler iteration. These properties avoid the vanishing/exploding gradient problem typical in RNN with long sequences in theory. Empirically, the proposed method is compared with multiple RNN architecture on various tasks. \n\nThe paper is clearly written and well organized. It starts with the existence and uniqueness of a fixed point; then provides the converge rate, and finally the main theorem of identity gradient. The main theorem provides a good theoretically guaranteed solution. The authors have done extensive experiments on several datasets compared against various popular and recently developed RNN-based models. The authors also provided some empirical experiments on the converge rate and the non-singularity of grad \\psi.\n\nThe motivation of the paper could be improved. For example, despite the appealing theoretical properties. I did not fully understand the motivation in Equation 3. It would be great if the authors could further elaborate on it.\n\nTypos:\nPage 4 at “Upon computation, we see that”. The gradient on the left-hand side should be grad \\psi? \nPage 4 at “at the equilibrium points we have”, the gradient of \\psi should be the gradient of \\phi?\n", "extra_scores": {"experience_assessment": "I have published one or two 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": "SJgfNIk3YB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The authors present a novel work to address the problem of signal propagation in the recurrent neural networks. The idea is to build a attractor system for the signal transition from state h_{k-1} to h_k. If the attractor system converges to a equilibrium, then the hidden to hidden gradient is an identity matrix. This idea is elegant. The authors verify the performance of Increment RNN on long-term-dependency tasks and non-long-term-dependency tasks.\n\nThe work successfully constructs a negative identity hidden to hidden gradient matrix but I still have a few concerns about the theory and the experiments. If the authors can address my concerns in the rebuttal, I am willing to increase my score. \n\nTheoretical concerns:\nEven in the limit sense, the inner ordinary differential equation of g will converge to the equilibrium, it may not converge in the finite steps. Thus, the state-to-state gradient may be slightly away from the identity. And we know that (0.99)^T goes to infinity when T goes to infinity. In practice, the long-term-gradient problem may still exist in the incremental RNN.\n\nExperimental concerns:\nThe theorem requires the norm of U to be bounded. But I cannot see how the authors bound the norm of U in the experiment section.\n\nClarity of writing:\nThere are a bunch of typos in the papers, especially the ones in the proof of Theorem 1. The proof of theorem 1 can be polished. The author swap the use of phi and psi several times in the proof. And gradient calculation on equation (5) should be expanded into more details. The authors also missed one U in the equation in the second last line of the proof. \n\nOverall, I think the paper is an interesting contribution to the community.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "S1l7cek0FS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Update: the authors have addressed my issues below and I have raised my score to 8.\n\n***\n\nThis paper on recurrent neural networks goes back to Rosenblatt's continuous time dynamics model and uses a discretised version of that equation (equation (1) in the paper) to build an incremental version of the RNN, called incremental RNN, where the transition from hidden state h_{k-1} at step k-1 to next step's h_k is done using small incremental updates until the system achieves equilibrium. It claims that it manages to solve the vanishing gradient problem by keeping all gradients \\frac{\\partial h_k}{\\partial h_{k-1}} equal to minus identity matrix. The algorithm is then extensively evaluated on a large number of tasks and compared with plain RNNs, LSTMs, and two recently published papers on antisymmetric RNN and FastRNN.\n\nI need to admit that after reading the paper twice, I am not sure I understand how the method works exactly (how does inserting intermediary steps and variables g_0, g_1, ... g_T enable the system to reach equilibrium: is there an iterative evaluation until convergence?) and more worringly, how the single-step SiRNN differs from a normal RNN with an extra residual connection?\n\nAccording to equation (5), for T=1 and g_0=0, we have:\ng_T = g_1 = \\eta_k^1 ( \\phi (U (h_{k-1}) + W x_k + b) - \\alpha h_{k-1} ).\nIf the gradients are vanishing in the normal RNN, why would they not vanish here for T=1?\n\nPropositions 1 and 2 are for the case K=\\infinity, and I could not understand the proof of theorem 1 that shows why \\frac{\\partial h_k}{\\partial h_{k-1}} = - I. This seems to be the major contribution of the paper and should be given prominence.\n\nWhat is missing is clear explanation, like (Bengio et al, 1994), of the identity gradient and of how the algorithm works. These questions could be solved by including code or pseudo-code explaining how to actually implement incremental RNNs.\n\nThere are also several important papers recently published that have approached the problems of continous-time dynamics and relaxation of hidden state to equilibria.\n* The paper does not mention at all Neural ODEs [2] [3] where the state flows in a continuously differentiable way thanks to the continuous-time residual network ODE formulation. Moreover, isn't the idea of inserting a relaxation to equilibrium using ODEs already implemented in the ODE-RNNs [3]?\n* How do incremental updates related to Adaptive Computation Time [4]?\n\nFor this reason, I am currently tending to reject the paper, but am open to change my score upon clarifications and links to other similar work.\n\nAdditional remarks:\nThe first paragraph of the paper explains the Elman RNN, not RNNs in general.\nPlease cite [1] alongside Bengio et al (1994) for the problem of the vanishing gradient.\nDefine alpha in equation (1)\nNotation k and K is very confusing\nBlue vs. green on Figure 2 is hard to read, and where is the new initialisation?\nWhy do you add h_k^K to h_{k-1} in equation (8)? I thought it was g_k^K?\nKeep the same colours for all experiments in figure 4.\n\n[1] Hochreiter (1991) \"Untersuchungen zu dynamischen neuronalen Netzen\"\n[2] Chen, Rubanova, Bettencourt & Duvenaud (2018) \"Neural Ordinary Differential Equations\"\n[3] Rubanova, Chen & Duvenaud (2019) \"Latent odes for irregularly-sampled time series\"\n[4] Graves (2016) \"Adaptive computation time for recurrent neural networks\"\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "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.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors propose the incremental RNN, a novel recurrent neural network architecture that resolves the exploding/vanishing gradient problem. While the reviewers initially had various concerns, the paper has been substantially improved during the discussion period and all questions by the reviewers have been resolved. The main idea of the paper is elegant, the theoretical results interesting, and the empirical evaluation extensive. The reviewers and the AC recommend acceptance of this paper to ICLR-2020.
Decision: Accept (Poster)