Robust empirical mean Estimators

Matthieu Leraslelabel=e1]mlerasle@unice.fr [

Roberto I. Oliveiralabel=e1]rimfo@impa.br [ CNRS-Université Nice and IMPA

Estrada Da. Castorina, 110.

Rio de Janeiro, RJ, Brazil. 22460-320

Abstract

: We study robust estimators of the mean of a probability measure P, called robust empirical mean estimators. This elementary construction is then used to revisit a problem of aggregation and a problem of estimator selection, extending these methods to not necessarily bounded collections of previous estimators.

We consider then the problem of robust M-estimation. We propose a slightly more complicated construction to handle this problem and, as examples of applications, we apply our general approach to least-squares density estimation, to density estimation with Küllback loss and to a non-Gaussian, unbounded, random design and heteroscedastic regression problem.

Finally, we show that our strategy can be used when the data are only assumed to be mixing.

\startlocaldefs\endlocaldefs

and

Keywords and phrases : Robust estimation, aggregation, estimator selection, density estimation, heteroscedastic regression.

AMS 2010 subject classification : Primary 62G05; Secondary 62G35.

1 Introduction

The goal of this paper is to develop the theory and applications of what we call robust empirical mean estimators. As a first step, we show that one can estimate the mean m:=𝔼_P(X) of a random variable X with distribution P based on the observation of a finite sample X₁:n:=(X₁,…,Xₙ) i.i.d with marginal P. More precisely, our estimator m̂(δ) takes as input the sample X₁:n and a confidence level δ∈(0,1), and satisfies:

ℙ{.m̂(δ)-m>Cσ√((ln(δ⁻¹))/(n)).}≤δ

(1)

where σ² is the variance of X and C is a universal constant. The classical empirical mean estimator m̂:=n⁻¹ Σᵢ₌₁ⁿ Xᵢ satisfies such bounds only when the observations are Gaussian. Otherwise, some extra assumptions on the data are generally required and the concentration of m̂ takes a different shape. For example, if X₁≤b, Bennett’s concentration inequality gives

ℙ{.m̂-m>σ√(2(ln(δ⁻¹))/(n))+(bln(δ⁻¹))/(3n).}≤δ ,

and heavier tails imply wider confidence intervals for the empirical mean.

The goal of achieving (1) is not new. Catoni [12, 14] has recently developed a Pac-Bayesian approach that has applied in several problems of non parametric statistics including linear regression and classification [1, 2, 13]. The main idea behind the constructions [14] is to do “soft-truncation” of the data, so as to mitigate heavy tails. This gives estimators achieving (1) with nearly optimal constant C∼√(2) for a wide range of δ.

One significant drawback of Catoni’s construction is that one needs to know σ or an upper bound for the kurtosis κ in order to achieve the bound in (1). In this paper we show that no such information is necessary. The construction we present, while not well-known, is not new: we learned about it from [20] and the main ideas seem to date back to the work of Nemirovsky and Yudin [29]. The main idea of these authors was to split the sample into regular blocks, then take the empirical mean on each block, and finally define our estimator as the median of these preliminary estimators. When the number V of blocks is about ln(δ⁻¹), the resulting robust empirical mean estimator satisfies (1).

This result is sufficient to revisit some recent procedures of aggregation and selection of estimators and extend their range of application to heavier-tailed distributions. Before we move on to discuss these applications, we note that in all cases the desired confidence level δ will be built into the estimator (ie. it must be chosen in advance), and it cannot be smaller than e⁻ⁿ⁄². While similar limitations are faced by Catoni in [14], the linear regression estimator in [2] manages to avoid this difficulty. By contrast, our estimators are essentially as efficient as their non-robust counterparts. This favourable trait is not shared by the estimator in [2], which is based on a non-convex optimization problem.

We now discuss our first application of robust estimator, to the least-squares density estimation problem. We study the Lasso estimator of [31], which is a famous aggregation procedure extensively studied over the last few years (see for example [7, 11, 15, 17, 19, 24, 28, 34, 35, 36] and the references therein), using ℓ₁-penalties. We modify the Lasso estimator, adapted to least-squares density estimation in [11], and extend the results of [11] to unbounded dictionaries.

We then study the estimator selection procedure of [3] in least-squares density estimation. Estimator selection is a new important theory that covers in the same framework the problems of model selection and of the selection of a statistical strategy together with the tuning constants associated. [3] provides a general approach including density estimation but his procedure based on pairwise tests between estimators, in the spirit of [8] was not computationally tractable. A tractable algorithm is available in Gaussian linear regression in [5]. Our contribution to the field is twofold. First, we extend the tractable approach of [5] to least-squares density estimation. Our results rely on empirical process theory rather than Gaussian techniques and may be adapted to other frameworks, provided that some uniform upper bounds on the previous estimators are available. Then, we extend these results using robust empirical means. The robust approach is restricted to the variable selection problem but allows to handle not necessarily bounded collections of estimators.

After these direct applications, we consider the problem of building robust estimators in M-estimation. We present a general approach based on a slightly more complicated version of the basic robust empirical mean construction. We introduce a margin type assumption to control the risk of our estimator. This assumption is not common in the literature but we present classical examples of statistical frameworks where it is satisfied. We apply then the general strategy to least-squares and maximum likelihood estimators of the density and to a non-Gaussian, non bounded, random design and heteroscedastic regression setting. In these applications, our estimators satisfy optimal risk bounds, up to a logarithmic factor. This is an important difference with [2] where exact convergence rates were obtained using a localized version of the Pac-Bayesian estimators.

Finally, the decomposition of the data set into blocks was used in recent works [4, 16, 23, 22] in order to extend model selection procedures to mixing data. The decomposition is done to couple the data with independent blocks and then apply the methods of the independent case. Similar ideas can be developed here, but it is interesting to notice that the extension does not require another block decomposition. The initial decomposition of the robust empirical mean algorithm is sufficient and our procedures can be used with mixing data. We extend several theorems of the previous sections to illustrate this fact.

The paper is organized as follows. Section 2 presents basic notations, the construction of the new estimators and the elementary concentration inequality that they satisfy. As a first application, we deduce an upper bound for the variance and a confidence interval for the mean. Section 3 presents the application to Lasso estimators. We extend the results of [11] in least-squares density estimation to unbounded dictionaries. Section 4 presents the results on estimator selection. We extend the algorithm of [5] to least-squares density estimation and obtain a general estimator selection theorem for bounded collections of estimators. We study also our robust approach in this context and extend, for the important subproblem of variable selection the estimator selection theorem to unbounded collections of estimators. Section 5 considers the problem of building robust estimators in M-estimation. We present a general strategy slightly more complicated than the one of Section 2 that we apply to the M-estimation frameworks of least-squares density estimation, density estimation with Küllback loss and an heteroscedastic and random design regression problem where the target functions are not bounded and the errors not Gaussian in general. Section 6 presents the extension to the mixing case and the proofs are postponed to the appendix.

2 Robust estimation of the mean

Let (X,X) be a measurable space, let X₁:n=(X₁,…,Xₙ₎ be i.i.d, X-valued random variables with common distribution P and let X be an independent copy of X₁. Let V≤n be an integer and let B=(B₁,…,B_V) be a regular partition of Iₙ:={.1,…,n.}, i.e.

∀ K=1,…,V, |CardB_K-(n)/(V)|≤1 .

( 𝐂 𝐫𝐞𝐠 subscript 𝐂 𝐫𝐞𝐠 \mathbf{C_{reg}} )

We will moreover always assume, for notational convenience, that V≤n/2 so that, from (Cᵣeg), CardB_K≥n/V-1≥n/(2V). For all non empty subsets A⊂ Iₙ, for all real valued measurable functions t (respectively for all integrable functions t), we denote by

P_A t=(1)/(Card(A))Σᵢ∈ A t(Xᵢ), Pt=𝔼(.t(X).) .

For short, we also denote by Pₙ=P_Iₙ. For all integers N, for all a₁:N=(a₁,…,a_N) in ℝ^N, we denote by Med(a₁:N) any real number b such that

Card{.i≤N s.t. aᵢ≤b.}≥(N)/(2), Card{.i=1≤N s.t. aᵢ≥b.}≥(N)/(2) .

Let us finally introduce, for all real valued measurable functions t,

P̅_Bt=Med{.P_B_Kt, K=1,…,V.} .

Our first result is the following concentration inequality.

Proposition 1.

Let (X,X) be a measurable space and let X₁:n be i.i.d, X-valued random variables with common distribution P. Let f: X R be a measurable function such that var_P(f)<∞ and let δ∈(0,1). Let V≤n/2 be an integer and let B be a partition of Iₙ satisfying (Cᵣeg). If V≥ln(δ⁻¹), we have, for some absolute constant L₁≤2√(6e),

ℙ{.P̅_Bf-Pf>L₁√(var_P f)√((V)/(n)).}≤δ .

Proposition 1 is proved in Section A.1.

Remark 1.

An important feature of this result is that the concentration inequality does not involve the sup-norm of the data. This is the key for the developments presented in Sections 3 and 4. The drawbacks are that the level δ has to be chosen before the construction of the estimator and that the process P̅_B is not linear.

As a first application, let us give the following control for var_P f.

Corollary 2.

Let (X,X) be a measurable space and let X₁:n be i.i.d, X-valued random variables with common distribution P. Let f: X R be a measurable function such that var_P(f²)<∞ and let δ∈(0,1). Let V≤n/2 be an integer and let B be a partition of Iₙ satisfying (Cᵣeg). Assume that V≥ln(δ⁻¹) and that

L₁(√(var_P f²))/(Pf²)√((V)/(n))1_Pf²≠0≤1/2.

( 𝐂 ​ ( 𝐟 ) 𝐂 𝐟 \mathbf{C(f)} )

Then

ℙ{.var_P(f)≤2P̅_Bf² .}≥1-δ.

Proof.

We can assume that Pf²≠0, otherwise var_P(f)=0 and the proposition is proved. We apply Proposition 1 to the function -f², since V≥ln(δ⁻¹), we have

ℙ{.P̅f²<Pf² (.1-L₁(√(var_P f²))/(Pf²)√((V)/(n)).).}≤δ.

We conclude the proof with assumption (C(f)). ∎

Using a union bound in Proposition 1 and Corollary 2, we get the following corollary.

Corollary 3.

Let Λ be a finite set and let π be a probability measure on Λ. Let D=(ψ_λ)_λ∈Λ be a set of measurable functions. Let (B_λ)_λ∈Λ be a set of regular partition of Iₙ with Card(B_λ)=V_λ≥ln(4(π(λ)δ)⁻¹). Assume that

∀λ∈Λ, var_P(ψ_λ²)<∞, and L₁(√(var_P(ψ_λ²)))/(Pψ_λ²)√((V_λ)/(n))1_Pψ_λ²≠0≤1/2

( 𝐂 ​ ( 𝒟 ) 𝐂 𝒟 \mathbf{C(\mathcal{D})} )

Then, for L₂=√(2)L₁, we have

P .∀λ∈, P_ B λ_λ-P_λ≤ L_2P B _λ_λ^2V_λn. ≥ 1-δ.

In Sections 3 and 4, we present several applications of these results.

3 Application to Lasso estimators in least-squares density estimation

Lasso estimators of [31] became popular over the last few years, in particular because they can be computed efficiently in practice. These estimators have been studied in density estimation in [11] for bounded dictionaries. We propose here to revisit and extend some results of [11] with our robust approach. This approach does not require boundedness of the dictionary as will be shown.

Let us recall here the classical framework of density estimation. We observe i.i.d random variables X₁:n, valued in a measured space (X,X,μ), with common distribution P. We assume that P is absolutely continuous with respect to μ and that the density s_ of P with respect to μ belongs to L²(μ). We denote respectively by ⟨.,.⟩ and ‖.‖ the inner product and the norm in L²(μ). The risk of an estimator ŝ of s_ is measured by its L²-risks, i.e. ‖s-s_‖^2. Given a collection (ŝ_θ)θ∈Θ of estimators (possibly random) of s, we want to select a data-driven θ̂ such that

P .∀θ∈, ‖ s_-s_θ‖^2≤ C‖ s_-s_θ‖^2+R(θ). ≥ 1-δ.

In the previous inequality the leading constant C is expected to be close to 1 and R(θ) should remain of reasonable size. In that case, ŝ_θ̂ is said to satisfy an oracle inequality since it behaves as well as an “oracle”, i.e. a minimizer of ‖ s_-s_θ‖^2 that is unknown in practice.

Let Λ be a finite set of cardinal M and let D={.ψ_λ, λ∈Λ.} be a dictionary, i.e., a finite set of measurable functions. In the case of the Lasso, Θ⊂ℝ^M and, for all θ=(θ_λ)_λ∈Λ ∈Θ,

s_θ=Σ_λ∈Λ θ_λ ψ_λ.

The risk of s_θ is equal to

‖ s_-s_θ‖^2= ‖ s_‖^2+‖ s_θ‖^2-2∫ s_s_θdμ = ‖ s_‖^2+‖ s_θ‖^2-2Σ_λ∈θ_λ∫ s__λdμ.

Therefore, the best estimator, or the oracle, in the collection (s_θ)_θ∈Θ⊂ℝ^M minimizes the ideal criterion

critᵢd(θ)=‖ s_θ ‖²-2Σ_λ∈Λ θ_λ Pψ_λ.

The idea of [11] is to replace the unknown critᵢd by the following penalized empirical version

crit_Las(θ)=‖ s_θ ‖²-2Σ_λ∈Λ θ_λ Pₙ ψ_λ+2Σ_λ∈Λ ω_λ |θ_λ | ,

for proper choice of the weights ω_λ. We modify this Lasso-type criterion with our robust version. Let B be a regular partition of {.1,…,n.} with cardinality V to be defined later. Let P̅_B be the associated empirical process introduced in Proposition 1. Our criterion is given by

crit(θ,B)=‖ s_θ ‖²-2Σ_λ∈Λ θ_λ P̅_Bψ_λ+2Σ_λ∈Λ ω_λ |θ_λ | ,

for weights ω_λ to be defined later. Our final estimator is then given by s_θ̂, where

θ=_θ∈ . crit (θ, B ). .

For all θ∈ℝ^M, let J(θ)={.λ∈Λ, θ_λ≠0.} , M(θ)=CardJ(θ). Let δ∈(0,1) and, for every λ,λ′ ∈Λ, let

ρ_M(λ,λ^′)= ⟨_λ,_λ^′⟩‖_λ‖‖λ^′‖, ρ(θ)=max_λ∈ J(θ)max_λ^′≠λρ_M(λ,λ^′) , ρ (θ)= Σ_λ∈ J(θ)Σ_λ^′> λρ_M(λ,λ^′), G(θ)=Σ_λ∈ J(θ)ω_λ^2 , F(θ)= nln(.(2M)/(δ).)max_λ∈ J(θ) .ω_λ‖_λ‖. , G=ln(.(2M)/(δ).)nmax_λ∈ .‖_λ‖ω_λ. .

Let us call Γ_M the gram matrix of D, i.e., the matrix with entries ρ_M(λ,λ′) and let ζ_M be the smallest eigenvalue of Γ_M. The following assumptions were used in [11] to state the results.

16GF(θ)M(θ)≤1 .

( 𝐇 𝟏 ​ ( θ ) subscript 𝐇 1 𝜃 \mathbf{H_{1}(\theta)} )

16GF(θ)ρ_∗(θ)√(M(θ))≤1 .

( 𝐇 𝟐 ​ ( θ ) subscript 𝐇 2 𝜃 \mathbf{H_{2}(\theta)} )

Γ_M>0 and ζ_M≥κ_M>0 .

( 𝐇 𝟑 ​ ( θ ) subscript 𝐇 3 𝜃 \mathbf{H_{3}(\theta)} )

This estimator satisfies the following Theorem.

Theorem 4.

Let δ∈(0,1), let D=(ψ_λ)_λ∈Λ, let B be a regular partition of {.1,…,n.}, with V≥ln(4Mδ⁻¹). Assume that (C(D)) holds for π the uniform distribution on Λ and, for all λ∈Λ, V_λ=V. If (H₁(θ)), (H₂(θ)) or (H₃(θ)) hold, the estimator s_θ̂ defined with L₃=2L₂ and

ω_λ≥L₃√(P̅_Bψ_λ²)√((V)/(n))

satisfies, for all α>1, with probability larger than 1-2δ, ∀θ∈Θ,

‖ s_θ-s_‖^2+(α)/(2(α+1))Σ_λ∈ω_λθ_λ-θ_λ≤(α+1)/(α-1)‖ s_θ-s_‖^2+8α^2α-1R(θ) .

Where the remainder term R(θ) is equal to F²(θ)M(θ)ln(4Mδ⁻¹)/n under (H₁(θ)) or (H₂(θ)) and to G(θ)/(nκ_M) under (H₃(θ)).

Remark 2.

The proof of Theorem 4 is decomposed into two propositions. The main one, Proposition 5 below, follows from the proofs of Theorems 1, 2 and 3 of [11] that won’t be reproduced here. We refer to this paper for the proof and for further comments on the main theorem. Let us remark that the improvement that we get using our robust approach is that we only require Pψ_λ⁴<∞ in our results whereas in [11], it is required that ‖ψ_λ ‖_∞<∞.

Remark 3.

An interesting feature of our result is that it allows to revisit famous procedures built with the empirical process. Pₙ has to be replaced by P̅_B for a proper choice of V and Bennett’s, Bernstein’s or Hoeffding’s inequalities can be replaced by Proposition 1. Theorem 4 is just an example of this general principle.

Proposition 5.

Under assumptions (H₁(θ)), (H₂(θ)) or (H₃(θ)), the following condition

∀θ∈, ‖ s_θ-s_‖^2+Σ_λ∈ω_λθ_λ-θ_λ≤‖ s_θ-s_‖^2+4Σ_λ∈ J(θ)ω_λθ_λ-θ_λ,

(2)

implies, for all α>1, ∀θ∈Θ,

‖ s_θ-s_‖^2+(α)/(2(α+1))Σ_λ∈ω_λθ_λ-θ_λ≤(α+1)/(α-1)‖ s_θ-s_‖^2+8α^2α-1R(θ) .

In order to prove Theorem 4, we only have to ensure that Condition (2) holds with the required probability, which will be done in the following proposition.

Proposition 6.

Let δ∈(0,1). Let B be a regular partition of {.1,…,n.}, with V≥ln(4Mδ⁻¹) and assume that (C(D)) holds. Assume that,

∀λ∈Λ, ω_λ≥L₃√(P̅_Bψ_λ²)√((V)/(n)) .

(3)

Then, with probability larger than 1-δ, ∀θ∈Θ,

‖ s_θ-s_‖^2+Σ_λ∈ω_λθ_λ-θ_λ≤‖ s_θ-s_‖^2+4Σ_λ∈ J(θ)ω_λθ_λ-θ_λ .

Proposition 6 is proved in Section A.2.

4 Estimator Selection

Estimator selection is a new theory developed in [3, 5]. It covers important statistical problems as Model Selection, aggregation of estimators, selecting tuning constants in statistical procedures and it allows to compare several estimation procedures. [3] developed a general approach in the spirit of [8]. It applies in various frameworks but it does not provide a method for practitioner because the resulting estimators are too hard to compute. On the other hand, [5] worked in a Gaussian regression framework and obtained efficient estimators. The approach of [5] can be adapted to the density estimation framework as we will see. In order to keep the paper of reasonable size, we won’t give practical ways to define the collections of estimators. This fundamental issue and several others are extensively discussed in [5], we refer to this paper for all the practical consequences of the main oracle inequality. As [5] worked in a Gaussian framework, they do not require any L^∞-norm. In order to emphasize the advantages of robust empirical mean estimators in this problem, let us first extend the results of [5] to the density estimation framework where conditions on L^∞-norms are classical [9, 6, 23].

4.1 The empirical version

Let (ŝ_θ)θ∈Θ be a collection of estimator of s. Let (Sₘ)_m∈M be a collection of linear subspaces of measurable functions and for all θ∈Θ, let M_θ be a subset of M, possibly random. For all θ∈Θ and all m∈M_θ, we choose an estimator s_θ,m, for example, the orthogonal projection of ŝ_θ onto Sₘ. Finally, we denote by pen:M→ℝ⁺ a function to be defined later. Let α>0 and let

crit _α(θ)=min_m∈ M _θ .‖s_θ,m‖^2-2P_ns_θ,m+α‖s_θ,m-s_θ‖^2+ pen (m). , θ=_θ∈ crit _α(θ) .

(4)

Let P(M) be the set of probability measures on M, let B(m) be the unit ball in L²-norm of Sₘ, B(m)={.t∈ Sₘ, ‖ t‖≤1.} and let Ψₘ=supₜ∈B(m) t². Let mₒ be a minimizer of n‖ s-sₘ ‖²+PΨₘ. Let us introduce the following assumption.

π∈ P ( M ), ε_n→ 0, δ_o∈(0,1) ∀ m∈ M , ‖ s_m-s_m_o‖_∞ln(.4π(m)δ_o.)n‖ s-s_m‖^2+P_m≤ε_n.

( 𝐂𝐒𝐄𝐃 𝐂𝐒𝐄𝐃 \mathbf{CSED} )

The following result holds.

Theorem 7.

Let X₁:n be i.i.d, X-valued, random variables with common density s_∈ L^2(μ). For all m∈M, let sₘ be the orthogonal projection of s_ onto Sₘ and assume that (4.1) holds. Let δ≥δₒ and let ε′ₙ=4√(εₙ)+εₙ/3 and let nₒ such that, for all n≥nₒ, εₙ′≤1/2. Let also

r_m(δ)=‖m‖∞ln(.(2)/(π(m)δ).)n .

Let θ̂ be the estimator (4) selected by a penalty pen such that, for some ν∈(0,1),

pen(m)≥(.5/2+2L₀ ν.)(PΨₘ)/(n)+(2Lₒ ‖ s‖)/(ν)rₘ(δ)+(2Lₒ)/(ν³)r²ₘ(δ) ,

where Lₒ≤16(ln 2)⁻¹+8. There exists a constant L_α such that, for all n≥nₒ, with probability larger than 1-δ, ∀θ∈Θ,

L_α‖s_θ-s_‖^2≤‖s_θ-s_‖^2+min_m∈ M _θ .‖s_θ,m-s_θ‖^2+2 pen (m). .

(5)

Theorem 7 is proved in Section A.3.

Remark 4.

It is shown in [22] that (4.1) typically holds in classical collections of models as Fourier spaces, and growing wavelet or histogram spaces, under reasonable assumptions on the risk of the estimator, for δₒ=O(n⁻κ). We refer to this paper for further details on this assumptions.

Remark 5.

It is usually assumed that, for some constant Γ, ‖Ψₘ ‖∞≤Γ PΨₘ. In that case, for those m such that PΨₘ →∞, we have rₘ(δ)=o(.n⁻¹ PΨₘ .) so that the condition on the penalty is asymptotically satisfied as soon as pen(m)>2.5PΨₘ/n. This last condition holds if we choose pen(m)>2.5‖Ψₘ ‖∞/n for example. A first application of our robust approach is that, using Corollary 3, we can choose pen(m)>5P̅_BΨₘ/n under the more reasonable assumptions (C(D)) with D=(Ψₘ)_m∈M. In that case, the condition on the penalty only holds with large probability but the interested reader can checked that this will only change δ into 2δ in (5).

Remark 6.

This result includes as a special case classical model selection framework of [9, 6] where Θ=M and, for all m∈M, ŝₘ is the projection estimator onto Sₘ.

Remark 7.

It covers also the problem of choosing a tuning parameter in a statistical estimation method. In that case Θ is usually a subset of ℝ and ŝ_θ is the estimator selected by the statistical method, with the tuning parameter equal to θ. It allows also to mix several estimation strategies, in that case Θ is typically the product of a finite set A describing the set of methods with a subspace of ℝ or ℝᵈ describing the possible values of the tuning parameters (see [5]).

4.2 A robust version

We have already shown in remark 5 that our robust approach can be used to build the penalty term in the “classical” estimator selection described above. However, this first approach relies on the assumptions that ‖Ψₘ ‖∞≤Γ PΨₘ, ‖ sₘ-s_m′‖∞≤Γ‖ sₘ-s_m′‖. We will now present another approach, totally based on robust estimators, which works without these assumptions. In this section, (ψ_λ)_λ∈Λ is an orthonormal system in L²(μ) and Λ_M ⊂Λ is a finite subset. Let (Λₘ)_m∈M be a collection of subsets of Λ_M, let Λₙ=∪_m∈MΛₘ, and for all m∈M, let Sₘ the linear span of (ψ_λ)_λ∈Λₘ. Let (ŝ_θ)θ∈Θ be a collection of estimator of s. For all θ∈Θ, let M_θ be a subset of M, possibly random. For all θ∈Θ and all m∈M_θ, we choose an estimator s_θ,m, for example, the orthogonal projection of ŝ_θ onto Sₘ. For all θ∈Θ, for all m∈M_θ and for all λ∈Λₘ, let β_λ^θ=⟨s_θ,m,_λ⟩. For all λ∈Λₙ, let B_λ be a regular partition of {.1,…,n.}, with cardinality V_λ to be defined later. Let pen:M→ℝ⁺ a function to be defined later. Let α>0 and let

crit _α(θ)=min_m∈ M _θ .‖s_θ,m‖^2-2Σ_λ∈mβ_λ^θP B _λ_λ+α‖s_θ,m-s_θ‖^2+ pen (m). θ=_θ∈ crit _α(θ) .

(6)

This estimator satisfies the following theorem.

Theorem 8.

Let X₁:n be i.i.d, X-valued random variables with common density s_∈ L^2(μ). Let δ∈(0,1) and ε∈(0,1/4). Let (ŝ_θ)_θ∈Θ be a collection of estimators, let (ψ_λ)_λ∈Λ, Λ_M, (Λₘ)_m∈M, (Sₘ)_m∈M, (M_θ)_θ∈Θ and (s_θ,m)_θ∈,m∈ M _θ be defined as above. Let π be a probability measure on Λ_M. Assume that, for all λ∈Λ_M, V_λ≥ln(2(π(λ)δ)⁻¹) Then, the estimator θ̂ defined in (6) with pen(m)≥(L₄)/(ε n)Σ_λ∈Λₘvar_P(ψ_λ)V_λ, where L₄=9L₁²/4 satisfies, with probability larger than 1-δ/2, ∀θ∈Θ,

((1-4ε)α)/(2(8+α))‖s_θ-s_‖^2≤‖s_θ-s_‖^2+min_m∈ M _θ .‖s_θ-s_θ‖^2+ pen (m). .

Theorem 8 is proved in Section A.4.

Remark 8.

In order to choose the penalty term, one can use Corollary 3. Under assumption (C(D)) for the dictionary (ψ_λ)_λ∈Λ_M, we have, with our choice of V_λ,

ℙ{.∀λ∈Λ_M, var_P(ψ_λ)≤2P̅_B_λψ_λ² .}≥1-(δ)/(2) .

we can therefore use the data-driven penalty

pen(m)=(2L₄)/(ε n)Σ_λ∈Λₘ(P̅_B_λψ_λ²)V_λ .

Remark 9.

Compared to Theorem 7, we see that the collection of models (Sₘ)m∈M is restricted here to a family generated by an orthonormal system (ψ_λ)λ∈Λ_M, the penalty term is in general heavier, which yields a loss (of order sup_λ∈ΛₘV_λ) in the convergence rates. On the other hand, we do not require ‖Ψₘ ‖∞ to be finite, we only need a finite moment of order 4 for the functions ψ_λ. Moreover, in order to build a data-driven penalty in Theorem 7, we asked that ‖Ψₘ ‖∞<<(PΨₘ)², whereas we only require now a bound on √(Pψ_λ⁴)/Pψ_λ² 1_Pψ_λ²≠0 of order smaller than √(n/V_λ). In order to emphasize the difference between these conditions, let us consider the case of an histogram, where for some disjoint measurable sets (I_λ)_λ∈Λₘ, ψ_λ=(μ(I_λ))⁻¹⁄² 1_I_λ. In that case, we have

‖Ψₘ ‖_∞=max_λ∈Λₘ(1)/(μ(I_λ)), Pψ_λ²=(PI_λ)/(μ(ψ_λ)), √(Pψ_λ⁴)=(√(PI_λ))/(μ(I_λ)) .

If s_ is upper bounded by c₊, we deduce that PΨₘ≤c₊ dₘ, where dₘ is the number of pieces of the histogram. If, moreover, s_ is lower bounded by c₋, we have

(√(Pψ_λ⁴))/(Pψ_λ²)≤(1)/(c₋√(μ(I_λ))).

The condition of Theorem 8 is therefore satisfied as soon as, for some constant r sufficiently large, μ(I_λ)≥r⁻¹ nV_λ⁻¹ whereas the condition of Theorem 7 holds only if μ(I_λ)>>dₘ⁻². This last condition is much more restrictive when the histograms are irregular.

Remark 10.

Important collections (ψ_λ)_λ∈Λ are the wavelet spaces, used for example in [18]. It is shown for example in [9] that the hard thresholded estimator of [18] coincide with the estimator chosen by model selection with the penalty dₘ ℓ(n), where ℓ(n) is the threshold. Moreover, the soft thresholded estimator coincide with the Lasso-estimator presented in the previous section (see for example [11] for details). Our estimator selection procedure can be used with wavelet estimators; it allows to select with the data the best strategie, together with the best thresholds.

5 Robust Estimators in M-estimation

The rest of the paper is devoted to the study of robust estimators in a more general context of M-estimation. These estimators will be defined using a slightly more elaborated construction than the one presented in Section 2. This general principle will then be applied to classical problems as density estimation and regression.

5.1 The general case

Hereafter, (X,X) denotes a measurable space, γ:X→ℝ is a measurable function, called contrast, P be a probability measure, we want to estimate the target s_=_t∈ X Pγ(t) based on the observation of i.i.d random variables X₁:n=X₁,…,Xₙ with common distribution P. Let 8≤V≤n/2 and let B be a a regular partition of {.1,...,n.}, with cardinality V. Let X_B_K=(Xᵢ)_i∈ B_K and let S be a subspace of X. Let ŝ_K be any estimator defined as a function ŝ_K=F(X_B_K) valued in S. For all K,K′=1,…,V and for all functions t, let

P̅_K,K′t=Med{.P_B_Jt, J≠K,K′ .} .

Our final estimator is defined as

s=s_K_, K_=_K=1,...,Vmax_K^′=1,…,V .P_K,K^′(.γ(s_K)-γ(s_K^′).). .

(7)

The risk of an estimator ŝ is measured with the excess risk

(s,s_)=P(.γ(s)-γ(s_).) .

We denote by s_o=_t∈ SPγ(t). We assume the following margin type condition.

N∈ N ,(α_i)i=1,…,N< 1, s.t. on_ε, max_K ‖ var [.(.γ(s_K)-γ(s_o).)(X) |. X_B_K.]‖∞ ≤σ_0^2(s_K,s_o)^2+Σ_i=1^Nσ_i^2(s_K,s_o)^2α_i.

( 𝐂𝐌𝐚𝐫𝐠 𝐂𝐌𝐚𝐫𝐠 \mathbf{CMarg} )

Remark 11.

Assumption (5.1) is not classical and might surprise at first sight. It will be discussed in Section 5.2. In particular, we show in this section that (5.1) holds under few assumptions on the data and the space S in density estimation and in a general not bounded, heteroscedastic, non Gaussian and random design regression framework.

We finally denote, for all real numbers a by ⌈ a⌉ the smallest integer b such that b≥a. Our result is the following.

Theorem 9.

Let X₁:n be i.i.d random variables and let δ>0 such that ⌈ln(δ⁻²)⌉≤n/2. Let B be a regular partition of {.1,…,n.}, with V=⌈ln(δ⁻²)⌉∨ 8. Let (ŝ_K)[K=1,…,V] be a sequence of estimators satisfying (5.1) and let s_K be the associated estimator defined in (7). Let C₀=L₁ and for all i=1,…,N, let Cᵢ=4(1-αᵢ)(L₁ αᵢ^αᵢ)¹/(1-αᵢ). For all Δ>1, let

νₙ(Δ)=C₀ σ₀√((V)/(n))+(N)/(Δ), Rₙ(Δ)=Σᵢ₌₁^N Cᵢ (.Δ^αᵢσᵢ√((V)/(n)).)⁽1)/(1-αᵢ).

For all Δ>1, with probability larger than 1-δ-ε,

(.1-ν_n(Δ).)(s_K_,s_o)≤(.1+3ν_n(Δ).)_K .(s_K,s_o). +R_n(Δ) .

In particular, for all Δ, n such that νₙ(Δ)≤1/2, we have, with probability larger than 1-ε-δ,

(s_K_,s_)≤(s_o,s_)+(.1+8ν_n(Δ).)_K .(s_K,s_o). +2R_n(Δ).

Theorem 9 is proved in Section B.1.

Remark 12.

Assume that, for all K, s_K=_t∈ SP_B_Kt and let ŝₙ denote the classical empirical risk minimizer, s_n=_t∈ SP_nγ(t). ŝₙ is known to have a nice behavior when the contrast γ is bounded and under some margin condition such as (see [25, 27] and the references therein),

α∈[0,1] and A≥ 1; s.t. ∀ t∈ S, var _P((γ(t)-γ(s_o)))≤ A(t,s_o)^α .

Our approach does not require a finite sup norm for γ. However, it should be mentioned that the confidence level δ has to be chosen in advance and that we loose a log factor in the expectation, as the ŝ_K are built with only V/n data.

5.2 Application to classical statistical problems

The aim of this section is to apply Theorem 9 in some well known problems. We show in particular that Condition (5.1) holds in these frameworks.

5.2.1 Density estimation with L²-loss

Assume that X₁:n have common marginal density s_. Assume that s_∈ L^2(μ). Then we have, for all t in L²(μ),

‖ s_-t‖^2=‖ s_‖^2+‖ t‖^2-2∫ tsdμ=‖ s_‖^2+‖ t‖^2-2Pt=‖ s_‖^2+Pγ(t).

In the previous inequality, γ(t)=‖ t‖²-2t, thus, s_=_t∈ L^2(μ)Pγ(t). We also have

Pγ(s_)=‖ s_‖^2-2∫ s_^2dμ=-‖ s_‖^2 ,

hence,

(s,s_)=‖ t‖^2-2∫ tsdμ+‖ s_‖^2=‖s-s_‖^2 .

Let S a linear space of measurable functions and let

s_K=_t∈ SP_B_Kγ(t).

ŝ_K is easily computed since, for all orthonormal bases (ψ_λ)_λ∈Λ of S, we have

ŝ_K=Σ_λ∈Λ(P_B_Kψ_λ)ψ_λ.

Let us denote by sₒ the orthogonal projection of s_ onto S. We have, from Pythagoras relation,

(s_K,s_)=‖s_K-s_‖^2=‖s_K-s_o‖^2+‖ s_o-s_‖^2.

Given an orthonormal basis (ψ_λ)_λ∈Λ of S, we have

𝔼(.‖ŝ_K-sₒ ‖² .)=𝔼(.Σ_λ∈Λ(.(P_B_K-P)ψ_λ .)² .)=(Σ_λ∈Λ var(ψ_λ(X₁)))/(|B_K|)=(PΨ-‖ sₒ ‖²)/(|B_K|) .

In the previous inequality, the function Ψ is equal to

Ψ=Σ_λ∈Λ ψ_λ²=supₜ∈ B t², where B={.t∈ S, ‖ t‖≤1.} .

The following proposition holds.

Proposition 10.

Let X₁:n be random variables with common marginal density s_ with respect to the Lebesgue measure μ. Assume that s_∈ L^2(μ). Let S be a linear space of measurable functions. Let V be an integer and let B₁,…,B_V be a regular partition of {.1,…,n.}. For all K=1,…,V, let ŝ_K be any estimator taking value in S and measurable with respect to σ(X_B_K). Then Condition (5.1) is satisfied with N=1, σ₀=0, α₁=1/2, σ₁²=PΨ-‖ sₒ ‖².

Proof.

We have γ(ŝ_K)=‖ŝ_K ‖²-2ŝ_K, hence,

var(.γ(ŝ_K(X))-γ(sₒ) |. X_B_K.)=4var(.(ŝ_K-sₒ)(X) |. X_B_K.).

We can write ŝ_K=Σ_λ∈Λâ_λ^K ψ_λ, with â_λ^K measurable with respect to σ(X_B_K). From Cauchy-Schwarz inequality, using the independence between X and the Xᵢ,

var((ŝ_K-sₒ)(X). . |. X_B_K)=𝔼(.(.Σ_λ∈Λ(â_λ^K-Pψ_λ)(ψ_λ(X)-Pψ_λ).)² |. X_B_K.)≤Σ_λ∈Λ[â_λ^K-Pψ_λ]²𝔼(.Σ_λ∈Λ[ψ_λ(X)-Pψ_λ]² .)=‖ŝ_K-sₒ ‖² (.PΨ-‖ sₒ ‖² .).

Therefore, (5.1) holds with N=1, σ₀=0, α₁=1/2, σ₁²=PΨ-‖ sₒ ‖². ∎

We can deduce from Theorem 9 the following result.

Proposition 11.

Let X₁:n be i.i.d random variables with common density s_ with respect to the Lebesgue measure μ. Assume that s_∈ L^2(μ). Let δ>0 such that ⌈ln(δ⁻²)⌉≤n/2. Let B be a regular partition of {.1,…,n.}, with V=⌈ln(δ⁻²)⌉∨ 8. ∀ K=1,…,V, let s_K=t∈ SP_B_Kγ(t) and let s_K be the associated estimator defined in (7). We have, for L₅=2√(e)+8L₁ e¹⁄⁴,

P (.‖s_K_-s_‖^2> ‖ s_o-s_‖^2+L_5(.P-‖ s_o‖^2.)(V)/(n).)≤ 2δ .

Remark 13.

A classical density estimator is the minimizer of the empirical risk,

s_m=_t∈ S_mP_nγ(t) .

This estimator satisfies the following risk bound (see for example [23]), with probability larger than 1-δ, for all ε>0,

‖s-s_‖^2≤‖ s_o-s_‖^2+(1+ε)P-‖ s_o‖^2n+C^′(.v^2ln(δ^-1)nε+b^2ln(δ^-1)^2ε^3n^2.).

In the last inequality v²=supₜ∈ B P((t-Pt)²)≤PΨ-‖ sₒ ‖², b²=‖Ψ‖_∞. The empirical risk minimizer is better when the bound b²≤n(PΨ-‖ sₒ ‖²) holds. However, our approach does not require that the sup-norm of the function Ψ is bounded, we only need a finite expectation.

Proof.

Since (5.1) holds, it comes from Theorem 9 that, for all Δ≥2, the estimator (7) satisfies, with probability larger than 1-δ,

‖s_K_-s_‖^2≤ ‖ s_o-s_‖^2+(.1+(8)/(Δ).)K .‖s_K-s‖^2. +L_1^2Δ(.P-‖ s_o‖^2.)(V)/(n) .

(8)

Moreover, as 𝔼(.‖ŝ_K-sₒ ‖² .)=(PΨ-‖ sₒ ‖²)/(|B_K|), by regularity of the partition, we deduce that

𝔼(.‖ŝ_K-sₒ ‖² .)≤2(.PΨ-‖ sₒ ‖² .)(V)/(n).

Hence, from (8) and Lemma 26, with probability larger than 1-2δ,

‖s_K_-s_‖^2≤‖ s_o-s_‖^2+(.2√e+16√eΔ+L_1^2Δ.)(.P-‖ s_o‖^2.)(V)/(n) .

We conclude the proof, choosing Δ=4e¹⁄⁴/L₁. ∎

5.2.2 Density estimation with Küllback loss

We observe X₁:n with density s_ with respect to the Lebesgue measure μ on [0,1]. We denote by L the space of positive functions t such that P|ln t|<∞. We have

s_=_t∈ L .-Pln(t). , hence γ(t)=-ln t.

Let S be a space of histograms on [0,1], i.e. there exists a partition (I_λ)_λ∈Λ of [0,1], where, for all λ∈Λ, μ(I_λ)≠0, such that all functions t in S can be written t=Σ_λ∈Λ a_λ 1_I_λ. We denote by

s_o=_t∈ S .-Pln t. , and ∀ K=1,…,V, s_K=_t∈ S-P_B_Kln t.

It comes from Jensen’s inequality that

sₒ=Σ_λ∈Λ(P1_I_λ)/(μ(I_λ))1_I_λ, and ∀ K=1,…,V, s̃_K=Σ_λ∈Λ(P_B_K1_I_λ)/(μ(I_λ))1_I_λ.

Therefore, for all K=1,…,V,

(sₒ)/(s̃_K)=Σ_λ∈Λ(P1_I_λ)/(P_B_K1_I_λ)1_I_λ.

For all K=1,…,V, the estimator s̃_K has a finite Küllback risk on the event

Ω_K={.∀λ∈Λ such that P1_I_λ>0, P_B_K1_I_λ>0.} .

In order to avoid this problem, we choose x>0 and define, for all K=1,…,V, the estimator

ŝ_K=(s̃_K+x1_[[0,1]])/(1+x).

(9)

This way, ŝ_K is always non-null and the Küllback risk of ŝ_K is always finite. Finally, we denote by Cᵣeg(S) a constant such that

min_λ∈ s.t. PI_λ≠ 0PI_λ≥ C_reg^-1(S).

( 𝐂𝐑 𝐂𝐑 \mathbf{CR} )

The following result ensures that (5.1) holds.

Proposition 12.

Let X₁:n be random variables with density s_ with respect to the Lebesgue measure μ on [0,1]. Let S be a space of histograms on [0,1]. Let V≤n be an integer and let B be a regular partition of {.1,…,n.}. For all K=1,…,V, let ŝ_K be the estimator defined in (9). Then, (5.1) holds with σ₀=0, N=1, α₁=1/2 and σ₁²=2+3ln(1+x⁻¹) .

Proposition 12 is proved in Section B.2.

Remark 14.

As for the L²-loss, no assumptions on the observations are required to check (5.1).

Proposition 13.

Let X₁:n with density s_ with respect to the Lebesgue measure μ on [0,1]. Let S be a space of histograms on [0,1] with finite dimension D and let Cᵣeg(S) be a constant satisfying condition (CR). Let δ>0 such that ⌈ln(δ⁻²)⌉≤n/2. Let B be a regular partition of {.1,…,n.}, with V=⌈ln(δ⁻²)⌉∨ 8. For all K=1,…,V, let ŝ_K be the estimator defined in (9), with x=n⁻¹ and let s_K_ be the associated estimator defined in (7). Then, for some absolute constant L₆,

P (.(s_K_,s_)> (s_o,s_)+L_6(Dln(n)V)/(n)(.1+C_reg(S)n.).)≤ 2δ .

Proposition 13 is proved in Section B.3.

5.2.3 Regression with L²-risk

Let (Xᵢ,Yᵢ)ᵢ₌₁,...,ₙ be independent copies of a pair of random variables (X,Y) satisfying the following equation

Y=s_(X)+σ(X)ε, E (ε|X)=0, E (ε^2|X)=1, σ,s_∈ L^2(P_X).

Let t in L²(P_X), we have

E (.(Y-t(X))^2.)= E (.(Y-t(X))^2 |. X.)= E (.(s_(X)-t(X))^2+σ^2(X).).

Hence, s_=_t∈ L^2(P_X)Pγ(t), with γ(t)(X,Y)=(Y-t(X))². Moreover, we have

(t,s_)= E (.(s_(X)-t(X))^2+σ^2(X).)- E (.σ^2(X).)= E (.(s_(X)-t(X))^2.)

Let S be a linear space of functions and let sₒ be the orthogonal projection of s_ onto S in L²(P_X). Let B={.t∈ S,‖ t‖_L²(P_X)≤1.}, Ψ=supₜ∈ B t². We assume the following moments assumptions. There exist finite D and M_Ψ such that

𝔼(.(Y-sₒ(X))² Ψ(X).)≤D, 𝔼(Ψ²(X))≤M_Ψ.

( 𝐂𝐌 𝐂𝐌 \mathbf{CM} )

The following Proposition ensures that Condition CM implies Condition (5.1).

Proposition 14.

Let (X,Y),((Xᵢ,Yᵢ))_[i=1,… n] be i.i.d. pairs of random variables such that,

Y=s_(X)+σ(X)ε, where E (ε|X)=0, E (ε^2|X)=1, s_,σ∈ L^2(P_X) .

Let S be a linear space of functions measurable with respect to L²(P_X). Let sₒ be the orthogonal projection of s_ onto S and assume the moment condition (CM). Let V≤n be an integer and let B be a regular partition of {.1,…,n.}. For all K=1,…,V, let s_K=_t∈ SP_B_Kγ(t). Then, (5.1) holds, with σ₀²=2M_Ψ, N=1, α₁=1/2, σ₁²=8D.

Proposition 14 is proved in Section B.4. We can now derive the following consequence of Theorem 9.

Proposition 15.

Let (X,Y),((Xᵢ,Yᵢ))_[i=1,… n] be i.i.d. pairs of random variables such that,

Y=s_(X)+σ(X)ε, where E (ε|X)=0, E (ε^2|X)=1, s_,σ∈ L^2(P_X).

Let S be a linear space of functions measurable with respect to L²(P_X). Let sₒ be the orthogonal projection on s_ onto S and assume the moment condition (CM). Let δ>0 such that ⌈ln(δ⁻²)⌉≤n/2. Let B be a regular partition of {.1,…,n.}, with V=⌈ln(δ⁻²)⌉∨ 8. For all K=1,…,V, let s_K=t∈ SP_B_Kγ(t) and let s_K be the associated estimator defined in (7). If 96eM_Ψ V≤n, then, for L₇=384+128√(2)eL₁,

P (.(s_K_,s_)≤(s_o,s_)+L_7(DV)/(n).)≥ 1-3δ.

Proposition 15 is proved in Section B.5.

6 Extension to mixing data

An interesting feature of our approach is that it can easily be adapted to deal with mixing data, using coupling methods as for example in [4, 16, 23, 22]. Let us recall the definition of β-mixing and ϕ-mixing coefficients, due respectively to [33] and [21]. Let (Ω,A,ℙ) be a probability space and let X and Y be two σ-algebras included in A. We define

β(X,Y)=1/2sup{.Σᵢ₌₁^I Σⱼ₌₁^J |ℙ{.Aᵢ ∩ Bⱼ .} -ℙ{.Aᵢ .} ℙ{.Bⱼ .} |.} , ϕ(X,Y)=sup_A∈X, ℙ{.A.}>0sup_B∈Yℙ{.B|A.} -ℙ{.B.} .

The first sup is taken among the finite partitions (Aᵢ)[i=1,…,I] and (Bⱼ)[j=1,…,J] of Ω such that, for all i=1,…,I, Aᵢ ∈X and for all j=1,…,J, Bⱼ ∈Y.

For all stationary sequences of random variables (Xₙ)ₙ∈ℤ defined on (Ω,A,ℙ), let

βₖ=β(σ(Xᵢ,i≤0),σ(Xᵢ,i≥k)), ϕₖ=ϕ(σ(Xᵢ,i≤0),σ(Xᵢ,i≥k)) .

The process (Xₙ)ₙ∈ℤ is said to be β-mixing when βₖ → 0 as k→∞, it is said to be ϕ-mixing when ϕₖ → 0 as k→∞. It is easily seen, see for example inequality (1.11) in [10] that β(X,Y)≤ϕ(X,Y) so that (Xₙ)ₙ∈ℤ is ϕ-mixing implies (Xₙ)ₙ∈ℤ is β-mixing.

6.1 Basic concentration inequality

In this section, we assume that n=2Vq. For all K=1,…,2V, let B_K={.(K-1)q+1,…,Kq.}, Bₘᵢₓ=(B₁,…,B₂V). For every f: R R, let P̅ₘᵢₓ f=P̅_Bₘᵢₓf. Our first result is the extension of Proposition 1 to mixing processes.

Proposition 16.

Let X₁:n be a stationary, real-valued, β-mixing process and assume that

Cᵦ²=2Σₗ≥0(l+1)βₗ<∞.

There exists an event Ω_coup satisfying ℙ{.Ω_coup .}≥1-2Vβ_q such that, for all f such that ‖ f‖_[4,P]:=(.Pf⁴ .)¹⁄⁴<∞, for all V≥ln(2δ⁻¹), we have, for L₈=4√(6e),

ℙ{.P̅ₘᵢₓ f-Pf>L₈√(Cᵦ)‖ f‖_[4,P]√((V)/(n))∩Ω_coup .}≤δ .

If moreover, X₁:n is ϕ-mixing, with Σᵢ₌₀ⁿ ϕ_q≤Φ², then, for all f such that Pf²<∞, for all V≥ln(2δ⁻¹),

ℙ{.P̅ₘᵢₓ f-Pf>L₈ Φ√(var_P f)√((V)/(n))∩Ω_coup .}≤δ .

Remark 15.

This result allows to extend the propositions of Section 2 and 3. We see that we only have to modify slightly the estimation procedure, choosing P̅ₘᵢₓ instead of P̅_B to deal with these processes and that the price to pay is to work under higher moments conditions. Under these stronger conditions, all the results remain valid.

Proof.

For all x>0 and all V, if the following bounds are satisfied

Med {.P_B_Kf, K=1,3,…,2V-1.} -Pf≤x Med {.P_B_Kf, K=2,4,…,2V.} -Pf≤x .

Then, there is at least V values of P_B_Kf smaller than Pf+x, so that P̅ₘᵢₓ f-Pf≤x. Hence

ℙ{.P̅ₘᵢₓ f-Pf>x.}≤ℙ{.Med{.P_B_Kf, K=1,3,…,2V-1.} -Pf>x.} +ℙ{.Med{.P_B_Kf, K=2,4,…,2V.} -Pf>x.}

The proof is then a consequence of Lemma 17 below. ∎

Lemma 17.

Let X₁:n be a stationary, real-valued, β-mixing process and assume that

Cᵦ²=2Σₗ≥0(l+1)βₗ<∞.

For all a∈{.0,1.}, there exists an event Ωᵃ_coup satisfying ℙ{.Ωᵃ_coup .}≥1-Vβ_q such that, for all f such that ‖ f‖₄:=(.Pf⁴ .)¹⁄⁴<∞, for all V≥ln(2δ⁻¹), we have, ℙ(.(Ωᵃᵦ)ᶜ ∩Ωᵃ_coup .)≤δ/2, where Ωᵦᵃ is the set

Med{.P_B_Kf, K=1+a,3+a,…,2V-1+a.} -Pf≤L₈√(Cᵦ)‖ f‖₄√((V)/(n)) .

If moreover, X₁:n is ϕ-mixing, with Σᵢ₌₀ⁿ ϕ_q≤Φ², then, for all f such that Pf²<∞, for all V≥ln(2δ⁻¹), we have, ℙ(.(Ωᵃ_ϕ)ᶜ ∩Ωᵃ_coup .)≤δ/2, where Ω_ϕᵃ is the set

Med{.P_B_Kf, K=1+a,3+a,…,2V-1+a.} -Pf≤L₈ Φ√(var_P f)√((V)/(n)) .

Lemma 17 is proved in Section C.1.

6.2 Construction of Estimators

The purpose of this section is to adapt the results of Section 5 to our mixing setting. Let V≥8 and assume that n can be divided by 2V. Let us write q=n/(2V) and, for all K=1,…,2V, B_K={.(K-1)q+1,…,Kq.}. Let us then denote by I=∪_K=1^V B₂K-1 ⊂{.1,…,n.}. We define now, for all K≠K′=1,…,V,

P̅ᵐⁱˣ_K,K′=Med_J∈I-{.B₂K-1,B_2K′-1.} P_B_Jt.

Let us assume, as in Section 5, that, for all K=1,…,V, ŝ_K=F(X_B₂K-1). Our final estimator is defined now by s^mix=s_K_^mix, where

K_^mix=_K=1,...,Vmax_K^′=1,…,V .P^mix_K,K^′(.γ(s_K)-γ(s_K^′).). .

(10)

Our result is the following.

Theorem 18.

Let X₁:n be ϕ-mixing random variables with Σ_q=1ⁿ ϕ_q≤Φ². Let δ>0 such that ⌈ln(2δ⁻²)⌉≤n/2 and let V=⌈ln(2δ⁻²)⌉∨ 16. Let (ŝ_K)_[K=1,…,V] be a sequence of estimators such that ŝ_K=F_K(X₂K-1) and assume that (5.1) holds. Let ŝᵐⁱˣ be the associated estimator defined in (10). Let C₀=L₈ Φ, and ∀ i=1,…,N, Cᵢ=(1-αᵢ)(.C₀(αᵢ)^αᵢ.)¹/(1-αᵢ). For all Δ>1, let

νₙ(Δ)=C₀ σ₀√((V)/(n))+(N)/(Δ), Rₙ(Δ)=Σᵢ₌₁^N Cᵢ (.Δ^αᵢσᵢ√((V)/(n)).)⁽1)/(1-αᵢ).

