The optimal mechanism in differential privacy

Geng, Quan

Permalink

https://hdl.handle.net/2142/46705 Copy

Description

Title

The optimal mechanism in differential privacy

Author(s)

Geng, Quan

Issue Date

2014-01-16T17:59:44Z

Director of Research (if dissertation) or Advisor (if thesis)

Viswanath, Pramod

Doctoral Committee Chair(s)

Viswanath, Pramod

Committee Member(s)

• Hajek, Bruce
• Srikant, Rayadurgam
• Vaidya, Nitin H.

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Differential Privacy
• Laplacian Mechanism
• Staircase Mechanism
• Privacy and Utility

Abstract

Differential privacy is a framework to quantify to what extent individual privacy in a statistical database is preserved while releasing useful aggregate information about the database. This dissertation studies the fundamental trade-off between privacy and utility in differential privacy in the most basic problem settings. We first derive the optimal (epsilon)-differentially private mechanism for single real-valued query function under a very general utility-maximization (or cost-minimization) framework. The class of noise probability distributions in the optimal mechanism has staircase-shaped probability density functions which are symmetric (around the origin), monotonically decreasing and geometrically decaying. The staircase mechanism can be viewed as a geometric mixture of uniform probability distributions, providing a simple algorithmic description for the mechanism. Furthermore, the staircase mechanism naturally generalizes to discrete query output settings as well as more abstract settings. We explicitly derive the parameter of the optimal staircase mechanism for ell_1 and ell_2 cost functions. Comparing the optimal performances with those of the usual Laplacian mechanism, we show that in the high privacy regime (epsilon is small), the Laplacian mechanism is asymptotically optimal as epsilon to 0; in the low privacy regime (epsilon is large), the minimum magnitude and second moment of noise are Theta(Delta e^{-epsilon/2) and Theta(Delta^2 e^{-{2\epsilon}/{3}) as epsilon to +infinity, respectively, while the corresponding figures when using the Laplacian mechanism are {Delta}/{epsilon} and {2\Delta^2}/{\epsilon^2}, where Delta is the sensitivity of the query function. We conclude that the gains of the staircase mechanism are more pronounced in the low privacy regime. We also show the optimality of the staircase mechanism for epsilon- differentially privacy in the multiple dimensional setting where the query output has multiple components, e.g., histogram query function. We prove that when the dimension is two, for the ell^1 cost function, the noise probability distribution in the optimal mechanism has a multiple dimensional staircase-shaped probability density function. We explicitly derive the parameter of the optimal two-dimensional staircase mechanism, and study the asymptotical performance of optimal mechanism in the high and low privacy regimes. Comparing the optimal performances with those of the usual Laplacian mechanism, we show that in the high privacy regime (epsilon is small), the Laplacian mechanism is asymptotically optimal as epsilon to 0; in the low privacy regime (epsilon is large), the optimal cost is Theta(e^{-{epsilon}/{3}), while the cost of the Laplacian mechanism is {2\Delta}/{\epsilon}. We conclude that the gains of the staircase mechanism are more pronounced in the low privacy regime. Lastly, we study the optimal mechanisms in (epsilon, delta)-differential privacy for integer-valued query functions under a utility-maximization/cost-minimization framework. We show that the (epsilon, delta)-differential privacy is a framework not much more general than the (epsilon, 0)-differential privacy and (0, \delta)-differential privacy in the context of ell^1 and ell^2 cost functions, i.e., minimum expected noise magnitude and noise power. In the same context of ell^1 and ell^2 cost functions, we show the near-optimality of uniform noise mechanism and discrete Laplacian mechanism in the high privacy regime (as (epsilon, delta) to (0,0)).

Graduation Semester

2013-12

Permalink

http://hdl.handle.net/2142/46705

Copyright and License Information

Copyright 2013 Quan Geng

Owning Collections