Differentially private sub-Gaussian location estimators
Marco Avella-Medina Victor-Emmanuel Brunel





DP location estimators
















M. Avella-Medina and V.-E. Brunel



abstractnameskip Abstract: 



 We tackle the problem of estimating a location parameter with differential privacy guarantees and sub-Gaussian deviations. Recent work in statistics has focused on the study of estimators that achieve sub-Gaussian type deviations even for heavy tailed data. We revisit some of these estimators through the lens of differential privacy and show that a naive application of the Laplace mechanism can lead to sub-optimal results. We design two private algorithms for estimating the median that lead to estimators with sub-Gaussian type errors. Unlike most existing differentially private median estimators, both algorithms are well defined for unbounded random variables that are not even required to have finite moments. We then turn to the problem of sub-Gaussian mean estimation and show that under heavy tails natural differentially private alternatives lead to strictly worse deviations than their non-private sub-Gaussian counterparts. This is in sharp contrast with recent results that show that from an asymptotic perspective the cost of differential privacy is negligible. 

  





Differential Privacy
Location estimators
Sub-Gaussian estimators
Median











§ INTRODUCTION


Differential privacy has emerged as a rigorous mathematical approach to privacy that has been extensively studied in the theoretical computer science and machine learning literature following the path breaking work of <cit.>.  In this framework one assumes that there is a trusted curator that holds some data containing some possibly sensitive records of n individuals. The goal of privacy is to simultaneously protect every individual record while releasing global characteristics of the database<cit.>.

Even though the machine learning community has been very prolific in developing differentially private algorithms for complex settings such as multi-armed bandit problems <cit.>,  high-dimensional regression <cit.> and  deep learning <cit.>,  some  basic statistical questions are only starting to be understood. For example, the first statistical minimax rates of convergence under differential privacy were recently established in <cit.>. Some earlier work framing differential privacy in traditional statistics terms include  <cit.>.  Recent work  has also sought to develop differential privacy tools for statistical inference and hypothesis testing <cit.>

In this paper we revisit the simple statistical problem of location parameter estimation and study the non-asymptotic deviations of differentially private location parameter estimators. More specifically, we consider the problem of constructing median and mean estimators that achieve sub-Gaussian deviations under heavy tails.



 §.§ Motivation

It is well known that given a random iid sample X_1,…,X_n of sub-Gaussian random variables with [X_1]=μ and [X_1]=σ^2,  the empirical mean X_n=1/n∑_i=1^nX_i satisfies with probability at least 1-α

    |X_n-μ|≤√(2σ^2log(2/α)/n).

The accuracy of the empirical mean estimator expressed in the above deviation inequality is a direct consequence of the sub-Gaussian assumption. In fact the dependence on 2/α in the error worsens significantly when the distribution does not have a moment generating function. In particular, when X_1 is only assumed to have two finite moments, one cannot get an error whose order is smaller than √(2σ^2/(nα)) as shown in <cit.>.  
For the empirical median on the other hand, one does not even need to assume any finite moments in order to establish similar sub-Gaussian deviations.

In light of <cit.>, one may naturally wonder how differential privacy will affect the deviation bounds discussed above. The statistical minimax rates established in <cit.> show that the rates of convergence of differentially private mean estimators are described by two terms. The first one correspond to the usual parametric 1/√(n) convergence, while the second one is driven by the differential privacy tuning parameters and  and is of the order 1/n. Consequently for large n differential privacy does not come at the expense of slower statistical convergence rates. Even though it seems intuitive that a similar phenomenon from a non-asymptotic deviations perspective deviations there are several technical obstacles that need to be addressed before one can attempt to establish such results.

A notorious technical difficulty that renders the study of non-asymptotic deviations challenging for differentially private mean and median estimators is the vast majority of existing algorithms requires the input data to be bounded; see for example <cit.>. This is clearly unsatisfactory from a theoretical and practical perspective as it rules out common distribution used in statistical modelling such as the normal, gamma and t-distributions just to name a few. This is particularly disturbing for median estimators since the usual non-private empirical median does not even need the existence of finite moments in order to exhibit sub-Gaussian deviations.






 §.§ Our contributions






  * We derive the first differentially private  median estimators with sub-Gaussian  type errors under minimal  conditions. This should arguably be one of the simplest differentially private estimators for which one can establish sub-Gaussian deviations without assuming bounded variables or the existence of a moment generating function. We attain this objective for two new differentially private median estimators that build on two different carefully calibrated variants of the popular Laplace mechanism. Indeed, the naive Laplace mechanism is not directly applicable to the median when the support of the data is unbounded. The first algorithm adapts the idea of smooth sensitivity calibration introduced in <cit.> for our median estimation problem with unbounded data without any finite moment assumptions. This first construction requires a truncation step of the data that can be avoided by our second algorithm. The latter revisits the propose-test-release paradigm introduced in <cit.> and leads to the desired sub-Gaussian deviations while avoiding any truncation. This is achieved by carefully controlling for the occurrence of unfavorable data configurations that are observed with negligible probability. 

