Score Attack: A Lower Bound Technique for Optimal Differentially Private Learning
This work addresses the problem of ensuring privacy in data analysis for researchers and practitioners, offering a general technique to assess optimality, though it is incremental as it builds on existing tracing attack concepts.
The paper tackles the challenge of characterizing optimal statistical performance under differential privacy constraints by proposing the score attack method, which provides a lower bound on the minimax risk for parameter estimation, demonstrated to be optimal up to a logarithmic factor across various statistical models.
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 non-parametric regression over the Sobolev class.