Mathieu Sart
email: mathieu.sart@univ-st-etienne.fr

ESTIMATING A DENSITY, A HAZARD RATE, AND A TRANSITION INTENSITY VIA THE ρ-ESTIMATION METHOD

Keywords: 2010 Mathematics Subject Classification. 62G07, 62G35, 62N02, 62M05 . ρ-estimator, maximum likelihood, qualitative assumptions, piecewise polynomial estimation

We propose a unified study of three statistical settings by widening the ρ-estimation method developed in [BBS17]. More specifically, we aim at estimating a density, a hazard rate (from censored data), and a transition intensity of a time inhomogeneous Markov process. We show nonasymptotic risk bounds for an Hellinger-type loss when the models consist, for instance, of piecewise polynomial functions, multimodal functions, or functions whose square root is piecewise convexconcave. Under convex-type assumptions on the models, maximum likelihood estimators coincide with ρ-estimators, and satisfy therefore our risk bounds. However, our results also apply to some models where the maximum likelihood method does not work. Subsequently, we present an alternative way, based on estimator selection, to define a piecewise polynomial estimator. We control the risk of the estimator and carry out some numerical simulations to compare our approach with a more classical one based on maximum likelihood only.

1. Introduction 1.1. Statistical settings. In the present paper, we are interested in estimating a unknown function s 0 that appears in one of the following frameworks.

Framework 1 (Density Estimation). Let X be a real-valued random variable with density function s 0 with respect to the Lebesgue measure µ. Our aim is to estimate the density s 0 from the observation of n independent copies X 1 , . . . , X n of X.

Framework 2 (Hazard rate estimation for right censored data). Let (T 1 , C 1 ), . . . , (T n , C n ) be n independent copies of a pair (T, C) of non-negative random variables. The variable C may take the value +∞. We suppose that T is independent of C and that T admits a density f 0 with respect to the Lebesgue measure µ. The target function is the hazard rate s 0 defined for t ≥ 0 by s 0 (t) = f 0 (t) P (T ≥ t) .

The observations are (X i , D i ) 1≤i≤n where X i = min{T i , C i } and

D i = 1 if T i ≤ C i , 0 otherwise.
Framework 3 (Estimation of the transition intensity of a Markov process). We consider a (possibly inhomogeneous) Markov process {X t , t ≥ 0} with the following properties:

• The process is cadlag with finite state space, says {0, 1, . . . , m}.

• The state 0 is absorbing.

• Let, for each interval I ⊂ [0, +∞), A I be the event: "the process jumps at least two times on I". Then, P (A I ) = o(µ(I)) when the length µ(I) of I tends to 0.

• The transition time

T 1,0 = inf {t > 0, X t-= 1, X t = 0} ,
which has values in [0, +∞], is absolutely continuous with respect to the Lebesgue measure µ on R and satisfies therefore for all Borel set A of R,

P (T 1,0 ∈ A) = A f 0 (t) dt,
for a suitable non-negative measurable function f 0 .

We consider an observation interval I obs ⊂ [0, +∞) either of the form I obs = [0, T ] with T ∈ (0, +∞) or I obs = [0, +∞). Our aim is to estimate the transition rate s 0 from state 1 to 0 defined for t > 0 by s 0 (t) = f 0 (t) P (X t-= 1) , from the observation of n independent copies {X (i) t , t ∈ I obs } of {X t , t ∈ I obs }.

In all these frameworks, we will always suppose that n ≥ 3. Although numerous estimation strategies can be considered, we will rather focus in this paper on a particular method presented in [START_REF] Baraud | A new method for estimation and model selection: ρ-estimation[END_REF] and named "ρ-estimation". 1.2. About ρ-estimation in framework 1. We begin by carrying out the method and some known results in density estimation. The key references are [START_REF] Baraud | A new method for estimation and model selection: ρ-estimation[END_REF][START_REF] Baraud | ρ-estimators for shape restricted density estimation[END_REF][START_REF] Baraud | ρ-estimators revisited: general theory and applications[END_REF].

We need a loss in order to measure the quality of an estimator. In ρ-estimation, we deal with the Hellinger distance h. It is defined for two non-negative integrable functions s and s ′ by

h 2 (s, s ′ ) = 1 2 R s(t) -s ′ (t) 2 dt.
The aim is then to define an estimator ŝ that minimizes as far as possible the Hellinger distance h between ŝ and the target s 0 .

The procedure is based on models S, that is a collections of densities, which translate, in mathematical terms, the knowledge we have on s 0 . A model may correspond to different assumptions, such as parametric, regularity, or qualitative ones. This includes in particular models S for which the maximum likelihood method does not work. Several examples are known in the literature. A very simple one is

S = K interval of R {s½ K ,
where s is a non-increasing density on K} , (1) where ½ K denotes the indicator function of K. In this model, the log likelihood can be made arbitrarily large, and the maximum likelihood estimator does not exist. By contrast, we may define, and study, ρ-estimators on S.

The maximal risk R S (n) = sup s 0 ∈S E[h 2 (s 0 , ŝ)] of a ρ-estimator ŝ on S can be controlled according to different notions that aim at measuring the "complexity" of the model S (entropy with bracketing, metric dimension, covering numbers. . . ). Interestingly, R S (n) achieves the optimal minimax rate of convergence in most cases we know (up to possible logarithmic factors). This minimax point of view supposes that s 0 does belong to S. Such an assumption corresponds to a perfect modelling of the statistical problem, which is scarcely the case in practice. It makes therefore more sense to study the risk of the estimator ŝ not only when s 0 lies in S but more generally when s 0 is close to the model S. It turns out that the Hellinger quadratic risk of a ρ-estimator ŝ can be bounded from above by E[h 2 (s 0 , ŝ)] ≤ C inf s∈S h 2 (s 0 , s) + R S (n) whatever the density s 0 , where C is a universal constant (that is a number). This inequality asserts that a small error in the choice of the model S induces a small error in the estimation of s 0 . This is a robustness property. Such a property is not shared in general by the maximum likelihood estimator: it may indeed perform very poorly when s 0 ∈ S but is close to S in terms of Hellinger distance.

The rate given by R S (n) stands for the worst-case rate over all densities s 0 of S. This rate may therefore be very pessimistic in the sense that the estimation may be much faster for some particular densities s 0 ∈ S. The preceding risk bound can be refined to take into account this phenomenon (named superminimaxity in [START_REF] Baraud | ρ-estimators for shape restricted density estimation[END_REF]). For illustration purposes, consider the model S defined by (1) and a ρ-estimator ŝ on S. Then, the rate of convergence of ŝ is at least ℓ/n log 3/2 (n/ℓ) when s 0 is not only non-increasing on an interval but also piecewise constant on ℓ intervals. In this case, the rate of estimation is much faster than the minimax rate.

There are moreover two additional properties of ρ-estimators we now briefly mention. First, ρestimators can be related to maximum likelihood ones. Second, it is possible to deal with penalized ρ-estimators, allowing to cope with model selection.

1.3. Hazard rate and transition intensity estimation. These two frameworks have not yet been studied by means of the ρ-estimation method. They appear in different domains such as reliability or survival analysis. For instance, in medical studies, a variable T may be used to represent the lifetime of a patient, the hazard rate s 0 at time t,

s 0 (t) = f 0 (t) P (T ≥ t) = lim h→0 P (t ≤ T ≤ t + h | T ≥ t) h ,
then measures the tendency of dying just after t, given survival to time t. Since patients may leave the study, the data may be censored. The random variable C then gives the time of leaving and D = ½ T ≤C indicates whether the patient dies (D = 1) or leaves the study (D = 0).

In medical trials, a Markov process {X t , t > 0} may be used to model the evolution of a disease, the state 0 representing (for instance) the death of the patient. The transition rate s 0 at time t,

s 0 (t) = f 0 (t) P (X t-= 1) = lim h→0 P (X t+h = 0 | X t-= 1) h ,
has similar interpretation than the hazard rate: it measures the risk of dying just after t, given the disease is in state 1 at time t-. This framework is actually more general than the one of hazard rate estimation (when the data are uncensored) as s 0 coincides with the hazard rate of T when the Markov process is defined by X t = ½ T ≥t .

In the literature, numerous estimators have been proposed to deal with (at least) one of these two frameworks. We may cite wavelet estimators, Kernel estimators, maximum likelihood estimators, procedures based on L 2 contrasts. . . However, non-asymptotic studies seem to be rather scarce. We refer to [BC05, RB06, BC08, Pla11, AD10] for results concerning procedures based on (penalized) L 2 contrasts. We may cite [START_REF] Van De Geer | Exponential inequalities for martingales, with application to maximum likelihood estimation for counting processes[END_REF][START_REF] Dohler | Adaptive estimation of hazard functions[END_REF] for a study of non-asymptotic properties of maximum likelihood estimators. We refer to [START_REF] Baraud | Estimating the intensity of a random measure by histogram type estimators[END_REF] for results concerning a selection rule based on pairwise comparisons of histogram type estimators. 1.4. A generalized procedure. In this paper, we propose to extend the scope of ρ-estimation to frameworks 2 and 3. Although it has already been studied in the literature, we do not exclude framework 1 for pedagogical and numerical reasons (see Section 1.5 below).

We measure the risks of our estimators by means of a (possibly random) Hellinger-type distance h adapted to the framework. In framework 1, h is the usual Hellinger distance, in framework 2,

h 2 (s, s ′ ) = 1 2
We finally explain how to modify this procedure to select adaptively the number ℓ of pieces from the data. In particular, we show that we can build an estimator that performs well when s 0 belongs, or is close to, the model P r = ∪ ∞ ℓ=1 P ℓ,r . We get a risk bound that almost corresponds to the one we would obtain for the best estimator of the family {ŝ ℓ,r , ℓ ≥ 1} where ŝℓ,r denotes the ρ-estimator on P ℓ,r .

1.6. Organization of the paper. We carry out in Section 2 the general statistical setting that encompasses the three frameworks and explain the estimation procedure. In Section 3, we present the required assumptions on the models as well as our main result on the theoretical performances of ρ-estimators. We also show how to use the loss h E in hazard rate estimation and relate our estimators to those of maximum likelihood. In Section 4, we deal with estimator selection to define a piecewise polynomial estimator in a more practical way. Section 5 is devoted to numerical simulations. The proofs are deferred to Section 6. The probabilistic tool that enables us to control the risk of ρestimators is quite technical and therefore delayed to Appendix A. We give a simple example to illustrate the robustness of ρ-estimators in hazard rate estimation in Appendix B. We discuss in more detail the numerical complexity of our procedures in Appendix C.

2. The ρ-estimation method 2.1. Statistical setting and notations. In this paper, the target s 0 is viewed as the intensity of a random measure ([BB09, [START_REF] Akakpo | Histogram selection for possibly censored data[END_REF][START_REF] Baraud | Estimator selection with respect to Hellinger-type risks[END_REF]). This makes possible a unified treatment of the three frameworks. More precisely, we consider an abstract probability space (Ω, E, P ) on which are defined the random variables appearing in the different frameworks. We associate to each framework, and each borel set A ∈ B(R) two random variables N (A) and M (A). We set in density estimation,

N (A) = 1 n n i=1 ½ A (X i ), M (A) = µ(A),
and in hazard rate estimation,

N (A) = 1 n n i=1 ½ A (X i )½ D i =1 , M (A) = 1 n n i=1 A ½ X i ≥t ½ [0,+∞) (t) dt.
In framework 3, we define the jump time of the i th process

T (i) 1,0 = inf t > 0, X (i) t-= 1, X (i)
t = 0 , and consider

N (A) = 1 n n i=1 ½ T (i) 1,0 ∈A ½ I obs (T (i) 1,0 ), M (A) = 1 n n i=1 A ½ X (i) t-=1 ½ I obs (t) dt.
These formulas define two random measures N and M on (R, B(R)) such that

E[N (A)] = E A s 0 (t) dM (t) for all A ∈ B(R).
In each of the frameworks, the statistical problem may be reduced to that of estimating s 0 from the observation of the random measures N and M .

As explained in the introduction, we will evaluate the quality of the estimators by using an Hellinger-type loss. This Hellinger-type distance h can be written simultaneously in the three statistical settings as

h 2 (s, s ′ ) = 1 2 R s(t) -s ′ (t) 2 dM (t),
for all non-negative integrable functions s and s ′ with respect to the measure M .

We now introduce some notations that will be used all along the paper. We define R + = [0, +∞), and set for x, y ∈ R, x∧ y = min(x, y), x∨ y = max(x, y). The positive part of a real valued functionf is denoted by f + and its negative part by f -. The distance between a point x and a set A in a metric space (E, d) is denoted by d(x, A) = inf y∈A d(x, y). We denote the cardinal of a set A by |A|, and its complement by A c . We set log + x = max{log x, 1} for all x > 0. The notations c, c ′ , C, C ′ , . . . are for the constants. These constants may change from line to line.

2.2. Heuristics. Let S = L 1 + (R, µ) be the cone of non-negative Lebesgue integrable functions in frameworks 1 and 3, and S be the cone of measurable non-negative functions which are locally integrable with respect to µ in framework 2. Let now S be a subset of S. Such set will be called a model. Our aim is to define an estimator ŝ with values in S such that h(s 0 , ŝ) is as small as possible.

Consider two arbitrary functions s, s ′ of S. We begin by defining an approximation

T E (s, s ′ ) of h 2 (s 0 , s) -h 2 (s 0 , s ′ ).
Let ψ be the real-valued function defined for x ≥ 0 by ψ(x) = √ x-1 √ x+1 , and ψ(+∞) = 1. For s, s ′ ∈ S, we set

T E (s, s ′ ) = R ψ s ′ /s s 0 dM - 1 4 R s ′ -s dM.
In this definition, and throughout the paper, we use the conventions 0/0 = 1 and x/0 = +∞ for all x > 0. Some computations show:

Lemma 1. For all s, s ′ ∈ S, 1 3 h 2 (s 0 , s) -3h 2 (s 0 , s ′ ) ≤ T E (s, s ′ ) ≤ 3h 2 (s 0 , s) - 1 3 h 2 (s 0 , s ′ ). (2)
Let S be a model and s ∈ S. We are interested in evaluating h 2 (s 0 , s)h 2 (s 0 , S). The smaller this number, the better s. As T E (s, s ′ ) is roughly of the order of h 2 (s 0 , s)h 2 (s 0 , s ′ ), it is natural to approximate h 2 (s 0 , s)h 2 (s 0 , S) by γ E (s) = sup s ′ ∈S T E (s, s ′ ) and to study the properties of the minimizers of γ E (•).

We deduce from the above lemma that for all s ∈ S,

1 3 h 2 (s 0 , s) -3h 2 (s 0 , S) ≤ γ E (s) ≤ 3h 2 (s 0 , s) - 1 3 h 2 (s 0 , S).
Minimizing γ E (•) over S yields a function s ∈ S (assuming such a function exists) such that,

1 3 h 2 (s 0 , s) -3h 2 (s 0 , S) ≤ γ E (s) ≤ inf s∈S γ E (s) ≤ 3 inf s∈S h 2 (s 0 , s) - 1 3 h 2 (s 0 , S) = 8 3 h 2 (s 0 , S).
Therefore, h 2 (s 0 , s) ≤ 17h 2 (s 0 , S), which means that s is, up to a multiplicative constant, the closest function to s 0 among the ones of S.

The approximation T E (s, s ′ ) of h 2 (s 0 , s)h 2 (s 0 , s ′ ) is unknown in practice as it involves s 0 . This prevents us from minimizing γ E (•). It can however be suitably approximated in practice.

2.3. The procedure. Let T (s, s ′ ) be the approximation of T E (s, s ′ ) defined for s, s ′ ∈ S by

T (s, s ′ ) = R ψ s ′ /s dN - 1 4 R s ′ -s dM.
This translates as

T (s, s ′ ) =                      1 n n i=1 ψ s ′ (X i )/s(X i ) - 1 4 R s ′ (t) -s(t) dt in framework 1, 1 n n i=1 ψ s ′ (X i )/s(X i ) ½ D i =1 - 1 4 ∞ 0 s ′ (t) -s(t) ½ X i ≥t dt in framework 2, 1 n n i=1 ψ s ′ (T (i) 1,0 )/s(T (i) 1,0 ) ½ I obs (T (i) 1,0 ) - 1 4 I obs s ′ (t) -s(t) ½ X (i) t-=1 dt in framework 3.
Let S be a model and for s ∈ S,

γ(s) = sup s ′ ∈S T (s, s ′ ).
Any estimator ŝ ∈ S satisfying

γ(ŝ) ≤ inf s∈S γ(s) + 1/n (3) is called a ρ-estimator.
Remark. Contrary to [BBS17, BB17], we do not assume that S consists of densities in framework 1 for more flexibility in the choice of models. Likewise, the functions of S may not be hazard rates in framework 2, or transition intensities in framework 3.

The procedure may also be used to estimate the restriction of s 0 to an interval K. Indeed, let N ′ be defined by

N ′ (A) = N (A ∩ K) for all A ∈ B(R). Then, E[N ′ (A)] = E[ A s 0 ½ K dM ]
and the target function becomes s 0 ½ K . Let now F be a collection of functions and S be a model of the form S = {f ½ K , f ∈ F}. Since the functions of S vanish outside K, we may replace N in the procedure by N ′ without changing the estimator. Thereby, when all functions of S vanish outside K, the estimator ŝ actually estimates s 0 ½ K .

Risk bounds for ρ-estimators

3.1. Assumptions on models. We recall that the definition of ρ-estimators is based on the minimization of a criterion γ(•) on S. This criterion γ(•) uses the approximation T (s, s ′ ) ≃ T E (s, s ′ ) where s, s ′ ∈ S. Bounding above the risk of the ρ-estimator requires to bound above the error due to the approximation of T E by T . For more informations on this point, we refer to Appendix A. We here only mention that it is possible to control the error under suitable assumptions on the model S we now describe.

We consider a non-decreasing collection (I d ) d≥1 of Borel sets. This class may be a collection of unions of at most d intervals, or more generally, in frameworks 1 and 2, a Vapnik-Chervonenkis class of dimension at most 2d.

Assumption 1. We suppose:

• in frameworks 1 and 2, that the collection I d is Vapnik-Chervonenkis with dimension at most 2d. Besides, the following technical condition holds: there exists an at most countable set I ′ d ⊂ I d such that for all I ∈ I d , there exists a sequence

(I m ) m≥0 ∈ I ′N d satisfying lim m→+∞ ½ Im (t) = ½ I (t)
for every t ∈ R.

• in framework 3, that the sets I ∈ I d are unions of at most d intervals.

We then consider models S satisfying the following condition.

Assumption 2. There exist S ⊂ S and a map d S (•) on S such that: for all s ∈ S, s ∈ S, u > 0, the set {t ∈ R, s(t) > us(t)} belongs to I d S (s) .

This assumption applies for several models of interest, including some which are well suited for estimating functions under smooth or shape constraints. We carry out below three examples.

Let ℓ ≥ 1 and M ℓ be the family that gathers all the collections m of size ℓ of the form

m = {[x 1 , x 2 ], (x 2 , x 3 ], (x 3 , x 4 ], . . . , (x ℓ , x ℓ+1 ]} , (4)
where

x 1 < x 2 < • • • < x ℓ+1 are ℓ + 1 real numbers (with the convention that m = {[x 1 , x 2 ]} when ℓ = 1).
We define for r ≥ 0 the model P ℓ,r by P ℓ,r = K∈m s K ½ K , where m ∈ M ℓ and s K is a polynomial function of degree at most r (5) that is non-negative on K .

Proposition 1. Let for d ≥ 1, I d be the collection of unions of at most d intervals. Then, Assumption 2 is fulfilled with S = S = P ℓ,r , and for all s ∈ S, d S (s) = (ℓ + 2)(r + 2).

We may also consider the model composed of piecewise monotone functions and the one composed of functions whose square roots are piecewise convex-concave. They are defined for k ≥ 1 by

F k = S ∩ K∈m s K ½ K , where m ∈ M k and s K is monotone on K . (6) G k = S ∩ K∈m s 2 K ½ K ,
where m ∈ M k and s K is a non-negative function that is either convex or concave on K} .

We recall here that S is the cone of non-negative integrable functions in frameworks 1 and 3, and the cone of non-negative locally integrable functions in framework 2.

When S = F k , we may define S as the set of functions of F k that are piecewise constant on a finite number of pieces. When S = G k , we may define S as the set of functions of G k whose square root is piecewise affine (on a finite number of pieces). More precisely, the proposition below is given by [BB16]: Proposition 2. Let for d ≥ 1, I d be the collection of unions of at most d intervals. Assumption 2 is fulfilled with:

• S = F k , S = S ∩ (∪ ∞ ℓ=1 P ℓ,0 ) ⊂ S and for all s ∈ S ∩ P ℓ,0 , d S (s) = (3/2)(k + ℓ + 5). • S = G k , S = S ∩ (∪ ∞
ℓ=1 P ℓ,1,sq.root ) ⊂ S, where P ℓ,1,sq.root = {s ∈ S, √ s ∈ P ℓ,1 }, and for all s ∈ S ∩ P ℓ,1,sq.root , d S (s) = 3(k + ℓ + 5).

3.2.

A uniform risk bound.

Theorem 3. Let (I d ) d≥1 be a non-decreasing collection of Borel sets that fulfils Assumption 1. For all ξ > 0, there exists an event of probability lower bounded by 1e -nξ on which: for all model S satisfying Assumption 2 and all ρ-estimator ŝ on S,

h 2 (s 0 , ŝ) ≤ C inf s∈ S h 2 (s 0 , s) + d S (s) n log 2 + n d S (s) + ξ log + (1/ξ) . (7)
In particular,

