# Optimality of Matrix Mechanism on ℓpp-metric

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 24 references that are in the map.
- First posted on arXiv 4 Jun 2024.

## Builds on (most cited first, 6 of 6)

- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [The Power of Factorization Mechanisms in Local and Central Differential Privacy](https://mlsanity.com/paper/1911.08339/) (2019)
- [Almost Tight Error Bounds on Differentially Private Continual Counting](https://mlsanity.com/paper/2211.05006/) (2022)
- [Constant matters: Fine-grained Complexity of Differentially Private Continual Observation](https://mlsanity.com/paper/2202.11205/) (2022)
- [Factorization Norms and Hereditary Discrepancy](https://mlsanity.com/paper/1408.1376/) (2014)
- [General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation](https://mlsanity.com/paper/2301.13850/) (2023)

## Abstract (arXiv)

In this paper, we introduce the ℓpp-error metric (for p ≥ 2) when answering linear queries under the constraint of differential privacy. We characterize such an error under (ε,δ)-differential privacy. Before this paper, tight characterization in the hardness of privately answering linear queries was known under ℓ22-error metric (Edmonds et al., STOC 2020) and ℓp2-error metric for unbiased mechanisms (Nikolov and Tang, ITCS 2024). As a direct consequence of our results, we give tight bounds on answering prefix sum and parity queries under differential privacy for all constant p in terms of the ℓpp error, generalizing the bounds in Henzinger et al. (SODA 2023) for p=2.