PaperlayerView exact revision on arXiv

Source-linked AI summary

Principled Evaluation of Differentially Private Algorithms using DPBench

Michael Hay, Ashwin Machanavajjhala, Gerome Miklau, Yan Chen, Dan Zhang

arXiv:1512.04817v1cs.DBcs.CR

TL;DR

Differentially private algorithms are increasingly complex and often data dependent, while existing evaluations do not adequately guide comparisons, parameter choices, or deployment across datasets. The paper introduces DPBENCH, a principled benchmark, and applies it to 15 algorithms on 27 datasets for 1- and 2-dimensional range queries. The study shows that scale and shape affect performance, resolves prior inconsistencies, and identifies practical evaluation and algorithm-selection challenges.

  • Problem

    Existing evaluations provide limited guidance because algorithm performance depends on dataset properties, studies have gaps and inconsistencies, and parameter choices, variability, and baselines are often insufficiently reported.

  • Method

    The paper proposes DPBENCH, a principled framework that tunes free parameters, measures error variability, compares algorithms with baselines, and evaluates range-query algorithms across datasets.

  • Results

    Across 1- and 2-dimensional range queries, DPBENCH shows that scale and shape affect algorithm error, resolves prior inconsistencies, and identifies state-of-the-art algorithms for their datasets.

  • Takeaways & Limitations

    Algorithm performance should be interpreted in context, because data-dependent methods can outperform alternatives at some scales yet underperform them at others.

  • Takeaways & Limitations

    The analysis is restricted to 1- and 2-dimensional range queries, and algorithm selection is not fully solved for practitioners.

Abstract

from arXiv · show

Differential privacy has become the dominant standard in the research community for strong privacy protection. There has been a flood of research into query answering algorithms that meet this standard. Algorithms are becoming increasingly complex, and in particular, the performance of many emerging algorithms is {\em data dependent}, meaning the distribution of the noise added to query answers may change depending on the input data. Theoretical analysis typically only considers the worst case, making empirical study of average case performance increasingly important. In this paper we propose a set of evaluation principles which we argue are essential for sound evaluation. Based on these principles we propose DPBench, a novel evaluation framework for standardized evaluation of privacy algorithms. We then apply our benchmark to evaluate algorithms for answering 1- and 2-dimensional range queries. The result is a thorough empirical study of 15 published algorithms on a total of 27 datasets that offers new insights into algorithm behavior---in particular the influence of dataset scale and shape---and a more complete characterization of the state of the art. Our methodology is able to resolve inconsistencies in prior empirical studies and place algorithm performance in context through comparison to simple baselines. Finally, we pose open research questions which we hope will guide future algorithm design.

1. INTRODUCTION

Differentially private query algorithms have become difficult to compare because empirical evidence is incomplete, data-dependent performance varies across datasets, and parameter choices and baselines are often inadequately handled. DPBENCH addresses these issues through principled evaluation and a broad study of range-query algorithms, revealing strong effects of scale and resolving prior inconsistencies.

  • Evaluation Challenges: Existing empirical studies leave gaps and inconsistencies because they do not comprehensively evaluate the growing set of differentially private algorithms.Increasing algorithmic complexity makes theoretical error analysis harder and strengthens the need for sound empirical evaluation.
  • Evaluation Challenges: Data-dependent algorithms can reverse their relative performance across datasets, while existing evaluations provide little guidance for extrapolating error to new scales or privacy settings.Their error depends on input properties, so an algorithm that wins on one dataset may lose on another.
  • Evaluation Challenges: Practitioners lack reliable algorithm-selection guidance because studies often report mean error without variability and omit comparisons with simple baselines such as the Laplace mechanism.The error is random, so mean performance alone does not characterize the output a practitioner may receive.
  • DPBENCH: DPBENCH defines evaluation principles and a methodology that tunes free parameters, ensures fair comparisons, analyzes data characteristics, and reports both mean and variation of error against baselines.The framework examines domain size, dataset scale, and empirical distribution shape.
  • Empirical Study: The benchmark evaluates 15 published algorithms across 27 datasets and 7,920 experimental settings for 1- and 2-dimensional range queries.The study is designed to characterize algorithm error across a broad set of datasets and settings.
  • Findings: At smaller scales, the best data-dependent algorithms can beat simpler data-independent algorithms by an order of magnitude, whereas many perform worse at large scales.The study identifies scale as a major determinant of data-dependent algorithm performance.
  • Findings: DPBENCH explains prior contradictory results by showing that one conclusion used small-scale data while the opposing conclusion used larger-scale datasets.The framework also formalizes scale-epsilon exchangeability and consistency to help extrapolate empirical findings.
  • Findings: DPBENCH’s tuning produces 13× lower error for some algorithms, including multiplicative weights, than original implementations using default parameter settings.The result shows that free-parameter choices can materially affect reported algorithm performance.

