# Less is More: Revisiting Gaussian Mechanism for Differential Privacy

anonymous author(s)  Tianxi Ji
Texas Tech University
<EMAIL_ADDRESS>Pan Li
Case Western Reserve University
<EMAIL_ADDRESS>
###### Abstract

Differential privacy (DP) via output perturbation has been a de facto standard
for releasing query or computation results on sensitive data. Different
variants of the classic Gaussian mechanism have been developed to reduce the
magnitude of the perturbation noise and improve the utility of sanitized query
results. However, we identify that all existing Gaussian mechanisms suffer
from the curse of full-rank covariance matrices, and hence the expected
accuracy losses of these mechanisms applied to high dimensional query results,
e.g., in $\mathbb{R}^{M}$, all increase linearly with $M$.

To lift this curse, we design a Rank-1 Singular Multivariate Gaussian
Mechanism (R1SMG). It achieves $(\epsilon,\delta)$-DP on query results in
$\mathbb{R}^{M}$ by perturbing the results with noise following a singular
multivariate Gaussian distribution, whose covariance matrix is a randomly
generated rank-1 positive semi-definite matrix. In contrast, the classic
Gaussian mechanism and its variants all consider deterministic full-rank
covariance matrices. Our idea is motivated by a clue from Dwork et al.’s
seminal work on Gaussian mechanism (Eurocrypt’06) that has been ignored in the
literature: when projecting multivariate Gaussian noise with a full-rank
covariance matrix onto a set of orthonormal basis in $\mathbb{R}^{M}$, only
the coefficient of a single basis can contribute to the privacy guarantee.

This paper makes the following technical contributions.

(i) R1SMG achieves $(\epsilon,\delta)$-DP guarantee on query results in
$\mathbb{R}^{M}$, while the magnitude of the additive noise decreases with
$M$. Therefore, less is more, i.e., less amount of noise is able to sanitize
higher dimensional query results. When $M\rightarrow\infty$, the expected
accuracy loss converges to ${2(\Delta_{2}f)^{2}}/{\epsilon}$, where
$\Delta_{2}f$ is the $l_{2}$ sensitivity of the query function $f$.

(ii) Compared with other mechanisms, R1SMG is less likely to generate noise
with large magnitude that overwhelms the query results, because the kurtosis
and skewness of the nondeterministic accuracy loss introduced by R1SMG is
larger than that introduced by other mechanisms.

##  1 Introduction

Differential privacy (DP) [15, 17] has been increasingly recognized as the
fundamental building block for privacy-preserving database query, sharing, and
analysis. In this area, one important privacy guarantee is
$(\epsilon,\delta)$-DP. It means that, except with a small probability of
$\delta$, the presence or absence of any data record in a dataset cannot
change the probability of observing a specific query result of the dataset by
more than a multiplicative factor of $e^{\epsilon}$.

The classic Gaussian mechanism, proposed by Dwork et al. [15], is an essential
tool to achieve $(\epsilon,\delta)$-DP. Particular, when the output of a query
function is a high dimensional vector, the classic Gaussian mechanism will add
independent and identically distributed (i.i.d.) noise to each component of
the result (please refer to Definition 3, as well as page 261 of [17] and page
3 of [15]).

This standard practice has spread widely into many fields. For example, a
differentially private mechanism returns noisy answers to a set of queries by
adding i.i.d. noise to each query result [36]. Privacy-preserving learning
employs differentially private stochastic gradient descent to perturb each
component of the gradient with i.i.d. Gaussian noise [3]. Unfortunately,
adoption of the classic Gaussian mechanism results in a bottleneck in further
improving the utility (accuracy) of the sanitized query results. This is
because the expected accuracy loss (Definition 1) of the Gaussian mechanism
scales linearly with the dimensionality $M$ of the query results. We refer to
this as the curse of full-rank covariance matrices.

######  Definition 1.

Accuracy Loss [36, 22]. The accuracy loss of a differentially private output
perturbation mechanism ($\mathcal{M}$) is

$\mathcal{L}=||\mathcal{M}(f(\bm{x}))-f(\bm{x})||_{2}^{2}=||\mathbf{n}||_{2}^{2},$
(1)

where $\bm{x}$ denotes a dataset, $f(\bm{x})$ is the query result on dataset
$\bm{x}$, and $\mathbf{n}$ is the noise vector added to the query result.

Due to the randomness involved in the perturbation noise, $\mathcal{L}$ is
nondeterministic. Thus, in this paper, we investigate the expected value of
accuracy loss, i.e., $\mathbb{E}[\mathcal{L}]$.

###  1.1 The Curse of Full-Rank Covariance Matrices

Here, we provide a high-level description on the identified curse of full-rank
covariance matrices, while the details are deferred to Section 3.

######  Proposition 1.

The Identified Curse. Let $\bm{x}$ be the dataset,
$f(\bm{x})\in\mathbb{R}^{M}$ be the queried results, and
$\mathbf{n}\in\mathbb{R}^{M}$ be the perturbation noises introduced by the
classic Gaussian mechanism (or its variants, e.g., the analytic Gaussian
mechanism [5], and the Matrix-Variate Gaussian (MVG) mechanism [10]). Then,
the expected accuracy loss is equal to the trace of the covariance matrix of
the Gaussian noise $\mathbf{n}$, i.e.,

$\mathbb{E}[\mathcal{L}]=Tr[Cov(\mathbf{n})]=\Theta(M),$

where $Cov(\mathbf{n})$ denotes the covariance matrix of the noise
$\mathbf{n}$.

Since existing Gaussian mechanisms always introduce noise that has a full-rank
covariance matrix, i.e., $rank(Cov(\mathbf{n}))=M$, where $Cov(\mathbf{n})$ is
positive definite. $\mathbb{E}[\mathcal{L}]$ is equivalent to the summation of
$M$ positive eigenvalues of $Cov(\mathbf{n})$. It implies that the expected
accuracy loss scales as $\Theta(M)$, i.e., on the order of the dimensionality
$M$ of the query output. In Section 3, we will prove Proposition 1 when
$f(\bm{x})$ is in a vector and in a matrix form under different variants of
the classic Gaussian mechanism.

###  1.2 Lifting the Curse: Clue and Contributions

To lift the identified curse, we resort to the singular multivariate Gaussian
distribution [28, 13, 41, 42, 31] (Definition 7) with rank-1 covariance matrix
and develop a Rank-1 Singular Multivariate Gaussian Mechanism (i.e., R1SMG).
Our idea is motivated by an ignored clue in Dwork and Roth’s proof for the DP
guarantee of the Gaussian mechanism [17].222According to [17], the DP
guarantee of the classic Gaussian mechanism was original observed by Dwork,
McSherry, Nissim, and Smith in [16]. The complete proof is presented by Dowrk
and Roth in [17]. Specifically, Dwork and Roth proved that by projecting the
additive noise $\mathbf{n}\in\mathbb{R}^{M}$ onto a fixed set of orthonormal
basis (e.g., $\bm{b}_{1},\bm{b}_{2},\cdots,\bm{b}_{M}$), only the coefficient
of a single basis (e.g., $\mathbf{n}^{T}\bm{b}_{1}$) contributes to the
privacy guarantee (more details are deferred to Section 4). However, this
important clue has been ignored in the literature. To the best of our
knowledge, our work is the first to discover and leverage this ignored clue.

Our main contributions are summarized as follows.

(1) A new DP Mechanism and Privacy Guarantee (Definition 8 and Theorem 5). We
develop a new mechanism R1SMG that can achieve $(\epsilon,\delta)$-DP
guarantee on high dimensional query results $f(\bm{x})\in\mathbb{R}^{M}$
($M>2$). The covariance matrix, denoted as $\bm{\Pi}$, of the noise introduced
by R1SMG is a random rank-1 positive semidefinite matrix, whose singular
vector is randomly sampled from the unit sphere embedded in $\mathbb{R}^{M}$.
Let $\sigma_{*}$ be the singular value of the rank-1 covariance matrix
$\bm{\Pi}$. We prove that a sufficient condition for R1SMG to achieve
$(\epsilon,\delta)$-DP is
$\sigma_{*}\geq\frac{2(\Delta_{2}f)^{2}}{\epsilon\psi}$, where $\Delta_{2}f$
is the $l_{2}$ sensitivity of the query function $f$,
$\psi=\left({\delta\Gamma(\frac{M-1}{2})}\Big{/}{\sqrt{\pi}\Gamma(\frac{M}{2})}\right)^{\frac{2}{M-2}}$
and $\Gamma(\cdot)$ is Gamma function.

(2) Decreasing expected accuracy loss (Theorem 7). We prove that the expected
accuracy loss on $f(\bm{x})$ caused by the proposed R1SMG (i.e.,
$||{R1SMG}(f(\bm{x}))-f(\bm{x})||_{2}^{2}$) equals $\sigma_{*}$, which
decreases with the dimension of $f(\bm{x})$, i.e., $M$, and that when
$M\rightarrow\infty$, we have
$\sigma_{*}\rightarrow\frac{2(\Delta_{2}f)^{2}}{\epsilon}$. This implies that
R1SMG is able to achieve $(\epsilon,\delta)$-DP with less perturbation noise
when $M$ increases, i.e., less is more. In contrast, all the other mechanisms
result in expected accuracy loss that scales linearly with $M$. Although it
might seem counterintuitive at the first sight, it is achieved by leveraging
the randomness of the angle between two randomly selected singular vectors
from $\mathbb{S}^{M-1}$ (the unit sphere embedded in $\mathbb{R}^{M}$). For
better understanding, we provide an intuitive explanation on this unique
property in Appendix A.

(3) Higher stability of the perturbed results (Theorem 8 and 9). We
theoretically show that the accuracy of the perturbed $f(\bm{x})$ obtained by
the proposed R1SMG is more stable than the other mechanisms. By “stable”, we
mean that it is less likely for R1SMG to generate noise with large magnitude
that overwhelms $f(\bm{x})$.

(4) Applications. We perform three case studies, including differentially
private 2D histogram query, principal component analysis, and deep learning,
to validate that the proposed R1SMG can significantly boost the utility of
various applications by introducing less noise.

Roadmap. We review the preliminaries for this study in Section 2. Next, we
identify the curse of full-rank covariance matrices in various types of
Gaussian mechanisms in Section 3. In Section 4, we revisit Dwork and Roth’s
proof, and identify a previously ignored clue that motivates our work. After
that, we formally develop R1SMG in Section 5. In Section 6, we analyze the
utility stability achieved by R1SMG and theoretically compare it with other
mechanisms. Section 7 presents the case studies. Section 8 discusses the
related works. Finally, Section 9 concludes the paper.

##  2 Preliminaries

In this section, we review $(\epsilon,\delta)$-DP, and revisit the definitions
and privacy guarantees of the classic Gaussian mechanism and its variants.
Table 1 lists the frequently used notations. In this paper, lowercase bold
symbol (e.g., $\bm{x}$) represents a vector, lowercase boldface character
(e.g., $\mathbf{x}$) represents a random vector, uppercase boldface character
(e.g., $\mathbf{X}$) denotes a matrix, and blackboard-bold uppercase character
(e.g., $\mathbb{X}$) represents a domain or a set.

$\Delta_{2}f$ |  $l_{2}$ sensitivity of query function $f$
---|---
$\sigma^{2}$ | variance of noise in classic Gaussian mechanism
$\sigma_{A}^{2}$ | variance of noise in analytic Gaussian mechanism
$\bm{\Sigma}$ and $\bm{\Psi}$ | row-, column-wise covariance matrices in MVG
$\bm{\Pi}$ | singular covariance matrix in the proposed R1SMG
$\sigma_{*}$ | singular value of $\bm{\Pi}$
$\mathbb{PSD}$ | set of positive semi-definitive matrices
$\mathbb{PD}$ | set of positive definitive matrices
$\mathcal{U}(\mathbb{V}_{1,M})$ | uniform distribution on Stiefel manifold $\mathbb{V}_{1,M}$
| (i.e., the unit sphere $\mathbb{S}^{M-1}$)
$\chi^{2}(M)$ | Chi-squared distribution with $M$ degrees of freedom
$\mathcal{L}$ | non-deterministic accuracy loss

Table 1: Frequently used notations in the paper.

Following the convention of [15, 17], a database $\bm{x}$ is represented by
its histogram in a universe $\mathcal{X}$:
$\bm{x}\in\mathbb{N}^{|\mathcal{X}|}$, where each entry $\bm{x}_{i}$ is the
number of elements in the database $\bm{x}$ of $type\ i\in\mathcal{X}$ (see
page 17 of [17]). $\bm{x}\sim\bm{x}^{\prime}$ denotes a pair of neighboring
databases that differ by one data record, and $\Delta_{2}f$ is the $l_{2}$
sensitivity of query function $f$, i.e.,
$\Delta_{2}f=\sup_{\bm{x}\sim\bm{x}^{\prime}}||f(\bm{x})-f(\bm{x}^{\prime})||_{2}$.

######  Definition 2.

$(\epsilon,\delta)$-DP [17]. A randomized mechanism $\mathcal{M}$ satisfies
$(\epsilon,\delta)$-DP if for any two neighboring datasets,
$\bm{x},\bm{x}^{\prime}\in\mathbb{N}^{|\mathcal{X}|}$, and for all
$\mathcal{S}\subseteq\rm{Range}(\mathcal{M})$, $\Pr[\mathcal{M}(\bm{x})\in
S]\leq e^{\epsilon}\Pr[\mathcal{M}(\bm{x}^{\prime})\in S]+\delta$ holds, where
$\epsilon>0$ and $0<\delta<1$.

Dwork et al. (page 6 of [18]) also give an alternative definition of
$(\epsilon,\delta)$-DP, i.e.,
$\ln\left(\frac{\Pr[\mathcal{M}(\bm{x})]}{\Pr[\mathcal{M}(\bm{x}^{\prime})]}\right)\leq\epsilon$
holds with all but $\delta$ probability. The log-ratio of the probability
densities is called the privacy loss random variable [5, 18] (Definition 6).

######  Definition 3.

The classic Gaussian Mechanism. Let
$f:\mathbb{N}^{|\mathcal{X}|}\rightarrow\mathbb{R}^{M}$ be an arbitrary
$M$-dimensional function. The Gaussian mechanism with parameter $\sigma$ adds
noise scaled to $\mathcal{N}(0,\sigma^{2})$ to each of the $M$ components of
the output.

######  Theorem 1.

DP Guarantee of classic Gaussian mechanism (cf. page 261 [17]) Let
$\epsilon\in(0,1)$ be arbitrary. If $\sigma\geq{c\Delta_{2}f}/{\epsilon}$,
where $c^{2}>2\ln(\frac{1.25}{\delta})$, then the classic Gaussian Mechanism
achieves ($\epsilon,\delta$)-DP.

The analytic Gaussian mechanism [5] follows the same procedure of the classic
Gaussian mechanism (discussed in Definition 3). It improves the classic
Gaussian mechanism by directly calibrating the variance ($\sigma_{A}^{2}$) of
the Gaussian noise via analytically solving an expression involving
$\sigma_{A}$. The privacy guarantee of this mechanism is stated as follows.

######  Theorem 2.

