PaperlayerView exact revision on arXiv

Source-linked AI summary

Private Learning and Sanitization: Pure vs. Approximate Differential Privacy

Amos Beimel, Kobbi Nissim, Uri Stemmer

arXiv:1407.2674v1cs.LGcs.CRstat.ML

TL;DR

The paper compares sample complexity for private learning and sanitization under pure versus approximate differential privacy. It defines quasi-concave promise problems and develops recursive private algorithms, finding substantially lower sample complexity under approximate privacy for several tasks.

  • Problem

    The paper asks how sample complexity for private learning and sanitization differs between pure and approximate differential privacy while protecting individuals’ sensitive data.

  • Method

    The paper defines quasi-concave promise problems and uses recursive private approximation of smaller instances to construct efficient algorithms.

  • Results

    Approximate differential privacy can require significantly fewer samples than pure privacy for learning and sanitizing POINTd and THRESHd, with additional learners for high-dimensional axis-aligned rectangles.

  • Takeaways & Limitations

    The constructions separate pure and approximate privacy sample complexity for several learning and sanitization tasks and provide time-efficient algorithms.

  • Takeaways & Limitations

    No lower bounds are known for approximate-private learners, and no generic construction is known to improve on the pure-private sample complexity construction.

Abstract

from arXiv · show

We compare the sample complexity of private learning [Kasiviswanathan et al. 2008] and sanitization~[Blum et al. 2008] under pure $ε$-differential privacy [Dwork et al. TCC 2006] and approximate $(ε,δ)$-differential privacy [Dwork et al. Eurocrypt 2006]. We show that the sample complexity of these tasks under approximate differential privacy can be significantly lower than that under pure differential privacy. We define a family of optimization problems, which we call Quasi-Concave Promise Problems, that generalizes some of our considered tasks. We observe that a quasi-concave promise problem can be privately approximated using a solution to a smaller instance of a quasi-concave promise problem. This allows us to construct an efficient recursive algorithm solving such problems privately. Specifically, we construct private learners for point functions, threshold functions, and axis-aligned rectangles in high dimension. Similarly, we construct sanitizers for point functions and threshold functions. We also examine the sample complexity of label-private learners, a relaxation of private learning where the learner is required to only protect the privacy of the labels in the sample. We show that the VC dimension completely characterizes the sample complexity of such learners, that is, the sample complexity of learning with label privacy is equal (up to constants) to learning without privacy.

1 Introduction

The paper compares private learning and sanitization under pure and approximate differential privacy, finding substantially lower sample complexity in the approximate setting. It develops recursive methods for quasi-concave promise problems and applies them to several concept classes, while characterizing label-private learning through VC dimension.

  • 1 Introduction: Approximate differential privacy can require significantly fewer samples than pure differential privacy for private learning and sanitization.The paper emphasizes that even negligible δ > 0 can substantially affect sample complexity.
  • Sanitization: The paper constructs sanitizers for point and threshold functions with sample complexity significantly below prior pure-private bounds.Sanitizer construction is not generally computationally feasible, although the paper’s learning algorithms are time-efficient.
  • 1.1 Our Contributions: The paper introduces Quasi-Concave Promise Problems and an efficient recursive private algorithm based on reducing problems to smaller instances.Threshold learning fits this framework, while threshold sanitization is handled through iterative use of a small number of such problems.
  • 1.1 Our Contributions: New time-efficient private algorithms address point functions, threshold functions, and discrete axis-aligned rectangles, separating approximate from pure private learning.The constructions improve on prior sample-complexity bounds for these classes.
  • Sanitization vs. Private Learning: A reduction from private learning to sanitization yields an explicit predicate class whose every private sanitizer requires databases of size Ω(VC(C) log |X|).This makes lower bounds for private learning applicable to unrestricted-access sanitization.
  • Label Privacy: For label-private learning, VC dimension characterizes sample complexity up to constants, matching non-private learning despite label privacy.Label privacy protects only the sample labels rather than the entire sample.

2 Preliminaries

The paper establishes notation for domains, Cartesian powers, distributions, and asymptotic notation used throughout its analysis.

  • O_γ(f(t)) abbreviates O(h(γ)·f(t)) for some non-negative function h.
  • The notation Õ(f(t)) denotes O(f(t)·polylog(f(t))).
  • X denotes an arbitrary domain, while X^d denotes the domain {0, 1}^d.
  • X^m is the mth Cartesian power of X, and X* is the union of X^m over all m ≥ 0.
  • For a distribution D, D(j) is the probability of j and D(J) is the probability of membership in J.

