Transformers are Minimax Optimal Nonparametric In-Context Learners
<|reference_start|>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 viewpoint of statistical learning theory. We develop approximation and generalization error bounds for a transformer composed of a deep neural network and one linear attention layer, pretrained on nonparametric regression tasks sampled from general function spaces including the Besov space and piecewise $\gamma$-smooth class. We show that sufficiently trained transformers can achieve -- and even improve upon -- the minimax optimal estimation risk in context by encoding the most relevant basis representations during pretraining. Our analysis extends to high-dimensional or sequential data and distinguishes the \emph{pretraining} and \emph{in-context} generalization gaps. Furthermore, we establish information-theoretic lower bounds for meta-learners w.r.t. both the number of tasks and in-context examples. These findings shed light on the roles of task diversity and representation learning for ICL.<|reference_end|>
@article{kim2024transformers,
    title={Transformers are Minimax Optimal Nonparametric In-Context Learners},
    author={Juno Kim, Tai Nakamaki, Taiji Suzuki},
    journal={arXiv preprint arXiv:2408.12186},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.12186},
    primaryClass={stat.ML cs.LG}
}