Optimal Private Discrete Distribution Estimation with One-bit Communication
Seung-Hyun Nam, KAIST, Korea (South); Vincent Y. F. Tan, National University of Singapore, Singapore; Si-Hyeon Lee, KAIST, Korea (South)
Session:
Differential Privacy in Learning 2
Track:
16: Privacy and Fairness
Location:
Ypsilon IV-V-VI
Presentation Time:
Mon, 8 Jul, 16:25 - 16:45
Session Chair:
Ayfer Ozgur, Stanford University
Abstract
We consider a private discrete distribution estimation problem with one-bit communication constraint. The privacy constraints are imposed with respect to the local differential privacy. The estimation error is quantified by the worst-case mean squared error. We completely characterize the first-order asymptotics of this privacy-utility trade-off under the one-bit communication constraint by using ideas from local asymptotic normality and the resolution of a block design mechanism. This results demonstrate the optimal dependence of the privacy-utility trade-off under the one-bit communication constraint in terms of the privacy constraint and the size of the alphabet of the discrete distribution.