Jean-Baptiste Monnier
email: monnier@math.jussieu.fr

Classification via local multi-resolution projections (extended version) Technical Report

Keywords: AMS 2000 subject classifications: Primary 62G05, 62G08, Secondary 62H30, 62H12 Nonparametric regression, Random design, Multi-resolution analysis, Supervised binary classification, Margin assumption. 1

We focus on the supervised binary classification problem, which consists in guessing the label Y associated to a co-variate X ∈ R d , given a set of n independent and identically distributed co-variates and associated labels (X i , Y i ). We assume that the law of the random vector (X, Y ) is unknown and the marginal law of X admits a density supported on a set A. In the particular case of plug-in classifiers, solving the classification problem boils down to the estimation of the regression function η(X) = E[Y |X]. Assuming first A to be known, we show how it is possible to construct an estimator of η by localized projections onto a multi-resolution analysis (MRA). In a second step, we show how this estimation procedure generalizes to the case where A is unknown. Interestingly, this novel estimation procedure presents similar theoretical performances as the celebrated local-polynomial estimator (LPE). In addition, it benefits from the lattice structure of the underlying MRA and thus outperforms the LPE from a computational standpoint, which turns out to be a crucial feature in many practical applications. Finally, we prove that the associated plug-in classifier can reach super-fast rates under a margin assumption.

1 Introduction

Setting

The supervised binary classification problem is directly related to a wide range of applications such as spam detection or assisted medical diagnosis (see [28, chap. 1] for more details). It can be described as follows.

The supervised binary classification problem. Let E stand for a subset of R d and write Y = {0, 1}. Assume we observe n co-variates X i ∈ E and associated labels Y i ∈ Y such that the elements of D n = {(X i , Y i ), i = 1, . . . , n} are n independent realizations of the random vector (X, Y ) ∈ E × Y of unknown law P X,Y . Given D n and a new co-variate X n+1 , we want to predict the associated label Y n+1 so as to minimize the probability of making a mistake.

In other words, we want to build a classifier h n : E → Y upon the data D n , which minimizes P(h n (X) = Y |D n ). It is well known that the Bayes classifier h * (τ ) := 1 {η(τ )≥1/2} , where η(τ ) := E[Y |X = τ ] = P(Y = 1|X = τ ) (unknown in practice), is optimal among all classifiers since, for any other classifier h n , we have ℓ(h n , h * ) := P(h n (X) = Y |D n ) -P(h * (X) = Y ) ≥ 0 (see [START_REF] Devroye | A probabilistic theory of pattern recognition[END_REF]). As a consequence, we measure the classification risk T (h n ) associated to a classifier h n as its average relative performance over all data sets D n , T (h n ) = E ⊗n ℓ(h n , h * ). As described in [START_REF] Devroye | A probabilistic theory of pattern recognition[END_REF]Chap. 7], there is no classifier h n such that T (h n ) goes to zero with n at a specified rate for all distributions P X,Y . We therefore make the assumption that P X,Y belongs to a class of distributions P (as large as possible) and aim at constructing a classifier h n such that inf θn sup P X,Y ∈P T (θ n ) sup

P X,Y ∈P T (h n ) (log n) δ inf θn sup P X,Y ∈P T (θ n ), n ≥ 1, (1)
where the infinimum is taken over all measurable maps θ n from E into Y and means lesser or equal up to a multiplicative constant factor independent of n. Any classifier h n verifying eq. ( 1) will be said to be (nearly) minimax optimal when δ = 0 (δ > 0). P will stand for the set of all distributions such that the marginal law P X of X admits a density µ on E and η belongs to a given smoothness class. Throughout the paper, we will denote by µ the density of P X .

Many classifiers have been suggested in the literature, such as k-nearest neighbors, neural networks, support vector machine (SVM) or decision trees (see [START_REF] Devroye | A probabilistic theory of pattern recognition[END_REF][START_REF] Hastie | The Elements of Statistical Learning: Data Mining, Inference and Prediction[END_REF]). In this paper, we will exclusively focus on plug-in classifiers h n (τ ) := 1 {ηn(τ )≥1/2} , where η n stands for an estimator of η. With such classifiers, it is shown in [START_REF] Vapnik | Statistical learning theory[END_REF] that,

T (h n ) ≤ 2E ⊗n E|η n (X) -η(X)|, (2)
where the term on the rhs is known as the regression loss (of the estimator η n of η) in L 1 (E, µ)norm. Eq. [START_REF] Antoniadis | Random design wavelet curve smoothing[END_REF] shows in particular that rates of convergence on the classification risk of a plug-in classifier h n can be readily derived from rates of convergence on the regression loss of η n . This prompts us to focus on the regression problem, which can be stated in full generality as follows.

The regression on a random design problem. Let E, Y stand for subsets of R d and R, respectively. Assume we dispose of n co-variates X i ∈ E and associated observations Y i ∈ Y such that the elements of D n = {(X i , Y i ), i = 1, . . . , n} are n independent realizations of the random vector (X, Y ) ∈ E × Y of unknown law P X,Y . We define ξ := Yη(X), where η(τ

) := E[Y |X = τ ],
so that by construction E[ξ|X] = 0. Given D n and under the assumption that P X,Y belongs to a large class of distributions P, we want to come up with an estimator η n of η, which is as accurate as possible for the wide range of losses S p (η n ) = E ⊗n E|η n (X)η(X)| p , p ≥ 1.

As described previously, in the particular case where Y = {0, 1}, we fall back on the regression problem associated to the classification problem with plug-in classifiers. In this case, ξ is bounded such that |ξ| ≤ 1. Notice however that the regression on a random design problem stated above permits for Y to be any subset of R (including R itself). To be more precise, and by analogy with eq. ( 1), our aim is to build an estimator η n of η such that, for all p ≥ 1, inf

θn sup P X,Y ∈P S p (θ n ) sup P X,Y ∈P S p (η n ) (log n) δ inf θn sup P X,Y ∈P S p (θ n ), n ≥ 1, (3)
where the infinimum is taken over all measurable maps θ n from E into Y. And η n will be said to be (nearly) minimax optimal when δ = 0 (δ > 0).

Motivations

Many estimators η n of η have been suggested in the literature to solve the regression on a random design problem. Among them, the celebrated local polynomial estimator (LPE) has been praised for its flexibility and strong theoretical performances (see [START_REF] Stone | Optimal rates of convergence for nonparametric estimators[END_REF][START_REF] Stone | Optimal global rates of convergence for nonparametric regression[END_REF]). As is well known, the LPE is minimax optimal in any dimension d ∈ N and for any S p -loss, p ∈ (0, ∞], over the set of laws P such that (i) µ is bounded from above and below on its support A := Suppµ = {τ : µ(τ ) > 0}, (ii) η belongs to a Hölder ball C s (E, M) of radius M and (iii) ξ has sub-Gaussian tails. As a drawback, the LPE is computationally expansive since it requires to perform a new regression at every single point x ∈ A where we want to estimate η. Computational efficiency is however of primary importance in many practical applications.

In this paper, we show that it is possible to construct a novel estimator η n of η by localized projections onto multi-resolution analysis (MRA) of L 2 (R d , λ) (where λ stands for the Lebesgue measure on E), which presents similar theoretical performances and is computationally more efficient than the LPE.

The hypotheses

In this section, we summarize the assumptions on µ, A, η and ξ that will be used throughout the paper.

Assumption on µ. Let us denote by µ min , µ max two real numbers such that 0 < µ min ≤ µ max < ∞. As is standard in the regression on a random design setting, we assume that the density µ is bounded above and below on its support A.

(D1) µ min ≤ µ(τ ) ≤ µ max for all τ ∈ A.

This guarantees that we have enough information at each point x ∈ A in order to estimate η with best accuracy. For a study with weaker assumptions on µ, the reader is referred to [START_REF] Gaïffas | Convergence rates for pointwise curve estimation with a degenerate design[END_REF][START_REF] Gaïffas | On pointwise adaptive curve estimation based on inhomogeneous data[END_REF], for example, and the references therein.

Assumption on A. We first assume that, (S1) A = E = [0, 1] d . Therefore A is known under (S1). We will deal with the case where A is unknown in Section 9.

Assumption on η. Fix r ∈ N. In the sequel, we will assume that, (H r s ) The regression function η belongs to the generalized Lipschitz ball L s (E, M) of radius M, for some s ∈ (0, r). Unless otherwise sated, s is unknown but belongs to the interval (0, r), where r is known. For a detailed review of generalized Lipschitz classes, the reader is referred to Section 13.1 below.

Assumptions on the noise ξ. We will consider the two following assumptions, (N1) Conditionally on X, the noise ξ is uniformly bounded, meaning that there exists an absolute constant K > 0 such that |ξ| ≤ K. (N2) The noise ξ is independent of X and normally distributed with mean zero and variance σ 2 , which we will denote by ξ ∼ Φ(0, σ 2 ). Assumption (N1) is adapted to the supervised binary classification setting, where Y = {0, 1}, while (N2) is more common in the regression on a random design setting, where Y = R.

Combination of assumptions.

In the sequel, we will conveniently refer by (CS1) to the set of assumptions (D1), (S1), (N1) or (N2). As detailed below in Section 3, configuration (CS1) is comparable to what is customary in the regression on a random design setting.

Our results

Assuming at first A to be known, we introduce a novel nonparametric estimator η @ of η built upon local regressions against a multi-resolution analysis (MRA) of L 2 (R d , λ) and show that, under (CS1), it is adaptive nearly minimax optimal over a wide generalized Lipschitz scale and across the wide range of losses L p (E, µ), p ∈ [1, ∞). We subsequently show that these results generalize to the case where A is unknown but belongs to a large class of (eventually disconnected) subsets of R d , provided we modify the estimator η @ accordingly. We denote by η this latter estimator and prove that η can be used to build an adaptive nearly minimax optimal plug-in classifier, which can reach super-fast rates under a margin assumption. The above results essentially hinge on an exponential upper-bound on the probability of deviation of η @ from η at a point, as detailed in Theorem 7.1. These results either improve on the current literature or are interesting in their own right for the following reasons. 1) They show that it is possible to use MRAs to construct an adaptive nearly minimax optimal estimator η @ of η under the sole set of assumptions (CS1). More precisely, our results (i) hold in any dimension d; (ii) over the wide range of L p (E, µ)-losses, p ∈ [1, ∞); (iii) and a large Lipschitz scale; (iv) and do not require any assumption on µ beyond (D1). It is noteworthy that, in contrary to most alternative MRA-based estimation methods, no smoothness assumption on µ is needed. 2) From a computational perspective, η @ outperforms other estimators of η under (D1) since it takes full advantage of the lattice structure of the underlying MRA. In particular it requires at most as many regressions as there are data points to be computed everywhere on E, while alternative kernel estimators must be recomputed at each single point of E. We illustrate this latter feature through simulation. 3) Furthermore, and in contrary to alternative MRA-based estimators, the local nature of η @ allows to relax the assumption that A is known. This latter configuration allows for µ to cancel on E as long as it remains bounded on its support A, which is particularly appropriate to the supervised binary classification problem under a margin assumption. 4) In the regression on a random design setting, η @ bridges in fact the gap between usual linear wavelet estimators and alternative kernel estimators, such as the LPE. On the one hand, η @ inherits its computational efficiency from the lattice structure of the underlying MRA. On the other hand, it features similar theoretical performances as the LPE in the random design setting. In particular, it remains a (locally) linear estimator of the data (modulo a spectral thresholding of the local regression matrix), and cannot discriminate finer smoothness than the one described by (generalized) Lipschitz spaces. Here is the paper layout. We start by a literature review in Section 3. We give a hand-waving introduction to the main ideas that underpin the local multi-resolution estimation procedure in Section 4. We define notations that will be used throughout the paper and introduce MRAs in Section 5. Our actual estimation procedure is described in Section 6 and the results are detailed in Section 7. We show how these results can be fine-tuned under additional assumptions in Section 8. Assumption (S1) is relaxed and the properties of η are detailed in Section 9. We show how these latter results spread to the classification setting in Section 10. Results of a simulation study with η @ under (CS1) are given in Section 11. Proofs of the regression results can be found in Section 12. The proofs of the classification results are simple modifications of the proofs given in [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF] and thus detailed in the Appendix in Section 13. In addition, the Appendix contains a detailed review of generalized Lipschitz spaces and MRAs in Section 13.1 and Section 13.2, respectively.

Literature review

Both the regression on a random design problem and the classification problem have a longstanding history in nonparametric statistics. We will therefore limit ourselves to a brief account of the corresponding literature that is relevant to the present paper.

Classification with plug-in classifiers

Let us start with a review of some of the classification literature dedicated to plug-in classifiers. The seminal work [START_REF] Marron | Optimal rates of convergence to the Bayes risk in nonparametric discrimination[END_REF] showed that plug-in rules are asymptotically optimal. It has been subsequently pointed out in [START_REF] Mammen | Smooth discrimination analysis[END_REF] that the classification problem is in fact only sensitive to the behavior of P X,Y near the boundary line M := {τ ∈ E : η(τ ) = 1/2}. So that assumptions on the behavior of P X,Y away from this boundary are in fact unnecessary. Subsequent works such as [START_REF] Audibert | Classification under polynomial entropy and margin assumptions and randomized estimators[END_REF] have shown that convex combinations of plug-in classifiers can reach fast rates (meaning faster than n -1/2 , and thus faster than nonparametric estimation rates). More recently, it has been shown in [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF] that plug-in classifiers can reach super fast rates (that is faster than n -1 ) under suitable conditions. All these results are derived under some sort of smoothness assumption on the regression function η (see [START_REF] Yang | Minimax nonparametric classification. I. rates of convergence[END_REF]) and a margin assumption (MA) (see Section 10 for details). This latter assumption clarifies the behavior of P X,Y in a neighborhood of M and kicks in naturally through the computation

T (h n ) ≤ δP(0 < |2η(X) -1| ≤ δ) + E|η n (X) -η(X)|1 {|ηn(X)-η(X)|>δ} ,
where δ is chosen such that it balances the two terms on the rhs. Finally, [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF] exhibited optimal convergence rates under smoothness and margin assumptions and showed that they are attained with plug-in classifiers. Let us now turn to the regression on a random design problem.

Regression on a random design with wavelets