DP Guarantee of Analytic Gaussian Mechanism [5]. The analytic Gaussian
mechanism achieves $(\epsilon,\delta)$-DP guarantee on the query result
$f(\bm{x})$ if

$\Phi\Big{(}\frac{\Delta_{2}f}{2\sigma_{A}}-\frac{\epsilon\sigma_{A}}{\Delta_{2}f}\Big{)}-e^{\epsilon}\Phi\Big{(}-\frac{\Delta_{2}f}{2\sigma_{A}}-\frac{\epsilon\sigma_{A}}{\Delta_{2}f}\Big{)}\leq\delta,$

where $\Phi(t)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{t}e^{-y^{2}/2}dy$ is the
cumulative distribution function of the standard univariate Gaussian
distribution.

The MVG mechanism [10] is an extension of the Gaussian mechanism to matrix-
valued query (i.e., $f(\bm{x})\in\mathbb{R}^{M\times N}$).

######  Definition 4.

MVG Mechanism [10]. Given a matrix-valued query function
$f(\bm{x})\in\mathbb{R}^{M\times N}$, the MVG mechanism is defined as
$\mathcal{M}_{MVG}(f(\bm{x}))=f(\bm{x})+\mathbf{N}$, where
$\mathbf{N}\sim\mathcal{N}_{M,N}(\mathbf{0},\bm{\Sigma},\bm{\Psi})$ represents
the matrix-variate Gaussian distribution with PDF

$f_{\mathbf{X}}=\frac{\exp\Big{(}-\frac{1}{2}Tr[\bm{\Psi}^{-1}(\mathbf{X}-\mathbf{M})^{T}\bm{\Sigma}^{-1}(\mathbf{X}-\mathbf{M})]\Big{)}}{(2\pi)^{MN/2}{\rm{det}}(\bm{\Psi})^{M/2}{\rm{det}}(\bm{\Sigma})^{N/2}}.$
(2)

$\mathbf{M}\in\mathcal{R}^{M\times N}$ is the mean.
$\bm{\Sigma}\in\mathbb{PD}^{M\times M}$ and $\bm{\Psi}\in\mathbb{PD}^{N\times
N}$ are the row-wise and column-wise full-rank covariance matrix.

######  Theorem 3.

DP Guarantee of MVG [10]. $\sigma(\bm{\Sigma}^{-1})$ and
$\sigma(\bm{\Psi}^{-1})$ are the vectors consisting singular values of
$\bm{\Sigma}^{-1}$ and $\bm{\Psi}^{-1}$. The MVG mechanism achieves
$(\epsilon,\delta)$-DP if
$||\sigma(\bm{\Sigma}^{-1})||_{2}||\sigma(\bm{\Psi}^{-1})||_{2}\leq{\Big{(}-\beta+\sqrt{\beta^{2}+8\alpha\epsilon}\Big{)}^{2}}\Big{/}{4\alpha^{2}}$.
$\alpha=2H_{r}\gamma\Delta_{2}f+(H_{r}+H_{r,\frac{1}{2}})\gamma^{2}$,
$\beta=2(MN)^{1/4}H_{r}\Delta_{2}f\tau(\delta)$ ($H_{r}$ is the harmonic
number of order $r$, $H_{r,\frac{1}{2}}$ is the harmonic number of order $r$
of $\frac{1}{2}$, $\gamma=\sup_{\bm{x}}||f(\bm{x})||_{F}$), and
$\tau(\delta)=2\sqrt{-MN\ln\delta}-2\ln\delta+MN$.

In our study, we also identify an approach to improve the MVG mechanism.
Please see Appendix D for the details.

##  3 Identifying The Curse

We identify the curse of full-rank covariance matrices by showing that the
expected value of the accuracy losses (Definition 1) introduced by the classic
Gaussian mechanism and its variants all increase linearly with the dimension
of $f(\bm{x})$.

###  3.1 Query Result is a Vector

If $f(\bm{x})\in\mathbb{R}^{M}$, the classic Gaussian mechanism perturbs each
element of $f(\bm{x})$ using i.i.d. Gaussian noise drawn from
$\mathcal{N}(0,\sigma^{2})$ (cf. Definition 3). Thus, we derive
$\mathbb{E}[\mathcal{L}]$ under the framework of classic Gaussian mechanism as

$\displaystyle\begin{aligned}
\mathbb{E}_{\rm{classic}}[\mathcal{L}]=&\mathbb{E}_{\mathbf{n}_{i}\sim\mathcal{N}(0,\sigma^{2})}\Big{[}{\sum}_{i}^{M}\mathbf{n}_{i}^{2}\Big{]}=\mathbb{E}_{z_{i}\sim\mathcal{N}(0,1)}\Big{[}{\sum}_{i}^{M}(\sigma
z_{i})^{2}\Big{]}\\\
\stackrel{{\scriptstyle(a)}}{{=}}&\sigma^{2}\mathbb{E}_{U\sim\chi^{2}(M)}[U]\stackrel{{\scriptstyle(b)}}{{=}}\sigma^{2}M=Tr[\sigma^{2}\mathbf{I}_{M\times
M}]=\Theta(M),\end{aligned}$

where $(a)$ and $(b)$ are obtained, because the squared sum of $M$ independent
standard Gaussian variable follows the chi-squared distribution with $M$
degrees of freedom, i.e., $\chi^{2}(M)$, whose expected value is $M$. Since
$\mathbf{n}$ in the classic Gaussian mechanism can be equivalently sampled
from a multivariate Gaussian distribution, i.e.,
$\mathbf{n}\sim\mathcal{N}(\mathbf{0},\sigma^{2}\mathbf{I}_{M\times M})$ with
PDF

$f_{\mathbf{n}}={\exp\Big{(}-\frac{1}{2}\mathbf{n}^{T}\bm{\Sigma}^{-1}\mathbf{n}\Big{)}}\Big{/}\Big{(}{(2\pi)^{\frac{M}{2}}\text{det}(\bm{\Sigma})^{\frac{1}{2}}}\Big{)},$
(3)

where $\bm{\Sigma}=Cov(\mathbf{n})=\sigma^{2}\mathbf{I}_{M\times
M}\in\mathbb{PD}^{M\times M}$. The value of $\bm{\Sigma}$ is uniquely
determined by the variance of the considered univariate Gaussian noise. Thus,
the instantiation of Proposition 1 under the classic Gaussian mechanism is

$\mathbb{E}_{\rm{classic}}[\mathcal{L}]=Tr[\bm{\Sigma}]=\Theta(M),$

which suggests that the expected accuracy loss of the classic Gaussian
mechanism is the summation of all $M$ positive eigenvalues of the underlying
covariance matrix (i.e., $\sigma^{2}\mathbf{I}_{M\times M}$).333The
eigenvalues and singular values are identical for positive (semi)-definite
matrices, thus we will use “eigenvalues” and “singular values” interchangeably
throughout this paper.

The same analysis also applies to the analytic Gaussian mechanism (discussed
in Section 2), because it still perturbs each element of $f(\bm{x})$ using
i.i.d. Gaussian noise with variance $\sigma_{A}^{2}$. Thus,
$\mathbb{E}_{\rm{Analytic}}[\mathcal{L}]=Tr[\sigma^{2}_{A}\mathbf{I}_{M\times
M}]=\sigma^{2}_{A}M=\Theta(M)$, i.e., its expected accuracy loss also increase
linearly with the size of the dimensionality of the output $M$.

###  3.2 Query Result is a Matrix

If $f(\bm{x})\in\mathbb{R}^{M\times N}$, even though the collection of the
i.i.d. noise becomes a matrix, the vectorization of the noise matrix is
attributed to $\mathcal{N}(\mathbf{0},\sigma^{2}\mathbf{I}_{MN\times MN})$,
thus, the identified curse still remains. Instead of adding i.i.d. Gaussian
noise, Chanyaswad et al. [10] perturbs the matrix-valued result by adding a
matrix noise (denoted as $\mathbf{X}$) attributed to the matrix-variate
Gaussian distribution shown in (2).

It is well-known that the vectorization of the matrix-variate Gaussian noise
can equivalently be sampled from a multivariate Gaussian distribution with a
new full-rank covariance matrix, i.e.,
$\bm{\Xi}=\bm{\Sigma}\otimes\bm{\Psi}\in\mathbb{PD}^{MN\times MN}$ [21]. In
general, $\bm{\Xi}$ will have nonzero off-diagonal entries, thus, the elements
in the additive noise are not mutually independent. Thus, we need another tool
to analyze the expected accuracy loss of the MVG mechanism. First, we observe
that $\mathcal{L}=||\mathbf{n}||_{2}^{2}=\mathbf{n}^{T}\mathbf{n}$ is a
quadratic form in random variable defined as follows.

######  Definition 5.

Quadratic Form in Random Variable [39]. Denote by $\mathbf{x}$ a random vector
with mean $\mathbf{\mu}$ and covariance matrix $\bm{\Xi}$. The quadratic form
in random variable $\mathbf{x}$ associated with a symmetric matrix
$\mathbf{A}$ is defined as $Q(\mathbf{x})=\mathbf{x}^{T}\mathbf{A}\mathbf{x}$.

Then $\mathcal{L}$ introduced by the MVG mechanism is a quadratic form in
multivariate Gaussian random variable attributed to
$\mathcal{N}(\mathbf{0},\bm{\Xi})$ with $\mathbf{A}$ being the identity
matrix. In the following theorem, we recall the $t$-th moment of quadratic
form in Gaussian random variable (which will also be used in our future
analyses on the kurtosis and skewness of $\mathcal{L}$ in Section 6).

######  Theorem 4 (Page 53, [39]).

The $t$-th moment of a quadratic form in multivariate Gaussian random
variable, i.e, $\mathbf{x}\sim\mathcal{N}(\mathbf{\mu},\bm{\Xi})$ with
$\bm{\Xi}$ being full-rank, is given by

$\displaystyle\mathbb{E}[Q(\mathbf{x})^{t}]=$
$\displaystyle\bigg{\\{}\sum_{t_{1}=0}^{t-1}{t-1\choose
t_{1}}g^{(t-1-t_{1})}\times$
$\displaystyle\sum_{t_{2}=0}^{t_{1}-1}{t_{1}-1\choose
t_{2}}g^{(t_{1}-1-t_{2})}\times\cdots\times\sum_{t_{2}=0}^{1}{1-1\choose
t_{2}}g^{(0)}\bigg{\\}},$

where
$g^{(k)}=2^{k}k!\left(Tr(\mathbf{A}\bm{\Xi})^{k+1}+(k+1)\mathbf{\mu}^{T}(\mathbf{A}\bm{\Xi})^{k}\mathbf{A}\mathbf{\mu}\right)$,
$k\in[0,t-1]$.

As a result, the instantiation of Proposition 1 under the MVG mechanism is

$\displaystyle\mathbb{E}_{\rm{MVG}}[\mathcal{L}]=\quad\mathbb{E}_{\mathclap{\begin{subarray}{c}\\\
\\\ \
\mathbf{N}\sim\mathcal{N}_{M,N}(\mathbf{0},\bm{\Sigma},\bm{\Psi})\end{subarray}}}[||\mathbf{N}||_{F}^{2}]=\quad\mathbb{E}_{\mathclap{\begin{subarray}{c}\\\
\\\ \
\mathbf{n}\sim\mathcal{N}(\mathbf{0},\bm{\Sigma}\otimes\bm{\Psi})\end{subarray}}}[||\mathbf{n}||_{2}^{2}]$
(4) $\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}$ $\displaystyle
Tr[\bm{\Sigma}\otimes\bm{\Psi}]=Tr[\Xi]=\Theta(MN),$

where (a) is obtained by applying Theorem 4 with $t=1$, i.e.,
$\mathbb{E}[Q(\mathbf{x})]=g^{(0)}=Tr[\bm{\Xi}]$. Clearly, (4) also suggests
that $\mathbb{E}_{\rm{MVG}}[\mathcal{L}]$ is the summation of $MN$ positive
eigenvalues, since $\bm{\Sigma}\otimes\bm{\Psi}$ is positive definite. Thus,
the expected accuracy loss of the MVG mechanism also increases linearly with
the size of the query output $MN$.

Another stealthy perspective to understand the identified curse of full-rank
covariance matrices is by observing that the PDFs in (2) and (3) all involve
determinants of covariance matrices in the denominators (which should be
nonzero). Then, theses covariance matrices should always be full-rank. As a
consequence, the curse cannot be compromised unless we use a new form of PDF
to generate the perturbation noise.

##  4 An Ignored Clue from Dwork et al. [15, 17, 16]

In this section, we recall Dwork and Roth’s proof of Gaussian mechanism
achieving $(\epsilon,\delta)$-DP [15, 17, 16] when the query function returns
a $M$-dimension vector. At the end of their proof, we identify the ignored
clue which corroborates that Gaussian noise with rank-1 covariance matrix is
sufficient to achieve $(\epsilon,\delta)$-DP and also motivates our work.

Dwork and Roth essentially investigate the upper bound of the privacy loss
random variable (PLRV) on a pair of neighboring database $\bm{x}$ and
$\bm{x}^{\prime}$ defined as follows.

######  Definition 6.

(page 6 of [18]) Consider running a randomized mechanism $\mathcal{M}$ on a
pair of neighboring dataset $\bm{x}$ and $\bm{x}^{\prime}$. For an outcome
$\mathbf{s}$, PLRV on $\mathbf{s}$ is defined as the log-ratio of the
probability density when $\mathcal{M}$ is running on each dataset, i.e.,

$\mathrm{PRLV}^{(\mathbf{s})}_{(\mathcal{M}(\bm{x})||\mathcal{M}(\bm{x}^{\prime}))}=\ln\left(\frac{\Pr[\mathcal{M}(\bm{x})=\mathbf{s}]}{\Pr[\mathcal{M}(\bm{x}^{\prime})=\mathbf{s}]}\right).$

The following derivations are restatements of content from pages 261-265 of
[17]. $f(\cdot)$ is the query function, i.e.,
$f:\bm{x}\in\mathbb{N}^{|\mathcal{X}|}\rightarrow\mathbb{R}^{M}$. We are
interested in multivariate Gaussian noise that can obscure the difference
$\bm{v}\triangleq f(\bm{x})-f(\bm{x}^{\prime})$. To achieve
$(\epsilon,\delta)$-DP, it requires that the $\mathrm{PLRV}$ associated with
the classic Gaussian mechanism (denoted as $\mathcal{G}$), i.e.,

$\mathrm{PRLV}^{(\mathbf{s})}_{(\mathcal{G}(\bm{x})||\mathcal{G}(\bm{x}^{\prime}))}=\left|\frac{1}{2\sigma^{2}}\left(||\bm{n}||^{2}-||\bm{n}+\bm{v}||^{2}\right)\right|,\
\ (\text{p. 265~{}\cite[cite]{[\@@bibref{}{dwork2014algorithmic}{}{}]}})$ (5)

is upper bounded by $\epsilon$. In
$\mathrm{PRLV}^{(\mathbf{s})}_{(\mathcal{G}(\bm{x})||\mathcal{G}(\bm{x}^{\prime}))}$,
$\bm{n}$ is chosen from $\mathcal{N}(0,\bm{\Sigma})$, where $\bm{\Sigma}$ is a
diagonal matrix with entries $\sigma^{2}$.

Then, Dwork and Roth bound
$\mathrm{PRLV}^{(\mathbf{s})}_{(\mathcal{G}(\bm{x})||\mathcal{G}(\bm{x}^{\prime}))}$
by observing that the multivariate Gaussian distribution is a spherically
symmetric distribution [4]. Thus, when representing the noise $\mathbf{n}$
using any fixed orthonormal basis $\bm{b}_{1},\bm{b}_{2},\cdots,\bm{b}_{m}$,
i.e, $\mathbf{n}=\sum_{i=1}^{M}\lambda_{i}\bm{b}_{i}$, the corresponding
coefficients are also attributed to the same Gaussian distribution, i.e.,
$\lambda_{i}\sim\mathcal{N}(0,\sigma^{2}),i\in[1,M]$. Furthermore, without
loss of generality, Dwork and Roth assume the first component (base)
$\bm{b}_{1}$ is parallel to $\bm{v}$ (the difference between $f(\bm{x})$ and
$f(\bm{x}^{\prime})$). Thus,

$\displaystyle\mathrm{PRLV}^{(\mathbf{s})}_{(\mathcal{G}(\bm{x})||\mathcal{G}(\bm{x}^{\prime}))}=\left|\frac{1}{2\sigma^{2}}\left(\left|\left|\sum_{i=1}^{M}\lambda_{i}\bm{b}_{i}\right|\right|^{2}-\left|\left|\sum_{i=1}^{M}\lambda_{i}\bm{b}_{i}+\bm{v}\right|\right|^{2}\right)\right|$
(6)
$\displaystyle=\left|\frac{1}{2\sigma^{2}}\left(||\bm{v}||^{2}+2\lambda_{1}||\bm{v}||\right)\right|\leq\frac{1}{2\sigma^{2}}\Big{(}(\Delta_{2}f)^{2}+2\lambda_{1}\Delta_{2}f\Big{)},$

where the second equality holds because $\bm{b}_{1}$ and $\bm{v}$ are
orthogonal to $\bm{b}_{i},i\in[2,M]$. The last inequality is due to the
definition of $l_{2}$ sensitivity. Since now
$\mathrm{PRLV}^{(\mathbf{s})}_{(\mathcal{G}(\bm{x})||\mathcal{G}(\bm{x}^{\prime}))}$
in (6) only involves a single Gaussian random variable, i.e., $\lambda_{1}$,
Theorem 1 can be proved by following the same procedure when the query
function returns a scalar value (p. 262-264 of [17]).

Clue comes up to the surface. From (6), it is clear that
$\mathrm{PRLV}^{(\mathbf{s})}_{(\mathcal{G}(\bm{x})||\mathcal{G}(\bm{x}^{\prime}))}$
is only related to $\lambda_{1}$ and $\Delta_{2}f$. Since $\lambda_{1}$ (a
Gaussian random variable) is the component of the noise $\mathbf{n}$ in the
direction of orthonormal base $\bm{b}_{1}$, it clearly suggests that, after
decomposing a multivariate Gaussian noise using a set of orthonormal basis,
only the coefficient of one basis contribute to the value of
$\mathrm{PRLV}^{(\mathbf{s})}_{(\mathcal{G}(\bm{x})||\mathcal{G}(\bm{x}^{\prime}))}$.
In other words, the coefficients of other basis have no impact on the privacy
loss of the Gaussian mechanism. Or mathematically, the privacy guarantee
achieve by $\mathbf{n}=\sum_{i=1}^{M}\lambda_{i}\bm{b}_{i}$ is identical to
that achieved by $\lambda_{1}\bm{b}_{1}$. This hidden clue motivates our idea
of using multivariate Gaussian noise whose covariance matrix has rank-1
(instead of multivariate Gaussian noise with full-rank covariance matrix) to
achieve $(\epsilon,\delta)$-DP.

##  5 Lifting the Curse

In what follows, we present the developed R$1$SMG mechanism, which lifts the
identified curse of full-rank covariance matrices. In particular, we first
introduce its noise generation process and a sufficient condition for it to
achieve $(\epsilon,\delta)$-DP. Next, we analyze the asymptotic behavior of
R1SMG as $M$ increases, and discuss the privacy leakage of utilizing vector in
the null space of the noise.

###  5.1 R1SMG: Multivariate Gaussian Noise with Random Rank-1 Covariance
Matrix

We first provide the statistical background on the singular multivariate
Gaussian distribution with a given rank-$r$ covariance matrix, e.g.,
$\bm{\Pi}$ and $Rank(\bm{\Pi})=r$.

######  Definition 7.

Singular Multivariate Gaussian Distribution [28, 13, 41, 42]. A
$M$-dimensional random variable $\mathbf{x}=[x_{1},x_{2},\cdots,x_{M}]^{T}$
has a singular multivariate Gaussian distribution with mean
$\mathbf{\mu}\in\mathbb{R}^{M}$ and singular covariance matrix
$\bm{\Pi}\in\mathbb{PSD}^{M\times M}$ with rank-$r$, i.e.,
$\mathbf{x}\sim\mathcal{N}(\mathbf{\mu},\bm{\Pi})$ and $Rank(\bm{\Pi})=r<M$,
if its PDF is

$f_{\mathbf{x};Rank(\bm{\Pi})=r}=\frac{(2\pi)^{-r/2}\exp\big{(}-\frac{1}{2}(\mathbf{x}-\mathbf{\mu})^{T}\bm{\Pi}^{\dagger}(\mathbf{x}-\mathbf{\mu})\big{)}}{\sqrt{\sigma_{1}(\bm{\Pi})\cdots\sigma_{r}(\bm{\Pi})}},$

where $\sigma_{i}(\bm{\Pi})$ is the $i$-th nonzero singular value of
$\bm{\Pi}$, and $\bm{\Pi}^{\dagger}$ is the generalized inverse of $\bm{\Pi}$.
$\bm{\Pi}^{\dagger}=\mathbf{V}_{r}\bm{\Lambda}_{r}^{-1}\mathbf{V}_{r}^{T}$,
$\bm{\Lambda}_{r}=\text{diag}(\sigma_{1}(\bm{\Pi}),\cdots,\sigma_{r}(\bm{\Pi}))\in\mathbb{R}^{r\times
r}$, and $\mathbf{V}_{r}\in\mathbb{R}^{M\times r}$ is the matrix of singular
vectors corresponding to the $r$ nonzero singular values.

Samples of $f_{\mathbf{x};Rank(\bm{\Pi})=r}$ (e.g., $\mathbf{n}$) can be
generated by applying the disintegration theorem [20]. In particular, if
$\mathbf{\mu}=\mathbf{0}$, by defining a linear mapping

$\mathbf{n}=\mathbf{V}_{r}\bm{\Lambda}_{r}^{1/2}\mathbf{z},\quad\mathrm{and}\quad\mathbf{z}\sim\mathcal{N}(\mathbf{0},\mathbf{I}_{r\times
r}),$ (7)

where
$\bm{\Lambda}_{r}^{1/2}=\text{diag}(\sqrt{\sigma_{1}(\bm{\Pi})},\sqrt{\sigma_{2}(\bm{\Pi})},\cdots,\sqrt{\sigma_{r}(\bm{\Pi})})\in\mathbb{R}^{r\times
r}$, then $\mathbf{n}$ is attributed to a singular multivariate Gaussian
distribution with a rank-$r$ covariance matrix. This can easily be verified by
checking the covariance matrix of $\mathbf{n}$;

$\begin{aligned}
Cov(\mathbf{n})=&Cov(\mathbf{V}_{r}\bm{\Lambda}_{r}^{1/2}\mathbf{z})=\mathbf{V}_{r}\bm{\Lambda}_{r}^{1/2}Cov(\mathbf{z})(\mathbf{V}_{r}\bm{\Lambda}_{r}^{1/2})^{T}\\\
\stackrel{{\scriptstyle(*)}}{{=}}&\mathbf{V}_{r}\bm{\Lambda}_{r}^{1/2}\mathbf{I}_{r\times
r}(\mathbf{V}_{r}\bm{\Lambda}_{r}^{1/2})^{T}=\mathbf{V}_{r}\bm{\Lambda}_{r}\mathbf{V}_{r}^{T}=\bm{\Pi}\end{aligned},$
(8)

where $(*)$ is due to
$\mathbf{z}\sim\mathcal{N}(\mathbf{0},\mathbf{I}_{r\times r})$. Then clearly,
$Cov(\mathbf{n})=r$.

When $r=1$, the singular covariance matrix $\bm{\Pi}$ only has 1 non-zero
singular value, and we denote it as $\sigma_{*}$. As a result, (7) becomes

$\mathbf{n}=\mathbf{v}\sqrt{\sigma_{*}}z,\quad\mathrm{and}\quad
z\sim\mathcal{N}(0,1),\quad\mathbf{v}^{T}\mathbf{v}=1.$ (9)

Singular multivariate Gaussian noise with a random rank-1 covariance matrix.
It is noteworthy that in (9), $\mathbf{v}$ needs to be generated randomly to
thwart attacks which takes advantage of sensing vectors in the null space of
$\mathbf{v}$ (or $\mathbf{n}$). In Section 5.3, we will show that by sampling
$\mathbf{v}$ uniformly at random, such attacks will success with zero
probability.

Since $\mathbf{v}$ is an orthonormal vector of dimension $M\times 1$, one
common approach to generate $\mathbf{v}$ randomly is by uniformly sampling
from a specific Stiefel manifold, i.e.,
$\mathbb{V}_{1,M}=\\{\mathbf{v}\in\mathbb{R}^{M\times
1}:\mathbf{v}^{T}\mathbf{v}=1\\}$, which represents the unite sphere
$\mathbb{S}^{M-1}$ embedded in $\mathbb{R}^{M}$. In Statistics literature, the
PDF of the _uniform distribution on the Stiefel manifold $\mathbb{V}_{1,M}$_
is given by

$f(\mathbf{v})=\frac{1}{\mathrm{Vol}(\mathbb{V}_{1,M})},\quad\forall\mathbf{v}\in\mathbb{V}_{1,M},$
(10)

(see page 280 of [21], page 17, equation 8.2.2 of [8], as well as page 30 of
[12] which gives the characteristic function of (10)). In particular, the
constant $\mathrm{Vol}(\mathbb{V}_{1,M})=\frac{2\pi^{M/2}}{\Gamma(M/2)}$ (see
page 19 and 26 of [21]) is the total volume of $\mathbb{V}_{1,M}$ and
$\Gamma(\cdot)$ is the ordinary gamma function [21].444This result can be
easily obtained by setting $p=1$ in Theorem 1.4.9 on page 25 of [21]. The
physical meaning of $\mathrm{Vol}(\mathbb{V}_{1,M})$ can be interpreted by
draw an analogy with an uniform distribution on 1D Euclidean space, i.e.,
uniform distribution on interval $[a,b]$ has PDF $f(x)=\frac{1}{b-a}$, and
$b-a$ is the total length (i.e., measure) of $[a,b]$. Technically speaking,
$\mathrm{Vol}(\mathbb{V}_{1,M})$ plays the same role on $\mathbb{V}_{1,M}$
that the Lebesgue measure plays in Euclidean space [8]. In the special cases,
when $M=3$, $\mathrm{Vol}(\mathcal{V}_{1,3})=4\pi$ is the surface area of an
unit sphere in 3D space, and when $M=2$,
$\mathrm{Vol}(\mathcal{V}_{1,2})=2\pi$ is the circumference of an unit circle
in 2D space.

We use $\mathbf{v}\sim\mathcal{U}(\mathbb{V}_{1,M})$ to represent that
$\mathbf{v}$ is a random variable uniformly sampled from $\mathbb{V}_{1,M}$.
As a consequence, the linear mapping defined in (9) becomes

$\displaystyle\mathbf{n}=\mathbf{v}\sqrt{\sigma_{*}}z,\quad\text{where}\quad
z\sim\mathcal{N}(0,1),\quad\mathbf{v}\sim\mathcal{U}(\mathbb{V}_{1,M}).$ (11)

Now, we introduce the proposed R$1$SMG and provide a sufficient condition for
it to achieve differential privacy.

######  Definition 8.

The Proposed R$1$SMG. Given a high dimensional query
$f(\bm{x})\in\mathbb{R}^{M}$, R$1$SMG is defined as

$\mathcal{M}_{R1SMG}\Big{(}f(\bm{x})\Big{)}=f(\bm{x})+\mathbf{n},$

where $\mathbf{n}$ (generated via (11)) is the noise attributed to a singular
multivariate Gaussian distribution with a random rank-$1$ covaraince matrix.

######  Theorem 5.

R$1$SMG achieves $(\epsilon,\delta)$-DP, if
$\sigma_{*}\geq\frac{2(\Delta_{2}f)^{2}}{\epsilon\psi}$, where
$\psi=\left(\frac{\delta\Gamma(\frac{M-1}{2})}{\sqrt{\pi}\Gamma(\frac{M}{2})}\right)^{\frac{2}{M-2}}$,
and $\Gamma(\cdot)$ is Gamma function.

###### Proof.

First, we review an important lemma in the following.

######  Lemma 1.

Distribution of Angle between Random Points on Unit Sphere (see page 1845 and
1860 of [7]). Let $h$ and $g$ be two randomly selected points on unit sphere
$\mathbb{S}^{P-1}$ (embedded in $\mathbb{R}^{P}$). Let $\mathbf{h}$ (resp.
$\mathbf{g}$) be the vector connecting the center of the sphere and $h$ (resp.
$g$). $\theta$ denotes the angle ($\theta\in[0,\pi]$) between $\mathbf{h}$ and
$\mathbf{g}$. Then

$\Pr\left[\left|\theta-\frac{\pi}{2}\right|\geq\theta_{0}\right]\leq\sqrt{\pi}\frac{\Gamma(\frac{P}{2})}{\Gamma(\frac{P-1}{2})}cos(\theta_{0})^{P-2},$
(12)

where $\theta_{0}$ is a given radian and $0\leq\theta_{0}\leq\frac{\pi}{2}$.

Inspired by Dwork and Roth’s work [17] (cf. Section 4), we investigate the
PRLV associated with R1SMG. Assume that $\mathbf{n}$ and $\mathbf{n}^{\prime}$
are the random noise used to perturb $f(\bm{x})$ and $f(\bm{x}^{\prime})$.
Then, R1SMG achieves $(\epsilon,\delta)$-DP if
$\mathrm{PLRV}^{(\mathbf{s})}_{(R1SMG(\bm{x})||R1SMG(\bm{x}^{\prime}))}=\ln\left(\frac{\Pr[f(\bm{x})+\mathbf{n}=\mathbf{s}\in\mathcal{S}]}{\Pr[f(\bm{x}^{\prime})+\mathbf{n}^{\prime}=\mathbf{s}\in\mathcal{S}]}\right)\leq\epsilon$
with all but $\delta$ probability (called the failing probability), where
$\mathcal{S}$ denotes all possible outcome of R1SMG.

According to (11), without loss of generality, let

$\mathbf{n}=\sqrt{\sigma_{*}}z_{1}\mathbf{h},\quad\mathbf{n}^{\prime}=\sqrt{\sigma_{*}}z_{2}\mathbf{g},$
(13)

