On the Optimality of the Exponential Mechanism
On the Optimality of the Exponential Mechanism
复制标题
论指数机制的最优性
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
H. Simon
中科院分区：
文献类型：
--
作者：
Francesco Aldà;H. Simon
在这项工作中，我们调查的差异隐私，即指数机制中使用的最著名的工具之一。我们首先研究的平均情况下，当输入/输出宇宙的机制可以建模为一个图，其中每个节点与一个数据库相关联的指数机制引入的错误的最优性。通过利用线性规划理论，我们提供了一些正则性条件下的图结构的指数机制最小化的平均误差。此外，我们给出了一个玩具的例子，其中的最优性被保存（一个常数因子），即使这些正则性条件只在一定程度上。最后，我们证明了指数机制的最坏情况下的最优性时，它被用来释放的排序功能的输出。
In this work, we investigate one of the most renowned tools used in differential privacy, namely the exponential mechanism. We first study the optimality of the error introduced by the exponential mechanism in the average-case scenario, when the input/output universe of the mechanism can be modeled as a graph where each node is associated with a database. By leveraging linear programming theory, we provide some regularity conditions on the graph structure under which the exponential mechanism minimizes the average error. Moreover, we give a toy example in which the optimality is preserved (up to a constant factor) even if these regularity conditions hold only to a certain extent. Finally, we prove the worst-case optimality of the exponential mechanism when it is used to release the output of a sorting function.