Instance-Specific Asymmetric Sensitivity in Differential Privacy
David Durfee
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.