# Sample Complexity Bounds for Recurrent Neural Networks with Application to Combinatorial Graph Problems

arXiv: https://arxiv.org/abs/1901.10289 · HTML: https://mlsanity.com/paper/1901.10289/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jan 2019.

## Built on by (most cited first, 2 of 2)

- [Framing RNN as a kernel method: A neural ODE approach](https://mlsanity.com/paper/2106.01202/) (2021)
- [Spectral Pruning for Recurrent Neural Networks](https://mlsanity.com/paper/2105.10832/) (2021)

## Abstract (arXiv)

Learning to predict solutions to real-valued combinatorial graph problems promises efficient approximations. As demonstrated based on the NP-hard edge clique cover number, recurrent neural networks (RNNs) are particularly suited for this task and can even outperform state-of-the-art heuristics. However, the theoretical framework for estimating real-valued RNNs is understood only poorly. As our primary contribution, this is the first work that upper bounds the sample complexity for learning real-valued RNNs. While such derivations have been made earlier for feed-forward and convolutional neural networks, our work presents the first such attempt for recurrent neural networks. Given a single-layer RNN with a rectified linear units and input of length b, we show that a population prediction error of varepsilon can be realized with at most tildeO(a4b/varepsilon2) samples. We further derive comparable results for multi-layer RNNs. Accordingly, a size-adaptive RNN fed with graphs of at most n vertices can be learned in tildeO(n6/varepsilon2), i.e., with only a polynomial number of samples. For combinatorial graph problems, this provides a theoretical foundation that renders RNNs competitive.