{'fraction_non_alphanumeric': 0.04501836275322829, 'fraction_numerical': 0.012004896734194212, 'mean_word_length': 4.15448809281498, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Convergence Rates for Differentially Private Statistical Estimation

Differential privacy is a cryptographically-motivated definition of privacy which has gained significant attention over the past few years. Differentially private solutions enforce privacy by adding random noise to a function computed over the data, and the challenge in designing such algorithms is to control the added noise in order to optimize the privacy-accuracy-sample size tradeoff. This work studies differentially-private statistical estimation, and shows upper and lower bounds on the convergence rates of differentially private approximations to statistical estimators. Our results reveal a formal connection between differential privacy and the notion of Gross Error Sensitivity (GES) in robust statistics, by showing that the convergence rate of any differentially private approximation to an estimator that is accurate over a large class of distributions has to grow with the GES of the estimator. We then provide an upper bound on the convergence rate of a differentially private approximation to an estimator with bounded range and bounded GES. We show that the bounded range condition is necessary if we wish to ensure a strict form of differential privacy.


Introduction
Differential privacy (Dwork et al., 2006b) is a strong, cryptographically-motivated definition of privacy which has gained significant attention in the machine-learning and data-mining communities over the past few years (McSherry & Mironov, 2009; Appearing in Proceedings of the 29 th International Conference on Machine Learning, Edinburgh, Scotland, UK, 2012. Copyright 2012 by the author(s)/owner(s). Chaudhuri et al., 2011;Friedman & Schuster, 2010;Mohammed et al., 2011). In differentially private solutions, privacy is guaranteed by ensuring that the participation of a single individual in a database does not change the outcome of a private algorithm by much. This is typically achieved by adding some random noise, either to the sensitive input data, or to the output of some function, such as a classifier, computed on the sensitive data. While this guarantees privacy, for most statistical and machine learning tasks, there is a subsequent loss in statistical efficiency, in terms of the number of samples required to estimate a function to a given degree of accuracy. Thus the main challenge in designing differentially private algorithms is to optimize the privacy-accuracy-sample size trade-off, and a body of literature has been devoted to this goal.
In this paper, we focus on differentially-private statistical estimation. We ask: what properties should a statistical estimator have, so that it can be approximated accurately with differential privacy? Privately approximating an estimator based on a functional T that performs well when data is drawn from a specific distribution F is easy: ignore the sensitive data, and output T (F ). Thus the challenge is to design differentially private approximations to estimators that are accurate over a wide range of distributions.
Previous work (Smith, 2011) on differentially private statistical estimation shows how to construct differentially private approximations to estimators which have asymptotic normality guarantees under fairly mild conditions. In practical situations, however, we must take into account the effect of a finite number of samples. Moreover, it has been empirically observed (e.g., Chaudhuri et al., 2011;Vu & Slavkovic, 2009) that there is often a significant gap in statistical efficiency between a differentially private estimator and its nonprivate counterpart. Thus there is a need to study finite sample convergence rates for differentially private statistical estimators, in order to characterize the properties that make a statistical estimator amenable to differentially-private approximations.
In this paper, we provide upper and lower bounds on the finite sample convergence rates of such estimators. Our first finite sample result draws a connection between differentially private statistical estimators and Gross Error Sensitivity, a measure commonly used in the robust statistics literature (Huber, 1981). The Gross Error Sensitivity (GES) of a statistical functional T at a distribution F is the maximum change in the value of T (F ) by an arbitrarily small perturbation of F by any point mass x in the domain. We provide a lower bound on the convergence rate of any differentially private statistical estimator, showing that an estimator that approximates T (F n ) well with differential privacy over a large class of distributions must have its convergence rate grow with the GES of T .
A natural question to ask next is whether bounded GES is sufficient for the existence of differentially private estimators that are accurate for large classes of distributions. We next show that at least for αdifferential privacy, this is not the case. Any estimator based on a functional T that takes values in a range of length R and guarantees α-differential privacy for a wide class of distributions, has to have a finite sample convergence rate that grows with increasing R.
We then show that bounded range and GES are indeed sufficient for differentially private estimation. In particular, given an estimator based on a functional T which takes values in a bounded range, and has bounded GES for all distributions close to the underlying data distribution F , we show how to compute a differentially private approximation to T (F ) based on sensitive data drawn from F . Our approximation preserves (α, δ)-differential privacy, a relaxation of αdifferential privacy, and is based on the smoothed sensitivity method (Nissim et al., 2007). We provide a finite sample upper bound on the convergence rate of this estimator.
The statistical estimators in our upper bounds are computationally inefficient in general. We conclude by providing a separate explicit method for privately approximating M-estimators with certain properties. We prove that these differentially-private estimators enjoy similar privacy and statistical guarantees as those based on the smooth-sensitivity method, while being more efficiently computable.

Related Work
Differential privacy was proposed by (Dwork et al., 2006b), and has been used since in many works on pri-vacy (e.g., Blum et al., 2005;Barak et al., 2007;Nissim et al., 2007;McSherry & Mironov, 2009;Chaudhuri et al., 2011). It has been shown to have strong semantic guarantees (Dwork et al., 2006b) and is resistant to many attacks (Ganta et al., 2008) that succeed against some other definitions of privacy. Dwork & Lei (2009) is the first work to identify a connection between differential privacy and robust statistics; based on robust statistical estimators as a starting point, they provide differentially private algorithms for several common estimation tasks, including interquartile range, trimmed mean and median, and regression.
In further work, Smith (2011) shows how to construct a differentially private approximation A T to certain types of statistical estimators T , and establishes asymptotic normality of his estimator provided certain conditions on T hold. We in contrast focus on finite sample bounds, with an aim towards characterizing the statistical properties of estimators that determine how closely they can be approximated with differential privacy. Lei (2011) considers M-estimation, and provides a simple and elegant differentially-private Mestimator which is statistically consistent.
Finally, work on the sample requirement of differentially private algorithms include bounds on the accuracy of differentially private data release (Hardt & Talwar, 2010), and the sample complexity of differentially private classification (Chaudhuri & Hsu, 2011).

Preliminaries
The goal of this paper is to examine the conditions under which we can find private approximations to estimators. The notion of privacy we use is differential privacy (Dwork et al., 2006b;a). Definition 1. A (randomized) algorithm A taking values in a range S is (α, δ)-differentially private if for all S ⊆ S, and all data sets D and D differing in a single entry, where Pr A [·] is the distribution on S induced by the output of A given a data set.
A general approach to developing differentially private approximations to functions is to add noise, either to the sensitive data, or to the output of a non-private function computed on the data. This work explores what properties statistical functionals need to have so that they can be accurately approximated with differential privacy.
Let F denote the space of probability distributions on a domain X . A statistical functional T : F → R is a real-valued function of a distribution F . The plug-in estimator of θ = T (F ) is given by θ n := T (F n ), where F n is the empirical distribution corresponding to an i.i.d. sample of size n drawn from F . A common measure of the robustness of a statistical functional is the influence function, which measures how a functional T (F ) responds to small changes to the input F .
where δ x denotes the point mass distribution at x.

It is a well-established result in theoretical statis
A related notion is that of gross error sensitivity, which measures the worst-case value of the influence function for any x ∈ X .
Definition 3. The gross error sensitivity GES(T, F ) for a functional T and distribution F is: We also define the notions of influence function and gross error sensitivity at a fixed scale ρ > 0: In this work, the data domain X will be a subset of R. We overload notation and use F to denote a distribution as well as its cumulative distribution function. For two distributions F and G, we use d GC (F, G) := sup x∈R |F (x) − G(x)| to denote the Glivenko-Cantelli distance between F and G. For a distribution F from a family F and a radius r > 0, let B GC (F, r) denote the set of distributions G ∈ F such that d GC (F, G) ≤ r. Finally,we use d TV (F, G) to denote the total variantion distance between F and G.
A statistical functional T is B-robust at F if GES(T, F ) is finite. B-robustness has been studied in the robust statistics literature (Hampel et al., 1986;Huber, 1981), and plug-in estimators for B-robust functionals are considered to be resistant to outliers and changes in the input.

Lower Bounds
We begin by establishing lower bounds on the convergence rate of any differentially private approximation to a statistical functional T (F ).

Lower Bounds based on Gross Error Sensitivity
We first show a lower bound on the error of any (α, δ)differentially private approximation to T in terms of the gross error sensitivity of T at a distribution F . Theorem 1. Pick any α ∈ (0, ln 2 2 ) and δ ∈ (0, α 23 ). Let F be the family of all distributions over X , and let A be any (α, δ)-differentially private algorithm. For all n ∈ N and all F ∈ F, there exists a radius ρ = ρ(n) = 1 n · ln 2 2α and a distribution G ∈ F with d TV (F, G) ≤ ρ, such that either Several remarks are in order. First of all, the form of Theorem 1 is slightly unconventional in the sense that applies not to particular distributions, but to a set of distributions. In particular, the bound states that either the convergence rate of F is high, or the convergence rate of some G close to F is high. Observe that for a fixed distribution F , it is trivial to construct a differentially private approximation to T (F ) that is accurate for F -ignore any sensitive input data, and simply output T (F ). This algorithm provides a perfectly accurate estimate when the input is drawn from F , but performs poorly otherwise; thus any lower bound that applies to all differentially private algorithms will have a similar form. On the other hand, the differentially private estimators in Theorem 1 have few restrictions: they are only expected to be accurate for distributions lying in a small neighborhood of F , and may be extremely inaccurate in general.
Second, for fixed n, ρ is a function ρ(n) = 1 n · ln 2 2α , which decreases to zero as n → ∞; provided GES ρ (T, F ) remains the same as ρ diminishes, the lower bound grows weaker with increasing n. The lower bound thus does not rule out the existence of consistent private estimators.
Finally, we observe from the proof of Theorem 1 that F need not be the family of all distributions over X ; the theorem will still apply if for every F ∈ F, and for all x ∈ X , (1 − ρ)F + ρδ x also lies in the family F; for example if F is the set of all discrete distributions over X .
While Theorem 1 is very general, we present below an example that illustrates an implication of the theorem.
Example 1. Let X = [0, a], and let F be the set of all discrete distributions over X . Let T (F ) be the mean of F .
Cosnider a fixed F ∈ F, and a fixed n. Let ρ = ρ(n) as in Theorem 1. For any F , GES ρ (T, F ) ≥ a 2 . It can be shown that for any G ∈ B TV (F, ρ(n)), Var [G] ≤ Var [F ] + ρ(1 − ρ)a 2 . Thus, the expected errors of the (non-private) plug-in estimators are bounded as . On the other hand, Theorem 1 shows that for every differentially private estimator A, at is Ω(ρa); this quantity is higher than the corresponding quantity for the non-private estimator so long as Proof of Theorem 1. Let x * be the x ∈ X that maximizes |IF ρ (x, T, F )|. Let γ > 0, and let ρ := 1 n ln 2 2α , and let G := (1 − ρ)F + ρδ x * . Observe that d TV (F, G) ≤ ρ and IF ρ (x * , T, F ) = (T (G) − T (F ))/ρ. Consider the following procedure for drawing n samples from G. First, draw a random sample F n of size n from F (we overload the notation F n to refer to both a random sample and its empirical distribution). Next, for each i = 1, 2, . . . , n, independently toss a biased coin with heads probability ρ; if the coin turns up heads, replace the i-th element of F n by x * ; otherwise, do nothing. This procedure constructs a random sample G n of size n from G, and in the process constructs a coupling between samples of size n from F and G.
In what follows, we will use this coupling to calculate the quantity Let F n be any randomly drawn sample of size n from F , and let G n be a corresponding sample from G as drawn from the coupling procedure. Call a pair (F n , G n ) ρ-close if they differ in at most ρn entries. As the median of Binomial(n, ρ) is ≤ ρn = ρn, the probability that at most ρn of the elements of F n are converted to x * by the coupling process is at least 1/2.

Lower Bounds as a Function of Range
Is the bound in Theorem 1 tight? In other words, if T has bounded GES, can we compute accurate differentially private approximations to T (F ) for all distributions F over a domain? We next show that at least for (α, 0)-differential privacy, Theorem 1 is not tight; if we wish to compute differentially private and accurate estimates of T (F ) for all distributons F in a family, where T (F ) can take any value in a range [λ, λ ], then the sample size must grow as a function of λ − λ.
Theorem 2. Let F be a family of distributions over X , and let A be any (α, 0)-differentially private algorithm. Suppose for all τ ∈ [λ, λ ], there exists some F τ ∈ F such that T (F τ ) = τ . Then there exists some F ∈ F such that Example 2. For any γ ∈ R, let U γ be the uniform distribution on [γ − 1, γ + 1], and let F be the family Let T (F ) be the median of F . For every F ∈ F, the non-private estimator T (F n ) converges to T (F ) at a rate proportional to O( 1 √ n ), independent of R. However, Theorem 2 shows that for every differentially private estimator A, there is some F ∈ F such that |A(F n ) − T (F )| grows with R.
Proof of Theorem 2. Let r := λ −λ 2+e αn and Γ := λ −λ r . For each i = 1, 2, . . . , Γ, let F i be a distribution in F such that T (F i ) = λ + (i − 1 2 )r; such distributions are guaranteed to exist by assumption. Also, for each i = 1, 2, . . . , Γ, let F i n be an iid sample of size n from F i , and define the half-open interval I i := [λ + (i − 1)r, λ + ir). Observe that the intervals I i are disjoint. To prove the theorem, let us assume the contrary: This, along with a Markov's inequality on |A( where the first step follows by assumption, the second step follows because the intervals {I j } are disjoint, and the third step from Lemma 2 and the fact that for any i and j, any F i n and F j n differ in at most n entries. Rearranging, the inequality becomes Γ ≤ 1 + e αn , which is a contradiction since Γ = (λ − λ)/r > 1 + e αn . Therefore (2) cannot hold, so the theorem follows.

Upper Bounds
In this section, we show that bounded GES and bounded range are sufficient conditions for the existence of an (α, δ)-differentially private approximation to T . Our approximation uses the smooth-sensitivity method of Nissim et al. (2007), for which we provide a new statistical analysis in Section 4.1 (Theorem 3). We also provide a specific analysis for the case of linear functionals in Appendix B.
Let d H (D, D ) denote the Hamming distance between D and D (the number of entries in which D and D differ), and recall the following definitions from Nissim et al. (2007). Throughout, we assume D ∈ R n is an i.i.d. sample of size n drawn from a fixed distribution F , and F n is the empirical CDF corresponding to this sample. For a statistical functional T , we use the overloaded notation SS β (T, F n ) to denote the β-smooth sensitivity of T (F n ) at the data set F n = D.

Estimator Based on Smooth Sensitivity
For a statistical functional T , let A T be the randomized estimator given by where β(α, δ) := α 2 ln(1/δ) and Z is an independent random variable drawn from the standard Laplace density p Z (z) = 0.5e −|z| . A T essentially computes T (F n ) and adds zero-mean noise, with the scale determined by the privacy parameters and the smooth sensitivity. Computing SS β(α,δ) (T, F n ) in general can be computationally challenging -see Nissim et al. (2007); our result thus demonstrates an upper bound.
The following guarantee is due to Nissim et al. (2007).
To give a statistical guarantee for A T , we begin with a standard tail bound based on the simple fact that Proposition 2. For any t > 0, It follows that the convergence rate of A T depends on the β-smooth sensitivity of T at F n , which can be bounded under the following conditions on T .
Condition 1 (Bounded range). There exists a finite R > 0 such that the range of T is contained in an interval of length R.
Even for non-private estimation, the robustness of an estimator depends not just on the influence functions at the target distribution F , but also on these quantities in a local neighborhood around F (Huber, 1981, p. 72). For convenience, Condition 2 is stated in terms of Glivenko-Cantelli distance, but can be easily changed to any distance under which F n converges to F as n → ∞ with suitable modifications in the analysis.
We now state our main statistical guarantee for A T . Theorem 3. Assume Condition 1 and Condition 2 hold. Pick any η ∈ (0, 1/4). With probability ≥ 1 − 2η, the estimator A T from (3) satisfies where R is the quantity in Condition 1, and Γ n is the quantity in Condition 2.
Proof. Follows from Proposition 2, Lemma 1, a union bound, and the triangle inequality.
The first term in the bound, |T (F n ) − T (F )|, is the error of the non-private plug-in estimate T (F n ). If T is Hadamard-differentiable, then T (F n ) − T (F ) converges in distribution to a zero-mean normal random variable with variance n −1 IF(x, T, F ) 2 dF (x); in this case, T (F n ) converges to T (F ) at an asymptotic n −1/2 rate (Wasserman, 2006). Non-asymptotic rates can also be established in terms of other specific properties of T and F (see Appendix B for an example).
The second term in the bound from Theorem 3 is roughly the larger of can be compared to the lower bounds from Section 3. The lower bound from Theorem 1 is close to A 1 as long as GES ρ (T, F ) ≈ Γ n for ρ = ln 2 2αn . This hold for sufficiently large n when lim n→∞ Γ n = GES(T, F ). The lower bound from Theorem 2 decreases as R·exp(−Ω(αn)), which is a little better than A 2 , but is otherwise qualitatively similar in terms of its dependence on the range R 2 . Example 3. If T (F ) is the median of F , and F := {U γ : γ ∈ [−R, R]} is the family of uniform distributions on unit length intervals [γ − 1, γ + 1] from Example 2, then Γ n = 1/2, and the bound in Theorem 3 reduces to n/ ln(1/δ)) .
2 Appendix E shows how this discrepancy can be reduced with a stronger condition.

