Kernel Methods: A Frontier-Lab Interview Deep Dive

Why this exists. Kernels are still asked in classical ML interviews, especially for SVM-related questions. The kernel trick is one of the most beautiful results in classical ML and a common interview probe (“why does the dual formulation enable kernels?”). Understanding kernels also clarifies what attention is doing — the attention $Q{K}^{\top }$ is essentially a learned kernel.

1. The kernel trick in one sentence

A kernel function $k(x,x^{\prime })$ computes an inner product in a (possibly infinite-dimensional) feature space without ever computing the features explicitly.

That sentence is the entire content of kernel methods. Once you have it, everything else follows.

Saying it out loud. The kernel trick is this: if your algorithm only ever touches the data through dot products, you can swap that dot product for a kernel function and suddenly you’re working in a much richer feature space, for free. Say you’d like to add every pairwise product of your features so a linear model can pick up interactions. Writing them all out is expensive, and for some kernels it’s literally infinite. But a kernel like $(x^{\top }{x}^{\prime }+1{)}^2$ gives you the dot product in that expanded space in the time it takes to do one dot product and square it. You never build the features; you just compute similarities. The tradeoff is that you now carry the training data around at prediction time instead of a fixed weight vector, so cost scales with dataset size, not dimension.

2. Why kernels exist

The motivation

Linear methods (linear regression, logistic regression, linear SVM) can only learn linear decision boundaries. Real data is often non-linear. Two options:

1. Hand-engineer features. Add $x_1^2,x_1{x}_2,\log x_3$, etc. Then apply a linear method.
2. Use kernels. Implicitly map $x\to \varphi (x)$ in some high-dimensional space, then apply the linear method there.

Kernels become useful when the feature mapping $\varphi$ is high-dimensional or infinite-dimensional — explicit computation of $\varphi (x)$ is intractable, but $\varphi (x{)}^{\top }\varphi (x^{\prime })=k(x,x^{\prime })$ might be cheap.

The trick

Many algorithms can be written so they only ever access the data through inner products $x_i^{\top }{x}_j$. Replace $x_i^{\top }{x}_j$ with $k(x_i,x_j)$ and you have a non-linear version of the algorithm operating in $\varphi$-space — without ever computing $\varphi$.

This is the kernel trick.

Saying it out loud. Kernels exist because linear models can only cut the space with a flat boundary, and most real problems aren’t flat. The old fix was to hand-engineer features — square this, multiply those — and then run your linear model on top. That works, but it explodes: all degree-4 interactions of a thousand features is billions of columns. The kernel insight is that a whole family of algorithms never look at individual features, only at inner products between examples, so you can jump straight to the inner product in the expanded space and skip the expansion. The number that makes it concrete: with the RBF kernel the implicit feature space is infinite-dimensional, and you compute each entry in a few flops.

3. Common kernels

Linear kernel

$$k(x,x^{\prime })=x^{\top }{x}^{\prime }$$

Just the dot product. No mapping. Equivalent to no kernel.

Polynomial kernel

$$k(x,x^{\prime })=(x^{\top }{x}^{\prime }+c{)}^d$$

Implicitly maps to a feature space containing all monomials up to degree $d$. For $d=2$: includes products like $x_1{x}_2,x_1^2$.

RBF (Gaussian) kernel

$$k(x,x^{\prime })=\exp \left(-\gamma \Vert x-x^{\prime }{\Vert }^2\right)$$

The most popular kernel. Implicitly maps to an infinite-dimensional feature space. $\gamma$ controls bandwidth: small $\gamma$ → smooth, large $\gamma$ → wiggly.

