Composition theorems are general and powerful tools that facilitate privacy accounting across multiple data accesses from per-access privacy bounds. However they often result in weaker bounds compared with end-to-end analysis. Two popular tools that mitigate that are the exponential mechanism (or report noisy max) and the sparse vector technique. They were generalized in a couple of recent private selection/test frameworks, including the work by Liu and Talwar (STOC 2019), and Papernot and Steinke (ICLR 2022). In this work, we first present an alternative framework for private selection and testing with a simpler privacy proof and equally-good utility guarantee. Second, we observe that the private selection framework (both previous ones and ours) can be applied to improve the accuracy/confidence trade-off for many fundamental privacy-preserving data-analysis tasks, including query releasing, top-$k$ selection, and stable selection. Finally, for online settings, we apply the private testing to design a mechanism for adaptive query releasing, which improves the sample complexity dependence on the confidence parameter for the celebrated private multiplicative weights algorithm of Hardt and Rothblum (FOCS 2010).
翻译:其构成是一般和强大的工具,便于从每个访问隐私圈的多个数据存取中进行隐私核算,但往往导致与端对端分析相比限制较弱。两种受欢迎的工具,即指数机制(或报告噪声最大)和稀疏矢量技术。它们在最近的几个私人选择/测试框架中被普遍采用,包括刘和塔尔瓦尔(STOC 2019)和Papernot和Steinke(ICLR 2022)的工作。在这项工作中,我们首先提出了一个私人选择和测试的替代框架,采用较简单的隐私证明和同等良好的公用事业保障。第二,我们观察到,私人选择框架(以前和我们)可以用来改进许多基本的保密数据分析任务的准确性/信任性交易,包括查询发布、最高至k$选择和稳定选择。最后,对于在线环境,我们应用私人测试来设计一个适应性查询释放机制,这提高了对庆祝硬和罗斯布卢的私人多倍重算算法(FOCS2010)的信任度参数的样本复杂性依赖度。