# Locally differentially private estimation of nonlinear functionals of discrete distributions

arXiv: https://arxiv.org/abs/2107.03940 · HTML: https://mlsanity.com/paper/2107.03940/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 31 references that are in the map.
- First posted on arXiv 8 Jul 2021.

## Builds on (most cited first, 12 of 12)

- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputs](https://mlsanity.com/paper/1811.01900/) (2018)
- [Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation](https://mlsanity.com/paper/1305.6000/) (2013)
- [Optimal rates of entropy estimation over Lipschitz balls](https://mlsanity.com/paper/1711.02141/) (2017)
- [The Role of Interactivity in Local Differential Privacy](https://mlsanity.com/paper/1904.03564/) (2019)
- [Local differential privacy: Elbow effect in optimal density estimation and adaptation over Besov ellipsoids](https://mlsanity.com/paper/1903.01927/) (2019)
- [Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms](https://mlsanity.com/paper/2005.12601/) (2020)
- [Estimating Renyi Entropy of Discrete Distributions](https://mlsanity.com/paper/1408.1000/) (2014)
- [INSPECTRE: Privately Estimating the Unseen](https://mlsanity.com/paper/1803.00008/) (2018)
- [On Estimation of Lr-Norms in Gaussian White Noise Models](https://mlsanity.com/paper/1710.03863/) (2017)
- [Exponential Separations in Local Differential Privacy](https://mlsanity.com/paper/1907.00813/) (2019)

## Abstract (arXiv)

We study the problem of estimating non-linear functionals of discrete distributions in the context of local differential privacy. The initial data x1,ldots,xn ∈ [K] are supposed i.i.d. and distributed according to an unknown discrete distribution p = (p1,ldots,pK). Only α-locally differentially private (LDP) samples z1,...,zn are publicly available, where the term 'local' means that each zi is produced using one individual attribute xi. We exhibit privacy mechanisms (PM) that are 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γ = sumk=1K pkγ, γ >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. (2017) 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. (2020). In the interactive case, we introduce for all γ >1 a two-step procedure which attains the faster parametric rate (n α2)-1/2 when γ ≥ 2. We give lower bounds results over all α-LDP mechanisms and all estimators using the private samples.