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

Arabic

ونحن نبحث عن تعلم توزيعًا مختلفًا على مستوى الأشخاص في الإعدادات المشتركة. ونحن نعطي مستخدمي $n$، كل مشاركة $m$ i.i.d. نموذجًا من توزيع لا يعرف $μ$ على $[k]$، ونبحث عن تقدير $μ$ مع خطأ التغيير الكامل $α$. ونحن نعطي ألغاز وقتية متعددة على حد سواء مع خصوصية التغيير البسيطة والمتوسطية. تحت نوعية $(\varepsilon,0)$-DP، ونحن نعرف $n = \widetilde O(k/(α^2 m)+k/(α\sqrt{m}\varepsilon)+k/\varepsilon)$، ونحن نعطي أول ضمانات وقتية نوعية

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