Differentially private depth functions and their associated medians

In this paper, we investigate the differentially private estimation of data depth functions and their associated medians. We start with several methods for privatizing depth values at a fixed point, and show that for some depth functions, when the depth is computed at an out of sample point, privacy can be gained for free when $n\rightarrow \infty$. We also present a method for privately estimating the vector of sample depth values, and show that privacy is not gained for free asymptotically. We also introduce estimation methods for depth-based medians for both depth functions with low global sensitivity and depth functions with only highly probably, low local sensitivity. We provide a general Theorem (Lemma 1) which can be used to prove consistency of an estimator produced by the exponential mechanism, provided the asymptotic cost function is uniquely minimized and is sufficiently smooth. We introduce a general algorithm to privately estimate minimizers of a cost function which has low local sensitivity, but high global sensitivity. This algorithm combines propose-test-release with the exponential mechanism. An application of this algorithm to generate consistent estimates of the projection depth-based median is presented. For these private depth-based medians, we show that it is possible for privacy to be free when $n\rightarrow \infty$.