For all Δ>1, we have, with probability larger than 1-δ-ε-Vβ_q,

(.1-ν_n(Δ).)(s^mix,s_o)≤(.1+3ν_n(Δ).)_K=1,…,V .(s_2K-1,s_o). +R_n(Δ) .

In particular, for all Δ, n such that νₙ(Δ)≤1/2, we have, with probability larger than 1-ε-δ-Vβ_q,

(s^mix,s_)≤(s_o,s_)+(.1+8ν_n(Δ).)_K=1,…,V .(s_2K-1,s_o). +2R_n(Δ).

Remark 16.

The only price to pay to work with these data is therefore the Vβ_q in the control of the probability and a small improvements of the constants. When δ,ε=O(n⁻²) and β_q≤Cq⁻⁽¹⁺ᶿ⁾ for θ>1, we obtain that this probability is O(n⁻²) in both cases, the price is negligible.

6.3 Application to density estimation

Proposition 10 ensures that Condition (5.1) holds for all stationary processes and all estimators. In order to extend Propostion 11 to mixing data, we only have to extend the inequality on 𝔼(.‖ŝ_K-sₒ ‖² .). The result is the following.

Proposition 19.

Let X₁:n be a ϕ-mixing process such that Σ_q=1ⁿ ϕ_q≤Φ, with common marginal density s_. Assume that s_∈ L^2(μ). Let δ>0 such that ⌈ln(δ⁻²)⌉≤n/2 and let V=⌈ln(δ⁻²)⌉∨ 16. Let B₁,…,B₂V be a regular partition of {.1,…,n.}. For all K, let s_K=_t∈ SP_B_Kγ(t) and let ŝᵐⁱˣ be the associated estimator defined in (10). We have

