Prove the representer theorem

ProofGraduate⏱ 1 hourClassical MLrepresenter theoremorthogonal decompositionrkhsflagship

Theory: Kernels, RKHS and the Representer Theorem →

Problem

Prove that any minimiser of $J(f) = c\big(f(x_1),\dots,f(x_n)\big) + \Omega(\|f\|_{\Hcal_K})$ over $\Hcal_K$ , with $\Omega$ strictly increasing, lies in $\operatorname{span}\{K(x_i,\cdot)\}_{i=1}^n$ . State where each hypothesis is used and give a counterexample showing that strict monotonicity of $\Omega$ cannot be dropped to mere monotonicity if uniqueness of the representation is wanted.

Write a complete argument. Every inequality you use should be one you could state precisely.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
Implement kernel ridge regression run	Classical ML	Coding	Intermediate	1 hour
Kernel ridge regression in closed form	Classical ML	Proof	Intermediate	30 min
The Gaussian kernel is positive definite	Classical ML	Proof	Intermediate	30 min
Prove the O(1/t) rate for gradient descent abyss	Optimization	Proof	Advanced	1 hour
The reproducing property and its consequences	Classical ML	Proof	Advanced	30 min