# Provable In-Context Learning of Nonlinear Regression with Transformers

arXiv: https://arxiv.org/abs/2507.20443 · HTML: https://mlsanity.com/paper/2507.20443/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 46 references that are in the map.
- First posted on arXiv 28 Jul 2025.

## Builds on (most cited first, 30 of 41)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Explanation of In-context Learning as Implicit Bayesian Inference](https://mlsanity.com/paper/2111.02080/) (2021)
- [Transformers learn in-context by gradient descent](https://mlsanity.com/paper/2212.07677/) (2022)
- [What Can Transformers Learn In-Context? A Case Study of Simple Function Classes](https://mlsanity.com/paper/2208.01066/) (2022)
- [What learning algorithm is in-context learning? Investigations with linear models](https://mlsanity.com/paper/2211.15661/) (2022)
- [A Survey on Visual Transformer](https://mlsanity.com/paper/2012.12556/) (2020)
- [Trained Transformers Learn Linear Models In-Context](https://mlsanity.com/paper/2306.09927/) (2023)
- [Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection](https://mlsanity.com/paper/2306.04637/) (2023)
- [Towards a Definition of Disentangled Representations](https://mlsanity.com/paper/1812.02230/) (2018)
- [Long-context LLMs Struggle with Long In-context Learning](https://mlsanity.com/paper/2404.02060/) (2024)
- [Many-Shot In-Context Learning](https://mlsanity.com/paper/2404.11018/) (2024)
- [Why Can GPT Learn In-Context? Language Models Implicitly Perform Gradient Descent as Meta-Optimizers](https://mlsanity.com/paper/2212.10559/) (2022)
- [One Step of Gradient Descent is Provably the Optimal In-Context Learner with One Layer of Linear Self-Attention](https://mlsanity.com/paper/2307.03576/) (2023)
- [Self-Adaptive In-Context Learning: An Information Compression Perspective for In-Context Example Selection and Ordering](https://mlsanity.com/paper/2212.10375/) (2022)
- [Birth of a Transformer: A Memory Viewpoint](https://mlsanity.com/paper/2306.00802/) (2023)
- [AMMUS : A Survey of Transformer-based Pretrained Models in Natural Language Processing](https://mlsanity.com/paper/2108.05542/) (2021)
- [What and How does In-Context Learning Learn? Bayesian Model Averaging, Parameterization, and Generalization](https://mlsanity.com/paper/2305.19420/) (2023)
- [The Evolution of Statistical Induction Heads: In-Context Learning Markov Chains](https://mlsanity.com/paper/2402.11004/) (2024)
- [How Transformers Learn Causal Structure with Gradient Descent](https://mlsanity.com/paper/2402.14735/) (2024)
- [In-Context Convergence of Transformers](https://mlsanity.com/paper/2310.05249/) (2023)
- [Disentangled Representation Learning](https://mlsanity.com/paper/2211.11695/) (2022)
- [How Do Transformers Learn Topic Structure: Towards a Mechanistic Understanding](https://mlsanity.com/paper/2303.04245/) (2023)
- [Training Dynamics of Multi-Head Softmax Attention for In-Context Learning: Emergence, Convergence, and Optimality](https://mlsanity.com/paper/2402.19442/) (2024)
- [Battle of the Backbones: A Large-Scale Comparison of Pretrained Models across Computer Vision Tasks](https://mlsanity.com/paper/2310.19909/) (2023)
- [Transformers Implement Functional Gradient Descent to Learn Non-Linear Functions In Context](https://mlsanity.com/paper/2312.06528/) (2023)
- [Is In-Context Learning in Large Language Models Bayesian? A Martingale Perspective](https://mlsanity.com/paper/2406.00793/) (2024)
- [Asymptotic theory of in-context learning by linear attention](https://mlsanity.com/paper/2405.11751/) (2024)
- [A Review of Deep Learning Techniques for Speech Processing](https://mlsanity.com/paper/2305.00359/) (2023)
- [ICLR: In-Context Learning of Representations](https://mlsanity.com/paper/2501.00070/) (2024)

## Built on by (most cited first, 4 of 4)

- [Bayesian Optimality of In-Context Learning with Selective State Spaces](https://mlsanity.com/paper/2602.17744/) (2026)
- [Why LLMs Fail at Causal Discovery and How Interventional Agents Escape](https://mlsanity.com/paper/2605.27567/) (2026)
- [To Theoretically Understand Transformer-Based In-Context Learning for Optimizing CSMA](https://mlsanity.com/paper/2508.09146/) (2025)
- [Demonstrations, CoT, and Prompting: A Theoretical Analysis of ICL](https://mlsanity.com/paper/2603.19611/) (2026)

## Abstract (arXiv)

The transformer architecture, which processes sequences of input tokens to produce outputs for query tokens, has revolutionized numerous areas of machine learning. A defining feature of transformers is their ability to perform previously unseen tasks using task specific prompts without updating parameters, a phenomenon known as in-context learning (ICL). Recent research has actively explored the training dynamics behind ICL, with much of the focus on relatively simple tasks such as linear regression and binary classification. To advance the theoretical understanding of ICL, this paper investigates more complex nonlinear regression tasks, aiming to uncover how transformers acquire in-context learning capabilities in these settings. We analyze the stage-wise dynamics of attention during training: attention scores between a query token and its target features grow rapidly in the early phase, then gradually converge to one, while attention to irrelevant features decays more slowly and exhibits oscillatory behavior. Our analysis introduces new proof techniques that explicitly characterize how the nature of general non-degenerate L-Lipschitz task functions affects attention weights. Specifically, we identify that the Lipschitz constant L of nonlinear function classes as a key factor governing the convergence dynamics of transformers in ICL. Leveraging these insights, for two distinct regimes depending on whether L is below or above a threshold, we derive different time bounds to guarantee near-zero prediction error. Notably, despite the convergence time depending on the underlying task functions, we prove that query tokens consistently attend to prompt tokens with highly relevant features at convergence, demonstrating the ICL capability of transformers for unseen functions.