mlsanityData to 7 Oct 2026

New Oracle-Efficient Algorithms for Private Synthetic Data Release

arXiv 2007.05453 ↗First posted 10 Jul 2020cs.LG cs.DS stat.MLcited by 43

Not on the map. Why?

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).

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 6; 2023: 13; 2024: 11; 2025: 5; 2026: 3.

43 papers.

Sort:

By area:

  1. 2023How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacycited by 150
  2. 2021Iterative Methods for Private Synthetic Data: Unifying Framework and New Methodscited by 58
  3. 2021Differentially Private Query Release Through Adaptive Projectioncited by 50
  4. 2021Leveraging Public Data for Practical Private Query Releasecited by 39
  5. 2023SoK: Privacy-Preserving Data Synthesiscited by 37
  6. 2022Private Synthetic Data for Multitask Learning and Marginal Queriescited by 35
  7. 2022Private Set Generation with Discriminative Informationcited by 34
  8. 2024Privacy-Preserving Instructions for Aligning Large Language Modelscited by 34
  9. 2023Generating Private Synthetic Data with Genetic Algorithmscited by 18
  10. 2023Graphical vs. Deep Generative Models: Measuring the Impact of Differentially Private Mechanisms and Budgets on Utilitycited by 13
  11. 2022dpart: Differentially Private Autoregressive Tabular, a General Framework for Synthetic Data Generationcited by 12
  12. 2024The Elusive Pursuit of Reproducing PATE-GAN: Benchmarking, Auditing, Debuggingcited by 12
31 more
  1. 2022Noise-Aware Statistical Inference with Differentially Private Synthetic Datacited by 9
  2. 2023Post-processing Private Synthetic Data for Improving Utility on Selected Measurescited by 9
  3. 2023Optimal Differentially Private Model Training with Public Datacited by 9
  4. 2024Privacy-preserving data release leveraging optimal transport and particle gradient descentcited by 8
  5. 2024Joint Selection: Adaptively Incorporating Public Information for Private Synthetic Datacited by 8
  6. 2024Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learningcited by 6
  7. 2024Tabular Data Synthesis with Differential Privacy: A Surveycited by 6
  8. 2021Relaxed Marginal Consistency for Differentially Private Query Answeringcited by 5
  9. 2024Oracle-Efficient Differentially Private Learning with Public Datacited by 5
  10. 2023A Unified View of Differentially Private Deep Generative Modelingcited by 4
  11. 2023A Simple and Practical Method for Reducing the Disparate Impact of Differential Privacycited by 4
  12. 2024A Study on Training and Developing Large Language Models for Behavior Tree Generationcited by 4
  13. 2024Private Regression via Data-Dependent Sufficient Statistic Perturbationcited by 4
  14. 2025The Importance of Being Discrete: Measuring the Impact of Discretization in End-to-End Differentially Private Synthetic Datacited by 4
  15. 2021Rejoinder: Gaussian Differential Privacycited by 2
  16. 2022Spending Privacy Budget Fairly and Wiselycited by 2
  17. 2022Private Synthetic Data with Hierarchical Structurecited by 2
  18. 2023ResidualPlanner+: a scalable matrix mechanism for marginals and beyondcited by 2
  19. 2024Differentially Private Synthetic Data Generation for Relational Databasescited by 2
  20. 2024Privacy without Noisy Gradients: Slicing Mechanism for Generative Model Trainingcited by 2
  21. 2025dpmm: Differentially Private Marginal Models, a Library for Synthetic Tabular Data Generationcited by 2
  22. 2023Differentially Private Algorithms for Synthetic Power System Datasetscited by 1
  23. 2023Private Synthetic Data Meets Ensemble Learningcited by 1
  24. 2026Rethinking Anonymity Claims in Synthetic Data Generation: A Model-Centric Privacy Attack Perspectivecited by 1
  25. 2023Coincidental Generationcited by 0
  26. 2023Partition-based differentially private synthetic data generationcited by 0
  27. 2025Understanding the Impact of Data Domain Extraction on Synthetic Data Privacycited by 0
  28. 2025Private Queries with Sigma-Countingcited by 0
  29. 2025Beyond One-Size-Fits-All: Neural Networks for Differentially Private Tabular Data Synthesiscited by 0
  30. 2026Fixed-Parameter Tractability of Private Synthetic Data Generationcited by 0
  31. 2026Differentially Private Paired Table-Image Multimodal Synthesiscited by 0