Efficient and Optimal Learning of Discrete Distributions with Person-Level Privacy

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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Machine Learning

• arXiv preprint · 22 October 2026

  Optimal Mixing for Local Edge-Coloring Dynamics on Trees

  Haoran wang
• arXiv preprint · 23 October 2026

  Beyond 3SUM-Hardness for Geometric Problems

  Nick Fischer
• arXiv preprint · 22 October 2026

  Report the tolerance, not the count: exact phylogenetic distance deconvolution with incomplete references

  Haotian Tang
• arXiv preprint · 23 October 2026

  The Exact Robustness of Smith's Rule with Predicted Processing Times

  Ohad Ayalon and Ilan Reuven Cohen
• arXiv preprint · 22 October 2026

  Near-Quadratic Time Multivariate Polynomial Interpolation

  Chandra Kanta Mohapatra

All new papers in Machine Learning