in-context learning, operator learning, efficient transformer, linear attention, generalization analysis

1 Introduction↩︎

Transformer-based neural networks have become the foundation of modern deep learning frameworks for natural language processing [@devlinBERTPretrainingDeep2018; @brownLanguageModelsAre2020a] and computer vision [@heMaskedAutoencodersAre2021; @peebles2023scalable]. Especially when trained with large and diverse corpora, transformers exhibit remarkable few/zero-shot generalization capabilities across various downstream tasks [@brownLanguageModelsAre2020a]. An underlying mechanism for this behavior is in-context learning, in which pretrained large language models (LLMs) condition on instructions or a few input-output pairs (both referred to as prompts) and make predictions on test examples without parameter updates. Many theoretical and empirical studies [@xie2022explanation; @garg2023what; @akyurek2023what; @zhang2023trained] have demonstrated that the emergence of in-context learning capability is closely related with the context-aware structure of the attention mechanism [@vaswaniAttentionAllYou2017] which enables each token in a sequence to adaptively weight information from all other tokens and to produce a representation conditioned on the sequence context.

However, the original softmax attention mechanism in [@vaswaniAttentionAllYou2017] is a double-edged sword: while it is beneficial for context-based representation learning, it suffers from quadratic computational complexity with respect to the context length [@zaheer2020big]. As context length grows dramatically, the quadratic computational and memory costs of the standard attention increasingly hinder autoregressive training and inference, undermining LLM performance in long-context modeling scenarios such as processing entire codebases, preserving coherence in long conversations and performing in-depth reasoning across several documents. Therefore, it’s crucial for the design of LLMs to alleviate the curse of quadratic complexity and improve long-context processing capabilities. Numerous works have been recently proposed with this motivation and show performance comparable to the standard attention, including RetNet [@sun2023retentive], Mamba [@guMambaLinearTimeSequence2023], and Gated Linear Attention [@yang2024gated]. One branch of these works is known as linear attention [@katharopoulos2020transformers; @choromanskiRethinkingAttentionPerformers2021; @yang2024gated; @zhang2024hedgehog], which replaces the exponential similarity function with a dot product of key/query functions and yields a linear computational complexity with respect to the context length. This reduction in time and memory cost enables much longer contexts and lower latency during the inference. Meanwhile, the introduction of the hidden-state memory matrix and the forgetting gate improves algorithm stability over utra-long contexts [@yang2024gated]. Although linear attention models have outperformed the softmax attention on some long-context modeling tasks, the theoretical understanding and design principles of these models, especially for in-context learning, remain limited and unexplored.

In this work, we investigate the approximation and generalization abilities of linear transformers with context-augmented inputs to reveal the advantage of the linear attention mechanism for the in-context learning scenario. We establish a connection between in-context learning and domain generalization frameworks and show that transformer-based neural networks perform in-context learning as domain generalization [@blanchard2011generalizing; @blanchard2021domain], and this connection demonstrates the essence of LLMs’ remarkable few/zero-shot generalization capabilities without parameter updates during testing. We work with the formulation in [@liu2025generalization] by representing the context information as a kernel embedding from context probability distributions to vector-valued functions, and exhibit how each word token interacts with the context embedding through an inner product of a tensor product Hilbert space. Based on this framework, we construct a linear transformer to perform in-context learning via a two-staged sampling process, which shows the internal mechanism of the robust generalization capabilities of LLMs. Our main contributions are as follows.

• We present a theoretical analysis framework for the family of linear transformers, one of the most compelling alternatives to the softmax attention in practice. By connecting domain generalization framework with in-context learning, we rigorously prove that linear transformers perform a robust generalization ability under distribution shifts, which builds the theoretical foundation for understanding the generalization abilities of linear transformers in long-context modeling.

• We observe a fast eigendecay phenomenon in the softmax attention weight matrix products of LLMs. We prove that this phenomenon helps linear transformers alleviate the negative effects of distribution shifts, achieve dimension-independent convergence rates in approximation and generalization analysis and efficiently mimic the behavior of the standard attention.

• We investigate the application of likelihood ratio moments to control distribution shifts in domain generalization. We apply a relaxed condition for unbounded likelihood ratios of probability distributions defined on the noncompact space \(\mathbb{R}^d\) and obtain a distribution-dependent concentration inequality for a second stage estimation by the connection between subgaussian norm and finite Rényi divergence.

• We propose a new perspective for linear conversion of LLMs with the softmax attentions based on our theoretical analysis framework. This conversion scheme captures information from data distributions and parameter matrices in pretrained softmax LLMs. It provides a new perspective on designing new activation functions and training loss for linear conversion of softmax LLMs.

In the following part of this paper, we first introduce the motivation and definition of linear transformers and a two-staged sampling process as our learning framework. Section 3 presents the main results on approximation and generalization, with a proof sketch in Subsection 3.3. Section 4 provides further discussion, and Appendix 5 contains the full proofs.

2 Linear Transformers and Formulations for In-Context Learning↩︎

In this Section, we first define the structure of linear transformers whose inputs are pairs \((\hat{\rho},x)\), where \(\hat{\rho}\) the empirical version of distribution \(\rho\) from which \(x\) is sampled. We refer to learning with samples \((\hat{\rho},x)\) as in-context learning, and these samples are generated from the two-staged sampling process defined in Subsection 2.2.

2.1 Linear Transformers↩︎

The standard Transformer [@vaswaniAttentionAllYou2017] consists of blocks of attention mechanisms and shallow networks to process sequential inputs. Let the input sequence \(Q = [x_1, \cdots, x_n]^T\) with token vectors \(x_i \in \mathbb{R}^d\) for \(1 \leq i \leq n\). Then \(Q\) is an input sequence of length \(n\) with feature dimension \(d\). The softmax attention is defined as, for \(1 \leq i \leq n\), \[\begin{align} \label{eq:attention} \operatorname{SoftmaxAttn}(x_i|Q) = \frac{\sum_{j=1}^n \operatorname{sim}(x_i, x_j)(W_v x_j)}{\sum_{j=1}^n \operatorname{sim}(x_i, x_j)} \in \mathbb{R}^d \text{ with } \operatorname{sim}(x_i,x_j) = \exp \left( \frac{\langle W_q x_i, W_k x_j\rangle}{\sqrt{d'}} \right) \end{align}\tag{1}\] where \(W_v \in \mathbb{R}^{d \times d}, W_{q} \in \mathbb{R}^{d' \times d}, W_{k} \in \mathbb{R}^{d' \times d}\) are parameter matrices for value, query, and key token vectors respectively. Intuitively, the attention mechanism \(\operatorname{SoftmaxAttn}\) takes the input sequence \(Q\) as context and produces a refined context-aware representation \(\operatorname{SoftmaxAttn}(x_i |Q)\) for each query token \(x_i\) in \(Q\).

To establish connections between each token and their context and to demonstrate the benefits of context-aware representation produced by the attention mechanism, we follow [@liu2025generalization; @furuyatransformers] to assume that \(Q\) is a realization with \(n\) samples drawn i.i.d. from a Borel probability measure \(\rho\) on \(\mathbb{R}^d\), with \(\rho\) regarded as the ground truth context. Then the RHS of the expression (1 ) can be written as \[\begin{align} \label{eq:context95attn} \operatorname{ SoftmaxAttn }(\hat{\rho},x_i)= \frac{{\int \operatorname{ sim }(x_{i}, x) (W_{v}x) \, d \hat{\rho}(x)}}{\int \operatorname{ sim }(x_{i},x) \, d \hat{\rho}(x)} \in \mathbb{R}^d \end{align}\tag{2}\] where \((\hat{\rho},x_i)\) is a context-augmented input and \(\hat{\rho}= \delta([x_1, \cdots, x_n])\) is the accessible context with \(\delta(\mathcal{S})\) defined as the empirical distribution generated by the dataset \(\mathcal{S}\). With a richer accessible context \(\hat{\rho}\) by more and more samplings from \(\rho\), the empirical distribution \(\hat{\rho}\) can recover the information of the population distribution \(\rho\) and produce more refined context-aware representation for each token \(x_i\), which is consistent with the empirical practice of increasing the context window length \(n\).

However, it’s easy to observe that for each query token \(x_i\) (\(1\leq i \leq n\)), we must evaluate \(\operatorname{sim}(x_i, x_j)\) for all \(1 \leq j \leq n\) and then normalize by \(\sum_{j=1}^n \operatorname{sim}(x_i,x_j)\), which creates an \(n \times n\) attention score matrix and causes both time and memory cost to scale quadratically in the context length \(n\) [@zaheer2020big]. Such quadratic growth poses significant challenges for efficient algorithm design in long-context modeling scenarios. The key idea of linear transformers is to reduce the quadratic time and memory cost to linear dependence on the context length \(n\) by decoupling queries and keys in \(\operatorname{sim}(x_i,x_j)\). By replacing the similarity function \(\operatorname{sim}(x_i,x_j)\) with \(\phi(x_i)^T\phi(x_j)\) where \(\phi:\mathbb{R}^d \to \mathbb{R}^{d'}\) is a feature mapping, a simple linear attention module can be written as \[\begin{align} \label{eq:linear-attention} \operatorname{LinearAttn}(\hat{\rho},x_i) = \frac{{ \phi(x_{i})^{T}\int \phi (x) (W_{v}x) \, d \hat{\rho}(x) }}{\phi(x_{i})^{T} \int \phi(x) \, d \hat{\rho}(x)} = \frac{{ \big[\int (W_{v}x) \phi(x)^T \, d \hat{\rho}(x) }\big]\phi(x_{i})}{\big[\int \phi(x)^T \, d \hat{\rho}(x)\big]\phi(x_i)}. \end{align}\tag{3}\] It’s easy to observe that a universal memory matrix \(\int(W_v x) \phi(x)^T d\hat{\rho}(x) \in \mathbb{R}^{d \times d'}\) can be shared across all query tokens, thus eliminating the need to compute and store the quadratic attention score matrix in 1 . Beyond this computational efficiency, recent empirical studies [@qin2022devil; @yang2024gated; @zhang2024hedgehog] have achieved performances comparable to the softmax attention using linear attentions. Motivated by normalization-free linear attentions in [@qin2022devil] and the design of shallow neural network feature mapping \(\phi\) in [@zhang2024hedgehog], we define Linear Transformers as follows. Let \(\sigma:\mathbb{R} \to \mathbb{R}\) denote the ReLU activation function \(\sigma(u)=\max\{u,0\}\), \(\sigma_{\tanh}:\mathbb{R} \to \mathbb{R}\) denote the tanh activation function \(\sigma_{\tanh}(u) = \frac{\exp(u)-\exp(-u)}{\exp(u)+\exp(-u)}\).

2.2 Two-Staged Sampling Framework for In-Context Learning↩︎

Our first novelty is to formulate the sequential modeling of transformers in in-context learning as the processing context-augmented inputs \((\hat{\rho},x)\) as in 2 3 ?? where samples like \((\hat{\rho},x)\) are generated by a two-staged sampling framework from domain generalization [@blanchard2011generalizing; @blanchard2021domain].

Let \(\mathcal{X} = \mathbb{R}^{d}\) denote the input space and \(\mathcal{Y} = \big\{ y \in \mathbb{R}^{d}: \|y\|_2 \leq M \big\}\) a closed ball with radius \(M >0\) be the output space. Let \(\mathcal{B}_2({\mathcal{X}})\) and \(\mathcal{B}_2({\mathcal{X} \times \mathcal{Y}})\) denote the set of all Borel probability measures with finite second moments on \(\mathcal{X}\) and \(\mathcal{X} \times \mathcal{Y}\), respectively. We equip \(\mathcal{B}_{2}(\mathcal{X})\) and \(\mathcal{B}_{2}(\mathcal{X} \times \mathcal{Y})\) with Wasserstein-2 distances denoted by \(W_2\) which metrize the weak topology on \(\mathcal{B}_{2}(\mathcal{X})\) and \(\mathcal{B}_{2}(\mathcal{X} \times \mathcal{Y})\). Then for context-augment inputs \((\rho,x)\), we define a complete separable metric space \(\Omega = \mathcal{B}_{2}(\mathcal{X})\times \mathcal{X}\) equipped with the metric \(d_{\Omega}\) as \[d_{\Omega}\big((\rho, x), (\rho',x') \big)= \sqrt{W_2(\rho,\rho')^2+\|x-x\|_2^2}.\]

With the two-staged sampling process induced by \(\mathcal{P}_{\mathcal{G}}\), for a prediction function \(\Phi: \Omega \to \mathbb{R}^d\), we define the population risk for in-context learning as \[\begin{align} \label{eq:loss} \mathcal{E}(\Phi)=\mathbb{E}_{\rho_{XY} \sim \mathcal{P}_{\mathcal{G}}} \mathbb{E}_{(X,Y) \sim \rho_{XY}} \| \Phi(\rho_{X},X)-Y \|_{2}^{2} \end{align}\tag{4}\] and the empirical risk with a dataset \(\mathbb{S}=\{(\hat{\rho}_X^{(i)}, X_{ij}, Y_{ij})_{j=1}^{n_i}\}_{i=1}^N\) as \[{\mathcal{E}}_{\mathbb{S}}(\Phi)=\frac{1}{N} \sum_{i=1}^{N} \frac{1}{n_{i}} \sum_{j=1}^{n_{i}} \| \Phi(\hat{\rho}_{X}^{(i)},X_{ij})- Y_{ij} \|_{2}^{2}.\]

Let \(\mathcal{H}_{\mathrm{T}_{n}}\) be the hypothesis space of a collection of linear transformers in Definition 1 and \(\mathrm{T}_{\mathbb{S},n} \in \mathcal{H}_{\mathrm{T}_{n}}\) be the function learned from the empirical risk minimization (ERM) algorithm by \[\begin{align} \label{eq:minimizer} \mathrm{T}_{\mathbb{S},n}=\arg\min_{\mathrm{T}_{n} \in\mathcal{H}_{\mathrm{T}_{n}}}{\mathcal{E}}_{\mathbb{S}}(\mathrm{T}_{n}). \end{align}\tag{5}\] Because of the boundedness of the output space \(\mathcal{Y}\), our estimator is given by \(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})\) where \(\mathscr{T}_{M}\) is a truncation operator defined on \(\mathbb{R}^{d}\) such that \(\mathscr{T}_{M}(y)=y \text{ if } \| y \|_{2} \leq M\) otherwise \(M \frac{y}{\| y \|_{2}}.\)

2.3 Latent Feature Space for Context-Augmented Inputs↩︎

Our second purpose is to investigate how context-augmented samples interact within the attention mechanism and to formulate this interaction into an inner product of a tensor-product Hilbert space (the latent feature space).

To mimic normalization-free attention for \((\rho,x)\) inspired by 2 as \(\int_{\mathcal{X}} \operatorname{sim}(x, x')x' d\rho(x')\), we first introduce an anisotropic Gaussian kernel \(k_{\boldsymbol{\lambda}}\) on \(\mathcal{X} \times \mathcal{X}\) as \[k_{\boldsymbol{\lambda}}(x,x')= \exp(-(x-x')^{T}\Sigma _{\boldsymbol{\lambda}}(x-x'))\] with shape parameter vector \(\boldsymbol{\lambda}=[\lambda_1, \cdots, \lambda_d]^T \in \mathbb{R}^d\) and \(\Sigma_{\boldsymbol{\lambda}}= \operatorname{diag}(\lambda_1^2, \cdots, \lambda_d^2)\). (For more details about the choice of the anisotropic Gaussian kernel, see Subsection 4.4.) We use kernel \(k_{\boldsymbol{\lambda}}\) to measure the similarity between different tokens and then the attention mechanism induced by \(k_{\boldsymbol{\lambda}}\) outputs \(\int_{\mathcal{X}} k_{\boldsymbol{\lambda}}(x,x') x' d\rho(x')\) for the context-augmented input \((\rho,x)\).

To better understand how the attention mechanism processes context information for context-augmented inputs, we introduce the following definition for context embedding.

Intuitively, \(K_{\boldsymbol{\lambda}}\) embeds context information \(\rho\) into a dictionary function mapping each query \(x_{\text{query}}\) to a context-aware representation \[K_{\boldsymbol{\lambda}}(\rho)(x_{\text{query}}) = \int_{\mathcal{X}}k_{\boldsymbol{\lambda}}(x_{\text{query}},x) x \, d\rho(x) \in \mathbb{R}^d.\]

Next, we define a feature mapping \(\mathrm{I}_{\boldsymbol{\lambda}}\) and a latent feature space \(\mathcal{H}_{\mathcal{F}}\) for context-augmented inputs \((\rho,x)\in \Omega\). In the latent feature space \(\mathcal{H}_{\mathcal{F}}\), the similarity measure between context inputs not only depends on context information, but also has the properties of the attention mechanism.

The similarity between context-augmented inputs \((\rho,x)\) and \((\rho,x')\) defined in (?? ), depends not only on the token values but also on the contexts \(\rho\) and \(\rho'\). This is consistent with a basic observation in natural language processing: a word may have different meanings in different contexts.

3 Main Results↩︎

This section states the main results of approximation and generalization analysis for in-context learning with linear transformers. We first introduce some assumptions on \(\mathcal{P}_{\mathcal{G}}\) for the two-staged sampling process and \(k_{\boldsymbol{\lambda}}\) for the latent feature space.

The two-staged sampling process induced by \(\mathcal{P}_{\mathcal{G}}\) in Definition 2 introduces a probability measure \(\mathcal{P_{G}^{X}}\) on \(\mathcal{B}_{2}(\mathcal{X})\) for context information by \[\begin{align} \label{eq:context95measure} \mathcal{P_{G}^{X}}(E) = \mathcal{P}_{\mathcal{G}}\big( \{\mu \in \mathcal{B}_{2}(\mathcal{X} \times \mathcal{Y}): \mu \circ \pi_{\mathcal{X}}^{-1} \in E \} \big) \end{align}\tag{6}\] for any Borel set \(E \in \mathcal{B}_{2}(\mathcal{X})\) with the coordinate map \(\pi_\mathcal{X}: \mathcal{X} \times \mathcal{Y} \to \mathcal{X}\), and also a probability measure \(\nu_{\mathcal{G}}\) for context-augmented inputs on the product \(\sigma\)-algebra of \(\Omega\) by \(\nu_{\mathcal{G}}(B\times A)=\int_B \rho(A) d \mathcal{P_{G}^{X}}(\rho)\) for any Borel set \(B \in \mathcal{B}_{2}(\mathcal{X}), A\in \mathcal{X}\).

We provide two examples of meta probability measure \(\mathcal{P_{G}^{X}}\) satisfying Assumptions 1 and 2 in Appendix 7.

3.1 Approximation of Variation Normed Functions↩︎

Our third contribution is to propose an explicit hypothesis space under which linear transformers achieve dimension-independent convergence rates for operator approximation without assuming access to the structure of a latent feature space \(\mathcal{H}_{\mathcal{F}}\), enabling further study on generalization error analysis.

First we impose a regularity condition on the true predictor for 4 using the latent feature mapping \(\mathrm{I}_{\boldsymbol{\lambda}}\) in ?? and a variation normed space. Let \(\mathcal{H}_{\mathrm{para}}=\mathcal{H}_{\mathcal{F}} \oplus \mathbb{R}\) (the extra dimension is left for bias weights) and \[\begin{align} \mathrm{B}(\mathcal{H}_{\mathrm{para}};\mathbb{R}^{d})= \Bigl\{ W \in \mathcal{L}(\mathcal{H}_{\mathrm{para}};\mathbb{R}^{d}) \,\Big| \, \| W \|_{\mathrm{op}} \leq 1 \Bigr\} \end{align}\] the closed unit ball with the operator norm in the space \(\mathcal{L}(\mathcal{H}_{\mathrm{para}};\mathbb{R}^{d})\) of all bounded linear operators from \(\mathcal{H}_{\mathrm{para}}\) to \(\mathbb{R}^{d}\). Note that the finite dimension of the output space makes \(\mathcal{L}(\mathcal{H}_{\mathrm{para}};\mathbb{R}^{d})\) identical with the Hilbert space of Hilbert-Schmidt operators, and hence \(\mathrm{B}(\mathcal{H}_{\mathrm{para}};\mathbb{R}^{d})\) is weakly compact in \(\mathcal{L}(\mathcal{H}_{\mathrm{para}};R^{d})\). Let \(\mathcal{M}(\mathrm{B}(\mathcal{H}_{\mathrm{para}};\mathbb{R}^{d}))\) denote the space of all signed Radon measures on \(\mathrm{B}(\mathcal{H}_{\mathrm{para}};\mathbb{R}^{d})\).

Then we give a dimension-independent approximation result with the hypothesis space \[\label{eq:hyp} \begin{align} &\mathcal{H}_{\mathrm{T}_{n}}=\Biggl\{ \mathrm{T}_{n}: \| \alpha \|_{1} \leq 2C_F, \sum_{p,q =1}^{m(n)}\left\| A_{p,q}^{(j)} \right\|_{F}^{2} \leq d,\| b_{j} \|_{2} \leq \sqrt{ 2dC_{\mathcal{B}}} \text{ for each } 1\leq j \leq n, \\ &\| b_{0} \|_{2} \leq C_F \sqrt{ 2dC_{\mathcal{B}}}, \,\left\| \Theta _{\tanh} \right\|_{\infty} \leq c_{1}(c_{2}\log(n))^{c_{3}(\log n)^{2}} \text{ and truncation level }v=C_{\mathcal{B}}\Biggr\}. \end{align}\tag{7}\] where \(C_F >0\) is a constant, \(c_1,c_2,c_3\) are constants depending on \(\theta,\gamma\) and \(\Theta_{\operatorname{tanh}}\) denotes the parameters in two-layered tanh neural networks satisfying a sparse structure such that \[\begin{align} W_{q,j} = \operatorname{diag}(W_{q,j}^{(1)} , ..., W_{q,j}^{(d)}) \text{ for }j=0,1,2 \end{align}\] where for \(1 \leq l \leq d\), \(W_{q,0}^{(l)} \in \mathbb{R}^{8\tilde{m}(n)\times 1}, W_{q,1}^{(l)}\in\mathbb{R}^{8\tilde{m}(n)\times 8\tilde{m}(n)}\) and \(W_{q,2}^{(l)}\in \mathbb{R}^{1 \times 8\tilde{m}(n)}\).

Let \(\tilde{X}=(\rho_X,X)\) be the context-augmented input with the ground truth context, and \(\tilde{X}_{ij}=(\hat{\rho}_{X}^{(i)},X_{ij})\) with the accessible context. We rewrite \(\mathcal{E}(\Phi)=\mathbb{E}_{(\tilde{X},Y)\sim \mathbb{P}_{\mathcal{G}}} \|\Phi(\tilde{X}) - Y\|_2 ^2\) where \(\mathbb{P}_{\mathcal{G}}\) is a probability measure induced by the two-staged sampling process with \(\mathcal{P}_{\mathcal{G}}\) [@blanchard2021domain]. Then the regression function for the population risk \(\mathcal{E}\) is defined as \[\begin{align} \label{eq:reg} \Phi _{\mathcal{G}}(\tilde{X})= \int_{\mathcal{Y}}y \, d\, \mathbb{P}_{\mathcal{G}}(\cdot| \tilde{X}). \end{align}\tag{8}\]

3.2 Generalization Analysis of In-Context Learning↩︎

Our final contribution is to address unbounded sampling (without domain restrictions) in the two-staged sampling process and establish an oracle inequality in Appendix 5.2. Combining Theorem 1 with this oracle inequality, we obtain a dimension-independent generalization rate.

3.3 Proof Sketch↩︎

The proof of the approximation result in Theorem 1 relies on the following error decomposition \[\label{eq:apperror} \begin{align} &\left\| \Phi _{\mathcal{G}}- \mathrm{T}_{2n,m,\tilde{m}} \right\|_{L^{2}(\nu_{\mathcal{G}})}\\ \leq & \| \Phi _{\mathcal{G}}-\mathcal{N}_{2n} \|_{L^{2}(\nu_{\mathcal{G}})}+ \| \mathcal{N}_{2n}- \Psi _{2n,m} \|_{L^{2}(\nu_{\mathcal{G}})}+ \left\| \Psi _{2n,m}- \mathrm{T}_{2n,m,\tilde{m}} \right\|_{L^{2}(\nu_{\mathcal{G}})} \end{align}\tag{9}\] for \(\mathrm{T}_{2n,m,\tilde{m}} \in \mathcal{H}_{\mathrm{T}_{2n}}\), where \(\mathcal{N}_{2n}\) is a shallow neural network with operator-valued parameters in \(\mathcal{L}(\mathcal{H}_{\mathrm{para}};\mathbb{R}^d)\) and \(\Psi _{2n,m}\) is a neural network with latent polynomial features depending on the parameterization of \(k_{\boldsymbol{\lambda}}\), both explicitly constructed in Section 5.1.

The approximation error \(\| \Phi _{\mathcal{G}}-\mathcal{N}_{2n} \|_{L^{2}(\nu_{\mathcal{G}})}\) is estimated by random approximation results from [@korolev2022twolayer] in Appendix 5.1. The estimation of the last two terms in the RHS of (9 ) relies on Assumption 2 to bound \(L^2\) errors under first-stage samples \(\rho_X\) with \(L^2\) error under the reference probability distribution \(\rho _{\kappa}\), as described in Appendix 5.1.1 and 5.1.2. More specifically, for the second term \(\| \mathcal{N}_{2n}- \Psi _{2n,m} \|_{L^{2}(\nu_{\mathcal{G}})}\), \(\mathcal{N}_{2n}\) can be regarded as a neural network with countably infinite feature-function parameters in an RKHS, and \(\Psi _{2n,m}\) is a neural network constructed by the optimal choice of selecting only \(m\) feature-function parameters based on the parameterization of \(k_{\boldsymbol{\lambda}}\). For the last term \(\left\| \Psi _{2n,m}- \mathrm{T}_{2n,m,\tilde{m}} \right\|_{L^{2}(\nu_{\mathcal{G}})}\), the idea is to show the linear attentions in \(\mathrm{T}_{2n,m,\tilde{m}}\) are fast universal approximators for any feature-function parameters in RKHS \(\mathcal{H}_{k_{\boldsymbol{\lambda}}}\) without any prior knowledge on the parameterization of \(k_{\boldsymbol{\lambda}}\). The approximation is considered with the supremum norm on the bounded domain \([-B, B]^d\), and the error outside this domain is controlled by a Gaussian tail decay (see Appendix 8.2).

For the generalization analysis, we define the first-stage sampling error \(\mathcal{E}_{N}\) as \[\mathcal{E}_{N} (\Phi)= \frac{1}{N} \sum_{i=1}^{N} \mathbb{E}\Big[\| \Phi (\tilde{X})-Y \|_{2}^{2} |\rho_{XY}^{(i)}\Big]\] and the second-stage sampling error \(\mathcal{E}_{N,\mathcal{X}}\) with ground truth context as \[\mathcal{E}_{N,\mathcal{X}}(\Phi)= \frac{1}{N}\sum_{i=1}^{N} \frac{1}{n_{i}} \sum_{j=1}^{n_{i}} \| \Phi(\rho_{X}^{(i)}, X_{ij})- Y_{ij} \|_{2}^{2}.\]

Then for any \(\Phi \in \mathcal{H}_{\mathrm{T}_{n}}\), we have the following error decomposition \[\begin{align} \mathcal{E}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))- \mathcal{E}(\Phi _{\mathcal{G}}) &= \mathcal{E}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))- \mathcal{E}_{N}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))+ \mathcal{E}_{N}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))- \mathcal{E}_{N,\mathcal{X}}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))\\&+ \mathcal{E}_{N,\mathcal{X}}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))-\mathcal{E}_{\mathbb{S}}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})) + \mathcal{E}_{\mathbb{S}}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))- \mathcal{E}_{\mathbb{S}}(\Phi) \\ &+\mathcal{E_{\mathbb{S}}}(\Phi) - \mathcal{E}_{N,\mathcal{X}}(\Phi) + \mathcal{E}_{N,\mathcal{X}}(\Phi)- \mathcal{E}_{N}(\Phi)+\mathcal{E}_{N}(\Phi)-\mathcal{E}(\Phi) \\ &+ \mathcal{E}(\Phi)- \mathcal{E}(\Phi _{\mathcal{G}}) \end{align}\] with \(\mathcal{E}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))- \mathcal{E}(\Phi _{\mathcal{G}})= \| \mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})- \Phi _{\mathcal{G}}\|_{L^2(\nu_{\mathcal{G}})}^2\) and \(\mathcal{E}_{\mathbb{S}}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))- \mathcal{E}_{\mathbb{S}}(\Phi) \leq 0.\)

Let \[\begin{align} & \mathcal{E}_{1}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))= \Big(\mathcal{E}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))- \mathcal{E}(\Phi _{\mathcal{G}})\Big) - \Big(\mathcal{E}_{N}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))-\mathcal{E}_{N}(\Phi _{\mathcal{G}} )\Big), \\ & \mathcal{E}'_{1}(\Phi)= \Big(\mathcal{E}_{N}(\Phi)-\mathcal{E}_{N}(\Phi _{\mathcal{G}}) \Big)-\Big(\mathcal{E}(\Phi)-\mathcal{E}(\Phi _{\mathcal{G}}) \Big) , \\ & \mathcal{E}_{2}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})) = \mathcal{E}_{N}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})) - \mathcal{E}_{N,\mathcal{X}}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})), \\ & \mathcal{E}'_{2} (\Phi) = \mathcal{E}_{N,\mathcal{X}}(\Phi ) -\mathcal{E}_{N}(\Phi) , \\ & \mathcal{E}_{3}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})) = \mathcal{E}_{N,\mathcal{X}}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})) - \mathcal{E}_{\mathbb{S}}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})), \\ & \mathcal{E}'_{3}(\Phi) = \mathcal{E}_{\mathbb{S}}(\Phi)-\mathcal{E}_{N,\mathcal{X}}(\Phi) \text{ and } \mathcal{E}_{4}(\Phi) = \mathcal{E}(\Phi)- \mathcal{E}(\Phi _{\mathcal{G}}). \end{align}\] Then we have \[\label{eq:error} \begin{align} \mathcal{E}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))- \mathcal{E}(\Phi _{\mathcal{G}})\leq& \mathcal{E}_{1}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))+\mathcal{E}'_{1}(\Phi)+ \mathcal{E}_{2}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))+ \mathcal{E}'_{2}(\Phi)\\&+\mathcal{E}_{3}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))+\mathcal{E}'_{3}(\Phi)+\mathcal{E}_{4}(\Phi). \end{align}\tag{10}\]

In the first-stage sampling, we control the effect of unbounded sampling on \(\mathcal{E}_{1}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))\) by using the covering number under a pseudo-metric defined by the supremum of distribution expectations over \(\mathcal{B}_{2,b}(\mathcal{X})\) (Appendix 5.2.3). In the second-stage sampling, the situation becomes more complicated with the structure of linear transformers, so we decompose the second-stage sampling error into two parts: \(\mathcal{E}_{2}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})),\mathcal{E}'_{2}(\Phi)\) defined using ground truth contexts (called pseudo second-stage sampling in Appendix 5.2.4) and \(\mathcal{E}_{3}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})),\mathcal{E}'_{3}(\Phi)\) defined using accessible contexts (Appendix 5.2.5).

For the case with ground truth contexts, the similar idea with the first-stage sampling applies: after introducing Rademacher complexity for sampling estimation, we bound the empirical process by the Dudley integral. We then use concavity to move the expectations over second stage samples into the covering number expression, thereby eliminating the effect of unbounded samples. For the last sampling estimation with accessible contexts, the problem becomes even more challenging in the presence of memory units in linear transformers, since both the input samples and the memory-unit outputs are unbounded. Here, we apply an extension of Azuma-McDiarmind’s inequality under subgaussian conditions to obtain a distribution-dependent probability concentration inequality where an observation on the relation between \(\|\omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})}\) and subgaussian norm plays an important role. To obtain the final generalization error, we apply the expectation identity for non-negative random variables to bring \(\|\omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})}\) out of the denominator and the exponential, so that we can take an expectation of \(\|\omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})}\) with respect to \(\mathcal{P_{G}^{X}}\) by Assumption 2.

4 Related Works and Discussions↩︎

4.1 In-Context Learning↩︎

Prior studies [@garg2023what; @akyurek2023what; @zhang2023trained; @shen2025understanding] often formulate in-context learning as predicting the label of a given sample conditioned an input prompt containing other samples and labels. As noted in [@zhang2023trained], a model \(\Phi\) performs in-context learning as \[\Phi: \mathcal{S} \times \mathcal{X} \to \mathcal{Y}, \quad \mathcal{S}= \cup_{n \in \mathbb{N}} \big\{(x_1,y_1,...,x_n,y_n): x_i \in \mathcal{X}, y_i \in \mathcal{Y}\big\}\] where \(\mathcal{X}\) is the input space and \(\mathcal{Y}\) the output space, and \(\Phi\) is trained on prompts of the form \(\mathscr{P}=(x_1,h(x_1), ..., x_{\vartheta},h(x_{\vartheta}),x_{\text{query}})\) with \(h \sim \mathcal{P}\) a distribution defined on a function space \(H\) to minimize the error \(\mathbb{E}_{\mathscr{P}}l(\Phi(\mathscr{P}), h(x_{\text{query}}))\) with a loss function \(l\). Previous theoretical work has focused on linear function spaces [@zhang2023trained] and Hölder spaces [@shen2025understanding]. These studies have demonstrated that transformers can perform well on structured prompts of input-output pairs, but this formulation has two limitations to bridge the gap between theory and application [@min2022rethinking]. First, in-context learning emerges as a property of LLMs after pretraining on tasks like autoregression or diffusion-based generation. A pretrained LLM can perform in-context learning without any parameter updates [@xie2022explanation], which is not consistent with theoretical settings that require training on structured prompts. Second, prompts for in-context learning are often unstructured and may lack labels. For example, in machine translation from English to French, the input prompt may contain only instructions in English. Empirical studies [@min2022rethinking] also show that the correct mapping between inputs and true labels in prompts has little performance gains for in-context learning: model performance with random labels closely matches that with true labels.

We address these problems by the domain generalization framework [@blanchard2011generalizing; @blanchard2021domain] and formulate in-context learning as operator learning with the two-staged sampling process: \[\begin{align} \label{def:in-context} \Phi: \hat{\rho}_X^{(i)} \mapsto (h: \mathcal{X} \to \mathcal{Y}), \quad \hat{\rho}^{(i)}_X= \delta([x_{i1},..., x_{in_i}]) \text{ with }x_{ij} \in \mathcal{X}. \end{align}\tag{11}\] This formulation suggests that the operator \(\Phi\) maps the context distribution \(\hat{\rho}^{(i)}_X\) to a response function \(h_{\hat{\rho}^{(i)}_X}\) that takes queries from \(\mathcal{X}\) and outputs \(h_{\hat{\rho}^{(i)}_X}(x_{\text{query}})\) for any \(x_{\text{query}} \in \mathcal{X}\), which aligns with both the nature of transformers as context-based representation learning and also the parameter-freezing setting after pretraining for in-context learning. With a richer unstructured prompt \([x_{i1},...,x_{in}]\) by more and more samplings (\(X_{ij} {\sim} \rho^{(i)}_X\)) from the ground truth context distribution \(\rho^{(i)}_X\), the empirical context distribution \(\hat{\rho}^{(i)}_X\) can recover \(\rho^{(i)}_X\) and then \(\hat{\Phi}(\hat{\rho}^{(i)}_X)\) can well approximate \(\Phi({\rho}^{(i)}_X)\) without parameter updates, where \(\hat{\Phi}\) is a pretrained Transformer model to approximate the operator \(\Phi\).

4.2 Normalization Factor and RMSNorm↩︎

Early linear attention models [@katharopoulos2020transformers; @choromanskiRethinkingAttentionPerformers2021] have some softmax-inspired design features 1 , such as inserting a normalization denominator as in 3 . However, [@qin2022devil] demonstrates both theoretically and empirically that linear transformers with 3 make the gradients for attention matrices unbounded and lead to a less stable optimization and worse convergence. To alleviate this negative effect, [@qin2022devil] removes the normalization factor in 3 and applies RMSNorm [@zhang2019root] to the linear attention output: \[\begin{align} \label{eq:dev95lin} O_{\text{norm}} = \operatorname{RMSNorm}(Q(K^TV)) \end{align}\tag{12}\] where \[\begin{align} Q &= [\phi(Q_1), \cdots, \phi(Q_n)]^T \in \mathbb{R}^{n \times d'}, \\ K &= [\phi(K_1), \cdots, \phi(K_n)]^T \in \mathbb{R}^{n \times d'}, \\ V & = [V_1, \cdots, V_n]^T \in \mathbb{R}^{n \times d} \end{align}\] and for input \(A=(a_{ij})_{i,j} \in \mathbb{R}^{n \times d}\), \(A'=\operatorname{RMSNorm}(A) \in \mathbb{R}^{n \times d}\) is defined as \[\begin{align} A'=(a'_{ij})_{i,j} \text{ such that }a'_{ij}= \frac{a_{ij}}{\sqrt{\frac{1}{d}\sum_{j=1}^d a_{ij}^2 + \epsilon}} \cdot \beta_j \end{align}\] with learnable scaling factor \(\boldsymbol{\beta}=(\beta_1, ...,\beta_d)^T \in \mathbb{R}^d.\) RMSNorm reduces the amount of computation and increases efficiency over LayerNorm, and it is widely used in the open-weight LLMs like Qwen3 [@yang2025qwen3a].

4.3 Activation Functions in LLM↩︎

The design of activation functions has evolved with the development of LLMs. While the original transformer used ReLU activation by default, early LLMs such as BERT and GPT-2/3 employed the Gaussian Error Linear Unit (GeLU) activation [@hendrycks2023gaussian], and it then became the standard choice. For \(x \in \mathbb{R}^d\), GeLU is defined as \[\operatorname{GeLU}(x)= x \odot \operatorname{F}(x)\] where \(\odot\) denotes the Hadamard product and \(\operatorname{F}\) denotes the cumulative distribution function for the standard gaussian and applies element-wise on \(d\)-dimensional vectors. In practice, GeLU activation function is often implemented via a tanh approximation ³ as \[\begin{align} \operatorname{GeLU}(x) \approx 0.5x\odot\left[1+\sigma_{\tanh}\left(\sqrt{\frac{2}{\pi}} \left(x+0.044715x^{\odot3}\right)\right)\right]. \end{align}\] where \(x^{\odot3}\) denotes the Hadamard power of order \(3\). Similar activation functions such as Swish activation [@ramachandran2017searching] were introduced later. It’s worth noting that Swish activation is defined as \[\begin{align} \operatorname{Swish}_{\beta}(x) = x \odot \operatorname{Sigmoid}(\beta\, x) \end{align}\] where \(\beta \in \mathbb{R}\) is a constant or learnable parameter and \(\operatorname{Sigmoid}\) applies element-wise on \(x\) with \[\begin{align} \label{eq:tanh} \operatorname{Sigmoid}(a) = \frac{1}{1+ \exp(-a)}=\frac{1}{2}(1+ \sigma_{\tanh}(a/2)) \text{ for } a \in \mathbb{R}. \end{align}\tag{13}\] SiLU is a special case of Swish with \(\beta=1\).

Finally, combining all tricks above, [@shazeer2020glu] proposed SwiGLU which is widely used in modern LLMs and defined as \[\begin{align} \operatorname{SwiGLU}_{\beta}(x) = W_o((W_1x+b_1) \odot \operatorname{Swish}_{\beta}( W_2x+b_2)). \end{align}\] In our definition of linear transformers [def:transformer], we use three nonlinear components: Tanh activation, product gate, and ReLU activation. It is easy to observe the connection between tanh activation and SwiGLU by Equation 13 . For ReLU activation, when \(\beta\) is large enough, \(\operatorname{Sigmoid}(\beta \, a)\) approximates the indicator function (except at zero) and \(\operatorname{Swish}_{\beta}\) behaves like a ReLU activation function. For product gate, when \(\beta=0\), \(\operatorname{Swish}_{\beta}(x)=x/2\) and then we can obtain \(x \odot x\) by SwiGLU activation with a suitable choice of parameters [@ramachandran2017searching].

4.4 Linear Conversion of Softmax LLMs↩︎

Distilling knowledge from pretrained softmax LLMs into subquadratic models [@zhang2024hedgehog] has recently attracted interest in the research community. Here, we present a perspective on linearizing pretrained softmax LLMs, derived from our theoretical analysis framework.

Recall the softmax attention module 1 . Following [@tsai2019transformer; @liu2025generalization], we take a kernelized viewpoint of attention modules by letting similarity function \(\operatorname{sim}(x_{i},x_{j})= \exp(\langle W_{q}x_{i},W_{k} x_{j}\rangle)\). Then 1 can be written as \[\begin{align} \label{eq:attn} \operatorname{SoftmaxAttn}(x_{i}|Q)= \frac{1}{\mathrm{Z}(x_{i})}\sum_{j=1}^{n}\operatorname{sim}(x_{i},x_{j})(W_{v}x_{j}) \end{align}\tag{14}\] where \(\mathrm{Z}(x_{i})= \sum_{j=1}^{n}\operatorname{sim}(x_{i},x_{j})\) is a normalization factor. For each pair of query and key weight matrices \((W_{q},W_{k})\), we perform singular value decomposition \(W_{q}^{T}W_{k}=W_1^{T} \Sigma_{\boldsymbol{\lambda}} W_2\) where \(W_1,W_2\) are \(d \times d\) orthogonal matrices and \(\Sigma_{\boldsymbol{\lambda}}\) is a positive diagonal matrix with rank \(d_{hidden}\). It’s obtained that

\[\label{eq:sim} \begin{align} \operatorname{sim}(x_{i},x_{j})&=\exp(x_{i}^{T}W_1^{T}\Sigma_{\boldsymbol{\lambda}} W_2x_{j})= \exp(\tilde{x}_{i}^{T}\Sigma_{\boldsymbol{\lambda}}\hat{x}_{j})\\&=\exp\left( \frac{1}{2} \tilde{x}^{T}_{i}\Sigma_{\boldsymbol{\lambda}} \tilde{x}_{i} \right)\exp \left( \frac{1}{2} \hat{x}^{T}_{j} \Sigma_{\boldsymbol{\lambda}}\hat{x}_{j}\right) \exp\left( -\frac{1}{2} (\tilde{x}_{i}-\hat{x}_{j})^{T}\Sigma_{\boldsymbol{\lambda}} (\tilde{x}_{i}-\hat{x}_{j}) \right) \end{align}\tag{15}\] with query \(\tilde{x}_{i}=W_1x_{i}\) and key \(\hat{x}_{j}=W_2x_{j}\). From the above expression, we observe that the roles of the key and query matrices can be decomposed into kernel asymmetry between queries and keys, represented by orthogonal matrices \(W_1,W_2\), and geometric information, represented by a diagonal matrix \(\Sigma_{\boldsymbol{\lambda}}\). In Figure 1, we show a numerical demonstration of singular values in diagonal matrices \(\Sigma_{\boldsymbol{\lambda}}\) in the attention modules of large language model Qwen3 [@yang2025qwen3a] , which exhibits a rapid decay of singular values across layers, nearly exponential for large \(d\). The rapid decay of shape parameters enables us to design linear transformers that efficiently mimic softmax attention and alleviate the negative effects of distribution shifts in our analysis.

For the construction of a linear attention, the key is to decouple the interaction in \(\operatorname{sim}(x_i, x_j)\) between queries and keys as shown in (3 ). For similarity function in Equation 15 , the target is to find a decoupling of query-key interaction between \(\tilde{x}\) and \(\hat{x}\) for the anisotropic gaussian kernel \(k_{\boldsymbol{\lambda}}(\tilde{x},\hat{x})=\exp (- \frac{1}{2}(\tilde{x}-\hat{x})^T \Sigma_{\boldsymbol{\lambda}}(\tilde{x}-\hat{x}))\) to mimic context modeling in softmax attention. In Appendix 8.1, we know that there’s an optimal linear approximation scheme for context embedding, denoted as \((\psi^{\boldsymbol{\lambda}}_q)_{q=1}^m\) with explicit expressions, which only depends on geometric information of \(\Sigma_{\boldsymbol{\lambda}}\) and underlying context distributions on \(\mathbb{R}^d\). With a suitable choice of \(m\), we have \[\begin{align} \label{sim:decom} \operatorname{sim}(x_i, x_j) \approx \sum_{q=1}^m \underbrace{ \exp\left( \frac{1}{2} \tilde{x}_{i}^{T}\Sigma _{\boldsymbol{\lambda}}\tilde{x}_{i} \right) \psi^{\boldsymbol{\lambda}}_{q}(\tilde{x}_{i}) }_{ query } \cdot \underbrace{ \exp\left( \frac{1}{2} \hat{x}_{i}^{T}\Sigma _{\boldsymbol{\lambda}}\hat{x}_{i} \right) \psi^{\boldsymbol{\lambda}}_{q}(\hat{x}_{i}) }_{ key }. \end{align}\tag{16}\]

Compared with previous methods [@katharopoulos2020transformers; @choromanskiRethinkingAttentionPerformers2021] for linear attention, the choice of \((\psi^{\boldsymbol{\lambda}}_q)\) captures the latent data structures learned by the pretrained softmax LLM and makes use of its parameters. However, in practice, it may be difficult to directly apply the approximation (16 ), because the semantic distributions of tokens are highly anisotropic and hard to estimate, while we use an isotropic Gaussian to roughly control the class of distributions in the two-staged sampling process. But it still provides us an idea to design new activation functions and regularity for feature mappings for linear conversion of pretrained softmax LLMs, just as in [@zhang2024hedgehog].

4.5 Conclusion↩︎

In this paper, we investigate the approximation and generalization ability of linear transformers under the two-staged sampling process from domain generalization. We demonstrate that the remarkable generalization and in-context learning capacities are closely related with context-aware structures in linear transformers, and we obtain a dimension-independent convergence rate in the generalization analysis that reveals a trade-off between the regularity of data distributions and the rate of spectral decay. It would be interesting to investigate the linearization algorithm proposed in Subsection 4.4 through extensive empirical experiments with various open-weight LLMs and optimization methods from theoretical aspects in operator learning [@mucke2021stochastic; @nguyen2024optimal]. An efficient, tunable conversion algorithm would be a breakthrough for adapting LLMs to long-context scenarios. On the other hand, hybrid models with both linear and softmax attention have shown their potentials to take advantage of both architectures, and theoretical analysis for such hybrid models would be important for understanding the mathematical foundations of Transformer variants.

5 Proof Details↩︎

5.1 Theorem 1: Approximation Scheme by Linear Transformers↩︎

By Proposition [prop:il], we know that \(\mathrm{I}_{\boldsymbol{\lambda}}:\Omega \to \mathcal{H}_{\mathcal{F}}\) is continuous, which introduces a pushforward probability measure \(\mu_{\mathcal{G}}\) on \(\mathcal{H}_{\mathcal{F}}\) by \(\mu_{\mathcal{G}}=\nu_{\mathcal{G}}\circ \mathrm{I}_{\boldsymbol{\lambda}}^{-1}\). Then we define a probability measure \(\tilde{\mu}_{\mathcal{G}}=\mu_{\mathcal{G}}\times \delta_1\) on \(\mathcal{H}_{\mathrm{para}}\). For \(h\in \mathcal{H}_{\mathrm{para}}\), let \(h_{\mathcal{F}}= \operatorname{Proj}_{\mathcal{H}_{\mathcal{F}}}(h)\) and we have \[\begin{align} \int _{\mathcal{H}_{\mathrm{para}}} \| h \|_{\mathcal{H}_{\mathrm{para}}}^{2} \, d \tilde{\mu}_{\mathcal{G}}(h)&= 1+\int _{\mathcal{H}_{\mathcal{F}}} \| h_{\mathcal{F}} \|_{\mathcal{H}_{\mathcal{F}}}^{2} \, d \mu_{\mathcal{G}}(h_{\mathcal{F}}) =1+ \int _{\Omega _{\mathcal{B}}} \| K_{\boldsymbol{\lambda}}(\rho) \otimes k_{\boldsymbol{\lambda}}(x,\cdot) \|_{\mathcal{H}_{\mathcal{F}}}^{2} \, d \nu_{\mathcal{G}}(\rho,x) \\ & = 1+ \int _{\Omega _{\mathcal{B}}} \| K_{\boldsymbol{\lambda}}(\rho) \|_{\mathcal{H}_{k_{\boldsymbol{\lambda}}}\otimes \mathbb{R}^{d}}^{2}\| k_{\boldsymbol{\lambda}}(x,\cdot) \|_{\mathcal{H}_{k_{\boldsymbol{\lambda}}}}^{2} \, d \nu_{\mathcal{G}}(\rho,x) \leq 1+ C_{\mathcal{B}}. \end{align}\]

We also note that for \(W\in \mathcal{L}(\mathcal{H}_{\mathrm{para}};\mathbb{R}^d)\), \(\|W\|_{\text{op}}\leq \|W\|_{\text{HS}}\leq \sqrt{d}\|W\|_{\text{op}}\) where \(\|\cdot\|_{\text{HS}}\) denotes Hilbert-Schmidt norm of \(\mathcal{HS}(\mathcal{H}_{\mathrm{para}};\mathbb{R}^d)\). let \(\{e_l\}_{l=1}^d\) denote an orthonormal basis of \(\mathbb{R}^d\) and for any \(h \in\mathcal{H}_{\mathrm{para}}\), we have \(\langle Wh, e _{l} \rangle _{\mathbb{R}^{d}}= \langle h, W^{*} e _{l} \rangle _{\mathcal{H}_{\mathrm{para}}}\). Denote \(w_{l}=W^{*}e _{l} \in \mathcal{H}_{\mathrm{para}}\) and then \[\begin{align} \label{eq:operator} Wh= \sum_{l=1}^{d} \langle h, w_{l} \rangle _{\mathcal{H}_{\mathrm{para}}} e _{l}= \sum_{l=1}^{d} (e _{l} \otimes w _{l})h. \end{align}\tag{17}\] It implies that the elements in \(\mathrm{B}(\mathcal{H}_{\mathrm{para}};\mathbb{R}^{d})\) share the form \(W=\sum_{l=1}^{d} e _{l} \otimes w_{l}\) where \(w_{l} \in \mathcal{H}_{\mathrm{para}}\) such that \[\begin{align} \| W \|_{\mathrm{op}}= \sup_{\| h \|_{\mathcal{H}_{\mathrm{para}}}= 1} \left( \sum_{l=1}^{d} \langle w_{l},h \rangle _{\mathcal{H}_{\mathrm{para}}}^{2} \right)^{\frac{1}{2}}\leq 1. \end{align}\]

For the probability measure \(\tilde{\mu}_{\mathcal{G}}\) and \(F \in \mathcal{F}_1(\mathcal{H}_{\mathrm{para}};\mathbb{R}^d)\), we have the following lemma from Theorem 3.24 in [@korolev2022twolayer] for the approximation by shallow nets with operator-valued parameters.

We apply the above lemma with \(\mu=\tilde{\mu}_{\mathcal{G}}\). Then for \(h =(h_{\mathcal{F}},1)\), \(\mathcal{N}_n(h)\) can be further written by (17 ) into \[\begin{align} \mathcal{N}_{n}(h)&=\sum_{j=1}^{n}\alpha _{j} \sigma(W_{j}h)=\sum_{j=1}^{n}\alpha _{j}\sigma\left( \sum_{l=1}^{d}(e _{l} \otimes w_{j,l})h \right)\\&=\sum_{j=1}^{n}\alpha _{j}\sigma\left( \sum_{l=1}^{d} (\langle v _{j,l}, h_{\mathcal{F}} \rangle _{\mathcal{H}_{\mathcal{F}}} + b_{j,l})e _{l} \right) \\ &=\sum_{j=1}^{n} \alpha _{j} \sigma\left( \sum_{l=1} ^{d} \langle v_{j,l}, h_{\mathcal{F}} \rangle _{\mathcal{H}_{\mathcal{F}}}e _{l} + b_{j} \right) \end{align}\] where \(b_{j} = \sum_{l=1}^{d}b_{j,l}e _{l} \in \mathbb{R}^{d}, w_{j,l}=(v_{j,l}, b_{j,l})\) with \(v_{j,l} \in \mathcal{H}_{\mathcal{F}}\) and \(b_{j,l} \in \mathbb{R}\) such that \[\| W_{j} \|_{\mathrm{op}}=\sup_{\| h \|_{\mathcal{H}_{\mathrm{para}}}=1} \left( \sum_{l=1}^{d} \langle w_{j,l}, h \rangle _{\mathcal{H}_{\mathrm{para}}}^{2} \right)^{\frac{1}{2}} \leq 1.\] We also know that for \(h=(h_{\mathcal{F}},1)\) in the support of \(\tilde{\mu}_{\mathcal{G}}\), \(h_{\mathcal{F}}=K_{\boldsymbol{\lambda}}(\rho) \otimes k_{\boldsymbol{\lambda}}(x, \cdot)\) for some \((\rho,x) \in \Omega _{\mathcal{B}}\). It follows that \(\| h \|_{\mathcal{H}_{\mathrm{para}}} \leq \sqrt{ 1+C_{\mathcal{B}} }\) and \(\| W_{j} h \|_{2} \leq \sqrt{ 1+C_{\mathcal{B}}}\) for \(h \in \operatorname{supp}(\tilde{\mu}_{\mathcal{G}})\). Then we construct a double-width shallow neural network \(\mathcal{N}_{2n}\) as \[\begin{align} \mathcal{N}_{2n}(h)&= \sum_{j=1}^{n} \alpha _{j} \Big(\sigma(W_{j}h+\sqrt{ 1+C_{\mathcal{B}}} \mathbf{1}_{d})-\sigma(W_{j}h- \sqrt{ 1+C_{\mathcal{B}}}\mathbf{1}_{d})-\sqrt{ 1+C_{\mathcal{B}}}\mathbf{1}_{d}\Big) \\ &= \sum_{j=1}^{2n} \alpha' _{j} \sigma\left( W'_{j}h+ (-1)^{\left\lfloor \frac{j-1}{n} \right\rfloor}\sqrt{ 1+C_{\mathcal{B}}} \mathbf{1}_{d} \right) - \sum_{j=1}^{n} \alpha _{j}\sqrt{ 1+C_{\mathcal{B}}} \mathbf{1}_{d} \\ &= \sum_{j=1}^{2n} \alpha' _{j} \sigma\left( \sum_{l=1}^{d} \langle v'_{j,l}, h_{\mathcal{F}} \rangle _{\mathcal{H}_{\mathcal{F}}} e _{l} + b'_{j} \right) +b'_{0} \end{align}\] to realize the same approximant in Lemma 1 by adding additional bias vectors and letting \(\alpha _{j}'= -\alpha' _{j+n}=\alpha _{j}\), \(v'_{j,l}=v'_{j+n,l}=v_{j,l}\), \(b'_{j}=b_{j}+\sqrt{ 1+C_{\mathcal{B}}}\mathbf{1}_{d}\), \(b'_{j+n}= b_{j}- \sqrt{ 1+C_{\mathcal{B}}}\mathbf{1}_{d}\) for \(1 \leq j \leq n\), and \(b_{0}= - \sum_{j=1}^{n} \alpha _{j} \sqrt{ 1+ C_{\mathcal{B}}} \mathbf{1}_{d}\). In the following content, we still use \((\alpha _{j}, v_{j,l},b_{j},b_{0})\) as notations for parameters in \(\mathcal{N}_{2n}\) with no confusion.

5.1.1 Neural Network with Latent Polynomial Features↩︎

Recall that for \((\rho,x)\) sampled from the probability measure \(\nu_{\mathcal{G}}\) on \(\Omega _{\mathcal{B}}\), we take the feature \(\mathrm{I}_{\boldsymbol{\lambda}}(\rho ,x)=K_{\boldsymbol{\lambda}}(\rho) \otimes k_{\boldsymbol{\lambda}}(x,\cdot) \in \mathcal{H}_{\mathcal{F}}\) as the model input. Let \((\psi^{\boldsymbol{\lambda}}_{q})_{q \in \mathbb{N}}\) be the orthonormal basis of \(\mathcal{H}_{k_{\boldsymbol{\lambda}}}\) and \((r^{\boldsymbol{\lambda}}_q)_{q \in \mathbb{N}}\) the eigenvalue sequence as defined in Appendix 8.1. Then for each pair \((j,l)\), \(v_{j,l}\) can be written as \[\begin{align} v_{j,l}=\sum_{p,q \in\mathbb{N}} \sum_{1\leq s\leq d} a_{p,q,s}^{(j,l)}(\psi^{\boldsymbol{\lambda}}_{p} \otimes e _{s}) \otimes \psi^{\boldsymbol{\lambda}}_{q} \text{ with } \sum_{p,q \in\mathbb{N}} \sum_{1 \leq s \leq d} (a_{p,q,s}^{(j,l)})^{2} \leq 1 . \end{align}\] It follows that \[\begin{align} \langle v_{j,l},\mathrm{I}_{\boldsymbol{\lambda}}(\rho,x) \rangle _{\mathcal{H}_{\mathcal{F}}}&= \sum_{p,q \in\mathbb{N}} \sum_{1 \leq s\leq d}a_{p,q,s}^{(j,l)}\langle \psi^{\boldsymbol{\lambda}}_{p}\otimes e _{s} \otimes \psi^{\boldsymbol{\lambda}}_{q}, K_{\boldsymbol{\lambda}}(\rho) \otimes k_{\boldsymbol{\lambda}}(x,\cdot) \rangle _{\mathcal{H}_{\mathcal{F}}}\\ &=\sum_{p,q \in\mathbb{N}} \sum_{1 \leq s \leq d} a _{p,q,s}^{(j,l)}\psi^{\boldsymbol{\lambda}}_{q}(x)\int \psi^{\boldsymbol{\lambda}}_{p}(y) e _{s}^Ty \, d \rho(y). \end{align}\]

The basic idea for constructing a neural network with latent polynomial features is to estimate the truncation error for the query index \(q\) and the context memory index \(p\).

