The power of factorization mechanisms in local and central differential privacy
The power of factorization mechanisms in local and central differential privacy
复制标题
DOI：
10.1145/3357713.3384297
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Alex Edmonds;Aleksandar Nikolov;Jonathan Ullman
中科院分区：
文献类型：
--
作者：
Alex Edmonds;Aleksandar Nikolov;Jonathan Ullman
我们给出了差分隐私的局部模型和中心模型下回答线性查询(统计查询)的样本复杂性的新刻画：(1)在非交互局部模型中，我们给出了样本复杂性的第一近似刻画。非正式地，我们的界限紧到查询数量和期望的准确率的多对数因子之内。我们的描述扩展到了局部模型中的不可知性学习。(2)在中心模型中，我们给出了高精度区域内样本复杂性的特征，这类似于Nikolov，Talwar和Zhang(STOC 2013)的特征，但在数量上更紧密，并且有一个非常简单的证明。我们的下界同样适用于经验问题和人口估计问题。在这两种情况下，我们的刻画表明特定的分解机制是近似最优的，并且最优样本复杂度是由与查询相关的矩阵的充分研究的因式分解范数上下有界的。
We give new characterizations of the sample complexity of answering linear queries (statistical queries) in the local and central models of differential privacy: (1) In the non-interactive local model, we give the first approximate characterization of the sample complexity. Informally our bounds are tight to within polylogarithmic factors in the number of queries and desired accuracy. Our characterization extends to agnostic learning in the local model. (2) In the central model, we give a characterization of the sample complexity in the high-accuracy regime that is analogous to that of Nikolov, Talwar, and Zhang (STOC 2013), but is both quantitatively tighter and has a dramatically simpler proof. Our lower bounds apply equally to the empirical and population estimation problems. In both cases, our characterizations show that a particular factorization mechanism is approximately optimal, and the optimal sample complexity is bounded from above and below by well studied factorization norms of a matrix associated with the queries.