# Privately Estimating a Gaussian: Efficient, Robust and Optimal 111Authors
are listed in alphabetical order.

Daniel Alabi222Email<EMAIL_ADDRESS>Supported by a Junior Fellowship
from the Simons Foundation Society of Fellows and Cooperative Agreement
CB20ADR0160001 with the U.S. Census Bureau. Columbia University  Pravesh K.
Kothari333Email<EMAIL_ADDRESS>Supported by NSF CAREER Award #2047933,
NSF #2211971, an Alfred P. Sloan Fellowship, and a Google Research Scholar
Award. Carnegie Mellon University  Pranay Tankala444Email:
<EMAIL_ADDRESS>Supported by Simons Foundation Grant 733782.
Harvard University  Prayaag Venkat555Email<EMAIL_ADDRESS>Supported
by NSF grant CCF-1565264 and an NSF Graduate Fellowship under grant
DGE1745303. Harvard University  Fred Zhang666Email<EMAIL_ADDRESS>Supported
by NSF award CCF-1951384. University of California, Berkeley

###### Abstract

In this work, we give efficient algorithms for privately estimating a Gaussian
distribution in both pure and approximate differential privacy (DP) models
with optimal dependence on the dimension in the sample complexity.

  * •

In the pure DP setting, we give an efficient algorithm that estimates an
unknown $d$-dimensional Gaussian distribution up to an arbitrary tiny total
variation error using $\widetilde{O}(d^{2}\log\kappa)$ samples while
tolerating a constant fraction of adversarial outliers. Here, $\kappa$ is the
condition number of the target covariance matrix. The sample bound matches
best non-private estimators in the dependence on the dimension (up to a
polylogarithmic factor). We prove a new lower bound on differentially private
covariance estimation to show that the dependence on the condition number
$\kappa$ in the above sample bound is also tight. Prior to our work, only
identifiability results (yielding inefficient super-polynomial time
algorithms) were known for the problem.

  * •

In the approximate DP setting, we give an efficient algorithm to estimate an
unknown Gaussian distribution up to an arbitrarily tiny total variation error
using $\widetilde{O}(d^{2})$ samples while tolerating a constant fraction of
adversarial outliers. Prior to our work, all efficient approximate DP
algorithms incurred a super-quadratic sample cost or were not outlier-robust.
For the special case of mean estimation, our algorithm achieves the optimal
sample complexity of $\widetilde{O}(d)$, improving on a
$\widetilde{O}(d^{1.5})$ bound from prior work.

Our pure DP algorithm relies on a recursive private preconditioning subroutine
that utilizes the recent work [HKM22] on private mean estimation. Our
approximate DP algorithms are based on a substantial upgrade of the method of
stabilizing convex relaxations introduced in [KMV22]. In particular, we
improve on their mechanism by using a new unnormalized entropy regularization
and a new and surprisingly simple mechanism for privately releasing
covariances.

##  1 Introduction

Learning a high-dimensional Gaussian distribution is arguably the most basic
task in statistical estimation. A long line of work has focused on finding
algorithms for this fundamental problem that satisfy additional constraints
such as robustness to adversarial outliers [LRV16, DKK+18, DKK+19, DK19,
KMZ22] and differential privacy [KV18, KLSU19, KSU20, BGS+21, LKKO21, BKSW21,
AAAK21, TCK+22, KMV22, LKO22, AL22, KMS+22b]. An overarching goal in this line
of work is to investigate the _cost of privacy_ —the overhead in sample
complexity and running time that one must incur over and above the setting
without the privacy constraints. Minimizing the cost of differential
privacy—and ideally, achieving the same asymptotic dependence on the
underlying dimension in sample complexity—is a challenging goal.

To appreciate this goal, note that differentially private algorithms must
necessarily have low sensitivity. That is, switching a single sample point in
the input should lead to a small change to the estimate output by the
algorithm. Importantly, this is a _worst-case_ guarantee: it must hold
regardless of whether the input data satisfies the modeling assumption of
being independent Gaussian samples. Natural and simple estimators such as the
empirical mean and covariance of the input data have an unbounded sensitivity
and result in no privacy guarantees.

Without privacy constraints, standard concentration inequalities imply that
the mean of an unknown Gaussian distribution can be estimated up to an
$\ell_{2}$ error (more stringently, the “Mahalanobis” error) of $\sim d/n$
with $n\gg d$ samples. For covariance estimation, a similar analysis yields an
error rate of $\sim d^{2}/n$ for $n\gg d^{2}$.777Note that for obtaining
vanishing total variation error guarantees, we need to estimate the covariance
of the unknown Gaussian in the relative Frobenius distance. The last few years
have seen remarkable progress in finding private estimators that come close to
the above benchmarks. A recent work [HKM22] provides an optimal estimator in
$\ell_{2}$ norm for the mean of a distribution with covariance bounded in
spectral norm while satisfying _pure_ differential privacy—the strongest
guarantee investigated in this setting. On the other hand, in the less
stringent model of approximate differential privacy, an essentially optimal
algorithm for estimating a Gaussian distribution was recently found in [AL22].

##### This Work

The main contribution of this work is providing new sample-optimal algorithms
for estimating a Gaussian distribution in both pure and approximate
differential privacy models. For pure differential privacy, the main challenge
is the task of covariance estimation for which no efficient algorithm was
known. We resolve this challenge with dimension-dependence that asymptotically
matches the optimal non-private bounds above. Our algorithms incur a
logarithmic dependence on $\kappa$, the condition number of the unknown
covariance. We improve prior lower bounds for the problem to show that such a
dependence is in fact necessary for any pure differentially private algorithm
thus concluding that our guarantees are asymptotically optimal.

For approximate differential privacy, our main result builds and improves upon
the framework of [KMV22]. In [KMV22], the authors gave an efficient algorithm
for Gaussian estimation that incurred dimension dependence of $\sim d^{8}$ in
the sample complexity. As an immediate consequence of our upgraded guarantees,
we obtain algorithms that use $\sim d^{2}$ samples to privately estimate a
Gaussian distribution while being resilient to a constant fraction of
adversarial outliers. This improves on the previous best algorithm of [AL22]
that incurred a $\sim d^{3.5}$ sample cost.

For our algorithms in the pure differential privacy model, our main technique
is a preconditioning scheme for covariance estimation that iteratively
constructs a rough estimate of the large eigenvalues of the unknown
covariance. Previously, such a subroutine was proposed in [KLSU19] with the
weaker guarantees of approximate differential privacy. Our subroutine relies
on the new sum-of-squares exponential mechanism introduced in the recent work
of [HKM22].

For our algorithms in the approximate differential privacy model, our main
contribution is a substantial upgrade of the method of _stabilizing_ convex
relaxations introduced in [KMV22]. Their work makes a basic connection between
outlier-robust and different private algorithms and introduces a general
scheme that transforms convex programming-based outlier-robust algorithms for
statistical estimation into (approximately) differentially private ones. Two
main pieces in their scheme are a strongly convex regularizer on top of the
starting convex relaxation and a noise addition mechanism for releasing the
covariance that adds “estimate dependent” noise — i.e., the distribution of
the noise depends on the computed covariance itself. They showed that despite
this apparently leaky noise addition mechanism, their scheme leads to
differentially private algorithms albeit with large polynomial factor losses
in the sample complexity. The appealing aspect of their scheme is the
generality and modularity in transforming robust estimators to private ones.
However, a large polynomial factor loss, if inherent to this translation,
could be prohibitive. Our main contribution is an upgrade on their scheme that
leads to sample-optimal private algorithms. Our key innovation is an
introduction and analysis of a new strongly convex regularizer based on
_unnormalized entropy_ and a new and substantially simpler and optimal noise
addition mechanism for releasing covariances. We believe that our improved
version of the stabilization method will find further uses in the design of
differentially private algorithms.

###  1.1 Our Results

We now describe our results in more detail. We start by formally defining
differential privacy.

######  Definition 1.1 (Differential Privacy [DMNS06, DKM+06]).

For $\varepsilon\geq 0$ and $\delta\in[0,1]$, a (randomized) algorithm
$\mathcal{M}$ is $(\varepsilon,\delta)$-differentially private if for all
pairs of neighboring databases $x,x^{\prime}$ that differ in exactly one row,
and for all output subsets $S$ of the range of $\mathcal{M}$, the following
holds:

$\mathbb{P}[\mathcal{M}(x)\in S]\leq
e^{\varepsilon}\cdot\mathbb{P}[\mathcal{M}(x^{\prime})\in S]+\delta,$

where the probability is over the coin flips of the algorithm $\mathcal{M}$.
We say that an algorithm satisfies $\varepsilon$-pure DP if it satisfies
$(\varepsilon,\delta)$-DP with $\delta=0$.

Our main contribution is finding sample-optimal private and outlier-robust
algorithms for estimating a high-dimensional Gaussian distribution. In Table
1, we summarize the sample complexity, privacy, and robustness guarantees of
our algorithms in relation to prior work.

Reference | Sample Complexity | Privacy | Robustness
---|---|---|---
Naïve estimator | $\frac{d^{2}}{\alpha^{2}}+\frac{\kappa d^{2}}{\alpha\varepsilon}$ | $(\varepsilon,\delta)$ | Not robust
[KLSU19] | $\frac{d^{2}}{\alpha^{2}}+\frac{d^{2}}{\alpha\varepsilon}+\frac{d^{3/2}\log^{1/2}\kappa}{\varepsilon}$ | $(\varepsilon,\delta)$ | Not robust
[KMS+22b] | $\frac{d^{2}}{\alpha^{2}}+\frac{d^{2}}{\alpha\varepsilon}+\frac{d^{5/2}}{\varepsilon}$ | $(\varepsilon,\delta)$ | Not robust
[AL22] and [TCK+22] | $\frac{d^{2}}{\alpha^{2}}+\frac{d^{2}}{\alpha\varepsilon}$ | $(\varepsilon,\delta)$ | Not robust
[AL22] | $\frac{d^{3.5}}{\alpha^{3}\varepsilon}$ | $(\varepsilon,\delta)$ | $\eta$
[KMV22] | $\frac{d^{8}}{\alpha^{4}\varepsilon^{8}}$ | $(\varepsilon,\delta)$ | $\eta$
Our result (Theorem 1.1) | $\frac{d^{2}\log\kappa}{\varepsilon}+\frac{d^{2}}{\alpha^{2}\varepsilon}$ | $(\varepsilon,0)$ | $\sqrt{\eta}$
Our result (Theorem 1.3) | $\frac{d^{2}}{\alpha^{2}\varepsilon^{4.5}}$ | $(\varepsilon,\delta)$ | $\eta$
Table 1: Computationally-efficient sample complexity upper bounds for DP
covariance estimators of $\mathcal{N}(0,\Sigma)$, with the utility guarantee
$\left\|\widehat{\Sigma}-\Sigma\right\|_{\Sigma}\leq\alpha$. Robustness refers
to additional error when the sample is $\eta$-corrupted. Here, $d$ is the
dimension, $\kappa$ is an a priori bound such that
$\mathbb{I}\preceq\Sigma\preceq\kappa\mathbb{I}$. The bounds suppress
polylogarithmic factors in $d,\frac{1}{\eta},\frac{1}{\alpha},$ and
$\frac{1}{\delta}$.

Specifically, in the setting of pure DP, we prove:

######  Theorem 1.1 (Pure DP Gaussian estimation; see Theorem 4.4 and Theorem
4.7).

Fix $\alpha,\varepsilon,\eta>0$. Let
$\mathbb{I}\preceq\Sigma_{*}\preceq\kappa\mathbb{I}$ and
$\left\lVert\mu_{*}\right\rVert_{2}\leq R$. There is an efficient
$\varepsilon$-pure DP algorithm that takes input an $\eta$-corrupted sample of
size $n$ from $\mathcal{N}(\mu_{*},\Sigma_{*})$ and with probability at least
$0.99$ over the draw of the sample and the randomness of the algorithm,
outputs estimates $\widehat{\mu}$, $\widehat{\Sigma}$ such that
$TV(\mathcal{N}(\mu_{*},\Sigma_{*}),\mathcal{N}(\widehat{\mu},\hat{\Sigma}))\leq\alpha+O(\sqrt{\eta})$
so long as
$n\geq\widetilde{O}\left(d^{2}\log(\kappa)/\varepsilon+d^{2}/\alpha^{2}\varepsilon+d\log
R/\varepsilon\right)$.

As discussed earlier, the case when $\Sigma=I$ (i.e., mean estimation) was
resolved in the recent work of [HKM22] with essentially optimal
$\widetilde{O}(d)$ sample complexity. For high dimensional covariance
estimation all prior efficient algorithms only satisfied an approximate DP
guarantee. We note that an identifiability argument was presented in [AAAK21,
BKSW21]. The conceptual barrier here is that the exponential mechanism, a
canonical mechanism for ensuring pure DP, does not admit a straightforward
efficient implementation for private estimation.

Our work provides the first computationally-efficient algorithm for covariance
estimation and achieves near optimal sample complexity. We note that the
dependence on $\eta$ (the fraction of outliers) in the total variation
guarantee can likely be improved to optimal [DKK+18] $\widetilde{O}(\eta)$
though our current techniques do not yield such a guarantee. Our key idea is
exploiting the pure DP mean estimation algorithm of [HKM22] to build a
preconditioning scheme for covariances (see Section 2.1). Such a scheme was
previously used in [KLSU19] for covariance estimation with approximate DP.

##### Approximate DP Algorithm

We first consider approximate DP robust mean estimation of
$\mathcal{N}(\mu_{*},I)$.

######  Theorem 1.2 (Approximate DP Robust Mean Estimation).

Let $d\in\mathbb{N}$ and $\varepsilon,\delta\in(0,1),\eta>0$. There is an
algorithm that takes input an $\eta$-corrupted sample of size $n$ from a
Gaussian distribution $\mathcal{N}(\mu_{*},I)$ and with probability at least
$0.99$ over the draw of the sample and the randomness of the algorithm,
outputs estimates $(\widehat{\mu},I)$ such that
$\left\lVert\widehat{\mu}-\mu_{*}\right\rVert_{2}\leq
O(\eta\sqrt{\log(1/\eta)})$ so long as
$n\geq\widetilde{O}\left(\frac{d\log^{3}(1/\delta)}{\varepsilon^{3}\eta^{2}}\right)$.

For the near optimal robustness guarantee that we get in the above result, the
prior best algorithms require $\widetilde{O}(d^{1.5})$ samples [LKKO21, AL22].
On the other hand, a suboptimal dependence of $O(\sqrt{\eta})$ on the additive
error as a function of the fraction of outliers can be obtained with linear
number of samples [HKM22]. Our contribution is showing a simple algorithm that
achieves the best of all worlds: a private, robust mean estimation algorithm
with optimal dependence on both fraction of outliers and the dimension $d$.

More generally, our method yields the following optimal guarantee for
estimating an unknown Gaussian distribution (i.e., mean and covariance
estimation).

######  Theorem 1.3 (Approximate DP Robust Covariance Estimation).

Fix $d\in\mathbb{N},\varepsilon,\delta\in(0,1),\eta>0$. There is an efficient
$(\varepsilon,\delta)$-DP algorithm that takes input an $\eta$-corrupted
sample of size $n$ from a Gaussian distribution
$\mathcal{N}(\mu_{*},\Sigma_{*})$ and with probability at least $0.99$ over
the draw of the sample and the randomness of the algorithm, outputs estimates
$(\hat{\mu},\hat{\Sigma})$ such that
$\text{TV}(\mathcal{N}(\mu_{*},\Sigma_{*}),\mathcal{N}(\hat{\mu},\hat{\Sigma}))\leq\widetilde{O}(\eta)$
so long as
$n\geq\widetilde{O}\left(\frac{d^{2}\log^{4}(1/\delta)}{\varepsilon^{4.5}\eta^{2}}\right)$.

The dependence on the sample complexity as a function of the dimension $d$ is
optimal. In addition, our algorithm gets the optimal dependence on the error
rate as a function of $\eta$.

There is a long sequence of works on private robust Gaussian estimation with
approximate DP. The best known prior work on private robust estimation is due
to [AL22], which requires $\widetilde{O}(d^{3.5})$ samples. Concurrent work of
[KMV22] gave an algorithm with a polynomial but worse $\widetilde{O}(d^{8})$
sample complexity. In addition, [AL22] gives a private yet non-robust
algorithm with $\widetilde{O}(d^{2})$ sample complexity. Similar to that, the
results of [KLSU19, KMS+22b] obtain (nearly) optimal sample cost, but fail at
being robust.

Our algorithm builds upon a general method introduced by [KMV22] for
stabilizing convex relaxations. However, their specific implementation seems
to inherently suffer from large polynomial losses in sample complexity. We
introduce an upgraded version of their framework via two important changes.
First, we introduce a new unnormalized entropy based regularization that
replaces the $\ell_{2}$ norm regularization used in [KMV22]. The analysis of
this regularization requires proving an inequality that improves on naïve
strong convexity in order to obtain a tighter guarantee; see Section 6.1.
Second, the algorithm of [KMV22] applies a sophisticated estimate-dependent
noise-injection mechanism to release the estimate from the convex programming
solution. The noise in turn hurts the accuracy of their final estimate. We
give a surprisingly simple mechanism to release covariances — our mechanism
simply releases $\sim d$ samples from an estimate of the covariance computed
by the stabilized relaxation. This mechanism turns out to be significantly
more efficient in terms of sample complexity. We give a high-level overview of
the approximate DP result in Section 2.2.

##### Pure DP Lower Bound

Reference | Sample Complexity | Privacy |
---|---|---|---
[KLSU19] | $\frac{d^{2}}{\alpha\varepsilon}$ | $(\varepsilon,0)$ |
[KMS22a] | $\frac{d^{2}}{\alpha\varepsilon}$ | $(\varepsilon,\delta)$ |
Our result (Theorem 1.4) | $\frac{d^{2}\log(\kappa)}{\varepsilon}+\frac{d^{2}}{\alpha\varepsilon}$ | $(\varepsilon,0)$ |
Table 2: Sample complexity lower bounds for DP covariance estimators of
$\mathcal{N}(0,\Sigma)$, with the utility guarantee
$\left\|\widehat{\Sigma}-\Sigma\right\|_{\Sigma}\leq\alpha$. Here, $d$ is the
dimension, $\kappa$ is an a priori bound such that
$\mathbb{I}\preceq\Sigma\preceq\kappa\mathbb{I}$. The bounds suppress
polylogarithmic factors in $d,\frac{1}{\alpha},$ and $\frac{1}{\delta}$.

We complement our algorithmic result with a nearly matching lower bound. The
analysis is a standard packing lower bound, building upon [KLSU19, BKSW21].
Previously, [KLSU19] shows that under $\varepsilon$-DP,
$\Omega\left(d^{2}/(\alpha\varepsilon)\right)$ samples are required to
estimate the covariance of a Gaussian up to an error $\alpha$ (in the
Mahalanobis distance). In contrast, our upper bound (Theorem 1.1) has a
$\log(\kappa)$ term. We show that the dependence on the condition number is
necessary:

######  Theorem 1.4 (Pure DP lower bound for covariance estimation; see
Theorem 7.1).

Let $\varepsilon,\alpha\in(0,1)$, $d\geq 2$. Any $\varepsilon$-DP algorithm
that, given $n$ i.i.d. samples $\mathcal{X}=\\{X_{1},\ldots,X_{n}\\}$ from
$\mathcal{N}(0,\Sigma)$ for an unknown $\Sigma\in{\mathbb{R}}^{d\times d}$
satisfying $I\preceq\Sigma\preceq\kappa I$, outputs
$\widehat{\Sigma}=\widehat{\Sigma}(\mathcal{X})$ such that, with probability
0.9,

$\text{TV}\left(\mathcal{N}(0,\Sigma),\mathcal{N}\left(0,\widehat{\Sigma}\right)\right)<O(\alpha),$

