论文标题
广泛的私人选择和高信心测试
Generalized Private Selection and Testing with High Confidence
论文作者
论文摘要
组成定理是一般且强大的工具，可促进来自Per-Access隐私范围的多个数据访问的隐私会计。但是，与端到端分析相比，它们通常会导致界限较弱。减轻指数机制（或报告噪声最大）和稀疏向量技术的两种流行工具。它们在最近的几个私人选择/测试框架中被概括，包括Liu和Talwar的作品（Stoc 2019），以及Papernot和Steinke（ICLR 2022）。 在这项工作中，我们首先提出了一个私人选择和测试的替代框架，并提供了更简单的隐私证明和同样良好的公用事业保证。其次，我们观察到，可以应用私人选择框架（以前的选择框架）来提高许多基本隐私的数据分析任务的准确性/置信度权衡，包括查询发布，上$ K $选择和稳定选择。 最后，对于在线设置，我们将私人测试应用于自适应查询释放的机制，从而提高了对Hardt和Rothblum的著名私人乘法算法的置信参数的样本复杂性依赖性（FOCS 2010）。
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).
