Instance-Optimal Differentially Private Estimation
In this work, we study local minimax convergence estimation rates subject to $\epsilon$-differential privacy. Unlike worst-case rates, which may be conservative, algorithms that are locally minimax optimal must adapt to easy instances of the problem. We construct locally minimax differentially private estimators for one-parameter exponential families and estimating the tail rate of a distribution. In these cases, we show that optimal algorithms for simple hypothesis testing, namely the recent optimal private testers of Canonne et al. (2019), directly inform the design of locally minimax estimation algorithms.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Near-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 SamplingSubset-Based Instance Optimality in Private Estimation
We propose a new definition of instance optimality for differentially private estimation algorithms. Our definition requires an optimal algorithm to compete, simultaneously for every dataset $D$, with the best private be…
Instance-Optimal Private Density Estimation in the Wasserstein Distance
Estimating the density of a distribution from samples is a fundamental problem in statistics. In many practical settings, the Wasserstein distance is an appropriate error metric for density estimation. For example, when …
Density EstimationInstance-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 differentially private low-rank trace regression with guaranteed private initialization
We study differentially private (DP) estimation of a rank-$r$ matrix $M \in \RR^{d_1\times d_2}$ under the trace regression model with Gaussian measurement matrices. Theoretically, the sensitivity of non-private spectral…
regressionRiemannian optimizationSensitivity