requires

$n=\widetilde{\Omega}\left(\frac{d^{2}\log(\kappa)}{\varepsilon}+\frac{d^{2}}{\alpha\varepsilon}\right).$

Comparing this with our upper bound (Theorem 1.1) shows that our pure DP
algorithmic result achieves nearly optimal sample complexity, only up to a
$1/\alpha$ factor in its second term.

We note that there are known _approximate DP_ algorithms [KMS+22b, KMV22,
AL22, LKO22] with sample complexity that do not depend on the condition
number. Thus, our lower bound above shows a basic separation in the sample
complexity for estimating a Gaussian distribution in pure and approximate DP
models.

##### Concurrent Work

In a concurrent work, Hopkins, Kamath, Majid and Narayanan [HKMN22] also
obtained near-optimal polynomial-time algorithms for learning a Gaussian
subject to pure and approximate DP and robustness constraints. The sample
complexities achieved in our paper for approximate DP are the same as those in
[HKMN22] up to $\operatorname{poly}(1/\varepsilon,\log(1/\delta),1/\alpha)$
factors.

###  1.2 Additional Related Work

##### Private Estimation

Prior to our work, there is large body of work on parameter estimation under
differential privacy. Assuming the data is drawn from a one-dimensional normal
distribution, Karwa and Vadhan [KV18] obtain the first (finite-sample)
guarantees for confidence interval estimation of the mean—whether or not the
variance of the population is known. Their bounds are tight up to logarithmic
factors. In the high-dimensional cases, Kamath, Li, Singhal, and Ullman
[KLSU19] give the first $(\varepsilon,\delta)$-DP algorithm for learning a
Gaussian. Their sample complexity has a logarithmic dependence on the
condition number of the unknown covariance. This result has since been
improved and refined by multiple follow-up papers, including [BDKU20, BGS+21,
AL22, KMS+22b, KMV22], with a focus on removing the dependence on
conditioning. We summarize these upper bounds in Table 1. We stress that all
of them study $(\varepsilon,\delta)$-DP. In fact, our work is the first
sample- and computationally-efficient algorithm for learning a multivariate
Gaussian under the stronger $\varepsilon$-DP.

For pure DP, the most relevant work to us is Hopkins, Kamath and Majid
[HKM22], which gives an efficient pure DP procedure for mean estimation of
bounded second moment distributions. Our pure DP algorithm builds upon their
main result. In addition, Bun et al. [BKSW21] gives a general (inefficient)
cover-based approach to pure DP estimation.

##### Robust Statistics and Connections with Privacy

Robust statistics is a classic area of study, dating back to at least 1960s
[Hub64, Tuk60]. Computationally-efficient procedures for robust statistics
have been developed more recently in the algorithms literature. We refer the
reader to [DK19] for a survey.

Robustness and privacy are spiritually similar. For robustly learning the mean
of a Gaussian distribution subject to privacy, Liu, Kong, Kakade, and Oh
provide polynomial-time algorithms with sub-optimal sample complexity
[LKKO21]. However, with optimal sample complexity, they only provide an
exponential-time algorithm. For robustly learning a general Gaussian
distribution subject to DP, Kothari, Manurangsi, and Velingker provide a
polynomial-time approximate DP algorithm with sample complexity
$\widetilde{O}(d^{8})$ [KMV22]. On the other hand, Ashtiani and Liaw obtain
polynomial-time private and robust algorithms with sample complexity
$\tilde{O}(d^{3.5})$ [AL22]. Liu, Kong, and Oh [LKO22] rely on the observation
that one-dimensional robust statistical estimators have low sensitivity on
resilient datasets. Resilience, defined by Steinhardt, Charikar, and Valiant
[SCV18], measures how stable the empirical mean is to deletion of a constant
fraction of a dataset. This definition is, intuitively, similar in spirit, but
not equivalent to DP guarantees. Using this framework and the exponential
mechanism, Liu, Kong, and Oh [LKO22] design computationally inefficient
algorithms for DP statistical estimation. More relevant to us, Kothari,
Manurangsi and Velingker [KMV22] studies transforming robust algorithms into
private ones. Our approximate DP result leverages and strenthens their
technique of stabilizing convex-programming-based estimators. Finally, a very
recent work by Georgiev and Hopkins [GH22] provides a generic meta-theorem for
obtaining robustness from DP.

##### Lower Bounds for DP

In the pure DP case, geometric packing-style arguments are often used to prove
lower bounds [MT07, BKN10, HT10]. Our pure DP lower bound arguments build upon
previous works [KLSU19, BKSW21]. For the approximate DP case, the lower bounds
are based on fingerprinting codes, introduced by Boneh and Shaw [BS98]. The
existence of such codes imply lower bounds for approximate DP [BUV14]. The
technique can be applied to prove sample complexity lower bounds for Gaussian
estimation under approximate DP [KMS22a].

###  1.3 Organization

The remainder of the paper is organized as follows. In Section 2, we give a
high-level overview of our techniques. In Section 3, we introduce notations
and technical backgrounds. In Section 4, we provide our pure DP estimation
results. We discuss an approximate DP mechanism, based on Gaussian sampling,
for releasing a covariance estimate in Section 5. Using this mechanism, we
provide our results on approximate DP and robust estimation in Section 6. In
Section 7, we prove a pure DP covariance estimation lower bound.

##  2 Techniques

In this section, we provide a high-level technical overview of our algorithmic
results.

###  2.1 Pure DP Estimation

To illustrate our main ideas, we focus on private covariance estimation where
we are given samples from $\mathcal{N}(0,\Sigma)$ and a promise that
$\mathbb{I}\preceq\Sigma\preceq\kappa\mathbb{I}$. At first blush, one could
imagine obtaining an approximate DP algorithm by taking the empirical
covariance matrix and “privatize” it by the Gaussian mechanism that adds an
independent Gaussian of an appropriate variance to every entry of the
estimated matrix. This mechanism, however, runs into immediate trouble – the
variance needs to be “calibrated” to the sensitivity of the algorithm to
switching a single point in the input. The naive empirical covariance has an
unbounded sensitivity and thus cannot be privatized at all!

It turns out (and was first observed and used in [KLSU19]) that if we first
delete input points $X$ such that $\|X\|_{2}^{2}>\kappa d$ and then use the
above simple mechanism, the sensitivity can be naturally upper bounded. This
yields a private covariance estimator but needs a sample complexity that grows
linearly in $\kappa$.

In order to improve the dependence on $\kappa$, [KLSU19] proposes a
(recursive) private conditioning scheme. Roughly speaking, the procedure and
its analysis work in two steps.

  1. (i)

First, they observe that the naïve application of the Gaussian mechanism to
clamped samples provides a rough estimate of the covariance already. In
particular, the large eigendirections have their corresponding eigenvalues
preserved multiplicatively, and their algorithm explicitly identifies them
from the rough estimate.

  2. (ii)

Second, once we approximate the large eigenvectors, their algorithm shrinks
the covariance along these directions, via partially projecting out the
eigenvectors associated with large eigenvalues. Recursively doing this
preconditions the covariance, reducing the conditioning number of $\Sigma$ to
a constant. Under this condition, the naiv̈e method of adding Gaussian noise
to the empirical estimate leads to good accuracy.

However, due to the use of the Gaussian mechanism, [KLSU19] only attains
approximate (and concentrated) DP guarantees. To obtain pure DP from this
construction, our main observation is that their first step can be precisely
replaced by the pure DP mean estimation algorithm of [HKM22] (on bounded
second moment distributions). This may sound surprising at first, but the idea
is straightforward. In particular, let $\\{X_{i}\\}_{i=1}^{n}$ be the i.i.d.
samples from $\mathcal{N}(0,\Sigma)$. If we form the samples
$\mathcal{Y}=\left\\{Y_{i}=X_{i}X_{i}^{\top}/\kappa:i\in[n]\right\\}$ for
$n\gg d^{2}/\varepsilon$, then [HKM22] guarantees that we can get
$\widehat{\Sigma}$ such that
$\left\lVert\widehat{\Sigma}-\Sigma\right\rVert_{F}\leq 0.01\kappa$. Note that
this already preserves the eigenvectors, up to additive $0.01\kappa$. This
means that the large ones (say, with eigenvalues at least $\kappa/2$) are well
preserved in a multiplicative sense. It turns out the guarantees are enough to
plug into the recursive preconditioning scheme.

The step above allows us to find a preconditioning matrix $A$ so that
$I\preceq A\Sigma A\preceq O(1)I$. With the covariance matrix being well-
conditioned, we observe that estimating it can be reduced to mean estimation.
Indeed, when $\Sigma$ has largest eigenvalue $\kappa$, a basic fact about the
moments of a Gaussian random variable $X\sim\mathcal{N}(0,\Sigma)$ is that
$XX^{\top}$ (with mean $\Sigma$) has covariance of spectral norm at most
$2\kappa^{2}$. Now after preconditioning we have $\kappa=O(1)$. Thus, we can
apply the pure DP algorithm of [HKM22] again on $XX^{\top}$. Using enough
samples, this time we get an estimate $\widehat{\Sigma}^{\prime}$ such that
$\left\lVert\widehat{\Sigma}^{\prime}-A\Sigma A\right\rVert_{F}\leq 0.01$.
Finally, by straightforward calculations,
$A^{-1}\widehat{\Sigma}^{\prime}A^{-1}$ is a good estimate of $\Sigma$ in the
right affline-invariant (i.e., relative Frobenius) norm.

The robustness guarantee of our algorithm is inherited from the use of
[HKM22]. We leave it as an open question to get optimal robustness subject to
pure DP.

###  2.2 Approximate DP Robust Estimation

Our approximate DP results are built upon the framework of [KMV22] that
reduces private estimation to robust estimation obtained via what they call
_witness producing convex relaxations_. The algorithm of [KMV22], though
robust and private, requires $\widetilde{O}(d^{8})$ samples, far cry from the
(non-private) optimal bound of $\widetilde{O}(d^{2})$ samples. For learning a
general Gaussian distribution, our algorithm achieves the same performance of
[KMV22] using only $\widetilde{O}(d^{2})$ samples. Our approach significantly
upgrades the methodology of [KMV22]. This involves two main technical
innovations: a regularization scheme via entropy maximization and a new
privacy mechanism based on Gaussian sampling. Along the way, we review several
key techniques in [KMV22] that we also employ.

##### Randomizing the Outlier Rate

A common recipe to design DP algorithm is to devise a stable algorithm whose
outputs are close when given two adjacent datasets. Then standard DP
mechanisms, such as the Gaussian mechanism, work by adding noise to the output
with the noise level calibrated to the sensitivity of the algorithm.
Therefore, the basic idea of [KMV22] is to stabilize the following
prototypical convex programming approach from the robust statistics
literature. Consider an inefficient algorithm which given an $\eta$-corrupted
dataset $Y=\\{Y_{i}\\}_{i=1}^{n}$:

  1. (i)

Finds a witness set $X$ of $n$ points such that the uniform distribution on
$X$ has subgaussian fourth moments and $|Y\cap X|\geq(1-\eta)n$. Rejects if no
such $X$ exists.

  2. (ii)

Returns the mean and covariance of $X$.

Such (exponential-time) witness checking procedure is statistically optimal.
It turns out, moreover, that this this scheme can be encoded by an
(efficiently-solvable) Sum-of-Squares (SoS) program. Moreover, the solution of
the SoS relaxation retains the optimal statistical guarantee [KSS18a, KMZ22].
However, the algorithm is unstable. Suppose $Y$ contains a unique witness set
$X$ of exactly $(1-\eta)n$ points. Then if $Y^{\prime}$ is adjacent to $Y$ but
missing a point from $X$, $Y^{\prime}$ may not contain a feasible witness set
at all and therefore will be rejected by the witness checking algorithm.
Hence, there must be adjacent $Y,Y^{\prime}$ such that the procedure accepts
one but rejects the other. To patch this, [KMV22] privately selects a outlier
rate $\eta^{\prime}$ (close to the true $\eta$) as an input parameter to
witness checking.

##### Stability from Entropy Regularization

Unfortunately, this alone does not resolve the problem. Another key barrier is
that there may be multiple differing solutions to the witness checking
constraints. Indeed, [KMV22] observes that even in one dimension, the simple
witness checking algorithm has feasible solutions of variance $1+O(\eta)$ and
of $1-O(\eta)$. To exclude such differing solutions, the crucial idea from
[KMV22] is to modify the convex relaxations for robust estimation to satisfy
strong sensitivity upper bounds. This is accomplished via a strongly convex
regularization on the weight vector on the input sample computed by the convex
program. Intuitively, strong convexity ensures that the optimal solution is
stable against slight perturbation in the input—particularly when given two
neighboring datasets. For that, [KMV22] simply chooses to minimize a $2$-norm
objective $\|w\|_{2}^{2}$, where $w$ is the (soft) indicator variable for the
witness set $X$ that the convex program optimizes for. This is a natural
choice of regularizer, since intuitively $\|\cdot\|^{2}_{2}$ encourages “flat”
vectors and thus can be seen as a surrogate for entropy. However, we observe
that the strong convexity parameter of the $2$-norm objective is rather weak.
This leads to quadratically worse bounds in the sample complexity.

To improve upon this, we propose to directly use the (unnormalized) entropy
function as an regularizing objective. To analyze the sensitivity of the
stabilized convex program, [KMV22] directly exploits the general strong
convexity of its objective with respect to $2$-norm (which, via a Cauchy-
Schwarz inequality, also yields a bound on the $1$-norm).

The unnormalized entropy already satisfies such a strong convexity property
directly with respect to the $1$-norm – this is a simple generalization of the
Pinsker’s inequality. However, a vanilla application of the generalized
Pinsker’s inequality yields a quadratically lossy bound in our case giving us
no benefit on top of the squared $\ell_{2}$ norm regularization in [KMV22].

Instead, we exploit the fact that in the regime we invoke it, Pinsker’s
inequality is far from tight. By a more direct analysis we get a essentially
lossless strong convexity for the weight vectors encountered in our analysis.
As a result, we obtain a strong $\sim\widetilde{O}(1/n)$ bound on the
sensitivity of our relaxation. This bound is almost optimal up to a
logarithmic factor and improves quadratically on the
$\approx\frac{1}{\sqrt{n}}$ bound proven in [KMV22].

##### Replacing Noise-Injection by Gaussian Sampling

Notice that throughout the discussion above, we have only touched upon the
sensitivity of the convex programming-based algorithm. To eventually privatize
its output, typically one needs to add noise, for example, via the Gaussian
mechanism. Specifically, in the context of simpler problems such as estimating
the mean of a spherical covariance distribution as studied in prior works,
simple and natural mechanisms work by adding independent Gaussian noise to
each entry of the estimated mean. For covariance, however, such entrywise
noise addition can completely destroy the eigenstructure and thus lead to
arbitrarily large total variation error. Therefore, as observed by [KMV22],
one needs mechanisms that respect the eigenvalue structure—in particular, one
must add smaller noise to the directions of lower variance. The issue is that
this causes privacy leakage, since the estimate is non-privately computed from
solving the convex relaxation. Nevertheless, [KMV22] found a way to add such
an estimate-dependent noise and still guarantee privacy. Their mechanism,
however, is complicated and sub-optimal and results in a further quadratic
loss in the sample complexity.

Instead, we replace the sophisticated noise-addition mechanism of [KMV22] by a
novel and extremely simple mechanism: release $\widetilde{O}(d^{2})$ i.i.d.
samples from Gaussian distribution $\mathcal{N}(0,\widehat{\Sigma})$, with
$\widehat{\Sigma}$ being the estimated covariance. We show that this simple
mechanism gives optimal approximate DP guarantees. By a standard concentration
inequality, taking the empirical covariance of these released samples
approximates $\widehat{\Sigma}$ well, which in turn is guaranteed to be close
to the true $\Sigma$. This results in a further quadratic improvement in the
sample complexity over [KMV22], completing our final sample complexity bound.

Our overall analysis of the convex program builds upon [KMV22] and prior work
in the literature of robust statistics [KSS18a, KMZ22]. At a conceptual level,
our work demonstrates a quantitatively strengthened connection between
robustness and privacy.

##  3 Preliminaries

##### Notation

Throughout this paper, we will use $X$ to denote an i.i.d. (uncorrupted)
sample of $n$ points in $\mathbb{R}^{d}$ and $Y$ to denote its
$(1-\alpha)$-corruption. For any finite set $S$ of points, we will use
$\mathbb{E}_{s\sim S}f(s)$ to denote the empirical average of $f(s)$ as $s$
varies uniformly over $S$. We denote the $d$-by-$d$ identity matrix by
$I_{d}$. Let $\mathbb{S}^{d}_{+}$ denote the set of $d$-by-$d$ positive
semidefinite (PSD) matrices. For a matrix $A$, we use $\|A\|,\|A\|_{2}$ to
denote the spectral norm of $A$ and $\|A\|_{F}$ denotes its Frobenius norm.
For PSD matrices $A,B$, we write $A\preceq B$ if $B-A$ is PSD. For a PSD
matrix $\Sigma$ and vector $x$, define
$\|x\|_{\Sigma}=\left\|\Sigma^{-1/2}x\right\|_{2}$. For a matrix $X$, define
$\|X\|_{\Sigma}=\left\|\Sigma^{-1/2}X\Sigma^{-1/2}\right\|_{F}$. For
$M\in\mathbb{R}^{m\times n}$ and $N\in\mathbb{R}^{m^{\prime}\times
n^{\prime}}$, we define $M\otimes N$ to be the standard $mm^{\prime}\times
nn^{\prime}$ matrix given by the Kronecker product of $M$ and $N$. Let
$\Delta_{d}=\left\\{p\in\mathbb{R}_{+}^{d},\sum_{i=1}^{d}p_{i}=1\right\\}$
denote the probability simplex in $\mathbb{R}^{d}$.

###  3.1 Computational Model and Numerical Issues

Our algorithms work in the standard word RAM model. In this model, the input
sample $Y$ is given to the algorithm after truncating the real numbers to
rational numbers with $\operatorname{poly}(d)$ bits of precision. The running
time of the algorithm is a function of the total bit complexity of the
representation of the input.

Throughout this work, we assume $\Sigma\geq 2^{-\operatorname{poly}(d)}I$.
This assumption is due to the numerical issue—namely, that truncation of $Y$
to rational numbers, in general, does not allow recovering eigenvalues of
$\Sigma$ that are not representable in polynomially many bits of precision.

###  3.2 Entropy Potential Function

######  Definition 3.1 (Unnormalized entropy).

For $x\in\mathbb{R}^{n}_{\geq 0}$, define the unnormalized entropy function
$\textsf{Ent}(x)=\sum_{i=1}^{n}x_{i}\log(1/x_{i})+x_{i}$. Following standard
convention, we take $0\log(1/0)=0$.

######  Lemma 3.1 (Lemma 3.21 of [KMV22]).

Suppose $x,y\in[0,1]^{n}$ such that $\sum_{i}x_{i},\sum_{i}y_{i}\geq n/2$ and
$\left\lVert x-y\right\rVert_{1}\leq\beta n$ for $\beta\leq 1/10$. Let
$\bar{x}=x/\left\lVert x\right\rVert_{1}$ and $\bar{y}=y/\left\lVert
y\right\rVert_{1}$ be the normalized versions of $x,y$. Then,

$\left\lVert\bar{x}-\bar{y}\right\rVert_{1}\leq 6\beta.$

###  3.3 Differential Privacy

######  Theorem 3.2 (Basic Composition [DMNS06]).

For every $\varepsilon,\delta\geq 0$ and $k\in\mathbb{N}$, the class of
$(\varepsilon,\delta)$-DP mechanisms is $\left(k\varepsilon,k\delta\right)$-DP
under $k$-fold adaptive compositions.

######  Theorem 3.3 (Variant of Parallel Composition [McS10]).

