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

Portuguese

Estudamos a aprendizagem de uma distribuição discreta sob privacidade diferencial de nível de pessoa na configuração batchada. Dados os usuários de $n$, cada um contribuindo $m$ i.i.d. amostras de uma distribuição desconhecida de $μ$ sobre $[k]$, buscamos uma estimativa de $μ$ com erro de variação total de $α$. Damos algoritmos de tempo polinômico sob privacidade diferencial pura e aproximada. Sob o $(\varepsilon,0)$-DP, encontramos $n = \widetilde O(k/((α^2 m)+k/(α\sqrt{m}\varepsilon)+k/\varepsilon)$, a primeira garantia de tempo puro polinômico de DP que corresponde ao otimismo

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