Transaction

jmetaB028c97758ff603b29768b74e12acca9e97f6a4e0e83c8a9c1f3c2fa7841f0b8ee5@104e04f4dc7bbb58b675a0be8ec8a2392cd828cadc0c1b85347e2d4ab003150erss.itemmetarss.netM³<item> <title>Private Mean Estimation with Person-Level Differential Privacy</title> <link>https://arxiv.org/abs/2405.20405</link> <description>arXiv:2405.20405v2 Announce Type: replace-cross Abstract: We study person-level differentially private (DP) mean estimation in the case where each person holds multiple samples. DP here requires the usual notion of distributional stability when $\textit{all}$ of a person's datapoints can be modified. Informally, if $n$ people each have $m$ samples from an unknown $d$-dimensional distribution with bounded $k$-th moments, we show that people are necessary and sufficient to estimate the mean up to distance $\alpha$ in $\ell_2$-norm under $\varepsilon$-differential privacy (and its common relaxations). In the multivariate setting, we give computationally efficient algorithms under approximate-DP and computationally inefficient algorithms under pure DP, and our nearly matching lower bounds hold for the most permissive case of approximate DP. Our computationally efficient estimators are based on the standard clip-and-noise framework, but the analysis for our setting requires both new algorithmic techniques and new analyses. In particular, our new bounds on the tails of sums of independent, vector-valued, bounded-moments random variables may be of interest. \[n = \tilde \Theta\left(\frac{d}{\alpha^2 m} + \frac{d}{\alpha m^{1/2} \varepsilon} + \frac{d}{\alpha^{k/(k-1)} m \varepsilon} + \frac{d}{\varepsilon}\right)\]</description> <guid isPermaLink="false">oai:arXiv.org:2405.20405v2</guid> <category>cs.DS</category> <category>cs.CR</category> <category>cs.IT</category> <category>cs.LG</category> <category>math.IT</category> <category>stat.ML</category> <arxiv:announce_type>replace-cross</arxiv:announce_type> <dc:rights>http://arxiv.org/licenses/nonexclusive-distrib/1.0/</dc:rights> <dc:creator>Sushant Agarwal, Gautam Kamath, Mahbod Majid, Argyris Mouzakis, Rose Silver, Jonathan Ullman</dc:creator> </item>