# Privacy-Utility Tradeoff of OLS with Random Projections

Yun Lu  University of VictoriaVictoriaCanada<EMAIL_ADDRESS>,  Malik Magdon-
Ismail  Rensselaer Polytechnic InstituteTroyUSA<EMAIL_ADDRESS>,  Yu Wei
Purdue UniversityWest LafayetteUSA<EMAIL_ADDRESS>and  Vassilis Zikas
Purdue UniversityWest LafayetteUSA<EMAIL_ADDRESS>
(2023)

###### Abstract.

We study the differential privacy (DP) of a core ML problem, linear ordinary
least squares (OLS), a.k.a. $\ell_{2}$-regression. Our key result is that the
approximate LS algorithm (ALS) (Sarlos, 2006), a randomized solution to the
OLS problem primarily used to improve performance on large datasets, also
preserves privacy. ALS achieves a better privacy/utility tradeoff, without
modifications or further noising, when compared to alternative private OLS
algorithms which modify and/or noise OLS. We give the first tight DP-analysis
for the ALS algorithm and the standard Gaussian mechanism (Dwork et al., 2014)
applied to OLS. Our methodology directly improves the privacy analysis of
(Blocki et al., 2012) and (Sheffet, 2019)) and introduces new tools which may
be of independent interest: (1) the exact spectrum of $(\epsilon,\delta)$-DP
parameters (“DP spectrum”) for mechanisms whose output is a $d$-dimensional
Gaussian, and (2) an improved DP spectrum for random projection (compared to
(Blocki et al., 2012) and (Sheffet, 2019)).

All methods for private OLS (including ours) assume, often implicitly,
restrictions on the input database, such as bounds on leverage and residuals.
We prove that such restrictions are necessary. Hence, computing the privacy of
mechanisms such as ALS must estimate these database parameters, which can be
infeasible in big datasets. For more complex ML models, DP bounds may not even
be tractable. There is a need for blackbox DP-estimators (Lu et al., 2022)
which empirically estimate a data-dependent privacy. We demonstrate the
effectiveness of such a DP-estimator by empirically recovering a DP-spectrum
that matches our theory for OLS. This validates the DP-estimator in a
nontrivial ML application, opening the door to its use in more complex
nonlinear ML settings where theory is unavailable.

††copyright: acmcopyright††journalyear: 2023††conference: ; ;

##  1\. Introduction

Linear ordinary least squares (OLS) (a.k.a. $\ell_{2}$-regression) is a
fundamental inference tool in data analysis, while also being a building block
for more sophisticated models like deep-networks. To protect the privacy of
sensitive data, prior work has considered differentially private (DP) versions
of OLS. Privacy in DP is quantified by two parameters: $\epsilon$
(intuitively, the privacy leakage), and $\delta$ (intuitively, the probability
of failure to achieve $\epsilon$-DP, i.e., DP with parameter $\epsilon$).
Naturally, the smaller the privacy parameters, the better; but as expected
there is an inherent trade-off between the above two parameters, making an
optimal choice a non-trivial task.

To achieve $(\epsilon,\delta)$-DP for OLS, previous works proposed
modifications to the OLS algorithm. The simplest one follows the classical DP
paradigm of adding noise to the OLS output drawn from a given distributions
(e.g., Gaussian). More sophisticated DP mechanisms add dummy entries to the
input data followed by a (randomized) OLS algorithm (Blocki et al., 2012;
Sheffet, 2017, 2019; Dwork et al., 2014). Both the above methods end up
modifying (implicitly or explicitly noising) the outcome of an existing OLS-
algorithm and as such, inherently introduce errors, reducing the utility of
the output/mechanism. For brevity we refer to the class of all such algorithms
as privatized OLS. The starting point of our work is the observation that
existing (non-privatized) OLS algorithms already use randomness to scale the
problem to huge data sets while provably preserving the utility of their
output. Thus, a natural question is:

”Do existing randomized OLS algorithms have good inherent DP, without further
privatization?”

We answer this question in the affirmative. We show that the mainstream
randomized OLS algorithm in (Sarlós, 2006), which we call approximate least
squares (ALS), achieves privacy-utility trade-offs that are better than
explicitly privatized OLS algorithms in (Blocki et al., 2012; Sheffet, 2017,
2019; Dwork et al., 2014). ALS solves the regression problem using Gaussian
random projections into $r$-dimensions. The accuracy of the solution depends
on an embedding parameter $r$.111Note, to make ALS efficient, one uses a fast
subsampled randomized Hadamard transform (SRHT) in place of Gaussian random
projection. While SRHT is statistically similar to a Gaussian random
projection, producing an asymptotically Normal output, we postpone the
analysis of SHRT to a full version of this paper. The inherent privacy of ALS
inherits from the randomness in the random projection. By arguing from the
asymptotic normality of the ALS-estimator, we give the first tight privacy
analysis of ALS, leveraging our main technical tool in Lemma 2 which gives an
exact and easy method to compute privacy analysis of high-dimensional Gaussian
mechanisms. This Lemma may be of independent interest since Gaussian
mechanisms are widely used in privacy analysis. Indeed, we apply Lemma 2 to
give the first general tight privacy analysis of a wide class of privatized
OLS algorithms whose outputs are Normal or asymptotically Normal. This
includes all the prior privatized OLS mechanisms in (Blocki et al., 2012;
Sheffet, 2017, 2019; Dwork et al., 2014). In addition, Gaussian random
projections are also a fundamental tool in data analysis, used as a
preprocessing step in several learning tasks (Bartan and Pilanci, 2020;
Upadhyay and Upadhyay, 2021; Arora and Upadhyay, 2019; Kharkovskii et al.,
2020; Upadhyay, 2014). Lemma 6 and 7 directly give a tight (exact) privacy
analysis of Gaussian random projections which replaces the relatively loose
bounds in (Blocki et al., 2012; Sheffet, 2019).

We demonstrate the theory on real data. We study the privacy-utility trade-
offs of ALS as well as the prior privatized OLS algorithms. Since our analysis
is tight (exact), we can give detailed comparisons of the DP-spectrum of ALS
and the prior privatized OLS algorithms, which would not be possible using the
looser bounds from prior work. On the real datasets, ALS achieves better
privacy-utility trade-offs than previous works.

We then address two issues when dealing with $(\epsilon,\delta)$-DP in OLS and
machine learning in general. First, we observe that all existing privacy
statements (including ours) for private OLS assume (implicitly or explicitly)
a restriction on properties of the input database. Our proof shows that the DP
of ALS depends on the leverage of data points and the optimal error-residuals
for the specific regression task being considered (Mahoney et al., 2012;
Drineas et al., 2007). This means an exact ALS privacy statement depends on
the specific database, i.e., cannot be generic. Thus, we restrict our (tight)
privacy statements to databases with bounds on the leverage/residuals. In
particular, in this work, we make a privacy claim for ALS, given the specific
database in the application at hand. In (Lu et al., 2022), the term relative
DP was coined to refer to the above non-generic privacy statement, a
terminology which is relevant here. A natural question is whether restricting
to (some form of) relative-DP is necessary and/or whether it is an artifact of
(non-privatized) ALS. Surprisingly, we prove that such restrictions are
necessary for differentially private OLS, independent of the algorithm. In
particular we prove in Corollary 4 that a class of queries, including private
OLS, are impossible without restricting the input database or allowing
arbitrarily bad utility. This means that even existing privatized OLS
algorithms cannot in fact achieve generic DP (i.e., DP which applies to any
database of some size). Their guarantees are with respect to bounds on
sensitivity which depend on parameters like singular values, leverages and
residuals. These bounds must hold over the full set of databases to which the
DP is applied (Blocki et al., 2012; Sheffet, 2017, 2019).

The need to restrict the database leads to the next issue. To compute an
explicit DP statement (e.g., for ALS or prior work on privatized OLS), the
necessary parameters must estimated, in this case leverages and residuals.
Unfortunately, computing these parameters can be costly for large datasets.
Even worse, for more general ML models, DP-estimates may be intractable. This
calls for a different methodology for estimating the actual privacy achieved
by such mechanisms when applied on real-world massive datasets. To this
direction, we showcase an alternative (practical) method of empirically
computing relative-DP. We validate this method on (randomized) OLS mechanisms
(with or without privatization) where we are able to recover DP-spectra that
are comparable to the theoretical analysis. Specifically, we use the blackbox
DP-estimator in (Lu et al., 2022) to directly estimate optimal
($\epsilon,\delta$) pairs that are achieved by the mechanism at hand, without
the need for the data-dependent parameters necessary to apply the theory. To
our knowledge, our results are the first validation of a blackbox DP-estimator
in a complex ML task, opening the door to the use of such blackbox empirical
estimators in more complex ML tasks.

We summarize our contributions as follows:

  1. (1)

Lemma 3: First tight privacy analysis for the ALS algorithm.

  2. (2)

Proposition 4: First tight privacy analysis for the Gaussian mechanism applied
to OLS, which also leads to improvements to the privacy bounds of previous
work (Blocki et al., 2012; Sheffet, 2017, 2019).

  3. (3)

Corollary 4/Lemma 5: Impossibility theorem proving the necessity of
restricting the input database to get tight privacy for OLS (and other
models).

  4. (4)

Section 5: Validation on real-world data comparing privacy/utility tradeo-ffs
between ALS and prior privatized OLS and demonstrating the power of blackbox
empirical DP-estimators.

###  1.1. Related Work

The most common way to privatize OLS is via the Gaussian mechanism, a
fundamental and generic DP mechanism (Dwork et al., 2014) that adds
multivariate Gaussian noise to the output. This simple method achieves a good,
and importantly, tuneable privacy/utility trade-off, but requires running
standard OLS on the whole data which makes it impractical for large datasets
(Blocki et al., 2012; Dwork et al., 2014). The Gaussian mechanism has been
used to privatize OLS, also in conjunction with random projections, (Sheffet,
2017, 2019). We give the first tight privacy analysis of the classic Gaussian
mechanism for all these OLS algorithms, including ALS, making explicit the
detailed dependence on database parameters like leverages, residuals, etc.
Prior analysis uses loose bounds on the sensitivity.

Blocki et al. (Blocki et al., 2012) initiated the more sophisticated
methodology of using random projections to achieve differential privacy. They
showed that standard Gaussian random projection can preserve privacy if the
$D$’s least singular value is large enough and each row’s norm is bounded.
More interestingly, they showed (by employing the DP sequential composition
theorem), that the random projection can also preserve privacy for OLS. More
recently Sheffet (Sheffet, 2017, 2019) studied the specific $r$-fold
composition of the random projection and improved on previous works’ analysis,
giving a stronger privacy statement for random projection. For private OLS,
the (non-privatized) OLS algorithm (Fox, 2015) is applied after the random
projection. This step can be considered as a post-processing of the random
projection, which preserves DP (Dwork and Roth, 2014). We note that while a
privacy statement can be obtained in this way, the statement may not be tight,
as applying OLS may actually augment privacy rather than simply preserve it.
In addition, this line of work modifies the input database (with the addition
of extra, possibly outlier data) to have certain desirable properties before
the random projection, which usually has a detrimental effect on utility.

In contrast, we offer a significantly more rigorous privacy analysis, by
directly studying the ALS algorithm’s privacy (rather than relying on DP’s
immunity to post-processing).

Further, our Lemma 7 directly gives tight (exact) analysis of Gaussian random
projections replacing the prior results. This is of general interest because
random projections are used as a preprocessing step in many applications
(Bartan and Pilanci, 2020; Upadhyay and Upadhyay, 2021; Arora and Upadhyay,
2019; Kharkovskii et al., 2020; Upadhyay, 2014).

##  2\. Background

#### Differentially Private OLS.

The setting for OLS algorithms is as follows: The algorithm is given as input
a database, represented as a matrix $D=[B,b]$, where $B$ is the feature
matrix, and $b$ is the label vector. The goal is to compute a vector
$x_{\texttt{opt}}$ which minimizes the $\ell_{2}$ distance between
$Bx_{\texttt{opt}}$ and $b$. In certain algorithms (such as ALS), randomness
is used to achieve better performance, at the cost of a slightly less optimal
solution. We call this randomized solution $\tilde{x}_{\texttt{opt}}$.

In fact, for private OLS, randomness is necessary. An OLS algorithm is
differentially private (DP), if for any database $D^{\prime}$ which is $D$ but
one row is zeroed out, the distance between the distributions of
$x_{\texttt{opt}}$ and $x_{\texttt{opt}}^{\prime}$ (solution for $D^{\prime}$)
is close. The pairs of such “similar” databases $D$ and $D^{\prime}$ are known
as neighbors.

###### Definition 0 (Neighboring Databases (for Private OLS)).

For fixed $n,d$, let $\mathcal{X}=\mathsf{R}^{n\times d}$. A pair of databases
$D,D^{\prime}\in\mathcal{X}$ is neighboring, denoted $D\simeq D^{\prime}$ if
$D^{\prime}$ can be obtained by replacing exactly one row in $D$ with a row of
zeros.

An algorithm is DP if its output distribution for any $D$ is similar to its
output distribution for any of $D$’s neighbors. This similarity is quantified
by parameters $\epsilon$ and $\delta$.

###### Definition 0 (Differential Privacy (DP) (Dwork and Roth, 2014)).

An algorithm $\mathcal{M}:=\mathcal{X}\mapsto\mathcal{O}$ is
$(\epsilon,\delta)$-DP if for all subset $\mathcal{S}\subseteq\mathcal{O}$ and
for all neighboring databases $D\simeq D^{\prime}$:

$\displaystyle\Pr[\mathcal{M}(D)\in\mathcal{S}]\leq
e^{\epsilon}Pr[\mathcal{M}(D^{\prime})\in\mathcal{S}]+\delta,$

and

$\displaystyle\Pr[\mathcal{M}(D^{\prime})\in\mathcal{S}]\leq
e^{\epsilon}Pr[\mathcal{M}(D)\in\mathcal{S}]+\delta.$

where the probability space is over the coin flips of $\mathcal{M}$. If
$\delta=0,$ we say that $\mathcal{M}$ is $\epsilon$-DP.

#### Differential Privacy on Neighboring Database Pairs.

An equivalent way (by rearranging the inequalities in the definition) to
describe DP which is used in our results, is that for any $\epsilon$, an
algorithm $\mathcal{M}$ satisfies $(\epsilon,\delta)$-DP for

$\delta\geq\max_{D\sim D^{\prime}\text{or}D^{\prime}\sim
D}\max_{\mathcal{S}\subseteq\mathcal{O}}\Pr[\mathcal{M}(D)\in\mathcal{S}]-e^{\epsilon}\Pr[\mathcal{M}(D^{\prime})\in\mathcal{S}]$

In fact, when $\geq$ is replaced by $=$ in the inequality above, $\delta$ is
the optimal $\delta$ possible, given $\mathcal{M}$ and $\epsilon$. Following
(Lu et al., 2022), we can also define the optimal $\delta$ for a particular
pair of databases $D$, $D^{\prime}$. Note that since $\delta$ is a
probability, it is capped between $[0,1]$.

###### Definition 0 (Optimal $\delta$).

Let $\mathcal{M}$ be an algorithm, $D,D^{\prime}$ be a pair of databases, and
$\epsilon\in\mathsf{R}_{\geq 0}$ be a privacy parameter. We say the privacy
parameter $\delta_{D,D^{\prime}}$ is optimal (minimal) with respect to the
tuple $(\mathcal{M}(D),\mathcal{M}(D^{\prime}),\epsilon)$ if

$\delta_{D,D^{\prime}}=\max(\max\limits_{\mathcal{S}\subseteq\mathcal{O}}\Pr[\mathcal{M}(D)\in\mathcal{S}]-e^{\epsilon}\Pr[\mathcal{M}(D^{\prime})\in\mathcal{S}],0).$

In our work, we prove tight privacy statements which depend on the properties
of $D$. Specifically, we compute $\max_{D^{\prime}:D\sim
D^{\prime}}\delta_{D,D^{\prime}}$ as a function of the leverage and residual
of $D$.

#### Approximate Least Squares (ALS) Algorithm.

The approximate least squares (ALS) algorithm (Fig. 1) is designed to improve
the OLS algorithm’s efficiency when the input database has a large number of
records $n$. ALS achieves this by first reducing the size of the database from
$n\times d$ to $r\times d$ ($r<<n$), via random projection. Then, ALS computes
the (optimal) OLS solution for the projected database. Since the projected
database preserves most of the information about the input databases, the
ALS’s output is a good approximate OLS solution for the original database.

Input: A matrix $D=[B,b]\in\mathsf{R}^{n\times d}$, where
$B\in\mathsf{R}^{n\times(d-1)}$ and $b\in\mathsf{R}^{n}$. Output: The
approximate solution $\tilde{x}_{opt}$ of $Bx=b.$ (1) Let matrix
$\Pi\in\mathsf{R}^{r\times n}$ be a random Gaussian matrix such that any of
$\Pi$’s entry $\left(\Pi\right)_{i,j}\sim\mathcal{N}(0,1)$ is an independent
standard normal random variable. (2) Return $\tilde{x}_{\texttt{opt}}=(\Pi
B)^{\dagger}\Pi b.$

Figure 1. Least Square Regression Approximate algorithm $\mathcal{A}^{l_{2}}$
from (Sarlós, 2006), Theorem 12.

#### Notation.

Table 1. Notation Table Symbol | Description
---|---
$n$ | number of individual records
$d-1$ | number of features each record has
$B$ |  $n\times(d-1)$ feature matrix
$b$ |  $n\times 1$ label vector, which corresponds to individual records
$[B,b]$ |  $n\times d$ matrix, represents the input database for algorithms
$[{B}^{\prime},{b}^{\prime}]$ |  neighbor database of $[B,b]$ (Def. 1)
$P$ |  $B(B^{T}B)^{-1}B^{T}$, the projection matrix of $B$
$x_{\texttt{opt}}$ |  $(B^{T}B)^{-1}B^{T}b$, (deterministic) optimal solution according to the
| OLS algorithm for database [B, b]
$\tilde{x}_{\texttt{opt}}$ | the randomized OLS solution, which is the output of ALS algorithm
$w$ |  $(I_{n}-P)b,$ the error vector (vector orthogonal to $B$’s column space)

We use standard notation from the machine learning literature. Let
$D\in\mathsf{R}^{n\times d}$ be a matrix representing a database. We use
$D_{(i)}$ to denote the matrix’s $i$-th row. We use $D^{(j)}$ to denote the
matrix’s $j$-th column. We use $\left(D\right)_{i,j}$ to denote the matrix’s
entry at $i$-th row and $j$-th column. We denote the column space of matrix
$D$ as $\bm{colspan}(D)$. We describe other notations we use in Table 1.

##  3\. Privacy of ALS

In this section, we analyze the privacy of the approximate least squares
algorithm (ALS). First, in Sec. 3.1, we prove the output of ALS is
asymptotically normally distributed. Then, in Sec. 3.2, we prove an exact DP
spectrum (i.e., privacy parameter $\delta$ as a function of parameter
$\epsilon$) for the multivariate Gaussian distribution—a result which may be
of independent interest. Combining these two, we prove the privacy of ALS
(Lemma 3). Our results from Sec. 3.2 can also extend to improve privacy bounds
for the Gaussian mechanism applied to OLS (Prop. 5), as well as privatized
(OLS) algorithms based on random projection.

###  3.1. Normality Analysis

Since the exact distribution of the ALS output (Algorithm 1) is complex and
might not be computable, we derive the asymptotic distribution (in terms of
$r$) of it. We will later do the differential privacy analysis on the
asymptotic distribution, and we will use our black-box estimator to show that
the privacy of the exact distribution and the asymptotic distribution tightly
match even with a reasonably small $r.$ This means that the asymptotic
behavior (with no surprise) kicks in at an early of $r$ and we can use it to
capture well the DP-spectrum of Algorithm 1.

######  Lemma 0 (Distribution of the Approximate Least Squares Algorithm).

The Algorithm 1’s output is asymptotically normally distributed with mean
$x_{\texttt{opt}}$ and covariance matrix
$\frac{{\left\|w\right\|}_{2}^{2}(B^{T}B)^{-1}}{r}.$ That is

$\displaystyle\tilde{x}_{\texttt{opt}}\xrightarrow{d}\mathcal{N}(x_{\texttt{opt}},\frac{{\left\|w\right\|}_{2}^{2}(B^{T}B)^{-1}}{r}).$

