Files in this item
Files  Description  Format 

application/pdf Quan_Geng.pdf (3MB)  (no description provided) 
Description
Title:  The optimal mechanism in differential privacy 
Author(s):  Geng, Quan 
Director of Research:  Viswanath, Pramod 
Doctoral Committee Chair(s):  Viswanath, Pramod 
Doctoral Committee Member(s):  Hajek, Bruce; Srikant, Rayadurgam; Vaidya, Nitin H. 
Department / Program:  Electrical & Computer Eng 
Discipline:  Electrical & Computer Engr 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(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 tradeoff between privacy and utility in differential privacy in the most basic problem settings. We first derive the optimal (epsilon)differentially private mechanism for single realvalued query function under a very general utilitymaximization (or costminimization) framework. The class of noise probability distributions in the optimal mechanism has staircaseshaped 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 staircaseshaped probability density function. We explicitly derive the parameter of the optimal twodimensional 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 integervalued query functions under a utilitymaximization/costminimization 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 nearoptimality of uniform noise mechanism and discrete Laplacian mechanism in the high privacy regime (as (epsilon, delta) to (0,0)). 
Issue Date:  20140116 
URI:  http://hdl.handle.net/2142/46705 
Rights Information:  Copyright 2013 Quan Geng 
Date Available in IDEALS:  20140116 
Date Deposited:  201312 
This item appears in the following Collection(s)

Dissertations and Theses  Electrical and Computer Engineering
Dissertations and Theses in Electrical and Computer Engineering 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois