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

DENSITY ESTIMATION UNDER LOCAL DIFFERENTIAL PRIVACY AND HELLINGER LOSS

Keywords: Mathematics Subject Classification. 62G05, 62G07 density estimation, minimax estimation, local differential privacy, Besov spaces

In this paper, we carry out a piecewise constant estimator of the density for privatised data. We establish a non-asymptotic oracle inequality for the Hellinger loss and deduce that our estimator is adaptive and (almost) rate optimal over a wide range of Besov classes. In particular, we show that a lower bound condition improves the convergence rates. This is in contrast to what happens with the L 2 loss where the rates can differ depending on whether the density is bounded or not.

Introduction

In this paper, we are interested in estimating the distribution of a random variable X with values in [0, 1]. Usually, n independent copies X 1 , . . . , X n of X are available to the statistician. This is no longer true in the framework we consider here where the data are protected by a privacy mechanism. This mechanism is known by the statistician and consists in transforming X into a new random variable Y with values in a measurable space (Y, E). The conditional probability distribution of Y given X, denoted by Q(• | X) in the sequel, is assumed to satisfy the following inequality for some α ∈ [0, +∞] and for all x, x ′ ∈ [0, 1],

sup A∈E Q(A | X = x ′ ) Q(A | X = x) ≤ e α . (1)
The parameter α thus tunes the level of privacy. In the limiting case α = 0, Y is independent of X and it it is not possible to retrieve information about X from Y . Conversely, if α = ∞, no confidentiality is guaranteed as Y = X suits. The aim of the paper is to estimate the distribution of X from the observation of n independent copies Y 1 , . . . , Y n of Y . This statistical setting corresponds to that of the estimation of the distribution under local α-differential privacy (without interaction). When X admits a density f with respect to the Lebesgue measure, estimating the distribution of X amounts to estimating f . We may then measure the quality of an estimator f by considering a class F , a loss function L (•, •), and by examining the maximal risk

R α (F , f , L ) = sup f ∈F E L (f, f )
of the estimator when f lies in F . This quantity may be compared to the minimax risk

R α (F , L ) = inf f ,Q sup f ∈F E L (f, f ) ,
where the infimum is taken over all privacy mechanisms Q satisfying (1) and all estimators f based on the privatised data Y 1 , . . . , Y n . An estimator f is then said to be rate optimal, or minimax, if R α (F , f , L ) and R α (F , L ) tends to 0 at the same rate when the sample size n goes to infinity.

In the literature, different estimation methods have been proposed. We may cite histogram estimators [START_REF] Wasserman | A statistical framework for differential privacy[END_REF][START_REF] Györfi | Multivariate density estimation from privatised data: universal consistency and minimax rates[END_REF], projection estimators [START_REF] Wasserman | A statistical framework for differential privacy[END_REF][START_REF] John C Duchi | Minimax optimal procedures for locally private estimation[END_REF], Kernel estimators [START_REF] Hall | Differential privacy for functions and functional data[END_REF][START_REF] Kroll | On density estimation at a fixed point under local differential privacy[END_REF] and wavelets estimators [START_REF] Butucea | Local differential privacy: Elbow effect in optimal density estimation and adaptation over besov ellipsoids[END_REF]. We focus here on density estimation but other topics have been explored in the private setup. Here are a few of them. The estimation of a functional of f is carried out in [BRS20, RS20, BI21], goodness-of-fit tests are developed in [START_REF] Lam-Weil | Minimax optimal goodness-of-fit testing for densities and multinomials under a local differential privacy constraint[END_REF][START_REF] Dubois | Goodness-of-fit testing for hölder continuous densities under local differential privacy[END_REF], the estimation of the spectral density is done in [START_REF] Kroll | Adaptive spectral density estimation by model selection under local differential privacy[END_REF], and the questions about regression and classification discussed in [START_REF] Thomas B Berrett | Strongly universally consistent nonparametric regression and classification with privatised data[END_REF] and in the references therein.

The minimax rates have been established in the aforementioned papers (sometimes up to logarithmic factors) when L = d q q is the q th power of the L q distance d q , and when F is a class corresponding to smoothness assumptions on the density. A standard way to measure this regularity is to use bounded subsets F = B β p,∞ (R) of Besov spaces B β p,∞ . The subscript p indicates in which (quasi) norm the regularity β is measured, and R is an upper-bound of the Besov (quasi) semi-norm of the maps f ∈ B β p,∞ (R). The most complete results we know on this subject are due to [START_REF] Butucea | Local differential privacy: Elbow effect in optimal density estimation and adaptation over besov ellipsoids[END_REF]. They prove a lower and upper bound on the minimax risk either when p ≥ q, or when p ∈ [1, q), β > 1/p. These two bounds coincide, within possible logarithmic factors. The estimation procedure they propose is adaptive with respect to β, p but involves an upper bound R of the Besov semi-norm of f . Let us mention that adaptive density estimation procedures are rather scarce in the literature, the only other one we know of being that of [START_REF] Kroll | On density estimation at a fixed point under local differential privacy[END_REF]. Like the previous one, his procedure involves an upper-bound of an a priori unknown parameter (the supremum norm f ∞ of f ).

In this paper, we propose a new estimator, fully data driven, and (nearly) rate optimal. We also pay special attention to the loss L = h 2 defined for f 1 , f 2 by

h 2 (f 1 , f 2 ) = 1 2 f 1 (x) -f 2 (x) 2 dx.
This Hellinger loss h has been widely used in direct density estimation, that is when α = ∞.

It has also been used in other frameworks such as the estimation of the intensity of a Poisson process, the conditional density, the hazard rate, the transition intensity of a Markov chain or a Markovian process, the means of non-negative data, see [START_REF] Baraud | Estimating the intensity of a random measure by histogram type estimators[END_REF][START_REF] Baraud | Estimator selection with respect to hellinger-type risks[END_REF][START_REF] Sart | Estimating a density, a hazard rate, and a transition intensity via the ρestimation method[END_REF] for some references. One of the goals of this manuscript is to find out the minimax rates for h 2 under smoothness constraints in an inverse problem context.

We thus propose an estimation procedure adapted to this Hellinger loss. The resulting estimator is piecewise constant on a possibly irregular partition. This partition may be very thin locally to adapt if needed to the irregularities or singularities of the density. Even if a piecewise constant estimator may lack smoothness, this approach allows to estimate densities that do not fit in the assumptions of the previous procedures. It also yields new theoretical results on the minimax rates, mainly under the Hellinger loss, but also some under the L 2 loss.

More precisely, we show that R α (F , h 2 ) converges at the rate n -β/(2β+2) (up to log factors) when F = B β p,∞ (R) for some p > 0, β ∈ ((1/p -1) + , 1). In the literature of estimation under Hellinger loss, the smoothness assumption is traditionally put on √ f in place of f . This is the reason why we also study the minimax risk when F corresponds to a class of densities whose square roots belong to B β p,∞ (R) for some p > 0 and β ∈ ((1/p -1/2) + , 1). We show that the minimax rate is faster in this case and it is equal to n -β/(2β+1) (to within log factors).

We can also infer from our estimation procedure new results on the

L 2 minimax risk R α (F , d 2 2 ) when F ⊂ B β p,∞ (R) with p ∈ [1, 2) and β ∈ ((1/p-1) + , 1/p].
We first suppose that the functions of F are uniformly bounded from above. We then prove that the minimax rate is, to within logarithmic factors, n -ψ where

ψ = β/(β + 1) if β > 2/p -1, βp/2 if β ≤ 2/p -1.
When the boundedness assumption is removed, the minimax rate may be slower. Actually, it cannot be faster than n -(β-1/p+1/2)/(β-1/p+1) > n -βp/2 when F = B β p,∞ (R) and β ∈ (1/p -1/2, 2/p -1). The upper bound condition f ∞ < ∞ plays thus an important role in the estimation under the L 2 loss. This was already true for raw data, see [START_REF] Birgé | Model selection for density estimation with L 2 -loss[END_REF] for more details. However, the elbow phenomenon that occurs here when the function is bounded did not arise in direct estimation.

As to the Hellinger loss, the optimal rates can be boosted under a lower bound condition 1/f ∞ < ∞. We show indeed that the minimax risk R α (F , h 2 ) converges at the rate n -ψ (to within log factors) when F ⊂ B β p,∞ (R) only gathers maps uniformly bounded from below (with p > 0, β ∈ ((1/p -1) + , 1)). The same result holds true when the smoothness assumption is put on √ f in place of f (at least when β ∈ ((1/p -1/2) + , 1)). Note that the two preceding classes F may contain unbounded densities (which may even be not square integrable). However, there is no additional gain to be expected if we restrict the classes F to bounded densities.

Throughout the paper, we will use the following notation. For all map f , set F and distance d, d(f, F ) = inf g∈F d(f, g). The cardinal of a finite set I is denoted by |I|. The same notation is used for the length of an interval I. The letters c, C, . . . stand for quantities that may change from line to line. This manuscript is organized as follows. We carry out our privacy mechanism, our estimation procedure as well as a non-asymptotic risk bound in Section 2. We present new results on the minimax rates in Section 3. The proofs are deferred in Section 4.

Privacy mechanism and estimation procedure

We begin by explaining how to simulate our sanitized version Y of X. We then consider specific partitions of [0, 1] that are involved in our estimation procedure. Lastly, we carry out our main theoretical result.

2.1. Privacy mechanism. We use a quite standard anonymization technique. More precisely, we suppose in the sequel that n ≥ 3, consider j ∈ {0, . . . , n} and define the regular partition mj of [0, 1] of size 2 j by mj = k2 -j , (k + 1)2 -j , k ∈ {0, . . . , 2 j -2}

(2 j -1)2 -j , 1 .

For each I ∈ mj , we generate a new real valued random variable W (I), independent of the others, and whose density is given for x ∈ R by

q(x) = 1 2 e -|x| .
We then consider the level α ∈ (0, ∞] of protection, set δ = 1/ log(log n), and introduce for j ∈ {0, . . . , n}, I ∈ mj ,

Y (I) = ½ I (X) + 2(1 + 1/δ)(1 + j) 1+δ α W (I). (2)
In this equality, the fraction is equal to 0 if α = ∞. We finally define the confidential version Y of X by Y = (Y (I)) I∈∪ j∈{0,...,n} mj . We show in Section 4.1:

