Title: A DEEP RECURRENT NEURAL NETWORK VIA UN-FOLDING REWEIGHTED 1 -1 MINIMIZATION

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.
and for < 0:
c g l , -λ1 c g l + λ2 c g l < u < -λ1 c g l + λ2 c g l , -λ1 c g l -λ2 c g l ≤ u ≤ -λ1 c g l + λ2 c g l u -λ1 c g l + λ2 c g l , -∞ < u < -λ1 c g l -λ2 c g l

1. INTRODUCTION:

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 s t ∈ R n0 , t = 1, 2, . . . , T , from low-dimensional measurements x t = As t , where A ∈ R n×n0 (n n 0 ) is a sensing matrix. We assume that s t has a sparse representation h t ∈ R h in a dictionary D ∈ R n0×h , that is, s t = Dh t . At each time step t, the signal s t can be independently reconstructed using the measurements x t by solving (Donoho, 2006) :

EQUATION

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 c D T A T (ADh (l-1) t -x t ))

, 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 1 2 x t -ADh t 2 2 . Under the assumption that sequential signal instances are correlated, we consider the following sequential signal reconstruction problem:

EQUATION

where λ 1 , λ 2 > 0 are regularization parameters and R(h t , h t-1 ) is an added regularization term that expresses the similarity of the representations h t and h t-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(h t , h t-1 ) = 1 2 Dh t -FDh t-1 2 2 , where F ∈ R n0×n0 is a correlation matrix between s t and s t-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(h t , h t-1 ) = h t -Gh t-1 1 , where G ∈ R h×h is an affine transformation that promotes the correlation between h t and h t-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) x t ), with W (l) = I -1 c D T A T AD, U (l) = 1 c D T A T , 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) } d l=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, ŝ1 , . . . , ŝT from an input measurement sequence, x 1 , . . . , x T , as following:

EQUATION

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:

EQUATION

where "•" denotes element-wise multiplication, g ∈ R h is a vector of positive weights, Z ∈ R h×h is a reweighting matrix, and G ∈ R h×h is an affine transformation that promotes the correlation between h t-1 and h t . Intuitively, Z is adopted to transform h t to Zh t ∈ R h , producing a reweighted version of it. Thereafter, g aims to reweight each transformed component of Zh t and Zh t -Gh t-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 h t to Zh t 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

(Zh t ) = 1 2 x t -ADZh t 2 2

and the non-smooth term g(Zh t ) = λ 1 g • Zh t 1 + λ 2 g • (Zh t -Gh t-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 Z l -with a gradient descent step on the fidelity term as u = Z l h

(l-1) t - 1 c Z l ∇f (h (l-1) t

), where ∇f (h

EQUATION

where the proximal operator

EQUATION

with = Gh t-1 . Since the minimization problem is separable, we can minimize (6) independently for each of the elements g l , , u of the corresponding g l , , u vectors. After solving (6), we obtain

EQUATION

c g l , (u) [for solving (6), we refer to Proposition B.1 in Appendix B]. For ≥ 0:

Φ λ 1 c g l , λ 2 c g l , ≥0 (u) =              u -λ1 c g l -λ2 c g l , ℏ - - 1 2 ℏ - + 1 2 ( ) , ,ℏ 1 2 ℏ + 1 2 - + 1 2 0 ℏ + + 1 2 - - 1 2 ( ) , ,ℏ 1 2 ℏ + - 1 2 ℏ - 1 2 0 (a) ≥ 0. ℏ - - 1 2 ℏ - + 1 2 ( ) , ,ℏ 1 2 ℏ + 1 2 - + 1 2 0 (b) < 0.

Figure 1 : The generic form of the proximal operators for Algorithm 1 -but also the activation function in the proposed reweighted-RNN. Note that per unit per layer g l leads to a different activation function.

Algorithm 1: The proposed algorithm for sequential signal reconstruction.

Input: Measurements x 1 , . . . , x T , measurement matrix A, dictionary D, affine transform G, initial h

(d) 0 ≡ h 0 , reweighting matrices Z 1 , . . . , Z d and vectors g 1 , . . . , g d , c, λ 1 , λ 2 . Output: Sequence of sparse codes h 1 , . . . , h T . for t = 1,. . . ,T do h (0) t = Gh (d) t-1 for l = 1 to d do u = [Z l -1 c Z l D T A T AD]h (l-1) t + 1 c Z l D T A T x t h (l) t = Φ λ 1 c g l , λ 2 c g l ,Gh (d) t-1 (u) end end return h (d) 1 , . . . , h (d) T

Fig. 1 depicts the proximal operators for ≥ 0 and < 0. Observe that different values of g l lead to different shapes of the proximal functions Φ λ 1 c g l , λ 2 c g l , (u) for each element u of u. Our iterative algorithm is given in Algorithm 1. We reconstruct a sequence h 1 , . . . , h T from a sequence of measurements x 1 , . . . , x T . For each time step t, Step 6 applies a gradient descent update for f (Zh t-1 ) and Step 7 applies the proximal operator Φ λ 1

c g l , λ 2 c g l ,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 Z l = I and g l = I). In that algorithm, the update terms in Step 6, namely I -1 c D T A T AD and 1 c D T A T , and the proximal operator in Step 7 are the same for all iterations of l. In contrast, Algorithm 1 uses a different Z l matrix per iteration to reparameterize the update terms (Step 6) and, through updating g l , 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

EQUATION

and the reconstructed signal at time step t is given by ŝt = Dh (d) t ; where U l , W l , V are defined as

EQUATION

EQUATION

EQUATION

)

The activation function is the proximal operator Φ λ 1 c g l , λ 2 c g l , (u) with learnable parameters λ 1 , λ 2 , c, g l (see Fig. 1 for the shapes of the activation functions). with the dictionary D. We train our network in an end-to-end fashion. During training, we minimize the loss function

t G G W2 W2 D h (d) t (b) 1-1-RNN. 1/2 U 2 U d d h (d) t-1 h (1) t h (2) t W1 W2 g 1 G ... ... ... st A xt U1 U2 Ud ŝ t G G W3 Wd D g 2 g d 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.

EQUATION

2 using stochastic gradient descent on minibatches, where the trainable parameters are

Θ = {A, D, G, h 0 , Z 1 , . . . , Z d , g 1 , . . . , g d , 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 =    Φ λ 1 c , λ 2 c ,Gh (d) t-1 W 1 h (d) t-1 + U 1 x t , if l = 1, Φ λ 1 c , λ 2 c ,Gh (d) t-1 W 2 h (l-1) t + U 1 x t , 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 λ1 c g l and λ2 c g l [see ( 7), ( 8), and Fig. 1 ] in our proximal operator, Φ λ 1 c g l , λ 2 c g l , (u), are learned for each hidden layer due to the reweighting vector g l ; hence, the proposed model has a different activation function for each unit per layer. The second difference comes from the set of parameters {W l , U l } in ( 13) and ( 9). The 1 -1 -RNN model uses the same {W 2 , U 1 } for the second and higher layers. In contrast, our reweighted-RNN has different sets of {W l , U l } per hidden layer due to the reweighting matrix Z l . 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 s t has a sparse representation h t and consecutive h t '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 W l and U l (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) . 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 W l p,q = ( j ( w l,j p ) q ) 1/q define the p,q -norm, p, q ≥ 1, of the weight-matrix W l , where w l,j ∈ R h is the j th row of W l . Since we focus on deep networks with soft-thresholding-based activation unitsdesigned by unfolding algorithms for 1 -norm minimization-we derive the network complexities under bounding per-unit 1 regularization, i.e., w l,j 1 . We also denote W l 1,∞ = max j w l,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 W l 1,∞ = max j w l,j 1 ≤ α l ; similarly, U l 1,∞ = max j u l,j 1 ≤ β l , where u l,j is the j th row of the matrix U l . As shown in ( 9), we can write the reweighted-RNN model recursively as h

Preliminaries: We consider a deep RNN as a d-layer network f (d) W,U ∈ F d,T : R h × R n → R h with weight parameters W = (W 1 , ..., W d ) and U = (U 1 , ..., U d ), where W l ∈ R h×h , U l ∈ R h×n . As in

(1)

t = f (1) W,U (h (d) t-1 , x t ) = Φ(W 1 h (d) t-1 +U 1 x t ) and h (l) t = f (l) W,U (h (d) t-1 , x t ) = Φ(W l f (l-1) W,U (h (d) t-1 , x t ) + U l x t )

, 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 ≡ h 0 .

We denote the true and training loss by L D (f ) and L S (f ), respectively, where S is the training set (of size m) drawn i.i.d. from the distribution D. The generalization error is L D (f ) -L S (f ), with f a function from the functional class F d,T . At time step t, we define X t ∈ R n×m as a matrix composed of m columns from the input vectors {x t,i } m i=1 . We also define

X t 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 X t , and h 0 ∞ = max j |h 0,j |. 

W l 1,∞ ≤ α l , U l 1,∞ ≤ β l , and 1 ≤ l ≤ d.

Assume that the input data X t 2,∞ ≤ √ mB x , the initial hidden state is h 0 , and the loss function is 1-Lipschitz and bounded by η. Then, for f ∈ F d,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,

EQUATION

where

EQUATION

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 

EQUATION

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 F d,t for 1 -1 -RNN is bounded as:

EQUATION

)

Corollary 3.1.3. The empirical Rademacher complexity of F d,t for Sista-RNN is bounded as:

EQUATION

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.

4. EXPERIMENTAL RESULTS:

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 ŝt and the original frame s t . 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 s 1 , . . . , s T ∈ R 256 . Per sequence, we obtain measurements x 1 , . . . , x T ∈ R n using a trainable linear sensing matrix A ∈ R n×n0 , with T = 20, n 0 = 256 and n < n 0 .

Our default settings are: a compressed sensing (CS) rate of n/n 0 = 0.2, d = 3 hidden layers3 with h = 2 10 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 ∈ R n0×h is initialized with the discrete cosine transform (DCT) with varying dictionary sizes of h = {2 7 , 2 8 , 2 9 , 2 10 , 2 11 , 2 12 } (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/n 0 . 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. 

5. CONCLUSIONS:

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.

A SUPPLEMENTARY EXPERIMENTS:

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) 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. c g, (u) in ( 6) for the reweighted 1 -1 minimization problem (4), for which g(v) = λ 1 g|v| + λ 2 g|v -|, is given by

Φ λ 1 c g, λ 2 c g, ≥0 (u) =              u -λ1 c g -λ2 c g, + λ1 c g + λ2 c g < u < ∞ , + λ1 c g -λ2 c g ≤ u ≤ + λ1 c g + λ2 c g u -λ1 c g + λ2 c g, λ1 c g -λ2 c g < u < + λ1 c g -λ2 c g 0, -λ1 c g -λ2 c g ≤ u ≤ λ1 c g -λ2 c g u + λ1 c g + λ2 c g, -∞ < u < -λ1 c g -λ2 c g (19) Φ λ 1 c g, λ 2 c g, <0 (u) =              u -λ1 c g -λ2 c g, λ1 c g + λ2 c g < u < ∞ 0, -λ1 c g + λ2 c g ≤ u ≤ λ1 c g + λ2 c g u + λ1 c g -λ2 c g, -λ1 c g + λ2 c g < u < -λ1 c g + λ2 c g , -λ1 c g -λ2 c g ≤ u ≤ -λ1 c g + λ2 c g u -λ1 c g + λ2 c g, -∞ < u < -λ1 c g -λ2 c g (20)

Proof. We compute the proximal operator Φ λ 1 c g,

EQUATION

)

We first consider the ∂ϕ(v)/∂v in v ∈ {(-∞, 0), (0, ), ( , ∞)}, in which ∂ϕ(v) exists. Taking the derivative of ϕ(v) in these intervals delivers

EQUATION

where sign(.) is a sign function. When setting ∂ϕ(v)/∂v = 0 to minimize ϕ(v), we derive:

v =    u -λ1 c g -λ2 c g, < v < ∞ u -λ1 c g + λ2 c g, 0 < v < u + λ1 c g + λ2 c g, -∞ < v < 0 (23)

From ( 21) and ( 23), we have

EQUATION

In the remaining range value of u, namely,

