High-Probability Bounds For Heterogeneous Local Differential Privacy

The unprecedented growth of data collection has made protecting user privacy a central challenge. Local Differential Privacy (LDP) offers a compelling solution, enabling the analysis of population-level statistics without exposing any individual's raw data--even to the aggregator [Dwork et al., 2006, Kasiviswanathan et al., 2011]. In this model, each user perturbs their own data before transmission, ensuring that only randomized reports reach the curator. This paradigm has moved well beyond theory, with large-scale deployments at Google [Erlingsson et al., 2014], Microsoft [Ding et al., 2017], and Apple [Differential Privacy T eam, Apple, 2017, Thakurta et al., 2017]. Most research on LDP, however, rests on two simplifying assumptions: that all users share a uniform privacy guarantee (ε) and that error bounds only need to hold in expectation or just with a constant probability . In this work, we move beyond this idealized model to study two crucial and more realistic variants of LDP .