# Differentially private projection-depth-based medians

Kelly Ramsay & Dylan Spicker

###### Abstract

We develop $(\epsilon,\delta)$-differentially private projection-depth-based
medians using the propose-test-release (PTR) and exponential mechanisms. Under
general conditions on the input parameters and the population measure, (e.g.
we do not assume any moment bounds), we quantify the probability the test in
PTR fails, as well as the cost of privacy via finite sample deviation bounds.
We demonstrate our main result on the canonical projection-depth-based median.
In the Gaussian setting, we show that the resulting deviation bound matches
the known lower bound for private Gaussian mean estimation, up to a polynomial
function of the condition number of the covariance matrix. In the Cauchy
setting, we show that the “outlier error amplification” effect resulting from
the heavy tails outweighs the cost of privacy. This result is then verified
via numerical simulations. Additionally, we present results on general PTR
mechanisms and a uniform concentration result on the projected spacings of
order statistics.

##  1 Introduction

Privacy has become a central concern in data collection and analysis owing to
considerations around personal autonomy, freedom of expression, and fairness
and equality. Differential privacy has emerged as a powerful framework for
maintaining privacy in data collection and analysis. It has recently been
adopted by many high profile institutions, including the United States Census
Bureau [1]. This has spurred investigations of many classical statistical
problems through a differentially private lens. Among such problems is median
estimation.

Early literature on differentially private median estimation focuses on the
univariate setting [10, 3, 7, 24]. In the multivariate setting, several
authors have studied differentially private medians through the lens of
differentially private mean estimation. These works have mainly focused either
on the Tukey median [6, 17, 4], or variants of it [15]. In addition, as part
of a more general framework for private high-dimensional estimation, Liu et
al., 2021b [18] studied one instance of a projection-depth-based median based
on the trimmed mean and the trimmed variance. Given that their focus was mean
estimation, all of these works enforce a bound on the number of moments
possessed by the population measure. However, a classical method for assessing
the robustness of a median is to examine its behavior in the case where the
population measure possesses no moments. Recently, Ramsay et al.,  [20]
considered this problem. They studied differentially private multivariate
medians arising from depth functions, including the Tukey median, without
enforcing any moment bounds on the population measure. However, their
framework does not cover projection-depth-based medians [26, 27].

Unlike the Tukey median and those studied by Ramsay et al.,  [20], when the
location and scale measures are chosen appropriately, projection-depth-based
medians simultaneously possess affine equivariance and achieve a high
breakdown point [26, 27]. Affine equivariance is a critical property for
location estimates, as it ensures that the units of measurement do not have an
effect on the resulting estimate, see, for example, Zuo and Serfling,  [28].
In addition, the breakdown point is a staple measure of the robustness of an
estimator. It measures the fraction of points which must be corrupted to make
an estimate arbitrarily large [14]. For instance, the breakdown point of the
Tukey median degrades quickly with the dimension $(1+d)^{-1}$, whereas, in
general, the projection-depth-based medians retain a much higher breakdown
point, (e.g., $\approx 1/2-d/n$ [26]). One may also note that (when the
location and scale measures are chosen appropriately) the projection-depth-
based medians enjoy higher relative efficiency than that of the Tukey median
[26]. Motivated by these properties, our present work develops and studies
differentially private projection-depth-based medians. We consider a general
location estimation setting and do not place any moment bounds on the
population measure.

Our main tool for privatizing projection-depth-based medians is the propose-
test-release (PTR) algorithm, which was introduced by Dwork and Lei,  [10] in
the context of differentially private estimation of various robust, univariate
statistics. Our work takes inspiration from that work, as well as from the
works of Brunel and Avella-Medina,  [7] and Brown et al.,  [6]. Brunel and
Avella-Medina,  [7] used PTR to develop sub-Gaussian median estimators in the
univariate setting. Additionally, Brown et al.,  [6] developed a private
Gaussian mean estimator, using a PTR algorithm based on safety and the
exponential mechanism, both of which we incorporate into our proposed
algorithm. Notably, Brown et al., ’s algorithm was also generalized by Liu et
al., 2021b [18] to be an all-purpose solution to various private, statistical
problems. Our work builds on that of Liu et al., 2021b [18], in the sense that
their mean estimator fits into the class of projection-depth-based estimators.

Our contributions are as follows: We first propose a class of
$(\epsilon,\delta)$-differentially private projection-depth-based medians.
Next, under general conditions on the population measure, we quantify both the
probability that the PTR algorithm fails to release an estimate and the cost
of privatizing the projection-depth-based medians (see Theorems 3.1, and 3.2,
respectively). To measure the cost of privacy, we provide finite sample bounds
on the distance between a private projection-depth-based median and the
corresponding population value, which hold with high probability. We then
demonstrate our methods for the canonical projection-depth-based median. In
particular, we show that Theorems 3.1 and 3.2 apply provided the “projected
densities” are bounded below in an interval containing a range of inner
quantiles (Condition 4). As a first example, we show that in the Gaussian
setting, our deviation bound matches the optimal lower bound for sub-Gaussian
mean estimation given by [16, 8], up to a polynomial function of the condition
number of the covariance matrix (see Example 3.1). We then show that in the
Cauchy setting, the increase in error resulting from contamination or heavy
tails, which we call the “outlier error amplification” is larger than the cost
of privacy (see Example 3.2). We then confirm this phenomenon with numerical
studies (see Section 4). Lastly, we provide some results for analysis of
general PTR mechanisms (see Section 5), as well as a uniform concentration
result on the projected spacings of order statistics (see Lemma C.2), which
may be of general interest.

##  2 Preliminaries

###  2.1 Differential privacy

We first review necessary concepts from differential privacy. For a textbook
introduction to differential privacy, see Dwork and Roth,  [11]. A _dataset_
of size $n\times d$ is a collection of $n$ points in $\mathbb{R}^{d}$,
$\mathbb{X}_{n}=\\{X_{i}\\}_{i=1}^{n}$, possibly with repetitions. Let
$\mathbf{D}_{n\times d}$ be the set of all datasets of size $n\times d$. For
datasets $\mathbb{X}_{n}$ and $\mathbb{Y}_{n}$, let
$\mathbb{X}_{n}\triangle\mathbb{Y}_{n}$ represent the dataset containing all
rows in $\mathbb{X}_{n}$ which are not contained in $\mathbb{Y}_{n}$. Define
$\mathbf{A}(\mathbb{X}_{n},m)=\left\\{\mathbb{Y}_{n}\in\mathbf{D}_{n\times
d}\colon|\mathbb{X}_{n}\triangle\mathbb{Y}_{n}|=m\right\\}$, the set of
datasets of size $n\times d$ which differ from $\mathbb{X}_{n}$ in exactly $m$
rows. Define the empirical measure of $\mathbb{X}_{n}$,
${\hat{\nu}}_{\mathbb{X}_{n}}$, as that which assigns $1/n$ probability to
each row in $\mathbb{X}_{n}$. For a dataset with empirical measure
${\hat{\nu}}_{\mathbb{X}_{n}}$ define

$\widetilde{\mathcal{M}}_{1}({\hat{\nu}}_{\mathbb{X}_{n}},m)=\\{\tilde{\nu}\in\mathcal{M}_{1}(\mathbb{R}^{d})\colon\tilde{\nu}={\hat{\nu}}_{\mathbb{Y}_{n}}\text{
for some }\mathbb{Y}_{n}\in\mathbf{A}(\mathbb{X}_{n},m)\\},$

where $\mathcal{M}_{1}(\mathbb{R}^{d})$ is the set of measures on
$\mathscr{B}(\mathbb{R}^{d})$, and $\mathscr{B}(S)$ denotes the Borel sets of
$S$.

Suppose that we observe a dataset ${\mathbb{X}}_{n}$ comprised of $n$ i.i.d.
samples from a measure $\nu\in\mathcal{M}_{1}(\mathbb{R}^{d})$, and wish to
estimate a parameter $\theta\in\Theta$. One way to do this is via a
_mechanism_. Formally, a mechanism, $P_{\hat{\nu}}$, maps an empirical measure
$\hat{\nu}$ to $\mathcal{M}_{1}(\Theta)$. The estimator $\tilde{\theta}$ is
then taken to be a draw from $P_{\hat{\nu}}$. When the corresponding measure
is clear from context, we will suppress dependence on it in notation, denoting
$P_{\hat{\nu}}$ as $P$. To produce a differentially private statistic,
$P_{\hat{\nu}}$ should satisfy the following privacy guarantee.

######  Definition 2.1.

A mechanism $P$ is $(\epsilon,\delta)$-differentially private if for any
dataset $\mathbb{X}_{n}$, any
$\tilde{\nu}\in\widetilde{\mathcal{M}}_{1}(\nu_{\mathbb{X}_{n}},1)$, and any
measurable set $B\in\mathscr{B}(\Theta)$, it holds that

$P_{\hat{\nu}_{\mathbb{X}_{n}}}(B)\leq e^{\epsilon}P_{\tilde{\nu}}(B)+\delta.$
(2.1)

One particular class of differentially private mechanisms are those based on
_propose-test-release_ (PTR) algorithms [10]. PTR algorithms generally rely on
the notion of _local sensitivity_. Colloquially, a statistic, $T$, is locally
sensitive with respect to a dataset $\mathbb{X}_{n}$ if
$\sup_{\mathbb{Y}_{n}\in\mathbf{A}(\mathbb{X}_{n},m)}|T(\mathbb{X}_{n})-T(\mathbb{Y}_{n})|$
is large for some small $m\in\mathbb{N}$. PTR algorithms are characterized by
a three-step procedure. First, you propose a statistic. Second, you test if
the proposed statistic is locally sensitive. Finally, if the proposed
statistic is not locally sensitive, you release a noisy version of the
statistic; if not, nothing is released. Even in the event that nothing is
released, the PTR mechanism uses up the $(\epsilon,\delta)$ privacy budget. To
formalize PTR, take $\widehat{\mathcal{M}}_{1}(n,d)$ to be the set of
empirical measures constructed from datasets of size $n\times d$,
$\\{\nu_{\mathbb{X}_{n}}\colon\ \mathbb{X}_{n}\in\mathbf{D}_{n\times d}\\}$.
Let $Ber(p)$ denote the Bernoulli measure with parameter $0\leq p\leq 1$.

######  Definition 2.2.

A test mechanism is any mechanism, $Q$, such that for all
$\hat{\nu}\in\widehat{\mathcal{M}}_{1}(n,d)$,
$Q_{\hat{\nu}}=Ber(\lambda(\hat{\nu}))$ for some $0\leq\lambda(\hat{\nu})\leq
1$.

Every test mechanism is characterized by its associated $\lambda$. We will
refer to a test mechanism by its associated $\lambda$ function.

######  Definition 2.3.

Given a mechanism $Q$ mapping to $\mathcal{M}_{1}(\Theta)$ and a test
mechanism $\lambda$, the PTR mechanism based on $(Q,\lambda)$ is given by the
map

$P_{\hat{\nu}}\colon(B)\mapsto\lambda(\hat{\nu})Q_{\hat{\nu}}(B\backslash\\{\perp\\})+\left[1-\lambda(\hat{\nu})\right]\mathbbm{1}\left\\{\perp\in
B\right\\},$

where $B\in\mathscr{B}(\Theta\cup\\{\perp\\})$ and
$\hat{\nu}\in\widehat{\mathcal{M}}_{1}(n,d)$.

The probability of any event under the PTR mechanism will be the probability
that the test is passed multiplied by the probability of the event under the
original mechanism, plus the probability of the test failing if $\perp$ is an
element of the event. We now introduce the notions of safety, safety margin,
and the exponential mechanism, which will be used to define the private
projection-depth-based median.

_Safety_ , introduced by Brown et al.,  [6] for Gaussian mean estimation,
represents a localized version of the $(\epsilon,\delta)$-differential privacy
guarantee. We present a generalized definition.

######  Definition 2.4.

Given $\epsilon,\delta>0$, the pair $(Q,\hat{\nu})$ is
$(\epsilon,\delta)$-safe if, for all
$\tilde{\nu}\in\widetilde{\mathcal{M}}(\hat{\nu})$ and $Q$-measurable sets
$B$, it holds that

$Q_{\hat{\nu}}(B;\epsilon,\delta)\leq
e^{\epsilon}Q_{\tilde{\nu}}(B;\epsilon,\delta)+\delta\qquad\text{and}\qquad
Q_{\tilde{\nu}}(B;\epsilon,\delta)\leq
e^{\epsilon}Q_{\hat{\nu}}(B;\epsilon,\delta)+\delta.$

The $(\epsilon,\delta)$-safe set of $Q$ is

$\mathbf{S}(Q,\epsilon,\delta)=\\{\hat{\nu}\in\widehat{M}_{1}(n,d)\colon\
(Q,\hat{\nu})\text{ is }(\epsilon,\delta)\text{-safe}\\}.$

We include $\epsilon$ and $\delta$ in the notation for the mechanism $Q$ to
emphasize that $Q$ typically depends on $\epsilon$ and $\delta$. Our proposed
algorithm’s test mechanism relies on the _safety margin_.

######  Definition 2.5.

Given $\epsilon,\delta>0$ and a mechanism $Q$, the safety margin of an
empirical measure $\hat{\nu}$ with respect to $Q$, is

$\operatorname{SM}(\hat{\nu},Q;\epsilon,\delta)=\inf\\{m\in\mathbb{Z}^{+}\colon\
\exists\tilde{\nu}\in\tilde{\mathcal{M}}(\hat{\nu},m)\ s.t.\
\tilde{\nu}\notin\mathbf{S}(Q,\epsilon,\delta)\\}.$

When $\epsilon$ and $\delta$ are clear from the context, we omit them,
denoting the safety margin as $\operatorname{SM}(\hat{\nu},Q).$ Observe that
if $\operatorname{SM}(\hat{\nu},Q)>0$, then $(Q,\hat{\nu})$ is safe.

Our proposed algorithm applies a test mechanism based on the safety margin,
and if the test is passed, releases a draw from the _exponential mechanism_.
For a cost function $\phi(\cdot;\hat{\nu})$, let
$A_{\tau,\hat{\nu}}=\\{\phi(x,\hat{\nu})\leq\tau\\}$. The exponential
mechanism $\operatorname{EM}_{\hat{\nu},\phi}(\cdot;\tau,\eta,\epsilon)$ is
the measure whose Radon–Nykodym density satisfies

$d\operatorname{EM}_{\hat{\nu},\phi}(\cdot;\tau,\eta,\epsilon)\propto\mathbbm{1}\left\\{x\in
A_{\tau,\hat{\nu}}\right\\}\exp(-\phi(x,{\hat{\nu})\epsilon/4\eta})dx.$ (2.2)

We omit the parameters $(\tau,\eta,\epsilon)$ in the notation when they are
clear from the context.

###  2.2 Outlyingness and projection-depth-based medians

We propose using the _projected outlyingness_ [9, 28, 26] for the cost
function of the exponential mechanism. For a measure
$\nu\in\mathcal{M}_{1}(\mathbb{R}^{d})$ and $u$ from the unit $(d-1)$-sphere,
$\mathbb{S}^{d-1}$, let $\nu_{u}$ be the law of $X^{\top}u$ if $X\sim\nu$.

######  Definition 2.6.

Given a translation and scale equivariant estimator $\mu$ and a translation
invariant and scale equivariant estimator $\sigma$, the projected outlyingness
at $x\in\mathbb{R}^{d}$ with respect to $\nu$ is

$O(x,\nu)=\sup_{u\in\mathbb{S}^{d-1}}O_{u}(x,\nu_{u})=\sup_{u\in\mathbb{S}^{d-1}}\frac{\left|x^{\top}u-\mu(\nu_{u})\right|}{\sigma(\nu_{u})}.$
(2.3)

For brevity, we will refer to the projected outlyingness as simply the
outlyingness, denote $\mu(\nu_{u})$ as $\mu_{u}$, $\sigma(\nu_{u})$ as
$\sigma_{u}$, $\mu(\hat{\nu}_{u})$ as $\hat{\mu}_{u}$, and
$\sigma(\hat{\nu}_{u})$ as $\hat{\sigma}_{u}$. The sample version of the
outlyingness function is given by $O(x,\hat{\nu})$. The canonical choices of
$\mu$ and $\sigma$ are the median and the median absolute deviation,
respectively. Alternatively, choosing $\mu$ and $\sigma$ to be the trimmed
mean and trimmed variance recovers the objective function used in the PTR
mechanism developed by Liu et al., 2021b [18] for differentially private mean
estimation. The minimizer of the outlyingness function is a _projection-depth-
based median_ [26], given by $\theta=\int_{\operatorname*{{\rm argmin}}O}xdP,$
where $P$ is uniform on $\operatorname*{{\rm argmin}}O$.

The projection-depth-based medians enjoy several nice properties: local and
global robustness, affine equivariance, strong $\sqrt{n}$-consistency and a
relatively simple limiting distribution [26, 27]. Notably, to the best of our
knowledge, among the competing affine equivariant medians, when the location
and scale measures are chosen appropriately, e.g. the median and median
absolute deviation, the projection-depth-based medians have the highest
breakdown point [26]. For instance, the breakdown point of the Tukey median
degrades quickly with the dimension $(1+d)^{-1}$, whereas, in general, the
projection-depth-based medians retain a much higher breakdown point, e.g.,
$\lfloor n/2-d+2\rfloor/n$ [26]. One may also note that the projection-depth-
based medians have been shown to have higher asymptotic efficiency, relative
to competitors [26]. For more information on projection-depth-based medians,
we refer the reader to [26, 27].

##  3 Main results

###  3.1 A private projection-depth-based median

In this section, we study a propose-test-release mechanism which outputs a
private version of $\theta$, the projection-depth-based median. For common
choices of $\mu,\ \sigma$, such as the median and median absolute deviation,
the global sensitivity of the outlyingness function is not finite. Therefore,
we cannot directly apply the exponential mechanism to develop a differentially
private projection-depth-based median estimator. However, the median and
median absolute deviation are robust statistics, in the sense that they are
not corrupted under small levels of contamination. Thus, the outlyingness
function should often be locally insensitive, making it natural to use in a
PTR mechanism.

We now introduce the private projection-depth-based median. Let $W$ be a
standard Laplace random variable. Take

$\lambda_{1}(\hat{\nu},\epsilon,\delta)=\Pr\left(\operatorname{SM}(\hat{\nu},\operatorname{EM}_{\hat{\nu},O})+\frac{2}{\epsilon}W>\frac{2\log(1/2\delta)}{\epsilon}\Bigg{|}\
\hat{\nu}\right),$ (3.1)

to be the test mechanism.

######  Definition 3.1.

Given parameters $\epsilon,\delta,\eta,\tau>0$, the private projection-depth-
based median is $\tilde{\theta}\sim P_{\hat{\nu}}$, where
$P_{\hat{\nu}}=P_{\hat{\nu}}(;\tau,\eta,\epsilon)$ is the PTR mechanism based
on $(\operatorname{EM}_{\hat{\nu},O},\lambda_{1})$.

The private projection-depth-based median is
$(\epsilon,\delta)$-differentially private (Theorem 5.1). We note that the
algorithms of Brown et al.,  [6] and Liu et al., 2021b [18] are PTR algorithms
based on exponential mechanisms and $\lambda_{1}$, using a different cost
function. The performance of a PTR mechanism is naturally characterized by
both the probability that the test is passed ($\mathbb{E}\lambda_{1}$) and the
accuracy of the approximation of $\theta$ by $\tilde{\theta}$. With these two
quantities, we characterize both the likelihood that the mechanism releases a
useful statistic, and how useful that statistic is likely to be.

To analyze these quantities, we first introduce the _projected sensitivity_
and the _maximal absolute projected deviation_ of an arbitrary statistic, $T$.
Define

$\tilde{S}_{n,k}(T)=\sup_{\begin{subarray}{c}\tilde{\nu}\in\widetilde{\mathcal{M}}_{1}(\hat{\nu},k)\\\
u\in\mathbb{S}^{d-1}\end{subarray}}|T(\hat{\nu}_{u})-T(\tilde{\nu}_{u})|\qquad\text{and}\qquad
S_{n}(T)=\sup_{u\in\mathbb{S}^{d-1}}|T(\hat{\nu}_{u})-T(\nu_{u})|.$

The first quantity ($\tilde{S}_{n,k}(T)$), which we call the projected
sensitivity, is an extension of sensitivity. It is the maximum change in $T$
when $k$ observations are set to arbitrary values, over all directions. The
second quantity ($S_{n,k}(T)$), referred to as the maximal absolute projected
deviation of $T$, is the maximum distance between the sample value of $T$ and
the population value of $T$, over all directions. Next we introduce three
regularity conditions.

######  Condition 1.

There exists constants $a_{1,d},a_{2,d,k}>0$, and a sequence
$\kappa_{n}\longrightarrow 0$ as $n\rightarrow\infty$ such that for all
$n,d\geq 1$ and $t\geq 0$ it holds that

$\Pr\left(\tilde{S}_{n,k}(T)\geq t\right)\leq
a_{1,d}\exp\left(-a_{2,d,k}nt\right)+\kappa_{n}.$

######  Condition 2.

There exists a sequence of functions non-increasing functions
$\zeta_{n,d}\longrightarrow 0$ as $n\to\infty$ such that for all $n,d\geq 1$
and $t\geq 0$ it holds that

$\Pr\Big{(}S_{n}(T)\geq t\Big{)}\lesssim\zeta_{n,d}(t).$

######  Condition 3.

There exists constants $c_{1},c_{2},c_{3}>0$ such that, for the population
measure $\nu$,
$0<c_{1}\leq\inf_{u\in\mathbb{S}^{d-1}}\sigma_{u}\leq\sup_{u\in\mathbb{S}^{d-1}}\sigma_{u}\leq
c_{2}<\infty$ and $\sup_{u\in\mathbb{S}^{d-1}}|\theta^{\top}u-\mu_{u}|\leq
c_{3}<\infty$.

