= Computational tradeoffs of the kernel trick
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^Tz)^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.
Back to article page
