Gilles Blanchard

Laurent Zwald

Finite Dimensional Projection for Classification and Statistical Learning

Keywords: statistical learning, classification, support vector machine (SVM), kernel principal component analysis (KPCA), regularization, dimension reduction

A new method for the binary classification problem is studied. It relies on empirical minimization of the hinge risk over an increasing sequence of finite-dimensional spaces. A suitable dimension is picked by minimizing the regularized risk, where the regularization term is proportional to the dimension. An oracle-type inequality is established for the excess generalization risk (i.e. regret to Bayes) of the procedure, which ensures adequate convergence properties of the method.

We suggest to select the considered sequence of subspaces by applying kernel principal components analysis. In this case the asymptotical convergence rate of the method can be better than what is known for the Support Vector Machine. Exemplary experiments are presented on benchmark datasets where the practical results of the method are comparable to the SVM.

A. The classification framework.

In this paper, we consider the framework of supervised binary classification. Let (X, Y ) denote a random variable with values in X × {-1, +1} and probability distribution P . The marginal distribution of X is denoted by Q. Y is the label associated to the input variable X. We observe a set of n independent and identically distributed (i.i.d.) pairs (X i , Y i ) n i=1 sampled according to P . These observations form the training set. (We will suppose n ≥ 3 to avoid inconsistencies in the sequel.)

A classifier is a mapping f from X to {-1, +1} assigning to every point x ∈ X a prediction of its label. The quality of such a classifier is naturally measured by its generalization error P[f (X) = Y ]. Consequently, the aim is to estimate (using only the information of the training set) the classifier having minimal generalization error, called Bayes classifier. We will denote this optimal classifier f * ; it is well-known that f * (x) = 21 {η(x)>1/2} -1 a.s. on the set {η(x) = 1/2} , where η(x

) = P[Y = 1|X = x].
Given a certain set of classifiers C fixed in advance, the Empirical Risk Minimization procedure (see, e.g., [START_REF] Vapnik | Statistical Learning Theory[END_REF]) consists in finding a classifier f ∈ C minimizing the empirical classification error 1 n n i=1 1 {f (Xi) =Yi} . Here, the function ℓ(f, (x, y)) = 1 {f (x) =y} , also called 0-1 loss, is the natural loss function for the classification framework. Unfortunately, minimizing exactly the empirical classification error is, in most cases, practically intractable, mainly because it is not a convex optimization procedure. This is the reason why numerous classification algorithms, such as the support vector machine (SVM for short in the sequel), or boosting, do not consider the 0-1 loss, but minimize instead a convex surrogate loss function γ over some real-valued (instead of {-1; 1}-valued) function space F, opening way to the use of efficient convex programming methods. A real output function f over X can then be transformed into a binary classifier by considering sign(f ). We will in this work concentrate on the surrogate loss function used by the SVM, called the hinge loss : γ h (g, (x, y)) = (1yg(x)) + , where (a) + = a1 {a≥0} denotes the positive part.

B. Regularization in classification and in regression

For a given loss function we call risk the averaged loss over some data distribution. The averaged loss over the training set is called empirical risk and the averaged loss over the draw of a new independent random observation (X, Y ) is called generalization risk or sometimes just risk. Overfitting is the phenomenon of excessive discrepancy between empirical risk (observed on the training sample) and generalization risk on independent test data, and leads to performance degradation and inconsistency. To avoid overfitting, a common remedy is to consider regularization: it consists in adding to the empirical risk an additional balancing term Ω(f ), which, roughly speaking, should be representative of how irregular the considered function is. The function f ∈ F minimizing the sum of these two terms is then picked. For SVMs, the regularization Ω(f ) = C f 2 is taken proportional to the squared norm of f in a certain functional Hilbert space H.

The latter form of regularizer is also known as Arsenin-Tikhonov's regularization (Tikhonov's regularization for short in the sequel), and has already been widely used and studied in statistics in the framework of least squares regression. In this case, and if the proportionality constant C is chosen in a suitable way as a function of the training sample size, it can be shown that the resulting estimator enjoys minimaxity properties over the Hilbert balls B(R) = {f ∈ H, f ≤ R} (see, e.g., [START_REF] Wahba | Spline Models for Observational Data[END_REF] for a survey). Note that B(R) can equally be seen as an (Hilbert-Schmidt) ellipsoid of L 2 (Q).

However, in the case of least square regression, an also widely used alternative strategy to Tikhonov's regularization is to consider least squares fitting over an increasing sequence of linear, finite dimensional subspaces S 1 ⊂ S 2 ⊂ . . . , and to use a regularization term proportional to the subspace dimension (the "number of parameters"). The selected dimension then minimizes the sum of the residual least squares and of the regularization term (see, e.g., [START_REF] Barron | Risk bounds for model selection via penalization[END_REF] for a extended study and [START_REF] Baraud | Model selection for regression on a random design[END_REF] for regression on a random design).

The interesting thing here is that these two regularization approaches for regression can be compared. More precisely, the following has been shown in the particular case of Gaussian white noise regression (see [START_REF] Massart | Concentration Inequalities and Model Selection[END_REF], section 4.3): if the subspace S D is taken to be the span of the D first principal axes of B(R) (as an ellipsoid in L 2 (Q)), then the finite-projection estimator is also minimax over B(R). More than that, it is even minimax for any other Hilbert-Schmidt ellipsoid of L 2 (Q) having the same principal axes. This, on the other hand, is not generally the case for the estimator obtained by Tikhonov's regularization. In conclusion, the finite-dimensional approach can actually be more adaptive than Tikhonov's regularization.

The reason for this long discussion of the regression setting is to motivate the goals of this paper. Namely, it does not appear that an approach similar to the finite-dimensional projection has been studied for classification. This is precisely the aim of the present work.

The paper is organized as follows. In Section 2, we present the finite-dimensional projection method and give our main theoretical result, an oracle inequality bounding the excess risk of the method. For this, we use theoretical tools of M-estimation ( [START_REF]Some applications of concentration inequalities to statistics[END_REF], [START_REF] Bartlett | Local Rademacher complexities[END_REF]). In Section 3, we compare the obtained bound to a bound available for SVMs and taking a similar form. In Section 4, we propose to use kernel principal component analysis to estimate the subspaces used for projection. The resulting algorithm is dubbed the kernel projection machine (KPM, originally introduced in [START_REF] Blanchard | Kernel projection machine: a new tool for pattern recognition[END_REF]): the model selection used in this new algorithm is guided by the previous theoretical result. Testing it on some benchmark datasets, we find results comparable to the SVM. While we do not outperform the SVM, the main point we want to convey in the present work is to show that finite dimensional projection is a viable alternative to Tikhonov's regularization.

II. FINITE DIMENSIONAL PROJECTION FOR CLASSIFICATION.

A. The finite dimensional projection estimator.

Remember our main loss function is the hinge loss γ h (g, (x, y)) = (1yg(x)) + . The hinge loss is consistent in the sense that the Bayes classifier satisfies (see [START_REF] Lin | Support Vector Machines and the Bayes rule in classification[END_REF])

f * = arg min g E [γ h (g)] .
It is straightforward that the hinge loss upper-bounds the classification error (0-1 loss):

γ h (g, (x, y)) ≥ 1 {g(x) =y} .
Moreover, the excess or regret hinge risk with respect to the Bayes classifier upper-bounds the excess classification error [START_REF] Zhang | Statistical behavior and consistency of classification methods based on convex risk minimization[END_REF]:

E [γ h (g)] -E [γ h (f * )] ≥ P (Y g(X) ≤ 0) -P (Y f * (X) ≤ 0) . (1)
This means that the rate of convergence to the Bayes classifier for the hinge risk is an upper bound on the classification error convergence rate.

We will now consider the following setting. Let (Ψ 1 , Ψ 2 , . . .) be an arbitrary family of functions fixed beforehand. We denote

S D = span {Ψ 1 , • • • , Ψ D }
f D = arg min f ∈SD 1 n n i=1 (1 -Y i f (X i )) + . (2)
At an intuitive level, we can think about the function family as a smoothness basis (think, e.g., a Fourier basis): subspaces S D with lower dimension D contain smoother functions. Note that there is no regularization term of any kind in the definition of f D . Instead, it the dimension parameter D will play the role of a complexity penalty. We now devise a method for the selection of the dimension. Some technical problems arising when analyzing the statistical properties of f D are caused by the unboundedness of the loss function γ h . In order to alleviate these, we introduce here the clip function (which was already considered in [START_REF] Györfi | A Distribution-Free Theory of Nonparametric Regression[END_REF] in a regression framework, in [START_REF] Bartlett | The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network[END_REF], and in [START_REF] Chen | Support vector machine soft margin classifiers: Error analysis[END_REF] in relation to the SVM) :

clip(g(x)) =      1 if g(x) ≥ 1 g(x) if -1 < g(x) < 1 -1 if g(x) ≤ -1 .
Note that the hinge loss of a clipped function corresponds to 'trimming' the hinge loss of the original function:

γ h (clip(f ), (x, y)) = min(γ h (f, (x, y)), 2) .
We now apply the following dimension selection strategy: we first "clip" the estimated function f D for each D, defining f D = clip( f D ). We define our final estimator by performing the model selection step over values of D using the clipped estimators f D . This is obtained by penalized minimization of the empirical risk: the final classifier is sign( f b D ) where

D = arg min D≥1 1 n n i=1 (1 -Y i f D (X i )) + + λD , (3)
and the constant λ has to be suitably chosen. The linear penalty λD will be justified from a statistical point of view in the next section. Some preliminary comments are in order. First, note that the clipping operation does not alter the associated classifier function since clipping leaves the sign unchanged. As a second point, note that the clipping is only performed for the dimension selection step. We could, of course, consider the option of minimizing the 'trimmed' loss min(γ h , 2) over each model S D to get completely rid of boundedness issues. But since the trimmed loss is not convex, it would be difficult to devise a practical procedure to minimize this function over a model S D . This is why we first minimize the true hinge loss γ h on every model S D (which is a convex optimization problem, hence amenable to convex programming techniques), and then choose the dimension D by minimizing the penalized trimmed loss of the functions f D . This, again, is a practically feasible step, since we only have to compare a finite -and relatively small -number of functions (we typically expect that the maximum dimension D max taken into consideration satisfies D max ≤ n). To sum up, the above procedure is practically feasible.

B. Main result.

We are now ready to formulate our main theoretical result: it aims at giving a precise statistical justification to the model selection procedure (3) involved in the finite dimensional regularization, and will be used for theoretical comparison with the SVM in the next section.

Theorem 1: Let (S D ) D≥1 be a family of linear subspaces of L 2 (Q) where S D is of dimension at most D and f D denotes the minimizer of the empirical risk:

f D = arg min f ∈SD n i=1 (1 -Y i f (X i )) + . (4)
Let η be defined as η(x) = P [Y = 1|X = x]. We suppose that the following "noise margin" condition holds:

∃ h 0 > 0, ∀x ∈ X , η(x) - 1 2 ≥ h 0 . (5)
Let f D = clip( f D ) . The dimension of the final estimator is selected by

D = arg min D≥1 1 n n i=1 (1 -Y i f D (X i )) + + pen n (D) . (6)
Then, there exist universal constants C 1 and C 2 such that, for any K > 1 , the following holds: provided that

∀ D ≥ 1, pen n (D) ≥ C 1 K h 0 D log n n , (7)
then the excess risk satisfies

E L h ( f b D , f * ) ≤ K K -1 inf D≥1 inf f ∈SD L h (f, f * ) + 2E[pen n (D)] + C 2 K h 0 n , (8)
where

