Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This is an interesting and very well-written paper. I read the paper carefully but I don’t have sufficient expertise to determine whether all the proof steps are correct.

This paper builds on recent works giving generalization bounds on RNNs.

The primary contribution is that they are able to bound the generalization error for RNNs without a dependence on the network size parameters d and m.

Their proof is roughly as follows:
1. They decompose the RNN + ReLU activation into the sum of a linear network and difference terms. This step is key because it lets you treat each term independently when estimating the Rademacher complexity.
2. The linear network term can be bounded directly with their Fisher-Rao norm.
3. They make a second decomposition: the difference term can be written as a sum of simpler terms
4. For the simpler terms, their Rademacher complexity can be bounded independently using matrix-1 norm. Using the matrix-1 norm instead of the spectral norm means their bounds won’t depend on the network size parameters.
5. Then they combine these bounds to give the Rademacher complexity bounds for RNNs.
6. Lastly, they combine the Rademacher complexity bound with Kuznetsov et al 2015’s multiclass margin bound to give the generalization bound.

The downside to their generalization bound is that it requires the covariance matrix of the input data must be positive definitive, and it explodes when the smallest eigenvalue is close to zero.

Their second contribution attempts to address these downsides. They prove another generalization bound for RNNs when training with random noise, which has the effect of increasing the term containing the smallest eigenvalue of the input covariance matrix.

They remark on several empirical phenomena that are consistent with their results:
- Correlation of features in the input data makes it harder for RNNs to generalize
- Weight decay could help by decreasing the relevant gradient terms in their bounds
- Gradient clipping could help when the smallest eigenvalue of the input covariance is very small

Their third contribution is a single experiment. This contribution is fairly weak and the practical value of their theoretical work would be much more convincing if they were to put more effort into this section.
- They use IMDB data set (50k movie reviews + binary sentiment classification task)
- They add Gaussian noise to the input data with four different values.
- They plot the generalization error, which is the difference between the test error without noise and the training error with noise

Specific comments to improve their experiment section:
- I’m confused by the following sentence: “generalization errors … for different combinations of L and \sigma_epsilon are shown in Figure 1.” However, in Figure 1 I only see different values of sigma. I don’t see anything about using various values for L. This should be clarified.
- Figure 1 draws linear interpolation between data points - there’s no evidence for those interpolations. It should be reported as a scatter plot, preferably with error bars.
- If space limitations prevent reporting the experiment results more rigorously, I would prefer to see the experiment results reported in an appendix, with a brief comment on their significance in the main paper.
review_title: Official Blind Review #4

final_score: rating: 6: Weak Accept
review_content: In this paper, the authors investigate the topic of theoretical generalizability in recurrent networks. Specifically, they extend a generalization bound using matrix 1-norm and the Fisher-Rao norm, proving the effectiveness of adding noise to input data for generalizability. These bounds have no dependence on the size of networks being investigated. The authors also propose a technique for representing RNNs as a decomposition into a sum of linear networks with a difference term, which allows for easier estimation of Rademacher complexity. The authors claim this is a representation that can be extended to other neural network architectures such as convolutional networks. 

This work has the potential to be of interest for the learning theory community on theoretical properties of recurrent neural networks.

One question I have for the authors: in the experiments on the IMDB dataset, the authors claim that the generalization error is worst at \sigma_{\epsilon} = 0, but it appears that the error is actually larger for \sigma_{\epsilon} = 0.4? 
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: This paper proposes a new generalization bound for vanilla RNN with ReLU activation in terms of matrix-1 norm and Fisher-Rao norm. This bound has no explicit dependence on the size of networks.

I am actually not familiar with the generalization theorem on RNN. Nevertheless, according to the demonstration of the authors, I can understand the results of the theorems in this paper. I think the analysis on the property of the covariance matrix of the input data are valuable. However, I still have some concerns as follows.

1.	It is interesting if the bound can be independent on the size of networks. However, according to the bounds, I find that the bounds still depend on the size of the network but implicitly. Thus, I understand why the authors claim that the bound they provide has no “explicit” dependence on the size of networks. Then what is the value of this contribution?
2.	In Section 3.4.1, the authors state that “Since the smaller eigenvalues usually contribute to high frequency components of the input signal, our bound suggests that high frequency information is often more difficult to generalize, which is consistent with intuition.”. Can the authors provide more explanations on this since I do not understand why smaller eigenvalues usually contribute to high frequency components of the input signal and what the frequency components of the input signal is. What is the formulation of the high frequency components of the input signal?
3.	It seems that ReLU activation is not widely used in RNN. Instead, tangent and sigmoid function are more prevalent. The authors mention in Conclusion that the extending the results to other variants of RNNs like LSTM and MGU might be an interesting topic for future research. I think the first extending work is to study the generalization bound of vanilla RNN with tangent or sigmoid activation. 


review_title: Official Blind Review #1

Meta-review: This paper presents a generalization bound for RNNs based on matrix-1 norm and Fisher-Rao norm. As the initial bound relies on non-signularity of input covariance, which may not always hold in practice, the authors present additional analysis by noise injection to ensure covariance is positive definite. Through the resulted bound, the paper discusses how weight decay and gradient clipping in the training can help generalization. There were some concerns raised by reviewers, including  rigorous report of the experiment results,  claims on generalization in IMDB experiment,  claims of no explicit dependence on the size of networks, and the relationship of small eigenvalues in input covariance to high frequency features. The authors responded to these and also revised their draft to address most of these concerns (in particular, authors added a new section in the appendix that includes additional experimental results). Reviewers were mainly satisfied with the responses and the revision, and they all recommend accept.

Decision: Accept (Poster)