Optimality of Matrix Mechanism on $\ell_p^p$-metric
Authors: Zongrui Zou, Jingcheng Liu, Jalaj Upadhyay
ICLR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we introduce the ℓp p-error metric (for p 2) when answering linear queries under the constraint of differential privacy. We characterize such an error under (ε, δ)-differential privacy in the natural add/remove model. Before this paper, tight characterization in the hardness of privately answering linear queries was known under ℓ2 2-error metric (Edmonds et al. (2020)) and ℓ2 p-error metric for unbiased mechanisms in the substitution model (Nikolov & Tang (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 ℓp p error, generalizing the bounds in Henzinger et al. (2023) for p = 2. Our main result is a lower bound on general (ε, δ)-differentially private mechanisms for answering linear queries in high privacy regimes in terms of certain factorization norms Nikolov & Tang (2024) defined below5 : γ(p)(A) := min LR=A trp/2(LL ) R 1 2 o , where trp(U) := Pd i=1 U p ii 1/p p < maxi [d] |Uii| p = is the p-trace. Equipped with this definition, we state our lower bound: Theorem 1.4 (Lower bound for (ε, δ)-DP) Fix any n, m N, ε (0, 1 2), 0 δ 1 and p [2, ). For any query matrix A Rm n, if a mechanism M : Rn Rm preserves (ε, δ)-differential privacy, then there exists a universal constant C , errℓp p(M, A) (1 δ)γ(p)(A) C ε , where δ = 2e2ε(e1/2 1) |
| Researcher Affiliation | Academia | Zongrui Zou, Jingcheng Liu State Key Laboratory for Novel Software Technology, New Cornerstone Science Laboratory Nanjing University 163 Xianlin Avenue, Nanjing, Jiangsu Province, 210023, China EMAIL, EMAIL Jalaj Upadhyay Management Science & Information Systems Department Rutgers University 100 Rockafeller Road, Piscataway, NJ 08854, USA EMAIL |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. It focuses on theoretical proofs and mathematical derivations of bounds. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code or links to a code repository. |
| Open Datasets | No | The paper introduces the ℓp p-error metric when answering linear queries under the constraint of differential privacy and studies problem types like prefix sum and parity queries. It does not refer to specific datasets used for empirical evaluation that would require public access information. |
| Dataset Splits | No | The paper focuses on theoretical analysis of error metrics for linear queries under differential privacy, and thus does not describe experiments with specific datasets or their splits. |
| Hardware Specification | No | The paper presents theoretical research, including proofs and derivations, and does not describe experiments requiring specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical in nature, presenting proofs and mathematical analysis. It does not describe any implementation or experimental setup that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper focuses on theoretical analysis and mathematical proofs related to differential privacy and error metrics for linear queries. It does not describe an experimental setup with hyperparameters or system-level training settings. |