How to Use Heuristics for Differential Privacy
How to Use Heuristics for Differential Privacy
复制标题
DOI：
10.1109/focs.2019.00014
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
Seth Neel;Aaron Roth;Zhiwei Steven Wu
中科院分区：
文献类型：
--
作者：
Seth Neel;Aaron Roth;Zhiwei Steven Wu
我们开发理论，使用算法来解决计算困难的问题，在不同的隐私。启发式方法在机器学习中取得了巨大的成功，其性能可以根据经验进行评估。然而，隐私保障不能凭经验进行评估，必须在不做启发性假设的情况下加以证明。我们表明，学习问题的广泛类的功能---那些具有多项式大小的通用标识集---可以私下和有效地解决，假设存在一个非私人的神谕解决同样的问题。我们的第一个算法产生了一个隐私保证，这是偶然的预言的正确性。然后，我们给出了一个减少，适用于一类我们称之为可认证的隐私保护，这使我们能够转换甲骨文依赖的隐私保证，最坏情况下的隐私保证，即使启发式站在甲骨文可能会失败的对抗方式。最后，我们考虑的功能，他们和他们的对偶类有小的通用标识集类。这包括PAC学习文献中研究的大多数简单布尔函数类，包括合取、析取、奇偶和离散半空间。我们表明，有一个有效的算法，私人构建合成数据的任何这样的类，给定一个非私人的学习预言。这特别给出了第一个用于私下生成列联表合成数据的高效算法。我们的工作留下的最有趣的问题是，是否每一个可以私下差分解决的问题都可以用一个高效的算法私下解决。虽然我们没有解决这个问题，我们给出了一个障碍的结果，表明任何通用的甲骨文有效的减少必须落在一个自然类的算法（其中包括本文给出的算法）。
We develop theory for using heuristics to solve computationally hard problems in differential privacy. Heuristic approaches have enjoyed tremendous success in machine learning, for which performance can be empirically evaluated. However, privacy guarantees cannot be evaluated empirically, and must be proven --- without making heuristic assumptions. We show that learning problems over broad classes of functions --- those that have polynomially sized universal identification sets --- can be solved privately and efficiently, assuming the existence of a non-private oracle for solving the same problem. Our first algorithm yields a privacy guarantee that is contingent on the correctness of the oracle. We then give a reduction which applies to a class of heuristics which we call certifiable, which allows us to convert oracle-dependent privacy guarantees to worst-case privacy guarantee that hold even when the heuristic standing in for the oracle might fail in adversarial ways. Finally, we consider classes of functions for which both they and their dual classes have small universal identification sets. This includes most classes of simple boolean functions studied in the PAC learning literature, including conjunctions, disjunctions, parities, and discrete halfspaces. We show that there is an efficient algorithm for privately constructing synthetic data for any such class, given a non-private learning oracle. This in particular gives the first oracle-efficient algorithm for privately generating synthetic data for contingency tables. The most intriguing question left open by our work is whether or not every problem that can be solved differentially privately can be privately solved with an oracle-efficient algorithm. While we do not resolve this, we give a barrier result that suggests that any generic oracle-efficient reduction must fall outside of a natural class of algorithms (which includes the algorithms given in this paper).