  The multi-head attention layer is one of the key components of the
transformer architecture that sets it apart from traditional feed-forward
models. Given a sequence length $k$, attention matrices
$\mathbf{\Theta}_1,\ldots,\mathbf{\Theta}_m\in\mathbb{R}^{d\times d}$, and
projection matrices $\mathbf{W}_1,\ldots,\mathbf{W}_m\in\mathbb{R}^{d\times
d}$, the corresponding multi-head attention layer $F: \mathbb{R}^{k\times d}\to
\mathbb{R}^{k\times d}$ transforms length-$k$ sequences of $d$-dimensional
tokens $\mathbf{X}\in\mathbb{R}^{k\times d}$ via $F(\mathbf{X}) \triangleq
\sum^m_{i=1}
\mathrm{softmax}(\mathbf{X}\mathbf{\Theta}_i\mathbf{X}^\top)\mathbf{X}\mathbf{W}_i$.
In this work, we initiate the study of provably learning a multi-head attention
layer from random examples and give the first nontrivial upper and lower bounds
for this problem:
  - Provided $\{\mathbf{W}_i, \mathbf{\Theta}_i\}$ satisfy certain
non-degeneracy conditions, we give a $(dk)^{O(m^3)}$-time algorithm that learns
$F$ to small error given random labeled examples drawn uniformly from $\{\pm
1\}^{k\times d}$.
  - We prove computational lower bounds showing that in the worst case,
exponential dependence on $m$ is unavoidable.
  We focus on Boolean $\mathbf{X}$ to mimic the discrete nature of tokens in
large language models, though our techniques naturally extend to standard
continuous settings, e.g. Gaussian. Our algorithm, which is centered around
using examples to sculpt a convex body containing the unknown parameters, is a
significant departure from existing provable algorithms for learning
feedforward networks, which predominantly exploit algebraic and rotation
invariance properties of the Gaussian distribution. In contrast, our analysis
is more flexible as it primarily relies on various upper and lower tail bounds
for the input distribution and "slices" thereof.
