mlsanityData to 14 Oct 2026

Transformers are Minimax Optimal Nonparametric In-Context Learners

arXiv 2408.12186 ↗First posted 22 Aug 2024stat.ML cs.LGcited by 37

Not on the map. Why?

Abstract (arXiv)

In-context learning (ICL) of large language models has proven to be a surprisingly effective method of learning a new task from only a few demonstrative examples. In this paper, we study the efficacy of ICL from the viewpoint of statistical learning theory. We develop approximation and generalization error bounds for a transformer composed of a deep neural network and one linear attention layer, pretrained on nonparametric regression tasks sampled from general function spaces including the Besov space and piecewise γ-smooth class. We show that sufficiently trained transformers can achieve -- and even improve upon -- the minimax optimal estimation risk in context by encoding the most relevant basis representations during pretraining. Our analysis extends to high-dimensional or sequential data and distinguishes the pretraining and in-context generalization gaps. Furthermore, we establish information-theoretic lower bounds for meta-learners w.r.t. both the number of tasks and in-context examples. These findings shed light on the roles of task diversity and representation learning for ICL.

Key facts. Cited by 37 papers in the map (data through 14 Oct 2026). Builds on 28 of its 46 references that are in the map. First posted on arXiv 22 Aug 2024.

Builds on

28 of 46 references.

References · 28

  1. 2020Language Models are Few-Shot Learnerscited by 32,419
  2. 2022Transformers learn in-context by gradient descentcited by 732
  3. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 715
  4. 2022What learning algorithm is in-context learning? Investigations with linear modelscited by 684
  5. 2016Error bounds for approximations with deep ReLU networkscited by 574
  6. 2017Nonparametric regression using deep neural networks with ReLU activation functioncited by 433
  7. 2015An Introduction to Matrix Concentration Inequalitiescited by 397
  8. 2023Trained Transformers Learn Linear Models In-Contextcited by 337
  9. 2023Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selectioncited by 298
  10. 2023Transformers learn to implement preconditioned gradient descent for in-context learningcited by 279
  11. 2020Few-Shot Learning via Learning the Representation, Provablycited by 214
  12. 2023One Step of Gradient Descent is Provably the Optimal In-Context Learner with One Layer of Linear Self-Attentioncited by 170
16 more
  1. 2018Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionalitycited by 162
  2. 2020Provable Meta-Learning of Linear Representationscited by 161
  3. 2023Pretraining task diversity and the emergence of non-Bayesian in-context learning for regressioncited by 146
  4. 2021Scatterbrain: Unifying Sparse and Low-rank Attention Approximationcited by 130
  5. 2023In-Context Convergence of Transformerscited by 115
  6. 2023How Many Pretraining Tasks Are Needed for In-Context Learning of Linear Regression?cited by 96
  7. 2023The unreasonable effectiveness of few-shot learning for machine translationcited by 91
  8. 2020Low-Rank Bottleneck in Multi-head Attention Modelscited by 89
  9. 2023How Do Transformers Learn In-Context Beyond Simple Functions? A Case Study on Learning with Representationscited by 75
  10. 2024Training Dynamics of Multi-Head Softmax Attention for In-Context Learning: Emergence, Convergence, and Optimalitycited by 74
  11. 2019Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov spacecited by 46
  12. 2024Transformers Learn Nonlinear Features In Context: Nonconvex Mean-field Dynamics on the Attention Landscapecited by 46
  13. 2024In-Context Learning of a Linear Transformer Block: Benefits of the MLP Component and One-Step GD Initializationcited by 33
  14. 2023Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Inputcited by 32
  15. 2019On the minimax optimality and superiority of deep neural network learning over sparse parameter spacescited by 24
  16. 2023Nonlinear Meta-Learning Can Guarantee Faster Ratescited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 6; 2025: 19; 2026: 12.

37 papers.

Sort:

By area:

  1. 2024Active-Dormant Attention Heads: Mechanistically Demystifying Extreme-Token Phenomena in LLMscited by 56
  2. 2024Large Language Models as Markov Chainscited by 35
  3. 2024Pretrained transformer efficiently learns low-dimensional target functions in-contextcited by 31
  4. 2025In-Context Learning Is Provably Bayesian Inference: A Generalization Theory for Meta-Learningcited by 22
  5. 2025Theory of Scaling Laws for In-Context Regression: Depth, Width, Context and Timecited by 16
  6. 2024Trained Transformer Classifiers Generalize and Exhibit Benign Overfitting In-Contextcited by 15
  7. 2025Understanding In-Context Learning on Structured Manifolds: Bridging Attention to Kernel Methodscited by 15
  8. 2025TabPFN: One Model to Rule Them All?cited by 14
  9. 2026Efficient and Minimax Optimal In-context Nonparametric Regression with Transformerscited by 7
  10. 2024In-Context Learning of Linear Systems: Generalization Theory and Applications to Operator Learningcited by 6
  11. 2025Hallucinations are inevitable but can be made statistically negligiblecited by 5
  12. 2025How to Train your Text-to-Image Model: Evaluating Design Choices for Synthetic Training Captionscited by 5
25 more
  1. 2025In-Context Learning of Linear Dynamical Systems with Transformers: Approximation Bounds and Depth-Separationcited by 4
  2. 2025Approximation Rates in Besov Norms and Sample-Complexity of Kolmogorov-Arnold Networks with Residual Connectionscited by 4
  3. 2025Optimal In-context Adaptivity and Distributional Robustness of Transformerscited by 4
  4. 2025When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspectivecited by 3
  5. 2025Transformers as Unsupervised Learning Algorithms: A study on Gaussian Mixturescited by 3
  6. 2025Optimization-Inspired Few-Shot Adaptation for Large Language Modelscited by 3
  7. 2026Understanding In-Context Learning for Nonlinear Regression with Transformers: Attention as Featurizercited by 3
  8. 2025Posterior Contraction for Sparse Neural Networks in Besov Spaces with Intrinsic Dimensionalitycited by 2
  9. 2025Review of Hallucination Understanding in Large Language and Vision Modelscited by 2
  10. 2024Provable optimal transport with transformers: The essence of depth and prompt engineeringcited by 1
  11. 2025On the Existence of Universal Simulators of Attentioncited by 1
  12. 2025Transformers are almost optimal metalearners for linear classificationcited by 1
  13. 2025Overfitting has a limitation: a model-independent generalization gap bound based on R'enyi entropycited by 0
  14. 2025Enhancing Privacy in Decentralized Min-Max Optimization: A Differentially Private Approachcited by 0
  15. 2025Shallow Neural Networks Learn Low-Degree Spherical Polynomials with Feature Learning by Learnable Channel Attentioncited by 0
  16. 2026Provable Target Sample Complexity Improvements as Pre-Trained Models Scalecited by 0
  17. 2026Demonstrations, CoT, and Prompting: A Theoretical Analysis of ICLcited by 0
  18. 2026Provable Data Scaling Law for Meta Learning via Complexity Minimizationcited by 0
  19. 2026Black-Box Assisted Regression: Phase Transitions and Minimax Optimalitycited by 0
  20. 2026A Unified Framework for In-Context Learning with Causal and Masked Language Modelscited by 0
  21. 2026Vector Search As Nearest Neighbor Matching: RAG-based Policy Learning in Causal Inferencecited by 0
  22. 2026Handover of In-Context Learning State Across Session Boundariescited by 0
  23. 2026The Illusion of Replacement: Rethinking Specialized Machine Learning Models in the Foundation Model Eracited by 0
  24. 2026Learn Your Own Thoughts: Abstract Token Curriculumcited by 0
  25. 2026Adaptive Mean Estimation by In-Context Learning: A Gradient-Flow Analysiscited by 0