We provide a new algorithmic framework for differentially private estimation of general functions that adapts to the hardness of the underlying dataset. We build upon previous work that gives a paradigm for selecting an output through the exponential mechanism based upon closeness of the inverse to the underlying dataset, termed the inverse sensitivity mechanism. Our framework will slightly modify the closeness metric and instead give a simple and efficient application of the sparse vector technique. While the inverse sensitivity mechanism was shown to be instance optimal, it was only with respect to a class of unbiased mechanisms such that the most likely outcome matches the underlying data. We break this assumption in order to more naturally navigate the bias-variance tradeoff, which will also critically allow for extending our method to unbounded data. In consideration of this tradeoff, we provide strong intuition and empirical validation that our technique will be particularly effective when the distances to the underlying dataset are asymmetric. This asymmetry is inherent to a range of important problems including fundamental statistics such as variance, as well as commonly used machine learning performance metrics for both classification and regression tasks. We efficiently instantiate our method in $O(n)$ time for these problems and empirically show that our techniques will give substantially improved differentially private estimations.

我们提供了一个新的算法框架，用于差分隐私估计一般函数，该框架根据底层数据集的难度进行动态调整。我们构建在先前的工作基础上，通过接近逆过程的数据集，即称为逆敏感性机制的指数机制选择一个输出的范例。我们的框架稍微修改了接近度度量，并提供了稀疏向量技术的简单有效应用。我们打破这个假设，以更自然地处理偏差-方差平衡，这也关键地允许我们将方法扩展到无界数据。考虑到这种平衡，我们提供了强有力的直觉和实证验证，表明我们的技术在与底层数据集的距离是非对称的情况下尤为有效。我们以$O(n)$的时间高效实现了这些问题，并通过实验证明我们的技术能够显著改进差分隐私估计。

差分隐私中的实例特定异质敏感度