2. PRELIMINARIES

The paper models private data as a multidimensional array of counts and studies range-query answering under differential privacy. It introduces the privacy model, Laplace-based noise, query representation, and the domain, scale, and shape properties used to characterize datasets and algorithms.

  • Privacy Model: Differential privacy requires randomized algorithms to protect neighboring databases that differ in at most one record.The privacy guarantee constrains how much the output distribution can change when one individual’s record is added or removed.
  • Privacy Model: Sequentially composing k algorithms with privacy parameters ϵ_1 through ϵ_k yields total privacy parameter ϵ = ∑i ϵ_i.The total ϵ acts as a privacy budget allocated across subroutines.
  • Privacy Mechanisms: The Laplace mechanism releases f(I) plus independent noise with scale Δf/ϵ, where Δf is the maximum L1 change caused by one record.For count queries with sensitivity 1, the added noise has distribution Laplace(1/ϵ).
  • Data Model and Task: The task represents a database as a multidimensional count array and answers range queries by summing entries in the corresponding hyper-rectangle.Experiments focus on low-dimensional settings with k ∈ {1, 2} target attributes.
  • Algorithm Classes: Data-independent algorithms add noise whose distribution does not depend on the input data, giving the same performance for datasets with a fixed domain size.The benchmark identifies algorithm properties and free parameters in its algorithm table.
  • Data Properties: Dataset domain size is the number of cells, scale is the total tuple count ||x||_1, and shape is the normalized distribution p = x/||x||_1.Shape captures how data is distributed over the domain and is independent of scale.

3. ALGORITHMS & PRIOR RESULTS

The paper organizes range-query algorithms into data-independent and data-dependent strategies, then reviews prior evidence showing unresolved disagreements about which approaches perform best across settings.

  • Algorithm strategies: Independent Laplace noise accumulates variance linearly with the number of cells in a range, making large-range queries increasingly inaccurate.Its performance therefore depends critically on domain size.
  • Algorithm strategies: Data-independent algorithms have dataset-invariant error at a fixed domain size, whereas data-dependent algorithms respond to dataset shape and scale.Data-independent methods differ mainly through their chosen linear combinations; data-dependent methods include partitioning strategies.
  • Algorithm strategies: Adaptive partitioning reduces noise by aggregating cell groups, but relies on assumptions such as within-bucket uniformity.Equi-width histograms are one example of this strategy.
  • Prior results: Prior studies disagree about whether data-dependent methods consistently outperform matrix-mechanism techniques, with MWEM reported as 2-10× worse than PRIVELET on some hard datasets.Coverage was also incomplete for two-dimensional range queries.
  • Prior results: Existing work left unresolved whether the best data-dependent algorithms consistently beat data-independent methods and which factors beyond domain size affect performance.The paper identifies this as a central state-of-the-art gap.

4. EVALUATION PRINCIPLES

