{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/46705"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/46705","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"The optimal mechanism in differential privacy","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)).","abstract_html":"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)).","abstract_has_math":false,"creators":["Geng, Quan"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Viswanath, Pramod","Hajek, Bruce","Srikant, Rayadurgam","Vaidya, Nitin H."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-01-16T17:59:44Z","date_published":"2014-01-16T17:59:44Z","updated_at":"2026-07-22T22:25:36Z","subjects":["Differential Privacy","Laplacian Mechanism","Staircase Mechanism","Privacy and Utility"],"languages":["en"],"rights":["Copyright 2013 Quan Geng"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/46705","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Viswanath, Pramod","Hajek, Bruce","Srikant, Rayadurgam","Vaidya, Nitin H."]},{"key":"dc:creator","label":"Author","values":["Geng, Quan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-01-16T17:59:44Z","2013-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Differential Privacy","Laplacian Mechanism","Staircase Mechanism","Privacy and Utility"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2013 Quan Geng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/46705"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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)).","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2013-11-26T21:15:05Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 Quan_phd_thesis_final.zip: 14509554 bytes, checksum: 0aa0cb59565b6f97d9fc19ae8186ad4e (MD5) Geng_Quan.pdf: 3056954 bytes, checksum: 177fdc8d3d990d30468753ea9ed6a69b (MD5)","Made available in DSpace on 2014-01-16T17:59:44Z (GMT). No. of bitstreams: 3 Quan_Geng.pdf: 3056954 bytes, checksum: 177fdc8d3d990d30468753ea9ed6a69b (MD5) Quan_phd_thesis_final.zip: 14509554 bytes, checksum: 0aa0cb59565b6f97d9fc19ae8186ad4e (MD5) license.txt: 4056 bytes, checksum: 964cd1e0c2dedab1e8aa422ed4f1eb25 (MD5)"]},{"key":"dc:title","label":"Title","values":["The optimal mechanism in differential privacy"]}]}],"canonical_facts":{"dc:contributor":["Viswanath, Pramod","Hajek, Bruce","Srikant, Rayadurgam","Vaidya, Nitin H."],"dc:creator":["Geng, Quan"],"dc:date":["2014-01-16T17:59:44Z","2013-12"],"dc:description":["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)).","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2013-11-26T21:15:05Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 Quan_phd_thesis_final.zip: 14509554 bytes, checksum: 0aa0cb59565b6f97d9fc19ae8186ad4e (MD5) Geng_Quan.pdf: 3056954 bytes, checksum: 177fdc8d3d990d30468753ea9ed6a69b (MD5)","Made available in DSpace on 2014-01-16T17:59:44Z (GMT). No. of bitstreams: 3 Quan_Geng.pdf: 3056954 bytes, checksum: 177fdc8d3d990d30468753ea9ed6a69b (MD5) Quan_phd_thesis_final.zip: 14509554 bytes, checksum: 0aa0cb59565b6f97d9fc19ae8186ad4e (MD5) license.txt: 4056 bytes, checksum: 964cd1e0c2dedab1e8aa422ed4f1eb25 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/46705"],"dc:language":["en"],"dc:rights":["Copyright 2013 Quan Geng"],"dc:subject":["Differential Privacy","Laplacian Mechanism","Staircase Mechanism","Privacy and Utility"],"dc:title":["The optimal mechanism in differential privacy"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:36Z"}