-λ1 c g -λ2 c g ≤ u ≤ λ1 c g -λ2 c g and + λ1 c g -λ2 c g ≤ u ≤ + λ1 c 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:

EQUATION

)

From ( 27), ϕ(v) is minimal when v = , since λ1 c g + λ2 c g -|u -| ≥ 0. Combining these results with the result in ( 24 W maps an input sample x i ∈ R n (from an input space X ) to an output y i ∈ R h (from an output space Y), i.e.,

y i = f (d) W (x i ). Let S denote a training set of size m, i.e., S = {(x i , y i )} m

i=1 and E (xi,y i )∼S [•] denote an expectation over (x i , y i ) from S. The set S is drawn i.i.d. from a distribution D, denoted as S ∼ D m , over a space Z = X × Y. Let F be a (class) set of functions. Let : F × Z → R denote the loss function and

• F = {z → (f, z) : f ∈ F}.

We define the true loss and the empirical (training) loss by L D (f ) and L S (f ), respectively, as follows:

EQUATION

and

EQUATION

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

L D (f ) -L S (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:

EQUATION

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 -δ,

EQUATION

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 , x t ) = Φ(W 1 h (d) t-1 +U 1 x t ) and h (l) t = f (l) W,U (h (d) t-1 , x t ) = Φ W l f (l-1) W,U (h (d) t-1 , x t ) + U l x t ,

where Φ is an activation function. The hidden state is updated as shown in ( 9). The real-valued family of functions, F d,t : R h × R n → R, for the functions f (d) W,U in layer d is defined by:

EQUATION

where α l , β l are nonnegative hyper-parameters for layer l, where 1 < l ≤ d. In layer l = 1, the real-valued family of functions, F 1,t : R h × R n → R, for the functions f

W,U is defined by:

EQUATION

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 ≡ h 0 .

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, F d,t : R h × R n → R, for the function f

EQUATION

where α 2 , β 1 are nonnegative hyper-parameters for layer l, where 1 < l ≤ d. In layer l = 1, the real-valued family of functions, F 1,t : R h × R n → R, for the functions f

W,U is defined by:

EQUATION

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:

EQUATION

The real-valued family of functions, F d,t : R h × R n → R, for the functions f

W,U in layer d is defined by:

EQUATION

where α 2 , β 1 , β 2 are nonnegative hyper-parameters. In layer l = 1,

EQUATION

where α 1 , β 1 are nonnegative hyper-parameters.

D PROOF OF THEOREM 3.1:

Proof. We consider the real-valued family of functions F d,T : R h × R n → R for the functions f

(d) W,U to update h (d)

T in layer d, time step T , defined as

EQUATION

where w d , u d are the corresponding rows from W d , U d , 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, F 1,1 : R h × R n → R, for the functions f

(1)

W,U is defined by:

EQUATION

where α 1 , β 1 are nonnegative hyper-parameters. We denote the input layer as f

W,U = h 0 at the first time step. From the definition of Rademacher complexity in (30) and the family of functions in ( 39) and ( 40), we obtain:

EQUATION

EQUATION

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:

EQUATION

EQUATION

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 w T l and f (l-1) W,U (h t-1,i , x t,i ) in ( 42), respectively, we get:

EQUATION

Similarly, from (43), we obtain:

EQUATION

where {τ, κ} = argmax t∈{1,...,T },j∈{1,...,n} m i=1 i x t,i,j .

From (41c), ( 44), and ( 46), we get:

EQUATION

EQUATION

EQUATION

EQUATION

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:

EQUATION

Let us denote µ = argmax j∈{1,...,h} m i=1 i h 0,j , from (48), we have:

EQUATION

EQUATION

EQUATION

EQUATION

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 X t ∈ R n×m , a matrix composed of m columns from the m input vectors {x t,i } m i=1 ; we also define X t 2,∞ = max 

Choosing λ = 2dT log 2+log √ n+log √ h d l=1 β l Λ l 2 Λ T 0 -1 Λ 0 -1 2 mB 2 x +Λ 2T 0 m h0 2 ∞

, we achieve the upper bound:

EQUATION

It can be noted that R S (F d,T ) in ( 50) is derived for the real-valued functions F d,T . For the vectorvalued functions F d,T : R h × R n → R h (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 h t of FastRNN is updated as follows:

EQUATION

where 0 ≤ a, b ≤ 1 are trainable parameters parameterized by the sigmoid function. Under the assumption that a + b = 1, the Rademacher complexity R S (F T ) of the class F T of FastRNN (Kusupati et al., 2018) , with W F ≤ α F , U F ≤ β F , and x t 2 ≤ B, is given by

EQUATION

)

Alternatively, under the additional assumption that a ≤ 1 2(2α F -1)T , the bound in Kusupati et al. (2018) becomes:

EQUATION

)