First results on multi-resolution analysis (MRA) and wavelet bases (see [START_REF] Mallat | Multiresolution approximations and wavelet orthonormal bases of L 2[END_REF][START_REF] Meyer | Wavelets and operators[END_REF]) emerged in the nonparametric statistics literature in the early 1990's (see [START_REF] Kerkyacharian | Density estimation in Besov spaces[END_REF][START_REF] Donoho | Ideal spatial adaptation by wavelet shrinkage[END_REF][START_REF] David | De-Noising by Soft-Thresholding[END_REF][START_REF] Donoho | Wavelet shrinkage: Asymptotia?[END_REF][START_REF] Donoho | Density estimation by wavelet thresholding[END_REF]). It has been proved that, under (CS1) and in the particular case where µ is the uniform distribution on E, thresholded wavelet estimators of η are nearly minimax optimal over a wide Besov scale and range of L p (E, µ)-losses (see [START_REF] Delyon | On minimax wavelet estimators[END_REF]). In order to leverage on the power of MRAs and associated wavelet bases, several authors attempted to transpose these latter results to more general design densities µ. This, however, led to a considerable amount of difficulties. The literature relative to the study of wavelet estimators on an unknown random design breaks down into two main streams. (i) The first one aims at constructing new wavelet bases adapted to the (empirical) measure of the design (see [START_REF] Kohler | Nonlinear orthogonal series estimates for random design regression[END_REF][START_REF] Kohler | Multivariate orthogonal series estimates for random design regression[END_REF][START_REF] Véronique Delouille | Nonparametric stochastic regression with design-adapted wavelets[END_REF][START_REF] Sweldens | The lifting scheme: a custom-design construction of biorthogonal wavelets[END_REF]). (ii) The second one aims at coming up with new algorithms to estimate the coefficients of the expansion of η on traditional wavelet bases (see [START_REF] Antoniadis | Random design wavelet curve smoothing[END_REF][START_REF] Hall | Interpolation methods for nonlinear wavelet regression with irregularly spaced design[END_REF][START_REF] Kovac | Extending the scope of wavelet regression methods by coefficientdependent thresholding[END_REF][START_REF] Michael | On the efficiency of wavelet estimators under arbitrary error distributions[END_REF][START_REF] Sardy | Wavelet shrinkage for unequally spaced data[END_REF]). The present paper belongs to this second line of research. As described in [START_REF] Hall | Interpolation methods for nonlinear wavelet regression with irregularly spaced design[END_REF], the success of the LPE on a random design results from the fact that it is built as a "ratio", which cancels out most of the influence of the design. In a wavelet context, a first suggestion has therefore been to use the ratio estimator of η (see [START_REF] Antoniadis | Wavelet regression for random or irregular design[END_REF][START_REF] Pensky | On non-equally spaced wavelet regression[END_REF], for example), well known from the statistics literature on orthogonal series decomposition (see [START_REF] Greblicki | A classification procedure using the multiple fourier series[END_REF][START_REF] Greblicki | Fourier and hermite series estimates of regression functions[END_REF] and [START_REF] Devroye | A probabilistic theory of pattern recognition[END_REF]Chap. 17] and the references therein). Roughly speaking, the ratio estimator is the wavelet equivalent of the Nadaraya-Watson estimator (see [START_REF] Nadaraya | On estimating regression[END_REF][START_REF] Watson | Smooth regression analysis[END_REF]). It is elaborated on the simple observation that η(x) = η(x)µ(x)/µ(x) for all x ∈ A, where both g(.) = η(.)µ(.) and µ(.) are easily estimated via traditional wavelet methods. The ratio estimator relies thus unfortunately on the estimation of µ itself and must therefore assume as much smoothness on µ as on η.

To address that issue, an other approach has been introduced in [START_REF] Cai | Wavelet shrinkage for nonequispaced samples[END_REF][START_REF] Kerkyacharian | Regression in random design and warped wavelets[END_REF]. They work with d = 1 and take E to be the unit interval [0, 1]. Their approach relies on the wavelet estimation of η •G -1 , where G stands for the cumulative distribution of the design and G -1 for its generalized inverse. Results are therefore stated in term of regularity of f •G -1 . Unfortunately, this method does not readily generalize to the the multi-dimensional case, where G admits no inverse. Finally, [START_REF] Baraud | Model selection for regression on a random design[END_REF] obtains adaptive near-minimax optimal wavelet estimators over a wide Besov scale under (CS1) by means of model selection techniques. His results are hence valid for the L 2 (E, µ)-loss only. Other relevant references that proceed with hybrid estimators (LPE and kernel estimator or LPE and wavelet estimator) are [START_REF] Gaïffas | Sharp estimation in sup norm with random design[END_REF] and [START_REF] Zhang | Wavelet threshold estimation of a regression function with random design[END_REF]. They both work under (CS1), with d = 1 and assume that µ is at least continuous.

A primer on local multi-resolution estimation under

(CS1) In order to fix the ideas, let us now give a hand-waving introduction to the local multi-resolution estimation method. Throughout the paper, we will work with r-MRAs of L 2 (R d , λ), for some r ∈ N, consisting of nested approximation spaces V j ⊂ V j+1 built upon compactly supported scaling functions (see Section 5.2 and [START_REF] Daubechies | Ten lectures on wavelets[END_REF][START_REF] Mallat | A wavelet tour of signal processing: the sparse way[END_REF][START_REF] Cohen | Numerical analysis of wavelet methods[END_REF][START_REF] Härdle | Wavelets, approximation and statistical applications[END_REF]). Under the assumption that η belongs to the generalized Lipschitz ball L s (E, M) of radius M, the essential supremum of the remainder of the orthogonal projection P j η of η onto V j decreases like 2 -js (see Section 13.1). The regression function η can therefore be legitimately approximated by P j η. As an element of V j , P j η may be written as an infinite linear combination of scaling functions at level j. In particular, there exists a partition F j of E into hypercubes of edge-length 2 -j such that, for all H ∈ F j and all x ∈ H, we can write P j η(x) = k∈S j (H) α j,k ϕ j,k (x), where S j (H) stands for a finite subset of Z d (see Figure 1). This leaves us in turn with the estimation of coefficients (α j,k ) k∈S j (H) for all H ∈ F j , which is achieved by least-squares and provides us with the estimator η @ j of η on H. It is noteworthy that the local estimator η @ j of η is exclusively built upon scaling functions and does not require the estimation of wavelet coefficients. In particular, it does not involve any sort of wavelet coefficient thresholding. To the best of the author knowledge, this is the first time that this local estimation procedure is proposed and studied from both a theoretical and computational perspective. In addition, we show that Lepski's method (see [START_REF] Lepski | Optimal spatial adaptation to inhomogeneous smoothness: an approach based on kernel estimates with variable bandwidth selectors[END_REF], for example) can be used to adaptively choose the resolution level j. Notice that Lepski's method has already been used in a MRA setting in [START_REF] Picard | Adaptive confidence interval for pointwise curve estimation[END_REF]. In what follows, we detail the local multi-resolution estimation method and establish the near minimax optimality of η @ . 5 Notations

R 0 H = 2 -j [0, 1] V j d = 1 ϕ j,k 1 ϕ j,k 5 2 -j Z

Preliminary notations

In the sequel, we will denote by B p (z, ρ) the closed ℓ p -ball of R d of center z and radius ρ. More generally, we adopt the following notations: for any subset S of a topological space E, Closure(S) will stand for its closure, Inter(S) for its interior, S c for its complement in E and ∂S = Closure(S) ∩ Inter(S) c for its boundary. Besides, for any two S 1 , S 2 ⊂ R d , we will denote the relative complement of S 2 in S 1 by S 1 \S 2 (= S 1 ∩ S c

2 ) and their symmetric difference S 1 \S 2 ∪ S 2 \S 1 by S 1 ∆S 2 . For any subset S of R d , z ∈ R d and τ ∈ R + , we will write z + S and τ S to mean the sets {z + u : u ∈ S} and {τ u : u ∈ S}, respectively. Finally, given a set (of functions) R, SpanR will denote the set of finite linear combinations of elements of R. For any p ∈ N, vectors v of R p will be seen as elements of M p,1 , that is matrix with p rows and one column. For any two u, v ∈ R p , u, v will denote their Euclidean scalar product. In addition, for any p, q ∈ N and M ∈ M p,q , M t will stand for the transpose of M. For any two matrices M, P , M • P will denote their matrix product when it makes sense. [M] k,ℓ and [M] k,• will respectively stand for the element of M located at line k, column ℓ and the k th row of M. Finally, M S will denote the spectral norm of M (see [29, §5.6.6]). We denote by ⌊z⌋ the integer part of z ∈ R defined as max{a ∈ Z : a ≤ z}. More generally, given z ∈ R d , we write ⌊z⌋ the integer part of z, meant in a coordinate-wise sense. In the same way, we denote by ⌈z⌉ the smallest integer greater than z (in a coordinate-wise sense). We write rhs (resp. lhs) to mean right-(resp. left-) hand-side and sometimes write := to mean equal by definition. Throughout the paper, we will refer to constants independent of n as absolute constants and c, C will stand for absolute constants whose value may vary from line to line. For any two sequences a n , b n of n, we will write a n b n to mean a n ≤ Cb n for some absolute constant C and a n ≈ b n to mean that there exist two constants c, C independent of n such that cb n ≤ a n ≤ Cb n .

The polynomial reproduction property

In what follows, we will exclusively consider MRAs built upon Daubechies' scaling functions ϕ j,k (see Section 13.2). Given a natural integer r, we will refer by r-MRA to a MRA whose nested approximation spaces V j reproduce polynomials up to order r -1. Daubechies' scaling functions are appealing in the estimation framework since they are compactly supported and have minimal volume supports among scaling functions that give rise to r-MRAs. Recall that a r-MRA can explain Lipschitz smoothness s for any s ∈ (0, r). Obviously, the usefulness of the 1-MRA, also known as the Haar MRA, is fairly limited when dealing with the estimation of smooth functions. However, the simple geometry of the Haar scaling function brings a great deal of simplification in the proofs, which will allow us to highlight the key points of our estimation procedure and hopefully clarify our arguments. This is the unique reason why we have treated the two cases r = 1 and r ≥ 2 distinctly in the proofs. The reader is referred to the Appendix in Section 13.2 for a detailed review of MRAs of R d .

General notations

Consider the Daubechies' r-MRA of L 2 (R d , λ) built upon Daubechies' scaling function ϕ, as described in Section 13.2. We will denote by Suppϕ j,k = {τ ∈ R d : ϕ j,k (τ ) > 0} the support of ϕ j,k . Recall that Suppϕ = [-(r -1), r] d . To alleviate notations, we will write ϕ k in place of ϕ 0,k and ϕ j in place of ϕ j,0 . Notice that Closure(Suppϕ j,k ) is in fact a closed hyper-cube of R d whose corners lie on the lattice 2 -j Z d (see Section 13.2). Moreover, for any x ∈ A, write

S j (x) = {ν ∈ Z d : x ∈ Suppϕ j,ν }.
Furthermore, we write F j := 2 -j ((0, 1) d +Z d )∩E. It defines a partition of E into 2 jd hypercubes of edge length 2 -j , modulo a λ-null set. For the sake of concision, we write R = 2r -1 in the sequel. We have the following proposition, whose proof is straightforward and thus left to the reader.

Proposition 5.1. S j verifies the following properties, 1. S j is constant on each element H ∈ F j . We will denote by S j (H) its value on H.

Moreover, for any two

H 1 , H 2 ∈ F j , H 1 = H 2 , S j (H 1 ) differs from S j (H 2 ) by at least one element. 3. Finally, for any H ∈ F j , #S j (H) = R d
It is a direct consequence of Proposition 5.1 that in the case where r = 1, we have #S j (H) = 1 for all H ∈ F j . We denote its single element by ν(H). It is in fact easy to show that ν(H) = ⌊2 j x⌋ for any x ∈ H. For any H ∈ F j , we write

α H = (α j,ν ) ν∈S j (H) ∈ R R d , ϕ H (.) = (ϕ j,ν (.)1 H (.)) ν∈S j (H) ∈ R R d .
and denote by Y H = (Y i 1 H (X i )) 1≤i≤n . Moreover, we write I H = {i : X i ∈ H} and n H = #I H .

6 Construction of the local estimator η @ Assume we are under (CS1) and work with the Daubechies' r-MRA of L 2 (R d , λ) (see Section 13.2). The estimation procedure is local, so that we start by selecting a point x ∈ A (see Section 13.3 for a technical remark). By construction, there exists H ∈ F j such that x ∈ H. We want to estimate η at point x. As detailed in Section 13.2, an estimator of η can be reduced to an estimator of the orthogonal projection P j η of η onto V j , modulo an error R j η, such that |R j η| ≤ M2 -js when η belongs to the generalized Lipschitz ball L s (E, M) of radius M. Now, we can write

P j η(x) = k∈Z d α j,k ϕ j,k (x) = k∈S j (H) α j,k ϕ j,k (x) = α H , ϕ H (x) .
This leaves us with exactly R d coefficients α j,ν , ν ∈ S j (H) to estimate, which are valid for any x ∈ H. We evaluate these coefficients by least-squares. Denote by B H ∈ M n,R d the matrix whose rows are the vectors ϕ H (X i ) t for 1 ≤ i ≤ n. Let us denote by k 1 , . . . , k R d the elements of S j (H). Then we choose

α ⋄ H ∈ arg min a∈R R d n i=1   Y i - R d t=1 a t ϕ j,kt (X i )   2 1 H (X i ) = arg min a∈R R d Y H -B H • a 2 ℓ 2 (R n ) , (4)
where we set α ⋄ H = 0 if the arg min above contains more than one element. Let us write

Q H = B t H • B H /n ∈ M R d ,R d .
As is well known, when Q H is invertible, the arg min on the rhs of eq. ( 4) admits one single element which writes as follows,

α ⋄ H = Q -1 H • 1 n B t H • Y H . (5)
Naturally, we will denote the corresponding estimator of P j η at point x by η ⋄ H (x) = α ⋄ H , ϕ H (x) . We now introduce a thresholded version of η ⋄ H based on the spectral thresholding of Q H . We denote by λ min (Q H ) the smallest eigenvalue of Q H in the case where r ≥ 2, when Q H is actually a matrix, and Q H itself in the case where r = 1, when it is a real number. Furthermore, we define

η @ H (x) = 0 if π -1 n > λ min (Q H ) η ⋄ H (x) otherwise , ( 6
)
where π n is a tuning parameter. In practice, and unless otherwise stated, we choose π n = log n. Moreover, we assume throughout the paper that n is large enough so that π -1 n ≤ min( g min 2 , 1), where, for reasons that will clarified later, we have denoted,

g min := µ min c min , (7)
and c min stands for the strictly positive constant defined in the proof of Proposition 12.4. Ultimately, the estimator η @ j of P j η is defined as,

η @ j (x) = H∈F j η @ H (x)1 H (x), x ∈ E. ( 8
)
7

The results

Let r be a natural integer, denote by P the set of all distributions on E × Y and write

P(CS1, H r s ) := {P ∈ P : (CS1) and (H r s ) hold true}. (9)
Furthermore, we define j r , j s , J and t(n) such that,

2 jr = ⌊n 1 2r+d ⌋, 2 js = ⌊n 1 2s+d ⌋, 2 Jd = ⌊nt(n) -2 ⌋, t(n) 2 = κπ 2 n log n,
where κ is a positive real number to be chosen later. In addition, we write J n = {j r , j r + 1, . . . , J -1, J}. Notice that j s strikes the balance between bias and variance in the sense that, for log n ≥ (2s + d) log 2 and s ∈ (0, r), one has got

n -1 2 2 js d 2 ≤ 2 -jss , (10a) 2
-jss ≤ 2 r+ d 2 2 js d 2 n -1 2 , (10b) 2 -jss ≤ 2 r n -s 2s+d . ( 10c
)
Throughout the sequel, we assume that n is large enough so that the latter inequalities hold true. Our first result gives an upper bound on the probability of deviation of η @ j form η at a point x ∈ A.

Theorem 7.1. Fix r ∈ N and assume we are under (CS1) and (H r s ). Recall that η @ j is defined in eq. ( 8). Then, for all j ∈ J n , all δ > 2M2 -js max(1, 3π n R d µ max ) and all x ∈ A, we have got