First we consider to estimate the truncation error on index \(q\). We make one step further by writing \[\langle v_{j,l}, \mathrm{I}_{\boldsymbol{\lambda}}(\rho,x) \rangle _{\mathcal{H}_{\mathcal{F}}} = \sum_{q \in\mathbb{N}}\left( \sum_{p \in\mathbb{N}} \sum_{1 \leq s \leq d} a_{p,q,s}^{(j,l)} \int \psi^{\boldsymbol{\lambda}}_{p}(y) e _{ s}^{T}y \, d \rho(y) \right)\psi^{\boldsymbol{\lambda}}_{q}(x)=: \sum_{q \in \mathbb{N}}b_{q}^{(j,l)}(\rho)\psi^{\boldsymbol{\lambda}}_{q}(x).\] Define \[\begin{align} A^{(j,l)}:l^{2}(\mathbb{N}\times[d]) \to l^{2}(\mathbb{N}) \text{ such that }(A^{(j,l)}z)_{q}=\sum_{p \in\mathbb{N}} \sum_{s \in[d]}a_{p,q,s}^{(j,l)}z_{p,s} \end{align}\] where \([d]:=\{ 1,\dots,d \}\) and \(q \in\mathbb{N}\). It is easy to see that \(A^{(j,l)}\) is a Hilbert-Schmidt operator with \(\| A^{(j,l)} \|_{\mathrm{HS}}^{2}=\sum _{p,q \in\mathbb{N},s \in[d]}(a_{p,q,s}^{(j,l)})^{2} \leq 1\). Also note that by dominated convergence theorem, \[\sum_{p \in\mathbb{N}} \sum_{s \in[d]}\left( \int \psi^{\boldsymbol{\lambda}}_{p}(y)e _{s}^{T}y \, d\rho (y) \right)^{2}\leq \int \sum_{p \in \mathbb{N}}(\psi^{\boldsymbol{\lambda}}_{p}(y))^{2} \| y \|^{2} _{2} \, d\rho(y)=\int k_{\boldsymbol{\lambda}}(y,y) \| y \|^{2} _{2} \, d \rho(y) \leq C_{\mathcal{B}},\] which shows that \(\int \psi^{\boldsymbol{\lambda}}(y) y \, d\rho(y):=\left( \int \psi^{\boldsymbol{\lambda}}_{p}(y)e _{s}^{T}y \, d\rho (y) \right)_{p \in \mathbb{N},s \in[d]} \in l^{2}(\mathbb{N} \times[d])\). It follows that \[\begin{align} C_{\mathcal{B}}^{\frac{1}{2}} &\geq \| A^{(j,l)} \|_{\mathrm{HS}} \left\| \int \psi^{\boldsymbol{\lambda}}(y)y\, d\rho(y) \right\|_{l^{2}(\mathbb{N} \times[d])} \\&\geq \left\| A^{(j,l)} \left( \int \psi^{\boldsymbol{\lambda}}(y)y\, d\rho(y) \right) \right\|_{l^{2}(\mathbb{N})}=\left( \sum_{q \in\mathbb{N}} (b_{q}^{(j,l)}(\rho))^{2} \right)^{\frac{1}{2}} \end{align}\] and \(\sum_{q \in \mathbb{N}} b_{q}^{(j,l)}(\rho)\psi^{\boldsymbol{\lambda}}_{q} \in\mathcal{H}_{k_{\boldsymbol{\lambda}}}\) for each \((j,l)\). Let \[\Psi _{2n,m_{1}}(\rho,x):= \sum_{j=1}^{2n}\alpha _{j}\sigma\left( \sum _{l=1}^{d}\sum_{q=1}^{m_{1}} b_{q}^{(j,l)}(\rho)\psi^{\boldsymbol{\lambda}}_{q}(x)e _{l} +b_{j} \right) +b_{0}.\] Then we have \[\begin{align} &\| \mathcal{N}_{2n}(\mathrm{I}_{\boldsymbol{\lambda}}(\cdot),1)-\Psi _{2n,m_{1}} \|^{2}_{L^{2}(\nu_{\mathcal{G}})}\notag\\&= \int _{\Omega _{\mathcal{B}}}\left\| \mathcal{N}_{2n}(\mathrm{I}_{\boldsymbol{\lambda}}(\rho,x),1)-\Psi _{2n,m_{1}}(\rho,x) \right\|^{2} _{2}\, d \nu_{\mathcal{G}}(\rho,x)\notag\\&\leq \int _{\Omega _{\mathcal{B}}} \left\| \sum_{j=1}^{2n} \left| \alpha _{j} \right| \sum_{l=1}^{d} \left| \sum_{q\geq m_{1}+1}b_{q}^{(j,l)}(\rho)\psi^{\boldsymbol{\lambda}}_{q}(x) \right| e _{l} \right\|^{2} _{2} \, d \nu_{\mathcal{G}}(\rho,x) \notag\\&= \int _{\Omega _{\mathcal{B}}} \sum_{l=1}^{d} \left( \sum_{j=1}^{2n}\left| \alpha _{j} \right|\left| \sum_{q\geq m_{1}+1}b_{q}^{(j,l)}(\rho)\psi^{\boldsymbol{\lambda}}_{q}(x) \right| \right)^{2} \, d\nu_{\mathcal{G}}(\rho,x) \notag\\ & \leq \int _{\Omega _{\mathcal{B}}} \sum_{l=1}^{d} \| \alpha \|_{1} \left[ \sum_{j=1}^{2n} \left| \alpha _{j} \right|\left( \sum_{q\geq m_{1}+1} b_{q}^{(j,l)}(\rho) \psi^{\boldsymbol{\lambda}}_{q}(x) \right)^{2} \right] d\nu_{\mathcal{G}}(\rho,x) \notag\\ &= \int _{\mathcal{B}_{2,b}(\mathcal{X})} \| \alpha \|_{1} \sum_{l=1}^{d} \left[ \sum_{j=1}^{2n} \left| \alpha _{j} \right| \int _{\mathcal{X}} \left( \sum_{q \geq m_{1}+1} b_{q}^{(j,l)}(\rho) \psi^{\boldsymbol{\lambda}}_{q}(x) \right)^{2} \, d \rho(x) \right] \, d\mathcal{P_{G}^{X}}(\rho) \notag\\ & \leq \int _{\mathcal{B}_{2,b}(\mathcal{X})} \| \alpha \|_{1}^{2} \sum_{l=1}^{d} \left[ \max_{1 \leq j\leq 2n} \int _{\mathcal{X}} \left( \sum_{q \geq m_{1}+1} b_{q}^{(j,l)}(\rho) \psi^{\boldsymbol{\lambda}}_{q}(x) \right)^{2} \, d \rho(x) \right]\, d \mathcal{P_{G}^{X}}(\rho) \notag\\ &=: \int _{\mathcal{B}_{2,b}(\mathcal{X})} \| \alpha \|_{1}^{2} \sum_{l=1}^{d} \Big(\max_{1\leq j\leq 2n} \mathcal{E}_{j,l}(\rho)\Big) \, d\mathcal{P_{G}^{X}}(\rho). \label{place1} \end{align}\tag{18}\] If \(1< \gamma<\infty\), for each pair \((j,l) \in \{ 1,\dots,n \}\times \{ 1,\dots,d \}\), we obtain that \[\begin{align} \mathcal{E}_{j,l}(\rho)&= \int _{\mathcal{X}} \left( \sum_{q \geq m_{1}+1} b_{q}^{(j,l)}(\rho)\psi^{\boldsymbol{\lambda}}_{q}(x) \right)^{2} \, d \rho(x) \\&=\int _{\mathcal{X}} \left( \sum_{q \geq m_{1}+1} b_{q}^{(j,l)}(\rho)\psi^{\boldsymbol{\lambda}}_{q}(x) \right)^{2} (\omega _{\kappa}(\rho)(x)) d\rho _{\kappa}(x) \\ &\leq \| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} \left[ \int _{\mathcal{X}} \left( \sum_{q \geq m_{1}+1} b_{q}^{(j,l)}(\rho)\psi^{\boldsymbol{\lambda}}_{q}(x) \right)^{\frac{2\gamma}{\gamma-1}} \, d \rho _{\kappa}(x) \right]^{\frac{\gamma-1}{\gamma}} \\ & \leq \| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} \left[ \int _{\mathcal{X}} \left( \sum_{q\geq m_{1}+1} b_{q}^{(j,l)}(\rho) \psi^{\boldsymbol{\lambda}}_{q}(x) \right)^{2} \, d\rho _{\kappa}(x) \right]^{\frac{\gamma-1}{\gamma}} \left\| \sum_{q\geq m_{1}+1} b_{q}^{(j,l)}(\rho)\psi^{\boldsymbol{\lambda}}_{q} \right\|_{\infty}^{\frac{2}{\gamma}} \end{align}\] \[\begin{align} & \leq \| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} \left\| \sum_{q \geq m_{1}+1} b_{q}^{(j,l)}(\rho) \psi^{\boldsymbol{\lambda}}_{q} \right\|_{L^{2}(\rho _{\kappa})}^{\frac{2(\gamma-1)}{\gamma}} \left\| \sum_{q \geq m_{1}+1} b_{q}^{(j,l)}(\rho)\psi^{\boldsymbol{\lambda}}_{q} \right\|_{\mathcal{H}_{k_{\boldsymbol{\lambda}}}} ^{\frac{2}{\gamma}} \\ & = \| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} \left\| \sum_{q \geq m_{1}+1} b_{q}^{(j,l)}(\rho) \psi^{\boldsymbol{\lambda}}_{q} \right\|_{L^{2}(\rho _{\kappa})} ^{\frac{2(\gamma-1)}{\gamma}} \left( \sum_{q \geq m_{1}+1} (b_{q}^{(j,l)}(\rho))^{2} \right)^{\frac{1}{\gamma}}. \end{align}\] Insert the above estimation back into (18 ). It can be derived by the approximation result in Appendix 8.1 that \[\begin{align} &\left\| \mathcal{N}_{2n} (\mathrm{I}_{\boldsymbol{\lambda}}(\cdot),1) - \Psi _{2n,m_{1}} \right\|^{2} _{L^{2}(\nu_{\mathcal{G}})} \\ \leq & \| \alpha \|_{1}^{2} \int _{\mathcal{B}_{2,b}(\mathcal{X})} \| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} \sum_{l=1}^{d} \left[ \max_{1 \leq j \leq 2n} \left\| \sum_{q \geq m_{1}+1} b_{q}^{(j,l)}(\rho) \psi^{\boldsymbol{\lambda}}_{q} \right\|_{L^{2}(\rho _{\kappa})} ^{\frac{2(\gamma-1)}{\gamma}} \left( \sum_{q \geq m_{1}+1} (b_{q}^{(j,l)}(\rho))^{2} \right)^{\frac{1}{\gamma}} \right]\, d \mathcal{P_{G}^{X}}(\rho) \\ \leq & 4C_{F}^{2} \int _{\mathcal{B}_{2,b}(\mathcal{X})} \| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} \sum_{l=1}^{d} \left[ \max_{1 \leq j \leq 2n} \left( \left( \sum_{q \in \mathbb{N}} (b_{q}^{(j,l)}(\rho))^{2} \right)^{\frac{1}{2}}C_{\kappa,\xi}m_{1}^{-\xi} \right)^{\frac{2(\gamma-1)}{\gamma}} \left( \sum_{q \in \mathbb{N}} (b_{q}^{(j,l)}(\rho))^{2} \right)^{\frac{1}{\gamma}} \right]\, d \mathcal{P_{G}^{X}}(\rho) \\=& 4C_{F}^{2} \int _{\mathcal{B}_{2,b}(\mathcal{X})} \| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} \sum_{l=1}^{d} \left[ \max_{1\leq j \leq 2n} \left( \sum_{q \in\mathbb{N}} (b_{q}^{(j,l)}(\rho)) ^{2} \right) \right]C_{\kappa,\xi,\gamma} m_{1} ^{-\xi \cdot\frac{ 2(\gamma-1)}{\gamma}} \, d\mathcal{P_{G}^{X}}(\rho) \\ \leq & 4C_{F}^{2} \int _{\mathcal{B}_{2,b}(\mathcal{X})} \| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} d C_{\mathcal{B}}C_{\kappa,\xi,\gamma} m_{1}^{-\xi \cdot \frac{2(\gamma-1)}{\gamma}} \, d\mathcal{P_{G}^{X}}(\rho) \leq C_{1} m_{1} ^{- \xi \cdot \frac{2(\gamma-1)}{\gamma}} \end{align}\] where \(C_{F}=\| F \|_{\mathcal{F}_{1}}\) and \(C_{1}= 4dC_{F}^{2}C_{\mathcal{B}}C_{\kappa,\xi,\gamma}C_{\mathcal{G}}^{\frac{1}{2}}\).

For \(\gamma=\infty\), it’s easy to obtain that \[\mathcal{E}_{j,l}(\rho)\leq \| \omega _{\kappa}(\rho)\|_{L^{\infty}(\rho _{\kappa})} \| \sum_{q \geq m_{1}+1} b_{q}^{(j,l)}(\rho) \psi^{\boldsymbol{\lambda}}_{q}\|_{L^{2}(\rho _{\kappa})}^{2}\] and then \[\| \mathcal{N}_{2n} -\Psi _{2n,m_{1}} \|_{L^{2}(\pi)}^{2} \leq C_{1}m_{1}^{-2\xi}.\]

Next we perform a truncation on the index \(p\): we let \[\Psi _{2n,m_{1},m_{2}}(\rho,x):= \sum_{j=1}^{2n}\alpha _{j}\sigma\left( \sum _{l=1}^{d}\sum_{q=1}^{m_{1}}\sum_{p=1}^{m_{2}}\sum_{s=1}^{d} a _{p,q,s}^{(j,l)}\psi^{\boldsymbol{\lambda}}_{q}(x)\int \psi^{\boldsymbol{\lambda}}_{p}(y) (e _{l}e _{s}^T)yd\rho(y) +b_{j} \right)+b_{0}.\] and \(a_{p,s}^{(j,l)}(x):= \sum_{q=1}^{m_{1}}a_{p,q,s}^{(j,l)}\psi^{\boldsymbol{\lambda}}_{q}(x)\). Then we have

\[\begin{align} & \left\| \Psi _{2n,m_{1}} - \Psi _{2n,m_{1}m_{2}} \right\|_{L^{2}(\nu_{\mathcal{G}})}^{2} = \int _{\Omega _{\mathcal{B}}} \| \Psi _{2n,m_{1}}(\rho,x)-\Psi _{2n,m_{1},m_{2}}(\rho,x) \|_{2}^{2} \, d \nu_{\mathcal{G}}(\rho,x) \notag \\ \leq & \int _{\Omega _{\mathcal{B}}} \left\| \sum_{j=1}^{2n} \left| \alpha _{j} \right| \sum_{l=1}^{d} \left| \sum_{q=1}^{m_{1}} \sum_{p\geq m_{2}+1} \sum_{s=1}^{d} a_{p,q,s}^{(j,l)}\psi^{\boldsymbol{\lambda}}_{q}(x)\int \psi^{\boldsymbol{\lambda}}_{p}(y) e _{s}^{T}y \, d\rho(y) \right|e _{l} \right\|_{2}^{2} \, d \nu_{\mathcal{G}}(\rho ,x)\notag \\ =& \int _{\Omega _{\mathcal{B}}} \sum_{l=1}^{d} \left( \sum_{j=1}^{2n} \left| \alpha _{j} \right| \left| \sum_{q=1}^{m_{1}} \sum_{p\geq m_{2}+1} \sum_{s=1}^{d} a_{p,q,s}^{(j,l)}\psi^{\boldsymbol{\lambda}}_{q}(x)\int \psi^{\boldsymbol{\lambda}}_{p}(y) e _{s}^{T}y \, d\rho(y) \right| \right)^{2} \, d \nu_{\mathcal{G}}(\rho ,x) \notag \\=: & \int _{\Omega _{\mathcal{B}}} \sum_{l=1}^{d} \left( \sum_{j=1}^{2n} \left| \alpha _{j} \right| \left| \sum_{p\geq m_{2}+1} \sum_{s=1}^{d} a_{p,s}^{(j,l)}(x)\int \psi^{\boldsymbol{\lambda}}_{p}(y) e _{s}^{T}y \, d\rho(y) \right| \right)^{2} \, d \nu_{\mathcal{G}}(\rho ,x) \, \notag \\ \leq & \int _{\Omega _{\mathcal{B}}} \| \alpha \|_{1} \sum_{l=1}^{d} \sum_{j=1}^{2n} \left| \alpha _{j} \right| \left( \sum_{p\geq m_{2}+1} \sum_{s=1}^{d} a_{p,s}^{(j,l)}(x)\int \psi^{\boldsymbol{\lambda}}_{p}(y) e _{s}^{T}y \, d\rho(y) \right)^{2} \, d\nu_{\mathcal{G}}(\rho,x) \notag \\ =: & \int _{\Omega _{\mathcal{B}}} \| \alpha \|_{1} \sum_{l=1}^{d} \sum_{j=1}^{2n} \left| \alpha _{j} \right| \mathcal{E}'_{j,l}(\rho,x) \, d\nu_{\mathcal{G}}(\rho,x) . \label{place2} \end{align}\tag{19}\] Similarly, by dominated convergence theorem and the integral shift to the gaussian distribution \(\rho _{\kappa}\), we obtain \[\begin{align} \mathcal{E}_{j,l}'(\rho,x)&=\left( \int \sum_{s=1}^{d} (e _{s}^{T}y) \left( \sum_{p\geq m_{2}+1} a_{p,s}^{(j,l)}(x) \psi^{\boldsymbol{\lambda}}_{p}(y) \right) \, d \rho(y) \right)^{2} \\ & = \left( \int \sum_{s=1}^{d} (e _{s}^{T}y) {a}_{s}^{(j,l)}(x,y)\, d\rho(y) \right)^{2} \leq \left( \int \|y\|_{2} \left( \sum_{s=1}^{d} {a}_{s}^{(j,l)}(x,y)^{2}\right)^{\frac{1}{2}} \, d \rho(y) \right)^{2} \\& \leq \mathbb{E}_{\rho}\|Y\|_{2}^{2} \int \sum_{s=1}^{d} {a}_{s}^{(j,l)}(x,y)^{2} \, d\rho(y) \leq C_{\mathcal{B}}\sum_{s=1}^{d}\int {a}_{s}^{(j,l)}(x,y)^{2} \omega _{\kappa}(\rho)(y)\, d\rho _{\kappa}(y) \\&\leq C_{\mathcal{B}}\| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} \sum_{s=1}^{d} \left[ \int \big({a}_{s}^{(j,l)}(x,y)\big)^{\frac{2\gamma}{\gamma-1}} \, d\rho _{\kappa}(y) \right]^{\frac{{\gamma-1}}{\gamma}} \\& \leq C_{\mathcal{B}}\|\omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} \sum_{s=1}^{d} \underbrace{ \|{a}_{s}^{(j,l)}(x,\cdot)\|_{L^{2}(\rho _{\kappa})}^{\frac{{2(\gamma-1)}}{\gamma}} }_{\mathrm{I}_{1}^{(j,l,s)}(x)} \underbrace{ \|{a}_{s}^{(j,l)}(x,\cdot)\|_{\infty}^{\frac{2}{\gamma}} }_{ \mathrm{I}_{2}^{(j,l,s)}(x) } \end{align}\] Then (19 ) can be further bounded by \[\begin{align} &C_{\mathcal{B}}\int _{\mathcal{B}_{2,b}(\mathcal{X})} \|\alpha\|_{1} \|\omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} \sum_{j=1}^{2n} \left| \alpha _{j} \right| \sum_{s,l=1}^{d}\left( \int _{\mathcal{X}} \mathrm{I}_{1}^{(j,l,s)}(x)\mathrm{I}_{2}^{(j,l,s)}(x) \, d \rho(x) \right) \, \, d\mathcal{P_{G}^{X}}(\rho)\\ \leq &\, C_{\mathcal{B}}\int _{\mathcal{B}_{2,b}(\mathcal{X})} \|\alpha\|_{1}^{2}\|\omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} \max_{1\leq j\leq 2n}\sum_{s,l=1}^{d}\left( \int _{\mathcal{X}} \mathrm{I}_{1}^{(j,l,s)}(x)\mathrm{I}_{2}^{(j,l,s)}(x) \, d \rho(x) \right) \, d\mathcal{P_{G}^{X}}(\rho)=:\Delta_{0} \end{align}\] where the integral of \(\mathrm{I}_{1}^{(j,l,s)}(x)\mathrm{I}_{2}^{(j,l,s)}(x)\) with respect to \(\rho\) can be bounded by \[\int_{\mathcal{X}} \mathrm{I}_{1}^{(j,l,s)}(x) \mathrm{I}_{2}^{(j,l,s)}(x) \, d \rho(x) \leq \left\| \mathrm{I}_{1}^{(j,l,s)} \right\|_{L^{\frac{\gamma}{\gamma-1}}(\rho)} \left\| \mathrm{I}_{2}^{(j,l,s)} \right\|_{L^{\gamma}(\rho)}.\] For the first term \(\mathrm{I}_{1}^{(j,l,s)}\), \[\begin{align} \left\| \mathrm{I}_{1}^{(j,l,s)} \right\|_{L^{\frac{\gamma}{\gamma-1}}(\rho)}& = \left( \int_{\mathcal{X}} \left\| {a}_{s}^{(j,l)}(x,\cdot)\right\|_{L^{2}(\rho _{\kappa})}^{2} \, d\rho(x) \right)^{\frac{{\gamma-1}}{\gamma}} \\ &= \left( \int \int \left( \sum_{p\geq m_{2}+1}a_{p,s}^{(j,l)}(x) \psi^{\boldsymbol{\lambda}}_{p}(y) \right)^{2} \, d\rho _{\kappa}(y) \, d \rho(x) \right)^{\frac{{\gamma-1}}{\gamma}} \\ & = \left( \int \int \sum_{p\geq m_{2}+1} (a_{p,s}^{(j,l)}(x))^{2} (\psi^{\boldsymbol{\lambda}}_{p}(y))^{2} \, d\rho _{\kappa}(y) \, d\rho(x) \right)^{\frac{{\gamma-1}}{\gamma}} \\ &= \left( \int \sum_{p \geq m_{2}+1}\left( \int ( a_{p,s}^{(j,l)}(x))^{2} \, d \rho(x) \right) (\psi^{\boldsymbol{\lambda}}_{p}(y) )^{2}\, d\rho _{\kappa}(y) \right)^{\frac{{\gamma-1}}{\gamma}} \\ &= \left\| \sum_{p \geq m_{2}+1} \left\| a_{p,s}^{(j,l)} \right\|_{L^{2}(\rho)} \psi^{\boldsymbol{\lambda}}_{p} \right\|_{L^{2}(\rho _{\kappa})}^{\frac{2(\gamma-1)}{\gamma}} . \end{align}\]

Perform the domain shift to each coefficient of \(\psi^{\boldsymbol{\lambda}}_{p}\) again and we can obtain \[\begin{align} \left\| a_{p,s}^{(j,l)} \right\|_{L^{2}(\rho)} &= \int \left( \sum_{q=1}^{m_{1}}a_{p,q,s}^{(j,l)}\psi^{\boldsymbol{\lambda}}_{q}(x) \right)^{2} \omega _{\kappa}(\rho)(x) \, d\rho _{\kappa}(x) \\ & \leq \| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} \left\| \sum_{q=1}^{m_{1}}a_{p,q,s}^{(j,l)}\psi^{\boldsymbol{\lambda}}_{q} \right\|_{L^{2}(\rho _{\kappa})}^{\frac{2(\gamma-1)}{\gamma}} \left\| \sum_{q=1}^{m_{1}}a_{p,q,s}^{(j,l)}\psi^{\boldsymbol{\lambda}}_{q}\right\|_{\mathcal{H}_{k_{\boldsymbol{\lambda}}}}^{\frac{2}{\gamma}} \\ &= \| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} \left( \sum_{q=1}^{m_{1}} (a_{p,q,s}^{(j,l)})^{2}r^{\boldsymbol{\lambda}}_{q} \right)^{\frac{\gamma-1}{\gamma}} \left( \sum_{q=1}^{m_{1}} (a_{p,q,s}^{(j,l)})^{2} \right)^{\frac{1}{\gamma}} \\ &\leq \| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} (r^{\boldsymbol{\lambda}}_{1})^{\frac{\gamma-1}{\gamma}} \sum_{q=1}^{m_{1}} (a_{p,q,s}^{(j,l)})^{2} , \end{align}\] which implies that \(\sum_{p\geq m_{2}+1} \left\| a_{p,s}^{(j,l)} \right\|_{L^{2}(\rho)} \psi^{\boldsymbol{\lambda}}_{p} \in \mathcal{H}_{k_{\boldsymbol{\lambda}}}\) with the RKHS norm \[\left( \sum_{p\geq m_{2}+1} \left\| a_{p,s}^{(j,l)} \right\|_{L^{2}(\rho)}^{2} \right)^{\frac{1}{2}} \leq\left( \|\omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})}(r^{\boldsymbol{\lambda}}_{1})^{\frac{{\gamma-1}}{\gamma}} \sum_{p\geq m_{2}+1} \sum_{q=1}^{m_{1}} (a_{p,q,s}^{(j,l)})^{2} \right)^{\frac{1}{2}}.\]

For the second term \(\mathrm{I}_{2}^{(j,l,s)}\), \[\begin{align} \left\| \mathrm{I}_{2}^{(j,l,s)} \right\|_{L^{\gamma}(\rho)}&= \left( \int \left\| a_{\boldsymbol{\lambda}}^{(j,l,s)}(x, \cdot) \right\|_{\infty} ^{2} \, d \rho(x) \right)^{\frac{1}{\gamma}} \leq \left( \int \left\| a_{\boldsymbol{\lambda}}^{(j,l,s)}(x, \cdot) \right\|_{\mathcal{H}_{k_{\boldsymbol{\lambda}}}}^{2} \, d \rho(x) \right)^{\frac{1}{\gamma}} \\ & \leq \left( \int \left\| \sum_{p\geq m_{2}+1} a_{p,s}^{(j,l)}(x) \psi^{\boldsymbol{\lambda}}_{p} \right\|_{\mathcal{H}_{k_{\boldsymbol{\lambda}}}}^{2} \, d\rho(x) \right)^{\frac{1}{\gamma}}= \left( \int \sum_{p\geq m_{2}+1}(a_{p,s}^{(j,l)}(x))^{2} \, d\rho(x) \right)^{\frac{1}{\gamma}} \\ & \leq \left( \int \sum_{p\geq m_{2}+1}\left( \sum_{q=1}^{m_{1}} a_{p,q,s}^{(j,l)}\psi^{\boldsymbol{\lambda}}_{q}(x) \right)^{2} \, d\rho(x) \right)^{\frac{1}{\gamma}} \\ & \leq \left( \int \left( \sum _{p \geq m_{2}+1}\sum_{q=1}^{m_{1}}(a_{p,q,s}^{(j,l)})^{2} \right)\left( \sum_{q=1}^{m_{1}} \psi^{\boldsymbol{\lambda}}_{q}(x)^{2} \right) \, d \rho(x) \right)^{\frac{1}{\gamma}} \\& \leq \left( \sum _{p \geq m_{2}+1}\sum_{q=1}^{m_{1}}(a_{p,q,s}^{(j,l)})^{2} \right)^{\frac{1}{\gamma}} \left( \int \sum_{q=1}^{\infty} \psi^{\boldsymbol{\lambda}}_{q}(x)^{2} \, d\rho(x) \right)^{\frac{1}{\gamma}} \\ & = \left( \sum _{p \geq m_{2}+1}\sum_{q=1}^{m_{1}}(a_{p,q,s}^{(j,l)})^{2} \right)^{\frac{1}{\gamma}}. \end{align}\] Combine the estimations for \(\mathrm{I}_{1}^{(j,l,s)}\) and \(\mathrm{I}_{2}^{(j,l,s)}\) and we get an upper bound that

\[\begin{align} \Delta _{0} &\leq 4C_{\mathcal{B}}C_{F}^{2}\int _{\mathcal{B}_{2,b}(\mathcal{X})} \| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} \left( \max_{1 \leq j \leq 2n} \sum_{s,l =1}^{d}\left\| \mathrm{I}_{1}^{(j,l)} \right\|_{L^{\frac{\gamma}{\gamma-1}}(\rho)} \left\| \mathrm{I}_{2}^{(j,l)} \right\|_{L^{\gamma}(\rho)} \right) \, d\mathcal{P_{G}^{X}}(\rho) \\ \leq 4C_{\mathcal{B}}C_{F}^{2} & \int _{\mathcal{B}_{2,b}(\mathcal{X})} \| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} \Biggl\{\max_{1 \leq j \leq 2n} \sum_{s,l =1}^{d} \left[ \left( \| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} (r^{\boldsymbol{\lambda}}_{1})^{\frac{\gamma-1}{\gamma}} \sum_{p \in \mathbb{N}} \sum_{ q=1}^{m_1} (a_{p,q,s}^{(j,l)})^{2} \right)^{\frac{1}{2}}C_{\kappa,\xi}m_{2}^{-\xi} \right]^{\frac{2(\gamma-1)}{\gamma}} \\& \quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \cdot \left( \sum_{p \in\mathbb{N}} \sum_{q=1}^{m_1} (a_{p,q,s}^{(j,l)})^{2} \right)^{\frac{1}{\gamma}} \Biggr\} \, d \mathcal{P_{G}^{X}}(\rho) \\ & \leq 4dC_{\mathcal{B}} C_{F}^{2} (r^{\boldsymbol{\lambda}}_{1})^{\frac{(\gamma-1)^{2}}{\gamma^{2}}} \int _{\mathcal{B}_{2,b}(\mathcal{X})} \| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} ^{\frac{2\gamma-1}{\gamma}} C_{\kappa,\xi,\gamma} m_{2} ^{-\xi \cdot \frac{2(\gamma-1)}{\gamma}} \, d \mathcal{P_{G}^{X}}(\rho) \end{align}\] \[\begin{align} & \leq 4dC_{\mathcal{B}}C_{F}^{2}C_{\kappa,\xi,\gamma}(r^{\boldsymbol{\lambda}}_{1})^{\frac{(\gamma-1)^{2}}{\gamma^{2}}} m_{2}^{-\xi \cdot \frac{2(\gamma-1)}{\gamma}} \int _{\mathcal{B}_{2,b}(\mathcal{X})} \| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})}^{ \frac{2\gamma-1}{\gamma}} \, d \mathcal{P_{G}^{X}}(\rho) \\ & \leq C_{2}m_{2}^{- \xi \cdot \frac{2(\gamma-1)}{\gamma}} \end{align}\] where \(C_{2}=4d C_{\mathcal{B}}C_{F}^{2}C_{\kappa,\xi,\gamma}(r^{\boldsymbol{\lambda}}_{1})^{\frac{(\gamma-1)^{2}}{\gamma^{2}}}C_{\mathcal{G}}^{\frac{2\gamma-1}{2\gamma}}\).

5.1.2 Linear Transformer with Adaptive Attention Heads↩︎

Recall that \[\begin{align} \Psi _{2n,m}(\rho,x)&:= \sum_{j =1}^{2n}\alpha _{j}\sigma\left( \sum _{l =1}^{d}\sum_{p,q=1}^{m}\sum_{s=1}^{d} a _{p,q,s}^{(j,l)}\psi^{\boldsymbol{\lambda}}_{q}(x)\int \psi^{\boldsymbol{\lambda}}_{p}(y) (e _{l}e _{s}^T)yd\rho(y) +b_{j} \right)+b_{0} \\&= \sum_{j=1 }^{2n} \alpha _{j} \sigma \left( \sum_{p,q=1}^{m} \psi^{\boldsymbol{\lambda}}_{q}(x) \int \psi^{\boldsymbol{\lambda}}_{p}(y) A_{p,q}^{(j)}y \, d \rho(y) +b_{j} \right)+b_{0} \end{align}\] with \(A_{p,q}^{(j)}= \sum_{l=1}^{d}\sum_{s=1}^{d} a_{p,q,s}^{(j,l)}e _{l}e _{s}^{T}=[a_{p,q,s}^{(j,l)}]_{1\leq l \leq d,1 \leq s \leq d}\).

Now we approximate each \(\psi^{\boldsymbol{\lambda}}_{q}\) with a neural network \(\phi _{q}\), and let \[\begin{align} \mathrm{T}_{2n,m}(\rho,x):= \sum_{j=1}^{2n}\alpha _{j} \sigma\left( \sum_{q =1}^{m} \phi _{q}(x) \left( \sum_{p=1}^{m} \int \phi _{p}(y) A_{p,q}^{(j)}y \, d \rho(y) \right) +b_{j} \right)+b_{0}. \end{align}\]

Then we have the error decomposition: \[\left\| \Psi _{2n,m} - \mathrm{T}_{2n,m} \right\|_{L^{2}(\nu_{\mathcal{G}})} \leq \| \Psi _{2n,m}- \widetilde{\mathrm{T}}_{2n,m} \|_{L^{2}(\nu_{\mathcal{G}})} + \| \widetilde{\mathrm{T}}_{2n,m} - \mathrm{T}_{2n,m} \|_{L^{2}(\nu_{\mathcal{G}})}\] where \[\widetilde{\mathrm{T}}_{2n,m}(\rho,x)= \sum_{j=1}^{2n} \alpha _{j} \sigma\left( \sum_{q=1}^{m} \phi _{q}(x) \left( \sum_{p=1}^{m} \int \psi^{\boldsymbol{\lambda}}_{p}(y) A_{p,q}^{(j)}y \, d \rho(y) \right) +b_{j}\right)+b_{0}.\]

Similar with error estimations for the truncated error, let \[\widetilde{b}_{q}^{(j,l)}(\rho):= \sum_{1\leq p \leq m,1\leq s \leq d} a_{p,q,s}^{(j,l)}\int \psi^{\boldsymbol{\lambda}}_{p}(y) e _{s}^{T}y \, d \rho(y)\] and we have \[\begin{align} &\left\| \Psi _{2n,m}- \widetilde{\mathrm{T}}_{2n,m} \right\|_{L^{2}(\nu_{\mathcal{G}})}^{2} \\ & \leq \int _{\Omega _{\mathcal{B}}} \left\| \sum_{j =1}^{2n} |\alpha _{j}| \sum_{l=1}^{d} \left| \sum_{q =1}^{m} \widetilde{b}_{q}^{(j,l)}(\rho)\big(\psi^{\boldsymbol{\lambda}}_{q}(x)-\phi _{q}(x)\big) \right| e _{l} \right\|_{2}^{2} \, d \nu_{\mathcal{G}}(\rho,x) \\ & = \int _{\Omega _{\mathcal{B}}} \sum_{l =1}^{d}\left( \sum_{j=1}^{2n} \left| \alpha _{j} \right| \left| \sum_{q =1}^{m} \widetilde{b}_{q}^{(j,l)}(\rho)\big(\psi^{\boldsymbol{\lambda}}_{q}(x)-\phi _{q}(x)\big)\right| \right)^{2} \, d \nu_{\mathcal{G}}(\rho,x) \\ & \leq \int _{\mathcal{B}_{2,b}(\mathcal{X})} \| \alpha \|_{1} \sum_{l=1}^{d} \sum_{j=1}^{2n} \left| \alpha _{j} \right| \int_{\mathcal{X}} \left( \sum_{q \in[m]}\widetilde{b}_{q}^{(j,l)}(\rho)\big(\psi^{\boldsymbol{\lambda}}_{q}(x)-\phi _{q}(x)\big) \right)^{2} \, d \rho(x) d \mathcal{P_{G}^{X}}(\rho) \\ & \leq \int _{\mathcal{B}_{2,b}(\mathcal{X})} \| \alpha \|_{1}^{2} \sum_{l=1}^{d} \max_{1\leq j \leq 2n} \left( \sum_{q=1}^{m}(\widetilde{b}_{q}^{(j,l)}(\rho))^{2} \right) \int_{\mathcal{X}} \sum_{q=1}^{m} \big( \psi^{\boldsymbol{\lambda}}_{q}(x)-\phi _{q}(x) \big)^{2}\, d \rho(x) d \mathcal{P_{G}^{X}}(\rho) \\ & \leq d \| \alpha \|_{1}^{2} C_{\mathcal{B}} \int _{\mathcal{B}_{2,b}(\mathcal{X})} \sum_{q=1}^{m}\int_{\mathcal{X}} \big( \psi^{\boldsymbol{\lambda}}_{q}(x)-\phi _{q}(x) \big)^{2}\, \, d \rho(x) \, d \mathcal{P_{G}^{X}}(\rho) \\ &=: dC_{\mathcal{B}} \| \alpha \|_{1}^{2} \sum_{q=1}^{m}\int _{\mathcal{B}_{2,b}(\mathcal{X})} \mathcal{\widetilde{E}}_{q}(\rho) \, d \mathcal{P_{G}^{X}}(\rho). \end{align}\] Take \(\phi _{q}= \phi_{q,\tilde{m}}\) to be the two-hidden-layer tanh neural network with a product gate in Appendix 8.2. Then we have \[\widetilde{\mathcal{E}}_{q}(\rho) \leq (4d^{2}+C_{\kappa,\gamma}\| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} ) \exp (-2\tilde{m}\log \tilde{m}).\] Take the estimation back and it follows that \[\left\| \Psi _{2n,m} - \widetilde{\mathrm{T}}_{2n,m,\tilde{m}} \right\|_{L^{2}(\nu_{\mathcal{G}})}^{2} \leq C_{3}m \exp(-2\tilde{m}\log\tilde{m})\]with \(C_{3}=4dC_{\mathcal{B}}C_{F}^{2}\left( 4d^{2}+C_{\kappa,\gamma}C_{\mathcal{G}}^{\frac{1}{2}} \right)\) for \(\tilde{m}> C_{\kappa,\theta,\gamma}\).

