Interactive privacy via the median mechanism

Aaron Roth, Tim Roughgarden

TL;DR

This paper introduces the "median mechanism," a novel interactive differentially private data analysis technique. It significantly improves the number of queries that can be answered while maintaining privacy and utility, outperforming previous methods by allowing query answers to adapt to each other and exploiting query correlations.

What Problem Does This Paper Address?

In today's data-driven world, we often need to analyze sensitive datasets (like medical records) to gain valuable insights. However, we must also protect the privacy of the individuals whose data is included. Differential privacy provides a rigorous framework for this, ensuring that the outcome of an analysis doesn't reveal whether any single individual's data was part of the dataset.

A key challenge is balancing privacy with utility: how much useful information can we extract while still guaranteeing strong privacy? Previous methods, like the Laplace mechanism, add noise to each query result independently. This works well for a few queries, but the amount of noise (and thus the privacy cost) increases linearly with the number of queries. This severely limits the number of queries that can be answered, especially when dealing with many queries or when strict privacy is required.

Furthermore, existing advanced privacy mechanisms often require all queries to be known upfront (non-interactive). This is impractical in many real-world scenarios where queries arrive sequentially and adaptively. This paper tackles the problem of designing an interactive differentially private mechanism that can handle an arbitrary number of queries arriving online, while achieving much better privacy-utility trade-offs than previous interactive methods.

Methods

The core innovation is the median mechanism. Unlike previous approaches that perturb each query independently, the median mechanism is designed to:

  • Adaptively classify queries: It categorizes queries into "easy" and "hard" based on the current state of knowledge derived from previous query answers.
  • Exploit query correlations: It leverages the fact that the answers to some queries can predict the answers to others.
  • Answer "easy" queries using medians: For "easy" queries, it uses the median of query results from a set of databases consistent with previous answers. This is more accurate than adding significant noise.
  • Answer "hard" queries using Laplace perturbations: For "hard" queries, it falls back to the standard Laplace mechanism, adding noise to ensure privacy.

The mechanism maintains a set of "consistent" databases. When a query is classified as "easy," it means the majority of these consistent databases would yield an accurate answer. The mechanism then releases the median of these accurate answers. For "hard" queries, it uses independent Laplace noise. This adaptive classification and use of medians allows it to answer exponentially more queries than previous interactive methods for the same privacy budget.

The paper also presents an efficient implementation of the median mechanism. The basic version is not computationally efficient because it requires working with potentially huge sets of databases. The efficient version uses fractional databases (represented as probability distributions) and leverages advanced techniques like random walks on convex bodies to achieve polynomial runtime in the database size, number of queries, and domain size.

Datasets

Not discussed in the paper. The paper focuses on theoretical guarantees for arbitrary databases and query sets, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Interactivity is not a fundamental barrier to better privacy: The paper demonstrates that by making queries adaptive and allowing them to inform each other, we can achieve significantly better privacy-utility trade-offs than purely independent query processing.
  • Query correlation is key: The median mechanism's power comes from its ability to identify and exploit relationships between queries, allowing it to be more precise when possible.
  • "Easy" vs. "Hard" query classification: This adaptive classification is crucial. By identifying queries whose answers are largely predictable from previous results, the mechanism can avoid adding excessive noise.
  • VC dimension is a powerful tool for privacy analysis: The paper uses VC dimension arguments to bound the number of "hard" queries, which is essential for proving the mechanism's efficiency and privacy guarantees.
  • Fractional databases for efficiency: The efficient implementation cleverly uses fractional representations of databases to make computations tractable, bridging the gap between theoretical constructs and practical algorithms.

Key Results

  • Improved query count: The median mechanism can answer exponentially more queries than the previously best interactive mechanism (Laplace mechanism) for the same privacy and accuracy constraints.
  • Near-optimal query count: The number of queries it can handle is close to the theoretical best possible, even for non-interactive settings.
  • Privacy guarantee: The mechanism is differentially private, with the privacy cost scaling logarithmically with the number of queries and the domain size (specifically, O(log k log |X|)).
  • Efficient implementation: A polynomial-time implementation is provided, which is (ε, δ)-useful for almost all input distributions.
  • Privacy for all inputs: The efficient implementation guarantees privacy for all input databases, though its utility guarantee holds for "almost all" distributions.

Limitations and Future Work

  • Worst-case utility for efficient implementation: The efficient version sacrifices worst-case utility guarantees for "almost all" input distributions. The paper notes that for a small fraction of distributions, the mechanism might halt early, falling back to the Laplace mechanism for remaining queries.
  • Optimizing constants: The paper mentions that the constants in the privacy and utility bounds were not optimized.
  • Open questions:
    • Can an interactive mechanism with polynomial runtime achieve worst-case utility guarantees?
  • Can we achieve better runtime for specific query classes?
  • Can we develop novel output representations to circumvent existing impossibility results?

The paper concludes by highlighting the significant progress made in interactive private data analysis and points towards exciting avenues for future research in this area.

Summary updated

BibTeX
@inproceedings{roth2010interactive,
  author = {Aaron Roth and Tim Roughgarden},
  title = {{Interactive privacy via the median mechanism}},
  booktitle = {STOC},
  year = {2010},
  doi = {10.1145/1806689.1806794},
}
Figure