DPBENCH defines evaluation principles covering input diversity, end-to-end privacy, and sound output assessment. These principles target incomplete understanding and unfair comparisons in prior evaluations.

  • Input diversity: DPBENCH requires diversity across ϵ, dataset scale, dataset shape, and domain size while varying each characteristic independently where possible.This is intended to reveal how algorithm error changes across input settings.
  • Input diversity: Because algorithm winners vary with ϵ, scale, shape, and domain size, diverse evaluation inputs remain necessary rather than optional.The paper reports this pattern for both one- and two-dimensional range queries.
  • End-to-end privacy: All computation before or after a private algorithm, including cleaning and output selection, must be accounted for in the overall privacy guarantee.A portion of the privacy budget may be allocated to these tasks when necessary.
  • End-to-end privacy: Required parameters must be set by data-independent or differentially private methods, and public side information must be used consistently across algorithms.Tuning parameters on the evaluation data or inconsistently assuming known scale can invalidate comparisons.
  • Output assessment: Sound evaluation measures expected error, error variability, bias, and performance under reasonable privacy and utility settings.The paper distinguishes output variability from uncertainty in estimating mean error.

5. DPBENCH EVALUATION FRAMEWORK

DPBENCH is a task-specific benchmarking framework that combines diverse data generation, privacy-preserving algorithm repairs, and standardized error interpretation. It supports fair comparisons across range-query algorithms and input conditions.

  • Framework structure: DPBENCH instantiates separate benchmarks for different analysis tasks and organizes each benchmark around workloads, datasets, algorithms, loss functions, and evaluation components.The benchmark is defined as a 9-tuple containing task-specific and task-independent elements.
  • Input generation: Its data generator varies scale and domain while using source datasets and coordinated domain choices to provide shape diversity.The generator is designed to vary one data characteristic while holding the others constant when studying effects.
  • Privacy repairs: DPBENCH learns free-parameter settings on separate training datasets, using ϵ, scale, and domain size to produce parameters for evaluation.The training datasets are not reused for evaluation.
  • Privacy repairs: Side-information-dependent algorithms can be repaired by spending part of the privacy budget to estimate required information privately.This repair introduces a parameter governing the budget fraction and is difficult to automate fully.
  • Error measurement: DPBENCH reports scaled average per-query error and compares both mean and 95 percentile error across repeated algorithm executions and generated samples.The 95 percentile captures performance volatility relevant to risk-averse users.
  • Error interpretation: IDENTITY and UNIFORM provide upper-bound baselines for interpreting whether sophisticated algorithms deliver useful error reductions.UNIFORM uses only estimated scale and assumes a uniform dataset shape.
  • Theoretical properties: Most evaluated algorithms are scale-ϵ exchangeable, so increasing dataset scale can have an effect on scaled error equivalent to increasing ϵ.This permits varying scale instead of ϵ in empirical studies when exchangeability is proven.
  • Theoretical properties: Consistency requires error to decrease toward zero as ϵ increases, while non-consistent algorithms are characterized as biased.The privacy guarantee weakens as ϵ increases.

6. EXPERIMENTAL SETUP

The experiments benchmark one- and two-dimensional range-query algorithms on varied datasets, workloads, and domain sizes. They also modify algorithms with free parameters or non-private side information to enforce the evaluation principles.

  • Benchmark design: The study evaluates one- and two-dimensional range-query benchmarks with reproducibly specified datasets, workloads, algorithms, and L2 loss.The experimental results use task-specific benchmark components defined for each dimensionality.
  • Datasets: The dataset collection includes 11 previously used and 14 newly introduced datasets, with generated scales from 10^3 through 10^8.New datasets increase shape diversity.
  • Datasets: Domain sizes range from 256 to 4096 in one dimension and from 32 × 32 to 256 × 256 in two dimensions.Five generated data vectors are sampled for each scale and domain-size setting.
  • Workloads: One-dimensional experiments primarily use all prefix queries, while two-dimensional experiments use 2000 random range queries.Prefix answers can derive any range query by combining exactly two prefix answers.
  • Privacy adjustments: The evaluation privately estimates scale for SF, MWEM, UGRID, and AGRID variants that otherwise assume the true scale is public.Using ρ_total = 0.05 produced reasonable performance in synthetic-data tests.
  • Parameter adjustments: MWEM and AHP receive learned parameter settings because their original free parameters were tuned on evaluation data, violating the no-free-parameters principle.The repaired versions are denoted MWEM* and AHP* and are trained on synthetic power-law and normal shape distributions.
  • Parameter adjustments: For MWEM*, the selected round count T varies from 2 to 100 across the evaluated scale range and improves performance over a static setting.The tuning searches T ∈ [1, 200] across ϵ-scale products.

