Fundamental Limits of Learning in Sequence Multi-Index Models and Deep Attention Networks: High-Dimensional Asymptotics and Sharp Thresholds
Abstract
In this manuscript, we study the learning of deep attention neural networks, defined as the composition of multiple self-attention layers, with tied and low-rank weights. We first establish a mapping of such models to sequence multi-index models, a generalization of the widely studied multi-index model to sequential covariates, for which we establish a number of general results. In the context of Bayes-optimal learning, in the limit of large dimension $D$ and proportionally large number of samples $N$, we derive a sharp asymptotic characterization of the optimal performance as well as the performance of the best-known polynomial-time algorithm for this setting –namely approximate message-passing–, and characterize sharp thresholds on the minimal sample complexity required for better-than-random prediction performance. Our analysis uncovers, in particular, how the different layers are learned sequentially. Finally, we discuss how this sequential learning can also be observed in a realistic setup.
Cite
Text
Troiani et al. "Fundamental Limits of Learning in Sequence Multi-Index Models and Deep Attention Networks: High-Dimensional Asymptotics and Sharp Thresholds." Proceedings of the 42nd International Conference on Machine Learning, 2025.Markdown
[Troiani et al. "Fundamental Limits of Learning in Sequence Multi-Index Models and Deep Attention Networks: High-Dimensional Asymptotics and Sharp Thresholds." Proceedings of the 42nd International Conference on Machine Learning, 2025.](https://mlanthology.org/icml/2025/troiani2025icml-fundamental/)BibTeX
@inproceedings{troiani2025icml-fundamental,
title = {{Fundamental Limits of Learning in Sequence Multi-Index Models and Deep Attention Networks: High-Dimensional Asymptotics and Sharp Thresholds}},
author = {Troiani, Emanuele and Cui, Hugo and Dandi, Yatin and Krzakala, Florent and Zdeborova, Lenka},
booktitle = {Proceedings of the 42nd International Conference on Machine Learning},
year = {2025},
pages = {60147-60182},
volume = {267},
url = {https://mlanthology.org/icml/2025/troiani2025icml-fundamental/}
}