Optimality of Matrix Mechanism on $\ell_p^p$-metric
This work addresses a theoretical gap in differential privacy for database queries, providing foundational insights for privacy-preserving data analysis, though it is incremental as it extends known results to a broader metric.
The paper tackles the problem of answering linear queries under differential privacy by introducing the ℓ_p^p-error metric for p ≥ 2 and characterizing the error under (ε,δ)-differential privacy, resulting in tight bounds for prefix sum and parity queries that generalize prior work for p=2.
In this paper, we introduce the $\ell_p^p$-error metric (for $p \geq 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 $\ell_2^2$-error metric (Edmonds et al., STOC 2020) and $\ell_p^2$-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 $\ell_p^p$ error, generalizing the bounds in Henzinger et al. (SODA 2023) for $p=2$.