High-Probability Bounds For Heterogeneous Local Differential Privacy
This work addresses the problem of ensuring high-probability accuracy guarantees in privacy-preserving data analysis for settings where users have varying privacy requirements, representing an incremental advancement in the heterogeneous LDP regime.
The paper tackles statistical estimation under local differential privacy with heterogeneous user privacy levels, developing finite sample upper bounds for mean estimation and distribution learning that hold with high probability, with results shown to be optimal up to constants through matching minimax lower bounds.
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 $\ell_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 $\ell_\infty$-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.