Bounding the Smooth Sensitivity
The proof of Theorem 3 (see Appendix C) is based on the following lemma, which establishes a highprobability bound on SS β (T, F n ) under Conditions 1 and 2.
Lemma 1. Assume Condition 1 and Condition 2 hold. With probability ≥ 1 − η, where R is the quantity in Condition 1, and Γ n is the quantity in Condition 2.

Differentially-Private M -Estimation
We now provide a procedure for constructing differentially private approximations to M -estimators that satisfy certain conditions. Unlike our estimators in Section 4.1, these estimators are computationally efficient; however they only apply to a more restricted class of estimators.

M -Estimators
An M -estimator T ψ (F n ) is given as the solution θ n ∈ R to the equation ψ(x, θ n )dF n (x) = 0 for some function ψ : R × R → R. For a CDF G and θ ∈ R, define Ψ(G, θ) := ψ(x, θ)dG(x) so Ψ(F n , T ψ (F n )) = 0. The derivative of Ψ with respect to its second argument, which is assumed to exist, is denoted by Ψ . Throughout, we will assume ψ satisfies the following condition.
Condition 3 (Bounded ψ-range and monotonicity). There exists a finite K > 0 such that the range of ψ is contained in [−K, K], and ψ is non-decreasing in its second argument.
Under this condition, the gross error sensitivity of T ψ at F can be bounded as Previous works (Chaudhuri et al., 2011) and (Rubinstein et al., 2009) have provided differentially private and computationally efficient algorithms for Mestimation under assumptions that are very similar to Condition 3. The algorithm in Rubinstein et al. (2009), and one of the algorithms in Chaudhuri et al. (2011) are based on the sensitivity method, while the main algorithm in Chaudhuri et al. (2011) is based on an objective perturbation method. While both algorithms are computationally efficient, both require explicit regularization. This is problematic in practice because determining the regularization parameter privately through differentially-private parameter-tuning requires extra data -for a more detailed discussion of this issue, see Chaudhuri et al. (2011). In contrast, our algorithm is based on the Exponential Mechanism, and does not have an explicit regularization parameter; instead we assume that Ψ is smooth, and our guarantees depend on the value of the derivative Ψ (F, T ψ (F )).

