Expected empirical training risk for spline series least squares

Write $\mathbf{X}=(X_1,\dots ,X_n)$ and ${ϵ}_i=Y_i-g_0(X_i)$. For fixed $\mathbf{x}$, set ${\kappa }_1=\kappa (x_1,\cdot )$ and, for $1\le m<n$, apply [F10] to ${\kappa }_m$ and $\kappa (x_{m+1},\cdot )$ to obtain ${\kappa }_{m+1}$; both factors are probability measures, so the rectangle formula gives total mass one at each stage. Induction gives the finite product probability measure ${\kappa }_n(\mathbf{x},\cdot )$ with rectangle values ${\kappa }_n(\mathbf{x},{\prod }_i{B}_i)={\prod }_i\kappa (x_i,B_i)$. The response rectangles form a pi-system because intersections of rectangles are rectangles, and [F5] says they generate the response product sigma-algebra. On response rectangles the evaluation is Borel in $\mathbf{x}$ by [F4] and [F10]. Because ${\kappa }_n(\mathbf{x},\cdot )$ is a probability measure, the class of sets with Borel evaluation contains the whole space, is closed under complements by subtraction from $1$, and is closed under disjoint countable unions by limits of partial sums; [F11] therefore gives measurability for every response Borel set. For rectangles $A={\prod }_i{A}_i$ and $B={\prod }_i{B}_i$, iid sampling gives $P(\mathbf{X}\in A,\mathbf{Y}\in B)={\prod }_i{\int }_{A_i}\kappa (x,B_i)P_X(dx)$, and repeated Tonelli [F13] gives ${\int }_A{\kappa }_n(\mathbf{x},B)P_X^{\otimes n}(d\mathbf{x})={\prod }_i{\int }_{A_i}\kappa (x,B_i)P_X(dx)\mathrm{.}$ For each fixed response rectangle $B$, the left side of the target identity is a finite measure in $A$; the right side is also a measure by [F12], applied to the nonnegative measurable function $\mathbf{x}\mapsto {\kappa }_n(\mathbf{x},B)$. Design rectangles form a pi-system because intersections are rectangles and generate the design product sigma-algebra by [F5], so [F11] extends the equality to every design Borel $A$. For each such $A$, both sides are finite measures in $B$: countable additivity on the right follows from countable additivity of ${\kappa }_n(\mathbf{x},\cdot )$ and monotone convergence [F14], and their common total mass is $P_X^{\otimes n}(A)$ because the joint design marginal is $P_X^{\otimes n}$ and ${\kappa }_n$ is a probability kernel. Thus the response sets $B$ for which the identity holds for every $A$ form a Dynkin system (complements use the common total mass); they contain the response rectangles, so [F11] gives equality for every response Borel set. Hence ${\kappa }_n$ is a conditional law of $\mathbf{Y}$ given $\mathbf{X}$. Under this product law the residuals are conditionally independent, have conditional means zero by [A2], and conditional second moments at most $\mathrm{\Delta }$. Hence $E[{ϵ}_i{ϵ}_j\mid \mathbf{X}]=0$ for $i\mathrm{\ne }j$ and $E[{ϵ}_i^2\mid \mathbf{X}]\le \mathrm{\Delta }$.

Let $Q={\mathrm{\Pi }}_{\mathrm{col}(D)}$. The matrix $Q$ is a Borel function of $D$: partition the finite-dimensional matrix space by rank and, within each positive-rank stratum, by the lexicographically first nonzero maximal minor; on each resulting Borel piece, the corresponding independent columns form a matrix $C$. The Gram matrix $C^{T}C$ is positive definite, and $C(C^{T}C{)}^{-1}{C}^T$ is symmetric, idempotent, and has image $\mathrm{col}(C)=\mathrm{col}(D)$, so it is the orthogonal projection; at rank zero put $Q=0$. These finitely many Borel formulas show that $Q$ is measurable with respect to $\mathbf{X}$. Its rank $r$ is at most $K$. Scanning the finitely many columns and retaining a column precisely when it is not in the span of those already retained gives a basis of $\mathrm{col}(D)$; applying Gram–Schmidt [F7] gives an $n\times r$ matrix $U$ with orthonormal columns spanning that subspace. For any $v$, $U{U}^{T}v$ belongs to $\mathrm{col}(D)$ and $U^T(v-U{U}^{T}v)=0$, so its residual is orthogonal to the columns of $U$ and hence to $\mathrm{col}(D)$. By the uniqueness in [F9], $Q=U{U}^T$; therefore $\mathrm{tr}(Q)=\mathrm{tr}(U^{T}U)=r\le K$. Since $Q_{ii}=\mathrm{\parallel }Q{e}_i{\mathrm{\parallel }}_2^2\ge 0$, step 1.1 gives $E[{ϵ}^{T}Qϵ\mid \mathbf{X}]={\sum }_i{Q}_{ii}E[{ϵ}_i^2\mid \mathbf{X}]\le \mathrm{\Delta }\mathrm{tr}(Q)\le \mathrm{\Delta }K\mathrm{.}$

Write $\mathbf{g}=(g_0(X_1),\dots ,g_0(X_n){)}^T$. From [F1] and [F8], ${\widehat{\mathbf{g}}}_K=Q\mathbf{Y}$, and $\mathbf{Y}=\mathbf{g}+ϵ$. In the orthogonal decomposition ${\mathbb{R}}^n=\mathrm{col}(D)\oplus \mathrm{col}(D{)}^{\perp }$, the projection [F9] is identity on the first summand and zero on the second, so $Q^T=Q=Q^2$, $\mathrm{\parallel }{\widehat{\mathbf{g}}}_K-\mathbf{g}{\mathrm{\parallel }}_2^2=\mathrm{\parallel }Qϵ-(I-Q)\mathbf{g}{\mathrm{\parallel }}_2^2={ϵ}^{T}Qϵ+\mathrm{\parallel }(I-Q)\mathbf{g}{\mathrm{\parallel }}_2^2,$ because $Q(I-Q)=0$. For $\bar{\mathbf{g}}=D{\bar{\beta }}_K\in \mathrm{col}(D)$, $(I-Q)\bar{\mathbf{g}}=0$; the nearest-point property [F6] therefore gives $\mathrm{\parallel }(I-Q)\mathbf{g}{\mathrm{\parallel }}_2^2\le \mathrm{\parallel }\mathbf{g}-\bar{\mathbf{g}}{\mathrm{\parallel }}_2^2$.

Taking expectations in step 3.1, applying step 2.1 and then iid sampling with [A3] yields $E\mathrm{\parallel }{\widehat{\mathbf{g}}}_K-\mathbf{g}{\mathrm{\parallel }}_2^2\le \mathrm{\Delta }K+E{\sum }_{i=1}^n\{g_0(X_i)-p_K(X_i{)}^T{\bar{\beta }}_K{\}}^2\le \mathrm{\Delta }K+n{C}^2{K}^{-2\gamma }\mathrm{.}$ Divide by $n$ to obtain the claimed expected empirical training-risk bound.