[bib]nametitledelim

# Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models

Jamil Arbas McMaster University<EMAIL_ADDRESS> Hassan Ashtiani McMaster
University<EMAIL_ADDRESS>Hassan Ashtiani is also a faculty affiliate
at Vector institue. Christopher Liaw Google<EMAIL_ADDRESS>
We study the problem of privately estimating the parameters of $d$-dimensional
Gaussian Mixture Models (GMMs) with $k$ components. For this, we develop a
technique to reduce the problem to its non-private counterpart. This allows us
to privatize existing non-private algorithms in a blackbox manner, while
incurring only a small overhead in the sample complexity and running time. As
the main application of our framework, we develop an
$(\varepsilon,\delta)$-differentially private algorithm to learn GMMs using
the non-private algorithm of [MV10] as a blackbox. Consequently, this gives
the first sample complexity upper bound and first polynomial time algorithm
for privately learning GMMs without any boundedness assumptions on the
parameters. As part of our analysis, we prove a tight (up to a constant
factor) lower bound on the total variation distance of high-dimensional
Gaussians which can be of independent interest.

##  1 Introduction

The problem of learning the parameters of a Gaussian Mixture Model (GMM) is a
fundamental problem in statistics, dating back to the early work of [Pea94] A
GMM with $k$ components in $d$ dimensions can be represented as
$(w_{i},\mu_{i},\Sigma_{i})_{i=1}^{k}$, where $w_{i}$ is a mixing weight
($w_{i}\geq 0$, and $\sum_{i\in[k]}w_{i}=1$), $\mu_{i}\in\mathbb{R}^{d}$ is a
mean, and $\Sigma_{i}\in\mathbb{R}^{d\times d}$ is a covariance matrix (of the
$i$-th Gaussian component). To draw a random instance from this GMM, one first
samples an index $i\in[k]$ (with probability $w_{i}$) and then returns a
random sample from the Gaussian distribution
$\mathcal{N}(\mu_{i},\Sigma_{i})$. In this work we consider the problem of
parameter estimation in the probably approximately correct (PAC) model, where
the goal is to “approximately recover”111See Definition 1.4 for the precise
notion of distance. the parameters of an unknown GMM given only independent
samples from it.

The sample complexity and computational complexity of learning the parameters
of GMMs has been studied extensively. A breakthrough in this line of work was
the development of polynomial-time methods (with respect to $d$) for learning
GMMs with minimal separation requirements [MV10, BS10]. The running time and
sample complexity of these methods is exponential $k$, which is generally
necessary for parameter estimation [MV10].

The above approaches, however, may not maintain privacy of the individuals
whose data has been used for the estimation. To address this issue, we adopt
the rigorous and widely accepted notion of differential privacy (DP) [DMNS06].
At a high-level, DP ensures that the contribution of each individual has only
a small (indistinguishable) effect on the output of the estimator. The
classical notion of $\varepsilon$-DP (pure DP) is, however, quite restrictive.
For instance, even estimating the mean of an unbounded univariate Gaussian
random variable in this model is impossible. Therefore, in line with recent
work on private estimation in unbounded domains, we consider the
$(\varepsilon,\delta)$-DP (i.e. approximate differential privacy [DKMMN06])
model.

For the simpler case of multivariate Gaussians (without any boundedness
assumptions on the parameters), it has been shown that learning with a finite
number of samples is possible in the $(\varepsilon,\delta)$-DP model [AAK21].
More recently, computationally efficient estimators have been devised for the
same task [AL22, KMSSU22, KMV22]. This begs answering the corresponding
question for GMMs.

> Is there an $(\varepsilon,\delta)$-DP estimator with a bounded sample
> complexity for learning unbounded GMMs? Is there a polynomial time estimator
> (in terms of $d$) for the same task?

Note that if additional boundedness222They assume there are known quantities
$R,\sigma_{max},\sigma_{min}$ such that $\forall i\in[k],\|\mu_{i}\|_{2}\leq
R\leavevmode\nobreak\ \leavevmode\nobreak\ \textrm{and}\leavevmode\nobreak\
\leavevmode\nobreak\ \sigma_{min}^{2}\leq||\Sigma_{i}||\leq\sigma_{max}^{2}$.
and strong separation333They assume $\forall i\neq
j,||\mu_{i}-\mu_{j}||_{2}\geq\widetilde{\Omega}\left(\sqrt{k}+\sqrt{\frac{1}{w_{i}}+\frac{1}{w_{j}}}\right)\cdot\max\left\\{||\Sigma_{i}^{1/2}||,||\Sigma_{j}^{1/2}||\right\\}$.
assumptions are made about the GMM, then the work of [KSSU19] offers a
positive answer to the above question in the $\varepsilon$-DP model. It has
also been shown that the separation condition between the components can be
significantly weakened [CKMST21, CCdEIST23]. Our aim is, however, learning
_unbounded_ GMMs with _minimal_ separation assumptions.

To approach this problem, it is natural to ask if there is a general reduction
from the private learning of GMMs to its non-private counterpart. If so, this
would enable us to easily reuse existing results for non-private learning of
GMMs.

> Is there a reduction from private to non-private learning of GMMs that
> incurs only a polynomial time and polynomial sample overhead?

The main result of this paper is the existence of such a reduction; see
Theorem 6.2 for a rigorous version.

######  Theorem 1.1 (Private to Non-private Reduction for GMMs, Informal).

There is a reduction from learning the parameters of a GMM in the
$(\varepsilon,\delta)$-DP model to its non-private counterpart. Moreover, this
reduction adds only polynomial time and sample overhead in terms of $d$ and
$k$.

This reduction, along with the non-private learner of [MV10] gives the first
finite sample complexity upper bound for learning the parameters of unbounded
GMMs in the $(\varepsilon,\delta)$-DP model. Moreover, the resulting estimator
essentially inherits all the properties of the non-private estimator of
[MV10]; it runs in time that is polynomial in $d$ (for fixed $k$) and shares
the advantage of requiring provably minimal separability assumptions on the
components of the GMM. We refer the reader to the related work section for a
comparison with [CKMST21] and [CCdEIST23].

###  1.1 Related Work

#### Private Learning of a Single Gaussian.

[KV17] established polynomial time and sample efficient methods for learning
the mean and variance of a univariate Gaussian in both the pure and
approximate-DP settings. Namely, in the $(\varepsilon,\delta)$-DP setting,
they can recover the mean and variance of the Gaussian without any boundedness
assumption on the parameters. This result can be generalized to the
multivariate setting [KLSU19, BDKU20], where one finds Gaussians that
approximate the underlying Gaussian in terms of total variation distance.
However, the sample complexity of these methods depends on the condition
number of the covariance matrix, and requires a priori bounds on the range of
the parameters. The first finite sample complexity bound for privately
learning unbounded Gaussians appeared in [AAK21], nearly matching the sample
complexity lower bound of [KMS22]. The work of [AAK21] relies on a private
version of the minimum distance estimator [Yat85] and is based on ideas from
the private hypothesis selection method [BSKW19]. However, this method is not
computationally efficient. Recently, several papers offered
$(\varepsilon,\delta)$-DP and computationally efficient algorithms for
learning unbounded Gaussians [AL22, KMSSU22, KMV22], where the work of [AL22]
achieved a near-optimal sample complexity for this task. Part of the approach
of [AL22] is a sub-sample-and-aggregate scheme which we modify and use in this
paper. FriendlyCore [TCKMS22] is an alternative sample-and-aggregate framework
that can be used for privately learning unbounded Gaussians. It is noteworthy
that the approaches of [AL22, KMV22] work in the robust setting as well albeit
with sub-optimal sample complexities. The recent work of [AKTVZ22] offers a
robust and private learner with near-optimal sample requirements in terms of
dimension. Finally, [HKMN23] ticks all the boxes by offering a sample near-
optimal, robust, and efficient learner for unbounded Gaussians.

Another related result is a sample-efficient and computationally efficient
method for learning bounded and high-dimensional Gaussians in the
$\varepsilon$-DP model [HKM22]. There is also work on the problem of private
mean estimation with respect to Mahalanobis distance [BGSUZ21, DHK23]. Finding
private and robust estimators [LKKO21] and also the interplay between
robustness and privacy [DL09, GH22, LKO22, HKMN23, AUZ23] are subjects of a
few recent papers.

#### Parameter Learning for GMMs with PAC Guarantees.

Given i.i.d. samples from a GMM, can we approximately recover its parameters?
There has been an extensive amount of research in developing sample efficient
and computationally efficient methods for learning the parameters of a GMM
[Das99, SK01, VW04, AM05, BV08, KMV10, FSO06, BS09, HP14, HK13, ABGRV14, RV17,
KSS18, HL18, LL22]. Remarkably, [MV10, BS10] presented the first polynomial
time algorithms for learning general GMMs with unbounded components and under
minimal separation assumptions. Here, the focus is on designing polynomial
methods _with respect to dimension_ , since having an exponential dependence
on the number of components is inevitable [MV10] (unless the components are
well-separated). These results haven been recently extended to the robust
setting [BDJKKV22, LM21, LM22].

In the private setting, the early work of [NRS07] offered an
$(\varepsilon,\delta)$-DP estimator for the means of a GMM, in the special
case where the components share the same mixing weight and the same (known)
covariance matrix. Note that this result also inherits the strong separation
assumption (of $\Omega(k^{1/4})$) between the Gaussian components from [VW04].
The recent (and independent) work of [CCdEIST23] shows that this separation
can be significantly relaxed. These results are, however, for learning
(unbounded) spherical Gaussian mixtures and unlike our work, they do not learn
the covariance matrices.

Perhaps more related to our paper is the work of [KSSU19], which offers an
$(\varepsilon,\delta)$-DP parameter learning method for GMMs with unknown
mixing weights, means, and covariance matrices. In fact, their approach is a
privatized version of [AM05]. However, their method only works when the
parameters of the Gaussian components are bounded and the means are strongly
separated (i.e., $\Omega(\sqrt{k})$-separated). In a related work, [BKS22]
show how can one use public data to improve this approach.

Finally, the more recent work of [CKMST21] improves over [KSSU19] by offering
a better sample complexity and requiring weaker separation between the
clusters. They show we can learn GMMs privately if we are given _(i)_ a
private learner for Gaussians and _(ii)_ a non-private clustering method
(i.e., an algorithm that can label the data points accurately based on their
clusters). Given the generality of their reduction, one can plug a non-private
clustering method that requires weaker separation between the components. On
top of the separation requirements for the clustering method, their result
also requires an $\Omega(\log{n})$ separation between the means, where $n$ is
the number of samples. Given, that $n$ is polynomial in $1/\varepsilon,k$ and
$d$, their approach requires mild separation (i.e., logarithmic in these
parameters).

