Florian Dussap
email: florian.dussap@gmail.com

Nonparametric Multiple Regression by Projection on Non-compactly Supported Bases

Keywords: nonparametric estimation, nonparametric regression, hermite basis, model selection

We study the nonparametric regression estimation problem with a random design in R p with p ≥ 2. We do so by using a projection estimator obtained by least squares minimization. Our contribution is to consider non-compact estimation domains in R p on which we recover the function, and to provide a theoretical study of the risk of the estimator relative to a norm weighted by the distribution of the design. We propose a model selection procedure in which the model collection is random and takes into account the discrepancy between the empirical norm and the norm associated with the distribution of design. We prove that the resulting estimator automatically optimizes the bias-variance trade-off in both norms, and we illustrate the numerical performance of our procedure on simulated data.

Introduction

We consider the following random design regression model:

Y i = b(X X X i ) + ε i , i = 1, . . . , n,
where the variables X X X i ∈ R p are independent but not necessarily identically distributed, the noise variables ε i ∈ R are i.i.d. centered with finite variance σ 2 and independent from the X X X i s, and b : R p → R is a regression function. We seek to recover the function b on a domain A ⊂ R p from the observations (X X X i ,Y i ) i=1,...,n .

More precisely, we consider the following framework. We assume that the variance of the noise σ 2 is known. We assume that the variables X X X i are independent but not identically distributed, we call µ i the distribution of X X X i , but we do not assume that µ i is known. However, we fix ν a reference measure on A and we assume that µ := 1 n ∑ n i=1 µ i admits a bounded density with respect to ν, so that we have L 2 (A, µ) ⊂ L 2 (A, ν). In particular, this assumption implies that supp(µ) ⊂ A. Finally, we consider domains A ⊂ R p of the form A 1 ו • •×A p where A k ⊂ R and we consider a measure ν on A that is of the form ν 1 ⊗ • • • ⊗ ν p with ν k supported on A k . Our goal is to estimate the regression function b on the domain A and to control the expected error with respect to the norm ∥•∥ µ associated with the distribution of the X X X i s:

∀t ∈ L 2 (A, µ), ∥t∥ 2 µ := A t(x x x) 2 dµ(x x x) = 1 n n ∑ i=1 A t(x x x) 2 dµ i (x x x).
We can interpret the error with respect to this norm as a prediction risk: if X X X ′ 1 , . . . , X X X ′ n are independent copies of X X X 1 , . . . , X X X n , then we have:

∀ b estimator, ∥b -b∥ 2 µ = 1 n n ∑ i=1 E b(X X X ′ i ) -b(X X X ′ i ) 2 X X X 1 , . . . , X X X n ,
which is the mean quadratic error of a new observation drawn uniformly from one of the distributions µ i .

Nonparametric regression problems have a long history, and a large number of methods have been proposed. In this introduction, we focus on two main families of methods: kernel estimators and projection estimators. For reference books on the subject, see [START_REF] Efromovich | Nonparametric curve estimation: methods, theory and applications[END_REF] regarding the projection method and [START_REF] Györfi | A Distribution-Free Theory of Nonparametric Regression[END_REF] for the kernel method.

The classical estimator of [START_REF] Nadaraya | On Estimating Regression[END_REF] and [START_REF] Watson | Smooth Regression Analysis[END_REF] consists of a quotient of estimators b f / f , where b f and f are kernel estimators of the functions b f and f (the function f being the common density of the X X X i s in the i.i.d case). This estimator can also be interpreted as locally fitting a constant by averaging the Y i s, the locality being determined by the kernel, see the book of [START_REF] Györfi | A Distribution-Free Theory of Nonparametric Regression[END_REF] or [START_REF] Tsybakov | Introduction to nonparametric estimation[END_REF]. This method can then be generalized by replacing the local constant by a local polynomial, leading to the so-called local polynomial estimator.

The main drawback of the Nadaraya-Watson estimator is that it relies on an estimator of the density of the X X X i s. As such, the rate of convergence depends on the regularity of f , and two smoothing parameters have to be chosen. A popular solution is to choose the same bandwidth for both estimators using leave-one-out cross validation. This method works well in practice and has been proven consistent by [START_REF] Härdle | Optimal Bandwidth Selection in Nonparametric Regression Function Estimation[END_REF] (see also Chapter 8 in [START_REF] Györfi | A Distribution-Free Theory of Nonparametric Regression[END_REF]). Recently, [START_REF] Comte | On a Nadaraya-Watson estimator with two bandwidths[END_REF] have proposed to use the Penalized Comparison to Overfitting method (PCO), a bandwidth selection method developed by [START_REF] Lacour | Estimator Selection: a New Method with Applications to Kernel Density Estimation[END_REF] for kernel density estimation, to select separately the bandwidths of the numerator and the denominator of the Nadaraya-Watson estimator. Their estimator matches the performances of the single bandwidth CV estimator when the noise is high, but the latter is better when the noise is small. Other bandwidth selection methods exist such as plug-in or bootstrap; see [START_REF] Köhler | A Review and Comparison of Bandwidth Selection Methods for Kernel Regression: Review of Bandwidth Selection for Regression[END_REF] for an extensive survey and comparison of the different bandwidth selection methods for the local linear estimator.

Another approach is to use a projection estimator. The idea is to minimize a least squares contrast over finite-dimensional spaces of functions {S m m m : m m m ∈ M n } called models:

bm m m := arg min

t∈S m m m 1 n n ∑ i=1 Y i -t(X X X i ) 2 ,
the model collection M n being allowed to depend on the number of observations. This method overcomes the problems of the Nadaraya-Watson estimator: it does not need to estimate the density of the X X X i s, and only one model selection procedure is required. Moreover, it can provide a sparse representation of the estimator. This approach was developed in a fixed design setting by [START_REF] Birgé | Minimum Contrast Estimators on Sieves: Exponential Bounds and Rates of Convergence[END_REF], [START_REF] Barron | Risk bounds for model selection via penalization[END_REF] and [START_REF] Baraud | Model selection for regression on a fixed design[END_REF]. In particular, the papers of [START_REF] Baraud | Model selection for regression on a fixed design[END_REF][START_REF] Baraud | Model selection for regression on a random design[END_REF] provide a model selection procedure that optimizes the bias-variance compromise under weak assumptions on the moments of the noise distribution. They obtain an estimator that is adaptive both in the fixed and random design setting when the domain A is compact.

The non-compact case have been studied recently in the simple regression setting (p = 1) by Comte and Genon-Catalot (2020a,b). They use non-compactly supported bases, specifically the Hermite basis (supported on R) and the Laguerre basis (supported on R + ), to construct their estimator. Significant attention has been paid to these bases in the past years since they exhibit nice mathematical properties that are useful for solving inverse problems [START_REF] Mabon | Adaptive Deconvolution on the Non-negative Real Line: Adaptive deconvolution on R+[END_REF][START_REF] Comte | Laguerre and Hermite bases for inverse problems[END_REF][START_REF] Sacko | Hermite density deconvolution[END_REF]. Non-compactly supported bases also avoid issues concerning the choice of support. When A is compact, the theory assumes it is fixed a priori. In practice, however, the support is generally determined using the data, although this dependency between data and support is not taken into account in the theoretical development. Working with a non-compact domain, for example R or R + , allows us to bypass this issue.

Concerning the regression problem, difficulties arise when we go from the compact case to the non-compact case. When A is compact, it is usual to assume that the density of the X X X i s is bounded from below by some positive constant f 0 . In the noncompact case, this assumption fails. Instead, the study of the minimum eigenvalue of some random matrix must be done. This question has been studied in the simple regression case (p = 1) by [START_REF] Cohen | On the Stability and Accuracy of Least Squares Approximations[END_REF] by using the matrix concentration inequalities of [START_REF] Tropp | User-Friendly Tail Bounds for Sums of Random Matrices[END_REF]. However, their results are obtained under the assumption that the regression function is bounded by a known quantity and they do not provide a model selection procedure.

We make the following contributions in our paper. We extend the results of Comte and Genon-Catalot (2020a) to the multiple regression case (p ≥ 2) with more general assumptions on the design, and we improve their result on the oracle inequality under the empirical norm (see Theorem 2). Our work generalizes the results of [START_REF] Baraud | Model selection for regression on a random design[END_REF] to the non-compact case and improves their results in the compact case (see Theorem 3). We do so by combining the fixed design results of [START_REF] Baraud | Model selection for regression on a fixed design[END_REF] with a more refined study of the discrepancy between the empirical norm and the µ-norm.

This discrepancy is expressed in terms of the deviation of the minimum eigenvalue of a random matrix, of which we control the probability with the concentration inequalities of [START_REF] Tropp | User-Friendly Tail Bounds for Sums of Random Matrices[END_REF] and [START_REF] Gittens | Tail bounds for all eigenvalues of a sum of random matrices[END_REF]. Finally, our estimator is constructed as a projection estimator on a tensorized basis whose coefficients are computed using hypermatrix calculus and can be implemented in practice. This feasibility is illustrated in Section 5 which also shows that the procedure works well.

Outline of the paper In Section 2 we define the projection estimator. In Section 3 we study the probability that the empirical norm and the µ-norm depart from each other and we derive an upper bound on the µ-risk of our estimator. In Section 4 we propose a model selection procedure and we prove that it satisfies an oracle inequality both in empirical norm and in µ-norm. Finally, in Section 5 we study numerically the performance of our estimator. All the proofs are gathered in Section 7.

Notations

-E X X X := E[ • | X X X 1 , . . . , X X X n ], P X X X := P[ • | X X X 1 , . . . , X X X n ], Var X X X := Var( • | X X X 1 , . . . , X X X n ), where X X X = (X X X 1 , . . . , X X X n ).
-If π is a measure on A, we write ∥•∥ π and ⟨•, •⟩ π the norm and the inner product weighted by the measure π. -We denote by ⟨•, •⟩ n and ∥•∥ n the empirical inner product and the empirical norm1 , defined as ⟨t,

s⟩ n := 1 n ∑ n i=1 t(X X X i )s(X X X i ) and ∥t∥ 2 n := 1 n ∑ n i=1 t(X X X i ) 2 . If u ∈ R n is a vector, we also write ∥u∥ 2 n := 1 n ∑ n i=1 u 2 i .

Projection estimator

In our setting, the domain is a Cartesian product

A = A 1 × • • • × A p and ν = ν 1 ⊗ • • • ⊗ ν p where ν k is supported on A k .
For each i ∈ {1, . . . , p}, we consider (ϕ i j ) j∈N an orthonormal basis of L 2 (A i , dν i ) and we form an orthonormal basis of L 2 (A, dν) by tensorization:

∀ j j j ∈ N p , ∀x x x ∈ A, ϕ j j j (x x x) := (ϕ 1 j 1 ⊗ • • • ⊗ ϕ p j p )(x x x) := ϕ 1 j 1 (x 1 ) × • • • × ϕ p j p (x p ).
For m m m ∈ N p + , we set S m m m := Span(ϕ j j j : j j j ≤ m m m -1) and we write D m m m := m 1 • • • m p its dimension. We estimate b by minimizing a least squares contrast on S m m m : bm m m := arg min

t∈S m m m 1 n n ∑ i=1 Y i -t(X X X i ) 2 .
If we expand bm m m on the basis (ϕ j j j ) j j j∈N p , this problem can be written as:

bm m m = ∑ j j j≤m m m-1 â(m m m) j j j ϕ j j j , â(m m m) := arg min a a a∈R m ∥Y -Φ Φ Φ m m m × p a∥ 2 R n , (1)
where

Y := (Y 1 , . . . ,Y n ) ∈ R n and Φ Φ Φ m m m ∈ R n×m m m is defined as: ∀i ∈ {1, . . . , n}, ∀ j j j ≤ m m m -1, Φ Φ Φ m m m i, j j j := ϕ j j j (X X X i ).
Using Lemma 8 in Appendix, the problem (1) has a unique solution if and only if Φ Φ Φ m m m is injective and in that case:

â(m m m) = ( Φ Φ Φ * m m m × 1 Φ Φ Φ m m m ) -1 × p Φ Φ Φ * m m m × 1 Y = 1 n G -1 m m m × p Φ Φ Φ * m m m × 1 Y,
where

[ Φ Φ Φ * m m m ] j j j,i = [ Φ Φ Φ m m m ] i, j j j
and where G m m m is the Gram hypermatrix of (ϕ j j j ) j j j≤m m m-1 relatively to the empirical inner product ⟨•, •⟩ n :

∀ j j j, k k k ≤ m m m -1, G m m m j j j,k k k := ⟨ϕ j j j , ϕ k k k ⟩ n . Notice that Φ Φ Φ m m m is injective if and only if G m m m is invertible, that is if and only if ∥•∥ n is a norm on S m m m .
3 Bound on the risk of the estimator Let us start with the classical bias-variance decomposition of the empirical risk. In our context this result is given by the next Proposition.

Proposition 1 If G m m m is invertible, then we have:

E X X X ∥b -bm m m ∥ 2 n = inf t∈S m m m ∥b -t∥ 2 n + σ 2 D m m m n .
As a consequence, if G m m m is invertible a.s, then we have:

E∥b -bm m m ∥ 2 n ≤ inf t∈S m m m ∥b -t∥ 2 µ + σ 2 D m m m n .
Hereafter, we always assume that Ĝm m m is invertible a.s.

If we want to obtain a similar result for the µ-norm, we need to understand how the empirical norm can deviate from the µ-norm. More generally, we need to understand the relations between the different norms we have on the subspace S m m m (∥•∥ n , ∥•∥ µ , ∥•∥ ν and ∥•∥ ∞ ). It is well known that all norms are equivalent on finite dimensional spaces; our question concerns the constants in this equivalence. We introduce the following notation: if ∥•∥ α and ∥•∥ β are two norms on a space S, we define: Lemma 1 Let (S, ⟨•, •⟩ α ) be a d-dimensional Euclidean vector space equipped with an orthonormal basis (φ 1 , . . . , φ d ). Let ⟨•, •⟩ β be another inner product on E and let G be the Gram matrix of the basis (φ 1 , . . . , φ d ) relatively to ⟨•, •⟩ β , that is:

K α β (S) := sup
G := ⟨φ j , φ k ⟩ β 1≤ j,k≤d .
We have:

K β α (S) = ∥G∥ op = λ max (G), K α β (S) = ∥G -1 ∥ op = 1 λ min (G) .
The proof of Lemma 1 is identical to the proof of Lemma 3.1 in [START_REF] Baraud | Model selection for regression on a fixed design[END_REF], so we leave it out.

The next lemma provides a way to compute K ∞ α (S) from an orthonormal basis when ∥•∥ α is Euclidean. It is essentially the same as Lemma 1 in [START_REF] Birgé | Minimum Contrast Estimators on Sieves: Exponential Bounds and Rates of Convergence[END_REF].

Lemma 2 Let S be a space of bounded functions on A such that d := dim(S) is finite. Let ⟨•, •⟩ α be an inner product on S. If (ψ 1 , . . . , ψ d ) is an orthonormal basis of S, then we have:

K ∞ α (S) = d ∑ j=1 ψ 2 j ∞
.

The question we are interested in is how close are the norms ∥•∥ n and ∥•∥ µ on S m m m . Following a similar idea of [START_REF] Cohen | On the Stability and Accuracy of Least Squares Approximations[END_REF], let us define the event:

∀δ ∈ (0, 1), Ω m m m (δ ) := ∀t ∈ S m m m , ∥t∥ 2 µ ≤ 1 1 -δ ∥t∥ 2 n = K µ n (m m m) ≤ 1 1 -δ . (2)
The key decomposition of the µ-risk of bm m m is given by the following Proposition.

Proposition 2 For all δ ∈ (0, 1), we have:

E∥b -bm m m ∥ 2 µ ≤ 1 + 2 1 -δ K ∞ µ (m m m) (1 -δ )n ∧ 1 inf t∈S m m m ∥b -t∥ 2 µ + 2σ 2 D m m m (1 -δ )n + 2∥b∥ 2 µ P[Ω m m m (δ ) c ] + E K µ n (m m m)∥Y∥ 2 n 1 Ω m m m (δ ) c ,
where K µ n (m m m) and K ∞ µ (m m m) are given by Lemmas 1 and 2. We see that we need an upper bound on the probability of the event Ω m m m (δ ) c . The following proposition is a consequence of the matrix Chernoff bound of [START_REF] Tropp | User-Friendly Tail Bounds for Sums of Random Matrices[END_REF] (Theorem 5 in Appendix) .

Proposition 3 For all δ ∈ (0, 1), we have:

P[Ω m m m (δ ) c ] ≤ D m m m exp -h(δ ) n K ∞ µ (m m m)
, where h(δ

) := δ + (1 -δ ) log(1 -δ ) and K ∞ µ (m m m) is given by Lemma 2.
Remark 1 The quantity K ∞ µ (m m m) is unknown but we have the following upper bound using Lemmas 1 and 2:

K ∞ µ (m m m) ≤ K ∞ ν (m m m) K ν µ (m m m) = sup x x x∈A ∑ j j j≤m m m-1 ϕ j j j (x x x) 2 ∥G -1 m m m ∥ op .
The quantity ∥G -1 m m m ∥ op is still unkown but can be estimated by plugging in G m m m .

Comte and Genon-Catalot (2020a) show in their Proposition 8 that, when one uses the Hermite or the Laguerre basis, the inverse of the Gram matrix is unbounded (it satisfies ∥G -1 m ∥ op ≳ √ m), while it is bounded in the compact case:

∥G -1 m m m ∥ op = sup t∈S m m m \{0} ∥t∥ 2 ν ∥t∥ 2 µ ≤ 1 f 0 , (3)
where f 0 is a positive lower bound of the covariates density. Hence, the least squares minimization problem will become highly unstable as the dimension of the projection space grows. That is why a form of regularization is needed if we want to control the µ-risk of the estimator. For α a positive constant, let us consider the following model collection:

M (1) n,α := m m m ∈ N p + K ∞ ν (m m m) ∥G -1 m m m ∥ op ∨ 1 ≤ α n log n . ( 4
)
Gathering Propositions 2 and 3, we obtain the following bound on the µ-risk of bm m m when m m m belongs to M

(1) n,α .

Theorem 1 Let us assume that b ∈ L 2r (µ) for some r ∈ (1, +∞] and let r ′ ∈ [1, +∞) be the conjugated index of r, that is:

1 r + 1 r ′ = 1. For all α ∈ (0, 1 2r ′ +1
) and for all m m m ∈ M

(1) n,α we have:

E∥b -bm m m ∥ 2 µ ≤ C n (α, r ′ ) inf t∈S m m m ∥b -t∥ 2 µ +C ′ (α, r ′ ) σ 2 D m m m n + C ′′ b, σ 2 , α, r n log n ,
where the constants C n (α, r ′ ) and C ′ (α, r ′ ) are given by:

C n (α, r ′ ) := 1+ 2 1 -δ (α, r ′ ) α 1 -δ (α, r ′ ) log n ∧ 1 , C ′ (α, r ′ ) := 2 1 -δ (α, r ′ ) ,
where δ (α, r ′ ) ∈ (0, 1) tends to 1 as α tends to 1 2r ′ +1 , and where C ′′ b, σ 2 , α, r is defined by (18).

Remark 2 Let us make some statements concerning the behavior of C n (α, r ′ ) and C ′ (α, r ′ ):

-C n (α, r ′ ) is bounded relatively to n; -C n (α, r ′ ) ≥ 1 and C ′ (α, r ′ ) ≥ 2; -as α → 1 2r ′ +1
with n fixed, C n (α, r ′ ) and C ′ (α, r ′ ) tend to +∞; as n → +∞ with α and r ′ fixed, C n (α, r ′ ) tends to 1.

Adaptive estimator

We consider the empirical version of the model collection M n,α defined by (4):

M (1) n,β := m m m ∈ N p + K ∞ ν (m m m) ∥ G -1 m m m ∥ op ∨ 1 ≤ β n log n , with β a positive constant. We choose m m m 1 ∈ M (1)
n,β by minimizing the following penalized least squares criterion:

m m m 1 := arg min m m m∈ M (1) n,β -∥ bm m m ∥ 2 n + (1 + θ )σ 2 D m m m n , θ > 0. ( 5
)
Based on a result of [START_REF] Baraud | Model selection for regression on a fixed design[END_REF] for fixed design regression, we prove that b m m m 1 automatically optimizes the bias-variance compromise in empirical norm on M n,α , up to a constant and a remainder term.

Theorem 2 If b ∈ L 2r (µ) for some r ∈ (1, +∞] and if E|ε 1 | q is finite for some q > 6, then there exists a constant α β ,r ′ > 0 depending on β and r ′ (the conjugated index of r) such that for all α ∈ (0, α β ,r ′ ), the following upper bound on the risk of the estimator b m m m 1 with m m m 1 defined by (5) holds:

E∥b -b m m m 1 ∥ 2 n ≤ C(θ ) inf m m m∈M (1) n,α inf t∈S m m m ∥b -t∥ 2 µ + σ 2 D m m m n + σ 2 Σ (θ , q) n + R n ,
where C(θ ) := (2 + 8θ -1 )(1 + θ ), and where:

Σ (θ , q) := C ′′ (θ , q) E|ε 1 | q σ q ∑ m m m∈N p + D -( q 2 -2) m m m , R n := C ′ (∥b∥ L 2r (µ) , σ 2 ) (log n) (p-1)/r ′ n κ(α,β )/r ′ , with κ(α, β ) a positive constant satisfying κ(α,β ) r ′ > 1 and κ(α,β ) r ′ → 1 as α → α β ,r ′ .
Remark 3 The term Σ (θ , q) is finite if q > 6. Indeed, let 2ε := ( q 2 -2) -1 > 0, we have:

∑ m m m∈N p + D -( q 2 -2) m m m = +∞ ∑ d=1 Card m m m ∈ N p + D m m m = d × d -( q 2 -2) ≤ +∞ ∑ d=1 o(d ε ) d 1+2ε < +∞,
where we use Theorem 7 in Appendix.

Remark 4 The constant α β ,r ′ is increasing with β and goes from 0 to 1 2r ′ +1 . It is also decreasing with r ′ (so increasing with r) and tends to 0 as r ′ → +∞ (as r → 1).

To transfer the previous adaptive result from the empirical norm into the µ-norm, we use once again concentration inequalities on the matrix G m m m . However, we need to make a distinction between the compact case and the non-compact case. Indeed, when A is compact, we can make the usual assumption that the density dµ dν is bounded from below and apply the matrix Chernoff bound of [START_REF] Gittens | Tail bounds for all eigenvalues of a sum of random matrices[END_REF], see Lemma 6. This lemma relies critically on the "bounded from below" assumption so it cannot work in the non-compact case.

To handle the non-compact case, we make use of the matrix Bernstein bound of Tropp ( 2012) instead (Theorem 6 in appendix), see Lemma 7. This inequality is different from the matrix Chernoff bounds we have used so far, so we have to consider smaller model collections to make it work. In the following, we consider two cases:

1. Compact case. We assume that there exists f 0 > 0 such that for all x ∈ A, dµ dν (x) > f 0 . In that case, G m m m is always invertible and we have ∥G -1 m m m ∥ op ≤ 1 f 0 , see (3). 2. General case. We consider smaller model collections:

M (2) n,α := m m m ∈ N p + K ∞ ν (m m m) ∥G -1 m m m ∥ 2 op ∨ 1 ≤ α n log n , M (2)
n,β := m m m ∈ N p + K ∞ ν (m m m) ∥ G -1 m m m ∥ 2 op ∨ 1 ≤ β n log n ,
where α and β are positive constants and we choose m

m m 2 ∈ M (2) n,β as: m m m 2 := arg min m m m∈ M (2) n,β -∥ bm m m ∥ 2 n + (1 + θ )σ 2 D m m m n , θ > 0. ( 6
)
Theorem 3 Let r ∈ (1, +∞], let r ′ ∈ [1, +∞) be its conjugated index and let us assume that b belongs to L 2r (µ) and that E|ε 1 | q is finite for some q > 6.

• Compact case. Let f 0 > 0 such that dµ dν (x) ≥ f 0 for all x ∈ A, there exists β f 0 ,r ′ > 0 such that for all β ∈ (0, β f 0 ,r ′ ), there exists α β ,r ′ > 0 such that for all α ∈ (0, α β ,r ′ ), the following upper bound on the risk of the estimator b m m m 1 with m m m 1 defined by (5) holds:

E∥b -b m m m 1 ∥ 2 µ ≤ C(θ , β , r) inf m m m∈M (1) n,α inf t∈S m m m ∥b -t∥ 2 µ + σ 2 D m m m n +C ′ (β , r)σ 2 Σ (θ , q) n + R n ,
where the remainder term is given by:

R n = C ′′ ∥b∥ L 2r (µ) , σ 2 , β , r n -κ(α,β ) r ′ (log n) p-1 r ′ + n -λ (β ,r, f 0 ) (log n) p-1 r ′ -1 , with λ (β , r, f 0 ) > 1 and κ(α,β ) r ′ > 1. • General case. Let B := (∥ dµ dν ∥ ∞ + 2 3 ) -1
, there exists β B,r ′ > 0 such that for all β ∈ (0, β B,r ′ ), there exists αβ,r ′ > 0 such that for all α ∈ (0, αβ,r ′ ), the following upper bound on the risk of the estimator b m m m 2 with m m m 2 defined by (6) holds:

E∥b -b m m m 2 ∥ 2 µ ≤ C(θ , β , r) inf m m m∈M (2) n,α inf t∈S m m m ∥b -t∥ 2 µ + σ 2 D m m m n +C ′ (β , r)σ 2 Σ (θ , q) n + R n ,
where the remainder term is given by:

R n = C ′′ ∥b∥ L 2r (µ) , σ 2 , β , r n -κ(α,β ) r ′ (log n) p-1 r ′ + n -λ (β ,r,B) (log n) p-1 r ′ -1 , with λ (β , r, B) > 1 and κ(α,β ) r ′ > 1.
This result shows that there is a range of values for the constant β that depends on the integrability of b and on f 0 (compact case) or ∥ dµ dν ∥ ∞ (general case), such that for the µ-norm, the estimator b m m m automatically optimizes the bias-variance trade-off (up to a constant and a rest) on M n,α for all α in a range that depends on β .

Remark 5 Theorem 3 improves previous results in the literature:

1. In the compact case, we improve the result of [START_REF] Baraud | Model selection for regression on a random design[END_REF]. Indeed in this article, the model collections considered are built by picking an "envelope model", that is a linear space S n with finite dimension N n , whose all models are a subspace. Their assumptions concern the space S n : they assume that K ∞ ν (S n ) ≤ C 2 N n for some constant C > 0 and they require that N n ≤ C -1 n/(log n) 3 . In comparison, our procedure avoids the choice a priori of an envelope model, and uses a looser constraint on the dimension of the models. 2. In the non-compact case, we extend the results of Comte and Genon-Catalot (2020a) to the case p ≥ 2 without losing much on the assumptions: their result requires a moment of order 6 on the noise whereas our result is obtained with a moment of order q, with q > 6. We also generalize their result by considering a non i.i.d. design and by using a more general moment assumption on the regression function.

Remark 6 (Unknown variance) During all of our work, we assume that σ 2 is known.

To handle the case of an unknown variance, we can use the same method proposed by [START_REF] Baraud | Model selection for regression on a fixed design[END_REF] in the fixed design setting. Using a residual least-squares estimator of σ 2 in the penalized criterion for choosing the model, they prove (Theorem 6.1) that the resulting estimator of the regression function satisfies an oracle inequality.

Starting from Baraud's result, and using the same arguments we used in this paper, we think one can obtain an oracle inequality for a projection estimator, in the random design framework with unknown variance. We omit such development for the sake of conciseness.

Numerical illustrations

In this section, we compare our estimator with the Nadaraya-Watson estimator on simulated data in the case p = 1 and p = 2.

Regression function We consider the following regression functions:

1. b 1 (x) = exp((x -1) 2 ) + exp((x + 1) 2 ), 2. b 2 (x) := 1 1+x 2 , 3. b 3 (x) := x cos(x), 4. b 4 (x) := |x|, 5. b 5 (x 1 , x 2 ) := exp(-1 2 [(x 1 -1) 2 + (x 2 -1) 2 ]) + exp(-1 2 [(x 1 + 1) 2 + (x 2 + 1) 2 ]), 6. b 6 (x 1 , x 2 ) := 1/(1 + x 2 1 + x 2 2 ), 7. b 7 (x 1 , x 2 ) := cos(x 1 ) sin(x 2 ), 8. b 8 (x 1 , x 2 ) := |x 1 x 2 |.
The functions b 2 and b 6 are smooth bounded functions and have a unique maximum at 0, so they should be an easy case. The functions b 1 and b 5 are smooth and bounded with two maximums. The functions b 3 and b 7 are smooth oscillating functions. Finally the functions b 4 and b 8 are not smooth nor bounded, and should be a harder case.

Distribution of X X X For the sake of simplicity, we consider the case where X X X 1 , . . . , X X X n are i.i.d. and have a density with respect to Lebesgue measure (i.e. ν = Leb). For the case p = 1, we consider the following distributions: X ∼ N (0, 1), and X ∼ Laplace. Both distributions are symmetric and centered at 0, but the normal distribution is more concentrated around its mean than the Laplace distribution. For the case p = 2, we use independent marginals for the distribution of the covariates: X X X ∼ N (0, 1) ⊗ N (0, 1), and X X X ∼ Laplace ⊗ Laplace.

Noise distribution We consider the normal distribution: ε ∼ N (0, σ 2 ). The variance σ 2 is chosen such that the signal-to-noise ratio is the same for each choice of regression function and distribution of X X X, where we define the signal-to-noise ratio as:

SNR := ∥b∥ 2 µ σ 2 .
We consider the following values: SNR = 2 (High noise), and SNR = 20 (Low noise).

Parameters of the projection estimator Since the distributions of X X X are supported on R or R 2 , we choose the Hermite basis. The Hermite functions are defined as:

ϕ j (x) := c j H j (x) e -x 2
2 , H j (x) := (-1) j e x 2 d j dx j e -x 2 , c j := 2 j j!

√ π -1/2 .
and form a basis of L 2 (R). We form a basis of L 2 (R 2 ) by tensorizing the Hermite basis as explained in Section 2. We choose the parameter m m m with the model selection procedure (6). This procedure requires two additional parameters: the constant θ in the penalty and the constant β in the model collection M

(2) n,β . We choose β such that the model collection M

(2) n,β is not too small, especially for small sample sizes. Indeed, we find that the operator norm ∥ G -1 m m m ∥ op can grow very fast with m m m, which can result in model collections with very few models. In our case, we choose β = 10 4 .

The constant κ := 1 + θ in front of the penalty is chosen following the "minimum penalty heuristic" [START_REF] Arlot | Data-driven Calibration of Penalties for Least-Squares Regression[END_REF]. On several preliminary simulations, we compute the selected dimension D m m m as a function of κ and we find κ min such that for κ < κ min the dimension is too high and for κ > κ min it is acceptable. Then, we choose κ ⋆ = 2κ min . In our case, we find κ ⋆ = 2 when p = 1 and p = 2.

Nadaraya-Watson estimator

Let us define the Nadaraya-Watson estimator in the case p = 1. For all h ∈ (0, 1), let K h be the pdf of the N (0, h) distribution. The Nadaraya-Watson estimator is defined as:

∀x ∈ R, bNW h (x) := ∑ n i=1 Y i K h (x -X i ) ∑ n i=1 K h (x -X i )
.

The bandwidth h is selected by leave-one-out cross validation, that is:

ĥ := arg min h n ∑ i=1 Y i -bNW h,-i (X i ) 2 ,
where bNW h,-i is the Nadaraya-Watson estimator computed from the data set:

(X j ,Y j ) : j ∈ {1, . . . n} \ {i} .
In the case p = 2, the definition of the estimator is the same but with a couple of bandwidths h h h = (h 1 , h 2 ) ∈ (0, 1) 2 , and with K h h h the pdf of the N 2 (0 0 0, H) distribution, where

H := diag(h 1 , h 2 ).
Computation of the risk We consider samples of size n = 250 and n = 1000 in the case p = 1, and samples of size n = 500 and n = 2000 in the case p = 2. For each choice of regression function, distribution of X X X and SNR, we generate N = 100 samples of size n. For each sample, we compute the Hermite projection estimator and the Nadaraya-Watson estimator, then we compute the relative µ-error of the estimators, that is:

relative error := ∥ b -b∥ 2 µ ∥b∥ 2 µ = R p | b(x x x) -b(x x x)| 2 f (x x x) dx x x R p b(x x x) 2 f (x x x) dx x x
, where f is the density of the distribution µ. We compute an approximation of these integrals: we consider a compact domain I × I with I an interval such that P[X ∈ I] = 95% in the case p = 1 and P[X X X ∈ I × I] = 95% in the case p = 2. Then, we consider a discretization with 200 points of I. In the case p = 1, we use Simpson's rule with this discretization of I to approximate the integrals. In the case p = 2, we approximate the integrals by a sum over the grid of I × I:

R 2 b(x x x) -b(x x x) 2 f (x x x) dx x x ≈ 200 ∑ i=1 200 ∑ j=1 b(x 1,i , x 2, j ) -b(x 1,i , x 2, j ) 2 f (x 1,i , x 2, j )∆ 2 ,
where ∆ is the discretization step.

Results

In the case p = 1, we show our results on Table 1. First of all, we see that the results are superior when X has a Normal distribution compared to a Laplace distribution. This can be explained by the fact that the Laplace distribution is less concentrated around 0 than the normal distribution, so the X i s are more scattered and the mu-risk covers a larger range. In addition, in the normal setting, we see that the Hermite estimator is better than the Nadaraya- For each distribution of X X X, regression function, SNR and n, we display the estimated relative µ-risk over N = 100 samples with a 95% confidence interval, multiplied by 100. For the projection estimator, we display the mean selected dimension, and for the Nadaraya-Watson estimator, we display the mean selected bandwidths.

setting, the Hermite estimator is still better for b 1 and b 2 , but for b 3 it has similar performances as the Nadaraya-Watson estimator. For estimating b 4 , the latter is better, although the difference becomes small as n increases.

In the case p = 2, we show our results on Table 2. In the normal setting, the Hermite projection estimator is better for estimating b 5 , b 6 and b 7 . For b 8 , its performances are worse than the kernel estimator on small samples but they are equivalent on large samples. In the Laplace setting, our estimator is better for estimating b 5 and b 6 , but it is worse for estimating b 7 . Moreover, the Hermite estimator has very poor performances for estimating b 8 . We think that the functions b 7 and b 8 are hard to approximate with the Hermite basis, so that the Hermite projection estimator performs poorly. This can be seen by looking at the mean selected dimension, which grows quickly as n grows, showing that the estimator needs a large number of coefficients to reconstruct the regression function. This is especially true for b 8 , as it is a non differentiable and unbounded function.

In addition, we observe that the Hermite estimator is faster to compute than the Nadaraya-Watson estimator with leave-one-out cross validation. The difference is small when n is small, but for example, when n = 2000 and p = 2, the Hermite estimator is about 3 time faster. In conclusion, the Hermite projection estimator is a good alternative to the Nadaraya-Watson estimator.

Concluding remark

In this paper, we have considered the nonparametric regression problem with a random design. The covariates are assumed to be independent but not identically distributed, and the variance of the noise is assumed to be known. We estimate the regression function on a non-compact domain of R p with a projection estimator, using tensorised orthonormal bases. The projection space is chosen by a penalized criterion, as in [START_REF] Birgé | Minimum Contrast Estimators on Sieves: Exponential Bounds and Rates of Convergence[END_REF] and [START_REF] Baraud | Model selection for regression on a fixed design[END_REF]. Our model collection depends on the design, and is thus random. Indeed, we consider subspaces S m m m on which the operator norm of the Gram hypermatrix associated to the least squared minimization problem is constrained. This constraint on the operator norm comes from a refined study of the discrepancy between the norms ∥•∥ n and ∥•∥ µ on S m m m . This study relies on Matrix concentration inequalities of [START_REF] Tropp | User-Friendly Tail Bounds for Sums of Random Matrices[END_REF] and [START_REF] Gittens | Tail bounds for all eigenvalues of a sum of random matrices[END_REF], as it has been suggested by the work of [START_REF] Cohen | On the Stability and Accuracy of Least Squares Approximations[END_REF]. Doing so, we obtain oracle bounds for the selected estimator, in both norms. Our work extends and improves the results of [START_REF] Baraud | Model selection for regression on a random design[END_REF] and Comte and Genon-Catalot (2020a), as explained by Remark 5.

Different extension of our work can be pursued. A natural extension would be to consider the heteroskedastic regression model, in which the observations (X X X i ,Y i ) satisfy:

Y i = b(X X X i ) + σ (X X X i )ε i ,
were ε i s have unit variance. Using the same projection estimator, Comte and Genon-Catalot (2020b) have obtained similar results for this model in the one-dimensional case. The extension to the multivariate case could be done in two ways. The first way would be to generalize the fixed design results of [START_REF] Baraud | Model selection for regression on a fixed design[END_REF] to the case of noise variables with different variance, and then to apply the same arguments we used in this paper to deduce the results for the random design setting. The second way would be be to follow the approach of Comte and Genon-Catalot (2020b), that is based on Talagrand's inequality, and to see if it can be extended to the multivariate case. Another extension of our work would be to investigate the use of more general approximation spaces S m , as does [START_REF] Baraud | Model selection for regression on a random design[END_REF]. We want to known if the same method we used could handle approximation spaces that are not constructed from an orthonormal basis. A typical example we have in mind is splines approximation. We suspect that our results on the comparison between the norms ∥•∥ n and ∥•∥ µ still hold in this context, so that adaptive strategies could be derived from it.

Proofs

Proofs of Section 2

Proof (Proposition 1) Let Π

(n) m m m be the projector on S m m m for the empirical inner product. We have the decomposition:

E X X X ∥b -bm m m ∥ 2 n = ∥b -Π (n) m m m b∥ 2 n + E X X X ∥ bm m m -Π (n) m m m b∥ 2 n = inf t∈S m m m ∥b -t∥ 2 n + E X X X ∥Π (n) m m m ε ε ε∥ 2 n = inf t∈S m m m ∥b -t∥ 2 n + σ 2 Tr Π (n) m m m n = inf t∈S m m m ∥b -t∥ 2 n + σ 2 D m m m n .
Taking the expected value in this equality, we obtain:

E∥b -bm m m ∥ 2 n = E inf t∈S m m m ∥b -t∥ 2 n + σ 2 D m m m n ≤ inf t∈S m m m E∥b -t∥ 2 n + σ 2 D m m m n = inf t∈S m m m E∥b -t∥ 2 µ + σ 2 D m m m n . ⊓ ⊔

Proofs of Section 3

Proof (Lemma 2) Let x ∈ A and let t = ∑ d j=1 a j ψ j ∈ S. The family of functions

(ψ 1 , • • • , ψ d ) is orthonormal with respect to ⟨•, •⟩ α ,
so by the Cauchy-Schwarz inequality we have:

t 2 (x) = d ∑ j=1 a j ψ j (x) 2 ≤ d ∑ j=1 a 2 j d ∑ j=1 ψ 2 j (x) = ∥t∥ 2 α d ∑ j=1 ψ 2 j (x),
with equality if (α 1 , . . . , α d ) is proportional to (ψ 1 (x), . . . , ψ d (x)). Hence we have:

d ∑ j=1 ψ 2 j (x) = sup t∈S\{0} t 2 (x) ∥t∥ 2 α .
Taking the supremum for x ∈ A, we obtain:

sup x∈A d ∑ j=1 ψ 2 j (x) = sup x∈A sup t∈S\{0} t 2 (x) ∥t∥ 2 α = sup t∈S\{0} sup x∈A t 2 (x) ∥t∥ 2 α ,
that is:

d ∑ j=1 ψ 2 j ∞ = sup t∈S\{0} ∥t∥ 2 ∞ ∥t∥ 2 α =: K ∞ α (S).

⊓ ⊔

To prove Proposition 3 and Theorem 2, we need the following lemma.

∀ j, k ∈ {1, . . . , D m m m }, H m m m j,k := ⟨ψ j , ψ k ⟩ n and H m m m j,k := ⟨ψ j , ψ k ⟩ µ .
For all δ ∈ (0, 1) we have:

P λ min ( H m m m ) ≤ (1 -δ )λ min (H m m m ) ≤ D m m m exp -h(δ ) nλ min (H m m m ) K ∞ α (m m m)
, with h(δ ) := δ + (1δ ) log(1δ ) and where K ∞ α (m m m) is given by Lemma 2.

Proof We use Theorem 5 in Appendix. Indeed, H m m m can be written as a sum Z 1 + . . . + Z n where:

∀ j, k ∈ {1, . . . , D m m m }, Z i j,k := 1 n ψ j (X X X i )ψ k (X X X i ),
so we have using Lemma 2:

λ max (Z i ) = ∥Z i ∥ op = 1 n D m m m ∑ k=1 ψ k (X X X i ) 2 ≤ 1 n D m m m ∑ k=1 ψ 2 k ∞ = 1 n K ∞ α (m m m).
Therefore, applying inequality (29) of Theorem 5 with

µ min = λ min (H m m m ) and R = 1 n K ∞ α (m m m) yields: P λ min ( H m m m ) ≤ (1 -δ )λ min (H m m m ) ≤ D m m m exp -h(δ ) nλ min (H m m m ) K ∞ α (m m m) . ⊓ ⊔ since K µ n (m m m) ≤ 1 1-δ on the event Ω m m m (δ ), see (2). Let Π (n)
m m m be the empirical projector on S m m m , we have:

∥b (n) m m m -b (µ) m m m ∥ 2 n = Π (n) m m m b -b (µ) m m m 2 n ≤ ∥b -b (µ) m m m ∥ 2 n .
Thus, we have shown:

E ∥b (n) m m m -b (µ) m m m ∥ 2 µ 1 Ω m m m (δ ) ≤ 1 1 -δ E∥b -b (µ) m m m ∥ 2 n = 1 1 -δ ∥b -b (µ) m m m ∥ 2 µ . (9) Secondly, let g := b -b (µ) m m m and let Π (n)
m m m be the empirical projector on S m m m we have:

E ∥b (n) m m m -b (µ) m m m ∥ 2 µ 1 Ω m m m (δ ) = E ∥Π (n) m m m g∥ 2 µ 1 Ω m m m (δ ) .
Let (ψ 1 , . . . , ψ D m m m ) be an orthonormal basis of S m m m for the inner product ⟨•, •⟩ µ , we have:

Π (n) m m m g = arg min t∈S m m m ∥g -t∥ 2 n = D m m m ∑ j=1 c ⋆ j ψ j , c ⋆ := arg min c∈R Dm m m ∥g -Ψ m m m c∥ 2 R n ,
where Ψ m m m ∈ R n×D m m m is the matrix defined by [Ψ m m m ] i, j := ψ j (X X X i ), and where g is the vector g(X X X 1 ), . . . , g(X X X n ) ∈ R n . By Lemma 8, c ⋆ is given by:

c ⋆ = (Ψ * m m m Ψ m m m ) -1 Ψ * m m m g = 1 n H -1 m m m Ψ * m m m g,
where H m m m is the Gram matrix of (ψ 1 , . . . , ψ D m m m ) relatively to the empirical inner product. Using Lemma 1, we get:

Π (n) m m m g 2 µ = c ⋆ 2 R Dm m m ≤ H -1 m m m 2 op 1 n Ψ * m m m g 2 R Dm m m = K µ n (m m m) 2 D m m m ∑ j=1 ⟨g, ψ j ⟩ 2 n .
Hence, on the event Ω m m m (δ ) we obtain:

Π (n) m m m g 2 µ 1 Ω m m m (δ ) ≤ 1 (1 -δ ) 2 D m m m ∑ j=1 ⟨g, ψ j ⟩ 2 n . Since g = b -b (µ) m m m is orthogonal to ψ 1 , . . . , ψ D m m m relatively to the inner product ⟨•, •⟩ µ , we have E[⟨g, ψ j ⟩ n ] = ⟨g, ψ j ⟩ µ = 0, so we get: E D m m m ∑ k=1 ⟨g, ψ k ⟩ 2 n = D m m m ∑ k=1 Var ⟨g, ψ k ⟩ n = 1 n 2 n ∑ i=1 D m m m ∑ j=1 Var g(X X X i )ψ j (X X X i ) = 1 n 2 n ∑ i=1 E g(X X X i ) 2 D m m m ∑ j=1 ψ j (X X X i ) 2 ≤ 1 n 2 n ∑ i=1 E g(X X X i ) 2 sup x∈A D m m m ∑ j=1 ψ j (x) 2 = 1 n ∥g∥ 2 µ K ∞ µ (m m m) = K ∞ µ (m m m) n ∥b -b (µ) m m m ∥ 2 µ ,
where the last equality comes from Lemma 2. Hence we have shown:

E ∥b (n) m m m -b (µ) m m m ∥ 2 µ 1 Ω m m m (δ ) ≤ 1 (1 -δ ) 2 K ∞ µ (m m m) n ∥b -b (µ) m m m ∥ 2 µ . (10)
Combining ( 9) and ( 10) yields:

E ∥b (n) m m m -b (µ) m m m ∥ 2 µ 1 Ω m m m (δ ) ≤ 1 1 -δ ∥b -b (µ) m m m ∥ 2 µ 1 ∧ K ∞ µ (m m m) (1 -δ )n . ( 11
)
For the second term in ( 7), we have:

E ∥b -bm m m ∥ 2 µ 1 Ω m m m (δ ) c ≤ 2∥b∥ 2 µ P[Ω m m m (δ ) c ] + 2 E ∥ bm m m ∥ 2 µ 1 Ω m m m (δ ) c .
We have the following upper bound on

∥ bm m m ∥ 2 µ : ∥ bm m m ∥ 2 µ ≤ K µ n (m m m) ∥ bm m m ∥ 2 n ≤ K µ n (m m m) ∥Y∥ 2 n , (12)
where the last inequality comes from the fact that bm m m is the empirical projection of Y.

Hence, we get:

E ∥b -bm m m ∥ 2 µ 1 Ω m m m (δ ) c ≤ 2∥b∥ 2 µ P[Ω m m m (δ ) c ] + 2 E K µ n (m m m) ∥Y∥ 2 n 1 Ω m m m (δ ) c . ( 13
)
The inequality of Proposition 2 is obtained using ( 8), ( 11) and ( 13) in ( 7). ⊓ ⊔

Proof (Theorem 1) Let m m m ∈ M (1)
n,α and let δ ∈ (0, 1) (we choose it later in the proof). By Remark 1, we have by definition of M

(1) n,α :

K ∞ µ (m m m) ≤ K ∞ ν (m m m)∥G -1 m m m ∥ op ≤ α n log n , ( 14
)
so Proposition 2 yields:

E∥b -bm m m ∥ 2 µ ≤ C n (δ , α) inf t∈S m m m ∥b -t∥ 2 µ +C ′ (δ )σ 2 D m m m n + R n , with C n (α, δ ) := 1 + 2 1-δ α (1-δ ) log n ∧ 1 , C ′ (δ ) := 2 1-δ and: R n := 2∥b∥ 2 µ P[Ω m m m (δ ) c ] + E K µ n (m m m)∥Y∥ 2 n 1 Ω m m m (δ ) c .
For the first term in R n , we apply Proposition 3 with ( 14):

P[Ω m m m (δ ) c ] ≤ D m m m n -h(δ ) α ≤ n -h(δ ) α +1 . (15)
For the second term in R n , since

∥•∥ µ ≤ ∥•∥ ∞ and m m m ∈ M (1)
n,α we have:

K µ n (m m m) ≤ K µ ν (m m m) K ν n (m m m) ≤ K ∞ ν (m m m) ∥G -1 m m m ∥ op ≤ α n log n , (16)
and we have using the independence of (X X X i ) 1≤i≤n and (ε i ) 1≤i≤n :

E ∥Y∥ 2 n 1 Ω m m m (δ ) c = 1 n n ∑ i=1 E b(X X X i ) + ε i 2 1 Ω m m m (δ ) c = E 1 n n ∑ i=1 b(X X X i ) 2 1 Ω m m m (δ ) c + σ 2 P[Ω m m m (δ ) c ].
We apply Hölder's inequality with r, r ′ ∈ (1, +∞) such that 1 r + 1 r ′ = 1:

E ∥Y∥ 2 n 1 Ω m m m (δ ) c ≤ E 1 n n ∑ i=1 b(X X X i ) 2 r 1 r P Ω m m m (δ ) c 1 r ′ + σ 2 P Ω m m m (δ ) c ≤ E 1 n n ∑ i=1 b(X X X i ) 2r 1 r P Ω m m m (δ ) c 1 r ′ + σ 2 P Ω m m m (δ ) c ≤ ∥b∥ 2 L 2r (µ) n -h(δ ) αr ′ + 1 r ′ + σ 2 n -h(δ ) α +1 ,
and if b ∈ L ∞ (µ), the last inequality also holds for r = ∞ and r ′ = 1 (just take the limit as r → +∞). Hence, we obtain:

E K µ n (m m m)∥Y∥ 2 n 1 Ω m m m (δ ) c ≤ α log n ∥b∥ 2 L 2r (µ) n -h(δ ) αr ′ + 1 r ′ +1 + σ 2 n -h(δ ) α +2 . (17)
If we choose δ such that h(δ ) ≥ (2r ′ + 1)α, then all the exponents of n in ( 15) and ( 17) are less than -1. The function h is an increasing function from [0, 1] to itself so it is invertible on [0, 1]. Since α ∈ (0, 1 2r ′ +1 ), we can choose δ = δ (α, r ′ ) := h -1 ((2r ′ + 1)α). For this choice, we obtain:

E∥b -bm m m ∥ 2 µ ≤ C n δ (α, r ′ ), α inf t∈S m m m ∥b -t∥ 2 µ +C ′ δ (α, r ′ ) σ 2 D m m m n + C ′′ b, σ 2 , α, r n log n ,
where C n (δ , α) and C ′ (δ ) were defined at the beginning of the proof, and where:

C ′′ b, σ 2 , α, r ≤ 2∥b∥ 2 L 2 (µ) + α ∥b∥ 2 L 2r (µ) + σ 2 . ( 18
) ⊓ ⊔ 7.3 Proof of Theorem 2
The proof of Theorem 2 is based on a result for fixed design regression of [START_REF] Baraud | Model selection for regression on a fixed design[END_REF]. Let M n be a finite collection of models, that may depend on (X X X 1 , . . . , X X X n ), such that for all m m m ∈ M n , G m m m is invertible. Let m m m ∈ M n be the minimizer of the following penalized least squares criterion:

m m m := arg min m m m∈ M n -∥ bm m m ∥ 2 n + pen(m m m) , pen(m m m) := (1 + θ )σ 2 D m m m n , θ > 0. ( 19
)
Theorem 4 (Corollary 3.1 in [START_REF] Baraud | Model selection for regression on a fixed design[END_REF]) If E|ε 1 | q is finite for some q > 4, then the following upper bound on the risk of the estimator b m m m with m m m defined by (19) holds:

E X X X ∥b -b m m m ∥ 2 n ≤ C(θ ) inf m m m∈ M n inf t∈S m m m ∥b -t∥ 2 n + σ 2 D m m m n + σ 2 Σ n (θ , q) n ,
with:

Σ n (θ , q) := C ′ (θ , q) E|ε 1 | q σ q ∑ m m m∈ M n D -( q 2 -2) m m m , where C(θ ) := (2 + 8θ -1 )(1 + θ ) and C ′ (θ , q) is a positive constant. Proof (Theorem 2) Let ∆ n,α,β := {M (1) n,α ⊂ M (1)
n,β }, we have:

E∥b -b m m m 1 ∥ 2 n = E E X X X ∥b -b m m m 1 ∥ 2 n 1 ∆ n,α,β + E ∥b -b m m m 1 ∥ 2 n 1 ∆ c n,α,β .
For the first term, on ∆ n,α,β we have inf

m m m∈ M (1) n,β (. . .) ≤ inf m m m∈M
(1) n,α (. . .) so by applying Theorem 4 we obtain:

E E X X X ∥b -b m m m 1 ∥ 2 n 1 ∆ n,α,β ≤ E C(θ ) inf m∈M (1) n,α inf t∈S m m m ∥b -t∥ 2 n + σ 2 D m m m n + σ 2 Σ (θ , q) n ≤ C(θ ) inf m∈M (1) n,α inf t∈S m m m ∥b -t∥ 2 µ + σ 2 D m m m n + σ 2 Σ (θ , q) n .
For the second term, we have:

∥b -b m m m 1 ∥ 2 n 1 ∆ c n,α,β ≤ 2∥b∥ 2 n 1 ∆ c n,α,β + 2∥ b m m m 1 ∥ 2 n 1 ∆ c n,α,β .
Using Hölder's inequality with r, r ′ ∈ (1, ∞) such that 1 r + 1 r ′ = 1, we obtain:

E ∥b∥ 2 n 1 ∆ c n,α,β ≤ E 1 n n ∑ i=1 b(X X X i ) 2 r 1/r P ∆ c n,α,β 1/r ′ ≤ ∥b∥ 2 L 2r (µ) P ∆ c n,α,β 1/r ′ , and if b ∈ L ∞ (µ), the inequality also holds for r = ∞ and r ′ = 1. Since b m m m 1 is the empirical projection of Y on S m m m 1 1 1 , we have ∥ b m m m 1 ∥ 2 n ≤ ∥Y∥ 2 n .
Hence, we get:

E ∥ b m m m 1 ∥ 2 n 1 ∆ c n,α,β ≤ E ∥Y∥ 2 n 1 ∆ c n,α,β = E 1 n n ∑ i=1 b(X X X i ) 2 1 ∆ c n,α,β + σ 2 P ∆ c n,α,β ≤ ∥b∥ 2 L 2r (µ) P ∆ c n,α,β 1 r ′ + σ 2 P ∆ c n,α,β . (20)
To conclude, we give an upper bound on P ∆ c n,α,β :

P ∆ c n,α,β = P ∃m m m ∈ N p + , m m m ∈ M (1) n,α and m m m / ∈ M (1) n,β ≤ ∑ m m m∈M (1) n,α P m m m ∈ M (1) n,α and m m m / ∈ M (1) n,β .
Using the following inclusion of events:

m m m ∈ M (1) n,α and m m m / ∈ M (1) n,β ⊂ K ∞ ν (m m m) ∥G -1 m m m ∥ op ∨ 1 ≤ α n log n ∩ K ∞ ν (m m m) ∥ G -1 m m m ∥ op ∨ 1 ≥ β n log n ⊂ ∥ G -1 m m m ∥ op ∥G -1 m m m ∥ op ≥ β α = λ min ( G m m m ) ≤ α β λ min (G m m m ) ,
we get:

P ∆ c n,α,β ≤ ∑ m m m∈M (1) n,α P λ min ( G m m m ) ≤ α β λ min (G m m m ) . (21)
Using Lemma 3 with the inequality

K ∞ ν (m m m)∥G -1 m m m ∥ op ≤ α n log n for m m m ∈ M (1)
n,α , we obtain:

∀m m m ∈ M (1) n,α , P λ min ( G m m m ) ≤ α β λ min (G m m m ) ≤ D m m m exp h(1 -α β ) n K ∞ ν (m m m)∥G -1 m m m ∥ op ≤ D m m m n -h(1-α β )/α .
Hence, we get:

P ∆ c n,α,β ≤ ∑ m m m∈M (1) n,α D m m m n -h(1-α β )/α ≤ Card(M (1) n,α ) n 1-h(1-α β )/α .
Using Proposition 4 in appendix, we obtain:

P ∆ c n,α,β ≤ n 2-h(1-α β )/α H p-1 n = n -κ(α,β ) H p-1 n , with H n := ∑ n k=1 1 k and κ(α, β ) := h(1-α β ) α
-2. We know that H n ∼ log n, so we want a condition on α such that the κ(α, β ) is strictly greater than r ′ . Let x := β α ≥ 1, we have:

κ(α, β ) > r ′ ⇐⇒ h 1 - α β > (2 + r ′ )α ⇐⇒ 1 - α β + α β log α β > (2 + r ′ )α ⇐⇒ 1 - 1 + log(x) x > (2 + r ′ )β x ⇐⇒ 1 + (2 + r ′ )β + log(x) x < 1. ( 22
)
The function:

f β ,r ′ (x) := 1 + (2 + r ′ )β + log(x)
x , is decreasing on [1, +∞), we have f β ,r ′ (1) > 1 and f β ,r ′ (x) → 0 when x → +∞, so there exists a unique x β ,r ′ ∈ (1, +∞) such that f β ,r ′ (x β ,r ′ ) = 1. Thus, we have:

(22) ⇐⇒ x ∈ (x β ,r ′ , +∞) ⇐⇒ α ∈ (0, α β ,r ′ ),
where α β ,r ′ := β x β ,r ′ . Hence, if α ∈ (0, α β ,r ′ ) then we have:

P ∆ c n,α,β 1/r ′ ≤ n -κ(α,β ) r ′ H p-1 r ′ n , with κ(α,β ) r ′ > 1 and κ(α,β ) r ′ → 1 as α → α β ,r ′ . ⊓ ⊔
Remark 7 If we use the collections M

(2) n,α and M

(2) n,β instead, we obtain the inequality (21) with α and β replaced by α ′ := √ α and β ′ := β . The rest of the proof is unchanged.

Proof (Remark 4) We have α β ,r ′ := β

x β ,r ′ where x β ,r ′ is the unique solution in (1, +∞) of the equation f β ,r ′ (x) = 1 with:

f β ,r ′ (x) := 1 + (2 + r ′ )β + log x x .
Hence, x β satisfies the relation:

x β ,r ′ -log x β ,r ′ = 1 + (2 + r ′ )β . ( 23
)
Since the functions f β ,r ′ are decreasing on (1, +∞) and since ∀x, f β ,r ′ (x) is increasing with β and r ′ , we see that x β ,r ′ is increasing with β and r ′ . Thus, the limits of x β ,r ′ when β → 0 and β → +∞ exist. Using the relation ( 23), we obtain:

lim β →0 x β ,r ′ = 1, lim β →+∞ x β ,r ′ = +∞, lim r ′ →∞
x β ,r ′ = +∞, and we have x β ,r ′ ∼ (2 + r ′ )β when β → +∞. Thus, the limits of α β ,r ′ are:

lim β →0 α β ,r ′ = 0, lim β →+∞ α β ,r ′ = 1 2 + r ′ , lim r ′ →+∞ α β ,r ′ = 0.
Since x β ,r ′ is increasing with r ′ , we see that α β ,r ′ is deacreasing with r ′ . Finally, using the relation ( 23) again, we have:

α β ,r ′ = β x β ,r ′ = 1 2 + r ′ 1 - 1 x β ,r ′ - log x β ,r ′ x β ,r ′ .
It is easy to see that the function x → 1 -1 x -log x x is increasing on [1, +∞) so α β ,r ′ is also increasing with β . ⊓ ⊔

Proof of Theorem 3

Before proving Theorem 3, we need some preliminary results.

Lemma 4 For all x > 0 and all m m m ∈ N p + we have:

P ∥ G m m m -G m m m ∥ op ≥ x ≤ D m m m exp -nx 2 /2 K ∞ ν (m m m) ∥G m m m ∥ op + 2 3 x ≤ D m m m exp -nx 2 /2 K ∞ ν (m m m) ∥ dµ dν ∥ ∞ + 2 3 x
.

Proof The set {ϕ j j j : j j j ≤ m m m -1} has cardinality D m m m so let {φ 1 , . . . , φ D m m m } be its elements. We define the matrix H m m m as:

∥G m m m ∥ op = sup a∈R m m m ∥a∥ R m m m =1 ∥G m m m × p a∥ 2 R m m m = sup a∈R m m m ∥a∥ R m m m =1 ∑ ℓ ℓ ℓ≤m m m-1 ∑ k k k≤m m m-1 ⟨ϕ ℓ ℓ ℓ , ϕ k k k ⟩a k k k 2 , ∥H m m m ∥ op = sup a∈R d ∥a∥ R d =1 ∥H m m m a∥ 2 R d = sup a∈R d ∥a∥ R d =1 d ∑ j=1 d ∑ i=1 ⟨ψ j , ψ i ⟩a i 2 .
Since the sets {ϕ j j j : j j j ≤ m m m -1} and {φ 1 , . . . , φ d } are equal, these two quantities are also equal. Hence we have:

∥ G m m m -G m m m ∥ op = ∥ H m m m -H m m m ∥ op ,
so we work on H m m m and H m m m from now on. We write:

H m m m -H m m m = n ∑ i=1 Z i , Z i := 1 n V i V ⊤ i -E V i V ⊤ i , V i :=    φ 1 (X X X i ) . . . φ D m m m (X X X i )    ,
and we use the Matrix Bernstein bound (Theorem 6 in appendix).

1. Bound on ∥Z i ∥ op :

1 n ∥V i V ⊤ i ∥ op = 1 n ∥V i ∥ 2 = 1 n D m m m ∑ j=1 φ j (X X X i ) 2 ≤ K ∞ ν (m m m) n ,
where the last inequality comes from Lemma 2. Hence,

∥Z i ∥ op ≤ R, with R := K ∞ ν (m m m) n . 2. Bound on ∥∑ n i=1 E Z 2 i ∥ op : n ∑ i=1 E Z 2 i op = sup ∥a∥=1 n ∑ i=1 E ∥Z i a∥ 2 = sup ∥a∥=1 n ∑ i=1 D m m m ∑ j=1 E (Z i a) 2 j = sup ∥a∥=1 n ∑ i=1 D m m m ∑ j=1
Var (Z i a) j , since EZ i = 0. We compute the variance:

Var (Z i a) j = Var 1 n φ j (X X X i ) D m m m ∑ k=1 φ k (X X X i ) a k ≤ 1 n 2 E   φ j (X X X i ) D m m m ∑ k=1 φ k (X X X i ) a k 2   = 1 n E φ j (X X X i ) 2 t a (X X X i ) 2 ,
where t a := ∑ D m m m k=1 a k φ k . Using Lemmas 1 and 2 yields:

n ∑ i=1 D m m m ∑ j=1 Var (Z i a) j ≤ 1 n 2 n ∑ i=1 E D m m m ∑ j=1 φ j (X X X i ) 2 t a (X X X i ) 2 ≤ 1 n K ∞ ν (m m m) ∥t a ∥ 2 µ ≤ 1 n K ∞ ν (m m m) K µ ν (m m m) ∥t a ∥ 2 ν = 1 n K ∞ ν (m m m) ∥G m m m ∥ op ∥a∥ 2 . Hence, ∥∑ n i=1 E Z 2 i ∥ op ≤ 1 n K ∞ ν (m m m)∥G m m m ∥ op =: v. Applying Theorem 6 yields: P ∥ H m m m -H m m m ∥ op ≥ x ≤ D m m m exp - nx 2 /2 K ∞ ν (m m m) ∥G m m m ∥ op + 2 3 x
, which is the first inequality of Lemma 4. The second inequality follows from the following upper bound on ∥G m m m ∥ op :

∥G m m m ∥ op = sup t∈S m m m \{0} ∥t∥ 2 µ ∥t∥ 2 ν ≤ dµ dν ∞ .

⊓ ⊔

In order to prove Theorem 3, let us consider the events:

Λ (ι) n (β , γ) := M (ι) n,β ⊂ M (ι) n,γ , Ω (ι) n (δ , γ) := m m m∈M (ι) n,γ Ω m m m (δ ), ι ∈ {1, 2}, (24)
where Ω m m m (δ ) is defined by (2).

Lemma 5 For ι ∈ {1, 2}, we have for all δ ∈ (0, 1) and all γ > 0:

P Ω (ι) n (δ , γ) c ≤ n -h(δ ) γ +2 H p-1 n ,
where H n := ∑ n k=1 1 k is the n-th harmonic number.

Proof We use Proposition 3 with Remark 1:

P Ω (ι) n (δ , γ) c ≤ ∑ m m m∈M (ι) n,γ P[Ω m m m (δ ) c ] ≤ ∑ m m m∈M (ι) n,γ D m m m exp -h(δ ) n K ∞ µ (m m m) ≤ ∑ m m m∈M (ι) n,γ D m m m exp -h(δ ) n K ∞ ν (m m m)∥G -1 m m m ∥ op ≤ ∑ m m m∈M (ι) n,γ D m m m n -h(δ ) γ ≤ n -h(δ ) γ +2 H p-1 n ,
where the last inequality comes from Proposition 4.

⊓ ⊔

Lemma 6 (Compact case) We have for all γ > β > 0:

P Λ (1) n (β , γ) c ≤ n -h(1-γ β ) f 0 β +1 H p-1 n , where h(δ ) = δ + (1 -δ ) log(1 -δ ), f 0 > 0 is such that dµ dν (x) ≥ f 0 for all x ∈ A and H n := ∑ n k=1 1 k .
Proof We start with a union bound:

P Λ (1) n (β , γ) c = P ∃m m m ∈ N p + , m m m ∈ M (1) n,β and m m m / ∈ M (1) n,γ ≤ ∑ m m m∈N p + K ∞ ν (m m m)≤β n log n P m m m ∈ M (1)
n,β and m m m / ∈ M

(1) n,γ .

We have the following inclusion of events:

m m m ∈ M (1) n,β and m m m / ∈ M (1) n,γ ⊂ K ∞ ν (m m m) ∥ G -1 m m m ∥ op ∨ 1 ≤ β n log n ∩ K ∞ ν (m m m) ∥G -1 m m m ∥ op ∨ 1 ≥ γ n log n ⊂ ∥G -1 m m m ∥ op ∥ G -1 m m m ∥ op ≥ γ β ⊂ λ min ( G m m m ) ≥ γ β λ min (G m m m ) ,
hence we obtain:

P Λ (1) n (β , γ) c ≤ ∑ m m m∈N p + K ∞ ν (m m m)≤β n log n P λ min ( G m m m ) ≥ γ β λ min (G m m m ) .
We apply inequality (30) of Theorem 5 with R

= 1 n K ∞ ν (m m m): P λ min ( G m m m ) ≥ γ β λ min (G m m m ) ≤ exp -h 1 - γ β n K ∞ ν (m m m)∥G -1 m m m ∥ op .
In the compact case, we have ∥G -1 m m m ∥ op ≤ 1 f 0 , see (3). Using Proposition 4, we obtain:

P Λ (1) n (β , γ) c ≤ ∑ m m m∈N p + K ∞ ν (m m m)≤β n log n n -h(1-γ β ) f 0 β ≤ n -h(1-γ β ) f 0 β +1 H p-1 n . ⊓ ⊔
Lemma 7 (General case) We have for all γ > β > 0:

P Λ (2) n (β , γ) c ≤ n -C(β ,γ) B 2β +2 H p-1 n , where C(β , γ) := 1 -β /γ 2 , B := ∥ dµ dν ∥ ∞ + 2 3 -1 and H n := ∑ n k=1 1 k .
Proof We start with a union bound:

P Λ (2) n (β , γ) c = P ∃m m m ∈ N p + , m m m ∈ M (2) n,β and m m m / ∈ M (2) n,γ ≤ ∑ m m m∈N p + K ∞ ν (m m m)≤β n log n P m m m ∈ M (2) n,β and m m m / ∈ M (2) n,γ .
We have the following inclusion of events:

m m m ∈ M (2) n,β and m m m / ∈ M (2) n,γ ⊂ K ∞ ν (m m m) ∥ G -1 m m m ∥ 2 op ∨ 1 ≤ β n log n ∩ K ∞ ν (m m m) ∥G -1 m m m ∥ 2 op ∨ 1 ≥ γ n log n ⊂ K ∞ ν (m m m)∥ G -1 m m m ∥ 2 op ≤ β n log n ∩ K ∞ ν (m m m)∥ G -1 m m m -G -1 m m m ∥ 2 op ≥ √ γ -β 2 n log n ⊂ ∥ G -1 m m m ∥ 2 op ≤ β K ∞ ν (m m m) n log n ∩ ∥ G -1 m m m -G -1 m m m ∥ op ≥ γ β -1 ∥ G -1 m m m ∥ op .
Let η := γ β -1 and let ε ∈ (0, 1). We consider the following decomposition:

∥ G -1 m m m -G -1 m m m ∥ op ≥ η∥ G -1 m m m ∥ op = E 1 ∪ E 2 ,
with:

E 1 := ∥ G -1 m m m -G -1 m m m ∥ op ≥ η∥ G -1 m m m ∥ op ∩ G -1 m m m (G m m m -G m m m ) op < ε , E 2 := ∥ G -1 m m m -G -1 m m m ∥ op ≥ η∥ G -1 m m m ∥ op ∩ G -1 m m m (G m m m -G m m m ) op ≥ ε .
-For E 1 , we apply Lemma 9 with

A := G m m m and B := G m m m -G m m m : E 1 ⊂    ∥ G -1 m m m ∥ 2 op ∥ G m m m -G m m m ∥ op 1 -G -1 m m m (G m m m -G m m m ) op ≥ η∥ G -1 m m m ∥ op    ∩ G -1 m m m (G m m m -G m m m ) op < ε ⊂ ∥ G -1 m m m ∥ op ∥ G m m m -G m m m ∥ op ≥ (1 -ε)η .
-For E 2 , we have directly:

E 2 ⊂ G -1 m m m (G m m m -G m m m ) op ≥ ε ⊂ ∥ G -1 m m m ∥∥G m m m -G m m m ∥ op ≥ ε .
Thus, we obtain:

∀ε ∈ (0, 1), E 1 ∪ E 2 ⊂ ∥ G -1 m m m ∥ op ∥G m m m -G m m m ∥ op ≥ (1 -ε)η ∧ ε .
We now choose ε maximizing (1ε)η ∧ ε. This maximum is achieved when ε = (1ε)η, that is:

ε = η 1 -η = 1 -β /γ =: c(β , γ) ∈ (0, 1).
Thus, we obtain:

P Λ (2) n (β , γ) c ≤ ∑ m m m∈N p + K ∞ ν (m m m)≤β n log n P ∥ G -1 m m m ∥ 2 op ≤ β K ∞ ν (m m m) n log n ∩ ∥ G m m m -G m m m ∥ op ≥ c(β , γ) ∥ G -1 m m m ∥ op ≤ ∑ m m m∈N p + K ∞ ν (m m m)≤β n log n P ∥ G m m m -G m m m ∥ op ≥ c(β , γ) K ∞ ν (m m m) β log n n . Let x := c(β , γ) K ∞ ν (m m m) β log n n and notice that x ≤ 1 if K ∞ ν (m m m) ≤ β n log n .
We apply Lemma 4 and Proposition 4:

P Λ (2) n (β , γ) c ≤ ∑ m m m∈N p + K ∞ ν (m m m)≤β n log n D m m m exp - n 2 c 2 (β , γ) K ∞ ν (m m m) β log n n K ∞ ν (m m m) dµ dν ∞ + 2 3 x -1 ≤ ∑ m m m∈N p + K ∞ ν (m m m)≤β n log n D m m m n -c 2 (β ,γ) B 2β ≤ n -c 2 (β ,γ) B 2β +2 H p-1 n , where B := (∥ dµ dν ∥ ∞ + 2 3 ) -1 . ⊓ ⊔
Now we can prove Theorem 3.

Proof (Theorem 3) Let δ ∈ (0, 1) and γ > β be constants to be chosen later. Let us introduce the event Ξ

(ι) n (β , γ, δ ) := Λ (ι) n (β , γ) ∩ Ω (ι) n (δ , γ) where Λ (ι) n (β , γ) and ≤ 2 ∥b∥ 2 µ + 4β n log n ∥Y∥ 2 n .
Using Hölder's inequality as we did in (20), we obtain:

E ∥b -b m m m ι ∥ 2 µ 1 Ξ (ι) n (β ,γ,δ ) c ≤ 2 ∥b∥ 2 µ P Ξ (ι) n (β , γ, δ ) c + 8β n log n ∥b∥ 2 L 2r (µ) P Ξ (ι) n (β , γ, δ ) c 1/r ′ + σ 2 P Ξ (ι) n (β , γ, δ ) c . (26)
We see we need to control P Ξ (ι) n (β , γ, δ ) c by a term of order n -2r ′ .

We have decomposed the risk as the sum of ( 25) and ( 26). We give different upper bounds on these two terms depending on whether we are in the compact case or the general case.

• Compact case. In equation ( 25), we apply Theorem 2: for all α ∈ (0, α β ,r ′ ) we have:

E ∥b -b m m m 1 ∥ 2 µ 1 Ξ (1) n (β ,γ,δ ) ≤ 2 + 4 1 -δ 1 +C(θ ) inf m m m∈M n,α inf t∈S m m m ∥b -t∥ 2 µ + σ 2 D m m m n + 4σ 2 1 -δ Σ (θ , q) n + 4 1 -δ C ′ ∥b∥ 2 L 2r (µ)
, σ 2 (log n) (p-1)/r ′ n κ(α,β )/r ′ , with κ(α,β ) r ′ > 1. To obtain an upper bound on (26), we apply Lemmas 5 and 6: P Ξ

(1) n (β , γ, δ ) c ≤ P Ω

(1) n (δ , γ) c + P Λ

(1)

n (β , γ) c ≤ n -h(δ ) γ +2 + n -h(1-γ β ) f 0 β +1 H p-1 n ,
where h(δ ) := δ + (1δ ) log(1δ ) and H n := ∑ n k=1 1 k . In order to obtain a term of order n -2r ′ , we need:

       h(δ ) γ -2 > 2r ′ , h 1 - γ β f 0 β -1 > 2r ′ , ⇐⇒      h(δ ) > 2(1 + r ′ )γ, h 1 - γ β > (2r ′ + 1) β f 0 , ⇐⇒              δ > h -1 2(1 + r ′ )γ , γ < 1 2(1 + r ′ ) , h 1 - γ β > (2r ′ + 1) β f 0 .
Let us work on the last two conditions. Let x := γ β > 1, the conditions on (β , γ) become:

      
x < 1 2(1 + r ′ )β ,

x log xx + 1 > (2r ′ + 1) β f 0 .

The function x → x log xx + 1 is increasing on (1, +∞) and ranges from 0 to +∞, so there exists x f 0 ,β > 1 such that for all x > x f 0 ,β we have x log xx + 1 > (2r ′ + 1) β f 0 . Hence we need to choose x such that:

x f 0 ,β < x < 1 (2r ′ + 2)β . (27)
This is possible only if x f 0 ,β < 1 (2r ′ +2)β , that is if:

(2r ′ + 1) β f 0 < 1 (2r ′ + 2)β log 1 (2r ′ + 2)β - 1 (2r ′ + 2)β + 1.
Let us introduce a new variable y := (2r ′ + 2)β and let R = 2r ′ +1 2r ′ +2 , the last inequality becomes: R f 0 y + 1 + log y y < 1.

