$\displaystyle\;=\;$ $\displaystyle
x_{n}^{\top}Bx_{n}-\tilde{x}_{n}^{\top}B\tilde{x}_{n}$ $\displaystyle\;\leq\;$
$\displaystyle 2\|B\|_{2}\;.$

So we have $|\ell_{D,\tilde{D}}|\leq\varepsilon$ whenever $\|B\|_{2}\leq
n\varepsilon\beta^{2}-1/n$.

For any fixed unit vector $\|v\|_{2}=1$, we have

$\displaystyle v^{\top}Bv=2\sum_{1\leq i\leq j\leq d}B_{ij}v_{i}v_{j}\sim{\cal
N}(0,2\sum_{1\leq i\leq j\leq d}v_{i}^{2}v_{j}^{2})\;\;=\;\;{\cal N}(0,1)\;.$

Then we have

$\displaystyle{\mathbb{P}}\left(|\ell_{D,\tilde{D}}|\geq\varepsilon\right)$
$\displaystyle\;\;\leq\;\;$ $\displaystyle{\mathbb{P}}\left(\|B\|_{2}\geq
n\varepsilon\beta^{2}-1/n\right)$ $\displaystyle\;\;=\;\;$
$\displaystyle{\mathbb{P}}\left({\cal N}(0,1)\geq
n\varepsilon\beta^{2}-\frac{1}{n}\right)$ $\displaystyle\;\;=\;\;$
$\displaystyle\Phi\left(\frac{1}{n}-n\varepsilon\beta^{2}\right)\;,$

where $\Phi$ is CDF of standard Gaussian. According to Gaussian mechanism, if
$\beta=(1/(n\varepsilon))\sqrt{2\log(1.25/\delta)}$, we have
$\Phi\left(\frac{1}{n}-n\varepsilon\beta^{2}\right)\leq\delta$.

1 _$q_{\rm
spectral}(\\{\\{\Psi_{r}^{(\ell)}\\}_{r\in[t_{\ell}]}\\}_{\ell\in[s]},\\{(\mu^{(\ell)},\lambda^{(\ell)})\\}_{\ell\in[s]},\varepsilon,\delta)$_
:

2 $S\leftarrow{\rm
Filter}(\\{\\{\Psi_{r}^{(\ell)}\\}_{r\in[t_{\ell}]}\\}_{\ell\in[s]},\\{(\mu^{(\ell)},\lambda^{(\ell)})\\}_{\ell\in[s]},\varepsilon,\delta)$

3 $\mu\leftarrow(1/|S|)\big{(}\sum_{i\in S}x_{i}\big{)}+{\cal
N}(0,(2B\sqrt{2d\log(1.25/\delta)}/(n\varepsilon))^{2}{\mathbf{I}})$

4 $\lambda\leftarrow\|M(S)-{\mathbf{I}}\|_{2}+{\rm
Lap}(2B^{2}d/(n\varepsilon))$

5 return _$(\mu,\lambda)$_

6 _$q_{\rm
size}(\\{\\{\Psi_{r}^{(\ell)}\\}_{r\in[t_{\ell}]}\\}_{\ell\in[s]},\\{(\mu^{(\ell)},\lambda^{(\ell)})\\}_{\ell\in[s]},\varepsilon,\delta)$_
:

7 $S\leftarrow{\rm
Filter}(\\{\\{\Psi_{r}^{(\ell)}\\}_{r\in[t_{\ell}]}\\}_{\ell\in[s]},\\{(\mu^{(\ell)},\lambda^{(\ell)})\\}_{\ell\in[s]},\varepsilon,\delta)$

8 return _$|S|+{\rm Lap}(1/\varepsilon)$_

9 _$q_{\rm
MMW}(\\{\\{\Psi_{r}^{(\ell)}\\}_{r\in[t_{\ell}]}\\}_{\ell\in[s]},\\{(\mu^{(\ell)},\lambda^{(\ell)})\\}_{\ell\in[s]},\alpha^{(s)},\mu^{(s)}_{t},\varepsilon,\delta)$_
:

10 $S\leftarrow{\rm
Filter}(\\{\\{\Psi_{r}^{(\ell)}\\}_{r\in[t_{\ell}]}\\}_{\ell\in[s]},\\{(\mu^{(\ell)},\lambda^{(\ell)})\\}_{\ell\in[s]},\varepsilon,\delta)$

11 $\Sigma^{(s)}_{t_{s}+1}\leftarrow M(S)+{\cal
N}(0,(4B^{2}d\sqrt{2\log(1.25/\delta)}/(n\varepsilon))^{2}{\mathbf{I}})$

12 $U\leftarrow(1/{\rm
Tr}(\exp(\alpha^{(s)}\sum_{r=1}^{t_{s}+1}(\Sigma_{r}^{(s)}-{\mathbf{I}}))))\exp(\alpha^{(s)}\sum_{r=1}^{t_{s}+1}(\Sigma_{r}^{(s)}-{\mathbf{I}}))$

13 $\psi\leftarrow\langle M(S)-{\mathbf{I}},U\rangle+{\rm
Lap}(2B^{2}d/(n\varepsilon))$

14 return _$(\Sigma_{t_{s}+1}^{(s)},U,\psi)$_

15 _$q_{\rm
1Dfilter}(\\{\\{\Psi_{r}^{(\ell)}\\}_{r\in[t_{\ell}]}\\}_{\ell\in[s]},\\{(\mu^{(\ell)},\lambda^{(\ell)})\\}_{\ell\in[s]},\mu,U,\alpha,\varepsilon,\delta)$_
:

16 $S\leftarrow{\rm
Filter}(\\{\\{\Psi_{r}^{(\ell)}\\}_{r\in[t_{\ell}]}\\}_{\ell\in[s]},\\{(\mu^{(\ell)},\lambda^{(\ell)})\\}_{\ell\in[s]},\varepsilon,\delta)$

17 return _$\rho\leftarrow\text{\sc
DPthreshold}(\mu,U,\alpha,\varepsilon,\delta,S)$_

18

19 _Filter
$(\\{\\{\Psi_{r}^{(\ell)}\\}_{r\in[t_{\ell}]}\\}_{\ell\in[s]},\\{(\mu^{(\ell)},\lambda^{(\ell)})\\}_{\ell\in[s]})$_:

20 $S^{(1)}\leftarrow[n]$

21 for  _epoch $\ell=1,\ldots,s$_ do

22 $\alpha^{(\ell)}\leftarrow 1/(100(0.1/C+1.01)\lambda^{(\ell)})$

23 $S_{1}^{(\ell)}\leftarrow S^{(\ell)}$

24 for  _$r=1,\ldots,t_{s}$_ do

25 $S_{r+1}^{(\ell)}\leftarrow S^{(\ell)}_{r}\setminus$ $\\{i\,|\,i\in{\cal
T}_{2\alpha}$ for
$\\{\tau_{j}=(x_{j}-\mu_{r}^{(\ell)})^{\top}U_{r}^{(\ell)}(x_{j}-\mu_{r}^{(\ell)})\\}_{j\in
S_{r}^{(\ell)}}$ and $\tau_{i}\geq\rho_{r}^{(\ell)}\,Z_{r}^{(\ell)}\\}$, where
${\cal T}_{2\alpha}$ is defined in Definition C.1.

26

Output: $S^{(s)}_{t_{s}}$

27

Algorithm 12 Interactive differentially private mechanisms for DPMMWfilter

Input: $\alpha\in(0,1)$, $T_{1},T_{2}$, $\varepsilon_{1}=\varepsilon/(4T_{1})$
, $\delta_{1}=\delta/(4T_{1})$,
$\varepsilon_{2}=\min\\{0.9,\varepsilon\\}/(4\sqrt{10T_{1}T_{2}\log(4/\delta)})$,
$\delta_{2}=\delta/(20T_{1}T_{2})$

1 if $n<(4/\varepsilon_{1})\log(1/(2\delta_{1}))$ then Output: $\emptyset$

2 for  _epoch $s=1,2,\ldots,T_{1}$_ do

3 $(\mu^{(s)},\lambda^{(s)})\leftarrow q_{\rm
spectral}(\\{\\{\Psi_{r}^{(\ell)}\\}_{r\in[t_{\ell}]}\\}_{\ell\in[s-1]},\\{(\mu^{(\ell)},\lambda^{(\ell)})\\}_{\ell\in[s-1]},\varepsilon_{1},\delta_{1})$

4 $n^{(s)}\leftarrow q_{\rm
size}(\\{\\{\Psi_{r}^{(\ell)}\\}_{r\in[t_{\ell}]}\\}_{\ell\in[s-1]},\\{(\mu^{(\ell)},\lambda^{(\ell)})\\}_{\ell\in[s-1]},\varepsilon_{1},\delta_{1})$

5 if $n^{(s)}\leq 3n/4$ then terminate

6 if  _$\lambda^{(s)}\leq C\alpha\log(1/\alpha)$ _ then

Output: $\mu^{(s)}$

7

8 $\alpha^{(s)}\leftarrow 1/(100(0.1/C+1.01)\lambda^{(s)})$

9 $t_{s}\leftarrow 0$

10

11 for  _$t=1,2,\ldots,T_{2}$_ do

12 $(\mu_{t}^{(s)},\lambda_{t}^{(s)})\leftarrow q_{\rm
spectral}(\\{\\{\Psi_{r}^{(\ell)}\\}_{r\in[t_{\ell}]}\\}_{\ell\in[s]},\\{(\mu^{(\ell)},\lambda^{(\ell)})\\}_{\ell\in[s]},\varepsilon_{2},\delta_{2})$

13 if  _$\lambda_{t}^{(s)}\leq 0.5\lambda^{(s)}$_ then

14 terminate epoch

15 else

16 $(\Sigma_{t}^{(s)},U_{t}^{(s)},\psi_{t}^{(s)})\leftarrow q_{\rm
PMMW}(\\{\\{\Psi_{r}^{(\ell)}\\}_{r\in[t_{\ell}]}\\}_{\ell\in[s]},\\{(\mu^{(\ell)},\lambda^{(\ell)})\\}_{\ell\in[s]},\alpha^{(s)},\mu_{t}^{(s)},\varepsilon_{2},\delta_{2})$

17

18 if  _$\psi_{t}^{(s)}\leq(1/5.5)\lambda_{t}^{(s)}$_ then

19 $\alpha^{(s)}_{t}\leftarrow 0$

20

21 else

22 $Z_{t}^{(s)}\leftarrow{\rm Unif}([0,1])$

23 $\rho_{t}^{(s)}\leftarrow
q_{\text{1Dfilter}}(\\{\\{\Psi_{r}^{(\ell)}\\}_{r\in[t_{\ell}]}\\}_{\ell\in[s]},\\{(\mu^{(\ell)},\lambda^{(\ell)})\\}_{\ell\in[s]},\mu_{t}^{(s)},U_{t}^{(s)},\alpha,\varepsilon_{2},\delta_{2})$

24 $\alpha_{t}^{(s)}\leftarrow\alpha$

25

26
$\Psi^{(s)}_{t}\leftarrow(\mu_{t}^{(s)},\lambda^{(s)}_{t},\Sigma_{t}^{(s)},U^{(s)}_{t},\psi^{(s)}_{t},Z^{(s)}_{t},\rho^{(s)}_{t},\alpha^{(s)}_{t})$

27 $t_{s}\leftarrow t$

28

29

Output: $\mu^{(T_{1})}_{t_{T_{1}}}$

Algorithm 13 Interactive version of DPMMWfilter

####  F.2 Proof of part 2 of Theorem 6 on accuracy

The accuracy of PRIME follows from the fact that $q_{\rm range}$ returns a
hypercube that contains all the clean data with high probability (Lemma D.2)
and that DPMMWfilter achieves the desired accuracy (Theorem 11) if the
original uncorrupted dataset $S_{\rm good}$ is $\alpha$-subgaussian good.
$S_{\rm good}$ is $\alpha$-subgaussian good if we have
$n=\widetilde{\Omega}(d/\alpha^{2})$ as shown in Lemma G.3. We present the
proof of Theorem 11 below.

######  Theorem 11 (Analysis of accuracy of DPMMWfilter).

Let $S$ be an $\alpha$-corrupted sub-Gaussian dataset, where $\alpha\leq c$
for some universal constant $c\in(0,1/2)$. Let $S_{\rm good}$ be
$\alpha$-subgaussian good with respect to $\mu\in{\mathbb{R}}^{d}$. Suppose
${\cal D}=\\{x_{i}\in\bar{x}+[-B/2,B/2]^{d}\\}_{i=1}^{n}$ be the projected
dataset. If
$n\geq\widetilde{\Omega}\left(\frac{d^{3/2}B^{2}\log(2/\delta)}{\varepsilon\alpha\log
1/\alpha}\right)$, then DPMMWfilter terminates after at most $O(\log dB^{2})$
epochs and outputs $S^{(s)}$ such that with probability $0.9$, we have
$|S_{t}^{(s)}\cap S_{\mathrm{good}}|\geq(1-10\alpha)n$ and

$\displaystyle\|\mu(S^{(s)})-\mu\|_{2}\lesssim\alpha\sqrt{\log 1/\alpha}\;.$

Moreover, each epoch runs for at most $O(\log d)$ iterations.

###### Proof.

