Research map / Learning theory and algorithms / Kernels and regression theory
Transformers are Minimax Optimal Nonparametric In-Context Learners
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives statistical risk bounds for in-context learning of a deep ReLU network followed by one linear attention layer pretrained on nonparametric regression tasks, showing near-minimax optimal ICL rates in Besov and piecewise smooth classes plus joint n,T lower bounds.
Problem
Statistical foundations of in-context learning: how well a pretrained transformer (DNN plus linear attention) can estimate nonparametric regression functions in context, and how pretraining task count T and prompt length n govern the error.
Approach
Decompose the in-context risk into a DNN approximation error, an in-context generalization gap (depends on n) and a pretraining generalization gap (depends on T), then instantiate with ReLU DNN and transformer classes over Besov spaces to show minimax-optimal ICL rates; add information-theoretic lower bounds jointly in n and T.
Key results
- In the Besov setting, ICL achieves the minimax rate n^{-2α/(2α+d)} up to log factors when T ≳ n^{(2α+2d)/(2α+d)} and N ≍ n^{d/(2α+d)}.
- For a coarser basis, pretraining lets ICL beat the a priori rate n^{-2τ/(2τ+d)}, attaining n^{-2α/(2α+d)} log n for sufficiently large T.
- Information-theoretic lower bounds in n and T show ICL is jointly optimal in the large-T regime and suboptimal when T is small.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use sufficiently many pretraining tasks, T\gtrsim n^\frac{2\alpha+2d}{2\alpha+d}, with N\asymp n^\frac{d}{2\alpha+d} | DNN + linear attention ICL · Besov space | mean-squared risk: n^{-\frac{2\alpha}{2\alpha+d}} | Helped |
| Use sufficient pretraining and an anisotropic Besov representation | DNN + linear attention ICL · Anisotropic Besov space | mean-squared risk: n^{-\frac{2\widetilde{\alpha}}{2\widetilde{\alpha}+1}} | Helped |
| Learn an informative representation of the coarser basis during pretraining | DNN + linear attention ICL · Coarser basis | mean-squared risk: n^{-\frac{2\tau}{2\tau+d}} -> n^{-\frac{2\alpha}{2\alpha+d}}\log n | Helped |
| Use insufficient pretraining, T=O(1), rather than enough tasks to learn the representation | DNN + linear attention ICL · Coarser basis | mean-squared risk: n^{-\frac{2\alpha}{2\alpha+d}} -> n^{-\frac{2\tau}{2\tau+d}} | Hurt |
| Use a fixed non-adaptive representation when p<2 | ICL and other meta-learning methods · Besov space with p<2 | approximation error: N^{-\alpha/d+(1/p-1/2)_+} | Hurt |
Surprising findings
- When the number of pretraining tasks T is small relative to n, ICL is provably suboptimal, with rate degrading to T^{-α/(α+d)}-type behavior.
- For p<2 Besov spaces, non-adaptive in-context representations are bounded below by the Kolmogorov width, strictly worse than the minimax rate.
Limitations
- Model is restricted to a single linear attention layer with a DNN feature map and does not cover multi-layer transformer ICL behaviors.
- Upper and lower bounds are not tight in some regimes, notably the coarser-basis setting.
- Optimization of the pretraining objective is not analyzed; only the empirical risk minimizer is studied.
Experimental setup
Datasets: synthetic nonparametric regression tasks sampled from Besov and piecewise gamma-smooth function classes
Metrics: mean squared estimation risk (L2) minimax rate exponents
Baselines: linear attention meta-learning bounds non-adaptive linear approximation (Kolmogorov width)
Builds on: linear attention ICL analyses DNN minimax optimality results for Besov spaces Bernstein-type covering bounds for ERM
Closest papers by meaning
- In-Context Learning with Representations: Contextual Generalization of Trained Transformers (NeurIPS 2024 · similarity 0.94)
- How Do Nonlinear Transformers Learn and Generalize in In-Context Learning? (ICML 2024 · similarity 0.93)
- How Do Transformers Learn In-Context Beyond Simple Functions? A Case Study on Learning with Representations (ICLR 2024 · similarity 0.92)
- Towards Understanding How Transformers Learn In-context Through a Representation Learning Lens (NeurIPS 2024 · similarity 0.92)
- Technical Debt in In-Context Learning: Diminishing Efficiency in Long Context (NeurIPS 2025 · similarity 0.91)
- In-Context Learning through the Bayesian Prism (ICLR 2024 · similarity 0.91)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.