Unlike [KSSU19, CKMST21], our approach does not require a priory bounds on the
range of the Gaussian means or on the condition numbers of the covariance
matrices. It may be possible to extend the result of [CKMST21] to the
unbounded setting, e.g., using the private Gaussian estimator of [AL22]; yet,
there are some subtle challenges for clustering when the condition number of
Gaussian components are high. Another difference lies in the separation
requirements. While [CKMST21] relaxes the separation requirements of [KSSU19],
it still requires a (mild) separation of $\log(kd/\varepsilon)$ between the
components. Moreover, additional separation requirements must be met for the
non-private clustering method to work. While for spherical Gaussians this
requirement is rather weak (i.e., $\sqrt{\log k}$ separation [LL22], we are
not aware of clustering methods that work for non-spherical Gaussians and
require weak separation (e.g., independent of the condition number of the
Gaussian components). In contrast, our approach uses non-private parameter
estimation (rather than clustering) and requires only “minimal separation”
that is independent of $\epsilon,k,d$ (see Definition 6.4).

#### Density Estimation for GMMs.

In the density estimation problem for GMMs, the goal is to recover a
distribution that is close (often in total variation distance) to the
underlying GMM. From the statistical point of view, the sample complexity of
this problem has been settled up to logarithmic factors [DL01, ABM18,
ABHLMP18, ABHLMP20]. Unlike the parameter learning setting, the sample
complexity is actually polynomial both in terms of the dimension and the
number of components. There are also computationally efficient algorithms for
learning one-dimensional GMMs [CDSS14, ADLS17, LLM22, WX18, LS17]. Designing a
polynomial time (with respect to dimension and number of components) algorithm
for learning GMMs with respect to total variation distance remains an
important open problem. Solving this problem is challenging as it requires
overcoming known statistical query lower bounds for the problem [DKS17].

In the private setting, one can use the private hypothesis selection framework
[BSKW19] or the private minimum distance estimator [AAK21] to learn classes
that admit a finite cover. Therefore, GMMs with bounded parameters admit an
$\varepsilon$-DP finite sample complexity guarantee [BSKW19]. A polynomial
sample complexity upper bound is known for learning axis-aligned GMMs in the
$(\varepsilon,\delta)$-DP model _without any boundedness assumptions on the
parameters_ [AAL21]. Extending this results to general GMMs remains an open
problem. Furthermore, designing private and computationally efficient
estimators for GMMs remains open even in the one dimensional setting. Another
relevant result is a lower bound on the sample complexity of learning GMMs
with known covariance matrices [ASZ21].

###  1.2 Preliminaries

We use $\|v\|_{2}$ to denote the Euclidean norm of a vector
$v\in\mathbb{R}^{d}$ and $\|A\|_{F}$ (resp. $\|A\|$) to denote the Frobenius
(resp. spectral) norm of a matrix $A\in\mathbb{R}^{d\times d}$.

In this paper, we write $\mathcal{S}^{d}$ to denote the positive-definite cone
in $\mathbb{R}^{d\times d}$. Let
$\mathcal{G}(d)=\\{\mathcal{N}(\mu,\Sigma)\,:\,\mu\in\mathbb{R}^{d},\Sigma\in\mathcal{S}^{d}\\}$
be the family of $d$-dimensional Gaussians. We can now define the class
$\mathcal{G}(d,k)$ of mixtures of Gaussians as follows.

######  Definition 1.2 (Gaussian Mixtures).

The class of mixtures of $k$ Guassians in $\mathbb{R}^{d}$ is defined by
$\mathcal{G}(d,k)\coloneqq\left\\{\sum\limits_{i=1}^{k}{w_{i}G_{i}}\,:\,G_{i}\in\mathcal{G}(d),w_{i}\geq
0,\sum_{i=1}^{k}w_{i}=1\right\\}$.

We represent the Gaussian Mixture Model (GMM) by a set of $k$ tuples
$\left(w_{i},\mu_{i},\Sigma_{i}\right)_{i=1}^{k}$, where each tuple represents
the mean, covariance matrix, and mixing weight of one of its components. Note
that the order of the components is important in our notation, since the order
of the output may have an impact on the privacy.

In the following definition and the remainder of the paper, we may abuse
terminology and refer to a distribution via its probability density function
(p.d.f.).

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

Given two absolutely continuous probability measures $f(x),g(x)$ on
$\mathbb{R}^{d}$, the total variation (TV) distance between $f$ and $g$ is
defined as
$d_{\mathrm{TV}}\left({f(x)},{g(x)}\right)=\frac{1}{2}\int_{\mathbb{R}^{d}}|f(x)-g(x)|\,\mathrm{d}x$.

A standard way to define the distance between two GMMs is as follows ([MV10],
Definition 2).

######  Definition 1.4 (The Distance between Two GMMs).

The $\operatorname{dist}_{\textsc{Gmm}}$ distance between two GMMs is defined
by

$\operatorname{dist}_{\textsc{Gmm}}\left(\left(w_{i},\mu_{i},\Sigma_{i}\right)_{i=1}^{k},\left(w^{\prime}_{i},\mu^{\prime}_{i},\Sigma^{\prime}_{i}\right)_{i=1}^{k}\right)\\\
=\min_{\pi}\max_{i\in[k]}\max\Big{\\{}|w_{i}-w_{\pi(i)}^{{}^{\prime}}|,\\\
d_{\mathrm{TV}}\left({\mathcal{N}(\mu_{i},\Sigma_{i})},{\mathcal{N}(\mu^{{}^{\prime}}_{\pi(i)},\Sigma^{{}^{\prime}}_{\pi(i)})}\right)\Big{\\}}$

where $\pi$ is chosen from the set of all permutations over $[k]$.

If $X$ (resp. $Y$) is a random variable distributed according to $f$ (resp.
$g$), we write
$d_{\mathrm{TV}}\left({X},{Y}\right)=d_{\mathrm{TV}}\left({f},{g}\right)$. We
drop the reference to the p.d.f. of the random variable when it is clear or
implicit from context.

###  1.3 Differential Privacy Basics

At a high-level, an algorithm is differentially private if, given two datasets
that differ only in a single element, the output distribution of the algorithm
are nearly the same444For sake of simplicity, we consider data sets to be
ordered and therefore the neighboring data sets are defined based on their
Hamming distances. However, one can easily translate guarantees proven for the
ordered setting to the unordered one; see Proposition D.6 in [BGSUZ21]..

######  Definition 1.5 (Neighbouring Datasets).

Let $\mathcal{X},\mathcal{Y}$ denote sets and $n\in\mathbb{N}$. Two datasets
$D=(X_{1},\ldots,X_{n}),D^{\prime}=(X_{1},\ldots,X_{n})\in\mathcal{X}^{n}$ are
said to be _neighbouring_ if $d_{H}(D,D^{\prime})\leq 1$ where $d_{H}$ denotes
Hamming distance, i.e., $d_{H}(D,D^{\prime})=|\\{i\in[n]\,:\,X_{i}\neq
X_{i}^{\prime}\\}|$.

######  Definition 1.6 ($(\varepsilon,\delta)$-Indistinguishable).

Let $D,D^{\prime}$ be two distributions defined on a set $\mathcal{Y}$. Then
$D,D^{\prime}$ are said to be $(\varepsilon,\delta)$-indistinguishable if for
all measurable $S\subseteq\mathcal{Y}$, $\mathbb{P}_{Y\sim D}\left[Y\in
S\right]\leq e^{\varepsilon}\mathbb{P}_{Y\sim D^{\prime}}\left[Y\in
S\right]+\delta$ and $\mathbb{P}_{Y\sim D^{\prime}}\left[Y\in S\right]\leq
e^{\varepsilon}\mathbb{P}_{Y\sim D}\left[Y\in S\right]+\delta$.

######  Definition 1.7 ($(\varepsilon,\delta)$-Differential Privacy [DMNS06]).

A randomized mechanism $\mathcal{M}\colon\mathcal{X}^{n}\to\mathcal{Y}$ is
said to be $(\varepsilon,\delta)$-differentially private if for all
neighbouring datasets $D,D^{\prime}\in\mathcal{X}^{n}$, $\mathcal{M}(D)$ and
$\mathcal{M}(D^{\prime})$ are $(\varepsilon,\delta)$-indistinguishable.

###  1.4 Techniques

The techniques in this paper are inspired by the techniques in [AL22] which
are based on the Propose-Test-Release framework [DL09] and the Subsample-And-
Aggregate framework [NRS07]. Given a dataset $D$, we first split $D$ into $t$
sub-datasets and run a non-private algorithm $\mathcal{A}$ on each of the sub-
datasets. Next, we privately check if most of the outputs of $\mathcal{A}$ are
“well-clustered” (i.e., are close to each other). If not, then the algorithm
fails as this suggests that the outputs of the non-private algorithm are not
very stable (either due to lack of data or simply that the non-private
algorithm is sensitive to its input). On the other hand, if most of the
outputs are well-clustered then we can aggregate these clustered outputs and
release a noisy version of it. There are, however, multiple additional
technical challenges that need to be addressed.

One core difficulty is the issue of the ordering of the Gaussian components.
Namely, the non-private GMM learners may output GMM components in different
orders. Therefore, aggregating these non-private solutions (e.g., by taking
their weighted average in the style of [AL22] seems impossible. We therefore
propose to skip the aggregation step all together by simply picking an
arbitrary solution from the cluster. Therefore, our private populous estimator
(PPE) simplifies and generalizes the private populous mean estimator (PPME)
framework of [AL22], making it applicable to general semimetric spaces (and
therefore GMMs). A precise discussion of this framework is presented in
Subsection 2.1.

Another challenge is designing an appropriate mechanism for adding noise to
GMMs. As discussed above, our framework requires that we are able to release a
noisy output of a candidate output. More precisely, given two neighbouring
datasets $Y_{1},Y_{2}$, we want to design a mechanism $\mathcal{B}$ such that
$\mathcal{B}(Y_{1})$, $\mathcal{B}(Y_{2})$ are indistinguishable whenever
$Y_{1},Y_{2}$ are sufficiently close. As in [AL22], we refer to such a
mechanism as a “masking mechanism”. In the context of mixture distributions
with $k$ components, a candidate output corresponds to a $k$-tuple where each
element of the tuple contain the parameters and the mixing weight of a single
component. We prove that, if one can design a masking mechanism for a _single_
component then it is possible to use this masking mechanism as a blackbox to
design a masking mechanism for the $k$-tuple with only a
$\operatorname{poly}(k)$ overhead in the running time. One important
ingredient is that we randomly shuffle the components, making the output
invariant to the order of the components.

Another challenge related to the order of components is that computing the
distance between two GMMs based on Definition 1.4 requires minimizing over all
permutations. A naive method for computing this distance could require
exponential time but we show this task can be done in polynomial time using a
simple reduction to bipartite matching.

To showcase the utility of the above framework, we show that it is
straightforward to apply the framework to privately learning mixtures of
Gaussians. We design a masking mechanism of a single Gaussian component which
consists of mixing the weight, the mean, and the covariance matrix. Masking
the mixing weight is fairly standard while masking the mean and the covariance
matrix can be done using known results (e.g. by using [AL22], Lemma 5.2) for
the covariance matrix and a similar technique for the mean).

Finally, we note that, in some of the literature for Gaussian mixtures, the
results usually assert that for each Gaussian component
$\mathcal{N}(\mu,\Sigma)$, the algorithm returns $\hat{\mu},\hat{\Sigma}$ such
that $\mathcal{N}(\mu,\Sigma)$ and $\mathcal{N}(\hat{\mu},\hat{\Sigma})$ are
close in _total variation_ distance (e.g. [MV10]). Our framework requires that
$\hat{\mu}$ (resp. $\hat{\Sigma}$) is close to $\mu$ (resp. $\Sigma$) for some
appropriate norm. Intuitively, this ought to be the case but no tight
characterization was previously known unless the Gaussians had the same mean
([DMR18], Theorem 1.1). In this paper, we prove the following tight
characterization between the TV distance of a Gaussian and its parameters. We
believe that such a result may be of independent interest.

theoremTightTV Let $\mu_{1},\mu_{2}\in\mathbb{R}^{d}$ and
$\Sigma_{1},\Sigma_{2}$ be $d\times d$ positive-definite matrices. Suppose
that we have
$d_{\mathrm{TV}}(\mathcal{N}(\mu_{1},\Sigma_{1}),\mathcal{N}(\mu_{2},\Sigma_{2}))<\frac{1}{600}$.
Let

$\Delta=\max\left\\{\|\Sigma_{1}^{-1/2}\Sigma_{2}\Sigma_{1}^{-1/2}-I_{d}\|_{F},\|\Sigma_{1}^{-1/2}(\mu_{1}-\mu_{2})\|_{2}\right\\}.$

Then

$\frac{1}{200}\Delta\leq
d_{\mathrm{TV}}\left({\mathcal{N}(\mu_{1},\Sigma_{1})},{\mathcal{N}(\mu_{2},\Sigma_{2})}\right)\leq\frac{1}{\sqrt{2}}\Delta.$

######  Remark 1.8.

Note that the total variation distance between
$\mathcal{N}(\mu_{1},\Sigma_{1})$ and $\mathcal{N}(\mu_{2},\Sigma_{2})$ is
symmetric (i.e. swapping $\mu_{1},\Sigma_{1}$ and $\mu_{2},\Sigma_{2}$ does
not affect the total variation distance) while the definition of $\Delta$ is
not. Thus, the theorem can be automatically strengthened to show that the
bounds also hold when $\Delta$ is defined by swapping $\Sigma_{1}$ and
$\Sigma_{2}$.

##  2 Private Populous Estimator

In this section, we describe our main framework which we call the “private
populous estimator” (PPE). Before that, we need a few definitions.

#### Semimetric spaces.

In our application, we need to deal with distance functions which only satisfy
an _approximate_ triangle inequality that hold only when the points are
sufficiently close together. To that end, we first define the notion of a
semimetric space.

######  Definition 2.1 (Semimetric Space).

We say $(\mathcal{F},\operatorname{dist})$ is a semimetric space if for every
$F,F_{1},F_{2},F_{3}\in\mathcal{F}$, the following conditions hold.

  1. 1.

Non-negativity. $\operatorname{dist}(F,F)=0$;
$\operatorname{dist}(F_{1},F_{2})\geq 0$.

  2. 2.

Symmetry. $\operatorname{dist}(F_{1},F_{2})=\operatorname{dist}(F_{2},F_{1})$.

  3. 3.

$z$-approximate $r$-restricted triangle inequality. Let $r>0$ and $z\geq 1$.
If $\operatorname{dist}(F_{1},F_{2}),\operatorname{dist}(F_{2},F_{3})\leq r$
then $\operatorname{dist}(F_{1},F_{3})\leq
z\cdot(\operatorname{dist}(F_{1},F_{2})+\operatorname{dist}(F_{2},F_{3}))$.

#### Masking mechanism.

Intuitively, a masking mechanism $\mathcal{B}$ is a random function that
returns a noisy version of its input, with the goal of making close inputs
indistinguishable. Formally, we define a masking mechanism as follows.

######  Definition 2.2 (Masking Mechanism ([AL22], Definition 3.3)).

Let $(\mathcal{F},\operatorname{dist})$ be a semimetric space. A randomized
function $\mathcal{B}\colon\mathcal{F}\to\mathcal{F}$ is a
$(\gamma,\varepsilon,\delta)$-masking mechanism for
$(\mathcal{F},\operatorname{dist})$ if for all $F,F^{\prime}\in\mathcal{F}$
satisfying $\operatorname{dist}(F,F^{\prime})\leq\gamma$, we have that
$\mathcal{B}(F),\mathcal{B}(F^{\prime})$ are
$(\varepsilon,\delta)$-indistinguishable. Further, $\mathcal{B}$ is said to be
$(\alpha,\beta)$-concentrated if for all $F\in\mathcal{F}$,
$\mathbb{P}[\operatorname{dist}(\mathcal{B}(F),F)>\alpha]\leq\beta$.

###  2.1 The Private Populous Estimator (PPE)

In this section, we define the PPE framework which allows us to use non-
private algorithms to design private algorithms. We represent the non-private
algorithm by $\mathcal{A}\colon\mathcal{X}^{*}\to\mathcal{Y}$ which takes
elements from a dataset as inputs and outputs an element in $\mathcal{Y}$. PPE
requires two assumptions. Firstly, we assume that
$(\mathcal{Y},\operatorname{dist})$ is a semimetric space. Secondly, we assume
that we have access to an efficient masking mechanism for
$(\mathcal{Y},\operatorname{dist})$.

The PPE framework we introduce in this section can be seen as a somewhat
generalized version of the framework used in [AL22] and requires fewer
assumptions. Given a dataset $D$ as inputs, we partition $D$ into $t$ disjoint
subsets. Next, we run the non-private algorithm $\mathcal{A}$ on each of these
subsets to produce $t$ outputs $Y_{1},\ldots,Y_{t}$. We then privately check
if most of the $t$ outputs are close to each other. If not, PPE fails.
Otherwise, it chooses a $Y_{j}$ that is close to more than $60\%$ of other
$Y_{i}$’s. It then adds noise to $Y_{j}$ using a masking mechanism
$\mathcal{B}$, and returns the masked version of $Y_{j}$. The formal details
of the algorithm can be found in Algorithm 1.

Algorithm 1 Private Populous Estimator

Input: Dataset $D=(X_{1},\ldots,X_{m})$, any algorithm
$\mathcal{A}\colon\mathcal{X}^{*}\to\mathcal{Y}$, parameters
$r,\varepsilon,\delta>0,z\geq 1,t\in\mathbb{N}_{\geq 1}$.

1:Let $s\leftarrow\lfloor m/t\rfloor$.

2:For $i\in[t]$, let
$Y_{i}\leftarrow\mathcal{A}(\\{X_{\ell}\\}_{\ell=(i-1)s+1}^{is})$.

3:For $i\in[t]$, let
$q_{i}\leftarrow\frac{1}{t}|\\{j\in[t]\,:\,\operatorname{dist}(Y_{i},Y_{j})\leq
r/2z\\}|$.

4:Let $Q\leftarrow\frac{1}{t}\sum_{i\in[t]}q_{i}$.

5:Let $Z\sim\operatorname{TLap}(2/t,\varepsilon,\delta)$.

6:Let $\widetilde{Q}\leftarrow Q+Z$.

7:If
$\widetilde{Q}<0.8+\frac{2}{t\varepsilon}\ln\left(1+\frac{e^{\varepsilon}-1}{2\delta}\right)$,
fail and return $\perp$.

8:$j=\min\\{i\,:\,q_{i}>0.6\\}$.

9:Return $\widetilde{Y}=\mathcal{B}(Y_{j})$.

The following theorem establishes the privacy and accuracy of Algorithm 1. The
proof can be found in Appendix D.1.

######  Theorem 2.3.

Suppose that $(\mathcal{Y},\operatorname{dist})$ satisfies a $z$-approximate
$r$-restricted triangle inequality. Further, suppose that $\mathcal{B}$ is a
$(r,\varepsilon,\delta)$-masking mechanism.

  * •

Privacy. For $t>5$, Algorithm 1 is $(2\varepsilon,4e^{\varepsilon}\delta)$-DP.

  * •

Utility. Suppose $\alpha\leq r/2z$ and
$t\geq(\frac{20}{\varepsilon}\ln\left(1+\frac{e^{\varepsilon}-1}{2\delta}\right)$.
Let $\mathcal{B}$ be $(\alpha/2z,\beta)$-concentrated. If there exists $Y^{*}$
with the property that for all
$i\in[t],\operatorname{dist}(Y^{*},Y_{i})<\alpha/2z$, then
$\mathbb{P}\left[\operatorname{dist}(\widetilde{Y},Y^{*})>\alpha\right]\leq\beta$.

The utility guarantee asserts that if the outcome of all non-private
procedures are close to each other, then the output of the PPE will be close
to those non-private outcomes.

######  Remark 2.4.

Let $T_{\mathcal{A}}$ be the running time of the algorithm $\mathcal{A}$ in
Line 2, $T_{\operatorname{dist}}$ be the time to compute
$\operatorname{dist}(Y_{i},Y_{j})$ for any $Y_{i},Y_{j}\in\mathcal{Y}$ in Line
3, and $T_{\mathcal{B}}$ be the time to compute $\widetilde{Y}$ in Line 9.
Then Algorithm 1 runs in time $O(t\cdot T_{\mathcal{A}}+t^{2}\cdot
T_{\operatorname{dist}}+T_{\mathcal{B}})$. We will see that $T_{\mathcal{A}}$,
$T_{\mathcal{B}}$, and $T_{\operatorname{dist}}$ can be polynomially bounded
for GMMs.

To apply Algorithm 1 for private learning of GMMs, we need to introduce a
masking mechanism for them.

In order to do that, we start by defining how one can convert a masking
mechanism for a component to one for mixtures (Section 3). We then define a
masking mechanism for a single Gaussian component (presented in Section 4).
Finally, we apply this to come up with a masking mechanism for GMMs as shown
in Section 5.

##  3 Masking Mixtures

The goal of this section is to show how to “lift” a masking mechanism for a
single component to a masking mechanism for mixtures. We can do this by adding
noise to each of the components and randomly permute the output components.

Formally, let $\mathcal{F}$ denote a space and let
$\mathcal{F}^{k}=\mathcal{F}\times\ldots\times\mathcal{F}$ ($k$ times). The
following definition is useful in defining the distance between two mixtures,
as it is invariant to the order of components.

######  Definition 3.1.

Let $\operatorname{dist}$ denote a distance function on $\mathcal{F}$. We
define
$\operatorname{dist}^{k}\colon\mathcal{F}^{k}\times\mathcal{F}^{k}\to\mathbb{R}_{\geq
0}$ as

$\operatorname{dist}^{k}((F_{1},\ldots,F_{k}),(F_{1}^{\prime},\ldots,F_{k}^{\prime}))\coloneqq\min_{\pi}\max_{i\in[k]}\operatorname{dist}(F_{i},F_{\pi(i)}^{\prime}),$

where the minimization is taken over all permutations $\pi$.

Note that computing $\operatorname{dist}^{k}$ requires computing a minimum
over all permutations $\pi$. Naively, one might assume that this requires
exponential time to try all permutations. However, it turns out that one can
reduce the problem of computing $\operatorname{dist}^{k}$ to deciding whether
a perfect matching exists in a weighted bipartite graph. The details of this
argument can be found in Appendix E.1.

######  Lemma 3.2.

If $T_{\operatorname{dist}}$ is the running time to compute
$\operatorname{dist}$ then $\operatorname{dist}^{k}$ can be computed in time
$O(k^{2}T_{\operatorname{dist}}+k^{3}\log k)$.

The following definition is useful for extending a masking mechanism for a
component to a masking mechanism for a mixture. The important thing is that
the components are shuffled randomly in this mechanism, making the outcome
independent of the original order of the components.

######  Definition 3.3.

Suppose that $\mathcal{B}$ is a $(\gamma,\varepsilon,\delta)$-masking
mechanism for $\mathcal{F}$. We define the mechanism
$\mathcal{B}_{\sigma}^{k}$ as
$\mathcal{B}_{\sigma}^{k}(F_{1},\ldots,F_{k})=(\mathcal{B}(F_{\sigma(1)}),\ldots,\mathcal{B}(F_{\sigma(k)}))$,
where $\sigma$ is a uniform random permutation.

We also note that $\mathcal{B}_{\sigma}^{k}$ can be computed with only
polynomial overhead. The proof can be found in Appendix E.2.

######  Lemma 3.4.

If $T_{\mathcal{B}}$ is the running time of $\mathcal{B}$ then
$\mathcal{B}_{\sigma}^{k}$ can be computed in time $O(k\cdot
T_{\mathcal{B}}+k\log k)$.

The next lemma shows that $\mathcal{B}_{\sigma}^{k}$ is indeed a masking
mechanism w.r.t. $(\mathcal{F}^{k},\operatorname{dist}^{k})$ and that
$\mathcal{B}_{\sigma}^{k}$ is accurate provided that $\mathcal{B}$ is
accurate. The proof can be found in Appendix E.3.

######  Lemma 3.5.

If $\mathcal{B}$ is an $(\alpha,\beta)$-concentrated
$(\gamma,\varepsilon,\delta)$-masking mechanism for
$(\mathcal{F},\operatorname{dist})$ then, for any $\delta^{\prime}>0$,
$\mathcal{B}_{\sigma}^{k}$ is an $(\alpha,k\beta)$-concentrated
$(\gamma,\varepsilon^{\prime},k\delta+\delta^{\prime})$-masking mechanism for
$(\mathcal{F}^{k},\operatorname{dist}^{k})$ where

$\varepsilon^{\prime}=\sqrt{2k\ln(1/\delta^{\prime})}\varepsilon+k\varepsilon(e^{\varepsilon}-1).$

Recall that Theorem 2.3 requires that the distance function satisfies an
$r$-restricted $z$-approximate. The following lemma shows that
$\operatorname{dist}^{k}$ indeed does satisfy this property provided that
$\operatorname{dist}$ does. The proof can be found in Appendix E.4.

######  Lemma 3.6.

If $\operatorname{dist}$ satisfies an $r$-restricted $z$-approximate triangle
inequality then so does $\operatorname{dist}^{k}$.

##  4 Masking a Single Gaussian Component

In this section, we develop a masking mechanism for a single Gaussian
component. For that we define a new distance measure between Gaussian
components.

Let
$\mathcal{F}_{\textsc{Comp}}=\mathbb{R}\times\mathbb{R}^{d}\times\mathbb{R}^{d\times
d}$ (corresponding to the weight $w$, mean $\mu$, and covariance matrix
$\Sigma$, respectively). Define
$\operatorname{dist}_{\textsc{Comp}}\colon\mathcal{F}_{\textsc{Comp}}\times\mathcal{F}_{\textsc{Comp}}\to\mathbb{R}_{\geq
0}$ as

$\operatorname{dist}_{\textsc{Comp}}((w_{1},\mu_{1},\Sigma_{1}),(w_{2},\mu_{2},\Sigma_{2}))=\max\\{|w_{1}-w_{2}|,\operatorname{dist}_{\textsc{Mean}}((\mu_{1},\Sigma_{1}),(\mu_{2},\Sigma_{2})),\operatorname{dist}_{\textsc{Cov}}(\Sigma_{1},\Sigma_{2})\\},$

where

$\operatorname{dist}_{\textsc{Cov}}(\Sigma_{1},\Sigma_{2})=\max\\{\|\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}-I_{d}\|_{F},\|\Sigma_{2}^{1/2}\Sigma_{1}^{-1}\Sigma_{2}^{1/2}-I_{d}\|_{F}\\}$

and

$\operatorname{dist}_{\textsc{Mean}}((\mu_{1},\Sigma_{1}),(\mu_{2},\Sigma_{2}))=\max\\{\|\mu_{1}-\mu_{2}\|_{\Sigma_{1}},\|\mu_{1}-\mu_{2}\|_{\Sigma_{2}}\\}.$

First, we show that $\operatorname{dist}_{\textsc{Comp}}$ satisfies an
approximate triangle inequality; this is useful in order to use Theorem 2.3.

######  Lemma 4.1.

$\operatorname{dist}_{\textsc{Comp}}$ satisfies a $1$-restricted
$(3/2)$-approximate triangle inequality.

###### Proof.

For any positive-definite matrix $\Sigma$, $\|\cdot\|_{\Sigma}$ is a metric
and thus, $\operatorname{dist}_{\textsc{Mean}}$ is a metric (and therefore
satisfies the $1$-restricted $(3/2)$-approximate triangle inequality). Next,
$\operatorname{dist}_{\textsc{Cov}}$ satisfies the $1$-restricted
$(3/2)$-approximate triangle inequality (see Lemma A.8). A straightforward
calculation concludes that, as a result, $\operatorname{dist}_{\textsc{Comp}}$
also satisfies a $1$-restricted $(3/2)$-approximate triangle inequality. ∎

The following lemma gives a masking mechanism for a single Gaussian mechanism.
The proof can be found Appendix F. The mechanism essentially noises the mixing
weight, the mean, and the covariance matrix separately. For noising the mixing
weight, one can do this using the Gaussian mechanism. Care must be taken to
noise the mean and the covariance matrix. In both cases, we use the empirical
covariance matrix itself to re-scale both the mean and the covariance matrix.
Note that the parameters $\gamma$ (how close the inputs must be) as well as
$\eta_{\textsc{W}},\eta_{\textsc{Mean}},\eta_{\textsc{Cov}}$ (the noise
magnitude) must be set correctly to ensure privacy and accuracy. Roughly
speaking, for a vector of size $d$, we should take the noise $\eta$ to about
$\alpha/\sqrt{d}$ to ensure that accuracy is within an error of $\alpha$. So
$\eta_{\textsc{W}}\sim\alpha$, $\eta_{\textsc{Mean}}\sim\alpha/\sqrt{d}$ and
$\eta_{\textsc{Cov}}\sim\alpha/d$. To ensure $(\varepsilon,\delta)$-DP, we
need to ensure that the outputs are guaranteed to be close enough (otherwise
the noise is not enough to make the inputs indistinguishable). The bottleneck
comes from noising the covariance matrix which requires that
$\gamma\sim\varepsilon\eta_{\textsc{Cov}}/\sqrt{d}\sim\alpha\varepsilon/d^{3/2}$.
More details about the parameter choices can be found in Appendix F.

######  Lemma 4.2.

For
$\gamma\leq\frac{\varepsilon\alpha}{C_{2}\sqrt{d^{2}(d+\ln(4/\beta))}\cdot\ln(2/\delta)}$,
there exists a $(\gamma,3\varepsilon,3\delta)$-masking mechanism,
$\mathcal{B}_{\textsc{Comp}}$, for
$(\mathcal{F}_{\textsc{Comp}},\operatorname{dist}_{\textsc{Comp}})$ that is
$(\alpha,3\beta)$-concentrated, where $C_{2}$ is a universal constant.

##  5 A Masking Mechanism for GMMs

In this section, we show how to mask a mixture of $k$ Gaussians. Let
$\mathcal{F}_{\textsc{Gmm}}=\mathcal{F}_{\textsc{Comp}}\times\ldots\times\mathcal{F}_{\textsc{Comp}}$
($k$ times). Note we drop $k$ from $\mathcal{F}_{\textsc{Gmm}}$ (and related
notation below) since $k$ is fixed and implied from context. Let
$\operatorname{dist}_{\textsc{Comp}}$ be as defined in Eq. (4) and define the
distance

$\operatorname{dist}_{\textsc{Param}}(\\{(w_{i},\mu_{i},\Sigma_{i})\\}_{i\in[k]},\\{(w_{i}^{\prime},\mu_{i}^{\prime},\Sigma_{i}^{\prime})\\}_{i\in[k]})=\min_{\pi}\max_{i\in[k]}\operatorname{dist}_{\textsc{Comp}}((w_{\pi(i)},\mu_{\pi(i)},\Sigma_{\pi(i)}),(w_{i}^{\prime},\mu_{i}^{\prime},\Sigma_{i}^{\prime})),$

where $\pi$ is chosen from the set of all permutations over $[k]$. Now define
the masking mechanism

$\mathcal{B}_{\textsc{Gmm}}(\\{(w_{i},\mu_{i},\Sigma_{i})\\}_{i\in[k]})=\\{\mathcal{B}_{\textsc{Comp}}(w_{\sigma(i)},\mu_{\sigma(i)},\Sigma_{\sigma(i)})\\}_{i\in[k]},$

where $\mathcal{B}_{\textsc{Comp}}$ is the masking mechanism from Lemma 4.2
and $\sigma$ is a permutation chosen uniformly at random from the set of all
permutations over $[k]$. In words, $\mathcal{B}_{\textsc{Gmm}}$ applies the
masking mechanism $\mathcal{B}_{\textsc{Comp}}$ from Section 4 to each
component separately and then permutes the components. To summarize the entire
masking mechanism for GMMs, we provide pseudocode in Algorithm 2.

The following lemma asserts that $\mathcal{B}_{\textsc{Gmm}}$ is indeed a
masking mechanism. At a high-level, it follows by combining Lemma 4.2 with
Lemma 3.5. The details can be found in Appendix G.1.

######  Lemma 5.1.

Let $\varepsilon<\ln(2)/3$. There is a sufficiently large constant $C_{2}$
such that for
$\gamma\leq\frac{\varepsilon\alpha}{C_{2}\sqrt{k\ln(2/\delta)}\sqrt{d^{2}(d+\ln(12k/\beta))}\cdot\ln(12k/\delta)}$,
$\mathcal{B}_{\textsc{Gmm}}$ is a $(\gamma,\varepsilon,\delta)$-masking
mechanism with respect to
$(\mathcal{F}_{\textsc{Gmm}},\operatorname{dist}_{\textsc{Param}})$. Moreover,
$\mathcal{B}_{\textsc{Gmm}}$ is $(\alpha,\beta)$-concentrated.

Note that $\operatorname{dist}_{\textsc{Param}}$ also satisfies a
$1$-restricted $(3/2)$-approximate triangle inequality since
$\operatorname{dist}_{\textsc{Comp}}$ does (see Appendix G.2 for a proof).

######  Lemma 5.2.

$\operatorname{dist}_{\textsc{Param}}$ satisfies a $1$-restricted
$(3/2)$-approximate triangle inequality.

Algorithm 2 GMM Masking Mechanism

Input: GMM given by $\\{(w_{i},\mu_{i},\Sigma_{i})\\}_{i\in[k]}$ and
parameters $\eta_{\textsc{W}},\eta_{\textsc{Mean}},\eta_{\textsc{Cov}}>0$

1:function $\mathcal{R}_{\textsc{W}}$($w$) $\triangleright$ Noise mixing
weights

2: Return $\max(0,w+\eta_{\textsc{W}}g)$ where $g\sim\mathcal{N}(0,1)$.

3:end function

4:function $\mathcal{R}_{\textsc{Mean}}$($\mu,\Sigma$) $\triangleright$ Noise
mean

5: Return $\mu+\eta_{\textsc{Mean}}g$ where $g\sim\mathcal{N}(0,\Sigma)$

6:end function

7:function $\mathcal{R}_{\textsc{Cov}}$($\Sigma$) $\triangleright$ Noise
covariance

8: Let $G\in\mathbb{R}^{d\times d}$ matrix with independent $\mathcal{N}(0,1)$
entries.

9: Return
$\Sigma^{1/2}(I_{d}+\eta_{\textsc{Cov}}G)(I_{d}+\eta_{\textsc{Cov}}G)^{\top}\Sigma^{1/2}$

10:end function

11:function $\mathcal{B}_{\textsc{Comp}}$($w,\mu,\Sigma$) $\triangleright$
Mask component

12: Return
$(\mathcal{R}_{\textsc{W}}(w),\mathcal{R}_{\textsc{Mean}}(\mu,\Sigma),\mathcal{R}_{\textsc{Cov}}(\Sigma))$

13:end function

14:function
$\mathcal{B}_{\textsc{Gmm}}$($\\{(w_{i},\mu_{i},\Sigma_{i})\\}_{i\in[k]}$)
$\triangleright$ Mask GMM

15: Let $\sigma$ be uniformly random permutation.

16:
$\\{(\hat{w}_{i},\hat{\mu},\hat{\Sigma}_{i})\\}\leftarrow\\{\mathcal{B}_{\textsc{Comp}}(w_{\sigma(i)},\mu_{\sigma(i)},\Sigma_{\sigma(i)})\\}$.

17: Normalize: $\hat{w}_{i}\leftarrow\hat{w}_{i}/\sum_{i\in[k]}\hat{w}_{i}$.

18: Return $\\{(\hat{w}_{i},\hat{\mu},\hat{\Sigma}_{i})\\}_{i\in[k]}$.

19:end function

##  6 Privately Learning GMMs

At this point, we have everything we need to develop a private algorithm for
learning the parameters of a GMM. First, we define the problem more formally.

######  Definition 6.1 (PAC Learning of Parameters of GMMs).

Let
$\mathcal{F}=\left\\{\left(w_{i}^{j},\mu_{i}^{j},\Sigma_{i}^{j}\right)_{i=1}^{k}\right\\}^{j}$
be a class of $d$-dimensional GMMs with $k$ components555For examples, it is
standard to pick $\mathcal{F}$ to be those GMMs that are
separable/identifiable.. Let $\mathcal{A}$ be function that receives a
sequence $S$ of instances in $\mathbb{R}^{d}$ and outputs a mixture
$\hat{F}=(\hat{w}_{i},\hat{\mu}_{i},\hat{\Sigma}_{i})_{i=1}^{k}$. Let
$m\colon(0,1)^{2}\times\mathbb{N}^{2}\to\mathbb{N}$. We say $\mathcal{A}$
learns the parameters of $\mathcal{F}$ with $m$ samples if for every
$\alpha,\beta\in(0,1)$ and every $F\in\mathcal{F}$, if $S$ is an i.i.d. sample
of size $m(\alpha,\beta,k,d)$ from $F$, then
$\operatorname{dist}_{\textsc{Gmm}}(F,\hat{F})<\alpha$ with probability at
least $1-\beta$.

Plugging the masking mechanism developed in Section 5 (in particular, Lemma
5.1 and Lemma 5.2) into PPE (Theorem 2.3) gives a private to non-private
reduction for GMMs.

######  Theorem 6.2 (Private to Non-Private Reduction).

Let $\mathcal{F}$ be a subclass of GMMs with $k$ components in
$\mathbb{R}^{d}$. Let $\mathcal{A}$ be a non-private Algorithm that PAC learns
the parameters of $\mathcal{F}$ with respect to
$\operatorname{dist}_{\textsc{Gmm}}$ using $m_{\textsc{non-
private}}(\alpha,\beta,k,d)$ samples. Then for every $\varepsilon<\ln(2)/3$,
$\delta\in(0,1)$,
$\gamma\leq\frac{\varepsilon\alpha}{C_{2}\sqrt{k\ln(2/\delta)}\sqrt{d^{2}(d+\ln(12k/\beta))}\cdot\ln(12k/\delta)}$
for a sufficiently large constant $C$ and
$t=\max\\{5,\lceil\frac{20}{\varepsilon}\ln(1+\frac{e^{\varepsilon}-1}{2\delta})\rceil\\}$,
there is a learner $\mathcal{A}_{\textsc{private}}$ with the following
properties:

  1. 1.

$\mathcal{A}_{\textsc{private}}$ is
$(2\varepsilon,4e^{\varepsilon}\delta)$-DP.

  2. 2.

$\mathcal{A}_{\textsc{private}}$ PAC learns the parameters of $\mathcal{F}$
using $O(m_{\textsc{non-
private}}(\gamma,\beta/2t,k,d)\log(1/\delta)/\varepsilon)$ samples.

  3. 3.

$\mathcal{A}_{\textsc{private}}$ runs in time
$O((\log(1/\delta)/\varepsilon)\cdot
T_{\mathcal{A}}+(\log(1/\delta)/\varepsilon)^{2}\cdot(k^{2}d^{3}+k^{3}\log
k))$, where $T_{\mathcal{A}}$ is the running time for the non-private
algorithm.

To prove Theorem 6.2, we require the following lemma whose proof can be found
in Appendix H.

######  Lemma 6.3.

Let $F=\left(w_{i},\mu_{i},\Sigma_{i}\right)_{i=1}^{k}$ and
$F^{\prime}=\left(w_{i}^{\prime},\mu_{i}^{\prime},\Sigma_{i}^{\prime}\right)_{i=1}^{k}$
be two $d$-dimensional GMMs where $\Sigma_{i}$ and $\Sigma^{\prime}_{i}$ are
positive-definite matrices. Suppose that
$\operatorname{dist}_{\textsc{Gmm}}\left(F,F^{\prime}\right)<\frac{1}{600}$.
Then
$\frac{1}{200}\operatorname{dist}_{\textsc{Param}}(F,F^{\prime})\leq\operatorname{dist}_{\textsc{Gmm}}(F,F^{\prime})\leq\frac{1}{\sqrt{2}}\operatorname{dist}_{\textsc{Param}}(F,F^{\prime})$.

###### Proof of Theorem 6.2.

Let $z=3/2$, $r=1$, and
$t\geq\frac{20}{\varepsilon}\ln\left(1+\frac{e^{\varepsilon}-1}{2\delta}\right)=O(\log(1/\delta)/\varepsilon)$.
We run Algorithm 1 with the following.

  * •

For the non-private algorithm $\mathcal{A}$, we use the algorithm from Theorem
6.5 with accuracy parameter $\alpha/2z$ and failure probability $\beta/2t$.

  * •

For the masking mechanism, we use the $(r,\varepsilon,\delta)$-masking
mechanism $\mathcal{B}_{\textsc{Gmm}}$ which is defined in Lemma 5.1. Further,
this mechanism is $(\alpha/2z,\beta/2)$-concentrated.

  * •

Finally, note that the distance function
$\operatorname{dist}_{\textsc{Param}}$ satisfies the $z$-approximate
$r$-restricted triangle inequality (Lemma 5.2).

Let $F^{*}$ be the true GMM. Let $F_{i}$ be the estimated GMMs computed by
$\mathcal{A}$ in Line 2 of Algorithm 1. Then the first item above guarantees
that $\operatorname{dist}_{\textsc{Param}}(F^{*},F_{i})\leq\alpha/2z$ for all
$i\in[t]$ with probability at least $1-\beta/2$.

We thus conclude that we have a private algorithm for learning GMMs that is
$(2\varepsilon,4e^{\varepsilon}\delta)$-DP and that returns $\widetilde{F}$
satisfying
$\operatorname{dist}_{\textsc{Param}}(\widetilde{F},F^{*})\leq\alpha$ with
probability $1-\beta$. By Lemma 6.3, we further conclude that
$\operatorname{dist}_{\textsc{Gmm}}(\widetilde{F},F^{*})\leq O(\alpha)$ with
probability $1-\beta$.

It remains to check the sample complexity and computational complexity of our
algorithm. Since we run $t$ independent instances of the non-private algorithm
$\mathcal{A}$, we require $t\cdot
m_{\textsc{private}}(\alpha/2z,\beta/2t,k,d)=O(m_{\textsc{private}}(\alpha/2z,\beta/2t,k,d)\cdot\log(1/\delta)/\varepsilon)$
samples. Finally, we bound the running time. Lemma 3.4 shows that the running
time to apply the masking mechanism is $O(k\cdot d^{3}+k\log k)$ and Lemma 3.2
shows that the running time to compute $\operatorname{dist}$ is
$O(k^{2}d^{3}+k^{3}\log k)$. The claimed running time now follows from Remark
2.4. ∎

###  6.1 Application

As a concrete application, we apply Theorem 6.2 with the algorithm of [MV10]
to obtain the first private algorithm for learning the parameters of a GMM
with sample and computational complexity that is polynomial in $d$ (for a
fixed $k$) with minimal separation assumptions. Note that our algorithm does
not require any boundedness assumptions on the parameters.

######  Definition 6.4 ($\gamma$-Statistically Learnable [MV10]).

We say a GMM $F=\left(w_{i},\mu_{i},\Sigma_{i}\right)_{i=1}^{k}$ is
$\gamma$-statistically learnable if (i) $\min_{i}w_{i}\geq\gamma$ and (ii)
$\min_{i\neq
j}d_{\mathrm{TV}}\left({\mathcal{N}(\mu_{i},\Sigma_{i})},{\mathcal{N}(\mu_{j},\Sigma_{j})}\right)\geq\gamma$.

If a GMM is $\gamma$-statistically learnable, we will be able to recover its
components accurately.

######  Theorem 6.5 (Non-private Learning of GMMs [MV10]).

There exists an algorithm $\mathcal{A}$ and a function
$m_{\mathcal{A}}(d,k,\alpha,\beta)$ with the following guarantee. Fix
$\alpha,\beta\in(0,1)$, $k,d\in\mathbb{N}$.

  * •

For fixed $k$, the sample complexity $m_{\mathcal{A}}(d,k,\alpha,\beta)$ is
polynomial in $d/\alpha\beta$.

  * •

For fixed $k$, $\mathcal{A}$ runs in time
$\operatorname{poly}(d/\alpha\beta)$.

  * •

Let $\mathcal{F}^{*}$ be an $\alpha$-statistically learnable subclass of GMMs
with $k$ components in $\mathbb{R}^{d}$ and let $F^{*}\in\mathcal{F}^{*}$.
Given an i.i.d. sample $D$ of size $m_{\mathcal{A}}(d,k,\alpha,\beta)$ drawn
from $F^{*}$, with probability at least $1-\beta$, $\mathcal{A}$ return
$\hat{F}$ such that
$\operatorname{dist}_{\textsc{Gmm}}(\hat{F},F^{*})\leq\alpha$.

The following corollary follows immediately by plugging Theorem 6.5 into
Theorem 6.2.

######  Corollary 6.6.

There exists an algorithm $\mathcal{A}$ and a function
$m_{\mathcal{A}}(d,k,\alpha,\beta,\varepsilon,\delta)$ with the following
guarantee. Fix $\alpha,\beta,\varepsilon,\delta\in(0,1)$, $k,d\in\mathbb{N}$.

  * •

$\mathcal{A}$ is $(\varepsilon,\delta)$-DP.

  * •

For fixed $k$, the sample complexity
$m_{\mathcal{A}}(d,k,\alpha,\beta,\varepsilon,\delta)$ is polynomial in
$d\log(1/\delta)/\alpha\beta\varepsilon$.

  * •

For fixed $k$, $\mathcal{A}$ runs in time
$\operatorname{poly}(d\log(1/\delta)/\alpha\beta\varepsilon)$.

  * •

Let $\mathcal{F}^{*}$ be an $\alpha$-statistically learnable subclass of GMMs
with $k$ components in $\mathbb{R}^{d}$ and let $F^{*}\in\mathcal{F}^{*}$.
Given an i.i.d. sample $D$ of size
$m_{\mathcal{A}}(d,k,\alpha,\beta,\varepsilon,\delta)$ drawn from $F^{*}$,
with probability at least $1-\beta$, $\mathcal{A}$ return $\hat{F}$ such that
$\operatorname{dist}_{\textsc{Gmm}}(\hat{F},F^{*})\leq\alpha$.

#### Acknowledgements.

The authors would like to thank Abbas Mehrabian for pointing out a mistake in
an earlier version Theorem 1.4. The authors would also like to the anonymous
reviewers for many insightful comments. Hassan Ashtiani was supported by an
NSERC Discovery grant.

## References

  * [AAK21] Ishaq Aden-Ali, Hassan Ashtiani and Gautam Kamath  “On the sample complexity of privately learning unbounded high-dimensional gaussians”  In _Algorithmic Learning Theory_ , 2021, pp. 185–216  PMLR
  * [AAL21] Ishaq Aden-Ali, Hassan Ashtiani and Christopher Liaw  “Privately learning mixtures of axis-aligned gaussians”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 3925–3938
  * [ABGRV14] Joseph Anderson, Mikhail Belkin, Navin Goyal, Luis Rademacher and James Voss  “The more, the merrier: the blessing of dimensionality for learning large Gaussian mixtures”  In _Conference on Learning Theory_ , 2014, pp. 1135–1164  PMLR
  * [ABHLMP18] Hassan Ashtiani, Shai Ben-David, Nicholas Harvey, Christopher Liaw, Abbas Mehrabian and Yaniv Plan  “Nearly tight sample complexity bounds for learning mixtures of gaussians via sample compression schemes”  In _Advances in Neural Information Processing Systems_ 31, 2018
  * [ABHLMP20] Hassan Ashtiani, Shai Ben-David, Nicholas JA Harvey, Christopher Liaw, Abbas Mehrabian and Yaniv Plan  “Near-optimal sample complexity bounds for robust learning of gaussian mixtures via compression schemes”  In _Journal of the ACM (JACM)_ 67.6 ACM New York, NY, USA, 2020, pp. 1–42
  * [ABM18] Hassan Ashtiani, Shai Ben-David and Abbas Mehrabian  “Sample-efficient learning of mixtures”  In _Proceedings of the AAAI Conference on Artificial Intelligence_ 32, 2018
  * [ADLS17] Jayadev Acharya, Ilias Diakonikolas, Jerry Li and Ludwig Schmidt  “Sample-optimal density estimation in nearly-linear time”  In _Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms_ , 2017, pp. 1278–1289  SIAM
  * [AKTVZ22] Daniel Alabi, Pravesh K. Kothari, Pranay Tankala, Prayaag Venkat and Fred Zhang  “Privately Estimating a Gaussian: Efficient, Robust and Optimal”  In _arXiv preprint arXiv:2212.08018_ , 2022
  * [AL22] Hassan Ashtiani and Christopher Liaw  “Private and polynomial time algorithms for learning Gaussians and beyond”  In _Conference on Learning Theory_ , 2022, pp. 1075–1076  PMLR
  * [AM05] Dimitris Achlioptas and Frank McSherry  “On spectral learning of mixtures of distributions”  In _International Conference on Computational Learning Theory_ , 2005, pp. 458–469  Springer
  * [ASZ21] Jayadev Acharya, Ziteng Sun and Huanyu Zhang  “Differentially private assouad, fano, and le cam”  In _Algorithmic Learning Theory_ , 2021, pp. 48–78  PMLR
  * [AUZ23] Hilal Asi, Jonathan Ullman and Lydia Zakynthinou  “From Robustness to Privacy and Back”  In _arXiv preprint arXiv:2302.01855_ , 2023
  * [BDJKKV22] Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M Kane, Pravesh K Kothari and Santosh S Vempala  “Robustly learning mixtures of k arbitrary gaussians”  In _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_ , 2022, pp. 1234–1247
  * [BDKU20] Sourav Biswas, Yihe Dong, Gautam Kamath and Jonathan Ullman  “Coinpress: Practical private mean and covariance estimation”  In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 14475–14485
  * [BGSUZ21] Gavin Brown, Marco Gaboardi, Adam Smith, Jonathan Ullman and Lydia Zakynthinou  “Covariance-aware private mean estimation without private covariance estimation”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 7950–7964
  * [BKS22] Alex Bie, Gautam Kamath and Vikrant Singhal  “Private Estimation with Public Data”  In _Advances in Neural Information Processing Systems_ , 2022
  * [BS09] Mikhail Belkin and Kaushik Sinha  “Learning Gaussian mixtures with arbitrary separation”  In _arXiv preprint arXiv:0907.1054_ , 2009
  * [BS10] Mikhail Belkin and Kaushik Sinha  “Polynomial learning of distribution families”  In _2010 IEEE 51st Annual Symposium on Foundations of Computer Science_ , 2010, pp. 103–112  IEEE
  * [BSKW19] Mark Bun, Thomas Steinke, Gautam Kamath and Zhiwei Steven Wu  “Private hypothesis selection”  In _Advances in Neural Information Processing Systems_ 32, 2019
  * [BV08] S Charles Brubaker and Santosh S Vempala  “Isotropic PCA and affine-invariant clustering”  In _Building Bridges_ Springer, 2008, pp. 241–281
  * [CCdEIST23] Hongjie Chen, Vincent Cohen-Addad, Tommaso d’Orsi, Alessandro Epasto, Jacob Imola, David Steurer and Stefan Tiegel  “Private estimation algorithms for stochastic block models and mixture models”  In _arXiv preprint arXiv:2301.04822_ , 2023
  * [CDSS14] Siu-On Chan, Ilias Diakonikolas, Rocco A Servedio and Xiaorui Sun  “Efficient density estimation via piecewise polynomial approximation”  In _Proceedings of the forty-sixth annual ACM symposium on Theory of computing_ , 2014, pp. 604–613
  * [CKMST21] Edith Cohen, Haim Kaplan, Yishay Mansour, Uri Stemmer and Eliad Tsfadia  “Differentially-private clustering of easy instances”  In _International Conference on Machine Learning_ , 2021, pp. 2049–2059  PMLR
  * [Das99] Sanjoy Dasgupta  “Learning mixtures of Gaussians”  In _40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039)_ , 1999, pp. 634–644  IEEE
  * [DHK23] John Duchi, Saminul Haque and Rohith Kuditipudi  “A Fast Algorithm for Adaptive Private Mean Estimation”  In _arXiv preprint arXiv:2301.07078_ , 2023
  * [DKMMN06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov and Moni Naor  “Our data, ourselves: Privacy via distributed noise generation”  In _Annual international conference on the theory and applications of cryptographic techniques_ , 2006, pp. 486–503  Springer
  * [DKS17] Ilias Diakonikolas, Daniel M Kane and Alistair Stewart  “Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures”  In _2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)_ , 2017, pp. 73–84  IEEE
  * [DL01] Luc Devroye and Gábor Lugosi  “Combinatorial methods in density estimation”  Springer Science & Business Media, 2001
  * [DL09] Cynthia Dwork and Jing Lei  “Differential privacy and robust statistics”  In _Proceedings of the forty-first annual ACM symposium on Theory of computing_ , 2009, pp. 371–380
  * [DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam Smith  “Calibrating noise to sensitivity in private data analysis”  In _Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3_ , 2006, pp. 265–284  Springer
  * [DMR18] Luc Devroye, Abbas Mehrabian and Tommy Reddad  “The total variation distance between high-dimensional Gaussians”  In _arXiv preprint arXiv:1810.08693_ , 2018
  * [DR+14] Cynthia Dwork and Aaron Roth  “The algorithmic foundations of differential privacy”  In _Foundations and Trends® in Theoretical Computer Science_ 9.3–4 Now Publishers, Inc., 2014, pp. 211–407
  * [DRV10] Cynthia Dwork, Guy N. Rothblum and Salil P. Vadhan  “Boosting and Differential Privacy”  In _2010 IEEE 51st Annual Symposium on Foundations of Computer Science_ , 2010, pp. 51–60
  * [FSO06] Jon Feldman, Rocco A Servedio and Ryan O’Donnell  “PAC learning axis-aligned mixtures of Gaussians with no separation assumption”  In _International Conference on Computational Learning Theory_ , 2006, pp. 20–34  Springer
  * [GDGK18] Quan Geng, Wei Ding, Ruiqi Guo and Sanjiv Kumar  “Truncated Laplacian mechanism for approximate differential privacy”  In _arXiv preprint arXiv:1810.00877_ Oct, 2018
  * [GH22] Kristian Georgiev and Samuel B Hopkins  “Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation”  In _arXiv preprint arXiv:2211.00724_ , 2022
  * [HK13] Daniel Hsu and Sham M Kakade  “Learning mixtures of spherical gaussians: moment methods and spectral decompositions”  In _Proceedings of the 4th conference on Innovations in Theoretical Computer Science_ , 2013, pp. 11–20
  * [HKM22] Samuel B Hopkins, Gautam Kamath and Mahbod Majid  “Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism”  In _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_ , 2022, pp. 1406–1417
  * [HKMN23] Samuel B Hopkins, Gautam Kamath, Mahbod Majid and Shyam Narayanan  “Robustness Implies Privacy in Statistical Estimation”  In _Proceedings of the 55th Annual ACM SIGACT Symposium on Theory of Computing_ , 2023
  * [HL18] Samuel B Hopkins and Jerry Li  “Mixture models, robustness, and sum of squares proofs”  In _Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing_ , 2018, pp. 1021–1034
  * [HP14] Moritz Hardt and Eric Price  “Sharp bounds for learning a mixture of two Gaussians”  In _ArXiv e-prints_ 1404, 2014
  * [KLSU19] Gautam Kamath, Jerry Li, Vikrant Singhal and Jonathan Ullman  “Privately learning high-dimensional distributions”  In _Conference on Learning Theory_ , 2019, pp. 1853–1902  PMLR
  * [KMS22] Gautam Kamath, Argyris Mouzakis and Vikrant Singhal  “New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma”  In _arXiv preprint arXiv:2205.08532_ , 2022
  * [KMSSU22] Gautam Kamath, Argyris Mouzakis, Vikrant Singhal, Thomas Steinke and Jonathan Ullman  “A private and computationally-efficient estimator for unbounded gaussians”  In _Conference on Learning Theory_ , 2022, pp. 544–572  PMLR
  * [KMV10] Adam Tauman Kalai, Ankur Moitra and Gregory Valiant  “Efficiently learning mixtures of two Gaussians”  In _Proceedings of the forty-second ACM symposium on Theory of computing_ , 2010, pp. 553–562
  * [KMV22] Pravesh Kothari, Pasin Manurangsi and Ameya Velingker  “Private robust estimation by stabilizing convex relaxations”  In _Conference on Learning Theory_ , 2022, pp. 723–777  PMLR
  * [KSS18] Pravesh K Kothari, Jacob Steinhardt and David Steurer  “Robust moment estimation and improved clustering via sum of squares”  In _Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing_ , 2018, pp. 1035–1046
  * [KSSU19] Gautam Kamath, Or Sheffet, Vikrant Singhal and Jonathan Ullman  “Differentially private algorithms for learning mixtures of separated gaussians”  In _Advances in Neural Information Processing Systems_ 32, 2019
  * [KV17] Vishesh Karwa and Salil Vadhan  “Finite sample differentially private confidence intervals”  In _arXiv preprint arXiv:1711.03908_ , 2017
  * [LKKO21] Xiyang Liu, Weihao Kong, Sham Kakade and Sewoong Oh  “Robust and differentially private mean estimation”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 3887–3901
  * [LKO22] Xiyang Liu, Weihao Kong and Sewoong Oh  “Differential privacy and robust statistics in high dimensions”  In _Conference on Learning Theory_ , 2022, pp. 1167–1246  PMLR
  * [LL22] Allen Liu and Jerry Li  “Clustering mixtures with almost optimal separation in polynomial time”  In _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_ , 2022, pp. 1248–1261
  * [LLM22] Allen Liu, Jerry Li and Ankur Moitra  “Robust Model Selection and Nearly-Proper Learning for GMMs”  In _Advances in Neural Information Processing Systems_ , 2022
  * [LM00] Beatrice Laurent and Pascal Massart  “Adaptive estimation of a quadratic functional by model selection”  In _Annals of Statistics_ JSTOR, 2000, pp. 1302–1338
  * [LM21] Allen Liu and Ankur Moitra  “Settling the robust learnability of mixtures of gaussians”  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , 2021, pp. 518–531
  * [LM22] Allen Liu and Ankur Moitra  “Learning gmms with nearly optimal robustness guarantees”  In _Conference on Learning Theory_ , 2022, pp. 2815–2895  PMLR
  * [LS17] Jerry Li and Ludwig Schmidt  “Robust and proper learning for mixtures of gaussians via systems of polynomial inequalities”  In _Conference on Learning Theory_ , 2017, pp. 1302–1382  PMLR
  * [MV10] Ankur Moitra and Gregory Valiant  “Settling the polynomial learnability of mixtures of gaussians”  In _2010 IEEE 51st Annual Symposium on Foundations of Computer Science_ , 2010, pp. 93–102  IEEE
  * [NRS07] Kobbi Nissim, Sofya Raskhodnikova and Adam Smith  “Smooth sensitivity and sampling in private data analysis”  In _Proceedings of the thirty-ninth annual ACM symposium on Theory of computing_ , 2007, pp. 75–84
  * [Pea94] Karl Pearson  “Contributions to the Mathematical Theory of Evolution”  In _Philosophical Transactions of the Royal Society of London_ 185, 1894, pp. 71–110
  * [RV17] Oded Regev and Aravindan Vijayaraghavan  “On learning mixtures of well-separated gaussians”  In _2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)_ , 2017, pp. 85–96  IEEE
  * [SK01] Arora Sanjeev and Ravi Kannan  “Learning mixtures of arbitrary gaussians”  In _Proceedings of the thirty-third annual ACM symposium on Theory of computing_ , 2001, pp. 247–257
  * [TCKMS22] Eliad Tsfadia, Edith Cohen, Haim Kaplan, Yishay Mansour and Uri Stemmer  “Friendlycore: Practical differentially private aggregation”  In _International Conference on Machine Learning_ , 2022, pp. 21828–21863  PMLR
  * [VW04] Santosh Vempala and Grant Wang  “A spectral algorithm for learning mixture models”  In _Journal of Computer and System Sciences_ 68.4 Elsevier, 2004, pp. 841–860
  * [WR06] Christopher KI Williams and Carl Edward Rasmussen  “Gaussian processes for machine learning”  MIT press Cambridge, MA, 2006
  * [WX18] Xuan Wu and Changzhi Xie  “Improved Algorithms for Properly Learning Mixture of Gaussians”  In _National Conference of Theoretical Computer Science_ , 2018, pp. 8–26  Springer
  * [Yat85] Yannis G Yatracos  “Rates of convergence of minimum distance estimators and Kolmogorov’s entropy”  In _The Annals of Statistics_ 13.2 Institute of Mathematical Statistics, 1985, pp. 768–774

##  Appendix A Standard Facts

######  Fact A.1.

Let $X_{1},X_{2},Y_{1},Y_{2}$ be random variables such that $X_{1},X_{2}$
(resp. $Y_{1},Y_{2}$) are independent. Then
$d_{\mathrm{TV}}\left({(X_{1},X_{2})},{(Y_{1},Y_{2})}\right)\leq
d_{\mathrm{TV}}\left({X_{1}},{Y_{1}}\right)+d_{\mathrm{TV}}\left({X_{2}},{Y_{2}}\right)$.

######  Fact A.2.

Let $X,Y$ be random variables. For any measurable function $f$,
$d_{\mathrm{TV}}\left({f(X)},{f(Y)}\right)\leq
d_{\mathrm{TV}}\left({X},{Y}\right)$.

The equality in the following fact is standard; for example, see Equation 2.3
in [WR06]. For the inequality, see the proof of Lemma 2.9 in [ABHLMP20].

######  Fact A.3.

Let $\mu_{1},\mu_{2}\in\mathbb{R}^{d}$ and $\Sigma_{1},\Sigma_{2}\succ 0$.
Then

$\displaystyle
D_{\mathrm{KL}}\left({\mathcal{N}(\mu_{1},\Sigma_{1})}\parallel{\mathcal{N}(\mu_{2},\Sigma_{2})}\right)$
$\displaystyle=\frac{1}{2}\big{[}\operatorname{tr}(\Sigma_{2}^{-1}\Sigma_{1}-I)+(\mu_{2}-\mu_{1})^{\top}\Sigma_{2}^{-1}(\mu_{2}-\mu_{1})-\ln\det(\Sigma_{2}^{-1}\Sigma_{1})\big{]}.$

Moreover, suppose that all the eigenvalues of
$\Sigma_{2}^{-1/2}\Sigma_{1}\Sigma_{2}^{-1/2}$ are at least $\frac{1}{2}$.
Then

$\displaystyle
D_{\mathrm{KL}}\left({\mathcal{N}(\mu_{1},\Sigma_{1})}\parallel{\mathcal{N}(\mu_{2},\Sigma_{2})}\right)$
$\displaystyle\leq\frac{1}{2}\big{[}\|\Sigma_{2}^{-1/2}\Sigma_{1}\Sigma_{2}^{-1/2}-I\|_{F}^{2}+(\mu_{2}-\mu_{1})^{\top}\Sigma_{2}^{-1}(\mu_{2}-\mu_{1})\big{]}.$

######  Lemma A.4 (Pinsker’s Inequality).

Let $P$ and $Q$ be two distributions for which KL-divergence is defined. Then
$d_{\mathrm{TV}}\left({P},{Q}\right)\leq\sqrt{0.5D_{\mathrm{KL}}\left({P}\parallel{Q}\right)}$.

######  Lemma A.5 ([LM00], Lemma 1).

Let $g_{1},\ldots,g_{k}$ be i.i.d. $\mathcal{N}(0,1)$ random variables. Then

$\mathbb{P}\left[\sum_{i=1}^{k}g_{i}^{2}\geq k+2\sqrt{kt}+2t\right]\leq
e^{-t}.$

