PaperlayerView exact revision on arXiv

Source-linked AI summary

A simple and practical algorithm for differentially private data release

Moritz Hardt, Katrina Ligett, Frank McSherry

arXiv:1012.4763v2cs.DS

TL;DR

Private data release must balance statistical usefulness with protection for individuals, while existing differentially private algorithms can add unacceptable noise. The paper presents MWEM, combining Multiplicative Weights with the Exponential Mechanism to select poorly tracked queries and update an approximating distribution. It reports substantial improvements over prior methods in error and practicality across several release tasks, while identifying settings where advanced query selection is unnecessary.

  • Problem

    Differentially private data release seeks useful statistics or synthetic data without exposing individual records, but existing algorithms can add unacceptable noise.

  • Method

    MWEM combines Multiplicative Weights updates with the Exponential Mechanism to select queries most incorrectly tracked by the current approximating distribution.

  • Results

    MWEM substantially improves experimental error over existing techniques across range queries, contingency-table release, and datacube release.

  • Takeaways & Limitations

    The algorithm offers a simple, broadly applicable way to produce high-fidelity differentially private synthetic data without requiring complicated knowledge of query structure.

  • Takeaways & Limitations

    At sufficiently high ε, judicious query selection is no longer required, so MWEM does not improve over more naive approaches in those regimes.

Abstract

from arXiv · show

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.

1. INTRODUCTION

The paper introduces MWEM, a simple differentially private synthetic-data algorithm that combines Multiplicative Weights with the Exponential Mechanism. It reports theoretical guarantees, empirical improvements across query-release tasks, and a scalable implementation for high-dimensional domains.

  • Contribution: The algorithm combines Multiplicative Weights updates with the Exponential Mechanism to select queries that the current approximation serves poorly.This approach improves the approximation using informative measurements rather than measuring every possible query.
  • Contribution: MWEM maintains a fractional weighting of the data domain that respects any set of linear queries, including counting queries.Its theoretical accuracy matches the best known, nearly optimal guarantees for differentially private counting-query release.
  • Empirical results: MWEM is evaluated on range queries, binary contingency-table release, and datacube release using prior work’s query classes and accuracy metrics.The experiments use a variety of real-world datasets and report often significant improvements in approximation quality.
  • Empirical results: Up to three orders of magnitude improvements in accuracy are reported for range queries across several datasets at fixed privacy parameters.The paper also reports improvements for every evaluated contingency-table benchmark and over specialized datacube algorithms.
  • Practical scope: Synthetic-data release preserves consistency of statistics and compatibility with downstream analyses that expect datasets as input.These properties motivate releasing synthetic data rather than only individual query answers.
  • Implementation: A scalable implementation processes datasets with thousands of attributes, corresponding to domains of size 2^1000.The implementation addresses the computational difficulty of synthetic-data generation, including cases with very large domains.

2. OUR APPROACH

MWEM combines the Exponential Mechanism with Multiplicative Weights to iteratively select poorly approximated queries, measure them privately, and refine a synthetic distribution. It provides strong formal guarantees, preserves differential privacy, and has practical improvements and scalable implementations despite worst-case computational hardness.

  • Algorithm: MWEM maintains an approximating distribution and repeatedly selects queries poorly served by it before improving the approximation using private measurements.The Exponential Mechanism selects queries, the Laplace Mechanism measures them, and Multiplicative Weights updates the distribution.
  • Privacy framework: Differential privacy requires randomized mechanisms to behave almost identically on datasets differing by one record, limiting disclosure of individual records.The paper distinguishes ε-differential privacy from (ε, δ)-differential privacy, with δ = 0 yielding ε-differential privacy.
  • Privacy mechanisms: The Exponential Mechanism privately selects among discrete alternatives using a quality score, while the Laplace Mechanism privately reports approximate sums by adding noise.The Exponential Mechanism favors higher-quality results exponentially; the Laplace Mechanism is more efficient for bounded sums.
  • Multiplicative Weights: Each Multiplicative Weights update reduces relative entropy by an additive (q(A) − q(B))^2 when the approximation and true distribution disagree on query q.The approximation is renormalized after scaling record weights.
  • Formal guarantees: MWEM satisfies ε-differential privacy and achieves the paper’s best-known theoretical accuracy guarantees for differentially private synthetic data release.The guarantees apply to linear-query sets and hold with high probability under the stated corollaries.
  • Improvements and variations: Practical variations improve performance without changing theoretical worst-case bounds, including adaptive selection of the iteration count T within a factor of two of optimal.The experiments use manually selected T rather than the adaptive procedure.

3. EXPERIMENTAL EVALUATION

