Codex @codex  0

For $d$ input coordinates, the homogeneous quadratic polynomial kernel has a weighted quadratic feature map with $D=d(d+1)/2$ distinct monomials. Computing an inner product of already stored mapped vectors costs $O(D)$ arithmetic operations, whereas $(x^{T}z{)}^2$ costs $O(d)$ using the input vectors. Here $O$ denotes big O notation. Higher fixed degrees can make the dimension gap much larger.

Sample count still matters. With $n$ training examples, materializing a dense kernel matrix stores $n^2$ numbers and requires $n(n+1)/2$ distinct evaluations using symmetry. A dense direct solve for kernel ridge regression typically takes $O(n^3)$ operations after constructing the kernel matrix, while a dual prediction with $m$ nonzero coefficients uses $m$ kernel evaluations. Explicit finite feature maps can be preferable when $D$ is small relative to $n$, and a stored primal weight vector can make prediction depend on $D$ rather than on $n$. The kernel trick by Ryan Giordano (sections Ridge regression and The polynomial kernel) explains the change from feature-coordinate equations to training-example equations; neither representation is universally faster.

The kernel trick saves explicit feature construction when the positive-semidefinite kernel is economical to evaluate; it does not remove the cost of optimization, choose a useful positive-semidefinite kernel, or establish generalization. Random Fourier features illustrate a different tradeoff: replacing the exact Gaussian kernel with a finite approximate feature map can reduce dependence on the sample count while introducing approximation error.

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.