We would like to highlight that two other mechanisms, essentially tailored for the estimation of location parameters,  have also been studied: exponential mechanism <cit.> and perturbation of the loss function for M-estimators <cit.>. However, these mechanisms seem not to be applicable to either the mean (unless the data are bounded), or the median. Indeed, in the case of the mean, the loss function is not Lipschitz and in the case of the median, the loss function is not smooth, which are two requirements for the validity of these mechanisms. Therefore, it seems that even the seemingly simple problem of estimating the median of unbounded random variables in a differentially private fashion is more involved than one would expect. 


  * 




We explore the possibility of constructing differentially private mean estimators with sub-Gaussian type leading errors terms when the underlying distributions are only assumed to have two finite moments.  This question is motivated by the significant attention given to the study of sub-Gaussian mean estimators over the last years  <cit.> and the numerous successful extensions of these methods to more complex models including <cit.>.  Unlike our private median estimators, natural differential private counterparts of known sub-Gaussian mean estimators fail to yield the desired deviations. This  suggests that differentially private mean estimation might come at the expense of worse non-asymptotic high probability deviations.







§ PRELIMINARIES




 §.§ Definitions



For x=(x_1,…,x_n)∈^n, we denote by x_(1), …, x_(n) the reordered coordinates of x in nondecreasing order, i.e. min_1≤ i≤ n x_i=x_(1)≤…≤ x_(n)=max_1≤ i≤ n x_i. We let ℓ=⌊ n/2⌋ and m̂(x)=x_(l) be the empirical (left) median of x.

For T>0 and u∈, let the truncation operator f_T be defined as f_T(u)=u if |u|≤ T, f_T(u)=sign(u)T otherwise. For x∈^n, let m̂_T(x)=m̂(y), where y=(y_1,…,y_n) is defined as the truncated version of x at level T, i.e., y_i=f_T(x_i), i=1,…,n.

