Journal of Machine Learning Research 5 (2004) 1007–1034 Submitted 6/03; Revised 05/04; Published 8/04

On Robustness Properties of Convex Risk Minimization Methods for Pattern Recognition

Andreas Christmann christmann@statistik.uni-dortmund.de University of Dortmund Department of Statistics 44221 Dortmund, Germany

Ingo Steinwart ingo@lanl.gov

Modeling, Algorithms and Informatics Group, CCS-3 Mail Stop B256 Los Alamos National Laboratory Los Alamos, NM 87545, USA

Editor: Peter Bartlett

Abstract

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. Keywords: AdaBoost loss function, influence function, kernel logistic regression, robustness, sensitivity curve, statistical learning, support vector machine, total variation

1. Introduction

In statistical learning theory the principle of regularized empirical risk minimization based on convex loss functions plays an important role, see Vapnik (1998). 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 (Hampel et al., 1986, p. 21):

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

\begin{matrix}c \\ ◯ \end{matrix} 2004 Andreas Christmann and Ingo Steinwart.

Christmann and Steinwart

this hope was often drastically wrong; even mild deviations often have much larger effects than were anticipated by most statisticians.

The main aims of robust statistics are the description of the structure best fitting the bulk of the data and the identification of points deviating from this structure or deviating substructures for further treatment, cf. Hampel et al. (1986). Very briefly, a good robust method can be described as follows.

• 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.

• A robust method should have a reasonable high efficiency when the data set was in fact generated by the assumed model.

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 independently generated by the 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 ... from the pattern set by the majority of the data”, see Hampel et al. (1986, p. 25). 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, e.g. typing errors and gross errors, which are errors due to a source of deviations which acts only occasionally but is quite powerful. 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, cf. Hampel et al. (1986, p. 27f). Especially in large data mining problems the data quality is sometimes far from being optimal, cf. Hand et al. (2001) or Hipp et al. (2001). Obviously, it is not the goal to 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.

Robustness of Convex Risk Minimization Methods

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 öffentlicher Versicherer in Düsseldorf, Germany, is investigated by Christmann (2004). 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, i.e. the primary response variable, is not known exactly for all customers. 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. 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, 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, 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, cf. Huber (1981, p. 7f) or Hampel et al. (1986, p. 41). 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 (Huber, 1964, 1981) 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 (Hampel, 1974; Hampel et al., 1986), the finite sample breakdown point proposed by Donoho and Huber (1983), the approach based on least favourable local alternatives (Rieder, 1994), and the regression depth method proposed by Rousseeuw and Hubert (1999).

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â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 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 ℙ can have on the statistical learning process which is specified via the regularized theoretical risk, i.e. the objective functions R_{L,ℙ,λ}^{reg}(.) and R_{L,ℙ,λ}^{reg}(.,.) given in (6) and (7).

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 12 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 (6) and (7). In Section 5 it is shown that the influence function of the solution of (7) and the difference quotient used in the definition of the influence function for (6) can be bounded independently of z and ℙ. 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.

2. 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} ≈ f(x_{i}) between an outcome y_{i} and a vector of explanatory variables x_{i} = (x_{i,1},...,x_{i,k})′∈ ℝ^{d}. The function f is unknown. The estimate for f is used to get predictions of an unobserved outcome y_{new} based on an observed value x_{new}. One needs the implicit assumption that the relationship between x_{new} and y_{new} is—at least almost—the same as in the training data set (x_{i},y_{i}), i = 1,...,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 ℙ 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_{ℙ}(x_{i}) that minimizes the expected loss, i.e.

𝔼_{ℙ}L(Y,f_{ℙ}(X)) = min_{f}𝔼_{ℙ}L(Y,f(X)),  (1)

where 𝔼_{ℙ}L(Y,f(X)) = ∫ L(y,f(x))dℙ(x,y) denotes the expectation of L with respect to ℙ. 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} ∈ Y := {−1,+1}. The straightforward prediction rule is: predict y_{i} = +1 if f(x_{i}) ≥ 0, and predict y_{i} = −1 otherwise. The loss function for the classification error is given by I(y_{i},f(x_{i})) = 𝕀(y_{i}f(x_{i}) < 0)+𝕀(f(x_{i}) = 0)𝕀(y_{i} = −1), where 𝕀 denotes the indicator function. Inspired by the law of large numbers one might estimate f_{ℙ} with the minimizer f_{emp} of the empirical classification error, that is

f_{emp} = argmin_{f} \frac{1}{n} ∑_{i=1}^{n} I(y_{i},f(x_{i})) .  (2)

To avoid over-fitting one usually has to restrict the class of functions f considered in (2). Unfortunately, the classification function I is not convex and the minimization of (2) is often NP-hard, cf. Höffgen et al. (1995). To circumvent this problem, one can replace the classification error function I(y_{i},f(x_{i})) in (2) by a convex upper bound L : Y × ℝ → ℝ cf. Vapnik (1998) and Schölkopf and Smola (2002). Furthermore, using reproducing kernel Hilbert spaces and an additional regularization term have some algorithmic advantages. These modifications lead to the following empirical regularized risks:

f̂_{n,λ} = argmin_{f∈H}λ∥f∥_{H}^{2} + \frac{1}{n} ∑_{i=1}^{n} L(y_{i},f(x_{i})),  (3)

(f̂_{n,λ},b̂_{n,λ}) = arg min_{f∈H,b∈ℝ} λ∥f∥_{H}^{2} + \frac{1}{n} ∑_{i=1}^{n} L(y_{i},f(x_{i}) + b),  (4)

where λ > 0 is a small regularization parameter, H is a reproducing kernel Hilbert space (RKHS) of a kernel k, and b is called offset. The decision functions are sign(f̂_{n,λ}) or sign(f̂_{n,λ} +b̂_{n,λ}). Note that in practice usually (4) is solved while many theoretical papers deal with (3) since the unregularized offset b often causes technical difficulties in the analysis.

In practice the dual problems of (3) and (4) are solved. In these problems the RKHS does not occur explicitly, instead the corresponding kernel is involved. The choice of the kernel k enables

Method  L  L′
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}  −2max(0,1 − v)
Modified Huber  −4v, if v < −1  −4, if v < −1
max(1 − v,0)^{2}, else −2max(0,1 − v), otherwise

Table 1: Loss functions, where v = yf(x) or v = y[f(x) + b], respectively.

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

k(x,x′) = exp(−γ∥x − x′∥^{2}), γ > 0,  (5)

which is a universal kernel on every compact subset of ℝ^{d} in the sense of Steinwart (2001). Furthermore, this kernel is a bounded kernel, as |k(x,x′)| ≤ 1 for all x,x′∈ ℝ^{d}. Polynomial kernels k(x,x′) = (c + ⟨x,x′⟩)^{m} are also popular in practice, but are unbounded for m ≥ 1 and X = ℝ^{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 1. 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 (Wahba, 1999) penalizes misclassifications in a similar way to the SVM, i.e. approximately linearly if v → −∞. The loss function used by AdaBoost increases exponentially for v → −∞, cf. Freund and Schapire (1996), Friedman et al. (2000), and Hastie et al. (2001). The modified Huber’s loss function, cf. Zhang (2004), changes the modified least squares loss such that misclassified points with v < −1 are penalized only linearly.

Two major benefits of using a convex loss function are known:

• For convex loss functions the resulting problems (3) and (4) are 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 Suykens et al. (2002).

• 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 (Tsybakov, 2004) and considers ERM-type algorithms with convex loss functions then learning rates up to n^{−1} are possible! For more information of this recent development we refer to Bartlett et al. (2002), Bartlett et al. (2003) and Bartlett and Mendelson (2002). In particular, this program has been successively applied to support vector machines by Scovel and Steinwart (2003). Learning rates for boosting methods are investigated by Blanchard et al. (2003).

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, c.f. Hampel et al. (1986) and Christmann (1994, 1998).

Problems (3) and (4) can be interpreted as a stochastic approximation of the minimization of the theoretical regularized risk given in (6) or (7), respectively (Vapnik, 1998; Zhang, 2004; Steinwart, 2002a):

f_{ℙ,λ} = argmin_{f∈H}λ∥f∥_{H}^{2} + 𝔼_{ℙ}L(Y,f(X)),  (6)
(f_{ℙ,λ},b_{ℙ,λ}) = arg min_{f∈H,b∈ℝ} λ∥f∥_{H}^{2} + 𝔼_{ℙ}L(Y,f(X) + b).  (7)

The objective functions in (6) and (7) are denoted by R_{L,ℙ,λ}^{reg}(.) and R_{L,ℙ,λ}^{reg}(.,.) in the sequel.

Steinwart (2002b) shows that SVM’s are universally consistent, i.e. the classification error of f̂_{n,λ}(.) converges to the optimal Bayes error 𝔼_{ℙ}I(Y,f_{ℙ}(X)) in probability, provided that the reproducing kernel Hilbert space is dense in the space C(X), X ⊂ ℝ^{d} compact, and λ = λ_{n} tends “slowly” to 0 for n → ∞. Zhang (2004) improves this result by showing that for many convex loss functions the classifiers based on (3) are universally consistent if λ_{n} → 0 and λ_{n}n → ∞. Steinwart (2002a) characterizes the loss functions which lead to universally consistent classifiers and establishes universal consistency for classifiers based on (3) and (4). 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 Steinwart (2001), Chen et al. (2003), and Scovel and Steinwart (2003). Moreover, Steinwart (2003) gives lower asymptotical bounds on the number of support vectors, i.e. on the data points with non-vanishing coefficients, and investigates the asymptotic behavior of f̂_{n,λ}(.) in terms of the loss function L. As a by-product it also turns out that the solutions of (3) and (6) are unique. The same holds for the RKHS part of the solutions of (4) and (7). Upper bounds on the number of support vectors can be found in Steinwart (2004). Schölkopf and Smola (2002) describe other support vector machines and give an overview on algorithms to solve the minimization problems corresponding to SVMs.

3. Robustness

In the statistical literature different criteria have been proposed to define the notion of robustness in a mathematical way, e.g. the minimax approach (Huber, 1964), the sensitivity curve (Tukey, 1977), the approach based on influence functions (Hampel, 1974; Hampel et al., 1986), the maxbias curve (Huber, 1964; Hampel et al., 1986), and the finite sample breakdown point (Donoho and Huber, 1983).

In this paper, we mainly use the approach based on the influence function proposed by Hampel (1974) and Hampel et al. (1986). We will consider a map T which assigns to every distribution ℙ on a given set Z an element T (ℙ) of a given Banach space E. In the case of the convex risk minimization methods given in (6) and (7) E equals the RKHS and T (ℙ) = f_{ℙ,λ} or T (ℙ) = (f_{ℙ,λ},b_{ℙ,λ}), respectively. The book by Huber (1981, p. 34ff) is a standard reference for Gâteaux and Fréchet derivatives in the context of robust statistics.

Definition 1 (Influence function) The influence function of T at a point z for a distribution ℙ is the special Gâteaux derivative (if it exists)

IF(z;T,ℙ) = lim_{ε↓0} \frac{T ((1 − ε)ℙ + εΔ_{z}) − T (ℙ)}{ε} ,  (8)

where Δ_{z} is the Dirac distribution at the point z such that Δ_{z}({z}) = 1.

The influence function has the interpretation, that it measures the impact of an (infinitesimal) small amount of contamination of the original distribution ℙ in direction of a Dirac distribution located in the point z on the theoretical quantity of interest T (ℙ). Therefore, in the robustness approach based on influence functions it is desirable that a statistical method which can be written as T (ℙ) has a bounded influence function. If T fulfills some regularity conditions, it can be linearized near ℙ in terms of the influence function via

T (ℙ^{∗}) = T (ℙ) + ∫ IF(z;T,ℙ)[ℙ^{∗}(dz) − ℙ(dz)] + ... ,

where ℙ^{∗} is a probability distribution near ℙ, cf. Huber (1981, p. 14). 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 Hampel et al. (1986, p. 93) can be interpreted as a finite sample version of the influence function, see (10). The sensitivity curve measures the impact of just one additional data point z on the empirical quantity of interest, i.e. on the estimate T_{n}.

Definition 2 (Sensitivity curve) The sensitivity curve of an estimator T_{n} at a point z given a data set z_{1},...,z_{n−1} is defined by

SC_{n}(z;T_{n}) = n(T_{n}(z_{1},...,z_{n−1} ,z) − T_{n−1} (z_{1},...,z_{n−1} )).  (9)

If the estimator T_{n} is defined via T (ℙ_{n}), where ℙ_{n} denotes the empirical distribution of the data points z_{1},...,z_{n}, then we have for ε_{n} = 1/n:

SC_{n}(z;T_{n}) = \frac{T ((1 − ε_{n})ℙ_{n−1} + ε_{n}Δ_{z}) − T (ℙ_{n−1} )}{ε_{n}} .  (10)

Of theoretical as well as of practical importance is also the notion of maxbias, which measures the maximum bias T (Q)−T (ℙ) within a neighborhood of probability distributions Q near ℙ. In robust statistics the so-called contamination (or gross-error) neighborhood (defined below), cf. Huber (1981), is quite common for the following three reasons. It allows a good interpretation because it contains mixture distributions with respect to the ’true’ distribution ℙ 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.

Definition 3 (Maxbias) Let ℙ be a fixed probability distribution on X ×Y. A contamination neighborhood of ℙ is given by

N_{ε}(ℙ) = \{ Q = (1 − ε)ℙ + εℙ̃; ℙ̃ is any distribution onX × Y, 0 ≤ ε < \frac{1}{2}\} .

The maxbias (or supremum bias) of T at the distribution ℙ with respect to the contamination neighborhood N_{ε}(ℙ) is defined by

maxbias(ε;T,ℙ) = sup_{Q∈N_{ε}(ℙ)}∥T (Q) − T (ℙ)∥.

4. Existence of the Influence Function

In this section we give sufficient conditions for the existence of the influence function for classifiers based on (6) and (7), whereas the next section will show that the influence function is bounded under weak conditions. Most of our results are valid for any distribution ℙ on X × Y. Therefore, they are also valid for the special case of the empirical distribution ℙ_{n} = \frac{1}{n}∑ _{i=1}^{n} Δ_{(x_{i},y_{i})}, i.e. for a given data set, and for the empirical regularized risks defined in (3) and (4).

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 → F be a map between two Banach spaces E and F. We say that G is (Fréchet)- differentiable in x_{0} ∈ E if there exists a bounded linear operator A: E → F and a function φ: E → F with \frac{φ(x)}{∥x∥} → 0 for x → 0 such that

G(x_{0}+ x) − G(x_{0}) = Ax + φ(x)  (11)

for all x ∈ E. It turns out that A is uniquely determined by (11). We hence write G′(x) := \frac{∂G}{∂E}(x) := A. The map G is called continuously differentiable if the map x ↦ 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 Φ : X → H, i.e. Φ(x) = k(x,.). Furthermore, let ℙ be a probability measure on X × Y and h : Y × X → ℝ be a function which is continuous in its second variable x ∈ X. Then the Bochner-integral 𝔼_{ℙ}h(Y,X)Φ(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 ×Y. For a precise definition of Bochner-integrals we refer to Diestel and Uhl (1977). Note that in our special situation we can also interpret 𝔼_{ℙ}h(Y,X)Φ(X) as an element of the dual space H′by the Fréchet-Riesz theorem, i.e. 𝔼_{ℙ}h(Y,X)Φ(X) acts as a functional on H via w ↦ ⟨𝔼_{ℙ}h(Y,X)Φ(X),w⟩. Finally, we have to consider Bochner-integrals of the form 𝔼_{ℙ}h(Y,X)⟨Φ(X), .⟩Φ(X) which define bounded linear operators on H by the map w ↦ 𝔼_{ℙ}h(Y,X)⟨Φ(X),w⟩Φ(X).

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

Theorem 4 Let L: Y × ℝ → [0,∞) be a convex and twice continuously differentiable loss function. Furthermore, let X ⊂ ℝ^{d} be a closed or open subset, H be a RKHS of a bounded continuous kernel on X and ℙ be a distribution on X × Y. We define G: ℝ × H → H by

G(ε,f) := 2λf + 𝔼_{(1−ε)ℙ+εΔ_{z}} L′(Y,f(X))Φ(X)

which implies

\frac{∂G}{∂ε}(0,f_{ℙ,λ}) = −𝔼_{ℙ}[L′(Y,f_{ℙ,λ}(X))Φ(X)] + L′(z_{y},f_{ℙ,λ}(z_{x}))Φ(z_{x}).

Furthermore, we define S: H → H by

S:= \frac{∂G}{∂H}(0,f_{ℙ,λ}) = 2λid_{H} + 𝔼_{ℙ}L′′(Y,f_{ℙ,λ}(X))⟨Φ(X),.⟩Φ(X).

Then the influence function of the classifiers based on (6) exists for all z = (z_{x},z_{y}) ∈ X × Y and is given by

IF(z;T,ℙ) = −S^{−1} ∘ \frac{∂G}{∂ε}(0,f_{ℙ,λ}) .  (12)

Remark 5 The influence function derived in Theorem 4 depends on the point z = (z_{x},z_{y}), where the point mass contamination takes place, only by the term L′(z_{y},f_{ℙ,λ}(z_{x}))Φ(z_{x}).

In practice the set X is usually a bounded and closed subset of ℝ^{d} 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.

Theorem 6 Let L: Y × ℝ → [0,∞) be a convex and twice continuously differentiable loss function. Furthermore, let X ⊂ ℝ^{d} be compact, H be a RKHS of a continuous kernel on X and ℙ be a distribution on X × Y. Then the influence function of the classifiers based on (6) exists for all z ∈ X × Y.

Remark 7 By a simple modification of the proof of the above theorem we actually find that the special Gâteaux derivative of T : ℙ ↦ f_{ℙ,λ} exists for every direction, i.e.

lim_{ε↓0} \frac{f_{(1−ε)ℙ+εℙ̃,λ} − f_{ℙ,λ}}{ε}

exists for all distributions ℙ and ℙ̃ on X × Y provided that the assumptions of Theorem 4 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.

The following theorem shows the existence of the influence function for classifiers based on (7). Since the offset b_{ℙ,λ} can be infinite for certain loss functions if ℙ is degenerate, i.e ℙ({(y,x) : x ∈ 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}),...,(1,x_{n})), or ((−1,x_{1}),...,(−1,x_{n})), respectively.

Theorem 8 Let L: Y × ℝ → [0,∞) be a convex and twice continuously differentiable loss function with L′′> 0. Furthermore, let X ⊂ ℝ^{d} be open or closed, H be a RKHS of a continuous kernel on X and ℙ be a non-degenerate distribution on X × Y. We define G: ℝ × H × ℝ → H × ℝ by

G(ε,f,b) := ( 2λf + 𝔼_{(1−ε)ℙ+εΔ_{z}} L′(Y,f(X) + b)Φ(X), 𝔼_{(1−ε)ℙ+εΔ_{z}} L′(Y,f(X) + b))

which implies

\frac{∂G}{∂ε}(0,f_{ℙ,λ},b_{ℙ,λ}) = −𝔼_{ℙ}[L′(Y,f_{ℙ,λ}(X) + b_{ℙ,λ})Φ(X)] + L′(z_{y},f_{ℙ,λ}(z_{x}) + b_{ℙ,λ})Φ(z_{x}).

Furthermore, for S:= \frac{∂G}{∂(H×ℝ)} (0,f_{ℙ,λ},b_{ℙ,λ}) we have

S = ( \begin{matrix}2λid_{H} + 𝔼_{ℙ}L′′(Y,f_{ℙ,λ}(X) + b_{ℙ,λ})⟨Φ(X),.⟩Φ(X) & 𝔼_{ℙ}L′′(Y,f_{ℙ,λ}(X) + b_{ℙ,λ})Φ(X) \\ 𝔼_{ℙ}L′′(Y,f_{ℙ,λ}(X) + b_{ℙ,λ})Φ(X) & 𝔼_{ℙ}L′′(Y,f_{ℙ,λ}(X) + b_{ℙ,λ}) \end{matrix} ) .

Then the influence function of the classifiers based on (7) exists for all z = (z_{x},z_{y}) ∈ X × Y and is given by

IF(z;T,ℙ) = −S^{−1} ∘ \frac{∂G}{∂ε}(0,f_{ℙ,λ},b_{ℙ,λ}) .  (13)

Remark 9 The influence function derived in Theorem 8 depends on the point z = (z_{x},z_{y}), where the point mass contamination takes place, only by the term L′(z_{y},f_{ℙ,λ}(z_{x}) + b_{ℙ,λ})Φ(z_{x}). Hence loss functions L and kernels k such that L′ and the feature map Φ are bounded are of special interest from the view point of robust statistics.

Remark 10 As in the case of problem (6) a slight modification of the proof gives that T : ℙ ↦ (f_{ℙ,λ},b_{ℙ,λ}) is special Gâteaux differentiable.

Remark 11 Considering the loss functions in Table 1 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.

5. 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 independently of z and ℙ for classifiers based on (6) and (7). For the formulation of our results we need to recall that the norm of total variation of a signed measure μ on a space X is defined by

∥μ∥_{M} := |μ|(X) := sup{ ∑_{i=1}^{n} |μ(A_{i})|: A_{1},...,A_{n} is a partition of X} .

For more information on this norm we refer to Brown and Pearcy (1977).

Our first result bounds the difference quotient in the definition of the influence function for classifiers based on (6). For practical applications Theorem 12 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 Steinwart (2003) applies to all six loss functions given in Table 1 because differentiability of L is not assumed.

Theorem 12 Let L : Y × ℝ → [0,∞) be a continuous and convex loss function. Furthermore, let X ⊂ ℝ^{d} and H be a RKHS of a bounded, continuous kernel on X. Then for all λ > 0 there exists a constant c_{L}(λ) > 0 explicitly given in (27) such that for all distributions ℙ and ℙ̃ on X × Y we have

∥ \frac{f_{(1−ε)ℙ+εℙ̃,λ} − f_{ℙ,λ}}{ε} ∥_{H} ≤ c_{L}(λ) ∥ℙ − ℙ̃∥_{M} , ε > 0.

Remark 13 The above theorem also gives uniform bounds for Tukey’s sensitivity curve of f. Consider the special case that ℙ is equal to the empirical probability measure of (n−1) data points, i.e. ℙ_{n−1} = \frac{1}{n−1} ∑ _{i=1}^{n−1} Δ_{(x_{i},y_{i})}, and that ℙ̃ is equal to the Dirac measure Δ_{(x,y)}in some point (x,y) ∈ X ×Y. Let ε = \frac{1}{n}. Under the assumptions of Theorem 12 it follows from (10), that

n∥f_{(1−ε)ℙ_{n−1} +εΔ_{(x,y)},λ} − f_{ℙ_{n−1} ,λ}∥_{H} ≤ c_{L}(λ) ∥ℙ_{n−1} − Δ_{(x,y)}∥_{M} , ε > 0.

Essentially, this result has already been established by Bousquet and Elisseeff (2002).

Remark 14 Because no assumptions on ℙ̃ are made in Theorem 12, an upper bound for the maxbias of f_{ℙ,λ} (see Definition 3) for such machine learning methods is given by

maxbias(ε;f,ℙ) = sup_{Q∈N_{ε}}∥f_{Q,λ}− f_{ℙ,λ}∥ ≤ εc_{L}(λ) sup_{ℙ̃∈P}∥ℙ − ℙ̃∥_{M} ≤ 2c_{L}(λ)ε,

where ε ∈ (0,1/2), and P denotes the set of all probability measures on X × Y. As no assumptions are made for ℙ, this result is valid for empirical distributions too. Consider the empirical distribution ℙ_{n} defined by given data set (x_{i},y_{i}) ∈ X × Y with n data points. Then the maxbias of f_{ℙ_{n},λ} in a contamination neighborhood N_{ε}(ℙ_{n}) is at most 2c_{L}(λ)ε, where ε ∈ (0,1/2).

Unfortunately, using the estimate of Steinwart (2003) does not give any meaningful result for classifiers based on (7). However, under some additional assumptions on L we can still bound the influence function.

Theorem 15 Let L: Y ×ℝ → [0,∞) be a convex and twice continuously differentiable loss function with a ≤ L′′≤ b for some a,b > 0. Furthermore, let X ⊂ ℝ^{d} be open or closed, H be a RKHS of a continuous kernel on X, and T_{λ}(ℙ) = (f_{ℙ,λ},b_{ℙ,λ}) be given by (7). Then for all λ > 0 there exists a constant c_{L}(λ) > 0 such that for all non-degenerated distributions ℙ on X × Y and all z ∈ X × Y we have

∥IF(z;T,ℙ)∥_{H×ℝ} ≤ c_{L}(λ) ∥ℙ − Δ_{z}∥_{M} .

Remark 16 Theorem 15 applies to (7) with the least squares loss function. However, Theorem 15 covers neither the logistic regression loss function as we only have L′′≥ 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 ℙ with

a ≤ ∫ L′′(Y,f_{ℙ,λ}(X) + b_{ℙ,λ})dℙ ≤ b  (14)

for some b ≥ a > 0. A simple sufficient condition for the latter can be derived by the proof of Steinwart (2002a, Lemma II.6): let A_{y}^{ρ} := {x ∈ X : ℙ(y|x) > ρ}, y ∈ Y, ρ > 0, and α_{ℙ}(ρ) := ρmin{ℙ_{X}(A_{1}^{ρ}),ℙ_{X}(A_{−1}^{ρ})}. Then fixing λ > 0, a twice continuously differentiable L and a threshold α > 0 there exist b ≥ a > 0 such that every ℙ with α_{ℙ}(ρ) ≥ α for some ρ > 0 satisfies (14). Note that the assumption α_{ℙ}(ρ) ≥ α guarantees that the two classes of ℙ are “balanced”.

Remark 17 As mentioned in Remark 10 the map T : ℙ ↦ (f_{ℙ,λ},b_{ℙ,λ}) is special Gâteaux differentiable. A simple modification of the proof of Theorem 15 shows that the special Gâteaux derivative of T can be uniformly bounded.

Remark 18 Consider the case that ℙ and ℙ̃ are probability measures with densities p and p̃with respect to some dominating measure ν. Then, the last two theorems also give bounds of the influence functions and the sensitivity curve in terms of the Hellinger metric H(ℙ,ℙ̃) = [∫(\sqrt{p}−\sqrt{p̃})^{2}dν]^{1/2}. This follows from a relationship between the norm of total variation and the Hellinger metric:

∥ℙ − ℙ̃∥_{M} ≤ 2H(ℙ,ℙ̃) ≤ 2∥ℙ − ℙ̃∥_{M}^{1/2}.

Note that the bounds for the difference quotient in Theorem 12 and for the influence function in Theorem 15 converge to infinity, if λ converges to 0 and ∥ℙ−ℙ̃∥_{M} > 0 or ∥ℙ−Δ_{z}∥_{M} > 0. However, λ converging to 0 has the interpretation that misclassifications are penalized by constants C tending to ∞. Therefore, decreasing values of λ correspond to a decreasing amount of robustness, which was to be expected. The quantity λ 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, e.g. Hubertype M-estimators in location or regression models. Consider the Huber-type M-estimator (Huber, 1964) in a univariate location model, where all data points are realizations from n independent and identically distributed random variables with some distribution function F (· − θ), where θ ∈ ℝ is unknown. Huber’s robust M-estimator with tuning constant b ∈ (0,∞) has an influence function proportional to ψ_{b}(z) = min{b,max{z − b}}, cf. Hampel et al. (1986, p. 104f). For all b ∈ (0,∞) the influence function is bounded by ±b. However, the bounds tend to ±∞ if b → ∞, and Huber’s M-estimator with b = ∞ is equal to the non-robust maximum likelihood estimator which has an unbounded influence function. Therefore, the quantity 1/λ (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.

6. 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 μ = (0,0) and covariance matrix Σ. 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 θ = (−1,1)′, b = 0.5, such that P(Y_{i} = +1) = [1 + exp(−(x′_{i}θ + b))]^{−1} and P(Y_{i} = −1) = 1−P(Y_{i} = +1). The computations were done using the software SVM^{light}developed by Joachims (1999). SVM^{light} solves the dual program corresponding to the primal optimization problem

argmin_{f∈H,b∈ℝ} \frac{1}{2Cn}||f||_{H}^{2} + \frac{1}{n} ∑_{i=1}^{n} ξ_{i}
such that  y_{i}(f(x_{i}) + b) ≥ 1 − ξ_{i}
ξ_{i} ≥ 0.

(15)

We consider two popular kernels: a Gaussian radial basis function kernel with parameter γ, see (5) and a linear kernel. Appropriate values for γ and for the constant C (or λ) are important for the SVM and are often determined by cross validation, cf. Schölkopf and Smola (2002, p. 217). 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

γ ∈ {0.05,0.1,0.25,0.5,0.75,1,1.5,2,3,4,5,10,20}

and

C ∈ {0.5,0.75,1,1.25,1.5,1.75,2,5,10,20}.

As a result of the cross validation, the tuning parameters for the SVM with RBF kernel were set to γ = 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 λ = (2Cn)^{−1} = 5 × 10^{−4} for the RFB kernel and λ = (2Cn)^{−1} = 0.001 for the linear kernel. Please note that such small values of λ will result in relatively large bounds.

Figure 1 shows the sensitivity curves of f̂+ b̂:= f̂_{n,λ} + b̂_{n,λ}, 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 f̂+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 2 where plots of f̂+ 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 f̂+ b̂approximately equal to zero outside a central region, as almost all data points are lying inside the central region. Comparing the plots of f̂+ 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 f̂+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 f̂+ b̂ estimated by a SVM with a linear kernel over a broader region than for an SVM with an RBF kernel.

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 3 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 ŷ= +1 outside the central region, if a RBF kernel is used, see Figure 4. In contrast to that, using a linear kernel results in estimated responses ŷ= +1 or ŷ= −1 of the additional data point depending on the affine half-space in which the x−value of z is lying. Finally, let us study the impact of an additional data point located at z = (x,y), where y = +1, on the estimated parameters b̂and θ̂, see Figure 5. We vary z over a grid in the x−coordinates in the same manner as before. As the plots for θ̂_{1} and θ̂_{2} are looking very similar, we only show the latter. Note that the axes are not identical in Figure 5 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 Figure 1: Sensitivity function of f̂+ 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.

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.

7. Concluding Remarks

In this paper, we used the influence function approach of robust statistics (Hampel et al., 1986) 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 ℙ in direction of a Dirac distribution located in the point z on the theoretical quantity of interest T (ℙ). 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 ℙ and the point z of the Dirac distribution Δ_{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â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 12 covers the SVM as a special case. We gave some numerical results for Figure 2: Plot of f̂+ 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.

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 f̂+ b̂and for the estimated coefficients (θ̂,b̂). Varying the position of one additional data point had a smooth and local impact on f̂+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 Rousseeuw and Hubert (1999) see Christmann and Rousseeuw (2001) and Christmann et al. (2002).

Figure 3: 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.

Figure 4: 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.

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

Acknowledgments

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 Figure 5: Sensitivity function for θ̂ and b̂, respectively. Upper left: Sensitivity function for θ̂_{2}, RBF

kernel. Upper right: Sensitivity function for θ̂_{2}, linear kernel. Lower left: Sensitivity function for b̂, RBF kernel. Lower right: Sensitivity function for b̂, linear kernel.

simulation”) are gratefully acknowledged. We thank three anonymous referees and the editor for helpful remarks on an earlier version of the paper.

Appendix A. Mathematical Background

In Appendix A we list some facts from functional analysis, which are used in Appendix B to prove our theorems.

Since our proofs are heavily based on the calculus in (infinite dimensional) Banach spaces we first recall the basic facts, see e.g. Akerkar (1999), Brown and Pearcy (1977), and Yosida (1974). To this end let G: E → F be a map between two Banach spaces E and F. Recall, that we say that G is (Fréchet)-differentiable in x_{0} ∈ E if there exists a bounded linear operator A : E → F and a function φ: E → F with \frac{φ(x)}{∥x∥} → 0 for x → 0 such that

G(x_{0}+ x) − G(x_{0}) = Ax + φ(x)  (16)

for all x ∈ E. It turns out that A is uniquely determined by (16). As in Section 4 we hence write G′(x) := \frac{∂G}{∂E}(x) := A. Again, the map G is called continuously differentiable if the map x ↦ G′(x) exists on E and is continuous. Analogously we define continuous differentiability on open subsets of E.

Unlike 1-dimensional derivates general Fréchet derivates suffer from some notational difficulties. For example, the derivate G′(x) itself is a map for every x and thus G′(x) is described by y ↦ G′(x)y. Furthermore, considering partial derivates can cause notational problems too. Indeed, if e.g. id_{E} is the identity of E we have

x = id′(x)x = \frac{∂id}{∂E}(x)x = \frac{∂id(x)}{∂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

(G_{2}∘ G_{1})′(x) = G′_{2}(G_{1}(x)) ∘ G′_{1}(x)

for G_{1} : E_{1} → E_{2}, G_{2} : E_{2} → E_{3} whenever all derivates exist in the above equation. Furthermore, for a bounded linear map A: E → F we have A′(x) = A for all x ∈ E. If G(f) := ∥f∥_{H}^{2} for all elements f of a Hilbert space H we find G′= 2id_{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 ℙ be a probability measure on a subset X ⊂ ℝ^{d} and H be a RKHS of bounded continuous functions over X with feature map Φ : X → H, i.e. Φ(x) := k(x,.), where k is the kernel of H. We consider the map G: H → ℝ which is defined by Gf := 𝔼_{ℙ}L ∘ f for all f ∈ H and a twice continuously differentiable function L : ℝ → ℝ. In order to compute the derivate of this map we decompose G into G = B ∘ A ∘ I, where I : H → C_{b}(X) is the canonical embbeding w ↦ ⟨w,Φ(.)⟩ of H into the space of all bounded continuous functions C_{b}(X), A : C_{b}(X) → C_{b}(X) is defined by f ↦ L∘f and B: C_{b}(X) → ℝ is the functional f ↦ 𝔼_{ℙ}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 ∈ H. Analogously, the linearity of B gives B′(f)g = 𝔼_{ℙ}g for all f,g ∈ C_{b}(X). As shown in the book of Akerkar (1999), we also have A′(f)g = g · (L′∘ f) for all f,g ∈ C_{b}(X), i.e. A′is the multiplication operator with respect to L′∘ f. Applying the chain rule to A ∘ I we hence find

(A ∘ I)′(v)w = (A′(I(v)) ∘ I′(v))w = L′∘ (Iv) · (Iw)

for all v,w ∈ H. As we see the brackets play an important role for the mechanic evaluation of these derivatives. Another application of the chain rule gives

G′(v)w = (B′(A ∘ I(v)) ∘ (A ∘ I)′(v))w = B′(A ∘ I(v))((A ∘ I)′(v)w)
= 𝔼_{ℙ}(A ∘ I)′(v)w
= 𝔼_{ℙ}L′∘ (Iv) · (Iw)

for all v,w ∈ H. Note that by definition G′(v) : H → ℝ is a bounded functional. By the theorem of Fréchet-Riesz such functionals can be represented by elements of H via the mapping v ↦ ⟨v,.⟩. In our situation we can directly compute this representation: for v,w ∈ H we have

⟨𝔼_{ℙ}L′∘ (Iv)Φ,w⟩ = 𝔼_{ℙ}L′∘ (Iv)⟨Iv,w⟩ = 𝔼_{ℙ}L′∘ (Iv) · (Iw),

i.e. 𝔼_{ℙ}L′∘(Iv)Φ is a representation of G′(v). Note that 𝔼_{ℙ}L′∘(Iv)Φ is a H-valued Bochner-integral. For finite dimensional spaces ℝ^{n} the ℝ^{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 Φ 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 Diestel and Uhl (1977) or Yosida (1974).

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échet-Riesz representation of G′. Analogously to the above considerations we decompose G′. To this end B : C_{b}(X) → H denotes the operator defined by Bf := 𝔼_{ℙ}fΦ for all f ∈ C_{b}(X). Furthermore, A: C_{b}(X) → C_{b}(X) is the operator Af := L′∘ f, f ∈ C_{b}(X). Using the Fréchet-Riesz representation of G′we then find G′= B ∘ A ∘ I. Now observe that B is linear. Therefore we have B′(f)g = 𝔼_{ℙ}gΦ for all g ∈ C_{b}(X). Moreover, we find (A ∘ I)′(v)w = L′′∘ (Iv)Iw for all v,w ∈ H as above. Using the chain rule this gives

G′′(v)w = B′′(A ∘ I(v))((A ∘ I)′(v)w) = 𝔼_{ℙ}(A ∘ I)′(v)wΦ = 𝔼_{ℙ}L′′∘ (Iv)IwΦ

for all v,w ∈ H.

Our proofs also heavily rely on the implicit function theorem in Banach spaces. Therefore, we recall a simplified version of this theorem (Akerkar, 1999; Zeidler, 1986). Here and throughout this appendix B_{E} denotes the open unit ball of a Banach space E.

Theorem 19 (Implicit function theorem) Let E,F be Banach spaces and G : E × F → F be a continuously differentiable map. Suppose that we have (x_{0},y_{0}) ∈ E × F such that G(x_{0},y_{0}) = 0 and \frac{∂G}{∂F}(x_{0},y_{0}) is invertible. Then there exists a δ > 0 and a continuously differentiable map f : x_{0}+ δB_{E} → y_{0}+ δB_{F} such that for all x ∈ x_{0}+ δB_{E}, y ∈ y_{0}+ δB_{F} we have

G(x,y) = 0  if and only if  y = f(x).

Moreover, the derivative of f is given by

f′(x) = −( \frac{∂G}{∂F}(x,f(x))) ^{−1} \frac{∂G}{∂E}(x,f(x)).

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, (Cheney, 2001) turns out to be very helpful:

Theorem 20 (Fredholm Alternative) Let E be a Banach space and S: E → E be a compact operator. Then id_{E}+ S is surjective if and only if it is injective.

We also need the Krein-Milman theorem, see Yosida (1974, p. 363) or Brown and Pearcy (1977, p. 309).

Theorem 21 (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.

Appendix B. Proofs of the Theorems

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.

Proof of Theorem 4. Let us first check that the solution f_{ℙ,λ} exists in our situation. Indeed, in the proof of the existence statement by Steinwart (2002a) the compactness of X is only used to ensure K := ∥I : H → ℓ_{∞} (X)∥ < ∞, where ℓ_{∞} (X) denotes the space of all bounded functions f : X → ℝ equipped with the supremum norm and I is the canonical embbeding. The finiteness of this norm, however, characterizes bounded kernels. Therefore, the existence statement by Steinwart (2002a) is true in our case too.

Now, let Φ : X → H be the feature map of H as in the above example. Our analysis heavily rely on the map G: ℝ × H → H that is defined by

G(ε,f) := 2λf + 𝔼_{(1−ε)ℙ+εΔ_{z}} L′(Y,f(X))Φ(X).

Note that for ε ∉ [0,1] the H-valued expectation is with respect to a signed measure. For these measures we refer to Dudley (2002). Now as in the above example, for ε ∈ [0,1] we obtain

G(ε,f) = \frac{∂R_{L,(1−ε)ℙ+εΔ_{z} ,λ}^{reg}}{∂H}(f).  (17)

Since f ↦ R_{L,(1−ε)ℙ+εΔ_{z} ,λ}^{reg}(f) is convex for all ε ∈ [0,1] Equation (17) shows that we have G(ε,f) = 0 if and only if f = f_{(1−ε)ℙ+εΔ_{z},λ} for such ε. Our aim is to show the existence of a differentiable function ε ↦ f_{ε} defined on a small interval [−δ,δ] for some δ > 0 that satisfies G(ε,f_{ε}) = 0 for all ε ∈ [−δ,δ]. Once we have shown the existence of this function we immediately obtain

IF(z;T,ℙ) = \frac{∂f_{ε}}{∂ε} (0).

For the existence of ε ↦ f_{ε} we only have to check by Theorem 19 that G is continuously differentiable and that \frac{∂G}{∂H}(0,f_{ℙ,λ}) is invertible. Let us start with the first: an easy computation shows

\frac{∂G}{∂ε}(ε,f) = −𝔼_{ℙ}L′(Y,f(X))Φ(X) + 𝔼_{Δ_{z}}L′(Y,f(X))Φ(X).  (18)

Moreover, as in the above example we find

\frac{∂G}{∂H}(ε,f) = 2λid_{H} + 𝔼_{(1−ε)ℙ+εΔ_{z}} L′′(Y,f(X))⟨Φ(X),.⟩Φ(X).  (19)

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, cf. Akerkar (1999). In order to show that \frac{∂G}{∂H}(0,f_{ℙ,λ}) is invertible it suffices to show by the Fredholm Alternative that \frac{∂G}{∂H}(0,f_{ℙ,λ}) is injective and that

Ag:= 𝔼_{ℙ}L′′(Y,f_{ℙ,λ}(X))g(X)Φ(X), g ∈ H,

defines a compact operator on H. To show the compactness we have to recall some measure theory, see Dudley (2002). Since X is assumed to be open or closed, it is a Polish space. Furthermore, Borel probability measures on Polish spaces are regular by Ulam’s theorem, i.e. they can be approximated from inside by compact sets, cf. Bauer (1990, p. 180). In our situation, this means that for all n ≥ 1 there exists a compact subset X_{n} ⊂ X with ℙ_{X}(X_{n}) ≥ 1 − 1/n, where ℙ_{X} denotes the marginal distribution of ℙ with respect to X. We define a sequence of operators A_{n}: H → H by

A_{n}g:= ∫_{X_{n}×Y}L′′(y,f_{ℙ,λ}(x))g(x)Φ(x)dℙ(x,y)

for all g ∈ 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 λ, L′′and K such that for all g ∈ B_{H} we have

A_{n}g ∈ c · \overline{acoΦ(X_{n})} ,  (20)

where acoΦ(X_{n}) denotes the absolute convex hull of Φ(X_{n}). Indeed, for discrete probability measures ℙ relation (20) follows directly from the definition using the fact ∥g∥_{∞} ≤ K for g ∈ B_{H}. To see the general case recall that by Krein-Milman’s theorem the set of discrete probability measures is weak^{∗}-dense in the set of probability measures. Then (20) follows since H has the approximation property (Lindenstrauss and Tzafriri, 1977). Furthermore, since Φ is continuous Φ(X_{n}) is compact and hence so is \overline{acoΦ(X_{n})}. This shows that A_{n} is compact. In order to see that A is compact, it therefore suffices to show ∥A_{n}− A∥ → 0 for n → ∞. The latter convergence can be easily checked using ℙ_{X}(X_{n}) ≥ 1 − 1/n.

It remains to prove that A is injective. To this end for g ≠ 0 we find

⟨(2λid_{H} + A)g,(2λid_{H} + A)g⟩ = 4λ^{2}⟨g,g⟩ + 4λ⟨g,Ag⟩ + ⟨Ag,Ag⟩
> 4λ⟨g,Ag⟩
= 4λ⟨g,𝔼_{ℙ}L′′(Y,f_{ℙ,λ}(X))g(X)Φ(X)⟩
= 4λ𝔼_{ℙ}L′′(Y,f_{ℙ,λ}(X))g^{2}(X)
≥ 0

Here, the last equation is due to the fact that B𝔼_{ℙ}h = 𝔼_{ℙ}Bh for all E-valued functions h and all bounded linear operators B : E → F between Banach spaces E and F. A much stronger result is given in Diestel and Uhl (1977, p. 47). The last inequality is true since the second derivative of a convex function is always nonnegative. Obviously, the above estimate shows that \frac{∂G}{∂H}(0,f_{ℙ,λ}) = 2λid_{H} + A is injective.

We use IF(z;T,ℙ) = \frac{∂f_{ε}}{∂ε} (0) to derive a formula for the influence function, where ε ↦ f_{ε} is the function implicitly defined by G(ε,f) = 0. The implicit function theorem hence gives

IF(z;T,ℙ) = −S^{−1} ∘ \frac{∂G}{∂ε}(0,f_{ℙ,λ}) ,  (21)

where S:= \frac{∂G}{∂H}(0,f_{ℙ,λ}).

Proof of Theorem 6. Since every compact subset of ℝ^{d} is closed and continuous kernels on compact subsets are bounded the assertion directly follows from Theorem 4.

Proof of Theorem 8. The proof is similar to that of Theorem 4. However, due to the extra variable b we have to adapt our approach. As in the proof of Theorem 4 we first point out that the solutions (f_{ℙ,λ},b_{ℙ,λ}) ∈ H ×ℝ exist. Again, this can be seen by a slight modification of the argument used by Steinwart (2002a). Now, let us define the map G: ℝ × H × ℝ → H × ℝ by

G(ε,f,b) := ( 2λf + 𝔼_{(1−ε)ℙ+εΔ_{z}} L′(f + b)Φ, 𝔼_{(1−ε)ℙ+εΔ_{z}} L′(f + b)) .

Again, for ε ∈ [0,1] the definition of G ensures

G(ε,f,b) = \frac{∂R_{L,(1−ε)ℙ+εΔ_{z} ,λ}^{reg}}{∂(H × ℝ)}(f) ,

if we apply the Fréchet-Riesz identification (H ×ℝ)′= H ×ℝ. Since R_{L,(1−ε)ℙ+εΔ_{z} ,λ}^{reg} is convex for all ε ∈ [0,1] we have G(ε,f,b) = 0 if and only if (f,b) minimizes R_{L,(1−ε)ℙ+εΔ_{z} ,λ}^{reg} for such ε. Our aim is to apply the implicit function theorem in the way we did it in the proof of Theorem 4. However, this time the implicit function theorem will also ensure the uniqueness of the solution of (7). Obviously, this is necessary for the existence of the influence function. In order to apply Theorem 19 we need the partial derivatives of G. By an easy computation we find

\frac{∂G}{∂ε}(ε,f,b) = −𝔼_{ℙ}L′(f + b)Φ(X) + 𝔼_{Δ_{z}}L′(f + b)Φ(X)

and

\frac{∂G}{∂(H × ℝ)} (ε,f,b) = ( \begin{matrix}2λid_{H} + 𝔼_{ε}L′′(f + b)⟨Φ,.⟩Φ & 𝔼_{ε}L′′(f + b)Φ \\ 𝔼_{ε}L′′(f + b)Φ & 𝔼_{ε}L′′(f + b) \end{matrix} ) ,

where we use the abbreviation 𝔼_{ε}:= 𝔼_{(1−ε)ℙ+εΔ_{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_{ℙ,λ},b_{ℙ,λ}) of (7). In order to show that the operator \frac{∂G}{∂(H×ℝ)} (0, f_{ℙ,λ},b_{ℙ,λ}) is invertible it suffices to show by the Fredholm Alternative that it is injective and that

A:= ( \begin{matrix}𝔼_{ℙ}L′′(f_{ℙ,λ} + b_{ℙ,λ})⟨Φ,.⟩Φ & 𝔼_{ℙ}L′′(f_{ℙ,λ} + b_{ℙ,λ})Φ \\ 𝔼_{ℙ}L′′(f_{ℙ,λ} + b_{ℙ,λ})Φ & 𝔼_{ℙ}L′′(f_{ℙ,λ} + b_{ℙ,λ}) − 2λ \end{matrix} )

is a compact operator on H × ℝ. The latter can be seen using the argument of the proof of Theorem 4. For the former let us suppose that we have an element (g,t) ∈ H ×ℝ with (2λid_{H×ℝ} +A)(g,t) = 0. This is equivalent to the following linear system of equations

2λg + 𝔼_{ℙ}L′′(f_{ℙ,λ} + b_{ℙ,λ})gΦ + t 𝔼_{ℙ}L′′(f_{ℙ,λ} + b_{ℙ,λ})Φ  = 0  (22)
𝔼_{ℙ}L′′(f_{ℙ,λ} + b_{ℙ,λ})g + t 𝔼_{ℙ}L′′(f_{ℙ,λ} + b_{ℙ,λ}) = 0.  (23)

Let us first assume that t = 0. Then the above system yields

2λg + 𝔼_{ℙ}L′′(f_{ℙ,λ} + b_{ℙ,λ})gΦ = 0.

Using the techniques of the proof of Theorem 4 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μ:= L′′(f_{ℙ,λ} + b_{ℙ,λ})dℙ. Note that L′′> 0 implies μ ≠ 0. Now, (23) yields

μ(g) = −μ(1),  (24)

where 1 denotes the constant function with value 1. Hence, by (22) we find

0 = 2λ⟨g,g⟩ + μ(g^{2}) + μ(g) = 2λ⟨g,g⟩ + μ(g^{2}) − μ(1) .  (25)

Furthermore, (24) implies

0 ≤ μ((g + 1)^{2}) = μ(g^{2}) + 2μ(g) + μ(1) = μ(g^{2}) − μ(1).

This together with (25) yields 2λ⟨g,g⟩ ≤ 0 and hence g = 0. However, the latter contradicts (24) and hence there is no non-trivial solution of the system (22), (23). Now, the implicit function theorem states in particular, that the solution (f_{ℙ,λ},b_{ℙ,λ}) is unique in a small neighborhood of (f_{ℙ,λ},b_{ℙ,λ}). Hence it is globally unique since the set of solutions of (7) is convex. The rest of the proof follows the ideas of the proof of Theorem 4.

We use IF(z;T,ℙ) = \frac{∂(f_{ε},b_{ε})}{∂ε}(0) to derive a formula for the influence function, where ε ↦ (f_{ε},b_{ε}) is the function implicitly defined by G(ε,f,b) = 0. The implicit function theorem hence gives

IF(z;T,ℙ) = −S^{−1} ∘ \frac{∂G}{∂ε}(0,f_{ℙ,λ},b_{ℙ,λ}) ,  (26)

where S:= \frac{∂G}{∂(H×ℝ)} (0,f_{ℙ,λ},b_{ℙ,λ}).

Proof of Theorem 12. Recall that every convex function on ℝ is locally Lipschitz continuous. Let |L_{|Y ×[−c,c]}|_{1} denote the Lipschitz constant of L restricted to Y × [−c,c], c > 0. We define δ_{λ} := \sqrt{(L(−1,0) + L(1,0))/λ} and K := sup_{x∈X} \sqrt{k(x,x)}. We fix a distribution ℙ. An easy estimate (Steinwart, 2002a) shows ∥f_{ℙ,λ}∥_{∞} ≤ δ_{λ}K. We will apply Theorem 28 in Steinwart (2003). 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 Steinwart (2003) 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 × Y → ℝ with ∥h∥_{∞} ≤ |L_{|Y ×[−δ_{λ}K,δ_{λ}K]}|_{1} such that for all distributions ℙ̂ we have

∥f_{ℙ,λ} − f_{ℙ̂,λ}∥_{H} ≤ \frac{1}{λ} ∥𝔼_{ℙ}hΦ − 𝔼_{ℙ̂}hΦ∥ _{H},

where Φ : X → H is the feature map of H. Let ℙ̂:= (1−ε)ℙ+εℙ̃. Then the above inequality yields

ε^{−1} ∥f_{(1−ε)ℙ+εℙ̃,λ} − f_{ℙ,λ}∥_{H} ≤ (ελ)^{−1} ∥𝔼_{ℙ}hΦ − 𝔼_{(1−ε)ℙ+εℙ̃} hΦ∥ _{H}
= λ^{−1} ∥𝔼_{ℙ}hΦ − 𝔼_{ℙ̃}hΦ∥_{H}
≤ c_{L}(λ)∥ℙ − ℙ̃∥_{M} ,

where

c_{L}(λ) = λ^{−1} K|L_{|Y ×[−δ_{λ}K,δ_{λ}K]}|_{1}.  (27)

This shows the assertion.

For the proof of Theorem 15 we need the following result.

Lemma 22 Let λ,μ ∈ (0,∞) be fixed constants. Then the function g : (0,1) → ℝ, g(s) = 2λs^{2} − 2μs[1 − s^{2}]^{1/2}+ μ has a global minimum in the point

s_{min}= 2^{−1/2} ( 1 − \frac{λ}{(μ^{2}+ λ^{2})^{1/2}} ) ^{1/2}

and

g(s_{min}) = λ( 1 − \frac{λ}{(μ^{2}+ λ^{2})^{1/2}} ) + μ( 1 − ( 1 − \frac{λ^{2}}{μ^{2}+ λ^{2}} ) ^{1/2}) > 0.

Proof of Lemma 22. Let s ∈ (0,1). We have g′(s) = 4λs − 2μ(1 − 2s^{2})[1 − s^{2}]^{−1/2} and

g′′(s) = 4λ + ( 4s − \frac{s(1 − 2s^{2})}{1 − s^{2}} ) \frac{2μ}{\sqrt{1 − s^{2}}} ≥ 4λ + 3s\frac{2μ}{\sqrt{1 − s^{2}}} > 0

for all s ∈ (0,1). Define a:= λ/[μ^{2}+ λ^{2}] ^{1/2}. We have 4λs_{min}> 0 and

\frac{2μ(1 − 2s_{min}^{2})[1 − s_{min}^{2}]^{−1/2}}{4λs_{min}} = \frac{μ}{λ} \frac{a}{[(1 + a)(1 − a)]^{1/2}}

= \frac{μ}{λ} [a^{−2} − 1] ^{−1/2} = \frac{μ}{λ} [ \frac{μ^{2}+ λ^{2}}{λ^{2}} − 1] ^{−1/2} = 1.

This yields g′(s_{min}) = 0 and we obtain the expression g(s_{min}) = λ[1 − \frac{λ}{(μ^{2}+λ^{2})^{1/2}} ] +μ[1 − (1 − \frac{λ^{2}}{μ^{2}+λ^{2}} )^{1/2}] .

Proof of Theorem 15. By rescaling problem (7) we may assume without loss of generality that K := sup_{x∈X} \sqrt{k(x,x)}≤ 1. Recall, that in the proof of Theorem 8 we used

IF(z;T,ℙ) = \frac{∂(f_{ε},b_{ε})}{∂ε}(0),

where ε ↦ (f_{ε},b_{ε}) was the function implicitly defined by G(ε,f,b) = 0. The implicit function theorem hence gives

IF(z;T,ℙ) = −S^{−1} ∘ \frac{∂G}{∂ε}(0,f_{ℙ,λ},b_{ℙ,λ}) ,  (28)

where S := \frac{∂G}{∂(H×ℝ)} (0,f_{ℙ,λ},b_{ℙ,λ}). Therefore, it suffices to bound the norms of the operators on the right side of (28). We begin with

∥ \frac{∂G}{∂ε}(0,f_{ℙ,λ},b_{ℙ,λ})∥ = ∥𝔼_{ℙ}L′(f_{ℙ,λ} + b_{ℙ,λ})Φ − 𝔼_{Δ_{z}}L′(f_{ℙ,λ} + b_{ℙ,λ})Φ∥
≤ b_{ℙ,λ}∥ℙ − Δ_{z}∥_{M} .

Furthermore, for (g,t) ∈ H × ℝ we have

S(g,t) = ( \begin{matrix}2λid_{H} + 𝔼_{ℙ}L′′(f_{ℙ,λ} + b_{ℙ,λ})⟨Φ,.⟩Φ & 𝔼_{ℙ}L′′(f_{ℙ,λ} + b_{ℙ,λ})Φ \\ 𝔼_{ℙ}L′′(f_{ℙ,λ} + b_{ℙ,λ})Φ & 𝔼_{ℙ}L′′(f_{ℙ,λ} + b_{ℙ,λ}) \end{matrix} ) ( \begin{matrix}g \\ t \end{matrix} )
= ( \begin{matrix}2λg + 𝔼_{ℙ}L′′(f_{ℙ,λ} + b_{ℙ,λ})gΦ + t𝔼_{ℙ}L′′(f_{ℙ,λ} + b_{ℙ,λ})Φ \\ 𝔼_{ℙ}L′′(f_{ℙ,λ} + b_{ℙ,λ})g + t𝔼_{ℙ}L′′(f_{ℙ,λ} + b_{ℙ,λ}) \end{matrix}  ) .

As in the proof of Theorem 8 we write dμ:= L′′(f_{ℙ,λ} + b_{ℙ,λ})dℙ. Then we find

⟨S(g,t),(g,t)⟩= 2λ⟨g,g⟩ + μ(g^{2}) + 2tμ(g) + t^{2}μ(1).  (29)

Let us suppose that ∥(g,t)∥ = 1. Then there exist w ∈ H with ∥w∥ = 1 and s ∈ [0,1] such that g = sw and t = ±\sqrt{1 − s^{2}} . If μ(w) ≥ 0 Equation (29) then yields

⟨S(g,t),(g,t)⟩≥ 2λs^{2}+ \frac{s^{2}μ^{2}(w)}{μ(1)}− 2s\sqrt{1 − s^{2}} μ(w) + (1 − s^{2})μ(1).  (30)

Here, we used μ(w) ≤ \sqrt{μ(1)}\sqrt{μ(w)}. It is easy to check that (30) also holds if μ(w) ≤ 0. Now, recall that by the assumption of the theorem we have L′′≥ a. This implies μ(1) ≥ a > 0. For the special case s = 0 it follows from (30), that

⟨S(g,t),(g,t)⟩≥ μ(1) > a > 0.  (31)

For the special case s = 1 it follows from (30), that

⟨S(g,t),(g,t)⟩≥ 2λ + \frac{μ^{2}(w)}{μ(1)} ≥ 2λ > 0.  (32)

Now, we will consider the case s ∈ (0,1). We first minimize the right hand side of (30) with respect to μ(w). To this end recall that K ≤ 1 implies |μ(w)| ≤ μ(1). Therefore, the function μ(w) ↦ \frac{s^{2}μ^{2}(w)}{μ(1)} − 2s\sqrt{1 − s^{2}} μ(w) is minimal if

μ(w) = min\{μ(1),μ(1)s^{−1} \sqrt{1 − s^{2}} \}.  (33)

Using (30) it follows for μ(w) = μ(1) that

⟨S(g,t),(g,t)⟩≥ 2λs^{2}+ μ(1)(1 − 2s\sqrt{1 − s^{2}} ) = 2λs^{2}− 2μ(1)s\sqrt{1 − s^{2}} + μ(1).  (34)

Hence, Lemma 22 and (34) yield for the case s ∈ (0,1) and μ(w) = μ(1) that

⟨S(g,t),(g,t)⟩≥ c_{low} ∈ (0,∞),  (35)

where

c_{low} = λ( 1 − \frac{λ}{(μ^{2}(1) + λ^{2})^{1/2}} ) + μ(1)( 1 − ( 1 − \frac{λ^{2}}{μ^{2}(1) + λ^{2}} ) ^{1/2}) .

By (33) we finally have to treat the case s ∈ (0,1) and μ(w) = μ(1)s^{−1} \sqrt{1 − s^{2}} . In this case we have s^{2} ≥ \frac{1}{2} by μ(w) ≤ μ(1). Hence we obtain from (30) that

⟨S(g,t),(g,t)⟩≥ 2λs^{2}+ (1 − s^{2})μ(1) − 2(1 − s^{2})μ(1) + (1 − s^{2})μ(1) = 2λs^{2} ≥ λ.  (36)

Combining (31), (32), (35), and (36) we obtain

⟨S(g,t),(g,t)⟩≥ min{a,2λ,c_{low},λ} > 0.  (37)

Therefore, by the proof of Pedersen (1989, Prop. 3.2.12) it follows

∥S(g,t)∥ ≥ min{a,λ,c_{low}}∥(g,t)∥

for all (g,t) ∈ H × ℝ, and

∥S^{−1} ∥ ≤ \frac{1}{min\{a,λ,c_{low}\}} ∈ (0,∞).

This shows the assertion.

References

R. Akerkar. Nonlinear Functional Analysis. Narosa Publishing House, New Dehli, 1999. P. L. Bartlett, O. Bousquet, and S. Mendelson. Local Rademacher complexities. http://www.

stat.berkeley.edu/˜ bartlett/papers/bbm-lrc-02b.pdf, 2002. P. L. Bartlett, M. I. Jordan, and J. D. McAuliffe. Convexity, classification, and risk bounds. http:

//stat-www.berkeley.edu/tech-reports/638.pdf, 2003. P. L. Bartlett and S. Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural

results. Journal of Machine Learning Research, 3:463–482, 2002. H. Bauer. Maß- und Integrationstheorie. De Gruyter, Berlin, 1990. G. Blanchard, G. Lugosi, and N. Vayatis. On the rate of convergence of regularized boosting clas-

sifiers. Journal of Machine Learning Research, 4:861–894, 2003. O. Bousquet and A. Elisseeff. Stability and generalization. Journal of Machine Learning Research,

2:499–526, 2002. A. Brown and C. Pearcy. Introduction to Operator Theory I. Springer, New York, 1977. D.-R. Chen, Q. Wu, Y. Ying, and D.-X. Zhou. Support vector machine soft margin classifiers. City

University of Hong Kong, 2003. W. Cheney. Analysis for Applied Mathematics. Springer, New York, 2001. A. Christmann. Least median of weighted squares in logistic regression with large strata.

Biometrika, 81:413–417, 1994. A. Christmann. On positive breakdown point estimators in regression models with discrete response

variables. 1998. Habilitation thesis, University of Dortmund, Department of Statistics. A. Christmann. On a strategy to develop robust and simple tariffs from motor vehicle insurance data.

Technical Report 16/04, University of Dortmund, SFB-475, 2004. http://www.statistik. uni-dortmund.de/download/mitarbeiter/christmann/Christmann-insurance04.pdf.

A. Christmann, P. Fischer, and T. Joachims. Comparison between various regression depth methods and the support vector machine to approximate the minimum number of misclassifications. Computational Statistics, 17:273–287, 2002.

A. Christmann and P. J. Rousseeuw. Measuring overlap in logistic regression. Computational

Statistics and Data Analysis, 37:65–75, 2001. J. Diestel and J. J. Uhl. Vector Measures. American Mathematical Society, Providence, RI, 1977. D. L. Donoho and P. J. Huber. The notion of breakdown point. In P. J. Bickel, K. A. Doksum, and

J. L. Hodges Jr, editors, A Festschrift for Erich L. Lehmann, pages 157–184, Belmont, California, Wadsworth, 1983.

R. M. Dudley. Real Analysis and Probability. Cambridge University Press, 2002.

Y. Freund and R. Schapire. Experiments with a new boosting algorithm. In Machine Learning: Proceedings of the 13th International Conference, pages 148–156. Morgan Kauffman Publishers, San Francisco, 1996.

J. Friedman, T. Hastie, and R. Tibshirani. Additive logistic regression: a statistical view of boosting (with discussion). Annals of Statistics, 28:337–407, 2000.

F. R. Hampel. The influence curve and its role in robust estimation. Journal of the American Statistical Association, 69:383–393, 1974.

F. R. Hampel, E. M. Ronchetti, P. J. Rousseeuw, and W. A. Stahel. Robust Statistics. The approach based on influence functions. Wiley, New York, 1986.

D. Hand, H. Mannila, and P. Smyth. Principles of Data Mining. MIT Press, Cambridge, Massachusetts, 2001.

T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning. Springer, New York, 2001.

J. Hipp, U. Güntzer, and U. Grimmer. Data quality mining - making a virtue of necessity. Workshop on Research Issues in Data Mining and Knowledge Discovery DMKD, Santa Barbara, CA, http: //www.cs.cornell.edu/johannes/papers/dmkd2001-papers/p5˙ hipp.pdf, 2001.

K. U. Höffgen, H.-U. Simon, and K. S. van Horn. Robust trainability of single neurons. Journal Computer and System Sciences, 50:114–125, 1995.

P. J. Huber. Robust estimation of a location parameter. Annals of Mathematical Statistics, 35: 73–101, 1964.

P. J. Huber. Robust statistics. Wiley, New York, 1981.

T. Joachims. Making large-scale SVM learning practical. In B. Schölkopf, C. Burges, and A. J. Smola, editors, Advances in Kernel Methods - Support Vector Learning, pages 41–56, MIT Press, Cambridge, Massachusetts, 1999.

J. Lindenstrauss and L. Tzafriri. Classicial Banach spaces I. Springer, Berlin, 1977.

G. K. Pedersen. Analysis Now. Springer, New York, 1989.

H. Rieder. Robust Asymptotic Statistics. Springer, New York, 1994.

P. J. Rousseeuw and M. Hubert. Regression depth. Journal of the American Statistical Association, 94:388–433, 1999.

B. Schölkopf and A. J. Smola. Learning with Kernels Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, Cambridge, Massachusetts, 2002.

J. C. Scovel and I. Steinwart. Fast rates for support vector machines. Los Alamos Technical Report LA-UR-03-9117, http://www.c3.lanl.gov/˜ ingo/publications/ann-03.ps, 2003.

I. Steinwart. On the influence of the kernel on the consistency of support vector machines. Journal of Machine Learning Research, 2:67–93, 2001.

I. Steinwart. Consistency of support vector machines and other regularized kernel machine. IEEE

Transactions on Information Theory, to appear, 2002a. I. Steinwart. Support vector machines are universally consistent. Journal of Complexity, 18:768–

791, 2002b. I. Steinwart. Sparseness of support vector machines. Journal of Machine Learning Research, 4:

1071–1105, 2003. I. Steinwart. Sparseness of support vector machines – some asymptotically sharp bounds. Proceed-

ings of Neural Information Processing Systems, in press, 2004. J. A. K. Suykens, J. De Brabanter, L. Lukas, and J. Vandewalle. Weighted least squares support

vector machines: robustness and sparse approximation. Neurocomputing, 48:85–105, 2002. A. B. Tsybakov. Optimal aggregation of classifiers in statistical learning. Annals of Statistics, 32:

135–166, 2004. J. W. Tukey. Exploratory Data Analysis. Addison-Wesley, Reading, Massachusetts, 1977. V. N. Vapnik. Statistical Learning Theory. Wiley, New York, 1998. G. Wahba. Support vector machines, reproducing kernel Hilbert spaces and the randomized GACV.

In B. Schölkopf, C. Burges, and A. J. Smola, editors, Advances in Kernel Methods - Support Vector Learning, pages 69–88, MIT Press, Cambridge, Massachusetts, 1999.

K. Yosida. Functional Analysis. Springer, Berlin, 4^{th}edition, 1974. E. Zeidler. Nonlinear Functional Analysis and its Applications I. Springer, New York, 1986. T. Zhang. Statistical behaviour and consistency of classification methods based on convex risk

minimization. Annals of Statistics, 32:56–134, 2004.