KNG: The K-Norm Gradient Mechanism

Matthew Reimherr, Jordan Awan

Introduction

Differential Privacy (DP) is the gold standard for protecting individual data points in statistical summaries, but it traditionally comes at a steep cost to utility. Historically, researchers have relied on the Exponential Mechanism (EM) because of its incredible flexibility—it can privatize almost any optimization problem. However, EM adds "noise" at the same scale as the statistical error ($O(n^{-1/2})$). This means that even with infinite data, the private version of an estimator remains significantly less accurate than its non-private counterpart.

Alternative methods like objective perturbation offer much higher accuracy but are highly restrictive. They require the objective function to be perfectly smooth (twice-differentiable) and strongly convex. This excludes many common statistical tools, such as medians, quantiles, and robust regressions, which are often non-smooth.

The K-Norm Gradient Mechanism (KNG) bridges this gap, providing the high accuracy of objective perturbation with the broad flexibility of the Exponential Mechanism.

The KNG Approach: Focusing on the Gradient

The core innovation of KNG is shifting the focus from the objective function itself to its gradient.

In a standard (non-private) setting, we find the best estimate $\hat{\theta}$ by finding where the gradient of our loss function is zero: $\nabla \ell(\hat{\theta}) = 0$. Instead of just picking the single point where the gradient is zero, KNG defines a probability distribution that favors points where the gradient is close to zero.

Specifically, it samples a sanitized estimate $\tilde{\theta}$ with a density proportional to $\exp(-c \|\nabla \ell_n(\theta)\|_K)$, where $\|\cdot\|_K$ is a chosen norm (like the Manhattan or Euclidean norm).

Why is this groundbreaking? By penalizing the gradient linearly, the resulting privacy noise scales at $O(n^{-1})$. Because standard statistical error scales at $O(n^{-1/2})$, the privacy noise becomes "asymptotically negligible." As the dataset size $n$ grows, the private estimator behaves almost exactly like the non-private one. Furthermore, calculating the "sensitivity" (how much one person's data can change the result) of the gradient is often mathematically simpler than calculating the sensitivity of the objective function.

Empirical Results

The authors evaluated KNG using synthetic simulations to precisely control the ground truth and observe asymptotic behavior across different sample sizes.

Linear Regression

In a 12-dimensional linear regression simulation (with sample sizes ranging from $10^2$ to $10^7$), KNG's error tracked the non-private Maximum Likelihood Estimator (MLE) almost perfectly as $n$ increased. In contrast, the Exponential Mechanism maintained a large, constant gap in accuracy.

Linear Regression Performance

Quantile Regression

Unlike objective perturbation, KNG does not require a second derivative. This allowed the authors to create an efficient private mechanism for quantile regression, a vital tool for understanding data distributions beyond just the average. In a 2-dimensional model (sample sizes from $10^1$ to $10^5$), KNG successfully privatized the regression where objective perturbation was mathematically inapplicable.

Quantile Regression Performance

Limitations and Future Work

While KNG offers a powerful new framework, it comes with practical challenges:

  • The Sampling Challenge: KNG defines a probability distribution, but drawing a sample from it isn't always straightforward. The authors used Markov Chain Monte Carlo (MCMC) for their simulations, which can be computationally expensive and requires careful tuning.
  • Non-Convexity: Like gradient descent, KNG could struggle with objective functions that have many local minima (such as deep neural networks). It might promote outputs near any local minimum, not just the global one.
  • High-Dimensional Scaling: While the paper demonstrates success in 12 dimensions, further research is needed to evaluate how KNG handles extremely high-dimensional parameter spaces where MCMC sampling typically degrades.

Summary updated

Abstract

This paper presents a new mechanism for producing sanitized statistical summaries that achieve {\it differential privacy}, called the {\it 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.
BibTeX
@inproceedings{reimherr2019kng,
  author = {Matthew Reimherr and Jordan Awan},
  title = {{KNG: The K-Norm Gradient Mechanism}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=INkLfuodPa},
}
Figure