E h 2 (s 0 , ŝ) ≤ C ′ inf s∈ S E h 2 (s 0 , s) + d S (s) n log 2 + n d S (s) . (8)
In the above inequalities C and C ′ are universal positive constants.

Define R S (s 0 , n) by R S (s 0 , n) = inf s∈ S E h 2 (s 0 , s) + d S (s) n log 2 + n d S (s) . ( 9
)
It follows from (8) that R S (s 0 , n) is -up to a universal multiplicative constant -an upper-bound of the Hellinger quadratic risk E h 2 (s 0 , ŝ) of a ρ-estimator ŝ on S. It then remains to compute R S (s 0 , n) to deduce (an upper bound of) the rate of convergence of the ρ-estimator when s 0 ∈ S. Let us now discuss what is new here.

First, in density estimation, our risk bound slightly improves the one of [START_REF] Baraud | ρ-estimators for shape restricted density estimation[END_REF] in the sense that our variance term involves a smaller exponent on the logarithm. The logarithmic term cannot be avoided in general under our assumptions (see Section 3.3). It is an open question to know whether the power 2 can be replaced by 1. A careful comparison between the two results show that our assumptions on models are more stringent. But, the conclusion is also stronger: the event on which (7) holds true depends on S through (I d ) d≥1 only. It remains the same when the model S changes but not the collection (I d ) d≥1 . This property is the keystone of Section 4.1 (see ( 17)) and at the heart of the developments of subsequent sections.

Second, our study is not restricted to density estimation but encompasses three frameworks. It is noteworthy that the risk bound is of the same form in the three frameworks: only the Hellinger loss depends on the framework. Thereby, we can effortlessly transfer results in density estimation to frameworks 2 and 3. In particular, the properties of "robustness" or "superminimaxity" described in the introduction remain valid in hazard rate and transition intensity estimation. For the sake of illustration, we make the risk bounds explicit when S = P ℓ,r , S = F k and S = G k in Sections 3.3 and 3.4.

3.3.

Risks of ρ-estimators on P ℓ,r . When S = P ℓ,r , Theorem 3 asserts

R P ℓ,r (s 0 , n) = E h 2 (s 0 , P ℓ,r ) + (ℓ + 2)(r + 2) log 2 + (n/((ℓ + 2)(r + 2))) n ≤ E h 2 (s 0 , P ℓ,r ) + 6ℓ(r + 1) log 2 + (n/(ℓ(r + 1))) n . ( 10
)
When s 0 ∈ P ℓ,r , but is close to P ℓ,r , E h 2 (s 0 , P ℓ,r ) is an approximation term that may be interpreted as a robustness term. It is, for instance, small when √ s 0 is smooth with bounded support, see [START_REF] Devore | Degree of adaptive approximation[END_REF].

When s 0 does belong to P ℓ,r , R P ℓ,r (s 0 , n) becomes

R P ℓ,r (s 0 , n) ≤ 6ℓ(r + 1) log 2 + (n/ℓ(r + 1)) n .
This bound is valid in the three frameworks and is almost optimal. Only the power 2 on the logarithm is sub-optimal in general (the optimal risk bound involves a power 1 instead of 2 in framework 1 when r = 0, see [START_REF] Birgé | Minimum contrast estimators on sieves: exponential bounds and rates of convergence[END_REF][START_REF] Baraud | ρ-estimators revisited: general theory and applications[END_REF]).

3.4. Risks of ρ-estimators on F k and G k . Bounding R S (s 0 , n) from above is no more difficult in frameworks 2 and 3 than in density estimation. Thereby, we may easily get upper-bounds in frameworks 2 and 3 from results obtained in the literature in density estimation. More precisely, two bounds on R S (s 0 , n) can be deduced from the results of [START_REF] Baraud | ρ-estimators for shape restricted density estimation[END_REF]: when S = F k and when S = G k . They are given below.

Corollary 1. There exist universal constants C, C ′ and a map V (•) on F k such that for all s 0 ∈ F k ,

R F k (s 0 , n) ≤ C inf ℓ≥1 s∈P ℓ,0 ∩F k E h 2 (s 0 , s) + k + ℓ n log 2 + n k + ℓ (11) ≤ C ′ V (s 0 ) log 2 n n 2/3 + k log 2 n n . (12)
Moreover, there exist universal constants C ′′ , C ′′′ and a map W (•) on G k such that for all

s 0 ∈ G k , R G k (s 0 , n) ≤ C ′′ inf ℓ≥1 s∈P ℓ,1,sq.root ∩G k E h 2 (s 0 , s) + k + ℓ n log 2 + n k + ℓ ≤ C ′′′ W (s 0 ) log 2 n n 4/5 + k log 2 n n . ( 13
)
This corollary gives therefore (an upper-bound of) the rates of convergence of ρ-estimators on F k and G k in the three frameworks, and in particular, in the two new ones. Up to logarithmic factors, we recover the expected rate n -1/3 for a multimodal function s 0 (using the loss h). Moreover, this rate becomes parametric when s 0 ∈ F k is also piecewise constant on ℓ pieces. More generally, the convergence rate we get is faster than n -1/3 if ℓ is allowed to depend on n, but in such a way that ℓn -1/3 tends to 0 (up to logarithmic factors). The number ℓ as well as the pieces on which s 0 is constant are possibly unknown to the statistician. This reasoning applies in a similar way to the collection G k .

Like-minded results have been obtained for least squares estimators in the regression setting. We refer to [Zha02, Cha14, BT15, CGS15, GS15, Bel18, CL19]. In isotonic regression, the risk of the least squares estimator is, in general, bounded from above by a quantity of the order of n -1/3 . This bound becomes of the order of (ℓ/n) log(n/ℓ) when the regression function is piecewise constant on ℓ pieces. Likewise, in convex regression, the result is better when the target is piecewise affine. This is the same phenomenon as described above for our estimators, although our results involve additional logarithmic factors.

In (12) and (13), the terms V (s 0 ), W (s 0 ) measure, in some sense, the "variations" of √ s 0 . To reduce the size of this paper, we propose to make explicit V (•) only.

Let for K ⊂ R,

M E (K) =      µ(K) in framework 1, K P (X ≥ t)½ [0,+∞) (t) dt in framework 2, K P (X t-= 1)½ I obs (t) dt in framework 3. The map V (•) is then defined for s 0 ∈ F k by V (s 0 ) = inf m K∈m   M E (K) sup x∈K s 0 (x) -inf x∈K s 0 (x) 2   1/3
, where the infimum runs over all collections m ∈ M k for which s 0 = K∈m s K ½ K where s K is monotone on K.

It can be bounded from above as follows when k = 2 and s 0 ∈ F 2 :

• in framework 1, V (s 0 ) ≤ 2L 1/3 supp (sup x∈R s 0 (x)) 1/3 , whenever the support of s 0 is of finite length L supp . • in framework 2, V (s 0 ) ≤ 2 (E(X)) 1/3 sup x≥0 s 0 (x) 1/3 , whenever X has finite expectation. • in framework 3, V (s 0 ) ≤ 2 (E(T 1 )) 1/3 sup x∈I obs s 0 (x) 1/3 , whenever T 1 = I obs ½ X t-=1 dt has finite expectation.
Contrary to density estimation, the size L supp of the support of s 0 is not involved in these upperbounds in hazard rate and transition intensity estimation.

3.5. About the risk bounds in hazard rate estimation. The empirical distance h has been scarcely used in hazard rate estimation. The only papers we are aware of that deal with this loss are [START_REF] Van De Geer | Exponential inequalities for martingales, with application to maximum likelihood estimation for counting processes[END_REF][START_REF] Baraud | Estimating the intensity of a random measure by histogram type estimators[END_REF]. But other losses may be considered, and in particular deterministic losses. Since s 0 is not integrable on (0, +∞), it is not possible to use a loss of the form

h 2 unif (s 0 , ŝ) = 1 2 α 0 s 0 (t) -ŝ(t) 2 dt,
when α = +∞. Setting α < +∞ amounts to measuring the quality of the estimation on an interval of finite length only. Moreover, the rate of convergence of h 2 unif (s 0 , ŝ) depends generally on α when α goes to infinity with n.

In the present paper, we dealt with h, but we may also consider

h 2 E (s 0 , ŝ) = 1 2 ∞ 0 s 0 (t) -ŝ(t) 2 P (X ≥ t) dt.
The difference between h E and h lies in the fact that h E involves the (unknown) survival function

G(t) = P (X ≥ t) of X whereas h involves its empirical counterpart G n (t) = n -1 n i=1 ½ X i ≥t .
Note that the quality of the estimation is not measured uniformly on (0, +∞) but according to the difficulty of the problem. In particular, the larger t, the farther ŝ(t) may be from s 0 (t).

Let us mention that we may always relate h unif to h E since

h 2 E (s 0 ½ [0,α] , ŝ½ [0,α] ) ≤ h 2 unif (s 0 , ŝ) ≤ (G(α)) -1 h 2 E (s 0 ½ [0,α] , ŝ½ [0,α] ),
when G(α) > 0. Likewise, we may relate h E to h as shown below.

Proposition 4. Consider framework 2, suppose n ≥ 1043, that G is continuous, E[X] < ∞ and that the density f 0 of T is square-integrable:

∞ 0 f 2 0 dµ < ∞.
Let α be a positive random variable such that

150 log n n ≤ G n (α) ≤ 151 log n n . ( 14
)
There exists a universal constant C such that, for all estimator ŝ ∈ S, the truncated estimator s defined by

s = min{ŝ, n 3 }½ [0, α] satisfies E h 2 E (s 0 , s) ≤ C E h 2 (s 0 , ŝ) + log n n + E[X] + ∞ 0 f 2 0 dµ n 2 .
Thereby, a truncation argument allows to deduce risk bounds for the deterministic loss h E from the ones established with h. For instance, let ŝ be a ρ-estimator satisfying the assumptions of Theorem 3. Then, the preceding proposition asserts:

E h 2 E (s 0 , s) ≤ C inf s∈ S h 2 E (s 0 , s) + d S (s) n log 2 + n d S (s) + E[X] + ∞ 0 f 2 0 dµ n 2 ≤ C R S (s 0 , n) + E[X] + ∞ 0 f 2 0 dµ n 2 .
Up to a remaining term, and a modification of the multiplicative constant, this bound corresponds to the one we would get for E h 2 (s 0 , ŝ) and that is written in (8). In particular, the rates of convergence we got for S = F k and S = G k are valid for s and the Hellinger loss h E .

3.6. Connection with maximum likelihood estimation. The ρ-estimation procedure differs from that of maximum likelihood. Nevertheless, the two approaches are very close in some situations, see [START_REF] Baraud | A new method for estimation and model selection: ρ-estimation[END_REF][START_REF] Baraud | ρ-estimators revisited: general theory and applications[END_REF] for results in density estimation. This point is crucial to reduce the numerical complexity when S = P ℓ,r (see Section 4).

We define

L(s) = R log s dN - R s dM for all s ∈ S, (15)
and call maximum likelihood estimator any estimator maximizing L(•) on S. In the above formula, and throughout the paper, the convention log 0 = -∞ is used.

