Robust Estimation of Discrete Distributions under Local Differential Privacy
This work addresses the challenge of robust statistical estimation for privacy-sensitive applications, combining two critical constraints in a novel way, though it is incremental in extending known minimax analysis to a combined setting.
The paper tackles the problem of estimating a discrete distribution from contaminated data under local differential privacy constraints, showing that the minimax estimation rate is ε√(d/(α²k)) + √(d²/(α²kn)), which is larger than the sum of the separate rates for contamination and privacy alone, and provides a polynomial-time algorithm achieving this bound.
Although robust learning and local differential privacy are both widely studied fields of research, combining the two settings is just starting to be explored. We consider the problem of estimating a discrete distribution in total variation from $n$ contaminated data batches under a local differential privacy constraint. A fraction $1-ε$ of the batches contain $k$ i.i.d. samples drawn from a discrete distribution $p$ over $d$ elements. To protect the users' privacy, each of the samples is privatized using an $α$-locally differentially private mechanism. The remaining $εn $ batches are an adversarial contamination. The minimax rate of estimation under contamination alone, with no privacy, is known to be $ε/\sqrt{k}+\sqrt{d/kn}$, up to a $\sqrt{\log(1/ε)}$ factor. Under the privacy constraint alone, the minimax rate of estimation is $\sqrt{d^2/α^2 kn}$. We show that combining the two constraints leads to a minimax estimation rate of $ε\sqrt{d/α^2 k}+\sqrt{d^2/α^2 kn}$ up to a $\sqrt{\log(1/ε)}$ factor, larger than the sum of the two separate rates. We provide a polynomial-time algorithm achieving this bound, as well as a matching information theoretic lower bound.