# Structure and Sensitivity in Differential Privacy: Comparing K-Norm Mechanisms

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jan 2018.

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

- [Joint Privacy Enhancement and Quantization in Federated Learning](https://mlsanity.com/paper/2208.10888/) (2022)
- [Mean estimation in the add-remove model of differential privacy](https://mlsanity.com/paper/2312.06658/) (2023)
- [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 multivariate medians](https://mlsanity.com/paper/2210.06459/) (2022)
- [Is merging worth it? Securely evaluating the information gain for causal dataset acquisition](https://mlsanity.com/paper/2409.07215/) (2024)
- [Pure Differential Privacy for Functional Summaries with a Laplace-like Process](https://mlsanity.com/paper/2309.00125/) (2023)
- [The Normal Distributions Indistinguishability Spectrum and its Application to Privacy-Preserving Machine Learning](https://mlsanity.com/paper/2309.01243/) (2023)
- [Choose Wisely and Privately: Proactive Client Selection for Fair and Efficient Federated Learning](https://mlsanity.com/paper/2605.20975/) (2026)

## Abstract (arXiv)

Differential privacy (DP), provides a framework for provable privacy protection against arbitrary adversaries, while allowing the release of summary statistics and synthetic data. We address the problem of releasing a noisy real-valued statistic vector T, a function of sensitive data under DP, via the class of K-norm mechanisms with the goal of minimizing the noise added to achieve privacy. First, we introduce the sensitivity space of T, which extends the concepts of sensitivity polytope and sensitivity hull to the setting of arbitrary statistics T. We then propose a framework consisting of three methods for comparing the K-norm mechanisms: 1) a multivariate extension of stochastic dominance, 2) the entropy of the mechanism, and 3) the conditional variance given a direction, to identify the optimal K-norm mechanism. In all of these criteria, the optimal K-norm mechanism is generated by the convex hull of the sensitivity space. Using our methodology, we extend the objective perturbation and functional mechanisms and apply these tools to logistic and linear regression, allowing for private releases of statistical results. Via simulations and an application to a housing price dataset, we demonstrate that our proposed methodology offers a substantial improvement in utility for the same level of risk.