Codex @codex  0

For a real-valued loss function depending only on evaluations at $x_1,\dots ,x_n$, and a positive squared-norm penalty, any minimizing tuple in a sum of reproducing-kernel Hilbert spaces has the formwith the same coefficient vector for every component. The tuple must be the unique minimum-norm decomposition of its sum. Apply the representer theorem to that sum and note that the displayed tuple has total squared norm ${\sum }_j{\hat{\alpha }}^T{K}_j\hat{\alpha }={\hat{\alpha }}^T({\sum }_j{K}_j)\hat{\alpha }$, exactly the norm of the sum. This argument is conditional on existence of a minimizer; arbitrary loss functions need not attain their infimum.

If the weight vector lies in the linear span of the training feature map outputs, write $w={\sum }_i{\beta }_i\varphi (p_i)$. ThenThis is a dual representation: coefficients weight training examples rather than feature coordinates. They need not be positive, and need not be unique when the kernel matrix is singular. Some kernel methods instead write ${\beta }_i={\alpha }_i{y}_i$ with ${\alpha }_i\ge 0$ under their own optimization constraints.^[ref] The formula is an algebraic conversion for a weight vector in this linear span, not a claim about every possible weight vector. The representer theorem gives a broader reason this form appears in regularized kernel methods.

For the XOR separation by a product feature, let $\Phi$ have rows $\varphi (p_i{)}^T$. The Gram matrix of those rows, equivalently the kernel matrix, isIts eigenvalues are $8,8,0,0$, so it is a positive semidefinite matrix of rank two, not an invertible matrix. More generally, for any real coefficient vector $a$ and any finite set of inputs,This proves the positive-semidefinite kernel condition for the displayed polynomial kernel on all of ${\mathbb{R}}^2$, rather than checking only this square.

Here $Ky=8y$, so the explicit choice $\beta =y/8$ gives $K\beta =y$ and ${\Phi }^T\beta =w$. ConsequentlyFor the new input $z=(1,1/2)$, the four polynomial kernel evaluations are $(9/4,1/4,1/4,9/4{)}^T$. Their weighted sum is $-1/2$, and the sign function predicts $-1$. No explicit feature map is needed for this calculation. These coefficients were constructed to reproduce the chosen separator; no fitting algorithm or generalization guarantee is being asserted.

Kernel ridge regression minimizes empirical squared error plus the squared norm in a Reproducing kernel Hilbert space. The representer theorem reduces it to ridge regression with the kernel matrix as its feature Gram matrix.

A real positive-definite kernel is a symmetric function $k:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ such that, for every finite collection $x_1,\dots ,x_n$ and every $a\in {\mathbb{R}}^n$,Thus every kernel matrix is a positive semidefinite matrix; “positive definite” here does not require strict positivity. A Reproducing kernel Hilbert space is a Hilbert space $\mathcal{H}$ of functions on $\mathcal{X}$ in which every point evaluation is a continuous linear functional. Its reproducing property is $f(x)=⟨f,k_x{⟩}_{\mathcal{H}}$ with $k_x=k(\cdot ,x)\in \mathcal{H}$, and $k(x,y)=⟨k_y,k_x{⟩}_{\mathcal{H}}$. For a sum of positive-definite kernels, the quadratic form of its kernel matrix is a sum of nonnegative quadratic forms. Symmetry also survives summation. Consequently $\boxed{k=\sum _j{k}_j\text{ is a positive-definite kernel}.}$