The proof of Lemma 1 is in the appendix. We give a computation sketch here to
help the reader read the proof.

  1. (1)

We first compute the difference between $\tilde{x}_{\texttt{opt}}$ and
$x_{\texttt{opt}}$. That is

$\displaystyle\tilde{x}_{\texttt{opt}}-x_{\texttt{opt}}=(\frac{1}{r}(\Pi
B)^{T}\Pi B)^{-1}\frac{1}{r}(\Pi B)^{T}\eta,$

where $r,\Pi,B$ are defined in the Algorithm 1 and $\eta$ is a multi-variate
Gaussian distribution, whose parameters can be computed from $B,b$. See
appendix for the description of $\eta.$

  2. (2)

We then show the first term of the difference $(\frac{1}{r}(\Pi B)^{T}\Pi
B)^{-1}$ converges almost surely to the constant $(B^{T}B)^{-1}$ as $r$
increases, and the second term $\frac{1}{r}(\Pi B)^{T}\eta$ converges in
distribution to multivariate Gaussian distribution
$\mathcal{N}(\overrightarrow{\mathbf{0}},\frac{{\left\|w\right\|}_{2}^{2}B^{T}B}{r})$
as $r$ increases. We also note that some of the facts used in this computation
is summarized in the appendix.

  3. (3)

We then compute the asymptotic distribution of the difference between
$\tilde{x}_{\texttt{opt}}$ and $x_{\texttt{opt}}$, which is a multivariate
normal distribution. Since we know $x_{\texttt{opt}}$ is a constant when $B,b$
are fixed, and the shift of a multivariate normal distribution is still a
multivariate normal distribution, we finally have the asymptotic (in $r$)
distribution of $\tilde{x}_{\texttt{opt}}.$

###  3.2. DP Spectrum of Multi-variate Gaussians

Lemma 1 shows that the Algorithm 1’s output is asymptotically normally
distributed. In this section, we derive a more general DP Spectrum result for
a pair of multi-dimensional normal random variables. We could use this result,
together with Lemma 1, to derive the privacy statement for Algorithm 1. We
could also use it to compute the exact DP-spectrum for the standard Gaussian
mechanism (Proposition 5).

######  Lemma 0 (DP Spectrum of Multi-dimensional Gaussians; proof in
appendix).

Let
$X\sim\mathcal{N}(\mu_{1},\Sigma_{1}),Y\sim\mathcal{N}(\mu_{2},\Sigma_{2})$ be
two multidimensional normal distributions, where the covariance matrix
$\Sigma_{1},\Sigma_{2}\in\mathsf{R}^{d\times d}$ and mean vector
$\mu_{1},\mu_{2}\in\mathsf{R}^{d}$ for some positive integer $d$. Let
$UAU^{T}$ be the Singular Value Decomposition (SVD) of the matrix
$I_{d}-\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}$, let
$b=-U^{T}\Sigma_{1}^{1/2}\Sigma_{2}^{-1}(\mu_{1}-\mu_{2}),$ and let
$c=\epsilon+\ln{\sqrt{\frac{\det{(\Sigma_{1})}}{\det{(\Sigma_{2})}}}}-\frac{1}{2}(\mu_{1}-\mu_{2})^{T}\Sigma_{2}^{-1}(\mu_{1}-\mu_{2}).$
Let $Z\sim\mathcal{N}(\overrightarrow{\mathbf{0}},I_{d})$ be a standard
$d$-dimensional Gaussian. Then,

$\displaystyle\delta(\mu_{1},\mu_{2},\Sigma_{1},\Sigma_{2})=\mathbb{E}\left(\max\\{0,1-\exp\left(\frac{1}{2}Z^{T}AZ+b^{T}Z+c\right)\\}\right)$

is optimal with respect to the tuple $(X,Y,\epsilon).$

###  3.3. Privacy of ALS

The lemma below proves the privacy of ALS. By plugging in the parameters in
this lemma, we can obtain the full expression as a function of the database’s
leverage and error-residual (see appendix).

######  Lemma 0 (Privacy of ALS).

Fix $\epsilon>0$ and let $[B,b]$ be the database. Then $\delta$ is given by

$\delta_{ALS}=\max_{i}\left\\{\max(\delta(\mu,\mu_{i},\Sigma,\Sigma_{i}),\delta(\mu_{i},\mu,\Sigma_{i},\Sigma)\right\\},$

where $\delta(\cdot,\cdot,\cdot,\cdot)$ is defined in Lemma 2, $i$ is an index
which ranges over the rows in $[B,b]$, $[{B}^{\prime},{b}^{\prime}]$ is a
neighboring database (Def. 1) with row $i$ set to zero and the parameters
$\mu,\mu_{i},\Sigma,\Sigma_{i}$ are computed by Lemma 1.

###### Proof.

The estimators $x_{opt}$ and $x_{opt}^{\prime}$ are asymptotically normal with
mean and covariances given by $\mu,\mu_{i},\Sigma,\Sigma_{i}$ (by Lemma 1).
The lemma now follows by applying Lemma 2 and then taking the max over the
index $i$. ∎

###  3.4. Extending Results to Achieve Tight Privacy Analysis for Gaussian
Mechanism and Random Projection

We can extend our techniques to improve the privacy bounds for the Gaussian
mechanism (applied to OLS), as well as the Gaussian random projection.

######  Proposition 0 (Proof in appendix).

Let neighbors (Def. 1) $[B,b]\simeq[{B}^{\prime},{b}^{\prime}]$ have full
column rank, i.e.,
$\mathbf{rank}([B,b])=\mathbf{rank}([{B}^{\prime},{b}^{\prime}])=d.$ Let
$\mathcal{M}$ be a mechanism which takes as input a dataset $[B,b]$ and
outputs $x_{\texttt{opt}}+X,$ where
$X\sim\mathcal{N}(\overrightarrow{\mathbf{0}},\sigma^{2}I_{d})$.

Then

$\displaystyle\delta=\frac{1-\exp\left(\epsilon\right)}{2}+\frac{1}{2}(\texttt{erf}\left(-\frac{\epsilon}{\sqrt{2}c}+\frac{c}{\sqrt{8}}\right)-\exp\left(\epsilon\right)\texttt{erf}\left(-\frac{\epsilon}{\sqrt{2}c}-\frac{c}{\sqrt{8}}\right)),$

where
$c=\frac{{\left|w_{(i)}\right|}}{{\left|\sigma\right|}}\frac{{\left\|(B^{T}B)^{-1}v\right\|}_{2}}{(1-\left(P\right)_{i,i})},$
is the optimal delta with respect to the tuple
$(\mathcal{M},[B,b],[{B}^{\prime},{b}^{\prime}],\epsilon).$

The following is an instantiation of Proposition 4. It analyzes the DP-
spectrum of the Gaussian mechanism (Dwork and Roth, 2014) which adds standard
multivariate normal random variable, where each coordinate is with variance
$2\ln{(1.25/\delta)}\frac{s^{2}}{\epsilon^{2}},$ and $s$ is the sensitivity
measured by Euclidean norm of the difference between
$x_{\texttt{opt}}-x_{\texttt{opt}}^{\prime}.$

######  Proposition 0.

Let neighbors (Def. 1) $[B,b]\simeq[{B}^{\prime},{b}^{\prime}]$ have full
column rank, i.e.,
$\mathbf{rank}([B,b])=\mathbf{rank}([{B}^{\prime},{b}^{\prime}])=d.$ Let
$\mathcal{M}_{\epsilon,\delta}$ be the Gaussian mechanism which takes as input
a dataset $[B,b]$ and outputs $x_{\texttt{opt}}+X,$ where
$X\sim\mathcal{N}(\overrightarrow{\mathbf{0}},\sigma^{2}I_{d})$,
$\sigma^{2}=2\ln{(1.25/\delta)}\frac{s^{2}}{\epsilon^{2}},$
$s={\left\|x_{\texttt{opt}}-x_{\texttt{opt}}^{\prime}\right\|}_{2}$. Then,

$\displaystyle\delta^{\prime}(\epsilon^{\prime})=\frac{1-\exp\left(\epsilon^{\prime}\right)}{2}+\frac{1}{2}(\texttt{erf}\left(-\frac{\epsilon^{\prime}}{\sqrt{2}c}+\frac{c}{\sqrt{8}}\right)-\exp\left(\epsilon^{\prime}\right)\texttt{erf}\left(-\frac{\epsilon^{\prime}}{\sqrt{2}c}-\frac{c}{\sqrt{8}}\right)),$

where $c=\frac{\epsilon}{\sqrt{2\ln{1.25/\delta}}},$ is the optimal delta with
respect to the tuple
$(\mathcal{M}_{\epsilon,\delta},[B,b],[{B}^{\prime},{b}^{\prime}],\epsilon^{\prime}).$

######  Lemma 0 (Privacy of Random linear Combination).

Let $\mathcal{M}_{RLC}$ be the random linear combination algorithm, that takes
as input a $n\times d$ real matrix $D$ with full column rank
$\mathbf{rank}(D)=d,$ samples a column vector $g$ from standard
$n$-dimensional normal distributions and outputs $D^{T}g$.

Fix $\epsilon>0$ and let $D$ be the database. Then $\delta$ is given by

$\delta_{RLC}=\max_{i}\left\\{\max(\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},D^{T}D,{D}^{\prime
T}_{i}{D}^{\prime}_{i}),\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},{D}^{\prime
T}_{i}{D}^{\prime}_{i},D^{T}D)\right\\},$

where $\delta(\cdot,\cdot,\cdot,\cdot)$ is defined in Lemma 2, $i$ is an index
which ranges over the rows in $D$, ${D}^{\prime}_{i}$ is a neighboring
database (Def. 1) with row $i$ set to zero.

######  Lemma 0 (Privacy of Random Projection).

Let $\mathcal{M}_{RP}$ be the random projection algorithm, that takes as input
a $n\times d$ real matrix $D$ with full column rank $\mathbf{rank}(D)=d,$
samples a $n\times r$ Gaussian matrix $G$, where each of entry is a standard
normal random variable, and outputs $D^{T}G$.

Fix $\epsilon>0$ and let $D$ be the database. Then $\delta$ is given by

$\delta_{RP}=\max_{i}\left\\{\max(\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},\Sigma,\Sigma_{i}),\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},\Sigma_{i},\Sigma)\right\\},$

where $\delta(\cdot,\cdot,\cdot,\cdot)$ is defined in Lemma 2, $i$ is an index
which ranges over the rows in $D$, ${D}^{\prime}_{i}$ is a neighboring
database (Def. 1) with row $i$ set to zero. $\Sigma$ is a $rd\times rd$ block
diagonal matrix with blocks $D^{T}D$, $\Sigma_{i}$ is a $rd\times rd$ block
diagonal matrix with blocks ${D}^{\prime T}{D}^{\prime}$.

##  4\. Impossibility of Private OLS without Restricting Input

In this section, we prove that for all functions with unbounded sensitivity
(Def. 1) including OLS, it is impossible to both preserve privacy and any form
of utility (Def. 2). In other words, privacy statements that depend on the
input database properties (e.g., via its leverage/residual as in our work) are
necessary in order to preserve privacy and utility.

###### Definition 0 (Function with unbounded sensitivity).

A function $f:\mathsf{R}^{n_{1}\times m_{1}}\mapsto\mathsf{R}^{n_{2}\times
m_{2}}$ has unbounded sensitivity if for any $a>0,$ there exists an
neighboring pair $D\simeq D^{\prime}$ and $i\in[n_{2}],j\in[m_{2}]$ such that
${\left|f(D)_{i,j}-f(D^{\prime})_{i,j}\right|}>a$.

###### Definition 0 (Useful Private Algorithm).

Let $\mathcal{M}$ be a (privatized) algorithm computing a function $f$. Let
$g$ be a utility function, where $g(D)$ outputs a non-negative real number
measuring the distance between $\mathcal{M}(D)$ and $f(D)$. Then $\mathcal{M}$
is $A$-useful with respect to $g,$ if for every database $D$ in $f$’s domain,
$g(\mathcal{M}(D),f(D))\leq A.$

Lemma 3 shows for every $f$ with unbounded sensitivity, no $\mathcal{M}$ can
achieve both privacy and utility guarantees. Here, we measure utility with by
the mean square error—in other words, private $\mathcal{M}$ for such functions
will have an unbounded mean square error!

######  Lemma 0 (Proof in Appendix).

Let $f:\mathsf{R}^{n\times m}\mapsto\mathsf{R}$ be a function with unbounded
sensitivity. Let $\mathcal{M}:\mathsf{R}^{n\times m}\mapsto\mathsf{R}$ be an
algorithm (for $f$) with input a database $D\in\mathsf{R}^{n\times m}$. Let
$g(D)=\mathbb{E}\left((\mathcal{M}(D)-f(D))^{2}\right)$ be the utility
function. If $\mathcal{M}$ satisfies $(\epsilon,\delta)$-DP for
$\epsilon\in\mathsf{R}_{\geq 0},\delta\in[0,\frac{1}{2}],$ then it is not
$A$-useful with respect to utility function $g$, for every $A>0$.

Intuitively, Lemma 5 holds since to achieve privacy, the output distribution
on neighboring databases must be close; meanwhile, a large sensitivity means
that $f$’s outputs on neighbors are far apart. This conflict means that
utility inherently suffers when maintaining privacy. The following corollary
extends the above lemma to functions with matrix-value outputs.

###### Corollary 0.

Let $f:\mathsf{R}^{n_{1}\times m_{1}}\mapsto\mathsf{R}^{n_{2}\times m_{2}}$ be
a function with unbounded sensitivity. Let
$\mathcal{M}:\mathsf{R}^{n_{1}\times m_{1}}\mapsto\mathsf{R}^{n_{2}\times
m_{2}}$ be an algorithm (computing $f$) that takes as input a database
$D\in\mathsf{R}^{n_{1}\times m_{1}}$, and outputs a matrix-valued random
variable. Let $g$ be the utility function outputting the variance of Frobenius
norm of $\mathcal{M}(D)-f(D),$ i.e.,
$Var\left({\left\|\mathcal{M}(D)-f(D)\right\|}_{F}\right)$. If $\mathcal{M}$
satisfies $(\epsilon,\delta)$-DP for some fixed and bounded
$\epsilon\in\mathsf{R}_{\geq 0},\delta\in[0,\frac{1}{2}],$ then it is not
$A$-useful, with respect to utility function $g$, for every $A>0$.

The following lemma shows that indeed, OLS has unbounded sensitivity, and thus
Cor. 4 holds.

######  Lemma 0 (Proof in Appendix).

Let $f([B,b])=(B)^{\dagger}b=(B^{T}B)^{-1}B^{T}b$ be the ordinary least square
(OLS) query for over-constrained systems ($B^{T}B$ has full rank). Then for
every database $D=[B,b]$ in the domain, and every $a>0,$ there is a database
$D^{\prime}$ such that $D^{\prime}\simeq D$ (Def. 1) and
${\left\|f(D)-f(D^{\prime})\right\|}_{\infty}>a.$

##  5\. Comparison and Evaluation

In Section 5, we compare the privacy/error tradeoff between ALS and previous
privatized OLS algorithms. We see that ALS achieves strictly better
privacy/error tradeoffs than previous work.

In light of our impossibility result Cor. 4, we also propose an alternative
method for computing the privacy parameters of private OLS algorithms. We
showcase the first use of DP-estimators to empirical compute the DP of private
OLS algorithms on real-world databases. We choose the DP-estimator of (Lu et
al., 2022) for its provable accuracy bounds as a function of sample size. The
match of the estimator output and theoretical results serve as compelling
evidence that in practical settings, the DP for private OLS algorithms can be
estimated accurately.

The datasets we use in this section are the Cancer
Database222https://data.world/nrippner/cancer-linear-regression-model-tutorial
with 12 features and 2809 records, and the Flight
Database333https://rpubs.com/salmaeng/linear_regression with 2 features and
327346 records. To run the DP-estimator (Lu et al., 2022) we used a training
set size of $10^{7}$ and a testing set size of $10^{6}$.

(a)

(b)

Figure 2. Comparison of privacy/utility tradeoff. ALS without further
privatization achieves the best utility privacy tradeoff. All three curves are
from our tight (exact) analysis of the DP-spectrum based on Lemma 1

(a)

(b)

Figure 3. Empirical estimates vs. Theoretical result showing that the
theoretical DP-spectrum is recovered from the empirical blackbox estimator of
the DP-spectrum on real data. The empirical estimate (red dots) converge to
the theoretical estimate (blue) from below, as can be evidenced on the flight
data. The convergence is from below because the estimated classifier is always
worse than the Bayes optimal classifier. The error bar depends on how many
training points are used for computing an estimate to the Bayes optimal
classifier and the number of test points used in evaluating the classifier. In
both cases, the more points the better. When $\delta$ is small (more privacy)
the error in the estimate is more visually pronounced, and more training
samples ought to be used.

We plot the privacy/utility trade-off of ALS, Gaussian LS (Gaussian mechanism
applied to OLS), and RP (random projection) LS (see Appendix). We measure
privacy by fixing $\epsilon$ and plotting the $\delta$. We measure utility by
the error $Var\left({\left\|\mathcal{M}(D)-f(D)\right\|}_{F}\right)$ (smaller
this number is, the better), which is the sum of the variance of each
coordinate between the $\mathcal{M}$’s output and the true query result.

#### Discussion of the empirical results

We observe that ALS has the best privacy-utility trade-off in both cases. We
also observe that the larger the dataset, the better privacy and utility for
ALS and Gaussian LS. Intuitively, this is because the influence of each record
is reduced when the database size increases. However, we also observe that RP
LS’s utility is not dependent on the database size, since it always introduces
some outlier records to increase privacy.

##  6\. Conclusion and Future Work

We studied the privacy guarantees of existing privacy preserving OLS
algorithms, as well as ALS, and provided the first tight theoretical analysis
of their privacy, improving on both the toolbox and the results of prior work.
Our results show that while ALS was not constructed originally with privacy in
mind, it (and systems that utilize ALS) already achieves state-of-the-art
privacy—“for free” (i.e., without further privatization). We further observe
that all DP-promising OLS-based algorithms rely on a (potentially
inefficiently computable) set of parameters. We demonstrate how to estimate
the privacy of such methods using DP-estimators. We believe that the use of
DP-estimators shows a promising future direction for computing the (inherent
or privatization-induced) privacy of more complex machine learning tasks.

