Score 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 bound, under privacy constraints is technically difficult. To address this issue, we propose a novel approach called the score attack, which provides a lower bound on the differential-privacy-constrained minimax risk of parameter estimation. The score attack method is based on the tracing attack concept in differential privacy and can be applied to any statistical model with a well-defined score statistic. It can optimally lower bound the minimax risk of estimating unknown model parameters, up to a logarithmic factor, while ensuring differential privacy for a range of statistical problems. We demonstrate the effectiveness and optimality of this general method in various examples, such as the generalized linear model in both classical and high-dimensional sparse settings, the Bradley-Terry-Luce model for pairwise comparisons, and nonparametric regression over the Sobolev class.
Code (0)
등록된 구현이 없습니다.
Tasks
parameter estimationSimilar Papers 제목 키워드 기반
The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Bounds
We propose differentially private algorithms for parameter estimation in both low-dimensional and high-dimensional sparse generalized linear models (GLMs) by constructing private versions of projected gradient descent. W…
LEMMAparameter estimationRobust Testing and Estimation under Manipulation Attacks
We study robust testing and estimation of discrete distributions in the strong contamination model. We consider both the "centralized setting" and the "distributed setting with information constraints" including communic…
Gradient Masking Causes CLEVER to Overestimate Adversarial Perturbation Size
A key problem in research on adversarial examples is that vulnerability to adversarial examples is usually measured by running attack algorithms. Because the attack algorithms are not optimal, the attack algorithms are p…
Adversarial Attacks on Adversarial Bandits
We study a security threat to adversarial multi-armed bandits, in which an attacker perturbs the loss or reward signal to control the behavior of the victim bandit player. We show that the attacker is able to mislead any…
Multi-Armed BanditsRecommendation SystemsClassifier-independent Lower-Bounds for Adversarial Robustness
We theoretically analyse the limits of robustness to test-time adversarial and noisy examples in classification. Our work focuses on deriving bounds which uniformly apply to all classifiers (i.e all measurable functions …
Adversarial AttackAdversarial RobustnessGeneral Classification