Proposition 1. For all α ∈ (0, ∞], the conditional distribution Q(• | X) of Y given X satis- fies (1).

Collection of partitions.

We introduce tree-structured partitions m of [0, 1] that are well suited to approximate smooth functions by piecewise constant maps. They follow from the recursive algorithm of [START_REF] Ronald | Degree of adaptive approximation[END_REF] described below.

Let I be the collection of intervals I of [0, 1] that are either of the form [a, b) with a < b < 1 or of the form [a, 1] with a < 1. Each I ∈ I can be divided into two intervals π 1 (I), π 2 (I) ∈ I of the same size. We then have

I = π 1 (I) ∪ π 2 (I) with |π 1 (I)| = |π 2 (I)| = |I|/2.
Let m be a partition of [0, 1] into intervals I of I . We define the collection

M(m) = m ′ ⊂m (m \ m ′ ) ∪ π 1 (I), π 2 (I), I ∈ m ′
of all partitions that can be obtained from m by splitting some of its intervals into two equal parts. We can now define collections M ℓ of partitions by induction by setting

M 0 = {{[0, 1]}}, M ℓ = M ℓ-1 ∪ m∈M ℓ-1 M(m),
and

M ∞ = ℓ≥0 M ℓ .
The partitions m of M ℓ are therefore composed of dyadic intervals whose length is between 2 -ℓ and 1. The parameter ℓ indicates the maximal thinness of these intervals. Note that M ℓ contains the regular partitions mj with j ≤ ℓ. It also contains partitions that are very thin locally and wider elsewhere.

Estimation procedure.

We now aim at estimating the density f from the observation of n independent copies Y 1 , . . . , Y n of Y .

Consider some ℓ ∈ {1, . . . , n} and m ∈ M ℓ . The probability P (X ∈ I) can be estimated for each interval I ∈ m by

P n (I) = 1 n n i=1 Y i (I).
We may then gather these estimations to define the standard piecewise constant estimator fm =

I∈m P n (I) |I| ½ I .
Note that fm may be non-positive in which case h 2 (f, fm ) is not defined. Since f is non-negative, it is natural to correct this problem by replacing fm by its positive part fm = ( fm ) + .

How to choose this partition m remains to be decided. The solution we propose below is to use a Lespki-type procedure [START_REF] Lepski | Asymptotically minimax adaptive estimation. i: Upper bounds. optimally adaptive estimates[END_REF] modified as in [START_REF] Sart | Estimation of the transition density of a Markov chain[END_REF][START_REF] Sart | Minimax bounds for besov classes in density estimation[END_REF] for computational reasons.

We introduce for each interval I ∈ I ,

ρ I = 2(1 + 1/δ)(1 + log 2 (1/|I|)) 1+δ α log(n/|I|) n , (3)
where log 2 denotes the logarithm base 2, where δ = 1/ log(log n) as defined previously, and where the fraction equals 0 if α = ∞. We define for all m ∈ M ℓ and interval J ∈ I , the partition m ∨ J = {I ∩ J, I ∈ m} of J induced by m. For all collection m of disjoint intervals I ∈ I of ∪ j∈{0,...,n} mj , we set pen(m) =

I∈m ρ I > log n n ρ 2 I max{P n (I), ρ I } + I∈m ρ I ≤ log n n ρ I + |m| n .
We consider some κ > 0 and define our criterion γ(•) for m ∈ M ℓ by

γ(m) = J∈m sup m ′ ∈M ℓ h 2 ( fm ½ J , fm∨m ′ ½ J ) -κ pen(m ′ ∨ J) .
We define m as any partition m ∈ M ℓ satisfying

γ( m) + (3/2)κ pen( m) = inf m∈M ℓ {γ(m) + (3/2)κ pen(m)} , (4)
and estimate f by

f = min 1, f m -1 f m. (5)
2.4. A non-asymptotic risk bound. We show in Section 4.2: Theorem 2. Let ℓ ∈ {1, . . . , n}. There exists a universal constant κ 0 such that if κ ≥ κ 0 , the preceding estimator f satisfies

E h 2 (f, f ) ≤ C inf m∈M ℓ h 2 (f, F m ) + κυ m . (6)
In this inequality, C is a universal constant and F m denotes the collection of non-negative piecewise constant maps based on m:

F m = I∈m a I ½ I such that a I ≥ 0 for all I ∈ m .
Moreover,

υ m = I∈m ρ I >log n/n ρ 2 I max {P (X ∈ I), ρ I } + I∈m ρ I ≤log n/n ρ I + |m| n ,
where ρ I is given by (3).

Up to the multiplicative factor C, the risk of the estimator can thus be bounded from above by the best possible compromise between a bias term h 2 (f, F m ) and an estimation term κυ m . The infimum is taken among all the partitions m of M ℓ , and this includes, in particular, partitions m whose thinness may vary spatially. Such a result is therefore well suited to estimate densities whose regularity is spatially inhomogeneous, see Section 3 for more details. The parameter ℓ, that tunes the minimal length of an interval I of a partition m ∈ M ℓ , can be any value of {1, . . . , n}. From a theoretical point of view, the larger ℓ is, the better. It is however useless to go higher than n. Indeed, a partition m ∈ M ℓ \ M ℓ-1 contains more than ℓ intervals. Consequently, υ m ≥ |m|/n ≥ 1 when ℓ ≥ n, and the infimum

κ -1 0 inf m∈M∞\Mn h 2 (f, F m ) + κυ m is always at least as large as 1 ≥ h 2 (f, f ).
For pedagogical reasons, let us consider the case of direct estimation, i.e. α = ∞. The term v m then reduces to v m = |m|/n. To compare with the literature, it is convenient to classify the existing histogram selection rules into two parts, according to their computational complexities and their theoretical results. We restrict attention to rules that yield results for the Hellinger loss. The first part we consider gathers the procedures based on the maximum likelihood method, see [START_REF] Castellan | Modified akaike's criterion for histogram density estimation[END_REF][START_REF] Barron | Risk bounds for model selection via penalization[END_REF][START_REF] Massart | Concentration inequalities and model selection[END_REF] for key references. These rules can be programmed on computer and executed fairly quickly if ℓ, n are of reasonable size. This point is also true for our procedure. For more information on these computational aspects, we refer to [START_REF] Blanchard | Oracle bounds and exact algorithm for dyadic classification trees[END_REF][START_REF] Akakpo | Inhomogeneous and anisotropic conditional density estimation from dependent data[END_REF][START_REF] Sart | Estimation of the transition density of a Markov chain[END_REF][START_REF] Sart | Minimax bounds for besov classes in density estimation[END_REF]. The theoretical results of these methods are, however, substantially different from ours. For instance, the results in [START_REF] Castellan | Modified akaike's criterion for histogram density estimation[END_REF][START_REF] Massart | Concentration inequalities and model selection[END_REF] require that the density be uniformly bounded from below by a positive constant, and impose a condition on the maximal thinness of the partitions m. The one of [START_REF] Barron | Risk bounds for model selection via penalization[END_REF] is not well adapted to deal with the collection M ℓ because it would lead to extra logarithmic factors in the estimation term. Lastly, the bias terms in these three papers involve the Kullback-Leibler divergence instead of the Hellinger distance as here. We now turn to a second group of procedures, those of [START_REF] Birgé | Model selection via testing: an alternative to (penalized) maximum likelihood estimators[END_REF][START_REF] Baraud | Estimating the intensity of a random measure by histogram type estimators[END_REF][START_REF] Baraud | Estimator selection with respect to hellinger-type risks[END_REF]. Basically, they are based either on a robust test or on the Lepski method. All these procedures suffer from their computational complexity, and we do not know how to use them in practice for reasonable values of ℓ. They give however theoretical results similar to ours. More precisely, they all lead to a non-asymptotic risk bound identical to (6), up to constants.

In indirect estimation, the term υ m is more complex. To analyze it, suppose that α ∈ (0, 1] and m ∈ M ℓ where ℓ is such that 2 ℓ ≤ n c for some c > 0. This implies that log 2 (1/|I|) ≤ c log n for all I ∈ m. A rough upper bound of υ m is then

υ m ≤ c ′ |m| √ α 2 N where N = n (log 3 n) log 2 (log n) , (7)
and where c ′ depends on c only. If we replace υ m by this upper bound in (6), the resulting inequality has the same flavour as in the direct case. Up to logarithmic factors, going from the direct to the indirect case simply amounts to reducing the sample size to √ α 2 n. Note that logarithmic terms are also involved in the results of the literature in non-parametric estimation under L q loss in the private setup as far as adaptivity is concerned, see [START_REF] Butucea | Local differential privacy: Elbow effect in optimal density estimation and adaptation over besov ellipsoids[END_REF][START_REF] Kroll | On density estimation at a fixed point under local differential privacy[END_REF]. Inequality (7) can be improved under a lower bound condition. Suppose that there exists

ε ∈ (0, 1) such that f (x) ≥ ε for all x ∈ [0, 1]. Then, υ m ≤ c ′   1 α 2 N I∈m 1 max ε|I|, 1/ √ α 2 N + |m| log n n   ,
where c ′ only depends on c. Besides, the second term in the bracket is not larger than the first one times a multiplicative constant. We deduce, up to an increase of c ′ ,

υ m ≤ c ′ α 2 N I∈m 1 max ε|I|, 1/ √ α 2 N . ( 8
)
This bound does not only depend on the cardinal of m but also on the thinness of its intervals. It can be simplified when m is a regular partition, that is when |I| = 1/|m| for all I ∈ m. In such a case,

υ m ≤ c ′ |m| 2 εα 2 N . (9)
Up to the terms c ′ , ε, the upper bound in (9) is the square of that of (7) and is therefore much better (at least when it is smaller than 1, but partitions m for which υ m > 1 are of little interest since h 2 (f, f ) ≤ 1).

Minimax rates

The goal of this section is to present new theoretical results on the minimax rates under smoothness constraints. Throughout this section, κ = κ 0 and ℓ is large enough, say ℓ = n for the sake of simplicity. For different classes F of functions, we give an upper bound on the maximal risk