## References

  * (1)
  * Arora and Upadhyay (2019) Raman Arora and Jalaj Upadhyay. 2019.  On Differentially Private Graph Sparsification and Applications. In _NeurIPS_. 13378–13389.
  * Bartan and Pilanci (2020) Burak Bartan and Mert Pilanci. 2020.  Distributed Sketching Methods for Privacy Preserving Regression.  _CoRR_ abs/2002.06538 (2020).  arXiv:2002.06538 https://arxiv.org/abs/2002.06538
  * Blocki et al. (2012) Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. 2012\.  The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy. In _FOCS_. IEEE Computer Society, 410–419.
  * Drineas et al. (2007) Petros Drineas, Michael W. Mahoney, S. Muthukrishnan, and Tamás Sarlós. 2007.  Faster least squares approximation.  _Numer. Math._ 117 (2007), 219–249.
  * Dwork and Roth (2014) Cynthia Dwork and Aaron Roth. 2014.  The Algorithmic Foundations of Differential Privacy.  _Found. Trends Theor. Comput. Sci._ 9, 3–4 (Aug. 2014), 211–407.  https://doi.org/10.1561/0400000042
  * Dwork et al. (2014) Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. 2014.  Analyze gauss: optimal bounds for privacy-preserving principal component analysis. In _Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014_ , David B. Shmoys (Ed.). ACM, 11–20.  https://doi.org/10.1145/2591796.2591883
  * Fox (2015) John Fox. 2015.  _Applied regression analysis and generalized linear models_.  Sage Publications.
  * Greene (2012) William H Greene. 2012\.  _Econometric analysis_.  Pearson Education Limited.
  * Kharkovskii et al. (2020) Dmitrii Kharkovskii, Zhongxiang Dai, and Bryan Kian Hsiang Low. 2020.  Private Outsourced Bayesian Optimization. In _ICML_ _(Proceedings of Machine Learning Research, Vol. 119)_. PMLR, 5231–5242.
  * Lu et al. (2022) Yun Lu, Yu Wei, Malik Magdon-Ismail, and Vassilis Zikas. 2022.  Eureka: A General Framework for Black-box Differential Privacy Estimators.  _IACR Cryptol. ePrint Arch._ (2022), 1250.  https://eprint.iacr.org/2022/1250
  * Mahoney et al. (2012) Michael W. Mahoney, Petros Drineas, Malik Magdon-Ismail, and David P. Woodruff. 2012.  Fast approximation of matrix coherence and statistical leverage. In _Proceedings of the 29th International Conference on Machine Learning, ICML 2012, Edinburgh, Scotland, UK, June 26 - July 1, 2012_. icml.cc / Omnipress.  http://icml.cc/2012/papers/80.pdf
  * Sarlós (2006) Tamás Sarlós. 2006\.  Improved Approximation Algorithms for Large Matrices via Random Projections. In _FOCS_. IEEE Computer Society, 143–152.
  * Sheffet (2017) Or Sheffet. 2017\.  Differentially Private Ordinary Least Squares. In _ICML_ _(Proceedings of Machine Learning Research, Vol. 70)_. PMLR, 3105–3114.
  * Sheffet (2019) Or Sheffet. 2019\.  Old Techniques in Differentially Private Linear Regression. In _Algorithmic Learning Theory, ALT 2019, 22-24 March 2019, Chicago, Illinois, USA_ _(Proceedings of Machine Learning Research, Vol. 98)_ , Aurélien Garivier and Satyen Kale (Eds.). PMLR, 788–826.  http://proceedings.mlr.press/v98/sheffet19a.html
  * Upadhyay (2014) Jalaj Upadhyay. 2014\.  Differentially Private Linear Algebra in the Streaming Model.  _CoRR_ abs/1409.5414 (2014).
  * Upadhyay and Upadhyay (2021) Jalaj Upadhyay and Sarvagya Upadhyay. 2021.  A Framework for Private Matrix Analysis in Sliding Window Model. In _Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event_ _(Proceedings of Machine Learning Research, Vol. 139)_ , Marina Meila and Tong Zhang (Eds.). PMLR, 10465–10475.  http://proceedings.mlr.press/v139/upadhyay21a.html

##  Appendix A Section 2 Cont’d: Notation, Additional Background

In this section, we include complementary material for Section 2 of the paper.
In particular, we include the background definition and theorems of large-
sample distribution theory, and an extended notation table for parameters we
use in the rest of the appendix.

###  A.1. Large-Sample Distribution Theory

###### Definition 0 (Almost Sure Convergence (Greene, 2012), Def D.3).

Let $x_{n}$ be a sequence of random variables indexed by the sample size. The
random variable $x_{n}$ converges almost surely to the constant $c$ if and
only if

$\displaystyle\Pr[\underset{n\rightarrow\infty}{\texttt{lim}}x_{n}=c]=1,$

Also, it is written as

$\displaystyle x_{n}\xrightarrow{a.s.}x.$

Almost sure convergence states that the probability of observing a sequence
that does not converge to $c$ ultimately vanishes. Intuitively, it states that
once the sequence $x_{n}$ becomes close to $c$, it stays close to $c$.

###### Theorem 2 (Kolmogorov’s Law of Large Numbers (Greene, 2012), Thm D.8).

Let $x_{1},\cdots,x_{n}$ be random variables independently and identically
distributed to a distribution with finite mean $\mu$ and finite variance.
Then,

$\displaystyle\bar{x}_{n}\xrightarrow{a.s.}\mu,$

where

$\displaystyle\bar{x}_{n}=\frac{1}{n}\sum\limits_{i=1}^{n}x_{i}.$

###### Definition 0 (Convergence in Distribution (Greene, 2012), Def D.9).

Let $x_{n}$ be a sequence of random variables indexed by the sample size with
cumulative density function (CDF) $F_{n}(x_{n})$, and let $x$ be random
variable with CDF $F(x).$ If

$\displaystyle\underset{n\rightarrow\infty}{\texttt{lim}}{\left|F_{n}(x_{n})-F(x)\right|}=0,$

at all continuity points of $F(x)$, then $x_{n}$ converges in distribution to
$x.$

###### Definition 0 (Limiting Distribution (Greene, 2012), Def D.10).

Let $x_{n}$ be a sequence of random variables indexed by the sample size with
cumulative density function (CDF) $F_{n}(x_{n})$, and let $x$ be random
variable with CDF $F(x).$ If $x_{n}$ converges in distribution to $x,$ then
$F(x)$ is the limiting distribution of $x_{n}.$ Also, it is written as

$\displaystyle x_{n}\xrightarrow{d}x.$

###### Theorem 5 (Multivariate Lindeberg–Levy Central Limit Theorem (Greene,
2012), Thm D.18A).

Let $x_{1},\cdots,x_{n}$ be random variables independently distributed to a
multivariate distribution with finite mean vector $\mu$ and finite positive
definite covariance matrix $Q,$ then

$\displaystyle\sqrt{n}(\bar{x}_{n}-\mu)\xrightarrow{d}\mathcal{N}(\overrightarrow{\mathbf{0}},Q),$

where

$\displaystyle\bar{x}_{n}=\frac{1}{n}\sum\limits_{i=1}^{n}x_{i}.$

###  A.2. Full Notation Table

Please refer to Table 2 for the full list of notations in this paper,
including those only used in the appendix.

Table 2. Full Notation Table Symbol | Description
---|---
$n$ | number of individual records
$d-1$ | number of features each record has
$B$ |  $n\times(d-1)$ feature matrix
$b$ |  $n\times 1$ label vector, which corresponds to individual records
$[B,b]$ |  $n\times d$ matrix, represents the input database for algorithms
$[{B}^{\prime},{b}^{\prime}]$ |  neighbor database of $[B,b]$ (Def. 1)
$P$ |  $B(B^{T}B)^{-1}B^{T}$, the projection matrix of $B$
$P^{\prime}$ |  ${B}^{\prime}(({B}^{\prime})^{T}{B}^{\prime})^{-1}({B}^{\prime})^{T}$ the projection matrix of neighbor of $B$
$x_{\texttt{opt}}$ |  $(B^{T}B)^{-1}B^{T}b$, (deterministic) optimal solution according to the
| OLS algorithm for database [B, b]
$\tilde{x}_{\texttt{opt}}$ | the randomized OLS solution, which is the output of ALS algorithm
${x_{\texttt{opt}}}^{\prime}$ |  optimal solution according to the OLS algorithm for database $[{B}^{\prime},{b}^{\prime}]$
$v^{T}$ |  $(d-1)\times 1$ individual record differentiating $B$ and its neighbor ${B}^{\prime}$
$w$ |  $(I_{n}-P)b,$ the error vector (vector orthogonal to $B$’s column space)
${w}^{\prime}$ |  error vector for neighboring matrix $[{B}^{\prime},{b}^{\prime}]$
$I_{d}$ |  identity matrix with size $d$

###  A.3. Algorithm of RP LS

Please see Fig. 4 for the random projection LS (RP LS) algorithm.

Input: A matrix $D=[B,b]\in\mathsf{R}^{n\times d}$, where
$B\in\mathsf{R}^{n\times(d-1)}$ and $b\in\mathsf{R}^{n}$. Privacy parameter
$\epsilon\in\mathsf{R}_{>0},\delta\in(0,1).$ Output: The approximate solution
$\tilde{x}_{opt}$ of $Bx=b.$ (1) Set the constant
$c_{1}=\max\\{{\left\|D_{(i)}\right\|}_{2}\\}_{i\in[n]}$. (2) Set the constant
$c_{2}=\sqrt{4c_{1}^{2}(2r\ln{\frac{4}{\delta}}+\ln{\frac{4}{\delta}})/\epsilon}$
(3) Set $\bar{D}=[\bar{B},\bar{b}]$ as the concatenation of $D$ with
$c_{2}I_{d}$ (4) Let matrix $\Pi\in\mathsf{R}^{r\times(n+d)}$ be a random
Gaussian matrix such that any of $\Pi$’s entry
$\left(\Pi\right)_{i,j}\sim\mathcal{N}(0,1)$ is an independent standard normal
random variable. (5) Return $\tilde{x}_{\texttt{opt}}=(\Pi B)^{\dagger}\Pi b.$

Figure 4. Random Projection Least Squares (RP LS) algorithm from (Sheffet,
2019)

##  Appendix B Section 3 Cont’d: Privacy of ALS, Gaussian LS, RP LS

In this section, we include complementary material for Section 3 of the paper.
In particular, the proof of privacy statement of ALS, Gaussian LS, RP LS.

###  B.1. Sec 3.1 Cont’d: Normality Analysis of ALS

In this section, We include the proof of Lemma 1.

###### Proof of Lemma 1.

We wrap some derivations used in the proof in Proposition 1, 2 and 3. We first
state these propositions and their proofs, then conclude the lemma’s proof.

######  Proposition 0.

Let $\Pi b=\Pi Bx_{\texttt{opt}}+\eta.$ Then, $\eta=\Pi w$ and, for each
$i\in[r],$ $\eta_{i}\sim\mathcal{N}(0,{\left\|w\right\|}_{2}^{2}).$

###### Proof.

Since

$\displaystyle\Pi Bx_{\texttt{opt}}+\eta$ $\displaystyle=\Pi
B(B^{T}B)^{-1}B^{T}b+\Pi(I_{n}-P)b$ $\displaystyle=\Pi Pb+\Pi(I_{n}-P)b$
$\displaystyle=\Pi b,$

we show that $\eta=\Pi w.$

For any fixed $i\in[n],$ Let
$g=\Pi_{(i)}^{T}\sim\mathcal{N}(\overrightarrow{\mathbf{0}},I_{n}),$ where
$I_{n}$ is a $n\times n$ identity matrix. Let
$g\sim\mathcal{N}(\overrightarrow{\mathbf{0}},I_{n}),$ where $I_{n}$ is a
$n\times n$ identity matrix.

$\displaystyle\eta_{i}$ $\displaystyle=\langle(I_{n}-P)b,g\rangle.$

Since we know $\\{g_{j}\\}_{j\in[n]}$ are independent Gaussian distribution,
by linear combination property of gaussian distribution we have

$\displaystyle\eta_{i}\sim\mathcal{N}(0,{\left\|(I_{n}-P)b\right\|}_{2}^{2}),$

which completes the proof. ∎

######  Proposition 0.

Let $x\sim\mathcal{N}(0,\sigma^{2})$ be normal distribution with $0$ mean and
$\sigma^{2}$ variance. Then, the second moment of $x$ is
$\mathbb{E}\left(x^{2}\right)=\sigma^{2}$ and the fourth moment of $x$ is
$\mathbb{E}\left(x^{4}\right)=3\sigma^{4}.$

###### Proof.

By variance definition
$Var\left(x\right)=\mathbb{E}\left(x^{2}\right)-\mathbb{E}\left(x\right)^{2}$,
we have

$\displaystyle\mathbb{E}\left(x^{2}\right)=Var\left(x\right)+\mathbb{E}\left(x\right)^{2}=\sigma^{2}.$

Since $x^{2}\sim\sigma^{2}\chi^{2}_{1}$ where $\chi^{2}_{1}$ is chi-square
distribution with $1$ degree of freedom, we have

$\displaystyle
Var\left(x^{2}\right)=Var\left(\sigma^{2}\chi^{2}_{1}\right)=\sigma^{4}Var\left(\chi^{2}_{1}\right)=2\sigma^{4}.$

We further have

$\displaystyle\mathbb{E}\left(x^{4}\right)=Var\left(x^{2}\right)+\mathbb{E}\left(x^{2}\right)^{2}=3\sigma^{4},$

which completes the proof. ∎

######  Proposition 0.

Let $v=B^{T}gg^{T}w,$ where $g\sim\mathcal{N}(0,I_{n}).$ The expectation of
$v$ is $\mathbb{E}\left(v\right)=0$. The covariance matrix of $v$ is
$Var\left(v\right)={\left\|w\right\|}_{2}^{2}B^{T}B$.

###### Proof.

We first compute the expectation of $v.$ We have

$\displaystyle\mathbb{E}\left(v\right)$
$\displaystyle=\mathbb{E}\left(B^{T}gg^{T}w\right)$ (by Linearity of
Expectation) $\displaystyle=B^{T}\mathbb{E}\left(gg^{T}\right)w$ ($gg^{T}\sim
W_{n}(B^{T}B,1)$) $\displaystyle=B^{T}I_{n}w$ $\displaystyle=B^{T}w$ ($w$ is
perpendicular to the column space of $B$) $\displaystyle=0.$

We then compute the covariance matrix of $v$. We have

$\displaystyle Var\left(v\right)=$
$\displaystyle\mathbb{E}\left((v-\mathbb{E}\left(v\right))(v-\mathbb{E}\left(v\right))^{T}\right)$
$\displaystyle=$ $\displaystyle\mathbb{E}\left(vv^{T}\right)$ $\displaystyle=$
$\displaystyle\mathbb{E}\left(B^{T}gg^{T}ww^{T}gg^{T}B\right)$ (1)
$\displaystyle=$ $\displaystyle
B^{T}\mathbb{E}\left(gg^{T}ww^{T}gg^{T}\right)B$

We focus on the expected matrix
$Q=\mathbb{E}\left(gg^{T}ww^{T}gg^{T}\right)\in\mathsf{R}^{(d-1)\times(d-1)}$.
For any fixed $a,b\in[d-1],$ we have

$\displaystyle\left(Q\right)_{a,b}=$
$\displaystyle\mathbb{E}\left(\sum\limits_{i,j}\left(gg^{T}\right)_{a,i}\left(ww^{T}\right)_{i,j}\left(gg^{T}\right)_{j,b}\right)$
$\displaystyle=$
$\displaystyle\sum\limits_{i,j}\left(ww^{T}\right)_{i,j}\mathbb{E}\left(\left(gg^{T}\right)_{a,i}\left(gg^{T}\right)_{j,b}\right)$
$\displaystyle=$
$\displaystyle\sum\limits_{i,j}\left(ww^{T}\right)_{i,j}\mathbb{E}\left(g_{a}g_{b}g_{i}g_{j}\right)$
(2) $\displaystyle=$
$\displaystyle\sum\limits_{i=j}\left(ww^{T}\right)_{i,i}\mathbb{E}\left(g_{a}g_{b}g_{i}^{2}\right)+\sum\limits_{i\neq
j}\left(ww^{T}\right)_{i,j}\mathbb{E}\left(g_{a}g_{b}g_{i}g_{j}\right)$

Now we first focus on the diagonal entries of $Q$, for any fixed
$a\in[d-1],b=a,$ continue the Equation 2, we have

$\displaystyle\left(Q\right)_{a,a}=$
$\displaystyle\sum\limits_{i}\left(ww^{T}\right)_{i,i}\mathbb{E}\left(g_{a}^{2}g_{i}^{2}\right)+\sum\limits_{i\neq
j}\left(ww^{T}\right)_{i,j}\mathbb{E}\left(g_{a}^{2}g_{i}g_{j}\right)$
$\displaystyle=$
$\displaystyle\sum\limits_{i}\left(ww^{T}\right)_{i,i}\mathbb{E}\left(g_{a}^{2}g_{i}^{2}\right)$
$\displaystyle=$
$\displaystyle\sum\limits_{i=a}\left(ww^{T}\right)_{a,a}\mathbb{E}\left(g_{a}^{4}\right)+\sum\limits_{i\neq
a}\left(ww^{T}\right)_{i,i}\mathbb{E}\left(g_{a}^{2}g_{i}^{2}\right)$
$\displaystyle=$ $\displaystyle 3\left(ww^{T}\right)_{a,a}+\sum\limits_{i\neq
a}\left(ww^{T}\right)_{i,i}$ (3) $\displaystyle=$ $\displaystyle
2w_{a}^{2}+{\left\|w\right\|}_{2}^{2}.$

Then, we focus on the off-diagonal entries of $Q,$ for any fixed
$a,b\in[d-1],a\neq b,$ continue the Equation 2, we have

$\displaystyle\left(Q\right)_{a,b}=$
$\displaystyle\sum\limits_{i}\left(ww^{T}\right)_{i,i}\mathbb{E}\left(g_{a}g_{b}g_{i}^{2}\right)+\sum\limits_{i\neq
j}\left(ww^{T}\right)_{i,j}\mathbb{E}\left(g_{a}g_{b}g_{i}g_{j}\right)$
$\displaystyle=$ $\displaystyle\sum\limits_{i\neq
j}\left(ww^{T}\right)_{i,j}\mathbb{E}\left(g_{a}g_{b}g_{i}g_{j}\right)$
$\displaystyle=$
$\displaystyle\sum\limits_{(i,j)=(a,b)\atop\texttt{or}(j,i)=(b,a)}\left(ww^{T}\right)_{i,j}\mathbb{E}\left(g_{a}g_{b}g_{i}g_{j}\right)+\sum\limits_{(i,j)\neq(a,b)\atop\texttt{or}(j,i)\neq(b,a)}\left(ww^{T}\right)_{i,j}\mathbb{E}\left(g_{a}g_{b}g_{i}g_{j}\right)$
$\displaystyle=$
$\displaystyle\left(ww^{T}\right)_{a,b}\mathbb{E}\left(g_{a}^{2}g_{b}^{2}\right)+\left(ww^{T}\right)_{b,a}\mathbb{E}\left(g_{a}^{2}g_{b}^{2}\right)$
(4) $\displaystyle=$ $\displaystyle 2\left(ww^{T}\right)_{a,b}.$

Collect together the Equation 3 and Equation 4 and let $I(a,b)$ be the
equality predicate, we have for any fixed $a,b\in[d-1]$

(5)
$\displaystyle\left(Q\right)_{a,b}=2\left(ww^{T}\right)_{a,b}+{\left\|w\right\|}_{2}^{2}I(a,b),$

or

(6) $\displaystyle Q=2ww^{T}+{\left\|w\right\|}_{2}^{2}I_{n}.$

Finally, plug the Equation 6 into Equation 1, we have

$\displaystyle Var\left(v\right)=$ $\displaystyle
B^{T}\mathbb{E}\left(gg^{T}ww^{T}gg^{T}\right)B$ $\displaystyle=$
$\displaystyle B^{T}(2ww^{T}+{\left\|w\right\|}_{2}^{2}I_{n})B$
$\displaystyle=$ $\displaystyle
2B^{T}ww^{T}B+{\left\|w\right\|}_{2}^{2}B^{T}B$ $\displaystyle=$
$\displaystyle{\left\|w\right\|}_{2}^{2}B^{T}B,$

which completes the proof. ∎

Now we have proven the crucial Propositions above, we continue the proof for
Lemma 1.

Let $x_{\texttt{opt}}=(B)^{\dagger}b=(B^{T}B)^{-1}B^{T}b.$ By Proposition 1,
we have

(7) $\displaystyle\Pi b=\Pi Bx_{\texttt{opt}}+\eta,$

where $\eta=\Pi w,$ and $w=(I_{n}-P)b.$

We first look at the distribution of the difference between
$\tilde{x}_{\texttt{opt}}$ and $x_{\texttt{opt}}$.

$\displaystyle\tilde{x}_{\texttt{opt}}-x_{\texttt{opt}}$ $\displaystyle=(\Pi
B)^{\dagger}\Pi b-(B)^{\dagger}b$ $\displaystyle=((\Pi B)^{T}\Pi B)^{-1}(\Pi
B)^{T}\Pi b-(B^{T}B)^{-1}B^{T}b$ $\displaystyle=((\Pi B)^{T}\Pi B)^{-1}(\Pi
B)^{T}(\Pi Bx_{\texttt{opt}}+\eta)-(B^{T}B)^{-1}B^{T}b$ $\displaystyle=((\Pi
B)^{T}\Pi B)^{-1}(\Pi B)^{T}(\Pi
B(B^{T}B)^{-1}B^{T}b+\eta)-(B^{T}B)^{-1}B^{T}b$
$\displaystyle=(B^{T}B)^{-1}B^{T}b+((\Pi B)^{T}\Pi B)^{-1}(\Pi
B)^{T}\eta-(B^{T}B)^{-1}B^{T}b$ $\displaystyle=((\Pi B)^{T}\Pi B)^{-1}(\Pi
B)^{T}\eta$ (8) $\displaystyle=(\frac{1}{r}(\Pi B)^{T}\Pi
B)^{-1}\frac{1}{r}(\Pi B)^{T}\eta$