7. EXPERIMENTAL FINDINGS

DPBench reveals that algorithm performance depends strongly on scale, dataset shape, domain size, tuning, and error variability, with no uniformly best algorithm. Data-dependent methods can excel at small scales but often lose their advantage as scale grows.

  • Scale: Data-dependent algorithms can outperform data-independent methods at small scales, by up to 2.47× in 1D and 3.10× in 2D on average.Some individual datasets show order-of-magnitude improvements.
  • Scale: At moderate or larger scales, many data-dependent algorithms perform worse than the IDENTITY baseline, and their comparative advantage often disappears.At the largest scales, almost all data-dependent algorithms underperform data-independent alternatives.
  • Data shape: Algorithm error varies substantially with dataset shape, and different algorithms perform best on different shapes.In 1D, EFPA’s error varies by a factor of 24.88 between its lowest and highest values at the smallest scale.
  • Domain size: Domain size affects data-dependent and data-independent algorithms differently: AGRID remains nearly flat, while DAWA is flat for some datasets and increases for others.For data-independent algorithms, error increases with domain size as expected, with Hb eventually outperforming IDENTITY.
  • Competitive algorithms: No single algorithm has uniformly low error: data-dependent algorithms dominate at small scales, while data-independent algorithms dominate at large scales.Eight algorithms are competitive in at least one 1D setting and five in at least one 2D setting.
  • Tuning: Tuning free parameters can reduce error by more than 7.5×, and synthetic-data training substantially improves MWEM, especially at large scales.For AHP, the trained variant was only slightly better on average, with a 1.03 improvement ratio at scale 10^7.
  • Error variability: Mean error alone can mislead risk-averse users because algorithms differ in error variability and 95th-percentile performance.DAWA was best by mean error but not 95th-percentile error in ten 1D scenarios.
  • Bias and consistency: At large scales, high error for MWEM, MWEM*, PHP, and UNIFORM is attributed to bias, and these algorithms are proven inconsistent.Their error becomes dominated by bias as scale increases.

8. DISCUSSION AND TAKEAWAYS

The discussion uses DPBench findings to explain prior inconsistencies and guide algorithm selection. It concludes that scale, privacy budget, and dataset shape determine which methods are competitive, while algorithm selection and public error bounds remain open challenges.

  • Explaining prior work: DPBench resolves prior inconsistencies by showing that MWEM’s relative performance depends on scale and epsilon, with advantages at small scale or low epsilon.The datasets where MWEM struggled had scale over 335,000.
  • Practitioner guidance: Practitioners should first assess signal strength from dataset scale and the epsilon budget when selecting an algorithm.Scale and epsilon are described as exactly exchangeable in their impact on scaled error.
  • Practitioner guidance: In high-signal regimes, simpler data-independent methods such as IDENTITY and Hb are unlikely to be beaten by complex data-dependent algorithms.Their error bounds are easier to derive, performance is data-independent, and they have few parameters.
  • Practitioner guidance: In low-signal regimes, data-dependent methods merit consideration, but their error can vary considerably with input properties and they lack public error bounds.DAWA is competitive for most 1D datasets; in 2D, AGRID is consistently strong while DAWA excels on very sparse datasets.
  • Open research problems: Open problems include understanding which data properties enable low error, developing better algorithm-selection methods, and providing error bounds for data-dependent algorithms.The paper states that current evaluation does not fully solve selection for a new dataset.

9. CONCLUSION

The paper presents DPBENCH as a principled framework for evaluating differentially private algorithms, applying it to 1- and 2-dimensional range queries. The evaluation resolves prior inconsistencies, identifies low-error algorithms for particular datasets, and motivates open research questions, while leaving broader tasks and privacy-parameter guidance for future work.

  • DPBENCH is a novel and principled framework for evaluating differential privacy algorithms.
  • The framework evaluates 1- and 2-dimensional range-query algorithms, resolving gaps and inconsistencies in prior work.
  • The evaluation identifies state-of-the-art algorithms that achieve the least error for their datasets.
  • The study poses open research questions for future work.
  • The investigation primarily evaluates utility under standard privacy settings and remains focused on 1- and 2-dimensional range queries.

