Clément Marteau

Mathieu Sart

DECONVOLUTION FOR SOME SINGULAR DENSITY ERRORS WITH RESPECT TO THE L 1 LOSS CL ÉMENT MARTEAU AND MATHIEU SART

come

Deconvolution for some singular density errors with respect to the L 1 loss

Introduction

Let Y 1 , . . . , Y n be n independent and identically distributed real valued random variables defined on an abstract probability space (Ω, E , P ). We assume that each random variable Y i can be written as (1)

Y i = X i + ε i , i ∈ {1, . . . , n}
where for all i ∈ {1, . . . , n}, X i denotes a random variable admitting a density f 0 with respect to the Lebesgue measure. The variable ε i denotes measurement errors, independent of X i , with known density q. Our aim is to estimate f 0 from the indirect observations Y 1 , . . . , Y n . This turns to be a deconvolution problem, the density of the Y i 's being the convolution product f 0 * q.

Deconvolution in a statistical context has been at the core of several investigations in the literature. We refer to, e.g., [START_REF] Meister | Deconvolution problems in nonparametric statistics[END_REF] for a comprehensive introduction to this topic. Over the last decades, several approaches have been proposed. For instance, kernel procedures have been designed, taking advantage of the convolution structure in the Fourier domain. We mention a seminal contribution by [START_REF] Fan | On the optimal rates of convergence for nonparametric deconvolution problems[END_REF] who establishes rates of convergence under smoothness assumptions on the target density f 0 . Several extensions and improvements have then been obtained, including in particular discussions regarding an adaptive choice of the bandwidth. We refer, e.g., to [START_REF] Delaigle | Bootstrap bandwidth selection in kernel density estimation from a contaminated sample[END_REF] for bootstrap bandwidth selection, [START_REF] Butucea | Adaptivity in convolution models with partially known noise distribution[END_REF] or [START_REF] Comte | Data-driven density estimation in the presence of additive noise with unknown distribution[END_REF] when the error density q is unknown, [START_REF] Dedecker | Minimax rates of convergence for Wasserstein deconvolution with supersmooth errors in any dimension[END_REF] for rates of convergence using the Wasserstein metric, or [START_REF] Rebelles | Structural adaptive deconvolution under L p -losses[END_REF][START_REF] Ov Lepski | Oracle inequalities and adaptive estimation in the convolution structure density model[END_REF] for adaptation under L p -losses. Alternatively, several methods based on the minimization of a (penalized) criterion over a given family have been carried out. Typically, given a collection of candidates for f 0 , one would like to find the one leading to the smallest quadratic risk. This optimal element (in a sense that should be made precise) is then approximated as a minimizer of a functional, playing the role of a risk estimator. This functional is possibly penalized to include constraints on the target, often in an adaptive way. We refer for instance to [START_REF] Comte | Penalized contrast estimator for adaptive density deconvolution[END_REF] for projection methods and to [START_REF] Mai | The dictionary approach for spherical deconvolution[END_REF] where the performance of a dictionary based method is investigated in a spherical context. Other authors have extended wavelet approaches to the deconvolution model. The idea is to take advantage of the density representation property in a wavelet basis. The coefficients of this decomposition must then be estimated and sometimes thresholded in an appropriate way, see [START_REF] Pensky | Adaptive wavelet estimator for nonparametric density deconvolution[END_REF][START_REF] Fan | Wavelet deconvolution[END_REF][START_REF] Cavalier | Multiscale density estimation with errors in variables[END_REF][START_REF] Lounici | Global uniform risk bounds for wavelet deconvolution estimators[END_REF].

The aforementioned references assess the quality of their estimators by means of L p -losses, with p larger than 1 (except [START_REF] Fan | On the optimal rates of convergence for nonparametric deconvolution problems[END_REF] and [START_REF] Ov Lepski | Oracle inequalities and adaptive estimation in the convolution structure density model[END_REF]). In the present paper, we focus to the case p = 1. The loss then does not only measure the distance between the estimator and the density f 0 , but also the distance between the two underlying probability measures.

We restrict our study to a moderately ill-posed deconvolution problem with small degree of ill-posedness. More precisely, we assume that the Fourier transform q ⋆ of q does not vanish and that |q ⋆ (t)| -1 is of the order of |t| β for large values of t. The parameter β should be smaller than 1/2, which indicates in some sense that q is singular enough, or in other terms, that the framework is not so far away from the direct setting (which would correspond to β = 0). As noticed by [START_REF] Meister | Deconvolution problems in nonparametric statistics[END_REF][START_REF] Dattner | On deconvolution of distribution functions[END_REF], this condition makes it possible the consistent estimation of the distribution function without further assumptions on f 0 . This last problem is indeed closely related to the estimation of a density using the L 1 loss. We refer to [START_REF] Devroye | Combinatorial methods in density estimation[END_REF] for more informations regarding this issue.

In direct estimation, there exist general procedures that lead to both optimal and robust estimators. We are thinking in particular to methods based on robust tests or like-minded approaches such as those described in [START_REF] Birgé | Approximation dans les espaces métriques et théorie de l'estimation[END_REF][START_REF] Birgé | Model selection via testing: an alternative to (penalized) maximum likelihood estimators[END_REF][START_REF] Devroye | Combinatorial methods in density estimation[END_REF][START_REF] Baraud | A new method for estimation and model selection: ρ-estimation[END_REF]. There does not seem to be, in the literature of deconvolution, a general-purpose estimation procedure. In this paper, we present a first attempt by proposing a new estimation procedure in line with [START_REF] Devroye | Combinatorial methods in density estimation[END_REF]. It does not lead to risk bounds as general as in the direct case, but at least, it already yields new results in the deconvolution setting. For each suitable collection F of densities (named model in the sequel), we define an estimator f ∈ F and get a non-asymptotic upper-bound for the L 1 risk d 1 (f 0 , f ) of the estimator, both in expectation and with high probability. We then deduce new upper bounds of the minimax risks for some collections corresponding to parametric, smoothness or shape constraints on f 0 as described below.

We obtain rates of convergence when f 0 is multimodal, or when f 0 is (piecewise) concave/convex. In both cases, only the number of modes or pieces must be known by the statistician. Their locations may be completely unknown. These rates are moreover better for some particular densities of F . They become, for instance, nearly parametric when f 0 is piecewise constant and when F models a multimodal density. This phenomenon is similar to the one which occurs for the Grenander estimator in direct estimation, see [START_REF] Birge | The Grenander estimator: a nonasymptotic approach[END_REF]. Let us mention that very few attempts have been conducted to deal with shape constraints in density deconvolution, the only ones we know about are [START_REF] Carroll | Testing and estimating shape-constrained nonparametric density and regression in the presence of measurement error[END_REF][START_REF] Schmidt-Hieber | Multiscale methods for shape constraints in deconvolution: confidence statements for qualitative features[END_REF].

We consider also the case where the target f 0 belongs to a bounded set F = B α p,∞ (R) of a Besov space. Here, p may be very small and in particular smaller than 1, which allows to take into account spatially inhomogeneous smoothness. Moreover, f 0 may not be continuous nor bounded as our condition of α is milder than α > 1/p. We then get a generalization of the minimax rates of [START_REF] Fan | On the optimal rates of convergence for nonparametric deconvolution problems[END_REF] which were restricted to Hölder balls (up to a logarithmic factor). We are not aware of many references in the literature mixing Besov spaces with p < 1 and L 1 loss in density deconvolution. For other losses or other smoothness assumptions, see [START_REF] Fan | Wavelet deconvolution[END_REF][START_REF] Comte | Penalized contrast estimator for adaptive density deconvolution[END_REF][START_REF] Comte | Anisotropic adaptive kernel deconvolution[END_REF][START_REF] Ov Lepski | Oracle inequalities and adaptive estimation in the convolution structure density model[END_REF] and the references therein. We also give an example of parametric model to illustrate the flexibility of our approach. We show that our estimator achieves a (near) parametric rate when f 0 is known, up to a location and scale parameter. It is worth mentioning that the method of maximum likelihood does not work here, and that ours is robust to model errors. Similar results are shown for the model F composed of all piecewise polynomial densities on at most d intervals (these intervals are not set by the model). Our rates may then be related to that obtained in [START_REF] Frick | Asymptotic laws for change point estimation in inverse regression[END_REF] under known bounds on f 0 ∞ in inverse regression. Their estimator, however, does not share same robustness properties than ours (which are crucial to deal with spatial inhomogeneity as in the previous paragraph). Although our estimator is piecewise polynomial in that case, it is not constructed to locate the possible discontinuities of the density. This other problem is studied for instance in [START_REF] Michael | Optimal change-point estimation in inverse problems[END_REF][START_REF] Goldenshluger | Optimal change-point estimation from indirect observations[END_REF][START_REF] Goldenshluger | Change-point estimation from indirect observations. I. Minimax complexity[END_REF]. This paper is organized as follows. In Section 2, we present an elementary approach based on an histogram-type estimator. We carry out our main results on shape, smooth and parametric constraints in Section 3. The description of our general procedure is deferred to Section 4. Section 5 gathers the proofs. To reduce the size of the paper, we study the problem of minimax estimation of a decreasing density in Appendix A. A lower bound on the minimax rate for concave densities is given in Appendix B. We carry out in Appendix C two elementary approximation lemmas that were required in our proofs.

Throughout the paper, we will use the following notation. The terms X, Y, ε denote generic random variables having same law than respectively X i , Y i and ε i . We will sometimes write A f instead of A f (x) dx to shorten the formulas and omit the set A when A = R. We denote the Fourier transform of a integrable, or square integrable, function f by f ⋆ . The following definition is used when f is integrable:

f ⋆ (t) = e itx f (x) dx, for all t ∈ R. The L 1 distance between two integrable functions f 1 , f 2 ∈ L 1 (R) is denoted by d 1 (f 1 , f 2 ) = R |f 1 (x) -f 2 (x)| dx. For all F ⊂ L 1 (R), and f ∈ L 1 (R), we set d 1 (f, F ) = inf g∈F d 1 (f, g).
The complex conjugate of a number x is x. The notation |I| may refer either to the Lebesgue measure or the cardinality of I. The supremum norm of a function f is f ∞ = sup x∈R |f (x)| and its derivative (provided it exists) is denoted by f ′ . The notations c, c ′ , C, C ′ , . . . are used for quantities that may change from line to line. They are usually constants (that is numbers), but may sometimes depend on some parameters. In that case, the dependency will be specified in the text.

Preliminaries

This section gathers some preliminary results. We introduce and comment our main assumption on the error density q. Then, we discuss the estimation of the probability that the variable X belongs to a given set and use the obtained results to design a first histogram estimator.

2.1. Assumptions on the error density. All along the paper, we will assume that the variables ε i involved in the model (1) admits a density q satisfying the following requirement. This assumption will always assumed to be met in the next sections (except in Proposition 4 below, but this will be specified).

Assumption 1. The Fourier transform q ⋆ of q does not vanish. Moreover there exist three constants κ 1 , κ 2 and β ∈ (0, 1/2) such that for all t ∈ R,

(2) |q ⋆ (t)| -2 ≤ κ 1 + κ 2 |t| 2β .
Such kind of assumption is quite classical in the statistical literature (see, e.g., [START_REF] Meister | Deconvolution problems in nonparametric statistics[END_REF]). The fact that q ⋆ is not allowed to vanish entails in particular that f ⋆ 0 can be recovered from (f 0 * q) ⋆ at any frequency and hence ensures that the problem is identifiable. Such a constraint is for instance satisfied when q is even and its derivative q ′ on (0, +∞) exists and is strictly increasing (see [START_REF] Oliver | On positivity of fourier transforms[END_REF]). The difficulty (expressed for instance in terms of convergence rates) of the deconvolution problem is often measured through the behavior of q ⋆ (t) for large value of t. The condition (2) indicates that q ⋆ has a polynomial behavior: the deconvolution problem is said in this case to be mildly ill-posed. We restrict our attention to the specific case where the polynomial exponent β is smaller than 1/2. The following proposition provides examples of densities satisfying such a requirement. In particular, such examples correspond to densities having a singularity on a given point which appears to be of first mathematical interest. The proof of Proposition 1 is postponed to Section 5.2.

Proposition 1. Let ϕ : R → R be a map such that ϕ(0) is positive and whose derivative exists, is bounded and integrable on R. Let q be a density of the form q(x) = |x| β-1 ϕ(x) with β ∈ (0, 1/2). Then if q ⋆ does not vanish, q satisfies Assumption 1.

Estimation of a probability.

Our procedures are heavily based on probability estimations of the form P(X ∈ I) = I f 0 for some I ⊂ R. The estimation of these terms seems to be tricky when I is only assumed to be a Borel set, but is more easy when I is an interval, or more generally a union of intervals. This has been studied for instance in [START_REF] Meister | Deconvolution problems in nonparametric statistics[END_REF][START_REF] Dattner | On deconvolution of distribution functions[END_REF], and we will adopt here the estimation strategy of [START_REF] Meister | Deconvolution problems in nonparametric statistics[END_REF]. Note that the frontier β = 1/2 for the index involved in (2) plays an important role for this problem.

In the following, for any d ∈ N ⋆ , we denote by I d the collection of unions of at most d intervals with finite length. For any I ∈ I d , the function φ I : t → ½ ⋆ I (t) × [q ⋆ (t)] -1 belongs to L 2 (R) according to Assumption 1. Its Fourier transform φ ⋆ I is therefore a square integrable function almost everywhere finite. It is also real-valued as φ I is Hermitian. Since Y is absolutely continuous with respect to the Lebesgue measure, the random variable Z(I) = (1/(2π))φ ⋆ I (Y ) is real-valued (and finite) on an event of probability 1. In the remaining part of the paper, the random variables can be defined almost surely without specifying it again. They can always be modified on zero probability events without changing our results.

When f 0 * q ∞ is finite, Z(I) has moments up to 2th order, see Proposition 2 below. We may moreover apply Plancherel isometry to get

E[Z(I)] = φ ⋆ I (y)(f 0 * q)(y) dy = 1 2π φ I (t)f ⋆ 0 (t)q ⋆ (t) dt = 1 2π ½ ⋆ I (t) f ⋆ 0 (t) dt = P(X ∈ I), (3)
where the last equality comes from Plancherel isometry when f 0 ∈ L 2 (R) and from an additional density argument otherwise, see Section 5.3. We deduce that (4)

