Locally differentially private estimation of nonlinear 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₁, . . ., x_n ∈ [K] are supposed i.i.d. and distributed according to an unknown discrete distribution p = (p₁, . . ., p_K). Only α-locally differentially private (LDP) samples z₁, ..., 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_γ =^PK_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α²)⁻¹/² when γ ≥ 2. We give lower bounds results over all α-LDP mechanisms and all estimators using the private samples.