We first look at the first term $(\frac{1}{r}(\Pi B)^{T}\Pi B)^{-1}$. When $r$
is large enough, we have

$\displaystyle(\frac{1}{r}(\Pi B)^{T}\Pi B)^{-1}$ $\displaystyle=$
$\displaystyle(\frac{1}{r}\sum\limits_{i=1}^{r}((\Pi B)^{T})^{(i)}\Pi
B_{(i)})^{-1}$ $\displaystyle=$
$\displaystyle(\frac{1}{r}\sum\limits_{i=1}^{r}(\Pi B_{(i)})^{T}\Pi
B_{(i)})^{-1}$ $\displaystyle=$
$\displaystyle(\frac{1}{r}\sum\limits_{i=1}^{r}(\Pi_{(i)}B)^{T}\Pi_{(i)}B)^{-1}$
($Z_{i}=(\Pi_{(i)}B)^{T}\Pi_{(i)}B\sim W_{n}(B^{T}B,1)$) $\displaystyle=$
$\displaystyle(\frac{1}{r}\sum\limits_{i=1}^{r}Z_{i})^{-1}$ $\displaystyle=$
$\displaystyle(\mathbb{E}\left(Z_{i}\right))^{-1}$ $\displaystyle=$
$\displaystyle(B^{T}B)^{-1}.$

We then look at the second term $\frac{1}{r}(\Pi B)^{T}\eta$. When $r$ is
large enough, we have

$\displaystyle\frac{1}{r}(\Pi B)^{T}\eta$ $\displaystyle=$
$\displaystyle\frac{1}{r}\sum\limits_{i=1}^{r}((\Pi B)^{T})^{(i)}\eta_{i}$
$\displaystyle=$ $\displaystyle\frac{1}{r}\sum\limits_{i=1}^{r}(\Pi
B_{(i)}\eta_{i})^{T}$ $\displaystyle=$
$\displaystyle\frac{1}{r}\sum\limits_{i=1}^{r}(\Pi_{(i)}B\eta_{i})^{T}$
$\displaystyle=$
$\displaystyle\frac{1}{r}\sum\limits_{i=1}^{r}(g^{T}B\eta_{i})^{T}$
$\displaystyle=$
$\displaystyle\frac{1}{r}\sum\limits_{i=1}^{r}(g^{T}B\cdot\langle(I_{n}-P)b,g\rangle)^{T}$
$\displaystyle=$
$\displaystyle\frac{1}{r}\sum\limits_{i=1}^{r}(g^{T}B\cdot\langle
w,g\rangle)^{T}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{r}}\left(\sqrt{r}\left(\frac{1}{r}\sum\limits_{i=1}^{r}B^{T}gg^{T}w\right)\right)$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{r}}\left(\sqrt{r}\left(\frac{1}{r}\sum\limits_{i=1}^{r}B^{T}gg^{T}w-\mathbb{E}\left(B^{T}gg^{T}w\right)\right)\right)$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{r}}\mathcal{N}(\overrightarrow{\mathbf{0}},{\left\|w\right\|}_{2}^{2}B^{T}B)$
(10) $\displaystyle=$
$\displaystyle\mathcal{N}(\overrightarrow{\mathbf{0}},\frac{{\left\|w\right\|}_{2}^{2}B^{T}B}{r})$

Plugging the Equation LABEL:equ:_asymptotic_distribution_of_xhat:_first_term
and Equation 10 into the Equation 8, we have, when $r$ is large enough,

$\displaystyle\tilde{x}_{\texttt{opt}}-x_{\texttt{opt}}$
$\displaystyle=(B^{T}B)^{-1}\mathcal{N}(\overrightarrow{\mathbf{0}},\frac{{\left\|w\right\|}_{2}^{2}B^{T}B}{r})$
$\displaystyle=\mathcal{N}(\overrightarrow{\mathbf{0}},\frac{{\left\|w\right\|}_{2}^{2}(B^{T}B)^{-1}B^{T}B(B^{T}B)^{-1}}{r})$
$\displaystyle=\mathcal{N}(\overrightarrow{\mathbf{0}},\frac{{\left\|w\right\|}_{2}^{2}(B^{T}B)^{-1}}{r}),$

or,

$\displaystyle\tilde{x}_{\texttt{opt}}=\mathcal{N}(x_{\texttt{opt}},\frac{{\left\|w\right\|}_{2}^{2}(B^{T}B)^{-1}}{r}),$

where $x_{\texttt{opt}}=(B^{T}B)^{-1}B^{T}b$ and $w=(I_{n}-P)b$, which
completes the proof. ∎

###  B.2. Sec 3.2 Cont’d: DP Spectrum of general Multi-dimensional Gaussians

In this section, we prove Lemma 2.

###### Proof of Lemma 2.

We first recall the cdf of $X$ over a fixed region $S\subseteq\mathsf{R}^{d}$

$\displaystyle\Pr[X\in
S]=\int_{S}\frac{1}{(2\pi)^{d/2}\det{(\Sigma_{1})}^{1/2}}\exp{\left(-\frac{1}{2}(x-\mu_{1})^{T}\Sigma_{1}^{-1}(x-\mu_{1})\right)}\mathrm{d}x,$

and the cdf of $Y$ over a fixed region $S\subseteq\mathsf{R}^{d}$

$\displaystyle\Pr[Y\in
S]=\int_{S}\frac{1}{(2\pi)^{d/2}\det{(\Sigma_{2})}^{1/2}}\exp{\left(-\frac{1}{2}(x-\mu_{2})^{T}\Sigma_{2}^{-1}(x-\mu_{2})\right)}\mathrm{d}x.$

Further, we have, for a fixed region $S\subseteq\mathsf{R}^{d}$,

$\displaystyle\Pr[X\in S]-\exp\left(\epsilon\right)\Pr[Y\in S]$
$\displaystyle=$
$\displaystyle\int_{S}\frac{\exp{\left(-\frac{1}{2}(x-\mu_{1})^{T}\Sigma_{1}^{-1}(x-\mu_{1})\right)}}{(2\pi)^{d/2}\det{(\Sigma_{1})}^{1/2}}\mathrm{d}x$
$\displaystyle-\exp\left(\epsilon\right)\int_{S}\frac{\exp{\left(-\frac{1}{2}(x-\mu_{2})^{T}\Sigma_{2}^{-1}(x-\mu_{2})\right)}}{(2\pi)^{d/2}\det{(\Sigma_{2})}^{1/2}}\mathrm{d}x$
$\displaystyle=$
$\displaystyle\int_{S}\frac{\exp{\left(-\frac{1}{2}(x-\mu_{1})^{T}\Sigma_{1}^{-1}(x-\mu_{1})\right)}}{(2\pi)^{d/2}\det{(\Sigma_{1})}^{1/2}}$
$\displaystyle-\frac{\exp{\left(\epsilon-\frac{1}{2}(x-\mu_{2})^{T}\Sigma_{2}^{-1}(x-\mu_{2})\right)}}{(2\pi)^{d/2}\det{(\Sigma_{2})}^{1/2}}\mathrm{d}x$
$\displaystyle=$
$\displaystyle\int_{\Sigma_{1}^{1/2}S+\mu_{1}}\frac{\exp\left(-\frac{1}{2}z^{T}z\right)}{(2\pi)^{d/2}}$
$\displaystyle-\frac{\exp\left(\epsilon\right)\det{(\Sigma_{1})}^{1/2}}{(2\pi)^{d/2}\det{(\Sigma_{2})}^{1/2}}\exp\left(-\frac{1}{2}(\Sigma_{1}^{1/2}z+\mu_{1}-\mu_{2})^{T}\Sigma_{2}^{-1}(\Sigma_{1}^{1/2}z+\mu_{1}-\mu_{2})\right)\mathrm{d}z$
$\displaystyle=$
$\displaystyle\int_{\Sigma_{1}^{1/2}S+\mu_{1}}\frac{\exp\left(-\frac{1}{2}z^{T}z\right)}{(2\pi)^{d/2}}\bigg{(}1-\frac{\exp\left(\epsilon\right)\det{(\Sigma_{1})}^{1/2}}{\det{(\Sigma_{2})}^{1/2}}$
(11)
$\displaystyle\exp\left(-\frac{1}{2}(\Sigma_{1}^{1/2}z+\mu_{1}-\mu_{2})^{T}\Sigma_{2}^{-1}(\Sigma_{1}^{1/2}z+\mu_{1}-\mu_{2})+\frac{1}{2}z^{T}z\right)\bigg{)}\mathrm{d}z$
$\displaystyle=$
$\displaystyle\int_{\Sigma_{1}^{1/2}S+\mu_{1}}\frac{\exp\left(-\frac{1}{2}z^{T}z\right)}{(2\pi)^{d/2}}\bigg{(}1-$
$\displaystyle\exp\left(-\frac{1}{2}(\Sigma_{1}^{1/2}z+\mu_{1}-\mu_{2})^{T}\Sigma_{2}^{-1}(\Sigma_{1}^{1/2}z+\mu_{1}-\mu_{2})+\frac{1}{2}z^{T}z+\epsilon+\ln{\sqrt{\frac{\det{(\Sigma_{1})}}{\det{(\Sigma_{2})}}}}\right)\bigg{)}\mathrm{d}z$
(12) $\displaystyle=$
$\displaystyle\int_{\Sigma_{1}^{1/2}S+\mu_{1}}\frac{\exp\left(-\frac{1}{2}z^{T}z\right)}{(2\pi)^{d/2}}(1-\exp\left(\psi\right))\mathrm{d}z,$

where
$\psi=-\frac{1}{2}(\Sigma_{1}^{1/2}z+\mu_{1}-\mu_{2})^{T}\Sigma_{2}^{-1}(\Sigma_{1}^{1/2}z+\mu_{1}-\mu_{2})+\frac{1}{2}z^{T}z+\epsilon+\ln{\sqrt{\frac{\det{(\Sigma_{1})}}{\det{(\Sigma_{2})}}}}$.

We then do some arrangement on the expression $\psi$

$\displaystyle\psi$
$\displaystyle=\frac{1}{2}z^{T}z-\frac{1}{2}(\Sigma_{1}^{1/2}z+\mu_{1}-\mu_{2})^{T}\Sigma_{2}^{-1}(\Sigma_{1}^{1/2}z+\mu_{1}-\mu_{2})$
$\displaystyle+\epsilon+\ln{\sqrt{\frac{\det{(\Sigma_{1})}}{\det{(\Sigma_{2})}}}}$
$\displaystyle=\frac{1}{2}z^{T}z-\frac{1}{2}z^{T}\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}z-(\mu_{1}-\mu_{2})^{T}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}z$
$\displaystyle-\frac{1}{2}(\mu_{1}-\mu_{2})^{T}\Sigma_{2}^{-1}(\mu_{1}-\mu_{2})+\epsilon+\ln{\sqrt{\frac{\det{(\Sigma_{1})}}{\det{(\Sigma_{2})}}}}$
$\displaystyle=\frac{1}{2}z^{T}(I_{d}-\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2})z-(\mu_{1}-\mu_{2})^{T}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}z$
$\displaystyle-\frac{1}{2}(\mu_{1}-\mu_{2})^{T}\Sigma_{2}^{-1}(\mu_{1}-\mu_{2})+\epsilon+\ln{\sqrt{\frac{\det{(\Sigma_{1})}}{\det{(\Sigma_{2})}}}}$
(Since $I_{d}-\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}$ is symmetric,
let it be factorized as $UAU^{T},$)
$\displaystyle=\frac{1}{2}v^{T}Av-(\mu_{1}-\mu_{2})^{T}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}Uv+\epsilon+\ln{\sqrt{\frac{\det{(\Sigma_{1})}}{\det{(\Sigma_{2})}}}}$
(where $U$ is orthogonal and $A$ is diagonal, $v=U^{T}z,z=Uv$)
$\displaystyle-\frac{1}{2}(\mu_{1}-\mu_{2})^{T}\Sigma_{2}^{-1}(\mu_{1}-\mu_{2})$

Recall we have defined in the theorem’s statement,

(Rearrange definition of $A$) $\displaystyle
A=U^{T}(I_{d}-\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2})U,$
$\displaystyle b=-U^{T}\Sigma_{1}^{1/2}\Sigma_{2}^{-1}(\mu_{1}-\mu_{2}),$

and

$\displaystyle
c=\epsilon+\ln{\sqrt{\frac{\det{(\Sigma_{1})}}{\det{(\Sigma_{2})}}}}-\frac{1}{2}(\mu_{1}-\mu_{2})^{T}\Sigma_{2}^{-1}(\mu_{1}-\mu_{2}).$

Then we plug the expression of $\Psi$ into the Equation 12, and have

$\displaystyle\Pr[X\in S]-\exp\left(\epsilon\right)\Pr[Y\in S]$
$\displaystyle=\int_{\Sigma_{1}^{1/2}S+\mu_{1}}\frac{\exp\left(-\frac{1}{2}z^{T}z\right)}{(2\pi)^{d/2}}(1-\exp\left(\psi\right))\mathrm{d}z$
($v=Uz,z=U^{T}v$)
$\displaystyle=\int_{U(\Sigma_{1}^{1/2}S+\mu_{1})}\frac{\exp\left(-\frac{1}{2}v^{T}v\right)}{(2\pi)^{d/2}}(1-\exp\left(\frac{1}{2}v^{T}Av+b^{T}v+c\right))\mathrm{d}v$

To compute $\delta_{1},$ we need to integrate over the region where $\Psi\leq
0,$ which maximizes the integral over all possible $S$. That is,

$\displaystyle\delta_{1}$ $\displaystyle=\int_{\Psi\leq
0}\frac{\exp\left(-\frac{1}{2}v^{T}v\right)}{(2\pi)^{d/2}}(1-\exp\left(\frac{1}{2}v^{T}Av+b^{T}v+c\right))\mathrm{d}v$
$\displaystyle=\int_{v\in\mathsf{R}^{d}}\frac{\exp\left(-\frac{1}{2}v^{T}v\right)}{(2\pi)^{d/2}}\max\\{0,1-\exp\left(\frac{1}{2}v^{T}Av+b^{T}v+c\right)\\}\mathrm{d}v$
($Z\sim\mathcal{N}(\overrightarrow{\mathbf{0}},I_{d})$)
$\displaystyle=\int_{v\in\mathsf{R}^{d}}\Pr[Z=v]\max\\{0,1-\exp\left(\frac{1}{2}v^{T}Av+b^{T}v+c\right)\\}\mathrm{d}v$
$\displaystyle=\mathbb{E}\left(\max\\{0,1-\exp\left(\frac{1}{2}Z^{T}AZ+b^{T}Z+c\right)\\}\right),$

where we can regard $\delta_{1}$ as the expectation of the function of a
standard $d$-dimensional multivariate Gaussians. ∎

###  B.3. Sec 3.3 Cont’d: Plugging in Parameters of Lemma 3

In this section, we plug in the parameters in Lemma 3 and obtain the full
expression of ALS’s privacy (Lemma 4) as a function of the database’s leverage
and error-residual. We first state Lemma 4, followed by its proof.

######  Lemma 0.

Let $M=B^{T}B$. Let $v_{i}$ be the $i$-th row of $B.$ Let
$U_{i,1}A_{i,1}U_{i,1}^{T}$ be the SVD of
$I_{d-1}-\frac{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}-w_{(i)}^{2}}M^{-1/2}(M-v_{i}v_{i}^{T})M^{-1/2}$,
let
$b_{i,1}=-U_{i,1}^{T}\frac{\sqrt{r}w_{(i)}{\left\|w\right\|}_{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}-w_{(i)}^{2}}M^{-1/2}(M-v_{i}v_{i}^{T})M^{-1}v_{i}$,
let
$c_{i,1}=\epsilon-\frac{1}{2}\ln{\left((1-\frac{w_{(i)}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}})^{d-1}(\frac{1}{1-\left(P\right)_{i,i}})\right)}-\frac{1}{2}\frac{r\left(P\right)_{i,i}w_{(i)}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}-w_{(i)}^{2}}$.

Let $U_{i,2}A_{i,2}U_{i,2}^{T}$ be the SVD of
$I_{d-1}-(1-\frac{w_{(i)}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}})(M-v_{i}v_{i}^{T})^{-1/2}M(M-v_{i}v_{i}^{T})^{-1/2}$,
let
$b_{i,2}=U_{i,2}^{T}\frac{\sqrt{r}w_{(i)}\sqrt{{\left\|w\right\|}_{2}^{2}-\frac{w_{(i)}^{2}}{1-\left(P\right)_{i,i}}}}{{\left\|w\right\|}_{2}^{2}(1-\left(P\right)_{i,i})}(M-v_{i}v_{i}^{T})^{-1/2}v_{i}$,
and let
$c_{i,2}=\epsilon+\frac{1}{2}\ln{((1-\frac{w_{(i)}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}})^{d-1}(\frac{1}{1-\left(P\right)_{i,i}}))}-\frac{1}{2}\frac{rw_{(i)}^{2}\left(P\right)_{i,i}}{{\left\|w\right\|}_{2}^{2}(1-\left(P\right)_{i,i})^{2}}$
.

Then,

$\displaystyle\delta_{ALS}=\max_{i}\bigg{\\{}\max\bigg{\\{}$
$\displaystyle\mathbb{E}\left(\max\\{0,1-\exp\left(\frac{1}{2}Z^{T}A_{i,1}Z+b_{i,1}^{T}Z+c_{i,1}\right)\\}\right),$
$\displaystyle\mathbb{E}\left(\max\\{0,1-\exp\left(\frac{1}{2}Z^{T}A_{i,2}Z+b_{i,2}^{T}Z+c_{i,2}\right)\\}\right)\bigg{\\}}\bigg{\\}},$

where $Z\sim\mathcal{N}(\overrightarrow{\mathbf{0}},I_{d-1})$.

###### Proof of Lemma 4.

We first state and prove useful Propositions 5, 6, 7, 8 and 9, then conclude
with the lemma’s proof.

######  Proposition 0.

$\displaystyle\mathbf{rank}(Q)=\mathbf{rank}({Q}^{\prime})=d-1.$

###### Proof.

This is because

$\displaystyle\mathbf{rank}(Q)$
$\displaystyle=\mathbf{rank}(\frac{{\left\|w\right\|}_{2}^{2}(B^{T}B)^{-1}}{r})$
$\displaystyle=\mathbf{rank}((B^{T}B)^{-1})$ ($B^{T}B$ is a full rank and
symmetric matrix) $\displaystyle=\mathbf{rank}(B^{T}B)$
$\displaystyle=\mathbf{rank}(B)=d-1,$

And similarly
$\mathbf{rank}({Q}^{\prime})=\mathbf{rank}({B}^{\prime})=\mathbf{rank}(Q)=d-1.$
∎

######  Proposition 0.

$\displaystyle{b}^{\prime T}{B}^{\prime}=b^{T}B-b_{(i)}v^{T}.$

###### Proof.

This is because

$\displaystyle{b}^{\prime T}{B}^{\prime}=$ $\displaystyle\sum\limits_{j\neq
i,j=1}^{n}b_{(j)}B_{(j)}$ $\displaystyle=$
$\displaystyle\sum\limits_{j=1}^{n}b_{(j)}B_{(j)}-b_{(i)}v^{T}$
$\displaystyle=$ $\displaystyle b^{T}B-b_{(i)}v^{T}.$

∎

######  Proposition 0.

$\displaystyle{x_{\texttt{opt}}}^{\prime}=x_{\texttt{opt}}-\frac{w_{(i)}(B^{T}B)^{-1}v}{1-\left(P\right)_{i,i}}.$

###### Proof.

This is because

