Research map / Learning theory and algorithms / Sample complexity
Transformers are almost optimal metalearners for linear classification
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.
Shows theoretically that a linear transformer trained by gradient descent (max-margin implicit bias) on random Gaussian-mixture classification tasks with a shared k-dimensional subspace learns to classify new tasks with O~(k/R~^4) in-context examples, nearly matching an oracle that knows the subspace and beating the d/R~^4 bound for single-task learners.
Problem
Whether transformers can act as metalearners for linear classification: adapt to new Gaussian-mixture tasks whose means lie in an unknown shared low-dimensional subspace using few in-context examples, without further training.
Approach
Analyze a convex linear-attention parameterization trained by GD on logistic/exponential loss; its max-margin limit is shown to behave like a projection onto the shared subspace followed by MLE averaging of in-context examples, giving sample complexity depending on k rather than d and with training size independent of d.
Key results
- Trained linear transformer achieves constant test error with O~(k/R~^4) in-context examples, versus Omega(d/R~^4) for any single-task learner.
- Matches the Omega(k/R~^4) lower bound for an optimal learner with access to the true subspace, up to log factors.
- Experiments (d=500, k=30, B=20000) show the linear transformer closely approaches projected MLE and outperforms full MLE and SVM.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| pretrain a linear transformer on related tasks with a shared low-dimensional subspace | Linear transformer · Gaussian mixture linear classification | in-context samples for small constant error: \Omega(d/\widetilde{R}^4) -> \widetilde{O}(k/\widetilde{R}^4) | Helped |
| pretrain a linear transformer on related tasks with a shared low-dimensional subspace | Linear transformer · Gaussian mixture linear classification | in-context samples for small constant error: \widetilde{O}(k/\widetilde{R}^4) vs. \Omega(k/\widetilde{R}^4) | No clear effect |
| use the trained linear transformer instead of full MLE or SVM | Linear transformer · Gaussian mixture linear classification | test accuracy | Helped |
| use the trained linear transformer instead of projected MLE | Linear transformer · Gaussian mixture linear classification | test accuracy | No clear effect |
| increase the signal strength R = tilde R | Linear attention models · Gaussian mixture linear classification | test accuracy | Helped |
Surprising findings
- Training requires only R = O~(1) rather than R = Omega(sqrt d) as in prior work, and B independent of d, so the transformer generalizes even when k = d.
Limitations
- Analysis restricted to a simplified linear attention with convex parameterization and fixed value/query entries, not softmax or multi-layer/multi-head models.
- Results hold up to polylogarithmic factors and for max-margin limit of GD rather than finite-time GD iterates.
- Requires assumptions on R, d and N (e.g., N >= C d/R^2) and large numbers of training tasks.
Experimental setup
Datasets: synthetic Gaussian mixture metatasks with shared k-dimensional subspace
Benchmarks: synthetic Gaussian mixture metalearning tasks
Metrics: test classification error in-context sample complexity
Baselines: Support vector machine maximum likelihood estimator (full) projected maximum likelihood estimator with true subspace
Builds on: implicit bias of gradient descent (max-margin) linear transformer in-context learning analyses Gaussian mixture minimax lower bounds
Closest papers by meaning
- On the Training Convergence of Transformers for In-Context Classification of Gaussian Mixtures (ICML 2025 · similarity 0.91)
- In-context Convergence of Transformers (ICML 2024 · similarity 0.90)
- Trained Transformer Classifiers Generalize and Exhibit Benign Overfitting In-Context (ICLR 2025 · similarity 0.89)
- How Do Nonlinear Transformers Learn and Generalize in In-Context Learning? (ICML 2024 · similarity 0.89)
- Pretrained Transformer Efficiently Learns Low-Dimensional Target Functions In-Context (NeurIPS 2024 · similarity 0.89)
- Transformer Learns Optimal Variable Selection in Group-Sparse Classification (ICLR 2025 · similarity 0.89)
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.