where $z_{1},z_{2}\sim\mathcal{N}(0,1)$ and
$\mathbf{h},\mathbf{g}\sim\mathcal{U}(\mathbb{V}_{1,M})$. Let
$\theta\in[0,\pi]$ be the angle between $\mathbf{h}$ and $\mathbf{g}$. Then,
we can establish the failing probability (which should be at most $\delta$) by
first constructing an event which is a subspace of the universe $\Omega$,
i.e.,

$\begin{aligned}
&\leavevmode\resizebox{455.3023pt}{}{$\mathcal{A}=\left\\{z_{1},z_{2},\mathbf{h},\mathbf{g}:z_{1},z_{2}\sim\mathcal{N}(0,1),\mathbf{h},\mathbf{g}\sim\mathcal{U}(\mathbb{V}_{1,M}),\left|\theta-\frac{\pi}{2}\right|<\theta_{0}\right\\}$}\\\
&\subset\Omega=\\{z_{1},z_{2},\mathbf{h},\mathbf{g}:z_{1},z_{2}\sim\mathcal{N}(0,1),\mathbf{h},\mathbf{g}\sim\mathcal{U}(\mathbb{V}_{1,M})\\}\end{aligned},$

where
$\theta_{0}=arccos\left(\left(\frac{\delta\Gamma(\frac{M-1}{2})}{\sqrt{\pi}\Gamma(\frac{M}{2})}\right)^{\frac{1}{M-2}}\right)$,
and $arccos(\cdot)$ is the inverse of the cosine function. We denote the
complementary of $\mathcal{A}$ as
$\mathcal{A}^{c}=\Omega\setminus\mathcal{A}$, i.e.,

$\mathcal{A}^{c}=\left\\{z_{1},z_{2},\mathbf{h},\mathbf{g}:z_{1},z_{2}\sim\mathcal{N}(0,1),\mathbf{h},\mathbf{g}\sim\mathcal{U}(\mathbb{V}_{1,M}),\left|\theta-\frac{\pi}{2}\right|\geq\theta_{0}\right\\}.$

Since $z_{1}$ and $z_{2}$ are independent of $\mathbf{h}$ and $\mathbf{g}$, by
applying Lemma 1 and setting $P=M$ and
$\sqrt{\pi}\frac{\Gamma(\frac{P}{2})}{\Gamma(\frac{P-1}{2})}cos(\theta_{0})^{P-2}=\delta$,
we establish the failing probability as $\Pr[\mathcal{A}^{c}]\leq\delta$.

As a result, it suffices to find a condition to make the following hold

$\ln\left(\frac{\Pr[f(\bm{x})+\mathbf{n}=\mathbf{s}\in\mathcal{S}]}{\Pr[f(\bm{x}^{\prime})+\mathbf{n}^{\prime}=\mathbf{s}\in\mathcal{S}]}\right)\leq\epsilon,\quad\forall(z_{1},z_{2},\mathbf{h},\mathbf{g})\in\mathcal{A}.$
(14)

Since $\mathbf{n}$ (resp. $\mathbf{n}^{\prime}$) is singular multivariate
Gaussian with zero mean by design (see (11)). Thus
$f(\bm{x})+\mathbf{n}=\mathbf{s}\in\mathcal{S}$ (resp.
$f(\bm{x}^{\prime})+\mathbf{n}^{\prime}=\mathbf{s}\in\mathcal{S}$) is
attributed to singular multivariate Gaussian distribution, with mean
$f(\bm{x})$ (resp. $f(\bm{x}^{\prime})$) and covariance matrix
$\mathbf{h}\sigma_{*}\mathbf{h}^{T}$ (resp.
$\mathbf{g}\sigma_{*}\mathbf{g}^{T}$) (one can verify this by setting $r=1$ in
(8)). Plugging the mean and generalized inverse covariance matrix into the PDF
provided in Definition 7 (with $r=1$), we have

$\displaystyle\mathrm{PLRV}^{(\mathbf{s})}_{(R1SMG(\bm{x})||R1SMG(\bm{x}^{\prime}))}=\ln\left(\frac{\Pr[f(\bm{x})+\mathbf{n}=\mathbf{s}\in\mathcal{S}]}{\Pr[f(\bm{x}^{\prime})+\mathbf{n}^{\prime}=\mathbf{s}\in\mathcal{S}]}\right)$
(15) $\displaystyle=$
$\displaystyle\leavevmode\resizebox{424.94574pt}{}{$\ln\left(\frac{{(2\pi)^{-\frac{1}{2}}\exp\left(-\frac{1}{2}\big{(}\mathbf{s}-f(\bm{x})\big{)}^{T}\big{(}\mathbf{h}\sigma_{*}^{-1}\mathbf{h}^{T}\big{)}\big{(}\mathbf{s}-f(\bm{x})\big{)}\right)}\Big{/}{\sqrt{\sigma_{*}}}}{{(2\pi)^{-\frac{1}{2}}\exp\left(-\frac{1}{2}\big{(}\mathbf{s}-f(\bm{x}^{\prime})\big{)}^{T}\big{(}\mathbf{g}\sigma_{*}^{-1}\mathbf{g}^{T}\big{)}\big{(}\mathbf{s}-f(\bm{x}^{\prime})\big{)}\right)}\big{/}{\sqrt{\sigma_{*}}}}\right)$}$
$\displaystyle=$
$\displaystyle\ln\left(\frac{\exp\left(-\frac{1}{2\sigma_{*}}\Big{(}\mathbf{h}^{T}(\mathbf{s}-f(\bm{x}))\Big{)}^{2}\right)}{\exp\left(-\frac{1}{2\sigma_{*}}\Big{(}\mathbf{g}^{T}(\mathbf{s}-f(\bm{x}^{\prime}))\Big{)}^{2}\right)}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{2\sigma_{*}}\left(\Bigg{(}\underbrace{\mathbf{g}^{T}(\mathbf{s}-f(\bm{x}^{\prime}))}_{\rho_{1}\in\mathbb{R}}\Bigg{)}^{2}-\Bigg{(}\underbrace{\mathbf{h}^{T}(\mathbf{s}-f(\bm{x}))}_{\rho_{2}\in\mathbb{R}}\Bigg{)}^{2}\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{2\sigma_{*}}\Big{(}|\rho_{1}|+|\rho_{2}|\Big{)}^{2}.$

In what follows, we derive tight upper bound on $|\rho_{1}|+|\rho_{2}|$. In
particular, with $||\mathbf{g}||_{2}=||\mathbf{h}||_{2}=1$, we notice that

$\displaystyle\begin{aligned}
|\rho_{1}|+|\rho_{2}|&\leq||\mathbf{g}||_{2}||\mathbf{s}-f(\bm{x}^{\prime})||_{2}+||\mathbf{h}||_{2}||\mathbf{s}-f(\bm{x})||_{2}\\\
&=||\mathbf{s}-f(\bm{x}^{\prime})||_{2}+||\mathbf{s}-f(\bm{x})||_{2},\end{aligned}$

Thus, we just need to bound
$||\mathbf{s}-f(\bm{x}^{\prime})||_{2}+||\mathbf{s}-f(\bm{x})||_{2}$.

First, we observe that the angle between $(\mathbf{s}-f(\bm{x}))$ and
$(\mathbf{s}-f(\bm{x}^{\prime}))$ is identical to the angle between
$\mathbf{h}$ and $\mathbf{g}$, because $(\mathbf{s}-f(\bm{x}))=\mathbf{n}$ and
$(\mathbf{s}-f(\bm{x}^{\prime}))=\mathbf{n}^{\prime}$, and $\mathbf{n}$ and
$\mathbf{n}^{\prime}$ are obtained by scaling $\mathbf{h}$ and $\mathbf{g}$.
We use $\theta$ to represent the angle between $\mathbf{h}$ and $\mathbf{g}$
(i.e., identically between $(\mathbf{s}-f(\bm{x}))$ and
$(\mathbf{s}-f(\bm{x}^{\prime}))$). Thus, from a geometric perspective,
$||\mathbf{s}-f(\bm{x}^{\prime})||_{2}+||\mathbf{s}-f(\bm{x})||_{2}$ is the
sum of the length of two edges of a triangle in $\mathbb{R}^{M}$, and the
angle between these two edges is $\theta$. Moreover, the length of the third
edge (opposite to this specific angle) is
$||(\mathbf{s}-f(\bm{x}^{\prime}))-(\mathbf{s}-f(\bm{x}))||_{2}=||f(\bm{x})-f(\bm{x}^{\prime})||_{2}$.
For better understanding, we visualize the above description in Figure 1(a),
where the red point (resp. blue point) indicates $\mathbf{n}$ (resp.
$\mathbf{n}^{\prime}$) in $\mathbb{R}^{M}$, and the red dashed line (resp.
blue dashed line) is the randomly sampled $\mathbf{h}$ (resp. $\mathbf{g}$)
(note that we show $\mathbf{h}$ and $\mathbf{g}$ as bidirectional, because
$\mathbf{n}$ and $\mathbf{n}^{\prime}$ can point to the opposite direction of
$\mathbf{h}$ and $\mathbf{g}$, respectively).

Figure 1: (a) Geometric interpretation of $|\rho_{1}|+|\rho_{2}|$.
Circumcircles of the described triangle with (b) $\theta<\frac{\pi}{2}$ and
(c) $\theta>\frac{\pi}{2}$.

It is well know that the length of each edge of a triangle is upper bounded by
the diameter of the circumscribed circle of the triangle. We demonstrate this
fact in Figure 1(b) and (c), where $\frac{d}{2}$ represents the radius of the
circumcircle. According to the law of sine, we have
$d=||f(\bm{x})-f(\bm{x}^{\prime})||_{2}\big{/}{sin(\theta)}$. Thus,

$\displaystyle||\mathbf{s}-f(\bm{x}^{\prime})||_{2}+||\mathbf{s}-f(\bm{x})||_{2}$
(16) $\displaystyle\leq$ $\displaystyle
2d=2||f(\bm{x})-f(\bm{x}^{\prime})||_{2}\big{/}{sin(\theta)}\leq\frac{2\Delta_{2}f}{sin(\theta)},$

where the last inequality is because the query sensitivity on neighboring
datasets is
$\Delta_{2}f=\max_{\bm{x}\sim\bm{x}^{\prime}}||f(\bm{x})-f(\bm{x}^{\prime})||_{2}$.

In (14), we require $(z_{1},z_{2},\mathbf{h},\mathbf{g})\in\mathcal{A}$, i.e.,
$\theta\in(\frac{\pi}{2}-\theta_{0},\frac{\pi}{2}+\theta_{0})$,
$\theta_{0}\in[0,\frac{\pi}{2}]$, and due to the symmetry of sine function
around $\frac{\pi}{2}$, the maximum value of
$\frac{2\Delta_{2}f}{sin(\theta)}$ is smaller than
$\frac{2\Delta_{2}f}{sin(\frac{\pi}{2}-\theta_{0})}$, which is equivalent to
$\frac{2\Delta_{2}f}{cos(\theta_{0})}$. Since
$\theta_{0}=arccos\left(\left(\frac{\delta\Gamma(\frac{M-1}{2})}{\sqrt{\pi}\Gamma(\frac{M}{2})}\right)^{\frac{1}{M-2}}\right)$
(given in event $\mathcal{A}$), we have

$\displaystyle\begin{aligned}
|\rho_{1}|+|\rho_{2}|\leq&||\mathbf{s}-f(\bm{x}^{\prime})||_{2}+||\mathbf{s}-f(\bm{x})||_{2}\\\
<&\frac{2\Delta_{2}f}{cos(\theta_{0})}=2\Delta_{2}f\Bigg{/}\left(\frac{\delta\Gamma(\frac{M-1}{2})}{\sqrt{\pi}\Gamma(\frac{M}{2})}\right)^{\frac{1}{M-2}}.\end{aligned}$

Combining the above results with (14) and (LABEL:eq:needs-to-show2), we obtain
the sufficient condition for the proposed R$1$SMG to achieve
$(\epsilon,\delta)$-differential privacy as
$\frac{1}{2\sigma_{*}}(|\rho_{1}|+|\rho_{2}|)^{2}\leq\frac{1}{2\sigma_{*}}\left(2\Delta_{2}f\Bigg{/}\left(\frac{\delta\Gamma(\frac{M-1}{2})}{\sqrt{\pi}\Gamma(\frac{M}{2})}\right)^{\frac{1}{M-2}}\right)^{2}\leq\epsilon\Leftrightarrow\sigma_{*}\geq\frac{2(\Delta_{2}f)^{2}}{\epsilon\psi}$.
∎

Implementation of R1SMG. According to the following theorem, we can obtain the
desired random variable supported on the Stiefel manifold by transforming
samples drawn i.i.d. from standard Gaussian distribution.

######  Theorem 6 (Generating Random Samples from $\mathbb{V}_{r,M}$ (cf. page
29, Theorem 2.2.1.(iii) of [12])).

Let $\mathbf{x}\in\mathbb{R}^{M\times r}$, whose elements are i.i.d. sampled
from $\mathcal{N}(0,1)$. Then
$\mathbf{v}=\mathbf{x}(\mathbf{x}^{T}\mathbf{x})^{-1/2}$ is uniformly
distributed on $\mathbb{V}_{r,M}$.

As a result, we can apply Theorem 6 with $r=1$ to draw the desired samples
from $\mathbb{V}_{1,M}$. Then, applying (11), we can generate a noise instance
of the proposed R1SMG. Note due to the constraint of a sphere (which should be
embedded in at least a 3D space), we require $M>2$ for our proposed R1SMG.

###  5.2 Asymptotic Behavior

Curse Lifted. At this point, we can do a quick check that the expected
accuracy loss introduced by R$1$SMG is $Tr[\bm{\Pi}]$, which is not the
summation of $M$ positive values any more;

$\displaystyle\begin{aligned}
&\mathbb{E}_{R1SMG}[\mathcal{L}]=\mathbb{E}[||\mathbf{n}||_{2}^{2}]\\\
=&\mathbb{E}_{\mathclap{\begin{subarray}{c}\\\ \\\ \\\
z\sim\mathcal{N}(0,1),\mathbf{v}\sim\mathcal{U}(\mathbb{V}_{1,M})\end{subarray}}}\Big{[}(\mathbf{v}\sigma_{*}^{1/2}z)^{T}\mathbf{v}\sigma_{*}^{1/2}z]=\sigma_{*}\mathbb{E}[z^{2}]=\sigma_{*},\end{aligned}$
(17)

and the last equality holds because $z^{2}\sim\chi^{2}(1)$ and the expected
value of chi-squared distributed variable is its degree of freedom. (17)
clearly shows that we have lifted the identified curse by considering noise
attributed to a singular multivariate Gaussian distribution with rank-1
covariance matrix.

Moreover, we prove that $\mathbb{E}_{R1SMG}[\mathcal{L}]$ decreases with
dimension of the query result ($M$), and if $M$ goes to infinity,
$\mathbb{E}_{R1SMG}[\mathcal{L}]$ converges to a constant, which means only
constant amount of noise is need to perturb $f(\bm{x})\in\mathbb{R}^{M}$. This
result is one of the main contributions of our proposed R1SMG.

