2
$\begingroup$

Let $K:X \times X \to \mathbb R$ be a (positive-definite) kernel and let $H$ be the induced reproducing kernel Hilbert space (RKHS). Fix $(x_1,y_1),\ldots,(x_n,y_n) \in X \times \mathbb R$. For $t \ge 0$, consider the functional $L:H \to \mathbb R$ defined by

$$ \tag{1} L(h) := \sum_{i=1}^n (|h(x_i)-y_i|+t\|h\|)^2. $$

Question. Is there a representer theorem for minimizers of $L$? That is, is it true that every minimizer $h$ of $L$ can be written as $h = \sum_{i=1}^n c_i K_{x_i}$, where the $c_i$'s are scalars and $K_{x_i} \in H$ is defined by $K_{x_i}(x) = K(x_i,x)$ for any $x \in X$?

Note that if $t=0$, then $L = \sum_{i=1}^n (h(x_i)-y_i)^2$, and the classical representer theorem applies.


More generally, given functions $G:\mathbb R^{n+1} \to \mathbb R$ and $u:\mathbb R \to \mathbb R$, I'm interested in conditions under which the functional $L:H \to \mathbb R$ defined by $$ L(h) := G(u(x_1,y_1),\ldots,u(x_n,y_n),\|h\|), $$ admits a representer theorem. In particular, (1) corresponds to the case where $G(r_1,\ldots,r_n,b) = \sum_i^n (r_i + t b)^2$ and $u(c,d) = |c-d|$, for all $r_1,\ldots,r_n,b,c,d \in \mathbb R$.


A perhaps useful observation

For any $\alpha \in (0,1)$, define the function $L_{\alpha}:H \to \mathbb R$ by $$ L_{\alpha}(h) := \dfrac{1}{\alpha}\sum_{i=1}^n(h(x_i)-y_i)^2 + \dfrac{t^2}{1-\alpha}\|h\|^2. $$

Then, for the function $L:H \to \mathbb R$ defined in (1), one has the identity

$$ L(h) = \inf_{\alpha \in (0,1)}L_{\alpha}(h). $$

It is clear that the $L_{\alpha}$'s admit a representer theorem. I don't know if any of this is useful.

$\endgroup$
2
  • $\begingroup$ Did you know this text? $\endgroup$ Mar 23, 2022 at 0:31
  • $\begingroup$ @JoséCFerreira No, but would be happy to know how this connects with my problem (section number, etc.). Thanks in advance. $\endgroup$
    – dohmatob
    Mar 23, 2022 at 1:16

1 Answer 1

2
$\begingroup$

Let $h=h_1 + h_2$, with $h_1\in\mathrm{span}(\{K(\cdot, x_i)\}_{i=1}^n)$ and $h_2$ in the orthogonal complement of this last set. It follows that $\|h\|_H^2 = \|h_1\|_H^2+ \|h_2\|_H^2$, and $\|h\|_H^2 \geq \|h_1\|_H^2$.

The reproducing property, gives you the equality $$h(x_i) = \langle h,K(\cdot,x_i)\rangle = \langle h_1,K(\cdot,x_i)\rangle + \langle h_2,K(\cdot,x_i)\rangle = \langle h_1,K(\cdot,x_i)\rangle =h_1(x_i)$$ Because $h_2$ is orthogonal to $\mathrm{span}(\{K(\cdot, x_i)\}_{i=1}^n)$.

It follows that, if $\|h_2\|>0$ then $$ L(h) = \sum_{i=1}^n (|h(x_i)-y_i|+t\|h\|)^2>\sum_{i=1}^n (|h_1(x_i)-y_i|+t\|h_1\|)^2=L(h_1).$$

Remark:

  1. To a more general case, let $$L(h) := G(u(h(x_1),y_1),\ldots,u(h(x_n),y_n),\|h\|),$$ being an increasing function, with respect to $\|h\|$. It holds the inequality $$L(h)\geq L(h_1),$$ and all minimizers of $L(h)$, if they exists, are in $\mathrm{span}(\{K(\cdot, x_i)\}_{i=1}^n)$.

  2. Searching for "\(\langle f,K(x,\cdot)\rangle\)" on SearchOnMath perhaps you find some usefull results about the representer theorem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.