Given a set $\mathcal{X}$ and RKHS $\mathcal{H}$ of functions on $\mathcal{X}$, we can recover a (pseudo)metric on $\mathcal{X}$ by $d(x,y)=||\phi\_x-\phi\_y||\_{\mathcal{H}}$, where $\phi\_x=k(x,\cdot)$.


It is straightforward to see that any function $f \in \mathcal{H}$ which has RKHS norm less than $L$ is Lipschitz (with respect to our metric above) with constant $L$:


$$|f(x)-f(y)|=|\langle f,\phi\_x-\phi\_y\rangle|\leq ||f||\_{\mathcal{H}}d(x,y), $$
for any $x,y \in \mathcal{X}$.


I am very interested in the following question: if we have a function $f\in \mathcal{H}$ which is Lipschitz with constant $L$, is there anything we can say about it's norm $||f||\_{\mathcal{H}}$?



RKHS norm of Lipschitz functions
I think that in general $L(.)$ and $\Vert.\Vert\_\mathcal{H}$ measure quite different things.


Writing $L(f)$ for


$$
\inf\{ M>0:|f(x)-f(x')| \leq Md(x,y) \;\forall \;x,x'\in \mathcal{X}\}
$$


let $\mathcal{X}=\mathbb{Z}$ and $\mathcal{H}=l^2$. Then (unless I've made an embarrassing mistake...) setting $f\_n=1\_{[-n,n]}$ gives you a sequence in $\mathcal{H}$ with $L(f\_n)=1/2$ and $\Vert f\_n\Vert\_\mathcal{H}=2n$.


