Locally differentially private estimation of functionals of discrete distributions

We study the problem of estimating non-linear functionals of discrete distributions in the context of local differential privacy. The initial data x 1 , . . . , x n ∈ [K] are supposed i.i.d. and distributed according to an unknown discrete distribution p = (p 1 , . . . , p K ). Only α-locally differentially private (LDP) samples z 1 , ..., z n are publicly available, where the term 'local' means that each z i is produced using one individual attribute x i . We exhibit privacy mechanisms (PM) that are sequentially interactive (i.e. they are allowed to use already published confidential data) or non-interactive. We describe the behavior of the quadratic risk for estimating the power sum functional F γ = K k=1 p γ k , γ > 0 as a function of K, n and α. In the non-interactive case, we study two plug-in type estimators of F γ , for all γ > 0, that are similar to the MLE analyzed by Jiao et al. [18] in the multinomial model. However, due to the privacy constraint the rates we attain are slower and similar to those obtained in the Gaussian model by Collier et al. [9]. In the sequentially interactive case, we introduce for all γ > 1 a two-step procedure which attains the parametric rate (nα 2 ) -1/2 when γ ≥ 2. We give lower bounds results over all α-LDP mechanisms and all estimators using the private samples.