Source-linked AI summary
Interactive Privacy via the Median Mechanism
Aaron Roth, Tim Roughgarden
TL;DR
Private data analysis seeks useful answers while protecting individuals in sensitive databases, but prior interactive methods handled queries independently and scaled poorly. The paper introduces the median mechanism, which correlates online answers to arbitrary predicate queries and also provides an efficient implementation. It achieves near-optimal interactive privacy dependence while retaining strong utility guarantees, with the efficient version weakening utility only for a negligible fraction of inputs.
Problem
Prior interactive privacy mechanisms lacked a way to exploit correlations among online predicate queries while preserving useful answers.
Method
The median mechanism classifies queries as easy or hard and uses prior answers to correlate perturbations while answering adaptively chosen queries online.
Results
Theorem 4.1 guarantees usefulness and differential privacy for adaptively chosen online predicate queries, under the stated database-size condition.
Takeaways & Limitations
The mechanism shows that interactivity does not pose an information-theoretic barrier to private predicate-query release, with query dependence nearly matching log k.
Takeaways & Limitations
The efficient implementation’s usefulness guarantee excludes a negligible fraction of input distributions, although its privacy guarantee holds for all input databases.
Abstract
from arXiv · showhide
We define a new interactive differentially private mechanism -- the median mechanism -- for answering arbitrary predicate queries that arrive online. Relative to fixed accuracy and privacy constraints, this mechanism can answer exponentially more queries than the previously best known interactive privacy mechanism (the Laplace mechanism, which independently perturbs each query result). Our guarantee is almost the best possible, even for non-interactive privacy mechanisms. Conceptually, the median mechanism is the first privacy mechanism capable of identifying and exploiting correlations among queries in an interactive setting. We also give an efficient implementation of the median mechanism, with running time polynomial in the number of queries, the database size, and the domain size. This efficient implementation guarantees privacy for all input databases, and accurate query results for almost all input databases. The dependence of the privacy on the number of queries in this mechanism improves over that of the best previously known efficient mechanism by a super-polynomial factor, even in the non-interactive setting.
1. INTRODUCTION
Differential privacy must balance useful analysis against protection for individuals, but independently noisy interactive answers scale poorly with the number of queries. The median mechanism addresses this gap by correlating answers online, achieving near-noninteractive performance and an efficient variant with almost-all-database utility.
- Motivation: Differential privacy formalizes the utility-privacy trade-off for releasing information from sensitive databases.Its output is designed to be essentially independent of whether any individual contributes data.
- Limitations of prior interactive methods: Independent Laplace perturbations impose privacy costs that grow linearly with k, limiting useful answering to k = o(n).For fixed usefulness parameters, maintaining privacy requires noise whose magnitude scales with the number of answered queries.
- Prior work: BLR08 reduces the privacy dependence to log k for predicate queries, but its non-interactive mechanism requires all queries in advance.Before this work, no interactive mechanism was known to outperform independent Laplace perturbations.
- Our results: The median mechanism interactively answers adaptively chosen predicate queries with privacy scaling as log k log |X| and performance close to the non-interactive optimum.It is presented as the first interactive mechanism better than Laplace perturbation.
- Our results: The efficient implementation runs in polynomial time in n, k, and |X|, preserving privacy while guaranteeing usefulness for all but a negligible fraction of input distributions.Its utility guarantee is weaker than that of the basic implementation, which is not efficient.
- Core idea: The mechanism exploits O(log k log |X|) hard queries whose answers determine the remaining query answers up to ±ǫ.This correlation structure enables low privacy cost despite online query arrival.
2. PRELIMINARIES
The paper models databases as multisets over a finite domain and predicate queries as fractions of records satisfying Boolean predicates. It defines accuracy, usefulness, neighboring databases, differential privacy, and query sensitivity for this setting.
- Setting: A database is an unordered multiset of elements from a finite domain X, with size n = |D|.Predicate queries are Boolean functions on X evaluated as fractions of database elements satisfying the predicate.
- Setting: A predicate query f(D) returns the fraction of database elements satisfying its predicate, and an answer is ε-accurate when |f_i(D) − a_i| ≤ ε.The mechanisms answer k predicate queries numerically.
- Usefulness: A mechanism is (ε, δ)-useful when it gives ε-accurate answers to every query sequence and database with probability at least 1 − δ.This definition quantifies utility over all query sequences and databases.
- Privacy: Neighboring databases have the same size and differ in exactly one element.This relation defines the single-person change protected by differential privacy.
- Privacy: (α, τ)-differential privacy bounds the output-probability change between neighboring databases for every query sequence and measurable output subset.The paper treats negligible τ as a function that decreases faster than every inverse polynomial.
- Sensitivity: The sensitivity of a real-valued query is its maximum change across neighboring databases; every non-trivial predicate query has sensitivity precisely 1/n.Approximate answers can also support efficient reconstruction of a consistent synthetic database.
3. THE MEDIAN MECHANISM: BASIC IMPLEMENTATION
The basic median mechanism processes predicate queries online, classifying each as easy or hard and using medians for queries whose answers are already determined by prior outputs. Hard queries receive Laplace-style treatment and update the consistent-database set.
- Query classification: The mechanism classifies each query as easy or hard according to whether prior answers determine an accurate answer for most consistent databases.Easy queries use the corresponding median value, while hard queries use the Laplace mechanism.
- Guarantees: The privacy and accuracy parameters, query count, and auxiliary parameters determine the mechanism’s privacy cost and usefulness guarantees.The denominator in the stated parameter expression represents privacy cost as a function of k; constants are not optimized.
- Algorithm: The mechanism initializes C0 as the databases of size m over X and processes f1, …, fk sequentially.At each step it maintains databases consistent with earlier hard-query answers.
- Algorithm: For each query, it perturbs the statistic r_i with Laplace noise and a randomly selected scale before deciding whether the query is easy or hard.The scale index j is chosen with probability proportional to 2^-j.
- Outputs: Easy queries output the median value over consistent databases, whereas hard queries output f_i(D) plus Laplace noise.Hard-query answers also filter the consistent-database set for subsequent steps.
- Failure condition: The mechanism halts and reports failure if hard-query processing exceeds its prescribed threshold.The threshold is expressed in terms of m and log |X|.
4. ANALYSIS OF MEDIAN MECHANISM
The analysis establishes utility and privacy guarantees for the median mechanism by separating easy and hard queries and bounding how many hard queries can occur. It also derives the mechanism’s error and explains the role of small representative databases and threshold privacy analysis.
- Theorem 4.1: Theorem 4.1 gives (ε, δ)-usefulness and (α, τ)-differential privacy for adaptively chosen predicate queries when the database is sufficiently large.Here, τ is negligible in k and |X|, while δ is inverse polynomial in k and n.
- Utility: Theorem 4.2 gives utility failure probability δ = k exp(−Ω(εnα′)).The theorem summarizes the utility guarantee proved from accurate hard-query answers, accurate median answers for easy queries, and a non-failure bound.
- Utility: Easy-query median answers are ε-accurate whenever the intermediate estimates satisfy |r_i − r̂_i| ≤ 1/100 for every query.The proof uses the fact that more than half of the consistent databases being ε-accurate makes their median an ε-accurate answer.
- Utility: All k predicate-query results can be approximated using a database of size O(log k), supporting the bound on the number of hard queries.A uniformly sampled database satisfies the simultaneous approximation bound except with probability δ, and an appropriate database of size m exists with error ε/400.
- Utility: The median mechanism answers fewer than 20m log |X| hard queries, so it terminates after answering all queries under the stated accuracy conditions.The proof tracks the contraction of consistent databases; their number decreases with each hard query but remains at least one because a representative database exists.
- Privacy: Theorem 4.8 establishes (α, τ)-differential privacy, with negligible τ when n is sufficiently large.The privacy analysis treats the mechanism as releasing answers and easy/hard indicators, then bounds the probability ratio for the resulting transcript.
5. THE MEDIAN MECHANISM: EFFICIENT IMPLEMENTATION
The efficient median mechanism replaces the basic implementation’s super-polynomial computation with polynomial-time sampling over convex polytopes, preserving privacy while weakening utility to almost all inputs. It answers exponentially many queries under the stated distributional guarantees, with negligible failure probability.
- Guarantees: The efficient mechanism is (α, τ)-differentially private for adaptively chosen online predicate queries, with negligible τ.The privacy guarantee holds for every sequence of adaptively chosen queries, while utility is guaranteed only for almost all fractional databases.
- Guarantees: Exponentially many queries are answered for all but an O(|X|^-m) fraction of distributions drawn from the unit ℓ1 ball and databases sampled from them.The same distributional guarantee is stated for the efficient implementation’s usefulness, with δ = k exp(-Ω(εnα′)).
- Guarantees: On the exceptional inputs where usefulness may fail, the mechanism halts after answering queries with the Laplace mechanism rather than outputting incorrect answers.Thus the worst case is fallback to Laplace answers before halting, while better cases answer many more queries.
- Efficient implementation: Each Ci is a convex polytope defined by intersections of halfspaces encoding consistency with previously answered hard queries.The construction uses probability distributions or fractional histograms over X and updates Ci by intersecting with pairs of halfspaces.
- Finite databases: For uniformly sampled databases of size n, (ε, δ)-usefulness holds for all but an n^2/|X| fraction, with δ = k exp(-Ω(εnα′)).The finite-database result follows from the efficient mechanism’s distributional analysis and applies to uniformly randomly sampled databases.
6. CONCLUSION
The paper concludes that interactivity is not an information-theoretic barrier for private predicate-query release, while identifying efficiency and worst-case utility as remaining challenges.
- Main conclusion: For predicate queries, interactivity does not pose an information-theoretic barrier to differentially private data release.The mechanism’s dependence on k nearly matches the optimal offline dependence of log k.
- Main conclusion: The mechanism’s dependence on the number of queries k nearly matches the optimal offline dependence of log k.The conclusion notes that dependence on ε is not necessarily optimal because Dwork et al. achieve a better optimal dependence.
- Open questions: The efficient implementation runs in polynomial time but sacrifices worst-case utility guarantees.An interactive mechanism with polynomial runtime in |X| and k and worst-case utility guarantees remains open.