Exponential Mechanism for M -Estimation
Fix a density µ on R, and let A ψ,µ be the randomized estimator whose output has probability density This estimator is derived from the exponential mechanism of McSherry & Talwar (2007), where the "cost" function is taken to be |Ψ(F n , ·)|/K. In many Mestimators of interest, particularly those involving data lying in a bounded range, a prior knowledge of K is reasonable.
If it is known that T ψ (F ) is contained in some interval, then one can take the prior density µ to be uniform over this interval. If no such prior knowledge is available, then µ can be taken to be a density with full support on R such as the standard Cauchy density.
The privacy guarantee for A ψ,µ follows easily from known properties of the exponential mechanism (Mc-Sherry & Talwar, 2007).
The accuracy guarantee for A ψ,µ relies on the following smoothness condition on Ψ at F .
With probability at least 1 − 3η, the estimator A ψ,µ satisfies The proof of Theorem 4 is in Appendix D. The condition in (5) required by Theorem 4 essentially states that the sample size n should be large enough for F n and T ψ (F n ) to be in the neighborhoods of F and T ψ (F ), respectively, where Ψ is locally Lipschitzsmooth.
It is straightforward to generalize the results to other prior densities µ. Observe that in the case the range of T ψ is [−R, R] for some unknown R, using the standard Cauchy density as µ yields a similar dependence on R (via log |T ψ (F )| ≤ log R) as what is obtained when µ is uniform over [−R, R]. The more probability mass µ assigns around T ψ (F ), the better the bounds are.
Also note that the main scaling factor of Γ = K/|Ψ (F, T ψ (F ))| in the sample size bound is precisely the bound on GES(T ψ , F ) from (4). A dependence on GES(T ψ , F ) is to be expected as per Theorem 1.

Conclusions
The finite sample analysis reveals a concrete connection between differential privacy and robust statistics, The main results shown here suggest using Brobustness as a criterion for designing differentiallyprivate statistical estimators, and also highlight the obstacles that even robust estimators face when the parameter space is very large or unbounded.
While our lower bounds may seem pessimistic, they apply to estimators that succeed for a wide class of distributions. One way of avoiding our lower bounds would be by using priors that allow an estimator to perform well on some input distributions but not-sowell on others; a future research direction is to investigate how this can help design better differentially private estimators.