论文标题
如何在凸赫尔私下找到一个点
How to Find a Point in the Convex Hull Privately
论文作者
论文摘要
我们研究了如何在$ {\ mathbb r}^d $中以差异私有方式计算输入集合$ s $ n $点$ s $ n $点的问题。这个问题是非琐事的，当施加差异性隐私时，事实证明是非常深的。特别是，众所周知，输入点必须位于固定有限的子集$ g \ subseteq {\ mathbb r}^d $上，此外，$ s $的大小必须随$ g $的大小而增长。以前的作品着重于了解$ n $需要如何使用$ | g | $增长，并表明$ n = o \ left（d^{2.5} \ cdot8^{\ log^*| g |} \ right）$ Suffices（因此，$ n $不必用$ | g | $显着增长）。但是，可用的构造显示运行时间至少$ | g |^{d^2} $，其中通常$ | g | = x^d $对于某些（大）离散参数$ x $，因此运行时间实际上是$ω（x^{d^3}）$。 在本文中，假设$ n =ω（d^4 \ log x）$，我们给出了以$ o（n^d）$时间运行的差异私有算法。为了获得这个结果，我们研究和利用Tukey级别的某些结构性属性（区域$ d _ {\ ge k} $由tukey深度至少为$ k $的点组成，以$ k = 0,1,1，... $）。特别是，我们在其量的卷中为点集$ s $在一般位置中得出了较低的界限，并为处理点的处理点设置$ s $ s $ s $ s $ s $ s $ s $ s $ s $ s $ s。建造Tukey区域的幼稚方法需要$ n^{o（d^2）} $时间。为了将成本降低到$ o（n^d）$，我们使用近似方案来估算Tukey区域的数量（在其仿射跨度内），以及从该区域中取得一个点，该方案基于Lováss和Vempala的体积估算框架（couss and Vempala）和COSIS和VEMPALA（coumpala）和Vempala和Vempala和Vempala和Vempala（focs couss and vempala and vempala and vempala and vempala and vempala）（使这个框架有差异化构成了我们解决的一系列技术挑战。
We study the question of how to compute a point in the convex hull of an input set $S$ of $n$ points in ${\mathbb R}^d$ in a differentially private manner. This question, which is trivial non-privately, turns out to be quite deep when imposing differential privacy. In particular, it is known that the input points must reside on a fixed finite subset $G\subseteq{\mathbb R}^d$, and furthermore, the size of $S$ must grow with the size of $G$. Previous works focused on understanding how $n$ needs to grow with $|G|$, and showed that $n=O\left(d^{2.5}\cdot8^{\log^*|G|}\right)$ suffices (so $n$ does not have to grow significantly with $|G|$). However, the available constructions exhibit running time at least $|G|^{d^2}$, where typically $|G|=X^d$ for some (large) discretization parameter $X$, so the running time is in fact $Ω(X^{d^3})$. In this paper we give a differentially private algorithm that runs in $O(n^d)$ time, assuming that $n=Ω(d^4\log X)$. To get this result we study and exploit some structural properties of the Tukey levels (the regions $D_{\ge k}$ consisting of points whose Tukey depth is at least $k$, for $k=0,1,...$). In particular, we derive lower bounds on their volumes for point sets $S$ in general position, and develop a rather subtle mechanism for handling point sets $S$ in degenerate position (where the deep Tukey regions have zero volume). A naive approach to the construction of the Tukey regions requires $n^{O(d^2)}$ time. To reduce the cost to $O(n^d)$, we use an approximation scheme for estimating the volumes of the Tukey regions (within their affine spans in case of degeneracy), and for sampling a point from such a region, a scheme that is based on the volume estimation framework of Lovász and Vempala (FOCS 2003) and of Cousins and Vempala (STOC 2015). Making this framework differentially private raises a set of technical challenges that we address.
