$O(n)$ Connections are Expressive Enough: Universal Approximability of
  Sparse Transformers
  Recently, Transformer networks have redefined the state of the art in many
NLP tasks. However, these models suffer from quadratic computational cost in
the input sequence length $n$ to compute pairwise attention in each layer. This
has prompted recent research into sparse Transformers that sparsify the
connections in the attention layers. While empirically promising for long
sequences, fundamental questions remain unanswered: Can sparse Transformers
approximate any arbitrary sequence-to-sequence function, similar to their dense
counterparts? How does the sparsity pattern and the sparsity level affect their
performance? In this paper, we address these questions and provide a unifying
framework that captures existing sparse attention models. We propose sufficient
conditions under which we prove that a sparse attention model can universally
approximate any sequence-to-sequence function. Surprisingly, our results show
that sparse Transformers with only $O(n)$ connections per attention layer can
approximate the same function class as the dense model with $n^2$ connections.
Lastly, we present experiments comparing different patterns/levels of sparsity
on standard NLP tasks.
