# New Oracle-Efficient Algorithms for Private Synthetic Data Release

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

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jul 2020.

## Built on by (most cited first, 30 of 43)

- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [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)
- [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)
- [Private Synthetic Data for Multitask Learning and Marginal Queries](https://mlsanity.com/paper/2209.07400/) (2022)
- [Privacy-Preserving Instructions for Aligning Large Language Models](https://mlsanity.com/paper/2402.13659/) (2024)
- [Private Set Generation with Discriminative Information](https://mlsanity.com/paper/2211.04446/) (2022)
- [Generating Private Synthetic Data with Genetic Algorithms](https://mlsanity.com/paper/2306.03257/) (2023)
- [Graphical vs. Deep Generative Models: Measuring the Impact of Differentially Private Mechanisms and Budgets on Utility](https://mlsanity.com/paper/2305.10994/) (2023)
- [The Elusive Pursuit of Reproducing PATE-GAN: Benchmarking, Auditing, Debugging](https://mlsanity.com/paper/2406.13985/) (2024)
- [dpart: Differentially Private Autoregressive Tabular, a General Framework for Synthetic Data Generation](https://mlsanity.com/paper/2207.05810/) (2022)
- [Noise-Aware Statistical Inference with Differentially Private Synthetic Data](https://mlsanity.com/paper/2205.14485/) (2022)
- [Post-processing Private Synthetic Data for Improving Utility on Selected Measures](https://mlsanity.com/paper/2305.15538/) (2023)
- [Optimal Differentially Private Model Training with Public Data](https://mlsanity.com/paper/2306.15056/) (2023)
- [Privacy-preserving data release leveraging optimal transport and particle gradient descent](https://mlsanity.com/paper/2401.17823/) (2024)
- [Joint Selection: Adaptively Incorporating Public Information for Private Synthetic Data](https://mlsanity.com/paper/2403.07797/) (2024)
- [Relaxed Marginal Consistency for Differentially Private Query Answering](https://mlsanity.com/paper/2109.06153/) (2021)
- [Oracle-Efficient Differentially Private Learning with Public Data](https://mlsanity.com/paper/2402.09483/) (2024)
- [Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning](https://mlsanity.com/paper/2404.03774/) (2024)
- [Tabular Data Synthesis with Differential Privacy: A Survey](https://mlsanity.com/paper/2411.03351/) (2024)
- [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)
- [A Unified View of Differentially Private Deep Generative Modeling](https://mlsanity.com/paper/2309.15696/) (2023)
- [A Simple and Practical Method for Reducing the Disparate Impact of Differential Privacy](https://mlsanity.com/paper/2312.11712/) (2023)
- [A Study on Training and Developing Large Language Models for Behavior Tree Generation](https://mlsanity.com/paper/2401.08089/) (2024)
- [Private Regression via Data-Dependent Sufficient Statistic Perturbation](https://mlsanity.com/paper/2405.15002/) (2024)
- [dpmm: Differentially Private Marginal Models, a Library for Synthetic Tabular Data Generation](https://mlsanity.com/paper/2506.00322/) (2025)
- [Rejoinder: Gaussian Differential Privacy](https://mlsanity.com/paper/2104.01987/) (2021)
- [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)

## Abstract (arXiv)

We present three new algorithms for constructing differentially private synthetic data---a sanitized version of a sensitive dataset that approximately preserves the answers to a large collection of statistical queries. All three algorithms are oracle-efficient in the sense that they are computationally efficient when given access to an optimization oracle. Such an oracle can be implemented using many existing (non-private) optimization tools such as sophisticated integer program solvers. While the accuracy of the synthetic data is contingent on the oracle's optimization performance, the algorithms satisfy differential privacy even in the worst case. For all three algorithms, we provide theoretical guarantees for both accuracy and privacy. Through empirical evaluation, we demonstrate that our methods scale well with both the dimensionality of the data and the number of queries. Compared to the state-of-the-art method High-Dimensional Matrix Mechanism citeMcKennaMHM18, our algorithms provide better accuracy in the large workload and high privacy regime (corresponding to low privacy loss varepsilon).