HDMM: Optimizing error of high-dimensional statistical queries under differential privacy
This work addresses the challenge of efficient and accurate private data analysis for statisticians and data scientists, representing an incremental improvement over existing methods.
The paper tackles the problem of answering high-dimensional statistical queries under differential privacy with low error, introducing the High-Dimensional Matrix Mechanism (HDMM) that optimizes error for predicate counting queries and empirically shows lower expected error than state-of-the-art techniques, nearly matching lower bounds in some cases.
In this work we describe the High-Dimensional Matrix Mechanism (HDMM), a differentially private algorithm for answering a workload of predicate counting queries. HDMM represents query workloads using a compact implicit matrix representation and exploits this representation to efficiently optimize over (a subset of) the space of differentially private algorithms for one that is unbiased and answers the input query workload with low expected error. HDMM can be deployed for both $ε$-differential privacy (with Laplace noise) and $(ε, δ)$-differential privacy (with Gaussian noise), although the core techniques are slightly different for each. We demonstrate empirically that HDMM can efficiently answer queries with lower expected error than state-of-the-art techniques, and in some cases, it nearly matches existing lower bounds for the particular class of mechanisms we consider.