Let $\mathcal{M}:\mathcal{O}\times\mathcal{Y}\to\mathcal{O}$ be an
$\varepsilon$-DP mechanism that takes as input some parameters
$w\in\mathcal{O}$ and a dataset $Y\in\mathcal{Y}$ and outputs
$\mathcal{M}(w,Y)\in\mathcal{O}$. For any $k\in\mathbb{N}$, let
$\mathcal{M}_{k}:\mathcal{O}\times\mathcal{Y}^{k}\to\mathcal{O}^{k+1}$ be a
mechanism that takes as input parameters $w_{0}\in\mathcal{O}$ and a dataset
$Y=(Y_{1},\ldots,Y_{k})\in\mathcal{Y}^{k}$ partitioned into $k$ disjoint
components where $k$ does not depend on $Y$.

Given $w_{0}\in\mathcal{O}$, the mechanism $\mathcal{M}_{k}$ (adaptively)
computes $w_{i}=\mathcal{M}(w_{i-1},Y_{i})$ for each $i\in[k]$, and outputs
$(w_{0},w_{1},\ldots,w_{k})$. Then $\mathcal{M}_{k}$ satisfies
$\varepsilon$-DP.

###### Proof.

Fix any sequence $w=(w_{0},w_{1},\ldots,w_{k})\in\mathcal{O}^{k+1}$ and let
$Y=(Y_{1},\ldots,Y_{k})$ and
$Y^{\prime}=(Y_{1}^{\prime},\ldots,Y_{k}^{\prime})$ be neighboring datasets in
$\mathcal{Y}^{k}$. We need to show that the ratio
$\frac{\Pr[\mathcal{M}_{k}(w_{0},Y)=w]}{\Pr[\mathcal{M}_{k}(w_{0},Y^{\prime})=w]}$
lies between $e^{-\varepsilon}$ and $e^{\varepsilon}$.

Since $k$ does not depend on any dataset and $Y$ is partitioned into disjoint
subsets, there must exist at most one partition that is neighboring. To this
end and without loss of generality, let $j\in[k]$ be an index such that
$Y_{j},Y_{j}^{\prime}\in\mathcal{Y}$ are neighboring datasets and
$Y_{i}=Y_{i}^{\prime}$ for all $i\neq j$. Therefore, by independence,

$\frac{\Pr[\mathcal{M}_{k}(w_{0},Y)=w]}{\Pr[\mathcal{M}_{k}(w_{0},Y^{\prime})=w]}=\prod_{i=1}^{k}\frac{\Pr[\mathcal{M}(w_{i-1},Y_{i})=w_{i}]}{\Pr[\mathcal{M}(w_{i-1},Y_{i}^{\prime})=w_{i}]}.$

Thus, in the rightmost product above, only the $j$th of the $k$ factors may
differ from $1$. Since $\mathcal{M}$ is $\varepsilon$-DP, this $j$th factor
lies between $e^{-\varepsilon}$ and $e^{\varepsilon}$. Thus, $\mathcal{M}_{k}$
is also $\varepsilon$-DP. ∎

######  Theorem 3.4 (Advanced Composition, Theorem III.3 of [DRV10]).

For every $\varepsilon,\delta,\delta^{\prime}>0$ and $k\in\mathbb{N}$, the
class of $(\varepsilon,\delta)$-DP mechanisms is
$\left(\sqrt{2k\log(1/\delta^{\prime})}\varepsilon+k\varepsilon(e^{\varepsilon}-1),k\delta+\delta^{\prime}\right)$-DP
under $k$-fold adaptive compositions.

######  Definition 3.2 (Differential Privacy under Condition).

An algorithm $\mathcal{M}:\mathcal{Y}\to\mathcal{O}$ is said to be
_$(\varepsilon,\delta)$ -differentially private under condition $\Psi$_ (or
_$(\varepsilon,\delta)$ -DP under condition $\Psi$_) for
$\varepsilon,\delta>0$ iff, for every $S\subseteq\mathcal{O}$ and every
neighboring datasets $Y,Y^{\prime}$ both satisfying $\Psi$, we have

$\Pr[\mathcal{M}(Y)\in S]\leq
e^{\varepsilon}\cdot\Pr[\mathcal{M}(Y^{\prime})\in S]+\delta.$

######  Lemma 3.5 (Composition for Algorithm with Halting, Lemma 3.30 of
[KMV22]).

Let
$\mathcal{M}_{1}:\mathcal{Y}\to\mathcal{O}_{1}\cup\\{\perp\\},\mathcal{M}_{2}:\mathcal{O}_{1}\times\mathcal{Y}\to\mathcal{O}_{2}\cup\\{\perp\\},\dots,\mathcal{M}_{k}:\mathcal{O}_{k-1}\times\mathcal{Y}\to\mathcal{O}_{k}\cup\\{\perp\\}$
be algorithms. Furthermore, let $\mathcal{M}$ denote the algorithm that
proceeds as follows (with $o_{0}$ being empty): For $i=1,\dots,k$, compute
$o_{i}=\mathcal{M}_{i}(o_{i-1},Y)$ and, if $o_{i}=\perp$, halt and output
$\perp$. Finally, if the algorithm has not halted, then output $o_{k}$.

Suppose that:

  * •

For any $1\leq i<k$, we say that $Y$ satisfies the condition $\Psi_{i}$ if
running the algorithm on $Y$ does not result in halting after applying
$\mathcal{M}_{1},\mathcal{M}_{2},\dots,\mathcal{M}_{i}$.

  * •

$\mathcal{M}_{1}$ is $(\varepsilon_{1},\delta_{1})$-DP.

  * •

$\mathcal{M}_{i}$ is $(\varepsilon_{i},\delta_{i})$-DP (with respect to
neighboring datasets in the second argument) under condition $\Psi_{i-1}$ for
all $i=\\{2,\dots,k\\}$.

Then, $\mathcal{M}$ is
$\left(\sum_{i\in[k]}\varepsilon_{i},\sum_{i\in[k]}\delta_{i}\right)$-DP.

######  Theorem 3.6 (Gaussian mechanism, [DMNS06, NTZ13]).

Let $f:(\mathbb{R}^{d})^{\otimes n}\rightarrow\mathbb{R}^{k}$ satisfy

$\max_{\mathcal{X},\mathcal{X}^{\prime}}\left\lVert
f(\mathcal{X})-f(\mathcal{X}^{\prime})\right\rVert_{2}\leq\Delta,$

where $\mathcal{X},\mathcal{X}^{\prime}$ are neighboring datasets. Then for
any $\varepsilon\in(0,1)$, $M(\mathcal{X})=f(\mathcal{X})+\sigma Z$ is
$(\varepsilon,\delta)$-DP, where $Z\sim\mathcal{N}(0,I_{k})$ and
$\sigma=\sqrt{2\ln(1.25/\delta)}\Delta/\varepsilon$.

######  Definition 3.3 ($f$-Divergence Family [CSI67, AS66]).

For any convex, lower semi-continuous function
$f:{\mathbb{R}}^{+}\rightarrow{\mathbb{R}}$, the $f$-Divergence between two
probability measures $P,Q$ is defined as

$D_{f}(P\|Q)=\int_{\mathcal{X}}f\left(\frac{dP}{dQ}\right)dQ=\int_{\mathcal{X}}q(x)f\left(\frac{p(x)}{q(x)}\right)dx.$

The family of $f$-divergences includes the Jensen-Shannon, total variation,
and hockey-stick divergences.

######  Definition 3.4 (Hockey-Stick divergence [SV16]).

Let $p,q$ be probability density functions on $\mathbb{R}^{d}$ and $\gamma\geq
0$. The hockey-stick divergence $D_{\gamma}(p,q)$ between $p,q$ is defined as

$D_{\gamma}(p,q)=\int_{x\in\mathbb{R}^{d}}[p(x)-\gamma q(x)]_{+}dx,$

where $[c]_{+}=\max(c,0)$.

We now state a consequence of the hockey-stick divergence bound for
differential privacy:

######  Fact 3.7.

Let $\mathcal{M}$ be a randomized algorithm whose output is in
$\mathbb{R}^{d}$. Then $\mathcal{M}$ is $(\varepsilon,\delta)$-DP if and only
if for any neighboring datasets $\mathcal{X},\mathcal{X}^{\prime}$ it holds
that
$D_{e^{\varepsilon}}(\mathcal{M}(\mathcal{X}),\mathcal{M}(\mathcal{X}^{\prime}))\leq\delta$
and
$D_{e^{\varepsilon}}(\mathcal{M}(\mathcal{X}^{\prime}),\mathcal{M}(\mathcal{X}))\leq\delta$.

The following condition is also useful for proving that a mechanism satisfies
$(\varepsilon,\delta)$-DP.

######  Lemma 3.8 (Lemma 1.5 in [Vad17], Section 1.1 of [BS16]).

For a (randomized) mechanism ${\cal M}$ and datasets $x,y$, define the
function

$f_{xy}(z)=\log\left(\frac{\Pr[{\cal M}(x)=z]}{\Pr[{\cal M}(y)=z]}\right).$

If $\Pr[f_{xy}({\cal M}(x))>\varepsilon]\leq\delta$ for all adjacent datasets
$x,y$, then ${\cal M}$ is $(\varepsilon,\delta)$-DP.

One of the most generic mechanisms used to satisfy pure differential privacy
is the Exponential Mechanism:

######  Theorem 3.9 (Exponential Mechanism [MT07]).

Let $\mathcal{X}\sim\mathcal{X}^{\prime}\in\mathcal{O}^{k}$ denote two
neighboring datasets. Consider any arbitrary utility function
$u:\mathcal{O}^{k}\times\mathcal{R}\rightarrow{\mathbb{R}}$ with global
sensitivity
$\Delta_{u}=\max_{\mathcal{X}\sim\mathcal{X}^{\prime},r}|u(\mathcal{X},r)-u(\mathcal{X}^{\prime},r)|$.
For any dataset $\mathcal{X}$, the exponential mechanism outputs
$r\in\mathcal{R}$ with probability $\propto\exp(\frac{\varepsilon\cdot
u(\mathcal{X},r)}{2\Delta_{u}})$.

Furthermore, the exponential mechanism satisfies $\varepsilon$-DP.

In general, the exponential mechanism is not computationally efficient to
implement. We cite a recent result on pure DP mean estimation (on bounded
second moment distributions), due to [HKM22], that presents computationally
efficient implementations of the exponential mechanism via a Sum-of-Squares
approach. Their main procedure is outlier-robust with a corruption level of
$\eta$, at the cost of increasing the estimation error by an additive
$O(\sqrt{\eta})$.

######  Theorem 3.10 (Pure DP mean estimation, Theorem 1.2 of [HKM22]).

For every $n,d\in\mathbb{N}$ and $R,\alpha,\varepsilon,\beta>0$ there is a
polynomial-time $\varepsilon$-DP algorithm PureDPMean such that for every
distribution $D$ on $\mathbb{R}^{d}$ such that $\left\lVert\mathbb{E}_{X\sim
D}X\right\rVert_{2}\leq R$ and $\text{Cov}_{X\sim D}(X)\preceq I_{d}$, given
$X_{1},\ldots,X_{n}\sim D$, with probability at least $1-\beta$ the algorithm
outputs $\widehat{\mu}$ such that $\left\lVert\widehat{\mu}-\mathbb{E}_{X\sim
D}X\right\rVert_{2}\leq\alpha$ so long as

$n\geq\widetilde{O}\left(\frac{d+\log(1/\beta)}{\alpha^{2}\varepsilon}+\frac{d\log(R)+\min(d,\log(R))\cdot\log(1/\beta)}{\varepsilon}\right).$

Furthermore, if an $\eta$-fraction of the samples are adversarially corrupted,
the algorithm maintains the same guarantee, at the cost now that
$\|\widehat{\mu}-\mathbb{E}_{X\sim D}X\|\leq\alpha+O(\sqrt{\eta})$.

###  3.4 Basic Tools from Probability Theory

######  Definition 3.5 (Total Variation Distance).

For any two distributions $P,Q$ over ${\mathbb{R}}^{d}$, the total variation
distance TV is defined as

$\text{TV}(P,Q)=\sup_{S\subseteq{\mathbb{R}}^{d}}|P(S)-Q(S)|.$

Moreover, it can be verified that

$\text{TV}(P,Q)=\frac{1}{2}\int_{{\mathbb{R}}^{d}}|p(x)-q(x)|dx.$

The following lemma shows how to convert parameter estimation to distribution
estimation (in total variation distance), for the multidimensional Gaussian
distribution.

######  Lemma 3.11 (Parameter closeness implies distribution closeness; see
Lemma 2.9 of [KLSU19]).

Let $\alpha\geq 0$, $\mu,\widehat{\mu}\in\mathbb{R}^{d}$ and
$\Sigma,\widehat{\Sigma}\in\mathbb{R}^{d\times d}$ be PSD. Suppose that

$\left\lVert\Sigma^{-1/2}(\mu-\widehat{\mu})\right\rVert_{2}\leq\alpha\text{
and
}\left\lVert\Sigma^{-1/2}\widehat{\Sigma}\Sigma^{-1/2}-I\right\rVert_{F}\leq\alpha.$

Then
$\text{TV}\left(\mathcal{N}(\mu,\Sigma),\mathcal{N}\left(\widehat{\mu},\widehat{\Sigma}\right)\right)\leq
O(\alpha)$.

The fact below follows from Theorem 4.12 of [DKK+19].

######  Fact 3.12.

Let $X\sim\mathcal{N}(0,\Sigma)$ and $Y=XX^{T}$. Then $\text{Cov}(Y)\preceq
3\Sigma\otimes\Sigma$.

For the Gaussian distribution, the empirical estimator of its covariance
attains the following statistical accuracy. This fact is needed for analyzing
our Gaussian sampling mechanism.

######  Theorem 3.13 (Empirical covariance estimator for Gaussian [Ver18]).

Let $\Sigma\in\mathbb{R}^{d\times d}$ be PSD,
$X_{1},\ldots,X_{n}\sim\mathcal{N}(0,\Sigma)$ be i.i.d. and
$\widehat{\Sigma}=\frac{1}{n}\sum_{i=1}^{n}X_{i}X_{i}^{T}$. Then with
probability $1-\gamma$, it holds that

$\left\lVert\Sigma^{-1/2}\widehat{\Sigma}\Sigma^{-1/2}-I\right\rVert_{F}\leq\rho,$

for some
$\rho=O\left(\sqrt{\frac{d^{2}+\log(1/\gamma)}{n}}+\frac{d^{2}+\log(1/\gamma)}{n}\right)$.

##### Concentration inequalities

We cite some standard concentration inequalities.

######  Theorem 3.14 (Hanson-Wright Inequality [RV13]).

Let $g\sim\mathcal{N}(0,I_{d})$ and $A\in\mathbb{R}^{d\times d}$. Then for
some absolute constant $c>0$ and every $t\geq 0$ it holds that

$\Pr(|g^{T}Ag-\mathbb{E}g^{T}Ag|\geq t)\leq
2\exp\left(-c\min\left(\frac{t^{2}}{\left\lVert
A\right\rVert_{F}^{2}},\frac{t}{\left\lVert A\right\rVert_{2}}\right)\right).$

######  Lemma 3.15 (Chi-squared tail bound).

Let $Z\sim\mathcal{N}(0,I_{d})$. Then there is some constant $c>0$ such that
for all $t\geq 0$,

$\Pr\left(\left\lVert Z\right\rVert_{2}^{2}\geq
d+t\right)\leq\exp\left(-c\min\left\\{t^{2}/d,t\right\\}\right).$

##### Sub-exponential random variables

We now cite some properties of sub-exponential random variables.

######  Definition 3.6 (Sub-exponential random variable; Definition 2.7 in
[Wai19]).

A random variable $X$ with mean $\mu=\mathbb{E}[X]$ is _sub-exponential_ if
there are non-negative parameters $(\nu,\alpha)$ such that

$\mathbb{E}\left[e^{\lambda(X-\mu)}\right]\leq
e^{\frac{\nu^{2}\lambda^{2}}{2}}\qquad\text{for all
}|\lambda|<\frac{1}{\alpha}.$

######  Lemma 3.16 (Sub-exponential tail bound, Proposition 2.9 in [Wai19]).

Suppose that $X$ is sub-exponential with parameters $(\nu,\alpha)$. Then

$\Pr[X-\mu\geq
t]\leq\max\left\\{e^{-\frac{t^{2}}{2\nu^{2}}},e^{-\frac{t}{2\alpha}}\right\\}.$

Let $\chi_{d}^{2}$ denote a Chi-squared random variable with $d$ degrees of
freedom.

######  Lemma 3.17 ($\chi^{2}_{1}$ sub-exponential parameters, Example 2.11 in
[Wai19]).

A chi-squared random variable with $1$ degree of freedom ($\chi_{1}^{2}$) is
sub-exponential with parameters $(\nu,\alpha)=(2,4)$.

######  Lemma 3.18 (Sub-exponential parameters of independent sum, Chapter 2
of [Wai19]).

Consider an independent sequence $X_{1},\ldots,X_{k}$ of random variables,
such that $X_{i}$ is sub-exponential with parameters $(\nu_{i},\alpha_{i})$.
Then the variable $\sum_{i=1}^{k}X_{i}$ is sub-exponential with the parameters
$(\nu_{*},\alpha_{*})$, where

$\alpha_{*}=\max_{i\in[k]}\alpha_{i}\qquad\text{and}\qquad\nu_{*}=\sqrt{\sum_{i=1}^{k}\nu_{i}^{2}}.$

###  3.5 Sum-of-Squares Optimization

We refer the reader to the monograph [FKP+19] for a detailed exposition of the
sum-of-squares method and its usage in average-case algorithm design. A
_degree- $\ell$ pseudo-distribution_ is a finitely-supported function
$D:\mathbb{R}^{n}\rightarrow\mathbb{R}$ such that $\sum_{x}D(x)=1$ and
$\sum_{x}D(x)f(x)^{2}\geq 0$ for every polynomial $f$ of degree at most
$\ell/2$. We define the _pseudo-expectation_ of a function $f$ on
$\mathbb{R}^{d}$ with respect to a pseudo-distribution $D$, denoted
$\widetilde{\mathbb{E}}_{D(x)}f(x)$, as
$\widetilde{\mathbb{E}}_{D(x)}f(x)=\sum_{x}D(x)f(x)$.

The degree-$\ell$ pseudo-moment of a pseudo-distribution $D$ is the tensor
$\mathbb{E}_{D(x)}(1,x_{1},x_{2},\ldots,x_{n})^{\otimes\ell}$ with entries
corresponding to pseudo-expectations of monomials of degree at most $\ell$ in
$x$. The set of all degree-$\ell$ moment tensors of degree $d$ pseudo-
distributions is also closed and convex.

######  Definition 3.7 (Constrained pseudo-distributions).

Let $D$ be a degree-$\ell$ pseudo-distribution over $\mathbb{R}^{n}$. Let
$\mathcal{A}=\\{f_{1}\geq 0,f_{2}\geq 0,\ldots,f_{m}\geq 0\\}$ be a system of
$m$ polynomial inequality constraints. We say that _$D$ satisfies the system
of constraints $\mathcal{A}$ at degree $r$_ (satisfies it
$\eta$-approximately, respectively), if for every $S\subseteq[m]$ and every
sum-of-squares polynomial $h$ with $\deg h+\sum_{i\in S}\max\\{\deg
f_{i},r\\}\leq\ell$, $\widetilde{\mathbb{E}}_{D}h\cdot\prod_{i\in S}f_{i}\geq
0$. We say that $D$ satisfies (similarly for approximately satisfying)
$\mathcal{A}$ (without mentioning degree) if $D$ satisfies $\mathcal{A}$ at
degree $r$.

##### Sum-of-squares proofs

A _sum-of-squares proof_ that the constraints $\\{f_{1}\geq 0,\ldots,f_{m}\geq
0\\}$ imply the constraint $\\{g\geq 0\\}$ consists of polynomials
$(p_{S})_{S\subseteq[m]}$ such that $g=\sum_{S\subseteq[m]}p_{S}\cdot\Pi_{i\in
S}f_{i}$.

We say that this proof has _degree $\ell$_ if for every set $S\subseteq[m]$,
the polynomial $p_{S}\Pi_{i\in S}f_{i}$ has degree at most $\ell$ and write:

$\\{f_{i}\geq 0\mid i\leq
r\\}\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{6.91663pt}{0.47787pt}\raisebox{-6.82222pt}{\makebox[6.91663pt]{\leavevmode\hbox{\set@color$\scriptstyle{\ell}$}}}\raisebox{1.96112pt}{\makebox[6.91663pt]{\leavevmode\hbox{\set@color$\scriptstyle{}$}}}$}}}\\{g\geq
0\\}\,.$ (3.1)

######  Fact 3.19 (Soundness).

If $D$ satisfies $\mathcal{A}$ for a degree-$\ell$ pseudo-distribution $D$ and
there exists a sum-of-squares proof
$\mathcal{A}\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{8.45248pt}{0.47787pt}\raisebox{-6.08612pt}{\makebox[8.45248pt]{\leavevmode\hbox{\set@color$\scriptstyle{r^{\prime}}$}}}\raisebox{1.96112pt}{\makebox[8.45248pt]{\leavevmode\hbox{\set@color$\scriptstyle{}$}}}$}}}\mathcal{B}$,
then $D$ satisfies $\mathcal{B}$ at degree $rr^{\prime}+r^{\prime}$.

######  Definition 3.8 (Total bit complexity of Sum-of-Squares Proofs).

Let $p_{1},p_{2},\ldots,p_{m}$ be polynomials in indeterminate $x$ with
rational coefficients. For a polynomial $p$ with rational coefficients, we say
that $\\{p_{i}\geq 0\\}$ derives $\\{p\geq 0\\}$ in degree $k$ and total bit
complexity $B$ if $p=\sum_{i}q_{i}^{2}+\sum_{i}r_{i}p_{i}$ where each
$q_{i}^{2},r_{i}$ are polynomials with rational coefficients of degree at most
$k$ and $k-deg(p_{i})$ for every $i$, and the total number number of bits
required to describe all the coefficients of all the polynomials
$q_{i},r_{i},p_{i}$ is at most $B$.

There is an efficient separation oracle for moment tensors of pseudo-
distributions that allows approximate optimization of linear functions of
pseudo-moment tensors approximately satisfying constraints. The _degree-
$\ell$ sum-of-squares algorithm_ optimizes over the space of all degree-$\ell$
pseudo-distributions that approximately satisfy a given set of polynomial
constraints:

######  Fact 3.20 (Efficient Optimization over Pseudo-distributions [Sho87,
Par00, Nes00, Las01]).

Let $\eta>0$. There exist an algorithm that for $n,m\in\mathbb{N}$ runs in
time $(n+m)^{O(\ell)}\operatorname{poly}\log 1/\eta$, takes input an
explicitly bounded and satisfiable system of $m$ polynomial constraints
$\mathcal{A}$ in $n$ variables with rational coefficients and outputs a
level-$\ell$ pseudo-distribution that satisfies $\mathcal{A}$
$\eta$-approximately.

###  3.6 Analytic Properties of Probability Distributions

##### Certifiable Subgaussianity

We define certifiable subgaussianity and it will be used in analysis of our
approximate DP robust mean estimation algorithm.

######  Definition 3.9 (Certifiable Subgaussianity).

A distribution $D$ on $\mathbb{R}^{d}$ with mean $\mu_{*}$ is said to be
$2k$-certifiably $C$-subgaussian if there is a degree $2k$ sum-of-squares
proof of the following polynomial inequality in $d$-dimensional vector-valued
indeterminate $v$:

$\mathbb{E}_{x\sim D}\left\langle
x-\mu_{*},v\right\rangle^{2k}\leq(Ck)^{k}\left(\mathbb{E}_{x\sim
D}\left\langle x-\mu_{*},v\right\rangle^{2}\right)^{k}\,.$

Furthermore, we say that $D$ is certifiable $C$-subgaussian if it is
$2k$-certifiably $C$-subgaussian for every $k\in\mathbb{N}$.

A finite set $X\subseteq\mathbb{R}^{d}$ is said to be $2k$-certifiable
$C$-subgaussian if the uniform distribution on $X$ is $2k$-certifiably
$C$-subgaussian.

##### Certifiable Hypercontractivity of Degree 2 Polynomials

Next, we define _certifiable hypercontractivity_ of degree-$2$ polynomials
that formulates (within SoS) the fact that higher moments of degree-$2$
polynomials of distributions (such as Gaussians) can be bounded in terms of
appropriate powers of their 2nd moment.

######  Definition 3.10 (Certifiably hypercontractive).

A distribution $\mathcal{D}$ on $\mathbb{R}^{d}$ with mean $\mu$ and
covariance $\Sigma$ is said to have $2h$-certifiably $C$-hypercontractive
degree-$2$ polynomials if for a $d\times d$ matrix-valued indeterminate $Q$
and $\overline{x}=x-\mu$,

$\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{11.53305pt}{0.47787pt}\raisebox{-6.82222pt}{\makebox[11.53305pt]{\leavevmode\hbox{\set@color$\scriptstyle{2h}$}}}\raisebox{3.32222pt}{\makebox[11.53305pt]{\leavevmode\hbox{\set@color$\scriptstyle{Q}$}}}$}}}\left\\{\mathbb{E}_{x\sim
D}\left(\overline{x}^{\top}Q\overline{x}-\mathbb{E}_{x\sim
D}\overline{x}^{\top}Q\overline{x}\right)^{2h}\leq(Ch)^{2h}\left\lVert\Sigma^{1/2}Q\Sigma^{1/2}\right\rVert_{F}^{2h}\right\\}.$

The Gaussian distribution and its affine transforms are known to satisfy
$2t$-certfiable $C$\- hypercontractivity with an absolute constant $C$ for
every $t$ [KOTZ14].

Certifiable hypercontractivity strictly generalizes the better known
certifiable subgaussianity property (formalized and studied first in [KSS18b])
that is the special case of certifiable hypercontractivity of (squares of)
linear polynomials, or, equivalently, when $Q=vv^{\top}$ for a vector-valued
indeterminate $v$.

##  4 Pure DP Covariance Estimation

In this section, we give an efficient algorithm for Gaussian covariance
estimation under pure differential privacy.

##### High-level overview

The procedure builds upon the recent work by Hopkins, Kamath and Majid [HKM22]
on pure DP mean estimation. First, we exploit their algorithm to precondition
the unknown covariance matrix such that it is approximately identity. A key
step is a weak preconditioning algorithm that uses the result of [HKM22] to
improve the conditioning of $\Sigma$ by a constant factor. We recursively
apply the construction to strengthen the conditioning of $\Sigma$. (This
recursive scheme was first proposed by [KLSU19] for approximate DP estimation,
but here we use it to obtain pure DP guarantees.) Once $\Sigma$ is nearly
identity, we show that appealing to a pure DP mean estimation algorithm would
suffice. For that purpose, we resort to [HKM22] again and complete the proof.

Our algorithm can be seen as a reduction to black-box applications to [HKM22].
As a result, our estimator retains the same robustness property of [HKM22],
albeit it is sub-optimal for the Gaussian distribution.

###  4.1 Weak Private Preconditioning

As we discussed, the key subroutine of our algorithm is a private conditioning
procedure. Given the samples, its goal is to output a preconditioning matrix
$A$ such that $I\preceq A\Sigma A\preceq 0.99\kappa I$, where $\kappa$ is the
condition number of the known covariance $\Sigma$. In other words, the
condition number of $A\Sigma A$ improves over that of $\Sigma$, by a constant
factor. This guarantee is similar to what appears in the previous literature
on private covaraince estimation and subspace recovery [KLSU19, SS21,
KMS+22b]. However, the algorithms from prior work crucially rely upon the
Gaussian mechanism, which only ensure approximate (or concentrated) DP. These
results, therefore, do not translate into pure DP guarantees.

In this section, we describe and analyze a weak pure DP algorithm for
preconditioning the covariance. puThe procedure reduces the condition number
of the covariance (multiplicatively) by a constant factor. Towards this goal,
a simple observation is that the algorithm for pure DP mean estimation from
[HKM22], applied naïvely, can be used for covariance estimation with an
absolute Frobenius norm error guarantee.

1. Input: Samples $\mathcal{X}=\\{X_{1},\ldots,X_{n}\\}\subset\mathbb{R}^{d}$, condition number $\kappa\geq 1$, accuracy parameter $\alpha>0$, failure probability $\beta>0$, privacy parameter $\varepsilon>0$. 2. Form the set of samples $\mathcal{Y}=\left\\{Y_{i}=\frac{X_{i}\otimes X_{i}}{\sqrt{3}\kappa}:i\in[n]\right\\}$. 3. Run the algorithm PureDPMean in Theorem 3.10 (the main result of [HKM22]) on input $\mathcal{Y}$ with $R=\sqrt{d/3}$ and $\alpha/\sqrt{3},\beta,\varepsilon>0$ to obtain an estimate $\tilde{\Sigma}$. 4. Output: Covariance matrix estimate $\widehat{\Sigma}=\sqrt{3}\kappa\tilde{\Sigma}$. Figure 1: PureDPMatrixMean (based on PureDPMean in Theorem 3.10)

######  Theorem 4.1 (Pure DP covariance estimation in absolute Frobenius
norm).

Let $\alpha>0$ be an error parameter, $\varepsilon>0$ be a privacy parameter
and $d\in\mathbb{N}$. There is a polynomial-time $\varepsilon$-DP algorithm
PureDPMatrixMean that, given $\varepsilon,\alpha$ and

$n\geq\widetilde{O}\left(\frac{d^{2}+\log(1/\beta)}{\alpha^{2}\varepsilon}\right)$

i.i.d. samples $\mathcal{X}=\\{X_{1},X_{2},\ldots,X_{n}\\}$ from
$\mathcal{N}(0,\Sigma)$ for an unknown $\Sigma\in\mathbb{R}^{d\times d}$
satisfying $\Sigma\preceq\kappa I$, outputs
$\widehat{\Sigma}=\widehat{\Sigma}(\mathcal{X})$ satisfying

$\left\lVert\widehat{\Sigma}-\Sigma\right\rVert_{F}\leq\alpha\kappa$

with probability at least $1-\beta$.

###### Proof.

Observe that

$\left\lVert\mathbb{E}Y_{i}\right\rVert_{F}\leq\frac{1}{\sqrt{3}\kappa}\left\lVert\Sigma\right\rVert_{F}\leq\sqrt{\frac{d}{3}}=R$

by the definition of $Y_{i}$, and

$\text{Cov}(Y_{i})\preceq\frac{1}{\kappa^{2}}\Sigma\otimes\Sigma\preceq I$

by Fact 3.12. By the choice of $n$ and the error guarantee of PureDPMean, we
have that the matrix $\widehat{\Sigma}$ output by Algorithm 1
(PureDPMatrixMean) satisfies
$\left\lVert\widehat{\Sigma}-\Sigma\right\rVert_{F}\leq\alpha\kappa$ with
probability at least $1-\beta$. Finally, the algorithm runs in polynomial
time, since PureDPMean is in polynomial time and it takes linear time to form
and rescale the samples. ∎

1. Input: Samples $\mathcal{X}=\\{X_{1},\ldots,X_{n}\\}\subset\mathbb{R}^{d}$, condition number $\kappa\geq 1$, accuracy parameter $\alpha>0$, failure probability $\beta>0$, privacy parameter $\varepsilon>0$. 2. Run Algorithm 1 PureDPMatrixMean on input $\mathcal{X}$ and with parameters $(\alpha=0.01,\beta,\varepsilon,\kappa)$ to obtain an estimate $\widehat{\Sigma}$ of the covariance matrix. 3. Let $V$ be the span of all eigenvectors of $\widehat{\Sigma}$ attaining eigenvalue at least $\kappa/2$, $\Pi$ be the projector onto $V$ and $\Pi_{\perp}$ be the projector onto the orthogonal complement of $V$. 4. Output: Weak preconditioner $A=1.19\cdot\left(0.9\Pi+\Pi_{\perp}\right)$. Figure 2: One round, weak private preconditioning algorithm

We leverage the above observation to design a weak preconditioning algorithm
(Algorithm 2) that reduces the condition number of $\Sigma$ by a constant
factor. Algorithm 2 first runs Algorithm 1 with an error parameter
$\alpha=0.01$. Then from the error guarantee of Theorem 4.1, we can privately
estimate all eigenvalues of $\Sigma$ up to an additive factor of $0.01\kappa$.
Finally, we run a partial projection step, a technique from [KLSU19].
Informally speaking, the algorithm partially projects out the eigenvectors
associated with large eigenvalues. Intuitively, this shrinks the directions of
large variance more so than those of small variance, and thus reduces
conditioning number.

The algorithm is formally described by Algorithm 2 and its guarantees given
below.

######  Lemma 4.2 (Private preconditioning, one round).

Let $\varepsilon>0$ be a privacy parameter, $d\in\mathbb{N}$, $\kappa\geq 20$,
and $\beta>0$ be a failure probability. There is a polynomial-time
$\varepsilon$-DP algorithm that, given $\varepsilon,\beta$ and

$n\geq\widetilde{O}\left(\frac{d^{2}+\log(1/\beta)}{\varepsilon}\right)$

i.i.d. samples $\mathcal{X}=\\{X_{1},X_{2},\ldots,X_{n}\\}$ from
$\mathcal{N}(0,\Sigma)$ for an unknown $\Sigma\in\mathbb{R}^{d\times d}$
satisfying $I\preceq\Sigma\preceq\kappa I$, outputs $A\in\mathbb{R}^{d\times
d}$ such that

$I\preceq A\Sigma A^{T}\preceq 0.99\kappa I$

with probability at least $1-\beta$.

###### Proof.

We will show that Algorithm 2 satisfies the claims. First, note that it is
$\varepsilon$-DP because the algorithm, based on PureDPMean, in Theorem 4.1 is
$\varepsilon$-DP and Algorithm 2 post-preprocesses its output. By our
distributional assumptions, with probability $1-\beta$ it holds that
$\widehat{\Sigma}$, computed in the second step of Algorithm 2, satisfies

$\left\lVert\widehat{\Sigma}-\Sigma\right\rVert_{F}\leq 0.01\kappa.$ (4.1)

This implies that, for any unit vectors $u,v$ it holds that

$\left|u^{T}\widehat{\Sigma}v-u^{T}\Sigma v\right|\leq 0.01\kappa.$

Let $V$ be the subspace spanned by all eigenvectors of $\widehat{\Sigma}$ with
corresponding eigenvalue at least $\kappa/2$, $\Pi$ be the projector onto $V$
and $\Pi_{\perp}$ be the projector onto $V^{\perp}$, the orthogonal complement
of $V$. We will now show that the matrix $A=\gamma\Pi+\Pi_{\perp}$ satisfies
$0.85I\preceq A\Sigma A\preceq 0.83\kappa I$ for $\gamma=0.9$. Then rescaling
$A$ by $1.19$ ensures that the conclusion of the lemma holds.

For the upper bound, we have that

$\displaystyle\left\lVert A\Sigma A\right\rVert_{2}$
$\displaystyle\leq\left\lVert A\widehat{\Sigma}A\right\rVert_{2}+\left\lVert
A\left(\Sigma-\widehat{\Sigma}\right)A\right\rVert_{2}$
$\displaystyle\leq\left\lVert
A\widehat{\Sigma}A\right\rVert_{2}+\left\lVert\Sigma-\widehat{\Sigma}\right\rVert_{2}\left\lVert
A\right\rVert_{2}^{2}$
$\displaystyle\leq\max\left(\kappa/2,\gamma^{2}\cdot\left\lVert\widehat{\Sigma}\right\rVert_{2}\right)+\left\lVert\Sigma-\widehat{\Sigma}\right\rVert_{2}\left\lVert
A\right\rVert_{2}^{2}$ $\displaystyle\leq\max\left(\kappa/2,\gamma^{2}\cdot
1.01\kappa\right)+0.01\kappa$
$\displaystyle\leq\left(1.01\gamma^{2}+0.01\right)\kappa$ $\displaystyle\leq
0.83\kappa,$

where the fist line is via triangle inequality, the second follows since the
spectral norm is sub-multiplicative, the third is by the choice of $A$, the
fourth line by the error guarantee of $\widehat{\Sigma}$ (Equation 4.1) and
$\|A\|_{2}\leq 1$, and the last two inequalities follow from simple algebra
and $\gamma=0.9$.

For the lower bound, consider any unit vector $u\in\mathbb{R}^{d}$. We will
lower bound $u^{T}A\Sigma Au$ in two different ways and maximize over the two.
First, because $\Sigma\succeq I$, we have that

$u^{T}A\Sigma Au\geq u^{T}A^{2}u=\gamma^{2}\left\lVert\Pi
u\right\rVert_{2}^{2}+\left\lVert\Pi_{\perp}u\right\rVert_{2}^{2}\geq\left\lVert\Pi_{\perp}u\right\rVert_{2}^{2}.$

For the second lower bound, we have

$u^{T}A\Sigma Au\geq\gamma^{2}u^{T}\Pi\Sigma\Pi u+\gamma
u^{T}\Pi_{\perp}\Sigma\Pi u+\gamma u^{T}\Pi\Sigma\Pi_{\perp}u.$

Since $\Pi u\in V$, the first term is lower bounded by
$.49\gamma^{2}\kappa\left\lVert\Pi u\right\rVert_{2}^{2}$. For the second (and
similarly for the third) term, we have that

$\left|\gamma u^{T}\Pi_{\perp}\Sigma\Pi u\right|\leq
0.01\gamma\kappa\left\lVert\Pi
u\right\rVert_{2}\left\lVert\Pi_{\perp}u\right\rVert_{2}\leq
0.01\gamma\kappa\left\lVert\Pi u\right\rVert_{2}.$

Aggregating these bounds, we have that for any unit vector
$u\in\mathbb{R}^{d}$, it holds that

$u^{T}A\Sigma
Au\geq\max\left(\left\lVert\Pi_{\perp}u\right\rVert_{2}^{2},\left(0.49\gamma^{2}\left\lVert\Pi
u\right\rVert_{2}^{2}-0.02\gamma\left\lVert\Pi
u\right\rVert_{2}\right)\kappa\right).$

Using the facts that $\kappa\geq 20$ and $\left\lVert\Pi
u\right\rVert_{2}^{2}+\left\lVert\Pi_{\perp}u\right\rVert_{2}^{2}=1$, it is
straightforward to verify that this lower bound is always at least $0.85$.
This completes the proof. ∎

###  4.2 Recursive Private Preconditioning

Given the weak conditioning algorithm, the natural next step is to recurse.
Applying the weak preconditioner for $O(\log\kappa)$ times suffices to put the
covariance nearly into identity.

1. Input: Samples $\mathcal{X}=\\{X_{1},X_{2},\ldots,X_{n}\\}\subset\mathbb{R}^{d}$, condition number $\kappa\geq 1$, privacy parameter $\varepsilon>0$. 2. Set $L=O(\log\kappa)$ and partition $\mathcal{X}=\mathcal{X}_{1}\sqcup\cdots\sqcup\mathcal{X}_{L}$ into $L$ subsets of size $n/L$ each. 3. Set $A_{0}=I_{d}$ and $\kappa_{1}=\kappa$. 4. For each $j\in[L]$: (a) Set $A_{<j}=\prod_{k=0}^{j-1}A_{k}$. (b) Run Algorithm 2 on samples $\left\\{A_{<j}X:X\in\mathcal{X}_{j}\right\\}$ with parameters $\left(\varepsilon,\beta=1/1000L,\kappa_{j}\right)$ to obtain a matrix $A_{j}\in\mathbb{R}^{d\times d}$. (c) Set $\kappa_{j+1}=0.99\kappa_{j}$. 5. Let $A=\prod_{i=j}^{L}A_{i}$ 6. Output: the preconditioning matrix $A$. Figure 3: Recursive private preconditioning algorithm

