Efficient and Optimal Learning of Discrete Distributions with Person-Level Privacy
Learning discrete distributions from batched user data under person-level privacy is a fundamental problem in federated analytics. This paper develops the first polynomial-time pure-DP algorithm that matches the information-theoretic sample complexity up to logarithmic factors, via a new degree-6 sum-of-squares certificate based on a trace-bounded diagonal majorizer for multinomial covariance. It also proves a statistical-query lower bound suggesting the gap between efficient and optimal robust rates may be inherent.
The paper makes a significant theoretical advance by giving polynomial-time pure- and approximate-DP algorithms for learning a $k$-ary discrete distribution from $n$ users with $m$ samples each, matching the optimal sample complexity up to logarithmic factors for the first time in the pure-DP setting. The degree-6 SoS certificate and diagonal majorizer are genuinely novel, though the robust estimator retains a $\sqrt{\log(1/\eta)}$ gap versus the information-theoretic $O(\eta/\sqrt{m})$ optimum. The approximate-DP guarantee also introduces an additive $\widetilde{O}(k)$ term that complicates the large-batch regime.
The standout contribution is the diagonal-majorizer certificate, which compresses $2^k$ subset-variance constraints into a single semidefinite condition that preserves the mean-dependent multinomial covariance. This enables both polynomial-time optimization and the low-sensitivity, quasi-convex score required by the robustness-to-privacy reduction. The statistical-query lower bound in Section 5 strengthens the result by providing conditional evidence that the $\sqrt{\log(1/\eta)}$ factor is not merely an artifact of the analysis.
The robust error $O(\eta\sqrt{\log(1/\eta)/m})$ misses the information-theoretic $O(\eta/\sqrt{m})$ rate established by Qiao and Valiant; while the SQ lower bound supports a conditional gap, it does not rule out better polynomial-time algorithms unconstrained by the SQ model. The approximate-DP guarantee carries an additive $\widetilde{O}(k)$ term that is absorbed by $k/\varepsilon$ in the pure-DP bound but becomes exposed when the other terms are small, reflecting a limitation of the robust-to-private conversion at coarse accuracy. No empirical validation or computational experiments are provided.
The paper situates its bounds honestly against prior work. It notes that Ghazi et al. achieved optimal sample complexity only via an exponential-time cover, while Liu et al. and Esfandiari et al. obtain efficient algorithms but with superlinear $k$-dependence in the privacy term for cryptographically small $\delta$. The pure-DP sample bound is proved to match known lower bounds up to logarithmic factors, and Remark 4.16 provides explicit constants.
The paper is purely theoretical with no code, data, or computational experiments. While the degree-6 SoS relaxation is polynomial time in principle, concrete runtime bounds, SDP solver precision requirements, and explicit constants in the $\widetilde{O}$ notation are omitted. Independent reproduction would require reimplementing the semidefinite program from scratch and tuning unspecified numerical tolerances.
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 $\mu$ over $[k]$, we seek an estimate of $\mu$ with total-variation error $\alpha$. We give polynomial-time algorithms under both pure and approximate differential privacy. Under pure $(\varepsilon,0)$-DP, we achieve $n = \widetilde O(k/(\alpha^2 m)+k/(\alpha\sqrt{m}\varepsilon)+k/\varepsilon)$, the first polynomial-time pure-DP guarantee matching the information-theoretic optimum up to logarithmic factors. Under approximate $(\varepsilon,\delta)$-DP, we achieve $n = \widetilde O(k/(\alpha^2 m)+k/(\alpha\sqrt{m}\varepsilon)+k+\log(1/\delta)/\varepsilon)$. At $\delta=2^{-\Theta(k)}$, this is $\widetilde O(k)$ for fixed $\alpha,\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(\eta\sqrt{\log(1/\eta)/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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.