P (.‖s^mix-s_‖^2> ‖ s_o-s_‖^2+C^2P(V)/(n).)≤δ+Vβ_q.

Proof.

As, on Ω_good the estimators are equal to those built using the independent data (A_K)_[K=1,…,V], we only have to prove, thanks to Theorem 18 and Lemma 26 that

𝔼(.‖ŝ_K-sₒ ‖² .)≤CΦ² PΨ(V)/(n)

to obtain the result. We have, from inequality (23),

𝔼(.‖ŝ_K-sₒ ‖² .)=Σ_λ∈Λ var(.(1)/(|B_K|)Σ_i∈ B_Kψ_λ(Xᵢ).)≤(4)/(|B_K|)P(.νΨ.)≤(4Φ² PΨ)/(|B_K|).

∎

Acknowledgements

We want to thank Antonio Galves for many discussions and fruitful advices during the redaction of the paper.

ML was supported by FAPESP grant 2009/09494-0. This work is part of USP project “Mathematics, computation, language and the brain”.

Appendix A Proofs of the basic results

A.1 Proof of Proposition 1

We have

P̅_Bf-Pf=Med{.P_B_Kf-Pf, K=1,…,V.} .

Denote, for all x>0, by Nₓ=Card{.K=1,…,V, s.t. P_B_Kf-Pf>x.}. For all V≤n, we have

