PaperlayerView exact revision on arXiv

Source-linked AI summary

Winning the NIST Contest: A scalable and general approach to differentially private synthetic data

Ryan McKenna, Gerome Miklau, Daniel Sheldon

arXiv:2108.04978v1cs.CR

TL;DR

Privacy concerns make data sharing difficult, while synthetic data requires formal privacy guarantees and scalable reconstruction. The paper proposes a three-step marginal-based framework centered on Private-PGM, and reports that MST works comparably to the winning NIST-MST without public provisional data. The framework is presented as a reusable basis for future differentially private synthetic-data mechanisms.

  • Problem

    Privacy-preserving synthetic data needs a formal privacy standard and methods that can generate useful data while scaling beyond high-dimensional reconstruction challenges.

  • Method

    The approach selects low-dimensional marginals, measures them privately, and uses Private-PGM to estimate a high-dimensional distribution and generate synthetic data.

  • Results

    MST performs comparably to NIST-MST without public provisional data; its difference was at most 0.01 for every metric and privacy budget evaluated.

  • Takeaways & Limitations

    Private-PGM lets mechanism designers focus on selecting statistics while providing a reusable post-processing component for differentially private synthetic data.

  • Takeaways & Limitations

    The approach assumes measured statistics depend on low-dimensional marginals, and its privacy-noise calibration reflects competition-era accounting choices.

Abstract

from arXiv · show

We propose a general approach for differentially private synthetic data generation, that consists of three steps: (1) select a collection of low-dimensional marginals, (2) measure those marginals with a noise addition mechanism, and (3) generate synthetic data that preserves the measured marginals well. Central to this approach is Private-PGM, a post-processing method that is used to estimate a high-dimensional data distribution from noisy measurements of its marginals. We present two mechanisms, NIST-MST and MST, that are instances of this general approach. NIST-MST was the winning mechanism in the 2018 NIST differential privacy synthetic data competition, and MST is a new mechanism that can work in more general settings, while still performing comparably to NIST-MST. We believe our general approach should be of broad interest, and can be adopted in future mechanisms for synthetic data generation.

1. Introduction

Differentially private synthetic data addresses privacy-constrained data sharing through a modular three-step framework: select marginals, measure them privately, and generate data preserving those measurements. NIST-MST won the 2018 NIST competition, while MST removes reliance on public provisional data and performs comparably.

  • Motivation: Privacy concerns constrain enterprise data sharing, motivating differentially private synthetic data as a formal privacy-preserving alternative.Synthetic data can support existing analytics and machine-learning workflows while protecting the original data.
  • Mechanisms: NIST-MST was the winning entry in the third round of the 2018 NIST Differential Privacy Synthetic Data Competition.The paper presents it as an instance of the general template for designing practical mechanisms.
  • General framework: The framework selects low-dimensional queries, measures them with the Gaussian mechanism, and uses Private-PGM to generate synthetic data preserving the noisy measurements.Query selection may be manual or algorithmic, and selected queries determine which statistics the synthetic data preserves accurately.
  • General framework: Private-PGM addresses synthetic-data reconstruction and high-dimensional scaling when the measured statistics depend only on low-dimensional marginals.This lets mechanism designers focus primarily on choosing which statistics to measure.
  • Mechanisms: MST avoids requiring public provisional data by using part of the privacy budget for private measurement selection and performs comparably to NIST-MST.The variant is intended for settings where high-quality provisional data is unavailable.

2. Background

The paper models a sensitive dataset as a finite-domain table and represents low-dimensional structure with marginals. Differential privacy is established through Gaussian and Exponential mechanisms, with RDP used to analyze repeated adaptive applications and translate guarantees to (ϵ, δ)-DP.

  • Data and privacy model: The input is a single table of records with potentially sensitive information, finite attribute domains, and a synthetic output satisfying (ϵ, δ)-differential privacy.The full domain is the Cartesian product of the attribute domains.
  • Marginals: A marginal counts occurrences of every combination of values for a selected subset of attributes, capturing low-dimensional structure in a high-dimensional distribution.The algorithms privately measure selected marginals and use them to construct synthetic data.
  • Data and privacy model: Differential privacy bounds how much one individual can affect an algorithm’s output by comparing outputs on datasets differing by one record.The paper defines neighboring datasets through adding or removing a single record.
  • Privacy mechanisms: The Gaussian mechanism adds Gaussian noise to vector-valued queries, while the Exponential Mechanism selects candidates according to a quality score.The algorithms use repeated applications of these mechanisms to achieve privacy.
  • Privacy accounting: RDP provides the framework for analyzing repeated adaptive Gaussian and Exponential mechanisms and translating the resulting guarantee into (ϵ, δ)-DP.The analysis uses sensitivity, adaptive composition, and an RDP-to-DP conversion.
  • Privacy accounting: Every marginal has L2 sensitivity 1, because one individual contributes to only one cell of its output vector.This sensitivity supports the privacy analysis of marginal measurements.

