Jean-Yves Audibert

Alexandre B Tsybakov

Fast learning rates for plug-in classifiers under the margin condition

Keywords: AMS 2000 Subject classifications. Primary 62G07, Secondary 62G08, 62H05, 68T10 classification, statistical learning, fast rates of convergence, excess risk, plug-in classifiers, minimax lower bounds

It has been recently shown that, under the margin (or low noise) assumption, there exist classifiers attaining fast rates of convergence of the excess Bayes risk, i.e., the rates faster than n -1/2 . The works on this subject suggested the following two conjectures: (i) the best achievable fast rate is of the order n -1 , and (ii) the plug-in classifiers generally converge slower than the classifiers based on empirical risk minimization. We show that both conjectures are not correct. In particular, we construct plug-in classifiers that can achieve not only the fast, but also the super-fast rates, i.e., the rates faster than n -1 . We establish minimax lower bounds showing that the obtained rates cannot be improved.

Introduction

Let (X, Y ) be a random couple taking values in Z R d × {0, 1} with joint distribution P . We regard X ∈ R d as a vector of features corresponding to an object and 1 Y ∈ {0, 1} as a label indicating that the object belongs to one of the two classes.

Consider the sample (X 1 , Y 1 ), . . . , (X n , Y n ), where (X i , Y i ) are independent copies of (X, Y ). We denote by P ⊗n the product probability measure according to which the sample is distributed, and by P X the marginal distribution of X.

The goal of a classification procedure is to predict the label Y given the value of X, i.e., to provide a decision rule f : R d → {0, 1} which belongs to the set F of all Borel functions defined on R d and taking values in {0, 1}. The performance of a decision rule f is measured by the misclassification error

R(f ) P (Y = f (X)).
The Bayes decision rule is a minimizer of the risk R(f ) over all the decision rules f ∈ F , and one of such minimizers has the form f * (X) = 1I {η(X)≥ 1 2 } where 1I {•} denotes the indicator function and η(X) P (Y = 1|X) is the regression function of Y on X (here P (dY |X) is a regular conditional probability which we will use in the following without further mention).

An empirical decision rule (a classifier) is a random mapping fn : Z n → F measurable w.r.t. the sample. Its accuracy can be characterized by the excess risk

E( fn ) = ER( fn ) -R(f * )
where E is the sign of expectation. A key problem in classification is to construct classifiers with small excess risk for sufficiently large n [cf. [START_REF] Devroye | A Probabilistic Theory of Pattern Recognition[END_REF], [START_REF] Vapnik | Statistical Learning Theory[END_REF]]. Optimal classifiers can be defined as those having the best possible rate of convergence of E( fn ) to 0, as n → ∞. Of course, this rate, and thus the optimal classifier, depend on the assumptions on the joint distribution of (X, Y ). A standard way to define optimal classifiers is to introduce a class of joint distributions of (X, Y ) and to declare fn optimal if it achieves the best rate of convergence in a minimax sense on this class.

Two types of assumptions on the joint distribution of (X, Y ) are commonly used: complexity assumptions and margin assumptions.

Complexity assumptions are stated in two possible ways. First of them is to suppose that the regression function η is smooth enough or, more generally, belongs to a class of functions Σ having a suitably bounded ε-entropy. This is called a complexity assumption on the regression function (CAR). Most commonly it is of the following form.

Assumption (CAR). The regression function η belongs to class Σ of functions on R d such that H(ε, Σ, L p ) ≤ A * ε -ρ , ∀ε > 0, with some constants ρ > 0, A * > 0. Here H(ε, Σ, L p ) denotes the ε-entropy of the set Σ w.r.t. an L p norm with some 1 ≤ p ≤ ∞.

At this stage of discussion we do not identify precisely the value of p for the L p norm in Assumption (CAR), nor the measure with respect to which this norm is defined. Examples will be given later. If Σ is a class of smooth functions with smoothness parameter β on a compact in R d , for example, a Hölder class, as described below, a typical value of ρ in Assumption (CAR) is ρ = d/β. Assumption (CAR) is well adapted for the study of plug-in rules, i.e. of the classifiers having the form f

P I n (X) = 1I {ηn(X)≥ 1 2 } (1.1)
where ηn is a nonparametric estimator of the function η. Indeed, Assumption (CAR)

typically reads as a smoothness assumption on η implying that a good nonparametric estimator (kernel, local polynomial, orthogonal series or other) ηn converges with some rate to the regression function η, as n → ∞. In turn, closeness of ηn to η implies closeness of fn to f : for any plug-in classifier f P I n we have

ER( f P I n ) -R(f * ) ≤ 2E |η n (x) -η(x)|P X (dx) (1.2)
(cf. Devroye, [START_REF] Devroye | A Probabilistic Theory of Pattern Recognition[END_REF], Theorem 2.2). For various types of estimators ηn and under rather general assumptions it can be shown that, if (CAR) holds, the RHS of (1.2) is uniformly of the order n -1/(2+ρ) , and thus sup P :η∈Σ

E( f P I n ) = O(n -1/(2+ρ) ), n → ∞, (1.3)
[cf. [START_REF] Yang | Minimax nonparametric classification -Part I: Rates of convergence, Part II: Model selection for adaptation[END_REF]]. In particular, if ρ = d/β (which corresponds to a class of smooth functions with smoothness parameter β), we get sup

P :η∈Σ E( f P I n ) = O(n -β/(2β+d) ), n → ∞.
(1.4)

Note that (1.4) can be easily deduced from (1.2) and standard results on the L 1 or L 2 convergence rates of usual nonparametric regression estimators on β-smoothness classes Σ. The rates in (1.3), (1.4) are quite slow, always slower than n -1/2 . In (1.4) they deteriorate dramatically as the dimension d increases. Moreover, [START_REF] Yang | Minimax nonparametric classification -Part I: Rates of convergence, Part II: Model selection for adaptation[END_REF] shows that, under general assumptions, the bound (1.4) cannot be improved in a minimax sense. These results raised some pessimism about the plug-in rules.

The second way to describe complexity is to introduce a structure on the class of possible decision sets G * = {x : f * (x) = 1} = {x : η(x) ≥ 1/2} rather than on that of regression functions η. A standard complexity assumption on the decision set (CAD) is the following.

Assumption (CAD).

The decision set G * belongs to a class G of subsets of R d such that

H(ε, G, d △ ) ≤ A * ε -ρ , ∀ε > 0,
with some constants ρ > 0, A * > 0. Here H(ε, G, d △ ) denotes the ε-entropy of the class G w.r.t. the measure of symmetric difference pseudo-distance between sets

defined by d △ (G, G ′ ) = P X (G△G ′ ) for two measurable subsets G and G ′ in R d .
The parameter ρ in Assumption (CAD) typically characterizes the smoothness of the boundary of G * [cf. Tsybakov (2004a)]. Note that, in general, there is no connection between Assumptions (CAR) and (CAD). Indeed, the fact that G * has a smooth boundary does not imply that η is smooth, and vice versa. The values of ρ closer to 0 correspond to smoother boundaries (less complex sets G * ). As a limit case when ρ → 0 one can consider the Vapnik-Chervonenkis classes (VC-classes) for which the ε-entropy is logarithmic in 1/ε.

Assumption (CAD) is suited for the study of empirical risk minimization (ERM) type classifiers introduced by Vapnik and Chervonenkis (1974), see also [START_REF] Devroye | A Probabilistic Theory of Pattern Recognition[END_REF], [START_REF] Vapnik | Statistical Learning Theory[END_REF]. As shown in Tsybakov (2004a), for every 0 < ρ < 1 there exist ERM classifiers f ERM n such that, under Assumption (CAD), sup

P :G * ∈G E( f ERM n ) = O(n -1/2 ), n → ∞. (1.5)
The rate of convergence in (1.5) is better than that for plug-in rules, cf. The margin assumption (or low noise assumption) is stated as follows.

Assumption (MA).

There exist constants C 0 > 0 and α ≥ 0 such that

P X 0 < |η(X) -1/2| ≤ t ≤ C 0 t α , ∀ t > 0. (1.6)
The case α = 0 is trivial (no assumption) and is included for notational convenience. Assumption (MA) provides a useful characterization of the behavior of regression function η in a vicinity of the level η = 1/2 which turns out to be crucial for convergence of classifiers (for more discussion of the margin assumption see Tsybakov (2004a)). The main point is that, under (MA), fast classification rates up to n -1 are achievable. In particular, for every 0 < ρ < 1 and α > 0 there exist ERM type classifiers f ERM n such that sup

P :(CAD),(M A) E( f ERM n ) = O(n -1+α 2+α+αρ ), n → ∞, (1.7)
where sup P :(CAD),(M A) denotes the supremum over all joint distributions P of (X, Y )

satisfying Assumptions (CAD) and (MA). The RHS of (1.7) can be arbitrarily close to O(n -1 ) for large α and small ρ. Result (1.7) for direct ERM classifiers on ε-nets is proved by Tsybakov (2004a), and for some other ERM type classifiers by Tsybakov and van de Geer (2005), [START_REF] Koltchinskii | Local Rademacher complexities and oracle inequalities in risk minimization[END_REF] and [START_REF] Audibert | Classification using Gibbs estimators under complexity and margin assumptions[END_REF] (in some of these papers the rate of convergence (1.7) is obtained with an extra log-factor).

Comparison of (1.5) and (1.7) with (1.2) and (1.3) seems to confirm the conjecture that the plug-in classifiers are inferior to the ERM type ones. The main message of the present paper is to disprove this conjecture. We will show that there exist plug-in rules that converge with fast rates, and even with super-fast rates, i.e.

faster than n -1 under the margin assumption (MA). The basic idea of the proof is to use exponential inequalities for the regression estimator ηn (see Section 3 below) or the convergence results in the L ∞ norm (see Section 5), rather than the usual

Notation and definitions

In this section we introduce some notation, definitions and basic facts that will be used in the paper.

We denote by C, C 1 , C 2 , . . . positive constants whose values may differ from line to line. The symbols P and E stand for generic probability and expectation signs, and E X is the expectation w.r.t. the marginal distribution P X . We denote by B(x, r)

the closed Euclidean ball in R d centered at x ∈ R d and of radius r > 0.

For any multi-index s = (s 1 , . . . , s d ) ∈ N d and any x = (x 1 , . . . , x d ) ∈ R d , we

define |s| = d i=1 s i , s! = s 1 ! . . . s d !, x s = x s 1 1 . . . x s d d and x (x 2 1 + • • • + x 2 d ) 1/2 . Let D s denote the differential operator D s ∂ s 1 +•••+s d ∂x s 1 1 •••∂x s d d .
Let β > 0. Denote by ⌊β⌋ the maximal integer that is strictly less than β. For any x ∈ R d and any ⌊β⌋ times continuously differentiable real valued function g on R d , we denote by g x its Taylor polynomial of degree ⌊β⌋ at point x:

g x (x ′ ) |s|≤⌊β⌋ (x ′ -x) s s! D s g(x).
Let L > 0. The β, L, R d -Hölder class of functions, denoted Σ(β, L, R d ), is defined as the set of functions g : R d → R that are ⌊β⌋ times continuously differentiable and satisfy, for any x, x ′ ∈ R d , the inequality

|g(x ′ ) -g x (x ′ )| ≤ L x -x ′ β .
Fix some constants c 0 , r 0 > 0. We will say that a Lebesgue measurable set

A ⊂ R d is (c 0 , r 0 )-regular if λ A ∩ B(x, r) ≥ c 0 λ B(x, r) , ∀ 0 < r ≤ r 0 , ∀ x ∈ A, (2.1)
where λ[S] stands for the Lebesgue measure of S ⊂ R d . To illustrate this definition, consider the following example. Let d ≥ 2. Then the set

A = x = (x 1 , . . . , x d ) ∈ R d : d j=1 |x j | q ≤ 1 is (c 0 , r 0 )
-regular with some c 0 , r 0 > 0 for q ≥ 1, and there are no c 0 , r 0 > 0 such that A is (c 0 , r 0 )-regular for 0 < q < 1.