ℙ {.P̅_Bf-Pf>x.}≤ℙ{.Nₓ≥(V)/(2).} .

Now let r>√(2) to be chosen later. It comes from Tchebychev’s inequality that

∀ K=1,…,V, ℙ{.P_B_Kf-Pf>√((var_P f)/(r))√((1)/(Card{.B_K .})).}≤r .

(11)

Let us also introduce a random variable B with binomial distribution B(V,r). It comes from Lemma 23 that

ℙ{.P̅_Bf-Pf>√((2)/(r))√(var_P f)√((V)/(n)).}≤ℙ{.B≥(V)/(2).} .

Now, it comes from equation (2.8) in Chapter 2 of [26] that

ℙ{.B≥(V)/(2).}≤e⁻(V)/(2)ln(.(1)/(4r(1-r)).).

We choose r=(1-√(1-e⁻²))/2, so that 4r(1-r)=e⁻². For all V≥ln(δ⁻¹), we have

ℙ{.P̅_Bf-Pf>√((2)/(r))√(var_P f)√((V)/(n)).}≤δ.

(12)

Finally, we have r≥1/(12e).

A.2 Proof of Proposition 6

Let us first remark that, for all θ∈Θ, we have

crit (θ, B ) =‖ s_θ‖^2-2Σ_λ∈θ_λP_ B λ+2Σ_λ∈ω_λθ_λ =‖ s_θ‖^2-2Σ_λ∈θ_λP_λ+2Σ_λ∈θ_λ(P-P B )λ+2Σ_λ∈ω_λθ_λ =‖ s_θ-s‖^2-‖ s_‖^2+2Σ_λ∈θ_λ(P-P_ B )_λ+2Σ_λ∈ω_λθ_λ .

By definition of θ̂, we have therefore, for all θ∈Θ,

‖ s_θ-s_‖^2≤ ‖ s_θ-s_‖^2+2Σ_λ∈(θ_λ-θ_λ)(P-P_ B )_λ +2Σ_λ∈ω_λθ_λ-2Σ_λ∈ω_λθ_λ .

Let Ω_good be the event

∀λ∈, P_λ-P_λ≤ L_2P_ B _λ^2√(V)/(n) .

Since V≥ln(4Mδ⁻¹) and (C(D)) holds, it comes from Corollary 3 for the dictionary D and the uniform probability measure on Λ that ℙ{.Ω_good .}≥1-δ. Moreover, on Ω_good

∀λ∈Λ, 2|(P-P̅_B)ψ_λ |≤ω_λ .

On Ω_good, for all θ∈Θ, by the triangular inequality, we have then

‖ s_θ-s_‖^2+Σ_λ∈ω_λθ_λ-θ_λ ≤‖ s_θ-s_‖^2+2Σ_λ∈ω_λθ_λ-θ_λ+2Σ_λ∈ω_λθ_λ-2Σ_λ∈ω_λθ_λ ≤‖ s_θ-s_‖^2+2Σ_λ∈ J(θ)ω_λθ_λ-θ_λ+2Σ_λ∈ J(θ)ω_λθ_λ-2Σ_λ∈ J(θ)ω_λθ_λ

≤‖ s_θ-s_‖^2+4Σ_λ∈ J(θ)ω_λθ_λ-θ_λ .

A.3 Proof of Theorem 7

Let us first remark that, for all mₒ ∈M,

crit α(θ)+‖ s‖^2+2(P_n-P)s_m_o =min_m∈ M θ ‖s_θ,m-s‖^2-2(P_n-. .P)(s_θ,m-s_m-s_m_o+s_m). .+α‖s_θ,m-s_θ‖^2+ pen (m) .

For all m∈M, we denote by (ψ_λ)_λ∈Λₘ an orthonormal basis of Sₘ and by β_λ^θ=⟨s_θ,m,_λ⟩. Using Cauchy-Schwarz inequality and the inequality 2ab≤ε a²+ε⁻¹ b², for all θ∈Θ, for all m∈M_θ, we obtain

2(P_n-P)(s_θ,m-s_m) =2Σ_λ∈_m(β_λ^θ-P_λ)[.(P_n-P)_λ.] ≤ 2Σ_λ∈_m(β_λ^θ-P_λ)^2Σ_λ∈_m[.(P_n-P)_λ.]^2 ≤εΣ_λ∈_m(β_λ^θ-P_λ)^2+(1)/(ε)Σ_λ∈_m[.(P_n-P)_λ.]^2 =ε‖s_θ,m-s_m‖^2+Σ_λ∈_m[.(P_n-P)_λ.]^2ε.

Let now Ω_good be the event

∀ m∈ M , (P_n-P)(s_m_o-s_m)≤ε_n^′(.‖ s_m-s_‖^2+P_mn.) Σ_λ∈_m[.(P_n-P)_λ.]^2≤(1+L_0ν)P_mn+L_o‖ s‖νr_m(δ)+L_oν^3r^2_m(δ) .

It comes from Lemma 24 in the appendix that, for all ν>0 and all δ>δₒ, ℙ{.Ω_good .}≥1-δ. Moreover, on Ω_good, for all ε>0, we have

|2(P_n-P). +ε‖s_θ,m-s_m‖^2+(1+L_0ν)P_mn+L_o‖ s‖νr_m(δ)+L_oν^3r^2_m(δ)ε .

We choose ε=1/2 and n≥nₒ. Since

pen(m)≥(.5/2+2L₀ ν.)(PΨₘ)/(n)+(2Lₒ ‖ s‖)/(ν)rₘ(δ)+(2Lₒ)/(ν³)r²ₘ(δ) ,

on Ω_good, using the triangular inequality, we have then

crit α(θ) +‖ s‖^2+2(P_n-P)s_m_o ≤min_m∈ M θ .(3)/(2)‖s_θ,m-s‖^2+α‖s_θ,m-s_θ‖^2+2 pen (m). ≤ 3‖s_θ-s_‖^2+min_m∈ M _θ .(3+α)‖s_θ,m-s_θ‖^2+2 pen (m). , crit α(θ) +‖ s‖^2+2(P_n-P)s_m_o

≥min_m∈ M θ .(1)/(2)‖s_θ,m-s‖^2+α‖s_θ,m-s_θ‖^2. ≥(.(1)/(4)(α)/(2).)‖s_θ-s_‖^2 .

By definition of θ̂, it follows that, on Ω_good, ∀θ∈Θ

‖s_θ-s_‖^2 ≤ 3‖s_θ-s_‖^2+min_m∈ M _θ .(3+α)‖s_θ,m-s_θ‖^2+2 pen (m). .

A.4 Proof of Theorem 8

The proof follows essentially the same steps as the one of Theorem 7. Let mₒ be a minimizer of 2ε‖ s_-s_m‖^2+4e(ε n)^-1Σ_λ∈_m var _P_λV_λ. We have

$$\mathrm{crit}_{\alpha}(\theta) +\left\lVert s_{\star}\right\rVert^{2}+2\sum_{\lambda\in\Lambda_{m_{o}}}P\psi_{\lambda}(\overline{P}_{\mathcal{B}_{\lambda}}-P)\psi_{\lambda^{\prime}}\qquad {}=\min_{m\in\mathcal{M}_{\theta}}\left\lbrace \left\lVert\breve{s}_{\theta,m}-s_{\star}\right\rVert^{2}-2\sum_{\lambda\in\Lambda_{m}}(\widehat{\beta}_{\lambda}^{\theta}-P\psi_{\lambda})(\overline{P}_{\mathcal{B}_{\lambda}}\psi_{\lambda}-P\psi_{\lambda})\right.\qquad {} \left.+2\sum_{\lambda\in\Lambda_{m}\cup\Lambda_{m_{o}}}a_{\lambda}(\overline{P}_{\mathcal{B}_{\lambda}}-P)\psi_{\lambda}+\alpha\left\lVert\breve{s}_{\theta,m}-\widehat{s}_{\theta}\right\rVert^{2}+\mathrm{pen}(m)\right\rbrace \enspace,$$

where, for all λ∈Λₘ ∪Λ_mₒ, a_λ=Pψ_λ(.1_λ∈Λ_mₒ-1_λ∈Λₘ.), so that Σ_λ∈Λₘ ∪Λ_mₒa_λ²=‖ sₘ-s_mₒ‖². Using Cauchy-Schwarz inequality and the inequality 2ab≤ε a²+ε⁻¹ b², for all θ∈Θ, for all m∈M_θ, we obtain

