# Relaxed Marginal Consistency for Differentially Private Query Answering

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 43 references that are in the map.
- First posted on arXiv 13 Sep 2021.

## Builds on (most cited first, 15 of 15)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Winning the NIST Contest: A scalable and general approach to differentially private synthetic data](https://mlsanity.com/paper/2108.04978/) (2021)
- [Graphical-model based estimation and inference for differential privacy](https://mlsanity.com/paper/1901.09136/) (2019)
- [Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods](https://mlsanity.com/paper/2106.07153/) (2021)
- [Differentially Private Query Release Through Adaptive Projection](https://mlsanity.com/paper/2103.06641/) (2021)
- [New Oracle-Efficient Algorithms for Private Synthetic Data Release](https://mlsanity.com/paper/2007.05453/) (2020)
- [Leveraging Public Data for Practical Private Query Release](https://mlsanity.com/paper/2102.08598/) (2021)
- [Optimizing error of high-dimensional statistical queries under differential privacy](https://mlsanity.com/paper/1808.03537/) (2018)
- [Dual Query: Practical Private Query Release for High Dimensional Data](https://mlsanity.com/paper/1402.1526/) (2014)
- [Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations](https://mlsanity.com/paper/1308.1385/) (2013)
- [Learning Graphical Model Parameters with Approximate Marginal Inference](https://mlsanity.com/paper/1301.3193/) (2013)
- [DPSyn: Experiences in the NIST Differential Privacy Data Synthesis Challenges](https://mlsanity.com/paper/2106.12949/) (2021)
- [Ektelo: A Framework for Defining Differentially-Private Computations](https://mlsanity.com/paper/1808.03555/) (2018)
- [Data-Dependent Differentially Private Parameter Learning for Directed Graphical Models](https://mlsanity.com/paper/1905.12813/) (2019)
- [Concavity of reweighted Kikuchi approximation](https://mlsanity.com/paper/1410.7098/) (2014)

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

- [Private Synthetic Data for Multitask Learning and Marginal Queries](https://mlsanity.com/paper/2209.07400/) (2022)
- [On the Utility Recovery Incapability of Neural Net-based Differential Private Tabular Training Data Synthesizer under Privacy Deregulation](https://mlsanity.com/paper/2211.15809/) (2022)
- [Utility Theory of Synthetic Data Generation](https://mlsanity.com/paper/2305.10015/) (2023)
- [Joint Selection: Adaptively Incorporating Public Information for Private Synthetic Data](https://mlsanity.com/paper/2403.07797/) (2024)
- [ResidualPlanner+: a scalable matrix mechanism for marginals and beyond](https://mlsanity.com/paper/2305.08175/) (2023)
- [Tight End-to-End Accounting for Differentially Private Synthetic Data](https://mlsanity.com/paper/2610.17249/) (2026)

## Abstract (arXiv)

Many differentially private algorithms for answering database queries involve a step that reconstructs a discrete data distribution from noisy measurements. This provides consistent query answers and reduces error, but often requires space that grows exponentially with dimension. Private-PGM is a recent approach that uses graphical models to represent the data distribution, with complexity proportional to that of exact marginal inference in a graphical model with structure determined by the co-occurrence of variables in the noisy measurements. Private-PGM is highly scalable for sparse measurements, but may fail to run in high dimensions with dense measurements. We overcome the main scalability limitation of Private-PGM through a principled approach that relaxes consistency constraints in the estimation objective. Our new approach works with many existing private query answering algorithms and improves scalability or accuracy with no privacy cost.