Source-linked AI summary
A Learning Theory Approach to Non-Interactive Database Privacy
Avrim Blum, Katrina Ligett, Aaron Roth
TL;DR
The paper asks whether private, non-interactive releases can support very large classes of queries without exposing sensitive database information. It develops net-based synthetic-data mechanisms and related algorithms, showing strong guarantees on discrete domains, impossibility results on continuous domains, and a stronger privacy notion.
Problem
The paper addresses how to release useful information for large query classes while preserving privacy, especially when analysts need non-interactive access to sensitive databases.
Method
The paper uses learning-theoretic nets and VC-dimension to design private query-release mechanisms, alongside relaxed utility for halfspaces and distributional privacy.
Results
The paper privately releases useful synthetic data for discretized domains, efficiently handles intervals and fixed-dimensional rectangles, supports halfspaces under relaxed utility, and proves continuous-domain impossibility for intervals.
Takeaways & Limitations
Small nets can certify accurate private mechanisms for broad counting-query classes, while domain continuity and computational efficiency impose distinct boundaries.
Takeaways & Limitations
The general net mechanism is not generally computationally efficient, and comparable utility with polynomial running time remains an open question.
Abstract
from arXiv · showhide
In this paper we demonstrate that, ignoring computational constraints, it is possible to privately release synthetic databases that are useful for large classes of queries -- much larger in size than the database itself. Specifically, we give a mechanism that privately releases synthetic data for a class of queries over a discrete domain with error that grows as a function of the size of the smallest net approximately representing the answers to that class of queries. We show that this in particular implies a mechanism for counting queries that gives error guarantees that grow only with the VC-dimension of the class of queries, which itself grows only logarithmically with the size of the query class. We also show that it is not possible to privately release even simple classes of queries (such as intervals and their generalizations) over continuous domains. Despite this, we give a privacy-preserving polynomial time algorithm that releases information useful for all halfspace queries, given a slight relaxation of the utility guarantee. This algorithm does not release synthetic data, but instead another data structure capable of representing an answer for each query. We also give an efficient algorithm for releasing synthetic data for the class of interval queries and axis-aligned rectangles of constant dimension. Finally, inspired by learning theory, we introduce a new notion of data privacy, which we call distributional privacy, and show that it is strictly stronger than the prevailing privacy notion, differential privacy.
1 Introduction
The paper studies non-interactive privacy mechanisms that release information useful for large query classes, while identifying important computational and domain limitations. It also introduces distributional privacy as a stronger alternative to differential privacy.
- Motivation: Database privacy seeks useful information from sensitive records without releasing the underlying data.The motivating tension arises when data administrators and analysts are different parties.
- Problem formulation: The paper defines usefulness for a query class as answering every counting query within ±α of its true fraction.Counting queries ask what fraction of database entries satisfy a predicate.
- Synthetic data release: For discretized domains, a net-based mechanism privately releases synthetic data whose error grows logarithmically with the smallest α-net.This is an information-theoretic result and is not generally computationally efficient.
- Synthetic data release: The net result yields counting-query error governed by the class’s VC-dimension, while efficient synthetic release is obtained for intervals and fixed-dimensional axis-aligned rectangles.The VC-dimension grows only logarithmically with the size of the query class.
- Continuous domains and relaxed utility: Over non-discretized domains, private release useful for even interval queries is impossible under the paper’s usefulness definition.For halfspaces, the paper instead relaxes utility so an answer may correspond to a nearby query, motivated by large-margin separators.
- Distributional privacy: Distributional privacy requires outputs to reveal only information about an underlying distribution and is strictly stronger than differential privacy.The paper shows distributional privacy implies differential privacy, but not conversely.
2 Definitions
This section formalizes databases, mechanisms, privacy, query usefulness, and complexity measures used throughout the paper. It focuses on counting queries and establishes their sensitivity while motivating one-shot public release.
- Databases and mechanisms: A database is an unordered multiset of n records from an abstract domain X, allowing repeated elements.Formally, databases are n-tuples in X^n without an ordering.
- Databases and mechanisms: A database access mechanism is a randomized mapping from databases to an arbitrary output range; synthetic data means the output is itself a database.Synthetic outputs have range X^*.
- Privacy: Neighboring databases differ in at most one data element, and differential privacy constrains outcome probabilities across every neighboring pair.The mechanism must satisfy the privacy inequality for all outcome events.
- Counting queries: A counting query evaluates the fraction of database elements satisfying a Boolean predicate, and every such query has global sensitivity at most 1/n.Changing one record can alter the fraction by at most 1/n.
- Complexity measures: VC-dimension measures the largest point set whose every subset can be selected by predicates in the class.A class shatters a set when it realizes all 2^|S| labelings on that set.
- Utility: The paper seeks one-shot outputs that remain useful for arbitrarily many queries, rather than interactive mechanisms whose accuracy degrades with query count.Usefulness requires all queries in a class to be answered approximately correctly with high probability.
- Utility: An α-net is a collection of databases that approximately represents every database with respect to a query class, with Nα(C) denoting a minimum-cardinality net.The net mechanism’s guarantees are built around this complexity measure.
3 General release mechanism
The Net mechanism instantiates the exponential mechanism over a small α-net of databases, privately selecting synthetic data that approximates answers for an entire query class. Its utility depends on net size and sensitivity, yielding counting-query guarantees governed by VC-dimension, but the construction may be computationally inefficient and has a tight VC-dimension dependence.
- Mechanism: The Net mechanism applies the exponential mechanism to an α-net of candidate databases, using query-answer agreement as its quality criterion.The exponential mechanism selects a candidate from the net according to a quality score measuring how well it matches the input database's query answers.
- Privacy and utility: The Net mechanism preserves ǫ-differential privacy and is (2α, δ)-useful when α satisfies a condition determined by net size and query sensitivity.Privacy follows from the exponential mechanism; utility is analyzed through the smallest α-net and the maximum query sensitivity.
- Counting queries: For counting queries, the mechanism reduces utility analysis to bounding sensitivity and the smallest α-net, with GSQ ≤1/n for every counting query.This reduction yields a direct utility corollary for counting-query classes.
- Counting queries: A database of size eO(log XVCDIM(C) α3ǫ ) suffices for α-useful, ǫ-differentially private release over a counting-query class C.The VC-dimension dependence is strictly stronger than the finite-class logarithmic bound because VCDIM(C) ≤log |C| for finite classes.
- Limitations: The general release results apply only to discretized domains and may not be computationally efficient because the exponential mechanism can range over a super-polynomially large set.The paper explicitly identifies both discretization and computational efficiency as limitations of this section's results.
- Lower bound: The dependence on VC-dimension is tight: privately achieving usefulness with databases of size n ≤VCDIM(C) is ruled out under the stated parameters.The lower bound is established using a shattered set and counting queries corresponding to its subsets.
4 Interval queries
The paper gives an efficient differentially private algorithm for releasing synthetic data useful for interval queries on discretized domains, extending to constant-dimensional axis-aligned rectangles. The algorithm partitions the domain by private binary searches and releases a synthetic database with controlled interval mass.
- Scope and contribution: ReleaseIntervals efficiently releases synthetic data useful for interval queries over a discretized domain and extends to constant-dimensional axis-aligned rectangles.The algorithm requires a database size polynomial in the privacy and usefulness parameters.
- Algorithm: The algorithm repeatedly uses privacy-preserving binary search to partition the unit interval into regions containing approximately an α′ fraction of the point mass.It then assigns exactly an α′ fraction of synthetic points to each discovered region.
- Privacy: ReleaseIntervals is ǫ-differentially private.Privacy follows from composing the Laplace-mechanism queries used during the binary searches.
- Utility: ReleaseIntervals is (α, δ)-useful for databases satisfying the theorem's size bound.The proof controls the Laplace noise at every search step and bounds the resulting error for arbitrary interval queries.
- Motivation: Although intervals are simple, their exponentially many queries make asking every interval interactively infeasible.This motivates a non-interactive synthetic-data release mechanism for the whole class.
5 Lower bounds
The paper proves that differential privacy cannot support useful release for interval queries on continuous domains, because useful median answers would contradict privacy. Discretization or a relaxed usefulness definition is therefore required for the positive results.
- Scope and escape routes: The impossibility result applies to non-discretized domains, whereas discretization or relaxed usefulness provides two ways around it.The paper takes the discretization route for some results and relaxes usefulness for halfspace queries in another section.
- Median lower bound: Useful median release is impossible on real-valued databases under ǫ-differential privacy for any δ < 50 and any ǫ.The proof uses databases whose entries transition one at a time between two real values, forcing a privacy violation.
- Query-class lower bound: No ǫ-differentially private mechanism can be (α, δ)-useful for interval queries on continuous domains when α, δ < 1/2.The same impossibility extends to higher-dimensional classes generalizing intervals, including halfspaces, axis-aligned rectangles, and spheres.
6 Answering Halfspace Queries
The paper releases a privacy-preserving data structure for large-margin halfspace queries rather than synthetic data. Random projections and low-dimensional nets support polynomial-time evaluation with accuracy guarantees for qualifying queries.
- Mechanism: The mechanism outputs a projected halfspace data structure instead of synthetic data.It maintains random projections, canonical halfspaces, and associated approximate answers.
- Utility scope: Large-margin halfspace queries are answered only when every database point has absolute inner product at least γ with the query vector.The margin condition is defined with respect to the private database.
- Mechanism: Random projections preserve the geometric information needed to approximate halfspace answers in a lower-dimensional space.The construction relies on norm and inner-product preservation with high probability.
- Mechanism: The canonical halfspaces form a γ/4-net in the projected space, whose size is exponential in T.Choosing T as a constant makes maintaining the net feasible.
- Privacy: The released structure preserves ε-differential privacy.Privacy follows by composing m|U| Laplace mechanisms, each using ε/(m|U|)-differential privacy.
- Utility guarantee: Except with probability β, every unit-vector query with margin γ has answer error at most α, with polynomial running time and output size for γ, α ∈ Ω(1).The guarantee applies to the large-margin query family rather than all halfspace queries.
7 Distributional Privacy
The paper introduces distributional privacy as a learning-theoretic privacy definition based on databases sampled from a common population. It proves a strict relationship with differential privacy: distributional privacy implies differential privacy under a small failure probability, but not conversely.
- Definition: Distributional privacy requires mechanisms to behave similarly on databases sampled from the same underlying population.The definition compares outputs for S-neighbor databases with probability at least 1−β.
- Relationship to differential privacy: If β = o(1/n^2), distributional privacy implies ε-differential privacy.The proof embeds any neighboring database pair among S-neighbors drawn from a set of size n+1.
- Relationship to differential privacy: Differential privacy does not imply distributional privacy for meaningful ε and β values.Theorem 7.5 gives mechanisms satisfying ε-differential privacy but failing (ε, β)-distributional privacy for every ε < 1 and β = o(1).
- Separation: The mirrored-mod function demonstrates that differential privacy can remain useful when distributional privacy makes useful information impossible to reveal.The comparison separates the two notions through a concrete query function.
- Scope condition: The implication from distributional privacy to differential privacy depends on sampling database elements without replacement.Without replacement, rare databases could be assigned exceptional behavior while preserving distributional privacy for sufficiently small β.
8 Conclusions and Open Problems
The paper establishes that small nets can certify accurate differentially private mechanisms, while also providing efficient mechanisms for selected query classes. It leaves open whether comparable utility can be achieved in polynomial time for broader classes.
- Small nets suffice to certify accurate differentially private mechanisms for a class of queries.For counting queries, the resulting database size can be logarithmic in the query-class size or linear in its VC-dimension.
- The authors give efficient algorithms for interval queries on a discrete interval and large-margin halfspace queries on the unit sphere.
- The main open problem is achieving utility comparable to the net mechanism with running time polynomial in the input database size n.
- Specific unresolved cases include conjunctions and parity queries.