$\displaystyle{x_{\texttt{opt}}}^{\prime}-x_{\texttt{opt}}$ (by Definition)
$\displaystyle=$
$\displaystyle(({B}^{\prime})^{T}{B}^{\prime})^{-1}({B}^{\prime})^{T}{b}^{\prime}-x_{\texttt{opt}}$
$\displaystyle=$
$\displaystyle(B^{T}B-vv^{T})^{-1}({B}^{\prime})^{T}{b}^{\prime}-x_{\texttt{opt}}$
(by Woodbury matrix identity) $\displaystyle=$
$\displaystyle\left((B^{T}B)^{-1}+\frac{(B^{T}B)^{-1}vv^{T}(B^{T}B)^{-1}}{1-v^{T}(B^{T}B)^{-1}v}\right)({B}^{\prime})^{T}{b}^{\prime}-x_{\texttt{opt}}$
(by Proposition 6) $\displaystyle=$
$\displaystyle\left((B^{T}B)^{-1}+\frac{(B^{T}B)^{-1}vv^{T}(B^{T}B)^{-1}}{1-v^{T}(B^{T}B)^{-1}v}\right)(B^{T}b-b_{(i)}v)-x_{\texttt{opt}}$
$\displaystyle=$
$\displaystyle\frac{(B^{T}B)^{-1}vv^{T}(B^{T}B)^{-1}(B^{T}b-b_{(i)}v)}{1-v^{T}(B^{T}B)^{-1}v}-(B^{T}B)^{-1}b_{(i)}v$
$\displaystyle=$
$\displaystyle\frac{(B^{T}B)^{-1}vv^{T}(B^{T}B)^{-1}B^{T}b-b_{(i)}(B^{T}B)^{-1}v}{1-v^{T}(B^{T}B)^{-1}v}$
$\displaystyle=$
$\displaystyle\frac{(B^{T}B)^{-1}vv^{T}x_{\texttt{opt}}-b_{(i)}(B^{T}B)^{-1}v}{1-v^{T}(B^{T}B)^{-1}v}$
$\displaystyle=$
$\displaystyle\frac{(v^{T}x_{\texttt{opt}}-b_{(i)})(B^{T}B)^{-1}v}{1-\left(P\right)_{i,i}}$
$\displaystyle=$
$\displaystyle\frac{(Pb_{(i)}-b_{(i)})(B^{T}B)^{-1}v}{1-\left(P\right)_{i,i}}$
$\displaystyle=$
$\displaystyle\frac{-w_{(i)}(B^{T}B)^{-1}v}{1-\left(P\right)_{i,i}}.$

∎

######  Proposition 0.

$\displaystyle{\left\|{w}^{\prime}\right\|}_{2}^{2}={\left\|w\right\|}_{2}^{2}-\frac{w_{(i)}^{2}}{1-\left(P\right)_{i,i}}.$

###### Proof.

$\displaystyle{\left\|w\right\|}_{2}^{2}-{\left\|{w}^{\prime}\right\|}_{2}^{2}$
(by error vector $w,{w}^{\prime}$’s definition) $\displaystyle=$
$\displaystyle{\left\|(I-P)b\right\|}_{2}^{2}-{\left\|(I-{P}^{\prime}){b}^{\prime}\right\|}_{2}^{2}$
$\displaystyle=$ $\displaystyle b^{T}(I-P)^{T}(I-P)b-{b}^{\prime
T}(I-{P}^{\prime})^{T}(I-{P}^{\prime}){b}^{\prime}$ ($I-P,I-{P}^{\prime}$ are
all idempotent) $\displaystyle=$ $\displaystyle b^{T}(I-P)b-{b}^{\prime
T}(I-{P}^{\prime}){b}^{\prime}$ $\displaystyle=$
$\displaystyle{\left\|b\right\|}_{2}^{2}-{\left\|{b}^{\prime}\right\|}_{2}^{2}-b^{T}Pb+{b}^{\prime
T}{P}^{\prime}{b}^{\prime}$ $\displaystyle=$ $\displaystyle
b_{(i)}^{2}-b^{T}Pb+{b}^{\prime T}{P}^{\prime}{b}^{\prime}$ $\displaystyle=$
$\displaystyle b_{(i)}^{2}-b^{T}Bx_{\texttt{opt}}+{b}^{\prime
T}{B}^{\prime}{x_{\texttt{opt}}}^{\prime}$ (by Proposition 6 and Proposition 7
) $\displaystyle=$ $\displaystyle
b_{(i)}^{2}-b^{T}Bx_{\texttt{opt}}+(b^{T}B-b_{(i)}v^{T})(x_{\texttt{opt}}+\frac{(v^{T}x_{\texttt{opt}}-b_{(i)})(B^{T}B)^{-1}v}{1-\left(P\right)_{i,i}})$
$\displaystyle=$ $\displaystyle
b_{(i)}^{2}-b_{(i)}(Pb)_{(i)}+\frac{(b^{T}B-b_{(i)}v^{T})(v^{T}x_{\texttt{opt}}-b_{(i)})(B^{T}B)^{-1}v}{1-\left(P\right)_{i,i}}$
($v^{T}x_{\texttt{opt}}=(Pb)_{(i)}$) $\displaystyle=$ $\displaystyle
b_{(i)}^{2}-b_{(i)}(Pb)_{(i)}+\frac{((Pb)_{(i)}-b_{(i)})(b^{T}B-b_{(i)}v^{T})(B^{T}B)^{-1}v}{1-\left(P\right)_{i,i}}$
($\left(P\right)_{i,i}=v^{T}(B^{T}B)^{-1}v$) $\displaystyle=$ $\displaystyle
b_{(i)}^{2}-b_{(i)}(Pb)_{(i)}+\frac{((Pb)_{(i)}-b_{(i)})(v^{T}x_{\texttt{opt}}-b_{(i)}\left(P\right)_{i,i})}{1-\left(P\right)_{i,i}}$
$\displaystyle=$
$\displaystyle\frac{(b_{(i)}-(Pb)_{(i)})^{2}}{1-\left(P\right)_{i,i}}$
$\displaystyle=$ $\displaystyle\frac{w_{(i)}^{2}}{1-\left(P\right)_{i,i}}.$

∎

######  Proposition 0.

$\displaystyle\frac{\det{({Q}^{\prime})}^{1/2}}{\det{(Q)}^{1/2}}=\left((1-\frac{w_{(i)}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}})^{d-1}(\frac{1}{1-\left(P\right)_{i,i}})\right)^{1/2}.$

###### Proof.

This is because

(by Definition)
$\displaystyle\frac{\det{({Q}^{\prime})}^{1/2}}{\det{(Q)}^{1/2}}$
$\displaystyle=\frac{\det{(\frac{{\left\|{w}^{\prime}\right\|}_{2}^{2}(({B}^{\prime})^{T}{B}^{\prime})^{-1}}{r})}^{1/2}}{\det{(\frac{{\left\|w\right\|}_{2}^{2}(B^{T}B)^{-1}}{r})}^{1/2}}$
$\displaystyle=\left(\frac{\frac{{\left\|{w}^{\prime}\right\|}_{2}^{2}}{r\det{(({B}^{\prime})^{T}{B}^{\prime}})}}{\frac{{\left\|w\right\|}_{2}^{2}}{r\det{(B^{T}B)}}}\right)^{1/2}$
(Matrices $B^{T}B,({B}^{\prime})^{T}({B}^{\prime})$ are of shape $d-1\times
d-1$ )
$\displaystyle=(\frac{{\left\|{w}^{\prime}\right\|}_{2}}{{\left\|w\right\|}_{2}})^{d-1}\left(\frac{\det{(B^{T}B)}}{\det{(({B}^{\prime})^{T}{B}^{\prime})}}\right)^{1/2}$
(by Matrix Determinant Lemma)
$\displaystyle=(\frac{{\left\|{w}^{\prime}\right\|}_{2}}{{\left\|w\right\|}_{2}})^{d-1}\left(\frac{1}{1-v^{T}(B^{T}B)^{-1}v}\right)^{1/2}$
$\displaystyle=(\frac{{\left\|{w}^{\prime}\right\|}_{2}}{{\left\|w\right\|}_{2}})^{d-1}\left(\frac{1}{1-B_{(i)}(B^{T}B)^{-1}(B_{(i)})^{T}}\right)^{1/2}$
$\displaystyle=(\frac{{\left\|{w}^{\prime}\right\|}_{2}}{{\left\|w\right\|}_{2}})^{d-1}\left(\frac{1}{1-\left(P\right)_{i,i}}\right)^{1/2}$
(${\left\|{w}^{\prime}\right\|}_{2}^{2}={\left\|w\right\|}_{2}^{2}-\frac{w_{(i)}^{2}}{1-\left(P\right)_{i,i}}$
by Proposition 8)
$\displaystyle=\left((\frac{{\left\|{w}^{\prime}\right\|}_{2}^{2}-{\left\|w\right\|}_{2}^{2}}{{\left\|w\right\|}_{2}^{2}}+1)^{d-1}(\frac{1}{1-\left(P\right)_{i,i}})\right)^{1/2}$
$\displaystyle=\left((1-\frac{w_{(i)}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}})^{d-1}(\frac{1}{1-\left(P\right)_{i,i}})\right)^{1/2}.$

∎

We continue with the proof of Lemma 4, by applying the above propositions and
Lemma 2.

Without loss of generality, we consider the neighboring pair
$[B,b]\simeq[{B}^{\prime},{b}^{\prime}]$ which differs at $i$-th row. Let $v$
be the row differentiating $B$ and its neighbor ${B}^{\prime}$. We first
recall $\mu_{1}=x_{\texttt{opt}},$ $\Sigma_{1}=Q,$
$\mu_{2}=x_{\texttt{opt}}^{\prime}$ and $\Sigma_{2}=Q^{\prime}$. Let
$U_{1}A_{1}U_{1}^{T}$ be the SVD of
$I_{d-1}-\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}$. Plug in the
expression, we have

$\displaystyle I_{d-1}-\Sigma_{1}^{1/2}\Sigma_{2}^{-1}\Sigma_{1}^{1/2}$
$\displaystyle=$ $\displaystyle
I_{d-1}-\frac{{\left\|w\right\|}_{2}(B^{T}B)^{-1/2}}{\sqrt{r}}\frac{r}{{\left\|{w}^{\prime}\right\|}_{2}^{2}}(({B}^{\prime})^{T}{B}^{\prime})\frac{{\left\|w\right\|}_{2}(B^{T}B)^{-1/2}}{\sqrt{r}}$
$\displaystyle=$ $\displaystyle
I_{d-1}-\frac{{\left\|w\right\|}_{2}^{2}}{{\left\|{w}^{\prime}\right\|}_{2}^{2}}(B^{T}B)^{-1/2}(({B}^{\prime})^{T}{B}^{\prime})(B^{T}B)^{-1/2}$
($M=B^{T}B$, $B^{T}B-({B}^{\prime})^{T}{B}^{\prime}=vv^{T}$) $\displaystyle=$
$\displaystyle
I_{d-1}-\frac{{\left\|w\right\|}_{2}^{2}}{{\left\|{w}^{\prime}\right\|}_{2}^{2}}M^{-1/2}(M-vv^{T})M^{-1/2}$
(by Proposition 8) $\displaystyle=$ $\displaystyle
I_{d-1}-\frac{{\left\|w\right\|}_{2}^{2}}{{\left\|w\right\|}_{2}^{2}-\frac{w_{(i)}^{2}}{1-\left(P\right)_{i,i}}}M^{-1/2}(M-vv^{T})M^{-1/2}$
$\displaystyle=$ $\displaystyle
I_{d-1}-\frac{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}-w_{(i)}^{2}}M^{-1/2}(M-vv^{T})M^{-1/2}.$

Plug in the expression
$b_{1}=-U_{1}^{T}\Sigma_{1}^{1/2}\Sigma_{2}^{-1}(\mu_{1}-\mu_{2}),$ we have

$\displaystyle b_{1}=$ $\displaystyle-
U_{1}^{T}\Sigma_{1}^{1/2}\Sigma_{2}^{-1}(\mu_{1}-\mu_{2})$ $\displaystyle=$
$\displaystyle-
U_{1}^{T}\frac{{\left\|w\right\|}_{2}(B^{T}B)^{-1/2}}{\sqrt{r}}\frac{r}{{\left\|{w}^{\prime}\right\|}_{2}^{2}}(({B}^{\prime})^{T}{B}^{\prime})(x_{\texttt{opt}}-x_{\texttt{opt}}^{\prime})$
$\displaystyle=$ $\displaystyle-
U_{1}^{T}\sqrt{r}\frac{{\left\|w\right\|}_{2}}{{\left\|{w}^{\prime}\right\|}_{2}^{2}}M^{-1/2}(M-vv^{T})(x_{\texttt{opt}}-x_{\texttt{opt}}^{\prime})$
(By Proposition 7) $\displaystyle=$ $\displaystyle-
U_{1}^{T}\sqrt{r}\frac{{\left\|w\right\|}_{2}}{{\left\|{w}^{\prime}\right\|}_{2}^{2}}M^{-1/2}(M-vv^{T})\frac{w_{(i)}(B^{T}B)^{-1}v}{1-\left(P\right)_{i,i}}$
(by Proposition 8) $\displaystyle=$ $\displaystyle-
U_{1}^{T}\sqrt{r}\frac{{\left\|w\right\|}_{2}}{{\left\|w\right\|}_{2}^{2}-\frac{w_{(i)}^{2}}{1-\left(P\right)_{i,i}}}M^{-1/2}(M-vv^{T})\frac{w_{(i)}(B^{T}B)^{-1}v}{1-\left(P\right)_{i,i}}$
$\displaystyle=$ $\displaystyle-
U_{1}^{T}\frac{\sqrt{r}w_{(i)}{\left\|w\right\|}_{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}-w_{(i)}^{2}}M^{-1/2}(M-vv^{T})M^{-1}v.$

Plug in the expression
$c_{1}=\epsilon+\ln{\sqrt{\frac{\det{(\Sigma_{1})}}{\det{(\Sigma_{2})}}}}-\frac{1}{2}(\mu_{1}-\mu_{2})^{T}\Sigma_{2}^{-1}(\mu_{1}-\mu_{2}),$
we have

$\displaystyle c_{1}=$
$\displaystyle\epsilon+\ln{\sqrt{\frac{\det{(\Sigma_{1})}}{\det{(\Sigma_{2})}}}}-\frac{1}{2}(\mu_{1}-\mu_{2})^{T}\Sigma_{2}^{-1}(\mu_{1}-\mu_{2})$
$\displaystyle=$
$\displaystyle\epsilon-\frac{1}{2}\ln{\left((1-\frac{w_{(i)}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}})^{d-1}(\frac{1}{1-\left(P\right)_{i,i}})\right)}$
(by Proposition 9)
$\displaystyle-\frac{1}{2}(x_{\texttt{opt}}-x_{\texttt{opt}}^{\prime})^{T}\frac{r}{{\left\|{w}^{\prime}\right\|}_{2}^{2}}(({B}^{\prime})^{T}{B}^{\prime})(x_{\texttt{opt}}-x_{\texttt{opt}}^{\prime})$
$\displaystyle=$
$\displaystyle\epsilon-\frac{1}{2}\ln{\left((1-\frac{w_{(i)}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}})^{d-1}(\frac{1}{1-\left(P\right)_{i,i}})\right)}$
$\displaystyle-\frac{1}{2}\frac{w_{(i)}v^{T}(B^{T}B)^{-1}}{1-\left(P\right)_{i,i}}\frac{r}{{\left\|{w}^{\prime}\right\|}_{2}^{2}}(({B}^{\prime})^{T}{B}^{\prime})\frac{w_{(i)}(B^{T}B)^{-1}v}{1-\left(P\right)_{i,i}}$
$\displaystyle=$
$\displaystyle\epsilon-\frac{1}{2}\ln{\left((1-\frac{w_{(i)}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}})^{d-1}(\frac{1}{1-\left(P\right)_{i,i}})\right)}$
$\displaystyle-\frac{1}{2}\frac{rw_{(i)}^{2}}{(1-\left(P\right)_{i,i})^{2}}\frac{1}{{\left\|{w}^{\prime}\right\|}_{2}^{2}}v^{T}(B^{T}B)^{-1}(({B}^{\prime})^{T}{B}^{\prime})(B^{T}B)^{-1}v$
$\displaystyle=$
$\displaystyle\epsilon-\frac{1}{2}\ln{\left((1-\frac{w_{(i)}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}})^{d-1}(\frac{1}{1-\left(P\right)_{i,i}})\right)}$
$\displaystyle-\frac{1}{2}\frac{rw_{(i)}^{2}}{(1-\left(P\right)_{i,i})^{2}}\frac{1}{{\left\|{w}^{\prime}\right\|}_{2}^{2}}v^{T}M^{-1}(M-vv^{T})M^{-1}v$
$\displaystyle=$
$\displaystyle\epsilon-\frac{1}{2}\ln{\left((1-\frac{w_{(i)}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}})^{d-1}(\frac{1}{1-\left(P\right)_{i,i}})\right)}$
(by Proposition 8)
$\displaystyle-\frac{1}{2}\frac{rw_{(i)}^{2}}{(1-\left(P\right)_{i,i})^{2}}\frac{1}{{\left\|w\right\|}_{2}^{2}-\frac{w_{(i)}^{2}}{1-\left(P\right)_{i,i}}}v^{T}M^{-1}(M-vv^{T})M^{-1}v$
$\displaystyle=$
$\displaystyle\epsilon-\frac{1}{2}\ln{\left((1-\frac{w_{(i)}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}})^{d-1}(\frac{1}{1-\left(P\right)_{i,i}})\right)}$
$\displaystyle-\frac{1}{2}\frac{rw_{(i)}^{2}}{(1-\left(P\right)_{i,i})^{2}{\left\|w\right\|}_{2}^{2}-(1-\left(P\right)_{i,i})w_{(i)}^{2}}v^{T}M^{-1}(M-vv^{T})M^{-1}v$
$\displaystyle=$
$\displaystyle\epsilon-\frac{1}{2}\ln{\left((1-\frac{w_{(i)}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}})^{d-1}(\frac{1}{1-\left(P\right)_{i,i}})\right)}$
$\displaystyle-\frac{1}{2}\frac{rw_{(i)}^{2}\left(P\right)_{i,i}(1-\left(P\right)_{i,i})}{(1-\left(P\right)_{i,i})^{2}{\left\|w\right\|}_{2}^{2}-(1-\left(P\right)_{i,i})w_{(i)}^{2}}$
$\displaystyle=$
$\displaystyle\epsilon-\frac{1}{2}\ln{\left((1-\frac{w_{(i)}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}})^{d-1}(\frac{1}{1-\left(P\right)_{i,i}})\right)}$
$\displaystyle-\frac{1}{2}\frac{r\left(P\right)_{i,i}w_{(i)}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}-w_{(i)}^{2}}.$

Then, by Lemma 2,
$\delta(\mu_{1},\mu_{2},\Sigma_{1},\Sigma_{2})=\mathbb{E}\left(\max\\{0,1-\exp\left(\frac{1}{2}Z^{T}A_{1}Z+b_{1}^{T}Z+c_{1}\right)\\}\right)$
where $Z\sim\mathcal{N}(\overrightarrow{\mathbf{0}},I_{d-1})$.

Similarly, let $U_{2}A_{2}U_{2}^{T}$ be the SVD of
$I_{d-1}-\Sigma_{2}^{1/2}\Sigma_{1}^{-1}\Sigma_{2}^{1/2}$. we have

$\displaystyle I_{d-1}-\Sigma_{2}^{1/2}\Sigma_{1}^{-1}\Sigma_{2}^{1/2}$
$\displaystyle=$ $\displaystyle
I_{d-1}-\frac{{\left\|{w}^{\prime}\right\|}_{2}}{\sqrt{r}}(({B}^{\prime})^{T}{B}^{\prime})^{-1/2}\frac{r}{{\left\|w\right\|}_{2}^{2}}(B^{T}B)\frac{{\left\|{w}^{\prime}\right\|}_{2}}{\sqrt{r}}(({B}^{\prime})^{T}{B}^{\prime})^{-1/2}$
($M=B^{T}B$, $B^{T}B-({B}^{\prime})^{T}{B}^{\prime}=vv^{T}$) $\displaystyle=$
$\displaystyle
I_{d-1}-\frac{{\left\|{w}^{\prime}\right\|}_{2}^{2}}{{\left\|w\right\|}_{2}^{2}}(M-vv^{T})^{-1/2}M(M-vv^{T})^{-1/2}$
(by Proposition 8) $\displaystyle=$ $\displaystyle
I_{d-1}-\frac{{\left\|w\right\|}_{2}^{2}-\frac{w_{(i)}^{2}}{1-\left(P\right)_{i,i}}}{{\left\|w\right\|}_{2}^{2}}(M-vv^{T})^{-1/2}M(M-vv^{T})^{-1/2}$
$\displaystyle=$ $\displaystyle
I_{d-1}-(1-\frac{w_{(i)}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}})(M-vv^{T})^{-1/2}M(M-vv^{T})^{-1/2}.$

