Sharp Critical Rates for Locally Private Distribution Estimation
Abstract
We determine sharp minimax rates for distribution estimation under pure local differential privacy at critical query smoothness. For the integral probability metric generated by the unit ball of Bd2,q, 1≤ q≤∞, over fixed periodic Sobolev density balls with positive smoothness and interior slack at the uniform density, the expected risk is of order N−1/2(log N)3/2−1/q, where N=nε2; expected squared risk has the squared order. The fine index governs aggregation across resolutions that share one private information budget. A single noninteractive release with a measurable proper density output attains these rates, and matching lower bounds allow finite public blackboard interaction and repeated participation under each user's total privacy budget. A known L2 radius permits the same rates without using density smoothness, with output in the L2 density ball. Separately, for positive smooth densities on [0,1], integrated squared CDF risk has minimax order (log N)2/N, with sharp quantile, Wasserstein, and transport map consequences. The rates hold uniformly for 0<ε≤1 as N→∞, with class parameters fixed.
Related
- De-biased Distribution Estimation for Locally Differential Private Survival Data
- Locally Private Inference for Riemannian Stochastic Optimization
- Optimal quantum locally differentially private mechanisms in the high-privacy regime
- Sparse Kernel Mechanisms for Locally Differentially Private Discrete Channels
- Differentially Private Average Treatment Effect Estimation by Propensity Score Blocking
BibTeX
@misc{liu2026sharp,
title = {{Sharp Critical Rates for Locally Private Distribution Estimation}},
author = {Yi Liu and Xiaotian Chang and Qirui Hu},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01289},
eprint = {2611.01289},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01289},
}
RIS
TY - UNPB
TI - Sharp Critical Rates for Locally Private Distribution Estimation
AU - Yi Liu
AU - Xiaotian Chang
AU - Qirui Hu
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01289
UR - https://arxiv.org/abs/2611.01289
AB - We determine sharp minimax rates for distribution estimation under pure local differential privacy at critical query smoothness. For the integral probability metric generated by the unit ball of B^d_2,q, 1≤ q≤∞, over fixed periodic Sobolev density balls with positive smoothness and interior slack at the uniform density, the expected risk is of order N^−1/2(log N)^3/2−1/q, where N=nε^2; expected squared risk has the squared order. The fine index governs aggregation across resolutions that share one private information budget. A single noninteractive release with a measurable proper density output attains these rates, and matching lower bounds allow finite public blackboard interaction and repeated participation under each user's total privacy budget. A known L^2 radius permits the same rates without using density smoothness, with output in the L^2 density ball. Separately, for positive smooth densities on [0,1], integrated squared CDF risk has minimax order (log N)^2/N, with sharp quantile, Wasserstein, and transport map consequences. The rates hold uniformly for 0<ε≤1 as N→∞, with class parameters fixed.
ER -