  The Randomized Response (RR) algorithm is a classical technique to improve
robustness in survey aggregation, and has been widely adopted in applications
with differential privacy guarantees. We propose a novel algorithm, Randomized
Response with Prior (RRWithPrior), which can provide more accurate results
while maintaining the same level of privacy guaranteed by RR. We then apply
RRWithPrior to learn neural networks with label differential privacy (LabelDP),
and show that when only the label needs to be protected, the model performance
can be significantly improved over the previous state-of-the-art private
baselines. Moreover, we study different ways to obtain priors, which when used
with RRWithPrior can additionally improve the model performance, further
reducing the accuracy gap between private and non-private models. We complement
the empirical results with theoretical analysis showing that LabelDP is
provably easier than protecting both the inputs and labels.
