Bounds on the sample complexity for private learning and private data release

Shiva Prasad KasiviswanathanOSTI 2024 · OpenAlex

This paper, a collaboration between researchers at Los Alamos National Laboratory and Ben-Gurion University, investigates the "privacy tax" of machine learning. It explores how much more data is required to learn a concept when we must also guarantee the privacy of the individuals in the training set.

TL;DR

The authors prove that the standard metric for learning complexity (VC-dimension) fails to characterize the data needs of private learning. They demonstrate that "proper" private learners (which must output a hypothesis from the target class) require significantly more data than "improper" ones, and that computational efficiency comes at the cost of even higher sample complexity.

What Problem Does This Paper Address?

In classical machine learning, specifically the Probably Approximately Correct (PAC) framework, the amount of data you need to learn a concept (sample complexity) is neatly tied to the VC-dimension of the concept class. If a concept is simple (low VC-dimension), you don't need much data.

However, when you add Differential Privacy (DP) to the mix—ensuring that the presence or absence of any single individual in the dataset doesn't significantly change the output—the rules change. Previous research suggested that private learning was always possible but often required data proportional to the logarithm of the size of the hypothesis class, which can be much larger than the VC-dimension.

The authors ask: Is this extra data requirement a fundamental law of private learning, or just a limitation of our current algorithms? Does the distinction between "proper" learning (outputting a hypothesis from the target class) and "improper" learning (outputting any predictive function) matter more under privacy constraints?

Methods

The authors use a "canary" concept class called $POINT_d$ to probe these questions. $POINT_d$ consists of functions that are 0 everywhere except at one specific point in a domain of size $2^d$.

  • Lower Bound Proofs: They use information-theoretic arguments to show that any proper private learner for $POINT_d$ must "leak" too much information unless it has a large number of samples.
  • Algorithm Construction: They develop a novel efficient improper private learner. This algorithm uses a "sampling-to-privacy" technique: it picks a small random subset of the data, runs a non-private learner, and then "noises" the output. To make it computationally efficient, they use Pseudorandom Functions (PRFs) to compress the description of the resulting hypothesis.
  • Separation Logic: By comparing the sample needs of different types of learners (proper vs. improper, efficient vs. inefficient) on the same concept class, they mathematically prove "separations"—gaps in complexity that don't exist in the non-private world.

Datasets

As a theoretical computer science paper, this work does not use empirical "real-world" datasets (like ImageNet or MNIST). Instead, it relies on:

  • Synthetic Concept Classes: Specifically $POINT_d$ and a variant $\widetilde{POINT}_d$ constructed using Pseudorandom Generators (PRGs) to prove the gap between efficient and inefficient learners.
  • Mathematical Frameworks: The results are evaluated against the discretized domain $X = \{1, \dots, 2^d\}$.

Key Insights and Ideas

  • VC-Dimension is Not Enough: In standard learning, $POINT_d$ has a VC-dimension of 1, meaning it's incredibly easy to learn. The authors show that for proper private learning, you need $\Omega(d)$ samples. This proves that VC-dimension cannot be the sole measure of private sample complexity.
  • The Power of Improper Learning: In the non-private world, improper learning is mostly a tool for computational efficiency. Here, it is a tool for data efficiency. An improper private learner can learn $POINT_d$ with $O(1)$ samples, while a proper one needs $\Omega(d)$.
  • The Efficiency Tax: The authors provide the first example where requiring a private algorithm to run in polynomial time (efficiency) actually forces you to use more data than an inefficient algorithm would need.
  • Sanitization Limits: For the task of "private data release" (creating a synthetic version of a dataset), they prove that a logarithmic dependence on the size of the domain is unavoidable, providing a tight lower bound for existing algorithms.

Key Results

The main findings are summarized in the paper's "Separation Results" table:

Concept Class Non-Private Learning Improper Private Proper Private
$POINT_d$ $\Theta(1)$ $\Theta(1)$ $\Theta(d)$
  • Proper vs. Improper: There is a massive gap ($\Theta(1)$ vs $\Theta(d)$) between what improper and proper learners can do with the same amount of data under privacy.
  • Efficiency Gap: For the $\widetilde{POINT}_d$ class, an inefficient proper learner needs very few samples, while an efficient one requires $\Omega(d)$.
  • Data Release: They prove that any useful, private non-interactive sanitizer for $POINT_d$ requires a database of size $\Omega(d)$, confirming that the domain size is a fundamental bottleneck for data privacy.

Limitations and Future Work

The authors acknowledge that while they have found tight bounds for specific classes like $POINT_d$, a general "Universal Characterization" (a private equivalent to VC-dimension) for all concept classes remains elusive.

Future work suggested by the paper includes:

  1. Finding a new combinatorial measure (beyond VC-dimension) that perfectly predicts private sample complexity.
  2. Exploring if these gaps exist for more "natural" or commonly used machine learning models like halfspaces or decision trees.
  3. Investigating the trade-offs in the "local" model of privacy, where data is noised before it even reaches the learner.

Summary updated

Abstract

Learning is a task that generalizes many of the analyses that are applied to collections of data, and in particular, collections of sensitive individual information. Hence, it is natural to ask what can be learned while preserving individual privacy. [Kasiviswanathan, Lee, Nissim, Raskhodnikova, and Smith; FOCS 2008] initiated such a discussion. They formalized the notion of private learning, as a combination of PAC learning and differential privacy, and investigated what concept classes can be learned privately. Somewhat surprisingly, they showed that, ignoring time complexity, every PAC learning task could be performed privately with polynomially many samples, and in many natural cases this could even be done in polynomial time. While these results seem to equate non-private and private learning, there is still a significant gap: the sample complexity of (non-private) PAC learning is crisply characterized in terms of the VC-dimension of the concept class, whereas this relationship is lost in the constructions of private learners, which exhibit, generally, a higher sample complexity. Looking into this gap, we examine several private learning tasks and give tight bounds on their sample complexity. In particular, we show strong separations between sample complexities of proper and improper private learners (such separation does not exist for non-private learners), and between sample complexities of efficient and inefficient proper private learners. Our results show that VC-dimension is not the right measure for characterizing the sample complexity of proper private learning. We also examine the task of private data release (as initiated by [Blum, Ligett, and Roth; STOC 2008]), and give new lower bounds on the sample complexity. Our results show that the logarithmic dependence on size of the instance space is essential for private data release.
BibTeX
@inproceedings{kasiviswanathan2024bounds,
  author = {Shiva Prasad Kasiviswanathan},
  title = {{Bounds on the sample complexity for private learning and private data release}},
  booktitle = {OSTI},
  year = {2024},
}

Loading related content...

Figure