Condition 1 can be viewed as guaranteeing robustness, with high probability.
It says that the probability that one can contaminate $k$ observations in the
sample so that the statistic of interest moves by at least $t$ is small. Of
these three conditions, this first is the most difficult to check. As a
result, we provide an example verifying it in Section 3.2. We show that for
certain choices of $\mu$ and $\sigma$, Condition 1 reduces to requiring a
lower bound on the “projected densities” of $\nu$. Condition 2 requires that
$T(\hat{\nu}_{u})$ concentrates around its population value uniformly in $u$.
This can typically be shown using standard empirical process or sub-Gaussian
concentration techniques, (see for example, Lemma E.1). Condition 3 is
standard for projection-depth-based estimators [27]. Under these three
conditions, we derive a general bound on the probability that the proposed PTR
mechanism fails the test based on $\lambda_{1}$.

######  Theorem 3.1.

Suppose that Conditions 1–3 hold for $(\nu,\mu,\sigma,k=4\log(1/2\delta)+1)$.
For all $d,n\geq 1$, $\delta\leq 1/2$, $\epsilon,\eta,\tau>0$ such that
$\tau>4\eta+16c_{3}/c_{1}$ and

$\delta>\exp\left(-\frac{\epsilon\tau}{8\eta}+\frac{\epsilon}{2}+d\log\left(\frac{2c_{2}(\tau+2\eta)+4c_{3}}{c_{1}\tau/4-\eta-4c_{3}}\right)\right),$

it holds that

$\mathbb{E}\lambda_{1}(\hat{\nu},\epsilon,\delta)\gtrsim 1-\delta-
a_{1,d}\exp\left(-\frac{a_{2,d,4\log(1/2\delta)/\epsilon+1}c_{2}n(\eta\wedge
1)}{4(\tau\vee 1)}\right)-\kappa_{n}-\zeta_{n,,d}(c_{1}/4).$

The proof of Theorem 3.1 is given in Appendix B. To interpret Theorem 3.1 note
that, given robust $\mu$ and $\sigma$ in the sense of Condition 1, the
probability of failing the test in the mechanism is governed by the ratio
$a_{2,d,4\log(1/2\delta)/\epsilon+1}\eta/\tau$ and $\delta$. Next, we show
that the mechanism will be accurate with high probability. The following
theorem bounds the deviation of the private projection-depth-based median
around its population value.

######  Theorem 3.2.

Suppose Conditions 2 and 3 hold. Then, for all $\epsilon,\eta>0$, $\delta\leq
1/2$, $\gamma~{}\in~{}(3\zeta_{n,d}(c_{1}/2\wedge c_{3})\vee
3(1-\mathbb{E}\lambda_{1}(\hat{\nu},\epsilon,\delta)),1]$, $\tau\geq
20(2c_{3}/(10c_{2}-c_{1})+c_{3}/c_{1})$ and $n,d\geq 1$, with probability
$1-\gamma$, it holds that

$\lVert\tilde{\theta}-\theta\rVert\lesssim\frac{c_{2}\eta}{\epsilon}\left[\log(1/\gamma)\vee
d\log\left(\frac{2c_{2}\tau}{c_{3}}+1\right)\vee\frac{c_{3}}{c_{1}}\right]\vee\frac{c_{2}}{c_{1}}\zeta_{n,d}^{-1}(\gamma/3).$

The proof of Theorem 3.2 is given in Appendix B. Theorem 3.2 shows that,
provided $\eta$ is relatively small and $\mathbb{E}\lambda_{1}$ is large
enough, the cost of privacy for privately estimating the projection-depth-
based median is governed by $\eta(\log(1/\gamma)\vee d)/\epsilon$. Theorem 3.1
and Theorem 3.2 quantify the trade-off inherent in $\eta$: smaller $\eta$
improves accuracy at the cost of a higher probability of failing the test. In
general, one would like to show that the cost of privacy is less than the
sampling error: $c_{2}\zeta_{n,d}^{-1}(\gamma/3)/c_{1}$. We will explore this
in the next section.

###  3.2 Verifying Condition 1 and example applications

We next verify Condition 1 for the canonical choices of $\mu$ and $\sigma$,
before applying Theorem 3.1 and Theorem 3.2 for Gaussian and Cauchy population
measures. We demonstrate our methodology for the median and median absolute
deviation, using the properties of order statistics.

For $\nu\in\mathcal{M}_{1}(\mathbb{R}^{d})$, let $F_{\nu}$ be the cumulative
distribution function and $f_{\nu}$ be the Radon–Nikodym derivative of $\nu$.
If $d=1$, let $F^{-1}_{\nu}$ be the left-continuous quantile function and let
$\xi_{q,u}=F^{-1}_{\nu_{u}}(q)$. We require the following condition for the
triple $(q,\nu,k)$, with $0<q\leq 1/2$.

######  Condition 4.

The measure $\nu$ is absolutely continuous and there exists $r,M>0$ such that,
for the interval $\mathcal{I}=[\xi_{q-k/n,u}-r,\xi_{1-q+k/n,u}+r]$, we have
$\inf_{\begin{subarray}{c}x\in\mathcal{I};u\in\mathbb{S}^{d-1}\end{subarray}}f_{\nu_{u}}(x)>M$.

For a given quantile, Condition 4 requires that the density of the projected
population measure is in some interval which contains
$(\xi_{q-k/n,u},\xi_{1-q+k/n,u})$, whose width depends on $k$. For $q=1/2$,
Condition 4 is a multivariate extension of the condition required for the
univariate PTR median [7], with a modified handling of $k$. Under Condition 4
the median and median absolute deviation both satisfy Conditions 1 and 2 (see
Lemmas E.1 and E.2).

######  Theorem 3.3.

Suppose for a given $k\in[n]$, there exists $0<q^{\prime}<q<1/4$ such that
both $k<n(q-q^{\prime})/2$ and Condition 4 holds for $(q^{\prime},\nu,k)$.
Then the median and median absolute deviation satisfy Condition 1 with
$a_{1,d}=\exp({d\log 9+\log(n(1-2q^{\prime}+1/n))})$, $a_{2,d,k}=3M/8k$ and
$\kappa_{n}=\exp({-nr^{2}M^{2}+d\log(cn/d)}).$

The proof follows directly from Lemmas C.3 and C.4. Typically, we will have
$k=o(n)$, and when we do, Theorem 3.3 is readily interpretable. Specifically,
provided the (univariate) projected densities are bounded below when computed
at the inner quantiles, then the median and median absolute deviation have
small projected sensitivity with high probability. Note that we can prove an
analogue of Theorem 3.3 with the interquartile range in place of the median
absolute deviation (see Lemma C.5).

######  Remark 3.4.

Liu et al., 2021b [18] studied a projection-depth-based median taking $\mu$
and $\sigma$ to be the trimmed mean and variance, respectively. The projected
sensitivities of trimmed estimators are governed by spacings between order
statistics. The main technical argument in Theorem 3.3 is Lemma C.2, which
controls the projected spacings between central order statistics. It is
straightforward to apply these same techniques to show that Condition 1 holds
for the trimmed estimators. Furthermore, the results of Fernandez-Rico,  [13]
can be applied to verify Condition 2, giving a straightforward application of
Theorems 3.1 and 3.2.

To illustrate the methodology, we begin with a simple example, taking $\nu$ to
be Gaussian.

######  Example 3.1 (Gaussian data).

Take the population measure to be $\mathcal{N}(\theta,\Sigma)$ with
$\theta\in\mathbb{R}^{d}$ and $\Sigma$ as a positive definite symmetric
matrix. Without loss of generality, we may assume that
$\nu=\mathcal{N}(0,\Lambda)$, where $\Lambda$ is a diagonal matrix with
eigenvalues $\beta_{1}\leq\cdots\leq\beta_{d}$ and let $\omega$ be the
condition number of $\Lambda$, i.e., $\omega=\beta_{d}/\beta_{1}$.
Specifically, the bounds produced by Theorems 3.1 and 3.2 when
$\nu=\mathcal{N}(0,\Lambda)$ are equivalent to those produced by taking
$\nu=\mathcal{N}(\theta,\Sigma)$, where $\Sigma=R\Lambda R^{\top}$ for some
unitary matrix $R$. To see this, note that
$R\nu+\theta=\mathcal{N}(\theta,\Sigma)$, where $A\nu+b$ represents the law of
$AX+b$ if $X\sim\nu$. Given that the outlyingness function is invariant under
affine transformations, with $O(x,\nu)=O(Ax+b,A\nu+b)$, and using the fact
that the private median is computed using only the outlyingness function, the
simplified case loses no generality.

First, we check Conditions 2–4. Direct calculation yields that Condition 3 is
satisfied with $c_{1}\leq\beta_{1}^{1/2}$, $c_{2}\geq\beta_{d}^{1/2}$ and
$c_{3}>0$. Take $c_{3}=1$. Next, we check Condition 4 for $q=1/8$,
$k=4\log(1/2\delta)/\epsilon$, and $r=\beta_{1}^{1/2}/4$. Provided that
$\delta>e^{-n\epsilon/32}/2$, then Condition 4 holds with

$M=(2\pi\beta_{d})^{-1/2}\exp({-(\Phi^{-1}(1/8-4\log(1/2\delta)/\epsilon
n)-1/4)^{2}/2}).$

We now apply Theorem 3.3 to show that Condition 1 holds. If
$4\log(1/2\delta)/\epsilon n\longrightarrow 0$, then
$M\gtrsim\beta_{d}^{-1/2}$ for large $n$. Applying Theorem 3.3,
$a_{1,d}\lesssim\exp({d+\log n})$,
$a_{2,d,4\log(1/2\delta)/\epsilon}\gtrsim\epsilon(\beta_{d}^{1/2}\log(1/\delta))^{-1}$,
and $\kappa_{n}\lesssim\exp\left(-c^{\prime}n/\omega+d\log(cd/n)\right).$
Next, using empirical process theory, (see Lemma E.1 and Lemma E.2) Condition
2 is satisfied for the median and median absolute deviation with

$\zeta_{n,d}(t)=\exp\left(-cnt^{2}/\beta_{d}+d\log(cn/d)\right)+\exp\left(-cn/\omega+d\log(cn/d)\right),$

for some universal constant $c>0$.

We can now apply Theorems 3.1 and 3.2. Beginning with Theorem 3.1, morally,
for

$\delta\gtrsim\exp\left(-\frac{\epsilon\tau}{\eta}+\epsilon+d\log\omega\right)\vee
e^{-n\epsilon},$

there exists universal constants $c,c^{\prime}>0$ such that

$\mathbb{E}\lambda(\hat{\nu},\epsilon,\delta)\gtrsim
1-\delta-\exp\left(-c^{\prime}\frac{n\eta\epsilon}{\log(1/\delta)(\tau\vee
1)}+d+\log n\right)-\exp\left(-\frac{c^{\prime}n}{\omega}+d\log(cn/d)\right).$

Thus, in order to control the probability of failing the test, it suffices to
inspect the ratio $n\eta\epsilon/\log(1/\delta)\tau.$ Note that $O$ is a
standardized measure of outlyingness, and doesn’t depend on the scale of the
data, therefore it is natural to take $\tau$ to be a constant. Next, suppose
$\delta=O(n^{-L})$ for some large $L>0$. Taking $\eta\gtrsim(L\log n)(d\vee
L\log n)/n\epsilon$ results in
$\mathbb{E}\lambda(\hat{\nu},\epsilon,\delta)\gtrsim 1-\delta$. In the best
case, taking $L<<d$ results in the slowest scaling in the dimension, given by
$\eta\gtrsim d\log^{2}n/n\epsilon$.

Next, taking $\eta\propto d\log^{2}n/n\epsilon$, we apply Theorem 3.2, which
yields that, provided $n\geq d\omega$, for all $n^{-L}\lesssim\gamma\leq 1,$
and $d\geq 1$, with probability $1-\gamma$,

$\lVert\tilde{\theta}-\theta\rVert\lesssim\frac{d\beta_{d}^{1/2}\log^{2}n}{n\epsilon^{2}}\left[\log(1/\gamma)\vee
d\log(\beta_{d}+1)\vee\beta_{1}^{-1/2}\right]\vee\sqrt{\beta_{d}\omega\frac{\log(1/\gamma)\vee
d\log(n/d)}{n}}.$

For many reasonable values of $\gamma$, the sampling error greatly exceeds the
cost of privacy. For instance, for $\gamma\propto\delta$, gives
$||\tilde{\theta}-\theta||\approx\sqrt{\beta_{d}\omega\cdot d\log(n/d)/n}$
whenever, roughly, $n\gtrsim d^{3}\log^{4}n/\omega\epsilon^{4}$. Therefore,
whenever $n\gtrsim d^{3}\log^{4}n/\omega\epsilon^{4}$, the deviations bound
obtained from Theorem 3.2 matches the optimal deviations bound (for sub-
Gaussian mean estimation) given by Cai et al.,  [8, see Theorem 3.1], see also
[16], up to logarithmic terms and a factor of $\omega^{1/2}$. Of course, there
exists estimators that achieve smaller upper bounds for private Gaussian mean
estimation, e.g., [2, 6]. This is not surprising, given the usual robustness-
efficiency trade-off in statistical estimation.

In our next example, we quantify the cost of privacy in the heavy-tailed
setting, i.e., when no moments of $\nu$ exist. We show that even in this
difficult setting, the cost of privacy is small relative to the sampling
error. Furthermore, we observe that the “outlier error amplification”
resulting from the heavy tails, greatly outweighs the cost of privacy.

######  Example 3.2 (Cauchy data).

Consider $\nu$ to be made up of $d$ independent Cauchy marginals with scale
parameter equal to one and location parameter equal to zero. Analogous to
Example 3.1, the assumptions of the scale parameter being one and location
parameter being zero are made without loss of generality. Again, we check the
Conditions 2–4. First, direct calculation yields that Condition 3 holds with
$c_{1}=1$, $c_{2}=d^{1/2}$ and $c_{3}=1$.

Provided that $\delta\geq e^{-cn\epsilon}$ for some universal constant $c>0$,
Condition 4 holds with $M\gtrsim d^{-1/2}$. Applying Theorem 3.3, we conclude
that Condition 1 holds. Indeed, $a_{1,d}\lesssim\exp(d+\log n)$,
$a_{2,d,4\log(1/2\delta)/\epsilon}\gtrsim\epsilon(d^{1/2}\log(1/\delta))^{-1}$,
and $\kappa_{n}\lesssim\exp(-c^{\prime}n/d+d\log\left(cn/d\right))$. Next, we
use Condition 4 to show that Condition 2 holds (see Lemma E.1 and Lemma E.2)
with

$\zeta_{n,d}(t)=\exp\left(-c^{\prime}nt^{2}/d+d\log(cn/d)\right)+\exp\left(-c^{\prime}n/d^{2}+d\log(cn/d)\right),$

for universal constants $c,c^{\prime}>0$. We have now shown that all necessary
conditions for the application of Theorems 3.1 and 3.2 are satisfied. We begin
with an application of Theorem 3.1 and omit universal constants for clarity.
For $\delta\gtrsim\exp\left(-\epsilon\tau/\eta+\epsilon+d\log(d\tau)\right)$,
we have

$\displaystyle\mathbb{E}\lambda(\hat{\nu},\epsilon,\delta)$
$\displaystyle\gtrsim
1-\delta-\exp\left(-\frac{n\eta\epsilon}{d^{1/2}\log(1/\delta)\tau}+d+\log
n\right)-\exp\left(-\frac{n}{d^{2}}+d\log(n/d)\right).$

Thus, compared to the Gaussian case, the lower bound on $\delta$ is larger.
Furthermore, we require $\eta\gtrsim d^{3/2}\log^{2}n/n\epsilon$ to ensure
that $\mathbb{E}\lambda(\hat{\nu},\epsilon,\delta)\gtrsim n^{-L}$, a factor of
$d^{1/2}$ larger than in the Gaussian case. We can now apply Theorem 3.2.
Taking $\eta\propto d^{3/2}\log^{2}n/n\epsilon$, for $n^{-L}<\gamma<1$ with
probability $1-\gamma$, it holds that

$\lVert\tilde{\theta}-\theta\rVert\lesssim\frac{d^{3/2}\log^{2}n\left[\log(1/\gamma)\vee
d\log d\right]}{n\epsilon^{2}}\vee\sqrt{\frac{d^{2}\log(1/\gamma)\vee
d^{3}\log(n/d)}{n}}.$

It is immediate that the scaling in the dimension of the deviations bound is
worse than that of the Gaussian case (Example 3.1). This is expected, given
that heavy-tailed estimation is a more challenging problem. We refer to this
as “outlier error amplification”. A similar phenomenon, in the form of sample
complexity bounds, was observed by Ramsay et al.,  [20], for private medians
based on other depth functions. Lastly, observe that the cost of privacy is
still greatly outweighed by the sampling error, provided $n\gtrsim
d^{2}\log^{4}n/\epsilon^{2}$.

##  4 Numerical experiments

To complement our theoretical results, we provide a numerical demonstration of
our proposed methods. In order to compute the private projection-depth-based
median, we employ discretized Langevin dynamics (as was done by Ramsay et al.,
[20]) and compute outlyingness by (randomly) discretizing the unit sphere, see
Appendix A for the algorithm. More efficient algorithms could be constructed
by using the methods and results of Dyckerhoff et al.,  [12], but we leave
that for future work, as the current implementation’s differential privacy
guarantee may be affected by the use of Markov chain Monte Carlo (MCMC)
methods [22]. The purpose of the implementation is to numerically investigate
the cost of privatizing the projection-depth-based median and compare to some
other private measures of location, and the non-private projection-depth-based
median. Our code is available on GitHub.

We compute the private and non-private projection-depth-based median based on
the median, with the median absolute deviation as the scale estimate. We
compare the performance of the projection-depth-based medians to the private
smoothed integrated dual depth median [20], the non-private sample mean, and
the private coin-press mean of Biswas et al.,  [5]. Following Ramsay et al.,
[20], for the integrated dual depth median, we set the smoothing parameter to
10, the prior as $\mathcal{N}(0,25dI)$. For the coin-press mean, we set the
bounding ball to have a radius of $10\sqrt{d}$ and the algorithm was run for
four iterations.

Figure 1: Empirical root mean squared error (ERMSE) of the location estimates
under (left) Gaussian data and (right) contaminated Gaussian data. The cost of
privacy is eclipsed by the outlier error amplification. The non-private
estimates are all relatively close to their non-private counterparts. By
contrast, the increase in error for all estimators resulting from
contamination is apparent. The usual differences between robust and non-robust
estimators are also apparent. Notably, the projection-depth-based median is
the most robust.

Following Ramsay et al.,  [20], we simulated fifty instances of each PD
median, with $n=10,000$ over a range of dimensions from two to twenty. 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)$. We set $\epsilon=10,\ \delta=10/n$, $\tau=1$ and
$\eta=30(\log n)/n$. The number of vectors was chosen to be 500 for $d<20$ and
1000 otherwise.

Figure 1 displays the empirical root mean squared error (ERMSE) for the
different location estimates. It is apparent that the cost of privacy is
relatively low for all estimates, though, the classical trade-off between
robustness and efficiency is evident. The mean estimators perform best in the
uncontaminated setting. The opposite is true in the contaminated setting. The
outlier error amplification is greater than the cost of privacy in both
scenarios. That is, the increase in error in all estimates resulting from the
outliers is much larger than the increase in error from private estimation. We
also note that the private smoothed integrated dual depth median performs
better than the private projection-depth-based median in the uncontaminated
setting, but worse than the private projection-depth-based median in the
contaminated setting. When considering which median to use, it is helpful to
note that the smoothed integrated dual depth median is considerably faster to
compute in high dimensions than the projection-depth-based median. However, it
is only equivariant under similarity transformations [20], while the
projection-depth-based medians, are equivariant under affine transformations
[26].

##  5 General results on propose-test-release mechanisms

In this section, we elaborate on the notion of safety [6, 17] in the general
case of PTR mechanisms. We show that safety is both sufficient and necessary
for privacy of a PTR mechanism. We also present general results for analyzing
a PTR mechanism based on the exponential mechanism. If $\lambda(\hat{\nu})$ is
small whenever $\hat{\nu}$ is not in the safe set of $Q$ and the test
mechanism is differentially private, then a PTR mechanism will be
differentially private.

######  Theorem 5.1.

Given $\epsilon_{1},\epsilon_{2},\delta_{1},\delta_{2},\delta_{3}>0$, let $P$
be the PTR mechanism based on $Q(\cdot;\cdot,\epsilon_{2},\delta_{2})$ and
$\lambda(\cdot,\epsilon_{1},\delta_{1})$. If $\lambda$ is
$(\epsilon_{1},\delta_{1})$-differentially private and is such that for any
$\hat{\nu}\notin\mathbf{S}(Q,\epsilon_{2},\delta_{2})$,
$\lambda(\hat{\nu},\epsilon_{1},\delta_{1})<\delta_{3}$, then $P$ is
$(\epsilon_{1}+\epsilon_{2},\delta_{1}+\delta_{2}\vee\delta_{3})$-differentially
private.

###### Proof.

First, consider $\hat{\nu}\in\mathbf{S}(Q,\epsilon_{2},\delta_{2})$. By
composition, the differential privacy bound with parameters
$(\epsilon_{1}+\epsilon_{2},\delta_{1}+\delta_{2})$ will be satisfied. Now,
consider $\hat{\nu}\notin\mathbf{S}(Q,\epsilon_{2},\delta_{3})$. For sets such
that $\perp\notin A$, then
$P_{\hat{\nu}}(A)\leq\lambda(\hat{\nu})\leq\delta_{3}.$ For sets such that
$\perp\in A$, then

$P_{\hat{\nu}}(A)\leq P_{\hat{\nu}}(\\{\perp\\})+\delta_{3}\leq
P_{\tilde{\nu}}(\\{\perp\\})e^{\epsilon_{1}}+\delta_{2}+\delta_{3}.\qed$