Then we use the same group of two-hidden-layer neural networks \(\{ \phi _{q,\tilde{m}} \}_{1\leq q \le m}\) to approximate \(\{ \psi^{\boldsymbol{\lambda}}_{q} \}_{1\leq q\leq m}\) in the context memory part. Now Let a linear Transformer \[\mathrm{T}_{2n,m,\tilde{m}}(\rho,x)=\sum_{j=1}^{2n} \alpha _{j} \sigma\left( \sum_{q=1}^{m} \phi _{q, \tilde{m}}(x) \left( \sum_{p=1}^{m}\int \phi _{p,\tilde{m}}(y)A_{p,q}^{(j)}y \, d \rho(y) \right)+b_{j} \right)+b_{0}.\] Then the approximation error for context functions can be measured as \[\begin{align} & \, \, \, \, \, \, \, \, \, \, \, \, \left\| \widetilde{\mathrm{T}}_{2n,m,\tilde{m}}- \mathrm{T}_{2n,m,\tilde{m}} \right\|_{L^{2}(\nu_{\mathcal{G}})}^{2} \\ &\leq \int _{\mathcal{B}_{2,b}(\mathcal{X})} \| \alpha \|_{1}^{2} \sum_{l=1}^{d} \max_{1\leq j\leq 2n} \int_{\mathcal{X}} \left( \sum_{1 \leq p,q \leq m,1 \leq s \leq d} a_{p,q,s}^{(j,l)} \phi _{q,\tilde{m}}(x) \int (\psi^{\boldsymbol{\lambda}}_{p}(y)-\phi _{p,\tilde{m}}(y)) e _{s}^{T}y \, d \rho(y) \right)^{2} \, d\rho(x)d\mathcal{P_{G}^{X}}(\rho) \\ &\leq \int _{\mathcal{B}_{2,b}(\mathcal{X})}\| \alpha \|_{1}^{2} \sum_{l=1}^{d} \max_{1\leq j \leq 2n}\left( \int_{\mathcal{X}} \sum_{1 \leq p \leq m, 1 \leq s \leq d} (\tilde{a}_{p,s}^{(j,l)}(x))^{2} d\rho(x) \right) \cdot\\& \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \, \,\, \, \left( \sum_{1\leq p \leq m, 1\leq s \leq d} \left( \int (\psi^{\boldsymbol{\lambda}}_{p}(y)-\phi _{p, \tilde{m}}(y))e _{s}^{T}y\, d \rho(y) \right)^{2} \right) \, d \mathcal{P_{G}^{X}}(\rho)\, \end{align}\] where \[\tilde{a}_{p,s}^{(j,l)}(x):= \sum_{q=1}^{m} a_{p,q,s}^{(j,l)}\phi _{q,\tilde{m}}(x).\]

For the first factor, let \[\mathrm{I}^{(j,l)}_{3}(\rho)= \int _{\mathcal{X}} \sum_{1\leq p\leq m,1\leq s\leq d} (\tilde{a}_{p,s}^{(j,l)}(x))^{2} \, d \rho(x),\] and we can obtain \[\begin{align} \sum_{l =1} ^{d} \max_{1\leq j \leq 2n} \mathrm{I}^{(j,l)} _{3}(\rho) &\leq d \sum_{q =1}^{m}\int_{\mathcal{X}} (\phi _{q,\tilde{m}}(x) )^{2}\, d \rho(x) \leq d\sum_{q =1}^{m} (2\| \psi^{\boldsymbol{\lambda}}_{q} \|_{L^{2}(\rho)}^{2} + 2\| \psi^{\boldsymbol{\lambda}}_{q}-\phi _{q,\tilde{m}} \|_{L^{2}(\rho)} ^{2})\\ &\leq 2d + 2dm (4d^{2}+C_{\kappa,\gamma}\| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} ) \exp (-2\tilde{m}\log \tilde{m}). \end{align}\] For the second factor, it’s easy to observe that \[\begin{align} &\sum_{1\leq p \leq m, 1\leq s \leq d} \left( \int (\psi^{\boldsymbol{\lambda}}_{p}(y)-\phi _{p, \tilde{m}}(y))e _{s}^{T}y\, d \rho(y) \right)^{2} \leq \sum_{p=1}^{m} \| \psi^{\boldsymbol{\lambda}}_{p}-\phi _{q,\tilde{m}} \|^{2}_{L^{2}(\rho)} \mathbb{E}_{X \sim\rho}\| X \|_{2}^{2} \\ & \leq C_{\mathcal{B}} m (4d^{2}+C_{\kappa,\gamma}\| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} ) \exp (-2\tilde{m}\log \tilde{m}). \end{align}\] Choose \(\tilde{m}\) such that \(m\exp(-2\tilde{m}\log\tilde{m})<1\). Combine two estimations and it is obtained that \[\begin{align} &\, \,\, \,\, \,\, \,\, \,\left\| \tilde{\mathrm{T}}_{n,m,\tilde{m}} - \mathrm{T}_{n,m, \tilde{m}} \right\|_{L^{2}(\nu_{\mathcal{G}})} ^{2} \\&\leq 8C_{F}^{2}C_{\mathcal{B}}d\int _{\mathcal{B}_{2}(\mathcal{X})} (20d^{4}+9d^{2}C_{\kappa,\gamma}\| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})}+ C_{\kappa,\gamma}^{2}\| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})}^{2} )m \exp(-2\tilde{m}\log\tilde{m}) \, d\mathcal{P_{G}^{X}}(\rho) \\ &\leq C_{4} m \exp(-2\tilde{m}\log\tilde{m}) \end{align}\] with \(C_{4}=8C_{F}^{2}C_{\mathcal{B}}d(20d^{4}+9d^{2}(1+C_{\kappa,\gamma}C_{\mathcal{G}})^{2}).\)

Combine all the estimations and we can achieve the following convergence rate for \(n \geq C'_{\kappa,\theta,\gamma}\) with \(C'_{\kappa,\theta,\gamma}=\exp\Big(\frac{4(\gamma-1)\xi C_{\kappa,\theta,\gamma}}{2(\gamma-1)\xi+\gamma}\Big)\): \[\begin{align} &\left\| F(\mathrm{I}_{\boldsymbol{\lambda}}(\cdot),1)- \mathrm{T}_{2n,m,\tilde{m}} \right\|_{L^{2}(\nu_{\mathcal{G}})} \\ \leq &\, \| F(\mathrm{I}_{\boldsymbol{\lambda}}(\cdot),1)-\mathcal{N}_{2n}(\mathrm{I}_{\boldsymbol{\lambda}}(\cdot),1) \|_{L^{2}(\nu_{\mathcal{G}})}+ \| \mathcal{N}_{2n}(\mathrm{I}_{\boldsymbol{\lambda}}(\cdot),1)- \Psi _{2n,m} \|_{L^{2}(\nu_{\mathcal{G}})}+ \left\| \Psi _{2n,m}- \mathrm{T}_{2n,m,\tilde{m}} \right\|_{L^{2}(\nu_{\mathcal{G}})} \\ \leq & \, ((1+C_{\mathcal{B}}) C_{F}^{2})^{\frac{1}{2}} n^{-\frac{1}{2}} + \left( C_{1}^{\frac{1}{2}} + C_{2}^{\frac{1}{2}} \right) m^{-\frac{\xi (\gamma-1)}{\gamma}}+ \left( C_{3}^{\frac{1}{2}}+C_{4}^{\frac{1}{2}} \right)m^{\frac{1}{2}} \exp(-\tilde{m}\log\tilde{m}) \leq C_{*} n^{-\frac{1}{2}} , \end{align}\] with \(C_{*}=3 \max \left\{ (1+C_{\mathcal{B}})^{\frac{1}{2}}C_{F}, C_{1}^{\frac{1}{2}}+C_{2}^{\frac{1}{2}}, C_{3}^{\frac{1}{2}}+C_{4}^{\frac{1}{2}} \right\}\), \[\begin{align} m=\left\lceil{n^{\frac{\gamma}{2(\gamma-1)\xi}}}\right\rceil \text{ and } \tilde{m}=\left\lceil{\left( \frac{1}{2}+\frac{\gamma}{4(\gamma-1)\xi} \right) \log n}\right\rceil. \end{align}\] \(\blacksquare\)

5.2 Oracle Inequality: Sampling Error for Linear Transformers↩︎

In this Subsection, we derive an oracle inequality for the two-stage sampling estimation. We first prove the compactness of the hypothesis space in 5.2.1, which guarantees the existence of \(\mathrm{T}_{\mathbb{S},n}\) in 5 . We then establish covering number estimates in 5.2.2 to bound the empirical processes of the first-stage sampling 5.2.3, the pseudo second-stage sampling 5.2.4 and the second-stage sampling 5.2.5.

5.2.1 Compact subspaces in \(C(\Omega)\)↩︎

Recall that \((\Omega, d_{\Omega})\) is a complete separable metric space. To prove that \(\mathcal{H}_{\mathrm{T}_{n}}\) is compact in \(C(\Omega)\), it’s sufficient to show that \(\mathcal{H}_{\mathrm{T}_{n}}\) is sequentially compact in \(C(\Omega)\). By Arzelà-Ascoli Theorem, it’s sufficient to check the equi-boundedness and equi-continuity of \(\mathcal{H}_{\mathrm{T}_{n}}\). For any \(\mathrm{T}_{n} \in \mathcal{H}_{\mathrm{T}_{n}}\), we can pick a group of parameters \(\Big((\alpha _{j}), (b_{j}), (A_{p,q}^{(j)}), \Theta _{\tanh}\Big)\) satisfying the conditions of the hypothesis space \(\mathcal{H}_{\mathrm{T}_{n}}\). For the simplicity, we let \[\sigma _{j}(\rho,x)= \sigma\left( \sum_{q=1}^{m(n)} {{\phi _{q,\tilde{m}(n)}(x)}} {{\left( \sum_{p=1}^{m(n)}\mathcal{T}_{C_{\mathcal{B}}}\left[ \int \phi _{p,\tilde{m}(n)}(y) A_{p,q}^{(j)} y \, d \rho(y) \right] \right)}}+b_{j}\right).\] Then we have \[\begin{align}&\| \mathrm{T}_{n}(\rho,x)- \mathrm{T}_{n}(\rho',x') \|_{2} = \left\| \sum_{j=1}^{n} \alpha _{j}(\sigma _{j}(\rho,x)-\sigma _{j}(\rho',x')) \right\|_{2} \leq \| \alpha \|_{1} \max _{1\leq j \leq n} \| \sigma _{j}(\rho,x)-\sigma _{j}(\rho',x') \|_{2} \\ \leq & \, \| \alpha \|_{1} \max _{1 \leq j \leq n} \sum_{p,q=1}^{m(n)}\left\| \phi _{q,\tilde{m}(n)}(x) \mathcal{T}_{C_{\mathcal{B}}}\left[ \int \phi _{p,\tilde{m}(n)}(y) A_{p,q}^{(j)}y \, d \rho(y) \right]- \phi _{q,\tilde{m}(n)}(x') \mathcal{T}_{C_{\mathcal{B}}}\left[ \int \phi _{p,\tilde{m}(n)}(y) A_{p,q}^{(j)}y \, d \rho'(y) \right] \right\|_{2} \\ \leq & \, \| \alpha \|_{1} \max _{1 \leq j \leq n} \sum_{p,q=1}^{m(n)} \Biggl\| \phi _{q,\tilde{m}(n)}(x) \left( \mathcal{T}_{C_\mathcal{B}}\left[ \int \phi _{p,\tilde{m}(n)}(y) A_{p,q}^{(j)} y \, d \rho(y) \right]-\mathcal{T}_{C_\mathcal{B}}\left[ \int \phi _{p,\tilde{m}(n)}(y) A_{p,q}^{(j)} y \, d \rho'(y) \right] \right)\\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\, + \mathcal{T}_{C_\mathcal{B}}\left[ \int \phi _{p,\tilde{m}(n)}(y) A_{p,q}^{(j)} y \, d \rho'(y) \right](\phi _{q,\tilde{m}(n)}(x)- \phi _{q,\tilde{m}(n)}(x')) \Biggr\|_{2} \end{align}\]

\[\begin{align} \leq & \, \| \alpha \| _{1} \max_{1\leq j\leq n} \sum_{p,q=1}^{m(n)} \Bigg( \underbrace{ \left\| \int (\phi _{p,\tilde{m}(n)}(y) A_{p,q}^{(j)}y - \phi _{p,\tilde{m}(n)}(y') A_{p,q}^{(j)}y') \, d \rho(y)d\rho'(y') \right\|_{2} }_{ \Delta(\rho,\rho') } \\ &\quad \quad\quad\quad\quad\quad\quad\quad+ \sqrt{ d }C_{\mathcal{B}} \left| \phi _{q,\tilde{m}(n)}(x)-\phi _{q,\tilde{m}(n)}(x') \right| \Bigg) . \end{align}\] Recall that \(\phi _{q,\tilde{m}(n)}(x)= \prod_{l=1}^{d} \mathcal{T}_{1}(\phi _{q,\tilde{m}(n)}^{(l)}(x))\), where \((\phi _{q,\tilde{m}(n)}^{(l)})_{l=1}^{d}\) is a group of two-hidden-layer tanh neural networks shown in Appendix 8.2. It’s easy to observe that \[\begin{align} &\left| \phi _{q, \tilde{m}(n)}(x) - \phi _{q,\tilde{m}(n)}(x') \right| \\ = & \left| \prod _{l=1}^{d} \mathcal{T}_{1}(\phi _{q, \tilde{m}(n)}^{(l)}(x)) - \prod _{l=1}^{d} \mathcal{T}_{1}(\phi _{q,\tilde{m}(n)}^{(l)}(x')) \right| \leq d \max_{1 \leq l \leq d} \left| \phi^{(l)}_{q,\tilde{m}(n)}(x) - \phi _{q,\tilde{m}(n)}^{(l)}(x') \right| \\ \leq &d \max_{1 \leq l \leq d} \left| c_{q,l} ^{T} [\sigma _{\tanh}(W_{q,1}^{(l)}\sigma _{\tanh}(W_{q,0}^{(l)}x+b_{q,0}^{(l)})+b_{q,1}^{(l)})- \sigma _{\tanh}(W_{q,1}^{(l)}\sigma _{\tanh}(W_{q,0}^{(l)}x'+b_{q,0}^{(l)})+b_{q,1}^{(l)})] \right| \\ \leq & d \max _{ 1 \leq l \leq d} \| c_{q,l}^{T} \|_{\infty} \left\| W_{q,1}^{(l)} (\sigma _{\tanh}(W_{q,0}^{(l)}x+b_{q,0}^{(l)})-\sigma _{\tanh}(W_{q,0}^{(l)}x'+b_{q,0}^{(l)})) \right\| _{\infty} \\ \leq & d\max _{ 1 \leq l \leq d} \| c_{q,l}^{T} \|_{\infty} \left\| W_{q,1}^{(l)} \right\|_{\infty} \left\| W_{q,0}^{(l)} \right\|_{\infty} \| x-x' \|_{\infty} \leq \Big(d\max_{1 \leq l \leq d} \| c_{q,l}^{T} \|_{\infty} \left\| W_{q,1}^{(l)} \right\|_{\infty}\left\| W_{q,0}^{(l)} \right\|_{\infty} \Big) \| x-x' \|_{2} \\ \leq& C_{n,d} \| x-x' \|_{2}.\end{align}\] Since the parameters in tanh neural networks are uniformly bounded by \(\| \Theta _{\tanh} \|_{\infty}\), \(C_{n,d}\) just depends on \(n\) and \(d\). It also follows that for any \(\tau \in \prod(\rho, \rho')\), \[\begin{align}\Delta(\rho, \rho')&\leq \int \left\| \phi _{p,\tilde{m}(n)}(y) A_{p,q}^{(j)} y - \phi _{p,\tilde{m}(n)}(y') A_{p,q}^{(j)}y'\right\|_{2} \, d \tau(y,y') \\ &\leq \left\| A_{p,q}^{(j)} \right\|_{F} \int \| \phi _{p,\tilde{m}(n)}(y)y- \phi _{p,\tilde{m}(n)}(y')y' \|_{2} \, d \tau(y,y') \\ & \leq \left\| A_{p,q}^{(j)} \right\|_{F} \left( \int \left\| \phi _{p,\tilde{m}(n)}(y) (y-y') \right\|_{2} \, d \tau (y,y') + \int \left\| y' (\phi _{p,\tilde{m}(n)}(y)- \phi _{p,\tilde{m}(n)}(y')) \right\|_{2} \, d \tau(y,y') \right)\\ & \leq \left\| A_{p,q}^{(j)} \right\|_{F} \left( \int \| y-y' \|_{2} \, d \tau(y,y') + C_{n,d}\sqrt{ \mathbb{E}_{\rho'}\left\| Y' \right\|_{2}^{2} } \sqrt{ \mathbb{E}_{\tau} \| Y-Y' \|_{2}^{2} } \right) \\ & \leq \left\| A_{p,q}^{(j)} \right\|_{F} (1+ C_{n,d} \sqrt{ \mathbb{E}_{\rho'} \| Y' \|_{2}^{2} }) \sqrt{ \mathbb{E}_{\tau} \| Y-Y' \|_{2}^{2} } . \end{align}\] Take the above estimation back and it can be obtained that \[\begin{align}&\left\| \mathrm{T}_{n}(\rho,x)- \mathrm{T}_{n}(\rho',x') \right\|_{2} \\\leq & \, \| \alpha \|_{1} \max_{1 \leq j \leq n} \sum_{p,q=1}^{m(n)} \Big(\left\| A_{p,q}^{(j)} \right\|_{F} (1+C_{n,d}\| Y \|_{L^{2}(\rho')} ) \| Y-Y' \|_{L^{2}(\tau)} + \sqrt{ d }C_{\mathcal{B}} C_{n,d} \| x-x' \|_{2} \Big)\\ \leq &\, \| \alpha \|_{1} m\sqrt{ d } (1+ C_{n,d}\| Y \|_{L^{2}(\rho')} +\sqrt{ d }C_{\mathcal{B}}C_{n,d} )(\| Y-Y' \|_{L^{2}(\tau)}+ \| x-x' \|_{2} )\end{align}\] which holds for any \(\tau \in \prod(\rho,\rho')\). It follows that \[\| \mathrm{T}_{n}(\rho,x) - \mathrm{T}_{n}(\rho',x') \|_{2} \leq C_{F}m\sqrt{ d }(1+C_{n,d}\| Y \|_{L^{2}(\rho')}+\sqrt{ d }C_{\mathcal{B}}C_{n,d})d_{\Omega}((\rho,x), (\rho',x'))\] and proves that \(\mathcal{H}_{\mathrm{T}_{n}}\) is equi-continuous at each \((\rho',x') \in \Omega\).

For any \((\rho,x) \in \Omega\), we have \[\begin{align} \| \mathrm{T}_{n}(\rho,x) \|_{2} &\leq \| b_{0} \|_{2}+ \| \alpha \|_{1} \max_{1 \leq j \leq n} \left( \| b_{j} \|_{2}+ \left\| \sum_{p,q=1}^{m(n)} \phi _{q, \tilde{m}(n)}(x) \mathcal{T}_{C_\mathcal{B}}\left[ \int \phi _{p,\tilde{m}(n)}(y) A_{p,q}^{(j) }y \, d \rho(y) \right] \right\|_{2} \right) \\ &\leq C_{F}\sqrt{ dC_{\mathcal{B}}}+C_{F} \left( \sqrt{ 2dC_{\mathcal{B}}} + \sum_{p,q=1}^{m(n)} \left\| \mathcal{T}_{C_\mathcal{B}}\left[ \int \phi _{p, \tilde{m}(n)}(y) A_{p,q}^{(j)}y \, d \rho(y) \right] \right\|_{2} \right) \\& \leq C_{F}(2\sqrt{ dC_{\mathcal{B}}} + m^{2}C_{\mathcal{B}}\sqrt{ d }). \end{align}\] which shows that \(\{ \mathrm{T}_{n }(\rho,x): \mathrm{T}_{n} \in \mathcal{H}_{\mathrm{T}_{n}}\}\) is bounded for each \((\rho,x )\in \Omega\). Therefore, \(\mathcal{H}_{\mathrm{T}_{n}}\) is compact in \(C(\Omega)\) which guarantees the existence of \(\mathrm{T}_{\mathbb{S},n}\) and the below covering number.

5.2.2 Covering Number Estimations↩︎

Note that in the first stage and pseudo second stage sampling, we have access to the true distributions sampled from \(\mathcal{P}_{\mathcal{G}}\) on \(\mathcal{B}_{2,b}(\mathcal{X})\) such that the second moments are uniformly bounded by \(C_{\mathcal{B}}\), which however doesn’t hold true for the empirical distributions in the second stage sampling.

Recall that the hypothesis space is defined as \[\begin{align}\mathcal{H}_{\mathrm{T}_{n}}=\Biggl\{ \mathrm{T}_{n}: \| \alpha \|_{1} \leq 2C_{F} , \sum_{p,q =1}^{m(n)}\| A_{p,q}^{(j)} \|_{F}^{2} \leq d, \| b_{j} \|_{2} \leq \sqrt{ 2dC_{\mathcal{B}}} \text{ for each }1\leq j\leq n, \\ \| b_{0} \|_{2} \leq C_{F}\sqrt{ 2dC_{\mathcal{B}}}, \text{ and } \left\| \Theta _{\tanh} \right\|_{\infty} \leq c_{1}(c'_{2}\log(n))^{c'_{3}(\log n)^{2}} \Biggr\}.\end{align}\] For \(\sigma _{j}(\rho,x)\) defined above, it’s easy to observe that for any \((\rho,x) \in \Omega _{\mathcal{B}}\), \[\begin{align}\| \sigma _{j}(\rho,x) \|_{2} &\leq \left\| b_{j} + \sum_{p,q=1}^{m(n)} \phi _{q,\tilde{m}(n)}(x) \mathcal{T}_{C_\mathcal{B}}\left[ \int \phi _{p,\tilde{m}(n)} (y) A_{p,q}^{(j)}y \, d \rho(y) \right] \right\|_{2} \\&\leq \| b_{j} \|_{2}+ \sum_{p,q=1}^{m(n)} \int \left\| A_{p,q}^{(j)}y \right\|_{2} d \rho(y) \\ & \leq \| b_{j} \|_{2} + C_{\mathcal{B}}^{\frac{1}{2}}\sum_{p,q=1}^{m(n)} \left\| A_{p,q}^{(j)} \right\|_{F}\\ &\leq \sqrt{ 2dC_{\mathcal{B}}} + \sqrt{ C_{\mathcal{B}}}m\sqrt{ d }\leq m\sqrt{2 d C_{\mathcal{B}}}. \end{align}\] Choose \(\mathrm{T}_{n}, \mathrm{ \bar{T}}_{n} \in \mathcal{H}_{\mathrm{T}_{n}}\) with \(\| \alpha-\bar{\alpha} \|_{1} \leq \epsilon\), \(\left( \sum_{p,q=1}^{m(n)}\left\| A_{p,q}^{(j)}- \bar{A}_{p,q}^{(j)} \right\|_{F}^{2} \right)^{\frac{1}{2}}\leq \epsilon\), \(\| b_{j}-\bar{b}_{j} \|_{2} \leq \epsilon\) for \(1 \leq j \leq n\), and \(\| b_{0}-\bar{b}_{0} \|_{2} \leq \epsilon\). Then we have \[\begin{align}\left\| \mathrm{T}_{n}(\rho,x)- \bar{\mathrm{T}}_{n}(\rho,x) \right\|_{2} &= \left\|(b_{0}-\bar{b}_{0})+ \sum_{j=1}^{n} (\alpha _{j} \sigma _{j}(\rho,x) - \bar{\alpha}_{j}\bar{\sigma}_{j}(\rho,x)) \right\| _{2} \\&\leq \| b_{0} -\bar{b}_{0}\|_{2} + \left\| \sum_{j=1}^{n} (\alpha _{j}-\bar{\alpha}_{j})\sigma _{j}(\rho,x)+\bar{\alpha}_{j}(\sigma _{j}(\rho,x)-\bar{\sigma}_{j}(\rho,x)) \right\|_{2} \\ & \leq \epsilon +\| \alpha-\bar{\alpha} \|_{1} \max_{1 \leq j \leq n} \| \sigma _{j}(\rho,x) \|_{2} + \| \bar{\alpha} \|_{1} \max_{1\leq j \leq n} \| \sigma _{j}(\rho,x)- \bar{\sigma}_{j}(\rho,x) \|_{2} \\ & \leq 2\sqrt{ dC_{\mathcal{B}}} m\epsilon + 2C_{F}\max_{1 \leq j\leq n} \| \sigma _{j}(\rho ,x)- \bar{\sigma}_{j}(\rho ,x) \|_{2}. \end{align}\] For the second term in the above inequality, it follows that \[\begin{align}&\| \sigma _{j}(\rho,x)- \bar{\sigma} _{j}(\rho ,x)\|_{2} \\\leq &\, \Biggl\|(b_{j}-\bar{b}_{j})+\sum_{p,q=1}^{m(n)} \Biggl(\phi _{q,\tilde{m}(n)}(x)\mathcal{T}_{C_\mathcal{B}}\left[ \int \phi _{p,\tilde{m}(n)}(y)A_{p,q}^{(j)}y \, d \rho(y) \right] \\& \,\,\,\,\,\,\,\,\,\,\, - \bar{\phi}_{q,\tilde{m}(n)}(x) \mathcal{T}_{C_\mathcal{B}}\left[ \int \bar{\phi}_{p,\tilde{m}(n)}(y) \bar{A}_{p,q}^{(j)}y \, d \rho(y) \right] \Biggr) \Biggr\|_{2} \\\leq & \, \| b_{j} - \bar{b} _{j}\|_{2} + \sum_{p,q=1}^{m(n)} \Biggl\|(\phi _{q,\tilde{m}(n)}(x) -\bar{\phi}_{q,\tilde{m}(n)}(x)) \mathcal{T}_{C_\mathcal{B}}\left[\int \phi _{p,\tilde{m}(n)}(y) A_{p,q}^{(j)}y \, d \rho(y) \right]\Biggr\|_{2} \\ &+ \sum_{p,q=1}^{m(n)} \left\| \bar{\phi}_{q,\tilde{m}(n)}(x) \left( \mathcal{T}_{C_\mathcal{B}}\left[\int \phi _{p,\tilde{m}(n)}(y) A_{p,q}^{(j)}y \, d\rho(y) \right] - \mathcal{T}_{C_\mathcal{B}}\left[\int \bar{\phi} _{p,\tilde{m}(n)}(y) \bar{A}_{p,q}^{(j)}y \, d\rho(y) \right]\right) \right\|_{2} \\ \leq & \, \| b_{j}-\bar{b}_{j} \|_{2} + \sum_{p,q=1}^{m(n)} \left| \phi _{q,\tilde{m}(n)}(x)- \bar{\phi}_{q,\tilde{m}(n)}(x) \right| \int \left\| A_{p,q}^{(j)} y\right\|_{2} \, d \rho(y) \\ & \,\,\,\,\,\,\,\,\,\, + \sum_{p,q=1}^{m(n)}\left\| \int \Big(\phi _{p,\tilde{m}(n)}(y) A_{p,q}^{(j)}y- \bar{\phi}_{p,\tilde{m}(n)}(y)\bar{A}_{p,q}^{(j)}y \Big)\, d \rho(y) \right\|_{2} \\ \leq&\| b_{j}- \bar{b}_{j} \|_{2} + C_{\mathcal{B}}^{\frac{1}{2}}\sum_{p,q=1}^{m(n)} \left\| A_{p,q}^{(j)} \right\|_{F} \left| \phi _{q,\tilde{m}(n)}(x)-\bar{\phi} _{q,\tilde{m}(n)}(x)\right| + \sum_{p,q=1}^{m(n)} \left\| \int \phi _{p,\tilde{m}(n)}(y) (A_{p,q}^{(j)}-\bar{A}_{p,q}^{(j)})y \, d \rho(y) \right\|_{2} \\ & \,\,\,\,\,\,\,\,\,\, + \sum_{p,q=1}^{m(n)} \left\| \int (\phi _{p,\tilde{m}(n)}(y)-\bar{\phi}_{p,\tilde{m}(n)}(y)) \bar{A}_{p,q}^{(j)}y \, d \rho(y) \right\|_{2} \\ \leq & \, \| b_{j}- \bar{b}_{j} \|_{2} + C_{\mathcal{B}}^{\frac{1}{2}} \max_{1 \leq q \leq m(n)} \left| \phi _{q,\tilde{m}(n)}(x)- \bar{\phi}_{q, \tilde{m}(n)}(x) \right| \sum_{p,q=1}^{m(n)} \left\| A_{p,q}^{(j)} \right\|_{F} + C_{\mathcal{B}}^{\frac{1}{2}} \sum_{p,q=1}^{m(n)}\left\| A_{p,q}^{(j)}- \bar{A}_{p,q}^{(j)} \right\|_{F} \\ & \,\,\,\,\,\,\,\,\,\, + \sum_{p,q=1}^{m(n)} \int \left| \phi _{p,\tilde{m}(n)}(y)- \bar{\phi} _{p, \tilde{m}(n)}(y) \right| \left\| \bar{A}_{p,q}^{(j)}y \right\|_{2} \, d \rho(y) \\ \leq \, &\epsilon + \sqrt{ C_{\mathcal{B}}}m\epsilon+ \sqrt{dC_{\mathcal{B}}}m \max_{1\leq q \leq m(n)} \left| \phi _{q,\tilde{m}(n)}(x)-\bar{\phi}_{q,\tilde{m}(n)}(x) \right|\\ &\quad\quad+\sqrt{ dC_{\mathcal{B}}}m \max_{1 \leq p \leq m(n)} \| \phi _{p,\tilde{m}(n)}-\bar{\phi}_{p,\tilde{m}(n)} \|_{L^{2}(\rho)}. \end{align}\] Recall that the above two-hidden-layer tanh neural networks have the form \(\phi _{p,\tilde{m}(n)}=\mathcal{T}_{1,\odot}\big(\phi^{(1)}_{p,\tilde{m}(n)}, \dots, \phi^{(d)}_{p, \tilde{m}(n)}\big)\) and then it can be obtained that for any \(x \in \mathbb{R}^{d}\), \[\begin{align}& \left| \phi _{p,\tilde{m}(n)}(x)- \bar{\phi}_{p,\tilde{m}(n)}(x) \right| \leq d \max _{1 \leq l \leq d} \left| \phi^{(l)} _{p,\tilde{m}(n)}(x)- \bar{\phi}_{p,\tilde{m}(n)}^{(l)}(x) \right| \\ \leq & \,d \max _{1 \leq l \leq d} \left| c_{p,l} ^{T} \underbrace{ \left[\sigma _{\tanh}(W_{p,1}^{(l)}\sigma _{\tanh}(W_{p,0}^{(l)}x+b_{p,0}^{(l)})+b_{p,1}^{(l)})\right] }_{ =: f_{p}^{(l)}(x) } - \bar{c}_{p,l} ^{T} \underbrace{ \left[\sigma _{\tanh}(\overline{W}_{p,1}^{(l)}\sigma _{\tanh}(\overline{W}_{p,0}^{(l)}x+\bar{b}_{p,0}^{(l)})+\bar{b}_{p,1}^{(l)})\right] }_{ =: \bar{f}_{p}^{(l)}(x) } \right| \\ \leq & \, d \max _{ 1 \leq l \leq d} \left| c_{p,l } ^{T}f_{p}^{(l)}(x)- \bar{c}_{p,l}^{T} f_{p}^{(l)}(x)+ \bar{c}_{p,l}^{T}f_{p}^{(l)}(x)-\bar{c}_{p,l}^{T} \bar{f}_{p}^{(l)}(x)\right| \\ \leq & \, d \max_{1 \leq l \leq d} \left(\| c_{p,l} - \bar{c}_{p,l} \|_{1} +\| \bar{c}_{p,l} \|_{1} \left\| f_{p}^{(l)}(x)- \bar{f}_{p}^{(l)}(x) \right\|_{\infty} \right) \\\leq& \, 8d\,\tilde{m}(n)\max_{1\leq l \leq d} \left\{\| c_{p,l}- \bar{c}_{p,l} \|_{\infty} + \| \bar{c}_{p,l} \|_{\infty} \left\| f_{p}^{(l)}(x)- \bar{f}_{p}^{(l)}(x) \right\|_{\infty} \right\} ,\end{align}\] where \[\begin{align}&\left\| f_{p}^{(l)}(x)- \bar{f}_{p}^{(l)}(x) \right\|_{\infty} \\\leq & \left\| (W_{p,1}^{(l)}\sigma _{\tanh}(W_{p,0}^{(l)}x+b_{p,0}^{(l)})+b_{p,1}^{(l)})-(\overline{W}_{p,1}^{(l)}\sigma _{\tanh}(\overline{W}_{p,0}^{(l)}x+\bar{b}_{p,0}^{(l)})+\bar{b}_{p,1}^{(l)}) \right\|_{\infty} \\ \leq & \left\| b_{p,1}^{(l)}- \bar{b}_{p,1}^{(l)} \right\|_{\infty} + \left\| W_{p,1}^{(l)} - \overline{W}_{p,1}^{(l)} \right\|_{\infty} + \left\| W_{p,1}^{(l)} \right\|_{\infty} \left\| ( W_{p,0}^{(l)}-\overline{W}_{p,0}^{(l)})x + b_{p,0}^{(l)}- \bar{b}_{p,0 }^{(l)} \right\|_{\infty} . \end{align}\] Choose that \[\label{ineq:cov} \begin{align} \| c_{p,l}-\bar{c}_{p,l} \|_{\infty} \leq \epsilon, &\left\| b_{p,1}^{(l)}- \bar{b}_{p,1}^{(l)} \right\|_{\infty} \leq \epsilon, \left\| W_{p,1}^{(l)}- \overline{W}_{p,1}^{(l)} \right\|_{\max} \leq \epsilon,\\ \left\| W_{p,0}^{(l)}- \overline{W}_{p,0}^{(l)} \right\|_{\max}&\leq \epsilon , \left\| b_{p,0}^{(l)}- \bar{b}_{p,0}^{(l)} \right\|_{\infty} \leq \epsilon. \end{align}\tag{20}\] Then it’s easy to see that \[\begin{align} \left\| f_{p}^{(l)}(x) - \bar{f}_{p}^{(l)}(x) \right\|_{\infty} \leq 24(1+\| x \|_{\infty})[c_{4}\tilde{m}(n)]^{c_{5}(\tilde{m}(n))^{2}}\epsilon, \end{align}\] which implies that \[\begin{align} \left| \phi _{p,\tilde{m}(n)}(x) - \bar{\phi}_{p, \tilde{m}(n)}(x) \right| \leq 192d \, (2+ \| x \|_{\infty})[c_{4}\tilde{m}(n)]^{3c_{5}(\tilde{m}(n))^{2}}\epsilon \end{align}\] and that \[\begin{align} &\sqrt{ dC_{\mathcal{B}}} m \Big(\max _{1\leq p,q\leq m(n)} \left| \phi _{q,\tilde{m}}(x) - \bar{\phi}_{q,\tilde{m}}(x) \right|+ \| \phi _{p,\tilde{m}}-\bar{\phi}_{p,\tilde{m}} \|_{L^{2}(\rho)} \Big) \\ \leq \, & \sqrt{ dC_{\mathcal{B}}} m \Big( 192d\left(4+\| x \|_{\infty} + \int_{\mathcal{X}} \| x \|_{\infty} \, d\rho \right)[c_{4}\tilde{m}(n)]^{3c_{5}(\tilde{m}(n))^{2}} \Big)\epsilon \\ \leq\, & 192C_{\mathcal{B}}d^{\frac{3}{2}}(5+\| x \|_{\infty})(m(n))[c_{4}\tilde{m}(n)]^{3c_{5}(\tilde{m}(n))^{2}}\epsilon. \end{align}\] We can conclude that \[\left\| \mathrm{T}_{n}(\rho,x)-\bar{\mathrm{T}}_{n}(\rho,x) \right\|_{2} \leq 386 C_{F}C_{\mathcal{B}}d^{\frac{3}{2}} (9+\| x \|_{\infty} )(m(n)) [c_{4}\tilde{m}(n)]^{3c_{5}(\tilde{m}(n))^{2}}\epsilon=: \mathrm{\Xi}(x, \epsilon).\]

For any pseudometric space \((\mathcal{H},d_{\mathcal{H}})\) and \(\epsilon >0\), the covering number of \((\mathcal{H}, d_{\mathcal{H}})\) with radius \(\epsilon\) is defined as \(\inf\{ \left| \mathcal{D} \right|: \mathcal{D} \subset \mathcal{H}, \text{for any } \Psi \in \mathcal{H} \text{ there exists } \Phi \in \mathcal{D} \text{ with } d_{\mathcal{H}}(\Psi,\Phi) \leq \epsilon \}.\)

We denote by \(\mathrm{N}(\mathcal{H}_{\mathrm{T}_{n}}, \epsilon, d_{\mathcal{B}_{2,b}(\mathcal{X})})\) the uniform \(\epsilon\)-covering number for the first stage sampling with the pseudometric \[\begin{align} d_{\mathcal{B}_{2,b}(\mathcal{X})}(\Phi _{1}, \Phi _{2})= \sup_{\rho \in \mathcal{B}_{2,b}(\mathcal{X})} \mathbb{E} _{\rho}\| \Phi_{1}(\tilde{X})- \Phi _{2}(\tilde{X}) \|_{2}. \end{align}\] It follows that for the above \(\mathrm{T}_{n}, \bar{\mathrm{T}}_{n}\) and the parameter selections,

\[\begin{align} d_{\mathcal{B}_{2,b}(\mathcal{X})}(\mathrm{T}_{n}, \bar{\mathrm{T}}_{n}) \leq \sup_{\rho \in \mathcal{B}_{2,b}(\mathcal{X})}\mathbb{E}_{\rho} \Xi(X, \epsilon)\leq c_{6}C_{F}C_{\mathcal{B}}^{2}d^{\frac{3}{2}} (m(n))[c_{4}\tilde{m}(n)]^{3c_{5}(\tilde{m}(n))^{2}}\epsilon. \end{align}\] Then the \(\tilde{\epsilon}\)-covering number of \(\mathcal{H}_{\mathrm{T}_{n}}\) with respect to \(d_{\mathcal{B}_{2,b}(\mathcal{X})}\) can bounded as \[\begin{align} &\quad\mathrm{N}(\mathcal{H}_{\mathrm{T}_{n}}, \tilde{\epsilon}, d_{\mathcal{B}_{2,b}(\mathcal{X})}) \\&\leq \left( 1+ \frac{4C_{F}}{\epsilon} \right)^{n}\left( 1+ \frac{2C_{F}\sqrt{ 2dC_{\mathcal{B}}}}{\epsilon} \right)^{n\Big(m^{2}d^{2}+d\Big)+1} \left( 1+ \frac{(c'_{2}\tilde{m})^{c'_{3}\tilde{m}^{2}}}{\epsilon} \right)^{[8\tilde{m}d+8\tilde{m}+(8\tilde{m})^{2}+8\tilde{m}+8\tilde{m}]dm} \\ & \leq \left( 1+ \frac{4C_{F}\sqrt{ dC_{\mathcal{B}}}}{\epsilon} \right)^{3nm^{2}d^{2}} \left(1+ \frac{{(c'_{2}\tilde{m})^{c'_{3}\tilde{m}^{2}}}}{\epsilon} \right)^{96d^{2}\tilde{m}^{2} m} \\ & \leq \left( 1+ \frac{4c_{6}C_{F}C_{\mathcal{B}}^{3}d^{2}m(c_{4}\tilde{m})^{3c_{5}\tilde{m}^{2}}}{\tilde{\epsilon}} \right)^{3d^{2}nm^{2}} \left( 1+\frac{c_{6}C_{F}C_{\mathcal{B}}^{2}d^{\frac{3}{2}}m(c_{4}\tilde{m})^{6c_{5}\tilde{m}^{2}}}{\tilde{\epsilon}} \right)^{96d^{2}\tilde{m}^{2}m} \\ &\leq \left(1+ \frac{8C_{d,F,\mathcal{B}}}{\tilde{\epsilon}} \right)^{100d^{2}nm^{2}} ((c_{4}m\tilde{m})^{600c_{5}d^{2}nm^{2}\tilde{m}^{2}}), \end{align}\] with \(C_{d,F,\mathcal{B}}=c_{6}C_{F}C_{\mathrm{\mathcal{B}}}^{3}d^{2}\), which is followed by \[\log \mathrm{N}(\mathcal{H}_{\mathrm{T}_{n}}, \tilde{\epsilon}, d_{\mathcal{B}_{2,b}(\mathcal{X})}) \leq 100nd^{2}m^{2}\log\left( 1+\frac{8C_{d,F,\mathcal{B}}}{\tilde{\epsilon}} \right)+ 600c_{5}d^{2}nm^{2}\tilde{m}^{2}\log(c_{4}m\tilde{m}).\] Conditioned on the pseudo second-stage samples \((\rho_{X}^{(i)}, X_{ij})_{1 \leq i \leq N, 1 \leq j \leq n_{i}}\), we can define the empirical \(L^{2}_{\hat{P}}\) \(\epsilon\)-covering number \(\mathrm{N}(\mathcal{H}_{\mathrm{T}_{n}}, \epsilon, d_{\hat{P}})\) with the pseudometric \[d _{\hat{P}}(\Phi_{1},\Phi_{2})=\left( \frac{1}{N}\sum_{i=1}^{N} \frac{1}{n_{i}} \sum_{j=1}^{n_{i}} \| \Phi _{1}(\rho_{X}^{(i)},X_{ij})- \Phi _{2}(\rho_{X}^{(i)},X_{ij}) \|_{2}^{2} \right)^{\frac{1}{2}}.\] Then for the above \(\mathrm{T}_{n}, \bar{\mathrm{T}}_{n}\) and the parameter selections, we have \[\begin{align} d_{\hat{P}}( \mathrm{T}_{n}, \bar{\mathrm{T}}_{n})&\leq \left( \frac{1}{N}\sum_{i=1}^{N} \frac{1}{n_{i}} \sum_{j=1}^{n_{i}} \Xi(X_{ij}, \epsilon)^{2} \right)^{\frac{1}{2}}\\&\leq 386\sqrt{ 2 }C_{F}C_{\mathcal{B}}d^{\frac{3}{2}} \left( 9 + \sqrt{ \frac{1}{N}\sum_{i=1}^{N} \frac{1}{n_{i}} \sum_{j=1}^{n_{i}} \| X_{ij} \|_{\infty}^{2} } \right)m[c_{4}\tilde{m}]^{3c_{5}\tilde{m}^{2}}\epsilon \\ &\leq c_{6}C_{F}C_{\mathcal{B}}d^{\frac{3}{2}} \underbrace{ \left(9+ \sqrt{ \frac{1}{N}\sum_{i=1}^{N} \frac{1}{n_{i}} \sum_{j=1}^{n_{i}} \| X_{ij} \|_{2}^{2} }\right) }_{ =: \| \hat{X} \|_{2} } m(c_{4}\tilde{m})^{3c_{5}\tilde{m}^{2}} \epsilon. \end{align}\] Similarly, it’s easy to see that \[\log \mathrm{N}(\mathcal{H}_{\mathrm{T}_{n}}, \tilde{\epsilon}, d_{\hat{P}}) \leq 100nd^{2}m^{2}\log\left(1+ \frac{8c_{6}C_{F}C_{\mathcal{B}}^{2}d^{2}\| \hat{X} \|_{2}}{\tilde{\epsilon}} \right)+ 600 c_{5}nd^{2}m^{2}\tilde{m}^{2}\log(c_{4}m\tilde{m}).\]

5.2.3 First-Stage Sampling Error Estimation↩︎

The following lemma is from Lemma 3.19 [@cuckerlearning].

We consider the class of functions \(\mathcal{J} _{\Phi}:\mathcal{B}_{2,b}(\mathcal{X} \times \mathcal{Y}) \to \mathbb{R}\), denoted by \[\mathscr{J}(\mathcal{H}_{\mathrm{T}_{n}}):= \Big\{ \mathcal{J} _{\Phi}:\mathcal{J} _{\Phi}(\rho_{XY})= \mathbb{E}[\| \mathscr{T}_{M}\Phi(\tilde{X})-Y \|_{2}^{2} | \rho_{XY} ] - \mathbb{E}[\| \Phi _{\mathcal{G}}(\tilde{X})-{Y} \|_{2}^{2} |\rho_{XY} ], \Phi \in \mathcal{H}_{\mathrm{T}_{n}}\Big\}.\] Then for each \(\mathcal{J} _{\Phi}\in \mathscr{J}(\mathcal{H}_{\mathrm{T}_{n}})\), we have \[\mathbb{E} (\mathcal{J} _{\Phi})=\mathcal{E}(\mathscr{T}_{M}\Phi)-\mathcal{E}(\Phi _{\mathcal{G}}) \text{ and } \frac{1}{N} \sum_{i=1}^{N}\mathcal{J} _{\Phi}(\rho_{XY}^{(i)})= \mathcal{E}_{N}(\mathscr{T}_{M}\Phi)-\mathcal{E}_{N}(\Phi _{\mathcal{G}}),\] where \(\begin{aligned}\mathcal{E}(\mathscr{T}_{M}\Phi)-\mathcal{E}(\Phi _{\mathcal{G}})= \| \mathscr{T}_{M}\Phi - \Phi _{\mathcal{G}}\|_{L^{2}_{\nu_{\mathcal{G}}}}^{2}. \end{aligned}\) Also notice that \[\begin{align}\left| \mathcal{J} _{\Phi}(\rho_{XY}) \right|&= \left| \mathbb{E}\big[\| \mathscr{T}_{M}\Phi(\tilde{X})-Y \|_{2}^{2}-\| \Phi _{\mathcal{G}}(\tilde{X})-Y \|^{2}_{2}\big|\rho_{XY}\big] \right|\\& \leq \left| \mathbb{E}\big[(\| \mathscr{T}_{M}\Phi(\tilde{X})-Y \|_{2}+\| \Phi _{\mathcal{G}}(\tilde{X})-Y \|_{2})(\| \mathscr{T}_{M}\Phi(\tilde{X})- \Phi _{\mathcal{G}}\|_{2} )\big|\rho_{XY}\big] \right|\\ & \leq 8M^{2},\end{align}\] which implies that \(\left| \mathcal{J} _{\Phi}(\rho_{XY})- \mathbb{E}(\mathcal{J} _{\Phi}) \right|\leq 16M^{2}\) and \[\begin{align}\mathbb{E}(\mathcal{J} _{\Phi}^{2})& \leq \mathbb{E}_{\rho_{XY} \sim \mathcal{P}_{\mathcal{G}}}\Big[ \mathbb{E}\big[(\| \mathscr{T}_{M} \Phi(\tilde{X})-Y \|_{2}^{2}-\| \Phi _{\mathcal{G}}(\tilde{X})-Y \|_{2}^{2} )^{2}|\rho_{XY} \big]\Big]\\&\leq 16M^{2}\mathbb{E}_{\rho_{X} \sim \mathcal{P_{G}^{X}}}(\mathbb{E}[\| \mathscr{T}_{M}\Phi(\tilde{X})-\Phi _{\mathcal{G}}\|_{2}|\rho_{X}])^{2} \leq 16M^{2}\| \mathscr{T}_{M} \Phi- \Phi _{\mathcal{G}}\|_{L_{\nu}^{2}}^{2}=16M^{2}\mathbb{E}(\mathcal{J} _{\Phi}). \end{align}\] Then for any \(\Phi _{1}, \Phi _{2} \in \mathcal{H}_{\mathrm{T}_{n}}\), it follows that \[\begin{align}\left| \mathcal{J} _{\Phi _{1}}(\rho_{XY})- \mathcal{J} _{\Phi_{2}}(\rho_{XY}) \right|&= \left| \mathbb{E}[\| \mathscr{T}_{M}\Phi_{1}(\tilde{X})-Y \|_{2}^{2} | \rho_{XY} ] -\mathbb{E}[\| \mathscr{T}_{M}\Phi_{2}(\tilde{X})-Y \|_{2}^{2} | \rho_{XY} ] \right| \\ & \leq 4M \left| \mathbb{E} \big[\| \mathscr{T}_{M} \Phi_{1}(\tilde{X})-\mathscr{T}_{M}\Phi_{2}(\tilde{X}) \|_{2} | \rho_{X}\big] \right| \\ &\leq 4M \left| \mathbb{E} \big[\| \Phi_{1}(\tilde{X})-\Phi_{2}(\tilde{X}) \|_{2} | \rho_{X}\big] \right| \leq 4M d_{\mathcal{B}_{2,b}(\mathcal{X})}(\Phi_{1}, \Phi_{2}),\end{align}\]which shows that \[\mathrm{N}(\mathscr{J}(\mathcal{H}_{\mathrm{T}_{n}}), \epsilon, \| \cdot \|_{L^{\infty}(\mathcal{B}_{2,b}(\mathcal{X}\times \mathcal{Y}))} ) \leq \mathrm{N}\left( \mathcal{H}_{\mathrm{T}_{n}}, \frac{\epsilon}{4M}, d_{\mathcal{B}_{2,b}(\mathcal{X})} \right).\] Then with the uniform ratio inequality, we have that \[\begin{align} &\mathbb{P} \left\{ \sup_{\Phi \in \mathcal{H}_{\mathrm{T}_{n}}} \frac{(\mathcal{E}(\mathscr{T}_{M}\Phi)-\mathcal{E}(\Phi _{\mathcal{G}})) -(\mathcal{E}_{N}(\mathscr{T}_{M}\Phi) -\mathcal{E}_{N}(\Phi _{\mathcal{G}}))}{\sqrt{ \mathcal{E}(\mathscr{T}_{M}\Phi)-\mathcal{E}(\Phi _{\mathcal{G}}) +\epsilon }} > \sqrt{ \epsilon } \right\} \\ &\leq \mathrm{N}\left( \mathscr{J}(\mathcal{H}_{\mathrm{T}_{n}}), \frac{\epsilon}{4}, \| \cdot \|_{L^{\infty}(\mathcal{B}_{2,b}(\mathcal{X}\times \mathcal{Y}))} \right) \exp \left\{ - \frac{3N\epsilon}{2048M^{2}} \right\} \leq \mathrm{N}\left( \mathcal{H}_{\mathrm{T}_{n}}, \frac{\epsilon}{16M}, d_{\mathcal{B}_{2,b}(\mathcal{X})} \right) \exp \left\{ - \frac{3N\epsilon}{2048M^{2}} \right\}. \end{align}\] It’s easy to see that \(\sqrt{( \mathcal{E}(\mathscr{T}_{M}\Phi)-\mathcal{E}(\Phi _{\mathcal{G}})+\epsilon) \epsilon } \leq \frac{1}{2}(\mathcal{E}(\mathscr{T}_{M}\Phi)-\mathcal{E}(\Phi _{\mathcal{G}}))+\epsilon\), which follows by taking \(\Phi= \mathrm{T}_{\mathbb{S},n}\) that \[\begin{align} \label{ineq:e1} \mathbb{P}\left\{ \mathcal{E}_{1}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})) > \frac{1}{2}\big(\mathcal{E}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))-\mathcal{E}(\Phi _{\mathcal{G}})\big) +\epsilon \right\} \leq \mathrm{N}\left( \mathcal{H}_{\mathrm{T}_{n}}, \frac{\epsilon}{16M}, d _{\mathcal{B}_{2,b}(\mathcal{X})} \right)\exp \left\{ - \frac{3N\epsilon}{2048M^{2}} \right\}. \end{align}\tag{21}\]

Similarly, For each \(\Phi \in \mathcal{H}_{\mathrm{T}_{n}}\), note that \(\| \Phi \|_{C(\Omega _{\mathcal{B}})}\) is uniformly bounded. We define \[\begin{align} \widetilde{\mathcal{J}}_{\Phi}(\rho_{XY})= \mathbb{E}[\| \Phi(\tilde{X})-Y \|_{2}^{2}|\rho_{XY}] - \mathbb{E}[\| \Phi _{\mathcal{G}}(\tilde{X})- Y \|_{2}^{2} | \rho_{XY}]. \end{align}\] \(\widetilde{\mathcal{J}}_{\Phi}\) can be considered as a random variable with \(\left| \widetilde{\mathcal{J}}_{\Phi}(\rho_{XY}) \right| \leq (3M+ \| \Phi \|_{C(\Omega _{\mathcal{B}})})^{2}\) and it follows that \[\left| \widetilde{\mathcal{J}}_{\Phi}(\rho_{XY})- \mathbb{E}(\widetilde{\mathcal{J}}_{\Phi}) \right| \leq 2(3M+\| \Phi \|_{C(\Omega _{\mathcal{B}})})^{2}\] and \[\mathbb{E}(\widetilde{\mathcal{J}}_{\Phi}^{2}) \leq (3M+\| \Phi \|_{C(\Omega _{\mathcal{B}})})^{2}\mathcal{E}_{4}(\Phi).\] Then with the Bernstein inequality, we have \[\begin{align} \label{ineq:e11} \mathbb{P}\{ \mathcal{E}'_{1}(\Phi) > \epsilon \} \leq \exp \left\{ - \frac{N\epsilon^{2}}{2(3M+\| \Phi \|_{C(\Omega _{\mathcal{B}})} )^{2}\left( \mathcal{E}_{4}(\Phi)+\frac{2}{3}\epsilon \right)} \right\}. \end{align}\tag{22}\]

5.2.4 Second-Stage Sampling Error with Ground Truth Context↩︎

Assume that \(n_{1}=\dots=n_{N}=\vartheta\). Conditioned on the given first-stage samples \((\rho_{XY}^{(i)})_{1 \leq i \leq N}\), the random variables \((X_{ij},Y_{ij})_{1\leq i\leq N,1 \leq j\leq \vartheta}\) are independent but not identically distributed: for each \(1 \leq i \leq N\), \((X_{ij}, Y_{ij}) \sim \rho_{XY}^{(i)}\). Let \(\widetilde{S}=(\rho_{X}^{(i)}, X_{ij},Y_{ij})_{1\leq i \leq N,1 \leq j \leq \vartheta}\). We introduce a random variable \[\Lambda(\widetilde{S})= \sup_{\bar{\Phi} \in \mathscr{T}_{M}(\mathcal{H}_{\mathrm{T}_{n}})} \frac{1}{N}\sum_{i=1}^N\frac{1}{\vartheta}\sum_{j=1}^{\vartheta} \Big(\mathbb{E}\big[\| \bar{\Phi}(\tilde{X})-Y \|_{2}^{2} \big|\rho_{XY}^{(i)} \big] - \| \bar{\Phi}(\rho_{X}^{(i)}, X_{ij}) - Y_{ij} \|_{2}^{2} \Big),\] which follows that \[\left| \Lambda(\widetilde{S}) - \Lambda (\widetilde{S}^{\backslash(i,j)}) \right| \leq \sup_{\bar{\Phi} \in \mathscr{T}_{M}(\mathcal{H}_{\mathrm{T}_{n}})} \frac{1}{N\vartheta}\left| \| \bar{\Phi}(\rho_{X}^{(i)},X_{ij})-Y_{ij} \|_{2}^{2}- \| \bar{\Phi}(\rho_{X}^{(i)},X_{ij}')-Y_{ij}' \|_{2}^{2} \right| \leq \frac{8M^{2}}{N\vartheta}\] where \(\widetilde{S}^{\backslash(i,j)}\) denotes the sample \(\widetilde{S}\) with a change on \((i,j)\)-th variable with \((X_{ij},Y_{ij})\overset{i.i.d}{\sim}(X_{ij}',Y_{ij}')\) while all others fixed. Then by Azuma-McDiarmind’s inequality, it can be derived that \[\mathbb{P} \left\{\left| \Lambda(\widetilde{S})- \mathbb{E}\big[\Lambda(\widetilde{S})|(\rho_{XY}^{(i)})_{i}\big]\right| > \epsilon \right\} \leq 2 \exp \left\{ - \frac{\left( N\vartheta \right)\epsilon^{2}}{32 M^{4}} \right\},\text{ for any }\epsilon>0.\] Let \((\zeta_{ij})_{1 \leq i\leq N, 1\leq j \leq \vartheta}\) be i.i.d Rademacher random variables. Then by the symmetrization [@ledoux1991probability], we have \[\begin{align} \mathbb{E}\big[\Lambda(\widetilde{S})\big|(\rho_{XY}^{(i)})_{i}\big]&\leq\mathbb{E}_{\big[(X_{ij},Y_{ij})\sim \rho_{XY}^{(i)}\big]_{i}} \mathbb{E}_{(\zeta _{ij})} \sup_{\bar{\Phi} \in \mathscr{T}_{M}(\mathcal{H}_{\mathrm{T}_{n}})} \frac{2}{N}\sum_{i=1}^{N} \frac{1}{\vartheta}\sum_{j=1}^{\vartheta} \zeta _{ij}\| \bar{\Phi}(\rho_{X}^{(i)},X_{ij})-Y_{ij} \|_{2}^{2} . \end{align}\] Since \(\left| l_{y}(u)-l_{y}(u') \right| \leq 4M \| u-u' \|_{2}\) where \(l_{y}(u):= \| u-y \|_{2}^{2}\) with \(\| u \|_{2}\) and \(\| y \|_{2}\) less than \(M\), it follows by the vector-contraction inequality [@maurer2016vectorcontraction] that \[\begin{align} \mathbb{E} [ \Lambda(\widetilde{S}) | (\rho_{XY}^{(i)})_{i}] &\leq 8\sqrt{ 2 }M\mathbb{E}_{\big[X_{ij} \sim \rho_{X}^{(i)}\big]_{i}} \mathbb{E}_{(\boldsymbol{\zeta}_{ij})}\sup_{\bar{\Phi} \in \mathscr{T}_{M}(\mathcal{H}_{\mathrm{T}_{n}})} \frac{1}{N}\sum_{i=1}^{N} \frac{1}{\vartheta} \sum_{j=1}^{\vartheta} \langle \boldsymbol{\zeta}_{ij}, \bar{\Phi}(\rho_{X}^{(i)},X_{ij}) \rangle \end{align}\] where \(\boldsymbol{\zeta}_{ij}\) is a random vector in \(\mathbb{R}^{d}\) with each component being i.i.d Rademacher random variable.

We define a family of zero-mean random variables indexed by \(\bar{\Phi} \in \mathscr{T}_{M}(\mathcal{H}_{\mathrm{T}_{n}})\) as \[Z_{\bar{\Phi}}:= \frac{1}{\sqrt{ N\vartheta }} \sum_{i=1}^{N} \sum_{j=1}^{\vartheta} \langle \boldsymbol{\zeta}_{ij}, \bar{\Phi}(\rho_{X}^{(i)},X_{ij}) \rangle,\] which implies that \[\mathbb{E}[\Lambda(\widetilde{S}) |(\rho_{XY}^{(i)})_{i}] \leq 8\sqrt{ 2 }M \mathbb{E}_{\left[ X_{ij} \sim \rho_{X}^{(i)} \right]_{i}} \mathbb{E}\left[ \sup_{\bar{\Phi}\in \mathscr{T}_{M}(\mathcal{H}_{\mathrm{T}_{n}})} \frac{1}{\sqrt{ N\vartheta }}Z_{\bar{\Phi}} \Bigg| (X_{ij})_{i,j}\right].\] For any \(\bar{\Phi}, \bar{\Phi}' \in \mathscr{T}_{M}(\mathcal{H}_{\mathrm{T}_{n}})\), \[\mathbb{E} [ \exp(v (Z_{\bar{\Phi}}-Z_{\bar{\Phi}'})) |(X_{ij})_{i,j}] \leq \exp(v^{2} d _{\vartheta}(\bar{\Phi},\bar{\Phi}')^{2}/2), \forall v \in \mathbb{R}\] where \[d_{\vartheta}(\bar{\Phi}, \bar{\Phi}'):= \| \bar{\Phi}-\bar{\Phi}' \|_{L^{2}({P}_{\vartheta})}=\left( \frac{1}{N\vartheta} \sum_{i=1}^{N}\sum_{j=1}^{\vartheta}\| \bar{\Phi}(\rho_{X}^{(i)},X_{ij})-\bar{\Phi}'(\rho_{X}^{(i)},X_{ij}) \|_{2}^{2} \right)^{\frac{1}{2}}.\] Then, conditioned on \((X_{ij})_{i,j}\), \(Z_{\bar{\Phi}}\) is a subgaussian process indexed by \(\bar{\Phi} \in \mathscr{T}_{M}(\mathcal{H}_{\mathrm{T}_{n}})\) with respect to \(d_{\vartheta}\). It follows by the Dudley Integral [@wainwright_high-dimensional_2019] that \[\mathbb{E} \left[\sup_{\bar{\Phi}\in \mathscr{T}_{M}(\mathcal{H}_{\mathrm{T}_{n}})}Z_{\bar{\Phi}}\Bigg|(X_{ij})_{i,j}\right] \leq 32\int ^{2M}_{0} \sqrt{ \log \mathrm{N}(u, \mathscr{T}_{M}(\mathcal{H}_{\mathrm{T}_{n}}),d_{\vartheta}) } \, du.\] It follows that \[\begin{align}&\mathbb{E}[\Lambda(\widetilde{S})|(\rho_{XY}^{(i)})_{i}] \leq \frac{256\sqrt{ 2 }M}{\sqrt{ N\vartheta }} \mathbb{E}_{[X_{ij} \sim \rho_{X}^{(i)}]_{i}}\left( \int _{0}^{2M} \sqrt{ \log \mathrm{N}(u, \mathcal{H}_{\mathrm{T}_{n}}, d_{\hat{\rho}_{\vartheta}}) } \, du \right) \\ & \leq \frac{256\sqrt{ 2 }M}{\sqrt{ N\vartheta }} \mathbb{E}_{[ X_{ij} \sim \rho_{X}^{(i)}]_{i}} \left( \int _{0}^{2M} \sqrt{ \underbrace{ 100nd^{2}m^{2} }_{ \varrho_{1} }\log\left(1+ \frac{8c_{6}C_{F}C_{\mathcal{B}}^{2}d^{2}\| \hat{X} \|_{2}}{u} \right)+ \underbrace{ 600 c_{5}nd^{2}m^{2}\tilde{m}^{2}\log(c_{4}m\tilde{m}) }_{ \varrho_{2} } } \, du \right) \\ &\leq \frac{256\sqrt{ 2 }M}{\sqrt{ N\vartheta }} \mathbb{E}_{[X_{ij} \sim \rho_{X}^{(i)}]_{i}} \left( 2M\sqrt{ \varrho_{2} }+ \sqrt{ \varrho_{1} }\int _{0}^{2M} \sqrt{ \log\left( 1+ \frac{8c_{6}C_{F}C_{\mathcal{B}}^2d^{2}\| \hat{X} \|_{2}}{u} \right) }\, du \right) \\ & \leq \frac{256\sqrt{ 2 }M}{\sqrt{ N \vartheta }} \mathbb{E}_{[X_{ij} \sim \rho _{X}^{(i)}]_{i}} \left( 2M \sqrt{ \varrho_{2} }+ \sqrt{ \varrho_{1} }\sqrt{ 8c_{6}C_{F}C_{\mathcal{B}}^2d^{2}\| \hat{X} \|_{2} } \int _{0}^{2M} u^{-\frac{1}{2}}\, du \right) \\ &= \frac{256\sqrt{ 2 }M}{\sqrt{ N\vartheta }}\left( 2M\sqrt{ \varrho_{2} }+ 8\sqrt{ \varrho_{1}c_{6}C_{F}C_{\mathcal{B}}^2d^{2}M }\,\, \mathbb{E}_{[X_{ij} \sim \rho_{X}^{(i)}]_{i}}\sqrt{ \| \hat{X} \|_{2} } \right) \end{align}\] where \[\mathbb{E}_{[X_{ij} \sim \rho _{X}^{(i)}]_{i}}\sqrt{ \| \hat{X} \|_{2} }\leq \sqrt{ \mathbb{E}_{[X_{ij}\sim \rho _{X}^{(i)}]_{i}} \| \hat{X} \|_{2} }= \sqrt{ 9+\mathbb{E} \sqrt{ \frac{1}{N\vartheta} \sum_{i=1}^{N} \sum_{j=1}^{\vartheta} \| X_{ij} \|_{2}^{2}} }\leq 9+ C_{\mathcal{B}}^{\frac{1}{2}}.\] Then we can obtain that \[\mathbb{E}[\Lambda(\widetilde{S})|(\rho_{XY}^{(i)})_{i}] \leq \frac{C_{M,\mathcal{B},d}}{\sqrt{ N\vartheta }} \sqrt{ n }m\tilde{m}^{2}\] with \(C_{M,\mathcal{B},d}=256\sqrt{ 2 }M\max\left\{ 20dM\sqrt{ 6c_{5} }, 80d^2(9+C_{\mathcal{B}}^{1/2})\sqrt{c_6C_FC_{\mathcal{B}}^2M} \right\}\).

Then we have \[\begin{align} \label{ineq:e2} \mathbb{P} \left\{ \sup_{\Phi \in \mathcal{H}_{\mathrm{T}_{n}}} \mathcal{E}_{2}(\mathscr{T}_{M}(\Phi)) > \epsilon + C_{M,\mathcal{B},d} \frac{\sqrt{ n }m\tilde{m}^{2}}{\sqrt{ N\vartheta }} \middle| \rho_{XY}^{(1)},\dots, \rho_{XY}^{(N)} \right\} \leq \exp\left( - \frac{(N\vartheta)\epsilon^{2}}{32M^{4}} \right). \end{align}\tag{23}\]

Similarly, for each \(\Phi \in \mathcal{H}_{\mathrm{T}_{n}}\), we define \[\tilde{\Lambda}_{\Phi}(\widetilde{S})=\frac{1}{N\vartheta}\sum_{i=1}^{N}\sum_{j=1}^{\vartheta} \Big(\| \Phi(\rho_{X}^{(i)},X_{ij})-Y_{ij} \|_{2}^{2}- \mathbb{E}\big[\| \Phi(\tilde{X})-Y \|_{2}^{2}| \rho_{XY}^{(i)} \big] \Big).\] Similarly, we have \[\left| \tilde{\Lambda}_{\Phi}(\widetilde{S}) - \tilde{\Lambda}_{\Phi}(\widetilde{S}^{\backslash (i,j)}) \right| \leq \frac{1}{N\vartheta} \left| \| \Phi(\rho_{X}^{(i)},X_{ij})-Y_{ij} \|_{2}^{2}- \| \Phi(\rho_{X}^{(i)}, X'_{ij})-Y'_{ij} \|_{2}^{2} \right|\leq \frac{4(M+\| \Phi \|_{C(\Omega _{\mathcal{B}})} )^{2}}{N\vartheta} .\] Then by Azuma-McDiarmind’s inequality, we can derive that \[\begin{align} \label{ineq:e22} \mathbb{P}\{ \mathcal{E}'_{2}(\Phi) > \epsilon | \rho_{XY}^{(1)},\dots, \rho_{XY}^{(N)} \} \leq \exp \left\{ -\frac{(N\vartheta)\epsilon^{2}}{8(M+\| \Phi \|_{C(\Omega _{\mathcal{B}})} )^{4}} \right\}. \end{align}\tag{24}\]

5.2.5 Second-Stage Sampling Error with Accessible Context↩︎

Now, we estimate the sampling error with accessible context information, i.e., the empirical distributions. We have \[\begin{align}&\quad\sup_{\Phi \in \mathcal{H}_{\mathrm{T}_{n}}}\left| \mathcal{E}_{3}(\mathscr{T}_{M}(\Phi)) \right|\\&= \sup_{\Phi \in\mathcal{H}_{\mathrm{T}_{n}}}\left | \frac{1}{N\vartheta} \sum_{i=1}^{N} \sum_{j=1}^{\vartheta}\Big(\| \mathscr{T}_{M}(\Phi)(\rho_{X}^{(i)}, X_{ij})-Y_{ij} \|_{2}^{2} - \| \mathscr{T}_{M}(\Phi)(\hat{\rho}_{X}^{(i)}, X_{ij})-Y_{ij} \|_{2}^{2} \Big) \right|\\& \leq \sup_{\Phi \in\mathcal{H}_{\mathrm{T}_{n}}}\frac{1}{N\vartheta} \sum_{i=1}^{N} \sum_{j=1}^{\vartheta} 4M \left\| \Phi(\rho_{X}^{(i)},X_{ij})- \Phi(\hat{\rho}_{X}^{(i)},X_{ij}) \right\|_{2} \\ & \leq \sup_{\Phi \in\mathcal{H}_{\mathrm{T}_{n}}} \frac{4M}{N} \sum_{i=1}^{N} \left( \| \alpha \|_{1} \max_{1\leq j'\leq n} \sum_{p,q=1}^{m(n)} \left\| \int_{\mathcal{X}} \phi _{p,\tilde{m}(n)}(x)A_{p,q}^{(j')}x \, d \rho_{X}^{(i)}-\int_{\mathcal{X}} \phi _{p,\tilde{m}(n)}(x)A_{p,q}^{(j')}x \, d\hat{\rho}_{X}^{(i)} \right\|_{2} \right) \\ &\leq \sup_{\phi \in \mathcal{N N}(\Theta _{\tilde{m}})} \frac{8MC_{F}}{N} \sum_{i=1}^{N} m\sqrt{ d } \max_{1\leq p\leq m} \left\|\int_{\mathcal{X}} \phi _{p,\tilde{m}(n)}(x)x \, d\rho_{X}^{(i)}- \int _{\mathcal{X}}\phi _{p,\tilde{m}(n)}(x)x \, d\hat{\rho}_{X}^{(i)} \right\|_{2} \\& \leq \frac{8MC_{F}\sqrt{ d }m}{N}\sum_{i=1}^{N} \underbrace{ \sup_{\phi \in \mathcal{N N}(\Theta _{\tilde{m}})} \left\| \int _{\mathcal{X}}\phi(x)x \, d\rho_{X}^{(i)}-\int _{\mathcal{X}}\phi(x) x\, d\hat{\rho}_{X}^{(i)} \right\|_{2} }_{ =:\mathcal{V}^{(i)}(\hat{\rho}_{X}^{(i)}) } \\& \leq 8MC_{F} \sqrt{ d }m \max_{1 \leq i \leq N} \mathcal{V}^{(i)}(\hat{\rho}_{X}^{(i)}). \end{align}\] Then for \(x=(x_{1},\dots,x_{\vartheta}) \in \mathcal{X}^{\vartheta}\) and the samples \((X_{i 1},\dots, X_{i \vartheta})\) in \(\hat{\rho}_{X}^{(i)}\), we define \[\begin{align} \mathcal{V}_{j}^{(i)}(\hat{\rho}_{X}^{(i)})(x)&= \mathcal{V}^{(i)}(\delta[x_{1},\dots, x_{j-1}, X_{ij}, x_{j+1},\dots,x_{\vartheta}])\\&\quad\quad- \mathbb{E}_{X'_{ij} \sim \rho_{X}^{(i)}}(\mathcal{V}^{(i)}(\delta[x_{1},\dots, x_{j-1}, X'_{ij},x_{j+1},\dots, x_{\vartheta}])) \end{align}\] for \(1 \leq j \leq \vartheta\) where \(\delta[S]\) is defined as the empirical distribution generated by the dataset \(S\).

We easily obtain that \[\begin{align}& \quad\left|\mathcal{V}_{j}^{(i)}(\hat{\rho}_{X}^{(i)})(x)\right|\\&= \left|\mathbb{E}_{X_{ij}'\sim \rho_{X}^{(i)}}\Big(\mathcal{V}^{(i)}(\delta[x_{1},\dots, x_{j-1},X_{ij}, x_{j+1},\dots, x_{\vartheta}])- \mathcal{V}^{(i)}(\delta[x_{1},\dots,x_{j-1}, X_{ij}', x_{j+1},\dots, x_{\vartheta}])\Big)\right|\\& \leq \mathbb{E}_{X_{ij}'\sim \rho_{X}^{(i)}} \Biggl| \sup_{\phi \in \mathcal{N N}(\Theta _{\tilde{m}})}\left\| \frac{1}{\vartheta}\left( \sum_{j' \neq j}\phi(x_{j'})x_{j'}+\phi(X_{ij})X_{ij} \right)- \mathbb{E}_{\rho_{X}^{(i)}}(\phi(X)X ) \right\|_{2} \\& \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,- \sup_{\phi \in \mathcal{N N}(\Theta _{\tilde{m}})} \left\| \frac{1}{\vartheta}\left( \sum_{j' \neq j} \phi(x_{j'})x_{j'}+\phi(X_{ij}')X_{ij}'\right)- \mathbb{E}_{\rho_{X}^{(i)}}(\phi(X)X) \right\|_{2} \Biggr| \\&\leq \mathbb{E}_{X_{ij}' \sim \rho_{X}^{(i)}} \left( \sup_{\phi \in \mathcal{N N}(\Theta _{\tilde{m}})} \frac{1}{\vartheta}\left\| \phi(X_{ij})X_{ij}- \phi(X_{ij}')X_{ij}' \right\|_{2} \right)\\ & \leq \mathbb{E}_{X_{ij}' \sim \rho_{X}^{(i)}} \left( \sup_{\phi \in \mathcal{N N}(\Theta _{\tilde{m}})} \frac{1}{\vartheta} (\| \phi(X_{ij})X_{ij} \|_{2}+ \| \phi(X_{ij}')X_{ij}' \|_{2} ) \right)\\ &\leq \frac{1}{\vartheta} (\| X_{ij} \|_{2} + \mathbb{E}_{X_{ij}' \sim \rho_{X}^{(i)}} \| X_{ij}' \|_{2} ) \leq \frac{1}{\vartheta} (\| X_{ij} \|_{2}+\sqrt{ C_{\mathcal{B}}} ). \end{align}\] For each \(\rho_{X}^{(i)} \in \mathcal{B}_{2,b}(\mathcal{X})\), we have the ratio condition that \(\| \omega _{\kappa }(\rho_{X}^{(i)})\|_{L^{\gamma}(\rho _{\kappa})}<\infty\). Then for \(X_{ij} \sim \rho_{X}^{(i)}\) and any \(p\geq 1\), we have \[\begin{align}\Big(\mathbb{E}_{\rho_{X}^{(i)}} \| X_{ij} \|_{2}^{p}\Big)^{\frac{1}{p}}&= \left( \int _{\mathcal{X}} \| x \|_{2}^{p} \cdot \omega _{\kappa }(\rho_{X}^{(i)})(x)\, d\rho _{\kappa}\right)^{\frac{1}{p}} \leq \| \omega _{\kappa }(\rho_{X}^{(i)})\|_{L^{\gamma}(\rho _{\kappa})}^{\frac{1}{p}} (\mathbb{E}_{\rho _{\kappa}} \| X \|_{2}^{p\gamma'})^{\frac{1}{p\gamma'}} \\ & \leq (1+ \| \omega _{\kappa }(\rho_{X}^{(i)})\|_{L^{\gamma}(\rho _{\kappa})}) (\mathbb{E}_{\rho _{\kappa}} \| X \|_{2}^{p\gamma'} )^{\frac{1}{p\gamma'}}\end{align}\] with \(\gamma' = \frac{\gamma}{\gamma-1}\). For \(X \sim \rho _{\kappa}\), \(\| X \|_{2}\) is a norm subgaussian random variable [@jin2019short] such that \((\mathbb{E}_{\rho _{\kappa}}\| X \|_{2}^{p})^{\frac{1}{p}}\leq c\kappa\sqrt{ d p }\) for any \(p \geq 1\) where \(c\) is an absolute constant. Then we have \[\begin{align} \Big(\mathbb{E}_{\rho_{X}^{(i)}} \| X_{ij} \|_{2}^{p}\Big)^{\frac{1}{p}} \leq c\kappa\sqrt{ \gamma' }\big(1+ \left\| \omega _{\kappa }(\rho_{X}^{(i)})\right\|_{L^{\gamma}(\rho _{\kappa})}\big)\sqrt{ p } \end{align}\] for any \(p\geq 1\). We define the subgaussian norm [@wainwright_high-dimensional_2019] for a random variable \(Z\) as \(\require{upgreek} \| Z \|_{\uppsi_{2}}= \sup_{p\geq 1} \frac{(\mathbb{E} \left| Z \right|^{p})^{\frac{1}{p}}}{\sqrt{ p }}\). Then \(\left\| X_{ij} \right\|_{2}\) is a subgaussian random variable with \(\require{upgreek} \left\| \| X_{ij} \|_{2} \right\|_{\uppsi_{2}}\leq c\kappa\sqrt{ \gamma' }(1+\| \omega _{\kappa }(\rho_{X}^{(i)})\|_{L^{\gamma}(\rho _{\kappa})})\). It also implies that for any \(x \in X^{\vartheta}\), \(\mathcal{V}_{j}^{(i)}(\hat{\rho}_{X}^{(i)})(x)\) is also a subgaussian random variable with \[\require{upgreek} \left\| \mathcal{V}_{j}^{(i)}(\hat{\rho}_{X}^{(i)})(x) \right\|_{\uppsi_{2}}\leq \frac{1}{\vartheta}\Big(\left\| \| X_{ij} \|_{2} \right\|_{\uppsi_{2}}+ \sqrt{ C_{\mathcal{B}}}\Big),\] because for any \(p\geq 1\), \[\begin{align} \Big(\mathbb{E}_{X_{ij}\sim \rho_{X}^{(i)}} \left| \mathcal{V}_{j}^{(i)}(\hat{\rho}_{X}^{(i)})(x) \right|^{p}\Big)^{\frac{1}{p}} \leq \frac{1}{\vartheta} \left[ (\mathbb{E}_{\rho_{X}^{(i)}}\| X_{ij} \|_{2}^{p})^{\frac{1}{p}}+ \sqrt{ C_{\mathcal{B}}} \right] \end{align}\] by Minkowski inequality. Then by Theorem 3 in [@maurer2021concentration], we have for any \(\epsilon>0\), \[\require{upgreek} \mathbb{P}\{ \mathcal{V}^{(i)}(\hat{\rho}_{X}^{(i)})- \mathbb{E}\mathcal{V}^{(i)}(\hat{\rho}_{X}^{(i)}) > \epsilon \} \leq \exp \left( - \frac{\vartheta\epsilon^{2}}{ \uppsi_{2}(\rho_{X}^{(i)})} \right)\] where \[\require{upgreek} \uppsi_{2}(\rho_{X}^{(i)})= 32e\Big(c\kappa\sqrt{ \gamma' }(1+\| \omega _{\kappa }(\rho_{X}^{(i)})\|_{L^{\gamma}(\rho _{\kappa})})+\sqrt{ C_{\mathcal{B}}}\Big)^{2}.\]

We also have \[\begin{align}\mathbb{E}\mathcal{V}^{(i)}(\hat{\rho}_{X}^{(i)})&= \mathbb{E}_{X_{ij} \sim P_{X}^{(i)}}\sup_{\phi \in \mathcal{N N}(\Theta _{\tilde{m}})} \left\| \frac{1}{\vartheta} \sum_{j=1}^{\vartheta} \phi(X_{ij})X_{ij}- \mathbb{E}_{P_{X}^{(i)}}(\phi(X)X) \right\|_{2}\\&\leq \mathbb{E}_{X_{ij},X_{ij}'\overset{i.i.d}{\sim}P_{X}^{(i)}} \sup_{\phi \in \mathcal{NN}(\Theta _{\tilde{m}})} \left\| \frac{1}{\vartheta} \sum_{j=1}^{\vartheta} [\phi(X_{ij})X_{ij}-\phi(X_{ij}')X_{ij}'] \right\|_{2} \\& =\frac{1}{\vartheta}\mathbb{E}_{X_{ij},X'_{ij} \overset{i.i.d}{\sim} P_{X}^{(i)}} \mathbb{E}_{\zeta _{ij}} \sup_{ \phi \in \mathcal{N N}(\Theta _{\tilde{m}})} \left\| \sum_{j=1}^{\vartheta} \zeta _{ij}[\phi(X_{ij})X_{ij}-\phi(X'_{ij})X'_{ij}] \right\|_{2} \\&\leq \frac{2}{\vartheta} \mathbb{E}_{X_{ij}} \mathbb{E}_{\zeta _{ij}}\sup_{\phi \in \mathcal{N N}(\Theta _{\tilde{m}})} \left\|\sum^{\vartheta}_{j=1} \zeta _{ij} \phi(X_{ij})X_{ij} \right\|_{2} \\ &= \frac{2}{\vartheta} \mathbb{E}_{X_{ij}} \mathbb{E}_{\zeta _{ij}} \sup_{\phi \in \mathcal{N N}(\Theta _{\tilde{m}})} \sup_{ \mathrm{u} \in S^{d-1}} \left( \sum_{j=1}^{\vartheta} \zeta _{ij}\phi(X_{ij})\mathrm{u}^{T}X_{ij}\right) \\&=\frac{2}{\vartheta} \mathbb{E}_{X_{ij}} \mathbb{E}_{\zeta _{ij}} \sup_{f \in \mathrm{U}} \left( \sum_{j=1}^{\vartheta} \zeta _{ij} f(X_{ij}) \right) \end{align}\] where \((\zeta _{ij})_{j=1}^{\vartheta}\) are independent Rademacher random variables and \[\mathrm{U}:= \{ f: f(x)=\phi(x)\mathrm{u}^{T}x \text{ with } \phi \in \mathcal{N N}(\Theta _{\tilde{m}}), \mathrm{u} \in S^{d-1} \}.\] We define a family of zero-mean random variables index by \(f \in \mathrm{U}\) as \[Z_{f}^{(i)}:= \frac{1}{\sqrt{ \vartheta }} \sum_{j=1}^{\vartheta}\zeta _{ij}f(X_{ij}),\] which implies that \[\mathbb{E} \mathcal{V}^{(i)}(\hat{\rho}_{X}^{(i)})\leq \mathbb{E}_{X_{ij}} \mathbb{E}\left[ \sup_{f \in \mathrm{U}} \frac{1}{\sqrt{ \vartheta }} Z_{f}^{(i)}\middle| (X_{ij})_{j} \right].\] For any \(f,f' \in \mathrm{U}\), \[\mathbb{E}[\exp(v(Z_{f}^{(i)}- Z_{f'}^{(i)}))| (X_{ij})_{i,j}] \leq \exp (v^{2}d_{\vartheta}^{(i)}(f,f') ^{2}/2), \,\forall v \in \mathbb{R}\] where \[d_{\vartheta}^{(i)}(f,f'):= \left( \frac{1}{\vartheta} \sum_{j=1}^{\vartheta} (f(X_{ij})-f'(X_{ij}))^{2} \right)^{\frac{1}{2}}.\] Then, conditioned on \((X_{ij})_{j}\), \(Z_{f}^{(i)}\) is a subgaussian process indexed by \(f \in \mathrm{U}\) with respect to \(d_{\vartheta}^{(i)}\). It’s easy to see that for any \(f,f' \in \mathrm{U}\), \[\begin{align} d_{\vartheta}^{(i)}(f,f')&=\left( \frac{1}{\vartheta} \sum_{j=1}^{\vartheta}\Big(\phi _{f}(X_{ij})\mathrm{u}_{f}^{T}X_{ij}- \phi _{f'}(X_{ij})\mathrm{u}_{f'}^{T}X_{ij}\Big)^{2} \right)^{\frac{1}{2}} \leq 2 \sqrt{ \frac{1}{\vartheta} \sum_{j=1}^{\vartheta} \left\| X_{ij} \right\|_{2}^{2} }=:2M_{i}. \end{align}\] If \(\left\| \mathrm{u}_{f}- \mathrm{u}_{f'} \right\|_{2} \leq \epsilon\) and parameters in \(\phi _{f}\) and \(\phi _{f'}\) satisfy (20 ), \[\begin{align} d_{\vartheta}^{(i)}(f,f') &\leq \left( \frac{1}{\vartheta}\sum_{j=1}^{\vartheta} \Big(\phi _{f}(X_{ij})\mathrm{u}_{f}^{T}X_{ij}- \phi _{f'}(X_{ij})\mathrm{u}_{f}^{T}X_{ij}\Big)^{2} \right)^{\frac{1}{2}} \\ &\,\,\,\,\,\,\,\,\,\,+ \left( \frac{1}{\vartheta}\sum_{j=1}^{\vartheta} \Big(\phi _{f'}(X_{ij})\mathrm{u}_{f}^{T}X_{ij}- \phi _{f'}(X_{ij})\mathrm{u}_{f'}^{T}X_{ij}\Big)^{2} \right)^{\frac{1}{2}} \\ & \leq \left( \frac{1}{\vartheta} \sum_{j=1}^{\vartheta}\Big(\phi _{f}(X_{ij})-\phi _{f'}(X_{ij})\Big)^{2}\left\| X_{ij} \right\|_{2}^{2} \right)^{\frac{1}{2}}+ M_{i} \left\| \mathrm{u}_{f}- \mathrm{u}_{f'} \right\|_{2} \\& \leq \left( \frac{1}{\vartheta} \sum_{j=1}^{\vartheta}\Big(192d(2+\| X_{ij} \|_{\infty} )[c_{4}\tilde{m}]^{3c_{5}\tilde{m}^{2}}\epsilon\Big)^{2} \| X_{ij} \|_{2}^{2} \right)^{\frac{1}{2}} + M_{i} \epsilon \\ & \leq \left( M_{i}+192d(c_4\tilde{m})^{3c_{5}\tilde{m}^{2}}\sqrt{ \frac{1}{\vartheta} \sum_{j=1}^{\vartheta}(8\| X_{ij} \|_{2}^{2} +2\| X_{ij} \|_{2}^{4} ) } \right) \epsilon. \end{align}\] Then the covering number \[\begin{align} \mathrm{N}(\tilde{\epsilon}, \mathrm{U}, d_{\vartheta}^{(i)}) & \leq \left( 1+ \frac{(c_{2}'\tilde{m})^{c_{3}'\tilde{m}^{2}}}{\epsilon} \right)^{96d^{2}\tilde{m}^{2}}\left( 1+ \frac{2}{\epsilon} \right)^{d}\leq \left( 1+ \frac{(c_{2}'\tilde{m})^{c_{3}'\tilde{m}^{2}}}{\epsilon} \right)^{100d^{2}\tilde{m}^{2}} \\ & \leq \left( 1+ \frac{\Delta^{(i)}}{\tilde{\epsilon}} \right)^{100d^{2}\tilde{m}^{2}} (c_{6}\tilde{m})^{c_{7}\tilde{m}^{4}}, \end{align}\] where \(\Delta^{(i)}:= M_{i}+ \sqrt{ \frac{1}{\vartheta}\sum_{j=1}^{\vartheta}(8\| X_{ij} \|_{2}^{2}+2\| X_{ij} \|_{2}^{4}) }\), \(c_{6}=192d(c_{2}'+c_{4})\) and \(c_{7}=100(c_{3}'+3c_{5})d^{2}\).

Then by Dudley integral, we have \[\begin{align} &\mathbb{E}\left[ \sup_{f \in \mathrm{U}} Z_{f}^{(i)}\middle|(X_{ij})_{j} \right]\leq 32 \int _{0}^{2M_{i}} \sqrt{ \log \mathrm{N}(v, \mathrm{U, d_{\vartheta}^{(i)}}) } \, dv \\ \leq & \, 32 \int _{0} ^{2M_{i}} \sqrt{100d^{2}\tilde{m}^{2} \log \left( 1+\frac{\Delta^{(i)}}{v} \right) + c_{7}\tilde{m}^{4} \log(c_{6}\tilde{m}) } \, dv \\ \leq & \, 32 \left( 2M_{i} \tilde{m}^{2}\sqrt{ c_{7}\log(c_{6}\tilde{m}) } + 10d\tilde{m}\int _{0}^{2M_{i}} \sqrt{ \log\left( 1+ \frac{\Delta^{(i)}}{v} \right) }\, dv \right)\\\leq & \, 32 \left( 2M_{i} \tilde{m}^{2}\sqrt{ c_{7}\log(c_{6}\tilde{m}) } + 10d\tilde{m}\int _{0}^{2M_{i}} \sqrt{ \Delta^{(i)} } v^{-\frac{1}{2}} \, dv \right) \\ \leq & \, 32 \Big(2M_{i} \tilde{m}^{2}\sqrt{ c_{7}\log(c_{6}\tilde{m}) } + 20d\tilde{m}\sqrt{ 2M_{i} \Delta^{(i)} }\Big). \end{align}\] Then we have \[\begin{align} \mathbb{E} \mathcal{V}^{(i)}(\hat{\rho}_{X}^{(i)}) &\leq \frac{1}{\sqrt{ \vartheta }}\mathbb{E}_{X_{ij}} 32 \Big(2M_{i} \tilde{m}^{2}\sqrt{ c_{7}\log(c_{6}\tilde{m}) } + 20d\tilde{m}\sqrt{ 2M_{i} \Delta^{(i)} }\Big) \\ & = \frac{1}{\sqrt{ \vartheta }} \left(64\tilde{m}^{2}\sqrt{ c_{7}\log(c_{6}\tilde{m}) } \mathbb{E}_{X_{ij}}M_{i}+ 640d\tilde{m}\mathbb{E}_{X_{ij}}\sqrt{ 2M_{i}\Delta^{(i)} } \right) \end{align}\] where \(\mathbb{E}_{X_{ij}}M_{i}= \mathbb{E}_{X_{ij}}\sqrt{ \frac{1}{\vartheta}\sum_{j=1}^{\vartheta} \| X_{ij} \|_{2}^{2} } \leq \sqrt{ \frac{1}{\vartheta}\sum_{j=1}^{\vartheta} \mathbb{E}_{X_{ij}} \| X_{ij} \|_{2}^{2} }=\sqrt{ C_{\mathcal{B}}}\) and \[\begin{align} \mathbb{E}_{X_{ij}} \sqrt{ 2M_{i}\Delta^{(i)} }&= \mathbb{E}_{X_{ij}} \sqrt{ 2M_{i}\left( M_{i}+\sqrt{ \frac{1}{\vartheta}\sum_{j=1}^{\vartheta}(8\| X_{ij} \|_{2}^{2} +2\| X_{ij} \|_{2}^{4} ) } \right) } \\ & \leq \mathbb{E}_{X_{ij}} \sqrt{ 2M_{i} \left( M_{i} + \sqrt{ \frac{1}{\vartheta} \sum_{j=1}^{\vartheta}8\| X_{ij} \|_{2}^{2} }+ \sqrt{ \frac{1}{\vartheta}\sum_{j=1}^{\vartheta}2\| X_{ij} \|_{2}^{4} } \right) } \\ & = \mathbb{E}_{X_{ij}} \sqrt{ (2+4\sqrt{ 2 })M_{i}^{2} + 2\sqrt{ 2 }M_{i}\sqrt{ \frac{1}{\vartheta}\sum_{j=1}^{\vartheta}\| X_{ij} \|_{2}^{4} }} \\ & \leq \sqrt{ (2+4\sqrt{ 2 })\mathbb{E}_{X_{ij}}M_{i}^{2}+ 2\sqrt{ 2 } \sqrt{ \mathbb{E}_{X_{ij}}M_{i}^{2} } \sqrt{ \mathbb{E}_{X_{ij}}\left( \frac{1}{\vartheta}\sum_{j=1}^{\vartheta} \| X_{ij} \|_{2}^{4} \right) } } \\ & \leq \sqrt{ (2+4\sqrt{ 2 })C_{\mathcal{B}}+ 2\sqrt{ 2 }\sqrt{ C_{\mathcal{B}}}C_{\mathcal{B}}} \leq \sqrt{ 2+6\sqrt{ 2 } } C_{\mathcal{B}}^{\frac{3}{4}}. \end{align}\] It follows that \[\mathbb{E} \mathcal{V}^{(i)}(\hat{\rho}_{X}^{(i)}) \leq \frac{1}{\sqrt{ \vartheta }}\left( 64\sqrt{ C_{\mathcal{B}}}\tilde{m}^{2}\sqrt{ c_{7}\log(c_{6}\tilde{m}) }+ 640d\sqrt{ 2+6\sqrt{ 2 } }C_{\mathcal{B}}^{\frac{3}{4}}\tilde{m}\right)\leq \frac{c_{8}}{\sqrt{ \vartheta }}\tilde{m}^{2}\sqrt{ \log(\tilde{m}) }\] where \(c_{8}=64\sqrt{ C_{\mathcal{B}}c_{7}(\log c_{6}+1) }+ 640d\sqrt{ 2+6\sqrt{ 2 } }C_{\mathcal{B}}^{\frac{3}{4}}\).

Then we have \[\require{upgreek} \mathbb{P}\left\{ \mathcal{V}^{(i)}(\hat{\rho}_{X}^{(i)}) > \epsilon + \frac{c_{8}\tilde{m}^{2}\sqrt{ \log(\tilde{m}) }}{\sqrt{ \vartheta }} \right\} \leq \exp\left( - \frac{\vartheta\epsilon^{2}}{\uppsi_{2}(\rho_{X}^{(i)})} \right),\] and it follows that \[\require{upgreek} \begin{align} \mathbb{P}\left\{ \sup_{\Phi \in \mathcal{H}_{\mathrm{T}_{n}}} \left|\mathcal{E}_{3}(\mathscr{T}_{M}(\Phi))\right| > 8MC_{F}\sqrt{ d }m \left( \epsilon+ \frac{c_{8}\tilde{m}^{2}\sqrt{ \log(\tilde{m}) }}{\sqrt{ \vartheta }} \right) \middle| \rho_{X}^{(1)},\dots, \rho_{X}^{(N)} \right\} \\ \leq N \exp \left( - \frac{\vartheta \epsilon^{2}}{\max_{1\leq i \leq N}\uppsi_{2}(\rho_{X}^{(i)})} \right) \end{align}\] which is equivalent to the inequality that \[\require{upgreek} \label{ineq:e3} \begin{align} \mathbb{P}\left\{ \sup_{\Phi \in \mathcal{H}_{\mathrm{T}_{n}}} |\mathcal{E}_{3}(\mathscr{T}_{M}(\Phi))| > \epsilon + \frac{8c_{8}\sqrt{d}MC_F\tilde{m}^{2}m\sqrt{ \log(\tilde{m}) }}{\sqrt{ \vartheta }} \middle| \rho_{X}^{(1)},\dots, \rho_{X}^{(N)} \right\} \\\leq N \exp \left( - \frac{\vartheta \epsilon^{2}}{64M^{2}C_{F}^{2}dm^{2} \max_{1 \leq i \leq N}\uppsi_{2}(\rho_{X}^{(i)})} \right). \end{align}\tag{25}\]

Similarly, for any \(\Phi \in \mathcal{H}_{\mathrm{T}_{n}}\), we have both \(\| \Phi \|_{C(\Omega _{\mathcal{B}})}\) and \(\| \Phi \|_{C(\Omega)}\) uniformly bounded respectively. Then we have \[\begin{align}\mathcal{E}_{3}(\Phi) &=\frac{1}{N\vartheta}\sum_{i=1}^{N} \sum_{j=1}^{\vartheta} \Big(\| \Phi(\hat{\rho}_{X}^{(i)},X_{ij})-Y_{ij} \|_{2}^{2}- \| \Phi(\rho_{X}^{(i)},X_{ij})-Y_{ij} \|_{2}^{2} \Big) \\ & \leq \frac{1}{N \vartheta} \sum_{i=1}^{N} \sum_{j=1}^{\vartheta}(2M+\| \Phi \|_{C(\Omega _{\mathcal{B}})}+\| \Phi \|_{C(\Omega)} ) \left\| \Phi(\hat{\rho}_{X}^{(i)},X_{ij})- \Phi(\rho_{X}^{(i)},X_{ij}) \right\|_{2} \\ & \leq 4(M+\| \Phi \|_{C(\Omega)} )C_{F}\sqrt{ d }m \max_{1\leq i \leq N} \left\| \int _{\mathcal{X}} \phi _{\Phi}(x)x \, d\hat{\rho}_{X}^{(i)} - \int _{\mathcal{X}} \phi _{\Phi}(x) x\, d\rho_{X}^{(i)} \right\|_{2}, \end{align}\] which follows that \[\require{upgreek} \label{ineq:e33} \begin{align} &\mathbb{P} \left\{ \mathcal{E}'_{3} (\Phi) > \epsilon + \frac{4c_8 C_F\sqrt{d}(M+\| \Phi \|_{C(\Omega)} )\tilde{m}^2m\sqrt{\log(\tilde{m})}}{\sqrt{ \vartheta }} \middle|\rho_{X}^{(1)},\dots, \rho_{X}^{(N)} \right\}\\ \leq& N \exp \left( - \frac{\vartheta \epsilon^{2}}{16(M+\| \Phi \|_{C(\Omega)} )^{2}C_{F}^{2}dm^{2}\max_{1 \leq i \leq N}\uppsi_{2}(\rho_{X}^{(i)})} \right) \end{align}\tag{26}\]

Recall that for any \(\Phi \in \mathcal{H}_{\mathrm{T}_{n}}\), \[\begin{align} &\mathcal{E}((\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})))- \mathcal{E}(\Phi _{\mathcal{G}})= \left\| \mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})- \Phi _{\mathcal{G}} \right\|_{L^{2}(\nu_{\mathcal{G}})} ^{2} \\ \leq&\, \mathcal{E}_{1}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))+ \mathcal{E}'_{1}(\Phi)+ \mathcal{E}_{2}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))+ \mathcal{E}'_{2}(\Phi) +\mathcal{E}_{3}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))+\mathcal{E}'_{3}(\Phi)+ \mathcal{E}_{4}(\Phi). \end{align}\] Then combine all inequalities 21 22 23 24 25 26 , and by the union bound, for any \(\Phi \in \mathcal{H}_{\mathrm{T}_{n}}\) and \(\epsilon>0\) we have \[\require{upgreek} \begin{align} &\mathbb{P} \left\{ \| \mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})-\Phi _{\mathcal{G}}\|_{L^{2}(\pi)}^{2}> 2 \mathcal{E}_{4}(\Phi) + 2C_{M,\mathcal{B},d} \frac{\sqrt{ n }m \tilde{m}^{2}}{\sqrt{ N\vartheta }} + c_9(3M+\| \Phi \|_{C(\Omega)} ) \frac{\tilde{m}^{2}m\sqrt{\log(\tilde{m}) }}{\sqrt{ \vartheta }} + 12\epsilon \right\} \\ \leq &\, \mathrm{N}\left( \mathcal{H}_{\mathrm{T}_{n}}, \frac{\epsilon}{16M}, d_{\mathcal{B}_{2,b}(\mathcal{X})} \right) \exp \left\{ - \frac{3N\epsilon}{2048M^{2}} \right\}+ \exp \left\{ - \frac{N \epsilon^{2}}{2(3M+\| \Phi \|_{C(\Omega _{\mathcal{B}})} )^{2}\left( \mathcal{E}_{4}(\Phi)+ \frac{2}{3} \epsilon \right)} \right\}\\ &+ 2\exp \left\{ - \frac{(N\vartheta)\epsilon^{2}}{32(M+\| \Phi \|_{C(\Omega _{\mathcal{B}})} )^{4}} \right\}\\&+ 2\mathbb{E}_{P_{X}^{(i)} \overset{}{\sim}\mathcal{P_{G}^{X}}} N \exp \left\{ - \frac{\vartheta\epsilon^{2}}{64(M+\| \Phi \|_{C(\Omega)} )^{2}C_{F}^{2}d m^{2} \max_{1\leq i\leq N}\uppsi_{2}(\rho_{X}^{(i)})} \right\} \end{align}\] where \(\mathcal{E}_{4}(\Phi)= \| \Phi -\Phi _{\mathcal{G}}\|_{L^{2}(\nu_{\mathcal{G}})}^{2}\) and \(c_9=8c_{8}C_{F}\sqrt{ d }\). \(\blacksquare\)

5.3 Theorem 2: Generalization Bound for Linear Transformers↩︎

From the approximation in Theorem 1, for \(n \geq 3\), there exists a transformer \(\mathrm{T} \in \mathcal{H}_{\mathrm{T}_{n}}\) such that \[\| \mathrm{T}- \Phi _{\mathcal{G}}\|_{L^{2}(\nu_{\mathcal{G}})}\leq C_{*} \left( \left\lfloor \frac{n}{2} \right\rfloor \right)^{-\frac{1}{2}} \leq C_{*}'n^{-\frac{1}{2}} \text{ with } C_{*}'= 2 C_{*}\] and by the approximant construction, we have \(\| \mathrm{T} \|_{C(\Omega _{\mathcal{B}})} \leq \| \mathrm{T} \|_{C(\Omega)}\leq 2 C_{F}\sqrt{ d(1+C_{\mathcal{B}}) }=\mathcal{A}_{1}\). Apply the above oracle inequality with letting \(\Phi=\mathrm{T}\) and \(\require{upgreek} \overline{\uppsi_{2}(\rho_{X})}:= \frac{1}{N}\sum_{i=1}^{N}\uppsi_{2}(\rho_{X}^{(i)})\), and we obtain that \[\require{upgreek} \begin{align}&\mathbb{P} \left\{ \| \mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})- \Phi _{\mathcal{G}}\|_{L^{2}(\pi)}^{2} > 2C_{*}'^{2} n^{-1}+2C_{M,\mathcal{B},d} \frac{\sqrt{ n }m\tilde{m}^{2}}{\sqrt{ N\vartheta }}+ 8c_{8}C_{F}\sqrt{ d }(3M+\mathcal{A}_{1} ) \frac{\tilde{m}^{2}m\sqrt{\log(\tilde{m}) }}{\sqrt{ \vartheta }}+12\epsilon \right\} \\ \leq & \, \exp \left\{ 100d^{2}nm^{2}\log \left( 1+\frac{128MC_{d,F,\mathcal{B}}}{\epsilon } \right) + 600 c_{5}d^{2}nm^{2}\tilde{m}^{2}\log(c_{4}m\tilde{m}) - \frac{3N\epsilon}{2048M^{2}}\; \right\} \\ &+ \, \exp \left\{ - \frac{N\epsilon^{2}}{2(3M+\mathcal{A}_{1})^{2}\left( C_{*}'^{2}n^{-1}+ \frac{2}{3}\epsilon \right)} \right\} + 2\exp \left\{ - \frac{(N\vartheta)\epsilon^{2}}{32(M+\mathcal{A}_{1})^{4}} \right\} \\ &\, + \, 2\mathbb{E}_{P_{X}^{(i)} \sim\mathcal{P_{G}^{X}}} N \exp \left\{ - \frac{\vartheta\epsilon^{2}}{64(M+\mathcal{A}_{1})^{2}dC_{F}^{2}m^{2}N\overline{\uppsi_{2}(\rho_{X})}} \right\}. \end{align}\]

We follow the parameter selections in the approximation by letting \(m= \lceil n^{\frac{\gamma}{2(\gamma-1)\xi}}\rceil\) and \(\tilde{m}= \lceil (\frac{1}{2}+ \frac{\gamma}{4(\gamma-1)\xi})\log n \rceil\). It’s obtained that \[\begin{align} &\mathbb{P} \left\{ \| \mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})- \Phi _{\mathcal{G}}\|_{L^{2}(\pi)}^{2} > 2C_{*}'^{2}n^{-1} + \mathcal{A}_{2} \frac{n^{\frac{1}{2}+ \frac{\gamma}{2(\gamma-1)\xi}}(\log n)^{2}}{\sqrt{ N\vartheta }} + \mathcal{A}_{3} \frac{n^{\frac{\gamma}{2(\gamma-1)\xi}}(\log n)^{3}}{\sqrt{ \vartheta }} + 12 \epsilon \right\}\\ \leq & \, \exp \left\{ 200d^{2}n^{1+ \frac{\gamma}{(\gamma-1)\xi}} \log\left( 1+\frac{128MC_{d,F,\mathcal{B}}}{\epsilon} \right) + \mathcal{A}_{4}n^{1+\frac{\gamma}{(\gamma-1)\xi}}(\log n)^{3} - \frac{3N\epsilon}{2048M^{2}}\right\} \end{align}\] \[\require{upgreek} \begin{align} &+ \, \exp \left\{ - \frac{N\epsilon^{2}}{2(3M+\mathcal{A}_{1})^{2}\left( C_{*}'^{2}n^{-1}+ \frac{2}{3}\epsilon \right)} \right\}+ 2 \exp \left\{ - \frac{(N\vartheta)\epsilon^{2}}{32(M+\mathcal{A}_{1})^{4}} \right\} \\ & + \,2 \mathbb{E}_{P_{X}^{(i)} \sim \mathcal{P_{G}^{X}}} N\exp \left\{ - \frac{\vartheta\epsilon^{2}}{128d(M+\mathcal{A}_{1})^{2}C_{F}^{2} n^{\frac{\gamma}{(\gamma-1)\xi}}N \overline{\uppsi_{2}(\rho_{X})}} \right\} \end{align}\] where \(\mathcal{A}_{2}=\big( 1+ \frac{\gamma}{2(\gamma-1)\xi} \big)^{2}C_{M,\mathcal{B},d}\), \(\mathcal{A}_{3}=32(3M+\mathcal{A}_{1})C_{F}\sqrt{ dC_{\mathcal{B}}}\) and \[\mathcal{A}_{4}=\left( 1+ \frac{\gamma}{(\gamma-1)\xi} \right)\left[ \left( 1200c_{5}d^{2}\left( \frac{1}{2}+ \frac{\gamma}{4(\gamma-1)\xi} \right)^{2}+\log c_{4}\left( \frac{1}{2}+\frac{\gamma}{4(\gamma-1)\xi} \right)^{2} \right) \right].\]

If we take \(\epsilon \geq 2C_{*}'^{2}n^{-1}(\log n)^{3}\), it follows that \[\require{upgreek} \begin{align} &\mathbb{P}\left\{ \| \mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})- \Phi _{\mathcal{G}}\|_{L^{2}(\pi)}^{2} > 13\epsilon + \mathcal{A}_{2} \frac{n^{\frac{1}{2}+ \frac{\gamma}{2(\gamma-1)\xi}}(\log n)^{2}}{\sqrt{ N \vartheta }} +\mathcal{A}_{3} \frac{n^{\frac{\gamma}{2(\gamma-1)\xi}}(\log n)^{3}}{\sqrt{ \vartheta }} \right\} \\ \leq & \, \exp \left\{ 200d^{2} n^{1+ \frac{\gamma}{(\gamma-1)\xi}} \log \left(1+ \frac{64MC_{d,F,\mathcal{B}}}{C_{*}'^{2}}\, n \right)+ \mathcal{A}_{4} n^{1+ \frac{\gamma}{(\gamma-1)\xi}} (\log n )^{3} - \frac{3N\epsilon}{2048M^{2}} \right\} \\ &+ \, \exp \left\{ - \frac{3N\epsilon}{8(3M+\mathcal{A}_{1})^{2}} \right\} + 2 \exp \left\{ - \frac{(N\vartheta)\epsilon^{2}}{32(M+\mathcal{A}_{1})^{4}} \right\}\\ &+\,2\mathbb{E}_{P_{X}^{(i)} \sim \mathcal{P_{G}^{X}}} N\exp \left\{ - \frac{\vartheta\epsilon^{2}}{128d(M+\mathcal{A}_{1})^{2}C_{F}^{2} n^{\frac{\gamma}{(\gamma-1)\xi}}N \overline{\uppsi_{2}(\rho_{X})}} \right\}. \end{align}\] Take \(n= \lfloor \mathcal{K}_{1} N^{\frac{1}{2+ \gamma/[(\gamma-1)\xi]}} \rfloor\) with \(\mathcal{K}_{1}=\left( \min\left\{ \frac{3C_{*}'^{2}}{819200M^{2}d^{2}\left( 1+\log\left( \frac{64MC_{d,F,\mathcal{B}}}{C_{*}} \right) \right)} ,\frac{3C_{*}'^{2}}{4096M^{2}\mathcal{A}_{4}} \right\} \right)^{\frac{1}{2+\frac{\gamma \xi}{(\gamma-1)}}}\) and the second stage data size \(\vartheta\geq N\), then we have \[\require{upgreek} \begin{align} &\mathbb{P}\{ \| \mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})- \Phi _{\mathcal{G}}\|_{L^{2}(\pi)}^{2} > \mathcal{A}_{5} \epsilon \} \\ \leq &\, \exp \left\{ \frac{3N\epsilon}{8192M^{2}}+ \frac{3N\epsilon}{8192M^{2}}- \frac{3N\epsilon}{2048M^{2}} \right\}+ \exp \left\{ - \frac{3N\epsilon}{8(3M+\mathcal{A}_{1})^{2}} \right\} +\, 2\exp \left\{ - \frac{C_{*}'^{2}N\epsilon}{16\mathcal{K}_{1}(M+\mathcal{A}_{1})^{4}} \right\} \\ &+ \, 2 \mathbb{E}_{P_{X}^{(i)}\sim \mathcal{P_{G}^{X}}}N \exp \left\{ - \frac{{ \vartheta }\epsilon}{\mathcal{A}_{6}N^{ \frac{3(\gamma-1)\xi+2\gamma}{2(\gamma-1)\xi+\gamma}}\overline{\uppsi_{2}(\rho_{X})}} \right\} \\ \leq &\, 4 \exp \left\{ - \frac{N\epsilon}{\mathcal{A}_{7}} \right\}+ 2\mathbb{E}_{P_{X}^{(i)} \sim \mathcal{P_{G}^{X}}} N \exp \left\{ - \frac{ { \vartheta } \epsilon}{\mathcal{A}_{6}N^{\frac{3(\gamma-1)\xi+2\gamma}{2(\gamma-1)\xi+\gamma}}\overline{\uppsi_{2}(\rho_{X})}} \right\}, \end{align}\] where \[\mathcal{A}_{5}=13+ \frac{\mathcal{A}_{2}\mathcal{K}_{1}^{\frac{3}{2}+\frac{\gamma}{2(\gamma-1)\xi}}+ \mathcal{A}_{3} \mathcal{K}_{1}^{1+\frac{\gamma}{(\gamma-1)\xi}}}{2C_{*}'^{2}} , \, \mathcal{A}_{6}= 128d(M+\mathcal{A}_{1})^{2}C_{F}^{2}\mathcal{K}_{1}^{\frac{\gamma}{(\gamma-1)\xi}},\] and \(\mathcal{A}_{7}= \min \left\{ \frac{3}{3096M^{2}}, \frac{3}{8(3M+\mathcal{A}_{1})^{2}}, \frac{C_{*}'^{2}}{16\mathcal{K}_{1}(M+\mathcal{A}_{1})^{4}} \right\}\).

Take \(t= \mathcal{A}_{5}\epsilon\). Then when \(t \geq 2\mathcal{A}_{5}C_{*}'^{2}n^{-1}(\log n)^{3}\), we have \[\require{upgreek} \mathbb{P}\{ \| \mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})- \Phi _{\mathcal{G}}\|_{L^{2}(\nu_{\mathcal{G}})}^{2}> t \}\leq 4 \exp \left\{ - \frac{Nt}{\mathcal{A}_{5}\mathcal{A}_{7}} \right\}+ 2 \mathbb{E}_{\rho_{X}^{(i)}\sim \mathcal{P_{G}^{X}}}N \exp \left\{ - \frac{{ \vartheta }t}{\mathcal{A}_{5}\mathcal{A}_{6}N^{\frac{3(\gamma-1)\xi+2\gamma}{2(\gamma-1)\xi+\gamma}}\overline{\uppsi_{2}(\rho_{X})}} \right\}.\] It implies that \[\require{upgreek} \begin{align} &\mathbb{E}\{ \mathcal{E}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))- \mathcal{E}(\Phi _{\mathcal{G}}) \}=\mathbb{E}\| \mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})-\Phi _{\mathcal{G}}\|_{L^{2}(\nu_{\mathcal{G}})}^{2} = \int _{0}^{\infty} \mathbb{P}\{ \| \mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})- \Phi _{\mathcal{G}}\|_{L^{2}(\nu_{\mathcal{G}})}^{2} > t \} \, dt \\ =&\,\left( \int_{0}^{2\mathcal{A}_{5}C_{*}'^{2}n^{-1}(\log n)^{3}} +\int _{2\mathcal{A}_{5}C_{*}'^{2}n^{-1}(\log n)^{3}}^{\infty} \right)\, \mathbb{P}\{ \| \mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})-\Phi _{\mathcal{G}}\|_{L^{2}(\nu_{\mathcal{G}})}^{2} >t \} \, dt \\ \leq & \, 2\mathcal{A}_{5}C_{*}'^{2}n^{-1}(\log n)^{3}+ \int _{0}^{\infty} \mathbb{P} \{ \| \mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n})-\Phi _{\mathcal{G}}\|_{L^{2}(\nu_{\mathcal{G}})}^{2} >t \} \, d t \\ \leq & \, 2\mathcal{K}_{2} N^{- \frac{1}{2+ \gamma/[(\gamma-1)\xi]}} (\log N)^{3} + \int_{0}^{\infty} 4 \exp \left\{ - \frac{N^{\frac{1}{2+\gamma/[(\gamma-1)\xi]}}t}{\mathcal{A}_{5}\mathcal{A}_{7}} \right\} \, dt \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+2\mathbb{E}_{\rho_{X}^{(i)}\sim \mathcal{P_{G}^{X}}}N \int _{0}^{\infty} \exp \left\{ - \frac{{ \vartheta }t}{\mathcal{A}_{5}\mathcal{A}_{6}N^{\frac{3(\gamma-1)\xi+2\gamma}{2(\gamma-1)\xi+\gamma}}\overline{\uppsi_{2}(\rho_{X})}} \right\} \, dt \\=& \, 2\mathcal{K}_{2} N^{- \frac{1}{2+ \gamma/[(\gamma-1)\xi]}} (\log N)^{3} + 4 \mathcal{A}_{5}\mathcal{A}_{7} N^{- \frac{1}{2+ \gamma/[(\gamma-1)\xi]}} + 2 \mathcal{A}_{5} \mathcal{A}_{6} \frac{N^{\frac{5(\gamma-1)\xi+3\gamma}{2(\gamma-1)\xi+\gamma}}}{{ \vartheta }} \mathbb{E}_{\rho_{X}^{(i)}\sim \mathcal{P_{G}^{X}}} \Big(\overline{\uppsi_{2}(\rho_{X})}\Big) \end{align}\] where \(\mathcal{K}_{2}=4\mathcal{A}_{5}C_{*}'^{2}\mathcal{K}_{1}^{-1}\left( \log \mathcal{K}_{1}+ \frac{1}{2+\gamma/[(\gamma-1)\xi]} \right)^{3}\). Take \(\vartheta= N^{3}\) and we obtain that \[\require{upgreek} \begin{align} \mathbb{E} \{ \mathcal{E}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))-\mathcal{E}(\Phi _{\mathcal{G}}) \}\leq \left(2\mathcal{K}_{2}+4\mathcal{A}_{5}\mathcal{A}_{7}+2\mathcal{A}_{5}\mathcal{A}_{6}\mathbb{E}_{\rho_{X}^{(i)}\sim \mathcal{P_{G}^{X}}}\Big(\overline{\uppsi_{2}(\rho_{X})}\Big)\right)N^{- \frac{1}{2+ \gamma/[(\gamma-1)\xi]}} (\log N)^{3} \end{align}\] where \[\require{upgreek} \begin{align}\mathbb{E}_{\rho_{X}^{(i)} \sim \mathcal{P_{G}^{X}}}\Big(\overline{\uppsi_{2}(\rho_{X})}\Big)&= \mathbb{E}_{\rho_{X}^{(i)}\sim \mathcal{P_{G}^{X}}}\left( \frac{1}{N} \sum_{i=1}^{N} \uppsi_{2}(\rho_{X}^{(i)})\right)\\&=32e \, \mathbb{E}_{\rho_{X}^{(i)}\sim\mathcal{P_{G}^{X}}} \frac{1}{N}\sum_{i=1}^{N}\Big(c\kappa\sqrt{ \gamma' }(1+\| \omega _{\kappa }(\rho_{X}^{(i)})\|_{L^{\gamma}(\rho _{\kappa})})+\sqrt{ C_{\mathcal{B}}}\Big)^{2} \\& \leq 64e \,\mathbb{E}_{\rho_{X} \sim \mathcal{P_{G}^{X}}} \Big(c ^{2}\kappa^{2}\gamma'(1+\| \omega _{\kappa}(\rho_{X}) \|_{L^{\gamma}(\rho _{\kappa})} )^{2}+ C_{\mathcal{B}}\Big) \\ &\leq \, 64e(C_{\mathcal{B}}+2 c ^{2}\kappa^{2}\gamma')+ 128e \, \mathbb{E}_{\rho_{X}\sim\mathcal{P_{G}^{X}}}\| \omega _{\kappa}(\rho_{X}) \|^{2}_{L^{\gamma}(\rho _{\kappa})}\\&\leq \, 64 e (C_{\mathcal{B}}+2 c ^{2}\kappa^{2}\gamma'+ 2C_{\mathcal{G}}). \end{align}\] It follows that \[\mathbb{E}\{ \mathcal{E}(\mathscr{T}_{M}(\mathrm{T}_{\mathbb{S},n}))- \mathcal{E}(\Phi _{\mathcal{G}}) \}\leq \mathcal{K}_{3}N^{- \frac{1}{2+ \gamma/[(\gamma-1)\xi]}} (\log N)^{3}\] with \(\mathcal{K}_{3}= 2\mathcal{K}_{2}+4\mathcal{A}_{5}\mathcal{A}_{7}+128e\mathcal{A}_{5}\mathcal{A}_{6}(C_{\mathcal{B}}+ 2c ^{2}\kappa^{2} \gamma'+ 2C_{\mathcal{G}})\). \(\blacksquare\)