For any two vectors x,x'∈^n, we define their Hamming distance (x,x') as the number of coordinates that differ in x and x': (x,x')=#{i=1,…,n:x_i≠ x_i'}, where # stands for cardinality. Before formally defining (ε,δ)-differential privacy, we first review some useful notions of sensitivity to the data that will serve as building blocks in the construction of our algorithms.






	Let h:^n→ be a given function. 
	
		
  * The local sensitivity of h maps any data point x∈^n to the (possibly infinite) number 
    _h(x)=sup{|h(x')-h(x)|: x'∈^n, (x,x')≤ 1}.

		 
		
  * The global sensitivity of h is the (possibly infinite) number 
    _h=sup_x∈^n_h(x).
 
		
  * For all β>0, the β-smooth sensitivity of h is the mapping 
	
    _h^(β)(x)=sup_x'∈^n(e^-β(x,x')LS_h(x')),    x∈^n.

	





	
  * It is easy to see that for all x∈^n, the local sensitivity of the empirical median is
	
    _m̂(x)=max(x_(ℓ+1)-x_(ℓ),x_(ℓ)-x_(ℓ-1)).

	Moreover, for all β>0 and all x∈^n, _m̂^(β)(x)=∞, and _m̂=∞.
	
  * Let μ̂(x)=n^-1∑_i=1^n x_i, x∈^n be the empirical mean function. Then, all the above quantities are infinite.
	
  * Let μ̂_T(x)=n^-1∑_i=1^n f_T(x_i) be the empirical mean of the truncated entries of x∈^n. Then, for all x∈^n, _μ̂_T(x)=n^-1max(T-f_T(x_(1)),f_T(x_(n))+T). Thus, _μ̂_T=2T and _μ̂_T(x)≤ 2T, for all x∈^d. 
	



Let us now compute the smooth sensitivity of the empirical median of truncated numbers.

 
	Let T>0 and x∈^n. Let y=(y_1,…,y_n) with y_i=f_T(x_i), i=1,…,n. For all k<0 (resp. k>n), set y_(k)=-T (resp. y_(k)=T). Then, for all β>0, _m̂_T^(β)(x)=max_k≥ 0e^-β kmax_t=0,…,k+1(y_(ℓ+t)-y_(ℓ+t-k-1)).


This lemma is a direct consequence of <cit.>. The same authors also showed that _m̂_T^(β)(x) can be computed in O(nlog n) operations .

In what follows, we refer as random function to any function h̃:^n→ such that for all x∈^n, h̃(x) is a Borelian random variable. In this paper, we will use the hat sign to denote non-randomized estimators, and the tilde sign to denote their randomized version (e.g., ĥ vs. h̃).


	Let ε,δ>0. A random function h̃ is called (ε,δ)-differentially private if and only if for each pair x,x'∈^n with (x,x')≤ 1 and for all Borel sets B⊆, 

    [h̃(x)∈ B]≤ e^ε[h̃(x')∈ B]+δ.



It is important to note that for all β≥β'>0, all functions h:^n→ and all x∈^n, it holds that

    _h(x)≤_h^(β)(x)≤_h^(β')(x)≤_h(x)≤∞.

In particular, using the global sensitivity is more restrictive than using the smooth sensitivities, which itself is more restrictive than using the local sensitivity.




 §.§ Background


The Laplace mechanism is one of the basic tools used in the differential privacy literature in order to construct private algorithms. The basic idea is to make deterministic functions private by adding  random noise calibrated using their sensitivity to the data. Let us review some well know results that we will use in the construction of our differentially private estimators.
Recall that the Laplace distribution with parameter λ>0 is the continuous probability distribution with density (λ/2)e^-λ|u|, u∈. We denote this distribution by Lap(λ). 

The following theorem, due to <cit.>, gives a very simple way to make a function h differentially private. However, it requires the very strong assumption that h has a finite global sensitivity.

 
	Let h:^n→ be a function with finite global sensitivity. Let Z be a Laplace random variable with parameter 1. For all ε>0, the random function h̃(x)=h(x)+Z/ε_h, x∈^n, is (ε,0)-differentially private.



The following result is due to <cit.>, and allows for less restrictive functions h.

 
	Let h:^n→ and assume that for all k=1,…,n and all x∈^n, _h^(k)(x)<∞. Let Z be a Laplace random variable with parameter 1. Let ε,δ>0 and set β=ε/2log(1/δ). Then, the random function h̃(x)=h(x)+2Z/ε_h^(β)(x), x∈^n, is (ε,δ)-differentially private.


Note that these two versions of the Laplace mechanisms, using either the global, or the smooth sensitivities, cannot be used directly for the empirical mean or the empirical median when the data are unbounded, since the two sensitivities are infinite. 
In the next section, we first adapt the Laplace mechanism with the smooth sensitivity, by truncating the data in order to ensure a finite smooth sensitivity. Note that the local sensitivity, which is the least restrictive in the sense of (<ref>), cannot be used directly in a Laplace mechanism, as explained in <cit.>. In the second part of next section, we define an estimator that uses some sort of local sensitivity, which is less restrictive than the smooth sensitivity and thanks to which we can avoid truncating the data.





§ MEDIAN ESTIMATION



In this section we describe two differentially private median estimators. As explained above, the first one uses the Laplace mechanism but forces us to truncate the data, and to assume that the true (and unknown) median of the data is bounded. In the second algorithm, we no longer truncate the data, by using a more subtle approach than the Laplace mechanism. Our differentially private algorithms seem to be the first ones to achieve optimal statistical rates of convergence under no moment assumptions on the data.



 §.§ Private median via smooth sensitivity calibration
 

We will only require the following distributional assumption in the derivation of our deviation inequalities for our  private median estimators.


 
	The distribution of X_1 has a density f with respect to the Lebesgue measure and it has a unique median m. Moreover, there exist positive constants r,L such that f(u)≥ L, for all u∈ [m-r,m+r].


In particular, under this assumption, the cdf F of X_1 satisfies the following: 

    |F(u)-F(v)|≥ L|u-v|, ∀ u,v∈ [m-r,m+r].
 
Even though the existence of a density is not very restrictive in practice, it seems that our results would still be true if we only assumed the existence of a density in the neighborhood [m-r,m+r] of m. Moreover, (<ref>) is a natural and standard assumption on the distribution of X_1 in order to estimate its population median m at the usual n^-1/2 rate. Indeed, if (<ref>) does not hold, then the distribution of X_1 does not put enough mass around the median, which becomes harder to estimate. For instance, it is well known that the empirical median of iid random variables is only asymptotically normal when the data have a positive density at the true median (the asymptotic variance being (4f(m))^-1).


We define the randomized estimator of the median as 

    m̃_T(x)=m̂_T(x)+2Z/ε_h^(β)(x), x∈^n,

where β=ε/2log(2/δ) and Z is a Laplace random variable with parameter 1. By Theorem <ref>, m̃_T is (ε,δ)-differentially private, and we have the following theorem. 

 

Let X=(X_1,…,X_n) be a vector of iid random variables satisfying Assumption <ref>. Assume that |m|≤ R for some R>0 and let T>R+r. Let α∈ [8e^-nL^2r^2/4,1]. Then, with probability at least 1-α,

    |m̃_T(X)-m|    ≤√(2log(8/α)/nL^2) + 4log(8/α)log(2/δ)/eLε^2 n(log⌊Lrn2⌋+ log(4/α)) 
        + 4Tlog(4/α)/εe^-ε Lrn/4log(2/δ).




Note that in this theorem, the probability is computed with respect to the joint randomness of the algorithm and of the data. Moreover, our estimator truncates the data but our guarantees do not assume that the data are bounded. Perhaps a drawback of this result is that it assumes that the true median lies in a bounded range.


	The proof is decomposed into two parts. First, we bound the smooth sensitivity of m̂_T evaluated at the random sample X=(X_1,…,X_n) with high probability, using Assumption <ref> (Lemma <ref> with α_2=α/4). Then, again using this assumption, we bound the deviations of the empirical truncated median m̂_T(X) (Lemma <ref> with α_3=α/4). Finally, we get the desired result by using a union bound, where we also control the tails of the Laplace random variable Z and apply the triangle inequality.
	
	
 

Let α_2∈ (0,1]. With probability at least 1-α_2-2e^-nL^2r^2/4,

    _m̂_T^(β)(X) ≤1/eLβ n(log⌊ Lrn/2⌋+ log(1/α_2)) +2Te^-β Lrn/2.







 

Let α_3∈ [2e^-nL^2r^2/2,1]. Then, with probability at least 1-α_3,

    |m̂_T(X)-m|≤√(2log(2/α_3)/nL^2).




The restriction on α_3 is necessary because Assumption <ref> only imposes a control of the cdf F on a neighborhood of m of size r.





The first term in the upper bound in Theorem <ref> is a sub-Gaussian term that comes from the empirical median itself. The other terms, of a smaller order in n, are the price to pay in order to apply the Laplace mechanism to the truncated median. Note that T can be chosen as a growing sequence of n so long as the last term does remains very small (while in many applications, ε may also depend on n, making the ratio in the exponential term small).




 §.§ A propose-test-release approach


Our second algorithm is inspired by the propose-test-release paradigm introduced in <cit.>. The high level idea of this approach is to propose a bound on the local sensitivity of the desired statistic and test in a differentially private way whether the suggested bound is high enough to ensure privacy. If the proposed bound passes the test then an appropriately calibrated noisy version of the statistic is released. If the proposed bound is not high enough then the algorithm returns “No Reply", which we denote by ⊥. Our estimator is carefully calibrated so that the resulting algorithm returns a numerical value with high probability while ensuring satisfactory finite sample statistical guarantees. In particular,  the leading term in the deviations resulting from this procedure coincides with the usual median sub-Gaussian deviations and  dominates the  additional error term  introduced by the privacy inducing mechanism. We require some additional notation in order to define our estimator.  A key component of the algorithm is the quantity


    Â(x)=min{k=0,1,…: ∃ x'∈^n, (x,x')=k, |m̂ (x)-m̂(x')|>η}.

It is not too difficult to see that the global sensitivity of Â equals 1 since for any x' such that (x,x')=1, the only possible values of Â(x') are Â(x)-1,Â(x) and Â(x)+1. Therefore, by Theorem <ref>, Â can be made (ε,0)-differentially private with the Laplace mechanism

    Ã(x)=Â(x)+1/ε Z_1,

where  Z_1∼Lap(1).  We introduce another independent random variable Z_2∼Lap(1) and define our randomized propose-test-release median estimator as

    m̃(x)=⊥   Ã(x) ≤ 1+1/εlog(2/δ) 
    m̂(x)+η/εZ_2    ,

for all x∈^n. Intuitively, m̃(x) is more likely to output “No Reply” for less favorable data configurations x∈^n that lead to small values of Â(x).  Clearly the choice η is critical as it controls the size of Â(x) and hence the probability of no reply, and also the noise term added to m̂(x) when it is released.   

It is interesting to notice that from a computer science perspective Â(x) can be thought of as the answer to the query: what is the minimum number of observations that we need to change to x before we change the value of the empirical median m̂(x) by at least η? From a statistical point of view,  it is reminiscent of the finite sample breakdown point studied in robust statistics <cit.>. While the finite sample breakdown point is usually defined as the minimum number of points that needs to be moved arbitrarily before an estimator becomes infinite, Â(x) can be interpreted as a relaxed version of the finite sample breakdown point of the median at the scale η.



The randomized estimator m̃ is (2ε,δ)-differentially private and can be computed in O(nlog(n)) time. Furthermore, let X=(X_1,…,X_n) be a vector of iid random variables that satisfy Assumption <ref> and let α∈ [8e^-L^2r^2n/2,1] and C=L^-1(1+log(4/α)/log(Lrn/2)). Then, choosing η=Clog(n)/ε n{log(2/δ)+log(8/α)+ε}, with probability at least 1-α we have that 

    |m̃(X)-m| ≤√(2log(8/α)/nL^2)+Clog(n){log(2/δ)+log(8/α)+ε}log(8/α)/ε^2 n



Note that in this theorem (as in Theorem <ref>), the probability is computed with respect to the joint randomness of the algorithm and of the data. Furthermore, the second term corresponds to a subexponential type error because the dependence on log(1/α) does not appear inside a square root.


 We only highlight the main ideas of the arguments and relegate some technical details to the proofs of Lemmas <ref>-<ref>  to the Appendix.  

The estimator m̃ can be shown to be (2ε,δ)-differentially private by adapting the arguments used for establishing differential privacy of  the propose-test-release median algorithm introduced in <cit.> (Lemma <ref>).  
Its computation is O(nlog(n)) time as it comes down to the complexity of sorting x=(x_1,…,x_n) and computing Â(x) using the sorted x for any x∈^n.  Once the data is sorted the computation of Â(x) can be done in O(nlog(n)) computations using an interval halving algorithm (Lemma <ref>).

For the desired sub-Gaussian deviation inequality we first note that with probability at least 1-α_2-τ_2

    |m̂(X)-m+η/εZ_2 | ≤√(2log(2/α_2)/nL^2)+ η/εlog(2/τ_2),

where we used the triangle inequality, equation (<ref>) in the Appendix and (|Z_2|>t)=e^-t. It therefore remains to verify that the choice of η stated in the theorem suffices to establish that the probability that m̃ gives a “No Reply” is at least α_1+τ_1. The main technical obstacle for this is to lower bound Â(X) with high probability. We establish this result by leveraging  Condition 1 in order to control the maximum gap between consecutive order statistics of X in a neighborhood of m̂(X) (Lemma <ref>).

 
The estimator m̃ is (2ε,δ)-differentially private.



 For all x∈^n, the computation of m̃(x) is O(nlog(n)).



Assume that Assumption <ref> holds and let η=Clog(n)/ε n{log(2/δ)+log(2/τ_1)+ε}. Then  for  τ_1∈ (0,1] and α_1∈(2e^-L^2r^2/2n,1],  we have that (m̃(X)=⊥)≤τ_1+α_1.






We note that while the propose-test-release median estimator of <cit.> was shown to converge in probability to the population median, it is easy to see that the resulting estimator converges at the rate n^1/3. Our estimator allows to take smaller values of ε and δ while preserving the finite sample sub-Gaussian deviations of the empirical median under minimal conditions.




§ DISCUSSION ON MEAN ESTIMATION




Recall the definition of the median of means function. Let K≤ n/2 be integer and let N=n/K, which we assume to be an integer, for the sake of simplicity. We partition the set {1,…,n} into N groups B_1,…,B_N of identical size K. For all x=(x_1,…,x_n)∈^n and each group B_j, j=1,…,N, we let x̅_j=K^-1∑_t∈ B_jx_t, the empirical mean of the coordinates of x indexed in B_j. We denote by x̅_(j), j=1,…,N the empirical means reordered in nondecreasing order. The median of means of x is defined as μ̂(x)=x̅_(ℓ), where now, ℓ=⌊ N/2⌋. 

It is well known that if X_1,…,X_n are iid random variables with only the first two moments assumed to be finite μ=[X_1] and σ^2=[X_1], then the median of mean estimator μ̂(X_1,…,X_n) satisfies the following, for N=8log(2/α) and K=n/N, where α∈ (0,1) is a prescribed probability level.

<cit.>
	With probability at least 1-α, 

    |μ̂(X_1,…,X_n)-μ|≤ 2σ√(log(2/α)/n).



However, the Laplace mechanism that we have used in Section <ref> cannot be applied directly to μ̂. It is easy to see that the global sensitivity _μ̂ is infinite. The local sensitivity is finite as long as the empirical means x̅_(j), j=1,…,N take at least three different values. In that case, _μ(x)=max(x̅_(ℓ)-x̅_(ℓ-1),x̅_(ℓ+1)-x̅_(ℓ)). However, the β-smooth sensitivity _μ̂^(β)(x) is infinite, for all x∈^n.

A natural alternative to μ̂ consists of truncating the empirical means x̅_j, j=1,…,N, before taking their median, or to first truncate the x_i's, compute the new empirical means on each block and take the median. These two functions are different, but we only focus on the first one, since a similar analysis would hold for the second one (with a different threshold).

For T>0, we define μ̂_T(x)=f_T(x̅_(ℓ)).

 
	Let β>0. Then, the β-smooth sensitivity of the function μ̂ is given by

    _μ̂_T^(β)=max_0≤ j≤ Ne^-β jmax_t=0,…,j+1(f_T(x̅_(ℓ+t))-f_T(x̅_(ℓ+t-j-1))),

where we set x̅_(j)=∞ if j≥ N+1 and x̅_(j)=-∞ if j≤ -1.
Moreover, it is bounded from above by 2T.


The proof of the first this lemma is similar to that of Lemma <ref> and is omitted here. For the second part, it is clear that one can bound _μ̂_T^(β) by f_T(x̅_(N))-f_T(x̅_(1)) and this bound is tight up to a constant. In general, unless T is significantly larger than √(n), X̅_(N)≥ T and X̅_(1)≤ -T with high probability. Therefore, the Laplace mechanism that we used in <ref> will not provide reasonable deviation bound. Actually, the same limitations also hold for the truncated mean estimator studied in <cit.>, where the authors deal with a truncation parameter T of order log n since their data are sub-Gaussian, whereas under the current assumptions, T should be taken of the order of √(n). In general, it seems that the usual estimators of the mean under the existence of only low moments (median of means, truncated mean, Catoni's estimators <cit.>) can not be adapted in a straightforward way in order to obtain differentially private estimators that admit a sub-Gaussian error plus a term of smaller order.

The propose-test-release approach  introduced in <ref> will also fail to give sub-Gaussian type deviations if applied to the median of means function. Indeed in order to obtain inequalities similar to the ones obtained in Theorem <ref> one would have to choose the constant η in equation (<ref>) to be of the order 1/n. However one can show that the expect the empirical means X̅_1,…,X̅_n are separated by a distance of at least of the order 1/√(nα) with probability 1-α. Consequently if we choose η smaller than 1/√(nα) the probability of “No Reply” of the propose-test-release approach will be too large since we will always have small values of Â(x). A similar argument suffices to see that our propose-test-release mechanism will also fail to give the desired deviations for the truncated mean estimator studied in <cit.>.







§ CONCLUSION


We studied the problem of differentially private location parameter estimation from a non-asymptotic deviations perspective.  In particular, we proposed the first private median estimators that exhibit a leading sub-Gaussian error  terms with high probability. Our first estimator uses truncation in order to get high probability control of the smooth sensitivity while the second one avoids truncating the data by first identifying in a privacy-preserving fashion whether the data are in a favorable configuration before releasing a noisy version of the desired output.

We showed that differentially private versions of well known sub-Gaussian mean estimators fail to exhibit the optimal deviations of their nonprivate counterparts. A possible explanation for these weaker results for mean estimation is that perhaps one can only expect to obtain sub-Gaussian type deviations for  differentially private versions of robust statistics in the sense of <cit.>. It would therefore be interesting to extend our methods to other robust statistics beyond the median.

plain





























§ APPENDIX: DIFFERENTIALLY PRIVATE SUB-GAUSSIAN LOCATION ESTIMATORS





 §.§ Proof of Lemma <ref>


Let k_0=⌊Lrn/2⌋. Note that k_0≤ n/4, since 2Lr≤ F(m+r)-F(m-r)≤  1, by Assumption <ref>. We decompose _h^(β)(X) into two parts:

    _m̂_T^(β)(X)     = max_k=0,…,k_0-1e^-β kmax_t=0,…,k+1(Y_(ℓ+t)-Y_(ℓ+t-k-1)) 
            + max_k≥ k_0e^-β kmax_t=0,…,k+1(Y_(ℓ+t)-Y_(ℓ+t-k-1))

The second term is upper bounded by 2Te^-β k_0. For the first term, we consider the event 𝒜={Y_(i+1)-Y_(i)≤Clog k_0/n, ∀ i=ℓ-k_0,…,ℓ+k_0-1}, where C=L^-1(1+log(1/α_2)/log(k_0)). If 𝒜 is satisfied, the first term in (<ref>) is bounded by 

    max_0≤ k≤ k_0-1 e^-β kkClog k_0/n    = max_0≤ k≤ k_0-1 e^-β kβ kClog k_0/β n
       ≤(max_u≥ 0e^-uu)Clog k_0/β n = Clog k_0/eβ n,
 
hence, if 𝒜 is satisfied, (<ref>) yields that 

    _m̂_T^(β)(X) ≤Clog k_0/eβ n+2Te^-β k_0.

Now, we control the probability of the complement of 𝒜. Consider the event ℬ={m-r<X_(ℓ-k_0)≤ X_(ℓ+k_0)<m+r}.
By Assumption <ref>, if ℬ is satisfied, it holds that for all i=ℓ-k_0,…,ℓ+k_0, X_(i)=Y_(i), and for all i=ℓ-k_0,…,ℓ+k_0-1,

    F(X_(i+1))-F(X_(i))    ≥ L(X_(i+1)-X_(i)) 
        = L(Y_(i+1)-Y_(i)),

hence, if 𝒜^∁ holds together with ℬ, then 

    max_i=ℓ-k_0,…,ℓ+k_0-1 U_(i+1)-U_(i)≥CLlog k_0/n,

where we have denoted by U_j=F(X_j), j=1,…,n. Therefore, 

    [𝒜^∁]     = [𝒜^∁∩ℬ] + [𝒜^∁∩ℬ^∁] 
       ≤[max_i=ℓ-k_0,…,ℓ+k_0-1 U_(i+1)-U_(i)≥CLlog k_0/n] +[ℬ^∁] 
       ≤∑_i=ℓ-k_0^ℓ+k_0-1[U_(i+1)-U_(i)≥CLlog k_0/n]+[ℬ^∁],

where the last inequality follows from a union bound. By Assumption <ref>, the U_j's are iid and uniformly distributed in [0,1]. Therefore, for all i=1,…,n-1, U_(i+1)-U_(i) has the same distribution as U_(1) and Therefore, for all i=ℓ-k_0,…,ℓ+k_0-1,

    [U_(i+1)-U_(i)≥CLlog k_0/n]     = [U_(1)≥CLlog k_0/n] 
        = [U_j≥CLlog k_0/n, ∀ j=1,…,n] 
        = [U_1≥CLlog k_0/n,]^n 
        = (1-CLlog k_0/n)^n ≤ e^-CLlog k_0.

In order to bound the probability of ℬ^∁, it suffices to note that 

    [ℬ^∁] = [X_(ℓ+k_0)>m+r]+[X_(ℓ-k_0)<m-r].

We only bound the first term in the right hand side of (<ref>), since the second term can be bounded with similar computations. By definition of the order statistics,

    [X_(ℓ+k_0)>m+r] 
          = [∑_i=1^n  1_X_i>m+r≥ n-(ℓ+k_0)+1] 
    	
          = [∑_i=1^n ( 1_X_i>m+r-(1-F(m+r))) ≥ n-(ℓ+k_0)+1-n(1-F(m+r))]
    	 
         ≤exp(-n/2(F(m+r)-ℓ+k_0/n)^2),

where the last inequality follows from Hoeffding's inequality. By Assumption <ref>, F(m+r)-ℓ+k_0/n≥ F(m)+Lr-1/2-k_0/n = Lr-k_0/n≥ Lr/2>0. Thus, using (<ref>), we have that [X_(ℓ+k_0)>m+r] ≤ e^-nL^2r^2/4=: α_1. Finally, we get that [ℬ^∁]≤ 2α_1. So, by (<ref>), 

    [𝒜^∁]    ≤ 2k_0e^-CLlog k_0+2α_1 
        = 2k_0^1-CL+2α_1 = α_2+2α_1.


This ends the proof of Lemma <ref>.




 §.§ Proof of Lemma <ref>


Let t∈ [0,r]. Then, 

    [|m̂(X)-m|>t] = [m̂(X)>m+t]+[m̂(X)<m-t].

Now, we only bound the first term, since the second term would be treated with the exact same arguments. By definition of the empirical median,

    [m̂(X)>m+t]     = [∑_i=1^n  1_X_i>m+t≥ n/2] 
        = [∑_i=1^n ( 1_X_i>m+t-(1-F(m+t)))≥ n(F(m+t)-1/2)] 
       ≤exp(-n/2(F(m+t)-1/2)^2) 
       ≤ e^-nL^2t^2/2,

where we used Hoeffding's inequality and Assumption <ref>. Therefore, we simply get, from (<ref>), that 

    [|m̂(X)-m|>t] ≤ 2e^-nL^2t^2/2.

Now, since -T<-R-r≤ m-r≤ m-t≤ m+t≤ m+r≤ R+r<T, if |m̂(X)-m|≤ t, then it must hold that m̂(X)=m̂_T(X), therefore, (<ref>) yields that 

    [|m̂_T(X)-m|>t] ≤[|m̂(X)-m|>t] ≤ 2e^-nL^2t^2/2.

This concludes the proof of the lemma, by taking t=√(2log(2/α_3)/nL^2).





 §.§ Proof of Lemma <ref>

Since  m̃(x)=⊥Ã(x)≤ 1+1/εlog(2/δ) and  Ã is (ε,0)-differentially private, it follows that 

    [m̃(x)=⊥]≤ e^ε[m̃(x')=⊥],
 
for all x,x' such that (x,x')≤ 1. Indeed outputting “No Reply” has the same privacy guarantee as Ã because differential privacy is not affected by post-processing <cit.>.

Let x,x'∈^n with (x,x')≤ 1. We will now show that for all Borel sets 𝒪⊆,

    [m̃(x)∈𝒪]≤  e^2ε[m̃(x')∈𝒪]+δ.

Note that for m̃(x) to be a real number, it has to be that the estimator has outputted a reply, i.e., Ã(x)>1+(1/ε)log(2/δ). On the one hand, if  |m̂(x)-m̂(x')|≤η, we have 

    [m̃(x)∈𝒪]   =[m̂(x)+η/εZ_2∈𝒪, Â(x)+1/εZ_1> 1+1/εlog(2/δ)] 
        =[m̂(x)+η/εZ_2∈𝒪][Â(x)+1/εZ_1 >1+1/εlog(2/δ)]
       ≤ e^ε[m̂(x')+η/εZ_2∈𝒪]e^ε[Â(x')+1/εZ_1 >1+1/εlog(2/δ)] 
       =e^2ε[m̃(x')∈𝒪]
       ≤ e^2ε[m̃(x')∈𝒪]+δ,

by the sliding property of the Laplace distribution <cit.> and where the second and the last equalities used independence of Z_1 and Z_2.  On the other hand, if |m̂(x)-m̂(x')| > η then Â(x)=Â(x')=1 which in turn entails that

    [m̃(x)∈𝒪]   =[m̂(x)+η/εZ_2∈𝒪, 1/εZ_1> 1/εlog(2/δ)]
       ≤[1/εZ_1 >1/εlog(2/δ)]
       =δ
       ≤ e^2ε[m̃(x')∈𝒪]+δ

Therefore, combining (<ref>) and (<ref>) yields (<ref>). Now, let 𝒪' be a Borel set of the extended real line ∪{⊥}. Then, 𝒪' is equal to either 𝒪, or 𝒪∪{⊥}, for some Borel set of . In the former case, (<ref>) concludes the proof of the lemma. In the latter case, we write, for all x,x'∈^n with (x,x')≤ 1:

    [m̃(x)∈𝒪']     = [m̃(x)∈𝒪] + [m̃(x)=⊥] 
       ≤ e^2ε[m̃(x')∈𝒪]+δ + e^ε[m̃(x')=⊥] 
       ≤ e^2ε[m̃(x')∈𝒪']+δ,

thanks to (<ref>) and (<ref>).



 §.§ Proof of Lemma <ref>


It suffices to show that Â(x) can be computed in near linear time.  For this we can  sort x and take the resulting order statistics x_(1),…,x_(n) to  compute Â(x)=min{k max_0≤ t≤ k+1 ( x_(m+t)-x_(m+t-k-1))>η}.  For a fixed k, solving max_0≤ t≤ k+1 ( x_(m+t)-x_(m+t-k-1)) takes at most O(n) operations. Furthermore, using a dichotomy method (which is valid since max_0≤ t≤ k+1 ( x_(m+t)-x_(m+t-k-1)) is monotone in k), we see that we only need to explore O(log(n)) values of k in order to find Â(x). Hence for sorted x, we showed that Â(x)  can be computed in in O(nlog (n)) time. Since the initial sorting step also takes O(n log (n)) operations, the overall algorithm is O(nlog(n)).



 §.§ Proof of Lemma <ref>

 Using the notation that we used in the proof of Lemma <ref>, it follows from the definition of m̃(X) that

    [m̃(X)=⊥]    =[Â(X)+1/εZ_1 ≤ 1+1/εlog(2/δ)] 
       ≤[{Â(X)+1/εZ_1 ≤ 1+1/εlog(2/δ)}∩ℬ] +[ℬ^∁]
       ≤[ {η n/Clog(n)+ 1/εZ_1≤ 1+1/εlog(2/δ)}∩ℬ]  +α_1
       ≤[η n/Clog(n) + 1/εZ_1≤1+1/εlog(2/δ)] +α_1 
       =[Z_1≤ε(1+ 1/εlog(2/δ)-η n/Clog(n))]+ α_1.

In order to set the above bound equal to τ_1+α_1 we have to use that [Z_1≤ -log(2/τ_1)]=τ_1. This requires that  

    -1/εlog(2/τ_1)=1+ 1/εlog(2/δ)-η n/Clog(n)

from which we obtain that

    η=Clog(n)/ε n(log(2/δ)+log(2/τ_1)+ε).




