Efficient privacy-preserving learning of complex one-dimensional data

Efficient Agnostic Learning of Univariate Densities Under Local Differential Privacy

Cryptography and SecurityData Structures and AlgorithmsInformation TheoryMachine Learning

Summary

Learning the shape of data while keeping each person's details private is challenging. The authors developed a new way to learn that works for complex data types like mixtures of normal distributions while protecting individual privacy without needing interactive communication. Their method is both sample-efficient and computationally efficient, meaning it learns accurately with fewer data and less computing power. They also proved limits on how well such learning can be done under strong privacy conditions.

What this means in practice

  • For privacy engineers: Protect individual data in statistical analysis pipelines while learning complex univariate distributions efficiently without interaction.
  • For mobile data analysts: Analyze user data locally on devices to learn trends modeled by mixtures of Gaussians under strict privacy constraints.

Authors

Mohammad Afzali, Hassan Ashtiani, Sivan Sabato

Abstract

We propose a general framework for non-interactive locally differentially private (LDP) learning of structured univariate distributions that can be approximated by piece-wise polynomials. This gives the first sample-efficient LDP learners for several distribution classes, including mixtures of log-concave distributions, such as Gaussian mixture models (GMMs). These learners also provide agnostic guarantees and are computationally efficient. We also prove a lower bound for learning GMMs under LDP, improving on the standard pure-DP packing lower bounds of Bun et al. [BKSW19]. To obtain our general learning framework, we develop an efficient non-interactive LDP algorithm for synthetic data generation over large domains, which may be of independent interest. We then use it together with a deterministic adaptation of the non-private piecewise polynomial learner of Acharya et al. [ADLS17].
View PDFOpen arXiv