Plug in the expression
$b_{2}=-U_{2}^{T}\Sigma_{2}^{1/2}\Sigma_{1}^{-1}(\mu_{2}-\mu_{1}),$ we have

$\displaystyle b_{2}=$ $\displaystyle-
U_{2}^{T}\Sigma_{2}^{1/2}\Sigma_{1}^{-1}(\mu_{2}-\mu_{1})$ $\displaystyle=$
$\displaystyle-
U_{2}^{T}\frac{{\left\|{w}^{\prime}\right\|}_{2}}{\sqrt{r}}(({B}^{\prime})^{T}{B}^{\prime})^{-1/2}\frac{r}{{\left\|w\right\|}_{2}^{2}}(B^{T}B)(x_{\texttt{opt}}^{\prime}-x_{\texttt{opt}})$
(by Proposition 7) $\displaystyle=$ $\displaystyle-
U_{2}^{T}\frac{\sqrt{r}{\left\|{w}^{\prime}\right\|}_{2}}{{\left\|w\right\|}_{2}^{2}}(({B}^{\prime})^{T}{B}^{\prime})^{-1/2}(B^{T}B)(-\frac{w_{(i)}(B^{T}B)^{-1}v}{1-\left(P\right)_{i,i}})$
$\displaystyle=$ $\displaystyle
U_{2}^{T}\frac{\sqrt{r}w_{(i)}{\left\|{w}^{\prime}\right\|}_{2}}{{\left\|w\right\|}_{2}^{2}(1-\left(P\right)_{i,i})}(({B}^{\prime})^{T}{B}^{\prime})^{-1/2}v$
(by Proposition 8) $\displaystyle=$ $\displaystyle
U_{2}^{T}\frac{\sqrt{r}w_{(i)}\sqrt{{\left\|w\right\|}_{2}^{2}-\frac{w_{(i)}^{2}}{1-\left(P\right)_{i,i}}}}{{\left\|w\right\|}_{2}^{2}(1-\left(P\right)_{i,i})}(M-vv^{T})^{-1/2}v$

Plug in the expression
$c_{2}=\epsilon+\ln{\sqrt{\frac{\det{(\Sigma_{2})}}{\det{(\Sigma_{1})}}}}-\frac{1}{2}(\mu_{2}-\mu_{1})^{T}\Sigma_{1}^{-1}(\mu_{2}-\mu_{1}),$
we have

$\displaystyle
c_{2}=\epsilon+\ln{\sqrt{\frac{\det{(\Sigma_{2})}}{\det{(\Sigma_{1})}}}}-\frac{1}{2}(\mu_{2}-\mu_{1})^{T}\Sigma_{1}^{-1}(\mu_{2}-\mu_{1})$
$\displaystyle=\epsilon+\frac{1}{2}\ln{\left((1-\frac{w_{(i)}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}})^{d-1}(\frac{1}{1-\left(P\right)_{i,i}})\right)}$
(by Proposition 9)
$\displaystyle-\frac{1}{2}(x_{\texttt{opt}}^{\prime}-x_{\texttt{opt}})^{T}\frac{r}{{\left\|w\right\|}_{2}^{2}}(B^{T}B)(x_{\texttt{opt}}^{\prime}-x_{\texttt{opt}})$
$\displaystyle=\epsilon+\frac{1}{2}\ln{\left((1-\frac{w_{(i)}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}})^{d-1}(\frac{1}{1-\left(P\right)_{i,i}})\right)}$
(by Proposition 7)
$\displaystyle-\frac{1}{2}(\frac{w_{(i)}v^{T}(B^{T}B)^{-1}}{1-\left(P\right)_{i,i}})\frac{r}{{\left\|w\right\|}_{2}^{2}}(B^{T}B)(\frac{w_{(i)}(B^{T}B)^{-1}v}{1-\left(P\right)_{i,i}})$
$\displaystyle=\epsilon+\frac{1}{2}\ln{\left((1-\frac{w_{(i)}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}})^{d-1}(\frac{1}{1-\left(P\right)_{i,i}})\right)}$
$\displaystyle-\frac{1}{2}\frac{rw_{(i)}^{2}}{{\left\|w\right\|}_{2}^{2}(1-\left(P\right)_{i,i})^{2}}v^{T}(B^{T}B)^{-1}v$
$\displaystyle=\epsilon+\frac{1}{2}\ln{((1-\frac{w_{(i)}^{2}}{(1-\left(P\right)_{i,i}){\left\|w\right\|}_{2}^{2}})^{d-1}(\frac{1}{1-\left(P\right)_{i,i}}))}-\frac{1}{2}\frac{rw_{(i)}^{2}\left(P\right)_{i,i}}{{\left\|w\right\|}_{2}^{2}(1-\left(P\right)_{i,i})^{2}}$

Then, by Lemma 2,
$\delta(\mu_{2},\mu_{1},\Sigma_{2},\Sigma_{1})=\mathbb{E}\left(\max\\{0,1-\exp\left(\frac{1}{2}Z^{T}A_{2}Z+b_{2}^{T}Z+c_{2}\right)\\}\right)$
where $Z\sim\mathcal{N}(\overrightarrow{\mathbf{0}},I_{d-1})$. ∎

###  B.4. Sec 3.4 Cont’d: Privacy of Gaussian LS

In this section, we prove Proposition 4 and Proposition 5.

###### Proof of Proposition 4.

We first state and prove the useful Proposition 10.

######  Proposition 0.

Let $b\in\mathsf{R}^{d}$ be a $d$-dimensional vector, $c\in\mathsf{R}$ be a
real number, and $Z\sim\mathcal{N}(\overrightarrow{\mathbf{0}},I_{d})$ be a
standard $d$-dimensional multivariate normal random variable. Then

$\displaystyle\mathbb{E}\left(\max\\{0,1-\exp\left(b^{T}Z+c\right)\\}\right)=$
$\displaystyle\frac{1}{2}+\frac{1}{2}\texttt{erf}\left(-\frac{c}{{\left\|b\right\|}_{2}\sqrt{2}}\right)-\exp\left(c+\frac{{\left\|b\right\|}_{2}^{2}}{2}\right)(\frac{1}{2}+\frac{1}{2}\texttt{erf}\left(-\frac{c}{{\left\|b\right\|}_{2}\sqrt{2}}-\frac{{\left\|b\right\|}_{2}}{\sqrt{2}}\right)).$

###### Proof.

$\displaystyle\mathbb{E}\left(\max\\{0,1-\exp\left(b^{T}Z+c\right)\\}\right)$
($b^{T}Z\sim\mathcal{N}(0,{\left\|b\right\|}_{2}^{2});X\sim\mathcal{N}(0,1)$)
$\displaystyle=$
$\displaystyle\mathbb{E}\left(\max\\{0,1-\exp\left({\left\|b\right\|}_{2}X+c\right)\\}\right)$
$\displaystyle=$ $\displaystyle\int\limits_{{\left\|b\right\|}_{2}x+c\leq
0}(1-\exp\left({\left\|b\right\|}_{2}x+c\right))\Pr[X=x]\mathrm{d}x$
$\displaystyle=$ $\displaystyle\int\limits_{{\left\|b\right\|}_{2}x+c\leq
0}\Pr[X=x]\mathrm{d}x-\int\limits_{{\left\|b\right\|}_{2}x+c\leq
0}\exp\left({\left\|b\right\|}_{2}x+c\right)\Pr[X=x]\mathrm{d}x$
$\displaystyle=$ $\displaystyle\Pr[{\left\|b\right\|}_{2}X+c\leq
0]-\int\limits_{{\left\|b\right\|}_{2}x+c\leq
0}\exp\left({\left\|b\right\|}_{2}x+c\right)\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{1}{2}x^{2}\right)\mathrm{d}x$
$\displaystyle=$
$\displaystyle\Pr[X\leq-\frac{c}{{\left\|b\right\|}_{2}}]-\exp\left(c\right)\int\limits_{{\left\|b\right\|}_{2}x+c\leq
0}\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{1}{2}x^{2}+{\left\|b\right\|}_{2}x\right)\mathrm{d}x$
$\displaystyle=$
$\displaystyle\Pr[X\leq-\frac{c}{{\left\|b\right\|}_{2}}]-\exp\left(c\right)\int\limits_{{\left\|b\right\|}_{2}x+c\leq
0}\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{1}{2}(x-{\left\|b\right\|}_{2})^{2}\right)\exp\left(\frac{{\left\|b\right\|}_{2}^{2}}{2}\right)\mathrm{d}x$
$\displaystyle=$
$\displaystyle\Pr[X\leq-\frac{c}{{\left\|b\right\|}_{2}}]-\exp\left(c+\frac{{\left\|b\right\|}_{2}^{2}}{2}\right)\int\limits_{{\left\|b\right\|}_{2}x+c\leq
0}\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{1}{2}(x-{\left\|b\right\|}_{2})^{2}\right)\mathrm{d}x$
($y=x-{\left\|b\right\|}_{2}$) $\displaystyle=$
$\displaystyle\Pr[X\leq-\frac{c}{{\left\|b\right\|}_{2}}]-\exp\left(c+\frac{{\left\|b\right\|}_{2}^{2}}{2}\right)\int\limits_{{\left\|b\right\|}_{2}y+{\left\|b\right\|}_{2}^{2}+c\leq
0}\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{1}{2}y^{2}\right)\mathrm{d}y$
$\displaystyle=$
$\displaystyle\Pr[X\leq-\frac{c}{{\left\|b\right\|}_{2}}]-\exp\left(c+\frac{{\left\|b\right\|}_{2}^{2}}{2}\right)\int\limits_{{\left\|b\right\|}_{2}y+{\left\|b\right\|}_{2}^{2}+c\leq
0}\Pr[X=y]\mathrm{d}y$ $\displaystyle=$
$\displaystyle\Pr[X\leq-\frac{c}{{\left\|b\right\|}_{2}}]-\exp\left(c+\frac{{\left\|b\right\|}_{2}^{2}}{2}\right)\Pr[{\left\|b\right\|}_{2}X+{\left\|b\right\|}_{2}^{2}+c\leq
0]$ $\displaystyle=$
$\displaystyle\Pr[X\leq-\frac{c}{{\left\|b\right\|}_{2}}]-\exp\left(c+\frac{{\left\|b\right\|}_{2}^{2}}{2}\right)\Pr[X\leq-\frac{c}{{\left\|b\right\|}_{2}}-{\left\|b\right\|}_{2}]$
$\displaystyle\frac{1}{2}+\frac{1}{2}\texttt{erf}\left(-\frac{c}{{\left\|b\right\|}_{2}\sqrt{2}}\right)-\exp\left(c+\frac{{\left\|b\right\|}_{2}^{2}}{2}\right)(\frac{1}{2}+\frac{1}{2}\texttt{erf}\left(-\frac{c}{{\left\|b\right\|}_{2}\sqrt{2}}-\frac{{\left\|b\right\|}_{2}}{\sqrt{2}}\right)).$

∎

Now we have proven the Proposition above, we continue the proof for
Proposition 4.

Applying Lemma 2, we have

$\displaystyle\delta(x_{\texttt{opt}},x_{\texttt{opt}}^{\prime},\sigma^{2}I_{d},\sigma^{2}I_{d})=\mathbb{E}\left(\max\\{0,1-\exp\left(b_{1}^{T}Z+c_{1}\right)\\}\right),$

where $b_{1}=\frac{1}{\sigma}(x_{\texttt{opt}}-x_{\texttt{opt}}^{\prime})$ and
$c_{1}=\epsilon-\frac{1}{2\sigma^{2}}{\left\|x_{\texttt{opt}}-x_{\texttt{opt}}^{\prime}\right\|}_{2}^{2}$.

Similarly, we have

$\displaystyle\delta(x_{\texttt{opt}}^{\prime},x_{\texttt{opt}},\sigma^{2}I_{d},\sigma^{2}I_{d})=\mathbb{E}\left(\max\\{0,1-\exp\left(-b_{1}^{T}Z+c_{1}\right)\\}\right)=\delta_{1},$

which is because $-b_{1}^{T}Z$ has the same distribution of $b_{1}^{T}Z$.

By Proposition 10, we could further simply and see

(13) $\displaystyle\delta=$
$\displaystyle\mathbb{E}\left(\max\\{0,1-\exp\left(-b_{1}^{T}Z+c_{1}\right)\\}\right)$
(14) $\displaystyle=$
$\displaystyle\frac{1}{2}+\frac{1}{2}\texttt{erf}\left(-\frac{c_{1}}{{\left\|b_{1}\right\|}_{2}\sqrt{2}}\right)-\exp\left(c_{1}+\frac{{\left\|b_{1}\right\|}_{2}^{2}}{2}\right)(\frac{1}{2}+\frac{1}{2}\texttt{erf}\left(-\frac{c_{1}}{{\left\|b_{1}\right\|}_{2}\sqrt{2}}-\frac{{\left\|b_{1}\right\|}_{2}}{\sqrt{2}}\right))$
(15) $\displaystyle=$
$\displaystyle\frac{1}{2}+\frac{1}{2}\texttt{erf}\left(-\frac{c_{1}}{{\left\|b_{1}\right\|}_{2}\sqrt{2}}\right)-\exp\left(\epsilon\right)(\frac{1}{2}+\frac{1}{2}\texttt{erf}\left(-\frac{c_{1}}{{\left\|b_{1}\right\|}_{2}\sqrt{2}}-\frac{{\left\|b_{1}\right\|}_{2}}{\sqrt{2}}\right))$
($c={\left\|b_{1}\right\|}_{2},c_{1}=\epsilon-\frac{c^{2}}{2}$)
$\displaystyle=$
$\displaystyle\frac{1}{2}+\frac{1}{2}\texttt{erf}\left(-\frac{\epsilon-\frac{c^{2}}{2}}{c\sqrt{2}}\right)-\exp\left(\epsilon\right)(\frac{1}{2}+\frac{1}{2}\texttt{erf}\left(-\frac{\epsilon-\frac{c^{2}}{2}}{c\sqrt{2}}-\frac{c}{\sqrt{2}}\right))$
(16) $\displaystyle=$
$\displaystyle\frac{1}{2}+\frac{1}{2}\texttt{erf}\left(-\frac{\epsilon}{\sqrt{2}c}+\frac{c}{\sqrt{8}}\right)-\exp\left(\epsilon\right)(\frac{1}{2}+\frac{1}{2}\texttt{erf}\left(-\frac{\epsilon}{\sqrt{2}c}-\frac{c}{\sqrt{8}}\right))$
(17) $\displaystyle=$
$\displaystyle\frac{1-\exp\left(\epsilon\right)}{2}+\frac{1}{2}(\texttt{erf}\left(-\frac{\epsilon}{\sqrt{2}c}+\frac{c}{\sqrt{8}}\right)-\exp\left(\epsilon\right)\texttt{erf}\left(-\frac{\epsilon}{\sqrt{2}c}-\frac{c}{\sqrt{8}}\right)),$

where
$c=\frac{{\left|w_{(i)}\right|}}{{\left|\sigma\right|}}\frac{{\left\|(B^{T}B)^{-1}v\right\|}_{2}}{(1-\left(P\right)_{i,i})},$
by Proposition 7.  ∎

###### Proof of Proposition 5.

The proof is simply plugging
$\sigma^{2}=2\ln{(1.25/\delta)}\frac{s^{2}}{\epsilon^{2}}$ into the statement
we obtained from Proposition 4. ∎

###  B.5. Sec 3.4 Cont’d: Privacy of RP LS

In this section, we include the proof of Lemma 6 and Lemma 7. We also discuss
how to simplify the expressions in these lemmas.

###### Proof of Lemma 6.

We first recall the Lemma 11, which says that a linear transformation of a
multivariate normal random vector also has a multivariate normal distribution.

######  Lemma 0 (Affine transformation).

Let $A\in\mathsf{R}^{n\times d}$ be a $n\times d$ matrix and
$X\sim\mathcal{N}(\mu,\Sigma)$ be a $d$-dimensions multivariate normal random
variables with $\mu\in\mathsf{R}^{d}$ and $\Sigma\in\mathsf{R}^{d\times d}$.
Then the multivariate $Y=AX$ is distributed as

$Y\sim\mathcal{N}(A\mu,A\Sigma A^{T}).$

Since we know $D^{T}g\sim\mathcal{N}(\overrightarrow{\mathbf{0}},D^{T}D)$ and
$D_{i}^{T}g\sim\mathcal{N}(\overrightarrow{\mathbf{0}},D_{i}^{T}D_{i})$ where
$D_{i}$ is the neighbor of $D$ zeroing the $i$-th row, by pluging in these two
multi-variate Gaussian into Lemma 2 we complete the proof. ∎

###### Proof of Lemma 7.

There exists an isomorphism between the probability space with the matrix-
valued distribution $D^{T}G$ and the probability space with the vector-valued
distribution $(D^{T}g_{1},\cdots,D^{T}g_{r})$ where $g_{i}$ is the $i$-th row
of $G.$ Since we know
$(D^{T}g_{1},\cdots,D^{T}g_{r})\sim\mathcal{N}(\overrightarrow{\mathbf{0}},\Sigma)$,
where $\Sigma$ is a $rd\times rd$ block diagonal matrix with blocks $D^{T}D,$
and
$(D_{i}^{T}g_{1},\cdots,D_{i}^{T}g_{r})\sim\mathcal{N}(\overrightarrow{\mathbf{0}},\Sigma_{i})$,
where $D_{i}$ is the neighbor of $D$ zeroing the $i$-th row and $\Sigma_{i}$
is a $rd\times rd$ block diagonal matrix with blocks $D_{i}^{T}D_{i},$ by
pluging in these two multi-variate Gaussian into Lemma 2 we complete the
proof. ∎

#### Simplifying Lemma 6 and Lemma 7

It is possible to simplify the above two lemmas. The derivation follows the
same steps as the proof of Proposition 4. For Lemma 6, computing the privacy
parameter $\delta$ given $\epsilon$ and database $D$ essentially equals to
computing
$\mathbb{E}\left(\max\\{0,1-\exp\left(c_{1}(a^{T}Z)^{2}+c\right)\\}\right)$
for some vector $a$, real number $c$ and integer $c_{1}\in\\{+1,-1\\}$, with
these parameters being determined by $D$ and $\epsilon$. If $c_{1}=-1$ or
$c_{1}=1$ and ${\left\|a\right\|}_{2}^{2}<\frac{1}{2}$,
$\mathbb{E}\left(\max\\{0,1-\exp\left(c_{1}(a^{T}Z)^{2}+c\right)\\}\right)$
can be converted to error function $\texttt{erf}\left(\cdot\right)$; if
$c_{1}=1$ and ${\left\|a\right\|}_{2}^{2}=\frac{1}{2}$,
$\mathbb{E}\left(\max\\{0,1-\exp\left(c_{1}(a^{T}Z)^{2}+c\right)\\}\right)$ is
just a constant; otherwise
$\mathbb{E}\left(\max\\{0,1-\exp\left(c_{1}(a^{T}Z)^{2}+c\right)\\}\right)$
can be converted to imaginary error function
$\texttt{erfi}\left(\cdot\right)$. These steps also apply to Lemma 7.

##  Appendix C Section 4 Cont’d: Impossibility of Private OLS without
Restricting Input

In this section, we include the proof of Lemma 3 and Lemma 5.

###### Proof of Lemma 3.

We prove the statement by contradiction. We first assume that there exists an
$(\epsilon,\delta)$-DP mechanism $\mathcal{M}$ for some
$\epsilon\in\mathsf{R}_{\geq 0},\delta\in[0,\frac{1}{2}]$ and assume that
there exists $b>0$ such that for any $D,$
$\mathbb{E}\left((\mathcal{M}(D)-f(D))^{2}\right)\leq b$. Then we will show
there is a contradiction.

We first show in Claim 1 that if the mean square error is bounded, then
$\mathcal{M}(D)$ is concentrated around $f(D)$.