Z n (I) = 1 2πn n j=1 φ ⋆ I (Y j )
is an unbiased estimator for the term P(X ∈ I). A control on its variance is given by the proposition below. Its proof is postponed to Section 5.4.

Proposition 2. For all union of at most d intervals I ∈ I d , we have Z(I) ∈ R and

E[(Z(I)) 2 ] ≤ f 0 * q ∞ κ 1 d|I| + c β κ 2 d 1+2β |I| 1-2β , (5)
where c β only depends on β.

2.3. Estimation of f 0 using histograms. In this paper, we are interested in the estimation of the density f 0 of the X i rather than a probability in itself. For pedagogical reasons, we present below an histogram estimator and give a L 1 risk bound. The following results should be seen as a foretaste of our main contributions that will be presented in Sections 3 and 4.

Let m be a given finite collection of size |m| of disjoint intervals of finite and positive lengths. The integral of f 0 over each interval I included in m can be estimated thanks to the expression (4). Gathering all these estimations, we can define an histogram estimator fm of f 0 as follows:

(6) fm = I∈m Z n (I) |I| ½ I .
By using Proposition 2, we get a control (in expectation) of its L 1 -risk as displayed in the following proposition. The proof is deferred to Section 5.5.

Proposition 3. For any finite collection m of disjoint intervals (of positive and finite lengths), let

(7) F m = I∈m α I ½ I , (α I ) I∈m ∈ [0, +∞) |m| , I∈m α I |I| = 1
be the collection of piecewise constant densities on m. Then,

E d 1 f 0 , fm ≤ 2d 1 (f 0 , F m ) + f 0 * q ∞ κ 1 ℓ|m| + c β κ 2 ℓ 1-2β |m| 1+2β n (8)
where ℓ = I∈m I . This upper bound is non-asymptotic and shares similarities with results obtained in the direct case (which would roughly correspond to β = 0). In particular, our bound is composed of a bias term d 1 (f 0 , F m ) and an estimation component. The supremum norm of f 0 * q that appears in this inequality can always be related to a suitable L s norm of f 0 . Indeed, by Young's inequality,

f 0 * q ∞ ≤ inf s≥1 f 0 s q s/(s-1) .
Since q is not bounded, we cannot get an upper bound of f 0 * q ∞ independent of f 0 . Nevertheless, we always have the rough upper-bound f 0 * q ∞ ≤ f 0 ∞ as q is a density. More generally, if q satisfies our conditions of Proposition 1 with a function ϕ that decreases fast enough at infinity, q s/(s-1) is finite as soon as s > 1/β.

We now give some direct illustrations of this result. First, when f 0 is piecewise constant on the collection m, the bias term in (8) vanishes and the estimator fm achieves the expected rate 1/ √ n. Second, when f 0 is compactly supported on [0, 1] and is smooth, the bias term can be controlled. For instance, if f 0 is Hölder with regularity α ∈ (0, 1], we may choose m as a regular partition of [0, 1] of adequate size to get the rate of convergence n -α/(2β+2α+1) . This rate cannot be improved in general, see [START_REF] Fan | On the optimal rates of convergence for nonparametric deconvolution problems[END_REF]. Thirdly, we can deal with the estimation of f 0 under monotonic constraints. Choosing m in an appropriate way allows then to obtain the optimal rate of convergence n -1/(2β+3) . For the sake of clarity, this result and its associated minimax lower bound are displayed in Appendix A.

According to the results presented above, the histogram estimator fm introduced in (6) leads to optimal rates of convergence in several situations. This estimator is particularly simple and can easily be computed in practice. Nevertheless, this approach has two major defects. The first is that the choice of m should be made according to the data. The second is that a piecewise constant estimator -no matter the choice of m -cannot be rate optimal under other assumptions of interest (which is the case, for instance, when α is larger than 1 in the Hölder case). 2.4. About higher values of β. In this paper, only the case β < 1/2 is studied. The reason is that the results may be quite different when β is larger. Consider for instance a partition m of [0, 1] into intervals, and the class

F m (2) = {f ∈ F m , f * q ∞ ≤ 2} (9)
composed of piecewise constant densities. As described above, the histogram estimator fm satisfies sup

f 0 ∈Fm(2) E d 1 (f 0 , fm ) ≤ c |m| β+1/2 √ n , ( 10
)
where the multiplicative factor c depends on β, κ 1 , κ 2 only. It is noteworthy that this upperbound depends on the partition only through its cardinal and not on the thinness of its elements. It turns out that such a result may be incorrect for larger values of β. The following proposition is the only one in this paper that does not suppose Assumption 1. It is proved in Section 5.6. Proposition 4. Suppose that q is bounded and there exists τ > 0 such that for all x > 0,

q(t -x) -q(t) 2 dt ≤ τ 2 x 2 . ( 11
)
Consider n > 2/(25τ 2 ) and the partition m of size 3 of [0, 1] defined by

m = 0, 1/ τ √ 50n , 1/ τ √ 50n , 2/ τ √ 50n , 2/ τ √ 50n , 1 .
Then, inf

f sup f 0 ∈Fm(2) E d 1 (f 0 , f ) ≥ 0.14 min {1, 1/ q ∞ } ,
where the infimum is taken over all possible estimators of f 0 .

The assumption in this proposition requires that √ q is sufficiently regular. An example is the Laplace distribution that satisfies (11) with τ 2 = 1/4. For other examples, or conditions that imply (11), we refer to [START_REF] Ibragimov | Has'minskii. Statistical estimation-asymptotic theory[END_REF]. Note that this result does not apply when β < 1/2 as q must be bounded.

Non-asymptotic risk bounds

We propose below a new estimation procedure inspired by both the median of mean principle and the combinatorial method. It allows to consider a wide variety of different problems and to obtain more general risk bounds than those displayed in Section 2. This procedure should be essentially considered as a tool leading to new theoretical results rather than a method for practical and applied statistical analysis. For the ease of exposition, we concentrate our attention on the associated results and defer the presentation of the procedure to Section 4.

3.1. Assumption and main result. In the following, F denotes a collection of densities given by the statistician. This collection can be seen as a translation of the a priori available knowledge on f 0 . We stress that f 0 should not necessarily belong to F but should at least be well approximated, in a sense which will be made precise later on, by some elements of this set. Concerning the set F , we consider the following assumption.

Assumption 2. There exist for every density f ∈ F two integers ℓ f , d f such that:

• For all f ∈ F , f is compactly supported on [-ℓ f , ℓ f ]. • For all f, g ∈ F , the set [f > g] = {x ∈ R, f (x) > g(x)} is a union of at most min{d f , d g } intervals.
Moreover, there exists an at most countable collection F ⊂ F such that: for all f ∈ F and ε > 0, there exists

f ′ ∈ F such that d 1 (f, f ′ ) ≤ ε, d f ′ ≤ d f and ℓ f ′ ≤ ℓ f .
As we will see in the forthcoming sections, this assumption is flexible enough to deal with several examples of interest. The existence of F is required for technical reasons, including in particular measurability restrictions. Under this assumption, it is possible to design an estimator f ∈ F (defined as a minimizer of a criterion (21) in Section 4) whose performances are given by the following theorem.

Theorem 5. Let ξ ≥ 1 and F be a model fulfilling Assumption 2. There exists an estimator f ∈ F satisfying

d 1 (f 0 , f ) ≤ 3 inf f ∈F d 1 (f 0 , f ) + c f 0 * q ∞ (κ 1 ℓ f d f + c β κ 2 ℓ 1-2β f d 2β+1 f ) (ξ + log(ℓ f d f )) n + 1 n (12)
on an event having probability 1e -ξ . Moreover, when ξ = log n,

E d 1 (f 0 , f ) ≤ 3 inf f ∈F    d 1 (f 0 , f ) + c ′ f 0 * q ∞ (κ 1 ℓ f d f + c β κ 2 ℓ 1-2β f d 1+2β f ) log(ℓ f n) n + 1 n    .
In the above inequalities, c, c ′ are universal constants and c β only depends on β.

It can be noticed that the above result, whose proof can be found in Section 5.12, applies in particular to the collection

F = F m introduced in (7) with ℓ f = | ∪ I∈m I|, d f = |m|.
In such a case, our estimator f leads to the same expectation bound (up to a log term) obtained in Proposition 3 for the histogram procedure. The main interest of this result is that it allows to cope with several alternative models that are described in the forthcoming sections.

Piecewise monotone densities.

In this section, we explain how to estimate a multimodal density f 0 in our deconvolution setting.

We consider r ≥ 1 and introduce the family M r that gathers all the collections m of size r of the form m = {[x 1 , x 2 ], (x 2 , x 3 ], (x 3 , x 4 ], . . . , (x r , x r+1 ]} , (13) where x 1 < x 2 < • • • < x r+1 are r + 1 real numbers (with the convention that m = {[x 1 , x 2 ]} when r = 1). We then define the collection F r of piecewise monotone functions by Note that compactly supported densities that are monotone on its support belongs to F 1 . The ones that are multimodal with r modes belongs to F 2r .

We may estimate such densities by applying Theorem 5 to a suitable subset of F r . More precisely, we introduce for k ≥ 1, the collection

P k = I∈m α I ½ I , where m ∈ M k , α I ∈ [0, +∞), I∈m α I |I| = 1
of piecewise constant densities based on collections of M k . According to Proposition 3 of [START_REF] Baraud | ρ-estimators for shape restricted density estimation[END_REF], Assumption 2 is fulfilled for the set

F = ∞ k=1 P k ∩ F r , (15)
with d f = 3(k + r + 5)/2 for all f ∈ P k ∩ F r . This enables Theorem 5 to be applied.

In the following, to measure the variations of a function f , we introduce for any interval I,

V I (f ) = sup x,y∈I |f (x) -f (y)| . ( 16
)
We then set for all f ∈ F r ,

L 1 (f ) = inf m∈Mr, f = I∈m f I ½ I I∈m log 1/2 (1 + |I|V I (f I ))
2 .

An application of Theorem 5 leads to the following result. Its proof can be found in Section 5.7.

Theorem 6. Consider r ≥ 1. There exists an estimator f ∈ F r satisfying for all integer ℓ and all f 0 such that

f 0 ½ [-ℓ,ℓ] ∈ F r , E d 1 (f 0 , f ) ≤ C L 1 (f 0 ½ [-ℓ,ℓ] ) (2β+1)/(2β+3) c 1 f 0 * q ∞ log n n 1/(2β+3) +c 1/2 2 L 1 (f 0 ½ [-ℓ,ℓ] ) × c -1/2 1 1/(2β+3) f 0 * q ∞ log n n (β+1)/(2β+3) + c 3 f 0 * q ∞ log n n 1/2 + 1 n + [-ℓ,ℓ] c f 0 ,
where C is a universal constant, where c 1 , c 2 , c 3 are defined by

c 1 = (1 + (log ℓ)/(log n))κ 2 c β ℓ 1-2β , c 2 = (1 + (log ℓ)/(log n))κ 1 ℓ, c 3 = c 1 r 1+2β + c 2 r,
and where c β only depends on β.

The term L 1 (f 0 ½ [-ℓ,ℓ]
) provides a description of the variation of the density f 0 on [-ℓ, ℓ]. In particular, when the f I admit slow variation on small intervals I, this quantity appears to be small. The extreme case is obtained when

f 0 is piecewise constant over r intervals included in [-ℓ, ℓ]. In such a case, L 1 (f 0 ½ [-ℓ,ℓ] ) = 0 and E d 1 (f 0 , f ) ≤ C c 3 f 0 * q ∞ log n n .
Up to the logarithmic term, this bound exactly corresponds to the one that can be obtained with our histogram estimator introduced in the previous section. However, the partition over which the target density is piecewise constant is completely unknown.

For a compactly supported density which is not piecewise constant, the dominating term in the above bound is the first displayed in the right-hand side. This suggests a rate of convergence for our estimator of the order of ((log n)/n) 1/(2β+3) . Our estimator explicitly depends on r but does not require the knowledge of other parameters about the density. In particular, the modes of the target f 0 are not supposed to be available.

Our result also applies to the situation where the target density f 0 is not compactly supported, but admits a tail that decreases fast enough. In that case, optimizing our risk bound with respect to ℓ yields:

Corollary 1. Suppose that f 0 is a bounded multimodal density with r modes. When there is p > 0 such that [-ℓ,ℓ] c f 0 ≤ e -pℓ for all ℓ, the estimator f defined on F r satisfies when n is large enough

E d 1 (f 0 , f ) ≤ C (log log n) (2β+1)/(2β+3) (log n) 2(1-β)/(2β+3) n -1/(2β+3) ,
where C only depends on κ 2 , β, p, r and f 0 * q ∞ . Hence, provided the density f 0 admits an exponential moment, we retrieve the same rates as in the compact case, up to some logarithmic terms. We point out that the estimator is adaptive with respect to the value of p.

Piecewise concave-convex densities.

We now consider stronger assumptions on the shape of f 0 in order to get faster rates of convergence. More precisely, we consider the estimation of a density f 0 that is piecewise concave-convex on its support.

We define for r ≥ 1,

G r = I∈m f I ½ I ,
F = ∞ k=1 (Q k ∩ G r ) , (18)
satisfies Assumption 2 with d f = 3(k + r + 5) for all f ∈ Q k ∩ G r . We may thus apply Theorem 5 to this model.