sup P∈P(CS1,H r s ) P ⊗n (|η(x) -η @ j (x)| ≥ δ) ≤ 2R 2d exp -n2 -jd π -2 n 2µ max R 4d + 4 3 R 2d π -1 n 1 {δ≤M } + R d Λ δ2 -j d 2 2π n R d , ( 11
)
where Λ is defined as follows,

Λ(δ) =                            2 exp - nδ 2 18K 2 µ max + 4K2 j d 2 δ , under (N1) 1 ∧ 2σ(µ max + 2 j d 2 δ) 1 2 δ √ 2πn exp - nδ 2 σ -2 µ max + 2 j d 2 δ +2 exp - nδ 2 2µ max + 4 3 2 j d 2 δ , under (N2)
As a consequence of the above theorem, we can deduce the (near) minimax optimality of η @ js over generalized Lipschitz balls.

Corollary 7.1. Fix r ∈ N and assume we are under (CS1) and (H r s ). Then, for any p ∈ [1, ∞) and j ∈ J n , one has got

sup P∈P(CS1,H r s ) E ⊗n η -η @ j p Lp(E,µ) ≤ C(p)π p n max 2 -js , 2 j d 2 √ n p , (12)
where η @ j and C(p) are defined in eq. ( 8) and Proposition 12.1 below, respectively. A fortiori, when s is known, we can choose j = j s and apply eq. (10a) and eq. (10c) above to obtain

sup P∈P(CS1,H r s ) E ⊗n η -η @ js p Lp(E,µ) ≤ C(p)2 rp π p n n -sp 2s+d .
This, together with the lower-bound of Theorem 7.3, proves that η @ js is (nearly) minimax optimal over the generalized Lipschitz ball L s (E, M) of radius M.

The next Theorem shows that the approximation level j can be determined from the data D n so that we obtain adaptation over a wide generalized Lipschitz scale.

Theorem 7.2. Fix r ∈ N and assume we are under (CS1) and (H r s ). We define

g(j, k) := 2 j d 2 √ n t(n) + 2 k d 2 √ n t(n) , j @ (x) := inf{j ∈ J n : |η @ j (x) -η @ k (x)| ≤ g(j, k), ∀k ∈ J n , k > j}, x ∈ A, where η @
j is defined in eq. ( 8) and inf

∅ = max(J n ) = J. If κ is chosen large enough, meaning κ ≥ p 2 C -1 9
, where C 9 is defined in Proposition 12.2, then we obtain

sup P∈P(CS1,H r s ) E ⊗n η @ j @ (.) (.) -η(.) p Lp(E,µ) ≤ 5 p 2 rp t(n) p n -sp 2s+d .
So that η @ j @ (.) (.) is a nearly minimax adaptive estimator of η over the generalized Lipschitz scale 0<s<r L s (E, M).

Finally, we prove that η @ is indeed (nearly) minimax optimal by giving the corresponding lower-bound result.

Theorem 7.3. Assume we are under (CS1) and (H r s ). We write inf θn the infinimum over all estimators θ n of η, that is all measurable functions of the data D n . Then, for d ≥ 1, s > 0, we have, for all 1 ≤ p < ∞,

inf θn sup P∈P(CS1,H r s ) E ⊗n θ n -η p Lp(E,µ) n -sp 2s+d .
The next section shows how these results can be improved in the case where we benefit from additional information on µ or η.

Refinement of the results

As can be seen from Corollary 7.1 and Theorem 7.2 above, π n appears as a multiplicative factor in the upper-bounds and thus deteriorates them by a multiplicative log n term. However, this needs not be the case, and under appropriate additional assumptions, π n can be chosen to be a constant. Consider indeed the following two assumptions. (O1) We know µ * min ∈ R, such that 0 < µ * min ≤ µ min . (O2) We know a finite positive real number M such that η L∞(E,λ) ≤ M. Under (O1), we know a lower bound µ * min of µ min , and therefore a lower bound g * min of g min (see eq. ( 7)). Under (O1), we will thus choose π -1 n = min( g * min 2 , 1). It is straightforward to show that Theorem 7.1 is still valid with this new value of π n (see Remark 12.1 in the proof of Theorem 7.1), and thus all the subsequent results follow as well. Under (O2), we know an upper bound M of the essential supremum of η on E. In that case, we redefine

η @ H (x) = T M (η ⋄ H (x))1 {λ min (Q H )>0} , (13)
where, for any z ∈ R, we have written T M (z) = z1 {|z|≤M } + Msign(z)1 {|z|>M } . Once again, it is straightforward to show that Theorem 7.1 is now valid with π -1 n = min( g min 2 , 1) and 2M in place of M in the indicator function on the rhs of eq. ( 11) (see Remark 12.1 in the proof of Theorem 7.1), and thus all the subsequent results follow as well. Notice that π n is an absolute constant under (O1) and (O2), while it is an increasing sequence of n to be fine-tuned by the statistician otherwise. Hence π n appears to be the price to pay for not knowing a lower bound of µ min or an upper bound of the essential supremum of η on E. 9 Relaxation of assumption (S1)

The problem

Now, we would like to relax assumption (S1) and allow for A to be an unknown subset of E, eventually disconnected. Under (CS1), the success of η @ stems from the fact that it is constructed upon an approximation grid of the form 2 -j Z d ∩ [0, 1] d , whose edges coincide exactly with the boundary of A. In the case where A is unknown, some cells of the lattice might straddle the boundary of A and thus require a new treatment. In order to handle this new configuration, we will need to make a smoothness assumption on the boundary of A and allow for the estimation cells to move with the point at which we want to estimate η. Ultimately, we devise a new estimator η of η which is built upon a moving approximation grid. In fact, this new estimation method ensures that the point x at which we want to estimate η always belongs to a cell H of F j at resolution level j, whose center belongs to A. This will ensure that local regressions performed on cells that straddle the boundary of A are still meaningful. The smoothness assumption we will make on A might be compared to the support assumption made in [4, eq. (2.1)] in the classification context. In substance, it is assumed in [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF] that A is locally ball-shaped to be compatible with the ball-shaped support of the LPE kernel, which they use to estimate η. In our case, we perform estimation with multi-dimensional scaling functions whose supports are cube-shaped and will thus assume that A is locally cube-shaped.

Smoothness assumption on A

Let us now make these informal arguments more precise. To that end we introduce assumption (S2) as an alternative to (S1) above. Fix an absolute constant m 0 ∈ (0, 1) and recall that 2 js = ⌊n 1 2s+d ⌋. With these notations, (S2) goes as follows,

2 j (A -x) B ∞(zx,m) j ≥ j s 0 2 j (A -x) B ∞(zx,m) j ≥ j s
A js := {A ⊂ R d :∃m ≥ m 0 , ∀x ∈ A, ∃z x ∈ R d , 0 ∈ B ∞ (z x , m) ⊂ 2 js (A -x)},
In words, (S2) means that if we zoom close enough to any x ∈ A, we can find a hypercube B ∞ (z x , m) that contains x and is a subset of A. Notice readily that for all j 1 ≥ j 2 , the component of 2 j 2 (Ax) that contains 0 is a subset of the component of 2 j 1 (Ax) that contains 0, so that A j 2 ⊂ A j 1 . Therefore A js grows with n and shrinks with s. Of course, (S1) is a particular case of (S2). Setting (S2) allows A to be unknown and belong to a wide class of subsets of R d , eventually disconnected (see Figure 2). In the sequel, we will conveniently refer by (CS2) to the set of assumptions (D1), (S2), (N1) or (N2).

Moving local estimation under (CS2)

As detailed above, η is obtained by local regression on a moving approximation grid. Let us describe the construction of η more precisely. First of all, we split the sample into two pieces. For simplicity, let us assume that we dispose of 2n data points. The first half of the sample points, which we denote by

D ′ n = {(X ′ i , Y ′ i ), i = 1, . . . ,
n}, will be used to identify the support A of µ, while the second half, which we denote by D n = {(X i , Y i ), i = 1, . . . , n}, will be used to estimate the scaling functions coefficients by local regressions. Let us denote by H 0 the cell 2 -j [0, 1] d of the lattice 2 -j Z d at resolution j. And denote by H 0 (x) the same cell centered in x, that is

H 0 (x) = x -2 -j-1 + 2 -j [0, 1] d . Then, the construction of η j (x) at a point x ∈ R d goes as follows. (i) If none of the design points (X ′ i ) of the sample D ′
n lie in H 0 (x), then take η (x) = 0. (ii) If one or more design points of the sample D ′ n lie in H 0 (x), we select one of them and denote it by X ′ ix (the selection procedure is of no importance beyond computational considerations). By construction, x belongs to the cell H 0 (X ′ ix ) centered in X ′ ix ∈ A. Since X ′ ix belongs to A, it makes sense to perform a local regression on H 0 (X ′ ix ) with the sample points D n , which gives rise to an estimator η of η valid at any point of H 0 (X ′ ix ) ∩ A. It is noteworthy that this procedure uses the sample D ′ n to identify the support A of µ. Interestingly, the above estimation procedure requires at most as many regressions as there are data points in D ′ n to return an estimator η of η at every single point x ∈ A. It is therefore computationally more efficient than any other kernel estimator, such as the LPE. The computational performance of η can in fact be further improved in the sense that the local regression on the cell H 0 (X ′ i ) can be omitted if the cell H 0 (X ′ i ) is itself included in the union of cells centered at other design points of D ′ n . In particular, we can choose X ′ ix to be a design point X ′ i of D ′ n that belongs to H 0 (x) and for which a local regression has already been performed, if it exists, or any one of the X ′ i that belong to H 0 (x) otherwise. Intuitively, the computational efficiency of η stems from the fact that the design points (X ′ i ) provide some valuable information on the unknown support A of µ, which can be exploited under (CS2). In particular, and as we will see below, (D1) guarantees that the design points of D ′ n populate A densely enough so that, as long as j ≤ J, the cells H 0 (X ′ i ), 1 ≤ i ≤ n, form a cover of A, modulo a set whose µ-measure decreases almost exponentially fast toward zero with n.

Construction of the local estimator η

Assume we are under (S2) and work with the Daubechies' r-MRA of L 2 (R d , λ). Obviously, shifting the approximation grid is equivalent to shifting the data points (X i ) of D n and keeping the lattice fixed. For ease of notations and clarity, we adopt this second point of view. In order to compute η at a point x ∈ H 0 (X ′ ix ) ∩ A, we want to shift the design points in such a way that X ′ ix falls right in the middle of H 0 . In other words, we want X ′ ix to be shifted at point 2 -j-1 ∈ R d (whose coordinates are worth 2 -j-1 ∈ R). This corresponds to the change of variable

X i = X i -(X ′ ix -2 -j-1
), where we have denoted by X i and X i the representations of a same data point in the canonical and shifted coordinate systems of R d , respectively. In order to compute η at point x ∈ H 0 (X ′ ix ) ∩ A, it is therefore enough to perform a local regression on H 0 against the shifted data points,

D x = {( X i , Y i ), i = 1, . . . , n}.
For the sake of concision, we will denote by u = u -(X ′ ix -2 -j-1 ) the coordinate representation of a point u in the shifted coordinate system of R d . Let us denote by k 1 , . . . , k R d the elements of S j (H 0 ). With these notations, eq. ( 4) must be corrected and written as

α ⋄ H 0 ∈ arg min a∈R R d n i=1   Y i - R d t=1 a t ϕ j,kt ( X i )   2 1 H ( X i ), (14)
where we set α ⋄ H 0 = 0 if the arg min above contains more than one element. The notations introduced in Section 5.3 can be updated to this new setting as follows. B H 0 stands now for the random matrix of M n,R d whose rows are the ϕ H 0 ( X i ) t , i = 1, . . . , n. In addition, we recall that we have defined

Q H 0 = B t H 0 • B H 0 /n ∈ M R d ,R d . Its coefficients write thus as [Q H 0 ] ν,ν ′ = 1 n n i=1 ϕ j,ν ( X i )ϕ j,ν ′ ( X i )1 H 0 ( X i ), ν, ν ′ ∈ S j (H 0 ).
Notice here that S j (H 0 ) = {ν ∈ Z d : 2 -1 ∈ Suppϕ ν }, which neither depends on j nor x. Therefore, and for later reference, we denote

S := {ν ∈ Z d : 2 -1 ∈ Suppϕ ν }, (15)
In addition, if we write

Y H 0 = (Y i 1 H 0 ( X i ))
1≤i≤n , then eq. ( 5) still holds true when the solution to eq. ( 14) is unique. So that, for all x ∈ H 0 (X ix ) ∩ A, we can write η ⋄ H 0 ( x) = α ⋄ H 0 , ϕ H 0 ( x) . Finally eq. ( 6) remains valid with X i replaced by X i and H by H 0 , η @ H 0 redefined as η H 0 and g min redefined as

g min = µ min c min , (16)
where c min is the strictly positive constant defined in Lemma 12.1 below. So that ultimately, the estimator η j of P j η at a point x ∈ R d writes as

η j (x) = η H 0 ( x), x ∈ E. (17)
Notice that by contrast with eq. ( 8) above, the sum over the hypercubes of F j has disappeared. This is due to the fact that the approximation grid moves with x so that we end up virtually always performing estimation on the same hypercube H 0 .

The results

Interestingly, η still verifies similar results as the ones described in Section 7. To be more precise, recall that we work with a sample of size 2n broken up into two pieces D n and D ′ n of size n. Let us redefine J n so that J n = {j s , j s + 1, . . . , J -1, J} where 2 js = ⌊n 1 2s+d ⌋. Then, we obtain the following result in place of Theorem 7.1.

Theorem 9.1. Fix r ∈ N and assume we are under (CS2) and (H r s ). Recall that η j is defined in eq. ( 17). Then, for all j ∈ J n , all δ > 2M2 -js max(1, 3π n R d µ max ) and all x ∈ A, we have got

sup P∈P(CS2,H r s ) P ⊗n (|η(x) -η j (x)| ≥ δ) ≤ 3R 2d exp -n2 -jd π -2 n 2µ max R 4d + 4 3 R 2d π -1 n 1 {δ≤M } + R d Λ δ2 -j d 2 2π n R d ,
where Λ has been defined in Theorem 7.1.

Left aside the fact that η is constructed upon a sample of size 2n, the sole difference with the result of Theorem 7.1 is that the leading constant in front of the exponential on the second line has changed from 2R d to 3R d . Furthermore, it is straightforward to deduce from Theorem 9.1 results similar to Corollary 7.1, Theorem 7.2 and Theorem 7.3, and a fortiori the refined results obtained in Section 8, for η under (CS2). The proofs of these results for η under the set of assumptions (CS2) follow, for the most part, exactly the same lines as the proofs given for η @ under (CS1). Details can be found in Section 12.2.

Classification via local multi-resolution projections

Recall from [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF] that the margin assumption can be written as, (MA) There exist constants C * > 0 and ϑ ≥ 0 such that

P(0 < |2η(X) -1| ≤ t) ≤ C * t ϑ , ∀t > 0.
The binary classification setting corresponds to (CS2), under assumptions (N1) and (O2).

Notice besides that we have K = 1 in (N1) and M = 1 in (H r s ). Since we are under (O2), it follows from Section 8 that π n = π 0 = min(1, g min 2 ) is independent of n and η is capped at M = 1 as in eq. ( 13). For the sake of coherence, we denote by j the adaptive resolution level built upon η , as described in Theorem 7.2, and define P(CS2, H r s ) by analogy with eq. ( 9) above. Finally, we recall that η is built upon a sample of size 2n split into two sub-samples D n and D ′ n of size n. In this context, we have the following Proposition.

Proposition 10.1. Fix r ∈ N and assume we are in the binary classification setting.

Assume moreover that (H r s ) holds true. Then, for all j ∈ J n , all x ∈ A and any

1 ≥ δ > 2 2 -js max(1, 3π 0 R d µ max ), we have got sup P∈P(CS2,H r s ) P ⊗n (|η(x) -η j (x)| ≥ δ) ≤ 3R 2d n -κC ′ 10 + 2R d exp(-C 10 a n (j)δ 2 ), (18)
and for

1 ≥ δ > 62 r t(n)n -s 2s+d , sup P∈P(CS2,H r s ) P ⊗n (|η(x) -η j (x) (x)| ≥ δ) ≤ 11R 2d (log n) 2 n -κC ′ 6 + 2R d exp(-C 11 n 2s 2s+d δ 2 ), (19)
where we have written a n (j) := n2 -jd and the constants C ′ 6 , C ′ 10 , C 10 , C 11 are all defined in the proof, eq. ( 38) and eq. ( 39).

The proof of this latter result is a straightforward consequence of Theorem 7.1 and Theorem 7.2. It is detailed in the Appendix. All the results that follow can be easily derived from [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF]. Their proofs are therefore not reported in this Section but delayed to the Appendix as well. The first result derives an upper-bound on the classification loss from an upper bound on the probability of deviation of a classifier η n from η at a point x ∈ A. It is similar to [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF]Theorem 3.1] in scope and proof.

Theorem 10.1. Fix r ∈ N and assume we are in the binary classification setting. Assume moreover that (H r s ) and (MA) hold true. Let η n be an estimator of η and assume there exists δ n ∈ (0, 1) and strictly positive constants C 11 , C 12 , C 13 such that, for all 1 ≥ δ ≥ δ n and almost all x ∈ A, we have sup P∈P(CS2,H r s ,MA)

P ⊗n (|η n (x) -η(x)| ≥ δ) ≤ C 11 b n + C 12 exp(-C 13 a n δ 2 ), (20)
for some positive sequences a n and b n . Consider the plug-in classifier h n (.) := 1 {ηn(.)≥

T (h n ) ≤ 2C * δ 1+ϑ n 1 + C 11 b n δ -(1+ϑ) n + C 12 k≥1 2 k(1+ϑ) exp(-C 13 a n δ 2 n 2 2(k-1) ) .
As a consequence of Theorem 10.

T (h js ) ≤ C 15 n -s 2s+d (1+ϑ) , as soon as κ > 1+ϑ 2C ′ 10 , (21)
sup

P∈P(CS2,H r s ,MA) T (h j ) ≤ C 16 (log n) 1+ϑ 2 n -s 2s+d (1+ϑ) , as soon as κ > 1+ϑ 2C ′ 6 , (22)
where C ′ 6 , C ′ 10 have been defined in Proposition 10.1 above and C 15 , C 16 are defined in the proof in eq. ( 40) and eq. ( 42).

In addition, the lower bound of [4, Theorem 3.5] carries over to the present setting after minor modifications. We have indeed the following Theorem.

Theorem 10.2. Fix r ∈ N and assume we are in the binary classification setting. Assume moreover that (H r s ) and (MA) hold true and sϑ ≤ d. Then there exists a constant c > 0 such that for any classifier θ n , that is any {0, 1}-valued measurable function θ n of the data D n , we have

sup P∈P(CS2,H r s ,MA) T (θ n ) n -s 2s+d (1+ϑ) .
So that, under the above assumptions, the classifiers h defined in Corollary 10.1 are (nearly) minimax optimal.

Simulation study

In order to illustrate the performance of η @ j @ , we have carried out a simulation study in the regression setting in the one-dimensional case, that is with d = 1. As detailed earlier, the sole purpose of this simulation is to show that (1) η @ can be easily implemented and is computationally efficient, (2) η @ works well in practice in the case where the density of the design µ is discontinuous, (3) and to give an intuitive visual feel for η @ , which is built upon the juxtaposition of local regressions against a set of scaling functions. In particular, we run our simulation against benchmark signals, which allows to compare them with the ones detailed in the literature for alternative kernel estimators (see simulation study in [START_REF] Lepski | Optimal spatial adaptation to inhomogeneous smoothness: an approach based on kernel estimates with variable bandwidth selectors[END_REF], for example). We have run them under (CS1), which corresponds to the case where η @ j can be completely computed with exactly 2 j regressions. We have in particular E = [0, 1] = A. We focus on the functions η introduced in [START_REF] Donoho | Ideal spatial adaptation by wavelet shrinkage[END_REF] and used as a benchmark in numerous subsequent simulation studies. They are made available through the Wavelab850 library freely available at http:// www-stat.stanford.edu/ ~wavelab/. In addition we have chosen the noise ξ to be standard normal, that is we are working under (N2) with σ = 1. In all cases, we have chosen the signal-to-noise ratio (SNR) to be equal to 7. To be more specific, we are working on a dyadic grid G of [0, 1] of resolution 2 -15 . We compute the root-mean-squared-error (RMSE) of both the signal and the noise on that grid and rescale the signal so that its RMSE be seven times bigger than the one of the noise. Let us now give details about the simulation of the sample points and the computation of the estimator. We divide the unit-interval into ten sub-segments A k := 10 -1 [k, k + 1] for k = 0, . . . , 9. We define the density of X as follows.

µ(x) = 9 k=0 p k λ(A k ) -1 1 A k (x).
We choose the p k 's at random. To that end, we denote by (u k ) 0≤k≤9 ten realizations of the uniform random variable on [.25, 1], write v = u 0 + . . . + u 9 and set p k = u k v -1 . Notice that this guarantees that µ ≥ min 0≤k≤9 10p k ≥ µ min = 0.25 on [0, 1]. We then simulate 3000 sample points X i according to µ. Finally, we bring the points back on the grid G by assimilating them to their nearest grid node. Since the X i 's are supposed to be drawn from a law that is absolutely continuous with respect to the Lebesgue measure on [0, 1], we must keep only one data point per grid node. This reduces the number of data points from 3000 to the number that is reported on top of each of the histograms. In order to compute the adaptive estimator at sample points X i , we use the boundary-corrected scaling functions coded into Wavelab850 for r = 3 and for which we must have j ≥ 3. We set J = ⌈log(n/ log n)/ log 2⌉. The elimination of redundant sample points on the grid removes on average 150 points so that we obtain J = 10. We therefore have J n = {3, 4, . . . , 10}. Notice interestingly that the computation of η @ 3 requires only 8 regressions and η @ 10 requires 1, 024 of them. This is much smaller than for the LPE whose computation necessitates as many regressions as there are sample points at each resolution level. In practice, we compute the minimum eigenvalues of all regression matrices across partitions and resolution levels and choose π -1 n to be the first decile of this set of values. When proving theoretical results, we have chosen η @ j to be zero on the small probability event where the minimum eigenvalue of the regression matrix is smaller than π -1 n . In practice we can choose it to be an average value of the nearby cells in order to get an estimator that is overall more appealing to the eye. In our simulation, we in fact do not use that modification. Instead, we modify j @ to be the highest j ∈ {3, . . . , j @ } such that η @ j @ has been computed from a valid regression matrix, meaning a regression matrix whose smallest eigenvalue is greater than the threshold π -1 n . In practice, for a given signal, we generate µ at random and compute η @ j @ for 100 samples drawn from µ. We quantify the performance η @ j @ by its relative RMSE, meaning its RMSE computed at sample points X i divided by the amplitude of the true signal, that is its maximal absolute value on the underlying dyadic grid. We display results for "Doppler", "HeaviSine", "Bumps" and "Blocks" corresponding to the median performance among the 100 trials. Each figure displays four graphs. Clockwise from the top left corner, they display in turn, an histogram of sample points X i ; the adaptive level j @ at sample points X i ; the true signal (black dots) and the estimator η @ j @ at sample points X i (solid blue line) and its corresponding relative RMSE in the title; and finally the original signal (solid blue line) with its noisy version at sample points X i (red dots).

Consider the term

I = A E[|η(x) -η @ j (x)| p ]µ(x)dx.
Now, apply Proposition 12.1 and notice that A µ(x)dx = 1 to show that I is upper-bounded by the term that appears on the rhs of eq. ( 12) stated in Corollary 7.1. In particular, for all 1 ≤ p < ∞, we obtain I ≤ C(p)π p n t(n) -p ≤ C(p) < ∞. This in turn proves that we can apply the Fubini-Tonelli theorem to get

I = E[ η -η @ j p Lp(E,µ) ],
and concludes the proof.

12.1.2 Proof of Theorem 7.1

Local estimation under (CS1) in the case where r = 1. Let x ∈ A and j ∈ J n . There exists H ∈ F j such that x ∈ H. Recall that with Haar MRAs, we have S j (H) = {ν(H)} so that B H ∈ M n,1 and for any i

∈ I H , [B H ] i = ϕ j,ν(H) (X i )1 H (X i ) = ϕ j,ν(H) (X i ) since H = Suppϕ j,ν(H) . So that Q H = 1 n i∈I H ϕ j,ν(H) (X i ) 2 = 2 jd n H n .
On {Q H ≥ π -1 n }, we can divide by Q H and thus write

α ⋄ j,ν(H) = n i=1 Y i ϕ j,ν(H) (X i ) n i=1 ϕ j,ν(H) (X i ) 2 = 2 -jd/2 n i=1 Y i 1 {X i ∈Suppϕ j,ν(H) } n i=1 1 {X i ∈Suppϕ j,ν(H) } = 2 -jd/2 1 n H i∈I H Y i .
On this event, the estimation error can hence be written as

|P j η(x) -η ⋄ H (x)| = 2 jd/2 |α j,ν(H) -α ⋄ j,ν(H) | = 1 n H | i∈I H α j,ν(H) ϕ j,ν(H) (X i ) - i∈I H Y i | = 1 n H | i∈I H (P j η(X i ) -Y i )| = 1 n H | i∈I H (R j η(X i ) + ξ i )| = n n H 2 -jd/2 1 n | n i=1 (ϕ j,ν(H) (X i )(R j η(X i ) + ξ i ))| ≤ 2 j d 2 π n 1 n | n i=1 (ϕ j,ν(H) (X i )(R j η(X i ) + ξ i ))|, since Q -1 H ≤ π n . Write W j,ν(H) = 1 n | n i=1 (ϕ j,ν(H) (X i )(R j η(X i ) + ξ i ))|.
By definition, we have η @ j (x) = η @ H (x), so that we have

P(|η(x) -η @ j (x)| ≥ δ) = P(|η(x) -η @ H (x)| ≥ δ, Q H ≥ π -1 n ) + P(|η(x) -η @ H (x)| ≥ δ, Q H < π -1 n ). ( 23
)
By construction, η @ H (x) = η ⋄ H (x) on the event {Q H ≥ π -1 n } and η @ H (x) = 0 on its complement. So that we obtain |η(x)η @ H (x)| = |η(x)| ≤ M on the rhs of eq. ( 23). Notice in addition that M2 -js ≥ |R j η(x)| under (H r s ) (see Section 13.1). Finally, we obtain, for δ 2 > M2 -js ≥ |R j η(x)|,

P(|η(x) -η @ j (x)| ≥ δ) ≤ P(|P j η(x) -η ⋄ H (x)| ≥ δ 2 , Q H ≥ π -1 n ) + P(Q H < π -1 n )1 { M ≥δ} ≤ P(W j,ν(H) ≥ 2 -jd/2-1 δπ -1 n ) + P(Q H < π -1 n )1 { M≥δ} .
where we have written M = M. The term on the rhs is tackled thanks to Proposition 12.5. Regarding the lhs, a direct application of Proposition 12.6 allows to write, for all δ > 2M2 -js max(1, 3π n µ max ),

P(W j,ν(H) ≥ 2 -jd/2-1 δπ -1 n ) ≤ Λ(2 -j d 2 -1 δπ -1 n ).
This concludes the proof.

Remark 12.1. Under (O2), we have |η @ H (x)| ≤ M, and since η ∈ L s (E, M), we obtain |η(x)η @ H (x)| ≤ 2M on the rhs of eq. ( 23). While on the lhs, it is straightforward that (see [START_REF] Györfi | A distribution-free theory of nonparametric regression[END_REF]Chap. 10])

|η(x) -η @ H (x)| = |η(x) -T M (η ⋄ H (x))| ≤ |η(x) -η ⋄ H (x)|.
Under (O1), the proof remains unchanged. So that the proof still holds with M = 2M, under (O2), M, otherwise.

Local estimation under (CS1) in the case where r ≥ 2. The proof follows the same lines as above, except that Q H is now a matrix. Let x ∈ A and j ∈ J n . There exists H ∈ F j such that x ∈ H. Let us work on the set {λ min (Q H ) ≥ π -1 n } on which Q H is invertible. On that set, we can write

|P j η(x) -η ⋄ H (x)| = | α H -α ⋄ H , ϕ H (x) | = | Q -1 H • B t H n • (B H • α H -Y H ) , ϕ H (x) | ≤ Q -1 H S B t H n • (B H • α H -Y H ) ℓ 2 (R R d ) ϕ H (x) ℓ 2 (R R d ) ≤ R d 2 2 j d 2 λ min (Q H ) -1 B t H n • (B H • α H -Y H ) ℓ 2 (R R d ) .
Now, notice that for all X i ∈ H, we have

Y i = α H , ϕ H (X i ) + R j η(X i ) + ξ i . Write R H = (R j η(X i )1 H (X i )) 1≤i≤n and ξ H = (ξ i 1 H (X i )) 1≤i≤n
. Then, we have,

W H = | B t H n • (B H • α H -Y H )| = | B t H n • (ξ H + R H )| ∈ R R d .
Thus, a direct application of Proposition 12.6 allows to write, for δ > 2M2 -js max(1, 3π n R d µ max ),

P(|η(x) -η ⋄ H (x)| ≥ δ, λ min (Q H ) ≥ π -1 n ) ≤ P( W H ℓ 2 (R R d ) ≥ δ2 -j d 2 2π n R d 2 ) ≤ R d sup k∈S j (H) P [W H ] k ≥ δ2 -j d 2 2π n R d ≤ R d Λ δ2 -j d 2 2π n R d .
At last, using exactly the same arguments as in the case where r = 1 above, we obtain

P(|η(x) -η @ j (x)| ≥ δ) ≤ P(|η(x) -η ⋄ H (x)| ≥ δ, λ min (Q H ) ≥ π -1 n ) + P(λ min (Q H ) < π -1 n )1 {δ≤ M }
, where M has been defined in Remark 12.1. The term on the lhs has been dealt with above. The term on the rhs is tackled using Proposition 12.3. This concludes the proof.

Proof of Theorem 7.2

