Dimension-Free Minimax Rates for Learning Pairwise Interactions in Attention-Style Models
Shai Zucker, Xiong Wang, Fei Lu, Inbar Seroussi
Abstract
We study the convergence rate of learning pairwise interactions in single-layer attention-style models, where tokens interact through a weight matrix and a non-linear activation function. We prove that the minimax rate is $M^{-\frac{2\beta}{2\beta+1}}$ with $M$ being the sample size, depending only on the smoothness $\beta$ of the activation, and crucially independent of token count, ambient dimension, or rank of the weight matrix. These results highlight a fundamental dimension-free statistical efficiency of attention-style nonlocal models, even when the weight matrix and activation are not separately identifiable and provide a theoretical understanding of the attention mechanism and its training.
BibTeX
@inproceedings{
zucker2026dimensionfree,
title={Dimension-Free Minimax Rates for Learning Pairwise Interactions in Attention-Style Models},
author={Shai Zucker and Xiong Wang and Fei Lu and Inbar Seroussi},
booktitle={The Fourteenth International Conference on Learning Representations},
year={2026},
url={https://openreview.net/forum?id=7Gfheg6seM}
}