######  Claim 1.

Let $b>0$ and $\mathbb{E}\left((\mathcal{M}(D)-f(D))^{2}\right)\leq b.$ Then
for any $k>0,$

$\displaystyle\Pr[{\left|\mathcal{M}(D)-f(D)\right|}\geq(k+1)\sqrt{b}]\leq\frac{1}{k^{2}}.$

###### Proof.

First, if the condition in the claim holds, we know the expectation of
$\mathcal{M}(D)$ is around $f(D)$:

$\displaystyle({\left|\mathbb{E}\left(\mathcal{M}(D)\right)-f(D)\right|})^{2}=(\mathbb{E}\left(\mathcal{M}(D)\right)-f(D))^{2}$
$\displaystyle=$
$\displaystyle\mathbb{E}\left(\mathcal{M}(D)\right)^{2}+f(D)^{2}-2f(D)\mathbb{E}\left(\mathcal{M}(D)\right)$
(By Jensen’s Inequality) $\displaystyle\leq$
$\displaystyle\mathbb{E}\left(\mathcal{M}(D)^{2}\right)+f(D)^{2}-2f(D)\mathbb{E}\left(\mathcal{M}(D)\right)$
(By Expectation’s Linearity) $\displaystyle=$
$\displaystyle\mathbb{E}\left(\mathcal{M}(D)^{2}-2f(D)\mathcal{M}(D)+f(D)^{2}\right)$
$\displaystyle=$
$\displaystyle\mathbb{E}\left((\mathcal{M}(D)-f(D))^{2}\right)\leq b,$

Thus, we have
${\left|\mathbb{E}\left(\mathcal{M}(D)\right)-f(D)\right|}\leq\sqrt{b}$.

Then, we know the variance of $\mathcal{M}(D)$ is bounded:

$\displaystyle
Var\left(\mathcal{M}(D)\right)=\mathbb{E}\left(\mathcal{M}(D)^{2}\right)-\mathbb{E}\left(\mathcal{M}(D)\right)^{2}$
$\displaystyle=$
$\displaystyle\mathbb{E}\left((\mathcal{M}(D)-f(D))^{2}\right)-({\left|\mathbb{E}\left(\mathcal{M}(D)\right)-f(D)\right|})^{2}$
$\displaystyle\leq$
$\displaystyle\mathbb{E}\left((\mathcal{M}(D)-f(D))^{2}\right)\leq b,$

Thus, we have $Var\left(\mathcal{M}(D)\right)\leq b.$

Lastly, for any $k>0,$

$\displaystyle\Pr[{\left|\mathcal{M}(D)-f(D)\right|}\geq(k+1)\sqrt{b}]$ (Since
${\left|\mathbb{E}\left(\mathcal{M}(D)\right)-f(D)\right|}\leq\sqrt{b}$)
$\displaystyle=$
$\displaystyle\Pr[{\left|\mathcal{M}(D)-\mathbb{E}\left(\mathcal{M}(D)\right)\right|}\geq
k\sqrt{b}]$ (Since $Var\left(\mathcal{M}(D)\right)\leq b$) $\displaystyle\leq$
$\displaystyle\Pr[{\left|\mathcal{M}(D)-\mathbb{E}\left(\mathcal{M}(D)\right)\right|}\geq
k\sqrt{Var\left(\mathcal{M}(D)\right)}]$ (by Chebyshev’s Inequality)
$\displaystyle\leq$ $\displaystyle\frac{1}{k^{2}}.$

∎

We proceed to prove Lemma 3, by showing that for every $b$, there exists a
dataset $D$ such that its mean square error cannot be bounded by $b.$ Let
constant $c=(k+1)\sqrt{b},$ where $k=\sqrt{\frac{1}{\frac{3}{4}-\delta}}$. Let
$D$ be a dataset which has a neighbor $D^{\prime}$ such that
${\left|f(D^{\prime})-f(D)\right|}>\sqrt{4be^{\epsilon}}+c.$ We know the
dataset $D$ must exist, since $f$ has unbounded sensitivity. We compute the
mean square error for $D$:

$\displaystyle\mathbb{E}\left((\mathcal{M}(D)-f(D))^{2}\right)$
$\displaystyle=$
$\displaystyle\int\limits_{-\infty}^{+\infty}(z-f(D))^{2}\Pr[\mathcal{M}(D)=z]\mathrm{d}z$
$\displaystyle\geq$
$\displaystyle\int\limits_{f(D^{\prime})-c}^{f(D^{\prime})+c}(z-f(D))^{2}\Pr[\mathcal{M}(D)=z]\mathrm{d}z$
$\displaystyle\geq$
$\displaystyle({\left|f(D^{\prime})-f(D)\right|}-c)^{2}\Pr[\mathcal{M}(D)\in[f(D^{\prime})-c,f(D^{\prime})+c]]$
($\mathcal{M}$ is $(\epsilon,\delta)$-DP) $\displaystyle\geq$
$\displaystyle({\left|f(D^{\prime})-f(D)\right|}-c)^{2}(e^{-\epsilon}\Pr[\mathcal{M}(D^{\prime})\in[f(D^{\prime})-c,f(D^{\prime})+c]]-e^{-\epsilon}\delta)$
(Using Claim 1 and plug in $c$’s value) $\displaystyle\geq$
$\displaystyle({\left|f(D^{\prime})-f(D)\right|}-c)^{2}\frac{e^{-\epsilon}}{4}$
(Plug in ${\left|f(D^{\prime})-f(D)\right|}>\sqrt{4be^{\epsilon}}+c$)
$\displaystyle>$ $\displaystyle b,$

which contradicts our initial assumption that the mean square error for any
dataset is at most $b$. ∎

###### Proof of Lemma 5.

Let $n-1$ be the number of rows of $D$. We append a zero-valued row to $D,$
which doesn’t change the OLS query result over $D.$ Let us henceforth refer to
this new $n\times d$ matrix using the same name, $D=[B,b]$. Now we construct
$D^{\prime}=[B^{\prime},b^{\prime}]$ from $D$ by replacing the zero-valued row
we just added. For $B^{\prime}$, let us call the replaced row of
${B}^{\prime}$ as $v^{T}$ (the transpose of column vector $v$), and for
$b^{\prime}$, let us call the replaced single entry as $c$. The following
claim describes the difference between $f(D)$ and $f(D^{\prime})$.

######  Claim 2.

Let us call the first row of ${B}^{\prime}$ as $v^{T}$ and the first entry of
${b}^{\prime}$ as $c.$ Then

$\displaystyle
f(D^{\prime})-f(D)=\frac{c(B^{T}B)^{-1}v-(B^{T}B)^{-1}vv^{T}f(D)}{1+v^{T}(B^{T}B)^{-1}v}.$

###### Proof.

$\displaystyle f(D^{\prime})-f(D)$ (by OLS query’s definition)
$\displaystyle=$ $\displaystyle({B}^{\prime T}{B}^{\prime})^{-1}{B}^{\prime
T}{b}^{\prime}-f(D)$ $\displaystyle=$
$\displaystyle(B^{T}B+vv^{T})^{-1}(B^{T}b+cv)-f(D)$ (by Woodbury matrix
identity) $\displaystyle=$
$\displaystyle\left((B^{T}B)^{-1}-\frac{(B^{T}B)^{-1}vv^{T}(B^{T}B)^{-1}}{1+v^{T}(B^{T}B)^{-1}v}\right)(B^{T}b+cv)-f(D)$
$\displaystyle=$ $\displaystyle
c(B^{T}B)^{-1}v-\frac{(B^{T}B)^{-1}vv^{T}f(D)}{1+v^{T}(B^{T}B)^{-1}v}-\frac{c(B^{T}B)^{-1}vv^{T}(B^{T}B)^{-1}v}{1+v^{T}(B^{T}B)^{-1}v}$
$\displaystyle=$
$\displaystyle\frac{c(B^{T}B)^{-1}v-(B^{T}B)^{-1}vv^{T}f(D)}{1+v^{T}(B^{T}B)^{-1}v}.$

∎

Now we will choose the vector $v$ and constant $c$ such that
$(f(D^{\prime})-f(D))_{(1)}>a$ (the first component of $f(D^{\prime})-f(D)$),
for any $a>0$. Then, it suffices to prove the statement. Without loss of
generality, assume $\left((B^{T}B)^{-1})\right)_{1,1}$ is not zero (since we
know there is at least a non-zero entry in the first row of $(B^{T}B)^{-1})$).
Let $v^{T}=(1,0,\cdots,0)$ and
$c>(f(D))_{(1)}+a+\frac{a}{\left((B^{T}B)^{-1})\right)_{1,1}}$. By plugging
into the Claim 2, we can see that $(f(D^{\prime})-f(D))_{(1)}>a,$ hence
completes the proof. ∎

##  Appendix D Proof of RP LS Algorithm’s DP Privacy

###  D.1. Expectation of exponential of Gaussian

######  Proposition 0 (Proof in Appendix D.1).

Let $a\in\mathsf{R}^{d}\setminus\overrightarrow{\mathbf{0}}$ be a
$d$-dimensional vector, $c\in\mathsf{R}$ be a real number. Let
$Z\sim\mathcal{N}(\overrightarrow{\mathbf{0}},I_{d})$ be a standard
$d$-dimensional multivariate normal random variable. Then

$\displaystyle\mathbb{E}\left(\max\\{0,1-\exp\left(-(a^{T}Z)^{2}+c\right)\\}\right)=1-\frac{\exp\left(c\right)}{\sqrt{2{\left\|a\right\|}_{2}^{2}+1}}+\frac{\exp\left(c\right)}{\sqrt{2{\left\|a\right\|}_{2}^{2}+1}}\texttt{erf}\left(\frac{\sqrt{c(2{\left\|a\right\|}_{2}^{2}+1)/2}}{{\left\|a\right\|}_{2}}\right)-\texttt{erf}\left(\frac{\sqrt{c/2}}{{\left\|a\right\|}_{2}}\right).$

###### Proof.

$\displaystyle\mathbb{E}\left(\max\\{0,1-\exp\left(-(a^{T}Z)^{2}+c\right)\\}\right)$
($X\sim\mathcal{N}(0,1)$) $\displaystyle=$
$\displaystyle\mathbb{E}\left(\max\\{0,1-\exp\left(-{\left\|a\right\|}_{2}^{2}X^{2}+c\right)\\}\right)$
$\displaystyle=$
$\displaystyle\int\limits_{-{\left\|a\right\|}_{2}^{2}x^{2}+c\leq
0}(1-\exp\left(-{\left\|a\right\|}_{2}^{2}x^{2}+c\right))\Pr[X=x]\mathrm{d}x$
$\displaystyle=$
$\displaystyle\int\limits_{-{\left\|a\right\|}_{2}^{2}x^{2}+c\leq
0}\Pr[X=x]\mathrm{d}x-\int\limits_{-{\left\|a\right\|}_{2}^{2}x^{2}+c\leq
0}\exp\left(-{\left\|a\right\|}_{2}^{2}x^{2}+c\right)\Pr[X=x]\mathrm{d}x$
$\displaystyle=$ $\displaystyle
2\Pr[X\geq\frac{\sqrt{c}}{{\left\|a\right\|}_{2}}]-\int\limits_{-{\left\|a\right\|}_{2}^{2}x^{2}+c\leq
0}\exp\left(-{\left\|a\right\|}_{2}^{2}x^{2}+c\right)\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{1}{2}x^{2}\right)\mathrm{d}x$
($y=\sqrt{2{\left\|a\right\|}_{2}^{2}+1}x$) $\displaystyle=$ $\displaystyle
2\Pr[X\geq\frac{\sqrt{c}}{{\left\|a\right\|}_{2}}]-\frac{\exp\left(c\right)}{\sqrt{2{\left\|a\right\|}_{2}^{2}+1}}\int\limits_{-\frac{{\left\|a\right\|}_{2}^{2}}{2{\left\|a\right\|}_{2}^{2}+1}y^{2}+c\leq
0}\frac{1}{\sqrt{{2\pi}}}\exp\left(-\frac{1}{2}y^{2}\right)\mathrm{d}y$
$\displaystyle=$ $\displaystyle
2\Pr[X\geq\frac{\sqrt{c}}{{\left\|a\right\|}_{2}}]-\frac{\exp\left(c\right)}{\sqrt{2{\left\|a\right\|}_{2}^{2}+1}}\int\limits_{-\frac{{\left\|a\right\|}_{2}^{2}}{2{\left\|a\right\|}_{2}^{2}+1}y^{2}+c\leq
0}\Pr[X=y]\mathrm{d}y$ $\displaystyle=$ $\displaystyle
2\Pr[X\geq\frac{\sqrt{c}}{{\left\|a\right\|}_{2}}]-\frac{\exp\left(c\right)}{\sqrt{2{\left\|a\right\|}_{2}^{2}+1}}\Pr[X^{2}\geq\frac{c(2{\left\|a\right\|}_{2}^{2}+1)}{{\left\|a\right\|}_{2}^{2}}]$
$\displaystyle=$ $\displaystyle
1-\texttt{erf}\left(\frac{\sqrt{c/2}}{{\left\|a\right\|}_{2}}\right)-\frac{\exp\left(c\right)}{\sqrt{2{\left\|a\right\|}_{2}^{2}+1}}(1-\texttt{erf}\left(\frac{\sqrt{c(2{\left\|a\right\|}_{2}^{2}+1)/2}}{{\left\|a\right\|}_{2}}\right))$
$\displaystyle=$ $\displaystyle
1-\frac{\exp\left(c\right)}{\sqrt{2{\left\|a\right\|}_{2}^{2}+1}}+\frac{\exp\left(c\right)}{\sqrt{2{\left\|a\right\|}_{2}^{2}+1}}\texttt{erf}\left(\frac{\sqrt{c(2{\left\|a\right\|}_{2}^{2}+1)/2}}{{\left\|a\right\|}_{2}}\right)-\texttt{erf}\left(\frac{\sqrt{c/2}}{{\left\|a\right\|}_{2}}\right).$

∎

######  Proposition 0.

Let $a\in\mathsf{R}^{d}$ be a $d$-dimensional vector and
${\left\|a\right\|}_{2}>\frac{\sqrt{2}}{2}$, $c<0$. Let
$Z\sim\mathcal{N}(\overrightarrow{\mathbf{0}},I_{d})$ be a standard
$d$-dimensional multivariate normal random variable. Then

$\displaystyle\mathbb{E}\left(\max\\{0,1-\exp\left((a^{T}Z)^{2}+c\right)\\}\right)=\texttt{erf}\left(\frac{\sqrt{-c/2}}{{\left\|a\right\|}_{2}}\right)-\frac{\exp\left(c\right)}{\sqrt{2{\left\|a\right\|}_{2}^{2}-1}}\texttt{erfi}\left(\frac{\sqrt{(\frac{1}{2}-{\left\|a\right\|}_{2}^{2})c}}{{\left\|a\right\|}_{2}}\right),$

where $\texttt{erfi}\left(\cdot\right)$ is the imaginary error function.

###### Proof.

$\displaystyle\mathbb{E}\left(\max\\{0,1-\exp\left((a^{T}Z)^{2}+c\right)\\}\right)$
($X\sim\mathcal{N}(0,1)$) $\displaystyle=$
$\displaystyle\mathbb{E}\left(\max\\{0,1-\exp\left({\left\|a\right\|}_{2}^{2}X^{2}+c\right)\\}\right)$
$\displaystyle=$
$\displaystyle\int\limits_{{\left\|a\right\|}_{2}^{2}x^{2}+c\leq
0}(1-\exp\left({\left\|a\right\|}_{2}^{2}x^{2}+c\right))\Pr[X=x]\mathrm{d}x$
$\displaystyle=$
$\displaystyle\int\limits_{{\left\|a\right\|}_{2}^{2}x^{2}+c\leq
0}\Pr[X=x]\mathrm{d}x-\int\limits_{{\left\|a\right\|}_{2}^{2}x^{2}+c\leq
0}\exp\left({\left\|a\right\|}_{2}^{2}x^{2}+c\right)\Pr[X=x]\mathrm{d}x$
$\displaystyle=$
$\displaystyle\Pr[-\frac{\sqrt{-c}}{{\left\|a\right\|}_{2}}\leq
X\leq\frac{\sqrt{-c}}{{\left\|a\right\|}_{2}}]-\int\limits_{{\left\|a\right\|}_{2}^{2}x^{2}+c\leq
0}\exp\left({\left\|a\right\|}_{2}^{2}x^{2}+c\right)\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{1}{2}x^{2}\right)\mathrm{d}x$
(let $({\left\|a\right\|}_{2}^{2}-\frac{1}{2})x^{2}=y^{2}$) $\displaystyle=$
$\displaystyle\Pr[-\frac{\sqrt{-c}}{{\left\|a\right\|}_{2}}\leq
X\leq\frac{\sqrt{-c}}{{\left\|a\right\|}_{2}}]-\frac{\exp\left(c\right)}{\sqrt{2\pi}}\frac{1}{\sqrt{{\left\|a\right\|}_{2}^{2}-\frac{1}{2}}}\int\limits_{\frac{{\left\|a\right\|}_{2}^{2}y^{2}}{{\left\|a\right\|}_{2}^{2}-\frac{1}{2}}+c\leq
0}\exp\left(y^{2}\right)\mathrm{d}y$ $\displaystyle=$
$\displaystyle\Pr[-\frac{\sqrt{-c}}{{\left\|a\right\|}_{2}}\leq
X\leq\frac{\sqrt{-c}}{{\left\|a\right\|}_{2}}]-\frac{\exp\left(c\right)}{\sqrt{2}}\frac{1}{\sqrt{{\left\|a\right\|}_{2}^{2}-\frac{1}{2}}}\frac{2}{\sqrt{\pi}}\int_{0}^{\frac{\sqrt{(\frac{1}{2}-{\left\|a\right\|}_{2}^{2})c}}{{\left\|a\right\|}_{2}}}\exp\left(y^{2}\right)\mathrm{d}y$
$\displaystyle=$
$\displaystyle\Pr[-\frac{\sqrt{-c}}{{\left\|a\right\|}_{2}}\leq
X\leq\frac{\sqrt{-c}}{{\left\|a\right\|}_{2}}]-\frac{\exp\left(c\right)}{\sqrt{2}}\frac{1}{\sqrt{{\left\|a\right\|}_{2}^{2}-\frac{1}{2}}}\texttt{erfi}\left(\frac{\sqrt{(\frac{1}{2}-{\left\|a\right\|}_{2}^{2})c}}{{\left\|a\right\|}_{2}}\right)$
$\displaystyle=$
$\displaystyle\texttt{erf}\left(\frac{\sqrt{-c/2}}{{\left\|a\right\|}_{2}}\right)-\frac{\exp\left(c\right)}{\sqrt{2{\left\|a\right\|}_{2}^{2}-1}}\texttt{erfi}\left(\frac{\sqrt{(\frac{1}{2}-{\left\|a\right\|}_{2}^{2})c}}{{\left\|a\right\|}_{2}}\right).$

∎

######  Proposition 0.

Let $a\in\mathsf{R}^{d}$ be a $d$-dimensional vector and
$0<{\left\|a\right\|}_{2}<\frac{\sqrt{2}}{2}$, $c<0$. Let
$Z\sim\mathcal{N}(\overrightarrow{\mathbf{0}},I_{d})$ be a standard
$d$-dimensional multivariate normal random variable. Then

$\displaystyle\mathbb{E}\left(\max\\{0,1-\exp\left((a^{T}Z)^{2}+c\right)\\}\right)=\texttt{erf}\left(\frac{\sqrt{-c/2}}{{\left\|a\right\|}_{2}}\right)-\frac{\exp\left(c\right)}{\sqrt{1-2{\left\|a\right\|}_{2}^{2}}}\texttt{erf}\left(\frac{\sqrt{(2{\left\|a\right\|}_{2}^{2}-1)c/2}}{{\left\|a\right\|}_{2}}\right).$

###### Proof.