In framework 1, the term R s dM = R s dµ plays the role of a Lagrange term as s ∈ S may not be a density. In framework 2, L(s) is the usual log likelihood when s is a hazard rate, up to some terms constant in s. The same is true for framework 3, see the literature of counting processes e.g. equation (3.2) of [Ant89] (using that s is an Aalen's multiplicative intensity).

We may write

T (s, s ′ ) = R tanh log s ′ -log s 4 dN - 1 4 R s ′ -s dM for all s, s ′ ∈ S.
As tanh(x) ≃ x when x ≃ 0, we deduce that if s maximizes L(•) and s ′ ≃ s,

T (s, s ′ ) ≃ 1 4 R log s ′ dN - R log s dN - 1 4 R s ′ dM - R s dM ≃ 1 4 L(s ′ ) -L(s) .
Thereby, T (s, s ′ ) is likely non-positive. Under suitable properties of S, this result does not only occur when s ′ ≃ s, but also for all s ′ ∈ S, which implies that γ(s) = 0. In particular, s is a ρ-estimator.

Theorem 5. Suppose that S is a convex subset of S. Let K be a subset of R such that {x ∈ R, s(x) = 0} ⊂ K for all s ∈ S. Define

L K (s) = K log s dN - K s dM for all s ∈ S,
and suppose that sup s∈S L K (s) ∈ {-∞, +∞}.

If there exists an estimator s ∈ S such that L K (s) ≤ L K (s) for all s ∈ S, then γ(s) = 0 and s is a ρ-estimator. Conversely, assume that there exists a ρ-estimator ŝ ∈ S such that γ(ŝ) = 0. Then, for all s ∈ S, L K (s) ≤ L K (ŝ), and ŝ maximizes L K (•) over S.

When K = R, L K (•) = L(•)
, which means that results on maximum likelihood estimators may be derived from that of ρ-estimators and vice versa. A similar result for convex sets of densities was obtained by Su Weijie in the context of framework 1 and was recently included in [START_REF] Baraud | ρ-estimators revisited: general theory and applications[END_REF]. Using sets K not equal to R may be of interest to remove some observations that would make the log likelihood identically equal to -∞. In that case, we rather estimate the restriction of s 0 to K as illustrated below.

We consider the convex model S in framework 1 defined by

S = s½ (0,+∞) , s is a non-increasing function of S on R . (16)
When the random variables X i are positive, which in particular holds true almost surely if s 0 does belong to S, the maximum likelihood estimator exists on S and is known as the Grenander estimator, see [START_REF] Grenander | On the theory of mortality measurement[END_REF]. We deduce from the above theorem with K = R that this estimator is, in this case, a ρ-estimator. When some of the random variables X i are non-positive, L(s) = -∞ for all s ∈ S, and we cannot maximize L(•) over S to design an estimator. However, the ρ-estimation approach works and still coincides with the maximum likelihood one, up to minor modifications. Indeed, in this case, the preceding theorem can be used with K = (0, +∞). Then, L K (s) takes the form

L K (s) = 1 n i∈{1,...,n} X i >0 log s(X i ) - ∞ 0 s(t) dt for all s ∈ S.
Let s be the Grenander estimator based on the random variables X 1 , . . . , X n that are positive. This estimator is a density and maximizes the map

s → 1 n 0 i∈{1,...,n} X i >0 log s(X i )
over the densities s of S, where n 0 is the number of positive random variables among X 1 , . . . , X n . One can verify that the estimator that maximizes L K (•) over S, and which is thus a ρ-estimator on S, is ŝ = (n 0 /n)s. Note that R ŝ dµ = n 0 /n, which means that ŝ is not a density unless all the observations X i are positive. This is due to the fact that ŝ here estimates the restriction of s 0 to (0, +∞) (which cannot be a density when some observations X i are negative).

Let us mention that a maximum likelihood estimator may not be rate optimal. We refer to Theorem 3 of [START_REF] Birgé | Rates of convergence for minimum contrast estimators[END_REF] for an example of convex set of densities where this phenomenon occurs. As S is convex in that example, the maximum likelihood estimator is also a ρ-estimator. This means that there are unfortunately ρ-estimators that do not reach the optimal minimax rate of convergence.

It is sometimes convenient to consider models S of the form S = f 2 , f ∈ F where F consists of non-negative functions. The set F can then be interpreted as a translation of the knowledge one has on √ s 0 . For instance, if F denotes the set of non-negative concave functions on [0, +∞) vanishing on (-∞, 0), the assumption

s 0 ∈ S means that √ s 0 is concave on [0, +∞) with support in [0, +∞).
It turns out that the connection between ρ-and maximum likelihood estimators remains valid when the convexity assumption is put on F instead of S.

Theorem 6. Let F be a convex set of non-negative functions such that

S = f 2 , f ∈ F is included in S. Let K be a subset of R such that {x ∈ R, f (x) = 0} ⊂ K for all f ∈ F. Then, if sup s∈S L K (s) ∈ {-∞,

From theory to practice: estimator selection

It is often difficult in practice to find a global minimum of γ(•) and thus to build ρ-estimators. In particular, we do not know how to construct a ρ-estimator on the model S = P ℓ,r . In this section, our goal is to propose an alternative way, more numerically friendly, to define an estimator with similar statistical properties on this model. We then explain how to make the estimator adaptive with respect to ℓ.

4.1. Maximum likelihood estimation. We start by considering a much simpler model than P ℓ,r . More precisely, we consider a partition m ∈ M ℓ and define the collection P r (m) ⊂ P ℓ,r of piecewise polynomial functions on m:

P r (m) = K∈m s K ½ K , for all K ∈ m,
s K is a polynomial function of degree at most r, non-negative on K} .

As P r (m) is convex, our procedure is essentially reduced to that of maximum likelihood, which is easier to implement in practice. Elementary computations show: Lemma 2. Let r ≥ 0, ℓ ≥ 1, m ∈ M ℓ , and for K ∈ m, P r (K) = {s½ K , s is a polynomial function of degree at most r and non-negative on K} .

Then, sup s∈Pr(K) L K (s) is finite and achieved at a point ŝK .

Moreover, ŝm =

K∈m ŝK is a ρ-estimator on the model

S = P r (m) that vanishes γ(•). If N (∪ K∈m K) = N (R), ŝm maximizes L(•)
and is therefore also a maximum likelihood estimator.

It follows from Theorem 3 that there is an event that does not depend on m, that holds true with probability larger than 1e -nξ , and on which:

h 2 (s 0 , ŝm ) ≤ C h 2 (s 0 , P r (m)) + ℓ(r + 1) n log 2 + n ℓ(r + 1) + ξ log + (1/ξ) . ( 17
)
Our objective in the subsequent sections is to define a good partition, that is a partition m for which the bias term h 2 (s 0 , P r (m)) is small. Remark: the preceding inequality shows that ŝm is robust with respect to model misspecification measured in terms of h. Let us mention that this property is not always true for maximum likelihood estimators, see Section 2.3 of [START_REF] Birgé | Model selection via testing: an alternative to (penalized) maximum likelihood estimators[END_REF] for an example in density estimation. This is not specific to this framework, see Appendix B for an example in hazard rate estimation. 4.2. Estimator selection. Let (m λ ) λ∈Λ be a family of (possibly random) partitions of M ℓ . The preceding section explains how to compute a ρ-estimator ŝm λ on P r (m λ ). We deduce from Proposition 1 that the (random) model S = {ŝ m λ , λ ∈ Λ} fulfils Assumption 2 with S = S, d S (ŝ m λ ) = (ℓ+2)(r +2). Applying our procedure to S leads to an estimator of the form ŝ = ŝm λ that satisfies on an event of probability lower bounded by 1e -nξ ,

h 2 (s 0 , ŝm λ ) ≤ C inf λ∈Λ h 2 (s 0 , ŝm λ ) + (r + 1)ℓ log 2 + (n/(ℓ(r + 1))) n + ξ log + (1/ξ) , ≤ C ′ inf λ∈Λ h 2 (s 0 , P r (m λ )) + (r + 1)ℓ log 2 + (n/(ℓ(r + 1))) n + ξ log + (1/ξ) , (18)
using ( 17). Here, C, C ′ are universal constants.

Instead of dealing with P ℓ,r -which seems to be very tricky in practice -we may restrict our procedure to the set S = {ŝ m λ , λ ∈ Λ}. Minimizing our criterion then requires to compute T (ŝ m λ , ŝm λ ′ ), for every pair (ŝ m λ , ŝm λ ′ ) ∈ S 2 . This is numerically feasible when S is finite and not too large.

As we see in (18), we should take {m λ , λ ∈ Λ} as large as possible to improve on the theoretical performances of the selected estimator. Ideally, {m λ , λ ∈ Λ} = M ℓ to recover the risk bound of a ρ-estimator ŝ on P ℓ,r :

h 2 (s 0 , ŝm λ ) ≤ C ′ h 2 (s 0 , P ℓ,r ) + (r + 1)ℓ log 2 + (n/(ℓ(r + 1))) n + ξ log + (1/ξ) . (19)
There is therefore a trade-off between the theoretical and computational properties of ŝm λ . The larger the collection, the better the theoretical properties, but the longer it takes to compute the estimator.

4.3.

Selecting among a special collection of piecewise polynomial estimators. In this section, we propose to deal with a special but possibly very large collection {ŝ m λ , λ ∈ Λ} of piecewise polynomial ρ-estimators. This collection being very rich, we hope to recover a theoretical risk bound akin to (19). Moreover, we propose a criterion γ 2 (•) that uses the particular structure of this collection to reduce the numerical complexity.

We consider a (possibly random) collection of distinct random variables {Y i , i ∈ Î} where Î is a (possibly random) set such that n = | Î| ≥ 2. Since the random variables (Y i ) i∈ Î are distinct almost surely, we may order them:

Y (1) < Y (2) < • • • < Y (n) . We define the collection M that gathers all the partitions m of [Y (1) , Y (n) ] of the form m = [Y (1) , Y (n 1 ) ], (Y (n 1 ) , Y (n 2 ) ], (Y (n 2 ) , Y (n 3 ) ], . . . , (Y (n k ) , Y (n) ] ,
where k ≥ 0 and 1

< n 1 < n 2 • • • < n k < n with the convention that m = {[Y (1) , Y (n) ]} when k = 0. We set for ℓ ∈ {1, . . . , n -1}, M ℓ = m ∈ M, |m| = ℓ . Note that M ℓ ⊂ M ℓ , but M ℓ = M ℓ .
We now consider a random variable l with values in {1, . . . , n-1}. For each m ∈ M l, we define the piecewise polynomial ρ-estimator ŝm on P r (m) as explained in Lemma 2. This construction implies that there exist l intervals on which ŝm is a polynomial function. Moreover, ŝm may have spikes on {Y (1) , Y (2) , . . . , Y (n) } only. We aim at selecting an estimator among the family {ŝ m , m ∈ M l}.

We define for m ∈ M, K ∈ m and m ′ ∈ M, the partition m ′ ∨ K of K by

m ′ ∨ K = K ′ ∩ K, K ′ ∈ m ′ , K ′ ∩ K = ∅ . (20)
We consider a positive number L and define the criterion γ 2 (•) for m ∈ M l by

γ 2 (ŝ m ) = K∈m sup m ′ ∈ M l T (ŝ m ½ K , ŝm ′ ½ K ) -L|m ′ ∨ K| (r + 1) log 2 + (n/(r + 1)) n . (21)
The selected estimator is then any estimator ŝ m of the collection {ŝ m , m ∈ M l} minimizing γ 2 (•):

γ 2 (ŝ m) = min m∈ M l γ 2 (ŝ m ). ( 22
)
Theorem 7. There exists a universal constant L 0 such that if L ≥ L 0 , any estimator ŝ m minimizing ( 22) satisfies for all ξ > 0, and probability larger than 1e -nξ ,

h 2 (s 0 , ŝ m) ≤ C inf m∈ M l h 2 (s 0 , P r (m)) + L (r + 1) l log 2 + (n/(r + 1)) n + ξ log + (1/ξ) . ( 23
)
In particular,

E h 2 (s 0 , ŝ m) ≤ C ′ E inf m∈ M l h 2 (s 0 , P r (m)) + L (r + 1) l log 2 + (n/(r + 1)) n . ( 24
)
In the above inequalities, C and C ′ are universal constants. Moreover, the event on which (23) holds may be chosen independently of (Y i ) i∈ Î , l, n, r and the value of L (when L ≥ L 0 ). This risk bound is very similar to the one (18) obtained when the first criterion γ(•) is minimized on S = {ŝ m , m ∈ M l} (we only slightly lose on the variance term). The main interest of this procedure compared to the first one lies in its numerical complexity. To avoid a digression, we defer the discussion on numerical aspects to Section 5 and Appendix C.

Let us mention that our procedure is in line with [START_REF] Sart | Estimation of the transition density of a Markov chain[END_REF] where a numerical complexity reduction work was carried out. More precisely, it is explained there how to select a partition m from the collection of dyadic partitions of [START_REF] Devore | Degree of adaptive approximation[END_REF]. This is very effective to estimate a function under smoothness assumptions (that is, under the assumption that the target belongs to a Besov space). Our aim in this paper is different. Instead, we want to design an estimator with similar statistical properties to that of a ρ-estimator on P ℓ,r . This is why we use a much richer collection than in [START_REF] Sart | Estimation of the transition density of a Markov chain[END_REF].

We now consider framework 1. When Y (1) ≤ min 1≤i≤n X i ≤ max 1≤i≤n X i ≤ Y (n) , ŝm maxi- mizes L(•)
and is therefore a maximum likelihood estimator. It is then natural to compare our estimator ŝ m to the one ŝ m that maximizes the log likelihood L(ŝ m ) over m ∈ M l. We refer to Section 5 for numerical simulations when {Y i , i ∈ Î} = {X i , i ∈ {1, . . . , n}} and r = 0. We do not know theoretical results for ŝ m. However, when {Y i , i ∈ Î} is not random, then results concerning ŝ m may be found in the literature. We refer to Theorem 3.2 of [START_REF] Castellan | Modified akaike's criterion for histogram density estimation[END_REF] (when r = 0) and Theorem 2 of [START_REF] Barron | Risk bounds for model selection via penalization[END_REF] (when r ≥ 0) for upper-bounds of the Hellinger risk in density estimation. Note that they put restrictions either on s 0 , or on the minimal length of the intervals K of the partitions m ∈ M l. Besides, contrary to ours, their upper-bounds involve the Kullback Leibler divergence.

The bias term in (23) depends on the collection M l and thus on the choice of {Y i , i ∈ Î}. In general, this bias term may be larger than the one we would obtain for a ρ-estimator on P l,r . As the Y i are allowed to be random, we may choose them according to the data, and in such a way that the bias term becomes comparable to the one we would obtain for the ρ-estimator, at least when r = 0. Suppose that {Y i , i ∈ Î} is rich enough to satisfy

N (A) = N ({Y i , i ∈ Î} ∩ A) for all A ∈ B(R). (25)
For instance, we may define {Y i , i ∈ Î} as follows:

• in framework 1, we may set Î = {1, . . . , n}, and for all i ∈ Î, Y i = X i , • in framework 2, suppose that the random variables X i are distinct almost surely. Then, we may consider a set Î ⊂ {1, . . . , n}, such that | Î| ≥ 2, Î ⊃ {i ∈ {1, . . . , n}, D i = 1} and define for all i ∈ Î, Y i = X i , • in framework 3, we may consider a set Î ⊂ {1, . . . , n}, such that | Î| ≥ 2 and Î ⊃ {i ∈ {1, . . . , n}, T

1,0 ∈ I obs }, and define for all i ∈ Î,

Y i = T (i) 1,0 .
We may show:

Corollary 2. Suppose (25) and that s 0 vanishes outside the interval [0, L supp ]. Let P l,0,[0,Lsupp] be the collection of step functions based on partitions m of [0, L supp ] belonging to M l.

There exists a universal constant L 0 such that if L ≥ L 0 , r = 0, any estimator ŝ m minimizing (22) satisfies for all ξ > 0, and probability larger than 1e -nξ ,

h 2 (s 0 , ŝ m) ≤ C h 2 s 0 , P l,0,[0,Lsupp] + L (r + 1) l log 2 + (n/(r + 1)) n + ξ log + (1/ξ) . ( 26
)
In particular,

E h 2 (s 0 , ŝ m) ≤ C ′ E h 2 s 0 , P l,0,[0,Lsupp] + L (r + 1) l log 2 + (n/(r + 1)) n .
In the above inequalities, C and C ′ are universal constants.

Note that the procedure does not require the knowledge of the support [0, L supp ] of s 0 . Moreover, the only difference between h 2 (s 0 , P l,0,[0,Lsupp] ) and h 2 (s 0 , P l,0 ) lies in the fact that the functions s ∈ P l,0 may be based on partitions of an interval K different from [0, L supp ]. In particular,

h 2 (s 0 , P l+2,0,[0,Lsupp] ) ≤ h 2 (s 0 , P l,0 ) ≤ h 2 (s 0 , P l,0,[0,Lsupp] ).
We recover, up to slight modifications, the risk bound we would obtain for a ρ-estimator on P l,0 .

The estimator ŝ m has however the advantage of being computable in practice when n and l are small enough, see Appendix C. We refer to Section 4.4 below for more general results (in particular to deal with r ≥ 1).

4.4.

Adaptive piecewise polynomial estimation. The preceding section explains how to define a piecewise polynomial estimator on l pieces. We show in this section that the criterion may be modified to choose l from the data, and get an estimator adaptive with respect to l.

We define for ℓ max ∈ {1, . . . , n -1} the collection M ≤ℓmax of partitions m ∈ M whose cardinal is at most ℓ max ,

M ≤ℓmax = m ∈ M, |m| ≤ ℓ max = ℓmax ℓ=1 M ℓ .
We consider a random variable lmax with values in {1, . . . , n -1} and aim at selecting an estimator among {ŝ m , m ∈ M ≤ lmax }.

We consider L > 0 and set for m ∈ M ≤ lmax ,

γ 3 (ŝ m ) = K∈m sup m ′ ∈ M ≤ lmax T (ŝ m ½ K , ŝm ′ ½ K ) -L|m ′ ∨ K| (r + 1) log 2 + (n/(r + 1)) n .
The selected estimator ŝ m is any estimator of the family satisfying

γ 3 (ŝ m) + 2L (r + 1)| m| log 2 + (n/(r + 1)) n (27) = inf m∈ M ≤ lmax γ 3 (ŝ m ) + 2L(r + 1) |m| log 2 + (n/(r + 1)) n .
The numerical complexity of this procedure is similar to that of Section 4.3. Moreover, we prove:

Theorem 8. There exists a universal constant L 0 such that if L ≥ L 0 , any estimator ŝ m satisfying (27) satisfies for all ξ > 0, and probability larger than 1e -nξ ,

h 2 (s 0 , ŝ m) ≤ C inf m∈ M ≤ lmax h 2 (s 0 , P r (m)) + L (r + 1)|m| log 2 + (n/(r + 1)) n + ξ log + (1/ξ) . ( 28
)
In particular,

E h 2 (s 0 , ŝ m) ≤ C ′ E inf m∈ M ≤ lmax h 2 (s 0 , P r (m)) + L (r + 1)|m| log 2 + (n/(r + 1)) n . ( 29
)
In the above inequalities, C and C ′ are universal constants. Moreover, the event on which (28) holds may be chosen independently of (Y i ) i∈ Î , lmax , n, r and the value of L (when L ≥ L 0 ). This risk bound improves when lmax grows. Moreover, (29) implies

E h 2 (s 0 , ŝ m) ≤ C ′ E inf 1≤ l≤ lmax inf m∈ M l h 2 (s 0 , P r (m)) + L (r + 1) l log 2 + (n/(r + 1)) n .
The right-hand side of this inequality corresponds to the bound (24) achieved by the estimator of Section 4.3 when the choice of l is the best possible among {1, . . . , lmax }.

The quality and the construction of the estimator ŝ m still depends on {Y i , i ∈ Î}. However, when lmax = n -1, and when {Y i , i ∈ Î} is rich enough, the infimum in (29) can be taken over the infinite collection M = ℓ≥1 M ℓ (up to a modification of C ′ ), as shown below.

Lemma 3. Suppose that {Y i , i ∈ Î} is chosen in such a way that N satisfies (25). There exists a universal constant C such that for all ξ > 0 and probability larger than 1e -nξ : for all ℓ ≥ 1,

inf m∈ M ≤2ℓ+3 h 2 (s 0 , ŝm ) ≤ C h 2 (s 0 , P ℓ,r ) + ℓ(r + 1) log 2 + (n/(ℓ(r + 1))) n + ξ log + (1/ξ) .
Suppose now that lmax = n -1, that (25) is satisfied, and that L ≥ max{1, L 0 }. We then deduce from M = M ≤ lmax and (29),

E h 2 (s 0 , ŝ m) ≤ C ′ E inf m∈ M h 2 (s 0 , P r (m)) + L |m|(r + 1) log 2 + (n/(r + 1)) n ,
where C ′ is a universal constant. Lemma 3 implies

E h 2 (s 0 , ŝ m) ≤ C ′′ E inf ℓ≥1 h 2 (s 0 , P ℓ,r ) + L ℓ(r + 1) log 2 + (n/(r + 1)) n , ≤ C ′′ inf ℓ≥1 R(ℓ),
where

R(ℓ) = E h 2 (s 0 , P ℓ,r ) + L ℓ(r + 1) log 2 + (n/(r + 1)) n .
This term R(ℓ) can be interpreted as an upper-bound of the risk of a ρ-estimator on P ℓ,r (up to constants), barely worse than the one given by Theorem 3 and that is written in (19).

Numerical simulations

5.1. About L. We propose in this section a simple way to tune the parameter L in the procedure of Section 4.3. In theory, any value of L larger than L 0 is suitable (where L 0 stands for a universal constant). Unfortunately, the value of L 0 is too large to be used in practice, and we do not know the smallest value of L 0 that would make the risk bound valid.

A simple solution to solve the choice of this calibration parameter L is to consider a collection L of such parameters and to select among them. More precisely, we minimize γ 2 (•) for each L ∈ L and denote the resulting estimator by ŝ mL to emphasize that it depends on L. We then pick out an estimator among {ŝ mL , L ∈ L} by the first selection rule, see Section 4.2.

A ρ-estimator on the (random) model {ŝ mL , L ∈ L} is of the form ŝ = ŝ mL and satisfies for all ξ > 0 and probability larger than 1e -nξ ,

h 2 (s 0 , ŝ) ≤ C inf L∈L h 2 (s 0 , ŝ mL ) + (r + 1) l log 2 + (n/(r + 1)) n + ξ log + (1/ξ) ,
where C is a universal constant. If L contains at least one number L larger than L 0 , we derive from (23),

h 2 (s 0 , ŝ) ≤ C ′   inf m∈ M l h 2 (s 0 , P r (m)) + min   1, inf L∈L, L≥L 0 L   l(r + 1) log 2 + (n/(r + 1)) n + ξ log + (1/ξ)   ,
where C ′ is a universal constant.

Thereby, the estimator ŝ no longer depends on the particular choice of L but rather on the collection L. The larger L, the better the risk bound. However, the numerical complexity of the whole procedure increases with the size of L, and the constant C ′ above may be larger than in (23). 5.2. Results. We consider framework 1, r = 0, ℓ ∈ {1, . . . , n}, {Y i , i ∈ Î} = {X 1 , . . . , X n } and the (random) collection M ℓ consisting of partitions of [X (1) , X (n) ] of size ℓ defined in Section 4.3. For each m ∈ M ℓ , we consider the ρ-and maximum likelihood estimator ŝm on P 0 (m) defined by

ŝm = K∈m N (K) µ(K) with N (K) = 1 n n i=1 ½ K (X i ).
We carry out in this section a numerical study to compare two selection rules described in Sections 4.3 and 5.1.

• The first procedure is based on the likelihood. We select the partition m(1,ℓ) ∈ M ℓ by maximizing the map

m → L(ŝ m ) = 1 n n i=1 log ŝm (X i ) over m ∈ M ℓ .
• The second procedure is based on the ρ-estimation method. We consider a set A consisting of 300 equally spaced points over [0, 3], and define

L = a log 2 n , a ∈ A .
For each L ∈ L, we use the procedure of Section 4.3 specified in ( 21) and ( 22) to get a partition mL ∈ M ℓ . We then use the procedure of Section 4.2 to pick out an estimator among {ŝ mL , L ∈ L} as explained in Section 5.1. This leads to a selected partition of the form mL ∈ M ℓ that will be denoted in the sequel by m(2,ℓ) .

We consider four densities s 0 :

Example 1. s 0 is the density of a Normal distribution

s 0 (x) = 1 √ 2π e -x 2 /2 for all x ∈ R.
Example 2. s 0 is the density of a log Normal distribution

s 0 (x) = 1 x √ 2π e -1 2 log 2 x ½ (0,+∞) (x) for all x ∈ R.
Example 3. s 0 is the density of an exponential distribution

s 0 (x) = e -x ½ [0,+∞) (x) for all x ∈ R.
Example 4. s 0 is the density of a mixture of uniform distributions

s 0 (x) = 1 2 × 3½ [0,1/3] (x) + 1 8 × 3½ [1/3,2/3] (x) + 3 8 × 3½ [2/3,1] (x) for all x ∈ R.
We simulate N rep samples (X 1 , . . . , X n ) according to a density s 0 defined above, and compute, in each of these samples the two selected estimators. Let, for k ∈ {1, 2} and i ∈ {1, . . . , N rep }, ŝ m(k,ℓ,i) be the value of the estimator corresponding to the k th procedure and the i th sample. We evaluate the quality of the estimators by

R(k, ℓ) = 1 N rep Nrep i=1 h 2 s 0 , ŝ m(k,ℓ,i) .
We estimate the probability that the two estimators coincide by

P equal (ℓ) = 1 N rep Nrep i=1 ½ m(2,ℓ,i) = m(1,ℓ,i)
Results are summarized in Figures 1 (when n = 50) and 2 (when n = 100).

Numerically, we observe in these examples that the two estimators ŝ m(1,ℓ) and ŝ m(2,ℓ) perform similarly. Their risks are close and the estimators may even coincide. In Example 4, s 0 does belong to P 3,0 and the fractions R(2, ℓ)/ R(1, ℓ) are very close to 1. In the other examples, s 0 is not piecewise constant, and the robustness properties of the second procedure may be useful. The fractions R(2, ℓ)/ R(1, ℓ) suggest indeed that the second procedure improves the risk of the first one by a few percent, at least when the size ℓ of the partitions is well adapted to the underlying density, that is when ℓ corresponds to the smallest values of R(1, ℓ) and R(2, ℓ).

Remark. The fractions R(2, ℓ)/ R(1, ℓ) are computed with all significant digits and are then rounded.

K = t ∈ R, s(t) = 0 or s ′ (t) = 0 .
Then,

1 2 K √ s ′ - √ s √ q ( √ s 0 - √ q) 2 dM = 1 2 K √ s ′ - √ s √ q s 0 dM + 1 2 K √ s ′ - √ s √ q dM - K √ s ′ - √ s √ s 0 dM. Note that h 2 (s 0 , s ′ ) -h 2 (s 0 , s) = 1 2 K (s ′ -s) dM + K √ s 0 √ s - √ s ′ dM.
Therefore,

1 2 K √ s ′ - √ s √ q ( √ s 0 - √ q) 2 dM = 1 2 K √ s ′ - √ s √ q s 0 dM + 1 2 K √ s ′ - √ s √ q dM - 1 2 K (s ′ -s) dM + h 2 (s 0 , s ′ ) -h 2 (s 0 , s) = T E (s, s ′ ) + h 2 (s 0 , s ′ ) -h 2 (s 0 , s). (30) Now, 1 2 K √ s ′ - √ s √ q ( √ s 0 - √ q) 2 dM = K √ s ′ - √ s √ s + √ s ′ √ s 0 - √ s + √ s ′ 2 2 dM ≤ K √ s 0 - √ s + √ s ′ 2 2 dM ≤ 1 4 K √ s 0 - √ s + √ s 0 - √ s ′ 2 dM.
By using the inequality (x + y) 2 ≤ (1 + α)

x 2 + (1 + α -1 )y 2 , 1 2 K √ s ′ - √ s √ q ( √ s 0 - √ q) 2 dM ≤ 1 + α 4 K √ s 0 - √ s 2 dM + 1 + α -1 4 K √ s 0 - √ s ′ 2 dM ≤ 1 + α 2 h 2 (s 0 , s) + 1 + α -1 2 h 2 (s 0 , s ′ ).
We now put this inequality into (30) to get

T E (s, s ′ ) ≤ 3 + α 2 h 2 (s 0 , s) - 1 -α -1 2 h 2 (s 0 , s ′ ).
The right-hand side of (2) follows from this inequality with α = 3. As to the left-hand side, note that we also have (setting α = 3, and exchanging the role of s and s ′ ),

T E (s ′ , s) ≤ 3h 2 (s 0 , s ′ ) - 1 3 h 2 (s 0 , s).
Yet, T E (s, s ′ ) = -T E (s ′ , s) and hence T E (s, s ′ ) ≥ 1 3 h 2 (s 0 , s) -3h 2 (s 0 , s ′ ) as wished. . 6.2. Proof of Proposition 1 for S = P ℓ,r . Let s, s ∈ P ℓ,r . There exist two partitions m 1 , m 2 of R into intervals such that |m 1 | = ℓ + 2 and |m 2 | = ℓ + 2 and such that s (respectively s) is polynomial on each element

K 1 ∈ m 1 (respectively K 2 ∈ m 2 ). Let m = {K 1 ∩ K 2 , (K 1 , K 2 ) ∈ m 1 × m 2 , K 1 ∩ K 2 = ∅} .
Then, m is a partition of R into intervals such that |m| ≤ |m 1 | + |m 2 | ≤ 2ℓ + 4. Moreover, we may write s and s as

s = K∈m s K ½ K and s = K∈m sK ½ K ,
where s K and sK are non-negative polynomial functions on K of degree at most r.

Let P K = s K -us K . Now, {t ∈ R, s(t) > us(t)} = K∈m {t ∈ K, P K (t) > 0} .
Let Z be the set gathering the zeros of P K . If Z = ∅, then P K is either positive, or negative on R and the set {t ∈ K, P K (t) > 0} is either empty or the interval K. If Z = R, then P K = 0 and {t ∈ K, P K (t) > 0} = ∅. Suppose now that Z = ∅ and Z = R. We may write

Z = {b 1 , . . . , b k } with b 1 < b 2 < • • • < b k and k ≤ r.
We set b 0 = -∞ and b k+1 = +∞. For all j ∈ {0, . . . , k}, P K is either positive or negative on (b j , b j+1 ), and its sign changes with j. Therefore, the set {t ∈ K, P K (t) > 0} is a union of at most k/2 + 1 intervals.

Finally, for all K ∈ m, {t ∈ K, P K (t) > 0} is always a union of at most r/2 + 1 intervals, which implies that {t ∈ R, s(t) > us(t)} is a union of at most (r/2 + 1)(2ℓ + 4) intervals.

6.3. Proof of Theorem 3. Let for d ≥ 1, ϑ(d) = d n log 2 + n d . (31)
We need to prove that there exist a universal constant C and an event Ω ξ such that P (Ω ξ ) ≥ 1e -nξ and on which any ρ-estimator ŝ on S satisfies

h 2 (s 0 , ŝ) ≤ C inf s∈ S h 2 (s 0 , s) + ϑ(d S (s)) + ξ log + (1/ξ) . ( 32
)
We introduce the following notations. We define for all odd integer d ≥ 3,

J d = ∞ r=1 A r , (A r ) r≥1 is a non-increasing sequence of I (d-1)/2 , Jd = J d ∪ {R \ A, A ∈ J d } .
Let s, s ′ ∈ S. Suppose that there exists d ≥ 1 such that for all u > 0, the set {t ∈ R, s ′ (t) > us(t)} belongs to I d . Then, d s ′ (s) stands for any number d such that

t ∈ R, s ′ (t) > us(t)
belongs to I d (for all u > 0). If the preceding assumption does not hold, we set d s ′ (s) = +∞. We define for all odd integers d ≥ 3,

G d = ψ(s ′ /s), s, s ′ ∈ S, d s ′ (s) = (d -1)/2 .
We will apply Theorem 11 (in Appendix A) to the class F = G d . We begin with the following elementary claim:

Claim 1. The functions f ∈ G d satisfy |f | ≤ 1. Moreover, the collection A = {{t ∈ R, f + (t) > u} , f ∈ G d , u ∈ (0, 1)} ∪ {{t ∈ R, f -(t) > u} , f ∈ G d , u ∈ (0, 1)} (33) is included in Jd . Proof. Let f ∈ G d written as f = ψ(s ′ /s). Then, {t ∈ R, f + (t) > u} = t ∈ R, ψ + (s ′ (t)/s(t)) > u = t ∈ R, s(t) = 0, ψ + (s ′ (t)/s(t)) > u ∪ t ∈ R, s(t) = 0, s ′ (t) > 0 = t ∈ R, s(t) = 0, s ′ (t) > vs(t) ∪ t ∈ R, s(t) = 0, s ′ (t) > 0 , where v = ψ -1 (u) ∈ (0, +∞). Therefore, {t ∈ R, f + (t) > u} = t ∈ R, s ′ (t) > vs(t) , belongs to I (d-1)/2 ⊂ Jd . Now, note that ψ -(x) = ψ + (1/x). Hence, {t ∈ R, f -(t) > u} = t ∈ R, ψ + (s(t)/s ′ (t)) > u .
By exchanging the role of s and s ′ in the above computations, we derive

{t ∈ R, f -(t) > u} = t ∈ R, s(t) > vs ′ (t) = t ∈ R, s ′ (t) < (1/v)s(t) . Now, for all r ≥ 1, t ∈ R, s ′ (t) > (1 -1/(2r))(1/v)s(t) ∈ I (d-1)/2 . Therefore, t ∈ R, s ′ (t) ≥ (1/v)s(t) = ∞ r=1 t ∈ R, s ′ (t) > (1 -1/(2r))(1/v)s(t) belongs to J d and {t ∈ R, f -(t) > u} = R \ {t ∈ R, s ′ (t) ≥ (1/v)s(t)} belongs to Jd .
Claim 2. The collection Jd is Vapnik-Chervonenkis with dimension at most 2d -1 ≤ 2d. Moreover, in framework 3, each set A ∈ Jd is a union of at most (d + 1)/2 ≤ d intervals.

Proof. Let t 1 , . . . , t 2n ∈ R and a non-increasing sequence (A r ) r≥1 . Then,

∞ r=1 ({t 1 , . . . , t 2n } ∩ A r ) = lim r→+∞ |{t 1 , . . . , t 2n } ∩ A r | .
The non-increasing sequence (|{t 1 , . . . , t 2n } ∩ A r |) r≥1 consists of integers. Therefore, there exists r 0 such that |{t 1 , . . . ,

t 2n } ∩ A r | = |{t 1 , . . . , t 2n } ∩ A r 0 | for all r ≥ r 0 . Hence, ∞ r=1 ({t 1 , . . . , t 2n } ∩ A r ) = {t 1 , . . . , t 2n } ∩ A r 0 . This implies that {{t 1 , . . . , t 2n } ∩ A, A ∈ J d } = {t 1 , . . . , t 2n } ∩ A, A ∈ I (d-1)/2
and S J d (2n) = S I (d-1)/2 (2n). Therefore, J d is Vapnik-Chervonenkis with dimension at most d -1. We deduce that Jd is Vapnik-Chervonenkis with dimension at most 2(d -1) + 1 ≤ 2d.

The two following elementary results show that each set A ∈ Jd is a union of at most (d + 1)/2 intervals in framework 3:

• For all union A of at most (d -1)/2 intervals, R \ A is a union of at most (d + 1)/2 intervals.

• For all non-increasing sequence (A r ) r≥1 consisting of unions of at most (d -1)/2 intervals, ∞ r=1 A r is a union of at most (d -1)/2 intervals.

Claim 3. For all s, s ′ ∈ S, R ψ 2 (s ′ /s) s 0 dM ≤ 4 h 2 (s 0 , s) + h 2 (s 0 , s ′ ) .
Proof of Claim 3. The proof of this lemma follows from some computations as in Section 8.4 of [START_REF] Baraud | Estimator selection with respect to Hellinger-type risks[END_REF] (see also Proposition 3 of [START_REF] Baraud | ρ-estimators revisited: general theory and applications[END_REF]). Let √ q = ( √ s + √ s ′ )/2 and

K = t ∈ R, s(t) = 0 or s ′ (t) = 0 . Then, R ψ 2 s ′ s s 0 dM = K ψ 2 s ′ s s 0 dM = 1 4 K √ s ′ - √ s 2 s 0 q dM = 1 4 K √ s ′ - √ s 2 s 0 q -1 + 1 2 dM ≤ 1 2 K √ s ′ - √ s 2 s 0 q -1 2 dM + 1 2 K √ s ′ - √ s 2 dM ≤ 1 2 K √ s ′ - √ s 2 q ( √ s 0 - √ q) 2 dM + h 2 (s, s ′ ) ≤ 2 K ( √ s 0 - √ q) 2 dM + h 2 (s, s ′ ) ≤ 1 2 K ( √ s 0 - √ s) + ( √ s 0 - √ s ′ ) 2 dM + h 2 (s, s ′ ) ≤ K √ s 0 - √ s 2 dM + K √ s 0 - √ s ′ 2 dM + h 2 (s, s ′ ) ≤ 2h 2 (s 0 , s) + 2h 2 (s 0 , s ′ ) + h 2 (s, s ′ ).
We complete the proof by using h 2 (s, s ′ ) ≤ 2h 2 (s 0 , s) + 2h 2 (s 0 , s ′ ).

The lemma below is at the core of the proof of Theorem 3.

Lemma 4. For all ξ > 0, there exists an event Ω ξ such that P (Ω ξ ) ≥ 1e -nξ and on which: for all ε ∈ (0, 1/12), s, s ′ ∈ S,

T (s, s ′ ) ≤ (3 + 4ε)h 2 (s 0 , s) - 4 -3ε 12 h 2 (s 0 , s ′ ) + c 1 min ϑ(d s ′ (s)), ϑ(d s (s ′ )) + c 2 ξ log + (1/ξ). ( 34
)
In the above inequality, c 1 and c 2 only depend on ε and the convention ϑ(+∞) = +∞ is used.

Proof. Let d ≥ 3 be an odd integer. Claims 1 and 2 show that the assumptions of Theorem 11 in Appendix A are satisfied with F = G d . Therefore, there exists for all ξ > 0 an event Ω ξ (d) such that P [Ω ξ (d)] ≥ 1e -nξ and on which: for all ε > 0, f ∈ G d of the form f = ψ(s ′ /s), with s, s ′ ∈ S,

|Z(f )| ≤ ευ(f ) + c ϑ (2d s ′ (s) + 1) + ξ log + (1/ξ) .
In this inequality, c only depends on ε. Let Ω ξ = d odd d≥3 Ω ξ+(2 log(1+d))/n (d). Then,

P [(Ω ξ ) c ] ≤ d odd d≥3 P Ω ξ+(2 log(1+d))/n (d) c ≤ ∞ d=1 e -nξ (1 + d) 2 ≤ e -nξ .

Moreover, on Ω

ξ : for all s, s ′ ∈ S, f = ψ(s ′ /s) such that d s ′ (s) < ∞, |Z(f )| ≤ ευ(f ) + cϑ (2d s ′ (s) + 1) + c ξ + 2 log(2 + 2d s ′ (s)) n log + 1 ξ + 2 log(2+2d s ′ (s)) n ≤ ευ(f ) + cϑ (2d s ′ (s) + 1) + 2c log(2 + 2d s ′ (s)) n log + n 2 log(2 + 2d s ′ (s)) + cξ log + (1/ξ) ≤ ευ(f ) + c ′ ϑ(d s ′ (s)) + cξ log + (1/ξ),
where c ′ only depends on ε. This last inequality remains true when d s ′ (s) = ∞ using the convention ϑ(+∞) = +∞. Moreover, as |Z(-f

)| = |Z(f )|, υ(-f ) = υ(f ), ψ(s/s ′ ) = -ψ(s ′ /s),
we may exchange the role of s and s ′ in the preceding inequality to get on Ω ξ :

|Z(f )| ≤ ευ(f ) + c ′ min ϑ(d s (s ′ )), ϑ(d s ′ (s)) + cξ log + (1/ξ). (35)
Now, it follows from (2) that for all s, s ′ ∈ S,

T (s, s ′ ) ≤ 3h 2 (s 0 , s) - 1 3 h 2 (s 0 , s ′ ) + Z(ψ(s ′ /s)). (36)
Therefore, we deduce from Claim 3 and from (35) that on Ω ξ : for all s, s ′ ∈ S,

T (s, s ′ ) ≤ (3 + 4ε)h 2 (s 0 , s) - 4 -3ε 12 h 2 (s 0 , s ′ ) + c ′ min ϑ(d s (s ′ )), ϑ(d s ′ (s)) + cξ log + (1/ξ),
which proves (34) with c 1 = c ′ and c 2 = c.

We now finish the proof of Theorem 3. Lemma 4 implies that on Ω ξ : for all s, s ′ ∈ S,

T (s, s ′ ) ≤ (3 + 4ε)h 2 (s 0 , s) - 4 -3ε 12 h 2 (s 0 , s ′ ) + c 1 ϑ(d s ′ (s)) + c 2 ξ log + (1/ξ). (37)
Thus, for all s ∈ S,

γ(s) ≤ (3 + 4ε)h 2 (s 0 , s) - 4 -3ε 12 h 2 (s 0 , S) + c 1 sup s ′ ∈S ϑ(d s ′ (s)) + c 2 ξ log + (1/ξ). ( 38
)
By using T (s, s ′ ) = -T (s ′ , s), we deduce from (37) that for all s, s ′ ∈ S,

4 -3ε 12 h 2 (s 0 , s ′ ) -(3 + 4ε)h 2 (s 0 , s) -c 1 ϑ(d s ′ (s)) -c 2 ξ log + (1/ξ) ≤ T (s ′ , s).
Any ρ-estimator ŝ satisfies on Ω ξ : for all s ∈ S,

4 -3ε 12 h 2 (s 0 , ŝ) -(3 + 4ε)h 2 (s 0 , s ′ ) -c 1 ϑ(d ŝ(s)) -c 2 ξ log + (1/ξ) ≤ T (ŝ, s) (39) ≤ γ(ŝ) ≤ γ(s) + 1/n.
Using now (38) and 1/n ≤ sup s ′ ∈S ϑ(d s ′ (s)), we deduce when ε ∈ (0, 1/12),

h 2 (s 0 , ŝ) ≤ inf s∈S c 1,ε h 2 (s 0 , s) -h 2 (s 0 , S) + c 2,ε sup s ′ ∈S ϑ(d s ′ (s)) + c 2,ε ξ log + (1/ξ) , (40)
with c 1,ε = 24(3 + 4ε)/(4 -3ε), and with c 2,ε depending only on ε.

When s ∈ S and s ′ ∈ S, Assumption 2 says that d s ′ (s) may be defined by d s ′ (s) = d S (s). Therefore, (40) becomes

h 2 (s 0 , ŝ) ≤ inf s∈ S c 1,ε h 2 (s 0 , s) -h 2 (s 0 , S) + c 2,ε ϑ(d S (s)) + c 2,ε ξ log + (1/ξ) ,
and it remains to choose ε arbitrarily in (0, 1/12) to prove the theorem. 6.4. Proof of Proposition 4. We begin by proving the following lemma.

Lemma 5. Consider framework 2, and suppose that G is continuous. Let ξ > 0 and suppose that there exists a positive random variable αξ satisfying

(70 + 16ξ) log n n ≤ G n (α ξ ) ≤ (71 + 16ξ) log n n . (41)
There exists an event which holds true with probability larger than 1n -ξ and on which: for all t ∈ [0, αξ ], G n (t) ≤ 4G(t) and G(t) ≤ (9/4)G n (t). Moreover, for all estimator ŝ ∈ S,

h 2 E (s 0 , ŝ½ [0, αξ ] ) ≤ (9/4)h 2 (s 0 ½ [0, αξ ] , ŝ½ [0, αξ ] ) + (80 + 18ξ) log n n (42) h 2 (s 0 , ŝ½ [0, αξ ] ) ≤ 4h 2 E (s 0 ½ [0, αξ ] , ŝ½ [0, αξ ] ) + (321 + 73ξ) log n n . ( 43
)
Proof of Lemma 5. We need the celebrated Vapnick-Chervonenkis inequalities for relative deviations (Theorem 14 in Section D.3). We apply this result with B = {[t, +∞), t ≥ 0}, S B (2n) = 2n + 1 and x 2 = 4ξ(log n)/n + 4(log 2 + log(16n + 8))/n. There exists therefore an event Ω 1,ξ such that P (Ω 1,ξ ) ≥ 1 -(1/2)n -ξ and on which: for all t ≥ 0,

G n (t) -G(t) ≤ x.
The assumption on αξ ensures that 4x 2 ≤ G n (α ξ ) and hence: for all t ∈ [0, αξ ],

G n (t) -G(t) ≤ (1/2) G n (α ξ ) ≤ (1/2) G n (t).
We deduce: for all t ∈ [0, αξ ], G n (t) ≤ 4G(t) and G(t) ≤ (9/4)G n (t). Now,

h 2 E (s 0 , ŝ½ [0, αξ ] ) ≤ h 2 E (s 0 ½ [0, αξ ] , ŝ½ [0, αξ ] ) + h 2 E (s 0 ½ [ αξ ,+∞) , 0) ≤ (9/4)h 2 (s 0 ½ [0, αξ ] , ŝ½ [0, αξ ] ) + h 2 E (s 0 ½ [ αξ ,+∞) , 0). If G C (resp G C ) denotes the survival function of C (resp T ), G = G C G T and thus h 2 E (s 0 ½ [ αξ ,+∞) , 0) = 1 2 ∞ αξ s 0 G dµ = 1 2 ∞ αξ s 0 G C G T dµ = 1 2 ∞ αξ f 0 G C dµ.
Therefore,

h 2 E (s 0 ½ [ αξ ,+∞) , 0) ≤ 1 2 ∞ αξ f 0 dµ × G C (α ξ ) ≤ 1 2 G T (α ξ )G C (α ξ ) ≤ 1 2 G(α ξ ).
It remains to use G(α ξ ) ≤ (9/4)G n (α ξ ), G n (α ξ ) ≤ (71 + 16ξ) (log n)/n to get (42) on Ω 1,ξ .

As to (43), note that

h 2 (s 0 , ŝ½ [0, αξ ] ) ≤ h 2 (s 0 ½ [0, αξ ] , ŝ½ [0, αξ ] ) + h 2 (s 0 ½ [ αξ ,+∞) , 0) ≤ 4h 2 E (s 0 ½ [0, αξ ] , ŝ½ [0, αξ ] ) + h 2 (s 0 ½ [ αξ ,+∞) , 0). (44)
If (9/2) (71 + 16ξ) (log n)/n ≥ 1, we set α = 0. If not, there exists a number α ≥ 0 such that

G(α) = 9 2 (71 + 16ξ) log n n .
On Ω ξ,1 ,

G(α ξ ) ≤ 9 4 G n (α ξ ) ≤ 9 4 (71 + 16ξ) log n n .
Therefore α ≤ αξ and (44) leads to

h 2 (s 0 , ŝ½ [0, αξ ] ) ≤ 4h 2 E (s 0 ½ [0, αξ ] , ŝ½ [0, αξ ] ) + h 2 (s 0 ½ [α,+∞) , 0). (45)
It follows from Bernstein's deviation inequality, and more precisely from (86), that there exists an event Ω ξ,2 such that

P [Ω ξ,2 ] ≥ 1 -(1/2)n -ξ and on which ∞ α s 0 G n ≤ 2 ∞ α s 0 G dµ + 2 ξ log n + log 2 n . Since ∞ α s 0 G dµ ≤ G(α) (see the preceding computations), ∞ α s 0 G n ≤ 2G(α) + 2 ξ log n + log 2 n .
We deduce,

h 2 (s 0 ½ [α,+∞) , 0) ≤ G(α) + ξ log n + log 2 n .
By using (45), we get on Ω ξ,1 ∩ Ω ξ,2 ,

h 2 (s 0 , ŝ½ [0, αξ ] ) ≤ 4h 2 E (s 0 ½ [0, αξ ] , ŝ½ [0, αξ ] ) + G(α) + ξ log n + log 2 n .
No matter if (9/2) (71 + 16ξ) (log n)/n is smaller or larger than 1,

G(α) ≤ 9 2 (71 + 16ξ) log n n ,
which shows (43).

Lemma 6. Consider framework 2, and suppose that G is continuous. Let ξ > 0 and suppose that there exists a positive random variable αξ satisfying (41). There exists an event which holds true with probability larger than 1n -ξ and on which: for all κ n > 0, all estimator ŝ ∈ S, and s = min{ŝ, κ n }½ [0, αξ ] ,

h 2 E (s 0 , s) ≤ (9/2)h 2 (s 0 , ŝ) + 9P f 0 (T ) > 70κ n log n n + (803 + 183ξ) log n n . ( 46
)
Proof of Lemma 6. We derive from (42) that with probability larger than 1n -ξ ,

h 2 E (s 0 , s) ≤ (9/4)h 2 (s 0 ½ [0, αξ ] , s) + (80 + 18ξ) log n n . Now, h 2 (s 0 ½ [0, αξ ] , s) = h 2 (s 0 ½ [0, αξ ] ½ ŝ≤κn , ŝ½ [0, αξ ] ½ ŝ≤κn ) + h 2 (s 0 ½ [0, αξ ] ½ ŝ>κn , κ n ½ [0, αξ ] ½ ŝ>κn ) ≤ h 2 (s 0 , ŝ) + h 2 (s 0 ½ [0, αξ ] ½ ŝ>κn , κ n ½ [0, αξ ] ½ ŝ>κn ).
We need to bound above the second term of this inequality. We have,

h 2 (s 0 ½ [0, αξ ] ½ ŝ>κn , κ n ½ [0, αξ ] ½ ŝ>κn ) ≤ h 2 (s 0 ½ [0, αξ ] ½ ŝ>κn,s 0 ≤κn , κ n ½ [0, αξ ] ½ ŝ>κn,s 0 ≤κn ) + h 2 (s 0 ½ [0, αξ ] ½ ŝ>κn,s 0 >κn , κ n ½ [0, αξ ] ½ ŝ>κn,s 0 >κn ).
Yet,

h 2 (s 0 ½ [0, αξ ] ½ ŝ>κn,s 0 ≤κn , κ n ½ [0, αξ ] ½ ŝ>κn,s 0 ≤κn ) ≤ h 2 (s 0 , ŝ), h 2 (s 0 ½ [0, αξ ] ½ ŝ>κn,s 0 >κn , κ n ½ [0, αξ ] ½ ŝ>κn,s 0 >κn ) ≤ h 2 (s 0 ½ [0, αξ ] ½ s 0 >κn , κ n ½ [0, αξ ] ½ s 0 >κn ).
By putting all these inequalities together,

h 2 E (s 0 , s) ≤ (9/2)h 2 (s 0 , ŝ) + (9/4)h 2 (s 0 ½ [0, αξ ] ½ s 0 >κn , κ n ½ [0, αξ ] ½ s 0 >κn ) + (80 + 18ξ) log n n . (47)
We now derive from (43),

h 2 (s 0 ½ [0, αξ ] ½ s 0 >κn , κ n ½ [0, αξ ] ½ s 0 >κn ) ≤ 4h 2 E (s 0 ½ [0, αξ ] ½ s 0 >κn , κ n ½ [0, αξ ] ½ s 0 >κn ) + (321 + 73ξ) log n n ≤ 2 αξ 0 (s 0 + κ n ) ½ s 0 >κn G dµ + (321 + 73ξ) log n n ≤ 4 αξ 0 s 0 ½ s 0 >κn G dµ + (321 + 73ξ) log n n ≤ 4 αξ 0 f 0 ½ s 0 >κn dµ + (321 + 73ξ) log n n .
As G is a non-increasing function, we deduce that for all t ∈ [0, αξ ],

G(t) ≥ G(α ξ ) ≥ (1/4)G n (α ξ ) ≥ (70 + 16ξ) log n n ≥ 70 log n n .
Moreover, s 0 (t) > κ n implies when t ∈ [0, αξ ],

f 0 (t) > κ n G(t) > 70κ n log n n .
Therefore, αξ 0 f 0 ½ s 0 >κn dµ ≤ P f 0 (T ) > 70κ n log n n .

We are now in position to state:

Proposition 9. Consider framework 2, and suppose that G is continuous. Let ξ > 0 and suppose that there exists a positive random variable αξ satisfying (41). Then, for all estimator ŝ ∈ S, and s = min{ŝ, κ n }½ [0, αξ ] ,

E h 2 E (s 0 , s) ≤ (9/2)E h 2 (s 0 , ŝ) + (803 + 183ξ) log n n + 9P f 0 (T ) > 70κ n log n n + 1 + κ n E[X] 2n ξ .
Proof of Proposition 9. Let A ξ be the event given by Lemma 6. Then

P (A ξ ) ≥ 1 -n -ξ . Moreover, E h 2 E (s 0 , s) ≤ E h 2 E (s 0 , s)½ A ξ + E h 2 E (s 0 , s)½ A c ξ . We have, h 2 E (s 0 , s) ≤ 1 2 ∞ 0 (s 0 + s) G dµ ≤ 1 2 1 + ∞ 0 κ n G dµ ≤ 1 + κ n E[X] 2 ,
and hence,

E h 2 E (s 0 , s) ≤ E h 2 E (s 0 , s)½ A ξ + 1 + κ n E[X] 2n ξ .
It remains to use (46) to finish the proof.

We may use this result with ξ = 5, κ n = n 3 and apply Markov's inequality

P f 0 (T ) > 70κ n log n n ≤ n 70κ n log n ∞ 0 f 2 0 dµ
to get Proposition 4. Note that there exists a random variable α satisfying (14) if 150(log n)/n < 1 that is n ≥ 1043.

6.5. Proof of Theorem 5. In each framework, the measure N can be put in the form

N (A) = n -1 i∈ Î ½ A (Y i )
where Î ⊂ {1, . . . , n}, and where the Y i are suitable real-valued random variables.

For instance, in framework 1, Î = {1, . . . , n}, Y i = X i , in framework 2, Î = {i ∈ {1, . . . , n}, D i = 1}, Y i = X i , and in framework 3, Î = {i ∈ {1, . . . , n}, T

(i) 1,0 ∈ I obs }, Y i = T (i) 1,0 . Set Ĵ = {i ∈ Î, Y i ∈ K}.
Then, for s, s ′ ∈ S, T (s, s ′ ) and L K (s) take the form

T (s, s ′ ) = 1 n j∈ Ĵ ψ s ′ (Y j ) s(Y j ) - 1 4 K s ′ -s dM L K (s) = 1 n j∈ Ĵ log s(Y j ) - K s dM.
The proof is straightforward if Ĵ = ∅ since then 4T (s, s ′ ) = L K (s ′ )-L K (s) and 4γ(s) = sup s ′ ∈S L K (s ′ )-L K (s). We suppose from now on that Ĵ = ∅.

Claim 4. Let S ′ = {s ∈ S, L K (s) = -∞} and s ∈ S ′ . Then, sup s ′ ∈S ′ T (s, s ′ ) = 0 if and only if

sup s ′ ∈S ′ L K (s ′ ) -L K (s) = 0. Proof. Suppose that sup s ′ ∈S ′ L K (s ′ ) -L K (s) = 0. Let S ′ 1 = {s ∈ S ′ , s = s ′ , N a.s} and S ′ 2 = S ′ \ S ′ 1 . When s ∈ S ′ 1 , T (s, s ′ ) = - 1 4 K s ′ -s dM = 1 4 L K (s ′ ) -L K (s) . Therefore, T (s, s ′ ) ≤ 0. Let now s ∈ S ′ 2 , u ∈ [0, 1] and ζ = s ′ -s. Note that s + uζ = (1 -u)s + us ′ ∈ S ′ and thus L K (s + uζ) -L K (s) ≤ 0. We introduce the real-valued map ℘ 1 for u ∈ [0, 1] defined by ℘ 1 (u) = L K (s + uζ) -L K (s) = 1 n j∈ Ĵ log s(Y j ) + uζ(Y j ) s(Y j ) -u K ζ dM.
We now define ℘ 2 for u ∈ [0, 1] by

℘ 2 (u) = 4 T (s, s + uζ) = 4 n j∈ Ĵ ψ s(Y j ) + uζ(Y j ) s(Y j ) -u K ζ dM.
Some computations show that ℘ 1 and ℘ 2 are twice differentiable on [0, 1] and

℘ 1 (0) = ℘ 2 (0) = 0 ℘ ′ 1 (0) = ℘ ′ 2 (0) = 1 n j∈ Ĵ ζ(Y j ) s(Y j ) - K ζ dM ℘ ′′ 1 (0) = ℘ ′′ 2 (0) = - 1 n j∈ Ĵ ζ(Y j ) s(Y j ) 2 . Therefore, ℘ ′′ 1 (0) and ℘ ′′ 2 (0) are always negative. Since ℘ 1 (u) is non-positive for all u ∈ [0, 1], ℘ ′ 1 (0) ≤ 0. The above computations show the existence of u 1 ∈ (0, 1] such that ℘ 2 (u) ≤ 0 for all u ∈ [0, u 1 ]. Now, ℘ 2 is concave, and hence non-positive on [0, 1]. In particular, ℘ 2 (1) = T (s, s ′ ) ≤ 0. Likewise, sup s ′ ∈S ′ T (s, s ′ ) = 0 implies sup s ′ ∈S ′ L K (s ′ ) -L K (s) = 0.
Let s ∈ S such that L K (s) ≥ L K (s) for all s ∈ S and L K (s) = -∞. The above claim then shows that T (s, s) ≤ 0 for all s ∈ S such that L K (s) = -∞. Choose now s ∈ S such that L K (s) = -∞. Define for u ∈ [0, 1], s u = (1u)s + us ∈ S and note that s 1 = s. If u ∈ [0, 1), L K (s u ) = -∞ and thus T (s, s u ) ≤ 0. The continuity of the map u ∈ [0, 1] → T (s, s u ) ensures that T (s, s) ≤ 0. Finally, γ(s) = 0.

Conversely, let ŝ be a ρ-estimator satisfying γ(ŝ) = 0. We begin by proving that

L K (ŝ) = -∞. Consider s ∈ S such that L K (s) = -∞ and define for u ∈ [0, 1], s u = (1 -u)ŝ + us ∈ S, ℘ 3 (u) = T (ŝ, s u ) = 1 n j∈ Ĵ ψ (1 -u)ŝ(Y j ) + us(Y j ) ŝ(Y j ) - 1 4 K (s u -ŝ) dM. When j ∈ Ĵ, s(Y j ) > 0. Therefore, if Ĵ′ = j ∈ Ĵ, ŝ(Y j ) = 0 and u ∈ (0, 1], ℘ 3 (u) = | Ĵ′ | n + 1 n j∈ Ĵ\ Ĵ′ ψ (1 -u)ŝ(Y j ) + us(Y j ) ŝ(Y j ) - 1 4 K (s u -ŝ) dM.
Therefore, if Ĵ′ = ∅ choosing u > 0 small enough leads to ℘ 3 (u) ≥ | Ĵ′ |/(2n) > 0, which is impossible as γ(ŝ) = 0. Therefore, Ĵ′ = ∅ and L K (ŝ) = -∞. The claim then asserts that for all s ∈ S such that

L K (s) = -∞, L K (s) ≤ L K (ŝ)
. This inequality being true if L K (s) = -∞, the proof is complete.

6.6. Sketch of the proof of Theorem 6. We define the elements Y i , Î, Ĵ as in the proof of Theorem 5. Let for x ∈ [0, +∞], ψ 2 (x) = ψ(x 2 ) and for f, f ′ ∈ F,

T 2 (f, f ′ ) = T (f 2 , f ′2 ) = 1 n j∈ Ĵ ψ 2 f ′ (Y j ) f (Y j ) - 1 4 K f ′2 -f 2 dM, L K,2 (f ) = L K (f 2 ) = 2 n j∈ Ĵ log f (Y j ) - K f 2 dM.
The proof is very similar to the one of Theorem 5. The main change lies in the replacement of the symbols S, T , L K by F, T 2 , L K,2 . We will only give some insight into why Claim 4 remains valid under these modifications.

As in the proof of Theorem 5, we may suppose that Ĵ = ∅.

Claim 5. Let F ′ = {f ∈ F, L K,2 (f ) = -∞} and f ∈ F ′ . Then, sup f ′ ∈F ′ T 2 (f, f ′ ) = 0 if and only if sup f ′ ∈F ′ L K,2 (f ′ ) -L K,2 (f ) = 0.
Sketch of the proof. We prove that sup

f ′ ∈F ′ L K,2 (f ′ ) -L K,2 (f ) = 0 implies sup f ′ ∈F ′ T 2 (f, f ′ ) = 0.
The proof of the converse is similar.

Let F ′ 1 = {f ′ ∈ F ′ , f ′ = f , N a.s} and F ′ 2 = F ′ \ F ′ 1 . As in the proof of Claim 4, T 2 (f, f ′ ) = (L K,2 (f ′ ) -L K,2 (f ))/4 when f ′ ∈ F ′ 1 and is thus non-positive. Let now f ′ ∈ F ′ 2 , u ∈ [0, 1] and ζ = f ′ -f . Note that f + uζ = (1 -u)f + uf ′ ∈ F ′ and thus L K,2 (f + uζ) -L K,2 (f ) ≤ 0.
We introduce the real-valued map ℘ 1 for u ∈ [0, 1] defined by

℘ 1 (u) = L K,2 (f + uζ) -L K,2 (f ) = 2 n j∈ Ĵ log f (Y j ) + uζ(Y j ) f (Y j ) -u 2 K ζ 2 dM -2u K ζf dM.
We now define ℘ 2 for u ∈ [0, 1] by

℘ 2 (u) = 4 T 2 (f, f + uζ) = 4 n j∈ Ĵ ψ 2 f (Y j ) + uζ(Y j ) f (Y j ) -u 2 K ζ 2 dM -2u K ζf dM. Some computations show that ℘ 1 (0) = ℘ 2 (0) = 0, ℘ ′ 1 (0) = ℘ ′ 2 (0), ℘ ′′ 1 (0) = ℘ ′′ 2 (0) < 0. As ℘ 1 (u) is non-positive for all u ∈ [0, 1], ℘ ′ 1 (0) ≤ 0. There exists therefore u 1 ∈ (0, 1] such that ℘ 2 (u) ≤ 0 for all u ∈ [0, u 1 ]. Since ψ 2 is concave, ℘ 2 is also concave, and ℘ 2 is non-positive on [0, 1]. In particular, ℘ 2 (1) = T 2 (f, f ′ ) ≤ 0.
6.7. Proof of Lemma 2. As in the proof of Theorem 5, the measure N can be put in the form

N (A) = n -1 i∈ Î ½ A (Y i )
where Î ⊂ {1, . . . , n}, and where the Y i are suitable real-valued random variables.

Note that if

K ∩ {Y (1) , . . . , Y (n) } = ∅ then, L K (s) = - K s(t) dM (t),
and the supremum sup s∈Pr(K) L K (s) is achieved at ŝK = 0 and equals 0. We now suppose that K ∩ {Y (1) , . . . , Y (n) } = ∅.

Let G n be the Radon-Nikodym derivative of M with respect to the Lebesgue measure µ. Then,

G n = 1 in framework 1, G n (t) = n -1 n i=1 ½ X i ≥t ½ [0,+∞) (t) in framework 2 and G n (t) = n -1 n i=1 ½ X (i) t-=1 ½ I obs (t)
in framework 3. Let k be the largest integer of {1, . . . , n} such that Y (k) belongs to K and

K ′ = K ∩ (-∞, Y (k) ]. There exists some α > 0 such that (Y (k) -α, Y (k) ) ⊂ K ′ . Moreover, we can choose α small enough to get G n (t) ≥ 1/n for all t ∈ (Y (k) -α, Y (k) ).
Let now s ∈ P r (K). Then, L K (s) takes the form

L K (s) = 1 n i∈ Î (log s(Y i )) ½ K (Y i ) - K s(t)G n (t) dt,
and is bounded from above by

L K (s) ≤ log + sup t∈K ′ s(t) - 1 n Y (k) Y (k) -α s(t) dt.
We endow the linear space consisting of polynomial functions of degree at most r with the two following norms:

s 1 = Y (k) Y (k) -α |s(t)| dt, s ∞ = sup t∈K ′ |s(t)| .
This linear space being of finite dimension, there exists C such that s ∞ ≤ C s 1 for all s ∈ P r (K). Now,

L K (s) ≤ log + (C s 1 ) - s 1 n .
The continuous map L K (•) tends therefore to -∞ when s 1 → +∞. As there exists at least a function s ∈ P r (K) such that L K (s) = -∞, ŝK does exist.

For the second part of the lemma, we use Theorem 5 to deduce that T (ŝ K , s K ) ≤ 0 for all

s K ∈ P r (K). If s ∈ P r (m) is of the form s = K∈m s K , T (ŝ m , s) = K∈m T (ŝ K , s K ) ≤ 0.
Thus, γ(ŝ m ) = 0 and ŝm is a ρ-estimator on P r (m).

Finally, ŝm maximizes

L ∪ K∈m (s) = K∈m log s dN - K∈m s dM over s ∈ P r (m). As s vanishes outside ∪ K∈m , L ∪ K∈m (s) = L(s) if N (∪ K∈m ) = N (R).
6.8. Proofs of Theorems 7 and 8. It is convenient for the demonstration to encompass the two procedures into a more general selection rule we now describe. Theorems 7 and 8 follow from Theorem 10 below. Their proofs are given in Sections 6.8.2 and 6.8.3.

We consider an arbitrary (possibly random) set Λ. For each λ ∈ Λ, we consider an estimator ŝλ with values in S. Our aim is to select an estimator among the collection {ŝ λ , λ ∈ Λ}.

We consider for each λ ∈ Λ a (possibly random) model Ŝλ ⊂ S. We associate to each λ ∈ Λ, s ∈ Ŝλ , two penalty terms pen 1,λ (s) and pen 2 (λ). We finally define the criterion γ 4 by

γ 4 (ŝ λ ) = sup s∈ Ŝλ T (ŝ λ , s) -pen 1,λ (s) .
The selected estimator ŝλ is then any estimator among {ŝ λ , λ ∈ Λ} satisfying

γ 4 (ŝ λ) + 2pen 2 ( λ) ≤ inf λ∈ Λ {γ 4 (ŝ λ ) + 2pen 2 (λ)} + 1/n.
The risk of this estimator is bounded from above as follows.

Theorem 10. Let (I d ) d≥1 be a non-decreasing collection of Borel sets that fulfils Assumption 1, and d s ′ (s) be the notation introduced in Section 6.3. Let for ξ > 0, Ω ξ be the event given by Lemma 4. It satisfies P (Ω ξ ) ≥ 1e -nξ . We suppose that there exist two real valued maps, ∆(•) ≥ 0 on Λ, and d(•) ≥ 1 on S such that

d ŝλ (s) ≤ d(s) + ∆(λ) for all λ ∈ Λ, s ∈ Ŝλ . ( 48
)
We suppose that there exist a (possibly random) model Ŝ ⊂ λ∈ Λ Ŝλ and a map pen 1 (•) on Ŝ such that pen 1,λ (s) ≤ pen 1 (s) + pen 2 (λ) for all s ∈ Ŝ, λ ∈ Λ. (49)

There exists a universal constant L 1 such that if for all λ ∈ Λ, s ∈ Ŝλ ,

pen 1,λ (s) ≥ L 1 d(s) n log 2 + n d(s) (50) pen 2 (λ) ≥ L 1 ∆(λ) n log 2 + n ∆(λ) ,
and if for all s ∈ Ŝ,

pen 1 (s) ≥ L 1 d(s) n log 2 + n d(s) ,
then, on Ω ξ :

h 2 (s 0 , ŝλ ) ≤ c inf λ∈ Λ h 2 (s 0 , ŝλ ) + pen 2 (λ) + inf s∈ Ŝ h 2 (s 0 , s) + pen 1 (s) + ξ log + (1/ξ) .
In the above inequality, c is a universal constant and the convention 0 × log 2 + (n/0) = 0 is used when ∆(λ) = 0. 6.8.1. Proof of Theorem 10. Let ε ∈ (0, 1/12). Lemma 4 asserts the following on Ω ξ : for all s, s ′ ∈ S

T (s, s ′ ) ≤ (3 + 4ε)h 2 (s 0 , s) - 4 -3ε 12 h 2 (s 0 , s ′ ) + c 1 min ϑ(d s ′ (s)), ϑ(d s (s ′ )) + c 2 ξ log + (1/ξ) (51)
where c 1 , c 2 only depend on ε and where ϑ(•) is given by (31).

Let λ ∈ Λ and s ∈ Ŝλ . Then,

T (ŝ λ , s) ≤ (3 + 4ε)h 2 (s 0 , ŝλ ) - 4 -3ε 12 h 2 (s 0 , s) + c 1 ϑ (d ŝλ (s)) + c 2 ξ log + (1/ξ).
Note that ϑ(d 1 ) ≤ 1.48ϑ(d 2 ) for all d 1 ≤ d 2 . Therefore,

T (ŝ λ , s) ≤ (3 + 4ε)h 2 (s 0 , ŝλ ) + 1.48c 1 ϑ(d(s) + ∆(λ)) + c 2 ξ log + (1/ξ) ≤ (3 + 4ε)h 2 (s 0 , ŝλ ) + 1.48c 1 ϑ(d(s)) + 1.48c 1 ϑ(∆(λ)) + c 2 ξ log + (1/ξ). If L 1 is large enough, T (ŝ λ , s) ≤ (3 + 4ε)h 2 (s 0 , ŝλ ) + pen 1,λ (s) + pen 2 (λ) + c 2 ξ log + (1/ξ),
and hence

γ 4 (ŝ λ ) ≤ (3 + 4ε)h 2 (s 0 , ŝλ ) + pen 2 (λ) + c 2 ξ log + (1/ξ). ( 52
)
We now derive from (51) that for all s ∈ Ŝλ ,

T (s, ŝλ ) ≤ (3 + 4ε)h 2 (s 0 , s) - 4 -3ε 12 h 2 (s 0 , ŝλ ) + c 1 ϑ(d ŝλ (s)) + c 2 ξ log + (1/ξ).
Using moreover that T (ŝ λ, s) = -T (s, ŝλ ) we deduce,

4 -3ε 12 h 2 (s 0 , ŝλ ) ≤ T (ŝ λ, s) + (3 + 4ε)h 2 (s 0 , s) + c 1 ϑ(d ŝλ (s)) + c 2 ξ log + (1/ξ) ≤ T (ŝ λ, s) + (3 + 4ε)h 2 (s 0 , s) + 1.48c 1 ϑ(d(s) + ∆( λ)) + c 2 ξ log + (1/ξ) ≤ T (ŝ λ, s) + (3 + 4ε)h 2 (s 0 , s) + 1.48c 1 ϑ(d(s)) + 1.48c 1 ϑ(∆( λ)) + c 2 ξ log + (1/ξ). If L 1 is large enough, 4 -3ε 12 h 2 (s 0 , ŝλ ) ≤ T (ŝ λ, s) + (3 + 4ε)h 2 (s 0 , s) + 1 2 pen 1, λ(s) + 1 2 pen 2 ( λ) + c 2 ξ log + (1/ξ) -1/n ≤ T (ŝ λ, s) -pen 1, λ(s) + 1 2 pen 2 ( λ) + (3 + 4ε)h 2 (s 0 , s) + 3 2 pen 1, λ(s) + c 2 ξ log + (1/ξ) -1/n.
Since this inequality is valid for all s ∈ Ŝλ and Ŝ ⊂ Ŝλ ,

4 -3ε 12 h 2 (s 0 , ŝλ ) ≤ γ 4 (ŝ λ) + 1 2 pen 2 ( λ) + inf s∈ Ŝ 3(1 + ε)h 2 (s 0 , s) + 3 2 pen 1, λ(s) + c 2 ξ log + (1/ξ) -1/n.
We deduce from (49),

4 -3ε 12 h 2 (s 0 , ŝλ ) ≤ γ 4 (ŝ λ) + 2pen 2 ( λ) + inf s∈ Ŝ 3(1 + ε)h 2 (s 0 , s) + 3 2 pen 1 (s) + c 2 ξ log + (1/ξ) -1/n.
By using the definition of λ and (52), we get for all λ ∈ Λ,

4 -3ε 12 h 2 (s 0 , ŝλ ) ≤ γ 4 (ŝ λ ) + 2pen 2 (λ) + inf s∈ Ŝ 3(1 + ε)h 2 (s 0 , s) + 3 2 pen 1 (s) + 2c 2 ξ log + (1/ξ) ≤ (3 + 4ε)h 2 (s 0 , ŝλ ) + 3pen 2 (λ) + inf s∈ Ŝ 3(1 + ε)h 2 (s 0 , s) + 3 2 pen 1 (s) + 2c 2 ξ log + (1/ξ).
It remains to take the infimum over λ ∈ Λ to finish the proof.

6.8.2. Proof of Theorem 7. We will apply the selection rule developed in Section 6.8 to pick out an estimator among {ŝ λ , λ ∈ Λ} = {ŝ m , m ∈ M l}. For this purpose, we need to explain the values of the different parameters involved in the procedure. We define I d as the collection of unions of at most d intervals. We set Ŝ = {ŝ m , m ∈ M l}, and for m ∈ M l,

Ŝm = K∈m ŝm K ½ K , m K ∈ M l .
Note that the assumption Ŝ ⊂ m∈ M l Ŝm of Theorem 10 is fulfilled. We define for m ∈ M l, K ∈ m and m K ∈ M l, the partition m K ∨K of K by (20). A function s ∈ Ŝm of the form s = K∈m ŝm K ½ K is piecewise polynomial. In the sequel, m(s) designs a partition of M of the form

m(s) = K∈m m K ∨ K,
with minimal length that is such that

|m(s)| = inf K∈m |m K ∨ K|, s = K∈m ŝm K ½ K .
Let S = ∞ k=1 P k,r and note that Ŝm ⊂ S for all m ∈ M l. Let s ∈ S and k ≥ 1 be the smallest integer for which s ∈ P k,r . It follows from Proposition 1 that Assumption 2 is satisfied with S = P l∨k,r and d P l∨k,r (s) = (( l ∨ k) + 2)(r + 2). In particular, for all m ∈ M l and s ∈ S, we may set since ŝm ∈ P l,r ,

d ŝm (s) = inf k≥1 P k,r ∋s ( l ∨ k) + 2 (r + 2).
We now define d(•) for s ∈ S and ∆(•) for m ∈ M l by

d(s) = inf k≥1 P k,r ∋s (k + 2)(r + 2), ∆(m) = l(r + 2).
We define d(•) arbitrarily when s ∈ S. Note that (48) is satisfied. We now define L 0 = 6L 1 and the penalties for L ≥ L 0 , m ∈ M l and s ∈ Ŝm by

pen 1,m (s) = L (r + 1)|m(s)| log 2 + (n/(r + 1)) n , pen 2 (m) = L (r + 1) l log 2 + (n/(r + 1)) n .
The first penalty satisfies the lower bound (50) since

d(s) ≤ (r + 2)(|m(s)| + 2) ≤ 6(r + 1)|m(s)| for all s ∈ Ŝm . It remains to define pen 1 (s) for s ∈ Ŝ = {ŝ m , m ∈ M l}. Claim 6. For all m, m ′ ∈ M, |m(ŝ m ′ )| ≤ |m| + |m ′ |.
Proof of Claim 6. We have,

|m(ŝ m ′ )| ≤ K∈m |m ′ K ∨ K| ≤ K∈m K ∩ K ′ , K ′ ∈ m, K ∩ K ′ = ∅ ≤ K ∩ K ′ , (K, K ′ ) ∈ m × m ′ , K ∩ K ′ = ∅ . Since m and m ′ are collections of intervals, |m(ŝ m ′ )| ≤ |m| + |m ′ |.
It then follows that for all m, m ′ ∈ M l,

pen 1,m (ŝ m ′ ) ≤ L (r + 1) l log 2 + (n/(r + 1)) n + pen 2 (m).
The penalty defined by pen 1 (ŝ m ′ ) = L (r + 1) l log 2 + (n/(r + 1)) n satisfies therefore (49).

Note now that the selection rules described in Sections 6.8 and 4.3 coincide. Theorem 10 controls the risk of the selected estimator: for all ξ > 0, there exists an event Ω ξ of probability larger than 1e -nξ , and on which:

h 2 (s 0 , ŝ m) ≤ C inf m∈ M l h 2 (s 0 , ŝm ) + pen 2 (m) + inf m∈ M l h 2 (s 0 , ŝm ) + pen 1 (ŝ m ) + ξ log + (1/ξ) ,
where C is a universal constant. By using the definition of the penalty terms,

h 2 (s 0 , ŝ m) ≤ C ′ inf m∈ M l h 2 (s 0 , ŝm ) + L (r + 1) l log 2 + (n/(r + 1)) n + ξ log + (1/ξ) ,
where C ′ is a universal constant. It then remains to use the fact that ŝm is a ρ-estimator on P r (m) to get a bound on h 2 (s 0 , ŝm ) on the same event Ω ξ (the event that appears in Theorem 3 to control the risk of a ρ-estimator is the same that the one that appears in Theorem 10. It is, in each case, defined by Lemma 4).

6.8.3. Proof of Theorem 8. The proof is almost the same as in the case of Theorem 7. The modifications are very mild, and this is the reason why we only specify the values of the different parameters involved in the procedure of Section 6.8:

Ŝ = {ŝ m , m ∈ M ≤ lmax } Ŝm = K∈m ŝm K ½ K , m K ∈ M ≤ lmax for all m ∈ M ≤ lmax pen 1 (ŝ m ) = pen 2 (m) = L (r + 1)|m| log 2 + (n/(r + 1)) n for all m ∈ M ≤ lmax .
6.9. Proof of Corollary 2. This corollary follows from (23) and the lemma below whose proof is given in the next section.

Lemma 7. Suppose that condition (25) is met and r = 0. Then, for all ξ > 0, the following holds with probability larger than 1e -nξ : for all ℓ ∈ {1, . . . , n -1}, m ∈ M ℓ written as in (4) and such that Y (1) and Y (n) belong to [x 1 , x ℓ+1 ], there exists m ′ ∈ M ℓ such that the ρ-estimator ŝm ′ satisfies

h 2 (s 0 , ŝm ′ ) ≤ C h 2 (s 0 , P 0 (m)) + ℓ log 2 + (n/ℓ) n + ξ log + (1/ξ) . (53)
6.10. Proofs of Lemmas 7 and 3. We set M = ℓ≥1 M ℓ . The following claim will be useful in the sequel.

Claim 7. Let ξ > 0 and Ω ξ be the event given by Lemma 4 when I d is the collection of unions of at most d intervals. Then, P (Ω ξ ) ≥ 1e -nξ . Let η ≥ 0, r ≥ 0, and m, m ′ ∈ M. The following holds on Ω ξ : for all piecewise polynomial estimators ŝm ∈ P r (m), ŝm

′ ∈ P r (m ′ ) such that T (ŝ m , ŝm ′ ) ≥ -η, h 2 (s 0 , ŝm ′ ) ≤ C h 2 (s 0 , ŝm ) + (r + 1)(|m| + |m ′ |) n log 2 + n (r + 1)(|m| + |m ′ |) + ξ log + (1/ξ) + η .
Moreover, if ŝm is a ρ-estimator on P r (m),

h 2 (s 0 , ŝm ) ≤ C h 2 (s 0 , P r (m)) + (r + 1)|m| n log 2 + n (r + 1)|m| + ξ log + (1/ξ) .
In the above inequalities, C is universal.

Proof. Let ε = 1/24. On Ω ξ :

T (ŝ m , ŝm ′ ) ≤ (3 + 4ε)h 2 (s 0 , ŝm ) - 4 -3ε 12 h 2 (s 0 , ŝm ′ ) + c 1 ϑ(d ŝm ′ (ŝ m )) + c 2 ξ log + (1/ξ), (54)
where c 1 and c 2 are universal constants. Now, ŝm and ŝm ′ belong to P r (m ′′ ) where

m ′′ = K ∩ K ′ , (K, K ′ ) ∈ m × m ′ , K ∩ K ′ = ∅ . Yet, |m ′′ | ≤ |m| + |m ′ |.
Thereby, ŝm and ŝm ′ belong to P |m|+|m ′ |,r and it follows from Proposition 1 that we may set

d ŝ′ m (ŝ m ) = (|m| + |m ′ | + 2)(r + 2).
We now bound ϑ(d ŝ′ m (ŝ m )) from above in (54), and then use T (ŝ m , ŝm ′ ) ≥ -η to prove the first inequality of the claim. The second one follows from Theorem 3 and Proposition 1.

Proof of Lemma 7. Let m ∈ M ′ ℓ be a collection written as Let ŝm and ŝ m be ρ-estimators on P 0 (m) and P 0 ( m) respectively. We order the intervals of m as follows. We define ℓ intervals I 1 , . . . , I ℓ such that m = {I 1 , . . . , I ℓ } and such that the value ŝ m on I j , denoted by ŝI j , is non-decreasing when j grows up. We denote the endpoints of I j by a j < b j . We now define j 1 as the largest integer of {1, . . . , n} such that Y (j 1 ) ≤ a j and j 2 as the smallest integer such that Y (j 2 ) ≥ b j . When j 1 = 1, we set K j = [Y (j 1 ) , Y (j 2 ) ] and when j 1 = 1, we set

m = {[x 1 , x 2 ], (x 2 , x 3 ], (
K j = (Y (j 1 ) , Y (j 2 ) ]. Note that K j is the smallest interval containing I j that is either of the form [Y (j 1 ) , Y (j 2 ) ] or (Y (j 1 ) , Y (j 2 ) ]. Define J 1 = K 1 and for j ∈ {2, . . . , ℓ}, J j = K j \ j-1 i=1 K i . Since K i ⊂ K j when i = j, K j \ K i is an interval. Therefore, J j = j i=1 (K j \ K i ) is also an interval. When it is not empty, it is either of the form [Y (1) , Y (i) ] with i > 1 or (Y (i 1 ) , Y (i 2 ) ] with i 1 < i 2 .
The collection m′ = {J j , j ∈ {1, . . . , ℓ}} defines therefore a partition of [Y (1) , Y (n) ] that belongs to M ℓ ′ with ℓ ′ ≤ ℓ (we must remove the empty sets). Let s be the step function of P 0 ( m′ ) defined by

s = ℓ j=1 ŝI j ½ J j . We now prove that s ≤ ŝ m. When t ∈ [Y (1) , Y (n) ], s(t) = ŝ m(t) = 0. When t ∈ [Y (1) , Y (n) ]
, there exist j ∈ {1, . . . , ℓ} such that t ∈ I j and j ′ ≤ j such that t ∈ J j ′ . Therefore, s(t) = ŝI j ′ . By using that ŝI j ′ ≤ ŝI j , we finally deduce that s(t) ≤ ŝ m(t).

Consider an interval I j ∈ m and let us denote the cardinal of Y (i) , Y (i) ∈ I j , i ∈ {1, . . . , n} by k j . When k j ≥ 3, there exists at least k j -2 random variables Y (i) that belong to I j but not to ∪ j ′ ∈{1,...,n} j ′ =j K j ′ . Such Y (i) belong therefore to J j and satisfy s(Y (i) ) = ŝ m(Y (i) ). Therefore,

Y (i) , s(Y (i) ) = ŝ m(Y (i) ), i ∈ {1, . . . , n} = ℓ j=1 Y (i) , s(Y (i) ) = ŝ m(Y (i) ), Y (i) ∈ I j , i ∈ {1, . . . , n} ≤ 2ℓ. ( 55
)
It follows from s ≤ ŝ m, (55) and (25) that T (s, ŝ m) ≤ 2ℓ/n. We now use Claim 7 to get on Ω ξ

h 2 (s 0 , s) ≤ C h 2 (s 0 , ŝ m) + ℓ n log 2 + (n/ℓ) + ξ log + (1/ξ) , ( 56
)
where C is universal.

We may refine the partition m′ ∈ M ℓ ′ to get m ′ ∈ M ℓ such that P 0 ( m′ ) ⊂ P 0 (m ′ ). Let ŝm ′ and ŝ m′ be ρ-estimators on P 0 (m ′ ) and P 0 ( m′ ) respectively. There exists a universal constant C ′ such that on Ω ξ :

h 2 (s 0 , ŝm ′ ) ≤ C ′ h 2 (s 0 , P 0 (m ′ )) + ℓ n log 2 + (n/ℓ) + ξ log + (1/ξ) .
By using that s ∈ P 0 ( m′ ) ⊂ P 0 (m ′ ) and (56),

h 2 (s 0 , ŝm ′ ) ≤ C ′ h 2 (s 0 , s) + ℓ n log 2 + (n/ℓ) + ξ log + (1/ξ) , ≤ C ′′ h 2 (s 0 , ŝ m) + ℓ n log 2 + (n/ℓ) + ξ log + (1/ξ) , (57
T (ŝ m, ŝm ) = T (ŝ m, ŝm ½ [Y (1) ,Y (n) ] ) + 1 4 R ŝm ½ [Y (1) ,Y (n) ] dM - R ŝm dM ≤ 0.
Therefore, Claim 7 asserts that

h 2 (s 0 , ŝ m) ≤ C ′′′ h 2 (s 0 , ŝm ) + ℓ n log 2 + (n/ℓ) + ξ log + (1/ξ) , (58)
where C ′′′ is universal. By using that ŝm is a ρ-estimator,

h 2 (s 0 , ŝm ) ≤ C ′′′′ h 2 (s 0 , P 0 (m)) + ℓ n log 2 + (n/ℓ) + ξ log + (1/ξ) . ( 59
)
It remains to put inequalities (57), (58) and (59) together to finish the proof.

Proof of Lemma 3. Note that we may always suppose that

K ∩ {Y (1) , . . . , Y (n) }, K ∈ m contains Y (1)
and Y (n) (up to an increase of |m| by 2). Let

m 1 = K ∈ m, {Y (1) , . . . , Y (n) } ∩ K = ∅ .
Then, m 1 = ∅ and we may write m 1 = {K j , j ∈ {1, . . . , k}} where 1 ≤ k ≤ ℓ and where K j is an interval with endpoints a j , b j satisfying a 1 < b 1 ≤ a 2 < b 2 < . . . . For each j ∈ {1, . . . , k}, we set

α j = min Y (i) , Y (i) ∈ K j , β j = max Y (i) , Y (i) ∈ K j .
We define for j ∈ {2, . . . , k -1}, J 2j = (β j , α j+1 ] and for j ∈ {2, . . . , k}, J 2j-1 = (α j ,

β j ]. If β 1 = Y (1) , we set J 1 = ∅, J 2 = [β 1 , α 2 ] and if β 1 > Y (1) , J 1 = [Y (1) , β 1 ], J 2 = (β 1 , α 2 ]
. Note that J 2j-1 ⊂ K j for all j ∈ {1, . . . , k}. The collection m ′ = {J j , j ∈ {1, . . . , 2k -1}} defines a partition of M such that |m ′ | ≤ 2k -1. We define the ρ-estimator

ŝm ′ = k j=1 ŝJ 2j-1 + k-1 j=1 ŝJ 2j ,
where ŝA maximizes L A (•) over P r (A) for all non-empty interval A with the convention that ŝ∅ = 0 when A = ∅. We now consider

sm ′ = k j=1 ŝJ 2j-1 .
Note that sm ′ also belongs to the random model P r (m ′ ) and hence T (ŝ m ′ , sm ′ ) ≤ 0. We deduce from Claim 7 and from

|m ′ | ≤ 2k -1 ≤ 2ℓ -1, that on Ω ξ h 2 (s 0 , ŝm ′ ) ≤ C h 2 (s 0 , sm ′ ) + (r + 1)ℓ n log 2 + n (r + 1)ℓ + ξ log + (1/ξ) , ( 60
)
where C is universal. Now, for all j ∈ {1, . . . , k}, such that J 2j-1 = ∅,

T ŝJ 2j-1 , ŝK j ½ J 2j-1 ≤ 0, (61)
since ŝJ 2j-1 maximizes L J 2j-1 (•) over P r (J 2j-1 ) and that ŝK j ½ J 2j-1 ∈ P r (J 2j-1 ). When J 2j-1 = ∅, T ŝJ 2j-1 , ŝK j ½ J 2j-1 = 0, and thus (61) also holds.

We define

A = k j=1 J 2j-1 .
We deduce from (61) that T (s m ′ ½ A , ŝm ½ A ) ≤ 0. Therefore,

T (s m ′ , ŝm ) = T (s m ′ ½ A , ŝm ½ A ) + T (0, ŝm ½ A c ) ≤ 0 + T (0, ŝm ½ A c ) ≤ A c ψ (ŝ m /0) dN,
where we recall the conventions ψ(0/0) = ψ(1) = 0, ψ(x/0) = ψ(∞) = 1 for all x > 0. Let B = k j=1 K j . Note that ŝm vanishes outside B and thus, as |ψ| ≤ 1,

T (s m ′ , ŝm ) ≤ B∩A c ψ (ŝ m /0) dN ≤ N (B ∩ A c ). (62) Now, N (B ∩ A c ) = k j=1 {N (K j ) -N (J 2j-1 )} .
Since α j , β j ∈ {Y i , i ∈ Î}, we deduce from (25) that N (K j ) -N (J 2j-1 ) = N ({α j }). In each of the frameworks, N ({α j }) ≤ 1/n and thus N (B ∩ A c ) ≤ k/n. By using (62), we get T (s m ′ , ŝm ) ≤ k/n. Claim 7 with η = k/n ≤ ℓ/n ensures that on Ω ξ :

h 2 (s 0 , sm ′ ) ≤ C ′ h 2 (s 0 , ŝm ) + (r + 1)ℓ n log 2 + n (r + 1)ℓ + ξ log + (1/ξ) ,
where C ′′ is universal. Since ŝm is a ρ-estimator on P r (m), we deduce that on the same event Ω ξ :

h 2 (s 0 , ŝm ) ≤ C ′′ h 2 (s 0 , P r (m)) + (r + 1)ℓ n log 2 + n (r + 1)ℓ + ξ log + (1/ξ) ,
where C ′′ is universal. It then remains to combine the two last inequalities with (60) to finish the proof.

For the proof of this inequality, we refer to Claim 3 page 26. Under suitable assumptions on the collection F = {ψ(s ′ /s), s, s ′ ∈ S}, Inequality (63) roughly says that with high probability (and ε = 1/24):

T (s, s ′ ) -T E (s, s ′ ) ≤ 1 6 h 2 (s 0 , s) + h 2 (s 0 , s ′ ) + R S (n) for all s, s ′ ∈ S. (64)
The term R S (n) depends on the probability of the event on which (64) holds true and the complexity of S. The approximation T (s, s ′ ) ≃ T E (s, s ′ ) is then accurate enough to control the risk of a ρestimator ŝ. Indeed, we deduce from (2), that for all s, s ′ ∈ S,

1 6 h 2 (s 0 , s) - 19 6 h 2 (s 0 , s ′ ) -R S (n) ≤ T (s, s ′ ) ≤ 19 6 h 2 (s 0 , s) - 1 6 h 2 (s 0 , s ′ ) + R S (n).
We may then replace T E (s, s ′ ) by T (s, s ′ ) and γ E (•) by γ(•) in the computations of Section 2.2 to bound the risk of a ρ-estimator ŝ. This leads to h 2 (s 0 , ŝ) ≤ 37h 2 (s 0 , S) + 12R S (n) + 6/n.

For a rigorous result, we refer to Theorem 3.

As a by-product of the proof of Theorem 11 we get the following proposition (to be proved in Section D.6) which may be of independent interest: Proposition 12. Consider framework 1 and an at most countable set F ⊂ S of functions f such that |f (t)| ≤ 1 for all t ∈ R, f ∈ F. Let for u ∈ (0, 1), A u be the collection of sets defined by

A u = {{t ∈ R, f + (t) > u} , f ∈ F} ∪ {{t ∈ R, f -(t) > u} , f ∈ F} ,
and S Au (2n) be the Vapnik-Chervonenkis shatter coefficient S Au (2n) = max t 1 ,...,t 2n ∈R |{{t 1 , . . . , t 2n } ∩ A, A ∈ A u }| .

Let σ 2 = sup f ∈F E[f 2 (X)] and r n = sup u∈(0,1) log + |S Au (2n)|. Then, there exist universal constants C, C ′ such that

E sup f ∈F |Z(f )| ≤ C inf η∈(0,1) σ log(1/η) + η 0 sup f ∈F P (|f (X)| > u) du r n n + C r n n ≤ C ′ σ r n log + (1/σ) n + r n n . ( 65
)
This proposition gives a bound on E sup f ∈F |Z(f )| that involves the Vapnik-Chervonenkis shatter coefficients S Au (2n) of A u . This result may not be as sharp as the bounds based on covering numbers (see Theorem 3.1 of [START_REF] Giné | Concentration inequalities and asymptotic results for ratio type empirical processes[END_REF]). It is, however, rather convenient in the situations where the shatter coefficients are easier to control than the covering numbers.

Our proposition may be viewed as a refined version of a result of [START_REF] Baraud | Bounding the expectation of the supremum of an empirical process over a (weak) vc-major class[END_REF] when the random variables X i are identically distributed and when A u is Vapnik-Chervonenkis with dimension d (apart from constants). Such an assumption corresponds to a notion of (weak) VC-major class. In that case, Sauer's lemma [START_REF] Sauer | On the density of families of sets[END_REF] implies

E sup f ∈F |Z(f )| ≤ C ′′ σ d log + (n/d) log + (1/σ) n + d log + (n/d) n , (66)
where C ′′ is a number. If we put aside the constant C ′′ , the main difference between this bound and Inequality (2.8) of [START_REF] Baraud | Bounding the expectation of the supremum of an empirical process over a (weak) vc-major class[END_REF] lies in the position of the logarithmic term log + (1/σ): it is here involved inside the square root while it is outside in [START_REF] Baraud | Bounding the expectation of the supremum of an empirical process over a (weak) vc-major class[END_REF]. Now, on A n , s(t) = 1/t when t ≥ 2η and hence using the definition of s 0 :

h 2 (s 0 , s) ≥ 1 4 1 2η 1 t 1 - η (n -1)t + η 2 dt. Now, inf t∈[2η,1] 1 - η (n -1)t + η 2 ≥ 1 - η 2(n -1)η + η 2 > 0.17.
Therefore, h 2 (s 0 , s) > 0.04 log(1/(2η)) and

E[h 2 (s 0 , s)] > 0.04 log(1/(2η))P (A n ∩ B n ).
It remains to use (67) to conclude.

We now turn to ρ-estimation. The model S fulfils Assumption 2 with d S (•) = 1, S = S and where I 1 is the collection of intervals. A ρ-estimator ŝ on S satisfies therefore

E[h 2 (s 0 , ŝ)] ≤ C E[h 2 (s 0 , S)] + log 2 n n .
Now, the bias term can be bounded above by

E[h 2 (s 0 , S)] ≤ E[h 2 (s 0 , s 1 )] with s 1 (t) = t -1 ½ t≥1 .
Sinces 0 differs from s 1 only on [η, 1),

E[h 2 (s 0 , S)] ≤ 1 2 1 η s 0 (t) -0 2 G(t) dt = P (T ∈ [η, 1]) 2 = G(η) -G(1) 2 = 1 -η n ≤ 1 n .
This concludes the proof.

We now need to study the deviations of Z Ms 0 . There is nothing to prove in framework 1 since then Z Ms 0 = 0. The lemma below allows to control the deviations of Z Ms 0 (f ) for all bounded function f . It is proved in Section D.4.

Lemma 10. Define G(t) = P (X ≥ t) in framework 2 and G(t) = P (X t-= 1)½ I obs (t) in framework 3. For all ξ > 0, there exists an event Ω ξ,2 such that P [Ω ξ,2 ] ≥ 1e -nξ and on which: for all ε > 0, and measurable function f such that |f (t)| ≤ 1 for all t ∈ R,

Z Ms 0 (f ) ≤ ευ Ms 0 (f ) + C ′ ε inf α≥0 [ξ + 1/n] α 0 s 0 dµ + ∞ α s 0 G dµ + ξ + 1/n . (72)
Moreover, in framework 2,

Z Ms 0 (f ) ≤ ευ Ms 0 (f ) + C ′′ ε (ξ + 1/n) log + [1/(ξ + 1/n)] . (73)
In these inequalities, C ′ ε and C ′′ ε only depend on ε.

The computation of the infimum in (72) may be avoided in framework 3 when one restricts the collection among which the functions f may vary. More precisely, a bound on Z Ms 0 (f ) may be deduced from the following result to be proved in Section D.5 and from Lemma 9.

Lemma 11. Consider framework 3. Let for d ≥ 1, I 2d be the class of unions of at most 2d intervals. Then, there exist a universal constant c 2 and an event Ω ξ,2 such that P [Ω ξ,2 ] ≥ 1e -nξ and on which (69) holds true for

Q = M s 0 for all A ∈ I 2d with α = β = c 2 [d log + (n/d) + nξ]/n.
We are now in position to prove (63). In framework 1, we use Lemmas 8 and 9 to deduce on Ω ξ,1 :

|Z(f )| ≤ ευ(f ) + C ε c 1 [log + |S A (2n)| + nξ] n log + n c 1 [log + |S A (2n)| + nξ] .
Sauer's lemma shows that there exists c ′ 1 such that log + |S A (2n)| ≤ c ′ 1 d log + (n/d). Inequality (63) then follows from elementary computations.

We now turn to frameworks 2 and 3. As in framework 1, Lemmas 8 and 9 imply on Ω ξ+(log 2)/n,1 :

|Z N (f )| ≤ ευ N (f ) + C ε d log 2 + (n/d) n + ξ log + (1/ξ) ,
where C ε only depends on ε. It follows from Lemmas 8, 10 and 11 that on Ω ξ+(log 2)/n,2 :

Z Ms 0 (f ) ≤ ευ Ms 0 (f ) + C ′ ε d log 2 + (n/d) n + ξ log + (1/ξ) , where C ′ ε only depends on ε. Since |Z(f )| ≤ |Z N (f )|+|Z Ms 0 (f )|, we get on Ω ξ+(log 2)/n,1 ∩Ω ξ+(log 2)/n,2 : |Z(f )| ≤ ε(υ N (f ) + υ Ms 0 (f )) + (C ε + C ′ ε ) d log 2 + (n/d) n + ξ log + (1/ξ) . (74) Now, υ N (f ) ≤ E R f 2 dN = E R f 2 dM s 0 . (75)
In framework 2, we deduce from Lemma 10 with ε = 1/2 that on Ω ξ+(log 2)/n,2 : R

f 2 dM s 0 -E R f 2 dM s 0 ≤ 1 2 E R f 4 dM s 0 + C(ξ + 1/n) log + [1/(ξ + 1/n)] ≤ 1 2 E R f 4 dM s 0 + C d log 2 + (n/d) n + ξ log + (1/ξ) , ( 76
)
where C is universal. In framework 3,

t ∈ R, f 2 (t) > u = t ∈ R, f + (t) > √ u t ∈ R, f -(t) > √ u
is a union of at most 2d intervals. Lemma 11 with Lemma 9 show that (76) remains valid on Ω ξ+(log 2)/n,2 . Moreover,

as |f | ≤ 1, E R f 2 dM s 0 ≤ 2 R f 2 dM s 0 + 2C d log 2 + (n/d) n + ξ log + (1/ξ) .
By using (75),

υ N (f ) ≤ 2υ Ms 0 (f ) + 2C d log 2 + (n/d) n + ξ log + (1/ξ) .
We put this inequality in (74) and use υ Ms

0 (f ) ≤ υ(f ) to show (63) on Ω ξ+(log 2)/n,1 ∩ Ω ξ+(log 2)/n,2 . Moreover, P Ω ξ+(log 2)/n,1 ∩ Ω ξ+(log 2)/n,2 c ≤ e -nξ .
D.2. Proof of Lemma 8. For convenience, and to make the proof more readable, we introduce a new notation. Given expressions x, y ∈ R, the assertion: there exists a universal constant C such that x ≤ Cy is written in the sequel as x y. The claim below follows from elementary computations.

Claim 8. When (69) holds true,

|Q(A) -E[Q(A)]| α min{Q(A), E[Q(A)]} + α + β. (77)
Proof of Claim 8. For reasons of symmetry, we may suppose that Q(A) ≥ E[Q(A)] to prove (77). We derive from (69),

|Q(A) -E[Q(A)]| αQ(A) + α + β α (Q(A) -E[Q(A)]) + αE[Q(A)] + α + β.
For all ε > 0, we deduce from the inequality 2

√ xy ≤ εx + ε -1 y, that |Q(A) -E[Q(A)]| ≤ 1 2 |Q(A) -E[Q(A)]| + C αE[Q(A)] + α + β ,
where C is universal. This shows (77).

Without loss of generality, we prove the lemma when the functions f of F are non-negative. We suppose moreover that we are on an event on which (69) holds true. Let for u ∈ (0, 1), A f,u = {t ∈ R, f (t) > u}. As in [START_REF] Baraud | Bounding the expectation of the supremum of an empirical process over a (weak) vc-major class[END_REF], the notion of integral is a great help: for all t ∈ R,

f (t) = 1 0 ½ A f,u (t) du.
Let ε > 0 and η ∈ (0, 1] to be specified later. Since

f 2 (t) = 2 1 0 u½ A f,u (t) du, we get |Z(f )| -ευ Q (f ) = 1 0 (Q(A f,u ) -E[Q(A f,u )]) du -2ε min 1 0 uQ(A f,u ) du, 1 0 uE[Q(A f,u )] du ≤ 1 0 {|Q(A f,u ) -E[Q(A f,u )]| -2εu min {Q(A f,u ), E[Q(A f,u )]}} du ≤ η 0 |Q(A f,u ) -E[Q(A f,u )]| du + 1 η {|Q(A f,u ) -E[Q(A f,u )]| -2εu min {Q(A f,u ), E[Q(A f,u )]}} du. ( 78
)
It follows from (77) and the inequality 2

√ xy ≤ εx + ε -1 y, |Q(A f,u ) -E[Q(A f,u )]| -2εu min {Q(A f,u ), E[Q(A f,u )]} α/(εu) + α + β.
We deduce,

|Z(f )| -ευ Q (f ) √ α η 0 E[Q(A f,u )] du + (α/ε) log (1/η) + α + β. (79)
We now optimize this result with respect to ε and η:

|Z(f )| √ α inf η∈(0,1] υ Q (f ) log(1/η) + η 0 E[Q(A f,u )] du + α + β. It remains to use E[Q(A f,u )] ≤ 1 to prove (70).
Elementary computations then show (71). As x → x log + (1/x) is non-decreasing, for all x ≤ y, xy log + (1/x) ≤ y 2 log + (1/y). Moreover, when x ≥ y, log + (1/x) ≤ log + (1/y) and hence xy log + (1/x) ≤ xy log + (1/y). Therefore, for all x, y > 0,

xy log + (1/x) ≤ max{x, y}y log + (1/y) ≤ (x + y)y log + (1/y).
We thus obtain for all ε > 0,

2 xy log + (1/x) ≤ ε(x + y) + ε -1 y log + (1/y) ≤ εx + C ε y log + (1/y),
where C ε = ε + ε -1 . We use this inequality with x = υ Q (f ) and y = α to get

2 αυ Q (f ) log + (1/υ Q (f )) ≤ ευ Q (f ) + C ε α log + (1/α).
This proves (71). D.3. Proof of Lemma 9. Let A ∈ A and (A m ) m≥1 be the sequence given by the theorem. Then, N (A m ) converges to N (A). Moreover, it follows from the dominated convergence theorem that

E R |½ Am -½ A | dN converges to 0. In particular, E[N (A m )] converges to E[N (A)]. We deduce that sup A∈A | N (A) -E[N (A)]| = sup A∈A ′ | N (A) -E[N (A)]|.
From now on, we may therefore consider, without loss of generality, the collection A as at most countable. We then use the celebrated Vapnik-Chervonenkis inequalities for relative deviation recalled below (see for instance page 24 of [START_REF] Devroye | Combinatorial methods in density estimation[END_REF]):

Theorem 14 (Vapnik-Chervonenkis inequalities for relative deviation). Let Z 1 , . . . , Z n be n independent and identically distributed random variables with values in a space X . Let B be an at most countable collection of measurable sets. Define the empirical measure ν

n (B) = n -1 n i=1 ½ B (Z i ), ν(B) = E[ν n (B)] and the Vapnik-Chervonenkis shatter coefficient S B (2n) = max z 1 ,...,z 2n ∈X |{{z 1 , . . . , z 2n } ∩ B, B ∈ B}| .
Then, for all x > 0,

P sup B∈B ν(B) -ν n (B) ν(B) ≥ x ≤ 4S B (2n)e -nx 2 /4 P sup B∈B ν n (B) -ν(B) ν n (B) ≥ x ≤ 4S B (2n)e -nx 2 /4 .
In particular,

P sup B∈B ν n (B) -ν(B) ≥ x ≤ 8S B (2n)e -nx 2 /4 . (80)
Assume that we are within framework 1. Then, the random measure N is the empirical measure of X 1 , . . . , X n . Now (80) with B = A,

x 2 = 4 n log 8 + log + |S A (2n)| + nξ
shows that (69) holds true with probability larger than 1e -nξ , α = x 2 , β = 0.

The proof in frameworks 2 and 3 is very similar since N is an empirical measure for suitable random variables with values in X = R × {0, 1}:

Z i = (X i , ½ D i =1 ) in framework 2 and Z i = (T (i) 1,0 ½ T (i) 1,0 ∈I obs , ½ T (i) 1,0 ∈I obs
) in framework 3. We apply (80) with B = {A × {1}, A ∈ A}. Moreover,

|S B (2n)| ≤ max x 1 ,...,x 2n ∈R |{{x 1 , . . . , x 2n } ∩ A, A ∈ A}| ≤ |S A (2n)| .
We end the proof as in framework 1. D.4. Proof of Lemma 10.

Claim 9. Let for t ≥ 0, V (t) = ½ X≥t in framework 2 and V (t) = ½ X t-=1 ½ I obs (t) in framework 3.

Then, for any Borel set A ⊂ [0, +∞), and k ≥ 1,

E A s 0 (t)V (t) dt k ≤ k! A s 0 (t)E[V (t)] dt.
The proof of this lemma is deferred to Sections D.4.1 and D.4.2 below. We define α > 0,

R α = α 0 s 0 G n - √ G 2 dµ,
and we prove:

Claim 10. For all ξ > 0 and probability larger than 1 -2e -nξ ,

R α ≤ 3ξ α 0 s 0 dµ. Proof. Let u = n/3 and λ = u/ α 0 s 0 dµ. It follows from Jensen's inequality that exp u R α α 0 s 0 dµ ≤ 1 α 0 s 0 dµ α 0 s 0 exp u( G n - √ G) 2 dµ.
We deduce,

E [exp (λR α )] ≤ 1 α 0 s 0 dµ α 0 s 0 (t)E exp u( G n (t) -G(t)) 2 dt. (81) Now, E exp u( G n (t) -G(t)) 2 = 1 + ∞ 1 P exp u( G n (t) -G(t)) 2 ≥ x dx = 1 + ∞ 1 P G n (t) -G(t) ≥ log x u dx.
The random variable nG n (t) is binomially distributed with parameters (n, G(t)). Therefore, we derive from Theorems 3 and 4 of [START_REF] Okamoto | Some inequalities relating to the partial sum of binomial probabilities[END_REF] that

P G n (t) -G(t) ≥ log x u ≤ 2 x n/u . Hence, E exp u( G n (t) -G(t)) 2 ≤ 1 + ∞ 1 2 x n/u dx ≤ 1 + ∞ 1 2 x 3 dx ≤ 2.
By (81), E [exp (λR α )] ≤ 2 and by Markov's inequality,

P [R α ≥ nξ/λ] = P e λRα ≥ e nξ ≤ 2e -nξ .
We now prove Lemma 10. We have,

|Z Ms 0 (f )| ≤ ∞ 0 s 0 |f (G n -G)| dµ ≤ Gn≤G s 0 f G n - √ G √ G -G n + 2 G n dµ + Gn>G s 0 f G n - √ G G n - √ G + 2 √ G dµ ≤ ∞ 0 s 0 |f | G n - √ G 2 dµ + 2 ∞ 0 s 0 |f | G n - √ G min{G n , G} dµ. Define R = R ∞ = ∞ 0 s 0 G n - √ G 2 dµ.
By using |f | ≤ 1 and Cauchy-Schwarz inequality,

|Z Ms 0 (f )| ≤ R + 2 √ R ∞ 0 s 0 f 2 min{G n , G} dµ ≤ R + 2 √ R υ Ms 0 (f ).
Therefore, for all ε > 0, using that 2

√ xy ≤ ε -1 x + εy, |Z Ms 0 (f )| ≤ ευ Ms 0 (f ) + (1 + ε -1 )R. (82)
It remains to bound R from above. We consider α ≥ 0 that minimizes

[ξ + 1/n] α 0 s 0 dµ + ∞ α s 0 G dµ + ξ + 1/n. Now, R ≤ R α + ∞ α s 0 (G n + G) dµ. ( 83
)
With probability larger than 1 -(1/2)e -nξ , Claim 10 ensures that

R α ≤ 3 ξ + log 4 n α 0 s 0 dµ. (84) Now, ∞ α s 0 G n dµ = 1 n n i=1 ∞ α s 0 (t)V i (t) dt,
where V i (t) = ½ X i ≥t in framework 2 and V i (t) = ½ X (i) t-=1 ½ I obs (t) in framework 3. Claim 9 shows that the assumptions of Bernstein's deviation inequality are satisfied (Proposition 2.9 of [START_REF] Massart | Concentration inequalities and model selection[END_REF]). Therefore, with probability larger than 1

-(1/2)e -nξ , ∞ α s 0 [G n -G] dµ ≤ 2 ξ + log 2 n ∞ α s 0 G dµ + ξ + log 2 n . (85) Since 2 √ xy ≤ x + y, ∞ α s 0 G n dµ ≤ 2 ∞ α s 0 G dµ + 2 ξ + log 2 n . (86)
By putting (84) and ( 86) into (83), we get with probability larger than 1e -nξ ,

R ≤ 3 log 4 n + ξ α 0 s 0 dµ + 3 ∞ α s 0 G dµ + 2ξ + 2 log 2 n .
It then remains to use the definition of α and (82) to prove (72). Moreover, in framework 2,

∞ α s 0 G dµ = ∞ α f 0 (t) P (T ≥ t) P (T ≥ t)P (C ≥ t) dt ≤ ∞ α f 0 dµ, and α 0 s 0 dµ = α 0 f 0 (t) P (T ≥ t) dt = -log ∞ α f 0 dµ ,
which gives (73). D.4.1. Proof of Claim 9 in framework 2. We define for k ≥ 1,

J k = t 1 ,...,t k ∈A t 1 <t 2 <•••<t k   k j=1 s 0 (t j )   P (X ≥ t k ) dt 1 dt 2 . . . dt k .
We have,

E A s 0 (t)½ X≥t dt k = E   A k k j=1 s 0 (t j )½ X≥t j dt 1 dt 2 . . . dt k   = A k   k j=1 s 0 (t j )   P (X ≥ max{t 1 , . . . , t k }) dt 1 dt 2 . . . dt k = k!J k . Now, J k ≤ t 1 ,...,t k-1 ∈A t 1 <t 2 <•••<t k-1   k-1 j=1 s 0 (t j )   ∞ t k-1 s 0 (t k )P (X ≥ t k ) dt k dt 1 dt 2 . . . dt k-1 , and ∞ t k-1 s 0 (t k )P (X ≥ t k ) dt k = ∞ t k-1 f 0 (t k )P (C ≥ t k ) dt k ≤ ∞ t k-1 f 0 (t k ) dt k P (C ≥ t k-1 ) ≤ P (T ≥ t k-1 )P (C ≥ t k-1 ) ≤ P (X ≥ t k-1 ). Therefore, J k ≤ t 1 ,...,t k-1 ∈A t 1 <t 2 <•••<t k-1   k-1 j=1 s 0 (t j )   P (X ≥ t k-1 ) dt 1 dt 2 . . . dt k-1 ≤ J k-1 .
By induction, J k ≤ J 1 . D.4.2. Proof of Claim 9 in framework 3.

Claim 11. Let t > 0, F t = σ(X v , v ≤ t) be the σ-algebra generated by the family of random variables X v , v ∈ [0, t]. Let B be an event F t -measurable. Let µ B be the measure defined for all A ∈ B(R) by µ B (A) = P (B and T 1,0 ∈ A) .

Then, for µ-almost all u > t, dµ B du (u) = P (B and X u-= 1) s 0 (u). (87)

Proof. First of all, µ B is absolutely continuous with respect to the Lebesgue measure µ and admits therefore a Radon-Nikodym derivative. We now aim to show that this derivative is given by (87) for almost all u > t.

Let Z h be the random variable giving the number of jumps of the Markov process in [u-h, u+h]. Then, P (Z h (u) ≥ 2) = o(h) when h → 0. We deduce, µ B ([u, u + h]) = P (B, Z h (u) = 1, T 1,0 ∈ [u, u + h]) + o(h).

When Z h (u) = 1, T 1,0 ∈ [u, u + h] is equivalent to X u-= 1 and X u+h = 0. This yields µ B ([u, u + h]) = P (B, Z h (u) = 1, X u-= 1, X u+h = 0) + o(h) = P (B, X u-= 1, X u+h = 0) + o(h) = P (B, X u-= 1)P (X u+h = 0 | B, X u-= 1) + o(h).

As B is F t -measurable and u > t, µ B ([u, u + h]) = P (B, X u-= 1)P (X u+h = 0 | X u-= 1) + o(h) = P (B, X u-= 1) P (X u-= 1, X u+h = 0) P (X u-= 1) + o(h). We now return to the proof of Claim 9. Without loss of generality, we suppose that A ⊂ I obs . Define for k ≥ 1,

J k = t 1 ,...,t k ∈A t 1 <t 2 <•••<t k   k j=1
s 0 (t j )   P (X t 1 -= 1, . . . , X t k -= 1) dt 1 dt 2 . . . dt k . Yet,

We have,

J k ≤ t 1 ,...,t k-1 ∈A t 1 <t 2 <•••<t k-1   k-1 j=1 s 0 (t j )   ∞ t k-1
s 0 (t k )P (X t 1 -= 1, . . . , X t k -= 1) dt k dt 1 dt 2 . . . dt k-1 .

Let B = X t 1 -= 1, . . . , X t k-1 -= 1 ∈ F t k-1 . Then, ∞ t k-1 s 0 (t k )P (X t 1 -= 1, . . . , X t k -= 1) dt k = ∞ t k-1 dµ B dt k (t k ) dt k = µ B ([t k-1 , +∞))
= P X t 1 -= 1, . . . , X t k-1 -= 1 and T 1,0 ≥ t k-1 ≤ P X t 1 -= 1, . . . , X t k-1 -= 1 .

Therefore, J k ≤ J k-1 and by induction J k ≤ J 1 . D.5. Proof of Lemma 11. Let I 2d be the class of unions of at most 2d intervals with endpoints in (Q ∩ [0, +∞)) ∪ {+∞}. Then, I 2d is at most countable, and we only need to prove (69) when A ∈ I 2d .

The random measure M s 0 is of the form

M s 0 (A) = 1 n n i=1 A s 0 (t)½ X (i)
t-=1 ½ I obs (t) dt for all A ∈ B(R).

There exist independent random variables Z 1 , . . . , Z n such that

M s 0 (A) = 1 n n i=1 f A (Z i ) with f A (Z i ) = A s 0 (t)½ X (i) t-=1 ½ I obs (t) dt.
We measure the complexity of the family {f A , A ∈ I 2d } by means of the notion of entropy with bracketing:

Claim 12. For all δ > 0, there exists a collection C δ of functions of the form f A with A ∈ I 2d . The cardinal of this set can be bounded by log |C δ | ≤ cd log + (1/δ 2 ), where c is a universal constant. Moreover, for all A ∈ I 2d , there exist f A 1 , f A 2 ∈ C δ such that f A 1 ≤ f A ≤ f A 2 and such that for all k ≥ 1,

E (f A 2 (Z 1 ) -f A 1 (Z 1 )) k ≤ k! 2 δ 2 .
Proof. First of all, we only need to prove the claim when δ is smaller than 1, what we will do in the sequel.

We endow I 2d with the distance dist defined for A 1 , A 2 ∈ I 2d by dist(A 1 , A 2 ) = E [M s 0 (A 1 ∆A 2 )] where A 1 ∆A 2 = (A 1 \ A 2 ) ∪ (A 2 \ A 1 ).

We may write dist(A 1 , A 2 ) as

dist(A 1 , A 2 ) = I obs |½ A 1 (t) -½ A 2 (t)| f 0 (t) dt.
We introduce the real valued function F defined for x ≥ 0 by

F (x) = x 0 f 0 (t) dt.
Since F is a continuous non-decreasing function such that F ([0, +∞)) ⊂ [0, 1], there exist an even integer ℓ ∈ [2, 8d/δ 2 + 2], and ℓ non-negative numbers (x 1 , x 2 , . . . , x ℓ-1 , x ℓ ) ∈ {0} × Q ℓ-2 × {+∞} such that max 1≤i≤ℓ-1 {F (x i+1 ) -F (x i )} ≤ δ 2 /(8d).

We may suppose that ℓ ≥ 2d. Let X = {x 1 , x 2 , . . . , x ℓ }, and I dis be the collection of unions of at most 2d closed intervals whose endpoints belong to X .

When k ≤ ℓ/2, choosing k disjoint closed intervals whose endpoints belong to X amounts to choosing 2k numbers among X . When k > ℓ/2, we cannot find k disjoint closed intervals with endpoints in X . The cardinality of I dis is therefore bounded by

|I dis | ≤ 2d k=0 C 2k ℓ .
Standard combinatorial arguments (see, for instance, Lemma 6 of [START_REF] Barron | Risk bounds for model selection via penalization[END_REF]) show that |I dis | ≤ (ℓe/(2d)) 2d . Using now that ℓ ≤ 8d/δ 2 + 2, we derive that log |I dis | ≤ cd log + (1/δ 2 ) for a suitable universal constant c.

For each set A ∈ I 2d , we now show that there exist A 1 , A 2 ∈ I dis such that f A 1 ≤ f A ≤ f A 2 and dist(A 1 , A 2 ) ≤ δ 2 /2. Let A ∈ I 2d be written as A = 2d k=1 A k where A k is an interval whose endpoints are a k ≤ b k . For each k ∈ {1, . . . , 2d}, there exist a

(1) k ≤ a (2) k ≤ b (1) k ≤ b (2) k ∈ X such that a (1) k ≤ a k ≤ a (2) k , b (1) k ≤ b k ≤ b (2) k , and
F a (2) k -F a (1) k ≤ δ 2 /(8d), F b (2) k -F b (1) k ≤ δ 2 /(8d).

Define the closed intervals

A (1) k = x ∈ R, a (2) k ≤ x ≤ b (1) k , A (2) k = x ∈ R, a (1) k ≤ x ≤ b (2) k . Then, A 1 = 2d k=1 A (1)
k and A 2 = 2d k=1 A

(2) k belong to I dis and satisfy f A 1 ≤ f A ≤ f A 2 . Moreover,

A 2 ∆A 1 ⊂ 2d k=1 [a (1) k , a (2)
k ) ∪ (b

(1) k , b (2)
k ],

and hence,

dist(A 1 , A 2 ) ≤ 2d k=1 [a (1) k ,a (2)
k )∪(b Now,

(1) k ,b (2)
E (f A 2 (Z 1 ) -f A 1 (Z 1 )) k = E f A 2 \A 1 (Z 1 ) k ≤ k!E [M s 0 (A 2 \ A 1 )] thanks to Claim 9 ≤ k!dist(A 1 , A 2 ) ≤ k!δ 2 /2,
which completes the proof with C δ = {f A , A ∈ I dis }.

We will use several times an exponential inequality of [START_REF] Massart | Concentration inequalities and model selection[END_REF] to prove Lemma 11. We keep the notation introduced at the beginning of Section D. Consider ξ > 0 and define J as the (possibly empty) set of non-negative integers j such that 2 -j ≥ d/(2n). Let, for j ∈ J, x j = 2 log(j+1)+1+nξ, A j = A ∈ I 2d , 2 -j-1 ≤ E[M s 0 (A)] ≤ 2 -j . Claims 9 and 12 show that assumptions of Corollary 6.9 of [START_REF] Massart | Concentration inequalities and model selection[END_REF] are satisfied with F = f A , -f A , A ∈ A j , σ 2 = 2 -j+1 , b = 1, and H(δ) = c 1 d log + (1/δ 2 ). There exists therefore an event Ω j such that P (Ω j ) ≥ 1e -x j and on which: for all A ∈ A j , We deduce from these computations that (69) holds true with Q = M s 0 on the event Ω ′ ∩ j∈J Ω j for all A ∈ j∈J A j ∪ A with α, β of the form c 2 In these two inequalities, C and C ′ are universal constants.

We integrate these inequalities with respect to ξ to get where C ′′′ is a universal constant. It then remains to bound from above these integrals.

  +∞}, the conclusions of Theorem 5 apply to S: any maximizer s ∈ S of L K (•) on S vanishes γ(•), and any ŝ ∈ S vanishing γ(•) maximizes L K (•) over S.

  x 3 , x 4 ], . . . , (x ℓ , x ℓ+1 ]} and such that x 1 ≤ Y (1) , and Y (n) ≤ x ℓ+1 . We may define a partition m ∈ M ′ ℓ of the form m = {[x 1 , x2 ], (x 2 , x3 ], (x 3 , x4 ], . . . , (x ℓ , xℓ+1 ]} where x1 = Y (1) and xℓ+1 = Y (n) and whose intervals are included into the ones of m.

  ) where C ′′ is universal. Note now that ŝm ½ [Y (1) ,Y (n) ] ∈ P 0 ( m) and thus T (ŝ m, ŝm ½ [Y (1) ,Y (n) ] ) ≤ 0 as ŝ m is a ρ-estimator on the convex model P 0 ( m) (see Theorem 5 and Lemma 2). Now,

  Let us recall that the ρ-estimator ŝm is of the form ŝm = K∈m ŝK where ŝK maximizes L K (•) over P r (K).When K ∈ m does not belong to m 1 , ŝK = 0 and hence ŝm = k j=1 ŝK j .

P

  (X u-= 1, X u+h = 0) = P (X u-= 1, X u+h = 0, Z h (u) = 1) + o(h) = P (T 1,0 ∈ [u, u + h], Z h (u) = 1) + o(h) = P (T 1,0 ∈ [u, u + h]) + o(h).

Finally, by putting

  this inequality into (88),µ B ([u, u + h]) = P (B, X u-= 1) P (T 1,0 ∈ [u, u + h]) P (X u-= 1) + o(h) = P (B, X u-= 1) hf 0 (u) P (X u-= 1) + o(h) = hP (B, X u-= 1)s 0 (u) + o(h),which proves (87).

  t j )½ X t j -=1 dt 1 dt 2 . . . dt k X t 1 -= 1, . . . , X t k -= 1) dt 1 dt 2 . . . dt k = k!J k .

  (8d) + δ 2 /(8d) ≤ δ 2 /2.