######  Theorem 7.

For any fixed $\epsilon>0,0<\delta<1$, given a dataset $\bm{x}$ and a query
result $f(\bm{x})\in\mathbb{R}^{M}$.
$\mathbb{E}_{R1SMG}[\mathcal{L}]=||R1SMG(f(\bm{x}))-f(\bm{x})||_{2}^{2}$
monotonically decreases with $M$. When $M\rightarrow+\infty$,
$\mathbb{E}_{R1SMG}[\mathcal{L}]\rightarrow\frac{2(\Delta_{2}f)^{2}}{\epsilon}$.

###### Proof.

First, by plugging $\psi$ in Theorem 5, we have
$\frac{2\Delta_{2}f^{2}}{\epsilon\psi}=\frac{2\Delta_{2}f^{2}}{\epsilon}\left(\frac{\sqrt{\pi}\Gamma(\frac{M}{2})}{\delta\Gamma(\frac{M-1}{2})}\right)^{\frac{2}{M-2}}=\frac{2\Delta_{2}f^{2}}{\epsilon}\exp\left(\frac{2}{M-2}\ln\left(\frac{\sqrt{\pi}\Gamma(\frac{M}{2})}{\delta\Gamma(\frac{M-1}{2})}\right)\right).$
By connecting $\frac{\Gamma(\frac{M}{2})}{\Gamma(\frac{M-1}{2})}$ to the
normalization constant of the Beta distribution $Beta(\alpha,\beta)$ with
$\alpha=\frac{M-1}{2}$ and $\beta=\frac{1}{2}$, it gives
$\frac{\Gamma(\frac{M}{2})}{\Gamma(\frac{M-1}{2})}\stackrel{{\scriptstyle
a}}{{\sim}}\frac{\sqrt{M-2}}{\sqrt{2}}$ [14], where $\stackrel{{\scriptstyle
a}}{{\sim}}$ means asymptotic equivalence. Hence, we have
$\frac{2\Delta_{2}f^{2}}{\epsilon\psi}\stackrel{{\scriptstyle
a}}{{\sim}}\frac{2\Delta_{2}f^{2}}{\epsilon}\exp\left(\frac{2}{M-2}\ln\left(\frac{\sqrt{\pi}}{\delta}\frac{\sqrt{M-2}}{\sqrt{2}}\right)\right)$,
which is a monotonically decreasing function w.r.t. $M$.

When $M\rightarrow\infty$, we have

$\displaystyle\lim_{M\rightarrow\infty}\frac{2\Delta_{2}f^{2}}{\epsilon\psi}\stackrel{{\scriptstyle
a}}{{\sim}}$
$\displaystyle\frac{2\Delta_{2}f^{2}}{\epsilon}\exp\left(\lim_{M\rightarrow\infty}\frac{2}{M-2}\ln\left(\frac{\sqrt{\pi}}{\delta}\frac{\sqrt{M-2}}{\sqrt{2}}\right)\right)$
$\displaystyle\stackrel{{\scriptstyle(*)}}{{=}}$
$\displaystyle\frac{2\Delta_{2}f^{2}}{\epsilon}\exp(0)=\frac{2\Delta_{2}f^{2}}{\epsilon},$

where $(*)$ is due to the l’Hôpital’s Rule. ∎

######  Remark 1.

The “magic” (the expected accuracy loss of R1SMG decreases with $M$) can also
be interpreted from a geometric perspective. From the proof of Theorem 5, we
know $\sigma_{*}=\frac{2(\Delta_{2}f)^{2}}{\epsilon sin^{2}(\theta)}$, where
$\theta$ is the angle between the noise ($\mathbf{n}$ and
$\mathbf{n}^{\prime}$) used to perturb $f(\bm{x})$ and $f(\bm{x}^{\prime})$.
Since $\mathbf{n}$ and $\mathbf{n}^{\prime}$ are scaled variables sampled from
the unit sphere, and as the dimension increases, the angle $\theta$ quickly
concentrates around $\frac{\pi}{2}$ (at the rate of $\sqrt{M}$ [7]), which
makes $\sigma_{*}$ converges to $\frac{2(\Delta_{2}f)^{2}}{\epsilon}$.

In Appendix A, we provide an intuitive explanation of the unique “magic” of
R1SMG by using counting queries as an example. In Appendix B, we plot the
empirical $\mathbb{E}[\mathcal{L}]$ versus $M$ achieved by R1SMG and other
mechanisms, and clearly show that
$\mathbb{E}_{R1SMG}[\mathcal{L}]=\frac{2\Delta_{2}f^{2}}{\epsilon\psi}$
monotonically decrease with $M$, whereas the other increase with $M$ (cf.
Figure 6).

###  5.3 Discussion on Privacy Leakage of Utilizing Sensing Vector in the Null
Space of $\mathbf{v}$

Our proposed R$1$SMG does not span the entire space of $\mathbb{R}^{M}$, thus,
it may raise concern of privacy leakage if one takes advantage of the sensing
vector in the null space of $\mathbf{v}$. To be more specific, let
$\mathbf{s}$ be the output of R$1$SMG and $\mathbf{u}\in Null(\mathbf{v})$,
i.e., $<\mathbf{u},\mathbf{v}>=0$. Since $\mathbf{n}\in Span(\mathbf{v})$, one
can have

$<\mathbf{u},\mathbf{s}>=<\mathbf{u},f(\bm{x})+\mathbf{n}>=<\mathbf{u},f(\bm{x})>,$

which implies potential privacy leakage of queries on $f(\bm{x})$.

However, we need to highlight that $\mathbf{v}$ is randomly sampled from
$\mathcal{U}(\mathbb{V}_{1,M})$, which is an intermediate noise to produce the
final noise of R$1$SMG and will not be made public. Note that this is not
against the core idea of differential privacy, i.e., “privacy without
obscurity", because the entire noise generation process, i.e, (11), including
the choice of distribution parameters are transparent. As a result, the
probability that a constructed $\mathbf{u}$ that is in the null space of a
randomly sampled $\mathbf{v}$ is zero, i.e., $\Pr[\mathbf{u}\in
Null(\mathbf{v})]=\frac{\mu(Null(\mathbf{v}))}{\mu(\mathbb{R}^{M})}=0$, where
$\mu(\cdot)$ denotes the Lebesgue measure of a measurable set.

In Appendix C, we give toy examples illustrating $\Pr[\mathbf{u}\in
Null(\mathbf{v})]=0$ in $\mathbb{R}^{2}$ and $\mathbb{R}^{3}$. In particular,
in $\mathbb{R}^{2}$, $\mathbb{V}_{1,2}$ is the unit circle, and
$Null(\mathbf{v})$ only contains two fixed points. In $\mathbb{R}^{3}$,
$\mathbb{V}_{1,3}$ is the unit sphere, and $Null(\mathbf{v})$ is a fixed
circle (see Figure 7 in Appendix C).

##  6 Stability of Various Mechanisms

Now, we evaluate the accuracy stability achieved by various output
perturbation mechanisms by studying the kurtosis and skewness of the
distribution of $\mathcal{L}$ (the non-deterministic accuracy loss defined in
Definition 1). In particular,

  * •

Kurtosis, a descriptor of “tail extremity” of a probability distribution, is
defined as the ratio between the $4$th moment and the square of the $2$nd
moment of a random variable, i.e.,
$\frac{\mathbb{E}[\mathcal{L}^{4}]}{(\mathbb{E}[\mathcal{L}^{2}])^{2}}$. A
larger kurtosis means that outliers or extreme large values are less likely to
be generated in a given probability distribution [44].

  * •

Skewness, a descriptor of the “bulk” of a probability distribution, is defined
as the ratio between the $3$rd moment and the square root of the cube of the
$2$nd moment of a random variable, i.e.,
$\frac{\mathbb{E}[\mathcal{L}^{3}]}{(\mathbb{E}[\mathcal{L}^{2}])^{3/2}}$. A
larger skewness means that the bulk of the samples is at the left region of
the PDF and the right tail is longer.

As a result, to have high accuracy stability on the perturbed query result,
$\mathcal{L}$ with both larger kurtosis and skewness is preferred. We
summarize the theoretical results for various mechanisms in Theorem 8 and 9.

######  Theorem 8.

The kurtosis of the distribution of $\mathcal{L}$ from R1SMG is $\frac{35}{3}$
which is larger than that of the classic Gaussian mechanism and the MVG
mechanism, i.e., the PDF of $\mathcal{L}$ from R1SMG is more leptokurtic than
that from the classic Gaussian mechanism and the MVG mechanism.

###### Proof.

First, for the proposed R1SMG, we have

$\displaystyle\begin{aligned} &{\rm{Kurt}_{R1SMG}}(\mathcal{L})\\\
&\leavevmode\resizebox{433.62pt}{}{$=\frac{\mathbb{E}[\mathcal{L}^{4}]}{(\mathbb{E}[\mathcal{L}^{2}])^{2}}\stackrel{{\scriptstyle(a)}}{{=}}\frac{\mathbb{E}\left[\left((\mathbf{v}\sqrt{\sigma_{*}}z)^{T}\mathbf{v}\sqrt{\sigma_{*}}z\right)^{4}\right]}{\left(\mathbb{E}\left[\left((\mathbf{v}\sqrt{\sigma_{*}}z)^{T}\mathbf{v}\sqrt{\sigma_{*}}z\right)^{2}\right]\right)^{2}}=\frac{\mathbb{E}\left[(z\sigma_{*}z)^{4}\right]}{\left(\mathbb{E}\left[(z\sigma_{*}z)^{2}\right]\right)^{2}}$}\\\
&\stackrel{{\scriptstyle(b)}}{{=}}\frac{48\sigma_{*}^{4}+32\sigma_{*}^{3}\sigma_{*}+12(\sigma_{*}^{2})^{2}+12\sigma_{*}^{2}(\sigma_{*})^{2}+(\sigma_{*})^{4}}{\big{(}2\sigma_{*}^{2}+(\sigma_{*})^{2}\big{)}^{2}}=\frac{35}{3},\end{aligned}$

where $(a)$ is due to the noise generation process of R1SMG in (11) and $(b)$
is obtained by applying Theorem 4 with $\mathbf{A}=1$ and
$\bm{\Xi}=\sigma_{*}$ (i.e., the case of univariant Gaussian).

Then, we show that both classic Gaussian mechanism and the MVG mechanism will
result in $\mathcal{L}$ with kurtosis less than $\frac{35}{3}$. In particular,
the classic Gaussian mechanism (denoted as $\mathcal{G}$) adds i.i.d. noise to
each entry of $f(\bm{x})$,
$\mathbf{n}_{i}\sim\mathcal{N}(0,\sigma^{2}),i\in[1,M]$. Thus, we have
$\mathbb{E}_{\mathcal{G}}[\mathcal{L}^{t}]=\mathbb{E}_{z_{i}\sim\mathcal{N}(0,1)}\left[\left(\sum_{i}\sigma^{2}z_{i}^{2}\right)^{t}\right]=\sigma^{2t}\mathbb{E}_{U\sim\chi^{2}(M)}[U^{t}]=\sigma^{2t}2^{t}\frac{\Gamma(t+\frac{M}{2})}{\Gamma(\frac{M}{2})}$,
where the last equality follows from the $t$th moments of Chi-squared random
variable. Set $t$ to be 4 and 2, one can verify that
${\rm{Kurt}_{\mathcal{G}}}(\mathcal{L})=\frac{\mathbb{E}_{\mathcal{G}}[\mathcal{L}^{4}]}{(\mathbb{E}_{\mathcal{G}}[\mathcal{L}^{2}])^{2}}={\sigma^{8}2^{4}\frac{\Gamma(4+\frac{M}{2})}{\Gamma(\frac{M}{2})}}\Bigg{/}{\left(\sigma^{4}2^{2}\frac{\Gamma(2+\frac{M}{2})}{\Gamma(\frac{M}{2})}\right)^{2}}<\frac{35}{3},\forall
M>1.$

MVG introduces the matrix-valued noise attributed to a matrix-valued Gaussian
distribution, i.e., $\mathcal{N}(\mathbf{0},\bm{\Sigma},\bm{\Psi})$, and the
vectorization of the noise matrix is also attributed to a multivariate
Gaussian distribution, i.e.,
$\mathcal{N}(\mathbf{0},\bm{\Sigma}\otimes\bm{\Psi})$ [21]. Thus, according to
Theorem 4,

$\displaystyle\begin{aligned}
&{\rm{Kurt}_{MVG}}(\mathcal{L})=\frac{\mathbb{E}[\mathcal{L}^{4}]}{(\mathbb{E}[\mathcal{L}^{2}])^{2}}=\frac{\mathbb{E}[Q(\mathbf{n})^{4}]}{(\mathbb{E}[Q(\mathbf{n})^{2}])^{2}}\\\
=&\frac{48Tr\bm{\Xi}^{4}+32Tr\bm{\Xi}^{3}Tr\bm{\Xi}+12(Tr\bm{\Xi}^{2})^{2}+12Tr\bm{\Xi}^{2}(Tr\bm{\Xi})^{2}+(Tr\bm{\Xi})^{4}}{\big{(}2Tr\bm{\Xi}^{2}+(Tr\bm{\Xi})^{2}\big{)}^{2}}.\end{aligned}$

Besides, for any positive integer $k$, we have

$\displaystyle\begin{aligned}
(Tr\bm{\Xi})^{k}&=(Tr\bm{\Sigma}\otimes\bm{\Psi})^{k}=(Tr\bm{\Sigma}\cdot
Tr\bm{\Psi})^{k}=\left[\left(\sum_{i=1}^{{\rm{rank}}(\bm{\Sigma})}\sigma_{i}(\bm{\Sigma})\right)\left(\sum_{j=1}^{{\rm{rank}}(\bm{\Psi})}\sigma_{j}(\bm{\Psi})\right)\right]^{k}\\\
&>\sum_{i=1,j=1}^{{\rm{rank}}(\bm{\Sigma}),{\rm{rank}}(\bm{\Psi})}\big{(}\sigma_{i}(\bm{\Sigma})\sigma_{j}(\bm{\Psi})\big{)}^{k}=Tr(\bm{\Sigma}\otimes\bm{\Psi})^{k}.\end{aligned}$

Hence,
${\rm{Kurt}_{MVG}}(\mathcal{L})<\frac{105(Tr\bm{\Xi})^{4}}{9Tr(\bm{\Sigma}\otimes\bm{\Psi})^{4}}<\frac{35}{3}$.
∎

######  Theorem 9.

The skewness of the distribution of $\mathcal{L}$ from R1SMG is
$\frac{5\sqrt{3}}{3}$ which is larger than that of the classic Gaussian
mechanism and the MVG mechanism, i.e., the PDF of $\mathcal{L}$ from the R1SMG
is more right-skewed than that from the classic Gaussian mechanism and the MVG
mechanism.

###### Proof.

The proof follows the same procedure with the proof of Theorem 8, thus we only
show the key steps here.

