Element Level Differential Privacy: The Right Granularity of Privacy
  Differential Privacy (DP) provides strong guarantees on the risk of
compromising a user's data in statistical learning applications, though these
strong protections make learning challenging and may be too stringent for some
use cases. To address this, we propose element level differential privacy,
which extends differential privacy to provide protection against leaking
information about any particular "element" a user has, allowing better utility
and more robust results than classical DP. By carefully choosing these
"elements," it is possible to provide privacy protections at a desired
granularity. We provide definitions, associated privacy guarantees, and
analysis to identify the tradeoffs with the new definition; we also develop
several private estimation and learning methodologies, providing careful
examples for item frequency and M-estimation (empirical risk minimization) with
concomitant privacy and utility analysis. We complement our theoretical and
methodological advances with several real-world applications, estimating
histograms and fitting several large-scale prediction models, including deep
networks.