2.1 Differential Privacy

Differential privacy limits how much changing one database entry can alter an algorithm’s output distribution. The section distinguishes pure and approximate privacy and states basic composition guarantees for repeated private interactions.

  • Differential privacy: Differential privacy requires that changing one database entry does not significantly change the algorithm’s output distribution.
  • Differential privacy: Neighboring databases differ in exactly one entry, and privacy compares output probabilities for every event across such databases.
  • Pure and approximate privacy: Pure differential privacy is the case δ = 0, whereas approximate differential privacy allows δ > 0, typically negligible in database size m.
  • Composition: Combining mechanisms with parameters (ε1, δ1) and (ε2, δ2) yields privacy parameters (ε1 + ε2, δ1 + δ2).
  • Composition: k adaptive interactions satisfy (kε, kδ)-differential privacy under basic composition, while stronger composition gives ε′, kδ + δ′ with ε′ roughly kε + kε^2.

2.2 Preliminaries from Learning Theory

Learning theory characterizes PAC sample complexity through VC dimension and generalization bounds. The section defines concepts, hypotheses, dichotomies, shattering, and the distinction between proper and improper learning.

  • PAC learning: A concept class contains predicates mapping a domain X to {0, 1}, and learning outputs a hypothesis approximating an unknown target concept.
  • PAC learning: PAC learning requires an output hypothesis to achieve bounded error with high probability over sampled examples and learner randomness.
  • PAC learning: If H ⊆ C, the learner is proper; otherwise, it is improper.
  • VC dimension: A set B induces the dichotomies Π_C(B), the binary labelings realized by C on B, and shattering occurs when Π_C(B) = {0, 1}^ℓ.
  • VC dimension: The VC dimension is the size of the largest domain subset whose every binary labeling is realized by the concept class.
  • Sample complexity: A sample of size Θ(VC(C)) is necessary and sufficient for PAC learning, while consistent hypotheses in C yield PAC learners under the stated bounds.

2.3 Private Learning

Private learning combines PAC learning with differential privacy. Its utility is evaluated on typical labeled samples, while privacy must hold for every pair of neighboring databases.

  • Private learning: Private learning seeks the PAC objective while protecting the privacy of the input database.
  • Definition: A private PAC learner must satisfy both (ε, δ)-differential privacy and PAC utility for its concept and hypothesis classes.
  • Definition: When δ = 0, the privacy parameter list omits δ and the learner is treated as purely private.
  • Requirements: Utility is an average-case requirement over i.i.d. correctly labeled samples, whereas privacy is a worst-case requirement over all neighboring databases.

2.4 Sanitization

Sanitization privately releases a database or estimator that preserves counting queries for every concept in a class. The section defines proper and improper sanitizers and reviews sample-complexity and size transformations.

  • Definitions: A sanitizer outputs a database or estimator whose counting queries approximate those of the input database for every concept in the class.For concept c, Qc(S) is the fraction of database entries satisfying c.
  • Definitions: An improper sanitizer outputs an estimator α-close to the input database with probability at least 1 − β.An estimator is α-close when every concept query differs from the true query by at most α.
  • Definitions: A proper sanitizer instead outputs a database whose counting queries define the estimator; when δ = 0, the privacy notation omits δ.The distinction is based on whether the estimator is induced by an actual database.
  • Transformations: Ignoring computational complexity, every improper sanitizer can be transformed into a proper sanitizer with twice the error, using the triangle inequality.The transformation finds a database α-close to the estimator, which is then 2α-close to the input database.
  • Sample complexity: Known pure-privacy sanitization bounds include a general upper bound, a lower bound for databases of size at most VC(C), and possible inefficiency.The upper-bound theorem states existence for sufficiently large m; the surrounding discussion notes that m may reach the representation size of elements in X.
  • Transformations: Theorem 2.21 gives a fixed-size sanitized database with size O(VC(C)), independent of the input database size, while the transformation doubles error.The construction finds a database of n entries α-close to the original sanitized database, yielding 2α closeness to the input with high probability.

2.5 Basic Differentially-Private Mechanisms

