Optimal Private Halfspace Counting via Discrepancy
S. Muthukrishnan Rutgers University, Aleksandar Nikolov Rutgers University
Abstract
A range counting problem is specified by a set $P$ of size $|P|=n$ of points in $\mathbb{R}^{d}$ , an integer weight $x_{p}$ associated to each point $p\in P$ , and a range space $\mathcal{R}\subseteq 2^{P}$ . Given a query range $R\in\mathcal{R}$ , the output is $R(\mathbf{x})=\sum_{p\in R}{x_{p}}$ . The average squared error of an algorithm $\mathcal{A}$ is $\frac{1}{|\mathcal{R}|}\sum_{R\in\mathcal{R}}{\left(\mathcal{A}(R,\mathbf{x})-R(\mathbf{x})\right)^{2}}$ . Range counting for different range spaces is a central problem in Computational Geometry.
中文速览
如何在保护数据隐私的前提下高效回答几何范围查询（range counting），是计算几何与差分隐私交叉领域长期未解决的核心问题。研究者针对半空间计数（halfspace counting）这一典型问题，借助组合差异理论（discrepancy theory）同时给出了上界和下界：构造了一个满足 (ε,δ)-差分隐私的算法，将平均平方误差控制在 O(n^{1−1/d}) 量级，并证明任何差分隐私算法都无法做得更好，从而得到紧匹配的 Θ(n^{1−1/d}) 界。这一结果说明经典 Dinur-Nissim 对任意子集查询所建立的 Ω(n) 下界并不适用于半空间这类具有几何结构的查询，同时也首次为正交范围计数（orthogonal range counting）给出了超常数下界 Ω((log n)^{d−1})，填补了该领域长达多年的空白，为利用查询的几何结构设计更精准的差分隐私机制提供了理论依据。
原文 arXiv:1203.5453;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1203.5453v1