KNG: The K-Norm Gradient Mechanism
This work addresses the challenge of balancing privacy and utility in statistical analysis for data scientists and privacy researchers, representing an incremental improvement over existing mechanisms like the exponential mechanism.
The paper tackles the problem of producing differentially private statistical summaries by introducing the K-Norm Gradient (KNG) mechanism, which achieves strong utility performance comparable to objective perturbation while maintaining flexibility, with theoretical and empirical results showing asymptotically negligible noise compared to statistical error in settings like linear and quantile regression.
This paper presents a new mechanism for producing sanitized statistical summaries that achieve \emph{differential privacy}, called the \emph{K-Norm Gradient} Mechanism, or KNG. This new approach maintains the strong flexibility of the exponential mechanism, while achieving the powerful utility performance of objective perturbation. KNG starts with an inherent objective function (often an empirical risk), and promotes summaries that are close to minimizing the objective by weighting according to how far the gradient of the objective function is from zero. Working with the gradient instead of the original objective function allows for additional flexibility as one can penalize using different norms. We show that, unlike the exponential mechanism, the noise added by KNG is asymptotically negligible compared to the statistical error for many problems. In addition to theoretical guarantees on privacy and utility, we confirm the utility of KNG empirically in the settings of linear and quantile regression through simulations.