R α ( f ) = R α ( f , h 2 ) = sup f ∈F E h 2 (f, f )
reached by f when f lies in F . We also establish a lower bound on the minimax risk

R α (F ) = R α (F , h 2 ) = inf f ,Q R α ( f )
and compare this result to our upper bound.

3.1. Hölder and Besov classes. The notion of smoothness of a function can be quantified through its belonging to a Hölder class or more finely to a Besov class. We recall their definition below to introduce our notations.

The Hölder class is denoted by B β ∞,∞ (R) in the sequel. It depends on two parameters β ∈ (0, 1) and R > 0 and is defined as the collection of functions f on [0, 1] satisfying for all h > 0,

x ∈ [0, 1 -h], |f (x + h) -f (x)| ≤ Rh β .
The Besov class B β p,∞ (R) depends on one more parameter p > 0. It specifies in which (quasi) norm the regularity β is measured. More precisely, we define the Besov class B β p,∞ (R) as the set of functions f on [0, 1] that are p th power integrable and that satisfy for all h > 0,

[0,1-h] |f (x + h) -f (x)| p dx 1/p ≤ Rh β .
We recall here some elementary properties on Besov classes that will be useful in the sequel and refer to [START_REF] Ronald | Constructive approximation[END_REF] for more details.

The smaller p is, the weaker the condition f ∈ B β p,∞ (R) is. Likewise, the smaller β is, the larger the class B β p,∞ (R) is. In general, the functions of B β p,∞ (R) may not be bounded. However, the L q norm of a density f ∈ B β p,∞ (R) satisfies f q ≤ c(1+ R) whenever β > 1/p -1/q, where c only depends on β, p, q. This inequality is valid whatever q ∈ [p, +∞].

Minimax rates over Besov classes.

In non-parametric estimation under L q norm, we usually aim at determining the optimal rates of convergence under smoothness assumptions on the function to be estimated. This amounts here to studying the minimax risk on F = B β p,∞ (R). When the loss is a Hellinger distance, however, the smoothness assumption is traditionally rather put on the square root of the target. In other terms, this means that f belongs to

SB β p,∞ (R) = f, f ∈ B β p,∞ (R) .
The following elementary proposition says that it is basically more stringent to impose regularity on √ f than on f when β > 1/p. This is no longer true when β < 1/p. It is proved in Section 4.3.

Proposition 3. Let p ∈ (0, ∞], β ∈ ((1/p -1/2) + , 1) and R > 0.
• For all β > 1/p, there exists R ′ > 0 such that every density of

SB β p,∞ (R) lie in B β p,∞ (R ′ ). • For all β < 1/p there is a density f ∈ SB β p,∞ (R) that does not lie in R ′ >0 B β p,∞ (R ′ ).
The minimax rates on B β p,∞ (R) and SB β p,∞ (R) turn out to be different. More precisely, we show in Sections 4.4 and 4.6: Proposition 4. For all p > 0, R ≥ 16, α ∈ (0, 1], β ∈ ((1/p -1) + , 1) and n large enough,

c 1 1 α 2 n β 2β+2 ≤ R α (B β ∞,∞ (R)) ≤ R α (B β p,∞ (R), f ) ≤ c 2 1 α 2 N β 2β+2 . (10) Moreover, if β ∈ ((1/p -1/2) + , 1), c 3 1 α 2 n β 2β+1 ≤ R α (SB β ∞,∞ (R)) ≤ R α (SB β p,∞ (R), f ) ≤ c 4 1 α 2 N β 2β+1 . ( 11
)
In the above inequalities, c 1 , c 3 only depend on R, β, and c 2 , c 4 only depend on R, p, β. Moreover, N is defined in (7).

We observe that the lower and upper bounds match, up to logarithmic factors. We deduce that our estimator is (nearly) optimal on the Besov classes B β p,∞ (R) and SB β p,∞ (R). It is also adaptive because its construction does not involve the parameters β, p and R. We mention here that values of β smaller than 1/p are allowed. This, in particular, allows the density f to be not bounded.

Minimax rates under a lower bound condition.

A minimax rate is always a bit pessimistic since it corresponds to the worst case scenario. The situation actually improves when the density is uniformly bounded from below. More precisely, consider ε ≥ 0 and define

B β p,∞ (R, ε) = f ∈ B β p,∞ (R), inf x∈[0,1] f (x) ≥ ε , SB β p,∞ (R, ε) = f, f ∈ B β p,∞ (R), inf x∈[0,1] f (x) ≥ ε .
For all β ∈ (0, 1), p, ε, R > 0, elementary computations give

B β p,∞ (R, ε) ⊂ SB β p,∞ (R ′ , ε), (12)
where R ′ = R/(2 √ ε). The smoothness exponent of √ f is then the same to that of f when β > 1/p, see Proposition 3. This may not be true when β < 1/p. In this case, it is weaker to put a smoothness assumption on √ f than on f . We set for p > 0 and β ∈ (0, 1),

ψ = β/(β + 1) if β > 2/p -1, βp/2 if β ≤ 2/p -1.
We show in Section 4.5:

Proposition 5. Let R, p > 0, α, ε ∈ (0, 1], β ∈ ((1/p -1) + , 1). Then, for n large enough, R α (B β p,∞ (R, ε), f ) ≤ c 1 log γ n α 2 n ψ . (13) Moreover, if β ∈ ((1/p -1/2) + , 1), R α (SB β p,∞ (R, ε), f ) ≤ c 2 log γ n α 2 n ψ . ( 14
)
In the above inequalities, c 1 , c 2 depend on R, p, β, ε only, and γ depends on p, β only. Moreover, if β = 2/p-1 and if β ∈ [2/p-2, 1/p-1/2], γ may be chosen in such a way that

(log γ n)/(α 2 n) = 1/(α 2 N ) where N is defined in (7).
The rate of convergence of our estimator f is therefore faster when the density is uniformly bounded from below. The rates given by ( 13) and ( 14) coincide although SB β p,∞ (R, ε) may be wider than B β p,∞ (R, ε). Note that f does not depend on ε nor on p, R, β and is therefore adaptive. We will see in the next section that it is also rate optimal (to within possible logarithmic factors).

3.4. About the L 2 loss. In this section, we are interested in the minimax rates under the L 2 loss. Although this loss is different from ours, it is possible to compare these rates with our own, at least partially. We recall that the minimax risk over a class F under L 2 loss is denoted by

R α (F , d 2 2 ) = inf f ,Q sup f ∈F E d 2 2 (f, f ) .
In the literature, the minimax rates over some Besov classes are known, up to possible logarithmic factors. Consider indeed ε ∈ [0, 1), α ∈ (0, 1], R > 0. We may then find the following lower and upper bounds: for n large enough, if p ≥ 2 or if p ≥ 1 and β > 1/p,

c 1 1 α 2 n β/(β+1) ≤ R α (B β p,∞ (R, ε), d 2 2 ) ≤ c 2 log θ n α 2 n β/(β+1)
, where c 1 , c 2 only depend on R, p, β and where θ only depends on p, β (θ = 0 if p ≥ 2). This result when ε = 0, that is when

B β p,∞ (R, ε) = B β p,∞ (R)
, is due to [START_REF] Butucea | Local differential privacy: Elbow effect in optimal density estimation and adaptation over besov ellipsoids[END_REF] but their proof also works with higher values of ε. Under their conditions, β/(β + 1) = ψ. We deduce that this rate can be either faster or equal to ours (depending on whether ε = 0 or not, and up to log factors). Note that the densities of B β p,∞ (R, ε) are both bounded from below and above when ε > 0 and β > 1/p (see the end of Section 3.1). Consequently, the Hellinger and L 2 distances are equivalent on B β p,∞ (R, ε) and the minimax rates correspond. In particular, the rate we obtained in Proposition 5 is (nearly) optimal when β > 1/p.

As far as we know, the minimax rates under L 2 loss are not yet known when p < 2 and β ≤ 1/p. Even in the direct case, it is only very recently that results have been established. Actually, the estimation rate of a bounded or unbounded density when β ≤ 1/p may not be the same, see [START_REF] Birgé | Model selection for density estimation with L 2 -loss[END_REF][START_REF] Sart | Minimax bounds for besov classes in density estimation[END_REF] for more details. It turns out that a similar phenomenon occurs in the private setup.

We start by studying the problem of estimating a bounded density f . We introduce therefore the set

F β p,∞ (R, ε) = f ∈ B β p,∞ (R, ε), f ∞ ≤ 2 (15)
composed of functions of B β p,∞ (R, ε) that are uniformly bounded from above by 2. We show in Section 4.6.1:

Proposition 6. Let R, p > 0, α ∈ (0, 1], ε, β ∈ (0, 1), such that β ∈ (1/p -1, 1/p]. Then for n large enough, R α (B β p,∞ (R, ε)) ≥ R α (F β p,∞ (R, ε)) ≥ c 1 α 2 n ψ , ( 16
)
where c depends on R and β only.

We therefore deduce from (12), ( 13) and ( 14) that our estimator f is (nearly) minimax on the three collections

F β p,∞ (R, ε), B β p,∞ (R, ε), SB β p,∞ (R, ε) when β ≤ 1/p. Note that h and d 2 are equivalent on F β p,∞ (R, ε) when ε > 0.
We deduce that n -ψ is also minimax on this class for the L 2 loss (up to log factors).

The results for the two distances do not always coincide. For instance, the lower bound condition f ≥ ε plays an important role in the minimax rates under the Hellinger loss, see Sections 3.2 and 3.3. This is no longer true for the L 2 loss and the condition can be dropped without changing the rates. More precisely, we explain in Section 4.7 how to adapt our estimation procedure to get the upper bound below.

Proposition 7. Let R, p > 0, α ∈ (0, 1], β ∈ (0, 1) such that β ∈ (1/p -1, 1/p]. Then for n large enough, c 1 1 α 2 n ψ ≤ R α (F β p,∞ (R, 0), d 2 2 ) ≤ c 2 log γ n α 2 n ψ ,
where c 1 depends on p, β only and where c 2 depends on R, p, β only. Moreover, the term γ is the same as in Proposition 5.

