AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data

Ryan McKenna; Brett Mullins; Daniel Sheldon; Gerome Miklau

Source-linked AI summary

AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data

Ryan McKenna, Brett Mullins, Daniel Sheldon, Gerome Miklau

arXiv:2201.12677v2Jan 29, 2022cs.DB

TL;DR

Differentially private synthetic data must provide useful answers for chosen workloads despite accuracy limits and the difficulty of detecting inaccurate outputs. AIM adaptively selects and measures workload-relevant queries, generates data from the noisy measurements, and adds high-probability error bounds. It consistently outperforms prior mechanisms while limiting its guarantees to marginal L1 error rather than individual marginal cells.

Problem
Existing workload-aware synthetic-data mechanisms can remain inaccurate on target workloads, while users lack reliable ways to detect that inaccuracy.
Method
AIM iteratively selects measurements using a score combining approximation quality, expected improvement, workload relevance, and privacy budget, then uses noisy measurements to generate synthetic data.
Results
AIM consistently outperforms prior work, improving error over the next-best mechanism by 1.6× on average and up to 5.7× in some cases.
Takeaways & Limitations
AIM combines workload-aware utility improvements with analytic error estimates that can inform confidence bounds and how much generated data should be trusted.
Takeaways & Limitations
The guarantees cover L1 error for each marginal but do not guarantee error for individual marginal cells.

Abstract

from arXiv · show

We propose AIM, a new algorithm for differentially private synthetic data generation. AIM is a workload-adaptive algorithm within the paradigm of algorithms that first selects a set of queries, then privately measures those queries, and finally generates synthetic data from the noisy measurements. It uses a set of innovative features to iteratively select the most useful measurements, reflecting both their relevance to the workload and their value in approximating the input data. We also provide analytic expressions to bound per-query error with high probability which can be used to construct confidence intervals and inform users about the accuracy of generated data. We show empirically that AIM consistently outperforms a wide variety of existing mechanisms across a variety of experimental settings.

1 INTRODUCTION

Differentially private synthetic data must be tailored to useful workloads because privacy limits accuracy, while existing workload-aware methods may still be inaccurate and provide no way to detect that. AIM addresses these gaps with adaptive query selection, analytic error bounds, and strong empirical performance.

1 INTRODUCTION: Existing workload-aware methods can fail even on their target workloads and offer users no way to detect inaccurate synthetic data.These limitations leave differentially private synthetic data generation practically unresolved.
1 INTRODUCTION: AIM selects, privately measures, and synthesizes data from queries chosen through an iterative, greedy procedure.The select-measure-generate paradigm uses Private-PGM to combine noisy measurements into a consistent representation.
1 INTRODUCTION: AIM’s selection score accounts for current approximation quality, expected improvement, workload relevance, and available privacy budget.Additional techniques include adaptive rounds and budgets, intelligent initialization, and expanded candidate sets.
1 INTRODUCTION: The paper provides high-probability per-query error bounds that support confidence bounds and help users judge which queries the synthetic data supports well.Unlike worst-case a priori bounds, the proposed analysis reflects AIM’s execution on the input data without additional privacy budget.
1 INTRODUCTION: AIM consistently outperforms prior mechanisms, reducing error by 1.6× on average and up to 5.7× in some cases.The evaluation compares AIM with a wide range of existing mechanisms.

2 BACKGROUND

The paper defines datasets, marginals, workloads, error, and differential privacy before describing Private-PGM as the optimization and synthesis component used with noisy marginal measurements.

2 BACKGROUND: A marginal is a histogram counting occurrences of attribute combinations, providing low-dimensional structure from high-dimensional data.The marginal query computes this count vector from the dataset.
2 BACKGROUND: A workload is a weighted collection of marginal queries that specifies which query answers the synthetic data should preserve.The paper focuses on weighted marginal query workloads and evaluates utility using workload error.
2 BACKGROUND: Workload error is measured as normalized L1 distance between true and synthetic workload query answers.The paper also reports supplemental L2 and L∞ evaluations.
2 BACKGROUND: Differential privacy bounds the effect of adding or removing one record, with sensitivity measuring the maximum L2 output change between neighboring datasets.Any marginal query has L2 sensitivity 1 because one individual contributes to only one output cell.
2 BACKGROUND: Private-PGM estimates a distribution that best explains noisy marginals and then generates synthetic tabular data from the estimated model.Its optimization exploits marginal structure, while junction-tree size governs computational complexity and model-capacity constraints.

