Near Instance-Optimality in Differential Privacy
This work addresses the challenge of optimizing privacy guarantees for specific data instances in differential privacy, which is incremental but offers practical improvements for privacy-preserving data analysis.
The authors tackled the problem of achieving near instance-optimality in differential privacy by developing new notions and mechanisms, showing that their inverse sensitivity mechanisms outperform the smooth sensitivity framework for functions like median and robust regression, with experimental validation.
We develop two notions of instance optimality in differential privacy, inspired by classical statistical theory: one by defining a local minimax risk and the other by considering unbiased mechanisms and analogizing the Cramer-Rao bound, and we show that the local modulus of continuity of the estimand of interest completely determines these quantities. We also develop a complementary collection mechanisms, which we term the inverse sensitivity mechanisms, which are instance optimal (or nearly instance optimal) for a large class of estimands. Moreover, these mechanisms uniformly outperform the smooth sensitivity framework on each instance for several function classes of interest, including real-valued continuous functions. We carefully present two instantiations of the mechanisms for median and robust regression estimation with corresponding experiments.