This result is obtained after a slight modification of [START_REF] Lepski | Optimal spatial adaptation to inhomogeneous smoothness: an approach based on kernel estimates with variable bandwidth selectors[END_REF]Proposition 3.4]. In the same way as in the proof of Theorem 7.1, we are brought back to controlling E|η @ j @ (x) (x)η(x)| p for all x ∈ A. To that end, we split this term as follows

E|η @ j @ (x) (x) -η(x)| p = E|η @ j @ (x) (x) -η(x)| p (1 {j @ (x)≤js} + 1 {j @ (x)>js} ) = I + II.
Let us first deal with I. Notice that

2 1-p |η @ j @ (x) (x) -η(x)| p ≤ |η @ j @ (x) (x) -η @ js (x)| p + |η @ js (x) -η(x)| p .
The last term is of the good order since

E|η @ js (x) -η(x)| p ≤ C(p)π p n max 2 -jss , 2 js d 2 √ n p = C(p) (κ log n) p 2 t(n)2 r n -s 2s+d p ,
according to Proposition 12.1, eq. (10a) and eq. ( 10c). Regarding the first term, notice that on the event {j @ (x) ≤ j s }, one has got

|η @ j @ (x) (x) -η @ js (x)| ≤ g(j @ (x), j s ) ≤ sup j̟≤k≤js g(k, j s ) ≤ g(j s , j s ) = 2t(n) 2 js d 2 √ n ≤ 2t(n)2 r n -s 2s+d ,
where we have used eq. (10a) and eq. ( 10c) and which is of the good order too. Let us now turn to II. For any two j < k, we write

G(x, j, k) = {|η @ j (x) -η @ k (x)| > g(j, k)}.
Write J n (j) = {k ∈ J n : k > j}. Notice first that we have the following inclusions

{j @ (x) = j} ⊆ k∈Jn(j-1) G(x, j -1, k), {j @ (x) > j s } = j∈Jn(js) {j @ (x) = j} ⊆ j∈Jn(js) k∈Jn(j-1) G(x, j -1, k).
Therefore, we can write

II ≤ j∈Jn(js) E|η @ j @ (x) (x) -η(x)| p 1 {j @ (x)=j} ≤ j∈Jn(js) k∈Jn(j-1) E|η @ j (x) -η(x)| p 1 G(x,j-1,k) .
Now, we notice that

|η @ j (x) -η @ k (x)| ≤ |η @ j (x) -η(x)| + |η(x) -η @ k (x)|. So that G(x, j, k) = {|η @ j (x) -η @ k (x)| > g(j, k)} ⊂ |η @ j (x) -η(x)| > 2 j d 2 √ n t(n) |η @ k (x) -η(x)| > 2 k d 2 √ n t(n) , P(G(x, j, k)) ≤ P |η @ j (x) -η(x)| > 2 j d 2 √ n t(n) + P |η @ k (x) -η(x)| > 2 k d 2 √ n t(n) .
So that a direct application of the Cauchy-Schwarz inequality leads to

E|η @ j (x) -η(x)| p 1 G(x,j-1,k) ≤ (E|η @ j (x) -η(x)| 2p ) 1 2 P(G(x, j -1, k)) 1 2 .
Now, a direct application of Proposition 12.1 for j s ≤ j ≤ J gets us

(E|η @ j (x) -η(x)| 2p ) 1 2 ≤ C(2p)π p n max 2 -js , 2 j d 2 √ n p ≤ C(2p)(κ log n) -p 2 .
Besides, notice that for j s ≤ j < k ≤ J, we can apply Proposition 12.2 with κ ≥ p 2 C -1 9 to obtain

P |η @ j (x) -η(x)| > 2 j d 2 √ n t(n) ∨ P |η @ k (x) -η(x)| > 2 k d 2 √ n t(n) ≤ 5R 2d n -p 2 .
To conclude the proof, it remains to notice that #J n ≤ log n and remark that the multiplicative constant in the upper-bound of Theorem 7.2 is indeed smaller than, say, 5 for n large enough.

A few useful Propositions and Lemmas

Proposition 12.1. Fix r ∈ N and assume we are under (CS1) and (H r s ). Then, For any x ∈ A and j ∈ J n , one has got

E[|η(x) -η @ j (x)| p ] ≤ C(p)π p n max 2 -js , 2 j d 2 √ n p , where
C(p) = 3 p M p max(1, R 2d µ max ) p + C 5 (r, d, p, µ max ; K, σ) + 2M p R 2d ,
and C 5 is made explicit in the proof at eq. ( 24).

Proof. For any

x ∈ A, take δ = 3M2 -js max(1, 3π n R d µ max ). Notice first that max(1, 3π n R d µ max ) ≤ π n max(1, 3R d µ max ) since, by construction, π -1 n ≤ 1 in any case. Now, write E[|η(x) -η @ j (x)| p ] = R + pt p-1 P(|η(x) -η @ j (x)| ≥ t)dt ≤ δ p + +∞ δ pt p-1 P(|η(x) -η @ j (x)| ≥ t)dt.
As δ has been fixed, we only need to tackle the rhs above, which we will denote by II. Using Theorem 7.1, we can write

II ≤ 2R 2d exp -n2 -jd π -2 n 2µ max R 4d + 4 3 R 2d π -1 n M 0 pt p-1 dt + R d ∞ 0 pt p-1 Λ t2 -j d 2 2π n R d dt.
Denote by II 1 and II 2 the lhs and rhs terms above, respectively. Now, recall that j ≤ J, where 2 Jd ≤ nt(n) -2 and t(n) 2 = κπ 2 n log n. Therefore, as soon as

κ ≥ p 2 2µ max R 4d + 4 3 R 2d π -1 n , we have II 1 ≤ 2M p R 2d n -p 2 .
Let us now turn to II 2 . Assume first that we are working under the bounded noise assumption, (N1). In that case, we have

II 2 ≤ 2R d ∞ 0 pt p-1 exp - n2 -jd t 2 π -2 n 64K 2 R 2d µ max + 8KR d π -1 n t dt ≤ C 2 (r, d, p, µ max , K) π n 2 j d 2 √ n p .
where the last inequality results from the change of variable u = √ n2 -j d 2 π -1 n t together with the fact that 2 jd ≤ n and we have written

C 2 := 2R d ∞ 0 pt p-1 exp - t 2 64K 2 R 2d µ max + 8KR d t dt.
Assume now that we are working under the Gaussian noise assumption (N2). In that case, we have

II 2 ≤ R d ∞ 0 pt p-1 1 ∧ 2σR d 2 (4R d µ max + 2tπ -1 n ) 1 2 tπ -1 n 2 -j d 2 √ 2πn exp - n2 -jd π -2 n t 2 σ -2 4R 2d µ max + 2R d π -1 n t dt + 2R d ∞ 0 pt p-1 exp - n2 -jd π -2 n t 2 8R 2d µ max + 8 3 R d π -1 n t dt.
Denote by II 3 and II 4 the first and second term, respectively. They can both be handled in the exact same way as II 2 , which leads to

II 4 ≤ C 4 (r, d, p, µ max ) π n 2 j d 2 √ n p ,
where we have written

C 4 := 2R d ∞ 0 pt p-1 exp - t 2 8R 2d µ max + 8 3 R d t dt,
and

II 3 ≤ C 3 (r, d, p, µ max , σ) π n 2 j d 2 √ n p ,
where we have written

C 3 := R d ∞ 0 pt p-1 1 ∧ 2σR d 2 (4R d µ max + 2t) 1 2 t √ 2π exp - t 2 σ -2 4R 2d µ max + 2R d t dt.
To conclude, let us write

C 5 (r, d, p, µ max ; K, σ) = C 2 (r, d, p, µ max , K) under (N1) C 3 (r, d, p, µ max , σ) + C 4 (r, d, p, µ max ) under (N2) (24)
Therefore, we ultimately obtain

E[|η(x) -η @ j (x)| p ] ≤ 3 p M p max(1, 3R d µ max ) p + C 5 + 2M p R 2d π p n max 2 -js , 2 j d 2 √ n p ,
which concludes the proof.

Proposition 12.2. Fix r in N and assume we are under (CS1) and (H r s ). This means in particular that s ∈ (0, r). Let j be such that j s ≤ j ≤ J. Let t(n) 2 = κπ 2 n log n, and define

C 9 (r, d, µ max , π n ; K, σ) := C 6 (r, d, µ max , K, π n ), under (N1) C 6 (r, d, µ max , σ, π n ), under (N2) ,
where C 6 is defined in eq. ( 25) below. Then we have, for n large enough,

P |η @ j (x) -η(x)| > 2 j d 2 √ n t(n) ≤ 5R 2d n -κC 9 .
Proof. The proof relies on a direct application of Theorem 7.1. Write C 0 = 2M max(1, 3π n R d µ max ) and notice indeed that the theorem applies since for j ≥ j s , we get 2

j d 2 n -1 2 ≥ 2 -(r+ d 2 )
2 -jss (see eq. ( 10b)) and, as soon as n is large enough, we have t(n) ≥ 2 r+ d 2 C 0 . This leads us to

P |η @ j (x) -η(x)| > 2 j d 2 √ n t(n) ≤ 2R 2d exp -n2 -jd π -2 n 2µ max R 4d + 4 3 R 2d π -1 n + R d Λ t(n) 2π n R d √ n .
Let us denote the first term by I and the second one by II. I is easily tackled noticing that for j ≤ J, n2 -jd ≥ n2 -Jd ≥ t(n) 2 = κπ 2 n log n. So that, we obtain I ≤ 2R 2d n -κC 6 , where we have written

C 6 (r, d, µ max , K, π n ) := min(1, K -2 ) 64µ max R 2d + 8R d π -1 n . ( 25
)
Let us now turn to II. Assume first we work under (N1). Then we can write

II ≤ 2R d exp   - t(n) 2 π -2 n 64R 2d K 2 µ max + 8R d Kπ -1 n 2 j d 2 t(n) √ n   .
Notice first that 2 j d 2 t(n) ≤ √ n. Therefore, we obtain II ≤ 2R d n -κC 6 . Assume now that we work under (N2). In that case, we obtain

II ≤ R d 1 ∧ 2R d 2 σ(4R d µ max + 2π -1 n 2 j d 2 t(n) √ n ) 1 2 t(n)π -1 n √ 2π exp   - t(n) 2 π -2 n σ -2 4R 2d µ max + 2R d π -1 n 2 j d 2 t(n) √ n   + 2R d exp   - t(n) 2 π -2 n 8R 2d µ max + 8 3 R d π -1 n 2 j d 2 t(n) √ n   .
We proceed exactly as under (N1). So that we obtain II ≤ C 7 n -κC 8 , where

C 8 (r, d, µ max , σ, π n ) := min(1, σ -2 ) 4R 2d µ max + 2R d π -1 n , C 7 (r, d, µ max , σ, π n , t(n)) = R d 2R d 2 σ(4R d µ max + 2π -1 n ) 1 2 t(n)π -1 n √ 2π + 2R d . So that C 7 ≤ 3R d for n large enough. Notice finally that C 8 (r, d, µ max , t, π n ) ≥ C 6 (r, d, µ max , t, π n ).
This concludes the proof.

Proposition 12.3. Fix an integer r ≥ 2 and assume we are under (CS1). Let x ∈ A and j ∈ J n . By construction, there exists H ∈ F j such that x ∈ H. Recall besides that #S j (H) = R d , where R = 2r-1 is obviously independent of both x and j. Write . = . ℓ 2 (R R d ) and assume there exists a strictly positive constant g min independent of x and j such that

λ min (EQ H ) = min u∈R R d : u =1 u, EQ H u ≥ g min . (26)
Then, for any real number t such that 0 < t ≤ g min 2 , we have

P(λ min (Q H ) ≤ t) ≤ 2R 2d exp -n2 -jd t 2 2µ max R 4d + 4 3 R 2d t .
Proof. Under the assumption described in eq. ( 26), we get

λ min (Q H ) ≥ min u∈R R d : u =1 u, EQ H u + min u∈R R d : u =1 u, (Q H -EQ H )u ≥ 2t - ν,ν ′ ∈S j (H) |[Q H ] ν,ν ′ -[EQ H ] ν,ν ′ |. Write T i = ϕ j,ν (X i )ϕ j,ν ′ (X i )1 H (X i ) -Eϕ j,ν (X)ϕ j,ν ′ (X)1 H (X), so that ET i = 0, VarT i ≤ µ max 2 jd and |T i | ≤ 2 jd+1
. A direct application of Bernstein inequality for any δ > 0 leads to

P(|[Q H ] ν,ν ′ -[EQ H ] ν,ν ′ | ≥ δ) = P(| 1 n n i=1 ϕ j,ν (X i )ϕ j,ν ′ (X i )1 H (X i ) -Eϕ j,ν (X)ϕ j,ν ′ (X)1 H (X)| ≥ δ) ≤ 2 exp - n2 -jd δ 2 2µ max + 4 3 δ .
To conclude, we write

P(λ min (Q H ) ≤ t) ≤ P( ν,ν ′ ∈S j (H) |[Q H ] ν,ν ′ -[EQ H ] ν,ν ′ | ≥ t) ≤ 2R 2d exp -n2 -jd t 2 2µ max R 4d + 4 3 R 2d t .
Proposition 12.4. Fix an integer r ≥ 2 and assume we are under (CS1). For any x ∈ A and j ∈ J n , we denote by H the unique hypercube of F j such that x ∈ H. Then, there exists a strictly positive absolute constant g min independent of both x and j such that, for all j ∈ J n and all x ∈ A, we have λ min (EQ H ) ≥ g min > 0.

Proof.

For any u ∈ R R d such that u ℓ 2 (R R d ) = 1, we can write u, EQ H • u = A   ν∈S j (H) u ν ϕ j,ν (w)1 H (w)   2 µ(w)dw ≥ µ min H   ν∈S j (H) u ν ϕ j,ν (w)   2 dw, (27)
= µ min [0,1] d ν∈S u ν ϕ ν (w) 2 dw, (28)
where S has been defined in eq. ( 15) and the last equality results from the fact that the value of the integral on the rhs of eq. ( 27) is invariant with H, meaning that for any H ∈ F j and

u ∈ R R d , H   ν∈S j (H) u ν ϕ j,ν (w)   2 dw = 2 -j [0,1] d   ν∈S j (2 -j [0,1] d ) u ν ϕ j,ν (w)   2 dw = [0,1] d ν∈S u ν ϕ ν (w) 2 dw.
Let us denote by S R d -1 the unit-sphere of R R d . As detailed in the proof of Lemma 12.1, the map

u ∈ S R d -1 → [0,1] d ν∈S u ν ϕ ν (w) 2 dw,
is absolutely continuous with respect to u on the compact subset S R d -1 of R R d . It therefore reaches its minimum at some point u * ∈ S R d -1 . It is a direct consequence of the local linear independence property of the scaling functions (ϕ k ) (see Proposition 12.8) that

[0,1] d ν∈S u * ν ϕ ν (w) 2 dw = c min > 0,
where c min is a constant that is both independent from x and j. This concludes the proof with g min = µ min c min .

Proposition 12.5. Fix r = 1 and assume we are under (CS1). Let x ∈ A, j ∈ J n and H ∈ F j such that x ∈ H. Then, for any real number t such that 0 < t ≤ g min 2 , we have