Introduce now two assumptions on the marginal distribution P X that will be used in the sequel. Definition 2.1 Fix 0 < c 0 , r 0 , µ max < ∞ and a compact C ⊂ R d . We say that the mild density assumption is satisfied if the marginal distribution P X is supported on a compact (c 0 , r 0 )-regular set A ⊆ C and has a uniformly bounded density µ w.r.t. the Lebesgue measure: µ(x) ≤ µ max , ∀ x ∈ A. Definition 2.2 Fix some constants c 0 , r 0 > 0 and 0 < µ min < µ max < ∞ and a compact C ⊂ R d . We say that the strong density assumption is satisfied if the marginal distribution P X is supported on a compact (c 0 , r 0 )-regular set A ⊆ C and has a density µ w.r.t. the Lebesgue measure bounded away from zero and infinity on A: µ min ≤ µ(x) ≤ µ max for x ∈ A, and µ(x) = 0 otherwise.

We finally recall some notions related to locally polynomial estimators. Definition 2.3 For h > 0, x ∈ R d , for an integer l ≥ 0 and a function K : R d → R + , denote by θx a polynomial on R d of degree l which minimizes

n i=1 Y i -θx (X i -x) 2 K X i -x h . (2.
2)

The locally polynomial estimator ηLP n (x) of order l, or LP(l) estimator, of the value η(x) of the regression function at point x is defined by: ηLP n (x) θx (0) if θx is the unique minimizer of (2.2) and ηLP n (x) 0 otherwise. The value h is called the bandwidth and the function K is called the kernel of the LP(l) estimator.

Let T s denote the coefficients of θx indexed by multi-index

s ∈ N d : θx (u) = |s|≤l T s u s . Introduce the vectors T T s |s|≤l , V V s |s|≤l where V s n i=1 Y i (X i -x) s K X i -x h , (2.3)
U(u) u s |s|≤l and the matrix Q Q s 1 ,s 2 |s 1 |,|s 2 |≤l where Q s 1 ,s 2 n i=1 (X i -x) s 1 +s 2 K X i -x h . (2.4)
The following result is straightforward (cf. Section 1.7 in [START_REF] Tsybakov | Introduction à l'estimation non-paramétrique[END_REF] where the case d = 1 is considered).

Proposition 2.1 If the matrix Q is positive definite, there exists a unique polynomial on R d of degree l minimizing (2.2). Its vector of coefficients is given by

T = Q -1
V and the corresponding LP(l) regression function estimator has the form

ηLP n (x) = U T (0)Q -1 V = n i=1 Y i K X i -x h U T (0)Q -1 U(X i -x).
3 Fast rates for plug-in rules: the strong density assumption

We first state a general result showing how the rates of convergence of plug-in classifiers can be deduced from exponential inequalities for the corresponding regression estimators.

In the sequel, for an estimator ηn of η, we write

P ηn (X) -η(X)| ≥ δ P ⊗n ηn (x) -η(x)| ≥ δ P X (dx), ∀ δ > 0,
i.e., we consider the probability taken with respect to the distribution of the sample (X 1 , Y 1 , . . . X n , Y n ) and the distribution of the input X.

Theorem 3.1 Let ηn be an estimator of the regression function η and P a set of probability distributions on Z such that for some constants C 1 > 0, C 2 > 0, for some positive sequence a n , for n ≥ 1 and any δ > 0, and for almost all x w.r.t. P X , we have sup

P ∈P P ⊗n ηn (x) -η(x)| ≥ δ ≤ C 1 exp -C 2 a n δ 2 . (3.1)
Consider the plug-in classifier fn = 1I {ηn≥ 1 2 } . If all the distributions P ∈ P satisfy the margin assumption (MA), we have

sup P ∈P ER( fn ) -R(f * ) ≤ Ca -1+α 2 n
for n ≥ 1 with some constant C > 0 depending only on α, C 0 , C 1 and C 2 .

Proof. Consider the sets

A j ⊂ R d , j = 1, 2, . . . , defined as A 0 x ∈ R d : 0 < |η(x) -1 2 | ≤ δ , A j x ∈ R d : 2 j-1 δ < |η(x) -1 2 | ≤ 2 j δ , for j ≥ 1.
For any δ > 0, we may write

ER( fn ) -R(f * ) = E |2η(X) -1|1I { fn(X) =f * (X)} = ∞ j=0 E |2η(X) -1|1I { fn(X) =f * (X)} 1I {X∈A j } ≤ 2δP X 0 < |η(X) -1 2 | ≤ δ + j≥1 E |2η(X) -1|1I { fn(X) =f * (X)} 1I {X∈A j } . (3.2) On the event { fn = f * } we have |η -1 2 | ≤ |η n -η|. So, for any j ≥ 1, we get E |2η(X) -1|1I { fn(X) =f * (X)} 1I {X∈A j } ≤ 2 j+1 δ E 1I {|ηn(X)-η(X)|≥2 j-1 δ} 1I {0<|η(X)-1 2 |≤2 j δ} ≤ 2 j+1 δ E X P ⊗n |η n (X) -η(X)| ≥ 2 j-1 δ 1I {0<|η(X)-1 2 |≤2 j δ} ≤ C 1 2 j+1 δ exp -C 2 a n (2 j-1 δ) 2 P X 0 < |η(X) -1 2 | ≤ 2 j δ ≤ 2C 1 C 0 2 j(1+α) δ 1+α exp -C 2 a n (2 j-1 δ) 2
where in the last inequality we used Assumption (MA). Now, from inequality (3.2), taking δ = a -1/2 n and using Assumption (MA) to bound the first term of the right hand side of (3.2), we get

ER( fn ) -R(f * ) ≤ 2C 0 a -1+α 2 n + Ca -1+α 2 n j≥2 2 j(1+α) exp -C 2 2 2j-2 ≤ Ca -1+α 2 n
. Inequality (3.1) is crucial to obtain the above result. This inequality holds true for various types of estimators and various sets of probability distributions P. Here we focus on a standard case where η belongs to the Hölder class Σ(β, L, R d ) and the marginal law of X satisfies the strong density assumption. We are going to show that in this case there exist estimators satisfying inequality (3.1) with a n = n 2β 2β+d . These can be, for example, locally polynomial estimators. Specifically, assume from now on that K is a kernel satisfying

∃c > 0 : K(x) ≥ c1I { x ≤c} , ∀x ∈ R d , (3.3)
R d K(u)du = 1, (3.4)
R d 1 + u 4β K 2 (u)du < ∞, (3.5)
sup

u∈R d 1 + u 2β K(u) < ∞. (3.6)
Let h > 0, and consider the matrix B Bs 1 ,s 2 |s 1 |,|s 2 |≤⌊β⌋ where Bs

1 ,s 2 = 1 nh d n i=1 X i -x h s 1 +s 2 K X i -x
P ⊗n η * n (x) -η(x) ≥ δ ≤ C 1 exp -C 2 nh d δ 2 (3.7)
for almost all x w.r.t. P X . As a consequence, there exist C 1 , C 2 > 0 such that for h = n -1 2β+d and any δ > 0, n ≥ 1 we have sup

P ∈P P ⊗n η * n (x) -η(x) ≥ δ ≤ C 1 exp -C 2 n 2β 2β+d δ 2 (3.8)
for almost all x w.r.t. P X . The constants C 1 , C 2 , C 3 depend only on β, d, L, c 0 , r 0 , µ min , µ max , and on the kernel K.

Proof. See Section 6.1.

Remark 3.1 We have chosen here the LP estimators of η because for them the exponential inequality (3.1) holds without additional smoothness conditions on the marginal density of X. For other popular regression estimators, such as kernel or orthogonal series ones, similar inequality can be also proved if we assume that the marginal density of X is as smooth as the regression function. with bandwidth h = n -1 2β+d satisfies sup

P ∈P Σ ER( f * n ) -R(f * ) ≤ Cn -β(1+α) 2β+d
where the constant C > 0 depends only on α, C 0 , C 1 and C 2 .

For αβ > d/2 the convergence rate n -β(1+α) 2β+d obtained in Theorem 3.3 is a fast rate, i.e., it is faster than n -1/2 . Furthermore, it is a super-fast rate (i.e., is faster than n -1 ) for (α -1)β > d. We must note that if this condition is satisfied, the class P Σ is rather poor, and thus super-fast rates can occur only for very particular joint distributions of (X, Y ). Intuitively, this is clear. Indeed, to have a very smooth regression function η (i.e., very large β) implies that when η hits the level 1/2, it cannot "take off" from this level too abruptly. As a consequence, when the density of the distribution P X is bounded away from 0 at a vicinity of the hitting point, the margin assumption cannot be satisfied for large α since this assumption puts an upper bound on the "time spent" by the regression function near 1/2. So, α and β cannot be simultaneously very large. It can be shown that the cases of "too large" and "not too large" (α, β) are essentially described by the condition (α -1)β > d.

To be more precise, observe first that P Σ is not empty for (α -1)β > d, so that the super-fast rates can effectively occur. Examples of laws P ∈ P Σ under this condition can be easily given, such as the one with P X equal to the uniform distribution on a ball centered at 0 in R d , and the regression function defined by To explain this and to have further insight into the problem of super-fast rates, consider the following two questions:

η(x) = 1/2 -C
• for which parameters α, β and d is there a distribution P ∈ P Σ such that the regression function associated with P hits 1 1/2 in the support of P X ?

• for which parameters α, β and d is there a distribution P ∈ P Σ such that the regression function associated with P crosses 2 1/2 in the interior of the support of P X ?

The following result gives a precise description of the constraints on (α, β) leading to possibility or impossibility of the super-fast rates.

Proposition 3.4

• If α(1∧β) > d, there is no distribution P ∈ P Σ such that the regression function η associated with P hits 1/2 in the interior of the support of P X .

• For any α, β > 0 and integer d ≥ α(1 ∧ β), any positive parameter L and any compact C ⊂ R d with non-empty interior, for appropriate positive parameters

1 A function f : R d → R is said to hit the level a ∈ R at x 0 ∈ R d if and only if f (x 0 ) = a and
for any r > 0 there exists x ∈ B(x 0 , r) such that f (x) = a .

2 A function f : R d → R is said to cross the level a ∈ R at x 0 ∈ R d if and only if for any r > 0, there exists x -and x + in B(x 0 , r) such that f (x -) < a and f (x + ) > a.

C 0 , c 0 , r 0 , µ max > µ min > 0, there are distributions P ∈ P Σ such that the regression function η associated with P hits 1/2 in the boundary of the support of P X .

• For any α, β > 0, any integer d ≥ 2α, any positive parameter L and any compact C ⊂ R d with non-empty interior, for appropriate positive parameters C 0 , c 0 , r 0 , µ max > µ min > 0, there are distributions P ∈ P Σ such that the regression function η associated with P hits 1/2 in the interior of the support of P X .

• If α(1 ∧ β) > 1 there is no distribution P ∈ P Σ such that the regression function η associated with P crosses 1/2 in the interior of the support of P X .

Conversely, for any α, β > 0 such that α(1∧β) ≤ 1, any integer d, any positive parameter L and any compact C ⊂ R d with non-empty interior, for appropriate positive parameters C 0 , c 0 , r 0 , µ max > µ min > 0, there are distributions P ∈ P Σ such that the regression function η associated with P crosses 1/2 in the interior of the support of P X .

Note that the condition α(1 ∧ β) > 1 appearing in the last assertion is equivalent

to β(1+α) 2β+d > (2β)∨(β+1) 2β+d
, which is necessary to have super-fast rates. As a consequence, in this context, super-fast rates cannot occur when the regression function crosses 1/2 in the interior of the support. The third assertion of the proposition shows that super-fast rates can occur with regression functions hitting 1/2 in the interior of the support of P X provided that the regression function is highly smooth and defined on a highly dimensional space and that a strong margin assumption holds (i.e. α large).

Proof. See Section 6.3.

The following lower bound shows optimality of the rate of convergence for the Hölder classes obtained in Theorem 3.3.

Theorem 3.5 Let d ≥ 1 be an integer, and let L, β, α be positive constants, such that αβ ≤ d. Then there exists a constant C > 0 such that for any n ≥ 1 and any classifier fn : Z n → F , we have sup

P ∈P Σ ER( fn ) -R(f * ) ≥ Cn -β(1+α) 2β+d .
Proof. See Section 6.2.

Note that the lower bound of Theorem 3.5 does not cover the case of super-fast rates ((α -1)β > d).

Finally, we discuss the case where "α = ∞", which means that there exists t 0 > 0 such that

P X 0 < |η(X) -1/2| ≤ t 0 = 0. (3.9)
This is a very favorable situation for classification. The rates of convergence of the ERM type classifiers under (3.9) are, of course, faster than under Assumption (MA) with α < ∞ [cf. [START_REF] Massart | Risk bounds for statistical learning[END_REF]], but they are not faster than n -1 .

Indeed, [START_REF] Massart | Risk bounds for statistical learning[END_REF] provide a lower bound showing that, even if Assumption (CAD) is replaced by a very strong assumption that the true decision set belongs to a VC-class (note that both assumptions are naturally linked to the study the ERM type classifiers), the best achievable rate is of the order (log n)/n. We show now that for the plug-in classifiers much faster rates can be attained. Specifically, if the regression function η has some (arbitrarily low) Hölder smoothness β the rate of convergence can be exponential in n. To show this, we first state a simple lemma which is valid for any plug-in classifier fn .

Lemma 3.6 Let assumption (3.9) be satisfied, and let ηn be an estimator of the regression function η. Then for the plug-in classifier fn = 1I {ηn≥ 1 2 } we have

ER( fn ) -R(f * ) ≤ P |η n (X) -η(X)| > t 0 .
Proof. Following the argument similar to the proof of Theorem 3.1 and using condition (3.9) we get

ER( fn ) -R(f * ) ≤ 2t 0 P X 0 < |η(X) -1/2| ≤ t 0 + E |2η(X) -1|1I { fn(X) =f * (X)} 1I {|η(X)-1/2|>t 0 } = E |2η(X) -1|1I { fn(X) =f * (X)} 1I {|η(X)-1/2|>t 0 } ≤ P |η n (X) -η(X)| > t 0 .
Lemma 3.6 and Theorem 3.2 immediately imply that, under assumption (3.9), the rate of convergence of the plug-in classifier f

* n = 1I {η * n ≥ 1
2 } with a small enough fixed (independent of n) bandwidth h is exponential. To state the result, we denote by P Σ,∞ the class of probability distributions P defined in the same way as P Σ , with the only difference that in Definition 3.1 the margin assumption (MA) is replaced by condition (3.9). Proposition 3.7 There exists a fixed (independent of n) h > 0 such that for any n ≥ 1 the excess risk of the plug-in classifier

f * n = 1I {η * n ≥ 1 2 } with bandwidth h satisfies sup P ∈P Σ,∞ ER( f * n ) -R(f * ) ≤ C 4 exp(-C 5 n)
where the constants C 4 , C 5 > 0 depend only on t 0 , β, d, L, c 0 , r 0 , µ min , µ max , and on the kernel K.

Proof. Use Lemma 3.6, choose h > 0 such that h < min(r 0 /c, (t 0 /C 3 ) 1/β ), and apply (3.7) with δ = t 0 .

Koltchinskii and Beznosova (2005) prove a result on exponential rates for the plug-in classifier with some penalized regression estimator in place of the locally polynomial one that we use here. Their result is stated under a less general condition, in the sense that they consider only the Lipschitz class of regression functions η, while in Proposition 3.7 the Hölder smoothness β can be arbitrarily close to 0. Note also that we do not impose any complexity assumption on the decision set. However, the class of distributions P Σ,∞ is quite restricted in a different sense. Indeed, for such distributions condition (3.9) should be compatible with the assumption that η belongs to a Hölder class. A sufficient condition for that is the existence of a band or a "corridor" of zero P X -measure separating the sets {x : η(x) > 1/2} and {x : η(x) < 1/2}. We believe that this condition is close to the necessary one.

Optimal learning rates without the strong density assumption

In this section we show that if P X does not admit a density bounded away from zero on its support the rates of classification are slower than those obtained in Section 3. In particular, super-fast rates, i.e., the rates faster than n -1 , cannot be achieved.

Introduce the following class of probability distributions. (iii) the mild density assumption on P X is satisfied.

In this section we mainly assume that the distribution P of (X, Y ) belongs to P ′ Σ , but we also consider larger classes of distributions satisfying the margin assumption (MA) and the complexity assumption (CAR).

Clearly, P Σ ⊂ P ′ Σ . The only difference between P ′ Σ and P Σ is that for P ′ Σ the marginal density of X is not bounded away from zero. The optimal rates for P ′ Σ are slower than for P Σ . Indeed, we have the following lower bound for the excess risk.

Theorem 4.1 Let d ≥ 1 be an integer, and let L, β, α be positive constants. Then there exists a constant C > 0 such that for any n ≥ 1 and any classifier fn : Z n → F we have sup

P ∈P ′ Σ ER( fn ) -R(f * ) ≥ Cn -(1+α)β (2+α)β+d .
Proof. See Section 6.2.

In particular, when α = d/β, we get slow convergence rate 1/ √ n, instead of the fast rate n -β+d 2β+d obtained in Theorem 3.3 under the strong density assumption. Nevertheless, the lower bound can still approach n -1 , as the margin parameter α tends to ∞.

We now show that the rate of convergence given in Theorem 4.1 is optimal in the sense that there exist estimators that achieve this rate. This will be obtained as a consequence of a general upper bound for the excess risk of classifiers over a larger set P of distributions than P ′ Σ . Fix a Lebesgue measurable set C ⊂ R d and a value 1 ≤ p ≤ ∞. Let Σ be a class of regression functions η on R d such that Assumption (CAR) is satisfied where the ε-entropy is taken w.r.t. the L p (C, λ) norm (λ is the Lebesgue measure on R d ).

Then for every ε > 0 there exists an ε-net N ε on Σ w.r.t. this norm such that

log card N ε ≤ A ′ ε -ρ , where A ′ is a constant. Consider the empirical risk R n (f ) = 1 n n i=1 1I {f (X i ) =Y i } , f ∈ F ,
and set

ε n = ε n (α, ρ, p) n -1 2+α+ρ if p = ∞, n - p+α (2+α)p+ρ(p+α) if 1 ≤ p < ∞.
Define a sieve estimator ηS n of the regression function η by the relation

ηS n ∈ Argmin η∈Nε n R n (f η) (4.1)
where f η(x) = 1I {η(x)≥1/2} , and consider the classifier f S n = 1I {η S n ≥1/2} . Note that f S n can be viewed as a "hybrid" plug-in/ ERM procedure: the ERM is performed on a set of plug-in rules corresponding to a grid on the class of regression functions η.

sup P ∈P ER( f S n ) -R(f * ) ≤ Cn -1+α 2+α+ρ . (4.2)
If 1 ≤ p < ∞ and, in addition, for all P ∈ P the marginal distributions P X are absolutely continuous w.r.t. the Lebesgue measure and their densities are uniformly bounded from above by some constant µ max < ∞, then for any n ≥ 1 we have

sup P ∈P ER( f S n ) -R(f * ) ≤ Cn -(1+α)p (2+α)p+ρ(p+α) . (4.3)
Proof. See Section 6.4.

Theorem 4.2 allows one to get fast classification rates without any density assumption on P X . Namely, define the following class of distributions P of (X, Y ).

Definition 4.2 For fixed parameters α ≥ 0, C 0 > 0, β > 0, L > 0, and for a fixed compact C ⊂ R d , let P 0 Σ denote the class of all probability distributions P on Z such that Lemma 5.1 For any distribution P of (X, Y ) satisfying Assumption (MA) we have

R( f ) -R(f * ) ≤ 2C 0 η -η 1+α ∞ , (5.1)
and

P X f (X) = f * (X), η(X) = 1/2 ≤ C 0 η -η α ∞ . (5.2)
Proof. To show (5.1) note that

R( f ) -R(f * ) = E |2η(X) -1|1I { f (X) =f * (X)} ≤ 2E |η(X) -1 2 |1I 0<{|η(X)-1 2 |≤|η(X)-η(X)|} ≤ 2 η -η ∞ P X 0 < |η(X) -1 2 | ≤ η -η ∞ ≤ 2C 0 η -η 1+α ∞ .
Similarly,

P X f (X) = f * (X), η(X) = 1/2 ≤ P X 0 < |η(X) -1 2 | ≤ |η(X) -η(X)| ≤ P X 0 < |η(X) -1 2 | ≤ η -η ∞ ≤ C 0 η -η α ∞ .
Remark 5.1 Lemma 5.1 offers an easy way to obtain the result of Theorem 3.3 in a slightly less precise form, with an extra logarithmic factor in the rate. In fact, under the strong density assumption, there exist nonparametric estimators ηn (for instance, suitably chosen locally polynomial estimators) such that [START_REF] Stone | Optimal global rates of convergence for nonparametric regression[END_REF]]. Taking here q = 1 + α and applying the comparison inequality (5.1) we immediately get that the plug-in classifier fn = 1I {ηn≥1/2} has the excess risk E( fn ) of the order (n/ log n) -β(1+α)/(2β+d) .

E ηn -η q ∞ ≤ C log n n qβ 2β+d , ∀ q > 0, uniformly over η ∈ Σ(β, L, R d ) [see, e.g.,
Another immediate application of Lemma 5.1 is to get lower bounds on the risks of regression estimators in the L ∞ norm from the corresponding lower bounds on the excess risks of classifiers (cf. Theorems 3.5 and 4.1). But here again we loose a logarithmic factor required for the best bounds.

We now consider the comparison inequalities for L p norms with 1 ≤ p < ∞. Lemma 5.2 For any 1 ≤ p < ∞ and any distribution P of (X, Y ) satisfying Assumption (MA) with α > 0 we have

R( f ) -R(f * ) ≤ C 1 (α, p) η -η p(1+α) p+α p , (5.3)
and

P X f (X) = f * (X), η(X) = 1/2 ≤ C 2 (α, p) η -η p p+α p , (5.4)
where

C 1 (α, p) = 2(α + p)p -1 p α α α+p C p-1 α+p 0 , C 2 (α, p) = (α + p)p -1 p α α α+p C p α+p 0 . In particular, R( f ) -R(f * ) ≤ C 1 (α, 2) [η(x) -η(x)] 2 P X (dx) 1+α 2+α
.

(5.5)

Proof. For any t > 0 we have

R( f ) -R(f * ) = E |2η(X) -1|1I { f (X) =f * (X)} = 2E |η(X) -1/2|1I { f (X) =f * (X)} 1I {0<|η(X)-1/2|≤t} + 2E |η(X) -1/2|1I { f (X) =f * (X)} 1I {|η(X)-1/2|>t} ≤ 2E |η(X) -η(X)|1I {0<|η(X)-1/2|≤t} + 2E |η(X) -η(X)|1I {|η(X)-η(X)|>t} ≤ 2 η -η p P X (0 < |η(X) -1/2| ≤ t) p-1 p + 2 η -η p p t p-1 (5.6)
by Hölder and Markov inequalities. So, for any t > 0, introducing E ηη p and using Assumption (MA) to bound the probability in (5.6) we obtain

R( f ) -R(f * ) ≤ 2 C p-1 p 0 t α(p-1) p E + E p t p-1 .
Minimizing in t the RHS of this inequality we get (5.3). Similarly,

P X f (X) = f * (X), η(X) = 1/2 ≤ P X 0 < |η(X) -1/2| ≤ t + P X |η(X) -η(X)| > t) ≤ C 0 t α + η -η p p t p ,
and minimizing this bound in t we obtain (5.4).

If the regression function η belongs to the Hölder class Σ β, L, R d there exist estimators ηn such that, uniformly over the class, E ηn (X)η(X)

λ B = min W =1 W T BW ≥ min W =1 W T BW + min W =1 W T ( B -B)W ≥ min W =1 W T BW -|s 1 |,|s 2 |≤⌊β⌋ Bs 1 ,s 2 -B s 1 ,s 2 . (6.1) Let A n u ∈ R d : u ≤ c; x + hu ∈ A
where c is the constant appearing in (3.3). Using (3.3), for any vector W satisfying W = 1, we obtain

W T BW = R d |s|≤⌊β⌋ W s u s 2 K(u)µ(x + hu)du ≥ cµ min An |s|≤⌊β⌋ W s u s 2 du.
By assumption of the theorem, ch ≤ r 0 . Since the support of the marginal distribution is (c 0 , r 0 )-regular we get By the compactness argument, the minimum in (6.2) exists and is strictly positive.

λ[A n ] ≥ h -d λ B(x, ch) ∩ A ≥ c 0 h -d λ B(x, ch) ≥ c 0 v d c d ,
For i = 1, . . . , n and any multi-indices

s 1 , s 2 such that |s 1 |, |s 2 | ≤ ⌊β⌋, define T i 1 h d X i -x h s 1 +s 2 K X i -x h -R d u s 1 +s 2 K(u)µ(x + hu)du.
We have

ET i = 0, |T i | ≤ h -d sup u∈R d 1 + u 2β K(u) κ 1 h -d
and the following bound for the variance of T i :

Var T i ≤ 1 h 2d E X i -x h 2s 1 +2s 2 K 2 X i -x h = 1 h d R d u 2s 1 +2s 2 K 2 (u)µ(x + hu)du ≤ µmax h d R d 1 + u 4β K 2 (u)du κ 2 h d .
From Bernstein's inequality, we get

P ⊗n | Bs 1 ,s 2 -B s 1 ,s 2 | > ǫ = P ⊗n 1 n n i=1 T i > ǫ ≤ 2 exp -nh d ǫ 2 2κ 2 +2κ 1 ǫ/3 .
This and (6.1) -(6.2) imply that

P ⊗n (λ B ≤ µ 0 ) ≤ 2M 2 exp -Cnh d (6.3)
where M 2 is the number of elements of the matrix B. Assume in what follows that

n is large enough, so that µ 0 > (log n) -1 . Then for λ B > µ 0 we have |η * n (x) -η(x)| ≤ |η LP n (x) -η(x)|. Therefore, P ⊗n η * n (x) -η(x) ≥ δ ≤ P ⊗n λ B ≤ µ 0 + P ⊗n ηLP n (x) -η(x) ≥ δ, λ B > µ 0 . (6.4)
We now evaluate the second probability on the right hand side of (6.4). For λ B > µ 0

we have ηLP

n (x) = U T (0)Q -1 V where V is given by (2.3) . Introduce the matrix Z Z i,s 1≤i≤n,|s|≤⌊β⌋ with elements Z i,s (X i -x) s K X i -x h .
The s-th column of Z is denoted by Z s , and we introduce

Z (η) |s|≤⌊β⌋ η (s) (x) s! Z s . Since Q = Z T Z, we get ∀|s| ≤ ⌊β⌋ : U T (0)Q -1 Z T Z s = 1I {s=(0,...,0)} , hence U T (0)Q -1 Z T Z (η) = η(x). So we can write ηLP n (x) -η(x) = U T (0)Q -1 (V -Z T Z (η) ) = U T (0) B-1 a where a 1 nh d H(V -Z T Z (η) ) ∈ R M and H is a diagonal matrix H H s 1 ,s 2 |s 1 |,|s 2 |≤⌊β⌋ with H s 1 ,s 2 h -s 1 1I {s 1 =s 2 } . For λ B > µ 0 we get ηLP n (x) -η(x) ≤ B-1 a ≤ λ -1 B a ≤ µ -1 0 a ≤ µ -1 0 M max s |a s |, (6.5)
where a s are the components of the vector a given by

a s = 1 nh d n i=1 Y i -η x (X i ) X i -x h s K X i -x h . Define T (s,1) i 1 h d Y i -η(X i ) X i -x h s K X i -x h , T (s,2) i 1 h d η(X i ) -η x (X i ) X i -x h s K X i -x h .
We have

|a s | ≤ 1 n n i=1 T (s,1) i + 1 n n i=1 T (s,2) i -ET (s,2) i + ET (s,2) i . (6.6)
Note that ET

(s,1) i = 0, T (s,1) i ≤ κ 1 h -d , and
Var T (s,1) i ≤ 4 -1 h -d u 2s K 2 (u)µ(x + hu)du ≤ (κ 2 /4)h -d , T (s,2) i -ET (s,2) i ≤ Lκ 1 h β-d + Lκ 2 h β ≤ Ch β-d , Var T (s,2) i ≤ h -d L 2 h 2β u 2s+2β K 2 (u)µ(x + hu)du ≤ L 2 κ 2 h 2β-d .
From Bernstein's inequality, for any ǫ 1 , ǫ 2 > 0, we obtain

P ⊗n 1 n n i=1 T (s,1) i ≥ ǫ 1 ≤ 2 exp - nh d ǫ 2 1 κ 2 /2+2κ 1 ǫ 1 /3
and

P ⊗n 1 n n i=1 T (s,2) i -ET (s,2) i ≥ ǫ 2 ≤ 2 exp - nh d ǫ 2 2 2L 2 κ 2 h 2β +2Ch β ǫ 2 /3 .
Since also

ET (s,2) i ≤ Lh β u s+β K 2 (u)µ(x + hu)du ≤ Lκ 2 h β
we get, using (6.6), that if 3µ -1 0 MLκ 2 h β ≤ δ ≤ 1 the following inequality holds

P ⊗n |a s | ≥ µ 0 δ M ≤ P ⊗n 1 n n i=1 T (s,1) i > µ 0 δ 3M + P ⊗n 1 n n i=1 T (s,2) i -ET (s,2) i > µ 0 δ 3M ≤ 4 exp -Cnh d δ 2 .
Combining this inequality with (6.3), (6.4) and (6.5), we obtain

P ⊗n η * n (x) -η(x) ≥ δ ≤ C 1 exp -C 2 nh d δ 2 (6.7)
for 3m -1 MLκ 2 h β ≤ δ (for δ > 1 inequality (6.7) is obvious since η * n , η take values in [0, 1]). The constants C 1 , C 2 in (6.7) do not depend on the distribution P X , on its support A and on the point x ∈ A, so that we get (3.7). Now, (3.7) implies (3.8) for Cn -β 2β+d ≤ δ, and thus for all δ > 0 (with possibly modified constants C 1 and C 2 ).

6.2 Proof of Theorems 3.5 and 4.1

The proof of both theorems is based on Assouad's lemma [see, e.g., [START_REF] Korostelev | Minimax Theory of Image Reconstruction[END_REF], Chapter 2 or Tsybakov (2004b), Chapter 2]. We apply it in a form adapted for the classification problem (Lemma 5.1 in Audibert ( 2004)).

For an integer q ≥ 1 we consider the regular grid on R d defined as

G q 2k 1 + 1 2q , . . . , 2k d + 1 2q : k i ∈ {0, . . . , q -1}, i = 1, . . . , d .
Let n q (x) ∈ G q be the closest point to x ∈ R d among points in G q (we assume uniqueness of n q (x): if there exist several points in G q closest to x we define n q (x) as the one which is closest to 0). Consider the partition X ′ 1 , . . . , X ′ q d of [0, 1] d canonically defined using the grid G q (x and y belong to the same subset if and only if n q (x) = n q (y)). Fix an integer m ≤ q d . For any i ∈ {1, . . . , m}, we define X i X ′ i and X 0 R d \ ∪ m i=1 X i , so that X 0 , . . . , X m form a partition of R d . Let u : R + → R + be a nonincreasing infinitely differentiable function such that u = 1 on [0, 1/4] and u = 0 on [1/2, ∞). One can take, for example, u(x)

= 1/2 1/4 u 1 (t)dt -1 ∞
x u 1 (t)dt where the infinitely differentiable function u 1 is defined as

u 1 (x) =    exp - 1 (1/2-x)(x-1/4) for x ∈ (1/4, 1/2), 0 otherwise.
Let φ : R d → R + be the function defined as

φ(x) C φ u( x ),
where the positive constant C φ is taken small enough so ensure that |φ(x ′ )-φ x (x ′ )| ≤ L x ′x β for any x, x ′ ∈ R d . Thus, φ ∈ Σ(β, L, R d ).

Define the hypercube H = P σ : σ = (σ 1 , . . . , σ m ) ∈ {-1, 1} m of probability distributions P σ of (X, Y ) on Z = R d × {0, 1} as follows.

For any P σ ∈ H the marginal distribution of X does not depend on σ, and has a density µ w.r.t. the Lebesgue measure on R d defined in the following way. Fix 0 < w ≤ m -1 and a set A 0 of positive Lebesgue measure included in X 0 (the particular choices of A 0 will be indicated later), and take:

(i) µ(x) = w/λ[B(0, (4q) -1 )] if x belongs to a ball B(z, (4q) -1 ) for some z ∈ G d , (ii) µ(x) = (1 -mw)/λ[A 0 ] for x ∈ A 0 , (iii) µ(x) = 0 for all other x.
Next, the distribution of Y given X for P σ ∈ H is determined by the regression function η σ (x) = P (Y = 1|X = x) that we define as η σ (x) = 1+σ j ϕ(x) 2

for any x ∈ X j , j = 1, . . . , m, and η σ ≡ 1/2 on X 0 , where ϕ(x) q -β φ q[x-n q (x)] . We will assume that C φ ≤ 1 to ensure that ϕ and η σ take values in [0, 1].

For any s ∈ N d such that |s| ≤ ⌊β⌋, the partial derivative D s ϕ exists, and D s ϕ(x) = q |s|-β D s φ q[xn q (x)] . Therefore, for any i ∈ {1, . . . , m} and any

x, x ′ ∈ X i , we have

|ϕ(x ′ ) -ϕ x (x ′ )| ≤ L x -x ′ β .
This implies that for any σ ∈ {-1, 1} m the function η σ belongs to the Hölder class Σ β, L, R d .

We now check the margin assumption. Set x 0 = 1 2q , . . . , 1 2q . For any σ ∈ {-1, 1} m we have

P σ 0 < η σ (X) -1/2 ≤ t = mP σ 0 < φ[q(X -x 0 )] ≤ 2tq β = m B(x 0 ,(4q) -1 ) 1I {0<φ[q(x-x 0 )]≤2tq β } w λ[B(0,(4q) -1 )] dx = mw λ[B(0,1/4)] B(0,1/4) 1I {φ(x)≤2tq β } dx = mw1I {t≥C φ /(2q β )} .
Therefore, the margin assumption (MA) is satisfied if mw = O(q -αβ ).

According to Lemma 5.1 in [START_REF] Audibert | Classification using Gibbs estimators under complexity and margin assumptions[END_REF], for any classifier fn we have sup

P ∈H ER( fn ) -R(f * ) ≥ mwb ′ (1 -b √ nw)/2 (6.8) where b 1 -X 1 1 -ϕ 2 (x) µ 1 (x)dx 2 1/2 = C φ q -β , b ′ X 1 ϕ(x)µ 1 (x)dx = C φ q -β with µ 1 (x) = µ(x)/ X 1 µ(z)dz.
We now prove Theorem 3.5. Take q = Cn 1 2β+d , w = C ′ q -d and m = C ′′ q d-αβ with some positive constants C, C ′ , C ′′ to be chosen, and set A 0 = [0, 1] d \ ∪ m i=1 X i . The condition αβ ≤ d ensures that the above choice of m is not degenerate: we have m ≥ 1 for C ′′ large enough. We now prove that H ⊂ P Σ under the appropriate choice of C, C ′ , C ′′ . In fact, select these constants so that the triplet (q, w, m) meets the conditions m ≤ q d , 0 < w ≤ m -1 , mw = O(q -αβ ). Then, in view of the argument preceding (6.8), for any σ ∈ {-1, 1} m the regression function η σ belongs to Σ β, L, R d and Assumption (MA) is satisfied. We now check that P X obeys the strong density assumption. First, the density µ(x) equals to a positive constant for x belonging to the union of balls ∪ m i=1 B(z i , (4q) -1 ) where z i is the center of X i , and µ(x) = (1mw)/(1mq -d ) = 1 + o(1), as n → ∞, for x ∈ A 0 . Thus, µ min ≤ µ(x) ≤ µ max for some positive µ min and µ max . (Note that this construction does not allow to choose any prescribed values of µ min and µ max , because µ(x) = 1 + o(1).

The problem can be fixed via a straightforward but cumbersome modification of the definition of A 0 that we skip here.) Second, the (c 0 , r 0 )-regularity of the support A of P X with some c 0 > 0 and r 0 > 0 follows from the fact that, by construction, r)) for all x ∈ A and r > 0 (here again we skip the obvious generalization allowing to get any prescribed c 0 > 0). Thus, the strong density assumption is satisfied, and we conclude that H ⊂ P Σ . Theorem 3.5 now follows from (6.8) if we choose C ′ small enough.

λ(A ∩ B(x, r)) = (1 + o(1))λ([0, 1] d ∩ B(x,
Finally, we prove Theorem 4.1. Take q = Cn 1 (2+α)β+d , w = C ′ q 2β /n and m = q d for some constants C > 0, C ′ > 0, and choose A 0 as a Euclidean ball contained in X 0 . As in the proof of Theorem 3.5, under the appropriate choice of C and C ′ , the regression function η σ belongs to Σ β, L, R d and the margin assumption (MA) is satisfied. Moreover, it is easy to see that the marginal distribution of X obeys the mild density assumption (the (c 0 , r 0 )-regularity of the support of P X follows from considerations analogous to those in the proof of Theorem 3.5). Thus, H ⊂ P ′ Σ . Choosing C ′ small enough and using (6.8) we obtain Theorem 4.1.

Proof of Proposition 3.4

The following lemma describes how the smoothness constraint on the regression function η at some point x ∈ R d implies that η "stays close" to η(x) in the vicinity of x. Lemma 6.1 For any distribution P ∈ P Σ with regression function η and for any κ > 0, there exist L ′ > 0 and t 0 > 0 such that for any x in the support of P X and 0 < t ≤ t 0 , we have

P X η(X) -η(x) ≤ t; X ∈ B x, κt 1 1∧β ≥ L ′ t d 1∧β .
Proof of Lemma 6.1. Let A denote the support of P X . Let us first consider the case β ≤ 1. Then for any

x, x ′ ∈ R d , we have η(x ′ ) -η(x) ≤ L x ′ -x β . Let κ ′ = κ ∧ L -1/β . For any 0 < t ≤ Lr β 0 , we get P X η(X) -η(x) ≤ t; X ∈ B x, κt 1 1∧β = P X η(X) -η(x) ≤ t; X ∈ B x, κt 1 β ∩ A ≥ P X X ∈ B x, κt 1 β ∧ t L 1 β ∩ A ≥ µ min λ B x, κ ′ t 1 β ∩ A ≥ c 0 µ min λ B x, κ ′ t 1 β ≥ c 0 µ min v d (κ ′ ) d t d β ,
which is the desired result with L ′ ≤ c 0 µ min v d (κ ′ ) d and t 0 ≤ Lr β 0 . For the case β > 1, by assumption, η is continuously differentiable. Let C(A) be the convex hull of the support A of P X . By compactness of C(A), there exists C > 0 such that for any s ∈ N

d with |s| = 1, sup x∈C(A) D s η(x) ≤ C.

So we have for any x, x

′ ∈ A, |η(x) -η(x ′ )| ≤ C x -x ′ .
The rest of the proof is then similar to the one of the first case.

• We will now prove the first item of Proposition 3.4. Let P ∈ P Σ such that the regression function associated with P hits 1/2 at x 0 ∈ • A, where • A denotes the interior of the support of P X . Let r > 0 such that B(x 0 , r) ⊂ A. Let x ∈ B(x 0 , r) such that η(x) = 1 2 . Let t 1 = η(x) -1/2 . For any 0 < t ≤ t 1 , let x t ∈ [x 0 ; x] such that η(x t ) -1/2 = t/2. We have x t ∈ A so that we can apply Lemma 6.1 (with κ = 1 for instance) and obtain for any 0 < t ≤ t 1 ∧ (4t 0 )

P X 0 < η(X) -1/2 ≤ t ≥ P X η(X) -η(x t ) ≤ t/4 ≥ L ′ (t/4) d 1∧β .
Now from the margin assumption, we get that for any small enough t > 0

C 0 t α ≥ L ′ (t/4) d 1∧β , hence α ≤ d 1∧β .
• For the second item of Proposition 3.4, to skip cumbersome details, we may assume that C contains the unit ball in R d . Consider the distribution such that -P X is the uniform measure on (x 1 , . .

. , x d ) ∈ R d : |x 1 -1/4| + |x 2 | + • • • + |x d | ≤ 1/4
the regression function associated with P is

η(x 1 , . . . , x d ) = 1 + C η sign(x 1 )|x 1 | β∧1 u(x 1 ) 2 ,
where

u(t) = exp -1 1-t 2 if |t| < 1 0 otherwise, and 0 < C η ≤ 1 is small enough so that for any x, x ′ ∈ R d , η satisfies |η(x ′ ) -η x (x ′ )| ≤ L x -x ′ β .
For appropriate positive parameters c 0 , r 0 , µ max > µ min > 0, the only nontrivial task in checking that P belongs to P Σ is to check the margin assumption.

For t small enough, we have

P X η(X)-1/2 t ≤ P X |X 1 | β∧1 ≤ Ct; |X 1 -1/4|+|X 2 |+• • •+|X d | ≤ 1/4
for some C > 0. Therefore, we have

P X 0 < η(X) -1/2 ≤ t ≤ Ct d β∧1
. So the margin assumption is satisfied for an appropriate C 0 whenever α ≤ d β∧1 . Since η hits 1/2 at 0 R d which is in boundary of the support of P X , we have proved the second assertion.

• For the third assertion of Proposition 3.4, to avoid cumbersome details again, we may assume that C contains the unit ball in R d . Consider the distribution such that -P X is the uniform measure on the unit ball, -the regression function associated with P is

η(x) = 1 + C η x 2 u( x 2 /2) 2 ,
where 0 < C η ≤ 1 is small enough so that for any Let r 1 > 0 such that B(x 0 , 3r 1 ) ⊂ A. Introduce x -and x + in B(x 0 , r 1 ) such that η(x -) < 1/2 and η(x Since η is continuous, there exists r 2 > 0 such that

x, x ′ ∈ R d , η satisfies |η(x ′ ) -η x (x ′ )| ≤ L x -x ′ β . 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
+ ) > 1/2. Let t 1 = 1/2 -η(x -) ∧ η(x + ) -1/2 . Define y = x -+x + 2 , e d = x + -x - x + -x -and D = x + -x -. Let
η(x) < 1/2 -t 1 /2 for any x ∈ B * (x -, r 2 ) η(x) > 1/2 + t 1 /2 for any x ∈ B * (x + , r 2 ) Let ζ = 1 β∧1 . For any k = (k 1 , . . . , k d-1 ) ∈ Z d-1 , introduce y k = y + t ζ d-1 i=1 k i e i .
For any t in ]0; t 1 [, consider the grid

G = y k ; k ∈ Z d-1 , max 1≤i≤d-1 |k i | ≤ D 2 √ d-1t ζ . For any y k in G, we have y k -y ≤ √ d -1 max 1≤i≤d-1 |t ζ k i | ≤ D/2 ≤ r 1 .
Therefore, using that y ∈ B(x 0 , r 1 ), the grid G is included in B(x 0 , 2r 1 D t ζ away from each other. The distance between w k and w k ′ is not less than the distance between the paths γ k and γ k ′ . Let U such that for any 0 < t < 4t 0 ∧ t 1 , C 0 t α ≥ P X 0 < η(X) -1 2 ≤ t ≥ where 0 < C η ≤ 1 is small enough so that for any x, x ′ ∈ R d , η satisfies

|η(x ′ ) -η x (x ′ )| ≤ L x -x ′ β .
For small enough t > 0, we have

P X η(X) -1/2 ≤ t ≤ P X |X 1 | β∧1 ≤ Ct ,
for some constant C > 0, so that we have P X 0 < η(X) -1 2 ≤ t ≤ 2(Ct) 1 β∧1 . As a consequence, for appropriate parameters C 0 , c 0 , r 0 , µ max > µ min > 0, the distribution P belongs to P Σ whenever α ≤ 1 β∧1 . Since η crosses 1/2 at 0 R d which is in the interior of the support of P X , the converse holds.

Proof of Theorem 4.2

We prove the theorem for p < ∞. The proof for p = ∞ is analogous. For any decision rule f we set d(f ) R(f ) -R(f * ) and

f * * (x, f ) f * (x) if η(x) = 1/2, f (x) if η(x) = 1/2, ∀ x ∈ R d .
Lemma 6.2 Under Assumption (MA) for any decision rule f we have P X (f (X) = f * * (X, f )) ≤ Cd(f ) α/(1+α) . (6.9)

Proof. Note that f * * (•, f ) is a Bayes rule, and following the same lines as in Proposition 1 of Tsybakov (2004a) we get P X (f (X) = f * * (X, f ), η(X) = 1/2) ≤ Cd(f ) α/(1+α) . It remains to observe that P X (f (X) = f * * (X, f ), η(X) = 1/2) = P X (f (X) = f * * (X, f )).

For a Borel function η on R d define f η 1I {η≥1/2} , f * η (•) f * * (•, f η) and

Z n (f η) [R n (f η) -R n (f * η )] -[R(f η) -R(f * η )] = [R n (f η) -R n (f * η )] -d(f η).
Let η n be an element of N εn such that η nη p,λ ≤ ε n , where • p,λ is the L p (C, λ) norm. In view of the assumption on P we have η nη p ≤ µ +P(Z n (f ηn ) ≥ t∆ n /4).

Note that for any decision rule f the value Z n (f ) is an average of n i.i.d. bounded and centered random variables whose variance does not exceed P X (f (X) = f * * (X, f )).

Thus, using Bernstein's inequality and (6.9) we obtain P(-Z n (f ) ≥ a) ≤ exp -Cna 2 a + d(f ) α/(1+α) , ∀ a > 0.

Therefore, for η ∈ N * n , P(Z n (f η) ≤ -d(f η)/2) ≤ exp(-Cnd(f η ) (2+α)/(1+α) )

≤ exp(-Cn(t∆ n ) (2+α)/(1+α) ).

Similarly, for t > C,

4 )

 4 , and it does not depend on ρ (respectively, on the dimension d). Note that the comparison between (1.5) and (1.3) -(1.4) is not quite legitimate, because there is no inclusion between classes of joint distributions P of (X, Y ) satisfying Assumptions (CAR) and (CAD). Nevertheless, such a comparison have been often interpreted as an argument in disfavor of the plug-in rules. Indeed, Yang's lower bound shows that the n -1/2 rate cannot be attained under Assumption (CAD) suited for the plug-in rules. Recently, advantages of the ERM type classifiers, including penalized ERM methods, have been further confirmed by the fact that, under the margin (or low noise) assumption, they can attain fast rates of convergence, i.e. the rates that are faster than n -1/2[START_REF] Mammen | Smooth discrimination analysis[END_REF], Tsybakov (2004a), Massart and Nédélec (2003), Tsybakov and van de Geer (2005), Koltchinskii (2005), Audibert (2004)].

h.

  Define the regression function estimator η * n as follows. If the smallest eigenvalue of the matrix B is greater than (log n) -1 we set η * n (x) equal to the projection of ηLP n (x) on the interval [0, 1], where ηLP n (x) is the LP(⌊β⌋) estimator with a bandwidth h > 0 and a kernel K satisfying (3.3) -(3.6). If the smallest eigenvalue of B is less than (log n) -1 we set η * n (x) = 0. Theorem 3.2 Let P be a class of probability distributions P on Z such that the regression function η belongs to the Hölder class Σ(β, L, R d ) and the marginal law of X satisfies the strong density assumption. Then there exist constants C 1 , C 2 , C 3 > 0 such that for any 0 < h ≤ r 0 /c, any C 3 h β < δ and any n ≥ 1 the estimator η *

Definition 3 . 1

 31 For a fixed parameter α ≥ 0, fixed positive parameters c 0 , r 0 , C 0 , β, L, µ max > µ min > 0 and a fixed compact C ⊂ R d , let P Σ denote the class of all probability distributions P on Z such that (i) the margin assumption (MA) is satisfied, (ii) the regression function η belongs to the Hölder class Σ(β, L, R d ), (iii) the strong density assumption on P X is satisfied. Theorem 3.1 and (3.8) immediately imply the next result. Theorem 3.3 For any n ≥ 1 the excess risk of the plug-in classifier f * n = 1I {η * n ≥ 1 2 }

Definition 4 . 1

 41 For a fixed parameter α ≥ 0, fixed positive parameters c 0 , r 0 , C 0 , β, L, µ max > 0 and a fixed compact C ⊂ R d , let P ′ Σ denote the class of all probability distributions P on Z such that (i) the margin assumption (MA) is satisfied, (ii) the regression function η belongs to the Hölder class Σ(β, L, R d ),

Theorem 4 . 2

 42 Let P be a set of probability distributions P on Z such that (i) the margin assumption (MA) is satisfied, (ii) the regression function η belongs to a class Σ which satisfies the complexity assumption (CAR) with the ε-entropy taken w.r.t. the L p (C, λ) norm for some 1 ≤ p ≤ ∞, (iii) for all P ∈ P the supports of marginal distributions P X are included in C. Consider the classifier f S n = 1I {η S n ≥1/2} . If p = ∞ for any n ≥ 1 we have

  where v d λ B(0, 1) is the volume of the unit ball and c 0 > 0 is the constant introduced in the definition (2.1) of the (c 0 , r 0 )-regular set. Let A denote the class of all compact subsets of B(0, c) having the Lebesgue measure c 0 v d c d . Using the previous displays we obtain min W =1 W T BW ≥ cµ min min W =1;S∈A S |s|≤⌊β⌋ W s u s 2 du 2µ 0 . (6.2)

Figure 1 :

 1 Figure 1: Notation summary

e 1 ,

 1 . . . , e d-1 be unit vectors such that e 1 , . . . , e d is an orthonormal basis of R d . Let B * (x, r) (resp. S * (x, r)) denote the ball (resp. the sphere) centered at x and of radius r wrt the norm x * = sup 1≤i≤d | x, e i |.

P 2 √ d-1t ζ d- 1 L

 21 X η(X)η(w k ) ≤ t/4; X ∈ B w k , r 2 t ζ √ 2D ≥ (2U + 1) d-1 L ′ (t/4) dζ ≥ D ′ (t/4) dζ ≥ Ct ζ , hence α ≤ ζ (which is the desired result).For the converse, the proof is similar to the ones of the second and third assertions of the proposition. Without loss of generality, we may assume thatS = (x 1 , . . . , x d ) ∈ R d : max 1≤i≤d |x i | ≤ 1/2 is a subset of C. we consider the distribution P such that -P X is the uniform measure on S the regression function associated with P is η(x 1 , . . . , x d ) = 1 + C η sign(x 1 )|x 1 | β∧1 u(x 1 ) 2 ,

  ε n where • p is the L p (R d , P X ) norm. It follows from the comparison inequality (5.3) thatd(f ηn ) ≤ Cε (1+α)p p+α n δ n . Set ∆ n = Cn -(1+α)p (2+α)p+ρ(p+α)(i.e., ∆ n is of the order of desired rate). Fix t > 0 and introduce the setN * n = {η ∈ N εn : d(f η) ≥ t∆ n }.For any t > 0 we haveP(d( f s n ) ≥ t∆ n ) ≤ P( min η∈N * n [R n (f η) -R n (f ηn )] ≤ 0) = P( min η∈N * n [Z n (f η) -Z n (f ηn ) + d(f η)d(f ηn )] ≤ 0) ≤ P( min η∈N * n [Z n (f η) -Z n (f ηn ) + d(f η)/2 + t∆ n /2d(f ηn )] ≤ 0) ≤ P( min η∈N * n [Z n (f η) + d(f η)/2] ≤ 0) +P(Z n (f ηn ) ≥ t∆ n /2d(f ηn )) ≤ P( min η∈N * n [Z n (f η) + d(f η)/2] ≤ 0) +P(Z n (f ηn ) ≥ t∆ n /2δ n ).Since ∆ n is of the same order as δ n , we can choose t large enough to have t∆ n /2-δ n ≥ t∆ n /4. Thus,P(d( f s n ) ≥ t∆ n ) ≤ card N * n max η∈N * n P(Z n (f η) ≤ -d(f η)/2) +P(Z n (f ηn ) ≥ t∆ n /4) ≤ exp(A ′ ε -ρ n ) max η∈N * n P(Z n (f η) ≤ -d(f η)/2)

P 2 n 2 n.

 22 (Z n (f ηn ) ≥ t∆ n /4) ≤ exp -Cn∆ ∆ n + d(f ηn ) α/(1+α) ≤ exp -Cn∆ ∆ n + δ α/(1+α) n ≤ exp -Cn∆ (2+α)/(1+α) nThe result of the theorem follows now from the above inequalities and the relation n∆(2+α)/(1+α) n ≍ ε -ρ n .

  L 1 or L 2 norm convergence of ηn , as previously described (cf. (1.2)). We do not know whether the super-fast rates are attainable for ERM rules or, more precisely,

	under Assumption (CAD) which serves for the study of the ERM type rules. It
	is important to note that our results on fast rates cover more general setting than
	just classification with plug-in rules. These are rather results about classification
	in the regression complexity context under the margin assumption. In particular, we
	establish minimax lower bounds valid for all classifiers, and we construct a "hybrid"
	plug-in/ ERM procedure (ERM based on a grid on a set regression functions η)
	that achieves optimality. Thus, the point is mainly not about the type of procedure
	(plug-in or ERM) but about the type of complexity assumption (on the regression
	function (CAR) or on the decision set (CAD)) that should be natural to impose.
	Assumption (CAR) on the regression function arises in a natural way in the anal-
	ysis of several practical procedures of plug-in type, such as boosting and SVM [cf.
	Blanchard, Lugosi and Vayatis (2003), Bartlett, Jordan and McAuliffe (2003), Scovel
	and Steinwart (2003), Blanchard, Bousquet and Massart (2004), Tarigan and van de
	Geer (2004)]. These procedures are now intensively studied but, to our knowledge,
	only suboptimal rates of convergence have been proved in the regression complexity
	context under the margin assumption. The results in Section 4 point out this fact
	(see also Section 5), and establish the best achievable rates of classification that
	those procedures should expectedly attain.

  x 2 with an appropriate C > 0. Clearly, η belongs to Hölder classes with arbitrarily large β and Assumption (MA) is satisfied with α = d/2. Thus, for d ≥ 3 and β large enough super-fast rates can occur. Note that in this example the

decision set {x : η(x) ≥ 1/2} has the Lebesgue measure 0 in R d . It turns out that this condition is necessary to achieve classification with super-fast rates when the Hölder classes of regression functions are considered.

  Consider a distribution P in P Σ . Let A be the support of P X . Fix x ∈ A and δ > 0. Consider the matrix B B s 1 ,s 2 |s 1 |,|s 2 |≤⌊β⌋ with elements B s 1 ,s 2 R d u s 1 +s 2 K(u)µ(x + hu)du. The smallest eigenvalue λ B of B satisfies

	6 Proofs
	6.1 Proof of Theorem 3.2
	2 ≤ Cn -2β 2β+d	(5.7)

  ). Forany y k ∈ G, let y - k = [x -; y k ] ∩ S * (x -, r 2 ) and y + k = [x + ; y k ] ∩ S * (x + , r 2 ). Since y ky ≤ D/2, we have y - k = x -+ r 2 e d + 2r 2 D t ζ d-1 i=1 k i e i and y + k = x +r 2 e d + 2r 2 D t ζ d-1 i=1 k i e i . For any y k in G, consider the continuous path formed by the segments [y - k ; y k ] and [y k ; y + k ]. Since η is continuous on this path, there exists w k ∈ γ k [y - k ; y k ]∪ [y k ; y + k ] such that η(w k ) = 1/2 + t/2. Now let us show that when k = k ′ , w k and w k ′ are at least

	√	2r 2

(i) the margin assumption (MA) is satisfied, (ii) the regression function η belongs to the Hölder class Σ(β, L, R d ), (iii) for all P ∈ P the supports of marginal distributions P X are included in C.

If C is a compact the estimates of ε-entropies of Hölder classes Σ(β, L, R d ) in the L ∞ (C, λ) norm can be obtained from [START_REF] Kolmogorov | ǫ-entropy and ǫ-capacity of sets in function spaces[END_REF], and they yield Assumption (CAR) with ρ = d/β. Therefore, from (4.2) we easily get the following upper bound.

with some constant C > 0 depending only on α, β, d, L and C 0 .

Since P ′ Σ ⊂ P 0 Σ , Theorems 3.5 and 4.3 show that n -(1+α)β (2+α)β+d is optimal rate of convergence of the excess risk on the class of distributions P 0 Σ .

Comparison lemmas

In this section we give some useful inequalities between the risks of plug-in classifiers and the L p risks of the corresponding regression estimators under the margin assumption (MA). These inequalities will be helpful in the proofs. They also illustrate a connection between the two complexity assumptions (CAR) and (CAD) defined in the Introduction and allow one to compare our study of plug-in estimators with that given by Yang (1999) who considered the case α = 0 (no margin assumption), as well as with the developments in [START_REF] Bartlett | Convexity, classification and risk bounds[END_REF] and Blanchard, [START_REF] Blanchard | On the rate of convergence of regularized boosting classifiers[END_REF].

Throughout this section η is a Borel function on R d and f (x) = 1I {η(x)≥1/2} .

For 1 ≤ p ≤ ∞ we denote by • p the L p (R d , P X ) norm. We first state some comparison inequalities for the L ∞ norm.

for some constant C > 0. This has been shown by [START_REF] Stone | Optimal global rates of convergence for nonparametric regression[END_REF] under the additional strong density assumption and by [START_REF] Yang | Minimax nonparametric classification -Part I: Rates of convergence, Part II: Model selection for adaptation[END_REF] with no assumption on P X . Using (5.7) and (5.5) we get that the excess risk of the corresponding plug-in classifier fn = 1I {ηn≥1/2} admits a bound of the order n -2β 2β+d 1+α 2+α which is suboptimal when α = 0 (cf. Theorems 4.2, 4.3). In other words, under the margin assumption, Lemma 5.2 is not the right tool to analyze the convergence rate of plug-in classifiers. On the contrary, when no margin assumption is imposed (i.e., α = 0 in our notation) inequality (1.2), which is a version of (5.5) for α = 0, is precise enough to give the optimal rate of classification [START_REF] Yang | Minimax nonparametric classification -Part I: Rates of convergence, Part II: Model selection for adaptation[END_REF]].

