Sharp Critical Rates for Locally Private Distribution Estimation
TL;DR
It is determined that sharp minimax rates for distribution estimation under pure local differential privacy at critical query smoothness are determined, and matching lower bounds allow finite public blackboard interaction and repeated participation under each user's total privacy budget.
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 $B^d_{2,q}$, $1\le q\le\infty$, 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\varepsilon^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<\varepsilon\le1$ as $N\to\infty$, with class parameters fixed.