√ n σ 0 H

 0 2.Set for δ > 0,B δ = C δ ∪ {-f, f ∈ C δ }. Note that log |B δ | ≤ log 2 + log |C δ | ≤ c 1 d log + (1/δ 2 ),where c 1 is a universal constant. We set H(δ) = c 1 d log + (1/δ 2 ) and for σ ∈ (0, 1],E = (u) ∧ n du + 2(1 + σ)H(σ).Simple arguments allow to bound E from above, see for instance page 190 of[START_REF] Giné | Mathematical foundations of infinite-dimensional statistical models[END_REF]: the fundamental theorem of calculus shows σ log(e/σ) = log + (1/σ 2 ) + d log + (1/σ 2 ). (89)

n

  |M s 0 (A) -E[M s 0 (A)]| E + σ √ nx j + x j .Hence,|M s 0 (A) -E[M s 0 (A)]| σ d log + (1/σ 2 ) + x j n + d log + (1/σ 2 ) + x j n .As σ 2 ≤ 4E[M s 0 (A)], σ 2 ≥ d/n, and x j log + (n/d) + nξ,|M s 0 (A) -E[M s 0 (A)]| E[M s 0 (A)] d log + (n/d) + nξ n + d log + (n/d) + nξ n . Let now A = A ∈ I 2d , E[M s 0 (A)] ≤ d/(2n). We apply Corollary 6.9 of[START_REF] Massart | Concentration inequalities and model selection[END_REF] withF = f A , -f A , A ∈ A , b = 1, σ 2 = min{d/n, 2}. We deduce that there exists an event Ω ′ such thatP (Ω ′ ) ≥ 1 -(1/2)e -nξ and on which: for all A ∈ A, |M s 0 (A) -E[M s 0 (A)]| σ d log + (1/σ 2 ) + nξ + log 2 n + d log + (1/σ 2 ) + nξ + log 2 n . Since σ ≤ d/n ≤ (d log + (n/d) + nξ)/n, |M s 0 (A) -E[M s 0 (A)]| d log + (n/d) + nξ n .