This section introduces the Laplace and exponential mechanisms and an alternative propose-test-release algorithm. Their stated properties connect sensitivity or score gaps to privacy and utility guarantees.

  • Laplace mechanism: A sensitivity-k function changes by at most k in ℓ1 distance on neighboring databases.Sensitivity measures the maximum total coordinate change between neighboring inputs.
  • Laplace mechanism: The Laplace mechanism adds independent Lap(k/ε) noise to each output coordinate and preserves ε-differential privacy.The mechanism applies noise to every coordinate of the function’s output.
  • Exponential mechanism: The exponential mechanism probabilistically selects a solution, assigning larger probability to solutions with higher quality scores.Its goal is to approximately maximize a quality function over a finite solution set.
  • Private learning: Using training accuracy as quality, the exponential mechanism yields a generic private proper learner for every finite concept class.The stated sample complexity is Oα,β,ε(log |C|).
  • Adist: Adist uses a noisy gap between the two highest-scoring solutions under the assumption that the best solution is sufficiently separated.It instantiates the Propose-Test-Release framework for sensitivity-1 quality functions.
  • Adist: Adist is (ε,δ)-differentially private and outputs the highest-scoring solution with probability at least 1 − β when the score gap meets the stated threshold.The threshold depends on β and δ.

2.6 Concentration Bounds

The section introduces independent Bernoulli variables and notes that their sum has expectation pn and is concentrated around this expectation by Chernoff bounds.

  • Bernoulli sums: For n independent Bernoulli variables with success probability p, the expected sum is pn.Each variable equals 1 with probability p and 0 otherwise.
  • Bernoulli sums: Chernoff bounds establish concentration of the Bernoulli sum around its expectation for 0 < δ < 1.The supplied passage states the parameter range but does not include the explicit bound.

3 Learning with Approximate Privacy

The paper develops proper learners under approximate differential privacy for point and threshold functions, using stability for points and recursive quasi-concave optimization for thresholds. These constructions separate approximate-private learning from pure-private learning in sample complexity.

  • Point functions: Pure-private proper learning for POINTd requires Ω(d) samples, despite VC(POINTd)=1 and constant-sample non-private proper learning.An improper pure-private learner can nevertheless use O_{α,β,ε}(1) samples.
  • Point functions: Approximate-private proper learning achieves O_{α,β,ε,δ}(1) sample complexity for POINTd, separating it from pure-private proper learning.The learner counts positive examples for each point and applies Adist to identify a high-quality candidate.
  • Point functions: For POINTd, the quality function counts appearances of each positively labeled point, making the target point distinguishable when its distributional mass is noticeable.The algorithm returns the selected point function, or samples a point function when Adist outputs ⊥.
  • Threshold functions: Approximate-private proper learning for THRESHd uses a recursive quasi-concave optimization procedure and has sample complexity roughly 2^{O(log*(d))}.The construction first locates a good interval, refines it, and then uses the exponential mechanism to choose a threshold endpoint.
  • High-dimensional extensions: The paper also extends approximate-private learning to axis-aligned rectangles and constructs an efficient sanitizer for THRESHd.The rectangle learner composes one execution per axis, while the threshold sanitizer is used to privately find interval boundaries.

4 Sanitization with Approximate Privacy

The section develops approximate-private sanitizers using bounded-growth choosing and recursive quasi-concave optimization, then contrasts their sample complexity with pure-private lower bounds. It gives constructions for point and threshold predicates and derives general sanitization bounds.

  • Approximate-private sanitizers: Approximate-private sanitizers are constructed for point and threshold predicates, separating the database sizes sufficient under (ε,δ)-privacy from those necessary under pure privacy.The section states these constructions and explicitly frames them as a separation between (ε,0)-private and (ε,δ)-private sanitization.
  • Choosing mechanism: A k-bounded-growth quality function changes each solution's score by at most one when a record is added, while increasing at most k solution scores.This property implies sensitivity 1 and limits the number of candidate solutions whose scores can increase.
  • Choosing mechanism: The choosing mechanism privately tests whether a sufficiently good solution exists, then applies the exponential mechanism to a small candidate set rather than the full solution space.The mechanism returns ⊥ when no good solution exists and otherwise chooses from G(S), the solutions meeting the quality threshold.
  • Choosing mechanism: For a k-bounded-growth quality function, the choosing mechanism outputs an α-good solution with probability at least 1 − β using a database whose size depends on α, β, ε, and δ.The stated guarantee applies when the database size satisfies the condition in Lemma 4.5.
  • Point sanitization: SanPoints uses point frequencies as a 1-bounded-growth quality function and invokes the choosing mechanism to construct an approximate-private sanitizer for point functions.The same approach extends to k-POINTd, whose concepts accept exactly a k-element subset of the domain.
  • Threshold sanitization: For threshold predicates, the sanitizer produces a database whose query fractions differ from the input by at most α for every threshold, with probability at least 1 − 3cβ.The construction invokes at most 4c approximate-private mechanisms and obtains the stated threshold-query accuracy guarantee.
  • Pure-private sanitization: Pure-private sanitizers for a concept class require m = Ω(log(XC) + VC(C)) samples, while the described improper sanitizer uses Oα,β,ε(log(XC) + VC(C) log VC(C)).The lower bound is stated for any sanitizer, and the upper bound is given for the described improper construction.

