mlsanityData to 14 Oct 2026

Minimax Rates for Learning Pairwise Interactions in Attention-Style Models

arXiv 2510.11789 ↗First posted 13 Oct 2025stat.ML cs.LG math.PRcited by 0

Not on the map. Why?

Abstract (arXiv)

We study the convergence rate of learning pairwise interactions in single-layer attention-style models, where tokens interact through a weight matrix and a nonlinear activation function. We prove that the minimax rate is M^-frac2β2β+1, where M is the sample size and β is the H"older smoothness of the activation function. Importantly, this rate is independent of the embedding dimension d, the number of tokens N, and the rank r of the weight matrix, provided that rd ≤ (M/log M)^frac12β+1. These results highlight a fundamental statistical efficiency of attention-style models, even when the weight matrix and activation are not separately identifiable, and provide a theoretical understanding of attention mechanisms and guidance on training.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 40 of its 64 references that are in the map. First posted on arXiv 13 Oct 2025.

Builds on

40 of 64 references.

References · 40

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2018Neural Ordinary Differential Equationscited by 3,779
  4. 2023Efficient Streaming Language Models with Attention Sinkscited by 2,186
  5. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 2,022
  6. 2020Linformer: Self-Attention with Linear Complexitycited by 1,474
  7. 2022Transformers learn in-context by gradient descentcited by 732
  8. 2017Nonparametric regression using deep neural networks with ReLU activation functioncited by 433
  9. 2024Massive Activations in Large Language Modelscited by 294
  10. 2023A mathematical perspective on Transformerscited by 164
  11. 2023The emergence of clusters in self-attention dynamicscited by 140
  12. 2021Sinkformers: Transformers with Doubly Stochastic Attentioncited by 138
28 more
  1. 2021SOFT: Softmax-free Transformer with Linear Complexitycited by 128
  2. 2020Infinite attention: NNGP and NTK for deep attention networkscited by 121
  3. 2023A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexitycited by 77
  4. 2024Attention Score is not All You Need for Token Importance Indicator in KV Cache Reduction: Value Also Matterscited by 73
  5. 2024Theory, Analysis, and Best Practices for Sigmoid Self-Attentioncited by 64
  6. 2024Active-Dormant Attention Heads: Mechanistically Demystifying Extreme-Token Phenomena in LLMscited by 56
  7. 2024Asymptotic theory of in-context learning by linear attentioncited by 55
  8. 2023On the Role of Attention in Prompt-tuningcited by 50
  9. 2024Bridging the Divide: Reconsidering Softmax and Linear Attentioncited by 48
  10. 2018Nonparametric inference of interaction laws in systems of agents from trajectory datacited by 44
  11. 2021Sparse Attention with Linear Unitscited by 41
  12. 2023What can a Single Attention Layer Learn? A Study Through the Random Features Lenscited by 40
  13. 2024Emergence of meta-stable clustering in mean-field transformer modelscited by 39
  14. 2023On the Optimization and Generalization of Multi-head Attentioncited by 37
  15. 2022SimA: Simple Softmax-free Attention for Vision Transformerscited by 32
  16. 2021Redesigning the Transformer Architecture with Insights from Multi-particle Dynamical Systemscited by 31
  17. 2024A phase transition between positional and semantic learning in a solvable model of dot-product attentioncited by 30
  18. 2019Learning interaction kernels in heterogeneous systems of agents from multiple trajectoriescited by 25
  19. 2020Learning interaction kernels in stochastic systems of interacting particles from multiple trajectoriescited by 25
  20. 2024Nonlocal Attention Operator: Materializing Hidden Knowledge Towards Interpretable Physics Discoverycited by 18
  21. 2024Attention layers provably solve single-location regressioncited by 17
  22. 2023Deep Neural Networks for Nonparametric Interaction Models with Diverging Dimensioncited by 15
  23. 2024High-dimensional learning of narrow neural networkscited by 12
  24. 2025Fundamental limits of learning in sequence multi-index models and deep attention networks: High-dimensional asymptotics and sharp thresholdscited by 12
  25. 2020Maximum likelihood estimation of potential energy in interacting particle systems from single-trajectory datacited by 10
  26. 2021Escaping the Gradient Vanishing: Periodic Alternatives of Softmax in Attention Mechanismcited by 7
  27. 2020On the coercivity condition in the learning of interacting particle systemscited by 2
  28. 2023Optimal minimax rate of learning nonlocal interaction kernelscited by 1

Built on by

Not cited yet.