A convex or concave function on a given interval I is not necessarily derivable. It is however derivable on both the left and right-hand sides. Such a derivative (on the right or the left, according to the reader's choice) will be denoted as f ′ . Then, we set for f ∈ G r ,

L 2 (f ) = inf m∈Mr, f = I∈m f I ½ I I∈m log 2/3 1 + |I| 2 V I (f ′ I ) 3 ,
where I denotes the interior of I and V I (•) was introduced in (16). We apply Theorem 5 to the above collection F and deduce the following theorem whose proof is deferred to Section 5.7.

Theorem 7. Consider r ≥ 1. There exists an estimator f ∈ G r satisfying for all integer ℓ and all f 0 such that

f 0 ½ [-ℓ,ℓ] ∈ G r , E d 1 (f 0 , f ) ≤ C L 2 (f 0 ½ [-ℓ,ℓ] ) (2β+1)/(2β+5) c 1 f 0 * q ∞ log n n 2/(2β+5) +c 1/2 2 L 2 (f 0 ½ [-ℓ,ℓ] ) × c -1/2 1 1/(2β+5) f 0 * q ∞ log n n (β+2)/(2β+5) + c 3 f 0 * q ∞ log n n 1/2 + 1 n + [-ℓ,ℓ] c f 0 ,
where C is a universal constant, where c 1 , c 2 , c 3 are defined by

c 1 = (1 + (log ℓ)/(log n))κ 2 c β ℓ 1-2β , c 2 = (1 + (log ℓ)/(log n))κ 1 ℓ, c 3 = c 1 r 1+2β + c 2 r,
and where c β only depends on β.

This result is hence very close to the one obtained for multimodal functions. The main differences are contained in the value of the exponents and in the way the variations of f 0 are measured on [-ℓ, ℓ].

Provided the target density f 0 is compactly supported and convex (or concave) on its support, we can deduce from the previous bound that for n large enough,

E d 1 (f 0 , f ) ≤ C((log n)/n) 2/(2β+5) ,
for an appropriate value C (not depending on n). This rate is better than the one obtained in Section 3.2 under a monotonicity constraint. It turns out that this rate is the expected one, up to the logarithmic factor, see Proposition 15 in Appendix B.

When f 0 is piecewise linear on r intervals, namely when

f 0 ∈ Q r , then L 2 (f 0 ½ [-ℓ,ℓ] ) = 0
for ℓ large enough. The estimation rate then becomes automatically parametric (up to a logarithmic term). By the way, our estimator is adaptive with respect to the intervals on which f 0 is linear.

Similarly to the discussion displayed in the previous section, this result can be extended to the situation where the target function is not compactly supported, but admit a fast decreasing tail. Such a situation is described in the following corollary.

Corollary 2. Suppose that f 0 is either convex or concave on each interval of a finite partition of R of size r with bounded (left-hand) derivative. When there is p > 0, such that [-ℓ,ℓ] c f 0 ≤ e -pℓ for all ℓ, the estimator f defined on G r satisfies when n is large enough,

E d 1 (f 0 , f ) ≤ C(log log n) (4β+2)/(2β+5) (log n) 4(1-β)/(2β+5) n -2/(2β+5) ,
where C depends on r, p, κ 2 , β, f 0 * q ∞ only.

Piecewise polynomial densities and application to

Besov semi-balls. In the previous results, the rate of convergence appears to be parametric (up to a logarithmic term) when the target density f 0 is piecewise constant (or linear) on a given number of intervals, that is when

f 0 ∈ P r ⊂ F r (or f 0 ∈ Q r ⊂ G r ).
It is in fact possible to extend these results to the situation where f 0 is piecewise polynomial.

We introduce the set F = F k,r of piecewise polynomial densities defined by

F k,r = I∈m f I ½ I , where m ∈ M k and f I is a polynomial function of degree at most r such that f = I∈m f I ½ I is a density . According to [Sar21], Assumption 2 is fulfilled for F = F k,r with d f = (r + 2)(k + 2
). An application of Theorem 5 hence shows: Theorem 8. For all k, r, there exists an estimator f ∈ F k,r such that for all f ∈ F k,r , and ℓ ≥ 1,

E d 1 (f 0 , f ) ≤ 3d 1 (f 0 , f ½ [-ℓ,ℓ] ) + C f 0 * q ∞ (κ 1 ℓk(r + 1) + c β κ 2 ℓ 1-2β (k(r + 1)) 1+2β ) log(ℓn) n + 3 n .
where C is universal and where c β only depends on β.

We get therefore a parametric rate of convergence when the target is piecewise polynomial (up to a logarithmic term). Besides, the knowledge of the intervals on which f 0 is polynomial is not necessary to define the estimator. This theorem can be applied to estimate smooth functions (in a sense which is made precise below).

Let α > 0, p > 0 and f be a compactly supported map on [0, 1]. We set r as the smallest integer larger than α, and define

∆ r h f (t) = r k=0 r k (-1) r-k f (t + kh), ω p (f, x) = sup 0<h≤x [0,1-rh] |∆ r h f (t)| p dt 1/p , and |f | p,∞ = sup x∈(0,1) ω p (f, x) x α .
We then define the Besov semi-ball B α p,∞ (R) as the set of compactly supported densities on

[0, 1] such that |f | p,∞ ≤ R.
The functions contained in Besov spaces are smooth and can be well approximated by piecewise polynomial functions. Besov semi-balls as defined above appears to be a generalization of Hölder semi-balls. From the point of view of approximation theory, there is a major difference between these two sets. Hölderian maps can be suitably approximated by piecewise polynomial functions on regular grids. This is no longer true for Besov spaces when p is small. In the later case, the grid over which a map is well approximated depends on the map itself (the grid may be locally alternatively very thin or quite rough). This explain in particular the fact that non-parametric estimation is easier over Hölder sets than over Besov sets, considering smaller values of p leading to additional technical issues.

We now use Theorem 8 and approximation results of [START_REF] Ronald | Degree of adaptive approximation[END_REF] to get an upper bound on the maximal risk over the collection

B α p,∞ (R, M ) = f ∈ B α p,∞ (R), f * q ∞ ≤ M .
More precisely, we prove in Section 5.8:

Corollary 3. Let p, R, M > 0 and α > (1/p -1) + . Then, if r ≥ α + 1 and if k is suitably chosen, the estimator f ∈ F k,r defined in Theorem 8 satisfies: for all f 0 ∈ B α p,∞ (R, M ), E d 1 (f 0 , f ) ≤ C R (2β+1)/(2β+2α+1) M log n n α/(2β+2α+1) + M log n n 1/2 + 1 n ,
where C only depends on κ 1 , κ 2 , β, p, r, α. The choice of k depends on α, β, p, R, M and n only.

In the literature of density deconvolution, many results can be found regarding the estimation of f 0 under regularity constraints. This no longer seems to be true when the L 1 loss is considered, and the above rate is, as far as we know, new under our assumptions. Note that we do not work in a standard framework since the error density q is neither squared integrable nor bounded. Moreover, p is allowed to be arbitrarily small, and in particular smaller than 1. Our result is therefore much better than the one that could have been achieved if the model were composed of piecewise polynomial functions on a regular grid of [0, 1] only.

The above maximum risk does not relate to the whole semi-ball B α p,∞ (R) but only to the smaller part B α p,∞ (R, M ). However, these two sets coincide in some cases. It follows from standard results about the inclusion of Besov spaces into L s spaces that f s ≤ c( f p + R) for all f ∈ B α p,∞ (R) and α > 1/p -1/s. Using this result with s = ∞ and noticing that f p ≤ 1 when p < 1 as f is a density, we deduce that f ∞ ≤ c( f p + 1). By using Young's inequality, we deduce that the set B α p,∞ (R, M ) coincides with the semi-ball B α p,∞ (R) when M = c(R + 1) and α > 1/p, p ∈ (0, 1). Moreover, when the conditions on q described page 6 are met, f * q ∞ ≤ c ′ f s for all s > 1/β and c ′ depending only on q, s. By choosing s appropriately, and by applying the reasoning of the previous paragraph,

B α p,∞ (R) = B α p,∞ (R, c ′′ (1 + R)) when α > 1/p -β and p ∈ (0, 1).
3.5. A parametric example. We illustrate in this section our procedure in an example corresponding to parametric assumptions on f 0 . More precisely, given a density f , we define the model

F = f m,s , m ∈ R, s ∈ (0, +∞) where f m,s (•) = 1 s f • -m s . ( 19
)
Saying that f 0 belongs to F amounts to saying that f 0 is known, up to a location m and scale parameter s.

In statistics, parametric estimation is often performed via the maximum likelihood method. However, the likelihood approach is not appropriate here as q is not bounded. Assume for instance that q admits a singularity in 0. In such a case, when f 0 = f m,s for some m ∈ R and s > 0, the density of the Y i 's can be rewritten as

(f m,s * q)(y) = f (t)q(y -m -st) dt, ∀y ∈ R.
Then, we can remark that for any y ∈ R,

sup m∈R s>0 (f m,s * q)(y) ≥ sup s>0 f (t)q(-st) dt ≥ f (t) lim inf s→0
q(-st) dt, using Fatou's lemma. Hence, the log-likelihood can take infinite values, and the maximum likelihood estimator is not defined.

An alternative approach would be to use estimators of f 0 * q leading to results for the L 1 loss like, for instance, the T -estimation method [START_REF] Birgé | Model selection via testing: an alternative to (penalized) maximum likelihood estimators[END_REF], or the combinatorial method [START_REF] Devroye | Combinatorial methods in density estimation[END_REF]. However, such procedures would lead to risk bounds for

E[d 1 (f 0 * q, f m,ŝ * q)] instead of E[d 1 (f 0 , f m,ŝ )]. Young's inequality asserts that E[d 1 (f 0 * q, f m,ŝ * q)] ≤ E[d 1 (f 0 , f m,ŝ )] but the converse is unfortunately not true in general.
To apply our procedure, we have to check that Assumption 2 holds. This is the aim of the next proposition (to be proved in Section 5.9). Proposition 9. Suppose that f is a positive density on (-1, 1) vanishing outside (-1, 1). Moreover, f is log-concave on (-1, 1) and unimodal with mode at 0. Then, Assumption 2 is fullfilled with d fm,s = 5 and ℓ m,s ≤ |m| + s + 1.

A direct application of Theorem 5 leads to the following result.

Theorem 10. Consider the collection F defined by (19) and suppose that f satisfies the conditions of Proposition 9. Then, there exists an estimator f of the form f = f m,ŝ such that:

E d 1 (f 0 , f ) ≤ 3 inf m∈R s>0 d 1 (f 0 , f m,s ) + c m,s f 0 * q ∞ log n n + 1 n , (20)
where in the above inequality,

c m,s = c(|m| + s + 1) 1 + log (|m| + s + 1)
log n for a term c depending only on β, κ 1 and κ 2 .

When f 0 does belong to the model F , that is when there exist m 0 , s 0 such that f 0 = f m 0 ,s 0 , we get

E[d 1 (f 0 , f )] ≤ 3 c m 0 ,s 0 f 0 * q ∞ log n n + 3 n .
Up to a logarithmic term, we recover the expected square root rate in parametric density estimation.

Let us mention that we do not assume that f 0 lies in the model in order to get (20). Since d 1 (f 0 , f ) ≥ d 1 (f 0 , F ) for all f ∈ F , an estimator can perform well only when there exists

f m 0 ,s 0 ∈ F such that d 1 (f 0 , F ) = d 1 (f 0 , f m 0 ,s 0 ) is small.
In that case, we observe that the risk of our estimator remains under control. In other words, our estimator f is robust with respect to model misspecification measured through the L 1 loss.

Estimation procedure

This section is devoted to the construction of the estimator f ∈ F leading to the results displayed in Theorem 5.

4.1. Probability estimators. In Section 2.2, we proposed simple estimators Z n (I) of P (X ∈ I). Unfortunately, the only deviations bounds that can be established for these quantities come from Chebyshev inequality (as Z(I) may not admit moments of order larger than 2). Such bounds are too rough to be used in the construction of our estimator f of f 0 . This is why we propose in the following new probability estimators for which uniform bounds in deviation can be proved. Their constructions involve different steps.

Step 1. We consider an interval I of finite length and begin by defining a median of means estimator of the probability P (X ∈ I). We refer, e.g., to [START_REF] Devroye | Subgaussian mean estimators[END_REF] for more details regarding this approach.

Let δ > 0 be a parameter whose value will be specified later on. When either δ ≥ n -1 or |I| = 0, we set Z δ (I) = 0. Otherwise, we split the data (Y 1 , . . . , Y n ) into r ∈ (δ, δ + 1] parts b 1 , . . . , b r . Each part should be approximatively of the same size and more precisely such that |b k | ∈ (n/r, n/r + 1]. For each k ∈ {1, . . . , r}, we define the empirical mean based on the observations in the k-th bloc only:

Z b k (I) = 1 2π|b k | Y j ∈b k φ ⋆ I (Y j ).
We then define Z δ (I) as any empirical median of {Z b 1 (I), . . . , Z br (I)}, that is as any real number such that

k ∈ {1, . . . , r}, Z b k (I) ≤ Z δ (I) = k ∈ {1, . . . , r}, Z b k (I) ≥ Z δ (I) .
Step 2. We broaden the previous definition of Z δ (I) to unions I of intervals. In the sequel, we denote I ∞ = ∪ ∞ d=1 I d and the closure of a set I by Ī. Every union of intervals I ∈ I ∞ can be written as Ī = d I j=1 Īj where d I ∈ N ⋆ and the I j are intervals such that Īj ∩ Īj ′ = ∅ for all j = j ′ . We stress that d I and the intervals Īj are defined in a unique way. Due to the additivity of measures, it is then natural to set

Z δ (I) = d I j=1 Z δ ( Īj ).
Note that this definition is coherent with the first step as Z δ (I) = Z δ ( Ī) when I is an interval (in which case d I = 1).

Step 3. One may already show that each estimator Z δ (I) is close to P (X ∈ I) with high probability. However, we need this result to be true uniformly for all I ∈ I ∞ . Hence, we add a technical discretization step.

For any d, j, ℓ ∈ N ⋆ , we introduce the grid

G d,j,ℓ = -ℓ + kℓ2 -(j-1) /d, k ∈ {0, . . . , d2 j } ⊂ [-ℓ, ℓ],
and define the set I d,j,ℓ ⊂ I d of unions of at most d intervals whose endpoints lie in G d,j,ℓ . For all union of intervals I ∈ I ∞ , let ℓ I be the smallest integer such that I ⊂ [-ℓ I , ℓ I ], and π j (I) be the largest set of I d I ,j,ℓ I included in I. If such set does not exist, π j (I) = ∅.

Consider ξ ≥ 1 and δ j (I) = 2 log(2jℓ

I d I ) + 2 log(1 + d I 2 j+1
) for all (I, j) ∈ I ∞ × N ⋆ . We define for all I ∈ I ∞ , our final estimator Z n,ξ (I) of P (X ∈ I) by

Z n,ξ (I) = Z ξ+δ 1 (I) (π 1 (I)) + ∞ j=1 Z ξ+δ j (I) (π j+1 (I) \ π j (I)).
This sum is composed of a finite number of terms as ξ + δ j (I) exceeds n -1 for j large enough. We prove in Section 5.10 the following result.

Proposition 11. Consider ξ ≥ 1. Then, there is an event of probability lower bounded by 1e -ξ on which: for all I ∈ I ∞ ,

Z n,ξ (I) -P (X ∈ I) ≤ C f 0 * q ∞ κ 1 ℓ I d I + c β κ 2 ℓ 1-2β I d 2β+1 I (ξ + log(ℓ I d I )) n .
In the above inequality, C denotes a universal constant and c β only depends on β.

4.2. Estimation procedure. We consider a collection F satisfying Assumption 2 and propose a theoretical procedure in line with the combinatorial method [START_REF] Devroye | Combinatorial methods in density estimation[END_REF] to define an estimator f ∈ F satisfying (12). Examples of such collections are given in Sections 3.2, 3.3, 3.4 and 3.5.

Our procedure relies on Scheffé's lemma which entails that

d 1 (f 0 , f ) = 2 sup I∈B(R) I f - I f 0 ,
where the supremum is taken over all Borelian sets of R. Actually, this supremum is reached for the collection

I ⋆ = {x ∈ R, f (x) ≥ f 0 (x)}.
According to Assumption 2, I ⋆ should be a union of intervals when f, f 0 ∈ F . We may then approximate the probability I f 0 = P (X ∈ I) by our estimator Z n,ξ (I). This yields an estimator γ ξ (f ) of d 1 (f 0 , f ) to be minimized over f ∈ F . More precisely, define for d ≥ 1, the set I d ⊂ I d of unions of at most d intervals of finite length with endpoints in Q. For any ξ ≥ 1, we introduce the criterion γ ξ (•) defined for f ∈ F by

γ ξ (f ) = sup I∈I d f I⊂[-ℓ f ,ℓ f ] I f -Z n,ξ (I) .
Then, we consider estimators f ∈ F satisfying

γ ξ ( f ) ≤ inf f ∈F γ ξ (f ) + 1/n. ( 21
)
Assumption 2 asserts that there is a dense and at most countable suitable subset F of F . The lemma below ensures that we may always define f as an element of this set F to avoid possible measurability issues.

Lemma 1. There exists an estimator f ∈ F satisfying (21).

Note that there is no uniqueness concerning the way where our estimator is defined. However, Theorem 5 applies for any of the estimators f satisfying (21).

Let us mention that there are algorithmic issues concerning the computation of this estimator that are far beyond the scope of this paper. This is the counterpart to get a versatile procedure. This weakness also appears for instance in the original combinatorial method of [START_REF] Devroye | Combinatorial methods in density estimation[END_REF], in the procedures based on robust tests, see [START_REF] Birgé | Model selection via testing: an alternative to (penalized) maximum likelihood estimators[END_REF], and in the ρ-estimation procedure [START_REF] Baraud | A new method for estimation and model selection: ρ-estimation[END_REF]. As it is said in the introduction of [START_REF] Birgé | From Probability to Statistics and Back: High-Dimensional Models and Processes[END_REF], we cannot have our cake and eat it.

4.3. About ξ. Our estimator explicitly depends on the desired confidence level for the risk bound (12). This is due to the use of a median of means estimator in the construction of Z n,ξ . It is however possible to substitute it with a subgaussian estimator to bypass this problem, see [START_REF] Devroye | Subgaussian mean estimators[END_REF]. This requires, however, to know an upper bound M on f 0 * q ∞ . In order to avoid redundancy with the previous section, we do not rewrite here the entire construction of the probability estimators. Let us simply mention that they will no longer depend on ξ but on M . We make a slight abuse of notations by writing them Z n,M (•). We have:

Proposition 12. Let M ≥ f 0 * q ∞ be a known number. Then, for all I ∈ I ∞ , there exist an estimator Z n,M (I) of P (X ∈ I) such that: for all ξ ≥ 1, and probability larger than 1e -ξ : for all

I ∈ I ∞ , Z n,M (I) -P (X ∈ I) ≤ C M κ 1 ℓ I d I + c β κ 2 ℓ 1-2β I d 2β+1 I (ξ + log(ℓ I d I )) n .
In the above inequality, C denotes a universal constant and c β only depends on β.

A sketch of its proof is given in Section 5.13. We may therefore use the same approach as above to estimate f 0 . By replacing Z n,ξ by Z n,M , we get a new estimator associated to the following result (for a description of the procedure, see Section 5.14).

Theorem 13. Let F be a model fulfilling Assumption 2 and M ≥ f 0 * q ∞ be a known number. There exists an estimator f ∈ F such that for all ξ ≥ 1 and probability larger than 1e -ξ ,

d 1 (f 0 , f ) ≤ 3 inf f ∈F    d 1 (f 0 , f ) + c M (κ 1 ℓ f d f + c β κ 2 ℓ 1-2β f d 2β+1 f ) (ξ + log(ℓ f d f )) n    .
Therefore,

E d 1 (f 0 , f ) ≤ 3 inf f ∈F    d 1 (f 0 , f ) + c ′ M (κ 1 ℓ f d f + c β κ 2 ℓ 1-2β f d 1+2β f )(1 + log(ℓ f d f )) n    .
In the above inequalities, c, c ′ are universal constants and c β only depends on β.

If we are interested in bounds in expectation, we can notice that we obtain a parametric rate of convergence as soon as the bias term vanishes for a function f corresponding to a term ℓ f d f not depending on n. Hence, some of our results can be improved when the bound M is available. For instance, the rate of convergence associated to the estimation of a piecewise constant (or more generally polynomial) density on a given number of (unknown) intervals becomes parametric (see, e.g. Theorem 8). Similarly, the logarithmic term in Theorem 10 can be omitted in this situation. However, when the infimum is reached for some ℓ f d f depending in a polynomial way of n, there is no gain to expect from the knowledge of M .

In general, when the quantity M is unknown, one can split the sample in two different parts, one of these parts allowing an estimation of this term. This issue is quite standard in statistics. It appears for instance in density estimation for some procedures based on penalized L 2 criteria. It is actually possible to obtain sharp bounds when the density f 0 * q is smooth enough. We refer to [START_REF] Birgé | From model selection to adaptive estimation[END_REF] for more details.

Proofs

5.

1. An elementary inequality. For the ease of exposition, we reproduce here the following simple inequality that will be used all along the proofs.

Lemma 2. For any non-negative sequence (a j ) j∈N , k ∈ N * and γ ∈ (0, 1) we have

k j=1 a 1-γ j ≤   k j=1 |a j |   1-γ k γ .
This bound is obtained thanks to a direct application of the Hölder inequality.

Sketch of the proof of Proposition 1. Define for t ∈ R,

I(t) = 1 -1 |x| β-1 e itx dx.
Then elementary computations give

|t| β I(t) = 2 |t| 0 y β-1 cos(y) dy.
We use classical results on Fourier cosine transforms to get |t| β I(t) -→ 2 cos(πβ/2)Γ(β) as |t| → +∞.

In the above equality, Γ(•) denotes the Gamma function. In particular, the limit is finite and non-zero.

Setting ψ(x) = |x| β-1 (ϕ(x)ϕ(0)) for all x ∈ R, we can write

1 -1 q(x)e itx dx = ϕ(0)I(t) + 1 -1 ψ(x)e itx dx.
On [-1, 1], ψ is bounded and its derivative is integrable. Therefore, integration by parts shows

1 -1 ψ(x)e itx dx = O(1/t) as |t| → +∞.
Likewise, on (-∞, -1] ∪ [1, +∞), q is bounded and its derivative is integrable and thus,

(-∞,-1] ∪[1,+∞) q(x)e itx dx = O(1/t).
Hence q ⋆ (t) = ϕ(0)I(t) + O(1/t) as t → +∞, from which we deduce that (|t| β |q ⋆ (t)|) -1 admits a finite limit when |t| → +∞. As q ⋆ does not vanish and is continuous, |q ⋆ (t)| -1 is bounded above on [-1, 1] and (|t| β |q ⋆ (t)|) -1 is bounded above on (-∞, -1] ∪ [1, +∞). This ends the proof.

5.3. Proof of (3) when f 0 ∈ L 2 (R). Without loss of generality, we may suppose that I is an interval says I = [a, b]. Let K be a density belonging to L 2 (R), h > 0 and K h (•) = (1/h)K(•/h). Then, if F 0 denotes the cumulative distribution function of X,

½ I (t)(f 0 * K h )(t) dt -½ I (t)f 0 (t) dt = K(x) (F 0 (b -xh) -F 0 (b) + F 0 (a) -F 0 (a -xh)) dx.
By using the dominated convergence theorem, we deduce,

lim h→0 ½ I (t)(f 0 * K h )(t) dt -½ I (t)f 0 (t) dt = 0. Yet, f 0 * K h ∈ L 2 (
R) as it is the case for K h , and by Plancherel isometry, lim h→0 1 2π

½ ⋆ I (t) f ⋆ 0 (t)K ⋆ h (t) dt = ½ I (t)f 0 (t) dt. Note that ½ ⋆ I (t) f ⋆ 0 (t) = (½ ⋆ I (t) [q ⋆ (t)] -1 ) × (q ⋆ (t)f ⋆ 0 (t)
). This map is a product of two square integrable functions (q ⋆ f ⋆ 0 belongs to L 2 (R) as q * f 0 does since this density is bounded) and is therefore integrable. We may thus use lim h→0 K ⋆ h (t) = K ⋆ (0) = 1 and the dominated convergence theorem to get

½ ⋆ I (t) f ⋆ 0 (t) dt = ½ I (t)f 0 (t)
E[(Z(I)) 2 ] = 1 4π 2 (φ ⋆ I (y)) 2 (f 0 * q)(y) dy, ≤ f 0 * q ∞ 4π 2 (φ ⋆ I (y)) 2 dy.
We successively use Fourier Plancherel theorem and Cauchy-Schwarz inequality to get

E[(Z(I)) 2 ] ≤ f 0 * q ∞ 2π ½ ⋆ I (t) q ⋆ (t) 2 dt = f 0 * q ∞ 2π k j=1 ½ ⋆ I j (t) q ⋆ (t) 2 dt ≤ f 0 * q ∞ 2π × k × k j=1 ½ ⋆ I j (t) q ⋆ (t) 2 dt.
For any j ∈ {1, . . . , k} and t ∈ R, we have

|½ ⋆ I j (t) | = |½ ⋆ I j (t)| = 2 | sin(t|I j |/2)| |t|
since I j is an interval of finite length |I j |. Hence, thanks to Assumption 1,

½ ⋆ I j (t) q ⋆ (t) 2 dt = 4 sin 2 (t|I j |/2) t 2 |q ⋆ (t)| 2 dt ≤ 4 sin 2 (t|I j |/2) t 2 κ 1 + κ 2 |t| 2β dt ≤ 4κ 1 (|I j |/2) sin 2 (t) t 2 dt + 4κ 2 (|I j |/2) 1-2β sin 2 (t)|t| 2β-2 dt.
By computing these integrals,

½ ⋆ I j (t) q ⋆ (t) 2 dt ≤ 2κ 1 π|I j | + 4κ 2 sin(πβ)Γ(2β) 1 -2β |I j | 1-2β ,
where Γ(•) denotes the Gamma function. Finally, we get For all I ∈ m, and α ∈ R,

E[(Z(I)) 2 ] ≤ f 0 * q ∞ 2π × k ×   2κ 1 π k j=1 |I j | + 4κ 2 sin(πβ)Γ(2β) 1 -2β k j=1 |I j | 1-2β   , ≤ f 0 * q ∞ 2π × d × 2κ 1 π|I| + 4κ 2 sin(πβ)Γ(2β) 1 -2β d 2β |I| 1-2β ,
I f 0 - 1 |I| I f 0 ≤ I |f 0 -α| + α|I| - I f 0 = I |f 0 -α| + I (α -f 0 ) ≤ 2 I |f 0 -α| .
Therefore,

d 1 (f 0 , fm ) = I∈m I f 0 - 1 |I| I f 0 + R\∪ I∈m I f 0 ≤ 2d 1 (f 0 , F m ).
Moreover,

E d 1 fm , fm = I∈m E [|Z n (I) -P (X ∈ I)|] ≤ I∈m E |Z n (I) -P (X ∈ I)| 2 ≤ 1 n 1/2 I∈m E (Z(I)) 2 .
By using Proposition 2 and Lemma 2,

E d 1 fm , fm ≤ f 0 * q 1/2 ∞ n 1/2 κ 1/2 1 I∈m |I| 1/2 + c 1/2 β κ 1/2 2 I∈m |I| 1/2-β , ≤ f 0 * q 1/2 ∞ n 1/2 κ 1/2 1 ℓ 1/2 |m| 1/2 + c 1/2 β κ 1/2 2 ℓ 1/2-β |m| 1/2+β
. The proof then follows from the triangle inequality

E d 1 f 0 , fm ≤ d 1 f 0 , fm + E d 1 fm , fm .

Proof of Proposition 4.

Let h be the Hellinger distance defined for two densities f 1 , f 2 by

h 2 (f 1 , f 2 ) = 1 2 R f 1 (x) -f 2 (x) 2 dx.
It follows from standard arguments (see, e.g., [START_REF] Alexandre | Introduction to nonparametric estimation[END_REF]) that inf

f sup f 0 ∈Fm(2) E d 1 (f 0 , f ) ≥ 1 2 sup f 1 ,f 2 ∈Fm(2) d 1 (f 1 , f 2 ) 1 - √ 2nh(f 1 * q, f 2 * q) . (22)
Consider p = min{1, 1/ q ∞ }, a = 50τ 2 , and set

f 1 = p √ an½ [0,1/ √ an) + (1 -p)½ [0,1] , f 2 = p √ an 2 ½ [0,2/ √ an) + (1 -p)½ [0,1] .
Young's Inequality implies f 1 * q ∞ ≤ p q ∞ + 1p ≤ 2. The same result is true for f 2 * q. Therefore, f 1 and f 2 both belong to F m (2).

We now bound h(f 1 * q, f 2 * q). We have,

f 2 * q(x) -f 1 * q(x) = p 2 1 0 q x -(u + 1)/ √ an -q x -u/ √ an du.
We introduce for x ∈ R,

ϕ 2 (x) = 1 0 q(x -(u + 1)/ √ an) -q(x -u/ √ an) 2 du,
and decompose f 2 * q(x)f 1 * q(x) as

f 2 * q(x) -f 1 * q(x) = p 2 ϕ 2 (x) + p 1 0 q x -(u + 1)/ √ an -q x -u/ √ an q x -u/ √ an du.
We apply Cauchy Schwarz inequality:

|f 2 * q(x) -f 1 * q(x)| ≤ p 2 ϕ 2 (x) + pϕ(x) 1 0 q x -u/ √ an du ≤ p 2 ϕ 2 (x) + ϕ(x) √ p f 1 * q(x). Let X = x ∈ R, f 1 * q(x) + f 2 * q(x) ≤ ϕ 2 (x) .
We deduce,

2h 2 (f 1 * q, f 2 * q) ≤ X |f 1 * q -f 2 * q| + X c (f 1 * q -f 2 * q) 2 f 1 * q + f 2 * q ≤ X ϕ 2 + 1 2 X c p 2 ϕ 4 + 4pϕ 2 f 1 * q f 1 * q + f 2 * q ≤ X ϕ 2 + 5 2 X c ϕ 2 ≤ 5 2 ϕ 2 .
Yet,

ϕ 2 ≤ sup u∈[0,1] q(x -(u + 1)/ √ an) -q(x -u/ √ an) 2 dx ≤ 2 sup u∈[0,1] q(x -(u + 1)/ √ an) -q(x) 2 dx + q(x -u/ √ an) -q(x) 2 dx ≤ 10τ 2 /(an)
thanks to (11). We use the definition of a to get 2nh 2 (f 1 , f 2 ) ≤ 1/2. We conclude by using ( 22) and by remarking that d 1 (f 1 , f 2 ) = p.

Proofs of Theorems 6 and 7. We need the elementary claim displayed below

Claim 1. For all positive numbers A, a, b, n, α,

inf k≥1 A k α + a 1/2 k 1/2 n 1/2 + b 1/2 k 1/2+β n 1/2 ≤ R + a 1/2 + b 1/2 n 1/2 where R = 2 A (2β+1)/(2β+2α+1) b α/(2α+2β+1) n α/(2α+2β+1) + A 1/(2α+2β+1) a 1/2 b 1/(4α+4β+2) n (α+β)/(2α+2β+1) .
Proof of Theorem 6. We apply Theorem 5, use

d 1 (f 0 , f ) ≤ d 1 (f 0 ½ [-ℓ,ℓ] , f ) + [-ℓ,ℓ] c f 0 and Lemma 4 in Appendix C to get for all ℓ ≥ 1, E d 1 (f 0 , f ) ≤ C ′ inf k≥1 L 1 (f 0 ½ [-ℓ,ℓ] )/k + f 0 * q ∞ κ 1 ℓ(k + r + 1) + κ 2 c β ℓ 1-2β (k + r + 1) 1+2β log(ℓn) n + 1 n + [-ℓ,ℓ] c f 0 .
We then use Claim 1.

Proof of Theorem 7. Similarly, we apply Theorem 5, use

d 1 (f 0 , f ) ≤ d 1 (f 0 ½ [-ℓ,ℓ] , f )+ [-ℓ,ℓ] c f 0 ,
and deduce from Lemma 5 in Appendix C that for all ℓ ≥ 1,

E d 1 (f 0 , f ) ≤ C ′ inf k≥1 L 2 (f 0 ½ [-ℓ,ℓ] )/k 2 + f 0 * q ∞ κ 1 ℓ(k + r + 1) + κ 2 c β ℓ 1-2β (k + r + 1) 1+2β log(ℓn) n + 1 n + [-ℓ,ℓ] c f 0 .
We finally use Claim 1.

5.8. Proof of Corollary 3. For all k ≥ 1, we use Corollary 3.3 of [START_REF] Ronald | Degree of adaptive approximation[END_REF] to get a piecewise polynomial function f of degree at most r and based on at most k pieces such that

d 1 (f 0 , f ½ [0,1] ) ≤ cR2 -k .
In this inequality, c only depends on α, p, r.

Let f + be the map defined by f + (x) = max{f (x), 0}½ [0,1] (x). Then, f + is still a piecewise polynomial function such that d 1 (f 0 , f + ) ≤ cR2 -k . It is, however, based on at most k(r + 1) pieces. When k is large enough, cR2 -k < 1 and f + cannot be identically zero. We may then set

f dens (x) = f + (x) f + (t) dt .
This map belongs to F k(r+1),r and satisfies

d 1 (f 0 , f dens ) ≤ cR2 -k .
Theorem 8 then implies (with ℓ = 1),

E d 1 (f 0 , f ) ≤ 3cR2 -k + C M (κ 1 k(r + 1) 2 + c β κ 2 (k(r + 1) 2 ) 1+2β ) log n n + 3 n .
It then remains to choose a k that minimizes the right-hand side of this inequality.

5.9. Proof of Proposition 9. We set

F = {f m,s , m ∈ Q, s ∈ Q ∩ (0, +∞)} .
For any (m, s) ∈ R × (0, +∞), there exists a sequence ( mr , sr ) r ∈ ((Q ∩ [-|m|, |m|]) × (Q ∩ (0, s])) N converging to (m, s). Since f is continuous almost everywhere, (f mr,sr ) r converges almost everywhere to f m,s . Scheffé's lemma then ensures that the convergence is in the L 1 space. This proves the second part of Assumption 2.

The proof of the first part is elementary but a bit tedious. We need to show that [f m,s > f m ′ ,s ′ ] is a union of at most 5 intervals. We may assume without loss of generality that m ′ = 0 and s ′ = 1 in which case f 0,1 = f . We moreover suppose in the sequel that m ≥ 0. The proof is similar when m is non-positive.

Let I = (-1, 1) ∩ (m -s, m + s) . Note that [f m,s > f ] ∩ I c = (m -s, m + s) ∩ (-1, 1) c , is a union of at most 2 intervals. Since f m,s -f is non-decreasing on I ∩ [0, m], [f m,s > f ] ∩ I ∩ [0, m] is an interval. We now show that [f m,s > f ] ∩ I ∩ (m + ∞) is an interval. Let x ∈ I ∩ (m, +∞).
We distinguish the cases s ≥ 1 and s < 1.

• Suppose first that s ≥ 1. Let f 2 be the concave function f 2 = log f . In the following, f ′ 2 denotes either the left or right derivative of f 2 . Since f ′ 2 is non-increasing and non-positive on [0, 1), and (xm)/s < x, we deduce that

f ′ 2 (x) ≤ f ′ 2 ((x -m)/s) ≤ f ′ 2 ((x -m)/s)/s. Hence, ϕ(x) = f 2 ((x -m)/s) -f 2 (x) is non-decreasing on I ∩ (m, +∞). Therefore, the set [f m,s > f ] ∩ I ∩ (m, +∞) = [ϕ > log s] ∩ I ∩ (m, +∞) is an interval. • Suppose now that s < 1. When x ≤ (x -m)/s, f ′ 2 ((x -m)/s)/s ≤ f ′ 2 ((x -m)/s) ≤ f ′ 2 (x). The map ϕ is therefore non-increasing on I ∩ [m/(1 -s), +∞) and [f m,s > f ] ∩ I ∩ [m/(1 -s), +∞) is an interval. Moreover, this interval is either empty, or contains m/(1 -s). When x ≥ (x -m)/s, f (x) ≤ f ((x -m)/s) < f ((x -m)/s)/s. Then, [f m,s > f ] ∩ I ∩ (m, m/(1 -s)) = (m, m/(1 -s))
is an interval. We derive that

[f m,s > f ] ∩ I ∩ (m, +∞) = ([f m,s > f ] ∩ I ∩ [m/(1 -s), +∞)) ∪ (m, m/(1 -s)) is an interval. We now show that [f m,s > f ] ∩ I ∩ (-∞, 0
) is an interval. For this purpose, remark that f is non-decreasing and f ′ 2 is both non-negative and non-increasing on (-∞, 0) ∩ I. Let

• When s ≥ 1, a similar reasoning to the previous one shows when x ∈ I ∩ (-∞, 0),

f m,s (x) ≤ f (x) when (x -m)/s ≤ x ϕ ′ (x) ≤ 0 when (x -m)/s ≥ x.
Therefore,

[f m,s > f ] ∩ I ∩ (-∞, 0) = [ϕ > log s] ∩ I ∩ (-∞, -m/(s -1))
is an interval. • When s < 1, (xm)/s ≤ x when x ∈ I ∩ (-∞, 0), and thus ϕ ′ (x) ≥ 0. This implies that

[f m,s > f ] ∩ I ∩ (-∞, 0) = [ϕ > log s] ∩ I ∩ (-∞, -m/(s -1)] is an interval.
Grouping all these results together concludes the proof.

Proof of Proposition 11

Claim 2. For all I ∈ I d ,

P (X ∈ I) ≤ f 0 * q ∞ [κ 1 d|I| + c β κ 2 d 1+2β |I| 1-2β ]. ( 23
)
Proof. We use Proposition 2 and Jensen's inequality E[Z(I)] ≤ E[(Z(I)) 2 ] Claim 3. For all δ > 0 and interval I ∈ I 1 , the following assertion holds true on an event of probability lower bounded by 1e -δ :

Z δ (I) -P (X ∈ I) ≤ C f 0 * q ∞ [κ 1 |I| + c β κ 2 |I| 1-2β ] (1 + δ) n . ( 24
)
In this inequality, C is a universal constant and c β only depends on β.

Proof. The proof is straightforward when |I| = 0. Suppose now that |I| > 0. When δ < n -1, this inequality comes from standard results about median of means estimators, see Section 4.1 of [START_REF] Devroye | Subgaussian mean estimators[END_REF]. When δ is larger, Z δ (I) = 0, and (24) ensues from (23).

Claim 4. For all ξ > 0, the following assertion holds true on an event of probability lower bounded by 1e -ξ : for all d, j, ℓ and closed interval I ∈ I 1 with endpoints lying in G d,j,ℓ ,

Z ξ+δ d,j,ℓ (I) -P (X ∈ I) ≤ C f 0 * q ∞ [κ 1 |I| + c β κ 2 |I| 1-2β ] (ξ + 1 + δ d,j,ℓ ) n , ( 25
)
where δ d,j,ℓ = 2 log(jdℓ) + 2 log(1 + d2 j ). In this inequality, C is a universal constant and c β only depends on β.

Proof. Let for all δ > 0 and interval I, E(δ, I) be the event on which (24) is true. Let I ′ d,j,ℓ be the collection of closed intervals with endpoints in G d,j,ℓ . Then, (25) holds true on

E = (d,j,ℓ)∈(N ⋆ ) 3 I∈I ′ d,j,ℓ E(ξ + δ d,j,ℓ , I).
Moreover, Bonferroni's inequality asserts

P (E c ) ≤ (d,j,ℓ)∈(N ⋆ ) 3 |I ′ d,j,ℓ |P E c (ξ + δ d,j,ℓ , I) ≤ e -ξ (d,j,ℓ)∈(N ⋆ ) 3
(1 + d2 j ) 2 e -2 log(jdℓ)-2 log(1+d2 j )

≤ e -ξ .

Claim 5. For all ξ > 0, the following assertion holds true on an event of probability lower bounded by 1e -ξ : for all d, j, ℓ and I ∈ I d,j,ℓ ,

Z ξ+δ d,j,ℓ (I) -P (X ∈ I) ≤ C f 0 * q ∞ [κ 1 d|I| + c β κ 2 d 1+2β |I| 1-2β ] (ξ + 1 + δ d,j,ℓ ) n .
In this inequality, C is a universal constant and c β only depends on β.

Proof. Let I ∈ I d,j,ℓ written as Ī = ∪ d k=1 Īk such that Īk 1 ∩ Īk 2 = ∅ for all k 1 = k 2 . Then,

Z ξ+δ d,j,ℓ (I) -P (X ∈ I) ≤ d k=1 Z ξ+δ d,j,ℓ ( Īk ) -P (X ∈ Īk ) .
Note that each Īk belongs to the set I ′ d,j,ℓ defined in the preceding proof. Therefore, on the event defined in the preceding claim,

Z ξ+δ d,j,ℓ (I) -P (X ∈ I) ≤ C f 0 * q ∞ (ξ + 1 + δ d,j,ℓ ) n d k=1 κ 1 |I k | + c β κ 2 |I k | 1-2β .
We finally use Cauchy-Schwarz inequality and Lemma 2.

Claim 6. For all ξ > 0, the following assertion holds true on an event of probability lower bounded by 1e -ξ : for all j and I ∈ I ∞ with endpoints lying in G 2d I ,j,ℓ I ,

Z ξ+δ j (I) (I) -P (X ∈ I) ≤ C f 0 * q ∞ [κ 1 d I |I| + c β κ 2 d 1+2β I |I| 1-2β ](ξ + 1 + δ j (I)) n .
In this inequality, C is a universal constant and c β only depends on β.

Proof. We apply the preceding claim, use that δ j (I) = δ 2d I ,j,ℓ I and increase C, c β .

Proof of Proposition 11. For all j and I ∈ I ∞ , |π j+1 (I) \ π j (I)| ≤ ℓ I 2 -j+2 and π j+1 (I) \ π j (I) belongs to I 2d I ,j,ℓ I . The preceding claim then ensures:

Z ξ+δ j (I) (π j+1 (I) \ π j (I)) -P (X ∈ π j+1 (I) \ π j (I)) ≤ C f 0 * q ∞ κ 1 d I ℓ I 2 -j + c β κ 2 d 1+2β I ℓ 1-2β I 2 -(1-2β)j (ξ + 1 + 2 log(2jℓ I d I ) + 2 log(1 + d I 2 j+1 )) n .
Therefore,

∞ j=1 Z ξ+δ j (I) (π j+1 (I) \ π j (I)) -P (X ∈ π j+1 (I) \ π j (I)) ≤ C ′ f 0 * q ∞ κ 1 ℓ I d I + c ′ β κ 2 ℓ 1-2β I d 2β+1 I (ξ + log(ℓ I d I )) n ,
where C ′ is a universal constant and where c ′ β depends on β only. Since

P (X ∈ I) = P (X ∈ π 1 (I)) + ∞ j=1 P (X ∈ π j+1 (I) \ π j (I)),
we obtain

Z n,ξ (I) -P (X ∈ I) ≤ C ′ f 0 * q ∞ κ 1 ℓ I d I + c ′ β κ 2 ℓ 1-2β I d 2β+1 I (ξ + log(ℓ I d I )) n + Z ξ+δ 1 (I) (π 1 (I)) -P (X ∈ π 1 (I)) .
We use Claim 6 again to bound the last term.

5.11. Proof of Lemma 1. Let f be an arbitrary function of F . Thanks to Assumption 2, there exists

f ′ ∈ F such that d f ′ ≤ d f , ℓ f ′ ≤ ℓ f , d 1 (f, f ′ ) ≤ 1/n. Then, γ ξ (f ′ ) ≤ sup I∈I d f ′ I⊂[-ℓ f ′ ,ℓ f ′ ] I f ′ - I f + I f -Z n,ξ (I) .
By Scheffe's identity,

γ ξ (f ′ ) ≤ d 1 (f, f ′ ) 2 + sup I∈I d f ′ I⊂[-ℓ f ′ ,ℓ f ′ ] I f -Z n,ξ (I) ≤ 1 2n + γ ξ (f ).
We thus deduce that inf

f ∈F γ ξ (f ) ≤ 1 2n + inf f ∈F γ ξ (f ).
Therefore, any f ∈ F such that

γ ξ ( f ) ≤ inf f ∈F γ ξ (f ) + 1 2n .
satisfies condition (21).

Proof of Theorem 5

Lemma 3. Let f ∈ F be an estimator satisfying (21). Then,

d 1 (f 0 , f ) ≤ inf f ∈F          3d 1 (f 0 , f ) + 4 sup I∈I d f I⊂[-ℓ f ,ℓ f ] Z n,ξ (I) - I f 0 + 2 n          . Proof. For all f ∈ F , we define I = [f > f ] when ℓ f ≤ ℓ f and I = [ f > f ] otherwise. Note that I ∈ I d f ∩I d f and is included in [-ℓ f , ℓ f ]∩[-ℓ f , ℓ f ] as the functions of F are non-negative.
Since the functions f ∈ F are densities,

d 1 (f, f ) = 2 I f - I f . There exists Ī ∈ I d f ∩ I d f included in I such that d 1 (f, f ) ≤ 2 Ī f - Ī f + 1 n ≤ 2 Ī f -Z n,ξ ( Ī) + 2 Z n,ξ ( Ī) - Ī f + 1 n .
Therefore,

d 1 (f, f ) ≤ 2γ ξ (f ) + 2γ ξ ( f ) + 1 n ≤ 4γ ξ (f ) + 2 n (26)
by using (21). Now,

γ ξ (f ) ≤ sup I∈I d f I⊂[-ℓ f ,ℓ f ] I f 0 - I f + sup I∈I d f I⊂[-ℓ f ,ℓ f ] I f 0 -Z n,ξ (I) .
By using Scheffe identity,

γ ξ (f ) ≤ d 1 (f 0 , f ) 2 + sup I∈I d f I⊂[-ℓ f ,ℓ f ] I f 0 -Z n,ξ (I) .
This inequality, together with (26) entails that

d 1 (f, f ) ≤ 2d 1 (f 0 , f ) + 4 sup I∈I d f I⊂[-ℓ f ,ℓ f ] I f 0 -Z n,ξ (I) + 2 n .
We conclude using the triangle inequality

d 1 (f 0 , f ) ≤ d 1 (f 0 , f ) + d 1 (f, f ).
Proof of Theorem 5. Combining Proposition 11 and Lemma 3 implies that for all f ∈ F , and probability larger than 1e -ξ ,

d 1 (f 0 , f ) ≤ 3d 1 (f 0 , f ) + C ′ f 0 * q ∞ κ 1 ℓ f d f + c β κ 2 ℓ 1-2β f d 2β+1 f (ξ + log(ℓ f d f )) n + 2 n , (27)
where C ′ is a universal constant. It can be easily seen that the residual term 2/n can be removed from the previous bound up to a slight change in C ′ and c β .

Concerning the second inequality, we apply the first part with ξ = log(2n). There exists therefore an event E n of probability 1 -1/(2n) and an estimator f such that

d 1 (f 0 , f )½ En is not larger than inf f ∈F    3d 1 (f 0 , f ) + c f 0 * q ∞ κ 1 ℓ f d f + c β κ 2 ℓ 1-2β f d 1+2β f (log ℓ f + log d f + log n) n    .
Up to an increase of c, we now assert that the term log d f inside the square root can be removed. Let f ∈ F such that d f ≥ n. Then, we have

3d 1 (f 0 , f ) + c f 0 * q ∞ κ 1 ℓ f d f + c β κ 2 ℓ 1-2β f d 1+2β f (log ℓ f + log d f + log 2n) n ≥ 3d 1 (f 0 , f ) + f 0 * q ∞ κ 1 ℓ f + c β κ 2 ℓ 1-2β f , ≥ 3d 1 (f 0 , f ) + 2 [-ℓ f ,ℓ f ] f 0 , ≥ 3d 1 (f 0 , f ) + 2(1 -d 1 (f 0 , f )).
The last term being always larger than 2, the risk bound becomes straightforward. To conclude the proof, just remark that

E d 1 (f 0 , f ) ≤ E d 1 (f 0 , f )½ En + E d 1 (f 0 , f )½ E c n ≤ E d 1 (f 0 , f )½ En + 1/n.
5.13. Sketch of the proof of Proposition 12. We explain here how Z n,M (I) is defined.

Thanks to (5), an upper bound of var(Z(I)) is known:

var(Z(I)) ≤ (M/4) κ 1 d|I| + c β κ 2 d 1+2β |I| 1-2β .
It then follows from (the proof of) Theorem 4.2 of [DLLO16] that there exists a multiple δ-sub-Gaussian estimator Z M (I) such that for all δ ∈ (0, n/2 -1log 4), and I ∈ I 1 ,

P Z M (I) -P (X ∈ I) ≤ c M (κ 1 |I| + c β κ 2 |I| 1-2β ) (1 + δ) n ≥ 1 -e -δ ,
where c is a universal constant.

We then set

Z M (I) = min Z M (I), (1/2) M (κ 1 |I| + c β κ 2 |I| 1-2β ) .
By using Claim 2, we get, up to an increase of c, that for all δ > 0 and I ∈ I 1 ,

P Z M (I) -P (X ∈ I) ≤ c M (κ 1 |I| + c β κ 2 |I| 1-2β ) (1 + δ) n ≥ 1 -e -δ .
This defines Z M (I) for all interval I. When I ∈ I ∞ is written as I = d I j=1 I j where d I ∈ N ⋆ , and where I j is an interval such that Īj ∩ Īj ′ = ∅ for all j = j ′ , we set

Z M (I) = d I j=1 Z M ( Īj ).
Finally, Z n,M (I) is defined by

Z n,M (I) = Z M (π 1 (I)) + n j=1 Z M (π j+1 (I) \ π j (I)).
Up to minor modifications, we show the uniform exponential deviation inequality for Z n,M (I) by the same method used in the proof of Proposition 11. The only things that change are the replacement of f 0 * q ∞ by M , the fact that the estimator no longer depends on the confidence level, and that the above sum is truncated to n instead of being infinite. 5.14. Sketch of the proof of Theorem 13. The procedure is the following. We define for f ∈ F ,

γ(f ) = sup I∈I d f I⊂[-ℓ f ,ℓ f ] I f -Z n,M (I) .
We then consider an estimator f ∈ F such that

γ( f ) ≤ inf f ∈F γ(f ) + 1/n.
We may prove a variant of Lemma 1 here to avoid measurability issues. Moreover, the theorem follows from same arguments as the ones used in the proof of Theorem 5. We merely use Proposition 12 in place of Proposition 11.

A. Minimax rates of convergence for decreasing densities

Proposition 14. Suppose Assumption 1 is met and that there exist

κ ′ 1 , κ ′ 2 , κ ′ 3 such that for all t ∈ R, |q ⋆ (t)| -2 ≥ κ ′ 1 + κ ′ 2 |t| 2β and (q ⋆ ) ′ (t) 2 ≤ κ ′ 3 |t| -2β-2
. Let D be the set of densities f that are non-increasing on [0, 1] and such that f ∞ ≤ 1. Then, for n large enough,

inf f sup f 0 ∈D E d 1 (f 0 ½ [0,1] , f ) ≤ C (1/n) 1/(2β+3) inf f sup f 0 ∈D E d 1 (f 0 ½ [0,1] , f ) ≥ c (1/n) 1/(2β+3)
where the infimum is taken over all possible estimators f of f 0 . Moreover, C depends only on κ 1 , κ 2 , β and c depends only on q.

Proof of Proposition 14. We remark that the proof of (8) also entails

E d 1 f 0 ½ [0,1] , fm ≤ 2d 1 (f 0 ½ [0,1] , F m ) + f 0 * q ∞ κ 1 |m| + c β κ 2 |m| 1+2β n , (28)
whenever m is a partition of [0, 1]. Let N be an integer whose value will be made precise later on. We consider here the partition m of size N introduced in [START_REF] Birgé | On the risk of histograms for estimating decreasing densities[END_REF]. It satisfies in particular

d 1 (f 0 ½ [0,1] , F m ) ≤ C/N provided f 0 ½ [0,1]
is non-increasing on [0, 1] and bounded by 1. Here C is a numerical constant.

We then choose N to balance the two terms in the right-hand side of (28).

We now turn our attention to the lower bound. The arguments we propose are inspired by the lower minimax bound of [START_REF] Birgé | Estimating a density under order restrictions: nonasymptotic minimax risk[END_REF] for non-increasing functions in the noise free case. The arguments we propose are inspired by the lower minimax bound of [START_REF] Birgé | Estimating a density under order restrictions: nonasymptotic minimax risk[END_REF] for non-increasing functions in the noise free case. Let p ≥ 1 whose value will be made precise at the end of the proof. We define

ε = log(3/2) p ≤ 1, u = [(1 + ε) p -1] -1 , and λ = 1 + ε u(1 + ε/2) .
For any j ∈ {1, . . . , p}, we introduce

x j = u[(1 + ε) j -1], I j = [x j-1 , x j ) and ℓ j = x j -x j-1 .
Remark that the intervals I j are disjoint and included in [0, 1]. Now, for any j ∈ {1, . . . , p}, define the functions f j and g j as

f j = λ(1 + ε) -j (1 + ε/2)½ [x j-1 ,x j ) , g j = λ(1 + ε) -j+1 ½ [x j-1 ,(x j-1 +x j )/2] + λ(1 + ε) -j ½ ((x j-1 +x j )/2,x j ) .
We denote by ϕ the Cauchy density, introduce for all ν ∈ {0, 1} p ,

φ ν = (1 -log(3/2))ϕ + p j=1 (ν j f j + (1 -ν j )g j ),
and gather all these functions into a set F = {φ ν , ν ∈ {0, 1} p }. We begin by establishing the following inequality:

Claim 7. We have F ⊂ D. Moreover, for any j ∈ {1, . . . , p}, d 1 (f j , g j ) ≥ ε 2 /3.

Proof. For any j ∈ {1, . . . , p}, we observe that the functions f j and g j share the following properties:

• f j and g j are piecewise constant functions, compactly supported on I j .

• for all x ∈ I j and y ∈ I j-1 , max{f j (x), g j (x)} ≤ min{f j-1 (y), g j-1 (y)}. (29)

• f j = g j = ε. • f 1 ∞ ≤ 1/2 and g 1 ∞ ≤ 1/2.
We deduce that φ ν is a density, non-increasing on [0, 1], and bounded by 1. Moreover,

d 1 (f j , g j ) = ℓ j λ(1 + ε) -j ε 2 = ε 2 × 1 2 + ε ≥ 1 3 ε 2 .
In the sequel, to underline the dependency of the density f 0 in the results, we add a subscript to the expectation. More precisely, E f corresponds to the expectation with respect to the variables X i which are assumed to be of density f . We have for all estimator f , sup

f 0 ∈D E f 0 d 1 (f 0 ½ [0,1] , f ) ≥ 1 2 p ν∈{0,1} p E φν d 1 (f 0 ½ [0,1] , f ) ≥ 1 2 p ν∈{0,1} p p j=1 E φν d 1 f ½ I j , φ ν ½ I j ≥ 1 2 inf ν∈{0,1} p p j=1 E φν j,1 d 1 f ½ I j , ((1 -log(3/2))ϕ + f j ) ½ I j +E φν j,0 d 1 f ½ I j , ((1 -log(3/2))ϕ + g j )½ I j ,
where for any ν ∈ {0, 1} p , and k ∈ {0, 1}, ν j,k = (ν 1 , . . . , ν j-1 , k, ν j+1 , . . . , ν p ).

Then, using the triangle inequality, sup

f 0 ∈D E f 0 d 1 (f 0 ½ [0,1] , f ) ≥ 1 2 inf ν∈{0,1} p p j=1 d 1 (f j , g j ) R n min n k=1 φ ν j,1 * q(x k ), n k=1 φ ν j,0 * q(x k ) dx.
Using Claim 7, we get sup

f 0 ∈D E f 0 d 1 (f 0 ½ [0,1] , f ) ≥ ε 2 6 inf ν∈{0,1} p p j=1 R n min n k=1 φ ν j,1 * q(x k ), n k=1 φ ν j,0 * q(x k ) dx. ( 30
)
For any j ∈ {1, . . . , p}, we recall that the χ 2 divergence between φ ν j,1 * q and φ ν j,0 * q is defined as

χ 2 ν (j) = (φ ν j,1 * q -φ ν j,0 * q) 2 φ ν j,0 * q .
It follows from standard results about distance comparisons that

R n min n k=1 φ ν j,1 * q(x k ), n k=1 φ ν j,0 * q(x k ) dx ≥ 1 -(1 + χ 2 ν (j)) n -1 1/2 . ( 31
)
We refer to Chapter 2 of [START_REF] Alexandre | Introduction to nonparametric estimation[END_REF] for the proof of this inequality. We use the claim below whose proof is delayed after the present proof.

Claim 8. There exists c depending only on q such that

sup 1≤j≤p χ 2 ν (j) ≤ c(1/p) 2β+3 .
By choosing p as the smallest integer larger than (2cn) 1/(2β+3) , χ 2 ν (j) ≤ 1/(2n). We now put (30), (31) and the elementary inequality (1 + 1/(2n)) n ≤ e 1/2 together to get sup

f 0 ∈D E f 0 d 1 (f 0 ½ [0,1] , f ) ≥ 1 6 1 -e 1/2 -1 ε 2 p,
which gives the desired result.

Proof of Claim 8. Consider some a such that a -a q(y) dy > 0. For all x ∈ R, j ∈ {1, . . . , p} and ν ∈ {0, 1} p ,

φ ν j,0 * q(x) ≥ (1 -log(3/2))ϕ * q(x), ≥ 1 -log(3/2) π a -a q(y) 1 + (x -y) 2 dy ≥ 1 -log(3/2) π a -a q(y) 1 + 2x 2 + 2a 2 dy.
There exists therefore c 0 (depending only on a and a -a q(y) dy and hence of q) such that

φ ν j,0 * q(x) ≥ 1 c 0 (1 + x 2 )
.

Therefore, for all j ∈ {1, . . . , p}, ν ∈ {0, 1} p χ 2 ν (j) ≤ c 0 (φ ν j,1 * q(x)φ ν j,0 * q(x)) 2 dx + x 2 (φ ν j,1 * q(x)φ ν j,0 * q(x)) 2 dx .

For any j ∈ {1, . . . , p}, let ψ j be the map defined as

ψ j (t) = φ ⋆ ν j,1 (t) -φ ⋆ ν j,0 (t) = f ⋆ j (t) -g ⋆ j (t)
= λε sin(tℓ j /4) t(1 + ε) j e it(x j +m j )/2e it(x j-1 +m j )/2 , where m j = (x j-1 + x j )/2 and ℓ j = x jx j-1 = u(1 + ε) j-1 ε. Then, by using Plancherel isometry,

χ 2 ν (j) ≤ c 0 2π |ψ j q ⋆ | 2 + ψ ′ j q ⋆ + ψ j (q ⋆ ) ′ 2 ≤ c 0 2π |ψ j q ⋆ | 2 + 2 ψ j (q ⋆ ) ′ 2 + 2 ψ ′ j q ⋆ 2 . (32) Moreover, |ψ j q ⋆ | 2 ≤ λ 2 ε 2 (1 + ε) 2j sin(tℓ j /4) t 2 |q ⋆ (t)| 2 dt.
Now, using elementary computations, we get

|ψ j q ⋆ | 2 ≤ c 1 λ 2 (1 + ε) -2j ε 2 ℓ 2β+1 j ,
where c 1 depends on κ ′ 1 , κ ′ 2 and β only. Likewise,

ψ j (q ⋆ ) ′ 2 ≤ c 2 λ 2 (1 + ε) -2j ε 2 ℓ 2β+3 j , ψ ′ j q ⋆ 2 ≤ c 3 λ 2 (1 + ε) -2j ε 2 ℓ 2β+1 j ,
where c 2 depends on κ ′ 3 , β only and where c 3 depends on κ ′ 1 , κ ′ 2 , β only. We finally deduce from (32) that

χ 2 ν (j) ≤ c 4 λ 2 (1 + ε) -2j ε 2 ℓ 2β+1 j ≤ c 5 (1/p) 2β+3
where c 5 depends on q only.

B. Minimax rates of convergence for concave densities

Proposition 15. Suppose Assumption 1 is met and that there exist κ ′ 1 , κ ′ 2 , κ ′ 3 such that for all t ∈ R,

|q ⋆ (t)| -2 ≥ κ ′ 1 + κ ′ 2 |t| 2β and (q ⋆ ) ′ (t) 2 ≤ κ ′ 3 |t| -2β-2
. Let C be the set of densities f that are concave on [0, 1], differentiable on (0, 1), and that satisfy f ∞ ≤ 2, f ′ ½ (0,1) ∞ ≤ 2. Then, there exists c depending only on q such that for n large enough,

inf f sup f 0 ∈C E d 1 (f 0 ½ [0,1] , f ) ≥ c (1/n) 2/(2β+5)
where the infimum is taken over all possible estimators f of f 0 .

We use here the same notation as those introduced in the proof of Proposition 14, except for p (which is an integer whose value, defined later on, will be different from the one in the previous proof). We set

λ-1 = 1 + ε 2 × 1 p p j=1 u 2 2 ε(1 + ε) j-2 + (1 -x j ) u 1 + ε .
We also define for x ∈ R, and j ∈ {1, . . . , p}, fj = λ(1 + ε) -j (1 + ε/2)½ [x j-1 ,x j ) , ḡj = λ(1 + ε) -j+1 ½ [x j-1 ,(x j-1 +x j )/2] + λ(1 + ε) -j ½ ((x j-1 +x j )/2,x j ) , F j (x) =

x -∞ fj (y) dy and G j (x) =

x -∞ ḡj (y) dy.

For ν ∈ {0, 1} p , we set

φν (x) =   1 -log(3/2) - λu 2 ε 3 8(1 + ε) 2 p j=1 (1 + ε) j (1 -ν j )   1/ √ 3 ϕ x/ √ 3 + p j=1 (ν j F j (x) + (1 -ν j )G j (x))½ [0,1] (x).
We gather these functions φν into the set H = { φν , ν ∈ {0, 1} p } and prove:

Claim 9. We have H ⊂ C. Moreover, for all j ∈ {1, . . . , p},

d 1 (F j , G j ) ≥ 0.3ε 3 .
Proof of Claim 9. Elementary but tedious computations give

λ-1 = (1 + ε/2)u 2(1 + ε) log(3/2) [2 log(3/2)(1 + u) -2 -ε] . Moreover, 0.3 ≤ λu 2 8(1 + ε) 2 ≤ λu 2 8(1 + ε) 2 (1 + ε) p ≤ 0.8. ( 33
)
Note now that ϕ(•/ √ 3) is concave on [0, 1] and

1 -log(3/2) - λu 2 ε 3 8(1 + ε) 2 p j=1 (1 + ε) j (1 -ν j ) ≥ 1 -log(3/2) -0.8ε 3 p > 0.
Moreover, for all x ∈ [0, 1],

φν (x) =   1 -log(3/2) - λu 2 ε 3 8(1 + ε) 2 p j=1 (1 + ε) j (1 -ν j )   1/ √ 3 ϕ x/ √ 3 + x -∞ p j=1 ν j fj (t) + (1 -ν j )ḡ j (t) dt.
As in (29), max{ fj (x), ḡj (x)} ≤ min{ fj-1 (y), ḡj-1 (y)}, for all x ∈ I j and y ∈ I j-1 . This implies that the sum in the integrate above is non-increasing and that φν is concave on [0, 1]. Besides, the map in the integrate is bounded from above by λ. Some computations show that this quantity is not greater than 0.95. In particular, φν is differentiable on (0, 1) and | φ′ ν | is bounded from above by a constant smaller than 1.1. The mean value theorem implies that | φν (x)| ≤ 1.3 < 2 for all x ∈ [0, 1] and the same result is true for x ∈ [0, 1]. Now,

I j F j (x) dx = λ(1 + ε) -j (1 + ε/2) ℓ 2 j 2 ,
and

1 0 F j (x) dx = I j F j (x) dx + (1 -x j )F j (x j ) = λε(1 + ε/2) u 2 2 ε(1 + ε) j-2 + (1 -x j ) u 1 + ε . Therefore, (34)
p j=1 1 0 F j (x) dx = λε(1 + ε/2) p j=1 u 2 2 ε(1 + ε) j-2 + (1 -x j ) u 1 + ε = εp = log(3/2).
We define the triangle function

ζ(x) = (1 -|x|)½ [-1,1] (x) and remark that (35) H j (x) = G j (x) -F j (x) = λεℓ j 4(1 + ε) j ζ 2(x -m j ) ℓ j .
In particular, since

G j (x) = F j (x) for all x ∈ [0, 1], [0,1] (G j -F j ) = R (G j -F j ) = λεℓ j 4(1 + ε) j R ζ 2(x -m j ) ℓ j dx, = λεℓ 2 j 8(1 + ε) j , = λu 2 8 ε 3 (1 + ε) j-2 .
This result, combined with (34), entails that φν is a density. It also gives as ζ ≥ 0,

d 1 (F j , G j ) = λu 2 8(1 + ε) 2 (1 + ε) j ε 3 ≥ λu 2 8(1 + ε) 2 ε 3 ≥ 0.3ε 3 .
By using usual techniques (see Appendix A for instance) we get for all estimator f , sup

f 0 ∈C E f 0 d 1 (f 0 ½ [0,1] , f ) ≥ 1 2 inf ν∈{0,1} p p j=1 E φν j,1 I j | f -φν j,1 | + E φν j,0 I j | f -φν j,0 | , ≥ 1 2 inf ν∈{0,1} p p j=1 I j | φν j,1 -φν j,0 | × 1 -((1 + χ2 ν (j)) n -1) 1/2 , (36)
where χ2 ν (j) = ( φν j,1 * qφν j,0 * q) 2 φν j,0 * q .

By using the triangle inequality,

I j | φν j,1 -φν j,0 | ≥ d 1 (F j , G j ) - λu 2 ε 3 8(1 + ε) 2 (1 + ε) j I j ϕ ≥ 0.3ε 3 -0.13 λu 2 ε 3 8(1 + ε) 2 (1 + ε) j ℓ j ≥ 0.3ε 3 -0.13 × 0.8ε 4 u(1 + ε) j-1 .
By using ε = log(3/2)/p, the definition of u, and elementary computations, we get

I j | φν j,1 -φν j,0 | ≥ 0.15ε 3 .
We deduce from (36), sup

f 0 ∈C E f 0 d 1 (f 0 ½ [0,1] , f ) ≥ 0.07ε 3 inf ν∈{0,1} p p j=1 1 -((1 + χ2 ν (j)) n -1) 1/2 .
We need the following result:

Claim 10. There exists c depending on q only such that: for all ν ∈ {0, 1} p ,

sup 1≤j≤p χ2 ν (j) ≤ c(1/p) 2β+5 .
By choosing p as the smallest integer than (2cn) 1/(2β+5) , χ2 ν (j) becomes not larger than 1/(2n). In particular, sup

f 0 ∈C E f 0 d 1 (f 0 ½ [0,1] , f ) ≥ 0.07 1 -e 1/2 -1 ε 3 p,
which concludes the proof of Proposition 15.

Sketch of the proof of Claim 10. It follows from the proof of Claim 8 that there is some c 0 depending only on q such that χ2 ν (j) ≤ c 0 ( φν j,1 * q(x)φν j,0 * q(x)) 2 dx + x 2 ( φν j,1 * q(x)φν j,0 * q(x)) 2 dx .

Let ψj be defined for j ∈ {1, . . . , p} and t ∈ R by ψj

(t) = φ⋆ ν j,1 (t) -φ⋆ ν j,0 (t), = F ⋆ j (t) -G ⋆ j (t) + λu 2 ε 3 8 ϕ ⋆ t √ 3 (1 + ε) j-2 .
Let ζ be the triangle function introduced in the proof of the preceding claim. Since ζ ⋆ (t) = 4 sin 2 (t/2)/t 2 for all t ∈ R, we deduce from (35),

ψj (t) = - λεℓ j 4(1 + ε) j ζ 2(. -m j ) ℓ j ⋆ (t) + λu 2 ε 3 8 ϕ ⋆ t √ 3 (1 + ε) j-2 , = - 2 λε (1 + ε) j sin 2 (tℓ j /4) t 2 e itm j + λu 2 ε 3 8 e - √ 3|t| (1 + ε) j-2 = 2 λε (1 + ε) j - sin 2 (tℓ j /4) t 2 e itm j + ℓ 2 j 16 e - √ 3|t| .
As for (32),

χ2 ν (j) ≤ c 0 2π | ψj q ⋆ | 2 + 2 | ψj (q ⋆ ) ′ | 2 + 2 | ψ′ j q ⋆ | 2 .
There exists C 1 depending only on κ ′ 1 , κ ′ 2 such that

| ψj q ⋆ | 2 ≤ C 1 λ2 ε 2 (1 + ε) 2j sin(tℓ j /4) t 4 1 1 + |t| 2β dt + ℓ 4 j .
By noticing that λ ≤ 0.95, ℓ j ≤ 3ε, we get

| ψj q ⋆ | 2 ≤ C ′ 1 ε 2β+5 ,
where C ′ 1 only depends on β, κ ′ 1 , κ ′ 2 . By doing quite similar computations,

| ψj (q ⋆ ) ′ | 2 ≤ C 2 ε 2β+5 , | ψ′ j q ⋆ | 2 ≤ C 3 ε 2β+5 ,
where C 2 , C 3 only depend on β, κ ′ 1 , κ ′ 2 , κ ′ 3 . By gathering these results, we deduce χ2 ν (j) ≤ C ′ ε 2β+5 , and it remains to say that ε = log(3/2)/p.

C. Approximation results

In this section, we group together two elementary approximation results that were required in the proofs of Theorems 6 and 7 and that we have not been able to find in the literature. Their proofs are given in Sections C.1 and C.2 below. Lemma 4. Let ℓ ≥ 1 and f be a density such that f ½ [-ℓ,ℓ] ∈ F r . Then, for all positive integer k, there exists a compactly supported density f ∈ F r ∩ P 3k+3r on [-ℓ, ℓ] such that

d 1 (f ½ [-ℓ,ℓ] , f ) ≤ 10 L 1 (f ½ [-ℓ,ℓ] ) k + [-ℓ,ℓ] c f.
Lemma 5. Let ℓ ≥ 1 and f be a density such that f ½ [-ℓ,ℓ] ∈ C r . Then, for all positive integer k, there exists a compactly supported density f ∈ C r ∩ Q 24k+24r on [-ℓ, ℓ] such that:

d 1 (f ½ [-ℓ,ℓ] , f ) ≤ 230 L 2 (f ½ [-ℓ,ℓ] ) k 2 + [-ℓ,ℓ] c f. C.1. Proof of Lemma 4
Claim 11. Let ε ≥ 0, k ≥ 1, and f be a non-negative continuous monotone function compactly supported on a closed interval I of finite length. There exist a partition m of I of the form

m = {[a 0 , a 1 ], (a 1 , a 2 ], . . . , (a 3k-1 , a 3k ]}
such that for all j, either

• a j+1 -a j ≤ |I|/k, |f (a j+1 ) -f (a j )| ≤ V I (f )/(k(1 + ε) k ), • or |f (a j+1 ) -f (a j )| ≤ ε min{f (a j ), f (a j+1 )}.
In particular, for all j,

(a j+1 -a j )|f (a j+1 ) -f (a j )| ≤ max |I|V I (f ) k 2 (1 + ε) k , ε a j+1 a j f .
Proof. We only prove the claim when f is non-decreasing on

I = [a, b]. Note that V I (f ) = f (b) -f (a)
. For all j ∈ {0, . . . , k}, there exists b j ∈ (a, b] such that

f (b j ) -f (a) = V I (f ) (1 + ε) k-j . Here, we set b k = b. This defines a partition of [b 0 , b] of size k such that f (b j+1 ) -f (b j ) ≤ ε (f (b j ) -f (a)) ≤ εf (b j ). Since V [a,b 0 ] (f ) ≤ V [a,b] (f )/(1 + ε) k ,
we may apply Lemma 8 of [START_REF] Baraud | ρ-estimators for shape restricted density estimation[END_REF] to define a partition of [a, b 0 ] of size 2k fulfilling the requirements of the first point. We then concatenate the two partitions.

Claim 12. Let f be a non-negative monotone function on an interval I of finite length such that I f ≤ 1. For all k, there exists a non-negative monotone function f that is piecewise constant on a partition of I into 3k intervals such that

d 1 (f ½ I , f ) ≤ 5 log (1 + |I|V I (f )) k .
Proof. Without loss of generality, we assume that f is non-decreasing on I. When V I (f ) = 0, or V I (f ) = +∞ the proof is straightforward. We now assume that V I (f ) = 0 and V I (f ) = ∞.

In particular f is bounded. We moreover suppose that f is continuous.

We extend f by continuity at the endpoints of Ī if needed. In particular, VĪ (f ) = V I (f ), and we may therefore assume I to be closed. Let m = {[a 0 , a 1 ], (a 1 , a 2 ], . . . , (a 3k-1 , a 3k ]} be the partition of I given by the preceding claim and

f = f (a 0 )½ [a 0 ,a 1 ] + 3k j=2 f (a j-1 )½ (a j-1 ,a j ] .
We have, We use the elementary inequalities x ≤ (1/(log 2)) log(1 + x) for all x < 1, and 2 log(x) + 1 ≤ (1/(log 2)) log(1 + x) for all x ≥ 1 to get whatever |I|V I (f ),

d 1 (f ½ I , f ) ≤ 3k j=1 (f (a j ) -f (a j-1 )) (a j -a j-1 ), ≤ 3 |I|V I (f ) k(1 + ε) k + ε I f, ≤ 3 |I|V I (f ) k(1 + ε) k + ε. If |I|V I (f ) ≤ 1, we set ε = 0 and get the bound d 1 (f ½ I , f ) ≤ 3|I|V I (f )/k. If |I|V I (f ) > 1, we define ε such that |I|V I (f ) (1 + ε) k = 1. The bound becomes d 1 (f ½ I , f ) ≤ 3 k + e 1
d 1 (f ½ I , f ) ≤ 3 log (1 + |I|V I (f )) k log 2 .
Suppose now that f is not continuous and let η = (5 -3/ log 2) log (1 + |I|V I (f )) /k > 0.

Then, there exists a continuous non-negative monotone function g vanishing outside I such that d 1 (f ½ I , g) ≤ η and V I (g) ≤ V I (f ). We apply the above proof to g to get

d 1 (f ½ I , f ) ≤ 5 log (1 + |I|V I (f )) k .
Proof of Lemma 4. We write f ½ [-ℓ,ℓ] = r j=1 f I j ½ I j ∈ F r . Let α = k/(L 1 (f ½ [-ℓ,ℓ] )) 1/2 and k j be the smallest integer such that k j ≥ α log 1/2 1 + |I j |V I j (f I j ) .

The preceding claim shows that there is a monotone piecewise constant function ḡj based on a partition of I j into 3k j intervals such that d 1 (f I j , ḡj ) ≤ 5 log 1 + |I j |V I j (f I j ))

k j ≤ 5 (L 1 (f ½ [-ℓ,ℓ]
)) 1/2 log 1/2 1 + |I j |V I j (f I j ) k .

Therefore, ḡ = r j=1 ḡj is based on at most 3k + 3r intervals and satisfies

d 1 (f ½ [-ℓ,ℓ] , ḡ) ≤ 5 k (L 1 (f ½ [-ℓ,ℓ] )) 1/2
d 1 (f ½ [-ℓ,ℓ] , f ) ≤ [-ℓ,ℓ] f + 1 ≤ 2 [-ℓ,ℓ] f + [-ℓ,ℓ] c f ≤ 10(L 1 (f ½ [-ℓ,ℓ] ))/k + [-ℓ,ℓ] c
f by (37).

If ḡ = 0, we set f = ( [-ℓ,ℓ] ḡ) -1 ḡ and deduce:

d 1 (f ½ [-ℓ,ℓ] , f ) ≤ d 1 (f ½ [-ℓ,ℓ] , ḡ) + ḡ -1 ≤ d 1 (f ½ [-ℓ,ℓ] , ḡ) + ḡ - [-ℓ,ℓ] f + [-ℓ,ℓ] c f ≤ 2d 1 (f ½ [-ℓ,ℓ] , ḡ) + [-ℓ,ℓ] c f.
The conclusion then follows from (37). Proof. Without loss of generality, assume that f is non-increasing. If f is either non-negative or non-positive we apply Claim 11 to f or -f . Otherwise, f is non-positive on I 1 and nonnegative on I 2 . We may then apply Claim 11 to f ½ I 1 and f ½ I 2 and gather the results.

Lemma 6. Let I be an interval of finite length and f be a map vanishing outside I such that f I is non-negative, either convex or concave, and I f ≤ 1. Then, for all positive integer k, there exists a map f such that:

• f vanishes outside I,

• f ½ I is a piecewise affine function based on a partition m of I into at most 24k intervals,

• f ½ I is either convex or concave,

• d 1 (f ½ I , f ) ≤ 115log 2 1 + |I| 2 V I (f ′ ) /k 2 .
Proof of Lemma 6. When V I (f ′ ) = ∞, there is nothing to prove, and we therefore assume that V I (f ′ ) < ∞. This in particular implies that f ′ is bounded on I. Since f I is monotone on at most 2 pieces, we may split the study into two parts, each part being applied to the interval on which the function is monotone. It then remains to gather the results. We propose in the sequel to deal only with the case where f ½ I is monotone.

We now assume f to be continuously differentiable on I. In particular, we may always modify f at the endpoints of Ī to make it continuously differentiable on Ī. We may therefore suppose without loss of generality that I is closed.

We apply Claim 13 to f ½ I and f ′ ½ I to get two partitions m 1 and m 2 of I. We then define the partition By using (39) and then (38),

m = {J 1 ∩ J 2 , (J 1 , J 2 ) ∈ m 1 × m 2 } = {[c 0 , c
2 c j+1 c j f (x) -f (x) dx ≤ max |I|V I (f ′ ) k 2 (1 + ε) k , ε |f (c j+1 ) -f (c j )| (c j+1 -c j ) ≤ max |I|V I (f ′ ) k 2 (1 + ε) k (c j+1 -c j ), ε |I|V I (f ) k 2 (1 + ε) k , ε 2 c j+1 c j f . Therefore, 2d 1 (f ½ I , f ) ≤ r-1 j=0 max |I|V I (f ′ ) k 2 (1 + ε) k (c j+1 -c j ), ε |I|V I (f ) k 2 (1 + ε) k , ε 2 c j+1 c j f ≤ |I| 2 V I (f ′ ) k 2 (1 + ε) k + 12ε |I|V I (f ) k(1 + ε) k + ε 2 .
By using V I (f ) ≤ |I|V I (f ′ ) and the inequality xy ≤ (x 2 + y 2 )/2,

2d 1 (f ½ I , f ) ≤ |I| 2 V I (f ′ ) k 2 (1 + ε) k + 6 |I| 2 V I (f ′ ) k(1 + ε) k 2 + 7ε 2 .
If |I| 2 V I (f ′ ) ≤ 1, we set ε = 0 and get

2d 1 (f ½ I , f ) ≤ 7 |I| 2 V I (f ′ ) k 2 .
If |I| 2 V I (f ′ ) > 1, we define ε such that

|I| 2 V I (f ′ ) (1 + ε) k = 1. We derive, 2d 1 (f ½ I , f ) ≤ 7 e log(|I| 2 V I (f ′ ))/k -1 2 + 7/k 2 .
Using now that e log(x)/k ≤ 2 log(x)/k for all k ≥ log x and d 1 (f

½ [0,1] , f ) ≤ 2, 2d 1 (f ½ I , f ) ≤ 7 4 log 2 (|I| 2 V I (f ′ )) + 1 k 2 .
We then use V I (f ′ ) = V I (f ′ ) and the elementary inequalities 57 log 2 (1 + √ x) ≥ 7/2x for all

x ≤ 1, 57 log 2 (1 + √ x) ≥ 14 log 2 (x) + 7/2 for all x ≥ 1 to get

d 1 (f ½ I , f ) ≤ 57 log 2 1 + |I| 2 V I (f ′ )
k 2 when f ½ I is monotone and continuously differentiable on I.

Suppose now that f ½ I is not continuously differentiable and consider η > 0. There exists a continuously differentiable monotone function that is either convex or concave on I, vanishing outside I, and such that d 1 (f ½ I , g) ≤ η. Moreover, V I (g ′ ) ≤ V I (f ′ ). We apply the lemma to g and use the triangular inequality with η small enough.

Proof of Lemma 5. We write f ½ [-ℓ,ℓ] = r j=1 f I j ½ I j , define α = k/(L 2 (f ½ [-ℓ,ℓ] )) 1/3 and consider the smallest integer k j such that k j ≥ α log 1/3 1 + |I j | 2 V Ij (f ′ I j ) , and the map ḡj given by Lemma 6. We have,

d 1 (f I j ½ I j , ḡj ) ≤ 115 log 2 1 + |I j | 2 V Ij (f ′ I j ) k 2 j ≤ 115 (L 2 (f ½ [-ℓ,ℓ] )) 2/3 log 2/3 1 + |I j | 2 V Ij (f ′ I j ) k 2 .
Therefore, ḡ = r j=1 ḡj satisfies d 1 (f ½ [-ℓ,ℓ] , ḡ) ≤ 115(L 2 (f ½ [-ℓ,ℓ] ))/k 2 . We then define f from ḡ as in the proof of Lemma 4.

F r =

 = I∈m f I ½ I , where m ∈ M r and f I is a non-negative monotone function on I . (14)

  where m ∈ M r and f I is either a convex or a concave (17) non-negative function on I , and for k ≥ 1, Q k = I∈m f I ½ I , where m ∈ M k and where f I is an affine function such that f = I∈m f I ½ I is a density . It follows from Proposition 5 of [BB16] that the set F defined as

  dt as wished. 5.4. Proof of Proposition 2. For any I ∈ I d , we can always write I = ∪ k j=1 I j where k ≤ d and where the I j are disjoint intervals. Then

  where we have used k ≤ d, k j=1 |I j | = |I| and Lemma 2 with γ = 2β to conclude.

k

  log(|I|V I (f )) -1.Using the boundse (1/k) log(|I|V I (f )) -1 ≤ 2 log(|I|V I (f ))/k when k ≥ log(|I|V I (f )) d 1 (f ½ I , f ) ≤ 2 when k ≤ log(|I|V I (f ))we getd 1 (f ½ I , f ) ≤ 2 log |I|V I (f ) + 3 k .

  2 (1 + |I j |V I j (f I j )).Since this inequality holds for anym ∈ M r s.t. f = I∈m f I ½ I ∈ F r we obtain d 1 (f ½ [-ℓ,ℓ] , ḡ) ≤ 5 k L 1 (f ½ [-ℓ,ℓ] ). (37)If ḡ = 0, we define f as an arbitrary density on [-ℓ, ℓ]. Then,

C. 2 .

 2 Proof of Lemma 5 Claim 13. Let ε ≥ 0, k ≥ 1, and f be a continuous monotone function compactly supported on a closed interval I of finite length. There exists a partition m of I of the formm = {[a 0 , a 1 ), [a 1 , a 2 ), . . . , [a 6k-1 , a 6k ]} such that for all j, (a j+1a j )|f (a j+1 )f (a j )| ≤ max |I|V I (f ) k 2 (1 + ε) k , ε(a j+1a j ) min{|f (a j )|, |f (a j+1 )|} .Moreover, f is either non-negative or non-positive on each interval [a j , a j+1 ].

  1 ), [c 1 , c 2 ), . . . , [c r-1 , c r ]} with r ≤ 12k.Since m is thinner than m 1 we deduce:(c j+1c j )|f (c j+1 )f (c j )| ≤ max |I|V I (f ) k 2 (1 + ε) k , ε(c j+1c j ) min{f (c j ), f (c j+1 )} , ≤ max |I|V I (f ) k 2 (1 + ε) k , ε c j+1 c j f . (38)Moreover, m is thinner than m 2 and thus(c j+1c j )|f ′ (c j+1 )f ′ (c j )| ≤ max |I|V I (f ′ ) k 2 (1 + ε) k , ε(c j+1c j ) min{|f ′ (c j )|, |f ′ (c j+1 )|} .Using that f ′ is either non-negative or non-positive on [c j , c j+1 ],(c j+1c j )|f ′ (c j+1 )f ′ (c j )| ≤ max |I|V I (f ′ ) k 2 (1 + ε) k , ε |f (c j+1 )f (c j )| . (39)We approximate f by the piecewise affine functionf (x) = r-1 j=0 f ′ (u j )(xc j ) + f (c j ) ½ [c j ,c j+1 ) (x), where u j ∈ [c j , c j+1 ] is such that f ′ (u j )(c j+1c j ) + f (c j ) = f (c j+1 ). Thereby, f ½ I is either convex or concave. For all x ∈ [c j , c j+1 ), f (x)f (x) ≤ x c j f ′ (u j )f ′ (t) dt ≤ f ′ (c j )f ′ (c j+1 ) (xc j ) , )f (x) dx ≤ f ′ (c j )f ′ (c j+1 ) (c j+1c j ) 2 .