2021/07/08 by Cristina Butucea, Butucea, Cristina, Yann Issartel +1
Computer Science · Decision Sciences · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Methodology (stat.ME) #Privacy-Preserving Technologies in Data #Probability and Risk Models #Statistical Methods and Bayesian Inference #Statistical Methods in Clinical Trials #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2107.03940
openalex publication_date 2021/07/08 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
We study the problem of estimating non-linear functionals of discrete\ndistributions in the context of local differential privacy. The initial data\nx1,\…,xn \∈ [K] are supposed i.i.d. and distributed according to an\nunknown discrete distribution p = (p1,\…,pK). Only \α-locally\ndifferentially private (LDP) samples z1,...,zn are publicly available,\nwhere the term 'local' means that each zi is produced using one individual\nattribute xi. We exhibit privacy mechanisms (PM) that are interactive (i.e.\nthey are allowed to use already published confidential data) or\nnon-interactive. We describe the behavior of the quadratic risk for estimating\nthe power sum functional F\γ = \∑k=1K pk\γ, \γ >0\nas a function of K, , n and \α. In the non-interactive case, we study\ntwo plug-in type estimators of F\γ, for all \γ >0, that are\nsimilar to the MLE analyzed by Jiao et al. (2017) in the multinomial model.\nHowever, due to the privacy constraint the rates we attain are slower and\nsimilar to those obtained in the Gaussian model by Collier et al. (2020). In\nthe interactive case, we introduce for all \γ >1 a two-step procedure\nwhich attains the faster parametric rate (n \α2)-1/2 when \γ\n\≥ 2. We give lower bounds results over all \α-LDP mechanisms and all\nestimators using the private samples.\n