arXiv 论文：首次在 person-level 差分隐私下多项式时间最优学习离散分布
Efficient and Optimal Learning of Discrete Distributions with Person-Level Privacy
一篇理论向的论文，作者把纯 DP 下学习离散分布的样本复杂度做到了信息论最优，核心工具是 sum-of-squares 估计器，做隐私统计的可以细看。
arXiv 论文 2610.31612 研究在 person-level 差分隐私下学习 [k] 上的离散分布，每个用户贡献 m 个 i.i.d. 样本。在纯 (ε,0)-DP 下，算法达到 n = O(k/(α²m)+k/(α√m·ε)+k/ε)，是首个在多项式时间内匹配信息论最优（仅差对数因子）的纯 DP 结果。在近似 (ε,δ)-DP 下，当 δ=2^{-Θ(k)} 时样本量约为 O(k)。技术上引入了新的 degree-6 sum-of-squares 估计器，并结合半定规划对偶与 Friedland-Lim 版 Grothendieck 不等式构造证书，同时给出 SQ 下界证明误差阶不可再降。
Efficient and Optimal Learning of Discrete Distributions with Person-Level Privacy
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.
