2025/10/13 by Maryam Aliakbarpour, Aliakbarpour, Maryam, Alireza Fallah +4
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.2510.11895
openalex publication_date 2025/10/13 · openalex created_date 2025/10/17 · openalex updated_date 2026/07/28
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.