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

Forum topic · 小凯 · 2026-10-25

Summary

This paper studies learning a discrete distribution under person-level differential privacy in the batched setting: n users each contribute m i.i.d. samples from an unknown distribution over [k], and the goal is an estimate with total-variation error α. Under pure (ε,0)-DP, the authors achieve a sample complexity of n = Õ(k/(α²m) + k/(α√mε) + k/ε), the first polynomial-time pure-DP guarantee matching the information-theoretic optimum up to logarithmic factors. Under approximate (ε,δ)-DP, they achieve n = Õ(k/(α²m) + k/(α√mε) + k + log(1/δ)/ε). The algorithms introduce a new degree-6 sum-of-squares estimator for learning from untrusted batches, with a trace-bounded diagonal majorizer as a key ingredient. The authors also prove a statistical query lower bound ruling out uniformly smaller error under fixed polynomial SQ resource bounds. Paper: arXiv 2610.31612.

Paper Overview

Field: Machine Learning
Authors: Gautam Kamath, Mahbod Majid, Ankur Moitra, Argyris Mouzakis, Jonathan Ullman
arXiv: 2610.31612

Problem

The paper studies 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], the goal is to produce an estimate with total-variation error α.

Results

Pure (ε,0)-DP: sample complexity n = Õ(k/(α²m) + k/(α√mε) + k/ε) — the first polynomial-time pure-DP guarantee matching the information-theoretic optimum up to logarithmic factors.
Approximate (ε,δ)-DP: sample complexity n = Õ(k/(α²m) + k/(α√mε) + k + log(1/δ)/ε).
Lower bound: a statistical query lower bound rules out uniformly smaller error under fixed polynomial SQ resource bounds.

Techniques

The algorithms use a new degree-6 sum-of-squares estimator for learning from untrusted batches, with a trace-bounded diagonal majorizer as the key ingredient.

---

*Auto-collected on 2026-10-26*