Paper recorded by Signals 4 on 2026-10-22 in cs.LG. Abstract reproduced from arXiv; link to the original below.
Published 2026-10-22 on arXiv · recorded by Signals 4 on 2026-10-23
Category: cs.LG · 机器学习 · first seen 2026-10-23
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