Mamba Can Learn Low-Dimensional Targets In-Context via Test-Time Feature Learning

## Abstract

Abstract Mamba, a recently proposed linear-time sequence model, has attracted significant attention for its computational efficiency and strong empirical performance. However, a rigorous theoretical understanding of its underlying mechanisms remains limited. In this work, we provide a theoretical analysis of Mamba’s in-context learning (ICL) capability by focusing on tasks defined by low-dimensional nonlinear target functions. Specifically, we study in-context learning of a single-index model y ≈ g ∗ ​ ( ⟨ 𝜷 , 𝒙 ⟩ ) y\approx g_{*}(\langle{\bm{\beta}},{\bm{x}}\rangle) , which depends on only a single relevant direction 𝜷 {\bm{\beta}} , referred to as feature . We prove that Mamba, pretrained by gradient-based methods, can achieve efficient ICL via test-time feature learning , extracting the relevant direction directly from context examples. Consequently, we establish a test-time sample complexity that improves upon linear Transformers—analyzed to behave like kernel methods—and is comparable to nonlinear Transformers, which have been shown to surpass the Correlational Statistical Query (CSQ) lower bound and achieve near information-theoretically optimal rate in previous works. Our analysis reveals the crucial role of the nonlinear gating mechanism in Mamba for feature extraction, highlighting it as the fundamental driver behind Mamba’s ability to achieve both computational efficiency and high performance.

## 1 Introduction

Mamba (Gu and Dao, 2024), a recently proposed state space model, has rapidly gained attention for its remarkable balance of computational efficiency and empirical performance. By replacing the quadratic-time attention mechanism of Transformers (Vaswani et al., 2017) with a selective state-space recurrence with nonlinear gating, Mamba enables scalable modeling of long sequences while maintaining competitive accuracy across a variety of tasks  (Dao and Gu, 2024; Waleffe et al., 2024; Wang et al., 2024; Patro and Agneeswaran, 2025).
Despite Mamba’s remarkable computational efficiency, it remains unknown whether it can exhibit strong adaptability (often referred to as *feature learning*), a property widely recognized as critical to the success of deep learning neural networks (Girshick et al., 2014; Suzuki, 2019; Damian et al., 2022).

A key benchmark for test-time adaptability is in-context learning (ICL) (Brown et al., 2020), which has emerged as a canonical paradigm for understanding the adaptability of large language models and sequence architectures. By conditioning on context examples provided in the input prompt, a model can achieve strong performance on new tasks at test time without explicit parameter updates. While the empirical effectiveness of ICL is well documented, theoretical understanding of when and how different architectures exhibit this behavior remains limited (Xie et al., 2022; Garg et al., 2022; Zhou et al., 2024). In particular, most existing theoretical analyses focus on Transformers (Ahn et al., 2023; Zhang et al., 2024; Mahankali et al., 2024; Huang et al., 2024; Kim and Suzuki, 2024), whose quadratic attention mechanisms make them both powerful and computationally demanding. It remains unclear whether alternative architectures such as Mamba can offer comparable adaptability.

Recent works have investigated Mamba’s ICL capabilities, empirically demonstrating that Mamba performs competitively across various ICL benchmarks (Grazzi et al., 2024; Park et al., 2024; Li et al., 2024c).
However, our understanding of Mamba’s ICL capabilities remains lacking. This is due to its distinct inductive bias from the Transformer. The recurrent state-space model with nonlinear gating processes inputs through recurrent updates that maintain and transform hidden states over time, rather than relying on global attention over the entire context. This distinction motivates new theoretical questions:

*Can Mamba provably achieve strong test-time adaptability like Transformers
with its recurrent state-space updates and nonlinear gating?*

### 1.1 Summary of Contributions

In this paper, we study the ICL capabilities of Mamba, focusing on a single-index model—a widely adopted theoretical tool for studying adaptability. We summarize our contributions as follows:

- •
We introduce a theoretical framework for analyzing Mamba’s ICL of single-index models, including input embeddings, the Mamba architecture, and a gradient-based pretraining algorithm. Under this framework, we characterize the optimization dynamics and establish the sample complexity in terms of the number of pretraining tasks and the number of context examples at pretraining and test time required to achieve strong performance (Theorem [3.3](https://arxiv.org/html/2510.12026v2#S3.Thmtheorem3)).
- •
Our analysis reveals that pretrained Mamba is capable of *test-time feature learning*, enabling it to extract task-relevant features directly from context examples (Proposition [4.1](https://arxiv.org/html/2510.12026v2#S4.Thmtheorem1)). This result implies that Mamba can surpass the performance of kernel regression baselines and achieve adaptation at test time. Specifically, the gating mechanism enables Mamba to achieve test-time feature learning, thereby overcoming the limitations inherent to purely linear recurrent updates.
- •
We provide a comparative analysis between Mamba and Transformer architectures, highlighting similarities and differences in their ICL mechanisms. Our results reveal that Mamba can achieve test-time feature learning via a qualitatively different mechanism—recurrent state-space updates with nonlinear gating—thus extending the theoretical landscape of in-context learning beyond attention-based models.

### 1.2 Related Works

#### Theory of In-Context Learning.

Theoretical investigations of ICL have predominantly centered on Transformers. Beyond initial results showing that Transformers trained on regression tasks can reproduce ordinary least squares solutions in-context (Akyürek et al., 2023; Zhang et al., 2024; Mahankali et al., 2024; Han et al., 2025), subsequent analyses reveal their ability to emulate more complex procedures such as multi-step gradient descent (Ahn et al., 2023; Saunshi et al., 2025), functional gradient descent (Cheng et al., 2024), and sparse regression (Bai et al., 2023). Parallel works extend this line of inquiry to classification, where recent studies provide provable insights into how Transformers implement in-context classification (Li et al., 2024a; Bu et al., 2025).

While the theoretical literature on ICL has dominantly focused on Transformers, a growing body of work is extending this theoretical analysis to linear-time sequence models. Recent works (Li et al., 2024b, 2025b) prove that H3-like model (Fu et al., 2023) and gated linear attention (Yang et al., 2024) can implement weighted preconditioned gradient descent based on loss landscape analysis. Bondaschi et al. (2025) study ICL of Mamba on Markov chains and show that it learns a Laplacian smoothing estimator in-context. However, these works do not provide optimization or generalization guarantees. Recent works by Jiang et al. (2025) and Li et al. (2025a) provide such guarantees for in-context learning of Mamba on linear regression and classification tasks with outliers, as we also do in this work.

#### Learning Low-Dimensional Target Function.

Low-dimensional target function classes, such as sparse parities (Barak et al., 2022; Suzuki et al., 2023; Glasgow, 2024), signal-noise models (Allen-Zhu and Li, 2020; Cao et al., 2022), are widely adopted as theoretical benchmarks for studying a neural network’s ability to perform feature learning.
This work specifically focuses on the single-index model. A line of theoretical work has analyzed the learning of these models and has established key results on sample complexity. The required sample complexity is governed by either the *information exponent* (for algorithms utilizing correlational information (Arous et al., 2021; Bietti et al., 2022; Damian et al., 2023; Mousavi-Hosseini et al., 2023)) or the *generative exponent* (for algorithms that employ suitable label transformations (Damian et al., 2024; Lee et al., 2024; Arnaboldi et al., 2024; Joshi et al., 2024)). We discuss these sample complexity results in more detail in Section [3.1](https://arxiv.org/html/2510.12026v2#S3.SS1).

Our work is most closely related to Oko et al. (2024); Nishikawa et al. (2025), which lie at the intersection of ICL and the single-index model. Specifically, Oko et al. (2024) show that a pretrained linear Transformer can effectively learn a single-index model in-context. More recent work by Nishikawa et al. (2025) establish an even smaller sample complexity and reveal that the nonlinear Transformer can perform test-time feature learning. A detailed comparison with these works is provided in Section [3.2](https://arxiv.org/html/2510.12026v2#S3.SS2).

## 2 Problem Setting

In this section, we provide a formal description of the key components we focus on: the ICL data distribution, the Mamba model, and the gradient-based pretraining algorithm.

#### Notation.

We denote the $i$-th coordinate of a vector ${\bm{v}}$ as ${\bm{v}}[i]$, and the $(i,j)$-th coordinate of a matrix ${\bm{M}}$ as ${\bm{M}}[i,j]$. The matrix $\mathrm{diag}({\bm{v}})$ represents a diagonal matrix with a vector ${\bm{v}}$ on its main diagonal. We use $\odot$ for the element-wise product.
For any $k\in\mathbb{N}$, we denote the vectors with all entries equal to one and zero as ${\bm{1}}_{k}$ and ${\bm{0}}_{k}$, respectively. We omit the subscript $k$ when the dimension is clear from the context.

### 2.1 Data Distribution for In-Context Learning

In-context learning aims to solve the *task* of predicting the *label* $y$ of a *query* ${\bm{x}}$ by leveraging a sequence of input-label pairs $\{({\bm{x}}_{i},y_{i})\}_{i\in[N]}$, which are referred to as *context examples*. The model then utilizes a prompt, which is a sequence $({\bm{x}}_{1},y_{1},\dots,{\bm{x}}_{N},y_{N},{\bm{x}})$ consisting of the context examples and the query, as its input. We focus on the case where prompts are constructed from the Gaussian single-index model, which is defined as follows.

###### Definition 2.1 (Gaussian Single-Index Model) .

Given a feature vector ${\bm{\beta}}\in\mathbb{R}^{d}$, we draw input-label pairs $({\bm{x}},y)\sim{\mathcal{D}}_{{\bm{\beta}}}$ as

$$ ${\bm{x}}\sim{\mathcal{N}}({\bm{0}},{\bm{I}}_{d}),\quad y=g_{*}(\langle{\bm{\beta}},{\bm{x}}\rangle)+\zeta,\quad\zeta\sim\mathrm{Unif}(\{-\tau,\tau\}),$ $$

where $g_{*}$ is a polynomial *link function* and $\tau>0$ represents the noise level. For simplicity, we assume that $\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}[g_{*}({\mathbf{z}})]=0,\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}[(g_{*}({\mathbf{z}}))^{2}]=1$ and $\tau$ is a small enough constant.

For each task, a prompt is constructed with a random choice of feature vectors.

###### Definition 2.2 (ICL Data Distribution) .

For given a context length $N$, we define a data distribution ${\mathcal{D}}(N)$ such that $({\bm{\beta}},\{({\bm{x}}_{i},y_{i})\}_{i\in[N]},{\bm{x}},y)\sim{\mathcal{D}}(N)$ is constructed as follows.

- 1.
We draw the feature vector ${\bm{\beta}}\in\mathbb{R}^{d}$ from the *intrinsic feature space* $S_{r}$, which is the unit sphere of a low-dimensional subspace with dimension $r$. This subspace is defined as:
${\bm{\beta}}\sim\mathrm{Unif}(S_{r}),\quad\text{where }S_{r}:=\left\{\bm{\theta}\in\mathbb{R}^{d}:\left\|\bm{\theta}\right\|=1,\bm{\theta}[j]=0\text{ for all }j\notin{\mathcal{I}}\right\},$
for some unknown feature index set ${\mathcal{I}}$ with $\left|{\mathcal{I}}\right|=r$.
- 2.
We sample $N$ context examples $\{({\bm{x}}_{i},y_{i})\}_{i\in[N]}$ and a query-label pair $({\bm{x}},y)$ from ${\mathcal{D}}_{\bm{\beta}}$.

Our task distribution exhibits a low-dimensional structure in two key aspects: (1) the label depends solely on the projection of the input onto the feature vector, and (2) feature vectors are supported on an $r$-dimensional subspace. We note that to achieve low prediction errors, it is crucial to extract both of these structures and estimate the link function $g_{*}$.

###### Definition 2.1 (Gaussian Single-Index Model) .

###### Definition 2.2 (ICL Data Distribution) .

### 2.2 Prediction Model Architecture

Our prediction model for ICL is composed of three parts: input embedding, one-layer Mamba, multi-layer perceptron (MLP).

#### Input Embedding.

Given a prompt $({\bm{x}}_{1},y_{1},\dots,{\bm{x}}_{N},y_{N},{\bm{x}})$ with context length $N$ and label $y$, we construct an input embedding ${\bm{Z}}\in\mathbb{R}^{(\tilde{d}+1)\times(N+1)}$ as

$$ ${\bm{Z}}=\begin{bmatrix}\phi({\bm{x}}_{1})&\phi({\bm{x}}_{2})&\dots&\phi({\bm{x}}_{N})&\phi({\bm{x}})\\ y_{1}&y_{2}&\dots&y_{N}&0\end{bmatrix}=[{\bm{z}}_{1},\dots\bm{z}_{N},{\bm{z}}_{N+1}]\in\mathbb{R}^{(\tilde{d}+1)\times(N+1)},$ $$

where $\tilde{d}=\frac{d(d+1)}{2}+1$ and $\phi:\mathbb{R}^{d}\rightarrow\mathbb{R}^{\tilde{d}}$ is defined as

$$ $\phi(\bm{\theta})=\left[1,\bm{\theta}[1],\dots,\bm{\theta}[d],\frac{\bm{\theta}[1]^{2}-1}{\sqrt{2}},\dots,\frac{\bm{\theta}[d]^{2}-1}{\sqrt{2}},\bm{\theta}[1]\bm{\theta}[2],\dots,\bm{\theta}[d-1]\bm{\theta}[d]\right].$ $$

An input embedding similar to ours was also considered in the recent work by Sun et al. (2025), who studied the in-context learning of high-order polynomial target functions. They showed this embedding can be implemented with a simple version of Gated Linear Unit (GLU) and demonstrated its efficacy for enabling linear Transformers to learn these functions in-context. Unlike Sun et al. (2025), who repeatedly stacked a linear Transformer and a GLU layer, in our work, a single GLU-based embedding is sufficient due to the nonlinearity in Mamba and MLP layers. We discuss the efficacy of this input embedding in more detail in Section [4.1](https://arxiv.org/html/2510.12026v2#S4.SS1).

###### Remark 2.3 .

Our input embedding is based on a basis for degree-2 polynomials in $\mathbb{R}^{d}$. Specifically, we use the standard basis of $\mathbb{R}^{d}$ for the construction of both the input embedding and the intrinsic feature space $S_{r}$. While extending our results to a general choice of $S_{r}$ with an arbitrary basis may require additional techniques, our setting remains valuable for studying Mamba’s ability to learn low-dimensional structure. Furthermore, we emphasize that our result also holds with the standard choice of input embedding $\phi({\bm{x}})={\bm{x}}$ with $\tilde{d}=d$, as considered in prior works including Von Oswald et al. (2023), for the case where link function $g_{*}$ is not an even function. We refer to Section [4](https://arxiv.org/html/2510.12026v2#S4) for a more detailed discussion.

###### Remark 2.3 .

#### One-Layer Mamba.

Given an input embedding ${\bm{Z}}=({\bm{z}}_{1},\dots,{\bm{z}}_{N+1})\in\mathbb{R}^{(\tilde{d}+1)\times(N+1)}$, a one-layer Mamba model ${\mathsf{Mamba}}(\cdot;\bm{\Theta})$ with parameters $\bm{\Theta}$ has sequential outputs ${\bm{o}}_{1},\dots,{\bm{o}}_{N+1}\in\mathbb{R}^{\tilde{d}+1}$ and hidden states for $i$-th channel ${\bm{h}}_{1}^{(i)},\dots,{\bm{h}}_{N}^{(i)}\in\mathbb{R}^{d_{h}}$ defined as below:

$$ $\displaystyle{\bm{h}}_{l}^{(i)}=\overline{{\bm{A}}}_{l}{\bm{h}}_{l-1}^{(i)}+\overline{{\bm{B}}}_{l}{\bm{z}}_{l}[i]\in\mathbb{R}^{d_{h}},\quad{\bm{o}}_{l}[i]={\bm{C}}_{l}^{\top}{\bm{h}}_{l}^{(i)}\in\mathbb{R},$ $\displaystyle\overline{{\bm{A}}}_{l}=\exp\left(\Delta_{l}{\bm{A}}\right)\in\mathbb{R}^{d_{h}\times d_{h}},\quad\overline{{\bm{B}}}_{l}=\left(\Delta_{l}{\bm{A}}\right)^{-1}(\exp\left(\Delta_{l}{\bm{A}}\right)-{\bm{I}}_{d_{h}})\Delta_{l}{\bm{B}}_{l}\in\mathbb{R}^{d_{h}},$ $$

where ${\bm{h}}_{0}^{(i)}={\bm{0}}_{d_{h}}$ and ${\bm{A}}\in\mathbb{R}^{d_{h}\times d_{h}}$. Here, the components of the selection algorithm ${\bm{A}},{\bm{B}}_{l},{\bm{C}}_{l},\Delta_{l}$ is chosen as

$$ ${\bm{A}}=-{\bm{I}}_{\tilde{d}+1},\quad{\bm{B}}_{l}={\bm{W}}_{B}{\bm{z}}_{l},\quad{\bm{C}}_{l}={\bm{W}}_{C}{\bm{z}}_{l},\quad\Delta_{l}=\mathrm{softplus}\left({\bm{w}}^{\top}{\bm{z}}_{l}+b\right),$ $$

with parameters ${\bm{W}}_{B},{\bm{W}}_{C}\in\mathbb{R}^{d_{h}\times(\tilde{d}+1)},{\bm{w}}\in\mathbb{R}^{\tilde{d}},b\in\mathbb{R}$.
Then, the $l$-th output can be expressed as

$$ ${\bm{o}}_{l}=\sum_{j=1}^{l}G_{j,l}({\bm{Z}}){\bm{z}}_{j}{\bm{z}}_{j}^{\top}{\bm{W}}_{B}^{\top}{\bm{W}}_{C}{\bm{z}}_{l},$ (1) $$

where $G_{j,l}({\bm{Z}})=\sigma\left({\bm{w}}^{\top}{\bm{z}}_{j}+b\right)\prod_{k=j+1}^{l}\left(1-\sigma\left({\bm{w}}^{\top}{\bm{z}}_{k}+b\right)\right)$ with sigmoid function $\sigma(\cdot)$. It implies that Mamba involves two key mechanisms: *nonlinear gating* $G_{j,l}({\bm{Z}})$ and *linear attention* with projection matrices ${\bm{W}}_{B}$ and ${\bm{W}}_{C}$. Yang et al. (2024) refer the combination of these mechanisms as *gated linear attention* and recent recurrent models including Mamba, mLSTM (Beck et al., 2024), and RWKV-6 (Peng et al., 2024) can be viewed within this framework.

To ensure a tractable optimization guarantee, we further introduce the following simplifications to our model:

$$ ${\bm{W}}_{B}^{\top}{\bm{W}}_{C}=\mathrm{diag}({\bm{\gamma}},0),\quad{\bm{w}}=\begin{bmatrix}{\bm{0}}_{\tilde{d}}\\ \rho^{-1}\end{bmatrix},$ $$

where ${\bm{\gamma}}\in\mathbb{R}^{\tilde{d}}$ is a learnable parameter, while ${\bm{w}}\in\mathbb{R}^{\tilde{d}+1}$ and $b\in\mathbb{R}$ are fixed.
Our approach of merging the product of two learnable matrices into a single matrix and using sparse learnable parameters is a technique also adopted in the theoretical literature on optimization of attention mechanisms (Ahn et al., 2023; Zhang et al., 2024; Mahankali et al., 2024; Kim and Suzuki, 2024). Under this simplification, the last coordinate of the final output which serves as the input to the MLP can be expressed as follows:

$$ ${\mathsf{Mamba}}({\bm{Z}};{\bm{\gamma}})[\tilde{d}+1,N+1]=\sum_{j=1}^{N}G_{j,N+1}({\bm{Z}})y_{j}\phi({\bm{x}}_{j})^{\top}\left({\bm{\gamma}}\odot\phi({\bm{x}})\right).$ $$

#### Multi-Layer Perceptron.

We use a two-layer MLP with ReLU activation, width $m$ and parameters ${\bm{u}},{\bm{v}},{\bm{a}}\in\mathbb{R}^{m}$ defined as follows:

$$ ${\mathsf{MLP}}(z;{\bm{u}},{\bm{v}},{\bm{a}}):=\sum_{k=1}^{m}{\bm{u}}[k]{\mathrm{ReLU}}\left({\bm{v}}[k]z+{\bm{a}}[k]\right).$ $$

We apply this MLP to the output of the Mamba layer, after normalizing it by its context length $N$. Then, the final output is given by

$$ $\displaystyle f({\bm{Z}};{\bm{\gamma}},{\bm{u}},{\bm{v}},{\bm{a}})$ $\displaystyle:={\mathsf{MLP}}\left(N^{-1}{\mathsf{Mamba}}({\bm{Z}};{\bm{\gamma}})[\tilde{d}+1,N+1];{\bm{u}},{\bm{v}},{\bm{a}}\right)$ $\displaystyle=\sum_{k=1}^{m}{\bm{u}}[k]{\mathrm{ReLU}}\left({\bm{v}}[k]N^{-1}\sum_{j=1}^{N}G_{j,N+1}({\bm{Z}})y_{j}\phi({\bm{x}}_{j})^{\top}\left({\bm{\gamma}}\odot\phi({\bm{x}})\right)+{\bm{a}}[k]\right).$ $$

###### Remark 2.4 .

A similar structure to our models, which combines a sequence model with a MLP, has also been utilized in two closely related prior works. For example, Nishikawa et al. (2025) follow a similar structure but use a softmax Transformer in place of Mamba. In contrast, Oko et al. (2024) use a different architectural design, applying the MLP to the input embedding before a linear Transformer, rather than after the sequence model.

Our goal for ICL is to find parameters ${\bm{\gamma}}\in\mathbb{R}^{\tilde{d}},{\bm{u}},{\bm{v}},{\bm{a}}\in\mathbb{R}^{m}$, and context length $N$, achieving a small ICL test error, which is defined as

$$ ${\mathcal{R}}_{N}({\bm{\gamma}},{\bm{u}},{\bm{v}},{\bm{a}}):=\mathbb{E}_{({\bm{Z}},y)\sim{\mathcal{D}}(N)}[\left|f({\bm{Z}},{\bm{\gamma}},{\bm{u}},{\bm{v}},{\bm{a}})-y\right|].$ $$

Here, we abuse notation and use $({\bm{Z}},y)$ to denote the input embedding and label for a prompt sampled from the ICL data distribution ${\mathcal{D}}(N)$.
More precisely, we are interested in the sample complexity of context examples required for the parameters learned from pretraining to achieve a low ICL test error.

###### Remark 2.4 .

### 2.3 Pretraining Algorithm

Our prediction model is pretrained on a set of $T_{{\mathrm{pt}}}=T_{1}+T_{2}$ tasks with context length $N_{\mathrm{pt}}$ drawn from ${\mathcal{D}}(N_{\mathrm{pt}})$. For each task $t\in[T_{\mathrm{pt}}]$, let we have input embedding ${\bm{Z}}^{t}$ constructed from context examples $\{({\bm{x}}_{i}^{t},y_{i}^{t})\}_{i\in[N_{\mathrm{pt}}]}$ and a query-label pair $({\bm{x}}^{t},y^{t})$ with a feature vector ${\bm{\beta}}^{t}$. Then, our training losses can be written as

$$ $L_{l}({\bm{\gamma}},{\bm{u}},{\bm{v}},{\bm{a}}):=\frac{1}{T_{l}}\sum_{t=T_{l-1}+1}^{T_{l-1}+T_{l}}\left(f\left({\bm{Z}}^{t};{\bm{\gamma}},{\bm{u}},{\bm{v}},{\bm{a}}\right)-y^{t}\right)^{2},$ $$

for $l=1,2$ and $T_{0}=0$. We employ a two-stage training procedure, as described in Algorithm [1](https://arxiv.org/html/2510.12026v2#algorithm1), using these objectives.

- 1.
In Stage I, we only train the Mamba layer parameter ${\bm{\gamma}}$, starting from proper initialization. Our training objective is $\ell_{2}$-regularized loss $L_{1}({\bm{\gamma}},{\bm{u}},{\bm{v}},{\bm{a}})+\frac{\lambda_{1}}{2}\left\|{\bm{\gamma}}\right\|^{2}$. Due to the non-linearity introduced by the MLP, this objective is non-convex. To make the training dynamics tractable, we apply one-step gradient descent, following the approaches studied in the literature of feature learning (Ba et al., 2022; Damian et al., 2022). As we describe in Section [4.1](https://arxiv.org/html/2510.12026v2#S4.SS1), a single step update is sufficient to capture the low-dimensional structure of the feature vectors.
- 2.
In Stage II, we fix the Mamba layer parameter ${\bm{\gamma}}^{*}$ obtained from Stage I and optimize the outer layer ${\bm{u}}$ of MLP on $\ell_{2}$-regularized loss $L_{2}({\bm{\gamma}}^{*},{\bm{u}},{\bm{v}}^{*},{\bm{a}}^{*})+\frac{\lambda_{2}}{2}\left\|{\bm{u}}\right\|^{2}$ with reinitialized inner layer parameters ${\bm{v}}^{*},{\bm{a}}^{*}$. This induces a convex problem that gradient-based methods can solve. As we show in Section [4.2](https://arxiv.org/html/2510.12026v2#S4.SS2), the optimized MLP is capable of estimating the link function $g_{*}$.

Figure: Algorithm 1 Gradient-based Pretraining of the Mamba Model

## 3 Mamba Efficiently Learns Single-Index Models In-Context

In this section, we present our theoretical results on the ICL performance of our model. Our analysis focuses on the asymptotic dependencies on the input dimension $d$, with the assumption that the feature dimension $r$ can scale with $d$, while the link function $g_{*}$ is fixed. For our analysis, we let $N^{*}$ and $T^{*}$ be the maximum admissible context length and the number of pretraining tasks, respectively. We assume that $N^{*},T^{*}\leq d^{C^{*}}$ for some large constant $C^{*}>0$. We use the standard asymptotic notation ${\mathcal{O}}(\cdot),\Omega(\cdot),\Theta(\cdot),o(\cdot)$ to express dependencies on $d$, and ${\tilde{\mathcal{O}}}(\cdot),\tilde{\Omega}(\cdot),\tilde{\Theta}(\cdot)$ to hide logarithmic factors of $d$.

### 3.1 Preliminaries

We first provide backgrounds on learning Gaussian single-index models, which are essential for understanding our main result.
Let $\mathrm{He}_{i}(z)=(-1)^{i}e^{\frac{z^{2}}{2}}\frac{\mathrm{d}^{i}}{\mathrm{d}z^{i}}e^{-\frac{z^{2}}{2}}$ denote the probabilist’s Hermite polynomials. Then, the set $\{\mathrm{He}_{i}(z)/\sqrt{i!}\}_{i\in\mathbb{N}\cup\{0\}}$ forms an orthonormal basis of the $L^{2}$ space with respect to the Gaussian measure and serves as a key technical tool for the analysis of Gaussian single-index models. We now introduce two key terms relevant to the sample complexity of learning.

###### Definition 3.1 .

For any function $h:\mathbb{R}\rightarrow\mathbb{R}$ which is $L^{2}$-integrable with respect to the Gaussian measure, we express its Hermite expansion as

$$ $h(z)=\sum_{i=0}^{\infty}\frac{H(h,i)}{i!}\mathrm{He}_{i}(z),\quad H(h,i):=\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}[h({\mathbf{z}})\mathrm{He}_{i}({\mathbf{z}})].$ $$

We also define the following quantities:

- •
We define $\mathrm{deg}(h)$ as the degree of $h$, if it is a polynomial.
- •
The *information exponent* (Arous et al., 2021; Damian et al., 2023) of $h$ is defined as
$\mathrm{ie}(h):=\min\{i\in\mathbb{N}:H(h,i)\neq 0\}.$
It implies that $\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}[h({\mathbf{z}})\mathrm{He}_{k}({\mathbf{z}})]=0$ for any $k\in\mathbb{N}$ with $k<\mathrm{ie}(h)$.
- •
The *generative exponent* (Damian et al., 2024) of $h$ is defined as the lowest possible information exponent after an $L^{2}$ transformation. It is formally defined as:
$\mathrm{ge}(h):=\min_{{\mathcal{T}}\in L^{2}(P_{h})}\min\{i\in\mathbb{N}:H({\mathcal{T}}\circ h,i)\neq 0\},$
where $L^{2}(P_{h})$ is the set of $L^{2}$-integrable functions with respect to $P_{h}$. Here, $P_{h}$ is the push-forward measure of the Gaussian measure by $h$.

While the definition of the generative exponent may seem difficult to apply at first glance, Lee et al. (2024) provides a characterization of the generative exponent for polynomials.

###### Lemma 3.2 (Proposition 6 in Lee et al. ( 2024 ) ) .

For a polynomial link function $g_{*}$, the generative exponent is characterized as $\mathrm{ge}(g_{*})=2$ if $g_{*}$ is an even function, and $\mathrm{ge}(g_{*})=1$ otherwise.

From the definition, $\mathrm{ge}(g_{*})\leq\mathrm{ie}(g_{*})\leq\mathrm{deg}(g_{*})$ and Lemma [3.2](https://arxiv.org/html/2510.12026v2#S3.Thmtheorem2) implies that the gap between these three terms can be arbitrarily large depending on the choice of $g_{*}$(^1^11For example, consider $g_{*}(z)=\mathrm{He}_{q}(z)+\mathrm{He}_{p}(z)$ with $1\ll q\ll p$.). With a slight abuse of notation, we use $\Theta(\mathrm{deg}(g_{*}))$ to denote a quantity that is bounded by a universal constant multiple of $\mathrm{deg}(g_{*})$. We also use $\Theta(\mathrm{ie}(g_{*}))$ and $\Theta(\mathrm{ge}(g_{*}))$, in similar manners.

###### Definition 3.1 .

###### Lemma 3.2 (Proposition 6 in Lee et al. ( 2024 ) ) .

#### Sample Complexity of Learning Single-Index Models.

Previous works have established the sample complexity of various methods for learning a Gaussian single-index model. For example, kernel methods, which lack an adaptive basis, require at least $d^{\mathrm{deg}(g_{*})}$ samples (Ghorbani et al., 2021; Donhauser et al., 2021). In contrast, adaptive methods such as gradient-based methods on two-layer neural networks can achieve a sample complexity of ${\tilde{\mathcal{O}}}\left(d^{\Theta(\mathrm{ie}(g_{*}))}\right)$ by learning an adaptive feature map (Arous et al., 2021; Ba et al., 2022; Damian et al., 2022, 2023; Dandi et al., 2024). These approaches fall under the category of CSQ algorithms, and in this category, a sample complexity that depends on the information exponent is inevitable (Damian et al., 2022). However, recent works show that a nonlinear transformation introduced by data reuse (Arnaboldi et al., 2024; Lee et al., 2024) enables the algorithm to move into the broader class of Statistical Query (SQ) algorithms. This transformation allows the “effective” information exponent to be lowered to the generative exponent, thereby achieving a sample complexity of ${\tilde{\mathcal{O}}}\left(d^{\Theta(\mathrm{ge}(g_{*}))}\right)$.

### 3.2 Main Result

We now present our main result, which provides a theoretical characterization of the pretraining and test-time sample complexities for achieving low ICL errors.

###### Theorem 3.3 .

Let $f(\cdot;{\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})$ be the Mamba model pretrained using Algorithm [1](https://arxiv.org/html/2510.12026v2#algorithm1). We assume the following conditions hold for its hyperparameters:

- •
The context length is $N_{\mathrm{pt}}=\tilde{\Omega}\left(\max\left\{r^{3\mathrm{ge}(g_{*})}d^{8},T_{1}^{2}d^{4}\right\}\right)$.
- •
The number of pretraining tasks are $T_{1}=\tilde{\Omega}\left(r^{3\mathrm{ge}(g_{*})}d^{6}\right)$ and $T_{2}=\tilde{\Omega}\left(r^{3\mathrm{ge}(g_{*})}\right)$.
- •
The MLP width is $m=\tilde{\Omega}\left(r^{4\mathrm{ge}(g_{*})}\right)$.
- •
The fixed weights are $\rho=\Theta\left((\log d)^{C_{\rho}}\right)$ and $b=C_{b}\log d$, and the initialization scale is $\gamma=\Theta((\log d)^{-C_{\gamma}})$ for sufficiently large constants $C_{\gamma},C_{\rho},C_{b}>0$.

Then, there exist hyperparameters $\lambda_{1},\lambda_{2},$ and $\eta$ such that with probability at least 0.99 over the training data and random initialization, the following holds:
If the test prompt length satisfies $N_{\mathrm{test}}=\tilde{\Omega}\left(r^{3\mathrm{ge}(g_{*})}\right)$, then the test error ${\mathcal{R}}_{N_{\mathrm{test}}}({\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})$ is bounded by $\tau+o(1)$.

We discuss our sample complexity results in comparison with other methods, including regression on test prompts and prior theoretical works (Oko et al., 2024; Nishikawa et al., 2025). We summarize these results in Table [1](https://arxiv.org/html/2510.12026v2#S3.T1) and highlight the following key points:

###### Theorem 3.3 .

#### Adaptation to Low-Dimensional Structure.

Our sample complexity depends on the intrinsic dimension of the feature vectors $r$, rather than the ambient dimension $d$. This is consistent with prior works (Oko et al., 2024; Nishikawa et al., 2025) that also demonstrate a dependence on intrinsic dimensionality. In contrast, the sample complexities of various regression algorithms we have discussed depend on the full input dimension $d$. This difference arises because pretrained models can learn the low-dimensional structure of the intrinsic feature space during pretraining.

#### Test-Time Feature Learning.

The dependence of the sample complexity on the intrinsic dimension $r$ in the work of Oko et al. (2024) is controlled by the degree of the link function $g_{*}$. This means that while their approach is more efficient than simple regression on full dimensions, its performance remains close to that of kernel methods on intrinsic dimensions. In contrast, our result depends on the generative exponent $\mathrm{ge}(g_{*})$, instead of its degree. This implies that Mamba’s efficient in-context learning is enabled not just by its ability to learn an intrinsic feature space, but also by a process called *test-time feature learning*, which allows the model to extract features directly from the context. The same process also works for the softmax Transformers considered in Nishikawa et al. (2025) and thus achieved a similar sample complexity. However, these models perform test-time feature learning through different mechanisms: Mamba relies on nonlinear gating, while the Transformer uses softmax attention.

#### Improvement in Pretraining Sample Complexity.

The conditions for the pretraining in our theorem can be satisfied with a pretraining sample complexity of $N_{\mathrm{pt}}=\Theta\left(d^{\Theta(\mathrm{ge}(g_{*}))}\right)$. In contrast, the pretraining sample complexities in previous works (Oko et al., 2024; Nishikawa et al., 2025) are governed by the information exponent, which can lead to a suboptimal rate in the worst case. This improvement is due to the nonlinearity of the MLP, as we discuss in detail in Section [4](https://arxiv.org/html/2510.12026v2#S4).

**Table 1: Summary of sample complexity results for regression algorithms on test prompt and prior works on in-context learning (Oko et al., 2024; Nishikawa et al., 2025).**
| Regression on Test Prompt |  |  |
| --- | --- | --- |
| Kernel | CSQ | SQ |
| $d^{\Theta(\mathrm{deg}(g_{*}))}$ | $d^{\Theta(\mathrm{ie}(g_{*}))}$ | $d^{\Theta(\mathrm{ge}(g_{*}))}$ |
| In-context learning |  |  |
| Transformer | Mamba |  |
| Oko et al. (2024) | Nishikawa et al. (2025) | This Work |
| *Pretrain:* $d^{\Theta(\mathrm{ie}(g_{*}))}$ | *Pretrain:* $d^{\Theta(\mathrm{ie}(g_{*}))}$ | *Pretrain:* $d^{\Theta(\mathrm{ge}(g_{*}))}$ |
| *Test:* $r^{\Theta(\mathrm{deg}(g_{*}))}$ | *Test:* $r^{\Theta(\mathrm{ge}(g_{*}))}$ | *Test:* $r^{\Theta(\mathrm{ge}(g_{*}))}$ |

## 4 Proof Overview

In this section, we provide an overview of the proof for our theorem. The proof consists of three main parts: an analysis of one-step gradient descent on the Mamba layer, the optimization of the MLP, and a test error analysis. The formal proofs for each of these steps are provided in Appendices [B](https://arxiv.org/html/2510.12026v2#A2), [C](https://arxiv.org/html/2510.12026v2#A3), and [D](https://arxiv.org/html/2510.12026v2#A4), respectively. In the following, we introduce the key ideas behind each step.

### 4.1 One-Step Gradient Descent on the Mamba Layer

Assuming a negative bias $b$ with sufficiently large absolute value, and a large enough number of tasks $T_{1}$ and context length $N_{\mathrm{pt}}$, the updated parameter ${\bm{\gamma}}^{*}$ can be approximated as follows:

$$ $\displaystyle{\bm{\gamma}}^{*}$ $\displaystyle\approx 2\eta\mathbb{E}_{({\bm{Z}},y)\sim{\mathcal{D}}(N_{\mathrm{pt}})}[y\nabla_{\bm{\gamma}}f({\bm{Z}};{\bm{\gamma}}(0),{\bm{u}}(0),{\bm{v}}(0),{\bm{a}}(0))]$ $\displaystyle\approx 2\eta\mathbb{E}_{\begin{subarray}{c}{\bm{\beta}}\sim\mathrm{Unif}(S_{r})\\ ({\bm{x}},y)\sim{\mathcal{D}}_{{\bm{\beta}}}\end{subarray}}\left[y\mathbbm{1}\left[\left\langle{\bm{c}}_{\bm{\beta}},{\bm{\gamma}}(0)\odot\phi({\bm{x}})\right\rangle>0\right]{\bm{c}}_{\bm{\beta}}\odot\phi({\bm{x}})\right],$ $$

where ${\bm{c}}_{\bm{\beta}}:=\mathbb{E}_{({\bm{x}},y)\sim{\mathcal{D}}_{\bm{\beta}}}\left[y\sigma(y/\rho+b)\phi({\bm{x}})\right]$ corresponds to a simplified expectation over context examples, neglecting the effect of “forgetting” in the gating mechanism.

#### The Role of Gating and Input Embedding.

In the absence of a gating mechanism and with only a linear attention, the term ${\bm{c}}_{\bm{\beta}}$ is replaced by $\mathbb{E}_{({\bm{x}},y)\sim{\mathcal{D}}_{\bm{\beta}}}[y\phi({\bm{x}})]$ and this term vanishes when $\mathrm{ie}(g_{*})>2$. This is a consequence of our input embedding using Hermite polynomials only up to the second degree, in combination with Stein’s lemma. As a result, pretraining in this case is unable to learn useful information.
However, we prove that the nonlinear transformation introduced by the gating mechanism can reduce the information exponent to the generative exponent: $\mathrm{ie}(g_{*}\sigma(g_{*}/\rho+b))=\mathrm{ge}(g_{*})$. Combining Lemma [3.2](https://arxiv.org/html/2510.12026v2#S3.Thmtheorem2) with our input embedding, we show that the gating enables the model to extract information. When $g_{*}$ is a non-even function, our result can also be shown to hold with the standard input embedding $\phi({\bm{x}})={\bm{x}}$, as can be seen from this intuition. Reducing the information exponent to the generative exponent crucially affects the achievement of a test-time sample complexity below the CSQ lower bounds. Nishikawa et al. (2025) shows that the softmax operator in the Transformer can also perform a nonlinear transformation on the label, which reduces the information exponent. This highlights a key difference in the mechanisms used by Mamba and the softmax Transformer to achieve this result.

#### Improved Sample Complexity of Pretraining.

If the indicator $\mathbbm{1}[\cdot]$ inside the expectation is 1 with high probability, then the updated parameter ${\bm{\gamma}}^{*}$ can be approximated as ${\bm{\gamma}}^{*}\approx 2\eta\mathbb{E}_{{\bm{\beta}}\sim\mathrm{Unif}(S_{r})}\left[\mathbb{E}_{({\bm{x}},y\sim{\mathcal{D}}_{\bm{\beta}})}[y{\bm{c}}_{\bm{\beta}}\odot\phi({\bm{x}})]\right]$ and this close to zero when $\mathrm{ie}(g_{*})>2$. However, we show that the indicator deviates significantly from a constant value. We formally prove that this deviation allows the indicator to reduce the information exponent when multiplied by the label $y$, thereby inducing a sample complexity not governed by $\mathrm{ie}(g_{*})$. While Nishikawa et al. (2025) employ an architecture with a similar structure to ours—an MLP following a Softmax Transformer—they do not achieve the same improvement. This is because their use of Softmax places the model in a regime where a key indicator function is 1 with high probability. In addition, our observation for this improvement cannot be directly applied to the work of Oko et al. (2024) due to a key architectural difference: applying the MLP layer in the input embedding rather than at the output layer.

#### Pretrained Mamba Perform Test-Time Feature Learning.

We show that the pretrained parameter ${\bm{\gamma}}^{*}$ recovers the intrinsic feature space $S_{r}$ by attaining significantly larger components within the feature index set ${\mathcal{I}}$ than in other indices. Furthermore, we show that pretrained mamba performs test-time feature learning by establishing the following proposition:

###### Proposition 4.1 (Informal) .

For a sampled ICL input embedding ${\bm{Z}}$ with context length $N=\tilde{\Omega}\left(r^{3\mathrm{ge}(g_{*})}\right)$, query ${\bm{x}}$, and feature vector ${\bm{\beta}}$, the following holds with high probability:

$$ ${\mathsf{Mamba}}({\bm{Z}};{\bm{\gamma}}^{*})\approx P_{1}+P_{2}\left(\frac{\langle{\bm{\beta}},{\bm{x}}\rangle}{r}\right)^{\mathrm{ge}(g_{*})}.$ (2) $$

###### Proposition 4.1 (Informal) .

### 4.2 Optimization of the MLP and Test Error Analysis

In our analysis of Stage II pretraining, we first construct an outer layer parameter ${\bm{u}}^{\prime}$ such that the loss $L_{2}({\bm{\gamma}}^{*},{\bm{u}}^{\prime},{\bm{v}},{\bm{a}})$ is sufficiently small and the norm $\left\|{\bm{u}}^{\prime}\right\|$ is well-bounded. Our construction is based on the techniques in Damian et al. (2022), which constructed a ReLU network approximating monomial transformations. This transformation allows our model to learn high-order polynomials with a few layers, in contrast to the multi-layer approach in Sun et al. (2025). More specifically, since Lemma [3.2](https://arxiv.org/html/2510.12026v2#S3.Thmtheorem2) implies that $g_{*}(z)$ is a polynomial of $z^{\mathrm{ge}(g_{*})}$, and then we can construct an MLP layer approximating $g_{*}(\langle{\bm{\beta}},{\bm{x}}\rangle)$, when the input is provided in the form of ([2](https://arxiv.org/html/2510.12026v2#S4.E2)).

From the equivalence between $\ell_{2}$-regularization and $\ell_{2}$ norm-constraints in convex problems, we show that for a proper $\lambda_{2}>0$, the minimizer ${\bm{u}}^{*}$ satisfies $L_{2}({\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})\leq L_{2}({\bm{\gamma}}^{*},{\bm{u}}^{\prime},{\bm{v}}^{*},{\bm{a}}^{*})$ and $\left\|{\bm{u}}^{*}\right\|\leq\left\|{\bm{u}}^{\prime}\right\|$.
Next, we show that the trained model achieves a small test error with context length $N_{\mathrm{pt}}$ by applying a standard generalization bound based on Rademacher complexity, which is applicable due to a well-bounded norm $\left\|{\bm{u}}^{*}\right\|$.
Lastly, we extend this error bound to a general context length $N_{\mathrm{test}}=\tilde{\Omega}\left(r^{3\mathrm{ge}(g_{*})}\right)$. It is possible because ([2](https://arxiv.org/html/2510.12026v2#S4.E2)) implies that prompts with $N_{\mathrm{test}}$ context examples and $N_{\mathrm{pt}}$context examples give similar outputs, given the same query.

## 5 Experiments

To support our theoretical findings, we pretrain and evaluate both Transformer and Mamba models on our data distribution. Our data is generated using a link function $g_{*}(z)=\mathrm{He}_{3}(z)/\sqrt{6}$ and an intrinsic dimension of $r=8$, with the varying ambient dimension $d=16,32$. We employ a 6-layer GPT-2 model (Radford et al., 2019) with 8 attention heads and a 12-layer Mamba model. To ensure a fair comparison, both models have an embedding dimension of 256 and a similar number of parameters. The overall experimental settings for pretraining follow those of prior works (Garg et al., 2022; Park et al., 2024). We also conduct kernel ridge regression on the intrinsic feature space to serve as a baseline for understanding the effect of feature learning. For this, we use a Gaussian RBF kernel with a bandwidth of 1 and a ridge parameter of 1. For evaluation, we measure the prediction error using squared error, with the number of context examples ranging from 1 to 40. We estimate the test error on 1024 randomly sampled tasks, using 2048 independent prompts for each task, and represent the results with the mean and standard deviation over these tasks.
Figure [1](https://arxiv.org/html/2510.12026v2#S5.F1) demonstrates our results. Both Transformer and Mamba models exhibit comparable performance that is rarely affected by the ambient dimension $d$. This suggests that both models mainly utilize information from the intrinsic feature space. In addition, these methods outperform kernel methods, even when we restrict the input of the kernel method to the intrinsic feature space. This observation aligns with our finding that Mamba, similar to Transformers, not only benefits from its adaptation to the intrinsic feature space but also performs test-time feature learning.
Figure 1: Prediction error for in-context learning with Transformer and Mamba models, and kernel regression.

## 6 Conclusion

We investigated Mamba’s capability for in-context learning by focusing on a Gaussian single-index model. We proved that Mamba, when pretrained with gradient-based optimization, can efficiently learn in-context through a mechanism we termed test-time feature learning. Our derived test-time sample complexity is comparable to that of the softmax Transformer model, a result established by Nishikawa et al. (2025) and also surpasses the CSQ lower bound. Our analysis reveals that Mamba’s gating mechanism is a key factor in enabling feature learning and strong performance. We also presented experimental results to support our findings.

We suggest several directions for future research. First, a valuable direction is to investigate whether our results can be extended to more general input embeddings by considering additional layers, which could help overcome our current limitations.
Second, while our analysis considers the case where “forgetting” in the gating mechanism is negligible, recent work by Li et al. (2025a) reveals that this effect can be beneficial for tasks with outliers. Investigating the combination of this effect with our insight could be an interesting direction. Finally, studying how different choices of gating functions within the gated linear attention framework (Yang et al., 2024) lead to different behaviors is a possible direction for future work.

## Acknowledgement

JO acknowledges partial support by the Institute for Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korean government (MSIT) (No. RS-2019-II190075, Artificial Intelligence Graduate School Program(KAIST)).
WH was supported by JSPS KAKENHI (24K20848) and JST BOOST (JPMJBY24G6). TS was partially supported by JSPS KAKENHI (24K02905) and JST CREST (JPMJCR2015).
This research is supported by the National Research Foundation, Singapore, Infocomm Media Development Authority under its Trust Tech Funding Initiative, and the Ministry of Digital Development and Information under the AI Visiting Professorship Programme (award number AIVP-2024-004). Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not reflect the views of National Research Foundation, Singapore, Infocomm Media Development Authority, and the Ministry of Digital Development and Information.

## References

- Ahn et al. (2023)
Kwangjun Ahn, Xiang Cheng, Hadi Daneshmand, and Suvrit Sra.
Transformers learn to implement preconditioned gradient descent for in-context learning.
*Advances in Neural Information Processing Systems*, 36:45614–45650, 2023.
- Akyürek et al. (2023)
Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou.
What learning algorithm is in-context learning? investigations with linear models.
In *The Eleventh International Conference on Learning Representations*, 2023.
URL [https://openreview.net/forum?id=0g0X4H8yN4I](https://openreview.net/forum?id=0g0X4H8yN4I).
- Allen-Zhu and Li (2020)
Zeyuan Allen-Zhu and Yuanzhi Li.
Towards understanding ensemble, knowledge distillation and self-distillation in deep learning.
*arXiv preprint arXiv:2012.09816*, 2020.
- Arnaboldi et al. (2024)
Luca Arnaboldi, Yatin Dandi, Florent Krzakala, Luca Pesce, and Ludovic Stephan.
Repetita iuvant: Data repetition allows SGD to learn high-dimensional multi-index functions.
*arXiv preprint arXiv:2405.15459*, 2024.
- Arous et al. (2021)
Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath.
Online stochastic gradient descent on non-convex losses from high-dimensional inference.
*Journal of Machine Learning Research*, 22(106):1–51, 2021.
- Ba et al. (2022)
Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, and Greg Yang.
High-dimensional asymptotics of feature learning: How one gradient step improves the representation.
*Advances in Neural Information Processing Systems*, 35:37932–37946, 2022.
- Bach (2024)
Francis Bach.
*Learning theory from first principles*.
MIT press, 2024.
- Bai et al. (2023)
Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei.
Transformers as statisticians: Provable in-context learning with in-context algorithm selection.
*Advances in neural information processing systems*, 36:57125–57211, 2023.
- Barak et al. (2022)
Boaz Barak, Benjamin Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang.
Hidden progress in deep learning: SGD learns parities near the computational limit.
*Advances in Neural Information Processing Systems*, 35:21750–21764, 2022.
- Beck et al. (2024)
Maximilian Beck, Korbinian Pöppel, Markus Spanring, Andreas Auer, Oleksandra Prudnikova, Michael Kopp, Günter Klambauer, Johannes Brandstetter, and Sepp Hochreiter.
xlstm: Extended long short-term memory.
*Advances in Neural Information Processing Systems*, 37:107547–107603, 2024.
- Bietti et al. (2022)
Alberto Bietti, Joan Bruna, Clayton Sanford, and Min Jae Song.
Learning single-index models with shallow neural networks.
*Advances in neural information processing systems*, 35:9768–9783, 2022.
- Bondaschi et al. (2025)
Marco Bondaschi, Nived Rajaraman, Xiuying Wei, Kannan Ramchandran, Razvan Pascanu, Caglar Gulcehre, Michael Gastpar, and Ashok Vardhan Makkuva.
From markov to laplace: How mamba in-context learns markov chains.
*arXiv preprint arXiv:2502.10178*, 2025.
- Brown et al. (2020)
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.
Language models are few-shot learners.
*Advances in neural information processing systems*, 33:1877–1901, 2020.
- Bu et al. (2025)
Dake Bu, Wei Huang, Andi Han, Atsushi Nitanda, Qingfu Zhang, Hau-San Wong, and Taiji Suzuki.
Provable in-context vector arithmetic via retrieving task concepts.
In *Forty-second International Conference on Machine Learning*, 2025.
- Cao et al. (2022)
Yuan Cao, Zixiang Chen, Misha Belkin, and Quanquan Gu.
Benign overfitting in two-layer convolutional neural networks.
*Advances in neural information processing systems*, 35:25237–25250, 2022.
- Cheng et al. (2024)
Xiang Cheng, Yuxin Chen, and Suvrit Sra.
Transformers implement functional gradient descent to learn non-linear functions in context.
In *Forty-first International Conference on Machine Learning*, 2024.
URL [https://openreview.net/forum?id=ah1BlQcLv4](https://openreview.net/forum?id=ah1BlQcLv4).
- Damian et al. (2023)
Alex Damian, Eshaan Nichani, Rong Ge, and Jason D Lee.
Smoothing the landscape boosts the signal for sgd: Optimal sample complexity for learning single index models.
*Advances in Neural Information Processing Systems*, 36:752–784, 2023.
- Damian et al. (2024)
Alex Damian, Loucas Pillaud-Vivien, Jason Lee, and Joan Bruna.
Computational-statistical gaps in gaussian single-index models.
In *The Thirty Seventh Annual Conference on Learning Theory*, pages 1262–1262. PMLR, 2024.
- Damian et al. (2022)
Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi.
Neural networks can learn representations with gradient descent.
In *Conference on Learning Theory*, pages 5413–5452. PMLR, 2022.
- Dandi et al. (2024)
Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan.
How two-layer neural networks learn, one (giant) step at a time.
*Journal of Machine Learning Research*, 25(349):1–65, 2024.
URL [http://jmlr.org/papers/v25/23-1543.html](http://jmlr.org/papers/v25/23-1543.html).
- Dao and Gu (2024)
Tri Dao and Albert Gu.
Transformers are SSMs: Generalized models and efficient algorithms through structured state space duality.
In *Forty-first International Conference on Machine Learning*, 2024.
URL [https://openreview.net/forum?id=ztn8FCR1td](https://openreview.net/forum?id=ztn8FCR1td).
- Donhauser et al. (2021)
Konstantin Donhauser, Mingqi Wu, and Fanny Yang.
How rotational invariance of common kernels prevents generalization in high dimensions.
In *International Conference on Machine Learning*, pages 2804–2814. PMLR, 2021.
- Fu et al. (2023)
Daniel Y Fu, Tri Dao, Khaled Kamal Saab, Armin W Thomas, Atri Rudra, and Christopher Re.
Hungry hungry hippos: Towards language modeling with state space models.
In *The Eleventh International Conference on Learning Representations*, 2023.
URL [https://openreview.net/forum?id=COZDy0WYGg](https://openreview.net/forum?id=COZDy0WYGg).
- Garg et al. (2022)
Shivam Garg, Dimitris Tsipras, Percy S Liang, and Gregory Valiant.
What can transformers learn in-context? a case study of simple function classes.
*Advances in neural information processing systems*, 35:30583–30598, 2022.
- Ghorbani et al. (2021)
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari.
Linearized two-layers neural networks in high dimension.
*The Annals of Statistics*, 49(2), 2021.
- Girshick et al. (2014)
Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik.
Rich feature hierarchies for accurate object detection and semantic segmentation.
In *Proceedings of the IEEE conference on computer vision and pattern recognition*, pages 580–587, 2014.
- Glasgow (2024)
Margalit Glasgow.
SGD finds then tunes features in two-layer neural networks with near-optimal sample complexity: A case study in the XOR problem.
In *The Twelfth International Conference on Learning Representations*, 2024.
URL [https://openreview.net/forum?id=HgOJlxzB16](https://openreview.net/forum?id=HgOJlxzB16).
- Grazzi et al. (2024)
Riccardo Grazzi, Julien Niklas Siems, Simon Schrodi, Thomas Brox, and Frank Hutter.
Is mamba capable of in-context learning?
In *International Conference on Automated Machine Learning*, pages 1–1. PMLR, 2024.
- Gu and Dao (2024)
Albert Gu and Tri Dao.
Mamba: Linear-time sequence modeling with selective state spaces.
In *First Conference on Language Modeling*, 2024.
- Han et al. (2025)
Chi Han, Ziqi Wang, Han Zhao, and Heng Ji.
Understanding emergent in-context learning from a kernel regression perspective.
*Transactions on Machine Learning Research*, 2025.
ISSN 2835-8856.
URL [https://openreview.net/forum?id=6rD50Q6yYz](https://openreview.net/forum?id=6rD50Q6yYz).
- Huang et al. (2024)
Yu Huang, Yuan Cheng, and Yingbin Liang.
In-context convergence of transformers.
In *Forty-first International Conference on Machine Learning*, 2024.
URL [https://openreview.net/forum?id=9GLvXGkUE2](https://openreview.net/forum?id=9GLvXGkUE2).
- Jiang et al. (2025)
Jiarui Jiang, Wei Huang, Miao Zhang, Taiji Suzuki, and Liqiang Nie.
Trained mamba emulates online gradient descent in in-context linear regression.
*arXiv preprint arXiv:2509.23779*, 2025.
- Joshi et al. (2024)
Nirmit Joshi, Theodor Misiakiewicz, and Nati Srebro.
On the complexity of learning sparse functions with statistical and gradient queries.
*Advances in Neural Information Processing Systems*, 37:103198–103241, 2024.
- Kim and Suzuki (2024)
Juno Kim and Taiji Suzuki.
Transformers learn nonlinear features in context: Nonconvex mean-field dynamics on the attention landscape.
In *International Conference on Machine Learning*, pages 24527–24561. PMLR, 2024.
- Lee et al. (2024)
Jason D Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu.
Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit.
*Advances in Neural Information Processing Systems*, 37:58716–58756, 2024.
- Li et al. (2024a)
Hongkang Li, Meng Wang, Songtao Lu, Xiaodong Cui, and Pin-Yu Chen.
How do nonlinear transformers learn and generalize in in-context learning?
In *Forty-first International Conference on Machine Learning*, 2024a.
URL [https://openreview.net/forum?id=I4HTPws9P6](https://openreview.net/forum?id=I4HTPws9P6).
- Li et al. (2025a)
Hongkang Li, Songtao Lu, Xiaodong Cui, Pin-Yu Chen, and Meng Wang.
Can mamba learn in context with outliers? a theoretical generalization analysis.
*arXiv preprint arXiv:2510.00399*, 2025a.
- Li et al. (2024b)
Yingcong Li, Ankit S Rawat, and Samet Oymak.
Fine-grained analysis of in-context linear estimation: Data, architecture, and beyond.
*Advances in Neural Information Processing Systems*, 37:138324–138364, 2024b.
- Li et al. (2024c)
Yingcong Li, Xupeng Wei, Haonan Zhao, and Taigao Ma.
Can mamba in-context learn task mixtures?
In *ICML 2024 Workshop on In-Context Learning*, 2024c.
- Li et al. (2025b)
Yingcong Li, Davoud Ataee Tarzanagh, Ankit Singh Rawat, Maryam Fazel, and Samet Oymak.
Gating is weighting: Understanding gated linear attention through in-context learning.
*arXiv preprint arXiv:2504.04308*, 2025b.
- Mahankali et al. (2024)
Arvind V. Mahankali, Tatsunori Hashimoto, and Tengyu Ma.
One step of gradient descent is provably the optimal in-context learner with one layer of linear self-attention.
In *The Twelfth International Conference on Learning Representations*, 2024.
URL [https://openreview.net/forum?id=8p3fu56lKc](https://openreview.net/forum?id=8p3fu56lKc).
- Mousavi-Hosseini et al. (2023)
Alireza Mousavi-Hosseini, Denny Wu, Taiji Suzuki, and Murat A Erdogdu.
Gradient-based feature learning under structured data.
*Advances in Neural Information Processing Systems*, 36:71449–71485, 2023.
- Nishikawa et al. (2025)
Naoki Nishikawa, Yujin Song, Kazusato Oko, Denny Wu, and Taiji Suzuki.
Nonlinear transformers can perform inference-time feature learning.
In *Forty-second International Conference on Machine Learning*, 2025.
URL [https://openreview.net/forum?id=xQTSvP57C3](https://openreview.net/forum?id=xQTSvP57C3).
- Oko et al. (2024)
Kazusato Oko, Yujin Song, Taiji Suzuki, and Denny Wu.
Pretrained transformer efficiently learns low-dimensional target functions in-context.
*Advances in Neural Information Processing Systems*, 37:77316–77365, 2024.
- Park et al. (2024)
Jongho Park, Jaeseung Park, Zheyang Xiong, Nayoung Lee, Jaewoong Cho, Samet Oymak, Kangwook Lee, and Dimitris Papailiopoulos.
Can mamba learn how to learn? a comparative study on in-context learning tasks.
In *International Conference on Machine Learning*, pages 39793–39812. PMLR, 2024.
- Patro and Agneeswaran (2025)
Badri Narayana Patro and Vijay Srinivas Agneeswaran.
Mamba-360: Survey of state space models as transformer alternative for long sequence modelling: Methods, applications, and challenges.
*Engineering Applications of Artificial Intelligence*, 159:111279, 2025.
- Peng et al. (2024)
Bo Peng, Daniel Goldstein, Quentin Gregory Anthony, Alon Albalak, Eric Alcaide, Stella Biderman, Eugene Cheah, Teddy Ferdinan, Kranthi Kiran GV, Haowen Hou, Satyapriya Krishna, Ronald McClelland Jr., Niklas Muennighoff, Fares Obeid, Atsushi Saito, Guangyu Song, Haoqin Tu, Ruichong Zhang, Bingchen Zhao, Qihang Zhao, Jian Zhu, and Rui-Jie Zhu.
Eagle and finch: RWKV with matrix-valued states and dynamic recurrence.
In *First Conference on Language Modeling*, 2024.
URL [https://openreview.net/forum?id=soz1SEiPeq](https://openreview.net/forum?id=soz1SEiPeq).
- Radford et al. (2019)
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al.
Language models are unsupervised multitask learners.
*OpenAI blog*, 1(8):9, 2019.
- Saunshi et al. (2025)
Nikunj Saunshi, Nishanth Dikkala, Zhiyuan Li, Sanjiv Kumar, and Sashank J. Reddi.
Reasoning with latent thoughts: On the power of looped transformers.
In *The Thirteenth International Conference on Learning Representations*, 2025.
URL [https://openreview.net/forum?id=din0lGfZFd](https://openreview.net/forum?id=din0lGfZFd).
- Sun et al. (2025)
Haoyuan Sun, Ali Jadbabaie, and Navid Azizan.
On the role of transformer feed-forward layers in nonlinear in-context learning.
*arXiv preprint arXiv:2501.18187*, 2025.
- Suzuki (2019)
Taiji Suzuki.
Adaptivity of deep reLU network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionality.
In *International Conference on Learning Representations*, 2019.
URL [https://openreview.net/forum?id=H1ebTsActm](https://openreview.net/forum?id=H1ebTsActm).
- Suzuki et al. (2023)
Taiji Suzuki, Denny Wu, Kazusato Oko, and Atsushi Nitanda.
Feature learning via mean-field langevin dynamics: classifying sparse parities and beyond.
*Advances in Neural Information Processing Systems*, 36:34536–34556, 2023.
- Vaswani et al. (2017)
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.
Attention is all you need.
*Advances in neural information processing systems*, 30, 2017.
- Von Oswald et al. (2023)
Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov.
Transformers learn in-context by gradient descent.
In *International Conference on Machine Learning*, pages 35151–35174. PMLR, 2023.
- Waleffe et al. (2024)
Roger Waleffe, Wonmin Byeon, Duncan Riach, Brandon Norick, Vijay Korthikanti, Tri Dao, Albert Gu, Ali Hatamizadeh, Sudhakar Singh, Deepak Narayanan, et al.
An empirical study of mamba-based language models.
*arXiv preprint arXiv:2406.07887*, 2024.
- Wang et al. (2024)
Junxiong Wang, Daniele Paliotta, Avner May, Alexander Rush, and Tri Dao.
The mamba in the llama: Distilling and accelerating hybrid models.
*Advances in Neural Information Processing Systems*, 37:62432–62457, 2024.
- Xie et al. (2022)
Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma.
An explanation of in-context learning as implicit bayesian inference.
In *International Conference on Learning Representations*, 2022.
URL [https://openreview.net/forum?id=RdJVFCHjUMI](https://openreview.net/forum?id=RdJVFCHjUMI).
- Yang et al. (2024)
Songlin Yang, Bailin Wang, Yikang Shen, Rameswar Panda, and Yoon Kim.
Gated linear attention transformers with hardware-efficient training.
In *International Conference on Machine Learning*, pages 56501–56523. PMLR, 2024.
- Zhang et al. (2024)
Ruiqi Zhang, Spencer Frei, and Peter L Bartlett.
Trained transformers learn linear models in-context.
*Journal of Machine Learning Research*, 25(49):1–55, 2024.
- Zhou et al. (2024)
Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Joshua M. Susskind, Samy Bengio, and Preetum Nakkiran.
What algorithms can transformers learn? a study in length generalization.
In *The Twelfth International Conference on Learning Representations*, 2024.
URL [https://openreview.net/forum?id=AssIuHnmHX](https://openreview.net/forum?id=AssIuHnmHX).

## Appendix A Proof Preliminaries

#### Notation.

We introduce the following additional notation for ease of presentation. We use $\mathbbm{1}[\cdot]$ to represent indicator function. We write $a\lesssim b$, $a\gtrsim b$, and $a\asymp b$ to denote that $a={\mathcal{O}}(b)$, $a=\Omega(b)$, and $a=\Theta(b)$, respectively. We also use $\mathrm{poly}(d)$ and $\mathrm{polylog}(d)$ to represent a sufficiently large polynomial in $d$ and $\log d$, respectively. Lastly, we use $o(1/\mathrm{polylog}(d))$ to represent a quantity that decreases faster than $(\log d)^{-C}$ for any constant $C>0$. Lastly, with a slight abuse of notation, we use the asymptotic notation we introduced to represent a vector when its norm satisfies the corresponding bound.

### A.1 Simplification of Mamba Output

The following lemma immediately implies ([1](https://arxiv.org/html/2510.12026v2#S2.E1)).

###### Lemma A.1 .

Given a prompt $({\bm{x}}_{1},y_{1},\dots,{\bm{x}}_{N},y_{N},{\bm{x}})$ and its input embedding ${\bm{Z}}\in\mathbb{R}^{(\tilde{d}+1)\times(N+1)}$. Let ${\mathsf{Mamba}}({\bm{Z}};\bm{\Theta})=({\bm{o}}_{1},\dots,{\bm{o}}_{N+1})\in\mathbb{R}^{(\tilde{d}+1)\times(N+1)}$ be outputs and ${\bm{h}}_{l}^{(i)}$’s be hidden states. For each $i\in[\tilde{d}+1]$ and $l\in[N+1]$, we have

$$ ${\bm{h}}_{l}^{(i)}=\sum_{j=1}^{l}G_{j,l}({\bm{Z}})({\bm{z}}_{j})_{i}{\bm{W}}_{B}{\bm{z}}_{j},\quad{\bm{o}}_{l}[i]=\sum_{j=1}^{l}G_{j,l}({\bm{Z}})({\bm{z}}_{j})_{i}{\bm{z}}_{j}^{\top}{\bm{W}}_{B}^{\top}{\bm{W}}_{C}{\bm{z}}_{l},$ $$

where $G_{j,l}({\bm{Z}})=\sigma\left({\bm{w}}^{\top}{\bm{z}}_{j}+b\right)\prod_{k=j+1}^{l}\left(1-\sigma\left({\bm{w}}^{\top}{\bm{z}}_{k}+b\right)\right)$.

###### Proof of Lemma A.1 .

For each $l\in[N+1]$, we have

$$ $\overline{{\bm{A}}}_{l}=\exp\left(-\mathrm{softplus}({\bm{w}}^{\top}{\bm{z}}_{l}+b){\bm{I}}_{\tilde{d}+1}\right)=\frac{1}{1+\exp({\bm{w}}^{\top}{\bm{z}}_{l}+b)}{\bm{I}}_{\tilde{d}+1}=\left(1-\sigma\left({\bm{w}}^{\top}{\bm{z}}_{l}+b\right)\right){\bm{I}}_{\tilde{d}+1}$ $$

and

$$ $\overline{{\bm{B}}}_{l}=-\left(\overline{{\bm{A}}}_{l}-{\bm{I}}_{\tilde{d}+1}\right){\bm{W}}_{B}{\bm{z}}_{l}\\ =\sigma\left({\bm{w}}^{\top}{\bm{z}}_{l}+b\right){\bm{W}}_{B}{\bm{z}}_{l}.$ $$

We fix any $i\in[\tilde{d}+1]$ and we will prove by applying induction on $l\in[N+1]$.
Let us first consider the case $l=1$. We have

$$ $\displaystyle{\bm{h}}_{1}^{(i)}$ $\displaystyle=\left(1-\sigma\left({\bm{w}}^{\top}{\bm{z}}_{l}+b\right)\right){\bm{h}}_{0}^{(i)}+\sigma\left({\bm{w}}^{\top}{\bm{z}}_{1}+b\right){\bm{W}}_{B}{\bm{z}}_{1}({\bm{z}}_{1})_{i}$ $\displaystyle=\sigma\left({\bm{w}}^{\top}{\bm{z}}_{1}+b\right){\bm{W}}_{B}{\bm{z}}_{1}{\bm{z}}_{1}[i]$ $\displaystyle=G_{1,1}({\bm{Z}}){\bm{z}}_{1}[i],{\bm{W}}_{B}{\bm{z}}_{1}$ $$

and

$$ ${\bm{o}}_{1}[i]=\left({\bm{W}}_{C}{\bm{z}}_{1}\right)^{\top}{\bm{h}}_{1}^{(i)}=\sigma\left({\bm{w}}^{\top}{\bm{z}}_{1}+b\right){\bm{z}}_{1}[i]{\bm{z}}_{1}^{\top}{\bm{W}}_{B}^{\top}{\bm{W}}_{C}{\bm{z}}_{1}=G_{1,1}({\bm{Z}}){\bm{z}}_{1}[i]{\bm{z}}_{1}^{\top}{\bm{W}}_{B}^{\top}{\bm{W}}_{C}{\bm{z}}_{1}.$ $$

Therefore, desired conclusions hold for the case $l=1$.

Next, we assume that our conclusion holds for $l<\tilde{d}+1$.

$$ $\displaystyle{\bm{h}}_{l+1}^{(i)}$ $\displaystyle=\left(1-\sigma\left({\bm{w}}^{\top}{\bm{z}}_{l+1}+b\right)\right){\bm{h}}_{l}^{(i)}+\sigma\left({\bm{w}}^{\top}{\bm{z}}_{l+1}+b\right){\bm{W}}_{B}{\bm{z}}_{l+1}({\bm{z}}_{l+1})_{i}$ $\displaystyle=\left(1-\sigma\left({\bm{w}}^{\top}{\bm{z}}_{l+1}+b\right)\right)\sum_{j=1}^{l}G_{j,l}({\bm{Z}}){\bm{z}}_{j}[i]{\bm{W}}_{B}{\bm{z}}_{j}+G_{l+1,l+1}({\bm{Z}}){\bm{z}}_{l+1}[i]{\bm{W}}_{B}{\bm{z}}_{l+1}$ $\displaystyle=\sum_{j=1}^{l+1}G_{j,l+1}({\bm{Z}}){\bm{z}}_{j}[i]{\bm{W}}_{B}{\bm{z}}_{j}$ $$

and

$$ $\displaystyle{\bm{o}}_{l+1}[i]$ $\displaystyle=\left({\bm{W}}_{C}{\bm{z}}_{l+1}\right)^{\top}{\bm{h}}_{l+1}^{(i)}$ $\displaystyle=\left({\bm{W}}_{C}{\bm{z}}_{l+1}\right)^{\top}\sum_{j=1}^{l+1}G_{j,l+1}({\bm{Z}}){\bm{z}}_{j}[i]{\bm{W}}_{B}{\bm{z}}_{j}$ $\displaystyle=({\bm{o}}_{l+1})_{i}=\sum_{j=1}^{l+1}G_{j,l+1}({\bm{Z}}){\bm{z}}_{j}[i]{\bm{z}}_{j}^{\top}{\bm{W}}_{B}^{\top}{\bm{W}}_{C}{\bm{z}}_{l+1}.$ $$

Therefore, we have the desired conclusions.
∎

###### Lemma A.1 .

###### Proof of Lemma A.1 .

### A.2 High Probability Events

Throughout the proof, we use the term “with high probability” which is defined as follows.

###### Definition A.2 .

We call that an event $E$ occurs *with high probability*, when

$$ $\mathbb{P}[E]\geq 1-d^{-C_{\mathrm{whp}}}$ $$

with a large enough $C_{\mathrm{whp}}>0$.

For example, ${\mathbf{z}}={\mathcal{O}}(\sqrt{\log d})$ for ${\mathbf{z}}\sim{\mathcal{N}}(0,1)$, with high probability, which is a direct consequence of Hoeffding’s inequality. In addition, the intersection of a $\mathrm{poly}(d)$ events also occurs with high probability. We use these property frequently throughout our proof.

The following lemma is useful when we bound some quantities with high probability.

###### Lemma A.3 (Corollary 17 in Oko et al. ( 2024 ) , adapted) .

Let $P$ be a polynomial with degree $\mathrm{deg}(P)$. If $\lVert{\bm{\beta}}\rVert=1$ and ${\bm{x}}\sim{\mathcal{N}}({\bm{0}},{\bm{I}}_{d})$, then $\left|P(\langle{\bm{\beta}},{\bm{x}}\rangle)\right|\lesssim(\log d)^{\mathrm{deg}(P)/2}$ holds with high probability.

This lemma implies that $y_{i}^{t}={\tilde{\mathcal{O}}}(1),\left\|\phi({\bm{x}}_{i}^{t})\right\|,\left\|\phi({\bm{x}}^{t})\right\|={\tilde{\mathcal{O}}}(d)$ holds for any $i\in[N_{\mathrm{pt}}],t\in[T_{\mathrm{pt}}]$, with high probability. We utilize these properties frequently in our proof.

The following lemma provides a high-probability guarantee regarding our input embedding, which is crucial for our analysis.

###### Lemma A.4 .

Let ${\mathbf{x}}_{1},\dots,{\mathbf{x}}_{N}\sim{\mathcal{N}}(0,1)$ and let ${\mathbf{z}}_{1},\dots,{\mathbf{z}}_{N}$ be i.i.d. random variables such that $|{\mathbf{z}}_{i}|\leq C$ with high probability where ${\mathbf{z}}_{i}$ might depend on ${\mathbf{x}}_{i}$. If $N=\tilde{\Omega}(C^{2})$ and $N\leq N^{*}$, then for each $k=0,1,2$,

$$ $\left|\frac{1}{N}\sum_{i=1}^{N}{\mathbf{z}}_{i}\mathrm{He}_{k}({\mathbf{x}}_{i})-\mathbb{E}[{\mathbf{z}}_{1}\mathrm{He}_{k}({\mathbf{x}}_{1})]\right|\leq{\tilde{\mathcal{O}}}\left(CN^{-1/2}\right),$ $$

with high probability. In addition, let ${\bm{x}}_{1}^{\prime},\dots,{\bm{x}}_{N}^{\prime}\sim{\mathcal{N}}(0,1)$, then under the same condition,

$$ $\left|\frac{1}{N}\sum_{i=1}^{N}{\mathbf{z}}_{i}{\mathbf{x}}_{i}{\mathbf{x}}_{i}^{\prime}-\mathbb{E}\left[{\mathbf{z}}_{1}{\mathbf{x}}_{i}{\mathbf{x}}_{i}^{\prime}\right]\right|\leq{\tilde{\mathcal{O}}}\left(CN^{-1/2}\right),$ $$

with high probability.

###### Proof of Lemma A.4 .

Let ${\mathbf{z}}^{\prime}_{i}:=\mathbbm{1}[|{\mathbf{z}}_{i}|\leq C]{\mathbf{z}}_{i}$. Then, ${\mathbf{z}}^{\prime}_{i},{\mathbf{z}}^{\prime}_{i}{\mathbf{x}}_{i},{\mathbf{z}}^{\prime}_{i}\mathrm{He}_{2}({\mathbf{x}}_{i}),{\mathbf{z}}^{\prime}_{i}{\mathbf{x}}_{i}{\mathbf{x}}_{i}^{\prime}$ are $C$-subexponential.
Since $N=\tilde{\Omega}(C^{2})$, for each $k=0,1,2$, we have

$$ $\left|\frac{1}{N}\sum_{i=1}^{N}{\mathbf{z}}^{\prime}_{i}\mathrm{He}_{k}({\mathbf{x}}_{i})-\mathbb{E}[{\mathbf{z}}^{\prime}_{1}\mathrm{He}_{k}({\mathbf{x}}_{i})]\right|\leq{\tilde{\mathcal{O}}}\left(CN^{-1/2}\right),$ $$

with probability and $\sum_{i=1}^{N}{\mathbf{z}}^{\prime}_{i}\mathrm{He}_{k}({\mathbf{x}}_{i})=\sum_{i=1}^{N}{\mathbf{z}}_{i}\mathrm{He}_{k}({\mathbf{x}}_{1})$ with high probability. In addition, we have

$$ $\displaystyle\left|\mathbb{E}[{\mathbf{z}}_{1}\mathrm{He}_{k}({\mathbf{x}}_{i})]-\mathbb{E}[{\mathbf{z}}^{\prime}\mathrm{He}_{k}({\mathbf{x}}_{i})]\right|$ $\displaystyle=\mathbb{E}[\mathbbm{1}[\left|{\mathbf{z}}_{1}\right|\geq C]\mathrm{He}_{k}({\mathbf{x}}_{i})]$ $\displaystyle\leq\mathbb{P}[\mathbbm{1}[\left|{\mathbf{z}}_{1}\right|\geq C]\mathbb{E}\left[\big(\mathrm{He}_{k}({\mathbf{x}}_{1})\big)^{2}\right]^{\frac{1}{2}}$ $\displaystyle\leq\frac{1}{\mathrm{poly}(d)}.$ $$

Therefore, by combining the two bounds above, we have the desired conclusion for the case $k=0,1,2$. Using the same argument, we can also obtain the last conclusion.
∎

###### Definition A.2 .

###### Lemma A.3 (Corollary 17 in Oko et al. ( 2024 ) , adapted) .

###### Lemma A.4 .

###### Proof of Lemma A.4 .

### A.3 Reducing the Information Exponent with Label Transformation

For any function $h$ which is $L^{2}$ integrable with respect to Gaussian measure and $p\in\mathbb{N}\cup\{0\}$, we define $e_{p}(h)\coloneqq\min\{i\in\mathbb{N}:H(f^{i},p)\neq 0\}$.
If this minimum does not exist (i.e., the set is empty), we set $e_{p}(f)=\infty$.
In addition, we define

$$ $\displaystyle\bar{g}_{*}(z):=\begin{cases}\frac{g_{*}(z)}{\rho}&\text{if }\left|\frac{g_{*}(z)}{\rho}\right|\leq\frac{1}{\log d}\\ 0&\text{otherwise}\end{cases}.$ $$

From our choice of $\rho$, $\bar{g}_{*}\left(y_{i}^{t}\right)=g_{*}\left(y_{i}^{t}\right)/\rho$ for all $i\in[N_{\mathrm{pt}}],t\in[T_{\mathrm{pt}}]$, with high probability. We use this frequently in our proof.
We also define the following function, which naturally appears in our analysis:

$$ $A(z):=\frac{1}{2}\left[(\rho\bar{g}_{*}(z)+\tau)\sigma\left(\bar{g}_{*}(z)+\tau/\rho-b\right)+(\rho\bar{g}_{*}(z)-\tau)\sigma\left(\bar{g}_{*}(z)-\tau/\rho-b\right)\right].$ $$

Let $A(z)=\sum_{k=0}^{\infty}\frac{a_{k}}{k!}\mathrm{He}_{k}(z)$ be the Hermite expansion. The following lemma characterizes its Hermite coefficients.

###### Lemma A.5 .

For any $p\in\mathbb{N}\cup\{0\}$, if $e_{p}(g_{*})<\infty$, we have

$$ $d^{C_{b}}a_{p}=\Theta\left(\left(\log d\right)^{-C_{\rho}(e_{p}(g_{*})-1)}\right),$ $$

where hidden constants depend on $g_{*}$ and $p$. In addition, if $e_{p}(g_{*})=\infty$, then $d^{C_{b}}\left|a_{p}\right|\lesssim 1/\mathrm{poly}(d)$.

The following two lemmas are crucial for our proof of Lemma [A.5](https://arxiv.org/html/2510.12026v2#A1.Thmtheorem5).

###### Lemma A.6 (Proposition 6 in Lee et al. ( 2024 ) ) .

For any polynomial $P$, there exist $C_{P},D_{P}>0$ depending only on $P$ such that the following holds.

- •
If $P$ is not an even function, then there exists $i\leq C_{P}$ such that $\left|H(f^{i},1)\right|\geq D_{P}$.
- •
If $P$ is an even function, then there exists $i\leq C_{P}$ such that $\left|H(f^{i},2)\right|\geq D_{P}$.

###### Lemma A.7 .

For any $k\in\mathbb{N}\cup\{0\}$ and $z<-k-2$, we have $\frac{e^{z}}{2}\leq\sigma^{(k)}(z)\leq 2e^{z}$.

###### Proof of Lemma A.7 .

For any $x<0$, we have

$$ $\sigma(x)=\frac{1}{1+\exp(-x)}=1-\frac{1}{1+\exp(x)}=\sum_{j=1}^{\infty}(-1)^{j-1}e^{jx}.$ $$

Therefore, we have

$$ $\sigma^{(k)}(z)=\sum_{j=1}^{\infty}(-1)^{j-1}j^{k}e^{jz}=e^{z}+\sum_{j=2}^{\infty}(-1)^{j-1}j^{k}e^{jz}.$ $$

For each $j\geq 2$, since $\frac{(j+1)^{k}e^{(j+1)z}}{j^{k}e^{jz}}\leq 2^{k}e^{z}$ and $2^{k}e^{z}<\frac{1}{3}$, we have

$$ $\left|\sigma^{(k)}(z)-e^{z}\right|\leq\sum_{j=2}^{\infty}j^{k}e^{jz}\leq 2^{k}e^{2z}\sum_{j=0}^{\infty}\left(2^{k}e^{z}\right)^{j}=\frac{2^{k}e^{2z}}{1-2^{k}e^{z}}\leq\frac{e^{z}}{2}.$ $$

Hence, we have a desired conclusion.
∎

We now prove Lemma [A.5](https://arxiv.org/html/2510.12026v2#A1.Thmtheorem5).

###### Proof of Lemma A.5 .

By applying Taylor’s theorem for $\sigma(\cdot)$ at points $\pm\tau/\rho+b$, for any $z\in\mathbb{R}$, we have

$$ $\displaystyle\quad 2\rho^{-1}A(z)$ $\displaystyle=(\bar{g}_{*}(z)+\tau/\rho)\sigma\left(\bar{g}_{*}(z)+\tau/\rho-b\right)+(\bar{g}_{*}(z)-\tau/\rho)\sigma\left(\bar{g}_{*}(z)-\tau/\rho-b\right)$ $\displaystyle=\sum_{i=0}^{e_{p}(g_{*})-1}(s_{i}+\tilde{s}_{i})\bar{g}_{*}^{i+1}(z)+\big(R(z)+\tilde{R}(z)\big)\bar{g}_{*}^{e_{p}(g_{*})+1}(z)$ $\displaystyle\quad+\tau\left[\sum_{i=0}^{e_{p}(g_{*})-1}(s_{i}-\tilde{s}_{i})\bar{g}_{*}^{i}(z)+\big(R(z)-\tilde{R}(z)\big)\bar{g}_{*}^{e_{p}(g_{*})}(z)\right]$ $$

where $s_{i}=\frac{\sigma^{(i)}(\tau/\rho+b)}{i!},\tilde{s}_{i}=\frac{\sigma^{(i)}(-\tau/\rho+b)}{i!}$ for $i=0,\dots,e_{p}(g_{*})-1$ and

$$ $\left|R(z)\right|,|\tilde{R}(z)|\leq\frac{\max_{t\in[b-1,b+1]}\left|\sigma^{(e_{p}(g_{*}))}(t)\right|}{(e_{p}(g_{*}))!}\leq\frac{2e^{b+1}}{(e_{p}(g_{*}))!}.$ $$

From the definition of $\bar{g}_{*}$, we have

$$ $\displaystyle\quad\sum_{i=0}^{e_{p}(g_{*})-1}(s_{i}+\tilde{s}_{i})\bar{g}_{*}^{i+1}(z)+\tau\sum_{i=0}^{e_{p}(g_{*})-1}(s_{i}-\tilde{s}_{i})\bar{g}_{*}^{i}(z)$ $\displaystyle=\sum_{i=0}^{e_{p}(g_{*})-1}\rho^{-(i+1)}(s_{i}+\tilde{s}_{i})g_{*}^{i+1}(z)+\tau\sum_{i=0}^{e_{p}(g_{*})-1}\rho^{-i}(s_{i}-\tilde{s}_{i})g_{*}^{i}(z)$ $\displaystyle\quad-\left(\sum_{i=0}^{e_{p}(g_{*})-1}\rho^{-(i+1)}(s_{i}+\tilde{s}_{i})g_{*}^{i+1}(z)+\tau\sum_{i=0}^{e_{p}(g_{*})-1}\rho^{-i}(s_{i}-\tilde{s}_{i})g_{*}^{i}(z)\right)\mathbbm{1}\left[\left|\frac{g_{*}(z)}{\rho}\right|\leq\frac{1}{\log d}\right].$ $$

For any $i=0,\dots,e_{p}(g_{*})$, we have

$$ $\displaystyle\left|\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[g_{*}^{i}({\mathbf{z}})\mathbbm{1}\left[\left|\frac{g_{*}(z)}{\rho}\right|\leq\frac{1}{\log d}\right]\right]\right|$ $\displaystyle\leq\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[g_{*}^{2i}({\mathbf{z}})\right]^{\frac{1}{2}}\mathbb{P}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[\left|\frac{g_{*}({\mathbf{z}})}{\rho}\right|\leq\frac{1}{\log d}\right]$ $\displaystyle=o\left(\frac{1}{\mathrm{polylog}(d)}\right).$ $$

Combining this with additivity of $H(\cdot,p)$ and the fact that $\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}[g_{*}({\mathbf{z}})]=0$, we have

$$ $\displaystyle 2\rho^{-1}a_{p}$ $\displaystyle=\rho^{-e_{p}(g_{*})}(s_{e_{p}(g_{*})-1}+\tilde{s}_{e_{p}(g_{*})-1})H\left(g_{*}^{e_{p}(g_{*})},p\right)$ $\displaystyle\quad+H\left((R+\tilde{R})\cdot\bar{g}_{*}^{e_{p}(g_{*})+1},p\right)+\tau H\left((R-\tilde{R})\cdot\bar{g}_{*}^{e_{p}(g_{*})},p\right)\pm o\left(\frac{1}{\mathrm{polylog}(d)}\right).$ $$

From our choice of $b$ and $\rho$, the first term is $\Theta(d^{-C_{b}}(\log d)^{-C_{\rho}e_{p}(g_{*})})$.
Next, we bound the second term. For any $z\in\mathbb{R}$, we have

$$ $\displaystyle\quad\left|H\left((R+\tilde{R})\cdot\bar{g}_{*}^{e_{p}(g_{*})+1},p\right)\right|$ $\displaystyle=\left|\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[\mathrm{He}_{p}({\mathbf{z}})(R({\mathbf{z}})+\tilde{R}({\mathbf{z}}))\bar{g}_{*}^{e_{p}(g_{*})+1}({\mathbf{z}})\right]\right|$ $\displaystyle\leq\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[\left|\mathrm{He}_{p}({\mathbf{z}})(R({\mathbf{z}})+\tilde{R}({\mathbf{z}}))\bar{g}_{*}^{e_{p}(g_{*})+1}({\mathbf{z}})\right|\right]$ $\displaystyle\leq\frac{2e^{b+1}}{(e_{p}(g_{*})+1)!}\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[\mathrm{He}_{p}({\mathbf{z}})^{2}\right]^{\frac{1}{2}}\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[\bar{g}_{*}({\mathbf{z}})^{2e_{p}(g_{*})+2}\right]^{\frac{1}{2}}$ $\displaystyle\leq\frac{2e^{b+1}\rho^{-(e_{p}(g_{*})+1)}}{(e_{p}(g_{*})+1)!}\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[\mathrm{He}_{p}({\mathbf{z}})^{2}\right]^{\frac{1}{2}}\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[g_{*}({\mathbf{z}})^{2e_{p}(g_{*})+2}\right]^{\frac{1}{2}},$ $$

where we apply the Cauchy–Schwarz inequality for the second inequality. Hence, the absolute value of the second term is ${\tilde{\mathcal{O}}}(d^{-C_{b}}(\log d)^{-C_{\rho}(e_{p}(g_{*})+1)})$. Using a similar argument, we can know that the absolute value of the third term is $\Theta\left(d^{-C_{b}}(\log d)^{-C_{\rho}e_{p}(g_{*})}\right)$. Combining with the fact that $\tau$ is small enough, we have our desired conclusion.

Using similar arguments, we can also obtain our conclusion for the case $e_{p}(g_{*})=\infty$.
∎

###### Lemma A.5 .

###### Lemma A.6 (Proposition 6 in Lee et al. ( 2024 ) ) .

###### Lemma A.7 .

###### Proof of Lemma A.7 .

###### Proof of Lemma A.5 .

## Appendix B One-Step Gradient Descent on the Mamba Layer

Let us define the function $\psi:\mathbb{R}^{d+3}\rightarrow\mathbb{R}^{\tilde{d}}$, which we use repeatedly in our proof. It is defined as

$$ $\psi(\bm{\theta},c_{0},c_{1},c_{2})\coloneqq\left[c_{0},c_{1}\bm{\theta}^{\top},\frac{c_{2}\left(\bm{\theta}\odot\bm{\theta}\right)^{\top}}{\sqrt{2}},c_{2}\bm{\theta}[1]\bm{\theta}[2],\dots,c_{2}\bm{\theta}[d-1]\bm{\theta}[d]\right]^{\top}.$ $$

Note that for any vector $\bm{\theta}\in\mathbb{R}^{d}$,

$$ $\left\|\psi(\bm{\theta},c_{0},c_{1},c_{2})\right\|^{2}=c_{0}^{2}+c_{1}^{2}\left\|\bm{\theta}\right\|^{2}+\frac{c_{2}^{2}\left\|\bm{\theta}\right\|^{4}}{2}.$ (3) $$

If we choose $\lambda_{1}=\eta^{-1}$, the updated parameter ${\bm{\gamma}}^{*}$ can be expressed as

$$ $\displaystyle{\bm{\gamma}}^{*}$ $\displaystyle=\frac{2\eta}{T_{1}}\sum_{t\in[T_{1}]}\left[\Big(y^{t}-f\left({\bm{Z}}^{t};{\bm{\gamma}}(0),{\bm{u}}(0),{\bm{v}}(0),{\bm{a}}(0)\right)\Big)\nabla_{\bm{\gamma}}f\left({\bm{Z}}^{t};{\bm{\gamma}}(0),{\bm{u}}(0),{\bm{v}}(0),{\bm{a}}(0)\right)\right]$ $\displaystyle=\frac{2\eta}{T_{1}}\sum_{t\in[T_{1}]}y^{t}\nabla_{\bm{\gamma}}f\left({\bm{Z}}^{t};{\bm{\gamma}}(0),{\bm{u}}(0),{\bm{v}}(0),{\bm{a}}(0)\right)$ $\displaystyle\quad-\frac{2\eta}{T_{1}}\sum_{t\in[T_{1}]}f\left({\bm{Z}}^{t};{\bm{\gamma}}(0),{\bm{u}}(0),{\bm{v}}(0),{\bm{a}}(0)\right)\Big)\nabla_{\bm{\gamma}}f\left({\bm{Z}}^{t};{\bm{\gamma}}(0),{\bm{u}}(0),{\bm{v}}(0),{\bm{a}}(0)\right).$ $$

The initial output evaluated at ${\bm{Z}}^{t}$ can be bounded as

$$ $\displaystyle\quad\left|f\left({\bm{Z}}^{t};{\bm{\gamma}}(0),{\bm{u}}(0),{\bm{v}}(0),{\bm{a}}(0)\right)\right|$ $\displaystyle={\mathrm{ReLU}}\left(N_{\mathrm{pt}}^{-1}\sum_{j=1}^{N_{\mathrm{pt}}}G_{j,n+1}({\bm{Z}})y_{j}^{t}\phi\left({\bm{x}}_{j}^{t}\right)^{\top}\left({\bm{\gamma}}(0)\odot\phi\left({\bm{x}}^{t}\right)\right)\right)$ $\displaystyle\leq N_{\mathrm{pt}}^{-1}\sum_{h=1}^{N_{\mathrm{pt}}}G_{j,n+1}({\bm{Z}})\left|y_{j}^{t}\right|\left\|\phi\left({\bm{x}}_{j}^{t}\right)\right\|\left\|\phi\left({\bm{x}}^{t}\right)\right\|$ $\displaystyle={\tilde{\mathcal{O}}}\left(d^{-C_{b}+2}\right),$ $$

with high probability.

The gradient of ${\bm{\gamma}}$ of output evaluated at ${\bm{Z}}^{t}$ can be calculated as

$$ $\displaystyle\quad\nabla_{\bm{\gamma}}f\left({\bm{Z}}^{t};{\bm{\gamma}}(0),{\bm{u}}(0),{\bm{v}}(0),{\bm{a}}(0)\right)$ $\displaystyle=\mathbbm{1}\left[\sum_{j=1}^{N_{\mathrm{pt}}}G_{j,N_{\mathrm{pt}}+1}\left({\bm{Z}}^{t}\right)y_{j}^{t}\phi\left({\bm{x}}_{j}^{t}\right)^{\top}\left({\bm{\gamma}}(0)\odot\phi\left({\bm{x}}^{t}\right)\right)>0\right]$ $\displaystyle\quad\times\left(N_{\mathrm{pt}}^{-1}\sum_{j=1}^{N_{\mathrm{pt}}}G_{j,N_{\mathrm{pt}}+1}\left({\bm{Z}}^{t}\right)y_{j}^{t}\phi\left({\bm{x}}_{j}^{t}\right)\odot\phi\left({\bm{x}}^{t}\right)\right)$ $$

and its norm can be bounded as

$$ $\displaystyle\left\|\nabla_{\bm{\gamma}}f\left({\bm{Z}}^{t};{\bm{\gamma}}(0),{\bm{u}}(0),{\bm{v}}(0),{\bm{a}}(0)\right)\right\|$ $\displaystyle\leq N_{\mathrm{pt}}^{-1}\sum_{h=1}^{N_{\mathrm{pt}}}G_{j,n+1}({\bm{Z}})\left|y_{j}^{t}\right|\left\|\phi\left({\bm{x}}_{j}^{t}\right)\right\|\left\|\phi\left({\bm{x}}^{t}\right)\right\|$ $\displaystyle={\tilde{\mathcal{O}}}\left(d^{-C_{b}+2}\right),$ $$

with high probability. Therefore, with high probability, we have

$$ ${\bm{\gamma}}^{*}=\frac{2\eta}{T_{1}}\sum_{t\in[T_{1}]}y^{t}\nabla_{\bm{\gamma}}f\left({\bm{Z}}^{t};{\bm{\gamma}}(0),{\bm{u}}(0),{\bm{v}}(0),{\bm{a}}(0)\right)+{\tilde{\mathcal{O}}}\left(\eta d^{-2C_{b}+4}\right).$ $$

Hence, we will focus on estimating the first term.

### B.1 Estimation of Label-Gradient Correlation

We first establish a high-probability guarantee for the term containing context examples.

###### Lemma B.1 .

Let $({\bm{x}}_{1},y_{1},\dots,{\bm{x}}_{N},y_{N},{\bm{x}})$ be a prompt with context length $N\leq N^{*}$ and feature vector ${\bm{\beta}}\in\mathbb{R}^{d}$ and its embedding ${\bm{Z}}\in\mathbb{R}^{(\tilde{d}+1)\times(N+1)}$. Then, the following holds with high probability:

$$ $N^{-1}\sum_{j=1}^{N}G_{j,N+1}\left({\bm{Z}}\right)y_{j}\phi\left({\bm{x}}_{j}\right)=\psi\left({\bm{\beta}},a_{0},a_{1},a_{2}\right)+{\tilde{\mathcal{O}}}\left(d^{-C_{b}+1}N^{-1/2}\right).$ $$

###### Proof of Lemma B.1 .

Note that with high probability, $y_{j}/\rho=\bar{g}_{*}\left(\left\langle{\bm{\beta}},{\bm{x}}_{j}\right\rangle\right)+\zeta_{j}/\rho$ with $\zeta_{j}\sim\mathrm{Unif}(\{-\tau,\tau\})$ for all $j\in[N]$. Condition on this event, we have

$$ $\displaystyle\quad N^{-1}\sum_{j=1}^{N}y_{j}\sigma(y_{j}/\rho+b)\phi\left({\bm{x}}_{j}\right)$ $\displaystyle=N^{-1}\sum_{j=1}^{N}\left[\left(\rho\bar{g}_{*}\left(\left\langle{\bm{\beta}},{\bm{x}}_{j}\right\rangle\right)+\zeta_{j}\right)\sigma\left(\bar{g}_{*}\left(\left\langle{\bm{\beta}},{\bm{x}}_{j}\right\rangle\right)+\zeta_{j}/\rho+b\right)\phi\left({\bm{x}}_{j}\right)\right].$ $$

From Stein’s lemma, we have

$$ $\displaystyle\quad\mathbb{E}\left[N^{-1}\sum_{j=1}^{N}\left[\left(\rho\bar{g}_{*}\left(\left\langle{\bm{\beta}},{\bm{x}}_{j}\right\rangle\right)+\zeta_{j}\right)\sigma\left(\bar{g}_{*}\left(\left\langle{\bm{\beta}},{\bm{x}}_{j}\right\rangle\right)+\zeta_{j}/\rho+b\right)\phi({\bm{x}}_{j}^{t})\right]\right]$ $\displaystyle=\mathbb{E}_{{\bm{x}}\sim{\mathcal{N}}({\bm{0}},{\bm{I}}_{d})}\left[A\left(\langle{\bm{\beta}}^{t},{\bm{x}}\rangle\right)\phi({\bm{x}})\right]$ $\displaystyle=\psi\left({\bm{\beta}}^{t},a_{0},a_{1},a_{2}\right).$ $$

By Lemma [A.4](https://arxiv.org/html/2510.12026v2#A1.Thmtheorem4), with high probability, we have

$$ $\quad\left\|N^{-1}\sum_{j=1}^{N}y_{j}\sigma(y_{j}/\rho+b)\phi\left({\bm{x}}_{j}\right)-\psi\left({\bm{\beta}},a_{0},a_{1},a_{2}\right)\right\|\leq{\tilde{\mathcal{O}}}\left(d^{-C_{b}+1}N^{-1/2}\right).$ $$

In addition, with high probability, we have

$$ $\displaystyle\quad\left\|N^{-1}\sum_{j=1}^{N}G_{j,n+1}\left({\bm{Z}}\right)y_{j}\phi\left({\bm{x}}_{j}\right)-N^{-1}\sum_{j=1}^{N}y_{j}\sigma(y_{j}/\rho+b)\phi\left({\bm{x}}_{j}\right)\right\|$ $\displaystyle=\left\|N^{-1}\sum_{j=1}^{N}\left[y_{j}\sigma(y_{j}/\rho+b)\left(1-\big(1-\sigma(b)\big)\prod_{i=j+1}^{N}\big(1-\sigma(y_{j}/\rho+b)\big)\right)\phi\left({\bm{x}}_{j}\right)\right]\right\|$ $\displaystyle\leq N^{-1}\sum_{j=1}^{N}\left[\left|y_{j}\sigma(y_{i}/\rho+b)\right|\left(1-\big(1-\sigma(b)\big)\prod_{i=j+1}^{N}\big(1-\sigma(y_{i}/\rho+b)\big)\right)\left\|\phi\left({\bm{x}}_{j}\right)\right\|\right]$ $\displaystyle\leq N^{-1}\sum_{j=1}^{N}\left[\left|y_{j}\sigma(y_{j}/\rho+b)\right|\left(1-\big(1-\sigma(2b)\big)^{N^{*}}\right)\left\|\phi\left({\bm{x}}_{j}\right)\right\|\right]$ $\displaystyle\leq{\tilde{\mathcal{O}}}(d^{-2C_{b}+C^{*}}).$ $$

From a large enough choice of $C_{b}$ and the triangular inequality, we have the desired conclusion.
∎

###### Corollary B.2 .

For each $t\in[T_{1}]$, the following holds with high probability:

$$ $\displaystyle\quad N_{\mathrm{pt}}^{-1}\sum_{j=1}^{N_{\mathrm{pt}}}G_{j,N_{\mathrm{pt}}+1}\left({\bm{Z}}^{t}\right)y_{j}^{t}\phi\left({\bm{x}}_{j}^{t}\right)^{\top}\left({\bm{\gamma}}(0)\odot\phi\left({\bm{x}}^{t}\right)\right)$ $\displaystyle=a_{0}\gamma^{2}+a_{1}\left\langle{\bm{\beta}}^{t},{\bm{x}}^{t}\right\rangle+a_{2}\gamma\mathrm{He}_{2}\left(\left\langle{\bm{\beta}}^{t},{\bm{x}}^{t}\right\rangle\right)+{\tilde{\mathcal{O}}}\left(d^{-C_{b}+2}N_{\mathrm{pt}}^{-1/2}\right).$ $$

###### Proof of Corollary B.2 .

From Lemma [B.1](https://arxiv.org/html/2510.12026v2#A2.Thmtheorem1), for each $t\in[T_{1}]$, with high probability, we have

$$ $\displaystyle\quad N_{\mathrm{pt}}^{-1}\sum_{j=1}^{N_{\mathrm{pt}}}G_{j,N_{\mathrm{pt}}+1}\left({\bm{Z}}^{t}\right)y_{j}^{t}\phi\left({\bm{x}}_{j}^{t}\right)^{\top}\left({\bm{\gamma}}(0)\odot\phi\left({\bm{x}}^{t}\right)\right)$ $\displaystyle=a_{0}\gamma^{2}+a_{1}\left\langle{\bm{\beta}}^{t},{\bm{x}}^{t}\right\rangle+a_{2}\gamma\mathrm{He}_{2}\left(\left\langle{\bm{\beta}}^{t},{\bm{x}}^{t}\right\rangle\right)+{\tilde{\mathcal{O}}}\left(d^{-C_{b}+1}N_{\mathrm{pt}}^{-1/2}\right)\left\|\phi\left({\bm{x}}^{t}\right)\right\|$ $\displaystyle=a_{0}\gamma^{2}+a_{1}\left\langle{\bm{\beta}}^{t},{\bm{x}}^{t}\right\rangle+a_{2}\gamma\mathrm{He}_{2}\left(\left\langle{\bm{\beta}}^{t},{\bm{x}}^{t}\right\rangle\right)+{\tilde{\mathcal{O}}}\left(d^{-C_{b}+2}N_{\mathrm{pt}}^{-1/2}\right),$ $$

where we use Lemma [A.3](https://arxiv.org/html/2510.12026v2#A1.Thmtheorem3) and ([3](https://arxiv.org/html/2510.12026v2#A2.E3)) for the last equality.
∎

Next, let us estimate the expectation of the first term that appears in the label-gradient correlation. The following lemma is useful for this purpose.

###### Lemma B.3 .

For any $\delta>0$ with $\delta={\tilde{\mathcal{O}}}(d^{-C_{\delta}})$ for some constant $C>0$, the following holds:

$$ $\mathbb{P}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[\left|a_{0}\gamma^{2}+a_{1}{\mathbf{z}}+a_{2}\gamma\mathrm{He}_{2}\left({\mathbf{z}}\right)\right|<d^{-C_{b}}\delta\right]\leq{\tilde{\mathcal{O}}}\left(d^{-C_{\delta}}\right).$ $$

###### Proof of Lemma B.3 .

For simplicity, let $\delta^{\prime}=d^{-C_{b}}\delta$. Note that $e_{0}(g_{*})=2$. Then, from Lemma [A.5](https://arxiv.org/html/2510.12026v2#A1.Thmtheorem5), we know that $d^{C_{b}}a_{0}=\Theta\left((\log d)^{-2C_{\rho}}\right)$. In addition, for $p=1,2$, $d^{C_{b}}a_{p}=\Theta\left((\log d)^{-C_{\rho}e_{p}(g_{*})}\right)$ if $e_{p}(g_{*})<\infty$ and $d^{C_{b}}a_{p}\lesssim\frac{1}{\mathrm{poly}(d)}$ otherwise.

Case 1: $a_{2}=0$.

In this case, $g_{*}$ is not an even function and then $d^{C_{b}}a_{1},d^{C_{b}}a_{0}=\tilde{\Theta}\left(1\right)$. Without loss of generality, we assume $a_{1}>0$. Then, we have

$$ $\displaystyle\quad\mathbb{P}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[\left|a_{0}\gamma^{2}+a_{1}{\mathbf{z}}+a_{2}\gamma\mathrm{He}_{2}\left({\mathbf{z}}\right)\right|<d^{-C_{b}}\delta\right]$ $\displaystyle=\mathbb{P}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[-\left(\delta^{\prime}+a_{0}\gamma^{2}-a2\gamma\right)/a_{1}<{\mathbf{z}}<\left(\delta^{\prime}-a_{0}\gamma^{2}+a_{2}\gamma\right)/a_{1}\right]$ $\displaystyle\leq\frac{2\delta^{\prime}}{\sqrt{2\pi}a_{1}}={\tilde{\mathcal{O}}}\left(d^{-C_{\delta}}\right).$ $$

Case 2: $a_{2}\neq 0$.

Without loss of generality, we assume $a_{2}>0$. Then, we have

$$ $\displaystyle\quad\mathbb{P}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[\left|a_{0}\gamma^{2}+a_{1}{\mathbf{z}}+a_{2}\gamma\mathrm{He}_{2}({\mathbf{z}})\right|<d^{-C_{b}}\delta\right]$ $\displaystyle=\mathbb{P}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[\frac{-a_{1}-\sqrt{a_{1}^{2}+4a_{2}\gamma(a_{2}\gamma-a_{0}\gamma^{2}+\delta^{\prime})}}{2a_{2}\gamma}<{\mathbf{z}}\right]$ $\displaystyle\quad-\mathbb{P}_{{\mathbf{z}}\sim{\mathcal{N}}(0,z)}\left[\frac{-a_{1}-\sqrt{a_{1}^{2}+4a_{2}\gamma(a_{2}\gamma-a_{0}\gamma^{2}-\delta^{\prime})}}{2a_{2}\gamma}<{\mathbf{z}}\right]$ $\displaystyle\quad+\mathbb{P}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[\frac{-a_{1}+\sqrt{a_{1}^{2}+4a_{2}\gamma(a_{2}\gamma-a_{0}\gamma^{2}-\delta^{\prime})}}{2a_{2}\gamma}<{\mathbf{z}}\right]$ $\displaystyle\quad-\mathbb{P}_{{\mathbf{z}}\sim{\mathcal{N}}(0,z)}\left[\frac{-a_{1}+\sqrt{a_{1}^{2}+4a_{2}\gamma(a_{2}\gamma-a_{0}\gamma^{2}+\delta^{\prime})}}{2a_{2}\gamma}<{\mathbf{z}}\right]$ $\displaystyle\leq\frac{\sqrt{a_{1}^{2}+4a_{2}\gamma(a_{2}\gamma-a_{0}\gamma^{2}+\delta^{\prime})}-\sqrt{a_{1}^{2}+4a_{2}\gamma(a_{2}\gamma-a_{0}\gamma^{2}-\delta^{\prime})}}{\sqrt{2\pi}a_{2}\gamma}$ $\displaystyle=\frac{4\delta^{\prime}}{\sqrt{2\pi}\left(\sqrt{a_{1}^{2}+4a_{2}\gamma(a_{2}\gamma-a_{0}\gamma^{2}+\delta^{\prime})}+\sqrt{a_{1}^{2}+4a_{2}\gamma(a_{2}\gamma-a_{0}\gamma^{2}-\delta^{\prime})}\right)}.$ $$

For the case $g_{*}$ is not an even function, then $d^{C_{b}}a_{0},d^{C_{b}}a_{1}=\tilde{\Theta}(1)$ and $d^{C_{b}}\left|a_{2}\right|\lesssim 1/\mathrm{poly}(d)$. If $g_{*}$ is an even function, then $d^{C_{b}}a_{0},d^{C_{b}}a_{2}=\tilde{\Theta}(1)$ and $d^{C_{b}}a_{1}\lesssim 1/\mathrm{poly}(d)$. In both cases, we can check that the term above is ${\tilde{\mathcal{O}}}(d^{-C_{\delta}})$.
∎

For each $t\in[T_{1}]$, define an event $E_{t}$ such that

$$ $\displaystyle\quad\mathbbm{1}\left[N_{\mathrm{pt}}^{-1}\sum_{j=1}^{N_{\mathrm{pt}}}G_{j,N_{\mathrm{pt}}+1}\left({\bm{Z}}^{t}\right)y_{j}^{t}\phi\left({\bm{x}}_{j}^{t}\right)^{\top}{\bm{\gamma}}(0)\phi\left({\bm{x}}^{t}\right)>0\right]$ $\displaystyle\neq\mathbbm{1}\left[a_{0}\gamma^{2}+a_{1}\left\langle{\bm{\beta}}^{t}{\bm{x}}^{t}\right\rangle+a_{2}\gamma\mathrm{He}_{2}\left(\langle{\bm{\beta}}^{t},{\bm{x}}^{t}\rangle\right)>0\right].$ $$

From Corollary [B.2](https://arxiv.org/html/2510.12026v2#A2.Thmtheorem2) and Lemma [B.3](https://arxiv.org/html/2510.12026v2#A2.Thmtheorem3), we have

$$ $\displaystyle\mathbb{P}_{{\bm{Z}}^{t}}[E_{t}]$ $\displaystyle\leq\mathbb{P}_{{\bm{Z}}^{t}}\left[\left|a_{0}\gamma^{2}+a_{1}\left\langle{\bm{\beta}}^{t},{\bm{x}}^{t}\right\rangle+a_{2}\gamma\mathrm{He}_{2}\left(\left\langle{\bm{\beta}}^{t},{\bm{x}}^{t}\right\rangle\right)\right|<{\tilde{\mathcal{O}}}\left(d^{-C_{b}+2}N_{\mathrm{pt}}^{-1/2}\right)\right]+\frac{1}{\mathrm{poly}(d)}$ $\displaystyle={\tilde{\mathcal{O}}}\left(d^{2}N_{\mathrm{pt}}^{-1/2}\right).$ $$

Combining with Corollary [B.2](https://arxiv.org/html/2510.12026v2#A2.Thmtheorem2), with probability at least $1-{\tilde{\mathcal{O}}}\left(d^{2}T_{1}N_{\mathrm{pt}}^{-1/2}\right)$ the following holds: For any $t\in[T_{1}]$, we have

$$ $\displaystyle\quad y^{t}\nabla_{\bm{\gamma}}f\left({\bm{Z}}^{t};{\bm{\gamma}}(0),{\bm{u}}(0),{\bm{v}}(0),{\bm{a}}(0)\right)$ $\displaystyle=y^{t}\mathbbm{1}\left[N_{\mathrm{pt}}^{-1}\sum_{j=1}^{N_{\mathrm{pt}}}G_{j,N_{\mathrm{pt}}+1}\left({\bm{Z}}^{t}\right)y_{j}^{t}\phi\left({\bm{x}}_{j}^{t}\right)^{\top}\left({\bm{\gamma}}(0)\odot\phi\left({\bm{x}}^{t}\right)\right)>0\right]$ $\displaystyle\quad\times\left(N_{\mathrm{pt}}^{-1}\sum_{j=1}G_{j,N_{\mathrm{pt}}+1}\left({\bm{Z}}^{t}\right)y_{j}^{t}\phi\left({\bm{x}}_{j}^{t}\right)\odot\phi\left({\bm{x}}^{t}\right)\right)$ $\displaystyle=y^{t}\mathbbm{1}\left[a_{0}\gamma^{2}+a_{1}\left\langle{\bm{\beta}}^{t},{\bm{x}}^{t}\right\rangle+a_{2}\gamma\mathrm{He}_{2}\left(\left\langle{\bm{\beta}}^{t},{\bm{x}}^{t}\right\rangle\right)>0\right]\phi({\bm{x}}^{t})\odot\psi\left({\bm{\beta}}^{t},a_{0},a_{1},a_{2}\right)$ $\displaystyle\quad+{\bm{n}}\left({\bm{Z}}^{t}\right)y^{t}\mathbbm{1}\left[a_{0}\gamma^{2}+a_{1}\left\langle{\bm{\beta}}^{t},{\bm{x}}^{t}\right\rangle+a_{2}\gamma\mathrm{He}_{2}\left(\left\langle{\bm{\beta}}^{t},{\bm{x}}^{t}\right\rangle\right)>0\right]\phi({\bm{x}}^{t})\odot\psi\left({\bm{\beta}}^{t},a_{0},a_{1},a_{2}\right),$ $$

where $\left\|{\bm{n}}({\bm{Z}}^{t})\right\|={\tilde{\mathcal{O}}}\left(d^{-C_{b}+1}N_{\mathrm{pt}}^{-1/2}\right)$ with high probability. With high probability, the following holds for all $t\in[T_{1}]$:

$$ $\displaystyle\quad\left\|y^{t}\mathbbm{1}\left[a_{0}\gamma^{2}+a_{1}\left\langle{\bm{\beta}}^{t},{\bm{x}}^{t}\right\rangle+a_{2}\gamma\mathrm{He}_{2}\left(\left\langle{\bm{\beta}}^{t},{\bm{x}}^{t}\right\rangle\right)>0\right]\phi\left({\bm{x}}^{t}\right)\odot{\bm{n}}({\bm{Z}}^{t})\right\|$ $\displaystyle\leq\left|y^{t}\right|\left\|{\bm{n}}\left({\bm{Z}}^{t}\right)\right\|\left\|\phi\left({\bm{x}}^{t}\right)\right\|$ $\displaystyle={\tilde{\mathcal{O}}}\left(d^{-C_{b}+2}N_{{\mathrm{pt}}}^{-1/2}\right).$ $$

###### Lemma B.1 .

###### Proof of Lemma B.1 .

###### Corollary B.2 .

###### Proof of Corollary B.2 .

###### Lemma B.3 .

###### Proof of Lemma B.3 .

#### Estimation of label-gradient correlation.

With probability at least $1-{\tilde{\mathcal{O}}}\left(d^{2}T_{1}N_{\mathrm{pt}}^{-\frac{1}{2}}\right)$, the following holds for all $t\in[T_{1}]$:

$$ $\displaystyle\quad y^{t}\nabla_{\bm{\gamma}}f\left({\bm{Z}}^{t};{\bm{\gamma}}(0),{\bm{u}}(0),{\bm{v}}(0),{\bm{a}}(0)\right)$ $\displaystyle=y^{t}\mathbbm{1}\left[a_{0}\gamma^{2}+a_{1}\left\langle{\bm{\beta}}^{t},{\bm{x}}^{t}\right\rangle+a_{2}\gamma\mathrm{He}_{2}\left(\left\langle{\bm{\beta}}^{t},{\bm{x}}^{t}\right\rangle\right)>0\right]\phi({\bm{x}}^{t})\odot\psi\left({\bm{\beta}}^{t},a_{0},a_{1},a_{2}\right)$ $\displaystyle\quad+{\tilde{\mathcal{O}}}\left(d^{-C_{b}+2}N_{\mathrm{pt}}^{-1/2}\right).$ $$

### B.2 Characterization of Updated Parameter

In this step, we characterize the updated parameter by establishing concentration results.

Note that every entry of $\psi\left({\bm{\beta}}^{t},a_{0},a_{1},a_{2}\right)$ are ${\tilde{\mathcal{O}}}(d^{-C_{b}})$-bounded by Lemma [A.5](https://arxiv.org/html/2510.12026v2#A1.Thmtheorem5). From Lemma [A.4](https://arxiv.org/html/2510.12026v2#A1.Thmtheorem4), with high probability, we have

$$ $\displaystyle\quad\left\|\frac{1}{T_{1}}\sum_{t=1}^{T_{1}}y^{t}\mathbbm{1}\left[a_{0}\gamma^{2}+a_{1}\left\langle{\bm{\beta}}^{t},{\bm{x}}^{t}\right\rangle+a_{2}\gamma\mathrm{He}_{2}\left(\left\langle{\bm{\beta}}^{t},{\bm{x}}^{t}\right\rangle\right)\right]\phi\left({\bm{x}}^{t}\right)\odot\psi\left({\bm{\beta}}^{t},a_{0},a_{1},a_{2}\right)-{\bm{c}}\right\|$ $\displaystyle={\tilde{\mathcal{O}}}\left(d^{-C_{b}+1}T_{1}^{-1/2}\right),$ $$

where

$$ ${\bm{c}}:=\mathbb{E}\left[y^{1}\mathbbm{1}\left[a_{0}\gamma^{2}+a_{1}\left\langle{\bm{\beta}}^{1},{\bm{x}}^{1}\right\rangle+a_{2}\gamma\mathrm{He}_{2}\left(\left\langle{\bm{\beta}}^{1},{\bm{x}}^{1}\right\rangle\right)>0\right]\phi\left({\bm{x}}^{1}\right)\odot\psi\left({\bm{\beta}}^{1},a_{0},a_{1},a_{2}\right)\right].$ $$

Define $B:\mathbb{R}\rightarrow\mathbb{R}$ as $B(z)=g_{*}(z)\mathbbm{1}[a_{0}\gamma^{2}+a_{1}z+a_{2}\gamma z^{2}>0]$ and denote its Hermite expansion as $B(z)=\sum_{k=0}^{\infty}\frac{b_{k}}{k!}\mathrm{He}_{k}(z)$. Then, we have

$$ $\displaystyle{\bm{c}}$ $\displaystyle=\mathbb{E}_{{\bm{\beta}}\sim\mathrm{Unif}(S_{r})}\left[\psi\left({\bm{\beta}},a_{0},a_{1},a_{2}\right)\odot\mathbb{E}_{{\bm{x}}\sim{\mathcal{N}}({\bm{0}},{\bm{I}}_{d})}\left[B({\bm{\beta}})\phi({\bm{x}})\right]\right]$ $\displaystyle=\mathbb{E}_{{\bm{\beta}}\sim\mathrm{Unif}(S_{r})}\left[\psi\left({\bm{\beta}},a_{0},a_{1},a_{2}\right)\odot\psi\left({\bm{\beta}},b_{0},b_{1},b_{2}\right)\right].$ $$

Therefore, we conclude that

$$ $\displaystyle\quad\frac{1}{T_{1}}\sum_{t=1}^{T_{1}}y^{t}\nabla_{\bm{\gamma}}f\left({\bm{Z}}^{t};{\bm{\gamma}}(0),{\bm{u}}(0),{\bm{v}}(0),{\bm{a}}(0)\right)$ $\displaystyle=\mathbb{E}_{{\bm{\beta}}\sim\mathrm{Unif}(S_{r})}\left[\psi\left({\bm{\beta}},a_{0},a_{1},a_{2}\right)\odot\psi\left({\bm{\beta}},b_{0},b_{1},b_{2}\right)\right]$ $\displaystyle\quad+{\tilde{\mathcal{O}}}\left(d^{-C_{b}+2}N_{\mathrm{pt}}^{-1/2}\right)+{\tilde{\mathcal{O}}}\left(d^{-C_{b}+1}T_{1}^{-1/2}\right),$ $$

with probability at least $1-{\tilde{\mathcal{O}}}\left(d^{2}T_{1}N_{\mathrm{pt}}^{-1/2}\right)$.

The remaining step is to characterize the Hermite coefficients $b_{0},b_{1},b_{2}$, and the following lemma is useful.

###### Lemma B.4 .

For any non zero polynomial $P$ independent of $r$ and $d$, the following holds except for the cases $g_{*}$ is even function and $P$ is an odd function.:

$$ $\left|\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\mathbbm{1}[a_{0}\gamma^{2}+a_{1}{\mathbf{z}}+a_{2}\gamma\mathrm{He}_{2}({\mathbf{z}})>0]\right]\right|\gtrsim\frac{1}{\mathrm{polylog}(d)}.$ $$

Here, dependency of $g_{*}$ appears in $a_{0},a_{1},a_{2}$.

###### Proof of Lemma B.4 .

Note that $e_{0}(g_{*})=2$. Then, from Lemma [A.5](https://arxiv.org/html/2510.12026v2#A1.Thmtheorem5), we know that $d^{C_{b}}a_{0}=\Theta\left((\log d)^{-2C_{\rho}}\right)$. In addition, for $p=1,2$, $d^{C_{b}}a_{p}=\Theta\left((\log d)^{-C_{\rho}e_{p}(g_{*})}\right)$ if $e_{p}(g_{*})<\infty$ and $d^{C_{b}}a_{p}\lesssim\frac{1}{\mathrm{poly}(d)}$ otherwise.

Case 1: $g_{*}$ is not an even function and $a_{2}=0$.

In this case, $a_{1}\neq 0$. We assume $a_{1}>0$, and we can also prove the case $a_{1}<0$ similarly. We have

$$ $\displaystyle\quad\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\mathbbm{1}[a_{0}\gamma^{2}+a_{1}{\mathbf{z}}>0]\right]$ $\displaystyle=\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\right]-\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\mathbbm{1}[{\mathbf{z}}<0])\right]-\frac{1}{\sqrt{2\pi}}\int_{0}^{a_{0}\gamma^{2}/a_{1}}P(z)e^{-\frac{z^{2}}{2}}\mathrm{d}z.$ $$

From our choice of $\gamma$, $a_{0}\gamma^{2}/a_{1}=1/\mathrm{polylog}(d)$ and we have

$$ $\left|\int_{0}^{a_{0}\gamma^{2}/a_{1}}P(z)e^{-\frac{z^{2}}{2}}\mathrm{d}z\right|\leq\frac{a_{0}\gamma^{2}}{a_{1}}\max_{z\in[-1,1]}\left|P(z)\right|\lesssim\frac{1}{\mathrm{polylog}(d)}$ $$

and this provides desired conclusion for the case $\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\right]\neq\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\mathbbm{1}[{\mathbf{z}}<0]\right]$. For the case $\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\right]=\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\mathbbm{1}[{\mathbf{z}}<0]\right]$, it suffices to show that

$$ $\left|\int_{0}^{a_{0}\gamma^{2}/a_{1}}P(z)e^{-\frac{z^{2}}{2}}\mathrm{d}z\right|\gtrsim\frac{1}{\mathrm{polylog}(d)}.$ $$

Since $a_{0}\gamma^{2}/a_{1}=1/\mathrm{polylog}(d)$, $P(z)$ is monotone and does not change its sign in $\left[0,a_{0}\gamma^{2}/a_{1}\right]$. Let $Q$ be the degree of $P$ and $q$ be the smallest degree that has non zero coefficient in $P$ and let $P(z)=\sum_{k=q}^{Q}p_{k}z^{k}$. Then, we have

$$ $\displaystyle\left|\int_{0}^{a_{0}\gamma^{2}/a_{1}}P(z)e^{-\frac{z^{2}}{2}}\mathrm{d}z\right|$ $\displaystyle=\left|\int_{0}^{a_{0}\gamma^{2}/a_{1}}\left|P(z)\right|e^{-\frac{z^{2}}{2}}\mathrm{d}z\right|$ $\displaystyle\geq e^{-\frac{1}{2}}\left|\int_{0}^{a_{0}\gamma^{2}/a_{1}}\left|P(z)\right|\mathrm{d}z\right|$ $\displaystyle\geq e^{-\frac{1}{2}}\left|\sum_{k=q}^{Q}\frac{p_{k}}{k+1}\left(\frac{a_{0}\gamma^{2}}{a_{1}}\right)\right|$ $\displaystyle\asymp\left(\frac{a_{0}\gamma^{2}}{a_{1}}\right)^{q+1}\gtrsim\frac{1}{\mathrm{polylog}(d)}.$ $$

Hence, we have the desired conclusion.

Case 2: $g_{*}$ is not an even function and $a_{2}\neq 0$.

In this case, $a_{1},a_{2}\neq 0$. We assume $a_{2}>0$ and we can prove the case $a_{2}<0$ using similar argument.
Note that

$$ $\displaystyle\quad\left|\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\mathbbm{1}\left[a_{0}\gamma^{2}+a_{1}{\mathbf{z}}+a_{2}\gamma\mathrm{He}_{2}({\mathbf{z}})>0\right]\right]\right|$ $\displaystyle\geq\left|\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\mathbbm{1}\left[a_{0}\gamma^{2}+a_{1}{\mathbf{z}}+a_{2}\gamma\mathrm{He}_{2}({\mathbf{z}})>0\wedge{\mathbf{z}}>-\sqrt{\log d}\right]\right]\right|$ $\displaystyle\quad-\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\big[\left|P({\mathbf{z}})\right|\mathbbm{1}[z\leq-\log d]\big]$ $\displaystyle\geq\left|\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\mathbbm{1}\left[a_{0}\gamma^{2}+a_{1}{\mathbf{z}}+a_{2}\gamma\mathrm{He}_{2}({\mathbf{z}})>0\wedge{\mathbf{z}}>-\sqrt{\log d}\right]\right]\right|$ $\displaystyle\quad-\left(\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})^{2}\right]\right)^{\frac{1}{2}}\left(\mathbb{P}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[z\leq-\sqrt{\log d}\right]\right)^{\frac{1}{2}}.$ $$

Since $\mathbb{P}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}[z<-\log d]=o(1/\mathrm{polylog}(d))$, it suffices to show that

$$ $\left|\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\mathbbm{1}\left[a_{0}\gamma^{2}+a_{1}{\mathbf{z}}+a_{2}\gamma\mathrm{He}_{2}({\mathbf{z}})>0\wedge{\mathbf{z}}>-\sqrt{\log d}\right]\right]\right|\gtrsim\frac{1}{\mathrm{polylog}(d)}.$ $$

From our choice of $\gamma$ and Lemma [A.5](https://arxiv.org/html/2510.12026v2#A1.Thmtheorem5), we have $\theta^{-}:=\frac{-a_{1}-\sqrt{a_{1}^{2}-4a_{2}(a_{0}\gamma-a_{2})\gamma^{2}}}{2a_{2}\gamma}<-\sqrt{\log d}$. In addition, define

$$ $\theta^{+}\coloneqq\frac{-a_{1}+\sqrt{a_{1}^{2}-4a_{2}(a_{0}\gamma-a_{2})\gamma^{2}}}{2a_{2}\gamma}\\ =\frac{2(a_{0}\gamma-a_{2})\gamma}{a_{1}+\sqrt{a_{1}^{2}-4a_{2}(a_{0}\gamma-a_{2})}},$ $$

then $\left|\theta^{+}\right|\lesssim 1/\mathrm{polylog}(d)$.
Therefore, we have

$$ $\displaystyle\quad\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\mathbbm{1}[a_{0}\gamma^{2}+a_{1}{\mathbf{z}}+a_{2}\gamma\mathrm{He}_{2}({\mathbf{z}})>0\wedge{\mathbf{z}}>-\sqrt{\log d}]\right]$ $\displaystyle=\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\mathbbm{1}\left[\theta^{+}\leq{\mathbf{z}}\right]\right]$ $\displaystyle=\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\right]-\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\mathbbm{1}[{\mathbf{z}}<0])\right]-\frac{1}{\sqrt{2\pi}}\int_{0}^{\theta^{+}}P(z)e^{-\frac{z^{2}}{2}}\mathrm{d}z.$ $$

Note that

$$ $\left|\int_{0}^{\theta^{+}}P(z)e^{-\frac{z^{2}}{2}}dz\right|\leq\left|\theta^{+}\right|\max_{z\in[-1,1]}\left|P(z)\right|\lesssim\frac{1}{\mathrm{polylog}(d)}$ $$

and this provides desired conclusion for the case $\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\right]\neq\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\mathbbm{1}[{\mathbf{z}}<0]\right]$. For the case $\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\right]=\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\mathbbm{1}[{\mathbf{z}}<0]\right]$, it suffices to show that

$$ $\left|\int_{0}^{\theta^{+}}P(z)e^{-\frac{z^{2}}{2}}dz\right|\gtrsim\frac{1}{\mathrm{polylog}(d)}.$ $$

Since $\theta^{+}\lesssim 1/\mathrm{polylog}(d)$, $P(z)$ is monotone and does not change its sign in $\left[0,\theta^{+}\right]$. Let $Q$ be the degree of $P$ and $q$ be the smallest degree that has non zero coefficient in $P$ and let $P(z)=\sum_{k=q}^{Q}p_{k}z^{k}$. Then, we have

$$ $\displaystyle\left|\int_{0}^{\theta^{+}}P(z)e^{-\frac{z^{2}}{2}}\mathrm{d}z\right|$ $\displaystyle=\left|\int_{0}^{\theta^{+}}\left|P(z)\right|e^{-\frac{z^{2}}{2}}\mathrm{d}z\right|$ $\displaystyle\geq e^{-\frac{1}{2}}\left|\int_{0}^{\theta^{+}}\left|P(z)\right|\mathrm{d}z\right|$ $\displaystyle\geq e^{-\frac{1}{2}}\left|\sum_{k=q}^{Q}\frac{p_{k}}{k+1}\left(\theta^{+}\right)^{k}\right|$ $\displaystyle\asymp\left(\theta^{+}\right)^{q+1}\gtrsim\frac{1}{\mathrm{polylog}(d)}.$ $$

Hence, we have desired conclusion.

Case 3: $g_{*}$ is an even function.

In this case, since $e_{1}(g_{*})=\infty$, $\left|a_{1}\right|\lesssim 1/\mathrm{poly}(d)$.
We assume $a_{2}>0$ and we can prove the case $a_{2}<0$ using similar arguments. Let $P_{\mathrm{even}}$ denote the even part of $P$. Then, we have

$$ $\displaystyle\quad\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}[P({\mathbf{z}})\mathbbm{1}[a_{0}\gamma^{2}+a_{1}{\mathbf{z}}+a_{2}\gamma\mathrm{He}_{2}({\mathbf{z}})>0]]$ $\displaystyle=\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\mathbbm{1}\left[{\mathbf{z}}>\theta^{+}\vee{\mathbf{z}}<-\theta^{-}\right]\right]$ $\displaystyle=\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P({\mathbf{z}})\mathbbm{1}\left[{\mathbf{z}}>\sqrt{1-a_{0}\gamma/a_{2}}\vee{\mathbf{z}}<-\sqrt{1-a_{0}\gamma/a_{2}}\right]\right]$ $\displaystyle\quad+\frac{1}{\sqrt{2\pi}}\int_{\theta^{+}}^{\sqrt{1-a_{0}\gamma/a_{2}}}P(z)e^{-\frac{z^{2}}{2}}\mathrm{d}z+\frac{1}{\sqrt{2\pi}}\int^{\theta^{-}}_{-\sqrt{1-a_{0}\gamma/a_{2}}}P(z)e^{-\frac{z^{2}}{2}}\mathrm{d}z$ $\displaystyle=2\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P_{\mathrm{even}}({\mathbf{z}})\mathbbm{1}\left[{\mathbf{z}}>\sqrt{1-a_{0}\gamma/a_{2}}\right]\right]$ $\displaystyle\quad+\frac{1}{\sqrt{2\pi}}\int_{\theta^{+}}^{\sqrt{1-a_{0}\gamma/a_{2}}}P(z)e^{-\frac{z^{2}}{2}}\mathrm{d}z+\frac{1}{\sqrt{2\pi}}\int^{\theta^{-}}_{-\sqrt{1-a_{0}\gamma/a_{2}}}P(z)e^{-\frac{z^{2}}{2}}\mathrm{d}z$ $\displaystyle=\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P_{\mathrm{even}}({\mathbf{z}})\right]-2\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[P_{\mathrm{even}}({\mathbf{z}})\mathbbm{1}[0<{\mathbf{z}}<1]\right]$ $\displaystyle\quad-\frac{2}{\sqrt{2\pi}}\int_{1}^{\sqrt{1-a_{0}\gamma/a_{2}}}P_{\mathrm{even}}(z)e^{-\frac{z^{2}}{2}}\mathrm{d}z$ $\displaystyle\quad+\underbrace{\frac{1}{\sqrt{2\pi}}\int_{\theta^{+}}^{\sqrt{1-a_{0}\gamma/a_{2}}}P(z)e^{-\frac{z^{2}}{2}}\mathrm{d}z+\frac{1}{\sqrt{2\pi}}\int^{\theta^{-}}_{-\sqrt{1-a_{0}\gamma/a_{2}}}P(z)e^{-\frac{z^{2}}{2}}\mathrm{d}z}_{(*)}.$ $$

From our choice of $\gamma$, we have

$$ $\displaystyle\left|\int_{1}^{\sqrt{1-a_{0}\gamma/a_{2}}}P_{\mathrm{even}}(z)e^{-\frac{z^{2}}{2}}\mathrm{d}z\right|$ $\displaystyle\leq\left|\int_{1}^{\sqrt{1-a_{0}\gamma/a_{2}}}\left|P_{\mathrm{even}}(z)\right|\mathrm{d}z\right|$ $\displaystyle\leq\left|\sqrt{1-a_{0}\gamma/a_{2}}-1\right|\max_{z\in[0,2]}\left|P_{\mathrm{even}}(z)\right|$ $\displaystyle\lesssim\frac{1}{\mathrm{polylog}(d)}.$ $$

Since $\left|a_{1}\right|\lesssim 1/\mathrm{poly}(d)$, we have $\left|\sqrt{1-a_{0}\gamma/a_{2}}-\theta^{+}\right|,\left|-\sqrt{1-a_{0}\gamma/a_{2}}-\theta^{-}\right|\lesssim 1/\mathrm{poly}(d)$ and using the same argument above, we obtain that $|(*)|\lesssim 1/\mathrm{poly}(d)$.

Hence, we obtain the conclusion if $\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}[P_{\mathrm{even}}({\mathbf{z}})]\neq 2\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}[P_{\mathrm{even}}({\mathbf{z}})\mathbbm{1}[0<{\mathbf{z}}<1]]$. For the case $\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}[P_{\mathrm{even}}({\mathbf{z}})]=2\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}[P_{\mathrm{even}}({\mathbf{z}})\mathbbm{1}[0<{\mathbf{z}}<1]]$, it is enough to show that

$$ $\left|\int_{1}^{\sqrt{1-a_{0}\gamma/2}}P_{\mathrm{even}}(z)e^{-\frac{z^{2}}{2}}dz\right|\gtrsim\frac{1}{\mathrm{polylog}(d)}.$ $$

From our small choice of $\gamma$, $P_{\mathrm{even}}$ is monotone and does not change its sign in $[1,\sqrt{1-a_{0}\gamma/a_{2}}]$(or $[\sqrt{1-a_{0}\gamma/a_{2}},1]$. Let $P_{\mathrm{even}}(z)=\sum_{k=q^{\prime}}^{Q^{\prime}}p^{\prime}_{k}(z-1)^{k}$ with $p^{\prime}_{q^{\prime}},p^{\prime}_{Q^{\prime}}\neq 0$. Then, we have

$$ $\displaystyle\left|\int_{1}^{\sqrt{1-a_{0}\gamma/a_{2}}}P_{\mathrm{even}}(z)e^{-\frac{z^{2}}{2}}\mathrm{d}z\right|$ $\displaystyle=\left|\int_{1}^{\sqrt{1-a_{0}\gamma/a_{2}}}\left|P_{\mathrm{even}}(z)\right|e^{-\frac{z^{2}}{2}}\mathrm{d}z\right|$ $\displaystyle\geq e^{-2}\left|\sum_{k=q^{\prime}}^{Q^{\prime}}\frac{p^{\prime}_{k}}{k+1}\left(\sqrt{1-a_{0}\gamma/a_{2}}-1\right)^{k}\right|$ $\displaystyle\asymp\left|\sqrt{1-a_{0}\gamma/a_{2}}-1\right|^{q^{\prime}}\gtrsim\frac{1}{\mathrm{polylog}(d)}.$ $$

Therefore, we have our desired conclusion.
∎

By Lemma [B.4](https://arxiv.org/html/2510.12026v2#A2.Thmtheorem4) with $g_{*}(z),g_{*}(z)z,g_{*}(z)\mathrm{He}_{2}(z)$, we have $b_{0},b_{2}=\tilde{\Theta}(1)$ and $b_{1}=\tilde{\Theta}(1)$ if $g_{*}$ is not an even function. We will show that $b_{1}=1/\mathrm{poly}(d)$ if $g_{*}$ is an even function. In this case, $a_{2}\neq 0$. Without loss of generality, we assume $a_{2}>0$. Then, we have

$$ $\displaystyle\quad 2\left|\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[g_{*}(z)z\mathbbm{1}[a_{0}\gamma^{2}+a_{1}{\mathbf{z}}+a_{2}\gamma\mathrm{He}_{2}({\mathbf{z}})>0]\right]\right|$ $\displaystyle=\Big|\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[g_{*}(z)z\mathbbm{1}[a_{0}\gamma^{2}+a_{1}{\mathbf{z}}+a_{2}\gamma\mathrm{He}_{2}({\mathbf{z}})>0]\right]$ $\displaystyle\quad-\mathbb{E}_{{\mathbf{z}}\sim{\mathcal{N}}(0,1)}\left[g_{*}(z)z\mathbbm{1}[a_{0}\gamma^{2}-a_{1}{\mathbf{z}}+a_{2}\gamma\mathrm{He}_{2}({\mathbf{z}})>0]\right]\Big|$ $\displaystyle\leq\frac{1}{\sqrt{2\pi}}\int_{\theta_{-}^{+}}^{\theta_{+}^{+}}\left|g_{*}(z)z\right|\mathrm{d}z+\frac{1}{\sqrt{2\pi}}\int_{\theta_{-}^{-}}^{\theta_{+}^{-}}\left|g_{*}(z)z\right|\mathrm{d}z,$ $$

where $\theta_{+}^{+}$, $\theta_{-}^{+}$, $\theta_{+}^{-}$, and $\theta_{-}^{-}$ are defined as follows:

$$ $\displaystyle\theta_{+}^{+}\coloneqq\frac{|a_{1}|}{2a_{2}\gamma}+\sqrt{\left(\frac{a_{1}}{2a_{2}\gamma}\right)^{2}+1-\frac{a_{1}\gamma}{a_{2}}},$ $\displaystyle\quad\theta_{-}^{+}\coloneqq-\frac{|a_{1}|}{2a_{2}\gamma}+\sqrt{\left(\frac{a_{1}}{2a_{2}\gamma}\right)^{2}+1-\frac{a_{1}\gamma}{a_{2}}}$ $\displaystyle\theta_{+}^{-}\coloneqq\frac{|a_{1}|}{2a_{2}\gamma}-\sqrt{\left(\frac{a_{1}}{2a_{2}\gamma}\right)^{2}+1-\frac{a_{1}\gamma}{a_{2}}},$ $\displaystyle\quad\theta_{-}^{-}\coloneqq-\frac{|a_{1}|}{2a_{2}\gamma}-\sqrt{\left(\frac{a_{1}}{2a_{2}\gamma}\right)^{2}+1-\frac{a_{1}\gamma}{a_{2}}}.$ $$

From Lemma [A.5](https://arxiv.org/html/2510.12026v2#A1.Thmtheorem5) and our choice of $\gamma$, $[\theta_{-}^{+},\theta_{+}^{+}]\subset[0,2]$. Hence, we have

$$ $\int_{\theta_{-}^{+}}^{\theta_{+}^{+}}\left|g_{*}(z)z\right|\mathrm{d}z\leq\left(\theta_{+}^{+}-\theta_{-}^{+}\right)\max_{z\in[0,2]}\left|g_{*}(z)z\right|=\frac{a_{1}}{a_{2}\gamma}\max_{z\in[0,2]}\left|g_{*}(z)z\right|=\frac{1}{\mathrm{poly}(d)}.$ $$

Applying a similar argument, we have the same bound for the second term, and we conclude $b_{1}=1/\mathrm{poly}(d)$.

###### Lemma B.4 .

###### Proof of Lemma B.4 .

#### Updated Parameter 𝜸 ∗ {\bm{\gamma}}^{*} .

With probability at least $1-{\tilde{\mathcal{O}}}\left(d^{2}T_{1}N_{\mathrm{pt}}^{-1/2}\right)$, the updated parameter ${\bm{\gamma}}^{*}$ is given by:

$$ $\displaystyle{\bm{\gamma}}^{*}$ $\displaystyle=2\eta\mathbb{E}_{{\bm{\beta}}\sim\mathrm{Unif}(S_{r})}\left[\psi({\bm{\beta}},a_{0},a_{1},a_{2})\odot\psi({\bm{\beta}},b_{0},b_{1},b_{2})\right]$ (4) $\displaystyle\quad+\eta{\tilde{\mathcal{O}}}\left(\max\left\{d^{-2C_{b}+4},d^{-C_{b}+2}N_{\mathrm{pt}}^{-1/2},d^{-C_{b}+1}T_{1}^{-1/2}\right\}\right),$ $$

with $a_{0},b_{0},b_{2}=\tilde{\Theta}(1)$ and $a_{\mathrm{ge}(g_{*})}=\tilde{\Theta}(1),a_{3-\mathrm{ge}(g_{*})}={\tilde{\mathcal{O}}}(1)$. Furthermore, $b_{1}=\tilde{\Theta}(1)$ if $\mathrm{ge}(g_{*})=1$, and $b_{1}\lesssim 1/\mathrm{poly}(d)$ otherwise.

### B.3 Output of Updated Mamba Layer

Lastly, we characterize the output of the Mamba layer with the updated parameter ${\bm{\gamma}}^{*}$, which serves as the input to the MLP layer. This characterization is given in the following proposition, which is a formal statement of Proposition [4.1](https://arxiv.org/html/2510.12026v2#S4.Thmtheorem1).

###### Proposition B.5 .

Let $({\bm{x}}_{1},y_{1},\dots,{\bm{x}}_{N},y_{N},{\bm{x}})$ be a prompt with context length $N\leq N^{*}$ and feature vector ${\bm{\beta}}\in\mathbb{R}^{d}$ and its embedding ${\bm{Z}}\in\mathbb{R}^{(\tilde{d}+1)\times(N+1)}$. If $N=\tilde{\Omega}\left(r^{3\mathrm{ge}(g_{*})}\right)$, ([4](https://arxiv.org/html/2510.12026v2#A2.E4)) holds, and $\eta=\Theta(d^{2C_{b}}(\log d)^{-C_{\eta}})$ with some large enough constant $C_{\eta}>0$, then the following holds with high probability:

$$ $N^{-1}{\mathsf{Mamba}}\left({\bm{Z}};{\bm{\gamma}}^{*}\right)[\tilde{d}+1,N+1]=P_{1}+P_{2}\left(\frac{\langle{\bm{\beta}},{\bm{x}}\rangle}{r}\right)^{\mathrm{ge}(g_{*})}\!\!\!\!+o\left(P_{2}r^{-3\mathrm{ge}(g_{*})/2}(\log d)^{-2\mathrm{deg}(g_{*})+2}\right),$ $$

where $P_{1}$ and $P_{2}$ are independent of data and satisfies $P_{1}=o(1)$ and $P_{2}=\Theta((\log d)^{-C_{P_{2}}})$ with some constant $C_{P_{2}}>0$.

###### Proof of Proposition B.5 .

Recall that ${\bm{c}}:=\mathbb{E}_{{\bm{\beta}}\sim\mathrm{Unif}(S_{r})}\left[\psi({\bm{\beta}},a_{0},a_{1},a_{2})\odot\psi({\bm{\beta}},b_{0},b_{1},b_{2})\right]$. From ([4](https://arxiv.org/html/2510.12026v2#A2.E4)), we have

$$ $\displaystyle\quad(2\eta)^{-1}N^{-1}{\mathsf{Mamba}}\left({\bm{Z}};{\bm{\gamma}}^{*}\right)[\tilde{d}+1,N+1]$ $\displaystyle=N^{-1}\sum_{j=1}^{N}G_{j,N+1}\left({\bm{Z}}\right)y_{j}\phi\left({\bm{x}}_{j}\right)^{\top}\big({\bm{c}}\odot\phi\left({\bm{x}}\right)\big)$ $\displaystyle\quad+{\tilde{\mathcal{O}}}\left(\max\left\{d^{-3C_{b}+4},d^{-2C_{b}+4}N_{\mathrm{pt}}^{-1/2},d^{-2C_{b}+3}T_{1}^{-1/2}\right\}\right)$ $\displaystyle=N^{-1}\sum_{j=1}^{N}y_{j}\sigma(y_{j}/\rho+b)\phi\left({\bm{x}}_{j}\right)^{\top}\big({\bm{c}}\odot\phi\left({\bm{x}}\right)\big)$ $\displaystyle\quad-N^{-1}\sum_{j=1}^{N}\left[y_{j}\sigma(y_{j}/\rho+b)\left(1-\big(1-\sigma(b)\big)\prod_{i=j+1}^{N}\big(1-\sigma(y_{j}^{t}/\rho+b)\big)\right)\phi\left({\bm{x}}_{j}^{t}\right)^{\top}\big({\bm{c}}\odot\phi({\bm{x}})\big)\right]$ $\displaystyle\quad+{\tilde{\mathcal{O}}}\left(\max\left\{d^{-3C_{b}+4},d^{-2C_{b}+4}N_{\mathrm{pt}}^{-1/2},d^{-2C_{b}+3}T_{1}^{-1/2}\right\}\right).$ $$

Note that for each $j\in[N]$, with high probability, $y_{j}=\rho\bar{g}_{*}({\bm{\beta}},{\bm{x}}_{j})+\zeta_{i}$ where $\zeta_{i}\sim\mathrm{Unif}(\{-\tau,\tau\})$. It implies that

$$ $\displaystyle\quad\left|y_{j}\sigma(y_{j}/\rho+b)\left(1-\big(1-\sigma(b)\big)\prod_{i=j+1}^{N}\big(1-\sigma(y_{j}^{t}/\rho+b)\big)\right)\phi\left({\bm{x}}_{j}^{t}\right)^{\top}\big({\bm{c}}\odot\phi({\bm{x}})\big)\right|$ $\displaystyle\leq N^{-1}\sum_{j=1}^{N}\left[\left|y_{j}\sigma(y_{j}/\rho+b)\right|\left(1-\big(1-\sigma(2b)\big)^{N^{*}}\right)\left\|\phi\left({\bm{x}}_{j}\right)\right\|\right]\left\|{\bm{c}}\right\|\left\|\phi({\bm{x}})\right\|$ $\displaystyle={\tilde{\mathcal{O}}}\left(d^{(-3C_{b}+C^{*}+2)}\right).$ $$

In addition, with high probability, we have

$$ $\displaystyle\quad\phi\left({\bm{x}}_{j}\right)^{\top}\big({\bm{c}}\odot\phi({\bm{x}})\big)$ $\displaystyle=\mathbb{E}_{{\bm{\beta}}\sim\mathrm{Unif}(S_{r})}\big[\left\langle\psi({\bm{\beta}},a_{0},a_{1},a_{2})\odot\phi({\bm{x}}_{j}),\psi({\bm{\beta}},b_{0},b_{1},b_{2})\odot\phi({\bm{x}})\right\rangle\big]$ $\displaystyle=a_{0}b_{0}+a_{1}b_{1}\mathbb{E}_{{\bm{\beta}}\sim\mathrm{Unif}(S_{r})}[\langle{\bm{\beta}},{\bm{x}}_{i}\rangle\langle{\bm{\beta}},{\bm{x}}\rangle]$ $\displaystyle\quad+\frac{a_{2}b_{2}}{2}\mathbb{E}_{{\bm{\beta}}\sim\mathrm{Unif}(S_{r})}\left[(\mathrm{He}_{2}(\langle{\bm{\beta}},{\bm{x}}\rangle)-1)(\mathrm{He}_{2}(\langle{\bm{\beta}},{\bm{x}}_{j}\rangle)-1)\right].$ $$

In addition, combining with Lemma [A.3](https://arxiv.org/html/2510.12026v2#A1.Thmtheorem3), we have

$$ $\phi\left({\bm{x}}_{j}\right)^{\top}\big({\bm{c}}\odot\phi\left({\bm{x}}\right)\big)={\tilde{\mathcal{O}}}\left(d^{-C_{b}}\right),$ $$

with high probability. Therefore, from our choice of $\eta=\Theta\left(d^{2C_{b}}(\log d)^{-C_{\eta}}\right)$, with high probability, we have

$$ $\left|\eta y_{j}\sigma(y_{j}/\rho+b)\phi({\bm{x}}_{j})^{\top}\big({\bm{c}}\odot\phi({\bm{x}})\big)\right|\leq 1.$ $$

Therefore, with high probability, we have

$$ $N^{-1}\sum_{j=1}^{N}\eta y_{j}\sigma(y_{j}/\rho+b)\phi({\bm{x}}_{j})^{\top}\big({\bm{c}}\odot\phi({\bm{x}})\big)=N^{-1}\sum_{j=1}^{N}\bar{\mathbf{z}}_{j},$ $$

where

$$ ${\mathbf{z}}_{j}:=\eta y_{j}\sigma(y_{j}/\rho+b)\phi({\bm{x}}_{j})^{\top}\big({\bm{c}}\odot\phi({\bm{x}})\big),\quad\bar{\mathbf{z}}_{j}:={\mathbf{z}}_{j}\mathbbm{1}[\left|{\mathbf{z}}_{j}\right|\leq 1].$ $$

By Höeffding’s inequality, with high probability, we have

$$ $\displaystyle N^{-1}\sum_{j=1}^{N}\bar{\mathbf{z}}_{j}$ $\displaystyle=\mathbb{E}_{{\bm{x}}_{1},y_{1}}[\bar{\mathbf{z}}_{1}]+{\tilde{\mathcal{O}}}\left(N^{-1/2}\right)$ $\displaystyle=\mathbb{E}_{{\mathbf{x}}_{1},y_{1}}[{\mathbf{z}}_{1}]+\mathbb{E}_{{\mathbf{x}}_{1},y_{1}}\left[{\mathbf{z}}_{1}\mathbbm{1}\left[\left|{\mathbf{z}}_{1}\right|>r^{2}\right]\right]+{\tilde{\mathcal{O}}}\left(N^{-1/2}\right)$ $\displaystyle=\mathbb{E}_{{\mathbf{x}}_{1},y_{1}}[{\mathbf{z}}_{1}]+{\tilde{\mathcal{O}}}\left(N^{-1/2}\right),$ $$

where the last inequality holds since

$$ $\left|\mathbb{E}_{{\mathbf{x}}_{1},y_{1}}\left[{\mathbf{z}}_{1}\mathbbm{1}\left[\left|{\mathbf{z}}_{1}\right|>r^{2}\right]\right]\right|\leq\mathbb{E}_{{\mathbf{x}}_{1},y_{1}}\left[{\mathbf{z}}_{1}^{2}\right]^{\frac{1}{2}}\mathbb{P}\left[\left|{\mathbf{z}}_{1}\right|>r^{2}\right]^{\frac{1}{2}}=\frac{1}{\mathrm{poly}(d)}.$ $$

Therefore, with high probability, we have

$$ $\displaystyle\quad N^{-1}{\mathsf{Mamba}}\left({\bm{Z}};{\bm{\gamma}}^{*}\right)[\tilde{d}+1,N+1]$ $\displaystyle=2\eta\mathbb{E}\left[y_{1}\sigma(y_{1}/\rho+b)\phi({\bm{x}}_{1})^{\top}\big({\bm{c}}\odot\phi({\bm{x}})\big)\right]$ $\displaystyle\quad+{\tilde{\mathcal{O}}}\left(N^{-1/2}\right)+{\tilde{\mathcal{O}}}\left(\max\left\{d^{-C_{b}+6},d^{4}N_{\mathrm{pt}}^{-1/2},d^{3}T_{1}^{-1/2}\right\}\right).$ $$

Lastly, the expectation can be calculated as

$$ $\displaystyle\quad\psi\left({\bm{\beta}},a_{0},a_{1},a_{2}\right)^{\top}\left({\bm{c}}\odot\phi\left({\bm{x}}\right)\right)$ $\displaystyle=\mathbb{E}_{{\bm{\beta}}^{\prime}\sim\mathrm{Unif}(S_{r})}\Big[\big\langle\psi({\bm{\beta}},a_{0},a_{1},a_{2})\odot\psi({\bm{\beta}}^{\prime},a_{0},a_{1},a_{2}),\psi({\bm{\beta}}^{\prime},b_{0},b_{1},b_{2})\odot\phi({\bm{x}})\big\rangle\Big]$ $\displaystyle=a_{0}^{2}b_{0}+a_{1}^{2}b_{1}\mathbb{E}_{{\bm{\beta}}^{\prime}\sim\mathrm{Unif}(S_{r})}\left[\sum_{i=1}^{d}{\bm{\beta}}[i]{\bm{x}}[i]{\bm{\beta}}^{\prime}[i]^{2}\right]$ $\displaystyle\quad+\frac{a_{2}^{2}b_{2}}{4}\left(\left(\sum_{i=1}^{d}{\bm{\beta}}[i]{\bm{x}}[i]{\bm{\beta}}^{\prime}[i]^{2}\right)^{2}-\sum_{i=1}^{d}{\bm{\beta}}[i]^{2}{\bm{\beta}}^{\prime}[i]^{2}\right)$ $\displaystyle=\left(a_{0}^{2}b_{0}-\frac{a_{2}^{2}b_{2}}{4}\right)+a_{1}^{2}b_{1}\left(\frac{\left\langle{\bm{\beta}},{\bm{x}}\right\rangle}{r}\right)+\frac{a_{2}^{2}b_{2}}{4}\left(\frac{\left\langle{\bm{\beta}},{\bm{x}}\right\rangle}{r}\right)^{2}.$ $$

Hence, we have

$$ $\displaystyle\quad N^{-1}{\mathsf{Mamba}}\left({\bm{Z}};{\bm{\gamma}}^{*}\right)[\tilde{d}+1,N+1]$ $\displaystyle=2\eta\left(\left(a_{0}^{2}b_{0}-\frac{a_{2}^{2}b_{2}}{4}\right)+a_{1}^{2}b_{1}\left(\frac{\left\langle{\bm{\beta}},{\bm{x}}\right\rangle}{r}\right)+\frac{a_{2}^{2}b_{2}}{4}\left(\frac{\left\langle{\bm{\beta}},{\bm{x}}\right\rangle}{r}\right)^{2}\right)$ $\displaystyle\quad+{\tilde{\mathcal{O}}}\left(N^{-\frac{1}{2}}\right)+{\tilde{\mathcal{O}}}\left(\max\left\{d^{-C_{b}+6},d^{4}N_{\mathrm{pt}}^{-1/2},d^{3}T_{1}^{-1/2}\right\}\right).$ $$

Our conclusion is reached by defining $P_{1}=2\eta(a_{0}^{2}b_{0}-a_{2}^{2}b_{2}/4)$ and

$$ $\displaystyle P_{2}=\begin{cases}2\eta a_{1}^{2}b_{1}&\text{if $\mathrm{ge}(g_{*})=1$}\\ \eta a_{2}^{2}b_{2}/2&\text{if $\mathrm{ge}(g_{*})=2$}\end{cases}.$ $$

∎

###### Proposition B.5 .

###### Proof of Proposition B.5 .

## Appendix C Optimizing MLP Layer

In this section, we analyze the second stage of pretraining, which focuses on the MLP layer.

### C.1 Construction of Approximating MLP Layer

First, we construct the infinite-width MLP layer approximating the link function $g_{*}$.

###### Lemma C.1 .

For given ${\bm{\beta}}\in\mathbb{R}^{d}$ with $\left\|{\bm{\beta}}\right\|=1$, suppose there exists a function $h:\mathbb{R}\rightarrow\mathbb{R}$ such that

$$ $h({\bm{x}})=P_{1}+P_{2}\left(\frac{\langle{\bm{\beta}},{\bm{x}}\rangle}{r}\right)^{\mathrm{ge}(g_{*})}+n({\bm{x}}),$ $$

where $P_{1}=o(1),P_{2}=\Theta\left((\log d)^{-C_{P_{2}}}\right)$, and $\left|n({\bm{x}})\right|=o\left(P_{2}r^{-3\mathrm{ge}(g_{*})/2}(\log d)^{-2\mathrm{deg}(g_{*})+2}\right)$ with high probability over ${\bm{x}}\sim{\mathcal{N}}({\bm{0}},{\bm{I}}_{d})$. Then, there exists a function $\pi(\cdot,\cdot):\mathbb{R}^{2}\rightarrow\mathbb{R}$ such that

$$ $\left|\mathbb{E}_{v\sim\mathrm{Unif}(\{\pm 1\}),a\sim\mathrm{Unif}([-1,1])}[\phi(v,a){\mathrm{ReLU}}(vh({\bm{x}})+a]-g_{*}(\langle{\bm{\beta}},{\bm{x}}\rangle)\right|=o(1),$ $$

with high probability over ${\bm{x}}\sim{\mathcal{N}}({\bm{0}},{\bm{I}}_{d})$. In addition, $\sup_{v,a}\left|\pi(v,a)\right|={\tilde{\mathcal{O}}}(r^{2\mathrm{ge}(g_{*})})$.

###### Proof of Lemma C.1 .

Since $\mathrm{ge}(g_{*})=2$ implies $g_{*}$ is even function, there exists a polynomial $\tilde{g}_{*}$ such that $g_{*}(z)=\tilde{g}_{*}\left(z^{\mathrm{ge}(g_{*}))}\right)$. Let $\tilde{g}_{*}(z)=\sum_{k=0}^{\mathrm{deg}(\tilde{g}_{*})}s_{k}z^{k}$. For any $k\in\mathbb{N}_{0}$, from Lemma 17 in Damian et al. (2022), there exists $\pi_{k}(\cdot,\cdot):\mathbb{R}^{2}\rightarrow\mathbb{R}$ such that for any $|z|\leq 1$

$$ $\mathbb{E}_{v\sim\mathrm{Unif}(\{\pm 1\}),a\sim\mathrm{Unif}([-1,1])}\left[\pi_{k}^{\prime}(v,a){\mathrm{ReLU}}(vz+a)\right]=z^{k}\text{ and }\sup_{v,a}\left|\pi_{k}^{\prime}(v,a)\right|={\mathcal{O}}(1).$ $$

Let us define $\pi^{\prime}(\cdot,\cdot):\mathbb{R}^{2}\rightarrow\mathbb{R}$ as

$$ $\pi^{\prime}(v,a)=\sum_{k=0}^{\mathrm{deg}(\tilde{g}_{*})}s_{k}\frac{\pi_{k}^{\prime}\big(v,ap^{-1}(\log d)^{-2}\big)}{p(\log d)^{2}}(\log d)^{2k},$ $$

where $p:=P_{2}r^{-\mathrm{ge}(g_{*})}$. Note that $\sup_{v,a}\left|\pi^{\prime}(v,a)\right|={\mathcal{O}}\left(p^{-1}(\log d)^{2\mathrm{deg}(g_{*})-2}\right)$ and if $\left|z\right|\leq(\log d)^{2}$, then we have

$$ $\displaystyle\quad\mathbb{E}_{\begin{subarray}{c}v\sim\mathrm{Unif}(\{\pm 1\})\\ a\sim\mathrm{Unif}([-p(\log d)^{2},p(\log d)^{2}])\end{subarray}}\left[\pi^{\prime}(v,a){\mathrm{ReLU}}\left(v(pz)+a\right)\right]$ $\displaystyle=\sum_{k=0}^{\mathrm{deg}(\tilde{g}_{*})}s_{k}\mathbb{E}_{\begin{subarray}{c}v\sim\mathrm{Unif}(\{\pm 1\})\\ a\sim\mathrm{Unif}([-p(\log d)^{2},p(\log d)^{2}])\end{subarray}}\left[\frac{\pi_{k}^{\prime}(v,ap^{-1}(\log d)^{-2})}{p(\log d)^{2}}(\log d)^{2k}{\mathrm{ReLU}}\left(v(pz)+a\right)\right]$ $\displaystyle=\sum_{k=0}^{\mathrm{deg}(\tilde{g}_{*})}s_{k}(\log d)^{2k}\mathbb{E}_{v\sim\mathrm{Unif}(\{\pm 1\}),a\sim\mathrm{Unif}([-1,1])}[\pi_{k}^{\prime}(v,a){\mathrm{ReLU}}(vz(\log d)^{-2}+a)]$ $\displaystyle=\sum_{k=0}^{\mathrm{deg}(\tilde{g}_{*})}s_{k}z^{k}=\tilde{g}_{*}(z).$ $$

Lastly, we define $\pi(\cdot,\cdot):\mathbb{R}^{2}\rightarrow\mathbb{R}$ as

$$ $\displaystyle\pi(v,a)$ $\displaystyle\coloneqq\frac{\mathbbm{1}[v=-1\wedge a\in[P_{1}-p(\log d)^{2},P_{1}+p(\log d)^{2}]]\pi^{\prime}(-1,b-P_{1})}{2p(\log d)^{2}}$ (5) $\displaystyle\quad+\frac{\mathbbm{1}[v=1\wedge a\in[-P_{1}-p(\log d)^{2},-P_{1}+p(\log d)^{2}]]\pi^{\prime}(1,b+P_{1})}{2p(\log d)^{2}},$ $$

then we have $\sup_{v,a}={\tilde{\mathcal{O}}}(r^{2\mathrm{ge}(g_{*})})$
With high probability, $\left|\langle{\bm{\beta}},{\bm{x}}\rangle\right|\leq(\log d)^{2}$ and thus we have

$$ $\displaystyle\quad 2\mathbb{E}_{v\sim\mathrm{Unif}(\{\pm 1\}),a\sim\mathrm{Unif}([-1,1])}[\pi(v,a){\mathrm{ReLU}}(vh({\bm{x}})+b)]$ $\displaystyle=\mathbb{E}_{a\sim\mathrm{Unif}([P_{1}-p(\log d)^{2},P_{1}+p(\log d)^{2}])}\left[\pi^{\prime}(-1,b-P_{1}){\mathrm{ReLU}}(-P_{1}-p(\langle{\bm{\beta}},{\bm{x}}\rangle)^{\mathrm{ge}(g_{*})})-n({\bm{x}})+a\right]$ $\displaystyle\quad+\mathbb{E}_{a\sim\mathrm{Unif}([P_{1}-p(\log d)^{2},P_{1}+p(\log d)^{2}])}\left[\pi^{\prime}(1,b-P_{1}){\mathrm{ReLU}}(P_{1}+p(\langle{\bm{\beta}},{\bm{x}}\rangle)^{\mathrm{ge}(g_{*})}+n({\bm{x}})+a)\right]$ $\displaystyle=2\mathbb{E}_{v\sim\mathrm{Unif}(\{\pm 1\}),a\sim\mathrm{Unif}([-p(\log d)^{2},p(\log d)^{2}])}\left[\pi^{\prime}(v,a){\mathrm{ReLU}}\left(vp\langle{\bm{\beta}},{\bm{x}}\rangle^{\mathrm{ge}(g_{*})}+a\right)\right]+o(1)$ $\displaystyle=2g_{*}(\langle{\bm{\beta}},{\bm{x}}\rangle)+o(1).$ $$

Here, the second equality holds from the fact that $\sup_{v,a}\left|\pi^{\prime}(v,a)\right|={\mathcal{O}}\left(p^{-1}(\log d)^{2\mathrm{deg}(g_{*})-2}\right)$ and $\left|n({\bm{x}})\right|=o\left(p(\log d)^{-2\mathrm{deg}(g_{*})+2}\right)$.

Therefore, we have the desired conclusion.
∎

Next, we prove that we can approximate the link function with a finite-width MLP.

###### Lemma C.2 .

Let ${\bm{v}}\sim\mathrm{Unif}(\{\pm 1\}^{m})$ and ${\bm{a}}\sim\mathrm{Unif}([-1,1]^{m})$. Under the same condition of Lemma [C.1](https://arxiv.org/html/2510.12026v2#A3.Thmtheorem1), there exists ${\bm{u}}^{\prime}\in\mathbb{R}^{m}$ such that

$$ $\left|\sum_{j=1}^{m}{\bm{u}}^{\prime}[j]{\mathrm{ReLU}}({\bm{v}}[j]h({\bm{x}})+{\bm{a}}[j])-g_{*}(\langle{\bm{\beta}},{\bm{x}}\rangle)\right|=o(1)$ $$

with high probability over ${\bm{x}}\sim{\mathcal{N}}({\bm{0}},{\bm{I}}_{d})$. Furthermore, $\left\|{\bm{u}}^{\prime}\right\|^{2}={\tilde{\mathcal{O}}}\left(r^{3\mathrm{ge}(g_{*})}m^{-1}\right)$ holds with high probability.

###### Proof of Lemma C.2 .

We choose ${\bm{u}}^{\prime}$ as ${\bm{u}}^{\prime}[j]=\pi({\bm{v}}[j],{\bm{a}}[j])/m$ where $\pi(\cdot,\cdot):\mathbb{R}^{2}\rightarrow\mathbb{R}$ is obtained from Lemma [C.1](https://arxiv.org/html/2510.12026v2#A3.Thmtheorem1). We will show that this choice satisfies the desired conclusions. Since $\left|h({\bm{x}})\right|\leq 1$ with high probability and $\sup_{v,a}\left|\pi(v,a)\right|={\tilde{\mathcal{O}}}(r^{2\mathrm{ge}(g_{*})})$, we can apply Höeffding’s inequality:

$$ $\displaystyle\quad\sum_{j=1}^{m}{\bm{u}}^{\prime}[j]{\mathrm{ReLU}}({\bm{v}}[j]h({\bm{x}})+{\bm{a}}[j])$ $\displaystyle=\frac{1}{m}\sum_{j=1}^{m}\pi({\bm{v}}[j],{\bm{a}}[j]){\mathrm{ReLU}}({\bm{v}}[j]h({\bm{x}})+{\bm{a}}[j])$ $\displaystyle=\mathbb{E}_{v\sim\mathrm{Unif}(\{\pm 1\}),a\sim\mathrm{Unif}([-1,1])}[\pi(v,a){\mathrm{ReLU}}(vh({\bm{x}})+a)]+{\tilde{\mathcal{O}}}(r^{2\mathrm{ge}(g_{*})}m^{-1/2})$ $\displaystyle=g_{*}(\langle{\bm{\beta}},{\bm{x}}\rangle)+{\tilde{\mathcal{O}}}(r^{2\mathrm{ge}(g_{*})}m^{-1/2})+o(1).$ $$

In addition, by applying Höeffding’s inequality, the following holds with high probability:

$$ $\displaystyle\left\|{\bm{u}}^{\prime}\right\|^{2}$ $\displaystyle=m^{-2}\sum_{j=1}^{m}\pi({\bm{v}}[j],{\bm{b}}[i])^{2}$ $\displaystyle=m^{-1}\mathbb{E}_{v\sim\mathrm{Unif}(\{\pm 1\}),a\sim\mathrm{Unif}([-1,1])}[\pi(v,a)^{2}]+{\tilde{\mathcal{O}}}(r^{4\mathrm{ge}(g_{*})}m^{-3/2}).$ $$

From ([5](https://arxiv.org/html/2510.12026v2#A3.E5)), $\pi(v,a)$ is nonzero with probability ${\tilde{\mathcal{O}}}(r^{-\mathrm{ge}(g_{*})})$. Combining with $\sup_{v,a}\left|\pi(v,a)\right|={\tilde{\mathcal{O}}}(r^{2\mathrm{ge}(g_{*})})$, we have desired conclusion.
∎

###### Lemma C.1 .

###### Proof of Lemma C.1 .

###### Lemma C.2 .

###### Proof of Lemma C.2 .

### C.2 Characterization of Estimation Error on the Training Set

The following lemma characterizes estimation on the training set after pretraining.

###### Lemma C.3 .

There exists $\lambda_{2}>0$ such that the following holds with probability at least $0.999$:

$$ $\frac{1}{T_{2}}\sum_{t=T_{1}+1}^{T_{1}+T_{2}}\left|y^{t}-f({\bm{Z}}^{t},{\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})\right|=\tau+o(1)\text{ and }\left\|{\bm{u}}^{*}\right\|={\tilde{\mathcal{O}}}\left(r^{3\mathrm{ge}(g^{*})/2}m^{-\frac{1}{2}}\right).$ $$

###### Proof of Lemma C.3 .

From Proposition [B.5](https://arxiv.org/html/2510.12026v2#A2.Thmtheorem5), the condition in Lemma [C.1](https://arxiv.org/html/2510.12026v2#A3.Thmtheorem1) is satisfied with probability at least $0.999$. Under this, let ${\bm{u}}^{\prime}$ be the output layer parameter obtained from Lemma [C.2](https://arxiv.org/html/2510.12026v2#A3.Thmtheorem2). From the equivalence between $\ell_{2}$-regularization and norm-constrained optimization, there exists $\lambda_{2}>0$ such that optimized parameter ${\bm{u}}^{*}$ satisfies $\left\|{\bm{u}}^{*}\right\|\leq\left\|{\bm{u}}^{\prime}\right\|={\tilde{\mathcal{O}}}(r^{3\mathrm{ge}(g_{*})/2}m^{-1/2})$ and

$$ $\displaystyle\left(\frac{1}{T_{2}}\sum_{t=T_{1}+1}^{T_{1}+T_{2}}\left|y^{t}-f({\bm{Z}}^{t},{\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})\right|\right)^{2}$ $\displaystyle\leq\frac{1}{T_{2}}\sum_{t=T_{1}+1}^{T_{1}+T_{2}}\left(y^{t}-f({\bm{Z}}^{t},{\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})\right)^{2}$ $\displaystyle\leq\frac{1}{T_{2}}\sum_{t=T_{1}+1}^{T_{1}+T_{2}}\left(y^{t}-f({\bm{Z}}^{t},{\bm{\gamma}}^{*},{\bm{u}}^{\prime},{\bm{v}}^{*},{\bm{a}}^{*})\right)^{2}$ $\displaystyle\leq(\tau+o(1))^{2}.$ $$

∎

###### Lemma C.3 .

###### Proof of Lemma C.3 .

## Appendix D Test Error Analysis

In this section, we analyze the test-time estimation error:

$$ ${\mathcal{R}}_{N_{\mathrm{test}}}({\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})=\mathbb{E}_{({\bm{Z}},y)\sim{\mathcal{D}}(N_{\mathrm{test}})}[\left|f({\bm{Z}},{\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})-y\right|].$ $$

### D.1 Test Error for Prompts with Pretraining Context Length

We first prove our conclusion for the case $N_{\mathrm{test}}=N_{\mathrm{pt}}$ by establishing a generalization bound using Rademacher complexity.

We define a family of functions ${\mathcal{F}}_{U}$ on inputs with context length $N_{\mathrm{test}}=N_{\mathrm{pt}}$ as follows:

$$ ${\mathcal{F}}_{U}\coloneqq\left\{({\bm{Z}},y)\mapsto\sum_{j=1}^{m}{\bm{u}}[j]{\mathrm{ReLU}}\left({\bm{v}}^{*}[j]N_{\mathrm{pt}}^{-1}{\mathsf{Mamba}}({\bm{Z}};{\bm{\gamma}}^{*})+{\bm{a}}^{*}[j]\right)\middle|\left\|{\bm{u}}\right\|\leq U\right\}.$ $$

In addition, the Rademacher complexity of ${\mathcal{F}}_{U}$ for sample size $T_{2}$ is defined as

$$ $\mathrm{Rad}_{T_{2}}({\mathcal{F}}_{U})=\mathbb{E}_{\begin{subarray}{c}({\bm{Z}}^{t},y^{t})\sim{\mathcal{D}}(N_{\mathrm{pt}})\\ \bm{\epsilon}\sim\mathrm{Unif}\left(\{\pm 1\}^{T_{2}}\right)\end{subarray}}\left[\sup_{\tilde{f}\in{\mathcal{F}}_{U}}\frac{1}{T_{2}}\sum_{t=1}^{T_{2}}\bm{\epsilon}[t]\tilde{f}({\bm{Z}}^{t},y^{t})\right].$ $$

In the following lemma, we characterize the Rademacher complexity of ${\mathcal{F}}_{U}$.

###### Lemma D.1 .

It holds that

$$ $\mathrm{Rad}_{T_{2}}({\mathcal{F}}_{U})={\tilde{\mathcal{O}}}\left(Um^{1/2}T_{2}^{-1/2}\right).$ $$

###### Proof of Lemma D.1 .

By sequentially applying Cauchy-Schwarz inequality and Jensen’s inequality, we have

$$ $\displaystyle\quad\mathrm{Rad}_{T_{2}}({\mathcal{F}}_{U})$ $\displaystyle=\mathbb{E}_{\begin{subarray}{c}({\bm{Z}}^{t},y^{t})\sim{\mathcal{D}}(N_{\mathrm{pt}})\\ \bm{\epsilon}\sim\mathrm{Unif}\left(\{\pm 1\}^{T_{2}}\right)\end{subarray}}\left[\sup_{\left\|{\bm{u}}\right\|\leq U}\sum_{j=1}^{m}{\bm{u}}[j]\left(\frac{1}{T_{2}}\sum_{t=1}^{T_{2}}\bm{\epsilon}[t]{\mathrm{ReLU}}\Big({\bm{v}}^{*}[j]N_{{\mathrm{pt}}}^{-1}{\mathsf{Mamba}}({\bm{Z}}^{t},{\bm{\gamma}}^{*})+{\bm{a}}^{*}[j]\Big)\right)\right]$ $\displaystyle\leq A\mathbb{E}_{\begin{subarray}{c}({\bm{Z}}^{t},y^{t})\sim{\mathcal{D}}(N_{\mathrm{pt}})\\ \bm{\epsilon}\sim\mathrm{Unif}\left(\{\pm 1\}^{T_{2}}\right)\end{subarray}}\left[\left(\sum_{j=1}^{m}\left(\frac{1}{T_{2}}\sum_{t=1}^{T_{2}}\bm{\epsilon}[t]{\mathrm{ReLU}}\Big({\bm{v}}^{*}[j]N_{{\mathrm{pt}}}^{-1}{\mathsf{Mamba}}({\bm{Z}}^{t},{\bm{\gamma}}^{*})+{\bm{a}}^{*}[j]\Big)\right)^{2}\right)^{\frac{1}{2}}\right]$ $\displaystyle\leq A\left(\mathbb{E}_{\begin{subarray}{c}({\bm{Z}}^{t},y)\sim{\mathcal{D}}(N_{\mathrm{pt}})\\ \bm{\epsilon}\sim\mathrm{Unif}\left(\{\pm 1\}^{T_{2}}\right)\end{subarray}}\left[\sum_{j=1}^{m}\left(\frac{1}{T_{2}}\sum_{t=1}^{T_{2}}\bm{\epsilon}[t]{\mathrm{ReLU}}\Big({\bm{v}}^{*}[j]N_{{\mathrm{pt}}}^{-1}{\mathsf{Mamba}}({\bm{Z}}^{t},{\bm{\gamma}}^{*})+{\bm{a}}^{*}[j]\Big)\right)^{2}\right]\right)^{\frac{1}{2}}$ $\displaystyle=A\left(\mathbb{E}_{({\bm{Z}}^{t},y^{t})\sim{\mathcal{D}}(N_{\mathrm{pt}})}\left[\frac{1}{T^{2}}\sum_{j=1}^{m}\sum_{t=1}^{T_{2}}\left({\mathrm{ReLU}}\Big({\bm{v}}^{*}[j]N_{{\mathrm{pt}}}^{-1}{\mathsf{Mamba}}({\bm{Z}}^{t},{\bm{\gamma}}^{*})+{\bm{a}}^{*}[j]\Big)\right)^{2}\right]\right)^{\frac{1}{2}}.$ $$

In addition, we have

$$ $\displaystyle\quad\mathbb{E}_{({\bm{Z}}^{t},y^{t})\sim{\mathcal{D}}(N_{\mathrm{pt}})}\left[\sum_{j=1}^{m}\sum_{t=1}^{T_{2}}\left({\mathrm{ReLU}}\Big({\bm{v}}^{*}[j]N_{{\mathrm{pt}}}^{-1}{\mathsf{Mamba}}({\bm{Z}}^{t},{\bm{\gamma}}^{*})+{\bm{a}}^{*}[j]\Big)\right)^{2}\right]$ $\displaystyle\leq\mathbb{E}_{({\bm{Z}}^{t},y^{t})\sim{\mathcal{D}}(N_{\mathrm{pt}})}\left[\sum_{j=1}^{m}\sum_{t=1}^{T_{2}}\left({\bm{v}}^{*}[j]N_{{\mathrm{pt}}}^{-1}{\mathsf{Mamba}}({\bm{Z}}^{t},{\bm{\gamma}}^{*})+{\bm{a}}^{*}[j]\right)^{2}\right]$ $\displaystyle\leq 2\mathbb{E}_{({\bm{Z}}^{t},y^{t})\sim{\mathcal{D}}(N_{\mathrm{pt}})}\left[\sum_{j=1}^{m}\sum_{t=1}^{T_{2}}\left({\bm{v}}^{*}[j]^{2}N_{{\mathrm{pt}}}^{-2}{\mathsf{Mamba}}({\bm{Z}}^{t},{\bm{\gamma}}^{*})^{2}+{\bm{a}}^{*}[j]^{2}\right)\right]$ $\displaystyle\leq 2\left(mT_{2}+mT_{2}\mathbb{E}_{({\bm{Z}},y)\sim{\mathcal{D}}(N_{\mathrm{pt}})}\left[N_{\mathrm{pt}}^{-2}{\mathsf{Mamba}}({\bm{Z}},{\bm{\gamma}}^{*})^{2}\right]\right).$ $$

Let $({\bm{Z}},y)\sim{\mathcal{D}}(N_{\mathrm{pt}})$ and ${\bm{\beta}}$, ${\bm{x}}$ be their feature vector and query data, respectively. From Lemma [A.1](https://arxiv.org/html/2510.12026v2#A1.Thmtheorem1), with high probability over $({\bm{Z}},y)\sim{\mathcal{D}}(N_{\mathrm{pt}})$, we have

$$ $N_{\mathrm{pt}}^{-1}{\mathsf{Mamba}}({\bm{Z}},{\bm{\gamma}}^{*})=P_{1}+P_{2}\left(\frac{\langle{\bm{\beta}},{\bm{x}}\rangle}{r}\right)^{\mathrm{ge}(g_{*})}\!\!\!\!+o\left(P_{2}r^{-\mathrm{ge}(g_{*})}(\log d)^{-2\mathrm{deg}(g_{*})}\right)={\tilde{\mathcal{O}}}(1).$ $$

It implies $\mathbb{E}_{({\bm{Z}},y)\sim{\mathcal{D}}(N_{\mathrm{pt}})}\left[N_{\mathrm{pt}}^{-2}{\mathsf{Mamba}}({\bm{Z}},{\bm{\gamma}}^{*})^{2}\right]={\tilde{\mathcal{O}}}(1)$ and it leads to our desired conclusion.
∎

Next, we obtain the following result on test error.

###### Lemma D.2 .

With probability at least $0.995$, it holds that ${\mathcal{R}}_{N_{\mathrm{pt}}}({\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})-\tau=o(1)$.

###### Proof of Lemma D.2 .

From Lemma [C.3](https://arxiv.org/html/2510.12026v2#A3.Thmtheorem3), with probability at least 0.999, we can choose $U={\tilde{\mathcal{O}}}(r^{3\mathrm{ge}(g_{*})/2}m^{-1/2})$ such that ${\bm{u}}^{*}\leq U$ and we have

$$ $\displaystyle\quad{\mathcal{R}}_{N_{\mathrm{pt}}}({\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})-\tau$ $\displaystyle=\frac{1}{T_{2}}\sum_{t=T_{1}+1}^{T_{1}+T_{2}}\left|y^{t}-f\left({\bm{Z}}^{t},{\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*}\right)\right|$ $\displaystyle\quad+\left({\mathcal{R}}_{N_{\mathrm{pt}}}({\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})-\frac{1}{T_{2}}\sum_{t=T_{1}+1}^{T_{1}+T_{2}}\left|y^{t}-f\left({\bm{Z}}^{t},{\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*}\right)\right|\right)-\tau$ $\displaystyle\leq\sup_{\tilde{f}\in\tilde{\mathcal{F}}_{U}}\left({\mathcal{R}}_{N_{\mathrm{pt}}}({\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})-\frac{1}{T_{2}}\sum_{t=T_{1}+1}^{T_{1}+T_{2}}\left|y^{t}-f\left({\bm{Z}}^{t},{\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*}\right)\right|\right)+o(1),$ $$

where $\tilde{\mathcal{F}}_{U}:={\mathcal{F}}_{U}\cup\{({\bm{Z}},y)\mapsto y\}$.
Using the standard symmetrization argument (Proposition 4.2 in Bach (2024)), we have

$$ $\displaystyle\quad\mathbb{E}\left[\sup_{\tilde{f}\in{\mathcal{F}}_{U}}\left({\mathcal{R}}_{N_{\mathrm{pt}}}({\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})-\frac{1}{T_{2}}\sum_{t=T_{1}+1}^{T_{1}+T_{2}}\left|y^{t}-f\left({\bm{Z}}^{t},{\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*}\right)\right|\right)\right]$ $\displaystyle\leq 2\mathrm{Rad}_{T_{2}}(\tilde{\mathcal{F}}_{U})$ $\displaystyle\leq 2\mathrm{Rad}_{T_{w}}({\mathcal{F}}_{U})+\frac{2}{T_{2}}\mathbb{E}_{\begin{subarray}{c}({\bm{Z}}^{t},y^{t})\sim{\mathcal{D}}(N_{\mathrm{pt}})\\ \bm{\epsilon}\sim\mathrm{Unif}\left(\{\pm 1\}^{T_{2}}\right)\end{subarray}}\left[\sum_{t=1}^{T_{2}}\left|\bm{\epsilon}[t]y^{t}\right|\right],$ $$

where the second inequality holds since ${\mathcal{F}}_{U}$ contains zero function. By the Cauchy-Schwarz inequality, we can also bound the second term as

$$ $\displaystyle\mathbb{E}_{\begin{subarray}{c}({\bm{Z}}^{t},y^{t})\sim{\mathcal{D}}(N_{\mathrm{pt}})\\ \bm{\epsilon}\sim\mathrm{Unif}\left(\{\pm 1\}^{T_{2}}\right)\end{subarray}}\left[\sum_{t=1}^{T_{2}}\left|\bm{\epsilon}[t]y^{t}\right|\right]$ $\displaystyle\leq\left(\mathbb{E}_{\begin{subarray}{c}({\bm{Z}}^{t},y^{t})\sim{\mathcal{D}}(N_{\mathrm{pt}})\\ \bm{\epsilon}\sim\mathrm{Unif}\left(\{\pm 1\}^{T_{2}}\right)\end{subarray}}\left[\left(\sum_{t=1}^{T_{2}}\bm{\epsilon}[t]y^{t}\right)^{2}\right]\right)^{\frac{1}{2}}$ $\displaystyle=\sqrt{T_{2}}\left(\mathbb{E}_{({\bm{Z}},y)\sim{\mathcal{D}}(N_{\mathrm{pt}})}\left[\left(y^{t}\right)^{2}\right]\right)^{\frac{1}{2}}.$ $$

Combining with Lemma [D.1](https://arxiv.org/html/2510.12026v2#A4.Thmtheorem1), we have

$$ $\displaystyle\quad\mathbb{E}\left[\sup_{\tilde{f}\in{\mathcal{F}}_{U}}\left({\mathcal{R}}_{N_{\mathrm{pt}}}({\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})-\frac{1}{T_{2}}\sum_{t=T_{1}+1}^{T_{1}+T_{2}}\left|y^{t}-f\left({\bm{Z}}^{t},{\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*}\right)\right|\right)\right]$ $\displaystyle={\tilde{\mathcal{O}}}\left(r^{3\mathrm{ge}(g_{*})/2}T_{2}^{-1/2}\right)=o(1).$ $$

Note that $\sup_{\tilde{f}\in\tilde{\mathcal{F}}_{U}}\left({\mathcal{R}}_{N_{\mathrm{pt}}}({\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})-\frac{1}{T_{2}}\sum_{t=T_{1}+1}^{T_{1}+T_{2}}\left|y^{t}-f\left({\bm{Z}}^{t},{\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*}\right)\right|\right)$ is always non-negative due to $({\bm{Z}},y)\mapsto y\in\tilde{\mathcal{F}}_{U}$. Therefore, by applying Markov’s inequality, we conclude that with probability at least $0.995$,

$$ ${\mathcal{R}}_{N_{\mathrm{pt}}}({\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})-\tau=o(1).$ $$

∎

###### Lemma D.1 .

###### Proof of Lemma D.1 .

###### Lemma D.2 .

###### Proof of Lemma D.2 .

### D.2 Test Error for Prompts with General Length

For the last step, we extend the result of the test error to a general test time context length $N_{\mathrm{test}}=\tilde{\Omega}\left(r^{3\mathrm{ge}(g_{*})}\right)$.

###### Proof of Theorem 3.3 .

To use the result of Lemma [D.2](https://arxiv.org/html/2510.12026v2#A4.Thmtheorem2), we bound the following quantity:

$$ $\displaystyle\quad\left|{\mathcal{R}}_{N_{\mathrm{test}}}({\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})-{\mathcal{R}}_{N_{\mathrm{pt}}}({\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})\right|$ $\displaystyle=\left|\mathbb{E}_{({\bm{Z}},y)\sim{\mathcal{D}}(N^{*})}\left[\left|y-f({\bm{Z}}_{N_{\mathrm{pt}}},{\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})\right|-\left|y-f({\bm{Z}}_{N_{\mathrm{test}}},{\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})\right|\right]\right|$ $\displaystyle\leq\mathbb{E}_{({\bm{Z}},y)\sim{\mathcal{D}}(N^{*})}\left[\left|f({\bm{Z}}_{N_{\mathrm{pt}}},{\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})-f({\bm{Z}}_{N_{\mathrm{test}}},{\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})\right|\right].$ $$

Here, $Z_{N_{\mathrm{pt}}}$ and $Z_{N_{\mathrm{test}}}$ are input embeddings consisting of the first $N_{\mathrm{pt}}$ and $N_{\mathrm{test}}$ context examples, respectively, along with the same query ${\bm{x}}$, when given an prompt ${\bm{Z}}$. From Lemma [A.1](https://arxiv.org/html/2510.12026v2#A1.Thmtheorem1), the following holds with high probability:

$$ $\left|N_{{\mathrm{pt}}}^{-1}{\mathsf{Mamba}}({\bm{Z}}_{{\mathrm{pt}}};{\bm{\gamma}}^{*})-N_{\mathrm{test}}^{-1}{\mathsf{Mamba}}({\bm{Z}}_{\mathrm{test}};{\bm{\gamma}}^{*})\right|=o\left(r^{-3\mathrm{ge}(g_{*})/2}(\log d)^{-2\mathrm{deg}(g_{*})+2-C_{P_{2}})}\right).$ $$

Combining with Lipschitz continuity of ReLU, this implies

$$ $\displaystyle\quad\left|f({\bm{Z}}_{N_{\mathrm{pt}}},{\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})-f({\bm{Z}}_{N_{\mathrm{test}}},{\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})\right|$ $\displaystyle\leq\sum_{j=1}^{m}\left|{\bm{u}}^{*}[j]\right|\left|N_{{\mathrm{pt}}}^{-1}{\mathsf{Mamba}}({\bm{Z}}_{{\mathrm{pt}}};{\bm{\gamma}}^{*})-N_{\mathrm{test}}^{-1}{\mathsf{Mamba}}({\bm{Z}}_{\mathrm{test}};{\bm{\gamma}}^{*})\right|$ $\displaystyle\leq\left\|{\bm{u}}\right\|m^{1/2}\left|N_{{\mathrm{pt}}}^{-1}{\mathsf{Mamba}}({\bm{Z}}_{{\mathrm{pt}}};{\bm{\gamma}}^{*})-N_{\mathrm{test}}^{-1}{\mathsf{Mamba}}({\bm{Z}}_{\mathrm{test}};{\bm{\gamma}}^{*})\right|$ $\displaystyle={\tilde{\mathcal{O}}}(r^{3\mathrm{ge}(g_{*})/2}m^{-1/2})\cdot m^{1/2}\cdot o\left(r^{-3\mathrm{ge}(g_{*})/2}(\log d)^{-2\mathrm{deg}(g_{*})+2-C_{P_{2}})}\right)$ $\displaystyle=o(1),$ $$

where we apply the Cauchy-Schwarz inequality for the last inequality, and the last equality holds since we can make $C_{P_{2}}$ arbitrarily large. Therefore, we have

$$ $\left|{\mathcal{R}}_{N_{\mathrm{test}}}({\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})-{\mathcal{R}}_{N_{\mathrm{pt}}}({\bm{\gamma}}^{*},{\bm{u}}^{*},{\bm{v}}^{*},{\bm{a}}^{*})\right|=o(1),$ $$

and this implies that our desired conclusion holds with probability at least 0.99.
∎

###### Proof of Theorem 3.3 .

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: - Which steps in the argument strictly require the Gaussian inputs and a polynomial link? Can this work be extended to non-Gaussian, or non-polynomial cases, with heavy-tailed noise?
- How do the required prompt lengths and task counts scale as the intrinsic dimension increases?
soundness: 3
strengths: - The paper shows that the nonlinear gate changes the label statistic so the task becomes identifiable. This allows the dependence of the sample complexity on the true nonlinearity of the teacher function.
- The main theorem gives concrete conditions under which a one-layer Mamba with MLP head can learn features from the prompt at test time, and the required number of in-context examples scales with the intrinsic dimension of the task subspace. 
- The detailed analysis and comparison with not only the Transformer architecture but also kernel methods, explain the benefits of gating.
summary: This paper analyzes Mamba's in-context learning on Gaussian single-index models and proves that pretrained Mamba achieves test-time feature learning by gating operation. This enables test-time sample complexity comparable to nonlinear Transformers, and better than linear-Transformers. The main theorem specifies pretrain and context lengths, number of tasks and width needed to achieve low test error with high probability. Experiments with r=8, d=16,32 show comparable performance of Transformer and Mamba, and that the results are insensitive to d. Both models outperform kernel ridge regression even when the kernel operates on the intrinsic features, supporting the main theory of test-time feature learning.
weaknesses: - Although not a major weakness, the distributional assumptions are strong: Gaussian single-index models with polynomial links and Hermite features.
- The experiments can be conducted over more range of intrinsic dimensions or sample sizes.

---

confidence: 4
contribution: 2
initial_rating: 4
presentation: 3
questions: 1. Could the authors consider analyzing Mamba’s training convergence under a more practical optimization process? (Weakness 1)

2. Could the authors provide an analysis of generalization—for example, how the model behaves when the data distribution at test time differs from that during training?
soundness: 3
strengths: 1. Most existing theoretical works on understanding in-context learning (ICL) focus on Transformers, and this paper’s analysis of Mamba—along with its comparison to Transformers—offers valuable and insightful contributions.

2. Provide conceptual insight: The identification of Mamba’s nonlinear gating as the driver of test-time feature learning is conceptually meaningful for understanding gated recurrent architectures.
summary: This paper provides a theoretical analysis of the Mamba architecture’s in-context learning (ICL) capability, focusing on low-dimensional nonlinear target functions. The authors establish that Mamba, when pretrained via a gradient-based algorithm, can achieve efficient in-context feature learning at test time. They prove that Mamba extracts task-relevant features directly from contextual examples, yielding sample complexity comparable to nonlinear Transformers while improving upon linear kernel-based models.
weaknesses: 1. Algorithm 1 appears unnatural. Algorithm 1 optimize the Mamba layer and the MLP layer separately, which is not how neural networks are actually optimized in practice. This mismatch with realistic training procedures weakens the contribution of the paper.

2. The input embedding also appears unnatural and overly hand-crafted, raising doubts about whether real models could actually learn such embeddings in practice.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: 1. Why do you need an MLP layer in your analysis? In line 365, you say the improvement of sample complexity comes from the MLP, then you need to clarify what makes Mamba better than Transformers in some aspect because MLP is not a key difference between Mamba and Transformers from my understanding. You need to distinguish what improvement comes from MLP and what comes from the key component of Mamba, i.e, the nonlinear gating. 

2. Why do you formulate $W_B^\top W_C$ with a simple veector $\gamma$ and why do you initialize $\gamma$ in a sepcial way in line 256?

3. It seems you reduce the analysis of a $d+1$-dimensional $w$ to a scalar $\rho$. What is the reason?

4. Why do you formulate $\phi(\theta)$ in a special way in line 154? Can you handle of case of $\phi(x)=x$?
soundness: 3
strengths: 1. The theoretical analysis is quite strong and solid.

2. The studied problem on Mamba with single-index models is interesting and novel.
summary: This paper studies the ICL ability of Mamba on single-index models by characterizing the optimization dynamics and the sample complexity in pretraining and testing. The theoretical results indicate that Mamba can implement test-time feature learning, which is enabled by the nonlinear gating. The authors also make a comparison between their results and previous works and other archtectures.
weaknesses: 1. The illustration in Section 4 is confusing to me. 

(a) Overall, I think many of this section is not a "proof overview" but some important discussion that you can put in previous sections. In other words, in Section 4.1, you introduce too much about some theoretical conclusions or the differences from existing works rather than the logic chain to derive your main theorem, which should be the proof idea from my understanding. 

(b). Regarding the role of gating and input embedding, $c_\beta$ vanishes when $ie(g_*)>2$ if it is linear attention, but what about Mamba? Do you mean $c_\beta$ will not vanish in this case? When I first read it, I got confused because I thought you would directly answer this question, but you started to talk about the generative exponent. I think it is better to first answer this question or briefly summarize the role of gating at the beginning of this paragraph. 

(c). Proposition 4.1 is still not "informal" enough. Why not directly write $Mamba(\cdot)$ as a $g_*(\cdot)$ function in Eqn. 2? You mention this possibility in line 433 that $g_*(z)$ is a polynomial of $z^{ge(g_*)}$. By the way, I took some time to recall what $P_1$ and $P_2$ are in this proposition. I found they are defined in line 300. It is better to intuitively explain them around this proposition.

2. Not enough experiments are presented. Can you empirically show the advantages of Mamba in sample complexity compared with Transformers, and can you empirically relate it to the nonlinear gating part?

---

confidence: 3
contribution: 2
initial_rating: 4
presentation: 3
questions: 1. Could the authors ellaborate on the fundamental difference between your paper and [1]? Though I haven't read [1] carefully, but it seems to me that your work inherits the target function $f_*$, the learning objective loss $L$, the two-stage pretraining algorithm and the diagonal structure of $W_B^\top W_C$ (which in [1]'s case is $W_Q^\top W_K$, and the $1$ in the right bottom corner could be ommitted because Mamba doesn't have value matrix $W_V$). The main difference is the replacement of the transformer model with the Mamba model, which mimics a linear self attention (admittedly the nonlinear gating may add some difficulty). Overall, I'm concerned about the techinical contribution of this paper and would be willing to reconsider my rating if the authors could convince me of it.


[1] Nishikawa, N., Song, Y., Oko, K., Wu, D., & Suzuki, T. Nonlinear transformers can perform inference-time feature learning. In Forty-second International Conference on Machine Learning.
soundness: 3
strengths: 1. The paper theoretically studies the ICL of Mamba, which is an interesting topic.
2. The paper is the first to provide a sample complexity result on the ICL of Mamba.
3. The writing is clear which makes the paper easy to follow.
summary: The paper studies the in-context learning of Mamba model in a theoretical way. It provides theoretical sample complexity bound on the number of pretraining tasks to achieve a fixed ICL test error via a two-stage gradient pretraining scheme. The paper also proves Mamba can achieve test time feature learning and conducts experiment to verify this.
weaknesses: 1. Since the authors listed proposition 4.1 as one of the core contributions, I think a formal version of it could benefit the paper, because currently it's hard to understand what $P_1$ and $P_2$ stands for without referring to the appendix (Lemma C.1).
2. The experiment doesn't collaborate with the theoretical results well. It only shows that Mamba **can** achieve in-context feature learning, which is not that surprising given empirical results on the ICL of Mamba models [1,2]. Perhaps some trends toward how the number of pretraining tasks affects the final ICL test error could be more relative to the point.
3. I'm currently not so sure about the siginificance of contribution compared with [3]. The two stage learning algorithm and the learning objective in this paper is the same as in [3], and the replacement of a transformer with a Mamba doesn't seem very fundamental.


[1] Grazzi, R., Siems, J., Schrodi, S., Brox, T., & Hutter, F. (2024). Is mamba capable of in-context learning?. arXiv preprint arXiv:2402.03170.

[2] Park, J., Park, J., Xiong, Z., Lee, N., Cho, J., Oymak, S., ... & Papailiopoulos, D. (2024). Can mamba learn how to learn? a comparative study on in-context learning tasks. arXiv preprint arXiv:2402.04248.

[3] Nishikawa, N., Song, Y., Oko, K., Wu, D., & Suzuki, T. Nonlinear transformers can perform inference-time feature learning. In Forty-second International Conference on Machine Learning.


Decision: Reject