$\displaystyle\mathbb{E}\left(\max\\{0,1-\exp\left((a^{T}Z)^{2}+c\right)\\}\right)$
($X\sim\mathcal{N}(0,1)$) $\displaystyle=$
$\displaystyle\mathbb{E}\left(\max\\{0,1-\exp\left({\left\|a\right\|}_{2}^{2}X^{2}+c\right)\\}\right)$
$\displaystyle=$
$\displaystyle\int\limits_{{\left\|a\right\|}_{2}^{2}x^{2}+c\leq
0}(1-\exp\left({\left\|a\right\|}_{2}^{2}x^{2}+c\right))\Pr[X=x]\mathrm{d}x$
$\displaystyle=$
$\displaystyle\int\limits_{{\left\|a\right\|}_{2}^{2}x^{2}+c\leq
0}\Pr[X=x]\mathrm{d}x-\int\limits_{{\left\|a\right\|}_{2}^{2}x^{2}+c\leq
0}\exp\left({\left\|a\right\|}_{2}^{2}x^{2}+c\right)\Pr[X=x]\mathrm{d}x$
$\displaystyle=$
$\displaystyle\Pr[-\frac{\sqrt{-c}}{{\left\|a\right\|}_{2}}\leq
X\leq\frac{\sqrt{-c}}{{\left\|a\right\|}_{2}}]-\int\limits_{{\left\|a\right\|}_{2}^{2}x^{2}+c\leq
0}\exp\left({\left\|a\right\|}_{2}^{2}x^{2}+c\right)\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{1}{2}x^{2}\right)\mathrm{d}x$
($\sqrt{1-2a^{2}}x=y$) $\displaystyle=$
$\displaystyle\Pr[-\frac{\sqrt{-c}}{{\left\|a\right\|}_{2}}\leq
X\leq\frac{\sqrt{-c}}{{\left\|a\right\|}_{2}}]-\frac{\exp\left(c\right)}{\sqrt{1-2{\left\|a\right\|}_{2}^{2}}}\int\limits_{\frac{{\left\|a\right\|}_{2}^{2}}{1-2{\left\|a\right\|}_{2}^{2}}y^{2}+c\leq
0}\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{1}{2}y^{2}\right)\mathrm{d}y$
$\displaystyle=$
$\displaystyle\Pr[-\frac{\sqrt{-c}}{{\left\|a\right\|}_{2}}\leq
X\leq\frac{\sqrt{-c}}{{\left\|a\right\|}_{2}}]-\frac{\exp\left(c\right)}{\sqrt{1-2{\left\|a\right\|}_{2}^{2}}}\int\limits_{\frac{{\left\|a\right\|}_{2}^{2}}{1-2{\left\|a\right\|}_{2}^{2}}y^{2}+c\leq
0}\Pr[X=y]\mathrm{d}y$ $\displaystyle=$
$\displaystyle\Pr[-\frac{\sqrt{-c}}{{\left\|a\right\|}_{2}}\leq
X\leq\frac{\sqrt{-c}}{{\left\|a\right\|}_{2}}]-\frac{\exp\left(c\right)}{\sqrt{1-2{\left\|a\right\|}_{2}^{2}}}\texttt{erf}\left(\frac{\sqrt{(2{\left\|a\right\|}_{2}^{2}-1)c/2}}{{\left\|a\right\|}_{2}}\right)$
$\displaystyle=$
$\displaystyle\texttt{erf}\left(\frac{\sqrt{-c/2}}{{\left\|a\right\|}_{2}}\right)-\frac{\exp\left(c\right)}{\sqrt{1-2{\left\|a\right\|}_{2}^{2}}}\texttt{erf}\left(\frac{\sqrt{(2{\left\|a\right\|}_{2}^{2}-1)c/2}}{{\left\|a\right\|}_{2}}\right).$

∎

###  D.2. DP-spectrum of Random linear combination

######  Lemma 0 (Privacy of Random Linear Combination).

Let $\mathcal{M}_{RLC}$ be the random linear combination algorithm, that takes
as input a $n\times d$ real matrix $D$ with full column rank
$\mathbf{rank}(D)=d,$ samples a column vector $g$ from standard
$n$-dimensional normal distributions and outputs $D^{T}g$.

Fix $\epsilon>0$ and let $D$ be the database. Then $\delta$ is given by

$\displaystyle\delta_{RLC}$
$\displaystyle=\begin{cases}\max_{i}\left\\{\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},D^{T}D,{D}^{\prime
T}_{i}{D}^{\prime}_{i})\right\\}&\text{if
$\epsilon\geq-\frac{1}{2}\ln{(1-\left(P\right)_{i,i})}$}\\\
\max_{i}\left\\{\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},{D}^{\prime
T}_{i}{D}^{\prime}_{i},D^{T}D)\right\\}&\text{If
$0\leq\epsilon<-\frac{1}{2}\ln{(1-\left(P\right)_{i,i})}$},\end{cases}$

where

$\displaystyle\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},D^{T}D,{D}^{\prime
T}_{i}{D}^{\prime}_{i})1-\exp\left(\epsilon\right)+\exp\left(\epsilon\right)\texttt{erf}\left(\sqrt{\frac{\epsilon-\frac{1}{2}\ln{(1-\left(P\right)_{i,i})}}{\left(P\right)_{i,i}}}\right)-\texttt{erf}\left(\sqrt{\frac{(\epsilon-\frac{1}{2}\ln{(1-\left(P\right)_{i,i})})(1-\left(P\right)_{i,i})}{\left(P\right)_{i,i}}}\right),$

and

$\displaystyle\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},{D}^{\prime
T}_{i}{D}^{\prime}_{i},D^{T}D)\texttt{erf}\left(\sqrt{\frac{-\epsilon-\frac{1}{2}\ln{1-\left(P\right)_{i,i}}}{\left(P\right)_{i,i}}}\right)-\exp\left(\epsilon\right)\texttt{erf}\left(\sqrt{\frac{(\epsilon+\frac{1}{2}\ln{1-\left(P\right)_{i,i}})(\left(P\right)_{i,i}-1)}{\left(P\right)_{i,i}}}\right).$

###### Proof.

The proof is about plugging in the Proposition D.1 into the Lemma 6. Let $P$
be the projection matrix for $D$ and $\left(P\right)_{i,i}$ be the $i$-th
diagonal entry of $P.$ Let $v_{i}$ be the transpose of $i$-th row of $D$.

According to Lemma 6,

$\displaystyle\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},D^{T}D,{D}^{\prime
T}_{i}{D}^{\prime}_{i})=\mathbb{E}\left(\max\\{0,1-\exp\left(-(a_{i,1}^{T}Z)^{2}+c_{i,1}\right)\\}\right),$

where
$a_{i,1}=\sqrt{\frac{1}{2}\frac{1}{1-\left(P\right)_{i,i}}}(D^{T}D)^{-\frac{1}{2}}v_{i}$
and $c_{i,1}=\epsilon-\frac{1}{2}\ln{(1-\left(P\right)_{i,i})}$. Then we plug
it in Proposition D.1, and have

$\displaystyle\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},D^{T}D,{D}^{\prime
T}_{i}{D}^{\prime}_{i})=1-\exp\left(\epsilon\right)+\exp\left(\epsilon\right)\texttt{erf}\left(\sqrt{\frac{\epsilon-\frac{1}{2}\ln{(1-\left(P\right)_{i,i})}}{\left(P\right)_{i,i}}}\right)-\texttt{erf}\left(\sqrt{\frac{(\epsilon-\frac{1}{2}\ln{(1-\left(P\right)_{i,i})})(1-\left(P\right)_{i,i})}{\left(P\right)_{i,i}}}\right)$

Similarly, according to Lemma 6,

$\displaystyle\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},{D}^{\prime
T}_{i}{D}^{\prime}_{i},D^{T}D)=\mathbb{E}\left(\max\\{0,1-\exp\left((a_{i,2}^{T}Z)^{2}+c_{i,2}\right)\\}\right),$

where $a_{i,2}=\sqrt{\frac{1}{2}\frac{1}{1+v_{i}^{T}({D}^{\prime
T}_{i}{D}^{\prime}_{i})^{-1}v_{i}}}({D}^{\prime
T}_{i}{D}^{\prime}_{i})^{-\frac{1}{2}}v_{i}$ and
$c_{i,2}=\epsilon+\frac{1}{2}\ln{(1-\left(P\right)_{i,i})}$.

If $\epsilon\geq-\frac{1}{2}\ln{(1-\left(P\right)_{i,i})}$ then
$\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},{D}^{\prime
T}_{i}{D}^{\prime}_{i},D^{T}D)=0.$ If
$\epsilon<-\frac{1}{2}\ln{(1-\left(P\right)_{i,i})}$, since by leverage
score’s property
${\left\|a_{i,2}\right\|}_{2}^{2}=\frac{1}{2}\frac{v_{i}^{T}({D}^{\prime
T}_{i}{D}^{\prime}_{i})^{-1}v_{i}}{1+v_{i}^{T}({D}^{\prime
T}_{i}{D}^{\prime}_{i})^{-1}v_{i}}=\frac{\left(P\right)_{i,i}}{2}\leq\frac{1}{2}$,
we plug it in Proposition 3, and we have

$\displaystyle\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},{D}^{\prime
T}_{i}{D}^{\prime}_{i},D^{T}D)=\texttt{erf}\left(\sqrt{\frac{-\epsilon-\frac{1}{2}\ln{1-\left(P\right)_{i,i}}}{\left(P\right)_{i,i}}}\right)-\exp\left(\epsilon\right)\texttt{erf}\left(\sqrt{\frac{(\epsilon+\frac{1}{2}\ln{1-\left(P\right)_{i,i}})(\left(P\right)_{i,i}-1)}{\left(P\right)_{i,i}}}\right).$

Combining the above together, we have

$\displaystyle\delta_{i}$
$\displaystyle=\max\\{\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},{D}^{\prime
T}_{i}{D}^{\prime}_{i},D^{T}D),\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},D^{T}D,{D}^{\prime
T}_{i}{D}^{\prime}_{i})\\}$
$\displaystyle=\begin{cases}\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},D^{T}D,{D}^{\prime
T}_{i}{D}^{\prime}_{i})&\text{if
$\epsilon\geq-\frac{1}{2}\ln{(1-\left(P\right)_{i,i})}$}\\\
\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},{D}^{\prime
T}_{i}{D}^{\prime}_{i},D^{T}D)&\text{If
$0\leq\epsilon<-\frac{1}{2}\ln{(1-\left(P\right)_{i,i})}$}.\end{cases}$

∎

###  D.3. DP-spectrum of Random Projection

######  Lemma 0 (Privacy of Random Projection).

Let $\mathcal{M}_{RP}$ be the random projection algorithm, that takes as input
a $n\times d$ real matrix $D$ with full column rank $\mathbf{rank}(D)=d,$
samples a $n\times r$ Gaussian matrix $G$, where each of entry is a standard
normal random variable, and outputs $D^{T}G$.

Fix $\epsilon>0$ and let $D$ be the database. Then $\delta$ is given by

$\displaystyle\delta_{RP}$
$\displaystyle=\begin{cases}\max_{i}\left\\{\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},\Sigma,\Sigma_{i})\right\\}&\text{if
$\epsilon\geq-\frac{1}{2}\ln{(1-\left(P\right)_{i,i})}$}\\\
\max_{i}\left\\{\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},\Sigma_{i},\Sigma)\right\\}&\text{If
$0\leq\epsilon<-\frac{1}{2}\ln{(1-\left(P\right)_{i,i})}$},\end{cases}$

where

$\displaystyle\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},\Sigma,\Sigma_{i})$
$\displaystyle=\frac{1}{2}-\exp\left(\epsilon-\frac{r}{2}\ln{(1-\left(P\right)_{i,i})}\right)\sqrt{\frac{1-\left(P\right)_{i,i}}{r\left(P\right)_{i,i}+1-\left(P\right)_{i,i}}}+\exp\left(\epsilon-\frac{r}{2}\ln{(1-\left(P\right)_{i,i})}\right)\sqrt{\frac{1-\left(P\right)_{i,i}}{r\left(P\right)_{i,i}+1-\left(P\right)_{i,i}}}$
$\displaystyle\texttt{erf}\left(\sqrt{\frac{(\epsilon-\frac{r}{2}\ln{(1-\left(P\right)_{i,i})})(r\left(P\right)_{i,i}+1-\left(P\right)_{i,i})}{r\left(P\right)_{i,i}}}\right)-\frac{1}{2}\texttt{erf}\left(\sqrt{\frac{(\epsilon-\frac{r}{2}\ln{(1-\left(P\right)_{i,i})})(1-\left(P\right)_{i,i})}{r\left(P\right)_{i,i}}}\right),$
$\displaystyle\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},\Sigma_{i},\Sigma)$
$\displaystyle=$
$\displaystyle\frac{1}{2}+\frac{1}{2}\texttt{erf}\left(\sqrt{\frac{-\epsilon-\frac{r}{2}\ln{1-\left(P\right)_{i,i}}}{r\left(P\right)_{i,i}}}\right)-\frac{\exp\left(\epsilon+\frac{r}{2}\ln{1-\left(P\right)_{i,i}}\right)}{\sqrt{1-r\left(P\right)_{i,i}}}\texttt{erf}\left(\sqrt{\frac{(\epsilon+\frac{r}{2}\ln{1-\left(P\right)_{i,i}})(r\left(P\right)_{i,i}-1)}{r\left(P\right)_{i,i}}}\right),$

if $r<\frac{1}{\left(P\right)_{i,i}}$ and

$\displaystyle\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},\Sigma_{i},\Sigma)$
$\displaystyle=$
$\displaystyle\frac{1}{2}+\frac{1}{2}\texttt{erf}\left(\sqrt{\frac{-\epsilon-\frac{r}{2}\ln{1-\left(P\right)_{i,i}}}{r\left(P\right)_{i,i}}}\right)-\frac{\exp\left(\epsilon+\frac{r}{2}\ln{1-\left(P\right)_{i,i}}\right)}{\sqrt{r\left(P\right)_{i,i}-1}}\texttt{erfi}\left(\sqrt{\frac{(\epsilon+\frac{r}{2}\ln{1-\left(P\right)_{i,i}})(1-r\left(P\right)_{i,i})}{r\left(P\right)_{i,i}}}\right).$

if $r>\frac{1}{\left(P\right)_{i,i}}$.

###### Proof.

The proof is about plugging in the Proposition D.1 into the Lemma 7. Let $P$
be the projection matrix for $D$ and $\left(P\right)_{i,i}$ be the $i$-th
diagonal entry of $P.$ Let $v_{i}$ be the transpose of $i$-th row of $D$.

According to Lemma 7,

$\displaystyle\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},\Sigma,\Sigma_{i})=\mathbb{E}\left(\max\\{0,1-\exp\left(-(a_{i,1}^{T}Z)^{2}+c_{i,1}\right)\\}\right),$

where
$a_{i,1}=\sqrt{\frac{1}{2}\frac{r}{1-\left(P\right)_{i,i}}}(D^{T}D)^{-\frac{1}{2}}v_{i}$
and $c_{i,1}=\epsilon-\frac{r}{2}\ln{(1-\left(P\right)_{i,i})}$.

Then we plug it in Proposition D.1, and have

$\displaystyle\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},\Sigma,\Sigma_{i})$
$\displaystyle=$
$\displaystyle\frac{1}{2}-\exp\left(\epsilon-\frac{r}{2}\ln{(1-\left(P\right)_{i,i})}\right)\sqrt{\frac{1-\left(P\right)_{i,i}}{r\left(P\right)_{i,i}+1-\left(P\right)_{i,i}}}+\exp\left(\epsilon-\frac{r}{2}\ln{(1-\left(P\right)_{i,i})}\right)\sqrt{\frac{1-\left(P\right)_{i,i}}{r\left(P\right)_{i,i}+1-\left(P\right)_{i,i}}}$
$\displaystyle\texttt{erf}\left(\sqrt{\frac{(\epsilon-\frac{r}{2}\ln{(1-\left(P\right)_{i,i})})(r\left(P\right)_{i,i}+1-\left(P\right)_{i,i})}{r\left(P\right)_{i,i}}}\right)-\frac{1}{2}\texttt{erf}\left(\sqrt{\frac{(\epsilon-\frac{r}{2}\ln{(1-\left(P\right)_{i,i})})(1-\left(P\right)_{i,i})}{r\left(P\right)_{i,i}}}\right).$

Similarly, according to Lemma 7,

$\displaystyle\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},\Sigma_{i},\Sigma)=\mathbb{E}\left(\max\\{0,1-\exp\left((a_{i,2}^{T}Z)^{2}+c_{i,2}\right)\\}\right),$

where $a_{i,2}=\sqrt{\frac{r}{2}\frac{1}{1+v_{i}^{T}({D}^{\prime
T}_{i}{D}^{\prime}_{i})^{-1}v_{i}}}({D}^{\prime
T}_{i}{D}^{\prime}_{i})^{-\frac{1}{2}}v_{i}$ and
$c_{i,2}=\epsilon+\frac{r}{2}\ln{(1-\left(P\right)_{i,i})}$.

If $\epsilon\geq-\frac{r}{2}\ln{(1-\left(P\right)_{i,i})}$, then
$\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},\Sigma_{i},\Sigma)=0.$
Then we consider the case when
$\epsilon<-\frac{r}{2}\ln{(1-\left(P\right)_{i,i})}$. If
$r<\frac{1}{\left(P\right)_{i,i}}$, then
${\left\|a_{i,2}\right\|}_{2}^{2}=\frac{r}{2}\frac{v_{i}^{T}({D}^{\prime
T}_{i}{D}^{\prime}_{i})^{-1}v_{i}}{1+v_{i}^{T}({D}^{\prime
T}_{i}{D}^{\prime}_{i})^{-1}v_{i}}=\frac{r\left(P\right)_{i,i}}{2}<\frac{1}{2}$,
we plug it in Proposition 3, and we have

$\displaystyle\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},\Sigma_{i},\Sigma)$
$\displaystyle=$
$\displaystyle\frac{1}{2}+\frac{1}{2}\texttt{erf}\left(\sqrt{\frac{-\epsilon-\frac{r}{2}\ln{1-\left(P\right)_{i,i}}}{r\left(P\right)_{i,i}}}\right)-\frac{\exp\left(\epsilon+\frac{r}{2}\ln{1-\left(P\right)_{i,i}}\right)}{\sqrt{1-r\left(P\right)_{i,i}}}\texttt{erf}\left(\sqrt{\frac{(\epsilon+\frac{r}{2}\ln{1-\left(P\right)_{i,i}})(r\left(P\right)_{i,i}-1)}{r\left(P\right)_{i,i}}}\right).$

If $r>\frac{1}{\left(P\right)_{i,i}}$, then
${\left\|a_{i,2}\right\|}_{2}^{2}=\frac{r}{2}\frac{v_{i}^{T}({D}^{\prime
T}_{i}{D}^{\prime}_{i})^{-1}v_{i}}{1+v_{i}^{T}({D}^{\prime
T}_{i}{D}^{\prime}_{i})^{-1}v_{i}}=\frac{r\left(P\right)_{i,i}}{2}>\frac{1}{2}$,
we plug it in Proposition 2, and we have

$\displaystyle\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},\Sigma_{i},\Sigma)$
$\displaystyle=$
$\displaystyle\frac{1}{2}+\frac{1}{2}\texttt{erf}\left(\sqrt{\frac{-\epsilon-\frac{r}{2}\ln{1-\left(P\right)_{i,i}}}{r\left(P\right)_{i,i}}}\right)-\frac{\exp\left(\epsilon+\frac{r}{2}\ln{1-\left(P\right)_{i,i}}\right)}{\sqrt{r\left(P\right)_{i,i}-1}}\texttt{erfi}\left(\sqrt{\frac{(\epsilon+\frac{r}{2}\ln{1-\left(P\right)_{i,i}})(1-r\left(P\right)_{i,i})}{r\left(P\right)_{i,i}}}\right).$

Combining the above together, we have

$\displaystyle\delta_{i}$
$\displaystyle=\max\\{\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},\Sigma,\Sigma_{i}),\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},\Sigma_{i},\Sigma)\\}$
$\displaystyle=\begin{cases}\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},\Sigma,\Sigma_{i})&\text{if
$\epsilon\geq-\frac{r}{2}\ln{(1-\left(P\right)_{i,i})}$}\\\
\delta(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{0}},\Sigma_{i},\Sigma)&\text{If
$0\leq\epsilon<\epsilon\geq-\frac{r}{2}\ln{(1-\left(P\right)_{i,i})}$}.\end{cases}$

∎