Appendix: Learning discrete distributions: user vs item-level privacy A Proof of Lemma 1 Note that ˆ p i = (N i + Z

The proof of Assouad's Lemma relies on Le Cam's method [Le Cam, 1973, Y u, 1997], which provide The first term follows from the classic Le Cam's lower bound (see [Y u, 1997, Lemma 1]). Next we need the group property of differential privacy. By [Acharya et al., 2020, Lemma 14 ], there exists a coupling In this section we provide learning lower bound for restricted estimators under pure differential privacy using Fano's method. The first term of (8) follows from the non-private Fano's inequality. Combining with (9) gives the desired lower bound.Proof of Theorem 3. To this end we need the following lemma from den Hollander [2012].