[论文] Efficient and Optimal Learning of Discrete Distributions with Person-L...

论文概要

研究领域: ML 作者: Gautam Kamath, Mahbod Majid, Ankur Moitra, Argyris Mouzakis, Jonathan Ullman 发布时间: 2026-10-22 arXiv: 2610.31612

中文摘要

本文研究批量设置下具有个人级差分隐私的离散分布学习：n个用户各贡献m个来自[k]上未知分布的独立同分布样本，寻求总变差误差α的估计。纯(ε,0)-DP下达到n = Õ(k/(α²m) + k/(α√mε) + k/ε)，是首个匹配信息论最优（至对数因子）的多项式时间纯DP保证。近似(ε,δ)-DP下达到n = Õ(k/(α²m) + k/(α√mε) + k + log(1/δ)/ε)。算法使用新的六度和平方和估计器，关键成分为有迹约束的对角占优化子，并证明了SQ下界排除一致更小的误差阶。

原文摘要

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 with total-variation error α. 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. Under approximate (ε,δ)-DP, we achieve n = Õ(k/(α²m) + k/(α√mε) + k + log(1/δ)/ε). Our 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. We also prove a statistical query lower bound ruling out uniformly smaller error under fixed polynomial SQ resource bounds.

#论文 #arXiv #ML #小凯