In $s=O(\log_{0.98}((C\alpha\log(1/\alpha))/\|M(S^{(1)})-{\mathbf{I}}\|_{2}))$
epochs, following Lemma F.3 guarantees that we find a candidate set $S^{(s)}$
of samples with $\|M(S^{(s)}-{\mathbf{I}}\|_{2}\leq C\alpha\log(1/\alpha)$. We
provide proof of Lemma F.3 in the Appendix F.3.

######  Lemma F.3.

Let $S$ be an $\alpha$-corrupted sub-Gaussian dataset under Assumption 1. For
an epoch $s\in[T_{1}]$ and an iteration $t\in[T_{2}]$, under the hypotheses of
Lemma F.4, if $S_{\rm good}$ is $\alpha$-subgaussian good with respect to
$\mu\in{\mathbb{R}}^{d}$ as in Definition G.2,
$n=\widetilde{\Omega}(d^{3/2}\log(1/\delta)/(\varepsilon\alpha))$, and
$|S_{t}^{(s)}\cap S_{\rm good}|\geq(1-10\alpha)n$ then with probability
$1-O(1/\log^{3}d)$ the conditions in Eqs. (14) and (15) hold. When these two
conditions hold, more corrupted samples are removed in expectation than the
uncorrupted samples, i.e., $\mathbb{E}|(S_{t}^{(s)}\setminus
S_{t+1}^{(s)})\cap S_{\rm good}|\leq\mathbb{E}|(S_{t}^{(s)}\setminus
S_{t+1}^{(s)})\cap S_{\rm bad}|$. Further, for an epoch $s\in[T_{1}]$ there
exists a constant $C>0$ such that if $\|M(S^{(s)})-{\mathbf{I}}\|_{2}\geq
C\,\alpha\log(1/\alpha)$, then with probability $1-O(1/\log^{2}d)$, the $s$-th
epoch terminates after $O(\log d)$ iterations and outputs $S^{(s+1)}$ such
that $\|M(S^{(s+1)})-{\mathbf{I}}\|_{2}\leq
0.98\|M(S^{(s)})-{\mathbf{I}}\|_{2}$.

Lemma G.7 ensures that we get the desired bound of
$\|\mu(S^{(s)})-\mu\|_{2}=O(\alpha\sqrt{\log(1/\alpha)})$ as long as $S^{(s)}$
has enough clean data, i.e., $|S^{(s)}\cap S_{\rm good}|\geq n(1-\alpha)$.
Since Lemma F.3 gets invoked at most $O((\log d)^{2})$ times, we can take a
union bound, and the following argument conditions on the good events in Lemma
F.3 holding, which happens with probability at least $0.99$. To turn the
average case guarantee of Lemma F.3 into a constant probability guarantee, we
apply the optional stopping theorem. Recall that the $s$-th epoch starts with
a set $S^{(s)}$ and outputs a filtered set $S^{(s)}_{t}$ at the $t$-th inner
iteration. We measure the progress by by summing the number of clean samples
removed up to epoch $s$ and iteration $t$ and the number of remaining
corrupted samples, defined as $d_{t}^{(s)}\triangleq|(S_{\mathrm{good}}\cap
S^{(1)})\setminus S_{t}^{(s)}|+|S_{t}^{(s)}\setminus(S_{\mathrm{good}}\cap
S^{(1)})|$. Note that $d_{1}^{(1)}=\alpha n$, and $d_{t}^{(s)}\geq 0$. At each
epoch and iteration, we have

$\displaystyle\mathbb{E}[d_{t+1}^{(s)}-d_{t}^{(s)}|d_{1}^{(1)},d_{2}^{(1)},\cdots,d_{t}^{(s)}]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[|S_{\mathrm{good}}\cap(S_{t}^{(s)}\setminus
S_{t+1}^{(s)})|-|S_{\mathrm{bad}}\cap(S_{t}^{(s)}\setminus
S_{t+1}^{(s)})|\right]\;\leq\;0,$

from part 1 of Lemma F.3. Hence, $d_{t}^{(s)}$ is a non-negative super-
martingale. By the optional stopping theorem, at stopping time, we have
$\mathbb{E}[d_{t}^{(s)}]\leq d_{1}^{(1)}=\alpha n$. By the Markov inequality,
$d_{t}^{(s)}$ is less than $10\alpha n$ with probability $0.9$, i.e.,
$|S_{t}^{(s)}\cap S_{\mathrm{good}}|\geq(1-10\alpha)n$. The desired bound in
Theorem 11 follows from Lemma G.7.

∎

####  F.3 Proof of Lemma F.3

Lemma F.3 is a combination of Lemma F.4 and Lemma F.5. We state the technical
lemmas and subsequently provide the proofs.

######  Lemma F.4.

For an epoch $s$ and an iteration $t$ such that
$\lambda^{(s)}>C\alpha\log(1/\alpha)$,
$\lambda_{t}^{(s)}>0.5\lambda_{0}^{(s)}$, and $n^{(s)}>3n/4$, if
$n\gtrsim\frac{B^{2}(\log B)d^{3/2}\log(1/\delta)}{\varepsilon\alpha}$ and
$|S_{t}^{(s)}\cap S_{\rm good}|\geq(1-10\alpha)n$ then with probability
$1-O(1/\log^{3}d)$, the conditions in Eqs. (14) and (15) hold. When these two
conditions hold we have $\mathbb{E}|S_{t}^{(s)}\setminus S_{t+1}^{(s)}\cap
S_{\rm good}|\leq\mathbb{E}|S_{t}^{(s)}\setminus S_{t+1}^{(s)}\cap S_{\rm
bad}|$. If $n\gtrsim\frac{B^{2}(\log
B)d^{3/2}\log(1/\delta)}{\varepsilon\alpha}$,
$\psi_{t}^{(s)}>\frac{1}{5.5}\lambda_{t}^{(s)}$, and $n^{(s)}>3n/4$, then we
have with probability $1-O(1/\log^{3}d)$, $\left\langle
M(S_{t+1}^{(s)})-{\mathbf{I}},U_{t}^{(s)}\right\rangle\leq 0.76\left\langle
M(S_{t}^{(s)})-{\mathbf{I}},U_{t}^{(s)}\right\rangle$.

######  Lemma F.5.

For an epoch $s$ and for all $t=0,1,\cdots,T_{2}=O(\log d)$ if Lemma F.4
holds, $n^{(s)}>3n/4$, and $n\gtrsim\frac{B^{2}(\log
B)d^{3/2}\log(1/\delta)}{\varepsilon\alpha}$, then we have
$\|M(S^{(s+1)})-{\mathbf{I}}\|_{2}\leq 0.98\|M(S^{(s)})-{\mathbf{I}}\|_{2}$
with probability $1-O(1/\log^{2}d)$.

#####  F.3.1 Proof of Lemma F.4

###### Proof of Lemma F.4.

To prove that we make progress for each iteration, we first show our dataset
satisfies regularity conditions in Eqs. (14) and (15) that we need for
DPthreshold. Following Lemma F.6 implies with probability $1-1/(\log^{3}d)$,
our scores satisfies the regularity conditions needed in Lemma E.1.

######  Lemma F.6.

For each epoch $s$ and iteration $t$, under the hypotheses of Lemma F.4, with
probability $1-O(1/\log^{3}d)$, we have

$\displaystyle\frac{1}{n}\sum_{i\in S_{\rm good}\cap{\cal
T}_{2\alpha}}\tau_{i}$ $\displaystyle\leq$ $\displaystyle\psi/1000$ (14)
$\displaystyle\frac{1}{n}\sum_{i\in S_{\rm good}\cap S_{t}^{(s)}}(\tau_{i}-1)$
$\displaystyle\leq$ $\displaystyle\psi/1000\;,$ (15)

where $\psi\triangleq\frac{1}{n}\sum_{i\in S_{t}^{(s)}}(\tau_{i}-1)$.

Then by Lemma E.1 our DPthreshold gives us a threshold $\rho$ such that

$\displaystyle\sum_{i\in S_{\rm good}\cap{\cal
T}_{2\alpha}}\textbf{1}\\{\tau_{i}\leq\rho\\}\frac{\tau_{i}}{\rho}+\textbf{1}\\{\tau_{i}>\rho\\}\leq\sum_{i\in
S_{\rm bad}\cap{\cal
T}_{2\alpha}}\textbf{1}\\{\tau_{i}\leq\rho\\}\frac{\tau_{i}}{\rho}+\textbf{1}\\{\tau_{i}>\rho\\}\;.$

Conditioned on the hypotheses and the claims of Lemma E.1, according to our
filter rule from Algorithm 10, we have

$\displaystyle\mathbb{E}|(S_{t}^{(s)}\setminus S_{t+1}^{(s)})\cap S_{\rm
good}|\;=\;\sum_{i\in S_{\rm good}\cap{\cal
T}_{2\alpha}}\textbf{1}\\{\tau_{i}\leq\rho\\}\frac{\tau_{i}}{\rho}+\textbf{1}\\{\tau_{i}>\rho\\}$

and

$\displaystyle\mathbb{E}|(S_{t}^{(s)}\setminus S_{t+1}^{(s)})\cap S_{\rm
bad}|\;=\;\sum_{i\in S_{\rm bad}\cap{\cal
T}_{2\alpha}}\textbf{1}\\{\tau_{i}\leq\rho\\}\frac{\tau_{i}}{\rho}+\textbf{1}\\{\tau_{i}>\rho\\}\;.$

This implies $\mathbb{E}|(S_{t}^{(s)}\setminus S_{t+1}^{(s)})\cap S_{\rm
good}|\leq\mathbb{E}|(S_{t}^{(s)}\setminus S_{t+1}^{(s)})\cap S_{\rm bad}|$.
At the same time, Lemma E.1 gives us a $\rho$ such that with probability
$1-O(\log^{3}d)$

$\displaystyle\frac{1}{n}\sum_{i\in
S_{t+1}^{(s)}}(\tau_{i}-1)-2\alpha\leq\frac{1}{n}\sum_{\tau_{i}\leq\rho}(\tau_{i}-1)\leq\frac{3}{4}\cdot\frac{1}{n}\sum_{i\in
S_{t}^{(s)}}(\tau_{i}-1)\;.$

Hence, we have

$\displaystyle\left\langle
M(S_{t}^{(s)})-{\mathbf{I}},U_{t}^{(s)}\right\rangle-\left\langle
M(S_{t+1}^{(s)})-{\mathbf{I}},U_{t}^{(s)}\right\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i\in S_{t}^{(s)}\setminus
S_{t+1}^{(s)}}(\tau_{i}-1)$ $\displaystyle\geq$
$\displaystyle\frac{1}{4n}\sum_{i\in S_{t}^{(s)}}(\tau_{i}-1)-2\alpha$
$\displaystyle\overset{(a)}{\geq}$
$\displaystyle\frac{1}{4}\cdot\frac{998}{1000}\left\langle
M(S_{t}^{(s)})-{\mathbf{I}},U_{t}^{(s)}\right\rangle\;,$

where $(a)$ follows from our assumption on $\lambda_{t}$ and stopping
criteria. Rearranging the terms completes the proof. ∎

#####  F.3.2 Proof of Lemma F.6

###### Proof of Lemma F.6.

First of all, Lemma G.9, Lemma G.10 and Lemma G.11 gives us following Lemma
F.7, which basically shows with enough samples, we can make sure the noises
added for privacy guarantees are small enough with probability
$1-O(1/\log^{3}d)$.

######  Lemma F.7.

For $\alpha\in(0,0.5)$, if $n\gtrsim\frac{B^{2}(\log
B)d^{3/2}\log(1/\delta)}{\varepsilon\alpha}$ and $n^{(s)}>3n/4$ then we have
with probability $1-O(1/\log^{3}d)$, following conditions simultaneously hold:

  1. 1.

$\|\mu_{t}^{(s)}-\mu(S_{t}^{(s)})\|_{2}^{2}\leq 0.001\alpha\log 1/\alpha$

  2. 2.

$|\psi_{t}^{(s)}-\left\langle
M(S_{t}^{(s)})-{\mathbf{I}},U_{t}^{(s)}\right\rangle|\leq 0.001\alpha\log
1/\alpha$

  3. 3.

$\left|\lambda_{t}^{(s)}-\|M(S_{t}^{(s)})-{\mathbf{I}}\|_{2}\right|\leq
0.001\alpha\log 1/\alpha$

  4. 4.

$\left|\lambda^{(s)}-\|M(S^{(s)})-{\mathbf{I}}\|_{2}\right|\leq
0.001\alpha\log 1/\alpha$

  5. 5.

$\left\|M(S_{t+1}^{(s)})-\Sigma_{t}^{(s)}\right\|_{2}\leq 0.001\alpha\log
1/\alpha$

  6. 6.

$\|\mu^{(s)}-\mu(S^{(s)})\|_{2}^{2}\leq 0.001\alpha\log 1/\alpha$

Now under above conditions, since $\lambda_{1}^{(s)}>C\alpha\log 1/\alpha$, we
have $\|M(S_{t}^{(s)})-{\mathbf{I}}\|_{2}>0.5(C-0.002)\alpha\log 1/\alpha$.
Using the fact that $\mu(S^{(s)}_{t})=(1/n)\sum_{i\in S_{t}^{(s)}}x_{i}$, we
also have

$\displaystyle\frac{1}{n}\sum_{i\in S_{t}^{(s)}}(\tau_{i}-1)$ $\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i\in
S_{t}^{(s)}}\left\langle\left(x_{i}-\mu_{t}^{(s)}\right)\left(x_{i}-\mu_{t}^{(s)}\right)^{\top}-{\mathbf{I}},U_{t}^{(s)}\right\rangle$
$\displaystyle=$ $\displaystyle\frac{1}{n}\sum_{i\in
S_{t}^{(s)}}\left\langle\left(x_{i}-\mu(S_{t}^{(s)})\right)\left(x_{i}-\mu(S_{t}^{(s)})\right)^{\top}-{\mathbf{I}},U_{t}^{(s)}\right\rangle$
$\displaystyle\;\;+\;\;\;\;\frac{|S_{t}^{(s)}|}{n}\left\langle\left(\mu(S_{t}^{(s)})-\mu_{t}^{(s)}\right)\left(\mu(S_{t}^{(s)})-\mu_{t}^{(s)}\right)^{\top},U_{t}^{(s)}\right\rangle$
$\displaystyle=$ $\displaystyle\left\langle
M(S_{t}^{(s)})-{\mathbf{I}},U_{t}^{(s)}\right\rangle+\frac{|S_{t}^{(s)}|}{n}\left\langle\left(\mu(S_{t}^{(s)})-\mu_{t}^{(s)}\right)\left(\mu(S_{t}^{(s)})-\mu_{t}^{(s)}\right)^{\top},U_{t}^{(s)}\right\rangle\;.$

Thus, from the first and the second claims in Lemma F.7, we have

$\displaystyle|\psi-\psi_{t}^{(s)}|\leq 0.002\;\alpha\log 1/\alpha\;.$ (16)

For an epoch $s$ and an iteration $t$, since $\alpha n\leq S_{\rm
good}\cap{\cal T}_{2\alpha}\cap S_{t}^{(s)}\leq 2\alpha n$, we have

$\displaystyle\frac{1}{n}\sum_{i\in S_{\rm good}\cap{\cal T}_{2\alpha}\cap
S_{t}^{(s)}}\tau_{i}\;\;=\;\;\frac{1}{n}\sum_{i\in S_{\rm good}\cap{\cal
T}_{2\alpha}\cap
S_{t}^{(s)}}\left\langle(x_{i}-\mu_{t}^{(s)})(x_{i}-\mu_{t}^{(s)})^{\top},U_{t}^{(s)}\right\rangle$
$\displaystyle\overset{(a)}{\leq}$ $\displaystyle\frac{2}{n}\sum_{i\in S_{\rm
good}\cap{\cal T}_{2\alpha}\cap
S_{t}^{(s)}}\left\langle(x_{i}-\mu)(x_{i}-\mu)^{\top},U_{t}^{(s)}\right\rangle+\frac{2|S_{\rm
good}\cap{\cal T}_{2\alpha}\cap
S_{t}^{(s)}|}{n}\left\langle(\mu-\mu_{t}^{(s)})(\mu-\mu_{t}^{(s)})^{\top},U_{t}^{(s)}\right\rangle$
$\displaystyle\overset{(b)}{\leq}$ $\displaystyle O(\alpha\log
1/\alpha)+4\alpha\left\langle(\mu-\mu_{t}^{(s)})(\mu-\mu_{t}^{(s)})^{\top},U_{t}^{(s)}\right\rangle$
$\displaystyle\leq$ $\displaystyle O(\alpha\log
1/\alpha)+4\alpha\|\mu_{t}^{(s)}-\mu\|_{2}^{2}$ $\displaystyle\leq$
$\displaystyle O(\alpha\log
1/\alpha)+4\alpha\left(\|\mu-\mu(S_{t}^{(s)})\|_{2}+\|\mu(S_{t}^{(s)})-\mu_{t}^{(s)}\|_{2}\right)^{2}$
$\displaystyle\overset{(c)}{\leq}$ $\displaystyle O\left(\alpha\log
1/\alpha\right)+4\alpha\left(O\left(\alpha\sqrt{\log
1/\alpha}\right)+\sqrt{\alpha\left(O\left(\alpha\log
1/\alpha\right)+\|M(S_{t}^{(s)})-{\mathbf{I}}\|_{2}\right)}+\|\mu(S_{t}^{(s)})-\mu_{t}^{(s)}\|_{2}\right)^{2}$
$\displaystyle\leq$ $\displaystyle O(\alpha\log
1/\alpha)+8\alpha^{2}\left(\|M(S_{t}^{(s)})-{\mathbf{I}}\|_{2}+O\left(\alpha\log
1/\alpha\right)\right)+O(8\alpha^{3}\log 1/\alpha)+8\alpha^{2}\log 1/\alpha$
$\displaystyle\overset{(d)}{\leq}$
$\displaystyle\frac{1}{1000}\left(\frac{\|M(S_{t}^{(s)})-{\mathbf{I}}\|_{2}-0.001\;\alpha\log
1/\alpha}{5.5}-0.002\;\alpha\log 1/\alpha\right)$ $\displaystyle\leq$
$\displaystyle\frac{\psi_{t}^{(s)}-0.002\;\alpha\log 1/\alpha}{1000}$
$\displaystyle\leq$ $\displaystyle\frac{\psi}{1000}\;,$

where $(a)$ follows from the fact that for any vector $x,y,z$, we have
$(x-y)(x-y)^{\top}\preceq 2(x-z)(x-z)^{\top}+2(y-z)(y-z)^{\top}$, $(b)$
follows from Lemma G.4, $(c)$ follows from Lemma G.7, $(d)$ follows from our
choice of large constant $C$, and in the last inequality we used Eq. (16).

Similarly we have

$\displaystyle\frac{1}{n}\sum_{i\in S_{\rm good}\cap S_{t}^{(s)}}(\tau_{i}-1)$
$\displaystyle=$ $\displaystyle\frac{1}{n}\sum_{i\in S_{\rm good}\cap
S_{t}^{(s)}}\left\langle(x_{i}-\mu_{t}^{(s)})(x_{i}-\mu_{t}^{(s)})^{\top}-{\mathbf{I}},U_{t}^{(s)}\right\rangle$
$\displaystyle=$ $\displaystyle\frac{1}{n}\sum_{i\in S_{\rm good}\cap
S_{t}^{(s)}}\left\langle\left(x_{i}-\mu(S_{\rm good}\cap
S_{t}^{(s)})\right)\left(x_{i}-\mu(S_{\rm good}\cap
S_{t}^{(s)})\right)^{\top}-{\mathbf{I}},U_{t}^{(s)}\right\rangle$
$\displaystyle+\frac{|S_{\rm good}\cap
S_{t}^{(s)}|}{n}\left\langle\left(\mu(S_{\rm good}\cap
S_{t}^{(s)})-\mu_{t}^{(s)}\right)\left(\mu(S_{\rm good}\cap
S_{t}^{(s)})-\mu_{t}^{(s)}\right)^{\top},U_{t}^{(s)}\right\rangle$
$\displaystyle\overset{(a)}{\leq}$ $\displaystyle O\left(\alpha\log
1/\alpha\right)+\left\|\mu(S_{\rm good}\cap
S_{t}^{(s)})-\mu_{t}^{(s)}\right\|_{2}^{2}$ $\displaystyle\leq$ $\displaystyle
O\left(\alpha\log 1/\alpha\right)+\left(\left\|\mu(S_{\rm good}\cap
S_{t}^{(s)})-\mu\right\|_{2}+\left\|\mu-\mu(S_{t}^{(s)})\right\|_{2}\right)^{2}+0.001\;\alpha\log
1/\alpha$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle O\left(\alpha\log
1/\alpha\right)+\left(O(\alpha\sqrt{\log
1/\alpha})+\sqrt{\alpha(\|M(S_{t}^{(s)})-{\mathbf{I}}\|_{2}+O(\alpha\log
1/\alpha))}\right)^{2}+0.001\;\alpha\log 1/\alpha$ $\displaystyle\leq$
$\displaystyle O\left(\alpha\log
1/\alpha\right)+\alpha\left(\|M(S_{t}^{(s)})-{\mathbf{I}}\|_{2}+O\left(\alpha\log
1/\alpha\right)\right)+O(\alpha^{2}\log 1/\alpha)++0.001\;\alpha\log 1/\alpha$
$\displaystyle\overset{(c)}{\leq}$
$\displaystyle\frac{1}{1000}\left(\frac{\|M(S_{t}^{(s)})-{\mathbf{I}}\|_{2}-0.001\;\alpha\log
1/\alpha}{5.5}-0.002\;\alpha\log 1/\alpha\right)$ $\displaystyle\leq$
$\displaystyle\frac{\psi_{t}^{(s)}-0.002\;\alpha\log 1/\alpha}{1000}$
$\displaystyle\leq$ $\displaystyle\frac{\psi}{1000}\;,$

where $(a)$ follows from Lemma G.4, $(b)$ follows from Lemma G.5 and Lemma G.7
and $(c)$ follows from our choice of large constant $C$.

∎

#####  F.3.3 Proof of Lemma F.5

###### Proof of Lemma F.5.

Under the conditions of Lemma F.7, we have picked $n$ large enough such that
with probability $1-O(1/\log^{3}d)$, we have

$\displaystyle\|\Sigma_{t+1}^{(s)}-{\mathbf{I}}\|_{2}\approx_{0.01}\|M(S_{t+1}^{(s)})-{\mathbf{I}}\|_{2}\;.$

By Lemma F.4, we now have

$\displaystyle\left\langle
M(S_{t+1}^{(s)})-{\mathbf{I}},U_{t}^{(s)}\right\rangle$ $\displaystyle\leq$
$\displaystyle 0.76\left\langle
M(S_{t}^{(s)})-{\mathbf{I}},U_{t}^{(s)}\right\rangle$ (17) $\displaystyle\leq$
$\displaystyle 0.76\left\langle
M(S_{1}^{(s)})-{\mathbf{I}},U_{t}^{(s)}\right\rangle$ $\displaystyle\leq$
$\displaystyle 0.76\|M(S_{1}^{(s)})-{\mathbf{I}}\|_{2}\;.$

Since $\lambda_{1}^{(s)}>C\alpha\log 1/\alpha$, we have
$\|M(S_{t+1}^{(s)})-{\mathbf{I}}\|_{2}>0.5(C-0.002)\alpha\log 1/\alpha$.
Combining the above inequality and the fifth claim of Lemma F.7 together, we
have

$\displaystyle\left\langle\Sigma_{t+1}^{(s)}-{\mathbf{I}},U_{t}^{(s)}\right\rangle\leq\left\langle
M(S_{t+1}^{(s)})-{\mathbf{I}},U_{t}^{(s)}\right\rangle+\|\Sigma_{t+1}^{(s)}-M(S_{t+1}^{(s)})\|_{2}\leq
0.77\|M(S_{1}^{(s)})-{\mathbf{I}}\|_{2}\;.$

By Lemma G.1, we have $M(S_{t+1}^{(s)})-{\mathbf{I}}\preceq
M(S_{1}^{(s)})-{\mathbf{I}}$. By our choice of $\alpha^{(s)}$, we have
$\alpha^{(s)}\left(M(S_{t+1}^{(s)})-{\mathbf{I}}\right)\preceq\frac{1}{100}{\mathbf{I}}$
and
$\alpha^{(s)}\left(\Sigma_{t+1}^{(s)}-{\mathbf{I}}\right)\preceq\frac{1}{100}{\mathbf{I}}$.
Therefore, by Lemma G.14, we have

$\displaystyle\left\|\sum_{t=1}^{T_{2}}\Sigma_{t+1}^{(s)}-{\mathbf{I}}\right\|_{2}$
$\displaystyle\leq$
$\displaystyle\sum_{t=1}^{T_{2}}\left\langle\Sigma_{t+1}^{(s)}-{\mathbf{I}},U_{t}^{(s)}\right\rangle+\alpha^{(s)}\sum_{t=1}^{T_{2}}\left\langle
U_{t}^{(s)},\left|\Sigma_{t+1}^{(s)}-{\mathbf{I}}\right|\right\rangle\|\Sigma_{t+1}^{(s)}-{\mathbf{I}}\|_{2}+\frac{\log(d)}{\alpha^{(s)}}$
$\displaystyle\overset{(a)}{\leq}$
$\displaystyle\sum_{t=1}^{T_{2}}\left\langle\Sigma_{t+1}^{(s)}-{\mathbf{I}},U_{t}^{(s)}\right\rangle+\frac{1}{100}\sum_{t=1}^{T_{2}}\left\langle
U_{t}^{(s)},\left|\Sigma_{t+1}^{(s)}-{\mathbf{I}}\right|\right\rangle+200\log(d)\|M(S_{1}^{(s)})-{\mathbf{I}}\|_{2}$

where $(a)$ follows from our choice of $\alpha^{(s)}$ and $C$. By Lemma G.6,
$M(S_{t+1}^{(s)})-{\mathbf{I}}\succeq-c_{1}\alpha\log 1/\alpha\cdot I$ for
$t=1,2,\cdots,T_{2}$, we have

$\displaystyle|M(S_{t+1}^{(s)})-{\mathbf{I}}|\preceq
M(S_{t+1}^{(s)})-{\mathbf{I}}+2c_{1}\alpha\log 1/\alpha\;{\mathbf{I}},$

and hence

$\displaystyle\left\langle
U_{t}^{(s)},\left|M(S_{t+1}^{(s)})-{\mathbf{I}}\right|\right\rangle\leq\left\langle
U_{t}^{(s)},M(S_{t+1}^{(s)})-{\mathbf{I}}\right\rangle+2c_{1}\alpha\log
1/\alpha$

Meanwhile, we have

$\displaystyle
M(S_{t+1}^{(s)})-{\mathbf{I}}-\|\Sigma_{t+1}^{(s)}-M(S_{t+1}^{(s)})\|_{2}\;{\mathbf{I}}\preceq\Sigma_{t+1}^{(s)}-{\mathbf{I}}\preceq
M(S_{t+1}^{(s)})-{\mathbf{I}}+\|\Sigma_{t+1}^{(s)}-M(S_{t+1}^{(s)})\|_{2}\;{\mathbf{I}}\;.$

Hence,

$\displaystyle|\Sigma_{t+1}^{(s)}-{\mathbf{I}}|\preceq
M(S_{t+1}^{(s)})-{\mathbf{I}}+(3\|\Sigma_{t+1}^{(s)}-M(S_{t+1}^{(s)})\|_{2}+2c_{1}\alpha\log
1/\alpha)\;{\mathbf{I}}$

Together with Eq. (17), we have

$\displaystyle\left\langle
U_{t}^{(s)},\left|\Sigma_{t+1}^{(s)}-{\mathbf{I}}\right|\right\rangle$
$\displaystyle\leq$ $\displaystyle\left\langle
U_{t}^{(s)},M(S_{t+1}^{(s)})-{\mathbf{I}}\right\rangle+3\|\Sigma_{t+1}^{(s)}-M(S_{t+1}^{(s)})\|_{2}+2c_{1}\alpha\log
1/\alpha$ $\displaystyle\leq$ $\displaystyle
0.79\;\left\|M(S_{1}^{(s)})-{\mathbf{I}}\right\|_{2}+2c_{1}\alpha\log
1/\alpha\;.$

By Lemma G.6, we have $M(S_{t+1}^{(s)})-{\mathbf{I}}\succeq-c_{1}\alpha\log
1/\alpha\;{\mathbf{I}}$. Also, we know $M(S_{t+1}^{(s)})-{\mathbf{I}}\preceq
M(S_{1}^{(s)})-{\mathbf{I}}$. Then we have

$\displaystyle\left\|M(S_{T_{2}+1}^{(s)})-{\mathbf{I}}\right\|_{2}$
$\displaystyle\leq$
$\displaystyle\frac{1}{T_{2}}\left\|\sum_{i=1}^{T_{2}}M({S_{t+1}^{(s)}})-{\mathbf{I}}\right\|_{2}$
$\displaystyle\leq$
$\displaystyle\frac{1}{T_{2}}\left\|\sum_{i=1}^{T_{2}}\Sigma_{t+1}^{(s)}-{\mathbf{I}}\right\|_{2}+0.001\;\alpha\log
1/\alpha$ $\displaystyle\leq$
$\displaystyle\frac{1}{T_{2}}\left(\sum_{t=1}^{T_{2}}\left\langle\Sigma_{t+1}^{(s)}-{\mathbf{I}},U_{t}^{(s)}\right\rangle+\frac{1}{100}\sum_{t=1}^{T_{2}}\left\langle
U_{t}^{(s)},\left|\Sigma_{t+1}^{(s)}-{\mathbf{I}}\right|\right\rangle+200\log(d)\|M(S_{1}^{(s)})-{\mathbf{I}}\|_{2}\right)+0.001\;\alpha\log
1/\alpha$ $\displaystyle\leq$ $\displaystyle
0.79\|M(S_{1}^{(s)})-{\mathbf{I}}\|_{2}+2c_{1}\alpha\log
1/\alpha+\frac{200\log(d)}{T_{2}}\|M(S_{1}^{(s)})-{\mathbf{I}}\|_{2}+0.001\;\alpha\log
1/\alpha$ $\displaystyle\leq$ $\displaystyle
0.98\;\|M(S_{1}^{(s)})-{\mathbf{I}}\|_{2}\;,$

where the last inequality follows from our assumption that
$\lambda_{0}^{(s)}>C\alpha\log 1/\alpha$, and conditions of Lemma F.7 hold and
we have $\|M(S_{t+1}^{(s)})-{\mathbf{I}}\|_{2}>0.5(C-0.002)\alpha\log
1/\alpha$. ∎

###  Appendix G Technical lemmas

####  G.1 Lemmata for sub-Gaussian regularity from [36]

######  Lemma G.1 ([36, Lemma 3.4] ).

If $S^{\prime}\subset S$, then $M(S^{\prime})\preceq M(S)$.

######  Definition G.2 ([36, Definition 4.1] ).

Let $D$ be a distribution with mean $\mu\in{\mathbb{R}}^{d}$ and covariance
${\mathbf{I}}$. For $0<\alpha<1/2$, we say a set of points
$S=\\{X_{1},X_{2},\cdots,X_{n}\\}$ is $\alpha$-subgaussian good with respect
to $\mu\in{\mathbb{R}}^{d}$ if following inequalities are satisfied:

  * •

$\|\mu(S)-\mu\|_{2}\lesssim\alpha\sqrt{\log 1/\alpha}$ and
$\left\|\frac{1}{|S|}\sum_{i\in
S}\left(X_{i}-\mu(S)\right)\left(X_{i}-\mu(S)\right)^{\top}-{\mathbf{I}}\right\|_{2}\lesssim\alpha\log
1/\alpha$.

  * •

for any subset $T\subset S$ so that $|T|=2\alpha|S|$, we have

$\displaystyle\left\|\frac{1}{|T|}\sum_{i\in
T}X_{i}-\mu\right\|_{2}\lesssim\sqrt{\log
1/\alpha}\;\;\text{and}\;\;\left\|\frac{1}{|T|}\sum_{i\in
T}\left(X_{i}-\mu(S)\right)\left(X_{i}-\mu(S)\right)^{\top}-{\mathbf{I}}\right\|_{2}\lesssim\log
1/\alpha\;.$

######  Lemma G.3 ([36, Lemma 4.1] ).

A set of i.i.d. samples from an identity covariance sub-Gaussian distribution
of size $n=\Omega\left(\frac{d+\log 1/\delta}{\alpha^{2}\log 1/\alpha}\right)$
is $\alpha$-subgaussian good with respect to $\mu$ with probability
$1-\delta$.

######  Lemma G.4 ([36, Fact 4.2] ).

Let $S$ be an $\alpha$-corrupted sub-Gaussian dataset under Assumption 1. If
$S_{\rm good}$ is $\alpha$-subgaussian good with respect to
$\mu\in{\mathbb{R}}^{d}$, then for any $T\subset S$ such that $|T|\leq
2\alpha|S|$, we have for any unit vector $v\in{\mathbb{R}}^{d}$

$\displaystyle\frac{1}{|S|}\sum_{X_{i}\in
T}\left\langle\left(X_{i}-\mu\right),v\right\rangle^{2}\lesssim\alpha\log
1/\alpha\;.$

For any subset $T\subset S$ such that $|T|\geq(1-2\alpha)|S|$, we have

$\displaystyle\left\|\frac{1}{|S|}\sum_{i\in
T}(x_{i}-\mu)(x_{i}-\mu)^{\top}-{\mathbf{I}}\right\|_{2}\lesssim\alpha\log
1/\alpha\;\text{ and }\;,$ $\displaystyle\left\|\frac{1}{|S|}\sum_{i\in
T}(x_{i}-\mu(T))(x_{i}-\mu(T))^{\top}-{\mathbf{I}}\right\|_{2}\lesssim\alpha\log
1/\alpha$

######  Lemma G.5 ([36, Corollary 4.3] ).

Let $S$ be an $\alpha$-corrupted sub-Gaussian dataset under Assumption 1. If
$S_{\rm good}$ is $\alpha$-subgaussian good with respect to
$\mu\in{\mathbb{R}}^{d}$, then for any $T\subset S$ such that $|T|\leq
2\alpha|S|$, we have

$\displaystyle\left\|\frac{1}{|S|}\sum_{X_{i}\in
T}\left(X_{i}-\mu\right)\right\|_{2}\lesssim\alpha\sqrt{\log 1/\alpha}\;.$

For any subset $T\subset S$ such that $|T|\geq(1-2\alpha)|S|$, we have

$\displaystyle\left\|\mu(T)-\mu\right\|_{2}\lesssim\alpha\sqrt{\log
1/\alpha}\;.$

######  Lemma G.6 ([36, Lemma 4.5] ).

Let $S$ be an $\alpha$-corrupted sub-Gaussian dataset under Assumption 1. If
$S_{\rm good}$ is $\alpha$-subgaussian good with respect to
$\mu\in{\mathbb{R}}^{d}$, then for any $T\subset S$ such that $|T\cap S_{\rm
good}|\geq(1-2\alpha)|S|$, then there is some universal constant $c_{1}$ such
that

$\displaystyle\frac{1}{|S|}\sum_{i\in
T}\left(x_{i}-\mu(T)\right)\left(x_{i}-\mu(T)\right)^{\top}\succeq(1-c_{1}\alpha\log
1/\alpha){\mathbf{I}}\;.$

######  Lemma G.7 ([36] Lemma 4.6 ).

Let $S$ be an $\alpha$-corrupted sub-Gaussian dataset under Assumption 1. If
$S_{\rm good}$ is $\alpha$-subgaussian good with respect to
$\mu\in{\mathbb{R}}^{d}$, then for any $T\subset S$ such that $|T\cap S_{\rm
good}|\geq(1-2\alpha)|S|$, we have

$\displaystyle\|\mu(T)-\mu\|_{2}\leq\frac{1}{1-\alpha}\cdot\left(\sqrt{\alpha\left(\left\|M(T)-{\mathbf{I}}\right\|_{2}+O\left(\alpha\log
1/\alpha\right)\right)}+O\left(\alpha\sqrt{\log 1/\alpha}\right)\right)\;.$

####  G.2 Auxiliary Lemmas on Laplace and Gaussian mechanism

######  Lemma G.8 (Theorem A.1 in [38]).

Let $\varepsilon\in(0,1)$ be arbitrary. For $c^{2}\geq 2\ln(1.25/\delta)$, the
Gaussian Mechanism with parameter $\sigma^{2}\geq
c^{2}\Delta_{2}f/\varepsilon$ is $(\varepsilon,\delta)$-differentially
private.

######  Lemma G.9.

Let $Y\sim{\rm Lap}(b)$. Then for all $h>0$, we have ${\mathbb{P}}(|Y|\geq
hb)=e^{-h}$.

######  Lemma G.10 (Tail bound of $\chi$-square distribution [77]).

Let $x_{i}\sim{\cal N}(0,\sigma^{2})$ for $i=1,2,\cdots,d$. Then for all
$\zeta\in(0,1)$, we have
${\mathbb{P}}(\|X\|_{2}\geq\sigma\sqrt{d\log(1/\zeta)})\leq\zeta$.

######  Lemma G.11 ([75, Corollary 2.3.6] ).

Let $Z\in{\mathbb{R}}^{d\times d}$ be a matrix such that $Z_{i,j}\sim{\cal
N}(0,\sigma^{2})$ for $i\geq j$ and $Z_{i,j}=Z_{j,i}$ for $i<j$. For
$\forall\zeta\in(0,1)$, then with probability $1-\zeta$ we have
$\left\|Z\right\|_{2}\leq\sigma\sqrt{d}\log(1/\zeta)$.

######  Lemma G.12 (Accuracy of the histogram using Gaussian Mechanism).

Let $f:\mathcal{X}^{n}\rightarrow{\mathbb{R}}^{\mathcal{S}}$ be a histogram
over $K$ bins. For any dataset $D\in{\cal X}^{n}$ and $\varepsilon$, Gaussian
Mechanism is an $(\varepsilon,\delta)$-differentially private algorithm $M(D)$
such that given

with probability $1-\zeta$ we have

