English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Learning to predict solutions to real-valued combinatorial graph problemspromises efficient approximations. As demonstrated based on the NP-hard edgeclique cover number, recurrent neural networks (RNNs) are particularly suitedfor this task and can even outperform state-of-the-art heuristics. However, thetheoretical framework for estimating real-valued RNNs is understood onlypoorly. As our primary contribution, this is the first work that upper boundsthe sample complexity for learning real-valued RNNs. While such derivationshave been made earlier for feed-forward and convolutional neural networks, ourwork presents the first such attempt for recurrent neural networks. Given asingle-layer RNN with $a$ rectified linear units and input of length $b$, weshow that a population prediction error of $\varepsilon$ can be realized withat most $\tilde{\mathcal{O}}(a^4b/\varepsilon^2)$ samples. We further derivecomparable results for multi-layer RNNs. Accordingly, a size-adaptive RNN fedwith graphs of at most $n$ vertices can be learned in$\tilde{\mathcal{O}}(n^6/\varepsilon^2)$, i.e., with only a polynomial numberof samples. For combinatorial graph problems, this provides a theoreticalfoundation that renders RNNs competitive.

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