Another way to obtain (5.5) is to use [START_REF] Bartlett | Convexity, classification and risk bounds[END_REF]: it is enough to apply their Theorem 10 with (in their notation)

and to note that for this choice of φ we have

Blanchard, Lugosi and Vayatis (2003) used the result of [START_REF] Bartlett | Convexity, classification and risk bounds[END_REF] to prove fast rates of the order n -2(1+α) 3(2+α) for a boosting procedure over the class of regression functions η of bounded variation in dimension d = 1. Note that the same rates can be obtained for other plug-in classifiers using (5.5). Indeed, if η is of bounded variation, there exist estimators of η converging with the mean squared L 2 rate n -2/3 [cf. van de Geer (2000), [START_REF] Györfi | A Distribution-Free Theory of Nonparametric Regression[END_REF]], and thus application of (5.5) immediately yields the rate n -2(1+α) 3(2+α) for the corresponding plug-in rule. However, Theorem 4.2 shows that this is not an optimal rate (here again we observe that inequality (5.5) fails to establish the optimal properties of plug-in classifiers). In fact, let d = 1 and let the assumptions of Theorem 4.2 be satisfied, where instead of assumption (ii) we use its particular instance: η belongs to a class of functions on [0, 1] whose total variation is bounded by a constant L < ∞. It follows from Birman and Solomjak (1967) that Assumption (CAR) for this class is satisfied with ρ = 1 for any 1 ≤ p < ∞. Hence, we can apply (4.3) of Theorem 4.2 to find that sup For appropriate positive parameters C 0 , c 0 , r 0 , µ max > µ min > 0, the distribution P belongs to P Σ provided that α ≤ d/2 (in order that the margin assumption holds). We have obtained the desired result since η hits 1/2 at 0 R d which is in the interior of the support of P X .

• For the last item of Proposition 3.4, let P ∈ P Σ such that the regression function η associated with P crosses 1/2 at x 0 ∈ 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 0000000000000000000000 denote the biggest integer smaller than or equal to

). This distance is equal to the distance between y - K and its orthogonal projection on [y - K ′ ; y K ′ ], which is the distance between y - K and the line (x -; y K ′ ). Let K ′′ = (0, U, . . . , U) ∈ Z d-1 . To compute this distance V , it suffices to look at the plane (x -; y K ′′ ; y K ) (see figure 2). We obtain that the angle θ between y K ′x -and y K ′′x + is smaller than π/4. As a consequence, V = y - Ky -

Finally, focusing on the behaviour of the regression function near the w k 's, by using Lemma 6.1 with κ = 4 ζ r 2 √ 2D , we obtain that there exists L ′ > 0 and t 0 > 0


S Strada

C Mari

J B Filippi

F Bosseur

FOREST FIRE IMPACT ON AIR QUALITY: THE LANCON-DE-PROVENCE 2005 CASE

Keywords: air quality, coupled fire-atmosphere model, Mediterranean fire, chemistry, dynamics

Forest fires release significant amounts of gases and aerosols into the atmosphere. Depending on meteorological conditions, fire emissions can efficiently spoil air quality and visibility far away from the source. The aim of this study is to evaluate the fire impact on air quality downwind of the burning region in the Mediterranean zone.

Wildfire behaviour is simulated using a semi-physical model, ForeFire, based on an analytical resolution of the rate of spread. ForeFire provides the burnt area at high temporal and spatial resolutions; in the mesoscale non-hydrostatic meteorological model Meso-NH fire forcings, as heating and water vapor fluxes, are computed scaling them to the burnt area data given by ForeFire. A chemical scheme is coupled to Meso-NH to account for air quality evolution. Chemical emissions are scaled to the heating fluxes and based on emission factors for the Mediterranean vegetation. The model is used both in a 3D regional and 2D LES configurations.

In 2005, an arson forest fire burned nearly 700 ha near Lançon-de-Provence, southeast France. ForeFire was successfully tested on this case study. Here, results from the coupled model, MesoNH-ForeFire, show the sensitivity of atmospheric dynamics and air quality situation to the coupling fire-atmosphere. Simulations put also on evidence how initial conditions and heat fluxes control fire emissions injection height. Finally, tracer distribution is simulated and its pattern shows that although the impact of the fire is visible several kilometres downwind of the burnt area, it remains confined within the planetary boundary layer. This behaviour is confirmed by comparing simulated aerosol particles concentrations with the air quality survey network available in southeastern France.

Introduction

In Mediterranean region climate change is making weather conditions more extremes, allowing huge forested areas to become ignited with increasing frequence, as noted by [START_REF] Pausas | Changes in fire and climate in the eastern iberian peninsula (Mediterranean basin)[END_REF].

Forest fires are a risk to the environment and to public health as wildfires represent a significant source of gases and aerosols. Depending on meteorological conditions, these emissions can efficiently perturb air quality and visibility far away from the sources [START_REF] Miranda | Forest Fire Impact on Air Quality over Portugal[END_REF][START_REF] Takegawa | Photochemical production of O 3 in biomass burning plumes in the boundary layer over northern Australia[END_REF][START_REF] Bytnerowicz | Analysis of the effects of combustion emissions and Santa Ana winds on ambient ozone during the October 2007 southern California wildfires[END_REF].

The aim of this work is to simulate the interactions of a Mediterranean fire with its environment both in terms of dynamics and air quality.

Fire-Atmosphere Coupled System

The fire spread model ForeFire has been coupled with the French mesoscale atmospheric model Meso-NH to better characterize the impact of fire dynamics and chemistry on the air quality downwind of the burnt area.

The case study is Lançon-de-Provence 2005 forest fire, a typical Mediterranean wildfire burst in the southeast of France.

The Lançon-de-Provence case has already been successfully simulated by several fire propagation models, including ForeFire, thus constitutes a good benchmark for testing the coupling and its forecasting performances.

The Atmospheric Model: Meso-NH Meso-NH is an anelastic, non-hydrostatic mesoscale meteorological model, designed to simulate atmospheric circulation from large synoptic to large eddy scales [START_REF] Lafore | The Meso-NH atmospheric simulation system. Part I: adiabatic formulation and control simulations[END_REF]. The model was jointly developped by Météo-France and Laboratoire d'Aérologie (CNRS).

