6 Notation, regularity preliminaries, and probabilistic toolkit↩︎

This appendix collects the conventions, the predictable filtration, and the concentration inequalities used in every later appendix. Every later appendix quotes a numbered lemma stated here so that the proofs are self-contained.

6.1 Notation↩︎

For a random variable \(U\) with values in a Euclidean space, \(\|U\|_2\) denotes its Euclidean norm and \(\|U\|_{\rm op}\) denotes the operator norm if \(U\) is matrix-valued. The Orlicz \(\psi_1\)-norm is \[\|U\|_{\psi_1} = \inf\{\lambda>0:\mathbb{E}\exp(|U|/\lambda)\le 2\},\] and the conditional Orlicz norm given a \(\sigma\)-algebra \(\mathcal{G}\) is defined analogously by replacing \(\mathbb{E}\) with \(\mathbb{E}[\cdot\mid\mathcal{G}]\) and the infimum by an essential infimum. We write \(a_n\lesssim b_n\) if there exists a constant \(C>0\), depending only on the structural constants \((d,c_X,C_X,\eta,\beta_{\min},\beta_{\max},c_V,C_V,C_q,\tau)\), such that \(a_n\le Cb_n\) for all \(n\) large enough; \(a_n\asymp b_n\) if both \(a_n\lesssim b_n\) and \(b_n\lesssim a_n\). The notation \(\widetilde{O}\) hides at most polylogarithmic factors in \(n\). For a function \(g:\mathcal{X}\to\mathbb{R}\), \(\|g\|_{L_2(P_X)}^2=\int g^2\,dP_X\) and \(\|g\|_N^2=N^{-1}\sum_{i=1}^N g(X_i)^2\).

6.2 Predictable filtration↩︎

We work on a single probability space supporting the entire experimental trajectory and the Bayesian teacher. Define the filtration \[\label{eq:filtration} \mathcal{F}_0=\sigma(\emptyset), \quad \mathcal{F}_t =\sigma\bigl(\{X_s,W_s,Y_s\}_{s\le t-1}\bigr), \quad \mathcal{F}_t^X =\sigma\bigl(\mathcal{F}_t\cup\{X_t\}\bigr), \quad \mathcal{F}_t^W =\sigma\bigl(\mathcal{F}_t^X\cup\{W_t\}\bigr).\tag{5}\] Equivalently, \(\mathcal{F}_t=\sigma(\mathcal{H}_{t-1})\). The propensity \(e_t(\cdot)\) is \(\mathcal{F}_t\)-measurable (it is a function of the past), \(X_t\) is \(\mathcal{F}_t^X\)-measurable, \(W_t\) is \(\mathcal{F}_t^W\)-measurable, and \(Y_t\) is \(\mathcal{F}_{t+1}\)-measurable. By construction \(\mathbb{E}[W_t\mid \mathcal{F}_t^X] = e_t(X_t),\) and \(\mathbb{E}[Y_t\mid \mathcal{F}_t^W] = \mu_{W_t}^\star(X_t).\) This is the predictable filtration on which all martingale arguments below are based.

6.3 Sub-exponential calculus↩︎

A random variable \(U\) is \((\sigma,K)\)-sub-exponential conditional on \(\mathcal{G}\) if \[\mathbb{E}\bigl[\exp\{\lambda(U-\mathbb{E}[U\mid\mathcal{G}])\}\,\big|\,\mathcal{G}\bigr] \le \exp\bigl(\sigma^2\lambda^2/2\bigr) \qquad \forall\,|\lambda|\le 1/K.\] Under Assumption 2, both \(\xi_{t,\mu,w}=Y_t-\mu_w^\star(X_t)\) and \(\xi_{t,q,w}=Y_t^2-q_w^\star(X_t)\) are conditionally sub-exponential given \((\mathcal{F}_t^X,W_t=w)\), with parameters \((\sigma_\xi,K_\xi)\) uniform in \(t,w\). Throughout \(\tau:=\max(\sigma_\xi,K_\xi)\) denotes the corresponding constant.

Sketch. Standard Freedman-type Bernstein bound for \(\psi_1\) MDS; see, e.g., [23] Lemma 8.2 or [24] Theorem 6.1 adapted to the predictable quadratic variation via a stopping-time argument. \(\square\)

6.4 Matrix Freedman↩︎

6.5 Le Cam–Birgé tests↩︎

The proof is the squared-residual likelihood ratio \(T_f=\mathbf{1}\{N^{-1}\sum (Z_i-f)^2-(Z_i-m^\star)^2\le -\frac{1}{2}\rho^2\}\), combined with Lemma 1 on \(\sum \xi_i\bigl(f(X_i)-m^\star(X_i)\bigr)\), the empirical-norm equivalence from Lemma 5 below, and the squared-loss bias identity. The detailed argument is reproduced inside Appendix 8.

6.6 Empirical norm equivalence on a finite-dimensional class↩︎

The proof is Appendix 7 (Lemma 9).

6.7 Triangular-array martingale CLT↩︎

6.8 Standing assumptions and quantities↩︎

We collect the constants used downstream: \[\begin{align} c_X,C_X &\in (0,\infty) & \text{density bounds on } P_X \notag\\ c_V,C_V &\in (0,\infty) & \text{variance bounds (Assumption~\ref{ass:basic})} \notag\\ \eta &\in (0,1/2) & \text{clip threshold} \notag\\ \beta_{\min},\beta_{\max} & & \text{smoothness range} \notag\\ \tau & & \text{sub-exponential constant for } \xi_{t,\mu,w},\xi_{t,q,w} \notag\\ \kappa & & \text{basis envelope: } \sup_x\|\phi_J(x)\|_2^2\le \kappa J \notag\\ R & & \text{Sobolev radius: } m^\star\in\mathcal{H}^{\beta^\star}(R). \notag \end{align}\] For the Fourier/Laplacian basis on \([0,1]^d\), \(\kappa\) is an absolute constant. Together with bounded density these constants yield the geometric facts of Appendix 7.

7 Basis geometry and adaptive Gram concentration↩︎

7.0.0.1 Roadmap.

The Bayesian update 1 is, on the active subspace of size \(J\), a finite-dimensional ridge regression with design matrix \(\Phi=[\phi_J(X_i)]_i\) and Gram \(\widehat\Gamma_J=N^{-1}\Phi^\top\Phi\). Every later contraction or rate argument needs this Gram to be uniformly well-conditioned — bounded eigenvalues both above and below — so that inversion is stable and empirical norms are equivalent to \(L_2(P_X)\) norms on the active class. This appendix proves uniform well-conditionedness in three escalating settings:

1. Population (Lemma 7): bounded density on \([0,1]^d\) pulls back the Lebesgue orthogonality of the cosine basis to a Riesz bound on \(\Gamma_J\).

2. IID empirical (Lemma 8): matrix Bernstein on iid rank-one matrices, valid as soon as \(N\gtrsim J\log J\).

3. Adaptive martingale (Lemma 9): for arm-specific covariates collected under the predictable Bayesian propensity, the Gram increments form a matrix MDS; matrix Freedman delivers the same conclusion under \(N_{t,w}\gtrsim J\log J\).

Lemma 10 unions these across all relevant \((J,t,w)\) to produce the single high-probability event \(\mathcal{G}_n\) on which every subsequent appendix argument operates.

7.0.0.2 Why the threshold \(N\gtrsim J\log J\).

Each rank-one summand \(\phi_J(X_i)\phi_J(X_i)^\top\) has operator norm \(O(J)\) but population mean operator norm \(O(1)\); the variance proxy is therefore order \(NJ\) rather than \(N\). To get a \(\le \tfrac12\) operator-norm relative error one needs the standard deviation \(\sqrt{NJ}/N\) to dominate, i.e.\(N\gtrsim J\), and an extra \(\log J\) from union-bounding across \(J\) matrix dimensions (matrix Bernstein). This \(J\log J\) threshold is exactly the dynamic-mask condition used by the transformer in Appendix 12: it is the minimum sample size at which finite-rank ridge updates are stable.

7.1 Reference basis on \([0,1]^d\)↩︎

Order the tensor-product cosine basis on \([0,1]^d\) by increasing Laplacian eigenvalue and call it \(\{\psi_j:j\ge 1\}\). By Weyl’s law, \(\lambda_j\asymp j^{2/d}.\) This basis is orthonormal under Lebesgue measure on \([0,1]^d\): \(\int \psi_j\psi_\ell=\mathbf{1}\{j=\ell\}\). It is uniformly bounded coordinatewise — \(\sup_x|\psi_j(x)|\le 2^{d/2}\) — so writing \(\phi_J(x)=(\psi_1(x),\ldots,\psi_J(x))^\top\), \[\label{eq:basis-envelope} \sup_{x\in[0,1]^d}\|\phi_J(x)\|_2^2 \le 2^d J =: \kappa J.\tag{6}\] The basis-Sobolev ball matches the spectral Sobolev ball: \(\mathcal{H}^\beta(R) = \{f=\sum_j\theta_j\psi_j:\sum_j j^{2\beta/d}\theta_j^2\le R^2\}.\)

7.2 Population Gram↩︎

Proof. For any \(a\in\mathbb{R}^J\), \(g_a(x):=\sum_{j\le J}a_j\psi_j(x)\) has Lebesgue \(L_2\) norm \(\|a\|_2\), since the cosine basis is Lebesgue-orthonormal. Thus \[a^\top\Gamma_J a = \int_{[0,1]^d}g_a(x)^2 p_X(x)\,dx \in \bigl[c_X\|a\|_2^2,\,C_X\|a\|_2^2\bigr].\] \(\square\)

7.3 Empirical Gram, iid case↩︎

Proof. Set \(Y_i=\Gamma_J^{-1/2}\phi_J(X_i)\phi_J(X_i)^\top\Gamma_J^{-1/2}-I_J\). Then \(\mathbb{E}Y_i=0\) and, using 6 and Lemma 7, \[\|Y_i\|_{\rm op} \le \|\Gamma_J^{-1/2}\phi_J(X_i)\|_2^2+1 \le \frac{\kappa J}{c_X}+1 \le \frac{2\kappa J}{c_X}=:R.\] The matrix variance is bounded by \(\|\mathbb{E}[Y_i^2]\|_{\rm op} \le \mathbb{E}\|Y_i\|_{\rm op}^2 \le R^2.\) Apply the matrix Bernstein inequality [27] to the iid sum \(\sum_i Y_i\): with \(\sigma^2=NR^2\) and \(u=N/2\), \[\Pr\!\left(\Bigl\|\tfrac1N\sum_i Y_i\Bigr\|_{\rm op}>\tfrac12\right) \le 2J\exp\!\left(-\frac{N/8}{R^2/(c_X^2)+R/3}\right) \le 2J\exp(-cN/J).\] Equivalently \(\tfrac12 I_J\preceq \Gamma_J^{-1/2}\widehat\Gamma_J\Gamma_J^{-1/2}\preceq \tfrac32 I_J\). Translating back gives the stated bound. The threshold \(N\ge CJ\log(J/\delta)\) makes the right-hand side \(\le \delta\). \(\square\)

7.4 Adaptive martingale Gram↩︎

Proof. Step 1 (sample-size lower bound). Define \(\Delta_i^{\rm cnt}=I_i(w)-e_i^B(X_i)\mathbf{1}\{w=1\}-(1-e_i^B(X_i))\mathbf{1}\{w=0\}\). Then \(\mathbb{E}[\Delta_i^{\rm cnt}\mid\mathcal{F}_i^X]=0\) and \(|\Delta_i^{\rm cnt}|\le 1\). By the bounded-difference Azuma inequality (Lemma 2), \[\Pr\!\left(\Bigl|\sum_{i\le t}\Delta_i^{\rm cnt}\Bigr|>u\right) \le 2\exp(-u^2/(2t)).\] Since the predictable conditional mean satisfies \(\mathbb{E}[I_i(w)\mid\mathcal{F}_i^X]\ge \eta\), \(\mathbb{E}[N_{t,w}\mid\mathcal{F}_t] \ge \eta t.\) With \(u=\eta t/2\), the Azuma bound gives \(\Pr(N_{t,w}<\eta t/2)\le 2\exp(-c\eta^2 t)\le \delta\) provided \(t\ge C\eta^{-2}\log(2/\delta)\), which is implied by the hypothesis when \(C_1\) is large.

Step 2 (martingale Gram increments). Define the increments \[\Delta_i := I_i(w)\phi_J(X_i)\phi_J(X_i)^\top -\mathbb{E}\bigl[I_i(w)\phi_J(X_i)\phi_J(X_i)^\top\,\big|\,\mathcal{F}_{i-1}\bigr].\] By the tower property and 5 , \[\mathbb{E}[I_i(w)\phi_J(X_i)\phi_J(X_i)^\top\mid\mathcal{F}_{i-1}] = \mathbb{E}_{X\sim P_X}\!\bigl[e_i^B(X)^{\mathbf{1}\{w=1\}}(1-e_i^B(X))^{\mathbf{1}\{w=0\}}\phi_J(X)\phi_J(X)^\top\bigr],\] and by clipping, \[\label{eq:gram-cond-bound} \eta\,\Gamma_J \preceq \mathbb{E}[I_i(w)\phi_J(X_i)\phi_J(X_i)^\top\mid\mathcal{F}_{i-1}] \preceq (1-\eta)\,\Gamma_J.\tag{7}\] The increments \(\Delta_i\) are MDS w.r.t. \(\mathcal{F}_i\). Their operator norm is bounded a.s. by \[\|\Delta_i\|_{\rm op} \le 2\|\phi_J(X_i)\|_2^2 \le 2\kappa J =:R_J.\] Their predictable matrix variance satisfies, using \(\|\phi_J(X_i)\phi_J(X_i)^\top\|_{\rm op}\le \kappa J\), \[\begin{align} \mathbb{E}[\Delta_i^2\mid\mathcal{F}_{i-1}] &\preceq \mathbb{E}[I_i(w)\|\phi_J(X_i)\|_2^2\phi_J(X_i)\phi_J(X_i)^\top\mid\mathcal{F}_{i-1}]\\ &\preceq \kappa J\,\mathbb{E}[I_i(w)\phi_J(X_i)\phi_J(X_i)^\top\mid\mathcal{F}_{i-1}] \preceq \kappa J(1-\eta)\Gamma_J. \end{align}\] Hence the cumulative predictable variance is bounded as \(\|W_t\|_{\rm op} \le \kappa J(1-\eta)\,t\,C_X.\)

Step 3 (matrix Freedman). Apply Lemma 3 to \(\sum_{i\le t}\Delta_i\): \[\Pr\!\left(\Bigl\|\sum_{i\le t}\Delta_i\Bigr\|_{\rm op}>u\right) \le 2J\exp\!\left(-\frac{u^2/2}{\kappa J(1-\eta) t C_X+R_Ju/3}\right).\] Choosing \(u=\eta c_X t/4\) (a constant fraction of the conditional mean) and \(t\ge C_1 J\log(J/\delta)/\eta\) for \(C_1\) large enough, this probability is at most \(\delta\).

Step 4 (combine). On the intersection of the Step 1 and Step 3 events (which has probability \(\ge 1-2\delta\)), \[\Bigl\|\sum_{i\le t}I_i(w)\phi_J(X_i)\phi_J(X_i)^\top -\sum_{i\le t}\mathbb{E}[I_i(w)\phi_J(X_i)\phi_J(X_i)^\top\mid\mathcal{F}_{i-1}]\Bigr\|_{\rm op} \le \eta c_X t/4,\] and \(N_{t,w}\ge \eta t/2\). Dividing the displayed bound by \(N_{t,w}\) and combining with 7 yields ?? . \(\square\)

7.5 Uniform Gram event↩︎

Proof. The event is a union of at most \(2J_{\max,n}\cdot t_{\max}\) events from Lemma 9, each of probability \(\le 2\delta_n\). The choice of \(\delta_n\) makes the total deviation at most \(n^{-A}\) after discretizing \(t\) on a logarithmic grid (the bound is monotone in \(t\) between grid points up to a factor \(1+o(1)\)). The Hessian bound follows from ?? together with \(\bar\sigma^2\rho_{d_{N,k}}^{-1}/N_{t,w}\le \bar\sigma^2\) on the active subspace and \(\rho_j^{-1}\ge 0\). \(\square\)

7.5.0.1 Reading the dynamic-mask conditions.

Lemma 10 explains the two conditions placed on the dynamic active dimension in the main text: the first condition \(N_{t,w}\gtrsim J\log J\) guarantees the empirical covariance is well-conditioned on the active subspace; the second condition \(\rho_{J,k}^{-1}\lesssim N_{t,w}\) ensures the rescaled prior precision \(N^{-1}\Lambda_k^{-1}\) does not blow up the upper Hessian eigenvalue. Together they give a constant condition number.

8 Proof of Proposition 1↩︎

8.0.0.1 Goal.

Given an adaptive arm-\(w\) subsample of size \(N=N_{t,w}\) and a Gaussian-series prior with smoothness \(\beta\) matched to the truth \(m^\star\in\mathcal{H}^\beta(R)\), prove that the (quasi-)posterior puts asymptotically all of its mass on a ball of radius \(M\varepsilon_N\) around \(m^\star\) in \(L_2(P_X)\), with \[\label{eq:contraction-rate-app} \varepsilon_N = N^{-\beta/(2\beta+d)}\,(\log N)^A.\tag{8}\] Apply the result to four targets \((w,h)\in\{0,1\}\times\{\mu,q\}\) to recover Proposition 1.

8.0.0.2 Strategy (Ghosal–Ghosh–van der Vaart template).

Posterior contraction at rate \(\varepsilon_N\) follows from three ingredients:

1. Prior small-ball. \(\Pi(\|f-m^\star\|_{L_2(P_X)}\le \varepsilon_N)\ge e^{-CN\varepsilon_N^2}\) — the prior must not be exponentially thin near the truth.

2. Sieve and entropy. A model space \(\mathcal{F}_n\) with \(\Pi(\mathcal{F}_n^c)\le e^{-(C+4)N\varepsilon_N^2}\) and metric entropy \(\le N\varepsilon_N^2\) at scale \(\varepsilon_N\).

3. Tests. Exponentially powerful tests separating \(m^\star\) from every alternative in \(\mathcal{F}_n\) at distance \(\ge M\varepsilon_N\).

Combining (I)–(III) via Bayes’ rule yields \(\Pi(\|f-m^\star\|>M\varepsilon_N\mid \mathcal{D}_N)\le e^{-N\varepsilon_N^2}\to 0\).

8.0.0.3 Where the rate \(\varepsilon_N=N^{-\beta/(2\beta+d)}\) comes from (bias–variance heuristic).

With \(J\) active coefficients and \(N\) samples, an OLS fit incurs a stochastic error of order \(\sqrt{J/N}\) on each coefficient (variance); truncating to \(J\) coefficients incurs a truncation bias \(\sum_{j>J}(\theta_j^\star)^2\lesssim J^{-2\beta/d}\). The two pieces together give \[\label{eq:bv-tradeoff} \mathrm{MSE}(J) \;\asymp\; \underbrace{J^{-2\beta/d}}_{\text{bias}^2} +\underbrace{J/N}_{\text{variance}}.\tag{9}\] Setting the derivative to zero gives the optimal \(J_N\asymp N^{d/(2\beta+d)}\) and the optimal \(\mathrm{MSE}\asymp N^{-2\beta/(2\beta+d)}\). The \(\log N\) in 8 is the price of the union bound in the test step (III).

8.0.0.4 Why the prior does not dominate.

The smoothness prior puts variance \(\rho_j(\beta)\asymp j^{-1-2\beta/d}\) on coefficient \(j\); equivalently, it contributes precision \(N^{-1}\rho_j^{-1}\asymp j^{1+2\beta/d}/N\) to the effective posterior precision (since the data contributes \(N\) on each active coordinate). At \(j=J_N\), \(N^{-1}\rho_{J_N}^{-1}\asymp J_N^{1+2\beta/d}/N\asymp 1\) — comparable to, not larger than, the data information. Past \(J_N\) the prior dominates and shrinks the coefficient to zero; before \(J_N\) the data dominates and we get a \(1/N\) posterior variance. The "active dimension" \(J_N\) is exactly the cutoff where the two information sources balance, validating 9 as the right MSE expression.

8.1 Setup↩︎

Fix arm \(w\) and a moment target. Let \(N=N_{t,w}\) and let \(\mathcal{D}_N=\{(X_i,Z_i):i\le t,\,W_i=w\}\) be the arm-\(w\) subsample. By the predictable filtration 5 , conditional on \((\mathcal{F}_{i-1},X_i,W_i=w)\), the noise \(\xi_i:=Z_i-m^\star(X_i)\) has \(\mathbb{E}[\xi_i\mid\mathcal{F}_{i-1},X_i,W_i=w]=0\) and is sub-exponential with parameter \(\tau\) uniform in \(i,w\) (Assumption 2).

8.1.0.1 Quasi-likelihood and pseudo-posterior.

The teacher uses the Gaussian quasi-likelihood \(L_N(f) \propto \exp\bigl\{-(2\bar\sigma^2)^{-1}\sum_{i:W_i=w}(Z_i-f(X_i))^2\bigr\}.\) We do not assume the noise is Gaussian; the squared-loss likelihood is treated as a quasi-likelihood whose population minimizer is \(m^\star\). The contraction rate is verified by a likelihood-ratio argument that uses sub-exponential noise concentration (Lemma 1) instead of Gaussian likelihood ratios.

8.1.0.2 Prior.

For fixed smoothness \(\beta\in[\beta_{\min},\beta_{\max}]\) matched to the target, the Gaussian-series prior is \(f=\sum_{j\ge1}\theta_j\psi_j\) with \(\theta_j\sim N(0,\rho_j(\beta))\), \(\rho_j(\beta)=j^{-1-2\beta/d}\) up to constants (Section 2).

8.1.0.3 Target rate.

Define \[\label{eq:target-rate} J_N := \bigl\lceil(N/\log N)^{d/(2\beta+d)}\bigr\rceil, \qquad \varepsilon_N := N^{-\beta/(2\beta+d)}(\log N)^A,\tag{10}\] for a constant \(A>0\) to be chosen large enough (depending only on structural constants). Note \(J_N\log N\asymp N\varepsilon_N^2\).

8.2 Step 1: Truncation bias↩︎

Idea. The smoothness assumption forces high-frequency coefficients \(\theta_j^\star\) to decay polynomially. Truncating the basis at \(J_N\) therefore loses only a power of \(J_N\) in \(L_2\), and our choice of \(J_N\) matches that loss to the target rate \(\varepsilon_N^2\).

Let \(m_J^\star(x)=\sum_{j\le J_N}\theta_j^\star\psi_j(x)\) be the projection of \(m^\star\) onto the first \(J_N\) basis functions. Bounded density gives \(\|f\|_{L_2(P_X)}^2\le C_X\|f\|_{\rm Lebesgue}^2\) for any \(f\in L_2\), and the cosine basis is Lebesgue-orthonormal, so \[\label{eq:trunc-1} \|m^\star-m_J^\star\|_{L_2(P_X)}^2 \le C_X\sum_{j>J_N}(\theta_j^\star)^2.\tag{11}\] The Sobolev norm \(\sum_j j^{2\beta/d}(\theta_j^\star)^2\le R^2\) controls the high-frequency tail by pulling out the smallest weight on the right tail: \[\label{eq:trunc-2} \sum_{j>J_N}(\theta_j^\star)^2 \;\le\; J_N^{-2\beta/d}\!\sum_{j>J_N}\!j^{2\beta/d}(\theta_j^\star)^2 \;\le\; R^2\,J_N^{-2\beta/d}.\tag{12}\] With \(J_N\asymp(N/\log N)^{d/(2\beta+d)}\), the right-hand side is \(\asymp \varepsilon_N^2\), so \(\|m^\star-m_J^\star\|_{L_2(P_X)}\lesssim \varepsilon_N\). This is the bias-half of the bias–variance tradeoff 9 .

8.3 Step 2: Prior small-ball↩︎

Idea. We need \(\Pi(\|f-m^\star\|_{L_2(P_X)}\le c\varepsilon_N)\ge e^{-CN\varepsilon_N^2}\). Decompose \(f-m^\star\) into a low-frequency part (first \(J_N\) coordinates) and a high-frequency tail. For the low-frequency part, we need the Gaussian prior to put adequate mass on a small ball around \(\theta^\star_{1:J_N}\) — this follows from Anderson’s inequality and is determined by (i) how spread the prior is on each coordinate (\(J_N\log N\) terms) and (ii) how far \(\theta^\star\) is from zero on each coordinate (the \(\sum (\theta_j^\star)^2/\rho_j(\beta)\) “signal-to-prior” term). The Sobolev assumption controls (ii) so that the sum is at most \(J_NR^2\asymp N\varepsilon_N^2\) — the same order as (i). The high-frequency tail is small in expectation because the prior variances are summable past \(J_N\), so a Markov bound gives constant probability.

We bound below \(\Pi_\beta(\|f-m^\star\|_{L_2(P_X)}\le c\varepsilon_N)\).

Low-frequency block. For \(a\in\mathbb{R}^{J_N}\) with \(\sum_{j\le J_N}(a_j-\theta_j^\star)^2\le c\varepsilon_N^2\), the corresponding \(g_a=\sum_{j\le J_N}a_j\psi_j\) satisfies \(\|g_a-m_J^\star\|_{L_2(P_X)} \le \sqrt{C_X}\,\sqrt{c}\,\varepsilon_N.\) The Gaussian small-ball lower bound for a product Gaussian measure (Anderson’s inequality, see [28]) gives \[\label{eq:small-ball-low} -\log \Pi_\beta\!\left(\sum_{j\le J_N}(\theta_j-\theta_j^\star)^2\le c\varepsilon_N^2\right) \le C_1\!\left(J_N\log\frac{J_N}{c\varepsilon_N^2}+\sum_{j\le J_N}\frac{(\theta_j^\star)^2}{\rho_j(\beta)}\right).\tag{13}\] For \(j\le J_N\), \(\rho_j(\beta)^{-1}=j^{1+2\beta/d}\le J_N j^{2\beta/d}\), so \[\sum_{j\le J_N}\frac{(\theta_j^\star)^2}{\rho_j(\beta)} \le J_N\sum_{j\le J_N}j^{2\beta/d}(\theta_j^\star)^2 \le J_N R^2.\] Combining with 13 and \(J_N\log(J_N/\varepsilon_N^2)\le C J_N\log N\le C N\varepsilon_N^2\) for \(A\) large, \[\label{eq:small-ball-low-final} -\log \Pi_\beta\!\left(\sum_{j\le J_N}(\theta_j-\theta_j^\star)^2\le c\varepsilon_N^2\right) \le C N\varepsilon_N^2.\tag{14}\]

High-frequency block. For the tail \(\sum_{j>J_N}\theta_j^2\), \[\mathbb{E}_\beta\sum_{j>J_N}\theta_j^2 = \sum_{j>J_N}\rho_j(\beta) \asymp \sum_{j>J_N}j^{-1-2\beta/d} \asymp J_N^{-2\beta/d} \lesssim \varepsilon_N^2.\] Markov’s inequality gives \(\Pi_\beta(\sum_{j>J_N}\theta_j^2\le C\varepsilon_N^2)\ge 1/2.\) Combining the two blocks (independence under the Gaussian-series prior), \[\label{eq:prior-mass-final} \Pi_\beta\!\left(\|f-m^\star\|_{L_2(P_X)}\le C_2\varepsilon_N\right) \ge \tfrac12\exp(-CN\varepsilon_N^2).\tag{15}\]

8.4 Step 3: Sieve↩︎

Idea. The full prior assigns nontrivial mass to functions with arbitrarily large coefficients; we cannot cover the entire support by finitely many balls. We carve out a sieve \(\mathcal{F}_n\) small enough to have entropy \(O(N\varepsilon_N^2)\) — exactly the budget allowed by the exponential test errors — yet large enough that the prior tail outside is exponentially small. The two bounds (\(\Pi(\mathcal{F}_n^c)\le e^{-(C+4)N\varepsilon_N^2}\) and entropy \(\le N\varepsilon_N^2\)) together with the test errors of Step 4 suffice for posterior concentration.

Define the sieve \[\mathcal{F}_n := \Bigl\{f=\sum_{j\ge 1}a_j\psi_j: \sum_{j\le J_N}a_j^2\le R_n^2,\, \sum_{j>J_N}a_j^2\le \varepsilon_N^2,\, \|f\|_\infty\le B_n\Bigr\},\] with \(R_n=N^A\) and \(B_n=\sqrt{\kappa J_N}R_n\) to absorb basis-envelope \(L_\infty\) bounds. We verify two properties.

Prior tail outside the sieve. \(\Pi_\beta(\mathcal{F}_n^c) \le \Pi_\beta(\sum_{j\le J_N}a_j^2>R_n^2) +\Pi_\beta(\sum_{j>J_N}a_j^2>\varepsilon_N^2) \le \exp(-CR_n^2)+\exp(-CN\varepsilon_N^2)\) by Gaussian tail and Markov on the truncated sum. With \(R_n^2\gg N\varepsilon_N^2\), this is at most \(\exp(-(C+4)N\varepsilon_N^2)\).

Entropy. The \(L_2(P_X)\) covering entropy of \(\mathcal{F}_n\) at scale \(\varepsilon\) satisfies \(\log N(\varepsilon,\mathcal{F}_n,L_2(P_X)) \le J_N\log(C R_n/\varepsilon) + \log\!\binom{J_{\max,n}}{J_N} \lesssim J_N\log N \lesssim N\varepsilon_N^2,\) since the high-frequency block contributes only \(\varepsilon\)-balls of fixed radius and the low-frequency block is a \(J_N\)-dimensional Euclidean ball.

8.5 Step 4: Tests↩︎

Idea. A test \(T_f\) accepts \(m^\star\) when the empirical squared residual \(\frac{1}{N}\sum(Z_i-f)^2\) is too large compared to \(\frac{1}{N}\sum(Z_i-m^\star)^2\). By straightforward algebra the difference of these two empirical sums equals \(\|f-m^\star\|_N^2\) minus an inner product between the noise \(\xi_i\) and \(f-m^\star\). The first term is \(\asymp \rho^2\) when \(f\) is \(\rho\)-separated from \(m^\star\), by Gram concentration (Lemma 9); the noise inner product is mean-zero and sub-exponential, so a Bernstein-MDS bound shows it cannot exceed \(\rho^2/4\) except with probability \(e^{-cN\rho^2}\). Hence the test makes both kinds of errors at level \(e^{-cN\rho^2}\), and a \(\rho\)-cover of the sieve costs \(e^{N\varepsilon_N^2}\) tests by entropy — affordable when \(M\) in \(\rho=M\varepsilon_N\) is large.

We construct tests for the alternative \(\{f\in\mathcal{F}_n:\|f-m^\star\|_{L_2(P_X)}>M\varepsilon_N\}\) via Lemma 4. Fix one \(f\) in this set and define the test statistic \[\widehat L_N(f) := \frac{1}{N}\sum_{i:W_i=w}\bigl[(Z_i-f(X_i))^2-(Z_i-m^\star(X_i))^2\bigr].\] Decompose: \[\label{eq:test-decomp} \widehat L_N(f) = \|f-m^\star\|_N^2 - \frac{2}{N}\sum_{i:W_i=w}\xi_i\bigl(f(X_i)-m^\star(X_i)\bigr).\tag{16}\]

Empirical-vs-population norm. On the Gram event \(\mathcal{G}_n\) (Lemma 10), the restriction of \(\|\cdot\|_N\) to the \(J_{\max,n}\)-dimensional active class satisfies \(\tfrac12 \|f-m^\star\|_{L_2(P_X)}^2 \le \|f-m^\star\|_N^2 \le \tfrac32\|f-m^\star\|_{L_2(P_X)}^2,\) uniformly in \(f\in\mathcal{F}_n\) provided \(N\ge C J_{\max,n}\log n\). Hence \[\label{eq:empirical-norm} \|f-m^\star\|_N^2 \ge \tfrac12 \|f-m^\star\|_{L_2(P_X)}^2.\tag{17}\]

Noise inner product. The sequence \(D_i:=I_i(w)\xi_i(f(X_i)-m^\star(X_i))\), \(1\le i\le t\), is an MDS w.r.t. \(\mathcal{F}_i^W\) because \(\mathbb{E}[\xi_i\mid\mathcal{F}_{i-1},X_i,W_i=w]=0\). Its predictable variance is \[\mathbb{E}[D_i^2\mid\mathcal{F}_{i-1}] = \mathbb{E}\!\bigl[I_i(w)(f(X_i)-m^\star(X_i))^2\mathbb{E}[\xi_i^2\mid\mathcal{F}_{i-1},X_i,W_i=w]\,\big|\,\mathcal{F}_{i-1}\bigr] \le \tau^2\,\|f-m^\star\|_{P_X}^2,\] since \(\mathbb{E}[\xi_i^2\mid\mathcal{F}_{i-1},X_i,W_i=w]\le \tau^2\) uniformly. Each \(D_i\) is sub-exponential with \(\|D_i\|_{\psi_1\mid\mathcal{F}_{i-1}}\le \tau B_n\) (boundedness of \(f-m^\star\) on the sieve). Apply Lemma 1 with \(u=cN\rho^2\), \(V_t\le N\tau^2\rho^2\), \(K=\tau B_n\): \[\label{eq:noise-bernstein} \Pr\!\left(\Bigl|\tfrac1N\sum_{i:W_i=w}\xi_i(f(X_i)-m^\star(X_i))\Bigr|>\rho^2/4\right) \le 2\exp\!\left(-c\min\!\Bigl\{\tfrac{N\rho^2}{\tau^2},\tfrac{N\rho}{\tau B_n}\Bigr\}\right).\tag{18}\] Set \(\rho=\|f-m^\star\|_{L_2(P_X)}>M\varepsilon_N\). Since \(B_n=\mathrm{poly}(N)\) and \(N\rho\ge N M\varepsilon_N\), the second term in the minimum dominates only when \(M\varepsilon_N\) is too small; choosing \(A\) in \(\varepsilon_N\) large enough so that \(NM\varepsilon_N/(\tau B_n)\ge cN\varepsilon_N^2\), the bound reduces to \(\exp(-cN\rho^2/\tau^2)\).

Test definition and errors. Define \(T_f:=\mathbf{1}\{\widehat L_N(f)\le -\rho^2/4\}\).

Type-I error under \(m^\star\). On \(\mathcal{G}_n\cap\{\eqref{eq:noise-bernstein}\text{ holds}\}\), combining 16 , 17 , and the Bernstein bound, \[\widehat L_N(f) \ge \|f-m^\star\|_N^2 -\tfrac{\rho^2}{4} \ge \tfrac12\rho^2-\tfrac{\rho^2}{4} = \tfrac{\rho^2}{4}.\] Hence \(T_f=0\) on this event. The complement has probability \(\le 3\exp(-cN\rho^2/\tau^2)\).

Type-II error under any \(g\) with \(\|g-m^\star\|_{L_2(P_X)}>\rho\). Symmetric argument: under \(g\), \(\widehat L_N(f)\) is \(\mathbb{E}_g\)-mean \(\|f-g\|_N^2-\|m^\star-g\|_N^2\) (a constant offset) shifted by a similar sub-exponential MDS. The same Bernstein bound shows \(\widehat L_N(f)\le -\rho^2/4\) with high probability when \(\|f-g\|<\rho/2<\|m^\star-g\|/2\), in particular when \(g=f\) itself. The detailed algebra is identical to the type-I argument and uses the empirical-norm bound on \(f-g\) and on \(g-m^\star\). The error is again \(\le 3\exp(-cN\rho^2/\tau^2)\).

Cover and union. Take \(\rho=M\varepsilon_N\) and let \(\mathcal{N}_\rho\) be a \(\rho/4\)-cover of \(\mathcal{F}_n\cap\{\|f-m^\star\|_{L_2(P_X)}>M\varepsilon_N\}\). By Step 3, \(\log|\mathcal{N}_\rho|\lesssim N\varepsilon_N^2\). Define \(\varphi_N=\max_{f\in\mathcal{N}_\rho}T_f\). Union bounds give \[\label{eq:tests-final} \mathbb{E}_{m^\star}\varphi_N\le 3|\mathcal{N}_\rho|e^{-cM^2N\varepsilon_N^2}, \qquad \sup_{f:\|f-m^\star\|_{L_2(P_X)}>2M\varepsilon_N} \mathbb{E}_f(1-\varphi_N) \le 3 e^{-cM^2N\varepsilon_N^2}.\tag{19}\] With \(M\) large enough so that \(cM^2-C\ge 1\) (where \(C\) is the entropy constant), both bounds are \(\le e^{-N\varepsilon_N^2}\).

8.6 Step 5: Posterior denominator↩︎

Idea. Bayes’ rule writes the posterior as a ratio \(\Pi(\cdot\mid\mathcal{D}_N)=N_N(\cdot)/D_N\). The numerator is small for alternatives by the tests of Step 4; for the contraction inequality to bite we also need the denominator \(D_N\) not to be too small. Restricting the integral defining \(D_N\) to the small-ball \(\{\|f-m^\star\|\le c\varepsilon_N\}\) and noting that on this ball the log-likelihood ratio \(\ell_N(f)-\ell_N(m^\star)\) is at most \(O(N\varepsilon_N^2)\) in absolute value (small empirical bias, controlled noise inner product) gives \(D_N\ge e^{-CN\varepsilon_N^2}\cdot\Pi(\text{small ball})\ge e^{-(C+C)N\varepsilon_N^2}\) by Step 2.

Let \(\ell_N(f):=-(2\bar\sigma^2)^{-1}\sum_{i:W_i=w}(Z_i-f(X_i))^2\) be the quasi log-likelihood. Define \[D_N := \int e^{\ell_N(f)-\ell_N(m^\star)}\,d\Pi_\beta(f).\] We bound below \(D_N\) on \(\mathcal{G}_n\).

Restriction to the small ball. For \(f\) with \(\|f-m^\star\|_{L_2(P_X)}\le c\varepsilon_N\), the squared-error gap is \[\label{eq:llh-gap} \ell_N(f)-\ell_N(m^\star) = -\frac{N}{2\bar\sigma^2}\,\|f-m^\star\|_N^2 + \frac{1}{\bar\sigma^2}\sum_{i:W_i=w}\xi_i\bigl(f(X_i)-m^\star(X_i)\bigr).\tag{20}\] On \(\mathcal{G}_n\), \(\|f-m^\star\|_N^2\le \tfrac32\|f-m^\star\|_{L_2(P_X)}^2\le \tfrac32 c^2\varepsilon_N^2\). Apply Lemma 1 with the same parameters as in Step 4 to the noise inner product, restricted to the small-ball cover at scale \(c\varepsilon_N/4\) of size \(\exp(N\varepsilon_N^2)\): with probability \(\ge 1-\exp(-CN\varepsilon_N^2)\), uniformly, \(\bigl|\sum\xi_i(f(X_i)-m^\star(X_i))\bigr|/N \le c\varepsilon_N^2\tau.\) Hence \(\ell_N(f)-\ell_N(m^\star)\ge -CN\varepsilon_N^2\) uniformly over the small ball. Combining with 15 , \[\label{eq:denom} D_N \ge e^{-CN\varepsilon_N^2}\,\Pi_\beta(\|f-m^\star\|_{L_2(P_X)}\le c\varepsilon_N) \ge e^{-(C+C)N\varepsilon_N^2}.\tag{21}\]

8.7 Step 6: Posterior numerator↩︎

Let \(B_N^c:=\{f:\|f-m^\star\|_{L_2(P_X)}>2M\varepsilon_N\}\). We decompose along the sieve \(\mathcal{F}_n\) from Step 3: \[\label{eq:posterior-decomp} \Pi_\beta(B_N^c\mid\mathcal{D}_N) \le \underbrace{\varphi_N}_{\text{type I error}} + \underbrace{\frac{(1-\varphi_N)\int_{B_N^c\cap\mathcal{F}_n}e^{\ell_N(f)-\ell_N(m^\star)}\,d\Pi_\beta(f)}{D_N}}_{\text{tested alternatives}} + \underbrace{\frac{\int_{\mathcal{F}_n^c}e^{\ell_N(f)-\ell_N(m^\star)}\,d\Pi_\beta(f)}{D_N}}_{\text{prior tail outside sieve}}.\tag{22}\] The third term is bounded by Markov on the likelihood ratio: \(\mathbb{E}_{m^\star}\!\int_{\mathcal{F}_n^c}e^{\ell_N(f)-\ell_N(m^\star)}\,d\Pi_\beta(f) \le \Pi_\beta(\mathcal{F}_n^c)\le e^{-(C+4)N\varepsilon_N^2}\), which divided by \(D_N\ge e^{-(C+2)N\varepsilon_N^2}\) from Step 5 gives \(\le e^{-2N\varepsilon_N^2}\).

For the second term in 22 , by Fubini and 19 , \[\mathbb{E}_{m^\star}\!\!\int_{B_N^c\cap\mathcal{F}_n}\!(1-\varphi_N)\,e^{\ell_N(f)-\ell_N(m^\star)}\,d\Pi_\beta(f) \;=\; \int_{B_N^c\cap\mathcal{F}_n}\!\mathbb{E}_f[1-\varphi_N]\,d\Pi_\beta(f) \;\le\; e^{-cM^2 N\varepsilon_N^2},\] which divided by \(D_N\ge e^{-(C+2)N\varepsilon_N^2}\) gives \(\le e^{-(cM^2-C-2)N\varepsilon_N^2}\). The first term \(\varphi_N\) is itself \(\le e^{-cM^2N\varepsilon_N^2}\) by 19 .

8.8 Step 7: Conclusion↩︎

Combine: with \(M\) chosen so that \(cM^2-C-2\ge 1\) and on the intersection of the Gram event \(\mathcal{G}_n\) and the denominator event, \[\Pi_\beta(\|f-m^\star\|_{L_2(P_X)}>2M\varepsilon_N\mid \mathcal{D}_N) \le \mathbb{E}_{m^\star}\varphi_N+e^{-N\varepsilon_N^2}+e^{-2N\varepsilon_N^2} \to 0.\] This proves Proposition 1 with rate \(\varepsilon_N=N^{-\beta/(2\beta+d)}(\log N)^A\).

8.9 Step 8: Specialization to four targets↩︎

Apply Steps 1–7 to the four cases:

1. \(w=0\), \(h=\mu\): \(Z_i=Y_i\), \(m^\star=\mu_0^\star\), \(\beta=\beta_{0,\mu}^\star\), \(N=N_{t,0}\).

2. \(w=0\), \(h=q\): \(Z_i=Y_i^2\), \(m^\star=q_0^\star\), \(\beta=\beta_{0,q}^\star\), \(N=N_{t,0}\).

3. \(w=1\), \(h=\mu\): \(Z_i=Y_i\), \(m^\star=\mu_1^\star\), \(\beta=\beta_{1,\mu}^\star\), \(N=N_{t,1}\).

4. \(w=1\), \(h=q\): \(Z_i=Y_i^2\), \(m^\star=q_1^\star\), \(\beta=\beta_{1,q}^\star\), \(N=N_{t,1}\).

The conditional sub-exponential property carries through: by Assumption 2, \(Y_i^2-q_w^\star(X_i)\) is sub-exponential under the predictable filtration, with norm controlled by the fourth moment \(C_q\). The Bayesian Gram event \(\mathcal{G}_n\) is shared across all four applications. Each rate becomes \(\varepsilon_{w,h,t} = N_{t,w}^{-\beta_{w,h}^\star/(2\beta_{w,h}^\star+d)}(\log N_{t,w})^A,\) and the contraction statements in Proposition 1 follow.\(\square\)

9 Proof of Proposition 2↩︎

9.0.0.1 Goal.

Show that the posterior-Neyman propensity \(e_t^{\rm B}\) converges in \(L_2(P_X)\) to the oracle Neyman propensity \(e^\star\).

9.0.0.2 Strategy.

Two short steps:

1. Variance contraction. The Bayesian residual-variance belief \(\bar v_{w,t}=\mathbb{E}_{\Pi_t}[\Pi_{[c_V,C_V]}(q_w-\mu_w^2)]\) contracts to \(v_w^\star\) in \(L_2(P_X)\). This is essentially the chain rule applied to the contractions of \(\mu_w\) and \(q_w\) from Proposition 1, with care for the conditional Jensen gap caused by the clip and the square.

2. Lipschitz Neyman map. The propensity is a smooth function of \((v_0,v_1)\) on the bounded box \([c_V,C_V]^2\). So once the inputs are close, the outputs are close.

The clip \(\mathrm{clip}_{[\eta,1-\eta]}\) is non-expansive, so the proof ignores it.

9.1 Step 1: posterior variance belief contracts↩︎

Recall the variance projection \(v_w(x)=\Pi_{[c_V,C_V]}\!\bigl\{q_w(x)-\mu_w(x)^2\bigr\}\) and the posterior variance belief \(\bar v_{w,t}(x)=\mathbb{E}_{\Pi_t}[v_w(x)\mid\mathcal{H}_t].\)

Proof. Let \(\widetilde{\mu}_w(x)=\mathbb{E}_{\Pi_t}[\mu_w(x)\mid\mathcal{H}_t]\) and \(\widetilde{q}_w(x)=\mathbb{E}_{\Pi_t}[q_w(x)\mid\mathcal{H}_t]\) denote the posterior means. Define the (un-clipped) posterior variance belief \(\widetilde{v}_w(x):=\widetilde{q}_w(x)-\widetilde{\mu}_w(x)^2\). We bound \(\|\bar v_{w,t}-v_w^\star\|_{L_2(P_X)}\) in two steps.

(a) Uncentered approximation. Add and subtract \(\widetilde{v}_w-(\widetilde{\mu}_w^2-\mathbb{E}_{\Pi_t}[\mu_w^2])\) inside \(\bar v_{w,t}\): \[\begin{align} \bar v_{w,t}(x) &= \mathbb{E}_{\Pi_t}[\Pi_{[c_V,C_V]}(q_w(x)-\mu_w(x)^2)\mid\mathcal{H}_t]\\ &= \Pi_{[c_V,C_V]}\bigl(\widetilde{q}_w(x)-\mathbb{E}_{\Pi_t}[\mu_w(x)^2\mid\mathcal{H}_t]\bigr) +\mathrm{R}_t(x), \end{align}\] where the residual \(\mathrm{R}_t(x)\) accounts for the conditional Jensen gap between the posterior expectation of the projection and the projection of the posterior expectation. The clip is 1-Lipschitz, so by Jensen’s inequality \(|\mathrm{R}_t(x)|\le \mathbb{E}_{\Pi_t}[|q_w(x)-\mu_w(x)^2-\widetilde{q}_w(x)+\mathbb{E}_{\Pi_t}\mu_w^2|\mid\mathcal{H}_t]\). This residual is dominated by the conditional standard deviations \(\mathrm{SD}_{\Pi_t}(q_w(x))+\mathrm{SD}_{\Pi_t}(\mu_w^2(x))\), which both vanish in \(L_2(P_X)\) by Proposition 1 (since posterior contraction implies posterior variance contraction at the same rate up to a constant factor; this is the standard "posterior second-moment contraction" corollary of small-ball prior mass).

(b) Plug-in error. By the bias–variance decomposition of the posterior squared-mean, \(\mathbb{E}_{\Pi_t}[\mu_w(x)^2\mid\mathcal{H}_t] = \widetilde{\mu}_w(x)^2+\mathrm{Var}_{\Pi_t}[\mu_w(x)\mid\mathcal{H}_t].\) Hence \[\widetilde{q}_w(x)-\mathbb{E}_{\Pi_t}[\mu_w(x)^2\mid\mathcal{H}_t] = \widetilde{q}_w(x)-\widetilde{\mu}_w(x)^2-\mathrm{Var}_{\Pi_t}[\mu_w(x)\mid\mathcal{H}_t].\] So \[\begin{align} \bar v_{w,t}(x) &= \Pi_{[c_V,C_V]}\!\bigl(\widetilde{q}_w(x)-\widetilde{\mu}_w(x)^2-\mathrm{Var}_{\Pi_t}[\mu_w(x)\mid\mathcal{H}_t]\bigr) +\mathrm{R}_t(x). \end{align}\] The clip is 1-Lipschitz, hence \[\begin{align} |\bar v_{w,t}(x)-v_w^\star(x)| &\le |\widetilde{q}_w(x)-q_w^\star(x)| +|\widetilde{\mu}_w(x)^2-\mu_w^\star(x)^2|\\ &\quad+\mathrm{Var}_{\Pi_t}[\mu_w(x)\mid\mathcal{H}_t] +|\mathrm{R}_t(x)|. \end{align}\]

(c) Bound the four terms in \(L_2(P_X)\).

• \(\|\widetilde{q}_w-q_w^\star\|_{L_2(P_X)}\to 0\) by Proposition 1 applied to \(q\).

• \(\widetilde{\mu}_w^2-\mu_w^{\star 2}=(\widetilde{\mu}_w-\mu_w^\star)(\widetilde{\mu}_w+\mu_w^\star)\). On the high-probability sieve from Appendix 8, \(|\widetilde{\mu}_w|\le B_\mu\) uniformly, and \(|\mu_w^\star|\le B_\mu\) by Assumption 1 (the fourth-moment bound implies a uniform \(L_\infty\) bound up to a vanishing event), so \(|\widetilde{\mu}_w^2-\mu_w^{\star 2}|\le 2B_\mu|\widetilde{\mu}_w-\mu_w^\star|.\) Thus \(\|\widetilde{\mu}_w^2-\mu_w^{\star 2}\|_{L_2(P_X)}\le 2B_\mu\|\widetilde{\mu}_w-\mu_w^\star\|_{L_2(P_X)}\to 0\).

• \(\mathrm{Var}_{\Pi_t}[\mu_w\mid\mathcal{H}_t]\to 0\) in \(L_2(P_X)\) because posterior contraction implies posterior variance contraction at rate \(\varepsilon_{\mu,w,t}^2\).

• \(|\mathrm{R}_t|\to 0\) in \(L_2(P_X)\) for the same reason.

Combining the four bounds gives Lemma 11. \(\square\)

9.2 Step 2: Lipschitz Neyman map↩︎

Proof. \(\Phi\) is differentiable on \([c_V,C_V]^2\). Compute \[\frac{\partial\Phi}{\partial v_0} = -\frac{\sqrt{v_1}}{2\sqrt{v_0}\,(\sqrt{v_0}+\sqrt{v_1})^2}, \qquad \frac{\partial\Phi}{\partial v_1} = \frac{\sqrt{v_0}}{2\sqrt{v_1}\,(\sqrt{v_0}+\sqrt{v_1})^2}.\] Both are bounded in absolute value by \(\sqrt{C_V}/(4 c_V (\sqrt{c_V})\cdot\sqrt{c_V})\le L_{\rm Ney}\) on \([c_V,C_V]^2\). Mean-value theorem gives the Lipschitz bound. \(\square\)

9.3 Step 3: design convergence↩︎

By definition, \(e_t^{\rm B}(x) = \mathrm{clip}_{[\eta,1-\eta]}\Phi(\bar v_{0,t-1}(x),\bar v_{1,t-1}(x))\) and \(e^\star(x)=\Phi(v_0^\star(x),v_1^\star(x))\). By Lemma 12, \[|e_t^{\rm B}(x)-e^\star(x)| \le L_{\rm Ney}\Bigl(|\bar v_{0,t-1}(x)-v_0^\star(x)|+|\bar v_{1,t-1}(x)-v_1^\star(x)|\Bigr).\] Squaring and integrating against \(P_X\), \[\|e_t^{\rm B}-e^\star\|_{L_2(P_X)}^2 \le 2L_{\rm Ney}^2 \sum_{w\in\{0,1\}} \|\bar v_{w,t-1}-v_w^\star\|_{L_2(P_X)}^2,\] which goes to zero by Lemma 11.\(\square\)

10 Proof of Theorem 3↩︎

The decisive feature of the design analyzed here is that the propensity \(e_t(\cdot)\) is known and predictable —— \(e_t\) is the actual Bernoulli parameter used to sample \(W_t\). Under this design, AIPW with predictable nuisance estimates is per-round unbiased and the second-order nuisance–propensity cross term that usually drives the \(o_p(n^{-1/2})\) double-robust rate disappears entirely. As a consequence, mere \(L_2(P_X)\) consistency of the posterior mean (Proposition 1) is enough; no \(\beta_{\min}>d/2\) assumption is needed. We follow the AIPW asymptotic normality argument of [5] in the adaptive-design setting, specialized to our predictable Bayesian-teacher posterior means and known clipped propensities.

10.1 Setup↩︎

The AIPW estimator is \[\label{eq:aipw} \widehat\tau_{\rm AIPW} = \frac{1}{n}\sum_{t=1}^n \psi_t(\widehat\mu_{0,t-1},\widehat\mu_{1,t-1},e_t),\tag{23}\] \[\psi_t(\mu_0,\mu_1,e) := \mu_1(X_t)-\mu_0(X_t) +\frac{W_t(Y_t-\mu_1(X_t))}{e} -\frac{(1-W_t)(Y_t-\mu_0(X_t))}{1-e},\] where \(\widehat\mu_{w,t-1}\) is the posterior mean computed from \(\mathcal{F}_{t-1}\) (the running predictable posterior). By construction \(\widehat\mu_{w,t-1}\) and \(e_t\) are \(\mathcal{F}_t^X\)-measurable. For batch inference one may equivalently use \(\widehat\mu_w\) trained on the full trajectory and recover the same conclusion via cross-fitting; see [5] for details.

The oracle predictable score is \[\label{eq:psi-pred} \psi_t^{\rm pred} := (\mu_1^\star-\mu_0^\star)(X_t)-\tau^\star +\frac{W_t-e_t}{e_t(1-e_t)}\bigl[(1-e_t)(Y_t-\mu_1^\star(X_t))-e_t(Y_t-\mu_0^\star(X_t))\bigr].\tag{24}\]

Proof. The bias term \((\mu_1^\star-\mu_0^\star)(X_t)-\tau^\star\) has \(P_X\)-mean zero since \(X_t\sim P_X\) independent of \(\mathcal{F}_t\). The IPW correction has predictable mean zero because \(\mathbb{E}[W_t\mid\mathcal{F}_t^X]=e_t\), and an explicit \(W_t\)-conditioning gives ?? (cf.[5]). \(\square\)

10.2 Decomposition: predictable MDS plus a vanishing nuisance MDS↩︎

Proof. Add and subtract \(\psi_t(\mu_0^\star,\mu_1^\star,e_t)=\psi_t^{\rm pred}+\tau^\star\) inside 23 . The remainder is exactly \(R_n^{\rm (nuis)}\). Predictable mean-zero of the centered IPW factor follows from \(\mathbb{E}[W_t\mid\mathcal{F}_t^X]=e_t\). \(\square\)

Proof. By orthogonality of the MDS terms, \[\mathbb{E}[(R_n^{\rm (nuis)})^2] = \frac{1}{n}\sum_{t=1}^n \mathbb{E}\!\left[(\widehat\mu_{w,t-1}-\mu_w^\star)^2(X_t)\cdot\mathrm{Var}(1-W_t/e_t\mid\mathcal{F}_t^X)\right] \le \frac{C}{\eta^2}\cdot\frac{1}{n}\sum_{t=1}^n\mathbb{E}\|\widehat\mu_{w,t-1}-\mu_w^\star\|_{L_2(P_X)}^2,\] since \(\mathrm{Var}(W_t/e_t\mid\mathcal{F}_t^X)=(1-e_t)/e_t\le 1/\eta-1\). Cesàro averaging on the per-round MSE — which goes to zero under Proposition 1 — yields \(\mathbb{E}[(R_n^{\rm (nuis)})^2]\to 0\), hence \(R_n^{\rm (nuis)}=o_P(1)\). \(\square\)

10.2.0.1 Why no rate condition is needed.

The standard double machine learning bound \(|R_n|\le \sqrt n\|\widehat\mu_w-\mu_w^\star\|\,\|\widehat e-e^\star\|\) forces a product rate because \(\widehat e\) is estimated from data. Here \(e_t\) is the actual Bernoulli parameter — there is nothing to estimate. The IPW correction with the true \(e_t\) is per-round unbiased given \(\mathcal{F}_t^X\), so the nuisance term collapses to a single MDS factor, and its \(L_2\) size is governed by \(\mathbb{E}\|\widehat\mu_{w,t-1}-\mu_w^\star\|^2\) alone. This is precisely the gain analyzed by [5] for adaptive designs with known propensities.

10.3 Triangular-array martingale CLT for \(M_n^{\rm pred}\)↩︎

We invoke Lemma 6:

• Conditional variance. By Proposition 2 and dominated convergence (using \(g(x,\cdot)\) continuous and bounded on \([\eta,1-\eta]\)), \(\tfrac1n\sum_{t=1}^n g(X_t,e_t) \xrightarrow{P} V^\star:=\mathbb{E}_{P_X}[g(X,e^\star(X))].\)

• Conditional Lindeberg. For \(\delta>0\), \(\mathbb{E}[(\psi_t^{\rm pred})^4\mid\mathcal{F}_t^X]\le C/\eta^4\) by Assumption 1 (fourth-moment bound). Cauchy–Schwarz gives the Lindeberg sum \(\le n^{-1}\delta^{-2}C/\eta^4\to 0\).

Hence \(M_n^{\rm pred}\rightsquigarrow N(0,V^\star)\) stably.

10.4 Identifying \(V^\star\) as the Hahn bound under Neyman↩︎

Proof. Substitute \(e=e^\star\) and \(1-e=\sqrt{v_0^\star}/(\sqrt{v_0^\star}+\sqrt{v_1^\star})\) into ?? : \(v_1^\star/e^\star+v_0^\star/(1-e^\star) = \sqrt{v_1^\star}(\sqrt{v_0^\star}+\sqrt{v_1^\star})+\sqrt{v_0^\star}(\sqrt{v_0^\star}+\sqrt{v_1^\star}) =(\sqrt{v_0^\star}+\sqrt{v_1^\star})^2.\) Hahn’s efficient-influence-function variance is \(\mathbb{E}[v_1^\star/e+v_0^\star/(1-e)+(\mu_1^\star-\mu_0^\star-\tau^\star)^2]\), and by Cauchy-Schwarz \(a^2/e+b^2/(1-e)\ge (a+b)^2\) with equality at \(e=a/(a+b)\), so the minimum is attained at the Neyman propensity. \(\square\)

10.5 Conclusion↩︎

By Proposition 8, \(\sqrt n(\widehat\tau_{\rm AIPW}-\tau^\star)=M_n^{\rm pred}+R_n^{\rm (nuis)}\). Lemma 14 gives \(R_n^{\rm (nuis)}=o_P(1)\) from Proposition 1. The MCLT in Section 10.3 gives \(M_n^{\rm pred}\rightsquigarrow N(0,V^\star)\). Slutsky and Lemma 15 yield \(\sqrt n(\widehat\tau_{\rm AIPW}-\tau^\star)\rightsquigarrow N(0,V^\star),\) with \(V^\star\) the Hahn semiparametric efficiency bound under Neyman allocation. \(\square\)

11 Proof of Theorem 4↩︎

11.0.0.1 Goal.

The Bayesian teacher does not know the true smoothness \(\beta^\star\). We show that placing a hyperprior \(\Pi_\beta\) on \([\beta_{\min},\beta_{\max}]\) makes the resulting hierarchical posterior contract at the oracle rate \(\varepsilon_N^{\rm ad}=N^{-\beta^\star/(2\beta^\star+d)}(\log N)^A\), up to logarithmic factors. The Bayesian model selects the right complexity scale on its own.

11.0.0.2 Why hierarchical Bayes adapts: shape of the marginal likelihood.

For each smoothness \(\beta\), the marginal likelihood \(D_N^{(\beta)}=\int e^{\ell_N(f)}\,d\Pi_0^{(\beta)}(f)\) aggregates the likelihood across all \(f\) drawn from the conditional prior. Heuristically:

• For \(\beta\approx \beta^\star\): the prior mass concentrates on functions matching the true smoothness; the data fits well; \(D_N^{(\beta)}\) is large, of order \(\exp(-c_\star N(\varepsilon_N^{\rm ad})^2)\).

• For \(\beta\gg \beta^\star\) (oversmoothed): the prior puts almost all mass on functions smoother than \(m^\star\); the truncation bias is huge and the squared-error is large; \(D_N^{(\beta)}\) decays exponentially faster than \(D_N^{(\beta^\star)}\).

• For \(\beta\ll \beta^\star\) (undersmoothed): the prior is too rough, the variance of the posterior mean is large, and the squared-error term again dominates; \(D_N^{(\beta)}\) also decays faster.

The transition between these regimes is sharp: a smoothness window of width \(O(1/\log N)\) around \(\beta^\star\) already gets within \(e^{O(1)}\) of the optimum. That window is what we call the near-oracle slab \(I_N\). Outside \(I_N\) the posterior weight on \(\beta\) is exponentially suppressed; inside, the conditional posterior \(\Pi(\cdot\mid\beta,\mathcal{D}_N)\) contracts at the oracle rate.

11.0.0.3 Strategy.

Given the goal of bounding \(\Pi(\|f-m^\star\|>M\varepsilon_N^{\rm ad}\mid\mathcal{D}_N)\):

1. Slab. Define \(I_N\subset [\beta_{\min},\beta_{\max}]\) of width \(1/\log N\) around \(\beta^\star\). By Lipschitzness of \(r(\beta)=\beta/(2\beta+d)\), every \(\beta\in I_N\) induces a contraction rate within \(e^{O(1)}\cdot \varepsilon_N^{\rm ad}\) of the oracle. In particular the prior small-ball at scale \(\varepsilon_N^{\rm ad}\) is uniform across \(I_N\).

2. Hierarchical denominator. Restricting the marginal likelihood integral to \(\beta\in I_N\) gives \(D_N\ge \Pi_\beta(I_N)\cdot e^{-CN(\varepsilon_N^{\rm ad})^2}\ge (\log N)^{-1}e^{-CN(\varepsilon_N^{\rm ad})^2}\). The \((\log N)^{-1}\) is what we pay for adaptation.

3. Hierarchical numerator. Use a single sieve covering the union of per-\(\beta\) sieves from Appendix 8.4. Its entropy is still \(O(N(\varepsilon_N^{\rm ad})^2)\) because the largest per-\(\beta\) effective dimension is at \(\beta_{\min}\). Tests + Bernstein-MDS as in Appendix 8.5 bound the numerator by \(e^{-cM^2 N(\varepsilon_N^{\rm ad})^2}\).

Combining (II) and (III) gives the contraction at rate \(\varepsilon_N^{\rm ad}\).

We extend the fixed-smoothness argument of Appendix 8 to the hierarchical-Bayes setting where the smoothness \(\beta\) is unknown and given a hyperprior \(\Pi_\beta\) on \([\beta_{\min},\beta_{\max}]\) with bounded density. The proof follows the standard “near-oracle smoothness slab + denominator + tests” template, with care for the predictable filtration and the sub-exponential quasi-likelihood used by the Bayesian teacher.

11.1 Setup and adaptive target rate↩︎

Recall the hierarchical posterior \(d\Pi_t(f,\beta)\propto e^{\ell_N(f)}\,d\Pi^{(\beta)}_0(f)\,d\Pi_\beta(\beta),\) with \(d\Pi^{(\beta)}_0(f)\) the conditional Gaussian-series prior at smoothness \(\beta\). As before, set \(N=N_{t,w}\).

Define the adaptive target rate \[\label{eq:target-rate-ad} \varepsilon_N^{\rm ad} := N^{-\beta^\star/(2\beta^\star+d)}(\log N)^{A}, \qquad J_N^\star := \lceil(N/\log N)^{d/(2\beta^\star+d)}\rceil,\tag{25}\] where \(\beta^\star\in[\beta_{\min},\beta_{\max}]\) is the true smoothness of \(m^\star\), and \(A>0\) is a structural constant chosen large enough.

11.2 Step 1: near-oracle slab↩︎

Proof. Direct from \(r'(\beta)=d/(2\beta+d)^2\). \(\square\)

Define the near-oracle slab \[\label{eq:slab} I_N := \begin{cases} [\beta^\star-\Delta_N,\beta^\star] & \text{if } \beta^\star-\Delta_N>\beta_{\min},\\ [\beta_{\min},\beta_{\min}+\Delta_N] & \text{if } \beta^\star\le \beta_{\min}+\Delta_N, \end{cases} \qquad \Delta_N=\frac{c_*}{\log N},\tag{26}\] for a small constant \(c_*\) chosen below. By Lemma 16 and \(\Delta_N\log N=c_*=O(1)\), every \(\beta\in I_N\) satisfies \(N^{r(\beta)}\asymp N^{r(\beta^\star)}\), i.e., the rate is preserved up to constants. Since \(\Pi_\beta\) has density bounded below by \(c_\beta>0\), \[\label{eq:slab-mass} \Pi_\beta(I_N)\ge c_\beta\Delta_N\asymp 1/\log N.\tag{27}\]

11.3 Step 2: uniform prior small-ball over \(I_N\)↩︎

Proof. Re-run Step 2 of Appendix 8.3 with \(\beta\in I_N\). The bias bound \(\sum_{j>J}(\theta_j^\star)^2\lesssim J^{-2\beta^\star/d}\lesssim (\varepsilon_N^{\rm ad})^2\) uses \(\beta^\star\), not \(\beta\), and so is unchanged.

The low-frequency block requires \(\sum_{j\le J}(\theta_j^\star)^2/\rho_j(\beta)\lesssim N(\varepsilon_N^{\rm ad})^2.\) Using \(\rho_j(\beta)^{-1}\asymp j^{1+2\beta/d}=j\cdot j^{2\beta^\star/d}\cdot j^{-2(\beta^\star-\beta)/d}\) and \(j\le J\le n\), so \(\log j\le \log n\): \[j^{-2(\beta^\star-\beta)/d} \le e^{2|\beta^\star-\beta|\log n/d} \le e^{2c_*\log n/(d\log N)} = O(1)\] for \(c_*\) small. Hence \(\rho_j(\beta)^{-1}\lesssim J j^{2\beta^\star/d}\) uniformly in \(\beta\in I_N\) and \(\sum_{j\le J}(\theta_j^\star)^2/\rho_j(\beta)\lesssim J\sum j^{2\beta^\star/d}(\theta_j^\star)^2\lesssim JR^2.\) The high-frequency tail \(\sum_{j>J}\rho_j(\beta)\lesssim J^{-2\beta/d}\) also matches \(J^{-2\beta^\star/d}\lesssim (\varepsilon_N^{\rm ad})^2\) uniformly in \(\beta\in I_N\) by the same argument applied with \(\beta^\star\to\beta\). The rest of the small-ball calculation goes through unchanged. \(\square\)

11.4 Step 3: hierarchical denominator↩︎

Proof. By restriction to the slab \(I_N\), \[D_N\ge \int_{I_N}\Pi^{(\beta)}_0\bigl(\|f-m^\star\|\le C\varepsilon_N^{\rm ad}\bigr) \cdot e^{-CN(\varepsilon_N^{\rm ad})^2} \,d\Pi_\beta(\beta),\] where the inner factor is the uniform small-ball lower bound on the log-likelihood within the small ball, established as in Step 5 of Appendix 8.6, and which is in turn \(\ge \exp(-CN(\varepsilon_N^{\rm ad})^2)\) uniformly in \(\beta\in I_N\) by Lemma 17. Combining with 27 , \(D_N\ge \frac{c_\beta}{\log N}\exp(-(C+C)N(\varepsilon_N^{\rm ad})^2).\) The extra \(\log\log N\) from \(\Pi_\beta(I_N)\) is absorbed into the \(\widetilde{O}\)-rate. \(\square\)

11.5 Step 4: hierarchical numerator↩︎

Define the joint sieve \[\mathcal{F}_n^{\rm hier} := \bigcup_{\beta\in[\beta_{\min},\beta_{\max}]}\mathcal{F}_n^{(\beta)},\] where \(\mathcal{F}_n^{(\beta)}\) is the per-\(\beta\) sieve from Appendix 8.4 with target rate \(\varepsilon_N^{\rm ad}\). Since the per-\(\beta\) effective dimension is at most \(J_n \asymp n^{d/(2\beta_{\min}+d)},\) which depends only logarithmically on \(\beta\), the entropy of \(\mathcal{F}_n^{\rm hier}\) at scale \(\rho\) satisfies \(\log N(\rho,\mathcal{F}_n^{\rm hier},L_2(P_X)) \lesssim J_n\log(C/\rho) \lesssim N(\varepsilon_N^{\rm ad})^2.\) The tail outside the sieve is also exponentially small, summed over a fine \(\beta\)-grid of cardinality \(|\beta_{\max}-\beta_{\min}|\cdot\log N\le C\log N\).

The same Le Cam–Birgé tests as in Step 4 of Appendix 8.5 apply to alternatives in \(\mathcal{F}_n^{\rm hier}\) separated by \(M\varepsilon_N^{\rm ad}\). Bernstein for sub-exponential MDS (Lemma 1) and matrix Freedman Gram concentration (Lemma 10) give the same exponential errors as in the fixed-smoothness case, with \(\rho^2\) replaced by \((\varepsilon_N^{\rm ad})^2\).

11.6 Step 5: hierarchical contraction↩︎

Combining Lemma 18 with the hierarchical numerator bound, on the intersection of the Gram event and the denominator event, \[\Pi(\|f-m^\star\|_{L_2(P_X)}>M\varepsilon_N^{\rm ad}\mid \mathcal{D}_N) \le \frac{e^{-cM^2N(\varepsilon_N^{\rm ad})^2}}{\Pi_\beta(I_N) e^{-C_D N(\varepsilon_N^{\rm ad})^2}} \le (\log N)\,e^{-(cM^2-C_D)N(\varepsilon_N^{\rm ad})^2} \to 0,\] provided \(M\) is chosen so that \(cM^2-C_D-1\ge 1\). The factor of \(\log N\) contributes at most an additive \(O(\log\log N)\) to the rate exponent and is absorbed into \(\widetilde{O}\). This proves Theorem 4 for the generic regression target.

11.7 Step 6: adaptive contraction of the smoothness posterior↩︎

The above also implies a contraction statement for the smoothness posterior: the marginal \(\Pi(\beta\mid\mathcal{D}_N)\) is asymptotically supported on smoothness values \(\beta\) with rate \(\beta/(2\beta+d)\ge \beta^\star/(2\beta^\star+d)-c/\log N\). Indeed, every \(\beta\) violating this gives a denominator decay strictly faster than the rate of \(f\in I_N\), while the slab \(I_N\) supplies the denominator. Equivalently, the posterior over \(\beta\) concentrates on smoothness levels whose induced contraction rate is within logarithmic factors of the oracle rate.

11.8 Step 7: Pseudo-Bayes generality↩︎

The argument above does not require the noise to be Gaussian. The quasi-likelihood-ratio \(e^{\ell_N(f)-\ell_N(m^\star)}\) is bounded below the exact-likelihood ratio for sub-exponential noise, with exponential correction \(\exp(O(N(\varepsilon_N^{\rm ad})^2))\) from the Bernstein-MDS bounds. This correction is absorbed into the constant \(C_D\) in Lemma 18, so the same conclusion holds.

11.9 Step 8: Specialization to four targets↩︎

Apply Steps 1–7 to the four cases as in Appendix 8.9. The resulting contraction rate is \(\varepsilon^{\rm ad}_{w,h,t} = N_{t,w}^{-\beta_{w,h}^\star/(2\beta_{w,h}^\star+d)}(\log N_{t,w})^A\) in \(L_2(P_X)\) for each \((w,h)\in\{0,1\}\times\{\mu,q\}\).\(\square\)

Smoothness-adaptive design consistency↩︎

Combining Theorem 4 with the proof of Proposition 2 verbatim (substituting \(\varepsilon^{\rm ad}_{w,h,t}\) for \(\varepsilon_{w,h,t}\) in Appendix 9) yields \(\|e_t^{\rm HB}-e^\star\|_{L_2(P_X)}\xrightarrow{P}0,\) where \(e_t^{\rm HB}\) is the posterior Neyman propensity formed under the hierarchical smoothness posterior. Theorem 3 continues to hold under the hierarchical design with the rate condition replaced by the adaptive analogue \(\beta^\star_{w,h}/(2\beta^\star_{w,h}+d)\).

12 Transformer construction and proof of Theorem 5↩︎

12.0.0.1 Goal.

Show that a ReLU-attention transformer of width \(\widetilde{O}(J_n)\) and depth \(O(\log n)\) contains a parameter setting whose output approximates the smoothness-adaptive Bayesian moment estimator at the oracle rate \(\widetilde{O}(N^{-\beta^\star/(2\beta^\star+d)})\) for every arm and every moment target. This is what populates the trainable hypothesis class of Appendix 13 with a low-risk comparator.

12.0.0.2 Strategy: split into computation + statistics.

The proof has two logically independent parts:

1. Computational realization (Sections 12.1–12.6). For each smoothness expert \(k\), the transformer exactly executes finite-rank masked ridge regression. We map each piece of the Bayesian update to a transformer primitive:

   • Sample averages (\(c_N=N^{-1}\sum_i \phi_iZ_i\), \(G_Na=N^{-1}\sum_i\phi_i(\phi_i^\top a)\), \(z_N^{(2)}=N^{-1}\sum_i Z_i^2\), dot products) \(\leftrightarrow\) normalized linear attention with coordinate-selector \(Q,K,V\) matrices. Attention is the natural “compute a per-history average” operation.

   • Coordinate masking and dynamic active dimension \(\leftrightarrow\) ReLU FFN. The indicator \(\mathbf{1}\{N\ge T_{j,k}\}\) is realized exactly by \(\sigma(N-T+1)-\sigma(N-T)\) on integer \(N\), and the masked product \(p\cdot a\) is realized exactly on a bounded domain (29 ).

   • Diagonal prior shrinkage \(\leftrightarrow\) tokenwise affine FFN.

   • Projected gradient descent on the masked ridge objective \(\leftrightarrow\) chain of \(L=O(\log n)\) attention/FFN blocks. Each iterate computes the gradient by attention, takes a step, and re-projects via the mask; geometric convergence follows from a \(O(1)\) condition number on the active subspace (Appendix 7).

   • Penalized-evidence MoE gate \(\leftrightarrow\) ReLU softmax with score \(S_k=\mathrm{RSS}_k+\mathrm{Prior}_k+A\,d_k\log n/N\).

   The total error is the sum of finite-depth GD error (\(n^{-A}\)), embedding error if features are computed from raw covariates (controllable by encoder size), and zero score/readout error.

2. Statistical (penalized-MoE) adaptation (Section 12.7). Even though the gate uses a computable penalized-likelihood approximation rather than the exact log marginal likelihood, the resulting weights still concentrate on the near-oracle expert. Two pieces:

   • Bad-expert lower bound. Any expert with risk \(R_k+\mathrm{pen}_k\gg r_N^2\) has score \(S_k\ge S_{k^\star}+\Omega(N r_N^2)\).

   • Near-oracle upper bound. The expert closest to \(\beta^\star\) on the grid has score \(S_{k^\star}\le \widetilde{O}(r_N^2)\).

   The exponential weighting \(\omega_k\propto \pi_k\exp(-\eta_g N S_k)\) then suppresses bad experts at rate \(e^{-\Omega(Nr_N^2)}\), and convexity of squared norm bounds the mixture risk by the weighted sum of individual risks.

12.0.0.3 Why the penalty \(A\,d_k\log n/N\) is the right complexity term.

The exact log marginal likelihood for ridge contains a log-determinant of the posterior covariance, which on the active subspace is approximately \(d_k\log N\) (one \(\log N\) for each active coordinate’s posterior precision, which scales linearly in \(N\)). So \(\mathrm{Prior}_k+A\,d_k\log n/N\) is the computable approximation to the exact \(-\frac{N}{2}\mathrm{RSS}_k+\frac{1}{2}\log\det\) score, up to constants. This is why Lemma 23 below recovers the true risk plus complexity penalty \(R_k+\mathrm{pen}_k\).

We work with a single generic regression target \(Z=m^\star(X)+\xi\), \(m^\star\in\mathcal{H}^{\beta^\star}(R)\). The specialization to \((w,h)\in\{0,1\}\times\{\mu,q\}\) uses the same arm-specific sample \(\mathcal{D}_N\) and the same predictable filtration as in Appendices 8–11.

12.1 Common basis, finite truncation, and active dimensions↩︎

Set \(J_n=\lceil n^{d/(2\beta_{\min}+d)}\rceil\) and \(\phi_n(x)=(\psi_1(x),\ldots,\psi_{J_n}(x))^\top\). Each smoothness expert \(k\in\{1,\ldots,K_n\}\) corresponds to a smoothness value \(\beta_k\in[\beta_{\min},\beta_{\max}]\); the grid is chosen so that mesh \(\le c/\log n\), hence \(K_n=O(\log n)\). Expert \(k\) uses the diagonal prior precision \(\Lambda_k^{-1}=\mathrm{diag}\{\rho_1(\beta_k)^{-1},\ldots,\rho_{J_n}(\beta_k)^{-1}\}\).

The dynamic active dimension for expert \(k\) at sample size \(N\) is \(d_{N,k}\le J_n\), defined as the largest \(J\le J_n\) such that \(N\ge C_1J\log J, \qquad \rho_J(\beta_k)^{-1}\le N.\) The mask is \(P_{N,k}=\mathrm{diag}\{p_{j,k}(N)\}\), \(p_{j,k}(N)=\mathbf{1}\{j\le d_{N,k}\}\), or equivalently \(\mathbf{1}\{N\ge T_{j,k}\}\) for precomputed thresholds.

12.1.0.1 Truncation bias.

As in Appendix 8.2, \(\|m^\star-m^\star_{J_n}\|_{L_2(P_X)}^2\lesssim J_n^{-2\beta^\star/d}.\) Since \(J_n\asymp n^{d/(2\beta_{\min}+d)}\) and \(\beta^\star\ge\beta_{\min}\), this is no worse than the roughest statistical rate and is absorbed.

12.2 Token structure↩︎

For an arm-filtered history \(\mathcal{D}_N=\{(X_i,Z_i)\}_{i=1}^N\): \[\begin{align} H_i &= [\phi_n(X_i),\,Z_i,\,Z_i^2,\,i/N,\,N/n,\,1/N,\,\log n/N,\,\mathrm{history}]\quad &\text{(history token)}\\ Q &= [\phi_n(x),\,N/n,\,1/N,\,\mathrm{query}]\quad &\text{(query token)}\\ E_k^{(\ell)} &= [\beta_k,\,1/N,\,\phi_n(x),\,a_k^{(\ell)},\,p_k(N),\,c_N,\,z_N^{(2)},\,\mathrm{expert}]\quad &\text{(expert register)}. \end{align}\] The deterministic prefix-level features \(1/N\), \(\log n/N\), \(i/N\), \(N/n\) remove the need to approximate reciprocal maps in attention and avoid all per-step division operations.

12.3 Statistic-attention computes the sufficient statistics↩︎

Proof. For (i) take \(Q=\mathbf{1}\) (selecting the constant coordinate), \(K\) selecting \(Z_i\), \(V\) selecting \(\phi_i\). Then \(N^{-1}\sum_i (Qh_i)^\top(Kh_j) Vh_j=N^{-1}\sum_i Z_i\phi_i\). For (ii) take \(K=Z_i,V=Z_i\). For (iii) take \(Q\) selecting \(a_k^{(\ell)}\), \(K\) selecting \(\phi_i\), \(V\) selecting \(\phi_i\). The dot products in (iv) are analogous. All selectors are coordinate projections of operator norm one. \(\square\)

12.3.0.1 Embedding error.

If the input contains exact features \(\phi_n(X)\), \(\delta_{\rm emb}=0\). If raw covariates are used, a pointwise ReLU encoder \(E_\theta:\mathbb{R}^d\to\mathbb{R}^{J_n}\) achieves \(\sup_x\|E_\theta(x)-\phi_n(x)\|_2\le \epsilon_{\rm emb}\) at parameter cost \(\widetilde{O}(J_n^{2+d/(2s)}\epsilon_{\rm emb}^{-d/s})\) for \(C^s\) basis functions [20]. By the same algebra as in [TCM §3.3], the propagation of embedding error through the ridge update is controlled by \(\sqrt{J_n}\epsilon_{\rm emb}=o(\varepsilon_n^{\rm ad}),\) which is the only constraint on \(\epsilon_{\rm emb}\).

12.4 ReLU FFN realization of the dynamic mask↩︎

The active-coordinate indicator \(\mathbf{1}\{N\ge T_{j,k}\}\) for integer \(N\) is exact: \[\label{eq:relu-indicator} p_{j,k}(N) = \sigma(N-T_{j,k}+1)-\sigma(N-T_{j,k}).\tag{28}\] The coordinate projection \(a_j\mapsto p_{j,k}\,a_j\) is exact on a bounded domain \(|a_j|\le B_a\): \[\label{eq:relu-mask-mult} p\,a = \sigma\{a-B_a(1-p)\}-\sigma\{-a-B_a(1-p)\},\tag{29}\] which equals \(a\) when \(p=1\) and \(0\) when \(p=0\). Hence \(\delta_{\rm mask}=0\).

12.5 Projected GD: one block, geometric convergence↩︎

For expert \(k\) at sample size \(N\), the masked ridge objective is \[Q_k(a) = \frac{1}{2N}\sum_{i=1}^N(Z_i-\phi_i^\top a)^2 +\frac{\bar\sigma^2}{2N}a^\top\Lambda_k^{-1}a, \quad a=P_{N,k}a.\] Its gradient is \(\nabla Q_k(a)=G_Na+(\bar\sigma^2/N)\Lambda_k^{-1}a-c_N\). One block executes \[\label{eq:gd-block} a^{(\ell+1)}=P_{N,k}\bigl[a^{(\ell)}-\eta(G_Na^{(\ell)}+(\bar\sigma^2/N)\Lambda_k^{-1}a^{(\ell)}-c_N)\bigr].\tag{30}\] Each piece is computed by Lemma 19 (cross-token via attention) and the ReLU FFN (within-token diagonal map and projection, 29 ). One attention-FFN block implements one projected GD step exactly.

Proof. The Hessian condition is from Lemma 10. Projected gradient descent on a strongly convex objective with \(\eta\in(0,2/M)\) contracts in the \(H_{N,k}\) norm at rate \(q\) [30]. \(\square\)

12.6 Penalized-evidence MoE gate↩︎

The implementable MoE gate uses the score \[\label{eq:score} S_k = \mathrm{RSS}_k+\mathrm{Prior}_k+A\frac{d_k\log n}{N},\tag{31}\] with \(\mathrm{RSS}_k=N^{-1}\sum_i(Z_i-\phi_i^\top a_k)^2\), \(\mathrm{Prior}_k=(\bar\sigma^2/N)a_k^\top\Lambda_k^{-1}a_k\), \(d_k=d_{N,k}\), and \(A>0\) a constant chosen below. The MoE weight is \[\omega_k = \frac{\pi_k\exp(-\eta_g N S_k)}{\sum_r\pi_r\exp(-\eta_g N S_r)},\] with \(\pi_k\asymp 1/K_n\) and \(\eta_g\) a fixed positive constant. The output is \(\widehat m_{\rm mix}(x)=\sum_k\omega_k\widehat m_k(x)\) where \(\widehat m_k(x)=\phi_x^\top a_k^{(L)}\).

12.6.0.1 Computability.

Each piece of \(S_k\) is exact under exact features:

• \(\mathrm{RSS}_k=z_N^{(2)}-2a_k^\top c_N+a_k^\top G_Na_k\) is a linear combination of attention-computable quantities;

• \(\mathrm{Prior}_k=(\bar\sigma^2/N)a_k^\top\Lambda_k^{-1}a_k\) uses the diagonal prior FFN and a dot-product attention head with selector \(1/N\);

• the active dimension \(d_k=\sum_j p_{j,k}(N)\) is a fixed linear sum of mask coordinates, and \(A\,d_k\log n/N\) uses the prefix-level scalar \(\log n/N\).

The exponential weights are realized by a piecewise-linear ReLU softmax approximation to error \(\varepsilon_{\rm sm}=n^{-A}\), with parameter cost \(P_{\rm sm}=n^{O(1)}\) (see [GPE §3.7]).

12.7 Penalized-MoE oracle inequality↩︎

We prove that the implementable gate gives an oracle-rate mixture risk.

12.7.1 Smoothness grid and near-oracle expert↩︎

Proof. Direct from the smoothness grid construction and Lemma 16. \(\square\)

12.7.2 Uniform concentration event \(\mathcal{E}_N\)↩︎

We establish the key uniform concentration event for the ridge spaces.

Proof. Cover \(\mathcal{F}_k\) by an \(L_2(P_X)\)-net at scale \(\rho>0\): \(\log N(\rho,\mathcal{F}_k,L_2(P_X))\lesssim d_k\log(C/\rho)\).

Empirical-population norm gap. For each cover element \(f_0\), \(\|f_0-m^\star\|_N^2-\|f_0-m^\star\|_{L_2(P_X)}^2\) is an iid average over \(X_i\) of a bounded random variable (bounded by \(\sup_x|f_0-m^\star|^2\le B_n^2\)). Bernstein for iid sums (or Lemma 1) gives \(|\|f_0-m^\star\|_N^2-\|f_0-m^\star\|_{P_X}^2|\lesssim B_n\rho/\sqrt N\) with probability \(1-2\exp(-cN\rho^2/B_n^2)\).

Peeling. Take a geometric peeling with \(r_j=2^j\rho_0\), \(\rho_0=N^{-1/2}\sqrt{d_k\log n}\), and union bound over the per-shell covers. The displayed inequality holds at each shell with \(C_*\) proportional to the union-bound constant; the additive \(d_k\log n/N\) term comes from the smallest shell \(r_0\) and the slack \(\frac{1}{8}\rho^2\) comes from interpolation between shells.

Noise inner product. Apply Lemma 1 to \(D_i=\xi_i(f_0-m^\star)(X_i)\) — an MDS w.r.t. \(\mathcal{F}_i^X\) with predictable variance \(\le \tau^2\|f_0-m^\star\|_N^2\) and envelope \(\tau B_n\) — combined with the same peeling. The result is ?? .

Union over experts. Union bound over \(K_n=O(\log n)\) experts adds at most a \(\log\log n\) factor. The total deviation is \(\le n^{-A}\) for \(A\) large. \(\square\)

12.7.3 Lower bound on \(S_k\) for “bad” experts↩︎

Proof. Expand \(\mathrm{RSS}_k=z_N^{(2)}-2\widehat a_k^\top c_N+\widehat a_k^\top G_N\widehat a_k\) and use the residual-bias identity for \(f=\widehat f_k\): \[\mathrm{RSS}_k-\bar\xi_N^2 = \|\widehat f_k-m^\star\|_N^2-\frac{2}{N}\sum\xi_i(\widehat f_k-m^\star)(X_i).\] Apply Lemma 22: on \(\mathcal{E}_N\), \[\|\widehat f_k-m^\star\|_N^2\ge \tfrac78 R_k-C_*\mathrm{pen}_k, \quad -\frac{2}{N}\sum\xi_i(\widehat f_k-m^\star)(X_i)\ge -\tfrac18 R_k-C_*\mathrm{pen}_k.\] Hence \(\mathrm{RSS}_k-\bar\xi_N^2\ge \tfrac34 R_k-2C_*\mathrm{pen}_k\). The prior energy is nonnegative, and adding \(A\,\mathrm{pen}_k\) gives \(S_k-\bar\xi_N^2\ge \tfrac34 R_k+(A-2C_*)\mathrm{pen}_k\ge \tfrac14(R_k+\mathrm{pen}_k)\) when \(A\ge 8C_*+1\). \(\square\)

12.7.4 Upper bound on \(S_{k^\star}\)↩︎

Proof. Let \(f_{k^\star}^\circ=\sum_{j\le d_{k^\star}}\theta_j^\star\psi_j\) be the projection of \(m^\star\) onto the active space of \(k^\star\). Since \(\widehat f_{k^\star}\) minimizes \(\mathrm{RSS}+\mathrm{Prior}\) over \(\mathcal{F}_{k^\star}\), \(\mathrm{RSS}_{k^\star}+\mathrm{Prior}_{k^\star} \le \mathrm{RSS}(f_{k^\star}^\circ)+\mathrm{Prior}(f_{k^\star}^\circ).\)

RSS bound for \(f_{k^\star}^\circ\). By the residual-bias identity and Lemma 22, \(\mathrm{RSS}(f_{k^\star}^\circ)-\bar\xi_N^2 \le \tfrac98\|f_{k^\star}^\circ-m^\star\|_{L_2(P_X)}^2+C_*\mathrm{pen}_{k^\star} \le C d_{k^\star}^{-2\beta^\star/d}+C_*\mathrm{pen}_{k^\star},\) using the truncation bias bound from Appendix 12.1.

Prior energy bound. \(\mathrm{Prior}(f_{k^\star}^\circ) = (\bar\sigma^2/N)\sum_{j\le d_{k^\star}}\rho_j(\beta_{k^\star})^{-1}(\theta_j^\star)^2.\) Using \(\rho_j(\beta_{k^\star})^{-1}\asymp j^{1+2\beta_{k^\star}/d}\le d_{k^\star}j^{2\beta^\star/d}\) (since \(\beta_{k^\star}\le \beta^\star\) up to \(1/\log n\)), \(\mathrm{Prior}(f_{k^\star}^\circ) \lesssim (d_{k^\star}/N)\sum j^{2\beta^\star/d}(\theta_j^\star)^2 \lesssim d_{k^\star}/N \le \mathrm{pen}_{k^\star}.\)

Combine. \(S_{k^\star}-\bar\xi_N^2 \le C d_{k^\star}^{-2\beta^\star/d}+(A+C_*+1)\mathrm{pen}_{k^\star}.\) With \(d_{k^\star}\asymp N^{d/(2\beta^\star+d)}/\log n\), both terms are \(\widetilde{O}(N^{-2\beta^\star/(2\beta^\star+d)})\). \(\square\)

12.7.5 Bad-expert weight decay↩︎

Let \(r_N^2=\widetilde{O}(N^{-2\beta^\star/(2\beta^\star+d)})\) be the oracle squared rate. Define \(\mathcal{B}_M=\{k:R_k+\mathrm{pen}_k>Mr_N^2\}.\) For \(k\in\mathcal{B}_M\), Lemma 23 gives \(S_k-\bar\xi_N^2\ge c_0Mr_N^2\), while \(S_{k^\star}-\bar\xi_N^2\le C_0r_N^2\) (Lemma 24). Hence the score gap is \(S_k-S_{k^\star}\ge (c_0M-C_0)r_N^2\ge c_1Mr_N^2\) for \(M\) large. The weight ratio \(\omega_k/\omega_{k^\star} = (\pi_k/\pi_{k^\star})\exp(-\eta_gN(S_k-S_{k^\star})) \le C\exp(-\eta_gc_1MNr_N^2).\) Summing over the at most \(K_n=O(\log n)\) bad experts and using \(Nr_N^2=\widetilde{O}(N^{d/(2\beta^\star+d)})\to\infty\), \[\label{eq:bad-weight} \sum_{k\in\mathcal{B}_M}\omega_k\le K_n\exp(-\eta_gc_1MNr_N^2)\to 0\tag{32}\] exponentially fast.

12.7.6 Mixture risk bound↩︎

Proof. Convexity of squared norm gives the first inequality. Decompose \(\sum_k\omega_kR_k=\sum_{k\in\mathcal{G}_M}\omega_kR_k+\sum_{k\in\mathcal{B}_M}\omega_kR_k\). For \(k\in\mathcal{G}_M\), \(R_k\le Mr_N^2\) by definition. On a high-probability event, \(R_k\) is uniformly bounded by a constant \(C_R\) (by the boundedness of \(\widehat f_k\) on the sieve). Hence \(\sum_{\mathcal{B}_M}\omega_kR_k\le C_R\sum_{\mathcal{B}_M}\omega_k=o(r_N^2)\) by 32 . \(\square\)

12.8 Combining computational and statistical errors↩︎

Let \(m_{\rm TF}\) denote the actual transformer output and \(\widehat f_{\rm mix}\) the ideal MoE estimator. The error decomposition is \[\|m_{\rm TF}-m^\star\|_{L_2(P_X)} \le \delta_{\rm emb}+\delta_{\rm GD}+\delta_{\rm score}+\delta_{\rm sm}+\|\widehat f_{\rm mix}-m^\star\|_{L_2(P_X)}.\] Under the construction:

• \(\delta_{\rm emb}=0\) for exact features; or \(\delta_{\rm emb}=o(\varepsilon_n^{\rm ad})\) for ReLU encoder with \(\sqrt{J_n}\epsilon_{\rm emb}=o(\varepsilon_n^{\rm ad})\);

• \(\delta_{\rm GD}=O(n^{-A})\) by Lemma 20;

• \(\delta_{\rm score}=0\) by Lemma 19 and exact mask realization 29 ;

• \(\delta_{\rm sm}=B_m\varepsilon_{\rm sm}=o(\varepsilon_n^{\rm ad})\) by ReLU softmax approximation;

• \(\|\widehat f_{\rm mix}-m^\star\|_{L_2(P_X)}=\widetilde{O}_p(N^{-\beta^\star/(2\beta^\star+d)})\) by Theorem 10.

Hence \(\|m_{\rm TF}-m^\star\|_{L_2(P_X)}=\widetilde{O}_p(N^{-\beta^\star/(2\beta^\star+d)}).\)

12.9 Specialization to four targets↩︎

Apply the result to each \((w,h)\in\{0,1\}\times\{\mu,q\}\) with arm-specific sample \(N=N_{t,w}\). The conditional sub-exponential noise condition (Assumption 2) is identical to the one used in Lemma 22, so the four rate statements \(\|\widehat\mu_{w,t}-\mu_w^\star\|_{L_2(P_X)}=\widetilde{O}_p(N_{t,w}^{-\beta^\star_{w,\mu}/(2\beta^\star_{w,\mu}+d)}),\) \(\|\widehat q_{w,t}-q_w^\star\|_{L_2(P_X)}=\widetilde{O}_p(N_{t,w}^{-\beta^\star_{w,q}/(2\beta^\star_{w,q}+d)}),\) all follow.

12.10 Neyman head↩︎

Composing \((\widehat\mu_0,\widehat\mu_1,\widehat q_0,\widehat q_1)\mapsto e^{\rm Ney}\) in Lemma 12 requires only Lipschitz operations on a bounded domain: square, clip, square root, ratio, clip. A ReLU FFN piecewise-linearly approximates each to accuracy \(\varepsilon_{\rm Ney}=n^{-A}\) with parameter cost \(P_{\rm Ney}=n^{O(1)}\) (see [GPE §6.1]). The propagated \(L_2\) error is \(\|\widehat e_t-e_t^{\rm B}\|_{L_2(P_X)}\le L_{\rm Ney}\cdot O(\varepsilon^{\rm ad})+\varepsilon_{\rm Ney}=o(\varepsilon^{\rm ad})\). This completes the construction underlying Theorem 5.\(\square\)

13 ERM oracle inequality for the pretrained experimenter↩︎

13.0.0.1 Goal.

Show that the parameter \(\widehat\theta\) minimizing the empirical pretraining risk over \(N_{\rm pre}\) independent trajectories satisfies the high-probability bound \[\label{eq:erm-target} R_{\rm est}(\widehat\theta) \le \inf_{\theta\in\mathcal{T}_n}R_{\rm est}(\theta) + C\sqrt{\frac{\widetilde{O}(P_n)+\log(1/\delta)}{N_{\rm pre}}}.\tag{33}\] This is the bound informally stated in Section 3.2. We do not compose with any decision-risk transfer; the appendix stops at this oracle inequality.

13.0.0.2 Strategy: textbook covering + Lipschitz net.

The proof is the standard learning-theory recipe:

1. Pointwise concentration. For any fixed \(\theta\), the empirical risk is an iid average over \(N_{\rm pre}\) trajectories of a bounded loss; Hoeffding gives sub-Gaussian deviations.

2. Cover the parameter space. The norm-bounded ball of transformer parameters has an \(\varepsilon\)-net of size \((p_n B_n/\varepsilon)^{p_n}\). Union bound across the net gives uniform concentration on the net.

3. Lipschitz extension. Push concentration from the net to the entire parameter ball using the parameter Lipschitz constant \(L_{{\rm net},n}\) of the loss. Choose \(\varepsilon\) to balance the two sources of error.

4. Comparator. The constructive transformer of Appendix 12 lies inside the trainable class, so the in-class minimum risk is bounded by its approximation error \(\varepsilon_{\rm app,n}^2=\widetilde{O}(n^{-2\beta^\star/(2\beta^\star+d)})\).

13.0.0.3 Two subtle points the proof emphasizes.

• Trajectory- vs.token-level independence. Tokens within a single trajectory are dependent (the design is adaptive: \(W_t\) uses \(\mathcal{F}_t\)). The trajectory-level loss \(\frac{1}{n}\sum_{t=1}^n[\cdots]^2\) averages over tokens within a trajectory, then we average across the \(N_{\rm pre}\) independent trajectories. Hoeffding’s iid concentration applies at the trajectory level, so the rate is \(1/\sqrt{N_{\rm pre}}\), not \(1/\sqrt{nN_{\rm pre}}\). Treating tokens as iid would be wrong by a factor of \(\sqrt n\).

• Polynomial Lipschitz constant. The entries of attention and FFN scale with the norm envelope \(B_n\) to high powers; without careful book-keeping the Lipschitz constant could blow up super-polynomially in \(n\). Section 13.3 verifies it is \(\log L_{{\rm net},n}=\widetilde{O}(1)\), which is what makes the final \(\widetilde{O}(\cdot)\) inside the square root tame.

This appendix proves the empirical-risk-minimization concentration bound quoted in Section 3: with high probability the pretrained transformer attains risk within \(\widetilde{O}(\sqrt{P_n/N_{\rm pre}})\) of the in-class minimum. The argument is a covering-number Hoeffding bound, with the two crucial points emphasized above.

13.1 Theoretical class↩︎

13.1.0.1 Architecture.

The theoretical class \(\mathcal{T}_n^{\rm est}(B_n,R_n)\) consists of encoder-only residual transformers with:

• Token width \(D_n\), FFN hidden width \(D'_n\), \(M_n\) heads per layer, \(L_n\) layers.

• Normalized ReLU attention \(A_i(H;Q,K,V)=S^{-1}\sum_j\sigma((Qh_i)^\top(Kh_j))Vh_j\), with signed linear attention realized as \(\sigma(z)-\sigma(-z)\) via two heads.

• ReLU FFN \(\mathrm{FFN}(h)=W_2\sigma(W_1h)\).

• Tokenwise Euclidean clipping to radius \(R_n\) after each sublayer (1-Lipschitz).

• Operator-norm constraints \(\|Q\|_{\rm op},\|K\|_{\rm op},\|V\|_{\rm op},\|W_1\|_{\rm op},\|W_2\|_{\rm op},\|W_{\rm out}\|_{\rm op}\le B_n\).

• \(2K_n\)-dimensional readout: \(K_n\) expert predictions \(\widehat m_{\theta,k}(x)\) and \(K_n\) evidence logits \(\widehat\ell_{\theta,k}\).

• Mixture weights \(\widetilde{\omega}=\widetilde{\mathrm{Softmax}}(\widehat\ell)\) via piecewise-linear ReLU softmax approximation with parameter count \(P_{\rm sm}\).

The design class \(\mathcal{T}_n^{\rm pol}(B_n,R_n)\) adds a ReLU FFN Neyman head with parameter count \(P_{\rm Ney}\).

13.1.0.2 Parameter dimension.

\[\label{eq:erm-pn} p_n^{\rm est} = P_{\rm enc} +O\{L_n(M_nD_n^2+D_nD'_n)\} +O(K_nD_n) +P_{\rm sm}.\tag{34}\] With \(D_n\asymp J_n\), \(D'_n=rD_n\), \(M_n=O(1)\), \(L_n=K_n=O(\log n)\), \(p_n^{\rm est}=P_{\rm enc}+\widetilde{O}(J_n^2)+P_{\rm sm}\).

13.2 Constructive comparator↩︎

Proof.verifies that each component (selector attention, mask FFN, diagonal prior FFN, GD FFN, evidence FFN, ReLU softmax, expert combination) has matrix and bias norm bounded by \(\mathrm{poly}(n,J_n,K_n,B_{Z,n})\), so \(\log B_n=\widetilde{O}(1)\). Hidden states are clipped at radius \(R_n=\mathrm{poly}(n,J_n,K_n,B_{Z,n})\), so \(\log R_n=\widetilde{O}(1)\). The risk bound is from Theorem 5 applied to the constructive parameter setting. \(\square\)

13.3 Parameter Lipschitz bound↩︎

Proof. \(\Delta V\) piece: \(|s_{ij}|=|\sigma((Qh_i)^\top(Kh_j))|\le B_n^2R_n^2\), so \(\|S^{-1}\sum s_{ij}\Delta Vh_j\|\le B_n^2R_n^2\cdot R_n\|\Delta V\|_{\rm op}\). \(\Delta Q\) piece: ReLU is 1-Lipschitz, \(|s_{ij}-s'_{ij}|\le B_nR_n^2\|\Delta Q\|_{\rm op}\), multiplied by \(\|Vh_j\|\le B_nR_n\) gives \(B_n^2R_n^3\|\Delta Q\|_{\rm op}\). \(\Delta K\) analogous. Summing the three pieces gives the displayed bound. \(\square\)

Proof. For attention, \(|s_{ij}-s'_{ij}|\le 2B_n^2R_n\Delta\), so the head output differs by at most \(CB_n^3R_n^2\Delta\). Sum over \(M_n\) heads, add identity shortcut and 1-Lipschitz clip: factor \(1+CM_nB_n^3R_n^2\). For FFN: residual plus \(\sigma\) 1-Lipschitz gives \(1+B_n^2\). Compose. \(\square\)

Proof. By induction on layers using the recurrence \(\Delta_\ell\le A_n\Delta_{\ell-1}+C_{\rm block,n}\|\theta_\ell-\theta'_\ell\|_2\), yielding \(\Delta_{L_n}\le A_n^{L_n}(C_{\rm enc,n}+\sqrt{L_n}C_{\rm block,n})\|\theta-\theta'\|_2\). Substituting \(L_n=O(\log n)\), \(\log A_n=\widetilde{O}(1)\), \(\log C_{\rm block,n}=\widetilde{O}(1)\) gives \(\log L_{{\rm net},n}=\widetilde{O}(1)\). The readout (linear map + softmax + expert combination) adds polynomial factors that are absorbed. \(\square\)

13.4 Trajectory-level independence↩︎

The pretraining data are \(N_{\rm pre}\) independent trajectories \(\{\mathcal{Z}_i\}_{i=1}^{N_{\rm pre}}\), each of length \(n\). Tokens within a trajectory are dependent (the design is adaptive). The trajectory-level loss \[\ell_{\rm est}(\theta;\mathcal{Z}) =\frac{1}{n}\sum_{t=1}^n\mathbb{E}_{x\sim P_X}[F_\theta(\mathcal{D}_t,x)-m^B_t(x)]^2\] is bounded by \(4B_y^2=:B_{\ell,{\rm est}}\). Define the population/empirical risks \(R_{\rm est}(\theta)=\mathbb{E}[\ell_{\rm est}(\theta;\mathcal{Z})],\quad \widehat R_{\rm est}(\theta)=N_{\rm pre}^{-1}\sum_i\ell_{\rm est}(\theta;\mathcal{Z}_i).\) The independent sample size for generalization is \(N_{\rm pre}\), not \(nN_{\rm pre}\).

13.5 Covering uniform deviation↩︎

Combining the two by union bound: \[\label{eq:net-uniform} \max_{\theta\in\mathcal{N}_\varepsilon}|\widehat R_{\rm est}(\theta)-R_{\rm est}(\theta)| \le CB_{\ell,{\rm est}}\sqrt{\frac{p_n^{\rm est}\log(CB_n\sqrt{p_n^{\rm est}}/\varepsilon)+\log(1/\delta)}{N_{\rm pre}}}\tag{35}\] with probability at least \(1-\delta\).

For an arbitrary \(\theta\in\Theta_n\) pick \(\theta^\sharp\in\mathcal{N}_\varepsilon\) with \(\|\theta-\theta^\sharp\|_2\le \varepsilon\). By Corollary 1, \(|R_{\rm est}(\theta)-R_{\rm est}(\theta^\sharp)|+|\widehat R_{\rm est}(\theta)-\widehat R_{\rm est}(\theta^\sharp)|\le 2L_{\ell,n}^{\rm est}\varepsilon.\) Choose \(\varepsilon=B_{\ell,{\rm est}}/(L_{\ell,n}^{\rm est}\sqrt{N_{\rm pre}})\) to balance the two error sources. Substituting \(\log B_n+\log L_{\ell,n}^{\rm est}=\widetilde{O}(1)\) yields \[\label{eq:erm-uniform} \sup_{\theta\in\Theta_n}|\widehat R_{\rm est}(\theta)-R_{\rm est}(\theta)| \le CB_{\ell,{\rm est}}\sqrt{\frac{\widetilde{O}(p_n^{\rm est})+\log(1/\delta)}{N_{\rm pre}}}.\tag{36}\]

13.6 Final ERM bound↩︎

Let \(\widehat\theta_{\rm est}\in\arg\min_{\theta\in\Theta_n}\widehat R_{\rm est}(\theta)\). Standard ERM: \(R_{\rm est}(\widehat\theta_{\rm est})\le \inf_{\theta\in\Theta_n}R_{\rm est}(\theta)+2\sup_\theta|\widehat R-R|.\) By Lemma 25, \(\inf_{\theta\in\Theta_n}R_{\rm est}(\theta)\le\varepsilon_{\rm app,n}^2\). Combining with 36 , \[\label{eq:erm-bound} R_{\rm est}(\widehat\theta_{\rm est}) \le \varepsilon_{\rm app,n}^2+CB_{\ell,{\rm est}}\sqrt{\frac{\widetilde{O}(p_n^{\rm est})+\log(1/\delta)}{N_{\rm pre}}}.\tag{37}\] Substituting \(p_n^{\rm est}=P_{\rm enc}+\widetilde{O}(J_n^2)+P_{\rm sm}\) gives the bound stated in §3.2.

13.7 Design ERM analogue↩︎

For the design transformer with BCE loss and clipped propensity in \([\eta,1-\eta]\), \(B_{\ell,{\rm pol}}=\log(1/\eta)\) and \(L_{\ell,n}^{\rm pol}\le \eta^{-1}L_{{\rm net},n}^{\rm pol}\), where the parameter dimension adds the Neyman head: \(p_n^{\rm pol} = p_n^{\rm est}+P_{\rm Ney}.\) The same covering argument gives \[\label{eq:erm-bound-pol} R_{\rm pol}(\widehat\theta_{\rm pol}) \le \inf_{\theta\in\mathcal{T}_n^{\rm pol}}R_{\rm pol}(\theta) +C\log(1/\eta)\sqrt{\frac{\widetilde{O}(p_n^{\rm pol})+\log(1/\delta)}{N_{\rm pre}}}.\tag{38}\]

13.8 Summary↩︎

The estimation ERM bound 37 simplifies, under the structural choices \(D_n\asymp J_n\), \(L_n=K_n=O(\log n)\), \(D'_n=rD_n\), \(M_n=O(1)\), to \[R_{\rm est}(\widehat\theta_{\rm est})\le \varepsilon_{\rm app,n}^2+CB_{\ell,{\rm est}}\sqrt{\frac{\widetilde{O}(P_{\rm enc}+J_n^2+P_{\rm sm})+\log(1/\delta)}{N_{\rm pre}}}.\] The constructive transformer of Appendix 12 lies in \(\Theta_n\) and approximates the Bayesian teacher with risk at most \(\varepsilon_{\rm app,n}^2=\widetilde{O}_p(n^{-2\beta^\star/(2\beta^\star+d)})\), so the ERM bound delivers an algorithm-imitation guarantee at the same rate up to the \(\widetilde{O}(\sqrt{P_n/N_{\rm pre}})\) statistical penalty.\(\square\)