The experiments evaluate MWEM across range queries, contingency-table release, and datacube release using several datasets and privacy settings. Across these tasks, MWEM often improves approximation quality, especially when selecting informative queries matters, but the advantage diminishes at sufficiently high ε.

  • Experimental scope: MWEM was evaluated on range queries, binary contingency-table release, and datacube release using varied datasets, query classes, and accuracy metrics.The study uses total squared error, relative entropy, and average absolute error across the three problem types.
  • 3.1 Range Queries: MWEM achieved lower error than the SVD lower bound in all four range-query datasets for sufficiently small ε.The comparison varies either the number of queries with ε fixed or ε with |Q| fixed, averaging five repetitions.
  • 3.1 Range Queries: The range-query improvement over the SVD bound was often more than one order of magnitude and reached up to three orders of magnitude.MWEM provides (ε, 0)-differential privacy, while the cited SVD bound uses an (ε, δ)-differential privacy guarantee with δ > 0.
  • 3.2 Contingency Tables: On small statistical benchmark datasets, selecting only informative queries substantially improved relative entropy over measuring all possible measurements.The heuristic MWEM approach often matched the good non-private relative entropy values reported by Fienberg et al.
  • 3.3.1 Experimental Results: For every dataset and query set, sufficiently high ε makes query selection unnecessary, so MWEM does not improve over more naive approaches in that regime.The benefit returns when the marginal dimension increases or ε decreases enough that many measurements are below the noise level.

4. A SCALABLE IMPLEMENTATION

The scalable implementation factorizes MWEM across independent attribute groups, replacing explicit exponential-domain computation with smaller component-wise computations. Experiments show that this preserves useful scaling behavior, while runtime depends on query evaluation and query-set complexity.

  • Scalable implementation: The explicit-domain approach can overwhelm even a large cluster because the domain remains exponential in the number of attributes.This motivates the factorized implementation.
  • Scalable implementation: MWEM can maintain its distribution implicitly from query history, substantially reducing memory use while retaining parallelizable query evaluation.The distribution is represented through recorded query measurements rather than explicitly enumerating the domain.
  • Scalable implementation: Partitioning attributes into disjoint groups makes the maintained distribution a product distribution when no query spans multiple groups.Each component uses only the relevant queries for its attribute group.
  • Scalable implementation: Component-wise summations reduce runtime from exponential in all attributes to a sum of exponentials over the attribute groups, except when attributes are fully entangled.Independent or irrelevant groups can therefore yield near-linear behavior in the number of attributes.
  • Scaling evaluation: Adding 50 attributes produced curves with shapes similar to the original experiment, indicating that MWEM can ignore irrelevant attributes, although the larger query set increased runtime.The query counts were (77 choose 3) versus (27 choose 3).
  • Scaling evaluation: For synthetic data, total runtime was dominated by evaluating queries against the private dataset, while factorized MWEM computation was essentially negligible.Even for 1000 binary attributes, MWEM logic took only 19 seconds.
  • Scaling evaluation: In the Adult experiment, each measurement and update took less than a second until measurement complexity increased, with MWEM complexity staying below |D1| = 227 and |D2| = 277.The original eight-attribute Adult dataset offered too little separation among components to show an improvement.

5. CONCLUSIONS

The authors conclude that MWEM combines high-fidelity differentially private release with a simple query-selection strategy. They argue that its simplicity and generality support practical use across varied data domains.

  • Conclusions: MWEM maintains high fidelity to protected source data while providing differential privacy with respect to records.Its theoretical analysis matches previous work, while experiments show substantial improvement in many settings.
  • Conclusions: Analysts need only enumerate measurements to preserve, avoiding specialized mathematical knowledge of linear algebra or the Hadamard transform.The authors connect this simplicity to broader use across data domains.

A. APPENDIX: PROOF OF THEOREM 2.2

The appendix proves MWEM’s maximum-error guarantee by combining near-optimal private query selection and noisy measurements with a potential-function analysis. The resulting bound follows by tracking decreases in relative entropy across iterations.

  • Proof strategy: The proof first bounds the quality of Exponential Mechanism selections and the error introduced by Laplace measurements across all iterations.A union bound gives failure probability at most 2T/|Q|^c for the generalized analysis.
  • Potential-function analysis: MWEM improves its approximation in rounds where the selected query exposes large disagreement between the current approximation and the private dataset.Relative entropy measures this improvement.
  • Potential-function analysis: The update ratio is exp(q_i(x)η_i)/β_i, with η_i = (m_i − q_i(A_i−1))/2n and β_i providing renormalization.This expression connects the noisy measurement to the multiplicative-weights update.
  • Error bound: Averaging the per-round potential decrease telescopes the relative-entropy terms, which are bounded by log(|D|)/T.This yields maxerr_i ≤ 2n(log(|D|)/T)^1/2 + 5 × adderr.
  • Error bound: Substituting adderr = 2T log |Q|/ε produces the theorem’s accuracy bound, with failure probability 1 − 2T/|Q|^c for arbitrary c > 0.The proof also uses the noisy-measurement bound |m_i − q_i(B)| ≤ adderr.
  • Implementation: The reference implementation alternates exponential-mechanism query selection, Laplace measurement, and multiplicative-weights updating.The code initializes a uniform approximation and records measurement pairs.
Loading 1012.4763v2…