We now examine the problem of estimating an unbounded density f . The importance of the condition f ∞ < ∞ can be assessed by comparing the minimax rates on F β p,∞ (R, ε) to those of B β p,∞ (R, ε). Note that these rates coincide for the Hellinger loss (up to log factors). This may not be true for the L 2 loss. We show indeed in Section 4.6.2:

Proposition 8. Let R, p > 0, α ∈ (0, 1], ε ∈ [0, 1), β ∈ (0, 1) such that β ∈ (1/p -1/2, 1/p]. Then for n large enough, R α (B β p,∞ (R, ε), d 2 2 ) ≥ c 1 α 2 n ψ ′ , ( 17
)
where

ψ ′ = β/(β + 1) if β ∈ (2/p -1, 1/p], (β -1/p + 1/2)/(β -1/p + 1) if β ∈ (1/p -1/2, 2/p -1],
and where c depends on R, p and β only.

We suspect that this rate is optimal up to possible logarithmic factors. Note that it may be made arbitrarily slow by letting β go to 1/p -1/2. In particular, it may be much slower than the optimal rate for the Hellinger loss on the same class (see Propositions 4 and 5). This phenomenon is probably due to the fact that the L 2 distance gives more weight to singularities than the Hellinger distance (which can be used even when f ∈ L 2 ).

Proofs

4.1. Proof of Proposition 1. Conditionally to X = x, Y has a density q(• | X = x) with respect to the multidimensional Lebesgue measure. For all y = (y(I j )) I j ∈ mj ,j∈{0,...,n} ,

q(y | X = x) = n j=0 I j ∈ mj α 4(1 + 1/δ)(1 + j) 1+δ exp - α 2(1 + 1/δ)(1 + j) 1+δ y(I j ) -½ I j (x) =   n j=0 I j ∈ mj α 4(1 + 1/δ)(1 + j) 1+δ   exp   - α 2(1 + 1/δ) n j=0 1 (1 + j) 1+δ I j ∈ mj y(I j ) -½ I j (x)   .
We deduce from the triangle inequality that for all x, x ′ ∈ [0, 1],

q(y | X = x) q(y | X = x ′ ) ≤ exp   α 2(1 + 1/δ) n j=0 1 (1 + j) 1+δ I j ∈ mj |½ I j (x ′ ) -½ I j (x)|   ≤ exp   α 2(1 + 1/δ) ∞ j=0 2 (1 + j) 1+δ   ≤ exp(α).

Proof of Theorem 2. Let us remark that each variable Y i (I) takes the form

Y i (I) = ½ I (X i ) + c I W i (I),
where

c I = 2(1 + 1/δ)(1 + log 2 (1/|I|)) 1+δ α , (18)
and where W 1 (I), . . . , W n (I) are n independent Laplacian random variables, that are independent of X 1 , . . . , X n .

We define for ℓ ∈ N ⋆ ∪ {∞}, the collection I ℓ = {I ∈ m, m ∈ M ℓ } of dyadic intervals. We begin by giving three probability results.

Lemma 1. There exists for all ξ > 0, and J ∈ I ∞ , an event of probability 1 -e -ξ on which:

for all m ′ ∈ M ∞ I∈m ′ ∨J   1 n n i=1 ½ I (X i ) -P (X ∈ I)   2 ≤ 412 |m ′ ∨ J| n + 202 ξ n . ( 19
)
Proof of Lemma 1. This lemma follows from Theorem 8 of [START_REF] Baraud | Estimating the intensity of a random measure by histogram type estimators[END_REF] and from a union bound (see their Section 3.2.

2).

Lemma 2. There exists for all ξ ≥ 1, an event of probability 1-e -ξ on which: for all interval I,

1 n n i=1 ½ I (X i ) -P (X ∈ I) ≤ 4 log n + ξ n .
Moreover,

1 n n i=1 ½ I (X i ) -P (X ∈ I) ≤ 4 log n + ξ n P (X ∈ I) + 16 log n + ξ n . ( 20
)
Proof of Lemma 2. We use Theorem 7 of [START_REF] Bousquet | Introduction to statistical learning theory[END_REF] with δ = e -ξ /2, the collection F of all indicator functions of the form f = ½ I where I is an interval. For such a collection, their term S F (2n) satisfies

S F (2n) ≤ 2n 0 + 2n 1 + 2n 2 ≤ 1 + n + 2n 2 .
We therefore deduce an event of probability 1 -e -ξ on which: for all interval I,

1 n n i=1 ½ I (X i ) -P (X ∈ I) ≤ 2 log(1 + n + 2n 2 ) + log 8 + ξ n .
We then simplify the right-hand side of this inequality. The proof of (20) comes from elementary computations, see Claim 8 of [START_REF] Sart | Estimating a density, a hazard rate, and a transition intensity via the ρestimation method[END_REF] for instance.

Lemma 3. There exists for all ξ ∈ [1, n], an event of probability 1 -e -ξ on which: for all

I ∈ I n , 1 n n i=1 W i (I) ≤ 7 ξ + log 2 (1/|I|) n . ( 21
)
Proof of Lemma 3. The random variables (W i (I)) i are independent and satisfy E[|W i (I)| q ] = q! for all q ≥ 1. We consider t > 0 and apply Bernstein's Inequality (Theorem 2.10 of [START_REF] Boucheron | Concentration inequalities: A nonasymptotic theory of independence[END_REF]) to the empirical sums n -1 n i=1 W i (I) and -n -1 n i=1 W i (I). This yields an event A t (I) such that P (A t (I)) ≥ 1 -2e -t and on which

1 n n i=1 W i (I) ≤ 2 t/n + t/n.
The number of intervals I ∈ I n such that |I| = 2 -ℓ is not larger than 2 ℓ . We then deduce from a union bound that the event

I∈In |I|=2 -ℓ ℓ≤n A ξ+2.1+ℓ (I)
holds true with probability 1 -e -ξ . On this event: for all I ∈ I n ,

1 n n i=1 W i (I) ≤ 2 ξ + 2.1 + log 2 (1/|I|) n + ξ + 2.1 + log 2 (1/|I|) n .
Elementary computations using ξ ∈ [1, n] then give (21).

We also need the following elementary result:

Lemma 4. For all a, c ≥ 0, and b ∈ R,

(a + b) + - √ c 2 ≤ 2 ( √ a - √ c) 2 + |b| . (22)
Moreover, for all d ≥ (11 + 5 √ 5)/4,

(a + b) + - √ c 2 ≤ 2 ( √ a - √ c) 2 + d b 2 c . ( 23
)
Proof of Lemma 4. Proving (22) amounts to showing that

γ(t) = 2 ( √ a - √ c) 2 + |t|a - ((1 + t)a) + - √ c 2 is non-negative for all t ∈ R.
When t < -1, we have

γ(t) = 2 a + c -2 √ ac + |t|a -c ≥ 2 a + c -2 √ ac + a -c ≥ 4 a - √ ac + c. (24)
We use the elementary inequality 2 √ ac ≤ 2a + c/2 to get γ(t) ≥ 0.

When t ∈ [-1, 0],

γ(t) = c + 2 √ ac √ 1 + t -2 + (1 -3t)a.
By computing the derivative of γ, we observe that γ is non-decreasing on [-1, min{0, t 0 }] and non-increasing on [min{0, t 0 }, 0] where t 0 = c/(9a) -1. Therefore, γ(t) ≥ min{γ(-1), γ(0)}. Note that γ(-1) coincides with the right-hand side of (24) and is hence non-negative. Moreover,

γ(0) = ( √ c - √ a) 2 ≥ 0. When t ≥ 0, γ(t) = a + c -4 √ ac + ta + 2 √ ac √ 1 + t is non-decreasing and satisfies therefore γ(t) ≥ γ(0) ≥ 0.
We now turn to the proof of (23). We assume without loss of generality that d = (11+ 5 √ 5)/4 and prove that

γ(t, u) = 2 (1 - √ u) 2 + dt 2 /u - (1 + t) + - √ u 2 is non-negative for all t ∈ R and u > 0. When (t, u) ∈ (-∞, -1] × (0, +∞), γ(t, u) = 2 + u -4 √ u + 2dt 2 /u ≥ 2 -4 √ u + u + 2d/u.
We may easily check that the right-hand side of this inequality is non-negative.

When (t, u) ∈ (0, ∞) × (0, +∞),

(1 + t) + - √ u 2 = (1 + t -u) 2 ( √ 1 + t + √ u) 2 .
We use the elementary inequality (x + y) 2 ≤ 2x 2 + 2y 2 to get

(1 + t) + - √ u 2 ≤ 2 (1 -u) 2 ( √ 1 + t + √ u) 2 + 2 t 2 ( √ 1 + t + √ u) 2 ≤ 2 (1 -u) 2 (1 + √ u) 2 + 2 t 2 u ≤ 2(1 - √ u) 2 + 2 t 2 u .
We finally assume that (t, u) ∈ (-1, 0] × (0, +∞). We set x ∈ (0, 1], y ∈ (0, +∞) such that t = x 2 -1, y 2 = u and define γ 2 (x, y) = uγ(t, u) = y 4 + 2y 3 x -4y 3 -x 2 y 2 + 2y 2 + 2dx 4 -4dx 2 + 2d.

Our aim is to show that γ 2 (x, y) ≥ 0 for all x ∈ (0, 1], y > 0.

For each x ∈ (0, 1], the map y → ∂γ 2 ∂y (x, y) is a polynomial function of degree 3 that admits three real valued roots. The first one is zero, and the other two are non-negative. Let us denote by ϕ 1 (x) ≤ ϕ 2 (x) these two solutions. Since the leading coefficient of the polynomial is positive, we deduce that y → γ 2 (x, y) is increasing on [0, ϕ 1 (x)], decreasing on [ϕ 1 (x), ϕ 2 (x)] and increasing on [ϕ 2 (x), ∞). In particular,

γ 2 (x, y) ≥ min{γ 2 (x, 0), γ 2 (x, ϕ 2 (x))}. Note that γ 2 (x, 0) = 2d(x 2 -1) 2 ≥ 0.
We now aim at showing that ψ(x) = γ 2 (x, ϕ 2 (x)) ≥ 0. In the sequel, we denote the derivative of a map f by ḟ , the second derivative by f and its third derivative by ... f . By using the explicit formula of ϕ 2 , we may remark that ϕ 2 (x) ≥ 1, φ2 (x) < 0 and φ2 (x) > 0. Yet, ...

ψ (x) = φ2 (x) ∂ 2 γ 2 ∂x∂y (x, ϕ 2 (x)) + ( φ2 (x)) 2 ∂ 3 γ 2 ∂x∂ 2 y (x, ϕ 2 (x)) + 2 φ2 (x) ∂ 3 γ 2 ∂ 2 x∂y (x, ϕ 2 (x)) + ∂ 3 γ 2 ∂ 3 x (x, ϕ 2 (x)).
Note that:

∂ 2 γ 2 ∂x∂y (x, ϕ 2 (x)) = 2ϕ 2 (x)(3ϕ 2 (x) -2x) ≥ 2(3 -2) > 0 ∂ 3 γ 2 ∂x∂ 2 y (x, ϕ 2 (x)) = 4(3ϕ 2 (x) -x) ≥ 4(3 -1) > 0 ∂ 3 γ 2 ∂ 2 x∂y (x, ϕ 2 (x)) = -4ϕ 2 (x) < 0 ∂ 3 γ 2 ∂ 3 x (x, ϕ 2 (x)) = 12(11 + 5 √ 5)x > 0.
This implies ... ψ (x) > 0. Therefore, ψ is either monotone, or decreasing then increasing. Since ψ(0) > 35.8 > 0, ψ(0.7) < -12.9 < 0, ψ(1) = 0, we are in case two. This also implies that there is x 0 ∈ (0, 1) such that ψ > 0 on [0, x 0 ) and ψ < 0 on (x 0 , 1). In particular, ψ is increasing then decreasing and hence ψ(x) ≥ min{ψ(0), ψ(1)} = 0.

We introduce for ξ > 0 and

I ∈ I n , ρ I,ξ = c I ξ + log 2 (1/|I|) n ,
where c I is given by (18). We also define for m ∈ M n , J ∈ I n ,

pen id,ξ (m ∨ J) = I∈m∨J ρ 2 I,ξ max{P (X ∈ I), ρ I,ξ } + |m ∨ J| n .
Let us observe that for all ξ ≤ 2 log n, ρ I,ξ ≤ √ 2ρ I , and pen id,ξ (m ∨ J) ≤ pen id,2 log n (m ∨ J) ≤ 2υ m∨J . (25)

Moreover:

Lemma 5. There exists an event of probability 1 -2/n 2 on which: for all m ∈ M n and J ∈ I n ,

v m∨J ≤ 84 pen(m ∨ J), (26) pen(m ∨ J) ≤ 166v m∨J . (27) Proof of Lemma 5. Let ξ ∈ [1, n].
We deduce from the triangle inequality, from Lemmas 2, 3 and from ρ I,ξ ≤ √ 2ρ I that with probability 1 -2e -ξ : for all I ∈ I n ,

|P n (I) -P (X ∈ I)| ≤ 4 log n + ξ n P (X ∈ I) + 16 log n + ξ n + 7 √ 2ρ I .
We use this result with ξ = 2 log n. The elementary inequality √ xy ≤ (1/8)x + 2y implies when

ρ I > log n/n that |P n (I) -P (X ∈ I)| ≤ 1 2 P (X ∈ I) + 82ρ I . ( 28
)
In particular, max{P n (I), ρ I } ≤ 83.5 max{P (X ∈ I), ρ I } ≤ 84 max{P (X ∈ I), ρ I } and hence (26).

As to (27), we get from (28),

P (X ∈ I) ≤ 2|P n (I)| + 164ρ I .
This gives max{P (X ∈ I), ρ I } ≤ 166 max{P n (I), ρ I } if P n (I) ≥ 0, which proves (27). If P n (I) < 0, we deduce from (28) that P (X ∈ I) ≤ 1/2P (X ∈ I) + 82ρ I and hence P (X ∈ I) ≤ 164ρ I ≤ 164 max{P n (I), ρ I }, which ends the proof.

We are in position to prove: Proposition 9. Let J ∈ I n . There exists for all ξ ∈ [1, n], an event of probability 1 -2e -ξ on which: for all m ′ ∈ M n ,

h 2 (f ½ J , fm ′ ∨J ½ J ) ≤ 4h 2 (f ½ J , F m ′ ∨J ) + 824pen id,ξ (m ′ ∨ J) + 404ξ/n. ( 29
)
Proof. We define for all

J ∈ I n , m ′ ∈ M n , fm ′ ∨J = I∈m ′ ∨J P (X ∈ I) |I| ½ I .
We use the triangle inequality, (a + b) 2 ≤ 2a 2 + 2b 2 , and Lemma 2 of [START_REF] Baraud | Estimating the intensity of a random measure by histogram type estimators[END_REF] to get

h 2 (f ½ J , fm ′ ∨J ½ J ) ≤ 2h 2 (f ½ J , fm ′ ∨J ) + 2h 2 ( fm ′ ∨J , fm ′ ∨J ) ≤ 4h 2 (f ½ J , F m ′ ∨J ) + 2h 2 ( fm ′ ∨J , fm ′ ∨J ).
We deduce from Lemma 4,

2h 2 ( fm ′ ∨J , fm ′ ∨J ) = I∈m ′ ∨J   1 n n i=1 ½ I (X i ) + c I n n i=1 W i (I) + -P (X ∈ I)   2 ≤ 2 I∈m ′ ∨J   1 n n i=1 ½ I (X i ) -P (X ∈ I)   2 + 2 I∈m ′ ∨J min    c I n n i=1 W i (I) , 11 + 5 √ 5 4P (X ∈ I) c I n n i=1 W i (I) 2    .
We then apply Lemmas 1 and 3.

Lemma 6. Let ℓ ∈ {1, . . . , n} and ξ ∈ [1, 2 log n]. Then, there exists a universal constant κ 0 such that if κ ≥ κ 0 , any estimator f m satisfying (4) satisfies with probability 1 -4e -ξ ,

h 2 (f, f m) ≤ C 1 inf m∈M ℓ h 2 (f, F m ) + γ(m) + κυ m + ξ/n . (30) Moreover, C 1 is a universal constant.
Proof of Lemma 6. We deduce from (29), ( 25), (26) an event of probability 1 -2e -ξ -2/n 2 ≥ 1 -4e -ξ on which: for all ℓ ∈ {1, . . . , n}, and m ′ ∈ M ℓ ,

h 2 (f, fm ′ ) ≤ 4h 2 (f, F m ′ ) + 824 × 2 × 84 × pen(m ′ ) + 404ξ/n.
Therefore, if κ 0 is large enough, say κ 0 = 824 × 2 × 84 × 2, and κ ≥ κ 0 ,

h 2 (f, fm ′ ) ≤ 4h 2 (f, F m ′ ) + (κ/2) pen(m ′ ) + 404ξ/n. (31) For all m ∈ M ℓ , h 2 f, f m ≤ 2h 2 f, f m∨m + 2 h 2 f m, f m∨m -κ pen( m ∨ m) + 2κ pen( m ∨ m) ≤ 2h 2 f, f m∨m + 2 J∈ m h 2 f m½ J , f m∨m ½ J -κ pen(m ∨ J) + 2κ pen( m ∨ m) ≤ 2h 2 f, f m∨m + 2γ( m) + 2κ pen( m ∨ m).
Note that m ∨ m ∈ M ℓ . We derive from (31),

h 2 f, f m ≤ 8h 2 f, F m∨m + 2γ( m) + 3κ pen( m ∨ m) + 808ξ/n. Since m ∨ m ⊂ m ∪ m, pen( m ∨ m) ≤ pen( m) + pen(m) and (4) entails, h 2 f, f m ≤ 8h 2 (f, F m ) + 2 [γ( m) + (3/2)κ pen( m)] + 3κ pen(m) + 808ξ/n ≤ 8h 2 (f, F m ) + 2γ(m) + 6κ pen(m) + 808ξ/n.
We finally use (27) to get (30).

Lemma 7. Let Z, R be two random variables and a > 0. We suppose that there exists for all ξ ∈ [1, a log n] an event of probability 1 -c 1 e -ξ on which Z ≤ R + c 2 ξ/n. Then,

E[Z½ A ] ≤ E[R½ A ] + (1 + c 1 )c 2 /n,
where A is an event of probability 1 -c 1 /n a .

Proof of Lemma 7. Let A ξ be the above event of probability 1 -c 1 e -ξ and A = A a log n . Then,

E[(Z -R) + ½ A ] = ∞ 0 P [(Z -R) + ½ A ≥ u] du ≤ (c 2 /n) 1 + a log n 1 P [(Z -R) + ½ A ≥ c 2 ξ/n] dξ ≤ (c 2 /n) 1 + c 1 a log n 1 e -ξ dξ ≤ (c 2 /n)(1 + c 1 ).
It then remains to use

E[Z½ A ] ≤ E[R½ A ] + E[(Z -R) + ½ A ]
to conclude.

Lemma 8. Let ℓ ∈ {1, . . . , n} and m ∈ M ℓ such that |m| ≤ n. Then, there is an event A of probability 1 -6/n such that if κ ≥ κ 0 ,

E [(γ(m)) + ½ A ] ≤ C 2 h 2 (f, F m ) + υ m .
Moreover, C 2 is a universal constant.

Proof of Lemma 8. We deduce from the triangle inequality that

γ(m) ≤ J∈m sup m ′ ∈M ℓ 2h 2 (f ½ J , fm ½ J ) + 2h 2 (f ½ J , fm ′ ∨J ) -κ pen(m ′ ∨ J) ≤ 2h 2 (f, fm ) + J∈m sup m ′ ∈M ℓ 2h 2 (f ½ J , fm ′ ∨J ) -κ pen(m ′ ∨ J) .
We deduce,

(γ(m)) + ≤ 2h 2 (f, fm ) + J∈m sup m ′ ∈M ℓ 2h 2 (f ½ J , fm ′ ∨J ) -κ pen(m ′ ∨ J) + . (32) Let ξ ∈ [1, 2 log n].
We derive from ( 29), ( 25), ( 26) that there is an event