6 Context Embedding and Feature Mapping↩︎

Proof. Continuity: Recall that \(\Omega=\mathcal{B}_{2}(\mathcal{X})\times \mathcal{X}\) is a metric space equipped with \(d_{\Omega}\). Also observe that \[\begin{align} \left\| \mathrm{I}_{\boldsymbol{\lambda}}(\rho,x)-\mathrm{I}_{\boldsymbol{\lambda}}(\rho',x') \right\|_{\mathcal{H}_{\mathcal{F}}} &\leq \| \mathrm{I}_{\boldsymbol{\lambda}}(\rho,x)-\mathrm{I}_{\boldsymbol{\lambda}}(\rho',x) \|_{\mathcal{H}_{\mathcal{F}}} + \| \mathrm{I}_{\boldsymbol{\lambda}}(\rho',x) - \mathrm{I}_{\boldsymbol{\lambda}}(\rho',x') \|_{\mathcal{H}_{\mathcal{F}}} \\ & =\| K_{\boldsymbol{\lambda}}(\rho-\rho') \otimes k_{\boldsymbol{\lambda}}(x, \cdot) \|_{\mathcal{H}_{\mathcal{F}}} + \| K_{\boldsymbol{\lambda}}(\rho') \otimes(k_{\boldsymbol{\lambda}}(x, \cdot)-k_{\boldsymbol{\lambda}}(x', \cdot)) \|_{\mathcal{H}_{\mathcal{F}}}, \end{align}\] in which \[\begin{align} &\| k_{\boldsymbol{\lambda}}(x,\cdot)-k_{\boldsymbol{\lambda}}(x',\cdot) \|_{\mathcal{H}_{k_{\boldsymbol{\lambda}}}}^{2}= 2(1-\exp \{ -(x-x')^{T}\Sigma _{\boldsymbol{\lambda}}(x-x') \})\\&\leq 2(x-x')^{T}\Sigma _{\boldsymbol{\lambda}}(x-x')\leq 2\| \Sigma _{\boldsymbol{\lambda}} \|_{2}\| x-x \|_{2}^{2}, \end{align}\] and for any \(\tau \in \prod (\rho,\rho')\), \[\begin{align} &\| K_{\boldsymbol{\lambda}}(\rho-\rho') \|_{\mathcal{H}_{k_{\boldsymbol{\lambda}}}\otimes \mathbb{R}^{d}} = \left\| \int _{\mathcal{X} \times \mathcal{X}} (k_{\boldsymbol{\lambda}}(\cdot,y)y-k_{\boldsymbol{\lambda}}(\cdot,y')y' )\, d\rho(y)d \rho'(y') \right\|_{\mathcal{H}_{k_{\boldsymbol{\lambda}}}\otimes \mathbb{R}^{d}} \\ &\leq \int _{\mathcal{X} \times \mathcal{X}} \| k_{\boldsymbol{\lambda}}(\cdot,y)y-k_{\boldsymbol{\lambda}}(\cdot,y')y' \|_{\mathcal{H}_{k_{\boldsymbol{\lambda}}}\otimes \mathbb{R}^{d}} \, d\tau(y,y') \\ & \leq \int _{\mathcal{X} \times \mathcal{X}} \| k_{\boldsymbol{\lambda}}(\cdot,y)(y-y') \|_{\mathcal{H}_{k_{\boldsymbol{\lambda}}}\otimes \mathbb{R}^{d}} + \| (k_{\boldsymbol{\lambda}}(\cdot,y)-k_{\boldsymbol{\lambda}}(\cdot,y'))y' \|_{\mathcal{H}_{k_{\boldsymbol{\lambda}}}\otimes \mathbb{R}^{d}} \, d\tau(y,y') \\ &\leq \int _{\mathcal{X} \times \mathcal{X}} \| y-y' \|_{2} \, d\tau(y,y') + \int _{\mathcal{X} \times \mathcal{X}} \sqrt{ 2 }\| \Sigma _{\boldsymbol{\lambda}} \|_{2}^{\frac{1}{2}} \| y-y' \|_{2} \| y' \|_{2} \, d \tau(y,y') \\ &\leq \left( \int _{\mathcal{X} \times \mathcal{X}} \| y-y' \|_{2}^{2} \, d \tau(y,y') \right)^{\frac{1}{2}} + \sqrt{ 2 } \| \Sigma _{\boldsymbol{\lambda}} \|_{2}^{\frac{1}{2}} \left( \int _{\mathcal{X} \times \mathcal{X}} \| y-y' \|_{2}^{2} \, d \tau(y,y') \right)^{\frac{1}{2}} (\mathbb{E}_{\rho'}\| Y' \|_{2}^{2})^{\frac{1}{2}} \\ & \leq \left( 1+ \sqrt{ 2 } \| \Sigma _{\boldsymbol{\lambda}} \|_{2}^{\frac{1}{2}}(\mathbb{E}_{\rho'}\| Y' \|_{2}^{2})^{\frac{1}{2}} \right) \left( \int _{\mathcal{X} \times \mathcal{X}} \| y-y' \|_{2}^{2} \, d \tau(y,y') \right)^{\frac{1}{2}}. \end{align}\] Since the above inequality holds for any \(\tau \in \prod(\rho, \rho')\), it follows that \[\| K_{\boldsymbol{\lambda}}(\rho-\rho') \|_{\mathcal{H}_{k_{\boldsymbol{\lambda}}}\otimes \mathbb{R}^{d}} \leq (1+ \sqrt{ 2 } \| \Sigma _{\boldsymbol{\lambda}} \|_{2}^{\frac{1}{2}}(\mathbb{E}_{\rho'}\| Y' \|_{2}^{2})^{\frac{1}{2}})W_{2}(\rho,\rho')\] and that \[\begin{align} \| \mathrm{I}_{\boldsymbol{\lambda}}(\rho,x)-\mathrm{I}_{\boldsymbol{\lambda}}(\rho',x') \|_{\mathcal{H}_{\mathcal{F}}} &\leq \left( 1+ \sqrt{ 2 } \| \Sigma _{\boldsymbol{\lambda}} \|_{2}^{\frac{1}{2}}(\mathbb{E}_{\rho'}\| Y' \|_{2}^{2})^{\frac{1}{2}} \right)W_{2}(\rho,\rho')+ \sqrt{ 2 }\| \Sigma _{\boldsymbol{\lambda}} \|_{2}^{\frac{1}{2}} (\mathbb{E}_{\rho'}\| Y' \|_{2}^{2}) \| x-x' \|_{2} \\ &\leq (1+2\sqrt{ 2 }\| \Sigma _{\boldsymbol{\lambda}} \|_{2}^{\frac{1}{2}} (\mathbb{E}_{\rho'}\| Y' \|_{2}^{2})) d_{\Omega}((\rho,x), (\rho',x')). \end{align}\]

Injection: \(k_{\boldsymbol{\lambda}}(x,y)=g_{\boldsymbol{\lambda}}(x-y)= \exp \left\{ -\frac{1}{2}(x-y)^{T} \Sigma _{\boldsymbol{\lambda}}^{-1}(x-y) \right\}\) with \(\Sigma _{\boldsymbol{\lambda}}=\mathrm{diag}(2\lambda_{1}^{-2},\dots, 2\lambda _{d}^{-2})\succ 0\). For each \(1\leq j \leq d\), let \[\widehat{K_{\boldsymbol{\lambda}}^{(j)}(\rho)}(\omega)= \int _{\mathbb{R}^{d}} e^{ -i \omega^{T}y } K_{\boldsymbol{\lambda}}^{(j)}(\rho)(y) \, dy=\int _{\mathbb{R}^{d}}\int _{\mathbb{R}^{d}} e^{ -i\omega^{T}y } g_{\boldsymbol{\lambda}}(y-x) x^{(j)}\, d\rho(x) \, dy.\] By Fubini Theorem, we have \[\begin{align} \widehat{K_{\boldsymbol{\lambda}}^{(j)}(\rho)}(\omega)&=\int _{\mathbb{R}^{d}} \left[ \int _{\mathbb{R}^{d}} e^{ -i\omega^{T}y }g_{\boldsymbol{\lambda}}(y-x) \, dy \right] \,x^{(j)} d\rho(x) \\ &=(2\pi)^{\frac{d}{2}} \det(\Sigma _{\boldsymbol{\lambda}})^{\frac{1}{2}} e^{ -\frac{1}{2}\omega^{T}\Sigma _{\boldsymbol{\lambda}}\omega } \int _{\mathbb{R}^{d}}x^{(j)} e^{ -i\omega^{T}x } \, d \rho(x) \\&=(2\pi)^{\frac{d}{2}} \det(\Sigma _{\boldsymbol{\lambda}})^{\frac{1}{2}} e^{ -\frac{1}{2}\omega^{T}\Sigma _{\boldsymbol{\lambda}}\omega } \,\, i \partial _{j} \mathrm{F}(\rho)(\omega), \end{align}\] where \(\mathrm{F}(\rho)\) is Fourier transform of probability measure \(\rho\).

It follows that \(\widehat{K_{\boldsymbol{\lambda}}(\rho)}(\omega)=(2\pi)^{\frac{d}{2}} \det(\Sigma _{\boldsymbol{\lambda}})^{\frac{1}{2}} e^{ -\frac{1}{2}\omega^{T}\Sigma _{\boldsymbol{\lambda}}\omega }\,\, i \nabla \mathrm{F}(\rho)(\omega)\). Take \(\mu=\rho_{1}-\rho_{2}\) with \(\rho_1, \rho_2 \in \mathcal{B}_{2}(\mathcal{X})\). If \({K_{\boldsymbol{\lambda}}(\mu)}=0\), then \(K_{\boldsymbol{\lambda}}(\mu)(y)=0\) for any \(y \in \mathbb{R}^{d}\). It implies that \(\widehat{K_{\boldsymbol{\lambda}}(\mu)}\equiv0\) and \(\nabla \mathrm{F}({\mu})\equiv 0\). Note that \(\mathrm{F}({\mu})(0)=\mu(\mathcal{X})=\rho_{1}(\mathcal{X})-\rho_{2}(\mathcal{X})=0\). It can be obtained that \(\mathrm{F}({\mu})\equiv 0\). Then by the inversion of Fourier transform of measures, we have \(\rho_{1}=\rho_{2}\), which shows that \(K_{\boldsymbol{\lambda}}\) is an injective mapping on \(\mathcal{B}_{2}(\mathcal{X})\). It also follows that \(\mathrm{I}_{\boldsymbol{\lambda}}\) is injective since \(x \mapsto k_{\boldsymbol{\lambda}}(x,\cdot)\) is also an injective mapping. \(\blacksquare\)

7 Examples for Marginal Meta Probability Measure↩︎

Proof. Take \((\mu_n)_{}\) a sequence in \(\mathcal{G}(\mathrm{B},\mathrm{C})\) with \(\mu_n \to \mu\) in \((\mathcal{B}_{2}(\mathcal{X}), W_2)\). Denote \(\mathrm{K}\) the closed ball of radius B centered at zero. Then by Portmanteau Theorem, the weak convergence of measures implies that \(1=\limsup_{n \to \infty} \mu_n(\mathrm{K})\leq \mu(\mathrm{K}) \leq1\). Therefore, \(\mu(\mathrm{K})=1\).

Also by the weak convergence, we have \(\int \varphi d\mu = \lim_{n \to \infty} \int \varphi d \mu_n \leq \mathrm{C}\int \varphi d \nu\) for any \(\varphi \in C_c^+(\mathrm{K})\), where \(\nu\) is Lebesgue measure. Then by the density of function class \(C_c^+(\mathrm{K})\), we have \(\mu(E) \leq \mathrm{C}\nu(E)\) for any Borel set \(E \subset \mathrm{K}\), which follows that \(\mu\) is absolute continuous with respect to \(\nu\) and \(d \mu / d\nu \leq \mathrm{C}\) almost everywhere on \(\mathrm{K}\). It implies that \(\mu \in \mathcal{G}(\mathrm{B},\mathrm{C})\) and then \(\mathcal{G}(\mathrm{B},\mathrm{C})\) is closed in \((\mathcal{B}_{2}(\mathcal{X}),W_2)\).

It’s easy to obtain that \[\begin{align} \mathbb{E}_{\rho \sim \mathcal{P_{G}^{X}}} \| \omega _{\kappa}(\rho)\|^{2}_{L^{\gamma}(\rho _{\kappa})}&= \, \int _{\mathcal{G}(\mathrm{B},\mathrm{C})} \left( \int _{\mathrm{K}} \left( \frac{d\rho}{d\rho _{\kappa}} \right)^{\gamma} \, d\rho _{\kappa}\right)^{\frac{2}{\gamma}}\, d\mathcal{P_{G}^{X}}(\rho) \\& \leq \mathrm{C}^{2} (2\pi\kappa^2)^{\frac{(\gamma-1)d}{\gamma}} \exp \left( \frac{(\gamma-1)\mathrm{B}^{2}}{\gamma\kappa^{2}} \right).\end{align}\] \(\blacksquare\)

Proof. Since the convolution between \(\mu\) and \(\rho _{\tilde{\kappa}}\) can be considered as the probability distribution of random variable \(X+Z_{\tilde{\kappa}}\) with \(X \sim \mu\) and \(Z_{\tilde{\kappa}} \sim \text{gaussian distribution } \rho _{\tilde{\kappa}}\) independently, \(W_{2}(\mu_{1}*\rho _{\tilde{\kappa}}, \mu_{2}*\rho _{\tilde{\kappa}})\leq W_{2}(\mu_{1}, \mu _{2})\) by the coupling argument. Similarly for \((\mu_{1}, t_{1}), (\mu_{2}, t_{2}) \in \mathcal{B}_{2,b}(\mathcal{X}) \times[t_{0},T]\), we have \[W_{2}(\mu_{1}*\rho _{t_{1}}, \mu _{2}*\rho _{t_{2}})\leq W_{2}(\mu _{1}, \mu_{2})+W_{2}(\rho _{t_{1}},\rho _{t_{2}})\leq W_{2}(\mu_{1}, \mu_{2})+\sqrt{ d } \left| t_{1}-t_{2} \right|,\] which shows that \(\tilde{\mathrm{I}}: (\mu, \tilde{\kappa}) \mapsto \mu * \rho _{\tilde{\kappa}}\) is continuous. Then the meta probability in domain generalization framework can be defined with \(\mathcal{P}_{\mathcal{G}}^{\mathcal{X}}= (\tilde{\mathcal{P}}_{\mathcal{G}}^{\mathcal{X}} \times \mathrm{Uniform}[t_{0},T]) \circ \tilde{\mathrm{I}}^{-1}\). It’s easy to see that for any \(\mu*\rho _{\tilde{\kappa}} \in \mathcal{G}_{[t_{0},T]}(\mathrm{B})\), we have \[\begin{align} \mathbb{E}\| X+Z \|_{2}^{4} &\leq \mathbb{E} (2\| X \|_{2}^{2}+ 2\| Z \|_{2}^{2})^2=4(\mathbb{E}\| X \|_{2}^{4}+ \mathbb{E}\| Z \|_{2}^{4})+8(\mathbb{E}\| X \|_{2}^2)(\mathbb{E}\| Z \|_{2}^{2})\\&\leq 4(\mathrm{B}^4+d(d+2)T^4)+8d\mathrm{B}^{2}T^2, \end{align}\] and \[\begin{align} &\|\omega _{\kappa}(\mu*\rho _{\tilde{\kappa}})\|_{L^{\gamma}(\rho _{\kappa})}^{\gamma} = (2\pi\kappa^{2})^{\frac{d(\gamma-1)}{2}}\int _{\mathbb{R}^{d}} (\mu*\rho _{\tilde{\kappa}}(x))^{\gamma} \exp\left( \frac{\gamma-1}{2\kappa^{2}}\| x \|_{2}^{2} \right) \, dx \\=\,& (2\pi\kappa^{2})^{\frac{d(\gamma-1)}{2}} (2\pi\tilde{\kappa}^{2})^{-\frac{d\gamma}{2}} \int _{\mathbb{R}^{d}} \left( \int_{\| y \|_{2} \leq \mathrm{B} } \exp\left( - \frac{{\| x-y \|_{2}^{2}}}{2\tilde{\kappa}^{2}} \right) \, d\mu(y)\right)^{\gamma} \exp \left( \frac{{\gamma-1}}{2\kappa^{2}} \| x \|_{2}^{2} \right) \, dx \\=\, & (2\pi\kappa^{2})^{\frac{d(\gamma-1)}{2}} (2\pi\tilde{\kappa}^{2})^{-\frac{d\gamma}{2}} \int _{\mathbb{R}^{d}} \left( \int _{\| y \|_{2} \leq \mathrm{B} } \exp \left( \frac{2x^{T}y-\| y \|_{2}^{2} }{2\tilde{\kappa}^{2}} \right) \, d\mu(y)\right)^{\gamma}\exp\left( - \left( \frac{\gamma}{2\tilde{\kappa}^{2}}- \frac{{\gamma-1}}{2\kappa^{2}} \right)\| x \|_{2}^{2} \right) \, dx . \end{align}\]

It’s easy to see that \(\| \omega _{\kappa}(\mu* \rho _{\tilde{\kappa}}) \|_{L^{\gamma}(\rho _{\kappa})} <\infty\) if and only if \(v_{\tilde{\kappa}}:=\frac{\gamma}{2\tilde{\kappa}^{2}}- \frac{{\gamma-1}}{2\kappa^{2}}\) which is equivalent to the condition \(\tilde{\kappa}< \sqrt{ \frac{\gamma}{\gamma-1} }\kappa\). Moreover, Let \(b_{\tilde{\kappa}}= \frac{\gamma}{\tilde{\kappa}^{2}}\). By Jensen’s inequality, we have \[\begin{align} &\| \omega _{\kappa}(\mu* \rho _{\tilde{\kappa}}) \|_{L^{\gamma}(\rho _{\kappa})}^{\gamma} \\&\leq \mathcal{A}_{d,\kappa,\gamma} \tilde{\kappa}^{-d\gamma} \int _{\mathbb{R}^{d}} \int _{\| y \|_{2} \leq \mathrm{B} } \exp\left( - \frac{{\gamma \| x-y \|_{2}^{2} }}{2\tilde{\kappa}^{2}} \right) \, d\mu(y) \exp\left( \frac{{\gamma-1}}{2\kappa^{2}} \| x \|_{2}^{2} \right) \, dx \\ & \leq \mathcal{A}_{d,\kappa,\gamma} \tilde{\kappa}^{-d\gamma} \int _{\| y \|_{2} \leq \mathrm{B}} \int _{\mathbb{R}^{d}} \exp \left( - \Big(\frac{\gamma}{2\tilde{\kappa}^{2}}-\frac{{\gamma-1}}{2\kappa^{2}}\Big)\| x \|_{2}^{2} \right) \exp\Big( \frac{{2\gamma x^{T}y-\gamma \| y \|_{2}^{2}}}{2\tilde{\kappa}^{2}} \Big) \, dx \, d\mu(y) \\ &\leq \mathcal{A}_{d,\kappa,\gamma} \tilde{\kappa}^{-d\gamma} \int_{\| y \|_{2} \leq \mathrm{B} } \int_{\mathbb{R}^{d}} \exp(-v_{\tilde{\kappa}}\| x \|_{2}^{2} +b_{\tilde{\kappa}}y^{T}x) \, dx \exp\Big(-\frac{{\gamma \| y \|_{2}^{2}}}{2\tilde{\kappa}^{2}} \Big) \, d\mu(y) \\& = \mathcal{A}_{d,\kappa,\gamma} \tilde{\kappa}^{-d\gamma} \int _{\| y \|_{2} \leq \mathrm{B} }\int _{\mathbb{R}^{d}} \exp\Big(-v_{\tilde{\kappa}}\left\| x-\frac{{b_{\tilde{\kappa}}y}}{2v_{\tilde{\kappa}}} \right\|_{2}^{2} \Big) \, dx \exp\Big( \frac{b_{\tilde{\kappa}}^{2}}{4v_{\tilde{\kappa}}}\| y \|_{2}^{2} -\frac{\gamma}{2\tilde{\kappa}^{2}}\| y \|_{2}^{2} \Big) \, d\mu(y) \\&=\mathcal{A}_{d,\kappa,\gamma}\Big(\frac{\pi}{v_{\tilde{\kappa}}}\Big)^{\frac{d}{2}} \tilde{\kappa}^{-d\gamma} \int _{\| y \|_{2} \leq \mathrm{B} } \,\exp\Big(\big(\frac{b_{\tilde{\kappa}}^{2}}{4v_{\tilde{\kappa}}}-\frac{\gamma}{2\tilde{\kappa}^{2}}\big)\| y \|_{2}^{2} \Big) d\mu(y) \\ & \leq \mathcal{A}_{d,\kappa,\gamma} \Big(\frac{\pi}{v_{\tilde{\kappa}}}\Big)^{\frac{d}{2}} \tilde{\kappa}^{-d\gamma} \exp\left( \frac{\gamma(\gamma-1)\tilde{\kappa}^{2}}{2(\gamma\kappa^{2}\tilde{\kappa}^{2}-(\gamma-1)\tilde{\kappa}^{4})} \mathrm{B^{2}}\right) =: f(\tilde{\kappa})^{\gamma} , \end{align}\] We can observe that \(f(\tilde{\kappa})\) is a continuous function on \([t_{0},T]\) and \(f(\tilde{\kappa})\sim \tilde{\kappa}^{-d\left( 1-\frac{1}{\gamma} \right)}, \tilde{\kappa}\to 0\). For the domain generalization assumption, we have \[\begin{align} \int _{\mathcal{B}_{2}(\mathcal{X})} \| \omega _{\kappa}(\rho)\|^{2}_{L^{\gamma}(\rho _{\kappa})} \, d \mathcal{P_{G}^{X}}(\rho) &= \int _{\mathcal{G}_{[t_{0},T]}(\mathrm{B})} \| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})}^{2} \, d \mathcal{P_{G}^{X}}(\rho)\\&= \frac{1}{T-t_{0}}\int_{t_{0}}^{T} \int_{\mathcal{B}_{2,c}(\mathcal{X})} \| \omega _{\kappa}(\mu*\rho _{\tilde{\kappa}}) \|_{L^{\gamma}(\rho _{\kappa})}^{2} \, d \tilde{\mathcal{P}}_{\mathcal{G}}^{\mathcal{X}}(\mu) \, d\tilde{\kappa}\\ &\leq \frac{1}{T-t_{0}} \int _{t_{0}}^{T} f(\tilde{\kappa})^{2} \, d \tilde{\kappa}\leq C_{t_{0},T,\gamma,\mathrm{B},d}. \end{align}\] \(\blacksquare\)

8 Approximation in Gaussian Space↩︎

8.1 Optimal Linear Approximation↩︎

Note that the space \(\mathcal{H}_{k_{\boldsymbol{\lambda}}}\) is actually the tensor product of unvariate RKHS with the kernels \(\exp \{- \lambda_{l}^2(a-b)^2\}\) for \(a,b \in \mathbb{R}\), so we first consider the univariate case with \(k_{\lambda_{1}}(a,b)=\exp \{ -\lambda _{1}^{2}(a-b)^{2} \}\) where \(a, b \in\mathbb{R}\) and the gaussian measure \(\rho _{1,\kappa}\) with density function \((2\pi \kappa^{2})^{-\frac{1}{2}}\exp \left\{ - \frac{a^{2}}{2\kappa^{2}} \right\}\).

For \(j \geq 1\), the eigenvalues and eigenfunctions are given in [@fasshauer2012dimensionindependent; @rasmussen2006gaussian] by \[r_{\lambda_{1},j}= (\sqrt{ 2 }\kappa)^{-1} \lambda_{1}^{2j-2}/ \mathcal{C}_{1}^{j-\frac{1}{2}} \text{ where } \mathcal{C}_{1}= \lambda_{1}^{2}+\frac{1}{4\kappa^{2}}+\frac{1}{2\kappa}\sqrt{ \frac{1}{4\kappa^{2}} +2\lambda_{1}^{2}},\] and \[\begin{align} \tilde{\varphi} _{\lambda_{1},j}(a)=\exp \left( -\left( \frac{1}{2\kappa}\sqrt{ \frac{1}{4\kappa^{2}} +2\lambda _{1}^{2}} -\frac{1}{4\kappa^{2}}\right)a^{2} \right)H_{j-1}\left( \frac{1}{\kappa^{\frac{1}{2}}} \left( \frac{1}{4\kappa^{2}}+2\lambda_{1}^{2} \right)^{\frac{1}{4}} a\right) \end{align}\] where \(H_{j-1}\) is the Hermite polynomial of degree \(j-1\), given by \[\begin{align} H_{j-1}(a)=(-1)^{j-1} e^{a^{2}} \frac{d^{j-1}}{da^{j-1}}e^{-a^{2}} \text{ for } a \in \mathbb{R} \end{align}\] such that \[\begin{align} \int _{\mathbb{R}} H^{2}_{j-1}(a) \exp(-a^{2}) \, da=\sqrt{ \pi }2^{j-1} (j-1)! \text{ for } j \in \mathbb{N}. \end{align}\]

Then we can take a orthonormal basis of \(L^{2}(\rho _{1,\kappa})\) to be \(\{ \varphi _{\lambda_{1},j} \}_{j \in \mathbb{N}}\) by \[\begin{align} \varphi _{\lambda_{1},j}(a)=\sqrt{ \frac{(1+8\kappa^{2}\lambda_{1}^{2})^{\frac{1}{4}}}{2^{j-1}(j-1)!} } \exp\left( - \frac{2\lambda_{1}^{2}a^{2}}{\sqrt{ 1+8\kappa^{2}\lambda_{1}^{2} }+1} \right)H_{j-1}\left( \frac{1}{\sqrt{ 2 }\kappa} (1+8\kappa^{2}\lambda_{1}^{2})^{\frac{1}{4}} a \right), \end{align}\] and observe that \((\sqrt{ 2 }\kappa )^{-1}\mathcal{C}_{1}^{-\frac{1}{2}}=1- \frac{\lambda_{1}^{2}}{\mathcal{C}_{1}}\), which allows us to rewrite \(r_{\lambda_{1},j}\) as \(r_{\lambda_{1},j}=(1-\eta _{\lambda_{1}})\eta _{\lambda_{1}}^{j-1}\) with

\[\begin{align} \eta _{\lambda_{1}}=\frac{\lambda _{1}^{2}}{\mathcal{C}_{1}}= \frac{4\kappa^{2}\lambda_{1}^{2}}{4\kappa^{2}\lambda_{1}^{2}+1+\sqrt{ 1+8\kappa^{2}\lambda_{1}^{2} } }\in(0,1). \end{align}\] For the multivariate case with \(\boldsymbol{\lambda}=(\lambda_{1},\dots,\lambda _{d})\), let \(\boldsymbol{j}\) be a multi-index with \(\boldsymbol{j}=(j_{1},\dots,j_{d}) \in \mathbb{N}^{d}\). Then the pairs \((r^{\boldsymbol{\lambda}}_{\boldsymbol{j}}, \varphi^{\boldsymbol{\lambda}}_{\boldsymbol{j}})\) of eigenvalues and eigenfunctions are given by \[\begin{align} r^{\boldsymbol{\lambda}}_{\boldsymbol{j}}:= \prod _{l=1}^{d}r_{\lambda _{l},j_{l}}=\prod _{l=1}^{d}(1-\eta _{\lambda _{l}})\eta _{\lambda _{l}}^{j_{l}-1} \text{ and } \varphi^{\boldsymbol{\lambda}}_{\boldsymbol{j}}(x):=\prod _{l=1}^{d} \varphi _{\lambda _{l},j_{l}}(x^{(l)}) \text{ for } x=[x^{(1)},..., x^{(d)}] \in \mathbb{R}^{d}. \end{align}\] We can also define an orthonormal basis \((\psi^{\boldsymbol{\lambda}}_{\boldsymbol{j}})\) on \(\mathcal{H}_{k_{\boldsymbol{\lambda}}}\) by \[\begin{align} \psi^{\boldsymbol{\lambda}}_{\boldsymbol{j}}(x):=\prod _{l=1}^{d} \psi _{\lambda _{l},j_{l}}(x^{(l)}) \text{ where }\psi _{\lambda _{l},j_{l}}:= \sqrt{ r_{\lambda _{l},j_{l}} }\varphi _{\lambda _{l},j_{l}}. \end{align}\]

For the simplicity of notation, we rearrange the sequence of eigenpairs \((r_{\boldsymbol{j}}^{\boldsymbol{\lambda}},\psi _{\boldsymbol{j}}^{\boldsymbol{\lambda}})_{\boldsymbol{j}\in \mathbb{N}^{d}}\) to the sequence \((r^{\boldsymbol{\lambda}}_{q}, \psi^{\boldsymbol{\lambda}}_{q})_{q \in\mathbb{N}}\) with the order of a non-increasing sequence of eigenvalues, i.e., \(r^{\boldsymbol{\lambda}}_{1} \geq r^{\boldsymbol{\lambda}}_{2} \geq \dots>0\).

By Corollary 4.12 in [@novak2008tractability], the optimal linear approximation error is \[\mathcal{E}(n,\mathcal{H}_{k_{\boldsymbol{\lambda}}}):= \inf_{\Lambda _{n}\subset \mathcal{H}_{k_{\boldsymbol{\lambda}}}}\sup_{\| f \|_{\mathcal{H}_{k_{\boldsymbol{\lambda}}}}\leq 1}\left\| f- \operatorname{ Proj }_{\Lambda _{n}}(f) \right\|_{L^{2}(\rho _{\kappa})}=\sqrt{ r^{\boldsymbol{\lambda}}_{n+1} }\] where \(\Lambda _{n}\) is an \(n\)-dimensional subspace of \(\mathcal{H}_{k_{\boldsymbol{\lambda}}}\). By Theorem 5.2 in [@fasshauer2012dimensionindependent], \(\mathcal{E}(n,\mathcal{H}_{k_{\boldsymbol{\lambda}}}) \leq C_{\delta,\kappa,\theta}n^{-\max\left( \theta, \frac{1}{2} \right)+\delta}\) for any \(\delta>0\) where \(C_{\delta,\kappa,\theta}\) only depends on \(\delta\), \(\kappa\) and \(\theta\).

8.2 Approximation of Eigenfunctions by Two-Hidden-Layer Tanh Neural Networks↩︎

In this part, we show \(L^{2}(\rho)\)-approximation of orthonormal basis defined in Appendix 8.1 by neural networks where \(\rho\) is a probability distribution with \(\| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})}< \infty\).

