Timezone: »

 
Poster
Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms
Hilal Asi · John Duchi

Tue Dec 08 09:00 AM -- 11:00 AM (PST) @ Poster Session 1 #260
in Poster Session 2 »

We study and provide instance-optimal algorithms in differential privacy by extending and approximating the inverse sensitivity mechanism. We provide two approximation frameworks, one which only requires knowledge of local sensitivities, and a gradient-based approximation for optimization problems, which are efficiently computable for a broad class of functions. We complement our analysis with instance-specific lower bounds for vector-valued functions, which demonstrate that our mechanisms are (nearly) instance-optimal under certain assumptions and that minimax lower bounds may not provide an accurate estimate of the hardness of a problem in general: our algorithms can significantly outperform minimax bounds for well-behaved instances. Finally, we use our approximation framework to develop private mechanisms for unbounded-range mean estimation, principal component analysis, and linear regression. For PCA, our mechanisms give an efficient (pure) differentially private algorithm with near-optimal rates.

Author Information

Hilal Asi (Stanford University)
John Duchi (Stanford)

More from the Same Authors