2 jd n H n ≥ t on the event Ω c j,ν(H) (t), where Ω j,ν(H) (t) := { 1 n n i=1 ϕ j,ν(H) (X i ) 2 < t}.
In addition, we have got

P(Ω j,ν(H) (t)) ≤ 2 exp -n2 -jd t 2 2µ max + 4 3 t .
Recall that the constant g min has been defined in Proposition 12.4.

Proof. Notice that

ϕ j,ν(H) (w) 2 µ(w)dw ≥ µ min ≥ 2t. (29)
On Ω c j,ν(H) (t), we have

2 jd n H n ≥ 1 n n i=1 ϕ j,ν(H) (X i ) 2 ≥ t.
For any δ > 0, we write

C j,k (δ) = | 1 n n i=1 ϕ j,k (X i ) 2 -Eϕ j,k (X) 2 | ≤ δ . (30)
Notice now that

Ω j,ν(H) (t) ⊂ { 1 n n i=1 ϕ j,ν(H) (X i ) 2 -Eϕ j,ν(H) (X i ) 2 < -t} ⊂ C c j,ν(H) (t),
where C j,ν(H) (t) is defined in eq. ( 30). Finally, it is straightforward that C c j,ν(H) (t) has very small probability thanks to Bernstein inequality (see [27, p. 165] for example). Write indeed

T i = ϕ j,ν(H) (X i ) 2 -Eϕ j,ν(H) (X) 2 . Then ET i = 0, VarT i ≤ µ max 2 jd and |T i | ≤ 2 jd+1
. Thus, we can write

P(C c j,ν(H) (t)) ≤ 2 exp -n2 -jd t 2 2µ max + 4 3 t
, which concludes the proof.

Proposition 12.6. Let (X i ) i=1,...,n and (ξ i ) i=1,...,n be sequences of independent random variables such that E(ξ|X) = 0. Take any j ≥ j r . Moreover, assume we are given a function R j (.) such that R j (.) L∞(E,λ) ≤ M2 -js , a subset H of E and a scaling function ϕ j,k . Write

W j,k = 1 n n i=1 ϕ j,k (X i )1 H (X i )(R j (X i ) + ξ i ),
and define

Λ(δ) =                            2 exp - nδ 2 18K 2 µ max + 4K2 j d 2 δ , under (N1) 1 ∧ 2σ(µ max + 2 j d 2 δ) 1 2 δ √ 2πn exp - nδ 2 σ -2 µ max + 2 j d 2 δ +2 exp - nδ 2 2µ max + 4 3 2 j d 2 δ , under (N2)
Then, for all δ > 3µ max M2 -j(s+ d 2 ) , we have

P(|W j,k | ≥ δ) ≤ Λ(δ).
Proof. Notice indeed that

W j,k ≤ | 1 n n i=1 ϕ j,k (X i )ξ i 1 H (X i )| + | 1 n n i=1 ϕ j,k (X i )R j (X i )1 H (X i ) -Eϕ j,k (X)R j (X)1 H (X)| + |Eϕ j,k (X)R j (X)1 H (X)| = I + II + III.
So that we can write

P(|W j,k | ≥ δ) ≤ P(I ≥ δ/3) + P(II ≥ δ/3) + P(III ≥ δ/3).
Now it is enough to notice that

III ≤ |ϕ j,k (w)R j (w)|1 H (w)µ(w)dw ≤ µ max E |ϕ j,k (w)R j (w)|dw ≤ µ max ϕ j,k L 1 (E,λ) R j L∞(E,λ) ≤ µ max M2 -j(s+ d 2 )
.

So that P(III ≥ δ/3) = 0 as soon as δ > 3µ max M2 -j(s+ d 2 ) . Now, turn to II and write

II = | T i /n| with T i = ϕ j,k (X i )R j (X i )1 H (X i ) -Eϕ j,k (X)R j (X)1 H (X).
Obviously

ET i = 0, VarT i ≤ E(ϕ j,ν (X)R j (X)1 H (X)) 2 ≤ µ max M 2 2 -2js and |T i | ≤ M2 -js 2 j d 2 +1
. So that we can apply Bernstein inequality to get

P(II ≥ δ/3) ≤ 2 exp - n2 2js δ 2 18µ max M 2 + 4M2 j d 2 2 js δ .
And finally, turn to III. Assume first that the noise ξ is bounded by K. We have obviously Eϕ

j,k (X i )ξ i 1 H (X i ) = 0, Var(ϕ j,k (X i )ξ i 1 H (X i )) ≤ K 2 µ max and |ϕ j,k (X i )ξ i 1 H (X i )| ≤ K2 j d 2 +1
, so that

P(I ≥ δ/3) ≤ 2 exp - nδ 2 18K 2 µ max + 4K2 j d 2 δ
. Now, it is enough to notice that for all s > 0 and j such that j ≥ 1 s log 2 M K (which becomes a constraint for K < M only),

n2 2js δ 2 18µ max M 2 + 4M2 j d 2 2 js δ ≥ nδ 2 18K 2 µ max + 4K2 j d 2 δ
, which concludes the proof under (N1). When j ≥ 1 s log 2 3M, the conclusion under (N2) is a direct consequence of Proposition 12.7.

Proposition 12.7. Let ϕ j,k be a scaling function and H a subset of E. Define

I = 1 n n i=1 ϕ j,k (X i )ξ i 1 H (X i ).
Assume now that the noise ξ is conditionally Gaussian, that is we are under (N2). Then, we notice that, conditionally on X 1 , . . . , X n ,

I ∼ Φ(0, σρ j,k / √ n), where ρ 2 j,k = n -1 n i=1 ϕ j,k (X i ) 2 1 H (X i ).
Then, for all δ > 0, one can write

P(|I| ≥ δ) ≤ 1 ∧ 2σ(µ max + 2 j d 2 δ) 1 2 δ √ 2πn exp - nδ 2 σ -2 µ max + 2 j d 2 δ + 2 exp - nδ 2 2µ max + 4 3 2 j d 2 δ
.

Proof. For any δ > 0, we write

C j,k (δ) = | 1 n n i=1 ϕ j,k (X i ) 2 1 H (X i ) -Eϕ j,k (X) 2 1 H (X)| ≤ δ .
Notice first that

C j,k (2 j d 2 δ) ⊂ {ρ 2 j,k ≤ µ max + 2 j d 2 δ}.
So that

1 {|I|≥δ} ≤ 1 {|I|≥δ} 1 {ρ 2 j,k ≤µmax+2 j d 2 δ} + 1 {|I|≥δ} 1 C c j,k (2 j d 2 δ) ≤ 1 {|I|≥δ} 1 {ρ 2 j,k ≤µmax+2 j d 2 δ} + 1 C c j,k (2 j d 2 δ)
.

The first term is handled thanks to a regular Gaussian tail inequality. Notice indeed that

P(|I| ≥ δ|X 1 , . . . , X n )1 {ρ 2 j,k ≤µmax+2 j d 2 δ} ≤ 1 ∧ 2ρ j,k σ δ √ 2πn exp - nδ 2 ρ 2 j,k σ 2 1 {ρ 2 j,k ≤µmax+2 j d 2 δ} ≤ 1 ∧ 2σ(µ max + 2 j d 2 δ) 1 2 δ √ 2πn exp - nδ 2 σ -2 µ max + 2 j d 2 δ
.

In addition, notice that Eϕ j,k (X) 4 1 H (X) ≤ µ max 2 jd and |ϕ j,k (X)

2 1 H (X i )-Eϕ j,k (X) 2 1 H (X)| ≤ 2 jd+1
, so that a direct application of Bernstein inequality leads to

P(C j,k (2 j d 2 δ) c ) ≤ 2 exp - n2 jd δ 2 2 jd (2µ max + 4 3 2 j d 2 δ) = 2 exp - nδ 2 2µ max + 4 3 2 j d 2 δ
, which concludes the proof.

12.2 Proof of the upper-bound results under (CS2)

Recall that under (CS2), we work with a sample of size 2n split into two pieces denoted by D n and D ′ n . As detailed previously, similar results as the ones described in Section 7, Section 8 and Section 12.1.4 are still valid with η under (CS2). They in fact all stem from Theorem 9.1. The proofs remain for the most part unchanged, with J n redefined as J n = {j s , j s + 1, . . . , J -1, J} where 2 js = ⌊n 1 2s+d ⌋, η in place of η @ , X i in place of X i (where we have written u = u -X ′ ix + 2 -j-1 ), and H 0 in place of H. The sole differences appear in the proofs of Theorem 9.1, Proposition 12.4 and Proposition 12.5. Let us start with the proof of Theorem 9.1.

Proof of Theorem 9.1. Assume we are under (CS2) and want to control the probability of deviation of η j (x) from η(x) at a point x ∈ A, for some j ∈ J n . Recall that H 0 (x) stands for the cell H 0 = 2 -j [0, 1] d centered in x at level j, that is H 0 (x) = x -2 -j-1 + 2 -j [0, 1] d and denote by O x the event

O x = {#{i : X ′ i ∈ H 0 (x)} ≥ 1}. We can write P(|η(x) -η j (x)| ≥ δ) = P(|η(x) -η j (x)| ≥ δ, O x ) + P(|η(x) -η j (x)| ≥ δ, O c
x ). Focus first on what happens on the event O c

x . The last term can be controlled easily since the probability that no single design point X ′ i of D ′ n belongs to H 0 (x) decreases exponentially fast with n. Notice indeed that, under (CS2),

P(O c x ) = (P(X ′ 1 / ∈ H 0 (x))) n = (1 -P(X ′ 1 ∈ H 0 (x))) n = 1 - A∩H 0 (x) µ(w)dw n ≤ 1 -µ min 2 -jd λ 2 j (A -x) ∩ [-2 -1 , 2 -1 ] d n ≤ (1 -µ min 2 -jd min(2m 0 , 2 -1 ) d ) n ≤ exp(-µ min min(2m 0 , 2 -1 ) d n2 -jd ),
where the before last inequality is a direct consequence of (S2) and the last one comes from the fact that for any x ∈ [0, 1), ln(1x) ≤ -x. Now, recall that η j (x) = 0 on O c x and |η(x)| ≤ M since η ∈ L s (R d , M). So that we obtain

P(|η(x) -η j (x)| ≥ δ, O c
x ) ≤ exp(-µ min min(2m 0 , 2 -1 ) d n2 -jd )1 {δ≤M } , which is smaller than the first term in the upper-bound of Theorem 9.1. Now focus on what happens on the event O x . We can write

P(|η(x) -η j (x)| ≥ δ, O x ) = P(O x )E[P(|η(x) -η j (x)| ≥ δ|X ′ ix )|O x ] ≤ E[P(|η(x) -η j (x)| ≥ δ|X ′ ix )|O x ].
Proof of Proposition 12.5 under (CS2). Recall first that x ∈ H 0 = 2 -j [0, 1] d and ν(H 0 ) = 0. At points x located at the boundary of A, the cell H 0 (X

′ ix ) = X ′ ix + 2 -j [-2 -1 , 2 -1 ] d centered in X ′
ix is eventually not a subset of A anymore, so that the proof of Proposition 12.5 breaks down at the level of eq. ( 29). Using the independence of X ′ ix from the points of D n , we can write

E[Q H 0 |X ′ ix ] = ϕ j,ν(H 0 ) ( w) 2 µ(w)dw ≥ µ min A 2 jd ϕ ν(H 0 ) (2 j (w -X ′ ix ) + 2 -1 ) 2 dw = µ min 2 j (A-X ′ ix ) ϕ(w + 2 -1 ) 2 dw ≥ µ min inf m≥m 0 inf z∈B∞(0,m) B∞(z,m) ϕ(w + 2 -1 ) 2 dw = µ min inf m≥m 0 inf z∈B∞(2 -1 ,m) B∞(z,m) ϕ(w) 2 dw ≥ µ min c min ≥ 2t,
where the before last inequality comes as a direct application of Lemma 12.1, eq. ( 32). The end of the proof follows the same lines as previously, under setting (CS1).

The updated proofs hinge on the following results.

inf u∈S R d -1 inf m≥m 0 inf z∈B∞(2 -1 ,m) B∞(z,m)∩[0,1] d ν∈S u ν ϕ ν (w) 2 dw ≥ c min , (31)
inf

m≥m 0 inf z∈B∞(2 -1 ,m) B∞(z,m) ν∈S ϕ ν (w) 2 dw ≥ c min . (32)
Proof. The proof of eq. ( 32) follows the same lines as the one of eq. ( 31). Therefore, we will only prove eq. ( 31). Now write u = (u ν ) ν∈S and ϕ S (.) = (ϕ ν (.)) ν∈S . Denote by S R d -1 the unit sphere of R R d . Consider the map defined by

f m :B ∞ (2 -1 , m) × S R d -1 → R, f m (z, u) = B∞(z,m)∩[0,1] d u, ϕ S (w) 2 dw.
Notice first that, u being fixed, inf z∈B∞(2 -1 ,m) f m (z, u) is an increasing function of m, since the integrand is positive and for m 1 ≥ m 2 , for all

z 1 ∈ B ∞ (2 -1 , m 1 ), we can find z 2 ∈ B ∞ (2 -1 , m 2 ) such that B ∞ (z 2 , m 2 ) ⊂ B ∞ (z 1 , m 1 ). So that inf m≥m 0 inf z∈B∞(2 -1 ,m) f m (z, u) reduces in fact to inf z∈B∞(2 -1 ,m 0 ) f m 0 (z, u).
From now on, let us write f in place of f m 0 and prove that f is continuous on its domain. We have indeed

|f (z 2 , u 2 ) -f (z 1 , u 1 )| ≤ |f (z 2 , u 2 ) -f (z 1 , u 2 )| + |f (z 1 , u 2 ) -f (z 1 , u 1 )|.
And

|f (z 1 , u 2 ) -f (z 1 , u 1 )| ≤ B∞(z 1 ,m 0 )∩[0,1] d | u 2 -u 1 , ϕ S (w) || u 2 + u 1 , ϕ S (w) |dw ≤ 2R d ϕ 2 L∞(R d ) u 2 -u 1 ℓ 2 (R R d ) .
Besides, noticing that

1 B∞(z 1 ,m 0 ) (w) = 1 [0,2m 0 ] d (w -z 1 + m 0 ) = 1 [0,1] d ( w -z 1 + m 0 2m 0 ),
we can write

|f (z 2 , u 2 ) -f (z 1 , u 2 )| ≤ [0,1] d |1 B∞(z 2 ,m 0 ) (w) -1 B∞(z 1 ,m 0 ) (w)| u 2 , ϕ S (w) dw ≤ R d/2 ϕ L∞(R d ) 2m 0 R d |1 [0,1] d (w + m 0 -z 2 2m 0 ) -1 [0,1] d (w + m 0 -z 1 2m 0 )|dw ≤ 2R d/2 ϕ L∞(R d ) z 2 -z 1 ℓ 1 (R d ) ,
where the last inequality comes as a direct application of Lemma 12.2. Since f is continuous and its domain is compact, it is in particular lower bounded and reaches its lower bound in (z * , u * ) ∈ B ∞ (2 -1 , m 0 ) × S r,d . Now, since u * = 0, it is a direct consequence of the local linear independence of the scaling functions (ϕ j,k ) k∈Z d described in Proposition 12.8 that f (z * , u * ) > 0. This concludes the proof. Proof. The proof follows the same lines as the proof of Theorem 3.7.1 and Remark 3.7.1 in [START_REF] Cohen | Numerical analysis of wavelet methods[END_REF] and relies on arguments detailed in [START_REF] Malgouyres | On the support of the scaling function in a multiresolution analysis[END_REF] and the references therein. For completeness, we detail the proof here.

