Person-level differential privacy for learning discrete distributions
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 α. The person-level privacy model considers each user's entire dataset as the unit of privacy, meaning that the mechanism must protect all m samples from a single user from being distinguished. This setting captures scenarios where users contribute multiple observations, and the privacy guarantee must hold across all of a user's contributions simultaneously.
The degree-6 sum-of-squares estimator and its certificate
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. This majorizer serves as a certificate that clean data satisfy a specific structural property, enabling the privacy-preserving learning algorithm to distinguish between in-distribution and out-of-distribution data. 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(η√(log(1/η)/m)) and providing the score required by the privacy reduction.
Pure differential privacy: matching the information-theoretic optimum
Under pure (ε,0)-DP, we achieve n = Õ(k/(α²m) + k/(α√mε) + k/ε), the first polynomial-time pure-DP guarantee matching the information-theoretic optimum up to logarithmic factors. This result is significant because, prior to this work, no polynomial-time algorithm could achieve the information-theoretic sample complexity bound under pure differential privacy. The three terms in the sample complexity have natural interpretations: k/(α²m) captures the statistical rate from m samples per user, k/(α√mε) reflects the privacy-induced error that depends on both the privacy parameter ε and the number of samples, and k/ε arises from the pure DP setting's fundamental limitations. The Õ notation hides logarithmic factors in the parameters, indicating that the bound is near-optimal.
Approximate differential privacy and the δ-dependent term
Under approximate (ε,δ)-DP, we achieve n = Õ(k/(α²m) + k/(α√mε) + k + log(1/δ)/ε). The additional term log(1/δ)/ε reflects the approximate nature of the privacy guarantee, allowing a small probability δ of privacy loss. At δ = 2^(-Θ(k)), this term becomes Õ(1)/ε for fixed k, and the overall sample complexity simplifies to Õ(k) for fixed α, ε, m and failure probability. This improvement over pure DP demonstrates the benefit of approximate DP when the privacy parameter δ can be made sufficiently small, specifically exponential in the number of outcomes k.
Certificates via Grothendieck's inequality and semidefinite programming duality
The certificate that clean data admit is established through semidefinite-programming duality and a new application of the stronger symmetric form of Grothendieck's inequality due to Friedland and Lim. Grothendieck's inequality is a fundamental result in functional analysis that provides bounds on bilinear forms; the symmetric version due to Friedland and Lim gives tighter constants that are particularly well-suited to the structure of multinomial covariance matrices. The trace-bounded diagonal majorizer constructed in the paper leverages this inequality to produce a certificate that captures the mean-dependent variance of multinomial batch averages while remaining computationally tractable. This certificate is the technical core that enables both the robust learning rate and the privacy reduction.
Statistical query lower bounds
We also prove a statistical query lower bound ruling out a uniformly smaller order of error under fixed polynomial SQ resource bounds. This lower bound establishes that no statistical query algorithm with polynomial resources can achieve a strictly better error rate than our algorithm, even approximately. The lower bound is information-theoretic in nature and applies to the statistical query model, which captures a broad class of learning algorithms that make queries about the expected value of functions of the data. This result confirms that the near-optimal sample complexity achieved by our algorithms is also optimal within the statistical query framework.
Implications for private learning
The results establish that polynomial-time learning of discrete distributions under person-level differential privacy is possible with sample complexity matching information-theoretic bounds, both for pure and approximate DP. The degree-6 sum-of-squares estimator with its trace-bounded diagonal majorizer provides a new tool for learning from untrusted batches, and the connection to Grothendieck's inequality through Friedland and Lim's symmetric form bridges discrete distribution learning with convex optimization and functional analysis. The statistical query lower bound confirms the optimality of the achieved rates within a broad model of computation. These contributions advance the theoretical foundation of private learning and provide concrete sample complexity guarantees that apply across the pure-to-approximate DP spectrum.
Read the paper on arXiv