Specifically, we show that Algorithm 3 satisfies the following guarantees.

######  Theorem 4.3 (Private preconditioning, recursive).

Let $\varepsilon>0$ be a privacy parameter and $d\in\mathbb{N}$. There is a
polynomial-time $\varepsilon$-DP algorithm that, given

$n\geq\widetilde{O}\left(\frac{d^{2}\log(\kappa)}{\varepsilon}\right)$

i.i.d. samples $\mathcal{X}=\\{X_{1},\ldots,X_{n}\\}$ from
$\mathcal{N}(0,\Sigma)$ for an unknown $\Sigma\in\mathbb{R}^{d\times d}$
satisfying $I\preceq\Sigma\preceq\kappa I$, outputs a matrix
$A\in\mathbb{R}^{d\times d}$ such that

$I\preceq A\Sigma A\preceq 20I$

with probability at least $0.99$.

###### Proof.

We will show that Algorithm 3 satisfies the claims. It follows from parallel
composition (Theorem 3.3) and the privacy of the weak preconditioner (Theorem
4.2) that the algorithm is $\varepsilon$-DP. Assume without loss of generality
that $\kappa\geq 20$. By the choice of $L=O(\log(\kappa))$ and $\beta=1/1000L$
and an application of union bound, with probability as least $0.999$, all $L$
invocations of Algorithm 2, in step 4(b), succeed. We now condition on this
success event.

Let $\Sigma_{1}=\Sigma$ and $\Sigma_{j}=A_{<j}\Sigma_{j}A_{<j}$ for every
$j\leq L$. By the guarantee of Algorithm 2, in the $j$-th iteration we get a
preconditioning matrix $A_{j}$ such that

$I\preceq A_{j}\Sigma_{j}A_{j}\preceq 0.99\kappa_{j}I.$ (4.2)

By induction on $j$ and the choice of $L$, we have that $A$ satisfies
$I\preceq A\Sigma A\preceq 20I$. ∎

###  4.3 Putting it Together

We can now put everything together and prove one of our primary results, the
main statement of Theorem 1.1. For convenience, we restate it below as Theorem
4.4.

1. Input: Samples $\mathcal{X}=\\{X_{1},\ldots,X_{n}\\}\subset\mathbb{R}^{d}$, condition number $\kappa\geq 1$, privacy parameter $\varepsilon>0$. 2. Compute the preconditioning matrix $A\in\mathbb{R}^{d\times d}$ using $\\{X_{1},\ldots,X_{n/2}\\}$ as input to Algorithm 3 and privacy parameter $\varepsilon/2$. 3. Run Algorithm 1 PureDPMatrixMean on samples $\\{AX_{n/2+1},\ldots,AX_{n}\\}$ with privacy parameter $\varepsilon/2$ and error parameter $\alpha/20$ to obtain a covariance matrix $\Sigma_{1}\in\mathbb{R}^{d\times d}$. 4. Output: Covariance estimate $\widehat{\Sigma}=A^{-1}\Sigma_{1}A^{-1}$. Figure 4: Private covariance estimation algorithm

######  Theorem 4.4 (Pure DP covariance estimation).

Let $\alpha>0$ be an error parameter, $\varepsilon>0$ be a privacy parameter,
and $d\in\mathbb{N}$. There is a polynomial-time $\varepsilon$-DP algorithm
that, given $\varepsilon$ and

$n\geq\widetilde{O}\left(\frac{d^{2}\log(\kappa)}{\varepsilon}+\frac{d^{2}}{\alpha^{2}\varepsilon}+\frac{d\log(R)}{\varepsilon}\right)$

i.i.d. samples $\mathcal{X}=\\{X_{1},\ldots,X_{n}\\}$ from
$\mathcal{N}(0,\Sigma)$ for an unknown $\Sigma\in\mathbb{R}^{d\times d}$
satisfying $I\preceq\Sigma\preceq\kappa I$, outputs
$\widehat{\Sigma}=\widehat{\Sigma}(\mathcal{X})$ satisfying

$\left\lVert\Sigma^{-1/2}\widehat{\Sigma}\Sigma^{-1/2}-I\right\rVert_{F}\leq\alpha$

with probability at least $0.99$.

###### Proof.

We will show that Algorithm 4 satisfies the claims. First, note that the
algorithm is $\varepsilon$-DP by applying basic composition (Theorem 3.2) to
the privacy guarantees of Theorem 4.3 and Theorem 4.1. Moreover, the algorithm
is in polynomial time, since Algorithms 1 and 3 both run in polynomial time.

It now suffices to prove the utility guarantees. Let $\mathcal{X}$ consist of
$n$ i.i.d. samples from $\mathcal{N}(0,\Sigma)$, for an unknown $\Sigma$
satisfying $I\preceq\Sigma\preceq\kappa I$. By Theorem 4.3, if

$n\geq\widetilde{O}\left(\frac{d^{2}\log(\kappa)}{\varepsilon}\right)$

the preconditioner $A$ computed in step 2 of Algorithm 4 satisfies $I\preceq
A\Sigma A\preceq 20I$ with probability 0.99. Conditioned on this event, the
samples $\\{AX_{n/2+1},\ldots,AX_{n}\\}$ are i.i.d. according to
$\mathcal{N}(0,A\Sigma A)$. Since $A\Sigma A\preceq 20I$ and
$n\geq\widetilde{O}\left(\frac{d^{2}}{\alpha^{2}\varepsilon}\right)$,
Algorithm 1 will return a covariance matrix $\Sigma_{1}$ satisfying

$\left\lVert\Sigma_{1}-A\Sigma A\right\rVert_{F}\leq\alpha,$

with probability at least $0.99$. We translate this into a relative Frobenius
distance guarantee as follows. Notice that

$\displaystyle\alpha\geq\left\lVert\Sigma_{1}-A\Sigma A\right\rVert_{F}$
$\displaystyle=\left\lVert
A\Sigma^{1/2}\left(\Sigma^{-1/2}A^{-1}\Sigma_{1}A^{-1}\Sigma^{-1/2}-I\right)\Sigma^{1/2}A\right\rVert_{F}$
$\displaystyle\geq\lambda_{\min}\left(A\Sigma
A\right)\left\lVert\Sigma^{-1/2}A^{-1}\Sigma_{1}A^{-1}\Sigma^{-1/2}-I\right\rVert_{F},$

where the last step uses the sub-multiplicativity of the Frobenius norm. By
definition of the algorithm, the final estimate of $\Sigma$ is
$\widehat{\Sigma}=A^{-1}\Sigma_{1}A^{-1}$. Plugging this into the inequality
above, we have

$\displaystyle\alpha\geq\left\lVert\Sigma_{1}-A\Sigma
A\right\rVert_{F}\geq\lambda_{\min}\left(A\Sigma
A\right)\left\lVert\Sigma^{-1/2}\widehat{\Sigma}\Sigma^{-1/2}-I\right\rVert_{F}.$
(4.3)

Observe that $\lambda_{\min}\left(A\Sigma A\right)\geq 1$, since $I\preceq
A\Sigma A$. Applying this fact and rearranging the inequality 4.3, we get that

$\left\lVert\Sigma^{-1/2}\widehat{\Sigma}\Sigma^{-1/2}-I\right\rVert_{F}\leq\alpha,$
(4.4)

completing the proof. ∎

###  4.4 Application: General Pure DP Gaussian Estimation

We now show how to estimate a high-dimensional Gaussian with unknown mean and
covariance in statistical distance, under pure DP. This is by combining our
result on private covaraince estimation and the prior work on mean estimation
[HKM22]. The argument is standard: we simply estimate the mean and covariance
separately and apply Lemma 3.11 that converts closeness in parameters to
closeness in distribution.

##### Pure DP mean estimation

The first step of the algorithm is to privately estimate the mean. The idea is
simple and similar to [KLSU19]. If $\Sigma$ were known, then we can apply
$\Sigma^{-1/2}$ to the samples and run the mean estimation algorithm
(PureDPMean) of [HKM22] on input
$\left\\{\Sigma^{-1/2}X_{i}\right\\}_{i=1}^{n}$. For
$X_{i}\sim\mathcal{N}(\mu,\Sigma)$, we have
$\Sigma^{-1/2}X_{i}\sim\mathcal{N}\left(\Sigma^{-1/2}\mu,I\right)$. Thus, the
output $\widehat{\mu}$ of PureDPMean satisfies that
$\left\|\Sigma^{-1/2}(\mu-\widehat{\mu})\right\|_{2}\leq\alpha$, which is what
we need for distribution estimation (Lemma 3.11).

In the setting when $\Sigma$ is unknown, we apply our our preconditioning
algorithm to privately learn a matrix $A$ that is spectrally close to
$\Sigma^{-1/2}$. This effectively sets the samples to have near identity
covariance. We show it suffices for our purpose.

1. Input: Samples $\mathcal{X}=\\{X_{1},X_{2},\ldots,X_{3n}\\}\subset\mathbb{R}^{d}$, privacy parameter $\varepsilon>0$. 2. For each $i=1,2,\ldots,n$, let $Y_{i}=\frac{1}{\sqrt{2}}\left(X_{2i}-X_{2i-1}\right)$. 3. Compute the preconditioning matrix $A\in\mathbb{R}^{d\times d}$ using $\\{Y_{1},\ldots,Y_{n}\\}$ as input to Algorithm 3 and privacy parameter $\varepsilon/2$. 4. Run the algorithm PureDPMean in Theorem 3.10 [HKM22] on samples $\\{AX_{2n+1}/\sqrt{20},\ldots,AX_{3n}/\sqrt{20}\\}$ with privacy parameter $\varepsilon/2$, error parameter $\alpha/\sqrt{20}$, and failure rate $\beta=0.01$ to obtain a mean estimate $\tilde{\mu}\in\mathbb{R}^{d}$. 5. Output: Mean estimate $\widehat{\mu}=\sqrt{20}A^{-1}\tilde{\mu}$. Figure 5: Private mean estimation algorithm

Specifically, our private mean estimation procedure is described by Algorithm
5 and its guarantees given below.

######  Lemma 4.5 (Pure DP Gaussian mean estimation).

Let $\alpha>0$ be an error parameter, $\varepsilon>0$ be a privacy parameter,
$R\in\mathbb{R}$ and $d\in\mathbb{N}$. There is a polynomial-time
$\varepsilon$-DP algorithm that, given $\varepsilon$ and

$n\geq\widetilde{O}\left(\frac{d^{2}\log(\kappa)}{\varepsilon}+\frac{d}{\alpha^{2}\varepsilon}+\frac{d\log(R)}{\varepsilon}\right)$

i.i.d. samples $\mathcal{X}=\\{X_{1},\ldots,X_{n}\\}$ from
$\mathcal{N}(\mu,\Sigma)$ for an unknown $\mu$ satisfying $\|\mu\|_{2}\leq R$
and an unknown $\Sigma\in\mathbb{R}^{d\times d}$ satisfying
$I\preceq\Sigma\preceq\kappa I$, outputs $\widehat{\mu}$ satisfying

$\left\|\Sigma^{-1/2}(\mu-\widehat{\mu})\right\|_{2}\leq\alpha$

with probability at least $0.9$.

###### Proof.

The privacy follows from basic composition of the privacy property of
Algorithm 3 and PureDPMean. We focus on the utility analysis proving that
$\left\|\Sigma^{-1/2}(\mu-\widehat{\mu})\right\|_{2}\leq\alpha$.

Since input samples $\\{X_{1},X_{2},\ldots,X_{2n}\\}$ are i.i.d. from
$\mathcal{N}(\mu,\Sigma)$, the random vectors $\\{Y_{1},Y_{2},\ldots,Y_{n}\\}$
are i.i.d. according to $\mathcal{N}(0,\Sigma)$. By Theorem 4.3, the choice of
$n$ and our assumption on $\Sigma$, step 2 of Algorithm 5 outputs a
preconditioning matrix $A\in\mathbb{R}^{d\times d}$ such that

$I\preceq A\Sigma A\preceq 20I$ (4.5)

with probability at least $0.99$. Since $I\preceq\Sigma$ and $A\Sigma A\preceq
20I$, we have $\|A\|_{2}\leq\sqrt{20}$. Since $\\{X_{2n+1},\ldots,X_{3n}\\}$
are i.i.d. from $\mathcal{N}(\mu,\Sigma$), then in step 3,
$\\{AX_{2n+1}/\sqrt{20},\ldots,AX_{3n}/\sqrt{20}\\}$ are i.i.d. according to
$\mathcal{N}(A\mu/\sqrt{20},A\Sigma A/20)$. Recall that the guarantee from $A$
ensures $A\Sigma A/20\preceq I$. Moreover,
$\|A\mu/\sqrt{20}\|_{2}\leq\|A\|_{2}\|\mu\|_{2}/\sqrt{20}\leq R$, since
$\|A\|_{2}\leq\sqrt{20}$. Therefore, conditioned on these events, Theorem 3.10
implies that the mean estimate $\tilde{\mu}$ in step 3 satisfies that
$\|A\mu/\sqrt{20}-\tilde{\mu}\|_{2}\leq\alpha/\sqrt{20}$, and hence
$\|A(\mu-\widehat{\mu})\|_{2}\leq\alpha$, with probability at least $0.99$.
Now since $I\preceq A\Sigma A$, we have $\|\Sigma^{-1/2}A^{-1}\|_{2}\leq 1$.
Hence,
$\left\|\Sigma^{-1/2}(\mu-\widehat{\mu})\right\|_{2}\leq\|\Sigma^{-1/2}A^{-1}\|_{2}\cdot\|A(\mu-\widehat{\mu})\|_{2}\leq\alpha$,
with probability at least $0.99$. The proof follows by applying a union bound
over the failure probability of step 2 and 3 of Algorithm 5.

∎

##### Putting it Together

We now put together Lemma 4.5 on mean estimation and Theorem 4.4 on covariance
estimation to show:

######  Theorem 4.6 (Pure DP Gaussian estimation).

Let $\alpha>0$ be an error parameter, $\varepsilon>0$ be a privacy parameter,
$R\in\mathbb{R}$ and $d\in\mathbb{N}$. There is a polynomial-time
$\varepsilon$-DP algorithm that, given $\varepsilon$ and

$n\geq\widetilde{O}\left(\frac{d^{2}\log(\kappa)}{\varepsilon}+\frac{d^{2}}{\alpha^{2}\varepsilon}+\frac{d\log(R)}{\varepsilon}\right)$

i.i.d. samples $\mathcal{X}=\\{X_{1},\ldots,X_{n}\\}$ from
$\mathcal{N}(\mu,\Sigma)$ for an unknown $\mu$ satisfying $\|\mu\|_{2}\leq R$
and an unknown $\Sigma\in\mathbb{R}^{d\times d}$ satisfying
$I\preceq\Sigma\preceq\kappa I$, outputs $\widehat{\mu},\widehat{\Sigma}$ such
that

$\text{TV}\left(\mathcal{N}(\mu,\Sigma),\mathcal{N}\left(\widehat{\mu},\widehat{\Sigma}\right)\right)\leq
O(\alpha)$ (4.6)

with probability at least $0.8$.

###### Proof.

For simplicity, assume that $n$ is even. We use $n/2$ samples as input to the
private mean estimation algorithm (Algorithm 5) and another $n/2$ samples for
covariance estimation (Algorithm 4), both with a privacy parameter
$\varepsilon/2$. Privacy follows from basic composition (Theorem 3.2). For
utility, by our choice of $n$, Lemma 4.5 implies that

$\left\|\Sigma^{-1/2}(\mu-\widehat{\mu})\right\|_{2}\leq\alpha$

with probability $0.9$, and Theorem 4.4 implies that

$\left\lVert\Sigma^{-1/2}\widehat{\Sigma}\Sigma^{-1/2}-I\right\rVert_{F}\leq\alpha$

with probability $0.9$. Conditioned on the success of both steps, Lemma 6.10
yields the desired total variation guarantee, Equation 4.6. The failure
probability follows from an application of union bound. ∎

###  4.5 Robustness

We now argue that our algorithms are robust to adversarial corruptions, with
the cost that estimation error generally is worsened to
$\alpha+O(\sqrt{\eta})$, where $\eta$ is the fraction of corrupted samples. As
we discussed, our algorithm for learning Gaussian under pure DP is by reducing
the problem to black-box applications of the main procedure from [HKM22],
namely, PureDPMean in Theorem 3.10. We exploit the robustness property of
PureDPMean to show:

######  Theorem 4.7 (Robust pure DP Gaussian estimation).

Let $\alpha>0$ be an error parameter, $\varepsilon>0$ be a privacy parameter,
$R\in\mathbb{R}$ and $d\in\mathbb{N}$. For a sufficiently small constant
$\eta$, there is a polynomial-time $\varepsilon$-DP algorithm that, given
$\varepsilon$ and

$n\geq\widetilde{O}\left(\frac{d^{2}\log(\kappa)}{\varepsilon}+\frac{d^{2}}{\alpha^{2}\varepsilon}+\frac{d\log(R)}{\varepsilon}\right)$

$\eta$-corrupted samples $\mathcal{X}=\\{X_{1},\ldots,X_{n}\\}$ from
$\mathcal{N}(\mu,\Sigma)$ for an unknown $\mu$ satisfying $\|\mu\|_{2}\leq R$
and an unknown $\Sigma\in\mathbb{R}^{d\times d}$ satisfying
$I\preceq\Sigma\preceq\kappa I$, outputs $\widehat{\mu}$ and
$\widehat{\Sigma}$ such that

$\text{TV}\left(\mathcal{N}(\mu,\Sigma),\mathcal{N}\left(\widehat{\mu},\widehat{\Sigma}\right)\right)\leq
O(\alpha+\sqrt{\eta})$ (4.7)

with probability at least $0.8$.

To give a proof sketch, the key step is to observe that our recursive
preconditioning algorithm (Algorithm 3) is robust. Recall that the algorithm
simply calls our weak preconditioning scheme (Algorithm 2) recursively (for
$\log\kappa$ times). This weak scheme, in turn, runs PureDPMean to roughly
estimate $\Sigma$, up to an additive error of $0.01\kappa$ in the (absolute)
Frobenius norm. We observe that the robustness property of PureDPMean suffices
to yield the same error guarantee even under $\eta$-corruption. Hence, the
recursive preconditioning algorithm retains its performance under corruption.
Finally, the remaining steps of our algorithms for mean and covariance
estimation simply calls PureDPMean on the preconditioned samples. We lose the
extra factor of $\sqrt{\eta}$ from there.

We remark that in the analysis we make no attempt to optimize the breakdown
point of the algorithm. (In fact, it depends on the hidden constant in the
$O(\sqrt{\eta})$ error term of PureDPMean.)

###### Proof of Theorem 4.7.

We start by modifying step 2 of Algorithm 2 to invoke Algorithm 1 with
$\alpha=0.0099$ instead. By the choice of $n,\alpha$ and for a sufficiently
small $\eta$, Theorem 3.10 implies that the rough estimate $\widehat{\Sigma}$,
computed in the second step of Algorithm 2, satisfies

$\left\lVert\widehat{\Sigma}-\Sigma\right\rVert_{F}\leq 0.01\kappa$ (4.8)

with probability $1-\beta$. Observe that with the error bound above, the rest
of the proof of Theorem 4.2 remains valid. Inspecting the analysis of the
recursively preconditioning algorithm, we note that the error guarantee of
Theorem 4.2 suffices to imply Theorem 4.3.

We now argue for the error rate on covariance and mean estimation, separately.

  * •

For covariance estimation, consider Algorithm 4 and its guarantees Theorem
1.1. Step 2, the preconditioning step, of Algorithm 4 retains its performance
exactly. In step 3, we instead get an estimate $\widehat{\Sigma}$ such that
$\left\lVert\Sigma^{-1/2}\widehat{\Sigma}\Sigma^{-1/2}-I\right\rVert_{F}\leq\alpha+O(\sqrt{\eta})$,
due to the robustness property of PureDPMean.

  * •

For mean estimation, consider Algorithm 5 and its guarantees Lemma 4.5.
Similarly, step 3 of the algorithm retains its performance exactly, and we
lose an extra $O(\sqrt{\eta})$ factor in step 4. Hence, the algorithm outputs
an $\widehat{\mu}$ such that $\|\mu-\widehat{\mu}\|\leq\alpha+O(\sqrt{\eta})$.

Applying the Lemma 6.10 converts the parameter closeness to distribution
closeness, and this finishes the proof. ∎

##  5 Gaussian Sampling Mechanism

In this section, we provide an approximate DP mechanism for releasing a
covariance estimate. The mechanism is simple and natural. It works by
approximating a PSD matrix $\Sigma$ empirically with independent samples from
$\mathcal{N}(0,\Sigma)$.

##### Setting

Consider a setting where there is an estimation algorithm
$\mathcal{M}:\left(\mathbb{R}^{d}\right)^{n}\rightarrow\mathbb{S}_{+}^{d}$
that given $n$ samples in $\mathbb{R}^{d}$ outputs a PSD matrix. For us, the
algorithm $\mathcal{M}$, roughly speaking, will be the solution of a
stabilized convex program (minimizing a strongly convex potential). In
particular, we can guarantee a sensitivity bound in the relative Frobenius
distance such that

$\left\|\mathcal{M}({\cal Y})^{1/2}\mathcal{M}({\cal
Y}^{\prime})^{-1}\mathcal{M}({\cal Y})^{1/2}-I\right\|_{F}\leq\Delta$

for some small $\Delta$, on any neighboring datasets
$\mathcal{Y},\mathcal{Y}^{\prime}$. Moreover, we can show that
$\mathcal{M}(\mathcal{Y})$ is close to the true covariance $\Sigma$, if
$\mathcal{Y}$ are samples from $\mathcal{N}(0,\Sigma)$. Yet, $\mathcal{M}$ by
itself provides no privacy. The goal, therefore, is to privately release the
estimate $\mathcal{M}(\mathcal{Y})$, while retaining its statistical
performance.

In light of standard DP mechanisms, it is a natural idea to design an explicit
noise-injection mechanism to privatize $\mathcal{M}(\mathcal{Y})$. This is
indeed the approach of [KMV22]. To ensure that the noise level does not hamper
accuracy, though, their mechanism depends on the estimate itself, which leads
to much technical complications. We now give a significantly simpler solution
to this problem, which we believe may find applications elsewhere.

###  5.1 Algorithm

The algorithm we propose is extremely simple. Let
$\Sigma=\mathcal{M}({\mathcal{Y}})$ be the covariance we intend to release. We
approximate by empirical samples. That is, given $\Sigma$ and an accuracy
parameter $k$, we sample $g_{i}\sim\mathcal{N}(0,\Sigma)$ for each $i\in[k]$
and release $\widehat{\Sigma}=\frac{1}{k}\sum_{i=1}^{k}g_{i}g_{i}^{T}$. The
algorithm is formally given in Algorithm 6.

1. Input: A PSD matrix $\Sigma\in\mathbb{R}^{d\times d}$ and parameter $k\in\mathbb{N}$ 2. Obtain vectors $g_{1},g_{2},\ldots,g_{k}$ by sampling $g_{i}\sim\mathcal{N}(0,\Sigma)$, independently for each $i\in[k]$. 3. Output: Covariance estimate $\widehat{\Sigma}=\frac{1}{k}\sum_{i=1}^{k}g_{i}g_{i}^{T}$. Figure 6: The Gaussian Sampling Mechanism

###  5.2 Analysis

We now give a privacy and utility analysis of the algorithm. Intuitively, when
$k\rightarrow\infty$, the output $\widehat{\Sigma}\rightarrow\Sigma$, which
means good utility. However, this leads to no privacy, since
$\Sigma=\mathcal{M}(\mathcal{Y})$ is not private (w.r.t. $\mathcal{Y}$). Our
theorem characterizes the utility-privacy trade-off quantitatively (when $k$
is finite). Note that for fixed $\varepsilon,\delta$, the smaller the
sensitivity bound $\Delta$ is, the higher we get to choose $k$, which leads to
better approximation accuracy.

######  Theorem 5.1 (Analysis of the Gaussian Sampling Mechanism).

Fix $\varepsilon,\delta\in(0,1)$ and $k\in\mathbb{N}$ and let

$\Delta=\min\left(\frac{\varepsilon}{\sqrt{8k\log(1/\delta)}},\frac{\varepsilon}{8\log(1/\delta)}\right)<1.$

Let $\mathcal{M}:\left(\mathbb{R}^{d}\right)^{n}\rightarrow\mathbb{S}_{+}^{d}$
be a (randomized) algorithm that given a dataset of $n$ points in
$\mathbb{R}^{d}$ outputs a PSD matrix. Suppose that $\mathcal{M}$ satisfies a
sensitivity bound that

$\left\|\mathcal{M}({\cal Y})^{1/2}\mathcal{M}({\cal
Y}^{\prime})^{-1}\mathcal{M}({\cal Y})^{1/2}-I\right\|_{F}\leq\Delta$

for any neighboring datasets $\mathcal{Y},\mathcal{Y}^{\prime}$. Then given an
input $\Sigma=\mathcal{M}(\mathcal{Y})$,

  * •

Algorithm 6 is $(\varepsilon,\delta)$-DP (with respect to the original dataset
$\mathcal{Y}$); and

  * •

Algorithm 6 outputs $\widehat{\Sigma}\in\mathbb{S}_{+}^{d}$ such that with
probability at least $1-\gamma$,

$\left\lVert\Sigma^{-1/2}\widehat{\Sigma}\Sigma^{-1/2}-I\right\rVert_{F}\leq\rho$

for
$\rho=O\left(\sqrt{\frac{d^{2}+\log(1/\gamma)}{k}}+\frac{d^{2}+\log(1/\gamma)}{k}\right)$.

###### Proof.

The utility guarantee is immediately implied by Theorem 3.13. For the proof of
privacy, let

$f_{\Sigma}(x)=(2\pi)^{-\frac{d}{2}}\det(\Sigma)^{-\frac{1}{2}}\exp\left(-\frac{1}{2}x^{\top}\Sigma^{-1}x\right)$

denote the ${\cal N}(0,\Sigma)$ density function, let $\Sigma_{1}=\Sigma({\cal
Y})$ and $\Sigma_{2}=\Sigma({\cal Y^{\prime}})$ for neighboring datasets
${\cal Y},{\cal Y^{\prime}}$, and let $g_{1},\ldots,g_{k}$ be the i.i.d.
samples from ${\cal N}(0,\Sigma_{1})$ output by Algorithm 6. By Theorem 3.8,
it suffices to show that $\Pr\left[Z>\varepsilon\right]\leq\delta,$ where

$Z=\sum_{i=1}^{k}\log\left(\frac{f_{\Sigma_{1}}(g_{i})}{f_{\Sigma_{2}}(g_{i})}\right)$

is the privacy loss random variable. To this end, define
$A=\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}$ and let
$A=\sum_{j=1}^{d}\lambda_{j}v_{j}v_{j}^{\top}$ be its spectral decomposition.
By assumption, we have

$\sqrt{\sum_{j=1}^{d}(\lambda_{j}-1)^{2}}=\|A-I\|_{F}\leq\Delta.$

Similarly, letting $B=\Sigma_{2}^{1/2}\Sigma_{1}^{-1}\Sigma_{2}^{-1/2}$ and
switching the roles of ${\cal Y}$ and ${\cal Y}^{\prime}$, we see that

$\sqrt{\sum_{j=1}^{d}(1-1/\lambda_{j})^{2}}=\|I-A^{-1}\|_{F}=\|I-B\|_{F}\leq\Delta.$

In the above calculation, we have used the fact that $A^{-1}=CC^{\top}$ and
$B=C^{\top}C$ for the matrix $C=\Sigma_{1}^{-1/2}\Sigma_{2}^{1/2}$, and hence
$A^{-1}$ and $B$ have the same eigenvalues. Next, let

$h_{ij}=\left\langle\Sigma_{1}^{-1/2}g_{i},v_{j}\right\rangle,$

and note that the random variables $h_{ij}$ are i.i.d. copies of ${\cal
N}(0,1)$. Using this notation, the privacy loss random variable $Z$ can be
expressed as follows:

$\displaystyle Z$
$\displaystyle=\sum_{i=1}^{k}\log\left(\frac{\det(\Sigma_{1})^{-\frac{1}{2}}\exp\left(-\frac{1}{2}g_{i}^{\top}\Sigma_{1}^{-1}g_{i}\right)}{\det(\Sigma_{2})^{-\frac{1}{2}}\exp\left(-\frac{1}{2}g_{i}^{\top}\Sigma_{2}^{-1}g_{i}\right)}\right)$
$\displaystyle=\sum_{i=1}^{k}\left(\frac{1}{2}g_{i}^{\top}\left(\Sigma_{2}^{-1}-\Sigma_{1}^{-1}\right)g_{i}-\frac{1}{2}\log\left(\frac{\det(\Sigma_{1})}{\det(\Sigma_{2})}\right)\right)$
$\displaystyle=\frac{1}{2}\sum_{i=1}^{k}\left(\left(\Sigma_{1}^{-1/2}g_{i}\right)^{\top}(A-I)\left(\Sigma_{1}^{-1/2}g_{i}\right)-\log\det(A)\right)$
$\displaystyle=\frac{1}{2}\sum_{i=1}^{k}\sum_{j=1}^{d}\Big{(}(\lambda_{j}-1)h_{ij}^{2}-\log(\lambda_{j})\Big{)},$

where the last step is by taking the spectral decomposition of $A$. Since
$h_{ij}^{2}\sim\chi^{2}_{1}$, Theorem 3.17 (sub-exponential parameters of
$\chi^{2}_{1}$) and Theorem 3.18 (sub-exponential parameters of an independent
sum) imply that $Z$ is a sub-exponential random variable with parameters
$\nu=\sqrt{k}\|A-I\|_{F}\leq\sqrt{k}\Delta$ and $\alpha=2\|A-I\|_{2}\leq
2\Delta$. Also, the mean of $Z$ is

$\displaystyle\mathbb{E}[Z]$
$\displaystyle=\frac{k}{2}\sum_{j=1}^{d}\left(\lambda_{j}-1-\log\left(\lambda_{j}\right)\right)$
(by linearity of expectation)
$\displaystyle\leq\frac{k}{2}\sum_{j=1}^{d}\left(\lambda_{j}-2+1/\lambda_{j}\right)$
$\displaystyle\text{(since $\lambda_{j}>0$ and}\log(x)\geq 1-1/x\text{ for
$x>0$})$
$\displaystyle=\frac{k}{2}\sum_{j=1}^{d}(\lambda_{j}-1)(1-1/\lambda_{j})$
$\displaystyle\leq\frac{k}{2}\|A-I\|_{F}\left\|I-A^{-1}\right\|_{F}$ (by
Cauchy-Schwarz) $\displaystyle\leq\frac{k}{2}\Delta^{2}$ (by the above
discussion) $\displaystyle\leq\frac{\varepsilon}{2}$ (because
$\Delta<\varepsilon/\sqrt{k}$ and $\varepsilon<1$).

Finally, using Theorem 3.16 (sub-exponential tail bound), we conclude that

$\Pr[Z>\varepsilon]\leq\Pr\left[Z-\mathbb{E}[Z]>\frac{\varepsilon}{2}\right]\leq\max\left\\{e^{-\frac{(\varepsilon/2)^{2}}{2\nu^{2}}},e^{-\frac{\varepsilon/2}{2\alpha}}\right\\}\leq\delta$

by plugging in the values of $\nu$, $\alpha$, and $\Delta$. This proves that
Algorithm 6 is $(\varepsilon,\delta)$-DP. ∎

##  6 Approximate DP Robust Estimation

In this section, we give an efficient algorithm for private and robust
estimation of mean and covariance of a high-dimensional Gaussian. The main
idea is to improve the sensitivity bound of [KMV22] via minimizing an entropy
potential instead of the 2-norm objective. Moreover, we use our Gaussian
sampling mechanism to replace the noise-addition mechanism of [KMV22] to
improve the sample cost.

Throughout we let $\textsf{Ent}(x)=\sum_{i=1}^{n}x_{i}\log(1/x_{i})+x_{i}$ be
the (unnormalized) negative entropy function,
$\mathcal{Y}=\\{Y_{i}\\}_{i=1}^{n}$ be the input data and $\eta$ be the
(fixed) corruption rate.

###  6.1 Stable Outlier Rate Selection

The main subroutine of our algorithm is to search for pseudo-distributions
that, in addition to satisfying certain witness checking constraints
$\mathcal{A}_{C,\eta,n}(\mathcal{Y})$, also minimize a strongly convex
potential.

######  Definition 6.1 (Potential).

Let $C>0$, $\eta\in[0,1]$, $t\in\mathbb{N}$,
$\mathcal{Y}\subset\mathbb{R}^{d}$ be a dataset of size $n$ and
$f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be convex. For any degree-$2t$ pseudo-
distribution $\zeta$ consistent with $\mathcal{A}_{C,\eta,n}(\mathcal{Y})$,
let
$\textsf{Pot}_{C,\eta,n,\zeta}(\mathcal{Y})=f\left(\widetilde{\mathbb{E}}_{\zeta}[w]\right)$.
Let
$\textsf{Pot}_{C,\eta,n}(\mathcal{Y})=\min_{\zeta}\textsf{Pot}_{C,\eta,n,\zeta}(\mathcal{Y})$,
where the minimum is over all degree-$2t$ pseudo-distributions $\zeta$
satisfying $\mathcal{A}_{C,\eta,n}(\mathcal{Y})$. If no such $\zeta$ exists,
we define $\textsf{Pot}_{C,\eta,n}(\mathcal{Y})=\infty$.

We choose $f(x)=-\textsf{Ent}(x)/\log(n)$. Moreover, we will define different
constraint systems $\mathcal{A}^{\textsf{mean}}_{C,\eta,n}(\mathcal{Y})$ and
$\mathcal{A}^{\textsf{cov}}_{C,\eta,n}(\mathcal{Y})$ for mean and covariance
estimation, respectively. Before that, the first step of our estimator is to
randomly select an outlier rate $\eta^{\prime}$ such that the potential
function on the pseudo-distribution we compute is close on two neighboring
input datasets.

##### DP Selection

Our algorithm of approximate DP estimation uses the private outlier rate
selection procedure of [KMV22]. For that, we need to apply the exponential
mechanism to select an outlier rate that satisfies a stability threshold. With
the vanilla exponential mechanism, however, one is not guaranteed to get
candidates with score above a certain threshold. Theorem 6.1 provides an
$(\varepsilon,\delta)$-DP selection mechanism, where the candidate selected
has utility score that is above a certain threshold. The caveat is that, with
probability at most $\beta$, the procedure might output $\perp$.

######  Lemma 6.1 (Theorem 3.34 of [KMV22]).

Fix $\beta\in(0,1]$. Let $\varepsilon,\delta\in(0,1]$ be privacy parameters.
$\Delta$ is the sensitivity bound for the scoring function. Let $\mathcal{C}$
be a set of candidates and let
$\textsf{score}:\mathcal{C}\times\mathcal{Y}\rightarrow{\mathbb{R}}$ be a
scoring function for candidates as a function of the databases
$Y\in\mathcal{Y}$, such that its sensitivity (w.r.t. $Y$) is at most $\Delta$.

There exists an algorithm DP-Selection with input parameter $\kappa$ that
satisfies the following properties:

  1. 1.

DP-Selection is $(\varepsilon,\delta)$-DP.

  2. 2.

If the output of DP-Selection is $c^{*}\neq\perp$, then
$\textsf{score}(c^{*},Y)\geq\kappa$.

  3. 3.

If there exists $c\in\mathcal{C}$ such that
$\textsf{score}(c,Y)\geq\kappa+O\left(\frac{\Delta}{\varepsilon}\cdot\log\left(\frac{|\mathcal{C}|}{\beta\delta}\right)\right)$,
then DP-Selection output $\perp$ with probability at most $\beta$.

While the exact implementation of DP-Selection is unimportant for us, it’s
simply a variant of the exponential mechanism, and we describe it in detail in
Section A.2 for the sake of completeness.

##### Outlier Rate Selection Mechanism

Now we describe the private outlier rate selection mechanism $\mathcal{M}_{1}$
in detail. The procedure is via running the DP-Selection mechanism with a
score function tied to the stability of the convex program.

In the following, the constraint system $\mathcal{A}(\eta^{\prime})$ generally
refers to $\mathcal{A}^{\textsf{mean}}_{C,\eta^{\prime},n}(\mathcal{Y})$ or
$\mathcal{A}^{\textsf{cov}}_{C,\eta^{\prime},n}(\mathcal{Y})$, for fixed $C,n$
and input data $\mathcal{Y}$.

######  Definition 6.2 (Stability).

Fix $L\in\mathbb{N}$. Let $\tau,\gamma\in\\{0,\dots,n\\}$ such that
$\gamma\leq\tau,n-\tau$. Suppose for some $Y\subseteq\mathbb{R}^{d}$ of size
$n$, the constraint system $\mathcal{A}((\tau-\gamma)/n)$ is feasible. We
define the stability of the $2\gamma$ length interval centered at $\tau$ to be

$\displaystyle\mathrm{stab}_{Y}(\tau,\gamma)=\textsf{Pot}_{(\tau-\gamma)/n}(Y)-\textsf{Pot}_{(\tau+\gamma)/n}(Y)$

######  Definition 6.3 (Score function).

Fix $n,k\in\mathbb{N}$ and $C>0$. Let $Y\subseteq\mathbb{R}^{d}$ be a set of
size $n$. For a parameter $L$, we define the following score function for
every integer $\tau\in[n]$:

$\displaystyle\textsf{score}_{n,C,k}(\tau,Y)=\begin{cases}0&\text{ if
}\mathcal{A}_{C,k,\tau/n,n}(Y)\text{ is infeasible},\\\
\max_{\gamma\atop\mathcal{A}_{C,k,(\tau-\gamma)/n,n}(Y)\text{ is
feasible}}\min\\{\gamma,20L-n\cdot\mathrm{stab}_{Y}(\tau,\gamma)\\}&\text{
otherwise}.\end{cases}$

In the second case, we define
$\gamma^{*}_{Y}(\tau):=\arg\max_{\gamma\atop\mathcal{A}_{C,k,(\tau-\gamma)/n,n}(Y)\text{
is feasible}}\min\\{\gamma,L-\mathrm{stab}_{Y}(\tau,\gamma)\\}$.

1. Input: The true outlier rate $\eta$, privacy loss $\varepsilon,\delta$, threshold $L$ 2. Run the $(\varepsilon,\delta)$-DP DP-Selection mechanism with $\kappa=L$ and score function defined in Definition 6.3 to sample $\tau\in[0,\eta n]$ or get $\perp$ 3. Output: An integer $\tau\in[0,\eta n]$ or $\perp$ Figure 7: The private outlier rate selection mechanism $\mathcal{M}_{1}$

Given a stability threshold (intuitively indicates how unstable the convex
program selecting the witness is), privacy parameters
$\varepsilon,\delta\in(0,1)$, and outlier rate $\eta\in[0,1/2)$, Algorithm 7
returns $\tau$, a value that defines a “stable” interval of outlier rates:
$[\tau/n-0.5L/n,\tau/n-0.5L/n]$.

##### Analysis

We analyze the outlier rate selection mechanism $\mathcal{M}_{1}$ as follows.
Our choice of entropy objective makes the analysis significantly differ from
[KMV22].

Moreover, for our privacy analysis, we rely on the following simple
observation about adjacent pseudo-distributions that are induced by adjacent
datasets:

######  Lemma 6.2 (Adjacent Pseudo-distributions, Lemma 4.9 of [KMV22]).

Let $\zeta$ be a pseudo-distribution of degree $2k$ that satisfies all the
constraints in $\mathcal{A}_{C,\eta,n}(\mathcal{Y})$ on dataset $\mathcal{Y}$
with outlier rate $\eta$. Let $\mathcal{Y}^{\prime}\subseteq\mathbb{R}^{d}$ be
adjacent to $Y$. Define an _adjacent pseudo-distribution_ $\zeta^{\prime}$
(that “zeroes out $w_{i}$”) by
$\widetilde{\mathbb{E}}_{\zeta^{\prime}}[w_{S}p(X^{\prime},\cdots)]=\widetilde{\mathbb{E}}_{\zeta}[w_{S}p(X^{\prime},\cdots)]$
if $i\not\in S$ and
$\widetilde{\mathbb{E}}_{\zeta^{\prime}}[w_{S}p(X^{\prime},\cdots)]=0$ if
$i\in S$ for every polynomial $p$ in $X^{\prime}$ and other auxiliary
indeterminates in $\mathcal{A}_{C,\eta,n}(\mathcal{Y})$. Then,
$\zeta^{\prime}$ is a pseudo-distribution of degree $2k$ that satisfies all
the constraints in $\mathcal{A}_{C,\eta,n}(\mathcal{Y})$ on both inputs
$\mathcal{Y}^{\prime}$ and $\mathcal{Y}$ with outlier parameter $\eta+1/n$.

To establish the sensitivity of the outlier rate selection procedure, we
require certain properties of the Ent objective:

######  Lemma 6.3 (Properties of Ent).

The function $f(x)=-\textsf{Ent}(x)/\log(n)$ satisfies the following
properties:

  1. (i)

For any $x\in[0,1/n]^{n}$ which satisfies $1\geq\left\lVert
x\right\rVert_{1}\geq(1-\eta)$, and $j\in[n]$, define
$\tilde{x}\in\mathbb{R}^{n}$ by $\tilde{x}_{j}=0$ and $\tilde{x}_{i}=x_{i}$
for $i\neq j$. Then it holds that $f(\tilde{x})\leq
f(x)+\frac{1}{n}+\frac{1}{n\log(n)}$.

  2. (ii)

For any $x\in[0,1]^{n}$ which satisfies $1\geq\left\lVert
x\right\rVert_{1}\geq(1-\eta)$, it holds that

$-1\leq f(x)\leq-(1-\eta)-\frac{1-\eta}{\log(n)}.$

###### Proof.

  1. (i)

Observe that
$\log(n)(f(\tilde{x})-f(x))=\textsf{Ent}(x)-\textsf{Ent}(\tilde{x})=x_{j}\log(1/x_{j})+x_{j}\leq\frac{\log(n)+1}{n}$.
Rearranging completes the proof.

  2. (ii)

Define the function $h(x)=\sum_{i=1}^{n}\frac{x_{i}}{\left\lVert
x\right\rVert_{1}}\log\left(\frac{\left\lVert
x\right\rVert_{1}}{x_{i}}\right)$ and observe that $\left\lVert
x\right\rVert_{1}h(x)=\left\lVert x\right\rVert_{1}\log(\left\lVert
x\right\rVert_{1})+\textsf{Ent}(x)-\left\lVert x\right\rVert_{1}$. Using the
fact that $h(x)\leq\log(n)$ for all $x\in[0,1]^{n}$ and rearranging completes
the proof of the lower bound on $f(x)$.

For the upper bound, begin by noting that $h(x)=h(x/\left\lVert
x\right\rVert_{1})$ and that $x/\left\lVert
x\right\rVert_{1}\in[0,1/(1-\eta)n]^{n}$. It is a standard fact that the min-
entropy of a distribution lower bounds the Shannon entropy. Hence,
$h(x/\left\lVert x\right\rVert_{1})\geq\log((1-\eta)n)$. Using the fact that
$\left\lVert x\right\rVert_{1}\geq(1-\eta)$ and rearranging completes the
proof of the upper bound on $f(x)$.

∎

We now show that for any stable interval defined around $\tau\in[0,\eta n]$,
the interval cannot have a significantly different value than another smaller-
length interval defined around $\tau$:

######  Lemma 6.4 (see Lemma 4.13 of [KMV22]).

Let $\tau,\gamma\in[n]$ such that $\gamma\leq\tau,n-\tau$. Suppose for some
$\mathcal{Y}\subseteq\mathbb{R}^{d}$ of size $n$, the constraint system
$\mathcal{A}_{C,(\tau-\gamma)/n,n}(\mathcal{Y})$ is feasible for both
$\mathcal{Y}.\mathcal{Y}^{\prime}$, where $\mathcal{Y}^{\prime}$ is a
neighboring dataset. Then, for any $\tau,\gamma$,

$\mathrm{stab}_{\mathcal{Y}^{\prime}}(\tau,\gamma-1)\leq\mathrm{stab}_{\mathcal{Y}}(\tau,\gamma)+\frac{2}{n}+\frac{2}{n\log(n)}$

###### Proof.

Using Lemmas 6.2, 6.3 and noting that if $\zeta^{\prime}$ is adjacent to
$\zeta$ then

$f\left(\widetilde{\mathbb{E}}_{\zeta^{\prime}}[w]\right)\leq
f\left(\widetilde{\mathbb{E}}_{\zeta}[w]\right)+\frac{1}{n}+\frac{1}{n\log(n)},$

we have:

$\textsf{Pot}_{(\tau-\gamma+1)/n}(\mathcal{Y}^{\prime})\leq\textsf{Pot}_{(\tau-\gamma)/n}(\mathcal{Y})+\frac{1}{n}+\frac{1}{n\log(n)},$

and

$\textsf{Pot}_{(\tau+\gamma)/n}(\mathcal{Y})\leq\textsf{Pot}_{(\tau+\gamma-1)/n}(\mathcal{Y}^{\prime})+\frac{1}{n}+\frac{1}{n\log(n)}.$

Combining the two equations yields

$\displaystyle\mathrm{stab}_{\mathcal{Y}^{\prime}}(\tau,\gamma-1)$
$\displaystyle=\textsf{Pot}_{(\tau-\gamma+1)/n}(\mathcal{Y}^{\prime})-\textsf{Pot}_{(\tau+\gamma-1)/n}(\mathcal{Y}^{\prime})$
$\displaystyle\leq\textsf{Pot}_{(\tau-\gamma)/n}(\mathcal{Y})-\textsf{Pot}_{(\tau+\gamma)/n}(\mathcal{Y})+\frac{2}{n}+\frac{2}{n\log(n)}$
$\displaystyle=\mathrm{stab}_{\mathcal{Y}}(\tau,\gamma)+\frac{2}{n}+\frac{2}{n\log(n)}.\qed$

To use the exponential mechanism (with any reasonable amount of utility), we
need a small sensitivity on the score function. We show that the score
function, as defined, has a small sensitivity:

######  Lemma 6.5 (Sensitivity of Score Function, Lemma 4.14 of [KMV22]).

Let $\mathcal{Y},\mathcal{Y}^{\prime}$ be set of $n$ points in
$\mathbb{R}^{d}$ differing at most in one point, and $\tau\in[n]$. Then, for
every $\tau>0$,

$|\textsf{score}(\tau,\mathcal{Y})-\textsf{score}(\tau,\mathcal{Y}^{\prime})|\leq
6.$ (6.1)

###### Proof.

The proof of this lemma is identical to that of Lemma 4.14 of [KMV22], but
invokes Lemma 6.4 instead of Lemma 4.13 in [KMV22]. ∎

The following lemma shows that not too many intervals can be unstable. This
implies that there must exist at least one stable interval:

######  Lemma 6.6 (Existence of a Good Stable Interval, Lemma 4.15 of
[KMV22]).

Suppose $\mathcal{A}_{C,\eta/2,n}(\mathcal{Y})$ is feasible . For every
$L\in[0,0.25\eta n]$, there is a $\tau\in[0,\eta n]$ such that
$\textsf{score}(\tau,\mathcal{Y})\geq L$.

###### Proof.

Consider
$\textsf{Pot}_{\eta/2},\textsf{Pot}_{\eta/2+2L/n},\dots,\textsf{Pot}_{\eta/2+2Lr/n}$
where $r:=\lfloor 0.25\eta n/L\rfloor$. Observe that
$\textsf{Pot}_{\eta/2}(Y)-\textsf{Pot}_{\eta}(Y)\leq\eta$ by Lemma 6.3.
Therefore, there must exist $r^{*}\in[r]$ such that

$\textsf{Pot}_{\eta/2+2L(r^{*}-1)/n}-\textsf{Pot}_{\eta/2+2Lr^{*}/n}\leq\frac{\eta}{r}\leq\frac{8L}{n}.$

Let $\tau=\eta/2+(2Lr^{*}-1)/n$ and $\gamma=L$. Then, we have
$\mathrm{stab}(\tau,\gamma)\leq\frac{8L}{n}$ and, thus,

$\displaystyle
n\cdot\textsf{score}(\tau,\mathcal{Y})\geq\min\\{\gamma,20L-8L\\}\geq L,$

and this finishes the proof. ∎

Since we are using the exponential mechanism to select a stable interval, we
now show that with high probability, we will succeed:

######  Lemma 6.7 (Utility of Score Function, Lemma 4.16 of [KMV22]).

Suppose $\mathcal{A}_{C,\eta/2,n}(\mathcal{Y})$ is feasible. Let
$\varepsilon,\delta,\beta\in(0,1]$. For every $L\in[0,0.25\eta n]$, if $L\geq
O\left(\frac{1}{\varepsilon}\cdot\log\left(\frac{n}{\beta\delta}\right)\right)$,
then with probability $1-\beta$, Theorem 6.1, invoked with the score function
in Definition 6.3 and $\kappa=L/2$, does not reject, and the output $\tau$
satisfies $\mathrm{stab}_{\mathcal{Y}}(\tau,L/2)<\frac{20L}{n}$.

###### Proof.

This follows from the guarantee of DP-Selection (Theorem 6.1), Lemma 6.6 and
the definition of score. ∎

######  Lemma 6.8 (Sensitivity from potential stability).

Let $x,x^{\prime}\in[0,2/n]^{n}$ such that
$|\textsf{Ent}(x)-\textsf{Ent}(x^{\prime})|\leq L/n$ for some $L\geq 0$. Then
$\left\lVert x-x^{\prime}\right\rVert_{1}\leq O(L/n\log(n))$.

###### Proof.

We begin by writing $x=y+z$ and $x^{\prime}=y^{\prime}+z^{\prime}$, where:

  * •

$y^{\prime}_{i}=x^{\prime}_{i}$ and $y_{i}=x_{i}$ for all coordinates $i$ for
which $x^{\prime}_{i}\geq x_{i}$ and $y^{\prime}_{i}=y_{i}=0$ for all other
coordinates. Hence, $y^{\prime}\geq y$ coordinate-wise.

  * •

$z^{\prime}_{i}=x^{\prime}_{i}$ and $z_{i}=x_{i}$ for all coordinates $i$ for
which $x^{\prime}_{i}<x_{i}$ and $z^{\prime}_{i}=z_{i}=0$ for all other
coordinates. Hence, $z^{\prime}<z$ coordinate-wise.

Next, note that
$\textsf{Ent}(x)=\textsf{Ent}(y)+\textsf{Ent}(z),\textsf{Ent}(x^{\prime})=\textsf{Ent}(y^{\prime})+\textsf{Ent}(z^{\prime})$.
Also, it holds that $\textsf{Ent}(y^{\prime})\geq\textsf{Ent}(y)$ and
$\textsf{Ent}(z^{\prime})\leq\textsf{Ent}(z)$ by monotonicity of the function
$g(x)=x\log(1/x)+x$ on the domain $[0,1]$. Assembling these facts, we have by
the triangle inequality that

$\max\left(|\textsf{Ent}(y)-\textsf{Ent}(y^{\prime})|,|\textsf{Ent}(z)-\textsf{Ent}(z^{\prime})|\right)\leq|\textsf{Ent}(x)-\textsf{Ent}(x^{\prime})|\leq
O(L/n).$

Thus, to complete the proof, it suffices to show that $\left\lVert
y-y^{\prime}\right\rVert_{1}\leq O(L/n)$, as the case for $z,z^{\prime}$ is
symmetric and $\left\lVert x-x^{\prime}\right\rVert_{1}=\left\lVert
y-y^{\prime}\right\rVert_{1}+\left\lVert z-z^{\prime}\right\rVert_{1}$.
Without loss of generality, since $y^{\prime}\geq y$, we may assume that
coordinates of $y^{\prime}$ are positive. Otherwise, we may decompose both
$\textsf{Ent}(y^{\prime})-\textsf{Ent}(y)$ and $y^{\prime}-y$ into a sum of
terms depending on the support and the complement of the support and apply the
argument below only on the support of $y^{\prime}$.

Because Ent is a concave function, we have that

$\textsf{Ent}(y^{\prime})-\textsf{Ent}(y)\geq\left\langle\nabla\textsf{Ent}(y^{\prime}),y^{\prime}-y\right\rangle,$

where $(\nabla\textsf{Ent}(y^{\prime}))_{i}=\log(1/y^{\prime}_{i})$888Note
that Ent is differentiable at $y^{\prime}$ since $y^{\prime}>0$.. Since
$y^{\prime}_{i}\leq 2/n$ for all $i\in[n]$, it holds that
$\left\langle\nabla\textsf{Ent}(y^{\prime}),y^{\prime}-y\right\rangle\geq\log(n/2)\left\lVert
y^{\prime}-y\right\rVert_{1}$. Rearranging and using the fact that
$\textsf{Ent}(y^{\prime})-\textsf{Ent}(y)\leq O(L/n)$ gives the desired bound.
∎

We now state the main guarantee of our private outlier rate selection
procedure.

######  Lemma 6.9 (Guarantees of private outlier rate selection).

Let $\beta\in(0,1)$ be a failure probability parameter, $\varepsilon,\delta$
be privacy parameters and $\eta\in[0,1/2)$ be a sufficiently small constant.
Let the parameters satisfy $\eta n\geq L$, where
$L=\Omega\left(\frac{1}{\varepsilon}\log\left(\frac{n}{\beta\delta}\right)\right)$.
Then, there is an $(\varepsilon,\delta)$-DP mechanism $\mathcal{M}_{1}$ that
on input dataset $\mathcal{Y}\subset\mathbb{R}^{d}$ of size $n$, outlier rate
$\eta\in(0,1/2)$ and parameter $C$ outputs
$\eta^{\prime}\in[\eta/2,\eta]\cup\\{\bot\\}$ with the following guarantees:

  1. (i)

Let $\mathcal{Y}^{\prime}$ be a neighboring dataset to $\mathcal{Y}$. If the
mechanism does not output $\bot$ on either $\mathcal{Y}$ or
$\mathcal{Y}^{\prime}$, then
$|\textsf{Pot}_{\eta^{\prime}}(\mathcal{Y})-\textsf{Pot}_{\eta^{\prime}}(\mathcal{Y}^{\prime})|\leq
O(L)$. Furthermore, let $\zeta$ and $\zeta^{\prime}$ degree-$2t$ pseudo-
distributions satisfying
$\textsf{Pot}_{C,\eta,n}(\mathcal{Y})=\textsf{Pot}_{C,\eta,n,\zeta}(\mathcal{Y})$
and
$\textsf{Pot}_{C,\eta,n}(\mathcal{Y}^{\prime})=\textsf{Pot}_{C,\eta,n,\zeta^{\prime}}(\mathcal{Y}^{\prime})$
and
$p=\widetilde{\mathbb{E}}_{\zeta}[w]/\left\lVert\widetilde{\mathbb{E}}_{\zeta}[w]\right\rVert_{1},p^{\prime}=\widetilde{\mathbb{E}}_{\zeta}[w^{\prime}]/\left\lVert\widetilde{\mathbb{E}}_{\zeta}[w^{\prime}]\right\rVert_{1}$.
Then, it holds that

$\left\lVert p-p^{\prime}\right\rVert_{1}\leq\frac{120L}{n}.$

  2. (ii)

The mechanism outputs $\bot$ with probability at most $\beta$.

###### Proof.

An argument nearly identical to the proof of Lemma 4.17 of [KMV22] ensures
that the second part of the claim holds and that
$|\textsf{Pot}_{\eta^{\prime}}(\mathcal{Y})-Pot_{\eta^{\prime}}(\mathcal{Y}^{\prime})|\leq
O(L/n)$ . We will now show that $\left\lVert p-p^{\prime}\right\rVert_{1}$
satisfies the desired inequality. By assumption, we have that

$\left|f\left(\widetilde{\mathbb{E}}_{\zeta}[w]\right)-f\left(\widetilde{\mathbb{E}}_{\zeta^{\prime}}[w]\right)\right|\leq
O(L/n).$

In other words,

$\left|\textsf{Ent}\left(\widetilde{\mathbb{E}}_{\zeta}[w]\right)-\textsf{Ent}\left(\widetilde{\mathbb{E}}_{\zeta^{\prime}}[w]\right)\right|\leq
O(L\log(n)/n).$

By the constraint $w_{i}^{2}=w_{i}/n$ in $\mathcal{A}$, it is straightforward
to derive that
$\left\lVert\widetilde{\mathbb{E}}_{\zeta}[w]\right\rVert_{\infty},\left\lVert\widetilde{\mathbb{E}}_{\zeta^{\prime}}[w]\right\rVert_{\infty}\leq
2/n$. Thus,
$\widetilde{\mathbb{E}}_{\zeta}[w],\widetilde{\mathbb{E}}_{\zeta^{\prime}}[w]$
satisfy the hypotheses of Lemma 6.8 and we conclude that

$\left\lVert\widetilde{\mathbb{E}}_{\zeta}[w]-\widetilde{\mathbb{E}}_{\zeta^{\prime}}[w]\right\rVert_{1}\leq
O(L/n).$

Applying Lemma 3.1 to the vectors
$\widetilde{\mathbb{E}}_{\zeta}[w],\widetilde{\mathbb{E}}_{\zeta^{\prime}}[w]$
completes the proof. ∎

###  6.2 Private Robust Mean Estimation

The building block of our mean estimator is a polynomial constraint system
$\mathcal{A}^{\textsf{mean}}_{C,\eta,n}(\\{Y_{1},\ldots,Y_{n}\\})$. Our
algorithm will solve its SoS relaxation. Algorithm 8 encodes the process of
non-privately finding $X^{\prime}$, a set of samples that intersects with the
corrupted sample in $(1-\eta)n$ points.

$\mathcal{A}^{\textsf{mean}}_{C,\eta,n}(\\{Y_{1},\ldots,Y_{n}\\})$: Constraint
system for mean estimation 1. $w_{i}^{2}=w_{i}/n$ for all $i\in[n]$. 2.
$\sum_{i\in[n]}w_{i}\geq 1-\eta$. 3.
$w_{i}\left({X}^{\prime}_{i}-Y_{i}\right)=0$ for all $i\in[n]$. 4.
$\widetilde{\mu}=\frac{1}{n}\sum_{i\in[n]}{X}^{\prime}_{i}$. 5.
$\frac{1}{n}\sum_{i\in[n]}\left\langle{X}^{\prime}_{i}-\widetilde{\mu},v\right\rangle^{2}\leq
C\left\lVert v\right\rVert_{2}^{2}$. Figure 8: Robust mean estimation convex
program $\mathcal{A}^{\textsf{mean}}_{C,\eta,n}(\\{Y_{1},\ldots,Y_{n}\\})$.

Following the framework of [KMV22], in Algorithm 9, we provide an end-to-end
$(\varepsilon,\delta)$-DP algorithm for robustly estimating the mean. The
three major steps (stable outlier rate selection, witness checking, and noise
injection) each satisfy $(\varepsilon/3,\delta/3)$-DP so that the result
follows by routine composition.

1. Input: Samples $\mathcal{Y}=\\{Y_{1},\ldots,Y_{n}\\}\subset\mathbb{R}^{d}$, outlier rate $\eta\in[0,1/2)$, privacy parameters $\varepsilon,\delta>0$, subgaussian parameter $C>0$, pseudo-distribution degree parameter $t$. 2. Stable outlier rate selection: Invoke the $(\varepsilon/3,\delta/3)$-DP mechanism $\mathcal{M}_{1}$ from Lemma 6.9 on input $(\mathcal{Y},\eta,C,\beta/3)$ to sample an outlier rate $\eta^{\prime}$. If $\eta^{\prime}=\bot$, then halt. 3. Witness checking: Compute a degree-$2t$ pseudo-distribution $\zeta$ satisfying $\mathcal{A}^{\textsf{mean}}_{C,\eta^{\prime},n}(\mathcal{Y})$ that minimizes $\textsf{Ent}\left(\widetilde{\mathbb{E}}_{\zeta}[w]\right)$. Invoke the $(\varepsilon/3,\delta/3)$-DP mechanism $\mathcal{M}_{2}$ from Lemma A.6 on input $(\mathcal{Y},\eta,C,\zeta,\beta/3)$ to sample $C^{\prime}$. If $C^{\prime}=\bot$, then halt. Otherwise, let $p=\widetilde{\mathbb{E}}_{\zeta}[w]/\left\lVert\widetilde{\mathbb{E}}_{\zeta}[w]\right\rVert_{1}$ and $\widetilde{\mu}=\sum_{i=1}^{n}p_{i}Y_{i}$. 4. Noise injection: Apply the Gaussian mechanism from Theorem 3.6 with privacy parameters $\varepsilon/3,\delta/3$ and noise level $\sigma=\widetilde{O}\left(C^{\prime}\sqrt{\log(1/\delta)}/\varepsilon\sqrt{n}\right)$ on $\widetilde{\mu}$ to obtain a vector $\widehat{\mu}\in\mathbb{R}^{d}$. 5. Output: Mean estimate $\widehat{\mu}$. Figure 9: Robust mean estimation algorithm

The privacy analysis of the algorithm uses the following lemma:

######  Lemma 6.10 (Fact 3.23 of [KMV22]).

Let $Y$ be a set of $n$ points in $\mathbb{R}^{d}$. Let
$p,p^{\prime}\in[0,1]^{n}$ be probability vectors such that $\left\lVert
p-p^{\prime}\right\rVert_{1}=\tau$. Suppose that $p$ and $p^{\prime}$ are
distributions on $Y$, where $p$ is $2k$-certifiably $C_{1}$-subgaussian and
$p^{\prime}$ is $2k$-certifiably $C_{2}$-subgaussian. Let
$\mu_{p}=\sum_{i}p_{i}y_{i}$ and
$\Sigma_{p}=\sum_{i}p_{i}(y_{i}-\mu_{p})(y_{i}-\mu_{p})^{\top}$ for every
$t\in\mathbb{N}$ be the mean and covariance distribution defined $p$. Define
$\mu_{p^{\prime}},\Sigma_{p^{\prime}},M^{(t)}_{p^{\prime}}$ similarly for the
distribution corresponding to $p^{\prime}$. Then, for every $\tau\leq\eta_{0}$
for some absolute constant $\eta_{0}$, for every $u\in\mathbb{R}^{d}$,
$C^{\prime}=C_{1}+C_{2}$ and $t\leq k$:

$\left\langle\mu_{p}-\mu_{p^{\prime}},u\right\rangle\leq\tau^{1-1/2k}\cdot
O\left(\sqrt{Ck}\sqrt{u^{\top}\Sigma_{p}u}\right).$

######  Theorem 6.11 (Privacy).

Given $\varepsilon\in(0,1),\delta>0$, any subgaussian parameter $C$, SoS
degree $t$ and outlier rate $\eta$, Algorithm 9 is $(\varepsilon,\delta)$-DP
provided that $n\geq
O\left(\frac{\log^{3}(n/\delta\beta)}{\varepsilon^{3}}\right)$.

###### Proof.

Observe that Algorithm 9 is an adaptive composition of $3$ steps, the first
two of which may halt early. By Lemma 3.5, it suffices to show that each of
the 3 steps is $(\varepsilon/3,\delta/3)$-DP to conclude that their
composition is $(\varepsilon,\delta)$-DP. We now verify the privacy of each of
these steps:

  * •

Stable outlier rate selection: In this step, we invoke the mechanism
$\mathcal{M}_{1}$ of Lemma 6.9, from which we may conclude that this step is
$(\varepsilon/3,\delta/3)$-DP.

  * •

Witness checking: We may now assume that the algorithm did not halt in the
previous step, so that the convex program
$\mathcal{A}^{\textsf{mean}}_{C,\eta^{\prime},n}$ is feasible. By Lemma A.6
and assuumption on $n$, we may immediately conclude this step is
$(\varepsilon/3,\delta/3)$-DP.

  * •

Noise injection: Let $\mathcal{Y},\mathcal{Y}^{\prime}$ be neighboring
datasets and assume that the algorithm did not halt in either of the previous
two steps for either of $\mathcal{Y},\mathcal{Y}^{\prime}$. To invoke the
guarantee of the Gaussian mechanism (Theorem 3.6), we now verify that
$\left\lVert\widetilde{\mu}(\mathcal{Y})-\widetilde{\mu}(\mathcal{Y}^{\prime})\right\rVert_{2}\leq\Delta$
for some $\Delta=\widetilde{O}(1/\sqrt{n})$. Since the algorithm did not halt
in the first step, Lemma 6.9 implies that $\left\lVert
p(\mathcal{Y})-p(\mathcal{Y}^{\prime})\right\rVert_{1}=O(L/n)$, where
$L=O(\frac{1}{\varepsilon}\log(\frac{n}{\beta\delta}))$. Since the algorithm
did not halt in the second step, $p(\mathcal{Y})$ and
$p(\mathcal{Y}^{\prime})$ induce $C^{\prime}$-subgaussian distributions on
$\mathcal{Y}$ and $\mathcal{Y}^{\prime}$, respectively. Hence, by Lemma 6.10,
it holds that
$\left\lVert\widetilde{\mu}(\mathcal{Y})-\widetilde{\mu}(\mathcal{Y}^{\prime})\right\rVert_{2}=O(C^{\prime}\sqrt{L/n})$,
which completes the proof.

This completes our privacy analysis. ∎

We now proceed to the utility analysis. It relies upon the following bound:

######  Lemma 6.12 (Special case of Theorem 1 of [KMZ22]).

Let $\mathcal{Y}$ be an $\eta$-corrupted sample of size $n$ from
$\mathcal{N}(\mu,I)$, $C$ be a large enough absolute constant and suppose
$n\geq\widetilde{O}(d\log^{5}(1/\beta)/\eta^{2})$. Then with probability
$1-\beta$, the degree-$12$ SoS relaxation of
$\mathcal{A}_{C,\eta,n}(\mathcal{Y})$ is feasible and any satisfying pseudo-
distribution $\zeta$ satisfies:

$\left\lVert\sum_{i=1}^{n}\widetilde{\mathbb{E}}_{\zeta}[w_{i}]Y_{i}-\mu\right\rVert_{2}\leq\widetilde{O}(\eta).$

With this result in hand, we are ready to show:

######  Theorem 6.13 (Utility).

Let $\mathcal{Y}=\\{Y_{1},\ldots,Y_{n}\\}$ be an $\eta$-corrupted sample from
$\mathcal{N}(\mu,I_{d})$ and assume that

$n\geq\widetilde{O}\left(\max\left(\frac{d\log^{5}(1/\beta)}{\eta^{2}},\frac{\log^{3}(n/\delta\beta)}{\varepsilon^{3}}\right)\right)$

Then with probability $1-\beta$, the output of Algorithm 9 on input
$\mathcal{Y}$ and parameters $\eta\in(0,1/2)$, $\varepsilon,\delta>0$, $t=12$,
$C=O(1)$ satisfies:

$\left\lVert\mu-\widehat{\mu}\right\rVert_{2}\leq
O(\eta\log(1/\eta))+O\left(\frac{1}{\varepsilon^{3/2}}\sqrt{\frac{(d+\log(1/\beta))\log(1/\delta)\log(n/\beta\delta)}{n}}\right).$

In particular, if
$n\geq\widetilde{O}(d\log^{3}(n/\beta\delta)/\eta^{2}\varepsilon^{3})$ as
well, we have $\|\mu-\widehat{\mu}\|\leq O(\eta\left(\log(1/\eta)\right)$

###### Proof.

By the guarantees of Lemma 6.9 and Lemma A.6, the algorithm fails to reach the
noise injection step with probability at most $2\beta/3$. On the event that
Algorithm 9 does not output halt in the first two steps, we have that
$\widehat{\mu}=\widetilde{\mu}+\sigma Z$, where
$\sigma=\sqrt{2\ln(1.25/\delta)}\Delta/\varepsilon$,
$\Delta=\widetilde{O}(C^{\prime}\sqrt{L/n})=O(\sqrt{L/n})$ (by assumption on
$C$ and the utility guarantee of Lemma A.6),
$L=O(\frac{1}{\varepsilon}\log(\frac{n}{\beta\delta}))$, and
$Z\sim\mathcal{N}(0,I_{d})$, as in the proof of Theorem 6.11. By the triangle
inequality, we have

$\left\lVert\mu-\widehat{\mu}\right\rVert_{2}\leq\left\lVert\mu-\widetilde{\mu}\right\rVert_{2}+\sigma\left\lVert
Z\right\rVert_{2}.$

By Lemma 3.15, with probability $1-\frac{\beta}{6}$, it holds that
$\left\lVert Z\right\rVert_{2}\leq\sqrt{d+O(\log(1/\beta))}$. By Theorem 6.12
and our assumption on $n$, with probability $1-\frac{\beta}{6}$, it holds that
$\left\lVert\mu-\widehat{\mu}\right\rVert_{2}\leq O(\eta\log(1/\eta))$. ∎

###  6.3 Private Robust Covariance Estimation

We now give an algorithm for private and robust Gaussian covariance
estimation. The algorithm builds on the constraint system
$\mathcal{A}^{\textsf{cov}}_{C,\eta,n}(\\{Y_{1},\ldots,Y_{n}\\})$ and its SoS
relaxation. For any $d$-by-$d$ matrix intermediate $Q$, define
$\overline{{x}_{i}^{\prime}}^{\top}Q\overline{x_{i}^{\prime}}=x^{\prime\top}Qx^{\prime}-\frac{1}{n}\sum_{i=1}^{n}x_{i}^{\prime\top}Qx_{i}^{\prime}$.

1. $w_{i}^{2}=w_{i}/n$ for all $i\in[n]$. 2. $\sum_{i\in[n]}w_{i}\geq 1-\eta$. 3. $w_{i}({X}^{\prime}_{i}-Y_{i})=0$ for all $i\in[n]$. 4. $\widetilde{\mu}=\frac{1}{n}\sum_{i\in[n]}{X}^{\prime}_{i}$.  5. $\Pi^{2}=\frac{1}{n}\sum_{i=1}^{n}\left(X^{\prime}_{i}-\widetilde{\mu}\right)\left(X^{\prime}_{i}-\widetilde{\mu}\right)^{\top}$, 6. $\frac{1}{n}\sum_{i=1}^{n}X_{i}^{\prime\top}QX_{i}^{\prime}\leq C\|\Pi Q\Pi\|_{F}^{2}$ Figure 10: Robust covariance estimation convex program $\mathcal{A}^{\textsf{cov}}_{C,\eta,n}(\\{Y_{1},\ldots,Y_{n}\\})$.

Algorithm 10 encodes non-privately finding $X^{\prime}$, a set of samples that
intersects with the corrupted sample in $(1-\eta)n$ points and has 4th moments
upper bounded in terms of the squared second moments in all directions. We
cite the following property of this constraint system.

######  Lemma 6.14 (analog of Lemma 5.5 of [KMV22]).

Let $\eta,\varepsilon,\delta>0$ and $L\in\mathbb{N}$ be the input parameters
to Algorithm 11 such that $0.25\eta n\geq
L=\Omega\left(\frac{1}{\varepsilon}\cdot\log\left(\frac{n}{\beta\delta}\right)\right)$.
Let $Y,Y^{\prime}$ be adjacent datasets. Suppose that the algorithm does not
halt in any of the steps and samples the constant $C^{\prime}$ in Step 3 and
chooses $\eta^{\prime}$ in Step 2 on input $Y$ and $Y^{\prime}$. Then, for
$\theta={L/n}$, we have:

$\left\lVert\Sigma_{p}^{-1/2}\Sigma_{p^{\prime}}\Sigma_{p}^{-1/2}-I\right\rVert_{F}\leq
O(C^{\prime})\theta^{1/2}.$

######  Lemma 6.15 (Theorem 1.3 of [KMV22]).

Let $\varepsilon\in(0,1),\delta>0$ and $\eta$ be a sufficiently small
constant. Let $\mathcal{Y}$ be an $\eta$-corrupted sample of size $n$ from
$\mathcal{N}(0,\Sigma)$, $C$ be larger than some absolute constant and suppose
$n\geq\widetilde{O}(d^{2}\log^{5}(1/\beta)/\eta^{2})$. Then with probability
$1-\beta$, the solution
$\widetilde{\Sigma}=\sum_{i=1}^{n}p_{i}Y_{i}Y_{i}^{\top}$ in Step 3 of
Algorithm 11 satisfies

$\left\lVert\Sigma^{-1/2}\widetilde{\Sigma}\Sigma^{-1/2}-I\right\rVert_{F}\leq\widetilde{O}\left(C\eta\right).$

###### Proof.

This result follows immediately from combining Theorem 1.3 of [KMV22],
Corollary 1.3 of [KMZ22] and the utility guarantee of Lemma A.6. ∎

1. Input: Samples $\mathcal{Y}=\\{Y_{1},\ldots,Y_{n}\\}\subset\mathbb{R}^{d}$, outlier rate $\eta\in[0,1/2)$, privacy parameters $\varepsilon,\delta>0$, certifiable hypercontractivity parameter $C>0$, pseudo-distribution degree parameter $t$, and Gaussian sampling parameter $k$. 2. Stable outlier rate selection: Invoke the $(\varepsilon/3,\delta/3)$-DP mechanism $\mathcal{M}_{1}$ from Lemma 6.9 on input $(\mathcal{Y}_{2},\eta,C,\beta/3)$ to sample an outlier rate $\eta^{\prime}$. If $\eta^{\prime}=\bot$, then halt. 3. Witness checking: Compute a degree-$2t$ pseudo-distribution $\zeta$ satisfying $\mathcal{A}^{\textsf{cov}}_{C,\eta^{\prime},n}(\mathcal{Y}_{2})$ that minimizes $\textsf{Ent}\left(\widetilde{\mathbb{E}}_{\zeta}[w]\right)$. Invoke the $\left(\varepsilon/3,\delta/3\right)$-DP mechanism $\mathcal{M}_{2}$ from Lemma A.6 on input $(\mathcal{Y}_{2},\eta,C,\zeta,\beta/3)$ to sample $C^{\prime}$. If $C^{\prime}=\bot$, then halt. Otherwise, let $p=\widetilde{\mathbb{E}}_{\zeta}[w]/\left\lVert\widetilde{\mathbb{E}}_{\zeta}[w]\right\rVert_{1}$ and $\widetilde{\Sigma}=\sum_{i=1}^{n}p_{i}Y_{i}Y_{i}^{T}$. 4. Noise injection: Invoke the $(\varepsilon/3,\delta/3)$-DP mechanism in Algorithm 6 on input $\widetilde{\Sigma}$ to obtain a matrix $\widehat{\Sigma}\in\mathbb{R}^{d\times d}$ with parameter $k$. 5. Output: Covariance estimate $\widehat{\Sigma}$. Figure 11: Covariance estimation algorithm

Following the framework of [KMV22], in Algorithm 11, we provide an end-to-end
$(\varepsilon,\delta)$-DP algorithm for robustly estimating the covariance
matrix. The three major steps (stable outlier rate selection, witness
checking, and noise injection) each satisfy $(\varepsilon/3,\delta/3)$-DP so
that the privacy guarantee follows by routine composition.

######  Theorem 6.16 (Privacy).

Given $\varepsilon,\delta\in(0,1]$, any SoS degree $t$ and outlier rate
$\eta$, Algorithm 11 with parameter $k$ is $(\varepsilon,\delta)$-DP provided
that

$n\geq
O\left(\frac{(C^{\prime}k\log(1/\delta)+\log^{2}(1/\delta))\cdot\log(n/\beta\delta)}{\varepsilon^{2.5}}+\frac{\log^{3}(n/\delta\beta)}{\varepsilon^{3}}\right)$

###### Proof.

Observe that Algorithm 11 is an adaptive composition of 3 steps, each of which
may halt early. By Lemma 3.5, it suffices to show that each of the 3 steps is
$(\varepsilon/3,\delta/3)$-DP to conclude that their composition is
$(\varepsilon,\delta)$-DP. The parts of Algorithm 11 that involve Stable
outlier rate selection and Witness checking can be shown to satisfy the
desired privacy guarantees in an identical way to the proof of privacy of
Algorithm 9 for mean estimation in Theorem 6.11. We now verify the privacy of
the remaining step:

  * •

Noise injection: Let $\mathcal{Y},\mathcal{Y}^{\prime}$ be neighboring
datasets and assume that the algorithm did not halt in any of the previous
steps for either of $\mathcal{Y},\mathcal{Y}^{\prime}$. To invoke guarantee of
the Gaussian sampling mechanism (Theorem 5.1), it suffices to verify that
$\left\lVert\widetilde{\Sigma}^{1/2}(\mathcal{Y})\widetilde{\Sigma}(\mathcal{Y}^{\prime})^{-1}\widetilde{\Sigma}(\mathcal{Y})^{1/2}-I\right\rVert_{F}\leq\Delta$
for $\Delta$ sufficiently small.

Since the algorithm did not halt after Stable outlier rate selection, Lemma
6.9 implies that $\left\lVert
p(\mathcal{Y})-p(\mathcal{Y}^{\prime})\right\rVert_{1}=O(L/n)$, where
$L=O(\frac{1}{\varepsilon}\log(\frac{n}{\beta\delta}))$. Since the algorithm
did not halt Witness checking, $p(\mathcal{Y})$ and $p(\mathcal{Y}^{\prime})$
induce $2t$-certifiably $C^{\prime}$-hypercontractive distributions on
$\mathcal{Y}$ and $\mathcal{Y}^{\prime}$, respectively. Hence, by Lemma 6.14,
it holds that

$\left\lVert\widetilde{\Sigma}^{1/2}(\mathcal{Y})\widetilde{\Sigma}(\mathcal{Y}^{\prime})^{-1}\widetilde{\Sigma}(\mathcal{Y})^{1/2}-I\right\rVert_{F}\leq\Delta=O\left(C^{\prime}\sqrt{L/n}\right).$

This value of $\Delta$ satisfies the conditions of Theorem 5.1 by our
assumption on $n$.

∎

######  Theorem 6.17 (Utility).

Let $\mathcal{Y}=\\{Y_{1},\ldots,Y_{n}\\}$ be an $\eta$-corrupted sample from