# Optimizing error of high-dimensional statistical queries under differential privacy

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Aug 2018.

## Built on by (most cited first, 29 of 29)

- [Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods](https://mlsanity.com/paper/2106.07153/) (2021)
- [Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams](https://mlsanity.com/paper/2202.08312/) (2022)
- [Differentially Private Query Release Through Adaptive Projection](https://mlsanity.com/paper/2103.06641/) (2021)
- [(Amplified) Banded Matrix Factorization: A unified approach to private training](https://mlsanity.com/paper/2306.08153/) (2023)
- [Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning](https://mlsanity.com/paper/2211.06530/) (2022)
- [Leveraging Public Data for Practical Private Query Release](https://mlsanity.com/paper/2102.08598/) (2021)
- [SoK: Privacy-Preserving Data Synthesis](https://mlsanity.com/paper/2307.02106/) (2023)
- [Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy](https://mlsanity.com/paper/2302.01463/) (2023)
- [Generating Private Synthetic Data with Genetic Algorithms](https://mlsanity.com/paper/2306.03257/) (2023)
- [Noise-Aware Statistical Inference with Differentially Private Synthetic Data](https://mlsanity.com/paper/2205.14485/) (2022)
- [Private Query Release via the Johnson-Lindenstrauss Transform](https://mlsanity.com/paper/2208.07410/) (2022)
- [Relaxed Marginal Consistency for Differentially Private Query Answering](https://mlsanity.com/paper/2109.06153/) (2021)
- [The Importance of Being Discrete: Measuring the Impact of Discretization in End-to-End Differentially Private Synthetic Data](https://mlsanity.com/paper/2504.06923/) (2025)
- [Online Differentially Private Synthetic Data Generation](https://mlsanity.com/paper/2402.08012/) (2024)
- [Improved Communication-Privacy Trade-offs in L2 Mean Estimation under Streaming Differential Privacy](https://mlsanity.com/paper/2405.02341/) (2024)
- [Improved Matrix Gaussian Mechanism for Differential Privacy](https://mlsanity.com/paper/2104.14808/) (2021)
- [General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation](https://mlsanity.com/paper/2301.13850/) (2023)
- [Spending Privacy Budget Fairly and Wisely](https://mlsanity.com/paper/2204.12903/) (2022)
- [Private Synthetic Data with Hierarchical Structure](https://mlsanity.com/paper/2206.05942/) (2022)
- [Answering Private Linear Queries Adaptively using the Common Mechanism](https://mlsanity.com/paper/2212.00135/) (2022)
- [ResidualPlanner+: a scalable matrix mechanism for marginals and beyond](https://mlsanity.com/paper/2305.08175/) (2023)
- [Efficient and Private Marginal Reconstruction with Local Non-Negativity](https://mlsanity.com/paper/2410.01091/) (2024)
- [Denoising the US Census: Succinct Block Hierarchical Regression](https://mlsanity.com/paper/2603.10099/) (2026)
- [Accurate and Scalable Matrix Mechanisms via Divide and Conquer](https://mlsanity.com/paper/2604.00868/) (2026)
- [PRIMO: Private Regression in Multiple Outcomes](https://mlsanity.com/paper/2303.04195/) (2023)
- [Partition-based differentially private synthetic data generation](https://mlsanity.com/paper/2310.06371/) (2023)
- [Differentially Private Range Queries with Correlated Input Perturbation](https://mlsanity.com/paper/2402.07066/) (2024)
- [Differentially Private Publication of Electricity Time Series Data in Smart Grids](https://mlsanity.com/paper/2408.16017/) (2024)
- [Minimax optimal differentially private synthetic data for smooth queries](https://mlsanity.com/paper/2602.01607/) (2026)

## Abstract (arXiv)

Differentially private algorithms for answering sets of predicate counting queries on a sensitive database have many applications. Organizations that collect individual-level data, such as statistical agencies and medical institutions, use them to safely release summary tabulations. However, existing techniques are accurate only on a narrow class of query workloads, or are extremely slow, especially when analyzing more than one or two dimensions of the data. In this work we propose HDMM, a new differentially private algorithm for answering a workload of predicate counting queries, that is especially effective for higher-dimensional datasets. HDMM represents query workloads using an implicit matrix representation and exploits this compact representation to efficiently search (a subset of) the space of differentially private algorithms for one that answers the input query workload with high accuracy. We empirically show that HDMM can efficiently answer queries with lower error than state-of-the-art techniques on a variety of low and high dimensional datasets.