Source-linked AI summary
Differentially Private Release and Learning of Threshold Functions
Mark Bun, Kobbi Nissim, Uri Stemmer, Salil Vadhan
TL;DR
The paper asks how much sample complexity differential privacy requires for threshold release, distribution learning, and proper PAC learning, especially as the domain grows. It analyzes these tasks through reductions to the interior-point problem and recursive lower-bound constructions. The results establish Ω(log^*|X|) lower bounds, improve threshold-release upper bounds to 2^(1+o(1) log^*|X|), and extend the lower bound to ℓ-dimensional thresholds.
Problem
The paper investigates whether private threshold release is possible on infinite domains and whether its sample complexity grows with the domain size.
Method
The paper reduces threshold release and proper learning to the interior-point problem and develops recursive constructions and fingerprinting-code techniques for its bounds.
Results
The paper proves Ω(log^*|X|) lower bounds for private threshold release, distribution learning, and proper threshold learning, while improving threshold-release upper bounds to 2^(1+o(1) log^*|X|).
Takeaways & Limitations
Private proper learning of thresholds requires asymptotically more samples than the VC dimension alone, with the ℓ-dimensional lower bound Ω(ℓ · log^*|X|).
Takeaways & Limitations
The gap between the roughly 2^(log^*|X|) upper bound and the log^*|X| lower bound remains open, including whether the upper bound can be reduced to poly(log^*|X|).
Abstract
from arXiv · showhide
We prove new upper and lower bounds on the sample complexity of $(ε, δ)$ differentially private algorithms for releasing approximate answers to threshold functions. A threshold function $c_x$ over a totally ordered domain $X$ evaluates to $c_x(y) = 1$ if $y \le x$, and evaluates to $0$ otherwise. We give the first nontrivial lower bound for releasing thresholds with $(ε,δ)$ differential privacy, showing that the task is impossible over an infinite domain $X$, and moreover requires sample complexity $n \ge Ω(\log^*|X|)$, which grows with the size of the domain. Inspired by the techniques used to prove this lower bound, we give an algorithm for releasing thresholds with $n \le 2^{(1+ o(1))\log^*|X|}$ samples. This improves the previous best upper bound of $8^{(1 + o(1))\log^*|X|}$ (Beimel et al., RANDOM '13). Our sample complexity upper and lower bounds also apply to the tasks of learning distributions with respect to Kolmogorov distance and of properly PAC learning thresholds with differential privacy. The lower bound gives the first separation between the sample complexity of properly learning a concept class with $(ε,δ)$ differential privacy and learning without privacy. For properly learning thresholds in $\ell$ dimensions, this lower bound extends to $n \ge Ω(\ell \cdot \log^*|X|)$. To obtain our results, we give reductions in both directions from releasing and properly learning thresholds and the simpler interior point problem. Given a database $D$ of elements from $X$, the interior point problem asks for an element between the smallest and largest elements in $D$. We introduce new recursive constructions for bounding the sample complexity of the interior point problem, as well as further reductions and techniques for proving impossibility results for other basic problems in differential privacy.
1 Introduction
The paper studies the sample complexity cost of differential privacy for threshold query release, distribution learning, and proper PAC learning. It proves domain-size-dependent lower bounds, improves upper bounds, and relates these tasks to interior-point mechanisms.
- 1 Introduction: Differential privacy can impose a sample-complexity cost because accuracy may require more individuals even as asymptotic error vanishes.The paper frames this cost as the privacy price hidden in convergence rates and the number of samples needed before accurate results become possible.
- 1.2 Private Query Release: n = Ω(log^*|X|) samples are necessary for privately releasing threshold functions, and no such algorithm exists over infinite data universes.The lower bound applies to threshold query release over a totally ordered domain X.
- 1.2 Private Query Release: 2^(1+o(1) log^*|X|) samples improve the previous roughly 8^(log^*|X|) upper bound for private threshold release.The improved algorithm is inspired by the lower-bound ideas, while closing the gap to the Ω(log^*|X|) lower bound remains open.
- 1.3 Private Distribution Learning: Ω(log^*|X|) samples are also necessary for privately learning arbitrary distributions on X with respect to Kolmogorov distance.The paper establishes this through an essential equivalence between threshold release and private distribution learning.
- 1.4 Private PAC Learning: Ω(log^*|X|) samples are necessary for proper private PAC learning of threshold functions, exceeding the non-private VC-dimension scale.For ℓ-dimensional thresholds, the lower bound becomes Ω(ℓ · log^*|X|) = Ω(VC(C) · log^*|X|).
- 1.5 Techniques: The results reduce threshold release and proper learning to the interior-point problem, whose private sample complexity is Ω(log^*|X|).The interior-point mechanism must output an element between the minimum and maximum database values, and the paper gives reductions establishing equivalent sample complexity up to constants.
2 Preliminaries
The paper fixes notation for threshold functions and recalls privacy mechanisms used in its algorithms and reductions. It also states the composition rule for combining differentially private mechanisms.
- [n] = {0, 1, ..., n−1} and log denotes log2 throughout the work.
- THRESHX denotes threshold functions cx over a totally ordered domain X, where cx(y) = 1 iff y ≤ x.
- The Laplace mechanism adds independent Lap(∆/ϵ) noise to each coordinate of a sensitivity-∆ function while preserving ϵ-differential privacy.
- The algorithms access databases through several differentially private mechanisms and use composition to establish overall privacy.
- Composing (ε1, δ1)- and (ε2, δ2)-differentially private mechanisms yields (ε1 + ε2, δ1 + δ2)-differential privacy.
3 The Interior Point Problem
The interior point problem asks for an element between a database’s minimum and maximum, and is closely connected to privately releasing and learning threshold functions. The paper proves an Ω(log^*|X|) private sample-complexity lower bound and develops recursive upper-bound methods, while leaving a gap between the bounds.
- Problem: The interior point problem outputs an x satisfying min D ≤ x ≤ max D, without requiring x to belong to the database.Its sample complexity is the database size n.
- Lower Bound: n ≥ Ω(log^*|X|) samples are required to solve the interior point problem privately with probability at least 3/4 under the stated ε and δ conditions.The lower bound applies for fixed 0 < ε < 1/4 and δ(n) ≤ 1/(50n^2).
- Lower Bound: The lower bound uses recursively constructed hard database distributions whose domains grow rapidly and whose prefix structure enables reductions between adjacent sample sizes.A private solver on the recursively enlarged database would yield a private solver for the preceding hard distribution.
- Lower Bound: The proof is also connected to interior point fingerprinting codes, a variant of fingerprinting codes used for lower bounds in approximate differential privacy.The paper gives a direct proof and separately relates the lemma to this combinatorial construction.
- Upper Bound: RecPrefix is a recursive algorithm for privately solving the interior point problem, with failure probability at most 3βt and privacy parameters (2εN, 2δN) after N recursive calls.Its privacy accounting follows from the recursive steps, choosing mechanism, Laplace mechanism, and composition.
- Open Questions: The roughly 2^log^*|X| upper bound and log^*|X| lower bound leave an open gap in the sample complexity of privately solving the interior point problem.The paper identifies closing this gap, potentially to poly(log^*|X|), as an open problem.
4 Query Release and Distribution Learning
This section defines query release and distribution learning, then establishes reductions connecting threshold release, Kolmogorov-distance learning, and the interior point problem.
- Query Release: Query release outputs simultaneous approximate answers for a family of counting queries on a database.For thresholds, the relevant query class is THRESHX.
- Distribution Learning: Distribution learning with respect to Q outputs a distribution whose query-distance from the target is at most α with probability at least 1 − β.For threshold queries on ordered domains, this distance is Kolmogorov distance between CDFs.
- Connections: Query release on a dataset amounts to learning its empirical distribution, while distribution learning can be obtained from query release on a sufficiently large random sample.These directions establish a close relationship between the two tasks.
- Interior Point Reductions: Threshold release reduces to the interior point problem: accurate threshold answers can yield an interior data-universe element.The converse reduction combines the interior point problem with threshold release on a smaller universe.
- Reductions: Private threshold release and distribution learning are equivalent up to stated accuracy, failure-probability, and sample-size transformations.Theorem 4.12 maps release to distribution learning, while Lemmas 4.13 and 4.14 provide converse and subsampling tools.
5 PAC Learning
This section contrasts private and non-private learning, develops empirical-learning tools, and relates private proper PAC learning of thresholds to the interior point problem.
- Private Learning: Without privacy, thresholds can be PAC learned with Oα,β(1) samples because their VC dimension is 1.The section emphasizes that privacy changes this sample-complexity picture.
- Empirical Learning: An empirical learner must find a low-error hypothesis on every fixed labeled database, unlike PAC learning, whose utility guarantee concerns random examples.Differential privacy nevertheless applies to every neighboring database pair.
- Empirical Learning: Privacy forces every empirical learner to use at least Ω(VC(C)) samples, whereas finding an empirically consistent hypothesis is otherwise trivial.The lower bound also applies to label-private empirical learners.
- Thresholds and Interior Points: Private proper PAC learning of thresholds and the interior point problem have sample complexities related by a Θ(1/α) multiplicative factor.The reductions preserve privacy up to parameter changes and explicitly give factors n/(2α), n/(3α), and 27αn in different directions.
- PAC–Empirical Connections: A private proper PAC learner for thresholds can be converted into a private empirical learner with sample complexity 9m.The converse direction converts empirical learning into PAC learning with additional samples and adjusted accuracy and failure probability.
6 Thresholds in High Dimension
The section extends private threshold lower bounds to conjunctions of independent thresholds in multiple dimensions and transfers them to high-dimensional query release.
- High-Dimensional Thresholds: For ℓ-dimensional threshold conjunctions, private proper learning requires sample complexity n = Ω(ℓ · log^*|X|).Theorem 6.2 establishes this under the stated accuracy, privacy, and δ conditions.
- Hardness Amplification: Conjunctions of ℓ independent concepts amplify private proper-learning hardness from n samples to Ω(ℓn) samples.The construction applies to classes C^ℓ formed by coordinatewise conjunctions.
- Scope of Amplification: The hardness amplification assumes a domain element labeled 1 by every concept, an assumption that excludes some classes such as point functions.Point functions can be privately learned with sample complexity independent of |X|.
- Reduction: The reduction embeds an n-point threshold-learning instance along one randomly selected axis and fills the other axes with independently sampled examples.The resulting multidimensional database is perfectly labeled by a conjunction of coordinate concepts.
- Reduction: The reduction preserves differential privacy because changing one input affects only one entry of the constructed multiset.With probability greater than 1 − 2β, it also recovers an (α/β)-consistent threshold hypothesis, yielding the contradiction.
- Query Release: The same lower bound transfers to releasing queries from THRESHX^ℓ through a private-learning-to-query-release reduction.Theorem 6.7 gives the resulting Ω(ℓ · log^*|X|) sample-complexity bound under its stated δ and accuracy parameters.
7 Mechanism-Dependent Lower Bounds
The section develops mechanism-dependent impossibility results for privately outputting undominated points and learning point functions over infinite domains. It uses reductions, packing, and disjoint good-hypothesis sets to establish these lower bounds.
- Undominated point problem: No (ε,δ)-differentially private mechanism can privately output an element at least as large as a database minimum on an infinite ordered domain without a maximum.The impossibility holds for every sample size n.
- Undominated point problem: A T-bounded undominated-point mechanism would yield an interior-point mechanism on a suitably constructed finite domain.The reduction rounds outputs to thresholds determined by iterates of T.
- Undominated point problem: n = Ω(log^*d) follows from the interior-point lower bound, contradicting existence of a fixed-sample mechanism for arbitrary d.The constructed mechanism solves the interior point problem with probability at least 3/4.
- Point-function learning: Point functions over an infinite domain cannot be privately learned with pure differential privacy using any countable hypothesis class.The theorem rules out even improper learners when their outputs are restricted to a countable class.
- Point-function learning: The point-function lower bound follows by constructing infinitely many pairwise-disjoint good-hypothesis sets inside a finite high-probability subset of the learner’s output class.Differential privacy transfers nontrivial output probability across carefully chosen distributions, while disjointness makes infinitely many such sets impossible.
A The Choosing Mechanism
The choosing mechanism combines a noisy estimate of the best quality with an exponential-mechanism selection among good candidates. Its privacy proof separates outputs appearing in only one neighboring database from shared outputs, while its utility follows from two high-probability events.
- Privacy: The choosing mechanism must satisfy (ε,δ)-differential privacy on neighboring databases, including the failure output ⊥.The proof analyzes arbitrary output sets R and separately handles whether ⊥ belongs to R.
- Proof ingredients: The proof uses sensitivity of OPT and bounded growth of the quality function to control noisy estimation and the number of candidate solutions.OPT has sensitivity at most 1, and at most km candidates can have positive quality on an m-element database.
- Privacy: Outputs appearing only in G(S) have probability at most δ, while shared outputs satisfy a multiplicative e^ε bound between neighboring databases.These two facts control the privacy loss in the main case.
- Utility: The mechanism’s utility analysis combines a lower bound on the noisy optimum with exponential-mechanism selection of a near-optimal candidate.The analysis allocates failure probability across the two events.
- Utility: With probability at least 1 − β, the choosing mechanism outputs a good solution.This follows by a union bound over the two utility events.
B Interior Point Fingerprinting Codes
Interior point fingerprinting codes adapt fingerprinting security to ordered domains, where pirate outputs must lie between coalition codewords. Recursive constructions then connect these codes to differential-privacy lower bounds.
- Definition and security: An interior point fingerprinting code requires every feasible pirate output to lie between the coalition’s smallest and largest codewords.Its security guarantee must hold for every coalition and pirate algorithm.
- Definition and security: The code consists of randomized Gen and Trace algorithms that share state; Trace outputs either a user index or ⊥.Gen samples the ordered codebook used by the tracing procedure.
- Definition and security: Completeness bounds the probability of failing to trace a feasible output, while soundness bounds accusing a user outside the pirate coalition.The respective errors are γ and ξ, with probabilities taken over Gen, Trace, and the pirate algorithm.
- Lower-bound reduction: An interior point fingerprinting code implies that no (ε,δ)-differentially private algorithm solves the interior point problem with probability at least 2/3 under stated error constraints.Lemma B.3 assumes ε ≤ 1, δ ≤ 1/(12n), γ ≤ 1/2, and ξ ≤ 1/(33n).
- Lower-bound reduction: The reduction replaces one coalition member and uses differential privacy to transfer tracing probability, contradicting fingerprinting-code soundness.The transferred probability exceeds ξ for the parameter regime in Lemma B.3.
- Recursive construction: Recursive code constructions use domains whose sizes grow as exponential towers in the number of users, recovering an Ω(log^*|X|) interior-point lower bound.Lemma B.4 gives completeness γ = 0 and soundness ξ on a domain of size at most tower(n + log^*(2n^2/ξ))(1).
- Recursive construction: The construction extends an n-user code by sampling a new codeword and encoding prior codewords through matching base-b(n) prefixes.Tracing either accuses the new user or recursively invokes the n-user tracer.
- Recursive construction: The recursive scheme achieves perfect completeness, and combining its construction with the reduction yields Theorem 1.8.The proof establishes perfect completeness inductively before applying Lemmas B.3 and B.4.