Sparse Estimation Under Local Differential Privacy at All Privacy Levels

Sparse estimation is an important task in modern data analysis. In recent years, researchers have applied local differential privacy (LDP) for privacy protection. However, while large privacy budget $\epsilon$ is commonly used in realworld applications, existing research focus primarily on the asymptotic performance with $\epsilon \rightarrow 0$. With large $\epsilon$, due to the additional error caused by randomness in the encoding step, current methods yield suboptimal performance. In this paper, we study sparse frequency and mean estimation problems under LDP for arbitrary $\epsilon$. We first propose Optimized Multiitem Response (OMR) for sparse frequency estimation. For each input vector x, OMR outputs a random set containing $k$ elements, and parameters are all optimized to achieve minimum mean squared error. We then extend it to general mean estimation problems. Compared with other methods, our new method does not introduce any unnecessary randomness during the encoding step. Our theoretical analysis and numerical experiments show that our method achieves comparable performance when $\epsilon<1$ and makes a significant improvement when $\epsilon \geq 1$.