# How to Prove the Semi-parametric Representer Theorem

This question concerns the generalized Representer Theorem, due to Schölkopf, Herbrich, and Smola. In this magnificent work, the authors provide two versions of the Representer Theorem, a non-parametric, and a semi-parametric one. Though, they provide a proof only for the non-parametric version, while they say that the proof for the semi-parametric version is slightly more technical, but straightforward.

I fully understand the proof for the non-parametric version, but unfortunately I cannot find a way in order to start the proof of the semi-parametric.

Below, I give the statements of the above two versions of the Representer Theorem, as well as the proof for the non-parametric case, and I would like to discuss about the proof of the semi-parametric version.

#Theorem 1 (Non-parametric Representer Theorem) Suppose we are given a nonempty set $$\mathcal{X}$$, a positive definite real-valued kernel $$k$$ on $$\mathcal{X}\times\mathcal{X}$$, samples $$(\mathbf{x}_1,y_1),\cdots,(\mathbf{x}_m,y_m)\in\mathcal{x}\times\mathbb{R}$$, a strictly monotonically increasing real-valued function $$g$$ on $$[0,\infty)$$, an arbitrary cost function $$c\colon(\mathcal{x}\times\mathbb{R}^2)^m\to\mathbb{R}\cup\{\infty\}$$, and a class of functions $$\mathcal{F}=\bigg\{ f\in\mathbb{R}^{\mathcal{X}} \mid f(\cdot)=\sum_{i=1}^{\infty}\beta_i k(\cdot, \mathbf{z}_i), \beta_i\in\mathbb{R}, \mathbf{z}_i\in\mathcal{X}, \lVert f \rVert < \infty \bigg\}.$$ Here, $$\lVert\cdot\rVert$$ denotes the norm in the Reproducing Kernel Hilbert Space (RKHS) $$\mathcal{H}$$ associated with $$k$$. Then any $$f\in\mathcal{F}$$ minimizing the regularized risk functional $$c \Big( (\mathbf{x}_1,y_1,f(\mathbf{x}_1)), \cdots, (\mathbf{x}_m,y_m,f(\mathbf{x}_m)) \Big) + g\big(\lVert f \rVert\big)$$ admits a representation of the form $$f(\cdot) = \sum_{i=1}^{m} \alpha_i k(\cdot,\mathbf{x}_i).$$

Proof: Let $$\phi: \mathcal{X}\to\mathbb{R}^{\mathcal{X}}$$, $$\mathbf{x}\mapsto k(\cdot,\mathbf{x}).$$ Since $$k$$ is a reproducing kernel, evaluation of the function $$\phi(\mathbf{x})$$ on the point $$\mathbf{x}'$$ yields $$(\phi(\mathbf{x}))(\mathbf{x}')=k(\mathbf{x}',\mathbf{x})=\langle \phi(\mathbf{x}'), \phi(\mathbf{x}) \rangle,$$ for all $$\mathbf{x},\mathbf{x}'\in\mathcal{X}$$. Here $$\langle \cdot,\cdot \rangle$$ denotes the dot product in $$\mathcal{H}$$. Given $$\mathbf{x}_1,\cdots,\mathbf{x}_m$$, any $$f\in\mathcal{F}$$ can be decomposed into a part that lives in the span of the $$\phi(\mathbf{x}_i)$$, and a part which is orthogonal to it, i.e. $$f = \sum_{i=1}^{m} \alpha_i\phi(\mathbf{x}_i) + u,$$ for some $$\alpha\in\mathbb{R}^m$$ and $$u\in\mathcal{F}$$ satisfying fot all $$j$$, $$\langle u,\phi(\mathbf{x}_j) \rangle = 0.$$ Using the latter and the reproducing property mentioned above, application of $$f$$ to an arbitrary point $$\mathbf{x}_j$$ yields $$f(\mathbf{x}_j) = \Big\langle \sum_{i=1}^{m} \alpha_i\phi(\mathbf{x}_i) + u, \phi(\mathbf{x}_j) \Big\rangle = \sum_{i=1}^{m} \alpha_i \Big\langle \phi(\mathbf{x}_i),\phi(\mathbf{x}_j) \Big\rangle,$$ which is independent of $$u$$. Consequently, the first term of the regularized risk functional is independent of $$u$$. As for the second term, since $$u$$ is orthogonal to $$\sum_{i=1}^{m}\alpha_i\phi(\mathbf{x}_i)$$, and $$g$$ is strictly monotonic, we get $$g\big(\lVert f \rVert\big) = g\bigg(\bigg\lVert \sum_{i=1}^{m} \alpha_i\phi(\mathbf{x}_i) + u \bigg\rVert\bigg) = g\bigg( \sqrt{ \bigg\lVert \sum_{i=1}^{m} \alpha_i\phi(\mathbf{x}_i) \bigg\rVert^2 + \bigg\lVert u \bigg\rVert^2 } \bigg) \geq g\bigg( \bigg\lVert \sum_{i=1}^{m} \alpha_i\phi(\mathbf{x}_i) \bigg\rVert \bigg),$$ with equality iff $$u=0$$. Setting $$u=0$$ thus, does not affect the first term of the regularized risk functional, while strictly reducing the second term - hence, any minimizer must have $$u=0$$. Consequently, any solution takes the form $$f=\sum_{i=1}^{m}\alpha_i\phi(\mathbf{x}_i)$$, i.e., using the reproducing property, $$f(\cdot) = \sum_{i=1}^{m}\alpha_i k(\cdot,\mathbf{x}_i).$$ Q.E.D.

Now, the statement of the semi-parametric version extends the non-parametric as follows:

#Theorem 2 (Semi-parametric Representer Theorem)

Suppose that, in addition to the assumptions of the previous theorem, we are given a set of $$M$$ real-valued functions $$\{\psi_p\}_{p=1}^{M}$$ defined on $$\mathcal{X}$$, with the property that the $$m\times M$$ matrix $$\big( \psi_p(\mathbf{x}_i) \big)_{ip}$$ has rank $$M$$. Then, any $$\tilde{f}:=f+h$$, with $$f\in\mathcal{F}$$ and $$h\in\operatorname{span}\{\psi_p\}$$, minimizing the regularized risk functional $$c \Big( (\mathbf{x}_1,y_1,\tilde{f}(\mathbf{x}_1)), \cdots, (\mathbf{x}_m,y_m,\tilde{f}(\mathbf{x}_m)) \Big) + g\big(\lVert f \rVert\big),$$ admits a representation of the form $$\tilde{f}(\cdot) = \sum_{i=1}^{m}\alpha_i k(\cdot,\mathbf{x}_i) + \sum_{p=1}^{M}\beta_p \psi_p(\cdot),$$ with unique coefficients $$\beta_p\in\mathbb{R}$$, for all $$p=1,\cdots,M$$.

It would be nice if you could provide a meaningful sketch of the proof. I think it may help some other people as well, who study this theory, but unfortunately do not have the appropriate background to prove such theorems by themselves (yet!). Thanks a lot!

Suppose that we have $\tilde f = f + h$ as described. Let $V = span( k(\cdot, x_i) )_{i=1,...,m}$. We can write any function $f \in \mathcal{F}$ as $f = f_s + f_p$ where $f_s \in V$ and $f_p \in V^{\perp}$.
This means that $$\tilde f(x_i) = f(x_i) + h(x_i) = f_s(x_i) + f_p(x_i) + h(x_i)$$ but since $f_p \in V^{\perp}$ we have that $f_p(x_i) =0$. Which yields: $$\tilde f(x_i) = f(x_i) + h(x_i) = f_s(x_i) + h(x_i)$$
Thus $$c( (x_i, y_i, \tilde f(x_i))_{i=1,...,m}) = c( (x_i, y_i, f_s(x_i) + h(x_i))_{i=1,...,m})$$ which means that $f_p$ has no effect on $c(\cdot)$. Moreover, since $$\|f\|^2 = \|f_s\|^2 + \|f_p\|^2$$ by the pythagorean theorem, we have $$\|f_s\| \le \|f\|$$ for all $f \in \mathcal{F}$. Thus $g(\|f_s\|) \le g(\|f\|)$ since $g$ is strictly increasing.
Thus we see if a function $\tilde f = f+h$ minimizes the cost function $f_p$ must be zero. Thus $\tilde f = f_s + h$ and since $f_s \in V$ we have that $$\tilde f = \sum_{i=1}^m a_i k(\cdot, x_i) + h$$
Finally when we evaluate $\tilde f(x_j) = \sum_{i=1}^m a_i k(x_j, x_i) + h(x_j)$ we get $m$ equations for $$h(x_j) = \sum_{p=1}^M \beta_p \psi_p(x_j) = \tilde f(x_j) - \sum_{i=1}^m a_i k(x_j, x_i).$$ By the assumptions on $\psi_p(x_j)$ we see that $(\psi_p(x_1),...,\psi_p(x_m))^T$ (for $p=1,2,...,M$) are linearly independent vectors, and thus the coefficients $\beta_p$ are uniquely determined.