Transformers Meet In-Context Learning: A Universal Approximation Theory

🎯 Pitch

A single transformer can be explicitly constructed to perform in-context learning for virtually any function—not just linear regression—by internally implementing a Lasso-like algorithm to find a sparse linear representation over universal features. The prediction error vanishes with more in-context examples, with guarantees that extend far beyond convex problems, showing that transformers are universal in-context learners.

1. Executive Summary

This paper develops a universal approximation theory for how transformers enable in-context learning without parameter updates. For a general class of functions—each representing a distinct task—the authors construct a multi-layer transformer that, given a few noisy in-context examples, predicts with vanishingly small risk, showing that any target function can be nearly linearly represented over a set of universal features with small ℓ₁-norm (Barron's approximation framework), and that a transformer can find this linear representation at test time by emulating proximal gradient steps to solve Lasso (L₁-regularized regression). The analysis yields a mean squared prediction error bounded by Õ(1/√N + n/L + log|N_ε|/n)—where N is the number of in-context examples, L is the transformer depth, and n controls the input dimension—establishing that a single transformer can universally handle tasks across a general function class far beyond convex problems like linear regression, with the model complexity scaling only logarithmically in the covering number of the target function class.

2. Context and Motivation

The Core Problem: Can Transformers Universally Approximate In-Context Learning?

The fundamental question this paper tackles is deceptively ambitious: can we construct a single transformer that, without any further weight updates or fine-tuning, can perform in-context learning for virtually any function in a broad, general class? This matters because in-context learning (ICL)—the emergent ability of large language models to perform new tasks at test time given just a handful of input-output demonstrations—has become a cornerstone capability of modern foundation models, yet our theoretical understanding of why it works and what transformers can actually learn in-context remains incomplete.

The gap this paper addresses is specifically in approximation theory: prior theoretical work explaining how transformers perform ICL is almost entirely restricted to simple convex problems (primarily linear regression), leaving open the question of whether transformers can serve as universal in-context learners for general, possibly nonconvex, function classes. This is not merely an academic curiosity. The practical implications are substantial:

Understanding model capabilities: If we can prove that transformers can approximate in-context learning for general function classes (function approximation, classification with complex decision boundaries, nonlinear dynamics), we gain confidence in deploying them for tasks where we lack explicit knowledge of the underlying function structure.
Unified theoretical foundations: The field currently has two largely disconnected theoretical perspectives on ICL—the Bayesian view (Xie et al., 2022) and the algorithm approximation view (Von Oswald et al., 2023)—and a universal approximation framework could unify these by showing that transformers are not merely mimicking specific algorithms but are fundamentally capable of representing and solving broad classes of statistical learning problems in-context.
Architectural design guidance: If the theory reveals that model complexity (depth L, input dimension D) needs to scale only logarithmically with the complexity of the target function class (measured by covering number), this provides concrete guidance for how to size transformers relative to task diversity.
Bridging the gap to practice: While real-world LLMs demonstrate ICL on remarkably diverse tasks (translation, reasoning, code generation), existing theory cannot explain this breadth, being confined largely to linear regression. Extending the theory to general function classes is a necessary step toward closing this explanatory gap.

The Algorithm Approximator Perspective and Its Fundamental Limitations

The dominant theoretical approach for explaining ICL in transformers has been to interpret them as algorithm approximators—showing that attention and feed-forward layers can emulate the iterative dynamics of classical optimization algorithms. This line of work has produced several elegant constructions:

Gradient descent emulation (Von Oswald et al., 2023; von Oswald et al., 2023): Transformers can be constructed such that each layer performs one step of gradient descent on a linear regression objective, with the in-context examples serving as training data.
Preconditioned gradient descent (Ahn et al., 2023): Transformers can implement preconditioned variants that accelerate convergence for linear regression.
Newton's method (Giannou et al., 2023; Fu et al., 2024): Higher-order optimization algorithms can also be emulated by transformer layers, achieving faster convergence rates for linear regression.
Algorithm selection (Bai et al., 2023; Hataya et al., 2024): With additional layers, transformers can even select which optimization algorithm to use based on the in-context demonstrations.

The underlying logic is elegant: if each iteration of an optimization algorithm can be realized via a few attention and feed-forward layers, then a multi-layer transformer can emulate the full iterative procedure, effectively "learning" from the in-context examples by running the optimization algorithm internally. This perspective provides a compelling mechanistic explanation for ICL.

However, this approach carries a fundamental structural limitation that the paper identifies explicitly (Section 1.2):

"its utility is fundamentally constrained by the convergence properties of the algorithms being mimicked"

The problem is that optimization algorithms like gradient descent and Newton's method enjoy global convergence guarantees primarily in convex settings—which is precisely why the algorithm approximator literature has been confined to linear regression or learning linear functions. When extended to nonconvex problems (learning general nonlinear functions), the approximation guarantees must account for the optimization error inherent to the algorithms being mimicked. If gradient descent can only find a local minimum or converges slowly for a particular nonconvex objective, then a transformer emulating gradient descent inherits those same limitations.

This creates a tight coupling between the transformer's capabilities and the algorithm it emulates: the transformer can only be as good at ICL as the algorithm it copies is at optimization. For linear regression (a convex problem with a unique global minimum), this coupling is not restrictive—gradient descent works perfectly well. But for learning general nonlinear functions, where the loss landscape may be nonconvex with multiple local minima, this coupling is severely limiting. The paper explicitly notes (Section 1.2):

"except for Giannou et al. (2023); Hataya et al. (2024), existing analyses from this perspective have been restricted to linear regression (or learning linear functions)"

This is not a coincidence or a minor gap—it is a direct consequence of the algorithm approximator methodology. The approach works beautifully for convex problems but cannot cleanly extend to general function classes without inheriting the limitations of convex optimization algorithms applied to nonconvex problems.

The Missing Piece: Barron's Universal Function Approximation for ICL

On the other side of the theoretical landscape, a rich body of work has established universal function approximation theory for neural networks, dating back to the seminal work of Barron (1993). The key insight of Barron's framework is that functions whose Fourier transforms have bounded first moments (i.e., whose gradients have bounded Fourier magnitude in the ℓ₁ sense) can be approximated by single-hidden-layer neural networks with error scaling as O(1/√m) where m is the number of hidden units—independent of the input dimension d, thereby breaking the curse of dimensionality.

This framework has been extensively developed (Hornik et al., 1994; Bach, 2017; Juditsky and Nemirovski, 2000; Kurková and Sanguineti, 2002; Lee et al., 2017; E et al., 2022), but critically, it had not been adapted to the ICL setting. The core challenge is that Barron's theory provides a representation guarantee—it tells us that there exists a good approximation to a target function using a linear combination of certain features—but it does not tell us how to find those coefficients at test time given only a few noisy examples. For ICL, the transformer must both represent the function class (during pretraining) and learn the specific function from in-context demonstrations (at test time), all within a single forward pass.

The paper identifies this gap explicitly (Section 1.2):

"there has been limited progress in adapting Barron's function approximation framework to illuminate the representation power of transformers for ICL. It was largely unclear how transformers can learn universal representation of a general class of functions while being fully adaptive to in-context examples at test time."

How This Paper Positions Itself: Integrating Two Frameworks

The paper's central intellectual move is to synthesize the algorithm approximator perspective with Barron's universal function approximation theory, creating a unified framework that inherits the generality of Barron's theory while using the algorithm approximator machinery to handle the test-time adaptation. This is a novel technical integration, not simply an application of either existing framework.

The synthesis works through two conceptual steps, which the paper previews in Section 1.3 and develops fully in Section 4:

Universal feature construction (Barron's contribution): For any function f in a general class F satisfying a bounded Fourier magnitude condition (quantified by the Barron parameter CF, defined in Equation 14), there exists a set of universal, task-agnostic features such that f can be approximately represented as a linear combination of these features, with the linear coefficients having small ℓ₁ norm. This is the "representation" part of the puzzle—showing that the function class is, in a sense, compressible with respect to a fixed feature set.
In-context coefficient learning via Lasso (algorithm approximator contribution): Given the small-ℓ₁-norm property, finding the coefficients from noisy examples is naturally framed as solving a Lasso (ℓ₁-regularized regression) problem at test time. Since Lasso is a convex optimization problem, the algorithm approximator perspective is applicable without the nonconvex limitations—transformers can be constructed to emulate proximal gradient descent iterations to solve Lasso, and the convergence guarantees for proximal gradient on convex problems are strong.

This synthesis is clever because it routes around the fundamental limitation of the algorithm approximator approach. Instead of trying to emulate an optimization algorithm for the original (potentially nonconvex) learning problem, the paper first transforms the problem into finding a linear representation in a fixed feature space—reducing general function learning to linear regression with an ℓ₁ penalty. The Lasso problem is convex, so the algorithm approximator machinery applies cleanly without worrying about local minima or slow convergence in nonconvex landscapes.

Reconciling Conflicting Perspectives in the Literature

The paper also implicitly addresses a tension in the theoretical ICL literature. On one hand, the algorithm approximator work has produced provable constructions for linear regression but struggles to extend beyond convex problems. On the other hand, the Bayesian perspective (Xie et al., 2022; Ahuja et al., 2023) provides a more general framework for understanding ICL as implicit inference, but does not provide explicit transformer constructions with approximation guarantees.

The paper's framework reconciles these by showing that the algorithm approximator approach can be made general if one first applies Barron's theory to reduce the general problem to a convex one. The "algorithm" being approximated is not gradient descent on the original nonconvex loss, but proximal gradient on a Lasso objective in a lifted feature space—a convex problem that admits clean convergence analysis. This bridges the gap between the generality of Bayesian perspectives and the constructive guarantees of algorithm approximation.

Why This Matters Beyond Linear Regression

The paper is explicit that its framework extends "far beyond convex statistical learning problems like linear regression" (Section 1.3). To make this concrete, Section 2.3 and Appendix B provide explicit calculations of the Barron parameter CF for several function classes that are nonlinear and nonconvex:

Class of linear functions: CF ≤ Ca + Cb (this recovers the linear case as a special case)
Linear combination of function classes: If each component class Fi has bounded Barron parameter, the composite class also has bounded Barron parameter, scaling linearly with the ℓ₁ norm of the combination coefficients
Two-layer neural networks with logistic activation: Functions of the form f(x) = ∫ ρ(a)σ(aᵀx)da, where σ is the logistic function, have CF ≤ ¼∫ ρ_max(a)(∥a∥₂ + 2)da

This last example is particularly significant because it shows that the framework accommodates neural network function classes—which are highly nonlinear and nonconvex. A transformer constructed by the paper's theory could, in principle, perform in-context learning for tasks drawn from a class of two-layer neural networks, something entirely outside the scope of prior algorithm approximator analyses.

The Technical Challenge: From Representation to Computation

The key technical challenge the paper must overcome is connecting the existence of a good linear representation (from Barron's theory) to an actual transformer computation that finds it. This involves several sub-challenges:

The universal features must be computable by transformer layers—the paper constructs them using sigmoid-like functions that can be expressed via ReLU activations (Equation 96-97)
The Lasso solver must be implementable within the transformer architecture—the paper shows how attention layers can compute gradient steps and feed-forward layers can apply soft-thresholding/proximal operators (Section A.4)
The entire construction must work simultaneously for all functions in the class with a single set of transformer parameters—the "universal" requirement that differentiates ICL from task-specific fine-tuning
The prediction error must be controllable in terms of interpretable quantities (N, L, n, CF) rather than depending on opaque constants
The dependence on the function class complexity (via covering number |Nε|) must be mild (logarithmic) to avoid the construction being exponentially large in problem parameters

The paper addresses each of these through a meticulous constructive proof that builds the transformer layer by layer, with explicit parameter matrices specified in Section A.4. This construction serves as an existence proof—showing that transformers can achieve universal ICL—rather than claiming that practical training would discover such parameters.

Summary of the Paper's Position

This paper positions itself at the intersection of two theoretical traditions—Barron's universal function approximation and the algorithm approximator view of transformers—to address a clear gap: the lack of universal approximation theory for in-context learning beyond convex problems. The contribution is not just an incremental extension of prior algorithm approximator results to slightly wider function classes, but a methodological innovation that uses Barron's theory to transform general function learning into a convex Lasso problem, then applies algorithm approximation to solve that Lasso in-context. This synthesis removes the fundamental bottleneck that had confined prior ICL approximation theory to linear regression, opening the door to theoretical guarantees for transformers learning general nonlinear functions in-context.

3. Technical Approach

3.1 Reader Orientation

This is a constructive approximation theory paper whose core idea is that a single, fixed transformer can serve as a universal in-context learner for a broad class of functions by first representing any target function as a sparse linear combination of universal features (via Barron's theory), then computing the optimal linear coefficients at test time by internally solving a Lasso problem (via emulated proximal gradient descent). The system being built is not a practical training recipe but rather an existence proof: the authors construct explicit transformer weights—layer by layer, attention head by attention head—to demonstrate that the transformer architecture has sufficient representational capacity to approximate in-context learning for general function classes, with the prediction error provably vanishing as the number of in-context examples $N$ , the transformer depth $L$ , and the input dimension $D$ grow appropriately.

3.2 Big-Picture Architecture (Diagram in Words)

The system has five major conceptual components, though they are realized within a single transformer's forward pass rather than as separate modules:

Universal Feature Constructor (FF₀ layer) — takes the raw input vectors $x_i$ and produces a fixed set of $n$ task-agnostic features $\phi^{\text{feature}}_1(x), \ldots, \phi^{\text{feature}}_n(x)$ plus a constant bias term. These features depend only on the function class $\mathcal{F}$ , not on any specific task, and are built from randomly sampled frequencies $\omega_i$ and thresholds $t_i$ combined with a sigmoid-like activation. This component embodies Barron's insight that functions with bounded Fourier magnitude can be linearly represented over such features.
Lasso Objective Former (implicit in the architecture) — given the $N$ in-context examples $(x_i, y_i)$ and the universal features, the transformer implicitly constructs the Lasso objective: minimize the mean squared error between $y_i$ and the linear prediction $\phi_i^\top \rho$ plus an $\ell_1$ penalty $\lambda \|\rho\|_1$ on the coefficient vector $\rho$ . This objective is never explicitly written down inside the transformer; rather, the transformer's layers are designed to compute its solution.
Proximal Gradient Emulator (Attn₁ + FF₁ layer pairs, repeated $(L-1)/2$ times) — each pair of attention and feed-forward layers executes one inexact proximal gradient step for the Lasso objective. The attention layer (Attn₁) computes the gradient of the data-fitting term using softmax-based inner products between the current coefficient estimate and the feature vectors. The feed-forward layer (FF₁) applies the soft-thresholding operator (the proximal operator for $\ell_1$ regularization) via ReLU activations. Together, one Attn₁+FF₁ block maps $\rho^{\text{proximal}}_{t}$ to approximately $\rho^{\text{proximal}}_{t+1}$ .
Prediction Extractor (Attn₂ layer) — after the proximal gradient iterations complete, a final attention layer computes the predicted output for the query input $x_{N+1}$ by taking the inner product between the learned coefficients $\rho^{(L)}$ and the feature vector $\phi_{N+1}$ . This prediction is stored in the $\widehat{y}$ component of the output matrix.
Input/Output Encoding Convention — all information flows through a matrix $H^{(l)} \in \mathbb{R}^{D \times (N+1)}$ at each layer $l$ , where each column $j$ corresponds to one in-context position (columns 1 through $N$ are the examples; column $N+1$ is the query). Rows encode different semantic components: the input vectors $x_j$ , the outputs $y_j$ , the feature vectors $\phi_j$ , the current coefficient estimate $\rho^{(l)}$ , the regularization parameter $\lambda^{(l)}$ , and the current prediction $\widehat{y}^{(l)}$ . This structured matrix representation is what enables attention layers to compute inner products between the right components and feed-forward layers to apply elementwise nonlinearities to the right rows.

Information flows as follows: the input sequence $(x_1, y_1, \ldots, x_N, y_N, x_{N+1})$ enters as $H^{(0)}$ → Attn₀ and FF₀ initialize the universal features and set $\lambda$ → the Attn₁/FF₁ blocks iterate $(L-1)/2$ times, updating $\rho$ toward the Lasso solution → Attn₂ extracts the prediction for the query → the final $H^{(L)}$ contains both the learned coefficients and the prediction, with $\widehat{y}_{N+1}$ read out as the transformer's answer.

3.3 Roadmap for the Deep Dive

First, the mathematical problem formulation and the Barron parameter $C_{\mathcal{F}}$ (Section 2 of the paper), because this quantity controls everything downstream—it quantifies the complexity of the function class, determines how many universal features are needed, and appears in the final error bound. Without understanding $C_{\mathcal{F}}$ , the rest of the construction appears unmotivated.
Second, the universal feature construction (Lemma 1), which is the bridge from Barron's abstract Fourier theory to concrete transformer-computable features. This is where the "universal" in "universal approximation" comes from—the features work for all functions in $\mathcal{F}$ simultaneously.
Third, the framing of coefficient learning as Lasso and the associated statistical guarantees (Lemma 2), which explains why the transformer needs to solve an $\ell_1$ -regularized problem specifically, and what optimization accuracy is required.
Fourth, the proximal gradient algorithm and its convergence analysis (Lemma 3), which provides the target dynamics that the transformer layers will emulate. Understanding this algorithm is essential because the transformer construction directly mirrors its update equations.
Fifth, the transformer construction itself (Lemma 4 and Appendix A.4), where we see exactly how attention and feed-forward layers realize each mathematical operation—gradient computation, soft-thresholding, and prediction extraction. This is the most technically dense part but also the core contribution.
Sixth, the assembly of all pieces into the final theorem (Theorem 1), showing how the error from each component (feature approximation error $\varepsilon_{\text{dis}}$ , optimization error $\varepsilon_{\text{opt}}$ , and finite-sample statistical error) combines into the overall prediction risk bound.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily a constructive approximation theory paper whose core idea is that the transformer architecture is expressive enough to simultaneously (i) embed a universal function representation derived from Fourier analysis and (ii) execute an iterative convex optimization algorithm to recover task-specific coefficients from noisy examples, all within a single forward pass with fixed weights.

3.4.1 The Input Model and the Learning Goal

The paper considers the following statistical learning setup. There is a function class $\mathcal{F}$ of real-valued functions mapping from $\mathbb{R}^d$ to $\mathbb{R}$ , where each function $f \in \mathcal{F}$ represents a distinct prediction task. At test time, the transformer receives a prompt containing $N$ noisy input-output examples followed by a query input:

$x_1, y_1, x_2, y_2, \ldots, x_N, y_N, x_{N+1}$

where for each $i = 1, \ldots, N$ :

$x_i \overset{\text{i.i.d.}}{\sim} D_X, \quad z_i \overset{\text{i.i.d.}}{\sim} D_Z, \quad y_i = f(x_i) + z_i$

and $f \in \mathcal{F}$ is unknown to the learner. The query $x_{N+1}$ is a new input for which the transformer must predict $f(x_{N+1})$ .

Key assumptions on the data. All input vectors lie within the unit Euclidean ball: $x \in \mathcal{B} := \{u \mid \|u\|_2 \leq 1\}$ for any input vector $x$ . This compact domain assumption is standard in approximation theory and simplifies the covering number analysis. The noise variables $z_i$ are independent, zero-mean, and sub-Gaussian with sub-Gaussian norm bounded by $\sigma$ , meaning:

$\mathbb{E}[z_i] = 0 \quad \text{and} \quad \mathbb{E}[e^{t z_i}] \leq \exp\left(\frac{\sigma^2 t^2}{2}\right) \quad \text{for every } t \in \mathbb{R}$

This sub-Gaussian condition covers Gaussian noise and any bounded noise as special cases, and is the standard assumption for obtaining exponential concentration inequalities in high-dimensional statistics.

What "in-context" means here. Crucially, the pairs $(x_i, y_i)$ are not training examples used to update the transformer's weights. They are provided within the prompt at test time. The transformer's weights are fixed after pretraining; all adaptation to the specific task $f$ must happen through the forward pass on these $N$ examples. This is the defining characteristic of in-context learning: the model uses the demonstrations to internally compute a prediction function without any parameter updates.

The universal design requirement. The objective is to design a single transformer—with fixed weights that do not depend on which $f \in \mathcal{F}$ will appear at test time—that makes reliable predictions for every $f \in \mathcal{F}$ simultaneously. The transformer's parameters can depend on $\mathcal{F}$ (so it "knows" the function class structure), but not on the specific task being queried. This aligns exactly with how practical LLMs operate: a single pretrained model can perform many different tasks in-context without task-specific fine-tuning.

The evaluation metric. The quality of the transformer's prediction $\widehat{y}_{N+1}$ is measured by the mean squared error:

$\mathbb{E}\left[(\widehat{y}_{N+1} - f(x_{N+1}))^2\right]$

where the expectation is taken over the randomness of the query input $x_{N+1}$ . The goal is to make this arbitrarily small (vanishing) by appropriately choosing the transformer architecture (depth $L$ , input dimension $D$ ) and by having enough in-context examples (large $N$ ).

3.4.2 The Barron Parameter: Quantifying Function Class Complexity

Before constructing anything, the paper needs a way to measure how "complex" the function class $\mathcal{F}$ is. This measurement must be tight enough to provide meaningful guarantees but general enough to cover interesting nonlinear function classes. The key quantity is the Barron parameter $C_{\mathcal{F}}$ , defined through Fourier analysis.

Fourier representation of a function. For any absolutely integrable function $f: \mathbb{R}^d \to \mathbb{R}$ , its Fourier transform $F_f(\omega)$ and inverse transform are:

$F_f(\omega) = \frac{1}{(2\pi)^d} \int_x e^{-j\omega^\top x} f(x) \, dx, \quad f(x) = \int_\omega e^{j\omega^\top x} F_f(\omega) \, d\omega$

where $j = \sqrt{-1}$ is the imaginary unit. The Fourier transform decomposes $f$ into a continuous superposition of complex exponentials (sinusoids) at different frequencies $\omega$ , with $|F_f(\omega)|$ representing the amplitude at frequency $\omega$ . Functions that are smooth and slowly varying have most of their Fourier mass concentrated at low frequencies (small $\|\omega\|_2$ ); functions with sharp transitions or high-frequency oscillations have significant mass at high frequencies.

Since we only care about $f$ on the unit ball $\mathcal{B}$ (because inputs are bounded), we only need $f$ to be absolutely integrable on $\mathcal{B}$ , not necessarily on all of $\mathbb{R}^d$ .

The maximum Fourier magnitude over the class. For the function class $\mathcal{F}$ , define the pointwise supremum of the Fourier transform magnitude:

$F^{\sup}(\omega) := \sup_{f \in \mathcal{F}} |F_f(\omega)|$

This captures, at each frequency $\omega$ , the maximum amplitude that any function in the class can have at that frequency. If $\mathcal{F}$ contains functions with diverse behaviors, $F^{\sup}(\omega)$ will be large across many frequencies.

The Barron parameter definition. The Barron parameter $C_{\mathcal{F}}$ is defined as:

$C_{\mathcal{F}} := \sup_{f \in \mathcal{F}} |f(0)| + \int_\omega \|\omega\|_2 F^{\sup}(\omega) \, d\omega < \infty$

where the integral is over all frequencies $\omega \in \mathbb{R}^d$ , and $\|\omega\|_2$ is the Euclidean norm of the frequency vector.

What this quantity measures operationally. The term $\sup_{f \in \mathcal{F}} |f(0)|$ bounds the magnitude of all functions at the origin—a baseline scale. The integral term $\int_\omega \|\omega\|_2 F^{\sup}(\omega) \, d\omega$ is the first moment of the maximum Fourier magnitude distribution. Intuitively, $\|\omega\|_2$ is large for high frequencies, so this integral penalizes function classes that have significant Fourier mass at high frequencies. A large $C_{\mathcal{F}}$ means the class contains functions with sharp variations or complex high-frequency structure.

Alternative characterization via gradients. Since $j\omega F_f(\omega)$ is precisely the Fourier transform of the gradient $\nabla f(x)$ , we can equivalently write:

$C_{\mathcal{F}} = \sup_{f \in \mathcal{F}} |f(0)| + \int_\omega \sup_{f \in \mathcal{F}} \|F_{\nabla f}(\omega)\|_2 \, d\omega$

This makes the connection to smoothness explicit: $C_{\mathcal{F}}$ tracks the $\ell_1$ -norm of the maximum Fourier magnitude of the function gradient. Functions in $\mathcal{F}$ with large gradients (steep slopes) contribute more to $C_{\mathcal{F}}$ .

Why this particular form. The choice of $\|\omega\|_2$ (rather than $\|\omega\|_2^2$ or $\|\omega\|_1$ ) is dictated by Barron's original analysis (Barron, 1993), which showed that the first moment (not the second moment) of the Fourier magnitude controls the approximation error of single-hidden-layer neural networks. Using $\|\omega\|_2^2$ would give a Sobolev-type smoothness measure, which leads to approximation rates that degrade with input dimension (the curse of dimensionality); using $\|\omega\|_2$ avoids this degradation. The integral is over all of $\mathbb{R}^d$ because the Fourier transform can have support anywhere, but the $\|\omega\|_2$ weighting ensures that high-frequency contributions are penalized linearly.

Comparison to Barron's original $C_f$ . Barron (1993) defined $C_f := \int_\omega \|\omega\|_2 |F_f(\omega)| \, d\omega$ for a single function $f$ . The paper's $C_{\mathcal{F}}$ differs by taking the supremum over the class inside the integral: $\int_\omega \|\omega\|_2 \sup_{f \in \mathcal{F}} |F_f(\omega)| \, d\omega$ . This is larger than $\sup_{f \in \mathcal{F}} C_f$ (which would swap the supremum and the integral) because it takes the worst-case Fourier magnitude at each frequency independently. This "worst-case envelope" approach is necessary because the universal features must work for all functions simultaneously—the transformer cannot adapt its features per function, so the features must be rich enough to cover the entire envelope of possible Fourier behaviors.

Concrete examples of $C_{\mathcal{F}}$ computation (Appendix B). To demonstrate that $C_{\mathcal{F}}$ is finite for interesting classes, the paper provides three worked examples:

Linear functions: For $\mathcal{F}_{\text{linear}} = \{f_{a,b} \mid \|a\|_2 \leq C_a, |b| \leq C_b\}$ with $f_{a,b}(x) = a^\top x + b$ , we have $C_{\mathcal{F}_{\text{linear}}} \leq C_a + C_b$ . The Fourier transform of a linear function's gradient is a Dirac delta at zero with magnitude $\|a\|_2$ , so the integral collapses to $C_a$ , and the $|f(0)|$ term contributes $|b| \leq C_b$ .

Linear combinations of function classes: For $\mathcal{F}_{\text{comp}} = \{g_{a,b} \mid \|a\|_1 \leq C_a, |b| \leq C_b, f_i \in \mathcal{F}_i\}$ with $g_{a,b}(x) = \langle a, f(x)\rangle + b$ , we have $C_{\mathcal{F}_{\text{comp}}} \leq 2 C_a \max_{1 \leq i \leq M} C_{\mathcal{F}_i} + C_b$ . This shows that the Barron parameter scales linearly with the $\ell_1$ norm of the combination coefficients—a sparsity-friendly scaling.

Two-layer neural networks with logistic activation: For $\mathcal{F}_{\text{neural}} = \{f_\rho(x) = \int_a \rho(a) \sigma(a^\top x) \, da\}$ where $\sigma$ is the logistic sigmoid, we have $C_{\mathcal{F}_{\text{neural}}} \leq \frac{1}{4} \int_a \rho_{\max}(a)(\|a\|_2 + 2) \, da$ . This is derived by computing the Fourier transform of the logistic function's gradient (Equation 117), which decays exponentially as $\omega / \sinh(\pi\omega)$ , and integrating over $\omega$ . The key point is that logistic-activated two-layer networks have finite Barron parameters, so the paper's theory applies to neural network function classes.

The role of $C_{\mathcal{F}}$ throughout the analysis. This single quantity appears in almost every bound: it controls the number of universal features needed ( $n \gtrsim \log |\mathcal{N}_\varepsilon|$ with $\mathcal{N}_\varepsilon$ depending on $C_{\mathcal{F}}$ ), the $\ell_1$ norm of the target coefficients ( $\|\rho^\star\|_1 \lesssim C_{\mathcal{F}}$ ), the required regularization parameter ( $\lambda \gtrsim \sqrt{\log N / N} (C_{\mathcal{F}} + \sigma)$ ), and the final prediction error ( $\widetilde{O}(C_{\mathcal{F}}(C_{\mathcal{F}} + \sigma)/\sqrt{N} + \ldots)$ ). Everything traces back to $C_{\mathcal{F}}$ .

3.4.3 Constructing Universal Features (Lemma 1)

The first major step in the proof is showing that every function $f \in \mathcal{F}$ can be approximately represented as a linear combination of a fixed, finite set of universal features—features that depend only on $\mathcal{F}$ and not on any particular $f$ . This is Lemma 1, which formalizes the integration of Barron's theory into the ICL setting.

The starting point: Fourier representation of $f(x) - f(0)$ . Since the universal features will be used to predict function values given inputs, it suffices to represent the deviation from the baseline $f(0)$ . Writing the Fourier transform in polar form as $F_f(\omega) = |F_f(\omega)| e^{j\theta_f(\omega)}$ and using the fact that $f(x)$ is real-valued (so the imaginary parts cancel), one obtains:

$f(x) - f(0) = \int_{\omega \neq 0} \left[\cos(\omega^\top x + \theta_f(\omega)) - \cos(\theta_f(\omega))\right] |F_f(\omega)| \, d\omega$

This is derived in Equation 51 of the proof. The key insight is that the difference $f(x) - f(0)$ can be written as an integral of cosine differences weighted by $|F_f(\omega)|$ . If we can approximate the cosine difference term by a function of a simple form, we can approximate the whole integral by a sum.

Approximating cosine differences by sigmoid-like functions. The technical bridge is Lemma 5 (proved in Appendix A.1.1), which builds on Barron (1993, Lemma 5). For any frequency vector $\omega$ , any phase $\theta$ , any $\tau \geq 2$ , and any input $x$ with $\|x\|_2 \leq 1$ , there exists a function $\gamma_{\omega,\theta}(t)$ taking values in $[-1, 1]$ such that:

$\left|\frac{\cos(\omega^\top x + \theta) - \cos(\theta)}{\|\omega\|_2} - \int_{t \in [-2,1]} \gamma_{\omega,\theta}(t) \, \phi\big(\tau(\|\omega\|_2^{-1} \omega^\top x - t)\big) \, dt\right| \leq 3 \delta_\tau$

where $\phi(z)$ is a specific sigmoid-like function defined as:

$\phi(z) = \left(\frac{z+1}{2}\right) \mathbf{1}\left(\frac{z+1}{2} > 0\right) - \left(\frac{z-1}{2}\right) \mathbf{1}\left(\frac{z-1}{2} > 0\right)$

This $\phi(z)$ satisfies: $\lim_{z \to -\infty} \phi(z) = 0$ , $\lim_{z \to \infty} \phi(z) = 1$ , and $\phi(0) = 1/2$ . It is a piecewise-linear approximation of the step function $\mathbf{1}(x > 0)$ , and critically, it can be expressed exactly in terms of ReLU activations (Equation 96):

$\phi(z) = \sigma_{\text{ff}}(z + 1/2) - \sigma_{\text{ff}}(z - 1/2)$

where $\sigma_{\text{ff}}(x) = x \mathbf{1}(x > 0)$ is the ReLU function. This connection is what makes the features implementable by transformer feed-forward layers.

The quantity $\delta_\tau$ (defined in Equation 52) measures the maximum discrepancy between $\phi(\tau x)$ and the step function $\mathbf{1}(x > 0)$ , and the paper proves $\delta_\tau = 1/\tau$ for $\tau \geq 2$ . This means that by making $\tau$ large, the sigmoid approximation of the step function becomes arbitrarily accurate.

From integral to expectation. Substituting the cosine approximation into the Fourier integral and rearranging yields an intermediate approximation $\widetilde{f}^{\text{approx}}(x)$ (Equation 59) that, by the definition of $C_{\mathcal{F}}$ , satisfies:

$|f(x) - f(0) - \widetilde{f}^{\text{approx}}(x)| \leq 3 C_{\mathcal{F}} \delta_\tau$

The key insight at this stage is that $\widetilde{f}^{\text{approx}}(x)$ can be rewritten as an expectation over a probability measure that is independent of $f$ . Specifically, define:

$\Gamma_{\mathcal{F}} := 3 \int_\omega \|\omega\|_2 F^{\sup}(\omega) \, d\omega \leq 3\left(C_{\mathcal{F}} - \sup_{\widetilde{f} \in \mathcal{F}} |\widetilde{f}(0)|\right) < \infty$

Then:

$\Lambda(dt, d\omega) := \Gamma_{\mathcal{F}}^{-1} \mathbf{1}(-2 \leq t \leq 1) \|\omega\|_2 F^{\sup}(\omega) \, dt \, d\omega$

is a valid probability measure on $\mathbb{R} \times \mathbb{R}^d$ (it is non-negative and integrates to 1). Using this, the approximation takes the form:

$f^{\text{approx}}(x) := \int_{\omega \neq 0} \int_t \rho_f(t, \omega) \, \phi\big(\tau(\|\omega\|_2^{-1} \omega^\top x - t)\big) \, \Lambda(dt, d\omega)$

where $\rho_f(t, \omega) := \gamma_{\omega, \theta_f(\omega)}(t) \|\omega\|_2 |F_f(\omega)| \, dt \, d\omega / \Lambda(dt, d\omega)$ is a task-specific weight function. The crucial properties of $\rho_f$ are (Equation 55):

$|\rho_f(t, \omega)| \leq 3\left(C_{\mathcal{F}} - \sup_{\widetilde{f} \in \mathcal{F}} |\widetilde{f}(0)|\right) \quad \text{and} \quad \mathbb{E}_{(t,\omega) \sim \Lambda}[|\rho_f(t, \omega)|] \leq 3\left(C_{\mathcal{F}} - \sup_{\widetilde{f} \in \mathcal{F}} |\widetilde{f}(0)|\right)$

These bounds are uniform over $f \in \mathcal{F}$ because they depend only on $F^{\sup}$ and not on any particular $f$ 's Fourier transform. This uniformity is essential for the universal construction.

From expectation to finite sum via Monte Carlo sampling. The expectation over $\Lambda$ is still an infinite object. The final step discretizes it: draw $n$ independent samples $(t_i, \omega_i) \sim \Lambda$ for $i = 1, \ldots, n$ , and define the universal features as:

$\phi^{\text{feature}}_i(x) = \phi\left(\tau\left(\frac{1}{\|\omega_i\|_2} \omega_i^\top x - t_i\right)\right)$

for each $i = 1, \ldots, n$ . Then, for any $f \in \mathcal{F}$ , the function $f(x) - f(0)$ can be approximated by:

$\frac{1}{n} \sum_{i=1}^n \rho^\star_{f,i} \, \phi^{\text{feature}}_i(x)$

where $\rho^\star_{f,i} = \rho_{\widehat{f}}(t_i, \omega_i)$ for an appropriately chosen representative $\widehat{f}$ from the $\varepsilon$ -cover. The approximation error (Equation 22) is:

$\left|f(x) - f(0) - \frac{1}{n} \sum_{i=1}^n \rho^\star_{f,i} \phi^{\text{feature}}_i(x)\right| \lesssim C_{\mathcal{F}}\left(\frac{1}{\tau} + \tau\varepsilon + \sqrt{\frac{\log |\mathcal{N}_\varepsilon|}{n}}\right)$

with probability at least 3/4 over the random draw of $(t_i, \omega_i)$ .

The $\ell_1$ norm bound. Critically, the coefficients satisfy (Equation 23):

$|f(0)| + \frac{1}{n} \sum_{i=1}^n |\rho^\star_{f,i}| < 4 C_{\mathcal{F}}$

This $\ell_1$ -norm bound is the linchpin that justifies using Lasso (with its $\ell_1$ penalty) for coefficient recovery. If the coefficients were merely bounded in $\ell_2$ norm, ordinary least squares would suffice; the $\ell_1$ structure specifically calls for $\ell_1$ regularization.

Why random sampling works. The use of random Monte Carlo sampling from $\Lambda$ (rather than a deterministic grid) is a standard technique from empirical process theory. The $\sqrt{\log |\mathcal{N}_\varepsilon| / n}$ term arises from applying Hoeffding's inequality with a union bound over the $\varepsilon$ -cover $\mathcal{N}_\varepsilon$ —we need the approximation to hold uniformly over the function class, so we control the worst-case deviation over the cover and then extend to all functions via the Lipschitz property of the features.

The dimension parameter $n$ . The number of universal features $n$ is a design parameter of the transformer architecture. It must satisfy $n \gtrsim \log |\mathcal{N}_\varepsilon|$ to make the Monte Carlo error $\sqrt{\log |\mathcal{N}_\varepsilon| / n}$ small. The transformer's input dimension is $D = d + 2n + 7$ , where the $2n$ accounts for storing both the features $\phi_i(x)$ and auxiliary copies used in the proximal gradient computation.

The discretization error $\varepsilon_{\text{dis}}$ . For notational convenience, the paper defines (Equation 25):

$\tau = 1/\sqrt{\varepsilon}, \quad \varepsilon_{\text{dis}} := c_{\text{dis}} C_{\mathcal{F}}\left(\sqrt{\varepsilon} + \sqrt{\frac{\log |\mathcal{N}_\varepsilon|}{n}}\right)$

such that the total feature approximation error is bounded by $\varepsilon_{\text{dis}}$ for all $f \in \mathcal{F}$ and $x \in \mathcal{B}$ . The parameter $\varepsilon$ controls the precision of both the sigmoid approximation (via $\tau = 1/\sqrt{\varepsilon}$ —larger $\tau$ means tighter sigmoid-to-step-function approximation) and the $\varepsilon$ -cover (via the $\tau\varepsilon$ term from the Lipschitz constant of the features). The choice $\tau = 1/\sqrt{\varepsilon}$ balances these two sources of error: the sigmoid approximation error $1/\tau = \sqrt{\varepsilon}$ and the discretization error $\tau\varepsilon = \sqrt{\varepsilon}$ are of the same order.

Putting Lemma 1 into the ICL framework. In the ICL setting, we have $N$ input-output examples $(x_i, y_i)$ with $y_i = f(x_i) + z_i$ . Using the universal features, we can write:

$y_i \approx f(0) + \frac{1}{n} \sum_{j=1}^n \rho^\star_{f,j} \phi^{\text{feature}}_j(x_i) + z_i$

where the approximation error is at most $\varepsilon_{\text{dis}}$ uniformly. This is precisely a linear regression problem with an intercept: the covariates are the feature vectors $\phi_i = [\phi^{\text{feature}}_1(x_i), \ldots, \phi^{\text{feature}}_n(x_i), 1]^\top \in \mathbb{R}^{n+1}$ , and the target coefficient vector is:

$\rho^\star = \left[\frac{\rho^\star_{f,1}}{n}, \ldots, \frac{\rho^\star_{f,n}}{n}, f(0)\right]^\top$

with $\|\rho^\star\|_1 \lesssim C_{\mathcal{F}}$ . The problem of learning $f$ from in-context examples has been reduced to estimating $\rho^\star$ from $N$ noisy linear measurements, with the $\ell_1$ -norm constraint making it a natural Lasso problem.

3.4.4 Learning Coefficients In-Context via Lasso (Lemma 2)

With the universal features in hand, the in-context learning problem reduces to recovering the coefficient vector $\rho^\star \in \mathbb{R}^{n+1}$ from the $N$ examples. Because $\|\rho^\star\|_1 \lesssim C_{\mathcal{F}}$ is small relative to the dimension $n+1$ , the appropriate estimator is the Lasso (Tibshirani, 1996):

$\underset{\rho \in \mathbb{R}^{n+1}}{\text{minimize}} \quad \ell(\rho) := \frac{1}{N} \sum_{i=1}^N (y_i - \phi_i^\top \rho)^2 + \lambda \|\rho\|_1$

where:

$\ell(\rho)$ is the Lasso objective: mean squared error plus $\ell_1$ penalty
$\phi_i = [\phi^{\text{feature}}_1(x_i), \ldots, \phi^{\text{feature}}_n(x_i), 1]^\top \in \mathbb{R}^{n+1}$ is the feature vector for example $i$
$y_i = f(x_i) + z_i$ is the noisy output
$\lambda > 0$ is the regularization parameter controlling the trade-off between data fit and coefficient sparsity
$\|\rho\|_1 = \sum_{j=1}^{n+1} |\rho_j|$ is the $\ell_1$ norm

What the Lasso does operationally. The Lasso solves for a coefficient vector $\rho$ that simultaneously fits the data well (small mean squared error on the $N$ examples) and has small $\ell_1$ norm. The $\ell_1$ penalty encourages many coefficients to be exactly zero (sparsity) or at least small, which is appropriate here because $\|\rho^\star\|_1$ is bounded. Without the $\ell_1$ penalty (ordinary least squares), the estimator would overfit when $n$ is large relative to $N$ , especially given the feature approximation error $\varepsilon_{\text{dis}}$ .

Why $\ell_1$ rather than $\ell_2$ regularization. The $\ell_1$ penalty is chosen specifically because Lemma 1 provides an $\ell_1$ -norm bound on the target coefficients ( $\|\rho^\star\|_1 \lesssim C_{\mathcal{F}}$ ), not an $\ell_2$ -norm bound. Lasso with $\ell_1$ regularization is the natural estimator when the true parameter has bounded $\ell_1$ norm (the " $\ell_1$ -constrained" or "sparse" setting). Using ridge regression ( $\ell_2$ penalty) would give weaker guarantees because the $\ell_2$ norm of $\rho^\star$ could be as large as $\|\rho^\star\|_1$ , which provides no useful constraint.

Approximate solutions are sufficient. The paper does not require computing the exact Lasso minimizer—an approximate solution $\widehat{\rho}$ satisfying:

$\ell(\widehat{\rho}) - \ell(\rho^\star) \leq \varepsilon_{\text{opt}}$

for some optimization error $\varepsilon_{\text{opt}} \geq 0$ is sufficient. Here, $\rho^\star$ is the ground-truth coefficient vector from Lemma 1, and the comparison is against $\ell(\rho^\star)$ rather than $\min_\rho \ell(\rho)$ . This choice facilitates the analysis because $\rho^\star$ is what we understand theoretically.

Statistical guarantee for any $\varepsilon_{\text{opt}}$ -approximate solution. Lemma 2 provides the key statistical result: for any $\widehat{\rho}$ that is statistically independent of the query $x_{N+1}$ and satisfies $\ell(\widehat{\rho}) - \ell(\rho^\star) \leq \varepsilon_{\text{opt}}$ , the following hold with probability at least $1 - O(N^{-10})$ :

Prediction error bound (Equation 31):

$\mathbb{E}\left[(\phi_{N+1}^\top \widehat{\rho} - f(x_{N+1}))^2\right] \lesssim \sqrt{\frac{\log N}{N}} \left(C_{\mathcal{F}}^2 + \lambda^{-2} \varepsilon_{\text{opt}}^2 + \sigma \varepsilon_{\text{dis}}\right) + \varepsilon_{\text{dis}}^2 + \lambda C_{\mathcal{F}} + \varepsilon_{\text{opt}}$

where the expectation is over $x_{N+1}$ only.

Coefficient norm bound (Equation 32):

$\|\widehat{\rho}\|_1 \lesssim C_{\mathcal{F}} + \lambda^{-1} \varepsilon_{\text{opt}}$

How to read the prediction error bound. The right-hand side has several distinct sources of error:

$\sqrt{\frac{\log N}{N}} C_{\mathcal{F}}^2$ : the fundamental statistical error from having only $N$ noisy samples, scaling as $1/\sqrt{N}$ with the complexity $C_{\mathcal{F}}^2$
$\sqrt{\frac{\log N}{N}} \sigma \varepsilon_{\text{dis}}$ : interaction between noise and feature approximation error
$\varepsilon_{\text{dis}}^2$ : irreducible error from the finite feature set not perfectly representing every function in $\mathcal{F}$
$\lambda C_{\mathcal{F}}$ : bias introduced by the $\ell_1$ regularization—larger $\lambda$ shrinks coefficients more, increasing bias
$\varepsilon_{\text{opt}}$ : error from not running the Lasso optimization to convergence
$\sqrt{\frac{\log N}{N}} \lambda^{-2} \varepsilon_{\text{opt}}^2$ : interaction between optimization error and statistical error

The $\lambda$ regularization parameter must be chosen to balance the $\lambda C_{\mathcal{F}}$ bias term against the statistical error terms. The paper sets $\lambda \geq c_\lambda \left(\sqrt{\frac{\log N}{N}} \sigma + C_{\mathcal{F}}^{-1} \varepsilon_{\text{dis}}^2\right)$ (for some sufficiently large constant $c_\lambda$ ), which ensures the statistical terms dominate the bias.

The $\ell_1$ -norm bound on $\widehat{\rho}$ and its importance. Lemma 2 also proves that any $\varepsilon_{\text{opt}}$ -approximate solution has $\ell_1$ norm at most $O(C_{\mathcal{F}} + \lambda^{-1} \varepsilon_{\text{opt}})$ . This bound is proved by contradiction in Equation 69: if $\|\widehat{\rho}\|_1$ were too large (more than $4\|\rho^\star\|_1 + C_{\mathcal{F}} + 4\lambda^{-1}\varepsilon_{\text{opt}}$ ), then using the empirical process bound from Lemma 6 would show that $\ell(\widehat{\rho}) - \ell(\rho^\star) > \varepsilon_{\text{opt}}$ , contradicting the $\varepsilon_{\text{opt}}$ -optimality. This $\ell_1$ -norm control is essential for the proximal gradient analysis in Lemma 3, because the convergence rate depends on the $\ell_1$ norm of the iterates.

What Lemma 2 tells us about the required $\varepsilon_{\text{opt}}$ . For the optimization error not to dominate the final prediction risk, we need $\varepsilon_{\text{opt}}$ to be of the same order as the statistical error—roughly $\widetilde{O}(1/\sqrt{N} + 1/L)$ . This motivates the proximal gradient construction: we need to solve Lasso to within this tolerance using a number of iterations $T$ that determines the transformer depth $L$ .

3.4.5 Solving Lasso via Inexact Proximal Gradient (Lemma 3)

The Lasso problem (27) is convex but non-smooth due to the $\ell_1$ penalty. The standard algorithm for such problems is the proximal gradient method (also known as ISTA—Iterative Shrinkage-Thresholding Algorithm), which the paper adapts with an allowance for inexact updates.

The exact proximal gradient update. Starting from $\rho^{\text{proximal}}_0 = 0$ , the exact update at iteration $t$ is:

$\rho^{\text{proximal}}_{t+1} = \text{ST}_{\eta\lambda}\left(\rho^{\text{proximal}}_t + \frac{2\eta}{N} \sum_{i=1}^N (y_i - \phi_i^\top \rho^{\text{proximal}}_t) \phi_i\right)$

where:

$\eta > 0$ is the step size
$\text{ST}_{\eta\lambda}(\cdot)$ is the soft-thresholding operator, applied elementwise: $\text{ST}_{\eta\lambda}(z) = \text{sign}(z) \max\{|z| - \eta\lambda, 0\}$
The term $\frac{2\eta}{N} \sum_{i=1}^N (y_i - \phi_i^\top \rho^{\text{proximal}}_t) \phi_i$ is the negative gradient of the data-fitting term $\frac{1}{N}\sum (y_i - \phi_i^\top \rho)^2$ scaled by $\eta$

What the soft-thresholding operator does. For each coordinate $j$ :

If $|z_j| \leq \eta\lambda$ : output is 0 (coefficient is thresholded to zero)
If $z_j > \eta\lambda$ : output is $z_j - \eta\lambda$ (coefficient is shrunk toward zero by $\eta\lambda$ )
If $z_j < -\eta\lambda$ : output is $z_j + \eta\lambda$ (coefficient is shrunk toward zero by $\eta\lambda$ )

This operator is the proximal operator for the $\ell_1$ norm: $\text{ST}_{\eta\lambda}(z) = \arg\min_\rho \{\frac{1}{2}\|z - \rho\|_2^2 + \eta\lambda \|\rho\|_1\}$ . Each iteration thus takes a gradient step in the data-fitting direction, then shrinks the result toward zero to enforce the $\ell_1$ penalty.

The inexact proximal gradient update. The paper considers the more realistic setting where each proximal gradient step may be inexact due to finite-precision computation (in the transformer construction, due to sigmoid approximation error). The inexact update is:

$\rho^{\text{proximal}}_{t+1} = \text{ST}_{\eta\lambda}\left(\rho^{\text{proximal}}_t + \frac{2\eta}{N} \sum_{i=1}^N (y_i - \phi_i^\top \rho^{\text{proximal}}_t) \phi_i\right) + e_{t+1}$

where $e_{t+1} \in \mathbb{R}^{n+1}$ is an additive error vector. These errors accumulate across iterations and must be controlled.

Convergence guarantee (Lemma 3). With $T = (L-1)/2$ iterations (where $L$ is the transformer depth), step size $\eta = 1/(2n)$ , and regularization $\lambda \gtrsim \sqrt{\frac{\log N}{N}} (C_{\mathcal{F}} + \sigma)$ , the following hold with probability at least $1 - O(N^{-10})$ :

Optimization error after $T$ iterations (Equation 36):

$\ell(\rho^{\text{proximal}}_T) - \ell(\rho^\star) \leq c_1 \frac{n C_{\mathcal{F}}^2}{L} + c_1 (L + n) \varepsilon_{\text{approx}} \left(C_{\mathcal{F}} + \sigma + \max_{1 \leq k \leq T} \|\rho^{\text{proximal}}_k\|_1 + \lambda\right)$

where $\varepsilon_{\text{approx}} = \max_{1 \leq t \leq T} \|e_t\|_1$ is the maximum per-iteration error magnitude.

Iterate norm bound (Equation 37): for all $t \leq T$ ,

$\|\rho^{\text{proximal}}_t\|_1 \lesssim C_{\mathcal{F}} + \frac{n C_{\mathcal{F}}^2}{t \lambda} + \sqrt{N}(t + n) \max_{1 \leq k \leq t} \|e_k\|_1 + \frac{t + n}{\lambda} \max_{1 \leq k \leq t} \{\|e_k\|_1 \|\rho^{\text{proximal}}_k\|_1\}$

How to read the convergence bound. The first term $c_1 n C_{\mathcal{F}}^2 / L$ is the standard $O(1/T)$ convergence rate of proximal gradient on convex problems—the optimization error decays inversely with the number of iterations. The second term is the accumulated error from the inexact updates, scaling with $(L+n)\varepsilon_{\text{approx}}$ . For the transformer construction to work, we need $\varepsilon_{\text{approx}}$ to be extremely small ( $\lesssim C_{\mathcal{F}} / ((L+n)nN)$ —see Lemma 7), which ensures that the accumulated error remains negligible compared to the $O(1/L)$ convergence rate.

Why step size $\eta = 1/(2n)$ . The gradient of the data-fitting term is $\frac{2}{N} \sum_{i=1}^N (y_i - \phi_i^\top \rho) \phi_i$ . Since $\|\phi_i\|_\infty \leq 1$ , the Lipschitz constant of this gradient with respect to $\|\cdot\|_1$ is bounded by $2n/N$ , and the effective Lipschitz constant after factoring in the $\ell_2$ geometry is $2n$ . Taking $\eta = 1/(2n)$ ensures the step size is within the standard $1/L$ -Lipschitz condition for convergence.

The proof technique for Lemma 3. The proof (Appendix A.3) uses a standard proximal gradient analysis technique: introducing an auxiliary sequence $\rho^\star_{t+1}$ that represents the exact proximal gradient step from $\rho^{\text{proximal}}_t$ , and then bounding the gap between the inexact iterate $\rho^{\text{proximal}}_{t+1}$ and the exact iterate $\rho^\star_{t+1}$ by $\|e_{t+1}\|_1$ . The convergence of the exact proximal gradient method is established via the standard descent lemma (Equation 80b):

$\ell(\rho^\star_{t+1}) - \ell(\rho^\star) \leq n\left(\|\rho^{\text{proximal}}_t - \rho^\star\|_2^2 - \|\rho^\star_{t+1} - \rho^\star\|_2^2\right)$

which, when summed over iterations, telescopes to give $\ell(\rho^\star_{k_t}) - \ell(\rho^\star) \leq n\|\rho^\star\|_1^2 / t$ . The inexactness is then accounted for by showing (Equation 83) that:

$\ell(\rho^{\text{proximal}}_{t+1}) - \ell(\rho^\star_{t+1}) \lesssim \|e_{t+1}\|_1 \left(C_{\mathcal{F}} + \sigma + \|\rho^{\text{proximal}}_{t+1}\|_1 + \lambda\right)$

3.4.6 Transformer Construction: Emulating Proximal Gradient (Lemma 4 and Appendix A.4)

This is the most technically involved part of the paper—showing that a transformer with explicit, hand-specified weight matrices can execute the inexact proximal gradient algorithm using only its standard attention and feed-forward layers. The construction is detailed in Lemma 4 and expanded over 16 pages in Appendix A.4.

The input matrix structure. All information flows through a single matrix $H^{(l)} \in \mathbb{R}^{D \times (N+1)}$ at each layer $l$ , with $D = d + 2n + 7$ . The matrix has the following row block structure (Equation 38):