Please note: This seminar will be given online.
Vikrant
Singhal, Khoury
College
of
Computer
Sciences
Northeastern
University
We give new upper and lower bounds on the minimax sample complexity of differentially private mean estimation of distributions with bounded k-th moments. Roughly speaking, in the univariate case, we show that n = \Theta(1/\alpha^2 + 1/\epsilon\alpha^{k/(k-1)}) samples are necessary and sufficient to estimate the mean to \alpha-accuracy under \epsilon-differential privacy, or any of its common relaxations. This result demonstrates a qualitatively different behavior compared to estimation absent privacy constraints, for which the sample complexity is identical for all k >= 2. We also give algorithms for the multivariate setting whose sample complexity is a factor of O(d) larger than the univariate case.
To join this seminar on Zoom, please go to https://zoom.us/j/99079454393?pwd=NEY3Y1ltTmxURFZsMUZQT09PcTNqdz09.