A ξ (J) of probability 1 -2e -ξ -2/n 2 ≥ 1 -4e -ξ on which: for all m ′ ∈ M ℓ , h 2 (f ½ J , fm ′ ∨J ½ J ) ≤ 4h 2 (f ½ J , F m ′ ∨J ) + (κ 0 /2) pen(m ′ ∨ J) + 404ξ/n, ( 33
)
where κ 0 = 824 × 2 × 84 × 2 as in the proof of Lemma 6. Therefore, if κ ≥ κ 0 , sup

m ′ ∈M ℓ 2h 2 (f ½ J , fm ′ ∨J ½ J ) -κ pen(m ′ ∨ J) + ½ A ξ (J) ≤ 8 sup m ′ ∈M ℓ h 2 (f ½ J , F m ′ ∨J ) + 808ξ/n.
We apply Lemma 7 to get an event A(J) of probability 1 -4/n 2 such that

J∈m E sup m ′ ∈M ℓ 2h 2 (f ½ J , fm ′ ∨J ) -κ pen(m ′ ∨ J) + ½ A(J) ≤ 8h 2 (f, F m ) + 4040|m|/n. (34)
Moreover, we deduce from (29) with J = [0, 1], and from (25), that for all ξ ∈ [1, 2 log n], and probability 1 -2e -ξ ,

h 2 (f, fm ) ≤ 4h 2 (f, F m ) + 824 × 2 × υ m + 404ξ/n.
We derive from Lemma 7 an event B of probability 1 -2/n 2 on which

E[h 2 (f, fm )½ B ] ≤ 4h 2 (f, F m ) + 824 × 2 × υ m + 1212/n. ( 35
)
We may now define the event A appearing in the lemma by

A = B J∈m A(J).
The probability of this event is not smaller than 1 -4|m|/n 2 -2/n 2 ≥ 1 -4/n -2/n 2 ≥ 1 -6/n. It then remains to put (32), (34), (35) together and to notice that |m|/n ≤ υ m /n. Lemma 9. Let f m be an estimator satisfying (4) and f be defined by (5). Then, h 2 (f, f ) ≤ 1 and

h 2 (f, f ) ≤ h 2 (f, f m). (36)
Proof. We first remark that

h 2 (f, f ) ≤ 1 2 f + f ≤ 1.
As to the proof of (36), we only need to consider the case f m > 1. We then have f = f m/ f m and hence

h 2 (f, f ) -h 2 (f, f m) = 1 2 - f f m f m - 1 2 f m + f f m = f m -1   f f m f m - 1 2 - 1 2 f m  .
By using the Cauchy-Schwarz inequality,

h 2 (f, f ) -h 2 (f, f m) ≤ f m -1 1 - 1 2 - 1 2 f m ≤ - 1 2 f m -1 2 ≤ 0.
Proof of Theorem 2. The infimum in the right-hand side of ( 6) is achieved for a partition m ∈ M ℓ . The result is straightforward if the cardinal |m| of this partition is larger than n, since then h 2 (f, f ) ≤ 1 ≤ υ m ≤ κυ m (κ 0 is larger than 1). We suppose from now on that |m| ≤ n.

Let A be the event associated to the partition m given by Lemma 8. It follows from Lemmas 6 and 7 (with Z = h 2 (f, f m)½ A ) that there exists an event A ′ of probability 1 -4/n 2 such that

E h 2 (f, f m)½ A ½ A ′ ≤ C 1 E h 2 (f, F m ) + γ(m) + κυ m + ½ A ½ A ′ + 5C 1 /n.
The probability of A ′′ = A ∩ A ′ is at least 1 -10/n. We deduce from Lemma 9, and then from Lemma 8,

E h 2 (f, f ) ≤ E h 2 (f, f )½ A ′′ + 10/n ≤ C 1 E h 2 (f, F m ) + γ(m) + κυ m + ½ A ′′ + (5C 1 + 10)/n, ≤ C 1 h 2 (f, F m ) + E [(γ(m)) + ½ A ] + κυ m + (5C 1 + 10)/n, ≤ C 1 h 2 (f, F m ) + C 2 h 2 (f, F m ) + υ m + κυ m + (5C 1 + 10)/n.
We conclude the proof by noticing that 1/n ≤ |m|/n ≤ υ m ≤ κυ m . 4.3. Proof of Proposition 3. Suppose that β > 1/p and consider a density f ∈ SB β p,∞ (R). Then, f is bounded from above by

f ∞ ≤ c(1 + R 2 ),
where c depends on β, p only, see Lemma 5 of [START_REF] Sart | Minimax bounds for besov classes in density estimation[END_REF] for instance. Moreover, for all x, x + h ∈ [0, 1],

|f (x + h) -f (x)| ≤ 2 f ∞ f (x + h) -f (x) . This implies that f ∈ B β p,∞ (R ′ ) with R ′ = 2R c(1 + R 2 ). Suppose now that β ∈ (1/p -1/2, 1/p). We set I k = [2 -k , 2 -k+1 ] and introduce for x ∈ [0, 1], g(x) = ∞ k=2 2 2(1/p-β)k ½ I k (x).
We have,

[0,1-h] g(x + h) -g(x) p dx 1/p ≤ ∞ k=2 2 (1/p-β)k [0,1-h] |½ I k (x + h) -½ I k (x)| p dx 1/p ≤ ∞ k=2 2 (1/p-β)k min{h, 2|I k |} 1/p ≤ c ′ h β
where c ′ only depends on p, β.

We define τ = g(x) dx < ∞ and suppose without loss of generality that c ′ is larger than R. The map f defined for x ∈ [0, 1] by

f (x) = 2 1 - (R/c ′ ) 2 τ max{τ, 1} ½ [1/2,1] (x) + (R/c ′ ) 2 max{τ, 1} g(x)
is a density belonging to SB β p,∞ (R). We now consider ℓ ≥ 3 and

h = 2 -ℓ . If x ∈ I ℓ , then x + h ∈ I ℓ-1 ⊂ [0, 1/2]. Moreover, [0,1-h] |f (x + h) -f (x)| p dx ≥ (R/c ′ ) 2p max{τ, 1} p [0,1-h]∩I ℓ |g(x + h) -g(x)| p dx. Note that g(x + h) -g(x) = 2 2(1/p-β)ℓ 2 -2(1/p-β) -1 .
We deduce that there exists c ′′ (depending only on p, β, R) such that

[0,1-h] |f (x + h) -f (x)| p dx ≥ c ′′ 2 (1-2pβ)ℓ . If f ∈ B β p,∞ (R ′ ) for some R ′ > 0, we get c ′′ 2 (1-2pβ)ℓ ≤ R ′ 2 -pβℓ
. Such a condition cannot be fulfilled if ℓ is large enough.

Proof of Proposition 4 (upper bounds).

The proof of the lower bounds is done in Section 4.6.1. We focus here on the proof of the upper bounds.

The two following points are results from the approximation theory that can be found in the literature. We refer, for instance, to Corollary 3.3 of [START_REF] Ronald | Degree of adaptive approximation[END_REF], Lemma 12 of [BBM99], Theorem 2 of [START_REF] Akakpo | Adaptation to anisotropy and inhomogeneity via dyadic piecewise polynomial selection[END_REF] or Proposition 5 of [START_REF] Sart | Minimax bounds for besov classes in density estimation[END_REF].

• Let k ≥ 1, p, R > 0, β ∈ ((1/p -1) + , 1) and f ∈ B β p,∞ (R). Then, there is a partition m ∈ M ∞ such that d 1 (f, F m ) ≤ CR2 -kβ
, where C depends on β, p only and where

|m| ≤ 2 k . • Let k ≥ 1, p, R > 0, β ∈ ((1/p -1/2) + , 1) and f ∈ SB β p,∞ (R). Then, there is a partition m ∈ M ∞ such that h 2 (f, F m ) ≤ CR 2 2 -2kβ
where C depends on β, p only and where |m| ≤ 2 k .

In both cases, m ∈ M ℓ with ℓ ≤ ck for some c depending on β, p only. Moreover, it follows from the text below Theorem 2 that the estimator f satisfies

E h 2 (f, f ) ≤ C ′ inf m∈M∞ h 2 (f, F m ) + υ m ,
where C ′ stands for a universal constant.

Let now m be one of the two partitions above, and k be some number such that 2 k ≤ n. We then deduce from (7) that

E h 2 (f, f ) ≤ C ′′ h 2 (f, F m ) + |m| √ α 2 N , (37)
where C ′′ depends on β, p only.

Suppose now that f ∈ B β p,∞ (R) for some p, R > 0, β ∈ ((1/p -1) + , 1). Let k be the largest integer such that 2 k(1+β) ≤ √ α 2 N . Note that 2 k ≤ n for n large enough. We use the partition given in the first point above, the elementary inequality h 2 (f, F m ) ≤ (1/2)d 1 (f, F m ) and (37) to get the right-hand side of (10).

Suppose that f ∈ SB β p,∞ (R) for some p, R > 0, β ∈ ((1/p -1/2) + , 1). Let k be the largest integer such that 2 k(1+2β) ≤ √ α 2 N . We have 2 k ≤ n for n large enough. We use the partition given in the second point above, and (37) to get the right-hand side of (11). 4.5. Proof of Proposition 5. As explained in the text below Theorem 2 the estimator f satisfies

E h 2 (f, f ) ≤ C inf m∈M∞ h 2 (f, F m ) + υ m , ( 38
)
where C is universal. It then remains to find an upper bound of this infimum. 4.5.1. Proof of (14). Let R, p > 0, α, ε ∈ (0, 1], β ∈ ((1/p -1/2) + , 1) and f ∈ SB β p,∞ (R, ε). Suppose first that p ≥ 2, and let k be the largest integer such that 2 k ≤ (α 2 N ) 1/(2β+2) . We use Lemma 12 of [START_REF] Barron | Risk bounds for model selection via penalization[END_REF] to get a regular partition m of [0, 1] of size 2 k such that h 2 (s, F m ) ≤ cR 2 2 -2kβ . Here, c is a term depending on β, p only. We deduce from (9) as m is regular and 2 k ≤ n for n large enough,

