Outlier Privacy

We introduce a generalization of differential privacy called

tailored differential privacy

, where an individual’s privacy parameter is “tailored” for the individual based on the individual’s data and the data set. In this paper, we focus on a natural instance of tailored differential privacy, which we call

outlier privacy

: an individual’s privacy parameter is determined by how much of an “

outlier

” the individual is. We provide a new definition of an outlier and use it to introduce our notion of outlier privacy. Roughly speaking,

ε

(·)

-outlier privacy

requires that each individual in the data set is guaranteed “

ε

(

k

)-differential privacy protection”, where

k

is a number quantifying the “outlierness” of the individual. We demonstrate how to release accurate histograms that satisfy

ε

(·)-outlier privacy for various natural choices of

ε

(·). Additionally, we show that

ε

(·)-outlier privacy with our weakest choice of

ε

(·)—which offers no explicit privacy protection for “non-outliers”—already implies a “distributional” notion of differential privacy w.r.t. a large and natural class of distributions.