Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms

2020-12-01 · NeurIPS 2020 12 · Hilal Asi, John C. Duchi

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.

📄 PDF Abstract BibTeX

Code (0)

등록된 구현이 없습니다.

Tasks

Sensitivity

Methods 이 논문이 사용한 방법론

PCA Principle Components Analysis (PCA) is an unsupervised method primary used for dimensionality reduction within machine learning. PCA is calculated via a singular value…

Near Instance-Optimality in Differential Privacy

2020-05-16 · Hilal Asi, John C. Duchi

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 C…

regression Sensitivity

Privacy-Preserving Q-Learning with Functional Noise in Continuous Spaces

2019-12-01 · NeurIPS 2019 12 · Baoxiang Wang, Nidhi Hegde

We consider differentially private algorithms for reinforcement learning in continuous spaces, such that neighboring reward functions are indistinguishable. This protects the reward information from being exploited by me…

Privacy Preserving Q-Learning reinforcement-learning Reinforcement Learning+1

Privacy-preserving Q-Learning with Functional Noise in Continuous State Spaces

2019-01-30 · Baoxiang Wang, Nidhi Hegde

Privacy Preserving Q-Learning reinforcement-learning Reinforcement Learning+1

Differentially Private Sliced Inverse Regression: Minimax Optimality and Algorithm

2024-01-16 · Xintao Xia, Linjun Zhang, Zhanrui Cai

Privacy preservation has become a critical concern in high-dimensional data analysis due to the growing prevalence of data-driven applications. Since its proposal, sliced inverse regression has emerged as a widely utiliz…

Dimensionality Reduction regression

Privacy and Utility Tradeoff in Approximate Differential Privacy

2018-10-01 · Quan Geng, Wei Ding, Ruiqi Guo, Sanjiv Kumar

We characterize the minimum noise amplitude and power for noise-adding mechanisms in $(\epsilon, \delta)$-differential privacy for single real-valued query function. We derive new lower bounds using the duality of linear…