Near Instance-Optimality in Differential Privacy
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.
Code (0)
등록된 구현이 없습니다.
Tasks
regressionSensitivitySimilar Papers 제목 키워드 기반
Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms
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 loc…
SensitivityNear-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment
In this paper, we study differentially private online learning problems in a stochastic environment under both bandit and full information feedback. For differentially private stochastic bandits, we propose both UCB and …
Thompson SamplingScore Attack: A Lower Bound Technique for Optimal Differentially Private Learning
Achieving optimal statistical performance while ensuring the privacy of personal data is a challenging yet crucial objective in modern data analysis. However, characterizing the optimality, particularly the minimax lower…
parameter estimationOrder-Optimal Instance-Dependent Bounds for Offline Reinforcement Learning with Preference Feedback
We consider offline reinforcement learning (RL) with preference feedback in which the implicit reward is a linear function of an unknown parameter. Given an offline dataset, our objective consists in ascertaining the opt…
Offline RLReinforcement Learning (RL)Optimality of Matrix Mechanism on $\ell_p^p$-metric
In this paper, we introduce the $\ell_p^p$-error metric (for $p \geq 2$) when answering linear queries under the constraint of differential privacy. We characterize such an error under $(\epsilon,\delta)$-differential pr…