In the one-dimensional case, the proof is given in

∈ Z d , ϕ k (x) = ϕ (d-1) k 1,d-1 (x 1,d-1 )ϕ (1) k d (x d ), we obtain 0 = k d ∈S 1 a k d ϕ (1) k d (x d ), on B ∞ (z d , m), a k d = m∈S d-1 α (m,k d ) g(x 1,d-1 )ϕ (d-1) m (x 1,d-1 )dx 1,d-1 .
However, the linear independence property in one dimension triggers a k d = 0 for all k d ∈ S 1 . Since the test function g is chosen arbitrarily, this latter result leads in turn to

m∈S d-1 α (m,k d ) ϕ (1,d-1) m (x 1,d-1 ) = 0, for all k d ∈ S 1 and x 1,d-1 ∈ B ∞ (z 1,d-1 , m).
Finally, using the induction hypothesis, we obtain α k = 0 for all k ∈ S d .

Lemma 12.2. Define the function f as follows

f : R d → R + , f (y) R d 1 {w+y∈[0,1] d } dw. Then, f is Lipschitz-continuous on R d , such that, for any two y, z ∈ R d , |f (y) -f (z)| ≤ 2 y -z ℓ 1 (R d ) .
Proof. The result is easily obtained by induction. We have indeed obviously for d = 1,

|f (y) -f (z)| ≤ R |1 {w+y∈[0,1]} -1 {w+z∈[0,1]} |dw ≤ λ([[0, 1] -y]∆[[0, 1] -z]) ≤ 2|y -z|. Now, write T(y) = [0, 1] d -y and T i (y) = [0, 1] -y i for 1 ≤ i ≤ d,
where y i stands for the i th coordinate of y. In addition, for 1 ≤ p ≤ q ≤ d, we write T p,q (y) = Π q i=p T i (y).

Lower bound under setting (CS1)

We choose µ(.) = 1, so that we are brought back to the case of a regression on a uniform design. Notice that, under (S1), such a µ verifies (D1) since µ min , µ max must be such that µ min ≤ 1 ≤ µ max . In the case of a Gaussian noise such as under (N2), the proof of the lowerbound is well known and can be found in [START_REF] Monnier | Non-parametric regression on the hyper-sphere with uniform design[END_REF][START_REF] Baldi | Asymptotics for spherical needlets[END_REF][START_REF] Chesneau | Wavelet block thresholding for samples with random design: a minimax approach under the L p risk[END_REF], to quote a few. In the case of a bounded noise, the same reasoning still applies thanks to Proposition 12.10 above.

Lower bound under setting (CS2)

In that case, a bit more work is needed. Let r ∈ N and recall that 2 js = ⌊n 1 2s+d ⌋. Let us write E = R d and denote by (V j ) j≥0 the Daubechies' r-MRA of L 2 (R d , λ). For any subset X of Z d , write ∇(X ) := [{0, 1}\{(0, . . . , 0)}] × X and ∇ := ∇(Z d ). We recall that the multivariate Daubechies' wavelets ψ ν , ν ∈ ∇ associated with the r-MRA above are supported on hypercubes of volume R d . We define the grid

G 2 j ζ := (k 1 , . . . , k d ) : k i ∈ {0, . . . , ⌊m2 js ⌋ -1} ,
for some absolute constant m to be chosen later. Obviously, we have #G 2 js = ⌊m2 js ⌋ d . In addition, we take

A = k∈G 2 js B ∞ (k, 1 2 ⌊m2 js ⌋ -1 ).
Now, choose m such that 2 js 2 -1 ⌊m2 js ⌋ -1 ≥ R, that is, say, m = (2R) -1 . We assume that n is large enough, that is 2 js ≥ 2R, so that the grid is not degenerate. It is immediate that A verifies (S2). Now, define μ on R d to be μ(.) = k∈G 2 js 1 B∞(k, 1 2 ⌊m2 js ⌋ -1 ) (.).

By construction, we obtain A μ(w)dw = 1. And finally, μ verifies (D1) since µ min ≤ 1 ≤ µ max , as desired. Let j ≥ j s . Notice now that for any k ∈ G 2 js , we can find a subset G * j,k of Z d such that #G * j,k = 2 (j-js)d and such that for all ν ∈ ∇(G * j,k ), Suppψ j,ν ⊂ B ∞ (k, 1 2 ⌊m2 js ⌋ -1 ). We write

Ḡj := k∈G 2 js G * j,k .
In addition, we denote by a a a := (a ν ) ν∈∇( Ḡj ) an element of {0, 1} ∇( Ḡj ) . With these notations, we define

Υ( Ḡj ) :=    η ∈ L s (R d , M) : η = γ j ν∈∇( Ḡj ) a ν ψ j,ν , a a a ∈ {0, 1} Ḡj    , j ≥ j s .
Now, we just need to remark that #∇( Ḡj ) ≈ 2 jd and for any two η 1 , η 2 ∈ Υ( Ḡj ),

η 1 -η 2 Lp(E,μ) = η 1 -η 2 Lp(R d ,λ) . (33)
This last result together with both Proposition 12.9 and Proposition 12.10 above allows us to conclude once more using the well known arguments of the proof of the lower bound in a uniform design, under both assumptions (N1) and (N2). For completeness, we detail the end of the reasoning below. We denote by (Ind) the assumption that ξ is independent of X and write

P * ( Ḡj ) := {P ∈ P(R d × R) : η ∈ Υ( Ḡj ), µ = μ, (Ind) holds true}.
We denote by η a a a the elements of Υ( Ḡj ), where we write a a a ∈ {0, 1} ∇( Ḡj ) . It appears that, for η a a a ∈ Υ( Ḡj ),

η a a a L s (R d ) ≤ C|γ j |2 j(s+ d 2 ) sup ν∈∇( Ḡj ) a ν ≤ C|γ j |2 j(s+ d 2 ) ,
where the first inequality is a direct application of eq. ( 37). Thus, in order to have

η a a a ∈ L s (R d , M), it is enough to choose |γ j | ≤ CM2 -j(s+ d 2 )
. With this constraint on γ j , we obtain

P(CS2, H r s ) ⊃ P * ( Ḡj ).
Besides, for any two a a a, a ′ a ′ a ′ ∈ {0, 1} ∇( Ḡj ) , a direct application of [10, eq. (3.6.16)] leads to

η a a a -η a ′ a ′ a ′ Lp(E,μ) ≥ c|γ j |2 jd( 1 2 -1 p )   ν∈∇( Ḡj ) |a ν -a ′ ν | p   1 p . ( 34
)
The Varshamov-Gilbert Lemma (see [51, Lemma 2.9]) ensures there exists a subset

∇(A j ) ⊂ ∇( Ḡj ) such that #∇(A j ) ≥ #∇( Ḡj ) 8 and ν∈∇(A j ) |a ν -a ′ ν | ≥ #∇( Ḡj ) 8
. Write Γ j := {(a ν ) ν∈∇( Ḡj ) :

a ν ∈ {0, 1 {ν∈∇(A j )} }}. Now, if we pick |γ| = c2 -j(s+ d 2 )
and a a a, a ′ a ′ a ′ ∈ Γ j , eq. ( 34) together with the latter results leads to

η a a a -η a ′ a ′ a ′ Lp(E,μ) ≥ c|γ|2 jd( 1 2 -1 p ) 2 jd 8 1 p = c2 -js . (35)
Now we can write δ := 1 2 c2 -js and G a a a = { θη a a a Lp(E,μ) < δ}. It results from eq. ( 35) that, for a a a ∈ Γ j , the G a a a 's are mutually exclusive. Let us denote by P ηa a a, μ the law of (X, Y ) under the assumption that η = η a a a and µ = μ and E ηa a a ,μ the corresponding expectation. We will add the superscript ⊗n when dealing with their n th tensorial product. Thus we can apply Theorem 12.1 to obtain max

P∈P * (Υ(A j )) E θ -η p Lp(E,μ) = max a a a∈Γ j E ⊗n ηa a a, μ θ -η a a a p Lp(A,μ) (36)
≥ δ p max a a a∈Γ j P ⊗n ηa a a, μ( θη a a a Lp(E,μ) ≥ δ)

= δ p max a a a∈Γ j P ⊗n ηa a a, μ(G c a a a ) ≥ δ p 1 2 ∧ C 2 #Γ j -1e -κ((P ⊗n ηa a a,
μ) a a a∈Γ j ) .

In addition both Proposition 12.9 and Proposition 12.10 lead to

K (P ⊗n ηa a a, μ, P ⊗n η a ′ a ′ a ′ ,μ ) = nK (P ηa a a, μ, P η a ′ a ′ a ′ ,μ ) ≤ Cn η a a a -η a ′ a ′ a ′ 2 L 2 (E,μ) = Cn|γ j | 2 ν∈∇(A j ) (a ν -a ′ ν )ψ j,ν 2 L 2 (E,λ) ≤ Cn|γ j | 2 ν∈∇(A j ) |a ν -a ′ ν | 2 ≤ Cn|γ j | 2 2 jd = Cn2 -2js ,
where the second equality makes use of eq. ( 33). As a consequence 2 #Γ j -1e -κ((P ⊗n ηa a a, μ) a a a∈Γ j ) ≥ 2 c2 jd e -cn2 -2js .

In order to balance this last term, it is enough to choose j such that n2 -2js = c2 jd , which leads to n -1 2 = c2 -j(s+ d 2 ) . Combining this value with eq. ( 36) and the inclusion

L s (R d , M) ⊃ Υ( Ḡj ) ⊃ Υ(A j ) gives sup P∈P(CS2,H r s ) E θ -η p Lp(E,μ) ≥ max P∈P * (Υ(A j )) E θ -η p Lp(E,μ) ≥ c(2 -j ) sp = cn -sp 2s+d .
This concludes the proof of Theorem 7.3.

(f, x) = |f (x + h) -f (x)| for any x ∈ R d .
For any r ∈ N and all x ∈ R d , we further define the r th -finite difference by induction as follows,

∆ r h (f, x) = ∆ 1 h (∆ r-1 h (f, x)),
and the r th -modulus of smoothness of f ∈ C (R d ) as follows

ω r (f, t) ∞ = sup 0≤ h ≤t ∆ r h (f, .) L∞(R d ,λ) .
Write s > 0 and r = ⌊s⌋ + 1. The Besov space B s ∞,∞ on R d , also known as the generalized Lipschitz space L s (R d ), is the collection of all functions f ∈ C (R d ) ∩ L ∞ (R d , λ) such that the semi-norm |f | L s (R d ) := sup t>0 t -s ω r (f, t) ∞ , is finite. The norm for L s (R d ) is subsequently defined as

f L s (R d ) := f L∞(R d ,λ) + |f | L s (R d ) .
Fix a real number M > 0. Throughout the paper, L s (R d , M) refers to the ball of L s (R d ) of radius M. Obviously, the elements of L s (R d , M) are λ-a.e. uniformly bounded by M on R d . As described in [START_REF] Devore | Constructive approximation[END_REF][START_REF] Cohen | Numerical analysis of wavelet methods[END_REF], there exists an alternative definition of Lipschitz spaces C s (R d ), also known as Hölder spaces, which goes as follows. For any integer d, multi-index q = (q 1 , . . . , q d ) ∈ N d and x = (x 1 , . . . , x d ) ∈ R d , we define the differential operator ∂ q as usual by ∂ q := ∂ q 1 +...+q d ∂ q 1 x 1 ...∂ q d x d . For any positive integer s, C s (R d ) consists of the functions f on R d such that ∂ q f is bounded and absolutely continuous on R d , for all q ∈ N d such that |q| 1 := q 1 + . . . + q d ≤ s. This definition is extended to non-integer s as follows,

C s (R d ) := {f ∈ C (R d ) ∩ L ∞ (R d , λ) : sup x∈R d ∆ 1 h (f, x) ≤ C|h| s }, 0 < s < 1, C s (R d ) := {f ∈ C (R d ) ∩ L ∞ (R d , λ) : ∂ q f ∈ C s-m (R d ), |q| 1 = m}, m < s < m + 1, m ∈ N.
It can be shown that, for all non-integer s > 0, C s (R d ) = L s (R d ), while C s (R d ) is a strict subset of L s (R d ) when s ∈ N (see [14, p. 52] for examples of functions that belong to L 1 ([0, 1]) but not to C 1 ([0, 1]) in the particular case where d = 1). Furthermore, we define these function spaces on the subset E of R d as the restriction of their elements to E. As explained in [START_REF] Cohen | Numerical analysis of wavelet methods[END_REF]Remark 3.2.4], function spaces on E can be defined by restriction or, alternatively, in an intrinsic way, and both definitions coincide for fairly general domains E of R d .

Looking at function spaces on E as function spaces on R d restricted to E justifies the use of MRAs of L 2 (R d , λ) in our local analysis.

MRAs and smoothness analysis 13.2.1 Generalities

In order to estimate η on E, we will work with MRAs of L 2 (R d , λ) built upon a compactly supported scaling function ϕ. Multivariate MRAs will always be assumed to be obtained from a tensorial product of one-dimensional MRAs, as described in [10, §1.4, eq. (1.4.10)] and recalled below. We will denote by ϕ j,k (.) = 2 jd/2 ϕ(2 j .k) the translated and dilated version of ϕ with k ∈ Z d . As usual, we denote V j = Closure(Span{ϕ j,k , k ∈ Z d }), so that Closure(∪ j≥0 V j ) = L 2 (R d , λ) (where the closures are taken with respect to the L 2 (R d , λ)-metric). As we are interested in finer and finer approximations of an objective function as the sample size grows, we can in fact truncate the MRA at resolution scales 2 -j , j ≥ 0. In the sequel, we will still refer to it as a MRA.

Here, let us simply recall that, for any k = (k 1 , . . . , k d ) ∈ Z where we have written ψ (0) = ϕ, ψ (1) = ψ and ε = (ε 1 , . . . , ε d ).

Connection between MRAs and generalized Lipschitz spaces

The r-MRAs defined in Section 5.2 are intimately connected with generalized Lipschitz spaces. Assume we are given a r-MRA with r ∈ N and η ∈ L s (R d , M), where s ∈ (0, r) and M > 0.