Meso-NH incorporates many options for the physical parametrisations. All prognostic variables are advected in an Eulerian way by the Piecewise Parabolic Method [START_REF] Colella | The piecewise parabolic method (PPM) for gasdynamical simulations[END_REF]. The microphysics included three water phases with five species of precipitating and nonprecipitating liquid and solid water [START_REF] Pinty | A mixed-phase cloud parameterization for use in mesoscale non-hydrostatic model: simulations of a squall line and of orographic precipitations[END_REF]. Radiative processes are represented are represented using the radiation scheme developed by the European Centre for Medium-Range Weather Forecast (ECMWF) (the Rapide Radiative Transfer Model, RRTM, [START_REF] Mlawer | Radiative transfer for inhomogeneous atmospheres: RRTM, a validated correlated-K model for the longwave[END_REF].

The model simulates the concentration of 40 chemical species utilising 73 chemical reactions [START_REF] Crassier | Development of a reduced chemical scheme for use in mesoscale meteorological models[END_REF]. Chemical species are initialized using ESCOMPTE campaign results [START_REF] Cros | The ESCOMPTE program: an overview[END_REF][START_REF] Mediasfrance | ESCOMPTE EXERCISE Homepage[END_REF] thanks to similarities in the geographical area and in the period of the year between the two studied cases. For the ESCOMPTE campaign MOCAGE, a multi-scale chemistry and transport model, has simulated concentrations of different chemical species. Results from MOCAGE simulations at 00:00 UTC 21 June, 2001, are taken as initial vertical profiles for some selected background species. Profiles from the nearest location to Lançon-de-Provence were used for the entire domain (i.e. initial concentrations are homogeneous over the entire domain).

At the resolution commonly used for mesoscale simulation, forest fires are sub-grid scale processes [START_REF] Freitas | Including the sub-grid scale plume rise of vegetation fires in low resolution atmospheric transport models[END_REF]. In order to constrain the effect of the fire in the 3D simulation we performed a 2D simulation of the perturbed atmosphere at high resolution.

• 3D model configuration

The 3D Meso-NH is run with three two-way grid-nested domains, whose horizontal mesh size is, respectively, 25, 5 and 1 km. The three domains are shown in the Figure 1. The vertical grid has 72 points up to an elevation of 23 km with a level spacing ranged from 40 m near the surface to 600 m higher in the atmosphere.

The simulation covers 19 h, starting on 00:00 UTC 1 July 2005, with different time steps for each domain. Dynamical variables are initialized and constrained at the boundaries using 00:00 and 12:00 UTC operational reanalysis from ECMWF (25 km horizontal resolution).

The turbulence parametrisation is based on a 1.5-order closure [START_REF] Cuxart | A turbulence scheme allowing for mesoscale and large-eddy simulations[END_REF]. The surface energy exchanges are parametrised according to four different physical model depending on the surface type (nature surface, urban area, ocean and lake). In particular, natural land surfaces are handled by the Interactions Soil-Biosphere-Atmosphere scheme (ISBA, [START_REF] Noilhan | A simple parameterization of land surface processes for meteorological models[END_REF]. Land use informations and soil occupation at 1 km resolution are provided by the global database Ecoclimap [START_REF] Masson | A Global Database of Land Surface Parameters at 1-km Resolution in Meteorological and Climate Models[END_REF].

• 2D model configuration In 2D, Meso-NH is run with horizontal resolutions set to 65 m along the y-axis and 250 m along the x-axis, over a flat terrain. The x-axis direction is defined along the plume trajectory simulated by the 3D model. The vertical grid has 120 levels, getting a maximal altitude of 23 km; the level spacing stretches from 2 m up to 500 m at the top of the model. At this resolution, convective fluxes are explicitly resolved by the model. A complete three dimensional scheme was used for resolving turbulent fluxes [START_REF] Cuxart | A turbulence scheme allowing for mesoscale and large-eddy simulations[END_REF].

Simulation starts on 1 July, 2005, at 11:00 UTC and it is integrated for 3 h, corresponding to the period of maximum of fire intensity. Initial and boundary meteorological conditions are defined from a radiosonde taken on 1 July, 2005, at 12:00 UTC in Nimes (located 63 km northwest away from Lançon-de-Provence).

The fire propagation model: ForeFire

Predicting wildfire behaviour asks for a Rate of Spread (RoS) equation: a ratio between the heat flux received by the potential fuel ahead of the fire and the heat required to ignite this fuel [START_REF] Pyne | Introduction to wildland fire[END_REF].

In the field of wildland fire behaviour modelling, a large used and well-known method is the Rothermel's one. This is an empirical fire spread model whose fomulation was drawn from fitting the solution of the energy balance equation to experimental data.

In this study, the semi-physical model ForeFire, developed at the University of Corte [START_REF] Filippi | Coupled atmosphere-wildland fire modelling[END_REF], is used to simulate the propagation of fire. ForeFire has an analytical formulation for the RoS where wind, slope effects and fuel parameters are explicitly taken into account, so, unlike Rothermel's model, no a priori knowledge is required [START_REF] Balbi | A physical model for wildland fires[END_REF].

In ForeFire the advance of the fire is controlled by a front tracking algorith. At each time step, the algorithm reconstructs the shape of the front fire by displacing each front agent according to the RoS information, along propagation vectors directed normal to the fireline.

The coupling method: Meso-NH-Fire model At the grid resolutions considered in 3D simulation, forest fires are subgrid scale processes. For this reason, an off-line coupling is initiated between the fire and the atmospheric model, i.e with no feedback from the atmosphere to the fire.

ForeFire provides the burnt area, A (in m 2 ), and the location of the burning cells to the meteorological model. The surface scheme ISBA accomplishes the fire-atmosphere coupling by computing wildfire contribution to latent and sensible heat fluxes at each time step of the meteorological model. The sensible heat flux φ S is set to 100 kW m -2 according to observations during a prescribed fire in Corsica [START_REF] Silvani | Fire spread experiments in the field: Temperature and heat fluxes measurements[END_REF]. Latent heat flux contribution, φ L is fixed to 100 kg m -2 following [START_REF] Filippi | Coupled atmosphere-wildland fire modelling[END_REF].

At low resolution (∆x = 1 km), the burnt area is much smaller than the Meso-NH grid cell which results in a dilution of the fire signatures. Coupling of subgrid scale fire properties and the thermal plume model in Meso-NH [START_REF] Pergaud | A Parameterization of Dry Thermals and Shallow Cumuli for Mesoscale Numerical Weather Prediction[END_REF] is currently being explored. On the contrary, at high resolution (∆x = 250 m), the turbulent motions, forced by fire heat fluxes, are explicitly resolved.

In 2D simulation, only the front of the fire is considered: its surface measures about 3 ha and it is stationary. Burnt area information is required also to calculate chemical emissions due to forest fires. Emissions are obtained in a two-step process. First, an estimate of carbon monoxide (CO) emission (in gr) for a specific compound i is calculated by the wellknown equation of [START_REF] Seiler | Estimates of gross and net fluxes of carbon between the biosphere and the atmosphere from biomass burning[END_REF]:

E i = A × F L × β × EF i ( 1
)
where A is the burnt area (in m 2 ); F L is the fuel loading (fuel material per unit area, in kg m -2 ); β is the burning efficiency of the aboveground biomass; EF i (in gr/kg) is the emission factor for the considered i specie. Second, an estimate of the emissions for the other gases is deduced using emission ratios with respect to carbon. The first part of the Table 1 gives values found in the litterature for fuel loading and burning efficiency for Mediterranean scrublands [START_REF] Miranda | Forest Fire Impact on Air Quality over Portugal[END_REF]; the second part resumes emission factors for some selected chemical species [START_REF] Miranda | An integrated numerical system to estimate air quality effects of forest fires[END_REF][START_REF] Miranda | Forest Fire Impact on Air Quality over Portugal[END_REF][START_REF] Trentmann | Chemical processes in a young biomassburning plume[END_REF][START_REF] Andreae | Emission of trace gases and aerosols from biomass burning[END_REF]. 6 square kilometers), on a surface mainly covered by garrigues, a type of low, soft-leaved scrubland found around the Mediterranean Basin, generally near the seacoast.

On 30 June, 2005, the 3D Meso-NH simulated synoptic situation over western Europe is characterized by a strong pressure gradient with high pressure over the Atlantic Ocean and a cyclonic situation over the Gulf of Genova. This gradient together with the tunnel between the Alps and the Massif Central favours a strong northwesterly wind, the so-called Mistral (Fig. 2).

On 1 July, 2005, at 07:00 UTC, simulated atmospheric conditions shows a boundary layer (BL) height (not shown) of ∼ 1 km near Lançon-de-Provence, BL height goes decreasing towards the sea to ∼ 0.8 km. At this time in the morning, the convective mixing layer is beginning to grow in depth; it acts as a stable cap for the atmosphere. Moreover, looking at the virtual potential temperature (not shown), a temperature inversion is located between 2 and 3 km: this inversion can control the injection height of the fire plume, preventing it from reaching higher altitudes [START_REF] Trentmann | Chemical processes in a young biomassburning plume[END_REF].

Model results

In the following, fire impacts on atmospheric dynamics and air quality are discussed comparing 2D and 3D simulations results.

Results from 2D configuration are given after 2 h of simulation time. For 3D Meso-NH-Fire model results correspond to the simulation of 1 July, 2005, at 12:00 UTC, on the finest nested grid (1 km increment). For 3D simulations, all cross sections have been obtained along the red tilted axis shown in Figure 5(a), along the plume trajectory.

Fire impacts on atmospheric dynamics

Biomass burning is a strong source of sensible and latent heat fluxes that are emitted in the atmosphere in the form of hot gases and water vapour [START_REF] Luderer | Modeling of biomass smoke injection into the lower stratosphere by a large forest fire (Part II): sensitivity studies[END_REF]. The interaction between the hot fire plume and the cooler surrounding air triggers turbulent eddies; turbulence associated to fire can efficiently mix colder air into the smoke plume, diluting the hot plume and reducing convection [START_REF] Freitas | Including the sub-grid scale plume rise of vegetation fires in low resolution atmospheric transport models[END_REF]. For this reason, it is interesting to examine how atmospheric turbulence and turbulent vertical fluxes can be affected by the ignition and the spread of a forest fire. In the following, turbulent kinetic energy (TKE, in m 2 / s 2 ) and the turbulent vertical kinematic heat flux (w ′ θ ′ , in K m/s) are shown for 2D and 3D simulations.

Figure 3 shows that the structure of the boundary layer is strongly perturbed over the point of ignition in the 2D model. Elevated TKE (> 20m 2 / s -2 ) extend over more than 10 km downwind of the fire, toward the sea. Fire-induced effects remain confined in the boundary layer, below 2 km altitude.

Figure 4 puts on evidence that fire impacts on atmospheric stability are too much diluted at mesoscale resolutions, in the 3D configuration of Meso-NH-Fire model. It is hard to distinguish fire-induced turbulence from orographic turbulence.

Air quality downwind of the fire

In spite of being a good benchmark for fire spread models, unfortunately Lançon-de-Provence forest fire is not a well documented wildfire. The lack of data makes difficult to validate the way the fire has been parametrised in the coupled model. Anyway, a MODIS image and measurements of pollutants provided by the air quality survey network ATMOPACA have been used to evaluate modelling results. MODIS-AQUA captured Lançon fire plume on 1 July, 2005, at 13:00 UTC. MODIS image, Fig. 5a, is compared to the horizontal pattern of CO simulated with the 3D Meso-NH-Fire model at altitude of 400 m, just 1 h before MODIS crossing time, Fig. 5b. CO is an insoluble species and has a lifetime of about one month in the troposphere, so it can be considered a good fire tracer. In term of trajectory the comparison is encouranging: Meso-NH-Fire model can reproduce fairly well the overall direction of the fire plume. The simulated plume is lightly rotated towards East compared to the real fire plume: this is due to a shift in Meso-NH wind patterns. Figure 5b shows very high mixing ratios in carbon monoxide (∼ 1000 ppbv) above the ignition point. CO mixing ratios go decreasing downwind the burning area. Inside the plume, CO levels are of ∼ 100 -200 ppbv, a typical background concentration at these latitudes [START_REF] Fisher | Model simulations and aircraft measurements of vertical, seasonal and latitudinal O 3 and CO distributions over europe[END_REF], only 60 km away of the fire.

Figure 6 shows the cross section of carbon monoxide concentration, in ppbv, simulated by the 2D and the 3D Meso-NH-Fire model. 2D LES simulation shows very high CO concentrations near the ignition point: ∼ 20000 ppbv (Fig. 6a). Such high mixing ratios were observed during prescribed [START_REF] Miranda | Smoke measurements during Gestosa-2002 experimental field fires[END_REF] and natural [START_REF] Jost | Trace gas chemistry in a young biomass burning plume over Namibia: Observations and model simulations[END_REF] fires. Then CO mixing ratios decrease downwind the fire, but still remain above background conditions. Figure 6b shows the vertical cross section of carbon monoxide concentration in the 3D version of the model, in units ppbv. This picture shows how CO, low reacting species, is primarly transported high in the atmosphere at a maximum altitude of 1 km. Near the fire location a strong gradient is observed with CO concentration halves over a distance of ∼ 20 km. Finally, the vertical structure of the CO plume confirms that Lançon fire plume remains confined in the BL. It is worth noting that the simulation at low resolution (Fig. 6b) understimates the CO mixing ratios and the injection height by 1 km compared to the LES simulation.

Figure 7 of NOx immediately induces a titration of ozone which levels fall below ambient concentration. Ozone levels recover their background concentrations several kilometers downwind of the fire.

Figure 8 presents the observed PM10 hourly concentrations registered on 30 June, 1 July and 2 July, 2005, by three air quality stations located near the burning area. MODIS AQUA image shows that the city of Marseille was affected by the smoke plume on 1 July, 2005. This critical situation in term of air quality is confirmed by PM10 levels recorded at three different air quality stations in Marseille (only one is shown here). The day before and after the fire, PM10 concentrations remained well below 70µg/m 3 . The day of the fire, a pick of 151µg/m 3 is registered at 12:00 UTC at the Marseille Timone station (Fig. 8a). Air quality stations located at the edge of the smoke plume, Avignon Mairie and Le Pontet, do not exhibit such increase. Meso-Nh simulates the increase of PM10 in the smoke plume, ∼ 40 km, downwind the fire. The observed and simulated increases of PM10 concentrations near the surface confirm that the smoke plume has remained trapped in the boundary layer rather than being transported to the free troposphere. This behaviour follows the global trend of Mediterranean fires that mostly deposit their emission into the atmospheric boundary layer, below 5 km [START_REF] Langmann | Vegetation fire emissions and their impact on air pollution and climate[END_REF][START_REF] Labonne | Injection height of biomass burning aerosols as seen from a spaceborne[END_REF].

Conclusions

The study illustrates the sensitivity of the atmospheric dynamics and air quality situation to the coupling between a fire and an atmospheric model.

Concerning atmospheric dynamics, in the 3D Meso-Nh-Fire model fire-induced flows are too much diluted and masked by orographic effects. On the contrary 2D LES simulation clearly shows an increase of turbulent motions due to fire forcings in term of heat fluxes. Both simulations show that the impact of fire on atmospheric tracers is visible several kilometers downwind of the burnt area, as confirmed by the MODIS-AQUA image. The fire impact on air quality spreads over more than 60 km. Both low resolution and LES models simulate a smoke plume trapped in the boundary layer, however at 1 km resolution the signatures of the fire are significantly diluted. The comparison between the air quality forecasting and the ground-based measurements of pollutants provided by the French air quality network confirms the advection of the smoke plume within the boundary layer.

In the future, some enhancements are planned for different aspects of the coupled model. In regards to atmospheric feedbacks induced by wildfires, an important aim is to improve the way fire processes are parametrised in lower resolution models and to implement new schemes for a better modelling of the plume rise. Concerning air quality study, sensitivity studies are planned on the ozone production efficiency in the fire plume as a function of the dynamics of the plume and the strenght of the emissions. Particular efforts are needed in the chemical reaction schemes to account for fire specific products (HCN, HCHO ...) and in refining emission factors database for Mediterranean region. Finally, for the numerical part, future enhancements are planned to test the on-line coupling between ForeFire and Meso-NH.

Figure 1 :

 1 Figure 1: Meso-NH nested domains used in the Lançon-de-Provence case study from the coarse 25-km grid down to the fine 1-km grid.

3.

  Figure 2: Wind pattern over southeast France at 1500 m above the mean sea level for 07:00 UTC 1 July, 2005, on 5 km grid-mesh domain. The dash line indicates boundaries of the 1 km grid-mesh domains. Wind arrows fly with the wind, contour levels indicate wind speed in m/s.

Figure 3 :

 3 Figure 3: Cross sections of TKE (m 2 / s -2 , Fig. (a)) and turbulent vertical kinematic heat flux (w ′ θ ′ , in K m/s, Fig. (b)) for simulation with 2D Meso-NH configuration, after 2 h of simulation time.

Figure 4 :

 4 Figure 4: Cross sections of TKE (m 2 / s -2 , Fig. (a)) and turbulent vertical kinematic heat flux (w ′ θ ′ , in K m/s, Fig. (b)) for simulation with 3D Meso-NH configuration on 1 July, 2005, at 12:00 UTC. The red line highlights the area covered by 2D LES simulation.

  shows difference in nitrogen oxides (NOx, Fig 7a) and ozone (O 3 , Fig 7b) mixing ratios between a fire-induced and a no-fire simulation at an altitude of 400 m after one hour of simulation. Directly over the burning area, the strong production

Figure 5 :

 5 Figure 5: Qualitative comparison between Lançon fire plume seen by MODIS-AQUA and simulated with the 3D Meso-NH-Fire model. (a) MODIS-AQUA image captured on 1 July, 2005, at 13:00 UTC. Lançon-de-Provence fire is the first red spot on the left of the picture. (b) Carbon monoxide plume (ppbv) simulated on 1 July, 2005, at 12:00 UTC, on the finest grid (1 km increment) at altitude of 400 m. The tilted axis indicates direction along with cross sections are traced for 3D simulation.

Figure 6 :

 6 Figure 6: Cross sections of the carbon monoxide (CO) concentration (in ppbv). (a) Simulated with the 2D Meso-NH-Fire model after 2 h of simulation time. (b) Simulated with the 3D Meso-NH-Fire model on 1 July, 2005, at 12:00 UTC.

Figure 7 :

 7 Figure 7: Concentration contour maps of nitrogen oxides (NOx, Fig. (a)) and ozone (O 3 , Fig. (b)) (ppbv) at 400 m above sea mean level on 1 July, 2005, at 12:00 UTC. The two plots show the concentration difference between the simulations with and without fire forcings.

Figure 8 :

 8 Figure 8: Daily pattern for PM10 concentration (in µg/m 3 ) measured on 30 June (red line), 1 July (green) and 2 July (blue), 2005, by the air quality survey network available in south-eastern France: ATMOPACA. Air quality stations: (a) Marseille Timone affected by the fire plume; (b) Avignon Mairie and (c) Le Pontet located outside the plume trajectory.

Table 1 :

 1 At each 2D model time step, sensible and latent heat fluxes are computed imposing same nominal values for φ S and φ L . Values for southern European forest fire emissions.

	Ref.	Vegetation type Fuel Load Combustion Efficiency
			(kg m -2 )	%
	Miranda et al. (2008) Shrubs	1.00	0.80
	Ref.		Gases	EF (g kg -1 )
	Miranda et al. (2008)	CO	82.0
			NO	7.0
			NO 2	7.0
	Trentmann et al. (2003)	HCHO	2.0
			Ethane C 2 H 6	0.7
			Alkanes	1.0
			(HC 3 , HC 5 , HC 8 , CH 3 OH)
			Alkene: C 2 H 4	1.2
			Alkene: C 3 H 6	0.5
			Ch 3 COOH	2.0
	Andreae and Merlet (2001) CH 3 CHO	0.5
			Aromatics	0.2
			(Toluene, Xylenes, Phenol)