(28)

The function y → R f 0 y + 1+log y y is increasing on (0, 1), it tends to -∞ at 0 and for y = 1 it is greater that 1, so there exists y f 0 ,r ′ ∈ (0, 1) such that the condition (28) is satisfied on (0, y f 0 ,r ′ ). To sum up, we have shown that there exists β f 0 ,r ′ ∈ (0, 1 2r ′ +2 ) such that for every β < β f 0 ,r ′ , the condition ( 27) is not empty. We choose:

γ := β x,
x satisfying (27),

δ := 1 + h -1 2(1 + r ′ )γ 2 ,
and we obtain that:

E ∥b -b m m m 1 ∥ 2 µ 1 Ξ (1) n (β ,γ,δ ) c ≤ C ′′ (∥b∥ L 2r (µ) , β , σ 2 ) n -λ (β ,r, f 0 ) (log n) p-1 r ′ -1 ,
where λ (β , r, f 0 ) > 1.

• General case. In equation ( 25), if we follow the proof of Theorem 2 (see Remark 7), we see that if α ∈ (0, α 2 β 1/2 ,r ′ ) then we have:

E∥b -b m m m 2 ∥ 2 n ≤ C(θ )∥b -t∥ 2 µ + σ 2 D m m m n + σ 2 Σ (θ , q) n +C ′ ∥b∥ 2 L 2r (µ) , σ 2 (log n) (p-1)/r ′ n κ(α 1 2 ,β 1
2 )/r ′ , with κ(α

1 2 ,β 1
2 ) r ′ > 1. Thus, we obtain:

E ∥b -b m m m 2 ∥ 2 µ 1 Ξ (2) n (β ,γ,δ ) ≤ 2 + 4 1 -δ 1 +C(θ ) inf m m m∈M (2) n,α inf t∈S m m m ∥b -t∥ 2 µ + σ 2 D m m m n + 4σ 2 1 -δ Σ (θ , q) n + 4 1 -δ C ′ ∥b∥ 2 L 2r (µ) , σ 2 (log n) (p-1)/r ′ n κ(α 1 2 ,β 1
2 )/r ′ .

To obtain an upper bound on (26), we apply Lemmas 5 and 7:

P Ξ

(2) n (β , γ, δ ) c ≤ P Ω To obtain a term of order n -2r ′ , we need:

       h(δ ) γ -2 > 2r ′ , C(β , γ) B 2β -2 > 2r ′ , ⇐⇒    h(δ ) > 2(1 + r ′ )γ, C(β , γ) B 2 > 2(1 + r ′ )β , ⇐⇒              δ > h -1 2(1 + r ′ )γ , γ < 1 2(1 + r ′ ) , C(β , γ)B 4(1 + r ′ ) > β .
Let x := β /γ ∈ (0, 1), the conditions on (β , γ) can be rewritten as:

       β x 2 < 1 2(1 + r ′ ) , β < (1 -x) 2 B 4(1 + r ′ ) , ⇐⇒ β < 1 2(1 + r ′ )
x 2 ∧ (1x) 2 B 2 .

then we have: = n H p-1 n .

Theorem 7 (Divisor bound) Let N ∈ N + and let div(N) be the set of divisors of N. We have for all ε > 0:

Card div(N) = o(N ε ).

As a consequence, we have for all ε > 0:

Card m ∈ N p + m 1 • • • m p = N ≤ Card div(N) p = o(N ε ).
A proof of this result can be found in [START_REF] Tao | The divisor bound[END_REF].

  S = S m m m , we use the notation K α β (m m m) := K α β (S m m m ). The next lemma gives the value of K β α (S) when the norms are Euclidean.

Lemma 3

 3 Let (ψ 1 , . . . , ψ D m m m ) be an orthnormal basis of S m m m relatively to an inner product ⟨•, •⟩ α . Let H m m m be the Gram matrix of this basis relatively to the empirical inner product and let H m m m := E[ H m m m ], that is:

∀

  j, k ∈ {1, . . . , D m m m }, H m m m j,k := ⟨φ j , φ k ⟩ n , and we denote its expectation H m m m , of which the components are ⟨φ j , φ k ⟩ µ . In other words, we have reshaped the hypermatrices G m m m and G m m m into D m m m × D m m m matrices. Moreover, this operation preserves the operator norm: ∥G m m m ∥ op = ∥H m m m ∥ op . Indeed, let d := D m m m , we have:

  Bernstein bound) Let Z 1 , . . . , Z n be independent random self-adjoint positive semidefinite matrices with dimension d, such that E[Z k ] = 0 and that sup k λ max (Z k ) ≤ R a.s. If v > 0 is such that: For n ≥ 1 and p ≥ 2 we have:Card m m m ∈ N p + m 1 • • • m p ≤ n ≤ n H p

Table 1

 1 Watson estimator for estimating b 1 , b 2 and b 3 , and both estimators are equivalent for estimating b 4 . In the Laplace Risk comparison, p = 1. Tableshowingthe relative µ-risks of the Hermite projection estimator and the Nadaraya-Watson estimator. For each distribution of X, regression function, SNR and n, we display the estimated relative µ-risk over N = 100 samples with a 95% confidence interval, multiplied by 100. For the projection estimator, we display the mean selected model, and for the Nadaraya-Watson estimator, we display the mean selected bandwidth.

	X distrib. Reg. fun.	Estim.	SNR = 2 n = 250 n = 1000	SNR = 20 n = 250 n = 1000
			1.23	0.288	0.138	0.034
		Hermite	[1.22, 1.24]	[0.284, 0.292]	[0.136, 0.140]	[0.034, 0.035]
	b 1		4 1.50	5 0.468	6 0.255	6 0.076
		NW	[1.49, 1.51]	[0.463, 0.472]	[0.253, 0.258]	[0.075, 0.076]
			0.307	0.212	0.724	0.763
			1.00	0.362	0.159	0.047
		Hermite	[0.99, 1.01]	[0.358, 0.366]	[0.157, 0.161]	[0.047, 0.047]
	b 2		3 1.38	5 0.475	6 0.236	8 0.075
		NW	[1.37, 1.40]	[0.470, 0.480]	[0.234, 0.238]	[0.074, 0.076]
	Norm.		0.281 1.77	0.214 0.477	0.161 0.206	0.126 0.050
		Hermite	[1.76, 1.79]	[0.472, 0.482]	[0.204, 0.208]	[0.049, 0.050]
	b 3		10 2.80	12 0.823	11 0.808	13 0.160
		NW	[2.78, 2.82]	[0.817, 0.829]	[0.799, 0.818]	[0.160, 0.161]
			0.138	0.107	0.088	0.066
			1.94	0.532	0.288	0.116
		Hermite	[1.92, 1.97]	[0.528, 0.536]	[0.286, 0.290]	[0.115, 0.116]
	b 4		9 1.86	12 0.585	11 0.344	13 0.108
		NW	[1.84, 1.88]	[0.581, 0.590]	[0.341, 0.347]	[0.107, 0.108]
			0.216	0.162	0.120	0.096
			1.81	0.400	0.162	0.047
		Hermite	[1.78, 1.83]	[0.394, 0.405]	[0.159, 0.164]	[0.046, 0.047]
	b 1		5 2.20	6 0.686	6 0.335	7 0.104
		NW	[2.18, 2.23]	[0.681, 0.691]	[0.332, 0.338]	[0.103, 0.105]
			0.347	0.260	0.182	0.147
			1.45	0.426	0.202	0.064
		Hermite	[1.43, 1.47]	[0.421, 0.430]	[0.199, 0.204]	[0.063, 0.064]
	b 2		3 1.94	5 0.725	7 0.0337	9 0.113
		NW	[1.92, 1.95]	[0.720, 0.731]	[0.334, 0.339]	[0.112, 0.114]
	Lap.		0.315 4.56	0.249 0.985	0.180 1.39	0.145 0.121
		Hermite	[4.49, 4.63]	[0.979, 0.991]	[1.32, 1.47]	[0.120, 0.123]
	b 3		19 3.57	27 0.974	20 1.09	29 0.258
		NW	[3.52, 3.61]	[0.968, 0.980]	[1.06, 1.11]	[0.254, 0.261]
			0.225	0.184	0.155	0.137
			8.61	1.04	1.59	0.177
		Hermite	[8.23, 8.98]	[1.04, 1.05]	[1.53, 1.65]	[0.175, 0.180]
	b 4		19 2.30	28 0.729	20 0.454	29 0.133
		NW	[2.28, 2.33]	[0.724, 0.733]	[0.451, 0.457]	[0.133, 0.134]
			0.294	0.224	0.171	0.127

Table 2

 2 Risk comparison, p = 2.Table showing the relative µ-risks of the Hermite projection estimator and the Nadaraya-Watson estimator.

in general it is a semi-norm but we will only consider subspaces on which it is a norm.

Acknowledgements I want to thank Fabienne Comte and Céline Duval for their helpful advice and their support of my work. I also want to thank Florence Merlevède for her help with the second inequality of the Matrix Chernoff bound. Finally, I want to thank Herb Susmann for proofreading this article.

This work was supported by a grant from Région Île-de-France.

Proof (Proposition 3) Let ψ 1 , . . . , ψ D m m m be an orthonormal basis of S m m m relatively to the inner product ⟨•, •⟩ µ . Let H m m m be their Gram matrix relatively to the empirical inner product. According to Lemma 1, we have

) is orthonormal for the inner product associated with µ, so the event Ω m m m (δ ) c can be written as:

Applying Lemma 3 yields the result.

⊓ ⊔

Proof (Proposition 2) We start with the decomposition:

We consider these two terms separately. The expectation of the first term is controlled as in Theorem 3 in [START_REF] Cohen | On the Stability and Accuracy of Least Squares Approximations[END_REF]. On the event Ω m m m (δ ) we have

We choose x maximizing this bound. This maximum is achieved when

. Finally we choose:

and we obtain that for all β ∈ (0, β B,r ′ ) with:

we have:

where λ (β , r, B) > 1. ⊓ ⊔

A Linear Algebra

Lemma 8 Let E be a Euclidean vector space and let ℓ : E → R n be an injective linear map. For y ∈ R n , the solution of the problem:

is given by: â

where ℓ * : R n → E is characterized by the relation y, ℓ(a) R n = ℓ * (y), a E .

Lemma 9 Let A, B be square matrices. If A is invertible and ∥A -1 B∥ op < 1, then A + B is invertible and it holds:

B Concentration inequalities

You can find the proofs of the following bounds in [START_REF] Tropp | User-Friendly Tail Bounds for Sums of Random Matrices[END_REF] and [START_REF] Gittens | Tail bounds for all eigenvalues of a sum of random matrices[END_REF].

Theorem 5 (Matrix Chernoff bound) Let Z 1 , . . . , Z n be independent random self-adjoint positive semidefinite matrices with dimension d, such that sup k λ max (Z k ) ≤ R a.s. If we define: