Year: 2019

Abstract:
Deep unfolding methods design deep neural networks as learned variations of optimization methods. These networks have been shown to achieve faster convergence and higher accuracy than the original optimization methods. In this line of research, this paper develops a novel deep recurrent neural network (coined reweighted-RNN) by unfolding a reweighted `1-`1 minimization algorithm and applies it to the task of sequential signal reconstruction. To the best of our knowledge, this is the first deep unfolding method that explores reweighted minimization. Due to the underlying reweighted minimization model, our RNN has a different soft-thresholding function (alias, different activation function) for each hidden unit in each layer. Furthermore, it has higher network expressivity than existing deep unfolding RNN models due to the over-parameterizing weights. Moreover, we establish theoretical generalization error bounds for the proposed reweighted-RNN model by means of Rademacher complexity. The bounds reveal that the parameterization of the proposed reweighted-RNN ensures good generalization. We apply the proposed reweighted-RNN to the problem of video-frame reconstruction from low-dimensional measurements, that is, sequential frame reconstruction. The experimental results on the moving MNIST dataset demonstrate that the proposed deep reweighted-RNN significantly outperforms existing RNN models.

heading: 1 INTRODUCTION
text: The problem of reconstructing sequential signals from low-dimensional measurements across time is of great importance for a number of applications such as time-series data analysis, future-frame prediction, and compressive video sensing. Specifically, we consider the problem of reconstructing a sequence of signals st ∈ Rn0 , t = 1, 2, . . . , T , from low-dimensional measurements xt = Ast, where A ∈ Rn×n0 (n n0) is a sensing matrix. We assume that st has a sparse representation ht ∈ Rh in a dictionary D ∈ Rn0×h, that is, st = Dht. At each time step t, the signal st can be independently reconstructed using the measurements xt by solving (Donoho, 2006):
min ht {1 2 ‖xt −ADht‖22 + λ‖ht‖1 } , (1)
where ‖ · ‖p is the `p-norm and λ is a regularization parameter. The iterative shrinkage-thresholding algorithm (ISTA) (Daubechies et al., 2004) solves (1) by iterating over h(l)t = φλ
c (h
(l−1) t −
1 cD TAT(ADh (l−1) t − xt)), where l is the iteration counter, φγ(u) = sign(u)[0, |u| − γ]+ is the soft-thresholding operator, γ = λc , and c is an upper bound on the Lipschitz constant of the gradient of 12‖xt −ADht‖ 2 2.
Under the assumption that sequential signal instances are correlated, we consider the following sequential signal reconstruction problem:
min ht {1 2 ‖xt −ADht‖22 + λ1‖ht‖1 + λ2R(ht,ht−1) } , (2)
where λ1, λ2 > 0 are regularization parameters and R(ht,ht−1) is an added regularization term that expresses the similarity of the representations ht and ht−1 of two consecutive signals. Wisdom et al. (2017) proposed an RNN design (coined Sista-RNN) by unfolding the sequential version of
ISTA. That study assumed that two consecutive signals are close in the `2-norm sense, formally, R(ht,ht−1) = 1 2‖Dht − FDht−1‖ 2 2, where F ∈ Rn0×n0 is a correlation matrix between st and st−1. More recently, the study by Le et al. (2019) designed the `1-`1-RNN, which stems from unfolding an algorithm that solves the `1-`1 minimization problem (Mota et al., 2017; 2016). This is a version of Problem (2) with R(ht,ht−1) = ‖ht −Ght−1‖1, where G ∈ Rh×h is an affine transformation that promotes the correlation between ht and ht−1. Both studies (Wisdom et al., 2017; Le et al., 2019) have shown that carefully-designed deep RNN models outperform the generic RNN model and ISTA (Daubechies et al., 2004) in the task of sequential frame reconstruction.
Deep neural networks (DNN) have achieved state-of-the-art performance in solving (1) for individual signals, both in terms of accuracy and inference speed (Mousavi et al., 2015). However, these models are often criticized for their lack of interpretability and theoretical guarantees (Lucas et al., 2018). Motivated by this, several studies focus on designing DNNs that incorporate domain knowledge, namely, signal priors. These include deep unfolding methods which design neural networks to learn approximations of iterative optimization algorithms. Examples of this approach are LISTA (Gregor & LeCun, 2010) and its variants, including ADMM-Net (Sun et al., 2016), AMP (Borgerding et al., 2017), and an unfolded version of the iterative hard thresholding algorithm (Xin et al., 2016).
LISTA (Gregor & LeCun, 2010) unrolls the iterations of ISTA into a feed-forward neural network with weights, where each layer implements an iteration: h(l)t = φγ(l)(W (l)h (l−1) t + U
(l)xt), with W(l) = I − 1cD TATAD, U(l) = 1cD TAT, and γ(l) being learned from data. It has been shown (Gregor & LeCun, 2010; Sprechmann et al., 2015) that a d-layer LISTA network with trainable parameters Θ = {W(l),U(l), γ(l)}dl=1 achieves the same performance as the original ISTA but with much fewer iterations (i.e., number of layers). Recent studies (Chen et al., 2018; Liu et al., 2019) have found that exploiting dependencies between W(l) and U(l) leads to reducing the number of trainable parameters while retaining the performance of LISTA. These works provided theoretical insights to the convergence conditions of LISTA. However, the problem of designing deep unfolding methods for dealing with sequential signals is significantly less explored. In this work, we will consider a deep RNN for solving Problem (2) that outputs a sequence, ŝ1, . . . , ŝT from an input measurement sequence, x1, . . . ,xT , as following:
ht = φγ(Wht−1 + Uxt),
ŝt = Dht. (3)
It has been shown that reweighted algorithms—such as the reweighted `1 minimization method by Candès et al. (2008) and the reweighted `1-`1 minimization by Luong et al. (2018)—outperform their non-reweighted counterparts. Driven by this observation, this paper proposes a novel deep RNN architecture by unfolding a reweighted-`1-`1 minimization algorithm. Due to the reweighting, our network has higher expressivity than existing RNN models leading to better data representations, especially when depth increases. This is in line with recent studies (He et al., 2016; Cortes et al.; Huang et al., 2017), which have shown that better performance can be achieved by highly overparameterized networks, i.e., networks with far more parameters than the number of training samples. While the most recent studies (related over-parameterized DNNs) consider fully-connected networks applied on classification problems (Neyshabur et al., 2019), our approach focuses on deep-unfolding architectures and opts to understand how the networks learn a low-complexity representation for sequential signal reconstruction, which is a regression problem across time. Furthermore, while there have been efforts to build deep RNNs (Pascanu et al., 2014; Li et al., 2018; Luo et al., 2017; Wisdom et al., 2017), examining the generalization property of such deep RNN models on unseen sequential data still remains elusive. In this work, we derive the generalization error bound of the proposed design and further compare it with existing RNN bounds (Zhang et al., 2018; Kusupati et al., 2018).
Contributions. The contributions of this work are as follows:
• We propose a principled deep RNN model for sequential signal reconstruction by unfolding a reweighted `1-`1 minimization method. Our reweighted-RNN model employs different soft-thresholding functions that are adaptively learned per hidden unit. Furthermore, the proposed model is over-parameterized, has high expressivity and can be efficiently stacked.
• We derive the generalization error bound of the proposed model (and deep RNNs) by measuring Rademacher complexity and show that the over-parameterization of our RNN ensures good generalization. To best of our knowledge, this is the first generalization error
bound for deep RNNs; moreover, our bound is tighter than existing bounds derived for shallow RNNs (Zhang et al., 2018; Kusupati et al., 2018).
• We provide experiments in the task of reconstructing video sequences from low-dimensional measurements. We show significant gains when using our model compared to several state-of-the-art RNNs (including unfolding architectures), especially when the depth of RNNs increases.
2 A DEEP RNN VIA UNFOLDING REWEIGHTED-`1-`1 MINIMIZATION
In this section, we describe a reweighted `1-`1 minimization problem for sequential signal reconstruction and propose an iterative algorithm based on the proximal method. We then design a deep RNN architecture by unfolding this algorithm.
The proposed reweighted `1-`1 minimization. We introduce the following problem:
min ht {1 2 ‖xt −ADZht‖22 + λ1‖g ◦ Zht‖1 + λ2‖g ◦ (Zht −Ght−1)‖1 } , (4)
where “◦” denotes element-wise multiplication, g ∈ Rh is a vector of positive weights, Z ∈ Rh×h is a reweighting matrix, and G ∈ Rh×h is an affine transformation that promotes the correlation between ht−1 and ht. Intuitively, Z is adopted to transform ht to Zht ∈ Rh, producing a reweighted version of it. Thereafter, g aims to reweight each transformed component of Zht and Zht −Ght−1 in the `1-norm regularization terms. Because of applying reweighting (Candès et al., 2008), the solution of Problem (4) is a more accurate sparse representation compared to the solution of the `1-`1 minimization problem in Le et al. (2019) (where Z = I and g = I). Furthermore, the use of the reweighting matrix Z to transform ht to Zht differentiates Problem (4) from the reweighted `1-`1 minimization problem in Luong et al. (2018) where Z = I.
The objective function in (4) consists of the differentiable fidelity term f(Zht) = 12‖xt−ADZht‖ 2 2 and the non-smooth term g(Zht) = λ1‖g ◦ Zht‖1 + λ2‖g ◦ (Zht −Ght−1)‖1. We use a proximal gradient method (Beck & Teboulle, 2009) to solve (4): At iteration l, we first update h(l−1)t —after being multiplied by Zl—with a gradient descent step on the fidelity term as u = Zlh (l−1) t − 1 cZl∇f(h (l−1) t ), where ∇f(h (l−1) t ) = D TAT(ADh (l−1) t − xt). Then, h (l) t is updated as
h (l) t = Φλ1
c gl, λ2 c gl,Ght−1
( Zlh (l−1) t − 1
c Zl∇f(h(l−1)t )
) , (5)
where the proximal operator Φλ1 c gl, λ2 c gl,Ght−1 (u) is defined as
Φλ1 c gl, λ2 c gl,~ (u) = arg min v∈Rh {1 c g(v) + 1 2 ||v − u||22 } , (6)
with ~ = Ght−1. Since the minimization problem is separable, we can minimize (6) independently for each of the elements gl, ~, u of the corresponding gl, ~, u vectors. After solving (6), we obtain Φλ1
c gl, λ2 c gl,~
(u) [for solving (6), we refer to Proposition B.1 in Appendix B]. For ~ ≥ 0:
Φλ1 c gl, λ2 c gl,~≥0 (u) =  u− λ1c gl − λ2 c gl, ~ + λ1 c gl + λ2 c gl < u <∞ ~, ~ + λ1c gl − λ2 c gl ≤ u ≤ ~ + λ1 c gl + λ2 c gl u− λ1c gl + λ2 c gl, λ1 c gl − λ2 c gl < u < ~ + λ1 c gl − λ2 c gl 0, −λ1c gl − λ2 c gl ≤ u ≤ λ1 c gl − λ2 c gl
u+ λ1c gl + λ2 c gl, −∞ < u < − λ1 c gl − λ2 c gl,
(7)
and for ~ < 0:
Φλ1 c gl, λ2 c gl,~<0 (u) =  u− λ1c gl − λ2 c gl, λ1 c gl + λ2 c gl < u <∞ 0, −λ1c gl + λ2 c gl ≤ u ≤ λ1 c gl + λ2 c gl u+ λ1c gl − λ2 c gl, ~− λ1 c gl + λ2 c gl < u < − λ1 c gl + λ2 c gl ~, ~− λ1c gl − λ2 c gl ≤ u ≤ ~− λ1 c gl + λ2 c gl
u− λ1c gl + λ2 c gl, −∞ < u < ~− λ1 c gl − λ2 c gl
(8)
Under review as a conference paper at ICLR 2020
ℏ − − 1 2
ℏ − +
1 2
( ) , ,ℏ 1 2
ℏ
+
1 2
− +
1 2
0
ℏ + + 1 2 − − 1 2 ( ) , ,ℏ 1 2 ℏ + − 1 2 ℏ − 1 2 0
Algorithm 1: The proposed algorithm for sequential signal reconstruction. 1 Input: Measurements x1, . . . ,xT , measurement matrix A, dictionary D, affine transform G,
initial h(d)0 ≡ h0, reweighting matrices Z1, . . . ,Zd and vectors g1, . . . , gd, c, λ1, λ2. 2 Output: Sequence of sparse codes h1, . . . ,hT . 3 for t = 1,. . . ,T do 4 h
(0) t = Gh (d) t−1
5 for l = 1 to d do 6 u = [Zl − 1cZlD TATAD]h(l−1)t + 1cZlD TATxt 7 h (l) t = Φλ1
c gl, λ2 c gl,Gh (d) t−1
(u)
8 end 9 end
10 return h(d)1 , . . . ,h (d) T
Fig. 1 depicts the proximal operators for ~ ≥ 0 and ~ < 0. Observe that different values of gl lead to different shapes of the proximal functions Φλ1
c gl, λ2 c gl,~ (u) for each element u of u. Our iterative algorithm is given in Algorithm 1. We reconstruct a sequence h1, . . . ,hT from a sequence of measurements x1, . . . ,xT . For each time step t, Step 6 applies a gradient descent update for f(Zht−1) and Step 7 applies the proximal operator Φλ1
c gl, λ2 c gl,Gh (d) t−1 element-wise to the result. Let us compare the proposed method against the algorithm in Le et al. (2019)—which resulted in the `1-`1-RNN—that solves the `1-`1 minimization in Mota et al. (2016) (where Zl = I and gl = I). In that algorithm, the update terms in Step 6, namely I− 1cD TATAD and 1cD TAT, and the proximal operator in Step 7 are the same for all iterations of l. In contrast, Algorithm 1 uses a different Zl matrix per iteration to reparameterize the update terms (Step 6) and, through updating gl, it applies a different proximal operator to each element u (in Step 7) per iteration l.
The proposed reweighted-RNN. We now describe the proposed architecture for sequential signal recovery, designed by unrolling the steps of Algorithm 1 across the iterations l = 1, . . . , d (yielding the hidden layers) and time steps t = 1, . . . , T . Specifically, the l-th hidden layer is given by
h (l) t =  Φλ1c g1,λ2c g1,Gh(d)t−1 ( W1h (d) t−1 + U1xt ) , if l = 1,
Φλ1 c gl, λ2 c gl,Gh (d) t−1
( Wlh (l−1) t + Ulxt ) , if l > 1,
(9)
and the reconstructed signal at time step t is given by ŝt = Dh (d) t ; where Ul, Wl, V are defined as
Ul = 1
c ZlD
TAT,∀l, (10)
W1 = Z1G− 1
c Z1DTATADG, (11)
Wl = Zl − 1
c ZlD
TATAD, l > 1. (12)
The activation function is the proximal operator Φλ1 c gl, λ2 c gl,~ (u) with learnable parameters λ1, λ2, c, gl (see Fig. 1 for the shapes of the activation functions).
Under review as a conference paper at ICLR 2020 11/12/2019 Copy of Copy of Copy of deepRNN.drawio
3/4
𝐡 (𝑑)
𝑡−1
𝐡 (1) 𝑡 𝐡 (2) 𝑡
𝐖2
𝐠1
𝐆
...
...
...
𝐬𝑡 𝐀 𝐱𝑡 𝐔1
𝐔2 𝐔𝑑
𝐬 ̂ 𝑡
𝐆 𝐆
𝐖3 𝐖𝑑 𝐃
𝐠2 𝐠𝑑
𝐡 (𝑑) 𝑡
𝐡 (𝑑)
𝑡−1
𝐡 (1) 𝑡 𝐡 (2) 𝑡
𝐖1
𝐖2
𝐆
...
...
...
𝐬𝑡 𝐀 𝐱𝑡 𝐔1
𝐔1 𝐔1
𝐬 ̂ 𝑡
𝐆 𝐆
𝐖2 𝐖2 𝐃 𝐡 (𝑑) 𝑡
𝐡 (1)
𝑡−1
𝐡 (1) 𝑡 𝐡 (2) 𝑡
𝐕1
𝐖2 ...
...
𝐱𝑡 𝐔1 𝐖3 𝐖𝑑 𝐃
𝐡 (𝑑) 𝑡
𝐡 (𝑑) 𝑡
𝐬𝑡 𝐬 ̂ 𝑡 𝐀
𝐡 (2)
𝑡−1
𝐕2
𝐡 (𝑑)
𝑡−1
𝐕𝑑
𝐖1
𝐡0
𝐡 (1) 1 𝐡 (2)
1
𝐖2
𝐠1
𝐆
...
...
...
𝐬1 𝐀 𝐱1 𝐔1
𝐔2 𝐔𝑑
𝐆 𝐆
𝐖3 𝐖𝑑 𝐃
𝐠2 𝐠𝑑
𝐬 ̂ 1
𝐡 (𝑑)
1
𝐡 (1) 2 𝐡 (2) 2
𝐖2
𝐠1
𝐆
...
...
...
𝐱2 𝐔1
𝐔2 𝐔𝑑
𝐆 𝐆
𝐖3 𝐖𝑑
𝐠2 𝐠𝑑
𝐬2 𝐬 ̂ 2𝐡(𝑑)2
𝐡 (𝑑)
1
𝐡 (𝑑)
𝑇−1
𝐡 (1) 𝑇 𝐡 (2) 𝑇
𝐖2
𝐠1
𝐆
...
...
...
𝐱𝑇 𝐔1
𝐔2 𝐔𝑑
𝐆 𝐆
𝐖3 𝐖𝑑
𝐠2 𝐠𝑑
𝐬𝑇 𝐬 ̂ 𝑇𝐡(𝑑)𝑇
... ... ... ... . ...
𝐀
𝐀
𝐃
𝐃
𝐖1
𝐖1
𝐖1
(a) The proposed reweighted-RNN
5/14/2019 deepRNN.drawio
1/2
x1s1 A U1 W2 h1(2) g2 h1(1) U2
Wd h1(d) Ud D s1 W1 h0 G x2s2 A U1 W2 h2(2)h2(1) U2 Wd h2(d) Ud D s2 W1 G W1 G xTA U1 W2 hT(2)hT(1) U2 Wd hT(d) Ud D sT W1 G ... sT ... ... ...... ... ... . ... ... ... . ... ... ... ^ ^ ^ g1 gd g2g1 gd g2g1 gd
h (d)
t−1
h (1) t
h (2) t
W1
W2
g1
ˤ
, ,G ̌ 1 c ̌ 2 c h (d) t−1
G
...
...
...
st
A
xt
U1
U2
Ud
s ̂ t
G
G
W3
Wd
D
g2
gd
h (d) t
h (d)
t−1
h (1) t
h (2) t
W1
W2
G
...
...
...
st
A
xt
U1
U1
U1
s ̂ t
G
G
W2
W2
D
h (d) t
(b) `1-`1-RNN.
5/16/2019 deepRNN.drawio
1/2
x1s1 A U1 W2 h1(2) g2 h1(1) U2
Wd h1(d) Ud D s1 W1 h0 G x2s2 A U1 W2 h2(2)h2(1) U2 Wd h2(d) Ud D s2 W1 G W1 G xTA U1 W2 hT(2)hT(1)
U2
Wd hT( )
Ud
D sT W1 G ... sT ... ... ...... ... ... . ... ... ... . ... ... ... ^ ^ ^ g1 gd g2g1 gd
g2g1 gd
h (d)
t−1
h (1) t
h (2) t
W1
W2
g1
G
...
...
...
st
A
xt
U1
U2
Ud
s ̂ t
G
G
W3
Wd
D
g2
gd
h (d) t
h (d)
t−1
h (1) t
h (2) t
W1
W2
G
...
...
...
st
A
xt
U1
U1
U1
s ̂ t
G
G
W2
W2
D
h (d) t
h (1)
t−1
h (1) t
h (2) t
V1
W2 ...
...
xt
U1
W3
Wd
D
h (d) t
h (d) t
st
s ̂ t
A
h (2)
t−1
V2
h (d)
t−1
Vd
(c) Stacked RNN.
Figure 2: The proposed (a) reweighted-RNN vs. (b) `1-`1-RNN and (c) Stacked RNN with d layers.
Fig. 2(a) depicts the architecture of the proposed reweighted-RNN. Input vectors st, t = 1, . . . , T are compressed by a linear measurement layer A, resulting in compressive measurements xt. The reconstructed vectors ŝt, t = 1, . . . , T , are obtained by multiplying linearly the hidden representation h (d) t with the dictionary D. We train our network in an end-to-end fashion. During training, we minimize the loss function L(Θ) = E
s1,··· ,sT
[∑T t=1 ‖st − ŝt‖22 ] using stochastic gradient descent on mini-
batches, where the trainable parameters are Θ = {A,D,G,h0,Z1, . . . ,Zd, g1, . . . , gd, c, λ1, λ2}. We now compare the proposed reweighted-RNN [Fig. 2(a)] against the recent `1-`1-RNN (Le et al., 2019) [Fig. 2(b)]. The l-th hidden layer in `1-`1-RNN is given by
h (l) t =  Φλ1c ,λ2c ,Gh(d)t−1 ( W1h (d) t−1 + U1xt ) , if l = 1,
Φλ1 c , λ2 c ,Gh (d) t−1
( W2h (l−1) t + U1xt ) , if l > 1.
(13)
The proposed model has the following advantages over `1-`1-RNN. Firstly, `1-`1-RNN uses the proximal operator Φλ1
c , λ2 c ,~
(u) as activation function, whose learnable parameters λ1, λ2 are fixed
across the network. Conversely, the corresponding parameters λ1c gl and λ2 c gl [see (7), (8), and Fig. 1] in our proximal operator, Φλ1 c gl, λ2 c gl,~
(u), are learned for each hidden layer due to the reweighting vector gl; hence, the proposed model has a different activation function for each unit per layer. The second difference comes from the set of parameters {Wl,Ul} in (13) and (9). The `1-`1-RNN model uses the same {W2,U1} for the second and higher layers. In contrast, our reweighted-RNN has different sets of {Wl,Ul} per hidden layer due to the reweighting matrix Zl. These two aspects [which are schematically highlighted in blue fonts in Fig. 2(a)] can lead to an increase in the learning capability of the proposed reweighted-RNN, especially when the depth of the model increases.
In comparison to a generic stacked RNN (Pascanu et al., 2014) [Fig. 2(c)], reweighted-RNN promotes the inherent data structure, that is, each vector st has a sparse representation ht and consecutive ht’s are correlated. This design characteristic of the reweighted-RNN leads to residual connections which reduce the risk of vanishing gradients during training [the same idea has been shown in several works (He et al., 2016; Huang et al., 2017) in deep neural network literature]. Furthermore, in (10) and (12), we see a weight coupling of Wl and Ul (due to the shared components of A, D and Z). This coupling satisfies the necessary condition of the convergence in Chen et al. (2018) (Theorem 1). Using Theorem 2 in Chen et al. (2018), it can be shown that reweighted-RNN, in theory, needs a smaller number of iterations (i.e., d in Algorithm 1) to reach convergence, compared to ISTA (Daubechies et al., 2004) and FISTA (Beck & Teboulle, 2009).