For the proposed R1SMG, we have
${\rm{skew}_{\mathrm{R1SMG}}}(\mathcal{L})=\frac{\mathbb{E}[\mathcal{L}^{3}]}{(\mathbb{E}[\mathcal{L}^{2}])^{3/2}}=\frac{\mathbb{E}\left[(z\sigma_{*}z)^{3}\right]}{\left(\mathbb{E}\left[(z\sigma_{*}z)^{2}\right]\right)^{3/2}}=\frac{\sigma_{*}^{3}2^{3}\frac{\Gamma(3+\frac{1}{2})}{\Gamma(\frac{1}{2})}}{\left(\sigma_{*}^{2}2^{2}\frac{\Gamma(2+\frac{1}{2})}{\Gamma(\frac{1}{2})}\right)^{3/2}}=\frac{5\sqrt{3}}{3}.$

For the classic Gaussian mechanism, one can verify that
${\rm{skew}_{\mathcal{G}}}(\mathcal{L})=\frac{\sigma_{G}^{6}2^{3}\frac{\Gamma(3+\frac{M}{2})}{\Gamma(\frac{M}{2})}}{\left(\sigma_{G}^{4}2^{2}\frac{\Gamma(2+\frac{M}{2})}{\Gamma(\frac{M}{2})}\right)^{3/2}}=\frac{\frac{\Gamma(3+\frac{M}{2})}{\Gamma(\frac{M}{2})}}{\left(\frac{\Gamma(2+\frac{M}{2})}{\Gamma(\frac{M}{2})}\right)^{3/2}}<\frac{5\sqrt{3}}{3},\forall
M>1$.

For the MVG mechanism, it is easy to check that
${\rm{skew}_{MVG}}(\mathcal{L})=\frac{\big{(}8Tr\bm{\Xi}^{3}+6Tr\bm{\Xi}^{2}Tr\bm{\Xi}+(Tr\bm{\Xi})^{3}\big{)}}{\big{(}2Tr\bm{\Xi}^{2}+(Tr\bm{\Xi})^{2}\big{)}^{3/2}}$,
where $\bm{\Xi}=\bm{\Sigma}\otimes\bm{\Psi}$. Besides, we have already shown
that for any positive integer $k$,
$(Tr\bm{\Xi})^{k}>Tr(\bm{\Sigma}\otimes\bm{\Psi})^{k}.$ Thus, we get
${\rm{skew}_{MVG}}(\mathcal{L})<\frac{15(Tr\bm{\Xi})^{3}}{(3Tr(\bm{\Sigma}\otimes\bm{\Psi})^{2})^{3/2}}<\frac{35}{3}$,
which completes the proof. ∎

######  Remark 2.

We can consider the univariate Gaussian with unit covariance, i.e.,
$\mathcal{N}(\mu,1)$, as a reference distribution, whose kurtosis value and
skewness value are $3$ and $0$, respectively. Then, it suggests that the
distribution of $\mathcal{L}$ from R1SMG are much more leptokurtic and right-
skewed than $\mathcal{N}(\mu,1)$. Moreover, since the noises used in the
classic (and analytic) Gaussian mechanism and MVG mechanism are characterized
by full-rank covariance matrices, their kurtosis value and skewness value
asymptotically converge to $3+12/H$ and $\sqrt{8/H}$, respectively [26] ($H$
is the degree of freedom of the obtained $\mathcal{L}$, and $H=M$ for
$f(\bm{x})\in\mathbb{R}^{M}$). It means that the distributions of
$\mathcal{L}$ resulted from the Gaussian mechanism and MVG are similar to
$\mathcal{N}(\mu,1)$ when $M$ is large. Based on the above theoretical
analysis, we can conclude that R1SMG outperforms the classic Gaussian
mechanism, the analytic Gaussian mechanism, and the MVG mechanism, because it
boosts the utility of the query result by achieving low (expected) accuracy
loss and higher accuracy stability.

In Section 7.1, by using 2D count query as an example, we will empirically
show that the distribution of $\mathcal{L}$ obtained by R1SMG is more
leptokurtic and right-skewed than that of the classic, analytic Gaussian, and
the MVG mechanism (cf. Figure 3). In other words, R1SMG returns differentially
private query results with highest accuracy stability.

##  7 Experiments

In this section, we conduct three case studies to validate the utility
boosting achieved by the proposed R1SMG, i.e., 2D count query, principal
component analysis (PCA), and deep learning, all in a differentially private
manner. The query results of these case studies are either matrices or
tensors, so R1SMG and classic (analytic) Gaussian mechanisms will first
generate noise in vector format, and then reshape the noise into the format
required by different studies.

###  7.1 Study i@: Uber Pickup Count Query

In this case study, we consider the New York City Uber pickups dataset [2],
and we are interested in releasing the counts of Uber pickups in different
areas of NYC from “4/1/2014 00:11:00” to “4/3/2014 23:57:00” in a
differentially private manner.555We choose 3 days instead of more days for a
better visualization result. The size of the count query $f(\bm{x})$ is
determined by the partition areas (defined later) of NYC. Location and
trajectory privacy breaches have been reported and investigated in several
research works, e.g., [34, 45, 24, 37], thus, it is important to guarantee
that the existence or absence of any pickup record is private when sharing the
count query.

In particular, we partition the map of NYC into small areas by evenly dividing
the latitude and longitude into 89 disjoint intervals.666Note that one can
also choose arbitrary partition size in practice [23], here we just consider
89 as an example. As a result, the considered query is
$f(\bm{x})\in\mathbb{R}^{89\times 89}$, whose entries record the number of
Uber pickups in different small areas. The sensitivity of this query is 2,
because the absence or presence of a specific pickup can change 2 entries of
$f(\bm{x})$ by 1. We also consider that the data consumer (i.e., the query
result recipient) has the prior knowledge of the valid pickup areas in the
resulted $89\times 89$ small areas. Thus, he can perform post-processing on
the noisy count query to eliminate the values in invalid areas (e.g., it is
impossible to have Uber pickups over the Hudson River). We visualize the non-
private Uber pickup count query in Figure 2(a). We observe that, in addition
to the high volumes of pickups around SOHO and Fifth avenue, there are also
large pickup counts near LaGuardia Airport.

|
---|---
(a) Non-private | (b) R1SMG
|
(c) classic Gauss. | (d) Analytic Gauss.
|
(e) MVG | (f) MGM
|
(g) DAWA | (h) $H_{b}$
Figure 2: Visualization of (a) non-private counts in bird’s eye view, (b)-(h)
are differentially private 2D counts obtained by R1SMG, classic Gaussian,
analytic Gaussian, MVG, MGM, DAWA, and $H_{b}$ mechanism.

Comparing Mechanisms. In additional to the $(\epsilon,\delta)$-DP output
perturbation mechanisms, i.e., classic, analytic
Gaussian,777https://github.com/BorjaBalle/analytic-gaussian-mechanism.
MVG,888https://github.com/inspire-group/MVG-Mechansim., and MGM ([46] a
variant of MVG). We also compare with the mechanisms that are specially
developed for differentially private 2D count queries. In particular, they are
(i) DAWA [33], which obtains differentially private count queries by adding
noise that is adapted to both the input data and the given query set, and (ii)
$H_{b}$ [40], which answers range queries using noisy hierarchies of equi-
width histograms.999Source code of both DAWA and $H_{b}$ are available at
https://github.com/dpcomp-org/dpcomp_core.

Results. Now, we visualize the differential-privately released count queries
obtained by the proposed R1SMG and other comparing mechanisms in Figure
2(b)-(h). The privacy budgets for all considered mechanismsm are
$\epsilon=0.5$ and $\delta=10^{-7}$. Clearly, R1SMG outperforms all the
comparing output perturbation mechanisms (i.e., Figure 2(c)-(f)), as it
preserves the global and local patterns of the non-private count query in
Figure 2(a). In contrast, the classic Gaussian, MVG, and MGM mechanism
compromise the utility of the count query the most. For example, in Figure
2(c), (e), and (f) many areas on the Manhattan island have no pickup counts,
and the maximum count is also increased significantly (i.e., higher than 60,
50, and 40 compared to the non-private maximum count which is only 25).
Although the analytic Gaussian mechanism outperforms the classic Gaussian and
MVG mechanism by calibrating the noise variance exactly, it still introduces
noise with higher magnitude than R1SMG. Finally, we observe that R1SMG has
comparable performance with DAWA and $H_{b}$ that are developed specially for
differentially private range queries. The error over ground truth ratio, i.e.,
$||\mathcal{M}(f(\bm{x}))-f(\bm{x})||_{F}/||f(\bm{x})||_{F}$ ($\mathcal{M}$
stands for a general mechanism), introduced by R1SMG, DAWA, and $H_{b}$ are
$0.47\%$, $0.43\%$, and $0.72\%$, respectively. Note that DAWA has better
results, because it is data-dependent (the noise is customized to the input
data [33]). $H_{b}$ has better results, as it adopts “constrained inference”
(an accuracy boosting scheme) to control the mean square error of counting
queries at various granularity. Although R1SMG introduces larger errors than
the two task-specific mechanisms under the approximately same privacy
guarantees (with additional $\delta$ probability), it is still very promising
in other real-world tasks, because it is not task-dependent and can be applied
to different applications.

|
---|---
(a) $\mathcal{L}$ of R1SMG | (b) $\mathcal{L}$ of classic Gaussian
|
(c) $\mathcal{L}$ of analytic Gaussian | (d) $\mathcal{L}$ of MVG
Figure 3: Accuracy loss introduced by different output perturbation mechanisms
when $\epsilon=0.5$ and $\delta=10^{-7}$.

Utility boosting and stability. Next, we empirically corroborate that the
proposed R1SMG boosts the utility of the NYC Uber pickup count query by
achieving lower accuracy loss and higher accuracy stability. Specifically, by
setting $\epsilon=0.5$ and $\delta=10^{-7}$, we repeat the noise generation
process for classic, analytic Gaussian, and MVG mechanisms 100 times, and
calculate the accuracy loss ($\mathcal{L}$, in Definition 1). In Figure 3, we
plot the corresponding histograms, empirical average values of $\mathcal{L}$,
and the empirical PDFs, obtained by different mechanisms. The plots associated
with R1SMG, classic Gaussian, analytic Gaussian, and MVG mechanisms are show
in Figure 3(a)-(d), respectively.

Figure 3 shows that the empirical mean obtained by using R1SMG is less than
that obtained by the other mechanisms. This means that under the same privacy
guarantee, R1SMG introduces additive noise with the least amount of magnitude
(squared Frobenius norm), which lead to lower empirical accuracy loss. In
particular, $\mathcal{L}$ obtained from R1SMG are in the order of $10^{3}$,
whereas, $\mathcal{L}$ obtained from the other mechanisms are all in the order
of $10^{4}$. We can also find that the histogram and the empirical PDF of
$\mathcal{L}$ obtained by R1SMG are much more leptokurtic and right-skewed
than that achieved by the others. This is because compared with Figure 3(b),
(c) and (d), Figure 3(a) has longer and fatter tail, higher and sharper
central peak, and the density is almost distributed at the left side. However,
empirical PDFs in Figure 3(b), (c), and (d) all have bell shapes, which
corroborate the analysis in Remark 2. Thus, R1SMG can reduce greatly the
probability that the additive perturbation noise having large magnitude.

###  7.2 Study ii@: Principal Component Analysis

In this case study, we consider differentially private PCA using the Swarm
Behaviour dataset [1] as an example. It contains 24016 records of flocking
behaviour (i.e., the way that groups of birds, insects, fish or other animals,
move close to each other). Each record has 2400 features characterizing a
flocking observation, e.g., radius of separation of groups of insects, moving
direction, moving velocity, etc. Each data record is assigned a binary label,
and “1" represents “flocking behavior" and “0" represents “not flocking". The
values of all features are normalized between $-1$ and $1$. Similar to [10],
we consider the query $f(\bm{x})$ as the covariance matrix of this dataset,
i.e., $f(\bm{x})={D^{T}D}/{24016}\in\mathbb{R}^{2400\times 2400}$, where
$D\in\mathbb{R}^{24016\times 2400}$ denotes the considered Swarm Behaviour
data.101010Since covariance matrices are symmetric, the data consumer will
perform post processing
$\big{(}\mathcal{M}(f(\bm{x}))+\mathcal{M}(f(\bm{x}))^{T}\big{)}/2$ to obtain
symmetric result. The privacy guarantee naturally holds due to the post-
processing immunity [17]. Then, the $l_{2}$ sensitivity of the query function
is
$s_{2}(f)=\sup_{D_{1},D_{2}}\frac{||{D_{1}}(i)^{T}{D_{1}}(i)-{D_{2}}(i)^{T}{D_{2}}(i)||_{F}}{24016}=\frac{\sqrt{2\times
2400^{2}}}{24016}=\frac{2400\sqrt{2}}{24016}$ (cf. Appendix B of [10]), where
$D_{1}$ and $D_{2}$ are two neighboring Swarm Behavior datasets, the first
equality is obtained by assuming the only different sensor record is at the
$i$th row of $D_{1}$ and $D_{2}$, i.e., ${D_{1}}(i)$ and ${D_{2}}(i)$, and the
second equality is because a single observation can change all $2400^{2}$
entries of $D^{T}D$ by 2.

We conduct singular value decomposition on the queried result (i.e., the noisy
empirical covariance matrix) to extract the components of the dataset. The
considered evaluation metric is the total deviation which is defined as
$\Delta=\textstyle\sum_{i=1}^{2041}\Delta_{i}=\textstyle\sum_{i=1}^{2041}|\lambda_{i}-\widetilde{\mathbf{v}_{i}}^{T}\mathbf{C}\widetilde{\mathbf{v}_{i}}|$,
where $\mathbf{C}$ is the ground-truth (non-private) empirical covariance
matrix, $\lambda_{i}$ is the $i$th eigenvalue of $\mathbf{C}$, and
$\widetilde{\mathbf{v}_{i}}$ is the $i$th differentially private component
(singular vector). Specifically, $\Delta_{i}$ quantifies the deviation of the
variance from $\lambda_{i}$ in the direction of the $i$th component. The
smaller $\Delta$ is, the higher utility the obtained components have, and we
have $\Delta=0$ for the non-private baseline.

Since PCA is usually served as a precursor to classification task, we also
evaluate the utility of the queried data by projecting the dataset onto the
subspace spanned by the first 20 PCs obtained from various noisy covariance
matrices, and then measure the classification accuracy using the projected
data. The higher the classification accuracy, the higher the utility of the
perturbed covariance matrix. In the experiments, we use $60\%$ and $40\%$ of
the dataset for training and testing, respectively, and the classification
algorithm is the linear SVM. Note that the accuracy of the non-private
baseline (i.e., classification using the original dataset project onto the
first 20 PCs of the original covariance matrix) is $96.89\%$.

Comparing Mechanisms. In addition to the output perturbation mechanisms, we
also consider the principal components obtained from 3 task-specific
differentially private algorithms designed specially for PCA, i.e., (i) PPCA
[11], which generates privacy-preserving components by sampling orthonormal
matrices from matrix Bingham distribution parametermized by the original non-
private empirical covariance matrix scaled by the privacy budget, (ii) MOD-
SULQ [11], which directly perturbs the covariance matrix using carefully
calibrated Gaussian noise, and (iii) the Wishart mechanism [25], which
perturbs the empirical covariance matrices using noise attributed to the
Wishart distribution.

