Efficient and Minimax Optimal In-context Nonparametric Regression with Transformers

We study in-context learning for nonparametric regression with $\alpha$-Hölder smooth regression functions, for some $\alpha>0$. We prove that, with $n$ in-context examples and $d$-dimensional regression covariates, a pretrained transformer with $\Theta(\log n)$ parameters and $\Omega(n^{2\alpha/(2\alpha+d)}\log^3 n)$ pretraining sequences can achieve the minimax optimal rate of convergence $O(n^{-2\alpha/(2\alpha+d)})$ 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.

We study the problem of learning nonparametric regression functions in-context using transformers. We show that a transformer can efficiently approximate local polynomial estimators using $\Theta(\log n)$ parameters, thus a pretrained transformer is able to achieve the minimax optimal rate for $\alpha$-Hölder regression functions with $\Omega\bigl(n^{2\alpha/(2\alpha+d)}\log^3 n\bigr)$ pretraining sequences.