On the geometry of differential privacy

By Moritz Hardt, Kunal Talwar. 2009

486 citations recorded by the source corpus.

We consider the noise complexity of differentially private mechanisms in the setting where the user asks d linear queries f:Rn -> R non-adaptively. Here, the database is represented by a vector in R and proximity between databases is measured in the l1-metric. We show that the noise complexity is determined by two geometric parameters associated with the set of queries. We use this connection to give tight upper and lower bounds on the noise complexity for any d ≤ n. We show that for d random linear queries of sensitivity 1, it is necessary and sufficient to add l2-error Θ(min d√d/ε,d√(log (n/d))/ε) to achieve ε-differential privacy. Assuming the truth of a deep conjecture from convex geometry, known as the Hyperplane conjecture, we can extend our results to arbitrary linear queries giving nearly matching upper and lower bounds. Our bound translates to error $O(min d/ε,√(d log(n/d)/ε)) per answer. The best previous upper bound (Laplacian mechanism) gives a bound of O(min (d/ε,√n/ε)) per answer, while the best known lower bound was Ω(√d/ε). In contrast, our lower bound is strong enough to separate the concept of differential privacy from the notion of approximate differential privacy where an upper bound of O(√{d}/ε) can be achieved.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Privacy & Security

Citations in the corpus

Protection Against Reconstruction and Its Applications in Private Federated Learning (2018, methodology): “Moreover, a simple modification of the techniques of Hardt and Talwar [39] shows that for W ∼ Uni(Sd−1), any ε-differentially private quantity Z for W satisfies E[‖Z −W‖2] & 1 whenever ε ≤ d − log 2.”
The structure of optimal private tests for simple hypotheses (2018, background): “There are also several rich lines of work attempting to give tight instance-specific characterizations of the sample complexities of various differentially private computations, most notably linear query release [11, 43, 48, 57, 58] and PAC and agnostic learning [10, 39, 46].”
An Economic Analysis of Privacy Protection and Statistical Accuracy as Social Choices (2018, background): “For mechanisms involving multiple linear queries, Hardt and Talwar (2010) established upper and lower bounds on the variance of the noise added to achieve privacy.”
Tight Lower Bounds for Differentially Private Selection (2017, methodology): “(ε, δ)differential privacy with δ = 0) lower bounds can be proved using the “packing” technique [38], [39], [40].”
Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, methodology): “The reduction to lower-bounds for 1-way marginals is not quite black-box; we exploit specific properties of the instances used by Hardt and Talwar [25], Bun et al. [8].”
Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning (2009, background): “Barak et al. (2007) presented a mechanism for releasing contingency tables that guarantees di erential privacy and also guarantees a notion of accuracy: with high probability all marginals from the released table are close in L1-norm to the true table's marginals.”
Minimax Optimal Procedures for Locally Private Estimation (2016, background): “…requires a formal definition of privacy, and differential privacy has been put forth as one such candidate (see, e.g., the articles Dwork et al. 2006; Blum, Ligett, and Roth 2008; Dwork, Rothblum, and Vadhan 2010; Hardt and Rothblum 2010; Hardt and Talwar 2010, and references therein).”
Robust Traceability from Trace Amounts (2015, background): “What if we are more demanding, and ask that an attacker not be able to determine whether an individual is present or absent from the dataset, that is, to trace? This in/out protection is the essence of differential privacy, and the question of how much noise is needed to ensure differential privacy,”
Universally utility-maximizing privacy mechanisms (2008, methodology): “The use of abstract “utility functions” in McSherry and Talwar [16] has a similar ﬂavor to our use of loss functions, though the motivations and goals of their work and ours are unrelated.”
Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation (2013, methodology): “…all possible channels Q ∈ Q α , we obtain the central object of interest for this paper, the α -private minimax rate for the family θ ( ), deﬁned as b A standard route for lower bounding the minimax risk (3a) is by reducing the estimation problem to the testing problem of identifying a point θ ∈…”
The geometry of differential privacy: the sparse and approximate cases (2012, methodology): “The optimal error achievable by any ( ε, δ )-diﬀerentially private algorithm for queries A and databases of size up to n is where the inﬁmum is taken over all ( ε, δ )-diﬀerentially private algorithms.”
Fingerprinting codes and the price of approximate differential privacy (2013, methodology): “[1] Barak, B., Chaudhuri, K., Dwork, C., Kale, S., McSherry, F., and Talwar, K. Privacy, accuracy, and consistency too: a holistic solution to contingency table release.”