When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspective
This work provides theoretical insights into when Transformers outperform classical architectures, which is significant for researchers in machine learning theory, though it is incremental as it builds on prior representational power studies.
The paper tackles the problem of comparing sample complexity across neural architectures by proving that Transformers can achieve sample complexity almost independent of sequence length in a sparse retrieval model, while feedforward and recurrent networks require more samples, with recurrent networks needing N^Ω(1) samples in some cases.
Theoretical efforts to prove advantages of Transformers in comparison with classical architectures such as feedforward and recurrent neural networks have mostly focused on representational power. In this work, we take an alternative perspective and prove that even with infinite compute, feedforward and recurrent networks may suffer from larger sample complexity compared to Transformers, as the latter can adapt to a form of dynamic sparsity. Specifically, we consider a sequence-to-sequence data generating model on sequences of length $N$, in which the output at each position depends only on $q$ relevant tokens with $q \ll N$, and the positions of these tokens are described in the input prompt. We prove that a single-layer Transformer can learn this model if and only if its number of attention heads is at least $q$, in which case it achieves a sample complexity almost independent of $N$, while recurrent networks require $N^{Ω(1)}$ samples on the same problem. If we simplify this model, recurrent networks may achieve a complexity almost independent of $N$, while feedforward networks still require $N$ samples. Consequently, our proposed sparse retrieval model illustrates a natural hierarchy in sample complexity across these architectures.