A Deep Recurrent Neural Network via Unfolding Reweighted l1-l1 Minimization
Authors: Huynh Van Luong
Duy Hung Le
Nikos Deligiannis
Venue:  (2020)

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

Under review as a conference paper at ICLR 2020
A DEEP RECURRENT NEURAL NETWORK VIA UN- FOLDING REWEIGHTED 11-11 MINIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Deep unfolding methods design deep neural networks as learned variations of optimization methods. These networks have been shown to achieve faster conver- gence and higher accuracy than the original optimization methods. In this line of research, this paper develops a novel deep recurrent neural network (coined neweighted-RNNg
by unfolding a reweighted ε-- minimization algorithm and applies it to the task of sequential signal reconstruction. To the best of knowl- edge, this is the first deep unfolding method that explores reweighted minimization. Due the underlying reweighted minimization model, our RNN has a different soft-thresholdigg 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 peeeperrmttiiiinngg weights. Moreover, we establish theoretical generalization erтor bounds for the proposed reweighted-RNN model by means of Rademacher complexity. The bounds reveal that the param- eterization of the proposed reweighted-RNy 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- -eNN significantly outperforms existing RNN models.
INTRODUCTION
The problem of reconstructing sequential signals from low-dimensional measurements across time of great importance for number of applications such as time-series data analysis, future-frame prediction, and compressive video sensing. Specifically, a sequence of signals S; E IR"0, f = .,2,..., T. from low-dimensional measurements x; As;, where A R (n < no) is sensing matrix. We assume that s; has a sparse representation h, E R in a dictionary D E Ro that is, sy = Dh,- At each time step t. the signal Sy can be independently reconstructed using the measurements x, by solving (Donoho) 2006):
consider the problem of reconstructing
min hr
x 12
ADh, 1 \|bbel11
where I is the -n-orrm and À is regularization parameter. The iterative shrinkagg-threshholling algorithm (ISTA) DDubeeciiss et al. 2004 solves (1) by iterating over ( = og (h (1-1)
DDTAT (ADD, (1-1) x,)), where is the iteration counter, (,) = sign(u) [0) |u|| 7 + is the soft-thresholding operator, 7 A and is upper bound the Lipschitz constant of the gradient of || ADh, 12.
Under the assumption that sequential signal instances are correlated, we consider the following sequential signal reconstruction problem:
min { ||x ADh,l + Aallballa + X2 R(h, h--1)
where d2 0 are regularization parameters and R(h;, hx-1) is an added regularization term that expresses the similarity of the representations h, and h of two consecutive signals. Wisdom et al. (2017) proposed RNN design (coined Sista-RNN) by unfolding the sequential version of

---

Under review as a conference paper at ICLR 2020
ISTA. That study assumed that two consecutive signals are close in the fy-norm sense, formally, R(b, 1 = [Dh, - F where F E Ro is a correlation matrix between S and 9t-1- More recently, the study by Le et al. (2019) designed the R which stems from unfolding an algorithm that solves the 11-81 minimization problem (Mota et al. 2017 2016). This is version of Problem (2) with R(h, hę-1) = [h, Gh,-1l11. where G E R is affine transformation that promotes the correlation between h, and h Both studies (Wisdom et al. Le et al. 2019) have shown that aarefully-designet deep RNN models outperform the generic RNN model and ISTA (Daubechies et al. 2004) in the task of sequential frame reconstruction.
2017
Deep neural networks (DNN) have achieved state-of-the-e art performance in solving ( 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
LeCCun 2010) and its variants, including ADMM-Net (Sun et al. 2016), AMP (Borgerding et al. 2017). and unfolded version of the iterative hard thresholding algorithm (Xin et al. (0166).
LISTA Grrgorr & LeCun 2010) unrolls the iterations of ISTA into a ford-forward neural network with weights, where each layer implements iteration: h (1) = d.yan (w (W"",, h("11) + U(*x,), with ( I- - 1 DT T A T AD, U = AD"AA" AT, and 7(() being learned from data. It has been shown (Gregor & LeCun 2010 Sprechmann al.. 2015) that a d-layer LISTA network with trainable parameters O (WO,, U (0) === 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 and U 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 sequence, $ $1,..., By from an input measurement sequence, x XT, as following:
h, (Wh, + Uxt),
S. = Dh.
It has been shown that reweighted algorithms- suchh as the reweighted l minimization method by Candès et al. (2008) and the reweighted f--;, minimization by Luong et al. (2018) -oupperform their non-reweighted counterparts. Driven by this observation, this paper proposes a novel deep RNN architecture by unfolding a reweighted-(i
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 al. 2017). which have shown that better performance can be achieved by highly over- parameterized networks, i.e., networks with far more parameters than the number of training samples. While the most recent studies (related over- wer-parameterized DNNs) consider fully-connected networks applied on classification problems (Neysaaurr et al. 2019), our approach focuses on deep-unfolding architectures and opts 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 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 al. 2018 Kusupati et al. 2018).
Contributions. The contributions of this work are as follows:
We propose principled deep RNN model for sequential signal reconstruction by unfolding a reweighted fi- minimization method. Our reweighted-RNV model employs different soft-thresholding functions that are adaptively learned per hidden unit. Furthermore, the proposed model over- parreearamtterized, 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-parameterizatte of our RNN ensures good generalization. To best of our knowledge, this is the first generalization error
2

---

Under review as a conference paper at ICLR 2020
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 the task of reconstructing video sequences from -iw-dimeniional measurements. We show significant gains when using our model compared to several state-of-the-ars RNNs (including unfolding architectures), especially when the depth of RNNs increases.
2 A DEEP RNN VIA UNFOLDING REWEIGHTED-G1-4 MINIMIZATION
In this section, we describe a reweighted l--6, minimization problem for sequential signal reconstruc- tion and propose an iterative algorithm based on the proximal method. We then design a deep RNN architecture by unfolding this algorithm.
The proposed reweighted E1-E, minimization. We introduce the following problem:
min
X ADZh, 12 A o Zh, |I + A2llg (Zh; Ghi-1)lia)
(4)
where "o" denotes element-wise multiplication, E R is a vector of positive weights, Z E Rexh is reweighting matrix, and G E Rhxh is an affine transformation that promotes the correlation between h and h2 Intuitively, Z is adopted to transform h, to Zh, E RR, producing a reweighted version of it. Thereafter, g aims to reweight each transformed component of Zh, and Zh, Gh,-1 in the L norm regularization terms. Because of applying reweighting (Candès et al. 2008). the solution of Problem (4) is more accurate sparse representation compared to the solution of the f1- minimization problem in Le et al. (2099) (where Z = and g = I). Furthermore, the use of the reweighting matrix Z transform h, Zh, differentiates Problem (4) from the reweighted f--1 minimization problem in Luong et al. 22018 8) where Z I.
The objective function in consists of the differentiable fidelity term /(Zh. | ADZh, 1/ Ai Zh; || +
Agllgo (Zh, Gh,-1)ll1. We use proximal gradient method (Beck & Teboulle, 2009) to solve (4) At iteration 4, we first update hit-11 after
and the non-smooth term g
(Zhh))
(1-1)
being multiplied by Z:-with gradient descent step on the fidelity term as Z,h;
Zz (b, where (5(h AT
(ADh, ((-1)
xx). Then, (!) is updated
A B, Gh Z,h (1-1) ZVT(((-)))
+ x2 8i.
(5)
where the proximal operator & و 22 Agg Gh.
(u) is defined as
1 { g(v) + - 11 u
Aa R. (u) arg min
(6)
veR*
with h Gh,-1- Since the minimization problem separable, we can minimize (6) independently for each of the elements gt. ht u of the corresponding g:, h vectors. After solving (6)
we obtain
Au A a (u) [for solving (6) we refer to Proposition B. in Appendix For 0:
A1 gi
Aa
h + A gi
A
u
gi < u X
h
h + X1 gi
L2
g:
<
<
h
+
A1
+
Az
i A1
Aa 8 Bi
A1 gi
A >2
Y gi b2 gi < u
h
+
g
Ag
gi
0,
A1 gi 22 g u <
2
g1
A2
gi
A1
Ag gi,
-00 < M gi A
+
gi
and for <<<
A1 gi
Aa gi,
A + da < M 00
0,
X1
gi
g
gi
L 2 (u)
4
A1 g
Aa gi,
ty gi 1 g
< M <
>1
g
A gi
(8)
h
1 gi A
gi
7
R
22 g
A1 gi
Aa gi,
8
h
A
69
3

---

Under review as a conference paper at ICLR 2020
2x 2an
(a) h 2
(b) < 0.
Figure 1: The generic form of the proximal operators for Algorithm 1 but also the activation function the proposed reweighted-RNy Note that per unit per layer gi leads a different activation function.
Algorithm 1: The proposed algorithm for sequential signal reconstruction.
Input: Measurements XI.... Xy, measurement matrix A, dictionary D, affine transform G,
initial hg
(d) = hy. reweighting matrices Zi...., Zu and vectors g...... gds c, A1. 22.
Output: Sequence of sparse codes h1...., hr.
for /....7''do
h, (0) Gh,- (d)
for / = / to do
[Z. A (1-1) AZ,
h,
(I) Φ J - Gh (u)
end
end
10
return h (d)
h
Fig. depicts the proximal operators for and Observe that different values gi lead to different shapes of the proximal functions Φ x, A2 (u) for each element of u. Our iterative algorithm is given in Algorithm We reconstruct sequence h1,..., hy from sequence of measurements XJ.... Xy. For each time step t, Step applies a gradient descent update for (Zh 1) and Step 7 applies the proximal operator 2 2 Gh
I
element-wise the result.
Let us compare the proposed method against the algorithm in Le al. (2019) -which resulted in the 41-2-RRN solves the f1-( minimization in Mota et al. (2016) (where Zi and g; = I). In that algorithm, the update terms in Step 6 namely
DD AD and A and the proximal operator in Step are the same for all iterations of 7. In contrast, Algorithm uses different Z matrix per iteration to reparameterize the update terms (Step and, through updating g;, applies a different proximal operator each element (in Step 7 per iteration /.
The proposed reweighted-He -NNN. We now describe the proposed architecture for sequential signal recovery, designed by unrolling the steps of Algorithm | across the iterations / I,..., d (yielding the hidden layers) and time steps t = ,,..., Specifically, the I-th hidden layer is given by
(d) W,h + U,X,
ifl = 11
h
Wih + U,x:)
ifl > 1,
Ch
and the reconstructed signal at time step is given by 8; = Dh, ( where U, Wi, are defined as
U, -ZZDDA' AT. VL,
(10)
W, = G AADTATADG.
(11)
W = Z, Z.DTAAAR 1> 1.
(12)
The activation function the proximal operator + x gi: gi (see Fig. for the shapes of the activation functions).
>/ a (u) with learnable parameters A1, X2, C,
4

---

Under review as a conference paper at ICLR 2020
Wy
W
(b) 21-41-RR -RNN.
Wi
1G
W.
W.
W.
D
(a) The proposed reweighted-RNN
Stacked RNN.
Figure 2: The proposed (a) reweighted-RNN vS. (b) R-NN-RNN and (c) Stacked RNN with d layers.
Fig. 2(a) depicts the architecture of the proposed neweighted-RNN Input vectors Sr, 1 1, ...., T are compressed by a linear measurement layer A, resulting in compressive measurements x, The recon- structed vectors $,, & ===1 -1..... T, are obtained by multiplying linearly the hidden representation h, with the dictionary D. We train our network in an end-to-end fashion. During training, we minimize the loss function (())
E
Σ
-..12 using stochastic gradient descent mini-
batches, where the trainable parameters are θ = {A, D. G, ho, Zi...., Ze. .i.......... ga. C, A1 22)-
against the recent 1--1--N--- -NNN Le et al. 2019 Fig. 2(b)). The I-th hidden layer in E1-1, RNN 18 given by
We now compare the proposed reweighted RNN FFgg, 2(a)
o x1 A2
W1h, + U1XI)
ifl =1
h (1)
c
(13)
+ Sy cn((
W2h, (t-1) + +IIe))
if 1.
The proposed model has the following advantages over RNNNN Firstly, RI-N--RNN uses the proximal operator T 22, in (u) activation function, whose learnable parameters \1, X2 are fixed
across the network. Conversely, the corresponding parameters 2 and 22 g/ [see
(7)
( and Fig.
I in our proximal operator, 4 2 > gn (u), are learned for each hidden layer due to the reweighting
vector gú; hence, the proposed model has a different activation function for each unit per layer. The second difference comes from the set of parameters (W,, U.} in (13) and (9) The f model uses the same (W2, U1} for the second and higher layers. In contrast, our reweighted-RNy
has different sets of (W,, U.} per hidden layer due to the reweighting matrix Z, These two aspects [which are schematically highlighted in blue fonts 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) newwighted-RNN promotes the inherent data structure, that is, each vector S, has sparse representation h, and consecutive h,'s 's are correlated. This design characteristic of the reweighted-Ree -RtntedddNNNN- 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.j [216)] Huang et al.] (017)) in deep neural network literature]. Furthermore, in (10) and (12) we see weight coupling of W and U; (due 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 Chen al. (2018), it can be shown that reweighted-RNNN in theory, needs a smaller number of iterations (i.c., d in Algorithm []] to reach convergence, compared to ISTA
(Daubechies al. 2004) and FISTA (Beck & Teboulle 2009).
3 GENERALIZATION ERROR BOUND
While increasing the network expressivity, the over parameterization of reweighted-RNy raises the question 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-of- the-art RNN architectures. We provide bounds on the Rademacher complexity (Shalev-Shwarzz & Ben-David 2014) for functional classes of the considered deep RNNs, which used to derive generalization error bounds for evaluating their generalization properties (we refer to Appendix C.] for definitions of the Rademacher complexity and the generalization emror bound).
5

---

Under review as a conference paper at ICLR 2020
Wi FaTT RA R with weight parameters W W W and U (U,- Ual. where W E R
Preliminaries: We consider deep RNN d-layer network w
R U E
Rhxn As in Bartlett et al. 2017) Golowich al. (2018): Neyshabur al. 2019 2015
derive generalization error bounds by controlling norms of the weight matrices. Let Wilpng
(I, pl)))) define the -ormm, p.g 9 2 1, of the weight-matrix Wt, where Wi. E R is
the 7 row of w, Since we focus on deep networks with soft-thresholding-bbee -baed activation units- designed by unfolding algorithms for & -norm minimization we derive the network complexities under bounding per-unit l regularization, i.e., I| We also denote || max, || I| as the maximum of the & -n-ormm of the matrix's 's rows. We assume that the -norm of the weights of each neuron bounded as |
max, ||W,,lla S oy; similarly, ||U/]|, = max, || I
3r, where j the jth row of the matrix Uy. As shown in
(9), we can write the reweighted-RNg RNN
model recursively as h WW 1-, x,) = ((W h (d) Ux,) and h - (-1 x,) =
((1)
(d)
(d)
L @(Wi (1-11) (d) xx) + UlX;), where (b) is an activation function. For convenience, we denote 1, we have hg ho-
the input layer as J h,"); namely,
We denote the true and training loss by T.D (f) and (.s( respectively, where S is the training set (of size m) drawn i.i.d. from the distribution D. The generalization error is TDD - [.s(),, with f a function from the functional class Fa,T. At time step t, we define X, E IR as a matrix composed
of m columns from the input vectors {xt, )== We also define |X|l2,0c = V (t......
max Σ x
as the maximum of the f2-norms of the rows of matrix X,, and |hooloo = max, [bo.jl.
Generalization error bound. We first derive the generalization error bound for the proposed teweighted-RNN. (with T time steps) based on Rademacher complexity (see Theorem 26.5 in Shalev Shwartz & Ben- Ben-David (2014) and Theorem C. the Appendix).
Theorem 3.1 (Generalization error bound). Let Far: RRAh x " IR denote the functional class of reweighted-RNi
with T time steps und d layers, where [| Son, [|Ui]| S 33, and 1 < 1 S d. Assume that the inpul data [[eel2.s0 S SymB,, Bxs the initial hidden state ha, and the loss function is I i-Lipschitz and bounded by n. Then, for f E Far and any 5 > 0, with probability at least 1 - over a training set S of size m drawn i..dd from the distribution D.
2 2log(4/8)
LD(f) - Ls(f) S 2Rs + Anp
(14)
where
Rs(Far) sv
(AdT log 2 + log n + log h)
/
(2
Σ 1=1
d
2
(1
'(47 1 2
B2 + 1 18.. (15)
Ao 1)
m
with At defined as follows: A
II ag with 051 d and Aa = 1. k=l-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 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 and the number time steps T under the appropriate norm constraints.
To compare our model with fi-(--RNN (Le et al. 2019) and Sista-RNN (Wisdom et al. 2017), we derive bounds on their Rademacher complexities for time step t. The definitions of functional class Fat for the tth time step of reweighted-RNNY f--(1-RNN and Sista-RNN are given in Appendix IR h denote matrix with columns the vectors of the previous hidden state max E 12 S VmB ke(L.....))
C.2
Let H E
(h--,, )mm and [ | V
6

---

Under review as a conference paper at ICLR 2020
Corollary 3.1.1. The empirical Rademacher complexity of Fd.: t for reweighted-RNN is bounded
2(4d 2 + log log h).
(2 B(A1)
(Fa SV
B +
(16)
m
with m the number of training samples and A given by Aa = 1, A = II k=1+1
with 0 05 d-1.
Proof. The proof is special case of Theorem 3.1 for time step t.
Following the proof of Theorem 3.1 we can obtain the Rademacher complexities for f and Sista-RNN: Corollary 3.1.2. The empirical Rademacher complexity of Fa, for C f1-L1-RNN is bounded as:
Rs s
2( 2og + log log h)
B
2 1 a2
1)
B ajaz 2(d-1) B
(17)
m
Corollary 3.1.3. The empirical Rademacher complexity of Fd.: for Sista-RNN is bounded as: (F(F)))
2 2(d + log n + log h)
87
2 - 1 a2
B² +
0102 + B2
(d-1)
(
dd-1 d-1
-1 11
))
B
h
1
02
(18)
By contrasting (16) with (17) and (8) we see that the complexities of f1-41-RNY and Sista-RNN have polynomial dependence on Q1 31 and a22 33 (the norms of first two layers), whereas the complexity reweighted-RNN has polynomial dependence on a Oa and Bi, 3r (the norms of all layers). This over-parameterization offers a flexible way to control the generalization error reweighted-RNN. We derive empirical generalization errors in Fig. 6 in Appendix A demonstrating that increasing the depth of reweighted-RNe -NNN still ensures the low generalization error.
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 hignal-to-noiee ratio (PSNR) between the reconstructed & and the original frame s, 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, IK, and IK sequences, respectively. In order reduce the training time and memory requirements, we downscale the frames from 64 x 64 to 16 x 16 pixels using bilinear decimation. After vectorizing, we obtain sequences of ....... Sy trainable linear sensing matrix A E [R with T = 20, no = 256 and n < 72g-
IR 256 Per sequence, obtain measurements Xi....,X0 XT E R" using
We compare the reconstruction performance of the proposed reweighted-Ree -NNN model against deep- unfolding RNN models, namely, RNNN- (Le et al. 2019). Sista-RNN (Wisdom et al.
2017 7).
and stacked-RNN models, that is, sRNN (Elman) 1990). LSTM (Hochreiter & Schmidhuber 1997
GRU CCoo et al. 2014). FastRNN (Kusupati et al. 2018 IndRNN (Li et al. 2018) and Spec- traIRNN (Zhang et al. 2018). For the vanilla RNN, LSTM and GRU, the native Pytorch cell implementations were used. The unfolding-
methods were implemented in Pytorch with (2017): Le et al.) (2019). For FastRNN, IndRNN, and SpectraIRNN cells, we use the publically available Tensorflow implementations. While Sista-RNN, (G-E-RRNN and reweighted-RNe -NN have their own layer-stacking schemes derived from unfolding minimization algorithms, we use the stacking rule in Pascanu et al. (2013) [see Fig 2 to build deep networks for other RNN architectures.
Sista-RNN and Li-N-RRNN tested by reproducing the experiments Wisdom
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 available at dttp:///dddy.m///ss... www.m//u.w...../////////aaaaahh Xa
7

---

Under review as a conference paper at ICLR 2020
Our default settings are: compressed sensing (CS) rate of n/noo 0.2, d' hidden layer with h = 20 hidden units per layer. each set of experiments, we vary each of these hyper- parameters while keeping the other two fixed. For the unfolding methods, the overcomplete dictionary initialized with the discrete cosine transform (DCT) with varying dictionary sizes
D E R of h (2?, 2 29, 200 211, 212) (corresponding to number of hidden neurons in the other methods). For initializing A1, A2 [see (2) ()).
we perform a random search in the range of [10-s, 3.0] To avoid the problem of exploding gradients, we clip the gradients during
in the validation backpropagation such that the mn-nrms are less than or equal to 0.25. We do not apply weight decay regularization as we found often leads to worse performance, especially since gradient clipping 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 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 summarizes the reconstruction results for different CS rates n/no. The reweighted-RNe model systematically outperforms the other models, often by large margin. Table shows similar improvements for various dimensions of hidden units. Table shows that IndRNN delivers higher reconstruction performance than model when small number of hidden layers (d 1,2) is used. Moreover, when the depth increases, reweighted -NNN 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, 21.48M, and 18. parameters, respectively.
Table 1: Average PSNR [dB] on the test set with different CS rates.
Rate
sRNN
LSTM
GRU
IndRNN
FastRNN
SpectraIRNN
Sista-RNN
4GNN-RNN
Ours
0.1
25.11
24.58
25.18
25.68
25.21
25.15
25.16
24.68
26.25
31.14
29.46
31.19
32.90
32.05
31.65
31.53
35.38
32.91
36.49
37.12
36.40
36.89
36.96
37.77
42.39
34.95
40.84
39.21
40.22
39.57
41.56
Table 2:
Average PSNR [dB] on the with different network widths h 12
0.2, d 3).
ng
GRU
IndRNN
FasRRN
SpectraIRNN
f1-41-RNN
Ours
2
23.55
23.90
2 25.81
23.88
26.67
27.10
26.71
24.46
29.64
29.55
31.46
2
28.72
26.83
30.29
32.03
29.92
30.23
31.30
30.61
33.61
n
31.14
29.46
31.19
32.90
32.05
31.65
31.53
30.79
34.19
2 29.91
29.30
31.15
33.10
30.80
31.68
31.82
30.45
34,80
2
29.71
29.08
30.93
32.47
24.26
29.26
31.63
30.09
34.98
Table 3: Average PSNR [dB] on the test set with different network depths d (a.
0.2, / 20)).
sRNN
LSTM
GRU
IndRNN
FastRNN
SpectraIRNN
Sista-RNN
RRNN
Ours
27.52
27.76
27.61
30.12
29.32
29.62
28.41
28.49
29.19
29.21
29.46
29.68
32.73
30.84
31.37
30.67
30.19
32.12
31.14
22.29
31.19
32.90
32.05
31.65
31.53
30.79
34.19
31.64
16.50
29.26
20.65
31.07
31.10
32.56
31.80
38,99
5
16.50
26.66
16.50
25.17
20.10
30.52
33.07
32,50
36.91
22.28
16.50
16.50
20.90
19.37
29.56
31.99
32,00
38.90
CONCLUSIONS
We designed a novel deep RNN by unfolding an algorithm that solves a reweighted εT-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 sequential video-frame reconstruction shows that our model (i) outperforms various state-of-th sate-off-hhe-nn art RNNs in terms of accuracy and (ii) is capable of stacking many hidden layers resulting in better learning capability than the existing unfolding methods.
In our experiments, the 2-layer L.S network outperforms the 3-layer one (see Table 3 the default setting for I. STM is thus using 2 layers.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Martin Arjovsky, Amar Shah, and Yoshua Bengio. Unitary evolution recurrent neural networks. In Proceedings of the 33rd International Conference on International Conference on Machine Learning (ICML), 2016.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normaaizzdd margin bounds for neural networks. In Advances in Neural Information Processing Systems 30, pp. 6240-62- (209..222.220 2017.
A. Beck and M. Teboulle. A fast iterative shrinkage-threshholding algorithm for linear inverse problems, SIAM Journal on Imaging Sciences, 2(1):183-202, 2009.
M. Borgerding, P. Schniter, and S. Rangan. AMP-inspired deep networks for sparse linear inverse problems. IEEE Transactions on Signal Processing, 63 65116):4233-4308 2017.
Emmanuel J. Candès, Michael B. Wakin, and Stephen P. Boyd. Enhancing sparsity by reweighted L minimization. Journal of Fourier Analysis and Applications, 14(5):877-905, 2008.
Xiaohan Chen, Jialin Liu, Zhangyang Wang, and Wotao Yin. Theoretical linear convergence of unfolded ista and its practical weights and thresholds. In Advances in Neural Information Processing Systems 31, 2018.
K. Cho, B. Van Merriënboer, C. Gulcehre, D. Bahdanau, F. Bougares, Schwenk, and Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. arXiv preprint arXiv: 4406. 1078, 2014.
Corinna Cortes, Xavier Gonzalvo, Vitaly Kuznetsov. Mehryar Mohri, and Scott Yang. AdaNet: Adaptive structural learning artificial neural networks. Proceedings of the 34th International Conference on Machine Learning, Sydney, Australia, 06-11 Aug.
I. Daubechies, M. Defrise, and De Mol. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Communications on Pure and Applied Mathematics, 57(11): 1413 1457, 2004.
D. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289-1306 April 2006.
Jeffrey L.. Elman. Finding structure in time. Cognitive Science, 14(2):179 - 1990.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Proceedings of the 31st Conference On Learning Theory. volume 75, pp. 297-299, 06-09 (6-09 Jul 2018.
Karol Gregor and Yann LeCun. Learning fast approximations of sparse coding. In Proceedings of the 27th International Conference International Conference on Machine Learning, ICML' 10, pp. 399-406, 2010.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, June 2016.
S. Hochreiter and J. Schmidhuber. Long short-term memory. Neural Computation, 983: 1780, 1997.
G. Huang, Z. Liu, L. v. d. Maaten, and K. Q. Weinberger. Densely connected convolutional networks. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017.
Aditya Kusupati, Manish Singh, Kush Bhatia, Ashish Kumar, Prateek Jain, and Manik Varma. Fastgrnn: A fast, accurate, stable and tiny kilobyte sized gated recurrent neural network. In Advances in Neural Information Processing Systems 31, 2018.
Hung Duy Le, Huynh Van Luong, and Nikos Deligiannis. Designing recurrent neural networks by unfolding an 11-11 minimization algorithm. In Proceedings of IEEE International Conference on Image Processing, 2019.

---

Under review as a conference paper at ICLR 2020
Quoe V. Le, Navdeep Jaitly, and Geoffrey E. Hinton. A simple way initialize recurrent networks of rectified linear units. CoRR, 100/1504400914,, 2015.
S. Li, W. Li, C. Cook, C. Zhu, and Y. Gao. Independently recurrent neural network (indrnn): Building a longer and deeper rnn. 2018 IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 5457-5466, June 2018.
Jialin Liu, Xiaohan Chen, Zhangyang Wang. and Wotao Yin. ALISTA: Analytic weights are as good as learned weights in LISTA. In International Conference on Learning Representations, 2019.
A. Lucas, M. Iliadis, R. Molina, and A. K. Katsaggelos. Using deep neural networks for inverse problems in imaging: beyond analytical methods. IEEE Signal Processing Magazine, 35(1):20-36, 2018.
W. Luo, W. Liu, and S. Gao. A revisit sparse coding based anomaly detection in stacked mnn framework. In 2017 IEEE International Conference Computer Vision (ICCV), pp. 341-349, Oct 2017.
H. V. Luong, N. Deligiannis, J. Seiler, S. Forchhammer, and A. Kaup. Compressive online robust principal component analysis via n-41 minimization. IEEE Transactions on Image Processing, 27 (9):4314-4329, Sept 2018
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning, Second edition. MIT Press, Cambridge, Massachusetts, USA, 2018. ISBN 9780262039406.
J. F. C. Mota, N. Deligiannis, A. C. Sankaranarayanan, V. Cevher, and M. R. D. Rodrigues. Adaptive- rate reconstruction of tire-varying signals with application in compressive foreground extraction. IEEE Transactions Signal Processing, 64(14))3651-366) July 2016.
C. Mota, N. Deligiannis, and M. D. Rodrigues. Compressed sensing with prior information: Strategies, geometry, and bounds. IEEE Transactions on Information Theory, 6377):4472-4496, July 2017.
Ali Mousavi, Ankit B Patel, and Richard G Baraniuk. A deep learning approach to structured signal recovery. In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1336-1343 IEEE, 2015.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Proceedings of The 28th Conference on Learning Theory, 2015.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of oaaataaraatniiiaaooon generalization of neural networks. Int. Conf. on Learning Representations, ICLR 2019, 2019.
R. Pascanu, C. Gulcehre, K. Cho, and Bengio. How to construct deep recurrent neural networks. arXiv preprint arXiv: /312.6063 2013.
R. Pascanu, C. Gulcehre, K. Cho, and Y. Bengio. How construct deep recurrent neural networks.
In International Conference on Learning Representations (ICLR), 2014.
Shai
and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, New York, NY, USA, 2014. ISBN 1107057132. 1070053337
Sprechmann, A. M. Bronstein, and Sapiro. Learning efficient sparse and low rank models. IEEE Transactions Pattern Analysis and Machine Intelligence, 37(9):1821-188 Sep. 2015.
N. Srivastava, E. Mansimov, and R. Salakhudinov. Unsupervised learning of video representations using LSTMs. In Proceedings of the 32nd International Conference on Machine Learning (ICML), 2015.
Sun, H. Li, and Xu. Deep ADMM-Net for compressive sensing MRI. Advances in Neural Information Processing Systems, pp. 10-18, 2016.
10

---

Under review as a conference paper at ICLR 2020
S. Wisdom, T. Powers, J. Pitton, and L. Atlas. Building recurrent networks by unfolding iterative thresholding for sequential sparse recovery. In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), March 2017.
B. Xin, Y. Wang, W. Gao, D. Wipf, and B. Wang. Maximal sparsity with deep networks? In Advances in Neural Information Processing Systems, pp. 4340-4348, 2016.
Jiong Zhang, Qi Lei, and Inderjit S. Dhillon. Stabilizing gradients for deep neural networks via efficient SVD parameterization. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, 2018.

---

Under review as a conference paper at ICLR 2020
A SUPPLEMENTARY EXPERIMENTS
In our experiments, we use the publically available Tensorflow implementations for FastRNN 7 IndRNN and SpectralRNN cells.
cells. While Sista-RNN, RNNN and reweighted-RNNN have their own layer-stacking schemes derived from unfolding minimization algorithms, we use the stacking rule in Pascanu et al. (013) [see Fig 2 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-RNG 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. different network depths d [Fig. 6 and different network widths h [Fig. 5).
Moen seghereeeeeer Ceneeeer
validudion Boss
Mean qggeeee
validation liss
train lows
vadidation Ins
100
159
308
100
159
200
100
150
Traising spuels
Training
Tpache specle
Training
(a) SRNN.
(b) LSTM.
(c) GRU.
Monn squeer cree
Moss squeee crne
200
train Bos
trxis
100
z00)
100
150
201
300
150
208
308
158
200
Traising sprels
Traising specla
Traising specls
(d) IndRNN.
(e) FastRNN.
(I) SpectraIRNN.
Moet saaaeeee
200
trais Joss
Mean Sopeeeeeenna
2000
Irais Joss
Meat spuretiaaaa
200
Insia validation Das
validudoon
validaiion
100
200
200
100
150
304
100
150
304
100 Training spacks
Tracsingspocla
Traising
(g) Rista-RNN.
(h) RNNN--RNN.
reweighted RNN.
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 = ").
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-RNe 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 Le et al. (2019) (as the baseline method) and Reweighted-RNN
Fast-RNN and Spectral RNN,
could be made between due to their similarities in implementations. At the default settings, it takes 3,521 seconds and 2,985 seconds to train Reweighted-RNN -NNN and f--E,- -RNN Le et al. 2019). respectively.
*Code available http://ghhaa..cmmmiicooofffffgf
*Code available at http://gghhua.com//hareerrmimm 'Code available http://gttticcooommmmnnnnn/////f
12

---

Under review as a conference paper at ICLR 2020
Mosu square eree
Mouse squaee ente
200
train Joss
Iriee loss validation bas
valitadon bas
100
200
Traisinz specis
Trainine specis
Trainins
(a) CS Rate 0.1.
(b) CS Rate is 0.2.
(c) CS Rate is 0.3.
Mosc sqgaree aaapate-eeree
validation
valldatiin Jos
Moun
300
Ste
108
20
Traking spechs
Traning epochs
(d) CS Rate is 0.4.
(e) CS Rate is 0.5.
Figure 4: Reweighted-RNY Average mean square error between the original and reconstructed frames training epoches the training and the validation sets with different CS rates (d 3, h 2
200
Irain
validadon bas
Moan square
validaatio bas
200
train loss
voldution
Mexx
Training-pch
Training
Training
(a) h 2
(b) h 2
(c) 2
Mean squaree ceree
Meato squareeeeee KePe
validation
260
200
100
150
308
100
159
100
150
500
Traising spacct
Training spects
Traising
(d) = 2
(c) h = 21
(f) = 22
Figure 5: Reweighted-RNN RRNN: Average mean square error between the original and reconstructed frames training epoches on the training and the validation sets with different network widths h (a CS rates is 0.2, 3).
200
200
Meaa sppeen aree
200
train bas
train Jost
Inala boos validation las
validudio
Moan opuere
validuion
100
300
200
160
159
308
100
159
209
100
Training
Traising
Traindng
(a)
(b)
(c) 3.
Mosn squueee enver
Mous squaree enter
trais
Ian
trai validatioo bas
validaden Box
validadon bat
100
Traising specis
Training speclo (c) 5.
Training specis
(d) d d= 4.
(f) d= 6.
Figure 6: Reweighted-Re 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 (a
CS rate is 0.2, h 210).
13

---

Under review as a conference paper at ICLR 2020
B THE PROXIMAL OPERATOR FOR PROBLEM ())
Proposition B.1. The proximal operator & x1 6. 2 g.h (u) in (6) for the reweighted f1-l minimization
problem 4) for which g(v) >ig/e)
+ >2g|u hdp given by
u g
A2 g,
+ d g + 2g < u < 00
h
h + A g g $ u 1 h +
A1
g
+
A2
Φx 21 8. (.)20(u)
Agg
g < ku <u<h+
A
//
A2 g
(19)
0,
A1 g 2g g
h1 g
u + g
A2 8.
-x < u < -
22
Aig g
2gg.
2 g + 3 g <
<
A g 2/ $ u
g + 2/
A1 2 (u)
+ A1 g
g.
1 g 2g g <
+ 2
(20)
c
h,
A g 2 8 <u < h
2t g + -
gg
x < < h 2g 2g
Proof. We compute the proximal operator &
2 gg (u)
(19) for h 2 it is similar for h < 0.
From
66)
8, 22 s. (u) is expressed by:
Aigg t (u) arg min { (p(() = A1 glol + glu te] + 2210
up3}
(21)
oER
We first consider the 0x(v)/00 E ((-20, 0), (0, h), (h, oo)], ; which ap((v) exists. Taking the derivative of (tv) in these intervals delivers
ap(c) À g sign(v) + A g sign (v h) + (v u), De
(22)
c
c
where sign(.) is sign function. When setting 0p( 0 to minimize s(v)), derive:
d g Ag g,
h < <0 0< < h
u
g + g.
(23)
+ Ag g + 2g
-00 <
From (1 and (23)
we have
Ag g 2gg
h+ -g u 0
+ 11 12 gn (1)
(w)=
u
d g + g,
= 2 < h
+
2g 22
2g
(24)
Ag g + beg.
-0 <u<<< 2
In the remaining range value of u, namely, - d g
d < u
Aig and h A g g S
S Àι g + dæ we prove that the minimum of (0)) (21) is obtained when e 0 and v respectively.
Let us rewrite v(v), which was defined in (1 as
A
A glu
(0)1) = g |||
h|
+
|: u|
(25)
2
By applying the inequality la - bl 2 |a| -
16).
where b E R.
to (25)
we obtain:
\ glul +
A₂
1
1
((u)=
c g
glhh
+
,
vu +
2 2²
c
2
1
A
|a||
g
+ g
[u]
gl
+ 25d 2
(26)
A For
21
b2 g. from (26) (pt) is minimal when u = 0, due to d Al
2g
0.
14

---

Under review as a conference paper at ICLR 2020
Similarly, for h+ Ag 2g S S h+ gg A2g, i... 2g Ag h $
A1 g
A2 g. we have
A1
A2
1 n)2 (27)
(Q()= 2 g/u - Ni|
-
g/ +
g/
N2| +
hi)2 -Iu - hilu ng
+
2
2
A
2/u hi
g
+
|u -
+ 2
(r-
h)2
glbl + (m-
From (27) (v) is minimal when h, since
An 2 g + 22
|u hl 2 0. Combining these results
with the result in (24) we conclude the proof.
C GENERALIZATION AND DEEP UNFOLDING RNNS
C.I GENERALIZATION ERROR BOUND DEFINITION
Notations. Let p(d) R" + R be the function computed by a d-layer network with weight parameters W. The network ((d) maps an input sample x; E IR" (from an input space X') to an output y; _² (from an output space V). i... y; f (x.). Let S denote a training set of size m, i.c., S = (x.,,,)) H and E (-xs),)>s( denote an expectation over (x,, y,) from S. The set S is drawn i.i.d. from distribution D, denoted S ~ DDm,, over a space
X' x y. Let F be a (class) set of functions. Let f: : F x 2 + E denote the loss function and o F = { 2(f.2)
F).
We define the true loss and the empirical (training) loss by (D(f) and Lg (f), respectively, follows:
[D( Bxx,y.)DD [< (x)))))
(28)
and
Ls(f) Ex.,,)) (f(())), [
(29)
The generalization error, which is defined as a measure of how accurately a learned algorithm is able predict outcome values for unseen data, calculated by LD(f) Ls()).
Rademacher complexity. Let F be a hypothesis set of functions (neural networks). The empirical Rademacher complexity of F (Shalev-Shwartz & Ben-David 2014 for training sample S is defined as follows:
1
Rs(F)
E
sup JEF
(x.)
(30)
where e = (61. ); here e are independent uniformly distributed random (Rademacher) variables from [=1], according to IP(e; 1] IPle = -] 1/2.
The generalization error bound (Shale--Shwartz & Ben-David 2014) is derived based on the Rademacher complexity defined in the following theorem:
Theorem C.1. (Shalev-Shae Shwarez & Ben-David 2014 Theorem 26.5)
Assume that [(( < for all f E E and z. Then, for any 8 > 0, with probability at least ô,
2 log((4/))
LD(s) - Ls(J)= < 2 4n
(31)
m
It can be noted that the bound in (11) via the Rademacher complexity depends on the training set S, which makes it applicable number of learning problems, e.g., regression and classification, under given a loss function e.
C.2 NOTATION FOR DEEP UNFOLDED RNNs
In this subsection, we provide the required notation for the proposed reweighted-RNY model, 61- RNN,, and Sista-RNN, which will be used in the derivation of their respective generalization analysis.
The proposed reweighted-RNN. Let h, be the hidden states in layer evolving in time step t. We (1)
write the reweighted-RNN model recursively as h." W (h (b(_), xx) &(W (d) + and
h (9)
( xx) o6 @Wirhwu (h xx) + U.x.). where Φ is an activation function. The
(1) (d)
15

---

Under review as a conference paper at ICLR 2020
hidden state is updated shown in (9) The real-valued family of functions, Fa, R R + R. for the functions sw.u in layer d is defined by:
Fa. = { (1121 x+) + @ d.
p (h (b)"),)) x.) + x1) : ad | S Bd
(32)
where 0n 3t are nonnegative real-valued family of functions, Fi,t RR*h x I IR, for the functions {(1) fwu is defined by:
for layer I, where << 1 S d. layer 1, the
FI.e
x.) - o w TT b + xxx) [ an 1 s $
(33)
(0)) where a1, B1 nonnegative hyper-parameters. We denote the input layer as fwu h, h in particular, & 1. h² ho.
(d)
The & 6--4 RNN model (Le et al. 2019). The hidden state h," for f1-4 RNNN is updated as shown
(13) The real-valuee family of functions, Fa. Rh R for the function fw.u layer dehned by:
Fat ( + (( w. (h xx) of x,) Well S 02 | S 881
(34)
where (22 31 are nonnegative hyper-parameters for layer 1, where << S d. layer / 1, the <(1) real-valued family of functions, FI. IR* x R + R, for the functions fwu is defined by:
F = { (h x.) + 2
( wTwh (0) - of x,) ) [Wilk Sn, 11 S $3). (35)
where 0n,, B1 are nonnegative byper-parameters.
The Sista-RNN model
(Wisdom et 2017). The hidden state h.") in Sista-RNN is updated by:
W + UIx:):
1=1,
h2
(36)
W Weh, (1-1) U2 U2h 1> 1,
The real-valued family of functions, Fa. Ra RR" + R. for the functions fw. layer d is defined by:
Fd, = (1h + of w /wu (,)
(ld-1)
x,) + uf x + u un
W W2ll1,0 & az | I 8, | 2,00 S 32).
(37)
where 0:2, ,1, B2 nonnegative Sypeer-aaammter In layer = 1,
Fi, = (ail)) + @ (wiTh + ufxx): 1/1ill,, I a1, |||,,, s B1}.
(38)
where a1, 91 are nonnegative byper-parameters.
D PROOF OF THEOREM 3.
Proof. We consider the real-valued family of functions Fa.T: Rh x R IR for the functions ww. to update (dd
(dd)
(d) in layer d, time step T, defined
Far = xT) + (ww?) (d-11) , xT) + xfxx)) Walli,o S asi 12ll22 s S.
(39)
16

---

Under review as a conference paper at ICLR 2020
where Wa, Pg the corresponding rows from Wa, d, Ud, respectively, and aq 8t, with < 1 S d. are nonnegative syper-parameters For the first layer and the first time step, i.e., I 1, t 1, the real-valued family of functions, Fi,1 :R x RR + R, for the functions IWu is defined by:
Fi.1 = { (h), x1) #(w + x) |Will S an, 1 S 31).
(40)
where 01 31 nonnegative hyper-parannn prpee-parammters. We denote the input layer Sw hu at the first time step. From the definition of Rademacher complexity in (30) and the family of functions in (39) and (40) we obtain:
mMs(Fa.r
(41a)
E c
sup
Σ i=1
c
wT Twu (hr-1,4 (hr-1,; + uuxx.:))
Wil
|| Soa |ux]i
ci w wile 11 xT.i) + uf u(pee:))
$ log exp
sup Wul
A
Σ
((d-1)
X
<E(=1)"
swalisaa
||ua||] S8a
1 log E
m2
Es W W (hT (hT- Σ eT,
T (d-1)
m
sup Will
exp
=E(=1)m
wall Sod ||ulll S3a
(41b)
< log
E c
sup Wul walliSaa
exp
w W (hT (br-1,,67:))
A
1=1
sup exp SAa
uu XT,
(41c)
where À > 0 is an arbitrary parameter, Eq. (41b)
follows Lemma D.I for I-Lipschitz & long with
Inequality (62) and (41c) holds by Inequality (59)
For layer < s d and time step i, let us denote:
4 D =
sup Wul I|wil
exp
AA Σ
E
w/
Swil (etz4/hi-1.0 (hI-1, (()))))))...))
(1-1)
(42)
[u x )
sup
exp
Adi Σ
(43)
|| full:s S3:
1=1
where A is defined follows: Aa A|
π ag with 1 d 1, and Ag II Ok-
k=l+1
Following the Hölder's inequality in (58) in case of p = 1 and q = oc applied to w/ and
((-1) (D--1,,, (42) respectively, we get:
(d)
(44)
hr-
sup W.l
exp
daa
Σ 1=1
+ W W (h:-15; Xx.)) + U Ua-1X(:))
pld-2)
W Saa-1
(U-illli S8a-1
17

---

Under review as a conference paper at ICLR 2020
m Σ
Xx,)) + u _ 1) (012)
sup wul
exp
max Aoy
6 w W
ke (1,- .b)
m Aai Σ
sup w.ll
exp
W W. (h:-1.1 xt,s) + u u
(45)
Similarly, from (43)
we obtain:
m
AB4 AB cxt, 10e) S Sexp
m
m
A/4 1 sup exp
A
qu Xt.s
S exp
Agd Σ
||ul||
S.aa
i=1
(46)
m
where {T
argmax
Σ 6xx,,
1E(1..... (eE((. .
From (4lc)
and (46) we get:
mDis
(F.s(Farr)
1
log
E
sup
exp
Pad
Σ
1, Tiu (bT-1,;.T,;) + 1
2(d-2)
Wul
i=1
Wa-LeellSoa-1
S
+ A
GXTTimm
1=1
1
log
E
sup Will
1
WA- Wa--1eel1Saa.
||u 592-1
m
exp
A
w
Wi
(d-2) (hT-1,;, + - + AB3 Σ
i=1
+ exp
PD
w W W.24 (hy (hT X7.1) + T 1
(dd-2)
ABa
1=1
i=
+
-exp
Xad
E/
w 1.1 W. Wu (hr bT + u +
(d-2)
ABa
+
exp
Aaa
w 4
Wd-1kJ-W (hy 1s. u
(d-2)
ABa Σ
t=1
1
log
4
E
hy-11x7
(d-1)
(d-1))
xx
exp Bad
(47a)
X
c
X
1
log
4d-1
E
1x
(I)
1 (1)
exp
31
Σ
6,,
(47b)
1=2
d
1
log
1d11
E
exp
A
B:4i
Σ
sup
exp
A41
Σ
w
A
cE(#1)m m
||w
1=2
1=1
sup
cxp
X11
Σ
ci (uf:x::))
(47c)
i=l
18

---

Under review as a conference paper at ICLR 2020
d
log
4d-1
E8
exp
A (>
Br41)
Σ
exari
sup
exp
Ado
Σ
e
1.1
Wul
1=2
1=1
1=1
||wall Sau
Lu ||| S.0a
m
exp
1
Σ
GxTT
(47d)
1 log
$
4th
E cE(11)
exp
1
Br A1
Σ
A
1=1
1=1
sup
exp
AAa
Σ
w pld-1) will
(hr 22, X1-15) + x
(47e)
W 14
wwll WolliSod
u SB2
where 47a) holds by inequality (59) and (47b) follows by repeating the process from layer d 1 to
layer for time step T. Furthermore, (47c) obtained as the beginning of the process for time step
T and 47d) follows inequality (58)
Proceeding by repeating the above procedure (7e) from time step T to time step we get:
(Far(F
1
AJ
log )
E
exp
A
Σ
B1
exrri
exp
Σ
ho
mm
1=1
i=1
(48)
m Σ echoo
Let us denote μ argmax
from (48)
we have:
kk
(Fa(Faa))
1
AT 1
))
X
log
4uT
=E(=1)m
E
exp
B141)
Ao
exp
AAg
Σe
b,
1=1
1=1
i=1
2dT log
1
exp { {>(>)))
(A)
Ag' 1
m
log
E.
3r
x
21
cE(+13m
Ao -
1=1
1=1
2
eep
AA
egho.
2dT
log
d Σ 3r4,)
A/
m Σ
log
E
exp
2X
X
2X
mE{+11m
No -
1-1
1=1
m
+
log
exp
2A12 T
Σ
(49a)
21
cE(111m
1=1
2dT log 2
1
A5 - Σ
log
E cE(11)m
exp
21
Brd1)
X
21
Ao
1=1
1=1
h
+
log
exp
2x T Σ
chho.t
(49b)
21
/=1
1=1
2dT log
1
771
d
AT
log
exp 2A
Σ
31
X
2X
(=
Ao
#=1
1
log
ΣI
II
m
EE
exp
2A45 exho.s
2)
(=(1)
i=1
19

---

Under review as a conference paper at ICLR 2020
2dT log?
1
d
A3 -
log
Σ
exp
21
Σ
3r41)
3r.5.
X
2X
2
to
J=1
1=1
1=1
A7"
+
exp
2X
BrA1)
2
Ao
h
+
1
log
Σ
II
exp
224h hos
+ 2
exp
- 1-21/hho.
2X
2
1=1
2dT
log
2 AAg -1 1 2 Σ Tiis
log
exp
21
Σ
B1411)
A
2X
Au -
/=1
1=1
+
1 log
Σ
exp
2x²
Σ
m
(49c)
2x
5=1
2dT log 2
log
2
( 110 - 1 2
logh
X
Σ
B(Ai)
mBx +
+ >A m mollool
2\
Ao
21
1=1
2dT log + log In log Vh
+ A
Be41)
)
2
mB² x + 1 m bb (49d) -1 Ao -
2
A
where (49a) follows inequality (61) and (49b) holds by replacing with Σ²= and Σ}= respectively,
In addition. followss (60) and [49d) obtained by the following definition: At time step f,
define X, E IR I a matrix composed of m columns from the m input vectors {x,.i)7 we also
detine
X 12,00
max
Σ x? 1 S VmBx, representing the maximum of the ---norms
of the rows of matrix X,, and |loolooo = max |bo.sk- 3
Choosing A
2dT log 2+lug vitlog via
we achieve the upper bound:
4 Bra))
A1 NO-T
mB2+15 millblll.
2(4dT log + log n + logh)
(1 B1)1
2 2(AAT 1 Ao -1 11
-1)
Rs(Far) <
B& + 13T
m
(50)
It can be noted that (s(.a.)) in (50) is derived for the real-valued functions Fa.T- For the vector- valued functions Fa. RR x R" + Rd (in Theorem 3.1. we apply the contraction lemma (Lemma[..] D.I) 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 1-Lipschitz loss function and from Theorem C.T Lemma D.I
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 al. (2018) or PAC-Bayes theory
[see SpectralRNN in Zhang et al. [. 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, of FastRNN is updated as follows:
h; = o ((Whh-1 + Ux.)
h, ah, bhe-1,
(51)
20

---

Under review as a conference paper at ICLR 2020
where 0 a, I are trainable parameters parameterized by the sigmoid function. Under the assumption that + = 1, the Rademacher complexity (sFFr) of the class Fr FastRNN (Kusupati et al. 2018). with | ar. | S ßr, and ||, 2|2 I B, is given by
2a
(1 a(2aF 1)) 1))=+111 a(2ar -11 1)
Rs
B3p
(52)
m
Alternatively, under the additional assumption that S 122p-1177" the bound in Kusupati al. (2018) becomes:
2a vm
2a(2ar -
Rs(Fr) S
B3g
(53)
(2aF-) -1)
SpectraIRNN (Zhang et al. 2018). The hidden state h, and output ye E R of SpectralRNN are computed as:
h: 0 Wh + Ux,)
Y, h
(54)
where Y RR The generalization error in Zhang al. 2018) derived for classification
problem. For any 8 > 0, > O, with probability > ó over training set S of size the generalization error (Zhang et al. 2018) of SpectraIRNN bounded by
(V
B (n(()
W + JUE + | In 3
(55)
where ( max W 2 max 0
1} max Y 112 1} and max(n, (n, Rly h).
Reweighted-RNN Based on Theorem 3.1 under the assumption that the initial hidden state hg = 0, the Rademacher complexity of reweighted RNN with d = 1 is bounded
4T log n + log (V23, af - Bx
Rs(Fir) &
(56)
We observe that the bound of SpectraIRNN (55) depends on T whereas the bound of FastRNN
either grows exponentially with 7 (52) is proportional T (53) Our bound (56) depends on
vT, given that the second factor in (56) only dependent on the norm constraints on, 81 and the input training data; meaning that is tighter than those of SpectraIRNN and FastRNN in terms of the number time steps.
D.2 BACKGROUND 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 p-Lisschitz functions.
Lemma D.I. (Shalev-Shwariz & Ben-David 2014 Lemma 26.9 Contraconn lemma)
Let F be set of functions, F {f : X R). and II,... &m p-Lipschitz functions, namely, (a) (B)) S pla for all a, 3 E for some p > For any sample set S of m points X1, X1, E X, let ( (x)) ((((x))) Then,
1
sup
c (xx)
<
P E
sup (xi) SEF 1=1
(57)
Mee(+1) o
fEF
MeE(+1)
m
alternatively, ( o < p
where denotes $ (x11),.... Dm (xm) ) for Proposition -ööldrr'ss inequality)
Proposition D.2. Mohri al. Let p.g. 9 2 1 be conjugate:
2018
Then, for all x,y E R".
||x yll < ||x|eelyll
(58)
with the equality when lyal 1x 11 for all [1.
21

---

Under review as a conference paper at ICLR 2020
Supporting inequalities:
(i) If A, B are sets of positive real numbers, then:
sup(AB) - sup(A) (B).
(59)
Given IR, we have:
exp(x) exp((=2) x]
I exp(x2222)
(60)
(iii) Let X and Y be random variables, the Cauchy- Bawuuhy-Bunyakkvsky-SSaeo Schwaarz inequality gives:
([[XY])² s E[X²] -E[Y"]
(61)
(iv) If db is convex function, the Jensen's inequality gives:
(E[[) - (X)(
(62)
E ADDITIONAL EXPERIMENTS
We test model 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 28 gray-scale image with a label from 9. We the reweighted-RNy
along with a softmax for category classification. We 256 hidden units for the reweighted-RNN. We consider two scenarios: the first where the pixels of each MNIST image 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. (a) (for pixel MNIST) and Fig. 7bb (for permuted pixel MNIST).
= 5 layers and
Aceurccy 1%6
Accuracy [%)
60
20
0
10
20
30
40
10
20
40
50
Training epochs
Training epochs
(a) Pixel MNIST.
(b) Permuted pixel MNIST.
Figure 7: Reweighted-RNe RNN on the (a) MiXeI-MNIST classification and (b) permuted pixel MNIST classification: Average classification accuracy training epoches the validation set.
square error
0.20
0.25
0.15
Criss saleopy
3..20
0.10
0.10
0.05
0.05
0.00
0.00
50
Training epochs
Training epochs
(a) Adding task.
(b) Copy task.
Figure 8: Geweighted-RNN on the (a) adding task with average mean square error and the (b) copy lask with average cross entropy vs. training epoches on the validation set.
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 entries of 1 and the
22

---

Under review as a conference paper at ICLR 2020
remaining entries of O, in which the first entry of 1 is randomly located in the first half of the sequence and the second entry of is randomly located in the second half. The output is the sum the two entrie of the first sequence, where located in the same posisions of the entries of 1 in the second sequence. We also use the reweighted-RNN with = 5 layers and = 256 hidden units for the input sequences of length T 300. Fig. [(a) shows the mean square versus training epoches on the validation set.
Copy task. We consider input sequence A A22000 (Zhang et al. 2018), where {as. ag). ... , Ig are uniformly sampled from {ao, ... (07) j. 40 dg, and the remaining 2; are set ag. The purpose of this task is to copy Zo. Fy to the end of the output sequence y A 7 given a time lag T', i.c., +VT+10,-
9r+119 = {Zo. ..., 2z9 and the remaining ys are equal to ag. layers and h 256 hidden units for the input sequences of time lag T = 100. Fig. 8(b) shows the cross entropy versus training epoches on the validation set.
We set the reWeighted-RNN
23


Reviews:
[{"review_id": "r1e_OXit9S", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Authors proposed a deep RNN via unfolding reweighted l1-l1 minimization, where reweighted l1-l1 minimization algorithms are applied to a video task. \nOverall, 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.\n\nMajor points:\nSection 1:\n-\tFirst 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.\nSection 2:\n-\tIt is hard to get how parameter g in Eq. (3) derives. \nSection 3:\n-\tHow to build network depth d for the network? A figure should be required.\nSection 4:\n-\tEven 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. \n-\tIn Table 3, how did you set LSTM deeper? Is it a stacked LSTM?\n-\tExisting 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.\n\nAppendix:\n-\tIt would be helpful for readers to show interpretabilities of the model additionally. For example, visualizing features from each RNN model would be beneficial.\n\nMinor points:\n-\tAfter introduction of unfolding reweighted l1-l1 minimization, how did the computational cost increase compared to previous l1-l1 minimization?\n-\tIn Section3, for easiness to readers, it may be good to briefly summarize how does the predictor’s generalizability and Rademacher complexities relate.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "ByebhFEatH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nStrength:\nThis 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. \n\nWeakness:\nThe effectiveness of the reweighted L1-L1 minimization method should be better explained and evaluated. It is not clear why the reweighted L1-L1 regularization is better than the L1-L1 regularization. In addition, the experimental evaluation does not support this claim well. The authors should compare the baseline method which uses the  L1-L1 regularization in their framework instead of directly comparing the proposed algorithm with [Le et al., 2019] as there exist differences in the algorithm design. This is an important baseline. \n\nAs claimed by the authors, the proposed reweighted-RNN has different sets of {W_l;U_l} for each hidden layer. This will definitively increase the model size when the depth increases. The authors should clarify whether the performance gains due to the only use of large model parameters. \n\nOverall, this paper proposes an effective reweighted-RNN model based on the solver of a reweighted L1-L1 minimization. Theoretical analysis and experimental results are provided. I would be willing to increase the score if these problems are solved in the authors’ response. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1e9hGLn5r", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nI recommend the paper to be accepted for mainly two reasons. First, they derive a tighter generalization bound for deep RNNs; Second, the experiment results align with the theory and show the continuous improvements when increasing the depth of RNNs.\n\nQuestions:\n1. How is the computation complexity of the proposed method when compared with other methods? Will the reweighting l1-l1 norm significantly increase the computation time?\n2. The experiments show that increasing the depth and/or width of the networks yields better performance, however, is there a boundary for such performance gain? For example, if the depth continues increasing, will the proposed method suffer the similar problem as other methods (performance does not improve or even degrade)?\n3. As the MOVING MNIST dataset is from a relatively simple and special domain, is it possible to reproduce the similar performance gain on other more realistic datasets?\n4. Are there any known limitations of the proposed method?", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a novel RNN algorithm based on unfolding a reweighted L1-L1 minimization problem. Authors derive the generalization error bound which is tighter than existing methods. 
All reviewers appreciate the theoretical contributions of the paper, particularly the derivation of generalization error bounds. However, at a higher-level, the overall idea is incremental because RNN by unfolding L1-L1 minimization problem (Le+,2019) and reweighted L1 minimization (Candes+,2008) are both known techniques. The proposed method is essentially a simple combination of them and therefore the result seems somewhat obvious. Also, I agree with reviewers that some experiments are not deep enough to support the theory. For example, for over-parameterization (large model parameters) issue, one can compare the models with the same number of parameters and observe how they generalize. 
Overall, this is the very borderline paper that provides a good theoretical contribution with limited conceptual novelty and empirical evidences. As a conclusion, I decided to recommend rejection but could be accepted if there is a room.

Decision: Reject