L h (g, f * ) = E [γ h (g)] -E [γ h (f * )]
is the excess hinge risk. This result is proved in appendix in a more generic framework. We now give some comments.

• The above theorem takes the form of a so-called oracle inequality [START_REF] Blanchard | Kernel projection machine: a new tool for pattern recognition[END_REF], where the excess risk of the penalized estimator can be compared to the excess risk of the best possible choice of function over each model. There is a tradeoff appearing between approximation error, decreasing with D, and estimation error (represented by the penalization term on the righthand side) which increases with D. If we make additional assumptions about the approximation properties of S D with respect to the target f * , this can be used to derive rates of convergence (this will be elaborated in the next section). A crucial point, however, is that the oracle inequality itself, and the penalty, are independent of any such assumptions on f * . It means that the resulting estimator enjoys adaptivity properties. • This result means that the penalty λD linear with the dimension used in the criterion (3) is statistically justified. However, admittedly, the multiplicative constant C 1 obtained by this theoretical study is too large to be directly used in practice. This theorem therefore should be seen essentially as a theoretical guarantee that using this form of penalty is well-founded from a statistical point of view, and will have suitable convergence properties as the sample size n grows large. • Using inequality (1), inequality (8) also provides an upper bound of the excess classification error (i.e. excess risk for the 0-1 loss) with respect to the Bayes classifier. • One important drawback of this result is the dependence of the penalty on the unknown margin parameter h 0 . Results of [START_REF] Massart | Risk bounds for statistical learning[END_REF] show that this parameter plays a crucial role for minimax rates of convergence in classification. A related and more general noise condition is Tsybakov's noise exponent (see [START_REF] Mammen | Asymptotical minimax recovery of sets with smooth boundaries[END_REF], [START_REF] Tsybakov | Optimal aggregation of classifiers in statistical learning[END_REF]) which similarly has a prominent influence on minimax rates. Procedures that can be shown to be adaptive to the noise margin parameter or to Tsybakov's noise exponent have only been studied very recently [START_REF] Tsybakov | Square root penalty: adaptation to the margin in classification and in edge estimation[END_REF]- [START_REF] Scott | Minimax optimal classification with dyadic decision trees[END_REF].

III. COMPARISON WITH THE RISK BOUND FOR THE SVM. In this section, we try to compare the rate of convergence that can be obtained for the finite-dimensional approach via Theorem 1 to the Tikhonov regularization approach. The natural candidate to compare against is therefore the Support Vector Machine (SVM), which uses this form of regularization with the same loss function as above.

If we draw a parallel to what can be shown in the least squares regression case [START_REF] Massart | Concentration Inequalities and Model Selection[END_REF], we must however consider several caveats. This will result in the picture of the present situation being unfortunately noticeably less complete.

• There is, up to our knowledge, no definite universal reference bound agreed upon that would accurately depict the behavior of the SVM, but there is a diversity of performance bounds to choose from in the recent literature (e.g., [START_REF] Chen | Support vector machine soft margin classifiers: Error analysis[END_REF], [START_REF] Steinwart | Fast rates for support vector machines using Gaussian kernels[END_REF], [START_REF] Vito | Learning from examples as an inverse problem[END_REF]).

Here, we have chosen to compare the bound of Theorem 1 to the performance bound shown in [START_REF] Blanchard | Statistical performance of support vector machines[END_REF]. The main reason for this choice is that the bounds in [START_REF] Blanchard | Statistical performance of support vector machines[END_REF] have a very similar 'oracle-type' form involving approximation properties of models (in the case of SVMs, these models are ellipsoids) for the excess hinge risk. This makes a comparison easier. • For least squares regression, minimax rates have been extensively studied, and provide a definite yardstick for establishing when a convergence bound is optimal and cannot be improved. For classification with the hinge loss, up to our knowledge, no minimax bounds have been established (and we do not know of lower bound results on the rate of convergence of the SVM). Here, the comparison will be therefore limited to an upper bound comparison. • In regression again, the least squares loss is associated to function approximation in L 2 distance, which is particularly well suited to compare approximation properties of ellipsoids and finite dimensional subspaces. For the hinge loss, comparing such approximation properties is far from obvious. We will therefore resort to bounding the excess hinge risk by the L 2 distance and compare the obtained bounds.

A. Background material on the SVM.

In this subsection, we recall briefly some points crucial to the support vector machine. Although it was not originally derived this way, the (soft-margin) SVM algorithm can be formulated as the minimization of the regularized empirical hinge risk [START_REF] Evgeniou | Regularization networks and Support Vector Machines[END_REF], [START_REF] Smola | On a kernel-based method for pattern recognition, regression, approximation and operator inversion[END_REF]:

g = arg min g∈H b 1 n n i=1 (1 -Y i g(X i )) + + Λ n g 2 H . (9)
Here

H b = {g(x) + b, g ∈ H, b ∈
R} and H is a reproducing kernel Hilbert space (RKHS) of functions on X , with Hilbert norm • H . We will actually consider a restricted case of the above where the minimization is over H instead of H b , i.e., the arbitrary constant b is set to zero. We will denote the resulting function g 0 . This simplified setting is frequently (although not always) used in theoretical studies of the SVM, among which [START_REF] Blanchard | Statistical performance of support vector machines[END_REF], which exposes the bound we wish to compare ourselves to. It is expected that this modification does no change fundamentally the asymptotical properties of the SVM. Note that the optimization problem (9) (with the above simplification to b = 0) can be rewritten in the following way:

g 0 = g b R where g R = arg min g∈E(R) 1 n n i=1 (1 -Y i g(X i )) + , and
R = arg min R≥0 1 n n i=1 (1 -Y i g R (X i )) + + CR 2 , (10)
where E(R) are balls of radius R in H . Thus, we can equivalently interpret the regularization (9) as model selection, where the models are balls E(R) , g R is the minimum empirical risk estimator on each model, and criterion ( 10) is used to select the radius R.

At this point, it is interesting to recall that the balls in the RKHS space H can be viewed as ellipsoids in L 2 (Q). Let us recall some facts about the structure of a RKHS H: such a space is uniquely characterized by a symmetric, positive definite kernel function k : X × X → R . We will assume that X is a metric compact space and k a continuous kernel, which allows us to apply Mercer's theorem. Let T k be the following integral kernel operator of L 2 (Q):

T k : g → X k(x, .)g(x)dQ(x) . (11)
The operator T k is compact and self-adjoint, and can therefore be diagonalized: let (Ψ i ) i≥1 be an L 2 (Q)-orthonormal basis of eigenfunctions corresponding to the non-increasing sequence of eigenvalues (λ i ) i≥1 . Mercer's theorem allows to get a representation of H in terms of spectral quantities associated to T k . Precisely, H can be characterized as

H =    g ∈ L 2 (Q) : g = i≥1 a i Ψ i such that g 2 H = i≥1 a 2 i λ i < ∞    . ( 12
)
We then have

E(R) = {g ∈ H, g H ≤ R} =    g ∈ L 2 (Q), g = i≥1 a i Ψ i ; i≥1 a 2 i λ i ≤ R 2    .
Consequently, a ball of the RKHS is an ellipsoid of L 2 (Q) whose principal axes are precisely the eigenfunctions of T k .

In [START_REF] Blanchard | Statistical performance of support vector machines[END_REF], the following result was proved for the SVM: assuming k(x, x) ≤ M for all x ∈ X , and under the same margin condition (5) as in Theorem 1, the function g 0 defined in equation ( 9) satisfies with probability at least 1δ , over the i.i.d. draw of the training sample:

L h ( g 0 , f * ) ≤ 2 inf g∈H L h (g, f * ) + C(M )Λ n g 2 H + C ′ Λ n , (13)
provided that Λ n is bounded from below by a certain function depending on the eigenvalue sequence (λ i ) . If the eigenvalues are of the form λ j = O(j -2γ ) for some γ ≥ 1 , then the corresponding condition reads

Λ n ≥ C(M, h 0 , δ)n -2γ 2γ+1
. Finally, it is reported in [START_REF] Blanchard | Statistical performance of support vector machines[END_REF] that a similar bound holds for the expected excess risk EL h ( g 0 , f * ) (averaged over the draw of the training sample), up to additional logarithmic factors in the penalty. We will use this averaged risk version for comparison with Theorem 1.

B. Bound comparison.

To set up the comparison with the finite-dimensional subspace method, we will consider the subspaces S D spanned using the sequence of functions (Ψ 1 , Ψ 2 , . . .) defined in the previous section as the eigenfunctions of operator T k . Note that in the present section, we assume that the marginal Q is known, and therefore that both (Ψ i ) and (λ i ) are known to be able to compare the performance bounds. (In the next section, we will discuss a practical procedure in order to approximate the sequence (Ψ i ) when Q is unknown.)

We will compare the obtained bounds in the following specific setting: (a) the eigenvalues satisfy a polynomial decay λ j = Θ(j -2γ ) . (Note that γ > 1 2 since the eigenvalues series must be summable, T k being a trace-class operator.) (b) the coefficients of the Bayes classifier

f * in the L 2 (Q) orthogonal basis (Ψ i ) satisfy f * , Ψ j = Θ(j -α ) . (Note that α > 1 2 since f * ∈ L 2 (Q) .
) As previously discussed in the caveats, in order to compare the approximation properties of the balls of H and the subspaces S D , we will additionally upper-bound (for both compared bounds) the excess hinge risk in the following way:

L h (f, f * ) ≤ f -f * Q,1 ≤ f -f * Q,2 , (14)
where the first inequality holds because the hinge loss γ h is Lipschitz.

We are now left with comparing the following bounds: for the SVM classifier g 0 , we have from ( 13), [START_REF] Massart | Risk bounds for statistical learning[END_REF] and condition (a):

E[L( g 0 , f * )] inf g∈H g -f * Q,2 + n -2γ 2γ+1 g 2 H , (15)
while Theorem 1 together with ( 14) yields for the finite-dimensional estimator f :

E[L( f , f * )] inf D≥1 inf g∈SD g -f * Q,2 + D n , (16)
where means that the bound holds up to a fixed multiplicative constant and possibly an additional factor log(n) . We sum up some necessary computations in the following lemma: Lemma 2: Assume condition (b) above holds.Then the right-hand side of inequality ( 16) is bounded the following way:

inf D≥1 inf g∈SD g -f * Q,2 + D n n -2α-1 2α+1 .
On the other hand, if conditions (a) and (b) above hold, and α < 2γ + 1 2 , the right-hand side of inequality ( 15) is at least

inf g∈H g -f * Q,2 + n -2γ 2γ+1 g 2 H n -2(2α-1)γ (2γ+1)(4γ-2α+1) .
In can be checked easily that 2α-1 2α+1 >

2(2α-1)γ (2γ+1)(4γ-2α+1
) is implied by the sufficient condition α ≤ γ + 3 8 . Of course, since we are only comparing upper bounds, the above result does not imply that the finite dimensional projection classifier is necessarily better than the SVM: more to the point, whenever the above condition is satisfied, the known bound on the rate of convergence of the finite dimensional projection classifier outperforms the known bound on the rate of the SVM.

It is now legitimate to ask in what situation the condition α ≤ γ + 3 8 is satisfied. We argue that, if the eigenvalues and the expansion coefficients follow a polynomial decrease as assumed above, then the condition actually covers most of the possible range of values for α and γ . A simple observation is namely that the Bayes classifier f * cannot belong to the RKHS H, since it is discontinuous (except for the trivial case where it is constant), while we assumed that the kernel was continuous, implying that all functions in H are also continuous. This therefore means that the series i>0 f 2 i /λ i must diverge, implying in turn necessarily that α < γ + 1 2 . Therefore, the condition α ≤ γ + 3 8 covers a very large part of the available range. It also trivially implies the condition needed for the second part of the lemma.