The previous theorem gives sufficient conditions on both the privacy guarantee
of the test mechanism and the relationship between the test mechanism and the
safe set of $Q$ to gain differential privacy of a PTR mechanism. We can
conversely show that a $(\epsilon,\delta)$-differentially private propose test
release algorithm consists of a test that is at least
$(\epsilon,\delta)$-differentially private and, for datasets likely to pass
the test, the release mechanism-dataset pair is safe.

######  Theorem 5.2.

Suppose that a PTR mechanism $P$ based on $Q$ and $\lambda$ is
$(\epsilon,\delta)$-differentially private. Then

  1. 1.

The test mechanism characterized by $\lambda$ satisfies
$(\epsilon,\delta)$-differential privacy.

  2. 2.

For any $\hat{\nu}$ such that $\lambda(\hat{\nu})>1/k$, the pair
$(Q(;\hat{\nu},\epsilon),\hat{\nu})$ is $(2\epsilon,k\delta
e^{\epsilon})$-safe.

###### Proof.

The first item follows from applying the $(\epsilon,\delta)$-differential
privacy inequality to the set $\\{\perp\\}$. The second item follows the first
item, and from applying the $(\epsilon,\delta)$-differential privacy
inequality to a set $A$ such that $\perp\notin A$. ∎

Now, the critical components for accuracy are that
$\Pr\left(\hat{\nu}\in\mathbf{S}(Q,\epsilon,\delta)\right)$ is large and that
$\lambda(\hat{\nu})$ is large when
$\hat{\nu}\in\mathbf{S}(Q,\epsilon,\delta)$. We formalize this for the well-
known exponential mechanism as follows. Let $G$ be the CDF of a standard
Laplace RV.

######  Lemma 5.3.

For all $\epsilon,\tau,\eta>0$, $\delta\leq e^{-\epsilon/2}/2$, $n,d\geq 1$
and $\nu\in\mathcal{M}_{1}(\mathbb{R}^{d})$ it holds that

$\mathbb{E}\lambda(\hat{\nu},\epsilon,\delta)\geq
1-\Pr\left(\inf_{y>0}e^{-\epsilon
y/4\eta}\frac{\operatorname{vol}(A_{\tau+2\eta,\hat{\nu}}\cap
A_{\tau-2\eta,\hat{\nu}}^{c})}{\operatorname{vol}(A_{\tau-y-2\eta,\hat{\nu}})}>e^{-\epsilon/4}\delta/3\right)\\\
-\inf_{k\in\\{0\\}\cup[n-1]}\left[\Pr\left(\sup_{\begin{subarray}{c}\tilde{\nu}\in\widetilde{\mathcal{M}}_{1}(\hat{\nu},k+1)\\\
x\in A_{\tau+\eta,\hat{\nu}}\cup
A_{\tau+\eta,\tilde{\nu}}\end{subarray}}|\phi(x,\hat{\nu})-\phi(x,\tilde{\nu})|>\eta/2\right)+G(\log(1/2\delta)-\epsilon
k/2)\right].$

The proof of Lemma 5.3 can be found in Appendix D. This lemma can be
interpreted as follows: the probability of passing the test is high when the
probability that, for some small $\alpha>0$, the $\tau\pm\alpha$-contours of
$\phi(\cdot,\hat{\nu})$ are not too steep and the objective is locally
insensitive within the $\tau\pm\alpha$-contour.

##  6 Conclusion

In this paper we introduce $(\epsilon,\delta)$-differentially private
projection-depth-based medians. Without enforcing any moment bounds on the
population measure, we bound the deviation of the private projection-depth-
based medians about their population values, and quantify the probability that
the test in the PTR algorithm fails. We demonstrate our results by applying
them to the particular projection-depth-based median that uses the median and
median absolute deviation. In this case, we show that in the Gaussian setting,
the deviation bound nearly matches the lower bound for sub-Gaussian mean
estimation given by Cai et al.,  [8]. This provides yet another example of the
usefulness of robust statistics in a differentially private setting. We also
show that in the Cauchy setting, the “outlier error amplification” is larger
than the cost of privacy. This phenomenon is also observed in our numerical
studies.

The main concern for future work is the computation of private projection-
depth-based medians. In particular, it is interesting and important to
quantify the violation of the differential privacy guarantee, if any, that
results from using Langevin Dynamics to sample from the exponential mechanism.
In addition, more sophisticated methods to compute the outlyingness could be
developed, possibly using the results of Dyckerhoff et al.,  [12].

## References

  * Abowd et al., [2022] Abowd, J., Ashmead, R., Cumings-Menon, R., Garfinkel, S., Heineck, M., Heiss, C., Johns, R., Kifer, D., Leclerc, P., Machanavajjhala, A., Moran, B., Sexton, W., Spence, M., and Zhuravlev, P. (2022).  The 2020 Census Disclosure Avoidance System TopDown Algorithm.  Harvard Data Science Review, (Special Issue 2).  https://hdsr.mitpress.mit.edu/pub/7evz361i.
  * Aden-Ali et al., [2021] Aden-Ali, I., Ashtiani, H., and Kamath, G. (2021).  On the sample complexity of privately learning unbounded high-dimensional gaussians.  In Feldman, V., Ligett, K., and Sabato, S., editors, Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pages 185–216. PMLR.
  * Avella-Medina and Brunel, [2019] Avella-Medina, M. and Brunel, V.-E. (2019).  Differentially private sub-Gaussian location estimators.  arXiv e-prints.  arXiv:1906.11923.
  * Ben-Eliezer et al., [2022] Ben-Eliezer, O., Mikulincer, D., and Zadik, I. (2022).  Archimedes Meets Privacy: On Privately Estimating Quantiles in High Dimensions Under Minimal Assumptions.  arXiv e-prints, page arXiv:2208.07438.
  * Biswas et al., [2020] Biswas, S., Dong, Y., Kamath, G., and Ullman, J. (2020).  CoinPress: Practical private mean and covariance estimation.  Advances in Neural Information Processing Systems, 33:14475–14485.
  * Brown et al., [2021] Brown, G., Gaboardi, M., Smith, A., Ullman, J., and Zakynthinou, L. (2021).  Covariance-aware private mean estimation without private covariance estimation.  Advances in Neural Information Processing Systems, 34:7950–7964.
  * Brunel and Avella-Medina, [2020] Brunel, V.-E. and Avella-Medina, M. (2020).  Propose, test, release: Differentially private estimation with high probability.  arXiv e-prints.  arXiv:2002.08774.
  * Cai et al., [2021] Cai, T. T., Wang, Y., and Zhang, L. (2021).  The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy.  The Annals of Statistics, 49(5):2825 – 2850.
  * Donoho and Gasko, [1992] Donoho, D. L. and Gasko, M. (1992).  Breakdown properties of location estimates based on halfspace depth and projected outlyingness.  The Annals of Statistics, 20(4):1803 – 1827.
  * Dwork and Lei, [2009] Dwork, C. and Lei, J. (2009).  Differential privacy and robust statistics.  Proceedings of the 41st annual ACM symposium on theory of computing - STOC ’09, page 371.
  * Dwork and Roth, [2014] Dwork, C. and Roth, A. (2014).  The algorithmic foundations of differential privacy.  Foundations and Trends in Theoretical Computer Science, 9(3–4):211–407.
  * Dyckerhoff et al., [2021] Dyckerhoff, R., Mozharovskyi, P., and Nagy, S. (2021).  Approximate computation of projection depths.  Computational Statistics & Data Analysis, 157:107166.
  * Fernandez-Rico, [2022] Fernandez-Rico, Z. (2022).  Optimal statistical estimation: sub-Gaussian properties, heavy-tailed data, and robustness.  PhD thesis, Instituto de Matemática Pura e Aplicada.
  * Hampel et al., [2005] Hampel, F. R., Ronchetti, E. M., Rousseeuw, P. J., and Stahel, W. A. (2005).  Robust Statistics: The Approach Based on Influence Functions.  Wiley.
  * Hopkins et al., [2022] Hopkins, S. B., Kamath, G., and Majid, M. (2022).  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.
  * Kamath et al., [2018] Kamath, G., Li, J., Singhal, V., and Ullman, J. (2018).  Privately learning high-dimensional distributions.  arXiv e-prints.  arXiv:1805.00216.
  * [17] Liu, X., Kong, W., Kakade, S., and Oh, S. (2021a).  Robust and differentially private mean estimation.  arXiv e-prints.  arXiv:2102.09159.
  * [18] Liu, X., Kong, W., and Oh, S. (2021b).  Differential privacy and robust statistics in high dimensions.  arXiv e-prints.  arXiv:2111.06578.
  * Pyke, [1965] Pyke, R. (1965).  Spacings.  Journal of the Royal Statistical Society: Series B (Methodological), 27(3):395–436.
  * Ramsay et al., [2022] Ramsay, K., Jagannath, A., and Chenouri, S. (2022).  Concentration of the exponential mechanism and differentially private multivariate medians.
  * Rousseeuw and Croux, [1993] Rousseeuw, P. J. and Croux, C. (1993).  Alternatives to the median absolute deviation.  Journal of the American Statistical Association, 88(424):1273–1283.
  * Seeman et al., [2021] Seeman, J., Reimherr, M., and Slavković, A. (2021).  Exact privacy guarantees for markov chain implementations of the exponential mechanism with artificial atoms.  Advances in Neural Information Processing Systems, 34:13125–13136.
  * Talagrand, [1994] Talagrand, M. (1994).  Sharper bounds for gaussian and empirical processes.  The Annals of Probability, 22(1):28–76.
  * Tzamos et al., [2020] Tzamos, C., Vlatakis-Gkaragkounis, E.-V., and Zadik, I. (2020).  Optimal private median estimation under minimal distributional assumptions.  Advances in Neural Information Processing Systems, 33:3301–3311.
  * Vershynin, [2018] Vershynin, R. (2018).  High-dimensional probability: An introduction with applications in data science, volume 47.  Cambridge university press.
  * Zuo, [2003] Zuo, Y. (2003).  Projection-based depth functions and associated medians.  The Annals of Statistics, 31(5):1460–1490.
  * Zuo, [2004] Zuo, Y. (2004).  Influence function and maximum bias of projection depth based estimators.  Annals of Statistics, 32(1):189–218.
  * Zuo and Serfling, [2000] Zuo, Y. and Serfling, R. (2000).  General notions of statistical depth function.  Annals of Statistics, 28(2):461–482.

##  Appendix A Algorithm

Here we outline the algorithm used to compute the private, projection-depth-
based median in Section 4. We will approximate $O(x,\hat{\nu})$ by
$\widehat{O}(x,\hat{\nu})=\sup_{u\in\mathcal{U}_{N}}O_{u}(x,\hat{\nu})$, where
$\mathcal{U}_{N}$ is a set of $N$ unit vectors sampled uniformly from
$\mathbb{S}^{d-1}$. The algorithm consists of two parts, executing the test
and sampling from the exponential mechanism. For the latter, observe that the
outlyingness function is quasiconvex, i.e., its lower level sets are convex.
This allows us to apply an envelope theorem to compute the gradient of
$\widehat{O}_{u}(x,\hat{\nu})$ with respect to $x$. To this end, for $x\in
A_{\tau}$, let $u_{x}$ be the unit vector that maximizes
$\widehat{O}_{u}(x,\hat{\nu})$. Then, for any $x\in A_{\tau}$, it holds that

$\displaystyle\nabla\widehat{O}(x,\nu)$
$\displaystyle=u_{x}\frac{\mathrm{sign}(x^{\top}u_{x}-\mu_{u_{x}})}{\sigma_{u_{x}}}.$

To compute the non-private projection-depth-based median, we use gradient
descent, and, to sample from the exponential mechanism, we use Langevin
Dynamics. Given that Langevin Dynamics samples approximately from the
exponential mechanism, we note that this may violate the differential privacy
condition, and stress that this implementation is just to confirm the
theoretical properties of the proposed private median. Of course, more
sophisticated methods to compute the outlyingness could be developed, such as
those based on [12], but we leave that for future work. Indeed, given the
caveat on using Langevin Dynamics to sample from the exponential mechanism
mentioned above, an algorithm to compute the private projection-depth-based
median is an interesting open problem.

Algorithm 1 Exponential Mechanism via Langevin Dynamics

procedure EM($X_{1},\ldots,X_{n},\epsilon,\eta,\tau,N,T,\omega$)

Set $\mathcal{U}_{N}$ to be $N$ independent random vectors uniformly over
$\mathbb{S}^{d-1}$.

Set $Y_{0}=\mathcal{N}(0,I)$

for $i\in[T]$ do

Set $O=\widehat{O}(x,\hat{\nu})$

if $O>\tau$ then

Set $\nabla O=0$

else

Set $\nabla O=\nabla\widehat{O}(x,\hat{\nu})$

end if

Set $Z_{i}=\mathcal{N}(0,I)$

Set $Y_{i}=Y_{i-1}-\omega\frac{\epsilon}{4\eta}\nabla O+\sqrt{2\omega}Z_{i}$

end for

return $Y_{T}$

end procedure

Algorithm 2 Test Mechanism

procedure Test($X_{1},\ldots,X_{n},\epsilon,\delta,\eta,\tau,d$)

Set $k=1$

Set $\mathrm{Dev\\_Cond}=$True

Set $\mathrm{Vol\\_Cond}=$True

while $\mathrm{Dev\\_Cond}$ and $\mathrm{Vol\\_Cond}$ do

Set $k=k+1$

Set $\mathrm{Vol\\_Cond}=\mathrm{VR}_{k}<\delta$

Compute $\widehat{S}_{n,k}(\sigma),\ \widehat{S}_{n,k}(\mu),\ \hat{b}$

Set $\mathrm{Dev\\_Cond}=\widehat{\Delta}_{k}<\eta$

end while

Set $\operatorname{SM}=k-2$.

Generate $W\sim\operatorname*{{\rm Laplace}}(0,1)$

return
$\operatorname{SM}+\frac{2}{\epsilon}>\frac{2\log(1/2\delta)}{\epsilon}$

end procedure

Algorithm 3 Private PDB Median

procedure
Private_Median($X_{1},\ldots,X_{n},\epsilon,\delta,\eta,\tau,d,T,\omega$)

Set $\mathrm{test}=$Test($X_{1},\ldots,X_{n},\epsilon,\delta,\eta,\tau,d$)

if $\mathrm{test}$ then return $\perp$

else return
$\operatorname{EM}(X_{1},\ldots,X_{n},\epsilon,\eta,\tau,T,\omega)$

end if

end procedure

To perform the test, it is clearly difficult to compute the safety margin in
this case. As a result, we can make use of Lemma D.2, Lemma B.3 and Lemma B.4.
Now, define

$\widehat{S}_{n,k}(T)=\sup_{\begin{subarray}{c}\tilde{\nu}\in\widetilde{\mathcal{M}}_{1}(\hat{\nu},k)\\\
u\in\mathcal{U}_{N}\end{subarray}}|T(\hat{\nu}_{u})-T(\tilde{\nu}_{u})|.$

We must first compute three quantities:
$\widehat{S}_{n,k}(\mu),\widehat{S}_{n,k}(\sigma)$ and
$\hat{b}=\inf_{\begin{subarray}{c}\tilde{\nu}\in\widetilde{\mathcal{M}}_{1}(\hat{\nu},k)\cup\\{\hat{\nu}\\}\\\
u\in\mathcal{U}_{N}\end{subarray}}\sigma(\hat{\nu}_{u})$. First, it is easy to
check that if $\mu=\operatorname{MED}$, then

$\widehat{S}_{n,k}(\mu)\leq\sup_{u\in\mathcal{U}_{N}}[|(X^{\top}u)_{(\lfloor(n+1)/2\rfloor+k)}-(X^{\top}u)_{(\lfloor(n+1)/2\rfloor)}|\vee|(X^{\top}u)_{(\lfloor(n+1)/2\rfloor)}-(X^{\top}u)_{(\lfloor(n+1)/2\rfloor-k)}|].$

In order to compute the $\widehat{S}_{n,k}(\sigma)$ where
$\sigma=\operatorname{MAD}$, we can first consider the local sensitivity of
the median absolute deviation, for a univariate sample $Z_{1},\ldots,Z_{n}$
with empirical measure $\hat{\nu}$. Let $Y_{i}(z)=|Z_{i}-z|$ and call this
measure $\hat{\nu}_{z}$. Consider $\tilde{\nu}\in\mathcal{M}(k,\hat{\nu})$.
First, note that
$\mu(\tilde{\nu})\in[Z_{(\lfloor(n+1)/2\rfloor+k)},Z_{(\lfloor(n+1)/2\rfloor-k)}]=[a_{k},b_{k}]$.
Now observe that

$\displaystyle\sup_{\tilde{\nu}\in\mathcal{M}(k,\hat{\nu})}|\sigma(\tilde{\nu})-\sigma(\hat{\nu})|$
$\displaystyle\leq\sup_{z\in[a_{k},b_{k}]}\sup_{\tilde{\nu}\in\mathcal{M}(k,\hat{\nu}_{z})}|\operatorname{MED}(\hat{\nu}_{z})-\operatorname{MED}(\tilde{\nu})|$
$\displaystyle\leq\sup_{z\in[a_{k},b_{k}]}|Y_{(\lfloor(n+1)/2\rfloor+k)}(z)-Y_{(\lfloor(n+1)/2\rfloor)}(z)|$
$\displaystyle\hskip
100.0pt\vee|Y_{(\lfloor(n+1)/2\rfloor-k)}(z)-Y_{(\lfloor(n+1)/2\rfloor)}(z)|.$

Note that the right-hand side of the above inequality is a piecewise linear
function in $z$, with knots at the observations. Thus, it suffices to compute
this function for the $2k$ observations in $[a_{k},b_{k}]$. Thus, letting
$Y_{i,u}(z)=|X_{i}^{\top}u-z|$,

$\widehat{S}_{n,k}(\sigma)\leq\sup_{\begin{subarray}{c}u\in\mathcal{U}_{N}\\\
z\in[a_{k},b_{k}]\end{subarray}}|Y_{(\lfloor(n+1)/2\rfloor+k),u}(z)-Y_{(\lfloor(n+1)/2\rfloor),u}(z)|\vee|Y_{(\lfloor(n+1)/2\rfloor-k),u}(z)-Y_{(\lfloor(n+1)/2\rfloor),u}(z)|.$

Similarly,
$\hat{b}\leq\inf_{u\in\mathcal{U}_{N}}\inf_{z\in[a_{k},b_{k}]}|Y_{(\lfloor(n+1)/2\rfloor),u}(z)|.$

Next, we can compute
$\widehat{\Delta}_{k}=((\tau+\eta)\widehat{S}_{n,k}(\sigma)+\widehat{S}_{n,k}(\mu))/\hat{b}$.
The last step is to compute the volume condition in Lemma D.2 using Lemma B.4
and check if

$\mathrm{VR}_{k}\coloneqq\exp\left(-\epsilon\tau/4\eta+\epsilon(1/2+\hat{\alpha}_{\mu}/4\inf_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}\eta)+d\right)\left(\frac{\sup_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau+2\eta)+\hat{\alpha}_{\mu}}{\inf_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}4\eta
d\epsilon}\right)^{d}\leq\delta.$

All the described methods are summarized in Algorithms 1–3.

##  Appendix B Proofs from Section 3.1

Prior to proving the main results, we first establish probability bounds that
will be used throughout the following proofs.

######  Lemma B.1.

Let
$\hat{\alpha}_{\mu}=\sup_{u\in\mathbb{S}^{d-1}}\hat{\mu}_{u}-\inf_{u\in\mathbb{S}^{d-1}}\hat{\mu}_{u}$
and
$\alpha_{\mu}=\sup_{u\in\mathbb{S}^{d-1}}\mu_{u}-\inf_{u\in\mathbb{S}^{d-1}}\mu_{u}$.

  1. 1.

Assuming Conditions 1-3:

$\Pr\Big{(}\inf_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\
\tilde{\nu}\in\\{\hat{\nu}_{u}\\}\cup\widetilde{\mathcal{M}}_{1}(\hat{\nu}_{u},k)\end{subarray}}\sigma(\tilde{\nu})\leq\frac{c_{1}}{2}\Big{)}\lesssim
a_{1,d}e^{-a_{2,d,k}nc_{1}/4}+\kappa_{n}+\zeta_{n,d}(\frac{c_{1}}{4}).$ (B.1)

  2. 2.

Assuming $\alpha_{\mu}\leq 2c_{3}$ and that Condition 2 holds:

$\Pr\left(\widehat{a}_{\mu}>4c_{3}\right)\lesssim\zeta_{n,d}(c_{3}).$ (B.2)

  3. 3.

Assuming Conditions 2 and 3:

$\Pr\left(\sup_{u\in\mathbb{S}^{d-1}}\sigma(\hat{\nu}_{u})\geq
2c_{2}\right)\lesssim\zeta_{n,d}(c_{2}).$ (B.3)

  4. 4.

Assuming Conditions 2 and 3:

$\Pr\left(\inf_{u\in\mathbb{S}^{d-1}}\sigma(\hat{\nu}_{u})\leq
c_{1}/2\right)\lesssim\zeta_{n,d}(\frac{c_{1}}{2}).$ (B.4)

###### Proof.

Proof of (B.1):

$\displaystyle\inf_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\
\tilde{\nu}\in\\{\hat{\nu}_{u}\\}\cup\widetilde{\mathcal{M}}_{1}(\hat{\nu}_{u},k)\end{subarray}}\sigma(\tilde{\nu})$
$\displaystyle=\inf_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\
\tilde{\nu}\in\\{\hat{\nu}_{u}\\}\cup\widetilde{\mathcal{M}}_{1}(\hat{\nu}_{u},k)\end{subarray}}(\sigma(\tilde{\nu})-\sigma(\hat{\nu})+\sigma(\hat{\nu}))$
$\displaystyle\geq\inf_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\
\tilde{\nu}\in\\{\hat{\nu}_{u}\\}\cup\widetilde{\mathcal{M}}_{1}(\hat{\nu}_{u},k)\end{subarray}}(\sigma(\tilde{\nu})-\sigma(\hat{\nu}))+\inf_{u\in\mathbb{S}^{d-1}}\sigma(\hat{\nu})$
$\displaystyle\geq\inf_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\
\tilde{\nu}\in\\{\hat{\nu}_{u}\\}\cup\widetilde{\mathcal{M}}_{1}(\hat{\nu}_{u},k)\end{subarray}}(\sigma(\tilde{\nu})-\sigma(\hat{\nu}))+\inf_{u\in\mathbb{S}^{d-1}}(\sigma(\hat{\nu})-\sigma(\nu))+\inf_{u\in\mathbb{S}^{d-1}}\sigma(\nu)$
$\displaystyle\geq-\sup_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\
\tilde{\nu}\in\\{\hat{\nu}_{u}\\}\cup\widetilde{\mathcal{M}}_{1}(\hat{\nu}_{u},k)\end{subarray}}|\sigma(\tilde{\nu})-\sigma(\hat{\nu})|-\sup_{u\in\mathbb{S}^{d-1}}|\sigma(\hat{\nu})-\sigma(\nu)|+c_{1}.$

The last inequality uses Condition 3. Then, if
$\inf_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\
\tilde{\nu}\in\\{\hat{\nu}_{u}\\}\cup\widetilde{\mathcal{M}}_{1}(\hat{\nu}_{u},k)\end{subarray}}\sigma(\tilde{\nu})\leq
c_{1}/2$,

$\displaystyle-\sup_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\
\tilde{\nu}\in\\{\hat{\nu}_{u}\\}\cup\widetilde{\mathcal{M}}_{1}(\hat{\nu}_{u},k)\end{subarray}}|\sigma(\tilde{\nu})-\sigma(\hat{\nu})|-\sup_{u\in\mathbb{S}^{d-1}}|\sigma(\hat{\nu})-\sigma(\nu)|+c_{1}$
$\displaystyle\leq\frac{c_{1}}{2}$
$\displaystyle\implies\sup_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\
\tilde{\nu}\in\\{\hat{\nu}_{u}\\}\cup\widetilde{\mathcal{M}}_{1}(\hat{\nu}_{u},k)\end{subarray}}|\sigma(\tilde{\nu})-\sigma(\hat{\nu})|+\sup_{u\in\mathbb{S}^{d-1}}|\sigma(\hat{\nu})-\sigma(\nu)|$
$\displaystyle\geq\frac{c_{1}}{2}.$

Taken together,

$\displaystyle\Pr\left(E_{2}^{c}\right)$
$\displaystyle\leq\Pr\left(\sup_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\
\tilde{\nu}\in\\{\hat{\nu}_{u}\\}\cup\widetilde{\mathcal{M}}_{1}(\hat{\nu}_{u},k)\end{subarray}}|\sigma(\tilde{\nu})-\sigma(\hat{\nu})|+\sup_{u\in\mathbb{S}^{d-1}}|\sigma(\hat{\nu})-\sigma(\nu)|\geq\frac{c_{1}}{2}\right)$
$\displaystyle\leq\Pr\left(\sup_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\
\tilde{\nu}\in\\{\hat{\nu}_{u}\\}\cup\widetilde{\mathcal{M}}_{1}(\hat{\nu}_{u},k)\end{subarray}}|\sigma(\tilde{\nu})-\sigma(\hat{\nu})|\geq\frac{c_{1}}{4}\right)+\Pr\left(\sup_{u\in\mathbb{S}^{d-1}}|\sigma(\hat{\nu})-\sigma(\nu)|\geq\frac{c_{1}}{4}\right)$
$\displaystyle\lesssim
a_{1,d}e^{-a_{2,d,k}nc_{1}/4}+\kappa_{n}+\zeta_{n,d}(\frac{c_{1}}{4}).$

The final inequality follows directly from Conditions 1 and 2

Proof of (B.2): Note that

$\displaystyle\hat{\alpha}_{\mu}=\sup_{u\in\mathbb{S}^{d-1}}\hat{\mu}_{u}-\inf_{u\in\mathbb{S}^{d-1}}\hat{\mu}_{u}$
$\displaystyle=\sup_{u\in\mathbb{S}^{d-1}}(\hat{\mu}_{u}+\mu_{u}-\mu_{u})+\sup_{u\in\mathbb{S}^{d-1}}(-\hat{\mu}_{u}+\mu_{u}-\mu_{u})$
$\displaystyle\leq\sup_{u\in\mathbb{S}^{d-1}}|\hat{\mu}_{u}-\mu_{u}|+\sup_{u\in\mathbb{S}^{d-1}}\mu_{u}+\sup_{u\in\mathbb{S}^{d-1}}|\mu_{u}-\hat{\mu}_{u}|-\inf_{u\in\mathbb{S}^{d-1}}\mu_{u}$
$\displaystyle=2\sup_{u\in\mathbb{S}^{d-1}}|\mu_{u}-\hat{\mu}_{u}|+a_{\mu}$
$\displaystyle\leq
2\left(\sup_{u\in\mathbb{S}^{d-1}}|\mu_{u}-\hat{\mu}_{u}|+c_{3}\right),$

where we used the fact that $\alpha_{\mu}\leq 2c_{3}$. As a result, applying
Condition 2,

$\Pr\left(E_{3}^{c}\right)\leq\Pr\left(2\left(\sup_{u\in\mathbb{S}^{d-1}}|\mu_{u}-\hat{\mu}_{u}|+c_{3}\right)>4c_{3}\right)=\Pr\left(\sup_{u\in\mathbb{S}^{d-1}}|\mu_{u}-\hat{\mu}_{u}|>c_{3}\right)\lesssim\zeta_{n,d}(c_{3}).$

Proof of (B.3):

$\displaystyle\sup_{u\in\mathbb{S}^{d-1}}\sigma(\hat{\nu}_{u})$
$\displaystyle=\sup_{u\in\mathbb{S}^{d-1}}\left(\sigma(\hat{\nu}_{u})-\sigma(\nu_{u})+\sigma(\nu_{u})\right)$
$\displaystyle\leq\sup_{u\in\mathbb{S}^{d-1}}\left(\sigma(\hat{\nu}_{u})-\sigma(\nu_{u})\right)+\sup_{u\in\mathbb{S}^{d-1}}\sigma(\nu_{u})$
$\displaystyle\leq\sup_{u\in\mathbb{S}^{d-1}}|\sigma(\hat{\nu}_{u})-\sigma(\nu_{u})|+c_{2},$

where the final inequality relies on condition 3. Then,

$\displaystyle\Pr\left(\sup_{u\in\mathbb{S}^{d-1}}\sigma(\hat{\nu}_{u})\geq
2c_{2}\right)$
$\displaystyle\leq\Pr\left(\sup_{u\in\mathbb{S}^{d-1}}|\sigma(\hat{\nu}_{u})-\sigma(\nu_{u})|+c_{2}\geq
2c_{2}\right)$
$\displaystyle=\Pr\left(\sup_{u\in\mathbb{S}^{d-1}}|\sigma(\hat{\nu}_{u})-\sigma(\nu_{u})|\geq
c_{2}\right)$ $\displaystyle\lesssim\zeta_{n,d}(c_{2}),$

where the final result is a straightforward application of condition 2.

Proof of (B.4):

$\displaystyle\inf_{u\in\mathbb{S}^{d-1}}\sigma(\hat{\nu}_{u})$
$\displaystyle=\inf_{u\in\mathbb{S}^{d-1}}\left(\sigma(\hat{\nu}_{u})-\sigma(\nu_{u})+\sigma(\nu_{u})\right)$
$\displaystyle\geq\inf_{u\in\mathbb{S}^{d-1}}\left(\sigma(\hat{\nu}_{u})-\sigma(\nu_{u})\right)+\inf_{u\in\mathbb{S}^{d-1}}\left(\sigma(\nu_{u})\right)$
$\displaystyle=-\sup_{u\in\mathbb{S}^{d-1}}\left(\sigma(\nu_{u})-\sigma(\hat{\nu}_{u})\right)+\inf_{u\in\mathbb{S}^{d-1}}\left(\sigma(\nu_{u})\right)$
$\displaystyle\geq-\sup_{u\in\mathbb{S}^{d-1}}\left|\sigma(\nu_{u})-\sigma(\hat{\nu}_{u})\right|+c_{1},$

where the final inequality relies on Condition 3. This means that

$\displaystyle\Pr\left(\inf_{u\in\mathbb{S}^{d-1}}\sigma(\hat{\nu}_{u})\leq\frac{c_{1}}{2}\right)$
$\displaystyle\leq\Pr\left(-\sup_{u\in\mathbb{S}^{d-1}}\left|\sigma(\nu_{u})-\sigma(\hat{\nu}_{u})\right|+c_{1}\leq\frac{c_{1}}{2}\right)$
$\displaystyle=\Pr\left(\sup_{u\in\mathbb{S}^{d-1}}\left|\sigma(\nu_{u})-\sigma(\hat{\nu}_{u})\right|\geq\frac{c_{1}}{2}\right)$
$\displaystyle\lesssim\zeta_{n,d}(\frac{c_{1}}{2}),$

where the final line is a simple application of Condition 2. ∎

###### Proof of Theorem 3.1.

First, note that $\mu$ and $\sigma$ may satisfy Conditions 1 and 2 for
different parameters, e.g., different sequences $\zeta$. However, we can
define a set of joint parameters $\zeta,\kappa_{n},\ldots$ for which the
bounds in Conditions 1 and 2 hold for both $\mu$ and $\sigma$, which we will
use throughout the proof. Let
$b_{k,u}^{-}=\inf_{\tilde{\nu}\in\\{\hat{\nu}_{u}\\}\cup\widetilde{\mathcal{M}}_{1}(\hat{\nu}_{u},k)}\sigma(\tilde{\nu})$,
$\hat{\alpha}_{\mu}=\sup_{u\in\mathbb{S}^{d-1}}\hat{\mu}_{u}-\inf_{u\in\mathbb{S}^{d-1}}\hat{\mu}_{u}$,
$\alpha_{\mu}=\sup_{u\in\mathbb{S}^{d-1}}\mu_{u}-\inf_{u\in\mathbb{S}^{d-1}}\mu_{u}$.

An application of Lemma 5.3 with $\phi=O$, and subsequently taking
$k=4\log(1/2\delta)/\epsilon$ yields:

$\displaystyle\mathbb{E}\lambda(\hat{\nu},\epsilon,\delta)$ $\displaystyle\geq
1-\Pr\left(E_{1}\right)$ $\displaystyle\hskip
30.0pt-\inf_{k\in[n]}\left[\Pr\Big{(}\sup_{\begin{subarray}{c}\tilde{\nu}\in\widetilde{\mathcal{M}}_{1}(\hat{\nu},k+1)\\\
x\in A_{\tau+\eta,\hat{\nu}}\cup
A_{\tau+\eta,\tilde{\nu}}\end{subarray}}|O(x,\hat{\nu})-O(x,\tilde{\nu})|>\eta\Big{)}+G\left(\log\frac{1}{2\delta}-\frac{\epsilon
k}{2}\right)\right]$ $\displaystyle\geq
1-\Pr\left(E_{1}\right)-\Pr\Big{(}\sup_{\begin{subarray}{c}\tilde{\nu}\in\widetilde{\mathcal{M}}_{1}(\hat{\nu},4\log(1/2\delta)/\epsilon+1)\\\
x\in A_{\tau+\eta,\hat{\nu}}\cup
A_{\tau+\eta,\tilde{\nu}}\end{subarray}}|O(x,\hat{\nu})-O(x,\tilde{\nu})|>\eta\Big{)}-\delta,$
(B.5)

where

$E_{1}=\left\\{\inf_{y>0}e^{-\epsilon
y/4\eta}\frac{\operatorname{vol}(A_{\tau+2\eta,\hat{\nu}}\cap
A^{c}_{\tau-2\eta,\hat{\nu}})}{\operatorname{vol}(A_{\tau-y-2\eta,\hat{\nu}})}>e^{-\epsilon/2}\delta\right\\}.$

We now bound the deviation of the outlyingness function with high probability.
To this end, note that Lemma B.3 implies that for any $k\in[n]$,

$\displaystyle\Pr\Big{(}\sup_{\begin{subarray}{c}\tilde{\nu}\in\widetilde{\mathcal{M}}_{1}(\hat{\nu},k)\\\
x\in A_{\tau+\eta,\hat{\nu}}\cup
A_{\tau+\eta,\tilde{\nu}}\end{subarray}}|O(x,\hat{\nu})-O(x,\tilde{\nu})|>\eta\Big{)}\leq\Pr\left(\Delta_{k}>\eta\right),$

where

$\Delta_{k}=\frac{\tau\tilde{S}_{n,k}(\sigma)+\tilde{S}_{n,k}(\mu)}{\inf_{u\in\mathbb{S}^{d-1}}b_{k,u}^{-}}.$

Define $E_{2}=\left\\{\inf_{u\in\mathbb{S}^{d-1}}b_{k,u}^{-}\geq
c_{1}/2\right\\}$. Then, conditioning on $E_{2}$ we have that

$\Delta_{k}\leq\frac{2}{c_{1}}\left[\tau\tilde{S}_{n,k}(\sigma)+\tilde{S}_{n,k}(\mu)\right],$

and so

$\displaystyle\Pr\left(\Delta_{k}\geq\eta|E_{2}\right)$
$\displaystyle\leq\Pr\left(\frac{2}{c_{1}}\left[\tau\tilde{S}_{n,k}(\sigma)+\tilde{S}_{n,k}(\mu)\right]\geq\eta|E_{2}\right)$
$\displaystyle\leq\Pr\left(\frac{2}{c_{1}}\left[\tau\tilde{S}_{n,k}\right]\geq\eta/2|E_{2}\right)+\Pr\left(\frac{2}{c_{1}}\left[(\sigma)+\tilde{S}_{n,k}(\mu)\right]\geq\eta/2|E_{2}\right)$
$\displaystyle=\Pr\left(\tilde{S}_{n,k}\geq
c_{1}\eta/4\tau|E_{2}\right)+\Pr\left((\sigma)+\tilde{S}_{n,k}(\mu)\geq
c_{1}\eta/4|E_{2}\right).$

Thus, applying Condition 1 gives

$\displaystyle\Pr\left(\Delta_{k}>\eta|E_{2}\right)$
$\displaystyle\lesssim\Pr\left(\tilde{S}_{n,k}(\mu)>c_{1}\eta/4|E_{2}\right)+\Pr\left(\tilde{S}_{n,k}(\sigma)>c_{1}\eta/4\tau|E_{2}\right)$
$\displaystyle\lesssim a_{1,d}e^{-a_{2,d,k}c_{1}n\eta/4(\tau\vee
1)}+\kappa_{n}.$ (B.6)

Note $\Pr\left(E_{2}^{c}\right)$ is bounded based on (B.1). Combining these
past three results yields

$\displaystyle\Pr\Big{(}\sup_{\begin{subarray}{c}\tilde{\nu}\in\widetilde{\mathcal{M}}_{1}(\hat{\nu},k)\\\
x\in A_{\tau+\eta,\hat{\nu}}\cup
A_{\tau+\eta,\tilde{\nu}}\end{subarray}}|O(x,\hat{\nu})-O(x,\tilde{\nu})|>\eta\Big{)}$
$\displaystyle\qquad\leq\Pr\left(\Delta_{k}>\eta|E_{2}\right)\Pr\left(E_{2}\right)+\Pr\left(\Delta_{k}>\eta|E_{2}^{c}\right)\Pr\left(E_{2}^{c}\right)$
$\displaystyle\qquad\leq\Pr\left(\Delta_{k}>\eta|E_{2}\right)+\Pr\left(E_{2}^{c}\right)$
$\displaystyle\qquad\lesssim
a_{1,d}\exp\left(-a_{2,d,k}\frac{c_{1}n}{4}\left[1\wedge\frac{\eta}{\tau\vee
1}\right]\right)+\kappa_{n}+\zeta_{n,d}(\frac{c_{1}}{4}).$

We next bound $\Pr\left(E_{1}\right)$. To do so we will make use of Lemma B.4.
In order to apply the result, we require that
$\inf_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau-y-2\eta)-\hat{\alpha}_{\mu}>0$.
Note that, given $E_{2}$ and the restriction that $\tau\geq
4\eta+16c_{3}/c_{1}$,

$\inf_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau-y-2\eta)-\hat{\alpha}_{\mu}\geq\frac{c_{1}(\tau-y-2\eta)}{2}-\hat{\alpha}_{\mu}\geq
c_{1}\eta+8c_{3}-\frac{c_{1}}{2}y-\hat{\alpha}_{\mu}.$

If we take $E_{3}=\left\\{\hat{\alpha}_{\mu}\leq 4c_{3}\right\\}$, then
further conditioning on $E_{3}$ gives that, for all $y\in\mathcal{L}$, where
$\mathcal{L}=(0,\tau-2\eta-8c_{3}/c_{1})$,
$\inf_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau-y-2\eta)-\hat{\alpha}_{\mu}>0$.
Thus,

$\displaystyle\frac{\operatorname{vol}(A_{\tau+2\eta,\hat{\nu}}\cap
A^{c}_{\tau-2\eta,\hat{\nu}})}{\operatorname{vol}(A_{\tau-y-2\eta,\hat{\nu}})}$
$\displaystyle\leq\left(\frac{\sup_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau+2\eta)+\hat{\alpha}_{\mu}}{\inf_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau-y-2\eta)-\hat{\alpha}_{\mu}}\right)^{d}$
$\displaystyle\qquad-\left(\frac{\inf_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau-2\eta)-\hat{\alpha}_{\mu}}{\inf_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau-y-2\eta)-\hat{\alpha}_{\mu}}\right)^{d}$
$\displaystyle\leq\left(\frac{\sup_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau+2\eta)+\hat{\alpha}_{\mu}}{\inf_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau-y-2\eta)-\hat{\alpha}_{\mu}}\right)^{d}.$

Define $E_{4}=\left\\{\sup_{u\in\mathbb{S}^{d-1}}\sigma(\hat{\nu}_{u})\leq
2c_{2}\right\\}$, so that given $E_{5}=E_{2}\cap E_{3}\cap E_{4}$,

$\left(\frac{\sup_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau+2\eta)+\hat{\alpha}_{\mu}}{\inf_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau-y-2\eta)-\hat{\alpha}_{\mu}}\right)^{d}\leq\left(\frac{2c_{2}(\tau+2\eta)+4c_{3}}{c_{1}(\tau-y-2\eta)/2-4c_{3}}\right)^{d}.$

Thus, taken together,

$\displaystyle\Pr\left(E_{1}\right)$
$\displaystyle\leq\Pr\left(E_{1}|E_{5}\right)+\Pr\left(E_{5}^{c}\right)$
$\displaystyle\leq\Pr\left(\inf_{y\in\mathcal{L}}e^{-\epsilon
y/4\eta}\left(\frac{2c_{2}(\tau+2\eta)+4c_{3}}{c_{1}(\tau-y-2\eta)/2-4c_{3}}\right)^{d}>e^{-\epsilon/2}\delta\right)+\Pr\left(E_{5}^{c}\right)$
$\displaystyle\leq\mathbbm{1}\left\\{\inf_{y\in\mathcal{L}}e^{\epsilon/2-\epsilon
y/4\eta}\left(\frac{2c_{2}(\tau+2\eta)+4c_{3}}{c_{1}(\tau-y-2\eta)/2-4c_{3}}\right)^{d}>\delta\right\\}+\Pr\left(E_{5}^{c}\right).$

Taking $y=\tau/2$, the inequality in the indicator is never satisfied for any

$\delta>e^{\epsilon/2-\epsilon
y/4\eta}\left(\frac{2c_{2}(\tau+2\eta)+4c_{3}}{c_{1}(\tau-y-2\eta)/2-4c_{3}}\right)^{d}=\exp\left\\{\frac{\epsilon}{2}-\frac{\epsilon\tau}{8\eta}+d\log\left(\frac{2c_{2}(\tau+2\eta)+4c_{3}}{c_{1}\tau/4-c_{1}\eta-4c_{3}}\right)\right\\}.$

Thus, for any such $\delta$, we have
$\Pr\left(E_{1}\right)\leq\Pr\left(E_{5}^{c}\right)$.

Using equations (B.1), (B.2), and (B.3) we have bounds on
$\Pr\left(E_{2}^{C}\right)$, $\Pr\left(E_{3}^{C}\right)$, and
$\Pr\left(E_{4}^{C}\right)$ respectively. These three bounds combine to give

$\Pr\left(E_{5}^{c}\right)\lesssim
a_{1,d}e^{-a_{2,d,k}nc_{1}/4}+\kappa_{n}+\zeta_{n,d}(\frac{c_{1}}{4}\wedge
c_{3}).$

Finally,

$\displaystyle\mathbb{E}\lambda(\hat{\nu},\epsilon,\delta)$ $\displaystyle\geq
1-\Pr\left(E_{1}\right)-\Pr\Big{(}\sup_{\begin{subarray}{c}\tilde{\nu}\in\widetilde{\mathcal{M}}_{1}(\hat{\nu},4\log(1/2\delta)/\epsilon+1)\\\
x\in A_{\tau+\eta,\hat{\nu}}\cup
A_{\tau+\eta,\tilde{\nu}}\end{subarray}}|O(x,\hat{\nu})-O(x,\tilde{\nu})|>\eta\Big{)}-\delta$
$\displaystyle\gtrsim
1-\Pr\left(E_{5}^{c}\right)-\left(a_{1,d}\exp\left(-a_{2,d,k}\frac{c_{1}n}{4}\left[1\wedge\frac{\eta}{\tau\vee
1}\right]\right)+\kappa_{n}+\zeta_{n,d}(\frac{c_{1}}{4})\right)-\delta$
$\displaystyle\gtrsim
1-(a_{1,d}e^{-a_{2,d,k}nc_{1}/4}+\kappa_{n}+\zeta_{n,d}(\frac{c_{1}}{4}\wedge
c_{3}))$
$\displaystyle\qquad-\left(a_{1,d}\exp\left(-a_{2,d,k}\frac{c_{1}n}{4}\left[1\wedge\frac{\eta}{\tau\vee
1}\right]\right)+\kappa_{n}+\zeta_{n,d}(\frac{c_{1}}{4})\right)-\delta$
$\displaystyle\gtrsim
1-\exp\left(-a_{2,d,k}\frac{c_{1}n}{4}\left[1\wedge\frac{\eta}{\tau\vee
1}\right]\right)-\kappa_{n}-\zeta_{n,d}(\frac{c_{1}}{4})-\delta\qed.$

###### Proof of Theorem 3.2.

To prove Theorem 3.2, it suffices to find a lower bound on $t$ such that

$\Pr\left(\lVert\tilde{\theta}-\theta\rVert\geq
t\right)\leq\Pr\left(\lVert\tilde{\theta}-\theta\rVert\geq
t\big{|}\tilde{\theta}\neq\perp\right)+\Pr\left(\tilde{\theta}=\perp\right)\leq\gamma.$

Furthermore, by assumption,
$\Pr\left(\tilde{\theta}=\perp\right)=1-\mathbb{E}\lambda(\hat{\nu},\epsilon,\delta)\leq\gamma/3$.
Thus, it suffices to find $t$ such that

$\Pr\left(\lVert\tilde{\theta}-\theta\rVert\geq
t\big{|}\tilde{\theta}\neq\perp\right)\leq 2\gamma/3.$

To this end, applying Lemma B.2, yields

$\Pr\left(\lVert\tilde{\theta}-\theta\rVert\geq
t\big{|}\tilde{\theta}\neq\perp\right)\\\
\lesssim\inf_{\begin{subarray}{c}0<s<c_{1}\tau/2-c_{3}\\\
0<r<c_{1}\tau/2-s-c_{3}\end{subarray}}\Bigg{[}\exp\left(\frac{\epsilon(c_{1}/2+2c_{2})(c_{3}+s)}{4\eta
c_{1}c_{2}}-\frac{\epsilon t}{8\eta c_{2}}+\frac{\epsilon
r}{2c_{1}\eta}+\log\frac{(2c_{2}\tau+s+c_{3})^{d}-t^{d}}{r^{d}}\right)\\\
+\zeta_{n,d}\left(s\wedge c_{3}\wedge c_{1}/2\right)\Bigg{]}.$ (B.7)

We first show that

$\inf_{\begin{subarray}{c}0<s<\frac{c_{1}\tau}{2}-c_{3}\\\
0<r<\frac{c_{1}\tau}{2}-s-c_{3}\end{subarray}}\Bigg{[}\exp\left(\frac{\epsilon(\frac{c_{1}}{2}+2c_{2})(c_{3}+s)}{4\eta
c_{1}c_{2}}-\frac{\epsilon t}{8\eta c_{2}}+\frac{\epsilon
r}{2c_{1}\eta}+\log\frac{(2c_{2}\tau+s+c_{3})^{d}-t^{d}}{r^{d}}\right)\Bigg{]}\leq\frac{\gamma}{3}.$
(B.8)

To this end, using the fact that $c_{1}<c_{2}$, for any $s,r>0$, we have that

$\displaystyle\frac{(c_{1}/2+2c_{2})(c_{3}+s)}{4c_{1}c_{2}}-\frac{t}{8c_{2}}+\frac{r}{2c_{1}}$
$\displaystyle\leq\frac{5(c_{3}+s)}{8c_{1}}-\frac{t}{8c_{2}}+\frac{r}{2c_{1}}=\frac{5(c_{3}+s)+4r-tc_{1}/c_{2}}{8c_{1}}.$

Next, for some $k_{r},k_{s}>0$, take $r=tc_{1}/(k_{r}c_{2})$ and $s=r/k_{s}$.
Then

$\displaystyle\frac{5(c_{3}+s)+4r-tc_{1}/c_{2}}{8c_{1}}$
$\displaystyle=\frac{(5+4k_{s})tc_{1}/(k_{r}c_{2}k_{s})-tc_{1}/c_{2}+5c_{3}}{8c_{1}}=\frac{(5+4k_{s}-k_{r}k_{s})t}{8c_{2}k_{r}k_{s}}+\frac{5c_{3}}{8c_{1}}.$

In order to apply this result to (B.8), it must be the case that
$0<s<c_{1}\tau/2-c_{3}$ and $0<r<c_{1}\tau/2-s-c_{3}$. Note that
$r<c_{1}\tau/2-s-c_{3}\implies r+s<c_{1}\tau/2-c_{3}\implies
s<c_{1}\tau/2-c_{3}$, so it suffices to consider $s>0$, and
$0<r<c_{1}\tau/2-s-c_{3}$. First, observe that $s,r>0$ always holds. Next,
simplifying the second bound yields

$\displaystyle r<c_{1}\tau/2-s-c_{3}$ $\displaystyle\implies
r+s<c_{1}\tau/2-c_{3}$
$\displaystyle\implies\frac{tc_{1}}{k_{r}c_{2}}(1+k_{s}^{-1})<c_{1}\tau/2-c_{3}$
$\displaystyle\implies
t<\frac{k_{r}c_{2}\tau-2k_{r}c_{2}c_{3}/c_{1}}{2(1+k_{s}^{-1})}.$

Assuming that this bound on $t$ holds, then

$\exp\left(\epsilon\frac{(c_{1}/2+2c_{2})(c_{3}+s)}{4\eta
c_{1}c_{2}}-\frac{\epsilon t}{8\eta c_{2}}+\frac{\epsilon
r}{2c_{1}\eta}+\log\frac{(2c_{2}\tau+s+c_{3})^{d}-t^{d}}{r^{d}}\right)\\\
\leq\exp\left(\left[\frac{5+4k_{s}-k_{r}k_{s}}{8k_{r}k_{s}}\right]\frac{t\epsilon}{c_{2}\eta}+\log\frac{(2c_{2}\tau+s+c_{3})^{d}-t^{d}}{r^{d}}+\frac{5c_{3}}{8c_{1}}\right).$
(B.9)

We next simplify the logarithmic term. First suppose that
$r=tc_{1}/(k_{r}c_{2})$, then,

$\displaystyle\log\frac{(2c_{2}\tau+s+c_{3})^{d}-t^{d}}{r^{d}}$
$\displaystyle=\log\frac{(2c_{2}\tau+tc_{1}/k_{r}c_{2}+c_{3})^{d}-t^{d}}{(tc_{1}/k_{r}c_{2})^{d}}$
$\displaystyle=d\log\frac{k_{r}c_{2}}{c_{1}}+\log\frac{(2c_{2}\tau+tc_{1}/k_{r}c_{2}+c_{3})^{d}-t^{d}}{t^{d}}$
$\displaystyle\leq
d\log\frac{k_{r}c_{2}}{c_{1}}+d\log\frac{2c_{2}\tau+tc_{1}/k_{r}c_{2}+c_{3}}{t}$
$\displaystyle=d\log\frac{k_{r}c_{2}}{c_{1}}+d\log\left(\frac{2c_{2}\tau+c_{3}}{t}+\frac{c_{1}}{k_{r}c_{2}}\right)$
$\displaystyle=d\log\left(\frac{2k_{r}c_{2}^{2}\tau+c_{3}k_{r}c_{2}}{tc_{1}}+1\right).$
(B.10)

Now, from Lemma B.2, if $t\geq 2c_{2}\tau+s+c_{3}$, then
$\Pr\left(\lVert\tilde{\theta}-\theta\rVert\geq
t\big{|}\tilde{\theta}\neq\perp\right)=0$ and so we consider
$t<2c_{2}\tau+s+c_{3}$. Based on the assumed values for $r$ and $s$ this gives

$t<2c_{2}\tau+\frac{tc_{1}}{k_{s}k_{r}c_{2}}+c_{3}\implies
t<\frac{2k_{s}k_{r}\tau
c_{2}^{2}+c_{3}k_{s}k_{r}c_{2}}{k_{r}k_{s}c_{2}-c_{1}},$

whenever $k_{r}k_{s}c_{2}-c_{1}>0$. This holds trivially for any
$k_{r}k_{s}\geq 1$. In order to ensure that the bounds discussed holds, we
require that this upper bound on $t$ is less than the previous upper bound on
$t$ to account for all values of $t$. Thus, using the fact that
$k_{r}k_{s}\geq 1$, we have that

$\displaystyle\frac{2k_{s}k_{r}\tau
c_{2}^{2}+c_{3}k_{s}k_{r}c_{2}}{k_{r}k_{s}c_{2}-c_{1}}\leq\frac{k_{r}c_{2}\tau-2k_{r}c_{2}c_{3}/c_{1}}{2(1+k_{s}^{-1})},$

whenever,

$\displaystyle\frac{2k_{s}k_{r}\tau
c_{2}^{2}+c_{3}k_{s}k_{r}c_{2}}{k_{r}k_{s}c_{2}-c_{1}}\leq\frac{k_{r}c_{2}\tau-2k_{r}c_{2}c_{3}/c_{1}}{2(1+k_{s}^{-1})}$
$\displaystyle\implies\frac{2k_{s}\tau
c_{2}+c_{3}k_{s}}{k_{r}k_{s}c_{2}-c_{1}}\leq\frac{\tau-2c_{3}/c_{1}}{2(1+k_{s}^{-1})}$
$\displaystyle\implies\frac{2(k_{s}+1)\tau
c_{2}+c_{3}(k_{s}+1)}{k_{r}k_{s}c_{2}-c_{1}}+\frac{c_{3}}{c_{1}}\leq\tau/2$
$\displaystyle\implies\frac{c_{3}(k_{s}+1)}{k_{r}k_{s}c_{2}-c_{1}}+\frac{c_{3}}{c_{1}}\leq\tau\frac{k_{r}k_{s}c_{2}-c_{1}-4(k_{s}+1)c_{2}}{2(k_{r}k_{s}c_{2}-c_{1})}$
$\displaystyle\implies\tau\geq\frac{2(k_{r}k_{s}c_{2}-c_{1})}{k_{r}k_{s}c_{2}-c_{1}-4(k_{s}+1)c_{2}}\left(\frac{c_{3}(k_{s}+1)}{k_{r}k_{s}c_{2}-c_{1}}+\frac{c_{3}}{c_{1}}\right).$

Now, say we take $k_{s}=1$ and $k_{r}=10$, then

$\displaystyle\tau\geq\frac{20-2(c_{1}/c_{2})}{2-(c_{1}/c_{2})}\left(\frac{2c_{3}}{10c_{2}-c_{1}}+\frac{c_{3}}{c_{1}}\right),$

for which we can simplify this to the requirement that

$\displaystyle\tau\geq
20\left(\frac{2c_{3}}{10c_{2}-c_{1}}+\frac{c_{3}}{c_{1}}\right),$

Thus, for this choice of $r$ and $s$, (B.9) becomes

$\exp\left(\frac{\epsilon(c_{1}/2+2c_{2})(c_{3}+s)}{4\eta
c_{1}c_{2}}-\frac{\epsilon t}{8\eta c_{2}}+\frac{\epsilon
r}{2c_{1}\eta}+\log\frac{(2c_{2}\tau+s+c_{3})^{d}-t^{d}}{r^{d}}+\frac{5c_{3}}{8c_{1}}\right)\\\
\leq\exp\left(\left[\frac{5+4k_{s}-k_{r}k_{s}}{8k_{r}k_{s}}\right]\frac{t\epsilon}{c_{2}\eta}+d\log\left(\frac{2k_{r}c_{2}^{2}\tau}{tc_{1}}+1\right)+\frac{5c_{3}}{8c_{1}}\right).$

As a result, the above argumentation gives consideration of

$t<\frac{k_{r}c_{2}\tau-2k_{r}c_{2}c_{3}/c_{1}}{2(1+k_{s}^{-1})}.$ (B.11)

Using the derived upper bound, for $t>1/n$,

$\exp\left(\left[\frac{5+4k_{s}-k_{r}k_{s}}{8k_{r}k_{s}}\right]\frac{t\epsilon}{c_{2}\eta}+d\log\left(\frac{2k_{r}c_{2}^{2}\tau}{tc_{1}}+1\right)+\frac{5c_{3}}{8c_{1}}\right)\\\
\leq\exp\left(\left[\frac{5+4k_{s}-k_{r}k_{s}}{8k_{r}k_{s}}\right]\frac{t\epsilon}{c_{2}\eta}+d\log\left(\frac{2nk_{r}c_{2}^{2}\tau}{c_{1}}+1\right)+\frac{5c_{3}}{8c_{1}}\right).$

Bounding this above by $\gamma/3$ yields

$\displaystyle\exp\left(\left[\frac{5+4k_{s}-k_{r}k_{s}}{8k_{r}k_{s}}\right]\frac{t\epsilon}{c_{2}\eta}+d\log\left(\frac{2nk_{r}c_{2}^{2}\tau}{c_{1}}+1\right)\right)\leq\frac{\gamma}{3}\exp\left(-\frac{5c_{3}}{8c_{1}}\right)$
$\displaystyle\implies\left[\frac{k_{r}k_{s}-5-4k_{s}}{8k_{r}k_{s}}\right]\frac{t\epsilon}{c_{2}\eta}\geq-\log\left(\frac{\gamma}{3}\exp\left(-\frac{5c_{3}}{8c_{1}}\right)\left(\frac{2nk_{r}c_{2}^{2}\tau}{c_{1}}+1\right)^{-d}\right)$
$\displaystyle\implies t>\frac{\eta
c_{2}}{\epsilon}\left[\frac{8k_{r}k_{s}}{k_{r}k_{s}-5-4k_{s}}\right]\log\left(\frac{3}{\gamma}\exp\left(\frac{5c_{3}}{8c_{1}}\right)\left(\frac{2nk_{r}c_{2}^{2}\tau}{c_{1}}+1\right)^{d}\right)$
$\displaystyle\implies t>80\frac{\eta
c_{2}}{\epsilon}\log\left(\frac{3}{\gamma}\exp\left(\frac{5c_{3}}{8c_{1}}\right)\left(\frac{20nc_{2}^{2}\tau}{c_{1}}+1\right)^{d}\right)$

Therefore, this reduces to

$\displaystyle t\gtrsim\frac{\eta c_{2}}{\epsilon}\left[\log(1/\gamma)\vee
d\log\left(\frac{20c_{2}^{2}n\tau}{c_{1}}+1\right)\vee c_{3}/c_{1}\right]\vee
1/n.$

Next we bound $\zeta_{n,d}(s\wedge c_{3}\wedge c_{1}/2)\leq\gamma/3$. By
assumption, $\gamma>3\zeta_{n,d}(c_{1}/2\wedge c_{3})$, and so we consider
only $\zeta_{n,d}(s)$ for $s<c_{1}/2\wedge c_{3}$. To this end, using the fact
that $\zeta_{n,d}$ are non-increasing, we have that

$\zeta_{n,d}(s)\leq\gamma/3\implies
t\gtrsim\frac{c_{2}}{c_{1}}\zeta_{n,d}^{-1}(\gamma/3).$

This completes the proof. ∎

######  Lemma B.2.

If Conditions 2 and 3 hold, then for all $\eta,\epsilon,\delta>0$, $t>0$, and
$n,d\geq 1$ then

$\Pr\left(\lVert\tilde{\theta}-\theta\rVert\geq
t\big{|}\tilde{\theta}\neq\perp\right)\\\
\lesssim\inf_{\begin{subarray}{c}0<s<c_{1}\tau/2-c_{3}\\\
0<r<c_{1}\tau/2-s-c_{3}\end{subarray}}\Bigg{[}\exp\left(\epsilon\frac{(c_{1}/2+2c_{2})(c_{3}+s)}{4\eta
c_{1}c_{2}}-\frac{\epsilon t}{8\eta c_{2}}+\frac{\epsilon
r}{2c_{1}\eta}+\log\frac{(2c_{2}\tau+s+c_{3})^{d}-t^{d}}{r^{d}}\right)\\\
+\zeta_{n,d}\left(s\wedge c_{3}\wedge c_{1}/2\right)\Bigg{]}.$

###### Proof of Lemma B.2.

Let $\beta=\epsilon/4\eta$ and define the events $E_{6,s}=\\{S_{n}(\mu)\leq
s\\}$ and

$E_{7}=\left\\{\inf_{u\in\mathbb{S}^{d-1}}\sigma(\hat{\nu}_{u})\geq
c_{1}/2\right\\}\cap\left\\{\sup_{u\in\mathbb{S}^{d-1}}\sigma(\hat{\nu}_{u})\leq
2c_{2}\right\\}\cap\left\\{\hat{\alpha}_{\mu}\leq 4c_{3}\right\\}.$

Condition 2 directly gives that
$\Pr\left(E_{6,s}^{c}\right)\lesssim\zeta_{n,d}(s)$. Using this, the
identities established in (B.2), (B.3), and (B.4), and noting that $c_{1}\leq
c_{2}$, yields that for all $s\geq 0$, we have

$\Pr\left((E_{7}\cap E_{6,s})^{c}\right)\lesssim\zeta_{n,d}(s\wedge
c_{3}\wedge c_{1}/2).$ (B.12)

Next, condition on $E_{7}\cap E_{6,s}$. For any $\lVert x-\theta\rVert\geq t$,

$\displaystyle O(x,\hat{\nu})$
$\displaystyle=\sup_{u\in\mathbb{S}^{d-1}}\frac{x^{\top}u-\theta^{\top}u+\theta^{\top}u-\hat{\mu}_{u}}{\sigma(\hat{\nu}_{u})}$
$\displaystyle\geq\frac{\sup_{u\in\mathbb{S}^{d-1}}(x-\theta)^{\top}u-\sup_{u\in\mathbb{S}^{d-1}}|\hat{\mu}_{u}-\theta^{\top}u|}{\sup_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}}$
$\displaystyle=\frac{\lVert
x-\theta\rVert-\sup_{u\in\mathbb{S}^{d-1}}|\hat{\mu}_{u}-\mu_{u}+\mu_{u}-\theta^{\top}u|}{\sup_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}}$
$\displaystyle\geq\frac{\lVert
x-\theta\rVert-\sup_{u\in\mathbb{S}^{d-1}}|\hat{\mu}_{u}-\mu_{u}|-\sup_{u\in\mathbb{S}^{d-1}}|\mu_{u}-\theta^{\top}u|}{\sup_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}}$
$\displaystyle\geq\frac{t-c_{3}-s}{2c_{2}}.$ (B.13)

The last inequality relies on $E_{6,s}$ and Condition 3. A similar argument
shows that, for any $r>0$ and $x\in\mathbb{R}^{d}$ such that $\lVert
x-\theta\rVert\leq r$,

$\displaystyle O(x,\hat{\nu})$
$\displaystyle=\sup_{u\in\mathbb{S}^{d-1}}\frac{x^{\top}u-\theta^{\top}u+\theta^{\top}u-\hat{\mu}_{u}}{\sigma(\hat{\nu}_{u})}$
$\displaystyle\leq\frac{\sup_{u\in\mathbb{S}^{d-1}}(x^{\top}u-\theta^{\top}u)+\sup_{u\in\mathbb{S}^{d-1}}(\theta^{\top}u-\hat{\mu}_{u})}{\inf_{u\in\mathbb{S}^{d-1}}\sigma(\hat{\nu}_{u})}$
$\displaystyle\leq\frac{r+\sup_{u\in\mathbb{S}^{d-1}}|\theta^{\top}u-\mu_{u}|+\sup_{u\in\mathbb{S}^{d-1}}|\mu_{u}-\hat{\mu}_{u}|}{c_{1}/2}$
$\displaystyle\leq\frac{r+c_{3}+s}{c_{1}/2}.$ (B.14)

Therefore, taking $B_{r}(x)$ to be the ball of radius $r$ centered on $x$,
then

$B_{c_{1}\tau/2-s-c_{3}}(\theta)\subset A_{\tau,\hat{\nu}}=\\{x\mid
O(x,\hat{\nu})<\tau\\}\subset B_{2c_{2}\tau+s+c_{3}}(\theta).$ (B.15)

Here, the first inclusion follows from (B.14) and the second from (B.13).

Next, note that by definition

$\Pr\left(\lVert\tilde{\theta}-\theta\rVert\geq t|E_{7}\cap
E_{6,s}\right)=\frac{\int_{B_{t}^{c}(\theta)\cap
A_{\tau,\hat{\nu}}}\exp{\left(-\beta
O(x,\hat{\nu})\right)}dx}{\int_{A_{\tau,\hat{\nu}}}\exp{\left(-\beta
O(x,\hat{\nu})\right)}dx}.$

Moreover, if $t\geq 2c_{2}\tau+s+c_{3}$, (B.15) indicates that
$B_{t}^{c}(\theta)\cap A_{\tau,\hat{\nu}}=\emptyset$ and so

$\int_{B_{t}^{c}(\theta)\cap A_{\tau,\hat{\nu}}}\exp{\left(-\beta
O(x,\hat{\nu})\right)}dx=0.$

As such, we restrict $t<2c_{2}\tau+s+c_{3}$. Under this restriction, applying
(B.13) we find that

$\displaystyle\int_{B_{t}^{c}(\theta)\cap A_{\tau,\hat{\nu}}}\exp{\left(-\beta
O(x,\hat{\nu})\right)}dx$ $\displaystyle\leq\int_{t\leq\lVert
x-\theta\rVert\leq 2c_{2}\tau+s+c_{3}}\exp{\left(-\beta
O(x,\hat{\nu})\right)}dx$ $\displaystyle\leq\int_{t\leq\lVert
x-\theta\rVert\leq
2c_{2}\tau+s+c_{3}}\exp{\left(\frac{-\beta(t-c_{3}-s)}{2c_{2}}\right)}dx$
$\displaystyle=\exp{\left(\frac{-\beta(t-c_{3}-s)}{2c_{2}}\right)}\operatorname{vol}(\\{t\leq\lVert
x\rVert\leq 2c_{2}\tau+s+c_{3}\\}).$

Similarly, an application of (B.14) gives

$\displaystyle\int_{A_{\tau,\hat{\nu}}}\exp{\left(-\beta
O(x,\hat{\nu})\right)}dx$ $\displaystyle\geq\sup_{0<r\leq
c_{1}\tau/2-s-c_{3}}\int_{B_{r}(\theta)}\exp{\left(-\beta
O(x,\hat{\nu})\right)}dx$ $\displaystyle\geq\sup_{0<r\leq
c_{1}\tau/2-s-c_{3}}\int_{B_{r}(\theta)}\exp{\left(\frac{-\beta(r+c_{3}+s)}{c_{1}/2}\right)}dx$
$\displaystyle\geq\sup_{0<r\leq
c_{1}\tau/2-s-c_{3}}\exp{\left(\frac{-\beta(r+c_{3}+s)}{c_{1}/2}\right)}\operatorname{vol}(B_{r}(\theta)).$

Combining these two bounds gives

$\displaystyle\Pr\left(\lVert\tilde{\theta}-\theta\rVert\geq t|E_{7}\cap
E_{6,s}\right)$
$\displaystyle\leq\frac{\exp{\left(\frac{-\beta(t-c_{3}-s)}{2c_{2}}\right)}\operatorname{vol}(\\{t\leq\lVert
x\rVert\leq 2c_{2}\tau+s+c_{3}\\})}{\sup_{0<r\leq
c_{1}\tau/2-s-c_{3}}\exp{\left(\frac{-\beta(r+c_{3}+s)}{c_{1}/2}\right)}\operatorname{vol}(B_{r}(\theta))}$
$\displaystyle=\inf_{0<r\leq
c_{1}\tau/2-s-c_{3}}\frac{\exp{\left(\frac{-\beta(t-c_{3}-s)}{2c_{2}}\right)}\operatorname{vol}(B_{t}^{c}(0)\cap
B_{2c_{2}\tau+s+c_{3}}(0))}{\exp{\left(\frac{-\beta(r+c_{3}+s)}{c_{1}/2}\right)}\operatorname{vol}(B_{r}(\theta))}$
$\displaystyle\lesssim\inf_{0<r\leq
c_{1}\tau/2-s-c_{3}}\exp{\left(-\beta\frac{c_{1}/2(t-c_{3}-s)-2c_{2}(r+c_{3}+s)}{c_{2}c_{1}}\right)}\frac{(2c_{2}\tau+s+c_{3})^{d}-t^{d}}{r^{d}}$
$\displaystyle=\inf_{0<r\leq
c_{1}\tau/2-s-c_{3}}\exp{\left(\beta\left(\frac{(c_{1}/2+2c_{2})(c_{3}+s)}{c_{1}c_{2}}-\frac{t}{2c_{2}}+\frac{2r}{c_{1}}\right)\right)}\frac{(2c_{2}\tau+s+c_{3})^{d}-t^{d}}{r^{d}}.$

This bound holds for all $0<s<c_{1}\tau/2-c_{3}$, and so we can take the least
upper bound on the range. Combining this and re-writing the expression gives

$\Pr\left(\lVert\tilde{\theta}-\theta\rVert\geq t|E_{7}\cap
E_{6,s}\right)\lesssim\inf_{\begin{subarray}{c}0<r\leq c_{1}\tau/2-s-c_{3}\\\
0<s<c_{1}\tau/2-c_{3}\end{subarray}}\exp\left(\beta\left(\frac{(c_{1}/2+2c_{2})(c_{3}+s)}{c_{1}c_{2}}-\frac{t}{2c_{2}}+\frac{2r}{c_{1}}\right)\right.\\\
\left.+\log\left(\frac{(2c_{2}\tau+s+c_{3})^{d}-t^{d}}{r^{d}}\right)\right).$

Since $\Pr\left(\lVert\tilde{\theta}-\theta\rVert\geq
t\right)\leq\Pr\left(\lVert\tilde{\theta}-\theta\rVert\geq t|E_{7}\cap
E_{6,s}\right)+P((E_{7}\cap E_{6,s})^{c})$, combining this result with (B.12)
gives the desired result. ∎

######  Lemma B.3.

For all $\tau>0$, $n,d\geq 1$, $\hat{\nu}\in\widehat{\mathcal{M}}(n,d)$ and
$k\in[n]$

$\sup_{\begin{subarray}{c}\tilde{\nu}\in\widetilde{\mathcal{M}}_{1}(\hat{\nu},k)\\\
x\in A_{\tau,\tilde{\nu}}\cup
A_{\tau,\hat{\nu}}\end{subarray}}|O(x,\hat{\nu})-O(x,\tilde{\nu})|\leq\frac{\tau\tilde{S}_{n,k}(\sigma)+\tilde{S}_{n,k}(\mu)}{\inf_{u\in\mathbb{S}^{d-1}}b_{k,u}^{-}}\coloneqq\Delta_{k}.$
(B.16)

###### Proof.

We use the fact that

$\sup_{\begin{subarray}{c}\tilde{\nu}\in\widetilde{\mathcal{M}}_{1}(\hat{\nu},k)\\\
x\in A_{\tau,\tilde{\nu}}\cup
A_{\tau,\hat{\nu}}\end{subarray}}|O(x,\hat{\nu})-O(x,\tilde{\nu})|\leq\sup_{\begin{subarray}{c}\tilde{\nu}\in\widetilde{\mathcal{M}}_{1}(\hat{\nu},k)\\\
u\in\mathbb{S}^{d-1}\\\ x\in A_{\tau,\tilde{\nu}}\cup
A_{\tau,\hat{\nu}}\end{subarray}}|O_{u}(x,\hat{\nu})-O_{u}(x,\tilde{\nu})|,$

and bound the right-hand side. Observe that for all $\tau>0$ and all
$\tilde{\nu}\in\widetilde{\mathcal{M}}_{1}(\hat{\nu},k)$ it holds that

$\displaystyle\sup_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\ x\in
A_{\tau,\hat{\nu}}\end{subarray}}|O_{u}(x,\hat{\nu})-O_{u}(x,\tilde{\nu})|$
$\displaystyle=\sup_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\ x\in
A_{\tau,\hat{\nu}}\end{subarray}}\left|\frac{x^{\top}u-\hat{\mu}_{u}}{\hat{\sigma}_{u}}-\frac{x^{\top}u-\mu(\tilde{\nu}_{u})}{\sigma(\tilde{\nu}_{u})}\right|$
$\displaystyle\leq\sup_{u\in\mathbb{S}^{d-1}}\frac{1}{\hat{\sigma}_{u}\sigma(\tilde{\nu}_{u})}\left(\left(\sup_{x\in
A_{\tau,\tilde{\nu}}}|x^{\top}u-\hat{\mu}_{u}|\right)\tilde{S}_{n,k}(\sigma)+\sigma(\hat{\nu}_{u})\tilde{S}_{n,k}(\mu)\right)$
$\displaystyle\leq\frac{\tau\tilde{S}_{n,k}(\sigma)+\tilde{S}_{n,k}(\mu)}{\inf_{u\in\mathbb{S}^{d-1}}b^{-}_{k,u}}.$

Using the same logic, for all $\tau>0$ and all
$\tilde{\nu}\in\widetilde{\mathcal{M}}_{1}(\hat{\nu},k)$ we can write:

$\displaystyle\sup_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\ x\in
A_{\tau,\tilde{\nu}}\end{subarray}}|O_{u}(x,\hat{\nu})-O_{u}(x,\tilde{\nu})|$
$\displaystyle\leq\frac{\tau\tilde{S}_{n,k}(\sigma)+\tilde{S}_{n,k}(\mu)}{\inf_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}}\leq\frac{\tau\tilde{S}_{n,k}(\sigma)+\tilde{S}_{n,k}(\mu)}{\inf_{u\in\mathbb{S}^{d-1}}b^{-}_{k,u}}.$

Combining these two results yields that, for all $\tau>0$ and all
$\tilde{\nu}\in\widetilde{\mathcal{M}}_{1}(\hat{\nu},k)$, it holds that

$\sup_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\ x\in
A_{\tau,\tilde{\nu}}\cup
A_{\tau,\hat{\nu}}\end{subarray}}|O_{u}(x,\hat{\nu})-O_{u}(x,\tilde{\nu})|\leq\frac{\tau\tilde{S}_{n,k}(\sigma)+\tilde{S}_{n,k}(\mu)}{\inf_{u\in\mathbb{S}^{d-1}}b_{k,u}^{-}}.\qed$

Let
$\hat{\alpha}_{\mu}=\sup_{u\in\mathbb{S}^{d-1}}\hat{\mu}_{u}-\inf_{u\in\mathbb{S}^{d-1}}\hat{\mu}_{u}$.

######  Lemma B.4.

For $\phi=O$, and all $\hat{\nu}\in\widehat{\mathcal{M}}_{1}(n,d)$ and
$\tau,\eta,y>0$ such that
$\inf_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau-y-2\eta)-\hat{\alpha}_{\mu}>0$,
it holds that

$\frac{\operatorname{vol}(A_{\tau+2\eta,\hat{\nu}}\cap
A^{c}_{\tau-2\eta,\hat{\nu}})}{\operatorname{vol}(A_{\tau-y-2\eta,\hat{\nu}})}\leq\left(\frac{\sup_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau+2\eta)+\hat{\alpha}_{\mu}}{\inf_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau-y-2\eta)-\hat{\alpha}_{\mu}}\right)^{d}-\left(\frac{\inf_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau-2\eta)-\hat{\alpha}_{\mu}}{\inf_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau-y-2\eta)-\hat{\alpha}_{\mu}}\right)^{d}.$

###### Proof.

Let $a(t)=\inf_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}t-\hat{\alpha}_{\mu}$ and
$b(t)=\sup_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}t+\hat{\alpha}_{\mu}$. We
first show that
$\operatorname{vol}(B_{a(t)})\leq\operatorname{vol}(A_{t,\hat{\nu}})\leq\operatorname{vol}(B_{b(t)}).$
Beginning with the upper bound, for any $z\in\mathbb{R}^{d}$,

$\displaystyle A_{t,\hat{\nu}}$
$\displaystyle=\\{x\colon\sup_{u\in\mathbb{S}^{d-1}}\frac{|x^{\top}u-\hat{\mu}_{u}|}{\hat{\sigma}_{u}}\leq
t\\}\subset\\{x\colon\sup_{u\in\mathbb{S}^{d-1}}|x^{\top}u-z^{\top}u|\leq\sup_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}t+\sup_{u\in\mathbb{S}^{d-1}}|z^{\top}u-\hat{\mu}_{u}|\\}.$

In particular, taking $z=v\hat{\mu}_{v}$ for $v\in\mathbb{S}^{d-1}$,

$\displaystyle A_{t,\hat{\nu}}$
$\displaystyle\subset\\{|x^{\top}u-\hat{\mu}_{v}v^{\top}u|\leq
b(t)\\}=\\{x\colon\lVert x-\hat{\mu}_{v}v\rVert\leq
b(t)\\}=B_{b(t)}(\hat{\mu}_{v}v).$

It follows that
$\operatorname{vol}(A_{t,\hat{\nu}})\leq\operatorname{vol}(B_{b(t)}).$ Next,
we show the analogous lower bound. To this end, note that for any
$z\in\mathbb{R}^{d}$

$\displaystyle A_{t,\hat{\nu}}$
$\displaystyle=\\{x\colon\sup_{u\in\mathbb{S}^{d-1}}\frac{|x^{\top}u-\hat{\mu}_{u}|}{\hat{\sigma}_{u}}\leq
t\\}\supset\\{x\colon\sup_{u\in\mathbb{S}^{d-1}}|x^{\top}u-z^{\top}u|\leq\inf_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}t-\sup_{u\in\mathbb{S}^{d-1}}|z^{\top}u-\hat{\mu}_{u}|\\}.$

Take $z=v\hat{\mu}_{v}$, where $v\in\mathbb{S}^{d-1}$, yielding
$A_{t,\hat{\nu}}\supset\\{x\colon\lVert x-v\hat{\mu}_{v}\rVert\leq
a(t)\\}=B_{a(t)}(v\hat{\mu}_{v}).$ It follows that
$\operatorname{vol}(A_{t,\hat{\nu}})\geq\operatorname{vol}(B_{a(t)}).$ Now, we
apply the upper and lower bounds, in conjunction with the assumption that
$a(\tau-y-2\eta)=\inf_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau-y-2\eta)-\hat{\alpha}_{\mu}>0$,
which results in

$\displaystyle\frac{\operatorname{vol}(A_{\tau+2\eta,\hat{\nu}}\cap
A^{c}_{\tau-2\eta,\hat{\nu}})}{\operatorname{vol}(A_{\tau-y-2\eta,\hat{\nu}})}$
$\displaystyle\leq\frac{\operatorname{vol}(B_{b(\tau+2\eta)}\cap
B^{c}_{a(\tau-2\eta)})}{\operatorname{vol}(B_{a(\tau-y-2\eta)})}$
$\displaystyle\leq\left(\frac{\sup_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau+2\eta)+\hat{\alpha}_{\mu}}{\inf_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau-y-2\eta)-\hat{\alpha}_{\mu}}\right)^{d}$
$\displaystyle\hskip
122.85876pt-\left(\frac{\inf_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau-2\eta)-\hat{\alpha}_{\mu}}{\inf_{u\in\mathbb{S}^{d-1}}\hat{\sigma}_{u}(\tau-y-2\eta)-\hat{\alpha}_{\mu}}\right)^{d}.\qed$

##  Appendix C Proofs from Section 3.2

Let $\lambda_{t,q_{1},q_{2}}=\inf_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\
z\in(\xi_{q_{1},u}-t,\xi_{q_{2},u}+t)\end{subarray}}f_{\nu_{u}}(z)$ and
$\hat{\xi}_{q,u}=F^{-1}_{\hat{\nu}_{u}}(q)$.

######  Lemma C.1.

If $\nu$ is absolutely continuous, then for all for $0<q_{1}\leq q_{2}<1$,
$n,d\geq 1$ and $t>0$ it holds that

$\Pr\left(\sup_{u\in\mathbb{S}^{d-1}}\sup_{x\in[q_{1},q_{2}]}|\xi_{x,u}-\hat{\xi}_{x,u}|\geq
t\right)\leq\left(\frac{cn}{d}\right)^{d}e^{-2nt^{2}\lambda_{t,q_{1},q_{2}}^{2}}.$

###### Proof.

Note that

$\Pr\Big{(}\sup_{\begin{subarray}{c}x\in[q_{1},q_{2}]\\\
u\in\mathbb{S}^{d-1}\end{subarray}}|\xi_{x,u}-\hat{\xi}_{x,u}|\geq
t\Big{)}=\Pr\Big{(}\bigcup_{\begin{subarray}{c}x\in[q_{1},q_{2}]\\\
u\in\mathbb{S}^{d-1}\end{subarray}}\left(\\{\hat{\xi}_{x,u}-\xi_{x,u}\geq
t\\}\cup\\{\xi_{x,u}-\hat{\xi}_{x,u}\geq t\\}\right)\Big{)}.$ (C.1)

Furthermore, a direct consequence of the mean value theorem is that

$\displaystyle\\{\hat{\xi}_{x,u}-\xi_{x,u}\geq t\\}$ $\displaystyle=\\{x\geq
F_{\hat{\nu}_{u}}(\xi_{x,u}+t)\\}$
$\displaystyle=\\{F_{\nu_{u}}(\xi_{x,u}+t)-F_{\hat{\nu}_{u}}(\xi_{x,u}+t)\geq
F_{\nu_{u}}(\xi_{x,u}+t)-x\\}$
$\displaystyle\subset\\{\sup_{\begin{subarray}{c}y\in[0,1]\\\
u\in\mathbb{S}^{d-1}\end{subarray}}|F_{\nu_{u}}(y)-F_{\hat{\nu}_{u}}(y)|\geq
t\inf_{\begin{subarray}{c}z\in[q_{1},q_{2}]\\\
u\in\mathbb{S}^{d-1}\end{subarray}}f_{\nu_{u}}(\xi_{z,u}+t)\\}.$

A similar argument yields

$\displaystyle\\{\xi_{x,u}-\hat{\xi}_{x,u}\geq t\\}$
$\displaystyle\subset\\{\sup_{\begin{subarray}{c}y\in[0,1]\\\
u\in\mathbb{S}^{d-1}\end{subarray}}|F_{\nu_{u}}(y)-F_{\hat{\nu}_{u}}(y)|\geq
t\inf_{\begin{subarray}{c}z\in[q_{1},q_{2}]\\\
u\in\mathbb{S}^{d-1}\end{subarray}}f_{\nu_{u}}(\xi_{z,u}-t)\\}.$

Combining these two set inequalities with (C.1) and applying Talagrand’s
inequality [23] results in

$\displaystyle\Pr\Big{(}\sup_{\begin{subarray}{c}x\in[q_{1},q_{2}]\\\
u\in\mathbb{S}^{d-1}\end{subarray}}|\xi_{x,u}-\hat{\xi}_{x,u}|\geq t\Big{)}$
$\displaystyle\leq\Pr\Big{(}\sup_{\begin{subarray}{c}y\in[0,1]\\\
u\in\mathbb{S}^{d-1}\end{subarray}}|F_{\nu_{u}}(y)-F_{\hat{\nu}_{u}}(y)|\geq
t\inf_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\
z\in(\xi_{q_{1},u}-t,\xi_{q_{2},u}+t)\end{subarray}}f_{\nu_{u}}(z)\Big{)}$
$\displaystyle=\Pr\Big{(}\sup_{\begin{subarray}{c}y\in[0,1]\\\
u\in\mathbb{S}^{d-1}\end{subarray}}|F_{\nu_{u}}(y)-F_{\hat{\nu}_{u}}(y)|\geq
t\lambda_{t,q_{1},q_{2}}\Big{)}$
$\displaystyle\leq\left(\frac{cn}{d}\right)^{d}e^{-2nt^{2}\lambda_{t,q_{1},q_{2}}^{2}}.\qed$

For $\mathbb{X}_{n}\in\mathbf{D}_{n\times d}$ and $u\in\mathbb{S}^{d-1}$, let
$(X^{\top}u)_{(k)}$ denote the $k$th order statistic of the sample
$X_{1}^{\top}u,\ldots,X_{n}^{\top}u$.

######  Lemma C.2.

If, for a given $0<q\leq 1/2$, Condition 4 holds for $(q,\nu,k)$, then there
exists a universal constant $c>0$ such that for all $d,n\geq 1$ and all $C>0$,
it holds that

$\Pr\Big{(}\sup_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\
p\in[q,1-q-k/n]\end{subarray}}(X^{\top}u)_{(\lfloor
pn\rfloor+k)}-(X^{\top}u)_{(\lfloor pn\rfloor)}\geq
C/n\Big{)}\lesssim\exp\left(-nr^{2}M^{2}+d\log(cn/d)\right)\\\
+\exp\left(-\frac{3MC}{4k}+d\log 9+\log n(1-2q+1/n)\right).$

###### Proof.

Let $m=\lfloor qn\rfloor$. Now, define

$E_{8}=\bigcap_{u\in\mathbb{S}^{d-1}}\left\\{\xi_{q,u}-r\leq(X^{\top}u)_{(m)}\leq(X^{\top}u)_{(m+k)}\leq\xi_{q,u}+r\right\\}.$

Now, noting that, for a given $j\in[n]$,
$(X^{\top}u)_{(j)}=\hat{\xi}_{j/n,u}$, applying Lemma C.1 with $q_{1}=q$,
$q_{2}=q+k/n$ and $t=r$ in conjunction with Condition 4 yields

$\Pr\left(E_{8}^{c}\right)\lesssim\exp\left(-nr^{2}\lambda_{r,q,q+k/n}^{2}+d\log(cn/d)\right)\leq\exp\left(-nr^{2}M^{2}+d\log(cn/d)\right).$
(C.2)

Now, let

$E_{9}=\left\\{\max_{m\leq
j<n-m}\sup_{u\in\mathbb{S}^{d-1}}\left[(X^{\top}u)_{(j+1)}-(X^{\top}u)_{(j)}\right]\geq\frac{C}{kn}\right\\},$

and note that

$\Pr\Big{(}\ \sup_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\
p\in[q,1-q-k/n]\end{subarray}}(X^{\top}u)_{(\lfloor
pn\rfloor+k)}-(X^{\top}u)_{(\lfloor
pn\rfloor)}\geq\frac{C}{n}\Big{)}\leq\Pr\left(E_{9}|E_{8}\right)+\Pr\left(E_{8}^{c}\right).$
(C.3)

We now consider the event $E_{9}$. Recall that the set
$\mathcal{N}_{\epsilon}$ is an $\epsilon$-net on $\mathbb{S}^{d-1}$ if for all
$u\in\mathbb{S}^{d-1}$, there exists $v\in\mathcal{N}_{\epsilon}$ such that
$\lVert u-v\rVert\leq\epsilon$. Letting $\mathcal{N}_{\epsilon}$ be an
arbitrary $\epsilon$-net on $\mathbb{S}^{d-1}$, it is straightforward (see,
e.g., [25, Lemma 4.4.1]) to show that for any $i,j\in[n]$,

$\sup_{u\in\mathbb{S}^{d-1}}|X_{i}^{\top}u-X_{j}^{\top}u|\leq\frac{1}{1-\epsilon}\sup_{u\in\mathcal{N}_{\epsilon}}|X_{i}^{\top}u-X_{j}^{\top}u|.$

Furthermore, there exists $\mathcal{N}_{1/4}$ such that
$|\mathcal{N}_{1/4}|\leq 9^{d}$ [25, see Corollary 4.2.13]. Applying these two
facts, in conjunction with two applications of subadditivity of probability
measures, yields

$\displaystyle\Pr\left(E_{8}\right)$ $\displaystyle\leq\Pr\left(\max_{m\leq
j<n-m}\sup_{u\in\mathcal{N}_{1/4}}(X^{\top}u)_{(j+1)}-(X^{\top}u)_{(j)}\geq\frac{3C}{4n}\right)$
$\displaystyle\leq 9^{d}\sup_{u\in\mathcal{N}_{1/4}}\Pr\left(\max_{m\leq
j<n-m}(X^{\top}u)_{(j+1)}-(X^{\top}u)_{(j)}\geq\frac{3C}{4n}\right)$
$\displaystyle\leq
9^{d}(n-2m+1)\sup_{\begin{subarray}{c}u\in\mathcal{N}_{1/4}\\\ m\leq
j<n-m\end{subarray}}\Pr\left((X^{\top}u)_{(j+1)}-(X^{\top}u)_{(j)}\geq\frac{3C}{4n}\right)$
$\displaystyle\coloneqq e^{d\log
9+\log(n-2m+1)}\sup_{\begin{subarray}{c}u\in\mathcal{N}_{1/4}\\\ m\leq
j<n-m\end{subarray}}\Pr\left(A_{3,u,j}\right).$ (C.4)

Now, observe that for any $m\leq j<n-m$ and $u\in\mathbb{S}^{d-1}$, using
Condition 4, together with the mean value theorem, imply that on $E_{8}$ and
$A_{3,u,j}$ it holds that

$\displaystyle\frac{F_{\nu_{u}}((X^{\top}u)_{(j+1)})-F_{\nu_{u}}((X^{\top}u)_{(j)})}{(X^{\top}u)_{(j+1)}-(X^{\top}u)_{(j)}}\geq
M\implies
F_{\nu_{u}}((X^{\top}u)_{(j+1)})-F_{\nu_{u}}((X^{\top}u)_{(j)})\geq\frac{3C}{4n}M.$
(C.5)

Let $U_{(j),u}=F_{\nu_{u}}((X^{\top}u)_{(j)})$. Now, recall that for any set
of $n$ independent standard uniform random variables $V_{1},\ldots,V_{n}$, for
any $j\in[n-1]$, it holds that
$V_{(j+1)}-V_{(j)}\stackrel{{\scriptstyle\text{d}}}{{=}}V_{(1)}$ and
$V_{(1)}\sim Beta(1,n)$ [see, e.g., 19]. These two facts, combined inequality
(C.5), results in

$\displaystyle\sup_{\begin{subarray}{c}u\in\mathcal{N}_{1/4}\\\ m\leq
j<n-m\end{subarray}}\Pr\left(A_{3,u}|E_{8}\right)$
$\displaystyle\leq\sup_{\begin{subarray}{c}u\in\mathcal{N}_{1/4}\\\ m\leq
j<n-m\end{subarray}}\Pr\left(U_{(j+1),u}-U_{(j),u}\geq 3CM/4n\right)$
$\displaystyle\leq\sup_{u\in\mathcal{N}_{1/4}}\Pr\left(U_{(1),u}\geq
3CM/4n\right)$ $\displaystyle\leq(1-(3CM/4n)\wedge 1)^{n}$ $\displaystyle\leq
e^{-3MC/4k}.$ (C.6)

Combining (C.2)–(C.6) yields

$\Pr\Big{(}\sup_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\
p\in[q,1-q-k]\end{subarray}}(X^{\top}u)_{(\lfloor
pn\rfloor+k)}-(X^{\top}u)_{(\lfloor
pn\rfloor)}\geq\frac{C}{n}\Big{)}\lesssim\exp\left(-nr^{2}M^{2}+d\log(cn/d)\right)\\\
\exp\left(-3MC/4k+d\log 9+\log(n-2m+1)\right).\qed$

######  Lemma C.3.

Let $\mu$ be the median functional. If Condition 4 holds for $(1/2,\nu,k)$,
then there exists a universal constant $c>0$ such that for all $d,n\geq 1$ and
$t>0$ it holds that

$\Pr\left(\tilde{S}_{n,k}(\mu)\geq
t\right)\lesssim\exp\left(-nr^{2}M^{2}+d\log(cn/d)\right)+\exp\left(-3MC/4k+d\log
9+\log n\right).$

###### Proof of Lemma C.3.

Observe that

$\tilde{S}_{n,k}(\mu)\leq\sup_{u\in\mathbb{S}^{d-1}}|(X^{\top}u)_{(\lfloor(n+1)/2\rfloor+k)}-(X^{\top}u)_{(\lfloor(n+1)/2\rfloor)}|.$
(C.7)

Therefore, applying Lemma C.2 with $q=1/2$ and $k=k$ gives the result. ∎

######  Lemma C.4.

Suppose that Condition 4 holds for $(q^{\prime},\nu,k)$ with $q^{\prime}<1/4$
and that there exists $q^{\prime}<q<1/4$ such that $k<n(q-q^{\prime})/2$. Then
for all $d,n\geq 1$ and $C>0$ it holds that

$\Pr\Big{(}\tilde{S}_{n,k}(\sigma)\geq
C/n\Big{)}\lesssim\exp\left(-nr^{2}M^{2}+d\log(cn/d)\right)\\\
+\exp\left(-3MC/8k+d\log 9+\log(n(1-2q^{\prime}+1/n))\right).$

###### Proof.

Let

$E_{10}=\Big{\\{}\sup_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\
p\in[q^{\prime},1-q^{\prime}-k/n]\end{subarray}}(X^{\top}u)_{(\lfloor
pn\rfloor+k)}-(X^{\top}u)_{(\lfloor pn\rfloor)}<C/2n\Big{\\}}.$

A direct application of Lemma C.2 gives that for all $u\in\mathbb{S}^{d-1}$
and $\tilde{\nu}_{u}\in\mathcal{M}(k,\hat{\nu})$,

$\Pr\left(E_{10}^{c}\right)\leq\exp\left(-3MC/8k+d\log
9+\log(n(1-2q^{\prime}+1/n))\right)\\\
+\exp\left(-nr^{2}M^{2}+d\log(cn/d)\right).$

It remains to show that on $E_{10}$, for all $u\in\mathbb{S}^{d-1}$ and
$\tilde{\nu}_{u}\in\mathcal{M}(k,\hat{\nu})$, it holds that
$\sigma(\hat{\nu}_{u})-C/n\leq\sigma(\tilde{\nu}_{u})\leq\sigma(\hat{\nu}_{u})+C/n$.
We begin by proving the upper bound. To this end, (C.7) implies that on
$E_{10}$ it holds that $\tilde{S}_{n,k}(\mu)<C/2n.$ This fact implies that

$[\hat{\mu}_{u}-\hat{\sigma}_{u},\hat{\mu}_{u}+\hat{\sigma}_{u}]\subset[\mu(\tilde{\nu}_{u})-\hat{\sigma}_{u}-C/2n,\mu(\tilde{\nu}_{u})+\hat{\sigma}_{u}+C/2n].$
(C.8)

Next, recall that, by definition, the median absolute deviation is equal to
half the length of the smallest interval which is symmetric about the median
and which contains $\lfloor(n+1)/2\rfloor$ of the observations. Therefore,
$\lfloor(n+1)/2\rfloor$ of the projected observations are contained in
$[\hat{\mu}_{u}-\hat{\sigma}_{u},\hat{\mu}_{u}+\hat{\sigma}_{u}]$.
Consequentially, (C.8) implies that on $E_{10}$, for all
$u\in\mathbb{S}^{d-1}$ and $\tilde{\nu}_{u}\in\mathcal{M}(k,\hat{\nu})$,
$\lfloor(n+1)/2\rfloor$ of the projected observations are also contained in
$[\mu(\tilde{\nu}_{u})-\hat{\sigma}_{u}-C/2n,\mu(\tilde{\nu}_{u})+\hat{\sigma}_{u}+C/2n]$.
This directly implies that for all $u\in\mathbb{S}^{d-1}$ and
$\tilde{\nu}_{u}\in\mathcal{M}(k,\hat{\nu})$, it holds that
$\sigma(\tilde{\nu}_{u})\leq\sigma(\hat{\nu}_{u})+C/2n$.

It remains to show that on $E_{10}$,
$\sigma(\hat{\nu}_{u})-C/n\leq\sigma(\tilde{\nu}_{u})$. First, by definition,
for all $u\in\mathbb{S}^{d-1}$ and
$\tilde{\nu}_{u}\in\mathcal{M}(k,\hat{\nu})$, $\lfloor(n+1)/2\rfloor-k$ of the
projected observations are contained in
$[\mu(\tilde{\nu}_{u})-\sigma(\tilde{\nu}_{u}),\mu(\tilde{\nu}_{u})+\sigma(\tilde{\nu}_{u})]$.
Next, note that for all $u\in\mathbb{S}^{d-1}$ there exists $q<p_{u}<1-q$ such
that $\hat{\sigma}_{u}=|\mu(\hat{\nu}_{u})-\hat{\xi}_{p_{u},u}|$. To see this,
take $q^{\prime}<q<1/4$, and note that by definition,

$\hat{\sigma}_{u}\leq|\hat{\xi}_{q,u}-\hat{\xi}_{1/2,u}|\vee|\hat{\xi}_{1-q,u}-\hat{\xi}_{1/2,u}|.$

(This is because $[\hat{\xi}_{q,u},\hat{\xi}_{1-q,u}]$ always contains at
least half of the observations by definition ($q<1/4$) and, therefore,
$\mu_{u}\pm|\hat{\xi}_{q,u}-\hat{\xi}_{1/2,u}|\vee|\hat{\xi}_{1-q,u}-\hat{\xi}_{1/2,u}|$
contains at least half of the observations.) Therefore, there exists
$q<p_{u}<1-q$ such that
$\hat{\sigma}_{u}=|\hat{\xi}_{1/2,u}-\hat{\xi}_{p_{u},u}|$.

Now, by assumption, $2k<n(q-q^{\prime})$, and so, for all
$u\in\mathbb{S}^{d-1}$, there exists $q^{\prime}<p_{u}<1-q^{\prime}$ such that
$\sigma(\tilde{\nu}_{u})=|\mu(\tilde{\nu}_{u})-\hat{\xi}_{p_{u},u}|$. (This is
because $\hat{\xi}_{q,u}$ is at least $2k$ observations away from
$\hat{\xi}_{q^{\prime},u}$.) Therefore, on $E_{10}$, $\lfloor(n+1)/2\rfloor$
of the observations lie within
$[\mu(\hat{\nu}_{u})-\sigma(\tilde{\nu}_{u})-C/n,\mu(\hat{\nu}_{u})+\sigma(\tilde{\nu}_{u})+C/n]$,
which immediately implies that
$\sigma(\hat{\nu}_{u})-C/n\leq\sigma(\tilde{\nu}_{u})$. ∎

######  Lemma C.5.

Let $\sigma$ be the interquartile range. If Condition 4 holds for
$(1/4,\nu,k)$, then for all $d,n\geq 1$ and $t>0$ it holds that

$\Pr\left(\tilde{S}_{n,k}(\sigma)\geq t\right)\lesssim\exp\left(-3MC/8k+d\log
9+\log(n(1/2+1/n))\right)\\\ +\exp\left(-nr^{2}M^{2}+d\log(cn/d)\right).$

###### Proof of Lemma C.5.

Observe that

$\displaystyle\tilde{S}_{n,k}(\sigma)\leq
2\sup_{u\in\mathbb{S}^{d-1}}|(X^{\top}u)_{(\lfloor(n+1)/4\rfloor+k)}-(X^{\top}u)_{(\lfloor(n+1)/4\rfloor)}|.$

Therefore, applying Lemma C.2 with $q=1/4$ and $k=k$ yields the result. ∎

##  Appendix D Proofs and related lemmas from Section 5

Let $h(A,\hat{\nu})=\int_{A}\exp(-\phi(x,{\hat{\nu})\epsilon/4\eta})dx$.

######  Lemma D.1.

For any $\hat{\nu}\in\widehat{\mathcal{M}}_{1}(n,d)$, $\tau,\epsilon>0$,
$0<\eta\leq\tau$ and $\delta\leq e^{\epsilon/2}/2$ if

$\sup_{\begin{subarray}{c}\tilde{\nu}\in\widetilde{\mathcal{M}}_{1}(\hat{\nu},1)\\\
x\in A_{\tau,\hat{\nu}}\cup
A_{\tau,\tilde{\nu}}\end{subarray}}|\phi(x,\hat{\nu})-\phi(x,\tilde{\nu})|\leq\eta,$
(D.1)

and

$\frac{h(A_{\tau-\eta,\hat{\nu}},\hat{\nu})}{h(A_{\tau+\eta,\hat{\nu}},\hat{\nu})}\geq
1-e^{-\epsilon/2}\delta/3,$ (D.2)

then
$(\operatorname{EM}_{\hat{\nu},\phi}(\cdot;\tau,\eta,\epsilon),\hat{\nu})$ is
$(\epsilon/2,\delta)$-safe.

###### Proof.

This proof is inspired by the techniques of Brown et al.,  [6]. Let
$Q=\operatorname{EM}_{\hat{\nu},\phi}(\cdot;\tau,\eta,\epsilon)$. For some
$\tilde{\nu}\in\mathcal{M}(\hat{\nu},1)$, let
$P=\operatorname{EM}_{\tilde{\nu},\phi}(\cdot;\tau,\eta,\epsilon)$. Take
$C=A_{\tau,\tilde{\nu}}\cap A_{\tau,\hat{\nu}}$ and
$E\in\mathscr{B}(\mathbb{R}^{d})$. Then,

$\displaystyle Q(E)$ $\displaystyle=Q(E\cap C)+Q(E\cap C^{c})$
$\displaystyle=\frac{Q(E\cap C)}{P(E\cap C)}P(E\cap C)+Q(E\cap
A_{\tau,\tilde{\nu}}^{c})+Q(E\cap A_{\tau,\hat{\nu}}^{c})-Q(E\cap
A_{\tau,\hat{\nu}}^{c}\cap A_{\tau,\tilde{\nu}}^{c})$
$\displaystyle\leq\frac{Q(E\cap C)}{P(E\cap C)}P(E\cap
C)+Q(A_{\tau,\tilde{\nu}}^{c})$ $\displaystyle\leq\frac{Q(E\cap C)}{P(E\cap
C)}P(E)+Q(A_{\tau,\tilde{\nu}}^{c}).$

Analogously, we have that

$\displaystyle P(E)$ $\displaystyle\leq\frac{P(E\cap C)}{Q(E\cap C)}Q(E\cap
C)+P(A_{\tau,\hat{\nu}}^{c})\leq\frac{P(E\cap C)}{Q(E\cap
C)}Q(E)+P(A_{\tau,\hat{\nu}}^{c}).$

It remains to show the following bounds:

$\displaystyle Q(A_{\tau,\tilde{\nu}}^{c}),P(A_{\tau,\hat{\nu}}^{c})$
$\displaystyle\leq\delta/3,\qquad\text{ and }\qquad\frac{Q(E\cap C)}{P(E\cap
C)},\frac{P(E\cap C)}{Q(E\cap C)}\leq e^{\epsilon/2}+2\delta/3.$

First, (D.1) implies that for $\tilde{\nu}\in\mathcal{M}(\hat{\nu},1)$, it
holds that both

$A_{\tau-\eta,\tilde{\nu}}\subset A_{\tau,\hat{\nu}}\subset
A_{\tau+\eta,\tilde{\nu}}\qquad\text{and}\qquad A_{\tau-\eta,\hat{\nu}}\subset
A_{\tau,\tilde{\nu}}\subset A_{\tau+\eta,\hat{\nu}}.$ (D.3)

In addition, noting that

$h(A,\tilde{\nu})=\int_{A}e^{-\phi(x,\tilde{\nu})}dx=\int_{A}e^{-(\phi(x,\tilde{\nu})-\phi(x,\hat{\nu}))}e^{-\phi(x,\hat{\nu})}dx,$

then (D.1) implies that for any $A\subset A_{\tau,\tilde{\nu}}\cup
A_{\tau,\hat{\nu}}$,

$e^{-\epsilon/4}h(A,\hat{\nu})\leq h(A,\tilde{\nu})\leq
e^{\epsilon/4}h(A,\hat{\nu}).$ (D.4)

Applying (D.3) and (D.4) together with (D.2) yields

$\displaystyle\frac{Q(E\cap C)}{P(E\cap C)}$ $\displaystyle\leq
e^{\epsilon/4}\frac{h(A_{\tau,\tilde{\nu}},\tilde{\nu})}{h(A_{\tau,\hat{\nu}},\hat{\nu})}\leq
e^{\epsilon/2}\frac{h(A_{\tau,\tilde{\nu}},\hat{\nu})}{h(A_{\tau,\hat{\nu}},\hat{\nu})}\leq
e^{\epsilon/2}\frac{h(A_{\tau+\eta,\hat{\nu}},\hat{\nu})}{h(A_{\tau,\hat{\nu}},\hat{\nu})}\leq
e^{\epsilon/2}(1-e^{-\epsilon/2}\delta/3)^{-1}\leq e^{\epsilon/2}+2\delta/3,$

noting that for $x\leq 1/2$, $(1-x)^{-1}\leq 1+1/x$. By an analogous argument,

$\displaystyle\frac{P(E\cap C)}{Q(E\cap C)}$ $\displaystyle\leq
e^{\epsilon/2}+2\delta/3.$

Next, applying (D.3) and (D.4) together with (D.2) yields

$\displaystyle Q(A_{\tau,\tilde{\nu}}^{c})$
$\displaystyle=1-\frac{h(A_{\tau,\tilde{\nu}}\cap
A_{\tau,\hat{\nu}},\hat{\nu})}{h(A_{\tau,\hat{\nu}},\hat{\nu})}\leq
1-\frac{h(A_{\tau-\eta,\hat{\nu}},\hat{\nu})}{h(A_{\tau,\hat{\nu}},\hat{\nu})}\leq
e^{-\epsilon/2}\delta/3\leq\delta/3.$

Similarly, we have that

$\displaystyle P(A_{\tau,\hat{\nu}}^{c})=\frac{h(A_{\tau,\tilde{\nu}}\cap
A_{\tau,\hat{\nu}}^{c},\tilde{\nu})}{h(A_{\tau,\tilde{\nu}},\tilde{\nu})}$
$\displaystyle\leq\frac{e^{\epsilon/4}h(A_{\tau,\hat{\nu}}^{c}\cap
A_{\tau,\tilde{\nu}},\hat{\nu})}{e^{-\epsilon/4}h(A_{\tau,\tilde{\nu}},\hat{\nu})}$
$\displaystyle\leq e^{\epsilon/2}\left(1-\frac{h(A_{\tau,\hat{\nu}}\cap
A_{\tau,\tilde{\nu}},\hat{\nu})}{h(A_{\tau,\tilde{\nu}},\hat{\nu})}\right)$
$\displaystyle\leq
e^{\epsilon/2}\left(1-\frac{h(A_{\tau-\eta,\hat{\nu}},\hat{\nu})}{h(A_{\tau+\eta,\hat{\nu}},\hat{\nu})}\right)$
$\displaystyle\leq
e^{\epsilon/2}\left(e^{-\epsilon/2}\delta/3\right)=\delta/3.\qed$

######  Lemma D.2.

If, for $\hat{\nu}\in\widehat{\mathcal{M}}_{1}(n,d)$, $k\in[n]$, $\epsilon>0$,
$0<\delta\leq e^{-\epsilon/2}/2$ and
$\operatorname{EM}_{\hat{\nu},\phi}=\operatorname{EM}_{\hat{\nu},\phi}(\cdot;\tau,\eta,\epsilon)$
it holds that

$\sup_{\begin{subarray}{c}\tilde{\nu}\in\widetilde{\mathcal{M}}_{1}(\hat{\nu},k)\\\
x\in A_{\tau+\eta,\hat{\nu}}\cup
A_{\tau+\eta,\tilde{\nu}}\end{subarray}}|\phi(x,\hat{\nu})-\phi(x,\tilde{\nu})|\leq\eta/2$
(D.5)

and

$\inf_{y>0}e^{-\epsilon
y/4\eta}\frac{\operatorname{vol}(A_{\tau+2\eta,\hat{\nu}}\cap
A_{\tau-2\eta,\hat{\nu}}^{c})}{\operatorname{vol}(A_{\tau-y-2\eta,\hat{\nu}})}\leq
e^{-\epsilon/4}\delta/3,$ (D.6)

then
$\operatorname{SM}(\hat{\nu},\operatorname{EM}_{\hat{\nu},\phi},\epsilon/2,\delta)\geq
k-1$.

###### Proof.

To say that
$\operatorname{SM}(\hat{\nu},\operatorname{EM}_{\hat{\nu},\phi},\epsilon/2,\delta)\geq
k-1$ is equivalent to saying that, for every
$\tilde{\nu}\in\mathcal{M}(\hat{\nu},k-1)$,
$(\operatorname{EM}_{\tilde{\nu},\phi},\tilde{\nu})$ is
$(\epsilon/2,\delta)$-safe. Using Lemma D.1 on $\tilde{\nu}$, we need only
show that (D.1) and (D.2) hold. That is

$\sup_{\begin{subarray}{c}\nu^{\prime}\in\widetilde{\mathcal{M}}_{1}(\tilde{\nu},1)\\\
x\in A_{\tau,\tilde{\nu}}\cup
A_{\tau,\nu^{\prime}}\end{subarray}}|\phi(x,\tilde{\nu})-\phi(x,\nu^{\prime})|\leq\eta,\qquad\text{and}\qquad\frac{h(A_{\tau-\eta,\tilde{\nu}},\tilde{\nu})}{h(A_{\tau+\eta,\tilde{\nu}},\tilde{\nu})}\geq
1-e^{-\epsilon/2}\delta/3.$

First, the assumption (D.5), together with the triangle inequality, implies
that, for every $v^{\prime}\in\widetilde{\mathcal{M}}_{1}(\tilde{\nu},1)$ and
$x\in A_{\tau+\eta,\tilde{\nu}}\cup A_{\tau+\eta,\nu^{\prime}}$,

$|\phi(x,\nu^{\prime})-\phi(x,\tilde{\nu})|=|\phi(x,\nu^{\prime})-\phi(x,\hat{\nu})+\phi(x,\hat{\nu})-\phi(x,\tilde{\nu})|\\\
\leq
2\sup_{\begin{subarray}{c}\tilde{\nu}\in\widetilde{\mathcal{M}}_{1}(\hat{\nu},k)\\\
x\in A_{\tau+\eta,\hat{\nu}}\cup
A_{\tau+\eta,\tilde{\nu}}\end{subarray}}|\phi(x,\hat{\nu})-\phi(x,\tilde{\nu})|\leq\eta.$

This, taken together with the fact that $A_{\tau,\nu}\subseteq
A_{\tau+\eta,\nu}$ for every $\nu$, implies that (D.1) holds.

Next, note that

$\frac{h(A_{\tau-\eta,\tilde{\nu}},\tilde{\nu})}{h(A_{\tau+\eta,\tilde{\nu}},\tilde{\nu})}=\frac{h(A_{\tau-\eta,\tilde{\nu}}\cap
A_{\tau+\eta,\tilde{\nu}},\tilde{\nu})}{h(A_{\tau+\eta,\tilde{\nu}},\tilde{\nu})}=\operatorname{EM}_{\tilde{\nu},\phi}(A_{\tau-\eta,\tilde{\nu}};\tau+\eta,\eta,\epsilon).$

As a result, (D.2) is equivalent to

$\operatorname{EM}_{\tilde{\nu},\phi}(A_{\tau-\eta,\tilde{\nu}};\tau+\eta,\eta,\epsilon)\geq
1-e^{-\epsilon/2}\delta/3\implies e^{-\epsilon/2}\delta/3\geq
1-\operatorname{EM}_{\tilde{\nu},\phi}(A_{\tau-\eta,\tilde{\nu}};\tau+\eta,\eta,\epsilon).$

Thus, we turn to proving the condition

$1-\operatorname{EM}_{\tilde{\nu},\phi}(A_{\tau-\eta,\tilde{\nu}};\tau+\eta,\eta,\epsilon)=\frac{h(A_{\tau-\eta,\tilde{\nu}}^{c}\cap
A_{\tau+\eta,\tilde{\nu}},\tilde{\nu})}{h(A_{\tau+\eta,\tilde{\nu}},\tilde{\nu})}\leq
e^{-\epsilon/2}\delta/3.$ (D.7)

To this end, note that for any $A\subset A_{\tau+\eta,\tilde{\nu}}\cup
A_{\tau+\eta,\hat{\nu}}$,

$e^{-\epsilon/4}h(A,\nu^{\prime})\leq h(A,\tilde{\nu})\leq
e^{\epsilon/4}h(A,\nu^{\prime}).$

Moreover, (D.5) implies that $A_{\tau,\tilde{\nu}}\subset
A_{\tau+\eta,\nu^{\prime}}\subset A_{\tau+2\eta,\tilde{\nu}}$ and
$A_{\tau,\nu^{\prime}}\subset A_{\tau+\eta,\tilde{\nu}}\subset
A_{\tau+2\eta,\nu^{\prime}}$. (D.3) Applying these two facts yields that for
any $y>0$, it holds that

$h(A_{\tau+\eta,\tilde{\nu}},\tilde{\nu})\geq
h(A_{\tau-y-2\eta,\tilde{\nu}},\tilde{\nu})\geq
e^{-\epsilon/4}h(A_{\tau-y-2\eta,\nu^{\prime}},\nu^{\prime})\geq
e^{-\epsilon(\tau-y-\eta)/(4\eta)}\operatorname{vol}(A_{\tau-y-2\eta,\nu^{\prime}}).$
(D.8)

Next, we bound the numerator in the left-hand side of (D.7) using the same two
facts,

$h(A_{\tau+\eta,\tilde{\nu}}\cap
A_{\tau-\eta,\tilde{\nu}}^{c},\tilde{\nu})\leq
e^{\epsilon/4}h(A_{\tau+2\eta,\hat{\nu}}\cap
A_{\tau-2\eta,\hat{\nu}}^{c},\hat{\nu})\leq
e^{-\epsilon(\tau+\eta)/(4\eta)}\operatorname{vol}(A_{\tau+2\eta,\hat{\nu}}\cap
A_{\tau-2\eta,\hat{\nu}}^{c}).$ (D.9)

Lastly, combining (D.8) and (D.9) with (D.6) yields

$\displaystyle\frac{h(A_{\tau-\eta,\tilde{\nu}}^{c}\cap
A_{\tau+\eta,\tilde{\nu}},\tilde{\nu})}{h(A_{\tau+\eta,\tilde{\nu}},\tilde{\nu})}$
$\displaystyle\leq
e^{-\epsilon(y+\eta)/4\eta}\frac{\operatorname{vol}(A_{\tau+2\eta,\hat{\nu}}\cap
A_{\tau-2\eta,\hat{\nu}}^{c})}{\operatorname{vol}(A_{\tau-y-2\eta,\hat{\nu}})}\leq
e^{-\epsilon/2}\delta/3,$

which completes the proof. ∎

###### Proof of Lemma 5.3.

Using the fact that $W$ is a standard Laplace random variable, for all
$k\in\\{0\\}\cup[n-1]$, it holds that

$\displaystyle 1-\mathbb{E}\lambda(\hat{\nu},\epsilon,\delta)$
$\displaystyle=\Pr\left(\operatorname{SM}(\hat{\nu},Q)+\frac{2}{\epsilon}W<\frac{2\log(1/2\delta)}{\epsilon}\right)$
$\displaystyle\leq\Pr\left(\operatorname{SM}(\hat{\nu},Q)<k\right)+\Pr\left(W<\log(1/2\delta)-\epsilon
k/2\right).$

It is immediate from the fact that the above bound holds for all
$k\in\\{0\\}\cup[n-1]$ that

$\displaystyle 1-\mathbb{E}\lambda(\hat{\nu},\epsilon,\delta)$
$\displaystyle\leq\inf_{k\in\\{0\\}\cup[n-1]}\left[\Pr\left(\operatorname{SM}(\hat{\nu},Q)<k\right)+\Pr\left(W<\log(1/2\delta)-\epsilon
k/2\right)\right].$

Applying Lemma D.2 yields that, for all $k\in\\{0\\}\cup[n-1]$, it holds that

$\Pr\left(\operatorname{SM}(\hat{\nu},Q)<k\right)\leq\Pr\Big{(}\sup_{\begin{subarray}{c}\tilde{\nu}\in\widetilde{\mathcal{M}}_{1}(\hat{\nu},k+1)\\\
x\in A_{\tau+\eta,\hat{\nu}}\cup
A_{\tau+\eta,\tilde{\nu}}\end{subarray}}|\phi(x,\hat{\nu})-\phi(x,\tilde{\nu})|>\eta/2\Big{)}\\\
+\Pr\left(\inf_{y>0}e^{-\epsilon
y/4\eta}\frac{\operatorname{vol}(A_{\tau+2\eta,\hat{\nu}}\cap
A_{\tau-2\eta,\hat{\nu}}^{c})}{\operatorname{vol}(A_{\tau-y-2\eta,\hat{\nu}})}>e^{-\epsilon/4}\delta/3\right).$

Combining the two bounds gives the result. ∎

##  Appendix E Results concerning Condition 2

Here, we show that the median and median absolute deviation satisfy Condition
2 under general conditions.

######  Lemma E.1.

Let $\mu$ be the median. If Condition 4 holds for $(1/2,\nu,0)$ then for all
$t\geq 0$ and $n,d\geq 1$

$\Pr\left(S_{n}(\mu)\geq
t\right)\lesssim\exp\left(-2nM^{2}t^{2}+d\log(cn/d)\right).$

###### Proof.

The proof follows from Lemma C.1. ∎

######  Lemma E.2.

Let $\sigma$ be the median absolute deviation. If for some $q^{\prime}$ that
satisfies

$0<q^{\prime}<\inf_{u\in\mathbb{S}^{d-1}}\operatorname*{{\rm argmin}}_{0<p\leq
1/2}|\xi_{1/2,u}-\xi_{p,u}-(\xi_{p+1/2,u}-\xi_{1/2,u})|,$

Condition 4 holds for $(q^{\prime},\nu,0)$ with $r\geq 1/3M$, and
$\sup_{\begin{subarray}{c}x\in\mathcal{I};u\in\mathbb{S}^{d-1}\end{subarray}}f_{\nu_{u}}(x)<L<\infty$,
then for all $t\geq 0$ and $n,d\geq 1$

$\Pr\left(S_{n}(\sigma)\geq
t\right)\lesssim\exp\left(-2nM^{2}t^{2}/16^{2}\vee-2n[(1/2-q^{\prime})M/L\wedge
1/3]^{2}+d\log(cn/d)\right).$

###### Proof.

Let

$\mathcal{C}_{u}(p)=\xi_{1/2,u}-\xi_{p,u}-(\xi_{p+1/2,u}-\xi_{1/2,u}),$

and $q_{u}=\operatorname*{{\rm argmin}}_{0<p\leq 1/2}|\mathcal{C}_{u}(p)|$.
Now, note that under absolute continuity of $\nu_{u}$, it holds that
$\sigma(\nu_{u})=|\xi_{1/2,u}-\xi_{q_{u},u}|$. This is because the median
absolute deviation of a measure $P$ is half the length of the symmetric
interval about the median, which contains 1/2 of the probability mass of $P$
[21]. Now, analogously, let

$\hat{\mathcal{C}}_{u}(p)=\hat{\xi}_{1/2,u}-\hat{\xi}_{p,u}-(\hat{\xi}_{p+1/2,u}-\hat{\xi}_{1/2,u})\qquad\text{and}\qquad\tilde{\mathcal{C}}_{u}(p)=\hat{\xi}_{1/2,u}-\hat{\xi}_{p-1/2,u}-(\hat{\xi}_{p,u}-\hat{\xi}_{1/2,u}),$

with

$\hat{q}_{u}=\operatorname*{{\rm argmin}}_{0\leq p\leq
1/2}|\hat{\mathcal{C}}_{u}(p)|\qquad\text{and}\qquad\tilde{q}_{u}=\operatorname*{{\rm
argmin}}_{1/2\leq p\leq 1}|\tilde{\mathcal{C}}_{u}(p)|.$

It follows by definition of the median absolute deviation that for any
$u\in\mathbb{S}^{d-1}$,

$|\hat{\xi}_{1/2,u}-\hat{\xi}_{\hat{q}_{u},u}|\wedge|\hat{\xi}_{1/2,u}-\hat{\xi}_{\tilde{q}_{u},u}|\leq\sigma(\hat{\nu}_{u})\leq|\hat{\xi}_{1/2,u}-\hat{\xi}_{\hat{q}_{u},u}|\vee|\hat{\xi}_{1/2,u}-\hat{\xi}_{\tilde{q}_{u},u}|.$

This fact directly implies that for any $u\in\mathbb{S}^{d-1}$, either

$|\sigma(\hat{\nu}_{u})-\sigma(\nu_{u})|\leq|\xi_{1/2,u}-\xi_{q_{u},u}-(\hat{\xi}_{1/2,u}-\hat{\xi}_{\hat{q}_{u},u})|\leq|\xi_{1/2,u}-\hat{\xi}_{1/2,u}|+|\xi_{\hat{q}_{u},u}-\xi_{q_{u},u}|+|\xi_{\hat{q}_{u},u}-\hat{\xi}_{\hat{q}_{u},u}|,$
(E.1)

holds, or

$|\sigma(\hat{\nu}_{u})-\sigma(\nu_{u})|\leq|\xi_{1/2,u}-\hat{\xi}_{1/2,u}|+|\xi_{\tilde{q}_{u},u}-\xi_{q_{u}+1/2,u}|+|\xi_{\tilde{q}_{u},u}-\hat{\xi}_{\tilde{q}_{u},u}|,$
(E.2)

holds. Next, we bound $\hat{q}_{u}$ below and $\tilde{q}_{u}$ above for all
$u\in\mathbb{S}^{d-1}$. Consider $w\in\mathbb{R}$ such that
$q^{\prime}<w<\inf_{u\in\mathbb{S}^{d-1}}q_{u}$. Now, it follows from
Condition 4 and an application of the mean value theorem that

$\xi_{w,u}-\xi_{q^{\prime},u}\leq(w-q^{\prime})/\inf_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\
x\in(\xi_{q^{\prime},u},\xi_{w,u})\end{subarray}}f_{u}(x)\leq M^{-1}.$

Now, using Condition 4 and the assumption that $r>1/3M$, together with an
application of Lemma C.1 yields

$\Pr\Big{(}\sup_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\
x\in\\{w,1/2\\}\end{subarray}}|\hat{\xi}_{x,u}-\xi_{x,u}|>1/3M\Big{)}\lesssim\left(\frac{cn}{d}\right)^{d}e^{-2n/9}.$
(E.3)

Next, we show that the probability that
$(\hat{\xi}_{w,u},\hat{\xi}_{1/2,u}+(\hat{\xi}_{1/2,u}-\hat{\xi}_{w,u}))=(\hat{\xi}_{w,u},2\hat{\xi}_{1/2,u}-\hat{\xi}_{w,u})$
contains less than 1/2 of the projected observations for at least one
$u\in\mathbb{S}^{d-1}$ is small. This immediately implies that
$\hat{q}_{u}\geq w>q^{\prime}$ for any $u\in\mathbb{S}^{d-1}$. To this end,
(E.3) implies that with high probability,

$(\hat{\xi}_{w,u},2\hat{\xi}_{1/2,u}-\hat{\xi}_{w,u})\supset(\xi_{w}+1/3M,2\xi_{1/2,u}-\xi_{w}-1/M)\supset(\xi_{q^{\prime}},2\xi_{1/2}-\xi_{q^{\prime}}).$

Now, we bound the probability that
$(\xi_{q^{\prime},u},2\xi_{1/2,u}-\xi_{q^{\prime},u})$ contains less than 1/2
of the projected observations. This is equivalent to bounding:

$\Pr\Big{(}\bigcup_{u\in\mathbb{S}^{d-1}}\\{\hat{\xi}_{1/2,u}<\xi_{q^{\prime},u}\\}\Big{)}\qquad\text{and}\qquad\Pr\Big{(}\bigcup_{u\in\mathbb{S}^{d-1}}\\{\hat{\xi}_{1/2,u}>2\xi_{1/2,u}-\xi_{q^{\prime},u}\\}\Big{)}.$
(E.4)

Starting with the left-hand term, utilizing the mean value theorem, together
with the upper bound on the projected density and an application of Lemma C.1,
yields

$\displaystyle\Pr\Big{(}\bigcup_{u\in\mathbb{S}^{d-1}}\\{\hat{\xi}_{1/2,u}<\xi_{q^{\prime},u}\\}\Big{)}$
$\displaystyle\leq\Pr\left(\sup_{u\in\mathbb{S}^{d-1}}|\hat{\xi}_{1/2,u}-\xi_{1/2,u}|>\inf_{u\in\mathbb{S}^{d-1}}[\xi_{1/2,u}-\xi_{q^{\prime},u}]\right)$
$\displaystyle\leq\Pr\left(\sup_{u\in\mathbb{S}^{d-1}}|\hat{\xi}_{1/2,u}-\xi_{1/2,u}|>(1/2-q^{\prime})/L\right)$
$\displaystyle\leq\left(\frac{cn}{d}\right)^{d}e^{-2nM^{2}(1/2-q^{\prime})^{2}/L^{2}}.$

Similarly, the right-hand term in (E.4) satisfies

$\displaystyle\Pr\Big{(}\bigcup_{u\in\mathbb{S}^{d-1}}\\{\hat{\xi}_{1/2,u}>\xi_{1/2,u}+\xi_{q^{\prime},u}\\}\Big{)}$
$\displaystyle\leq\left(\frac{cn}{d}\right)^{d}e^{-2nM^{2}(1/2-q^{\prime})^{2}/L^{2}}.$

Thus,

$\Pr\left(\inf_{u\in\mathbb{S}^{d-1}}\hat{q}_{u}<q^{\prime}\right)\lesssim\left(\frac{cn}{d}\right)^{d}e^{-2nM^{2}[(1/2-q^{\prime})/L\wedge
M/3]^{2}}.$

An analogous argument gives that

$\Pr\Big{(}\sup_{u\in\mathbb{S}^{d-1}}\tilde{q}_{u}>1-q^{\prime}\Big{)}\lesssim\left(\frac{cn}{d}\right)^{d}e^{-2nM^{2}[(1/2-q^{\prime})/L\wedge
M/3]^{2}}.$

Let $E_{11}=\\{q^{\prime}<\hat{q}_{u}<\tilde{q}_{u}\leq 1-q^{\prime}\\}$ and
note that we have just shown that

$\Pr\left(E_{11}^{c}\right)\lesssim\left(\frac{cn}{d}\right)^{d}e^{-2nM^{2}[(1/2-q^{\prime})/L\wedge
M/3]^{2}}.$ (E.5)

The next step is to show that
$\\{\sup_{u\in\mathbb{S}^{d-1}}|\xi_{\hat{q},u}-\xi_{q,u}|\geq
t|E_{11}\\}\subset\\{\sup_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\
q^{\prime}<p<1-q^{\prime}\end{subarray}}|\xi_{p,u}-\hat{\xi}_{p,u}|\gtrsim
t|E_{11}\\}$. To this end, observe that

$\displaystyle\\{\sup_{u\in\mathbb{S}^{d-1}}|\xi_{\hat{q},u}-\xi_{q,u}|\geq
t|E_{11}\\}$
$\displaystyle=\bigcup_{u\in\mathbb{S}^{d-1}}\\{\inf_{\begin{subarray}{c}q^{\prime}<p<1/2\\\
|\xi_{p,u}-\xi_{q,u}|>t\end{subarray}}|\hat{\mathcal{C}}_{u}(p)|-|\hat{\mathcal{C}}_{u}(q)|\leq
0\\}$
$\displaystyle=\bigcup_{u\in\mathbb{S}^{d-1}}\\{|\hat{\mathcal{C}}_{u}(q)|-\inf_{\begin{subarray}{c}q^{\prime}<p<1/2\\\
|\xi_{p,u}-\xi_{q,u}|>t\end{subarray}}|\hat{\mathcal{C}}_{u}(p)|\geq 0\\}$
$\displaystyle\subset\\{8\sup_{\begin{subarray}{c}u\in\mathbb{S}^{d-1}\\\
q^{\prime}<p<1-q^{\prime}\end{subarray}}|\xi_{p,u}-\hat{\xi}_{p,u}|\geq\inf_{p<1/2,\
|\xi_{p,u}-\xi_{q,u}|>t}|\mathcal{C}_{u}(p)|\\}.$

It remains to show that for any $u\in\mathbb{S}^{d-1}$, $\inf_{0<p<1/2,\
|\xi_{p,u}-\xi_{q,u}|>t}|\mathcal{C}_{u}(p)|\gtrsim t$. This is equivalent to

$\displaystyle\inf_{\begin{subarray}{c}0<p<1/2\\\
|\xi_{p,u}-\xi_{q,u}|>t\end{subarray}}|\xi_{q,u}-\xi_{p,u}+\xi_{q+1/2,u}-\xi_{p+1/2,u}|\gtrsim
t.$

Now,

$\displaystyle\inf_{\begin{subarray}{c}0<p<1/2\\\
|\xi_{p,u}-\xi_{q,u}|>t\end{subarray}}|\xi_{q,u}-\xi_{p,u}+\xi_{q+1/2,u}-\xi_{p+1/2,u}|=\inf_{\begin{subarray}{c}0<p<1/2\\\
|\xi_{p,u}-\xi_{q,u}|>t\end{subarray}}[|\xi_{q,u}-\xi_{p,u}|+|\xi_{q+1/2,u}-\xi_{p+1/2,u}|]\geq
t.$

The first equality comes from the fact that
$|\xi_{p,u}-\xi_{q,u}+\xi_{q+1/2,u}-\xi_{p+1/2,u}|$ is of the form of $|a+b|$
where $sign(a)=sign(b)$. The second inequality comes from the fact that we are
minimizing over $|\xi_{p,u}-\xi_{q,u}|>t$ and the fact that the second term is
non-negative. Thus,

$\\{|\xi_{\hat{q},u}-\xi_{q,u}|\geq
t|E_{11}\\}\subset\\{\sup_{q^{\prime}<p<1-q^{\prime}}|\xi_{p,u}-\hat{\xi}_{p,u}|\geq
t/8\\}.$ (E.6)

By an analogous argument,

$\\{|\xi_{q,u}-\xi_{\tilde{q},u}|\geq
t|E_{11}\\}\subset\\{\sup_{q^{\prime}<p<1-q^{\prime}}|\xi_{p,u}-\hat{\xi}_{p,u}|\geq
t/8\\}.$ (E.7)

Now, combining equations (E.1), (E.2), (E.5), (E.6) and (E.7),

$\displaystyle\Pr\left(S_{n}(\sigma)\geq t\right)$
$\displaystyle\lesssim\Pr\left(\sup_{q^{\prime}<p<1-q^{\prime}}|\xi_{p,u}-\hat{\xi}_{p,u}|\geq
t/16\right)+\left(\frac{cn}{d}\right)^{d}e^{-2n[(1/2-q^{\prime})M/L\wedge
1/3]^{2}}$
$\displaystyle\lesssim\left(\frac{cn}{d}\right)^{d}e^{-2nM^{2}t^{2}/16^{2}}+\left(\frac{cn}{d}\right)^{d}e^{-2n[(1/2-q^{\prime})M/L\wedge
1/3]^{2}}.\qed$