SpectralRNN (Zhang et al., 2018) . The hidden state h t and output y t ∈ R ny of SpectralRNN are computed as:

EQUATION

where Y ∈ R ny×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

EQUATION

where

ζ = max{ W 2T -2 2 , 1} max{ U 2 2 , 1} max{ Y 2 2 ,

1} and ξ = max{n, n y , h}. Reweighted-RNN. Based on Theorem 3.1, under the assumption that the initial hidden state h 0 = 0, the Rademacher complexity of reweighted-RNN with d = 1 is bounded as

EQUATION

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 → R}, and Φ 1 , ..., Φ m , ρ-Lipschitz functions, namely, |Φ i (α) -Φ i (β)| ≤ ρ|α -β| for all α, β ∈ R for some ρ > 0. For any sample set S of m points x 1 , ..., x m ∈ X , let (Φ • f )(x i ) = Φ(f (x i )). Then,

EQUATION

alternatively, R S (Φ • F) ≤ ρR S (F), where Φ denotes Φ 1 (x 1 ), ..., Φ m (x m ) for S. Proposition D.2. (Mohri et al., 2018, Proposition A. 1-Hölder's inequality) Let p, q ≥ 1 be conjugate: 1 p + 1 q = 1. Then, for all x, y ∈ R n , x • y 1 ≤ x p y q , (58) 

with

(iii) Let X and Y be random variables, the Cauchy-Bunyakovsky-Schwarz inequality gives:

EQUATION

(iv) If ψ is a convex function, the Jensen's inequality gives:

EQUATION

E ADDITIONAL EXPERIMENTS:

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. 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 ∈ A T +20 (Zhang et al., 2018) , where A = {a 0 , • • • , a 9 }. x 0 , • • • , x 9 are uniformly sampled from {a 0 , • • • , a 7 }, x T +10 = a 9 , and the remaining x i are set to a 8 . The purpose of this task is to copy x 0 , • • • , x 9 to the end of the output sequence y ∈ A T +20 given a time lag T , i.e., {y T +10 , • • • , y T +19 } ≡ {x 0 , • • • , x 9 } and the remaining y i are equal to a 8 . We set the reweighted-RNN d = 5 layers and h = 256 hidden units for the input sequences of a time lag T = 100. 

:

GENERALIZATION ERROR BOUNDWhile 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).

Kusupati 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.

Our implementations are available at https://1drv.ms/u/s!ApHn770BvhH2aWay9xEhAiXydfo?e=aCX1X0.

In our experiments, the 2-layer LSTM network outperforms the 3-layer one (see Table3), the default setting for LSTM is thus using 2 layers.

Code available at https://github.com/microsoft/EdgeML

Code available at https://github.com/batzner/indrnn

Code available at https://github.com/zhangjiong724/spectral-RNN

Figures and Tables:

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 s t , t = 1, . . . , T are compressed by a linear measurement layer A, resulting in compressive measurements x t . The reconstructed vectors ŝt , t = 1, . . . , T , are obtained by multiplying linearly the hidden representation h (d) t

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 Shalev-Shwartz & Ben-David (2014) and Theorem C.1 in the Appendix). Theorem 3.1 (Generalization error bound). Let F d,T : R h × R n → R h denote the functional class of reweighted-RNN with T time steps and d layers, where

[see Fig 2(c)] to build deep networks for other RNN models.

Figure3shows 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].

Figure 3: Average mean square error between the original and reconstructed frames vs. training epoches on the training and the validation sets for the default setting (a CS rate is 0.2, d = 3, h = 2 10 ).

Figure 4: Reweighted-RNN: Average mean square error between the original and reconstructed frames vs. training epoches on the training and the validation sets with different CS rates (d = 3, h = 2 10 ).

Figure 5: Reweighted-RNN: Average mean square error between the original and reconstructed frames vs. training epoches on the training and the validation sets with different network widths h (a CS rates is 0.2, d = 3).

Figure 6: Reweighted-RNN: Average mean square error between the original and reconstructed frames vs. training epoches on the training and the validation sets with different network depths d (a CS rate is 0.2, h = 2 10 ).

), we conclude the proof. C GENERALIZATION AND DEEP UNFOLDING RNNS C.1 GENERALIZATION ERROR BOUND DEFINITION Notations. Let f (d) W : R n → R h be the function computed by a d-layer network with weight parameters W. The network f (d)

representing the maximum of the 2 -norms of the rows of matrix X t , and h 0 ∞ = max j |h 0,j |.

the equality when|y i | = |x i | 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(x 2 /2).

The classification accuracy results are shown in Fig. 7(a) (for pixel MNIST) and Fig. 7(b) (for permuted pixel MNIST).

Figure 7: Reweighted-RNN on the (a) pixel-MNIST classification and (b) permuted pixel MNIST classification: Average classification accuracy vs. training epoches on the validation set.

Figure 8: Reweighted-RNN on the (a) adding task with average mean square error and the (b) copy task with average cross entropy vs. training epoches on the validation set.

Fig. 8(b)  shows the cross entropy versus training epoches on the validation set.

Corollary 3.1.1. The empirical Rademacher complexity of F d,t for reweighted-RNN is bounded as

Table content: <table/>

Average PSNR [dB]  on the test set with different CS rates.

Table content: <table><tr><td>CS Rate</td><td>sRNN</td><td>LSTM</td><td>GRU</td><td>IndRNN</td><td>FastRNN</td><td>SpectralRNN</td><td>Sista-RNN</td><td>1-1-RNN</td><td>Ours</td></tr><tr><td>0.1</td><td>25.11</td><td>24.58</td><td>25.18</td><td>25.68</td><td>25.21</td><td>25.15</td><td>25.16</td><td>24.68</td><td>26.25</td></tr><tr><td>0.2</td><td>31.14</td><td>29.46</td><td>31.19</td><td>32.90</td><td>32.05</td><td>31.65</td><td>31.53</td><td>30.79</td><td>34.19</td></tr><tr><td>0.3</td><td>35.38</td><td>32.91</td><td>36.49</td><td>37.12</td><td>36.40</td><td>36.89</td><td>36.96</td><td>37.77</td><td>42.39</td></tr><tr><td>0.4</td><td>38.05</td><td>34.95</td><td>39.47</td><td>40.84</td><td>39.21</td><td>40.22</td><td>39.57</td><td>40.35</td><td>46.03</td></tr><tr><td>0.5</td><td>39.34</td><td>36.28</td><td>41.12</td><td>45.49</td><td>41.87</td><td>41.36</td><td>41.56</td><td>43.35</td><td>48.70</td></tr></table>

Average PSNR [dB]  on the test set with different network widths h ( n n0 = 0.2, d = 3).

Table content: <table><tr><td>h</td><td>sRNN</td><td>LSTM</td><td>GRU</td><td>IndRNN</td><td>FastRNN</td><td>SpectralRNN</td><td>Sista-RNN</td><td>1-1-RNN</td><td>Ours</td></tr><tr><td>2 7</td><td>23.35</td><td>22.87</td><td>23.55</td><td>23.82</td><td>23.83</td><td>22.92</td><td>23.86</td><td>23.90</td><td>28.09</td></tr><tr><td>2 8</td><td>25.81</td><td>23.88</td><td>26.67</td><td>27.10</td><td>26.71</td><td>24.46</td><td>29.64</td><td>29.55</td><td>31.46</td></tr><tr><td>2 9</td><td>28.72</td><td>26.83</td><td>30.29</td><td>32.03</td><td>29.92</td><td>30.23</td><td>31.30</td><td>30.61</td><td>33.61</td></tr><tr><td>2 10</td><td>31.14</td><td>29.46</td><td>31.19</td><td>32.90</td><td>32.05</td><td>31.65</td><td>31.53</td><td>30.79</td><td>34.19</td></tr><tr><td>2 11</td><td>29.91</td><td>29.30</td><td>31.15</td><td>33.10</td><td>30.80</td><td>31.68</td><td>31.82</td><td>30.45</td><td>34.80</td></tr><tr><td>2 12</td><td>29.71</td><td>29.08</td><td>30.93</td><td>32.47</td><td>24.26</td><td>29.26</td><td>31.63</td><td>30.09</td><td>34.98</td></tr></table>

Average PSNR [dB]  on the test set with different network depths d ( n n0 = 0.2, h = 2 10 ).

Table content: <table><tr><td>d</td><td>sRNN</td><td>LSTM</td><td>GRU</td><td>IndRNN</td><td>FastRNN</td><td>SpectralRNN</td><td>Sista-RNN</td><td>1-1 -RNN</td><td>Ours</td></tr><tr><td>1</td><td>27.52</td><td>27.76</td><td>27.61</td><td>30.12</td><td>29.32</td><td>29.62</td><td>28.41</td><td>28.49</td><td>29.19</td></tr><tr><td>2</td><td>29.21</td><td>29.46</td><td>29.68</td><td>32.73</td><td>30.84</td><td>31.37</td><td>30.67</td><td>30.19</td><td>32.12</td></tr><tr><td>3</td><td>31.14</td><td>22.29</td><td>31.19</td><td>32.90</td><td>32.05</td><td>31.65</td><td>31.53</td><td>30.79</td><td>34.19</td></tr><tr><td>4</td><td>31.64</td><td>16.50</td><td>29.26</td><td>20.65</td><td>31.07</td><td>31.10</td><td>32.56</td><td>31.80</td><td>35.99</td></tr><tr><td>5</td><td>16.50</td><td>26.66</td><td>16.50</td><td>25.17</td><td>20.10</td><td>30.52</td><td>33.07</td><td>32.50</td><td>36.91</td></tr><tr><td>6</td><td>22.28</td><td>16.50</td><td>16.50</td><td>20.90</td><td>19.37</td><td>29.56</td><td>31.99</td><td>32.00</td><td>38.90</td></tr></table>

Peer review (iclr2020):
Authors proposed a deep RNN via unfolding reweighted l1-l1 minimization, where reweighted l1-l1 minimization algorithms are applied to a video task. Overall, the paper is well explained in a theoretical part and exhibits a good result compared with other conventional RNN methods in the experiment. In Section 3, authors formulate Rademacher complexities for both conventional and proposed method, which shows the generalization performance of the proposed method when d increases. And this is empirically highlighted in Table 3 in Section 4. Major points: Section 1: - First part of the introduction can be confusing because Eq. (1) sounds like representing dictionary learning framework (plus DNN is immediately described after Eq. (1) instead of RNN) and RNN is not explicitly written. It should be clearly written and flow should be considered. Section 2: - It is hard to get how parameter g in Eq. (3) derives. Section 3: - How to build network depth d for the network? A figure should be required. Section 4: - Even though previous papers (e.g., Wisdom et al. and Le et al.) just focus on single dataset like moving MNIST, I believe testing on language data is also quite important (this is a full paper and exhaustive experiments should be mandatory). For example, it may be good to use Penn TreeBank dataset to make a comparison. - In Table 3, how did you set LSTM deeper? Is it a stacked LSTM? - Existing RNN methods should include other variations of LSTM (in particular, SOTA methods are welcomed) such as bidirectional LSTM and LSTM with attention mechanism. It should be better to compare with these methods. Appendix: - It would be helpful for readers to show interpretabilities of the model additionally. For example, visualizing features from each RNN model would be beneficial. Minor points: - After introduction of unfolding reweighted l1-l1 minimization, how did the computational cost increase compared to previous l1-l1 minimization? - In Section3, for easiness to readers, it may be good to briefly summarize how does the predictor’s generalizability and Rademacher complexities relate.