$\displaystyle\|M(D)-f(D)\|_{\infty}\leq
O(\frac{\sqrt{\log({K}/{\zeta})\log(1/\delta)}}{\varepsilon n})\;.$

###### Proof.

First notice that the $\ell_{2}$ sensitivity of histogram function $f$ is
$\sqrt{2}/n$. Thus, by Lemma G.8, by adding noise ${\cal
N}(0,(\frac{2\sqrt{2\log(1.25/\delta)}}{n\varepsilon})^{2})$ to each entry of
$f$, we have a $(\varepsilon,\delta)$ differentially private algorithm. Since
Gaussian tail bound implies that $\mathbb{P}_{x\sim{\cal
N}(0,\sigma^{2})}[x\geq\Omega(\sqrt{\log(K/\eta)}\sigma)]\leq\eta/K$, we have
that with probability $1-\eta$, the $\ell_{\infty}$ norm of the added noise is
bounded by $O(\frac{\sqrt{\log(1/\delta)\log(K/\eta)}}{n\varepsilon})$. This
concludes the proof. ∎

######  Lemma G.13 (Composition theorem of [51, Theorem 3.4]).

For $\varepsilon\leq 0.9$, an end-to-end guarantee of
$(\varepsilon,\delta)$-differential privacy is satisfied if a dataset is
accessed $k$ times, each with a
$(\varepsilon/2\sqrt{2k\log(2/\delta)},\delta/2k)$-differential private
mechanism.

####  G.3 Analysis of $\|M(S_{t}^{(s)})-\mathbf{I}\|_{2}$ shrinking

For any symmetric matrix $A=\sum_{i=1}^{d}\lambda_{i}v_{i}v_{i}^{\top}$, we
let $|A|$ denote $|A|=\sum_{i=1}^{d}|\lambda_{i}|v_{i}v_{i}^{\top}$.

######  Lemma G.14 (Regret bound, Special case of [4, Theorem 3.1]).

Let

$U_{t}\;\;=\;\;\frac{\exp(\alpha\sum_{k=1}^{t-1}(\Sigma_{k}-{\mathbf{I}}))}{\operatorname{Tr}(\exp(\alpha\sum_{k=1}^{t-1}(\Sigma_{k}-{\mathbf{I}})))}\;,$

and $\alpha$ satisfies $\alpha(\Sigma_{t+1}-{\mathbf{I}})\preceq I$ for all
$k\in[T]$, then for all $U\succeq 0$, $\operatorname{Tr}(U)=1$, it holds that

$\displaystyle\sum_{t=1}^{T}\langle(\Sigma_{t+1}-{\mathbf{I}}),U-U_{t}\rangle\leq\alpha\sum_{t=1}^{T}\langle|(\Sigma_{t+1}-{\mathbf{I}}),U_{t}|\rangle\cdot\|(\Sigma_{t+1}-{\mathbf{I}})\|_{2}+\frac{\log
d}{\alpha}.$

Rearranging terms, and taking a supremum over $U$, we obtain that

$\displaystyle\|\sum_{t=1}^{T}(\Sigma_{t+1}-{\mathbf{I}})\|_{2}\leq\sum_{t=1}^{T}\langle
U_{t},(\Sigma_{t+1}-{\mathbf{I}})\rangle+\alpha\sum_{t=1}^{T}\langle|(\Sigma_{t+1}-{\mathbf{I}}),U_{t}|\rangle\cdot\|(\Sigma_{t+1}-{\mathbf{I}})\|_{2}+\frac{\log
d}{\alpha}.$

###  Appendix H Exponential time DP robust mean estimation of sub-Gaussian and
heavy tailed distributions (Algorithm 2)

In this section, we give a self-contained proof of the privacy and utility of
our exponential time robust mean estimation algorithm for sub-Gaussian and
heavy tailed distributions. The proof relies on the resilience property of the
uncorrupted data as shown in the following lemmas.

######  Lemma H.1 (Lemma 10 in [73]).

If a set of points $\\{x_{i}\\}_{i\in S}$ lying in ${\mathbb{R}}^{d}$ is
$(\sigma,\alpha)$-resilient around a point $\mu$, then

$\|\frac{1}{|T^{\prime}|}\sum_{i\in
T^{\prime}}(x_{i}-\mu)\|_{2}\leq\frac{2-\alpha}{\alpha}\sigma.$

for all sets $T^{\prime}$ of size at least $\alpha|S|$.

######  Lemma H.2 (Finite sample resilience of sub-Gaussian distributions [81,
Theorem G.1]).

Let $S_{\rm good}$ be a set of i.i.d. points from a sub-Gaussian distribution
$\cal{D}$ with a parameter ${\mathbf{I}}_{d}$. Given that $|S_{\rm
good}|=\Omega((d+\log(1/\zeta))/(\alpha^{2}\log 1/\alpha)\,)$, $S_{\rm good}$
is $(\alpha\sqrt{\log(1/\alpha)},\alpha)$-resilient around its mean $\mu$ with
probability $1-\zeta$.

######  Lemma H.3 (Finite sample resilience of heavy-tailed distributions [81,
Theorem G.2]).

Let $S_{\rm good}$ be a set of i.i.d. samples drawn from distribution
$\cal{D}$ whose mean and covariance are $\mu,\Sigma$ respectively, and that
$\Sigma\preceq I$. Given that $|S|=\Omega(d/(\zeta\alpha))$, there exists a
constant $c_{\zeta}$ that only depends on $\zeta$ such that $S_{\rm good}$ is
$(c_{\zeta}\sqrt{\alpha},\alpha)$-resilient around $\mu$ with probability
$1-\zeta$.

####  H.1 Case of heavy-tailed distributions and a proof of Theorem 8

Lemma K.1 ensures that $q_{\rm range-ht}$ returns samples in a bounded support
of Euclidean distance $\sqrt{d}B/2$ with $B=50/\sqrt{\alpha}$ where
$(1-2\alpha)n$ samples are uncorrupted ($\alpha n$ is corrupted by adversary
and $\alpha n$ can be corrupted by the pre-processing step). For a
$(c_{\zeta}\sqrt{3\alpha},3\alpha)$-resilient dataset, we first show that
$R(S)$ is robust against corruption.

######  Lemma H.4 ($\alpha$-corrupted data has small $R(S)$).

Let $S$ be the set of $2\alpha$-corrupted data. Given that
$n=\Omega(d/(\zeta\alpha))$, with probability $1-\zeta$, $R(S)\leq
c_{\zeta}\sqrt{3\alpha}$.

This follows immediately by selecting $S^{\prime}$ to be the uncorrupted
$(1-2\alpha)$ fraction of the dataset and applying
($c_{\zeta}\sqrt{3\alpha},3\alpha$)-resilience. After pre-processing, we have
that $\|x_{i}-\bar{x}\|_{2}\leq B\sqrt{d}/2$, and then clearly $R(\cdot)$ has
sensitivity $\Delta_{R}\leq B\sqrt{d}/n$.

######  Lemma H.5 (Sensitivity and Privacy of ${\hat{R}(S)}$).

Given that $\hat{R}(S)=R(S)+{\rm Lap}(\frac{3B\sqrt{d}}{n\varepsilon})$,
$\hat{R}(S)$ is $(\varepsilon/3,0)$-differentially private. Further, with
probability $1-\delta/3$,
$|\hat{R}(S)-R(S)|\leq\frac{3B\sqrt{d}\log(3/\delta)}{n\varepsilon}$.

In the algorithm, we first compute $\hat{R}(S)$. If $\hat{R}(S)\geq
2c_{\zeta}\sqrt{\alpha}$, we stop and output $\emptyset$. Otherwise, we use
exponential mechanism with score function $d(\hat{\mu},S)$ to find an estimate
$\hat{\mu}$. We prove the privacy guarantee of our algorithm as follows.

######  Lemma H.6 (Privacy).

Algorithm 2 is $(\varepsilon,\delta)$-differentially private if $n\geq
6B\sqrt{d}\log(3/\delta)/(c_{\zeta}\varepsilon\sqrt{\alpha})$.

###### Proof.

We consider neighboring datasets $S$, $S^{\prime}$ under the following two
scenario

  1. 1.

$R(S)>3c_{\zeta}\sqrt{\alpha}$

In this case, given that
$n\geq\frac{6B\sqrt{d}\log(3/\delta)}{c_{\zeta}\sqrt{\alpha}\varepsilon}$, we
have $\widehat{R}(S)>2c_{\zeta}\sqrt{\alpha}$ and the output of the algorithm
${\cal A}(S)=\emptyset$ with probability at least $1-\delta/3$, and ${\cal
A}(S^{\prime})=\emptyset$ with probability at least $1-\delta/3$. Thus, for
any set $Q$, ${\mathbb{P}}[{\cal A}(S)\in Q]\leq{\mathbb{P}}[{\cal
A}(S^{\prime})\in Q]+\delta/3$.

  2. 2.

$R(S)\leq 3c_{\zeta}\sqrt{\alpha}$

######  Lemma H.7 (Sensitivity of $d(\hat{\mu},S)$).

Given that $R(S)\leq 3c_{\zeta}\sqrt{\alpha}$, for any neighboring dataset
$S^{\prime}$, $|d(\hat{\mu},S)-d(\hat{\mu},S^{\prime})|\leq
12c_{\zeta}/(n\sqrt{\alpha})$.

In this case, the privacy guarantee of $\hat{R}(S)$ yields that
${\mathbb{P}}[{\hat{R}}(S)\in
Q]\leq\exp(\varepsilon/3)\cdot{\mathbb{P}}[{\hat{R}}(S^{\prime})\in Q]$. Lemma
H.7 yields that ${\mathbb{P}}[{\hat{\mu}}(S)\in
Q]\leq\exp(\varepsilon)\cdot{\mathbb{P}}[{\hat{\mu}}(S^{\prime})\in Q]$. A
simple composition of the privacy guarantee with $q_{\rm range-ht}$($\cdot$)
and the exponential mechanism gives that

${\mathbb{P}}[({\hat{R}}(S),\hat{\mu}(S))\in
Q]\leq\exp(\varepsilon)\cdot{\mathbb{P}}[({\hat{R}}(S^{\prime}),\hat{\mu}(S^{\prime}))\in
Q]+\delta/3$

This implies that ${\mathbb{P}}[{\cal A}(S)\in
Q]\leq\exp(\varepsilon)\cdot{\mathbb{P}}[{\cal A}(S^{\prime})\in Q]+\delta/3$.

∎

######  Lemma H.8 (Utility of the algorithm).

For an $2\alpha$-corrupted dataset $S$, Algorithm 2 achieves
$\|\hat{\mu}-\mu^{*}\|_{2}\leq c_{\zeta}\sqrt{\alpha}$ with probability
$1-\zeta$, if
$n=\Omega(d/(\alpha\zeta)+(d\log(d/\alpha^{1.5})+\log(1/\zeta)/(\varepsilon\alpha))$.

###### Proof of Lemma H.8.

We use the following lemma showing that $d(\hat{\mu},S)$ is a good
approximation of $\|\hat{\mu}-\mu^{*}\|_{2}$.

######  Lemma H.9 ($d(\mu,S)$ approximates $\|\mu-\mu^{*}\|$).

Let $S$ be the set of $2\alpha$-corrupted data. Given that
$n=\Omega(d/(\zeta\alpha))$, with probability $1-\zeta$,

$\big{|}\,d(\hat{\mu},S)-\|\hat{\mu}-\mu^{*}\|_{2}\,\big{|}\;\;\leq\;\;7c_{\zeta}\sqrt{\alpha}\;.$

This implies that the exponential mechanism achieves the following bounds.

$\displaystyle{\mathbb{P}}(\|\hat{\mu}-\mu^{*}\|\leq c_{\zeta}\sqrt{\alpha})$
$\displaystyle\geq$ $\displaystyle\frac{1}{A}e^{-\frac{\varepsilon\alpha
n}{3}}\,{\rm Vol}(c_{\zeta}\sqrt{\alpha},d)\text{, and}$
$\displaystyle{\mathbb{P}}(\|\hat{\mu}-\mu^{*}\|\geq
22c_{\zeta}\sqrt{\alpha})$ $\displaystyle\leq$
$\displaystyle\frac{1}{A}e^{-\frac{5\varepsilon\alpha n}{8}}\,B^{d}\;,$

where $A$ denotes the normalizing factor for the exponential mechanism and
${\rm Vol}(r,d)$ is the volume of a ball of radius $r$ in $d$ dimensions. It
follows that

$\displaystyle\log\Big{(}\frac{{\mathbb{P}}(\|\hat{\mu}-\mu^{*}\|_{2}\leq
c_{\zeta}\sqrt{\alpha})}{{\mathbb{P}}(\|\hat{\mu}-\mu^{*}\|_{2}\geq
22c_{\zeta}\sqrt{\alpha})}\Big{)}$ $\displaystyle\geq$
$\displaystyle\frac{7}{24}\varepsilon\alpha n-C\,d\log(dB/\alpha)$
$\displaystyle\geq$ $\displaystyle\log(1/\zeta)\;,$

for $n=\Omega((d\log(d/\alpha^{1.5})+\log(1/\zeta))/(\varepsilon\alpha))$.

∎

#####  H.1.1 Proof of Lemma H.7

Since $R(S)\leq 3c_{\zeta}\sqrt{\alpha}$, define $S_{\rm good}$ as the
minimizing subset in Definition 4.2 such that

$R(S)=\max_{T\subset S_{\rm good},|T|=(1-\alpha)|S_{\rm
good}|}\|\mu(T)-\mu(S_{\rm good})\|_{2}\;.$

By this definition of $S_{\rm good}$ and Lemma H.1,

$|v^{\top}(\mu(S_{\rm good}\cap{\cal T}^{v})-\mu(S_{\rm good}))|\leq
6c_{\zeta}\sqrt{1/\alpha},\text{ and }$ $|v^{\top}(\mu(S_{\rm good}\cap{\cal
B}^{v})-\mu(S_{\rm good}))|\leq 6c_{\zeta}\sqrt{1/\alpha}.$

Therefore,

$\min_{i\in S_{\rm good}\cap{\cal T}^{v}}|v^{\top}(x_{i}-\mu(S_{\rm
good}))|\leq|v^{\top}(\mu(S_{\rm good}\cap{\cal T}^{v})-\mu(S_{\rm
good}))|\leq 6c_{\zeta}\sqrt{1/\alpha},$

and similarly

$\min_{i\in S_{\rm good}\cap{\cal B}^{v}}|v^{\top}(x_{i}-\mu(S_{\rm
good}))|\leq|v^{\top}(\mu(S_{\rm good}\cap{\cal B}^{v})-\mu(S_{\rm
good}))|\leq 6c_{\zeta}\sqrt{1/\alpha}$

This implies

$\displaystyle\min_{i\in S_{\rm good}\cap{\cal T}^{v}}v^{\top}x_{i}-\max_{i\in
S_{\rm good}\cap{\cal
B}^{v}}v^{\top}x_{i}\;\;\leq\;\;12c_{\zeta}\sqrt{1/\alpha}\;.$ (18)

This implies that distribution of one-dimensional points
$S_{(v)}=\\{v^{\top}x_{i}\\}$ is dense at the boundary of top and bottom
$\alpha$ quantiles, and hence cannot be changed much by changing one entry.
Formally, consider a neighboring dataset $S^{\prime}$ (and the corresponding
$S^{\prime}_{(v)}$) where one point $x_{i}$ in ${\cal M}^{(v)}(S)$ is replaced
by another point $\tilde{x}_{i}$. If $v^{\top}\tilde{x}_{i}\in[\,\max_{i\in
S_{\rm good}\cap{\cal B}^{v}}v^{\top}x_{i}\,,\,\min_{i\in S_{\rm
good}\cap{\cal T}^{v}}v^{\top}x_{i}\,]$, then Eq. (18) implies that this only
changes the mean by $6c_{\zeta}/(\sqrt{\alpha}n)$. Otherwise, ${\cal
M}^{v}(S^{\prime})$ will have $x_{i}$ replaced by either $\arg\min_{i\in
S_{\rm good}\cap{\cal T}^{v}}v^{\top}x_{i}$ or $\arg\max_{i\in S_{\rm
good}\cap{\cal B}^{v}}v^{\top}x_{i}$. In both cases, Eq. (18) implies that
this only changes the mean by $12c_{\zeta}/(\sqrt{\alpha}n)$. The other case
of when the replaced sample $x_{i}\in S$ is not in ${\cal M}^{v}(S)$ follows
similarly. From this, we upper bounds the maximum difference between $S$ and
$S^{\prime}$ when projected on $v$, that is

$\left|v^{\top}\left(\mu({\cal M}^{v}(S))-\mu({\cal
M}^{v}(S^{\prime}))\right)\right|\leq\frac{12c_{\zeta}}{\sqrt{\alpha}n}\;.$

This implies the sensitivity of $d(\mu,S)$ is bounded by
$6c_{\zeta}/(\sqrt{\alpha}n)$:

$\displaystyle|d(\mu,S)-d(\mu,S^{\prime})|$ $\displaystyle=$
$\displaystyle\Big{|}\,\max_{v\in{\mathbb{S}}^{d-1}}\,v^{\top}\mu(M^{v}(S))\,-\max_{\tilde{v}\in{\mathbb{S}}^{d-1}}\,\tilde{v}^{\top}\mu(M^{v}(S^{\prime}))\,\,\Big{|}$
$\displaystyle\leq$
$\displaystyle\max_{v\in{\mathbb{S}}^{d-1}}\big{|}\,v^{\top}(\mu(M^{v}(S))\,-\mu(M^{v}(S^{\prime}))\,)\,\big{|}\;\leq\;\frac{12c_{\zeta}}{\sqrt{\alpha}\,n}$

#####  H.1.2 Proof of Lemma H.9

First we show $|v^{\top}\left(\mu({\cal M}^{v})-\mu^{*}\right)|\leq
7c_{\zeta}\sqrt{\alpha}$. Notice that $|S_{\rm good}\cap{\cal T}^{v}|\leq
3\alpha|S|$, and $|S_{\rm good}\cap{\cal B}^{v}|\leq 3\alpha|S|$. By the
($c_{\zeta}\sqrt{3\alpha},3\alpha$)-resilience property, we have
$|v^{\top}(\mu(S_{\rm good}\cap{\cal T}^{v})-\mu^{*})|\leq
c_{\zeta}\sqrt{3/\alpha}$, and $|v^{\top}(\mu(S_{\rm good}\cap{\cal
B}^{v})-\mu^{*})|\leq c_{\zeta}\sqrt{3/\alpha}$. Since $|S_{\rm good}\cap{\cal
M}^{v}|\geq(1-8\alpha)|S_{\rm good}|$, by the
$(c_{\zeta}\sqrt{8\alpha},8\alpha)$-resilience property,

$|v^{\top}(\mu(S_{\rm good}\cap{\cal
M}^{v})-\mu^{*})|\;\;\leq\;\;c_{\zeta}\sqrt{8\alpha}\;.$

Since ${\cal T}^{v}$, ${\cal B}^{v}$ are the largest and smallest $3\alpha n$
points respectively and $|S_{\rm bad}|\leq 2\alpha n$, we get

$|v^{\top}(\mu(S_{bad}\cap{\cal
M}^{v})-\mu^{*})|\;\;\leq\;\;2c_{\zeta}\sqrt{3/\alpha}.$

Combining $S_{\rm good}\cap{\cal M}^{v}$ and $S_{\rm bad}\cap{\cal M}^{v}$ we
get

$\displaystyle|v^{\top}(\mu({\cal M}^{v})-\mu^{*})|$
$\displaystyle\leq\frac{|S_{bad}\cap{\cal M}^{v}|}{|{\cal
M}^{v}|}|v^{\top}(\mu(S_{bad}\cap{\cal M}^{v})-\mu^{*})|+\frac{|\mu(S_{\rm
good}\cap{\cal M}^{v}|}{|{\cal M}^{v}|}|v^{\top}(\mu(S_{\rm good}\cap{\cal
M}^{v})-\mu^{*})|$ $\displaystyle\leq 7c_{\zeta}\sqrt{\alpha}.$

Finally we get that

$\displaystyle\big{|}\,d(\hat{\mu},S)-\|\hat{\mu}-\mu^{*}\|_{2}\,\big{|}$
$\displaystyle\overset{(a)}{=}\left|\max_{v\in\mathbb{S}^{d-1}}\left|v^{\top}\left(\mu({\cal
M}^{(v)})-\hat{\mu}\right)\right|-\max_{v\in\mathbb{S}^{d-1}}|v^{\top}(\hat{\mu}-\mu^{*})|\right|$
$\displaystyle\overset{(b)}{\leq}\max_{v\in\mathbb{S}^{d-1}}\left|v^{\top}\left(\mu({\cal
M}^{(v)})-\mu^{*}\right)\right|$ $\displaystyle\leq 7c_{\zeta}\sqrt{\alpha},$

where $(a)$ holds by the definition of the distance :

$\|\mu-\mu^{*}\|_{2}\;=\;\max_{v\in\mathbb{S}^{d-1}}|v^{\top}(\mu-\mu^{*})|,$

and $(b)$ holds by triangle inequality.

####  H.2 Case of sub-Gaussian distributions and a proof of Theorem 7

Th proof is analogous to the previous section, we only state the lemmas that
differ. $q_{\rm range}$ returns a hypercube $\bar{x}+[-B/2,B/2]^{d}$ that
includes all uncorrupted data points with a high probability.

######  Lemma H.10 ($\alpha$-corrupted data has small $R(S)$).

Let $S$ be the set of $\alpha$-corrupted data. Given that
$n=\Omega(\frac{d+\log(1/\zeta)}{\alpha^{2}\log 1/\alpha})$, with probability
$1-\zeta$, $R(S)\leq 3\,\alpha\sqrt{\log(1/3\alpha)}$.

######  Lemma H.11 (Privacy).

Algorithm 2 is $(\varepsilon,\delta)$-differentially private if $n\geq
3B\sqrt{d}\log(3/\delta)/(\varepsilon\alpha\sqrt{\log(1/\alpha)})$.

This follows from the following lemma.

######  Lemma H.12 (Sensitivity of $d(\hat{\mu},S)$).

Given that $R(S)\leq 3\alpha\sqrt{\log(1/\alpha)}$, for any neighboring
dataset $S^{\prime}$, $|d(\hat{\mu},S)-d(\hat{\mu},S^{\prime})|\leq
12\sqrt{\log 1/\alpha}/n$.

######  Lemma H.13 ($d(\hat{\mu},S)$ approximates $\|\hat{\mu}-\mu^{*}\|$).

Let $S$ be the set of $\alpha$-corrupted data. Given that
$n=\Omega(\frac{d+\log(1/\zeta)}{\alpha^{2}\log 1/\alpha})$, with probability
$1-\zeta$,

$\big{|}\,d(\hat{\mu},S)-\|\hat{\mu}-\mu^{*}\|_{2}\,\big{|}\;\;\leq\;\;14\,\alpha\,\sqrt{\log
1/\alpha}\;.$

This implies the following utility bound.

######  Lemma H.14 (Utility of the algorithm).

For an $\alpha$-corrupted dataset $S$, Algorithm 2 achieves
$\|\hat{\mu}-\mu^{*}\|_{2}\leq\alpha\sqrt{\log 1/\alpha}$ with probability
$1-\zeta$, if
$n=\Omega((d+\log(1/\zeta))/(\alpha^{2}\log(1/\alpha))+(d\log(d\sqrt{\log(dn/\zeta)}/\alpha)+\log(1/\zeta)/(\varepsilon\alpha))$.

###  Appendix I Background on exponential time approaches for Gaussian
distributions

In this section, we provide a background on exponential time algorithms that
achieve optimal guarantees but only applies to and heavily relies on the
assumption that samples are drawn from a Gaussian distribution. In §4, we
introduce a novel exponential time approach that seamlessly generalizes to
both sub-Gaussian and covariance-bounded distributions.

We introduce Algorithm 14, achieving the optimal sample complexity of
$\widetilde{O}(d/\min\\{\alpha\varepsilon,\alpha^{2}\\})$ (Theorem 12). The
main idea is to find an approximate Tukey median (which is known to be a
robust estimate of the mean [82]), using the exponential mechanism of [69] to
preserve privacy.

Tukey median set. For any set of points
$S=\\{x_{i}\in{\mathbb{R}}^{d}\\}_{i=1}^{n}$ and
$\hat{\mu}\in{\mathbb{R}}^{d}$, the Tukey depth is defined as the minimal
empirical probability density on one side of a hyperplane that includes
$\hat{\mu}$:

$\displaystyle D_{\rm
Tukey}(S,\hat{\mu})\;=\;\inf_{v\in{\mathbb{R}}^{d}}{\mathbb{P}}_{x\sim\hat{p}_{n}}(v^{\top}(x-\hat{\mu})\geq
0)\;,$

where $\hat{p}_{n}$ is the empirical distribution of $S$. The Tukey median set
is defined as the set of points achieving the maximum Tukey depth, which might
not be unique. Tukey median reduces to median for $d=1$, and is a natural
generalization of the median for $d>1$. Inheriting robustness of one-
dimensional median, Tukey median is known to be a robust estimator of the
multi-dimensional mean under an adversarial perturbation. In particular, under
our model, it achieves the optimal sample complexity and accuracy. This
optimality follows from the well-known fact that the sample complexity of
$O((1/\alpha^{2})({d+\log(1/\zeta))})$ cannot be improved upon even if we have
no corruption, and the fact that the accuracy of $O(\alpha)$ cannot be
improved upon even if we have infinite samples [82]. However, finding a Tukey
median takes exponential time scaling as $\tilde{O}(n^{d})$ [67].

######  Corollary I.1 (Corollary of [82, Theorem 3]).

For a dataset of $n$ i.i.d. samples from a $d$-dimensional Gaussian
distribution ${\cal N}(\mu,{\mathbf{I}}_{d})$, an adversary corrupts an
$\alpha\in(0,1/4)$ fraction of the samples as defined in Assumption 1. Then,
any $\hat{\mu}$ in the Tukey median set of a corrupted dataset $S$ satisfies
$\|\hat{\mu}-\mu\|_{2}=O(\alpha)$ with probability at least $1-\zeta$ if
$n=\Omega((1/\alpha^{2})(d+\log(1/\zeta)))$.

Exponential mechanism. The exponential mechanism was introduced in [69] to
elicit approximate truthfulness and remains one of the most popular private
mechanisms due to its broad applicability. It can seamlessly handle queries
with non-numeric outputs, such as routing a flow or finding a graph. Consider
a utility function $u(S,\hat{\mu})\in{\mathbb{R}}$ on a dataset $S$ and a
variable $\hat{\mu}$, where higher utility is preferred. Instead of truthfully
outputting $\arg\max_{\hat{\mu}}u(S,\hat{\mu})$, the exponential mechanism
outputs a randomized approximate maximizer sampled from the following
distribution:

$\displaystyle
r_{S}(\hat{\mu})\;=\;\frac{1}{Z_{S}}e^{\frac{\varepsilon}{2\,\Delta_{u}}u(S,\hat{\mu})}\;,$
(19)

where $\Delta_{u}=\max_{\hat{\mu},S\sim
S^{\prime}}|u(S,\hat{\mu})-u(S^{\prime},\hat{\mu})|$ is the sensitivity of $u$
(from Definition 1.2) and $Z_{S}$ ensures normalization to one. This mechanism
is $(\varepsilon,0)$-differentially private, since
$e^{\frac{\varepsilon}{2\Delta_{u}}|u(S,\hat{\mu})-u(S^{\prime},\hat{\mu})|}\leq
e^{{\varepsilon}/{2}}$ and $e^{-\varepsilon/2}\leq Z_{S}/Z_{S^{\prime}}\leq
e^{\varepsilon/2}$.

######  Proposition I.2 ([69, Theorem 6] ).

The sampled $\hat{\mu}$ from the distribution (19) is
$(\varepsilon,0)$-differentially private.

This naturally leads to the following algorithm. The privacy guarantee follows
immediately since the Tukey depth has sensitivity $1/n$, i.e., $|\,D_{\rm
Tukey}(S_{n},\hat{\mu})-D_{\rm Tukey}(S^{\prime}_{n},\hat{\mu})\,|\leq 1/n$
for all $\hat{\mu}\in{\mathbb{R}}^{d}$ and two neighboring databases
$S_{n}\sim S_{n}^{\prime}$ of size $n$. In this section, for the analysis of
private Tukey median, we assume the mean is from a known bounded set of the
form $[-R,R]^{d}$ for some known $R>0$.

Output a random data point $\hat{\mu}\in[-2R,2R]^{d}$ sampled from a density
$r(\hat{\mu})\;\propto\;e^{(1/2)\varepsilon nD_{\rm Tukey}(S,\hat{\mu})}\;.$

Algorithm 14 Private Tukey median

The private Tukey median achieves the following near optimal guarantee, whose
proof is provided in §J. The accuracy of $O(\alpha)$ and sample complexity of
$n=\Omega((1/\alpha^{2})(d+\log(1/\zeta)))$ cannot be improved even without
privacy (cf. Corollary I.1), and $n=\tilde{\Omega}(d/(\alpha\varepsilon))$ is
necessary even without any corruption [52, Theorem 6.5].

######  Theorem 12.

Under the hypotheses of Corollary I.1, there exists a universal constant $c>0$
such that if $\mu\in[-R,R]^{d}$, $\alpha\leq\min\\{c,R\\}$ and
$n=\Omega((1/\alpha^{2})(d+\log(1/\zeta))+(1/\alpha\varepsilon)d\log(dR/\zeta\alpha))$,
then Algorithm 14 is $(\varepsilon,0)$-differentially private and achieves
$\|\hat{\mu}-\mu\|_{2}=O(\alpha)$ with probability $1-\zeta$.

The private Tukey median, however, is a conceptual algorithm since we cannot
sample from $r(\hat{\mu})$. The ${\cal A}_{FindTukey}$ algorithm from [9]
approximately finds the Tukey median privately. This achieves $O(\alpha)$
accuracy with
$n=\tilde{\Omega}(d^{3/2}\log(1/\delta)/(\alpha\varepsilon)+(1/\alpha^{2})(d+\log(1/\zeta)))$,
but it still requires a runtime of $O(n^{{\rm poly}(d)})$. Alternatively, we
can sample from an $\alpha$-cover of $[-2R,2R]^{d}$, which has
$O((dR/\alpha)^{d})$ points. However, evaluating the Tukey depth of a point is
an NP-hard problem [5], requiring a runtime of $\tilde{O}(n^{d-1})$ [66]. The
runtime of the discretized private Tukey median is
$\tilde{O}(n^{-1}(dnR/\alpha)^{d})$. Similarly, [14] introduced an exponential
mechanism over the $\alpha$-cover with a novel utility function achieving the
same guarantee as Theorem 12, but this requires a runtime of
$O(n(dR/\alpha)^{2d})$.

###  Appendix J Proof of Theorem 12 on the accuracy of the exponential
mechanism for Tukey median

First, the $(\varepsilon,0)$-differential privacy guarantee of private Tukey
median follows as a corollary of Proposition I.2, by noting that sensitivity
of $n\,D_{\rm Tukey}({\cal D}_{n},x)$ is one, where ${\cal D}_{n}$ is a
dataset of size $n$. This follows from the fact that for any fixed $x$ and
$v$, $|\\{z\in{\cal D}_{n}:(v^{\top}(x-z))\geq 0\\}|$ is the number of samples
on one side of the hyperplane, which can change at most by one if we change
one sample in ${\cal D}$.

Next, given $n$ i.i.d samples $X_{1},X_{2},\ldots X_{n}$ from distribution
$p$, denote $\hat{p}_{n}$ as the empirical distribution defined by the samples
$X_{1},X_{2},\ldots X_{n}$. Denote $\tilde{p}_{n}$ as the distribution that is
corrupted from $\hat{p}_{n}$. We slightly overload the definition of Tukey
depth to denote $D_{\text{Tukey}}(p,x)$ as the Tukey depth of point
$x\in{\mathbb{R}}^{d}$ under distribution $p$, which is defined as

$D_{{\text{Tukey}}}(p,x)=\inf_{v\in{\mathbb{R}}^{d}}{\mathbb{P}}_{z\sim
p}(v^{\top}(x-z)\geq 0).$

Note that this is the standard definition of Tukey depth. First we show that
for $n$ large enough, the Tueky depth for the empirical distribution is close
to that of the true distribution. We provide proofs of the following lemmas
later in this section.

######  Lemma J.1.

With probability $1-\delta$, for any $p$ and $x\in{\mathbb{R}}^{d}$,

$|D_{\text{Tukey}}(p,x)-D_{\text{Tukey}}(\hat{p}_{n},x)|\leq
C\cdot\sqrt{\frac{d+1+\log(1/\delta)}{n}}.$

The proof of Lemma J.1can be found in §J.1. This allows us to use the known
Tukey depths of a Gaussian distribution to bound the Tukey depths of the
corrupted empirical one. We use this to show that there is a strict separation
between the Tueky depth of a point in $S_{1}=\\{x:\|x-\mu\|\leq\alpha\\}$ and
a point in $S_{2}=\\{x:\|x-\mu\|\geq 10\alpha\\}$. The proof of Lemma J.2 can
be found in §J.2.

######  Lemma J.2.

Define $p=\mathcal{N}(\mu,I)$, and assume $\alpha<0.01$. Given that
$n=\Omega(\alpha^{-2}(d+\log(1/\delta)))$, with probability $1-\delta$,

  1. 1.

For any point $x\in{\mathbb{R}}^{d}$, $\|x-\mu\|\leq\alpha$, it holds that

$D_{\text{Tukey}}(\tilde{p}_{n},x)\geq\frac{1}{2}-2\alpha$

  2. 2.

For any point $x\in{\mathbb{R}}^{d}$, $\|x-\mu\|\geq 10\alpha$, it holds that

$D_{\text{Tukey}}(\tilde{p}_{n},x)\leq\frac{1}{2}-5\alpha.$

This implies that most of the probability mass of the exponential mechanism is
concentrated inside a ball of radius $O(\alpha)$ around the true mean $\mu$.
Hence, with high probability, the exponential mechanism outputs an approximate
mean that is $O(\alpha)$ close to the true one. The following lemma finishes
the proof the the desired claim, whose proof can be found in §J.3.

######  Lemma J.3 (Utility).

Denote $\tilde{p}_{n}$ as the distribution that is corrupted from
$\hat{p}_{n}$. Suppose $x$ is sampled from $[-2R,2R]^{d}$ with density
$r(x)\propto\exp(-(1/2)\varepsilon nD_{\text{Tukey}}(\tilde{p}_{n},x))$, then
given
$n=\Omega(\,(d/(\alpha\varepsilon))\log(dR/\eta\alpha)+(1/\alpha^{2})(d+\log(1/\eta))\,)$
and $\mu\in[-R,R]^{d}$, and $R\geq\alpha$,

${\mathbb{P}}({\|x-\mu\|\leq 5\alpha})\geq 1-\eta\;.$

####  J.1 Proof of Lemma J.1

From the VC inequality ([25], Chap 2, Chapter 4.3) and the fact that the
family of sets $\\{\\{z|v^{\top}z\geq
t\\}|\|v\|=1,t\in{\mathbb{R}},v\in{\mathbb{R}}^{d}\\}$ has VC dimension $d+1$,
there exists some universal constant $C$ such that with probability at least
$1-\delta$

$\sup_{t\in{\mathbb{R}},v\in{\mathbb{R}}^{d},\|v\|=1}|{\mathbb{P}}_{z\sim
p}(v^{\top}z\geq t)-{\mathbb{P}}_{z\sim\hat{p}_{n}}(v^{\top}z\geq t)|\leq
C\cdot\sqrt{\frac{d+1+\log(1/\delta)}{n}},$

which implies, for any $x\in{\mathbb{R}}^{d}$,

$\sup_{v\in{\mathbb{R}}^{d}}|{\mathbb{P}}_{z\sim p}(v^{\top}(x-z)\geq
0)-{\mathbb{P}}_{z\sim\hat{p}_{n}}(v^{\top}(x-z)\geq 0)|\leq
C\cdot\sqrt{\frac{d+1+\log(1/\delta)}{n}},$

by letting $t=v^{\top}x$. We conclude the proof since

$\displaystyle|D_{\text{Tukey}}(p,x)-D_{\text{Tukey}}(\hat{p}_{n},x)|$
$\displaystyle=|\inf_{v\in{\mathbb{R}}^{d}}{\mathbb{P}}_{z\sim
p}(v^{\top}(x-z)\geq
0)-\inf_{v\in{\mathbb{R}}^{d}}{\mathbb{P}}_{z\sim\hat{p}_{n}}(v^{\top}(x-z)\geq
0)|$ $\displaystyle\leq\sup_{v\in{\mathbb{R}}^{d}}|{\mathbb{P}}_{z\sim
p}(v^{\top}(x-z)\geq 0)-{\mathbb{P}}_{\hat{p}_{n}}(v^{\top}(x-z)\geq 0)|$
$\displaystyle\leq C\cdot\sqrt{\frac{d+1+\log(1/\delta)}{n}}.$

####  J.2 Proof of Lemma J.2

For the first claim, we first prove a lower bound on $D_{\text{Tukey}}(p,x)$.
Since $p=\mathcal{N}(\mu,I)$, for any $v\in{\mathbb{R}}^{d}$ such that
$\|v\|_{2}=1$,

$\displaystyle{\mathbb{P}}_{z\sim p}(v^{\top}(z-x)\geq 0)$
$\displaystyle={\mathbb{P}}_{z\sim N(0,1)}(z\geq v^{\top}(x-\mu))$
$\displaystyle=\int_{v^{\top}(x-\mu)}^{\infty}\frac{1}{\sqrt{2\pi}}\exp(-z^{2}/2)dz$
$\displaystyle\geq\frac{1}{2}-\frac{1}{\sqrt{2\pi}}v^{\top}(x-\mu)$
$\displaystyle\geq\frac{1}{2}-\frac{1}{\sqrt{2\pi}}\|x-\mu\|_{2}$
$\displaystyle\geq\frac{1}{2}-\frac{1}{\sqrt{2\pi}}\alpha$

Thus,

$\displaystyle D_{\text{Tukey}}(p,x)$
$\displaystyle=\inf_{v\in{\mathbb{R}}^{d}}{\mathbb{P}}_{z\sim
p}(v^{\top}(x-z)\geq 0)$
$\displaystyle\geq\frac{1}{2}-\frac{1}{\sqrt{2\pi}}\alpha$

Then Lemma J.1 implies that with probability $1-\delta$

$D_{\text{Tukey}}(\hat{p}_{n},x)\geq\frac{1}{2}-\frac{1}{\sqrt{2\pi}}\alpha-C\cdot\sqrt{\frac{d+1+\log(1/\delta)}{n}}.$

Since the corruption can change at most $\alpha$ probability mass, it holds
that
$|D_{\text{Tukey}}(\tilde{p}_{n},x)-D_{\text{Tukey}}(\hat{p}_{n},x)|\leq\alpha$.
Setting $n=\Omega(\alpha^{-2}(d+\log(1/\delta)))$ yields

$\displaystyle
D_{\text{Tukey}}(\tilde{p}_{n},x)\geq\frac{1}{2}-\frac{1}{\sqrt{2\pi}}\|x-\mu\|_{2}-C\cdot\sqrt{\frac{d+1+\log(1/\delta)}{n}}-\alpha$
$\displaystyle\geq\frac{1}{2}-2\alpha.$

For the second claim, note that

$\displaystyle D_{\text{Tukey}}(p,x)$ $\displaystyle\leq$
$\displaystyle\int_{v^{\top}(x-\mu)}^{\infty}\frac{1}{\sqrt{2\pi}}\exp(-z^{2}/2)dz$
$\displaystyle\overset{(a)}{\leq}$
$\displaystyle\frac{1}{2}-\frac{1}{\sqrt{2\pi}}\exp(-(20\alpha)^{2}/2)\cdot
20\alpha$ $\displaystyle\overset{(b)}{\leq}$
$\displaystyle\frac{1}{2}-7\alpha$

where (a) holds since $\|x-\mu\|\geq 20\alpha$, and it is easy to verify that
(b) holds for $\alpha\leq 0.01$. The second claim holds since

$\displaystyle D_{\text{Tukey}}(\tilde{p}_{n},x)$ $\displaystyle\leq$
$\displaystyle D_{\text{Tukey}}(\hat{p}_{n},x)+\alpha$ $\displaystyle\leq$
$\displaystyle
D_{\text{Tukey}}(p,x)+\alpha+C\cdot\sqrt{\frac{d+1+\log(1/\delta)}{n}}$
$\displaystyle\overset{(a)}{\leq}$ $\displaystyle
D_{\text{Tukey}}(p,x)+2\alpha$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}-5\alpha,$

where $(a)$ holds by setting $n=\Omega(\alpha^{-2}(d+\log(1/\delta)))$.

####  J.3 Proof of Lemma J.3

Let $r(x)=\frac{1}{A}\exp(-\varepsilon nD_{\text{Tukey}}(\tilde{p}_{n},x))$
where $A$ is the normalization factor. Then

${\mathbb{P}}({\|x-\mu\|\leq\alpha})\geq\frac{1}{A}\exp(\varepsilon
n(\frac{1}{2}-2\alpha))\cdot\frac{\pi^{d/2}}{\Gamma(d/2+1)}\alpha^{d},$

using the fact that $\mu\in[-R,R]^{d}$ and that $R\geq\alpha$, and

${\mathbb{P}}({\|x-\mu\|\geq 5\alpha})\leq\frac{1}{A}\exp(\varepsilon
n(\frac{1}{2}-10\alpha))\cdot{(4R)}^{d}.$

Hence

$\log(\frac{{\mathbb{P}}({\|x-\mu\|\leq\alpha})}{{\mathbb{P}}({\|x-\mu\|\geq
5\alpha})})\geq\varepsilon n(3\alpha)-C\cdot d\log(dR/\alpha),$

where $C$ is an absolute constant. If we set
$n=\Omega(\frac{d\log(dB/\delta\alpha)}{\alpha\varepsilon})$, we get that

$\frac{{\mathbb{P}}({\|x-\mu\|\leq\alpha})}{{\mathbb{P}}({\|x-\mu\|\geq
5\alpha})}\geq\frac{10}{\delta},$

which implies that with probability at least $1-\delta$, $\|x-\mu\|\leq
5\alpha$.

###  Appendix K The algorithmic details and the analysis of PRIME-ht for
covariance bounded distributions

We provide the algorithm and the analysis for the range estimation query
$q_{\rm range-ht}$, and then prove the result on analyzing PRIME-ht.

####  K.1 Range estimation with $q_{\rm range-ht}$

Input: $S=\\{x_{i}\\}_{i=1}^{n}$, $\varepsilon$, $\delta$, $\zeta$

1 Randomly partition the dataset $S=\cup_{\ell\in[m]}S^{(\ell)}$ with
$m=200\log(2/\zeta)$

2 $\bar{x}^{(\ell)}\leftarrow q_{\rm
range}(S^{(\ell)},\varepsilon/m,\delta/m,\sigma=40$) for all $\ell\in[m]$

3 $\hat{x}_{j}\leftarrow{\rm median}(\\{\bar{x}_{j}^{(\ell)}\\}_{\ell\in[m]})$
for all $j\in[d]$

Output: $(\hat{x},B=50/\sqrt{\alpha})$

Algorithm 15 Differentially private range estimation for covariance bounded
distributions ($q_{\rm range-ht}$) [54, Algorithm 2]

######  Lemma K.1.

$q_{\rm range-ht}$ is $(\varepsilon,\delta)$-differentially private. Under
Assumption 2 and for $\alpha\in(0,0.01)$, if
$n=\Omega((1/\alpha)\log(1/\zeta)+(\sqrt{d\log(1/\delta)}\log(1/\zeta)\log(d/\delta)/\varepsilon))$,
$q_{\rm range-ht}$ returns a ball ${\cal B}_{\sqrt{d}B/2}(\bar{x})$ of radius
$\sqrt{d}B/2$ centered at $\bar{x}$ that includes $(1-2\alpha)n$ uncorrupted
samples where $B=50/\sqrt{\alpha}$ with probability $1-\zeta$.

We first show that applying the private histogram to each coordinate provides
a robust estimate of the range, but with a constant probability 0.9.

######  Lemma K.2 (Robustness of a single private histogram).

Under the $\alpha$-corruption model of Assumption 2, if
$n=\Omega(\sqrt{d\log(1/\delta)}\log(d/\delta)/\varepsilon)$, for
$\alpha\in(0,0.01)$, $q_{\rm range}$ in Algorithm 5 with a choice of
$\sigma=40$ and $B=120$ returns intervals $\\{I_{j}\\}_{j=1}^{d}$ of size
$|I_{j}|=240$ such that $\mu_{j}\in I_{j}$ with probability 0.9 for each
$j\in[d]$.

###### Proof of Lemma K.2.

The proof is analogous to Appendix D.1 and we only highlight the differences
here. By Lemma D.1 we know that $|\tilde{p}_{k}-\hat{p}_{k}|\leq 0.01$ with
the assumption on $n$. The corruption can change the normalized count in each
bin by $\alpha\leq 0.01$ by assumption. It follows from Chebyshev inequality
that ${\mathbb{P}}(|x_{i,j}-\mu_{j}|^{2}>\sigma^{2})\leq 1/\sigma^{2}$. It
follows from (e.g. [54, Lemma A.3]) that
${\mathbb{P}}(|\\{i:x_{i,j}\notin[\mu-\sigma,\mu+\sigma]\\}|>(100/\sigma^{2})n)<0.05$.
Hence the maximum bin has $\tilde{p}_{k}\geq 0.5(1-100/\sigma^{2})-0.02$ and
the true mean is in the maximum bin or in an adjacent bin. The largest non-
adjacent bucket is at most $100/\sigma^{2}+0.02$. Hence, the choice of
$\sigma=40$ ensures that we find the $\mu$ within $3\sigma=120$.

∎

Following [54, Algorithm 2], we partition the dataset into
$m=200\log(2/\zeta)$ subsets of an equal size $n/m$ and apply the median-of-
means approach. Applying Lemma K.2, it is ensured (e.g., by [54, Lemma A.4])
that more than half of the partitions satisfy that the center of the interval
is within 240 away from $\mu$, with probability $1-\zeta$. Therefore the
median of those $m$ centers is within $240$ from the true mean in each
coordinate. This requires the total sample size larger only by a factor of
$\log(d/\zeta)$.

To choose a radius $\sqrt{d}B/2$ ball around this estimated mean that includes
$1-\alpha$ fraction of the points, we choose $B=25/\sqrt{\alpha}$. Since
$\|\hat{\mu}-\mu\|_{2}\leq 120\sqrt{d}\ll\sqrt{d}B/2$ for $\alpha\leq 0.01$,
this implies that we can choose $\sqrt{d}B/2$-ball around the estimated mean
with $B=50/\sqrt{\alpha}$.

Let $z_{i}={\mathbb{I}}(\|x_{i}-\mu\|_{2}>\sqrt{d}B/2)$. We know that
${\mathbb{E}}[z_{i}]={\mathbb{P}}[(\|x_{i}-\mu\|_{2}>\sqrt{d}B/2)]\leq{\mathbb{E}}[\|x_{i}-\mu\|_{2}^{2}(2/dB^{2})]=(1/1250)\alpha$.
Applying multiplicative Chernoff bound (e.g., in [54, Lemma A.3]), we get
$|\\{i:\|x_{i}-\mu\|_{2}\leq\sqrt{d}B/2\\}|\geq 1-(3/2500)\alpha$ with
probability $1-\zeta$, if $n=\Omega((1/\alpha)\log(1/\zeta))$. This ensures
that with high probability, $(1-\alpha)$ fraction of the original uncorrupted
points are included in the ball. Since the adversary can corrupt $\alpha n$
samples, at least $(1-2\alpha)n$ of the remaining good points will be inside
the ball.

####  K.2 Proof of Theorem 9

The proof of the privacy guarantee of Algorithm 16 follows analogously from
the proof of the privacy of PRIME and is omitted here. The accuracy guarantee
follows form the following theorem and Lemma K.1.

######  Theorem 13 (Analysis of accuracy of DPMMWfilter-ht).

Let $S$ be an $\alpha$-corrupted covariance bounded dataset under Assumption
2, where $\alpha\leq c$ for some universal constant $c\in(0,1/2)$. Let $S_{\rm
good}$ be $\alpha$-good with respect to $\mu\in{\mathbb{R}}^{d}$. Suppose
${\cal D}=\\{x_{i}\in{\cal B}_{\sqrt{d}B/2}(\bar{x})\\}_{i=1}^{n}$ be the
projected dataset. If
$n\geq\widetilde{\Omega}\left(\frac{d^{3/2}B^{2}\log(1/\delta)}{\varepsilon}\right)$,
then DPMMWfilter-ht terminates after at most $O(\log dB^{2})$ epochs and
outputs $S^{(s)}$ such that with probability $0.9$, we have $|S_{t}^{(s)}\cap
S_{\mathrm{good}}|\geq(1-10\alpha)n$ and

$\displaystyle\|\mu(S^{(s)})-\mu\|_{2}\lesssim\sqrt{\alpha}\;.$

Moreover, each epoch runs for at most $O(\log d)$ iterations.

Input: $S=\\{x_{i}\in{\cal B}_{\sqrt{d}B/2}(\bar{x})\\}_{i=1}^{n}$,
$\alpha\in(0,1)$, $T_{1}=O(\log B\sqrt{d}),T_{2}=O(\log d)$,
$B\in{\mathbb{R}}_{+}$, $(\varepsilon,\delta)$

1 if $n<(4/\varepsilon_{1})\log(1/(2\delta_{1}))$ then Output: $\emptyset$

2 Initialize $S^{(1)}\leftarrow[n]$,
$\varepsilon_{1}\leftarrow\varepsilon/(4T_{1})$,
$\delta_{1}\leftarrow\delta/(4T_{1})$,
$\varepsilon_{2}\leftarrow\min\\{0.9,\varepsilon\\}/(4\sqrt{10T_{1}T_{2}\log(4/\delta)})$,
$\delta_{2}\leftarrow\delta/(20T_{1}T_{2})$, a large enough constant $C>0$

3 for  _epoch $s=1,2,\ldots,T_{1}$_ do

4
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\lambda^{(s)}}\leftarrow\|M(S^{(s)})\|_{2}+{\rm
Lap}(2B^{2}d/(n\varepsilon_{1}))$

5 $n^{(s)}\leftarrow|S^{(s)}|+{\rm Lap}(1/\varepsilon_{1})$

6 if $n^{(s)}\leq 3n/4$ then terminate

7 if  _$\lambda^{(s)}\leq C$ _ then

Output:
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mu^{(s)}}\leftarrow(1/|S^{(s)}|)\big{(}\sum_{i\in
S^{(s)}}x_{i}\big{)}+{\cal
N}(0,(2B\sqrt{2d\log(1.25/\delta_{1})}/({n\,\varepsilon_{1}}))^{2}{\mathbf{I}}_{d\times
d})$

8

9 $\alpha^{(s)}\leftarrow 1/(100(0.1/C+1.05)\lambda^{(s)})$

10 $S^{(s)}_{1}\leftarrow S^{(s)}$

11 for  _$t=1,2,\ldots,T_{2}$_ do

12
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\lambda_{t}^{(s)}}\leftarrow\|M(S_{t}^{(s)})\|_{2}+{\rm
Lap}(2B^{2}d/(n\varepsilon_{2}))$

13 if  _$\lambda_{t}^{(s)}\leq 2/3\lambda_{0}^{(s)}$_ then

14 terminate epoch

15 else

16
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Sigma_{t}^{(s)}}\leftarrow
M(S_{t}^{(s)})+{\cal
N}(0,(4B^{2}d\sqrt{2\log(1.25/\delta_{2})}/(n\varepsilon_{2}))^{2}{\mathbf{I}_{d^{2}\times
d^{2}}})$

17
$U_{t}^{(s)}\leftarrow(1/\operatorname{Tr}(\exp(\alpha^{(s)}\sum_{r=1}^{t}(\Sigma_{r}^{(s)}))))\exp(\alpha^{(s)}\sum_{r=1}^{t}(\Sigma_{r}^{(s)}))$

18
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\psi_{t}^{(s)}}\leftarrow\left\langle
M(S_{t}^{(s)}),U_{t}{{}^{(s)}}\right\rangle+{\rm
Lap}(2B^{2}d/(n\varepsilon_{2}))$

19 if  _$\psi_{t}^{(s)}\leq(1/5.5)\lambda_{t}^{(s)}$_ then

20 $S_{t+1}^{(s)}\leftarrow S_{t}^{(s)}$

21 else

22 $Z_{t}^{(s)}\leftarrow{\rm Unif}([0,1])$

23
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mu_{t}^{(s)}}\leftarrow(1/|S_{t}^{(s)}|)\big{(}\sum_{i\in
S_{t}}x_{i}\big{)}+{\cal
N}(0,(2B\sqrt{2d\log(1.25/\delta_{2})}/({n\,\varepsilon_{2}}){\mathbf{I}}_{d\times
d})^{2})$

24
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\rho_{t}^{(s)}}\leftarrow\text{\sc
DPthreshold-
ht}(\mu_{t}^{(s)},U_{t}^{(s)},\alpha,\varepsilon_{2},\delta_{2},S^{(s)}_{t})$
[Algorithm 17]

25 $S_{t+1}^{(s)}\leftarrow S_{t}^{(s)}\setminus$ $\\{i\,|\,$
$\\{\tau_{j}=(x_{j}-\mu_{t}^{(s)})^{\top}U_{t}^{(s)}(x_{j}-\mu_{t}^{(s)})\\}_{j\in
S_{t}^{(s)}}$ and $\tau_{i}\geq\rho_{t}^{(s)}\,Z_{t}^{(s)}\\}$.

26

27

28 $S^{(s+1)}\leftarrow S^{(s)}_{t}$

29

Output: $\mu^{(T_{1})}$

Algorithm 16 Differentially private filtering with matrix multiplicative
weights (DPMMWfilter-ht) for distributions with bounded covariance

Input: $\mu$, $U$, $\alpha\in(0,1)$, target privacy $(\varepsilon,\delta)$,
$S=\\{x_{i}\in{\cal B}_{B\sqrt{d}/2}({\bar{x}})\\}$

1 Set $\tau_{i}\leftarrow(x_{i}-\mu)^{\top}U(x_{i}-\mu)$ for all $i\in S$

2 Set $\tilde{\psi}\leftarrow(1/n)\sum_{i\in S}\tau_{i}+{\rm
Lap}(2B^{2}d/n\varepsilon))$

3 Compute a histogram over geometrically sized bins
$I_{1}=[1/4,1/2),I_{2}=[1/2,1),\ldots,I_{2+\log(B^{2}d)}=[2^{\log(B^{2}d)-1},2^{\log(B^{2}d)}]$
$h_{j}\leftarrow\frac{1}{n}\cdot|\\{i\in
S\,|\,\tau_{i}\in[2^{-3+j},2^{-2+j})\\}|\;,\;\;\;\;\text{ for all
}j=1,\cdots,2+\log(B^{2}d)$

4 Compute a privatized histogram $\tilde{h}_{j}\leftarrow h_{j}+{\cal
N}(0,(4\sqrt{2d\log(1.25/\delta)}/(n\varepsilon))^{2})$, for all
$j\in[2+\log(B^{2}d)]$

5 Set $\tilde{\tau}_{j}\leftarrow 2^{-3+j}$, for all $j\in[2+\log(B^{2}d)]$

6 Find the largest $\ell\in[2+\log(B^{2}d)]$ satisfying
$\sum_{j\geq\ell}(\tilde{\tau}_{j}-\tilde{\tau}_{\ell})\,\tilde{h}_{j}\geq
0.31\tilde{\psi}$

Output: $\rho=\tilde{\tau}_{\ell}$

Algorithm 17 Differentially private estimation of the threshold for bounded
covariance DPthreshold-ht

#####  K.2.1 Analysis of DPMMWfilter-ht and a proof of Theorem 13

Algorithm 16 is a similar matrix multiplicative weights based filter algorithm
for distributions with bounded covariance. Similarly, we first state following
Lemma K.3 and prove Theorem 13 given Lemma K.3

######  Lemma K.3.

Let $S$ be an $\alpha$-corrupted bounded covariance dataset under Assumption
2. For an epoch $s$ and an iteration $t$ such that $\lambda^{(s)}>C$,
$\lambda_{t}^{(s)}>2/3\lambda_{0}^{(s)}$, and $n^{(s)}>3n/4$, if
$n\gtrsim\frac{B^{2}(\log B)d^{3/2}\log(1/\delta)}{\varepsilon}$ and
$|S_{t}^{(s)}\cap S_{\rm good}|\geq(1-10\alpha)n$, then with probability
$1-O(1/\log(d)^{3})$, we have the condition in Eq. (20) holds. When this
condition holds, we have more corrupted samples are removed in expectation
than the uncorrupted samples, i.e., $\mathbb{E}|(S_{t}^{(s)}\setminus
S_{t+1}^{(s)})\cap S_{\rm good}|\leq\mathbb{E}|(S_{t}^{(s)}\setminus
S_{t+1}^{(s)})\cap S_{\rm bad}|$. Further, for an epoch $s\in[T_{1}]$ there
exists a constant $C>0$ such that if $\|M(S^{(s)})\|_{2}\geq C$, then with
probability $1-O(1/\log^{2}d)$, the $s$-th epoch terminates after $O(\log d)$
iterations and outputs $S^{(s+1)}$ such that $\|M(S^{(s+1)})\|_{2}\leq
0.98\|M(S^{(s)})\|_{2}$.

Now we define $d_{t}^{(s)}\triangleq|(S_{\mathrm{good}}\cap S^{(1)})\setminus
S_{t}^{(s)}|+|S_{t}^{(s)}\setminus(S_{\mathrm{good}}\cap S^{(1)})|$. Note that
$d_{1}^{(1)}=\alpha n$, and $d_{t}^{(s)}\geq 0$. At each epoch and iteration,
we have

$\displaystyle\mathbb{E}[d_{t+1}^{(s)}-d_{t}^{(s)}|d_{1}^{(1)},d_{2}^{(1)},\cdots,d_{t}^{(s)}]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[|S_{\mathrm{good}}\cap(S_{t}^{(s)}\setminus
S_{t+1}^{(s)})|-|S_{\mathrm{bad}}\cap(S_{t}^{(s)}\setminus
S_{t+1}^{(s)})|\right]\;\leq\;0,$

from the part 1 of Lemma K.3. Hence, $d_{t}^{(s)}$ is a non-negative super-
martingale. By optional stopping theorem, at stopping time, we have
$\mathbb{E}[d_{t}^{(s)}]\leq d_{1}^{(1)}=\alpha n$. By Markov inequality,
$d_{t}^{(s)}$ is less than $10\alpha n$ with probability $0.9$, i.e.
$|S_{t}^{(s)}\cap S_{\mathrm{good}}|\geq(1-10\alpha)n$. The desired bound in
Theorem 13 follows from Lemma K.11.

#####  K.2.2 Proof of Lemma K.3

Lemma K.3 is a combination of Lemma K.4, Lemma K.5 and Lemma K.6. We state the
technical lemmas and subsequently provide the proofs.

######  Lemma K.4.

For each epoch $s$ and iteration $t$, under the hypotheses of Lemma K.3 then
with probability $1-O(1/\log^{3}d)$, we have

$\displaystyle\frac{1}{n}\sum_{i\in S_{\rm good}\cap S_{t}^{(s)}}\tau_{i}$
$\displaystyle\leq$ $\displaystyle\psi/1000\;,$ (20)

where $\psi\triangleq\frac{1}{n}\sum_{i\in S_{t}^{(s)}}\tau_{i}$.

######  Lemma K.5.

For each epoch $s$ and iteration $t$, under the hypotheses of Lemma K.3, if
condition Eq. (20) holds, then we have $\mathbb{E}|S_{t}^{(s)}\setminus
S_{t+1}^{(s)}\cap S_{\rm good}|\leq\mathbb{E}|S_{t}^{(s)}\setminus
S_{t+1}^{(s)}\cap S_{\rm bad}|$ and with probability $1-O(1/\log^{3}d)$, and
$\left\langle M(S_{t+1}^{(s)}),U_{t}^{(s)}\right\rangle\leq 0.76\left\langle
M(S_{t}^{(s)}),U_{t}^{(s)}\right\rangle$.

######  Lemma K.6.

For epoch $s$, suppose for $t=0,1,\cdots,T_{2}$ where $T_{2}=O(\log d)$, if
Lemma K.5 holds, $n\gtrsim\frac{B^{2}(\log
B)d^{3/2}\log(1/\delta)}{\varepsilon\alpha}$, and $n^{(s)}>3n/4$, then we have
$\|M(S^{(s+1)})\|_{2}\leq 0.98\|M(S^{(s)})\|_{2}$ with probability
$1-O(1/\log^{2}d)$.

#####  K.2.3 Proof of Lemma K.4

###### Proof.

By Lemma G.9, Lemma G.10 and Lemma G.11, we can pick
$n=\widetilde{\Omega}\left(\frac{B^{2}d^{3/2}\log}{\varepsilon}\right)$ such
that with probability $1-O(1/\log^{3}d)$, following conditions simultaneously
hold:

  1. 1.

$\|\mu_{t}^{(s)}-\mu(S_{t}^{(s)})\|_{2}^{2}\leq 0.001$

  2. 2.

$|\psi_{t}^{(s)}-\left\langle M(S_{t}^{(s)}),U_{t}^{(s)}\right\rangle|\leq
0.001$

  3. 3.

$\left|\lambda_{t}^{(s)}-\|M(S_{t}^{(s)})\|_{2}\right|\leq 0.001$

  4. 4.

$\left|\lambda^{(s)}-\|M(S^{(s)})\|_{2}\right|\leq 0.001$

  5. 5.

$\left\|M(S_{t+1}^{(s)})-\Sigma_{t}^{(s)}\right\|_{2}\leq 0.001$

  6. 6.

$\|\mu^{(s)}-\mu(S^{(s)})\|_{2}^{2}\leq 0.001$ .

Then we have

$\displaystyle\frac{1}{n}\sum_{i\in S_{\rm good}\cap S_{t}^{(s)}}\tau_{i}$
$\displaystyle=$ $\displaystyle\frac{1}{n}\sum_{i\in S_{\rm good}\cap
S_{t}^{(s)}}\left\langle(x_{i}-\mu_{t}^{(s)})(x_{i}-\mu_{t}^{(s)})^{\top},U_{t}^{(s)}\right\rangle$
$\displaystyle\overset{(a)}{\leq}$ $\displaystyle\frac{2}{n}\sum_{i\in S_{\rm
good}\cap S_{t}^{(s)}}\left\langle(x_{i}-\mu(S_{\rm good}\cap
S_{t}^{(s)}))(x_{i}-\mu(S_{\rm good}\cap
S_{t}^{(s)}))^{\top},U_{t}^{(s)}\right\rangle$ $\displaystyle+\frac{2|S_{\rm
good}\cap S_{t}^{(s)}|}{n}\left\langle(\mu(S_{\rm good}\cap
S_{t}^{(s)})-\mu_{t}^{(s)})(\mu(S_{\rm good}\cap
S_{t}^{(s)})-\mu_{t}^{(s)})^{\top},U_{t}^{(s)}\right\rangle$
$\displaystyle\leq$ $\displaystyle 2\left\langle M((S_{\rm good}\cap
S_{t}^{(s)}),U_{t}^{(s)}\right\rangle+2\|\mu_{t}^{(s)}-\mu(S_{\rm good}\cap
S_{t}^{(s)})\|_{2}^{2}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle
2+2\left(\|\mu_{t}^{(s)}-\mu\|_{2}+\|\mu(S_{\rm good}\cap
S_{t}^{(s)})-\mu\|_{2}\right)^{2}$ $\displaystyle\overset{(c)}{\leq}$
$\displaystyle
2+2\left(0.01+2\sqrt{\alpha\|M(S_{t}^{(s)})\|_{2}}+3\sqrt{\alpha}\right)^{2}$
$\displaystyle\leq$ $\displaystyle 3+8\alpha\|M(S_{t}^{(s)})\|_{2}+32\alpha$
$\displaystyle\overset{(d)}{\leq}$
$\displaystyle\frac{\psi_{t}^{(s)}-0.002}{1000}$ $\displaystyle\leq$
$\displaystyle\frac{\psi}{1000}\;,$

where $(a)$ follows from the fact that for any vector $x,y,z$, we have
$(x-y)(x-y)^{\top}\preceq 2(x-z)(x-z)^{\top}+2(y-z)(y-z)^{\top}$, $(b)$
follows from $\alpha$-goodness of $S_{\rm good}$, $(c)$ follows from Lemma
K.11 and $(d)$ follows from our choice of large constant $C$ and sample
complexity $n$.

∎

#####  K.2.4 Proof of Lemma K.5

###### Proof.

Lemma K.4 implies with probability $1-O(1/\log^{3}d)$, our scores satisfies
the condition in Eq. (20). Then by Lemma K.7 our DPthreshold-ht gives us a
threshold $\rho$ such that

$\displaystyle\sum_{i\in S_{\rm good}\cap
S_{t}^{(s)}}\textbf{1}\\{\tau_{i}\leq\rho\\}\frac{\tau_{i}}{\rho}+\textbf{1}\\{\tau_{i}>\rho\\}\leq\sum_{i\in
S_{\rm bad}\cap
S_{t}^{(s)}}\textbf{1}\\{\tau_{i}\leq\rho\\}\frac{\tau_{i}}{\rho}+\textbf{1}\\{\tau_{i}>\rho\\}\;.$

According to our filter rule from Algorithm 17, we have

$\displaystyle\mathbb{E}|(S_{t}^{(s)}\setminus S_{t+1}^{(s)})\cap S_{\rm
good}|=\sum_{i\in S_{\rm good}\cap
S_{t}^{(s)}}\textbf{1}\\{\tau_{i}\leq\rho\\}\frac{\tau_{i}}{\rho}+\textbf{1}\\{\tau_{i}>\rho\\}$

and

$\displaystyle\mathbb{E}|(S_{t}^{(s)}\setminus S_{t+1}^{(s)})\cap S_{\rm
bad}|=\sum_{i\in S_{\rm bad}\cap
S_{t}^{(s)}}\textbf{1}\\{\tau_{i}\leq\rho\\}\frac{\tau_{i}}{\rho}+\textbf{1}\\{\tau_{i}>\rho\\}\;.$

This implies $\mathbb{E}|(S_{t}^{(s)}\setminus S_{t+1}^{(s)})\cap S_{\rm
good}|\leq\mathbb{E}|(S_{t}^{(s)}\setminus S_{t+1}^{(s)})\cap S_{\rm bad}|$.

At the same time, Lemma K.7 gives us a $\rho$ such that with probability
$1-O(\log^{3}d)$, we have

$\displaystyle\frac{1}{n}\sum_{i\in
S_{t+1}^{(s)}}\tau_{i}\leq\frac{1}{n}\sum_{\tau_{i}\leq\rho,i\in
S_{t}^{(s)}}\tau_{i}\leq\frac{3}{4}\cdot\frac{1}{n}\sum_{i\in
S_{t}^{(s)}}\tau_{i}\;.$

Hence, we have

$\displaystyle\left\langle M(S_{t+1}^{(s)}),U_{t}^{(s)}\right\rangle$
$\displaystyle=$ $\displaystyle\left\langle\frac{1}{n}\sum_{i\in
S_{t+1}^{(s)}}(x_{i}-\mu(S_{t+1}^{(s)}))(x_{i}-\mu(S_{t+1}^{(s)}))^{\top},U_{t}^{(s)}\right\rangle$
$\displaystyle\leq$ $\displaystyle\left\langle\frac{1}{n}\sum_{i\in
S_{t+1}^{(s)}}(x_{i}-\mu(S_{t}^{(s)}))(x_{i}-\mu(S_{t}^{(s)}))^{\top},U_{t}^{(s)}\right\rangle$
$\displaystyle\leq$ $\displaystyle\frac{1}{n}\sum_{i\in
S_{t+1}^{(s)}}\tau_{i}+\|\mu_{t}^{(s)}-\mu(S_{t}^{(s)})\|_{2}^{2}$
$\displaystyle\leq$ $\displaystyle\frac{3}{4n}\sum_{i\in
S_{t}^{(s)}}\tau_{i}+0.01$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle
0.76\left\langle M(S_{t}^{(s)}),U_{t}^{(s)}\right\rangle\;,$

where $(a)$ follows from our assumption that
$\psi_{t}^{(s)}>\frac{1}{5.5}\lambda_{t}^{(s)}>\frac{2}{16.5}C$.

∎

#####  K.2.5 Proof of Lemma K.6

###### Proof.

If Lemma K.5 holds, we have

$\displaystyle\left\langle M(S_{t}^{(s)}),U_{t}^{(s)}\right\rangle$
$\displaystyle\leq$ $\displaystyle 0.76\left\langle
M(S_{t-1}^{(s)}),U_{t}^{(s)}\right\rangle$ $\displaystyle\leq$ $\displaystyle
0.76\left\langle M(S_{1}^{(s)}),U_{t}^{(s)}\right\rangle$ $\displaystyle\leq$
$\displaystyle 0.76\|M(S_{1}^{(s)})\|_{2}$

We pick $n$ large enough such that with probability $1-O(\log^{3}d)$,

$\displaystyle\|\Sigma_{t}^{(s)}\|_{2}\approx_{0.05}\|M(S_{t}^{(s)})\|_{2}\;.$

Thus, we have

$\displaystyle\left\langle\Sigma_{t}^{(s)},U_{t}^{(s)}\right\rangle\leq
0.81\|M(S_{1}^{(s)})\|_{2}\;.$

By Lemma G.1, we have $M(S_{t}^{(s)})\preceq M(S_{1}^{(s)})$. by our choice of
$\alpha^{(s)}$, we have
$\alpha^{(s)}M(S_{t+1}^{(s)})\preceq\frac{1}{100}{\mathbf{I}}$ and
$\alpha^{(s)}\Sigma_{t}^{(s)}\preceq\frac{1}{100}{\mathbf{I}}$. Therefore, by
Lemma G.14 we have

$\displaystyle\left\|\sum_{i=1}^{T_{2}}\Sigma_{t}^{(s)}\right\|_{2}$
$\displaystyle\leq$
$\displaystyle\sum_{t=1}^{T_{2}}\left\langle\Sigma_{t}^{(s)},U_{t}^{(s)}\right\rangle+\alpha^{(s)}\sum_{t=0}^{T_{2}}\left\langle
U_{t}^{(s)},\left|\Sigma_{t}^{(s)}\right|\right\rangle\|\Sigma_{t}^{(s)}\|_{2}+\frac{\log(d)}{\alpha^{(s)}}$
$\displaystyle\overset{(a)}{\leq}$
$\displaystyle\sum_{t=1}^{T_{2}}\left\langle\Sigma_{t}^{(s)},U_{t}^{(s)}\right\rangle+\frac{1}{100}\sum_{t=1}^{T_{2}}\left\langle
U_{t}^{(s)},\left|\Sigma_{t}^{(s)}\right|\right\rangle+200\log(d)\|M(S_{1}^{(s)})\|_{2}$

where $(a)$ follows from our choice of $\alpha^{(s)}$, $C$, and $n$.

Meanwhile, we have

$\displaystyle|\Sigma_{t}^{(s)}|\preceq M(S_{t}^{(s)})+0.15\;{\mathbf{I}}\;.$

Thus we have

$\displaystyle\left\langle
U_{t}^{(s)},\left|\Sigma_{t}^{(s)}\right|\right\rangle\;\leq
0.91\;\left\|M(S_{1}^{(s)})\right\|_{2}$

Then we have

$\displaystyle\left\|M(S_{T_{2}}^{(s)})\right\|_{2}\leq\frac{1}{T_{2}}\left\|\sum_{i=1}^{T_{2}}M({S_{t}^{(s)}})\right\|_{2}$
$\displaystyle\;\;\;\;\;\leq\frac{1}{T_{2}}\left\|\sum_{i=1}^{T_{2}}\Sigma_{t}^{(s)}\right\|_{2}+0.05\;\|M(S_{1}^{(s)})\|_{2}$
$\displaystyle\;\;\;\;\;\leq\frac{1}{T_{2}}\left(\sum_{t=1}^{T_{2}}\left\langle\Sigma_{t}^{(s)},U_{t}^{(s)}\right\rangle+\frac{1}{100}\sum_{t=1}^{T_{2}}\left\langle
U_{t}^{(s)},\left|\Sigma_{t}^{(s)}\right|\right\rangle+200\log(d)\|M(S_{1}^{(s)})\|_{2}\right)+0.05\;\|M(S_{1}^{(s)})\|_{2}$
$\displaystyle\;\;\;\;\;\leq
0.91\|M(S_{1}^{(s)})\|_{2}+\frac{200\log(d)}{T_{2}}\|M(S_{1}^{(s)})\|_{2}+0.05\;\|M(S_{1}^{(s)})\|_{2}$
$\displaystyle\;\;\;\;\;\leq 0.98\;\|M(S_{1}^{(s)})\|_{2}$

∎

#####  K.2.6 Proof of DPthreshold-ht for distributions with bounded covariance

######  Lemma K.7 (DPthreshold-ht: picking threshold privately for
distributions with bounded covariance).

Algorithm DPthreshold-ht($\mu,U,\alpha,\varepsilon,\delta,S$) running on a
dataset $\\{\tau_{i}=(x_{i}-\mu)^{\top}U(x_{i}-\mu)\\}_{i\in S}$ is
$(\varepsilon,\delta)$-DP. Define $\psi\triangleq\frac{1}{n}\sum_{i\in
S}\tau_{i}$. If $\tau_{i}$’s satisfy

$\displaystyle\frac{1}{n}\sum_{i\in S_{\rm good}\cap S}\tau_{i}$
$\displaystyle\leq$ $\displaystyle\psi/1000\;,$

and $n\geq\tilde{\Omega}\left(\frac{B^{2}d}{\varepsilon}\right)$ then
DPthreshold-ht outputs a threshold $\rho$ such that

$\displaystyle 2(\sum_{i\in S_{\rm good}\cap
S}\textbf{1}\\{\tau_{i}\leq\rho\\}\frac{\tau_{i}}{\rho}+\textbf{1}\\{\tau_{i}>\rho\\})\leq\sum_{i\in
S_{\rm bad}\cap
S}\textbf{1}\\{\tau_{i}\leq\rho\\}\frac{\tau_{i}}{\rho}+\textbf{1}\\{\tau_{i}>\rho\\}\;,$
(21)

and with probability $1-O(1/\log^{3}d)$,

$\displaystyle\frac{1}{n}\sum_{\tau_{i}<\rho}\tau_{i}\;\;\leq\;\;0.75\psi\;.$

###### Proof.

1\. $\rho$ cuts enough

Let $\rho$ be the threshold picked by the algorithm. Let $\hat{\tau}_{i}$
denote the minimum value of the interval of the bin that $\tau_{i}$ belongs
to. It holds that

$\displaystyle\frac{1}{n}\sum_{\tau_{i}\geq\rho,i\in[n]}({\tau}_{i}-\rho)\geq\frac{1}{n}\sum_{\tilde{\tau}_{i}\geq\rho,i\in[n]}({\hat{\tau}}_{i}-\rho)$
$\displaystyle\;\;\;\;\;=\sum_{\tilde{\tau}_{j}\geq\rho,j\in[2+\log(B^{2}d)]}(\tilde{\tau}_{j}-\rho){h}_{j}$
$\displaystyle\;\;\;\;\;\overset{(a)}{\geq}\sum_{\tilde{\tau}_{j}\geq\rho,j\in[2+\log(B^{2}d)]}(\tilde{\tau}_{j}-\rho)\tilde{h}_{j}-O\left(\log(B^{2}d)\cdot
B^{2}d\cdot\frac{\sqrt{\log(\log(B^{2}d)\log d)\log(1/\delta)}}{\varepsilon
n}\right)$
$\displaystyle\;\;\;\;\;\overset{(b)}{\geq}0.31\tilde{\psi}-\tilde{O}(\frac{B^{2}d}{\varepsilon
n})$
$\displaystyle\;\;\;\;\;\overset{(c)}{\geq}0.3\psi-\tilde{O}(\frac{B^{2}d}{\varepsilon
n})\;,$

where $(a)$ holds due to the accuracy of the private histogram (Lemma G.12),
$(b)$ holds by the definition of $\rho$ in our algorithm, and $(c)$ holds due
to the accuracy of $\tilde{\psi}$. This implies

$\displaystyle\frac{1}{n}\sum_{\tau_{i}<\rho}{\tau}_{i}\leq\psi-\frac{1}{n}\sum_{\tau_{i}\geq\rho}({\tau}_{i}-\rho)\leq
0.7\psi+\tilde{O}({B^{2}d/\varepsilon n}).$

2\. $\rho$ doesn’t cut too much

Define $C_{2}$ to be the threshold such that
$\frac{1}{n}\sum_{\tau_{i}>C_{2}}(\tau_{i}-C_{2})=(2/3)\psi$. Suppose
$2^{b}\leq C_{2}\leq 2^{b+1}$, we have $\sum_{\hat{\tau}_{i}\geq
2^{b-1}}(\hat{\tau}_{i}-2^{b-1})\geq(1/3)\psi$ because $\forall\tau_{i}\geq
C_{2}$, $(\hat{\tau}_{i}-2^{b-1})\geq\frac{1}{2}(\tau_{i}-C_{2})$. Then the
threshold picked by the algorithm $\rho\geq 2^{b-1}$, which implies
$\rho\geq\frac{1}{4}C_{2}$. Suppose $\rho<C_{2}$, since
$\rho\geq\frac{1}{4}C_{2}$

$\displaystyle\sum_{i\in S_{\rm bad}\cap S,\tau_{i}<\rho}\tau_{i}+\sum_{i\in
S_{\rm bad}\cap S,\tau_{i}\geq\rho}\rho$ $\displaystyle\geq$
$\displaystyle\frac{1}{4}(\sum_{i\in S_{\rm bad}\cap
S,\tau_{i}<C_{2}}\tau_{i}+\sum_{i\in S_{\rm bad}\cap S,\tau_{i}\geq
C_{2}}C_{2})$ $\displaystyle\overset{(a)}{\geq}$
$\displaystyle\frac{10}{4}(\sum_{i\in S_{\rm good}\cap
S,\tau_{i}<C_{2}}\tau_{i}+\sum_{i\in S_{\rm good}\cap S,\tau_{i}\geq
C_{2}}C_{2})$ $\displaystyle\overset{(b)}{\geq}$
$\displaystyle\frac{10}{4}(\sum_{i\in S_{\rm good}\cap
S,\tau_{i}<\rho}\tau_{i}+\sum_{i\in S_{\rm good}\cap
S,\tau_{i}\geq\rho}\rho),$

where (a) holds by Lemma K.8, and (b) holds since $\rho\leq C_{2}$. If
$\rho\geq C_{2}$, the statement of the Lemma K.8 directly implies Equation
(21).

######  Lemma K.8.

Assuming that the condition in Eq.(20) holds, then for any $C$ such that

$\displaystyle\frac{1}{n}\sum_{i\in
S,\tau_{i}<C}\tau_{i}+\frac{1}{n}\sum_{i\in S,\tau_{i}\geq
C}C\geq(1/3)\psi\;,$

we have

$\displaystyle\sum_{i\in S_{\rm bad}\cap S,\tau_{i}<C}\tau_{i}+\sum_{i\in
S_{\rm bad}\cap S,\tau_{i}\geq C}C\geq{10}(\sum_{i\in S_{\rm good}\cap
S,\tau_{i}<C}\tau_{i}+\sum_{i\in S_{\rm good}\cap S,\tau_{i}\geq C}C)$

###### Proof.

First we show an upper bound on $S_{\rm good}$:

$\displaystyle\frac{1}{n}\sum_{i\in S_{\rm good}\cap
S,\tau_{i}<C}\tau_{i}+\frac{1}{n}\sum_{i\in S_{\rm good}\cap S,\tau_{i}\geq
C}C\leq\frac{1}{n}\sum_{i\in S_{\rm good}\cap S}\tau_{i}\leq\psi/1000.$

Then we show an lower bound on $S_{\rm bad}$:

$\displaystyle\frac{1}{n}\sum_{i\in S_{\rm bad}\cap
S,\tau_{i}<C}\tau_{i}+\frac{1}{n}\sum_{i\in S_{\rm bad}\cap S,\tau_{i}>C}C$
$\displaystyle=$ $\displaystyle\frac{1}{n}\sum_{i\in
S,\tau_{i}<C}\tau_{i}+\frac{1}{n}\sum_{i\in S,\tau_{i}\geq C}C$
$\displaystyle-(\frac{1}{n}\sum_{i\in S_{\rm good}\cap
S,\tau_{i}<C}\tau_{i}+\frac{1}{n}\sum_{i\in S_{\rm good}\cap S,\tau_{i}\geq
C}C)$ $\displaystyle\geq$ $\displaystyle(1/3-1/1000)\psi\;.$

Combing the lower bound and the upper bound yields the desired statement ∎

∎

#####  K.2.7 Regularity lemmas for distributions with bounded covariance

######  Definition K.9 ([36, Definition 3.1] ).

Let $D$ be a distribution with mean $\mu\in{\mathbb{R}}^{d}$ and covariance
$\Sigma\preceq{\mathbf{I}}$. For $0<\alpha<1/2$, we say a set of points
$S=\\{X_{1},X_{2},\cdots,X_{n}\\}$ is $\alpha$-good with respect to
$\mu\in{\mathbb{R}}^{d}$ if following inequalities are satisfied:

  * •

$\|\mu(S)-\mu\|_{2}\leq\sqrt{\alpha}$

  * •

$\left\|\frac{1}{|S|}\sum_{i\in
S}\left(X_{i}-\mu(S)\right)\left(X_{i}-\mu(S)\right)^{\top}\right\|_{2}\leq
1$.

######  Lemma K.10 ([36, Lemma 3.1] ).

Let $D$ be a distribution with mean $\mu\in{\mathbb{R}}^{d}$ and covariance
$\Sigma\preceq{\mathbf{I}}$. Let $S=\\{X_{1},X_{2},\cdots,X_{n}\\}$ be a set
of i.i.d. samples of $D$. If $n=\Omega(d\log(d)/\alpha)$, then with
probability $1-O(1)$, there exists a set $S_{\rm good}\subseteq S$ such that
$S_{\rm good}$ is $\alpha$-good with respect to $\mu$ and $|S_{\rm
good}|\geq(1-\alpha)n$.

######  Lemma K.11 ([36, Lemma 3.2] ).

Let $S$ be an $\alpha$-corrupted bounded covariance dataset under Assumption
2. If $S_{\rm good}$ is $\alpha$-good with respect to $\mu$, then for any
$T\subset S$ such that $|T\cap S_{\rm good}|\geq(1-\alpha)|S|$, we have

$\displaystyle\|\mu(T)-\mu\|_{2}\leq\frac{1}{1-2\alpha}\cdot\left(2\sqrt{\alpha\left\|M(T)\right\|_{2}}+3\sqrt{\alpha}\right)\;.$

###  Appendix L Experiments

We evaluate PRIME and compare with a DP mean estimator of [52] on synthetic
dataset in Figure 1 and Figure 2, which consists of samples from
$(1-\alpha){\cal N}(0,\mathbf{I})+\alpha{\cal N}(\mu_{\rm bad},\mathbf{I})$.
The main focus of this evaluation is to compare the estimation error and
demonstrate the robustness of PRIME under differential privacy guarantees. Our
choice of experimental settings and hyper parameters are as follows: $1\leq
d\leq 100$, $\mu_{\rm bad}=(1.5,1.5,\cdots,1.5)_{d}$,
$0.001\leq\varepsilon\leq 100$, $0.01\leq\alpha\leq 0.1$ , $C=1$.

Figure 2 shows additional experiments including the regime where we do not
have enough number of samples. When $n\leq cd^{1.5}/\alpha\varepsilon$, the
utility guarantee (Theorem 5) does not hold. The noise we add on the final
output becomes large as $n$ decreases and dominates the estimation error. The
DP Mean [52] has lower error compared to PRIME when $n$ is small because PRIME
spends some privacy budget to perform operations other than those in DP Mean
in the Algorithm 10. In practice, we can check whether there are enough number
of samples based on known parameters $(\varepsilon,\delta,n,\alpha)$, and
choose to use DP Mean (or adjust how the privacy budget is distributed in
PRIME).

Figure 2: Estimation error achieved by PRIME significantly improves upon that
of DP Mean in the large sample regime where our theoretical guarantees apply.
In the small sample regime, the noise from the DP mechanisms dominate the
error, which increases with decreasing $n$. We choose
$(\alpha,\varepsilon,\delta,d)=(0.1,100,0.01,50)$. Each data point is repeated
50 runs and standard error is shown in the error bar.

Our implementation is based on Python with basic Numpy library. We run on a
2018 Macbook Pro machine. For each choice of $d$ in our settings, it takes
less than $2$ minutes and PRIME stops after at most $3$ epochs. We have
attached our code as supplementary materials.