A simple and practical algorithm for differentially private data release

Abstract

We present new theoretical results on differentially private data release useful with respect to any target class of counting queries, coupled with experimental results on a variety of real world data sets. Specifically, we study a simple combination of the multiplicative weights approach of [Hardt and Rothblum, 2010] with the exponential mechanism of [McSherry and Talwar, 2007]. The multiplicative weights framework allows us to maintain and improve a distribution approximating a given data set with respect to a set of counting queries. We use the exponential mechanism to select those queries most incorrectly tracked by the current distribution. Combing the two, we quickly approach a distribution that agrees with the data set on the given set of queries up to small error. The resulting algorithm and its analysis is simple, but nevertheless improves upon previous work in terms of both error and running time. We also empirically demonstrate the practicality of our approach on several data sets commonly used in the statistical community for contingency table release.

rewritten, with much more extensive experimental validation than the previous version

References in corpus (1)

• Efficient Batch Query Answering Under Differential Privacy

Cited by in corpus (63)

• Differential Privacy: An Economic Method for Choosing Epsilon
• Extremal Mechanisms for Local Differential Privacy
• How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy
• Generalized Gaussian Mechanism for Differential Privacy
• Privacy-preserving Artificial Intelligence Techniques in Biomedicine
• The Geometry of Differential Privacy: the Sparse and Approximate Cases
• Proving differential privacy in Hoare logic
• Comparative Study of Differentially Private Data Synthesis Methods
• DataLens: Scalable Privacy Preserving Training via Gradient Compression and Aggregation
• Proving Differential Privacy with Shadow Execution
• Privately Solving Linear Programs
• MVG Mechanism: Differential Privacy under Matrix-Valued Query
• Differential Privacy for the Analyst via Private Equilibrium Computation
• Differentially Private Synthetic Data: Applied Evaluations and Enhancements
• On the Power of Multiple Anonymous Messages
• PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions
• Differentially Private Bayesian Programming
• DP-MERF: Differentially Private Mean Embeddings with Random Features for Practical Privacy-Preserving Data Generation
• Privacy, ethics, and data access: A case study of the Fragile Families Challenge
• Permute-and-Flip: A new mechanism for differentially private selection
• Leveraging Public Data for Practical Private Query Release
• Differentially Private False Discovery Rate Control
• Sub-Linear Privacy-Preserving Near-Neighbor Search
• Differentially Private Query Release Through Adaptive Projection
• Private Post-GAN Boosting
• Anonymizing Data for Privacy-Preserving Federated Learning
• The future of statistical disclosure control
• The Podium Mechanism: Improving on the Laplace and Staircase Mechanisms
• A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy
• Differentially Private Learning of Undirected Graphical Models using Collective Graphical Models
• Statistical Properties of Sanitized Results from Differentially Private Laplace Mechanism with Univariate Bounding Constraints
• Principled Evaluation of Differentially Private Algorithms using DPBench
• Does Differentially Private Synthetic Data Lead to Synthetic Discoveries?
• PEARL: Data Synthesis via Private Embeddings and Adversarial Reconstruction Learning
• An Uncertainty Principle is a Price of Privacy-Preserving Microdata
• The Price of Differential Privacy under Continual Observation
• Quantum algorithms for spectral sums
• Synthetic Tabular Data: Methods, Attacks and Defenses
• Model-based Differentially Private Data Synthesis and Statistical Inference in Multiply Synthetic Differentially Private Data
• APEx: Accuracy-Aware Differentially Private Data Exploration
• Differentially Private $k$-Means Clustering
• Utility-aware Privacy-preserving Data Releasing
• Optimizing Fitness-For-Use of Differentially Private Linear Queries
• Turbo: Effective Caching in Differentially-Private Databases
• Privacy-preserving Data Sharing on Vertically Partitioned Data
• One Step to Efficient Synthetic Data
• SoK: Chasing Accuracy and Privacy, and Catching Both in Differentially Private Histogram Publication
• Free Gap Information from the Differentially Private Sparse Vector and Noisy Max Mechanisms
• TableGAN-MCA: Evaluating Membership Collisions of GAN-Synthesized Tabular Data Releasing
• AHEAD: Adaptive Hierarchical Decomposition for Range Query under Local Differential Privacy
• Relaxed Marginal Consistency for Differentially Private Query Answering
• A One-Pass Private Sketch for Most Machine Learning Tasks
• Answering Multi-Dimensional Range Queries under Local Differential Privacy
• Marginal Release Under Local Differential Privacy
• Improving Utility of Differentially Private Mechanisms through Cryptography-based Technologies: a Survey
• DPSyn: Experiences in the NIST Differential Privacy Data Synthesis Challenges
• Optimizing Batch Linear Queries under Exact and Approximate Differential Privacy
• Not All Attributes are Created Equal: $d_{\mathcal{X}}$-Private Mechanisms for Linear Queries
• A Minimax Distortion View of Differentially Private Query Release
• Differentially Private Data Releasing for Smooth Queries with Synthetic Database Output
• Efficient Privacy-Preserved Processing of Multimodal Data for Vehicular Traffic Analysis
• Differentially Private Data Release via Statistical Election to Partition Sequentially
• On the Relation Between Identifiability, Differential Privacy and Mutual-Information Privacy