\documentclass[twoside,11pt,letter]{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}
\usepackage{amsmath,amsfonts,latexsym,epsf}
\usepackage[dvips]{color}
\usepackage{url}
\setlength{\parindent}{1em}

% Definitions of handy macros can go here
\input{symbolne}

\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}{1007--1034}{6/03; Revised 05/04}{8/04}{Andreas Christmann and Ingo Steinwart}

% Short headings should be running head and authors last names

\ShortHeadings{Robustness of Convex Risk Minimization Methods}{Christmann and Steinwart}
\firstpageno{1007}

\begin{document}

\title{On Robustness Properties of Convex Risk Minimization Methods for Pattern Recognition}

\author{\name Andreas Christmann \email christmann@statistik.uni-dortmund.de \\
       \addr University of Dortmund\\
       Department of Statistics\\
       44221 Dortmund, Germany
       \AND
       \name Ingo Steinwart \email ingo@lanl.gov \\
       \addr Modeling, Algorithms and Informatics Group, CCS-3\\
       Mail Stop B256 \\
       Los Alamos National Laboratory\\
       Los Alamos, NM 87545, USA}

\editor{Peter Bartlett}
\maketitle
%\copyright{Andreas Christmann and Ingo Steinwart}

\begin{abstract}%   <- trailing '%' for backward compatibility of .sty file
The paper brings together methods from two disciplines: machine learning theory and
robust statistics.
We argue that robustness is an important aspect and
we show that many existing machine learning methods
based on the convex risk minimization principle have
$-$ besides other good properties $-$ also the advantage of being robust.
Robustness properties of machine learning methods based
on convex risk minimization are investigated for the problem of pattern recognition.
Assumptions are given for the existence of the influence function of the classifiers and for bounds on the
influence function. Kernel logistic regression, support vector machines, least squares and
the AdaBoost loss function are treated as
special cases. Some results on the robustness of such methods are also obtained for the
sensitivity curve and the maxbias, which are two other robustness criteria.
A sensitivity analysis of the support vector machine is given.
\end{abstract}

\begin{keywords}
  AdaBoost loss function, influence function, kernel logistic regression, robustness, sensitivity curve,
  statistical learning, support vector machine, total variation
\end{keywords}

\section{Introduction}

In statistical learning theory the principle of regularized empirical risk
minimization based on convex loss functions plays an important role, see
\citet{Vapnik98}. One strong argument in favor of such methods is that
many classifiers based on convex loss functions are
universally consistent under weak conditions.
Nevertheless, it is important to investigate robustness properties
for such statistical learning methods for the following reasons.
In almost all cases statistical models are only approximations to
the true random process which generated a given data set and for
which a method for analyzing the data is designed. Hence the
natural question arises what impact such deviations may have on
the results. J.W.~Tukey, one of the pioneers of robust statistics,
mentioned already in 1960
\citep[p.~21]{Hampeletal1986}:
\begin{quotation}
\noindent
\emph{A tacit hope in ignoring deviations from ideal models was that they would not matter;
that statistical procedures which were optimal under the strict model would still be
approximately optimal under the approximate model. Unfortunately, it turned out that this
hope was often drastically wrong; even mild deviations often have much larger effects
than were anticipated by most statisticians.}
\end{quotation}
The main aims of robust statistics are the description of the structure best fitting
the \emph{bulk} of the data and the identification of points deviating from this structure
or deviating substructures for further treatment,
\emph{cf.} \citet{Hampeletal1986}.
Very briefly, a good robust method can be described as follows.
%
\begin{itemize}
\item If the strict model assumptions are violated, than the results of a robust method
      are only influenced in a moderate way by a few data points, which deviate
      grossly from the structure of the bulk of the data set, or by many data points,
      which deviate only mildly from the structure of the bulk of the data set.
\item A robust method should have a reasonable high efficiency when the data set
      was in fact generated by the assumed model.
\end{itemize}
%
In practice one has to apply machine learning methods to a data
set with a finite sample size.
Machine learning methods are nonparametric tools.
Nevertheless, the robustness issue is important, because the classical assumption
that all data points were \emph{independently} generated by the \emph{same} distribution
can be violated in practice.
One reason is that outliers often occur in real data sets.
Outliers can be described as data points which ``are far away
$\ldots$ from the pattern set by the majority of the data'', see
\citet[p.~25]{Hampeletal1986}. Sometimes outliers are even correlated, which
contradicts the classical assumption that the observations in the data set were
generated in an independent manner. There are many reasons for the
occurrence of outliers, \emph{e.g.} typing errors and gross errors, which
are errors due to a source of deviations which acts only
occasionally but is quite powerful. \emph{E.g.} undetected outliers may
have an extreme impact on the estimation of insurance tariffs computed by
motor vehicle insurance companies. From a robustness point of view
the occurrence of outliers is only one of several possible
deviations from the assumed model. There are often no or virtually
no gross errors in high-quality data, but $1\%$ to $10\%$ of gross
errors in routine data seem to be more the rule than the
exception, \emph{cf.} \citet[p.~27f]{ Hampeletal1986}. Especially in
large data mining problems the data quality is sometimes far from
being optimal, \emph{cf.} \citet{HandMannilaSmyth2001} or
\citet{HippGruentzerGrimmer2001}. Obviously, it is
\emph{not} the goal to \emph{model} the occurrence of typing
errors or gross errors, because it is unlikely that they will occur in the
same manner for other data sets which will be collected in the future.
Goals of robust statistics are to investigate the impact such data points can
have on the results of estimation, testing or prediction methods and the development
of methods such that the impact of such data points is bounded.

We like to give an example showing that robustness properties of statistical methods
can be very important in practice.
A data set from 15 German motor vehicle insurance
companies from the Verband {\"o}ffentlicher Versicherer in D{\"u}sseldorf, Germany,
is investigated by \citet{Christmann2004a}.
The main goals are the estimation of the expected claim amount, which is the primary
response variable, and the probability that a customer has at least one claim within
one year, which is the secondary response variable.
It is well-known that even the very weak assumptions typically made by
machine learning methods, see Section 2, may be violated for such data sets for the following
reasons.
The true values of the claim amount, \emph{i.e.} the primary response variable, is not known
exactly for all customers. \emph{E.g.} if a major accident occurs
in November, the exact claim size will often not be known at the end of the year and
perhaps not even at the end of the following year. Possible reasons are law-suits or
the case of physical injuries. In this case, a statistician will have to use more or less
appropriate estimations of the exact claim size to construct a new insurance tariff
for the next year. Hence, the empirical distribution of the claim amount
is in general a mixture of really observed values and of estimated claim amounts.
Further, some explanatory variables may have imprecise values. \emph{E.g.} there is a
variable describing how many kilometers a customer is driving with the car within one
year. The customer has to choose between some categories,
\emph{e.g.} below $9000$ kilometers, between $9000$ and $12000$ kilometers, between $12000$ and $15000$
kilometers, and so on.
There are reasons making it plausible, that a percentage of these values in the
data set are too small, \emph{e.g.} it is well-known to the customers that the premium
of an insurance tariff increases for increasing values of this variable.
The data set contains data from
more than four million customers with more than 70 variables. Hence
there is a high probability that some data points are typing errors,
although the data set is of high quality.

There are different approaches to robustness in the statistical literature.
For statistics representable as a functional of the empirical distribution,
qualitative robustness, which is defined as equicontinuity of the distributions
of the statistic as the sample size changes, is closely related
to continuity of the statistic viewed as a functional in the weak(-star) topology,
\emph{cf.} \citet[p.~7f]{Huber1981} or \citet[p.~41]{Hampeletal1986}.
The concept of qualitative robustness is a rather weak robustness criterion. It has
the disadvantage that it does not offer arguments how to choose among different
qualitative robust procedures.
Huber's minimax approach of robust statistics
\citep{Huber1964,Huber1981} is to
minimize the maximum asymptotic variance of the estimator within a neighborhood
of the model.
Other strategies of robust statistics are Hampel's influence function
\citep{Hampel1974,Hampeletal1986}, the finite sample breakdown point proposed by
\citet{DonohoHuber1983},
the approach based on least fa\-vour\-able local alternatives
\citep{Rieder1994}, and the regression depth method
proposed by \citet{RousseeuwHubert1999}.

Here, we will mainly use the approach based on the influence
function. This approach can be applied to quite general models and
the influence function has a nice interpretation, because it is a special
G{\^a}teaux derivative, see Section 3.
A map $T$ is called robust in the theory of robust statistics based on
influence functions, if $T$ has as a \emph{bounded}
influence function. From the viewpoint of robust statistics
it is important to investigate the
impact a small amount of contamination of the `true' probability measure
$\mathbb{P}$ can have on the statistical learning process which is
specified via the regularized theoretical risk,
\emph{i.e.} the objective functions $R_{L,\P,\lb}^{reg}(.)$ and
$R_{L,\P,\lb}^{reg}(.,.)$ given in (\ref{r4a}) and (\ref{r4b}).

This paper investigates robustness properties of
statistical learning methods based on convex risk minimization and is organized as follows.
Section 2 gives some notions on convex risk minimization methods.
Section 3 gives the definitions of the influence function, the sensitivity curve,
and the maxbias, which are the robustness concepts we are dealing with.
Section 4 and Section 5 contain the main results.
For practical applications Theorem \ref{bound1} is our most important result and it covers
a broad class of loss functions including the ones used by SVM, kernel logistic regression,
AdaBoost and least squares.
In Section 4 sufficient conditions are given for the existence of the influence
function for classifiers based on (\ref{r4a}) and (\ref{r4b}).
In Section 5 it is shown that the influence function of the solution of
(\ref{r4b}) and the difference quotient used in the definition of the influence function
for (\ref{r4a}) can be bounded independently of $z$ and $\P$.
Bounds for the sensitivity curve and for the maxbias are also given.
Section 6 describes the results of some simulation experiments to gain insight into the robustness properties
of the SVM for finite sample sizes and investigates the impact a single data point can have if a radial basis function
kernel or a linear kernel is used. Section~7 contains the conclusion.
Finally, the Appendix gives the proofs of the main theorems discussed in this paper
and lists some mathematical facts which are used in our proofs.

%----------------------------------------------------------------------------------%
\section{Convex Risk Minimization in Machine Learning}

In pattern recognition and statistical machine learning the major goal is the estimation of
a functional relationship $y_i \approx f(x_i)$ between an outcome $y_i$ and a vector of explanatory variables
$x_i=(x_{i,1},\ldots,x_{i,k})'\in \mathbb{R}^d$.
The function $f$ is unknown. The estimate for $f$ is used to get predictions of an
unobserved outcome $y_\textrm{new}$ based on an observed value $x_\textrm{new}$.
One needs the implicit assumption that the relationship between $x_\textrm{new}$ and 
$y_\textrm{new}$ is---at least almost---the same as in the training data set $(x_i,y_i)$, $i=1,\ldots,n$.
Otherwise, it is useless to extract knowledge on $f$ from the training data set.
The classical assumption in machine learning is that the training data $(x_i,y_i)$ are independent and identically
generated from an underlying unknown distribution $\mathbb{P}$ for a pair of random variables $(X_i,Y_i)$.
In practical applications the training data set is often quite large, high dimensional and complex.
The quality of the predictor $f(x_i)$ is measured by some loss function $L(y_i,f(x_i))$.
The goal is to find a predictor $f_\P(x_i)$ that minimizes the expected loss, \emph{i.e.}
%
\begin{equation}\label{r1a}
   \E_{\,\mathbb{P}} \, L(Y,f_\P(X)) = \min_f \E_{\,\mathbb{P}} \, L(Y,f(X)),
\end{equation}
%
where $\E_{\,\mathbb{P}} \, L(Y,f(X)) = \int L(y,f(x)) d\mathbb{P}(x,y)$
denotes the expectation of $L$ with respect to $\mathbb{P}$.
We sometimes write $L(f)$ instead of $L(y,f(x))$ and $L(f+b)$ instead of $L(y,f(x)+b)$ to shorten the notation, if misunderstandings are unlikely.
We use this kind of notation also for derivatives of $L$.

%
In this paper we are interested in binary classification, where $y_i \in Y:=\{-1,+1 \}$.
The straightforward prediction rule is: predict $y_i=+1$ if $f(x_i) \ge 0$,
and predict $y_i=-1$ otherwise.
The loss function for the classification error is given by
$I(y_i,f(x_i))=\mathbb{I}(y_i f(x_i)<0)+\mathbb{I}(f(x_i)=0)\mathbb{I}(y_i=-1)$, where
$\mathbb{I}$ denotes the indicator function.
Inspired by the law of large numbers one might estimate $f_\P$ with the minimizer $f_{emp}$
of the empirical classification
error, that is
%
\begin{equation}\label{r2a}
  f_{emp} =\arg\min_f\frac{1}{n} \sum_{i=1}^{n} \, I(y_i, f(x_i)) \ .
\end{equation}
%
%or
%
%\begin{equation}\label{r2b}
%  \frac{1}{n} \sum_{i=1}^{n} \, I(y_i, f(x_i)+b)
%\end{equation}
%
To avoid over-fitting one usually has to restrict the class of functions $f$ considered in (\ref{r2a}).
Unfortunately, the classification function $I$ is not convex
and the minimization of (\ref{r2a}) is
often NP-hard, \emph{cf.} \citet{HoeffgenSimonVanHorn1995}.
To circumvent this problem, one can replace the classification error
function $I(y_i,f(x_i))$ in (\ref{r2a}) by a
convex upper bound $L:Y\times \R \to \mathbb{R}$
\emph{cf.} \citet{Vapnik98} and \citet{SchoelkopfSmola2002}.
Furthermore, using reproducing kernel Hilbert spaces and an additional regularization term
have some algorithmic advantages.
These modifications lead
to the following empirical regularized risks:
%
\begin{equation}\label{r3a}
   \hat{f}_{n,\lb}  =  \arg\min _{f \in H} \lambda \|f\|_H^2 + \frac{1}{n} \sum_{i=1}^{n} \, L(y_i, f(x_i)),
\end{equation}
%
%
\begin{equation}\label{r3b}
   (\hat{f}_{n,\lb}, \hat b_{n,\lb})  =  \arg\min _{f \in H, \, b \in \mathbb{R}} \,
    \lambda \|f\|_H^2 + \frac{1}{n} \sum_{i=1}^{n} \, L(y_i, f(x_i)+b),
\end{equation}
%
where $\lambda>0$ is a small regularization parameter, $H$ is a
reproducing kernel Hilbert space (RKHS) of a kernel $k$, and $b$ is called {\em offset}.
The decision functions are $\sign(\hat{f}_{n,\lambda})$ or $\sign(\hat{f}_{n,\lambda} + \hat b_{n,\lambda})$.
Note that in practice usually (\ref{r3b}) is solved while many theoretical
papers deal with (\ref{r3a}) since the unregularized offset $b$ often
causes technical difficulties in the analysis.

In practice the dual problems of (\ref{r3a}) and (\ref{r3b}) are solved.
In these problems the RKHS does not occur explicitly, instead the corresponding
kernel is involved.
The choice of the kernel $k$ enables
the above methods to efficiently estimate not only linear,
but also non-linear functions.
Of special importance is the Gaussian radial basis function (RBF) kernel
%
\begin{equation}
  k(x,x')=\exp(-\gamma \| x-x' \|^2) \,  , \quad \gamma > 0, \label{RBF}
\end{equation}
%
which is a universal kernel on every compact subset of
$\mathbb{R}^d$ in the sense of \citet{Ste01a}.
Furthermore, this kernel is a bounded kernel, as $|k(x, x')| \le 1$ for all $x,x'\in \R^d$.
Polynomial kernels $k(x,x') =  \left( c+ \langle x , x' \rangle \right)^m$ are also popular
in practice, but are unbounded for $m \ge 1$ and $X=\mathbb{R}^d$.


Popular loss functions depend on $y$ and $f$ via $v=yf(x)$ or $v=y(f(x)+b)$.
Some important specifications of $L$ are given in Table \ref{tab:loss functions}.
The support vector machine (SVM) penalizes points linearly if $v<1$.
Kernel logistic regression and AdaBoost use twice continuously differentiable loss
functions.
The loss function used by kernel logistic regression \citep{Wahba1999}
penalizes misclassifications in a
similar way to the SVM, \emph{i.e.} approximately linearly if $v \to -\infty$.
The loss function used by AdaBoost increases exponentially for $v \to -\infty$,
\emph{cf.} \citet{FreundSchapire1996},
\citet{FriedmanHastieTibshirani2000},
and \citet{HastieTibshiraniFriedman2001}.
The modified Huber's loss function, \emph{cf.} \citet{Zhang04a}, changes the modified least
squares loss such that misclassified points with $v<-1$ are penalized only linearly.
\begin{table}[t]
\begin{tabular}{lll}
  Method & $L$ & $L'$ \\
  \hline
  Support Vector Machine & $\max(1-v,0)$ & $-1$, if $v < 1$ \\
                         &               & $0$, if $v > 1$ \\
  Kernel Logistic Regression & $\ln(1+\exp(-v))$ & $-1/(1+\exp(v))$ \\
  AdaBoost & $\exp(-v)$ & $-\exp(-v)$ \\
  Least Squares & $(1-v)^2$ & $2(v-1)$  \\
  Modified Least Squares & $\max(1-v,0)^2$ & $-2 \max(0, 1-v)$  \\
  Modified Huber &  $-4v$, if $v<-1$                & $-4$, if $v<-1$\\
                 &  $\max(1-v,0)^2$, else & $-2 \max(0, 1-v)$, otherwise \\
  \hline
\end{tabular}
\caption{Loss functions, where $v=yf(x)$ or $v=y[f(x)+b]$, respectively. \label{tab:loss functions}}
\end{table}

%\begin{figure}[t]
%   \begin{center}
%       \includegraphics[height=12.0cm, angle=0]{lossfunctions3.eps}
%       \caption{Illustration of different loss functions. \label{fig:loss functions}}
%   \end{center}
%\end{figure}
%
Two major benefits of using a convex loss function are known:
\begin{itemize}
\item For convex loss functions the
resulting problems (\ref{r3a}) and (\ref{r3b}) are {\em
computationally tractable} in the sense that they can be approximately solved in
polynomial time. In fact, for many loss functions fast algorithms
do exist. For bounded loss functions the convexity is lost and to
our best knowledge almost nothing is known whether the problems
are computational tractable. For applications of non-convex loss
functions in the context of weighted least squares support vector
machines for regression problems see \citet{SuykensDebrabanterLukasVandewalle2002}.
\item In the last two years an exciting observation almost
revolutionized considerations on the learning performance of
classification algorithms. The standard approach for bounding the
estimation error of (regularized) empirical risk minimization (ERM) algorithms
is to apply a uniform deviation bound. With this technique no
learning rates faster than $n^{-\frac{1}{2}}$, where $n$ is the
sample size, can be obtained for nontrivial function classes and
noisy distributions. However, if one ``quantifies'' the amount of
noise \citep{Tsy04a} and considers ERM-type
algorithms with {\em convex} loss
functions then learning rates up to $n^{-1}$ are possible! For
more information of this recent development we refer to
\citet{BartlettBousquetMendelson2002}, \citet{BaJoMc03a} and \citet{BarlettMendelson2002}.
In particular, this program has been successively applied to support vector machines by
\citet{ScovelSteinwart2003}.
Learning rates for boosting methods are investigated by
\citet{BlanchardLugosiVayatis2003}.
\end{itemize}
These two benefits of convex loss functions are the major reasons
why the convexity plays a very important role in recent machine
learning algorithms. This is in contrast to robust statistics,
where often non-convex loss functions are used, although such
robust statistics are based on objective functions with more than
one local optimum, \emph{c.f.}
\cite{Hampeletal1986} and \cite{Christmann1994,Christmann1998a}.

Problems (\ref{r3a}) and  (\ref{r3b}) can be interpreted as a stochastic approximation of
the minimization of the theoretical regularized risk given in
(\ref{r4a}) or (\ref{r4b}), respectively
\citep{Vapnik98,Zhang04a,Ste03d}:
%
\begin{equation}\label{r4a}
   f_{\P,\lb} = \arg\min _{f \in H} \lambda \|f\|_H^2 + \E_{\,\P} \, L(Y,f(X)) \, ,
\end{equation}
%
%
\begin{equation}\label{r4b}
   (f_{\P,\lb},b_{\,\P,\lb}) = \arg\min _{f \in H, \, b \in \mathbb{R}} \lambda \|f\|_H^2 + \E_{\,\P} \, L(Y,f(X)+b) \, .
\end{equation}
%
The objective functions in (\ref{r4a}) and (\ref{r4b}) are denoted by
$R_{L,\P,\lb}^{reg}(.)$ and $R_{L,\P,\lb}^{reg}(.,.)$ in the sequel.

\citet{Ste02a} shows that SVM's are universally consistent,
\emph{i.e.} the classification error of $\hat{f}_{n,\lb}(.)$
converges to the optimal Bayes error
$\E_{\,\mathbb{P}} \, I(Y,f_\P(X))$ in probability, provided that the
reproducing kernel Hilbert space is dense in the space $C(X)$,
$X\subset \Rn$ compact, and $\lb=\lb_n$ tends ``slowly'' to 0 for $n\to \infty$.
\citet{Zhang04a} improves this result by showing that for many convex loss functions
the classifiers based on (\ref{r3a}) are
universally consistent if $\lambda_n \to 0$ and $\lambda_n n \to \infty$.
\citet{Ste03d} characterizes the loss functions which lead to universally consistent
classifiers and establishes universal consistency for classifiers based on (\ref{r3a}) and (\ref{r3b}).
Furthermore, he shows that there exist solutions of both
the theoretical and the empirical problems.
Under certain assumptions on the data generating distribution one
can even establish rates on the learning speed of SVM's.
Such results can be found in \citet{Ste01a}, \citet{ChenEtAl2003}, and
\citet{ScovelSteinwart2003}.
Moreover, \citet{Ste03c} gives
lower asymptotical bounds on the number of support vectors, \emph{i.e.} on the
data points with non-vanishing coefficients, and investigates the asymptotic behavior of $\hat{f}_{n,\lb}(.)$
in terms of the loss function $L$.
As a by-product it also turns out that the solutions
of (\ref{r3a}) and (\ref{r4a}) are unique. The same holds for the RKHS part
of the solutions of (\ref{r3b}) and (\ref{r4b}).
Upper bounds on the number of support vectors can be found in \citet{Ste03e}.
\citet{SchoelkopfSmola2002} describe other support vector machines and
give an overview on algorithms to solve the minimization problems corresponding to SVMs.



%-----------------------------------------------------------------------------------%
\section{Robustness}


In the statistical literature different criteria have been proposed to define the notion
of robustness in a mathematical way, \emph{e.g.}
the minimax approach \citep{Huber1964},
the sensitivity curve \citep{Tukey1977},
the approach based on influence functions \citep{Hampel1974,Hampeletal1986},
the maxbias curve \citep{Huber1964,Hampeletal1986},
and the finite sample breakdown point \citep{DonohoHuber1983}.

In this paper, we mainly use the approach based on the influence function
proposed by \citet{Hampel1974} and \citet{Hampeletal1986}.
We will consider a map $T$ which assigns to every distribution $\P$ on a given set $Z$
an element $T(\P)$ of a given Banach space $E$.
In the case of the convex risk minimization methods given in (\ref{r4a}) and (\ref{r4b})
$E$ equals the RKHS and $T(\P)=f_{\P,\lb}$ or $T(\P)=(f_{\P,\lb},b_{\,\P,\lb})$,
respectively.
The book by \citet[p.~34ff]{Huber1981} is a standard reference for G{\^a}teaux and Fr\'echet
derivatives in the context of robust statistics.

\begin{definition}[Influence function]
The influence function of $T$ at a point $z$ for a distribution $\mathbb{P}$ is the
 special
G{\^a}teaux derivative (if it exists)
%
\begin{equation}
  \mathit{IF}(z;T,\mathbb{P}) = \lim_{\varepsilon \downarrow 0} \,
  \frac{T\bigl((1-\varepsilon)\mathbb{P}+\varepsilon\Delta_z\bigr)-  T(\mathbb{P})} {\varepsilon} \quad , \label{r5}
\end{equation}
%
where $\Delta_z$ is the Dirac distribution at the point $z$ such that $\Delta_z(\{z\})=1$.
\end{definition}

The influence function has the interpretation, that it measures the impact of an
(infinitesimal) small amount of contamination of the original distribution $\mathbb{P}$ in
direction of a Dirac distribution located in the point $z$ on the theoretical quantity of interest $T(\mathbb{P})$.
Therefore, in the robustness approach based on influence functions it is desirable that
a statistical method which can be written as $T(\mathbb{P})$ has a
\emph{bounded} influence function.
If $T$ fulfills some regularity conditions, it can be linearized near $\mathbb{P}$ in
terms of the influence function via
%
\begin{displaymath}
 T(\mathbb{P}^*)=T(\mathbb{P})+\int \mathit{IF}(z;T,\mathbb{P})\, [\mathbb{P}^*(dz)-\mathbb{P}(dz)] + \ldots \, ,
\end{displaymath}
%
where $\mathbb{P}^*$ is a probability distribution near $\mathbb{P}$,
\emph{cf.} \citet[p.~14]{Huber1981}.
If different methods have a bounded influence function, the one with a lower bound
is the more robust one.

The sensitivity curve $SC_n$ proposed by J.W. Tukey and discussed in detail by
\citet[p.~93]{Hampeletal1986}
can be interpreted as a finite sample version of the influence function, see ({\ref{scn2}}).
The sensitivity curve measures the impact of just one additional data point $z$ on the empirical quantity of interest,
\emph{i.e.} on the estimate $T_n$.

\begin{definition}[Sensitivity curve]\label{sc}
The sensitivity curve of an estimator $T_n$ at a point $z$ given a data set $z_1, \ldots, z_{n-1}$ is
defined by
%
\begin{equation}
  \mathit{SC}_n(z;T_n) = n \bigl( T_n(z_1,\ldots,z_{n-1},z) - T_{n-1}(z_1,\ldots,z_{n-1}) \bigr) \, .
 \label{SCn}
\end{equation}
%
\end{definition}

If the estimator $T_n$ is defined via $T(\mathbb{P}_n)$,
where $\mathbb{P}_n$ denotes the empirical distribution of the data points
$z_1,\ldots,z_n$, then we have for $\varepsilon_n=1/n$:
%
\begin{equation}{\label{scn2}}
  \mathit{SC}_n(z;T_n) = \frac { T\bigl( ( 1-\varepsilon_n) \mathbb{P}_{n-1}  + \varepsilon_n \Delta_z \bigr)
                                  - T(\mathbb{P}_{n-1})} {\varepsilon_n} \, .
\end{equation}
%

Of theoretical as well as of practical importance is also the notion of maxbias, which
measures the maximum bias $T(Q)-T(\mathbb{P})$ within a neighborhood of probability
distributions $Q$ near $\mathbb{P}$.
In robust statistics the so-called contamination (or gross-error)
neighborhood (defined below), \emph{cf.} \citet{Huber1981}, is quite common for the following three reasons.
It allows a good interpretation because it contains mixture distributions with respect to
the 'true' distribution $\mathbb{P}$ and some other distribution.
The contamination neighborhood has some relationship
to the influence function and to breakdown points, and finally it is often easier to deal with this set of
distributions than with other neighborhoods.
Note that the contamination neighborhood is not a neighborhood in the topological sense.

\begin{definition}[Maxbias]\label{maxbias}
Let $\mathbb{P}$ be a fixed probability distribution on $X \times Y$.
A contamination neighborhood of $\mathbb{P}$ is given by
%
\begin{displaymath}
  N_{\varepsilon}(\mathbb{P}) =
    \left\{Q=(1-\varepsilon)\mathbb{P}+\varepsilon \tilde{\mathbb{P}} ; \,
    \tilde{\mathbb{P}} {\rm \,\, is \,\, any \,\, distribution \,\, on \,\,} X \times Y,
    \,0 \le \varepsilon < \frac{1}{2} \right\} \, .
\end{displaymath}
%
The maxbias (or supremum bias) of $T$ at the distribution $\mathbb{P}$ with respect to
the contamination neighborhood $N_{\varepsilon}(\mathbb{P})$ is defined by
%
\begin{displaymath}
  {\rm maxbias}(\varepsilon; T, \mathbb{P}) =
    \sup_{Q \in N_{\varepsilon}(\mathbb{P})} \snorm {T(Q) - T(\mathbb{P})} \, .
\end{displaymath}
%
\end{definition}

%-----------------------------------------------------------------------------------%


%-----------------------------------------------------------------------------------%
\section{Existence of the Influence Function}\label{exists-IF-sect}


In this section we give sufficient conditions for the existence of the influence
function for classifiers based on (\ref{r4a}) and (\ref{r4b}), whereas the next section
will show that the influence function is bounded under weak conditions.
Most of our results are valid for \emph{any} distribution $\mathbb{P}$ on $X \times Y$.
Therefore, they are also valid for the special case of the empirical distribution
$\mathbb{P}_n=\frac{1}{n}\sum_{i=1}^{n} \Delta_{(x_i,y_i)}$, \emph{i.e.} for a given
data set, and for the empirical regularized risks defined in (\ref{r3a}) and (\ref{r3b}).




Since our robustness results in this section are based on the
calculus in (infinite dimensional) Banach spaces
we first recall some basic notions; more details are given in the
appendix. To this end let $G:E\to F$ be a map between two
Banach spaces $E$ and $F$. We say that $G$ is
{\em (Fr\'echet)-differentiable in $x_0\in E$} if there exists a bounded
linear operator $A:E\to F$ and a function $\p:E\to F$ with $\frac
{\p(x)}{\snorm x}\to 0$ for $x\to 0$ such that
\begin{equation}\label{def-diff}
G(x_0+x) - G(x_0) \Eq Ax + \p(x)
\end{equation}
for all $x\in E$. It turns out that $A$  is uniquely determined by
(\ref{def-diff}). We hence write $G'(x):= \frac{\partial
G}{\partial E}(x):= A$. The map $G$ is called continuously
differentiable if the map $x\mapsto G'(x)$ exists on $E$ and is
continuous. Analogously we define continuous differentiability on
open subsets of $E$.

We also have to introduce the notion of Bochner-integrals. For simplicity we
restrict ourselves to the RKHS case, since this is the only one we actually
need.
To this end let $H$ be a RKHS of a bounded, continuous kernel $k$ on $X$ with feature map
$\Phi:X\to H$, i.e.~$\Phi(x)=k(x,.)$. Furthermore, let $\P$ be a probability measure
on $X\times Y$ and $h:Y\times X\to \R$ be a
function which is continuous in its second variable $x\in X$. Then
the Bochner-integral $\E_{\P} h(Y,X)\Phi(X)$ is an element of $H$ which in our
case can be computed by a simple Riemann approach, i.e.~by partitioning
the underlying space $X\times Y$. For a precise definition of Bochner-integrals
we refer to \cite{DiUh77}. Note that in our special situation we can also interpret
$\E_{\P} h(Y,X)\Phi(X)$ as an element of the dual space $H'$ by the
Fr\'echet-Riesz theorem, i.e.~$\E_{\P} h(Y,X)\Phi(X)$ acts as a functional on $H$ via
$w\mapsto \langle \E_{\P} h(Y,X)\Phi(X), w\rangle$.
Finally, we have to consider Bochner-integrals of the form
$\E_{\P} h(Y,X)\langle \Phi(X),\, .\,\rangle \Phi(X)$ which define
bounded linear operators on $H$ by the map
$w\mapsto \E_{\P} h(Y,X)\langle \Phi(X),w\rangle \Phi(X)$.

We can now establish our first two
results which treat classifiers based on (\ref{r4a}) with a
smooth loss function and a bounded continuous kernel.
The first theorem covers \emph{e.g.} the Gaussian RBF kernel.
The Dirac distribution in the point $z$ is denoted by $\Delta_z$.

\begin{theorem}\label{exist-IF1}
Let $L:Y\times \R\to [0,\infty)$ be a convex and twice continuously differentiable loss
function. Furthermore, let $X\subset \Rn$ be a closed or open subset, $H$ be a RKHS of a
bounded continuous kernel on $X$ and $\P$ be a distribution on $X\times Y$.
We define $G:\R\times H \to H$ by
$$
G(\e,f) := 2\lb f + \E_{(1-\e)\P + \e \D_z} L'(Y,f(X))\Phi(X)
$$
which implies
$$
\frac{\partial G}{\partial \e}(0,f_{\P,\lb})=
-\E_{\P}[L'(Y,f_{\P,\lb}(X))\Phi(X)] + L'(z_y,f_{\P,\lb}(z_x)) \Phi(z_x).
$$
Furthermore, we define $S:H\to H$ by
$$S:=\frac{\partial G}{\partial H}(0,f_{\P,\lb})=
    2\lb\, \id_H + \E_{\P} L''(Y,f_{\P,\lb}(X))\langle \Phi(X),.\rangle\Phi(X) \, .
$$
Then the influence function of the classifiers based on (\ref{r4a}) exists for all
$z = (z_x, z_y) \in X\times Y$
and is given by
\begin{equation}
\mathit{IF} (z;T,\P) = -S^{-1} \circ
\frac{\partial G}{\partial \e}(0,f_{\P,\lb}) \ .
\end{equation}
\end{theorem}

\begin{remark}
The influence function derived in Theorem \ref{exist-IF1} depends on
the point $z = (z_x, z_y)$, where the point mass contamination
takes place, only by the term $L'(z_y,f_{\P,\lb}(z_x)) \Phi(z_x)$.
\end{remark}

In practice the set $X$ is usually a bounded and closed subset of $\Rn$ and hence compact.
In this case existence of the influence function can be shown without the
assumption that the kernel is bounded, and hence the following theorem
covers also polynomial kernels.

\begin{theorem}\label{exist-IF1compact}
Let $L:Y\times \R\to [0,\infty)$ be a convex and twice continuously differentiable loss function.
Furthermore, let $X\subset \Rn$ be compact, $H$ be a RKHS of a continuous kernel on $X$
and $\P$ be a distribution on $X\times Y$.
Then the influence function of the classifiers based on (\ref{r4a}) exists for all
$z\in X\times Y$.
\end{theorem}


\begin{remark}
By a simple modification of the proof of the above theorem we actually find that
the special G{\^a}teaux derivative of
$T:\P\mapsto f_{\P,\lb}$
exists for every direction, \emph{i.e.}
$$
\lim_{\varepsilon \downarrow 0} \,
  \frac{f_{(1-\varepsilon)\mathbb{P}+\varepsilon\tilde\P,\lb}-  f_{\P,\lb}} {\varepsilon}
$$
exists for all distributions $\P$ and $\tilde \P$ on $X\times Y$ provided that the assumptions
of Theorem \ref{exist-IF1} hold.
This is an interesting result from the viewpoint of applied statistics, because
a point mass contamination is just one possible kind of contamination which can occur in practice.
\end{remark}





The following theorem shows the existence of the influence function
for classifiers based on (\ref{r4b}). Since the offset $b_{\P,\lb}$ can be infinite
for certain loss functions if $\P$ is degenerate,
i.e~$\P(\{(y,x):x\in X\})= 1$ for $y=+1$ or $y=-1$, we have to exclude these probability measures.
Note that these measures almost surely produce training sets of the form
$((1,x_1),\dots,(1,x_n))$, or $((-1,x_1),\dots,(-1,x_n))$, respectively.


\begin{theorem}\label{exist-IF2}
Let $L:Y\times \R\to [0,\infty)$ be a convex and twice continuously differentiable
loss function with $L''>0$.
Furthermore, let $X\subset \Rn$ be open or closed, $H$ be a RKHS of a continuous
kernel on $X$ and $\P$ be a non-degenerate distribution on $X\times Y$.
We define $G:\R\times H\times \R\to H\times \R$ by
$$
G(\e,f,b) := \Bigl(2\lb f + \E_{(1-\e)\P + \e \D_z}L'(Y,f(X)+b)\Phi(X),\,
                    \E_{(1-\e)\P + \e \D_z} L'(Y,f(X)+b)\Bigr) 
$$
which implies
$$
\frac{\partial G}{\partial \e}(0,f_{\P,\lb},b_{\,\P,\lb}) =
-\E_{\P}[L'(Y,f_{\P,\lb}(X)+b_{\,\P,\lb})\Phi(X)] +
  L'(z_y,f_{\P,\lb}(z_x)+b_{\,\P,\lb}) \Phi(z_x)\, .
$$
Furthermore, for $S:=\frac{\partial G}{\partial (H\times \R)}(0,f_{\P,\lb},b_{\,\P,\lb})$
we have
$$
S =
\left(
\begin{array}{ll}
 2\lb\, \id_H + \E_{\P} L''(Y,f_{\P,\lb}(X)+b_{\,\P,\lb})\langle \Phi(X),.\rangle\Phi(X) &
 \E_{\P} L''(Y,f_{\P,\lb}(X)+b_{\,\P,\lb}) \Phi(X) \\
 \E_{\P} L''(Y,f_{\P,\lb}(X)+b_{\,\P,\lb}) \Phi(X) &
 \E_{\P} L''(Y,f_{\P,\lb}(X)+b_{\,\P,\lb})
\end{array}
\right)\, .
$$
Then the influence function of the classifiers based on (\ref{r4b}) exists for all
$z = (z_x, z_y) \in X\times Y$
and is given by
\begin{equation}
\mathit{IF} (z;T,\P) = -S^{-1} \circ
\frac{\partial G}{\partial \e}(0,f_{\P,\lb},b_{\,\P,\lb}) \ .
\end{equation}
\end{theorem}

\begin{remark}
The influence function derived in Theorem \ref{exist-IF2} depends on
the point $z = (z_x, z_y)$, where the point mass contamination
takes place, only by the term $L'(z_y,f_{\P,\lb}(z_x)+b_{\,\P,\lb}) \Phi(z_x)$.
Hence loss functions $L$ and kernels $k$ such that $L'$ and the feature map $\Phi$
are bounded are of special interest from the view point of robust statistics.
\end{remark}

\begin{remark}\label{all-gat}
As in the case of problem (\ref{r4a}) a slight modification of the proof gives that $T:\P\mapsto (f_{\P,\lb},b_{\,\P,\lb})$
is special G{\^a}teaux differentiable.
\end{remark}


\begin{remark}
Considering the loss functions in Table \ref{tab:loss functions} we immediately see that
the above theorems apply to the kernel logistic regression, the least squares and
the AdaBoost loss function. The second derivatives of the modified least squares and the modified Huber
loss function fail to exists in only one point. For the loss function of the standard SVM,
even the first derivative does not exist in one point.
\end{remark}






%-----------------------------------------------------------------------------------%
\section{Bounds on the Influence Function, Sensitivity Curve and Maxbias}


As mentioned in Section 1, a desirable property of a robust statistical method is that
$T$ has a bounded influence function.
In this section we show that for certain loss functions the influence function
can be bounded \emph{independently} of $z$ and $\P$ for classifiers based on (\ref{r4a}) and (\ref{r4b}).
For the formulation of our results we need to recall that the norm
of total variation of a signed measure $\mu$ on a space $X$ is
defined by
$$
\snorm{\mu}_{\mathcal M} := |\mu|(X) := \sup \Bigl\{ \sum_{i=1}^n |\mu(A_i)| : A_1,\dots,A_n
\mbox{ is a partition of $X$}\Bigr\}\, .
$$
For more information on this norm we refer to \citet{BrownPearcy1977}.

Our first result bounds the difference quotient in the definition
of the influence function for classifiers based on (\ref{r4a}).
For practical applications Theorem \ref{bound1} is our most
important result. In particular, it states that the influence
function of these classifiers is uniformly bounded whenever it
exists, and that the sensitivity curve is uniformly bounded too.
Please note that the following theorem based on \citet{Ste03c}
applies to all six loss functions given in Table \ref{tab:loss
functions} because differentiability of $L$ is not assumed.

\begin{theorem}\label{bound1}
Let $L:Y\times \R\to [0,\infty)$ be a continuous and convex loss function.
Furthermore, let $X\subset \Rn$ and $H$ be a RKHS of a bounded, continuous kernel on $X$.
Then for all $\lb > 0$ there exists a constant $c_L(\lb)>0$ explicitly given in (\ref{cL}) such that for all distributions
$\P$ and $\tilde \P$ on $X\times Y$ we have
$$
\Norm{\frac{f_{(1-\varepsilon)\mathbb{P}+\varepsilon\tilde \P,\lb}-  f_{\P,\lb}} {\varepsilon}}_H
\leq c_L(\lb)\ \snorm{\P-\tilde \P}_{\mathcal M} \, , \quad \varepsilon > 0\, .
$$
%where $f_{\P,\lb}$ and $f_{(1-\varepsilon)\mathbb{P}+\varepsilon\tilde \P,\lb}$ are the solutions of
%(\ref{r4a}) for $\P$ and $(1-\varepsilon)\mathbb{P}+\varepsilon\tilde \P$, respectively.
\end{theorem}

\begin{remark}\label{resultforscn}
The above theorem also gives uniform bounds for Tukey's sensitivity curve of $f$.
Consider the special case that $\mathbb{P}$ is equal to the empirical probability measure
of $(n-1)$ data points, \emph{i.e.} $\mathbb{P}_{n-1}=\frac{1}{n-1}\sum_{i=1}^{n-1}\Delta_{(x_i,y_i)}$,
and that $\tilde{\mathbb{P}}$ is equal to the Dirac measure $\Delta_{(x,y)}$ in some
point $(x,y) \in X \times Y$.
Let $\varepsilon=\frac{1}{n}$. Under the assumptions of Theorem \ref{bound1}
it follows from ({\ref{scn2}}), that
$$
n \snorm{ f_{(1-\varepsilon)\mathbb{P}_{n-1}+\varepsilon\Delta_{(x,y)},\lb}
 -  f_{\mathbb{P}_{n-1},\lb}}_H
\leq c_L(\lb)\ \snorm{\mathbb{P}_{n-1}-\Delta_{(x,y)}}_{\mathcal M} \, , \quad \varepsilon > 0\, .
$$
Essentially, this result has already been established by \citet{BoEl02a}.
\end{remark}

\begin{remark}\label{resultsformaxbias}
Because no assumptions on $\tilde{\mathbb{P}}$ are made in Theorem \ref{bound1},
an upper bound for the maxbias of $f_{\mathbb{P},\lambda}$ (see Definition \ref{maxbias}) for such machine learning methods
is given by
$$
{\rm maxbias}(\varepsilon; f, \mathbb{P})
= \sup_{Q \in N_\varepsilon} \snorm{f_{Q,\lambda}-f_{\mathbb{P},\lambda}}
\leq \varepsilon \, c_L(\lb) \,
      \sup_{\tilde{\mathbb{P}} \in \mathcal{P}} \snorm{\P-\tilde \P}_{\mathcal M}
\leq 2 c_L(\lb) \varepsilon \, ,
$$
where $\varepsilon \in (0,1/2)$, and $\mathcal{P}$ denotes the set of all probability measures on $X \times Y$.
As no assumptions are made for $\mathbb{P}$, this result is valid for
empirical distributions too. Consider the empirical distribution $\mathbb{P}_n$
defined by given data set $(x_i,y_i) \in X \times Y$ with $n$ data points.
Then the maxbias of $f_{\mathbb{P}_n,\lambda}$ in a contamination neighborhood
$N_{\varepsilon}(\mathbb{P}_n)$ is at most $2 c_L(\lb) \varepsilon$, where $\varepsilon \in (0,1/2)$.
\end{remark}

Unfortunately, using the estimate of \citet{Ste03c} does not
give any meaningful result for classifiers based on (\ref{r4b}).
However, under some additional assumptions on $L$ we can still
bound the influence function.


\begin{theorem}\label{bound2}
Let $L:Y\times \R\to [0,\infty)$ be a convex and twice
continuously differentiable loss function with $a\leq L''\leq b$
for some $a,b>0$. Furthermore, let $X\subset \Rn$ be open or closed, $H$
be a RKHS of a continuous kernel on $X$, and $T_\lb(\P) =
(f_{\P,\lb},b_{\,\P,\lb})$ be given by (\ref{r4b}). Then for all
$\lb > 0$ there exists a constant $c_L(\lb)>0$ such that for all
non-degenerated distributions $\P$ on $X\times Y$ and all $z\in
X\times Y$ we have
$$
\snorm{\mathit{IF}(z;T,\mathbb{P})}_{H\times\R}
\leq c_L(\lb)\ \snorm{\P-\D_z}_{\mathcal M}\, .
$$
\end{theorem}



\begin{remark}
Theorem \ref{bound2} applies to (\ref{r4b}) with the least squares loss function.
However, Theorem \ref{bound2} covers neither the logistic regression loss function
as we only have $L'' \ge 0$
nor the AdaBoost loss function which satisfies $L''=L=\exp(-\, .)$
However, we get the same bound of the influence function if we restrict our considerations to
distributions $\mathbb{P}$ with
%
\begin{equation}\label{cond1}
a \Leq \int L''(Y,f_{\mathbb{P,\lambda}}(X)+b_{\,\mathbb{P},\lambda}) d\mathbb{P} \Leq b
\end{equation}
%
for some $b\geq a>0$.
A simple sufficient condition for the latter can be derived by the proof of
\citet[Lemma~II.6]{Ste03d}:
let $A_y^\rho:=\{x\in X: \P(y|x)>\r\}$, $y\in Y$, $\r>0$, and
$\a_{\,\P}(\r):= \r \min\{\P_X(A_1^\r),\P_X(A_{-1}^\r)\}$. Then fixing $\lb>0$, a
twice continuously differentiable $L$ and a threshold $\a>0$
there exist $b\geq a>0$ such that every $\P$ with $\a_{\,\P}(\r)\geq \a$ for some $\r>0$ satisfies (\ref{cond1}).
Note that the assumption $\a_{\,\P}(\r)\geq \a$ guarantees that the two classes of $\mathbb{P}$ are ``balanced''.
\end{remark}

\begin{remark}
As mentioned in Remark \ref{all-gat} the map $T:\P\mapsto (f_{\P,\lb},b_{\,\P,\lb})$
is special G{\^a}teaux differentiable. A simple modification of the proof of
Theorem \ref{bound2} shows that the special G{\^a}teaux derivative of $T$ can be uniformly bounded.
\end{remark}

\begin{remark}
Consider the case that $\mathbb{P}$ and $\tilde{\mathbb{P}}$ are probability measures with densities $p$ and
$\tilde{p}$ with
respect to some dominating measure $\nu$.
Then, the last two theorems also give bounds of the influence functions and the
sensitivity curve in terms of the Hellinger metric
$H(\mathbb{P},\tilde{\mathbb{P}})=[\int (\sqrt{p} - \sqrt{\tilde{p}})^2\,d\nu]^{1/2}$.
This follows from a relationship between the norm of total variation and the Hellinger metric:
%
\begin{displaymath}
  \| \mathbb{P} - \tilde{\mathbb{P}} \|_{\mathcal M} \le
  2 \, H(\mathbb{P},\tilde{\mathbb{P}}) \le
  2 \, \| \mathbb{P} - \tilde{\mathbb{P}} \|_{\mathcal M}^{1/2} \, .
\end{displaymath}
%
\end{remark}

Note that the bounds for the difference quotient in Theorem \ref{bound1} and for the
influence function in Theorem \ref{bound2} converge to infinity,
if $\lambda$ converges to $0$ and $\snorm{\P-\tilde{\P}}_{\mathcal M}>0$ or
$\snorm{\P-\D_z}_{\mathcal M}>0$.
However, $\lambda$ converging to $0$ has the interpretation that misclassifications
are penalized by constants $C$ tending to $\infty$. Therefore, decreasing
values of $\lambda$ correspond to a decreasing amount of robustness, which was to be
expected. The quantity $\lambda$ can be interpreted as a tuning constant
controlling the robustness properties of the method in a similar way than it is
well-known for many robust methods, \emph{e.g.} Huber-type M-estimators in location or
regression models.
Consider the Huber-type M-estimator \citep{Huber1964}
in a univariate location model, where all data points are realizations from
$n$ independent and identically distributed random variables with some distribution
function $F(\cdot-\theta)$, where $\theta \in \mathbb{R}$ is unknown.
Huber's robust M-estimator with tuning constant $b \in (0,\infty)$ has an influence function
proportional to $\psi_b(z)=\min{\{b, \max{\{z-b\}}\}}$, \emph{cf.}
\citet[p.~104f]{Hampeletal1986}. For all $b\in (0,\infty)$ the influence
function is bounded by $\pm b$. However, the bounds tend to $\pm \infty$ if $b\to \infty$, and
Huber's M-estimator with $b=\infty$ is equal to the non-robust maximum likelihood estimator
which has an unbounded influence function. Therefore, the quantity $1/\lambda$
(or the cost $C)$ in the machine learning methods we are dealing with has a similar role
to the tuning constant $b$ in Huber-type M-estimators.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\section{Empirical Results for the SVM}

In this section we study the impact an additional data point can have on the SVM with offset $b$ for pattern
recognition. An analogous investigation for the case without offset gave similar results to those
described in this section. We generated a training data set with $n=500$ data points $x_i$
from a bivariate normal distribution with expectation $\mu=(0,0)$ and covariance
matrix $\Sigma$. The variances were set to $1$, whereas the
covariance was set to $0.5$. The responses $y_i$ were generated from a classical logistic
regression model with $\theta=(-1,1)'$, $b=0.5$, such that
$P(Y_i=+1)=[1+\exp(-(x_i'\theta+b))]^{-1}$ and $P(Y_i=-1)=1-P(Y_i=+1)$.
The computations were done using the software ${\rm SVM}^{light}$ developed by
\citet{Joachims1999}.
${\rm SVM}^{light}$ solves the dual program corresponding to the primal optimization
problem
%
\begin{equation}
\begin{array}{lll}
  \arg\min _{f \in H, \, b \in \mathbb{R}} & \frac{1}{2Cn} \, || f ||_H^2 + \frac{1}{n} \Sum_{i=1}^n \xi_i
  \label{SVMprimalb1}
 \\
    {\mbox{such that} \,} &
      y_i (f(x_i)+b) \ge   1 - \xi_i   \\
  &
  \xi_i \ge   0 \, .
\end{array}
\end{equation}
%
We consider two popular kernels: a Gaussian radial basis function kernel
with parameter $\gamma$, see {(\ref{RBF})} and a linear kernel.
Appropriate values for $\gamma$ and for the constant $C$ (or $\lambda$) are important for
the SVM and are often determined by cross validation, \emph{cf.}
\citet[p.~217]{SchoelkopfSmola2002}.
A cross validation based on the leave-one-out error for the training data set was carried out by a
two-dimensional grid search on
\begin{displaymath}
\gamma \in \{0.05, 0.1, 0.25, 0.5, 0.75, 1, 1.5, 2, 3, 4, 5, 10, 20 \}
\end{displaymath}
and
\begin{displaymath}
 C \in \{ 0.5, 0.75, 1, 1.25, 1.5, 1.75, 2, 5, 10, 20 \}.
\end{displaymath}
As a result of the cross validation, the tuning parameters for the SVM with RBF kernel were set to $\gamma=0.25$ and
$C=2$.
The leave-one-out error for the SVM with a linear kernel turned out to be stable over a broad range of values for $C$.
We used $C=1$ in the computations for the linear kernel.
For $n=500$ this results in $\lambda =(2Cn)^{-1} = 5 \times 10^{-4}$ for the RFB kernel and
$\lambda =(2Cn)^{-1}=0.001$ for the linear kernel. Please note that such small values of $\lambda$ will result
in relatively large bounds.
% Figures \ref{fig:fsensitivityb1} to \ref{fig:thetasensitivityb1}} show the results.

Figure \ref{fig:fsensitivityb1} shows the sensitivity curves of
$\hat{f}+\hat{b}:=\hat f_{n,\lambda}+\hat{b}_{n,\lambda}$,
if we add a single point $z=(x,y)$ to the original data set, where $x_1=6$, $x_2=6$, and
$y=+1$.
The additional data point has a local and smooth impact on $\hat{f}+\hat{b}$ with a peak
in a neighborhood of $(x_1,x_2)$, if one uses the RBF kernel.
For a linear kernel, the impact is approximately linear.
The reason for this different behavior of the SVM with different kernels becomes clear from Figure \ref{fig:fplotb1}
where plots of $\hat{f}+\hat{b}$ are given for the original data set and for the modified data set, which contains the
additional data point $z$.
Please note that the RBF kernel yields $\hat{f}+\hat{b}$ approximately equal to zero outside a central region,
as almost all data points are lying inside the central region. Comparing the plots of $\hat{f}+\hat{b}$ based on the
RBF kernel for the modified data set with the corresponding plot for the original data set, it is obvious that the
additional smooth peak is due to the new data point located at $x=(6,6)$ with $y=+1$.
It is interesting to note that although the estimated functions $\hat{f}+\hat{b}$ for the original data set and for the
modified data set based on the SVM with the linear kernel are looking quite similar, the sensitivity curve
is similar to an affine hyperplane which is affected by the value of $z$.
This allows the interpretation, that just a single data point can have an impact on $\hat{f}+\hat{b}$ estimated by a
SVM with a linear kernel over a broader region than for an SVM with an RBF kernel.

\begin{figure}[t]
   \begin{center}
   \begin{tabular}{cc}
     \includegraphics[height=6cm, angle=-90]{simulation3n500radialb1.scnpred.eps}\!\!\!&\!\!\!
     \includegraphics[height=6cm, angle=-90]{simulation3n500linearb1.scnpred.eps}
   \end{tabular}
   \end{center}
   \caption{Sensitivity function of $\hat{f}+\hat{b}$, if the additional data point $z$ is located at $z=(x,y)$,
       where $x=(6,6)$ and $y=+1$. Left: RBF kernel. Right: linear kernel. \label{fig:fsensitivityb1}}
\end{figure}

\begin{figure}[t]
   \begin{center}
   \begin{tabular}{cc}
       \includegraphics[height=6cm, angle=-90]{simulation3n500radialb1.predorig.eps}\!\!\!&\!\!\!
       \includegraphics[height=6cm, angle=-90]{simulation3n500linearb1.predorig.eps} \\
       \includegraphics[height=6cm, angle=-90]{simulation3n500radialb1.predmod.eps}\!\!\!&\!\!\!
       \includegraphics[height=6cm, angle=-90]{simulation3n500linearb1.predmod.eps}
   \end{tabular}
   \caption{Plot of $\hat{f}+\hat{b}$.
               Upper left: RBF kernel, original data set.
               Upper right: linear kernel, original data set.
               Lower left: RFB kernel, modified data set.
               Lower right: linear kernel, modified data set.
               The modified data set contains the additional data point $z=(x,y)$, where $x=(6,6)$ and $y=+1$.
                \label{fig:fplotb1}}
   \end{center}
\end{figure}

%
Now, we study the impact of an additional data point $z=(x,y)$, where $y=+1$, on the
percent of classification errors and on the fitted $y-$value for $z$.
We vary $z$ over a grid in the $x-$coordinates.
Figure \ref{fig:proberrorb1} shows that the percentage of classification errors is
approximately constant outside the central region that contains almost all data points if a Gaussian RBF kernel was used.
For the SVM with a linear kernel, the percentage of classification errors tends to be
approximately constant in one half-space but changes in the other half-space.
The response of the additional data point was correctly estimated by $\hat{y}=+1$ outside
the central region, if a RBF kernel is used, see Figure \ref{fig:fittedvalueb1}.
In contrast to that, using a linear kernel results in estimated responses $\hat{y}=+1$ or $\hat{y}=-1$
of the additional data point depending on the affine half-space in which the $x-$value of $z$ is lying.
%
\begin{figure}[t]
   \begin{center}
   \begin{tabular}{cc}
         \includegraphics[height=6cm, angle=-90]{simulation3n500radialb1.out5.eps}\!\!\!&\!\!\!
       \includegraphics[height=6cm, angle=-90]{simulation3n500linearb1.out5.eps}
   \end{tabular}
   \caption{Percent of classification errors if one data point $z=(x,1)$ is added to the
            original data set, where $x$ varies over the grid.
            Left: RBF kernel. Right: linear kernel.
            \label{fig:proberrorb1}}
   \end{center}
\end{figure}
%
%
\begin{figure}[t]
   \begin{center}
   \begin{tabular}{cc}
         \includegraphics[height=6cm, angle=-90]{simulation3n500radialb1.out3.eps}\!\!\!&\!\!\!
       \includegraphics[height=6cm, angle=-90]{simulation3n500linearb1.out3.eps}
   \end{tabular}
   \caption{Fitted $y-$value for new observation if one data point $z=(x,1)$ is added to the
               original data set, where $x$ varies over the grid.
               Left: RBF kernel. Right: linear kernel.
            \label{fig:fittedvalueb1}}
   \end{center}
\end{figure}
%
Finally, let us study the impact of an additional data point located at $z=(x,y)$, where
$y=+1$, on the estimated parameters $\hat{b}$ and $\hat{\theta}$, see
Figure \ref{fig:thetasensitivityb1}.
We vary $z$ over a grid in the $x-$coordinates in the same manner as before.
As the plots for $\hat{\theta}_1$ and $\hat{\theta}_2$ are looking very similar, we only
show the latter.
Note that the axes are not identical in Figure \ref{fig:thetasensitivityb1} due to the
kernels.
The sensitivity curves for the slopes estimated by the SVM with an RBF kernel are similar
to a hyperplane outside the central region, which contains almost all data points.
In the central region, there is a smooth transition between
regions with higher sensitivity values and regions with lower sensitivity values.
The sensitivity curves for the slopes of the SVM with a linear kernel are flat in one
affine half-space, but change approximately linearly in the other affine half-space.
This behavior also occurs for the sensitivity curve of the offset by using a linear kernel. In contrast to that,
the sensitivity curve of the offset based on a SVM with a RBF kernel shows a smooth but curved shape outside the
region containing the majority of the data points.
%
\begin{figure}[t]
   \begin{center}
   \begin{tabular}{cc}
         \includegraphics[height=6cm, angle=-90]{simulation3n500radialb1.out2.eps}\!\!\!&\!\!\!
       \includegraphics[height=6cm, angle=-90]{simulation3n500linearb1.out2.eps} \\
         \includegraphics[height=6cm, angle=-90]{simulation3n500radialb1.out0.eps}\!\!\!&\!\!\!
       \includegraphics[height=6cm, angle=-90]{simulation3n500linearb1.out0.eps}
   \end{tabular}
   \caption{ Sensitivity function for $\hat{\theta}$ and $\hat{b}$, respectively.
             Upper left: Sensitivity function for $\hat{\theta}_2$, RBF kernel.
             Upper right: Sensitivity function for $\hat{\theta}_2$, linear kernel.
             Lower left: Sensitivity function for $\hat{b}$, RBF kernel.
             Lower right: Sensitivity function for $\hat{b}$, linear kernel.
             \label{fig:thetasensitivityb1}}
   \end{center}
\end{figure}

%-------------------------------------------------------------------------------------------%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Concluding Remarks}

In this paper, we used the influence function approach of robust statistics
\citep{ Hampeletal1986} for recent statistical learning methods based on convex
risk minimization methods for the problem of pattern recognition.
The influence function has the interpretation that it measures the impact of an
infinitesimal amount of contamination of the original distribution
$\mathbb{P}$ in direction of a Dirac distribution located in the point $z$ on the
theoretical quantity of interest $T(\mathbb{P})$.
Special cases of such convex risk minimization methods are the support vector machine,
kernel logistic regression, AdaBoost, and least squares. Assumptions were derived for
the existence of the influence function of $f$ or $(f,b)$ used by the classifiers
and also for uniform bounds on the influence function which hold with respect
to the distribution $\mathbb{P}$ and the point $z$ of the Dirac
distribution $\Delta_z$ describing the contamination.
For the case without offset $b$ one can uniformly bound the difference quotient
considered by the influence function under weak conditions which also yields uniform
bounds for Tukey's sensitivity curve and uniform upper bounds for the maxbias.
In particular, the influence function for these classifiers is uniformly bounded if it
exists.
Some of the results are not limited to the special G{\^a}teaux derivative used in the
definition of the influence function.
The assumptions of some of our results exclude the support vector machine because the
SVM uses a loss function which is not differentiable in one point, but
Theorem \ref{bound1} covers the SVM as a special case. We gave some numerical results for the
sensitivity curve, which can be interpreted as a finite sample
version of the influence function, of the SVM classifier. It turned out, that
the popular exponential radial basis function kernel resulted in smooth sensitivity
curves for $\hat{f}+\hat{b}$ and for the estimated coefficients
$(\hat{\theta},\hat{b})$. Varying the position of one additional data point had a
smooth and local impact on $\hat{f}+\hat{b}$, if one uses an RBF kernel.
For the linear kernel the impact of varying one additional data point
behaves also in a relatively smooth manner, but the impact seems to be more globally
than locally.

For a numerical comparison between the support vector machine and the regression depth
method recently proposed by \citet{RousseeuwHubert1999} see
\citet{ChristmannRousseeuw2001} and \citet{ChristmannFischerJoachims2002}.

It would be interesting to study the influence function of convex risk minimization
methods for other problems, \emph{e.g.} $\varepsilon-$regression or kernel principal component
analysis, or to consider other robustness concepts, but this is beyond the scope of
this paper.

%----------------------------------------------------------------------------------------------------------------%


%\newpage
% Acknowledgements should go at the end, before appendices and references
\acks{The financial support of the Deutsche Forschungsgemeinschaft
(SFB 475, "Reduction of complexity in multivariate data structures") and of
DoMuS (University of Dortmund, "Model building and simulation") are gratefully
acknowledged.
We thank three anonymous referees and the editor
for helpful remarks on an earlier version of the paper.}

% Manual newpage inserted to improve layout of sample file - not
% needed in general before appendices/bibliography.

%-------------------------------------------------------------------------------------%
%\newpage

\appendix

%-------------------------------------------------------------------------------------%
\section{Mathematical Background}
In Appendix A we list some facts from functional analysis, which are used
in Appendix B to prove our theorems.

%Throughout the appendix $B_E$ denotes the closed unit ball of
%a Banach space $E$. \\ \fix{$B_E$ closed, spaeter open}

Since our proofs are heavily based on the
calculus in (infinite dimensional) Banach spaces we first recall
the basic facts, see \emph{e.g.} \citet{Akerkar99},
\citet{BrownPearcy1977}, and \citet{Yosida1974}.
To this end let $G:E\to F$ be a map between two
Banach spaces $E$ and $F$. Recall, that
we say that $G$ is
(Fr\'echet)-differentiable in $x_0\in E$ if there exists a bounded
linear operator $A:E\to F$ and a function $\p:E\to F$ with $\frac
{\p(x)}{\snorm x}\to 0$ for $x\to 0$ such that
\begin{equation}\label{def-diff-2}
G(x_0+x) - G(x_0) \Eq Ax + \p(x)
\end{equation}
for all $x\in E$. It turns out that $A$  is uniquely determined by
(\ref{def-diff-2}). As in Section \ref{exists-IF-sect} we hence write $G'(x):= \frac{\partial
G}{\partial E}(x):= A$. Again, the map $G$ is called continuously
differentiable if the map $x\mapsto G'(x)$ exists on $E$ and is
continuous. Analogously we define continuous differentiability on
open subsets of $E$.

Unlike 1-dimensional derivates general Fr\'echet derivates suffer
from some notational difficulties. For example, the derivate
$G'(x)$ itself is a {\em map} for every $x$ and thus $G'(x)$ is
described by $y\mapsto G'(x)y$. Furthermore, considering partial
derivates can cause notational problems too. Indeed, if
\emph{e.g.}~$\id_E$ is the identity of $E$ we have
$$
x \Eq \id'(x)x \Eq \frac {\partial \id}{\partial E}(x)x \Eq
\frac{\partial \id (x)}{\partial x} x\,
$$
where the right expression uses standard notation. We feel that
the latter can cause problems for the unexperienced reader.


As in the finite dimensional case the differential operator
satisfies basic calculus, that is linearity and a chain rule
$$
\bigl(G_2\circ G_1\bigr)'(x)
\Eq
G_2'(G_1(x)) \circ G_1'(x)
$$
for $G_1:E_1\to E_2$, $G_2:E_2\to E_3$ whenever all derivates exist in the above equation.
Furthermore, for a bounded linear map $A:E\to F$ we have $A'(x)=A$ for all $x\in E$.
If $G(f):= \snorm f^2_H$ for all elements $f$ of a Hilbert space $H$ we find
$G' =2\id_H$, where $\id_H$ denotes the identity on $H$.

Let us consider an example that helps to understand the differentiation steps
in the following proofs. To this end let $\P$ be a probability measure on a subset $X\subset \R^d$
and $H$ be a RKHS of bounded continuous functions over $X$ with feature map
$\Phi:X\to H$, \emph{i.e.}~$\Phi(x):= k(x,.)$, where $k$ is the kernel of $H$. We consider the map $G:H\to \R$ which is defined by
$Gf:= \E_\P L\circ f$ for all $f\in H$ and a twice continuously differentiable function
$L:\R\to \R$. In order to compute the derivate of this map
we decompose $G$ into $G=B \circ A\circ I$, where $I:H\to C_b(X)$ is the canonical embbeding
$w\mapsto \langle w,\Phi(.)\rangle$ of $H$ into the space of all bounded continuous functions
$C_b(X)$, $A:C_b(X)\to C_b(X)$ is defined by $f\mapsto L\circ f$
and $B:C_b(X)\to \R$ is the functional $f\mapsto \E_\P f$.
For the chain rule we need to compute the derivatives of these factors.
Since $I$ is linear we have $I'(v)w= Iw$ for all $v,w\in H$.
Analogously, the linearity of $B$ gives $B'(f)g= \E_\P g$ for all $f,g\in C_b(X)$.
As shown in the book of \citet{Akerkar99},
we also have $A'(f)g= g\cdot(L'\circ f)$ for all $f,g\in C_b(X)$,
\emph{i.e.}~$A'$ is the multiplication operator with respect to $L'\circ f$.
Applying the chain rule to $A\circ I$ we hence find
$$
(A\circ I)'(v)w
\Eq
(A' (I(v)) \circ I'(v))w
\Eq
L'\circ (Iv)\cdot(Iw)
$$
for all $v,w\in H$. As we see the brackets play an important role
for the mechanic evaluation of these derivatives. Another
application of the chain rule gives
\begin{eqnarray*}
G'(v)w \Eq \bigl(B'(A\circ I(v))\circ (A\circ I)'(v)\bigr)w & = &
B'(A\circ I(v)) \bigl((A\circ I)'(v)w\bigr)\\
& = &
\E_\P (A\circ I)'(v)w\\
& = &
\E_\P L'\circ (Iv)\cdot(Iw)
\end{eqnarray*}
for all $v,w\in H$. Note that by definition $G'(v):H\to \R$ is a
bounded functional. By the theorem of
Fr\'echet-Riesz such
functionals can be represented by elements of $H$ via the mapping
$v\mapsto \langle v,.\rangle$. In our situation we can directly
compute this representation: for $v,w\in H$ we have
$$
\langle \E_\P L'\circ (Iv) \Phi,w\rangle
\Eq
\E_\P L'\circ (Iv) \langle Iv, w\rangle
\Eq
\E_\P L'\circ (Iv)\cdot(Iw)\, ,
$$
\emph{i.e.}~$\E_\P L'\circ (Iv) \Phi$ is a representation of
$G'(v)$. Note that $\E_\P L'\circ (Iv) \Phi$ is a $H$-valued {\em
Bochner-integral}. For finite dimensional spaces $\R^n$ the
$\R^n$-valued Bochner-integral can be computed by the integrals of
the $n$ components. In general
Banach spaces some problems can
occur by different notions of measurability. Since in our case $H$
is separable by the continuity of $\Phi$ and all our functions are
continuous we do not have these difficulties. In fact for compact
$X$ our Bochner-integrals can be even computed using a simple
Riemann approach. For more information about Bochner-integrals we
refer to \citet{DiUh77} or \citet{Yosida1974}.

Since in our proofs we also have to compute the second derivate of
maps of the form of $G$, let us now treat $G''$. For convenience
we use the Fr\'echet-Riesz representation of $G'$. Analogously to the above
considerations we decompose $G'$. To this end $B:C_b(X)\to H$
denotes the operator defined by $Bf:= \E_\P f \Phi$
 for all $f\in C_b(X)$. Furthermore, $A:C_b(X)\to C_b(X)$ is the operator $Af:=
L'\circ f$, $f\in C_b(X)$. Using the Fr\'echet-Riesz
representation of $G'$ we then find $G'= B\circ A\circ I$. Now
observe that $B$ is linear. Therefore we have $B'(f)g= \E_\P g
\Phi$ for all $g\in C_b(X)$. Moreover, we find $(A\circ I)'(v)w =
L''\circ (Iv)Iw$ for all $v,w\in H$ as above. Using the chain rule
this gives
$$
G''(v)w
\Eq
B''(A\circ I(v)) \bigl((A\circ I)'(v)w\bigr)
\Eq
\E_\P (A\circ I)'(v)w \Phi
\Eq
\E_\P L''\circ (Iv)Iw\Phi
$$
for all $v,w\in H$.

Our proofs also heavily rely on the implicit function theorem in Banach
spaces. Therefore, we recall a simplified version of this theorem
\citep{Akerkar99,Zeidler1986}. Here and throughout
this appendix $B_E$ denotes the open unit ball of a Banach space $E$.\\


\begin{theorem}[Implicit function theorem]\label{implicit-thm}
Let $E, F$ be Banach spaces and $G:E\times F\to F$ be a continuously differentiable map.
Suppose that we have $(x_0,y_0)\in E\times F$ such that $G(x_0,y_0)=0$ and
$\frac{\partial G}{\partial F}(x_0,y_0)$ is invertible. Then there exists a $\d>0$ and
a continuously differentiable map $f: x_0+\d B_E \to y_0 + \d B_F$ such that for all $x\in x_0+\d B_E$,
$y\in y_0 + \d B_F$ we have
$$
G(x,y)=0     \qquad \mbox{ if and only if } \qquad y=f(x)\, .
$$
Moreover, the derivative of $f$ is given by
$$
f'(x) = -\left(\frac{\partial G}{\partial F}\bigl(x,f(x)\bigr) \right)^{-1}
  \frac{\partial G}{\partial E}\bigl(x,f(x)\bigr)\, .
$$
\end{theorem}

For the application of
the implicit function theorem we have to show that certain operators are invertible.
For this the following theorem which is known as the Fredholm Alternative,
\citep{Cheney2001} turns out to be very helpful:

\begin{theorem}[Fredholm Alternative]
Let $E$ be a Banach space and $S:E\to E$ be a compact operator. Then $\id_E+S$ is
surjective if and only if it is injective.
\end{theorem}


We also need the Krein-Milman theorem, see \citet[p.~363]{Yosida1974} or
\citet[p.~309]{BrownPearcy1977}.
%
\begin{theorem}[Krein-Milman theorem]
Let $K$ be a non-void compact convex subset of a locally convex real linear topological
space. Then $K$ is equal to the closure of the convex hull of the set of all extreme
points of $K$.
\end{theorem}

%--------------------------------------------------------------------------------------%
\section{Proofs of the Theorems}
%\label{app:theorem}

% Note: in this sample, the section number is hard-coded in. Following
% proper LaTeX conventions, it should properly be coded as a reference:

In this appendix we prove the theorems from Section 4 and Section 5.
We sometimes write $L(f)$ instead of $L(y,f(x))$ and $L(f+b)$ instead
of $L(y,f(x)+b)$ to shorten the notation, if misunderstandings are unlikely.
We use this kind of notation also for derivatives of $L$.\\


%---------------------------------------------------------------------%
\textsc{Proof of Theorem \ref{exist-IF1}.} $\quad$ Let us first
check that the solution $f_{\P,\lb}$ exists in our situation.
Indeed, in the proof of the existence statement by
\citet{Ste03d} the compactness of $X$ is only used to ensure
$K:=\snorm{I:H\to \ell_\infty(X)}<\infty$, where $\ell_\infty(X)$
denotes the space of all bounded functions $f:X\to \R$ equipped
with the supremum norm and $I$ is the canonical embbeding. The
finiteness of this norm, however, {\em characterizes} bounded
kernels. Therefore, the existence statement by \citet{Ste03d} is true in our case too.

Now, let $\Phi:X\to H$ be the feature map of $H$ as in the above example.
Our analysis heavily rely on the map $G:\R \times H\to H$ that is defined by
$$
G(\e,f) := 2\lb f + \E_{(1-\e)\P + \e \D_z} L'(Y,f(X))\Phi(X)\, .
$$
Note that for $\e\not\in [0,1]$ the $H$-valued expectation is with respect to a signed measure.
For these measures we refer to \citet{Dudley02}.
Now as in the above example, for $\e\in[0,1]$ we obtain
\begin{equation}\label{help-1}
G(\e,f) = \frac {\partial R_{L,{(1-\e)\P + \e \D_z},\lb}^{reg}}{\partial H}(f)\, .
\end{equation}
Since $f\mapsto R_{L,{(1-\e)\P + \e \D_z},\lb}^{reg}(f)$
is convex for all $\e \in[0,1]$ Equation (\ref{help-1})
shows that we have $G(\e,f)=0$
if and only if $f=f_{(1-\e)\P + \e \D_z,\lb}$ for such $\e$.
Our aim is to show the existence of a differentiable
function $\e\mapsto f_\e$ defined on a small interval $[-\d,\d]$ for some $\delta>0$ that satisfies $G(\e,f_\e)=0$ for all
$\e\in [-\d,\d]$. Once we have shown the existence of this function we immediately obtain
$$
\mathit{IF} (z;T,\P) = \frac {\partial f_{\e}} {\partial \e} (0)\, .
$$
For the existence of $\e\mapsto f_\e$ we only have to check by Theorem \ref{implicit-thm}
that $G$ is continuously differentiable
and that $\frac{\partial G}{\partial H}(0,f_{\P,\lb})$ is invertible. Let us start with the first:
an easy computation shows
\begin{equation}\label{r-part-deriv}
\frac{\partial G}{\partial \e}(\e,f) = -\E_{\,\P} L'(Y,f(X))\Phi(X) + \E_{\D_z}L'(Y,f(X)) \Phi(X) \, .
\end{equation}
Moreover, as in the above example we find
\begin{equation}\label{H-part-deriv}
\frac{\partial G}{\partial H}(\e,f) =
 2\lb\, \id_H + \E_{(1-\e)\P + \e \D_z} L''(Y,f(X))\langle \Phi(X),.\rangle\Phi(X)\, .
\end{equation}
Since $H$ has a bounded kernel it is
a simple routine to check that both partial derivatives are continuous. This together with
the continuity of $G$ ensures that $G$ is continuously differentiable,
\emph{cf.} \citet{Akerkar99}.\\
In order to show that $\frac{\partial G}{\partial H}(0,f_{\P,\lb})$ is invertible it suffices to show by the Fredholm
Alternative
that $\frac{\partial G}{\partial H}(0,f_{\P,\lb})$ is injective and that
$$
Ag:= \E_{\,\P} L''(Y,f_{\P,\lb}(X))g(X)\Phi(X)
\, , \qquad g\in H ,
$$
defines a compact operator on $H$.
To show the compactness we have to recall some measure theory, see \citet{ Dudley02}.
Since $X$ is assumed
to be open or closed, it is a Polish space. Furthermore, Borel probability measures on
Polish spaces are {\em regular} by Ulam's theorem, \emph{i.e.}~they can be approximated from inside
by compact sets, \emph{cf.} \citet[p.~180]{Bauer1990}.
In our situation, this means that for all $n\geq 1$ there exists a compact
subset $X_n\subset X$ with $\P_X(X_n)\geq 1-1/n$, where $\P_X$ denotes the marginal distribution
of $\P$ with respect to $X$. We define a sequence of operators $A_n:H\to H$ by
$$
A_n g
:=
\int_{X_n\times Y} L''(y,f_{\P,\lb}(x))g(x)\Phi(x)d\P(x,y)
$$
for all $g\in H$. Let us now show that all $A_n$ are compact.
By the definition of $A_n$
there exists a constant $c>0$ depending on $\lb$, $L''$ and $K$
such that for all $g\in B_H$ we have
\begin{equation}\label{def-An}
A_ng \in c \cdot \overline{\aco \Phi(X_n)}\, ,
\end{equation}
where $\aco\Phi(X_n)$ denotes the absolute convex hull of $\Phi(X_n)$.
Indeed, for discrete probability measures $\P$ relation (\ref{def-An})
follows directly from the definition using the fact
$\inorm{g}\leq K$ for $g\in B_H$. To see the general case recall that by Krein-Milman's theorem
the set of discrete probability measures is $\mathrm{weak}^*$-dense in the set of probability measures. Then
(\ref{def-An}) follows since $H$ has
the approximation property \citep{LindenstraussTzafriri77}.
Furthermore, since $\Phi$ is continuous $\Phi(X_n)$ is compact and hence so is
$\overline{\aco \Phi(X_n)}$. This shows that $A_n$ is compact. In order to
see that $A$ is compact, it therefore suffices to show $\snorm{A_n-A}\to 0$ for $n\to \infty$.
The latter convergence can be easily checked using $\P_X(X_n)\geq 1-1/n$.

It remains to prove that $A$ is injective. To this end
for $g\neq 0$ we find
\begin{eqnarray*}
\bigl\langle (2\lb\, \id_H + A)g, (2\lb\, \id_H + A)g\bigr\rangle
& = &
4\lb^2 \langle g ,g \rangle + 4 \lb \langle g, Ag\rangle + \langle Ag,Ag\rangle \\
& > &
 4 \lb \langle g, Ag\rangle  \\
& = &
4 \lb\bigl\langle g, \E_{\,\P} L''(Y,f_{\P,\lb}(X))g(X)\Phi(X)\bigr\rangle\\
& = &
4 \lb\E_{\,\P} L''(Y,f_{\P,\lb}(X))g^2(X)\\
& \geq  & 0\,
\end{eqnarray*}
Here, the last equation is due to the fact that $B\E_\P h= \E_\P
Bh$ for all $E$-valued functions $h$ and all bounded linear
operators $B:E\to F$ between Banach spaces $E$ and $F$. A much stronger result
is given in \citet[p.~47]{DiUh77}. The last
inequality is true since the second derivative of a convex
function is always nonnegative. Obviously, the above estimate
shows that $\frac{\partial G}{\partial H}(0,f_{\P,\lb}) = 2\lb\,
\id_H + A$ is injective.

We use $\mathit{IF} (z;T,\P) = \frac {\partial f_{\e}} {\partial \e} (0)$
to derive a formula for the influence function,
where $\e\mapsto f_{\e}$ is the function implicitly defined by $G(\e,f)=0$.
The implicit function theorem hence gives
\begin{equation}\label{deriv1}
\mathit{IF} (z;T,\P) = -S^{-1} \circ
\frac{\partial G}{\partial \e}(0,f_{\P,\lb}) \ ,
\end{equation}
where $S:=\frac{\partial G}{\partial H}(0,f_{\P,\lb})$.
$\BlackBox$\\

%-------------------------------------------------------------------------%
\textsc{Proof of Theorem \ref{exist-IF1compact}.}
Since every compact subset of $\R^d$ is closed
and continuous kernels on compact subsets are bounded
the assertion directly follows from Theorem \ref{exist-IF1}.
$\BlackBox$\\

%-------------------------------------------------------------------------%

\textsc{Proof of Theorem \ref{exist-IF2}.} The proof is
similar to that of Theorem \ref{exist-IF1}. However, due to the
extra variable $b$ we have to adapt our approach. As in the proof
of Theorem \ref{exist-IF1} we first point out that the solutions
$(f_{\P,\lb},b_{\,\P,\lb})\in H\times \R$ exist. Again, this can be
seen by a slight modification of the argument used by \cite{Ste03d}.
Now, let us define the map $G:\R\times H\times \R\to
H\times \R$ by
$$
G(\e,f,b) := \Bigl(2\lb f + \E_{(1-\e)\P + \e \D_z} L'(f+b)\Phi,\, \E_{(1-\e)\P + \e \D_z} L'(f+b)\Bigr).
$$
Again, for $\e\in[0,1]$ the definition of $G$ ensures
$$
G(\e,f,b) = \frac {\partial R_{L,{(1-\e)\P + \e \D_z},\lb}^{reg}}{\partial (H\times \R)}(f)\ ,
$$
if we apply the Fr\'echet-Riesz identification $(H\times \R)'= H\times \R$.
Since $R_{L,{(1-\e)\P + \e \D_z},\lb}^{reg}$ is convex for all $\e \in[0,1]$ we have $G(\e,f,b)=0$
if and only if $(f,b)$ minimizes $R_{L,{(1-\e)\P + \e \D_z},\lb}^{reg}$ for such $\e$.
Our aim is to apply the implicit function theorem in the way we did it in the proof of
Theorem \ref{exist-IF1}. However, this time the implicit function theorem will also
ensure the uniqueness of the solution of (\ref{r4b}). Obviously, this is necessary for the
existence of the influence function. In order to apply Theorem \ref{implicit-thm}
we need the partial derivatives of $G$. By an easy computation we find
$$
\frac{\partial G}{\partial \e}(\e,f,b) = -\E_{\,\P} L'(f+b)\Phi(X) + \E_{\D_z}L'(f+b) \Phi(X)
$$
and
$$
\frac{\partial G}{\partial (H\times \R)}(\e,f,b) =
\left(
\begin{array}{ll}
     2\lb\, \id_H + \E_{\,\e} L''(f+b)\langle \Phi,.\rangle\Phi &
     \E_{\,\e} L''(f+b)\Phi \\
     \E_{\,\e} L''(f+b)\Phi &
     \E_{\,\e} L''(f+b)
\end{array}
\right)\, ,
$$
where we use the abbreviation $\E_{\,\e}:=\E_{(1-\e)\P + \e \D_z}$. A routine check shows that both $G$ and the
partial derivatives are continuous and hence $G$ is continuously differentiable.\\
Now, let us fix a solution $(f_{\P,\lb},b_{\,\P,\lb})$ of (\ref{r4b}).
In order to show that the operator
$\frac{\partial G}{\partial (H\times \R)}(0,$ $f_{\P,\lb},b_{\,\P,\lb})$
is invertible it suffices to show by the Fredholm
Alternative
that it 
%$$\frac{\partial G}{\partial (H\times \R)}(0,f_{\P,\lb},b_{\,\P,\lb})$$
is injective and that
$$
A: =
\left(
\begin{array}{ll}
      \E_{\,\P} L''(f_{\P,\lb}+b_{\,\P,\lb})\langle \Phi,.\rangle\Phi &
     \E_{\,\P} L''(f_{\P,\lb}+b_{\,\P,\lb})\Phi \\
     \E_{\,\P} L''(f_{\P,\lb}+b_{\,\P,\lb})\Phi &
     \E_{\,\P} L''(f_{\P,\lb}+b_{\,\P,\lb}) -2\lb
\end{array}
\right)
$$
is a compact operator on $H\times \R$. The latter can be seen using the argument of the proof
of Theorem \ref{exist-IF1}. For the former let us suppose that we have an element $(g,t)\in H\times \R$
with $(2\lb \id_{H\times \R} + A)(g,t)=0$. This is equivalent to the following linear system
of equations
\begin{eqnarray}\label{system1}
    2\lb g + \E_{\,\P} L''(f_{\P,\lb}+ b_{\,\P,\lb})g\, \Phi + t\, \E_{\,\P} L''(f_{\P,\lb}+ b_{\,\P,\lb})\Phi
    & = & 0 \\ \label{system2}
    \E_{\,\P} L''(f_{\P,\lb}+ b_{\,\P,\lb})g + t\, \E_{\,\P} L''(f_{\P,\lb}+ b_{\,\P,\lb}) & = & 0\, .
\end{eqnarray}
Let us first assume that $t=0$. Then the above system yields
$$
2\lb g + \E_{\,\P} L''(f_{\P,\lb}+ b_{\,\P,\lb})g\Phi= 0\, .
$$
Using the techniques of the proof
of Theorem \ref{exist-IF1} we easily find that this implies $g=0$.
Therefore, we may assume without loss of generality that $t=1$.
In order to avoid long notations we introduce the measure
$d\mu := L''(f_{\P,\lb}+ b_{\,\P,\lb})d\P$. Note that $L''>0$ implies
$\mu \neq 0$.
Now, (\ref{system2}) yields
\begin{equation}\label{system3}
\mu (g) = - \mu (\eins)\, ,
\end{equation}
where $\eins$ denotes the constant function with value $1$.
Hence, by (\ref{system1}) we find
\begin{equation}\label{system4}
0 = 2\lb \langle g,g\rangle + \mu(g^2) +  \mu(g) = 2\lb \langle g,g\rangle + \mu(g^2) -  \mu(\eins)\ .
\end{equation}
Furthermore, (\ref{system3}) implies
$$
0 \leq \mu((g+\eins)^2) = \mu(g^2) + 2\mu(g) + \mu(\eins) = \mu(g^2)-\mu(\eins)\, .
$$
This together with (\ref{system4}) yields $2\lb\langle g,g\rangle \leq 0$ and hence $g=0$. However,
the latter contradicts (\ref{system3}) and hence there is no non-trivial solution of the system
(\ref{system1}), (\ref{system2}).\\
Now, the implicit function theorem states in particular, that the solution $(f_{\P,\lb},b_{\,\P,\lb})$
is unique in a small neighborhood of $(f_{\P,\lb},b_{\,\P,\lb})$. Hence it is globally unique
since the set of solutions of (\ref{r4b}) is convex. The rest of the proof follows the ideas
of the proof of Theorem \ref{exist-IF1}.

We use $\mathit{IF} (z;T,\P) = \frac {\partial (f_{\e},b_\e)} {\partial \e} (0)$
to derive a formula for the influence function,
where $\e\mapsto (f_{\e},b_\e)$ is the function implicitly defined by $G(\e,f,b)=0$.
The implicit function theorem hence gives
\begin{equation}\label{deriv2}
\mathit{IF} (z;T,\P) = -S^{-1} \circ
\frac{\partial G}{\partial \e}(0,f_{\P,\lb},b_{\,\P,\lb}) \ ,
\end{equation}
where $S:=\frac{\partial G}{\partial (H\times \R)}(0,f_{\P,\lb},b_{\,\P,\lb})$.
$\BlackBox$\\


%--------------------------------------------%

\textsc{Proof of Theorem \ref{bound1}.} $\quad$ Recall that every
convex function on $\R$ is locally Lipschitz continuous. Let
$|L_{|Y\times[-c,c]}|_1$ denote the Lipschitz constant of $L$
restricted to $Y\times [-c,c]$, $c>0$. We define $\d_\lb :=
\sqrt{(L(-1,0)+L(1,0))/\lb}$ and $K:=\sup_{x\in X}\sqrt{k(x,x)}$.
We fix a distribution $\P$. An easy estimate
\citep{Ste03d} shows $\inorm{f_{\P,\lb}} \leq
\d_\lb K$. We will apply Theorem 28 in \citet{Ste03c}. Since
this result is only formulated for compact subsets $X$ we first have
to check that it is also true in our situation. Indeed
Propositions 26 and 27 in \citet{Ste03c} only uses the
boundedness of the kernel. Furthermore, the proof of Theorem 28
itself only uses the boundedness, too. Hence this theorem actually
holds in our case! Thus, there exists a measurable function
$h:X\times Y\to \R$ with $\inorm h \leq \bigl|L_{|Y\times[-\d_\lb
K,\d_\lb K]}\bigr|_1$ such that for all distributions $\hat \P$ we
have
$$
\snorm {f_{\P,\lb}-f_{\hat \P,\lb}}_H \leq
\frac 1 \lb { \Norm{\E_{\,\P} h\Phi-\E_{\,\hat \P}h\Phi}  }_H   \, ,
$$
where $\Phi:X\to H$ is the feature map of $H$.
Let $\hat \P := (1-\e)\P + \e \tilde \P$.
Then the above inequality yields
\begin{eqnarray*}
\varepsilon^{-1} \, \snorm{f_{(1-\varepsilon)\mathbb{P}+\varepsilon\tilde \P,\lb}-  f_{\P,\lb}}_H
& \leq &
(\varepsilon \lb)^{-1} \, { \snorm{\E_{\,\P} h\Phi-\E_{(1-\e)\P + \e \tilde \P}h\Phi}  }_H \\
& = &
\lb ^{-1} \, \snorm{\E_{\,\P} h\Phi-\E_{\,\tilde \P}h\Phi}_H \\
& \leq &
c_L(\lambda) \, \snorm{\P-\tilde \P}_{\mathcal M}\, ,
\end{eqnarray*}
where
%
\begin{equation}
c_L(\lambda) = \lambda ^{-1} \, K \bigl|L_{|Y\times[-\d_\lb K,\d_\lb K]}\bigr|_1 \,. \label{cL}
\end{equation}
%
This shows the assertion.
$\BlackBox$\\

For the proof of Theorem \ref{bound2} we need the following result.

%------------------------------------------------------%
\begin{lemma}\label{lemma1}
Let $\lambda, \mu \in (0, \infty)$ be fixed constants.
Then the function
$g:(0,1) \to \mathbb{R}$, $g(s)=2\lambda s^2 -2\mu s [1-s^2]^{1/2}+\mu$ has
a global minimum in the point
$$
s_{min}=2^{-1/2} \left( 1-\frac{\lambda}{(\mu^2+\lambda^2)^{1/2}} \right)^{1/2}
$$
and
$$
g(s_{min})=\lambda \left( 1-\frac{\lambda}{(\mu^2+\lambda^2)^{1/2}} \right) +
            \mu \left( 1- \left( 1-\frac{\lambda^2}{\mu^2+\lambda^2} \right)^{1/2} \right) > 0 \, .
$$
\end{lemma}

%-----------------------------------------------------------------%

\textsc{Proof of Lemma \ref{lemma1}.} $\quad$
Let $s \in (0,1)$.
We have $g^{\prime}(s)=4\lambda s -2\mu(1-2s^2)[1-s^2]^{-1/2}$ and
$$
g^{\prime \prime}(s) =
4\lambda + \left(4s-\frac{s(1-2s^2)}{1-s^2} \right) \frac{2\mu}{\sqrt{1-s^2}}
\ge
4\lambda + 3s \frac{2\mu}{\sqrt{1-s^2}} > 0
$$
for all $s \in (0,1)$. Define $a:= \lambda / \left[ \mu^2+\lambda^2 \right ]^{1/2}$.
We have $4\lambda s_{min} > 0$ and
\begin{eqnarray*}
\frac{2 \mu (1-2 s_{min}^2)[1-s_{min}^2]^{-1/2}}{4 \lambda s_{min}} & = &
\frac{\mu}{\lambda} \, \frac{a}{[(1+a)(1-a)]^{1/2}} \\ \nonumber
 = \frac{\mu}{\lambda} \, \left[a^{-2}-1 \right]^{-1/2} & = &
 \frac{\mu}{\lambda} \, \left[ \frac{\mu^2+\lambda^2}{\lambda^2}-1 \right]^{-1/2} = 1 \, .
\end{eqnarray*}
This yields $g'(s_{min})=0$ and we obtain the expression
$
g(s_{min})=\lambda \left[ 1-\frac{\lambda}{(\mu^2+\lambda^2)^{1/2}} \right] +
            \mu \left[ 1- ( 1-\frac{\lambda^2}{\mu^2+\lambda^2} )^{1/2} \right] \,.
$
$\BlackBox$\\

%------------------------------------------------------------------%
\textsc{Proof of Theorem \ref{bound2}.} $\quad$
By rescaling problem (\ref{r4b}) we may assume without loss of generality
that $K:=\sup_{x\in X}\sqrt{k(x,x)}\leq 1$. Recall, that in the proof of Theorem \ref{exist-IF2} we used
$$
\mathit{IF} (z;T,\P) = \frac {\partial (f_{\e},b_\e)} {\partial \e} (0)\, ,
$$
where $\e\mapsto (f_{\e},b_\e)$ was the function implicitly defined by $G(\e,f,b)=0$.
The implicit function theorem hence gives
\begin{equation}\label{deriv}
\mathit{IF} (z;T,\P) = -S^{-1} \circ
\frac{\partial G}{\partial \e}(0,f_{\P,\lb},b_{\,\P,\lb}) \ ,
\end{equation}
where $S:=\frac{\partial G}{\partial (H\times \R)}(0,f_{\P,\lb},b_{\,\P,\lb})$.
Therefore, it suffices to bound the norms of the operators on the right side of (\ref{deriv}).
We begin with
\begin{eqnarray*}
\Norm{\frac{\partial G}{\partial \e}(0,f_{\P,\lb},b_{\,\P,\lb})}
& =&
\snorm{\E_\P L'(f_{\P,\lb}+b_{\,\P,\lb})\Phi - \E_{\D_z}L'(f_{\P,\lb}+b_{\,\P,\lb})\Phi}\\
& \leq &
b_{\,\P,\lb} \, \snorm{\P-\D_z}_{\mathcal M}\, .
\end{eqnarray*}
Furthermore, for $(g,t)\in H\times \R$ we have
\begin{eqnarray*}
S (g,t)
& = &
\left(
\begin{array}{ll}
     2\lb\, \id_H + \E_{\,\P} L''(f_{\P,\lb}+b_{\,\P,\lb})\langle \Phi,.\rangle\Phi &
     \E_{\,\P} L''(f_{\P,\lb}+b_{\,\P,\lb})\Phi \\
     \E_{\,\P} L''(f_{\P,\lb}+b_{\,\P,\lb})\Phi &
     \E_{\,\P} L''(f_{\P,\lb}+b_{\,\P,\lb})
\end{array}
\right)
\left(
\begin{array}{l}
     g\\
     t
\end{array}
\right)\\
& = &
\left(
\begin{array}{l}
     2\lb g + \E_{\,\P} L''(f_{\P,\lb}+b_{\,\P,\lb})g\Phi + t \E_{\,\P} L''(f_{\P,\lb}+b_{\,\P,\lb})\Phi \\
     \E_{\,\P} L''(f_{\P,\lb}+b_{\,\P,\lb})g + t \E_{\,\P} L''(f_{\P,\lb}+b_{\,\P,\lb})
\end{array}
\right) \, .
\end{eqnarray*}
As in the proof of Theorem \ref{exist-IF2} we write $d\mu:=
L''(f_{\P,\lb}+b_{\,\P,\lb})d\P$. Then we find
\begin{equation}\label{h1}
\left\langle S (g,t), (g,t)\right\rangle
 =  2\lb \langle g,g\rangle + \mu(g^2) + 2 t\mu(g) + t^2\mu(\eins) \, .
\end{equation}
Let us suppose that $\snorm{(g,t)}=1$. Then there exist $w \in H$ with $\snorm w=1$ and $s\in[0,1]$
such that $g=sw$ and $t=\pm\sqrt{1-s^2}$.
If $\mu(w)\geq 0$ Equation (\ref{h1}) then yields
\begin{equation}\label{k-h2}
\left\langle S (g,t), (g,t)\right\rangle
\Geq
2\lb s^2  + \frac{s^2\mu^2(w)}{\mu(\eins)}- 2 s\sqrt{1-s^2}\mu(w) + (1-s^2)\mu(\eins)\, .
\end{equation}
Here, we used $\mu(w)\leq \sqrt{\mu(\eins)}\sqrt{\mu(w)}$. It is easy to check that
(\ref{k-h2}) also holds if $\mu(w)\leq 0$.
Now, recall that by the assumption of the
theorem we have $L''\geq a$. This implies $\mu(\eins) \geq a > 0$.
For the special case $s=0$ it follows from (\ref{k-h2}), that
\begin{equation}\label{case-s0}
\left\langle S (g,t), (g,t)\right\rangle \ge \mu(\eins) > a > 0.
\end{equation}
For the special case $s=1$ it follows from (\ref{k-h2}), that
\begin{equation}\label{case-s1}
\left\langle S (g,t), (g,t)\right\rangle \ge 2 \lambda + \frac{\mu^2(w)}{\mu(\eins)}
 \ge
 2 \lambda
 > 0 \, .
\end{equation}
Now, we will consider the case $s \in (0,1)$.
We first minimize the right hand side of (\ref{k-h2}) with respect to $\mu(w)$.
To this end recall that $K\leq 1$ implies $|\mu(w)|\leq \mu(\eins)$.
Therefore, the function
$\mu(w)\mapsto\frac{s^2\mu^2(w)}{\mu(\eins)}- 2 s\sqrt{1-s^2}\mu(w)$ is
minimal if
\begin{equation}\label{k-h3a}
\mu(w) = \min\{\mu(\eins), \mu(\eins)s^{-1}\sqrt{1-s^2}\}\, .
\end{equation}
%
Using (\ref{k-h2}) it follows for $\mu(w)=\mu(\eins)$ that
\begin{equation}\label{k-h3}
\left\langle S (g,t), (g,t)\right\rangle
\Geq
2\lb s^2 + \mu(\eins) \bigl(1-2s\sqrt{1-s^2}\bigr)
=
2\lb s^2 - 2 \mu(\eins) s \sqrt{1-s^2} + \mu(\eins) \, .
\end{equation}
%
Hence, Lemma \ref{lemma1} and (\ref{k-h3}) yield for the case $s \in (0,1)$
and $\mu(w)=\mu(\eins)$ that
%
\begin{equation}\label{case-3}
\left\langle S (g,t), (g,t)\right\rangle \Geq c_{low} \in (0, \infty) \, ,
\end{equation}
where
$$
c_{low} = \lambda \left( 1-\frac{\lambda}{(\mu^2(\eins)+\lambda^2)^{1/2}} \right) +
            \mu(\eins) \left( 1- \left( 1-\frac{\lambda^2}{\mu^2(\eins)+\lambda^2}
        \right)^{1/2} \right) \, .
$$
%
By (\ref{k-h3a}) we finally have to treat the
case $s \in (0,1)$ and $\mu(w) = \mu(\eins)s^{-1}\sqrt{1-s^2}$.
In this case we have $s^2\geq \frac 1 2$ by $\mu(w) \leq \mu(\eins)$. Hence we obtain from
(\ref{k-h2}) that
\begin{equation}\label{case-4}
\left\langle S (g,t), (g,t)\right\rangle
\Geq
2\lb s^2 + (1-s^2)\mu(\eins) - 2 (1-s^2)\mu(\eins) + (1-s^2)\mu(\eins)
\Eq
2\lb s^2
\Geq
\lb \, .
\end{equation}
%
Combining (\ref{case-s0}), (\ref{case-s1}), (\ref{case-3}), and (\ref{case-4}) we obtain
\begin{equation}\label{combi}
\left\langle S (g,t), (g,t)\right\rangle
\Geq
\min \left\{ a, 2\lambda, c_{low}, \lambda \right\} > 0 \, .
\end{equation}
%
Therefore, by the proof of \citet[Prop.~3.2.12]{Pedersen1989} it follows
$$
\snorm{S(g,t)} \geq \min\{ a, \lambda, c_{low}\} \, \snorm{(g,t)}
$$
for all $(g,t)\in H\times \R$, and
$$
\snorm{S^{-1}} \leq \frac{1}{\min\{ a, \lambda, c_{low} \} } \in (0, \infty) \, .
$$
This shows the assertion.
$\BlackBox$\\

%-----------------------------------------------------------------------------------------%
%\bibliographystyle{natbib}
\bibliography{svmrobust}



\end{document}
