On the Provable Generalization of Recurrent Neural Networks

Recurrent Neural Network (RNN) is a fundamental structure in deep learning. Recently, some works study the training process of over-parameterized neural networks, and show that over-parameterized networks can learn functions in some notable concept classes with a provable generalization error bound. In this paper, we analyze the training and generalization for RNNs with random initialization, and provide the following improvements over recent works:

1. For a RNN with input sequence $x=(X_1,X_2,\mathrm{.}\mathrm{.}\mathrm{.},X_L)$, previous works study to learn functions that are summation of $f({\beta }_l^T{X}_l)$ and require normalized conditions that $\mathrm{\mid }\mathrm{\mid }{X}_l\mathrm{\mid }\mathrm{\mid }\le ϵ$ with some very small $ϵ$ depending on the complexity of $f$. In this paper, using detailed analysis about the neural tangent kernel matrix, we prove a generalization error bound to learn such functions without normalized conditions and show that some notable concept classes are learnable with the numbers of iterations and samples scaling almost-polynomially in the input length $L$.
2. Moreover, we prove a novel result to learn N-variables functions of input sequence with the form $f({\beta }^T[X_{l_1},\mathrm{.}\mathrm{.}\mathrm{.},X_{l_N}])$, which do not belong to the “additive” concept class, i,e., the summation of function $f(X_l)$. And we show that when either $N$ or $l_0=\max (l_1,\mathrm{.}\mathrm{.},l_N)-\min (l_1,\mathrm{.}\mathrm{.},l_N)$ is small, $f({\beta }^T[X_{l_1},\mathrm{.}\mathrm{.}\mathrm{.},X_{l_N}])$ will be learnable with the number iterations and samples scaling almost-polynomially in the input length $L$.