论文标题
低维
Private Approximations of a Convex Hull in Low Dimensions
论文作者
论文摘要
我们给出了第一个差异私人算法，这些算法估算了欧几里得空间中点的各种几何特征，例如直径，宽度，凸面船体的体积，最小的盒子，最小球。我们的算法并没有（非主要）近似给定的点$ p $的凸起，而是近似于$ p $引起的$κ$ -Tukey区域的几何特征（Tukey-Depth $κ$或更大的点的所有点）。此外，我们的近似值都是双重标准：对于任何几何特征$ $ $ $ $ us $（α，δ）$ - 近似值是$（1-α）μ（d_p（κ）$和$（1+α）μ（d_p（κ-δ）$）之间的“夹紧”的值。 我们的工作旨在生产$ d_p（κ）$}的\ emph {$（α，δ）$ - 内核，即$ \ nathcal {s} $，使得（换档后）认为$（1-α）d_p（1-α）d_p（κ）\ subset \ subset \ subss \ subss \ subss \ subssf { （1+α）d_p（κ-δ）$。我们表明，正如Agarwal等人〜[2004]，\ emph {Fails flafs}提出的，对方向内核的双标准近似的类似概念，因此我们会导致键入近似项目产生核的近似值的概念。首先，我们提供了差异化的私有算法，这些算法找到了“脂肪” Tukey-Region的$（α，δ）$ - 内核。然后，基于最小框的私人近似值，我们找到了一种转换，该转换确实将$ d_p（κ）$转换为“脂肪”区域\ emph {，但仅当它的体积与$ d_p（κ-Δ）$的体积成正比时。最后，我们给出了一种新颖的私人算法，该算法找到了深度参数$κ$，$ d_p（κ）$的体积可与$ d_p（κ-δ）$相当。我们希望这项工作能够进一步研究差异隐私和计算几何形状的交集。
We give the first differentially private algorithms that estimate a variety of geometric features of points in the Euclidean space, such as diameter, width, volume of convex hull, min-bounding box, min-enclosing ball etc. Our work relies heavily on the notion of \emph{Tukey-depth}. Instead of (non-privately) approximating the convex-hull of the given set of points $P$, our algorithms approximate the geometric features of the $κ$-Tukey region induced by $P$ (all points of Tukey-depth $κ$ or greater). Moreover, our approximations are all bi-criteria: for any geometric feature $μ$ our $(α,Δ)$-approximation is a value "sandwiched" between $(1-α)μ(D_P(κ))$ and $(1+α)μ(D_P(κ-Δ))$. Our work is aimed at producing a \emph{$(α,Δ)$-kernel of $D_P(κ)$}, namely a set $\mathcal{S}$ such that (after a shift) it holds that $(1-α)D_P(κ)\subset \mathsf{CH}(\mathcal{S}) \subset (1+α)D_P(κ-Δ)$. We show that an analogous notion of a bi-critera approximation of a directional kernel, as originally proposed by Agarwal et al~[2004], \emph{fails} to give a kernel, and so we result to subtler notions of approximations of projections that do yield a kernel. First, we give differentially private algorithms that find $(α,Δ)$-kernels for a "fat" Tukey-region. Then, based on a private approximation of the min-bounding box, we find a transformation that does turn $D_P(κ)$ into a "fat" region \emph{but only if} its volume is proportional to the volume of $D_P(κ-Δ)$. Lastly, we give a novel private algorithm that finds a depth parameter $κ$ for which the volume of $D_P(κ)$ is comparable to $D_P(κ-Δ)$. We hope this work leads to the further study of the intersection of differential privacy and computational geometry.
