  In this paper, we introduce a novel concept of user-entity differential
privacy (UeDP) to provide formal privacy protection simultaneously to both
sensitive entities in textual data and data owners in learning natural language
models (NLMs). To preserve UeDP, we developed a novel algorithm, called
UeDP-Alg, optimizing the trade-off between privacy loss and model utility with
a tight sensitivity bound derived from seamlessly combining user and sensitive
entity sampling processes. An extensive theoretical analysis and evaluation
show that our UeDP-Alg outperforms baseline approaches in model utility under
the same privacy budget consumption on several NLM tasks, using benchmark
datasets.
