Questions: Representer Theorem

Question 1

A kernel method is applied to 500 training points using an RBF kernel (infinite-dimensional RKHS). The representer theorem guarantees the solution has what form?

• A. A function represented by the 500 most important eigenfunctions of the kernel
• B. A linear combination of exactly 500 kernel functions: f(x) = sum_{i=1}^{500} alpha_i * k(x_i, x), one centered at each training point
• C. A function that can be expressed with at most 500 parameters in the original input space
• D. A 500-dimensional feature vector that captures the essential information in the RKHS

Answer: (B)

The representer theorem states that the optimal solution lies in the span of {k(x_1, ·), k(x_2, ·), ..., k(x_n, ·)} — the kernel functions centered at the training points. For n = 500 training points, the solution is f*(x) = sum_{i=1}^{500} alpha_i * k(x_i, x). The 500 coefficients alpha_i are all that need to be determined, reducing the infinite-dimensional optimization to a 500-dimensional one. This is remarkable: the RKHS for the RBF kernel is infinite-dimensional, yet the optimal regularized solution lives in a 500-dimensional subspace determined entirely by the training data.

Question 2

The representer theorem applies only to the squared RKHS norm penalty ||f||^2. Other regularizers require different theoretical justification.

• T. True
• F. False

Answer: False

The representer theorem is more general than many expositions suggest. It applies to any regularizer that is a strictly monotonically increasing function of the RKHS norm ||f||, not just the squared norm. This includes ||f||, ||f||^2, ||f||^p for any p > 0, and even non-polynomial increasing functions of the norm. The key requirement is monotonicity: the penalty must increase when the norm increases. This ensures that the component of f orthogonal to the span of the training kernel functions only increases the penalty without reducing the empirical loss, so the optimal solution has zero orthogonal component.

Question 3

Without regularization (minimizing only the empirical loss over the RKHS), the representer theorem still guarantees a finite-dimensional solution.

• T. True
• F. False

Answer: False

Without regularization, the representer theorem does not apply in its standard form. The regularization term is what eliminates the component of f orthogonal to the span of training kernel functions — without it, there may be many functions achieving the same minimum loss, some of which have nonzero orthogonal components. The unregularized problem may not have a unique minimum-norm solution, or the solution may not be finite-dimensional. This is one theoretical reason why regularization is essential in kernel methods, beyond just preventing overfitting — it makes the optimization well-posed and finite-dimensional.

Question 4

Explain why the representer theorem makes kernel methods computationally tractable despite working in potentially infinite-dimensional function spaces.

Model answer: Without the representer theorem, optimizing over an RKHS would require searching an infinite-dimensional space — computationally impossible. The theorem restricts the search to the n-dimensional subspace spanned by kernel functions at the training points, reducing the problem to finding n coefficients alpha_1, ..., alpha_n. The optimization then involves only the n-by-n kernel matrix K_{ij} = k(x_i, x_j), which is finite and computable. For kernel ridge regression, the solution is alpha = (K + lambda*I)^{-1} * y, a standard linear algebra problem. The computational cost is O(n^3) for the matrix inversion, independent of the RKHS dimension. This is the practical miracle of kernel methods: the infinite-dimensional function space collapses to an n-dimensional problem, and the kernel trick means you never need to compute the (possibly infinite-dimensional) feature vectors explicitly.

The O(n^3) cost is also the main limitation of kernel methods for large datasets. Methods like Nystrom approximation and random Fourier features address this by approximating the kernel matrix, but the representer theorem remains the foundational result explaining why exact kernel methods are possible at all.