Locally Private Histograms in All Privacy Regimes

The next statistics seminar will be presented by Dr Clement Canonne from School of Computer Science.

Title: Locally Private Histograms in All Privacy Regimes
Speaker: Clément Canonne
Time and location : 1-2pm on Carslaw 275 or Zoom
Abstract :

Frequency estimation asks, given a dataset of n values, to output a good approximation of its empirical histogram (frequency counts): typically, this must be done under algorithmic or information-theoretic constraints on the way the "dataset" is accessed. Being a fundamental task in data analysis, this question has been thoroughly studied under a variety of computational and restricted data access models, including that of differential privacy -- a mathematical formalisation of data privacy. In particular, computing histograms in the so-called "local" model of privacy (LDP) has been the focus of a fruitful recent line of work, and various algorithms have been proposed, all achieving the order-optimal pointwise error while also balancing other considerations such as time- and communication-efficiency. Optimal, as these guarantees are complemented by information-theoretic lower bounds.

However, this is all in the "high-privacy" regime ("small epsilon"). In this talk, I will argue that the (quite common in practice) "low-privacy" regime is not only much less understood, but also that it is surprisingly interesting, both in terms of results and mathematical analysis. In particular, our results rely on some recent improved bounds for high-dimensional parameter estimation and expected maximum of sub-gamma-type random variables, the "Local Glivenko-Cantelli"-type results.

Joint work with Abigail Gentle.