\documentclass[twoside,11pt]{article}

% Any additional packages needed should be included after jmlr2e.
% Note that jmlr2e.sty includes epsfig, amssymb, natbib and graphicx,
% and defines many common macros, such as 'proof' and 'example'.
%
% It also sets the bibliographystyle to plainnat; for more information on
% natbib citation styles, see the natbib documentation, a copy of which
% is archived at http://www.jmlr.org/format/natbib.pdf

\usepackage{jmlr2e}

% Definitions of handy macros can go here

\newtheorem{problem}[theorem]{Problem}

\def\bbbr{{\mathbb R}} %reelle Zahlen
\def\bbbn{{\mathbb N}} %natuerliche Zahlen

%%%%%%   Greek Letters   %%%%%%
\def\ga{\alpha}
\def\gA{{\rm A}}
\def\gb{\beta}
\def\gB{{\rm B}}
\def\gga{\gamma}
\def\gG{\Gamma}
\def\gd{\delta}
\def\gD{\Delta}
\def\gep{\varepsilon}
\def\gz{\zeta}
\def\gZ{{\rm Z}}
\def\gth{\theta}
\def\gTh{\Theta}
\def\gf{\varphi}
\def\gF{\Phi}
\def\gy{\upsilon}
\def\gk{\kappa}
\def\gl{\lambda}
\def\gL{\Lambda}
\def\gs{\sigma}
\def\gS{\Sigma}
\def\gt{\tau}
\def\gT{{\rm T}}
\def\gr{\varrho}
\def\go{\omega}
\def\gO{\Omega}

%%%%%%   Symbols   %%%%%%
\def\NN{\bbbn}
\def\ZZ{\bbbz}
\def\RR{\bbbr}
\def\CC{\bbbc}

%%%% end of Fonts %%%%

\newcommand{\dataset}{{\cal D}}
\newcommand{\fracpartial}[2]{\frac{\partial #1}{\partial  #2}}


% Heading arguments are {volume}{year}{pages}{submitted}{published}{author-full-names}

\jmlrheading{5}{2004}{1143--1175}{9/03; Revised 4/04}{9/04}{Di-Rong Chen, Qiang Wu,
Yiming Ying, and Ding-Xuan Zhou}

% Short headings should be running head and authors last names

\ShortHeadings{SVM Soft Margin Classifiers}{Chen, Wu, Ying, and Zhou}
\firstpageno{1143}

\begin{document}

\title{Support Vector Machine Soft Margin Classifiers: Error Analysis}

\author{\name Di-Rong Chen \email drchen@buaa.edu.cn \\
       \addr Department of Applied Mathematics \\
     Beijing University of Aeronautics and Astronautics \\
      Beijing 100083, P. R. CHINA
       \AND
       \name Qiang Wu \email wu.qiang@student.cityu.edu.hk \\
       \name Yiming Ying \email ymying@cityu.edu.hk \\
       \name Ding-Xuan Zhou \email mazhou@math.cityu.edu.hk \\
       \addr Department of Mathematics \\
        City University of Hong Kong \\
        Kowloon, Hong Kong, P. R. CHINA}


\editor{Peter Bartlett}

\maketitle

\begin{abstract}%   <- trailing '%' for backward compatibility of .sty file
The purpose of this paper is to provide a PAC error analysis for
the $q$-norm soft margin classifier, a support vector machine
classification algorithm. It consists of two parts:
regularization error and sample error. While many techniques
are available for treating the sample error, much less is known
for the regularization error and the corresponding
approximation error for reproducing
kernel Hilbert spaces. We are mainly concerned about the
regularization error. It is estimated for general distributions
by a $K$-functional in weighted $L^q$ spaces. For weakly
separable distributions (i.e., the margin may be zero)
satisfactory convergence rates are provided by means of separating functions.
A projection operator is introduced, which leads to
better sample error estimates especially for small complexity kernels.
The misclassification error is bounded
by the $V$-risk associated with a general class of
loss functions $V$. The difficulty of bounding the offset is overcome.
Polynomial kernels and Gaussian kernels are used to
demonstrate the main results.
The choice of the regularization parameter
plays an important role in our analysis.
\end{abstract}

\begin{keywords}
  support vector machine classification,
misclassification error, $q$-norm soft margin classifier, regularization error,
approximation error
\end{keywords}

\section{Introduction}

In this paper we study support vector machine (SVM) classification
algorithms and investigate the SVM $q$-norm soft margin classifier
with $1 < q <\infty$. Our purpose is to provide an error analysis
for this algorithm in the PAC framework.

Let $(X, d)$ be a compact metric space and $Y=\{1, -1\}$. A binary
classifier $f: X \to \{1, -1\}$ is a function from $X$ to $Y$
which divides the input space $X$ into two classes.

Let $\rho$ be a probability distribution on $Z:=X\times Y$ and
$({\cal X}, {\cal Y})$ be the corresponding random variable. The
{\it misclassification error} for a classifier $f: X \to Y$ is
defined to be the probability
of the event $\{f({\cal X})\not= {\cal Y}\}$:
\begin{equation}\label{miserror}
 {\cal R}(f):= \hbox{\rm Prob}\left\{f({\cal X})\not= {\cal Y}\right\}
=\int_X P({\cal Y}\not= f(x)|x) d \rho_X (x).
\end{equation}
Here
$\rho_X$ is the marginal distribution on $X$ and $P (\cdot|x)$ is
the conditional probability measure given ${\cal X} =x$.

The SVM $q$-norm soft margin classifier (Cortes and Vapnik, 1995; Vapnik, 1998) is
constructed from samples and depends on a
reproducing kernel Hilbert space associated with a Mercer kernel.

Let $K: X\times X \to \RR$ be continuous, symmetric and
positive semidefinite, i.e., for
any finite set of distinct points $\{x_1, \cdots, x_\ell\}\subset X$, the matrix
$(K(x_i, x_j))_{i, j=1}^\ell$ is positive semidefinite. Such a kernel is called
a {\it Mercer kernel}.

The {\it Reproducing Kernel Hilbert Space} (RKHS) ${\cal H}_{K}$ associated
with the kernel $K$ is defined (Aronszajn, 1950) to be the closure of the linear
span of the set of functions $\{K_x:= K(x, \cdot): \,
x\in X\}$ with the inner product $\langle \cdot, \cdot\rangle_{{\cal H}_K} =
\langle\cdot, \cdot\rangle_{K}$ satisfying $\langle K_x, K_y\rangle_K = K(x, y)$ and
$$ \langle K_x, g\rangle_{K} = g(x), \qquad \forall x\in X, g\in {\cal H}_K. $$
Denote $C(X)$ as the space of continuous functions on $X$ with the
norm $\|\cdot\|_\infty$. Let $\kappa:=\sqrt{\|K\|_{\infty}}$. Then
the above reproducing property tells us that
\begin{equation}\label{repro}
\|g\|_{\infty} \le \kappa\|g\|_K, \qquad \forall g\in {\cal H}_K.
\end{equation}

Define $\overline{{\cal H}}_K :={\cal H}_K +\RR$. For a function
$f = f_1 +b$ with $f_1 \in {\cal H}_K$ and $b\in\RR$, we denote
$f^* =f_1$ and $b_f =b\in\RR$. The constant term $b$ is called
the 
{\it offset}. For a function $f: X\to \RR$, the sign function is
defined as $\hbox{sgn}(f)(x)=1$ if $f(x)\ge 0$ and
$\hbox{sgn}(f)(x)=-1$ if $f(x)< 0$.

Now the {\it SVM $q$-norm soft margin classifier} (SVM $q$-classifier)
associated with the Mercer kernel $K$ is defined as
sgn$\, (f_{\bf z})$, where $f_{\bf z}$ is a minimizer of the
following optimization problem involving a set of random samples
${\bf z}=(x_i, y_i)_{i=1}^m \in Z^m$ independently drawn according
to $\rho$:
\begin{equation}\label{svmone}
\begin{array}{ll} &f_{\bf z} := \displaystyle\arg\min_{f\in \overline{{\cal H}}_K}
\quad {1 \over 2} \|f^*\|_K^2 +
{C \over m} \sum_{i=1}^m \xi_i^q, \\ & \qquad \hbox{ subject to} \quad y_i
f(x_i) \ge 1 - \xi_i, \hbox{ and }  \xi_i \ge 0 \hbox{ for } i=1,
\ldots, m. \end{array}
\end{equation}
Here $C$ is a constant which
depends on $m$: $C= C(m)$, and often $\lim\limits_{m\to\infty}
C(m)=\infty$.

Throughout the paper, we assume $1<q<\infty$, $m\in \NN$, $C>0$,
and ${\bf
z}=(x_i,y_i)_{i=1}^m$ are random samples independently drawn
according to $\rho.$ Our target is to understand how
$\hbox{sgn}(f_{\bf z})$ converges (with respect to the
misclassification error) to the best classifier, the Bayes rule,
as $m$ and hence $C(m)$ tend to infinity.
Recall the regression function of $\rho$:
\begin{equation}\label{regre}
f_\rho (x) = \int_Y y d \rho(y|x)=P({\cal Y}=1|x) - P({\cal Y}=-1|x),
\qquad x\in X.
\end{equation}
Then the {\it Bayes rule} is given
(e.g. Devroye, L. Gy\"orfi and G. Lugosi, 1997) by the sign of
the regression function $f_c:= \hbox{sgn}(f_\rho)$. Estimating the
excess misclassification error
\begin{equation}\label{misclasserror}
{\cal R}(\hbox{sgn}(f_{\bf z})) - {\cal R}(f_c)
\end{equation}
for the classification algorithm (\ref{svmone}) is our goal. In
particular, we try to understand how the choice of the
regularization parameter $C$ affects the error.

To investigate the error bounds for general kernels, we rewrite (\ref{svmone})
as a regularization scheme. Define the loss function $V=V_q$ as
\begin{equation}\label{loss}
 V(y, f(x)): =(1 - y f(x))^q_+ =|y - f(x)|^q \chi_{\{y f(x) \le 1\}},
\end{equation}
where $(t)_+ =\max\{0, t\}$. The corresponding {\it $V$-risk} is
\begin{equation}\label{error}
 {\cal E}(f):=E\bigl(V(y, f(x))\bigr)=\int_Z V(y, f(x)) d \rho (x, y).
\end{equation}

If we set the empirical error as
\begin{equation}\label{emerror}
{\cal E}_{{\bf z}}(f):={1 \over m} \sum_{i=1}^m V(y_i, f(x_i))
={1 \over m} \sum_{i=1}^m \left(1 - y_i f(x_i)\right)^q_+,
\end{equation}
then the scheme (\ref{svmone}) can be written as (see
Evgeniou, Pontil and Poggio, 2000)
\begin{equation}\label{svmtwo}
f_{\bf z} =\arg \min_{f\in \overline{{\cal H}}_K}
\left\{{\cal E}_{{\bf z}}(f) + {1 \over 2 C} \|f^*\|_K^2\right\}.
\end{equation}

Notice that when $\overline{{\cal H}}_K$ is replaced by ${\cal H}_K$,
the scheme (\ref{svmtwo}) is exactly the Tikhonov
regularization scheme (Tikhonov and Arsenin, 1977) associated with
the loss function $V$. So one may hope that the method for analyzing
regularization schemes can be applied.

The definitions of the $V$-risk (\ref{error}) and the
empirical error (\ref{emerror}) tell us that for a function $f=f^* + b
\in \overline{{\cal H}}_K$, the random variable $\xi = V(y, f(x))$
on $Z$ has the mean ${\cal E}(f)$ and ${1 \over m} \sum_{i=1}^m
\xi (z_i) = {\cal E}_{\bf z} (f)$. Thus we may expect by some
standard empirical risk minimization (ERM) argument
(e.g. Cucker and Smale, 2001;
Evgeniou, Pontil and Poggio, 2000; Shawe-Taylor et al., 1998;
Vapnik, 1998; Wahba, 1990) to derive bounds for
${\cal E}(f_{\bf
z}) - {\cal E}(f_q)$, where $f_q$ is a minimizer of the
$V$-risk (\ref{error}). It was shown in Lin (2002) that for
$q>1$ such a minimizer is given by
\begin{equation}\label{regV}
 f_q (x) ={(1 + f_\rho (x))^{1/(q-1)} - (1 - f_\rho (x))^{1/(q-1)} \over
(1 + f_\rho (x))^{1/(q-1)} + (1 - f_\rho (x))^{1/(q-1)}}, \qquad x\in X.
\end{equation}
For $q=1$ a minimizer is $f_c$, see Wahba (1999).
Note that $\hbox{sgn}(f_q) = f_c$.

Recall that for the classification algorithm (\ref{svmone}), we
are interested in the excess misclassification error
(\ref{misclasserror}), not the excess $V$-risk 
${\cal
E}(f_{\bf z}) - {\cal E}(f_q)$. But we shall see in Section 3 that
${\cal R}(\hbox{sgn}(f)) - {\cal R}(f_c)\le\sqrt{2 \left({\cal
E}(f) - {\cal E}(f_q)\right)}$. One might apply this to the
function $f_{\bf z}$ and get estimates for (\ref{misclasserror}).
However, special features of the loss function (\ref{loss}) enable
us to do better: by restricting $f_{\bf z}$ onto $[-1,1]$, we can
improve the sample error estimates.
The idea of the following projection operator was introduced
for this purpose
in Bartlett (1998).

\begin{definition}
 The {\rm projection operator} $\pi$ is
defined on the space of measurable functions $f: X \to \RR$ as
\begin{equation}\label{projectionop}
 \pi (f)(x)=\left\{\begin{array}{ll} 1, & \hbox{ if } f(x) \ge 1, \\
-1, & \hbox{ if } f (x) \le -1, \\
f(x), & \hbox{ if } -1 < f (x) < 1. \end{array}\right.
\end{equation}
\end{definition}

It is trivial that sgn$(\pi (f))= \hbox{sgn}(f)$. Hence
\begin{equation}\label{misbound}
{\cal R}(\hbox{sgn}(f_{\bf z})) - {\cal R}(f_c) \le
\sqrt{2 \left({\cal E}(\pi (f_{\bf z})) - {\cal E}(f_q)\right)}.
\end{equation}
The definition
of the loss function (\ref{loss}) also tells us that
$V(y, \pi(f) (x))
\le V(y, f (x))$, so
\begin{equation}\label{projest}
{\cal E}(\pi (f)) \le {\cal E}(f) \qquad \hbox{and} \qquad
{\cal E}_{\bf z} (\pi (f)) \le {\cal E}_{\bf z}(f).
\end{equation}

According to (\ref{misbound}), we need to estimate ${\cal E}(\pi
(f_{\bf z})) - {\cal E}(f_q)$ in order to bound (\ref{misclasserror}).
To this end, we introduce a {\it regularizing function} $f_{K,
C}\in \overline{{\cal H}}_K$. It is arbitrarily chosen and depends
on $C$.

\begin{proposition}\label{prop1.1}
Let $f_{K,
C}\in \overline{{\cal H}}_K$,
and $f_{\bf z}$ be defined by (\ref{svmtwo}).
Then ${\cal E}(\pi
(f_{\bf z})) - {\cal E}(f_q)$ can be bounded by
\begin{equation}\label{decomerror}
\biggl\{ {\cal E} (f_{K, C}) -  {\cal E}(f_q) + {1 \over 2 C}
\|f_{K, C}^*\|_K^2\biggr\} +
\biggl\{{\cal E}(\pi (f_{\bf z})) -
{\cal E}_{\bf z} (\pi (f_{\bf z}))  +
 {\cal E}_{\bf z} (f_{K, C}) - {\cal E} (f_{K, C})\biggr\}.
\end{equation}
\end{proposition}

\begin{proof}
 Decompose the difference ${\cal E}(\pi
(f_{\bf z})) - {\cal E}(f_q)$ as
\begin{eqnarray*}
&\displaystyle \Big\{{\cal E}(\pi (f_{\bf z})) - {\cal E}_{\bf z}
(\pi (f_{\bf z}))\Big\} + \left\{\left({\cal E}_{\bf z} (\pi
(f_{\bf z})) + {1 \over 2 C} \|f_{\bf z}^*\|_K^2\right) -
\left({\cal E}_{\bf z} (f_{K, C})
 + {1 \over 2 C} \|f_{K, C}^*\|_K^2 \right)\right\} \\
&\displaystyle \qquad + \Big\{{\cal E}_{\bf z} (f_{K, C}) - {\cal
E} (f_{K, C})\Big\} + \left\{ {\cal E} (f_{K, C}) -  {\cal E}(f_q)
+ {1 \over 2 C} \|f_{K, C}^*\|_K^2\right\} - {1 \over 2 C}
\|f_{\bf z}^*\|_K^2.
\end{eqnarray*}
 By the definition of $f_{\bf z}$ and
(\ref{projest}), the second term is $\le 0$. Then the statement follows.
\end{proof}

The first term in (\ref{decomerror}) is called the regularization
error (Smale and Zhou, 2004). It can be expressed as a generalized
$K$-functional $\inf\limits_{f\in \overline{{\cal H}}_K}
\left\{{\cal E} (f) - {\cal E}(f_q) + {1 \over 2 C}
\|f^*\|_K^2\right\}$ when $f_{K, C}$ takes a special choice
$\widetilde{f}_{K, C}$ (a standard choice in the literature, e.g.
Steinwart 2001) defined as
\begin{equation}\widetilde{f}_{K,
C}:=\arg \min_{f\in \overline{{\cal H}}_K} \left\{{\cal E} (f) +
{1 \over 2 C} \|f^*\|_K^2 \right\}. \label{targetf}
\end{equation}

\begin{definition}\label{defn1.2}
Let $V$ be a general loss function
and $f_\rho^V$ be a minimizer of the $V$-risk 
(\ref{error}). The {\rm regularization error} for the regularizing
function $f_{K, C}\in \overline{{\cal H}}_K$ is defined as
\begin{equation}
{\cal D}(C) := {\cal E} (f_{K, C}) - {\cal E}(f_\rho^V) +
{1 \over 2 C} \|f_{K, C}^*\|_K^2. \label{regerror}
\end{equation}
It is called the {\rm regularization error of the scheme}
(\ref{svmtwo}) when $f_{K, C} = \widetilde{f}_{K, C}$:
$$ \widetilde{{\cal D}} (C):=
\inf_{f\in \overline{{\cal H}}_K} \left\{{\cal E} (f) - {\cal
E}(f_\rho^V) + {1 \over 2 C} \|f^*\|_K^2\right\}. $$
\end{definition}

The main concern of this paper is the regularization error. We
shall investigate its asymptotic behavior. This investigation is
not only important for bounding the first term in
(\ref{decomerror}), but also crucial for bounding the second term
(sample error): it is well known in structural risk minimization
(Shawe-Taylor et al., 1998) that the size of the hypothesis space
is essential. This is determined by ${\cal D}(C)$ in our setting. 
Once $C$ is fixed, the sample error
estimate becomes routine. Therefore, we need to understand the
choice of the parameter $C$ from the bound for ${\cal D}(C)$.

\begin{proposition}\label{prop1.2}
For any $C \ge 1/2 $ and any $f_{K,
C} \in \overline{{\cal H}}_K$, there holds
\begin{equation}
{\cal
D}(C)\ge \widetilde{\cal D} (C) \ge {\widetilde\kappa^2 \over 2 C}
\label{lowerD}
\end{equation} where
\begin{equation}
\widetilde\kappa := {\cal E}_0/(1 +\kappa q 4^{q-1} ), \qquad
{\cal E}_0 := \inf_{b\in\RR} \bigl\{{\cal E}(b) - {\cal
E}(f_q)\bigr\}. \label{kappatilde}
\end{equation}
Moreover,
$\widetilde\kappa =0$ if and only if for some $p_0 \in [0, 1]$,
$P({\cal Y}=1|x) = p_0$ in probability.
\end{proposition}

This proposition will be proved in Section 5.

According to Proposition \ref{prop1.2}, the decay of ${\cal D}(C)$
cannot be faster than $O(1/C)$ except for some very special
distributions. This special case is caused by the offset in
(\ref{svmtwo}), for which $\widetilde{\cal D} (C) \equiv 0$.
Throughout this paper we shall ignore this trivial case and assume
$\widetilde\kappa >0$.

When $\rho$ is strictly separable, ${\cal D}(C) = O(1/C)$. But
this is a very special phenomenon. In general, one should not
expect ${\cal E} (f)= {\cal E}(f_q)$ for some $f\in
\overline{{\cal H}}_K$. Even for (weakly) separable distributions
with zero margin, ${\cal D}(C)$ decays as $O(C^{-p})$ for some
$0<p<1$. To realize such a decay for these separable
distributions, the regularizing function will be multiples of a
separating function. For details and the concepts of 
strictly or weakly separable distributions, see Section 2.

For general distributions, we shall choose $f_{K, C} =
\widetilde{f}_{K, C}$ in Sections 6 and 7 and estimate the
regularization error of the scheme (\ref{svmtwo}) associated with
the loss function (\ref{loss}) by means of the approximation in
the function space $L^q_{\rho_X}$. In particular,
$\widetilde{{\cal D}}(C) \le {\cal K}(f_q, {1 \over 2 C})$, where
${\cal K}(f_q, t)$ is a $K$-functional defined as
\begin{equation}
{\cal K}(f_q, t):= \left\{ \begin{array}{ll} \inf\limits_{f\in
\overline{{\cal H}}_K} \left\{\|f-f_q \|_{L^q_{\rho_X}}^q + t
\|f^*\|_K^2 \right\}, & \hbox{ if } 1 < q \le 2, \\
\inf\limits_{f\in \overline{{\cal H}}_K} \left\{q 2^{q-1} (2^{q-1}
+ 1) \|f-f_q \|_{L^q_{\rho_X}} + t \|f^*\|_K^2 \right\}, & \hbox{
if } q>2. \end{array}\right. \label{Kfunctional}
\end{equation}

In the case $q=1$, the regularization error (Wu and Zhou, 2004)
depends on the approximation in $L^1_{\rho_X}$ of the function
$f_c$ which is not continuous in general. For $q>1$, the
regularization error depends on the approximation in
$L^q_{\rho_X}$ of the function $f_q$. When the regression function
has good smoothness, $f_q$ has much higher regularity than $f_c$.
Hence the convergence for $q>1$ may be faster than that for $q=1$,
which improves the regularization error.

The second term in (\ref{decomerror}) is called the {\it sample
error}. When $C$ is fixed, the sample error
${\cal E}(f_{\bf
z})-{\cal E}_{\bf z}(f_{\bf z})$
is well understood (except for
the offset term).
In (\ref{decomerror}), the sample error is for
the function $\pi(f_{\bf z})$ instead of $f_{\bf z}$ while the
misclassification error (\ref{misclasserror}) is kept: ${\cal
R}\bigl(\hbox{sgn}(\pi(f_{\bf z}))\bigr) ={\cal
R}(\hbox{sgn}(f_{\bf z}))$. Since the bound 
for $V(y, \pi (f)(x))$ is much smaller than that for 
$V(y, f(x))$, the projection improves the sample error estimate. 

Based on estimates for the regularization error and sample error
above, our error analysis will provide $\gep(\gd, m, C, \gb)>0$
for any $0<\gd <1$ such that with confidence $1-\gd$,
\begin{equation}
{\cal E}(\pi (f_{\bf z})) - {\cal E}(f_q) \le (1 + \gb)
\bigl\{ {\cal D}(C) + \gep (\gd, m, C, \gb) \bigr\}.
\label{restateThm}
\end{equation}
Here $0<\beta\le 1$ is an
arbitrarily fixed number. Moreover, $\lim\limits_{m\to\infty} \gep
(\gd, m, C, \gb) =0$.

If $f_q$ lies in the $L^q_{\rho_X}$-closure of $\overline{{\cal
H}}_K$, then $\lim\limits_{t\to 0}{\cal K}(f_q, t) =0$ by
(\ref{Kfunctional}). Hence ${\cal E}(\pi(f_{\bf z})) - {\cal
E}(f_q) \to 0$ with confidence as $m$ (and hence $C=C(m)$) becomes
large. This is the case when $K$ is a universal kernel, i.e.,
${\cal H}_K$ is dense in $C(X)$, or when a sequence of kernels
whose RKHS tends to be dense (e.g. polynomial kernels with
increasing degrees) is used.

In summary, estimating the excess misclassification error ${\cal
R}(\hbox{sgn}(f_{\bf z})) - {\cal R}(f_c)$ consists of three
parts: the comparison (\ref{misbound}), the regularization error
${\cal D}(C)$ and the sample error $\gep (\gd, m, C, \gb)$ in
(\ref{restateThm}). As functions of the variable $C$, ${\cal
D}(C)$ decreases while $\gep (\gd, m, C, \gb)$ usually increases.
Choosing suitable values for the regularization parameter $C$ will
give the optimal convergence rate. To this end, we need to
consider the tradeoff between these two errors. This can be done
by minimizing the right side of (\ref{restateThm}), as shown in
the following form.

\begin{lemma}\label{lem1.1}
Let $p, \ga, \tau >0$. Denote $c_{p, \ga,
\tau}:= \bigl(p/\tau\bigr)^{{\tau \over \tau +p}} +
\bigl(\tau/p\bigr)^{{p \over \tau +p}}$. Then for any $C>0$,
\begin{equation} C^{-p} +{C^\tau \over m^\ga} \ge c_{p, \ga, \tau}
\biggl({1 \over m}\biggr)^{{\ga p \over \tau +p}}.
\label{tradeoff}
\end{equation}
The equality holds if and only if
$C=\bigl(p/\tau\bigr)^{{1 \over \tau +p}} m^{{\ga \over \tau
+p}}$. This yields the optimal power ${\ga p \over \tau +p}$.
\end{lemma}

The goal of the regularization error estimates is to have $p$ in
${\cal D}(C) =O(C^{-p})$, as large as possible. But $p\le 1$
according to Proposition \ref{prop1.2}. Good methods for sample
error estimates provide large $\ga$ and small $\tau$ such that
$\gep (\gd, m, C, \gb) =O({C^\tau \over m^\ga})$. Notice that,
as always, both the approximation properties
(represented by the exponent $p$) and the estimation properties
(represented by the exponents $\tau$ and $\ga$) are important
to get good estimates for the learning rates (with the optimal rate ${\ga p \over \tau +p}$).

\section{Demonstrating with Weakly Separable Distributions}

With some special cases let us demonstrate how our error
analysis yields some guidelines for choosing the regularization parameter $C.$
For weakly separable distributions, we also compare our results
with bounds in the literature. To this end, we
need the covering number of the unit ball
${\cal B}:=\{f\in {\cal H}_K: \|f\|_K \le 1\}$ of ${\cal H}_K$
(considered as a subset of $C(X)$).

\begin{definition}\label{defn2.1}
For a subset ${\cal F}$ of a metric
space and $\eta>0$, the {\rm covering number} ${\cal N}({\cal F},
\eta)$ is defined to be the minimal integer $\ell\in\NN$ such that
there exist $\ell$ disks with radius $\eta$ covering ${\cal F}$.
\end{definition}

Denote the covering number of ${\cal B}$ in $C(X)$ by ${\cal
N}({\cal B}, \eta)$. Recall the constant $\widetilde{\kappa}$ 
defined in (\ref{kappatilde}). Since the algorithm involves an offset term,
we also need its covering number and set
\begin{equation}{\cal
N}(\eta) := \Bigl\{\bigl(\kappa +{1 \over \widetilde\kappa}\bigr)
{1 \over \eta} +1\Bigr\} {\cal N}({\cal B}, \eta).
\label{defcoveringnumber}
\end{equation}

\begin{definition}\label{defn2.2}
We say that the Mercer kernel $K$
has {\rm logarithmic complexity exponent} $s \ge 1$ if for some $c>0$,
there holds
\begin{equation}
\log  {\cal N}(\eta) \le c
\left(\log(1/\eta)\right)^{s}, \qquad \forall \eta >0.
\label{coveringanal}
\end{equation}
The kernel $K$ has {\rm polynomial
complexity exponent} $s>0$ if
\begin{equation}\log  {\cal N}(\eta)
\le c \left(1/\eta\right)^{s}, \qquad \forall \eta >0.
\label{coveringsob}
\end{equation}
\end{definition}

The covering number ${\cal N}({\cal B}, \eta)$ has been
extensively studied (see e.g. Bartlett, 1998; Williamson, Smola and
Sch\"olkopf, 2001; Zhou, 2002; Zhou, 2003a). In particular, for
convolution type kernels $K(x,y)=k(x-y)$ with $\hat k \geq 0$ 
decaying exponentially fast, (\ref{coveringanal}) holds 
(Zhou,
2002, Theorem 3). As an example,
consider the Gaussian kernel $K(x, y)= \exp\{-|x-y|^2/\gs^2\}$
with $\gs>0.$ If $X\subset [0, 1]^n$ and $0<\eta \le \exp\{90
n^2/\gs^2 - 11n -3\}$, then (\ref{coveringanal}) is valid (Zhou,
2002) with $s=n+1$. A lower bound (Zhou, 2003a) holds with
$s={n\over 2}$, which shows the upper bound is almost sharp. It
was also shown in (Zhou, 2003a) that $K$ has polynomial complexity
exponent $2n/p$ if $K$ is $C^p$.

To demonstrate our main results concerning the regularization
parameter $C$, we shall only choose kernels having
logarithmic complexity exponents or having polynomial
complexity exponents with $s$ small.
This means, $\overline{{\cal H}}_K$ has small complexity.

The special case we consider here is the deterministic case:
${\cal R}(f_c)=0$. Understanding how to find ${\cal D}(C)$ and
$\gep (\gd, m, C, \gb)$ in (\ref{restateThm}) and then how to
choose the parameter $C$ is our target. For $M\ge 0$, denote
\begin{equation}
\theta_M=\left\{\begin{array}{ll}0, & \hbox{ if } M=0, \\
1, & \hbox{ if } M>0.\end{array}\right.
\label{Mtheta}
\end{equation}

\begin{proposition}\label{prop2.1}
Suppose ${\cal R}(f_c) =0$. If
$f_{K, C} \in \overline{{\cal H}}_K$ satisfies $\|V(y, f_{K, C}
(x))\|_\infty \le M$, then for every $0<\gd <1$, with confidence
at least $1-\gd$, we have
\begin{equation}
{\cal
R}(\hbox{sgn}(f_{\bf z})) \le 2 \max\left\{\gep^*, {4 M
\log(2/\gd) \over m}\right\} + 4 {\cal D}(C),
\label{determ}
\end{equation}
where with ${\cal M}:= \sqrt{2 C
{\cal D}(C) + 2 C \gep \theta_M}$, $\gep^*>0$ is the unique
solution to the equation
\begin{equation}
\log {\cal N}
\left({\gep \over q 2^{q +3} {\cal M}}\right) - {3m \gep \over
2^{q +9}} =\log (\delta/2). \label{kernelcov}
\end{equation}
\begin{enumerate}

\item[{\rm (a)}] If (\ref{coveringanal}) is valid, then with
$\widetilde{c}= 2^{q +9} \bigl\{1 + c ((q +4) \log 8)^s\bigr\}$,
$$ \gep^* \le \widetilde{c} \biggl({\bigl(\log m +
\log \bigl(C {\cal D}(C)\bigr) + \log \bigl(C \theta_M\bigr)\bigr)^s
+ \log(2/\gd) \over m}\biggr).  $$

\item[{\rm (b)}] If (\ref{coveringsob}) is valid and $C\ge 1$,
then with a constant $\widetilde{c}$ (given explicitly in the
proof),
\begin{equation}
\gep^* \le \widetilde{c} \log(2/\gd) \biggl\{{\bigl(2 C
{\cal D}(C)\bigr)^{s/(2s +2)} \over m^{1/(s+1)}} + {\bigl(2
C\bigr)^{s/(s +2)} \over m^{1/({s \over 2}+1)}}\biggr\}.
\label{errorsob}
\end{equation}
\end{enumerate}
\end{proposition}

Note that the above constant $\widetilde{c}$ depends on $c, q,$
and $\kappa$, but not on $C$, $m$ or $\gd$. The proof of
Proposition \ref{prop2.1} will be given in Section 5.

We can now derive our error bound for weakly separable distributions.

\begin{definition}\label{defn2.3}
We say that $\rho$ is {\rm (weakly)
separable} by $\overline{{\cal H}}_K$ if there is a function
$f_{\hbox{sp}} \in \overline{{\cal H}}_K$, called a {\rm separating
function}, satisfying $\|f_{\hbox{sp}}^*\|_K =1$ and $y
f_{\hbox{sp}} (x) > 0$ almost everywhere. It has {\rm separation
exponent} $\theta \in (0, +\infty]$ if there are positive
constants $\gga, c'$ such that
\begin{equation}
\rho_X \bigl\{x \in
X: |f_{\hbox{sp}} (x)| < \gga t \bigr\} \le c' t^\theta, \qquad
\forall \ t>0. \label{sepexp}
\end{equation}
\end{definition}

Observe that condition (\ref{sepexp}) with $\theta=+\infty$ is
equivalent to
$$ \rho_X \bigl\{x \in X: |f_{\hbox{sp}} (x)| < \gga t \bigr\} =0,
\qquad \forall \ 0<t<1. $$
That is, $|f_{\hbox{sp}} (x)| \ge \gga$
almost everywhere. Thus, weakly separable distributions with 
separation
exponent $\theta= +\infty$ are exactly strictly separable distributions. 
Recall (e.g. Vapnik,
1998; Shawe-Taylor et al., 1998) that $\rho$ is said to be {\it
strictly separable} by $\overline{{\cal H}}_K$ with margin $\gga
>0$ if $\rho$ is (weakly) separable together with the requirement
$y f_{\hbox{sp}} (x) \ge \gga$ almost everywhere. 

>From the first part of Definition \ref{defn2.3}, we know that for
a separable distribution $\rho$, the set $\{x: f_{\hbox{sp}} (x)
=0\}$ has $\rho_X$-measure zero, hence
$$ \lim_{t \to 0} \rho_X \bigl\{x \in X: |f_{\hbox{sp}} (x)| <t \bigr\} =0. $$
The separation exponent $\theta$ measures the asymptotic behavior
of $\rho$ near the boundary of two classes.
It gives the convergence with a polynomial decay.

\begin{theorem}\label{thm1}
If $\rho$ is separable and has separation
exponent $\theta \in (0, +\infty]$ with (\ref{sepexp}) valid, then
for every $0<\gd <1$, with confidence at least $1-\gd$, we have
\begin{equation}
{\cal R}(\hbox{sgn}(f_{\bf z})) \le 2 \gep^* + {8
\log(2/\gd) \over m} + 4 \bigl(2 c'\bigr)^{{2 \over \theta +2}}
\bigl(C \gga^2\bigr)^{-{\theta \over \theta +2}},
\label{Thmbound}
\end{equation}
where $\gep^*$ is solved by
\begin{equation}
\log {\cal N} \biggl({\gep \over q 2^{q +3} \sqrt{2
\bigl(2 c'\bigr)^{{2 \over \theta +2}} \gga^{-{2 \theta \over
\theta +2}} C^{{2 \over \theta +2}} + 2 C \gep}}\biggr) - {3m \gep
\over 2^{q +9}} =\log (\delta/2). \label{solveThm}
\end{equation}
\begin{enumerate}
\item[{\rm (a)}] If (\ref{coveringanal}) is satisfied, with a
constant $\widetilde{c}$ depending on $\gga$ we have
\begin{equation}
{\cal R}(\hbox{sgn}(f_{\bf z})) \le
\widetilde{c} \biggl({\log (2/\gd) + \bigl(\log m + \log C\bigr)^s
\over m} + C^{-{\theta \over \theta +2}}\biggr).
\label{boundwithexp}
\end{equation}

\item[{\rm (b)}] If (\ref{coveringsob}) is satisfied, there holds
\begin{equation}
{\cal R}(\hbox{sgn}(f_{\bf z})) \le \widetilde{c}
\biggl\{\log {2 \over \gd} \biggl(C^{{s \over (s+1)(\theta +2)}}
m^{-{1 \over s+1}} + C^{{s \over s+2}} m^{-{1 \over {s/2} +1}}
\biggr) + C^{-{\theta \over \theta +2}}\biggr\}.
\label{boundwithsob}
\end{equation}
\end{enumerate}
\end{theorem}

\begin{proof} Choose $t=\bigl({\gga^\theta \over 2 c'
C}\bigr)^{1/(\theta +2)}>0$ and the function $f_{K, C} ={1 \over
t} f_{\hbox{sp}} \in \overline{{\cal H}}_K$. Then we have ${1
\over 2 C} \|f_{K, C}^*\|_K^2 = {1 \over 2 C t^2}$.

Since $y f_{\hbox{sp}} (x) > 0$ almost everywhere, we know that
for almost every $x\in X$, $y= \hbox{sgn} (f_{\hbox{sp}}) (x)$.
This means $f_\rho = \hbox{sgn} (f_{\hbox{sp}})$ and then $f_q =
\hbox{sgn} (f_{\hbox{sp}})$. It follows that ${\cal R}(f_c) =0$
and $V(y, f_{K, C}(x)) = \bigl(1 - {|f_{\hbox{sp}} (x)| \over
t}\bigr)_+^q \in [0, 1]$ almost everywhere. Therefore, we may take
$M=1$ in Proposition \ref{prop2.1}. Moreover,
$$ {\cal E}(f_{K, C}) = \int_Z \Bigl(1 - {y f_{\hbox{sp}} (x) \over t}\Bigr)_+^q d \rho
= \int_X \Bigl(1 - {|f_{\hbox{sp}} (x)| \over t}\Bigr)_+^q d
\rho_X. $$ This can be bounded by (\ref{sepexp}) as
$$ \int_{\{x: |f_{\hbox{sp}} (x)| < t\}}
\Bigl(1 - {|f_{\hbox{sp}} (x)| \over t}\Bigr)_+^q d \rho_X \le
\rho_X \bigl\{x \in X: |f_{\hbox{sp}} (x)| < t \bigr\} \le c'
\Bigl({t \over \gga}\Bigr)^\theta. $$
It follows from the choice
of $t$ that
\begin{equation}
{\cal D}(C) \le c' \Bigl({t \over
\gga}\Bigr)^\theta + {1 \over 2 C t^2} = \bigl(2 c'\bigr)^{{2
\over \theta +2}} \bigl(C \gga^2\bigr)^{-{\theta \over \theta
+2}}. \label{decayDC}
\end{equation}
Then our conclusion follows
from Proposition \ref{prop2.1}. \end{proof}

In case (a), the bound (\ref{boundwithexp}) tells us to choose $C$
such that $(\log C)^s /m \to 0$ and $C\to \infty$ as $m\to
\infty$. By (\ref{boundwithexp}) a reasonable choice of the
regularization parameter $C$ is $C= m^{{\theta +2 \over \theta}}$,
which yields ${\cal R}(\hbox{sgn}(f_{\bf z})) = O\bigl({(\log m)^s
\over m}\bigr)$. In case (b),
\begin{equation}
\hbox{when }
(\ref{coveringsob}) \hbox{ is valid}, \quad C= m^{{\theta +2 \over
\theta + s + \theta s}} \Longrightarrow {\cal R}(\hbox{sgn}(f_{\bf
z})) = O\bigl(m^{-{\theta \over \theta + s + \theta s}}\bigr).
\label{boundsepsob}
\end{equation}

The following is a typical example of separable distribution which is
not strictly separable. In this example, the separation exponent is $\theta=1$.

\begin{example}\label{Example2.1}
Let $X= [-1/2, 1/2]$ and $\rho$ be the
Borel probability measure on $Z$ such that $\rho_X$ is the
Lebesgue measure on $X$ and
$$ f_\rho (x) = \left\{\begin{array}{ll} 1, & \hbox{ for } -1/2 \le
x \le -1/4 \hbox{ and }1/4 \le x \le 1/2, \\ -1, & \hbox{ for }
-1/4 \le x <1/4.
\end{array}\right.$$
\begin{enumerate}
\item[{\rm (a)}] If $K$ is the linear polynomial kernel $K(x, y) =
x \cdot y$, then ${\cal R}(\hbox{sgn}(f_{\bf z})) - {\cal R}(f_c)
\ge 1/4$.
\item[{\rm (b)}] If $K$ is the quadratic polynomial
kernel $K(x, y) = (x \cdot y)^2$, then with confidence $1-\gd$,
$${\cal R}(\hbox{sgn}(f_{\bf z})) \le
{q (q+4) 2^{q + 11} \left(\log m + \log C + 2 \log (2/\gd)\right) \over m}
+ {16 \over C^{1/3}}. $$
Hence one should take $C$ such that $\log C/m \to 0$ and $C\to \infty$ as $m\to \infty$.
\end{enumerate}
\end{example}

\begin{proof} The first statement is trivial.

To see (b), we note that dim${\cal H}_K =1$ and $\kappa =1/4$.
Also, ${\cal E}_0 = \inf\limits_{b\in\RR} {\cal E}(b) =1$. Hence
$\widetilde\kappa = 1/(1 + q 4^{q-2})$. Since ${\cal H}_K =\{a
x^2: a\in \RR\}$ and $\|a x^2\|_K =|a|$, ${\cal N}({\cal B}, \eta)
\le 1/(2 \eta)$. Then (\ref{coveringanal}) holds with $s=1$ and
$c=4 q$. By Proposition \ref{prop2.1}, we see that $\gep^* \le {q (q+4) 2^{q
+ 11} \left(\log (C m) + \log (2/\gd)\right) \over m}$.

Take the function $f_{\hbox{sp}} (x)
= x^2 - 1/16 \in \overline{{\cal H}}_K$ with
$\|f_{\hbox{sp}}^*\|_K =1$. We see that
$y f_{\hbox{sp}} (x) > 0$ almost everywhere. Moreover,
$$\bigl\{x \in X: |f_{\hbox{sp}} (x)| < t \bigr\} \subseteq
\biggl[{\sqrt{1 - 16 t} \over 4}, {\sqrt{1 + 16 t} \over 4}\biggr]
\bigcup \biggl[-{\sqrt{1 + 16 t} \over 4}, -{\sqrt{1 - 16 t} \over
4}\biggr]. $$ The measure of this set is bounded by $8 \sqrt{2}
t$. Hence (\ref{sepexp}) holds with $\theta=1$, $\gga =1$ and $c'
=8 \sqrt{2}$. Then Theorem \ref{thm1} gives the stated bound for ${\cal
R}(\hbox{sgn}(f_{\bf z}))$. \end{proof}

In this paper, for the sample error estimates we only use the
(uniform) covering numbers in $C(X)$. Within the last a few years,
the empirical covering numbers (in $\ell^\infty$ or $\ell^2$), the
leave-one-out error or stability analysis (e.g. Vapnik, 1998;
Bousquet and Ellisseeff, 2002; Zhang, 2004), and some other advanced
empirical process techniques such as the local Rademacher averages
(van der Vaart and Wellner, 1996; Bartlett, Bousquet and Mendelson,
2004; and references therein) and the entropy integrals (van der
Vaart and Wellner, 1996) have been developed to get better sample
error estimates. These techniques can be applied to various
learning algorithms. They are powerful to handle general
hypothesis spaces even with large capacity.

In Zhang (2004) the leave-one-out technique was applied to
improve the sample error estimates given in Bousquet and Ellisseeff
(2002): the sample error has a kernel-independent bound $O({C
\over m})$, improving the bound $O({C \over \sqrt{m}})$ in
Bousquet and Ellisseeff (2002); while the regularization error
$\widetilde{{\cal D}}(C)$ depends on $K$ and $\rho$. In
particular, for $q=2$ the bound (Zhang, 2004, Corollary 4.2) takes
the form:
\begin{equation}
E\bigl({\cal E}(f_{\bf z})\bigr) \le
\Bigl(1 + {4 \kappa^2 C \over m}\Bigr)^2 \inf_{f\in {\cal H}_K}
\Bigl\{{\cal E} (f) + {1 \over 2 C} \|f\|_K^2\Bigr\} = \Bigl(1 +
{4 \kappa^2 C \over m}\Bigr)^2 \Bigl\{\widetilde{{\cal D}}(C) +
{\cal E}(f_q)\Bigr\}. \label{Zhangresult}
\end{equation}

In Bartlett, Jordan and  McAuliffe (2003) the empirical process
techniques are used to improve the sample error estimates for ERM.
In particular, Theorem 12 there states that for a convex set
${\cal F}$ of functions on $X$, the minimizer $\widehat{f}$ of the
empirical error over ${\cal F}$ satisfies
\begin{equation}
{\cal
E} (\widehat{f}) \le \inf_{f\in {\cal F}} {\cal E}(f) + K \max
\biggl\{\gep^*, \Bigl({c_r L^2 \log (1/\gd) \over m}\Bigr)^{1/(2 -
\beta)}, {B L \log (1/\gd) \over m}\biggr\}.
\label{bjmresult}
\end{equation}
Here $K, c_r, \beta$ are
constants, and $\gep^*$ is solved by an inequality. The constant
$B$ is a bound for differences, and $L$ is the Lipschitz constant
for the loss $\phi$ with respect to a pseudometric on $\RR$. For
more details, see Bartlett, Jordan and McAuliffe (2003). The
definitions of $B$ and $L$ together tell us that
\begin{equation}
|\phi(y_1 f(x_1)) - \phi(y_2 f(x_2))| \le L B,
\qquad \forall \ (x_1, y_1) \in Z, (x_2, y_2) \in Z, f\in {\cal
F}. \label{lipschitzc}
\end{equation}

Because of our improvement for the bound of
the random variables $V(y, f(x))$ given by the projection
operator, for the algorithm (\ref{svmone}) the error bounds we
derive here are better than existing results when the kernel has
small complexity. Let us confirm this for separable distributions
with separation exponent $0<\theta<\infty$ and for kernels with
polynomial complexity exponent $s>0$ satisfying
(\ref{coveringsob}). Recall that ${\cal D}(C) =O(C^{-{\theta \over
\theta +2}})$. Take $q=2$.

Consider the estimate (\ref{Zhangresult}). This together with
(\ref{decayDC}) tells us that the derived bound for $E\bigl({\cal
E}(f_{\bf z}) -{\cal E}(f_q)\bigr)$ is at least of the order
$\widetilde{{\cal D}}(C) + {C \over m} \widetilde{{\cal D}}(C) =
O(C^{-{\theta \over \theta +2}} + {C^{{2 \over \theta +2}} \over
m})$. By Lemma \ref{lem1.1}, the optimal bound derived from
(\ref{Zhangresult}) is $O(m^{-{\theta \over \theta +2}})$. Thus,
our bound (\ref{boundsepsob}) is better than (\ref{Zhangresult})
when $0<s<{2 \over \theta +1}$.

Turn to the estimate (\ref{bjmresult}). Take ${\cal F}$ to be the
ball of radius $\sqrt{2 C \widetilde{{\cal D}}(C)}$ of ${\cal
H}_K$ (the expected smallest ball where $f_{\bf z}^*$ lies), we
find that the constant $L B$ in (\ref{lipschitzc}) should be at
least $\kappa \sqrt{2 C \widetilde{{\cal D}}(C)}$. This tells us
that one term in the bound (\ref{bjmresult}) for the sample error
is at least $O\Big({\sqrt{2 C \widetilde{{\cal D}}(C)} \over
m}\Big) = O({C^{{1 \over \theta +2}} \over m})$, while the other
two terms are more involved. Applying Lemma \ref{lem1.1} again, we
find that the bound derived from (\ref{bjmresult}) is at least
$O(m^{-{\theta \over \theta +1}})$. So our bound
(\ref{boundsepsob}) is better than (\ref{bjmresult}) at least for
$0<s<{1 \over \theta +1}$.

Thus, our analysis with the help of the projection operator
improves existing error bounds when the kernel
has small complexity.
Note that in (\ref{boundsepsob}), the values of $s$ 
for which the projection operator gives an improvement 
are values corresponding to rapidly diminishing regularization 
($C=m^\beta$ with $\beta >1$ being large). 

For kernels with large complexity, refined empirical process
techniques (e.g. van der Vaart and Wellner, 1996; Mendelson, 2002;
Zhang, 2004; Bartlett, Jordan and  McAuliffe, 2003) should give
better bounds: the capacity of the hypothesis space may have more
influence on the sample error than the bound of the random
variable $V(y, f(x))$, and the entropy integral is powerful to
reduce this influence. To find the range of this large complexity,
one needs explicit rate analysis for both the sample error and
regularization error. This is out of our scope. It would be
interesting to get better error bounds by combining the ideas of
empirical process techniques and the projection operator.

\begin{problem} \label{problem2.1}
How much improvement can we get for the
total error when we apply the projection operator to empirical
process techniques?
\end{problem}

\begin{problem}\label{problem2.2}
Given $\theta>0, s>0, q \ge 1$, and
$0<\gd<1$, what is the largest number $\ga>0$ such that ${\cal
R}(\hbox{sgn}(f_{\bf z})) =O(m^{-\ga})$ with confidence $1-\gd$
whenever the distribution $\rho$ is separable with separation
exponent $\theta$ and the kernel $K$ satisfies
(\ref{coveringsob})? What is the corresponding optimal choice of
the regularization parameter $C$?
\end{problem}

In particular, for Example \ref{Example2.1} we have the following.

\begin{conjecture} \label{conj2.1}
In Example \ref{Example2.1}, with confidence $1-\gd$
there holds ${\cal R}(\hbox{sgn}(f_{\bf z})) =O({\log (2/\gd)
\over m})$ by choosing $C=m^3$.
\end{conjecture}

Consider the well known setting (Vapnik,
1998; Shawe-Taylor et al., 1998; Steinwart, 2001; Cristianini and
Shawe-Taylor, 2000) of strictly separable distributions
with margin $\gga>0$. In this case, Shawe-Taylor et al. (1998) shows that 
\begin{equation}\label{strictbound}
{\cal R}(\hbox{sgn}(f)) \le {2 \over m} \bigl(\log {\cal N}({\cal F}, 2 m, \gga/2)
+ \log(2/\gd)\bigr) 
\end{equation}
with confidence $1 - \gd$ for $m>2/\gga$
whenever $f\in {\cal F}$ satisfies $y_i f(x_i) \ge \gga$. Here
${\cal F}$ is a function set, ${\cal N}({\cal F}, 2 m, \gga/2)
=\sup\limits_{\vec t \in X^{2m}} {\cal N}({\cal F}, \vec t,
\gga/2)$ and ${\cal N}({\cal F}, \vec t, \gga/2)$ denotes the
covering number of the set $\{(f(t_i))_{i=1}^{2 m}: f\in {\cal
F}\}$ in $\RR^{2 m}$ with the $\ell^\infty$ metric. For a
comparison of this covering number with that in $C(X)$, see Pontil
(2003).

In our analysis, we can take $f_{K, C} = {1 \over \gga}
f_{\hbox{sp}} \in \overline{{\cal H}}_K$. Then $M=\|V(y, f_{K,
C}(x))\|_\infty =0,$ and ${\cal D}(C) = {1 \over 2 C \gga^2}$. We
see from Proposition \ref{prop2.1} (a) that when
(\ref{coveringanal}) is satisfied, there holds ${\cal R}(f_{\bf
z}) \le \widetilde{c} \bigl({(\log(1/\gga)+\log m )^s + \log
(1/\gd) \over m}\bigr)$. But the optimal bound $O({1 \over m})$ is
also valid for spaces with larger complexity, which can be 
seen from (\ref{strictbound}) by the relation of the covering numbers:   
${\cal N}({\cal F}, 2 m, \gga/2) \leq {\cal N}({\cal F}, \gga/2)$. 
See also Steinwart (2001). We see the shortcoming of
our approach for kernels with large complexity. This convinces the
interest of Problem \ref{problem2.1} raised above.

\section{Comparison of Errors}

In this section we consider how to bound the misclassification
error by the $V$-risk. A systematic study of this
problem was done for convex loss functions by Zhang (2004), and
for more general loss functions by Bartlett, Jordan, and McAuliffe
(2003). Using these results, it can be shown that for the
loss function $V_q$, there holds
$$ \psi \Big({\cal R}(\hbox{\rm sgn}(f)) - {\cal R}(f_c)\Big)
\le {\cal E}(f) -
{\cal E}(f_q), $$
where
$\psi: [0, 1] \to \RR_+$ is a function defined in 
Bartlett, Jordan, and McAuliffe
(2003) and can be explicitly computed. 

In fact, we have 
\begin{equation}\label{compareVq}
{\cal R}(\hbox{\rm sgn}(f)) - {\cal R}(f_c) \le c \sqrt{{\cal E}(f) -
{\cal E}(f_q)}.
\end{equation}
Such a comparison of errors holds true even for a general convex loss function, see
Theorem \ref{thm2} in Appendix.
The derived bound for the constant 
$c$ in (\ref{compareVq}) need not be optimal. In the
following we shall give an optimal estimate in a simpler form.

The constant we derive depends on $q$ and is given by
\begin{equation}
C_q =\left\{ \begin{array}{ll} 1, & \hbox{ if }
1\le q \le 2,\\  2 (q-1)/ q, & \hbox{ if }q >2.
\end{array}\right. \label{constq}
\end{equation}
We can see that
$C_q \leq 2$.

\begin{theorem}\label{prop3.1}
Let $f: X\to\RR$ be measurable.
Then
$${\cal R}(\hbox{\rm sgn}(f)) - {\cal R}(f_c) \le \sqrt{C_q \left({\cal E}(f) -
{\cal E}(f_q)\right)} \le \sqrt{2 \left({\cal E}(f) -
{\cal E}(f_q)\right)}.$$
\end{theorem}

\begin{proof} By the definition, only points with sgn$(f)(x)\not= f_c
(x)$ are involved for the misclassification error. Hence
\begin{equation}
{\cal R}(\hbox{sgn}(f)) - {\cal R}(f_c) = \int_X
|f_\rho (x)| \chi_{\{\hbox{sgn} (f)(x)\not= \hbox{sgn} (f_q)
(x)\}} d \rho_X. \label{misdiff}
\end{equation} This in connection
with the Schwartz inequality implies that
$$ {\cal R}(\hbox{sgn}(f)) - {\cal R}(f_c)
\le \left\{\int_X |f_\rho (x)|^2 \chi_{\{\hbox{sgn} (f)(x)\not=
\hbox{sgn} (f_q) (x)\}} d \rho_X \right\}^{1/2}. $$ Thus it is
sufficient to show for those $x\in X$ with $\hbox{sgn} (f)(x)\not=
\hbox{sgn} (f_q) (x)$,
\begin{equation} |f_\rho (x)|^2 \le C_q
\left({\cal E}(f|x) - {\cal E}(f_q|x)\right),
\label{claimone}
\end{equation}
where for $x\in X$, we have denoted
\begin{equation}
{\cal E}(f|x):=\int_Y
V_q (y, f(x)) d \rho (y|x).
\end{equation}

By the definition of the loss function $V_q$, we
have
\begin{equation}{\cal E}(f|x) =(1 - f(x))_+^q {1 + f_\rho (x)
\over 2} + (1 + f(x))_+^q {1 - f_\rho (x) \over 2}.
\label{diffexp}
\end{equation}
It follows that
\begin{equation}
{\cal E}(f|x) - {\cal E}(f_q|x)= \int_0^{f(x) - f_q (x)} F (u) d
u, \label{diff}
\end{equation}
where $F(u)$ is the function
(depending on the parameter $f_\rho (x)$):
$$ F (u) = {1 - f_\rho (x) \over 2} q ( 1 + f_q (x) + u)_+^{q-1}
- {1 + f_\rho (x) \over 2} q ( 1 - f_q (x) - u)_+^{q-1}, \quad
u\in\RR. $$
Since $F(u)$ is nondecreasing and $F(0)=0$, we see
from (\ref{diff}) that when $\hbox{sgn} (f)(x)\not= \hbox{sgn}
(f_q) (x)$, there holds
\begin{equation}{\cal E}(f|x) - {\cal
E}(f_q|x) \ge \int_0^{-f_q (x)} F(u) d u = {\cal E}(0|x) - {\cal
E}(f_q|x) = 1- {\cal E}(f_q|x).
\label{localdifference}
\end{equation}
But
\begin{equation}
{\cal
E}(f_q|x) = {2^{q-1} \left(1 - |f_\rho (x)|^2\right) \over
\left\{(1 + f_\rho (x))^{1/(q-1)} + (1 - f_\rho (x))^{1/(q-1)}
\right\}^{q-1}}. \label{usesmall}
\end{equation}
Therefore,
(\ref{claimone}) is valid (with $t=f_\rho (x)$) once the following
inequality is verified:
$$ {t^2 \over C_q} \le 1 - {2^{q-1} \left(1 - t^2\right) \over
\left\{(1 + t)^{1/(q-1)} + (1 - t)^{1/(q-1)} \right\}^{q-1}},
\qquad t\in [-1, 1]. $$
This is the same as the inequality
\begin{equation}
\left(1 - {t^2 \over C_q}\right)^{-1/(q-1)} \le {(1 +
t)^{-1/(q-1)} + (1 - t)^{-1/(q-1)} \over 2}, \qquad t\in [-1, 1].
\label{claimtwo}
\end{equation}

To prove (\ref{claimtwo}), we use the Taylor expansion
$$ (1 +u)^\ga = \sum_{k=0}^\infty \left(\matrix{\ga \cr k \cr}\right) u^k =
\sum_{k=0}^\infty {\prod_{\ell=0}^{k-1} (\ga -\ell) \over k!} \
u^k, \qquad u\in (-1, 1). $$
With $\ga = -1/(q-1)$, we have
$$ \left(1 - {t^2 \over C_q}\right)^{-1/(q-1)} =
\sum_{k=0}^\infty {\prod_{\ell=0}^{k-1} \left({1 \over q-1} +
\ell\right) \over k!} \ {1 \over C_q^k} \ t^{2 k}  $$
and (all the
odd power terms vanish)
$$ {(1 + t)^{-1/(q-1)} + (1 - t)^{-1/(q-1)} \over 2}
= \sum_{k=0}^\infty {\prod_{\ell=0}^{k-1} \left({1 \over q-1} +
\ell\right) \over k!} \left(\prod_{\ell=0}^{k-1} {{1 \over q-1} +
\ell + k \over 1 + \ell + k}\right)  t^{2 k}. $$
Note that
$$ \prod_{\ell=0}^{k-1} {{1 \over q-1} + \ell + k \over 1 + \ell + k} \ge {1 \over C_q^k}. $$
This proves (\ref{claimtwo}) and hence our conclusion.
\end{proof}

When ${\cal R}(f_c) =0$, the estimate in Theorem \ref{prop3.1}
can be improved (Zhang  2004, Bartlett,  Jordan and McAuliffe 2003)
to
\begin{equation}{\cal R}(\hbox{sgn}(f)) \le {\cal E}(f).
\label{sepbound}
\end{equation}

In fact, ${\cal R}(f_c)=0$ implies $|f_\rho (x)| =1$ almost
everywhere. This in connection with (\ref{usesmall}) and
(\ref{localdifference}) gives ${\cal E}(f_q|x) =0$ and ${\cal
E}(f|x) \ge 1$ when sgn$(f)(x)\neq f_c(x).$ Then (\ref{claimone})
can be improved to the form $|f_\rho (x)| \le  {\cal E}(f|x)$.
Hence (\ref{sepbound}) follows from (\ref{misdiff}).

Theorem \ref{prop3.1} tells us that the misclassification
error can be bounded by the $V$-risk associated with
the loss function $V$. So our next step is to study the
convergence of the $q$-classifier with respect to the
$V$-risk ${\cal E}$.

\section{Bounding the Offset}

If the offset $b$ is fixed in the scheme (\ref{svmone}), the
sample error can be bounded by standard argument using some
measurements of the capacity of the RKHS. However, the offset is
part of the optimization problem and even its boundedness can not
be seen from the definition. This makes our setting here
essentially different from the standard Tikhonov regularization
scheme. The difficulty of bounding the offset $b$ has been
realized in the literature (e.g. Steinwart, 2002; Bousquet and
Ellisseeff, 2002). In this paper we shall overcome this difficulty
by means of special features of the loss function $V$.

The difficulty raised by the offset can also be seen from the
stability analysis (Bousquet and Ellisseeff, 2002). As shown in
Bousquet and Ellisseeff (2002), the SVM $1$-norm classifier without
the offset is uniformly stable, meaning that $\sup\limits_{{\bf
z}\in Z^m, {z}_0' \in Z} \|V(y, f_{{\bf z}}(x)) - V(y, f_{{\bf
z}'}(x))\|_{L^\infty} \le \gb_m$ with $\gb_m \to 0$ as $m\to
\infty$, and ${\bf z}'$ is the same as ${\bf z}$ except that one
element of ${\bf z}$ is replaced by $z_0'$.

The SVM $1$-norm classifier with the offset is not uniformly
stable. To see this, we choose $x_0 \in X$ and samples ${\bf z}
=\{(x_0, y_i)\}_{i=1}^{2 n +1}$ with $y_i =1$ for $i=1, \ldots,
n+1$, and $y_i = -1$ for $i=n+2, \ldots, 2 n +1$. Take $z_0'
=(x_0, -1)$. As $x_i$ are identical, one can see from the
definition (\ref{svmtwo}) that $f_{\bf z}^* =0$ (since ${\cal
E}_{\bf z}(f_{\bf z}) = {\cal E}_{\bf z}(b_{\bf z} + f_{\bf
z}(x_0))$). It follows that $f_{\bf z} = 1$ while $f_{{\bf z}'}
=-1$. Thus, $|f_{\bf z}- f_{{\bf z}'}| =2$ which does not converge
to zero as $m=2 n +1$ tends to infinity. It is unknown whether the
$q$-norm classifier is uniformly stable for $q>1$.

How to bound the offset is the main goal of this section. In Wu and
Zhou (2004) a direct computation is used to realize this point for
$q=1$. Here the index $q>1$ makes a direct computation very
difficult, and we shall use two bounds to overcome this
difficulty. By $x\in (X, \rho_X)$ we mean that $x$ lies in the
support of the measure $\rho_X$ on $X$.

\begin{lemma}\label{lem4.1}
For any $C>0, m\in\NN$ and ${\bf z} \in
Z^m$, a minimizer of (\ref{svmtwo}) satisfies
\begin{equation}
\min_{1\le i \le m} f_{\bf z} (x_i)  \le 1 \quad \hbox{and} \quad
\max_{1\le i \le m} f_{\bf z} (x_i)  \ge
-1\label{boundfz}
\end{equation}
and a minimizer of (\ref{targetf})
satisfies
\begin{equation}
 \inf_{x\in (X, \rho_X)}
\widetilde{f}_{K, C}(x) \le 1 \quad \hbox{and} \quad \sup_{x\in
(X, \rho_X)} \widetilde{f}_{K, C}(x) \ge -1.
\label{boundfh}
\end{equation}
\end{lemma}

\begin{proof} Suppose a minimizer of (\ref{svmtwo}) $f_{\bf z}$
satisfies $r:=\min\limits_{1\le i \le m} f_{\bf z} (x_i) >1$. Then
$f_{\bf z} (x_i) - (r-1) \ge 1$ for each $i$. We claim that
$$ y_i =1, \qquad \forall i=1, \ldots, m. $$

In fact, if the set $I :=\{i\in\{1, \ldots, m\}: \, y_i =-1\}$ is not empty, we have
$$ {\cal E}_{\bf z} (f_{\bf z} - (r-1)) =
{1 \over m} \sum_{i\in I} \left(1 + f_{\bf z} (x_i) -(r
-1)\right)^q < {1 \over m} \sum_{i\in I} \left(1 + f_{\bf z}
(x_i)\right)^q = {\cal E}_{\bf z} (f_{\bf z}), $$
which is a
contradiction to the definition of $f_{\bf z}$. Hence our claim is
verified. From the claim we see that ${\cal E}_{\bf z} (f_{\bf z}
- (r-1)) = 0 = {\cal E}_{\bf z} (f_{\bf z})$. This tells us that
$\widetilde{f}_{\bf z}:=f_{\bf z} - (r-1)$ is a minimizer of
(\ref{svmtwo}) satisfying the first inequality, hence both
inequalities of (\ref{boundfz}).

In the same way, if a minimizer of (\ref{svmtwo}) $f_{\bf z}$
satisfies $r:=\max\limits_{1\le i \le m} f_{\bf z} (x_i) < -1$.
Then we can see that $y_i =-1$ for each $i$. Hence ${\cal E}_{\bf
z} (f_{\bf z} - r-1) = {\cal E}_{\bf z} (f_{\bf z})$ and
$\widetilde{f}_{\bf z}:=f_{\bf z} - r-1$ is a minimizer of
(\ref{svmtwo}) satisfying the second inequality and hence both
inequalities of (\ref{boundfz}).

Therefore, we can always find a minimizer of (\ref{svmtwo})
satisfying (\ref{boundfz}).

We prove the second statement in the same way. Suppose
$r:=\inf\limits_{x\in (X, \rho_X)} \widetilde{f}_{K, C} (x) >1$
for a minimizer $\widetilde{f}_{K, C}$ of (\ref{targetf}). Then
$\widetilde{f}_{K, C} (x) -(r-1) \ge 1$ for almost every $x\in (X,
\rho_X)$. Hence
$${\cal E} \left(\widetilde{f}_{K, C} - (r-1)\right) = \int_{X}
\left(1 + \widetilde{f}_{K, C} (x) - (r-1)\right)^q P({\cal
Y}=-1|x) d \rho_X \le {\cal E} \bigl(\widetilde{f}_{K, C}\bigr).
$$ As $f_{K, C}$ is a minimizer of (\ref{targetf}), the
above equality must hold. It follows that $P({\cal Y}=-1|x)=0$ for
almost every $x\in (X, \rho_X)$. Hence $\widetilde{F}_{K, C}:=
\widetilde{f}_{K, C} -(r-1)$ is a minimizer of (\ref{targetf})
satisfying the first inequality and thereby both inequalities of
(\ref{boundfh}).

Similarly, when $r:=\sup\limits_{x\in (X, \rho_X)}
\widetilde{f}_{K, C} (x) <-1$ for a minimizer $\widetilde{f}_{K,
C}$ of (\ref{targetf}). Then $P({\cal Y}=1|x)=0$ for almost every
$x\in (X, \rho_X)$. Hence $\widetilde{F}_{K, C}:= f_{K, C} - r-1$
is a minimizer of (\ref{targetf}) satisfying the second inequality
and thereby both inequalities of (\ref{boundfh}).

Thus, (\ref{boundfh}) can always be realized by a minimizer of
(\ref{targetf}). \end{proof}

In what follows we always choose $f_{\bf z}$ and
$\widetilde{f}_{K, C}$ to satisfy (\ref{boundfz}) and
(\ref{boundfh}), respectively.

Lemma \ref{lem4.1} yields bounds for the ${\cal H}_K$-norm and
offset for $f_{\bf z}$ and $\widetilde{f}_{K, C}$. Denote
$b_{\widetilde{f}_{K, C}}$ as $\widetilde b_{K, C}$.

\begin{lemma}\label{lem4.2}
For any $C>0, m\in\NN, f_{K, C} \in
\overline{{\cal H}}_K$, and ${\bf z} \in Z^m$, there hold
\begin{enumerate}
\item[{\rm (a)}] $\|\widetilde{f}_{K, C}^*\|_K \le \sqrt{2 C
\widetilde{{\cal D}}(C)} \le \sqrt{2 C}, \quad |\widetilde
b_{K,C}|\le 1+\|\widetilde{f}_{K,C}^*\|_\infty. $
\item[{\rm (b)}]
$\|\widetilde{f}_{K, C}\|_{\infty} \le 1+2\kappa \sqrt{2 C
\widetilde{{\cal D}}(C)} \le 1+2\kappa \sqrt{2 C}, \quad {\cal
E}(\widetilde{f}_{K, C}) \le {\cal E}(f_q) + \widetilde{{\cal
D}}(C) \le 1.$
\item[{\rm (c)}] $|b_{\bf z}| \le 1 + \kappa
\|f_{\bf z}^*\|_K.$
\end{enumerate}
\end{lemma}

\begin{proof} By the definition (\ref{targetf}), we see from the choice $f= 0
+ 0$ that
\begin{equation}\widetilde{{\cal D}}(C) = {\cal E}
(\widetilde{f}_{K, C}) -{\cal E}(f_q) + {1 \over 2 C}
\|\widetilde{f}_{K, C}^*\|_K^2 \le 1 - {\cal
E}(f_q).\label{normbound}
\end{equation}
Then the first inequality
in (a) follows.

Note that (\ref{boundfh}) gives
$$-1 \le \sup_{x\in (X,\rho_X)}\widetilde{f}_{K,C}\le
\widetilde b_{K,C} + \|\widetilde{f}_{K,C}^*\|_\infty$$
and
$$\widetilde b_{K,C}- \|\widetilde{f}_{K,C}^*\|_\infty
\le \inf_{x\in (X,\rho_X)}\widetilde{f}_{K,C}\le 1.$$
Thus,
$|\widetilde b_{K,C}|\le 1+\|\widetilde{f}_{K,C}^*\|_\infty$. This
proves the second inequality in (a).

Since the first inequality in (a) and (\ref{repro}) lead to
$\|\widetilde{f}_{K, C}^*\|_{\infty} \le \kappa \sqrt{2 C
\widetilde{{\cal D}}(C)},$ we obtain
$\|\widetilde{f}_{K,C}\|_\infty\le
1+2\|\widetilde{f}_{K,C}^*\|_\infty\le 1+2\kappa\sqrt{2C
\widetilde{{\cal D}}(C)}.$ Hence the first inequality in (b)
holds.

The second inequality in (b) is an easy consequence of
(\ref{normbound}).

The inequality in (c) follows from (\ref{boundfz}) in the same way
as the proof of the second inequality in (a). \end{proof}

\section{Convergence of the $q$-Norm Soft Margin Classifier}

In this section, we apply the ERM technique to analyze the
convergence of the $q$-classifier for $q>1$. The situation here is
more complicated than that for $q=1$. We need the following lemma
concerning $q>1$.

\begin{lemma}\label{lem5.1}
For $q>1$, there holds
$$ \left|(x)_+^q - (y)_+^q\right| \le
q \left(\max\{x, y\}\right)_+^{q-1} |x-y|, \qquad \forall x, y\in\RR. $$
If $y\in [-1, 1]$, then
$$ \left|(1-x)_+^q - (1-y)_+^q\right| \le
q 4^{q-1} |x-y| + q 2^{q-1} |x-y|^q, \qquad \forall x\in\RR. $$
\end{lemma}

\begin{proof} We only need to prove the first inequality for $x>y$. This is trivial:
$$ (x)_+^q - (y)_+^q =\int_y^x q (u)_+^{q-1} d u \le q (x)_+^{q-1} (x-y). $$

If $y\in [-1, 1]$, then $1-y \ge 0$ and the first inequality
yields
\begin{equation} \left|(1-x)_+^q - (1-y)_+^q\right| \le q
\left(\max\{1-x, 1-y\}\right)_+^{q-1} |x-y|.
\label{intermed}
\end{equation}
When $x \ge 2 y -1$, we have
$$ \left|(1-x)_+^q - (1-y)_+^q\right| \le q 2^{q-1} (1-y)^{q-1} |x-y| \le q 4^{q-1} |x-y|. $$
When $x < 2 y -1$, we have $1-x < 2 (y-x)$ and $x<1$. This in
combination with $\max\{1-x, 1-y\} \le \max\{1-x, 2\}$ and
(\ref{intermed}) implies
$$ \left|(1-x)_+^q - (1-y)_+^q\right| \le q \{(1-x)^{q-1} + 2^{q-1}\} |x-y|
\le q 2^{q-1} |x-y|^q + q 2^{q-1} |x-y|. $$ This proves Lemma
\ref{lem5.1}.
\end{proof}

The second part of Lemma \ref{lem5.1} will be used in Section 6.
The first part can be used to verify Proposition \ref{prop1.2}.

\medskip

\noindent {\bf Proof of Proposition \ref{prop1.2}.} It is trivial
that ${\cal D}(C)\ge \widetilde{\cal D}(C).$ To show the second
inequality, apply the first inequality of Lemma \ref{lem5.1} to
the two numbers $1- y\widetilde f _{K,C} (x)$ and   $1- y
\widetilde b_{K, C}$. We see that
$$ \bigl(1- y \widetilde f_{K, C} (x) \bigr)_+^q \ge
\bigl(1- y \widetilde b_{K, C}\bigr)_+^q - q \bigl ( 1+
|\widetilde f_{K,C}(x)| + |\widetilde b_{K,C}| \bigr)^{q-1}
|\widetilde f _{K,C}^* (x)|. $$
Notice that $|\widetilde f_{K,
C}^*(x)| \le \kappa \|\widetilde f_{K, C}^*\|_K$ and by Lemma
\ref{lem4.2}, $|\widetilde b_{K,C}| \le 1+ \kappa \|\widetilde
f_{K,C}^*\|_K.$ Hence
$${\cal E}(\widetilde f_{K, C}) \ge {\cal E}(\widetilde b_{K, C}) -
\kappa q 2^{q-1} \bigl( 1 + \kappa \|\widetilde f_{K, C}^*\|_K
\bigr) ^{q-1} \|\widetilde f_{K, C}^*\|_K.$$
It follows that when
$\|\widetilde f_{K, C}^*\|_K \le \widetilde \kappa$, we have
$${\cal E}(\widetilde f_{K, C}) - {\cal E}(f_q) \ge {\cal E}_0 -
\kappa q 2^{q-1} \bigl( 1 + \kappa \widetilde \kappa \bigr) ^{q-1}
\widetilde \kappa.$$
Since ${\cal E}_0\le 1$, the definition
(\ref{kappatilde}) of $\widetilde \kappa$ yields $\widetilde
\kappa \le 1/(1 + \kappa) \le \min\{1, 1/\kappa\}.$ Hence
$$\widetilde{\cal D}(C) \ge {\cal E}(\widetilde f_{K, C}) - {\cal E}(f_q) \ge
{\cal E}_0- \kappa q 4^{q-1}\widetilde \kappa =\widetilde\kappa
\ge \widetilde\kappa^2. $$
As $C\ge 1/2,$ we conclude
(\ref{lowerD}) in this case.

When $\|\widetilde f_{K, C}^*\|_K > \widetilde\kappa$, we also have
$$ \widetilde {\cal D}(C) \ge {1 \over 2 C } \|\widetilde f_{K, C}^*\|_K^2 \ge
{\widetilde\kappa^2 \over 2 C }. $$

Thus in both case we have verified (\ref{lowerD}).

Note that  $\widetilde\kappa =0$ if and only if ${\cal E}_0 =0.$
This means for some $b_0' \in [-1, 1]$, $f_q (x) = b_0'$ in
probability. By the definition of $f_q$, the last assertion of
Proposition \ref{prop1.2} follows. \hfill\BlackBox

The loss function $V$ is not Lipschitz, but Lemma \ref{lem5.1}
enables us to derive a bound for ${\cal E}(\pi (f_{\bf z})) -
{\cal E}_{\bf z} (\pi (f_{\bf z}))$ with confidence, as done for
Lipschitz loss functions in Mukherjee, Rifkin and  Poggio (2002).
Since the function $\pi (f_{\bf z})$ changes and lies in a set of
functions, we shall compare the error with the empirical error for
functions from a set
\begin{equation} {\cal F}:=\left\{\pi (f):
f\in B_R +[-B, B]\right\}. \label{subRB}
\end{equation}
Here $B_R = \{f^* \in {\cal H}_K:
\|f^*\|_K \le R\}$ and the
constant $B$ is a bound for the offset.

The following probability inequality was motivated by sample error
estimates for the square loss (Barron 1990, Bartlett 1998, Cucker
and Smale 2001, Lee, Bartlett and Williamson 1998) and will be
used in our estimates.

\begin{lemma}\label{lem5.2}
Suppose a random variable $\xi$
satisfies $0\le \xi \le M$, and ${\bf z}=(z_i)_{i=1}^m$ are
independent samples. Let $\mu= E(\xi)$. Then for every $\gep >0$
and $0<\ga \le 1$, there holds
$$ \hbox{\rm Prob}_{{\bf z} \in Z^m} \left\{ {\mu - {1 \over m} \sum_{i=1}^m \xi (z_i) \over
\sqrt{\mu + \gep} } \geq \ga \sqrt{\gep}\right\} \le \exp\left\{-{3
\ga^2 m \gep \over 8 M}\right\}. $$
\end{lemma}

\begin{proof} As $\xi$ satisfies $|\xi - \mu| \le M$,
the one-side Bernstein inequality tells us that
$$ \hbox{\rm Prob}_{{\bf z} \in Z^m} \left\{ {\mu - {1 \over m} \sum_{i=1}^m \xi (z_i) \over
\sqrt{\mu + \gep}} \geq \ga \sqrt{\gep}\right\} \le \exp\left\{-{\ga^2
m (\mu + \gep) \gep \over 2 \left(\gs^2 + {1 \over 3} M \ga
\sqrt{\mu + \gep} \sqrt{\gep}\right)}\right\}. $$
Here $\gs^2 \le
E(\xi^2) \le M E(\xi) = M \mu$ since $0\le \xi \le M$. Then we
find that
$$ \gs^2 + {1 \over 3} M \ga \sqrt{\mu + \gep} \sqrt{\gep}
\le M \mu + {1\over 3} M {(\mu + \gep)} \le {4 \over 3} M (\mu +
\gep). $$ This yields the desired inequality. \end{proof}

Now we can turn to the error bound involving a function set. Lemma
\ref{lem5.1} yields the following bounds concerning the loss
function $V$:
\begin{equation} \left|{\cal E}_{\bf z}(f) - {\cal
E}_{\bf z}(g)\right| \le q \max\left\{\left(1 +
\|f\|_{\infty}\right)^{q-1}, \left(1 +
\|g\|_{\infty}\right)^{q-1}\right\} \|f-g\|_{\infty}
\label{lipschitzem}
\end{equation}
and
\begin{equation}\left|{\cal
E} (f) - {\cal E} (g)\right| \le q \max\left\{\left(1 +
\|f\|_{\infty}\right)^{q-1}, \left(1 +
\|g\|_{\infty}\right)^{q-1}\right\} \|f-g\|_{\infty}.
\label{lipschitz}
\end{equation}

\begin{lemma}\label{lem5.3}
Let ${\cal F}$ be a subset of $C(X)$
such that $\|f\|_\infty \le 1$ for each $f\in {\cal F}$. Then for
every $\gep >0$ and $0<\ga \le 1$, we have
$$\hbox{\rm Prob}_{{\bf z}\in Z^m} \left\{ \sup_{f \in
{\cal F}} {{\cal E}(f) - {\cal E}_{\bf z}(f) \over \sqrt{{\cal
E}(f) + \gep}} \ge 4 \ga \sqrt{\gep}\right\}
 \le {\cal N}\left({\cal F}, {\ga \gep \over q 2^{q-1}}\right)
\exp\left\{-{3 \ga^2 m \gep \over 2^{q +3}}\right\}. $$
\end{lemma}

\begin{proof} Let $\{f_j\}_{j=1}^J \subset {\cal F}$ with $J={\cal
N}\left({\cal F}, {\ga \gep \over q 2^{q-1}}\right)$ such that
${\cal F}$ is covered by balls centered at $f_j$ with radius ${\ga
\gep\over q 2^{q-1}}$. Note that $\xi =V(y, f(x))$ satisfies $0\le
\xi \le \left(1 +\|f\|_\infty\right)^q \le 2^q$ for $f\in {\cal
F}$. Then for each $j$, Lemma \ref{lem5.2} tells
$$\hbox{\rm Prob}_{{\bf z}\in Z^m} \left\{{{\cal E}(f_j) -
{\cal E}_{\bf z}(f_j) \over \sqrt{{\cal E}(f_j) + \gep}} \ge \ga
\sqrt{\gep}\right\} \le \exp\left\{-{3 \ga^2 m \gep \over 8 \cdot
2^q}\right\}. $$

For each $f \in {\cal F}$, there is some $j$ such that $\|f -
f_j\|_{\infty} \le {\ga \gep\over q 2^{q-1}}$. This in connection
with (\ref{lipschitzem}) and (\ref{lipschitz}) tells us that
$|{\cal E}_{\bf z}(f) - {\cal E}_{\bf z}(f_j)|$ and $|{\cal E}(f)
- {\cal E}(f_j)|$ are both bounded by $\ga \gep$. Hence
$${|{\cal E}_{\bf z}(f) - {\cal E}_{\bf z}(f_j)| \over \sqrt{{\cal E}(f) +
\gep}}\le \ga \sqrt{\gep} \qquad \hbox{ and } \qquad {|{\cal E}
(f) - {\cal E} (f_j)|\over \sqrt{{\cal E}(f) + \gep}} \le \ga
\sqrt{\gep}.$$
The latter implies that $\sqrt{{\cal E}(f_j) +
\gep} \le 2 \sqrt{{\cal E}(f) + \gep}. $ Therefore,
$$\hbox{\rm Prob}_{{\bf z}\in Z^m} \left\{ \sup_{f \in
{\cal F}} {{\cal E}(f) - {\cal E}_{\bf z}(f) \over \sqrt{{\cal
E}(f) + \gep}} \ge 4 \ga \sqrt{\gep}\right\} \le \sum_{j=1}^J
\hbox{\rm Prob} \left\{{{\cal E}(f_j) - {\cal E}_{\bf z}(f_j)
\over \sqrt{{\cal E}(f_j) + \gep}} \ge \ga \sqrt{\gep}\right\}  $$
which is bounded by $J \cdot \exp\left\{-{3 \ga^2 m \gep \over
2^{q +3}}\right\}$. \end{proof}

Take ${\cal F}$ to be the set (\ref{subRB}). The following
covering number estimate will be used.

\begin{lemma}\label{lem5.4}
Let ${\cal F}$ be given by (\ref{subRB})
with $R\ge \widetilde\kappa$ and $B=1 + \kappa R.$ Its covering
number in $C(X)$ can be bounded as follows:
$${\cal N}({\cal F},\eta)\le {\cal
N}\left( {\eta\over 2R}\right), \qquad \forall \eta >0.$$
\end{lemma}

\begin{proof} It follows from the fact $\|\pi (f) - \pi (g)\|_\infty \le
\|f-g\|_\infty$ that
$${\cal N}({\cal F},\eta)\le{\cal N}\left(B_R +[-B,B],
\eta\right).$$
The latter is bounded by
$\bigl\{\bigl(\kappa + {1 \over \widetilde\kappa}\bigr){2 R \over \eta} +1\bigr\}
{\cal
N}\left(B_R, {\eta\over 2}\right)$ since
${2B \over \eta}
\le \bigl(\kappa + {1 \over \widetilde\kappa}\bigr){2 R \over \eta}$ and
$$\|(f^*+b_f)-(g^*+b_g)\|_\infty\le \|f^*-g^*\|_\infty+|b_f-b_g|.$$
Note that an ${\eta \over 2R}$-covering of ${\cal B}$ is the same
as an ${\eta\over 2}$-covering of $B_R$. Then our conclusion
follows from Definition \ref{defn2.1}.\end{proof}

We are in a position to state our main result on the error
analysis. Recall $\theta_M$ in (\ref{Mtheta}).

\begin{theorem}\label{thm3}
Let $f_{K, C}\in \overline{{\cal H}}_K,$
$M\ge \|V(y, f_{K, C}(x))\|_\infty,$ and $0<\gb \le 1$. For every
$\gep>0$, we have
$$ {\cal E}(\pi (f_{\bf z})) - {\cal E}(f_q) \le (1 + \gb)
\left(\gep + {\cal D}(C)\right) $$
with confidence at least $1- F(\gep)$ where $F: \RR_+ \to \RR_+$
is defined by
\begin{equation}F(\gep) := \exp\left\{-{ m \gep^2
\over 2 M (\gD + \gep)}\right\} + {\cal N}\left({\gb( \gep + {\cal
D}(C))^{3/2} \over q2^{q+3}\gS}\right) \exp\left\{-{3 m \gb^2
\left({\cal D}(C) + \gep\right)^2 \over 2^{q +9} \left(\gD +
\gep\right)}\right\} \label{Fexpression}
\end{equation} with $\gD:=
{\cal D}(C) +{\cal E}(f_q)$ and $\gS:=  \sqrt{2 C(\gD + \gep)( \gD
+ \theta_M\gep)}$.
\end{theorem}

\begin{proof} Let $\gep >0$. We prove our conclusion in three steps.

\smallskip
{\it Step 1:} Estimate ${\cal E}_{\bf z}(f_{K, C})- {\cal E}(f_{K,
C})$.

Consider the random variable $\xi= V(y, f_{K, C}(x))$ with $0\le
\xi \le M.$ If $M>0$, since $\sigma^2(\xi)\le M {\cal E}(f_{K,C})
\le M ({\cal D}(C)+{\cal E}(f_q)),$ by the one-side Bernstein
inequality we obtain ${\cal E}_{\bf z}(f_{K, C})- {\cal E}(f_{K,
C}) \le  \gep$ with confidence at least
$$1- \exp\left\{-{m {\gep^2} \over 2(\sigma^2(\xi)+{1\over 3}M\gep)}
\right\}  \ge 1- \exp\left\{-{m \gep^2 \over
2M(\gD+\gep)}\right\}.$$ If $M=0$, then $\xi =0$ almost
everywhere. Hence ${\cal E}_{\bf z}(f_{K, C})- {\cal E}(f_{K, C})
=0$ with probability $1$. Thus, in both cases, there exists
$U_1\in Z^m$ with measure at least $1- \exp\left\{-{ m \gep^2
\over 2 M\left(\gep + \gD\right)}\right\}$ such that ${\cal
E}_{\bf z}(f_{K, C})- {\cal E}(f_{K, C})\le \theta_M \gep$
whenever ${\bf z}\in U_1.$

\smallskip
{\it Step 2:} Estimate ${\cal E}(\pi (f_{\bf z})) - {\cal E}_{\bf
z} (\pi (f_{\bf z}))$.

Let ${\cal F}$ be given by (\ref{subRB}) with $R=\sqrt{2 C
\left(\gD + \theta_M \gep\right)}$ and $B= 1 + \kappa R$. By
Proposition \ref{prop1.2}, $R \ge \sqrt{2 C {\cal D}(C)} \ge
\widetilde\kappa$. Applying Lemma \ref{lem5.3} to ${\cal F}$ with
$\tilde{\gep}:={\cal D}(C) + \gep
>0$ and $\ga ={\gb \over 8} \sqrt{\tilde{\gep}/\left(\tilde{\gep} +{\cal
E}(f_q)\right)} \in (0, 1/8],$ we have
\begin{equation} {\cal
E}(f) - {\cal E}_{\bf z} (f) \le 4 \ga \sqrt{\tilde{\gep}}
\sqrt{{\cal E}(f) - {\cal E}(f_q) + \tilde{\gep} + {\cal E}(f_q)},
\qquad \forall f\in {\cal F} \label{estfz}
\end{equation} for ${\bf
z} \in U_2$ where $U_2$ is a subset of $Z^m$ with measure at least
$$1- {\cal N}\Big({\cal F}, {\ga \tilde{\gep} \over q 2^{q-1}}\Big)
\exp\bigg\{-{3  m\ga^2 \tilde{\gep} \over 2^{q +3}}\bigg\} \ge 1-
{\cal N}\Big({\gb( \gep + {\cal D}(C))^{3/2} \over
q2^{q+3}\gS}\Big) \exp\bigg\{-{3m\gb^2({\cal D}(C)+\gep)^2\over
2^{q+9}(\Delta+\gep)}\bigg\}. $$ In the above inequality we have
used Lemma \ref{lem5.4} to bound the covering number.

For ${\bf z} \in U_1 \cap U_2$, we have
$$ {1 \over 2 C} \|f_{\bf z}^*\|_K^2 \le {\cal E}_{\bf z} (f_{K, C})
+ {1 \over 2 C} \|f_{K, C}^*\|_K^2 \le {\cal E} (f_{K, C}) +
\theta_M \gep + {1 \over 2 C} \|f_{K, C}^*\|_K^2$$ which equals to
${\cal D}(C) + \theta_M \gep +{\cal E}(f_q) = \gD + \theta_M\gep.$
It follows that $\|f_{\bf z}^*\|_K \le R$. By Lemma \ref{lem4.2},
$|b_{\bf z}| \le B$. This means, $\pi (f_{\bf z}) \in {\cal F}$
and (\ref{estfz}) is valid for $f=\pi (f_{\bf z})$.

\smallskip
{\it Step 3:} Bound ${\cal E}(\pi (f_{\bf z})) - {\cal E}(f_q)$
using (\ref{decomerror}).

Let $\ga$ and $\tilde{\gep}$ be the same as in Step 2. For ${\bf
z}\in U_1\bigcap U_2,$ both ${\cal E}_{\bf z} (f_{K, C})-{\cal
E}(f_{K, C})\le \theta_M\gep \le \gep$ and (\ref{estfz}) with
$f=\pi (f_{\bf z})$ hold true. Then (\ref{decomerror}) tells us
that
$${\cal E}(\pi (f_{\bf z})) - {\cal E}(f_q) \le 4 \ga
\sqrt{\tilde{\gep}} \sqrt{\left({\cal E}(\pi (f_{\bf z})) - {\cal
E}(f_q)\right) + \tilde{\gep} + {\cal E}(f_q)}  + \tilde{\gep}. $$

Denote $r:= {\cal E}(\pi (f_{\bf z})) - {\cal E}(f_q) +
\tilde{\gep} + {\cal E}(f_q)>0$, we see that
$$r \le \tilde{\gep} + {\cal E}(f_q) + 4 \ga \sqrt{\tilde{\gep}}
\sqrt{r} + \tilde{\gep}. $$
It follows that
$$ \sqrt{r} \le 2 \ga \sqrt{\tilde{\gep}} + \sqrt{4 \ga^2 \tilde{\gep} + 2
\tilde{\gep} +  {\cal E}(f_q)}. $$
Hence
$$ {\cal E}(\pi (f_{\bf z})) - {\cal E}(f_q) = r - (\tilde{\gep} + {\cal E}(f_q))
\le \tilde{\gep} + 8 \ga^2 \tilde{\gep} + 4 \ga \tilde{\gep}
\sqrt{4 \ga^2 + 2 +  {\cal E}(f_q)/\tilde{\gep}}.
$$
Putting the choice of $\ga$ into above, we find that
$$ {\cal E}(\pi (f_{\bf z})) - {\cal E}(f_q) \le
\tilde{\gep} + {\gb^2 \tilde{\gep}^2 \over 8 \left(\tilde{\gep} +
{\cal E}(f_q)\right)} + {\gb \tilde{\gep} \over 2}
\sqrt{{\tilde{\gep} \over \tilde{\gep} +  {\cal E}(f_q)}}
\sqrt{{\gb^2 \tilde{\gep} \over 16 \left(\tilde{\gep} +  {\cal
E}(f_q)\right)} + 2 + {{\cal E}(f_q) \over \tilde{\gep}}} $$
which
is bounded by $(1 + \gb) \tilde{\gep}=(1 + \gb)(\gep+{\cal
D}(C)).$

Finally, noting that the measure of $U_1\bigcap U_2$ is at least
$1-F(\gep)$, the proof is finished. \end{proof}

Observe that the function $F$ is strictly decreasing and $F(0)>1,
\lim\limits_{\gep \to \infty} F(\gep) =0$. Hence for every $0<\gd
< 1$ there exists a unique number $\gep >0$ satisfying $F(\gep) =
\gd$. Also, for a fixed $\gep >0$, $F(\gep) <\gd$ for sufficiently
large $m$, since $F(\gep)$ can be written as $a^m + c b^m$ with
$0<a, b <1$. Therefore, Theorem \ref{thm3} can be restated in the following
form.

\begin{corollary}\label{cor5.1}
Let $F$ be given in Theorem \ref{thm3}. For
every $0<\gd <1$, define $\gep(\gd, m, C, \gb) >0$ to be the
unique solution to the equation $F(\gep) =\gd$. Then with
confidence at least $1-\delta$, (\ref{restateThm}) holds.
Moreover, $\lim\limits_{m\to\infty} \gep (\gd, m, C, \gb) =0$.
\end{corollary}

Now we can prove the statements we made in Section 2 for the
deterministic case.

\medskip

\noindent {\bf Proof of Proposition \ref{prop2.1}.} Take $\gb =1$.
Since ${\cal R}(f_c) =0$, we know that $f_q = f_c,\ {\cal
E}(f_q)=0$ and $\gD={\cal D}(C)$. Then $\gS \le \sqrt{2 C ({\cal
D}(C) + \theta_M \gep)} \sqrt{{\cal D}(C) + \gep}$ and
$${\cal
N}\left({\gb( \gep + {\cal D}(C))^{3/2} \over
q2^{q+3}\gS}\right)
\le {\cal N}\left({\gep\over
q2^{q+3}{\cal M}}\right).$$

The function value $F(\gep)$ can be bounded by
$$\exp\left\{-{m \gep^2 \over 2 M ({\cal D}(C)+\gep)}\right\}
+ {\cal N}\left({\gep\over
q2^{q+3}{\cal M}}\right)
\exp\left\{-{3 m \gep \over 2^{q
+9}}\right\}. $$
The first term above is bounded by $\gd/2$ when $\gep \ge
{4 M \log (2/\gd)\over m}+{\cal D}(C).$ The second term is at most
$\gd/2$ if $\gep \ge \gep^*.$ Therefore
$$\gep (\gd, m, C, \gb)\le
\max\left\{{4 M \log (2/\gd)\over m}+{\cal D}(C), \gep^*\right\},
$$ and (\ref{determ}) follows from Theorem \ref{thm3}.

(a) When (\ref{coveringanal}) holds, noting that the left side of
(\ref{kernelcov}) is strictly decreasing, it is easy to check that
$$\gep^* \le 2^{q +9} \biggl\{1 + c ((q +4) \log 8)^s\biggr\}
{\bigl(\log m + \log \bigl(C {\cal D}(C)\bigr) +
\log \bigl(C \theta_M\bigr)\bigr)^s + \log(2/\gd) \over m}.  $$
This yields the stated bound for $\gep^*$ in the case (a).

(b) If (\ref{coveringsob}) is true, then the function defined by
$$ \widetilde{F} (\gep) := c {\bigl(q2^{q+4}\bigr)^s
\bigl\{\bigl(2 C {\cal D}(C)\bigr)^{s/2}
+ \bigl(2 C \gep\bigr)^{s/2}\bigr\} \over \gep^s}
-{3 m \gep \over 2^{q +9}} $$
satisfies $\widetilde{F} (\gep^*) \ge \log(\gd/2)$. Since $\widetilde{F}$
is a decreasing function, $\gep^* \le \widetilde{\gep}^*$ whenever
$\widetilde{F}(\widetilde{\gep}^*) \le \log(\gd/2)$.

If $\widetilde{\gep}^* \ge r m^{-1/(s+1)}
\bigl(2 C {\cal D}(C)\bigr)^{s/(2 s +2)} \log{2 \over \gd}$ with
\begin{equation}
r \ge 2^{q +8} \widetilde\kappa^{-s/(s+1)} + q 2^{q +10}
c^{1/(s+1)}/\log 2, \label{conditionone}
\end{equation}
then
$$c \bigl(q2^{q+4}\bigr)^s {\bigl(2 C {\cal D}(C)\bigr)^{s/2}
\over (\widetilde{\gep}^*)^s}
-{m \widetilde{\gep}^* \over 2^{q +8}} \le {r m^{s/(s+1)} \over
2^{q +8}} \bigl(2 C {\cal D}(C)\bigr)^{{s \over 2 s +2}} \log{2
\over \gd} \biggl\{{c \bigl(q2^{q+4}\bigr)^s 2^{q +8} \over
\bigl(r \log (2/\gd)\bigr)^{s+1}} -1\biggr\}. $$
Since $r \ge q
2^{q +10} c^{1/(s+1)}/\log 2$, according to Proposition
\ref{prop1.2}, this can be bounded by
$$ {r \over 2^{q +8}} m^{s/(s+1)} \bigl(2 C {\cal D}(C)\bigr)^{s/(2 s +2)}
\log{2 \over \gd} \biggl\{-{1 \over 2}\biggr\}
\le {r \over 2^{q +9}} \widetilde\kappa^{s/(s +1)}
\log {\gd\over 2} \le {1 \over 2} \log {\gd\over 2}. $$
Here we have used the condition $r \ge 2^{q +8} \widetilde\kappa^{-s/(s+1)}$.

In the same way, if $\widetilde{\gep}^* \ge r m^{-2/(s+2)} \bigl(2
C\bigr)^{s/(s +2)} \log{2 \over \gd}$ with
\begin{equation}r \ge
2^{q +9} + q^2 4^{q +5} c^{2/(s+2)}/\log 2,
\label{conditiontwo}
\end{equation}
we have for $C\ge 1/2$,
$$c \bigl(q2^{q+4}\bigr)^s \left({2 C \over \widetilde{\gep}^*}\right)^{s/2}
-{m \widetilde{\gep}^* \over 2^{q +9}}
\le {1 \over 2} \log {\gd\over 2}. $$

Combining the above two bounds, we obtain the desired estimate
(\ref{errorsob}) with $\widetilde{c}$ determined by the two
conditions (\ref{conditionone}) and (\ref{conditiontwo}). The
proof of Proposition \ref{prop2.1} is complete. \hfill\BlackBox

In the general case, the following bounds hold.

\begin{corollary}\label{cor5.2}
For every $0<\gd \le 1$, with
confidence at least $1-\gd$ there holds
$${\cal E}\bigl(\pi (f_{\bf z})\bigr) - {\cal E}(f_q) \le 2
\max\biggl\{ {2^{q +1}\biggl(1+\kappa\sqrt{2C \widetilde{{\cal
D}}(C)}\biggr)^{q/2} \sqrt{\log(2/\gd)} \over \sqrt{m}},
\gep^*\biggr\} +2 \widetilde{{\cal D}}(C), $$
where $\gep^*$ is
the solution to the equation
\begin{equation} \log {\cal N}
\biggl({\gep^{3/2} \over q 4^{q+2} \sqrt{2 C}}\biggr)- {3 m \gep^2
\over 4^{q + 5}}=\log {\gd \over 2}.
\label{generalcov}
\end{equation}
\end{corollary}

\begin{proof} Take $\gb =1$ and $f_{K, C} = \widetilde{f}_{K, C}$. By
Lemma \ref{lem4.2}, $\|\widetilde{f}_{K, C}\|_\infty \le 1 + 2
\kappa \sqrt{2 C \widetilde{{\cal D}}(C)}$ and we can take $M= 2^q
(1+ \kappa \sqrt{2 C \widetilde{{\cal D}}(C)})^q$. Also, $\gD =
\widetilde{{\cal D}} (C) + {\cal E}(f_q) \le 1$. It follows that
$\gS \le  \sqrt{2 C} (\gD + \gep)\le \sqrt{2 C} (1+ \gep)$.

Since ${\cal E}\bigl(\pi (f_{\bf z})\bigr) \le 2^q$,
we only need to consider the range $\gep \le 2^q$ to
bound $\gep(\gd, m, C, \gb)$. In this range,
$$ {\cal
N}\biggl({\gb( \gep + \widetilde{{\cal D}}(C))^{3/2} \over
q 2^{q+3}\gS}\biggr) \le {\cal N} \left({\gep^{3/2} \over q 4^{q +2}
\sqrt{2 C}}\right). $$
Then $F(\gep)$ can be bounded by
$$ \exp\biggl\{-{m \gep^2 \over 4^{q+1}
\bigl(1+\kappa \sqrt{2C \widetilde{{\cal D}}(C)}\bigr)^q}\biggr\}
+ {\cal N} \biggl({\gep^{3/2} \over q 4^{q+2} \sqrt{2 C}}\biggr)
\exp \biggl\{-{3 m \gep^2 \over 4^{q + 5}}\biggr\}. $$
Thus
$F(\gep) \le \gd$ if
$$ \gep \ge \max\biggl\{ {2^{q +1}(1+\kappa\sqrt{2C \widetilde{{\cal D}}(C)})^{q/2}
\sqrt{\log(2/\gd)} \over \sqrt{m}}, \gep^*\biggr\}$$
where
$\gep^*$ is the solution to the equation (\ref{generalcov}). This
together with Theorem \ref{thm3} yields the desired estimate.
\end{proof}

The bound for the sample error derived in Corollary \ref{cor5.2}
may be further improved by the well developed empirical process
techniques in the literature. We shall discuss this elsewhere.

The total error (\ref{decomerror}) consists of two parts. We shall
not discuss the possibility of further improving the sample error
bound here, because it is of the same importance to understand the
regularization error. This becomes more important when not much
estimate is available for the regularization error. In the
previous sections, we could compute ${\cal D}(C)$ explicitly only
for special cases. Most of the time, $\rho$ is not strictly
separable, even not weakly separable. Hence it is desirable to
estimate ${\cal D}(C)$ explicitly for general distributions. In
the following we shall choose $f_{K, C} = \widetilde{f}_{K, C}$
and estimate $\widetilde{{\cal D}}(C)$.


\section{Error Analysis by Approximation in $L^q$ Spaces}

The main result on the convergence analysis given in Section 5
enables us to have some nice observations. These follow from facts
on approximation in $L^q$ spaces.

\begin{lemma}\label{lem6.1}
If $1<q \le 2$, then
$$ (1 + u)_+^q \le 1 + |u|^q + q u, \qquad \forall u\in \RR. $$
\end{lemma}

\begin{proof} Set the continuous function
$f(u):= 1 + |u|^q + q u - (1 + u)_+^q$. Then $f(0)=0$.

Since $0<q-1 \le 1$, for $u>0$ we have
$$ f' (u) = q \left(1 + u^{q-1} - (1 + u)^{q-1}\right) \ge 0. $$
Hence $f(u) \ge 0$ for $u\ge 0$.

For $-1<u <0$, we see that
$$ f'(u) = q \left(1 - (-u)^{q-1} - (1 +u)^{q-1}\right) =
q \left(1 - |u|^{q-1} - (1 - |u|)^{q-1}\right) \le 0. $$
Hence $f(u) \ge 0$ for $-1<u<0$.

Finally, when $u< -1$, there holds
$$ f' (u) = q \left(1 - (-u)^{q-1}\right) \le 0. $$
Therefore, we also have $f (u) \ge f(-1) \ge 0$ for $u\le -1$.

Thus $f(u) \ge 0$ on the whole real line and Lemma \ref{lem6.1} is
proved.
\end{proof}

\begin{theorem} \label{thm4}
Let $f: X \to \RR$ be measurable. Then
$${\cal E}(f) - {\cal E}(f_q) \le \left\{\begin{array}{ll}
\|f-f_q \|_{L^q_{\rho_X}}^{q}, & \hbox{ if }1<q \le 2,\\ q 2^{q-1}
\|f-f_q \|_{L^q_{\rho_X}} \left( 2^{q-1} + \|f-f_q
\|_{L^q_{\rho_X}}^{q-1}\right), & \hbox{ if } q>2.
\end{array}\right. $$
\end{theorem}

\begin{proof} Since $|f_q (x)| \le 1$, by the second inequality of
Lemma \ref{lem5.1}, for each $x\in X$ we have
\begin{eqnarray*}
{\cal E}(f|x) - {\cal E}(f_q|x) & \displaystyle =
\int_Y (1 - y f(x))_+^q - (1 - y f_q (x))_+^q d \rho (y|x) \qquad \\ &\le
q 4^{q-1} |f(x) - f_q (x)| + q 2^{q-1} |f(x) - f_q (x)|^q.
\end{eqnarray*} 
It follows that
$$ {\cal E}(f) - {\cal E}(f_q) = \int_X {\cal E}(f|x) - {\cal E}(f_q|x) d \rho_X
\le q 4^{q-1} \|f-f_q \|_{L^1_{\rho_X}}
+ q 2^{q-1} \|f-f_q \|_{L^q_{\rho_X}}^q. $$
Then the inequality for the case $q>2$ follows from the H\"older inequality.

Turn to the case $1< q \le 2$. It is sufficient to show that for
each $x\in X$,
\begin{equation} {\cal E}(f|x) - {\cal E}(f_q|x)
\le |f(x) - f_q (x)|^q. \label{ineqsmall}
\end{equation} The
definition (\ref{regV}) of $f_q$ tells us that
$$ (1 + f_q (x))^{q-1} = {2^{q-1} (1 + f_\rho (x)) \over
\{(1 + f_\rho (x))^{1/(q-1)} + (1 - f_\rho (x))^{1/(q-1)} \}^{q-1}} $$
and
$$ (1 - f_q (x))^{q-1} = {2^{q-1} (1 - f_\rho (x)) \over
\{(1 + f_\rho (x))^{1/(q-1)} + (1 - f_\rho (x))^{1/(q-1)}
\}^{q-1}}. $$ These expressions in connection with (\ref{diffexp})
imply
$${\cal E}(f|x) = {(1 + f(x))_+^q (1 - f_q (x))^{q-1} \over
(1 + f_q (x))^{q-1} + (1 - f_q (x))^{q-1}} +
 {(1 - f(x))_+^q (1 + f_q (x))^{q-1} \over
(1 + f_q (x))^{q-1} + (1 - f_q (x))^{q-1}} $$
and together with
(\ref{usesmall})
$${\cal E}(f_q|x) = {2 (1 - f_q (x))^{q-1} (1 + f_q (x))^{q-1} \over
(1 + f_q (x))^{q-1} + (1 - f_q (x))^{q-1}}. $$
Thus
(\ref{ineqsmall}) follows from the following inequality (by taking
$t= f(x)$ and $\theta=f_q (x)$):
\begin{equation}
\begin{array}{l}\displaystyle{(1 + t)_+^q (1 - \theta)^{q-1} \over (1 +
\theta)^{q-1} + (1-\theta)^{q-1}} + {(1 - t)_+^q (1 +
\theta)^{q-1} \over (1 + \theta)^{q-1} + (1-\theta)^{q-1}} \\
\qquad\qquad\displaystyle  - 2 {(1 - \theta)^{q-1} (1 +
\theta)^{q-1} \over (1 + \theta)^{q-1} + (1-\theta)^{q-1}} \le
|t-\theta|^q, \qquad \forall t\in\RR, \theta\in (-1,
1).\end{array}\label{claimsmall}
\end{equation}

What is left is to verify the inequality (\ref{claimsmall}). Since
$-1<\theta <1$, we have
$$ (1 + t)_+^q (1 - \theta)^{q-1} = (1 - \theta^2)^{q-1}
(1 + \theta) \left({1 + t \over 1 + \theta}\right)_+^q = (1 -
\theta^2)^{q-1} (1 + \theta) \left(1 + {t- \theta \over 1 +
\theta}\right)_+^q. $$
By Lemma \ref{lem6.1} with $u=
(t-\theta)/(1 + \theta)$, we see that
$$ (1 + t)_+^q (1 - \theta)^{q-1} \le (1 - \theta^2)^{q-1}
(1 + \theta) \left(1 + \left|{t- \theta \over 1 + \theta}\right|^q
+ q {t- \theta \over 1 + \theta}\right). $$
In the same way, by
Lemma \ref{lem6.1} with $u=-(t-\theta)/(1 - \theta)$, we have
$$ (1 - t)_+^q (1 + \theta)^{q-1} \le (1 - \theta^2)^{q-1}
(1 - \theta) \left(1 + \left|{t- \theta \over 1 - \theta}\right|^q
- q {t- \theta \over 1 - \theta}\right). $$
Combining the above
two estimates, we obtain
$$ (1 + t)_+^q (1 - \theta)^{q-1} + (1 - t)_+^q (1 + \theta)^{q-1}
\le 2 (1 - \theta^2)^{q-1} + |t -\theta|^q \left\{(1 -
\theta)^{q-1} + ( 1 + \theta)^{q-1}\right\}. $$
This proves our
claim (\ref{claimsmall}), thereby Theorem \ref{thm4}. \end{proof}

Recall the $K$-functional given by (\ref{Kfunctional}).

\begin{theorem}\label{thm5}
For each $C>0$, there holds
$$ \widetilde{{\cal D}}(C)\le {\cal K}(f_q, {1 \over 2 C}). $$
\end{theorem}

\begin{proof} The case $1<q\le 2$ is an easy consequence of Theorem \ref{thm4}.

Turn to the case $q>2$. The special choice $f= 0 + 0 \in
\overline{{\cal H}}_K$ and the fact $\|f_q \|_{L^q_{\rho_X}} \le
1$ tell us that for any $t>0$,
$$ {\cal K}(f_q, t)= \inf_{{f\in \overline{{\cal H}}_K}\atop{\|f - f_q \|_{L^q_{\rho_X}} \le
1}}\left\{q 2^{q-1} (2^{q-1} + 1) \|f-f_q \|_{L^q_{\rho_X}} + t
\|f^*\|_K^2 \right\}. $$
According to Theorem \ref{thm4}, for
$f\in \overline{{\cal H}}_K$ with $\|f - f_q \|_{L^q_{\rho_X}} \le
1$, we have
$$ {\cal E}(f) - {\cal E}(f_q) \le q 2^{q-1} (2^{q-1} + 1)
\|f-f_q \|_{L^q_{\rho_X}}. $$
Thus,
$$ \widetilde{{\cal D}} (C)=\inf_{f\in \overline{{\cal H}}_K}
\left\{ {\cal E}(f) - {\cal E}(f_q) + {1 \over 2 C} \|f^*\|_K^2
\right\} \le {\cal K}(f_q, {1 \over 2 C}) $$
and the proof of
Theorem \ref{thm5} is complete. \end{proof}

We can now derive several observations from Theorem \ref{thm5}.

The first observation says that the SVM $q$-classifier
converges when $f_q$ lies in the closure of $\overline{{\cal
H}}_K$ in $L^q_{\rho_X}$. In particular, for any Borel probability
measure $\rho,$ this is always the case if $K$ is a universal
kernel since $C(X)$ is dense in $L^q_{\rho_X}.$

\begin{corollary}\label{cor6.1}
If $f_q$ lies in the closure of
$\overline{{\cal H}}_K$ in $L^q_{\rho_X}$, then for every $\gep
>0$ and $0<\delta<1$, there exist $C_\gep>0,$ $m_0\in\NN$ and a sequence
${C_m}$ with $\lim\limits_{m\to \infty} C_m=\infty$ such that
$$ \hbox{\rm Prob}_{{\bf z} \in Z^m} \left\{{\cal R}(\hbox{sgn}(f_{\bf z})) - {\cal R}(f_c)
 \le \gep\right\} \ge 1-\delta, \qquad \forall m\ge m_0, \ C_\gep\le C\le C_m.$$
\end{corollary}

\begin{proof} Since $f_q$ lies in the closure of $\overline{{\cal H}}_K$ in
$L^q_{\rho_X}$, for every $\gep >0$ there is some $f_{\gep} =
f_\gep^* +b_\gep \in \overline{{\cal H}}_K$ such that $q 2^{q}
(2^{q-1} +1) \|f_\gep -f_q \|_{L^q_{\rho_X}} \le \gep^2 /16$. Take
$C_\gep = 8 \|f^*_\gep\|_K^2/\gep^2$. Then for any $C\ge C_\gep$,
we have ${1 \over 2C} \|f_{\gep}^*\|_K^2 \le \gep^2 /16$. Theorem
\ref{thm5} tells us that $\widetilde{{\cal D}}(C) \le \gep^2/8$.

Take $m_0$ such that
$${2^{q +1}(1+\kappa\sqrt{2C_\gep})^{q/2} \sqrt{\log(2/\gd)}
\over \sqrt{m_0}} \le {\gep^2\over 8}$$
and
$$ \log {\cal N} \left({\gep^{3} \over
q 4^{q
+4} \sqrt{2 C_\gep}}\right)-{3 m_0 \gep^4 \over 4^{q + 8}}\le
\log {\gd \over 2}. $$
Also, we choose $C_m$ such that
$$ {2^{q +1}(1+\kappa\sqrt{2C_m})^{q/2} \sqrt{\log(2/\gd)} \over \sqrt{m}}<{\gep^2\over 8}$$
and
$$ \log {\cal N} \left({\gep^{3} \over
q 4^{q +4} \sqrt{2 C_m}}\right)-{3 m \gep^4 \over 4^{q + 8}}\le
\log {\gd \over 2}.$$ Then by Corollary 5.2, $\gep(\gd, m, C,
\gb)\le {\gep^2\over 8}$ when $m\ge m_0$ and $C_\gep\le C\le C_m$.
Together with Theorem \ref{prop3.1}, our conclusion is
proved.\end{proof}

Our second observation from Theorem \ref{thm5} concerns
nonuniversal kernels which nonetheless ensures the convergence of
the SVM $q$-classifier. The point here is that ${\cal H}_K$ is not
dense in $C(X)$, but after adding the offset the space
$\overline{{\cal H}}_K$ becomes dense.

\begin{example}\label{example6.1}
Let $K$ be a Mercer kernel on $X=[0,
1]$:
$$ K(x, y) = \sum_{j\in J} a_j (x \cdot y)^j, $$
where $J$ is a subset of $\NN$, $a_j >0$ for each $j\in J$, and
$\sum\limits_{j\in J} a_j <\infty.$ Note that this  kernel
satisfies $K_0 (y) \equiv 0$, hence $f(0)=0$ for all $f\in {\cal
H}_K$. Hence the space ${\cal H}_K$ is not dense in $C(X)$ and $K$
is not an universal kernel. But if $\sum\limits_{j\in J} {1 \over
j} = \infty$, then  $\overline{{\cal H}}_K$ is dense in $C(X)$
(Zhou 2003a) and hence in $L^q_{\rho_X}$. Therefore, the SVM
$q$-classifier associated with the (identical) kernel $K$
converges.
\end{example}

\begin{remark} In Section 4 and the proof of Theorem \ref{thm3}, we
have shown how the offset influences the sample error. Proposition
\ref{prop1.2} and Example \ref{example6.1} tell that it may also
influence the approximation error. However, our analysis in the
following two sections will not focus on this point and it may be
an interesting topic.
\end{remark}

In practical applications, one can use varying kernels for
(\ref{svmone}).

\begin{definition}\label{defn6.1}
Let $\{K_d\}_{d\in\NN}$ be a
sequence of Mercer kernels on $X$. We say that the SVM
$q$-classifier associated with the kernels $\{K_d\}$ {\it
converges} if for a sequence $\{C_m\}_{m\in\NN}$ of positive
numbers, $f_{\bf z}$ defined by (\ref{svmone}) with $K=K_d$ and
$C=C_m$ satisfies the following:

{\sl For every Borel probability measure $\rho$ on $Z$, and
$0<\gd<1$, $\gep>0$, for sufficiently large $d$ there is some $m_d
\in\NN$ such that}
$$\hbox{\rm Prob}_{{\bf z} \in Z^m}
\left\{{\cal R}(\hbox{\rm sgn}(f_{\bf z})) - {\cal R}(f_c) \le
\gep \right\} \ge 1- \gd, \qquad \forall m \ge m_d. $$
\end{definition}

For a universal kernel $K$, one may take $K_d$ to be identically
$K$ and the convergence holds. But the kernels could change such
as the polynomial kernels (Boser, Guyon and Vapnik, 1992). Our
third observation from Theorem \ref{thm5} is to confirm the
convergence of the SVM $q$-classifiers with these kernels.

\begin{proposition}\label{prop6.1}
For any $1<q<\infty, n\in\NN$ and
$X \subset \RR^n$, the SVM $q$-classifier associated with
$\{K_d\}_{d=1}^\infty$, the polynomial kernels $K_d (x, y)=(1 + x
\cdot y)^d$, converges.
\end{proposition}

Proposition \ref{prop6.1} is a consequence of a quantitative
result below.

Let $P_d$ be the space of all polynomials of degree at most $d$.
It is a RKHS ${\cal H}_{K_d}$ with the Mercer kernel $K_d (x, y) =
(1 + x \cdot y)^d$. The rich knowledge from approximation theory
tells us that for an arbitrary Borel probability measure on $Z$,
there is a sequence of polynomials $\{p_d \in P_d\}_{d=1}^\infty$
such that $\lim\limits_{d\to\infty} \|f_q - p_d\|_{L^q_{\rho_X}}
=0$. The rate of this convergence depends on the regularity of the
function $f_q$ (hence the function $f_\rho$) and the marginal
distribution $\rho_X$. With this in hand, we can now state the
result on the convergence of the $q$-classifier with polynomial
kernels $K_d$.

\begin{corollary}\label{cor6.2}
Let $X \subset \RR^n$, and $\rho$ be
an arbitrary Borel probability measure on $Z$. Let $d\in\NN$ and
$K_d (x, y) = (1 + x \cdot y)^d$ be the polynomial kernel. Set
$\|X\|:=\sup\limits_{x\in X} |x|$. Let $\{p_d \in
P_d\}_{d=1}^\infty$ satisfy $E_d:=\|f_q - p_d\|_{L^q_{\rho_X}} \to
0$ (as $d\to\infty$). Set $N:= (n +d)!/(n! d!)+1$ and $0<\gs <{2
\over q}$. Then there exists $m_{q, \gs} \in\NN$ such that for $m
\ge m_{q, \gs}$ and $C=m^\gs$, for every $0<\gd <1$, with
confidence $1-\gd$ there holds
$$ {\cal R}(\hbox{\rm sgn}(f_{\bf z})) - {\cal R}(f_c) \le \sqrt{q} 2^{q+1}
\sqrt{E_d} + {\|p_d\|_{K_d} \over m^{\gs/2}} + {
2^{q+5}\bigl(N\log{({2\over \delta })} \bigr)^{1/4}
(1+\|X\|^2)^{qd/8} \over m^{{1 \over 4} - {q \gs \over 8}}}.$$
\end{corollary}

\begin{proof} Take $p_d^* = p_d$ with zero offset in the $K$-functional.
Then by Theorem \ref{thm5},
$$ \widetilde{{\cal D}}(C) \le {\cal K}(f_q, {1 \over 2 C})
\le q 2^{q-1} (2^{q-1} + 1) E_d + {1 \over 2 C} \|p_d\|_{K_d}^2.
$$

The covering numbers of the finite dimensional space $P_d$  (e.g.
Cucker and Zhou, 2004) and (\ref{defcoveringnumber}) give us the
estimate:
$$ {\cal N} (\eta)
\le ({\kappa+{ 1\over{ \tilde{\kappa} }}})\left({2 \over
\eta} +1\right)^N,
$$
where $N-1=(n +d)!/(n! d!)$ is the dimension
of the space $P_d
(\RR^n)$. Also, $\kappa = \sqrt{\|K_d\|_\infty} \le (1 +
\|X\|^2)^{d/2}$.

Take $C= m^\gs$. By Corollary \ref{cor5.2}, solving the equation
(\ref{generalcov}) yields
$$ \gep(\gd, m, C, \gb) \le { \bigl(2^{q+5} \sqrt{N} +
\sqrt{\log (\kappa+ {1 \over \tilde{\kappa}})} \bigl(\log m + \log
(2/\gd)\bigr)^{1/2} \over \sqrt{m}} + {{4^{q+2}\kappa^{ { q\over
2}} \sqrt{\log({2\over \delta }) }} \over { m^{{1\over
2}-{{q\gs}\over{4}}}}} $$
which is bounded by
$4^{5+q}\sqrt{N\log{({2\over \delta })}}\kappa^{q/2} m^{{q \gs
\over 4}- {1 \over 2}}$ for $m\ge m_{q, \gs}$. Here $m_{q, \gs}$
is an integer depending on $q, \gs$ (but not on $m$, $d$ or
$\gd$). Then for each $m\ge m_{q, \gs}$, with confidence $1-\gd$
the desired estimate holds true. \end{proof}

\begin{remark} Note that $P_d$ is a finite dimension space.
Thus the norms $\|\cdot\|_{K_d}$ and $\|\cdot\|_{L^q_{\rho_X}}$
are equivalent for a fixed $d$ when $\rho_X$ is non-degenerate. It
would be interesting to compare the norm $\|p\|_{K_d}$ with
$\|p\|_{L^q_{\rho_X}}$ for $p\in P_d$ as $d$ tends to infinity.
\end{remark}

\noindent {\bf Proof of Proposition \ref{prop6.1}.} For every
$\gep >0$, there exists some $d_0 \in\NN$ such that $\sqrt{q}
2^{q-1} \sqrt{E_d} \le \gep/2$ for every $d\ge d_0$. Then by
Corollary \ref{cor6.2} we can find some $m_{q, \gs} \le m_d
\in\NN$ such that $m_d^{-\gs/2} \|p_d \|_{K_d} \le \gep /4$ and
$2^{q +5} \bigl(N \log (2/\gd)\bigr)^{1/4} (1 + \|X\|^2)^{d q/8}
m_d^{{q \gs \over 8}- {1 \over 4}} \le \gep/4$. Then for any $m\ge
m_d$ we have ${\cal R}(\hbox{sgn}(f_{\bf z})) - {\cal R}(f_c) \le
\gep$ with confidence $1-\gd$. This proves Proposition
\ref{prop6.1}.\hfill\BlackBox

\section{Rate of Convergence for the $q$-Norm Soft Margin
Classifier}

Corollary \ref{cor5.2} and Theorem \ref{thm5} enable us to get the
convergence rate for the SVM $q$-classifier. The rate depends on
the $K$-functional ${\cal K}(f_q, t)$. It can be characterized by
the quantity (Smale and Zhou 2003; Zhou 2003b)
\begin{equation} I_q
(g, R):= \inf_{{f\in \overline{{\cal H}}_K}\atop{ \|f^*\|_K \le
R}} \left\{\|g - f\|_{L^q_{\rho_X}}\right\}.
\label{approxerror}
\end{equation}
Define
$$ J_q (f_q, R):=\left\{
\begin{array}{ll}\left(I_q (f_q, R)\right)^q, & \hbox{ if }1<q \le 2, \\
q 2^{q-1} (2^{q-1} + 1) I_q (f_q, R), & \hbox{ if } q>2.
\end{array}\right.$$
Then the following corollary holds true.

\begin{corollary}\label{cor7.1}
For any $t>0$ there holds $${\cal
K}(f_q,t)\le \inf_{R>0} \big\{J_q(f_q,R)+tR^2\big\}.$$
\end{corollary}

One may choose appropriate $R$ to estimate the convergence rate of
${\cal K}(f_q,t)$, which together with Corollary \ref{cor5.2} gives the
convergence rate of the $V$-risk and a strategy of
choosing the regularization parameter $C$. In general,
the choice of $R$ depends on
the regularity of $f_q$ and the kernel $K.$ Let us demonstrate
this by examples.

In what follows let $X \subset \RR^n$ have Lipschitz boundary and
$\rho$ be a probability measure such that $d\rho_X=dx$ is the
Lebesgue measure. Consider $q=2$ and thus $f_q=f_\rho.$ We use
the approximation error studied in Smale and Zhou (2003) (see also
Niyogi and Girosi (1996) for related discussion):
$$ I^*_2 (g, R):= \inf_{{f^*\in {\cal H}_K}\atop{\|f^*\|_K \le R}}
\left\{\|g - f^*\|_{L^2}\right\} $$
to bound the term
$I_2(f_\rho,R).$ With the choice $b_f=0$ we obtain
$$I_2(f_\rho, R) \le I^*_2 (f_\rho, R).$$
Note that we disregard
the influence of the offset here and thus the rate need not be
optimal.

The first example includes spline kernels (Wahba 1990).

\begin{example}\label{example7.1}
Let $X \subset \RR^n$ and $K$ be a
Mercer kernel such that ${\cal H}_K$ is the Sobolev space $H^r(X)$
with $r>n/2.$ If $f_\rho$ lies in the Sobolev space $H^s(X)$ with
$0<s<r,$ then
$${\cal E}(\pi(f_{\bf z}))-{\cal E}(f_\rho)=O\left({\sqrt{\log m + C}
\over \sqrt{m}}+{C^{n/(4r+3n)}\over
m^{2r/(4r+3n)}}\right)+O\biggl(C^{-s/ r}\biggr).$$ Thus, $C$
should be chosen such that $C\to \infty$, $C/m\to 0$ as
$m\to\infty$.
\end{example}

\begin{proof} It was shown in Smale and Zhou (2003, Theorem 3.1) that for $0<\theta <1$,
$I^*_2 (f_\rho, R) =O(R^{-\theta/(1-\theta)})$ if and only if
$f_\rho$ lies in the interpolation space
$(L^2_{\rho_X}, {\cal H}_K)_{\theta,\infty}$. It is well known that
$H^s(X) \subset (L^2, H^r (X))_{s/r, \infty}$ for $0<s <r$.
Here ${\cal H}_K =H^r(X)$ and $d \rho_X = d x$. Therefore, the assumption
$f_\rho \in H^s (X)$ tells us that
$f_\rho \in (L^2_{\rho_X}, {\cal H}_K)_{s/r,\infty}$. Hence
there holds
$$I_2(f_\rho,R)\le
I_2^*(f_\rho,R)\le C_\rho R^{-s/(r-s)}$$
for some constant
$C_\rho.$ Choose $R=C_\rho^{(r-s)/r}C^{(r-s)/2r}$ to obtain
$${\cal K}(f_\rho,{1\over 2C})\le (I_2(f_\rho,R))^2+{R^2\over 2C}\le
{3\over 2}C_\rho^{2(r-s)/r}C^{-s/r}.$$
Using the well known
covering number estimates for Sobolev spaces
$$\log {\cal
N}(B_R, \eta) \le C_r\left(1\over \eta\right)^{n/r}$$
and solving
the equation (\ref{generalcov}), we see that
$$\gep^*\le 2^6 \sqrt{{\log \kappa +\log m +\log C + \log (2/\gd) \over
m}}+ 2^{6 + 3n/(4r)} \sqrt{C_r} {C^{n/(4r+3n)} \over
m^{2r/(4r+3n)}}.$$ This proves the conclusion. \end{proof}

\begin{example}\label{example7.2}
Let $\gs >0, s>0$ and $K$ be the
Gaussian kernel $ K(x, y) = \exp\left\{-{|x-y|^2 \over
\gs^2}\right\}. $
\begin{enumerate}
\item[{\rm (a)}] If $f_\rho$ lies in the interpolation space
$(L^2_{\rho_X}, {\cal H}_K)_{\theta,\infty}$ for some
$0<\theta<1,$ that is, ${\cal K}(f_\rho,t)\le C_\theta t^{\theta
}$ for some constant $C_\theta,$ then for any $0<\gd <1$, with
confidence $1-\gd$, there holds
$${\cal E}(\pi(f_{\bf z}))-{\cal E}(f_\rho)=O\left(
{\sqrt{C +(\log m)^{n+1}} \over \sqrt{m}}\right)
+O\biggl(C^{-\theta}\biggr).$$
This implies the parameter $C$ should be taken
to satisfy $C\to \infty$ and $C/m\to 0$ as $m\to \infty.$
An asymptotic optimal choice
is $C=O(m^{1/(1 + 2\theta)})$. With this choice, the convergence rate is
$O(m^{-\theta/(1+2 \theta)}).$
\item[{\rm (b)}] If $f_\rho\in H^s(X)$ with $s>0$, then for any
$0<\gd <1$, with confidence $1-\gd$, we have
$${\cal E}(\pi(f_{\bf z}))-{\cal E}(f_\rho)=O\left(
{\sqrt{C +(\log m)^{n+1}} \over \sqrt{m}}\right) +O\left((\log
C)^{-s/2}\right).$$
An asymptotically optimal choice is
$C=O\left({m \over (\log m)^{s}}\right)$ which gives the
convergence rate $O((\log m)^{-s/2}).$
\end{enumerate}
\end{example}

\begin{proof} Solving the equation (\ref{generalcov}) with the covering number
estimate (\ref{coveringanal}) yields
$$\varepsilon^* =O \biggl( {\sqrt{(1+c)(\log
C+\log m)^{n+1}} \over \sqrt{m}}\biggr).$$ Then the statement in
(a) follows easily from Corollary \ref{cor5.2}, Theorem \ref{thm3}
and Corollary \ref{cor7.1}.

To see the conclusion in (b), we notice that the assumption
$f_\rho \in H^s (X)$ provides the approximation error estimates
(Smale and Zhou, 2003; Zhou, 2003b)
$$I_2(f_\rho,R)\le I^*_2 (f_\rho, R) \le C_s \left(\log R\right)^{-s/4}$$
for every $R>C_s$,
where $C_s$ is a constant depending on $s, \gs, n$ and the Sobolev
norm of $f_\rho$. Choose $R=\sqrt{2C} \left(\log C\right)^{-s/4}$
to obtain
$${\cal K}(f_\rho, {1\over 2C})\le (I_2(f_\rho, R))^2+ {R^2\over 2C}
\le (2^sC_s^2+1)(\log C)^{-s/2}.$$ Then the desired bound follows
from Theorem \ref{thm5} and the above established bound for
$\gep^*$.
\end{proof}

It was shown in Smale and Zhou (2003) that for the Gaussian kernel
in Example \ref{example7.2}, $I_2^* (g, R) = O(R^{-\epsilon})$
with $\epsilon
>0$ only if $g$ is $C^\infty$. Hence logarithmic convergence rate
is expected for a Sobolev function $f_\rho$. However, in practice,
one often chooses the different variances $\gs$ of the Gaussian
kernel according to the different sample size $m$. With this
flexibility, the regularization error can be improved greatly and
polynomial convergence rates are possible.


\acks{The authors would like to thank
Professor Zhen Wang for his helpful discussion on the best
constants in Theorem \ref{prop3.1} and Theorem \ref{thm4}.
They are also grateful to the referees for the constructive
suggestions and comments.

This work is supported partially by the Research Grants Council of
Hong Kong [Project No. CityU 1087/02P] and by City University of
Hong Kong [Project No. 7001442]. The corresponding author is
Ding-Xuan Zhou. Yiming Ying is on leave from Institute of
Mathematics, Chinese Academy of Science, Beijing 100080, P. R.
CHINA.}

\appendix
\section{Error Comparison for a General Loss Function}
\label{generalloss}

In this appendix for a general convex loss function
we bound the excess misclassification error
by the excess $V$-risk.
Here the loss function takes the form
$$ V(y, f(x)) = \phi (y f(x))$$
for a univariate function $\phi: \RR \to \RR_+$.

For each $x\in X$, we denote
\begin{equation}{\cal E}(f|x):=\int_Y
V(y, f(x)) d \rho (y|x), \label{localerror}
\end{equation}
then
${\cal E}(f|x) = Q(\eta (x), f(x))$. Here $Q: [0, 1]\times (\RR
\cup \{\pm\infty\}) \to \RR_+$ is given by
$$ Q(\eta, f) = \eta \phi(f) + (1-\eta) \phi(-f), $$
and $\eta: X \to \RR$ is defined by $\eta (x) := P({\cal Y}=1|x)$.
Set
$$f_\phi^*(\eta) :=\arg\min_{f\in \RR \cup \{\pm\infty\}}
Q(\eta, f).$$
Then $f_\rho^V (x) = f_\phi^* (\eta (x))$. The main
result of Zhang (2004) can be stated as follows.

\medskip

\noindent{\bf Theorem A} {\it Let $\phi$ be convex. Assume
$f_\phi^*(\eta)
>0$ when $\eta >0.5$. Assume there exists $c>0$ and $s\ge 1$ such
that for all $\eta \in [0, 1]$,
\begin{equation} |0.5 - \eta|^s
\le c^s \left(Q(\eta, 0) - Q(\eta, f_\phi^*(\eta))\right),
\label{Zhangc}
\end{equation}
then for any measurable function
$f(x)$:}
$$ {\cal R}(\hbox{\rm sgn}(f)) - {\cal R}(f_c) \le 2 c \left({\cal E}(f) -
{\cal E}(f_\rho^V)\right)^{1/s}. $$

Further analysis was made by Bartlett, Jordan and McAuliffe (2003).
For example, it was proved in Bartlett, Jordan and McAuliffe (2003,
Theorem 6) that for a convex function $\phi$, $f_\phi^*(\eta) >0$
for any $\eta >0.5$ if and only if $\phi$ is differentiable at $0$
and $\phi' (0) <0$. Borrowing some ideas from Bartlett, Jordan and
McAuliffe (2003), we can derive a simple criterion for the
condition (\ref{Zhangc}) with $s=2$. The existence of $\phi'' (0)$
means that the function $\phi' (x)$ is well defined in a
neighborhood of $0$ and is differentiable at $0$. Note that the
convexity of $\phi$ implies $\phi'' (0) \ge 0$.

\begin{theorem}\label{thm2}
Let $\phi: \RR \to \RR_+$ be a convex
function such that $\phi'' (0)$ exists. If $\phi' (0) <0$ and
$\phi'' (0) >0$, then (\ref{Zhangc}) holds for $s=2$. Hence for
any measurable function $f$:
$$ {\cal R}(\hbox{\rm sgn}(f)) - {\cal R}(f_c) \le 2 c \sqrt{{\cal E}(f) -
{\cal E}(f_\rho^V)}. $$
\end{theorem}

\begin{proof} By the definition of $\phi'' (0)$, there exists some $1/2
\ge c_0 >0$ such that
$$\left|{\phi' (f) - \phi' (0) \over f} - \phi'' (0)\right| \le {\phi'' (0) \over 2},
\qquad \forall  f\in [-c_0, c_0]. $$ This implies
$$\phi' (0) + \phi'' (0) f - {\phi'' (0) \over 2} |f|
\le  \phi' (f) \le \phi' (0) + \phi'' (0) f + {\phi'' (0) \over 2} |f|. $$

If $\eta >1/2$, then for $0\le f \le c_0$,
$$ {\partial Q \over \partial f}(\eta, f) = \eta \phi' (f) - (1-\eta) \phi' (-f)
\le (2 \eta -1) \phi' (0) + \phi'' (0) f  + {\phi'' (0) \over 2} f. $$
Thus for $0\le f \le \gD_\eta:= \min\{{-\phi' (0) \over \phi'' (0)} (\eta - {1 \over 2}), c_0\}$,
we have
$$ {\partial Q \over \partial f}(\eta, f)  \le (2 \eta -1) \phi' (0) +
{3 \over 2} \phi'' (0) {-\phi' (0) \over \phi'' (0)} (\eta - {1
\over 2}) \le {\phi' (0) \over 2} (\eta - {1 \over 2}) <0. $$
Therefore as a function of the variable $f$, $Q(\eta, f)$ is
strictly decreasing on the interval $[0, \gD_\eta]$. But $f_\phi^*
(\eta)>0$ is its minimal point, hence
$$ Q(\eta, 0) - Q(\eta, f_\phi^*(\eta)) \ge
Q(\eta, 0) - Q(\eta, \gD_\eta) \ge -{\phi' (0) \over 2} (\eta - {1 \over 2}) \gD_\eta. $$
When ${-\phi' (0) \over \phi'' (0)} (\eta - {1 \over 2}) > c_0$, we have
$\gD_\eta = c_0 \ge 2 c_0 (\eta - {1 \over 2})$.
Hence
$$ Q(\eta, 0) - Q(\eta, f_\phi^*(\eta))
\ge {-\phi' (0) \over 2} \min\left\{2 c_0, {-\phi' (0) \over
\phi'' (0)}\right\}  (\eta - {1 \over 2})^2.  $$ That is,
(\ref{Zhangc}) holds with $s=2$ and
$$ c= \max\left\{{\sqrt{2 \phi'' (0)} \over - \phi' (0)},
\sqrt{{1 \over - \phi' (0) c_0}} \right\}. $$

The proof for $\eta <1/2$ is the same by estimating the upper
bound of ${\partial Q \over \partial f}(\eta, f)$ for $f<0$.
\end{proof}

Turn to the special loss function $V= V_q$ given in
(\ref{loss}) by $\phi(t) = (1-t)_+^q$. Applying Theorem \ref{thm2}, we see
that the function $\phi$ satisfies $\phi' (0) = -q<0$ and $\phi''
(0) = q (q-1) >0$. This verifies (\ref{compareVq}) and the constant
$c$ can be obtained from the proof of Theorem
\ref{thm2}.

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

\bibitem[Aronszajn (1950)]{Aron} N. Aronszajn. 
Theory of reproducing kernels. {\it Trans. Amer. Math. Soc.} {\bf 68}
(1950), 337--404, 1950.

\bibitem[Barron (1990)] {Bar} A. R. Barron. Complexity regularization with
applications to artificial neural networks.  G. Roussa, editor,
   in {\it Nonparametric Functional Estimation}, Kluwer, Dortrecht,
    pages 561--576, 1990.

\bibitem[Bartlett (1998)] {Bartlett} P. L. Bartlett. The sample complexity of
pattern classification
   with neural networks: the size of the weights is more important than the size
   of the network. {\it IEEE Transactions on Information Theory}, {\bf 44}:  525--536, 1998.

\bibitem[Bartlett et al (2002)] {BBM} P. L. Bartlett, O. Bousquet, and S. Mendelson. Local
Rademacher complexities. {\it Annals Statis.}, 2004, to appear.

\bibitem [Bartlett et al (2003)] {BMM} P. L. Bartlett, M. I. Jordan, and J. D. McAuliffe. 
Convexity, classification, and risk bounds. Preprint, 2003.

\bibitem[Boser et al (1992)] {BGV} B. E. Boser, I. Guyon, and V. Vapnik. A training
algorithm for optimal
   margin classifiers. In {\it Proceedings of the Fifth Annual Workshop of
   Computational Learning Theory}, {\bf 5}, Pittsburgh, ACM, pages 144--152, 1992.

\bibitem[Bousquet et al (2002)] {BouE} O. Bousquet and  A. Elisseeff. Stability and
generalization. {\it Journal of Machine Learning Research}, {\bf 2}:  499--526, 2002.

\bibitem[Cortes et al (1995)]{CV} C. Cortes and V. Vapnik. Support-vector networks. 
{\it Machine Learning},  {\bf 20}:  273--297, 1995.

\bibitem[Cristianini et al (2000)]  {CSh} N. Cristianini and J. Shawe-Taylor. 
{\it An Introduction
to Support Vector Machines}. 
   Cambridge University Press, 2000.

\bibitem[Cucker Smale (2001)] {CS} F. Cucker and S. Smale. On the mathematical
foundations of learning. {\it  Bull. Amer. Math. Soc.}, {\bf
39}:  1--49, 2001.

\bibitem[Cucker Zhou (2004)] {CuZ} F. Cucker and D. X. Zhou. {\it Learning Theory: An
Approximation Theory Viewpoint}.
  Monograph manuscript in preparation for Cambridge University Press, 2004.

\bibitem[DGL (1997)] {DGL} L. Devroye, L. Gy\"orfi, and G. Lugosi. {\it A
Probabilistic Theory of Pattern Recognition}. 
   Springer-Verlag, New York, 1997.

\bibitem[EPP (2000)] {EPP} T. Evgeniou, M.
Pontil, and T. Poggio. Regularization networks and support vector
machines.
 {\it  Adv. Comput. Math.}, {\bf 13}:  1--50, 2000.

\bibitem[LBW (1998)] {LBW} W. S. Lee, P. Bartlett, and R. Williamson. The
importance of convexity in learning with least square loss. {\it
IEEE Transactions on Information Theory}, {\bf 44}: 1974--1980, 1998.

\bibitem[Lin (2002)] {Linone} Y. Lin. Support vector machines and the Bayes
rule in classification. {\it  Data Mining and Knowledge Discovery}
{\bf 6}: 259--275,  2002.

\bibitem[Mendelson (2002)] {Mendel} S. Mendelson. Improving the sample complexity
using global data. {\it IEEE Transactions on Information Theory} {\bf 48}:
1977--1991,  2002.

\bibitem[MRP (2002)] {MRP} S. Mukherjee, R. Rifkin, and T. Poggio. 
   Regression and classification with regularization. In D. D. Denison,
   M. H. Hansen, C. C. Holmes, B. Mallick, and B. Yu, eds., {\it Lecture Notes in Statistics:
   Nonlinear Estimation and Classification},
   Springer-Verlag, New York, pages 107--124, 2002.

\bibitem[Niyogi et al (1996)] {NG} P. Niyogi and F. Girosi. On the relationship between
generalization error,
   hypothesis complexity, and sample complexity for radial basis functions.
    {\it  Neural Comp.}, {\bf 8}: 819--842,  1996.

\bibitem[Pontil (2003)] {Pontil} M. Pontil. A note on different covering numbers
in learning theory. {\it  J. Complexity} {\bf 19}: 665--671, 2003.

\bibitem[Rosenblatt (1962)] {Rosen} F. Rosenblatt. {\it Principles of Neurodynamics}.
Spartan Book, New York, 1962.

\bibitem[SBWA (1998)] {SBWA} J. Shawe-Taylor, P. L. Bartlett,
R. C. Williamson, and M. Anthony. 
   Structural risk minimization over data-dependent hierarchies. {\it IEEE Transations on Information Theory}
   {\bf 44}: 1926--1940, 1998.

\bibitem[Smale Zhou (2003)] {SZ} S. Smale and D. X. Zhou. Estimating the approximation
error in learning theory. {\it Anal. Appl.},  {\bf 1}: 17--41,
2003.

\bibitem[Smale Zhou (2004)] {SZtwo} S. Smale and D. X. Zhou. Shannon sampling and
function reconstruction from point values. {\it Bull. Amer.
Math. Soc. },   {\bf 41}: 279--305,  2004.

\bibitem[Steinwart (2001)] {Steintwo} I. Steinwart. On the influence of the kernel on
the consistency of support vector machines. {\it Journal of
Machine Learning Research}, {\bf 2}:  67--93, 2001.

\bibitem[Steinwart (2002)] {Steinw} I. Steinwart. Support vector machines are
universally consistent. {\it J. Complexity},  {\bf 18}:
768--791, 2002.

\bibitem[Tikhonov et al (1977)] {Tik} A. Tikhonov and V. Arsenin. {\it Solutions of Ill-posed
Problems}. W. H. Winston, 1977.

\bibitem[Vaart et al (1996)] {Vaart} A. W. van der Vaart and J. A. Wellner. { \it Weak
Convergence and Empirical Processes}. Springer-Verlag, New York,
1996.

\bibitem[Vapnik (1982)] {Vapone} V. Vapnik. {\it Estimation of Dependences Based on
Empirical Data}. Springer-Verlag, New York, 1982.

\bibitem[Vapnik (1998)] {Vaptwo} V. Vapnik. {\it Statistical Learning Theory}. John
Wiley and Sons, 1998.

\bibitem[Wahba (1990)]{Wa} G. Wahba. {\it Spline models for observational data}. SIAM,
1990.

\bibitem[Wahba (1999)] {Wahbatwo} G. Wahba. Support vector machines, reproducing
kernel Hilbert spaces
   and the Randomized GACV. In Sch\"olkopf, Burges and Smola, eds.,
   {\it Advances in Kernel Methods - Support Vector Learning},
    MIT Press, pages 69--88, 1999.

\bibitem[Williamson et al (2001)] {WSS} R. C. Williamson, A. J. Smola, and B. Sch\"olkopf.
Generalization performance of regularization networks and support 
vector machines via entropy numbers of compact operators. 
{\it  IEEE Transactions on Information Theory} {\bf 47}: 2516--2532,  2001.

\bibitem[WuZhou (2004)] {Wuzhou} Q. Wu and D. X. Zhou. Analysis of support vector
machine classification. Preprint, 2004.

\bibitem[Zhang (2004)] {Zhang} T. Zhang. Statistical behavior and consistency of
classification methods based on convex risk minimization. {\it
Annals Statis.}, {\bf 32}:  56--85, 2004.

\bibitem[Zhou (2002)] {Zhou} D. X. Zhou. The covering number in learning theory.
{\it J. Complexity}, {\bf 18}: 739--767,  2002.

\bibitem[Zhou  (2003)] {Zhoucap} D. X. Zhou. Capacity of reproducing kernel
spaces in learning theory. {\it IEEE Transactions on Information Theory}, {\bf
49}: 1743--1752,  2003a.

\bibitem[Zhou (2003b)] {Zhoudensity} D. X. Zhou. Density problem and approximation
error in learning theory. Preprint, 2003b.

\end{thebibliography}

\end{document}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%% Support vector machine soft-margin classifiers  %%%%%%%
%%%%%%%      July 19, 2004 %%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\begin{eqnarray}
%f_{\bf z} &:=\displaystyle\arg\min_{f\in \overline{{\cal H}}_K}
%\quad {1 \over 2} \|f^*\|_K^2 +
%{C \over m} \sum_{i=1}^m \xi_i^q, \nonumber\\ & \quad \hbox{subject to} \quad y_i
%f(x_i) \ge 1 - \xi_i,  \label{svmone}\\ & \qquad  \xi_i \ge 0, \qquad i=1,
%\ldots, m.  \nonumber
%\end{eqnarray}

$$ \psi (\theta) =\frac{1}{2}
\left(1- 2^{q-1} (1 + \theta)(1 - \theta) \left(\left(\frac{1 +
\theta}{2}\right)^{1/(q-1)} + \left(\frac{1 -
\theta}{2}\right)^{1/(q-1)}\right)^{1-q}\right). $$ 

For a single function $f$ with $f^*$
lying in the set
\begin{equation}B_R = \{f^* \in {\cal H}_K:
\|f^*\|_K \le R\}, \label{BRset}
\end{equation}
the projection
operator $\pi$ improves the bound for the random variable:
\begin{equation}
V(y,\pi(f)(x)) \le 2^q, \quad \hbox{while } V(y,f(x)) \le
2^q(1+\kappa R)^q, \qquad \forall f^*\in B_R.
\label{boundcompare}
\end{equation}
In the error analysis, $R=R(C)$
increases as $C$ and in general, $\lim\limits_{C\to \infty} R(C) =
\infty$. Hence the exponential term in the sample error estimates
is greatly improved for a single function $f$. Since $f_{\bf z}$
changes with the random sample ${\bf z}$, our technique can be
used to improve the sample error estimates, at least when the ball
$B_R$ of ${\cal H}_K$ has small complexity.
