A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexity

Hongkang Li, Meng Wang, Sijia Liu, Pin-yu Chen

TL;DR

This paper presents the first theoretical analysis of training a shallow Vision Transformer (ViT) using Stochastic Gradient Descent (SGD) for a classification task. The authors mathematically prove that SGD naturally drives the self-attention mechanism to become sparse, focusing strictly on label-relevant tokens while ignoring background noise. Furthermore, they establish a formal sample complexity bound, providing a theoretical foundation for why token pruning (sparsification) improves both computational efficiency and generalization.

What Problem Does This Paper Address?

While Vision Transformers (ViTs) have achieved massive empirical success, replacing Convolutional Neural Networks (CNNs) across numerous computer vision tasks, their theoretical foundations remain largely mysterious. Analyzing how ViTs learn is notoriously difficult due to the highly non-convex interactions across layers and the non-linear nature of the softmax activation function within the self-attention module.

Previous theoretical works either oversimplified the network (e.g., using Neural Tangent Kernels, which freeze feature learning during training) or failed to analyze generalization performance. This paper tackles a fundamental question: Under what conditions does a Transformer trained with SGD achieve satisfactory generalization? Specifically, it aims to quantify the sample complexity—the number of training samples required to achieve zero generalization error—and explain why empirical strategies like token pruning actually help networks generalize better.

Methods

The authors analyze a basic shallow ViT consisting of a single-head self-attention layer followed by a two-layer perceptron (MLP), trained using mini-batch SGD.

To model realistic data, they introduce a structured data model where an image is composed of multiple tokens (patches). These tokens are categorized into:

  1. Label-relevant tokens: Discriminative patterns that determine the true image label via a majority vote.
  2. Confusion tokens: Patterns associated with the opposing class.
  3. Label-irrelevant tokens: Background patterns or noise that do not affect the label.

The core technical novelty lies in their new analytical framework. Instead of freezing weights, they track the exact optimization dynamics of multiple weight matrices ($W_Q, W_K, W_V, W_O$) simultaneously. They successfully bound the highly non-linear softmax gradients by exploiting the underlying data structure, showing how SGD selectively scales up the magnitude of label-relevant features over time.

Datasets

The theoretical bounds were validated using two main setups:

  • Synthetic Datasets: Tokens generated from a Gaussian distribution centered around distinct orthonormal base patterns to precisely control variables like noise ($\tau$) and the fraction of label-relevant tokens ($\alpha_*$).
  • Image Classification Dataset (Modified CIFAR-10): To simulate label-irrelevant background noise and spurious correlations, the authors integrated resized CIFAR-10 images (as label-relevant patches) into noisy background images from the ImageNet "Plants" synset. Models were initialized using pre-trained weights from CIFAR-100.

Key Insights and Ideas

  • Emergent Attention Sparsity: The paper mathematically confirms a long-standing intuition: training naturally forces attention maps to become sparse. As SGD progresses, attention weights automatically concentrate on label-relevant tokens and drop to near-zero for background tokens.
Figure 4: Concentration of at- tention weights
  • The ViT Advantage over CNNs: The authors show that the self-attention layer drastically reduces sample complexity. For data where only a fraction ($\alpha_*$) of tokens are label-relevant, a ViT's sample complexity scales with $1/\alpha_*^2$, whereas a comparable CNN scales with $1/\alpha_*^4$. This represents a massive reduction in required data when dealing with cluttered or noisy images.
Figure 3: Comparison of ViT and CNN
  • The Blessing of Token Pruning: Token sparsification (removing patches during inference or training) is widely used to save compute. This paper provides the mathematical justification for it: if a pruning method successfully removes label-irrelevant or highly noisy tokens, it directly reduces the model's sample complexity and eliminates spurious correlations, boosting test accuracy.

Key Results

  • Zero Generalization Guarantee: The authors prove that under proper initialization, a shallow ViT trained with SGD achieves exactly zero generalization error with a probability of at least 0.99, given sufficient samples.
  • Sample Complexity Bounds: The required number of training samples $N$ is proven to be positively correlated with the token noise level ($\tau$), the initial model error ($\sigma$), and critically, the inverse fraction of label-relevant tokens ($\alpha_*^{-2}$).
  • Pruning Verification: Empirical results show that explicitly removing label-irrelevant or noisy tokens leads to a direct and significant decrease in test loss, validating their theoretical claims.
Impact of token sparsification on testing loss

Limitations and Future Work

As a pioneering theoretical work, the study focuses on a simplified architecture: a shallow ViT with a single attention head. While the authors provide brief sketches in the appendix on extending their work to multi-head attention, skip connections, and multi-class problems, a rigorous, fully realized analysis of deep, multi-layer, multi-head ViTs remains an open challenge for future research.

Summary updated

Abstract

Vision Transformers (ViTs) with self-attention modules have recently achieved great empirical success in many vision tasks. Due to non-convex interactions across layers, however, theoretical learning and generalization analysis is mostly elusive. Based on a data model characterizing both label-relevant and label-irrelevant tokens, this paper provides the first theoretical analysis of training a shallow ViT, i.e., one self-attention layer followed by a two-layer perceptron, for a classification task. We characterize the sample complexity to achieve a zero generalization error. Our sample complexity bound is positively correlated with the inverse of the fraction of label-relevant tokens, the token noise level, and the initial model error. We also prove that a training process using stochastic gradient descent (SGD) leads to a sparse attention map, which is a formal verification of the general intuition about the success of attention. Moreover, this paper indicates that a proper token sparsification can improve the test performance by removing label-irrelevant and/or noisy tokens, including spurious correlations. Empirical experiments on synthetic data and CIFAR-10 dataset justify our theoretical results and generalize to deeper ViTs.
BibTeX
@inproceedings{li2023theoretical,
  author = {Hongkang Li and Meng Wang and Sijia Liu and Pin-yu Chen},
  title = {{A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexity}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=jClGv3Qjhb},
}
Figure