Recall that \(\psi^{\boldsymbol{\lambda}}_{\boldsymbol{j}}\) has a product form of factors being elements with a unit norm in \(\mathcal{H}_{k_{\lambda _{l}}}\). To approximate analytic functions with this form, we apply the shallow neural network with and tanh activation functions and a product-gated output defined in (1).

By scaling and translating the variable, for each pair \((\lambda _{l}, j_{l} )\), we define \(g_{\lambda _{l},j_{l}}(t):= \psi_{\lambda _{l},j_{l}}\left( 2B\left( t -\frac{1}{2} \right) \right)\) for \(t \in [0,1]\) with some number \(B>0\). Here we introduce the class of \((Q,R)\)-analytic functions with \(Q,R >0\) in which an analytic function \(f\) satisfies the smoothness condition that \(\| D^{\beta}f \|_{L^{\infty}([0,1]^{d})} \leq Q R^{-\beta}\beta!\) for all \(\beta \in \mathbb{N}\).

By Theorem 1 in [@zhou2008derivative], for each \(\psi _{\lambda _{l},j_{l}} \in \mathcal{H}_{k_{\lambda _{l}}}\), we have that \[\begin{align} \left| D^{\beta} g_{\lambda _{l},j_{l}}(t) \right| &= \left| (2B)^{\beta}D^{\beta}\psi_{\lambda _{l},j_{l}}\left( 2B\left( t-1 /2 \right) \right) \right| = \left| (2B)^{\beta} \left\langle (D^{\beta}k_{\lambda _{j}})_{2B\left( t-\frac{1}{2} \right)} ,\psi_{\lambda _{l},j_{l}}\right\rangle _{\mathcal{H}_{k_{\lambda _{l}}}} \right| \\ &\leq (2B)^{\beta} \sqrt{ D^{(\beta,\beta)}k_{\lambda _{l}}(x,x) } \leq (4B\lambda _{l})^{\beta} \beta! \leq (4BC_{\theta})^{\beta} \beta!. \end{align}\] It implies that \(g_{\lambda _{l},j_{l}}\) is a \((1, (4BC_{\theta})^{-1})\)-analytic function for each pair \((\lambda _{l},j_{l})\).

Indeed, for \(k_{\lambda _{l}}(a,b)= \exp \{ -\lambda _{l}^{2} (a-b)^{2}\}\), \[\begin{align} D^{(\beta,\beta)}k_{\lambda _{l}}=\partial _{a}^{\beta} \partial _{b}^{\beta}k_{\lambda _{l}}=(-\lambda _{l}^{2})^{\beta} \partial _{c}^{2\beta} \exp \{ -c ^{2} \} \text{ with } c =\lambda _{l}(a-b). \end{align}\] By the definition of Hermite polynomials, \(\partial _{c}^{2\beta} \exp(-c ^{2})=H_{2\beta}(c)\exp(-c ^{2})\). It follows that \[\begin{align} \partial _{c}^{2\beta} \exp(-c ^{2})|_{c=0}= H_{2\beta}(0)= (-1)^{\beta} \frac{(2\beta)!}{\beta!} \end{align}\] which is called Hermite numbers of the even order. Then we have \[\begin{align} \sqrt{ D^{(\beta,\beta)} k_{\lambda _{l}}(x,x) }\leq \lambda _{l}^{\beta} \sqrt{ \frac{(2\beta)!}{\beta!} } = \lambda _{l}^{\beta} \sqrt{ \binom{2\beta}{\beta} \beta!}\leq (2\lambda _{l})^{\beta}\beta!, \end{align}\] which proves the claim with \(Q=1, R=(4BC_{\theta})^{-1}\).

The following lemma follows from an application of Theorem B.7 in [@deryck2023error] and Corollary 5.5 in [@deryck2021approximation] by taking \(s=4\tilde{m}, N=\tilde{m}\).

We define \(\hat{\psi}_{\lambda _{l},j_{l}}^{\tilde{m}}(t)= \hat{g}_{\lambda _{l},j_{l}}^{\tilde{m}}\left( \frac{t}{2B} + \frac{1}{2} \right)\) and recall the product gate \(\mathcal{T}_{1,\odot}\) defined as \[\mathcal{T}_{1,\odot}(x) = \prod _{l=1}^{d} \mathcal{T}_{1}(x_{l}) \text{ with } \mathcal{T}_{1}(x_{l})=x_{l} \text{ if }\left| x_{l} \right|<1 \text{ otherwise } \frac{x_{l}}{\left| x_{l} \right| }\] (\(\mathcal{T}_{1}\) can be also implemented by a fixed ReLU neural network as \(\sigma(x_{l}+1)-\sigma(x_{l}-1)-1\)). Then we can construct an approximant for \(\psi^{\boldsymbol{\lambda}}_{\boldsymbol{j}}= \prod_{l=1}^{d}\psi_{\lambda _{l},j_{l}}\) by \(\hat{\psi}_{\boldsymbol{j},\tilde{m}}^{\boldsymbol{\lambda}}:=\mathcal{T}_{1,\odot}\big((\hat{\psi}_{\lambda _{1},j_{1}}^{\tilde{m}},\dots, \hat{\psi}_{\lambda _{d},j_{d}}^{\tilde{m}})\big)\) with \(L^{2}(\rho)\) approximation error \[\begin{align} \left\| \psi^{\boldsymbol{\lambda}}_{\boldsymbol{j}}- \hat{\psi}^{\boldsymbol{\lambda}}_{\boldsymbol{j},\tilde{m}} \right\|_{L^{2}(\rho)}^{2} &= \left( \int_{\| x \|_{\infty} \leq B } \;+ \int _{\| x \|_{\infty} >B } \, \right) (\psi^{\boldsymbol{\lambda}}_{\boldsymbol{j}}(x)-\hat{\psi}^{\boldsymbol{\lambda}}_{\boldsymbol{j},\tilde{m}}(x))^{2} \, d \rho(x) \\ & \leq \sup_{\| x \|_{\infty} \leq B } ( \psi^{\boldsymbol{\lambda}}_{\boldsymbol{j}}(x)-\hat{\psi}^{\boldsymbol{\lambda}}_{\boldsymbol{j},\tilde{m}}(x) )^{2} + 2\rho(\{ x:\| x \|_{\infty}>B \}). \end{align}\] For the first term, we bound it with Lemma 3 by introducing intermediate terms as follows: \[\begin{align}& \sup_{\| x \|_{\infty}\leq B } \bigl|\psi^{\boldsymbol{\lambda}}_{\boldsymbol{j}}(x)-\hat{\psi}^{\boldsymbol{\lambda}}_{\boldsymbol{j},\tilde{m}}(x)\bigr| =\Bigl\|\prod_{l=1}^{d}\psi_{\lambda _{l},j_{l}}-\prod_{l=1}^{d}\mathcal{T}_{1}(\hat{\psi}_{\lambda _{l},j_{l}}^{\tilde{m}})\Bigr\|_{L^{\infty}([-B,B]^{d})}\\[2pt] \le &\Bigl\|\prod_{l=1}^{d}\psi_{\lambda _{l},j_{l}}-\mathcal{T}_{1}(\hat{\psi}_{\lambda _{1},j_{1}}^{\tilde{m}})\prod_{l=2}^{d}\psi_{\lambda _{l},j_{l}}+\cdots+\prod_{l'=1}^{h}\mathcal{T}_{1}(\hat{\psi}_{\lambda _{l'},j_{l'}}^{\tilde{m}})\prod_{l=h+1}^{d}\psi_{\lambda _{l},j_{l}}-\prod_{l'=1}^{h+1}\mathcal{T}_{1}(\hat{\psi}_{\lambda _{l'},j_{l'}}^{\tilde{m}})\prod_{l=h+2}^{d}\psi_{\lambda _{l},j_{l}} \\ & +\cdots + \prod _{l'=1}^{d-1}\mathcal{T}_{1}(\hat{\psi}_{\lambda _{l},j_{l}}^{\tilde{m}}) \psi _{\lambda _{d},j_{d}}- \prod _{l=1}^{d}\mathcal{T}_{1}(\hat{\psi}_{\lambda _{l},j_{l}}^{\tilde{m}})\Bigr\|_{L^{\infty}([-B,B]^{d})} \\ \leq & d \max_{0 \leq h \leq d-1} \left\| \prod_{l'=1}^{h}\mathcal{T}_{1}(\hat{\psi}_{\lambda _{l'},j_{l'}}^{\tilde{m}})\prod_{l=h+1}^{d}\psi_{\lambda _{l},j_{l}}-\prod_{l'=1}^{h+1}\mathcal{T}_{1}(\hat{\psi}_{\lambda _{l'},j_{l'}}^{\tilde{m}})\prod_{l=h+2}^{d}\psi_{\lambda _{l},j_{l}}\right\|_{L^{\infty}([-B,B]^{d})} \\ \leq & d \max _{0\leq h \leq d-1} \| \psi _{\lambda _{h+1}, j_{h+1}} - \mathcal{T}_{1}(\hat{\psi}^{\tilde{m}}_{\lambda _{h+1},j_{h+1}}) \|_{L^{\infty}([-B,B])} \leq d \max _{0 \leq h \leq d-1} \| \psi _{\lambda _{h+1}, j_{h+1}} - \hat{\psi}^{\tilde{m}}_{\lambda _{h+1},j_{h+1}} \|_{L^{\infty}([-B,B])} \\ \leq & 2d \exp \left( - 4\tilde{m} \log \left( \frac{\tilde{m}}{6BC_{\theta}} \right) \right) . \end{align}\] For the second term, we bound it by the subgaussian tail decay of probability measures: \[\begin{align} \rho(\{ x: \| x \|_{\infty} >B \})&= \int_{\| x \|_{\infty} >B } \omega _{\kappa}(\rho)(x) \, d\rho _{\kappa}(x) \leq \| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} (\rho _{\kappa}(\{ x: \| x \|_{\infty}>B \}))^{\frac{\gamma-1}{\gamma}} \\ & \leq \| \omega _{\kappa}(\rho)\|_{L^{\gamma }(\rho _{\kappa})} \left( d \cdot \frac{\kappa}{\sqrt{ 2\pi }}B^{-1} \exp\left( -\frac{B^{2}}{2\kappa^{2}} \right) \right)^{\frac{\gamma-1}{\gamma}} \\ & \leq C_{\kappa,\gamma}d \| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} \exp \left( - \frac{\gamma-1}{\gamma} \Big(\frac{B^{2}}{2\kappa^{2}}+\log B\Big) \right) \end{align}\] with \(C_{\kappa,\gamma}=\left( \frac{\kappa}{\sqrt{ 2\pi }} \right)^{\frac{\gamma-1}{\gamma}}\). Let \(B= \frac{\tilde{m}^{\frac{3}{4}}}{6C_{\theta}}\) and the above upper bound can written as \[\begin{align} \rho(\{ x:\| x \|_{\infty} >B \}) & \leq dC_{\kappa,\gamma} \| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} \exp \left( - \frac{\gamma-1}{\gamma} \Big(\frac{\tilde{m}^{\frac{3}{2}}}{72\kappa^{2}C_{\theta}^{2}} + \frac{3}{4}\log \tilde{m}-\log 6C_{\theta}\Big) \right) \\ & \leq d C_{\kappa,\gamma} \| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} \exp (- 2\tilde{m}\log \tilde{m}) \end{align}\] when \(\tilde{m}> C_{\kappa,\theta,\gamma}\) with \(C_{\kappa,\theta,\gamma}\) a constant only depending on \(\kappa, \gamma\) and \(C_{\theta}\).

Then combine two estimations and we can the final bound as \[\begin{align} \| \psi^{\boldsymbol{\lambda}}_{\boldsymbol{j}}-\hat{\psi}_{\boldsymbol{j},\tilde{m}}^{\boldsymbol{\lambda}} \|_{L^{2}(\rho)}^{2} &\leq (2d)^{2} \exp(-2\tilde{m}\log\tilde{m}) + 2d C_{\kappa,\gamma}\| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} \exp(- 2\tilde{m}\log \tilde{m}) \\ & \leq (4d^{2}+C_{\kappa,\gamma}\| \omega _{\kappa}(\rho)\|_{L^{\gamma}(\rho _{\kappa})} ) \exp (-2\tilde{m}\log \tilde{m}) \end{align}\] for \(\tilde{m}> C_{\kappa,\theta,\gamma}\). \(\blacksquare\)

---

1. Email: peilin.6liu@gmail.com↩︎

2. Email: dingxuan.zhou@sydney.edu.au↩︎

3. Refer to GeLU implementation in Pytorch 2.8 documentation: https://docs.pytorch.org/docs/stable/generated/torch.nn.GELU.html↩︎