# Statistical Theory of Differentially Private Marginal-based Data Synthesis Algorithms

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 37 references that are in the map.
- First posted on arXiv 21 Jan 2023.

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

- [Real-valued (Medical) Time Series Generation with Recurrent Conditional GANs](https://mlsanity.com/paper/1706.02633/) (2017)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [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)
- [Tight Lower Bounds for Differentially Private Selection](https://mlsanity.com/paper/1704.03024/) (2017)
- [Collecting and Analyzing Data from Smart Device Users with Local Differential Privacy](https://mlsanity.com/paper/1606.05053/) (2016)
- [Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations](https://mlsanity.com/paper/1308.1385/) (2013)
- [Measuring the quality of Synthetic data for use in competitions](https://mlsanity.com/paper/1806.11345/) (2018)

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

- [A Survey on Statistical Theory of Deep Learning: Approximation, Training Dynamics, and Generative Models](https://mlsanity.com/paper/2401.07187/) (2024)
- [Graphical vs. Deep Generative Models: Measuring the Impact of Differentially Private Mechanisms and Budgets on Utility](https://mlsanity.com/paper/2305.10994/) (2023)
- [Unified Enhancement of Privacy Bounds for Mixture Mechanisms via f-Differential Privacy](https://mlsanity.com/paper/2310.19973/) (2023)
- [Utility Theory of Synthetic Data Generation](https://mlsanity.com/paper/2305.10015/) (2023)
- [Neural Collapse Meets Differential Privacy: Curious Behaviors of NoisyGD with Near-perfect Representation Learning](https://mlsanity.com/paper/2405.08920/) (2024)
- [Bounding the Excess Risk for Linear Models Trained on Marginal-Preserving, Differentially-Private, Synthetic Data](https://mlsanity.com/paper/2402.04375/) (2024)
- [PrAda-GAN: A Private Adaptive Generative Adversarial Network with Bayes Network Structure](https://mlsanity.com/paper/2511.07997/) (2025)

## Abstract (arXiv)

Marginal-based methods achieve promising performance in the synthetic data competition hosted by the National Institute of Standards and Technology (NIST). To deal with high-dimensional data, the distribution of synthetic data is represented by a probabilistic graphical model (e.g., a Bayesian network), while the raw data distribution is approximated by a collection of low-dimensional marginals. Differential privacy (DP) is guaranteed by introducing random noise to each low-dimensional marginal distribution. Despite its promising performance in practice, the statistical properties of marginal-based methods are rarely studied in the literature. In this paper, we study DP data synthesis algorithms based on Bayesian networks (BN) from a statistical perspective. We establish a rigorous accuracy guarantee for BN-based algorithms, where the errors are measured by the total variation (TV) distance or the L2 distance. Related to downstream machine learning tasks, an upper bound for the utility error of the DP synthetic data is also derived. To complete the picture, we establish a lower bound for TV accuracy that holds for every ε-DP synthetic data generator.