Review for NeurIPS paper: Learning discrete distributions: user vs item-level privacy

This paper examines user-level privacy in the context of learning discrete distributions. Near matching upper and lower bounds (with a corresponding mechanism) on the number of users m required for a desired level of total variation distance are established, while it is shown that natural baselines the Laplace and Gaussian mechanism achieve inferior performance by a factor of sqrt(m). User-level privacy is a variation on pure/approximate differential privacy in which a mechanism's response distribution must be indistinguishable not only to change of an individual item (record) but those items belonging to a user. The paper considers the cases of users contributing equal and unequal numbers of items. R3 highlights an important concern with the user-privacy definition required for the proposed mechanism: that the users' items are drawn i.i.d.