Let us finally briefly describe a very simple example illustrating the above situation. Assume that X is the real interval [0, 1] , that the marginal Q is the Lebesgue measure; and consider the following kernel:

k(x, y) = 1 + 2 j≥1 λ j (cos(2πjx) cos(2πjy) + sin(2πjx) sin(2πjy)) ,
where, for j ≥ 2, λ j = (2πj) -2γ with γ > 1 2 . In this case, {Ψ i } i≥1 is the trigonometric basis of L 2 ([0, 1]) . It is known (see e.g. [START_REF] Wahba | Spline Models for Observational Data[END_REF], chapter 2 ) that, if γ is an integer, the RKHS associated with this kernel is the Sobolev space of order γ with periodic boundary conditions

H (γ) per . Precisely, H (γ) per is the set of functions of L 2 ([0, 1]) with γ -1 continuous derivatives satisfying f (0) = f (1), • • • , f (γ-1) (0) = f (γ-1) (0) , and with f (γ) ∈ L 2 ([0, 1]). It is endowed with the Sobolev norm f 2 Sob = 1 0 |f (γ) (t)| 2 dt + 1 0 f (t)dt 2
. This norm coincides with the RKHS norm implicitly defined by k. In this situation, the non-continuity of f * prevents normal convergence of its Fourier series, so that necessarily α ≤ 1 . On the other hand, the parameter γ represents the regularity of the kernel and it is not customary to choose very irregular kernels, so that we would expect in a reasonable practical situation that γ > 1 : in this case, the sufficient condition giving the advantage to the finite dimensional bound is satisfied.

As a final note, it is reported in [START_REF] Blanchard | Statistical performance of support vector machines[END_REF] that the quadratic penalty Λ n g 2 H in the 'standard' SVM (i.e., Tikhonov's regularization) could in principle be reduced to a lighter linear (instead of quadratic) penalty of the form Λ n g H . With this type of regularization, different from Tikhonov's, it is still possible to ensure good statistical properties, i.e., an oracle inequality similar to (13) holds. It is possible that, for this modified SVM with linear penalty, the corresponding oracle bound would also give rise to a faster convergence rate. Here however, our point here was to compare the finite dimensional approach to the "standard" SVM only, so that we did not consider this alternative regularization.

The above bound comparison suggests that it should be a good idea to use the basis (Ψ 1 , Ψ 2 , . . .) of eigenfunctions of T k for the finite-dimensional projection approach. However, these functions are in general not available, since the marginal Q is not known. In the next section, we will propose a practical procedure to approximate these functions using Kernel PCA.

IV. KERNEL PROJECTION MACHINE AND NUMERICAL RESULTS.

In this section, we will compare the finite dimensional projection approach to the classical SVM on real data by constructing an actual classification algorithm based on the finite dimensional projection principle. This algorithm is dubbed kernel projection machine (KPM, originally introduced in [START_REF] Blanchard | Kernel projection machine: a new tool for pattern recognition[END_REF]).

A. Using kernel PCA to approximate eigenfunctions

The theoretical study in the previous section suggests to use a basis of functions which is, in some sense, adapted to the underlying distribution Q of the input data, by considering

S D = span {Ψ 1 , . . . , Ψ D } ,
where (Ψ 1 , . . . , Ψ D ) are the eigenfunctions (in order of decreasing eigenvalues) of the operator T k given by [START_REF] Györfi | A Distribution-Free Theory of Nonparametric Regression[END_REF]. In practice, Q is not known exactly, so that the functions (Ψ i ) are also unknown. A standard approach, the so-called Nyström approximation [START_REF] Baker | The numerical treatment of integral equations[END_REF], consists in replacing Q by the empirical distribution of the X i in the definition of the kernel operator.

Formally, we will therefore consider the eigenfunctions Ψ i of the operator

T k,n f (x) = 1 n n i=1 f (x i )k(x, x i ) (17)
to define the models S D . Finding the eigenfunctions of T k,n is equivalent to performing the well-known kernel principal components analysis (KPCA) algorithm [START_REF] Schölkopf | Nonlinear component analysis as a kernel eigenvalue problem[END_REF]. A very convenient fact used to perform this step efficiency is to note that it suffices to diagonalize the n × n kernel Gram matrix K 1,n = 1 n (k(X i , X j )) 1≤i,j≤n to obtain the eigenfunctions of T k,n . Indeed, for j ≥ 1 such that λ j > 0,

Ψ j (x) = 1 λ j n n i=1 V (i) j k(X i , x) , (18)
where (V j ) 1≤j≤n is an orthonormal basis of eigenvectors of K 1,n associated to the eigenvalues ( λ j ) 1≤j≤n , sorted in decreasing order. The above normalization ensures

Ψ j H = 1.
This choice of functions and models S D is now data-dependent; for this reason, strictly speaking, this does not enter in the framework of Theorem 1 where models are assumed to be fixed. An exact study of the whole data-dependent procedure, also taking precisely into account the variability in the data-dependent models, is however out of the scope of the present paper. Let us only mention here that it is well-known that Ψ i converges to Ψ i as n → ∞ and details of this convergence have been studied (see, e.g., [START_REF] Koltchinskii | Asymptotics of spectral projections of some random matrices approximating integral operators[END_REF]- [START_REF] Zwald | On the convergence of eigenspaces in kernel principal component analysis[END_REF]), so that using this approximation is a well-founded heuristic.

Furthermore, there is a particular data-dependent setting where Theorem 1 strictly applies, namely when the eigenfunctions are estimated on a distinct data sample. Let us assume that we have an independent (unlabeled) sample (X ′ i ) drawn according to the same input distribution Q . This situation is not uncommon in a lot of practical applications where only a part of the available data has been labeled. The eigenfunctions ( Ψ i ) are estimated using this unlabeled sample. These are then used to perform the finite-dimensional projection estimation on the original sample (X i , Y i ) . In this case, conditionally to (X ′ i ) Theorem 1 applies. We therefore have the following:

Corollary 1: Assume that the noise margin condition (5) holds. Let D = (X i , Y i ) i=1,...,n be an i.i.d. sample drawn from P and D ′ = (X ′ j ) j=1,...,m be an independent, unlabeled i.i.d. sample. Assume the unlabeled sample D ′ is used to construct a family of functions ( Ψ i ) and put S D = span Ψ 1 , . . . , Ψ D .

Follow the same estimation procedure as in Theorem 1 with the data-dependent subspace family S D used in place of S D , i.e. definitions (4), [START_REF]Some applications of concentration inequalities to statistics[END_REF], giving rise to estimator f ′ b D .

Then, there exist universal constants C 1 , C 2 such that for any K > 1 , if condition [START_REF] Bartlett | Local Rademacher complexities[END_REF] on the penaly function holds, then

E D,D ′ L h ( f ′ b D , f * ) ≤ K K -1 E D ′ inf D≥1 inf f ∈ b SD L h (f, f * ) + 2E D [pen n (D)] + C 2 K h 0 n . ( 19
)
Proof: Conditionally to the unlabeled sample D ′ the functions ( Ψ i ) , and the models S D are fixed; therefore Theorem 1 applies. We then take the expectation of ( 8) with respect to D ′ .

In the next section, we will however only consider the situation where we use only one sample for simplicity and give a detailed account of the obtained algorithm.

B. The kernel projection machine (KPM) algorithm.

Using the approximate eigenfunctions, the first step consists in computing the empirical minimizers over 1,

Ψ 1 , • • • , Ψ D : f D = arg min f ∈ 1, b Ψ1,••• , b ΨD n i=1 (1 -Y i f (X i )) + . (20)
Note that the constant function 1 equal to one is systematically included in the models in order to take into account translation on the data: this function corresponds to the threshold b in the original SVM algorithm. This optimization problem can be put under the form of a linear programming (LP) problem (see [START_REF] Steinwart | Fast rates for support vector machines using Gaussian kernels[END_REF]

φ j (X i ) = n b λi K 1,n V j (i) = n λ j V (i)
j , so that ( γ, b) are given as the solutions of

( γ, b) = arg min γ∈R D ,b∈R n i=1   1 -Y i   D j=1 γ j V (i) j + b     + .
To conclude, the KPM algorithm can be summarized as follows: 1) given data X 1 , . . . , X n ∈ X and a positive kernel k defined on X ×X , compute the kernel matrix K 1,n and its eigenvectors V 1 , . . . , V n together with its eigenvalues in decreasing order

λ 1 ≥ λ 2 ≥ . . . ≥ λ n . 2)
ξ i ≥ 0 , and Y i   D j=1 γ j V (i) j + b   ≥ 1 -ξ i . (21)
Next, put

α i = D j=1 γ j n λ j V (i) j , and finally f D = n i=1 α i k(x i , .) + b .
3) The last step is the model selection problem consisting in choosing the dimension D ; for this step, we use the penalized trimmed hinge loss as studied earlier:

D = arg min D≥1 1 n n i=1 (1 -Y i f D (X i )) + + λD , (22)
where f D = clip( f D ).

C. Some numerical results.

We first illustrate the Nyström approximation on a controlled example where the theoretical eigenfunctions are known. Then, in our main experiment, the performances of KPM are compared with the SVM on several benchmark classification datasets.

First, we consider the idealized case of a perfect model selection step. This amounts to choosing the regularization parameter for both methods (denoted C in equation ( 9) for the SVM and λ for the KPM) on the test set. This allows to compare directly the best estimators within the families considered by the SVM and the KPM, respectively. Remember that the "KPM classifier family" is formed of empirical risk minimization (ERM) estimators on linear subspaces of increasing dimension, while the "SVM classifier family" can be understood as ERM estimators on RKHS balls of increasing radii. Although selecting the model on the test set does not correspond to a realistic situation, this comparison is useful to decouple and understand separately the quality of the classifier families considered, independently of the additional error introduced by model selection.

In our final experiments, we consider in turn a comparison for a realistic practical scenario: in this case, 5-fold cross-validation is used to select the regularization parameter for each method.

1) Numerical experiments for the Nyström approximation:

The KPM algorithm relies on the Nyström approximation formulated in equations ( 17), [START_REF] De Geer | Classifiers of support vector machine type, with ℓ 1 penalty[END_REF]. In order to illustrate it, a Gaussian kernel is considered along with a Gaussian input distribution Q. In this case, Theorem 9, recalled for completeness in the appendix, gives explicitly the eigenfunctions; they are of multiplicity 1. The empirical eigenfunctions are computed by using formula [START_REF] De Geer | Classifiers of support vector machine type, with ℓ 1 penalty[END_REF] and a random draw of 500 points. Figure 1 is obtained with a = 1 4 and b = 1 18 where b determines the width of the gaussian kernel k(x, y) = e -b(x-y) 2 and a the gaussian law dP (x) = 1 √ 2π e -2ax 2 dx of X. The straight lines (resp. the circles) represent the theoretical (resp. empirical) eigenfunctions. These graphics highlight a consequence of results of [START_REF] Koltchinskii | Asymptotics of spectral projections of some random matrices approximating integral operators[END_REF]: the accuracy of Nyström approximation decreases with the eigenvalues, suggesting that the approximation of the theoretical eigenfunctions by the empirical ones is more suitable for large eigenvalues, i.e., for the first eigenfunctions.

