改进隐私保护密度估计，查询更快更准。
Differentially Private Kernel Density Estimation
- 设计新树结构，将查询结果拆成更高效组合。
- 查询时间降为原来的1/α⁻¹log n，误差更小。
- 适合需要高精度隐私计算的科研与工程场景。
本文提出一种优化的差分隐私数据结构用于核密度估计（KDE），在隐私-效用权衡和效率上均优于以往方法。给定相似度函数 $f$（或DP KDE）及私有数据集 $X \subset \mathbb{R}^d$，目标是预处理 $X$，使对任意查询点 $y\in\mathbb{R}^d$，能以差分隐私方式近似计算 $\sum_{x \in X} f(x, y)$。此前最优算法针对 $f(x,y) =\| x - y \|_1$，需 $O(nd)$ 预处理空间与时间，查询时间为 $d \log n$，误差保证为 $(1+α)$-近似，且误差依赖于 $ε^{-1} α^{-0.5} d^{1.5} R \log^{1.5} n$。本文在三方面实现改进：查询时间降低 $α^{-1} \log n$ 倍；近似比从 $α$ 提升至 1；误差依赖项减少 $α^{-0.5}$ 倍。技术上，新方法重构搜索树：不同于以往将答案拆分为 $α^{-1} \log n$ 个由 $\log n$ 个值求和得到的部分，我们将其拆为 $\log n$ 个部分，每部分由两个距离值、两个计数值及 $y$ 本身智能组合而成。该树结构可能具有独立研究价值。
原文摘要 · Abstract (English)
We introduce a refined differentially private (DP) data structure for kernel density estimation (KDE), offering not only improved privacy-utility tradeoff but also better efficiency over prior results. Specifically, we study the mathematical problem: given a similarity function $f$ (or DP KDE) and a private dataset $X \subset \mathbb{R}^d$, our goal is to preprocess $X$ so that for any query $y\in\mathbb{R}^d$, we approximate $\sum_{x \in X} f(x, y)$ in a differentially private fashion. The best previous algorithm for $f(x,y) =\| x - y \|_1$ is the node-contaminated balanced binary tree by [Backurs, Lin, Mahabadi, Silwal, and Tarnawski, ICLR 2024]. Their algorithm requires $O(nd)$ space and time for preprocessing with $n=|X|$. For any query point, the query time is $d \log n$, with an error guarantee of $(1+α)$-approximation and $ε^{-1} α^{-0.5} d^{1.5} R \log^{1.5} n$. In this paper, we improve the best previous result [Backurs, Lin, Mahabadi, Silwal, and Tarnawski, ICLR 2024] in three aspects: - We reduce query time by a factor of $α^{-1} \log n$. - We improve the approximation ratio from $α$ to 1. - We reduce the error dependence by a factor of $α^{-0.5}$. From a technical perspective, our method of constructing the search tree differs from previous work [Backurs, Lin, Mahabadi, Silwal, and Tarnawski, ICLR 2024]. In prior work, for each query, the answer is split into $α^{-1} \log n$ numbers, each derived from the summation of $\log n$ values in interval tree countings. In contrast, we construct the tree differently, splitting the answer into $\log n$ numbers, where each is a smart combination of two distance values, two counting values, and $y$ itself. We believe our tree structure may be of independent interest.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。