One-Layer Transformer Provably Learns One-Nearest Neighbor In Context

Transformers have achieved great success in recent years. Interestingly, transformers have shown particularly strong in-context learning capability - even without fine-tuning, they are still able to solve unseen tasks well purely based on task-specific prompts.