Can SGD Learn Recurrent Neural Networks with Provable Generalization?

However, due to the complexity raised by recurrent structure, they remain one of the least theoretically understood neural-network models. In this paper, we show that if the input labels are (approximately) realizable by certain classes of (nonlinear) functions of the input sequences, then using the vanilla stochastic gradient descent (SGD), RNNs can actually learn them efficiently, meaning that both the training time and sample complexity only scale polynomially with the input length (or almost polynomially, depending on the classes of non-linearity). We would like to thank Yingyu Liang and Zhao Song for very helpful conversations. Part of the work was done when Yuanzhi Li was visiting Microsoft Research Redmond. 1 Introduction Recurrent neural networks (RNNs) is one of the most popular models in sequential data analysis [25].When processing an input sequence, a recurrent neural network repeatedly and sequentially applies the same operation to each position of the input. The special structure of RNNs allows it to capture the dependencies among different points inside each sequence, which is empirically shown to be effective in many applications such as natural language processing[28], speech recognition [12] and so on. The recurrent structure in RNNs shows great power in practice, however, it also imposes great challenge in theory.