How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity
How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity
复制标题
DOI：
10.48550/arxiv.2210.03831
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Jeremiah Blocki;Elena Grigorescu;Tamalika Mukherjee;Samson Zhou
中科院分区：
文献类型：
--
作者：
Jeremiah Blocki;Elena Grigorescu;Tamalika Mukherjee;Samson Zhou
我们开发了一个框架，有效地将某些近似算法转换为差分私有变量，在黑盒的方式。具体地说，我们的结果集中在算法A，它输出一个近似函数f的形式$（1-a）f（x）-k \leq A（x）\leq（1+a）f（x）+k$，其中$k \in \mathbb{R}_{\geq 0}$表示加法误差，$a \in [0，1）$表示乘法误差可以"调整“到足够小的值，同时只会在运行时间/空间中引起多项式爆破。我们表明，这样的算法可以DP而不牺牲精度，只要函数f具有小的全局灵敏度。我们通过应用Nissim、Raskhodnikova和Smith（STOC 2007）开发的平滑灵敏度框架来实现这些结果。我们的框架自然适用于将非私有FPRAS和FPTAS算法转换为$\N $-DP近似算法，其中前一种情况需要额外的后处理步骤。我们应用我们的框架中的次线性时间和次线性空间算法的上下文中，同时保留在有意义的参数范围内的算法的性质。我们的结果包括第一个（据我们所知）$\n $-边缘DP次线性时间算法估计的三角形的数量，连接组件的数量，和一个最小生成树的图的重量。在流媒体算法领域，我们的研究结果包括$\emdash $-DP算法估计LP-范数，不同的元素，和加权最小生成树的插入只有和旋转栅门流。我们的变换还提供了一个私人版本的平滑直方图框架，这是通常用于转换流算法到滑动窗口变量，并实现了乘法近似许多问题，如估计Lp-范数，不同的元素，和最长的长度增加子序列。
We develop a framework for efficiently transforming certain approximation algorithms into differentially-private variants, in a black-box manner. Specifically, our results focus on algorithms A that output an approximation to a function f of the form $(1-a)f(x)-k \leq A(x) \leq (1+a)f(x)+k$, where $k \in \mathbb{R}_{\geq 0}$ denotes additive error and $a \in [0,1)$ denotes multiplicative error can be``tuned"to small-enough values while incurring only a polynomial blowup in the running time/space. We show that such algorithms can be made DP without sacrificing accuracy, as long as the function f has small global sensitivity. We achieve these results by applying the smooth sensitivity framework developed by Nissim, Raskhodnikova, and Smith (STOC 2007). Our framework naturally applies to transform non-private FPRAS and FPTAS algorithms into $\epsilon$-DP approximation algorithms where the former case requires an additional postprocessing step. We apply our framework in the context of sublinear-time and sublinear-space algorithms, while preserving the nature of the algorithm in meaningful ranges of the parameters. Our results include the first (to the best of our knowledge) $\epsilon$-edge DP sublinear-time algorithm for estimating the number of triangles, the number of connected components, and the weight of a minimum spanning tree of a graph. In the area of streaming algorithms, our results include $\epsilon$-DP algorithms for estimating Lp-norms, distinct elements, and weighted minimum spanning tree for both insertion-only and turnstile streams. Our transformation also provides a private version of the smooth histogram framework, which is commonly used for converting streaming algorithms into sliding window variants, and achieves a multiplicative approximation to many problems, such as estimating Lp-norms, distinct elements, and the length of the longest increasing subsequence.