Learning discrete data distributions efficiently with user privacy guarantees
Efficient and Optimal Learning of Discrete Distributions with Person-Level Privacy
Machine LearningCryptography and SecurityData Structures and Algorithms
Summary
This paper deals with a problem where we want to learn the pattern of a dataset made up of small categories, while protecting the privacy of individual people who contributed data. The authors develop fast algorithms that give nearly the best possible accuracy while ensuring strong privacy rules. They do this by using a new mathematical technique involving advanced polynomial estimators and inequalities to handle noisy or untrusted data batches. Their work also shows some fundamental limits on how accurately such private learning can be done.
What this means in practice
- •For data privacy engineers: Enable efficient learning of discrete data patterns while ensuring strong person-level privacy in applications with batched user data.
- •For statistical software developers: Incorporate new privacy-preserving estimators to improve robust distribution learning algorithms for datasets with multiple samples per user.
Authors
Gautam Kamath, Mahbod Majid, Ankur Moitra, Argyris Mouzakis, Jonathan Ullman
Abstract
We study learning a discrete distribution under person-level differential privacy in the batched setting. Given $n$ users, each contributing $m$ i.i.d. samples from an unknown distribution $μ$ over $[k]$, we seek an estimate of $μ$ with total-variation error $α$. We give polynomial-time algorithms under both pure and approximate differential privacy. Under pure $(\varepsilon,0)$-DP, we achieve $n = \widetilde O(k/(α^2 m)+k/(α\sqrt{m}\varepsilon)+k/\varepsilon)$, the first polynomial-time pure-DP guarantee matching the information-theoretic optimum up to logarithmic factors. Under approximate $(\varepsilon,δ)$-DP, we achieve $n = \widetilde O(k/(α^2 m)+k/(α\sqrt{m}\varepsilon)+k+\log(1/δ)/\varepsilon)$. At $δ=2^{-Θ(k)}$, this is $\widetilde O(k)$ for fixed $α,\varepsilon,m$ and failure probability. Our algorithms use a new degree-6 sum-of-squares estimator for learning from untrusted batches. Its key ingredient is a trace-bounded diagonal majorizer for the difference between the empirical covariance of the repaired batch averages and the multinomial covariance predicted by their mean. We prove that clean data admit this certificate through semidefinite-programming duality and a new application of the stronger symmetric form of Grothendieck's inequality due to Friedland and Lim. The certificate preserves the mean-dependent variance of multinomial batch averages, yielding the near-optimal robust rate $O(η\sqrt{\log(1/η)/m})$ and providing the score required by the privacy reduction. We also prove a statistical query lower bound ruling out a uniformly smaller order of error under fixed polynomial SQ resource bounds.