This paper presents a provable learning algorithm for multi-head attention layers in transformers, along with matching lower bounds. The multi-head attention layer is a key component of the transformer architecture, which computes a weighted sum of a sequence of vectors based on their pairwise similarities after linear transformations. The authors focus on learning this layer from random examples, providing the first nontrivial upper and lower bounds for this problem. The algorithm works by first estimating the sum of projection matrices using correlations between input and output. It then uses these estimates to sculpt a convex body that approximates the affine hull of the attention matrices. This process involves generating linear constraints that are satisfied by the true attention matrices, allowing the algorithm to refine its estimates iteratively. The authors show that under certain non-degeneracy conditions, they can learn the multi-head attention layer to small error given random labeled examples drawn from a Boolean distribution. They also prove that exponential dependence on the number of heads is unavoidable in the worst case, providing computational lower bounds. The paper also discusses the challenges of learning multi-head attention layers compared to traditional feed-forward networks. Unlike feed-forward networks, which can be analyzed using moment-based techniques, multi-head attention layers require geometric, rather than algebraic, moment-based techniques. The authors show that the self-attention setting evades existing algorithmic approaches in deep learning theory and require new arguments. The paper provides a detailed technical overview of the algorithm, including the estimation of projection matrix sums, sculpting the affine hull, and extracting the span of the attention matrices. It also discusses the challenges of learning multi-head attention layers, including the need for large-margin attention patterns and the use of convex bodies to approximate the affine hull of the attention matrices. The authors conclude that their results open up new avenues for exploring computation-statistical tradeoffs for learning transformers. They also highlight the importance of understanding the learnability of transformers over domains that are structurally reminiscent of those that arise in practice, such as the discrete nature of tokens in language. The paper also discusses the challenges of learning deeper architectures and the potential benefits of modifying distributional assumptions or adding additional assumptions about the parameters of the transformer.This paper presents a provable learning algorithm for multi-head attention layers in transformers, along with matching lower bounds. The multi-head attention layer is a key component of the transformer architecture, which computes a weighted sum of a sequence of vectors based on their pairwise similarities after linear transformations. The authors focus on learning this layer from random examples, providing the first nontrivial upper and lower bounds for this problem. The algorithm works by first estimating the sum of projection matrices using correlations between input and output. It then uses these estimates to sculpt a convex body that approximates the affine hull of the attention matrices. This process involves generating linear constraints that are satisfied by the true attention matrices, allowing the algorithm to refine its estimates iteratively. The authors show that under certain non-degeneracy conditions, they can learn the multi-head attention layer to small error given random labeled examples drawn from a Boolean distribution. They also prove that exponential dependence on the number of heads is unavoidable in the worst case, providing computational lower bounds. The paper also discusses the challenges of learning multi-head attention layers compared to traditional feed-forward networks. Unlike feed-forward networks, which can be analyzed using moment-based techniques, multi-head attention layers require geometric, rather than algebraic, moment-based techniques. The authors show that the self-attention setting evades existing algorithmic approaches in deep learning theory and require new arguments. The paper provides a detailed technical overview of the algorithm, including the estimation of projection matrix sums, sculpting the affine hull, and extracting the span of the attention matrices. It also discusses the challenges of learning multi-head attention layers, including the need for large-margin attention patterns and the use of convex bodies to approximate the affine hull of the attention matrices. The authors conclude that their results open up new avenues for exploring computation-statistical tradeoffs for learning transformers. They also highlight the importance of understanding the learnability of transformers over domains that are structurally reminiscent of those that arise in practice, such as the discrete nature of tokens in language. The paper also discusses the challenges of learning deeper architectures and the potential benefits of modifying distributional assumptions or adding additional assumptions about the parameters of the transformer.