# High-Probability Bounds For Heterogeneous Local Differential Privacy

arXiv: https://arxiv.org/abs/2510.11895 · HTML: https://mlsanity.com/paper/2510.11895/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 34 references that are in the map.
- First posted on arXiv 13 Oct 2025.

## Builds on (most cited first, 18 of 18)

- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [Loss minimization and parameter estimation with heavy tails](https://mlsanity.com/paper/1307.1827/) (2013)
- [Local Differential Privacy and Its Applications: A Comprehensive Survey](https://mlsanity.com/paper/2008.03686/) (2020)
- [Local, Private, Efficient Protocols for Succinct Histograms](https://mlsanity.com/paper/1504.04686/) (2015)
- [Heterogeneous Differential Privacy](https://mlsanity.com/paper/1504.06998/) (2015)
- [Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication](https://mlsanity.com/paper/1802.04705/) (2018)
- [A Comprehensive Survey on Local Differential Privacy Toward Data Statistics and Analysis](https://mlsanity.com/paper/2010.05253/) (2020)
- [Optimal and Differentially Private Data Acquisition: Central and Local Mechanisms](https://mlsanity.com/paper/2201.03968/) (2022)
- [Local Differential Privacy Is Equivalent to Contraction of Eγ-Divergence](https://mlsanity.com/paper/2102.01258/) (2021)
- [High-probability minimax lower bounds](https://mlsanity.com/paper/2406.13447/) (2024)
- [Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Free](https://mlsanity.com/paper/2305.09668/) (2023)
- [Mean Estimation Under Heterogeneous Privacy Demands](https://mlsanity.com/paper/2310.13137/) (2023)
- [Private Distribution Testing with Heterogeneous Constraints: Your Epsilon Might Not Be Mine](https://mlsanity.com/paper/2309.06068/) (2023)
- [Private Estimation when Data and Privacy Demands are Correlated](https://mlsanity.com/paper/2407.11274/) (2024)
- [Locally Private Histograms in All Privacy Regimes](https://mlsanity.com/paper/2408.04888/) (2024)

## Built on by (most cited first, 1 of 1)

- [Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacy](https://mlsanity.com/paper/2606.23096/) (2026)

## Abstract (arXiv)

We study statistical estimation under local differential privacy (LDP) when users may hold heterogeneous privacy levels and accuracy must be guaranteed with high probability. Departing from the common in-expectation analyses, and for one-dimensional and multi-dimensional mean estimation problems, we develop finite sample upper bounds in ℓ2-norm that hold with probability at least 1-β. We complement these results with matching minimax lower bounds, establishing the optimality (up to constants) of our guarantees in the heterogeneous LDP regime. We further study distribution learning in ℓ_∞-distance, designing an algorithm with high-probability guarantees under heterogeneous privacy demands. Our techniques offer principled guidance for designing mechanisms in settings with user-specific privacy levels.