On the Role of Noise in the Sample Complexity of Learning Recurrent Neural Networks: Exponential Gaps for Long Sequences
This work addresses the sample complexity challenge in learning recurrent neural networks, revealing that noise can dramatically improve efficiency, which is significant for machine learning practitioners dealing with long sequences, though it is incremental as it builds on existing theoretical frameworks.
The paper tackles the problem of PAC learning noisy recurrent neural networks for sequence classification, showing that adding Gaussian noise to neurons reduces sample complexity from an exponential dependence on sequence length T to a logarithmic one, specifically from Ω(wT) to O(w log(T/σ)).
We consider the class of noisy multi-layered sigmoid recurrent neural networks with $w$ (unbounded) weights for classification of sequences of length $T$, where independent noise distributed according to $\mathcal{N}(0,σ^2)$ is added to the output of each neuron in the network. Our main result shows that the sample complexity of PAC learning this class can be bounded by $O (w\log(T/σ))$. For the non-noisy version of the same class (i.e., $σ=0$), we prove a lower bound of $Ω(wT)$ for the sample complexity. Our results indicate an exponential gap in the dependence of sample complexity on $T$ for noisy versus non-noisy networks. Moreover, given the mild logarithmic dependence of the upper bound on $1/σ$, this gap still holds even for numerically negligible values of $σ$.