# Concentration of the exponential mechanism and differentially private
multivariate medians

Kelly Ramsay, Aukosh Jagannath, and Shoja’eddin Chenouri

###### Abstract.

We prove concentration inequalities for the output of the exponential
mechanism about the maximizer of the population objective function. This bound
applies to objective functions that satisfy a mild regularity condition. To
illustrate our result, we study the problem of differentially private
multivariate median estimation. We present novel finite-sample performance
guarantees for differentially private multivariate depth-based medians which
are essentially sharp. Our results cover commonly used depth functions, such
as the halfspace (or Tukey) depth, spatial depth, and the integrated dual
depth. We show that under Cauchy marginals, the cost of heavy-tailed location
estimation outweighs the cost of privacy. We demonstrate our results
numerically using a Gaussian contamination model in dimensions up to $d=100$,
and compare them to a state-of-the-art private mean estimation algorithm.

##  1\. Introduction

Protecting user privacy is necessary for a safe and fair society. In order to
protect user privacy, many large institutions, including the United States
Census Bureau [1], Apple [18], and Google [28], utilize a strong notion of
privacy known as differential privacy. Differential privacy is favored because
it protects against many adversarial attacks while requiring minimal
assumptions on both the data and the adversary [22]. Generating a
differentially private statistic requires a stochastic solution, i.e., one
must add calibrated noise to the statistic to ensure privacy [21]. A key
framework for generating differentially private statistics is the exponential
mechanism [41].

In this context, a critical problem is measuring the cost of privacy: What is
the loss in accuracy induced by this added stochasticity? The standard
approach is to control the difference between the maximum of the empirical
objective function and the empirical objective function value achieved by the
private estimator [41]. This approach, however, does not address the
_consistency_ of this estimator, that is, it does not quantify the distance
between the private estimate and the population parameter. Chaudhuri and Hsu
[13] began the study of this question by developing finite-sample error bounds
for the exponential mechanism in the univariate setting. More recently, Awan
et al. [5] developed the asymptotic consistency of the exponential mechanism
for strictly concave objective functions. In this paper, we investigate the
finite-sample error of the exponential mechanism in the multivariate setting.
We develop a concentration inequality for estimators generated by the
exponential mechanism about their population value. Our bound holds under mild
assumptions on the objective function and the population measure, and provides
sample complexity bounds as well. We do not require concavity or moment
assumptions, but instead assume uniform continuity of the objective function
and a regularity condition called $(K,\mathscr{F})$-regularity. (For a
definition, see Definition 2.1.)

To illustrate our results, we study the problem of differentially private and
robust multivariate location estimation. To date, the literature on this
problem has largely focused on the problem of mean estimation. Foygel Barber
and Duchi [25] proved a lower bound on the minimax risk of differentially
private mean estimation in terms of the number of moments possessed by the
population measure. Other early works focused on the univariate setting [32,
10]. Kamath et al. [30] and Bun et al. [11] studied differentially private
mean estimation for several parametric models, including the multivariate
Gaussian model. Later, several authors studied differentially private mean
estimation for sub-Gaussian measures [12, 7, 8, 40]. After which, Kamath et
al. [31], Liu et al. [39] and Hopkins et al. [29] studied differentially
private mean estimation for measures with a finite second moment. Within this
framework, Kamath et al. [31] considered heavy tails and Liu et al. [39] and
Hopkins et al. [29] considered robustness in terms of contamination models.
Kamath et al. [31] quantified the sample complexity of their private mean
estimate in terms of the number of moments possessed by the population
measure. Liu et al. [39] quantify the relationship between the accuracy of an
approximately differentially private mean estimate and the level of
contamination in the observed sample. On a similar note, Hopkins et al. [29]
show that there exists a level of contamination under which the sample
complexity of their purely differentially private mean estimate remains
unchanged.

On the other hand, considerably less attention has been given to robust
differentially private location estimation via a median. To date, the
literature has focused on univariate median estimation: Dwork and Lei [19]
introduced an approximately differentially private median estimator with
asymptotic consistency guarantees, Avella-Medina and Brunel [3], Brunel and
Avella-Medina [9] then introduced several median estimators which achieve sub-
Gaussian error rates, and Tzamos et al. [55] introduce median estimators with
optimal sample complexity. Private estimation of multivariate medians has not
been addressed.

In this paper, we study differentially private, multivariate median estimation
through the framework of depth functions. Depth-based median estimation is the
standard approach to multivariate median estimation. Here, one has a function,
called the depth function, which provides a measure of centrality. Its
maximizer is then the median, which is generally robust. Popular depth-based
medians include the halfspace (or Tukey) median [54], the spatial median [56],
and the simplicial median [37]. For more on the motivation of the depth-based
medians approach, see Section 3 below and [51, 56, 50]. Our results apply to a
broad class of depth functions, including those listed above, and we make
minimal distributional assumptions. In particular, we do not require concavity
of the depth function or that the population measure has moments of any order.

Our contributions are as follows: Our main result is a concentration bound
(Theorem 2.1) for the exponential mechanism. We give a novel regularity
condition “$(K,\mathscr{F})$-regularity” (Condition 3) on the objective
function. This regularity condition implies both an upper bound on the sample
complexity of a draw from the exponential mechanism and an upper bound on the
global sensitivity of the objective function. In our main application
(Corollary 3.1), we give upper bounds on the sample complexities of several,
purely differentially private multivariate medians arising from data depth
functions. These bounds are essentially sharp given recent results of Kamath
et al. [30] and do not require any moment assumptions on the population
measure. In addition, we provide a fast implementation of a smoothed version
of the integrated dual depth-based median [17]; we can compute the (non-
private) median of ten thousand 100-dimensional samples in less than one
second on a personal computer. We show that this smoothed version of the
integrated dual depth satisfies desirable properties for a depth function and
can be approximated in polynomial time with finite-sample performance
guarantees. As a by-product of our analysis, we uncover uniform non-asymptotic
error bounds for several depth functions and a differentially private
estimator of data depth values.

Before turning to our main results, it is important to note that several
authors have recently used depth functions in the context of differential
privacy, likely due to their robustness properties, with a heavy focus on the
halfspace depth, in settings such as finding a point in a convex hull [6, 27],
comparing $k$-norm mechanisms [4], and improving robustness for mean
estimation for Gaussian models [8, 39]. To our knowledge, however, none of
these works have addressed median estimation. (See also an earlier work by two
of us, which discusses the asymptotic version of the current work and a
propose-test-release algorithm for estimation of the projection depth-based
median [43].)

##  2\. Main results

We begin this section by stating our main technical result in a more general
setting, which we imagine will be useful more broadly. We then specialize to
setting of differential privacy in the following section.

###  2.1. A concentration inequality for the exponential mechanism

Suppose that we are given a function
$\phi:\mathbb{R}^{d}\times\mathcal{M}_{1}(\mathbb{R}^{d})\to\mathbb{R}$ and
$n$ i.i.d. samples, ${\mathbb{X}}_{n}=(X_{\ell})_{\ell=1}^{n}$, from some
unknown measure $\mu\in\mathcal{M}_{1}(\mathbb{R}^{d})$, where
$\mathcal{M}_{1}(\mathbb{R}^{d})$ is the space of probability measures on
$\mathbb{R}^{d}$. Our goal is to estimate $\theta_{0}=\operatorname*{{\rm
argmax}}_{\theta\in\mathbb{R}^{d}}\phi(\theta,\mu)$ privately via the
exponential mechanism, which is defined as follows. Let $\beta>0$ and
$\pi\in\mathcal{M}_{1}(\mathbb{R}^{d})$ be fixed, and suppose that
$\int\exp(\beta\phi(\theta,\nu))d\pi(\theta)<\infty$ for all
$\nu\in\mathcal{M}_{1}(\mathbb{R}^{d})$. We view $\pi$ as a prior and
$\beta>0$ as a tunable parameter. Finally, let
${\hat{\mu}}_{n}=\frac{1}{n}\sum\delta_{X_{i}}$ denote the empirical measure
of the data, ${\mathbb{X}}_{n}$. The _exponential mechanism_ with parameter
$\beta>0$ is the probability measure

$Q_{{\hat{\mu}}_{n},\beta}\propto\exp(\beta\phi(\theta,{\hat{\mu}}_{n}))d\pi.$
(2.1)

Our estimate of $\theta_{0}$ is then given by a sample from the exponential
mechanism: $\tilde{\theta}_{n}\sim Q_{{\hat{\mu}}_{n},\beta}.$

The basic question we seek to answer here is:

“How well does $\tilde{\theta}_{n}$ approximate $\theta_{0}$?”

Our main technical result is a concentration inequality that answers this
question.

To state this result, we need to introduce the following notation. Let
$\mathscr{B}$ denote the space of Borel functions $\mathbb{R}^{d}\to[0,1]$.
For a family of functions, $\mathscr{F}\subseteq\mathscr{B}$, define a
pseudometric on $\mathcal{M}_{1}(\mathbb{R}^{d})$,
$d_{\mathscr{F}}(\mu,\nu)=\sup_{g\in\mathscr{F}}|\int gd(\mu-\nu)|$, where
$\mu,\nu\in\mathcal{M}_{1}(\mathbb{R}^{d})$. Recall that many standard metrics
on probability measures can be written in this fashion. For example, taking
$\mathscr{F}$ to be the set of indicator functions of Borel sets yields the
Total Variation distance, taking $\mathscr{F}$ to be the set of indicator
functions of semi-infinite rectangles yields the Kolmogorov–Smirnov distance,
and taking $\mathscr{F}$ to be the set of 1-Lipschitz functions yields the
1-Wasserstein distance. We then define the following important regularity
condition.

######  Definition 2.1.

We say that $\phi$ is _$(K,\mathscr{F})$ -regular_ if there exists some class
of functions $\mathscr{F}\subset\mathscr{B}$ such that $\phi(x,\cdot)$ is
$K$-Lipschitz with respect to the $\mathscr{F}$-pseudometric uniformly in $x$,
i.e., for all $\mu,\nu\in\mathcal{M}_{1}(\mathbb{R}^{d})$

$\sup_{x}|\phi(x,\mu)-\phi(x,\nu)|\leq Kd_{\mathscr{F}}(\mu,\nu).$

$(K,\mathscr{F})$-regularity can be thought of as a robustness condition in
the sense that $(K,\mathscr{F})$-regular functions are affected by extreme
observations in a very limited manner, through boundedness of
$g\in\mathscr{F}$. For example, one can show that $(K,\mathscr{F})$-regularity
implies bounds on the global sensitivity (see Lemma A.2). In our applications,
we will typically take $\mathscr{F}$ to be a class of functions with low
complexity (in the sense of Vapnik–Chervonenkis dimension).

We also require the following regularity conditions on the pair $(\mu,\phi)$.
In the following, let $\operatorname{VC}(\mathscr{F})$ denote the
Vapnik–Chervonenkis dimension of $\mathscr{F}$.

######  Condition 1.

The function $\phi(\cdot,\mu)$ has a maximizer.

######  Condition 2.

The map $x\mapsto\phi(x,\mu)$ is $\pi$-a.s. uniformly continuous with modulus
of continuity $\omega$.

######  Condition 3.

There is some $K>0$ and some family of functions
$\mathscr{F}\subseteq\mathscr{B}$ with $\operatorname{VC}(\mathscr{F})<\infty$
such that $\phi$ is $(K,\mathscr{F})$-regular.

Let us now define the following important functions. Let
$E_{\phi,\mu}=\\{\theta:\phi(\theta,\mu)=\max_{x}\phi(x,\mu)\\}$ denote the
set of maximizers of $\phi(\cdot,\mu)$ for fixed $\phi$. For a set $A$, let
$B_{r}(A)=\\{x\colon\min_{y\in A}\left\lVert x-y\right\rVert\leq r\\}$. The
discrepancy function of the pair $(\phi,\mu)$ is

$\alpha(t)=\phi(\theta_{0},\mu)-\sup_{x\in
B^{c}_{t}(E_{\phi,\mu})}\phi(x,\mu).$ (2.2)

In Table 1 below, we explicitly calculate $\alpha$ for several objective
functions of interest in median estimation. The _calibration function_ of the
triple $(\phi,\mu,\pi)$ is the function

$\psi(\lambda)=\min_{r>0}[\lambda\cdot\omega(r)-\log\pi(B_{r}(E_{\phi,\mu}))]$
(2.3)

Note that $\psi(\lambda)$ is decreasing and tends to $0$ as
$\lambda\to\infty$. The _rate function_ of the prior is given by

$I(t)=-\log\pi(B_{t}^{c}(E_{\phi,\mu})).$ (2.4)

The concentration/entropy function of the prior is the rate at which the prior
concentrates around the maximizers of the population risk. For large $t$, it
is the rate of decay of the tails of $\pi$.

Our main result is the following theorem, which says that the accuracy of
$\tilde{\theta}_{n}$ drawn from (2.1).

######  Theorem 2.1.

Suppose that Conditions 1-3 hold for some $K>0$. Then, there are universal
constants $c_{1},c_{2}>0$ such that the following holds. For any $t,\beta>0$,
we have that

$\Pr\left(\max_{\theta_{0}\in
E_{\phi,\mu}}\left\lVert\tilde{\theta}_{n}-\theta_{0}\right\rVert\geq
t\right)\leq\left(\frac{c_{1}n}{\operatorname{VC}(\mathscr{F})}\right)^{\operatorname{VC}(\mathscr{F})}e^{-c_{2}n\left[\frac{1}{\beta}I(t)\vee\alpha(t)\right]^{2}/K^{2}}+e^{-\beta\alpha(t)/2-I(t)/2+\psi(\beta)}.$

It is helpful to view the two terms in the above bounds separately. The first
term measures the sample complexity of estimation and, in the absence of
sampling considerations, recovers the concentration properties of classical
(non-private) estimators. (In particular, the non-private bound can be
obtained from the above by formally setting $\beta=\infty$.) The second term
is novel and is a measure of the cost of sampling and encodes the trade-off
between the prior, $\pi$, the parameter $\beta$, and the objective function
$\alpha$.

###  2.2. Application to differential privacy: consistency of the exponential
mechanism

We now discuss our main results in the context of differential privacy. Let us
begin by briefly recalling the following essential notions and definitions
from differential privacy. For a textbook introduction to the concept of
differential privacy see Dwork and Roth [20].

A _dataset_ of size $n\times d$ is a collection of $n$ points in
$\mathbb{R}^{d}$, $\mathbb{X}_{n}=(X_{\ell})_{\ell=1}^{n}$, with repetitions
allowed. Let $\mathbf{D}_{n\times d}$ be the set of all datasets of size
$n\times d$. For a dataset $\mathbb{Y}_{n}$, let
$\mathcal{D}(\mathbb{Y}_{n},m)=\left\\{\mathbb{Z}_{n}\in\mathbf{D}_{n\times
d}\colon|\mathbb{Z}_{n}\triangle\mathbb{Y}_{n}|=m\right\\},$ that is,
$\mathcal{D}(\mathbb{Y}_{n},m)$ is the set of datasets of size $n\times d$
which differ from $\mathbb{Y}_{n}$ in exactly $m$ points. Two data sets
$\mathbb{Y}_{n}$ and $\mathbb{Z}_{n}$ are said to be _adjacent_ if
$\mathbb{Z}_{n}\in\mathcal{D}(\mathbb{Y}_{n},1)$. Finally, for a dataset
$\mathbb{Y}_{n}$ with empirical measure ${\hat{\mu}}_{\mathbb{Y}_{n}}$ define

$\widetilde{\mathcal{M}}(\mathbb{Y}_{n})=\\{\tilde{\mu}\in\mathcal{M}_{1}(\mathbb{R}^{d})\colon\tilde{\mu}={\hat{\mu}}_{\mathbb{Z}_{n}}\text{
for some }\mathbb{Z}_{n}\in\mathcal{D}(\mathbb{Y}_{n},1)\\}.$

Let us now recall the notion of differential privacy. Suppose that we observe
a dataset ${\mathbb{X}}_{n}$ comprised of $n$ i.i.d. samples from some
distribution $\mu\in\mathcal{M}_{1}(\mathbb{R}^{d})$ and produce a statistic,
$\tilde{\theta}_{n}$, whose law conditionally on the samples depends on their
empirical measure, $\hat{\mu}_{n}$. Let us denote this law by
$P_{\hat{\mu}_{n}}$. The goal of differential privacy is to produce a
statistic such that $P_{{\hat{\mu}}_{n}}$ is non-degenerate and, more
precisely, obeys a certain “privacy guarantee” which is defined as follows.
Following the privacy literature, we call the algorithm that takes
${\hat{\mu}}_{n}$ and returns the (random) statistic, $\tilde{\theta}_{n}$, a
_mechanism_. We also follow the standard abuse of terminology and call
$\tilde{\theta}_{n}$ the mechanism when it is clear from context.

######  Definition 2.2.

A mechanism $\tilde{\theta}_{n}$ is $\epsilon$-differentially private if for
any dataset $\mathbb{Y}_{n}$, any
$\tilde{\mu}\in\widetilde{\mathcal{M}}(\mathbb{Y}_{n})$, and any measurable
set $B$, it holds that

$P_{\hat{\mu}_{\mathbb{Y}_{n}}}(B)\leq e^{\epsilon}P_{\tilde{\mu}}(B).$ (2.5)

The exponential mechanism is defined as follows. For a given base measure
(i.e., prior) $\pi\in\mathcal{M}_{1}(\mathbb{R}^{d})$ and objective function
$\phi:\mathbb{R}^{d}\times\mathcal{M}_{1}(\mathbb{R}^{d})\to\mathbb{R}$, the
_exponential mechanism_ with base measure $\pi$ defined by (2.1) with the
specific choice of $\beta$ given by

$\beta=\frac{\epsilon}{2\mathrm{GS}_{n}(\phi)}.$ (2.6)

Here $\epsilon$ is the _privacy parameter_ , and $\mathrm{GS}_{n}$ is the
_global sensitivity_ of $\phi$ on datasets of size $n$, namely

$\mathrm{GS}_{n}(\phi)=\sup_{\begin{subarray}{c}\mathbb{X}_{n}\in\mathbf{D}_{n\times
d},\\\
\tilde{\mu}_{n}\in\widetilde{\mathcal{M}}(\mathbb{X}_{n})\end{subarray}}\sup_{x}|\phi(x,\hat{\mu}_{n})-\phi(x,{\tilde{\mu}_{n}})|.$

It was shown by McSherry and Talwar [41] that if $\tilde{\theta}_{n}$ is
produced by the exponential mechanism with
$\beta=\epsilon/2\mathrm{GS}_{n}(\phi)$, then it is $\epsilon$-differentially
private. To put our results in this context, note that Condition 3 implies
that $\mathrm{GS}_{n}(\phi)\leq K/n$, see Lemma A.2 and therefore setting
$\beta=n\epsilon/2K$ ensures $\tilde{\theta}_{n}$ is $\epsilon$-differentially
private, see Lemma A.1. Our main technical result provides a consistency bound
(and thereby a sample complexity bound) for the exponential mechanism. More
precisely, Theorem 2.1 in this setting shows the following:

$\Pr\left(\max_{\theta_{0}\in
E_{\phi,\mu}}\left\lVert\tilde{\theta}_{n}-\theta_{0}\right\rVert\geq
t\right)\leq\left(\frac{c_{1}n}{\operatorname{VC}(\mathscr{F})}\right)^{\operatorname{VC}(\mathscr{F})}e^{-c_{2}n\left[\frac{1}{n\epsilon}I(t)\vee\alpha(t)/2K\right]^{2}}+e^{-n\epsilon\alpha(t)/4K-I(t)/2+\psi(n\epsilon/2K)}.$
(2.7)

Let us pause here to interpret this result. The cost of consistent estimation
is encoded in the first terms of (2.7) and, in particular, can be related to
the non-private setting as well. The cost of privacy is encoded in the second
term in (2.7). Finally, we note that the second term in $\eqref{eqn::private-
conc-bound}$ encodes a trade-off between an effect of the prior and the
privacy parameter.

Equation (2.7) readily yields the sample complexity of an estimator drawn from
the exponential mechanism.111To see this briefly, assume for simplicity that
$\pi$ is the uniform measure on a hypercube whose side lengths are at most
polynomial in $d$. In addition, assume that $\theta_{0}$ is well captured by
this hypercube, i.e., $\theta_{0}$ is at least $e^{-d}$ far from any boundary
of the cube. Suppose we want to estimate a maximizer of $\phi(\cdot,\mu)$
within some error level $t$ with probability at least $1-e^{-d}$. Lemma 4.2
and Corollary 3.1 give that it is sufficient for
$\operatorname{VC}(\mathscr{F})$ to be polynomial in $d$ to ensure that the
sample complexity is polynomial in $d$.  See, for instance, Lemma 4.2 and
Corollary 3.1 below. Rather than stating an abstract sample complexity bound,
we present an in-depth study of such bounds in the context of depth-based
median estimation in the next section. We end this section with the following
important remark.

######  Remark 2.2 (Comparison to McSherry and Talwar [41]).

It is helpful to compare our result to the widely used accuracy bound of
McSherry and Talwar [41]. The latter controls the accuracy of the estimator
$\tilde{\theta}_{n}$ as measured by the empirical objective value: it bounds
the difference between the empirical objective value achieved by the
exponential mechanism and the maximal empirical objective value. More
precisely, if we let $S_{t}=\\{x\in\mathbb{R}^{d}\colon\
\phi(x,{\hat{\mu}}_{n})-\sup_{\theta}\phi(\theta,{\hat{\mu}}_{n}))\geq 2t\\}$,
the result of McSherry and Talwar [41] says that

$\Pr\left(\sup_{\theta}\phi(\theta,{\hat{\mu}}_{n})-\phi(\tilde{\theta}_{n},{\hat{\mu}}_{n})>2t\right)\leq
e^{-t\epsilon}/\pi(S_{t}).$

As well, note that there is no analogous sample complexity bound because this
approximation is not improving with the sample size. By contrast, (2.7)
concerns the consistency of $\tilde{\theta}_{n}$ as an estimator, namely the
distance between the estimator and any minimizer of the population objective,
that is $\lVert\tilde{\theta}_{n}-\theta_{0}\rVert$. Furthermore, the quality
of this concentration bound depends on $n$ and thus a sample complexity bound
can be read off readily.

##  3\. Robust private median estimation

As the main application of our results, we provide sample complexity bounds
for differential private robust multivariate location estimation. When
studying multivariate median estimation, one might try to naively extend prior
work on univariate medians to the multivariate setting, i.e., the coordinate-
wise median. This, however, is well-known to be an unsatisfactory as a measure
of center [51]. Indeed, the coordinate-wise median can reside outside the
convex hull of the data [50]. Instead, the key framework for multivariate
median estimation is by minimizing a _depth function_.

Depth functions are functions that assign to each point in space and are
viewed as a measure of centrality with respect to a distribution. They are
functions of the form ${\rm
D}\colon\mathbb{R}^{d}\times\mathcal{M}_{1}(\mathbb{R}^{d})\rightarrow\mathbb{R}^{+}$
which, given a measure and a point in the domain, assigns a number, called the
depth of that point. Given a depth function, the corresponding median is then
defined to be a maximizer of this depth, or simply the deepest point:

$\operatorname{MED}(\mu;{\rm D})=\operatorname*{{\rm
argmax}}_{x\in\mathbb{R}^{d}}{\rm D}(x,\mu).$

Depth-based medians are generally robust, in the sense that they are not
affected by outliers. For instance, depth-based medians have a high breakdown
point and favorable properties related to the influence function [15, 59].
This makes them an interesting direction of study in a differentially private
setting. Examples of commonly used depth functions include the halfspace depth
(or Tukey depth) [54], the simplicial depth [36], the spatial depth [56, 48],
the integrated dual depth (IDD) [17], and the integrated-rank-weighted (IRW)
depth [45]. For a precise definition of the depth functions we discuss here,
as well as a discussion of their basic properties, see Section 5 below. If
instead of the median one is interested in computing depth values themselves,
this can be done privately with an additive noise mechanism, such as the
Laplace mechanism [21]; see Section 6.

###  3.1. Sample complexity for depth-based medians

Using Theorem 2.1, we obtain bounds on the number of samples required for
consistent median estimation via depths. For concreteness, we present our
results for two of the most popular choices of priors, namely Gaussian
measures and the uniform measure on $A_{R}(y)$, the $d$-dimensional cube of
side-length $R$ centered at $y$. In the following, let $d_{R,y}(x)$ denote the
minimum distance from a point $x$ to a face of the cube $A_{R}(y)$:
$d_{R,y}(x)=\min_{1\leq i\leq d}|x_{i}-y_{i}\pm R/2|$. Similarly, denote the
minimum distance from a set $B$ to a face of the cube $A_{R}(y)$ by
$d_{R,y}(B)=\inf_{x\in B}d_{R,y}(x)$ and let $d(x,B)=\inf_{y\in B}\left\lVert
x-y\right\rVert$ denote the usual point-to-set distance.

######  Corollary 3.1.

Suppose that Conditions 1 and 3 hold with $\phi={\rm D}$ for some ${\rm D}$.
In addition, suppose that the map $x\mapsto{\rm D}(x,\mu)$ is $L$-Lipschitz
a.e. for some $L>0$. Then the following holds

  1. (i)

Suppose that ${\rm D}(x,\mu)\leq 1$ and $L\geq 1$. If
$\pi=\mathcal{N}(\theta_{p},\sigma_{p}^{2}I)$, then there exists universal
constants $C,c>0$ such that for all $t\geq 0$, all $d>2$ and all $0<\gamma<1$,
we have that $d(E_{\phi,\mu},\tilde{\theta}_{n})<t$ with probability at least
$1-\gamma$ provided

$n>CK^{2}\left(\frac{\log(1/\gamma)\vee[\operatorname{VC}(\mathscr{F})\log(\frac{K}{c\alpha(t)})\vee
1]}{\alpha(t)^{2}}\vee\frac{\log\left(1/\gamma\right)\vee\left(d(E_{\phi,\mu},\theta_{p})^{2}/\sigma^{2}_{p}\right)\vee
d\log\left(\frac{\sigma_{p}\cdot L}{\alpha(t)}\vee
d\right)}{\epsilon\alpha(t)}\right).$ (3.1)

  2. (ii)

If instead $\pi\propto\mathbbm{1}\left\\{x\in A_{R}(\theta_{p})\right\\}$
where $E_{\phi,\mu}\subset A_{R}(\theta_{p})$, then there exists universal
constants $C,c>0$ such that for all $t\geq 0$, all $d\geq 1$ and all
$0<\gamma<1$, we have that $d(E_{\phi,\mu},\tilde{\theta}_{n})\leq t$ with
probability at least $1-\gamma$ provided

$n>CK^{2}\left(\frac{\log(1/\gamma)\vee[\operatorname{VC}(\mathscr{F})\log(\frac{K}{c\alpha(t)})\vee
1]}{\alpha(t)^{2}}\vee\frac{\log\left(1/\gamma\right)\vee
d\log\left(\frac{R}{d_{R,\theta_{p}}(E_{\phi,\mu})\wedge\alpha(t)/L}\right)}{\alpha(t)\epsilon}\right).$
(3.2)

While we state our result for general depths satisfying the above assumptions,
our results apply to many of the most popular depths, such as half-space depth
and, more broadly, Type D depths in the sense of Zuo and Serfling [60],
spatial depth, simplicial depth and both the integrated rank-weighted and
integrated dual depths. Depths to which these results apply and the conditions
under which they apply are discussed at length in Section 5. The conditions
for specific popular depths are summarized in Table 2. Observe that many of
the depths have $K=O(1)$ and $\operatorname{VC}(\mathscr{F})=O(d)$, in this
case, the cost of privacy is at most a multiplicative factor of $\alpha\log
d/\epsilon$ under a Gaussian prior and $\alpha/\epsilon$ under a uniform
prior.

We note that our bound is essentially sharp, see Lemma 4.5 below. Given the
fact that if $\mu$ is Gaussian, then the population mean equals the population
median, Corollary 3.1 matches the lower bound on the sample complexity for
private Gaussian mean estimation given by [30, Theorem 6.5] and [29, Theorem
7.2] up to logarithmic factors. It also matches the upper bound for one-
dimensional Gaussian mean estimation given in Karwa and Vadhan [32] and the
minimax sample complexity for one-dimensional median estimation given by
Tzamos et al. [55].

Table 1. Table of $\alpha$ for different depth functions and underlying population measures. Note that $v_{1}$ is the eigenvector associated with the largest eigenvalue of $\Sigma$. Recall that $X$ is $d$-version symmetric about zero if for any unit vector $u$, $X^{\top}u\stackrel{{\scriptstyle\text{d}}}{{=}}a(u)Z$ where $Z\sim\nu$ such that $Z\stackrel{{\scriptstyle\text{d}}}{{=}}-Z$ and $a(u)=a(-u)$. ${\rm D}$/$\mu$: | $N_{d}(\theta_{0},\Sigma)$ |  $d$-version symmetric
---|---|---
$\operatorname{HD}$ | $\Phi(t/\sqrt{\lambda_{1}})-1/2$ | $1/2-\sup_{\left\lVert v\right\rVert=1}\inf_{u}F_{0}\left(\frac{-tv^{\top}u}{a(u)}\right)$
$\operatorname{IRW}$ | $\int|1/2-\Phi\left(\frac{tv_{1}^{\top}u}{\sqrt{u^{\top}\Sigma u}}\right)|d\nu$ | $\inf_{\left\lVert v\right\rVert=1}\int|\frac{1}{2}-F_{0}\left(\frac{tv^{\top}u}{a(u)}\right)|d\nu$
$\operatorname{IDD}$ | $1/4-\int\Phi\left(\frac{-tv_{1}^{\top}u}{\sqrt{u^{\top}\Sigma u}}\right)\Phi\left(\frac{tv^{\top}u}{u^{\top}\Sigma u}\right)d\nu$ | $1/4-\sup_{\left\lVert v\right\rVert=1}\int F_{0}\left(\frac{tv^{\top}u}{a(u)}\right)F_{0}\left(\frac{-tv^{\top}u}{a(u)}\right)d\nu$

Recall that estimating a parameter from an unbounded parameter space, i.e.,
unbounded estimation, is non-trivial in the setting of differential privacy,
e.g., see [3]. Corollary 3.1 shows that choosing $\sigma_{p}$ relatively large
allows one to perform unbounded estimation at a cost of only $\log d$ to the
sample complexity. To elaborate, using a depth function in the exponential
mechanism with a Gaussian prior constitutes unbounded estimation of the
population median. Corollary 3.1 then shows that
$d(E_{\phi,\mu},\theta_{p})/\sigma_{p}=O(\sqrt{d\log d})$ is sufficient for
the sample complexity under a Gaussian prior to match the sample complexity
under a correctly specified uniform prior, up to a logarithmic factor in $d$.
Thus, we only require $d(E_{\phi,\mu},\theta_{p})$ to be polynomial in $d$,
i.e., choosing $\sigma_{p}$ to be some large polynomial in $d$ will ensure
that $\sigma_{p}\geq d(E_{\phi,\mu},\theta_{p})/\sqrt{d\log d}$.

######  Remark 3.2.

One popular notion of depth not covered by our analysis is the projection
depth [58]. This is because a private median drawn from the exponential
mechanism based on the empirical versions of this depth function is
inconsistent, see Lemma A.3.

######  Remark 3.3.

The left-hand term in Corollary 3.1 gives an upper bound on the sample
complexity for non-private depth-based medians. If we assume that
$\theta_{0}\in A_{R}(0)$ and choose the depth function to be halfspace depth,
then this upper bound recovers the upper bound on the non-private estimation
error of the halfspace median for the Gaussian measure, given by Theorem 3 of
Zhu et al. [57].

######  Remark 3.4.

The Lipschitz condition is not necessary, however, all the depth functions we
consider are Lipschitz functions a.e. under mild assumptions, see Theorem 5.5.
In addition, virtually all definitions of depth are bounded above by 1 for any
$\mu$ [60]. It is also not necessary to require that $E_{\phi,\mu}\subset
A_{R}(\theta_{p})$. It is sufficient to assume that $E_{\phi,\mu}\cap
A_{R}(\theta_{p})\neq\emptyset$. In this case, one can replace
$d_{R,\theta_{p}}(E_{\phi,\mu})$ with $d_{R,\theta_{p}}(E_{\phi,\mu}\cap
A_{R}(\theta_{p}))$.

###  3.2. Examples

Let us now turn to some concrete examples that illustrate our result. We first
consider the canonical problem of multivariate Gaussian location estimation
under a mis-specified prior. We quantify the relationship between sample
complexity, prior mis-specification, privacy budget, dimension and statistical
accuracy. In this case, for a mis-specification level of
$\left\lVert\theta_{0}-\theta_{p}\right\rVert/\sigma_{p}\leq\sqrt{d\log d}$,
the sample complexity of the private median reduces to $O(d\log d)$.

Next, we consider estimating the location parameter of a population measure
made up of Cauchy marginals. This setup is more difficult in the sense that
the mean of $\mu$ does not exist. We demonstrate that the number of samples
required to estimate location under heavy tails $O(d^{2})$ eclipses the cost
of privacy $O(d^{3/2}\log d/\epsilon)$; if we have enough samples to perform
heavy tailed estimation, then we have enough samples to ensure privacy.

######  Example 3.1 (Multivariate Gaussians with mis-specified prior).

Consider the problem of estimating the location parameter of a multivariate
Gaussian measure, i.e., $\mu=\mathcal{N}(\theta_{0},\Sigma)$ and we wish to
estimate $\theta_{0}$. For this example, let
$\lambda_{1}>\ldots>\lambda_{d}>0$ be the ordered eigenvalues of $\Sigma$.
Suppose that in order to estimate $\theta_{0}$ we use the exponential
mechanism paired with the halfspace depth $\phi=\operatorname{HD}$ in
conjunction with a mis-specified Gaussian prior:
$\pi=\mathcal{N}(\theta_{p},\sigma^{2}_{p}I)$.

In order to apply Corollary 3.1, we need to check Condition 1, 3 and Lipschitz
continuity of $\operatorname{HD}$. First, note that Condition 1 holds for any
bounded depth function as defined in Definition 5.1. Next, one can show that
(see Theorem 5.5) the halfspace depth is $(1,\mathscr{F})$-regular where
$\mathscr{F}$ is the set of closed halfspaces in $\mathbb{R}^{d}$, thus,
$\operatorname{VC}(\mathscr{F})=d+2$. Lastly, the map
$x\mapsto\operatorname{HD}(x,\mu)$ is $L$-Lipschitz with
$L=(2\pi\lambda_{d})^{-1/2}$, implying Condition 2. We may now apply Corollary
3.1, for which we must compute $\alpha(t)$. To this end, it holds that222See
Lemma A.5.

$\alpha(t)=1/2-\sup_{\left\lVert x-\theta_{0}\right\rVert=t}\inf_{\left\lVert
u\right\rVert=1}\Phi\left(\frac{(x-\theta_{0})^{\top}u}{\sqrt{u^{\top}\Sigma
u}}\right)=\Phi\left(t/\sqrt{\lambda_{1}}\right)-1/2.$

Therefore, under halfspace depth, we have consistency to level $t$ with
probability at least $1-\gamma$ provided that

$n\geq
C\left(\frac{\log(1/\gamma)\vee[d\log(\frac{1}{\Phi\left(t/\sqrt{\lambda_{1}}\right)-1/2})\vee
1]}{(\Phi\left(t/\sqrt{\lambda_{1}}\right)-1/2)^{2}}\vee\frac{\log\left(1/\gamma\right)\vee\left(\left\lVert\theta_{0}-\theta_{p}\right\rVert^{2}/\sigma^{2}_{p}\right)\vee
d\log\left(\frac{\sigma_{p}/\lambda_{d}}{\Phi\left(t/\sqrt{\lambda_{1}}\right)-1/2}\vee
d\right)}{\epsilon(\Phi\left(t/\sqrt{\lambda_{1}}\right)-1/2)}\right),$

for some $C>0$ universal. Suppose we would like to achieve a success rate of
$1-e^{-d}$. This reduces the sample complexity bound to

$\displaystyle n\geq
C\left(\frac{d\log\left(\frac{1}{\Phi\left(t/\sqrt{\lambda_{1}}\right)-1/2}\right)\vee
1}{(\Phi\left(t/\sqrt{\lambda_{1}}\right)-1/2)^{2}}\vee\frac{\left(\left\lVert\theta_{0}-\theta_{p}\right\rVert^{2}/\sigma^{2}_{p}\right)\vee
d\log\left(\frac{\sigma_{p}/\lambda_{d}}{\Phi\left(t/\sqrt{\lambda_{1}}\right)-1/2}\vee
d\right)}{\epsilon(\Phi\left(t/\sqrt{\lambda_{1}}\right)-1/2)}\right)\cdot$

For large $d$, the right-hand term dominates the sample complexity. For the
prior effect to be negligible, we require
$\left\lVert\theta_{0}-\theta_{p}\right\rVert/\sigma_{p}\leq\sqrt{d\log d}$
and that $\sigma_{p}$ is at most polynomial in $d$. This suggests that, up to
a point, a larger prior variance $\sigma_{p}^{2}$ produces a lower sample
complexity. In this case, when $t$, $\epsilon$ and $\Sigma$ are fixed, we only
need $n$ to grow slightly faster than the dimension $n\geq Cd\log d$ in order
to maintain a consistent level of error. If the prior effect is negligible in
the sense just described, then the sample complexity bound reduces to

$\displaystyle n\geq
C\left(\frac{d\log\left(\frac{1}{\Phi\left(t/\sqrt{\lambda_{1}}\right)-1/2}\right)\vee
1}{(\Phi\left(t/\sqrt{\lambda_{1}}\right)-1/2)^{2}}\vee\frac{d\log\left(\frac{d/\lambda_{d}}{\Phi\left(t/\sqrt{\lambda_{1}}\right)-1/2}\right)}{\epsilon(\Phi\left(t/\sqrt{\lambda_{1}}\right)-1/2)}\right)\cdot$

The trade-off between the error tolerance $t$ and the privacy parameter
$\epsilon$ is now clear. For example, in the case of a very small error:
$\left(\Phi\left(t/\sqrt{\lambda_{1}}\right)-1/2\right)\leq\epsilon/\log d$,
the privatization does not contribute to the sample complexity. On the other
hand, in the case of large $d$ and fixed $t$, i.e.,
$\left(\Phi\left(t/\sqrt{\lambda_{1}}\right)-1/2\right)\geq\epsilon/\log d$,
the sample complexity is directly affected by the privacy parameter: $n\geq
C\cdot\epsilon^{-1}\cdot d\log d$.

Table 2. Table of values for which different depth functions satisfy Theorem 2.1. Letting $\mu_{u}$ be the law of $X^{\top}u$ if $X\sim\mu$, $f_{u}$ is the density of $\mu_{u}$ with respect to the Lebesgue measure and $L^{\prime}$ denotes $\sup_{y}\mathbb{E}\left\lVert y-X\right\rVert^{-1}$. | $\operatorname{HD}$ | $\operatorname{IDD}$ | $\operatorname{IRW}$ | $\operatorname{SMD}$ | $\operatorname{SD}$ | $\operatorname{MSD}$
---|---|---|---|---|---|---
$\operatorname{VC}(\mathscr{F})$ | $O(d)$ | $O(d)$ | $O(d)$ | $O(d^{2}\log d)$ | $O(d)$ | $O(d)$
$K$ | 1 | 3 | 4 | $d+1$ | $d$ | 1
$L$ | $\sup_{u}\left\lVert f_{u}\right\rVert$ | $3\sup_{u}\left\lVert f_{u}\right\rVert$ | $2\sup_{u}\left\lVert f_{u}\right\rVert$ | $\sup_{u}\left\lVert f_{u}\right\rVert$ | $2L^{\prime}$ | $2\sqrt{d}L^{\prime}$
$\mathscr{A}$ | $\mathcal{M}_{1}(\mathbb{R}^{d})$ | $\mathscr{C}$ | $\mathscr{C}$ | $\mathscr{N}$ |  $\emptyset$ (see Remark 5.3) | $\emptyset$

######  Example 3.2 (Cauchy marginals).

Suppose that $\mu$ is constructed from independent Cauchy marginals with
location parameter 0 and scale parameters $\sigma_{1},\ldots,\sigma_{d}$ and
we would like to use the exponential mechanism to privately estimate the
halfspace median of $\mu$. In this case, $\mu$ is d-version symmetric, with
$a(u)=\sum_{j=1}^{d}\sigma_{j}|u_{j}|$ where $u_{j}$ is the $j^{th}$
coordinate of $u$. A similar analysis as to that of Example 3.1, gives that
halfspace depth satisfies the conditions of Corollary 3.1. Note that in this
setting, the Lipschitz constant scales with the dimension: $L=O(\sqrt{d})$.
The next step is to compute $\alpha(t)$. Let
$\bar{\sigma}=d^{-1}\sum_{j=1}^{d}\sigma_{j}$. Observe that when the scale
parameters are fixed in the dimension,
$\sup_{u}a(u)=~{}\sqrt{d}~{}\bar{\sigma}$. It follows that under the halfspace
depth,
$\alpha(t)=\frac{1}{\pi}\arctan\left(\frac{t}{\sqrt{d}\bar{\sigma}}\right)$.
If $t$ is small, then we can write
$\alpha(t)\approx\pi^{-1}t\sqrt{d}\bar{\sigma}/(d\bar{\sigma}^{2}+t).$ If we
use a Gaussian prior with unit scale,333We don’t lose generality here; we can
arbitrarily shrink the scale of the $\mu$. then the sample complexity bound
becomes

$\displaystyle n$ $\displaystyle\geq C\left(\frac{d^{2}\bar{\sigma}^{2}\log
d}{t^{2}}\vee\frac{d^{1/2}\left[\left\lVert\theta_{p}\right\rVert^{2}+d\log\left(\frac{\bar{\sigma}}{t}d\right)\right]}{\epsilon
t}\right).$

We immediately see the difficulty of estimating location when $\mu$ is high-
dimensional and heavy-tailed: the non-private term is now $O(d^{2})$. On the
other hand, the number of samples required to estimate location under heavy
tails eclipses the cost of privacy, which is $O(d^{3/2}\log d/\epsilon)$.
Thus, if we have enough samples to perform heavy tailed estimation, then we
have enough samples to ensure privacy.

Figure 1. Logarithm of the inverse of the value of the discrepancy function at
$t=1$, $\log(1/\alpha(1))$, as the dimension increases. Here, $\mu$ is made up
of $d$ independent standard Cauchy marginals. Notice that halfspace depth has
the smallest values of $1/\alpha(1)$ which implies it has a smaller bound on
the sample complexity. This demonstrates the trade-off between accuracy and
computability when choosing a depth function. For the integrated depths, the
value of the integrand is approximated via Monte Carlo simulation with 10,000
unit vectors.

In the Gaussian setting, the discrepancy function is relatively similar
between the halfspace depth to the integrated depths. However, in the Cauchy
setting, the discrepancy functions differ between the halfspace depth, the
integrated-rank weighted depth and the integrated dual depth. To see this, we
must evaluate the integrals in Table 1. For the $\operatorname{IRW}$ this
integral is given by

$\alpha(t)=\frac{1}{\pi}\inf_{\left\lVert
v\right\rVert=1}\int\left|\arctan\left(\frac{tv^{\top}u}{\sum_{j=1}^{d}\sigma_{j}|u_{j}|}\right)\right|d\nu(u).$

We evaluate these integrals via Monte Carlo simulation with 10,000 unit
vectors. Figure 1 plots the logarithm of the inverted discrepancy function
computed at $t=1$: $\log(1/\alpha(1))$ for the three depth functions as the
dimension increases. Observe that the halfspace depth’s discrepancy function
decreases the slowest. Thus, the halfspace depth gives the smallest sample
complexity for heavy tailed estimation when the dimension is large. The
difference in accuracy between the halfspace depth and the integrated depths
demonstrates the trade-off between computability and statistical accuracy.

###  3.3. Simulation

To complement our theoretical results, we demonstrate the cost of privacy
through simulation. In order to simulate a private median, we use discretized
Langevin dynamics. We recognize that privacy guarantees are affected by the
use of Markov chain Monte Carlo (MCMC) methods; the purpose of the current
implementation is to investigate the accuracy of the methods. For a discussion
on the level of privacy guaranteed by MCMC, see [46]. As a by-product of our
work, we also provide a fast implementation of a modified version of the non-
private integrated dual depth-based median. This implementation shows that
this multivariate median can be computed quickly, even when the dimension is
large. For example, we can compute the median of ten thousand 100-dimensional
samples in less than one second on a personal computer.444The code was run on
a desktop computer with an Intel i7-8700K 3.70GHz chipset and an Nvidia GTX
1660 super graphics card. We call this modified version of the integrated dual
depth the smoothed integrated dual depth, see Section 5.3 for more details.
Our code is available at [44].

Aside from the private smoothed integrated dual depth median, we also computed
the non-private smoothed integrated dual depth median and the private coin-
press mean of Biswas et al. [7]. When computing the coin-press mean, we used
the existing GitHub implementation provided by the authors. The bounding ball
for the coin-press algorithm had radius $10\sqrt{d}$ and was run for four
iterations.

Figure 2. Empirical root mean squared error (ERMSE) of the location estimates
under (left) Gaussian data and (right) contaminated Gaussian data. In the
uncontaminated setting, the ERMSE of the private median grows at a slightly
faster rate than its non-private counterpart and the mean estimates. This is
due to the cost of privacy. On the other hand, in the contaminated setting,
the ERMSE of median estimates is much lower than that of the mean estimates.
This demonstrates the usual trade-off between accuracy and robustness between
the mean and the median.

We simulated fifty instances with $n=10,000$ over a range of dimensions from
two to one hundred. The data were either generated from a standard Gaussian
measure or contaminated standard Gaussian measure. In the contaminated model,
25% of the observations had mean $(5,\ldots,5)$. The privacy parameter
$\epsilon$ and the smoothing parameter $s$ were both fixed at 10 and
$\pi=\mathcal{N}(0,25dI)$.

Figure 2 shows the empirical root mean squared error (ERMSE) for the different
location estimates as the dimension increases. Notice that the private median
ERMSE grows at a similar rate as that of the non-private ERMSE. The mean
estimates perform very well in the uncontaminated setting, but poorly in the
contaminated setting. The median estimates do not perform as well as the mean
estimates in the standard Gaussian setting, but do not become corrupted in the
contaminated setting. This demonstrates the usual trade-off between accuracy
and robustness between the mean and the median.

##  4\. Proof of main results

Let us now turn to proving the main results in turn. In the following, we
write $a\lesssim b$ if $a\leq Cb$ for some universal constant $C>0$.

######  _Proof of Theorem 2.1_.

We first prove that the regularity conditions imply that the empirical
objective function concentrates around the population objective function. By
Condition 3, there are some $K>0$ and $\mathscr{F}$ with
$\operatorname{VC}(\mathscr{F})<\infty$ such that $\phi$ is
$(K,\mathscr{F})$-regular, i.e.,

$\sup_{x}|\phi(x,\mu)-\phi(x,\hat{\mu}_{n})|\leq
K\sup_{g\in\mathscr{F}}|\mathbb{E}_{\hat{\mu}_{n}}g(X)-\mathbb{E}_{\mu}g(X)|.$
(4.1)

Now, for a probability measure $Q$ over $\mathscr{B}$, let
$N(\tau,\mathscr{F},L_{2}(Q))$ be the $\tau$-covering number of $\mathscr{F}$
with respect to the $L^{2}(Q)$-norm. By assumption, for any $g\in\mathscr{F}$,
$\left\lVert g\right\rVert_{\infty}\leq 1$ and
$\operatorname{VC}(\mathscr{F})<\infty$. This fact implies that there is some
universal $c>0$ such that for any $0<\tau<1$, it holds that,

$\displaystyle\sup_{Q}N\left(\tau,\mathscr{F},L^{2}(Q)\right)\lesssim\operatorname{VC}(\mathscr{F})\left(\frac{c}{\tau}\right)^{2\operatorname{VC}(\mathscr{F})}.$

See [47, Theorem 7.11], or [34, Theorem 9.3]. Talagrand’s inequality [53,
Theorem 1.1] implies that there is some universal $c>0$ such that for all
$n\geq 1$ and for all $t>0$, it holds that

$\Pr\left(\sqrt{n}\sup_{g\in\mathscr{F}}\left|\frac{1}{n}\sum_{i=1}^{n}g(X_{i})-\mathbb{E}g(X)\right|\geq
t\right)\leq\left(\frac{ct^{2}}{\operatorname{VC}(\mathscr{F})}\right)^{\operatorname{VC}(\mathscr{F})}e^{-2t^{2}}.$
(4.2)

The next step is to show that (4.2) implies that

$\Pr\left(\sqrt{n}\sup_{g\in\mathscr{F}}\left|\frac{1}{n}\sum_{i=1}^{n}g(X_{i})-\mathbb{E}g(X)\right|\geq
t\right)\leq\left(\frac{cn}{\operatorname{VC}(\mathscr{F})}\right)^{\operatorname{VC}(\mathscr{F})}e^{-2t^{2}}.$

To this end, we consider two cases. When $t>\sqrt{n}$, this bound trivially
holds because the left-hand side is $0$ since $0\leq g\leq 1$. On the other
hand, when $t\leq\sqrt{n}$, we are simply replacing the $t^{2}$ with $n$ in
the first term of the right-hand side of (4.2).

Now, let $c_{1}^{*}=2/K^{2}$. For all $t>0$, it holds that

$\displaystyle\Pr\left(\sup_{x\in\mathbb{R}^{d}}|\phi(x,\hat{\mu}_{n})-\phi(x,\mu)|>t\right)$
$\displaystyle\leq\Pr\left(K\sup_{g\in\mathscr{F}}\left|\frac{1}{n}\sum_{i=1}^{n}g(X_{i})-\mathbb{E}g(X)\right|>t\right)$
$\displaystyle=\Pr\left(\sqrt{n}\sup_{g\in\mathscr{F}}\left|\frac{1}{n}\sum_{i=1}^{n}g(X_{i})-\mathbb{E}g(X)\right|>\sqrt{n}t/K\right)$
$\displaystyle\leq\left(\frac{cn}{\operatorname{VC}(\mathscr{F})}\right)^{\operatorname{VC}(\mathscr{F})}e^{-2nt^{2}/K^{2}}.$
(4.3)

We can now use the concentration result (4.3) to prove the rest of the
theorem. For brevity, let

$D_{n,t}=\left\\{\max_{\theta_{0}\in
E_{\phi,\mu}}\left\lVert\tilde{\theta}_{n}-\theta_{0}\right\rVert>t\right\\},$

and for any $y>0$, let
$A_{n,y}=\\{\left\lVert\phi(\cdot,\hat{\mu}_{n})-\phi(\cdot,\mu)\right\rVert_{\infty}<y\\}$.
It follows from the law of total probability and (4.3) that for any $y>0$ it
holds that

$\displaystyle\Pr\left(D_{n,t}\right)$ $\displaystyle=\Pr\left(D_{n,t}\cap
A_{n,y}^{c}\right)+\Pr\left(D_{n,t}\cap A_{n,y}\right)$
$\displaystyle\leq\Pr\left(A_{n,y}^{c}\right)+\Pr\left(D_{n,t}\cap
A_{n,y}\right)$
$\displaystyle\leq\left(\frac{cn}{K\operatorname{VC}(\mathscr{F})}\right)^{\operatorname{VC}(\mathscr{F})}e^{-2ny^{2}/K^{2}}+\Pr\left(D_{n,t}\cap
A_{n,y}\right).$ (4.4)

We now focus on the right-hand term above. By definition, we have that

$\displaystyle\frac{1}{\beta}\log\Pr\left(D_{n,t}\cap A_{n,y}\right)$
$\displaystyle=\frac{1}{\beta}\log\int_{A_{n,y}}\frac{\int_{B_{t}^{c}(E_{\phi,\mu})}\exp{\left(\beta\phi(x,\hat{\mu}_{n})\right)}d\pi}{\int_{\mathbb{R}^{d}}\exp{\left(\beta\phi(x,\hat{\mu}_{n})\right)}d\pi}d\mu.$
(4.5)

On $A_{n,y}$ it holds that

$\exp{\left(\beta\phi(x,\mu)\right)}\exp(-\beta
y)\leq\exp{\left(\beta\phi(x,\hat{\mu}_{n})\right)}\leq\exp{\left(\beta\phi(x,\mu)\right)}\exp{(\beta
y)}.$ (4.6)

Applying (4.6) to the right-hand side of (4.5) results in

$\displaystyle\frac{1}{\beta}\log\Pr\left(D_{n,t}\cap A_{n,y}\right)$
$\displaystyle\leq\frac{1}{\beta}\log\int_{A_{n,y}}\frac{\int_{B_{t}^{c}(E_{\phi,\mu})}\exp{\left(\beta\phi(x,\hat{\mu}_{n})\right)}d\pi}{\int_{\mathbb{R}^{d}}\exp{\left(\beta\phi(x,\hat{\mu}_{n})\right)}d\pi}d\mu$
$\displaystyle\leq\frac{1}{\beta}\log\frac{\int_{B_{t}^{c}(E_{\phi,\mu})}\exp{\left(\beta\phi(x,\mu)\right)}d\pi}{\int_{\mathbb{R}^{d}}\exp{\left(\beta\phi(x,,\mu)\right)}d\pi}+\frac{1}{\beta}\log\Pr\left(A_{n,y}\right)+2y$
$\displaystyle\leq\frac{1}{\beta}\log\frac{\int_{B_{t}^{c}(E_{\phi,\mu})}\exp{\left(\beta\phi(x,\mu)\right)}d\pi}{\int_{\mathbb{R}^{d}}\exp{\left(\beta\phi(x,\mu)\right)}d\pi}+2y.$

Thus, we have that

$\displaystyle\frac{1}{\beta}\log\Pr\left(D_{n,t}\cap A_{n,y}\right)$
$\displaystyle\leq\frac{1}{\beta}\log\frac{\int_{B_{t}^{c}(E_{\phi,\mu})}\exp{\left(\beta\phi(x,\mu)\right)}d\pi}{\int_{\mathbb{R}^{d}}\exp{\left(\beta\phi(x,\mu)\right)}d\pi}+2y.$
(4.7)

We now bound $\mathbb{E}_{\pi}\exp{\left(\beta\phi(x,\mu)\right)}$ below. For
any $r>0$, Condition 2 implies that

$\displaystyle\frac{1}{\beta}\log\int_{\mathbb{R}^{d}}\exp{\left(\beta\phi(x,\mu)\right)}d\pi$
$\displaystyle\geq\frac{1}{\beta}\log\int_{B_{r}(E_{\phi,\mu})}\exp{\left(\beta\phi(x,\mu)\right)}d\pi$
$\displaystyle=\phi(\theta_{0},\mu)+\frac{1}{\beta}\log\int_{B_{r}(E_{\phi,\mu})}\exp{\left(\beta(\phi(x,\mu)-\phi(\theta_{0},\mu))\right)}d\pi$
$\displaystyle\geq\phi(\theta_{0},\mu)-\omega(r)+\beta^{-1}\log\pi(B_{r}(E_{\phi,\mu})).$

Maximizing the right-hand side of the above, and recalling the definition of
the calibration function, $\psi$, from (2.3), yields

$\frac{1}{\beta}\log\int_{\mathbb{R}^{d}}\exp{\left(\beta\phi(x,\mu)\right)}d\pi\geq\phi(\theta_{0},\mu)-\psi(\beta)/\beta.$

Plugging this lower bound into (4.7) yields

$\displaystyle\frac{1}{\beta}\log\Pr\left(D_{n,t}\cap A_{n,y}\right)$
$\displaystyle\leq\frac{1}{\beta}\log\int_{B_{t}^{c}(E_{\phi,\mu})}\exp{\left(\beta\phi(x,\mu)\right)}d\pi-\phi(\theta_{0},\mu)+\psi(\beta)/\beta+2y$
$\displaystyle\leq\sup_{x\in
B_{t}^{c}(E_{\phi,\mu})}\phi(x)-\phi(\theta_{0})+\frac{1}{\beta}\log\pi(B_{t}^{c}(E_{\phi,\mu}))+\psi(\beta)/\beta+2y$
$\displaystyle=-\alpha(t)-I(t)/\beta+\psi(\beta)/\beta+2y,$

where the last line follows from the definitions of $\alpha(t)$ and $I(t)$.
Rewriting the last inequality gives that

$\displaystyle\Pr\left(D_{n,t}\cap A_{n,y}\right)$
$\displaystyle\leq\exp\left(-\beta\alpha(t)-I(t)+\psi(\beta)+2\beta y\right).$
(4.8)

Let $c_{4}=c_{1}^{*}/16$. Now, setting $y=f(t,\beta)=\alpha(t)/2\vee
I(t)/2\beta$ and plugging (4.8) into (4.4) results in

$\displaystyle\Pr\left(\max_{\theta_{0}\in
E_{\phi,\mu}}\left\lVert\tilde{\theta}_{n}-\theta_{0}\right\rVert>t\right)$
$\displaystyle\leq\left(\frac{cn}{\operatorname{VC}(\mathscr{F})}\right)^{\operatorname{VC}(\mathscr{F})}e^{-nf(t,\beta)^{2}/(8K^{2})}+\Pr\left(D_{n,t}\cap
A_{n,f(t,\beta)}\right)$
$\displaystyle\leq\left(\frac{cn}{\operatorname{VC}(\mathscr{F})}\right)^{\operatorname{VC}(\mathscr{F})}e^{-nf(t,\beta)^{2}/8K^{2}}+e^{-\beta\alpha(t)-I(t)+\psi(\beta)+2\beta
f(t,\beta)}.$ (4.9)

Now, note that

$\alpha(t)+I(t)/\beta-f(t,\beta)\geq\alpha(t)/2+I(t)/2\beta.$

Plugging this inequality into (4.9) results in

$\displaystyle\Pr\left(\max_{\theta_{0}\in
E_{\phi,\mu}}\left\lVert\tilde{\theta}_{n}-\theta_{0}\right\rVert>t\right)$
$\displaystyle\leq\left(\frac{c}{\operatorname{VC}(\mathscr{F})}\right)^{\operatorname{VC}(\mathscr{F})}e^{-nf(t,\beta)^{2}/(8K^{2})}+e^{-\beta\alpha(t)/2-I(t)/2+\psi(\beta)}.\qed$

We now prove Corollary 3.1 with a series of lemmas. Let us first note the
following fact.

######  Lemma 4.1.

Let $a,b,c\in\mathbb{R}^{+}$. The function $h(x)=ax-b\log\left(cx/b\right)$ is
increasing and positive for

$\displaystyle x\geq\frac{2b}{a}[\log\left(c/a\right)\vee 1].$

###### Proof.

First, we use the derivative test to determine when the function $h(x)$ is
increasing. Doing so yields that $h(x)$ is increasing for $x\geq b/a$. Now, it
remains to find $x\geq b/a$ such that $h(x)\geq 0$. In other words, for
$n^{\prime}(R)=Rb/a,$ we want to find $R\geq 1$ such that
$h(n^{\prime}(R))\geq 0$. By definition,

$\displaystyle h(n^{\prime}(R))$
$\displaystyle=c\left(R-\log\left(dR/ab\right)\right).$

It follows that $h(n^{\prime}(R))\geq 0$ is satisfied for $R$ such that
$R-\log R\geq\log(d/ab).$ Applying the inequality $x-\log x\geq x/2$ for
$x\geq 1$ yields that $R-\log R\geq\log(d/ab)$ is satisfied when

$\displaystyle R\geq 2\log\left(d/ab\right).$

Therefore, $h(n)$ is positive and increasing for

$\displaystyle n\geq 2\frac{c}{ab}\log\left(\frac{d}{ab}\vee e\right).$

######  Lemma 4.2.

Suppose that Conditions 1 and 3 hold with $\phi=D$ for some $K>0$. In
addition, suppose that the map $x\mapsto{\rm D}(x,\mu)$ is $L$-Lipschitz for
some $L>0$. There is a universal $c>0$ such that for all $t\geq 0$, all $d\geq
1$ and all $0<\gamma<1$, we have that
$\left\lVert\tilde{\theta}_{n}-E_{\phi,\mu}\right\rVert<t$ with probability at
least $1-\gamma$ provided that

$n\gtrsim\left[K^{2}\frac{\log(1/\gamma)\vee(\operatorname{VC}(\mathscr{F})\log(\frac{K}{c\alpha(t)})\vee
1)}{\alpha(t)^{2}}\right]\bigvee\left[K\frac{\log\left(1/\gamma\right)\vee-\log\pi(B_{\alpha(t)/4L}(E_{\phi,\mu}))}{\epsilon\alpha(t)}\right].$
(4.10)

###### Proof.

Note that all of the conditions of Theorem 2.1 hold, and so we can apply
Theorem 2.1 with $\beta=n\epsilon/2K$. Proving the sample complexity bound
then amounts to finding $n$ which ensures that

$\displaystyle\left(\frac{c_{1}n}{\operatorname{VC}(\mathscr{F})}\right)^{\operatorname{VC}(\mathscr{F})}e^{-c_{2}n\left[2KI(t)/n\epsilon\vee\alpha(t)\right]^{2}/K^{2}}+e^{-n\epsilon\alpha(t)/2K-I(t)/2+\psi(n\epsilon/2K)}\leq\gamma.$
(4.11)

We will focus on the two terms individually; we will find $n$ such that both

$\displaystyle\left(\frac{c_{1}n}{\operatorname{VC}(\mathscr{F})}\right)^{\operatorname{VC}(\mathscr{F})}e^{-c_{2}n\left[2KI(t)/n\epsilon\vee\alpha(t)\right]^{2}/K^{2}}\leq\gamma/2,$
(4.12)

and

$\displaystyle
e^{-n\epsilon\alpha(t)/2K-I(t)/2+\psi(n\epsilon/2K)}\leq\gamma/2,$ (4.13)

hold. Together, (4.12) and (4.13) imply (4.11).

We start with $n$ such that (4.12) holds. First, note that

$\left(\frac{c_{1}n}{\operatorname{VC}(\mathscr{F})}\right)^{\operatorname{VC}(\mathscr{F})}e^{-c_{2}n\left[2KI(t)/n\epsilon\vee\alpha(t)\right]^{2}/K^{2}}\leq\left(\frac{c_{1}n}{\operatorname{VC}(\mathscr{F})}\right)^{\operatorname{VC}(\mathscr{F})}e^{-c_{2}n\alpha(t)^{2}/K^{2}}.$

We will show a lower bound on $n$ which implies that

$\left(\frac{c_{1}n}{\operatorname{VC}(\mathscr{F})}\right)^{\operatorname{VC}(\mathscr{F})}\leq
e^{c_{2}n\alpha(t)^{2}/2K^{2}}.$ (4.14)

The preceding inequality then implies that

$\left(\frac{c_{1}n}{\operatorname{VC}(\mathscr{F})}\right)^{\operatorname{VC}(\mathscr{F})}e^{-c_{2}n\alpha(t)^{2}/K^{2}}\leq
e^{-c_{2}\alpha(t)^{2}/2K^{2}}.$

from which (4.12) holds provided that

$n\gtrsim\frac{K^{2}\log(2/\gamma)}{\alpha(t)^{2}}.$ (4.15)

It remains to find $n$ such that (4.14) holds.

To this end, define the function

$\displaystyle
h(n)=c_{2}n\alpha(t)^{2}/2K^{2}-\operatorname{VC}(\mathscr{F})\log\left(c_{1}n/\operatorname{VC}(\mathscr{F})\right).$

The condition (4.14) is then equivalent to the condition $h(n)\geq 0$. Note
that $h(n)$ is in the form of Lemma 4.1 with $a=c_{2}\alpha(t)^{2}/2K^{2}$,
$b=\operatorname{VC}(\mathscr{F})$ and $c=c_{1}$. Applying Lemma 4.1 yields
that $h(n)\geq 0$ provided that

$n\gtrsim
K^{2}\frac{\operatorname{VC}(\mathscr{F})\log\left(\frac{K^{2}}{c\alpha(t)^{2}}\right)\vee
1}{\alpha(t)^{2}},$ (4.16)

for some universal $c>0$.

In light of (4.15), it follows that there exists a universal constant $c>0$
such that (4.12) holds provided that

$n\gtrsim
K^{2}\frac{\log(1/\gamma)\vee\operatorname{VC}(\mathscr{F})\log(\frac{K}{c\alpha(t)})\vee
1}{\alpha(t)^{2}}.$ (4.17)

We now turn to finding $n$ such that (4.13) holds. The bound (4.13) is
satisfied when

$n>2K\frac{\log\left(2/\gamma\right)-I(t)/2+\psi(n\epsilon/2K)}{\epsilon\alpha(t)}.$

In order to simplify this bound, we require that

$\displaystyle\psi(n\epsilon/2K)\leq n\epsilon\alpha(t)/4K.$ (4.18)

Given that by assumption ${\rm D}$ is $L$-Lipschitz, we have that
$\omega(r)\leq Lr$. Plugging this in to the definition of $\psi$ from (2.3),
we have that

$\psi(n\epsilon/2K)\leq\min_{r>0}\left\\{\frac{n\epsilon}{2K}\cdot L\cdot
r-\log\pi(B_{r}(E_{\phi,\mu}))\right\\}.$

By taking the specific choice $r=\alpha/4L$, we see that a sufficient
condition for (4.18) to hold is

$\frac{n\epsilon\alpha(t)}{8K}-\log\pi(B_{\alpha(t)/4L}(E_{\phi,\mu}))\leq\frac{n\epsilon\alpha(t)}{4K},$
(4.19)

which is equivalent to

$n>\frac{-4K\log\pi(B_{\alpha(t)/4L}(E_{\phi,\mu}))}{\epsilon\alpha(t)}.$
(4.20)

Combining (4.17) and (4.20) yields that (4.11) is satisfied when

$\displaystyle
n\gtrsim\left[K^{2}\frac{\log(1/\gamma)\vee\operatorname{VC}(\mathscr{F})\log(\frac{K}{c\alpha(t)})\vee
1}{\alpha(t)^{2}}\right]\bigvee\left[K\frac{\log\left(1/\gamma\right)\vee(-\log\pi(B_{\alpha(t)/4L}(E_{\phi,\mu}))}{\epsilon\alpha(t)}\right].$

∎

######  Lemma 4.3.

If $\pi=\mathcal{N}(\theta_{p},\sigma_{p}^{2}I)$ with $\sigma_{p}\geq 1/4$,
then for all $E\subset\mathbb{R}^{d}$, all $d>2$ and all $R\leq\sigma_{p}$ it
holds that

$-\log\pi(B_{R}(E))\lesssim\frac{d(E,\theta_{p})^{2}}{\sigma_{p}^{2}}+d\log\left(\frac{\sigma_{p}}{R}\vee
d\right).$ (4.21)

###### Proof.

Let $R_{*}=R^{2}/\sigma^{2}_{p}$, $\theta_{0}\in E$ and let
$W\sim\chi^{2}_{d}(\left\lVert\theta_{0}-\theta_{p}\right\rVert^{2}/\sigma_{p}^{2})$.
We can lower bound $\pi(B_{R}(E))$ as follows:

$\pi(B_{R}(E))\geq\pi(\left\lVert X-\theta_{0}\right\rVert\leq
R)=\Pr\left(W\leq R_{*}\right).$ (4.22)

Let $G(x,k,\lambda)$ be the cumulative distribution function for the non-
central chi-squared measure with $k$ degrees of freedom and non-centrality
parameter $\lambda$. Recall that for all $x,k,\lambda>0$, it holds that

$\displaystyle G(x,k,\lambda)$
$\displaystyle=e^{-\lambda^{2}}\sum_{j=0}^{\infty}\frac{(\lambda/2)^{j}}{j!}G(x,k+2j)\geq
e^{-\lambda^{2}}G(x,k,0).$

Therefore,

$\Pr\left(W\leq R_{*}\right)\geq
e^{-\left\lVert\theta_{0}-\theta_{p}\right\rVert^{2}/2\sigma_{p}^{2}}G(R_{*},d,0).$
(4.23)

We now lower bound $G(x,d,0)$ for $x\leq 1$. Let $\gamma$ be the lower
incomplete gamma function. It follows from the properties of the gamma
function that

$\displaystyle-\log G(x,d,0)$
$\displaystyle=-\log\gamma(x/2,d/2)+\log\Gamma(d/2)\lesssim-\log\gamma(x/2,d/2)+d\log
d.$

Note that the assumption $d>2$ implies that $\sup_{y}\gamma(y,d/2)\geq 1$.
This implies that $y^{d/2-1}e^{-y/2}$ is increasing on $(0,x)$. Thus, for any
$0<r<1$ it holds that

$\displaystyle-\log G(x,d,0)$
$\displaystyle\lesssim-\log\int_{0}^{x}(y/2)^{d/2-1}e^{-y/2}/2\ dy+d\log d$
$\displaystyle\lesssim-\log(x-r)(r/2)^{d/2-1}/2+r/2+d\log d.$

Setting $r=x/2$ and using the fact that $x\leq 1$ results in

$\displaystyle-\log G(x,d,0)$
$\displaystyle\lesssim\frac{x}{4}+\frac{d}{2}\log\left(\frac{4}{x}\right)+d\log
d\lesssim d\log\left(\frac{4}{x}\vee d\right),$ (4.24)

Note that $R_{*}^{2}=R^{2}/\sigma^{2}_{p}\leq 1$ by assumption. Thus, applying
(4.24) results in

$-\log G(R,d,0)\lesssim d\log\left(\frac{\sigma_{p}}{R}\vee d\right).$ (4.25)

Combining (4.22), (4.23) and (4.25) implies that

$\displaystyle-\log\pi(B_{R}(E))$
$\displaystyle\lesssim\frac{\left\lVert\theta_{0}-\theta_{p}\right\rVert^{2}}{\sigma_{p}^{2}}+d\log\left(\frac{\sigma_{p}}{R}\vee
d\right).$

Now, note that this bound holds for all $\theta_{0}\in E$, therefore, it holds
that

$\displaystyle-\log\pi(B_{R}(E))$
$\displaystyle\lesssim\frac{d(E,\theta_{p})^{2}}{\sigma_{p}^{2}}+d\log\left(\frac{\sigma_{p}}{R}\vee
d\right).\qed$

######  Lemma 4.4.

Suppose that $\pi\propto\mathbbm{1}\left\\{x\in A_{R}(\theta_{p})\right\\}$
where $E\subset A_{R}(\theta_{p})$, then for all $E\subset\mathbb{R}^{d}$,
$d>0$ and all $r>0$ it holds that

$\displaystyle-\log\pi(B_{r}(E))\lesssim
d\log\left(\frac{R}{d_{R,\theta_{p}}(E)\wedge r}\right).$

###### Proof.

First, note that for any ball $B_{r}(x)$ such that $B_{r}(x)\subset
A_{R}(\theta_{p})$, we have that

$\displaystyle\pi(B_{r}(x))=\frac{r^{d}\pi^{d/2}}{R^{d}\Gamma(d/2+1)}\geq\left(\frac{r}{R}\right)^{d}\left(d/2+1\right)^{d/2+1}\pi^{d/2}e^{-d/2}\geq\left(\frac{r}{R}\right)^{d}\left(\frac{\pi
d}{2e}\right)^{d/2}.$

Taking the negated logarithm of both sides implies that

$-\log\pi(B_{r}(x))\lesssim d\log\left(\frac{R}{r}\right)-d\log\pi
d/2+d\lesssim d\log\left(\frac{R}{r}\right).$ (4.26)

If there exists $\theta_{0}\in E$ such that $B_{r}(\theta_{0})\subset
A_{R}(\theta_{p})$ then (4.26) implies that

$-\log\pi(B_{r}(\theta_{0}))\lesssim d\log\left(\frac{R}{r}\right).$ (4.27)

If instead there exists $\theta_{0}\in E$ such that $A_{R}(\theta_{p})\subset
B_{r}(\theta_{0})$ then

$-\log\pi(B_{r}(\theta_{0}))=0.$ (4.28)

Suppose finally that for all $\theta_{0}\in E$ it holds that both
$B_{r}(\theta_{0})\not\subset A_{R}(\theta_{p})$ and
$A_{R}(\theta_{p})\not\subset B_{r}(\theta_{0})$. Now, by assumption, there
exists $\theta_{0}\in E$ such that $\theta_{0}\in A_{R}$. For such
$\theta_{0}\in A_{R}$, the definition of $d_{R,\theta_{p}}$ immediately
implies that $B_{d_{R,\theta_{p}}(\theta_{0})}(\theta_{0})\subset
A_{R}(\theta_{p})$. Therefore, (4.26) implies that

$-\log\pi(B_{r}(E))\leq-\log\pi(B_{r}(\theta_{0}))\lesssim
d\log\left(\frac{R}{d_{R,\theta_{p}}(\theta_{0})}\right).$ (4.29)

It follows from (4.27), (4.28) and (4.29) that for all $d>0$ and all $0r$ it
holds that

$-\log\pi(B_{r}(E))\lesssim
d\log\left(\frac{R}{d_{R,\theta_{p}}(\theta_{0})\wedge r}\right).$ (4.30)

Note that (4.30) holds for all $\theta_{0}\in E$, thus, for all $d>0$ and all
$0r>0$ it holds that

$-\log\pi(B_{r}(E))\lesssim d\log\left(\frac{R}{d_{R,\theta_{p}}(E)\wedge
r}\right).\qed$

We can now prove Corollary 3.1.

######  _Proof of Corollary 3.1_.

First note that by assumption, all of the conditions of Lemma 4.2 are
satisfied. To prove (3.1) and (3.2) we apply Lemma 4.3 and Lemma 4.4,
respectively, in conjunction with Lemma 4.2. To apply Lemma 4.3, first,
observe that together, the assumptions that $L>1$, $\sigma_{p}^{2}\geq 1/16$
and ${\rm D}(x;\mu)\leq 1$ imply that $\alpha(t)/4L\sigma_{p}\leq 1$. Applying
Lemma 4.3 with $R=\alpha(t)/4L$ and $E=E_{\phi,\mu}$ in conjunction with
(4.10) yields that there exists a universal constant $c>0$ such that for all
$t\geq 0$, all $d>2$ and all $0<\gamma<1$, we have that
$d(E_{\phi,\mu},\tilde{\theta}_{n})<t$ with probability at least $1-\gamma$
provided that

$n\gtrsim
K^{2}\left[\frac{\log(1/\gamma)\vee(\operatorname{VC}(\mathscr{F})\log(\frac{K}{c\alpha(t)})\vee
1)}{\alpha(t)^{2}}\right]\bigvee\left[K\frac{\log\left(1/\gamma\right)\vee
d(E_{\phi,\mu},\theta_{p})^{2}/\sigma^{2}_{p}\vee
d\log\left(\frac{L\sigma_{p}}{\alpha(t)}\vee
d\right)}{\epsilon\alpha(t)}\right].$

To show (3.2), we apply Lemma 4.4 with $r=\alpha(t)/4L$ and $E=E_{\phi,\mu}$
in conjunction with (4.10), which yields that there exists a universal
constant $c_{1}>0$ such that for all $t\geq 0$, all $d\geq 1$ and all
$0<\gamma<1$, we have that $d(E_{\phi,\mu},\tilde{\theta}_{n})<t$ with
probability at least $1-\gamma$ provided that

$\displaystyle n\gtrsim
K^{2}\left[\frac{\log(1/\gamma)\vee(\operatorname{VC}(\mathscr{F})\log(\frac{K}{c\alpha(t)})\vee
1)}{\alpha(t)^{2}}\right]\bigvee\left[K\frac{\log\left(1/\gamma\right)\vee
d\log\left(\frac{R}{d_{R,\theta_{p}}(E_{\phi,\mu})\wedge\alpha(t)/L}\right)}{\alpha(t)\epsilon}\right].$

###  4.1. Optimality of Corollary 3.1

######  Lemma 4.5.

The upper bound on the sample complexity of $\tilde{\theta}_{n}$ given in
Corollary 3.1 is sharp, up to logarithmic factors.

###### Proof.

Recall that Theorem 6.5 of [30] is given by

######  Theorem.

For any $t\leq 1$ smaller than some absolute constant, any
$(\epsilon,\delta)$-DP mechanism (for $\delta\leq O(\sqrt{d}R/n)$ which
estimates a Gaussian measure (with mean $\theta_{0}\in A_{R}(0)$ and known
covariance $\sigma^{2}I$) to accuracy $\leq t$ in total variation distance
with probability $\geq 2/3$ requires
$n~{}=~{}\Omega(\frac{d}{t\epsilon\log(dR)})$ samples.

We show that for a specific set of parameters, the upper bound given in
Corollary 3.1 matches the lower bound of Theorem 6.5 of [30] up to logarithmic
factors in $d$ and $t^{-1}$. Specifically, set ${\rm D}=\operatorname{HD}$,
$\theta_{0}\in A_{R}(0)$, $\pi=A_{R}(0)$, that
$\mu=\mathcal{N}(\theta_{0},\sigma^{2}I)$. For $t\geq R$, the sample
complexity is $1$. We then focus on the case where $t\leq R$.

We now check the conditions of Corollary 3.1 under these parameters. First,
$\sup_{x}{\rm D}(x,\mu)={\rm D}(\theta_{0},\mu)$ and so Condition 1 is
satisfied. Next, $\operatorname{HD}$ satisfies Condition 3 with $K=1$ and
$\operatorname{VC}(\mathscr{F})=d+2$, as shown in Lemma B.4. Furthermore, we
have that $\operatorname{HD}(\cdot,\mu)$ is $\sigma^{-1}$-Lipschitz.
Therefore, the conditions of Corollary 3.1 are satisfied.

Plugging these values into Corollary 3.1 then gives the bound

$n\gtrsim\frac{\log(1/\gamma)\vee d\log\left(\frac{K}{\alpha(t)}\vee
e\right)}{\alpha(t)^{2}}\vee\frac{\log\left(1/\gamma\right)\vee
d\log\left(\frac{R/\sigma}{d_{R,\theta_{p}}(\theta_{0})\wedge\alpha(t)}\vee
d\right)}{\alpha(t)\epsilon}.$

Setting $\gamma=1/3$, as in Theorem 6.5 of [30], results in

$n\gtrsim\frac{d\log\left(\frac{K}{\alpha(t)}\vee
e\right)}{\alpha(t)^{2}}\vee\frac{d\log\left(\frac{R/\sigma}{d_{R,\theta_{p}}(\theta_{0})\wedge\alpha(t)}\vee
d\right)}{\alpha(t)\epsilon}.$ (4.31)

Note that in this case, we have that

$\alpha(t)=\Phi(t/\sigma)-1/2.$

Let $a(R)=(\Phi(R/\sigma)-1/2)/R$. Now, since $t\leq R$, concavity of $\Phi$
on $\mathbb{R}^{+}$ implies that

$\alpha(t)=\Phi(t/\sigma)-1/2\geq\left(\frac{\Phi(R/\sigma)-1/2}{R}\right)t=a(R)t.$
(4.32)

Applying (4.32) to (4.31) results in

$n\gtrsim\frac{d\log\left(\frac{1}{a(R)t}\vee e\right)}{a(R)^{2}\cdot
t^{2}}\vee\frac{d\log\left(\frac{R/\sigma}{d_{R,\theta_{p}}(\theta_{0})\wedge
a(R)t}\vee d\right)}{a(R)\cdot t\cdot\epsilon},$

which matches the bound given in Theorem 6.5 of [30] up to logarithmic factors
in $d$ and $t^{-1}$. ∎

##  5\. Depth functions and their properties

For the convenience of the reader, we collect here some basic facts about
depth functions. We begin by recalling the definition of depth functions. (We
work with a slightly weaker notion of depth than is common in the literature
to unify notation. See Remark 5.1) We then review several common depth
functions in the literature and their properties. We then introduce a new
depth function, the smoothed integrated dual depth, which has desirable
properties from a computational perspective and is used in our simulations.
For proofs of the results from this section, see Section B.

###  5.1. Definition of a depth function

Recall that a measure $\mu\in\mathcal{M}_{1}(\mathbb{R}^{d})$ is _centrally
symmetric_ about a point $x\in\mathbb{R}^{d}$ if
$X-x\stackrel{{\scriptstyle\text{d}}}{{=}}x-X$ for $X\sim\mu$. In the
following, for $A\in\mathbb{R}^{d\times d}$ and $b\in\mathbb{R}^{d}$, let
$A\mu+b$ be the law of $AX+b$ if $X\sim\mu$ and let
$\mathscr{C}_{x}\subset\mathcal{M}_{1}(\mathbb{R}^{d})$ denote the set of
centrally symmetric measures about $x$.

######  Definition 5.1.

A function ${\rm
D}\colon\mathbb{R}^{d}\times\mathcal{M}_{1}(\mathbb{R}^{d})\rightarrow\mathbb{R}^{+}$
is a _depth function_ with admissible set
$\mathscr{A}\subset\mathcal{M}_{1}(\mathbb{R}^{d})$ if, for all
$\mu\in\mathscr{A}$, the following four properties hold:

  1. (1)

Similarity invariance: For all orthogonal matrices $A\in\mathbb{R}^{d\times
d}$ and $b\in\mathbb{R}^{d}$ it holds that ${\rm D}(x,\mu)={\rm
D}(Ax+b,A\mu+b)$.

  2. (2)

Maximality at center: If $\mu\in\mathscr{C}_{\theta_{0}}$ then ${\rm
D}(\theta_{0},\mu)=\sup_{x}{\rm D}(x,\mu)$.

  3. (3)

Decreasing along rays: Suppose ${\rm D}$ is maximized at $\theta_{0}$. For all
$p\in(0,1)$, it holds that ${\rm D}(x,\mu)\leq{\rm
D}(p\theta_{0}+(1-p)x,\mu)\leq{\rm D}(\theta_{0},\mu).$

  4. (4)

Vanishing at infinity: $\lim_{c\rightarrow\infty}{\rm D}(cu,\mu)=0$ for any
unit vector $u$.

######  Remark 5.1.

Note that we use a weaker definition of a depth function than is given in the
influential work of Zuo and Serfling [60], which replaces similarity
invariance with affine invariance. For a discussion of desirable properties
for a depth function to possess, see [60, 38, 49].

###  5.2. Some well-known depth functions and their properties

We now define several depth functions discussed in this paper, after which we
give a short summary of their properties. For $X\sim\mu$, define

$F(x,u,\mu)=\mu\left(\mathbbm{1}\left\\{X^{\top}u\leq
x^{\top}u\right\\}\right)\qquad\text{and}\qquad
F(x-,u,\mu)=\mu\left(\mathbbm{1}\left\\{X^{\top}u<x^{\top}u\right\\}\right).$

Halfspace depth, otherwise known as Tukey depth [54], is defined as follows:

######  Definition 5.2 (Halfspace depth).

The halfspace depth $\operatorname{HD}$ of a point $x\in\mathbb{R}^{d}$ with
respect to $\mu\in\mathcal{M}_{1}(\mathbb{R}^{d})$ is

$\operatorname{HD}(x,\mu)=\inf_{\left\lVert u\right\rVert=1}F(x,u,\mu).$

The halfspace depth of a point $x\in\mathbb{R}^{d}$ is the minimum probability
mass contained in a closed halfspace containing $x$. Another classical depth
function is the simplicial depth [36, 37]. Let $\Delta(x_{1},\ldots,x_{d+1})$
be the $d$-dimensional simplex with vertices $x_{1},\ldots,x_{d+1}$.
Simplicial depth is defined as follows:

######  Definition 5.3 (Simplicial Depth).

Suppose that $Y_{1},\ldots,Y_{d+1}$ are i.i.d. from
$\mu~{}\in~{}\mathcal{M}_{1}(\mathbb{R}^{d})$. The simplicial depth of a point
$x\in\mathbb{R}^{d}$ with respect to $\mu$ is

$\operatorname{SMD}(x,\mu)=\Pr\left(x\in\Delta(Y_{1},\ldots,Y_{d+1})\right).$

The simplicial depth of a point $x\in\mathbb{R}^{d}$ can be interpreted as the
probability that $x$ is contained in the simplex defined by $d+1$ draws from
$\mu$. The next depth function we introduce is spatial depth [56, 48], which
is maximized at the well-known spatial median [56]. Define the spatial sign
function [14, 33] as

$\operatorname{SR}(y)=\left\\{\begin{array}[]{cc}y/\left\lVert
y\right\rVert&y\neq 0\\\ 0&y=0\end{array}\right..$

We can then define the spatial rank function as
$\mathbb{E}_{\mu}\operatorname{SR}(x-X)$. The norm of the spatial rank of
$x\in\mathbb{R}^{d}$ is a measure of the outlyingness of $x$ with respect to
$\mu$. With this in mind, the spatial depth is defined as follows:

######  Definition 5.4.

The spatial depth $\operatorname{SD}$ of a point $x\in\mathbb{R}^{d}$ with
respect to $\mu\in\mathcal{M}_{1}(\mathbb{R}^{d})$ is

$\operatorname{SD}(x,\mu)=1-\left\lVert\mathbb{E}_{\mu}\operatorname{SR}(x-X)\right\rVert.$
(5.1)

We will see below that the spatial depth is $(K,\mathscr{F})$-regular,
however, $K=O(d)$. Replacing the norm in (5.1) with its square eliminates this
inconvenience, and still yields a depth function which is maximized at the
spatial median. Therefore, we define the modified spatial depth as follows:

######  Definition 5.5.

The modified spatial depth $\operatorname{MSD}$ of a point
$x\in\mathbb{R}^{d}$ with respect to $\mu\in\mathcal{M}_{1}(\mathbb{R}^{d})$
is

$\operatorname{MSD}(x,\mu)=1-\left\lVert\mathbb{E}_{\mu}\operatorname{SR}(x-X)\right\rVert^{2}.$

Lastly, we define the integrated depth functions. Here, the idea is to define
the depth of a point $x\in\mathbb{R}^{d}$ as the average, univariate depth
$x^{\top}u$ over all directions $u$. The first integrated depth function555The
first integrated multivariate depth function, to be precise. The first
integrated depth was developed for functional data [26]. is the integrated
dual depth of Cuevas and Fraiman [17], which, letting $\nu$ be the uniform
measure on $\mathbb{S}^{d-1}$, is defined as follows:

######  Definition 5.6 (Integrated Dual Depth).

The integrated dual depth of a point $x\in\mathbb{R}^{d}$ with respect to
$\mu\in\mathcal{M}_{1}(\mathbb{R}^{d})$ is

$\operatorname{IDD}(x,\mu)=\int_{\mathbb{S}^{d-1}}F(x,u,\mu)\left(1-F(x,u,\mu)\right)d\nu(u).$
(5.2)

The integrated dual depth of $x\in\mathbb{R}^{d}$ is the average univariate
simplicial depth of $x^{\top}u$ over all directions $u\in\mathbb{S}^{d-1}$.
The integrated rank-weighted depth [45] replaces the simplicial depth in (5.2)
with a slightly modified version of halfspace depth:

######  Definition 5.7 (Integrated Rank-Weighted Depth).

The integrated rank-weighted depth of a point $x\in\mathbb{R}^{d}$ with
respect to $\mu\in\mathcal{M}_{1}(\mathbb{R}^{d})$ is

$\operatorname{IRW}(x,\mu)=2\int_{\mathbb{S}^{d-1}}F(x,u,\mu)\wedge\left(1-F(x-,u,\mu)\right)d\nu(u).$

We now turn to a brief discussion of when the aforementioned functions are in
fact depth functions over some admissible set. To this end, let us recall the
following classes of measures. Let
$\mathscr{C}\subset\mathcal{M}_{1}(\mathbb{R}^{d})$ denote the set of
centrally symmetric measures over $\mathbb{R}^{d}$. A measure $\mu$ is
_angularly symmetric_ about a point $\theta_{0}\in\mathbb{R}^{d}$ if
$\frac{X-\theta_{0}}{\left\lVert
X-\theta_{0}\right\rVert}\stackrel{{\scriptstyle\text{d}}}{{=}}\frac{\theta_{0}-X}{\left\lVert
X-\theta_{0}\right\rVert}$ for $X\sim\mu$ [37]. Let
$\mathscr{N}\subset\mathcal{M}_{1}(\mathbb{R}^{d})$ denote the set of
angularly symmetric measures over $\mathbb{R}^{d}$ that are absolutely
continuous with respect to the Lebesgue measure. The following proposition
collects existing results in the literature:

######  Proposition 5.2.

The aforementioned depth functions satisfy the following:

  * •

Halfspace depth is a depth function with admissible set
$\mathcal{M}_{1}(\mathbb{R}^{d})$.

  * •

Simplicial depth is a depth function with admissible set $\mathscr{N}$.

  * •

Spatial depth and the modified spatial depth satisfy properties (1), (2) and
(4) for all $\mu~{}\in~{}\mathcal{M}_{1}(\mathbb{R}^{d})$.

  * •

Integrated dual depth and integrated rank-weighted depth are depth functions
with admissible set $\mathscr{C}$. Furthermore, they satisfy properties (1),
(2) and (4) for any $\mu\in\mathcal{M}_{1}(\mathbb{R}^{d})$.

######  Remark 5.3.

Note that spatial depth does not satisfy Definition 5.1, as property (3) fails
to hold. However, spatial depth satisfies spatial angle monotonicity and
spatial rank monotonicity [49, see Section 4.3], which together provide a
weaker alternative to property (3). This allows one to interpret
$\operatorname{SD}$ as a measure of depth. In addition, simplicial depth and
halfspace depth are affine invariant, which is a stronger version of property
(1).

######  Remark 5.4.

Both the halfspace depth and the simplicial depth function have an exact
computational running time of $O(n^{d-1})$, see, e.g., [23, 2] and the
references therein. By contrast, the spatial depth and the integrated depth
functions are computable in high dimensions [14, 45]. For instance, the
integrated depth functions can be approximated easily via sampling, say, $m$
points from $\nu$. One can then approximate the sample depth value of a given
point in $O(mnd)$ time [45].

The following theorem demonstrates that the depth functions defined in this
section satisfy the conditions of Theorem 2.1. Let $\mu_{u}$ be the law of
$X^{\top}u$ if $X\sim\mu$.

######  Theorem 5.5.

The aforementioned depth functions satisfy the following:

  * •

Condition 1 holds for each of the depth functions defined in Section 5.

  * •

Suppose that $\pi$ is absolutely continuous and that for all
$u\in\mathbb{S}^{d-1}$, the measure $\mu_{u}$ is absolutely continuous with
density $f_{u}$ and $\sup_{\left\lVert u\right\rVert=1}\left\lVert
f_{u}\right\rVert_{\infty}=L<\infty$. Then there exists a universal constant
$C>0$ such that for all $s\in(0,\infty]$, halfspace, simplicial, integrated
rank-weighted and the smoothed integrated dual depth666The smoothed integrated
dual depth is introduced in Section 5.3 below and equals the integrated dual
depth when $s=\infty$. satisfy Condition 2 with $\omega(r)=C\cdot L\cdot r$.

  * •

Suppose that $\mu$ has a bounded density and that
$\sup_{y}\mathbb{E}\left\lVert y-X\right\rVert^{-1}=L^{\prime}\leq\infty$.
Then modified spatial depth satisfies Condition 2 with
$\omega(r)=2\sqrt{d}\cdot L^{\prime}\cdot r$ and spatial depth satisfies
Condition 2 with $\omega(r)=2\cdot L^{\prime}\cdot r$.

  * •

Condition 3 holds for each of the depth functions defined in Section 5.

The above results are also summarized in Table 2.

###  5.3. The smoothed integrated dual depth

One issue with many of the aforementioned depth functions is that their
empirical versions contain indicator functions, which are non-smooth. This
fact is inconvenient from an optimization perspective, e.g., we cannot apply
gradient descent to estimate the median. To resolve this issue, recall that

$\mathbbm{1}\left\\{X_{i}^{\top}u\leq
x^{\top}u\right\\}\approx\sigma\left(s(x-X)^{\top}u\right),$

for large $s$, where $\sigma$ is the usual sigmoid function:
$\sigma(x)=(1+e^{-x})^{-1}$. This motivates the following definition of depth,
which we use in our simulation study from Section 3.3.

######  Definition 5.8 (Smoothed Integrated Dual Depth).

The smoothed integrated dual depth with smoothing parameter $s>0$ of a point
$x\in\mathbb{R}^{d}$ with respect to $\mu\in\mathcal{M}_{1}(\mathbb{R}^{d})$
is

$\operatorname{IDD}(x,\mu,s)=\int_{\mathbb{S}^{d-1}}\mathbb{E}\sigma\left(s(x-X)^{\top}u\right)\left(1-\mathbb{E}\sigma\left(s(x-X)^{\top}u\right)\right)d\nu(u).$
(5.3)

As $s\rightarrow\infty$, the smoothed integrated dual depth converges to the
integrated dual depth. However, the smoothed integrated dual depth is
convenient in that its empirical version is differentiable. Furthermore, the
smoothed integrated dual depth is a depth with admissible set $\mathscr{C}$:

######  Proposition 5.6.

For any $s>0$, the smoothed integrated dual depth is a depth function with
admissible set $\mathscr{C}$. In addition, properties (1) and (4) hold for any
$\mu\in\mathcal{M}_{1}(\mathbb{R}^{d})$.

In the simulations presented in Section 3.3, we approximate (5.3) with

$\widehat{\operatorname{IDD}}(x,\mu,s)=\frac{1}{M}\sum_{m=1}^{M}\mathbb{E}\sigma\left(s(x-X)^{\top}u_{m}\right)\left(1-\mathbb{E}\sigma\left(s(x-X)^{\top}u_{m}\right)\right),$

where $u_{1},\ldots,u_{M}$ are drawn i.i.d. from $\nu$. We can show that the
number of necessary unit vectors needed to maintain a fixed level of error
with high probability is polynomial in $n$ and $d$:

######  Proposition 5.7.

Let $u_{1},\ldots,u_{M}$ be i.i.d. from $\nu$. Then for all $d,s,t>0$ and all
$0<\gamma<1$, there exists a universal constant $c_{1}>0$ such that

$\sup_{x}\left|\widehat{\operatorname{IDD}}(x,\hat{\mu}_{n},s)-\operatorname{IDD}(x,\hat{\mu}_{n},s)\right|\leq
t,$

with probability $1-\gamma$, provided that

$\displaystyle M\geq c_{1}\frac{\log(1/\gamma)\vee dn\log\left(\frac{1}{t}\vee
e\right)}{t^{2}}.$

##  6\. Computing private depth values

Aside from computing medians, the depth values themselves can be of interest.
For example, they are used in visualization and a host of inference procedures
[35, 16]. We can use the theoretical analysis from the previous sections to
study simple differentially private methods for estimating depth values. If we
know a-priori the values at which we would like to compute the depth, then we
can use an additive noise mechanism, such as the Laplace mechanism or the
Gaussian mechanism [21]. These mechanisms simply add noise to a statistic that
is calibrated to ensure that differential privacy is satisfied. For example,
for some non-private statistic $T(\hat{\mu}_{n})$, the Laplace mechanism is
defined as

$\widetilde{T}(\hat{\mu}_{n})=T(\hat{\mu}_{n})+W_{1}\mathrm{GS}_{n}(T)/\epsilon,$

where $W_{1}\sim\operatorname*{{\rm Laplace}}(1)$. It is well known that the
statistic $\widetilde{T}(\hat{\mu}_{n})$ is $\epsilon$-differentially private
[21]. Theorem 2.1 implies that the private depth values generated from the
Laplace mechanism concentrate around their population values:

######  Corollary 6.1.

Suppose that ${\rm D}$ satisfies Condition 3. For $x\in\mathbb{R}^{d}$ chosen
independently of the data, it holds that

$\widetilde{{\rm D}}(x,\hat{\mu}_{n})={\rm
D}(x,\hat{\mu}_{n})+W_{1}\frac{K}{n\epsilon},$

is $\epsilon$-differentially private. In addition, there exists universal
constants $c_{1},c_{2}>0$ such that for all $t\geq 0$ it holds that

$\Pr\left(\left|\widetilde{{\rm D}}(x,\hat{\mu}_{n})-{\rm
D}(x,\mu)\right|>t\right)\leq\left(\frac{c_{1}n}{\operatorname{VC}(\mathscr{F})}\right)^{\operatorname{VC}(\mathscr{F})}e^{-c_{2}nt^{2}/K^{2}}+e^{-n\epsilon
t/2K}.$

###### Proof.

Together, Lemma A.2 and the definition of the Laplace mechanism imply that
$\widetilde{{\rm D}}(x,\hat{\mu}_{n})$ is $\epsilon$-differentially private.
Furthermore, the properties of the Laplace measure give that

$\displaystyle\Pr\left(\left|\widetilde{{\rm D}}(x,\hat{\mu}_{n})-{\rm
D}(x,\mu)\right|>t\right)$ $\displaystyle\leq\Pr\left(\left|{\rm
D}(x,\hat{\mu}_{n})-{\rm
D}(x,\mu)\right|>t/2\right)+\Pr\left(|W_{1}\frac{K}{n\epsilon}|>t/2\right)$
$\displaystyle\leq\Pr\left(\left|{\rm D}(x,\hat{\mu}_{n})-{\rm
D}(x,\mu)\right|>t/2\right)+e^{-n\epsilon t/2K}.$

Applying (4.3) yields

$\displaystyle\Pr\left(\left|\widetilde{{\rm D}}(x,\hat{\mu}_{n})-{\rm
D}(x,\mu)\right|>t\right)$ $\displaystyle\leq
e^{\operatorname{VC}(\mathscr{F})\log\left(c_{1}\frac{n}{\operatorname{VC}(\mathscr{F})}\right)-c_{2}nt^{2}}+e^{-n\epsilon
t/2K}.\qed$

Therefore, Corollary 6.1 suggests taking $\epsilon\propto t/K$ when simulating
private depth values. An obvious problem of interest is estimating the vector
of depth values at the sample points, i.e., how can we estimate

$\widehat{\mathbf{D}}(\hat{\mu}_{n})=\left({\rm
D}(X_{1},\hat{\mu}_{n}),\ldots,{\rm D}(X_{n},\hat{\mu}_{n})\right),$

privately? In general,
$\mathrm{GS}_{n}(\widehat{\mathbf{D}}(\hat{\mu}_{n}))=O(1)$, see Lemma A.4. As
a result, if $\widetilde{\mathbf{D}}$ is the vector of depth values generated
from the Laplace mechanism then
$\left\lVert\widetilde{\mathbf{D}}(\hat{\mu}_{n})-\mathbf{D}(\mu)\right\rVert=O_{p}(n^{1/2})$;
the level of noise is greater than that of the sampling error. This result is
intuitive; these vectors reveal more information about the population as $n$
grows, which differs markedly from the single depth value case, where the
amount of information received is fixed in $n$. In fact, for large $n$ the
vector of depth values at the sample points contains a significant amount of
information about $\mu$; the depth function can, under certain conditions,
characterize the distribution of the input measure $\mu$ [see 52, 42, and the
references therein]. In order to release so much information about the
population privately, we must inject non-negligible noise.

We cannot, then, simply plug in the $n$ private sample depth values into an
inference procedure and proceed. We can instead sample $N$ points from the
exponential mechanism for the median given in Section 3 using a very small
$\epsilon$. This will give points similar in nature to the original sample. We
can then either apply Corollary 6.1 to these points or compute the sample
depth function from those private points. The performance of these procedures
in specific inference settings is an interesting topic of future research.

##  7\. Conclusion

In this paper we studied using the exponential mechanism to estimate
differentially private depth-based medians and depth values. We proved upper
bounds on the sample complexity of these private depth-based medians, which
also results in concentration inequalities on the private depth values. The
upper bound on the sample complexity for many of the medians is $O(d\log d)$,
which matches the lower bound on private Gaussian mean estimation up to
logarithmic factors [see Theorem 6.5 of 30]. We introduce a new general
regularity condition “$(K,\mathscr{F})$-regularity” and associated sample
complexity result (Corollary 3.1) which can be used to prove an upper bound on
the sample complexity of any $(K,\mathscr{F})$-regular function used in the
exponential mechanism.

In terms of future research, practical polynomial time, private approximations
of these estimators is a main issue. The given estimators have exponential
running time in the dimension, which is not computationally feasible in high
dimensions. Additional directions of future study include the following: Can
we use the data to privately inform a prior on the median? We have discussed
how to assess the accuracy for given $\epsilon$, but how can we choose the
appropriate value of $\epsilon$ to ensure privacy? One might also ask how
these procedures perform in other privacy models, and how other depth-based
inference methods perform under differential privacy.

## Acknowledgments

The authors acknowledge Gautam Kamath for his helpful comments and discussion,
which improved the paper.

## Funding

The authors acknowledge the support of the Natural Sciences and Engineering
Research Council of Canada (NSERC). Cette recherche a été financée par le
Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG),
[RGPIN-2020-04597, DGECR-2020-00199].

## References

  * Abowd et al. [2022] J. Abowd, R. Ashmead, R. Cumings-Menon, S. Garfinkel, M. Heineck, C. Heiss, R. Johns, D. Kifer, P. Leclerc, A. Machanavajjhala, B. Moran, W. Sexton, M. Spence, and P. Zhuravlev.  The 2020 Census Disclosure Avoidance System TopDown Algorithm.  _Harvard Data Science Review_ , (Special Issue 2), 6 2022\.  https://hdsr.mitpress.mit.edu/pub/7evz361i.
  * Afshani et al. [2015] P. Afshani, D. R. Sheehy, and Y. Stein.  Approximating the simplicial depth.  _arXiv e-prints_ , 2015.  arXiv:1512.04856.
  * Avella-Medina and Brunel [2019] M. Avella-Medina and V.-E. Brunel.  Differentially private sub-Gaussian location estimators.  _arXiv e-prints_ , 2019.  arXiv:1906.11923.
  * Awan and Slavković [2021] J. Awan and A. Slavković.  Structure and sensitivity in differential privacy: Comparing $k$-norm mechanisms.  _Journal of the American Statistical Association_ , 116(534):935–954, 2021.  doi: 10.1080/01621459.2020.1773831.
  * Awan et al. [2019] J. Awan, A. Kenney, M. Reimherr, and A. Slavković.  Benefits and pitfalls of the exponential mechanism with applications to Hilbert spaces and functional PCA.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97, pages 374–384. PMLR, 6 2019.
  * Beimel et al. [2019] A. Beimel, , S. Moran, K. Nissim, and U. Stemmer.  Private center points and learning of halfspaces.  In _Proceedings of the Thirty-Second Conference on Learning Theory_ , volume 99, pages 269–282. PMLR, 6 2019.
  * Biswas et al. [2020] S. Biswas, Y. Dong, G. Kamath, and J. Ullman.  CoinPress: Practical private mean and covariance estimation.  _Advances in Neural Information Processing Systems_ , 33:14475–14485, 2020.
  * Brown et al. [2021] G. Brown, M. Gaboardi, A. Smith, J. Ullman, and L. Zakynthinou.  Covariance-aware private mean estimation without private covariance estimation.  _Advances in Neural Information Processing Systems_ , 34:7950–7964, 2021.
  * Brunel and Avella-Medina [2020] V.-E. Brunel and M. Avella-Medina.  Propose, test, release: Differentially private estimation with high probability.  _arXiv e-prints_ , 2020.  arXiv:2002.08774.
  * Bun and Steinke [2019] M. Bun and T. Steinke.  Average-case averages: Private algorithms for smooth sensitivity and mean estimation.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Bun et al. [2019] M. Bun, G. Kamath, T. Steinke, and S. Z. Wu.  Private hypothesis selection.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Cai et al. [2021] T. T. Cai, Y. Wang, and L. Zhang.  The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy.  _The Annals of Statistics_ , 49(5):2825 – 2850, 2021.  doi: 10.1214/21-AOS2058.
  * Chaudhuri and Hsu [2012] K. Chaudhuri and D. Hsu.  Convergence rates for differentially private statistical estimation.  In _Proceedings of the International Conference on Machine Learning._ , page 1327, 2012.
  * Chaudhuri [1996] P. Chaudhuri.  On a geometric notion of quantiles for multivariate data.  _Journal of the American Statistical Association_ , 91:862–872, 1996.
  * Chen and Tyler [2002] Z. Chen and D. E. Tyler.  The influence function and maximum bias of Tukey’s median.  _Annals of Statistics_ , 30(6):1737–1759, 2002\.  doi: 10.1214/aos/1043351255.
  * Chenouri et al. [2011] S. Chenouri, C. G. Small, and T. J. Farrar.  Data depth-based nonparametric scale tests.  _Canadian Journal of Statistics_ , 39(2):356–369, 2011.  doi: 10.1002/cjs.10099.
  * Cuevas and Fraiman [2009] A. Cuevas and R. Fraiman.  On depth measures and dual statistics. a methodology for dealing with general data.  _Journal of Multivariate Analysis_ , 100(4):753–766, 2009.
  * Differential Privacy Team [2017] Differential Privacy Team.  Learning with privacy at scale.  _Apple_ , 2017.
  * Dwork and Lei [2009] C. Dwork and J. Lei.  Differential privacy and robust statistics.  _Proceedings of the 41st annual ACM symposium on theory of computing - STOC ’09_ , page 371, 2009.
  * Dwork and Roth [2014] C. Dwork and A. Roth.  The algorithmic foundations of differential privacy.  _Foundations and Trends in Theoretical Computer Science_ , 9(3–4):211–407, 2014.  ISSN 1551-305X.  doi: 10.1561/0400000042.
  * Dwork et al. [2006] C. Dwork, F. McSherry, K. Nissim, and A. Smith.  Calibrating noise to sensitivity in private data analysis.  In _Theory of Cryptography Conference_ , pages 265–284, 2006.
  * Dwork et al. [2017] C. Dwork, A. Smith, T. Steinke, and J. Ullman.  Exposed! A survey of attacks on private data.  _Annual Review of Statistics and Its Application_ , 4(1):61–84, 4 2017.  doi: 10.1146/annurev-statistics-060116-054123.
  * Dyckerhoff and Mozharovskyi [2016] R. Dyckerhoff and P. Mozharovskyi.  Exact computation of the halfspace depth.  _Computational Statistics & Data Analysis_, 98:19–30, 2016.
  * Dümbgen [1992] L. Dümbgen.  Limit theorems for the simplicial depth.  _Statistics & Probability Letters_, 14(2):119 – 128, 1992.  doi: https://doi.org/10.1016/0167-7152(92)90075-G.
  * Foygel Barber and Duchi [2014] R. Foygel Barber and J. C. Duchi.  Privacy and statistical risk: Formalisms and minimax bounds.  _arXiv e-prints_ , 2014.  arXiv:1412.4451.
  * Fraiman and Muniz [2001] R. Fraiman and G. Muniz.  Trimmed means for functional data.  _Test_ , 10(2):419–440, 12 2001.  ISSN 1133-0686.  doi: 10.1007/BF02595706.
  * Gao and Sheffet [2020] Y. Gao and O. Sheffet.  Private approximations of a convex hull in low dimensions.  _arXiv e-prints_ , 2020.  arXiv:2007.08110.
  * [28] M. Guevara.  How we’re helping developers with differential privacy.  Technical report.
  * Hopkins et al. [2022] S. B. Hopkins, G. Kamath, and M. Majid.  Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism.  In _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_ , pages 1406–1417, 2022.
  * Kamath et al. [2018] G. Kamath, J. Li, V. Singhal, and J. Ullman.  Privately learning high-dimensional distributions.  _arXiv e-prints_ , 2018.  arXiv:1805.00216.
  * Kamath et al. [2020] G. Kamath, V. Singhal, and J. Ullman.  Private mean estimation of heavy-tailed distributions.  _arXiv e-prints_ , 2 2020.  arXiv:2002.09464.
  * Karwa and Vadhan [2017] V. Karwa and S. Vadhan.  Finite sample differentially private confidence intervals.  _arXiv e-prints_ , 2017.  arXiv:1711.03908.
  * Koltchinskii [1997] V. I. Koltchinskii.  M-estimation, convexity and quantiles.  _The Annals of Statistics_ , 25:435–477, 1997.
  * Kosorok [2008] M. R. Kosorok.  _Introduction to empirical processes and semiparametric inference._ Springer, 2008.
  * Li and Liu [2004] J. Li and R. Y. Liu.  New nonparametric tests of multivariate locations and scales using data depth.  _Statistical Science_ , 19(4):686–696, 11 2004\.  doi: 10.1214/088342304000000594.
  * Liu [1988] R. Y. Liu.  On a notion of simplicial depth.  _Proceedings of the National Academy of Sciences_ , 85(6):1732–1734, 1988.  doi: 10.1073/pnas.85.6.1732.
  * Liu [1990] R. Y. Liu.  On a notion of data depth based on random simplices.  _Annals of Statistics._ , 18(1):405–414, 3 1990\.  doi: 10.1214/aos/1176347507.
  * Liu et al. [2006] R. Y. Liu, R. J. Serfling, and D. L. Souvaine.  _Data depth: Robust multivariate analysis, computational geometry, and applications_ , volume 72.  American Mathematical Soc., 2006.
  * Liu et al. [2021a] X. Liu, W. Kong, S. Kakade, and S. Oh.  Robust and differentially private mean estimation.  _arXiv e-prints_ , 2021a.  arXiv:2102.09159.
  * Liu et al. [2021b] X. Liu, W. Kong, and S. Oh.  Differential privacy and robust statistics in high dimensions.  _arXiv e-prints_ , 2021b.  arXiv:2111.06578.
  * McSherry and Talwar [2007] F. McSherry and K. Talwar.  Mechanism design via differential privacy.  In _48th Annual IEEE Symposium on Foundations of Computer Science_ , pages 94–103. IEEE, 10 2007.  doi: 10.1109/FOCS.2007.4389483.
  * Nagy [2021] S. Nagy.  Halfspace depth does not characterize probability distributions.  _Statistical Papers_ , 62(3):1135–1139, 2021\.
  * Ramsay and Chenouri [2021] K. Ramsay and S. Chenouri.  Differentially private depth functions and their associated medians.  _arXiv e-prints_ , 2021.  arXiv:2101.02800.
  * Ramsay and Jagannath [2022] K. Ramsay and A. Jagannath.  DP-MVT-Medians.  https://github.com/12ramsake/DP-MVT-Medians, 2022.  GitHub repository.
  * Ramsay et al. [2019] K. Ramsay, S. Durocher, and A. Leblanc.  Integrated rank-weighted depth.  _Journal of Multivariate Analysis_ , 173:51 – 69, 2019\.  doi: https://doi.org/10.1016/j.jmva.2019.02.001.
  * Seeman et al. [2021] J. Seeman, M. Reimherr, and A. Slavković.  Exact privacy guarantees for markov chain implementations of the exponential mechanism with artificial atoms.  _Advances in Neural Information Processing Systems_ , 34:13125–13136, 2021.
  * Sen [2018] B. Sen.  A gentle introduction to empirical process theory and applications.  _Lecture Notes, Columbia University_ , 2018.
  * Serfling [2002] R. Serfling.  A depth function and a scale curve based on spatial quantiles.  In _Statistical Data Analysis Based on the $L_{1}$-Norm and Related Methods_, pages 25–38. Birkhäuser Basel, 2002.
  * Serfling [2019] R. Serfling.  Depth functions on general data spaces, II. Formulation and maximality, with consideration of the Tukey, projection, spatial, and “contour” depths.  Technical report, Serfling & Thompson Statistical Consulting, 2019.
  * Serfling [2006] R. J. Serfling.  Depth functions in nonparametric multivariate inference.  _Data Depth: Robust Multivariate Analysis, Computational Geometry, and Applications_ , pages 1–16, 2006.
  * Small [1990] C. G. Small.  A survey of multidimensional medians.  _International Statistical Review / Revue Internationale de Statistique_ , 58(3):263, 12 1990.  doi: 10.2307/1403809.
  * Struyf and Rousseeuw [1999] A. Struyf and P. J. Rousseeuw.  Halfspace depth and regression depth characterize the empirical distribution.  _Journal of Multivariate Analysis_ , 69:1355153, 1999.
  * Talagrand [1994] M. Talagrand.  Sharper bounds for gaussian and empirical processes.  _The Annals of Probability_ , 22(1):28–76, 1994\.  ISSN 00911798.
  * Tukey [1974] J. W. Tukey.  Mathematics and the picturing of data.  In _Proceedings of the International Congress of Mathematicians_ , 1974.
  * Tzamos et al. [2020] C. Tzamos, E.-V. Vlatakis-Gkaragkounis, and I. Zadik.  Optimal private median estimation under minimal distributional assumptions.  _Advances in Neural Information Processing Systems_ , 33:3301–3311, 2020.
  * Vardi and Zhang [2000] Y. Vardi and C.-H. Zhang.  The multivariate $L_{1}$-median and associated data depth.  _Proceedings of the National Academy of Sciences of the United States of America_ , 97:1423–6, 03 2000.  doi: 10.1073/pnas.97.4.1423.
  * Zhu et al. [2020] B. Zhu, J. Jiao, and J. Steinhardt.  When does the Tukey median work?  _2020 IEEE International Symposium on Information Theory_ , pages 1201–1206, 2020.  doi: 10.1109/ISIT44484.2020.9173995.
  * Zuo [2003] Y. Zuo.  Projection-based depth functions and associated medians.  _The Annals of Statistics_ , 31(5):1460–1490, 10 2003.  doi: 10.1214/aos/1065705115.
  * Zuo [2004] Y. Zuo.  Influence function and maximum bias of projection depth based estimators.  _Annals of Statistics_ , 32(1):189–218, 2004\.
  * Zuo and Serfling [2000] Y. Zuo and R. Serfling.  General notions of statistical depth function.  _Annals of Statistics_ , 28(2):461–482, 2000\.

##  Appendix A Auxiliary Lemmas

######  Lemma A.1.

Suppose $U_{n}$ is an upper bound on $\mathrm{GS}_{n}(\phi)$. Setting
$\beta=\epsilon/2U_{n}$ implies $\tilde{\theta}_{n}$ is
$\epsilon$-differentially private.

###### Proof.

From the definition of differential privacy, it is immediate that for any
$0<\delta_{1}<\delta_{2}$, we have that $\delta_{1}$-differential privacy
implies $\delta_{2}$-differential privacy. Now, it remains to show that
$\tilde{\theta}_{n}$ is $\delta$-differentially private for some
$\delta<\epsilon$. To see this, note that
$\epsilon/2U_{n}\leq\epsilon/2\mathrm{GS}_{n}(\phi)$, which implies that there
exists $\delta<\epsilon$ such that
$\epsilon/2U_{n}=\delta/2\mathrm{GS}_{n}(\phi)$. This implies that
$\tilde{\theta}_{n}$ is $\delta$-differentially private and the result
follows. ∎

######  Lemma A.2.

If $\phi$ satisfies Condition 3 then $\mathrm{GS}_{n}(\phi)\leq K/n$.

###### Proof.

Definition 2.1 gives that

$\sup_{\begin{subarray}{c}\mathbb{X}_{n}\in\mathbf{D}_{n\times d},\\\
\tilde{\mu}_{n}\in\widetilde{\mathcal{M}}(\mathbb{X}_{n})\end{subarray}}\sup_{x}|\phi(x,\hat{\mu}_{n})-\phi(x,\tilde{\mu}_{n})|\leq
K\sup_{\begin{subarray}{c}\mathbb{X}_{n}\in\mathbf{D}_{n\times d},\\\
\tilde{\mu}_{n}\in\widetilde{\mathcal{M}}(\mathbb{X}_{n})\end{subarray}}\sup_{g\in\mathscr{F}}|\int
gd(\hat{\mu}_{n}-\tilde{\mu}_{n})|\leq K\sup_{g\in\mathscr{F}}\left\lVert
g\right\rVert/n=K/n.\qed$

######  Lemma A.3.

Let ${\rm D}$ be the projection depth with location measure
$\operatorname{MED}$ and scale measure $\operatorname{MAD}$. If
$\epsilon=O(1)$ and $\pi$ is not proportional to $\mathbbm{1}\left\\{x\in
E_{{\rm D},\mu}\right\\}$, then $\mathrm{GS}_{n}({\rm D})=1$ and a median
drawn from the exponential mechanism based on ${\rm D}$ with
$\beta=\epsilon/2\mathrm{GS}_{n}({\rm D})$ is inconsistent $\mu$-a.s. .

###### Proof.

The univariate sample median has infinite global sensitivity [9], which
implies that the projection depth with location measure $\operatorname{MED}$
and scale measure $\operatorname{MAD}$ has sensitivity 1. Zuo [58] gives that
${\rm D}(x,\hat{\mu}_{n})\rightarrow{\rm D}(x,\mu)\ \mu-a.s.$ as
$n\rightarrow\infty$. Thus, $Q_{\hat{\mu}_{n},\beta}\rightarrow Q_{\mu,\beta}\
\mu-a.s.$ as $n\rightarrow\infty$. If $\pi$ is not proportional to
$\mathbbm{1}\left\\{x\in E_{{\rm D},\mu}\right\\}$, then there exists $t>0$
such that $Q_{\mu,\beta}(d(E_{\mu,\phi},X)\geq t)\neq 0$. Thus, there exists
$t>0$ such that

$\Pr\left(d(E_{\mu,\phi},\tilde{\theta}_{n})\geq t\right)\rightarrow
Q_{\mu,\beta}(d(E_{\mu,\phi},X)\geq t)\neq 0\ \mu-a.s.\ .\qed$

######  Lemma A.4.

Suppose that ${\rm D}$ is non-negative and satisfies properties (2) and (4) in
Definition 5.1. Then there exists a universal constant $C>0$ such that
$\mathrm{GS}_{n}(\widehat{\mathbf{D}}(\hat{\mu}_{n}))\geq C$. Furthermore, if
${\rm D}$ satisfies Condition 3, then
$\mathrm{GS}_{n}(\widehat{\mathbf{D}}(\hat{\mu}_{n}))=O(1)$.

###### Proof.

Consider $\tilde{\mu}_{n}$ to be centrally symmetric about $X_{1}$. Property
(2) and non-negativity imply that ${\rm D}(X_{1},\tilde{\mu}_{n})=C>0$. Let
$\tilde{\mu}_{n}(Y_{1})$ be the empirical measure corresponding to
$Y_{1},\ldots,X_{n}$ with $Y_{1}\neq X_{1}$. Given that
$\tilde{\mu}_{n}(Y_{1})\in\widetilde{\mathcal{M}}(\mathbb{X}_{n})$, property
(4) implies that

$\displaystyle\mathrm{GS}_{n}(\widehat{\mathbf{D}}(\hat{\mu}_{n}))$
$\displaystyle\geq\sup_{Y_{1}\in\mathbb{R}^{d}}|{\rm
D}(Y_{1},\tilde{\mu}_{n}(Y_{1}))-{\rm D}(X_{1},\hat{\mu}_{n})|\geq{\rm
D}(X_{1},\hat{\mu}_{n})-\inf_{Y_{1}\in\mathbb{R}^{d}}{\rm
D}(Y_{1},\tilde{\mu}_{n}(Y_{1}))\geq C.$

Now, if ${\rm D}$ satisfies Condition 3, then Lemma A.2 implies that

$\displaystyle\mathrm{GS}_{n}(\widehat{\mathbf{D}}(\hat{\mu}_{n}))^{2}$
$\displaystyle\leq\frac{K^{2}}{n}+\sup_{\hat{\mu}_{n},y}|{\rm
D}(y,\hat{\mu}_{n})-{\rm
D}(X_{1},\hat{\mu}_{n})|^{2}\leq\frac{K^{2}}{n}+\left\lVert{\rm
D}\right\rVert=O(1).\qed$

######  Lemma A.5.

If $\mu=\mathcal{N}(\theta_{0},\Sigma)$ then for all $t>0$ and positive
definite $\Sigma$, $\sup_{\left\lVert
x\right\rVert=t}\operatorname{HD}(x,\mu)=\Phi(-t/\sqrt{\lambda_{1}})$.

###### Proof.

From the fact that $\operatorname{HD}$ is affine invariant, without loss of
generality we can set $\theta_{0}=0$. From the fact that $\Phi$ is increasing,
it holds that

$\displaystyle\sup_{\left\lVert x\right\rVert=t}\operatorname{HD}(x,\mu)$
$\displaystyle=\sup_{\left\lVert x\right\rVert=t}\inf_{\left\lVert
u\right\rVert=1}\Phi(\frac{x^{\top}u}{\sqrt{u^{\prime}\Sigma
u}})=1-\inf_{\left\lVert v\right\rVert=1}\sup_{\left\lVert
u\right\rVert=1}\Phi(\frac{tv^{\top}u}{\sqrt{u^{\prime}\Sigma
u}})=1-\Phi(t\inf_{\left\lVert v\right\rVert=1}\sup_{\left\lVert
u\right\rVert=1}\frac{v^{\top}u}{\sqrt{u^{\prime}\Sigma u}}).$

It suffices to compute

$\inf_{\left\lVert v\right\rVert=1}\sup_{\left\lVert
u\right\rVert=1}\frac{(v^{\top}u)^{2}}{u^{\prime}\Sigma u}.$

First, note that

$\displaystyle\inf_{\left\lVert v\right\rVert=1}\sup_{\left\lVert
u\right\rVert=1}\frac{(v^{\top}u)^{2}}{u^{\prime}\Sigma
u}\geq\inf_{\left\lVert
v\right\rVert=1}\frac{(v^{\top}v)^{2}}{v^{\prime}\Sigma v}=1/\lambda_{1}.$

Showing the reverse inequality, setting $v=e_{1}$ and setting
$z=\Sigma^{1/2}u$ gives that

$\displaystyle\inf_{\left\lVert v\right\rVert=1}\sup_{\left\lVert
u\right\rVert=1}\frac{(v^{\top}u)^{2}}{u^{\prime}\Sigma u}$
$\displaystyle\leq\sup_{\left\lVert
u\right\rVert=1}\frac{(e_{1}^{\top}u)^{2}}{u^{\top}\Sigma
u}=\sup_{\left\lVert\Sigma^{-1/2}z\right\rVert=1}\frac{(e_{1}^{\top}\Sigma^{-1/2}z)^{2}}{z^{\top}z}=\sup_{\left\lVert\Sigma^{-1/2}z\right\rVert=1}(e_{1}^{\top}z/\left\lVert
z\right\rVert)^{2}/\lambda_{1}\leq\frac{1}{\lambda_{1}}.$

Thus,

$\displaystyle\sup_{\left\lVert x\right\rVert=t}\operatorname{HD}(x,\mu)$
$\displaystyle=1-\Phi(t/\sqrt{\lambda_{1}})\geq\Phi(-t/\sqrt{\lambda_{1}}).$

∎

##  Appendix B Proofs of the results from Section 5

We now prove the various results presented in Section 5.

###### Proof of Proposition 5.2.

With the exception of the modified spatial depth, these results were shown by
[60, 36, 48, 17, 45], respectively. For the modified spatial depth, properties
(1), (2) and (4) follow from the fact that properties (1), (2) and (4) for
spatial depth. ∎

###### Proof of Proposition 5.6.

We prove properties (1)-(4) in order. Let $A\in\mathbb{R}^{d\times d}$ be any
orthogonal matrix and $b\in\mathbb{R}^{d}$. For any integrable function
$h\colon\mathbb{S}^{d-1}\rightarrow\mathbb{R}^{+}$ , it holds that

$\int_{\mathbb{S}^{d-1}}h(u)d\nu=\int_{\mathbb{S}^{d-1}}h(Au)d\nu.$ (B.1)

Given that $A$ is an orthogonal matrix, it also holds that

$(Ax+b-AX-b)^{\top}u=A^{\top}(x-X)^{\top}u=A^{\top}u^{\top}(x-X).$

Let $Y\sim A\mu+b$. Applying the above identity implies that

$\mathbb{E}\sigma\left(s(Ax+b-Y)^{\top}u\right)=\mathbb{E}\sigma\left(sA^{\top}u(x-X)\right).$

The result follows from the definition of the smoothed integrated dual depth
and (B.1).

For property (2), by definition $\sup_{x}\operatorname{IDD}(x,\mu,s)\leq 1/4$.
It remains to show $\operatorname{IDD}(\theta_{0},\mu,s)=1/4$. We will use the
fact that

$(1-\sigma(x-X))=\sigma(X-x).$ (B.2)

Now, consider the integrand in the definition of smoothed integrated dual
depth at any fixed $u$. Central symmetry of $\mu$ and (B.2) yield that

$\displaystyle\mathbb{E}\sigma\left(s(\theta_{0}-X)^{\top}u\right)\left(1-\mathbb{E}\sigma\left(s(\theta_{0}-X)^{\top}u\right)\right)$
$\displaystyle=\left(\mathbb{E}\sigma\left(s(X-\theta_{0})^{\top}u\right)\right)^{2}.$

Central symmetry of $\mu$ and (B.2) also yield that

$\displaystyle\mathbb{E}\sigma\left(s(\theta_{0}-X)^{\top}u\right)\left(1-\mathbb{E}\sigma\left(s(\theta_{0}-X)^{\top}u\right)\right)$
$\displaystyle=\left(1-\mathbb{E}\sigma\left(s(X-\theta_{0})^{\top}u\right)\right)^{2}.$

These two equalities yield that

$\displaystyle\qquad\mathbb{E}\sigma\left(s(X-\theta_{0})^{\top}u\right)=1/2.$

Given that this holds for any $u\in\mathbb{S}^{d-1}$, it follows immediately
that
$\operatorname{IDD}(\theta_{0};\mu,s)=1/4=\sup_{x}\operatorname{IDD}(x;\mu,s)$.

For property (3), at any fixed $u$, central symmetry of $\mu$ and the fact
that $\sigma$ is increasing yields that either

$\displaystyle\mathbb{E}\sigma\left(s(x-X)^{\top}u\right)\leq\mathbb{E}\sigma\left(s(p\theta_{0}+(1-p)x-X)^{\top}u\right)\leq
1/2,$

holds or

$\displaystyle
1/2\leq\mathbb{E}\sigma\left(s(p\theta_{0}+(1-p)x-X)^{\top}u\right)\leq\mathbb{E}\sigma\left(s(x-X)^{\top}u\right),$

holds. The result follows immediately from the fact that $f(x)=x(1-x)$ is
monotone on both $[0,1/2]$ and $[1/2,1]$.

Lastly, we show property (4). For any fixed $u$, the fact that
$\lim_{x\rightarrow\infty}\sigma(x)\sigma(-x)=0$ and the bounded convergence
theorem imply that

$\displaystyle\lim_{c\rightarrow\infty}\operatorname{IDD}(cu;\mu,s)$
$\displaystyle=\lim_{c\rightarrow\infty}\int_{\mathbb{S}^{d-1}}\left(\mathbb{E}\sigma\left(s(cu-X)^{\top}u\right)\right)\left(1-\mathbb{E}\sigma\left(s(cu-X)^{\top}u\right)\right)d\nu(u)$
$\displaystyle=\int_{\mathbb{S}^{d-1}}\lim_{c\rightarrow\infty}\left(\mathbb{E}\sigma\left(s(cu-X)^{\top}u\right)\right)\left(1-\mathbb{E}\sigma\left(s(cu-X)^{\top}u\right)\right)d\nu(u)$
$\displaystyle=0.\qed$

###### Proof of Proposition 5.7.

Let

$Z=\sup_{x}\left|\widehat{\operatorname{IDD}}(x,\hat{\mu}_{n},s)-\operatorname{IDD}(x,\hat{\mu}_{n},s)\right|.$

We first prove a concentration result for $Z$. To this end, let

$\displaystyle G_{n}(x,u,s)$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\sigma\left(s(x-X_{i})^{\top}u\right)$
$\displaystyle W_{1}$
$\displaystyle=\sup_{x}\left|\frac{1}{M}\sum_{m=1}^{M}G_{n}(x,u_{m},s)-\int_{\mathbb{S}^{d-1}}G_{n}(x,u,s)d\nu(u)\right|$
$\displaystyle W_{2}$
$\displaystyle=\sup_{x}\left|\frac{1}{M}\sum_{m=1}^{M}G_{n}(x,u_{m},s)^{2}-\int_{\mathbb{S}^{d-1}}G_{n}(x,u,s)^{2}d\nu(u)\right|.$

From the fact that $Z\leq W_{1}+W_{2}$, we need only prove concentration
results for $W_{1}$ and $W_{2}$. Let

$\displaystyle\mathscr{G}$ $\displaystyle=\left\\{\sigma(y^{\top}u+b)/n\colon
y\in\mathbb{R}^{d},\ b\in\mathbb{R}\right\\}.$

Note that $\operatorname{VC}(\mathscr{G})\leq d+2$. Therefore, it follows from
Lemma 7.11 in [47] that there exists a universal constant $K>0$ such that for
all $\epsilon\in(0,1)$, it holds that

$\sup_{Q}N(\epsilon/n,\mathscr{G},L_{2}(Q))\leq\left(\frac{K}{\epsilon}\right)^{2d+4}.$

Now, define

$\sum_{i=1}^{n}\mathscr{G}_{i}=\left\\{\frac{1}{n}\sum_{i=1}^{n}\sigma(y_{i}^{\top}u+b_{i})\colon
y_{1},\ldots,y_{n}\in\mathbb{R}^{d},\
,b_{1},\ldots,b_{n}\in\mathbb{R}\right\\}.$

It follows from Lemma 7.19 in [47] that for all $\epsilon\in(0,1)$, it holds
that

$\displaystyle\sup_{Q}N\left(2\epsilon,\sum_{i=1}^{n}\mathscr{G}_{i},L_{2}(Q)\right)\leq\left(\frac{K}{\epsilon}\right)^{2dn+4n}.$

It follows from [53, 47], that there exists a universal constant
$K^{\prime}>0$ such that for all $t>0$, it holds that

$\displaystyle\Pr\left(\sqrt{M}W_{1}>t\right)$
$\displaystyle\leq\left(\frac{K^{\prime}t}{\sqrt{2dn+4n}}\right)^{2dn+4n}e^{-2t^{2}}.$

However, note that $|W_{1}|\leq 1/4$, therefore, for $t>\sqrt{M}/4$, it holds
that $\Pr\left(\sqrt{M}W_{1}>t\right)=0$. Therefore, it holds that

$\displaystyle\Pr\left(W_{1}>t\right)$
$\displaystyle\leq\left(\frac{K^{\prime}M}{4dn}\right)^{dn}e^{-2Mt^{2}}.$

The same logic applied to $W_{2}$ gives that there exists a universal constant
$K^{\prime\prime}>0$ such that for all $t>0$, it holds that

$\displaystyle\Pr\left(W_{2}>t\right)$
$\displaystyle\leq\left(\frac{K^{\prime\prime}M}{dn}\right)^{dn}e^{-2Mt^{2}}.$

Therefore, there exists universal constants $K,K^{\prime}>0$ such that for all
$t>0$, it holds that

$\displaystyle\Pr\left(Z>t\right)$
$\displaystyle\leq\left(\frac{KM}{dn}\right)^{dn}e^{-K^{\prime}Mt^{2}}.$

Now, to prove the sample complexity bound, we want to find $M$ such that

$\left(\frac{KM}{dn}\right)^{dn}e^{-K^{\prime}Mt^{2}}\leq\gamma,$

which is equivalent to the inequality

$-dn\log
M+K^{\prime}Mt^{2}\geq\log(1/\gamma)+dn\log\left(\frac{K}{dn}\right).$ (B.3)

First, we show that $dn\log M\leq K^{\prime}Mt^{2}/2.$ Note that the function
$h(M)=K^{\prime}Mt^{2}/2-dn\log M$ satisfies the conditions of Lemma 4.1.
Applying Lemma 4.1 yields that $h(M)\geq 0$ for

$M\geq 2\frac{2dn}{K^{\prime}t^{2}}\log\left(\frac{2}{K^{\prime}t^{2}}\vee
e\right)\gtrsim\frac{dn}{t^{2}}\log\left(\frac{1}{t}\vee e\right).$ (B.4)

When (B.4) is satisfied, we have that (B.3) is satisfied for

$M\geq
2\frac{\log(1/\gamma)+dn\log\left(\frac{K}{dn}\right)}{K^{\prime}t^{2}}.$
(B.5)

Thus, for all $t>0$ and all $0<\gamma<1$, there exists a universal constant
$c_{1}>0$ such that

$\sup_{x}\left|\widehat{\operatorname{IDD}}(x,\hat{\mu}_{n},s)-\operatorname{IDD}(x,\hat{\mu}_{n},s)\right|\leq
t,$

with probability $1-\gamma$, provided that

$M\geq c_{1}\frac{\log(1/\gamma)\vee dn\log\left(\frac{1}{t}\vee
e\right)}{t^{2}}.\qed$

We prove Theorem 5.5 with a series of Lemmas.

######  Lemma B.1.

Condition 1 holds for each of the depth functions defined in Section 5.

###### Proof.

Recall that all of the depth functions satisfy property (4) given in
Definition 5.1. Property (4) implies that there exists a compact set $E$ such
that $\sup_{x\in\mathbb{R}^{d}}{\rm D}(x,\mu)=\sup_{x\in E}{\rm D}(x,\mu)$. It
follows from boundedness of ${\rm D}(x,\mu)$ and compactness of $E$ that there
exists a point in $y\in E$ such that ${\rm D}(y,\mu)=\sup_{x\in E}{\rm
D}(x,\mu)=\sup_{x\in\mathbb{R}^{d}}{\rm D}(x,\mu)$. ∎

######  Lemma B.2.

Suppose that $\pi$ is absolutely continuous and that for all
$u\in\mathbb{S}^{d-1}$, the measure $\mu_{u}$ is absolutely continuous with
density $f_{u}$ and $\sup_{\left\lVert u\right\rVert=1}\left\lVert
f_{u}\right\rVert_{\infty}=L<\infty$. Then there exists a universal constant
$C>0$ such that for all $s\in(0,\infty]$, halfspace, simplicial, integrated
rank-weighted and smoothed integrated dual depth satisfy Condition 2 with
$\omega(r)=C\cdot L\cdot r$ .

###### Proof.

We prove the result for each depth in turn.

Halfspace depth: Consider two points $x,y\in\mathbb{R}^{d}$. By assumption,
$F(\cdot,u,\mu)$ is $L$-Lipschitz function a.e. . It follows that

$\displaystyle|\operatorname{HD}(x,\mu)-\operatorname{HD}(y;\mu)|$
$\displaystyle=|\inf_{u}F(x,u,\mu)-\inf_{u}F(y,u,\mu)|$
$\displaystyle\leq\sup_{u}|F(x,u,\mu)-F(y,u,\mu)|$ $\displaystyle\leq
L\cdot\left\lVert x-y\right\rVert\ a.e.\ .$

Integrated rank-weighted depth: For integrated rank-weighted depth, note that
absolute continuity of $\mu_{u}$ implies that $F(x,u,\mu)=F(x-,u,\mu)$. With
this in mind, for any two points $x,y\in\mathbb{R}^{d}$ the reverse triangle
inequality yields that

$\displaystyle|\operatorname{IRW}(x,\mu)-\operatorname{IRW}(y,\mu)|$
$\displaystyle\leq\int_{\mathbb{S}^{d-1}}2|F(x,u,\mu)-F(y,u,\mu)|d\nu(u)\leq
2L\cdot\left\lVert x-y\right\rVert\ a.e.\ .$

Integrated dual depth: For any $h:\rightarrow[0,1]$,
$h^{\prime}:S\rightarrow[0,1]$, for any $x\in S$ it holds that

$\displaystyle|h(x)(1-h(x))-h^{\prime}(x)(1-h^{\prime}(x))|$
$\displaystyle\leq 3|h(x)-h^{\prime}(x)|.$ (B.6)

Using this inequality,

$\displaystyle|\operatorname{IDD}(x,\mu,s)-\operatorname{IDD}(y,\mu,s)|$
$\displaystyle\leq
3\sup_{u}\left|\mathbb{E}_{\mu}\sigma(s(x-X)^{\top}u)-\mathbb{E}_{\mu}\sigma(s(y-X)^{\top}u)\right|.$
(B.7)

It remains to bound
$\left|\mathbb{E}_{\mu}\sigma(s(x-X)^{\top}u)-\mathbb{E}_{\mu}\sigma(s(y-X)^{\top}u)\right|$.
To this end, first assume that $s\leq\infty$ and let $w,z\in\mathbb{R}$. Using
the fact that $\sigma$ is a $1/4$-Lipschitz function, it holds that

$\displaystyle\left|\mathbb{E}_{\mu_{u}}\sigma(s(w-X))-\mathbb{E}_{\mu_{u}}\sigma(s(z-X))\right|$
$\displaystyle=\left|\int\sigma(s(w-t))-\sigma(s(z-t))f_{u}(t)dt\right|$
$\displaystyle=\left|\frac{1}{s}\int\sigma(v)-\sigma(sz-
sw+v)f_{u}(-v/s-w)dv\right|$
$\displaystyle\leq|z-w|/4\int\left|f_{u}(-v/s-w)\right|dt$
$\displaystyle\leq|z-w|\left\lVert f_{u}\right\rVert/4,$

where in the second line we use the substitution $v=s(w-t)$. The preceding
inequality and (B.7) imply that

$|\operatorname{IDD}(x,\mu,s)-\operatorname{IDD}(y,\mu,s)|\leq
3\sup_{u}\left|\mathbb{E}_{\mu}\sigma(s(x-X)^{\top}u)-\mathbb{E}_{\mu}\sigma(s(y-X)^{\top}u)\right|\leq\frac{3}{4}L\left\lVert
x-y\right\rVert.$

Now assume that $s=\infty$. It follows from absolute continuity of $\mu_{u}$
and (B.7) that

$\displaystyle|\operatorname{IDD}(x,\mu)-\operatorname{IDD}(y,\mu)|\leq
3\sup_{u}\left|F(x,u,\mu)-F(y,u,\mu)\right|\leq 3L\left\lVert x-y\right\rVert\
a.e.$

Simplicial depth: For simplicial depth, we must show that
$\Pr(x\in\Delta(X_{1},\ldots,X_{d+1})$ is Lipschitz continuous. It is easy to
begin with two dimensions. Consider
$\Pr(x\in\Delta(X_{1},X_{2},X_{3}))-\Pr(y\in\Delta(X_{1},X_{2},X_{3}))$, as
per [37], we need to show that $\Pr(\overline{X_{1}X_{2}}\text{ intersects
}\overline{xy})\leq L\cdot\left\lVert x-y\right\rVert$. In order for this
event to occur, we must have that $X_{1}$ is above $\overline{xy}$ and $X_{2}$
is below $\overline{xy}$, but both are projected onto the line segment
$\overline{xy}$ when projected onto the line running through $\overline{xy}$.
Affine invariance of simplicial depth implies we can assume, without loss of
generality, that $x$ and $y$ lie on the axis of the first coordinate. Let
$x_{1}$ and $y_{1}$ be the first coordinates of $x$ and $y$. Suppose that
$X_{11}$ is the first coordinate of $X_{1}$. It then follows from a.e.
Lipschitz continuity of $F(x,u,\mu)$ that

$\Pr(\overline{X_{1}X_{2}}\text{ intersects
}\overline{xy})\leq\Pr(x_{1}<X_{11}<y_{1})\leq L\cdot|x_{1}-y_{1}|\leq
L\left\lVert x-y\right\rVert\ a.e.\ .$

In dimensions greater than two, a similar line of reasoning can be used. We
can again assume, without loss of generality, that $x$ and $y$ lie on the axis
of the first coordinate. It holds that

$\Pr(x\in\Delta(X_{1},X_{2},X_{3}))-\Pr(y\in\Delta(X_{1},X_{2},X_{3}))\leq\binom{d+1}{d}\Pr(A_{d}),$

where $A_{d}$ is the event that the $d-1$-dimensional face of the random
simplex, formed by $d$ points randomly drawn from $F$, intersects the line
segment $\overline{xy}$. It is easy to see that

$\displaystyle\Pr(A_{d})\leq\Pr(x_{1}<X_{11}<y_{1})\leq\left\lVert
f_{u}\right\rVert_{\infty}|x_{1}-y_{1}|\leq L\cdot\left\lVert x-y\right\rVert\
a.e.\ .$ ∎

######  Lemma B.3.

Suppose that $\mu$ has a bounded density and that
$\sup_{y}\mathbb{E}\left\lVert y-X\right\rVert^{-1}=L^{\prime}\leq\infty$.
Then the modified spatial depth satisfies Condition 2 with
$\omega(r)=2\sqrt{d}L^{\prime}\cdot r$ and spatial depth satisfies Condition 2
with $\omega(r)=2L^{\prime}\cdot r$.

###### Proof.

Taking the derivative of $\operatorname{MSD}$ and using the assumption of a
bounded density results in

$\displaystyle\frac{d\operatorname{MSD}(y,\mu)}{dy}=-2\mathbb{E}{\mu}\left(\operatorname{SR}(y-X)\right)\mathbb{E}_{\mu}\left[\frac{1_{d}}{\left\lVert
y-X\right\rVert}-\frac{(y-X)*(y-X)^{\top}1_{d}}{\left\lVert
y-X\right\rVert^{3}}\right].$

Now,

$\displaystyle||\frac{d\operatorname{MSD}(y,\mu)}{dy}||\leq
2\sqrt{d}\sup_{y}\mathbb{E}\left\lVert
y-X\right\rVert^{-1}=2\sqrt{d}L^{\prime}.$

Thus, the map $y\mapsto\operatorname{MSD}(y,\mu)$ is
$2\sqrt{d}L^{\prime}$-Lipschitz.

Define the spatial rank function
$h(y,\mu)=\mathbb{E}{\mu}\left(\operatorname{SR}(y-X)\right).$ Proposition 4.1
of [33] says that if $\mu$ has a bounded density, then the map $y\mapsto
h(y,\mu)$ is continuously differentiable in $\mathbb{R}^{d}$ with derivative

$\displaystyle\frac{dh}{dy}=\int_{\\{x\neq y\\}}\frac{1}{\left\lVert
y-x\right\rVert}\left[I_{d}-\frac{(y-x)(y-x)^{\top}}{\left\lVert
y-x\right\rVert^{2}}\right]d\mu(x).$

Now,

$\displaystyle||\frac{dh}{dy}||\leq 2\sup_{y}\mathbb{E}\left\lVert
y-X\right\rVert^{-1}=2L^{\prime},$

where $\left\lVert\cdot\right\rVert$ denotes the operator norm. Thus, the map
$y\mapsto h(y,\mu)$ is $2L^{\prime}$-Lipschitz, which implies that the map
$y\mapsto\operatorname{SD}(y,\mu)$ is also $2L^{\prime}$-Lipschitz. ∎

######  Lemma B.4.

Condition 3 holds for each of the depth functions defined in Section 5.

###### Proof.

We prove the result for each depth in turn.

Halfspace depth: Let

$\mathscr{F}=\left\\{\mathbbm{1}\left\\{X^{\top}u\leq y\right\\}\colon\
u\in\mathbb{S}^{d-1},\ y\in\mathbb{R}\right\\}$

and recall that the set of subgraphs of $\mathscr{F}$ is the set of closed
halfspaces in $\mathbb{R}^{d}$. Furthermore, it holds that

$\displaystyle\sup_{x}|\operatorname{HD}(x,\mu_{1})-\operatorname{HD}(x,\mu_{2})|$
$\displaystyle\leq\sup_{g\in\mathscr{F}}|\mathbb{E}_{\mu_{1}}g(X)-\mathbb{E}_{\mu_{2}}g(X)|.$

Thus, it follows $\operatorname{HD}$ is $(1,\mathscr{F})$-regular with
$\operatorname{VC}(\mathscr{F})=d+2$.

Integrated rank-weighted-depth: First observe that

$\displaystyle\sup_{x}|\operatorname{IRW}(x,\mu_{1})-\operatorname{IRW}(x,\mu_{2})|\leq
4\sup_{u,x}\left|F(x,u,\mu_{1})-F(x,u,\mu_{2})\right|\vee\left|F(x-,u,\mu_{1})-F(x-,u,\mu_{2})\right|.$

Define

$\displaystyle\mathscr{G}$ $\displaystyle=\left\\{g\colon
g(X)=\mathbbm{1}\left\\{X^{\top}u<y\right\\},\ u\in\mathbb{S}^{d-1},\
y\in\mathbb{R}\right\\}.$

We see that the integrated rank-weighted depth function is
$(4,\mathscr{G}\vee\mathscr{F})$-regular. Furthermore, since the subgraphs of
$\mathscr{G}$ are contained in those of $\mathscr{F}$, we have that
$\operatorname{VC}(\mathscr{G}\vee\mathscr{F})=d+2$.

Integrated dual depth: If $s=\infty$ then it follows immediately from (B.6)
and the analysis of halfspace depth that the integrated dual depth is
$(3,\mathscr{F})$-regular with $\operatorname{VC}(\mathscr{F})=d+2$. Suppose
that $s<\infty$. It follows from (B.6) that

$\displaystyle\sup_{x}|\operatorname{IDD}(x,\mu_{2})-\operatorname{IDD}(x,\mu_{1})|\leq
3\sup_{y\in\mathbb{R},u\in\mathbb{S}^{d-1}}|\mathbb{E}_{\mu_{1}}\sigma(s(x-X)^{\top}u)-\mathbb{E}_{\mu_{2}}\sigma(s(x-X)^{\top}u)|.$

We have that

$\displaystyle\sup_{y\in\mathbb{R},u\in\mathbb{S}^{d-1}}|\mathbb{E}_{\mu_{1}}\sigma(s(x-X)^{\top}u)-\mathbb{E}_{\mu_{2}}\sigma(s(x-X)^{\top}u)|\leq\sup_{g\in\mathscr{F}^{\prime}}|\mathbb{E}_{\mu_{1}}g(X)-\mathbb{E}_{\mu_{2}}g(X)|,$

where

$\displaystyle\mathscr{F}^{\prime}$
$\displaystyle=\left\\{\sigma(AX_{i}+b)\colon
A\in\mathbb{R}^{d},b\in\mathbb{R}\right\\}.$

The class of functions $\mathscr{F}^{\prime}$ is a constructed from a monotone
function applied to a finite-dimensional vector space of measurable functions.
It follows from Lemma 7.14 and Lemma 7.17 of Sen [47] that
$\operatorname{VC}(\mathscr{F}^{\prime})=d+2$. Therefore, the smoothed
integrated dual depth is $(3,\mathscr{F}^{\prime})$-regular with
$\operatorname{VC}(\mathscr{F}^{\prime})=d+2$.

Simplicial Depth: Dümbgen [24] gives that

$\sup_{x}|\operatorname{SMD}(x,\mu_{1})-\operatorname{SMD}(x,\mu_{2})|\leq(d+1)\sup_{A\in\mathscr{A}}|\mu_{1}(A)-\mu_{2}(A)|,$

where $\mathscr{A}$ is the set of intersections of $d$ open half-spaces in
$\mathbb{R}^{d}$. Define the set of Boolean functions
$\mathscr{A}^{\prime}=\\{g(x)=\mathbbm{1}\left\\{x\in A\right\\}\colon
A\in\mathscr{A}\\}$. Thus, simplicial depth is
$(d+1,\mathscr{A}^{\prime})$-regular with
$\operatorname{VC}(\mathscr{A}^{\prime})=O(d^{2}\log d)$.

Spatial Depth: Applying the reverse triangle inequality yields

$\displaystyle\sup_{x}\left|\
\left\lVert\mathbb{E}_{\mu_{1}}\frac{x-X}{\left\lVert
x-X\right\rVert}\right\rVert-\left\lVert\mathbb{E}_{\mu_{2}}\frac{x-X}{\left\lVert
x-X\right\rVert}\right\rVert\ \right|$
$\displaystyle\leq\sup_{x}\left\lVert\mathbb{E}_{\mu_{1}}\frac{x-X}{\left\lVert
x-X\right\rVert}-\mathbb{E}_{\mu_{2}}\frac{x-X}{\left\lVert
x-X\right\rVert}\right\rVert$
$\displaystyle\leq\sup_{x}\sum_{j=1}^{d}\left|\mathbb{E}_{\mu_{1}}\frac{x_{j}-X_{j}}{\left\lVert
x-X\right\rVert}-\mathbb{E}_{\mu_{2}}\frac{x_{j}-X_{j}}{\left\lVert
x-X\right\rVert}\right|$ $\displaystyle\leq d\sup_{x,1\leq j\leq
d}\left|\mathbb{E}_{\mu_{1}}\frac{x_{j}-X_{j}}{\left\lVert
x-X\right\rVert}-\mathbb{E}_{\mu_{2}}\frac{x_{j}-X_{j}}{\left\lVert
x-X\right\rVert}\right|.$

It remains to compute the VC-dimension of

$\mathscr{G}=\left\\{g(X)=\frac{x_{j}-X_{j}}{\left\lVert
x-X\right\rVert}\colon x\in\mathbb{R}^{d},\ j\in[d]\right\\}.$

Now, let $E$ be the set of standard basis vectors for $\mathbb{R}^{d}$. We can
then write

$\mathscr{G}=\left\\{g(X)=\frac{e^{\top}(x-X)}{\left\lVert
x-X\right\rVert}\colon x\in\mathbb{R}^{d},\ e\in E\right\\}.$

It is now easy to see that

$\mathscr{G}\subset\left\\{g(X)=y^{\top}(x-X)\colon x\in\mathbb{R}^{d},\
y\in\mathbb{R}^{d}\ j\in[d]\right\\}.$

It follows that $\operatorname{VC}(\mathscr{G})\leq O(d)$ and that spatial
depth is $(d,\mathscr{G})$ regular.

Modified Spatial Depth: We may write

$\displaystyle\sup_{x}|\operatorname{SD}(X,\mu_{1})-\operatorname{SD}(X,\mu_{2})|$
$\displaystyle=\sup_{x}\left|\
\left\lVert\mathbb{E}{\mu_{1}}\left(\frac{x-X}{\left\lVert
x-X\right\rVert}\right)\right\rVert^{2}-\left\lVert\mathbb{E}{\mu_{2}}\left(\frac{x-X}{\left\lVert
x-X\right\rVert}\right)\right\rVert^{2}\ \right|$
$\displaystyle=\sup_{x}\left|\
\sup_{u}\left[\mathbb{E}{\mu_{1}}\left(\frac{x-X}{\left\lVert
x-X\right\rVert}\right)^{\top}u\right]-\sup_{u}\left[\mathbb{E}{\mu_{2}}\left(\frac{x-X}{\left\lVert
x-X\right\rVert}\right)^{\top}u\right]\ \right|$
$\displaystyle\leq\sup_{u}\sup_{x}\left|\
\mathbb{E}{\mu_{1}}\left(\frac{x-X}{\left\lVert
x-X\right\rVert}\right)^{\top}u-\mathbb{E}{\mu_{2}}\left(\frac{x-X}{\left\lVert
x-X\right\rVert}\right)^{\top}u\ \right|$
$\displaystyle\leq\sup_{u}\sup_{x}\left|\
\mathbb{E}{\mu_{1}}\left(\frac{x-X}{\left\lVert
x-X\right\rVert}^{\top}u\right)-\mathbb{E}{\mu_{2}}\left(\frac{x-X}{\left\lVert
x-X\right\rVert}^{\top}u\right)\ \right|.$

It remains to compute the VC-dimension of

$\mathscr{G}=\left\\{g(X)=\frac{u^{\top}(x-X)}{\left\lVert
x-X\right\rVert}\colon x\in\mathbb{R}^{d},\ u\in\mathbb{S}^{d-1}\right\\}.$

It is now easy to see that

$\mathscr{G}\subset\left\\{g(X)=y^{\top}X+b\colon b\in\mathbb{R},\
y\in\mathbb{R}^{d}\ j\in[d]\right\\}.$

It follows that $\operatorname{VC}(\mathscr{G})\leq d+2$ and that the modified
spatial depth is $(1,\mathscr{G})$ regular. ∎

###### Proof of Theorem 5.5.

The result follows from Lemmas B.1-B.4. ∎