heading: 3 GENERALIZATION ERROR BOUND
text: While increasing the network expressivity, the over-parameterization of reweighted-RNN raises the question of whether our network ensures good generalization. In this section, we derive and analyze the generalization properties of the proposed reweighted-RNN model in comparison to state-ofthe-art RNN architectures. We provide bounds on the Rademacher complexity (Shalev-Shwartz & Ben-David, 2014) for functional classes of the considered deep RNNs, which are used to derive generalization error bounds for evaluating their generalization properties (we refer to Appendix C.1 for definitions of the Rademacher complexity and the generalization error bound).
Preliminaries: We consider a deep RNN as a d-layer network f (d)W,U ∈ Fd,T : Rh × Rn 7→ Rh with weight parametersW = (W1, ...,Wd) and U = (U1, ...,Ud), where Wl ∈ Rh×h, Ul ∈ Rh×n. As in Bartlett et al. (2017); Golowich et al. (2018); Neyshabur et al. (2019; 2015), we derive generalization error bounds by controlling norms of the weight matrices. Let ‖Wl‖p,q = ( ∑ j(‖wl,j‖p)q)1/q define the `p,q-norm, p, q ≥ 1, of the weight-matrix Wl, where wl,j ∈ Rh is the jth row of Wl. Since we focus on deep networks with soft-thresholding-based activation units— designed by unfolding algorithms for `1-norm minimization—we derive the network complexities under bounding per-unit `1 regularization, i.e., ‖wl,j‖1. We also denote ‖Wl‖1,∞ = maxj ‖wl,j‖1 as the maximum of the `1-norms of the matrix’s rows. We assume that the `1-norm of the weights of each neuron is bounded as ‖Wl‖1,∞ = maxj ‖wl,j‖1 ≤ αl; similarly, ‖Ul‖1,∞ = maxj ‖ul,j‖1 ≤ βl, where ul,j is the jth row of the matrix Ul. As shown in (9), we can write the reweighted-RNN model recursively as h(1)t = f (1) W,U (h (d) t−1,xt) = Φ(W1h (d) t−1+U1xt) and h (l) t = f (l) W,U (h (d) t−1,xt) = Φ(Wlf (l−1) W,U (h (d) t−1,xt) + Ulxt), where Φ(·) is an activation function. For convenience, we denote the input layer as f (0)W,U = h (d) t−1; namely, at t = 1, we have h (l) 0 ≡ h0.
We denote the true and training loss by LD(f) and LS(f), respectively, where S is the training set (of size m) drawn i.i.d. from the distribution D. The generalization error is LD(f)−LS(f), with f a function from the functional class Fd,T . At time step t, we define Xt ∈ Rn×m as a matrix composed of m columns from the input vectors {xt,i}mi=1. We also define ‖Xt‖2,∞ = √ max
k∈{1,...,n}
∑m i=1 x 2 t,i,k
as the maximum of the `2-norms of the rows of matrix Xt, and ‖h0‖∞ = maxj |h0,j |. Generalization error bound. We first derive the generalization error bound for the proposed reweighted-RNN (with T time steps) based on Rademacher complexity (see Theorem 26.5 in ShalevShwartz & Ben-David (2014) and Theorem C.1 in the Appendix). Theorem 3.1 (Generalization error bound). Let Fd,T : Rh × Rn 7→ Rh denote the functional class of reweighted-RNN with T time steps and d layers, where ‖Wl‖1,∞ ≤ αl, ‖Ul‖1,∞ ≤ βl, and 1 ≤ l ≤ d. Assume that the input data ‖Xt‖2,∞ ≤ √ mBx, the initial hidden state is h0, and the loss function is 1-Lipschitz and bounded by η. Then, for f ∈ Fd,T and any δ > 0, with probability at least 1− δ over a training set S of size m drawn i.i.d. from the distribution D,
LD(f)− LS(f) ≤ 2RS(Fd,T ) + 4η √ 2 log(4/δ)
m , (14)
where RS(Fd,T ) ≤ √ 2(4dT log 2 + log n+ log h)
m · √√√√( d∑ l=1 βlΛl )2(ΛT0 − 1 Λ0 − 1 )2 B2x + Λ 2T 0 ‖h0‖2∞, (15)
with Λl defined as follows: Λl = d∏
k=l+1
αk with 0 ≤ l ≤ d− 1 and Λd = 1.
Proof. The proof is given in Appendix D.
The generalization error in (14) is bounded by the Rademacher complexity, which depends on the training set S. If the Rademacher complexity is small, the network can be learned with a small generalization error. The bound in (15) is in the order of the square root of the network depth d multiplied by the number of time steps T . The bound depends on the logarithm of the number of measurements n and the number of hidden units h. It is worth mentioning that the second square root in (15) only depends on the norm constraints and the input training data, and it is independent of the network depth d and the number of time steps T under the appropriate norm constraints.
To compare our model with `1-`1-RNN (Le et al., 2019) and Sista-RNN (Wisdom et al., 2017), we derive bounds on their Rademacher complexities for a time step t. The definitions of a functional class Fd,t for the tth time step of reweighted-RNN, `1-`1-RNN, and Sista-RNN are given in Appendix C.2. Let Ht−1 ∈ Rh×m denote a matrix with columns the vectors of the previous hidden state {ht−1,i}mi=1, and ‖Ht−1‖2,∞ = √ max
k∈{1,...,h}
∑m i=1 h 2 t−1,i,k ≤ √ mBht−1 .
Corollary 3.1.1. The empirical Rademacher complexity of Fd,t for reweighted-RNN is bounded as
RS(Fd,t) ≤ √ 2(4d log 2 + log n+ log h)
m · √√√√( d∑ l=1 βlΛl )2 B2x + Λ 2 0B 2 ht−1 , (16)
with m the number of training samples and Λl given by Λd = 1, Λl = d∏
k=l+1
αk with 0 ≤ l ≤ d− 1.
Proof. The proof is a special case of Theorem 3.1 for time step t.
Following the proof of Theorem 3.1, we can obtain the Rademacher complexities for `1-`1-RNN and Sista-RNN: Corollary 3.1.2. The empirical Rademacher complexity of Fd,t for `1-`1-RNN is bounded as:
RS(Fd,t) ≤ √ 2(4d log 2 + log n+ log h)
m ·
√ β21 (αd2 − 1 α2 − 1 )2 B2x + α 2 1α 2(d−1) 2 B 2 ht−1 . (17)
Corollary 3.1.3. The empirical Rademacher complexity of Fd,t for Sista-RNN is bounded as: RS(Fd,t)
≤ √ 2(4d log 2 + log n+ log h)
m · √√√√β21(αd2 − 1α2 − 1 )2 B2x + ( α1α (d−1) 2 + β2 (αd−12 − 1 α2 − 1 ))2 B2ht−1 .
(18)
By contrasting (16) with (17) and (18), we see that the complexities of `1-`1-RNN and Sista-RNN have a polynomial dependence on α1, β1 and α2, β2 (the norms of first two layers), whereas the complexity of reweighted-RNN has a polynomial dependence on α1, . . . , αd and β1, . . . , βd (the norms of all layers). This over-parameterization offers a flexible way to control the generalization error of reweighted-RNN. We derive empirical generalization errors in Fig. 6 in Appendix A demonstrating that increasing the depth of reweighted-RNN still ensures the low generalization error.

