SBO-RNN: Reformulating Recurrent Neural Networks via Stochastic Bilevel Optimization
Authors: Ziming Zhang
Yun Yue
Guojun Wu
Yanhua Li
Haichong Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: recurrent neural networks
stochastic bilevel optimization
training stability

Abstract: In this paper we consider the training stability of recurrent neural networks (RNNs) and propose a family of RNNs, namely SBO-RNN, that can be formulated using stochastic bilevel optimization (SBO). With the help of stochastic gradient descent (SGD), we manage to convert the SBO problem into an RNN where the feedforward and backpropagation solve the lower and upper-level optimization for learning hidden states and their hyperparameters, respectively. We prove that under mild conditions there is no vanishing or exploding gradient in training SBO-RNN. Empirically we demonstrate our approach with superior performance on several benchmark datasets, with fewer parameters, less training data, and much faster convergence. Code is available at https://zhang-vislab.github.io.

SBO-RNN: Reformulating Recurrent Neural Networks via Stochastic Bilevel Optimization
Ziming Zhang, Yun Yue, Guojun Wu, Yanhua Li, Haichong Zhang
Worcester Polytechnic Institute
Worcester, MA 01609
(zzhang15, yyue, gwu, yli15, hzhang10 0 @wpi edu
Abstract
In this paper consider the training stability of recurrent neural networks (RNNs), and propose family of RNNs, namely SBO-RNN, that can be formulated using stochastic bilevel optimization (SBO). With the help of stochastic gradient descent (SGD), we manage to convert the SBO problem into an RNN where the feedforward and backpropagation solve the lower and upper-level optimization for learning hidden states and their hyperparameters, respectively. We prove that under mild conditions there is no vanishing or exploding gradient in training SBO-RNN. Empirically we demonstrate our approach with superior performance on several benchmark datasets, with fewer parameters, less training data, and much faster convergence. Code is available at gettps:/zzhagg-ee waw...llb......... waa.ll...ttttttt github. io
Introduction
Training Stability in RNNs. Recurrent neural networks (RNNs) have achieved significant success in learning complex patterns for sequential input data. Due to the repeatability of network weights the chain rule when computing gradients. vanishing exploding gradients often occur in training RNNs, i.e. the gradient magnitudes either too small too large, leading to the well-known critical training stability issue Pascanu et al. [2013a). To see this, suppose that we optimizing the following RNN:
min E. (e..iiexxx y:w), s.t. h, [h xx; 0), Vx, E x, Ve,ViC E [T), w.O
(1)
where (I. E X' y denotes the training data with samples {x1, {'1,.... XTT Rd and label hg E Rº' denotes the hidden state variable at the f-th time step with a predefined initial hos e, f denote the loss and nonconvex transition functions parametrized by w, respectively, and E denotes the expectation operation. The gradient of w.r.t. 0 per data in the RNN can be computed as follows:
Ot de
Öhe The
where OhT Thg
Ohe
Σ I5KST
II
06
Ohr
Th, 00
The training challenge mainly comes from 0hy
i.e., 0bbr 0 leading to vanishing gradients and + +oo leading to exploding gradients, where || | denotes the magnitude of gradient.
Sh.
Olvr Bh.
CenaltyL.agranginn Methods. fact, the learning problem in Eq. is a constrained optimization problem with recursive equality constraints. To solve it, an intuitive idea is to relax it to uncon- strained optimization problem using, for instance, penalty methods [Zhang and Brand 2017] or (augmented) Lagrangian methods [Gu et al. 2020 that lift the constraints into the objective function. As demonstration, we list a relaxation of Eq. Jusing a penalty method as follows:
min B(xa))xx wh0,
((hr, + Σ N lh+ f(h--,,x;0)11
(3)
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

where A 2 O, vt denotes a penalty coefficient. Now the gradient w.r.f 0 is only dependent on the second term, i.e., least squares, with no training stability issue. Such relaxation has modified the RNN network architectures that leads to new challenges in such methods for RNN training, for instance:
The size of variables {he) increases linearly w.r.f. the sequence length T, leading large memory. The learned parameters w, 0 may not work well in the original RNN at test time, due to the penalty,
How to solve these challenges in the relaxed training approaches still remains open question [Gu ct al. 2020].
Bilevel Optimization (BO) & Ordinary Differential Equations (ODEs), Alternatively, based on
similar idea of penalty methods, a trivial yet equivalent modification of Eq. D listed as Eq. below, which essentially defines a bilevel optimization problem where one optimization problem is
embedded within the other (e.g., [Vicente and Calamai 1994 Sinha et al. 2017))
min E (xx.))xxxxx y;w), s.t. h2 = arg min ||- f(he- 1, Xx; O)I VI E [T]
(4)
w/B
h
min LE (xxx)) yiw), s.t. h4 = h4 f(h Vt [T], w,0
(5)
where hn denotes the change rate of variable fy over time in the gradient flow, and he 0 when he converges to a fixed point, if exists. In fact, some of recent ODE based RNNs have similar transition functions to Eq. 5 For instance. Kag et al. [2020) proposed (h+ + 1, 8) (0) 0. and proved that
incremental RNN (iRNN) with
transition function of -hh, there is no vanishing/exploding gradient in training IRNN. As we can see, the key difference between iRNN and Eq. 5 is that the current hidden state variable ht is introduced into function f. leading to sequence of updates for he through variable discretization. However, to the best of our knowledge, so far work has been proposed to formulate RNNs using BO. Recently BO regains attention in meta-learning. For instance, |Franceschi et al. 2018 proposed a framework based on bilevel programming to unify gradient-based hyperparameter optimization and meta-learning, Mounsaveng et al. [2021) proposed using online BO to tune the hyperparameters for data augmentation.
(he + h4-1
Our Contributions. In contrast to the literature, in this paper we consider the training of RNNs itself as a bilevel optimization problem. Specifically, we propose a new family of RNNs, namely SBO-RNN, that can be formulated using stochastic bilevel optimization (SBO), where we consider hidden state vectors as intermediate auxiliary variables that depend on the RNN model parameters. These auxiliary variables are optimized in the lower-level problem of SBO, and the model parameters as well as the predictor are learned by optimizing the outer objective function. We utilize stochastic gradient descent (SGD) and its momentum variants to solve such SBO problems, where in return the optimization process of the lower-level problem can be (approximately) represented by SBO-RNN. We also prove that under mild conditions, our SBO-RNN can avoid vanishing or exploding gradients in training by selecting proper learning rates for the lower-level problem. We conduct comprehensive experiments several benchmark datasets to evaluate our approach, and achieve superior results.
In summary, our key contributions in this paper are listed as follows:
We propose new family of RNNs, namely SBO-RNN, that are the first in the literature, to the best of our knowledge, to formulate RNNs using stochastic bilevel optimization for streaming data.
We prove that our networks manage to obtain good training stability by selecting proper learning rates for the lower-level problem to avoid vanishing and exploding gradients.
We demonstrate superior performance empirically with fewer parameters, less training data, and much faster convergence.
2 Related Work
RNN Architectures. To address the training stability issue, there are significant amount of works on developing RNN architectures such as, just to name a few, long short-term memory (LSTM)
[Hochreiter and Schmidhuber] 1997]. gated recurrent unit (GRU) [Cho et al.) 2014 Collins et al.
2016), unitary RNNs (Arjovsky et al. 2016 Jing et al.) 2017 Zhang et al.) 2018 Pennington et al.
2017]. deep RNNs [Pascanu et al. 201 3b Zilly et al. 2017 Mujika et al. 2017, Zhang et al. [021]
linear RNNs [Bradbury et al. 2016 Iei
et al. 2018 Balduzzi and Ghifary| (016). residual/skip
RNNs Jaeger et al. 2007
Bengio et al. 2013
Chang al. 2017
Campos al. 2017 Kusupati

---

et al
2018a
ODE RNNs (Talthi and Vartak, 2015
Niu et al. 2019
Chang et al. 2019 Kusupati
ct al.
2018a
Chen et al. 2018 Rubanova et al. 2019 Kag et al.
2020
Rusch and Mishra 202
Bai
et al.
2019
Frichson et al., 2020]. implicit RNN [Revay and Manchester 2020]. and TreeRNN Lyu
et al.
2021
We summarize the literature as the following groups:
Recurrent units: LSTM applies gate-controlled memory cells to mitigate the vanishing/exploding
gradient issue in sequence-based tasks. GRU is another widely-used variant of RNNs, and similar
to LSTM it can stabilize the training [Chung et al., 2014]. Recently, Jose et al. [2018] proposed
a flexible Kronecker recurrent unit (KRU) based on Kronecker product. Nguyen et al. 2020
proposed MomentumRNN by integrating momentum into the recurrent unit.
Residual/Skip RNNs: This family of RNNs feed-forward state vectors with the help of skip or
residual connections to serve as middle ground between feed-forward and recurrent models and to mitigate gradient decay. Such network architectures can also be used to search for equilibrium
(or fixed) points in ODEs, such as iRNN (Kag et al., 2020).
Stable recurrent models: [Mlllrr and Hardt 2019] proved that stable recurrent neural networks are well approximated by feed-forwart networks for the purpose of both inference and training by gradient descent. The analysis is based on the contraction assumption in the state transition function. Revay and Manchester [2020] proposed an implicit model structure that allows for convex parametrization of stable models using contraction analysis of non-linear systems. [Collins) jtt al. [2016] showed experimentally that all common RNN architectures achieve nearly the same per-task and per-unit capacity bounds with careful training, for a variety of tasks and stacking depths.
Unitary and orthogonal RNNs: These RNNs aim to preserve the norm of hidden features (i.e., || Bia || in Eq. [) by controlling the eigenvalues, explicitly or implicitly, that has been studied
extensively recent years [Arjovsky et al.] 2016, [iig et al., 2017 Zhang et al.] 2018 Pennington cct al. 2017 Erichson et al. [2020] Kerg et al. [019 Lezcano Casado and Marunez Rubio 2019 Helfrich et al. 20188 Maduranga et al. 2019 MMhammedi et al. [017]. For instance, Lezcano [2019] proposed expRNN by performing the first-order optimization with orthogonal and unitary constraints based on parametrization stemming from Lie group theory through the exponential map.
Casado and Martunez-Rube
RNNs with equilibrium hidden states: In such RNNs, the hidden states are represented by the equilibrium points, if exist, of certain dynamical systems defined by ODEs, for instance. Typical works include AntisymmetricRNNG [Chang et al., 2019]. FastRNN (Kusupati et al. 2018b). iRNN (Kag et al. 2020], Lipschitz RNN [Erichson et al. 2020). It seems that all these works can prove good training stability from different perspectives such as generalization bound or norm of gradients. with empirical demonstration.
Deep RNNs: RNNs are inherently deep in time. Inspired by this property. researchers are seeking develop new networks to investigate the benefits of depth in space of RNN architectures. For instance, [Graves et al., 2013) combined multiple recurrent levels on the basis of bi-directional LSTM Graves and Schmidhuber 2005 [Schuster and Paliwal| 1997] to improve RNN performance in speech recognition task. Another study in [Hermans and Schrauwen, 2013]. with a deeper analysis of the different emergent time scales, also proposed similar stacking architecture. Some
deep RNNs have been proposed in the literature well [Chen et al.)
1995 El Hihi and Bengio
[996 Fernández et al. 2007 [Schiidhuber] 1992 Graves [
2007 Pascanu et al. 2013b
Pinheiro and Collobert 2014 [14|Liia 201, 8, Dennis et 2019).
Optimization for RNNs Same as training other deep networks, SGD is widely used in training RNNs, but there is no guarantee of good training stability. In contrast, some works focus on optimization in RNNs stabilize gradients. Typical works include truncated backpropagation
through time (TBPTT) [Jaeger 2002), real-time recurrent lcarning (RTRL) [Williams and Zipser Frank-Waoor
algorithm Yue al.) 2020). gradient clipping (Pascanu | [0133a] Li et al. 2018 Zhang et al.) 2020]. identity or orthogonal weight initialization Le et al. 2015 Arjovsky et al.
1989
2016 Jing et al. | Jose et al., 2017 Mhammedi et al.) 2017
Wisdom et al.) 2016 Vorontsov Different from these works, we propose using SBO to interpret RNNs and further train them based on a two-loop algorithm where the inner loop solves the SBO problems and the outer loop optimizes the RNN parameters.
et al.
2017]. weight matrix reparametrization Zhangg et al. 2018
Training Stability Analysis in RNNs. The stability analysis of different network architectures often comes with the eigenvalues of the Jacobian of the hidden state dynamics, because RNNs can be considered dynamical systems. For instance, Engelken et al. [2020] studied the Lyapunov spectra
3

---

Algorithm Training algorithm for SBO-RNN
Input
:loss function parametrized by state transition function F parametrized by 0, step size training data X' and labels y
Output:minimin w",0"
Randomly initialize .",
repeat
/* 1ower-level optimization:
RNN inference
foreach x E X do
hg f- 0:
foreach t E [T] do
he hi-1 - (h-1,
1/ or momentum SGD using Eq.
B
or
end
end
x* upper-Leved optimization: hyperparameter learning
w", 00 arg min ((x,)) y: w-w)
until Converge;
return ,";
of chaotic recurrent neural networks. Vogt et al. 2020] proposed using Lyapunov exponents to
understand the information propagation in RNNs, but unfortunately there is discussion how to
introduce such nice Lyapunov stability into the development of RNNs. Drgona et al. (0200) proposed viewing neural networks from dynamical systems perspective pointwise affine maps. However, the theoretical results are adapted from dynamical system analysis and the assumptions for deep neural networks too strong be met in practice. Tuoor et al. (2020) proposed ODE based network implementation to guarantee stability as well as incorporating prior knowledge. Recently, Ribeiro et al. 2020 proposed analyzing RNN training using attractors and smoothness alternatives.
3 SBO-RNN
3.1 Stochastic Bilevel Optimization Formulation for RNNs
Recall that the goal of RNNs is to learn discriminant representations for different data sequences, regardless of how the intermediate hidden states are defined. In our approach, first assume that {x1, Xx) is generated by certain stochastic process with distribution Py that is conditional on the label y of a. That is, each x,, Vt E [T] is sampled from Pg. i.e., X, ~ Py We observe that this assumption can work well in practice, even for the sequences with strong dependencies among samples. Based on this assumption, we propose the following learning problem:
data sequence
min E (x))) ():, s.t. w.0
E arg min ExpxP, F (h,x;;0) ho 0, Vx, E Ex, Vt E [T]. (6)
REH
where is proper, differentiable everywhere, and lower-bounded function. we can see, the lower-level optimization in Eq. 6 aims to learn the data representations on-the-fly, while the upper- level optimization aims to learn the hyperparameter of F as well as the predictor w simultaneously. Different from Eq. 4 for instance, representations data sequences, and is learned so that such stationary points can be separated well for prediction. Similar ideas have been explored in the orthogonal RNNs such expRNN [ezcano--Casee and Martunez- Rubio 2019 where the transition functions are nonexpansive w.r.t. hidden states (but guarantee of convergence). It has been demonstrated that such nonexpansive constraints in learning can significantly improve the performance of RNNs. this paper we further demonstrate that such convergence in the lower-level optimization can not only improve performance but also accelerate the training (see our experimental section).
approach utilizes the stationary points of function F as the
3.2 Learning
Lower-level Optimization. We show our general training algorithm in Alg. where the lower-level optimization solved using SGD. We can also employ momentum SGD our solver to train SBO-RNN. Specifically, below we list three popular variants of SGD, namely vamilla SGD, stochastic

---

hç+1
Re-1
R141
R1-1
h4
h
+
Vir
VFc+1
V.
V/++
VFr
VF++1
hi
he+1
h
hig (c) SNAG
At+1
(a) SGD
(b)
SHB
Figure 1: Illustration of SBO-RNN architectures using the optimizers in Eq. and respectively.
heavy-ball (SHB) momentum, and stochastic Nesterov accelerated gradient (SNAG) momentum:
SGD: h2 = h1-1 1) v/ F,, ho = 0, ht = hT, Vt E [T],
(7)
SHB: h4 ph4-1 1/ F2, f4 h4-1 + he, ho hg = 0, h² = h Vt E [T],
(8)
SNAG: h; h,-1 F, hr h4 uhh, h4-1)) 1), ho ho 0, hr, At e [T),
where V denotes the gradient operator, VF, V (h x,, 0) denotes the current gradient w.t.f. h. 17 2 0 denotes the step size, and E [0, 1] denotes the momentum parameter. Note that SHB and SNAG is identical to SGD when μ O.
RNN Interpretation. Eq. 7 S and define three different iterative methods that take the previous hidden state imput and output the current hidden state, leading to three different SBO-RNN network architectures (see Fig. T.. Note that our 3BO-RNN shares similarities some recent RNNs such as FastRNN [Kusupati et al. 201 8b and iRNN (Kag et al., 2020 that have skip connections in the architectures and have been demonstrated to be trained stably. Recently, momentumRNN [Nguyen] et al. 2020) was proposed by drawing connection between the dynamics of hidden states and GD. is clear, however, that in terms of formulation the "momentum' here is only used for accumulating the weighted data samples without any purpose in optimization. In other words, its update rule has nothing to do with GD or momentum variants. In contrast, in our SBO-RNN we utilize first-order methods really solve the lower-level optimization problems, which makes the gradient term in SBO-RNN analytically integralable.
Instantiations. In this paper, we demonstrate our approach based on the following two functions:
F(h, xxi 0) def
|lah o (UTh + VT xx + bb]l
(10)
def |1/l 1 U ( h V +
Fh, xx;
(11)
where U EDDD V E Bd RR,, E R together form the model parameters 0, Φ R - R denotes an entry-wise nonconvex and differentiable function such as ReLU and tanh, and (-) denote the matrix transpose and inverse operators. Here we borrow the transition function vanilla RNNs that aim to enforce the hidden state vectors to satisfy certain properties induced by ø. Note that in Eq. 11 we presume that U is full-rank and thus invertible. In practice we observe that this assumption holds all the time. Correspondingly, the gradients of both models are:
VF, (aI VnΦi (aht-1- -.), V = ah-11 Φ..
(12)
where 6, = (1th:- V x, + b), and denotes the identity matrix. Now we can substitute these gradients into Eq. 7 and 9 respectively, to solve the lower-level optimization in Alg. Note that Eq. leads to a similas ar update rule for the hidden states to FastRNN (usupati et al. 20 8b).. Without explicitly mentioning, in our experiments we will show the best performance from the two instantiations in Eq. 10 and
Convergence Rate. Under some mild conditions, to minimize strongly-convex and smooth objectives, all the three stochastic optimizers can converge with the same rates as their deterministic counterparts [Assran and Rabbat 2020]. In the convex and smooth setting, recent results in (Sebbouh al. 2021 proved that their convergence rates can be arbitrarily close to o(1/vi), and can be exactly o o(l/t) in
5

---

the overparametrized case. In both nonconvex and smooth and nonconvey and nonsmooth settings, the convergence rates are changed to O(1/Vt) Yan et al. 2018 Mai and Johansson 2020 Overall, our solvers should be able to locate solutions around stationary points for our problem in Eq. 6
Network Implementation. We illustrate three different network blocks for SBO-RNN in Fig.
where each directed edge towards ④ is associated with certain learnable weight that is either or related to one of a. μt 17 in Eq.
and L0 As we sec, Fig. (Ta) is essentially a variant of and (c) are similar to dual-path networks (DPN) [Chen et al. 2017] where information is propagated between two parallel paths. Note that though both (b) and (c)
ResNet [He et al. 2016], and Fig.
come from momentum SGD, the distributions of h and h are totally different due to their weighting strategies for gradients. The output hy is fed to a predictor parametrized by in Eq. 6
Such networks can implement Alg. D effectively and efficiently. Precisely, we utilize the network blocks in Fig. to construct a (sub)network to solve the lower-level optimization (i.e., the foreach loop in Alg. D appended with a prediction subnetwork (e.g., fully- colly-eoneeeted layer). The outputs of the entire network are used for minimizing the upper-level optimization problem. In training, we still use some popular deep learning solvers such as Adam [Kingma and Ba| 2014] to backpropagate gradients to update the network parameters, while the feedforward solves the lower-level optimization.
3.3 Analysis
Theorem (Upper Bound of Hidden Feature Distance during Network Inference). Let Vt E (T) x== {xe), [x1} and { }hi} denote two data sequences and their corresponding hidden fea-
tures, repectively. Suppose that function F Fh,, Xt; 0) is differentiable, Ln-smooth w.r.t h, i.c.
(h;, F xx;81]] < Ln Wl,, and its gradient w.r.t. x; is L LipLipschitz, ie.,
(h, - (k,, f)1 < Lz||xx x(11- Then for SGD in Eq. 7 we have
|1,, h2ll S Σ nLa(11 + +nLL)
x1,1 S ty = O(tr))
(13)
kE(()
where Y+- = maX ||* - xXا1 and nIn < 1.
This result provides hypothesis our faster convergence empir- ically that is beneficial from the factor Tr in the upper bound. Since we assume x, ~ py. it is very likely that 7/ for the data from the same class will be smaller than that from different classes, leading to clusters for different classes. We illustrate this intuition in Fig, 2 where red and green colors denote two different classes. The smaller upper bound encourages the data from the same class to form clus- ter that can be easily separate from the data from different classes. This behavior would accelerate the learning of discriminative fea- tures in the networks, leading to fast convergence. Note that with simple algebra can show that both F's in Eq. 10 I1 satisfy the smoothness conditions in Thm.
h2
ht
h1
ho = hb = 1/
Corollary 1. For SHB in Eq. and SNAG in Eq. 9 supposing that the assumptions in Thm. hold as well, then still have ||/, - Aall I O(tr),, Vt E [T].
Figure 2: Illustration of clus- tering in the hidden feature space based on Thm.
To this, can simply scale the upper bound with a factor T.
Theorem 2 (Training Stability). Suppose that function F is differentiable and L-smooth w.r.t h.
ie., V < LI or F < L where I denotes the identity matrix. Then by properly choosing n (0, Ti, where T is the sequence length and e E (0,1) is sufficiently small constant, we can guarantee that there is no vanishing/exploding gradient for training SBO-RNN using SGD in Eq. 7
Corollary 2. For SHB in Eq. Band SNAG in Eg. 9 supposing that the assumptions in Thm.. hoold we still can guarantee that there is no vanishing and exploding gradient when training SBO-RNN.
To see this, we can rewrite the update rules as accumulation of the previous gradients. Then based on the fact that Sha-1 The O, Vk E [t 1] holds, we can still achieve ah
8h,
x I - F, that leads to the
same conclusion in Thm. 2

---

Table 2:
Performance summary of different variants of our SBO-RNN HAR-2. The training/test time is for per batch with 64 sequences.
dense SGD
dense SHB
dense SNAG
sparse SGD
sparse SHB
sparse SNAG
1% data acc. (%)
90.25+ 0.71
86.59-40.74
87.19+0.114
79.18+1.445
78.55=11.45
77.89+ 1.41
10% data acc. (%)
93.25.1 0.07
93.44:10.67
93.52-10.38
90.76110.22
0.49
9188110.59
training time (s)
0.00
0.65:10.06
0.67:10.10
0.54
0.55
0.58.10.04
test time (s)
0.30=0.00
0.33+00.05
0.31+0.02
0.28+0.01
0.26++0.01
0.27++0.01
4 Experiments
We evaluate our method on long- sequence benchmarks with varying difficul- ties, and list the statisties of these datasets in We strictly follow the experimental settings in the previous works (e.g.. [Kg et al., 2020 Kusupati et al., 2018b) for fair com-- parison. Specifically, Pixel-MNIST refers to pixel-by-pixel sequences of images in MNIST
Datasets.
Table 1: Statistics and dimension of hidden state vectors in each benchmark dataset.
Table [
Statisties
Dim.
Dataset
#Train
#Test
#Time #Feat, #Cls.
D
PiXel-MNIST
60k
10k
784
1
10
128
HAR-2
7.3k
2.9k
128
9
2
128
PTB
929k
82k
300
300
10k
300
[LeCun and Cortes) 2010) where each 28 x 28 image is flattened into a 784 time-step sequence vector
and normalized zero mean and unit variance. HAR-2 [Kusupati al. 2018a] was collected from an accelerometer and gyroscope on a Samsung Galaxy S3 smartphone for human activity recognition tasks with zero mean and unit variance. Penn Treebank ( (PTB) dataset (Melis et al. 2017] consists of 300-word sequences for word-level language modeling task using the PTB corpus. The vocabulary consists of 10, 000 words and the size of trainable word embeddings is kept the same as the number of hidden units of the architecture.
Baseline Algorithms. We compare results with baselines including vanilla RNN, LSTM (Hochre iter and Schmidhuber [997], AntisymmetricRNN [Chang et al., 2019]. FastRNN [usupati et al. 2018b]. FastGRNN KKsuupati et al. 2018b). ShaRNN [Dnnis et al. 2019), IndRNN Li et al. 2018 INNN Kag et al. 2020J. LipschitZRNN EEiicssn et al. 2020) and MomentumRNN Nguyenn et al. 2020 Note that using the public code we have verified the results of each competitor the datasets that were reported the references. For simplicity and consistency we cite the numbers from the references, if exist, otherwise, we report our reproduced results with best tuned hyperparameters.
Training Testing Protocols. our implementation we utilize ReLU as our activation function (i.e., & in Eq. [0), as we observed that this activation works better than others such as tanh in terms of both accuracy and convergence. This observation is consistent with the state-of of-the-------ttt---- methods. We replicate the same benchmark training/testing split with 20% of training data for validation to tune hyperparameters. Then we retrain the models using best tuned hyperparameters using the full training set and test them on the test set. We report our results (i.e., accuracy and running time) over three trials with randomization wherever needed such as parameter initialization. All the experiments were on an Nvidia GeForee RTX 2080 Ti GPU server.
Hyperparameters. We use the grid search fine-tune the hyperparameters of each baseline as well as ours on the validation datasets whenever is necessary. We follow (Kusupati et al.) 2018 8b Kag al. 2020 Chang et al. 2019 to set the hidden feature dimension D, as listed in Table [ We further set 17 10 in Eq. [ and 9 in all the experiments as we observe that this number works well and consistently that leads the lower-level optimization to converge. The batch size of 64 is used across all the datasets for all the methods. Adam (Kingma and Ba (014)) is used as the optimizer for all the methods. The learning rate for training SBO-RNN architectures is always initialized to 10 with linear scheduling of weight decay.
4.1 Ablation Study on Adding Task and HAR-2 Dataset
The adding task is widely used for RNN evaluation. We strictly follow (Arjovsky et al., 2016
to generate the data using their public code. There are two sequences with length 7'= = 100, 500, respectively. The first sequence is sampled uniformly at random (0 1]. The second sequence is filled with 0 except for two entries of 1. The two entries of 1 are located uniformly at random
7

---

HAR-2. T2878, 1% training date
0.25
Adding Task, T-100
dense SGD
0.90
0.90
0.70
sparse 50D
derse SHd
derse 50D
Fast
LSTH
100.00
90.00
HAR-2. Tw128. training
Training MBE
0.20
SM1
g 0.50
derse SNAG
spense 5:10
VanillRAN
Test Accuracy
sparse SMA6
70.00
0:45
sparde
0.10
LipachizaRNN
Fastitiuk
0.20
0.30
50.00
60.00
SHB
550
IRNM
0.05
0.10
ShåG
SMAS
Vanilssoo
0.00
0.00
30.00
Training Steps 15 101
Epochs
Spochs
HAR-2, T=128, 10% training data
0.30
Adding Task. T-500
100.00
HAR-2, T-128 10% trairing data
dense SGD
Sporse SGD
FastRMN
sperce Sean
derse
Taahine MSB
0.20
sparse
dence SHB
sparse 5-18
derse SKAG
VanilARAN
Test Accurdty
80.00
dense SMAG
Sporse S146
70.00
0:15
Lipcchrzttiin
FaStRAN
SNAG
0.30
00.00
50,00
dense SHn
dense SED
Sparse SCD
FamtRU
LSTH
0.20
spanse 5it
IRAN
0.05
0.10
dense SNAG
spena SWAG
0.00
2
8
221
30,00
Training Steps 15 10')
Epochs
Spochs
(a) Adding Task
(b) HAR-2: Training Loss
(c) HAR-2: Test Accuracy
Figure 3: (a) Training loss on the Adding Task. (b-c) Training loss and test accuracy on HAR-2.
Plosi WNBT
HAIR2
>
143
+57
132
Peptesty
L570
132
LSTV JUPAA
10 aOOM
Johemite (176
mocemrmeee of D0
Menniee 20.30)
0 Das pm art
2.52
D Cles (19-35
logi9Paramiine
Figure 4: Benchmark comparison using different RNNs.
position i2 in the first half and second half of the sequence. The prediction value the sum the first sequence between (i,, 2g]. The ground- -ttut mean squared error is 0. when model simply guesses I as the output regardless of the input sequence. We use the value 0.167 as the bascline.
We conduct comprehensive experiments based on F' defined in Eq. to demonstrate the effectiveness of SBO-RNN, trained with mean- leaan--qure--rren (MSE) loss and hidden feature dimension = 128. from the following three perspectives, compared with other baseline RNNs as summarized in Fig. and Table
Fewer parameters: To this end, we simply set U- = 3II where 3 E R is learnable parameter. In this way, we reduce the model size (including U, V, b, a,,,), from D(D x d 1) + to D(d + 1) + 4. We denote this variant "sparse" model in contrast to the default "dense" model. For instance, on HAR-2 our sparse models contain only 1.5K parameters, in contrast to the dense models with 17.9K parameters, that is more than one order of magnitude reduction. In terms of convergence, sparse models are slightly worse than the dense models, leading to worse test accuracy as well, generally speaking. We also try to implement a sparse variant of each competitor based on our setup, and compare these models on HAR-2. Using the whole training data, the test results for FastRNN, iRNN, LipschitzRNN, vanilla RNN and ours are 94.57%, 80.21% %6 85.03%, 84.90%, and 94. 96%, respectively, where our result is still the best. For the adding task, with the increase of T, the convergence behavior of SBO-RNN does not vary a lot in terms of number of training steps. Less training data: On HAR-2 2, using either 1 1% or 10% of the original training data, our method outperform the competitors significantly by ~ 10% in terms of test accuracy. Also in such
8

---

cases, our method converges faster when data is more, and our dense models seem to consistently work better than sparse ones. The number of data has more impact on sparse models than dense models, as the accuracy increases by ~33 and ~3%, respectively. Also, we observe that the hidden dimension has bigger impact on the performance for less training data. For instance, based on 1 1%, 10%, and full training data, we can achieve the test accuracy of 83.99% 91.31 %, 95.08%, respectively, with D = 128, in contrast with 86.29% 92.37%, 94.74% with D = 256.
Faster convergence: On both Adding Task and HAR-2 dataset, we clearly observe the much faster convergence of all of our models than the competitors, in terms of both training loss and the test accuracy. We hypothesize that such behavior has strong correlation with the lower-level optimization that enforces data to cluster, as shown in Thm. [
From Table 2 we can see that the running time of sparse models in both training and testing is significantly shorter than dense models, with smaller standard deviation as well (iee. better stability). Using the same setting, Fa iRNN, LipschitZRNN, and vanilla RNN have the running time of 0.37x, 0.80x, 0.73x, 0.27x of our dense model, respectively, because our computational complexity per time step is higher (but F in Eq. I has similar complexity to FastRNN), Also, from the table[] we can see that the three optimizers for the lower-level optimization often achieve similar performance with small margins, especially when the training data is sufficiently large. Momentum variants bring more computation in both feedforward and backpropagation in training networks and inference. Therefore, in practice SGD based SBO-RNN seems to be sufficient. In terms of memory usage, they have 0.44x, 0.63x, 0.66x, 0.44x of our dense model.
In summary, our dense models outperform all the other models on Adding Task and HAR-2 dataset, and our sparse models seem to demonstrate strong potential in hardware implementation under resource-limited circumstances, achieving similar performance to those with larger model sizes.
4.2 State-of-the-art Comparison on PiXel-MNIST, HAR-2, and PTB Datasets
We compare the best performance of our dense models with other proposed baseline RNNs in Fig. The x-axis measures the number of parameters in each network (including the classifier) in log-scale. Overall, our approach can always achieve comparable accuracy the state-of-the-ar,, and for complex datasets such as PTB our approach can produce superior performance with smaller model sizes. Although the model sizes of our sparse models are much smaller (e.g., ~00 smaller than FasIGRNN (Kusupati et al. 2018b] that was designed as a tiny-size RNN), the test accuracy is notably lower than the of-te-of-the-are and thus we do not show them in the figure. Recall that our F function is so simple that its variant is used in vanilla RNNs, while all the methods that achieve better accuracy, e.g., IndRNN [Li et al.) 2018), have very complicated hidden state transition functions, even with larger model sizes. In summary, our SBO-RNN has great potential to achieve the state-of-the-art with simpler transition functions and smaller model sizes.
Conclusion
In this paper we propose new family of RNNs, namely SBO-RNN, that can be formulated using stochastic bilevel optimization. Using SGD or its momentum variants we convert such a bilevel optimization problem into an RNN architecture, where the lower-level optimization is mapped to the sub-network for computing hidden features and the upper-level optimization defines the predictor based on the computed features. We prove that under mild conditions there is vanishing/xxploding gradient in the training of our SBO-RNN, and thus our training is casy and stabilized. Furthermore, we demonstrate the superior performance of SBO-RNN several benchmark datasets with faster convergence, even based on fewer parameters and less training data.
Currently, we lack strong theorems to explain the fast convergence behavior of SBO-RNO RO-N,NN, though we have the hypothesis of data clustering, due to the lower-level optimization, that may significantly contribute to this. Also, our current setting has difficulty in adapting to deep RNNs such as IndRNN. In our future work, we will explore more on these topics.
Acknowledgement. Ziming Zhang and Yun Yue were supported in part by NSF grant CCF- 2006738, Guojun Wu and Yanhua Li were supported in part by NSF grants 194-1942680 (CAREER), CMMI-1831 140, and DGF--221871, and Haichong Zhang was supported in part by NIH DP5-OD028162.

---

References
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning, pages 1310-1318, 2013a.
Ziming Zhang and Matthew Brand, Convergent block coordinate descent for training tikhonov regularized deep neural networks. In NeurlPS, 2017.
Fangda Gu, Armin Askari, and Laurent EI Ghaoui. Fenchel lifted networks: A lagrange relaxation of neural network training. In International Conference on Artificial Intelligence and Statistics, pages 3362-3371. PMLR, 2020.
Luis N. Vicente and Paul H. Calamai. Bilevel and multilevel programming: A bibliography review, Journal of Global Optimization, 5(3):291-306, 1994.
Ankur Sinha, Pekka Malo, and Kalyanmoy Deb. A review bilevel optimization: from classical evolutionary approaches and applications. IEEE Transactions on Evolutionary Computation, 22(2):276-22 295, 2017.
Anil Kag, Ziming Zhang, and Venkatesh Saligrama. Rnns incrementally evolving on an equilibrium manifold: A panacea for vanishing and exploding gradients? In International Conference on Learning Representations, 2020.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil, Bilevel programming for hyperparameter optimization and meta-learning. In International Conference Machine Learning, pages 1568-1577 PMLR, 2018.
Saypraseuth Mounsaveng, Issam Laradji, Ismail Ben Ayed, David Vazquez, and Marco Pedersoli. Learning data augmentation with online bilevel optimization for image classification. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 1691-1700, 2021.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 98)):1335-1780, 1997.
Kyunghyun Cho, Bart Van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. On the properties of neural machine translation: Encoder-decoder approaches. arXiv preprint arXiv: 1409, 1259, 2014.
Jasmine Collins, Jascha Sohl-Dickstein, and David Sussillo. Capacity and Trainability in Recurrent Neural Networks. arXiv e-prints, art. arXiv:161 1.09913, November 2016.
Martin Arjovsky, Amar Shah, and Yoshua Bengio. Unitary evolution recurrent neural networks. International Conference on Machine Learning, pages 1120-1122 2016.
Li Jing, Yichen Shen, Tena Dubcek, John Peurifoy, Scott Skirlo, Yann LeCun, Max Tegmark, and Marin Soljačić. Tunable efficient unitary neural networks (eunn) and their application to rans. In International Conference on Machine Learning, pages 1733-1741 2017.
Jiong Zhang, Qi Lei, and Inderjit S. Dhillon. Stabilizing gradients for deep neural networks via efficient svd parameterization. In JCML, 2018
Jeffrey Pennington, Samuel Schoenholz, and Surya Ganguli. Resurrecting the sigmoid deep leamingg through dynamical isometry: theory and practice. In Advances in Neural Information Processing Systems 30, pages 1785-4799 2017.
Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, and Yoshua Bengio. How to construct deep recurrent neural networks. arXiv preprint arXiv: 13/266066, 2013b.
Julian Georg Zilly, Rupesh Kumar Srivastava, Jan Koutník, and Jürgen Schmidhuber. Recurrent highway networks. In ICML, pages 4189-4198. JMLR. org, 2017.
Asier Mujika, Florian Meier, and Angelika Steger. Fast-slow recurrent neural networks. In Advances in Neural Information Processing Systems, pages 5915-5924, 2017.
Ziming Zhang, Guojun Wu, Yun Yue, Yanhua Li, and Xun Zhou. Deep incremental rnn for learning sequential data: A Iyаpшnov stable dynamical system. In Proceedings of IEEE International Conference on Data Mining (ICDM), 2021.
James Bradbury, Stephen Merity, Caiming Xiong, and Richard Socher. Quasi-recurree neural networks. CoRR, abs/1611.01577 2016. URL TRLLhtt::/// /ttp/aaxvvv.oo/////ee org. www.//////aaaooooooooooo 611 01576
10

---

Tao Lei, Yu Zhang, Sida I. Wang, Hui Dai, and Yoav Arizi. Simple recurrent units for highly parallelizable recurrence. In Empirical Methods in Natural Language Processing (EMNLP). 2018.
David Balduzzi and Muhammad Ghifary. Strongly-typed recurrent neural networks. arXiv preprint arXiv:1602.0220 02218, 2016.
Herbert Jaeger, Mantas Lukosevicius, Dan Popovici, and Udo Siewert. Optimization and applications of echo state networks with leaky-integratee neurons. Neural networks the official journal of the International Neural Network Society, 20:335-52, 05 2007. doi: 10.10066j.eeunet.2000
Yoshua Bengio. Nicolas Joulanger-Lewandowsak and Razvan Pascanu. Advances in optimizing recurrent networks. 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, pages 8624-8628. 2013.
Shiyu Chang, Yang Zhang. Wei Han, Mo Yu, Xiaoxiao Guo, Wei Tan, Xiaodong Cui, Michael Withrock, Mark A Hasegawa-Johnson, and Thomas $ Huang. Dilated recurrent neural networks. In Advances in Neural Information Processing Systems, pages 77-87, 2017.
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 arXiv: 06834, 2017.
Aditya Kusupati, Manish Singh, Kush Bhatia, Ashish Kumar, Prateek Jain, and Manik Varma. Fastgrun: A fast, accurate, stable and tiny kilobyte sized gated recurrent neural network. In Advances in Neural Information Processing Systems, 2018a.
Sachin Talathi and Aniket Vartak. Improving performance of recurrent neural network with relu nonlinearity. arXiv preprint arXiv:1511.00 151.01111.377,,111 2015.
Murphy Yuezhen Niu, Lior Horesh, and Isaac Chuang. Recurrent neural networks in the eye of differential equations. arXiv preprint arXiv:1904. 12933, 2019.
Bo Chang, Minmin Chen, Fldad Haber, and Ed H. Chi. AntisymmetticRNN: A dynamical system view on recurrent neural networks. In International Conference Learning Representations, 2019.
Tian Qi Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differential equations. In Advances in Neural Information Processing Systems, pages 65513,,83, 2018.
Yulia Rubanova, Ricky T. Q. Chen, and David Duvenaud. Latent odes for iaepulerly-sampleed time series. CoRR, abs/1907.03900 2019. URL
T. Konstantin Rusch and Siddhartha Mishra. Coupled oscillatory recurrent neural network (coRNN): An accurate and (gradient) stable architecture for learning long time dependencies. In International Conference on Learning Representations, 2021.
Shaojie Bai, J. Zico Kolter, and Vladlen Koltun. Deep equilibrium models. In Advances in Neural Information Processing Systems, 2019.
N Benjamin Erichson, Omri Azencot, Alejandro Queiruga, and Michael W Mahoney. Lipschitz recurrent neural networks. Xrviv preprint arXiv:2006. /2070, 2020.
Max Revay and lan Manchester. Contracting implicit recurrent neural networks: Stable models with improved trainability. In Proceedings of the 2nd Conference on Learning for Dynamics and Control, pages 393-403, 2020.
Yecheng Lyu, Ming Li, Xinming Huang, Ulkuhan Guler, Patrick Schaumont, and Ziming Zhang. Treemn:: Topology-presst preserving deep graph embedding and learning. In 2020 25th International Conference on Pattern Recognition (ICPR), pages 7493-7499, 2021.
doi: 10.1 10.1109/CPR4880666 S0W.CCPRRS880222...... 2021.9412800
Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated
recurrent neural networks sequence modeling. arXiv preprint arXiv: arXiv:/412.3555 /412.3555 2014.
Cijo Jose, Moustapha Cissé, and Francois Fleuret, Kronecker recurrent units. In International Conference on Machine Learning, pages 2380-2389. PMLR, 2018
Tan M Nguyen, Richard G Baraniuk, Andrea L Bertozzi, Stanley J Osher, and Bao Wang. Momentummn: Integrating momentum into recurrent neural networks. arXiv preprint arXiv:2006.06919 2020.
John Miller and Moritz Hardt. Stable recurrent models. In International Conference on Learning Representations. 2019.

---

Jasmine Collins, Jascha Sohl-Dickstein, and David Sussillo. Capacity and trainability in recurrent neural networks. arXiv preprint 161
1.099113, .09913 2016.
Giancarlo Kerg. Kyle Goyette, Maximilian Puelma Touzel, Gauthier Gidel, Eugene Vorontsov, Yoshua Bengio, and Guillaume Lajoie. Non-normal recurrent neural network (nnrnn): learning long time dependencies while improving expressivity with transient dynamics. Advances in Neural Information Processing Systems, pages 1.3613-13623 2019.
Mario Lezcano- Casado and David Martmez-Rubio. Cheap orthogonal constraints in neural networks: A simple parametrization of the orthogonal and unitary group. In International Conference Machine Learning. pages 38033, 2019.
Kyle Helfrich, Devin Willmott, and Qiang Ye. Orthogonal recurrent neural networks with scaled cayley transform. In International Conference on Machine Learning, pages 1969-1978, 2018.
Kehelwala DG Maduranga, Kyle Helfrrih,, and Qiang Ye. Complex unitary recurrent neural networks using scaled cayley transform. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4528 4535, 2019.
Zakaria Mhammedi, Andrew Hellicar, Ashfaqur Rahman, and James Bailcy. Efficient orthogonal parametrisation of recurrent neural networks using houscholder reflections. reffectiin In International Conference on Machine Learning, pages 2401-2409 2409, PMLR, 2017.
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, pages 9017-9028, 2018b.
Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton. Speech recognition with deep recurrent neural networks. In 2013 IEEE international conference on acoustics, speech and signal processing, pages 6645- 6649. IEEE, 2013.
Alex Graves and Jürgen Schmidhuber. Framewise phoneme classification with bidirectional Istm and other neural network architectures. Neural networks, 18(5-6):602-611 2005.
Mike Schuster and Kuldip K Paliwal. Bidirectional recurrent neural networks. IEEE transactions on Signal Processing, 45(1 1):2673 2681, 1997.
Michiel Hermans and Benjamin Schrauwen. Training and analysing deep recurrent neural networks. In Advances neural information processing systems, pages 190-198, 2013.
Wen- Yuan Chen, Yuan-Fu Liao, and Sin-Horng Chen. Speech recognition with hierarchical recurrent neural networks. Pattern Recognition, 28(6):795 805, 1995.
Salah El Hihi and Yoshua Bengio. Hicrarchical recurrent neural networks for long-term dependencies. In Advonces neural information processing systems, pages 493-499, 1996.
Santiago Fernández, Alex Graves, and Jürgen Schmidhuber. Sequence labelling structured domains with hierarchical recurrent neural networks. In Proceedings of the 20th International Joint Conference on Artificial Intelligence, IJCA/ 2007, 2007.
Jürgen Schmidhuber. Learning complex, extended sequences using the principle of history compression. Neural Computation, 4(2):234-26 2422,42222112 1992.
Alex Graves. Generating sequences with recurrent neural networks. arXiv preprint arXiv: 2013.
Herbert Jaeger. Discovering multiscale dynamical features with hierarchical echo state networks. Technical report, Jacobs University Bremen, 2007.
Pedro HO Pinheiro and Ronan Collobert. Recurrent convolutional neural networks for scene labeling. In 31st International Conference on Machine Learning (ICML), 2014.
Shuai Li, Wanqing Li, Chris Cook, Ce Zhu, and Yanbo Gao. Independently recurrent neural network (indmn): Building longer and deeper mnn. Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5457-5466, 2018.
Don Dennis, Durmus Alp Emre Acar, Vikram Mandikal, Vinu Sankar Sadasivan, Venkatesh Saligrama, Har- sha Vardhan Simhadri, and Prateek Jain. Shallow rmn: accurate time-series classification on resource constrained devices. In Advances in Neural Information Processing Systems, pages 12896 12906, 2019.
12

---

Herbert Jaeger. Tutorial on training recurrent neural networks, covering BPPT. RTRL, EKF and the" echo state network" approach, volume S. GMD-Porschunnszzentru Informationstechnik Bonn, 2002.
Ronald Williams and David 7ipser. A learning algorithm for continually running fully recurrent neural networks. Neural computation, 1(2):270-280 1989.
Yun Yue, Ming Li, Venkatesh Saligrama, Ziming Zhang. Rnn training along locally optimal trajectoriesvia frank-wolfe algorithm. arXiv preprint arXiv:2010.0552 2020.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaic. Why gradient clipping accelerates training: theoretical justification for adaptivity. International Conference on Learning Representations, 2020.
Quoe V Le, Navdeep Jaitly, and Geoffrey E Hinton. A simple way to initialize recurrent networks of rectified linear units. arXiv preprint arXiv: 1504. 00941, 2015.
Cijo Jose, Moustpaha Cisse, and Francois Fleuret. Kronecker recurrent units. arXiv preprint 1rXi:1700.10042, 2017.
Scott Wisdom, Thomas Powers, John Hershey, Jonathan Le Roux, and Les Atlas. Full-capacity unitary recurrent neural networks. In Advances in neural information processing systems, pages 1880-4888, 2016.
Eugene Vorontsov, Chiheb Trabelsi, Samuel Kadoury, and Chris networks with long term dependencies. In International Conference on Machine Learning, pages 3570-3578, 2017.
orthogonality and learning recurrent
Jiong Zhang, Qi Lei, and Inderjit Dhillon. Stabilizing gradients for deep neural networks via efficient svd parameterization. urXiv preprint arXiv:/803.09327 2018.
Rainer Engelken, Fred Wolf, and LF Abbott. Lyapunov spectra of chaotic recurrent neural networks, arXiv preprint arXiv:2006.02422 2020.
Ryan Vogt, Maximilian Puelma Touzel, Eli Shlizerman, and Guillaume Lajoie. On іyаршпov exponents for mns:
Understanding information propagation using dynamical systems tools. arXiv preprint 141233, 2020.
Jan Drgona, Elliott Skomski, Soumya Vasisht, Aaron Tuor, and Draguna Vrabie. Spectral analysis and stability of deep neural dynamics. arXiv preprint arXiv:201 J. 13492, 2020.
Aaron Tuor, Jan Drgona, and Draguna Vrabic. Constrained neural ordinary differential equations with stability guarantces. arXiv preprint arXiv:2004. 10883, 2020.
António Ribeiro, Koen Tiels, Luis A Aguirre, and Thomas Schön. Beyond exploding and vanishing gradicnts: analysing rmn training using attractors and smoothness. In International Conference on Artificial Intelligence and Statistics, pages 2370-2380. PMLR, 2020.
Mahmoud Assran and Michael Rabbat. On the convergence of nesterov's accelerated gradient method in stochastic settings. arXiv preprint ar ar0iv:2002. 12414, 2020.
Othmane Sebbouh, Robert Gower, and Aaron Defazio. Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball. 2021.
Yan Yan, Tianbao Yang. Zhe Li. Qihang Lin, and Yi Yang. unified analysis of stochastic momentum methods for deep learning. arviv preprint 1808 10396, 2018.
Vien Mai and Mikael Johansson. Convergence of stochastic gradient method with momentum for non-smooth non-convex optimization. In International Conference Machine Learning, pages 6630-6639, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-778, 2016.
Yunpeng Chen, Jianan Li, Huaxin Xiao, Xiaojie Jin, Shuicheng Yan, and Jiashi Feng. Dual path networks. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 4470-4478, 2017.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1xXiv:1412.6988) 2014.
Yann LeCunn and Corinna Cortes. MNIST handwritten digit database. 2010.
Gábor Melis, Chris Dyer, and Phil Blunsom. On the state of the art of evaluation in neural language models. arXiv preprint arXiv:1707.05588 2017.
13


Reviews:
[{"review_id": "t0wOuGbB9qw", "reviewer": "Reviewer_Qm4o", "summary": "The paper considers the problem of training recurrent neural networks (RNNs) using an online bilevel optimization (OBLO). This allows to consider the problem as a meta-learning-like problem with streaming data, and obtain a new family of RNNs, dubbed as meta-RNN. The OBLO formulation is derived leading to two optimization problems that are solved interleaved. The first and inner stage is an inference step for the network (i.e., a forward pass) computes the hidden state out of the current network. Three versions are proposed to solve it based on stochastic gradient methods: SGD, SHB, and SNAG. Then, the convergence of these methods for this inner optimization task is analyzed theoretically to show the training stability in this inner optimization task. The second optimization aims to update the meta-RNN weights and hyperparameters. Last, the method is compared to several other RNN methods on four tasks: adding task, sequential MNIST and its permuted version, and HAR-2 (time series for activity recognition).\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "The idea of looking at meta-learning with OBLO as an RNN is novel to me. The idea seems interesting. The paper cites a long list of papers. While doing an extensive review of related work is welcomed, it is always nice to explain how the current work differentiates from each one of these. In some cases, one may find that some of these works may not need to be cited or their detailed summary relegated to the supplementary material while using the space for the own technical aspects of this work.\n\nThe submission seems mostly technically sound. There are a few details that are unclear or seem missing. I would appreciate if the authors can respond to my questions below on these and other matters. The theoretical part of the paper is welcomed, however it is common to refer to the gradients of the weight updates (2 stage) for training stability of RNNs. Moreover, the main paper does not discuss the details of solving the network parameters stage. Another welcomed aspect is the extensive comparison against other methods in the experimental section. On the other hand, the authors forgot to discuss how to apply the model after trained to new (e.g., test) sequences, like those in the test sets in the experimental section. Regarding your deep-RNN limitation, you may find some inspiration in [1]. \n\nThe paper seems nicely written and well organized. In general, the work is simple to understand. However, there some clarity details missing in the text that could improve the readability and reproducibility of this work. It is slightly confusing to go from RNN to meta-learning and back to meta-RNN in the introduction. Also, its motivation could be improved as well (what problem are we solving?). Referring to the parameters of the network with $\\theta$ as the hyperparameters (for meta-learning) was confusing. There are some details described above that are missing (e.g., applying trained model to new sequences, solving the other optimization task, theorem assumptions met).\n\nThe methods presented in this work are relevant to the NeurIPS community. However, the potential value of this work seems small in my opinion. The missing details and the several limitations of this work are behind my score. I would be happy to reconsider my score if the authors could address my concerns.\n\nQuestions for the authors:\n1. In Eq. (1), the RNN learning problem is defined as a constrained optimization problem. However, the constrain depends on $x$, which is part of the input distribution and changes with each input. It is unclear to me why this can be done. I would appreciate if the authors include the derivation that shows how they arrive to (1) from training. \n2. Could you comment whether the conditions of the Theorems 1 and 2 are met after updating the network weights for your choice of $F$? How can one make sure that the method remains stable over batches? It would be very valuable to discuss this in the main paper. \n3. How well does an LSTM perform in the HAR-2 10% and 1% of training data problem? (of similar hidden size and with a similar number of parameters.\n4. How does your meta-RNN deal with problems that need to output sequences instead of a single prediction?\n5. Both in training and testing(inference) time, what is the computational complexity (runtime and memory) of your method? How does it compare to training an RNN/LSTM  with SGD?\n\nMinor:\n* Please, consider removing the legend from inside the plots in Figure 4 to having it one time outside the plots. \n* Consider increasing font size in plots.\n\nReferences\n\n[1] Turek et al., Approximating Stacked and Bidirectional Recurrent Architectures with the Delayed Recurrent Neural Network, ICML 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "One important limitation that hasn't been addressed or mentioned by the authors is the fact that sequences can have variable length. This is very common in natural language for example. Another limitations not addressed is solving tasks that require sequential outputs.\n\nOther limitations and societal impact have been mentioned to the best of my understanding.", "review_text": "", "extra_scores": {"ethical_concerns": "Not to the best of my knowledge.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "suitKgd0yrp", "reviewer": "Reviewer_Vvok", "summary": "The authors propose viewing RNNs as meta-learning algorithms, where the RNN parameters optimize the hidden state. By using carefully chosen functions they show that reasonable RNN cells come out, like a residual RNN. They experimentally show to perform on par or better than competing approaches in 3 toy tasks.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "Pros\n- Seemingly good results on toy tasks.\n\nCons\n- The authors make the paper unnecessarily difficult to follow by trying to draw parallel to meta-learning and optimization algorithms. The fact that the proposed RNN cells are the application of an optimization algorithm on a carefully chosen function doesn't add anything to the discussion. You could probably choose the function carefully  enough to get an LSTM or any other kind of RNN in the for of a meta-RNN. It's clear the authors have carefully chosen the function (Equation 10) to get an affine transformation as it's derivative (Equation 11). \n- Theorem 2 should just be an observation. Obviously, if you have a residual connection which dominates, you're gradient won't vanish/explode. However, this again becomes harder to see if you make claims about meta-learning using the SGD optimizer.\n- The paper lacks proper experiments. HAR-2, MNIST and the adding task are just toy problems that should be used to illustrate elements of the model. They can't be the only supporting experimental evidence.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "KBS5NoSD9j", "reviewer": "Reviewer_8SmP", "summary": "This paper proposes a formulation of RNNs which allow practitioners to train RNNs using bilevel optimization algorithms. This is a novel perspective of RNNs.\n\nThe authors claim that their formulation of RNNs as an optimization process and their approach of training RNNs by solving a bilevel optimization problem prevents the problems of gradient vanishing/exploding. The authors demonstrate their methods on small datasets such as Pixel MNIST, Permutation MNIST, and HAR-2 (a dataset from phone accelerometer/gyroscope for activity recognition).\n", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "The paper provides an interesting and novel perspective of RNNs. I will first summarize the method. Let $h_t$ be an RNN’s state at time step $t$, then the standard forward propagation of RNNs would set $h_t = f(h_{t-1}, \\theta)$ where $f$ is the parameterized function of the RNNs (such as an LSTM). Now, instead of enforcing the equality $h_t = f(h_{t-1}, \\theta)$, this paper treats $h_t$ as a *free* parameter that should minimize the difference $|| h_t - f(h_{t-1}, \\theta) || $. Under this formulation, the forward pass of an RNN can be treated as an optimization problem. This paper considers this optimization problem to be an inner loop of a bilevel optimization problem. Now, the entire RNN is supposed to minimize an objective function – for instance, predicting the correct MNIST pixel at each step. This objective function can be treated as an outer loop of the RNN’s bilevel optimization problem. This resulting bilevel optimization problem removes the recursive dependency of each $h_t$ on $h_{<t}$, and hence effectively avoids the RNN’s gradients from vanishing/exploding.\n\nI personally find this bilevel optimization perspective of RNNs fascinating, novel, and interesting. In addition to this interesting formulation, the authors also derive an efficient analytical formula to iteratively solve their bilevel optimization problem using gradient-based updates (Equation 10-11). The authors also demonstrate that their meta-RNNs can be trained effectively to perform well on some small RNN tasks, namely Pixel-MNIST, Permuted-MNIST, and HAR-2.\n\nWhile I like the perspective of this paper very much, I believe the following discussions and analysis should be included, in order for meta-RNNs to become useful:\n\n1. Experiments on larger, more “real” situations such as large language models, should be conducted. There is also the Long-range Arena challenge, which measures how well RNNs can learn on long sequences. The authors can consider trying meta-RNNs on that challenge too.\n\n2. Bilevel optimization is slow and finicky. The authors should compare the training time of meta-RNNs with other baselines. Table 2 does report the training time of meta-RNNs, but I cannot find any comparison of meta-RNNs’s training time and other methods. The comparison should be in controlled environments, e.g. on the same devices.\n\n3. RNNs are no longer the state-of-the-art in sequence modeling. That title belongs to the Transformer model now. Can meta-RNNs achieve the same performance with Transformer? What are the pros and cons in comparison?\n\nOverall, despite the novel perspective that this paper describes, I wish the authors had added larger and more “real” experiments to attest to the strengths of their model and method. Therefore, I am not certain whether this paper should be accepted or rejected.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Interesting novel perspective. Little to no practical impact for the present.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "9hLYye-QQuJ", "reviewer": "Reviewer_2xM4", "summary": "This paper formulates the problem of RNN training as a bilevel optimization problem in which the outer optimization is over the RNN parameters and the inner optimization is over the RNN activations. The authors prove upper bounds on the hidden feature distance of similar inputs. Moreover, the authors prove bounds on the inner optimization rate to guarantee training stability. Finally, the authors empirically find that their RNN formulation requires fewer parameters, less training data and converges faster than competing RNN formulations on benchmark problems.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "**Originality**\nThis paper appears similar to prior works that view RNN hidden states as equilibrium points of a dynamical system (as noted by the authors in section 2). In this paper, the dynamical system over hidden states is itself an optimization. However, this contribution does not seem particularly novel since in prior work like iRNN, the dynamics of hidden states can also be viewed as an optimization (in which equilibrium points represent local minima of the lower-level optimization problem).\n\n**Quality**\nThe theoretical claims appear correct and provide some justification for using meta-RNN, although it is not clear whether the results are specific to meta-RNN or whether similar results could be shown for standard RNNs.\n\nThe authors compare meta-RNN to several baselines. Unfortunately, the experimental results do not convincingly show that meta-RNN requires fewer parameters and less training data than baselines. Firstly, in Figure 5, meta-RNN-dense appears to require a similar number of parameters as baselines. Meta-RNN-sparse requires fewer parameters, but this does not appear to be a fair comparison with other dense methods such as regular RNN. A fair comparison would compare meta-RNN-sparse with sparse versions of baselines.\n\nMoreover, the claim that meta-RNN requires less training data than baselines is not well supported by Figure 4. It appears that meta-RNN performs better than baselines in general for both the 1% and 10% training data settings on HAR-2. There doesn't appear to be evidence that meta-RNN is better than baselines *particularly* when training data is limited. This is partly because training curves for the full HAR-2 training data sets are not presented.\n\nFinally, the datasets appear relatively simple. Conducting experiments on more challenging datasets would significantly improve this work.\n\nIn summary, the experiments could be further improved as follows:\n1) Compare with sparse versions of baselines\n2) Show that meta-RNN performs relatively better than baselines in regimes with low training data (vs. high training data)\n3) Conduct experiments on more challenging datasets.\n\n\n**Clarity**\nThe framing of the method in this paper as a type of meta-learning is slightly confusing since meta-learning typically refers to settings where a shared set of meta-parameters are found over several related datasets or tasks. In this paper, the shared set of meta-parameters correspond to a single task, which makes it unclear initially how this setting corresponds to meta-learning.\n\nIn general, meta-learning is a specific case of bilevel optimization in which an upper-level optimization problem is conducted over *several* different lower-level optimization problems. I believe that meta-RNN can be categorized as a type of meta-learning-  however, this needs to be further clarified by the authors.\n\nIn addition, it would help for the authors to clarify how their work conceptually differs from other RNN formulations with equilibrium hidden states. In section 3.2, the authors imply that prior works do not really solve their lower-level optimization problems- it would be ideal if the authors could be provide evidence for this.\n\nThere are also a few minor improvements that could be made:\n1) If the authors wish to retain the meta-learning framing, it would help to refer to hyperparameters as meta-parameters\n2) $\\epsilon$ is not defined in Theorem 2\n3) The authors state in section 3.1 that \"Recall that the goal of RNNs is to learn discriminant representations for different data sequences, regardless of how the intermediate hidden states are defined.\". This does not necessarily seem to be true: certain tasks may require similar representations for different data sequences. In general, the goal of RNNs depends on the optimization objective.\n\n**Significance**\nCurrently, this contribution appears to be relatively incremental relative to prior RNN formulations that also use a dynamic update process to define hidden states. However, if experimental results and the clarity of the paper can be improved, the contributions of meta-RNN using fewer parameters, training data and training time could leave a significant impact in the research community.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately state the limitations of the work in the conclusion. There also do not appear to be potential negative societal impacts specific to this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall this paper is not well written and it is hard to understand why the main algorithm (Algorithm 1) makes sense. It is also not clear if the relationship to meta-learning is useful. The results are on toy problems only plus on PennTreebank added during the rebuttal with performance much worse than ones reported in the literature for LSTM’s (on this dataset). It is good that there is a lot of relationship to literature, but the authors should provide in clearer derivation and intuitive explanation of the algorithm and resolved the discrepancy between their performance and the ones in literature.

Mini review from AC:
Even after the discussions I still don’t understand why Algorithm 1 makes sense. Intuitively, consider a sequence such as text. Inputs (x_t’s) at different time represent different pieces of information that need to be aggregated and processed using the rnn. One part of the text talks about something and another talks about something else. Why is h_t a gradient step from h_{t-1} of a function of x_t? Since x_t have completely different meaning at different times, how is this optimising anything? Is it because of assumption at line 142 and why this then possibly works so badly on PTB? Another thing unclear in the algorithm: The innermost loop in Algorithm 1 is a deterministic computation that depends on x and theta*. How does the h_T in the upper level optimisation then depend on theta (without star)? Or is it meant to be theta* and the theta, w minimization is done using bptt? Can you please provide full self-contained details of this algorithm together with the intuitive explanation why it makes sense?

Decision: Accept (Poster)