######  Lemma A.6 ([AL22], Lemma D.2).

Let $\mu_{1},\mu_{2}\in\mathbb{R}^{d}$ and let $\Sigma_{1},\Sigma_{2}$ be
full-rank $d\times d$ PSD matrices. Let
$Y\sim\mathcal{N}(\mu_{1},\Sigma_{1})$. Then

$\displaystyle\mathcal{L}_{{\mathcal{N}(\mu_{1},\Sigma_{1})}\parallel{\mathcal{N}(\mu_{2},\Sigma_{2})}}(Y)$
$\displaystyle\leq
D_{\mathrm{KL}}\left({\mathcal{N}(\mu_{1},\Sigma_{1})}\parallel{\mathcal{N}(\mu_{2},\Sigma_{2})}\right)$
(A.1)
$\displaystyle+2\|\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}-I_{d}\|_{F}\cdot\sqrt{\ln(2/\delta)}+2\|\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}-I_{d}\|\cdot\ln(2/\delta)$
$\displaystyle+\|\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}\|\cdot\|\Sigma_{1}^{-1/2}\cdot(\mu_{2}-\mu_{1})\|_{2}\cdot\sqrt{2\ln(2/\delta)}$

with probability at least $1-\delta$.

######  Fact A.7.

For $x\in(0,\ln(2))$, we have $e^{x}\leq 1+2x$

###### Proof.

Consider the function $f(x)=1+2x-e^{x}$. Then $f^{\prime\prime}(x)=-e^{x}$ so
$f$ is concave. Note that $f(0)=0$ and $f(\ln(2))=1+2\ln(2)-2>0$ so $f(x)\geq
0$ for $x\in[0,\ln(2)]$ (by concavity). ∎

######  Lemma A.8 ([AL22], Lemma 3.2).

Let $\mathcal{S}^{d}$ be the set of all $d\times d$ positive definite
matrices. For $A,B\in\mathcal{S}^{d}$ let
$\operatorname{dist}(A,B)=\max\\{\|A^{-1/2}BA^{-1/2}-I\|,\|B^{-1/2}AB^{-1/2}-I\|\\}$.
Then $(\mathcal{S}^{d},\operatorname{dist})$ is a semimetric space which
satisfies a $(3/2)$-approximate $1$-restricted triangle inequality.

######  Fact A.9.

Let $\Sigma_{1},\Sigma_{2}$ be $d\times d$ positive-definite matrices. Then
$\Sigma_{2}^{-1/2}\Sigma_{1}\Sigma_{2}^{-1/2}$ and
$\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}$ have the same spectrum.

###### Proof.

Suppose that $x\in\mathbb{R}^{d}$ is an eigenvector of
$\Sigma_{2}^{-1/2}\Sigma_{1}\Sigma_{2}^{-1/2}$ with eigenvalue $\lambda$. Let
$y=\Sigma_{1}^{1/2}\Sigma_{2}^{-1/2}x$. Then

$\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}y=\Sigma_{1}^{1/2}\Sigma_{2}^{-1/2}\left(\Sigma_{2}^{-1/2}\Sigma_{1}\Sigma_{2}^{-1/2}\right)x=\lambda\Sigma_{1}^{1/2}\Sigma_{2}^{-1/2}x=\lambda
y.$

In other words, $y$ is an eigenvector of
$\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}$ with eigenvalue $\lambda$. ∎

##  Appendix B TV Distance of Gaussian Distributions

In this section, we prove the following theorem. *

Our proof makes use of the following two theorems from [DMR18].

######  Theorem B.1 ([DMR18], Theorem 1.1).

Let $\mu\in\mathbb{R}^{d}$, $\Sigma_{1}$, $\Sigma_{2}\in\mathcal{S}^{d}$, The
total variation distance between Gaussians with the same mean is bounded by

$\frac{\min\left\\{1,\|\Sigma_{1}^{-1/2}\Sigma_{2}\Sigma_{1}^{-1/2}-I_{d}\|_{F}\right\\}}{100}\leq
d_{\mathrm{TV}}\left({\mathcal{N}(\mu,\Sigma_{1})},{\mathcal{N}(\mu,\Sigma_{2})}\right)$

######  Theorem B.2 ([DMR18], Theorem 1.3).

The total variation distance between one-dimensional Gaussians is bounded by

$\frac{1}{200}\min\left\\{1,\max\left\\{\frac{|\sigma_{1}^{2}-\sigma_{2}^{2}|}{\sigma_{1}^{2}},\frac{40|\mu_{1}-\mu_{2}|}{\sigma_{1}}\right\\}\right\\}\leq
d_{\mathrm{TV}}\left({\mathcal{N}(\mu_{1},\sigma_{1}^{2})},{\mathcal{N}(\mu_{2},\sigma_{2}^{2})}\right)\leq\frac{3|\sigma_{1}^{2}-\sigma_{2}^{2}|}{2\sigma_{1}^{2}}+\frac{|\mu_{1}-\mu_{2}|}{2\sigma_{1}}.$

######  Lemma B.3.

$d_{\mathrm{TV}}\left({\mathcal{N}(0,\Sigma_{1})},{\mathcal{N}(0,\Sigma_{2})}\right)\leq
2\cdot
d_{\mathrm{TV}}\left({\mathcal{N}(\mu_{1},\Sigma_{1})},{\mathcal{N}(\mu_{2},\Sigma_{2})}\right)$.

###### Proof.

Let $X_{1},X_{2},Y_{1},Y_{2}$ be independent random variables where
$X_{1},X_{2}\sim\mathcal{N}(\mu_{1},\Sigma_{1})$ and
$Y_{1},Y_{2}\sim\mathcal{N}(\mu_{2},\Sigma_{2})$. Applying Fact A.1 gives

$\displaystyle d_{\mathrm{TV}}\left({(X_{1},X_{2})},{(Y_{1},Y_{2})}\right)$
$\displaystyle\leq
d_{\mathrm{TV}}\left({X_{1}},{Y_{1}}\right)+d_{\mathrm{TV}}\left({X_{2}},{Y_{2}}\right)$
$\displaystyle=d_{\mathrm{TV}}\left({\mathcal{N}(\mu_{1},\Sigma_{1})},{\mathcal{N}(\mu_{2},\Sigma_{2})}\right)+d_{\mathrm{TV}}\left({\mathcal{N}(\mu_{1},\Sigma_{1})},{\mathcal{N}(\mu_{2},\Sigma_{2})}\right)$
$\displaystyle=2\cdot
d_{\mathrm{TV}}\left({\mathcal{N}(\mu_{1},\Sigma_{1})},{\mathcal{N}(\mu_{2},\Sigma_{2})}\right).$

Now, let $X=(X_{1},X_{2})$ and $Y=(Y_{1},Y_{2})$, and define the function
$f(X)=f(X_{1},X_{2})=(X_{1}-X_{2})/\sqrt{2}$. Then by applying Fact A.2 we
have

$d_{\mathrm{TV}}\left({f(X_{1},X_{2})},{f(Y_{1},Y_{2})}\right)\leq
d_{\mathrm{TV}}\left({(X_{1},X_{2})},{(Y_{1},Y_{2})}\right)\leq 2\cdot
d_{\mathrm{TV}}\left({\mathcal{N}(\mu_{1},\Sigma_{1})},{\mathcal{N}(\mu_{2},\Sigma_{2})}\right).$

Note that if $X_{1},X_{2}\sim\mathcal{N}(\mu_{1},\Sigma_{1})$ then
$f(X)\sim\mathcal{N}(0,\Sigma_{1})$. Therefore we have

$d_{\mathrm{TV}}\left({\mathcal{N}(0,\Sigma_{1})},{\mathcal{N}(0,\Sigma_{2})}\right)\leq
2\cdot
d_{\mathrm{TV}}\left({\mathcal{N}(\mu_{1},\Sigma_{1})},{\mathcal{N}(\mu_{2},\Sigma_{2})}\right),$

as required. ∎

######  Lemma B.4.

Let $\mu\in\mathbb{R}^{d}$. If
$d_{\mathrm{TV}}\left({\mathcal{N}(0,I_{d})},{\mathcal{N}(\mu,I_{d})}\right)\leq
3\alpha<1/200$ then $\|\mu\|_{2}\leq 15\alpha$.

###### Proof.

Let $g_{1}\sim\mathcal{N}(0,I_{d})$, $g_{2}\sim\mathcal{N}(\mu,I_{d})$ and
$v=\mu/\|\mu\|_{2}$. Note that $v^{\top}g_{1}\sim\mathcal{N}(0,1)$ and
$v^{\top}g_{2}\sim\mathcal{N}(\|\mu\|_{2},1)$. Applying Fact A.2 (with
$f(x)=v^{\top}x$) we have

$d_{\mathrm{TV}}\left({\mathcal{N}(0,1)},{\mathcal{N}(\|\mu\|_{2},1)}\right)\leq
d_{\mathrm{TV}}\left({\mathcal{N}(0,I_{d})},{\mathcal{N}(\mu,I_{d})}\right)\leq
3\alpha<1/200.$

Applying Theorem B.2 on the left side, we have

$\frac{1}{200}\min\left\\{1,40\|\mu\|_{2}\right\\}\leq
d_{\mathrm{TV}}\left({\mathcal{N}(0,1)},{\mathcal{N}(\|\mu\|_{2},1)}\right)\leq
d_{\mathrm{TV}}\left({\mathcal{N}(0,I_{d})},{\mathcal{N}(\mu,I_{d})}\right)\leq
3\alpha<1/200.$

Note that this implies $\min\left\\{1,40\|\mu\|_{2}\right\\}=40\|\mu\|_{2}<1$.
Therefore we conclude that $\|\mu\|_{2}\leq 15\alpha$. ∎

######  Lemma B.5.

Let $\mu_{1},\mu_{2}\in\mathbb{R}^{d}$ and $\Sigma_{1},\Sigma_{2}$ be full-
rank $d\times d$ positive-definite matrices. Suppose that

$d_{\mathrm{TV}}\left({\mathcal{N}(\mu_{1},\Sigma_{1})},{\mathcal{N}(\mu_{2},\Sigma_{2})}\right)\leq\alpha<\frac{1}{600}.$

Then (i) $\|\Sigma_{1}^{-1/2}\Sigma_{2}\Sigma_{1}^{-1/2}-I_{d}\|_{F}\leq
200\alpha$ and (ii) $\|\Sigma_{1}^{-1/2}(\mu_{1}-\mu_{2})\|_{2}\leq 15\alpha$.

###### Proof.

(i) Starting from the assumption

$d_{\mathrm{TV}}\left({\mathcal{N}(\mu_{1},\Sigma_{1})},{\mathcal{N}(\mu_{2},\Sigma_{2})}\right)\leq\alpha<\frac{1}{600},$

we apply Lemma B.3 to obtain

$d_{\mathrm{TV}}\left({\mathcal{N}(0,\Sigma_{1})},{\mathcal{N}(0,\Sigma_{2})}\right)\leq
2\alpha<\frac{1}{300}.$

Applying Theorem B.1 gives

$\min\left\\{1,\|\Sigma_{1}^{-1/2}\Sigma_{2}\Sigma_{1}^{-1/2}-I_{d}\|_{F}\right\\}\leq
100\cdot
d_{\mathrm{TV}}\left({\mathcal{N}(0,\Sigma_{1})},{\mathcal{N}(0,\Sigma_{2})}\right)\leq
200\alpha<\frac{1}{3}.$

Note that the inequality implies that
$\min\left\\{1,\|\Sigma_{1}^{-1/2}\Sigma_{2}\Sigma_{1}^{-1/2}-I_{d}\|_{F}\right\\}=\|\Sigma_{1}^{-1/2}\Sigma_{2}\Sigma_{1}^{-1/2}-I_{d}\|_{F}$.
We conclude that

$\|\Sigma_{1}^{-1/2}\Sigma_{2}\Sigma_{1}^{-1/2}-I_{d}\|_{F}\leq 200\alpha.$

This proves the first assertion.

(ii) By the triangle inequality, we have

$\displaystyle
d_{\mathrm{TV}}\left({\mathcal{N}(\mu_{1},\Sigma_{1})},{\mathcal{N}(\mu_{2},\Sigma_{1})}\right)$
$\displaystyle\leq
d_{\mathrm{TV}}\left({\mathcal{N}(\mu_{1},\Sigma_{1})},{\mathcal{N}(\mu_{2},\Sigma_{2})}\right)+d_{\mathrm{TV}}\left({\mathcal{N}(\mu_{2},\Sigma_{1})},{\mathcal{N}(\mu_{2},\Sigma_{2})}\right)$
$\displaystyle=d_{\mathrm{TV}}\left({\mathcal{N}(\mu_{1},\Sigma_{1})},{\mathcal{N}(\mu_{2},\Sigma_{2})}\right)+d_{\mathrm{TV}}\left({\mathcal{N}(0,\Sigma_{1})},{\mathcal{N}(0,\Sigma_{2})}\right).$

Our hypothesis is that

$d_{\mathrm{TV}}\left({\mathcal{N}(\mu_{1},\Sigma_{1})},{\mathcal{N}(\mu_{2},\Sigma_{2})}\right)\leq\alpha<\frac{1}{600},$

which, by Lemma B.3, implies that

$d_{\mathrm{TV}}\left({\mathcal{N}(0,\Sigma_{1})},{\mathcal{N}(0,\Sigma_{2})}\right)\leq
2\alpha<\frac{1}{300}.$

Thus, we have

$d_{\mathrm{TV}}\left({\mathcal{N}(\mu_{1},\Sigma_{1})},{\mathcal{N}(\mu_{2},\Sigma_{1})}\right)\leq
3\alpha<\frac{1}{200}.$

Furthermore, since bijective mappings preserve the total variation distance,
we have

$\displaystyle
d_{\mathrm{TV}}\left({\mathcal{N}(\mu_{1},\Sigma_{1})},{\mathcal{N}(\mu_{2},\Sigma_{1})}\right)$
$\displaystyle=d_{\mathrm{TV}}\left({\mathcal{N}(\Sigma_{1}^{-1/2}\mu_{1},I_{d})},{\mathcal{N}(\Sigma_{1}^{-1/2}\mu_{2},I_{d})}\right)$
$\displaystyle=d_{\mathrm{TV}}\left({\mathcal{N}(0,I_{d})},{\mathcal{N}(\Sigma_{1}^{-1/2}(\mu_{1}-\mu_{2}),I_{d})}\right).$

Finally, applying Lemma B.4 gives
$\|\Sigma_{1}^{-1/2}(\mu_{1}-\mu_{2})\|_{2}\leq 15\alpha$. ∎

###### Proof of Theorem 1.4.

The lower bound follows from Lemma B.5.

The upper bound is a standard application of Pinsker’s Inequality but we
provide the proof for completeness. By Lemma B.5(i) the eigenvalues of
$\Sigma_{2}^{-1/2}\Sigma_{1}\Sigma_{2}^{-1/2}$ are strictly larger than $1/2$
(note we swapped the indices in the application of Lemma B.5). Therefore,
using Fact A.3 we know that

$D_{\mathrm{KL}}\left({\mathcal{N}(\mu_{1},\Sigma_{1})}\parallel{\mathcal{N}(\mu_{2},\Sigma_{2})}\right)\leq\frac{1}{2}\big{[}\|\Sigma_{2}^{-1/2}\Sigma_{1}\Sigma_{2}^{-1/2}-I\|_{F}^{2}+(\mu_{2}-\mu_{1})^{\top}\Sigma_{2}^{-1}(\mu_{2}-\mu_{1})\big{]}.$

Using Pinsker’s inequality (Lemma A.4) and the known fact
$\|\mu\|_{\Sigma}=\|\Sigma^{-1/2}\mu\|_{2}=\sqrt{(\mu^{T}\Sigma^{-1}\mu)}$ we
have

$d_{\mathrm{TV}}\left({\mathcal{N}(\mu_{1},\Sigma_{1})},{\mathcal{N}(\mu_{2},\Sigma_{2})}\right)\leq\frac{1}{2}\sqrt{\big{[}\|\Sigma_{2}^{-1/2}\Sigma_{1}\Sigma_{2}^{-1/2}-I\|_{F}^{2}+(\mu_{2}-\mu_{1})^{\top}\Sigma_{2}^{-1}(\mu_{2}-\mu_{1})\big{]}}\leq\frac{\Delta}{\sqrt{2}}$

which concludes the proof. ∎

##  Appendix C Standard Facts about Differential Privacy

######  Definition C.1.

Let $\mathcal{D}_{1},\mathcal{D}_{2}$ be two continuous distributions defined
on $\mathbb{R}^{d}$ and let $f_{1},f_{2}$ be the respective density functions.
We use
$\mathcal{L}_{{\mathcal{D}_{1}}\parallel{\mathcal{D}_{2}}}\colon\mathbb{R}^{d}\to\mathbb{R}$
to denote the logarithm of the likelihood ratio, i.e. for any
$x\in\mathbb{R}^{d}$,

$\mathcal{L}_{{\mathcal{D}_{1}}\parallel{\mathcal{D}_{2}}}(x)\coloneqq\ln\frac{f_{1}(x)}{f_{2}(x)}.$
(C.1)

Below definition has $D,D^{\prime}$ which are different in single individual
data and function f can capture the change in magnitude at the worst case.

######  Definition C.2 ($L_{1}$-Sensitivity ([DR+14], Definition 3.1)).

The $L_{1}$-sensitivity of a function
$f\colon\mathcal{X}^{n}\to\mathbb{R}^{k}$ is defined as:

$\Delta(f)=\max_{D,D^{\prime}\in\mathcal{X}^{n}\,:\,d_{H}(D,D^{\prime})\leq
1}||f(D)-f(D^{\prime})||_{1}$

where $d_{H}$ is Hamming distance identified in Definition 1.5

######  Definition C.3 ($L_{2}$-Sensitivity ([DR+14], Definition 3.8)).

The $L_{2}$-sensitivity of a function
$f\colon\mathcal{X}^{n}\to\mathbb{R}^{k}$ is defined as:

$\Delta_{2}(f)=\max_{D,D^{\prime}\in\mathcal{X}^{n}\,:\,d_{H}(D,D^{\prime})\leq
1}||f(D)-f(D^{\prime})||_{2}$

where $d_{H}$ is Hamming distance identified in Definition 1.5

The Gaussian Mechanism with parameter $\sigma$ adds noise scaled to
$\mathcal{N}(0,\sigma^{2})$ to each of the $d$ components of the output.

######  Theorem C.4 (Gaussian Mechanism ([DR+14], Theorem 3.22)).

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

The amount of noise necessary to ensure differential privacy for a given
function depends on the sensitivity of the function. In other words, we can
guarantee privacy using additive noise if the sensitivity of the function is
bounded. The sensitivity of a function reflects the amount the function’s
output will change when its input changes.

######  Definition C.5 (Truncated Laplace distribution).

It is denoted by $\operatorname{TLap}(\Delta,\varepsilon,\delta)$ whose
probability density function is given by

$f_{\operatorname{TLap}(\Delta,\varepsilon,\delta)}(x)\coloneqq\begin{cases}Be^{-|x|/\lambda}&x\in[-A,A]\\\
0&x\notin[-A,A]\end{cases},$

where $\lambda=\frac{\Delta}{\varepsilon}$,
$A=\frac{\Delta}{\varepsilon}\ln\left(1+\frac{e^{\varepsilon}-1}{2\delta}\right)$,
$B=\frac{1}{2\lambda(1-e^{-A/\lambda})}$.

######  Theorem C.6 ([GDGK18], Theorem 1).

Suppose that $q\colon\mathcal{X}^{n}\to\mathbb{R}$ is a function with
$L_{1}$-sensitivity $\Delta$. Then the mechanism $q(x)+Y$ where
$Y\sim\operatorname{TLap}(\Delta,\varepsilon,\delta)$ is
$(\varepsilon,\delta)$-DP.

######  Theorem C.7 (Advanced Composition [DRV10]).

Let $\mathcal{D}_{1},\ldots,\mathcal{D}_{k}$ and
$\mathcal{D}_{1}^{\prime},\ldots,\mathcal{D}_{k}^{\prime}$ be probability
densities such that $\mathcal{D}_{j},\mathcal{D}_{j}^{\prime}$ are
$(\varepsilon,\delta)$-indistinguishable for all $j\in[k]$. Let
$\mathcal{D}=(\mathcal{D}_{1},\ldots,\mathcal{D}_{k})$ and
$\mathcal{D}^{\prime}=(\mathcal{D}_{1}^{\prime},\ldots,\mathcal{D}_{k}^{\prime})$.
Then for every $\delta^{\prime}>0$, $\mathcal{D},\mathcal{D}^{\prime}$ are
$(\varepsilon^{\prime},k\delta+\delta^{\prime})$-indistinguishable for

$\varepsilon^{\prime}=\sqrt{2k\ln(1/\delta^{\prime})\varepsilon}+k\varepsilon(e^{\varepsilon}-1).$

######  Lemma C.8.

Let $\mathcal{D}_{1},\ldots,\mathcal{D}_{k}$ and
$\mathcal{D}^{\prime}_{1},\ldots,\mathcal{D}^{\prime}_{k}$ denote probability
distributions on a space $\mathcal{X}$. Suppose that for all $j\in[k]$,
$\mathcal{D}_{j}$ and $\mathcal{D}^{\prime}_{j}$ are
$(\varepsilon,\delta)$-indistinguishable. Let $w=(w_{1},\ldots,w_{k})$ be a
probability vector, i.e. $w_{j}\geq 0$ for $j\in[k]$ and
$\sum_{j\in[k]}w_{j}=1$. Then the probability distributions
$\sum_{j\in[k]}w_{j}\mathcal{D}_{j}$ and
$\sum_{j\in[k]}w_{j}\mathcal{D}_{j}^{\prime}$ are
$(\varepsilon,\delta)$-indistinguishable.

###### Proof.

Let $\mathcal{D}=\sum_{j\in[k]}w_{j}\mathcal{D}_{j}$ and
$\mathcal{D}^{\prime}=\sum_{j\in[k]}w_{j}\mathcal{D}^{\prime}_{j}$. Fix a set
$S\subseteq\mathcal{X}$. Then

$\mathbb{P}_{x\sim\mathcal{D}}[x\in
S]=\sum_{j=1}^{k}w_{j}\mathbb{P}_{x\sim\mathcal{D}_{j}}[x\in
S]\leq\sum_{j=1}^{k}w_{j}\left[e^{\varepsilon}\cdot\mathbb{P}_{x\in\mathcal{D}_{j}^{\prime}}[x\in
S]+\delta\right]=e^{\varepsilon}\cdot\mathbb{P}_{x\sim\mathcal{D}^{\prime}}[x\in
S]+\delta,$

as required. ∎

######  Lemma C.9 ([AL22], Lemma 2.10).

Let $\mathcal{D}_{1},\mathcal{D}_{2}$ be continuous distributions defined on
$\mathbb{R}^{d}$. If

$\mathbb{P}_{Y\sim\mathcal{D}_{1}}\left[\mathcal{L}_{{\mathcal{D}_{1}}\parallel{\mathcal{D}_{2}}}(Y)\geq\varepsilon\right]\leq\delta\quad\text{and}\quad\mathbb{P}_{Y\sim\mathcal{D}_{2}}\left[\mathcal{L}_{{\mathcal{D}_{2}}\parallel{\mathcal{D}_{1}}}(Y)\geq\varepsilon\right]\leq\delta$

then $\mathcal{D}_{1},\mathcal{D}_{2}$ are
$(\varepsilon,\delta)$-indistinguishable.

##  Appendix D Missing Proofs from Section 2

###  D.1 Proof of Theorem 2.3

###### Proof of Theorem 2.3.

Proof of privacy. Let $D$ and $D^{\prime}$ be two neighbouring datasets and
let $\mathcal{A}$ denote the non-private algorithm specified in Algorithm 1.
Note that the $Q$ computed in Line 4 has sensitivity less than $\frac{2}{t}$.
Since we use the Truncated Laplace mechanism in Line 7, we have (by Theorem
C.6)

$\mathbb{P}\left[\mathcal{A}(D)=\perp\right]\leq
e^{\varepsilon}\mathbb{P}\left[\mathcal{A}(D^{\prime})=\perp\right]+\delta$
(D.1)

We now show that for any $T\subseteq\mathcal{Y}$, we have

$\displaystyle\mathbb{P}\left[\mathcal{A}(D)\in T\right]$ $\displaystyle\leq
e^{2\varepsilon}\mathbb{P}\left[\mathcal{A}(D^{\prime})\in
T\right]+3e^{\varepsilon}\delta\quad\text{and}$ (D.2)
$\displaystyle\mathbb{P}\left[\mathcal{A}(D)\in T\cup\\{\perp\\}\right]$
$\displaystyle\leq e^{2\varepsilon}\mathbb{P}\left[\mathcal{A}(D^{\prime})\in
T\cup\\{\perp\\}\right]+4e^{\varepsilon}\delta$ (D.3)

which establishes that Algorithm 1 is $(\varepsilon,\delta)$-DP. To this end,
we consider two different cases.

#### Case 1: $Q<0.8$.

In this case,
$\widetilde{Q}<0.8+\frac{2}{t\varepsilon}\ln\left(1+\frac{e^{\varepsilon}-1}{2\delta}\right)$
with probability $1$ so $\mathbb{P}\left[\mathcal{A}(D)=\perp\right]=1$. We
now verify that Eq. (D.2) and Eq. (D.3) hold. For any $T\subseteq\mathcal{Y}$,
we have $\mathbb{P}\left[\mathcal{A}(D)\in T\right]=0$ so Eq. (D.2) is
trivially satisfied. To check Eq. (D.3) holds, we apply Eq. (D.1) to see that

$\mathbb{P}\left[\mathcal{A}(D)\in
T\cup\\{\perp\\}\right]=\mathbb{P}\left[\mathcal{A}(D)=\perp\right]\leq
e^{\varepsilon}\mathbb{P}\left[\mathcal{A}(D^{\prime})=\perp\right]+\delta\leq
e^{\varepsilon}\mathbb{P}\left[\mathcal{A}(D^{\prime})\in
T\cup\\{\perp\\}\right]+\delta.$

#### Case 2: $Q\geq 0.8$.

Let $Y_{1},\ldots,Y_{t}$ and $Y_{1}^{\prime},\ldots,Y_{t}^{\prime}$ be the
outputs in Line 2 assuming the dataset is $D,D^{\prime}$, respectively. Let
$j,j^{\prime}$ be the output of Line 8 assuming the dataset is $D,D^{\prime}$,
respectively. Next, we show that
$\operatorname{dist}(Y_{j},Y_{j}^{\prime})\leq r$.

Let $S=\\{\ell\in[t]\,:\,\operatorname{dist}(Y_{j},Y_{\ell})\leq r/2z\\}$ and
$S^{\prime}=\\{\ell\in[t]\,:\,\operatorname{dist}(Y_{j}^{\prime},Y_{\ell}^{\prime})\leq
r/2z\\}$. We know that $|S|>0.6t$ and $|S^{\prime}|>0.6t$ (by definition of
$j$ in Line 8). By the inclusion-exclusion principle, we have $|S\cap
S^{\prime}|=|S|+|S^{\prime}|-|S\cup S^{\prime}|>0.6t+0.6t-t=0.2t$. Thus, if
$t\geq 5$, we have $|S\cap S^{\prime}|>1$ and since $|S\cap S^{\prime}|$ is an
integer, we must have $|S\cap S^{\prime}|\geq 2$. Since $D,D^{\prime}$ differ
only in a single datapoint, there is some $\ell\in S\cap S^{\prime}$ such that
$Y_{\ell}=Y_{\ell}^{\prime}$. Thus, we conclude that

$\operatorname{dist}(Y_{j},Y_{j}^{\prime})\leq\operatorname{dist}(Y_{j},Y_{\ell})+\operatorname{dist}(Y_{\ell},Y_{j}^{\prime})\leq
z\cdot(r/2z+r/2z)=r,$

where in the final inequality, we used that $\operatorname{dist}$ is a
$z$-approximate $r$-restricted triangle inequality and that
$\operatorname{dist}(Y_{j},Y_{\ell}),\operatorname{dist}(Y_{\ell},Y_{j}^{\prime})\leq
r$.

We are now ready to verify that Eq. (D.2) and Eq. (D.3) hold. Let
$\mathcal{M}$ denote the mechanism described in Algorithm 1. Fix any
$T\subseteq\mathcal{Y}$. Then we have