Denote by P j η the projection of η onto V j and by R j η = η -P j η the corresponding remainder. Then, we have for all x ∈ R d , η(x) = P j η(x) + R j η(x) where R j η L∞(R d ,λ) ≤ M2 -js , as detailed in [10, Corollary 3.

This latter result happens to be useful in the proof of the lower bound (see Section 12.3). This is due to the fact that #S j (x) is constant on each open hypercube of 2 -j [Z d + (0, 1) d ] while it raises (r = 1) or drops (r ≥ 2) at their boundary. However, notice that it is only necessary to focus on the case where x ∈ Inter(Suppϕ j,k ), since we are interested in results that hold P X -almost surely. P X is indeed absolutely continuous with respect to the Lebesgue measure λ on R d (with density µ) and for any j ≥ 0, k ∈ Z d , λ(∂Suppϕ j,k ) = 0. Consequently

P X   j≥0,k∈Z d ∂Suppϕ j,k   = 0.
When working under (S1), we implicitly assume throughout the paper that

A = [0, 1] d \ j≥0,k∈Z d ∂Suppϕ j,k .
Notice that this problem does not occur under (CS2) where, by construction, x is always located inside H 0 (X ix ). Therefore, for any two (E, B(E))-measurable maps η 1 , η 2 , one can write

K (P η 1 , P η 2 ) = Ω log dP η 1 dP η 2 (ω) dP η 1 (ω) = 1 2 A dxµ(x) K -K duC K [(u -η 2 (x)) 2 -(u -η 1 (x)) 2 ]e -1 2 (u-η 1 (x)) 2 = 1 2 A dxµ(x)(η 1 (x) -η 2 (x)) 2 K -K duC K e -1 2 (u-η 1 (x)) 2 + A dxµ(x)(η 1 (x) -η 2 (x)) K -K duC K (u -η 1 (x))e -1 2 (u-η 1 (x)) 2 .
Now, notice first that

K -K duC K e -1 2 (u-η 1 (x)) 2 ≤ 2KC K .
Besides, eq. (10c) leads to 2 -jss ≤ 2 r n -s 2s+d . Finally, notice that . This concludes the proof of eq. ( 21) with

C 14 := 3 max(1, 3π 0 R d µ max ), [START_REF] Meyer | Wavelets and operators[END_REF] where C 10 is defined in eq. ( 38) above. Let us now turn to eq. ( 22) and choose δ n = t(n)n -s 2s+d . Notice now that

n 2s 2s+d δ 2 n ≥ t(n) 2
and 2R d k≥1 2 k(1+ϑ) exp(-C 11 t(n) 2 2 2(k-1) ) can be made as small as we want for n large enough. Finally, notice that

(log n) 2 δ -(1+ϑ) n n -κC ′ 6 ≤ C(log n) 2 t(n) -(1+ϑ) n s 2s+d (1+ϑ)-κC ′ 6
which goes to zero as soon as, say, κ > 1+ϑ 2C ′

6

. This concludes the proof with

C 16 := 2C * . ( 42
)
Proof of Theorem 10.2. Notice first that for all s > 0, L s (R d ) ⊃ C s (R d ) so that we can rely on the proof of [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF]Theorem 3.5]. This latter proof carries over word for word to the present setting after replacing ℓ 2 -balls by ℓ ∞ -balls in the definition of the support of µ.

Figure 1 :

 1 Figure 1: Description of the localization cells H and their relations to the Suppϕ j,k .

0Figure 2 :

 2 Figure 2: (S2) allows for A to be non-convex and eventually disconnected. (S2) E = R d and A belongs to A js , where

1

 1 Proof of the upper-bound results under (CS1) 12.1.1 Proof of Corollary 7.1

Lemma 12 . 1 .

 121 Let r ∈ N. Let ϕ be the Daubechies' scaling function of regularity r and S = {ν ∈ Z d : 2 -1 ∈ Suppϕ ν }. Then, there exists a strictly positive absolute constant c min such that

Proposition 12 . 8 .

 128 Let m be a constant such that m > 0 and fixz ∈ R d such that z ∈ B ∞ (2 -1 , m). Write S d := {k ∈ Z d : 2 -1 ∈ Suppϕ k },the set of indexes corresponding to the scaling functions whose support Suppϕ k contains the point 2 -1 ∈ R d . The scaling functions (ϕ k ) verify the local linear independence property in the sense that k∈S α k ϕ k = 0 on the domain B ∞ (z, m) if and only if α k = 0 for all k ∈ S.

[ 36 ,

 36 Corollaire 3]. Notice indeed that for d = 1, λ(Suppϕ k ) = R := 2r -1 and∪ k∈S Suppϕ k = [-R + 1, R]. Set 1 [a,b] = 0 and [a, b] = ∅ as soon as a > b. Now, k∈S α k ϕ k = 0 on [zm, z + m] implies that both restrictions 1 [-R+1,z-m] k∈S α k ϕ k and 1 [z+m,R] k∈S α k ϕ k belong to V 0 , according to [36, Proposition 1]. However z ∈ [1/2m, 1/2 + m], therefore λ([-R + 1, zm]) < R and λ([z + m, R]) < R, whichleads to a contradiction thanks to [36, Lemme 1, (ii)]. Therefore, both restrictions must be zero as well, which leads to k∈S α k ϕ k = 0 and thus α k = 0 for all k ∈ S, since the (ϕ k ) k∈Z have disjoint supports. The generalization to the d-dimensional case follows by induction as in the proof of Theorem 3.7.1 in [10]. Assume the property holds in dimension d -1 and let us work in dimension d. Let z ∈ B ∞ (2 -1 , m) and, for any x ∈ R d , write x = (x 1,d-1 , x d ), where x 1,d-1 is the element of R d-1 consisting of the first d -1 coordinates of x and x d is its last coordinate. Assume now that k∈S d α k ϕ k (x) = 0 on B ∞ (z, m). We can integrate this latter expression against a test function g(x 1,d-1 ) supported on B ∞ (z 1,d-1 , m) along the first d -1 dimensions. Using the fact that for all x ∈ R d and k

  d and x = (x 1 , . . . , x d ) ∈ R d , the multivariate scaling functions write asϕ j,k (x) = ϕ j,k 1 (x 1 ) . . . ϕ j,k d (x d ).Let us denote by ψ the univariate wavelet associated to the univariate scaling function ϕ. Then the multivariate wavelets ψ j,ν are indexed by j ≥ 0 and the double index ν = (ε, k) ∈ ∇ = [{0, 1} d \{(0, . . . , 0)}] × Z d and write asψ j,ν (x) = ψ (ε 1 ) j,k (x 1 ) . . . ψ (ε d ) j,k (x d ),

  3.1]. It is noteworthy that the above approximation results remain valid in the particular case where we work on the subset E of R d and consider η to be the restriction to E of an element of L s (R d ). Let us denote by {ϕ k : k ∈ Z d } ∪ {ψ j,ν : j ≥ 0, ν ∈ ∇} the Daubechies' wavelet basis associated to a r-MRA (see Section 13.2 for notations and[START_REF] Daubechies | Ten lectures on wavelets[END_REF] Chap. 5,[START_REF] Baraud | Model selection for regression on a random design[END_REF] for a detailed review of wavelet bases and [10, §1.4,Remark 1.4.5] for the construction of their multi-dimensional isotropic version). For any η ∈ L s (R d ), we write α k := η, ϕ k L 2 (R d ,λ) and β j,ν := η, ψ j,ν L 2 (R d ,λ) . Then, we have the following well-known norm equivalenceη L s (R d ) ≈ sup k∈Z d |α k | + supj≥0 2 j(s+ d 2 ) sup ν∈∇ |β j,ν |, s ∈ (0, r).

13. 3 A

 3 technical comment relative to the lattice structure of the MRA under (CS1) Assume we work under (CS1) with the Daubechies' r-MRA of L 2 (R d , λ). Let x ∈ [0, 1] d . Notice that the scaling functions ϕ j,k , k ∈ Z d are supported on hypercubes of the form Suppϕ j,k = 2 -j (N 1,k , N 2,k ), where N 1,k , N 2,k ∈ Z d . When doing estimation at point x at resolution 2 -j , we have to differentiate two cases according to whether x belongs to Inter(Suppϕ j,k ) or ∂Suppϕ j,k .

13. 4

 4 Proof of Proposition 12.10Proof of Proposition 12.10. For any two Borel subsets A and B of R and E, respectively, and any (E, B(E))-measurable map η, a straightforward computation leads toP η (Y ∈ A, X ∈ B) = B µ(x)dx A duC K e -12 (u-η(x)) 2 .

10 which

 10 goes to zero as soon as, say, κ > 1+ϑ 2C ′ 10

C 15 :

 15 = 2C * C 1+ϑ 14 2 r(1+ϑ) 2 + 2R d k≥1 2 k(1+ϑ) exp(-C 10 C 2 14 2 2(k-1) ) ,

  Corollary 10.1. Fix r ∈ N and assume we are in the binary classification setting. Assume moreover that (H r s ) and (MA) hold true. Consider the plug-in classifiers h js (.) = 1 {η js (.)≥ 1

	and h j (.) = 1 {η j (.)	(.)≥ 1 2 } . Then, we have	2 }
	sup
	P∈P(CS2,H r s ,MA)

1, we can use the plug-in classifier built upon η to obtain similar results as the ones given in [4,

Lemma 3.1]

for LPE based plug-in classifiers.

  ) the spaces of continuous and absolutely continuous functions on R d , respectively. Let us denote by . the Euclidean norm of R d , f a function defined on R d and write ∆ 1 h

	13 Appendix
	13.1 Generalized Lipschitz spaces

Here, we sum up relevant facts about Lipschitz and Besov spaces on R d as stated in [10, Chap. 3] for any d ∈ N and [14, Chap. 2, §9] for d = 1. Let us denote by C (R d ) and C (R d

Acknowledgement. The author would like to thank Dominique Picard for many fruitful discussions and suggestions. He would also like to acknowledge interesting conversations with Gérard Kerkyacharian. Finally, he would like to thank two anonymous referees and an associate editor whose constructive comments led to a full refactoring of the paper and largely contributed to improve it.

Therefore, it is enough to control the probability of deviation of η j (x) from η(x) on O x , conditionally on X ′ ix . It is controlled in exactly the same way as the probability of deviation of η @ j (x) from η(x) under (CS1), except that we now work with conditional probabilities and expectations with respect to X ′ ix . Interestingly, the random variable X ′ ix is independent of the points of D n since it is built upon the design points (X ′ i ) of D ′ n which are themselves independent of the points of D n . This is a key feature that makes theoretical computations tractable under (CS2) and allows to handle η in a similar way as η @ under (CS1). As announced above, Proposition 12.4 and Proposition 12.5 are the sole results that are not obviously true under (CS2). However we show below that they can indeed be extended to setting (CS2) without much trouble. Ultimately, this proves that, on the event O x and conditionally on X ′ ix , the probability of deviation of η j (x) from η(x) verifies Theorem 7.1. So that finally, it remains to put everything together to obtain the results announced in Theorem 9.1, which concludes the proof.

Let us now show how the proofs of Proposition 12.4 and Proposition 12.5 can be extended to setting (CS2), thanks to the local linear independence property of the scaling functions (see Proposition 12.8) and a compactness argument.

Proof of Proposition 12.4 under (CS2). The proof of Proposition 12.4 under (CS1) breaks down under (CS2) at boundary points of A. Eq. ( 28) is indeed not valid anymore under (CS2) since µ eventually cancels on the cell H 0 (X ′ ix ) centered in X ′ ix . Recall however that S j (H 0 ) = S = {ν ∈ Z d : 2 -1 ∈ Suppϕ ν } is a set of indexes which is independent of both x and j. Recall that all computations at point x are performed conditionally on X ′ ix under (CS2). Recall that we write w = w -X ′ ix + 2 -j-1 . Given the independence of X ′ ix from the points of D n , we can write

Thus, a direct application of Lemma 12.1 leads to

This concludes the proof with g min = µ min c min .

Recall that, for any y, z ∈ R d , we have the following relationships

Making a repeated use of them, we can write

Now remark that each of the four above sets define hyper-rectangles of R d . Denote by λ k the Lebesgue measure of R k and notice that λ

Therefore, we obtain

Consequently, we obtain immediately by induction that

Proof of the lower-bound

In this section, we show that the proof of Theorem 7.3 under both settings (CS1) and (CS2) hinges on the well-known arguments of the proof of the lower-bound in the uniform design case. The arguments that follow are for the most part standard. Nonetheless, we report them here for completeness.

Preliminary results

First recall the definition of the Kullback-Leibler divergence for two probabilities P and Q on some measurable space (Ω, F ):

Here we use a version of Fano's lemma that is due to [START_REF] Birgé | Gaussian model selection[END_REF]. It can be stated as follows Theorem 12.1 (Fano's Lemma). Let F be a σ-algebra on the space Ω.

Furthermore, we will need the following two Propositions that give upper bounds on the Kullback-Leibler divergence under specific sets of assumptions.

Proposition 12.9. Assume we work under (S2) and the Gaussian noise hypothesis (N2).

Then, for any two (E, B(E))-measurable maps η 1 , η 2 , we have

Proof. The proof is straightforward and can be found in [9, Lemma 3.3].

Proposition 12.10. Assume we work under any of the two settings (S1) and (S2) and the bounded noise assumption (N1). Assume moreover ξ to be independent of X and such that, for any Borel subset B of [-K, K],

Then for any two (E, B(E))-measurable maps η 1 , η 2 , we obtain

where B(E) stands for the Borel σ-field of E.

Proof. The proof is straightforward and hence reported to the Appendix.

In addition, notice that

Consequently, we end up with the desired result

Proof of the classification results

Proof of Proposition 10.1. Notice first that eq. ( 18) is a direct consequence of Theorem 9.1. The proof of eq. ( 19) follows the same lines as the proof of Theorem 7.2. The reader is therefore advised to read the latter proof before this one. Notice that

Let us denote the three terms on the rhs from top to bottom by I, II and III. I is upper bounded using eq. ( 18) above with j = j s and δ > 6 2 -jss max(1, 3π 0 R d µ max ). This leads to

where C ′ 10 and C 10 are such that

and C 6 is defined in eq. ( 25). Now, recall from the proof of Theorem 7.2 that, on the event {j ≤ j s }, II = 0 as soon as δ > 6t(n)2 js d 2 n -1 2 . Let us finally turn to III. With the same notations as in the proof of Theorem 7.2, we obtain III ≤ j∈Jn(js) k∈Jn(j-1)

where the last inequality uses Proposition 12.2 and the fact that #J n ≤ log n. Denote moreover,

and notice finally that C ′ 10 ∧ C 6 > C ′ 6 . Besides, recall from eq. (10c) that 2 -jss ≤ 2 r n -s 2s+d , so that for n large enough, 6 2 -jss max(1, 3π 0 R d µ max ) ≤ 62 r t(n)n -s 2s+d and a direct application of eq. (10c) leads to C 10 a n (j s ) ≥ C 11 n 2s 2s+d . This concludes the proof.

Proof of Theorem 10.1. It follows closely the proof of [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF]Theorem 3.1]. Consider the sets A k defined as

where we define k by

Notice now that we have |η -

where the before last inequality uses eq. ( 20), which is possible since 2 k-1 δ n ≤ 1 as long as k ≤ k, and the last one uses (MA). So that putting everything together, we obtain It remains to notice that 2 kδ n ≤ 1 to conclude the proof.

Proof of Corollary 10.1. The proof of eq. ( 21) and eq. ( 22) are straightforward consequences of Proposition 10.1 and Theorem 10.1. Start with eq. ( 21) and choose δ n = 32 -jss max(1, 3π 0 R d µ max ). Notice first that eq. (10a) leads to a n (j s )δ 2 n ≥ 9 max(1, 3π 0 R d µ max ) 2