betaFeedback

WorksMathematics

Functional Estimation under Local Differential Privacy: General Lower Bounds and Applications to Entropy and Power Sums

Abstract

We study the estimation of functionals of discrete distributions under local differential privacy (LDP). Even for well-studied examples like Shannon entropy and power sums, the existing bounds left open how the minimax risk scales with the alphabet size, the sample size, and the privacy parameter. To understand these dependences, we establish two general minimax lower bounds for the broader class of additive functionals. The first lower bound links the difficulty of estimating a functional to how well it can be approximated by polynomials of a given degree. The second complements the first by capturing how sensitive the functional is to small changes in the underlying distribution. To illustrate the effectiveness of these two bounds, we apply them to the estimation of Shannon entropy and power sums. In both cases, they close the existing polynomial gaps and, perhaps surprisingly, show that simple plug-in type estimators already achieve the optimal polynomial rates.

Paper details

vlnc:W_uhcxysvc
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…