{"ID":2856567,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.11895","arxiv_id":"2510.11895","title":"High-Probability Bounds For Heterogeneous Local Differential Privacy","abstract":"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.","short_abstract":"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 samp...","url_abs":"https://arxiv.org/abs/2510.11895","url_pdf":"https://arxiv.org/pdf/2510.11895v1","authors":"[\"Maryam Aliakbarpour\",\"Alireza Fallah\",\"Swaha Roy\",\"Ria Stevens\"]","published":"2025-10-13T19:54:44Z","proceeding":"stat.ML","tasks":"[\"stat.ML\",\"cs.CR\",\"cs.DS\",\"cs.LG\"]","methods":"[]","has_code":false}