私人统计估计的普遍实例 - 最佳机制

我们考虑差分隐私约束下的实例最优统计估计问题，其中机制必须适应输入数据集的难度。我们使用新的散度证明了一个新的实例特定下界，并表明它表征了私人统计估计的局部极小极大最优率。我们提出了两种新机制，它们对于一般估计问题（高达对数因子）来说是普遍实例最优的。我们的第一个机制，即总变异机制，建立在指数机制的基础上，具有总变异距离的稳定近似值，并且在高隐私制度 ε≤1/n\varepsilon \le 1/\sqrt{n}ε≤1/n​中是普遍实例最优的。我们的第二种机制，T 机制，基于 T 估计框架（Birge´，2006），使用截断对数似然比作为稳定测试：它对于任何 ε≤1\varepsilon \le 1ε≤1 直至对数因子都获得实例最优速率。最后，我们研究了我们的结果对鲁棒统计估计的影响，并表明我们的算法对于这个问题来说是普遍最优的，表征了鲁棒统计估计的最佳极小极大率。

ε≤1/n\varepsilon \le 1/\sqrt{n}ε≤1/n​ ε≤1/n\varepsilon \le 1/\sqrt{n} ε≤1/n ε ≤ 1 / n \varepsilon \le 1/\sqrt{n} ε≤1/n​ ε≤ 1/n​ 1/ n​ ​ ε≤1\varepsilon \le 1ε≤1 ε≤1\varepsilon \le 1 ε≤1 \varepsilon \le 1

† 西北大学‡ 斯坦福大学