% Ulrike von Luxburg and Olivier Bousquet


% keywords: metric space, Lipschitz function, large margin, Rademacher
% complexity, transportation problem


\documentclass[twoside,11pt]{article}
\usepackage{jmlr2e}

%----------------------------------------------------------------------
% styles and packages:
%----------------------------------------------------------------------
% for maths:
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{bbold} % used in definition of \charfct below

% for bibliography:
% bibliography: already in jmlr style file
%\usepackage[round]{natbib}
%\bibliographystyle{plainnat}

% misc:
\usepackage{wasysym}% for smiley at end of proofs
\usepackage{xspace}% for nice spaces after macros
\usepackage{letterspace} %needed to fix the overfull-hbox-bug in AMS theorems


%----------------------------------------------------------------------
% new commands and abbreviations:
%----------------------------------------------------------------------

% sets of numbers:
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\Nat}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}

% math letters:
\newcommand{\Bcal}{\mathcal{B}}
\newcommand{\Ccal}{\mathcal{C}}
\newcommand{\Dcal}{\mathcal{D}}
\newcommand{\Fcal}{\mathcal{F}}
\newcommand{\Gcal}{\mathcal{G}}
\newcommand{\Hcal}{\mathcal{H}}
\newcommand{\Xcal}{\mathcal{X}}

% new operators:
\DeclareMathOperator{\minimize}{minimize}
\DeclareMathOperator{\argmin}{argmin}
\DeclareMathOperator{\aufspan}{span} % linear span of a set
\DeclareMathOperator{\linspan}{span} % linear span of a set
\DeclareMathOperator{\supp}{supp} % support of a function
\DeclareMathOperator{\Lip}{Lip}
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator*{\train}{train}
\DeclareMathOperator{\remp}{R_{emp}}

% norms:
\newcommand{\norminf}[1][\cdot]{\|#1\|_{\infty}}
\newcommand{\normL}[1][\cdot]{\|#1\|_{L}}
\newcommand{\normone}[1][\cdot]{\|#1\|_{1}}
\newcommand{\normtwo}[1][\cdot]{\|#1\|_{2}}
\newcommand{\norm}[1][\cdot]{\|#1\|}
\newcommand{\normAE}[1][\cdot]{\|#1\|_{AE}}
\newcommand{\normrbf}[1][\cdot]{\|#1\|_{rbf}}

% equations:
\newcommand{\be}{\begin{eqnarray}}
\newcommand{\ee}{\end{eqnarray}}
\newcommand{\bestar}{\begin{eqnarray*}}
\newcommand{\eestar}{\end{eqnarray*}}
\newcommand{\nn}{\nonumber}
\def\ba#1\ea{\begin{align*}#1\end{align*}} %\ba = \begin{algin*}, \ea = \end{align*}
\def\banum#1\eanum{\begin{align}#1\end{align}} 


% misc math:
\newcommand{\preperp}[1]{{^\perp}#1}
\newcommand{\gdw}{\ensuremath{\; \Leftrightarrow \;}}% genau dann, wenn
\newcommand{\eps}{\ensuremath{\varepsilon}}
\newcommand{\charfct}{\mathbb{1}}
\newcommand{\dcube}{[0,1]^d}
\newcommand{\cor}{\ensuremath{\leftrightarrowtriangle}}%corresponds to
\newcommand{\CX}{\Ccal(\Xcal)}

% misc non-math
\newcommand{\eqstar}{\eqref{star}\xspace}% used as label;
\newcommand{\eqhash}{\eqref{hash}\xspace}% used as label;

% smilies at end of proofs, can be uncommented if you don't like it :-(
%\renewcommand{\BlackBox}{\smiley}

%----------------------------------------------------------------------
% stuff that needs to be removed for submitting:
%----------------------------------------------------------------------
\newcommand{\todo}{{\bf TO DO } }

% suppress most of the underfull/overfull hbox warnings:
\hfuzz = 1cm       % report overfull hbox only if it is larger than  1cm
\hbadness = 10000  % underfull hboxes only reported if badness >= 10000

%%% to get rid of a font warning for bold math fonts I don't even use:
%%\wasyfamily
%%\DeclareFontShape{U}{wasy}{b}{n}{ <-10> ssub * wasy/m/n
%% <10> <10.95> <12> <14.4> <17.28> <20.74> <24.88>wasyb10 }{}

%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
% correct hyphenation
\hyphenation{Lip-schitz ana-lyse ma-the-ma-ti-cal}

\begin{document}
\title{Distance-Based Classification with Lipschitz Functions}
\author{%
\name Ulrike~von~Luxburg  \email ulrike.luxburg@tuebingen.mpg.de \\
\name Olivier~Bousquet \email olivier.bousquet@tuebingen.mpg.de \\
\addr Max Planck Institute for Biological Cybernetics \\
Spemannstrasse 38\\
72076 T\"ubingen,
Germany
}

\editor{Kristin Bennett and Nicol\`{o} Cesa-Bianchi}

\jmlrheading{5}{2004}{669--695}{1/04}{6/04}{Ulrike~von~Luxburg and Olivier~Bousquet}

% Short headings should be running head and authors last names
\ShortHeadings{Distance-Based Classification with Lipschitz Functions
}{von Luxburg and  Bousquet}

\firstpageno{669} 






\maketitle


\begin{abstract}
The goal of this article is to develop a framework for large margin
classification in metric spaces.  We want to find a generalization of
linear decision functions for metric spaces and define a corresponding
notion of margin such that the decision function separates the
training points with a large margin.  It will turn out that using
Lipschitz functions as decision functions, the inverse of the
Lipschitz constant can be interpreted as the size of a margin.  In
order to construct a clean mathematical setup we isometrically embed
the given metric space into a Banach space and the space of Lipschitz
functions into its dual space.  To analyze the resulting algorithm, we
prove several representer theorems. They state that there always
exist solutions of the Lipschitz classifier which can be expressed in
terms of distance functions to training points.  We provide
generalization bounds for Lipschitz classifiers in terms of the
Rademacher complexities of some Lipschitz function classes.  The
generality of our approach can be seen from the fact that several
well-known algorithms are special cases of the Lipschitz classifier,
among them the support vector machine, the linear programming machine,
and the 1-nearest neighbor classifier.
\end{abstract}
%
%----------------------------------------------------------------------
\section{Introduction} \label{sec-intro}
%----------------------------------------------------------------------
%
Support vector machines (SVMs) construct linear decision boundaries in
Hilbert spaces such that the training points are separated with a
large margin. The goal of this article is to extend this approach from
Hilbert spaces to metric spaces: we want to find a generalization of
linear decision functions for metric spaces and define a corresponding
notion of margin such that the decision function separates the
training points with a large margin.
%
The reason why we are interested in metric spaces is that in many
applications it is easier or more natural to construct distance
functions between objects in the data space than positive definite
kernel functions as they are used for support vector
machines. Examples for this situation are the edit distance used to
compare strings or graphs and the earth
mover's distance  on images.  %\citep{RbTomGui00} 
%or the similarity metric constructed in \citep{LiCheLiMaVit}. 














SVMs can be seen from two different points of view.  In the
regularization interpretation, for a given positive definite kernel
$k$, the SVM chooses a decision function of the form $f(x) = \sum_i
\alpha_i k(x_i, x ) + b$ which has a low empirical error $\remp$ and
is as smooth as possible.  According to the large margin point of
view, SVMs construct a linear decision boundary in a Hilbert space
$\Hcal$ such that the training points are separated with a large
margin and the sum of the margin errors is small.  Both viewpoints can
be connected by embedding the sample space $\Xcal$ into the reproducing
kernel Hilbert space $\Hcal$ via the so called ``feature map'' and the
function space $\Fcal$ into the dual $\Hcal'$.  Then the regularizer
(which is a functional on $\Fcal$)
%$\norm[f]^2$ 
corresponds to the inverse margin (which is a norm of a linear
operator), 
%%$\norm[\omega]^2_{\Hcal'}$ (where $\omega$ is the normal vector of the
%%decision hyperplane) 
and the empirical error corresponds to the margin error
\citep[cf. Sections 4.3 and 7 of][]{SchSmo02}. The benefits of these
two dual viewpoints are that the regularization framework gives some
intuition about the geometrical meaning of the norm on $\Hcal$, %$\norm_{\Hcal}$,
and the large margin framework leads to statistical learning theory
bounds on the generalization error of the classifier.

Now consider the situation where the sample space is a metric space
$(\Xcal,d)$.  From the regularization point of view, a convenient set of
functions on a metric space is the set of Lipschitz functions, as
functions with a small Lipschitz constant have low variation.  Thus it
seems desirable to separate the different classes by a decision
function which has a small Lipschitz constant. In this article we want
to construct the dual point of view to this approach.  To this end, we
embed the metric space $(\Xcal,d)$ in a Banach space $\Bcal$ and the space
of Lipschitz functions into its dual space $\Bcal'$.  Remarkably, both
embeddings can be realized as isometries simultaneously. By this
construction, each $x \in \Xcal$ will correspond to some $m_x \in \Bcal$
and each Lipschitz function $f$ on $\Xcal$ to some functional $T_f \in
\Bcal'$ such that $f(x) = T_fm_x$ and the Lipschitz constant $L(f)$ is
equal to the operator norm $\norm[T_f]$.  In the Banach space $\Bcal$
we can then construct a large margin classifier such that the
size of the margin will be given by the inverse of the operator norm
of the decision functional.  The basic algorithm implementing this
approach is
\begin{gather*} %\tag{$*$} \label{star}
\text{minimize } \remp(f) + \lambda L(f)
\end{gather*}
%
in regularization language and
%
\begin{gather*} %\tag{$*$} \label{star}
\text{minimize } L(f) + C\sum\nolimits_i \xi_i \text{ subject to } y_if(x_i)
\geq 1-\xi_i, \; \xi_i \geq 0
\end{gather*}
%
in large margin language. In both cases, $L(f)$ denotes the Lipschitz
constant of the function $f$, and the minimum is taken over a subset
of Lipschitz functions on $\Xcal$.  To apply this algorithm in practice,
the choice of this subset will be important. We will see that by
choosing different subsets we can recover the SVM (in cases where the
metric on $\Xcal$ is induced by a kernel), the linear programming machine
\citep[cf.][]{GraHerEtal99a}, and even the 1-nearest neighbor
classifier.  In particular this shows that all these algorithms are
large margin algorithms. So the Lipschitz framework can help to
analyze a wide range of algorithms which do not seem to be connected
at the first glance.  \\

This paper is organized as follows: in Section \ref{sec-lipschitz-spaces}
we provide the necessary functional analytic background for the
Lipschitz algorithm, which is then derived in Section
\ref{sec-lipschitz-classifier}. We investigate representer theorems for this
algorithm in Section \ref{sec-representer}. It will turn out that the
algorithm always has a solution which can be expressed by distance
functions to training points.  In Section \ref{sec-rademacher} we
compute error bounds for the Lipschitz classifier in terms of
Rademacher complexities. In particular, this gives valuable
information about how fast the algorithm converges for different
choices of subsets of Lipschitz functions. The geometrical
interpretation for choosing different subsets of Lipschitz functions
is further discussed in Section \ref{sec-free}. 





%
%----------------------------------------------------------------------
\section{Lipschitz Function Spaces} \label{sec-lipschitz-spaces}
%----------------------------------------------------------------------
%
% ----------------------------------------
% Lipschitz functions:
%
In this section we introduce several Lipschitz function spaces and
their properties.  For a comprehensive overview we refer to
\citet{Weaver99}. 

A metric space $(\Xcal,d)$ is a set $\Xcal$ together with a metric $d$, that
is a non-negative, symmetric function $d: \Xcal \times \Xcal \to \RR$ which  fulfills
$d(x,y)=0 \gdw x=y$ and the triangle inequality $d(x,y) + d(y,z) \leq
d(x,z)$.
%
A function $f:\Xcal\to \RR$ on a metric space $(\Xcal,d)$ is called a Lipschitz function if
there exists a constant $L$ such that
$|f(x)-f(y)| \leq L d(x,y)$ for all $x,y \in \Xcal$.
The smallest constant $L$ such that this
inequality holds is called the Lipschitz constant of $f$, denoted by
$L(f)$. For convenience, we recall some standard facts about Lipschitz
functions:

\begin{lemma}[Lipschitz functions] \label{prop-facts-lip}
Let $(\Xcal,d)$ be a metric space, $f, g: \Xcal \to \RR$ Lipschitz functions and
$a \in \RR$. Then
$L(f+g) \leq L(f) + L(g)$,
$L(af) \leq |a|L(f)$ and
$L(\min(f,g)) \leq \max\{L(f),L(g)\}$,
where $\min(f,g)$ denotes the pointwise minimum of the functions $f$
and $g$. Moreover, let $f:= \lim_{n \to \infty} f_n$ the pointwise limit of Lipschitz
functions $f_n$ with $L(f_n) \leq c$ for all $n \in \Nat$. Then $f$ is a
Lipschitz function with $L(f) \leq c$.
\end{lemma}

For a metric space $(\Xcal,d)$ consider the set
%
$$\Lip(\Xcal) := \{f:\Xcal \to \RR; \; f \text{ is a bounded Lipschitz
  function}\}.$$
%
It forms a vector space, and the Lipschitz constant $L(f)$ is a
seminorm on this space.  To define a convenient norm on this space we
restrict ourselves to {\em bounded} metric spaces. These are spaces
which have a finite diameter $\diam(\Xcal) := \sup_{x,y \in \Xcal}d(x,y)$.
For the learning framework this is not a big drawback as the training
and test data can always be assumed to come from a bounded region of
the underlying space.  For a bounded metric space $\Xcal$ we choose the
norm
%
$$\normL[f] := \max\left\{ L(f),\frac{\norminf[f]}{\diam(\Xcal)}\right\}$$
%
as our default norm on the space $\Lip(\Xcal)$. 
%
It is easy to see that this indeed is a norm. 
Note that in the mathematical literature, $\Lip(\Xcal)$  is usually endowed
with the slightly different norm 
$\norm[f] := \max \{ L(f),\norminf[f] \}$. But we will see that the
norm $\normL$ fits very naturally in our classification setting, as
already can be seen by the following intuitive argument. 
Functions that are used as classifiers are supposed to take positive and
negative values on the respective classes and satisfy
\be \label{eq-pos-neg}
\norminf[f]
= \sup_x |f(x)|
\leq \sup_{x,y} |f(x) -f(y)|
\leq \diam(\Xcal)L(f), 
\ee
that is $\normL[f] = L(f).$ Hence, the $L$-norm of a classification
decision function
is determined by the quantity $L(f)$ we use as regularizer later on.
Some more technical reasons for the choice of $\normL$ will become clear later.\\
%
%----------------------------------------
% Lip_0(\Xcal):
%

Another important space of Lipschitz functions is constructed as
follows.
Let $(\Xcal_0,d)$ be a metric space with a distinguished ``base point''
$e$ which is fixed in advance. $(\Xcal_0,d,e)$ is called a {\em pointed metric
space}. We define 
%
$$\Lip_0(\Xcal_0) := \{f \in \Lip(\Xcal_0); \; f(e) = 0\}.$$
%
On this space,  the Lipschitz constant $L(\cdot)$ is a norm.
%
%----------------------------------------
% 'translation' between Lip(\Xcal) and Lip_0(\Xcal_0):
%
However, its disadvantage in
the learning framework is the condition $f(e)=0$, which is an
inconvenient a priori restriction on our classifier as $e$ has to be
chosen in advance.
To overcome this restriction, for  a given bounded
metric space $(\Xcal,d)$ we define a corresponding extended pointed metric
space
$\Xcal_0:= \Xcal \cup \{e\}$  for a new base element $e$ with the metric
\begin{gather}  \label{eq-extended-space}
d_{\Xcal_0}(x,y) =
\begin{cases}
d(x,y) & \text{ for } x,y \in \Xcal \\
\diam(\Xcal) & \text{ for } x \in \Xcal, y = e.
\end{cases}
\end{gather}
%
Note that $\diam(\Xcal_0) = \diam(\Xcal)$. Then we define the map
%
\begin{equation} \label{def-embedding-Lip-Lip0}
\psi: \Lip(\Xcal) \to \Lip_0(\Xcal_0), \quad
\psi(f)(x) =
\begin{cases}
f(x) &   \text{ if } x\in \Xcal\\
0 & \text{ if } x = e .
\end{cases}
\end{equation}
%

\begin{lemma}[Isometry between Lipschitz function spaces] \label{lemma-lip-lip0}
$\psi$ is an isometric isomorphism between $\Lip(\Xcal)$ and
$\Lip_0(\Xcal_0)$. 
\end{lemma}
\begin{proof}
Obviously, $\psi$ is bijective and linear. Moreover, for $f_0:= \psi(f)$ we have
\bestar% the \! has to be used to ensure that it is no overfull box
L(f_0) &=& \!\!\sup_{x,y \in \Xcal_0}\! \frac{|f_0(x)-f_0(y)|}{d_{\Xcal_0}(x,y)} =
\max
%\left
\{ \!\sup_{x,y \in \Xcal} \frac{|f(x)-f(y)|}{d(x,y)},
           \sup_{x   \in \Xcal} \frac{|f(x)-f(e)|}{d_{\Xcal_0}(x,e)}
%\right
\}=\\
&=& \max\{ L(f), \frac{\norminf[f]}{\diam(\Xcal)}\} = \normL[f].
\eestar
Hence, $\psi$ is an isometry. 
\end{proof}

%----------------------------------------
% Arens-Eells space:
In some respects, the space $(\Lip_0(\Xcal_0),L(\cdot))$ is more convenient to work with
than $(\Lip(\Xcal), \normL)$. In particular it has some very useful
duality properties.  Let $(\Xcal_0,d,e)$ be a pointed metric space with some
distinguished base element $e$.  A {\em molecule} of $\Xcal_0$ is a
function $m:\Xcal_0\to\RR$ such that its support (i.e., the set where $m$
has non-zero values) is a finite set and $\sum_{x\in \Xcal_0}m(x)=0$. For
$x,y \in \Xcal_0$ we define the {\em basic molecules } $m_{xy}:=
\charfct_x - \charfct_y$. It is easy to see that every molecule $m$
can be written as a (non unique) finite linear combination of basic
molecules. Thus we can define
\begin{equation*} %\label{def-norm-molecule}
\normAE[m]:= \inf\left\{\sum_i|a_i|d(x_i,y_i); \; m = \sum_i a_i
m_{x_iy_i}\right\}
\end{equation*}
%
which is a norm on the space of
molecules. The completion of the space of molecules with
respect to $\normAE$ is called the Arens-Eells space $AE(\Xcal_0)$. Denoting its dual space
(i.e., the space of all continuous linear forms on $AE(\Xcal_0)$)  by
$AE(\Xcal_0)'$ the following theorem holds true \citep[cf.][]{AreEel56,Weaver99}.
%
\begin{theorem}[\boldmath Isometry between $AE(\Xcal_0)'$ and $\Lip_0(\Xcal_0)$]
%[Isometry of $\boldsymbol{\Lip_0(\Xcal_0)}$]
\label{th-isometry-lip-ae}
$AE(\Xcal_0)'$ is isometrically isomorphic to \\$\Lip_0(\Xcal_0)$.
\end{theorem}
This means that we can regard a Lipschitz function $f$ on $\Xcal_0$ as a linear
functional $T_f$ on the space of molecules, and the Lipschitz constant
$L(f)$
coincides with the operator norm of the corresponding
functional $T_f$.
For a molecule $m$ and a Lipschitz function $f$ this duality can be
expressed as
\begin{equation} \label{eq-duality}
\langle f, m \rangle = \sum_{x \in \Xcal_0}m(x)f(x).
\end{equation}
It can be proved that $\normAE[m_{xy}] = d(x,y)$ holds for all basic
molecules $m_{xy}$.  Hence, it is possible to embed $\Xcal_0$ isometrically in
$AE(\Xcal_0)$ via
\begin{equation} \label{eq-embed-X0-AE}
\Gamma : \Xcal_0 \to AE(\Xcal_0), \; x \mapsto m_{xe}. \\
\end{equation}

The norm $\normAE$  has a nice geometrical interpretation in terms of
the {\em mass
transportation problem} \citep[cf.][]{Weaver99}: 
some product is manufactured in
varying amounts at several factories and has to be distributed
to several shops. The (discrete) transportation problem is to find an optimal
way to transport the product from the factories to the shops.
The costs of such a transport are defined as  $\sum_{ij} a_{ij}
d_{ij}$ where $a_{ij}$ denotes the amount of the product
transported from factory $i$ to shop $j$ and $d_{ij}$ the distance
between them. If $f_i$ denotes the amount produced in factory $i$ and
$s_i$ denotes the amount needed in shop $i$, the formal definition of
the transportation problem is 
%
\be \label{def-transportation-problem}
\min_{i,j=1,...,n}  \sum a_{ij} d_{ij}
% 
\;\;\text{ subject to } \;\;
%
a_{ij} \geq 0,\;
 \sum_j a_{ij} = s_j, \;
\sum_i a_{ij} = f_i.
\ee
%



To connect the Arens-Eells space to this problem we identify the
locations of the factories and shops with a molecule $m$. The points
$x$ with $m(x) > 0$ represent the factories, the ones with $m(x) < 0$
the shops.  It can be proved that $\normAE[m]$ equals the minimal
transportation costs for molecule $m$. A special case is when the
given molecule has the form $m_0 = \sum m_{x_iy_j}$.  In this case,
the transportation problem reduces to the {\em bipartite minimal matching
problem}: given $2m$ points $(x_1, \hdots, x_n, y_1,\hdots,y_n)$ in a
metric space, we want to match each of the $x$-points to one of the
$y$-points such that the sum of the distances between the matched
pairs is minimal. The formal statement of this
problem is 
\be \label{def-minimal-matching}
\min_{\pi} \sum_{i,j} d(x_i, y_{\pi(i)})
\ee
where the minimum is taken over all permutations $\pi$ of the set
$\{1,...,n\}$  \citep[cf.][]{Steele97}. \\

In Section \ref{sec-representer} we will also need the notion of a vector
lattice. A vector lattice is a vector space $V$ with an ordering $\preceq$
which respects the vector space structure (i.e., for $x,y,z \in V,
a>0$:
$x\preceq y \implies x+z\preceq y+z$ and $ax\preceq ay$)
and such that for any two
elements $f,g \in V$ there exists a greatest lower bound
$\inf(f,g)$. In particular, the space of Lipschitz functions with the ordering $f
\preceq g \gdw \forall x \; f(x) \leq g(x)$ forms a vector lattice.
%
%----------------------------------------------------------------------
\section{The Lipschitz Classifier} \label{sec-lipschitz-classifier}
%----------------------------------------------------------------------

Let $(\Xcal,d)$ be a metric space and $(x_i,y_i)_{i=1, \hdots, n} \subset
\Xcal\times \{\pm 1\}$ some training data.  In order to be able to define
hyperplanes, we want to embed $(\Xcal,d)$ into a vector space, but without
loosing or changing the underlying metric structure.
%
\subsection{Embedding and Large Margin in Banach Spaces}
%
Our first step is to embed
$\Xcal$ by the identity mapping into the extended space $\Xcal_0$ as described in
\eqref{eq-extended-space},  which in
turn is embedded into $AE(\Xcal_0)$ via \eqref{eq-embed-X0-AE}.  We denote
the resulting composite embedding by
\begin{equation*} %\label{eq-embed-X-AE}
\Phi: \Xcal \to AE(\Xcal_0), \; x \mapsto m_x := m_{xe}.
\end{equation*}
Secondly, we identify $\Lip(\Xcal)$ with $\Lip_0(\Xcal_0)$ according to
\eqref{def-embedding-Lip-Lip0}
%of Lemma \ref{lemma-lip-lip0}
and then  $\Lip_0(\Xcal_0)$ with $AE(\Xcal_0)'$ according to Theorem
\ref{th-isometry-lip-ae}.
Together this defines the map
\begin{equation*}%\label{eq-iso-Lip-AE}
\Psi: \Lip(\Xcal) \to AE(\Xcal_0)', \; f \mapsto T_f.
\end{equation*}
%
\begin{lemma}[Properties of the embeddings] \label{prop-embeddings}
The mappings $\Phi$ and $\Psi$ have the following properties:
\begin{enumerate}
\item $\Phi$ is an isometric embedding of $\Xcal$ into $AE(\Xcal_0)$: to
  every point $x \in \Xcal$ corresponds a molecule $m_x \in AE(\Xcal_0)$ such
  that $d(x,y) = \normAE[m_x - m_y]$ for all $x,y \in \Xcal$.
\item $\Lip(\Xcal)$ is isometrically isomorphic to $AE(\Xcal_0)'$: to every
  Lipschitz function $f$ on $\Xcal$ corresponds an operator $T_f$ on
  $AE(\Xcal_0)$ such that $\normL[f] = \norm[T_f]$ and vice versa.
\item It makes no difference whether we evaluate operators on the
  image of $\Xcal$ in $AE(\Xcal_0)$ or apply Lipschitz functions on $\Xcal$
  directly:
  $T_fm_x = f(x)$.
\item Scaling a linear operator is the same as scaling the
  corresponding Lipschitz function: for $a \in \RR$ we have
  $aT_f = T_{af}$.
\end{enumerate}
\end{lemma}
\begin{proof}
All these properties are direct consequences of the construction and
Equation \eqref{eq-duality}. \\ \mbox{}
\end{proof}

The message of this lemma is that it makes no difference whether
we classify our training data on the space $\Xcal$ with the decision
function $\sgn f(x)$ or on $AE(\Xcal_0)$ with the hyperplane
$\sgn(T_fm_x)$.  The advantage of the latter is that constructing a
large margin classifier in a Banach space is a well studied
problem. In \citet{BenBre00} and \citet{ZhoXiaZhoDai02} it has been
established that constructing a maximal margin hyperplane between the
set $X^+$ of positive and $X^-$ of negative training points in a
Banach space $V$ is
equivalent to finding the distance between the convex hulls of $X^+$
and $X^-$. More precisely, let $C^+$ and $C^-$ the convex hulls of the
sets $X^+$ and $X^-$. In the separable case, we define the margin of a
separating hyperplane $H$ between $C^+$ and $C^-$ as the minimal
distance between the training points and the hyperplane:
%
$$\rho(H) := \inf_{i=1,...,n} d(x_i,H).$$

The margin of the maximal
margin hyperplane coincides with half the distance
%$d(C^+,C^-) = \inf_{p^+ \in C^+, p^- \in C^-} \norm[p^+ - p^-]$$
between the convex hulls of the positive and negative training
points. Hence, determining the maximum margin hyperplane can be
understood as solving the optimization problem $$\inf_{p^+ \in C^+, p^-
  \in C^-} \norm[p^+ - p^-].$$ By duality arguments
\citep[cf.][]{BenBre00} it can be seen that
its solution coincides with the solution of
$$\sup_{T \in  V'} \inf_{p^+ \in C^+, p^- \in C^-}
{\langle T,p^+ - p^- \rangle}/{\norm[T]}.$$ This can be
equivalently rewritten as the optimization problem
%
\be \label{eq-large-margin}
 \inf_{T \in V', b \in \RR } \norm[T] \text{ subject to }
y_i ( \langle T, x_i \rangle + b) \geq 1 \;\;\forall i=1,...,n.
\ee

A solution of this problem is called a large margin classifier. The
decision function has the form 
$f(x) = \langle
T, x \rangle + b$, and its margin is given by  $1/\norm[T]$. For  details  we refer to
\citet{BenBre00} and \citet{ZhoXiaZhoDai02}. \\

\subsection{Derivation of the Algorithm}
%
Now we can apply this construction to our situation. We embed $\Xcal$
isometrically into the Banach space $AE(\Xcal_0)$ and use the above reasoning to construct
a  large margin
classifier.  As the dual space of $AE(\Xcal_0)$ is
$\Lip_0(\Xcal_0)$ and $\langle f, m_x \rangle = f(x)$, the optimization
problem \eqref{eq-large-margin} in our case is 
%
$$ \inf_{f_0 \in \Lip_0(\Xcal_0), b \in \RR} L(f_0) \text{ subject to }
y_i (f_0(x_i) + b ) \geq 1 \;\;\forall i=1,...,n. $$
%
By the isometry stated in Theorem \ref{th-isometry-lip-ae}, this is equivalent to the problem
%
$$ \inf_{f \in \Lip(\Xcal), b \in \RR} \normL[f]\text{ subject to } y_i
(f(x_i) + b ) \geq 1 \;\;\forall i=1,...,n. $$

Next we want to  show that the solution of this optimization problem does
not depend on the variable $b$.  To this
end, we first set $g:= f+b \in \Lip(\Xcal)$ to obtain
%
$$ \inf_{g \in \Lip(\Xcal), b \in \RR} \normL[g-b]\text{ subject to } y_i
g(x_i) \geq 1 \;\;\forall i=1,...,n.$$
%
Then  we observe that
$$\normL[g-b] =
\max \{ L(g-b), \frac{\norminf[g-b]}{\diam(\Xcal)}\} =
\max \{ L(g), \frac{\norminf[g-b]}{\diam(\Xcal)}\} \geq L(g) =
\max \{ L(g), \frac{\norminf[g]}{\diam(\Xcal)}\}.$$

Here the  last step is true because of the fact that
$g$ takes positive and negative values and thus
${\norminf[g]}/{\diam(\Xcal)} \leq L(g)$ as we explained in Equation 
\eqref{eq-pos-neg}
of Section
\ref{sec-lipschitz-spaces}.
Hence, under the constraints $y_i g(x_i) \geq 1$ we have
$\inf_b\normL[g-b] = L(g)$, and we can rewrite our optimization problem
in the final form
%
\begin{gather} \tag{$*$} \label{star}
\inf_{f \in \Lip(\Xcal)} L(f) \text{ subject to } y_if(x_i) \geq 1, \;
i=1,  \hdots , n .
\end{gather}
%
We call a solution of this problem a (hard margin) {\em Lipschitz
classifier}. So we have proved:
%
\begin{theorem}[Lipschitz classifier] \label{th-margin} \sloppy
Let $(\Xcal,d)$ be a bounded metric space, $(x_i,y_i)_{i=1,  \hdots , n} \subset
\Xcal\times \{\pm 1\}$ some training data containing points of both
classes. Then a solution $f$ of \eqref{star} is  a large margin
classifier, and its margin is given by $1/ L(f)$. 
\end{theorem}

One nice aspect about the above construction is that the margin
constructed in the space $AE(\Xcal_0)$ also
has a geometrical meaning in the original input space $\Xcal$ itself: it
is a lower bound on
the  minimal distance
between the ``separation surface'' $S:=\{s \in \Xcal; \; f(s) = 0\}$ and the
training points. To see this, normalize the function $f$ such that
$\min_{i=1,\hdots , n} |f({x_i}) | = 1$. This does not change the set
S. Because of 
$$1 \leq  |f({x_i}) | = |f(x_i)-f(s)|\leq L(f) d(x_i,s)$$ we thus get 
$d(x_i,s) \geq 1/L(f)$. \\
%%Note also that a relation between margins and
%%Lipschitz constants in the context of normed vector spaces has already
%%been observed in \citet{SchSmoWilBar00}.\\

Analogously to SVMs 
we  also define the soft margin
version of the Lipschitz classifier by introducing slack variables
$\xi_i$ to allow some training points to lie inside the margin or even
be misclassified:
%
\begin{gather} \tag{$**$} \label{starstar}
\inf_{f \in \Lip(\Xcal)} L(f) + C \sum_{i=1}^n \xi_i \text{ subject to } y_if(x_i)
\geq 1 - \xi_i, \; \xi_i \geq 0 .
\end{gather}
%
In regularization language, the soft margin Lipschitz classifier can
be stated as
$$\inf_{f \in \Lip(\Xcal)} \ell(y_if(x_i)) + \lambda L(f)$$ where the loss
function $\ell$ is given by 
$\ell(y_i f(x_i)) = \max\{0, 1-y_if(x_i) \}$.  
%%$\ell(y_i f(x_i)) = 0$ if $y_i f(x_i) \geq
%%1$ and $\ell(y_i f(x_i)) = |y_i -f(x_i)|$ otherwise. \\

In Section \ref{sec-representer}, we will give an analytic expression
for a solution of \eqref{star} and show how \eqref{starstar} can be
written as a linear programming problem.  However, it may be sensible
to restrict the set over which the infimum is taken in order to avoid
overfitting. We thus suggest to consider the above optimization
problems over subspaces of $\Lip(\Xcal)$ rather than the whole space
$\Lip(\Xcal)$. In Section \ref{sec-free} we
derive a geometrical interpretation of the choice of different
subspaces.  Now we want to point out some special cases. 

Assume
that we are given training points in some reproducing kernel Hilbert
space $H$.  As it is always the case for linear functions, the
Lipschitz constant of a linear function in $H'$ coincides with its
Hilbert space norm. This means that the support vector machine in $H$
chooses the same linear function as the Lipschitz algorithm, if the
latter takes the subspace of linear functions as hypothesis space. 

In the case where we optimize over the subset of all linear combinations of
distance functions of the form $f(x) = \sum_{i=1}^n a_i d(x_i,x) + b$,
the Lipschitz algorithm can be approximated by the linear programming machine
\citep[cf.][]{GraHerEtal99a}:
$$\inf_{a,b} \sum_{i=1}^{n} |a_i|
 \text{ subject to } y_i(\sum_{i=1}^n a_i d(x_i,x) + b) \geq 1. $$
The reason for this is that the Lipschitz constant of a function
$f(x) = \sum_{i=1}^n a_i d(x_i,x) + b$ is upper bounded by $\sum_i
|a_i|$. 
Furthermore, if we do not restrict the function space at
all, then we will see in the next section that the 1-nearest
neighbor classifier is a solution of the Lipschitz algorithm. 

These examples
show that the Lipschitz algorithm is a very general approach. By
choosing different subsets of Lipschitz functions we recover
several well known algorithms. As the Lipschitz algorithm is a
large margin algorithm according to Theorem \ref{th-margin}, the
same holds for the recovered algorithms. For instance the
linear programming machine, originally designed with little
theoretical justification, can now be understood as a large margin
algorithm.
%
%----------------------------------------------------------------------
\section{Representer Theorems}\label{sec-representer}
%----------------------------------------------------------------------
%
A crucial theorem in the context of SVMs and other kernel
algorithms is the representer theorem \citep[cf.][]{SchSmo02}. It
states that even though the space of possible solutions of these
algorithms forms an infinite dimensional space, there always
exists a solution  in the finite dimensional subspace spanned by
the training points. It is because of this theorem that SVMs
overcome the curse of dimensionality and yield computationally
tractable solutions. In this section we prove a similar theorem
for the Lipschitz classifiers \eqstar and \eqref{starstar}. To simplify the discussion,
we denote $\Dcal := \{d(x,\cdot); \; x \in \Xcal\} \cup \{\charfct\}$ and
$\Dcal_{\train}:= \{d(x_i,\cdot); \; x_i \text{ training point }\}
\cup \{\charfct\}$, where $\charfct$ is the constant-1 function.
%

\subsection{Soft Margin Case}
We first start by recalling a general result which implies the
classical representer theorem in the case of SVMs.
\begin{lemma}[Minimum norm interpolation] \label{lemma-min-norm-inter}
Let $V$ be a function of $n+1$ variables which is non-decreasing in
its $n+1$-st argument. Given $n$ points $x_1,\ldots,x_n$ and a
functional $\Omega$, any function which is a solution of the
problem
\begin{equation}\label{v}
\inf_{f} V(f(x_1),\ldots,f(x_n),\Omega(f))
\end{equation}
%(i.e., $f = \argmin V(f(x_1),\ldots,f(x_n),\Omega(f))$)
is a solution of the minimum norm interpolation problem
\begin{equation}\label{mni}
\inf_{f:\forall i,\,f(x_i)=a_i} \Omega(f)
\end{equation}
%(i.e., $f = \argmin_{f:\forall i,\,f(x_i)=a_i} \Omega(f)$)
for some $a_1,\ldots,a_n\in\RR$.
\end{lemma}

Here, $f$ being a solution of a problem of the form $\inf W(f)$ means
$f = \argmin W(f)$. 
We learned this theorem from M. Pontil, but it seems
to be due to C. Micchelli.
\begin{proof}
Let $f_0$ be a solution of the first problem. Take $a_i=f_0(x_i)$.
Then for any function $f$ such that $f(x_i)=a_i$ for all $i$, we
have 
$$V(f(x_1),\ldots,f(x_n),\Omega(f)) \ge
V(f_0(x_1),\ldots,f_0(x_n),\Omega(f_0)) =
V(f(x_1),\ldots,f(x_n),\Omega(f_0)).$$ Hence, by monotonicity of
$V$ we get $\Omega(f)\ge \Omega(f_0)$, which concludes the proof.
\end{proof}

The meaning of the above result is that if the solutions of
problem \eqref{mni} have specific properties, then the solutions
of problem \eqref{v} will also have these properties. So instead of
studying the properties of solutions of \eqref{starstar} directly, we
will investigate the properties of \eqref{mni} when the functional
$\Omega$ is the Lipschitz norm. 
%
We first need to introduce the concept of Lipschitz extensions.
\begin{lemma}[Lipschitz extension]\label{le-lip-ext}
Given a function $f$ defined on a finite subset $x_1,\ldots,x_n$
of $\Xcal$, there exists a function $f'$ which coincides with $f$ on
$x_1,\ldots,x_n$, is defined on the whole space $\Xcal$, and has the same
Lipschitz constant as $f$. Additionally, it is possible to
explicitly construct $f'$ in the form
\[
f'(x) = \alpha \min_{i=1,\ldots,n} (f(x_i) + L(f)d(x,x_i)) +
(1-\alpha)\max_{i=1,\ldots,n} (f(x_i)-L(f)d(x,x_i))\,,
\]
for any $\alpha\in[0,1]$, with $L(f) = \max_{i,j=1,\ldots,n}
(f(x_i)-f(x_j))/d(x_i,x_j)$.
\end{lemma}
\begin{proof}
Consider the function $g(x)=\min_{i=1,\ldots,n}(f(x_i)+
L(f)d(x,x_i))$. We have 
$$|g(x)-g(y)|\le
\max_{i=1,\ldots,n}|f(x_i)+ L(f)d(x,x_i)-f(x_i)- L(f)d(y,x_i)|\le
L(f)d(x,y),$$
so that $L(g)\le L(f)$. Also, by definition $g(x_i)
\le f(x_i) + L(f)d(x_i,x_i)=f(x_i)$. Moreover, if $i_0$ denotes
the index where the minimum is achieved in the definition of
$g(x_i)$, i.e. $g(x_i) = f(x_{i_0}) +L(f)d(x_i,x_{i_0})$, then by
definition of $L(f)$ we have 
$g(x_i) \ge f(x_{i_0}) + (f(x_i)-f(x_{i_0})) = f(x_i)$. 
As a result, for all $i=1,\ldots,n$
we have $g(x_i)=f(x_i)$, which also implies that $L(g)=L(f)$. \\
%
Now the same reasoning can be applied to $h(x)=\max_{i=1,\ldots,n}
(f(x_i)-L(f)d(x,x_i))$. Since $\alpha\in[0,1]$ we have 
$f'(x_i)=f(x_i)$ for all $i$. Moreover, $L(\alpha g +
(1-\alpha)h)\le \alpha L(g)+ (1-\alpha)L(h) = L(f)$ and thus
$L(f')=L(f)$, which concludes the proof.
\end{proof}

From the above lemma, we obtain an easy way to construct solutions
of minimum norm interpolation problems like \eqref{mni} with
Lipschitz norms, as is expressed in the next lemma.
\begin{lemma}[Solution of the Lipschitz minimal norm interpolation problem]
 \label{lemma-solution-min-norm-inter} \mbox{}\\
Let $a_1,\ldots,a_n\in\RR^n$, $\alpha\in[0,1]$, 
$L_0 = \max_{i,j=1,\ldots,n} (a_i-a_j)/d(x_i,x_j)$, and 
\[
f_\alpha(x) := \alpha \min_{i=1,\ldots,n} (a_i + L_0 d(x,x_i)) +
(1-\alpha)\max_{i=1,\ldots,n} (a_i-L_0 d(x,x_i))\,.
\]
Then $f_\alpha$ is a solution of the minimal norm interpolation
problem \eqref{mni} with $\Omega(f)=L(f)$. 
Moreover, when $\alpha=1/2$ then $f_\alpha$ is a solution of the
minimal norm interpolation problem \eqref{mni} with
$\Omega(f)=\norm[f]_L$.
\end{lemma}
\begin{proof}
Given that a solution $f$ of \eqref{mni} has to satisfy
$f(x_i)=a_i$, it cannot have $L(f)< L_0$. Moreover, by Lemma
\ref{le-lip-ext} $f_\alpha$ satisfies the constraints and has
$L(f)=L_0$, hence it is a solution of \eqref{mni} with
$\Omega(f)=L(f)$.

When one takes $\Omega(f)=\norm[f]_L$, any solution $f$ of
\eqref{mni} has to have $L(f)\ge L_0$ and $\norm[f]_\infty \ge
\max_i |a_i|$. The proposed solution $f_\alpha$ with $\alpha=1/2$
not only satisfies the constraints $f_\alpha(x_i)=a_i$ but also
has $L(f)=L_0$ and $\norm[f]_\infty = \max_i |a_i|$, which shows
that it is a solution of the considered problem.\\
%
To prove that $\norm[f]_\infty = \max_i |a_i|$, consider $x\in \Xcal$
and denote by $i_1$ and $i_2$ the indices where the minimum and the
maximum, respectively,  are achieved in the definition of $f_\alpha(x)$.
Then one has
\[
f_{1/2}(x) \le \frac{1}{2}\left(a_{i_2} + L_0 d(x,x_{i_2})\right)
+ \frac{1}{2}\left(a_{i_2} - L_0 d(x,x_{i_2})\right) = a_{i_2}\,,
\]
and similarly $f_{1/2}(x)\ge a_{i_1}$. 
\end{proof}

Now we can formulate a general representer theorem for the soft
margin Lipschitz classifier. 

\begin{theorem}[Soft margin representer theorem]\label{th-representer-soft}
There exists a solution of the soft margin Lipschitz classifier
\eqref{starstar} in the vector lattice spanned by
$\Dcal_{\train}$ which is of the form
\[
f(x) = \frac{1}{2}\min(a_i + L_0 d(x,x_i)) + \frac{1}{2}\max(a_i -
L_0 d(x,x_i))
\]
for some real numbers $a_1,\ldots,a_n$ with
$L_0:=\max_{i,j}(a_i-a_j)/d(x_i,x_j)$. Moreover one has
$\norm[f]_L = L(f) = L_0$.
\end{theorem}
\begin{proof}
The first claim follows from Lemmas \ref{lemma-min-norm-inter} and
\ref{lemma-solution-min-norm-inter}. The second claim
follows from the fact that a solution of \eqref{starstar}
satisfies $\norm[f]_L = L(f)$.
\end{proof}

Theorem \ref{th-representer-soft} is remarkable as the space $\Lip(\Xcal)$
of possible solutions of \eqref{starstar} contains the whole vector
lattice spanned by $\Dcal$. The theorem thus states that even though
the Lipschitz algorithm searches for solutions in the whole lattice
spanned by $\Dcal$ it always manages to come up with a solution in the
sublattice spanned by $\Dcal_{\train}$.

\subsection{Algorithmic Consequences}
As a consequence of the above theorem, we can obtain a tractable
algorithm for solving problem \eqref{starstar}. First, we determine
the coefficients $a_i$ by solving
\[
\min_{a_1,\ldots,a_n\in \RR} \sum_{i=1}^n \ell(y_ia_i) +
\lambda\max_{i,j}\frac{(a_i-a_j)}{d(x_i,x_j)}\,,
\]
which can be rewritten as a linear programming problem
\[
\min_{a_1,\ldots,a_n,\xi_1,\ldots,\xi_n,\rho\in\RR} \sum_{i=1}^n \xi_i +
\lambda\rho\,,
\]
under the constraints $\xi_i\ge 0$, 
$y_ia_i \geq 1 - \xi_i$, 
$\rho\ge (a_i - a_j)/d(x_i,x_j)$. 
%This problem has $n^2 + 2n$ constraints and $2n+1$ variables. 
Once a solution is
found, one can simply take the function $f_{1/2}$ defined in
Theorem \ref{th-representer-soft} with the coefficients $a_i$
determined by the linear program. Note, however, that in  practical
applications, the solution found by this procedure might overfit as
it optimizes \eqref{starstar} over the whole class $\Lip(\Xcal)$.

\subsection{Hard Margin Case}
The representer theorem for the soft margin case clearly also holds in
the hard margin case, so that there will always be a solution of
\eqref{star} in the
vector lattice spanned by $\Dcal_{\train}$. But in the hard margin case, also
a different representer theorem is valid. We
denote the set of all training points with positive label by
$X^+$, the set of the training points with negative label by
$X^-$, and for two subsets $A,B \subset \Xcal$ we define $d(A,B):=
\inf_{a\in A, b \in B}d(a,b)$.
%
\begin{theorem}[Hard margin representer theorem]
\label{th-representer-sets} Problem \eqstar always has a solution
which is a linear combination of distances to {\em sets}  of
training points.
\end{theorem}
%
To prove this theorem we first need a simple lemma. 
%
\begin{lemma}[Optimal Lipschitz constant]  \label{prop-min-L}
The Lipschitz constant $L^*$ of a solution of \eqstar satisfies 
  $L^* \geq {2}/{d(X^+,X^-)}$.
\end{lemma}
\begin{proof}
For a solution $f$ of  \eqstar we have \bestar L(f) &=& \sup_{x,y
\in \Xcal} \frac{|f(x)-f(y)|}{d(x,y)} \geq \max_{i,j=1,  \hdots , n}
\frac{|f(x_i)-f(x_j)|}{d(x_i,x_j)}
 \nn \\
&\geq& \max_{i,j=1,  \hdots , n}  \frac{|y_i-y_j|}{d(x_i,x_j)} =
\frac{2}{\min_{x_i \in X^+, x_j \in X^-}d(x_i,x_j)} =
\frac{2}{d(X^+,X^-)}. \qquad\quad\;\; \eestar
%
\end{proof}
%
\begin{lemma}[Solutions of \eqref{star}]
\label{prop-solutions-star}
Let $L^* = {2}/{d(X^+,X^-)}$. For all $\alpha\in[0,1]$, the
following functions solve \eqref{star}:
\begin{gather*}
f_\alpha(x): = \alpha \min_i(y_i+L^*d(x,x_i) + (1-\alpha) \max_i (y_i - L^* d(x,x_i))\\
g(x):= \frac{d(x,X^-) - d(x,X^+)}{d(X^+,X^-)}
\end{gather*}
\end{lemma}
\begin{proof}
By Lemma \ref{le-lip-ext}, $f_\alpha$ has Lipschitz constant $L^*$
and satisfies $f_\alpha(x_i)=y_i$. Moreover, it is easy to see
that $y_ig(x_i) \geq 1$. Using the properties of Lipschitz
constants stated in Section \ref{sec-lipschitz-spaces} and the fact
that the function $d(x,\cdot)$ has Lipschitz constant 1 we see
that $L(g)\leq L^*$. Thus $f_\alpha$ and $g$ are solutions of
\eqref{star} by Lemma \ref{prop-min-L}.
\end{proof}

The functions $f_\alpha$ and $g$ lie in the vector lattice spanned
by $\Dcal_{\train}$. As $g$ is a linear combination of distances
to sets of training points we have proved Theorem \ref{th-representer-sets}. \\

It is interesting to have a closer look at the functions of
Lemma \ref{prop-solutions-star}. The functions $f_0$ and
$f_1$ are the smallest and the largest functions, respectively,
that solve problem \eqstar with equality in the constraints: any
function $f$ that satisfies $f(x_i) = y_i$ and has Lipschitz
constant $L^*$ satisfies $f_0(x) \leq f(x) \leq f_1(x)$.  
The
functions $g$ and $f_{1/2}$ are especially remarkable: 
\begin{lemma}[1-nearest neighbor classifier] \label{lemma-1nn}
The functions $g$ and $f_{1/2}$ defined above have the sign of the
$1$-nearest neighbor classifier. 
\end{lemma}
\begin{proof}
It is obvious that 
 $g(x) > 0 \iff d(x,X^+) < d(x,X^-)$ and $g(x)
< 0 \iff d(x,X^+) > d(x,X^-)$. For the second function, we rewrite $f_{1/2}$ as follows:
\[
f_{1/2}(x)=\frac{1}{2}(\min(L^*d(x,X^+)+1,L^*d(x,X^-)-1)-\min(L^*d(x,X^+)-1,L^*d(x,X^-)+1))\,.
\]
Consider $x$ such that $d(x,X^+)\ge d(x,X^-)$. Then 
$d(x,X^+)+1\ge d(x,X^-)-1$ and thus
\[
f_{1/2}(x) =\frac{1}{2}\left(L^*d(x,X^-)-1 -
\min(L^*d(x,X^+)-1,L^*d(x,X^-)+1)\right) \le 0\,.
\]
The same reasoning applies to the situation $d(x,X^+)\le d(x,X^-)$
to yield $f_{1/2}(x)\ge 0$ in this case.
\end{proof}

Note that $g$ needs not reach equality in the constraints on all the
data points, whereas the function $f_{1/2}$ always satisfies equality
in the constraints.
%
Lemma \ref{lemma-1nn} has the surprising consequence that according to
Section \ref{sec-lipschitz-classifier}, the 1-nearest neighbor classifier
actually is a large margin classifier. \\

\subsection{Negative Results}
So far we have proved that \eqstar always has a solution which can
be expressed as a linear combination of distances to sets of training
points. But maybe we even get a theorem stating that we always
find a solution which is a linear combination of distance
functions to single training points?  Unfortunately, in the metric
space setting such a theorem is not true in general. This can be
seen  by the following counterexample:
%
\begin{example} \label{ex1}
Assume four training points $x_1,x_2,x_3,x_4$ with distance matrix
%$[0 \;2 \; 1\;  1;\; 2\; 0 \;1\; 1;\; 1\; 1\; 0\; 2;\; 1\; 1\; 2\; 0\;]$ (in matlab notation)
$$ %
D = \begin{pmatrix}
0 & 2 & 1 & 1\\
2 & 0 & 1 & 1\\
1 & 1 & 0 & 2\\
1 & 1 & 2 & 0
\end{pmatrix}
$$
and label vector $y = (1,1,-1,-1)$. Then the set
$$\{f:\Xcal\to\RR | \; y_if(x_i) \geq 1, \; f(x) = \sum_{i=1}^4 a_i d(x_i,x) +b
\}$$ is empty. The reason for this is that the distance matrix is
singular and we have $d(x_1, \cdot) + d(x_2, \cdot) = d(x_3,\cdot)
= d(x_4, \cdot)$. Hence, in this example, \eqstar has no solution
which is a linear combination of distances to single training
points. But it  still has a solution as linear combination of
distances to sets of training points according to  Theorem
\ref{th-representer-sets}.
\end{example}
%

Another negative result is the following. Assume that instead of
looking for solutions of \eqstar in the space of all Lipschitz
functions we only consider functions in the vector space spanned
by $\Dcal$. Is it in this case always possible to find solution in
the linear span of $\Dcal_{train}$? The answer is no again. An
example for this is the following:
%
\begin{example} \label{ex2}
Let $\Xcal = \{x_1,...,x_5\}$ consist of five points with distance
matrix
$$
D = \begin{pmatrix}
0 & 2 & 1 & 1 & 1 \\
2 & 0 & 1 & 1 & 1\\
1 & 1 & 0 & 2 & 1\\
1 & 1 & 2 & 0 & 2 \\
1 & 1 & 1 & 2 & 0\\
\end{pmatrix}.
$$
Let the first four points be training points with the label vector
$y = (-1,-1,-1,1)$. As above  there exists no feasible function in
the vector space spanned by $\Dcal_{train}$. But as the distance
matrix of all five points is invertible, there exist feasible
functions in the vector space spanned by $\Dcal$.
\end{example}
%

In the above examples the problem was that the distance matrix on
the training points was singular. But there are also other sources
of problems that can occur.  In particular it can be the case that
the Lipschitz constant of a function restricted to the training
set takes the minimal value $L^*$, but the Lipschitz constant on
the whole space $\Xcal$ is larger. Then it can happen that although we
can find a linear combination of distance functions that satisfies
$f(x_i) = y_i$, the function $f$ has a Lipschitz constant larger
than $L^*$ and thus is no solution of \eqstar. An example for this
situation is the following:
%
\begin{example} \label{ex-oben}
Let $\Xcal = \{x_1,...,x_5\}$ consist of five points with distance
matrix
$$
D = \begin{pmatrix}
0 & 1 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 & 2\\
1 & 1 & 0 & 2 & 1\\
1 & 1 & 2 & 0 & 1 \\
1 & 2 & 1 & 1 & 0\\
\end{pmatrix}.
$$
Let the first four points be training points with the label vector
$y = (1,1,-1,-1)$. The optimal Lipschitz constant in this problem
is $L^* = 2/d(X^{+} , X^{-}) = 2$. The function $f(x) = -2d(x_1,x)
- 2d(x_2,x) + 3$ has this Lipschitz constant if we evaluate it on
the training points only. But if we also consider $x_5$, the
function has
Lipschitz constant $4$. \\
\end{example}


These examples show that, in general, Theorem
\ref{th-representer-sets} cannot be improved to work in the vector
space instead of the vector lattice spanned by $\Dcal_{\train}$.
This also holds if we consider some subspaces of the set of
Lipschitz functions. Thus we are in the interesting situation that
it is not enough to consider distance functions to single training
points -- we have to deal with distances to sets of training
points.
%

%----------------------------------------------------------------------
\section{Error Bounds} \label{sec-rademacher}
%----------------------------------------------------------------------
%
In this section we compute error bounds for the Lipschitz
classifier using Rademacher averages. This can be done following
techniques introduced for example in Chapter 3 of 
\citet{DevLug01} or in \cite{BarMen02}.
%
The measures of capacity we consider are the Rademacher average
$R_n$ and the related maximum discrepancy  $\tilde{R}_n$. For an
arbitrary class $\Fcal$ of functions, they are defined as
%
$$R_n(\Fcal) :=
E\left(\frac{1}{n} \sup_{f \in \Fcal} |\sum_{i=1}^{n} \sigma_i
  f(X_i)|\right)
\geq \frac{1}{2} E\left(\frac{1}{n}\sup_{f \in \Fcal} |\sum_{i=1}^{n}
( f(X_i) -
  f(X_i')) \right)| =: \frac{1}{2}\tilde{R}_n(\Fcal)
$$
%
where $\sigma_i$ are iid Rademacher random variables (i.e.,
$Prob(\sigma_i = +1 ) = Prob(\sigma_i = -1 ) = 1/2$), $X_i$ and
$X'_i$ are iid sample points according to the (unknown) sample
distribution, and the expectation is taken with respect to all
occurring random variables. Sometimes we also consider the conditional
Rademacher average $\hat{R}_n$, where the expectation is taken only 
conditionally on the sample points $X_1,...,X_n$. 
%
For decision function $f$, consider the loss function $\ell(f(x),
y) = 1$ if $yf(x) \leq -1 $, $1-yf(x)$ if $0 \leq yf(x) \leq 1$, and
$0$ if $yf(x) \geq 1$. Let $\Fcal$ be a class of functions, denote
by $E$ the expectation with respect to the unknown sample
distribution and by $E_n$ the expectation with respect to the
empirical distribution of the training points.
\begin{lemma}[Error bounds]
With probability at least $1-\delta$ over the iid drawing of $n$
sample points, every $f \in \Fcal$ satisfies
$$E(\ell(f(X),Y)) \leq E_n(\ell(f(X),Y)) + 2R_n(\Fcal) + \sqrt{\frac{8
  \log(2/\delta)}{n}}.$$
\end{lemma}
\begin{proof}
The proof is based on techniques of \citet[chap. 3 of][]{DevLug01}
and \cite{BarMen02}: McDiarmid's concentration inequality,
symmetrization and contraction property of Rademacher averages.
\end{proof}
A similar bound can be obtained with the maximum discrepancy
\citep[see][]{BarMen02}. \\

We will describe two different ways to compute Rademacher averages
for sets of Lipschitz functions. One way is a classical approach
using entropy numbers and leads to an upper bound on $R_n$.  For
this approach we always assume that the metric space $(\Xcal,d)$ is
precompact (i.e., it can be covered by finitely many balls of
radius $\eps$ for every $\eps>0$).

The other way is more elegant: because of the definition of
$\normL$ and the resulting isometries, the maximum discrepancy of
a $\normL$-unit ball of $\Lip(\Xcal)$ is the same as of the
corresponding unit ball in $AE(\Xcal_0)'$. Hence it will be possible
to express $\tilde{R}_n$ as the norm of an element of the
Arens-Eells space. This norm can then be computed via bipartite
minimal matching. In the following, $B$ always denotes the unit
ball of the considered function space.
%----------------------------------------------------------------------
\subsection{The Duality Approach} 
%----------------------------------------------------------------------
The main insight to compute the maximum discrepancy by the duality
approach is the following observation:
%
\be \sup_{\normL[f]\leq 1} | \sum_{i=1}^n f(x_i) - f(x_i') | =
\sup_{\norm[T_f]\leq 1}
| \sum_{i=1}^n T_f m_{x_i} - T_f m_{x_i'} | = \nn\\
= \sup_{\norm[T_f]\leq 1} | \langle T_f, \sum_{i=1}^n m_{x_i} -
m_{x_i'} \rangle | = \normAE[\sum_{i=1}^n m_{x_i x_i'}] \nn \ee
Applying this to the definition of the maximum discrepancy
immediately yields
\begin{equation} \label{eq-rad-dual}
\tilde{R}_n(B) = \frac{1}{n} E \normAE[\sum_{i=1}^n m_{X_i X_i'}].
\end{equation}

As we already explained in Section \ref{sec-lipschitz-spaces}, the norm
$\normAE[\sum_{i=1}^n m_{X_i X_i'}]$ can be interpreted as the
costs of a minimal bipartite matching between $\{X_1,  \hdots ,
X_n\}$ and $\{X_1',
 \hdots , X_n'\}$.  To compute the right hand side of \eqref{eq-rad-dual} we
need to know the expected value of random instances of the
bipartite minimal matching problem, where we assume that the {
points } $X_i$ and $X'_i$ are drawn iid from the sample
distribution. In particular we want to know how this value scales
with the number $n$ of points as this indicates how fast we can
learn. This question has been solved for some special cases of
random bipartite matching. Let the random variable $C_n$ describe
the minimal bipartite matching costs for a matching between the
points $X_1,  \hdots , X_n$ and $X'_1,  \hdots ,X'_n$ drawn iid
according to some distribution $P$. In \citet{Yukich95} it has
been proved that for an arbitrary distribution on the unit square
of $\RR^d$ with $d\geq 3$ we have $\lim C_n / ( n^{d-1/d}) = c > 0$
a.s. for some constant $c$. The upper bound $E C_n \leq c \sqrt{n
\log n}$ for arbitrary distributions on the unit square in $\RR^2$
was presented in \citet{Talagrand91}. These results, together with
Equation \eqref{eq-rad-dual}, lead to the following maximum
discrepancies:
%
\begin{theorem}[Maximum discrepancy of unit ball of $\boldsymbol{\Lip(\dcube)}$]
%  need dcube here as otherwise conflict with parantheses
  \label{th-matching-rademacher}
Let $\Xcal = [0,1]^d  \subset \RR^d$ with the Euclidean metric. Then
the maximum discrepancy of the $\normL$-unit ball $B$  of
$\Lip(\Xcal)$  satisfies 
%
\ba
& \tilde{R}_n(B) \leq c_2 {\sqrt{\log n}}/{\sqrt{n}} \;\;\text{ for all } n
\in \Nat && \text{ if }d=2 \\
%
& \lim_{n \to \infty}  \tilde{R}_n(B)\,\sqrt[d]{n}  = c_d > 0 && \text{ if }
d \geq 3
\ea
where $c_d$ ($d \geq 2)$ are constants which are independent of
$n$ but depend on $d$. 
\end{theorem}

Note that this procedure gives (asymptotically) exact results rather than upper bounds  in
cases where  we have (asymptotically) exact  results on the bipartite matching
costs. This is for example the case for cubes in $\RR^d, d\geq 3$
as \citet{Yukich95} gives an exact limit result, or for $\RR^2$
with the uniform distribution.
%
%----------------------------------------------------------------------
\subsection{Covering Number Approach}
%----------------------------------------------------------------------
%
To derive the Rademacher complexity in more general settings than
Euclidean spaces we use an adapted version of the classical
entropy bound of Dudley based on covering numbers. The covering number
$N(\Xcal, \eps, d)$ of a totally bounded metric space $(\Xcal,d)$ is
the smallest number of balls of radius $\eps$ with centers in $\Xcal$
which can cover $\Xcal$ completely.  The proof of the following  
theorem can be found in the appendix.
%
\begin{theorem}[Generalized entropy bound] \label{th-refined-dudley}
Let $\Fcal$ be a class of functions and $X_1,  \hdots , X_n$ iid sample
points with empirical distribution $\mu_n$. Then, for every $\eps > 0$,
$$
\hat{R}_n(\Fcal) \leq 2\eps +
\frac{4\sqrt{2}}{\sqrt{n}}
\int_{\eps/4}^{\infty}   \sqrt{ \log N(\Fcal, u, {L_2(\mu_n)})} \; du.
$$
\end{theorem}
%
To apply this theorem we need to know covering numbers of spaces of
Lipschitz functions. This can be found for example in \citet{KolTih61}, pp.353--357.
%
\begin{theorem}[Covering numbers for Lipschitz function balls]
\label{th-covering-lip}
For  a totally bounded metric space  $(\Xcal,d)$ and  the unit ball $B$ of
$(\Lip(\Xcal),\normL)$,
\bestar
2^{N(\Xcal,4\eps,d)}
\leq N(B,\eps,\norminf)
\leq \left(2 \left\lceil \frac{2 \diam(\Xcal)}{\eps} \right\rceil + 1
\right)^{N(\Xcal,\frac{\eps}{4},d)}.
\eestar
%
If, in addition,  $\Xcal$ is connected and centered (i.e., for all subsets $A
\subset \Xcal$ with $\diam(A)\leq 2r$ there exists a point $x \in \Xcal$ such that
$d(x,a) \leq r$ for all $a\in A$),
\bestar
2^{N(\Xcal,2\eps,d)}
\leq N(B,\eps,\norminf)
\leq \left( 2 \left\lceil \frac{2 \diam(\Xcal)}{\eps} \right\rceil +1
\right) \cdot 2^{N(\Xcal,\frac{\eps}{2},d)}.
\eestar
\end{theorem}
%
Combining Theorems \ref{th-refined-dudley} and \ref{th-covering-lip}
and using $N(\Fcal,u, {L_2(\mu_n)}) \leq N(\Fcal,u,\norminf)$
now gives a bound on the Rademacher complexity of balls of $\Lip(\Xcal)$:
%
%there seems to be a bug in the AMS theorem environment: The words
%'theorem 12' and the optional argument are not spaced correctly,
%which results in a slightly overfull hbox. To get rid of this overfull box I
%used here the letterspace command - ugly, but it works.
\begin{theorem}%
[\letterspace to .95\naturalwidth{Rademacher complexity of unit ball of }$\boldsymbol{\Lip(\Xcal)}$]
\label{th-rademacher-lip}
Let $(\Xcal,d)$ be a totally bounded metric space with diameter $\diam(\Xcal)$
and $B$ the ball of Lipschitz functions with $\normL[f] \leq 1$.
Then, for every $\eps > 0$,
$$
R_n(B) \leq 2\eps +
\frac{4\sqrt{2}}{\sqrt{n}}
\int_{\eps/4}^{4\diam(\Xcal)}   \sqrt{
N(\Xcal,\frac{u}{4},d) \log
\left(2 \left\lceil \frac{2 \diam(\Xcal)}{u} \right\rceil + 1
\right)
} \; du.
$$
If, in addition, $\Xcal$ is connected and centered, we have
$$
R_n(B) \leq 2\eps +
\frac{4\sqrt{2}}{\sqrt{n}}
\int_{\eps/4}^{2\diam(\Xcal)}   \sqrt{
N(\Xcal,\frac{u}{2},d) \log2 + \log(2 \left\lceil \frac{2 \diam(\Xcal)}{u} \right\rceil + 1
)} \; du.
$$
\end{theorem}

In our framework this is a nice result as the bound on the complexity
of balls
of $\Lip(\Xcal)$ only uses the metric properties of the underlying
space $\Xcal$.
Now we want to compare the results of Theorems \ref{th-matching-rademacher}
and \ref{th-rademacher-lip} for two simple examples. 


\begin{example}[\boldmath $d$-dimensional unit square, $d \geq 3$]\label{ex-Rd}
Let $\Xcal = [0,1]^d \subset \RR^d, d\geq 3$, with the Euclidean
metric $\normtwo$. This is a connected and centered space. 
In Theorem \ref{th-matching-rademacher} we showed that
$\tilde{R}_n(B)$ asymptotically scales as  ${1} /{\sqrt[d]{n}}$, and
this result cannot be improved. Now we want to check whether Theorem 
\ref{th-rademacher-lip} achieves a similar scaling rate. To this end
we choose $\eps = {1} / {\sqrt[d]{n}}$ (as we know that we cannot
obtain a rate smaller than this) 
and use that the covering
numbers of $\Xcal$ have the form $N(\Xcal,\eps,\normtwo) = {c} /
{\eps^d}$
\citep[e.g., page 1 of][]{MenVer03}. 
After evaluating the second integral of Theorem
\ref{th-rademacher-lip} we find that $R_n(B)$ indeed scales as ${1} /
{\sqrt[d]{n}}$.
\end{example}
%%
\begin{example}[2-dimensional unit square]\label{ex-R2}
Let $\Xcal = [0,1]^2 \subset \RR^2$ with the Euclidean metric.
Applying Theorem \ref{th-rademacher-lip} similar to Example
\ref{ex-Rd} yields a bound on $R_n(B)$ that scales as ${\log n} / {\sqrt{n}}$.
\end{example}

In case of Example \ref{ex-Rd} the scaling behavior of the upper bound
on $R_n(B)$ obtained by the covering number approach coincides with
the exact result for $\tilde{R}_n(B)$ derived in Theorem
\ref{th-matching-rademacher}. In case of Example \ref{ex-R2} the
covering number result $\log n /\sqrt{n}$ is slightly worse than
the result $\sqrt{\log(n)}/\sqrt{n}$ obtained in  Theorem
\ref{th-matching-rademacher}.
%
%------------------------------------------------------------
\subsection{Complexity of Lipschitz RBF Classifiers}
%------------------------------------------------------------
In this section we want to derive a bound for the Rademacher
complexity of radial basis function classifiers of the form
\begin{equation} \label{def-rbf}
\Fcal_{rbf} := \{f: \Xcal \to \RR | \; f(x) = \sum_{k=1}^l a_k
g_k(d(p_k,x)), \;g_k \in \Gcal, \; l < \infty \}, 
\end{equation}
where $p_k \in \Xcal$, $a_k\in \RR$, and
$\Gcal \subset \Lip(\Xcal)$ is a (small) set of $\norminf$-bounded Lipschitz
functions on $\RR$ whose Lipschitz constants are  bounded from below by a
constant $c>0$. As an example, consider
$\Gcal = \{g:\RR\to \RR|\; g(x) = \exp(-x^2/\sigma^2), \sigma \geq 1\}$.
The special case $\Gcal  = \{id\}$ corresponds to the function class which is
used by the linear programming machine.
It can easily be seen that the Lipschitz constant of an RBF function
satisfies
$ L(\sum_k a_k g_k (d(p_k,\cdot)) ) \leq \sum_k |a_k| L(g_k).$
%
We define a norm on $\Fcal_{rbf}$ by
%
$$ \normrbf[f] := \inf \left\{ \sum_k |a_k| L(g_k); \; f = \sum_k a_k
g_k(d(p_k, \cdot))  \right\}$$
%
and derive the Rademacher
complexity of a unit ball $B$ of $(\Fcal_{rbf},\normrbf)$.
Substituting $a_k$ by $c_k/L(g_k)$ in the expansion of $f$ we get
\be
\sup_{f \in B}
| \sum_{i=1}^n \sigma_i f(x_i) |
%
&=&
\sup_{\sum|a_k|L(g_k) \leq 1, p_k \in \Xcal, g_k \in \Gcal}
 | \sum_{i=1}^n \sigma_i \sum_{k=1}^l a_k g_k(d(p_k,
 x_i)) | \nn \\
&=&
\sup_{\sum|c_k|\leq 1, p_k \in \Xcal, g_k \in \Gcal}
 | \sum_{i=1}^n \sigma_i \sum_{k=1}^l \frac{c_k}{L(g_k)} g_k(d(p_k,
 x_i)) | \nn \\
%
&=&
\sup_{\sum|c_k|\leq 1, p_k \in \Xcal, g_k \in \Gcal}
| \sum_{k=1}^l {c_k} \sum_{i=1}^n \sigma_i \frac{1}{L(g_k)} g_k(d(p_k, x_i)) |
\nn \\
&=& \sup_{p\in \Xcal, g \in \Gcal}
| \sum_{i=1}^n \sigma_i \frac{1}{L(g)} g(d(p,x_i)) |.
\label{eq-trick}
\ee

For the last step observe that the
supremum in  the linear expansion in the second last line is
obtained when one of the $c_k$ is 1 and all the others are 0.
%
To proceed we
introduce the notations $h_{p,g}(x):=  g(d(p,x_i)) /L(g)$,
$\Hcal:=\{ h_{p,g};\; p \in \Xcal, g \in \Gcal\}$, and
 $\Gcal_1:=\{g/L(g); \; g \in \Gcal \}$. We
rewrite the right hand side of Equation \eqref{eq-trick} as
%
\bestar
%
\sup_{p\in \Xcal, g \in \Gcal}
| \sum_{i=1}^n \sigma_i \frac{1}{L(g)} g(d(p,x_i)) |
&=&
\sup_{h_{p,g} \in \Hcal}
| \sum_{i=1}^n \sigma_i h_{p,g}(x_i) |
\eestar
%
and thus obtain $R_n(B) = R_n(\Hcal)$. To calculate the latter we need
the following:
%
\begin{lemma} \label{lemma-covering-rbf}
$N(\Hcal,2\eps, \norminf) \leq  N(\Xcal,\eps,d) N(\Gcal_1,\eps,\norminf).$
\end{lemma}
\begin{proof}
First we observe that for
$h_{p_1,g_1}, h_{p_2,g_2} \in \Hcal$
%
\be
\lefteqn{\norminf[h_{p_1,g_1} - h_{p_2,g_2}]
%
=
%
\sup_{x \in \Xcal}
| \frac{g_1(d(p_1,x))}{L(g_1)} - \frac{g_2(d(p_2,x))}{L(g_2)} |  }\nn \\
%
&\leq&
%
\sup_{x \in \Xcal} \left(
|  \frac{g_1(d(p_1,x))}{L(g_1)} - \frac{g_1(d(p_2,x))}{L(g_1)}| +
| \frac{|g_1(d(p_2,x))}{L(g_1)} - \frac{g_2(d(p_2,x))}{L(g_2)}|
\right)  \nn \\
%
&\leq&
%
\sup_{x \in \Xcal}|d(p_1,x) - d(p_2,x)| +
\norminf[\frac{g_1}{L(g_1)}-\frac{g_2}{L(g_2)}] \nn \\
%
&\leq&
d(p_1,p_2) + \norminf[\frac{g_1}{L(g_1)}-\frac{g_2}{L(g_2)}] =: d_{\Hcal}(h_{p_1,g_1},
h_{p_2,g_2})
\label{eq-covering}
\ee
%
For the step from the second to the third line we used the Lipschitz
property of $g_1$. Finally, it is easy to see that
$N(\Hcal,2\eps, d_{\Hcal}) \leq N(\Xcal,\eps,d) N(\Gcal_1,\eps,\norminf).$
  \end{proof}

Plugging lemma \ref{lemma-covering-rbf} in Theorem
\ref{th-refined-dudley} yields the following Rademacher complexity:
%
\begin{theorem}[Rademacher complexity of unit ball of $\boldsymbol{\Fcal_{rbf}}$]
  \label{th-rademacher-rbf}\sloppy
Let $B$ be the unit ball of $(\Fcal_{rbf}, \norm_{rbf})$, $\Gcal_1$  the rescaled
functions of $\Gcal$ as defined above,
and $w := \max\{ \diam(\Xcal,d), \diam(\Gcal_1, \norminf) \}$.
Then, for every $\eps > 0$,
$$
R_n(B) \leq  2\eps +
\frac{4\sqrt{2}}{\sqrt{n}}
\int_{\eps/4}^{w}
\sqrt{\log N(\Xcal,\frac{u}{2},d) +
\log N(\Gcal_1,\frac{u}{2},\norminf) }
\;\; du .
$$
\end{theorem}

This theorem is a huge improvement compared to Theorem
\ref{th-rademacher-lip} as instead of the covering numbers we now have
log-covering numbers in the integral.
As an example consider
the linear programming machine on $\Xcal = [0,1]^d$.
Because of $\Gcal =\{id\}$,
the second term in the square root vanishes, and the integral over the
log-covering numbers of $\Xcal$ can be bounded by a constant independent of $\eps$.
As result we obtain that in this case $R_n(B)$ scales as $1/\sqrt{n}$.
%










%----------------------------------------------------------------------
\section{Choosing Subspaces of $\boldsymbol{\Lip(\Xcal)}$} \label{sec-free}
%----------------------------------------------------------------------
So far we always considered the isometric embedding of the given
metric space into the Arens-Eells space and discovered many
interesting properties of this embedding. But there exist many
different isometric embeddings which could be used instead.  Hence,
the construction of embedding the metric space isometrically into some
Banach space and then using a large margin classifier in this Banach
space is also possible with different Banach spaces than the
Arens-Eells space.  For example, \citet{HeiBou03} used the Kuratowski
embedding, which maps a metric space $\Xcal$ isometrically in the
space of continuous functions $(\CX,\norminf)$ (see
Example \ref{ex-kuratowski} below). Now it is a natural question 
whether there are interesting
relationships between large margin classifiers constructed by the
different isometric embeddings, especially with respect to the
Lipschitz classifier. \\

A second question concerns the choice of subspaces of $\Lip(\Xcal)$.
At the end of Section \ref{sec-lipschitz-classifier} we already explained that we
have to work on some ``reasonable'' subspace of Lipschitz functions to
apply the Lipschitz classifier in practice. This is justified by
complexity arguments, but does the large margin interpretation still
hold if we do this? Is there some geometric intuition which could help
choosing a subspace?\\

It will turn out that both questions are inherently related to each
other. We will show that there is a correspondence between embedding
$\Xcal$ into a Banach space $V$ and constructing the large margin
classifier on $V$ on the one hand, and choosing a subspace $F$ of
$\Lip(\Xcal)$ and constructing the Lipschitz classifier from $F$ on
the other hand. Ideally, we would like to have a one-to-one
correspondence between $V$ and $F$. In one direction this would mean
that we could realize any large margin classifier on any Banach space
$V$ with the Lipschitz classifier on an appropriate subspace $F$ of
Lipschitz functions. In the other direction this would mean that
choosing a subspace $F$ of Lipschitz functions corresponds to a large
margin classifier on some Banach space $V$. We could then study the
geometrical implications of a certain subspace $F$ via the geometric
properties of $V$. \\

Unfortunately, such a nice one-to-one correspondence between $V$ and
$F$ is not always true, but in many cases it is. 
We will show that given an embedding into some vector space $V$, the
hypothesis class of the large margin classifier on $V$ always
corresponds to a subspace $F$ of Lipschitz functions (Lemma
\ref{lemma-given-v-then-f}).  In general, this
correspondence will be an isomorphism, but not an isometry. The other
way round, given a subspace $F$ of Lipschitz functions, under some
conditions we can construct a vector space $V$ such that $\Xcal$ can
be isometrically embedded into $V$ and the large margin classifiers on
$V$ and $F$ coincide (Lemma \ref{th-subspace-lip}). \\

The key ingredient in this section is the fact that $AE(\Xcal_0)$ is a
free Banach space. The following definition can be found for example
in \citet{Pestov86}.

\begin{definition}[Free Banach space] \label{def-free}
Let $(\Xcal_0,d,e)$ be a pointed metric space. A Banach space $(E,\norm_E)$ is a
free Banach space over $(\Xcal_0,d,e)$ if the following properties hold:
\begin{enumerate}
\item
There exists an isometric embedding $\Phi: \Xcal_0 \to E$ with $\Phi(e) =
0$, and $E$ is the closed linear span of $\Phi(\Xcal_0)$.
\item For every Banach
space $(V,\norm_V)$ and every Lipschitz map $\Psi: \Xcal_0 \to V$ with $L(\Psi) = 1$ and
$\Psi(e) = 0$ there exists a linear operator $T: E \to V$ with
$\norm[T]=1$ such that $T \circ \Phi = \Psi$.
\end{enumerate}
\end{definition}

It can be shown that the free Banach space over $(\Xcal,d,e)$ always
exists and is unique up to isomorphism \citep[cf. ][]{Pestov86}. \\

\begin{lemma}[\boldmath $AE$ is a free Banach space]
For any pointed metric space $(\Xcal_0,d,e)$, 
$AE(\Xcal_0)$ is a free Banach space. 
\end{lemma}
\begin{proof}
Property (1) of Definition \ref{def-free} is clear by construction. For a proof of
property (2), see for example Theorem 2.2.4 of \citet{Weaver99}.
\end{proof}



We are particularly interested in the case where the mapping $\Psi: \Xcal_0 \to V$
of Definition \ref{def-free} 
is an isometric embedding of $\Xcal_0$ into some vector space $V$. 
Firstly we want to find out under which conditions its
dual $V'$ is isometric isomorphic to some subspace $F$ of
$\Lip(\Xcal)$. Secondly, given a subspace $F$ of $\Lip(\Xcal)$ the
question is whether there exists a Banach space $V$ such that
$\Xcal_0$ can be embedded isometrically into $V$ and simultaneously $V'$ is
isometric isomorphic to $F$. 
Both questions will be answered by considering the mapping $T$ of
Definition \ref{def-free} and its adjoint
$T'$. The following treatment will be rather technical, and it might
be helpful to have Figure \ref{fig-free-bs} in mind, which shows which
relations we want to prove. \\

\begin{figure}[htb]
\begin{center}
\includegraphics[width=0.7\textwidth]{luxburg04b_figures/free_banach_space}
\caption{\em Relations between Banach spaces and subspaces of Lipschitz
  functions. The left part shows the commutative diagram corresponding
to the free Banach space property of $AE(\Xcal_0)$. The right part
shows the adjoint mapping $T'$ of $T$. The dotted arrows in the middle
show the relationships we want to investigate. }
\label{fig-free-bs}
\end{center}
\end{figure}



Now we want to go into detail and start with the first question. For
simplicity, we make the following definition. 


\begin{definition}[Dense isometric embedding]
Let $(\Xcal_0,d)$ a metric space and $V$ a normed space. 
A mapping $\Psi: \Xcal_0 \to V$ is called 
 a {\em dense isometric embedding} if $\Psi$ is an isometry 
and  if $V$ is the norm-closure of
$\linspan\{\Psi(x); x\in \Xcal_0\}$.
\end{definition}

%%Our goal is to characterize the dense isometric embeddings in
%%terms of the class of functions they correspond to when used in
%%large margin classification. More precisely, we want to know the
%%properties of the class of hyperplanes (i.e. dual elements) for
%%those embeddings.
%%Next lemma gives necessary conditions that these space of
%%functions satisfy.


\begin{lemma}[\boldmath Construction of $F$ for given $V$] \label{lemma-given-v-then-f}
Let $(\Xcal_0,d)$ be a pointed metric space, $(V,\norm_V)$ a normed
space and $\Psi:\Xcal_0\to V$  a dense isometric embedding. Then
$V'$ is isomorphic to a closed subspace $F\subset \Lip_0(\Xcal_0)$, 
and the canonical injection $i:F\to
\Lip_0(\Xcal_0)$ satisfies $\norm[i]\le 1$.
%%When $F$ is endowed with the norm $\norm_F$ defined as
%%\[
%%\norm[f]_F := \sup\left\{\sum_{i=1}^k a_i f(x_i) \; ; \; x_i \in
%%\Xcal_0,\; a_i \in\RR,\; k<\infty, \, \norm[\sum_{i=1}^k
%%a_i\Psi(x_i)]_V\le 1\right\}\,
%%\]
%%this isomorphism is isometric.   Moreover, for all
%%$x,y\in \Xcal_0$ we have 
%%\[
%%\sup_{f\in F:\norm[f]_F\le 1} f(x)-f(y) = d(x,y)\,.
%%\]
\end{lemma}

\begin{proof}
Recall the notation
$m_x := \Phi(x)$ from Section \ref{sec-lipschitz-classifier} and
analogously denote $v_x := \Psi(x)$. 
Let $T: AE(\Xcal_0) \to V$ the linear mapping with $T \circ \Phi =
\Psi$ as in Definition \ref{def-free}. As $\Psi$ is an isometry,
$T$ satisfies $\norm[T] = 1$, and maps $AE(\Xcal_0)$ on some dense
subspace of $V$.  Consider the adjoint $T': V' \to AE(\Xcal_0)'$.  It
is well known \citep[e.g., Chapter 4 of][]{Rudin91} that  
$\norm[T] = \norm[T']$ and that $T'$ is injective iff
the range of $T$ is dense. Thus, in our case $T'$ is injective. 
As by construction also $\langle Tm_x, v' \rangle = \langle T'v', m_x
\rangle$, we have a unique correspondence between the linear
functions in $V'$ and some subspace $F:= T'V' \subset
AE(\Xcal_0)'$: for $g \in V'$ and $f = T'g \in \Lip_0(\Xcal_0)$ we have $g(v_x) =
f(m_x)$ for every $x \in \Xcal_0$.
The canonical inclusion $i$ corresponds to the adjoint
$T'$. 
\end{proof}


Lemma \ref{lemma-given-v-then-f} shows that the hypothesis space $V'$ 
constructed by embedding $\Xcal$ into $V$ is isomorphic to a subset $F
\subset \Lip_0(\Xcal_0)$. 
But it is important to note that this isomorphism is not isometric in
general. Let $g \in V'$ and $f \in \Lip_0(\Xcal_0)$ be corresponding
functions, that is  $f = T'g$.  Because of $\norm[T']=1$ we know that
$\norm[f]_{AE'} \leq \norm[g]_{V}$, but in general we do not have
equality.
%%Nor does a
%%monotonicity statement such as $\norm[g_1]_{V'} \leq \norm[g_2]_{V'}
%%\implies \norm[f_1]_{L} \leq \norm[f_2]_{L}$ hold in general.  
This
means that the margins $\norm[g]_{V'}$ and $\norm[f]_{AE'}$ of
corresponding functions are measured with respect to different norms
and might have different sizes.  
As a consequence, the solutions of the two large margin problems 
\ba
\min_{g \in V'} \norm[g]_{V'} \text{ subject to } y_i g(v_{x_i}) \geq
1
\ea and 
\ba
\min_{f \in F} \norm[f]_{L} \text{ subject to } y_i f({x_i}) \geq
1
\ea
might be different,  even though the sets
of feasible functions are the same in both cases. \\

To illustrate this we will consider two examples. The first one shows
how the large margin classifier in $V$
can give different results than the one constructed by using the
corresponding subspace for the Lipschitz classifier. In the second
example we show a situation where both classifiers
coincide. 






\begin{example}[Kuratowski embedding] \label{ex-kuratowski}  \sloppy
Let $(\Xcal,d)$ be an arbitrary compact metric space and
${(\Ccal(\Xcal),\norminf)}$ the space of continuous functions on
$\Xcal$. Define $\Psi: \Xcal \to \Ccal(\Xcal),\; x \mapsto d(x,
\cdot)$. This mapping is an isometric embedding called Kuratowski
embedding, and it has been used in \citet{HeiBou03} to construct a
large margin classifier. We want to compare the large margin
classifiers resulting from the Kuratowski embedding
and the embedding in the Arens-Eells space. 
As an example consider the finite metric  space
$\Xcal = \{x_1,...,x_4\}$ with distance matrix 
\ba
D = \begin{pmatrix}
0 & 5 & 3 & 6 \\ 
5 & 0 & 4 & 1 \\
3 & 4 & 0 & 5 \\
6 &1 & 5 & 0\\
\end{pmatrix}.
\ea Let $V = \linspan\{d(x,\cdot); \; x \in \Xcal\} \subset \CX$,
endowed with the norm $\norminf$. 
$V$ is a 4-dimensional vector space. Let $V'$ its dual space. Via
the mapping $T'$, each linear operator $g \in V'$ corresponds to the
linear operator $f \in \Lip_0(\Xcal_0)$ with $f(x_i) = \langle g,
d(x_i,\cdot) \rangle = : c_i$. Now we want to compare the norms of $g$
in $V'$ and $f$ in $\Lip(\Xcal)$.%% The norm of $f$ in
%%$\Lip_0(\Xcal_0)$ is given by its Lipschitz constant of the extended
%%function $f_0$, or equivalently by $\normL[f]$. 
The norm of $g$ in $V'$ can be computed as follows: \ba
\norm[g]_{V'} %
%
 & = \sup \{ \langle g,v \rangle :\; v \in V, \, \norm[v]_{V} \leq 1 \} \\
%
& = \sup \{ \langle g, \sum_{i=1}^4 a_i d(x_i,\cdot) \rangle :\; a_i
\in \RR, \, 
\norminf[\sum_{i=1}^4 a_i d({x_i},\cdot)]\leq 1 \}  \\
%
& = \sup \{ \sum_{i=1}^4 a_i c_i: \; a_i
\in \RR, \,
-1 \leq \sum_{i=1}^4 a_i  d({x_i},x_j) \leq 1 \text{ for all }
j=1,...,4 \; \}. 
\ea
%
For given function $g \in V'$ (that is, for given values $c_i$) this
norm can be computed by a linear program. Consider the two functions
$g_1, g_2 \in V'$ with values on $x_1,x_2,x_3,x_4$ given as $(-1,-1,-1,-1)$ and $(1,0,1,0)$,
respectively, and let $f_1,f_2 \in \Lip_0(\Xcal_0)$ be the
corresponding Lipschitz functions. Then we have 
$\normL[f_1] = 0.166 < 0.25 = \normL[f_2]$ and 
$\norm[g_1]_{V'} = 0.366 > 0.28 = \norm[g_2]_{V'}$.  
So the norms $\norm_{V'}$ and $\normL$ do not coincide, and moreover
there is no monotonic relationship between them. If the maximal margin algorithm had to
choose between functions $f_1$ and $f_2$, it would 
come to different
solutions,  depending whether the underlying norm is $\norm_{V'}$ as
for the large margin classifier in $V'$ or $\normL$ as for the
Lipschitz classifier in $T'V'$.
\end{example}

\begin{example}[Normed space] \sloppy
Let $(\Xcal,\norm_\Xcal)$ be a normed vector space with dual
${(\Xcal',\norm_{\Xcal'})}$.
As the norm of linear functions coincides with
their Lipschitz constant, $\Xcal'$ is {\em isometrically} isomorphic to a
subspace of $\Lip_0(\Xcal_0).$ This  means that it
makes no difference whether we construct a large margin classifier on
the normed space $\Xcal$ directly or ignore the fact that $\Xcal$ is a normed
space, embed $\Xcal$ into $AE(\Xcal_0)$ and
then construct the Lipschitz classifier on $AE(\Xcal_0)$ with the subspace
 $T'\Xcal'$. We already mentioned this fact in
Section \ref{sec-lipschitz-classifier} when we stated that the SVM solution is
the same one as the Lipschitz classifier on $\Xcal'$.
\end{example}


Now we want to investigate our second question: given some subspace $F
\subset \Lip_0(\Xcal_0)$, is $F$  the dual space of some Banach space $V$
such that $\Xcal_0$ can be embedded isometrically into $V$ and $V' \simeq F$?
%
To answer this question we have to deal with some technical problems.
First of all, $F$ has to possess a {\em pre-dual}, that is a vector
space $V$ whose dual $V'$ coincides with $F$. In general, not every
Banach space possesses a pre-dual, and if it exists, it needs not be
unique. Secondly, it turns out that the canonical injection $T': F \to
\Lip_0(\Xcal_0)$ has to have a {\em pre-adjoint}, that is a mapping $T:
AE(\Xcal_0) \to V$ whose adjoint coincides with $T'$. Pre-adjoints also
not always exist.  In general, neither the existence of a pre-dual nor
the existence of pre-adjoints are easy to prove. One situation where
both can be handled is the case where $F$ is closed under pointwise
convergence:

\begin{lemma}[\boldmath Construction of $V$ for given $F$] \label{th-subspace-lip}
Let $\Xcal_0$ be a bounded metric space, and $F$ a subspace of $(\Lip_0(\Xcal_0),
L(\cdot))$ which is closed under pointwise convergence and satisfies
the condition
\be \label{eq-isometry}
\sup_{f \in F,L(f) \leq 1} |f(x) - f(y)| =  d(x,y)
\ee
for all $x,y \in \Xcal_0$.  Then there
exists a normed space $V$ such that $\Xcal_0$ can be isometrically
embedded into $V$ and its dual $V'$ is isometrically isomorphic to
$F$. 
\end{lemma}



Before we can start with the proof we need two more definitions:
Let $M$ be a subspace of some Banach space $V$ and $N$ a subspace of the
dual space $V'$. Then the annihilator $M^{\perp}$ and the
pre-annihilator $\preperp N$
are defined as $M^{\perp} = \{T \in V'; \;Tm = 0 \text{ for all } m \in
M\}$ and $\preperp N = \{e \in V; \;Te = 0 \text{ for all } T \in
N\}$. As the proof is a bit technical, we refer to \citet{Megginson98} for
background reading.\\

\begin{proof}
For a bounded metric space $\Xcal_0$, the topology of pointwise
convergence on $\Lip_0(\Xcal_0)$ coincides with its weak* topology. Thus
by assumption, $F$ is weak*-closed, which implies that $\preperp{F}$
is a closed subspace of $AE(\Xcal_0)$. Hence, the quotient space $V :=
AE(\Xcal_0)/\preperp{F}$ exists, and there exists an isometric isomorphism
between $V'$ and $(\preperp{F})^{\perp}$. As $F$ is weak*-closed,
$(\preperp{F})^{\perp} = F$.
% (Megginson Lemma 2.6.6.).
So $V$ is a pre-dual of $F$.
%
Let $T': F \to \Lip_0(\Xcal_0)$ be the canonical inclusion. It has a pre-adjoint,
namely the quotient mapping $\pi: AE(\Xcal_0) \to V$.
Define the mapping $\Psi: \Xcal_0 \to V$, $x \mapsto \pi m_x =:v_x$.
We have
$$
\langle f, v_x \rangle =
\langle f, \pi m_x \rangle =
\langle T'f, m_x \rangle =
\langle f, m_x \rangle =
f(x). $$ Hence, by assumption \eqref{eq-isometry}, $\Psi$ is an
isometry:
$$
\norm[\Psi(x) - \Psi(y)]_V =
\sup_{f \in F, L(f) \leq 1} \{|\langle f, v_x -v_y \rangle | \}
=
\sup_{f \in F,   L(f) \leq 1} \{|f(x) - f(y)|\} = d(x,y).
$$
\end{proof}

Lemma \ref{th-subspace-lip} gives a nice interpretation of what it
means geometrically to choose a subspace $F$ of Lipschitz functions:
the Lipschitz classifier with hypothesis space $F$ corresponds to
embedding $\Xcal$ isometrically into the pre-dual $V$ of ${F}$ and
constructing the large margin classifier on $V$ directly. Condition
\eqref{eq-isometry}, which $F$ has to satisfy to allow this
interpretation, intuitively means that $F$ has to be a ``reasonably
large'' subspace.


\begin{example}[Linear combination of distance functions] \sloppy Let $F$ be the subspace of $\Lip(\Xcal)$ consisting of
  functions of the form $f(x) = \sum_i a_i d(x_i,x) + b$, and $\bar{F}
  \subset \Lip(\Xcal)$ its closure under pointwise convergence. As norm on
  $\bar{F}$ we take the Lipschitz constant. On $\bar{F}$, condition
  \eqref{eq-isometry} is satisfied: trivially, we always have $\leq$
  in \eqref{eq-isometry}, and for given $x,y \in \Xcal$, equality is
  reached for the function $f= d(x,\cdot)$. So we can conclude by
  Lemma \ref{th-subspace-lip} that the Lipschitz classifier on
  $\bar{F}$ has the geometrical interpretation explained above.
\end{example}











%----------------------------------------------------------------------
\section{Discussion}
%----------------------------------------------------------------------
%
We derived a general approach to large margin classification on metric
spaces which uses Lipschitz functions as decision functions.  Although
the Lipschitz algorithm, which implements this approach, has been
derived in a rather abstract mathematical framework, it boils down to
an intuitively plausible mechanism: it looks for a decision function
which has a small Lipschitz constant. This agrees with the regularization
principle that tries to avoid choosing functions with a high
variation.
The solution of the Lipschitz algorithm is well behaved as, by the
representer theorems of Section \ref{sec-representer}, it can always
be expressed by distance functions to training points. For some
special cases, the solution corresponds to solutions of other well
known algorithms, such as the support vector machine, the linear
programming machine, or the 1-nearest neighbor classifier.
We provide Rademacher complexity bounds for some of the
involved function classes which can be used to bound the
generalization error of the classifier.
\\

In spite of all those nice properties there are several important
questions which remain unanswered. To apply the Lipschitz algorithm in
practice it is important to choose a suitable subspace of Lipschitz
functions as hypothesis space.  In Section \ref{sec-free} we found a
geometrical explanation of what the choice of certain subspaces $F$
means: it is equivalent to using a different isometric embedding of
the metric space into some Banach space. But this explanation does not
solve the question of which subspace we should choose in the end.
Moreover, there exist isometric embeddings in certain Banach spaces
which have no such interpretation in terms of subspaces of Lipschitz
functions.  For example, \citet{HeiBou03} studied the Kuratowski
embedding of a metric space into its space of continuous functions to
construct a large margin algorithm. As we explained in Example
\ref{ex-kuratowski}, the large margin classifier resulting from this
embedding can be different from the Lipschitz classifier. 
%%The question of which embedding should be used has a similar flavor
%%as the problem of choosing the kernel function for support vector
%%machines. There are attempts to solve the latter by computing
%%capacities of some kernel function classes \citep[e.g.,][]{BouHer03}. This might
%%also be a passable way to treat this problem in the Lipschitz function
%%case.
It is an interesting question how different embeddings into different
Banach spaces should be compared. One way to do this could be 
comparing the capacities
of the induced function spaces. An interesting question in this
context is to find the ``smallest space'' (for instance, in terms of
the Rademacher complexities) in which a given data space can be
embedded isometrically. \\



  

There is also a more practical problem connected to the choice of the
subspace of Lipschitz functions.  To implement the Lipschitz algorithm
for a given subspace of Lipschitz functions, we need to know some way
to efficiently compute the Lipschitz constants of the functions in the
chosen subspace. For example, in case of the linear programming
machine it was possible to bound the Lipschitz constants of the
functions in the parameterized subspace of functions 
$\sum_i a_i d(x_i,\cdot) + b$ in terms of their parameters by $\sum_i
|a_i|$. But in many cases, there is no obvious parametric
representation of the Lipschitz constant of a class of functions. Then
it is not clear how the task of minimizing the Lipschitz constant can
be efficiently implemented.\\


An even more heretic question is whether isometric embeddings should
be used at all. In our approach we adopted the point of view that a
meaningful distance function between the training points is given by
some external knowledge,  and that we are not allowed to question it. But in
practical applications it is often the case that distances are
estimated by some heuristic procedure which might not give a sensible
result for all the training points.  In those cases the paradigm of
isometric embedding might be too strong. Instead we could look for
bi-Lipschitz embeddings or low distortion embeddings of the metric
space into some Banach space, or even into some Hilbert space. We
would then loose some (hopefully unimportant) information on the distances in the metric
space, but the gain might consist in a simpler structure of the
classification problem in the target space.\\

Finally, many people argue that for classification only ``local
properties'' should be considered. One example is the assumption that
the data lies on some low dimensional manifold in a higher dimensional
space. In this case, the meaningful information consists of the
intrinsic distances between points along the manifold. In small
neighborhoods, those distances are close to the distances measured in
the enclosing space, but for points which are far away from each other
this is not true any more. In this setting it is not very useful to
perform an isometric embedding of the metric space into a Banach space
as the additional linear structure the Banach space imposes on the
training data might be more misleading than helpful.  Here a different
approach has to be taken, but it is not clear how a large margin
algorithm in this setting can be constructed, or even whether in this
case the large margin paradigm should be applied at all.


%%As a summary we would like to draw the following conclusions: If one
%%accepts the assumption that all the distances between the training
%%points reflect important structure of the training data, the Lipschitz
%%approach is a well controlled framework to perform large margin
%%classification on the metric space.
%%If one believes only in local distances, there might be other
%%approaches which try to encorporate this assumption. Th







%
%
%
%----------------------------------------------------------------------
%\section*{Acknowledgements}
%----------------------------------------------------------------------
\acks{We would like to thank  Matthias Hein and Bernhard Sch\"olkopf for helpful
discussions. }

%
%
%----------------------------------------------------------------------
\appendix
\section{Proof of Theorem \ref{th-refined-dudley}}
%----------------------------------------------------------------------
%
The idea of the proof of Theorem \ref{th-refined-dudley} is the
following.
Instead of bounding the Rademacher complexity on the whole set of
functions $\Fcal$,
we first consider a  maximal
$\eps$-separating subset $\Fcal_{\eps}$ of $\Fcal$. This is a maximal subset such that
all its points have distance at least $\eps$ to each other.
To this special set we will apply the classical entropy bound of
\cite{dudley87}:
%
\begin{theorem}[Classical entropy bound] \label{th-dudley}
For  every class $\Fcal$ of functions there exists a constant $C$ such
that
\begin{gather*}
\hat{R}_n(\Fcal) \leq
%
 \frac{C}{\sqrt{n}}\int_0^{\infty} \sqrt{ \log N(\Fcal, u, L_2(\mu_n))} \; du
\end{gather*}
where $\mu_n$ is the empirical distribution of the sample.
\end{theorem}

As a second step we then
bound the error we make by computing the Rademacher complexity of
$\Fcal_{\eps}$ instead of $\Fcal$. This will lead to the additional offset of
$2\eps$ in  Theorem \ref{th-refined-dudley}.
%
The following lemma can be found as Lemma 3.10 in
\cite{thesis_olivierb} (for the definition of a separable process see
also \citealt{VaaWel96}). 
\begin{lemma}[$\boldsymbol{\eps}$-separations of an empirical process] \label{lemma-olivier}
Let $\{Z_t; t \in T\}$ be a separable stochastic process satisfying
for $\lambda > 0$ the increment condition
%
$$ \forall s, t \in T: E\big( e^{\lambda(Z_t -Z_s)}\big) \leq
e^{\lambda^2c^2d^2(s,t)/2}.$$
%
Let $\eps \geq 0$ and $\delta > 0$. If
$\eps >0$, let $T_{\eps}$ denote a maximal $\eps$-separated subset of
$T$ and let $T_{\eps} = T$ otherwise. Then for all $t_0$,
$$ E \left( \sup_{t\in T_{\eps}, d(t,t_0)\leq \delta}  Z_t - Z_{t_0} \right)
  \leq 4\sqrt{2}c \int_{\eps/4}^{\delta/2}
  \sqrt{ \log N(T,u,d)} du .
$$
\end{lemma}

To apply this lemma to the Rademacher complexity of a function
class $\Fcal$, we choose the index set $T = \Fcal$, the
fixed index $t_0 = f_0$ for some $f_0 \in \Fcal$, the empirical
process $Z_f = \frac{1}{n} \sum \sigma_i f(X_i)$, and $\delta \to
\infty$. Note that the Rademacher complexity satisfies the increment
condition of Lemma \ref{lemma-olivier}
with respect to the $L_2(\mu_n)$--distance
with constant $c = \sqrt{n}$. Moreover, observe that 
$E(\sup_t Z_t - Z_{t_0}) = E(\sup_t Z_t) - E(Z_{t_0})$ and 
$E(Z_{t_0}) = E(\frac{1}{n}\sum \sigma_i f_0(X_i) ) = 0$. 
Together with the symmetry of the distribution of $Z_f$ we thus get the next lemma:
%
%----------------------------------------
%
\begin{lemma}[Entropy bound for $\boldsymbol\eps$-separations]
  \label{lemma-entropy-eps}
Let $(X_i)_{i=1 , \hdots , n}$ be iid training points with empirical
distribution $\mu_n$, $\Fcal$  an arbitrary class of functions, and
$\Fcal_{\eps}$ a maximal $\eps$-separating subset of
$\Fcal$ with respect to
$L_2(\mu_n)$- norm. Then
%
$$ E \left( \sup_{f \in \Fcal_{\eps}}
\frac{1}{n} | \sum_i \sigma_i f(X_i) |
\Big | X_1,  \hdots , X_n
\right)
\leq \frac{4\sqrt{2}}{\sqrt{n}} \int_{\eps/4}^{\infty} \sqrt{ \log
  N(\Fcal,u, L_2(\mu_n))}\;\; du .
$$
\end{lemma}

With this lemma we achieved that the integral over the covering
numbers starts at $\eps/4$
instead of 0 as it is the case in Theorem \ref{th-dudley}.
The price we pay is that  the supremum on the left hand side is taken over
the smaller set
$\Fcal_{\eps}$  instead of the whole class $\Fcal$. Our next step is
to bound the mistake we make by this procedure.
%
\begin{lemma}\label{lemma-diff-f-feps} Let $\Fcal$ be a class of
  functions and $\Fcal_{\eps}$ a maximal $\eps$-separating subset of
  $\Fcal$ with respect to  $\norm_{L_2(\mu_n)}$. Then
$ |  R_n(\Fcal) - R_n(\Fcal_{\eps}) |  \leq 2\eps.$
\end{lemma}
%
\begin{proof}
We want to bound the expression
$$ {|  R_n(\Fcal) - R_n(\Fcal_{\eps}) | }
%
= E  \frac{1}{n} { \left| \sup_{f \in \Fcal}|\sum \sigma_i f(X_i) | -
 \sup_{f \in \Fcal_{\eps}}|\sum \sigma_i f(X_i) |  \right|}.$$
%
First look at the expression inside the expectation, assume that
the $\sigma_i$ and $X_i$ are fixed and that
$\sup_{f \in \Fcal}|\sum \sigma_i f(x_i) | = |\sum \sigma_i
f^*(x_i)|$ for some function $f^*$ (if $f^*$ does not  exist
we additionally have to use a limit argument).
Let $f_{\eps} \in \Fcal_{\eps}$ such that
$\|f^*-f_{\eps}\|_{L_2(\mu_n)} \leq 2\eps$.
Then,
\begin{gather*}
\frac{1}{n}\left| \sup_{f \in \Fcal}|\sum \sigma_i f(x_i) | -
 \sup_{f \in \Fcal_{\eps}}|\sum \sigma_i f(x_i) |  \right|
\leq
\frac{1}{n} \left| |\sum \sigma_i f^*(x_i)| - |\sum \sigma_i f_{\eps}(x_i)|
\right|  \\
%
\leq \frac{1}{n} \left | \sum \sigma_i (f^*(x_i) - f_{\eps}(x_i) ) \right  |
%
%\leq \frac{1}{n} \sum \norminf[f^* - f_{\eps}]
\leq \norm[f^* - f_{\eps}]_{L_1(\mu_n)}
\leq \norm[f^* - f_{\eps}]_{L_2(\mu_n)}
\leq 2\eps.
\end{gather*}
%
As this holds conditioned on all fixed values of $\sigma_i$ and $X_i$ we get the
same for the expectation. This proves the lemma.
\end{proof}

To prove Theorem \ref{th-refined-dudley} we now combine lemmas
\ref{lemma-entropy-eps} and \ref{lemma-diff-f-feps}.

%
%
%
%
%
%\bibliography{merged_bib_ule}
%
%

\begin{thebibliography}{20}
\expandafter\ifx\csname natexlab\endcsname\relax\def\natexlab#1{#1}\fi
\expandafter\ifx\csname url\endcsname\relax
  \def\url#1{{\tt #1}}\fi

\bibitem[Arens and Eells(1956)]{AreEel56}
R.~Arens and J.~Eells.
\newblock On embedding uniform and topological spaces.
\newblock {\em Pacific Journal of Mathematics}, 6:\penalty0 397--403, 1956.

\bibitem[Bartlett and Mendelson(2002)]{BarMen02}
P.~Bartlett and S.~Mendelson.
\newblock Rademacher and {G}aussian complexities: Risk bounds and structural
  results.
\newblock {\em Journal of Machine Learning Research}, 3:\penalty0 463--482, 2002.

\bibitem[Bennett and Bredensteiner(2000)]{BenBre00}
K.~Bennett and E.~Bredensteiner.
\newblock Duality and geometry in {SVM} classifiers.
\newblock In P.~Langley, editor, {\em Proceedings of the Seventeenth
  International Conference on Machine Learning}, pages 57--64. Morgan Kaufmann,
  San Francisco, 2000.

\bibitem[Bousquet(2002)]{thesis_olivierb}
O.~Bousquet.
\newblock {\em Concentration Inequalities and Empirical Processes Theory
  Applied to the Analysis of Learning Algorithms}.
\newblock PhD thesis, Ecole Polytechnique, 2002.

\bibitem[Devroye and Lugosi(2001)]{DevLug01}
L.~Devroye and G.~Lugosi.
\newblock {\em Combinatorial Methods in Density Estimation}.
\newblock Springer, New York, 2001.

\bibitem[Dobric and Yukich(1995)]{Yukich95}
V.~Dobric and J.~Yukich.
\newblock Asymptotics for transportation costs in high dimensions.
\newblock {\em Journal of Theoretical Probability}, 8\penalty0 (1):\penalty0 97--118, 1995.

\bibitem[Dudley(1987)]{dudley87}
R.~M. Dudley.
\newblock Universal {D}onsker classes and metric entropy.
\newblock {\em Annals of Probability}, 15\penalty0 (4):\penalty0 1306--1326, 1987.

\bibitem[Graepel et~al.(1999)Graepel, Herbrich, Sch{\"o}lkopf, Smola, Bartlett,
  M{\"u}ller, Obermayer, and Williamson]{GraHerEtal99a}
T.~Graepel, R.~Herbrich, B.~Sch{\"o}lkopf, A.~Smola, P.~Bartlett,
  K.~M{\"u}ller, K.~Obermayer, and R.~Williamson.
\newblock Classification of proximity data with {LP} machines.
\newblock In {\em Proceedings of the Ninth International Conference on
  Artificial Neural Networks}, pages 304--309, 1999.

\bibitem[Hein and Bousquet(2003)]{HeiBou03}
M.~Hein and O.~Bousquet.
\newblock Maximal margin classification for metric spaces.
\newblock In M.~Warmuth B.~Sch{\"o}lkopf, editor, {\em Proceedings of
  the 16th Annual Conference on Computational Learning Theory}, pages 72--86. Springer
  Verlag, Heidelberg, 2003.

\bibitem[Kolmogorov and Tihomirov(1961)]{KolTih61}
A.~N. Kolmogorov and V.~M. Tihomirov.
\newblock {$\varepsilon $}-entropy and {$\varepsilon $}-capacity of sets in
  functional space.
\newblock {\em American Mathematical Society Translations (2)}, 17:\penalty0 277--364, 1961.

\bibitem[Megginson(1998)]{Megginson98}
R.~Megginson.
\newblock {\em An Introduction to {Banach} Space Theory}.
\newblock Springer, New York, 1998.

\bibitem[Mendelson and Vershynin(2003)]{MenVer03}
S.~Mendelson and R.~Vershynin.
\newblock Entropy and the combinatorial dimension.
\newblock {\em Inventiones Mathematicae}, 152\penalty0 (1):\penalty0 37--55,
  2003.

\bibitem[Pestov(1986)]{Pestov86}
V.~Pestov.
\newblock Free {Banach} spaces and representations of topological groups.
\newblock {\em Functional Analysis and Its Applications}, 20:\penalty0 70--72, 1986.

\bibitem[Rudin(1991)]{Rudin91}
W.~Rudin.
\newblock {\em Functional Analysis}.
\newblock McGraw-Hill Inc., Singapore, 2nd edition, 1991.

\bibitem[Sch{\"o}lkopf and Smola(2002)]{SchSmo02}
B.~Sch{\"o}lkopf and A.~Smola.
\newblock {\em Learning with Kernels}.
\newblock MIT Press, Cambridge, MA, 2002.

\bibitem[Steele(1997)]{Steele97}
J.~M. Steele.
\newblock {\em Probability theory and combinatorial optimization}, volume~69 of
  {\em CBMS-NSF Regional Conference Series in Applied Mathematics}.
\newblock Society for Industrial and Applied Mathematics (SIAM), Philadelphia,
  PA, 1997.

\bibitem[Talagrand(1992)]{Talagrand91}
M.~Talagrand.
\newblock The {A}jtai-{K}oml\'os-{T}usn\'ady matching theorem for general
  measures.
\newblock In {\em Probability in Banach spaces, 8 (Brunswick, ME, 1991)},
  volume~30 of {\em Progress in Probability}, pages 39--54. Birkh\"auser Boston,
  MA, 1992.

\bibitem[van~der Vaart and Wellner(1996)]{VaaWel96}
A.~W. van~der Vaart and J.~A. Wellner.
\newblock {\em Weak Convergence and Empirical Processes}.
\newblock Springer, New York, 1996.

\bibitem[Weaver(1999)]{Weaver99}
N.~Weaver.
\newblock {\em Lipschitz algebras}.
\newblock World Scientific, Singapore, 1999.

\bibitem[Zhou et~al.(2002)Zhou, Xiao, Zhou, and Dai]{ZhoXiaZhoDai02}
D.~Zhou, B.~Xiao, H.~Zhou, and R.~Dai.
\newblock Global geometry of {SVM} classifiers.
\newblock Technical Report 30-5-02, Institute of Automation, Chinese Academy of
  Sciences, 2002.

\end{thebibliography}


\end{document}