D. 6 . 1 η

 61 (d log + (n/d) + nξ)/n. Now, I 2d = j∈J A j ∪ A, and P Proof of Proposition 12. Suppose without loss of generality that the functions f are nonnegative. Consider ε > 0 and η ∈ (0, 1). We derive from the beginning of the proof of Theorem 11 that for all f ∈ F, and u ∈ (0, 1), there exists A u ∈ A u (we omit the subscript f ) such that|Z(f )| ≤ εσ 2 + η 0 |N (A u ) -E[N (A u )]| du + {|N (A u ) -E[N (A u )]| -2εuE[N (A u )]} du.Therefore,E sup f ∈F |Z(f )| ≤ εσ 2 + η 0 E sup Au∈Au |N (A u ) -E[N (A u )]| du (90) + 1 η E sup Au∈Au {|N (A u ) -E[N (A u )]| -2εuE[N (A u )]} du.Let now ξ > 0. As (69) holds true for all A ∈ A u , on an event Ω ξ,u such that P [Ω ξ,u ] ≥ 1e -nξ , with α = c[log + |S Au (2n)| + nξ]/n, β = 0, we deduce from Claim 8 that on this event: for all A u ∈ A u ,|N (A u ) -E[N (A u )]| ≤ C log + |S Au (2n)| + nξ n E[N (A u )] + log + |S Au (2n)| +nξ n , and using that √ xy ≤ C/(8εu)x + (2εu/C)y, |N (A u ) -E[N (A u )]| -2εuE[N (A u )] ≤ C ′ log + |S Au (2n)| + nξ n + log + |S Au (2n)| + nξ nεu .

E

  sup Au∈Au |N (A u ) -E[N (A u )]| ≤ C ′′ log + |S Au (2n)| n sup Au∈Au E[N (A u )] + log + |S Au (2n)| n ,andE sup Au∈Au {|N (A u ) -E[N (A u )]| -2εuE[N (A u )]} ≤ C ′′ log + |S Au (2n)| n + log + |S Au (2n)| nεuwhere C ′′ is universal. We now deduce from (90), (A u )] log + |S Au (2n)| du + C ′′ n 1 0 log + |S Au (2n)| du. As ε > 0 and η ∈ (0, 1) are arbitrary, (A u )] log + |S Au (2n)| du + C ′′′ n 1 0 log + |S Au (2n)| du,

  Results for simulated data with n = 50, N rep = 10000.

		Ex 1 Ex 2 Ex 3 Ex 4	Ex 1 Ex 2 Ex 3 Ex 4
	R(1, 2) 0.057 0.078 0.064 0.052	R(1, 5) 0.062 0.063 0.061 0.060
	R(2, 2) 0.057 0.080 0.065 0.051	R(2, 5) 0.059 0.062 0.059 0.060
	R(2,2) R(1,2)	1.00 1.02 1.02 0.99	R(2,5) R(1,5)	0.95 0.98 0.98 1.00
	P equal (2) 0.76 0.75 0.80 0.78 P equal (5) 0.27 0.33 0.32 0.39
	R(1, 3) 0.052 0.056 0.053 0.048	R(1, 6) 0.067 0.068 0.066 0.065
	R(2, 3) 0.047 0.055 0.052 0.047	R(2, 6) 0.065 0.067 0.065 0.065
	R(2,3) R(1,3)	0.91 0.98 0.97 0.99	R(2,6) R(1,6)	0.97 0.99 0.99 1.00
	P equal (3) 0.63 0.64 0.66 0.57 P equal (6) 0.28 0.33 0.33 0.37
	R(1, 4) 0.057 0.058 0.056 0.054	R(1, 7) 0.071 0.072 0.071 0.070
	R(2, 4) 0.052 0.055 0.053 0.053	R(2, 7) 0.070 0.072 0.070 0.071
	R(2,4) R(1,4)	0.92 0.94 0.95 0.98	R(2,7) R(1,7)	0.99 1.00 1.00 1.00
	P equal (4) 0.32 0.40 0.40 0.43 P equal (7) 0.32 0.36 0.35 0.41
	Figure 1. Ex 1 Ex 2 Ex 3 Ex 4	Ex 1 Ex 2 Ex 3 Ex 4
	R(1, 2) 0.055 0.074 0.056 0.035	R(1, 5) 0.038 0.038 0.037 0.033
	R(2, 2) 0.056 0.076 0.057 0.034	R(2, 5) 0.035 0.034 0.035 0.033
	R(2,2) R(1,2)	1.03 1.02 1.02 0.98	R(2,5) R(1,5)	0.92 0.94 0.95 1.00
	P equal (2) 0.63 0.60 0.70 0.80 P equal (5) 0.15 0.18 0.17 0.23
	R(1, 3) 0.034 0.042 0.037 0.023	R(1, 6) 0.041 0.040 0.039 0.037
	R(2, 3) 0.033 0.042 0.036 0.024	R(2, 6) 0.039 0.040 0.038 0.037
	R(2,3) R(1,3)	0.96 1.00 0.98 1.01	R(2,6) R(1,6)	0.95 0.97 0.98 1.00
	P equal (3) 0.71 0.63 0.63 0.57 P equal (6) 0.10 0.15 0.11 0.19
	R(1, 4) 0.036 0.035 0.034 0.028	R(1, 7) 0.044 0.043 0.043 0.40
	R(2, 4) 0.032 0.034 0.032 0.028	R(2, 7) 0.043 0.043 0.042 0.40
	R(2,4) R(1,4)	0.90 0.96 0.94 0.98	R(2,7) R(1,7)	0.96 0.99 0.98 1.00
	P equal (4) 0.29 0.39 0.35 0.33 P equal (7) 0.09 0.11 0.11 0.16
	Figure 2. Results for simulated data with n = 100, N rep = 1000.
				6. Proofs
	6.1. Proof of Lemma 1. Let	√ q = ( √ s +	√ s ′ )/2 and

Appendix A. A uniform exponential inequality.

In this section, we present the key tool to control the error due to the approximation T (s, s ′ ) ≃ T E (s, s ′ ). It is used in the proof of Theorem 3. Its proof is given in Appendix D.

We introduce for any bounded function f ∈ S, the centered random variable

It can also be written as

in framework 1,

1,0 ) -

This variable Z(f ) measures the approximation error of T E (s, s ′ ) by T (s, s ′ ) when f = ψ(s ′ /s). The theorem below allows to control the deviations of Z(f ).

Theorem 11. Let F ⊂ S be a set of functions f such that |f (t)| ≤ 1 for all f ∈ F, t ∈ R. Let A be the collection of sets defined by

Suppose:

• in frameworks 1 and 2 that A is a Vapnik-Chervonenkis class of dimension at most 2d. Moreover, there exists an at most countable set A ′ ⊂ A satisfying the following technical assertion: for all A ∈ A, there exists a sequence (A m ) m≥0 ∈ A ′N such that lim m→+∞ ½ Am (t) = ½ A (t) for every t ∈ R.

• in framework 3, that each set A ∈ A is a union of at most d intervals.

Let, for f ∈ F,

dt in framework 3. Then, there exists for all ξ > 0 an event which holds true with probability larger than 1e -nξ and on which: for all f ∈ F, and ε > 0,

