Appendix: Learning discrete distributions: user vs item-level privacy

B.1 Proof of Theorem 4 The proof of Assouad's Lemma relies on Le Cam's method [Le Cam, 1973, Yu, 1997], which provide lower bounds for min-max error in hypothesis testing. P be two disjoint subsets of distributions. The first term follows from the classic Le Cam's lower bound (see [Yu, 1997, Lemma 1]). Next we need the group property of differential privacy. The final step is to apply the classic Assouad's Lemma [Yu, 1997]: Theorem 10 (Assouad's Lemma).