2Σ_λ∈mβ_λ^θ-P_λ P B _λ_λ-P_λ ≤ 2Σ_λ∈_m(β_λ^θ-P_λ)^2Σ_λ∈m[.(P B _λ_λ-P_λ).]^2 ≤Σ_λ∈_m(β_λ^θ-P_λ)^2+(1)/()Σ_λ∈m[.(P B _λ_λ-P_λ).]^2 =‖s_θ,m-s_m‖^2+(1)/()Σ_λ∈m[.(P B _λ_λ-P_λ).]^2 .

(13) (14)

2Σ_λ∈_m∪m_o a_λ(P B _λ-P)_λ ≤ 2Σ_λ∈_m∪_m_oa_λ^2Σ_λ∈_m∪m_o[.(P B _λ-P)_λ.]^2 ≤ε‖ s_m-s_m_o‖^2+(1)/(ε)Σ_λ∈_m∪m_o[.(P B λ-P)λ.]^2 ≤ 2ε‖ s-s_m_o‖^2+2ε‖ s_m-s‖^2+(1)/(ε)(.Σ_λ∈_m∪m_o[.(P B _λ-P)_λ.]^2.).

(15)

Let now Ω_good be the event

$$\forall\lambda\in\Lambda_{M}, \qquad\left\lvert\overline{P}_{\mathcal{B}_{\lambda}}\psi_{\lambda}-P\psi_{\lambda}\right\rvert\leq L_{1}\sqrt{\mathrm{var}_{P}(\psi_{\lambda})}\sqrt{\frac{V_{\lambda}}{n}}\enspace.$$

Using a union bound in Proposition 1, since V_λ≥ln(2(π(λ)δ)⁻¹), we have, ℙ{.Ω_good .}≥1-δ/2. Moreover, on Ω_good, from (14). for all η>0, we have

$$2\sum_{\lambda\in\Lambda_{m}}\left\lvert\widehat{\beta}_{\lambda}^{\theta}-P\psi_{\lambda}\right\rvert\left\lvert\overline{P}_{\mathcal{B}_{\lambda}}\psi_{\lambda}-P\psi_{\lambda}\right\rvert\leq\eta\left\lVert\breve{s}_{\theta,m}-s_{m}\right\rVert^{2}+\frac{L_{1}^{2}}{\eta n}\sum_{\lambda\in\Lambda_{m}}\mathrm{var}_{P}(\psi_{\lambda})V_{\lambda}.$$

From (15), for all ε>0, on Ω_good,

2 Σ_λ∈_m∪m_o a_λ(P B λ-P)λ ≤ 2ε‖ s-s_m_o‖^2+2ε‖ s_m-s‖^2+L_1^2nε(.Σ_λ∈_m∪_m_o var P(λ)V_λ.) ≤ 2ε‖ s-s_m_o‖^2+2ε‖ s_m-s‖^2 +L_1^2nε(.Σ_λ∈_m var _P(_λ)V_λ+Σ_λ∈_m_o var _P(_λ)V_λ.)

$${} \leq 4\epsilon\left\lVert s_{m}-s_{\star}\right\rVert^{2}+\frac{L_{2}^{2}}{n\epsilon}\sum_{\lambda\in\Lambda_{m}}\mathrm{var}_{P}(\psi_{\lambda})V_{\lambda}\enspace.$$

The last inequality is due to the definition of mₒ. We choose η=4ε, on Ω_good, using the triangular inequality, we deduced that, for L₄=L₂²+L₁²/4=9L₁²/4, crit α(θ)+‖ s‖^2+2Σ_λ∈m_oP_λ(P B _λ_λ-P_λ) is smaller than the infimum over m∈M_θ

$$\leq 4\left\lVert\widehat{s}_{\theta}-s_{\star}\right\rVert^{2}+\left(\left.4+\alpha\right.\right)\left\lVert\breve{s}_{\theta,m}-\widehat{s}_{\theta}\right\rVert^{2}+\frac{L_{4}}{n\epsilon}\sum_{\lambda\in\Lambda_{m}}\mathrm{var}_{P}(\psi_{\lambda})V_{\lambda}+\mathrm{pen}(m)\enspace.$$

On the other hand, crit α(θ)+‖ s‖^2+2Σ_λ∈m_oP_λ(P B _λ_λ-P_λ) is larger than the infimum over m∈M_θ of

$$\geq\frac{1}{2}\left(\left.(1-4\epsilon)\wedge\alpha\right.\right)\left\lVert\widehat{s}_{\theta}-s_{\star}\right\rVert^{2}-\frac{L_{4}}{n\epsilon}\sum_{\lambda\in\Lambda_{m}}\mathrm{var}_{P}(\psi_{\lambda})V_{\lambda}+\mathrm{pen}(m)\enspace.$$

Since

$$\mathrm{pen}(m)\geq\frac{L_{4}}{n\epsilon}\sum_{\lambda\in\Lambda_{m}}\mathrm{var}_{P}(\psi_{\lambda})V_{\lambda}\enspace,$$

by definition of θ̂, we deduce that, on Ω_good, for all θ∈Θ,

$$\frac{1}{2}\qquad {} \leq 4\left\lVert\widehat{s}_{\theta}-s_{\star}\right\rVert^{2}+\min_{m\in\mathcal{M}_{\theta}}\left\lbrace \left(\left.4+\alpha\right.\right)\left\lVert\breve{s}_{\theta,m}-\widehat{s}_{\theta}\right\rVert^{2}+2\mathrm{pen}(m)\right\rbrace \enspace.$$

Appendix B Proofs for M-estimation

B.1 Proof of Theorem 9

Let Ω₍C) be the event

$$\max_{K}\left\lVert\mathrm{var}\left[\left.\left(\left.\gamma(\widehat{s}_{K})-\gamma(s_{o})\right.\right)(X)\,\right|\left.\,X_{B_{K}}\right.\right]\right\rVert_{\infty}\leq\sigma_{0}^{2}\ell(\widehat{s}_{K},s_{o})^{2}+\sum_{i=1}^{N}\sigma_{i}^{2}\ell(\widehat{s}_{K},s_{o})^{2\alpha_{i}}.$$

We apply Proposition 1 to f=(.γ(ŝ_K)-γ(sₒ).)1_Ω₍C) and to -f, conditionally to the random variables X_B_K and to the partition B=(B_J)_J≠K,K′ of {.1,…,n.} /(B_K ∪ B_K′), with cardinality n-|B_K|-|B_K′|≥n(1-2/V-2/n)>n/2 since V≥8. We have

$$\mathrm{var}(f(X)|X_{B_{K}})\leq\sigma_{0}^{2}\ell(\widehat{s}_{K},s_{o})^{2}+\sum_{i=1}^{N}\sigma_{i}^{2}\ell(\widehat{s}_{K},s_{o})^{2\alpha_{i}}\enspace.$$

Since V≥ln(δ⁻²), Proposition 1 gives that, with probability larger than 1-2δ², conditionally to X_B_K, the following event holds

_(C)∩ (P_K,K^′-P)(.γ(s_K)-γ(s_o).) > L_1σ_0^2(s_K,s_o)^2+Σ_i=1^Nσ_i^2(s_K,s_o)^2α_i√(V)/(n) _(C)∩ (P_K,K^′-P)(.γ(s_K)-γ(s_o).) > L_1(.σ_0(s_K,s_o)+Σ_i=1^Nσ_i(s_K,s_o)^α_i.)√(V)/(n) .

As the bound on the probability does not depend on X_B_K, the same bound holds unconditionally. We use repeatedly the classical inequality a^α b¹-α≤α a+(1-α)b. Let rₙ=√(n⁻¹ V), let C₀=L₁ and, for all i=1,…,N let Cᵢ=(1-αᵢ)(.L₁(αᵢ)^αᵢ.)¹/(1-αᵢ), we obtain that the following event has probability smaller than 2δ²,

$$\Omega_{(C)}\cap \left\lvert(\overline{P}_{K,K^{\prime}}-P)\left(\left.\gamma(\widehat{s}_{K})-\gamma(s_{o})\right.\right)\right\rvert\qquad \qquad\leq\left(\left.C_{0}\sigma_{0}r_{n}+\frac{N}{\Delta}\right.\right)\ell(\widehat{s}_{K},s_{o})+\sum_{i=1}^{N}C_{i}\left(\left.\Delta^{\alpha_{i}}\sigma_{i}r_{n}\right.\right)^{\frac{1}{1-\alpha_{i}}}.$$

Using a union bound, we get that the probability that the following event has probability larger than 1-V(V-1)δ²-ε, ∀ K,K′=1,…,V,

$${} \left|(\overline{P}_{K,K^{\prime}}-P)\left(\left.\gamma(\widehat{s}_{K})-\gamma(\widehat{s}_{K^{\prime}})\right.\right)\right|\qquad \quad\leq\left(\left.C_{0}\sigma_{0}r_{n}+\frac{N}{\Delta}\right.\right)\left(\left.\ell(\widehat{s}_{K},s_{o})+\ell(\widehat{s}_{K^{\prime}},s_{o})\right.\right)+2\sum_{i=1}^{N}C_{i}\left(\left.\Delta^{\alpha_{i}}\sigma_{i}r_{n}\right.\right)^{\frac{1}{1-\alpha_{i}}}.$$

Given the value of V, we obtain that

$$V(V-1)\delta^{2} =\left(\left.\left\lceil\ln(\delta^{-2})\right\rceil\left(\left.\left\lceil\ln(\delta^{-2})\right\rceil-1\right.\right)\right.\right)\delta^{2}\leq\left(\left.\left(\left.\ln(\delta^{-2})+1\right.\right)\ln(\delta^{-2})\right.\right)\delta^{2}\qquad {} \leq\delta\left(\left.\sup_{\delta\in(0,1)}\left\lbrace \left.\delta\left(\left.\left(\left.\ln(\delta^{-2})+1\right.\right)\ln(\delta^{-2})\right.\right)\right.\right\rbrace \right.\right)\leq\delta.$$

Hereafter, we denote by

$$\nu_{n}(\Delta)=C_{0}\sigma_{0}r_{n}+\frac{N}{\Delta},\quad R_{n}(\Delta)=2\sum_{i=1}^{N}C_{i}\left(\left.\Delta^{\alpha_{i}}\sigma_{i}r_{n}\right.\right)^{\frac{1}{1-\alpha_{i}}}$$

and by Ω_good(δ) the event,

$$\bigcap_{K,K^{\prime}=1,\ldots,V} \left\lbrace \left\lvert(\overline{P}_{K,K^{\prime}}-P)\left(\left.\gamma(\widehat{s}_{K})-\gamma(\widehat{s}_{K^{\prime}})\right.\right)\right\rvert\right.\qquad {} \left.\qquad\leq\nu_{n}(\Delta)\left(\left.\ell(\widehat{s}_{K},s_{o})+\ell(\widehat{s}_{K^{\prime}},s_{o})\right.\right)+R_{n}(\Delta)\right\rbrace .$$

Let Kₒ be the index such that Pγ(ŝ_K) is minimal. For all n, Δ sufficiently large so that νₙ(Δ)<1, on Ω_good, we have

$$\ell(\widehat{s}_{K_{\star}},s_{o})=\left(\left.P\left(\left.\gamma(\widehat{s}_{K_{\star}})-\gamma(\widehat{s}_{K_{o}})\right.\right)\right.\right)+\ell(\widehat{s}_{K_{o}},s_{o})\qquad {}=\left[\left.P\left(\left.\gamma(\widehat{s}_{K_{\star}})-\gamma(\widehat{s}_{K_{o}})\right.\right)-\nu_{n}(\Delta)\left(\left.\ell(\widehat{s}_{K_{\star}},s_{o})+\ell(\widehat{s}_{K_{o}},s_{o})\right.\right)\right.\right]\qquad {}+\nu_{n}(\Delta)\left(\left.\ell(\widehat{s}_{K_{\star}},s_{o})\right.\right)+\left(\left.1+\nu_{n}(\Delta)\right.\right)\ell(\widehat{s}_{K_{o}},s_{o})\qquad {}=\sup_{K}\left[\left.P\left(\left.\gamma(\widehat{s}_{K_{\star}})-\gamma(\widehat{s}_{K})\right.\right)-\nu_{n}(\Delta)\left(\left.\ell(\widehat{s}_{K_{\star}},s_{o})+\ell(\widehat{s}_{K},s_{o})\right.\right)\right.\right]$$ $${}+\nu_{n}(\Delta)\left(\left.\ell(\widehat{s}_{K_{\star}},s_{o})\right.\right)+\left(\left.1+\nu_{n}(\Delta)\right.\right)\ell(\widehat{s}_{K_{o}},s_{o})\qquad {} \leq\sup_{K}\left[\left.\overline{P}_{K_{\star},K}\left(\left.\gamma(\widehat{s}_{K_{\star}})-\gamma(\widehat{s}_{K})\right.\right)\right.\right]\qquad {}+\nu_{n}(\Delta)\left(\left.\ell(\widehat{s}_{K_{\star}},s_{o})\right.\right)+\left(\left.1+\nu_{n}(\Delta)\right.\right)\ell(\widehat{s}_{K_{o}},s_{o})+R_{n}(\Delta).$$

By definition of K_, we have

$$\quad\leq\sup_{K}\left[\left.\overline{P}_{K_{o},K}\left(\left.\gamma(\widehat{s}_{K_{\star}})-\gamma(\widehat{s}_{K})\right.\right)\right.\right]+\left(\left.1+\nu_{n}(\Delta)\right.\right)\ell(\widehat{s}_{K_{o}},s_{o})+R_{n}(\Delta)\qquad \quad\leq\sup_{K}\left[\left.P\left(\left.\gamma(\widehat{s}_{K_{o}})-\gamma(\widehat{s}_{K})\right.\right)+\nu_{n}(\Delta)\left(\left.\ell(\widehat{s}_{K_{o}},s_{o})+\ell(\widehat{s}_{K},s_{o})\right.\right)\right.\right]\qquad \qquad+\left(\left.1+\nu_{n}(\Delta)\right.\right)\ell(\widehat{s}_{K_{o}},s_{o})+2R_{n}(\Delta)\qquad \quad=\sup_{K}\left[\left.\left(\left.1+\nu_{n}(\Delta)\right.\right)\ell(\widehat{s}_{K_{o}},s_{o})-\left(\left.1-\nu_{n}(\Delta)\right.\right)\ell(\widehat{s}_{K},s_{o})\right.\right]$$ $$\qquad+\left(\left.1+\nu_{n}(\Delta)\right.\right)\ell(\widehat{s}_{K_{o}},s_{o})+2R_{n}(\Delta)\qquad \quad=\left(\left.1+3\nu_{n}(\Delta)\right.\right)\ell(\widehat{s}_{K_{o}},s_{o})+2R_{n}(\Delta)\enspace.$$

This concludes the proof of Theorem 9.

B.2 Proof of Proposition 12

We have

$$\frac{s_{o}}{\widehat{s}_{K}}=\sum_{\lambda\in\Lambda}\frac{(1+x)P\mathbf{1}_{I_{\lambda}}}{P_{B_{K}}\mathbf{1}_{I_{\lambda}}+x}\mathbf{1}_{I_{\lambda}}.$$

We deduce that

$$\ln\left(\left.\frac{s_{o}}{\widehat{s}_{K}}\right.\right)\leq\ln\left(\left.\frac{(1+x)}{x}\right.\right)=\ln\left(\left.x^{-1}+1\right.\right).$$

We have, by Cauchy-Schwarz inequality,

ℓ(ŝ_K,sₒ)=∫ sₒ ln(.(sₒ)/(ŝ_K).)=∫_sₒ>ŝ_Ksₒ ln(.(sₒ)/(ŝ_K).)-∫_sₒ<ŝ_Ksₒ ln(.(ŝ_K)/(sₒ).)≥∫_sₒ>ŝ_Ksₒ ln(.(sₒ)/(ŝ_K).)-∫_sₒ<ŝ_Ksₒ (.ln(.(ŝ_K)/(sₒ).).)²

(16)

Let us now recall the following lemma, see for example [26] Lemma 7.24.

Lemma 20.

For all probability measures P, Q with P<<Q,

$$\frac{1}{2}\int(dP\wedge dQ)\left(\left.\ln\left(\left.\frac{dP}{dQ}\right.\right)\right.\right)^{2}\leq\int dP\ln\left(\left.\frac{dP}{dQ}\right.\right)$$

Using Lemma 20, we get

$$\int_{s_{o}\lt \widehat{s}_{K}}s_{o}\left(\left.\ln\left(\left.\frac{\widehat{s}_{K}}{s_{o}}\right.\right)\right.\right)^{2}\leq\int s_{o}\wedge\widehat{s}_{K}\left(\left.\ln\left(\left.\frac{s_{o}}{\widehat{s}_{K}}\right.\right)\right.\right)^{2}\leq 2\int s_{o}\ln\left(\left.\frac{s_{o}}{\widehat{s}_{K}}\right.\right).$$

Plugging this inequality in (16), we obtain

$$\int_{s_{o}\gt \widehat{s}_{K}}s_{o}\ln\left(\left.\frac{s_{o}}{\widehat{s}_{K}}\right.\right)\leq 3\int s_{o}\ln\left(\left.\frac{s_{o}}{\widehat{s}_{K}}\right.\right).$$

Finally, we obtain

var=∫_sₒ<ŝ_Ksₒ (.ln(.(sₒ)/(ŝ_K).).)²+∫_sₒ>ŝ_Ksₒ (.ln(.(sₒ)/(ŝ_K).).)²≤2∫ sₒ ln(.(sₒ)/(ŝ_K).)+ln(x⁻¹+1)∫_sₒ>ŝ_Ksₒ ln(.(sₒ)/(ŝ_K).)≤(2+3ln(x⁻¹+1))ℓ(ŝ_K,sₒ).

(5.1) holds with σ₀=0, N=1, α₁=1/2,

$$\sigma_{1}^{2}=2+3\ln(1+x^{-1})\enspace.$$

B.3 Proof of Proposition 13

Condition (5.1) holds from Proposition 12. Hence, Theorem 9 ensures that, for all Δ≥2, the estimator (7) satisfies, with probability larger than 1-δ,

$$\ell(\widehat{s}_{K_{\star}},s_{\star})\leq\ell(s_{o},s_{\star})+\left(\left.1+\frac{8}{\Delta}\right.\right)\inf_{K}\left\lbrace \left.\ell(\widehat{s}_{K},s_{\star})\right.\right\rbrace +L_{1}^{2}\Delta(2+3\ln(1+x^{-1}))\frac{V}{n}\enspace.$$

Let us now fix some K in 1,…,V and let us denote, for all λ∈Λ by a_λ=P(I_λ), â_λ=(P_B_K(I_λ)+x)/(1+x). We have

$$\mathbb{E}\left(\left.\ell(\widehat{s}_{K},s_{o})\right.\right) =\mathbb{E}\left(\left.\int\left(\left.\sum_{\lambda\in\Lambda}\frac{a_{\lambda}}{\mu(I_{\lambda})}\ln\left(\left.\frac{a_{\lambda}}{\widehat{a}_{\lambda}}\right.\right)\right.\right)d\mu\right.\right)\qquad {}=\sum_{\lambda\in\Lambda,a_{\lambda}\neq 0}a_{\lambda}\mathbb{E}\left(\left.\ln\left(\left.\frac{a_{\lambda}}{\widehat{a}_{\lambda}}\right.\right)\right.\right)\enspace.$$

Now, we have

$$\ln\left(\left.\frac{a_{\lambda}}{\widehat{a}_{\lambda}}\right.\right)=-\ln\left(\left.1-\frac{a_{\lambda}-\widehat{a}_{\lambda}}{a_{\lambda}}\right.\right),\;with\;\frac{a_{\lambda}-\widehat{a}_{\lambda}}{a_{\lambda}}=1-\frac{\widehat{a}_{\lambda}}{a_{\lambda}}\leq 1-\frac{x}{(1+x)}\enspace.$$

We use the following inequalities, for all u≤1-Γ⁻¹

$$\frac{-\ln(1-u)-u}{u^{2}}\leq\frac{\Gamma^{2}\ln(\Gamma)}{(\Gamma-1)^{2}}+\frac{\Gamma}{\Gamma-1}\enspace.$$

we deduce that

$$\ln\left(\left.\frac{a_{\lambda}}{\widehat{a}_{\lambda}}\right.\right)\leq\frac{a_{\lambda}-\widehat{a}_{\lambda}}{a_{\lambda}}+\left(\left.(1+x)^{2}\ln\left(\left.\frac{1+x}{x}\right.\right)+1+x\right.\right)\left(\left.\frac{a_{\lambda}-\widehat{a}_{\lambda}}{a_{\lambda}}\right.\right)^{2}\enspace.$$

Moreover, we have,

$$0\lt x\leq 1,\;and\;\mathbb{E}\left(\left.a_{\lambda}-\widehat{a}_{\lambda}\right.\right)\leq 0,\;\mathbb{E}\left(\left.\left(\left.\widehat{a}_{\lambda}-a_{\lambda}\right.\right)^{2}\right.\right)\leq\frac{a_{\lambda}}{|B_{K}|}+x^{2}\enspace.$$

We deduce that, for all λ∈Λ such that a_λ≠0,

a_λ𝔼(.ln(.(a_λ)/(â_λ).).)=a_λ𝔼(.-ln(.1-(a_λ-â_λ)/(a_λ).).)≤𝔼(.a_λ-â_λ .)+(4ln(2x⁻¹)+2)/(a_λ)𝔼(.(.â_λ-a_λ .)² .)≤(.4ln(2x⁻¹)+2.)(.(1)/(|B_K|)+(x²)/(a_λ).)≤(.4ln(2x⁻¹)+2.)(.(1)/(|B_K|)+x² Cᵣeg(S).).

We deduce that

$$\mathbb{E}\left(\left.\ell(\widehat{s}_{K},s_{o})\right.\right)\leq\left(\left.4\ln(2x^{-1})+2\right.\right)D\left(\left.\frac{V}{n}+x^{2}C_{reg}(S)\right.\right).$$

Hence, applying Lemma 26 with α=1 and the previous bound in expectation, we obtain

$$\mathbb{P}\left\lbrace \left.\inf_{K=1,\ldots,V}\ell(\widehat{s}_{K},s_{o})\gt \sqrt{e}\left(\left.4\ln(2x^{-1})+2\right.\right)D\left(\left.\frac{V}{n}+x^{2}C_{reg}(S)\right.\right)\right.\right\rbrace \leq\delta.$$

This concludes the proof, choosing Δ=2 and x=n⁻¹.

B.4 Proof of Proposition 14

We have

$$\mathrm{var}\qquad {}=\mathrm{var}\left(\left.\left(\left.\widehat{s}_{K}(X)-s_{o}(X)\right.\right)^{2}+2\left(\left.s_{o}(X)-\widehat{s}_{K}(X)\right.\right)\left(\left.Y-s_{o}(X)\right.\right)\,\right|\left.\,X_{B_{K}}\right.\right)\qquad {} \leq 2\mathrm{var}\left(\left.\left(\left.\widehat{s}_{K}(X)-s_{o}(X)\right.\right)^{2}\,\right|\left.\,X_{B_{K}}\right.\right)\qquad \quad+8\mathrm{var}\left(\left.\left(\left.s_{o}(X)-\widehat{s}_{K}(X)\right.\right)\left(\left.Y-s_{o}(X)\right.\right)\,\right|\left.\,X_{B_{K}}\right.\right)$$ $${} \leq 2\mathbb{E}\left(\left.\left(\left.\widehat{s}_{K}(X)-s_{o}(X)\right.\right)^{4}\,\right|\left.\,X_{B_{K}}\right.\right)\qquad \quad+8\mathbb{E}\left(\left.\left(\left.s_{o}(X)-\widehat{s}_{K}(X)\right.\right)^{2}\left(\left.Y-s_{o}(X)\right.\right)^{2}\,\right|\left.\,X_{B_{K}}\right.\right).$$

Let us now consider an orthonormal basis (in L²(P_X)) (ψ_λ)_λ∈Λ of S and let us write

$$s_{o}=\sum_{\lambda\in\Lambda}a_{\lambda}\psi_{\lambda},\;\widehat{s}_{K}=\sum_{\lambda\in\Lambda}\widehat{a}_{\lambda}(K)\psi_{\lambda},\;hence\;P(s_{o}-\widehat{s}_{K})^{2}=\sum_{\lambda\in\Lambda}(a_{\lambda}-\widehat{a}_{\lambda}(K))^{2}.$$

From Cauchy-Schwarz inequality Ψ=Σ_λ∈Λ ψ_λ², hence, from Cauchy-Schwarz inequality, we have

$${}=\left(\left.\sum_{\lambda\in\Lambda}(a_{\lambda}-\widehat{a}_{\lambda}(K))\psi_{\lambda}\right.\right)^{2}\qquad {} \leq\left(\left.\sum_{\lambda\in\Lambda}(a_{\lambda}-\widehat{a}_{\lambda}(K))^{2}\right.\right)\left(\left.\sum_{\lambda\in\Lambda}\psi_{\lambda}^{2}\right.\right)=\ell(\widehat{s}_{K},s_{o})\Psi.$$

Thus, we have

$$\mathbb{E}\left(\left.\left(\left.\widehat{s}_{K}(X)-s_{o}(X)\right.\right)^{4}\,\right|\left.\,X_{B_{K}}\right.\right)\leq(\ell(\widehat{s}_{K},s_{o}))^{2}\mathbb{E}\left(\left.\Psi^{2}(X)\right.\right)=M_{\Psi}(\ell(\widehat{s}_{K},s_{o}))^{2}.$$

Moreover, from Cauchy-Schwarz inequality,

$$\mathbb{E}\left(\left.\left(\left.s_{o}(X)-\widehat{s}_{K}(X)\right.\right)^{2}\left(\left.Y-s_{o}(X)\right.\right)^{2}\,\right|\left.\,X_{B_{K}}\right.\right)\leq\ell(\widehat{s}_{K},s_{o})D.$$

We deduce that (5.1) holds, with σ₀²=2M_Ψ, N=1, α₁=1/2, σ₁²=8D.

B.5 Proof of Proposition 15

Theorem 9 and 144M_Ψ V≤n ensure that, for all Δ≥4, we have νₙ(Δ)=6√((M_Ψ V)/(n))+(1)/(Δ)≤1/2, hence, the estimator (7) satisfies, with probability larger than 1-δ,

$$\ell(\widehat{s}_{K_{\star}},s_{\star})\leq\ell(s_{o},s_{\star})+\left(\left.1+8\nu_{n}(\Delta)\right.\right)\inf_{K}\left\lbrace \left.\ell(\widehat{s}_{K},s_{\star})\right.\right\rbrace +8L_{1}^{2}\Delta\frac{DV}{n}.$$

(17)

In order to control K .(s_K,s)., we use the following method, due to Saumard [30]. We fix K in 1,… V and, for all constants C, we denote by

$$\mathcal{G}_{C}=\left\lbrace \left.t\in S,\;\ell(t,s_{o})\leq C\right.\right\rbrace ,\qquad\mathcal{G}_{\gt C}=\left\lbrace \left.t\in S,\;\ell(t,s_{o})\gt C\right.\right\rbrace .$$

We have, by definition of ŝ_K,

$$\ell\qquad \Rightarrow\sup_{t\in\mathcal{G}_{C}}P_{B_{K}}(\gamma(s_{o})-\gamma(t))\leq\sup_{t\in\mathcal{G}_{\gt C}}P_{B_{K}}(\gamma(s_{o})-\gamma(t))\qquad \Rightarrow\sup_{t\in\mathcal{G}_{C}}\left\lbrace \left.(P_{B_{K}}-P)(\gamma(s_{o})-\gamma(t))-\ell(t,s_{o})\right.\right\rbrace\qquad \qquad\leq\sup_{t\in\mathcal{G}_{\gt C}}\left\lbrace \left.(P_{B_{K}}-P)(\gamma(s_{o})-\gamma(t))-\ell(t,s_{o})\right.\right\rbrace$$ $$\Rightarrow\sup_{t\in\mathcal{G}_{\gt C}}\left\lbrace \left.(P_{B_{K}}-P)(\gamma(s_{o})-\gamma(t))-\ell(t,s_{o})\right.\right\rbrace \geq 0.$$

Let us now write

$$\gamma(s_{o})-\gamma(t) =(Y-s_{o}(X))^{2}-(Y-t(X))^{2}\qquad {}=-2(Y-s_{o}(X))(s_{o}(X)-t(X))-(s_{o}(X)-t(X))^{2}\enspace.$$

Given an orthonormal basis (in L²(P_X)) (ψ_λ)_λ∈Λ of S, we write

$$s_{o}(X)-t(X)=\sum_{\lambda\in\Lambda}a_{\lambda}\psi_{\lambda}.$$

Hence, we have, for all t in S, for all ε>0, using Cauchy-Schwarz inequality,

-P)(γ(sₒ)-γ(t))=-2Σ_λ∈Λ a_λ(P_B_K-P)(.(Y-sₒ)ψ_λ .)-Σ_λ,λ′ ∈Λa_λ a_λ′(P_B_K-P)(ψ_λ ψ_λ′)≤2√(Σ_λ∈Λ a_λ²)√(Σ_λ∈Λ(.(P_B_K-P)(.(Y-sₒ)ψ_λ .).)²) +Σ_λ∈Λ a_λ²√(Σ_λ,λ′ ∈Λ(.(P_B_K-P)(ψ_λ ψ_λ′).)²)

$${} \leq\frac{1}{\epsilon}\sum_{\lambda\in\Lambda}\left(\left.(P_{B_{K}}-P)\left(\left.(Y-s_{o})\psi_{\lambda}\right.\right)\right.\right)^{2}\qquad \quad+\left(\left.\epsilon+\sqrt{\sum_{\lambda,\lambda^{\prime}\in\Lambda}\left(\left.(P_{B_{K}}-P)(\psi_{\lambda}\psi_{\lambda^{\prime}})\right.\right)^{2}}\right.\right)\ell(t,s_{0}).$$

We have obtained that if ℓ(ŝ_K,sₒ)>C then

$$\sup_{t\in\mathcal{G}_{\gt C}}\left\lbrace \frac{1}{\epsilon}\right. \left.\sum_{\lambda\in\Lambda}\left(\left.(P_{B_{K}}-P)\left(\left.(Y-s_{o})\psi_{\lambda}\right.\right)\right.\right)^{2}\right.\qquad {} \left.-\left(\left.1-\epsilon-\sqrt{\sum_{\lambda,\lambda^{\prime}\in\Lambda}\left(\left.(P_{B_{K}}-P)(\psi_{\lambda}\psi_{\lambda^{\prime}})\right.\right)^{2}}\right.\right)\ell(t,s_{0})\right\rbrace \geq 0.$$

Let Ω_K={.Σ_λ,λ′ ∈Λ(.(P_B_K-P)(ψ_λ ψ_λ′).)²≤1/4.} and take ε=1/4, we deduce from the previous bound that, on Ω_K,

$$\ell(\widehat{s}_{K},s_{o})\gt C\Rightarrow 16\sum_{\lambda\in\Lambda}\left(\left.(P_{B_{K}}-P)\left(\left.(Y-s_{o})\psi_{\lambda}\right.\right)\right.\right)^{2}\geq C.$$

This means that ℓ(ŝ_K,sₒ)1_Ω_K≤16Σ_λ∈Λ(.(P_B_K-P)(.(Y-sₒ)ψ_λ .).)², in particular,

$$\mathbb{E}\left(\left.\ell(\widehat{s}_{K},s_{o})\mathbf{1}_{\Omega_{K}}\right.\right) \leq 16\frac{\sum_{\lambda\in\Lambda}\mathrm{var}{\left(\left.(Y-s_{o})\psi_{\lambda}\right.\right)}}{|B_{K}|}\leq 16\frac{\mathbb{E}\left(\left.\left(\left.Y-s_{o}\right.\right)^{2}\Psi(X)\right.\right)}{|B_{K}|}\qquad {}=16\frac{D}{|B_{K}|}\leq 32\frac{DV}{n}\enspace.$$

(18)

We have

$$\mathbb{E}\left(\left.\sum_{\lambda,\lambda^{\prime}\in\Lambda}\left(\left.(P_{B_{K}}-P)(\psi_{\lambda}\psi_{\lambda^{\prime}})\right.\right)^{2}\right.\right)\leq\frac{\mathbb{E}(\Psi^{2})}{|B_{K}|}\leq 2\frac{M_{\Psi}V}{n}\enspace.$$

Hence, if r=(1-√(1-e⁻²))/2, by Markov property,

$$\mathbb{P}\left(\left.\sum_{\lambda,\lambda^{\prime}\in\Lambda}\left(\left.(P_{B_{K}}-P)(\psi_{\lambda}\psi_{\lambda^{\prime}})\right.\right)^{2}\gt \frac{2M_{\Psi}V}{rn}\right.\right)\leq r\enspace.$$

As r≥1/(12e) and 24e(M_Ψ V)/(n)<1/4, we deduce

$$\mathbb{P}\left(\left.\Omega_{K}^{c}\right.\right)\leq r\enspace.$$

(19)

From Lemma 27 and equations (18), (19), we deduce that

$$\mathbb{P}\left(\left.\inf_{K=1,\ldots,V}\ell(\widehat{s}_{K},s_{o})\gt 128e^{2}\frac{DV}{n}\right.\right)\leq 2e^{-V}\enspace.$$

Together with (17), this yields, for Δ=√(2)8eL₁⁻¹,

$$\mathbb{P}\left\lbrace \left.\ell(\widehat{s}_{K_{\star}},s_{\star})\gt \left(\left.384+128\sqrt{2}eL_{1}\right.\right)\frac{DV}{n}\right.\right\rbrace \leq\delta+2\delta^{2}\enspace.$$

Appendix C Proofs in the mixing-case

C.1 Proof of Proposition 17

Let a∈{.0,1.} and let us recall the following lemma due to Viennet [32].

Lemma 21. (Lemma 5.1 in [32]) Assume that the process (X₁,...,Xₙ) is β-mixing. There exist random variables (A_K)_[K=1,…,V] such that:

1. ∀ K=1,…,V, A_K has the same law as (Xᵢ)_i∈ B₂K-1+a,
2. ∀ K=1,…,V, A_K is independent of (Xᵢ)_i∈ B₁₊ₐ,...,(Xᵢ)_i∈ B₂(K-1)-1+a, A₁,...,A_K-1,
3. ∀ K=1,…,V, ℙ((Xᵢ)_i∈ B₂K-1+a≠A_K)≤β_q.

Let us define the event

$$\Omega^{a}_{coup}=\left\lbrace \left.\forall K=1,\ldots,V,\;(X_{i})_{i\in B_{2K-1+a}}=A_{K}\right.\right\rbrace .$$

It comes from Viennet’s Lemma that ℙ{.Ωᵃ_coup .}≥1-Vβ_q. For all K=1,…,V, let A_K=(Yᵢ)_i∈ B_K and for all measurable t, let

$$P_{A_{K}}t=\frac{1}{\mathrm{Card}(B_{K})}\sum_{i\in B_{K}}t(Y_{i})\enspace.$$

On Ωᵃ_coup, we have P_B₂K-1+af=P_A_Kf, hence,

p(x):=ℙ{.Med{.P_B_Kf, K=1,3,…,2V-1+a.} -Pf>x∩Ωᵃ_coup .}≤ℙ{.Card{.K=1,3,…,2V-1+a, s.t. P_B_Kf-Pf>x.}≥(V)/(2)∩Ωᵃ_coup .}≤ℙ{.Card{.K=1,…,V, s.t. P_A_Kf-Pf>x.}≥(V)/(2).} .

(20)

By Markov inequality, for all r, for all K=1,…,V,

$$\mathbb{P} \left\lbrace \left.P_{A_{K}}f-Pf\gt \sqrt{\frac{\mathrm{var}\left(\left.P_{B_{K}}f-Pf\right.\right)}{r}}\right.\right\rbrace\qquad \qquad\qquad=\mathbb{P}\left\lbrace \left.P_{B_{K}}f-Pf\gt \sqrt{\frac{\mathrm{var}\left(\left.P_{B_{K}}f-Pf\right.\right)}{r}}\right.\right\rbrace \leq r\enspace.$$

From Lemma 23, we deduce, denoting by xᵣ=√((var(.P_B_Kf-Pf.))/(r)) and by B(V,r) a binomial random variable with parameters V and r, that

$$p(x_{r})\leq\mathbb{P}\left\lbrace \left.B(V,r)\geq\frac{V}{2}\right.\right\rbrace \leq e^{\frac{V}{2}\ln\left(\left.\frac{1}{4r(1-r)}\right.\right)}\enspace.$$

(21)

We choose r=(1-√(1-e⁻²))/2 so that ln(.(1)/(4r(1-r)).)=2. We recall now the following inequality for mixing processes (see for example [16] inequalities (6.2) and (6.3) or Lemma 4.1 in [32]).

Lemma 22.

Let (Xₙ)ₙ∈ℤ be ϕ-mixing data. There exists a function ν satisfying, for all p,q in ℕ,

$$\nu=\sum_{l\geq 0}\nu_{l},\;\mathrm{with}\;P\nu_{q}\leq\beta_{q},\;P(\nu^{p})\leq p\sum_{l\geq 0}(l+1)^{p-1}\beta_{l}\;\mathrm{and}\;\left\lVert\nu_{q}\right\rVert_{\infty}\leq\phi_{q}\enspace,$$

(22)

such that, for all t in L²(μ),

$$\mathrm{var}\left(\left.\sum_{i=1}^{q}t(X_{i})\right.\right)\leq 4qP(\nu t^{2})\enspace.$$

(23)

We apply Lemma 22 and we obtain, when Cᵦ<∞, ∀ K=1,3,…,2V-1

$$\mathrm{var}\left(\left.P_{B_{K}}f-Pf\right.\right)\leq\frac{4}{\mathrm{Card}{B_{K}}}P(\nu f^{2})\leq\frac{8V}{n}\sqrt{P(\nu^{2})P(f^{4})}\enspace.$$

Moreover, when X₁:n is ϕ-mixing, with Σ_q=1ⁿ ϕ_q≤Φ², we apply Lemma 22 to f-Pf and we get ∀ K=1,3,…,2V-1,

$$\mathrm{var}\left(\left.P_{B_{K}}f-Pf\right.\right)\leq\frac{4}{\mathrm{Card}{B_{K}}}P(\nu(f-Pf)^{2})\leq 8\Phi^{2}\frac{V}{n}\mathrm{var}_{P}f\enspace.$$

Plugging these inequalities in (21) yields the result, since we have

$$x_{r}\leq\sqrt{\frac{\mathrm{var}_{P}\left(\left.(P_{B_{K}}-P)f\right.\right)}{r}}\leq\sqrt{8e\mathrm{var}_{P}\left(\left.(P_{B_{K}}-P)f\right.\right)}\enspace.$$

C.2 Proof of Theorem 18

Let us denote by Ω_(C) the same event as in the proof of Theorem 9. We can apply Lemma 17 to the function f=(.γ(ŝ_K)-γ(sₒ).)1_Ω_(C) conditionally to the random variables X_B₂K-1 and to the partition (B₂J-1)_J≠K,K′ of I/(B₂K-1 ∪ B_2K′-1), with cardinality n/2-|B₂K-1|-|B_2K′-1|≥n(1/2-2/V-2/n)>n/4 since V≥16. Condition (5.1) implies

$$\mathrm{var}_{P}\left(\left.\left(\left.\gamma(\widehat{s}_{K})-\gamma(s_{o})\right.\right)\mathbf{1}_{\Omega_{{\bf(C)}}}\,\right|\left.\,X_{B_{2K-1}}\right.\right)\leq\sigma_{0}^{2}\ell(\widehat{s}_{K},s_{o})^{2}+\sum_{i=1}^{N}\sigma_{i}^{2}\ell(\widehat{s}_{K},s_{o})^{2\alpha_{i}}\enspace.$$

We introduce

$$C_{0}=8\sqrt{e}\Phi,\;and\;\forall i=1,\ldots,N,\;C_{i}=(1-\alpha_{i})\left(\left.C_{0}(\alpha_{i})^{\alpha_{i}}\right.\right)^{1/(1-\alpha_{i})}.$$

Since V≥ln(2δ⁻²), there exists a set Ω_good satisfying ℙ{.Ω_good .}≥1-Vβ_q such that, with probability larger than 1-δ², conditionally to X_B₂K-1, the following event holds

_int∩ (P^mix_K,K^′-P)(.γ(s_K)-γ(s_o).) ≤ C_0√(V)/(n)σ_0^2(s_K,s_o)^2+Σ_i=1^Nσ_i^2(s_K,s_o)^2α_i _int∩ (P^mix_K,K^′-P)(.γ(s_K)-γ(s_o).) ≤ C_0√(V)/(n)(.σ_0(s_K,s_o)+Σ_i=1^Nσ_i(s_K,s_o)^α_i.).

where Ωᵢₙₜ=Ω_good ∩Ω_(C). As the bound on the probability does not depend on X_B₂K-1, the same bound holds unconditionally. We use repeatedly the classical inequality a^α b¹-α≤α a+(1-α)b, we obtain that

$$C_{0}\sqrt{\frac{V}{n}}\qquad {} \leq\left(\left.C_{0}\sigma_{0}\sqrt{\frac{V}{n}}+\frac{N}{\Delta}\right.\right)\ell(\widehat{s}_{K},s_{o})+\sum_{i=1}^{N}C_{i}\left(\left.\Delta^{\alpha_{i}}\sigma_{i}\sqrt{\frac{V}{n}}\right.\right)^{\frac{1}{1-\alpha_{i}}}.$$

Using a union bound, we get that the following event holds with probability larger than 1-V(V-1)δ²-ε-Vβ_q, ∀ K,K′=1,…,V,

$${} \left|(\overline{P}^{mix}_{K,K^{\prime}}-P)\left(\left.\gamma(\widehat{s}_{K})-\gamma(\widehat{s}_{K^{\prime}})\right.\right)\right|\qquad {} \leq\left(\left.C_{0}\sigma_{0}\sqrt{\frac{V}{n}}+\frac{N}{\Delta}\right.\right)\left(\left.\ell(\widehat{s}_{K},s_{o})+\ell(\widehat{s}_{K^{\prime}},s_{o})\right.\right)+2\sum_{i=1}^{N}C_{i}\left(\left.\Delta^{\alpha_{i}}\sigma_{i}\sqrt{\frac{V}{n}}\right.\right)^{\frac{1}{1-\alpha_{i}}}.$$

We conclude as in the proof of Theorem 9.

Appendix D Tools

D.1 A coupling result

The aim of this section is to prove the coupling result used in the proof of Proposition 1.

Lemma 23.

Let Y₁:N be independent random variables, let x be a real number and let

$$A=\mathrm{Card}\left\lbrace \left.i=1,\ldots,N\,s.t.\,Y_{i}\gt x\right.\right\rbrace .$$

Let p∈(0,1] such that, for all i=1,…,N, p≥ℙ{.Yᵢ>x.} and let B be a random variable with a binomial law B(N,p). There exists a coupling C̃=(Ã,B̃) such that à has the same distribution as A, B̃ has the same distribution as B and such that A≤B. In particular, for all y>0,

$$\mathbb{P}\left\lbrace \left.A\gt y\right.\right\rbrace \leq\mathbb{P}\left\lbrace \left.B\gt y\right.\right\rbrace \enspace.$$

(24)

Proof.

Let U₁:N be i.i.d random variables with uniform distribution on [0,1]. Let us define, for all i=1,…,N,

$$\tilde{A}_{i}=\mathbf{1}_{U_{i}\leq\mathbb{P}\left\lbrace \left.Y_{i}\gt x\right.\right\rbrace },\qquad\tilde{B}_{i}=\mathbf{1}_{U_{i}\leq p},\qquad\tilde{A}=\sum_{i=1}^{N}\tilde{A}_{i},\qquad\tilde{B}=\sum_{i=1}^{N}\tilde{B}_{i}\enspace.$$

By construction, for all i=1,…,N, A_i≤B_i, hence A≤B. Moreover, B̃ is the sum of independent random variables with common Bernoulli distribution of parameter p, it has therefore the same distribution as B. We also have that (Ãᵢ)[i=1,…,N] has the same distribution as (1_Yᵢ>x)[i=1,…,N] since the marginals have the same distributions and the coordinates are independent. Since A=Σᵢ₌₁^N 1_Yᵢ>x, A and à have the same distribution.

In order to prove (24), we just say that A≤B implies that {.Ã>y.} ⊂{.B̃>y.}, hence

$$\mathbb{P}\left\lbrace \left.A\gt y\right.\right\rbrace =\mathbb{P}\left\lbrace \left.\tilde{A}\gt y\right.\right\rbrace \leq\mathbb{P}\left\lbrace \left.\tilde{B}\gt y\right.\right\rbrace =\mathbb{P}\left\lbrace \left.B\gt y\right.\right\rbrace \enspace.$$

∎

D.2 Concentration inequalities for Estimator Selection

Lemma 24.

Let (Sₘ)_m∈M be a collection of linear spaces of measurable functions and for all m∈M, let (ψ_λ)_λ∈Λₘ be an orthonormal basis of Sₘ and Ψₘ=Σ_λ∈Λₘψ_λ². Let π be a probability measure on M. For all δ∈(0,1), we denote by

$$r_{m}(\delta)=\frac{\sqrt{\left\lVert\Psi_{m}\right\rVert_{\infty}}\ln\left(\left.\frac{2}{\pi(m)\delta}\right.\right)}{n}\enspace.$$

Let X₁:n be i.i.d, X-valued, random variables with common density s_∈ L^2(μ). For all m∈M, let sₘ be the orthogonal projection of s_ onto Sₘ and assume that (4.1) holds. Let us denote, for all δ∈(0,1),

$$\forall m\in\mathcal{M},\;\eta_{\infty,2}(1\vee\left\lVert s\right\rVert)\sqrt{\left\lVert s_{m}-s_{\star}\right\rVert^{2}+\frac{P\Psi_{m}}{n}}\ln\left(\left.\frac{4}{\delta\pi(m)}\right.\right)\leq\varepsilon_{m}(\delta)\enspace.$$

Then, with probability 1-δ, the following event holds. ∀ m∈M,

$${} \left\lvert(P_{n}-P)(s_{m_{o}}-s_{m})\right\rvert\leq\frac{8\sqrt{2}}{3}\varepsilon_{m}(\delta)\left(\left.\left\lVert s_{m}-s_{\star}\right\rVert^{2}+\frac{P\Psi_{m}}{n}\right.\right)\qquad \sum_{\lambda\in\Lambda_{m}}\left[\left.(P_{n}-P)\psi_{\lambda}\right.\right]^{2}\leq(1+L_{0}\nu)\frac{P\Psi_{m}}{n}+\frac{L_{o}\left\lVert s\right\rVert}{\nu}r_{m}(\delta)+\frac{L_{o}}{\nu^{3}}r^{2}_{m}(\delta)\enspace.$$

Proof.

Let Zₘ=Σ_λ∈Λₘ[.(Pₙ-P)ψ_λ .]². We proved the following concentration inequality for Zₘ in [23]. Let v²ₘ=supₜ∈B(m) P[.(t-Pt)² .], for some absolute L₀≤16(ln 2)⁻¹+8, we have, for all δ>0, ν>0, with probability larger than 1-δ/2,

$$Z_{m}-\frac{P\Psi_{m}}{n}\leq L_{0}\left(\left.\nu\frac{P\Psi_{m}}{n}+\frac{1}{\nu}\left(\left.\frac{v^{2}_{m}\ln(2/\delta)}{n}+\frac{\left\lVert\Psi_{m}\right\rVert_{\infty}(\ln(2/\delta))^{2}}{\nu^{2}n^{2}}\right.\right)\right.\right)\enspace.$$

We have

