# KNG: The K-Norm Gradient Mechanism

arXiv: https://arxiv.org/abs/1905.09436 · HTML: https://mlsanity.com/paper/1905.09436/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2019.

## Built on by (most cited first, 8 of 8)

- [Differentially private Riemannian optimization](https://mlsanity.com/paper/2205.09494/) (2022)
- [Differentially Private Bootstrap: New Privacy Analysis and Inference Strategies](https://mlsanity.com/paper/2210.06140/) (2022)
- [Shape And Structure Preserving Differential Privacy](https://mlsanity.com/paper/2209.12667/) (2022)
- [Differentially Private Covariate Balancing Causal Inference](https://mlsanity.com/paper/2410.14789/) (2024)
- [Differentially Private Topological Data Analysis](https://mlsanity.com/paper/2305.03609/) (2023)
- [Geometric Renyi Differential Privacy: Ricci Curvature Characterized by Heat Diffusion Mechanisms](https://mlsanity.com/paper/2604.20761/) (2026)
- [Pure Differential Privacy for Functional Summaries with a Laplace-like Process](https://mlsanity.com/paper/2309.00125/) (2023)
- [Differentially Private Geodesic Regression](https://mlsanity.com/paper/2504.11304/) (2025)

## Abstract (arXiv)

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.