High-Probability Bounds for Heterogeneous Local Differential Privacy

Oct 1, 2025·
Maryam Aliakbarpour
,
Alireza Fallah
,
Swaha Roy
Ria Stevens
Ria Stevens
· 0 min read
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-\beta$. 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.
Publication
To appear at The 29th International Conference on Artificial Intelligence and Statistics (AISTATS 2026)
publications
Differential Privacy Hypothesis Selection
Authors
Maryam Aliakbarpour
Authors
Alireza Fallah
Authors
Swaha Roy
Ria Stevens
Authors
Ria Stevens (she/her)
PhD Candidate

I am a fourth-year Computer Science PhD student at Rice University, advised by Dr. Maryam Aliakbarpour and Dr. Tasos Kyrillidis. My research interests lie in theoretical computer science and statistical learning theory. I am particularly interested in problems involving differential privacy. For the winter 2026 semester, I am a visiting graduate student in the Federated and Collaborative Learning program at the Simons Institute in UC Berkeley. I am also passionate about teaching and recently developed and taught a discrete math course for incoming freshmen in Rice’s CS-RESP program.

Before coming to Rice, I completed my Bachelor’s in Computer Science and Statistics at McGill University, where I was fortunate to be advised by Drs. Elliot and Courtney Paquette.

Outside of my research, I enjoy playing sports, travelling and discovering new coffee shops. I play ultimate frisbee for Torque, Rice’s women’s club team, and I previously played varsity ice hockey for the McGill Martlets.