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...lab......... 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.. 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. 20 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 | [2113a] 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. E arg min ExpxP, F (h,x;;0) ho 0, Vx, E Ex, Vt E [T]. (6) w.0
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 as 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- - oi), V = ah-11 Φ1.
(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 similat 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 I Lz||xx x(11- Then for SGD in Eq. 7 we have
|1,, h2ll S Σ nLa(11 + +,
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 11 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 ||/, - M6lll 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. 128, 1% training date
0.25
Adding Task, T-100
dence SGD
0.90
0.90
0.70
sparse 5GD
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
ShAG
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 x 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- -otut 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-1744 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.//////aaaoooooooooo 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-Lewandowskk 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-presse 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.94128000
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": "seju3_8LowL", "reviewer": "Reviewer_AbCy", "summary": "This paper considered bi-level gradient-based meta-learning for training Recurrent Neural Networks (RNNs). In this paper, the author first formulated the training problem of RNNs as a bi-level meta-learning problem, where the inner level learns the hidden states of the RNN while the outer level optimizes the RNN’s model weights as well as the hyperparameters for hidden states. In addition, the author proposed a class of RNN, namely meta-RNN, which can be formulated via online bi-level optimization. To solve the inner-level problem, this paper considered SGD and two variants with momentum, thus the inner-level optimization process can be formulated as the meta-RNN with certain architecture. The authors provided theoretical analyses on how the proposed meta-RNN could handle gradient vanishing or exploding as well as some potential reasons for faster convergence of meta-RNN. At last, several experiments were conducted to show their method’s performance and convergence rate.", "questions": "", "limitations": "", "rating": 8, "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": "This paper has several strengths yet also triggers nontrivial concerns.\n\nStrengths:\n•\tThe main technical contribution is solid (bi-level gradient-based meta-learning of RNN)\n•\tThough simple, the techniques proposed in this paper (in particular, meta-learning for training RNN) look reasonable and novel to me.\n•\tBoth theories and empirical results are shown to support the author’s claims about the proposed method’s superiority.\n\nWeaknesses:\n•\tI have some concerns with respect to Eq (6). First, in line 145, why function F is from the feasible space H? Shouldn’t it be hidden state h is from H? Second, in line 147, should “the hyperparameter θ of h” be corrected as “the hyperparameter θ of F”? Also, I am not quite sure why function F has the variable x which is related to t but after “argmin” the hidden state becomes free of t?\n•\tThe name meta RNN seems already been used in some published papers. For example, the paper named \"Meta-Learning Backpropagation And Improving It\". Actually, I found that there have been several published papers under this umbrella (meta RNNs), but I did not find most of them in this paper’s literature review section. I think it is important and necessary to differentiate the meta-RNN proposed in this paper from those I just mentioned to help better evaluate this work’s overall novelty.\n•\t The current Thm 1 is interesting and makes sense to some degree but based on my understanding the assumption over F seems too strong to be applicable for more sophisticated cases like more advanced RNNs with F not satisfying those two variable-wise Lipschitz conditions. \n•\tSome places need to be refined in the current manuscript. For example, in Figure 1, the curves for SHB and SNAG are highly overlapped, and I can barely see that for SHB after zooming in. In addition, I am not sure why the author spent almost one-page discussing different architectures of current RNNs, which seems not closely related to the core of this paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no obvious negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "dBHmiO9fB64", "reviewer": "Reviewer_5uYD", "summary": "The paper formulates an RNN as a meta-learning problem, where the inner loop updates the sequence of recurrent hidden states and the outer loop minimizes a given task loss. Unlike a normal RNN, where each hidden state is computed from a previous hidden state by an MLP, the paper proposes to compute each hidden state from the previous hidden state by taking a gradient step towards a given inner loop objective. The main benefit of so doing is that we avoid the vanishing/exploding gradients problem, and the main drawback is that we have to pay the additional memory/compute cost of doing gradient-based meta-learning.", "questions": "", "limitations": "", "rating": 7, "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": "This is a highly novel idea: using meta-learning as a solution to an RNN's vanishing/exploding gradients problem is very original and not something that I have encountered in the literature. It also draws interesting connections between neural ODEs and meta-learning / bi-level optimization, and shows promising results on toy tasks.\n\nMy main concern with the paper is that it does not acknowledge the limitations of the method it is proposing. Learning long sequences with RNNs is an optimization challenge because of the vanishing gradients problem. While the proposed solution avoids the optimization challenge, it introduces a resource challenge because of the cost of second-order optimization in gradient-based meta-learning. This could make the solution prohibitive for long sequences, thus ultimately still thwarting our goal of learning long sequences with RNNs.\n\nI'd like to see the authors acknowledge this limitation, show comparisons on actual wall-clock run time and memory use instead of just the number of parameters, and discuss solutions that can be explored in future work to overcome it.\n\nNit: I think the presentation of the ideas can be made clearer if the introduction was re-written to provide more motivation and background. \n\nEdit: I had a misunderstanding where I thought that the authors were computing second-order gradients by backpropagating through gradient descent as in MAML. However, with a suitable F, we don't have to compute any second-order information. Specifically, equation (11) shows this. I'm increasing my score to a 7 to reflect this.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "3wJb9vFgynT", "reviewer": "Reviewer_doUF", "summary": "The paper proposes to view RNN training as a bi-level optimisation process:\n* Inner loop: Updating states $h_t$ by following the the gradient of the transition function $h_t \\leftarrow h_{t-1} - \\eta \\nabla F(h_{t-1}, x_t; \\theta)$\n* Outer loop: Updating the transition function parameters $\\theta$ and hyperparameters $\\omega$\n\nThe authors empirically demonstrate learning with fewer parameters, less training data, and faster convergence compared to vanilla RNNs and related methods (iRNN, FastRNN, LipschitzRNN).\n\nThe authors prove that vanishing and exploding gradients can be avoided by selecting a proper learning rate in the inner loop.", "questions": "", "limitations": "", "rating": 6, "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": "# Significance & Originality\n\nRecurrent neural networks (RNNs) are extensively used in the deep learning literature. Any advances in training stability, convergence, and sample efficiency have far-reaching implications for many machine learning models. Viewing the training of RNNs as a bilevel optimisation is an interesting perspective, although seems very related to meta learning of objective functions [1-3].\n\n# Empirical gains, LSTM comparison in fig 4 and table 2 needed\n\nThe authors show on simple benchmarks (MNIST, Permuted MNIST, HAR-2) that their method converges faster, requires less training data, and can be trained with fewer parameters.\n\nUnfortunately, the ubiquitous LSTM baseline is missing in the experiments in figure 4 and table 2.\nHow does convergence compare? How does the LSTM fare with less training data? How do the learning curves compare? At least the final performance of the LSTM in figure 5 seems to be lower.\n\n# Training stability proof\n\nThe authors proof that for small enough inner-loop learning rates, vanishing and exploding gradients are avoided.\nThis is a very interesting insight, although I have not checked the proofs in detail.\n\n# Scalability to harder benchmarks?\n\nWould the gains in sample efficiency, performance, and sparsity transfer to harder tasks?\nAs no explanation is given on why these improvements are observed it is hard to judge whether these benefits would extend to harder problems.\nI think the current preliminary experiments are OK, but it would be very useful to have some scaled experiments.\n\n# Can this be extended to sequence-to-sequence problems?\n\nAlong these lines I wonder whether the same or a similar framework could apply to sequence-to-sequence problems (eg RL settings or encoder-decoder architectures). At the moment the authors only have a single scalar label for each sequence. As the authors argue about RNNs in general, this is an important aspect to discuss. I am not sure whether the same gradient-based dynamics would be useful in the seq-2-seq setup.\n\n# Connection to meta-learning objective functions\n\nThere is work on meta-learning objective functions that are used to update a neural network / RL policy in the inner loop [1-3]. This also forms a recurrent neural network as a bi-level optimisation very similar to the proposed principle (where the RNN state corresponds to the network parameters). The proposed paper puts this in a different perspective and adds empirical and theoretical insights, so I don't think this should be an issue for acceptance. But I would highly encourage the authors to discuss the connections and cite these related works.\n\n[1] Chebotar, Y., Molchanov, A., Bechtle, S., Righetti, L., Meier, F., & Sukhatme, G. (2019). Meta-Learning via Learned Loss. ArXiv Preprint ArXiv:1906.05374.\n\n[2] Kirsch, L., van Steenkiste, S., & Schmidhuber, J. (2020). Improving Generalization in Meta Reinforcement Learning using Learned Objectives. International Conference on Learning Representations.\n\n[3] Oh, J., Hessel, M., Czarnecki, W. M., Xu, Z., van Hasselt, H., Singh, S., & Silver, D. (2020). Discovering Reinforcement Learning Algorithms. ArXiv Preprint ArXiv:2007.08794.\n\n# Why is less training data impacting the proposed method less?\n\nThe authors argue that 'One of the benefits from meta-learning is to learn models using less data'. But this applies only to meta-test time.\nIn contrast, the author's are interested in training efficiency at meta-training time.\nThus, I believe the statement is not true and requires additional justification why their method may be more sample efficient.\n\n# meta-RNN naming conflicts with existing work\n\nSometimes previous work for RNNs that meta-learn in their activations (without gradients) [4,5] are referred to as Meta RNNs [2].\nThis conflicts with the method name the authors propose.\nI suggest to adapt the naming scheme.\n\n[4] Hochreiter, S., Younger, A. S., & Conwell, P. R. (2001). Learning to learn using gradient descent. International Conference on Artificial Neural Networks.\n\n[5] Wang, J. X., Kurth-Nelson, Z., Tirumala, D., Soyer, H., Leibo, J. Z., Munos, R., Blundell, C., Kumaran, D., & Botvinick, M. (2016). Learning to reinforcement learn. ArXiv Preprint ArXiv:1611.05763.\n\n# Summary\n\nThis is a good paper, but needs some additional discussions, experiments, and related work as described above. I would consider raising my score if the authors address most of these issues.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately discussed the limitations of their work, although it is not clear yet how well their method scales to harder problems.\nThe authors have not discussed any societal impacts of their work. Their contribution is very theoretical, so I would consider this OK.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "1PXOYGPpWiQ", "reviewer": "Reviewer_CDfk", "summary": "This paper addresses exploding and/or vanishing gradient problems assocaited with the training of RNNs. It does so by considering RNN training as a meta-learning problem, where the hidden states are a set of variables that are optimized in conjunction with the parameters of the network. This is in turn formulated as a bilevel optimization problem, where the lower level optimization learns data representations for each class, and the upper-level optimization learns the both the transition function parameters and final classifier parameters. From this, they present theory and experiments giving evidence of fewer (or no) troublesome gradient behavior, and shows that the method performs particularly well in data-scarce and low-parameter contexts.", "questions": "", "limitations": "", "rating": 7, "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": "I enjoyed this paper quite a bit - it offers a new perspective on a well-known training problem with RNNs, and framing the problem in this way leads to several insights on the problem and is translated into better methods for empirical performance. It was well-written, contained some nice theorems, and had well-organized experimental results. In particular, I was impressed that the meta-RNN-sparse, which reduces the transition matrix to a single learnable parameter, manages to achieve reasonably good results, as most other RNN methods would fall apart in this case.\n\nI do have a few minor concerns and comments.\n\n1) I was surprised to see the assumption that each x_t is drawn from a distribution based only on y. Do I have it right that 1) this implies no interdependence among inputs at different timesteps, and that 2) this assumption is not often the case in real-world datasets (e.g. MNIST)? On its own I'm not too concerned about this - if we are aiming for a method that we want to perform well in practice, a minor unrealistic assumption along the way is not the end of the world. But in light of this, I found it strange to call upon this fact in line 228 when giving some intuition about faster empirical convergence; in a real dataset, I think it would be fairly unlikely that \\gamma_t would actually be much smaller for samples from the same class vs those in different classes, because the thing that makes that sequence belong to a specific class has much more to do with the interrelations between inputs than each input considered in isolation. Please let me know if I am off here.\n\n2) I have seen in several other RNN papers the practice of treating the initial hidden vector h_0 as a learnable parameter, and in practice seems to be a simple method for improving performance. Is there a reason you didn't want to do this? How would this interact with the assumptions and formulations of your method?\n\n3) I would have liked to see some larger experiments, e.g. bigger datasets or D=256, though considering the large number of competing experiments and the convention in the literature, sticking to D=128 is understandable.\n\n4) This is very minor, but some of the figures are a bit poorly constructed; in Figure 2, the notation inside the boxes does not fit, and in Figure 5a, it seems the meta-RNN-dense box is almost completely covering up the FastGRNN symbol, which I did not notice until zooming in (presumably the point of the symbols in these plots being unfilled is so that this does not happen!).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed this.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new type of RNN where the hidden state at the current time step is taken to be the result of a single optimizer step applied to a function involving the previous hidden state and the current observation. It is argued that if the optimizer step defining the dynamics uses a learning rate that scales as 1/T, where T is the number of time steps, then the parameter gradient will be well behaved (i.e. won't vanish or explode). 

The reviewers liked the paper and its core idea, and viewed it as a solid contribution to the field of RNN design. Their main complaint was about the small-scale nature of the experiments and the lack of an LSTM comparison, which the paper's authors have promised to address in a future revision.

There are two possible problems that stick out to me as the meta-reviewer. First, the 1/T learning rate for the hidden state dynamics seems like it would be too small to allow the hidden state to adapt quickly to new inputs. And second, "meta learning" is probably not the right way to frame what this method is doing, since the hidden state dynamics aren't really "learning" anything. (Using an optimizer doesn't equate to learning.)

Despite this concerns I will recommend this paper for acceptance.
Decision: Accept (Poster)