Efficient and Minimax Optimal In-context Nonparametric Regression with Transformers
This work proves that Transformers can achieve minimax optimal nonparametric regression rates with Θ(log n) parameters, requiring Ω(n^{2α/(2α+d)} log^3 n) pretraining sequences.
Key Findings
Methodology
The paper demonstrates that pretrained Transformers, by implementing kernel-weighted polynomial bases and employing gradient descent, can efficiently approximate local polynomial estimators. Specifically, with Θ(log n) parameters and Ω(n^{2α/(2α+d)} log^3 n) pretraining sequences, the model attains the minimax convergence rate of O(n^{-2α/(2α+d)}) in mean squared error. The approach leverages linear attention to simulate local polynomial fitting, significantly reducing parameter and data requirements compared to prior works. The theoretical analysis combines approximation theory with empirical process bounds to establish the optimality of the method.
Key Results
- The proposed Transformer achieves the minimax rate of O(n^{-2α/(2α+d)}) with parameter complexity Θ(log n) and pretraining sequences Ω(n^{2α/(2α+d)} log^3 n), outperforming previous models requiring Θ(n^{d/(2α+d)}) parameters and Ω(n^{(2α+d)/(2α+d)} log n) sequences.
- Constructing the kernel-weighted polynomial basis enables the Transformer to approximate local polynomial estimators, reducing the parameter burden while maintaining statistical optimality.
- Empirical experiments on simulated data confirm the theoretical predictions, showing error rates matching the minimax bounds and demonstrating the efficiency of the approach.
Significance
This work advances the theoretical understanding of deep learning models in nonparametric statistics, establishing that Transformers can achieve optimal convergence rates with minimal parameters and data. It addresses longstanding challenges in high-dimensional nonparametric regression, offering a scalable and theoretically grounded solution. The results have broad implications for the deployment of large pretrained models in statistical inference, signal processing, and high-dimensional data analysis, potentially transforming how complex models are trained and applied in practice.
Technical Contribution
The core technical innovation lies in proving that Transformers with Θ(log n) parameters can approximate local polynomial estimators via kernel-weighted bases and gradient descent. This reduces the parameter complexity from previous Θ(n^{d/(2α+d)}) to logarithmic scale, while maintaining minimax optimality. The paper introduces a novel approximation theory for Transformers, combining neural network approximation capabilities with classical statistical estimators, and provides rigorous bounds on the excess risk using empirical process theory. This bridges the gap between deep learning approximation theory and statistical optimality in nonparametric regression.
Novelty
This is the first work to rigorously demonstrate that Transformers can achieve the minimax optimal convergence rate in nonparametric regression under α-Hölder smoothness with only Θ(log n) parameters. Unlike prior methods requiring polynomially many parameters, this approach leverages kernel-based approximations and gradient descent, significantly reducing model complexity. The theoretical guarantees and approximation framework are novel contributions that push the boundary of deep learning's statistical understanding.
Limitations
- The analysis assumes linear attention; extending results to softmax or ReLU attention involves additional technical challenges. Practical training dynamics and convergence guarantees remain open questions.
- The theoretical results rely on α-Hölder smoothness; real-world functions may not satisfy such regularity, affecting applicability.
- While parameter and sequence complexity are reduced, large-scale pretraining still demands substantial computational resources, limiting immediate deployment in resource-constrained environments.
Future Work
Future research should explore the extension to nonlinear attention mechanisms, analyze training dynamics and convergence in practice, and validate the approach on real-world datasets with complex functions. Additionally, integrating adaptivity to unknown smoothness levels and extending to high-dimensional manifolds will broaden applicability.
AI Executive Summary
This paper addresses a fundamental challenge in nonparametric regression—achieving optimal convergence rates with minimal model complexity. Traditional methods like local polynomial estimators are statistically optimal but computationally intensive, especially in high dimensions. Recent deep learning approaches, particularly Transformer architectures, have shown promise but often require a large number of parameters and extensive pretraining, limiting scalability.
The authors propose a novel theoretical framework demonstrating that pretrained Transformers, equipped with linear attention and simple feed-forward layers, can approximate local polynomial estimators efficiently. By implementing a kernel-weighted polynomial basis within the Transformer, they show that only Θ(log n) parameters and Ω(n^{2α/(2α+d)} log^3 n) pretraining sequences suffice to attain the minimax optimal rate of O(n^{-2α/(2α+d)}). This marks a significant reduction compared to previous models, which needed polynomially many parameters and sequences.
The core technical insight involves constructing a Transformer that simulates the weighted least squares solution of local polynomial fitting via gradient descent, leveraging the approximation power of neural networks for polynomials and the efficiency of linear attention. Theoretical proofs rigorously establish the approximation quality and statistical optimality, supported by empirical simulations confirming the model's effectiveness.
This work bridges deep learning and classical statistics, providing a scalable, theoretically grounded approach for high-dimensional nonparametric regression. It opens pathways for deploying large pretrained models in statistical inference tasks, with potential extensions to nonlinear attention mechanisms and real-world data applications. Despite some limitations in training dynamics and assumptions on smoothness, the results mark a major step toward efficient, minimax-optimal deep learning estimators in high-dimensional settings.
Deep Analysis
Background
近年来，Transformer架构在自然语言处理和计算机视觉中取得巨大成功，推动了深度学习的发展。学界对Transformer的理论理解逐渐深入，尤其在模型逼近能力和泛化性能方面。早期研究如Vaswani等（2017）提出了注意力机制，随后多项工作探索其在参数估计、分类和回归中的潜力。Kim等（2024）利用多项式基逼近非参数回归，Shen等（2025）证明Transformer能逼近Nadaraya–Watson估计器。尽管如此，现有方法普遍依赖大量参数和预训练序列，限制了实际应用的规模和效率。
Core Problem
非参数回归在高维和光滑性不足的场景中，传统方法如局部多项式估计虽达最优速率，但参数需求庞大，难以扩展到大规模数据。Transformer作为强大的函数逼近器，其潜力未被充分挖掘。现有理论多依赖复杂模型参数，限制了其在实际中的应用。如何在保证最优收敛速率的同时，降低参数和数据需求，成为亟待解决的问题。
Innovation
本研究的核心创新在于：1）证明Transformer可以高效逼近局部多项式估计器，利用核加权多项式基和梯度下降实现参数效率提升；2）参数复杂度由Θ(n^{d/(2α+d)})降至Θ(log n)，预训练序列数由Ω(n^{(2α+d)/(2α+d)} log n)减至Ω(n^{2α/(2α+d)} log^3 n)，大幅降低了训练成本；3）提出线性注意力机制模拟局部拟合，为深度学习在统计学中的应用提供理论基础。
Methodology
- �� 构建核加权多项式基，利用ReLU神经网络逼近多项式，确保逼近误差为O(1/nc)。
- �� 设计Transformer架构，通过多层线性注意力和前馈网络模拟局部多项式估计的参数优化过程。
- �� 利用梯度下降在Transformer中实现最小二乘解，避免矩阵求逆，提升效率。
- �� 证明Transformer参数有限，逼近误差可控，确保在α-Hölder空间达到最优收敛速率。
- �� 通过覆盖数分析，界定模型复杂度，确保泛化能力。
Experiments
采用模拟数据集，函数由随机Fourier级数生成，维度d=3，光滑指数α=3，噪声标准差σ=0.01。模型架构为线性注意力、嵌入维度de=256、FFN宽度dffn=1024、L=12层。训练采用AdamW优化，迭代5万步，采样40个随机函数，验证误差与理论一致。对比传统局部多项式估计和其他Transformer模型，验证参数效率和收敛速度。
Results
实验显示，本文模型在不同样本量n（15至35）下，误差均优于基线，误差降低至最优极限，参数数目仅为Θ(log n)，预训练序列数为Ω(n^{2α/(2α+d)} log^3 n)，实现了理论预期。与Kim等（2024）和Shen等（2025）相比，参数和数据需求大幅减少，验证了模型的高效逼近能力。
Applications
该方法可应用于大规模统计推断、信号处理和高维数据分析，尤其在数据有限或计算资源受限场景中表现优越。预训练Transformer可作为非参数估计的高效工具，满足工业界对快速、准确的模型需求。
Limitations & Outlook
模型依赖于α-Hölder光滑假设，实际中可能面临非光滑或复杂函数的挑战。训练过程中梯度优化可能受非凸性影响，实际效果受限于优化算法的性能。未来需结合非线性注意力机制，优化训练动态，扩展到更复杂的函数空间。
Plain Language Accessible to non-experts
想象你在厨房里做菜，传统的方法就像用大锅煮一锅汤，虽然可以做出不错的味道，但需要很多食材和时间。而新方法像是用一个智能厨师，只用少量食材，经过巧妙的调配，就能做出和大锅一样的美味。这里的‘厨师’就是Transformer，它通过学习和模仿局部的调味技巧（局部多项式估计），用很少的参数就能做出高质量的“菜”。这个厨师还会不断学习，变得越来越厉害，能在不同的菜谱中灵活应对。这样，不仅节省了材料和时间，还能做出更精细、更符合需求的菜肴。
ELI14 Explained like you're 14
想象你在学校里学习数学，老师教你用一种特别的魔法（叫Transformer）来猜答案。以前，要学会这个魔法需要很多练习和很多材料（参数和数据），才能猜得准。而这篇论文告诉我们，这个魔法其实可以变得很聪明，只用很少的材料（参数）和少量练习（预训练序列），就能猜出正确答案。它就像一个聪明的机器人，能通过观察一些例子，快速学会如何解决新问题。它用一种叫“局部多项式”的魔法技巧，模仿老师的教法，然后用梯度下降这个“学习”方法，不断调整自己，直到猜得和老师一样准。这意味着我们可以用更少的资源，得到更好的结果，就像用少量的练习就能成为数学天才一样。
Glossary
Hölder光滑 (Hölder smoothness)
描述函数在某区域内的连续性和光滑程度，满足特定的Hölder条件。技术上指函数的偏导数满足特定的变化界限。
论文中假设回归函数属于α-Hölder空间，以保证局部多项式估计的最优收敛速率。
局部多项式估计器 (Local Polynomial Estimator)
一种非参数回归方法，通过在点邻域内拟合多项式，估算目标函数值。技术上是加权最小二乘问题。
论文中用作理论基准，Transformer逼近的目标即为局部多项式估计器。
线性注意力 (Linear Attention)
一种注意力机制，将注意力计算线性化，减少复杂度，便于逼近和优化。
论文中用以模拟局部拟合，保证参数效率和逼近能力。
α-Hölder空间 (α-Hölder Space)
函数空间，包含满足特定光滑条件的函数，光滑指数为α。
假设回归函数属于此空间，以实现最优收敛速率。
Open Questions Unanswered questions from this research
- 1 当前模型在非光滑或高噪声环境下的表现尚未充分验证，未来需研究其鲁棒性和泛化能力。
- 2 训练动态和优化算法的收敛性分析仍不完善，影响实际应用的可行性。
- 3 如何在更复杂的函数空间中保持参数和样本效率，是未来的重要研究方向。
Applications
Immediate Applications
高维非参数回归分析
可用于金融、医疗等领域的高维数据建模，利用预训练Transformer实现快速、准确的非参数估计，减少样本和计算成本。
信号处理与时间序列预测
在信号分析中，Transformer可作为局部拟合工具，有效处理噪声和非线性关系，提升预测精度。
Long-term Vision
统计推断与大数据分析
未来Transformer将成为统计学中的核心工具，支持大规模非参数推断、模型选择和不确定性量化，推动智能数据分析的普及。
Abstract
We study in-context learning for nonparametric regression with $α$-Hölder smooth regression functions, for some $α>0$. We prove that, with $n$ in-context examples and $d$-dimensional regression covariates, a pretrained transformer with $Θ(\log n)$ parameters and $Ω\bigl(n^{2α/(2α+d)}\log^3 n\bigr)$ pretraining sequences can achieve the minimax optimal rate of convergence $O\bigl(n^{-2α/(2α+d)}\bigr)$ in mean squared error. Our result requires substantially fewer transformer parameters and pretraining sequences than previous results in the literature. This is achieved by showing that transformers are able to approximate local polynomial estimators efficiently by implementing a kernel-weighted polynomial basis and then running gradient descent.