A. DATASET DESCRIPTIONS

The paper’s dataset collection covers 1D and 2D histograms from previously used sources, newly derived filtered datasets, and a new stroke-trial dataset. These constructions vary attribute choice, filtering, spatial representation, and data shape.

  • Table 2 summarizes the 1D and 2D datasets considered in the paper.
  • 1D Datasets: The 1D collection combines seven datasets from prior papers with eleven new datasets derived from three original data sources.
  • 1D Datasets: Filtering secondary attributes creates alternative 1D shape distributions on a selected primary attribute.
  • 1D Datasets: BIDS datasets histogram bid IP addresses, with BIDS-FJ and BIDS-FM filtering records by jewelry and mobile merchandise, respectively.
  • 2D Datasets: The 2D datasets include taxi mobility traces, previously used datasets, subsets of 1D sources, and the STROKE dataset using age and systolic blood pressure.

B. ALGORITHM DESCRIPTIONS

The algorithms use data-independent strategy queries, data-dependent partitioning, workload-aware updates, Fourier representations, and hierarchical structures to reduce range-query error. Their privacy and utility behavior depends on how strategies, partitions, counts, and privacy budgets are selected.

  • Data-Independent Algorithms: Data-independent methods select linear strategy queries, privately estimate them with Laplace noise, and reconstruct workload answers.
  • Hierarchical Strategies: Hierarchical methods organize individual queries into trees whose internal nodes sum child queries and whose root equals the database size.
  • Hierarchical Strategies: GREEDY H is workload-aware because it modifies hierarchical-query weights in response to the input workload, unlike static H, Hb, and PRIVELET strategies.
  • Data-Dependent Partitioning Algorithms: Data-dependent partitioning algorithms privately select disjoint buckets before estimating their counts.
  • Data-Dependent Partitioning Algorithms: Partitioning methods allocate privacy budget between partition selection and count estimation, with ρ denoting the proportion used for partition identification.
  • Data-Dependent Partitioning Algorithms: DAWA uses dynamic programming with noisy costs to find a least-cost partition, derives hierarchical strategy queries, and applies a Hilbert transformation for 2D data.
  • Other Data-Dependent Algorithms: MWEM iteratively selects the workload query with highest error and updates a uniform initial estimate using multiplicative weights.
  • Other Data-Dependent Algorithms: EFPA retains k Fourier coefficients, adds Laplace noise, and inverts the transform, trading approximation error against reduced noise.

C. THEORETICAL ANALYSIS

The theoretical analysis tests consistency and scale-epsilon exchangeability across the studied mechanisms and algorithms. It proves these properties for several methods, while identifying failures caused by fixed tree heights, iteration counts, cluster counts, or other design choices.

  • The analysis examines whether the algorithms satisfy consistency and scale-epsilon exchangeability.
  • Consistency and Scale-Epsilon Exchangeability: Any Matrix Mechanism instance satisfies both consistency and scale-epsilon exchangeability.
  • Consistency and Scale-Epsilon Exchangeability: IDENTITY, PRIVELET, H, Hb, and GREEDY H therefore ensure both consistency and scale-epsilon exchangeability.
  • Consistency: EFPA ensures consistency, with its selected coefficient count approaching the full set as ϵ tends to infinity.
  • Consistency: AHP, DAWA, DPCUBE, AGRID, and UGRID ensure consistency.
  • Consistency: QUADTREE and HYBRIDTREE do not ensure consistency on sufficiently large domains because their fixed maximum heights can leave multiple domain cells in a leaf.
  • Consistency: PHP, StructureFirst, and MWEM do not ensure consistency under the stated fixed iteration or cluster-count choices.
  • Scale-Epsilon Exchangeability: PHP, MWEM, EFPA, DAWA, AHP, AGRID, UGRID, QUADTREE, and HYBRIDTREE ensure scale-epsilon exchangeability, while StructureFirst does not.
Loading 1512.04817v1…