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

Russian

Мы изучаем изучение дискретного распределения при дифференциальной конфиденциальности на уровне человека в пакете. Учитывая пользователей $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