Efficient and Minimax Optimal In-context Nonparametric Regression with Transformers
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Transformers are Minimax Optimal Nonparametric In-Context Learners
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 view…
DiversityIn-Context LearningLearning TheoryRepresentation LearningAdversarial learning for nonparametric regression: Minimax rate and adaptive estimation
Despite tremendous advancements of machine learning models and algorithms in various application domains, they are known to be vulnerable to subtle, natural or intentionally crafted perturbations in future input data, kn…
regressionStandard Transformers Achieve the Minimax Rate in Nonparametric Regression with $C^{s,λ}$ Targets
The tremendous success of Transformer models in fields such as large language models and computer vision necessitates a rigorous theoretical investigation. To the best of our knowledge, this paper is the first work provi…
Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
A fundamental challenge in contextual bandits is to develop flexible, general-purpose algorithms with computational requirements no worse than classical supervised learning tasks such as classification and regression. Al…
Multi-Armed BanditsregressionTransfer Learning for Nonparametric Regression: Non-asymptotic Minimax Analysis and Adaptive Procedure
Transfer learning for nonparametric regression is considered. We first study the non-asymptotic minimax risk for this problem and develop a novel estimator called the confidence thresholding estimator, which is shown to …
regressionTransfer Learning