General
Functional Estimation under Local Differential Privacy: General Lower Bounds and Applications to Entropy and Power Sums
arXiv stat.TH0 views
arXiv:2611.25063v1 Announce Type: new 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.
Source:https://arxiv.org/abs/2611.25063PreviousGeometry, Local Minimax Risk, and the Limits of Sample Average Approximation in Linear Stochastic OptimizationNextThe Scaled Dirichlet Distribution: Lauricella Representations and Estimation
Related posts
Kernel Regression using Persistence Diagrams
0arXiv stat.TH
The Scaled Dirichlet Distribution: Lauricella Representations and Estimation
0arXiv stat.TH
Scaling GR(1) Synthesis via a Compositional Framework for LTL Discrete Event Control
0arXiv cs.SE
Solomonoff induction of selected bits and online classification
0arXiv math.IT
Generalized Covering radii and Deep Holes of a Family of Antiprimitive Narrow-Sense BCH Codes in Even Characteristic
0arXiv math.IT
Open Response Explorer: a Structured Collaborative Writing System for Peer-Informed Open-Response Assignments
0arXiv cs.HC