2) Numerical results for the KPM algorithm: The KPM was implemented in Matlab using the free library GLPK for solving the linear optimization problem. Since the algorithm involves the eigendecomposition of the kernel matrix, only relatively small datasets have been considered at this point.

It has been tested on benchmark datasets taken from [START_REF] Raetsch | [END_REF]: they consist in some data originally coming from the UCI repository, to which some standardization transforms have been applied. All datasets consist of 100 samples, each sample being split into a training sample and a test sample; in all datasets except "banana" the 100 samples actually contain the same data points and only differ in the training/test split. The results obtained by applying several state-of-art classification algorithms have been reported in [START_REF] Raetsch | [END_REF], including the SVM with Gaussian kernel k(x, y) = e -x-y 2 2σ 2

. In this case, suitable values (chosen by cross-validation) for parameters σ G (kernel width) and C G (SVM regulatization parameter) are also reported. These values are specific to each benchmark dataset G.

In all experiments presented here, we used the Gaussian kernel with parameter σ G fixed to the value reported in [START_REF] Raetsch | [END_REF]. Without selecting the regularization parameter, the family of classifiers obtained by the KPM algorithm is ( f D ) D≥1 and the family obtained by the SVM algorithm is ( f C ) C∈C . The set C of possible regularization constants that we consider for the SVM are tailored to each benchmark G by forming a geometric sequence of 101 points running over C G /100 to 100 C G and containing the "optimal" C G .

Comparison of the family of SVM classifiers and KPM classifiers. Remember that here we aim at comparing the two families by shunting off the model selection procedure . In table I, for each sample, the smallest test error of the KPM (w.r.t. the parameter D) is compared with the smallest test error of the SVM (w.r.t. the parameter C). Each time, the winner is given one point.

Parameter selection by cross-validation. Table II presents results of SVM (resp. KPM) where the regularization parameters C (resp. λ) is chosen by 5 fold-cross-validation separately on each of the samples. The results are presented in the form { mean of the 100 test errors } ± { variance of the 100 test errors }.

These two tables highlight that the performances of KPM are comparable with the SVM. Considering table I, the SVM appears to have a slight advantage over the KPM which also appears in table II when the parameters are selected by crossvalidation. However, note that average differences are quite small, in particular relative to the variance. Moreover, it is worth noticing that the same fixed parameter σ G is used for the KPM and the SVM, whereas it was originally tailored in [START_REF] Raetsch | [END_REF] for good performance of the SVM only. Finally, from an algorithmic optimization point of view, a nice property of the KPM is that the classifier f D can be used as a "hot start" point in the optimization search for f D+1 since f D ∈ S D+1 . This will gnerally make the procedure faster than restarting separately the optimization for each value of D .

V. CONCLUSION AND DISCUSSION.

A. Highlight of the present work.

We described the finite dimensional approach in the classification framework and deduced an effective algorithm: the KPM. The model selection aspect is tackled using a penalized criterion: we gave theoretical results justifying the use of a penalty which is a linear function of the dimension. We presented a theoretical study comparing known bounds on convergence rates of the finite-dimensional projection approach as compared to the SVM. We also compared performances of the KPM against the SVM in a realistic scenario in which the KPM appeared to be almost as efficient as the SVM although some parameters shared by both methods were chosen to optimize the SVM performance.

The main point of all the presented results is to highlight that regularization can be performed thanks to a dimensionality reduction method such as Kernel-PCA . Consequently, the finite dimensional projection is a credible alternative to the Tikhonov's regularization used, for example, in the SVM algorithm.

An interesting view of the KPM is is that the training labels are used to select the optimal dimension D in a dimensionreduction method -optimal means that the resulting D-dimensional representation of the data contains the right amount of information needed to classify the inputs. To sum up, the KPM can be seen as a dimensionality-reduction-based classification method that takes into account the labels for choosing the right dimension in the dimensionality reduction step.

B. Comparison with other work.

We provided a detailed comparison of the theoretical bounds obtained for the KPM and of the bounds obtained in [START_REF] Blanchard | Statistical performance of support vector machines[END_REF] for the SVM. It is more difficult to draw a meaningful comparison with other known bounds on the SVM; for example, in [START_REF] Steinwart | Fast rates for support vector machines using Gaussian kernels[END_REF], a Gaussian kernel with width depending on the sample size n as well as on some "geometric" assumptions on P (Y |X) is considered. Here our focus was on a fixed kernel.

In [START_REF] De Geer | Classifiers of support vector machine type, with ℓ 1 penalty[END_REF], estimators with a finite expansion on a fixed function basis are considered, which is related to the present setting. A ℓ 1 -penalty in the coefficients is considered, and the procedure is shown to be adapative to the "Tsybakov noise exponent" parameter (a more general version of ( 5)). Here, we study a ℓ 0 -penalty and our results are not adaptive to the noise margin parameter. However, [START_REF] De Geer | Classifiers of support vector machine type, with ℓ 1 penalty[END_REF] needs additional hypotheses on the L 2 (Q) structure of the function family considered as well as on their supremum norm. In contrast, our focus here for the theoretical part was to obtain results on arbitrary function subspaces S D without additional hypotheses.

C. Discussion: inverse problems and the spectral point of view.

It is interesting to note that, in the case of least squares regression, both Tikhonov's regularization and the finite-dimensional projection (when the projection dimension is fixed) can be seen as special cases of a large class of linear estimators that have a diagonal form when expanded on the eigenfunction basis of a certain autoadjoint operator A . In the present case, A is the kernel integral operator, but in a broader point of view, A could be more general. This is precisely the setting which is traditionally the basis of the inverse problems litterature. A recent and very general account of this point view for linear least squares estimation can be found in [START_REF] Bissantz | Convergence rates of general regularization methods for statistical inverse problems and applications[END_REF] , where a much broader situation is studied (i.e. the operator A is not assumed to be compact, so that the spectrum may not be discrete, in which case the most elegant way to describe linear estimators is really directly by their action on the spectrum).

Interpreting classification problems as inverse problems is not new (seminal ideas are found in [START_REF] Vapnik | Estimation of Dependences Based on Empirical Data[END_REF]), but has received renewed attention recently due in particular to the strong link of support vector machines with inverse problems, as studied notably in [START_REF] Vito | Learning from examples as an inverse problem[END_REF]. In the present paper, what we called finite dimensional projection generally referred to as spectral cut-off method in the inverse problems litterature.

A major part of the difficulties arising in the study of such methods for classification problems resides in the non-least squares cost function, so that the penalized empirical risk minimizer does not give rise to a linear estimator. In the present work, we have studied convergence rates for an equivalent of spectral cut-off in this setting (more precisely, combined with adequate model selection). Clearly, it would be of great interest to develop this point of view in more generality for classification problems and possibly try to recover the extent of results available for inverse problems in regression.

D. Ending remarks and future work.

The main drawback of Theorem 1 is the lack of adaptativity to the noise margin: the penalty function involves the unknown noise margin parameter. This leads to difficulties to calibrate the penalization constant in practice. We plan to investigate other calibration techniques for λ than cross-validation. One interesting direction is the so-called "slope heuristic" where the behavior of the empirical error of f D as a function of D is used to select a suitable parameter λ.

An interesting potential advantage of the KPM with respect to the SVM is that it can easily be extended to use different kernels simultaneously by considering finite dimensional spaces spanned by eigenfunctions of kernel operators associated to several different kernels. Oracle inequalities can be obtained in this case using the same methodology (it suffices to change accordingly the weight x D appearing in the proof of Theorem 1). To avoid additional technicalities, in this paper, only the simplest version involving one model for each dimension is stated. However, it is clear that an extension where several subspaces with the same dimension D are available is straightforward.

Taking into account precisely the variability in the data-dependent models is also an interesting topic. One possible lead is to use stability results on the estimated models (see, e.g., [START_REF] Zwald | On the convergence of eigenspaces in kernel principal component analysis[END_REF]); another is to extend the study of the method in a semi-supervised setting where unlabeled data is available, thereby developing the ideas of Section IV.

APPENDIX RISK BOUNDS FOR THE CLIPPED FINITE DIMENSIONAL APPROACH.

In this appendix, Theorem 1 is proved considering a slightly more generic setting. The training data ((X 1 , Y 1 ), . . . , (X n , Y n )) belong to (X × Y) n and we only assume that the loss function is Lipschitz.

A. Clipped empirical risk minimization on one model.

In this section, we obtain an excess risk bound for a clipped empirical error minimizer s D over a fixed vector space S D of dimension at most D with a generic loss function γ:

s D = arg min t∈SD 1 n n i=1 γ(t, (X i , Y i )) ,
and

s D = clip( s D ) .
The goal is to estimate the target function s minimizing the risk over a "large" class S ⊃ S D :

s * = arg min s∈S E[γ(s, (X, Y ))] .
The excess risk with respect to γ is:

L(g, s * ) = E [γ(g, (X, Y ))] -E [γ(s * , (X, Y ))] .
In the sequel, s * is supposed to take values in [-1, 1].

All the results will be stated under the following assumption on the loss which we will refer to as "assumption (A)" in the sequel:

(A1) ∀y ∈ Y, γ(y, .) is Lipschitz. (A2) ∀ s ∈ S, ∀ y ∈ Y, ∀ x ∈ X , γ(y, s(x)) ≥ γ(y, clip(s(x))) .
We will prove two results; the first one (Theorem 5) provides an excess risk bound for a fixed model S D ; then, a similar technique will be used to prove a model selection result (Theorem 6). The proofs of these two theorems rely on a very fundamental result coming from [START_REF] Bartlett | Local Rademacher complexities[END_REF], providing a control of the empirical processes over a function class using localized Rademacher averages. We recall it now.

We need to introduce some notation first. A function Ψ : [0, ∞) → [0, ∞) is called sub-root if it is non-negative, nondecreasing and if r → Ψ(r) √ r is non-increasing for r > 0. It can be shown that the fixed point equation Ψ(r) = r has a unique positive solution (except for the trivial case Ψ ≡ 0). Moreover, a sub-root function is a continuous function on ]0, +∞[ satisfing Ψ(r) > r for r ∈]0, r * [ and Ψ(r) < r for r ∈]r * , +∞[. Let F be a set of functions. The following notation for the Rademacher average of F will be useful:

R n F = sup f ∈F 1 n n i=1 ε i f (X i ) ,
where

(ε i ) i=1•••n are independent and identically distributed Rademacher variables (P[ε 1 = 1] = P[ε 1 = -1] = 1/2).
The notation E ε means that the expectation is considered only with respect to ε: the variables X 1 , . . . , X n are "fixed". We now recall the following result: Theorem 3 ( [START_REF] Bartlett | Local Rademacher complexities[END_REF], Theorem 4.1): Let F be a class of functions with ranges in [-1, +1] and assume that there is some constant κ such that for every f ∈ F, P f 2 ≤ κP f . Denote star(F) = {λf, 0 ≤ λ ≤ 1 , f ∈ F} . Let Ψ n be a (possibly data-dependent) sub-root function and let r * be the fixed point of Ψ n . Fix ξ > 0 and assume that Ψ n satisfies, for any r ≥ r * ,

Ψ n (r) ≥ 2(10 ∨ κ)E ǫ R n {f ∈ star(F); P n f 2 ≤ 2r} + (2(10 ∨ κ) + 11) ξ n . (23)
Then, for any K > 1 with probability at least 1 -3e -ξ ,

∀f ∈ F, P f ≤ K K -1 P n f + 6K κ r * + ξ(11 + 5κK) n .
The crux of the results to come will rely on the application of Theorem 3 to the excess loss function class on a model S D , defined as

F D = {(x, y) → γ(s(x), y) -γ(s * (x), y), s ∈ clip(S D )} . (24)
An important technical result is therefore to have an estimate of the fixed point r * appearing in Theorem 3, for the above class. This is the goal of the following result, whose proof is postponed to section D. Theorem 4: Let F D be defined as in [START_REF] Evgeniou | Regularization networks and Support Vector Machines[END_REF]; assume |s * (x)| ≤ 1 , and that (A1) is satisfied. Let r * D,n denote the fixed point of the sub-root function ψ(r) = E ε R n f ∈ star(F D ) , P n f 2 ≤ 2r . Then, the following holds:

r * D,n ≤ A 1 D + 1 n log n D + + 1 . ( 25
)
where A 1 is a constant (A 1 = 1200 is suitable). With these prerequisites in hand, we are now in a position to state and prove our main results. The first one concerns estimation on a fixed model S D .

Theorem 5: Let S D be a vector space of dimension at most D. Assume the following conditions are met: (i) The target function is bounded by 1:

|s(x)| ≤ 1 . (ii) γ satisfies assumption (A) . (iii) P f 2 ≤ κP f for all f ∈ F D = {γ(t) -γ(s * ), t ∈ clip(S D )} .
Then, for all K > 1 , the following inequality holds:

E [L( s D , s * )] ≤ K K -1 inf t∈SD L(t, s * ) + C 3 K (10 ∨ κ) 2 κ D n log n + C 4 K(κ ∨ 10) n ,
where C 3 and C 4 are numerical constants.

Proof of Theorem 5 . Let s D be an arbitraty element of S D . First, note that

P n (γ( s D ) -γ(s)) ≤ P n (γ( s D ) -γ(s)) ≤ P n (γ(s D ) -γ(s)) , (26)
where the first inequality follows from assumption (A2) and the last from the definition of the empirical minimizer. Thus,

L( s D , s * ) = P (γ( s D ) -γ(s * ) ≤ (P -P n )(γ( s D ) -γ(s * )) + P n (γ(s D ) -γ(s * )) . (27)
In order to control (P -P n )(γ( s D )-γ(s * )), we apply as announced Theorem 3 to the class of functions F D = {γ(t)-γ(s * ), t ∈ clip(S D )}. Note that by assumptions (i) and (A1), all functions in F D have range in [-1, 1] which is the first requirement to apply Theorem 3. Then, assumption (iii) is the second condition required to apply Theorem 3. We now need to find the fixed point of the function appearing in [START_REF] Blanchard | Statistical performance of support vector machines[END_REF]. Let ξ > 0 be fixed. Theorem 4 gives us a bound on the fixed point r * D,n of the sub-root function ψ(r) = E ε R n f ∈ star(F D ) , P n f 2 ≤ 2r . In sight of [START_REF] Blanchard | Statistical performance of support vector machines[END_REF] , we need a bound on the fixed point r * D,n of an affine tranform a ψ(x) + b of ψ (with a = 2(10 ∨ κ), b = (2(10 ∨ κ) + 11) ξ n ). Elementary arguments not reproduced here (see [START_REF] Bousquet | Concentration inequalities and empirical processes theory applied to the analysis of learning algorithms[END_REF], Lemma 4.10) then show that

r * D,n ≤ 4a 2 r * D,n + 2b ≤ 16(10 ∨ κ) 2 A 1 D + 1 n log n D + + 1 + 2ξ n (2(10 ∨ κ) + 11) ≤ C (10 ∨ κ) 2 D log n n + C ′ ξ(10 ∨ κ) n . (28)
Consequently, Theorem 3 implies that ∀K > 1, with probability at least 1 -3e -ξ , ∀f ∈ F D ,

(P -P n )f ≤ 1 K -1 P n f + 6K κ r * D,n + ξ(11 + 5κK) n .
Since the bound is available simultaneously for all functions in F D , we can apply it to the random function f = γ( s D )-γ(s * ) ∈ F D . This yields that, with probability at least 1 -3e -ξ ,

(P -P n )(γ( s D ) -γ(s * )) ≤ 1 K -1 P n (γ( s D ) -γ(s * )) + 6K κ r * D,n + ξ(11 + 5κK) n (29) ≤ 1 K -1 P n (γ(s D ) -γ(s * )) + 6K κ r * D,n + ξ(11 + 5κK) n ,
where we have used again inequality [START_REF] Baker | The numerical treatment of integral equations[END_REF] for the last step. We now plug this inequality into [START_REF] Schölkopf | Nonlinear component analysis as a kernel eigenvalue problem[END_REF] to obtain

L( s D , s * ) ≤ K K -1 P n (γ(s D ) -γ(s * )) + 6K κ r * D,n + ξ(11 + 5κK) n .
This concludes the proof of Theorem 5 by integrating with respect to the sample, bounding r * D,n using [START_REF] Koltchinskii | Asymptotics of spectral projections of some random matrices approximating integral operators[END_REF], then taking the infimum over s D ∈ S D .

B. Model selection by penalization.

We now present a relatively general result about penalized minimization of the trimmed empirical risk over finite dimensional vector spaces. Theorem 1 will then be derived as a corollary.

Theorem 6: Let {S D } D≥1 be a collection of vector spaces such that dim(S D ) ≤ D. Assume the following: (i) The target function is bounded by 1:

|s * (x)| ≤ 1 . (ii) γ satisfies assumption (A) . (iii) P f 2 ≤ κP f for all f ∈ F D = {γ(t) -γ(s * ), t ∈ clip(S D )} . Let K > 1.
Choosing the dimension with the following penalized criterion

D = arg min D≥1 1 n n i=1 γ( s D , (X i , Y i )) + pen n (D) ,
with a possibly data dependent penalty function pen n such that

∀ D ≥ 1 , pen n (D) ≥ C 5 K (κ ∨ 10) 2 κ D n log n , (30)
the following inequality holds

E[L( s b D , s * )] ≤ K K -1 inf D≥1 inf s∈SD L(s, s * ) + E[pen n (D)] + C 6 K(κ ∨
where the second inequality is due to assumption (A2). Thus, ∀D ≥ 1 ,

L( s b D , s * ) = (P -P n )(γ( s b D ) -γ(s * )) + P n (γ( s b D ) -γ(s * )) ≤ (P -P n )(γ( s b D ) -γ(s * )) + n (γ(s D ) -γ(s * )) + pen n (D) -pen n ( D) . (32)
Let D ′ ≥ 1. Let x D be such that D≥1 e -xD ≤ 1. We now follow the same reasoning leading to inequality [START_REF] Dauxois | Asymptotic theory for the Principal Component Analysis of a vector random function: some applications to statistical inference[END_REF] in the proof of Theorem 5, and also use [START_REF] Koltchinskii | Asymptotics of spectral projections of some random matrices approximating integral operators[END_REF], obtaining that ∀K > 1 , with probability at least 1 -3e -ξ-x D ′ ,

(P -P n )(γ( s D ′ ) -γ(s * )) ≤ 1 K -1 P n (γ( s D ′ ) -γ(s * )) + C K(10 ∨ κ) 2 κ D ′ n log(n) + C ′ K(ξ + x D ′ )(10 ∨ κ) n ,
We now use a union bound to obtain the previous inequality simultaneously for all D ′ ≥ 1 and apply it to D ′ = D. With probability at least 1 -3e -ξ ,

(P -P n )(γ( s b D ) -γ(s * )) ≤ 1 K -1 P n (γ( s b D ) -γ(s * )) + C K(10 ∨ κ) 2 κ D n log(n) + C ′ K(ξ + x b D )(10 ∨ κ) n .
Plugging this inequality into (32) and using again (31) leads to:

L( s b D , s * ) ≤ C K(10 ∨ κ) 2 κ D n log(n) + C ′ K(ξ + x b D )(10 ∨ κ) n + K K -1 P n (γ(s D ) -γ(s * )) + pen n (D) -pen n ( D) .
Choosing x D = 2 log(D + 1), condition (30) entails

L( s b D , s * ) ≤ C ′ Kξ(10 ∨ κ) n + K K -1 (P n (γ(s D ) -γ(s * )) + pen n (D)) .
Taking the infimum over D ≥ 1 and integrating with respect to the sample:

L( s b D , s * ) ≤ K K -1 E inf D≥1 (P n (γ(s D ) -γ(s * )) + pen n (D)) + C ′ 3K(10 ∨ κ) n ,
and finally:

L( s b D , s * ) ≤ K K -1 inf D≥1 (P (γ(s D ) -γ(s * )) + E[pen n (D)]) + C ′ 3K(10 ∨ κ) n .
This concludes the proof of Theorem 6.

C. Application to classification: proof of Theorem 1.

Theorem 1 is now a simple consequence of Theorem 6 whose conditions are met for the hinge loss with S = L 2 (Q) and s * = f * (the Bayes classifier). Checking for conditions (i)-(ii) of Theorem 6 is straightforward, and the lemma below ensures that assumption (iii) is met with κ = 1 h0 . (A related result appears in [START_REF] Blanchard | Statistical performance of support vector machines[END_REF], but we provide a proof here for completeness.) This concludes the proof of Theorem 1.

Lemma

7: Let f : X → [-1, 1]. We suppose that |η(x) -1 2 | ≥ h 0 where η(x) = P [Y = 1|X = x]. Then γ h (f ) -γ h (f * ) 2 2 ≤ 1 h 0 L h (f, f * ) .
Proof of Lemma 7. Since f, f * take their values in the interval [-1, 1] , we have

(1 ± f (x)) + = 1 ± f (x) and (1 ± f * (x)) = 1 ± f * (x)
, so that we can write explicitly

L h (f, f * ) = η(x)[(1 -f (x)) + -(1 -f * (x)) + ] + (1 -η(x))[(1 + f (x)) + -(1 + f * (x)) + ] dP (x) = η(x)(f * (x) -f (x)) + (1 -η(x))(f (x) -f * (x)) dP (x) = |2η(x) -1| |f * (x) -f (x)| dP (x) ,
(where the introduction of absolute values in the last line can be checked to hold separately for the two cases (p(x)

> 1 2 , f * (x) = 1) and (p(x) < 1 2 , f * (x) = -1)), and
γ h (f ) -γ h (f * ) 2 2 = η(x)[(1 -f (x)) + -(1 -f * (x)) + ] 2 + (1 -η(x))[(1 + f (x)) + -(1 + f * (x)) + ] 2 dP (x) . = (f (x) -f * (x)) 2 dP (x) .
Hence the ratio of the two integrands is just

|f (x) -f * (x)| |2η(x) -1| ≤ 1 h 0 ,
and the statement follows by integrating with respect to x.

D. Proof of Theorem 4.

Below we will use the standard covering number notation: let N (ǫ, G, d) (resp. M(ǫ, G, d)) denote the covering number (resp. packing number) of set G for distance d. The proof of Theorem 4 is inspired by the work of L. Györfi and al. [START_REF] Györfi | A Distribution-Free Theory of Nonparametric Regression[END_REF]. In particular, it relies on Theorem 9.4 of this reference for the control of packing numbers on VC-subgraph sets of functions. We reproduce it here:

Theorem 8 (Györfi et al.): Let G be a class of functions g : X -→ [0, A] with V (G) ≥ 2. Let p ≥ 1 and ν be a probability measure on X . Let ε such that 0 < ε < A 4 . Then the following holds :

M(ε, G, . Lp(ν) ) ≤ 3 2eA p ε p log 3eA p ε p V (G)
, where V (G) is the VC-dimension of all subgraphs of functions of G , i.e., the set {{(z, t) ∈ X × R; t ≤ g(z)}; g ∈ G} .

To begin with, we control the L 2 (P n )-covering numbers of star(F D ) . Note that since this set contains the null function and has diameter bounded by 1, any covering number for ε > 1 is equal to 1. In what follows we therefore assume ε ≤ 1 .

Following [START_REF] Bartlett | Local Rademacher complexities[END_REF], since any g ∈ star(F) is of the form g = λf with λ ∈ [0, 1] , f ∈ F , we can construct an ε-cover of star(F) by taking the direct product of an ε 2 -cover for F and an ε 2 -cover for the interval [0, 1], which implies

N (ε, star(F), L 2 (P n )) ≤ 2 ε + 1 N ε 2 , F, L 2 (P n ) . (33)
Moreover,

N ε 2 , F, L 2 (P n ) ≤ M ε 2 , F, L 2 (P n ) ≤ M ε 2 , {t -s, t ∈ clip(S D )}, L 2 (P n ) = M ε 2 , {t + 1, t ∈ clip(S D )}, L 2 (P n ) ,
where the second inequality holds because γ is Lipschitz, and the last equality holds because covering and packing numbers are translation invariant.

We now apply Theorem 8 with A = 2 , thus, for 0 < ε < .

The second inequality is obtained by using log(x) ≤ x e . Moreover, V (clip(S D )+1) = V (clip(S D )) ≤ V (S D ) ≤ D +1 . The first equality holds because the subgraph VC-dimension is translation invariant. The last inequality is a well-known property of finite dimensional function spaces (see, e.g., Lemma 2.6.15 of [START_REF] Van Der Vaart | Weak Convergence and Empirical Processes[END_REF]). Finally, the middle inequality comes from the observation that a discrete set shattered by the subgraph class of clip(G) is also shattered by the subgraph class of G . Namely, let (z i , t i ) 1≤i≤K be a finite set shattered by the subgraph class of clip(G) . We must have -1 < t i ≤ 1 for all i , since otherwise the corresponding point would belong to (resp. be outside of) the subgraph of all functions. Using this property, it is easy to check that, if a function family (clip(g j )) 1≤j≤2 K is a witness of the shattering in clip(G) , then so is (g j ) in G . Now, gathering inequality [START_REF] Vapnik | Estimation of Dependences Based on Empirical Data[END_REF] and the previous ones, we get for 0 < ε < We now use Dudley's entropy integral (also known as chaining technique, see [START_REF] Dudley | Uniform Central Limit Theorems, ser. Cambridge Studies in advanced mathematics[END_REF]) theorem, which states that

E ε R n (G) ≤ 4 √ 2 √ n ∞ 0 log N (u, G, L 2 (P n ))du .
Therefore, using the above upper bound on the covering numbers and standard calculus, (β iβ * i ) 2 . The infimum point (β • i ) is such that every partial derivative with respect to β i cancels, so that

ψ(r) = E ǫ R n f ∈ star(F), P n f 2 ≤ 2r ≤ 4 √ 2 √ n
β • i = β * i λ i λ i + 2Λ n µ β • ,
and

µ β • = 2 i≥1 β * i Λ n µ β • λ i + 2Λ n µ β • 2 ≥ 1 2 i≥1 s.t. λi≤2Λnµ β • β * 2 i .
Since λ j = Θ(j -2γ ) , the condition λ i ≤ 2Λ n µ β • is implied by i ≥ cn This concludes the proof of the lemma.

ADDITIONAL MATERIAL: EIGENFUNCTIONS IN THE GAUSSIAN CASE

We use the following normalization for the Hermite polynomials: H n is an orthogonal system of L 2 (e -x 2 ) i.e. e 2λx-λ 2 = n≥0 H n (x) λ n n! . In this case, if f n (x) = H n (x)e -x 2 2 then f n , f m L2(R) = δ n,m √ π2 n n!.

Theorem 9 ( [START_REF] Zhu | Gaussian regression and optimal finite dimensional linear models[END_REF] and [START_REF] Williams | The effect of the input density distribution on kernel-based classifiers[END_REF]): Let dµ(x) = 1 √ 2π e -2ax 2 dx and T k be the integral operator associated with the Gaussian kernel k(x, y) = e -b(x-y) 2 .

T k : L 2 (µ) → L 2 (µ) f → R f (x)e -b(x-y) 2 dµ(x)

An explicit orthonormal basis of L 2 (µ) of eigenvectors of T k associated to λ j = 1 2A b A j-1 is given by: Ψ j (x) = (4c)

1 4 e -(c-a)x 2 H j-1 ( √ 2cx)

(2 j-1 (j -1)!)

1 2
where c = √ a 2 + 2ab and A = a + b + c and j ≥ 1.

Finite

  the functional subspace spanned by the first D functions in the family. The following classifier is associated to each dimension D ∈ N * by minimization of the empirical hinge risk over S D :

  below). If we adopt the parametrization by ( γ, b) of f , of the form f D = φ j + b * , then equation (18) leads to

  for each dimension D such that λ D > 0 solve the linear optimization problem γ, b = arg min γ,b,ξ n i=1 ξ i under the constraints: ∀i = 1 . . . n :

Fig. 1 .

 1 Fig.1. From the left to the right: approximation of the first, the second, the third eigenfunctions of the kernel integral operator for a Gaussian kernel and Gaussian input distribution.

  of the third eigenfunction with n=500

where C 5

 5 and C 6 are numerical constants. Proof: Let s D be a fixed element of S D . The definition of s b D leads to the following chain of inequalities: ∀D ≥ 1, P n γ( s b D ) + pen n ( D) ≤ P n γ( s D ) + pen n (D) ≤ P n γ( s D ) + pen n (D) ≤ P n γ(s D ) + pen n (D) ,

1 ,

 1 log N (ε, star(F), L 2 (P n ))

2 :+ 1 , 1 2

 211 = φ(r) .We easily check that φ is a sub-root function. Hence, the fixed point r * of φ is an upper bound on the fixed point r * D,n of ψ . Our goal is now to upper bound r * by r * D,n = A 1 D+1 n log n D + + 1 ; once this is established the proof is finished. By properties of sub-root functions, the inequality r * ≤ r * D,n is equivalent to the following inequality being statisfied:φ r * D,n ≤ r * D,n .(34)If A 1 ≥ 11 2 /(2e), then it can be checked that log where C = 22 A 1 log[START_REF] Györfi | A Distribution-Free Theory of Nonparametric Regression[END_REF] . We obtain[START_REF] Bousquet | Concentration inequalities and empirical processes theory applied to the analysis of learning algorithms[END_REF] by noting thatC ≤ A 1 if A 1 ≥ 1200 . PROOF OF LEMMA 2. Let β * i = f * , φ i L2(Q) . Obviously inf g∈SD gf * Q,2 is attained for g = -α + D n n -2α-1 2α+1 ,where we have used β * i = Θ(j -α ) and taken D = ⌊n 2 2α-1 ⌋ . For the second inequality of the lemma, putting Λ n = n -2γ 2γ+1

.

  c . Since β * j = O(j -α ) , this leads to µ β • n -Finally solving this inequality for 2α -1 < 4γ entailsµ β • n -4(2α-1)γ (4γ+2)(4γ-2α+1) , so that inf g∈H gf * 2 + Λ n g 2 H n -4(2α-1)γ 2(2γ+1)(4γ-2α+1) .

TABLE I BEST

 I CLASSIFIER IN THE FAMILY (NB. OF WINS)

		KPM SVM
	Banana	31	67
	Breast Cancer 44	50
	Diabetis	55	42
	Flare Solar	19	63
	German	43	49
	Heart	27	64
	TABLE II
	TEST ERRORS
		SVM	KPM
	Banana (σ = 0.7071)	10.69 ± 0.67 10.91±0.57
	Breast Cancer(σ = 5)	26.68 ± 5.23 28.73±4.42
	Diabetis (σ = 3.1623)	23.79 ± 2.01 23.77±1.69
	Flare Solar (σ = 3.8730)	32.62 ± 1.86 32.52±1.78
	German (σ = 5.2440 )	23.79 ± 2.12 24.09±2.38
	Heart (σ = 7.7460 )	16.23 ± 3.18 17.35±3.54

  1, M ε 2 , {t + 1, t ∈ clip(S D )}, L 2 (P n )

	≤ 3	32e ε 2 log	ε 2 48e	V (clip(SD)+1)
	≤	ε 11	4V (clip(SD)+1)

ACKNOWLEDGEMENTS

We are extremely grateful to P. Massart and R. Vert who contributed equally with us in the original introduction of the KPM algorithm in [8] and kindly allowed us to reuse the code and algorithm presentation for the purposes of the present paper.

Support from the IAP research network nr. P6/03 of the Federal Science Policy, Belgium, is acknowledged. This work was supported in part by the IST Programme of the European Community, under the PASCAL Network of Excellence, IST-2002-506778.


E Liarokapis

D Lampakis

E Siranidi

M Calaniotou

Pressure induced lattice instability and phase separation in the cuprates

High pressure structural studies using a synchrotron source and Raman measurements on various cuprates reveal several structural modifications. The data have shown strong deviations from the normal equation of state at characteristic pressures, hysteresis, and the appearance of additional peaks that can be attributed to a new phase. The combined data of synchrotron angle-dispersive experiments with the optical measurements indicate that at some critical pressures, at least for certain compounds, non-linear effects are observed together with phase separation that affect the distribution of the carriers and the transition temperature. The comparison of the data with those induced by an internal pressure by an atomic substitution indicates that the effect is related to the existence of carriers within the CuO 2 superconducting planes.

INTRODUCTION

Chemical doping induces radical modifications in the characteristic properties of the high T c cuprates, with the appearance of superconductivity in a small range of carrier concentration [1,2]. The systematic studies over the years have proved that there are several competing order parameters, which complicate the phase diagram [3]. Hydrostatic pressure is one, rather clean, way to investigate the phase diagram and the competing parameters without the complications that arise from possible inhomogeneities in the case of chemical doping. ȉhe pressure dependence (dT c /dP) of the superconducting transition temperature T c of the cuprates varies with doping and among the compounds [4]. In some cases a strong pressure increase of T c leads to the discovery of new compounds with higher T c by mimicking the external by an internal (chemical) pressure [5]. Over the last years we have carried out systematic Raman measurements under high pressure on several high T c cuprates, which have indicated lattice instabilities and phase separation at critical pressures, where the transition temperature shows a non-linear dependence on pressure [6][7][8]. Those studies indicate that the hydrostatic pressure has a non-linear effect on the structure of those compounds and induces lattice distortions and instabilities exactly where dT c /dP shows anomalies [9]. The analysis of the Raman spectral modifications under pressure points to variations in the bond lengths within the CuO 2 planes and in the tilting of the CuO 5 pyramids [7]. Due to the strong anisotropicity of those compounds, the dT c /dp value actually reflects the average strain dependence of the three lattice axis.

By combining the high pressure Raman data with synchrotron measurements under pressure, we find clear evidence that for certain cuprates (YBa 2 Cu 3 O 7 [10], PrBa 2 Cu 3 O 7 , YBa 2 Cu 4 O 8 [11]) there are pronounced deviations from the normal equation of state at pressures, where there is a change in T c . The comparison of these results with those from rare earth substitutions that induce an internal pressure reveals systematic instabilities in all cuprates studied. In this work, data from several

A c c e p t e d m a n u s c r i p t

hydrostatic pressure measurements are presented and discussed that show the contribution of the lattice to the dT c /dp dependence.

EXPERIMENTAL METHOD

The Raman measurements have been carried out on several cuprates at high hydrostatic pressures (up to 8 GPa) using a T64000 Jobin-Yvon triple spectrometer. A liquid nitrogen cooled charge coupled device (CCD) was the detector and the spectrometer was equipped with a microscope of magnification ×100 (×40 for the hydrostatic pressure measurements). For the high-pressure measurements a Merrill-Bassett type diamond anvil cell (DAC) was used with a mixture of methanol-ethanol as the pressure-transmitting medium. Various silicon crystals were used inside the gasket to monitor the pressure and any deviation from quasi-hydrostatic conditions. The beam from several lines of an Ar + laser was focused on the sample at a spot of diameter 1-2 ȝm (×100) or 3-5 ȝm (×40), while the power level was kept below 0.20 mW (or 0.40 mW for the high pressure measurements). Always freshly cut samples were used for the study of the various scattering geometries.

The synchrotron xrd measurements were carried out in ESRF with a dense sampling over an extended pressure range (a ~0.5GPa step up to ~14 GPa in compression). The data have been collected both on pressure increase and on decompression using a DAC and a 4:1 methanol-ethanol mixture as a pressure medium. 2D diffraction images have been recorded with a wavelength Ȝ= 0.7117 Å using a MAR345 image plate detector and have been converted to 2ș patterns after correcting for distortions and refining the detector distance using a LaB 6 standard by fit-2d [12]. The intensity vs. 2ș patterns have been analysed with the Rietveld method using Fullprof [13].

RESULTS AND DISCUSSION

Figure 1 presents Raman spectra in the zz-scattering polarization of YBa 2 Cu 3 O x for selected hydrostatic pressures and two oxygen concentrations, optimally doped (ortho-I phase with T c =92K) and half doping (x=6.5, ortho-II phase with T c =60K). For both concentrations there is an apparent splitting of the in-phase mode of the plane oxygen atoms O2,3 around p~2 GPa marked in figure with straight lines. A similar splitting of this mode has been observed in the YBa 2 Cu 4 O 8 superconductor with the intensity of the two peaks depending on the direction of polarization of the incoming and scattered light [6]. In Bi 2 Sr 2 CaCu 2 O 8 the relative mode has also shown a splitting at a similar critical pressure [14] and the effect seems to be characteristic in all cuprates.

Furthermore, pressure induces a non-linear dependence of the frequency of the A g -phonons in YBa 2 Cu 3 O x [7,8], YBa 2 Cu 4 O 8 [6], and Bi 2 Sr 2 CaCu 2 O 8 [14]. Besides in Fig. 1 there is a pronounced broadening for the phonon of the plane copper atoms (Cu2), which originally becomes much wider with hydrostatic pressure, but around p~3 GPa its width decreases again to practically the same value as at ambient pressure. Similar anomalies in the width appear for the other A g -symmetry phonons [6]. On the other hand, the B 1g -symmetry phonon, which appears in the Raman spectra in xx-polarization does not have any pressure dependence anomaly. This happens for both oxygen concentrations of the superconducting YBa 2 Cu 3 O x and for YBa 2 Cu 4 O 8 [6][7][8] but it does not appear in the non-superconducting PrBa 2 Cu 3 O 7 compound (Fig. 2). The xx-polarization spectra of PrBa 2 Cu 3 O 7 are not pressure The observed hydrostatic pressure induced Raman spectral modifications bears resemblance with the pressure dependence of the superconducting transition temperature of these compounds [5,8]. Therefore, they may be related with charge transfer from the chains to planes, its redistribution between the CuO 2 planes, and other effects. To this context subtle structural modifications and lattice distortions should correlate with pressure modifications of T c and their study can contribute to the efforts of understanding the mechanisms underlying superconductivity in the high temperature superconducting cuprates.

Structural studies under hydrostatic pressure previously reported in these compounds were limited either to the low pressure range (up to 0.6GPa) [15] or by the low resolution of the energy dispersive diffraction method, which were used for the experiment [16]. Structural studies of the YBa 2 Cu 4 O 8 compound as a function of pressure gave only marginal evidence that the changes of the lattice parameters and bond lenghts follow the non-linear pressure dependence observed for T c above 4 GPa [17,18].

We have measured high quality fully refinable angular-dispersive synchrotron powder diffraction patterns under high hydrostatic pressure (up to ~14 GPa with a ~0.5 GPa step) of various high T c superconducting cuprates, e.g. the YBa 2 Cu 4 O 8 , which is a model compound for the under-doped oxides, the optimally doped YBa 2 Cu 3 O y superconductor, and the non-superconducting PrBa 2 Cu 3 O 7 cuprate. Our measurements of high quality synchrotron powder diffraction patterns with a dense sampling over an extended pressure range document a clear deviation of the structural parameters from the expected equation of state correlating with phase separation effects.

With the application of hydrostatic pressure, the YBa 2 Cu 3 O 7 superconductor shows a strong anomaly mainly on the c-axis and to a smaller extend on the b-axis [10]. The data are presented in Fig. 3 both for increasing and decreasing pressures. It is clear that there is a deviation from expected pressure dependence in the pressure range ~3.5-10.5 GPa. Besides, there is an obvious irreversibility on the pressure dependence, and the data at reducing pressure follow the anticipated normal equation of state, without any anomaly. At the pressure ~3.5 GPa where the data start to deviate from the normal behaviour, new peaks appear in the xrd patterns. The whole structure including the new peaks could not be fitted assuming the formation of a single homogeneous superstructure phase. Therefore, it is induced that the new peaks should correspond to another phase. This phase disappears together with the new peaks upon pressure release at ~3.0 GPa [10], to reappear again if pressure is increased above the same level [11]. If somebody tries to index the new peaks independently of the main phase, it turns out that it could be indexed as a superstructure with about the same c-axis and double the a-and b-axis.

In Fig. 3 the pressure dependence of the c-axis is compared with the modifications recorded in the Raman spectra for the phonon of the apical oxygen atom (frequency and width). Similar behaviour has been observed for the other A gsymmetry phonons of the two superconducting phases of YBa 2 Cu 3 O x [7]. It is seen that up to ~2 GPa there is a continuous increase in the apex phonon frequency, which subsequently remains constant in the interval ~2-3.5 GPa, to increase again at higher pressures. The width of the A g -symmetry phonons shows also unconventional pressure dependence. It increases up to ~2 GPa and subsequently decreases at higher pressures reaching a minimum value of the same amount as in the ambient pressure

A c c e p t e d m

a n u s c r i p t around 3.5 GPa, i.e. at the pressure where the new peaks appear in the xrd patterns and a deviation of the c-axis from the normal equation of state. This unconventional pressure dependence of the phonon modes indicates a phase transformation at this pressure range with a new phase appearing in the same pressure range. The fact that the same phonon modes are present in all spectra proves that there is no structural phase transition to another crystal symmetry, but rather small lattice distortions and sudden modifications in certain bond lengths at a critical hydrostatic pressure. Looking closely at the variation of the bond lengths with pressure, one finds that mainly the bond distances of the Cu2 atom with the oxygen atoms in the planes and the apical are affected [10]. Actually, there is a deviation from the normal reduction of these bond lengths around 3.5 GPa, which explains the modifications in the lattice constants at the same pressure. Since the apical oxygen controls the transfer of carriers to the CuO 2 planes [19], the bond length variations reflect changes in the charge transfer to the superconducting planes from the CuO chains.

In principle, one could mimic the external hydrostatic pressure with rare earth substitutions of varying ionic radius [20,21]. Therefore, if the observed effects under hydrostatic pressure are strictly related to the strain, one should expect to observe similar modifications in the lattice constants and the bond lengths by combinations of rare earth substitutions [20,21]. . The variation of the bond lengths Cu2-O1 (apical), Cu2-O3, and the c-axis with the average ionic radius are presented. For an average radius of ~1.08 Å, there is a deviation in the c-axis mainly for the La-R123 compounds. The compounds with Pr seem to have zero or very small anomalies. The same happens for the bond lengths; the anomaly involves the La compounds, and it is smaller or absent in the Pr substitutions. Only the Cu2-O1 distance varies practically the same way in all substitutions, defining again a critical average ionic radius, where there is a modification in the charge transfer to the CuO 2 planes from the chains.

The large variations in the data points can be understood, because in most of the cases the amount of oxygen was not measured and therefore the exact doping due to oxygen may vary among the compounds. But, the decrease of the Cu2-O1 distance is consistent with an increase in the amount of charge transfer to the superconducting planes, and it does not agree with the disappearance of superconductivity in most of the compounds at large ionic radii. For example the Y-Pr123 and the Pr-R123 compounds are non-superconducting towards the large ionic radii, i.e., exactly after the critical radius of ~1.08 Å. So, the structural data start to deviate very close to the interatomic distances where, for some reason, the carrier properties of the compounds are modified. On the other hand, the La-R123 system remains superconducting in the whole range of ionic radii, in spite the fact that it also shows deviations for the Cu2-O1 bond length at the same critical ionic radius (Fig. 4, middle). The main difference of the La compounds from the other non-superconducting compounds is the increase of the Cu2-O3 distance at the same average radius (Fig. 4, top), which is related with the redistribution of the carriers among the Cu2 and O2,3 atoms. It should be noted that in the mixed compounds, one may have phase separation, especially when there is a large difference between the ionic radii of the two rare earths or yttrium (for average ionic radii smaller than 1.08 ǖ, Ref. [21]). The superconductivity in those systems may be a result of percolation in the phase separated system, where one should expect RBa 2 Cu 3 O x nano-sized regions rich in each rare earth or yttrium [20,21]. This Towards the large values of the ionic radius, one expects the system to behave as homogeneous and therefore, we should look at this region to identify modifications in T c and the structural data. The basic difference is between the La-R123 and the other non-superconducting compounds, which may indicate the importance of the bond length distance within the superconducting planes. Therefore, the strain itself is not the only parameter that defines the effect of pressure, internal or external to the compound, but there are other factors involved that are related to the carriers and the phase separation that affect the superconducting properties of the cuprates. One should always have in mind the lattice effects as well, that can mask the dT c /dp dependence in the cuprates.

CONCLUSIONS

We have carried out a systematic comparison of the hydrostatic pressure dependence of the structural and Raman data for several cuprates. It appears that the synchrotron structural data fully support the original findings of the Raman spectra under pressure bringing more information on the changes in the bond lengths, which are responsible for the spectral modifications. The study of the non-superconducting PrBa 2 Cu 3 O 7 compound shows that there is no structural anomaly, both in the xrd data and the Raman spectra, pointing to some connection of these changes with the amount and the distribution of the carriers. The comparison with all published data on the rare earth substitutions for yttrium that induce an internal pressure, supports our findings and proves that the effect is not simply related to the amount of internal strain, but it is also interrelated to the amount and distribution of carriers, explaining the correlation of the structural anomalies with the dT c /dp non-linear dependence. Raman Shift (cm -1 )

[zz]

[zz]

A c c e p t e d m a n u s c r i p t dependent (Fig. 2 )

 2 , similar with the corresponding spectra in the xx-polarization of the superconducting compounds YBa 2 Cu 3 O x (ortho-I and ortho-II phases).

Figure 4

 4 presents data from various rare earth combinations; RBa 2 Cu 3 O 7 (R123, filled black squares), La 0.5 R 0.5 Ba 2 Cu 3 O 7 (La-R123, open blue squares), Pr 0.5 R 0.5 Ba 2 Cu 3 O 7 (Pr-R123, open green triangles), and Y 1-x Pr x Ba 2 Cu 3 O 7 (Y-Pr123, filled red circles)

A c c e p t e d m a n u s c r i p t

  complicates the interrelation of the structural and Raman data with the variation of T c .

A c c e p t e d m a n u s c r i p t FIGURE CAPTIONS Figure 1 .

 1 FIGURE CAPTIONSFigure1. Characteristic Raman spectra under hydrostatic pressure of the YBa 2 Cu 3 O x superconductor for two oxygen doping levels with T c 92 K (ortho-I) and 60 K (orth-II phase). The modifications in the Cu2 phonon are marked together with the appearance of another peak of the in-phase oxygen mode (straight lines).

Figure 2 .

 2 Figure 2. Raman spectra under hydrostatic pressure of the PrBa 2 Cu 3 O 7 compound, which is not superconducting, in the two scattering polarizations (xx and zz). In the xx-polarization the B 1g -phonon is marked and in the other the Cu2 phonon, both unmodified by the pressure.

Figure 3 .

 3 Figure 3. The comparison of the apical phonon frequency and width (upper part) with the pressure dependence of the c-axis (lower part) in the YBa 2 Cu 3 O 7 superconductor. Crosses define the decompression data and full squares those at increasing pressure.

Figure 4 .

 4 Figure 4. The variation of the Cu2-O3 (top), Cu2-O1 (middle) bond lengths and the caxis (bottom) vs. the average ionic radius for various compounds of the yttrium family: RBa 2 Cu 3 O 7 (R123), La 0.5 R 0.5 Ba 2 Cu 3 O 7 (La-R123), Pr 0.5 R 0.5 Ba 2 Cu 3 O 7 (Pr-R123), and Y 1-x Pr x Ba 2 Cu 3 O 7 (Y-Pr123), where R defines a rare earth ion or yttrium.

ACKNOWLWDGEMENTS

Work partially supported by the E.C. STREP Project COMEPHS.


R Johansson

Ahuja

L Huang

M Ramzan

L Vitos

B Johansson

R Ahuja

Anomalous temperature dependence

Anomalous temperature dependence of elastic constant c in V, Nb, Ta, Pd, and Pt

constant with temperature, while electronic contribution is determined by the unique character of electronic structure of elements and leads to the anomalous effect to the elastic constant with temperature.

A c c e p t e d m a n u s c r i p t I. INTRODUCTION

The elastic constants are perhaps the most fundamental property of condensed matter.

In general, due to the thermal expansion of lattice, the elastic constants show a monotonically decreasing trend with increasing temperature. However, with the pronounced effect of electronic entropy, an anomalous temperature dependence of the shear elastic constant c 44 has been observed for transition metals V, Nb, Ta, Pd, and Pt [1][2][3][4][5][6][7].

In this letter, by applying a simple quasi-harmonic approximation [8], the electronic effect is separately calculated from the normal thermal expansion effect. In this way, the subtle contribution of electronic structure on the temperature dependence of elastic constant can be precisely evaluated. Our theoretical results show a good agreement with the previous experimental measurements. Compared with other theoretical methods [9,10], which can be used for the calculation of elastic constant with temperature, our model shows a good calculation efficiency and a transparent physical picture.

II. METHODS

The isothermal elastic constants c ij ( simplified as c) are derived from the second order strain derivative of the Helmholtz free energy of the system, which can be separated as

F (V, T ) = E e (T, V ) + F v (T, V ) -T S e (T, V ). ( 1
)
where E e is the electronic energy, F v is the phonon vibrational free energy, and S e is the electronic entropy given by

S el = -2k B {f (E)lnf (E) + [1 -f (E)]ln[1 -f (E)]}N(E)dE. ( 2
)
where f (E) is the Fermi-Dirac distribution, N(E) is the density of states (DOS), and k B is the Boltzman constant. The function inside the big brackets is sharply peaked around the chemical potential μ, thus only N(E) around μ gives the contribution to the electronic entropy. The electronic energy E e and entropy S e were calculated using the finite temperature density functional theory [11]. Including explicitly the Fermi-Dirac statistics, the temperature dependent charge density and chemical potential μ are calculated to determine E e and S e . The variation of the elastic constants from zero temperature T 0 = 0K to temperature

A c c e p t e d m a n u s c r i p t

T is equal to Δc(T, V ) ≡ c(T, V )c(T 0 , V 0 ).Δc(T, V ) can be calculated as the sum of a constant temperature and volume component [8] Δ

T c = c(T, V ) -c(T, V 0 ) and Δ V c = c(T, V 0 ) -c(T 0 , V 0 ). (3)
In Fig. 1, the c 44 of Nb, at the constant temperature, shows a closely linear decreasing dependence on increasing volume. The linear dependences for various temperatures are differed by less than 2% up to the melting temperature. Furthermore, we observed the same behavior with all the other calculated elements. Therefore, in this study, we take an approximation assuming Δ T c(T, V ) shows a constant linear dependence of V , thus can be calculated by equation

Δ T c(T, V ) ≈ ∂c ∂V | V 0 ,T 0 [V (T ) -V 0 ], (4)
The thermal expansion can be calculated by the equation

V (T ) -V 0 = T T 0 V (T )αdT , ( 5
)
where α, the thermal expansion coefficient, is calculated using a Debye theory combined with the ab-initio equation of state (EOS) [12]. We neglect the phonon contributions at fixed volume and use the electronic free energy F e (T, V 0 ) to compute Δ V c(T, V 0 ), which only contains the electronic contribution from Fermi-Dirac distribution and its function with T is closely related with the variation of density of states around the Fermi level induced by the distortion matrix of c. The electronic free energies F e are calculated using the exact muffin-tin orbitals (EMTO) method [13,14]. When compared to the conventional muffintin or nonoverlapping approach, the exact crystal potential is more accurately described by the overlapping spheres in EMTO method. The generalized gradient approximation (GGA) [15] was used for treating exchange correlation potential. The s, p, d, and f orbitals (l max =3) are used to solve the one electron equations with the soft-core approximations.

To obtain the good accuracy for the calculation of elastic constants, we used about 30 000 uniformly distributed k points in the irreducible wedge of the Brillouin zones. The shear elastic constant c 44 in cubic lattice is calculated from a volume conserving monoclinic deformation,

⎛ ⎜ ⎜ ⎜ ⎝ 1 0 1 0 0 0 1/(1 -2 ) ⎞ ⎟ ⎟ ⎟ ⎠ . ( 6
)

A c c e p t e d m a n u s c r i p t

The corresponding strain energy

E( ) = E(0) + 2V c 44 2 + O( 4 ) ( 7 )
for four distortions = 0.00, 0.01, 0.02, 0.03 is calculated. The c 44 were determined from the linear function in 2 fitted to the total energy E( ).

III. RESULTS AND DISCUSSIONS

The table I shows the calculated equilibrium volume V 0 , bulk modulus B, elastic constant c 44 , and the thermal expansion coefficient α compared with experimental values [16].

The good agreement between theoretical and experimental data shows that our calculation method can give an accurate description on the ground state properties. are also plotted.

Δc V 44 contains the electronic contribution and is closely related with the density of states around Fermi level. Fig. 4 shows calculated density of states (DOS) around Fermi level for five elements in their equilibrium lattice and in the corresponding c 44 typed monoclinic distorted lattice. The common feature that all the Fermi levels for the five elements are located at the right side of valence band peak can be clearly noticed. The DOS for c 44 typed distorted lattice show subtle variations from the equilibrium lattice. As for the variation of Δc V with temperature, it can be easily deduced that the lower DOS by distorted lattice will give an increasing effect, while the higher DOS by the distorted lattice will give a decreasing effect. Our calculation on the elastic constant can precisely capture the subtle effect of electronic structure of each elements. According to the equation 2, only the density of states around Fermi energy has a contribution to the electronic entropy. When temperature increases, the wider range of density of states around Fermi level will be included to contribute the electronic entropy. For V, Nb, and Ta, the density of states for distorted lattice within ± 0.1 eV around Fermi level show higher than the density of states for bcc lattice, while become lower at the wider energy range. Thus from the Fig. 2 As is seen, the results of Δ T c 44 using Debye model show good agreement with the Δ T c 44 calculated using experimental α, especially at the lower temperature range.

The over all variations of c 44 with temperature are compared with experimental data in

IV. CONCLUSIONS

To summarize, we have shown by approximating the variation of elastic constants with temperature as the sum of thermal expansion and electronic contributions, the anomalous temperature dependence of c 44 for five transition metals V, Nb, Ta, Pd, and Pt, can be accurately captured by our theoretical model. The separating treatment for the different contributions can provide a transparent physical picture on how the each parameters will influence the total variation of elastic constants.

Fig. ( 2

 2 Fig. (2 and 3) shows the calculated temperature dependence of c 44 for the elements Nb and Pd, respectively. In there, the electronic and thermal expansion contributions are shown in (a) and (b), respectively. The total variations of c 44 with temperature are shown in (c) and compared with previous experimental data. The previous reported theoretical results

  (a) Δ V c 44 first shows a A c c e p t e d m a n u s c r i p t decrease at lower temperature and then an increase at higher temperature. For fcc elements Pd and Pt, the DOS for c 44 distorted lattice around Fermi energy are always lower than the DOS for fcc lattice. Thus seen in the Fig. 3 (a), Δ V c 44 always increase when temperature is increased from 0 K. The temperature dependence of the second component Δ T c 44 is much simple. As seen in Fig 2 and 3 (b), when temperature higher than the debye temperature, Δ T c 44 always shows a linearly decreasing trend with increasing temperature and this behavior is the so called normal temperature dependence of elastic constants. Our calculated thermal expansions α for five elements show certain deviation from the experimental values. Using the experimental α, we made recalculation of Δ T c 44 , indicated by the dashed line in Figure (b).

Fig 2 and 3

 3 Fig 2 and 3 (c), which show that the main temperature dependence trend for each elements are closely agreed between experiments and our theory. Especially, for the fcc Pd, the flat curves of c 44 as a function of temperature at lower temperature range is closely captured by our theoretical calculations.

A c c e p t e d m a n u s c r i p t A c c e p t e d m a n u s c r i p t

A c c e p t e d m a n u s c r i p t FIG. 1 :A c c e p t e d m a n u s c r i p t FIG. 2 :

 t1t2 FIG. 1: Elastic constant c 44 as a function of volume at different constant temperatures from 100 K to 4000 K.

A c c e p t e d m a n u s c r i p t FIG. 3 :

 t3 FIG. 3: The calculated temperature dependence of c 44 of fcc Pd. The experimental data [4] are compared with our theoretical result. Other description is the same as in Fig. 2.

TABLE I :

 I Theoretical and experimental[16] equilibrium volume V 0 , bulk modulus B, shear elastic constant c 44 , and thermal expansion coefficient α.

			V 0 ( Å3 )	B(GPa)	c 44 (GPa)	α(x10 -6 K -1 )
	V	EMTO	13.47	175	35.69	6.6
		Exp.	13.77	162	45.87	7.8
	Nb	EMTO	18.13	161	37	6.0
		Exp.	17.98	170	30	7.1
	Ta	EMTO	18.41	185	95.8	4.6
		Exp.	18.13	200	87.6	6.3
	Pd	EMTO	15.48	165	85.15	12.59
		Exp.	14.72	181	71.17	11.6
	Pt	EMTO	15.84	244	98.72	8.13
		Exp.	15.06	230	77.4	8.9