heading: 4 EXPERIMENTAL RESULTS
text: We assess the proposed RNN model in the task of video-frame reconstruction from compressive measurements. The performance is measured using the peak signal-to-noise ratio (PSNR) between the reconstructed ŝt and the original frame st. We use the moving MNIST dataset (Srivastava et al., 2015), which contains 10K video sequences of equal length (20 frames per sequence). Similar to the setup in Le et al. (2019), the dataset is split into training, validation, and test sets of 8K, 1K, and 1K sequences, respectively. In order to reduce the training time and memory requirements, we downscale the frames from 64× 64 to 16× 16 pixels using bilinear decimation. After vectorizing, we obtain sequences of s1, . . . , sT ∈ R256. Per sequence, we obtain measurements x1, . . . ,xT ∈ Rn using a trainable linear sensing matrix A ∈ Rn×n0 , with T = 20, n0 = 256 and n < n0. We compare the reconstruction performance of the proposed reweighted-RNN model against deepunfolding RNN models, namely, `1-`1-RNN (Le et al., 2019), Sista-RNN (Wisdom et al., 2017), and stacked-RNN models, that is, sRNN (Elman, 1990), LSTM (Hochreiter & Schmidhuber, 1997), GRU (Cho et al., 2014), FastRNN (Kusupati et al., 2018)1, IndRNN (Li et al., 2018) and SpectralRNN (Zhang et al., 2018). For the vanilla RNN, LSTM and GRU, the native Pytorch cell implementations were used. The unfolding-based methods were implemented in Pytorch2, with Sista-RNN and `1-`1-RNN tested by reproducing the experiments in Wisdom et al. (2017); Le et al. (2019). For FastRNN, IndRNN, and SpectralRNN cells, we use the publically available Tensorflow implementations. While Sista-RNN, `1-`1-RNN and reweighted-RNN have their own layer-stacking schemes derived from unfolding minimization algorithms, we use the stacking rule in Pascanu et al. (2013) [see Fig 2(c)] to build deep networks for other RNN architectures.
1Kusupati et al. (2018) also proposed FastGRNN; we found that, in our application scenario, the non-gated variant (the FastRNN) consistently outperformed FastGRNN. As such, we do not include results with the latter.
2Our implementations are available at https://1drv.ms/u/s!ApHn770BvhH2aWay9xEhAiXydfo?e=aCX1X0.
Our default settings are: a compressed sensing (CS) rate of n/n0 = 0.2, d = 3 hidden layers3 with h = 210 hidden units per layer. In each set of experiments, we vary each of these hyperparameters while keeping the other two fixed. For the unfolding methods, the overcomplete dictionary D ∈ Rn0×h is initialized with the discrete cosine transform (DCT) with varying dictionary sizes of h = {27, 28, 29, 210, 211, 212} (corresponding to a number of hidden neurons in the other methods). For initializing λ1, λ2 [see (2), (4)], we perform a random search in the range of [10−5, 3.0] in the validation set. To avoid the problem of exploding gradients, we clip the gradients during backpropagation such that the `2-norms are less than or equal to 0.25. We do not apply weight decay regularization as we found it often leads to worse performance, especially since gradient clipping is already used for training stability. We train the networks for 200 epochs using the Adam optimizer with an initial learning rate of 0.0003, and a batch size of 32. During training, if the validation loss does not decrease for 5 epochs, we reduce the learning rate to 0.3 of its current value.
Table 1 summarizes the reconstruction results for different CS rates n/n0. The reweighted-RNN model systematically outperforms the other models, often by a large margin. Table 2 shows similar improvements for various dimensions of hidden units. Table 3 shows that IndRNN delivers higher reconstruction performance than our model when a small number of hidden layers (d = 1, 2) is used. Moreover, when the depth increases, reweighted-RNN surpasses all other models. Our network also has fewer trainable parameters compared to the popular variants of RNN. At the default settings, reweighted-RNN, the stacked vanilla RNN, the stacked LSTM, and the stacked GRU have 4.47M, 5.58M, 21.48M, and 16.18M parameters, respectively.

heading: 5 CONCLUSIONS
text: We designed a novel deep RNN by unfolding an algorithm that solves a reweighted `1-`1 minimization problem. Our model has high network expressivity due to per-unit learnable activation functions and over-parameterized weights. We also established the generalization error bound for the proposed model via Rademacher complexity. We showed that reweighted-RNN has good generalization properties and its error bound is tighter than existing RNNs in function of the number of time steps. Experimentation on the task of sequential video-frame reconstruction shows that our model (i) outperforms various state-of-the-art RNNs in terms of accuracy and (ii) is capable of stacking many hidden layers resulting in a better learning capability than the existing unfolding methods.
3In our experiments, the 2-layer LSTM network outperforms the 3-layer one (see Table 3), the default setting for LSTM is thus using 2 layers.

heading: A SUPPLEMENTARY EXPERIMENTS
text: In our experiments, we use the publically available Tensorflow implementations for FastRNN4, IndRNN5, and SpectralRNN6 cells. While Sista-RNN, `1-`1-RNN and reweighted-RNN have their own layer-stacking schemes derived from unfolding minimization algorithms, we use the stacking rule in Pascanu et al. (2013) [see Fig 2(c)] to build deep networks for other RNN models.
Figure 3 shows the learning curves of all methods under the default setting. It can be seen that reweighted-RNN achieves the lowest mean square error on both the training and validation sets. It can also be observed that the unfolding methods converge faster than the stacked RNNs, with the proposed reweighted-RNN being the fastest. More experimental results for the proposed reweighted-RNN are provided to illustrate the learning curves, which measure the average mean square error vs. the training epochs between the original frames and their reconstructed counterparts, with different CS rates [Fig. 4], different network depths d [Fig. 6], and different network widths h [Fig. 5].
Since we use different frameworks to implement the RNNs used in our benchmarks, we do not report and compare the computational time for training of the models. Specifically, we rely on the Tensorflow implementations from the authors of Independent-RNN, Fast-RNN and Spectral RNN, while the rest is written in Pytorch. Furthermore, even among Pytorch models, the vanilla RNN, LSTM, and GRU cells are written in CuDNN (default Pytorch implementations), so that they are significantly faster in training than the others. This does not mean that these networks have better runtime complexities, but rather more efficient implementations. However, an important comparison could be made between `1-`1-RNN Le et al. (2019) (as the baseline method) and Reweighted-RNN due to their similarities in implementations. At the default settings, it takes 3,521 seconds and 2,985 seconds to train Reweighted-RNN and `1-`1-RNN Le et al. (2019), respectively.
4Code available at https://github.com/microsoft/EdgeML 5Code available at https://github.com/batzner/indrnn 6Code available at https://github.com/zhangjiong724/spectral-RNN

heading: B THE PROXIMAL OPERATOR FOR PROBLEM (4)
text: Proposition B.1. The proximal operator Φλ1 c g, λ2 c g,~ (u) in (6) for the reweighted `1-`1 minimization problem (4), for which g(v) = λ1g|v|+ λ2g|v − ~|, is given by
Φλ1 c g, λ2 c g,~≥0 (u) =  u− λ1c g − λ2 c g, ~ + λ1 c g + λ2 c g < u <∞ ~, ~ + λ1c g − λ2 c g ≤ u ≤ ~ + λ1 c g + λ2 c g u− λ1c g + λ2 c g, λ1 c g − λ2 c g < u < ~ + λ1 c g − λ2 c g 0, −λ1c g − λ2 c g ≤ u ≤ λ1 c g − λ2 c g
u+ λ1c g + λ2 c g, −∞ < u < − λ1 c g − λ2 c g
(19)
Φλ1 c g, λ2 c g,~<0 (u) =  u− λ1c g − λ2 c g, λ1 c g + λ2 c g < u <∞ 0, −λ1c g + λ2 c g ≤ u ≤ λ1 c g + λ2 c g u+ λ1c g − λ2 c g, ~− λ1 c g + λ2 c g < u < − λ1 c g + λ2 c g ~, ~− λ1c g − λ2 c g ≤ u ≤ ~− λ1 c g + λ2 c g
u− λ1c g + λ2 c g, −∞ < u < ~− λ1 c g − λ2 c g
(20)
Proof. We compute the proximal operator Φλ1 c g, λ2 c g,~ (u) (19) for ~ ≥ 0, it is similar for ~ < 0. From (6), Φλ1
c g, λ2 c g,~
(u) is expressed by:
Φλ1 c g, λ2 c g,~ (u) = arg min v∈R
{ ϕ(v) :=
λ1 c g|v|+ λ2 c g|v − ~|+ 1 2 |v − u|2
} . (21)
We first consider the ∂ϕ(v)/∂v in v ∈ {(−∞, 0), (0, ~), (~,∞)}, in which ∂ϕ(v) exists. Taking the derivative of ϕ(v) in these intervals delivers
∂ϕ(v) ∂v = λ1 c g · sign(v) + λ2 c g · sign(v − ~) + (v − u), (22)
where sign(.) is a sign function. When setting ∂ϕ(v)/∂v = 0 to minimize ϕ(v), we derive:
v =  u− λ1c g − λ2 c g, ~ < v <∞ u− λ1c g + λ2 c g, 0 < v < ~
u+ λ1c g + λ2 c g, −∞ < v < 0
(23)
From (21) and (23), we have
Φλ1 c g, λ2 c g,~ (u) =  u− λ1c g − λ2 c g, ~ + λ1 c g + λ2 c g < u <∞ u− λ1c g + λ2 c g, λ1 c g − λ2 c g < u < ~ + λ1 c g − λ2 c g
u+ λ1c g + λ2 c g, −∞ < u < − λ1 c g − λ2 c g
(24)
In the remaining range value of u, namely, −λ1c g − λ2 c g ≤ u ≤ λ1 c g − λ2 c g and ~ + λ1 c g − λ2 c g ≤ u ≤ ~ + λ1c g + λ2 c g, we prove that the minimum of ϕ(v) (21) is obtained when v = 0 and v = ~, respectively.
Let us rewrite ϕ(v), which was defined in (21), as
ϕ(v) = λ1 c g|v|+ λ2 c g|v − ~|+ 1 2 |v − u|2 (25)
By applying the inequality |a− b| ≥ |a| − |b|, where a, b ∈ R, to (25), we obtain:
ϕ(v) ≥ λ1 c g|v|+ λ2 c g|v| − λ2 c g|~|+ 1 2 v2 − vu+ 1 2 u2
≥ |v| (λ1 c g + λ2 c g − |u| ) + 1 2 v2 − λ2 c g|~|+ 1 2 u2 (26)
For−λ1c g− λ2 c g ≤ u ≤ λ1 c g− λ2 c g, from (26), ϕ(v) is minimal when v = 0, due to λ1 c g+ λ2 c g−|u| ≥ 0.
Similarly, for ~+ λ1c g− λ2 c g ≤ u ≤ ~+ λ1 c g+ λ2 c g, i.e., λ1 c g− λ2 c g ≤ u−~ ≤ λ1 c g+ λ2 c g, we have
ϕ(v) ≥λ1 c g|v − ~| − λ1 c g|~|+ λ2 c g|v − ~|+ 1 2 (v − ~)2 − |v − ~||u− ~|+ 1 2 (u− ~)2
≥|v − ~| (λ1 c g + λ2 c g − |u− ~| ) + 1 2 (v − ~)2 − λ1 c g|~|+ 1 2 (u− ~)2. (27)
From (27), ϕ(v) is minimal when v = ~, since λ1c g + λ2 c g − |u− ~| ≥ 0. Combining these results with the result in (24), we conclude the proof.

heading: C GENERALIZATION AND DEEP UNFOLDING RNNS
text: C.1 GENERALIZATION ERROR BOUND DEFINITION
Notations. Let f (d)W : Rn 7→ Rh be the function computed by a d-layer network with weight parametersW . The network f (d)W maps an input sample xi ∈ Rn (from an input space X ) to an output yi ∈ Rh (from an output space Y), i.e., yi = f (d) W (xi). Let S denote a training set of size m, i.e., S = {(xi,yi)}mi=1 and E(xi,yi)∼S [·] denote an expectation over (xi,yi) from S. The set S is drawn i.i.d. from a distribution D, denoted as S ∼ Dm, over a space Z = X × Y . Let F be a (class) set of functions. Let ` : F × Z 7→ R denote the loss function and ` ◦ F = {z 7→ `(f, z) : f ∈ F}. We define the true loss and the empirical (training) loss by LD(f) and LS(f), respectively, as follows:
LD(f) = E(xi,yi)∼D [ ` ( f(xi),yi )] , (28)
and LS(f) = E(xi,yi)∼S [ ` ( f(xi),yi )] . (29) The generalization error, which is defined as a measure of how accurately a learned algorithm is able to predict outcome values for unseen data, is calculated by LD(f)− LS(f). Rademacher complexity. Let F be a hypothesis set of functions (neural networks). The empirical Rademacher complexity of F (Shalev-Shwartz & Ben-David, 2014) for a training sample set S is defined as follows:
RS(F) = 1
m E ∈{±1}m [ sup f∈F m∑ i=1 if(xi) ] , (30)
where = ( 1, ..., m); here i are independent uniformly distributed random (Rademacher) variables from {±1}, according to P[ i = 1] = P[ i = −1] = 1/2. The generalization error bound (Shalev-Shwartz & Ben-David, 2014) is derived based on the Rademacher complexity defined in the following theorem: Theorem C.1. (Shalev-Shwartz & Ben-David, 2014, Theorem 26.5) Assume that |`(f, z)| ≤ η for all f ∈ F and z. Then, for any δ > 0, with probability at least 1− δ,
LD(f)− LS(f) ≤ 2RS(` ◦ F) + 4η √ 2 log(4/δ)
m . (31)
It can be noted that the bound in (31) via the Rademacher complexity depends on the training set S, which makes it applicable to a number of learning problems, e.g., regression and classification, under given a loss function `.
C.2 NOTATION FOR DEEP UNFOLDED RNNS
In this subsection, we provide the required notation for the proposed reweighted-RNN model, `1- `1-RNN, and Sista-RNN, which will be used in the derivation of their respective generalization analysis.
The proposed reweighted-RNN. Let h(l)t be the hidden states in layer l evolving in time step t. We write the reweighted-RNN model recursively as h(1)t = f (1) W,U (h (d) t−1,xt) = Φ(W1h (d) t−1+U1xt) and h (l) t = f (l) W,U (h (d) t−1,xt) = Φ ( Wlf (l−1) W,U (h (d) t−1,xt) +Ulxt ) , where Φ is an activation function. The
hidden state is updated as shown in (9). The real-valued family of functions, Fd,t : Rh × Rn 7→ R, for the functions f (d)W,U in layer d is defined by:
Fd,t = { (h (d) t−1,xt) 7→ Φ(wTd f (d−1) W,U (h (d) t−1,xt) + u T d xt) : ‖Wd‖1,∞ ≤ αd, ‖Ud‖1,∞ ≤ βd } ,
(32)
where αl, βl are nonnegative hyper-parameters for layer l, where 1 < l ≤ d. In layer l = 1, the real-valued family of functions, F1,t : Rh × Rn 7→ R, for the functions f (1)W,U is defined by:
F1,t = { (h (d) t−1,xt) 7→ Φ(wT1 h (d) t−1 + u T 1 xt) : ‖W1‖1,∞ ≤ α1, ‖U‖1,∞ ≤ β1 } , (33)
where α1, β1 are nonnegative hyper-parameters. We denote the input layer as f (0) W,U = h (d) t−1, in particular, at t = 1, h(l)0 ≡ h0.
The `1-`1-RNN model (Le et al., 2019). The hidden state h (l) t for `1-`1-RNN is updated as shown in (13). The real-valued family of functions, Fd,t : Rh × Rn 7→ R, for the function f (d)W,U in layer d is defined by:
Fd,t = { (h (d) t−1,xt) 7→ Φ(wT2 f (d−1) W,U (h (d) t−1,xt) + u T 1 xt) : ‖W2‖1,∞ ≤ α2, ‖U1‖1,∞ ≤ β1 } ,
(34)
where α2, β1 are nonnegative hyper-parameters for layer l, where 1 < l ≤ d. In layer l = 1, the real-valued family of functions, F1,t : Rh × Rn 7→ R, for the functions f (1)W,U is defined by:
F1,t = { (h (d) t−1,xt) 7→ Φ(wT1 h (d) t−1 + u T 1 xt) : ‖W1‖1,∞ ≤ α1, ‖U‖1,∞ ≤ β1 } , (35)
where α1, β1 are nonnegative hyper-parameters.
The Sista-RNN model (Wisdom et al., 2017). The hidden state h(l)t in Sista-RNN is updated by:
h (l) t =  φ ( W1h (d) t−1 + U1xt ) , l = 1, φ ( W2h (l−1) t + U1xt + U2h (d) t−1 ) , l > 1,
(36)
The real-valued family of functions, Fd,t : Rh × Rn 7→ R, for the functions f (d)W,U in layer d is defined by:
Fd,t = { (h (d) t−1,xt) 7→ φ ( wT2 f (d−1) W,U (h (d) t−1,xt) + u T 1 xt + u T 2 h (d) t−1 ) : ‖W2‖1,∞ ≤ α2, ‖U‖1,∞ ≤ β1, ‖U‖2,∞ ≤ β2 } , (37)
where α2, β1, β2 are nonnegative hyper-parameters. In layer l = 1, F1,t = { (h (d) t−1,xt) 7→ φ ( wT1 h (d) t−1 + u T 1 xt ) : ‖W1‖1,∞ ≤ α1, ‖U‖1,∞ ≤ β1 } , (38)
where α1, β1 are nonnegative hyper-parameters.

heading: D PROOF OF THEOREM 3.1
text: Proof. We consider the real-valued family of functions Fd,T : Rh×Rn 7→ R for the functions f (d)W,U to update h(d)T in layer d, time step T , defined as
Fd,T = { (h (d) T−1,xT ) 7→ Φ(w T d f (d−1) W,U (h (d) T−1,xT ) + u T d xT ) : ‖Wd‖1,∞ ≤ αd, ‖Ud‖1,∞ ≤ βd } ,
(39)
where wd,ud are the corresponding rows from Wd,Ud, respectively, and αl, βl, with 1 < l ≤ d, are nonnegative hyper-parameters. For the first layer and the first time step, i.e., l = 1, t = 1, the real-valued family of functions, F1,1 : Rh × Rn 7→ R, for the functions f (1)W,U is defined by:
F1,1 = { (h0,x1) 7→ Φ(wT1 h0 + uT1 x1) : ‖W1‖1,∞ ≤ α1, ‖U‖1,∞ ≤ β1 } , (40)
where α1, β1 are nonnegative hyper-parameters. We denote the input layer as f (0) W,U = h0 at the first time step. From the definition of Rademacher complexity in (30) and the family of functions in (39) and (40), we obtain:
mRS(Fd,T ) (41a)
≤ E ∈{±1}m [ sup W,U
‖wd‖1≤αd ‖ud‖1≤βd
m∑ i=1 iΦ ( wTd f (d−1) W,U (hT−1,i,xT,i) + u T d xT,i
)]
≤ 1 λ log exp
( E
∈{±1}m [ sup W,U
‖wd‖1≤αd ‖ud‖1≤βd
λ m∑ i=1 i ( wTd f (d−1) W,U (hT−1,i,xT,i) + u T d xT,i
)])
≤ 1 λ log E ∈{±1}m [ sup W,U
‖wd‖1≤αd ‖ud‖1≤βd
exp ( λ
m∑ i=1 i ( wTd f (d−1) W,U (hT−1,i,xT,i) ) + λ m∑ i=1 iu T d xT,i
)]
(41b)
≤ 1 λ log E ∈{±1}m [ sup W,U
‖wd‖1≤αd
exp ( λ
m∑ i=1 i ( wTd f (d−1) W,U (hT−1,i,xT,i)
))
· sup ‖ud‖1≤βd exp
( λ
m∑ i=1 iu T d xT,i
)] , (41c)
where λ > 0 is an arbitrary parameter, Eq. (41b) follows Lemma D.1 for 1-Lipschitz Φ a long with Inequality (62), and (41c) holds by Inequality (59).
For layer 1 ≤ l ≤ d and time step t, let us denote:
∆ (l) ht−1,xt
= sup W,U
‖wl‖1≤αl
exp ( λΛl
m∑ i=1 i ( wTl f (l−1) W,U (ht−1,i,xt,i) )) , (42)
∆(l)xt = sup ‖ul‖1≤βl exp
( λΛl
m∑ i=1 i ( uTl xt,i )) , (43)
where Λl is defined as follows: Λd = 1, Λl = d∏
k=l+1 αk with 1 ≤ l ≤ d− 1, and Λ0 = d∏ k=1 αk.
Following the Hölder’s inequality in (58) in case of p = 1 and q = ∞ applied to wTl and f (l−1) W,U (ht−1,i,xt,i) in (42), respectively, we get:
∆ (d) ht−1,xt
(44)
≤ sup W,U
‖Wd−1‖1,∞≤αd−1 ‖Ud−1‖1,∞≤βd−1
exp ( λαd ∥∥∥∥∥ m∑ i=1 iΦ ( Wd−1f (d−2) W,U (ht−1,i,xt,i) + Ud−1xt,i )∥∥∥∥∥ ∞ )
≤ sup W,U
‖wd−1,k‖1≤αd−1 ‖ud−1,k‖1≤βd−1
exp ( λαd max
k∈{1,··· ,h} ∣∣∣∣∣ m∑ i=1 iΦ ( wTd−1,kf (d−2) W,U (ht−1,i,xt,i) + u T d−1,kxt,i )∣∣∣∣∣ )
≤ sup W,U
‖wd−1,k‖1≤αd−1 ‖ud−1,k‖1≤βd−1
exp ( λαd ∣∣∣∣∣ m∑ i=1 iΦ ( wTd−1,kf (d−2) W,U (ht−1,i,xt,i) + u T d−1,kxt,i )∣∣∣∣∣ ) . (45)
Similarly, from (43), we obtain:
∆(d)xt ≤ sup ‖ud‖1≤βd exp
( λ
m∑ i=1 iu T d xt,i
) ≤ exp ( λβd ∥∥∥ m∑ i=1 ixt,i ∥∥∥ ∞ ) ≤ exp ( λβd ∣∣∣ m∑ i=1 ixτ,i,κ ∣∣∣), (46)
where {τ, κ} = argmax t∈{1,...,T},j∈{1,...,n} ∣∣∣ m∑ i=1 ixt,i,j ∣∣∣. From (41c), (44), and (46), we get:
mRS(Fd,T )
≤ 1 λ log
( E
∈{±1}m [ sup W,U
‖wd−1,k‖1≤αd−1 ‖ud−1,k‖1≤βd−1
exp ( λαd ∣∣∣∣∣ m∑ i=1 iΦ ( wTd−1,kf (d−2) W,U (hT−1,i,xT,i) + u T d−1,kxT,i )∣∣∣∣∣ + λβd
∣∣∣ m∑ i=1 ixτ,i,κ ∣∣∣)])
≤ 1 λ log
( E
∈{±1}m [ sup W,U
‖wd−1,k‖1≤αd−1 ‖ud−1,k‖1≤βd−1
(
exp ( λαd
m∑ i=1 iΦ ( wTd−1,kf (d−2) W,U (hT−1,i,xT,i) + u T d−1,kxT,i ) + λβd m∑ i=1 ixτ,i,κ
)
+ exp ( λαd
m∑ i=1 iΦ ( wTd−1,kf (d−2) W,U (hT−1,i,xT,i) + u T d−1,kxT,i ) − λβd m∑ i=1 ixτ,i,κ
)
+ exp ( − λαd
m∑ i=1 iΦ ( wTd−1,kf (d−2) W,U (hT−1,i,xT,i) + u T d−1,kxT,i ) + λβd m∑ i=1 ixτ,i,κ
)
+ exp ( − λαd
m∑ i=1 iΦ ( wTd−1,kf (d−2) W,U (hT−1,i,xT,i) + u T d−1,kxT,i ) − λβd m∑ i=1 ixτ,i,κ
))])
≤ 1 λ log ( 4 E ∈{±1}m [ ∆ (d−1) hT−1,xT ∆(d−1)xT exp ( βdλ m∑ i=1 ixτ,i,κ )]) (47a)
≤ 1 λ log
( 4d−1 E
∈{±1}m
[ ∆
(1) hT−1,xT ∆(1)xT exp ( λ ( d∑ l=2 βlΛl ) m∑ i=1 ixτ,i,κ )]) (47b)
≤ 1 λ log
( 4d−1 E
∈{±1}m
[ exp ( λ ( d∑ l=2 βlΛl ) m∑ i=1 ixτ,i,κ ) sup ‖w1‖1≤α1 exp ( λΛ1 m∑ i=1 i ( wT1 hT−1,i ))
· sup ‖u1‖1≤β1 exp
( λΛ1
m∑ i=1 i ( uT1 xT,i ))]) (47c)
≤ 1 λ log
( 4d−1 E
∈{±1}m
[ exp ( λ ( d∑ l=2 βlΛl ) m∑ i=1 ixτ,i,κ ) sup W,U
‖wd‖1≤αd ‖ud‖1≤βd
exp ( λΛ0 ∥∥∥ m∑ i=1 ihT−1,i ∥∥∥ ∞ )
· exp ( λβ1Λ1 ∥∥∥ m∑ i=1 ixT,i ∥∥∥ ∞ ))]) (47d)
≤ 1 λ log
( 4d E
∈{±1}m
[ exp ( λ ( d∑ l=1 βlΛl ) m∑ i=1 ixτ,i,κ )
· sup W,U
‖wd‖1≤αd ‖ud‖1≤βd
exp ( λΛ0
m∑ i=1 iΦ ( wTd f (d−1) W,U (hT−2,i,xT−1,i) + u T d xT−1,i ))]) , (47e)
where (47a) holds by inequality (59), and (47b) follows by repeating the process from layer d− 1 to layer 1 for time step T . Furthermore, (47c) is obtained as the beginning of the process for time step T − 1 and (47d) follows inequality (58). Proceeding by repeating the above procedure in (47e) from time step T − 1 to time step 1, we get: mRS(Fd,T )
≤ 1 λ log
( 4dT E
∈{±1}m
[ exp ( λ ( d∑ l=1 βlΛl )(ΛT0 − 1 Λ0 − 1 ) m∑ i=1 ixτ,i,κ ) exp ( λΛT0 ∥∥∥ m∑ i=1 ih0 ∥∥∥ ∞ ]) .
(48)
Let us denote µ = argmax j∈{1,...,h} ∣∣∣ m∑ i=1 ih0,j ∣∣∣, from (48), we have: mRS(Fd,T )
≤ 1 λ log
( 4dT E
∈{±1}m
[ exp ( λ ( d∑ l=1 βlΛl )(ΛT0 − 1 Λ0 − 1 ) m∑ i=1 ixτ,i,κ ) exp ( λΛT0 m∑ i=1 ih0,µ )])
≤ 2dT log 2 λ + 1 2λ log
( E
∈{±1}m
[ exp ( λ ( d∑ l=1 βlΛl )(ΛT0 − 1 Λ0 − 1 ) m∑ i=1 ixτ,i,κ )
· exp ( λΛT0 m∑ i=1 ih0,µ )])2
≤ 2dT log 2 λ + 1 2λ log E ∈{±1}m
[ exp ( 2λ ( d∑ l=1 βlΛl )(ΛT0 − 1 Λ0 − 1 ) m∑ i=1 ixτ,i,κ )]
+ 1
2λ log E ∈{±1}m
[ exp ( 2λΛT0 m∑ i=1 ih0,µ )] (49a)
≤ 2dT log 2 λ + 1 2λ log n∑ j=1 E ∈{±1}m
[ exp ( 2λ ( d∑ l=1 βlΛl )(ΛT0 − 1 Λ0 − 1 ) m∑ i=1 ixτ,i,j )]
+ 1
2λ log h∑ j=1 E ∈{±1}m
[ exp ( 2λΛT0 m∑ i=1 ih0,j )] (49b)
≤ 2dT log 2 λ + 1 2λ log n∑ j=1 m∏ i=1 E ∈{±1}m
[ exp ( 2λ ( d∑ l=1 βlΛl )(ΛT0 − 1 Λ0 − 1 ) ixτ,i,j )]
+ 1
2λ log h∑ j=1 m∏ i=1 E ∈{±1}m
[ exp ( 2λΛT0 ih0,j )]
≤ 2dT log 2 λ + 1 2λ log n∑ j=1 m∏ i=1
[ 1
2 exp ( 2λ ( d∑ l=1 βlΛl )(ΛT0 − 1 Λ0 − 1 ) xτ,i,j )
+ 1
2 exp
( − 2λ ( d∑ l=1 βlΛl )(ΛT0 − 1 Λ0 − 1 ) xτ,i,j )]
+ 1
2λ log h∑ j=1 m∏ i=1
[ 1
2 exp
( 2λΛT0 h0,j ) + 1
2 exp
( − 2λΛT0 h0,j )]
≤ 2dT log 2 λ + 1 2λ log n∑ j=1
[ exp ( 2λ2 ( d∑ l=1 βlΛl )2(ΛT0 − 1 Λ0 − 1 )2 m∑ i=1 x2τ,i,j )]
+ 1
2λ log h∑ j=1
[ exp ( 2λ2Λ2T0 m∑ i=1 h20,j )] (49c)
≤ 2dT log 2 λ + log n 2λ + λ ( d∑ l=1 βlΛl )2(ΛT0 − 1 Λ0 − 1 )2 mB2x + log h 2λ + λΛ2T0 m‖h0‖2∞ ≤ 2dT log 2 + log √ n+ log √ h
λ + λ (( d∑ l=1 βlΛl )2(ΛT0 − 1 Λ0 − 1 )2 mB2x + Λ 2T 0 m‖h0‖2∞ ) , (49d)
where (49a) follows inequality (61), and (49b) holds by replacing with ∑n j=1 and ∑h j=1, respectively. In addition, (49c) follows (60), and (49d) is obtained by the following definition: At time step t, we define Xt ∈ Rn×m, a matrix composed of m columns from the m input vectors {xt,i}mi=1; we also define ‖Xt‖2,∞ = √ max
k∈{1,...,n}
∑m i=1 x 2 t,i,k ≤ √ mBx, representing the maximum of the `2-norms
of the rows of matrix Xt, and ‖h0‖∞ = max j |h0,j |.
Choosing λ = √√√√ 2dT log 2+log√n+log√h( d∑
l=1
βlΛl )2( ΛT0 −1 Λ0−1 )2 mB2x+Λ 2T 0 m‖h0‖2∞ , we achieve the upper bound:
RS(Fd,T ) ≤ √√√√2(4dT log 2 + log n+ log h) m (( d∑ l=1 βlΛl )2(ΛT0 − 1 Λ0 − 1 )2 B2x + Λ 2T 0 ‖h0‖2∞ ) .
(50)
It can be noted that RS(Fd,T ) in (50) is derived for the real-valued functions Fd,T . For the vectorvalued functions Fd,T : Rh × Rn 7→ Rh (in Theorem 3.1), we apply the contraction lemma (Lemma D.1) to a Lipschitz loss to obtain the complexity of such vector-valued functions by means of the complexity of the real-valued functions. Specifically, in Theorem 3.1, under the assumption of the 1-Lipschitz loss function and from Theorem C.1, Lemma D.1, we complete the proof.
D.1 COMPARISON WITH EXISTING GENERALIZATION BOUNDS
Recent works have established generalization bounds for RNN models with a single recurrent layer (d = 1) using Rademacher complexity [see FastRNN in Kusupati et al. (2018)] or PAC-Bayes theory [see SpectralRNN in Zhang et al. (2018)]. We re-state these generalization bounds below and apply Theorem 3.1 with d = 1 to compare with our bound for reweighted-RNN.
FastRNN (Kusupati et al., 2018). The hidden state ht of FastRNN is updated as follows:
h̃t = φ(Wht−1 + Uxt)
ht = ah̃t + bht−1, (51)
where 0 ≤ a, b ≤ 1 are trainable parameters parameterized by the sigmoid function. Under the assumption that a + b = 1, the Rademacher complexity RS(FT ) of the class FT of FastRNN (Kusupati et al., 2018), with ‖W‖F ≤ αF , ‖U‖F ≤ βF , and ‖xt‖2 ≤ B, is given by
RS(FT ) ≤ 2a√ m BβF ( (1 + a(2αF − 1))T+1 − 1 a(2αF − 1) ) . (52)
Alternatively, under the additional assumption that a ≤ 12(2αF−1)T , the bound in Kusupati et al. (2018) becomes:
RS(FT ) ≤ 2a√ m BβF (2a(2αF − 1)(T + 1)− 1 (2αF − 1) ) . (53)
SpectralRNN (Zhang et al., 2018). The hidden state ht and output yt ∈ Rny of SpectralRNN are computed as:
ht =φ(Wht−1 + Uxt)
yt =Yht, (54)
where Y ∈ Rny×h. The generalization error in Zhang et al. (2018) is derived for a classification problem. For any δ > 0, γ > 0, with probability ≥ 1 − δ over a training set S of size m, the generalization error (Zhang et al., 2018) of SpectralRNN is bounded by
O
(√ B2T 4ξ ln(ξ)
γ2 (‖W‖ 2 F + ‖U‖2F + ‖Y‖2F ) · ζ + ln m δ
m
) , (55)
where ζ = max{‖W‖2T−22 , 1}max{‖U‖22, 1}max{‖Y‖22, 1} and ξ = max{n, ny, h}. Reweighted-RNN. Based on Theorem 3.1, under the assumption that the initial hidden state h0 = 0, the Rademacher complexity of reweighted-RNN with d = 1 is bounded as
RS(F1,T ) ≤ √ 4T log 2 + log n+ log h
m
(√ 2β1
αT1 − 1 α1 − 1 Bx
) . (56)
We observe that the bound of SpectralRNN in (55) depends on T 2, whereas the bound of FastRNN either grows exponentially with T (52) or is proportional to T (53). Our bound (56) depends on√ T , given that the second factor in (56) is only dependent on the norm constraints α1, β1 and the input training data; meaning that it is tighter than those of SpectralRNN and FastRNN in terms of the number of time steps.
D.2 BACKGROUND ON RADEMACHER COMPLEXITY CALCULUS
The contraction lemma in Shalev-Shwartz & Ben-David (2014) gives the Rademacher complexity of the composition of a class of functions with ρ-Lipschitz functions. Lemma D.1. (Shalev-Shwartz & Ben-David, 2014, Lemma 26.9—Contraction lemma) Let F be a set of functions, F = {f : X 7→ R}, and Φ1, ..., Φm, ρ-Lipschitz functions, namely, |Φi(α) − Φi(β)| ≤ ρ|α − β| for all α, β ∈ R for some ρ > 0. For any sample set S of m points x1, ...,xm ∈ X , let (Φ ◦ f)(xi) = Φ(f(xi)). Then,
1 m E ∈{±1}m [ sup f∈F m∑ i=1 i(Φ ◦ f)(xi) ] ≤ ρ m E ∈{±1}m [ sup f∈F m∑ i=1 if(xi) ] , (57)
alternatively, RS(Φ ◦ F) ≤ ρRS(F), where Φ denotes Φ1(x1), ..., Φm(xm) for S. Proposition D.2. (Mohri et al., 2018, Proposition A.1—Hölder’s inequality) Let p, q ≥ 1 be conjugate: 1p + 1 q = 1. Then, for all x,y ∈ R n,
‖x · y‖1 ≤ ‖x‖p‖y‖q, (58)
with the equality when |yi| = |xi|p−1 for all i ∈ [1, n].
Supporting inequalities:
(i) If A, B are sets of positive real numbers, then:
sup(AB) = sup(A) · sup(B). (59)
(ii) Given x ∈ R, we have: exp(x) + exp(−x)
2 ≤ exp(x2/2). (60)
(iii) Let X and Y be random variables, the Cauchy–Bunyakovsky–Schwarz inequality gives:
(E[XY])2 ≤ E[X2] · E[Y2]. (61)
(iv) If ψ is a convex function, the Jensen’s inequality gives:
ψ(E[X]) ≤ E[ψ(X)]. (62)

heading: E ADDITIONAL EXPERIMENTS
text: We test our model on three popular tasks for RNNs, namely the sequential pixel MNIST classification, the adding task, and the copy task (Le et al., 2015; Arjovsky et al., 2016; Zhang et al., 2018).
Sequential pixel MNIST and permuted pixel MNIST classification. This task aims to classify MNIST images to a class label. MNIST images are formed by a 28×28 gray-scale image with a label from 0 to 9. We use the reweighted-RNN along with a softmax for category classification. We set d = 5 layers and h = 256 hidden units for the reweighted-RNN. We consider two scenarios: the first one where the pixels of each MNIST image are read in the order from left-to-right and bottom-to-top and the second one where the pixels of each MNIST image are randomly permuted. The classification accuracy results are shown in Fig. 7(a) (for pixel MNIST) and Fig. 7(b) (for permuted pixel MNIST).
Adding Task. The task inputs two sequences of length T . The first sequence consists of entries that are uniformly sampled from [0, 1]. The second sequence comprises two entries of 1 and the
remaining entries of 0, in which the first entry of 1 is randomly located in the first half of the sequence and the second entry of 1 is randomly located in the second half. The output is the sum of the two entrie of the first sequence, where are located in the same posisions of the entries of 1 in the second sequence. We also use the reweighted-RNN with d = 5 layers and h = 256 hidden units for the input sequences of length T = 300. Fig. 8(a) shows the mean square error versus training epoches on the validation set.
Copy task. We consider an input sequence x ∈ AT+20 (Zhang et al., 2018), where A = {a0, · · · , a9}. x0, · · · , x9 are uniformly sampled from {a0, · · · , a7}, xT+10 = a9, and the remaining xi are set to a8. The purpose of this task is to copy x0, · · · , x9 to the end of the output sequence y ∈ AT+20 given a time lag T , i.e., {yT+10, · · · , yT+19} ≡ {x0, · · · , x9} and the remaining yi are equal to a8. We set the reweighted-RNN d = 5 layers and h = 256 hidden units for the input sequences of a time lag T = 100. Fig. 8(b) shows the cross entropy versus training epoches on the validation set.

Review summaries:
This paper proposes a new reweighted-RNN by unfolding a reweighted L1-L1 minimization problem. It develops an iterative algorithm to solve the reweighted L1-L1 minimization problem, where the soft-thresholding functions can be adaptively learned. This paper provides the generalization error bound for deep RNNs and shows that the proposed reweighted-RNN has a lower generalization error bound. In addition, the paper shows that the proposed algorithm can be applied to video-frame reconstruction and achieves favorable results against state-of-the-art methods. The paper is well organized, and the motivation is clear. 

This paper proposes a novel method to solve the sequential signal reconstruction problem. The method is based on the deep unfolding methods and incorporates the reweighting mechanism. Additionally, they derive the generalization error bound and show how their over-parameterized reweighting RNNs ensure good generalization. Lastly, the experiments on the task of video sequence reconstruction suggest the superior performance of the proposed method.