|
---|---
(a) Deviation versus $\epsilon$. | (b) Accuracy versus $\epsilon$.
Figure 4: Utility of the noisy covariance matrices obtained by various
mechanisms. (a) The total deviation. (b) The classification accuracy measured
on the projected testing dataset.

Results. In this experiment, we vary $\epsilon$ from $0.2$ to $1.6$ and set
$\delta=10^{-7}$. Figure 4(a) and (b) plots the total derivation ($\Delta$)
and classification accuracy on the projected testing data obtained from all
mechanisms. Clearly, R1SMG has the highest utility given all the privacy
budgets and is also the closest to the non-private baselines (i.e., $\Delta=0$
and $96.89\%$ accuracy). This is because R1SMG introduces perturbation noise
with smaller magnitudes under the same privacy guarantee, whereas, the noise
magnitude introduced by the comparing output perturbation mechanisms are much
higher. Take the MVG mechanism as an example, according to Theorem 3, when
$\epsilon=1.6$ and $\delta=10^{-7}$, MVG requires
$||\sigma(\bm{\Sigma}^{-1})||_{2}||\sigma(\bm{\Psi}^{-1})||_{2}\leq 0.011$ to
achieve the desired privacy guarantee. This means the covariance matrices will
have very large singular values, which implies large expected accuracy loss
(as discussed in Section 3) and causes the original data be overwhelmed in the
additive noise. Actually, according to [10], for MVG to have a decent
performance on differentially private PCA, it requires $\epsilon\geq 5$. In
this case study, R1SMG even outperforms PPCA, MOD-SULQ, and Wishart mechanism.
In other words, R1SMG not only achieves the lowest $\Delta$, but also gives
the highest classification accuracy for all the chosen $\epsilon$. This
suggests that R1SMG is very promising in boosting the accuracy of high-
dimensional differentially private query. Note that in this study, R1SMG also
achieves the most stable accuracy, i.e., the accuracy loss introduced by it
has leptokurtic and right-skewed histogram and empirical PDF, but the others
still have bell-shaped empirical PDFs (similar to Figure 3), we omit the plots
due to space limit.

###  7.3 Study iii@: Deep Learning with DP

In this case study, we show the feasibility of replacing the classic Gaussian
mechanism with the proposed R1SMG in the DPSGD (differentially private
stochastic gradient descent) optimization framework, and validate that R1SMG
can boost the utility (testing accuracy) of a differentially-private deep
learning model and improve its training efficiency by reducing the number of
epochs. Please note that this case study is not intended to be comprehensive,
as differentially-private deep learning constitutes a distinct research
direction in its own right.

As a proof of concept, we consider the standard MNIST handwritten digit
dataset, which consists 60,000 training images and 10,000 testing images [32],
and compare our R1SMG-based DPSGD with the seminal work of DPSGD in deep
learning (Abadi et al. CCS’16 [3]). For a given deep neural network, Abadi et
al. introduce calibrated i.i.d. Gaussian noise
($\mathcal{N}(0,\sigma^{2}C^{2}\mathbf{I})$) to the gradients computed on
grouped batches of training data, where $C$ is a norm clipping parameter to
control the sensitivity (Algorithm 1 in [3]). They also developed the privacy
accountant scheme to tightly bound the cumulative privacy loss for the entire
training process. In particular, the total privacy budget $(\epsilon,\delta)$
is determined by noise level $\sigma$, sampling ratio $q$, and the number of
epochs $E$ (so number of gradient descent steps is $T=E/q$).

In the experiment, we give our R1SMG-based DPSGD the same total privacy budget
$(\epsilon,\delta)$, $C$, $q$, and $E$ with that of Abadi et al. Then, we
amortize $(\epsilon,\delta)$ to all gradient descent steps in our R1SMG-based
DPSGD, i.e., each step is assigned with $(\epsilon_{0},\delta_{0})$. To be
more specific, $(\epsilon_{0},\delta_{0})$ is obtained by solving the
following equations formulated using the strong composition theorem [19]
considering $\frac{E}{q}$ repetitive executions of gradient descent.

$\begin{cases}&\epsilon=\sqrt{2\frac{E}{q}\ln\left(\frac{1}{\delta^{\prime}}\right)}(q\epsilon_{0})+\frac{E}{q}(q\epsilon_{0})\left(e^{(q\epsilon_{0})}-1\right)\\\
&\delta=\frac{E}{q}(q\delta_{0})+\delta^{\prime}\end{cases},$ (18)

where $q\epsilon_{0}$ and $q\delta_{0}$ are due to privacy amplification via
sampling [6, 27] (see discussion on page 3, right column of [3]). For example,
based on the TensorFlow tutorial for DPSGD on MNIST [38], when $C=1$,
$\sigma=1.1$, $q=\frac{256}{60000}$, and $E=30$, it leads to $\epsilon=1.795$.
Then, set $\delta=10^{-5}$, $\delta^{\prime}=10^{-10}$ and solve (18), we have
$(\epsilon_{0},\delta_{0})=(0.71,3.33\times 10^{-7})$. When $C=1$,
$\sigma=0.5$, $q=\frac{256}{60000}$, and $E=30$, it leads
$(16.983,10^{-5})$-DP for classic DPSGD, which makes
$(\epsilon_{0},\delta_{0})=(5.42,3.33\times 10^{-7})$ for our R1SMG-based
DPSGD.

Note that using strong composition theorem to assign amortized privacy budget
to each step of our R1SMG-based DPSGD actually gives more favor to the classic
Gaussian mechanism based DPSGD in the comparison. This is because strong
composition is much looser than the privacy accountant scheme used in the
classic DPSGD (empirically validated by Figure 2 of [3]), thus, the amortized
$(\epsilon_{0},\delta_{0})$ can be limited. Developing a tight composition
framework for R1SMG in SGD-based learning will be a separate research topic.

Even though the classic DPSGD is given more favor in the comparison, our
R1SMG-based DPSGD still outperforms it by achieving higher training and
testing accuracy. We show the comparison results for the above parameters
setups in Figure 5. In particular, Figure 5(a) and (b) show the training and
testing accuracy for the first 30 epochs achieved by various approaches when
the entire learning process is $(1.795,10^{-5})$-DP and $(16.983,10^{-5})$-DP
(discussed above), respectively. The blue lines and dashed lines in Figure 5
are the result of non-private SGD (the one uses original gradients calculated
from the data).

---
(a) The entire learning process is $(1.795,10^{-5})$-DP.
(b) The entire learning process is $(16.983,10^{-5})$-DP.
Figure 5: Comparison of training and testing accuracy.

Clearly, compared with classic DPSGD, R1SMG-based DPSGD can achieve higher
training and testing accuracy in just a few epochs. For example, when the
entire privacy budget is $(16.983,10^{-5})$, our method achieves 95% accuracy
on the testing dataset using 5 epochs, whereas classic DPSGD requires 14
epochs. Our R1SMG-based DPSGD also leads to performance that is closer to the
non-private baseline, because even though the amortized privacy budget for
each R1SMG-based DPSGD step is limited, the magnitude of the perturbation
noise introduced by R1SMG is much less than that required by the classic
DPSGD.

##  8 Related Work

In the literature, many works have attempted to improve the classic Gaussian
mechanism. Here, we review some representative ones.

The analytic Gaussian mechanism proposed by Balle et al. [5] (see Theorem 2)
improves the classic Gaussian mechanism by calibrating the variance of the
Gaussian noise directly using the Gaussian cumulative density function instead
of the tail bound approximation, and develop an analytical solution to the
variance given specific choices $\epsilon$ and $\delta$. Although this
mechanism can reduce the magnitude of the noise when perturbing a scalar-
valued quantity, it still suffers the curse of full-rank covariance matrices
when applied to perturb high-dimensional query result (as discussed in Section
3).

Zhao et al. [47] investigate the classic Gaussian mechanism under high privacy
budgets, i.e., $\epsilon>1$, and derive a closed-form upper bounds for the
noise variance used in the analytic Gaussian mechanism. Their mechanism can
achieve utility higher than the classic Gaussian mechanisms, but still lower
than the analytic Gaussian mechanism.

Chanyaswad et al. [10] (see Definition 4 and Theorem 3) propose the MVG
mechanism and develop the technique of directional noise to restrict the
impact of the perturbation noise on the utility of a matrix-valued query
function. However, to obtain the directional noise, one either needs a domain
expert to determine the principal components of the queried data or has to
calculate them via principal component analysis which consumes some privacy
budget. Besides, as we have shown in Section 3, the expected accuracy loss of
the MVG mechanism also increases linearly with the size of the query result
due to our identified curse.

Some other variants of the classic Gaussian mechanism includes the Generalized
Gaussian mechanism [35], which investigates noise calibration under the
general $l_{p}$ sensitivity, and the discrete Gaussian mechanism [9], which
uses noise attributed to discrete Gaussian distribution to protect the privacy
of query results in a discrete domain.

Our proposed R1SMG differs with the above-mentioned mechanisms, as we
explicitly require the covariance matrix of the additive noise to be rank-1.
Thus, R1SMG lifts the identified curse and boost the utility of high
dimensional query results. Additionally, by leveraging the randomness of the
angle between random unit vectors, R1SMG can also provide more privacy at much
lower cost of accuracy.

##  9 Conclusions

In this paper, we have proposed a novel mechanism, i.e., R1SMG, to boost the
utility (accuracy) of differentially-private high dimensional query results.
In particular, we first identified the curse of full-rank covariance matrices
in all existing variants of the classic Gaussian mechanism. Then, we lift the
curse by developing R1SMG which perturbs the query results using singular
multivariate Gaussian distribution with random rank-1 covariance matrix. By
introducing additional randomness when generating singular vector of the
rank-1 covariance matrix, the proposed R1SMG can boost the utility of the
query results significantly given limited privacy budget. Notably, in R1SMG,
the expected accuracy loss to achieve certain level of privacy guarantee
decreases with the dimension of the query results, i.e., less is more. We
rigorously analyze the privacy guarantee of R1SMG, and theoretically
demonstrate that R1SMG can achieve lower accuracy loss and higher accuracy
stability than the classic Gaussian, analytic Gaussian, and the MVG mechanism.

## References

  * [1] Swarm behaviour dataset.  https://archive.ics.uci.edu/ml/datasets/Swarm+Behaviour.  (Accessed on 02/20/2021).
  * [2] Uber pickups in new york city.  https://www.kaggle.com/fivethirtyeight/uber-pickups-in-new-york-city.  (Accessed on 02/20/2021).
  * [3] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308–318, 2016.
  * [4] Mir M Ali.  Characterization of the normal distribution among the continuous symmetric spherical class.  Journal of the Royal Statistical Society: Series B (Methodological), 42(2):162–164, 1980.
  * [5] Borja Balle and Yu-Xiang Wang.  Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising.  In International Conference on Machine Learning, pages 394–403. PMLR, 2018.
  * [6] Amos Beimel, Hai Brenner, Shiva Prasad Kasiviswanathan, and Kobbi Nissim.  Bounds on the sample complexity for private learning and private data release.  Machine learning, 94:401–437, 2014.
  * [7] Tony Cai, Jianqing Fan, and Tiefeng Jiang.  Distributions of angles in random packing on spheres.  Journal of Machine Learning Research, 14(21):1837–1864, 2013.
  * [8] Gabriel Camano-Garcia.  Statistics on Stiefel manifolds.  Iowa State University, 2006.
  * [9] Clément L Canonne, Gautam Kamath, and Thomas Steinke.  The discrete gaussian for differential privacy.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 15676–15688. Curran Associates, Inc., 2020.
  * [10] Thee Chanyaswad, Alex Dytso, H. Vincent Poor, and Prateek Mittal.  Mvg mechanism: Differential privacy under matrix-valued query.  In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS ’18, pages 230–246, New York, NY, USA, 2018. ACM.
  * [11] Kamalika Chaudhuri, Anand Sarwate, and Kaushik Sinha.  Near-optimal differentially private principal components.  Advances in Neural Information Processing Systems, 25:989–997, 2012\.
  * [12] Yasuko Chikuse.  Statistics on special manifolds, volume 174.  Springer Science & Business Media, 2012.
  * [13] Harald Cramér.  Mathematical methods of statistics, volume 43.  Princeton university press, 1999.
  * [14] Jack D’Aurizio.  How to show $\frac{\Gamma((n-1)/2)}{\Gamma(n/2)}=\frac{\sqrt{2}}{\sqrt{n-2}}$.  Mathematics Stack Exchange, https://math.stackexchange.com/q/3007170.
  * [15] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor.  Our data, ourselves: Privacy via distributed noise generation.  In Serge Vaudenay, editor, Advances in Cryptology - EUROCRYPT 2006, pages 486–503, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
  * [16] 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, pages 265–284. Springer, 2006.
  * [17] Cynthia Dwork and Aaron Roth.  The algorithmic foundations of differential privacy.  Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014.
  * [18] Cynthia Dwork and Guy N Rothblum.  Concentrated differential privacy.  arXiv preprint arXiv:1603.01887, 2016.
  * [19] Cynthia Dwork, Guy N Rothblum, and Salil Vadhan.  Boosting and differential privacy.  In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 51–60. IEEE, 2010.
  * [20] David H Fremlin.  Measure theory, volume 4.  Torres Fremlin, 2000.
  * [21] Arjun K Gupta and Daya K Nagar.  Matrix variate distributions.  Chapman and Hall/CRC, 2018.
  * [22] Moritz Hardt and Kunal Talwar.  On the geometry of differential privacy.  In Proceedings of the forty-second ACM symposium on Theory of computing, pages 705–714, 2010.
  * [23] Michael Hay, Ashwin Machanavajjhala, Gerome Miklau, Yan Chen, and Dan Zhang.  Principled evaluation of differentially private algorithms using dpbench.  In Proceedings of the 2016 International Conference on Management of Data, pages 139–154. ACM, 2016.
  * [24] Kaifeng Jiang, Dongxu Shao, Stéphane Bressan, Thomas Kister, and Kian-Lee Tan.  Publishing trajectories with differential privacy guarantees.  In Proceedings of the 25th International Conference on Scientific and Statistical Database Management, pages 1–12, 2013.
  * [25] Wuxuan Jiang, Cong Xie, and Zhihua Zhang.  Wishart mechanism for differentially private principal components analysis.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
  * [26] Norman L Johnson, Samuel Kotz, and Narayanaswamy Balakrishnan.  Continuous univariate distributions, volume 2, volume 289.  John wiley & sons, 1995.
  * [27] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.  What can we learn privately?  SIAM Journal on Computing, 40(3):793–826, 2011.
  * [28] Chinubhai G Khatri.  Some results for the singular normal multivariate regression models.  Sankhyā: The Indian Journal of Statistics, Series A, pages 267–280, 1968.
  * [29] Donald Ervin Knuth.  The art of computer programming, volume 3.  Pearson Education, 1997.
  * [30] Valentin Fedorovich Kolchin and Valentin Fedorovich Kolchin.  Random graphs.  Number 53. Cambridge University Press, 1999.
  * [31] Koon-Shing Kwong and Boris Iglewicz.  On singular multivariate normal distribution and its applications.  Computational statistics and data analysis, 22(3):271–285, 1996\.
  * [32] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * [33] Chao Li, Michael Hay, Gerome Miklau, and Yue Wang.  A data-and workload-aware algorithm for range queries under differential privacy.  Proceedings of the VLDB Endowment, 7(5), 2014.
  * [34] Changchang Liu, Supriyo Chakraborty, and Prateek Mittal.  Dependence makes you vulnberable: Differential privacy under dependent tuples.  In NDSS, volume 16, pages 21–24, 2016.
  * [35] Fang Liu.  Generalized gaussian mechanism for differential privacy.  IEEE Transactions on Knowledge and Data Engineering, 31(4):747–756, 2018.
  * [36] Aleksandar Nikolov, Kunal Talwar, and Li Zhang.  The geometry of differential privacy: the sparse and approximate cases.  In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 351–360, 2013.
  * [37] Lu Ou, Zheng Qin, Shaolin Liao, Yuan Hong, and Xiaohua Jia.  Releasing correlated trajectories: Towards high utility and optimal differential privacy.  IEEE Transactions on Dependable and Secure Computing, 17(5):1109–1123, 2018.
  * [38] TensorFlow Privacy.  TensorFlow Privacy: MNIST DP-SGD Tutorial.  https://github.com/tensorflow/privacy/blob/master/tutorials/mnist_dpsgd_tutorial.py, 2023\.  Accessed on: 02/24.
  * [39] Serge B Provost and AM Mathai.  Quadratic forms in random variables: theory and applications.  M. Dekker, 1992.
  * [40] Wahbeh Qardaji, Weining Yang, and Ninghui Li.  Understanding hierarchical methods for differentially private histograms.  Proceedings of the VLDB Endowment, 6(14):1954–1965, 2013.
  * [41] Calyampudi Radhakrishna Rao and Mathematischer Statistiker.  Linear statistical inference and its applications, volume 2.  Wiley New York, 1973.
  * [42] Muni Shanker Srivastava and CG Khatri.  An introduction to multivariate statistics.  2009\.
  * [43] Meng Sun and Wee Peng Tay.  On the relationship between inference and data privacy in decentralized iot networks.  IEEE Transactions on Information Forensics and Security, 15:852–866, 2019.
  * [44] Peter H Westfall.  Kurtosis as peakedness, 1905–2014. rip.  The American Statistician, 68(3):191–195, 2014.
  * [45] Yonghui Xiao and Li Xiong.  Protecting locations with differential privacy under temporal correlations.  In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 1298–1309, 2015.
  * [46] Jungang Yang, Liyao Xiang, Jiahao Yu, Xinbing Wang, Bin Guo, Zhetao Li, and Baochun Li.  Matrix gaussian mechanisms for differentially-private learning.  IEEE Transactions on Mobile Computing, 2021.
  * [47] Jun Zhao, Teng Wang, Tao Bai, Kwok-Yan Lam, Zhiying Xu, Shuyu Shi, Xuebin Ren, Xinyu Yang, Yang Liu, and Han Yu.  Reviewing and improving the gaussian mechanism for differential privacy.  arXiv preprint arXiv:1911.12060, 2019.