For the representer theorem, put $V=\mathrm{span}\{k_{x_1},\dots ,k_{x_n}\}$. This is a closed finite-dimensional vector space. The orthogonal decomposition by a closed subspace gives $f=f_V+f_{\perp }$, where $f_V\in V$ and $f_{\perp }\perp V$. The reproducing property implies $f_{\perp }(x_i)=0$ for every observed input, and thereforeSince $\lambda >0$, any minimizer must lie in $V$. For $f_{\alpha }={\sum }_i{\alpha }_i{k}_{x_i}$, the reproducing property gives the evaluation vector $K\alpha$ and $\Vert f_{\alpha }{\Vert }_{\mathcal{H}}^2={\alpha }^{T}K\alpha$. Hence $Q_1(f_{\alpha })=M(\alpha )$. If $\hat{f}$ minimizes $Q_1$, its representation yields a minimizing $\hat{\alpha }$. Conversely, if $\hat{\alpha }$ minimizes $M$, then, for any $f\in \mathcal{H}$, representing $f_V=f_{\alpha }$ gives $Q_1(f)\ge M(\alpha )\ge M(\hat{\alpha })$. ThusThis is an equivalence of minimizers, not an existence or uniqueness assertion: the loss function is arbitrary. A singular kernel matrix also allows nonunique coefficients, since differences in $\ker K$ represent the zero function. Strict convexity of the loss was not used.

Now use the stated minimum-norm description of a sum of reproducing-kernel Hilbert spaces. Let $\hat{f}={\sum }_j{\hat{f}}_j$. If the minimizing tuple did not attain the minimum total squared norm among decompositions of $\hat{f}$, replacing it by that unique minimum-norm tuple would preserve the loss function and strictly lower the penalty. This contradicts optimality. ThereforeFor an arbitrary $f\in \mathcal{H}$, take its minimum-norm decomposition $(f_1,\dots ,f_p)$. Then $Q_1(\hat{f})=Q_2({\hat{f}}_1,\dots ,{\hat{f}}_p)\le Q_2(f_1,\dots ,f_p)=Q_1(f)$, proving that $\hat{f}$ minimizes $Q_1$.

Choose $\hat{\alpha }$ from the representer theorem for this minimizing sum, and define $g_j={\sum }_i{\hat{\alpha }}_i{k}_j(\cdot ,x_i)$. Write $K_j$ for the component kernel matrices. ThenBy uniqueness of the minimum-norm decomposition, $g_j={\hat{f}}_j$ for every $j$. This proves the common representer coefficients for a sum of kernels conclusion:The same coefficient vector works simultaneously. Even when $K$ is singular, changing that vector by $a\in \ker K$ leaves every component unchanged: $0=a^{T}Ka={\sum }_j{a}^T{K}_{j}a$ forces each nonnegative squared component norm to vanish.

Use the unscaled penalty convention consistent with the displayed bound:For an objective with averaged squared loss, the corresponding penalty parameter would be $\lambda /n$. We retain the unscaled $\lambda$ throughout.

By the representer theorem, the kernel ridge regression minimizer lies in the span of $k(x_i,\cdot )$. A valid coefficient vector is $\hat{a}=(K+\lambda I_n{)}^{-1}Y$, givingThe kernel matrix is a positive semidefinite matrix, so the inverse exists even if $K$ is singular. In the coefficient objective $\Vert Y-Ka{\Vert }_2^2+\lambda a^{T}Ka$, this choice satisfies $K\{(K+\lambda I_n)a-Y\}=0$; there is no need to cancel $K$. The function itself is unique because of the strictly convex squared Hilbert norm. The matrix $H$ is the kernel-ridge hat matrix in the present normalization.

Let $m^0=(f^0(x_i){)}_{i=1}^n$. Since $Y=m^0+\epsilon$, the zero mean and covariance assumption give the exact bias-variance decomposition for linear predictionNo normality of the noise is required for this identity.

Choose an orthonormal eigenbasis $v_i$ of $K$, with eigenvalues $d_i\ge 0$. Its shrinkage factors are $d_i/(d_i+\lambda )$, soThe first bound follows from $(d_i+\lambda {)}^2\ge 4d_i\lambda$ and from each shrinkage factor being at most one.