3. Competition setup

The 2018 competition evaluated differentially private synthetic data mechanisms on census data across multiple privacy levels and utility criteria. Its metrics tested preservation of 3-way marginals, high-order conjunctions, and an income- and gender-related statistic.

  • Competition format: The competition focused on the third of three rounds, which increased in complexity and required contestants to design a differentially private synthetic-data mechanism.Competitors had approximately one month and received a provisional dataset, domain information, evaluation code, and a baseline.
  • Data: Algorithms were evaluated on 1940 U.S. decennial census data, with public provisional data from Colorado and private holdout data from another state.The holdout state was unknown to competitors during the competition.
  • Evaluation: Scores averaged normalized performance across three equally weighted metrics and privacy levels ϵ = 0.3, 1.0, 8.0 with δ ≈2 · 10^-12.Computational efficiency was not included in the score.
  • Evaluation metrics: The high-order conjunction metric evaluated 300 random conjunctions over randomly sampled attribute sets and domain subsets.The expected sampled attribute-set size was approximately 10.
  • Evaluation metrics: The third metric assessed income inequality and gender wage-gap statistics by city, effectively requiring accurate preservation of the marginal on (SEX,CITY,INCWAGE).Unlike the first two metrics, this metric required preserving one marginal well.

4. Overview of Measurement and Inference with Private-PGM

The framework selects marginals, measures them privately, and uses Private-PGM to infer a distribution and generate synthetic data that preserves measured marginals. Private-PGM reduces inconsistency and error, estimates unmeasured marginals without additional privacy cost, and supports efficient inference through a graphical-model representation.

  • The framework selects marginals, measures them with Gaussian noise, and uses Private-PGM to generate synthetic data preserving the measured marginals.The measurement procedure records noisy marginal answers and associated metadata for Private-PGM post-processing.
  • Private-PGM infers a full data distribution from noisy marginal measurements, producing mutually consistent query answers even when the measurements conflict.It uses a compact graphical-model representation rather than explicitly optimizing over the full exponential-size distribution.
  • The optimization has an optimum represented by a graphical model whose factors correspond to the measured attribute sets, reducing inference to a lower-dimensional parameter vector.A proximal algorithm solves the reduced problem through repeated marginal-inference computations.
  • Generating synthetic data: Private-PGM generates synthetic data whose marginals closely preserve the model marginals, more closely than i.i.d. sampling in the described example.The model marginals contain fractional counts, whereas the generated synthetic data has integer counts.
  • Reducing error on measured marginals: Private-PGM can reduce error in measured marginals by combining noisy information into a cohesive estimate; one example reports L1 distances of about 213 and 272 versus 251 and 295 for noisy marginals.The estimated marginals also agree on the total count, reporting 436.873.
  • Estimating unmeasured marginals: Private-PGM estimates unmeasured marginals without spending additional privacy budget, with one reported normalized L1 error of 0.135.It uses the inferred distribution to answer queries that were not measured directly.

5. Algorithm Description

NIST-MST measures carefully selected low-dimensional marginals with the Gaussian mechanism and uses Private-PGM to generate synthetic data consistent with noisy measurements. Its design combines domain compression, data transformations, and provisional-data-driven marginal selection.

  • Core mechanism: NIST-MST measures selected 1-, 2-, and 3-way marginals with the Gaussian mechanism, then post-processes them with Private-PGM to obtain synthetic data.The resulting synthetic data is designed to be most consistent with the measured marginals.
  • Privacy calibration: Privacy calibration solves for Gaussian noise σ under the composed privacy analysis, with the contest using a moments-accountant minimization over α = 1, ..., 512.The paper notes that later analytic Gaussian calibration could typically reduce σ by 10 to 20 percent.
  • Preprocessing: Domain compression uses IPUMS documentation to reduce possible values, improving Private-PGM efficiency and preventing out-of-domain synthetic tuples.For EDUC, the domain is reduced from 100 to 13 possible values.
  • Preprocessing: NIST-MST transforms large-domain VALUEH and INCWAGE attributes before synthesis to make their domains more manageable.VALUEH is compressed to 5003 values while covering about 99.7% of observed values; INCWAGE is truncated above 5000, covering over 99.95% of provisional records before further transformation.
  • Marginal selection: The algorithm first answers all 1-way marginals, then selects 2- and 3-way marginals whose measurements determine which statistics the synthetic data preserves.Selection uses a provisional dataset rather than the sensitive dataset and is based on correlations represented by mutual information.
  • Marginal selection: NIST-MST constructs a maximum spanning tree from attribute correlations, adds specially weighted edges, and selects further marginals while retaining a tractable model structure.The selection procedure adds 2-way marginals for tree edges and uses additional structure for higher-order marginals.

