Source-linked AI summary
What Can We Learn Privately?
Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam Smith
TL;DR
The paper asks which learning tasks and concept classes can be performed privately under differential privacy. It develops private learners and characterizes local private learning through statistical queries, showing broad private learnability, efficient parity learning, and a separation between interactive and noninteractive local learning.
Problem
The paper asks what computational learning tasks and concept classes can be performed while maintaining privacy, extending privacy research beyond releasing approximations to fixed database functions.
Method
The paper constructs generic private agnostic learners, an efficient private PAC learner for parity functions, and simulations relating local private algorithms to statistical query algorithms.
Results
Private agnostic learning uses a sample size approximately logarithmic in |C|, local learnability equals SQ learnability, and parity and masked-parity separate private, SQ, and nonadaptive SQ learning classes.
Takeaways & Limitations
Ignoring computational constraints, concept classes learnable with polynomial sample complexity and output size can also be learned privately with polynomially many samples.
Takeaways & Limitations
The masked-parity separation between adaptive and nonadaptive SQ learning is established under the uniform distribution, while the distribution-free separation remains open.
Abstract
from arXiv · showhide
Learning problems form an important category of computational tasks that generalizes many of the computations researchers apply to large real-life data sets. We ask: what concept classes can be learned privately, namely, by an algorithm whose output does not depend too heavily on any one input or specific training example? More precisely, we investigate learning algorithms that satisfy differential privacy, a notion that provides strong confidentiality guarantees in contexts where aggregate information is released about a database containing sensitive information about individuals. We demonstrate that, ignoring computational constraints, it is possible to privately agnostically learn any concept class using a sample size approximately logarithmic in the cardinality of the concept class. Therefore, almost anything learnable is learnable privately: specifically, if a concept class is learnable by a (non-private) algorithm with polynomial sample complexity and output size, then it can be learned privately using a polynomial number of samples. We also present a computationally efficient private PAC learner for the class of parity functions. Local (or randomized response) algorithms are a practical class of private algorithms that have received extensive investigation. We provide a precise characterization of local private learning algorithms. We show that a concept class is learnable by a local algorithm if and only if it is learnable in the statistical query (SQ) model. Finally, we present a separation between the power of interactive and noninteractive local learning algorithms.
1 Introduction
The paper asks which learning tasks remain feasible under differential privacy and develops results spanning sample complexity, computational efficiency, and interaction. It shows broad private learnability, an efficient private learner for parity, an SQ characterization of local learning, and an interaction separation.
- Private learning foundations: Private agnostic learning uses a number of samples proportional to log |C| for any concept class C, although the learner is not necessarily computationally efficient.This is presented as a private analogue of the cardinality version of Occam’s razor.
- Efficient private learning: A computationally efficient, distribution-free differentially private PAC learner for parity has sample and time complexity comparable to the best non-private learner.The parity learner uses roughly 1/ϵ times more samples and about the same computation time as the non-private learner.
- Local and SQ learning: A concept class is learnable by a local differentially private algorithm if and only if it is learnable in the statistical query model.The equivalence connects local randomization with SQ learning and preserves the correspondence between interaction and adaptivity.
- Interaction and adaptivity: Masked-parity is efficiently learnable by interactive local algorithms under the uniform distribution but requires exponentially many samples for noninteractive local learning.The equivalence with SQ learning also separates adaptive from nonadaptive SQ learning, under the stated distributional setting.
- Private learning foundations: Polynomial sample complexity and polynomial output size imply private learnability with a polynomial number of samples, possibly in exponential time.The result establishes feasibility of private learning when computation is unrestricted.
- Classes of private learning algorithms: The class relationships satisfy LNI*=NASQ* ⊊ LI*=SQ* ⊊ PPAC*=PAC*, with parity and masked-parity providing the separations.These relationships account for sample complexity but not computational efficiency.
2 Preliminaries
The paper formalizes databases, differential privacy, and distribution-free learning, then defines PAC and agnostic learning through labeled examples and misclassification error.
- Privacy preliminaries: A statistical database is a vector whose entries represent information contributed by individuals.Neighboring databases differ in one entry, and algorithms are evaluated on their output distributions.
- Privacy preliminaries: Differential privacy requires neighboring databases to induce nearby output distributions for every output set.The probability is over the randomized algorithm’s coins.
- Privacy preliminaries: Differential privacy composes across multiple private algorithms, with privacy parameters accumulating across the composition.Post-processing the combined outputs preserves the resulting privacy guarantee.
- Learning preliminaries: A concept class contains functions labeling examples, while a hypothesis is evaluated by its misclassification error on a labeled-example distribution.The paper focuses on binary classification and defines err(h) as the probability that h(x) differs from y.
- Learning preliminaries: PAC learning uses i.i.d. examples labeled by a target concept, whereas agnostic learning permits arbitrary labeled-example distributions and compares error with the best concept-class error.Both frameworks quantify success using accuracy and failure parameters α and β.
- Efficiency measures: The paper distinguishes polynomial sample complexity from efficient private learning, which additionally requires polynomial computation time.Its asymptotic complexity parameter is the binary description length d of examples.
3 Private PAC and Agnostic Learning
Private PAC learning combines differential privacy with predictive utility, and the paper develops a generic exponential-mechanism learner whose sample complexity depends logarithmically on the hypothesis-class size.
- Definitions: Private PAC learning requires both differential privacy and PAC utility, while private agnostic learning replaces PAC utility with agnostic utility.The privacy requirement is worst-case, whereas learning utility is evaluated over i.i.d. examples or an agnostic distribution.
- Generic private learner: Finding a good hypothesis is harder than privately evaluating a fixed hypothesis because the hypothesis space may be exponentially large.The paper addresses this search problem with the exponential mechanism.
- Generic private learner: The private learner scores hypotheses by negative empirical mistakes and samples hypotheses with probability proportional to an exponential function of that score.Changing one example changes the score by at most 1, yielding differential privacy.
- Generic private learner: n = O((ln |H_d| + ln 1/β)/α^2) labeled examples suffice for private agnostic learning when H_d = C_d, although the learner may be inefficient.The theorem applies when the concept-class cardinality is at most exp(poly(d)).
- Sample complexity: Compared with non-private agnostic learning, the private bound incurs a factor O(α/ϵ) when α > ϵ and no factor difference when α ≤ ϵ.For PAC learning, the private and non-private bounds differ by O(1/ϵ).
- Implications: A concept class with a polynomial-output-length non-private learner can be privately learned with polynomially many samples, potentially using exponential computation time.The hypothesis class induced by the learner’s output has at most exponentially many hypotheses.
- Compression: Compression alone does not guarantee privacy because a compressed output may reveal a few training examples directly.The paper extends its theorem to obtain a private PAC learner with an expected sample count similar to the compression algorithm.
- VC dimension: Every concept class is privately agnostically learnable with n = O((VC DIM(C_d) · ln |X_d| + ln 1/β)/α^2) examples, without an efficiency guarantee.This is a VC-dimension corollary of the generic private learner.
4 An Efficient Private Learner for PARITY
The paper constructs an efficient private PAC learner for PARITY by subsampling examples, solving the resulting linear system, and privately amplifying success. It proves privacy and utility, with private and non-private sample bounds differing by only a logarithmic-confidence factor over ϵ.
- Motivation: The standard PARITY learner solves linear equations for the hidden vector, but fails on databases inconsistent with every parity function.The private learner must specify output behavior on all databases, including inconsistent ones.
- Privacy: Adding one example shrinks the space of consistent parity hypotheses by at most a factor of 2, enabling differential privacy.The construction relies on this bound when comparing outputs on neighboring databases.
- Algorithm: The private algorithm includes each example independently with probability p = ϵ/4, solves the induced equations by Gaussian elimination, and samples a consistent parity uniformly.If the solution space is empty, it outputs ⊥.
- Amplification: The learner amplifies constant success by generating multiple hypotheses and selecting one using Laplacian-noised training errors.The perturbed errors are released privately because training-error sensitivity is 1/s.
- Guarantees: Theorem 4.4 establishes that A∗ efficiently and privately PAC learns PARITY, while its private sample bound exceeds the non-private bound by O(ln(1/β)/ϵ).The non-private case requires O((d+ln(1/β))/α) labels.
5 Local Protocols and SQ learning
The paper establishes an equivalence between local private learning and statistical-query learning under i.i.d. inputs, including preservation of efficiency and interaction structure. This equivalence yields strict limitations for local learners and a separation between interactive and noninteractive learning under the uniform distribution.
- Equivalence of Local and SQ Models: Local and SQ models are equivalent when database entries are sampled i.i.d. from D, with query complexity preserved up to polynomial factors.Each model can simulate the other under the stated sampling condition.
- Equivalence of Local and SQ Models: An SQ algorithm making at most t queries with tolerance τ can be simulated privately using n ≥ c·t log(t/β)/ϵ^2τ^2 database entries.The simulation matches the SQ output with probability at least 1−β.
- Equivalence of Local and SQ Models: The SQ-to-local simulation is noninteractive when the SQ algorithm is nonadaptive and efficient when the original SQ algorithm is efficient.The reverse simulation uses O(t·e^ϵ) expected SQ queries with accuracy τ = Θ(β/(e^2ϵt)).
- Implications for Local Learning: A concept class is locally learnable if and only if it is SQ learnable, with interactive and noninteractive models corresponding to adaptive and nonadaptive learning.The correspondence also preserves efficient computation under transparent randomizers.
- Implications for Local Learning: Local learners form a strict subset of privately PAC-learnable concept classes, even with unlimited computation.PARITY is privately learnable but is subject to SQ lower bounds that rule out corresponding local learners.
- The Power of Interaction in Local Protocols: MASKED-PARITY is efficiently learnable interactively but requires exponentially many examples noninteractively under the uniform distribution.The separation transfers between SQ and local models, showing that adaptivity or interaction can provide substantial power.
- The Power of Interaction in Local Protocols: The interaction separation applies only to strong learning, while separating adaptive from nonadaptive distribution-free learning remains open.The MASKED-PARITY results concern learnability under the uniform distribution.
A Concentration Bounds
The paper records standard concentration tools, including Chernoff-Hoeffding bounds and a bound for sums of Laplace random variables. The Laplace bound is derived using moment-generating functions and included because no suitable reference was found.
- The appendix states multiplicative Chernoff bounds for independent Bernoulli random variables.
- It also states a real-valued additive Chernoff-Hoeffding bound for independent bounded random variables.
- A lemma gives a concentration bound for sums of independent Laplace random variables.
- The authors include the Laplace lemma because they could not find an appropriate reference, although its proof is standard.
- The Laplace-sum proof bounds the moment-generating function of the sum by raising the single-variable moment-generating function to the nth power.