3 PRIOR WORK ON SYNTHETIC DATA

Prior synthetic-data mechanisms use the select-measure-generate framework but differ in query selection, privacy mechanisms, and data-generation methods. The section organizes these mechanisms by workload, data, budget, and efficiency awareness, identifying gaps addressed by AIM.

3.1 The Select-Measure-Generate Paradigm: Synthetic-data mechanisms select queries, measure them privately, and generate data consistent with noisy measurements.The framework includes iterative methods that alternate between selection and measurement.
3.1 The Select-Measure-Generate Paradigm: MWEM+PGM iteratively selects poorly approximated marginals, measures them with Gaussian noise, and updates a Private-PGM distribution.It serves as both a concrete example of the framework and the starting point for AIM.
3.2 Basic Elements of a Good Mechanism: Good mechanisms measure entire marginals, prefer Gaussian noise when advantageous, and allocate most privacy budget to measurement rather than selection.The section also discusses unbounded differential privacy as a lower-noise alternative under its stated assumptions.
3.3 Taxonomy of Existing Mechanisms: Existing mechanisms vary in workload, data, budget, and efficiency awareness, while AIM is the only listed mechanism aware of all four factors.The taxonomy cautions that more awareness markers do not necessarily imply better performance.
3.3 Taxonomy of Existing Mechanisms: Private-PGM-based mechanisms need candidate-selection safeguards because some selected marginals can produce intractable junction-tree models.Several mechanisms include tractability heuristics, whereas Gaussian, HDMM+PGM, and MWEM+PGM do not.

4 AIM: AN ADAPTIVE AND ITERATIVE MECHANISM FOR SYNTHETIC DATA

AIM improves the select-measure-generate paradigm through adaptive marginal selection, workload-aware scoring, adaptive budget allocation, candidate restrictions, and model-capacity safeguards. Its privacy analysis establishes ρ-zCDP while its execution adapts the number of rounds to the available budget.

4 AIM: An Adaptive and Iterative Mechanism for Synthetic Data: AIM modifies MWEM+PGM with adaptive selection, budget allocation, candidate construction, and privacy-preserving generation using Private-PGM.The section presents AIM as Algorithm 2 and analyzes its design decisions and privacy.
Intelligent Initialization: AIM initializes an independent model from privately measured one-way marginals before iterative selection and measurement.This preserves one-way marginals well and supports estimating higher-order marginals under an independence assumption.
New Candidates: AIM restricts candidates to the workload’s downward closure and filters selections that would exceed a prescribed model-capacity limit.Lower-dimensional marginals can offer better signal-to-noise ratios, while the capacity filter supports predictable memory and runtime.
Better Selection Criteria: AIM scores candidate marginals by current estimation error, expected improvement, workload relevance, and available privacy budget.The workload weight reflects overlap with workload marginals and changes the score sensitivity used by the exponential mechanism.
Adaptive Rounds and Budget Split: AIM adapts per-round privacy spending through annealing, eliminating the need to specify the number of rounds in advance.When little information is learned, it increases the per-round privacy budget and reduces noise; larger budgets generally permit more rounds.
Privacy Analysis: For any T≥d, α∈(0,1), and ρ≥0, AIM satisfies ρ-zCDP and terminates without exceeding its available privacy budget.The privacy proof accounts for initialization, exponential-mechanism selection, Gaussian measurement, and budget-filter logic.

5 UNCERTAINTY QUANTIFICATION

AIM quantifies uncertainty using its private noisy measurements and selected queries without additional privacy budget. It derives high-probability bounds for supported and unsupported marginals and translates those bounds into confidence intervals for synthetic-data error.

5 Uncertainty Quantification: AIM’s uncertainty method uses noisy marginals and selected queries to bound workload-marginal error without additional privacy budget.The guarantees apply to marginals in the workload’s downward closure.
The Easy Case: Supported Marginal Queries: For supported marginals, AIM combines independent unbiased estimates from selected marginals into a weighted-average estimator with analytically bounded error.The estimator’s error is related to synthetic-data error through the triangle inequality.
The Hard Case: Unsupported Marginal Queries: For unsupported marginals, AIM bounds error by relating unselected queries to selected queries, whose error can be directly bounded.This hard case is needed because unsupported marginals lack the same unbiased estimates available for selected or supported queries.
Putting it Together: The resulting bounds can be computed from AIM’s private outputs and expressed as one-sided confidence intervals that contain true error with high probability.The bounds can also be extended from intermediate models to an arbitrary synthetic dataset.
Putting it Together: A valid bound must use one selected round rather than choosing the smallest bound across rounds after observing the results.Using the minimum over rounds would invalidate the guarantee.
Putting it Together: The bounds may be looser for supported marginals when the unsupported-marginal guarantee is used, and the synthetic dataset can have lower error than the estimator without a clear corresponding guarantee.The latter gap is identified as a limitation of the analysis rather than a claim about the mechanism’s realized error.

6 EXPERIMENTS

Across diverse datasets, workloads, and privacy levels, AIM generally achieves the lowest workload error among evaluated mechanisms. Ablations show that its adaptive selection and budget allocation, Private-PGM generation, and uncertainty bounds contribute to performance and practical error assessment.

6.2 Experimental Results: Across all datasets and privacy regimes, AIM improves over PrivMRF by 1.3× on average and over other baselines by factors ranging from 1.5× to 5.6×.The largest average improvement is 5.6× over RAP; extreme-case improvements reach 118× over MST.
6.2 Experimental Results: AIM is best in 76% of settings and in 100% of settings with 𝜖≥1.0, while MWEM+PGM is best in 18% and GEM in 5%.These results cover six datasets and nine privacy parameters.
6.3 Ablations: AIM’s adaptive rounds and budget split improve error by 1.48×, its new selection criteria by 1.37×, and Private-PGM generation by 2.36× on average.The benefits of adaptive rounds plus budget splitting and Private-PGM increase with 𝜖.
6.3 Ablations: All tested AIM elements have statistically positive effects, with combined p-values ranging from 10−22 for initialization to 10−166 for adaptive rounds and budget splitting.The analysis aggregates 162 p-values using Stouffer’s Z-score method.
6.3 Ablations: Larger AIM model capacities improve utility but increase runtime.
6.4 Uncertainty Quantification: The uncertainty bounds always exceeded observed error in the reported evaluation, with median bound-to-error ratios of 4.4 for supported and 8.3 for unsupported marginals.Supported marginals also had lower errors, lower bounds, and tighter bounds than unsupported marginals.

7 DISCUSSION AND LIMITATIONS

AIM improves differentially private synthetic data generation while providing uncertainty guarantees, but its current scope excludes several workload and data settings.

AIM consistently and significantly outperformed competing mechanisms while its uncertainty guarantees identify which queries synthetic data preserves well.The paper frames these guarantees as important for downstream analyses.
Handling More General Workloads: AIM currently focuses on weighted marginal workloads, leaving more general linear, machine-learning, and nonlinear workloads as open problems.Existing alternatives can handle some broader linear workloads, but the paper identifies substantial room for improvement.
Handling Mixed Data Types: Numerical attributes must be discretized, and discretization quality can significantly affect generated-data quality because AIM assumes discrete finite-domain input.The experiments discretize numerical attributes into 32 equal-width bins.
Uncertainty Quantification Guarantees: The uncertainty guarantees cover L1 error for marginals but not errors in individual marginal cells.Finer-grained cell-level guarantees remain a future technical challenge.
Small Workloads: AIM may be less suitable for small workloads, where Gaussian+PGM can perform better because AIM need not spend privacy budget selecting queries.
High-cardinality attributes: AIM scalability depends on attribute domain sizes, and high-cardinality datasets may require special treatment for sparse marginals.The evaluated datasets mostly had attribute domains of size 50 or less.

D.1 Experiments

Structural-zero constraints improve AIM’s average workload error on the fire dataset, although the improvement is not universal across privacy levels.

On average, imposing structural-zero constraints improves AIM’s performance on the fire dataset, but not for every tested epsilon.The experiment used nine attribute pairs containing 2,696 structural-zero constraints.

E RUNTIME EXPERIMENTS

AIM’s runtime grows sharply with the privacy parameter because budget awareness enables larger marginals and more rounds, while deployment runtime depends on computational resources.

Runtime increases drastically with epsilon because AIM selects larger marginals and runs more rounds when more privacy budget is available.The runtime experiment concerns AIM on the all-3way workload.
The JT-SIZE constraint is essential at large epsilon to prevent excessive memory use and allow AIM to terminate.For small epsilon, the constraint is inactive and could be removed without changing AIM’s behavior.
Runtime measurements used one compute-cluster core with 4 GB of memory and a 2.4 GHz CPU, while better hardware could significantly reduce runtime.

G TUNING MODEL CAPACITY

AIM trades runtime for lower workload error as model capacity increases, with diminishing returns and a policy-dependent choice of capacity.

AIM's 80 MB default capacity can be adjusted to trade accuracy against runtime, with no single capacity sweet spot.The authors frame the choice of model capacity as a policy decision.
Runtime increases with model capacity, while workload error decreases; beyond 20 MB, both level off when 𝜖=0.1.At 𝜖=0.1, the capacity constraint is inactive because AIM already favors small marginals under a small privacy budget.
13% lower error requires increasing model capacity to 1.28 GB and waiting 7 days, compared with the default capacity's 9-hour runtime.Reducing capacity to 5 MB increases error by about 75% but takes less than one hour.

H ADAPTIVE ROUNDS EXPERIMENTS

Adaptive rounds with budget splitting outperform fixed-round alternatives on average, while hindsight tuning offers only a small additional utility gain at substantial privacy cost.

The experiments compare fixed-round alternatives against adaptive rounds and budget splitting, using model-capacity-related comparisons as additional experimental context.The supplied figure captions identify experiments on adaptive rounds and model capacity, but do not report additional figure outcomes.
Adaptive rounds with budget splitting improve utility by 1.48× over the default number of rounds on average.Fixed-round alternatives achieved 1.06×, 1.17×, and 1.27× improvements for T=64, 128, and 256, respectively.
Choosing the best fixed round count in hindsight is only 1.1× better than adaptive rounds with budget splitting on average.Finding that setting in practice would require spending significant privacy budget on hyper-parameter optimization.

I SENSITIVITY TO HYPER-PARAMETERS

Competing mechanisms' best round counts vary with privacy level, but default settings remain preferable to differentially private hyper-parameter optimization because its privacy cost outweighs the utility gain.

MWEM+PGM performs well with T=8 for 𝜖≤0.3 and with T∈{64, 75, 128} for 𝜖≥1, while T=16 incurs some loss.None of the mechanisms completed for 256 rounds; GEM and RAP also failed to complete at larger round counts under the time limits.
GEM performs well with T=32 for 𝜖≤0.1 and T∈{64, 75} for 𝜖≥0.32, with the default setting often best.Where the default is not optimal, it remains better than using a differentially private mechanism to optimize the hyper-parameter.
RAP follows the same trend: larger T works better for larger 𝜖, and smaller T works better for smaller 𝜖.
Default hyper-parameter settings are not hindsight-optimal, yet optimizing them does not improve utility enough to justify the privacy cost or change the main findings.Differentially private hyper-parameter selection incurs a multiplicative 3× cost to the privacy parameter.

J OTHER ERROR METRICS

AIM's performance under L2 and maximum-error metrics is broadly similar to its L1 performance, with dataset-specific exceptions.

The paper primarily evaluates mechanisms using the L1 workload error metric but also visualizes L2 and maximum error.
Under L2 error, AIM's relative performance is roughly unchanged across datasets, except that MWEM+PGM outperforms AIM on salary when 𝜖≤1.
AIM is often the best-performing mechanism under L∞ maximum error, although GEM outperforms it in some settings.

K RESULTS ON 2-WAY MARGINALS

On the all-2way workload, AIM consistently outperforms competing mechanisms, although Gaussian performs strongly at higher privacy budgets.

AIM consistently outperforms all competing mechanisms on the all-2way workload.Gaussian surpasses AIM at 𝜖=1 on the msnbc dataset, unlike its behavior on the other workloads.
Gaussian performs especially well for higher values of 𝜖 and on the msnbc dataset.
The all-2way workload contains all 2-way marginal queries and is smaller than the other evaluated workloads.Its smaller size reduces the noise required to measure every workload query.
Gaussian can achieve lower workload error than synthetic-data mechanisms but does not produce synthetic data.It therefore is unsuitable when synthetic data is required.