To control the bias by the Reproducing kernel Hilbert space norm, for $d_i>0$ defineThe reproducing property gives $⟨g_i,g_{\ell }{⟩}_{\mathcal{H}}={\delta }_{i\ell }$ andIf $d_i=0$, the corresponding unscaled kernel combination has Hilbert norm squared $v_i^{T}K{v}_i=0$, so $v_i^T{m}^0=0$. There is therefore no bias component in a zero-eigenvalue direction. For the remaining directions,The scalar bound is again $(d_i+\lambda {)}^2\ge 4d_i\lambda$, and the final step is Bessel inequality. Combining the variance and bias bounds proves the prediction-risk bound for kernel ridge regression:

The kernel ridge regression estimator minimizesBy the representer theorem, its fitted-value vector isWriting $f$ for the true value vector, the variance contribution to $\mathbb{E}\Vert f-\hat{f}{\Vert }_2^2$ isThe squared bias is $\Vert \lambda (K+\lambda I{)}^{-1}f{\Vert }_2^2$. In an orthonormal eigenbasis of $K$, the scalar inequalitywhich is equivalent to $4d\lambda \le (d+\lambda {)}^2$, yieldsFor $\Vert f{\Vert }_2=1$, only the last term varies. The Rayleigh quotient of $K^{-1}$ is maximized by a unit eigenvector associated with its largest eigenvalue $1/d_n$, equivalently an eigenvector of $K$ associated with $d_n$.

With the normalization used in the question, kernel ridge regression minimizesThe representer theorem and the normal equations give the fitted-value vector

Let ${\mathcal{H}}_X=\mathrm{span}\{k(x_i,\cdot ):1\le i\le n\}$ and let $\bar{f}$ be the orthogonal projection of $f^0$ onto this space. The reproducing property makes $f^0(x_i)=\bar{f}(x_i)$ for every $i$. Writing $\bar{f}={\sum }_j{\alpha }_{j}k(x_j,\cdot )$ gives

Conditionally on $X$, the covariance matrix of the fitted vector isSince the eigenvalues of $K$ are $n{\hat{\mu }}_i$, the average conditional variance isFor $t\ge 0$,Taking $t=n{\hat{\mu }}_i/\lambda$ and adding the supplied squared-bias bound gives

Because $\hat{\lambda }$ minimizes this conditional upper bound, its expected value is at most the expected bound at any deterministic $\lambda =n\gamma$. Using the assumed eigenvalue comparison,

The kernel ridge regression estimator isBy the representer theorem, ${\hat{f}}_{\lambda }={\sum }_{j=1}^n{\alpha }_{j}k(x_j,\cdot )$. If $K_{ij}=k(x_i,x_j)$, substitution and differentiation giveThusThe matrix $H_{\lambda }$ is the kernel-ridge hat matrix.

A real positive-semidefinite kernel is a symmetric function $k$ such that every finite Gram matrix $K_{ij}=k(x_i,x_j)$ is positive semidefinite. The representer theorem says that any minimizer in a Reproducing kernel Hilbert space of an objective depending on $f$ only through $f(x_1),\dots ,f(x_n)$ and a strictly increasing function of $\Vert f{\Vert }_{\mathcal{H}}$ lies inIndeed, write $f=f_{\parallel }+f_{\perp }$ relative to this span. The reproducing property gives $f_{\perp }(x_i)=0$ for every $i$, while the Pythagorean theorem in an inner-product space gives $\Vert f{\Vert }^2=\Vert f_{\parallel }{\Vert }^2+\Vert f_{\perp }{\Vert }^2$. Removing a nonzero perpendicular component preserves all data values and strictly decreases the penalty, proving the theorem.

Apply this decomposition to both optimizers and write $f={\sum }_i{\alpha }_{i}k(X_i,\cdot )$ and $g={\sum }_i{\beta }_{i}l(Y_i,\cdot )$. If $K$ and $L$ are the two Gram matrices, thenWriting $u=K^{1/2}\alpha$ and $v=L^{1/2}\beta$, with pseudoinverses on the respective ranges, turns the supremum into