##  Appendix A Intuitive Explanation of the the Counterintuitive “Magic”

R1SMG brings an unique property (the 2nd contribution in Section 1.2). This
property is missing in all existing DP mechanisms. Here, we provide an
intuitive explanation to this property. To do so, we first present it
informally in Property 1. A formal version (Theorem 7) is proved in Section
5.2.

######  Property 1.

Unique Property of R1SMG (Informal). For any fixed $\epsilon$ and $\delta$,
the magnitude of the noise required by R1SMG to attain $(\epsilon,\delta)$-DP
on $f(\bm{x})\in\mathbb{R}^{M}$ is non-increasing with $M$. For sufficiently
large $M$, the magnitude of the noise is a constant.

An intuitive explanation. Due to the widely accepted common practice of
perturbing each component of $f(\bm{x})$ using i.i.d. Gaussian noise to
achieve DP, it makes sense that larger dimensional $f(\bm{x})$ requires larger
magnitude of noises. Thus, Property 1 is counterintuitive and seems to be a
“magic”. Yet, it can be intuitively explained via an example of database
querying. Consider each component of $f(\bm{x})$ as a scalar-valued query
result obtained from the database $\bm{x}$. Higher dimension of $f(\bm{x})$
means larger number of queries applied on the same $\bm{x}$. The query results
can become dependent with each other as the query number increases. Suppose
the $i$th and $j$th query, i.e., $f(\bm{x})_{i}$ and $f(\bm{x})_{j}$, are
dependent (in other words, the mutual information between $f(\bm{x})_{i}$ and
$f(\bm{x})_{j}$ is 0 [43]), thus the privacy leakage on $\bm{x}$ by observing
$f(\bm{x})_{i}$, $f(\bm{x})_{j}$, or $[f(\bm{x})_{i}\ f(\bm{x})_{j}]$ is
identical. Hence, intuitively, the same amount of noise can be used to perturb
$f(\bm{x})_{i}$, $f(\bm{x})_{j}$, and $[f(\bm{x})_{i}\ f(\bm{x})_{j}]$. It
implies that as $M$ increases and the queried results become dependent, it is
possible to achieve DP by perturbing $f(\bm{x})$ using noise with non-
increasing magnitude. In what follows, we provide an informal technical
reasoning for the above example.

An informal reasoning. We consider $f(\cdot)$ as count queries for example.
Given a database $\bm{x}$ represented as histogram, a set of $M$ counting
queries can be represented as a binary matrix
$Q\in\\{0,1\\}^{M,|\mathcal{X}|}$. Then, $f(\bm{x})=Q\bm{x}\in\mathbb{R}^{M}$
is the query results. For simplicity, we assume that each element of $Q$ has
equal probability of being 0 or 1. If $M>|\mathcal{X}|$, the query vectors
(rows in $Q$) are linearly dependent, i.e., given $|\mathcal{X}|$ independent
query results, the other $M-|\mathcal{X}|$ results can be determined. In other
words, by observing $f(\bm{x})$ or the set of $|\mathcal{X}|$ independent
query, the privacy leakage of $\bm{x}$ are identical. Thus, the same amount of
noises can be used to sanitize both (refer to [43] for an analysis from the
perspective of mutual information). Thus, noise with constant magnitude can
protect the privacy of $f(\bm{x})$ for sufficiently large $M$.

Now we consider the case where $M\leq|\mathcal{X}|$. Suppose that $Q$ has
$M_{1}$ independent rows, then the space spanned by $Q$ has dimension $M_{1}$
(i.e., $rank(Q)=M_{1}\leq|\mathcal{X}|$). Adding a new row to $Q$ leaves the
rank unchanged with probability $2^{M_{1}-|\mathcal{X}|}$ (see Chapter 3.2,
page 127 of [30]). In other words, rows in $Q$ becomes linear dependent with
probability $2^{M_{1}-|\mathcal{X}|}$. When $M_{1}$ increases from 1 to
$|\mathcal{X}|$, the probability of $Q$ becomes rank deficiency also
increases. This implies that there is an increasing probability that a higher
dimensional $f(\bm{x})$ will lead to the same amount of privacy leakage
compared with a lower dimensional $f(\bm{x})$.

Combing the non-increasing privacy leakage as $M$ increases and constant
privacy leakage when $M$ is sufficiently large. It essentially suggests that
less amount of noise can sanitize higher dimensional query results, when $M$
goes to infinity, the magnitude of the noise should be a constant. We
rigorously prove this in Section 5.2.

##  Appendix B $\mathbb{E}[\mathcal{L}]$ versus $M$ for Various Mechanisms

We empirically investigate the accuracy loss of the query results
$f(\bm{x})\in\mathbb{R}^{M}$ when $M$ is increasing. In Figure 6, by assuming
$\Delta_{2}f=1$, varying $M$ from $10^{2}$ to $10^{10}$, and fixing
$\delta=10^{-7}$, we plot the expected accuracy loss introduced by our
proposed R1SMG, classical Gaussian, and analytic Gaussian mechanism when
$\epsilon\in\\{0.01,0.1,1\\}$. Note that we do not include MVG mechanism in
the comparison, because (i) it requires the prior knowledge of
$\gamma=\sup_{\bm{x}}||f(\bm{x})||_{F}$, which depends on specific datasets
and applications (e.g., see Theorem 3), and (ii) the analytic Gaussian
mechanism is known to achieve less error than MVG.

Figure 6: Expected accuracy loss of R1SMG, classical Gaussian, and analytic
Gaussian mechanism under increasing query size (i.e., $M$) when
$\epsilon\in\\{0.01,0.1,1\\}$ and $\delta=10^{-7}$.

From Figure 6, we observe that, for both classical and analytic Gaussian
mechanisms, the expected utility loss (i.e., $Tr[\sigma^{2}\mathbf{I}_{M\times
M}]$ and $Tr[\sigma_{A}^{2}\mathbf{I}_{M\times M}]$) scales linearly with $M$,
which validates our theoretical findings in Section 3. In contrast, as $M$
increases, the expected accuracy loss caused by R1SMG (i.e.,
$Tr[\bm{\Pi}]=\sigma_{*}$) decreases and converges to
$\frac{2(\Delta_{2}f)^{2}}{\epsilon}$. As discussed in Section 5.2,
$\sigma_{*}$ is proportional to $1/\psi$ and $\sqrt{\psi}$ is the result of
sine function applied a random angle in high dimension. Since the angle
quickly approaches to $\frac{\pi}{2}$ as $M$ increases, which causes $1/\psi$
decrease. Thus, the proposed R1SMG not only breaks the curse of full rank
covariance, but also significantly improves the accuracy (utility) of the
perturbed $f(\bm{x})$, as it is able to achieve $(\epsilon,\delta)$-DP by
using decreasing amount noise when the dimension of $f(\bm{x})$ increases.

##  Appendix C Toy Examples on $\Pr[\mathbf{u}\in Null(\mathbf{v})]=0$

Here, we give toy examples in $\mathbb{R}^{2}$ and $\mathbb{R}^{3}$ (when
$M=2$ and $M=3$). Note that in practice R1SMG requires $M>2$, here we use
$\mathbb{R}^{2}$ just to visualize the idea (the probability that a
constructed $\mathbf{u}$ that is in the null space of a randomly sampled
$\mathbf{v}$ is zero) which is actually independent of the dimensionality.

Particularly, in $\mathbb{R}^{2}$, $\mathbb{V}_{1,2}$ is the unit circle shown
in Figure 7 (left). Suppose $\mathbf{v}_{1}=[-1/\sqrt{5},2/\sqrt{5}]^{T}$ is
the randomly sampled variable in $\mathbb{V}_{1,2}$, then
$Null(\mathbf{v}_{1})$ is $\mathcal{I}$ (the dashed line orthogonal to
$\mathbf{v}_{1}$). Clearly, the probability of sampling a point from
$\mathbb{R}^{2}$ that resides on a specific line is 0. Likewise, in
$\mathbb{R}^{3}$, $\mathbb{V}_{1,3}$ is the unit sphere shown in Figure 7
(right). Suppose $\mathbf{v}_{2}=[1/\sqrt{3},-1/\sqrt{3},1/\sqrt{3}]^{T}$ is
the randomly sampled variable in $\mathbb{V}_{1,3}$, then
$Null(\mathbf{v}_{2})$ is $\mathcal{F}$ (the plane orthogonal to
$\mathbf{v}_{2}$). The probability of sampling a point from $\mathbb{R}^{3}$
that resides on a specific plane is also 0. Although, it is publicly known
that $\mathbf{v}$ is sampled from $\mathcal{U}(\mathbb{V}_{1,M})$, the
Lebesgue measure of $Null(\mathbf{v})$ (given
$\mathbf{v}\subset\mathbb{V}_{1,M}$) is still 0. For example, the probability
of sampling the blue points in Figure 7 (left) is 0, and the probability of
sampling points residing on $\mathcal{C}\subset\mathcal{F}$ (the circle
orthogonal to $\mathbf{v}_{2}$) in Figure 7 (right) is also 0. Hence, by
generating $\mathbf{v}$ randomly, the proposed R$1$SMG will cause privacy
leakage of using the sensing vector in the null space of $\mathbf{v}$ to have
probability zero.

Figure 7: Visualization of the null space of the noise generated by R$1$SMG.
Left: $\mathbb{V}_{1,2}$. Right: $\mathbb{V}_{1,3}$.

##  Appendix D Potential Improvement of the MVG Mechanism

When studying the MVG mechanism, we observe one potential solution to improve
its privacy guarantee. In particular, one intermediate step in the proof of
the MVG mechanism requires deriving an upper bound for

$\displaystyle\clubsuit=Tr\Big{[}$
$\displaystyle\bm{\Psi}^{-1}\mathbf{Y}^{T}\bm{\Sigma}^{-1}\Delta+\bm{\Psi}^{-1}\Delta^{T}\bm{\Sigma}^{-1}\mathbf{Y}$
$\displaystyle+\bm{\Psi}^{-1}f(D_{2})^{T}\bm{\Sigma}^{-1}f(D_{2})-\bm{\Psi}^{-1}f(D_{1})^{T}\bm{\Sigma}^{-1}f(D_{1})\Big{]},$

where $\mathbf{Y}$ stands for the output of the MVG mechanism and
$\Delta=f(D_{1})-f(D_{2})$ (see [10] page 244, right column). Due to the
negative sign in the fourth term, the authors simply bound its absolute value,
i.e.,
$\big{|}Tr\big{[}\bm{\Psi}^{-1}f(D_{1})^{T}\bm{\Sigma}^{-1}f(D_{1})\big{]}\big{|}$,
which results in a very loose upper bound related to the quadratic form in the
Frobenius norm of the matrix query result (i.e, $\gamma^{2}$ in Theorem 3),
and further compromises the utility.

In fact, the original proof of the MVG mechanism can be improved if we apply
the transformation

$\begin{aligned}
&Tr\big{[}\bm{\Psi}^{-1}f(D_{2})^{T}\bm{\Sigma}^{-1}f(D_{2})-\bm{\Psi}^{-1}f(D_{1})^{T}\bm{\Sigma}^{-1}f(D_{1})\big{]}\\\
=&Tr\Big{[}\bm{\Psi}^{-1}\Big{(}f(D_{2})^{T}\bm{\Sigma}^{-1}\big{(}f(D_{2})-f(D_{1})\big{)}\\\
&\qquad+\big{(}f(D_{2})-f(D_{1})\big{)}^{T}\bm{\Sigma}^{-1}f(D_{1})\Big{)}\Big{]}\end{aligned},$

and rewrite $\clubsuit$ as

$\clubsuit=Tr\Big{[}\bm{\Psi}^{-1}\big{(}\mathbf{Y}-f(D_{2})\big{)}^{T}\bm{\Sigma}^{-1}\Delta+\bm{\Psi}^{-1}\Delta^{T}\bm{\Sigma}^{-1}\big{(}\mathbf{Y}-f(D_{1})\big{)}\Big{]},$

then bound $\clubsuit$ using singular values, then the quadratic form in the
Frobenius norm of the query result can be completely removed. We do not follow
the above steps to further develop an improved version of the MVG mechanism,
because the improved version is still a “victim” of the identified curse of
full rank covariance matrices.