υ m ≤ c ′ |m| 2 α 2 N ε .
The result then follows from (38).

We now suppose that p < 2 and β > 2/p -1. We set k as above and apply the first assertion of Proposition 5 of [START_REF] Sart | Minimax bounds for besov classes in density estimation[END_REF] to get a partition m such that h 2 (s, F m ) ≤ cR 2 2 -2kβ and

I∈m 1 |I| ≤ 2 2k .
Moreover, log(1/|I|) ≤ c ′′ log n for all I ∈ m and for some term c ′′ depending only on β, p (for n large enough). Therefore, (8) entails

υ m ≤ c ′ α 2 N ε I∈m 1 |I| ,
and we use (38) as in the first case.

We finally assume that p < 2 and β ≤ 2/p -1. Since β ∈ (0, 1), we may assume that β ≤ 1/p. We set for j ≥ 0,

ηj = R2 j/2 (α 2 N ) -1/2 if 2 j ≤ √ α 2 N R(α 2 N ) -1/4 if 2 j > √ α 2 N .
Lemma 4 of [START_REF] Sart | Minimax bounds for besov classes in density estimation[END_REF] (with a suitable value of η j ) gives a partition m of M ∞ such that

|m j | ≤ R 2 -(j-1)(β-1/p+1/2) ηj-1 p ,
where m j = I ∈ m, |I| = 2 -j . This partition satisfies

h 2 (f, F m ) ≤ C 1 ∞ j=0 |m j |η 2 j , (39)
where C 1 depends on β, p only.

Observe that |m j | = 0 if 2 (j-1)(β-1/p+1/2) > (α 2 N ) 1/4 and 2 j ≥ √ α 2 N. We deduce from (8) that there exists c depending only on β, p and ε such that, for n large enough,

υ m ≤ c α 2 N   2 j ≤ √ α 2 N 2 j |m j | + √ α 2 N 2 j > √ α 2 N |m j |   . (40) Yet, 2 j ≤ √ α 2 N 2 j |m j | ≤ 2 j ≤ √ α 2 N 2 j 2 -(j-1)(β-1/p+1/2) 2 -(j-1)/2 (α 2 N ) 1/2 p ≤ 2 (β-1/p+1)p (α 2 N ) p/2 2 j ≤ √ α 2 N 2 j(2/p-1-β)p ≤ C 2 (α 2 N ) p/2 log (α 2 N ) θ (α 2 N ) (2/p-1-β)p/2 , ( 41
)
where θ = 0 if β < 2/p -1 and θ = 1 if β = 2/p -1. Moreover, C 2 only depends on β, p. We deduce,

2 j ≤ √ α 2 N 2 j |m j | ≤ C 2 log (α 2 N ) θ (α 2 N ) 1-βp/2 .
Moreover,

2 j > √ α 2 N |m j | ≤ 2 j > √ α 2 N 2 -(j-1)(β-1/p+1/2) (α 2 N ) 1/4 p ≤ 2 p(β-1/p+1/2) (α 2 N ) p/4 2 j > √ α 2 N 2 -jp(β-1/p+1/2) ≤ C 3 (α 2 N ) 1/2-βp/2 , ( 42
)
where C 3 only depends on p, β.

By putting (40), (41) and (42) together, we get for n large enough,

υ m ≤ C 4 log θ (α 2 N ) (α 2 N ) -βp/2 ,
where C 4 only depends on ε, p, β. Moreover, (39) yields

h 2 (f, F m ) ≤ C 1 R 2   1 α 2 N 2 j ≤ √ α 2 N 2 j |m j | + 1 √ α 2 N 2 j > √ α 2 N |m j |   .
We now use (41) and (42) to get

h 2 (f, F m ) ≤ C 5 R 2 log θ (α 2 N ) (α 2 N ) -βp/2 .
It then remains to apply (38).

4.5.2. Proof of (13). Because of (12), we only need to prove the result when β ∈ ((1/p -1) + , (1/p -1/2) + ]. If p ≥ 2, (1/p -1/2) + = 0 and there is nothing to show. We suppose therefore that p < 2. Note that ψ = βp/2 here.

We suppose first that β ≥ 2(1/p -1). Note that for all x ≥ ε, y > 0

, q ∈ [1, 2], √ x - √ y 2 ≤ ε 1-q |x -y| q .
Therefore, for all non negative map g, 2h 2 (f, g) ≤ ε 1-q d q q (f, g).

Let now q ∈ [1, 2] such that β = 2(1/p -1/q) and k be the largest integer such that 2 k ≤ (α 2 N) 1/(2+q(β-1/p)) . The third point of Proposition 5 of [START_REF] Sart | Minimax bounds for besov classes in density estimation[END_REF] shows the existence of a partition m ∈ M k such that

d q q (f, F m ) ≤ C ′ Rk2 -kq(β+1/q-1/p) and I∈m 1 |I| ≤ k2 k .
Here, C ′ depends on q, β, p only. We deduce from (8), that for n large enough,

υ m ≤ c ′ α 2 N k2 k .
It then remains to replace k by its value and apply (38).

We now suppose that β ∈ (1/p -1, 2(1/p -1)). We set for j ≥ 0,

ηj = R(α 2 N ) -1 2 j if 2 j ≤ √ α 2 N R(α 2 N ) -1/2 if 2 j > √ α 2 N .
Lemma 4 of [START_REF] Sart | Minimax bounds for besov classes in density estimation[END_REF] gives a partition m of M ∞ such that

|m j | ≤ R 2 -(j-1)(β-1/p+1) ηj-1 p ,
where m j = I ∈ m, |I| = 2 -j and such that

2h 2 (f, F m ) ≤ d 1 (f, F m ) ≤ C 1 ∞ j=0 |m j |η j ,
where C 1 depends on β, p only. We then proceed as in the end of the proof of (14).

4.6. Proofs of the minimax lower bounds 4.6.1. Proofs of the left-hand sides of (10), (11) and proof of (16). We need the following lemma that ensues from [START_REF] John C Duchi | Minimax optimal procedures for locally private estimation[END_REF].

Lemma 10. We endow the set of densities with a distance d, consider D ≥ 1, and endow {0, 1} D with the Hamming distance

∆(δ, δ ′ ) = D k=1 δ k -δ ′ k .
We consider η > 0 and a family of densities

F = {f δ , δ ∈ {0, 1} D } satisfying d 2 (f δ , f δ ) ≥ η∆(δ, δ ′ ) (43)
for all δ, δ ′ ∈ {0, 1} D . Moreover, we suppose that for all δ, δ ′ ∈ {0, 1} D such that ∆(δ, δ ′ ) = 1,

d 2 1 (f δ , f δ ′ ) ≤ 1 n(e α -1) 2 . (44) Then, inf f ,Q sup f ∈F E d 2 (f, f ) ≥ 0.03Dη,
where the infimum is taken over all privacy mechanisms Q satisfying (1) and all estimators f based on the privatised data Y 1 , . . . , Y n .

Proof of Lemma 10. We denote by M δ the distribution measure of a α-locally differential private sample (Y 1 , . . . , Y n ) when the X i are distributed according to the density f δ . Corollary 3 of [START_REF] John C Duchi | Minimax optimal procedures for locally private estimation[END_REF] says that

K(M δ , M δ ′ ) ≤ n(e α -1) 2 d 2 1 (f δ , f δ ′ ) for all δ, δ ′ , where K(•, •) denotes the Kullback-Leibler divergence. Therefore, K(M δ , M δ ′ ) ≤ 1 for all δ, δ ′ such that ∆(δ, δ ′ ) = 1. It then follows from classical arguments, see (2.84) of [Tsy03] for instance, that inf δ∈{0,1} D Q sup f δ ∈F E ∆(δ, δ) ≥ D 1 -1/2 /2. ( 45
)
Let now f be an arbitrary estimator of f . Let δ f ∈ {0, 1} D be a random variable such that

d(f δ f , f ) = inf δ∈{0,1} D d(f δ , f ). We have for all δ, d(f δ , f δ f ) ≤ 2d(f δ , f ) and hence inf f ,Q sup f δ ∈F E d 2 (f δ , f ) ≥ (1/4) inf δ,Q sup f δ ∈F E d 2 (f δ , fδ ) ≥ (η/4) inf δ,Q sup f δ ∈F E ∆(δ, δ) .
We conclude by using (45).

Lemma 11. We consider α, p, R > 0, and β, ε ∈ (0, 1).

• Suppose that R ≥ 10, that D is the smallest integer larger than

D 1+2β ≥ (2 -4β /768)R 2 (e α -1) √ n and that η = (2 -4β /1536)R 2 D -2β-1 .
Then, there exists for n large enough a collection F ⊂ SB β ∞,∞ (R) of densities satisfying the assumptions of Lemma 10 with d = h.

• Suppose that R ≥ 16, that D is the smallest integer larger than

D 1+β ≥ (2 -2β /64)R(e α -1) √ n and that η = (2 -2β /128)RD -1-β .
Then, there exists for n large enough a collection F ⊂ B β ∞,∞ (R) of densities satisfying the assumptions of Lemma 10 with d = h.

• Suppose that D is the smallest integer larger than

D 1+β ≥ (2 -2β /64)R(e α -1) √ n and η < (2 -4β /1536)R 2 D -2β-1 .
Then, there exists for n large enough a collection F ⊂ F β ∞,∞ (R, ε) of densities satisfying the assumptions of Lemma 10 with d = h.

• Suppose that β ≤ 1/p, that D is the largest integer smaller than

2 -pβ R p (e α -1)
√ n

1-pβ and η = 1/(16(e α -1) √ n). Then, there exists for n large enough a collection F ⊂ F β p,∞ (R, ε) of densities satisfying the assumptions of Lemma 10 with d = h.

Proof of the first point of Lemma 11. We consider a non-negative map K defined on R, vanishing outside (0, 1/2), and whose restriction to [0, 1] belongs to B β ∞,∞ (1). We may for instance choose the triangle function

K(x) = min{x, 1/2 -x}½ [0,1/2] (x).
We define for k ∈ {1, . . . , 2D} and x ∈ [0, 1],