6. Extensions

MST extends NIST-MST beyond competition-specific preprocessing and public provisional data by privately selecting correlated marginals from the sensitive dataset. It allocates privacy budget between selection and measurement while retaining differential privacy guarantees and comparable performance to NIST-MST.

  • Generalization: MST removes NIST-MST’s census-specific transformations and replaces provisional-data-based selection with a differentially private procedure using the sensitive dataset.This broadens the mechanism to settings without suitable public provisional data.
  • Privacy allocation: MST allocates 1/3 of the RDP budget to measurement selection and 2/3 to measuring the selected marginals.Privacy follows by adaptive composition.
  • Private selection: The private selection algorithm seeks attribute pairs forming a maximum spanning tree by using low-sensitivity mutual-information weights and the exponential mechanism.The exponential mechanism replaces the non-private choice of the highest-weight edge.
  • Private selection: MST can include an initial set of important attribute pairs before constructing a maximum spanning tree around them.This provides flexibility when particular marginals should be preserved even if they are not selected by the default procedure.
  • Privacy guarantee: Algorithm 6 satisfies (α, αρ)-RDP for all α ≥ 1.This is the stated privacy guarantee for the private measurement-selection algorithm.

7. Experiments

The experiments show that NIST-MST was the strongest contest submission across most metrics, while MST remained nearly as effective without public provisional data. The results also indicate that measurement selection and evaluation-aware design strongly influenced performance.

  • NIST-MST consistently performed best among contest submissions for most metrics and privacy budgets.
  • NIST-MST outperformed DPSyn on 3-way marginals and high-order conjunctions but performed slightly worse on income inequality.
  • NIST-MST and DPSyn scored well on income inequality, suggesting that designing mechanisms around the evaluation criteria contributed to their superior performance.
  • MST performed comparably to NIST-MST without relying on provisional data, with performance differences of at most 0.01 for every evaluated metric and privacy budget.
  • At ϵ = 0.3, MST achieved a smaller overall score than NIST-MST and would have placed first overall if submitted in the competition.
  • Future work could adaptively select the number of measured marginals according to the privacy budget and available data.

8. Related Work

Prior work includes computationally impractical database mechanisms, marginal-based methods, GANs, and alternative evaluation measures. The paper distinguishes its approach through Private-PGM’s principled use of noisy measurements and its applicability to high-dimensional settings.

  • The small database mechanism is impractical because enumerating all fixed-size datasets causes a combinatorial explosion.
  • Several marginal-based methods follow the select-measure-reconstruct template, but Private-PGM resolves measurement inconsistencies and uses all available noisy marginals to improve utility.
  • GAN-based approaches were used by two NIST competition teams but were generally not competitive with marginal-based methods.
  • Synthetic-data quality can be assessed through distributional similarity, machine-learning efficacy, and other measures, with the appropriate choice depending on the data and its use cases.
  • Workload-adaptive mechanisms generally struggle with high-dimensional domains, although combining them with Private-PGM can improve scalability and utility.

9. Conclusions

The paper presents NIST-MST and MST as strong instances of a Private-PGM-centered framework for differentially private synthetic data. It concludes that the framework can support future mechanisms, while the broader problem remains unsolved.

  • NIST-MST won the NIST differential privacy synthetic data competition, while MST works almost as well without public provisional data.
  • Private-PGM lets mechanism designers focus on measurement selection rather than post-processing noisy measurements into synthetic data while extracting utility.
  • The framework appears reusable: both first- and second-place teams in the NIST 2020 Temporal Map Challenge used Private-PGM for post-processing while developing new measurement-selection techniques.
  • The paper states that differentially private synthetic data remains far from solved despite these state-of-the-art mechanisms.

Appendix A. Supplementary Material

The supplementary material gives implementation and privacy-accounting details for MST, synthetic-data generation, transformations, and an additional comparison of measurement selection. It also records the formal privacy guarantee and supporting symbolic calculations.

  • MST divides its RDP budget across measurement-selection and other algorithmic steps, with noise calibration derived from the target (ϵ, δ)-DP guarantee.
  • The entire algorithm satisfies ρ-RDP by three-fold composition and converts this guarantee to (ϵ, δ)-DP.
  • The appendix includes sympy code supporting the proof of Theorem 2 and compares marginals selected from public versus sensitive data under different privacy budgets.
  • The synthetic-data generation procedures construct columns from graphical-model fractional counts and assemble them into a dataset.
  • Supplementary algorithms include transformations between sensitive-data attributes and reverse transformations used in the data-processing pipeline.
Loading 2108.04978v1…