$\displaystyle\mathbb{P}\left[\mathcal{M}(D)\in T\right]$
$\displaystyle=\mathbb{P}\left[\mathcal{M}(D)\neq\perp\right]\mathbb{P}\left[\mathcal{B}(Y_{j})\in
T\right]$
$\displaystyle\leq(e^{\varepsilon}\mathbb{P}\left[\mathcal{M}(D^{\prime})\neq\perp\right]+\delta)(e^{\varepsilon}\mathbb{P}\left[\mathcal{B}(Y_{j^{\prime}}^{\prime})\in
T\right]+\delta)$
$\displaystyle=(e^{2\varepsilon}\mathbb{P}\left[\mathcal{M}(D^{\prime})\neq\perp\right]\mathbb{P}\left[\mathcal{B}(Y_{j^{\prime}}^{\prime})\in
T\right]+2e^{\varepsilon}\delta+\delta^{2}$ $\displaystyle\leq
e^{2\varepsilon}\mathbb{P}\left[\mathcal{M}(D)\in
T\right]+3e^{\varepsilon}\delta$

where in first inequality we used the fact that $\mathcal{B}$ is a
$(r,\varepsilon,\delta)$-masking mechanism, which satisfies Eq. (D.2). Next,
we also have

$\displaystyle\mathbb{P}\left[\mathcal{M}(D)\in\\{\perp\\}\cup T\right]$
$\displaystyle=\mathbb{P}\left[\mathcal{M}(D)=\perp\right]+\mathbb{P}\left[\mathcal{M}(D)\in
T\right]$ $\displaystyle\leq
e^{\varepsilon}\mathbb{P}\left[\mathcal{M}(D^{\prime})=\perp\right]+\delta+e^{2\varepsilon}\mathbb{P}\left[\mathcal{M}(D^{\prime})\in
T\right]+3e^{\varepsilon}\delta$ $\displaystyle\leq
e^{2\varepsilon}\mathbb{P}\left[\mathcal{M}(D^{\prime})\in\\{\perp\\}\cup
T\right]+4e^{\varepsilon}\delta.$

This completes the proof of privacy.

Proof of utility. We divide the proof into two parts.

  1. 1.

First, we show that $\widetilde{Y}$ (the noisy output) concentrates around
$Y^{*}$.

  2. 2.

Second, we show that Algorithm 1 does not fail in Line 7.

For the first part, We know that $\mathcal{B}$ is $(\frac{\alpha}{2z},\beta)$
concentrated. Furthermore, $\forall i\in[t]$, $Y_{i}$ satisfies
$\operatorname{dist}(Y^{*},Y_{i})<\frac{\alpha}{2z}$. we have

$\displaystyle\mathbb{P}[\operatorname{dist}(\widetilde{Y},Y^{*})>\frac{\alpha}{2}+\frac{\alpha}{2}]$
$\displaystyle\leq\mathbb{P}[z\cdot\operatorname{dist}(\widetilde{Y},Y_{j})+z\cdot\operatorname{dist}(Y_{j},Y^{*})>\frac{\alpha}{2}+\frac{\alpha}{2}]$
$\displaystyle\leq\mathbb{P}[\operatorname{dist}(\widetilde{Y},{Y}_{j})+\operatorname{dist}({Y}_{j},F^{*})>\frac{\alpha}{2z}+\frac{\alpha}{2z}]$
$\displaystyle\leq\mathbb{P}[\operatorname{dist}(\widetilde{Y},{Y}_{j})>\frac{\alpha}{2z}]+\mathbb{P}[\operatorname{dist}({Y}_{j},Y^{*})>\frac{\alpha}{2z}]$
$\displaystyle\leq\beta+0\leq\beta,$

where the first inequality follows from the $r$-restricted $z$-approximate
triangle inequality 3 (since $\alpha/2z<r/4z^{2}$ by assumption), and the
first part of the last inequality follows the concentration of the masking
mechanism. We get
$\mathbb{P}[\operatorname{dist}(\widetilde{Y},{Y}_{j})>\frac{\alpha}{2z}]=\beta$,
because $\widetilde{Y}$ is just a masked version of ${Y}_{j}$. Also
$\mathbb{P}[\operatorname{dist}({Y}_{j},Y^{*})>\frac{\alpha}{2z}]=0$, because
$Y_{j}$ is selected from $Y_{i}$’s, and none of them located in a distance
larger than $\frac{\alpha}{2z}$ from ${Y}^{*}$ based on our assumption.

For the second part, we start by guaranteeing that $Q$ in Line 4 equals to 1.
For that we need to ensure that for all $i,j\in[t]$,
$\operatorname{dist}(Y_{i},Y_{j})\leq\frac{r}{2z}$. To see this by triangle
inequality, we have

$\operatorname{dist}(Y_{i},Y_{j})\leq
z\cdot(\operatorname{dist}(Y_{i},Y^{*})+\operatorname{dist}(Y^{*},Y_{j}))$

since
$\operatorname{dist}(Y_{i},Y^{*}),\operatorname{dist}(Y^{*},Y_{j})\leq\frac{r}{4z^{2}}$.
So we conclude that $Q=1$.

Now we need to show that $\widetilde{Q}\leq 0.9$. From Line 6,
$\widetilde{Q}=Q+Z$. Therefore it is enough to show $|Z|\leq 0.1$. We know
that from Definition C.5
$|Z|\leq\frac{2}{t\varepsilon}\ln\left(1+\frac{e^{\varepsilon}-1}{2\delta}\right)$.
By the assumption that
$t\geq\frac{20}{\varepsilon}\ln\left(1+\frac{e^{\varepsilon}-1}{2\delta}\right)$
we conclude that $\widetilde{Q}\leq 0.9$, so the Algorithm 1 does not fail in
Line 7. ∎

##  Appendix E Missing Proofs from Section 3

###  E.1 Proof of Lemma 3.2

###### Proof of Lemma 3.2.

The plan is to reduce the problem of computing $\operatorname{dist}^{k}$ to
binary search and checking if a bipartite graph has a perfect matching.

First, we compute $\operatorname{dist}(F_{i},F_{j})$ for every $i,j\in[k]$.
This takes time $k^{2}T_{\operatorname{dist}}$. Note that

$\operatorname{dist}^{k}((F_{1},\ldots,F_{k}),(F_{1}^{\prime},\ldots,F_{k}^{\prime}))$

must be one of these $k^{2}$ values. In addition, observe that we can
determine if

$\operatorname{dist}^{k}((F_{1},\ldots,F_{k}),(F_{1}^{\prime},\ldots,F_{k}^{\prime}))\leq
x$

for any number $x$ by consider the following bipartite graph. The disjoint
node sets are $\\{F_{1},\ldots,F_{k}\\}$ and
$\\{F_{1}^{\prime},\ldots,F_{k}^{\prime}\\}$ and there is an edge between
$F_{i},F_{j}^{\prime}$ if and only if
$\operatorname{dist}(F_{i},F_{j}^{\prime})\leq x$. We then determine if there
is a complete bipartite matching on this graph, which takes time at most
$O(k^{3})$ (e.g. by using the Hungarian algorithm). Thus, we can simply
combine this with a binary search on the sorted values given by
$\\{\operatorname{dist}(F_{i},F_{j}^{\prime})\\}_{i,j^{\prime}}$ to compute
$\operatorname{dist}^{k}$. ∎

###  E.2 Proof of Lemma 3.4

###### Proof of Lemma 3.4.

Computing $\mathcal{B}_{\sigma}^{k}$ only requires computing $\mathcal{B}$ a
total of $k$ times and finding permutation. The former takes time $O(k\cdot
T_{\mathcal{B}})$ and the latter takes time $O(k\log k)$ (say by sampling $k$
uniform random numbers in $[0,1]$ and then sorting). ∎

###  E.3 Proof of Lemma 3.5

###### Proof of Lemma 3.5.

First, we prove privacy. Let $F=(F_{1},\ldots,F_{k})\in\mathcal{F}^{k}$ and
$F^{\prime}=(F_{1}^{\prime},\ldots,F_{k}^{\prime})\in\mathcal{F}_{k}$ be such
that $\operatorname{dist}^{k}(F,F^{\prime})\leq\gamma$. In other words, there
exists a permutation $\pi$ such that
$\operatorname{dist}(F_{i},F_{\pi(i)}^{\prime})\leq\gamma$ for all $i\in[k]$.
Since $\mathcal{B}$ is a $(\gamma,\varepsilon,\delta)$-masking mechanism, we
know that $\mathcal{B}(F_{i}),\mathcal{B}(F^{\prime}_{\pi(i)})$ are
$(\varepsilon,\delta)$-indistinguishable. Thus, by advanced composition (see
Theorem C.7), $(\mathcal{B}(F_{1}),\ldots,\mathcal{B}(F_{k}))$ and
$(\mathcal{B}(F^{\prime}_{\pi(1)}),\ldots,\mathcal{B}(F^{\prime}_{\pi(k)}))$
are $(\varepsilon^{\prime},k\delta+\delta^{\prime})$-indistinguishable with
$\varepsilon^{\prime}$ as stated in the lemma. Since
$\mathcal{B}_{\sigma}^{k}((F_{1}^{\prime},\ldots,F_{k}^{\prime}))$ has the
same distribution has
$\mathcal{B}_{\sigma}^{k}((F^{\prime}_{\pi(1)},\ldots,F^{\prime}_{\pi(k)}))$,
we conclude, using the fact that permutation preserves privacy (see Lemma
C.8), that $\mathcal{B}_{\sigma}^{k}(F)$ and
$\mathcal{B}_{\sigma}^{k}(F^{\prime})$ are
$(\varepsilon^{\prime},k\delta+\delta^{\prime})$-indistinguishable.

Finally, it remains to prove accuracy (i.e. that $\mathcal{B}_{\sigma}^{k}$ is
$(\alpha,k\beta)$-concentrated). Indeed, given
$F=(F_{1},\ldots,F_{k})\in\mathcal{F}^{k}$, we know that
$\operatorname{dist}(\mathcal{B}(F_{i}),F_{i})\leq\alpha$ with probability at
least $1-\beta$. Thus, by a union bound
$\operatorname{dist}(\mathcal{B}(F_{i}),F_{i})\leq\alpha$ for all $i\in[k]$
with probability at least $1-k\beta$. We conclude that
$\operatorname{dist}(\mathcal{B}(F),F)\leq\alpha$ with probability at least
$1-k\beta$. ∎

###  E.4 Proof of Lemma 3.6

###### Proof of Lemma 3.6.

Let $F,F^{\prime},F^{\prime\prime}\in\mathcal{F}^{k}$. We need to show that if
$\operatorname{dist}^{k}(F,F^{\prime})\leq r$ and
$\operatorname{dist}^{k}(F^{\prime},F^{\prime\prime})\leq r$ then
$\operatorname{dist}^{k}(F,F^{\prime\prime})\leq
z\cdot(\operatorname{dist}^{k}(F,F^{\prime})+\operatorname{dist}^{k}(F^{\prime},F^{\prime\prime}))$.
To that end, let
$\pi_{1}^{*}\in\operatorname*{arg\,min}_{\pi}\max_{i\in[k]}(F_{i},F_{\pi(i)}^{\prime})$
and let
$\pi_{2}^{*}\in\operatorname*{arg\,min}_{\pi}\max_{\in[k]}(F_{\pi_{1}^{*}(i)}^{\prime},F_{\pi(i)}^{\prime\prime})$.
Since $\operatorname{dist}$ satisfies $r$-restricted $z$-approximate triangle
inequality and for any $i$,
$\operatorname{dist}(F_{i},F_{\pi_{1}^{*}(i)}^{\prime}),\operatorname{dist}(F_{\pi_{1}^{*}(i)}^{\prime},F_{\pi_{2}^{*}(i)}^{\prime\prime})\leq
r$, we have

$\displaystyle\operatorname{dist}(F_{i},F_{\pi_{2}^{*}(i)}^{\prime\prime})$
$\displaystyle\leq
z\cdot\left(\operatorname{dist}(F_{i},F_{\pi_{1}^{*}(i)}^{\prime})+\operatorname{dist}(F_{\pi_{1}^{*}(i)}^{\prime},F_{\pi_{2}^{*}(i)}^{\prime\prime})\right)$
$\displaystyle\leq
z\cdot\left(\operatorname{dist}^{k}(F,F^{\prime})+\operatorname{dist}^{k}(F^{\prime},F^{\prime\prime})\right).$

In particular

$\operatorname{dist}^{k}(F,F^{\prime\prime})\leq\max_{i\in[k]}\operatorname{dist}(F_{i},F_{\pi_{2}^{*}(i)}^{\prime\prime})\leq
z\cdot\left(\operatorname{dist}^{k}(F,F^{\prime})+\operatorname{dist}^{k}(F^{\prime},F^{\prime\prime})\right),$
(E.1)

as required. ∎

##  Appendix F Proof of Lemma 4.2

This section is dedicated to proving Lemma 4.2. In particular, we will
introduce the masking mechanism $\mathcal{B}_{\textsc{Comp}}(w,\mu,\Sigma)$
that satisfies the conditions of Lemma 4.2. In order to add noise to a
Gaussian component $(w_{i},\mu_{i},\Sigma_{i})$ we perform a number of steps:

  1. 1.

In Subsection F.1, we discuss how to noise the mixing weight of a single
component. This is the most straightforward as we can simply use the Gaussian
mechanism.

  2. 2.

In Subsection F.2, we discuss how to noise the mean of a single component. To
do this, we use an empirically re-scaled Gaussian mechanism where the
empirical covariance matrix is used to shape the noise that we add to the
mean. This is somewhat similar to the empirically re-scaled Gaussian mechanism
used by [BGSUZ21].

  3. 3.

In Subsection F.3, we discuss how to noise the covariance matrix of a single
component. To do this, we use the noising mechanism described in [AL22].

###  F.1 Noising the Mixing Weights

For noising the weights, we simply use the Gaussian mechanism. Let
$\mathcal{R}_{\textsc{w}}(w,\eta)=\max(0,w+\eta g)$ where
$g\sim\mathcal{N}(0,1)$ and $w,\eta\in\mathbb{R}$.

######  Lemma F.1.

Let $\alpha,\beta,\delta>0$, $\eta=\frac{\alpha}{\sqrt{2+2\ln(1/\beta)}}$, and
$\gamma\leq\frac{\alpha\varepsilon}{2\sqrt{2}\ln(2/\delta)\sqrt{1+\ln(1/\beta)}}$.

  1. 1.

Let $w_{1},w_{2}\in\mathbb{R}$. If $|w_{1}-w_{2}|\leq\gamma$ then
$\mathcal{R}_{\textsc{w}}(w_{1},\eta)$ and
$\mathcal{R}_{\textsc{w}}(w_{2},\eta)$ are
$(\varepsilon,\delta)$-indistinguishable.

  2. 2.

Let $w\in\mathbb{R}$. Then $|\mathcal{R}_{\textsc{w}}(w,\eta)-w|\leq\alpha$
with probability at least $1-\beta$.

###### Proof.

The first item is simply the guarantee of the Gaussian Mechanism Theorem C.4
when substituting $\Delta_{2}f,\sigma$ with $\gamma,\eta$ respectively
(followed by post-processing to deal with the $\max$). The second item follows
from standard tail bounds on a Gaussian random variable (e.g., Lemma A.5). ∎

###  F.2 Noising the Mean

In this section, we prove that the mechanism
$\mathcal{R}_{\textsc{Mean}}(\mu,\Sigma,\eta)=\mu+\eta g$ where
$g\sim\mathcal{N}(0,\Sigma)$ effectively privatizes the mean.

######  Lemma F.2.

Let $\alpha,\beta,\delta>0$,
$\eta=\sqrt{\frac{\alpha^{2}}{3(d+\ln(1/\beta))}}$ and let
$\gamma\leq\min\\{\frac{1}{2},\frac{\varepsilon\alpha}{24\ln(2/\delta)\sqrt{d+\ln(1/\beta)}}\\}$.
Let $\mu_{1},\mu_{2}\in\mathbb{R}^{d}$ and let $\Sigma_{1},\Sigma_{2}$ be
$d\times d$ positive-definite matrices. Suppose that

  1. 1.

$\max\\{\|\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}-I_{d}\|_{F},\|\Sigma_{2}^{1/2}\Sigma_{1}^{-1}\Sigma_{2}^{1/2}-I_{d}\|_{F}\\}\leq\gamma$;
and

  2. 2.

$\max\\{\|\mu_{1}-\mu_{2}\|_{\Sigma_{1}},\|\mu_{1}-\mu_{2}\|_{\Sigma_{2}}\\}\leq\gamma$.

Then $\mathcal{R}_{\textsc{Mean}}(\mu_{1},\Sigma_{1},\eta)$ and
$\mathcal{R}_{\textsc{Mean}}(\mu_{2},\Sigma_{2},\eta)$ are
$(\varepsilon,\delta)$-indistinguishable. In addition, if we let
$\widetilde{\mu}=\mathcal{R}_{\textsc{Mean}}(\mu,\Sigma,\eta)$ then
$\|\widetilde{\mu}-\mu\|_{\Sigma}\leq\alpha$ with probability at least
$1-\beta$.

First, we prove a bound on the privacy loss.

######  Lemma F.3.

Let $\eta>0$ and $\gamma\in(0,1/2]$. Let $\mu_{1},\mu_{2}\in\mathbb{R}^{d}$
and let $\Sigma_{1},\Sigma_{2}$ be $d\times d$ positive-definite matrices.
Suppose that

  1. 1.

$\max\\{\|\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}-I_{d}\|_{F},\|\Sigma_{2}^{1/2}\Sigma_{1}^{-1}\Sigma_{2}^{1/2}-I_{d}\|_{F}\\}\leq\gamma$;
and

  2. 2.

$\max\\{\|\mu_{1}-\mu_{2}\|_{\Sigma_{1}},\|\mu_{1}-\mu_{2}\|_{\Sigma_{2}}\\}\leq\gamma$.

Let $Y\sim\mathcal{N}(\mu_{1},\eta^{2}\Sigma_{1})$ and define
$\mathcal{L}\coloneqq\mathcal{L}_{{\mathcal{N}(\mu_{1},\eta^{2}\Sigma_{1})}\parallel{\mathcal{N}(\mu_{2},\eta^{2}\Sigma_{2})}}(Y)$.
Then

$\mathcal{L}\leq\frac{\gamma^{2}}{2}+\frac{\gamma^{2}}{2\eta^{2}}+2\gamma\sqrt{\ln(2/\delta)}+2\gamma\ln(2/\delta)+2\gamma\sqrt{2\ln(2/\delta)}/\eta$
(F.1)

with probability at least $1-\delta$.

###### Proof.

We directly utilize Lemma A.6 and bound each term in Eq. (A.1). For the first
term, we have, using Fact A.3 and that the eigenvalues of
$\Sigma_{2}^{-1/2}\Sigma_{1}\Sigma_{2}^{-1/2}$ are at least $1/2$ by
assumption (since $\gamma<1/2$), we have666 Note that we use that
$\Sigma_{2}^{-1/2}\Sigma_{1}\Sigma_{2}^{-1/2}$ and
$\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}$ have the same spectrum (see
Fact A.9).

$\displaystyle
D_{\mathrm{KL}}\left({\mathcal{N}(\mu_{1},\eta\Sigma_{1})}\parallel{\mathcal{N}(\mu_{2},\eta\Sigma_{2})}\right)$
$\displaystyle\leq\frac{1}{2}\left[\|\Sigma_{2}^{-1/2}\Sigma_{1}\Sigma_{2}^{-1/2}-I_{d}\|_{F}^{2}+(\mu_{2}-\mu_{1})^{\top}(\eta^{2}\Sigma_{2})^{-1}(\mu_{2}-\mu_{1})\right]$
$\displaystyle\leq\frac{1}{2}\left[\gamma^{2}+\frac{\gamma^{2}}{\eta^{2}}\right]$

The second term in Eq. (A.1) is bounded by $2\gamma\sqrt{\ln(2/\delta)}$. The
third term in Eq. (A.1) is bounded by $2\gamma\ln(2/\delta)$. Finally, the
fourth term in Eq. (A.1) is bounded by
$(1+\gamma)\frac{\gamma}{\eta}\sqrt{2\ln(2/\delta)}$. ∎

The next lemma shows that $\mathcal{R}_{\textsc{Mean}}(\mu,\Sigma,\eta)$
concentrates tightly around $\mu$ w.r.t. Mahalanobis distance.

######  Lemma F.4.

Let $\widetilde{\mu}=\mathcal{R}_{\textsc{Mean}}(\mu,\Sigma,\eta)$. Then
$\mathbb{P}\left[\|\widetilde{\mu}-\mu\|_{\Sigma}^{2}\geq
3\eta^{2}(d+\ln(1/\beta))\right]\leq\beta$.

###### Proof.

Recall that $\widetilde{\mu}=\mu+\eta\Sigma^{1/2}g$ where
$g\sim\mathcal{N}(0,I_{d})$. Thus,
$\|\widetilde{\mu}-\mu\|_{\Sigma}^{2}=\eta^{2}\|g\|_{2}^{2}$. Applying Lemma
A.5 gives that

$\displaystyle\mathbb{P}\left[\|\widetilde{\mu}-\mu\|_{\Sigma}^{2}\geq
3\eta^{2}(d+\ln(1/\beta))\right]$
$\displaystyle=\mathbb{P}\left[\|g\|_{2}^{2}\geq 3(d+\ln(1/\beta))\right]$
$\displaystyle\leq\mathbb{P}\left[\|g\|_{2}^{2}\geq
d+2\sqrt{d\ln(1/\beta)}+2\ln(1/\beta)\right]$ $\displaystyle\leq 1/\beta,$

where in the first inequality, we used that $2\sqrt{d\ln(1/\beta)}\leq
d+\ln(1/\beta)$. ∎

###### Proof of Lemma F.2.

Note that

$\gamma\leq\frac{\varepsilon\alpha}{24\ln(2/\delta)\sqrt{d+\ln(1/\beta)}}\leq\min\left\\{\sqrt{\frac{\varepsilon}{2}},\sqrt{\frac{\varepsilon\alpha^{2}}{6(d+\ln(1/\beta))}},\frac{\varepsilon}{8\ln(2/\delta)},\frac{\varepsilon\alpha}{24\sqrt{\ln(2/\delta)(d+\ln(1/\beta))}}\right\\}$

so the first claim follows by Lemma C.9 and plugging $\gamma$ and $\eta$ into
Lemma F.3 to make each term in Eq. (F.1) is at most $\varepsilon/4$. Accuracy
follows from Lemma F.4 using our choice of $\eta$. ∎

###  F.3 Noising the Covariance Matrix

Define $\mathcal{R}_{\textsc{Cov}}(\Sigma,\eta)=\Sigma^{1/2}(I_{d}+\eta
G)(I_{d}+\eta G)^{\top}\Sigma^{1/2}$ where $G\in\mathbb{R}^{d\times d}$ is a
matrix with independent $\mathcal{N}(0,1)$ entries. We require the following
lemma which is paraphrased from Lemma 5.1 and Lemma 5.2 in [AL22]. A proof can
be found in Appendix F.5.

######  Lemma F.5 ( [AL22], Lemma 5.1 & Lemma 5.2).

There are absolute constant $C_{1},C_{2}>0$ such that the following holds. Let
$\varepsilon,\delta,\beta\in(0,1]$ and set
$\eta=\frac{\alpha}{C_{1}\sqrt{d}(\sqrt{d}+\sqrt{\ln(4/\beta)})}$.

  * •

Suppose that
$\gamma\leq\frac{\varepsilon\alpha}{C_{2}\sqrt{d^{2}(d+\ln(4/\beta))}\cdot\ln(2/\delta)}$.
If $\Sigma_{1},\Sigma_{2}$ are positive-definite $d\times d$ matrices such
that

$\max\\{\|\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}-I_{d}\|,\|\Sigma_{2}^{1/2}\Sigma_{1}^{-1}\Sigma_{2}^{1/2}-I_{d}\|\\}\leq\gamma$

then $\mathcal{R}_{\textsc{Cov}}(\Sigma_{1},\eta)$ and
$\mathcal{R}_{\textsc{Cov}}(\Sigma_{2},\eta)$ are
$(\varepsilon,\delta)$-indistinguishable.

  * •

Let $\widetilde{\Sigma}=\mathcal{R}_{\textsc{Cov}}(\Sigma,\eta)$. Then

$\max\left\\{\|\Sigma^{-1/2}\widetilde{\Sigma}\Sigma^{-1/2}-I_{d}\|_{F},\|\widetilde{\Sigma}^{-1/2}\Sigma\widetilde{\Sigma}^{-1/2}-I_{d}\|_{F}\right\\}\leq\alpha$

with probability at least $1-\beta$.

###  F.4 Masking a Single Gaussian Component

Now we use the previous three subsections to devise a masking mechanism for
masking a single component. Let
$\eta_{\textsc{W}}=\frac{\alpha}{\sqrt{2+2\ln(1/\beta)}}$,
$\eta_{\textsc{Mean}}=\frac{\alpha}{\sqrt{3(d+\ln(1/\beta))}}$ and
$\eta_{\textsc{Cov}}=\frac{\alpha}{C_{1}(\sqrt{d}+\sqrt{\ln(4/\beta)}}$ for a
sufficiently large constant $C_{1}$. Consider the mechanism

$\mathcal{B}_{\textsc{Comp}}(w,\mu,\Sigma)=(\mathcal{R}_{\textsc{W}}(w,\eta_{\textsc{W}}),\mathcal{R}_{\textsc{Mean}}(\mu,\Sigma,\eta_{\textsc{Mean}}),\mathcal{R}_{\textsc{Cov}}(\Sigma,\eta_{\textsc{Cov}}))$
(F.2)

###### Proof of Lemma 4.2.

The fact that $\mathcal{B}_{\textsc{Comp}}$ is a
$(\gamma,3\varepsilon,3\delta)$-masking follow from Lemma F.1, Lemma F.2, and
Lemma F.5 along with basic composition. That $\mathcal{B}_{\textsc{Comp}}$ is
$(\alpha,3\beta)$-concentrated also follow from Lemma F.1, Lemma F.2, and
Lemma F.5 along with a union bound. ∎

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

To prove Lemma F.5, we require the following two lemmas from [AL22]. Note that
Lemma F.7 is slightly different than what is stated in [AL22] but follows
easily from the proof.

######  Lemma F.6 ([AL22], Lemma 5.1).

Let $d\in\mathbb{N},\eta>0,\varepsilon\in(0,1],\delta\in(0,1],\gamma>0$ and
suppose that

$\gamma\leq\min\left\\{\sqrt{\frac{\varepsilon}{2d(d+1/\eta^{2})}},\frac{\varepsilon}{8d\sqrt{\ln(2/\delta)}},\frac{\varepsilon}{8\ln(2/\delta)},\frac{\varepsilon\eta}{12\sqrt{d}\sqrt{\ln(2/\delta)}}\right\\}.$
(F.3)

Let $\Sigma_{1},\Sigma_{2}$ be two positive-definite $d\times d$ matrices.
Suppose that

$\max\\{\|\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}-I_{d}\|,\|\Sigma_{2}^{1/2}\Sigma_{1}^{-1}\Sigma_{2}^{1/2}-I_{d}\|\\}\leq\gamma.$

Define $\mathcal{R}_{\textsc{Cov}}(\Sigma,\eta)=\Sigma^{1/2}(I+\eta G)(I+\eta
G)^{\top}\Sigma^{1/2}$ where $G\sim\mathbb{R}^{d\times d}$ is a matrix with
independent $\mathcal{N}(0,1)$ entries. Then
$\mathcal{R}_{\textsc{Cov}}(\Sigma_{1},\eta)$ and
$\mathcal{R}_{\textsc{Cov}}(\Sigma_{2},\eta)$ are
$(\varepsilon,\delta)$-indistinguishable.

######  Lemma F.7 ([AL22], Lemma 5.2).

There is a sufficiently large constant $C>0$ such that the following holds.
Let $\beta>0$ and $\Sigma$ be a positive-definite $d\times d$ matrix and set
$\eta=\frac{\alpha}{C\sqrt{d}(\sqrt{d}+\sqrt{\ln(4/\beta)})}$. If
$\widetilde{\Sigma}=\mathcal{R}_{\textsc{Cov}}(\Sigma,\eta)$ then

$\max\left\\{\|\Sigma^{-1/2}\widetilde{\Sigma}\Sigma^{-1/2}-I_{d}\|_{F},\|\widetilde{\Sigma}^{-1/2}\Sigma\widetilde{\Sigma}^{-1/2}-I_{d}\|_{F}\right\\}\leq\alpha$

with probability at least $1-\beta$.

######  Remark F.8.

Lemma F.7 is stated in [AL22] with respect to spectral distance while we state
it with respect to Frobenius distance. Thus, we scaled $\eta$ down by a factor
of $\sqrt{d}$ compared to [AL22].

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

For the first assertion, it suffices to show that the inequality in Eq. (F.3)
holds. Since Plugging $\eta$ into the fourth term of Eq. (F.3), we note that

$\gamma\leq\frac{\varepsilon\alpha}{C_{2}\sqrt{d^{2}(d+\ln(4/\beta))}\ln(2/\delta)}.$
(F.4)

Thus, it is clear that $\gamma$ is bounded above by the second and third terms
of Eq. (F.3) provided $C_{2}$ is sufficiently large. Next, we prove that
$\gamma$ is bounded above by the first term in Eq. (F.3). Indeed, we have

$\eta^{2}=\frac{\alpha^{2}}{C_{1}^{2}d(\sqrt{d}+\sqrt{\ln(4/\beta)})^{2}}\geq\frac{\alpha^{2}}{2C_{1}^{2}d(d+\ln(4/\beta))},$

where in the last inequality we used the fact that $(a+b)^{2}\leq
2a^{2}+2b^{2}$ for any real numbers $a,b$. Plugging this bound of $\eta^{2}$
into Eq. (F.3) and some calculations give that

$\sqrt{\frac{\varepsilon}{2d(d+1/\eta^{2})}}\geq\sqrt{\frac{\varepsilon\alpha^{2}}{C_{3}d^{2}(d+\ln(4/\beta))}},$
(F.5)

for some constant $C_{3}>0$. Thus, if $C_{2}$ is large enough then the right
side of Eq. (F.4) is upper bounded by the right side of Eq. (F.5). In
particular, the smallest term in Eq. (F.3) is the fourth term. Finally, it is
straightforward to check that $\gamma$ is at most the last term in Eq. (F.4)
by plugging in the value of $\eta$. ∎

##  Appendix G Missing Proofs from Section 5

###  G.1 Proof of Lemma 5.1

###### Proof.

Applying Lemma 3.5 for masking mixtures (with $\varepsilon,\delta$ in Lemma
3.5 replaced by $3\varepsilon,3\delta$, respectively), we have, for every
$\delta^{\prime}>0$, that $\mathcal{B}_{\textsc{Gmm}}$ is a
$(\gamma,\varepsilon^{\prime},3k\delta+\delta^{\prime})$-masking mechanism
where

$\varepsilon^{\prime}=3\sqrt{2k\ln(1/\delta^{\prime})}\varepsilon+3k\varepsilon(e^{3\varepsilon}-1).$

a
$(\gamma,3\sqrt{2k\ln(1/\delta^{\prime})}\varepsilon+3k\varepsilon(e^{3\varepsilon}-1),3k\delta+\delta^{\prime})$-masking
mechanism. As this is true for any $\delta^{\prime}$, we can take
$\delta^{\prime}=3k\delta$ and applying the numeric inequality $e^{x}\leq
1+2x$, valid for $x<\ln(2)$ (see Fact A.7) to get that

$\varepsilon^{\prime}\leq
3\sqrt{2k\ln(1/3k\delta)}\varepsilon+18k\varepsilon^{2},$

Finally, to prove the accuracy part ($\mathcal{B}_{\textsc{Gmm}}$ is
$(\alpha,3k\beta)$-concentrated), we apply the accuracy part of Lemma 3.5 for
masking mixtures which was proved by union bound for all $i\in[k]$. Also
defining the distance to be the maximum between all three component
parameters; weight $w$, mean $\mu$, and covariance matrix $\Sigma$.

$\operatorname{dist}_{\textsc{Param}}(\\{(w_{i},\mu_{i},\Sigma_{i})\\}_{i\in[k]},\\{(w_{i}^{\prime},\mu_{i}^{\prime},\Sigma_{i}^{\prime})\\}_{i\in[k]})=\min_{\pi}\max_{i\in[k]}\operatorname{dist}_{\textsc{Comp}}((w_{\pi(i)},\mu_{\pi(i)},\Sigma_{\pi(i)}),(w_{i}^{\prime},\mu_{i}^{\prime},\Sigma_{i}^{\prime})).$

We can conclude that

$\operatorname{dist}_{\textsc{Param}}(\mathcal{B}_{\textsc{Gmm}}(\\{(w_{i},\mu_{i},\Sigma_{i})\\}_{i\in[k]}),\\{(w_{i},\mu_{i},\Sigma_{i})\\}_{i\in[k]})\leq\alpha$

with probability at least $1-3k\beta$.

Now we have $\mathcal{B}_{\textsc{Gmm}}$ is a
$(\gamma,3\sqrt{2k\ln(1/3k\delta)}\varepsilon+18k\varepsilon^{2},6k\delta)$-masking
mechanism with respect to
$(\mathcal{F}_{\textsc{Gmm}},\operatorname{dist}_{\textsc{Param}})$. Moreover,
$\mathcal{B}_{\textsc{Gmm}}$ is $(\alpha,3k\beta)$-concentrated.

To simplify it, let
$\varepsilon^{\prime}<\ln(2)/3,\delta^{\prime}<1,\alpha^{\prime}<1,\beta^{\prime}<1$
be parameters. We set $\delta=\delta^{\prime}/6k$, $\beta=\beta^{\prime}/3k$,
$\alpha=\alpha^{\prime}$ and
$\varepsilon=\min\left\\{\frac{\varepsilon^{\prime}}{6\sqrt{2k\ln(1/3k\delta)}},\sqrt{\frac{\varepsilon^{\prime}}{36k}}\right\\}\geq\frac{\varepsilon^{\prime}}{\sqrt{72k\ln(2/\delta^{\prime})}}$.
Then for sufficiently large constant $C$ such that if
$\gamma\leq\frac{\varepsilon^{\prime}\alpha^{\prime}}{C_{2}\sqrt{k\ln(2/\delta^{\prime})}\sqrt{d(d+\ln(12k/\beta^{\prime}))}\cdot\ln(12k/\delta^{\prime})}$,
$\mathcal{B}_{\textsc{Gmm}}$ is a
$(\gamma,\varepsilon^{\prime},\delta^{\prime})$-masking mechanism that is
$(\alpha^{\prime},\beta^{\prime})$-concentrated. This proves the claim. ∎

###  G.2 Proof of Lemma 5.2

###### Proof of Lemma 5.2.

Lemma 4.1 asserts that $\operatorname{dist}_{\textsc{Comp}}$ satisfies
$1$-restricted $(3/2)$-approximate triangle inequality. Therefore, applying
Lemma 3.6 (and recalling Definition 3.1)
$\operatorname{dist}_{\textsc{Param}}$ satisfies $1$-restricted
$(3/2)$-approximate triangle inequality. ∎

##  Appendix H Missing Proofs from Section 6

###### Proof of Lemma 6.3.

Recall from Definition 1.4 that $\operatorname{dist}_{\textsc{Gmm}}$ is
defined as

$\operatorname{dist}_{\textsc{Gmm}}\left(F,F^{\prime}\right)=\min_{\pi}\max_{i\in[k]}\max\left\\{|w_{i}-w_{\pi(i)}^{{}^{\prime}}|,d_{\mathrm{TV}}\left({\mathcal{N}(\mu_{i},\Sigma_{i})},{\mathcal{N}(\mu^{{}^{\prime}}_{\pi(i)},\Sigma^{{}^{\prime}}_{\pi(i)})}\right)\right\\}$

where $\pi$ is chosen from the set of all permutations over $[k]$. Also recall
that

$\operatorname{dist}_{\textsc{Param}}(F,F^{\prime})=\min_{\pi}\max_{i\in[k]}\operatorname{dist}_{\textsc{Comp}}((w_{\pi(i)},\mu_{\pi(i)},\Sigma_{\pi(i)}),(w_{i}^{\prime},\mu_{i}^{\prime},\Sigma_{i}^{\prime})),$

where $\operatorname{dist}_{\textsc{Comp}}$ is as defined in Section 4.

By Theorem 1.4, it is straightforward to check that
$\frac{1}{200}\operatorname{dist}_{\textsc{Param}}(F,F^{\prime})\leq\operatorname{dist}_{\textsc{Gmm}}(F,F^{\prime})\leq\frac{1}{\sqrt{2}}\operatorname{dist}_{\textsc{Param}}(F,F^{\prime})$.
∎