Why a Representer Theorem Holds
In an RKHS, an objective may use a function only through its values at finitely many inputs, while also penalizing its norm. A representer theorem explains why such an optimization can be reduced to a finite-dimensional subspace, even when the RKHS itself is infinite-dimensional. The key condition here is modest: the penalty must be a nondecreasing function of the norm.
This condition ensures that removing a function component invisible to the observed evaluations cannot worsen the objective. It does not, by itself, guarantee that a minimizer exists or that every minimizer lies in the finite-dimensional subspace. Those distinctions matter when using the theorem.
The reproducing property says \(f(x_i)=\langle f,K(x_i,\cdot)\rangle_{\mathcal H}\). Consequently, the evaluation at each observed input depends only on the component of \(f\) in \(S\). The component orthogonal to \(S\) is invisible to all these evaluations.
The General Representer Result
For any \(f\in\mathcal H\), write its orthogonal decomposition as \(f=s+r\), where \(s\in S\) and \(r\in S^\perp\). Since every kernel section \(K(x_i,\cdot)\) belongs to \(S\), the reproducing property gives \(r(x_i)=0\). Meanwhile, orthogonality gives \(\|f\|_{\mathcal H}^2=\|s\|_{\mathcal H}^2+\|r\|_{\mathcal H}^2\), so \(\|s\|_{\mathcal H}\leq\|f\|_{\mathcal H}\). These facts yield the theorem.
Proof. Fix \(f=s+r\) as in the orthogonal decomposition. For each \(i\), \(r(x_i)=\langle r,K(x_i,\cdot)\rangle_{\mathcal H}=0\), and hence \(f(x_i)=s(x_i)\). Thus the \(\Psi\) terms agree. Also, \(\|s\|_{\mathcal H}\leq\|f\|_{\mathcal H}\), so the nondecreasing property of \(g\) implies \(g(\|s\|_{\mathcal H})\leq g(\|f\|_{\mathcal H})\). Therefore \(J(s)\leq J(f)\).
Because \(S\subseteq\mathcal H\), the infimum over \(\mathcal H\) cannot exceed the infimum over \(S\). Conversely, \(J(s)\leq J(f)\) for the projection \(s\in S\) of every \(f\in\mathcal H\), so the infimum over \(S\) cannot exceed the infimum over \(\mathcal H\). The two infima are equal. If a minimizer \(f\) exists, its projection \(s\) has \(J(s)\leq J(f)\), and \(J(f)\) is already the minimum; therefore \(s\) is a minimizer too. Finally, if \(g\) is strictly increasing and \(r\neq0\), then \(\|s\|_{\mathcal H}<\|f\|_{\mathcal H}\), making \(J(s)<J(f)\). Such an \(f\) cannot be a minimizer. \(\square\)
Worked Example: A Quadratic Penalty in a Linear RKHS
Take \(\mathcal X=\mathbb R^2\) and the linear kernel \(K(x,z)=x^\mathsf Tz\). Its RKHS can be represented by \(f_w(x)=w^\mathsf Tx\), with \(\|f_w\|_{\mathcal H}=\|w\|_2\). Observe only at \(x_1=(1,0)^\mathsf T\), and minimize \(J(f_w)=(f_w(x_1)-2)^2+\|f_w\|_2^2\).
Writing \(w=(a,b)^\mathsf T\), the evaluation is \(f_w(x_1)=a\), so \(J(f_w)=(a-2)^2+a^2+b^2=2(a-1)^2+b^2+2\). The minimum is \(2\), attained at \(a=1,b=0\). Here \(S\) consists exactly of functions \(f_{(a,0)}\): the only observed kernel section is \(K(x_1,\cdot)\). The calculation confirms that the minimizer lies in \(S\); the theorem explains why components in the unobserved direction cannot improve the objective.
What the Theorem Does Not Guarantee
Equality of infima is not the same as attainment: an infimum can fail to be a minimum. Also, when \(g\) is merely nondecreasing, projecting a minimizer into \(S\) preserves or improves its objective, but a nonzero orthogonal component may leave the penalty unchanged. Thus a span-valued minimizer is guaranteed whenever a minimizer exists, but it need not be the only minimizer.
Worked Example: A Flat Penalty Allows Minimizers Outside the Span
Use the same two-dimensional linear RKHS and the single evaluation at \(x_1=(1,0)^\mathsf T\). Set \(J(f_w)=(f_w(x_1)-2)^2+\min(\|w\|_2^2,1)\). The penalty \(g(r)=\min(r^2,1)\) is nondecreasing, but becomes flat once \(r\geq1\).
If \(\|w\|_2<1\), then \(|a|<1\), so \((a-2)^2>1\); the penalty is nonnegative and therefore \(J(f_w)>1\). If \(\|w\|_2\geq1\), the penalty equals \(1\), and the squared loss is nonnegative, so \(J(f_w)\geq1\). Taking \(w=(2,0)^\mathsf T\) gives \(J=1\), proving that the minimum is \(1\).
More generally, every \(w=(2,b)^\mathsf T\) has norm at least \(2\), zero squared loss, and penalty \(1\). Hence every such \(w\) is a minimizer. When \(b\neq0\), its function has a nonzero component orthogonal to \(S\). Projection still gives the span-valued minimizer \(w=(2,0)^\mathsf T\), but not every minimizer is in the span.
Worked Example: A Minimizer Need Not Exist
In the same RKHS, consider one evaluation at \(x_1=(1,0)^\mathsf T\) and the objective \(J(f_w)=\exp(f_w(x_1))\), corresponding to the nondecreasing penalty \(g(r)=0\). With \(w=(a,b)^\mathsf T\), \(J(f_w)=\exp(a)>0\) for every finite \(a\). Taking \(a=-m\) gives \(J=\exp(-m)\to0\) as \(m\to\infty\). The infimum is \(0\), but no \(w\) attains it.
The infimum over the span is also \(0\), as the theorem states, but there is no span-valued minimizer. A representer theorem reduces the search for a minimizer if one exists; it does not automatically establish existence.
A Useful Existence Condition
Existence can be secured by conditions that make the reduced objective lower semicontinuous and force it upward as the norm grows. The next result gives a convenient sufficient condition. It is not required for the equality-of-infima theorem.
Proof. The space \(S\) is finite-dimensional, since it is spanned by \(n\) kernel sections. On \(S\), every evaluation map \(s\mapsto s(x_i)\) is continuous, and the norm is continuous. Thus \(s\mapsto\Psi(s(x_1),\ldots,s(x_n))\) is continuous, and \(s\mapsto g(\|s\|_{\mathcal H})\) is lower semicontinuous. Their sum \(J\) is lower semicontinuous on \(S\).
Let \(m\) be a lower bound for \(\Psi\). Then \(J(s)\geq m+g(\|s\|_{\mathcal H})\), which tends to infinity whenever \(\|s\|_{\mathcal H}\to\infty\). Choose a sequence in \(S\) whose objective values approach \(\inf_{s\in S}J(s)\). Its objective values are bounded above, so the coercive bound just established implies that the sequence is bounded in norm. Every bounded sequence in a finite-dimensional space has a convergent subsequence; let its limit be \(s_*\in S\). Lower semicontinuity gives \(J(s_*)\leq\liminf J(s_k)\) along that subsequence, so \(s_*\) attains the infimum over \(S\). The representer theorem then shows this is also the infimum over \(\mathcal H\). \(\square\)
Worked Example: Strict Increase Does Not Ensure Uniqueness
Again use the linear RKHS in \(\mathbb R^2\), with one evaluation at \(x_1=(1,0)^\mathsf T\), but now set \(J(f_w)=(f_w(x_1)^2-1)^2+\|w\|_2^2\). The penalty \(g(r)=r^2\) is strictly increasing for \(r\geq0\).
For \(w=(a,b)^\mathsf T\), write \(t=a^2\geq0\). Then \(J(f_w)=(a^2-1)^2+a^2+b^2=t^2-t+1+b^2=(t-\tfrac12)^2+\tfrac34+b^2\). The minimum is \(3/4\), attained when \(t=1/2\) and \(b=0\). Thus both \(w=(1/\sqrt2,0)^\mathsf T\) and \(w=(-1/\sqrt2,0)^\mathsf T\) minimize the objective. Strict increase forces both minimizers into \(S\), but it does not make the minimizer unique.
Uniqueness and a Common Pitfall
A familiar sufficient condition for uniqueness is strict convexity of the full objective. For example, if \(\Psi\) is convex and the penalty is \(\lambda\|f\|_{\mathcal H}^2\) with \(\lambda>0\), then the objective is strictly convex on \(\mathcal H\): the squared Hilbert-space norm is strictly convex, and adding a convex function preserves strict convexity. If a minimizer exists, it is therefore unique. Monotonicity of \(g\) alone is weaker: it guarantees the projection comparison, not strict convexity.
Common mistake: “The objective depends only on the observed values, so every minimizer must be a linear combination of the observed kernel sections.” The first clause does not imply the conclusion. The penalty also depends on the function, and if it is flat over some range, an orthogonal component can leave both the evaluations and the penalty unchanged. The correct conclusion is that projection onto \(S\) cannot increase the objective; every minimizer has a span-valued counterpart. To conclude that every minimizer lies in \(S\), require a strictly increasing penalty.
This reduction matters because it separates the infinite-dimensional structure from the finite set of observed evaluations. Once the theorem justifies restricting attention to \(S\), the optimization can be represented using finitely many kernel sections. For computation, existence and uniqueness still require attention: a finite-dimensional representation does not by itself supply either property.
Check Your Understanding
Use the projection argument and the conditions in the results above to answer these questions.
- Why does the orthogonal component \(r\in S^\perp\) have zero evaluation at each observed input?
- What does the representer theorem say about the two infima, even when neither is attained?
- Why can a nonzero orthogonal component remain in a minimizer when the penalty is nondecreasing but not strictly increasing?
- For the existence result, which assumptions ensure that a minimizing sequence in \(S\) has a convergent subsequence whose limit attains the minimum?
- Does a strictly increasing penalty guarantee a unique minimizer? Explain what additional type of condition can ensure uniqueness.