On the Provable Generalization of Recurrent Neural Networks

Abstract

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,...,X_L)$, previous works study to learn functions that are summation of $f({\beta }_l^T{X}_l)$ and require normalized conditions that $||X_l||\le \epsilon$ with some very small $\epsilon$ 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},...,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,..,l_N)-\min (l_1,..,l_N)$ is small, $f({\beta }^T[X_{l_1},...,X_{l_N}])$ will be learnable with the number iterations and samples scaling almost-polynomially in the input length $L$.

arXiv commentAccepted to Neurips 2021

References in corpus (15)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks
• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• On the Power of Over-parametrization in Neural Networks with Quadratic Activation
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• Gradient Descent Learns Linear Dynamical Systems
• On the Convergence Rate of Training Recurrent Neural Networks
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK