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

Renpu Liu, Ruida Zhou, Cong Shen, Jing Yang

TL;DR

Transformers don't just mimic basic gradient descent during in-context learning (ICL); they can implicitly execute sophisticated Learning-to-Optimize (L2O) algorithms. This paper proves that a $K$-layer Transformer can solve sparse recovery problems (LASSO) with a rapid, linear convergence rate while vastly outperforming traditional L2O methods in generalizing to unseen measurement matrices.

What Problem Does This Paper Address?

In-context learning (ICL) is a superpower of Transformers, allowing them to solve new inference tasks purely from prompt demonstrations without updating their weights. Recent theoretical work suggests that the forward pass of a Transformer achieves this by implicitly running gradient descent.

However, standard gradient descent is notoriously slow (sublinear convergence) for complex problems like sparse recovery (LASSO). This creates a paradox: why do shallow Transformers perform so well on these tasks in practice? Furthermore, existing specialized "Learning-to-Optimize" (L2O) algorithms (like LISTA) achieve fast linear convergence but are brittle—they break down completely if the underlying measurement matrix changes between training and testing. This paper addresses these gaps by investigating whether Transformers can implement flexible, fast-converging L2O algorithms during ICL.

Methods

The authors mathematically construct a $K$-layer decoder-based Transformer structure that implements a novel algorithm they call LISTA-VM (Learned Iterative Shrinkage-Thresholding Algorithm with Varying Measurements).

Key technical components include:

  • Attention Layers as Dynamic Optimizers: Instead of using static weight matrices like traditional L2O, the Transformer's attention mechanism constructs input-dependent matrices. It uses learned internal parameters to approximate the inverse Hessian, effectively mimicking second-order optimization methods.
  • MLP Layers as Thresholds: The Multi-Layer Perceptron (MLP) blocks utilize ReLU activations to perfectly execute the mathematical soft-thresholding operation required to enforce sparsity constraints.
  • Read-out Mechanisms: The authors analyze both linear and query-based (explicitly quadratic) read-out functions to extract the final prediction from the sequence embeddings.

Datasets

The paper relies entirely on synthetically generated data to rigorously control and evaluate the sparse recovery setup:

  • Sparse Vectors: Ground-truth sparse vectors ($\beta^*$) are generated with a dimension of $d=20$ and a fixed sparsity level of $S=3$ (17 entries set to zero).
  • Measurement Matrices: Matrices ($X$) of size $10 \times 20$ are randomly sampled from standard normal and sub-Gaussian distributions.
  • Evaluation Regimes: The models are evaluated under two settings: "Fixed $X$" (the same matrix is used for training and testing) and "Varying $X$" (matrices change dynamically during inference). No real-world datasets were used.

Key Insights and Ideas

  • The Hessian Shortcut: The Transformer doesn't just take simple gradient steps; it learns curvature information. The learned internal matrices act as approximations of the inverse Hessian, allowing a shallow network to achieve second-order optimization speeds.
  • Input-Dependent Flexibility: Traditional L2O models are locked into the specific measurement matrix they trained on. Transformers overcome this by dynamically adapting their implicit optimization weights based on the prompt's context.
  • Linear Convergence Proof: The authors provide a theoretical guarantee that the Transformer's ICL error decreases linearly with the number of layers $K$, a massive upgrade over the sublinear rates of standard gradient descent.

Key Results

  • Varying Matrix Generalization: In the "Varying $X$" setup, standard L2O algorithms (LISTA, LISTA-CP) fail completely, maintaining a high prediction error of around 3.0. In contrast, the proposed LISTA-VM framework drops this error significantly, and off-the-shelf Transformer architectures (GPT-2 and a constructed Small TF) match or exceed this performance (~0.68 error).
Algorithm Fixed $X$ Error Varying $X$ Error
Traditional LISTA Low (~0.2) High (~3.0)
LISTA-VM (Ours) Low (~0.2) Low (~0.68)
GPT-2 Low (~0.2) Low (<0.68)
  • Exploiting Structural Prior Knowledge: When prior knowledge of the sparsity pattern is introduced, a modified version (LISTA-VM-SS) improves prediction error by nearly 10$\times$ (down to ~0.07).
  • Read-out Impact: Query-based (quadratic) read-out functions consistently yield lower label prediction errors than simple linear read-outs, especially for smaller prompt lengths ($n$).

Limitations and Future Work

  • Noiseless Assumption: The theoretical proofs primarily focus on a noiseless scenario, though the authors note that the framework can be extended to bounded noise conditions.
  • Synthetic Constraints: The experiments and theory are restricted to synthetic, low-dimensional linear sparse recovery (LASSO). How well these L2O capabilities translate to highly non-linear optimization problems or massive real-world data distributions remains an open question for future research.

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