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, generalized in a recent private selection framework by Liu and Talwar (STOC 2019). In this work, we propose a flexible framework of private selection and testing that generalizes the one proposed by Liu and Talwar, supporting a wide range of applications. We apply our framework to solve several fundamental tasks, including query releasing, top-$k$ selection, and stable selection, with improved confidence-accuracy tradeoffs. Additionally, for online settings, we apply our 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).
翻译:在这项工作中,我们提议了一个灵活的私人选择和测试框架,将刘和塔尔瓦尔提出的个人选择和测试框架加以概括,支持广泛的应用。我们运用我们的框架来解决若干基本任务,包括查询释放、最高至一万元选择和稳定选择,同时改进信任度和准确性权衡。此外,对于在线环境,我们运用我们的私人测试设计一个适应性查询释放机制,从而改进对值得庆祝的哈特和罗布卢(2010年FOCS)私人多倍数加权算法(FOCS)的信任度参数的抽样复杂性。