Transformer Learns Optimal Variable Selection in Group-Sparse Classification
Chenyang Zhang, Xuran Meng, Yuan Cao · 2025
Read Transformer Learns Optimal Variable Selection in Group-Sparse Classification by Chenyang Zhang, Xuran Meng, Yuan Cao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-08638.txt.
Introduction
Attention heads can learn to pick the right group of variables, Chenyang Zhang, Xuran Meng, and Yuan Cao prove in a 2025 paper. Their test task sorts data whose label depends on just one group among many. Transformers are famously strong yet poorly understood, so a clean case study helps.
A one-layer transformer trained by gradient descent learns to attend to the label-bearing group and ignore the rest, the proof shows. A well-pretrained unit then adapts to new tasks with few samples. The result gives a rare full account of how attention performs variable selection, a basic move inside many real models.
Catalog record
| CREATOR | Chenyang Zhang, Xuran Meng, Yuan Cao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 218 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-08638
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
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. 1 Introduction The Transformer architecture ( Vaswani et al., 2017 ) has emerged as one of the most popular models in the modern deep learning, demonstrating remarkable success across a wide range of real-world applications, including language processing and language modeling ( Vaswani et al., 2017 ; Radford et al., 2019 ; OpenAI, 2023 ) , computer vision ( Dosovitskiy et al., 2020 ; Rao et al., 2021 ) , and reinforcement learning ( Jumper et al., 2021 ; Chen et al., 2021 ; Janner et al., 2021 ) . Despite its empirical achievements, the underlying mechanisms of transformers remain poorly understood due to their complex architecture, especially the mechanism of the self-attention layers. As the core of the Transformer architecture, the attention mechanism has consistently been the primary focus of research aimed at understanding how Transformers work. Some empirical research ( Xu et al., 2019 ; Vig and Belinkov, 2019 ; Rao et al., 2021 ; Yao et al., 2021 ; Chen et al., 2022 ) demonstrated that the attention layer can effectively extract structure information by assigning different weights to different input tokens. To fully understand such property theoretically, researchers explore the expressive power of transformers across various aspects ( Edelman et al., 2022 ; Bai et al., 2024 ) . Edelman et al. (2022) study the capacity of single-head attention to approximate sparse function by presenting the covering-number of attention function class. Bai et al. (2024) demonstrate that the transformers can implement a broad class of standard machine learning algorithms in context with various data distributions. In addition to examining the expressive power of Transformers with custom-designed parameters, some recent studies have focused on analyzing the training dynamics of Transformers to determine whether these favorable properties can be attained using popular optimization algorithms in the deep learning community. Zhang et al. (2024b) provide a global convergence analysis of gradient flow on the linear regression in-context tasks, where they consider a linear layer for attention calculation. Huang et al. (2024) ; Siyu et al. (2024) extend this result to one-layer transformers with a softmax attention layer. Wang et al. (2024) ; Chen et al. (2024b) study the capacities of transformers to learn sparse linear regression tasks. Specifically, by exploring the optimization trajectory, Wang et al. (2024) show that one-layer transformers can effectively extract the positional information, and provide a rigorous convergence analysis. At the same time, fully-connected neural networks fail in the worst case. Chen et al. (2024b) study the mechanisms of multi-head attention, revealing that multi-head attention will exhibit a sparsity in multiple-layer transformers. All the preceding works focus on the regression tasks, and for the classification task, Jelassi et al. (2022) theoretically demonstrate that the one-layer vision transformer trained by gradient descent can converge on spatially structured data and the attention map exhibit patch association. Tarzanagh et al. (2023a) ; Tarzanagh et al. (2023b) prove that one-layer attention can converge in direction to the hard margin solution of SVM. Li et al. (2023a) provide a generalization error bound for vision transformers trained by stochastic gradient descent. Although these papers provide some insights into mechanisms of one-layer attention for classification tasks, their theoretical results rely on some specific initialization which is practically infeasible, or strong assumptions that input data follows some particular patterns or certain parameters of attention architecture remain fixed throughout the training. To further explore how transformers extract structure information in classification tasks, we consider a classic statistical problem with “group sparsity”. In this setting, input variables are generated from multiple groups, while the true label of this input is determined by variables from a single group. We investigate the properties of one-layer transformers trained by gradient descent on this data model. The major contributions of this paper can be summarized as follows: 1. We establish a tight global convergence analysis with a matching lower and upper bound for the population cross-entropy loss of a one-layer transformer trained by gradient descent (Theorem 3.2 ). All parameters in the one-layer transformer are jointly trained with the same learning rate from zero initialization, without imposing any prior knowledge of the desirable patterns of the parameters. Specifically, by precisely characterizing the global optimization trajectories of all trainable parameters, we decrypt the working mechanism of each component of the one-layer transformer for learning the “group sparse” data model. Our results theoretically verify that transformers can learn the optimal variable selections. 2. We demonstrate that the well pre-trained one-layer transformers on “group-sparse” inputs can be efficiently transferred to a downstream task sharing the same group sparsity pattern. Specifically, denote the number of variable groups as D , the dimension of variables in each group as d , and the downstream sample size as n . Then we show that the one-layer transformers fine-tuned by online-SGD on the downstream task can achieve \widetilde{O}\big(\frac{d+D}{n}\big) generalization error bound (Theorem 4.2 ). 3. We conduct numerical experiments, empirically show that training loss will converge, and verify our conclusions regarding the optimization trajectories of trainable parameters. Specifically, the sparsity of the attention score matrix empirically demonstrates that one-layer transformers can effectively learn the optimal variable selection. Additionally, we transfer the pre-trained one-layer transformers to downstream tasks, and empirically show that it can achieve a good generalization performance with a small sample size. All these empirical observations back up our theoretical findings. Notation. Given two sequences \{x_{n}\} and \{y_{n}\} , we denote x_{n}=O(y_{n}) if there exist some absolute constant C_{1}>0 and N>0 such that |x_{n}|\leq C_{1}|y_{n}| for all n\geq N . Similarly, we denote x_{n}=\Omega(y_{n}) if there exist C_{2}>0 and N>0 such that |x_{n}|\geq C_{2}|y_{n}| for all n>N . We say x_{n}=\Theta(y_{n}) if x_{n}=O(y_{n}) and x_{n}=\Omega(y_{n}) both holds. Besides, we denote x_{n}=o(y_{n}) if, for any \epsilon>0 , there exists some N(\epsilon)>0 such that |x_{n}|\leq\epsilon|y_{n}| for all n\geq N(\epsilon) , and we denote x_{n}=\omega(y_{n}) if y_{n}=o(x_{n}) . We use \widetilde{O}(\cdot) , \widetilde{\Omega}(\cdot) , and \widetilde{\Theta}(\cdot) to hide logarithmic factors in these notations respectively. Moreover, we denote x_{n}=\mathrm{poly}(y_{n}) if x_{n}=O(y_{n}^{D}) for some positive constant D , and x_{n}=\mathrm{polylog}(y_{n}) if x_{n}=\mathrm{poly}(\log(y_{n})) . For two scalars a and b , we denote a\vee b=\max\{a,b\} and a\wedge b=\min\{a,b\} . Finally, for any n\in\mathbb{N}_{+} , we use [n] to denote the set \{1,2,\cdots,n\} . 2 Additional related works Expressiveness of transformers. There has been a line of works studying the expressiveness of transformers. Yun et al. (2020) ;