Newest papers

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

Gautam Kamath, Mahbod Majid, Ankur Moitra, Argyris Mouzakis, Jonathan Ullman · 2026 · arXiv

DOI: 10.48550/arXiv.2610.31612 · open-access PDF

Chinese

我们研究在批量设置中学习人级差异隐私下的分布式分布。鉴于 $n$用户,每个贡献 $m$ i.i.d. 样本来自一个未知的分布式 $μ$ 超过 $[k]$,我们寻求对 $μ$ 的总变量错误(α$)的估计。我们在纯粹和近似差异隐私下提供多元时间算法。在纯 $(\varepsilon,0)$-DP 中,我们报告了 $n = \widetilde O(k/(α^2 m)+k/(α\sqrt{m}\varepsilon)+k/\varepsilon)$,第一个多元时间纯DP 保证匹配信息理论最佳到逻辑因素。

Machine translation (Meta M2M100); the English original follows.

Abstract

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 $

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange