Research map / Federated learning and privacy / Differential privacy
Optimality of Matrix Mechanism on $\ell_p^p$-metric
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Characterizes the worst-case l_p^p error of answering linear queries under (epsilon,delta)-DP via the generalized factorization norm gamma_(p), showing the matrix mechanism is near-optimal among all DP mechanisms, with tight bounds for prefix sums and parity queries.
Problem
Answering linear queries under differential privacy with an l_p^p error metric (p>=2) that interpolates between squared error and absolute error; prior tight characterizations covered only l_2^2 error or unbiased mechanisms under l_p^2 error.
Approach
Defines the l_p^p error and shows lower bounds for oblivious additive-noise mechanisms (without assuming unbiasedness) via a covariance p-trace argument, handling bias by case analysis and using a Hammersley-Chapman-Robins/chi-square argument on a restricted distribution, then reduces general DP mechanisms to oblivious ones; the matching upper bound is the factorization-based matrix mechanism with
Key results
- Lower bound: any (epsilon,delta)-DP mechanism has l_p^p error at least (1-delta~) gamma_(p)(A)/(C' epsilon), matching the matrix mechanism upper bound up to O(log(1/delta) min{p, log(2m)}) factors.
- For prefix sums, the l_p^p error is Theta(n^{1/p} log n) for constant p under (epsilon,delta)-DP, with a sqrt(log n) gap for p growing.
- For parity queries, the worst-case l_p^p error is Omega((1-delta)/(e^{3eps}-1) * binom(d,w)^{1/2+1/p}), matching the Gaussian mechanism for constant p.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an optimal matrix-mechanism factorization with Gaussian noise | Private answering of linear queries · General linear queries | ℓ_p^p error: \mathsf{err}_{\ell_p^p}(\mathcal M_{\mathsf{matrix}}, A) \lesssim \mathsf{err}_{\ell_p^p}(\mathcal M, A)\cdot \mathsf{po | Helped |
| Use a factorization matrix mechanism | Private prefix-sum queries · Prefix sum | ℓ_p^p error: O\left( \frac{n^{1/p}\log(n) \sqrt{\log(1/\delta)\cdot \min\{ p,\log(n)\}}}{ \varepsilon} \right) | Helped |
| Use the same mechanism for all constant p | Private prefix-sum queries · Prefix sum | ℓ_p^p error: \Theta_{\varepsilon,\delta}(n^{1/p} \log(n)) | Helped |
| Use the trivial Gaussian mechanism for parity queries | Private parity-query answering · Parity queries | ℓ_p^p error: O_{\varepsilon,\delta}\left( m^{1/2+1/p} \min\{ p,\log (m) \} \right); lower bound: \Omega_{\varepsilon,\delta}\left( m^ | Mixed |
Surprising findings
- The lower bound does not assume unbiased mechanisms, and the dependence on the minimum width of the sensitivity polytope appears only in the admissible range of delta rather than in the bound itself.
Limitations
- Only worst-case lower bounds over inputs; instance-optimality is not obtained for general mechanisms.
- Lower bound for general (epsilon,delta) with arbitrary epsilon relies on high privacy regime (epsilon<1/2) for some results.
- Sqrt(log n) gap between upper and lower bounds for prefix sums when p is large.
Experimental setup
Metrics: l_p^p error gamma_(p) factorization norm
Baselines: Gaussian mechanism binary tree mechanism Nikolov and Tang 2024
Builds on: Edmonds et al. 2020 (l_2^2 lower bound) Nikolov and Tang 2024 (l_p^2 instance optimality) Bhaskar et al. reduction matrix mechanism
Closest papers by meaning
- Asymptotic Optimality of the High-Dimensional Gaussian Mechanism and Improved Low-Dimensional Mechanisms for Differential Privacy (ICML 2026 · similarity 0.89)
- A Central Limit Theorem for Differentially Private Query Answering (NeurIPS 2021 · similarity 0.89)
- Approximate Differential Privacy of the $\ell_2$ Mechanism (ICML 2025 · similarity 0.89)
- Perturb-and-Project: Differentially Private Similarities and Marginals (ICML 2024 · similarity 0.86)
- Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation (NeurIPS 2026 · similarity 0.85)
- Private Prediction via Shrinkage (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.