Saying it out loud. RBF is the default kernel and it’s basically a similarity that decays with distance — points close together are similar, points far apart are essentially unrelated. If you Taylor-expand that exponential you get infinitely many polynomial terms, which is why people say it maps into an infinite-dimensional space; you never see any of it. The one knob that matters is $\gamma$, the bandwidth. Small $\gamma$ means every point influences a wide neighborhood and you get smooth, almost-linear boundaries; large $\gamma$ means influence dies off immediately and each training point carves out its own little island. That’s the named failure mode: crank $\gamma$ up and RBF-SVM memorizes the training set — perfect training accuracy, chance-level test accuracy.

Sigmoid kernel

$$k(x,x^{\prime })=\tanh (\alpha x^{\top }{x}^{\prime }+c)$$

Inspired by neural networks. Not always positive semi-definite (Mercer’s condition might fail) but used in practice.

Cosine kernel

$$k(x,x^{\prime })=\frac{x^{\top }{x}^{\prime }}{\Vert x\Vert \Vert x^{\prime }\Vert }$$

Normalized inner product. Used heavily in NLP/IR.

4. Mercer’s theorem

In plain language: this section answers “which similarity functions am I actually allowed to plug in?” You can’t just invent any function of two points and call it a kernel — it has to behave like a genuine inner product. Mercer’s theorem gives you the two-item checklist for that, and the notation below is just the formal statement of the checklist.

For a function $k(x,x^{\prime })$ to be a valid kernel (i.e., correspond to some inner product in some feature space):

1. Symmetric: $k(x,x^{\prime })=k(x^{\prime },x)$.
2. Positive semi-definite: for any finite set $\{x_1,\dots ,x_n\}$, the kernel matrix $K_{ij}=k(x_i,x_j)$ has all eigenvalues $\ge 0$.

Equivalently: there exists a feature map $\varphi$ such that $k(x,x^{\prime })=\varphi (x{)}^{\top }\varphi (x^{\prime })$.

This is Mercer’s theorem. It’s why we can use kernels without ever computing $\varphi$ — the PSD condition guarantees an implicit feature space exists.

Saying it out loud. Mercer’s theorem tells you when a similarity function is a legal kernel, and the answer is: it has to be symmetric, and the matrix of pairwise similarities on any set of points has to be positive semi-definite. If those hold, then some feature map exists that makes your kernel an honest dot product — you don’t have to find it, you just get to know it’s there. That’s what licenses the whole trick. And it matters practically: the sigmoid kernel isn’t PSD for all parameter settings, so you can hand a solver a kernel matrix with negative eigenvalues, and then the SVM’s convex optimization problem stops being convex and the solver can diverge or return nonsense.

5. Kernel SVM: the canonical application

Linear SVM optimizes:

$$\underset{w}{\min }\frac{1}{2}\Vert w{\Vert }^2+C\sum _i\max (0,1-y_i(w^{\top }{x}_i+b))$$

The dual formulation (using Lagrange multipliers ${\alpha }_i$):

$$\underset{\alpha }{\max }\sum _i{\alpha }_i-\frac{1}{2}\sum _{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i^{\top }{x}_j)$$

subject to $0\le {\alpha }_i\le C$, ${\sum }_i{\alpha }_i{y}_i=0$. Decision function:

$$f(x)=\sum _i{\alpha }_i{y}_i(x_i^{\top }x)+b$$

The dual only accesses data through inner products. Replace $x_i^{\top }{x}_j$ with $k(x_i,x_j)$:

$$f(x)=\sum _i{\alpha }_i{y}_{i}k(x_i,x)+b$$

Boom — non-linear SVM in the kernel feature space, computed without ever materializing $\varphi$.

Saying it out loud. The reason SVMs and kernels are always taught together is the dual. In the primal you’re solving for a weight vector $w$ that lives in feature space, and if that space is infinite-dimensional you’re stuck. Flip to the dual with Lagrange multipliers and the objective only ever contains $x_i^{\top }{x}_j$ — inner products between training points, nothing else. So you substitute $k(x_i,x_j)$ and you’ve got a nonlinear classifier with no code changes beyond one function call. The tradeoff you pay is scaling: the dual has one variable per training example and needs an $N\times N$ kernel matrix, so past roughly $10^5$ points you’re out of memory.

Support vectors

Most ${\alpha }_i$ end up at 0 in the dual. The non-zero ${\alpha }_i$ correspond to support vectors — points on or inside the margin. Decision function only depends on support vectors:

$$f(x)=\sum _{i\in \text{SV}}{\alpha }_i{y}_{i}k(x_i,x)+b$$

Cost: $O(|\text{SV}|\cdot \text{kernel eval})$ per prediction.

Saying it out loud. Support vectors are the training points that actually matter — the ones sitting on the margin or violating it. Everything comfortably on the right side gets a dual coefficient of exactly zero and drops out of the model entirely. That’s the sparsity that makes kernel SVMs usable: prediction costs one kernel evaluation per support vector, not per training point. The failure mode to name is when that sparsity collapses. With a badly tuned RBF bandwidth or heavy label noise, nearly every point becomes a support vector, and then inference is $O(N)$ kernel evaluations per query and the model is both slow and overfit.

6. RKHS (Reproducing Kernel Hilbert Space)

In plain language: this section is about the space of functions your kernel model can express. Every kernel quietly defines a set of allowed functions, and every model you fit is a weighted sum of kernel evaluations sitting inside that set. The formalism below exists to explain why an infinite-dimensional model doesn’t automatically overfit — the space comes with a built-in notion of “how wiggly is this function,” and training penalizes wiggliness.

The advanced framing.

For any valid kernel, there exists a Hilbert space ${\mathcal{H}}_k$ of functions where:

1. Each kernel evaluation $k(\cdot ,x)$ is itself a function in ${\mathcal{H}}_k$.
2. Inner product in ${\mathcal{H}}_k$ is given by the kernel: $⟨f,k(\cdot ,x)⟩=f(x)$ — the reproducing property.

Functions learned by kernel methods (SVM, kernel ridge, GP) live in ${\mathcal{H}}_k$ — they’re linear combinations of kernel evaluations.

Why it matters: RKHS provides a unified theoretical framework. The “regularization with $\Vert f{\Vert }_{{\mathcal{H}}_k}^2$” view explains why SVM with RBF kernel doesn’t overfit despite operating in infinite dimensions.

Saying it out loud. The RKHS is the honest answer to “how can an infinite-dimensional model possibly generalize?” A kernel doesn’t just give you similarities, it defines a whole space of functions, and that space comes with a norm that measures roughly how wiggly a function is. When you train an SVM or kernel ridge regression you’re not searching all functions — you’re minimizing loss plus that norm, so you’re being pushed toward the smoothest function that fits. The reproducing property is the bit of magic that makes it work: evaluating a function at a point is the same as taking an inner product with the kernel centered at that point. The practical upshot is that capacity is controlled by the regularizer and the bandwidth, not by dimension, which is why infinite dimensions don’t scare anyone here.

7. Other kernel methods

Beyond SVM, the kernel trick applies to many algorithms:

Kernel ridge regression

$$\hat{f}(x)=\sum _i{\alpha }_{i}k(x_i,x),\alpha =(K+\lambda I{)}^{-1}y$$

Closed-form. Just like linear ridge but in kernel space.

Gaussian processes

Bayesian extension. $f\sim \mathrm{GP}(0,k)$. Posterior given data is also Gaussian, with mean $\mu (x)=k(x,X)(K+{\sigma }^{2}I{)}^{-1}y$ and variance ${\sigma }^2(x)=k(x,x)-k(x,X)(K+{\sigma }^{2}I{)}^{-1}k(X,x)$. Provides uncertainty estimates.

Kernel PCA

PCA in feature space via the kernel trick. Useful for non-linear dimensionality reduction.

Kernel k-means

K-means in feature space. Equivalent to spectral clustering for some kernels.

Saying it out loud. Once you see that the trick only needs inner products, you realize it applies almost everywhere. Ridge regression kernelizes into a one-line closed form: invert $K+\lambda I$ and you’re done. PCA kernelizes into nonlinear dimensionality reduction. K-means kernelizes and turns into something very close to spectral clustering. And Gaussian processes are the Bayesian version — same kernel, but you get a posterior variance too, so the model tells you where it’s uncertain, which is why GPs still own Bayesian optimization and hyperparameter search. The shared tradeoff across all of them is that $(K+\lambda I{)}^{-1}$ is $O(N^3)$ to compute and $O(N^2)$ to store, so everything here dies somewhere around tens of thousands of points.

8. Why kernels lost to deep learning

Kernel methods dominated 1995–2010. Then deep learning won. Why?

Computational scaling

Kernel methods are typically $O(N^2)$ memory (full kernel matrix) and $O(N^2)$ to $O(N^3)$ training. For $N>10^5$, infeasible. Deep learning scales linearly in data size.

Representation learning

Kernels are fixed: you choose RBF, polynomial, etc. Deep learning learns the representation end-to-end. For images, text, audio, the right “feature space” is task-specific, and deep learning discovers it.

Hyperparameter tuning

Kernel choice + bandwidth + regularization is hard to tune. Deep learning hyperparameters are easier to navigate at scale.

Where kernels still win

• Small data ($N<10^4$).
• Tabular data where SVM with RBF beats logistic regression but you don’t have the data for deep learning.
• Bayesian uncertainty (Gaussian processes).
• Theoretical analysis (NTK).

Saying it out loud. Kernels lost for two reasons, and only one of them is about speed. The speed one: you need an $N\times N$ kernel matrix, so memory is quadratic and training is quadratic to cubic, which caps you around $10^5$ examples while neural nets scale roughly linearly and just eat more data. The deeper one: a kernel is a similarity function you choose in advance, so the representation is frozen before you see the task. Deep learning learns the representation, and for pixels and text nobody knows how to hand-write the right similarity. Kernels still win in a few places worth naming — small tabular datasets under about ten thousand rows, and anywhere you need calibrated uncertainty, where Gaussian processes are still the standard.

9. The Neural Tangent Kernel (NTK) — connection to deep learning

Jacot et al. 2018. In the infinite-width limit of a deep neural network with appropriate scaling, the network’s training behavior is exactly described by a kernel — the NTK.

$$k_{\text{NTK}}(x,x^{\prime })=\mathbb{E}\left[⟨{\nabla }_{\theta }f(x),{\nabla }_{\theta }f(x^{\prime })⟩\right]$$

i.e., inner product of the gradients of the network’s output with respect to its parameters, in the limit of infinite width.

Why it matters

• Provides a theoretical framework for understanding what NNs are doing.
• The NTK is fixed at initialization — doesn’t change during training (in the infinite-width limit). Training is equivalent to kernel ridge regression with the NTK.
• Explains why over-parameterized NNs generalize: under NTK dynamics, gradient descent finds the minimum-norm solution in ${\mathcal{H}}_{\text{NTK}}$.

Limitations

The NTK theory describes wide networks at initialization. Real NNs at modest width or after substantial training don’t behave purely as NTK — feature learning happens. So NTK is a useful theoretical lens but doesn’t fully explain deep learning’s success.

Saying it out loud. The Neural Tangent Kernel is the punchline that a neural network, in the limit of infinite width, stops being mysterious and becomes kernel ridge regression. The kernel is the inner product of the gradients of the output with respect to the parameters, and in that limit it’s fixed at initialization and never moves during training. So gradient descent on the network is just a linear method in a fixed feature space, and you can prove things about convergence and generalization. It’s a beautiful bridge back to classical theory. But name the limitation, because it’s the follow-up question: real finite-width networks do change their features while training, and that feature learning is most of what makes them work — so NTK explains the trainability, not the magic.

10. Connection to attention

The attention mechanism is essentially a learned kernel.

Attention computes:

$$\mathrm{attention}(Q,K,V{)}_i=\sum _j\frac{\exp (q_i^{\top }{k}_j/\sqrt{d_k})}{{\sum }_{j^{\prime }}\exp (q_i^{\top }{k}_{j^{\prime }}/\sqrt{d_k})}{v}_j$$

Compare to kernel ridge regression’s prediction:

$$\hat{f}(x)=\sum _i{\alpha }_{i}k(x_i,x)$$

Attention is similar — query attends to keys via a kernel-like similarity (dot product), then weighted-averages values.

The key difference: attention’s “kernel” $\exp (q^{\top }k/\sqrt{d_k})$ is learned via $W_Q,W_K$. Classical kernels are fixed. This is why attention is so powerful — it learns the right similarity per task.

This connection is increasingly invoked in research (e.g., Tsai et al., “Transformer Dissection: An Unified Understanding for Transformer’s Attention via the Lens of Kernel”). Frontier-lab interview-relevant.

Saying it out loud. Attention is a kernel method where the kernel got promoted to a trainable parameter. Look at what attention does: for a given query it computes a similarity to every key, normalizes those into weights, and returns a weighted average of the values. That’s structurally identical to kernel regression, where you predict at a new point by averaging training targets weighted by kernel similarity. The difference is the whole story — classical kernels like RBF are fixed before training, while attention’s similarity $\exp (q^{\top }k/\sqrt{d_k})$ is computed through learned projections $W_Q$ and $W_K$, so the model discovers what “similar” means for this task. Same math, and the same quadratic cost: attention is $O(n^2)$ in sequence length for exactly the reason kernel methods are $O(N^2)$ in dataset size.

11. Common interview gotchas

Saying it out loud. If you only keep one thread through all of these, make it this: a kernel is a similarity function that secretly computes a dot product in a bigger space, and any algorithm phrased purely in dot products gets to use it for free. From that one idea you can rederive everything — why the SVM dual matters, why Mercer’s PSD condition is the admission ticket, why RBF is infinite-dimensional, why support vectors are the only points that survive. The two things that trip people up are thinking the feature map gets computed (it never does) and thinking kernels are dead (they’re not — GPs still own uncertainty estimation). And the number to have ready is the scaling wall: quadratic memory in $N$, which is what stopped kernel methods around $10^5$ examples.

12. The 8 most-asked kernel interview questions

1. What’s the kernel trick? Replace inner products with kernel evaluations to operate in implicit feature space.
2. Mercer’s theorem? Symmetric + PSD ⟹ valid kernel.
3. RBF kernel? $\exp (-\gamma \Vert x-x^{\prime }{\Vert }^2)$. Infinite-dimensional implicit feature space. Most popular.
4. Why does kernel SVM use the dual? Dual formulation accesses data only via inner products → kernel trick applies.
5. Support vectors? Non-zero ${\alpha }_i$ in the dual; decision function depends only on these.
6. Why kernels lost to deep learning? $O(N^2)$ scaling, fixed kernels, no representation learning.
7. What’s the NTK? Infinite-width NN behaves as kernel ridge regression with the NTK. Theoretical bridge.
8. Connection to attention? Attention is a learned kernel — query-key dot product is a similarity function the model learns.

13. Drill plan

1. State the kernel trick precisely.
2. Memorize RBF kernel + Mercer’s conditions.
3. Walk through SVM dual derivation.
4. Cite the NTK connection at sketchy level.
5. Drill INTERVIEW_GRILL.md.

14. Further reading

• Schölkopf & Smola, Learning with Kernels (2002) — the textbook.
• Hastie, Tibshirani, Friedman, Elements of Statistical Learning, Chapter 12.
• Rasmussen & Williams, Gaussian Processes for Machine Learning (2006).
• Jacot et al., “Neural Tangent Kernel” (2018).
• Tsai et al., “Transformer Dissection: Attention as a Kernel” (2019).