Lune

ICLR2025Top-tier venue

Transformer Learns Optimal Variable Selection in Group-Sparse Classification

Chenyang Zhang, Xuran Meng, Yuan Cao

Abstract

Transformers have demonstrated remarkable success across various applications. However, the success of transformers have not been understood in theory. In this work, we give a case study of how transformers can be trained to learn a classic statistical model with "group sparsity", where the input variables form multiple groups, and the label only depends on the variables from one of the groups. We theoretically demonstrate that, a one-layer transformer trained by gradient descent can correctly leverage the attention mechanism to select variables, disregarding irrelevant ones and focusing on those beneficial for classification. We also demonstrate that a well-pretrained one-layer transformer can be adapted to new downstream tasks to achieve good prediction accuracy with a limited number of samples. Our study sheds light on how transformers effectively learn structured data.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

7 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Transformers Trained via Gradient Descent Can Provably Learn a Class of Teacher Models cites Towards Understanding Transformers in Learning Random Walks
  • Transformers Trained via Gradient Descent Can Provably Learn a Class of Teacher Models cites Offline Reinforcement Learning as One Big Sequence Modeling Problem
  • Transformers Trained via Gradient Descent Can Provably Learn a Class of Teacher Models cites An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale
  • Transformers Trained via Gradient Descent Can Provably Learn a Class of Teacher Models cites Decision Transformer: Reinforcement Learning via Sequence Modeling
  • Transformers Trained via Gradient Descent Can Provably Learn a Class of Teacher Models cites DynamicViT: Efficient Vision Transformers with Dynamic Token Sparsification
  • Transformers Trained via Gradient Descent Can Provably Learn a Class of Teacher Models cites On the Robustness of Transformers against Context Hijacking for Linear Classification
  • Transformers Efficiently Perform In-Context Logistic Regression via Normalized Gradient Descent cites Transformers Trained via Gradient Descent Can Provably Learn a Class of Teacher Models
  • Transformers Efficiently Perform In-Context Logistic Regression via Normalized Gradient Descent cites Towards Understanding Transformers in Learning Random Walks
  • Transformers Efficiently Perform In-Context Logistic Regression via Normalized Gradient Descent cites Offline Reinforcement Learning as One Big Sequence Modeling Problem
  • Transformers Efficiently Perform In-Context Logistic Regression via Normalized Gradient Descent cites An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale
  • Transformers Efficiently Perform In-Context Logistic Regression via Normalized Gradient Descent cites DynamicViT: Efficient Vision Transformers with Dynamic Token Sparsification
  • Transformers Efficiently Perform In-Context Logistic Regression via Normalized Gradient Descent cites On the Robustness of Transformers against Context Hijacking for Linear Classification
  • Transformers Efficiently Perform In-Context Logistic Regression via Normalized Gradient Descent cites What Can Transformers Learn In-Context? A Case Study of Simple Function Classes
  • Towards Understanding Transformers in Learning Random Walks cites Offline Reinforcement Learning as One Big Sequence Modeling Problem
  • Towards Understanding Transformers in Learning Random Walks cites An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale
  • Towards Understanding Transformers in Learning Random Walks cites Decision Transformer: Reinforcement Learning via Sequence Modeling
  • Towards Understanding Transformers in Learning Random Walks cites DynamicViT: Efficient Vision Transformers with Dynamic Token Sparsification
  • Offline Reinforcement Learning as One Big Sequence Modeling Problem cites Decision Transformer: Reinforcement Learning via Sequence Modeling
  • Decision Transformer: Reinforcement Learning via Sequence Modeling cites An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale
  • DynamicViT: Efficient Vision Transformers with Dynamic Token Sparsification cites An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale
  • On the Robustness of Transformers against Context Hijacking for Linear Classification cites What Can Transformers Learn In-Context? A Case Study of Simple Function Classes
  • What Can Transformers Learn In-Context? A Case Study of Simple Function Classes cites An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale
  • High-Dimensional Analysis of Single-Layer Attention for Sparse-Token Classification cites An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers7

  1. High-Dimensional Analysis of Single-Layer Attention for Sparse-Token ClassificationNicholas Barnfield, Hugo Cui, Yue M. LuICLR 2026 · 8 citations
  2. On the Robustness of Transformers against Context Hijacking for Linear ClassificationTianle Li, Chenyang Zhang, Xingwu Chen, Yuan Cao et al.NeurIPS 2025 · 7 citations
  3. Transformers Efficiently Perform In-Context Logistic Regression via Normalized Gradient DescentChenyang Zhang, Yuan CaoICML 2026 · 1 citation
  4. Towards Understanding Transformers in Learning Random WalksWei Shi, Yuan CaoNeurIPS 2025 · 1 citation
  5. Transformers Trained via Gradient Descent Can Provably Learn a Class of Teacher ModelsChenyang Zhang, Qingyue Zhao, Quanquan Gu, Yuan CaoICLR 2026

Builds on35

  1. An Image is Worth 16x16 Words: Transformers for Image Recognition at ScaleAlexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn et al.ICLR 2021 · 21,477 citations
  2. Decision Transformer: Reinforcement Learning via Sequence ModelingLili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee et al.NeurIPS 2021 · 2,557 citations
  3. DynamicViT: Efficient Vision Transformers with Dynamic Token SparsificationYongming Rao, Wenliang Zhao, Benlin Liu, Jiwen Lu et al.NeurIPS 2021 · 1,343 citations
  4. Offline Reinforcement Learning as One Big Sequence Modeling ProblemMichael Janner, Qiyang Li, Sergey LevineNeurIPS 2021 · 950 citations
  5. What Can Transformers Learn In-Context? A Case Study of Simple Function ClassesShivam Garg, Dimitris Tsipras, Percy Liang, Gregory ValiantNeurIPS 2022 · 883 citations

Related papers

  1. How Transformers Utilize Multi-Head Attention in In-Context Learning? A Case Study on Sparse Linear RegressionXingwu Chen, Lei Zhao, Difan ZouNeurIPS 2024 · 19 citations
  2. Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets CannotZixuan Wang, Stanley Wei, Daniel Hsu, Jason D. LeeICML 2024 · 22 citations
  3. One-Layer Transformer Provably Learns One-Nearest Neighbor In ContextZihao Li, Yuan Cao, Cheng Gao, Yihan He et al.NeurIPS 2024 · 25 citations
  4. Dissecting the Interplay of Attention Paths in a Statistical Mechanics Theory of TransformersLorenzo Tiberi, Francesca Mignacco, Kazuki Irie, Haim SompolinskyNeurIPS 2024 · 12 citations
  5. Understanding Transformers for Time Series Forecasting: A Case Study on MOIRAIYu-Hsuan Wu, Yihan He, Yuan Cao, Jianqing Fan et al.ICLR 2026
Dusk over the sea between two cliffs drawn in fine vertical lines