ϕ k (x) = 2 -4β-2 R 2 D -2β K 2 4D x - k -1 4D . Each ϕ k is compactly supported on [(k -1)/(4D), (k -1/2)/(4D)] ⊂ [0, 1/2) and belongs to SB β ∞,∞ (R/2). Let ϕ ∈ SB β ∞,∞ (2 √ 6
) be a density defined on [0, 1] and vanishing outside (1/2, 1], say ϕ

(x) = 24(x -1/2) 2 ½ [1/2,1] (x).
We then define for δ ∈ {0, 1} D and x ∈ [0, 1],

f δ (x) = (1 -p) ϕ(x) + D k=1 {δ k ϕ 2k-1 (x) + (1 -δ k )ϕ 2k (x)} , where p = D ϕ k (x) dx = 2 -4β-4 R 2 D -2β τ, (46)
and where τ = R K 2 (x) dx = 1/96. We suppose from now on that n is large enough to ensure p ∈ (0, 1]. This in particular implies that f δ is a density. Moreover,

f δ belongs to SB β ∞,∞ (max{2 √ 6 + R/2, R}) ⊂ SB β ∞,∞ (R) as R ≥ 10. For all δ, δ ′ ∈ {0, 1} D such that ∆(δ, δ ′ ) = 1, there exists k ′ ∈ {1, . . . , 2D -1} such that |f δ -f δ ′ | = |ϕ k ′ -ϕ k ′ +1 | = ϕ k ′ + ϕ k ′ +1 . It then follows from (46) that d 1 (f δ , f δ ′ ) = 2 -4β-3 R 2 D -2β-1 τ.
The condition on D then ensures that (44) is met.

Besides, for all δ, δ ′ ∈ {0, 1} D ,

f δ -f δ ′ = D k=1 δ k -δ ′ k √ ϕ 2k-1 + √ ϕ 2k
and hence,

h 2 (f δ , f δ ′ ) = 1 2 D k=1 δ k -δ ′ k 2 ϕ 2k-1 (x) + ϕ 2k (x) 2 dx = 2 -4β-4 R 2 D -2β-1 τ D k=1 δ k -δ ′ k 2 = 2 -4β-4 R 2 D -2β-1 τ ∆(δ, δ ′ ),
which leads to (43).

Sketch of the proof of the second point of Lemma 11. We set for

x ∈ R, K(x) = min{x, 1/2 - x}½ [0,1/2] (x), and for k ∈ {1, . . . , 2D}, x ∈ [0, 1], φ k (x) = 2 -2β-1 RD -β K 4D x - k -1 4D . Note that φ k ∈ B β ∞,∞ (R/2). Let φ ∈ B β ∞,∞ (8)
be the density defined by φ(x) = 8|x -1/2|½ [1/2,1] (x).

We then define the collection F = {f δ , δ ∈ {0, 1} D } by setting

f δ (x) = (1 -p) φ(x) + D k=1 {δ k φ 2k-1 (x) + (1 -δ k )φ 2k (x)} , where p = D φ k (x) dx = 2 -2β-3 RD -β τ,
and where τ = R K(x) dx = 1/16. The proof that F fulfils the conditions of Lemma 10 is similar to the proof of the first point.

Sketch of the proof of the third point of Lemma 11.

To keep this paper to a reasonable size, we only say that the family F can be defined by Then, f δ is a density, upper bounded by 2 and lower bounded by ε if n is large enough.

f δ (x) = (1 -p) ½ [0,1] (x) + D k=1 {δ k φ 2k-1 (x) + (1 -δ k )φ 2k (x)} ,
Let h > 0. Since f δ (x) = f δ (x + h) for x ∈ (2D/r, 1 -h), We may now prove the left-hand side of (10). We apply Lemma 10 to the family given by the second point of Lemma 11. This leads to the lower bound

R α (B β ∞,∞ (R)) ≥ c ′ 1 (e α -1) 2 n β 2β+2
, where c ′ depends on β, R only. It then remains to use the elementary inequality e α -1 ≤ 2α when α ∈ (0, 1].

The proof of the left-hand side of (11) is similar. We just use the family given by the first point of Lemma 11. As to (16), we use the family given by the third point if ψ = β/(β + 1) and by the four point if ψ = βp/2. 4.6.2. Proof of (17). The proof when ψ ′ = β/(β+1) ensues from the same standard arguments than the ones used in the proof of Proposition 2.1 of [START_REF] Butucea | Local differential privacy: Elbow effect in optimal density estimation and adaptation over besov ellipsoids[END_REF]. To make the paper self contained, we may also observe that the collection defined in the third point of Lemma 11 satisfies (43) with d = d 2 , and η = (2 -4β /768)R 2 D -2β-1 . It then remains to notice that

R α (B β p,∞ (R, ε), d 2 2 ) ≥ R α (B β ∞,∞ (R, ε), d 2
2 ) and apply Lemma 10 to get the result.

The proof when ψ ′ = (β -1/p + 1/2)/(β -1/p + 1) is rather similar to that of [START_REF] Birgé | Model selection for density estimation with L 2 -loss[END_REF] in the direct case. We introduce a density ϕ on R with support included in (0, 1). We suppose that the restriction of ϕ to [0, 1] belongs to B β p,∞ (R). We set r = 2(e α -1) √ n, and a such that a 1+β-1/p = Rr 1/p-β . The map g(x) = aϕ(arx) is compactly supported on [0, 1/2] when n is large enough.

We define two densities f 1 and f 2 for x ∈ [0, 1] by f 1 (x) = g(x)+1-1/r, and f 2 (x) = f 1 (1-x). They both belong to B β p,∞ (R, ε) when n is large enough. Moreover,

d 2 2 (f 1 , f 2 ) = 2 g 2 2 ≥ η
where • 2 denotes the L 2 norm, and where η = 2 ϕ 2 2 R 1/(1+β-1/p) r -2(β-1/p+1/2)/(β-1/p+1) . We also have,

d 1 (f 1 , f 2 ) = 2
1/(ar) 0 g(x) dx = 2/r.

We then use Lemma 10 with d = d 2 , F = {f 1 , f 2 } and conclude by using the elementary inequality e α -1 ≤ 2α when α ∈ (0, 1]. 4.7. Proof of Proposition 7. We only need to prove the upper bound. The idea is simply to randomize the sample to act as if the density was bounded from below by a constant, say 1/4. Let for i ∈ {1, . . . , n}, Y i be the confidential version of X i . Then Y i takes the form Y i = (Y i (I)) I∈∪ j∈{0,...,n} mj where Y i (I) = ½ I (X i ) + 2(1 + 1/δ)(1 + j) 1+δ α W i (I), and where W i (I) is an independent copy of W (I).

We now simulate n uniform random variables U 1 , . . . , U n on [0, 1], n Bernoulli random variables η 1 , . . . , η n with parameter 1/4, and n copies W ′ 1 (I), . . . , W ′ n (I) of W (I). Each of these variables is generated independently of all the others. We then set

Y ′ i (I) = ½ I (U i ) + 2(1 + 1/δ)(1 + j) 1+δ α W ′ i (I), Y ′′ i (I) = (1 -η i )Y i (I) + η i Y ′ i (I). Let us observe that Y ′′ i (I) = ½ I (X ′ i ) + 2(1 + 1/δ)(1 + j) 1+δ α W ′′ i (I),
where X ′ i = η i U i + (1 -η i )X i admits the density f ′ defined for x ∈ [0, 1] by f ′ (x) = 1/4 + (3/4)f (x), and where W ′′ i (I) = (1 -η i )W i (I) + η i W ′ i (I) is a Laplace random variable.

We set Y ′′ i = (Y ′′ i (I)) I∈∪ j∈{0,...,n} mj and apply our procedure to the data Y ′′ 1 , . . . , Y ′′ n to estimate f ′ . Since f ∈ F β p,∞ (R, 0), f ′ lies in B β p,∞ (3R/4, 1/4). It then follows from (13), that our estimator f satisfies for n large enough (depending on p, β, R, α but not on f ),

E h 2 (f ′ , f ) ≤ c 1 log γ n nα 2 ψ . ( 47
)
We then set f ′ = min{ f , 7/4} and f = (4/3)( f ′ -1/4). Note that h 2 (f ′ , f ′ ) ≤ h 2 (f ′ , f ) since f ′ ≤ 7/4. Moreover,

d 2 2 (f, f ) = 16 9 d 2 2 (f ′ , f ′ ) ≤ 224 9 h 2 (f ′ , f ′ ) ≤ 224 9 h 2 (f ′ , f ).
We then use (47) to conclude.

Remark: the estimator f does not only depend on the data Y 1 , . . . , Y n but also on some additional random variables generated artificially. This dependence can be removed by taking the conditional expectation f of the estimator f given the data. Jensen's inequality then shows that

E[d 2 2 (f, f )] ≤ E[d 2 2 (f, f )].

  where p and the φ k are defined in the proof of the second point.Sketch of the proof of the four point of Lemma 11. For k ∈ {1, . . . , 2D}, and x ∈ [0, 1], we setg k (x) = ½ [0,1] r x -k -1 r ,where r = 2(e α -1) √ n. Each g k vanishes outside [(k -1)/r, k/r]. We set for δ ∈ {0, 1} D andx ∈ [0, 1],f δ (x) = (1 -D/r) ½ [0,1] (x) + D k=1{δ k g 2k-1 (x) + (1 -δ k )g 2k (x)} .

  |f δ (x + h) -f δ (x)| p dx = 2D k=1 [(k-1)/r,k/r]∩[0,1-h] |f δ (x + h) -f δ (x)| p dx. Let (x, x + h) ∈ [0, 1] 2 . Then |f δ (x + h) -f δ (x)| = 0 if x ∈ ((k -1)/r, k/r -h)and is bounded from above by 1 otherwise. We deduce,[0,1-h] |f δ (x + h) -f δ (x)| p dx = 2D k=1 [(k-1)/r,k/r]∩[k/r-h,k/r]∩[0,1-h] |f δ (x + h) -f δ (x)| p dx ≤ 2D min{h, 1/r}. Therefore, [0,1-h] |f δ (x + h) -f δ (x)| p dx 1/p ≤ 2 1/p D 1/p r β-1/p h βand f δ belongs to B β p,∞ (R, ε). Elementary computations give (43) and (44).