KNG: The K-Norm Gradient Mechanism

Matthew Reimherr, Jordan Awan

Abstract

This paper presents a new mechanism for producing sanitized statistical summaries that achieve differential privacy, called the 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.

Introduction

In the field of Differential Privacy (DP), researchers often face a significant "utility gap." The Exponential Mechanism (EM) is the standard tool due to its immense flexibility; it can be applied to almost any problem where a "score" function can be defined. However, EM typically introduces noise on the order of $O(1/\sqrt{n})$, which can overwhelm the signal in small to medium-sized datasets.

In contrast, Objective Perturbation provides much higher accuracy with noise on the order of $O(1/n)$. However, its application is restricted to objective functions that are twice-differentiable and strongly convex. This precludes its use in common statistical tasks such as median estimation or quantile regression, where the underlying loss functions are non-smooth. The K-Norm Gradient (KNG) mechanism is designed to bridge this gap, offering the high utility of objective perturbation with the broad flexibility of the exponential mechanism.

The K-Norm Gradient Mechanism

The core innovation of KNG is the shift from penalizing the value of the loss function to penalizing its gradient. KNG releases a parameter estimate $\theta$ based on a probability density proportional to:

$$\exp\left( -\frac{\epsilon}{2\Delta} \|\nabla \ell_n(\theta)\|_K \right)$$

Where:

  • $\nabla \ell_n(\theta)$ is the gradient of the loss function (e.g., Mean Squared Error).
  • $\|\cdot\|_K$ is a custom "K-norm" that allows researchers to tailor the noise to the specific geometry of the problem.
  • $\epsilon$ is the privacy budget.

Because the optimal solution occurs where the gradient is zero, KNG naturally concentrates probability mass on the most accurate estimates. Unlike the Exponential Mechanism, where the penalty often grows quadratically near the optimum, KNG's linear penalty near the optimum allows the added noise to vanish at a rate of $O(1/n)$ as the sample size $n$ increases. This makes the privacy noise "statistically invisible" much sooner than with traditional general-purpose mechanisms.

Empirical Evaluation

The authors validated KNG through synthetic simulations, comparing its performance against the Exponential Mechanism (ExpMech), Objective Perturbation (ObjPert), and a non-private baseline.

Linear Regression

In a 12-dimensional linear regression model with sample sizes ranging from 100 to 10 million, KNG demonstrated performance nearly identical to Objective Perturbation, the current gold standard for accuracy in smooth settings. Both mechanisms significantly outperformed the Exponential Mechanism, which exhibited error rates orders of magnitude higher at large sample sizes.

Average L2 distance to truth for linear regression across different mechanisms. KNG tracks the performance of Objective Perturbation and approaches the non-private baseline as n increases.

Quantile Regression

The advantages of KNG are most apparent in non-smooth settings like quantile regression (simulated here in a 2-dimensional model with $n$ up to 100,000). Objective Perturbation cannot be applied here because the loss function is not smooth. KNG, however, handles these objectives easily. Simulations show that KNG's error rate closely tracks the non-private ideal, while the Exponential Mechanism remains significantly less accurate.

Average L2 distance to truth for quantile regression. KNG maintains high utility where Objective Perturbation is inapplicable, closely following the non-private estimator.

Discussion and Future Work

KNG provides a unified framework that encompasses several existing specialized DP algorithms, such as the Private Quantile algorithm. By exploiting the "gradient is enough" realization, KNG simplifies privacy proofs and sensitivity calculations.

However, challenges remain. Like gradient descent, KNG may struggle with non-convex objective functions where multiple local minima exist. Additionally, sampling from the KNG distribution in high-dimensional spaces can be computationally intensive, often requiring Markov Chain Monte Carlo (MCMC) methods. Future research may extend KNG to more complex structures like manifolds or Hilbert spaces, further expanding the toolkit for high-utility differential privacy.

Summary updated

Abstract

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.
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},
}

Loading related content...

Figure