$$v^{2}_{m}\leq\sqrt{\left\lVert\Psi_{m}\right\rVert_{\infty}}\sup_{t\in\mathbb{B}(m)}P\left[\left.\left\lvert t\right\rvert\right.\right]\leq\sqrt{\left\lVert\Psi_{m}\right\rVert_{\infty}}\left\lVert s\right\rVert.$$

Hence, if we denote by

$$r_{m}(\delta)=\frac{\sqrt{\left\lVert\Psi_{m}\right\rVert_{\infty}}\ln\left(\left.\frac{2}{\pi(m)\delta}\right.\right)}{n}\enspace,$$

we obtain,

$$\mathbb{P}\left\lbrace \left.\forall m\in\mathcal{M},\quad Z_{m}\gt (1+L_{0}\nu)\frac{P\Psi_{m}}{n}+\frac{L_{o}\left\lVert s\right\rVert}{\nu}r_{m}(\delta)+\frac{L_{o}}{\nu^{3}}r^{2}_{m}(\delta)\right.\right\rbrace \leq\frac{\delta}{2}\enspace.$$

Moreover, Bernstein’s inequality yields, for all m∈M, for all mₒ, and for all δ∈(0,1), with probability larger than 1-δ/2,

$$\left\lvert(P_{n}-P)(s_{m_{o}}-s_{m})\right\rvert\leq\sqrt{\frac{2\mathrm{var}_{P}(s_{m}-s_{m_{o}})\ln(4/\delta)}{n}}+\frac{\left\lVert s_{m}-s_{m_{o}}\right\rVert_{\infty}\ln(4/\delta)}{3n}\enspace.$$

Using Cauchy-Schwarz inequality and assumption (4.1), we deduce that, if mₒ is a minimizer of ‖ s_m-s_‖^2+P_m/n,

$$\mathrm{var}_{P}(s_{m}-s_{m_{o}}) \leq\left\lVert s_{m}-s_{m^{\prime}}\right\rVert_{\infty}P|s_{m}-s_{m_{o}}|\qquad {} \leq\eta_{\infty,2}P(\Psi_{m}+\Psi_{m_{o}})\left\lVert s\right\rVert\left\lVert s_{m}-s_{m_{o}}\right\rVert^{2}\qquad {} \leq 8n\eta_{\infty,2}\left\lVert s\right\rVert\left(\left.\left\lVert s_{m}-s_{\star}\right\rVert^{2}+\frac{P\Psi_{m}}{n}\right.\right)^{2}\enspace.$$

Actually, we have ‖ s_-s_m_o‖^2≤‖ s_-s_m_o‖^2+P_m_o/n≤‖ s_m-s_‖^2+P_m/n, hence, by the triangular inequality,

$$\left\lVert s_{m}-s_{m_{o}}\right\rVert^{2}\leq 2\left\lVert s_{m}-s_{\star}\right\rVert^{2}+2\left\lVert s_{\star}-s_{m_{o}}\right\rVert^{2}\leq 4\left(\left.\left\lVert s_{m}-s_{\star}\right\rVert^{2}+\frac{P\Psi_{m}}{n}\right.\right)\enspace.$$

Moreover, P_m_o≤ n‖ s_-s_m_o‖^2+P_m_o≤ n‖ s_m-s_‖^2+P_m, hence,

$$P(\Psi_{m}+\Psi_{m_{o}})\leq 2n\left(\left.\left\lVert s_{m}-s_{\star}\right\rVert^{2}+\frac{P\Psi_{m}}{n}\right.\right).$$

We also have

‖ s_m-s_m_o‖∞ln(4/(δπ(m)))3n ≤2∞,2P(_m+m_o)‖ s_m-s_m_o‖^2ln(4/(δπ(m)))n ×∞,2P(m+m_o)ln(4/(δπ(m)))18n ≤2√23∞,2ln(.(4)/(δπ(m)).)(.‖ s_m-s‖^2+P_mn.)^3/2 .

Using a union bound, we deduce that, with probability larger than 1-δ/2, ∀ m∈M,

$$\left\lvert(P_{n}-P)(s_{m_{o}}-s_{m})\right\rvert\leq\frac{8\sqrt{2}}{3}\varepsilon_{m}(\delta)\left(\left.\left\lVert s_{m}-s_{\star}\right\rVert^{2}+\frac{P\Psi_{m}}{n}\right.\right)\enspace.$$

Let us then denote by L₁(ε)=3ε⁻¹ L₀+16√(2)/3 and by ∎

D.3 Control of the infimum

Lemma 25.

Let X₁:n be i.i.d random variables and let δ>0 such that ⌈ln(δ⁻²)⌉≤n/2. Let B be a regular partition of {.1,…,n.}, with V=⌈ln(δ⁻²)⌉∨ 8. Let (ŝ_K) be a sequence of estimators such that, for all K, ŝ_K=f(X_B_K). Let α∈(0,1) and let x_α be a real number satisfying the following property.

$$\mathrm{Card}\left\lbrace \left.K=1,\ldots,V,\;\mathbb{P}\left(\left.\ell(\widehat{s}_{K},s_{o})\gt x_{\alpha}\right.\right)\leq e^{-\frac{1}{2\alpha}}\right.\right\rbrace \geq\alpha V.$$

Then we have

$$\mathbb{P}\left(\left.\inf_{K=1,\ldots,V}\ell(\widehat{s}_{K},s_{o})\gt x_{\alpha}\right.\right)\leq\delta.$$

Proof.

By independence of the X_B_K,

$$\mathbb{P}\left(\left.\inf_{K=1,\ldots,V}\ell(\widehat{s}_{K},s_{o})\gt x_{\alpha}\right.\right)=\prod_{K=1}^{V}\mathbb{P}\left(\left.\ell(\widehat{s}_{K},s_{o})\gt x_{\alpha}\right.\right)\leq(e^{-\frac{1}{2\alpha}})^{\alpha V}\leq\delta.$$

∎

An elementary application of the previous result is the following lemma.

Lemma 26.

Let X₁:n be i.i.d random variables and let δ>0 such that ⌈ln(δ⁻²)⌉≤n/2. Let B be a regular partition of {.1,…,n.}, with V=⌈ln(δ⁻²)⌉∨ 8. Let (ŝ_K) be a sequence of estimators such that, for all K, ŝ_K=f(X_B_K). Let α∈(0,1) and let E_α≥0 such that

$$\mathrm{Card}\left\lbrace \left.K=1,\ldots,V,\;\mathbb{E}(\ell(\widehat{s}_{K},s_{o}))\leq E_{\alpha}\right.\right\rbrace \geq\alpha V.$$

Then, we have

$$\mathbb{P}\left(\left.\inf_{K}\ell(\widehat{s}_{K},s_{o})\leq e^{\frac{1}{2\alpha}}E_{\alpha}\right.\right)\geq 1-\delta.$$

Proof.

From Markov inequality,

$$\mathbb{P}\left(\left.\ell(\widehat{s}_{K},s_{o})\leq e^{\frac{1}{2\alpha}}\mathbb{E}\left(\left.\ell(\widehat{s}_{K},s_{o})\right.\right)\right.\right)\leq e^{-\frac{1}{2\alpha}}.$$

Hence, the result follows from Lemma 25 and the assumption on E_α. ∎

Lemma 27.

Let X₁:n be i.i.d random variables with common measure P. Let B be a regular partition of {.1,…,n.} with cardinality larger than ⌈ln(δ⁻²)⌉. Let r=(1-√(1-e⁻²))/2 and assume that there exist a collection of independent events (Ω_K)_[K=1,…,V] such that

$$\forall K=1,\ldots,V,\qquad\mathbb{E}\left(\left.\ell(\widehat{s}_{K},s_{o})\mathbf{1}_{\Omega_{K}}\right.\right)\leq E,\qquad\mathbb{P}\left\lbrace \left.\Omega_{K}^{c}\right.\right\rbrace \leq r\enspace.$$

Then, we have

$$\mathbb{P}\left(\left.\inf_{K=1,\ldots,V}\ell(\widehat{s}_{K},s_{o})\gt 4e^{2}E\right.\right)\leq 2e^{-V}\enspace.$$

Proof.

We introduce the random variables Y_K=1_Ω_Kᶜ. We apply Lemma 23 with x=1/2, and p=r. Denoting by B(V,r) a random variable with binomial distribution of parameters V and r, we obtain

$$\mathbb{P}\left\lbrace \left.\mathrm{Card}\left\lbrace \left.K=1,\ldots,V,\,s.t.\,\Omega_{K}^{c}\;holds\right.\right\rbrace \geq\frac{V}{2}\right.\right\rbrace \leq\mathbb{P}\left\lbrace \left.B(V,r)\geq\frac{V}{2}\right.\right\rbrace \enspace.$$

Let us denote by Ω={.K=1,…,V, s.t. Ω_Kᶜ holds.} and N=CardΩ. By inequality (2.8) in [26]

$$\mathbb{P}\left\lbrace \left.N\geq\frac{V}{2}\right.\right\rbrace \leq e^{-\frac{V}{2}\ln\left(\left.\frac{1}{4r(1-r)}\right.\right)}=e^{-V}\enspace.$$

As a consequence,

$$\mathbb{P}\left\lbrace \left.V-N\lt \frac{V}{2}\right.\right\rbrace \leq e^{-V}\enspace.$$

(25)

Moreover, for all x>4, we have

P ._K=1,…,V(s_K,s_o)> xE∩ N< (V)/(2). =Σ_A .1,…,n. , Card A≥(V)/(2) P ._K=1,…,V(s_K,s_o)> xE∩^c=A. ≤Σ_A .1,…,n. , Card A≥(V)/(2) P ._K∈ A(s_K,s_o)> xE∩^c=A. ≤Σ_A .1,…,n. , Card A≥(V)/(2) P ._K∈ A(s_K,s_o) 1 __K> xE.

$${} \leq\sum_{A\subset\left\lbrace \left.1,\ldots,n\right.\right\rbrace ,\;\mathrm{Card}{A}\geq\frac{V}{2}}\left(\left.\frac{1}{x}\right.\right)^{\mathrm{Card}{A}}\enspace.$$

We conclude the proof with the fact that, if x=4e², (1/x)^CardA≤x⁻V/2≤(2e)⁻V and the fact that there is less than 2^V terms in the sum. ∎

References

• [1]

  P. Alquier. Pac-bayesian bounds for randomized empirical risk minimizers. Mathematical Methods of Statistics, 17(4):279–304, 2008.

• [2]

  P. Alquier and O. Catoni. Risk bounds in linear regression through pac-bayesian truncation. In revision for Ann. Stat., 2010.

• [3]

  Y. Baraud. Estimator selection with respect to hellinger type risks. To appear in Probab. Theory Related Fields, 2011.

• [4]

  Y. Baraud, F. Comte, and G. Viennet. Adaptive estimation in autoregression or β-mixing regression via model selection. Ann. Statist., 29(3):839–875, 2001.

• [5]

  Y. Baraud, C. Giraud, and S. Huet. Estimator selection in the gaussian setting. To appear in ”Ann. Statist.”, 2011.

• [6]

  A. Barron, L. Birgé, and P. Massart. Risk bounds for model selection via penalization. Probab. Theory Related Fields, 113(3):301–413, 1999.

• [7]

  P. J. Bickel, Y. Ritov, and A. B. Tsybakov. Simultaneous analysis of lasso and dantzig selector. Ann. Statist., 37:1705–1732, 2009.

• [8]

  L. Birgé. Model selection via testing: an alternative to (penalized) maximum likelihood estimators. Ann. Inst. H. Poincaré Probab. Statist., 42(3):273–325, 2006.

• [9]

  L. Birgé and P. Massart. From model selection to adaptive estimation. In Festschrift for Lucien Le Cam, pages 55–87. Springer, New York, 1997.

• [10]

  R. C. Bradley. Basic properties of strong mixing conditions. a survey and some open questions. Probab. Survey, 2:107–144, 2005.

• [11]

  F. Bunea, A. B. Tsybakov, F. H. Wegkamp, and A. Barbu. Spades and mixture models. Ann. Statist., 38(4):2525–2558, 2010.

• [12]

  O. Catoni. Statistical learning theory and stochastic optimization, Lectures on Probability Theory and Statistics, École d’Été de Saint Flour XXXI–2001, volume 1851 of Lecture Notes in Math. Springer, 2004.

• [13]

  O. Catoni. Pac-bayesian supervised classification: The thermodynamics of statistical learning. IMS Lecture Notes Monograph Series. Institute of Mathematical Statistics., 56, 2007.

• [14]

  O. Catoni. Challenging the empirical mean and empirical variance: a deviation study. ArXive: 1009.2048v1, 2010.

• [15]

  S. Chen, D. Donoho, and M. Saunders. Atomic decomposition by basis pursuit. SIAM rev., 43:129–159, 2001.

• [16]

  F. Comte and F. Merlevède. Adaptive estimation of the stationary density of discrete and continuous time mixing processes. ESAIM Probab. Statist., 6:211–238 (electronic), 2002. New directions in time series analysis (Luminy, 2001).

• [17]

  D. Donoho, M. Elad, and V. Temlyakov. Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Trans. Inform. Theory, 52:6–18, 2006.

• [18]

  D. L. Donoho, I. M. Johnstone, G. Kerkyacharian, and D. Picard. Density estimation by wavelet thresholding. Ann. Statist., 24(2):508–539, 1996.

• [19]

  E. Greenshtein and Y. Ritov. Persistency in high dimensional linear predictor-selection and the virtue of over-parametrization. Bernoulli, 10:971–988, 2004.

• [20]

  D. Hsu. Robust statistics, 2010. http://www.inherentuncertainty.org/2010/12/robust-statistics.html.

• [21]

  I.A. Ibragimov. Some limit theorems for stationary processes. Theory Probab. Appl., 7:349–382, 1962.

• [22]

  M Lerasle. Optimal model selection for for stationary data under various mixing conditions. To appear in ”Ann. Statist.”, 2011.

• [23]

  M Lerasle. Optimal model selection in density estimation. to appear in ” Ann. Inst. H. Poincaré Probab. Statist.”, 2011.

• [24]

  K. Lounici. Sup-norm convergence rate and sign concentration property of lasso and dantzig estimators. Electron. J. Statist., 2:90–102, 2008.

• [25]

  E. Mammen and A. B. Tsybakov. Smooth discrimination analysis. Ann. Statist., 27:1808–1829, 1999.

• [26]

  P. Massart. Concentration inequalities and model selection, volume 1896 of Lecture Notes in Mathematics. Springer, Berlin, 2007. Lectures from the 33rd Summer School on Probability Theory held in Saint-Flour, July 6–23, 2003, With a foreword by Jean Picard.

• [27]

  P. Massart and E. Nédélec. Risk bounds for statistical learning. Ann. Statist., 34(5):2326–2366, 2006.

• [28]

  N. Meinshausen and P. Bühlmann. High-dimensional graphs and variable selection with the lasso. Ann. Statist., 34:1436–1462, 2006.

• [29]

  A. S. Nemirovsky and D. B. Yudin. Problem Complexity and Method Efficiency in Optimization. 1983.

• [30]

  A. Saumard. Nonasymptotic quasi-optimality of aic and the slope heuristics in maximum likelihood estimation of density using histogram models. hal-00512310, v1, 2011.

• [31]

  R. Tibshirani. Regression shrinkage and selection via the lasso. J. Roy. Statist. Soc. Ser. B, 58:267–288, 1996.

• [32]

  G. Viennet. Inequalities for absolutely regular sequences: application to density estimation. Probab. Theory Related Fields, 107(4):467–492, 1997.

• [33]

  V. A. Volkonskiĭ and Y. A. Rozanov. Some limit theorems for random functions. I. Teor. Veroyatnost. i Primenen, 4:186–207, 1959.

• [34]

  C.H. Zhang and J. Huang. The sparsity and bias of the lasso selection in high dimensional linear regression. Ann. Statist., 36:1567–1594, 2008.

• [35]

  P. Zhao and B. Yu. On model selection consistency of lasso. J. Mach. Learn. Res., 7:2541–2567, 2007.

• [36]

  H. Zou. The adaptive lasso and its oracle properties. J. Amer. Statist. Assoc., 101:1418–1429, 2006.