Differentially Private Learning of Structured Discrete Distributions

Ilias Diakonikolas, Moritz Hardt, Ludwig SchmidtNeurIPS 2015 · OpenReview

TL;DR

This paper introduces a novel framework for learning structured discrete probability distributions—such as histograms or unimodal distributions—while guaranteeing rigorous Differential Privacy (DP). The authors show that the "privacy tax" (the additional samples and computational time required for privacy) is remarkably low. Their algorithms are nearly as efficient as non-private counterparts, even when applied to massive data domains.

The Challenge of Private Density Estimation

In modern data science, density estimation is a fundamental task: given a set of samples, how do we determine the underlying probability distribution? However, when these samples contain sensitive individual data (like medical records or financial transactions), the resulting model can inadvertently leak information about specific individuals.

Differential Privacy (DP) offers a mathematical guarantee against such leaks. Historically, private density estimation forced a trade-off: you could achieve privacy, statistical accuracy, or computational speed, but rarely all three simultaneously. Previous private algorithms scaled poorly with the domain size ($N$), rendering them impractical for high-precision data where $N$ might exceed $10^{18}$. This paper addresses a critical question: Can we learn structured distributions privately with near-optimal sample sizes and near-linear running time?

A New Framework for Structured Distributions

The authors bridge the gap between privacy and efficiency by focusing on structured distributions—those that can be well-approximated by piecewise polynomials, including monotone, log-concave, and mixture models.

Their core contribution is a two-step framework:

  1. Private Kolmogorov Approximation: Instead of attempting to match the distribution directly (which is notoriously difficult to do privately), the algorithm approximates the Cumulative Distribution Function (CDF). They introduce a greedy, iterative algorithm called the MAXIMUMERRORRULE (MERR). In each step, MERR identifies the interval where the current estimate deviates most from the data and adds a new "piece" to the approximation.
  2. The Choosing Mechanism: To ensure MERR remains private, the authors employ a "choosing mechanism" that selects these intervals without overly relying on any single data point. Crucially, this subroutine runs in time logarithmic to the domain size ($\log N$), enabling it to handle massive scales efficiently.
  3. Agnostic Learning: The framework is "agnostic," meaning it remains robust even if the true distribution doesn't perfectly fit the assumed structure (e.g., if it is "mostly" unimodal but contains some noise).
Iterative piecewise approximation of a CDF using the MERR algorithm.

Experimental Validation

The authors evaluated their approach using both synthetic and real-world data:

  • Synthetic Mixture Models: Used to rigorously test how the algorithm scales with varying domain sizes and sample counts.
  • Higgs Boson Data: The authors used the "lepton $p_T$" (transverse momentum) feature from high-energy physics experiments. With roughly 11 million samples and 18 digits of precision, the effective domain size is a staggering $N = 10^{18}$. This served as a rigorous "stress test" for the algorithm's efficiency.

Key Insights and Results

  • The "Privacy Tax" is Small: For many natural distribution families, the cost of adding privacy is merely a small multiplicative factor in sample complexity. The authors match non-private rates up to a factor of $O(2^{\log^* N})$, where $\log^*$ is the iterated logarithm (essentially a constant in practice).
  • Kolmogorov Distance as a Catalyst: By optimizing for Kolmogorov distance (the maximum difference between CDFs) rather than Total Variation distance, the authors utilized a metric that is easier to satisfy privately, yet strong enough to imply high accuracy for structured distributions.
  • Sub-logarithmic Dependence: This is the first implemented DP learner that scales to massive domains with a sub-logarithmic dependence on the domain size in its approximation guarantee.
Performance on the Higgs dataset showing Kolmogorov error and running time across different sample sizes and iterations (m).

Empirically, the results are striking:

  • Speed: On the massive Higgs dataset ($10^7$ samples, $10^{18}$ domain size), the private algorithm runs in less than 5 seconds. This is only about 7x slower than simply sorting the data—a mandatory baseline step for almost any distribution learner.
  • Accuracy: As the number of samples ($n$) increases, the error of the private MERR algorithm quickly converges toward the non-private baseline.
  • Theoretical Optimality: The paper provides the first computationally efficient $(\epsilon, \delta)$-DP agnostic learners for piecewise polynomials with near-optimal sample complexity.

Limitations and Future Work

While groundbreaking, the framework has areas for future refinement:

  • Hyperparameter Tuning: The number of iterations ($m$) in the MERR algorithm currently requires manual selection. Developing an adaptive method to choose this parameter dynamically would be a significant enhancement.
  • Constant Factors: Although the scaling is theoretically optimal, the "hidden constants" in the privacy analysis of the choosing mechanism remain somewhat large. A tighter analysis could potentially reduce the required sample size by another order of magnitude.
  • Post-Processing: The current output resembles a "blocky" histogram. Applying post-processing techniques, such as smoothing, could yield distributions that are both more accurate and visually appealing.

Summary updated

Abstract

We investigate the problem of learning an unknown probability distribution over a discrete population from random samples. Our goal is to design efficient algorithms that simultaneously achieve low error in total variation norm while guaranteeing Differential Privacy to the individuals of the population.We describe a general approach that yields near sample-optimal and computationally efficient differentially private estimators for a wide range of well-studied and natural distribution families. Our theoretical results show that for a wide variety of structured distributions there exist private estimation algorithms that are nearly as efficient - both in terms of sample size and running time - as their non-private counterparts. We complement our theoretical guarantees with an experimental evaluation. Our experiments illustrate the speed and accuracy of our private estimators on both synthetic mixture models and a large public data set.
BibTeX
@inproceedings{diakonikolas2015differentially,
  author = {Ilias Diakonikolas and Moritz Hardt and Ludwig Schmidt},
  title = {{Differentially Private Learning of Structured Discrete Distributions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=rJZiv_ZuZr},
}
Figure