In this work, we study high-dimensional mean estimation under user-level
differential privacy, and design an $(\varepsilon,\delta)$-differentially
private mechanism using as few users as possible. In particular, we provide a
nearly optimal trade-off between the number of users and the number of samples
per user required for private mean estimation, even when the number of users is
as low as $O(\frac{1}{\varepsilon}\log\frac{1}{\delta})$. Interestingly, this
bound on the number of \emph{users} is independent of the dimension (though the
number of \emph{samples per user} is allowed to depend polynomially on the
dimension), unlike the previous work that requires the number of users to
depend polynomially on the dimension. This resolves a problem first proposed by
Amin et al. Moreover, our mechanism is robust against corruptions in up to
$49\%$ of the users. Finally, our results also apply to optimal algorithms for
privately learning discrete distributions with few users, answering a question
of Liu et al., and a broader range of problems such as stochastic convex
optimization and a variant of stochastic gradient descent via a reduction to
differentially private mean estimation.

本文研究了用户级差分隐私下的高维度平均值估计，提供了用户数量与每个用户所需样本数量之间的最优权衡，并设计了一个 (ε,δ)- 差分隐私机制，即使当用户数量与 δ 的对数之积很小时也能保证隐私安全，同时与维度无关，适用于学习离散分布以及其它问题。