5 Sanitization and Proper Private PAC

This section establishes reductions between sanitization and proper private learning, then uses them to transfer sample-complexity bounds and privacy guarantees. Sanitization for a concept class yields proper private learning for that class through the modified class Clabel.

  • Sanitization and Private Learning: The reduction from private learning to sanitization applies even to arbitrary sanitizers, not only sanitizers restricted to statistical queries.This complements an earlier statistical-query reduction by showing that arbitrary sanitizer access also implies a private learner.
  • Sanitization Implies Proper PPAC: An (α, β, ǫ, m)-sanitizer for C yields a ((2α + 2β), β, ǫ, qm)-sanitizer for C when q is sufficiently large.The proof partitions a database into q blocks, sanitizes each block, and concatenates the sanitized outputs; Chernoff bounds control the fraction of good blocks.
  • Sanitization Implies Proper PPAC: A sanitizer for Clabel with sufficient database size yields a proper ((2α + γ), 2β, ǫ, m)-PPAC learner for C.The construction sanitizes the sample and outputs a concept minimizing empirical error on the sanitized database.
  • Sanitization Implies Proper PPAC: A sanitizer for C can be converted into a sanitizer for Clabel, enabling a reduction from sanitization to proper private learning.Clabel augments examples with a label bit and preserves VC dimension within a factor of two.
  • Sanitization Implies Proper PPAC: Combining the reductions, a sanitizer for C gives a proper ((15α + 12β), 10β, 6ǫ, t)-PPAC learner for C, where t = Oα,β,ǫ(m).The reduction is efficient when the sanitizer and a non-private learner for C are efficient.
  • A Lower Bound for k-POINTd: Lower bounds for pure-private learners transfer through the reduction to lower bounds on database size for pure-private sanitizers.For k-POINTd, the resulting bounds involve VC(k-POINTd) and log |Xd|; a second application of the reduction can strengthen the bound.

6 Label-Private Learners

This section studies learning when only labels require privacy and shows that VC dimension characterizes the resulting sample complexity. It also extends the model to semi-private learning when the data distribution is public.

  • Generic Label-Private Learner: Label-private learning protects the labels while allowing the learner to treat the example identities as non-private.The algorithm must be differentially private as a function of the label database for every fixed unlabeled sample.
  • Generic Label-Private Learner: VC dimension characterizes label-private sample complexity: for every α, β, ǫ, a learner exists with m = Oα,β,ǫ(VC(C)) samples.The theorem states that the learner need not be efficient.
  • Generic Label-Private Learner: The generic label-private learner builds hypotheses from an unlabeled sample and uses the exponential mechanism to select among them using the labels.The constructed hypothesis set contains one representative for every labeling realized by the concept class on the sampled points.
  • Generic Label-Private Learner: The learner achieves an α-good hypothesis with failure probability at most β when the sampling and exponential-mechanism events hold with high probability.The utility analysis combines generalization control with the exponential mechanism’s selection guarantee.
  • Label Privacy Extension: Semi-private learning protects the entire labeled sample while treating an unlabeled database representing the distribution as public.For every fixed distribution database D, the algorithm must preserve differential privacy over the labeled input.
  • Label Privacy Extension: Semi-private learning has sample complexity Oα,β,ǫ(VC(C)), matching the non-private order when the relevant distribution is publicly known.The corresponding lower bound is Ω(VC(C)).
Loading 1407.2674v1…