On the Learn-to-Optimize Capabilities of Transformers in In-Context Sparse Recovery

Renpu Liu, Ruida Zhou, Cong Shen, Jing Yang

Introduction

Transformers possess a remarkable ability to perform in-context learning (ICL), solving novel tasks simply by observing a few input-output demonstration pairs in a prompt—all without any parameter updates. While previous theoretical work suggested that Transformers achieve this by implicitly executing gradient descent during their forward pass, standard gradient descent converges at a sublinear rate. This sublinear rate fails to fully explain the high efficiency and accuracy observed in practice, especially in shallow networks.

This paper bridges that gap by demonstrating that Transformers are sophisticated "meta-optimizers." Specifically, it proves that a $K$-layer Transformer can implement a "Learning-to-Optimize" (L2O) algorithm for sparse recovery tasks, achieving a linear convergence rate that significantly outperforms standard gradient descent.

The Problem: Brittleness in Traditional L2O

In signal processing, Learning-to-Optimize (L2O) algorithms—such as the Learned Iterative Soft-Thresholding Algorithm (LISTA)—were designed to solve sparse recovery (LASSO) problems much faster than classical iterative methods. However, traditional L2O models are notoriously brittle. They typically only function correctly if the "measurement matrix" (the specific way the data was sampled) remains identical between training and testing.

The authors investigate whether Transformers can implement a more robust version of L2O that not only converges faster than simple gradient descent but also dynamically adapts to varying tasks and measurement matrices.

Methodology: Bridging Transformers and L2O

To answer this, the authors introduce a novel algorithm called LISTA-VM (LISTA with Varying Measurements) and provide a theoretical construction proving that a $K$-layer decoder-based Transformer can execute it.

The theoretical bridge relies on several key architectural mappings:

  • Weight Construction and Adaptivity: The attention mechanism is shown to calculate a context-dependent "pre-conditioner." Instead of relying on hard-coded weights for a specific measurement matrix, the Transformer treats the measurement matrix provided in the prompt as data, allowing it to build a custom optimization strategy on the fly.
  • MLP as Soft-Thresholding: The Multi-Layer Perceptron (MLP) layers, utilizing standard ReLU activations, can perfectly implement the soft-thresholding operations required for sparse recovery.
  • Read-out Functions: The study analyzes different ways to extract the final prediction, proving that a complex "query-based" quadratic read-out offers superior convergence guarantees compared to a simple linear read-out.

Experimental Setup

To maintain mathematical rigor, the study relies on synthetically generated datasets for sparse recovery instances (dimension $d=20$, sparsity $S=3$) with measurement matrices sampled from sub-Gaussian distributions.

The researchers evaluated a custom 12-layer "Small Transformer" and the standard GPT-2 architecture. These models were benchmarked against classical iterative algorithms (ISTA, FISTA) and state-of-the-art L2O models (LISTA, LISTA-CP, ALISTA).

Key Insights and Results

  • The "Aha" Moment of Linear Convergence: Most prior theoretical work on ICL pointed to sublinear convergence rates ($1/K$). By proving that Transformers can implement L2O, this paper demonstrates they can achieve linear convergence ($e^{-K}$). This mathematically explains why even shallow Transformers are incredibly powerful at ICL.
  • Superior Zero-Shot Generalization: When the measurement matrix was altered during testing, traditional L2O methods like LISTA failed completely. In stark contrast, GPT-2 and the Small Transformer maintained high accuracy, effectively "re-solving" the new optimization problem in-context.
  • Exploiting Hidden Structure: If the training data contains hidden patterns (e.g., signals are consistently sparse within a specific subset of indices), the Transformer automatically learns to exploit this structural information to accelerate convergence—a feat classical algorithms cannot replicate.
  • Robustness to Prompt Length: The Transformer-based L2O approach remains highly effective across varying lengths of demonstration pairs, whereas conventional L2O algorithms typically struggle when the number of measurements changes.

Limitations and Future Work

While groundbreaking, the theoretical proofs primarily assume a noiseless scenario, though the authors note the findings can be extended to bounded noise. Furthermore, the proofs are centered specifically on LASSO sparse recovery; it remains to be seen how these L2O capabilities translate to more complex, non-linear optimization tasks. Finally, while the paper proves that a specific configuration of attention and MLP weights can execute LISTA-VM, there remains a "black box" element regarding exactly how a randomly initialized Transformer discovers these optimal weight configurations during standard pre-training.

Summary updated

Abstract

An intriguing property of the Transformer is its ability to perform in-context learning (ICL), where the Transformer can solve different inference tasks without parameter updating based on the contextual information provided by the corresponding input-output demonstration pairs. It has been theoretically proved that ICL is enabled by the capability of Transformers to perform gradient-descent algorithms (Von Oswald et al., 2023a; Bai et al., 2024). This work takes a step further and shows that Transformers can perform learning-to-optimize (L2O) algorithms. Specifically, for the ICL sparse recovery (formulated as LASSO) tasks, we show that a K-layer Transformer can perform an L2O algorithm with a provable convergence rate linear in K. This provides a new perspective explaining the superior ICL capability of Transformers, even with only a few layers, which cannot be achieved by the standard gradient-descent algorithms. Moreover, unlike the conventional L2O algorithms that require the measurement matrix involved in training to match that in testing, the trained Transformer is able to solve sparse recovery problems generated with different measurement matrices. Besides, Transformers as an L2O algorithm can leverage structural information embedded in the training tasks to accelerate its convergence during ICL, and generalize across different lengths of demonstration pairs, where conventional L2O algorithms typically struggle or fail. Such theoretical findings are supported by our experimental results.
BibTeX
@inproceedings{liu2025learn,
  author = {Renpu Liu and Ruida Zhou and Cong Shen and Jing Yang},
  title = {{On the Learn-to-Optimize Capabilities of Transformers in In-Context Sparse Recovery}},
  booktitle = {International Conference on Learning Representations},
  year = {2025},
  url = {https://openreview.net/forum?id=NHhjczmJjo},
}
Figure