A Tighter Converse for the Locally Differentially Private Discrete Distribution Estimation Under the One-bit Communication Constraint

Abstract

We consider a discrete distribution estimation problem under the local differential privacy and the one-bit communication constraints. A fundamental privacy-utility tradeoff in this problem is formulated as the minimax squared loss. We show a tighter lower bound on the minimax squared loss, which has exactly the same form with the upper bound by the recursive Hadamard response by Chen et al. up to a constant factor of 4 for arbitrary LDP constraint and arbitrary finite data space. To derive the lower bound, we modify the van Trees inequality to involve a symmetrized Fisher information, which is invariant under the choice of the coordinate system on the probability simplex. We further characterize the maximum of the symmetrized Fisher information by considering the joint effect of the privacy and the communication constraints.