Abigail Gentle

Distributed data analysis is a large and growing field driven by a massive proliferation of user devices, and by privacy concerns surrounding the centralised storage of data. We consider two adaptive algorithms for estimating one quantile (e.g. the median) when each user holds a single data point lying in a domain \([B]\) that can be queried once through a private mechanism; one under local differential privacy (LDP) and another for shuffle differential privacy (shuffle-DP). In the adaptive setting we present an \(\varepsilon\)-LDP algorithm which can estimate any quantile within error \(\alpha\) only requiring \(O(\frac{\log B}{\varepsilon^2\alpha^2})\) users, and an \((\varepsilon,\delta)\)-shuffle DP algorithm requiring only \(\widetilde{O}((\frac{1}{\varepsilon^2}+\frac{1}{\alpha^2})\log B)\) users. Prior (nonadaptive) algorithms require more users by several logarithmic factors in \(B\). We further provide a matching lower bound for adaptive protocols, showing that our LDP algorithm is optimal in the low-\(\varepsilon\) regime. Additionally, we establish lower bounds against non-adaptive protocols which paired with our understanding of the adaptive case, proves a fundamental separation between these models.

Frequency estimation, a.k.a. histograms, is a workhorse of data analysis, and as such has been thoroughly studied under differentially privacy. In particular, computing histograms in the local model of privacy has been the focus of a fruitful recent line of work, and various algorithms have been proposed, achieving the order-optimal \(\ell_\infty\) error in the high-privacy (small \(\varepsilon\)) regime while balancing other considerations such as time- and communication-efficiency. However, to the best of our knowledge, the picture is much less clear when it comes to the medium- or low-privacy regime (large \(\varepsilon\)), despite its increased relevance in practice. In this paper, we investigate locally private histograms, and the very related distribution learning task, in this medium-to-low privacy regime, and establish near-tight (and somewhat unexpected) bounds on the \(\ell_\infty\) error achievable. As a direct corollary of our results, we obtain a protocol for histograms in the shuffle model of differential privacy, with accuracy matching previous algorithms but significantly better message and communication complexity.

Our theoretical findings emerge from a novel analysis, which appears to improve bounds across the board for the locally private histogram problem. We back our theoretical findings by an empirical comparison of existing algorithms in all privacy regimes, to assess their typical performance and behaviour beyond the worst-case setting.