In the above inequality, C ε only depends on ε.

Theorem 11 is well tailored for bounding the risk of a ρ-estimator. Indeed, when f = ψ(s ′ /s), the random variable υ(f ) can be bounded from above as follows: for all s, s ′ ∈ S, υ ψ(s ′ /s) ≤ 4 h 2 (s 0 , s) + h 2 (s 0 , s ′ ) .

Appendix B. Robustness of ρand maximum likelihood estimators

We show here that the behaviour of a ρ-estimator can be very different from that of a maximum likelihood estimator in framework 2.

Proposition 13. Let α > 0, s α (t) = t -1 ½ t≥α be the hazard rate of a Pareto distribution, and the model S = {s α , α > 0}. Suppose that the data are not censored, that is C = +∞ almost surely, and that the target hazard rate is s 0 (t) = f 0 (t)/P (T ≥ t) where f 0 is a mixture of two Pareto distributions defined for η ∈ (0, 1/2) by

t 2 . Then, there exists a universal positive constant c such that the risk of a maximum likelihood estimator s is bounded from below by

By contrast, the risk of a ρ-estimator can be bounded from above by

where C is a universal constant.

The risk bound log 2 n/n of the ρ-estimator is likely not optimal. However, we observe that it does not increase when η runs from 1/2 to 0. This is different for the maximum likelihood estimator: its risk may be made arbitrarily large by playing with η.

Proof of Proposition 13. The survival function G and the hazard rate s 0 of T are given by

The maximum likelihood estimator on S = {s α , α > 0} is s = s α where α = min 1≤i≤n X i .

Let A n be the event on which there exists at least one observation X i smaller than 2η. Then,

Let now t 0 be defined by the relation G(t 0 ) = 2/3 and B n be the event on which n/2 observations X i are not smaller than t 0 . Then, P (B n ) = P (Y ≥ n/2) where Y is binomially distributed with parameters (n, 2/3). Therefore, P (B n ) ≥ 0.74 as n ≥ 3, and

Appendix C. Numerical complexity

We discuss here the numerical complexity of the procedure defined in Section 4.3.

Optimizing a criterion crit(•) on M l is not an easy task as M l is often very large: computing all the crit(m) is numerically prohibitive. Luckily, dynamic programming allows to solve more efficiently the optimization problem when the criterion takes the form

Let K be the collection of intervals with endpoints in {Y (i) , i ∈ {1, . . . , n}}. Let κ be the number of computations needed to compute all the F (K) when K varies among K. Then, we may minimize or maximize crit(•) on M l by a dynamic programming algorithm in at most κ + O(n 2 l) operations. A description of this algorithm may be found in [START_REF] Kanazawa | An optimal variable cell histogram based on the sample spacings[END_REF] and in Section 4.2 of [START_REF] Comte | A new algorithm for fixed design regression and denoising[END_REF].

Here, γ 2 (ŝ m ) is equal to γ 2 (ŝ m ) = K∈m F (K) where

and where ŝK , ŝK ′ are defined in Lemma 2. Algorithms may therefore be used to compute each F (K) and to minimize γ 2 (•).

Suppose first that r = 0. We begin by storing in memory all the ŝK , N (K), M (K) with K ∈ K. This requires at most O(c • n • n2 ) operations where c = 1 in frameworks 1, 2 and where c depends on the Markov processes in framework 3. Let K ∈ K. Since K ∩ K ′ ∈ K, we may compute all the

when K ′ runs among K in at most O(n 2 ) operations. Computing all the F (K) with O(n 2 ) dynamic programming algorithms requires at most O(n 4 l) additional operations. It then remains to minimize γ 2 (•). Finally, the number of operations needed to define ŝm is at most O(n 2 (cn + n2 l)).

When r ≥ 1, the procedure is similar, although slower. We define for K, K ′ ∈ K, k 1 (respectively k 2 ) as the maximum number of operations needed to know ŝK (respectively K∩K ′ ŝK dM ). We begin by storing in memory all the ŝK , all the atoms of N on K, and all the K∩K ′ ŝK dM . This requires at most O((

We store all the T (ŝ K ½ K∩K ′ , ŝK ′ ½ K∩K ′ ), and use O(n 2 ) dynamic programming algorithms to know all the F (K). A last algorithm is used to minimize γ 2 (•). Finally, the minimization of γ 2 (•) may be performed in at most O(n 4 ( l

The estimator ŝ m may therefore be computed in practice in favorable situations. Numerical simulations are also possible (see Section 5). Unfortunately, the preceding bounds may be quite large, especially when n is large. They are, however, much smaller than the number of computations we would need to perform to minimize the first criterion γ(•) by a naive algorithm that would require to know every T (ŝ m , ŝm ′ ).

Remark. We may also optimize a criterion of the form (68) when M l is replaced by M ≤ l = {m ∈ M, |m| ≤ l}. This only increases the computational cost of the algorithm by O( l). Let, for each A ∈ B(R), Q(A) be a random variable such that Q(•) defines a measure on (R, B(R)). Let f be a bounded function and

We now aim at controlling the deviations of Z Q . We begin by showing that this issue boils down to a suitable control of the deviations of Q

Suppose that sup A∈A E[Q(A)] ≤ 1, that there exist non-negative numbers α, β, and an event on which: for all A ∈ A,

Then, on this event, for all f ∈ F,

where

The constant C is universal whereas C ε only depends on ε.

The proof of this result is delayed to Section D.2 below. As N is an empirical measure, we can prove that (69) is valid with Q = N on an event of high probability by using, for example, the Vapnik-Chervonenkis inequalities for relative deviations. More precisely: Lemma 9. Let A ⊂ B(R) be a collection of Borel sets and S A (2n) be the Vapnik-Chervonenkis shatter coefficient of A defined by S A (2n) = max t 1 ,...,t 2n ∈R |{{t 1 , . . . , t 2n } ∩ A, A ∈ A}| .

Suppose that there exists an at most countable set A ′ ⊂ A such that: for all A ∈ A, there exists a sequence (A m ) m≥0 ∈ A ′N satisfying lim m→+∞ ½ Am (t) = ½ A (t) for every t ∈ R.

Let now ξ > 0. Then, there exist a universal constant c 1 and an event Ω ξ,1 such that P [Ω ξ,1 ] ≥ 1e -nξ and on which (69) holds for Q = N and for all A ∈ A with α = c 1 [log + |S A (2n)| + nξ]/n and β = 0.