mlsanityData to 14 Oct 2026

Learning on Transformers is Provable Low-Rank and Sparse: A One-layer Analysis

arXiv 2406.17167 ↗First posted 24 Jun 2024cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

Efficient training and inference algorithms, such as low-rank adaption and model pruning, have shown impressive performance for learning Transformer-based large foundation models. However, due to the technical challenges of the non-convex optimization caused by the complicated architecture of Transformers, the theoretical study of why these methods can be applied to learn Transformers is mostly elusive. To the best of our knowledge, this paper shows the first theoretical analysis of the property of low-rank and sparsity of one-layer Transformers by characterizing the trained model after convergence using stochastic gradient descent. By focusing on a data model based on label-relevant and label-irrelevant patterns, we quantify that the gradient updates of trainable parameters are low-rank, which depends on the number of label-relevant patterns. We also analyze how model pruning affects the generalization while improving computation efficiency and conclude that proper magnitude-based pruning has a slight effect on the testing performance. We implement numerical experiments to support our findings.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 37 of its 45 references that are in the map. First posted on arXiv 24 Jun 2024.

Builds on

37 of 45 references.

References · 37

  1. 2017Attention Is All You Needcited by 60,361
  2. 2020Language Models are Few-Shot Learnerscited by 32,419
  3. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  4. 2022Training language models to follow instructions with human feedbackcited by 15,971
  5. 2021LoRA: Low-Rank Adaptation of Large Language Modelscited by 14,380
  6. 2021Swin Transformer: Hierarchical Vision Transformer using Shifted Windowscited by 12,139
  7. 2023QLoRA: Efficient Finetuning of Quantized LLMscited by 3,418
  8. 2023Sparks of Artificial General Intelligence: Early experiments with GPT-4cited by 2,592
  9. 2015Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Codingcited by 2,329
  10. 2021Decision Transformer: Reinforcement Learning via Sequence Modelingcited by 1,546
  11. 2023SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shotcited by 1,121
  12. 2023A Simple and Effective Pruning Approach for Large Language Modelscited by 800
25 more
  1. 2020Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learningcited by 297
  2. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 261
  3. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  4. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 143
  5. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 142
  6. 2021Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learningcited by 119
  7. 2023In-Context Convergence of Transformerscited by 115
  8. 2023Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformercited by 102
  9. 2022Vision Transformers provably learn spatial structurecited by 93
  10. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  11. 2023How Do Transformers Learn Topic Structure: Towards a Mechanistic Understandingcited by 86
  12. 2023A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexitycited by 77
  13. 2023Transformers as Support Vector Machinescited by 74
  14. 2023Max-Margin Token Selection in Attention Mechanismcited by 58
  15. 2023Transformers learn through gradual rank increasecited by 52
  16. 2023JoMA: Demystifying Multilayer Transformers via JOint Dynamics of MLP and Attentioncited by 52
  17. 2023On the Role of Attention in Prompt-tuningcited by 50
  18. 2022A Theoretical Analysis on Feature Learning in Neural Networks: Emergence from Inputs and Advantage over Fixed Featurescited by 49
  19. 2024How Do Nonlinear Transformers Learn and Generalize in In-Context Learning?cited by 35
  20. 2022Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Samplingcited by 23
  21. 2023Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networkscited by 16
  22. 2024What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encodingcited by 14
  23. 2022On the Neural Tangent Kernel Analysis of Randomly Pruned Neural Networkscited by 9
  24. 2022Learning and generalization of one-hidden-layer neural networks, going beyond standard Gaussian datacited by 8
  25. 2024How does promoting the minority fraction affect generalization? A theoretical study of the one-hidden-layer neural network on group imbalancecited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 4; 2026: 2.

8 papers.

  1. 2025When is Task Vector Provably Effective for Model Editing? A Generalization Analysis of Nonlinear Transformerscited by 38
  2. 2024Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysiscited by 14
  3. 2025Subspace Networks: Scaling Decentralized Training with Communication-Efficient Model Parallelismcited by 12
  4. 2025Compression Barriers for Autoregressive Transformerscited by 5
  5. 2024On Generalisation Error Bounds for Transformerscited by 4
  6. 2025How Can Mamba Learn In Context with Outliers and Generalize Provably?cited by 2
  7. 2026Visual prompting reimagined: The power of the Activation Promptscited by 1
  8. 2026Transformers Learn the Optimal DDPM Denoiser for Multi-Token GMMscited by 0