smallequation

$\BODY$

(1)

smallalign

$\BODY$

(2)

# Differential Privacy with Random Projections
and Sign Random Projections

Ping Li, Xiaoyun Li
LinkedIn Ads
700 Bellevue Way NE, Bellevue, WA 98004, USA
{pinli<EMAIL_ADDRESS>
###### Abstract

In this paper, we develop a series of differential privacy (DP) algorithms
from a family of random projections (RP), for general applications in machine
learning, data mining, and information retrieval. Among the presented
algorithms, iDP-SignRP is remarkably effective under the setting of
“individual differential privacy” (iDP), based on sign random projections
(SignRP). Also, DP-SignOPORP considerably improves existing algorithms in the
literature under the standard DP setting, using “one permutation + one random
projection” (OPORP), where OPORP is a variant of the celebrated count-sketch
method with fixed-length binning and normalization. Without taking signs,
among the DP-RP family, DP-OPORP achieves the best performance.

The concept of iDP (individual differential privacy) is defined only on a
particular dataset of interest. While iDP is not strictly DP, it might be
useful in certain applications, such as releasing a dataset (including sharing
embeddings across companies or countries). In our study, we find that iDP-
SignRP is remarkably effective for search and machine learning applications,
in that the utilities are exceptionally good even at a very small privacy
parameter $\epsilon$ (e.g., $\epsilon<0.5$).

Privacy can be protected at various stages of data life cycle. In this study,
our methods can be applied as early as at data collection time. Instead of
directly using the original $p$-dimensional vector $u$, we let
$x_{j}=\sum_{i=1}^{p}u_{i}w_{ij}$, where $j=1$ to $k$ and $w_{ij}$ is sampled
from the Gaussian distribution. This is known as random projections (RP). In
this paper, we assume the projection matrix $\\{w_{ij}\\}$ is also released to
the public, as a stronger privacy setting. The previous algorithm named “DP-
RP-G” can be improved quite considerably by setting the noise more carefully.
The proposed new variant, named “DP-RP-G-OPT”, compares favorably with
directly adding noise to the original data. DP-RP-G-OPT can be further
improved by “DP-RP-G-OPT-B” by replacing the Gaussian projections with
Rademacher projections due to the smaller sensitivity. Finally, via the fixed-
length binning mechanism, “DP-OPORP” slightly outperforms DP-RP-G-OPT-B.
Empirical evidence shows that these DP-RP algorithms require $\epsilon\approx
20$ to achieve a good utility.

Our key idea for improving DP-RP is to take only the signs, i.e.,
$sign(x_{j})=sign\left(\sum_{i=1}^{p}u_{i}w_{ij}\right)$, of the projected
data. The intuition is that the signs often remain unchanged when the original
data ($u$) exhibit small changes (according to the “neighbor” definition in
DP). In other words, the aggregation and quantization operations themselves
provide good privacy protections. We develop a technique called “smooth
flipping probability” that incorporates this intuitive privacy benefit of
SignRPs and improves the standard DP bit flipping strategy. Based on this
technique, we propose DP-SignOPORP which satisfies strict DP and outperforms
other DP variants based on SignRP (and RP), especially when $\epsilon$ is not
very large (e.g., $\epsilon=5\sim 10$). Moreover, if an application scenario
accepts individual DP, then we immediately obtain an algorithm named iDP-
SignRP which achieves excellent utilities even at small $\epsilon$ (e.g.,
$\epsilon<0.5$).

In practice, the main obstacle for deploying DP at the source of data is the
severe degradation of performance because the amount of required noise is
typically high. We hope our proposed series of DP (and iDP) algorithms, e.g.,
DP-OPORP, DP-SignOPORP, iDP-SignRP, will help promote the industrial
applications of DP in search, retrieval, ranking, and AI in general.

###### Contents

  1. 1 Introduction
    1. 1.1 Random Projections (RP) and Very Sparse Random Projections (VSRP)
    2. 1.2 Sign Random Projections (SignRP)
    3. 1.3 Count-Sketch and OPORP: One Permutation + One Random Projection
    4. 1.4 DP Through RP and SignRP: Applications, Algorithms and Results
  2. 2 Preliminaries
    1. 2.1 Differential Privacy
    2. 2.2 Local Sensitivity and Smooth Sensitivity
    3. 2.3 Relaxation: Individual Differential Privacy (iDP)
  3. 3 DP-RP: Differentially Private Random Projections
    1. 3.1 Gaussian Noise Mechanism for DP-RP
    2. 3.2 The Optimal Gaussian Noise Mechanism for DP-RP
    3. 3.3 The Laplace Noise Mechanism for DP-RP
    4. 3.4 DP-RP-G-OPT-B: DP-RP with Rademacher Projections
    5. 3.5 DP-OPORP: A More Efficient Alternative
    6. 3.6 Comparison: Inner Product Estimation
  4. 4 DP-SignRP: Differentially Private Sign Random Projections
    1. 4.1 DP-SignRP-RR by Randomized Response
      1. 4.1.1 The flipping probability and calculation of $N_{+}$
      2. 4.1.2 Utility in angle estimation by DP-SignRP-RR
    2. 4.2 DP-SignRP-RR-Smooth Using Smooth Flipping Probability
    3. 4.3 DP-SignRP with Rademacher Projections
    4. 4.4 DP-SignOPORP with Smooth Flipping Probability
  5. 5 Experiments
    1. 5.1 Similarity Search
    2. 5.2 SVM Classification
    3. 5.3 Results for DP-SignOPORP
  6. 6 iDP-SignRP Under Individual Differential Privacy (iDP)
    1. 6.1 iDP-SignRP-G by Gaussian Noise Addition
    2. 6.2 iDP-SignRP-RR by Randomized Response
    3. 6.3 Empirical Results on iDP
  7. 7 Conclusion
  8. A Deferred Proofs
    1. A.1 Proof of Lemma 3.6
    2. A.2 Proof of Lemma 4.2

##  1 Introduction

With the rapid growth of capable electronic devices, personal data has been
continuously collected by companies/organizations. Protecting data privacy has
become an urgent need and a trending research topic in computer science,
statistics, applied mathematics, etc. Among many notions of privacy, the
“differential privacy” (DP) (Dwork et al., 2006) has gained tremendous
attention in both the research community and industrial applications. The
intuition of DP is straightforward:

We want to find a randomized data output procedure, such that a small change
in the database can hardly be detected by an adversary based on the
observation of the output.

Differential privacy provides a formal mathematical definition of privacy (see
Section 2 for the details) that is powerful in the sense that it protects the
sensitive data regardless of how the adversary utilizes the data subsequently.
The strength of DP is usually characterized by two parameters, $\epsilon$ and
$\delta$. If $\delta=0$, we say that the algorithm is “pure DP” (i.e.,
$\epsilon$-DP); if $\delta>0$, the algorithm is called “approximate DP” (i.e.,
$(\epsilon,\delta)$-DP). The typical technique of DP is to randomize/perturb
the algorithm output by adding noise or probabilistic sampling. DP has been
widely applied to numerous tasks such as clustering (Feldman et al., 2009;
Gupta et al., 2010), regression and classification (Chaudhuri and Monteleoni,
2008; Zhang et al., 2012), DP-SGD (Abadi et al., 2016; Agarwal et al., 2018;
Fang et al., 2023), principle component analysis (Ge et al., 2018), empirical
risk minimization (Chaudhuri et al., 2011), matrix completion (Blum et al.,
2005; Jain et al., 2018), graph distance estimation (Kasiviswanathan et al.,
2013; Fan and Li, 2022; Fan et al., 2022). In industry, DP has been broadly
deployed to collect user data for (e.g.,) frequency or mean estimation at, for
example, Google (Erlingsson et al., 2014), Apple111https://docs-
assets.developer.apple.com/ml-research/papers/learning-with-privacy-at-
scale.pdf, and Microsoft (Ding et al., 2017).

The data to be protected may have various forms and come from various sources,
for example: (i) the user “profile” vectors that contain sensitive attributes
like personal information, click history, etc.; (ii) the embedding vectors
learned from the user data, which may also contain rich information about the
users and could be attacked by malicious adversaries to infer user attributes
(Beigi et al., 2020; Zhang et al., 2021). In a machine learning model, there
are several choices on when to deploy differential privacy (DP): (a) at the
data collection/processing stage (Zhang et al., 2014; Yang et al., 2015;
Berlioz et al., 2015; Cormode et al., 2018b); (b) during the model training
stage (Abadi et al., 2016; Wei et al., 2020); and (c) on the model output (or
summary data statistics) (Dwork and Lei, 2009). While each of them may find
its need depending on the application scenarios, applying DP as early as at
the data collection stage provides strong protection in the sense that the
subsequent operations or outputs will become private by the post-processing
property of differential privacy. Moreover, the data holder may need to
release the data to third-parties. In this case, a private data publishing
mechanism (at an early stage) becomes necessary.

In this work, we study differential privacy algorithms for protecting data
vectors, based on the broad family of random projections (RP) and sign random
projections (SignRP). Our algorithms can be applied to data publishing and
processing for downstream machine learning tasks. In this paper, besides the
standard DP, we also consider a relaxation of DP called “individual
differential privacy” (iDP) (Soria-Comas et al., 2017), which was proposed
with the aim of improving the utility of private algorithms. It turns out
that, when it is applied to SignRP, iDP indeed provides a much better utility,
a phenomenon which might be interesting to the DP researchers and
practitioners and provides a plausible option for balancing the privacy and
utility in practice.

###  1.1 Random Projections (RP) and Very Sparse Random Projections (VSRP)

In practice, compression and dimension reduction techniques can be crucial
when dealing with massive (high-dimensional) data. The random projection (RP)
method is an important fundamental algorithm. Denote $u\in\mathbb{R}^{p}$ as
the data vector with $p$ features. With some $k$ (and typically $k\ll p$), we
define the random projection of $u$ as

$\displaystyle X=\frac{1}{\sqrt{k}}W^{T}u,\ \ W\in\mathbb{R}^{p\times k}.$ (3)

The entries of the random matrix $W$ typically follow the Gaussian
distribution or Gaussian-like distribution such as uniform. It has been well-
understood that, with a sufficient number of projections ($k$), the similarity
between two vectors (using the same projection $W$) is preserved within a
small multiplicative error with high probability. The dimensionality reduction
and geometry preserving properties make RP widely useful in numerous
applications, such as distance estimation, nearest neighbor search,
clustering, classification, compressed sensing, etc. (Johnson and
Lindenstrauss, 1984; Indyk and Motwani, 1998; Dasgupta, 2000; Bingham and
Mannila, 2001; Achlioptas, 2003; Fern and Brodley, 2003; Vempala, 2005; Candès
et al., 2006; Donoho, 2006; Li et al., 2006; Freund et al., 2007; Dasgupta and
Freund, 2008; Dahl et al., 2013; Li and Li, 2019a; Rabanser et al., 2019;
Tomita et al., 2020; Zhang and Li, 2020; Li and Li, 2023a).

Instead of using dense projections, it is also common to sample the entries of
$W$ from the following “very sparse” distribution, i.e., VSRP (Li et al.,
2006):

$\displaystyle\sqrt{s}\times\left\\{\begin{array}[]{rrl}-1&\text{with
prob.}&1/(2s)\\\ 0&\text{with prob.}&1-1/s\ ,\\\ +1&\text{with
prob.}&1/(2s)\end{array}\right.$ (7)

which generalizes Achlioptas (2003) (for $s=1$ and $s=3$). Note that when
$s=1$, it is also called the “symmetric Bernoulli” distribution or the
“Rademacher” distribution. In a recent study by Li and Li (2023a), the
estimation accuracy of VSRP can be substantially improved via a normalization
step.

###  1.2 Sign Random Projections (SignRP)

While RP is able to reduce the dimensionality to, e.g., hundreds, storing and
transmitting the random projections might still be expensive for large
datasets. To this regard, one can further compress the RPs by
quantization/discretization, where we only use a few bits to represent the
projected data, instead of using full-precision (32 or 64 bits). Quantized
random projections (QRP) and the extensions (e.g., to non-linear kernels) have
many applications in various fields, e.g., compressed sensing, approximate
nearest neighbor search, similarity estimation, large-scale machine learning
(Goemans and Williamson, 1995; Charikar, 2002; Datar et al., 2004; Boufounos
and Baraniuk, 2008; Dong et al., 2008; Zymnis et al., 2010; Leng et al., 2014;
Li et al., 2014; Knudson et al., 2016; Slawski and Li, 2018; Li, 2019; Li and
Li, 2019b; Xu et al., 2021; Li and Li, 2021). In particular, in this paper, we
will consider the differential privacy of the extreme case of sign (1-bit)
random projection (SignRP), also known as the “SimHash” in the literature,
where only the sign of the projected data is stored. Compared with storing the
full-precision floats, SignRP provides substantial memory and communication
saving which could be beneficial for large-scale databases.

From the sign random projections, one can estimate the angle/cosine between
the data vectors. Consider two data vectors $u$ and $v$ with
$\rho=\frac{u^{T}v}{\|u\|\|v\|}$ and $\theta=\cos^{-1}(\rho)$. Denote
$x=\frac{1}{\sqrt{k}}W^{T}u$ and $y=\frac{1}{\sqrt{k}}W^{T}v$, with
$x,y\in\mathbb{R}^{k}$. The standard result (Goemans and Williamson, 1995;
Charikar, 2002) gives the collision probability for a single sign random
projection as

$\displaystyle Pr\left(sign(x_{j})=sign(y_{j})\right)=1-\frac{\theta}{\pi},\ \
\forall j=1,...,k,$ (8)

which leads to a straightforward estimator of the angle $\theta$ as

$\displaystyle\hat{\theta}=\pi\left(1-\frac{1}{k}\sum_{j=1}^{k}\mathbbm{1}\\{sign(x_{j})=sign(y_{j})\\}\right).$
(9)

As $\mathbbm{1}\\{sign(x_{j})=sign(y_{j})\\}$ follows a Bernoulli
distribution, the mean and variance of $\hat{\theta}$ can be precisely
computed:

$\displaystyle\mathbb{E}[\hat{\theta}]=\theta,\quad
Var(\hat{\theta})=\frac{\theta(\pi-\theta)}{k}.$ (10)

In addition to the mentioned benefits of achieving highly compact
representations of the original data, SignRP has also been widely used for
approximate near neighbor (ANN) search (Friedman et al., 1975) by building
hash tables from the SignRP bits (Indyk and Motwani, 1998; Charikar, 2002;
Shrivastava and Li, 2014).

###  1.3 Count-Sketch and OPORP: One Permutation + One Random Projection

The celebrated count-sketch data structure (Charikar et al., 2004) can be
viewed as a special type of very sparse projections. Count-sketch is highly
efficient because, as an option, it only requires “one permutation + one
random projection” (OPORP), as opposed to $k$ projections. The recent work by
Li and Li (2023a) improved the original count-sketch in two aspects: (i) Using
a fixed-length binning scheme makes the algorithms more convenient and also
reduces the variance by a factor of $\frac{p-k}{p-1}$. (ii) The projected data
(i.e., vectors in $k$ dimensions) should be normalized before they are used to
estimate the original cosine. By doing so, the estimation variance can be
substantially reduced, essentially from $(1+\rho^{2})/k$ (un-normalized) to
$(1-\rho^{2})^{2}/k$ (normalized).

As the name OPORP suggests, the original data vector $u$ is first permuted by
a random permutation, and then it is divided into $k$ bins. Within each bin,
we apply a random projection of size $p/k$ to obtain one projected value.
Thus, we still obtain $k$ projected values but the procedure is drastically
more efficient than the standard random projections. The count-sketch data
structure and variants have been widely used in applications. Recent examples
include graph embedding (Wu et al., 2019), word & image embedding (Chen et
al., 2017; Zhang et al., 2020; AlOmar et al., 2021; Singhal et al., 2021;
Zhang et al., 2022), model & communication compression (Weinberger et al.,
2009; Chen et al., 2015; Rothchild et al., 2020; Haddadpour et al., 2020; Li
and Zhao, 2022) for linear models as well as deep neural nets, etc.

###  1.4 DP Through RP and SignRP: Applications, Algorithms and Results

In this paper, we propose to use random projection (RP) and sign random
projection (SignRP) for data privatization. We name our methods
“differentially private random projections” (DP-RP) and DP-SignRP.
Additionally, we develop a series of algorithms for OPORP, named DP-OPORP and
DP-SignOPORP. Finally, we will present iDP-SignRP using individual
differential privacy (iDP).

The typical use cases of the proposed algorithms include:

  * •

In on-device data collection, each user can apply our methods locally (with
shared projection matrix/vectors) before sending the data to the server in the
data collection process.

  * •

At the central data silo, the data curator can first apply our methods to the
data attributes (or embeddings) and then publish the output (randomized data)
for data analysis or modeling.

By the geometry-preserving property of RP and SignRP, our approaches could be
naturally and effectively applied to a variety of distance/similarity based
downstream tasks like (approximate) nearest search, clustering,
classification, and regression. Additionally, with DP-RP and DP-SignRP, the
data compression (especially for high-dimensional datasets) is also able to
consequently reduce the computational cost and the communication overhead when
transmitting the data.

More specifically, for a data vector $u\in\mathbb{R}^{p}$, our goal is to make
its RP and SignRP, namely $x=W^{T}u$ and $sign(X)$, differentially private.
Then, for a database $U$ consisting of $n$ data vectors, applying this
mechanism to all the points makes $U$ differentially private against a change
in one data record. In the literature, there are works on randomized
algorithms that assume the randomness of the algorithm (e.g., the hash keys or
projection matrices) are “internal” and also kept private (Blocki et al.,
2012; Smith et al., 2020; Dickens et al., 2022). We assume the projection
matrix $W$ is known/public, which is stronger in privacy and enables broader
applications of the released data. In addition, a “known projection matrix” is
the typical case in the local DP model (Kairouz et al., 2014; Cormode et al.,
2018a), since the projection matrix is created and shared among the users by
the data aggregator.

In summary, in this paper we make the following contributions:

  * •

In Section 3, for DP-RP, we first revisit/analyze the prior work (Kenthapadi
et al., 2013) on the $(\epsilon,\delta)$-DP random projection based on
Gaussian noise addition (called DP-RP-G). Then we propose an optimal Gaussian
noise mechanism DP-RP-G-OPT, which improves the previous method. Then, we
present DP-RP-G-OPT-B (which uses Rademacher projection and optimal noise) and
DP-OPORP. We compare these variants of DP-RP with the strategy of adding
(optimal) Gaussian noise to the raw data, in terms of the accuracy of inner
product estimation.

  * •

In Section 4, we propose two algorithms for privatizing the (1-bit) DP-SignRP.
The first method, DP-SignRP-RR, is based on the standard “randomized response”
(RR). Then, we propose an improved method named DP-SignRP-RR-smooth based on a
proposed concept of “smooth flipping sensitivity”, thanks to the robustness
brought by the “aggregate-and-sign” operation of SignRP. Finally, we extend
the idea of smooth flipping probability to the OPORP variant, and show that
DP-SignOPORP is more advantageous in terms of differential privacy.

  * •

In Section 5, we conduct retrieval and classification experiments on benchmark
datasets. Specifically, for DP-RP, the proposed optimal DP-RP-G-OPT method
substantially improves DP-RP-G, which is the previous DP-RP method in the
literature. DP-OPORP performs similarly to DP-RP-G-OPT-B. For the 1-bit
variants, our proposed DP-SignOPORP outperforms DP-RP variants and DP-OPORP
especially when $\epsilon$ is not large (e.g., $\epsilon=5\sim 10$).

  * •

In Section 6, we further design iDP-SignRP algorithms under the setting of
individual differential privacy (iDP), which is a relaxed definition of the
standard DP (Soria-Comas et al., 2017). Experiments demonstrate that iDP-
SignRP is able to achieve excellent utilities (precision, recall,
classification accuracy) even when $\epsilon$ is small (e.g., $\epsilon<0.5$).
We anticipate that iDP-SignRP will be useful (e.g.,) as a data-publishing
mechanism, among other applications.

##  2 Preliminaries

Throughout the paper, $\|\cdot\|_{1}$ and $\|\cdot\|_{2}$ are the $l_{1}$ and
$l_{2}$ norms, respectively. For convenience, $\|\cdot\|$ will denote the
$l_{2}$ norm if there is no risk of confusion. Let
$u\mathcal{U}\subset\mathbb{R}^{p}$ be a data vector of $p$ dimensions. We
assume $\|u\|>0$, i.e., there is no all-zero data sample.

###  2.1 Differential Privacy

Differential privacy (DP) has been one of the standard tools in the literature
to protect against (e.g.,) attribute inference attacks. The formal definition
of DP is as follows.

######  Definition 2.1 (Differential Privacy (Dwork et al., 2006)).

For a randomized algorithm $\mathcal{M}:\mathcal{U}\mapsto
Range(\mathcal{M})$, if for any two adjacent datasets $u$ and $u^{\prime}$, it
holds that

$Pr[\mathcal{M}(u)\in O]\leq e^{\epsilon}Pr[\mathcal{M}(u^{\prime})\in
O]+\delta$ (11)

for $\forall O\subset Range(\mathcal{M})$ and some $\epsilon,\delta\geq 0$,
then algorithm $\mathcal{M}$ is called $(\epsilon,\delta)$-differentially
private. If $\delta=0$, $\mathcal{M}$ is called $\epsilon$-differentially
private.

Consider the classic noise addition approaches in DP. Given some definition of
“neighboring”, one important quantity is the “sensitivity” described below.

######  Definition 2.2 (Sensitivity).

Let $Nb(u)$ denote the neighbor set of $u$, and
$\mathcal{N}(\mathcal{U})=\\{(u,u^{\prime}):u^{\prime}\in
Nb(u),u,u^{\prime}\in\mathcal{U}\\}$ be the collection of all possible
neighboring data pairs. The $l_{1}$-sensitivity and $l_{2}$-sensitivity of a
function $f:\mathcal{U}\mapsto\mathbb{R}^{k}$ are defined respectively as

$\displaystyle\Delta_{1}=\max_{(u,u^{\prime})\in\mathcal{N}(\mathcal{U})}\|f(u)-f(u^{\prime})\|_{1},\quad\Delta_{2}=\max_{(u,u^{\prime})\in\mathcal{N}(\mathcal{U})}\|f(u)-f(u^{\prime})\|_{2}.$

In this work, our goal is to protect the data itself independent of subsequent
tasks or operations. We follow the natural and standard definition in the DP
literature of “neighboring” for data vectors, that two vectors are adjacent if
they differ in one element (e.g., Dwork et al. (2006); Kenthapadi et al.
(2013); Xu et al. (2013); Dwork and Roth (2014); Smith et al. (2020);
Stausholm (2021); Dickens et al. (2022); Zhao et al. (2022); Li and Li
(2023b)).

######  Definition 2.3 ($\beta$-adjacency).

Let $u\in[-1,1]^{p}$ be a data vector. A vector $u^{\prime}\in[-1,1]^{p}$ is
said to be $\beta$-adjacent to $u$ if $u^{\prime}$ and $u$ differ in one
dimension $i$, and $|u_{i}-u_{i}^{\prime}|\leq\beta$.

Data vectors $u$ and $u^{\prime}$ satisfying Definition 2.3 are called
$\beta$-adjacent or $\beta$-neighboring. Several remarks follow:

  * •

Compared with $l_{1}$ difference: $\|u-u^{\prime}\|_{1}\leq\beta$, Definition
2.3 (i.e., $u^{\prime}$ and $u$ differ in one dimension $i$ with
$|u_{i}-u_{i}^{\prime}|\leq\beta$) considers the worst case of the $l_{1}$
difference in sensitivity analysis.

  * •

In the literature (e.g., Kenthapadi et al. (2013) for RP), $\beta=1$ is
typically used. We allow a more general $\beta$ to accommodate the need from
practical applications.

  * •

Assuming $u\in[-1,1]^{p}$ is merely for convenience, as one can easily extend
the results to $u\in[-C,C]^{p}$ for an arbitrary $C>0$. Note that,
coincidentally, the “max normalization” is a common data pre-processing
strategy, where each feature dimension is normalized to $[-1,1]$.

We make a more detailed explanation of the first point above. Since the
neighboring data vector $u^{\prime}$ and the raw data $u$ only differ in one
attribute by at most $\beta$, by Definition 2.2, it is easy to see that for RP
the sensitivities are precisely $\frac{1}{\sqrt{k}}$ times the largest row
norm of $W$:

$\displaystyle\Delta_{1}$
$\displaystyle=\frac{1}{\sqrt{k}}\beta\max_{(u,u^{\prime})\in\mathcal{N}(\mathcal{U})}\|W^{T}u-W^{T}u^{\prime}\|_{1}=\frac{1}{\sqrt{k}}\beta\max_{i=1,...,p}\|W_{[i,:]}\|_{1},$
(12) $\displaystyle\Delta_{2}$
$\displaystyle=\frac{1}{\sqrt{k}}\beta\max_{(u,u^{\prime})\in\mathcal{N}(\mathcal{U})}\|W^{T}u-W^{T}u^{\prime}\|_{2}=\frac{1}{\sqrt{k}}\beta\max_{i=1,...,p}\|W_{[i,:]}\|_{2}.$
(13)

where $W_{[i,:]}$ is the $i$-th row of $W$. It is a known fact that Definition
2.3 for neighboring is the worst case for the alternative neighboring
definition using the $l_{1}$ difference: “$u$ and $u^{\prime}$ are neighboring
if $\|u-u^{\prime}\|_{1}=\sum_{i=1}^{p}|u_{i}-u_{i}^{\prime}|\leq\beta$.”
Particularly, in our work, we have $f(u)=\frac{1}{\sqrt{k}}W^{T}u$, and thus

$\displaystyle\frac{1}{\sqrt{k}}\max_{\|u-u^{\prime}\|_{1}\leq\beta}\|W^{T}u-W^{T}u^{\prime}\|_{1}$
$\displaystyle=\frac{1}{\sqrt{k}}\max_{\|u-u^{\prime}\|_{1}\leq\beta}\|\sum_{i=1}^{p}(u_{i}-u_{i}^{\prime})W_{[i,:]}\|_{1}$
$\displaystyle\leq\frac{1}{\sqrt{k}}\max_{\|u-u^{\prime}\|_{1}\leq\beta}\sum_{i=1}^{p}|u_{i}-u_{i}^{\prime}|\|W_{[i,:]}\|_{1}$
$\displaystyle=\frac{1}{\sqrt{k}}\beta\max_{i=1,...,p}\|W_{[i,:]}\|_{1}=\Delta_{1}.$

Note that the last line equals (12) corresponding to the sensitivity based on
Definition 2.3. Since the neighboring condition in Definition 2.3 also
satisfies $\|u-u^{\prime}\|_{1}\leq\beta$, we know that the equality can be
exactly attained. Similarly, for the $l_{2}$ sensitivity, we have

$\displaystyle\frac{1}{\sqrt{k}}\max_{\|u-u^{\prime}\|_{1}\leq\beta}\|W^{T}u-W^{T}u^{\prime}\|_{2}$
$\displaystyle=\frac{1}{\sqrt{k}}\max_{\|u-u^{\prime}\|_{1}\leq\beta}\|\sum_{i=1}^{p}(u_{i}-u_{i}^{\prime})W_{[i,:]}\|_{2}$
$\displaystyle=\frac{1}{\sqrt{k}}\beta\max_{i=1,...,p}\|W_{[i,:]}\|_{2}=\Delta_{2}.$

Therefore, for the sensitivity analysis, the “$\beta$-adjacency” in Definition
2.3 in fact covers the definition of neighboring based on the $l_{1}$
difference.

Once the sensitivities can be identified/computed, the following two standard
noise addition mechanisms can be applied to make an algorithm differentially
private.

######  Theorem 2.1 (Laplace mechanism (Dwork et al., 2006)).

Given any function $f:\mathcal{U}\mapsto\mathbb{R}^{k}$ and $\epsilon>0$, the
randomized algorithm $\mathcal{M}(u)=f(u)+(Z_{1},...,Z_{k})$ is $\epsilon$-DP,
where $Z_{1},...,Z_{k}$ follow iid $Laplace(\Delta_{1}/\epsilon)$. The
centered Laplace distribution with scale $\lambda$ has density function
$g(x)=\frac{1}{2\lambda}e^{-\frac{|x|}{\lambda}}$.

######  Theorem 2.2 (Gaussian mechanism (Dwork and Roth, 2014)).

Given any function $f:\mathcal{U}\mapsto\mathbb{R}^{k}$, $0<\epsilon<1$,
$0<\delta<1$, the randomized algorithm $\mathcal{M}(u)=f(u)+(Z_{1},...,Z_{k})$
is $(\epsilon,\delta)$-DP, where $Z_{1},...,Z_{k}$ follow iid
$N(0,\sigma^{2})$ with
$\sigma=\Delta_{2}\frac{\sqrt{2\log(1.25/\delta)}}{\epsilon}$.

We remark that Theorem 2.2 requires $\epsilon<1$. The behavior of the Gaussian
noise for general $\epsilon$ will be discussed shortly in Section 3.
Furthermore, one of the nice facts about DP is that, multiple DP algorithms
can be composed together, where the final output is still DP.

######  Theorem 2.3 (Composition Theorem (Dwork and Roth, 2014)).

Let $\mathcal{M}_{j}:\mathcal{U}\rightarrow\mathbb{R}$ be an
$(\epsilon_{j},\delta_{j})$-DP algorithm for $j=1,...,k$. Then
$\mathcal{M}(u)=(\mathcal{M}_{1}(u),...,\mathcal{M}_{k}(u))$ is
$(\sum_{j=1}^{k}\epsilon_{i},\sum_{j=1}^{k}\delta_{j})$-DP.

###  2.2 Local Sensitivity and Smooth Sensitivity

The sensitivity in Definition 2.2 is a “global” worst-case bound over all
possible neighboring data $(u,u^{\prime})$ in the data domain, which in many
cases leads to overly large noise added to the algorithm output. Intuitively,
for each specific data $u$, to make $\mathcal{M}(u)$ and
$\mathcal{M}(u^{\prime})$ indistinguishable in the sense of DP, we may not
always need the worst-case noise. This is grasped by the concept of “local
sensitivity” as defined below.

######  Definition 2.4 (Local sensitivity (Nissim et al., 2007)).

For $u\in\mathcal{U}$ and a function $f:\mathcal{U}\mapsto\mathbb{R}^{k}$, the
local sensitivities of $f$ at $u$ are

$\displaystyle LS_{1}(u)=\max_{u^{\prime}\in
Nb(u)}\|f(u)-f(u^{\prime})\|_{1},\quad LS_{2}(u)=\max_{u^{\prime}\in
Nb(u)}\|f(u)-f(u^{\prime})\|_{2}.$

Instead of bounding the worst-case change in the output, the local sensitivity
at $u$ just focuses on the neighborhood of each specific $u$. By the
definitions, it is clear that $LS_{1}(u)\leq\Delta_{1}$ and
$LS_{2}(u)\leq\Delta_{2}$ for all $u\in\mathcal{U}$, i.e., the global
sensitivity is an upper bound of local sensitivity. That said, the noise level
calibrated to the local sensitivity is always smaller than the noise magnitude
calculated by the global sensitivity, which implies (substantially) better
utility.

One however cannot simply add noise according to the instance-specific local
sensitivity to achieve DP, for several reasons. (A) Only ensuring “local”
indistinguishability at each specific data instance does not satisfy the
rigorous DP condition (Definition 2.1), which requires the
indistinguishability between all possible adjacent data pairs. (B) The noise
level itself, when computed by the local sensitivity, is a function of $u$,
which may reveal the information of the database. Intuitively, the issue of
local sensitivity is that, although $u$ has small local sensitivity, its
neighbor $u^{\prime}$ may have very large local sensitivity. If the injected
noise is determined according to the local sensitivity, then the very
different noise scale may be detected by an adversary to distinguish $u$ from
$u^{\prime}$, violating the goal of DP. A simple example is provided in Nissim
et al. (2007) for reporting the median. In that same paper, the authors
proposed “smooth sensitivity” which leverages local sensitivity in the noise
calibration, at the same time also satisfies the DP definition. The intuition
is that, whatever “local” notion of sensitivity at $u$ we employ must account
for the more sensitive data which are nearby, but at a discounted factor
depending on how far they are from $u$.

######  Definition 2.5 (Smooth sensitivity (Nissim et al., 2007)).

For $u,u^{\prime}\in\mathcal{U}$, denote $d(u,u^{\prime})$ as the minimal
number of “neighboring operations” needed to derive $u^{\prime}$ from $u$
222For example, if $u$ and $u^{\prime}$ are two databases that differ in $t$
sample records, then $d(u,u^{\prime})=t$.. The $\epsilon$-smooth sensitivity
of $f:\mathcal{U}\mapsto\mathbb{R}^{k}$ at $u$ is defined as

$\displaystyle SS(u)=\max_{u^{\prime}\in\mathcal{U}}e^{-\epsilon
d(u,u^{\prime})}LS(u^{\prime}),$

where $LS(u^{\prime})$ is the local sensitivity (in proper metric) of $f$ at
$u^{\prime}$ in Definition 2.4.

The smooth sensitivity $SS(u)$ is an $\epsilon$-smooth upper bound of the
local sensitivity $LS(u)$ satisfying two conditions: (i) $SS(u)\geq LS(u)$,
$\forall u\in\mathcal{U}$; (ii) $SS(u)\leq e^{\epsilon}SS(u^{\prime})$,
$\forall u,u^{\prime}\in\mathcal{U}$ with $d(u,u^{\prime})=1$. Moreover,
$SS(u)$ is the smallest upper bound $\forall u$ among all such
$\epsilon$-smooth upper bounds333The global sensitivity (Definition 2.2) is
also an $\epsilon$-smooth upper bound of the local sensitivity.. Nissim et al.
(2007) also proposed several noise addition mechanisms tailored to the
(instance-specific) smooth sensitivity, with rigorous DP guarantees. In
particular, the smooth sensitivity usually works very well for robust
statistics/estimators (e.g., the median, the interquartile range), in which
the local sensitivity in the neighborhood of most data does not change much.

For DP-RP studied in our paper, it is easy to check that both the local
sensitivity and smooth sensitivity, at any $u\in[-1,1]^{p}$, are the same as
the global sensitivity by (12) and (13). Thus, for DP-RP, these two concepts
may not help much. Fortunately, for DP-SignRP, the “aggregate-and-sign”
operation brings robustness against small data changes. Therefore, we can
leverage the idea of local or smooth sensitivity to develop novel and better
DP algorithms than the standard bit/sign flipping approach (Section 4.2 and
Section 6).

###  2.3 Relaxation: Individual Differential Privacy (iDP)

Besides the smooth sensitivity framework, many extensions or relaxations of DP
have also been proposed to improve the utility of DP mechanisms. Examples
include concentrated differential privacy (Dwork and Rothblum, 2016), Rényi
differential privacy (Mironov, 2017), and Gaussian differential privacy (Dong
et al., 2022). These alternatives provide less strict requirement on the
“indistinguishability” (11) for privacy and better composition properties than
those of the standard “worst-case” DP, thus reducing the noise needed
(Jayaraman and Evans, 2019). Another possible direction to elevate the
empirical performance of DP is to relax the DP definition by constraining the
scope of neighboring datasets depending on the specific use case of DP (Soria-
Comas et al., 2017; Desfontaines and Pejó, 2020). In this paper, we also
consider the concept called “individual differential privacy” (iDP), also
known as “data-centric DP”, as follows.

######  Definition 2.6 (Individual DP (Soria-Comas et al., 2017)).

Given a dataset $u$, an algorithm $\mathcal{M}$ satisfies
$(\epsilon,\delta)$-iDP for $u$ if for any dataset $u^{\prime}$ that is
adjacent to $u$, it holds that

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

We should emphasize that, individual DP does not satisfy the rigorous DP
definition, as iDP only focuses on the “point-wise” guarantee of privacy. It
protects the neighborhood of a specific dataset of interest, instead of
fulfilling DP requirements for all possible adjacent databases. While
deviating from the standard DP definition, we discuss it in our work because
iDP might be sufficient for some applications, and the utility gain of iDP can
be substantial.

The intuition of iDP is that, while the standard DP (Definition 2.1) requires
indistinguishability between any pair of neighboring databases, in some
practical scenarios, the data custodian only holds one “ground truth” data
vector $u$ that needs to be protected. Limiting the scope of the neighborhood
could be reasonable in certain practical scenarios. For example, for the
centralized data server to (non-interactively) publish the user data matrix or
user embedding vectors to the public, we essentially care about preserving the
privacy of the true user data at hand, as no information other than the
perturbed database would be released. In this paper, while we will mainly
focus on the standard DP definition, we also find that using iDP for sign-
based RP methods provides good utilities. Therefore, we will also discuss iDP-
based variants in Section 6, as it may provide another direction/option for
balancing the trade-off between privacy and utility in practice, based on
specific applications.

##  3 DP-RP: Differentially Private Random Projections

In this section, we study the differentially private random projections (DP-
RP). We first revisit the noise addition mechanisms reported in Kenthapadi et
al. (2013) for Gaussian random projections, an algorithm which we name “DP-
RP-G”. Then we apply the optimal Gaussian mechanism (Balle and Wang, 2018) to
DP-RP to obtain an improved algorithm named “DP-RP-G-OPT”. In Section 5, our
experiments confirm that DP-RP-G-OPT considerably improves DP-RP-G. Moreover,
by replacing the Gaussian projection matrix with the Rademacher projection
matrix, we obtain a further improved version named “DP-RP-G-OPT-B”.
Furthermore, one can obtain another variant called “DP-OPORP” by replacing the
dense Rademacher projections with OPORP, which is a variant of count-sketch
and is computationally much more efficient than dense projections.

We also analytically compare those variants of DP-RP with the basic DP
strategy of directly adding Gaussian noise to each dimension of the original
data vectors. Our analysis explains the improvements by using DP-RP in high-
dimensional data.

###  3.1 Gaussian Noise Mechanism for DP-RP

1 Input: Data $u\in[-1,1]^{p}$, privacy parameters $\epsilon>0$,
$\delta\in(0,1)$, number of projections $k$

2Output: $(\epsilon,\delta)$-differentially private random projections
$\tilde{x}\in\mathbb{R}^{k}$

3Apply RP $x=\frac{1}{\sqrt{k}}W^{T}u$, where $W\in\mathbb{R}^{p\times k}$ has
iid entries sampled from $N(0,1)$

4Compute the sensitivity $\Delta_{2}$ by (13)

5Generate the random noise vector $G\in\mathbb{R}^{k}$ whose entries are iid
samples from $N(0,\sigma^{2})$ where $\sigma$ is obtained by Theorem 3.1 (DP-
RP-G) or Theorem 3.5 (DP-RP-G-OPT)

Return $\tilde{x}=x+G$

Algorithm 1 DP-RP-G and DP-RP-G-OPT

The general Gaussian noise mechanism for DP-RP is detailed in Algorithm 1. We
present the algorithms for a single data point $u$, and the procedure is
applied to every data vector in the database (with same $W$ but independent
noise). Given the projection matrix $W\in\mathbb{R}^{d\times k}$, we first
compute the $l_{2}$-sensitivity $\Delta_{2}$ of the RPs according to (13).
Then we generate the random Gaussian noise vector following iid
$N(0,\sigma^{2})$ where $\sigma$ is derived by Theorem 3.1 below, and output
the projected vector plus the noise. The following Gaussian mechanism for
random projections is known in the literature. We call it the “DP-RP-G”
method.

######  Theorem 3.1 (DP-RP-G (Kenthapadi et al., 2013)).

Let $\Delta_{2}$ be defined in (13). For any $\epsilon>0$ and
$0<\delta<\frac{1}{2}$, DP-RP-G in Algorithm 1 is $(\epsilon,\delta)$-DP if
$\sigma\geq\Delta_{2}\frac{\sqrt{2(\log(1/\delta)+\epsilon)}}{\epsilon}$.

According to Theorem 3.1, one will choose $\sigma$ based on the observed
$\Delta_{2}$ which is calculated according to (13) for a given realization of
the projection matrix $W$. For the convenience of theoretical analysis, it is
often desirable to derive the criterion for choosing $\sigma$ directly in
terms of the input parameters $\epsilon$, $\delta$, $p$, and $k$. We call the
corresponding algorithm to be “Analytic DP-RP-G”. This is achieved by bounding
$\Delta_{2}$ in high probability.

######  Lemma 3.2 (Laurent and Massart (2000)).

Let $Y_{1},...,Y_{n}$ be iid standard Gaussian random variables, and denote
$Z_{i}=\sum_{i=1}^{n}Y_{i}^{2}$. Then for any $t>0$,

$\displaystyle Pr(Z\geq n+2\sqrt{nt}+2t)\leq\exp(-t).$

######  Lemma 3.3 (Bounding $\Delta_{2}$).

Let $W\in\mathbb{R}^{p\times k}$ be a random matrix with iid $N(0,1)$ entries,
and $\Delta_{2}$ be defined in (13). Then for any $0<\delta<1$,

$\displaystyle
Pr\left(\Delta_{2}\geq\beta\sqrt{1+2\sqrt{\log(p/\delta)/k}+2\log(p/\delta)/k}\right)\leq\delta.$

###### Proof.

Let $e_{i}$ be the unit base vector with the $i$-th dimension being $1$ and
all other dimensions being zero. For each $i=1,...,p$, $W^{T}e_{i}$ follows
iid chi-square distribution with $k$ degree of freedom. Applying Lemma 3.2 we
have that for any $\delta^{\prime}>0$,

$\displaystyle Pr\left(\|W^{T}e_{i}\|^{2}\geq
k+2\sqrt{k\log(1/\delta^{\prime})}+2\log(1/\delta^{\prime})\right)\leq\delta^{\prime},\
\ \forall i=1,...,p.$

Applying union bound gives

$\displaystyle
Pr\left(\frac{1}{k}\beta^{2}\max_{i=1,...,p}\|W^{T}e_{i}\|^{2}\geq\beta^{2}\left(1+2\sqrt{\log(1/\delta^{\prime})/k}+2\log(1/\delta^{\prime})/k\right)\right)\leq
p\delta^{\prime}.$

Setting $\delta=p\delta^{\prime}$ and taking the square root on both sides
completes the proof. ∎

With the high probability bound on the $l_{2}$-sensitivity $\Delta_{2}$, we
have the following result.

######  Theorem 3.4 (Analytic DP-RP-G).

For any $\epsilon>0$ and $0<\delta<\frac{1}{2}$, Algorithm 1 achieves
$(\epsilon,\delta)$-DP when
$\sigma\geq\frac{\beta\sqrt{1+2\sqrt{\log(2p/\delta)/k}+2\log(2p/\delta)/k}\sqrt{2(\log(2/\delta)+\epsilon)}}{\epsilon}$.

###### Proof.

By Lemma 3.3, with probability $\delta/2$, $\Delta_{2}$ is bounded by
$\beta\sqrt{1+2\sqrt{\log(2p/\delta)/k}+2\log(2p/\delta)/k}$. In this event,
by Theorem 3.1, Algorithm 1 is $(\epsilon,\delta/2)$-DP when
$\sigma\geq\Delta_{2}\frac{\sqrt{2(\log(2/\delta)+\epsilon)}}{\epsilon}$.
Therefore, the approach is $(\epsilon,\delta)$-DP. ∎

We remark that, since this analytic version is built upon a high probability
bound on the sensitivity, in most cases, the noise variance in Theorem 3.4
will be slightly larger than the one computed by the realized/exact
sensitivity in Theorem 3.1.

###  3.2 The Optimal Gaussian Noise Mechanism for DP-RP

In Theorem 3.1 (as well as the classical Gaussian mechanism, e.g., Dwork and
Roth (2014)), the analysis on the noise level is based on upper bounding the
tail of Gaussian distribution444More specifically, the analysis of the classic
Gaussian mechanism is based on bounding the probability of
$X=\log\frac{p_{\mathcal{M}(u)}(y)}{p_{\mathcal{M}(u^{\prime})}(y)}\geq\epsilon$,
where $u$ and $u^{\prime}$ are neighboring databases and $y$ is an output.
$X$, called the privacy loss random variable, is shown to follow a Gaussian
distribution (Dwork and Rothblum, 2016) when the injected noise is Gaussian.
The tail probability of $X$ is then bounded by standard concentration
inequalities.. While the noise level in Theorem 3.1 is rate optimal (see
Remark 3.1), it can be improved by computing the exact tail probabilities
instead of the upper bounds. Balle and Wang (2018, Theorem 8) proposed the
optimal Gaussian mechanism based on this idea, using which allows us to
improve Theorem 3.1 and obtain the optimal DP-RP-Gaussian-Noise (DP-RP-G-OPT)
method as follows.

######  Theorem 3.5 (DP-RP-G-OPT).

Suppose $\Delta_{2}$ is defined as (13). For any $\epsilon>0$ and
$0<\delta<1$, DP-RP-G-OPT in Algorithm 1 achieves $(\epsilon,\delta)$-DP if
$\sigma\geq\sigma^{*}$ where $\sigma^{*}$ is the solution to the equation

$\displaystyle\Phi\left(\frac{\Delta_{2}}{2\sigma}-\frac{\epsilon\sigma}{\Delta_{2}}\right)-e^{\epsilon}\Phi\left(-\frac{\Delta_{2}}{2\sigma}-\frac{\epsilon\sigma}{\Delta_{2}}\right)=\delta,$
(14)

where $\Phi(\cdot)$ is the cumulative distribution function (cdf) of the
standard normal distribution.

######  Remark 3.1.

For both Theorem 3.5 and Theorem 3.1, the Gaussian noise level is
$\sigma=\mathcal{O}(\frac{\Delta_{2}}{\epsilon})=\mathcal{O}(\frac{1}{\epsilon})$
when $\epsilon$ is small (i.e., $\epsilon\rightarrow 0$), and
$\sigma=\mathcal{O}(\frac{1}{\sqrt{\epsilon}})$ when $\epsilon$ is large
(i.e., $\epsilon\rightarrow\infty$). This is rate optimal as Gaussian
mechanism must incur a noise
$\sigma=\Omega(\frac{\Delta_{2}}{\sqrt{\epsilon}})$ when
$\epsilon\rightarrow\infty$ (Balle and Wang, 2018). Theorem 3.5 reduces the
variance of Theorem 3.1 by analyzing the tail probability exactly.

Figure 1: Left panel: the optimal Gaussian noise $\sigma$ versus $\epsilon$
for a series of $\Delta_{2}$ values, by solving the nonlinear equation (14) in
Theorem 3.5, for $\delta=10^{-6}$. Right panel: the optimal Gaussian noise
$\sigma$ versus $\Delta_{2}$ for a series of $\epsilon$ values.

###  3.3 The Laplace Noise Mechanism for DP-RP

1 Input: Data $u\in[-1,1]^{p}$, privacy parameters $\epsilon>0$, number of
projections $k$

2Output: $\epsilon$-differentially private random projections
$\tilde{x}\in\mathbb{R}^{k}$

3Apply RP $x=\frac{1}{\sqrt{k}}W^{T}u$, where $W\in\mathbb{R}^{p\times k}$ is
a random $N(0,1)$ matrix

4Compute sensitivity $\Delta_{1}$ by (12)

5Generate iid random noise vector $L\in\mathbb{R}^{k}$ following
$Laplace(\frac{\Delta_{1}}{\epsilon})$

Return $\tilde{x}=x+L$

Algorithm 2 DP-RP-L

By Theorem 2.1, one may add $Laplace(\lambda)$ noise to the projected data
with $\lambda=\Delta_{1}/\epsilon$ to achieve $\epsilon$-DP. For completeness,
we detail the approach in Algorithm 2, which is the same as Algorithm 1 except
for the noise added. $\Delta_{1}$ is the $l_{1}$-sensitivity for a given $W$
given in (12):
$\Delta_{1}=\frac{1}{\sqrt{k}}\beta\max_{i=1,...,p}\|W_{[i,:]}\|_{1}$. Each
term in the maximum operator is a sum of $k$ iid standard half-normal random
variables ($Y=|X|$ where $X$ is standard normal). The readers might be
interested in a comparison between the noise level of the two noise addition
mechanisms, i.e., DP-RP-G and DP-RP-L. To observe the dependence of the noise
level $\lambda$ on $\epsilon$, $k$ and $p$, we derive a tail bound on the
$l_{1}$-sensitivity. We first establish the following lemma.

######  Lemma 3.6 (Half-normal tail bound).

Let $X_{1},...,X_{n}$ be iid $N(0,1)$ random variables and let
$Y_{i}=|X_{i}|$, $\forall i$. Denote $Z=\sum_{i=1}^{n}Y_{i}$. Then for any
$t>0$, it holds that

$\displaystyle Pr(Z\geq\sqrt{2n^{2}\log 2+2nt})\leq\exp(-t).$

Using Lemma 3.6, we obtain a high probability bound on the $l_{1}$-sensitivity
as follows. The proof is omitted since it is similar to the proof of Lemma
3.3.

######  Lemma 3.7 (Bounding $\Delta_{1}$).

Let $W\in\mathbb{R}^{p\times k}$ be a random matrix with iid $N(0,1)$ entries,
and $\Delta_{1}$ be defined in (12). Then for any $0<\delta<1$,

$\displaystyle Pr\left(\Delta_{1}\geq\beta\sqrt{2k\log
2+2\log(p/\delta)}\right)\leq\delta.$

It is important to point out that, unlike in the Gaussian mechanism, simply
inserting the upper bound in Lemma 3.7 to replace the (exact) $\Delta_{1}$ in
the noise level of $Laplace(\Delta_{1}/\epsilon)$ in Algorithm 2 does not
provide pure $\epsilon$-DP. In other words, we must compute the actual
$\Delta_{1}$ by (12) for a realization of the projection matrix $W$. This is
because, using the high probability bound of $\Delta_{1}$ would introduce a
failure probability (i.e., when the actual $\Delta_{1}$ is larger than the
bound) which violates $\epsilon$-DP.

Comparison with DP-RP-G-OPT. Lemma 3.7 provides an estimate of the noise level
required by the Laplace mechanism. We can roughly compare DP-RP-L with DP-RP-
OPT in terms of the noise variances, which equal $\sigma^{2}$ for Gaussian and
$2\lambda^{2}$ for Laplace, respectively. Lemma 3.7 shows that in most cases,
the Laplace noise requires $\lambda=\mathcal{O}(\frac{\sqrt{k}}{\epsilon})$.
Recall that in DP-RP-G and DP-RP-G-OPT, the Gaussian noise level
$\sigma=\mathcal{O}(\frac{1}{\epsilon})$ when $\epsilon\rightarrow 0$ and
$\sigma=\mathcal{O}(\frac{1}{\sqrt{\epsilon}})$ when
$\epsilon\rightarrow\infty$. Thus, the Gaussian noise would be smaller with
relatively small $\epsilon$, and the Laplace noise would be smaller only when
$\epsilon=\Omega(k)$, which is usually too large to be useful since in
practice $k$ is usually hundreds to thousands. As a result, we would expect
DP-RP-G methods to perform better than DP-RP-L in common scenarios. Therefore,
in the remaining parts of the paper, we will mainly focus on the Gaussian
mechanism for noise addition.

###  3.4 DP-RP-G-OPT-B: DP-RP with Rademacher Projections

We have considered the Gaussian random projections. We can also adopt other
types of projection matrices which might even work better for DP. The
following distributions of $w_{ij}$ are popular:

  * •

The uniform distribution, $\sqrt{3}\times unif[-1,1]$. The $\sqrt{3}$ factor
is placed here to have $\mathbb{E}(w_{ij}^{2})=1$ by following the convention
in the practice of random projections.

  * •

The “very sparse” distribution, as used in Li et al. (2006):

$\displaystyle w_{ij}=\sqrt{s}\times\left\\{\begin{array}[]{rrl}-1&\text{with
prob.}&1/(2s)\\\ 0&\text{with prob.}&1-1/s,\\\ +1&\text{with
prob.}&1/(2s)\end{array}\right.$ (18)

which generalizes Achlioptas (2003) (for $s=1$ and $s=3$). Note that when
$s=1$, it is also called the “symmetric Bernoulli” distribution or the
“Rademacher” distribution.

From Theorem 3.1 and Theorem 3.5, it is clear that the noise magnitude of
Gaussian noise in DP-RP directly depends on the $l_{2}$-sensitivity
$\Delta_{2}$, which, according to (13), equals the largest row norm of the
projection matrix $W$. Among the above-mentioned distributions, the dense
Rademacher projection ($s=1$ in (18)) has
$\Delta_{2}=\frac{1}{\sqrt{k}}\beta\times\sqrt{k}=\beta$ which is independent
of $p$. This could be much smaller than the dense Gaussian projection (i.e.,
DP-RP-G-OPT) as can be seen from the bound in Lemma 3.3).

Figure 2: The $l_{2}$-sensitivity $\Delta_{2}$ (13) for different types of
random projection matrices against the data dimensionality $p$, at $k=256$ and
$k=512$, respectively. $\beta=1$.

In Figure 2, we numerically simulate the $\Delta_{2}$ of different projection
matrices, which shows that the Rademacher projection produces the smallest
sensitivity. This, when plugged into the optimal Gaussian mechanism (Theorem
3.5), leads to smaller Gaussian noise variance needed. For clarity, we
summarize the DP-RP based on Rademacher projections in Algorithm 3. We name it
“DP-RP-G-OPT-B”, where “G” stands for the Gaussian noise mechanism and “B”
stands for “symmetric Bernoulli” projections.

1 Input: Data $u\in[-1,1]^{p}$, privacy parameters $\epsilon>0$,
$\delta\in(0,1)$, number of projections $k$

2Output: $(\epsilon,\delta)$-differentially private random projections
$\tilde{x}\in\mathbb{R}^{k}$

3Apply RP $x=\frac{1}{\sqrt{k}}W^{T}u$, where $W\in\mathbb{R}^{p\times k}$ is
a random Rademacher matrix

4Generate iid random noise vector $G\in\mathbb{R}^{k}$ following
$N(0,\sigma^{2})$ where $\sigma$ is obtained by Theorem 3.5 with
$\Delta_{2}=\beta$

Return $\tilde{x}=x+G$

Algorithm 3 DP-RP-G-OPT-B

Does the reduction in noise magnitude translate into better utility? We first
provide an approximate assessment as follows. Note that when the data
$u\in[-1,1]^{p}$ is not too sparse, the distribution of
$\sum_{i=1}^{p}w_{i}u_{i}$, where $w_{i}$ follows Rademacher distribution, is
asymptotically normal according to the Central Limit Theorem (CLT), with mean
$0$ and variance $\|u\|^{2}$. This distribution is the same as the
distribution of $\sum_{i=1}^{p}w_{i}u_{i}$ when $w_{i}$ is from $N(0,1)$.
Therefore, we may expect the projected data of Gaussian RP and Rademacher RP
to have similar magnitude. Hence, the signal-to-noise ratio (SNR) of DP-RP-G-
OPT-B using Rademacher projections would be higher than that of DP-RP-G-OPT
using Gaussian projections, as a result of the smaller noise level. An
analytical comparison in terms of inner product estimation variance will be
given in Section 3.6.

###  3.5 DP-OPORP: A More Efficient Alternative

The standard random projection (3) requires $k$ projections which takes
$O(kp)$ complexity. We can reduce the cost to $O(p)$ by the idea of “binning +
RP”. Basically, we split the data entries into $k$ bins, and apply RP in each
bin to generate $k$ samples. Zhao et al. (2022) studied noise injection
mechanism for count-sketch. Recently, Li and Li (2023a) proposed OPORP (One
Permutation + One Random Projection), an improved variant of count-sketch
(Charikar et al., 2004), by using fixed-length binning and normalization. The
steps of OPORP for a data vector $u$ are summarized in Algorithm 4 (for
convenience, assume $p$ can be integer divided by $k$).

1 Input: Data vector $u\in\mathbb{R}^{p}$, number of projected samples $k$

2Output: $k$ OPORP samples

3Apply a permutation $\Pi:[p]\mapsto[p]$ to $u$ to get $u_{\Pi}$

4Split the $p$ permuted data columns (features) into $k$ consecutive fixed-
length bins each containing $p/k$ features:
$u_{\Pi}=[u_{\Pi}^{(1)},...,u_{\Pi}^{(k)}]$

5Generate one projection vector $w\in\mathbb{R}^{p}$ following a proper
probability distribution (see Section 3.4). Denote it as a concatenation of
bins $w=[w^{(1)},...,w^{(k)}]$

Return $k$ projected samples by $x_{i}={w^{(i)}}^{T}u_{\Pi}^{(i)}$, for
$i=1,...,k$.

Algorithm 4 OPORP: count-sketch with fixed-length binning and normalization.

Note that the same permutation $\Pi$ and projection vector $w$ should be used
to process all the data vectors. Let $x_{i}$ be an OPORP of $u$, and $y_{i}$
be an OPORP of $v$. It can be shown that $\mathbb{E}[x_{i}y_{i}]=u^{T}v$,
i.e., OPORP provides an unbiased estimator of the inner product. Regarding the
estimation variance, note that in step 2, OPORP deploys a fixed-length binning
scheme; in prior works, the lengths of the bins are random and follow a
multinomial distribution. Li and Li (2023a) showed that fixed-length binning
can reduce the inner product and cosine estimation variance of variable-length
binning, by a factor of $\frac{p-k}{p-1}$, when the projection vector follows
the symmetric Bernoulli (Rademacher) distribution (see (18)). Furthermore, the
estimation variance can be substantially reduced by normalizing the output
vector of OPORP. It was also shown by Li and Li (2023a) that one can
substantially improve the estimates of “very sparse random projections” via
the same normalization technique.

Next, we consider the differential privacy of OPORP and propose DP-OPORP
analogously, as given in Algorithm 5. Since we have shown that Gaussian noise
would be better than Laplace noise in most cases for DP-SignRP (see Section
3.3), we present the optimal Gaussian noise mechanism here for conciseness.
Also, while one may choose any projection vector $w$ in OPORP (Algorithm 4),
Li and Li (2023a) showed that the Rademacher projection gives the smallest
cosine and inner product estimation variance. Hence, we adopt the Rademacher
projection in DP-OPORP.

1 Input: Data $u\in[-1,1]^{p}$, privacy parameters $\epsilon>0$,
$\delta\in(0,1)$, number of projections $k$

2Output: Differentially private OPORP

3Apply Algorithm 4 with a random Rademacher projection vector to obtain the
OPORP $x$

4Set sensitivity $\Delta_{2}=\beta$

5Generate iid random vector $G\in\mathbb{R}^{k}$ following $N(0,\sigma^{2})$
where $\sigma$ is computed by Theorem 3.5

Return $\tilde{x}=x+G$

Algorithm 5 DP-OPORP

In Algorithm 5, we formalize the DP-OPORP method. It is a variant of DP-RP-G-
OPT-B, where Gaussian noise is added to the OPORP. Note that the sensitivity
$\Delta_{2}=\beta$, due to the nature of OPORP: changing the data $u$ by
$\beta$ (Definition 2.3) would lead to at most $\beta$ change in $x$ in term
of $l_{2}$ distance. Note that, if we directly add noise to each dimension of
the original data, then the sensitivity by definition
$\Delta_{2}=\max_{(u,u^{\prime})\in\mathcal{N}(\mathcal{U})}\|f(u)-f(u^{\prime})\|_{2}$
is also $\beta$.

###  3.6 Comparison: Inner Product Estimation

We now analytically compare different DP algorithms, in terms of inner product
estimation. Here for simplicity, we assume the data are normalized, i.e., the
data vector has $l_{2}$ norm equal to 1. In this case, the inner product is
also the cosine. The baseline method is the most straightforward: we add
optimal Gaussian noise to each dimension of the original data (Raw-data-G-
OPT). As mentioned earlier, the sensitivity is also $\Delta_{2}=\beta$. This
means, when we compare all three methods: Raw-data-G-OPT, DP-RP-G-OPT-B, and
DP-OPORP, the noise level $\sigma$ is the same. This makes it convenient to
conduct the comparisons, from which we can gain valuable insights.

######  Theorem 3.8 (Raw-data-G-OPT, i.e., adding optimal Gaussian noise on
raw data).

Let $\sigma$ be the solution to (14) with $\Delta_{2}=\beta$. For any
$u,v\in\mathcal{U}$, let $\tilde{u}_{i}=u_{i}+a_{i}$ and
$\tilde{v}_{i}=v_{i}+b_{i}$ be the DP noisy vectors, with $a_{i},b_{i}\sim
N(0,\sigma^{2})$ i.i.d. Then, denote
$\hat{g}_{org}=\sum_{i=1}^{p}\tilde{u}_{i}\tilde{v}_{i}$. we have

$\displaystyle\mathbb{E}[\hat{g}_{org}]=\sum_{i=1}^{p}u_{i}v_{i},\hskip
21.68121ptVar\left(\hat{g}_{org}\right)=\sigma^{2}\sum_{i=1}^{p}\left(u_{i}^{2}+v_{i}^{2}\right)+p\sigma^{4}.$
(19)

###### Proof.

To add Gaussian noise to the original data, it suffices to find the
sensitivity, which, by Definition 2.3, is $\Delta_{2}=\beta$. Thus, the
approach is $(\epsilon,\delta)$-DP according to the optimal Gaussian mechanism
(Theorem 3.5). To compute the mean and variance, consider some $i\in[p]$. We
have

$\displaystyle\mathbb{E}\left[\left(u_{i}+a_{i}\right)\left(v_{i}+b_{i}\right)\right]=\mathbb{E}[u_{i}v_{i}+a_{i}v_{i}+b_{i}u_{i}+a_{i}b_{i}]=u_{i}v_{i}.$

Thus, taking the sum implies
$\mathbb{E}[\hat{g}_{org}]=\sum_{i=1}^{p}u_{i}v_{i}$. For the variance,

$\displaystyle\mathbb{E}\left[\left(u_{i}+a_{i}\right)\left(v_{i}+b_{i}\right)\right]^{2}=\mathbb{E}[u_{i}v_{i}+a_{i}v_{i}+b_{i}u_{i}+a_{i}b_{i}]^{2}=u_{i}^{2}v_{i}^{2}+\sigma^{2}\left(u_{i}^{2}+v_{i}^{2}\right)+\sigma^{4},$

which leads to

$\displaystyle
Var\left(\left(u_{i}+a_{i}\right)\left(v_{i}+b_{i}\right)\right)=\sigma^{2}\left(u_{i}^{2}+v_{i}^{2}\right)+\sigma^{4}.$

Therefore, by independence,

$\displaystyle
Var\left(\hat{g}_{org}\right)=Var\left(\sum_{i=1}^{p}\left(u_{i}+a_{i}\right)\left(v_{i}+b_{i}\right)\right)$
$\displaystyle=\sigma^{2}\sum_{i=1}^{p}\left(u_{i}^{2}+v_{i}^{2}\right)+p\sigma^{4},$

which proves the claim. ∎

For DP-RP-G-OPT-B and DP-OPORP, we have the following results.

######  Theorem 3.9 (DP-RP-G-OPT-B inner product estimation).

Let $\sigma$ be the solution to (14) with $\Delta_{2}=\beta$. In Algorithm 3,
let $W\in\\{-1,1\\}^{p\times k}$ be a Rademacher random matrix. Denote
$x=\frac{1}{\sqrt{k}}W^{T}u$, $y=\frac{1}{\sqrt{k}}W^{T}v$, and $a$, $b$ are
two random Gaussian noise vectors following $N(0,\sigma^{2})$. Let
$\hat{g}_{rp}=\sum_{j=1}^{k}(x_{j}+a_{j})(y_{j}+b_{j})$. Then,
$\mathbb{E}[\hat{g}_{rp}]=\sum_{i=1}^{p}u_{i}v_{i}$, and

$\displaystyle
Var\left(\hat{g}_{rp}\right)=\sigma^{2}\sum_{i=1}^{p}\left(u_{i}^{2}+v_{i}^{2}\right)+k\sigma^{4}+\frac{1}{k}\left(\sum_{i=1}^{p}u_{i}^{2}\sum_{i=1}^{p}v_{i}^{2}+\left(\sum_{i=1}^{p}u_{i}v_{i}\right)^{2}-2\sum_{i=1}^{p}u_{i}^{2}v_{i}^{2}\right).$
(20)

###### Proof.

The conditional mean and variance can be computed as

$\displaystyle\mathbb{E}\left[\sum_{j=1}^{k}\left(x_{j}+a_{j}\right)\left(y_{j}+b_{j}\right)|x_{j},y_{j},j=1,...,k\right]=\sum_{j=1}^{k}x_{j}y_{j},$
$\displaystyle
Var\left(\sum_{j=1}^{k}\left(x_{j}+a_{j}\right)\left(y_{j}+b_{j}\right)|x_{j},y_{j},j=1,...,k\right)=\sigma^{2}\sum_{j=1}^{k}(x_{j}^{2}+y_{j}^{2})+k\sigma^{4},$

where the variance calculation follows from Theorem 3.8. Hence, we have

$\displaystyle\mathbb{E}\left[\sum_{j=1}^{k}\left(x_{j}+a_{j}\right)\left(y_{j}+b_{j}\right)\right]=\mathbb{E}\left[\sum_{j=1}^{k}x_{j}y_{j}\right]=\sum_{i=1}^{p}u_{i}v_{i},$
$\displaystyle Var\left(\hat{g}_{rp}\right)=$
$\displaystyle\mathbb{E}\left[\sigma^{2}\sum_{j=1}^{k}(x_{j}^{2}+y_{j}^{2})+k\sigma^{4}\right]+Var\left(\sum_{j=1}^{k}x_{j}y_{j}\right)$
$\displaystyle=$
$\displaystyle\sigma^{2}\sum_{i=1}^{p}\left(u_{i}^{2}+v_{i}^{2}\right)+k\sigma^{4}+\frac{1}{k}\left(\sum_{i=1}^{p}u_{i}^{2}\sum_{i=1}^{p}v_{i}^{2}+\left(\sum_{i=1}^{p}u_{i}v_{i}\right)^{2}-2\sum_{i=1}^{p}u_{i}^{2}v_{i}^{2}\right).$
(21)

In the above calculation, the formula of
$Var\left(\sum_{j=1}^{k}x_{j}y_{j}\right)$ is from the result in Li et al.
(2006) with $s=1$ for Rademacher distribution. ∎

######  Theorem 3.10 (DP-OPORP inner product estimation).

Let $\sigma$ be the solution to (14) with $\Delta_{2}=\beta$. Let
$w\in\\{-1,1\\}^{p}$ be a Rademacher random vector. In Algorithm 5, let $x$
and $y$ be the OPORP of $u$ and $v$, and $a$, $b$ be two random Gaussian noise
vectors following $N(0,\sigma^{2})$. Denote
$\hat{g}_{oporp}=\sum_{j=1}^{k}(x_{j}+a_{j})(y_{j}+b_{j})$. Then,
$\mathbb{E}[\hat{g}_{oporp}]=\sum_{i=1}^{p}u_{i}v_{i}$, and

$\displaystyle
Var\left(\hat{g}_{oporp}\right)=\sigma^{2}\sum_{i=1}^{p}\left(u_{i}^{2}+v_{i}^{2}\right)+k\sigma^{4}+\frac{1}{k}\left(\sum_{i=1}^{p}u_{i}^{2}\sum_{i=1}^{p}v_{i}^{2}+\left(\sum_{i=1}^{p}u_{i}v_{i}\right)^{2}-2\sum_{i=1}^{p}u_{i}^{2}v_{i}^{2}\right)\frac{p-k}{p-1}.$
(22)

###### Proof.

The proof is similar to that of Theorem 3.9, with the help of the result in Li
and Li (2023a). ∎

The variance reduction factor $\frac{p-k}{p-1}$ can be quite beneficial when
$p$ is not very large. Also, see Li and Li (2023a) for the normalized
estimators for both OPORP and VSRP (very sparse random projections). The
normalization steps can substantially reduce the estimation variance.

Comparison. For the convenience of comparison, let us assume that the data are
row-normalized, i.e., $\|u\|^{2}=1$ for all $u\in\mathcal{U}$. Let
$\rho=\sum_{i=1}^{p}u_{i}v_{i}$. We have

$\displaystyle Var\left(\hat{g}_{org}\right)=2\sigma^{2}+p\sigma^{4},$
$\displaystyle
Var\left(\hat{g}_{rp}\right)=2\sigma^{2}+k\sigma^{4}+\frac{1}{k}\left(1+\rho^{2}-2\sum_{i=1}^{p}u_{i}^{2}v_{i}^{2}\right),$
$\displaystyle
Var\left(\hat{g}_{oporp}\right)=2\sigma^{2}+k\sigma^{4}+\frac{1}{k}\left(1+\rho^{2}-2\sum_{i=1}^{p}u_{i}^{2}v_{i}^{2}\right)\frac{p-k}{p-1}.$

For high-dimensional data (large $p$), we see that $\hat{g}_{rp}$ and
$\hat{g}_{oporp}$ has roughly the same variance, approximately
$2\sigma^{2}+k\sigma^{4}+\frac{1}{k}$. We would like to compare this with
$Var\left(\hat{g}_{org}\right)=2\sigma^{2}+p\sigma^{4}$ the variance for
adding noise directly to the original data.

Let’s define the ratio of the variances:

$\displaystyle
R=\frac{2\sigma^{2}+p\sigma^{4}}{2\sigma^{2}+k\sigma^{4}+\frac{1}{k}}\sim\frac{p\sigma^{4}}{k\sigma^{4}}=\frac{p}{k}\
\ (\text{if }p\text{ is large or }\sigma\text{ is high})$ (23)

to illustrate the benefit of RP-type algorithms (DP-RP and DP-OPORP) in
protecting the privacy of the (high-dimensional) data. If $\frac{p}{k}=100$,
then it is possible that the ratio of the variances can be roughly 100. This
would be a huge advantage. Figure 3 plots the ratio $R$ for $p=1000$ and
$p=10000$ as well as a series of $k/p$ values, with respect to $\sigma$.

Figure 3: We plot the ratio of variances in (23) for $p=1000$ and $p=10000$.
We choose $k$ values with $k/p\in\\{0.01,0.05,0.1,0.5\\}$. Then for any
$\sigma$ value, we are able to compute the ratio $R$. For larger $\sigma$, we
have $R\sim\frac{p}{k}$ as expected. See Figure 1 for the relationship among
$\sigma$, $\Delta$, and $\epsilon$ (and $\delta$).

Figure 3 also illustrates when it might be a good strategy to directly add
noise to the original data. For example, when $p=1000$, the ratio can be below
1 if $\sigma<0.1$. Figure 1 depicts the relationship among $\sigma$, $\Delta$,
and $\epsilon$ (and $\delta$). One can verify that, in order for $\sigma<0.1$
at $\Delta_{2}=\beta=1$, we need $\epsilon>100$. In the literature, many DP
applications typically require a much smaller $\epsilon$, such as
$\epsilon\in[0.1,20]$ (e.g., Haeberlen and Khanna (2014); Kenny et al.
(2021)).

##  4 DP-SignRP: Differentially Private Sign Random Projections

We have reviewed in the Introduction the advantage of sign random projections
(SignRP) (in terms of storage, communications, and computations). In this
section, we propose algorithms that output SignRP with differential privacy
guarantees. The straightforward approach is directly taking the signs of DP-RP
methods, e.g., from Algorithm 1 or Algorithm 3. By the post-processing
property of DP, the resultant signs are also DP. In our study, we focus on
algorithms that randomize the signs (bit-vector) of the non-private RPs. That
is, we first generate non-private SignRP, and then perturb the bits.

In the following, we first study the DP-SignRP from Gaussian random
projections. Then we demonstrate the use of Rademacher projections for
improving the performance. Finally, we propose algorithms for DP-SignOPORP and
discuss its advantages in terms of privacy protection.

###  4.1 DP-SignRP-RR by Randomized Response

1 Input: Data $u\in[-1,1]^{p}$; $\epsilon>0$, $0<\delta<1$, number of
projections $k$, norm lower bound $m$

2

3Output: Differentially private sign random projections

4

5Apply RP by $x=\frac{1}{\sqrt{k}}W^{T}u$, where $W\in\mathbb{R}^{p\times k}$
is a random $N(0,1)$ matrix

6Let $N_{+}(m,\delta,k,p)$ be computed as (27) in Proposition 4.5

7Compute $\tilde{s}_{j}=\begin{cases}sign(x_{j}),&\text{with prob.}\
\frac{e^{\epsilon^{\prime}}}{e^{\epsilon^{\prime}}+1}\\\
-sign(x_{j}),&\text{with prob.}\ \frac{1}{e^{\epsilon^{\prime}}+1}\end{cases}$
for $j=1,...,k$, with $\epsilon^{\prime}=\epsilon/N_{+}(m,\delta,k,p)$

Return $\tilde{s}$ as the DP-SignRP of $u$

Algorithm 6 DP-SignRP-RR

Firstly, we develop a DP algorithm for SignRP based on the classic randomized
response (RR) technique (Warner, 1965; Dwork and Roth, 2014) and call it DP-
SignRP-RR. As summarized in Algorithm 6, after we apply random projection
$x=\frac{1}{\sqrt{k}}W^{T}u$, we take $s=sign(x)$. Then, for each $s_{j}$, we
keep the sign with probability
$\frac{e^{\epsilon^{\prime}}}{e^{\epsilon^{\prime}}+1}$ and flip the sign with
probability $\frac{1}{e^{\epsilon^{\prime}}+1}$. Here
$\epsilon^{\prime}=\epsilon/N_{+}$, where $N_{+}(m,\delta,k,p)$ is an upper
bound on the number of different signs (among $k$ signs) of
$x=\frac{1}{\sqrt{k}}W^{T}u$ and $x=\frac{1}{\sqrt{k}}W^{T}u^{\prime}$ for any
$\beta$-adjacent $(u,u^{\prime})$, which will be derived later in Proposition
4.5. The final output is $\tilde{s}$ after perturbing $s$ by the above
procedure. Note that, in Algorithm 6, in order to achieve differential
privacy, we additionally assume that there exists a lower bound on the $l_{2}$
norm of the data, i.e., $\|u\|\geq m$ for all $u$ in the data domain. We have
the following privacy guarantee as a Theorem.

######  Theorem 4.1.

Algorithm 6 is $(\epsilon,\delta)$-DP.

######  Remark 4.1.

If we do not assume a lower bound on the data norm (i.e., $m=0$), then
$N_{+}=k$. That is, we need to set $\epsilon^{\prime}=\epsilon/k$ in Algorithm
6, and the algorithm becomes $\epsilon$-DP.

###### Proof.

For any data point $u\in\mathcal{U}$ and its $\beta$-adjacent neighbor
$u^{\prime}$, denote $s=sign(W^{T}u)\in\\{-1,+1\\}^{k}$,
$s^{\prime}=sign(W^{T}u^{\prime})\in\\{-1,+1\\}^{k}$, and let $\tilde{s}$ and
$\tilde{s}^{\prime}$ be the corresponding randomized sign vectors output by
Algorithm 6. Denote $S=\\{i:s_{j}\neq s_{j}^{\prime}\\}$ and
$S^{c}=[k]\setminus S$. For any vector $y\in\\{-1,+1\\}^{k}$, define
$S_{0}=\\{j\in S:s_{j}=y_{j}\\}$, $S_{1}=\\{j\in S:s_{j}\neq y_{j}\\}$,
$S^{c}_{0}=\\{j\in S^{c}:s_{j}=y_{j}\\}$ and $S^{c}_{1}=\\{j\in
S^{c}:s_{j}\neq y_{j}\\}$. By Proposition 4.5, we know that the event
$\\{|S|\leq N_{+}(m,\delta,k,p)\\}$ happens with probability at least
$1-\delta$. In this event, we have

$\displaystyle\log\frac{Pr(\tilde{s}=y)}{Pr(\tilde{s}^{\prime}=y)}$
$\displaystyle=\log\frac{\prod_{j\in
S^{c}_{0}}\frac{e^{\epsilon^{\prime}}}{e^{\epsilon^{\prime}}+1}\prod_{j\in
S^{c}_{1}}\frac{1}{e^{\epsilon^{\prime}}+1}\prod_{j\in
S_{0}}\frac{e^{\epsilon^{\prime}}}{e^{\epsilon^{\prime}}+1}\prod_{j\in
S_{1}}\frac{1}{e^{\epsilon^{\prime}}+1}}{\prod_{j\in
S^{c}_{0}}\frac{e^{\epsilon^{\prime}}}{e^{\epsilon^{\prime}}+1}\prod_{j\in
S^{c}_{1}}\frac{1}{e^{\epsilon^{\prime}}+1}\prod_{j\in
S_{0}}\frac{1}{e^{\epsilon^{\prime}}+1}\prod_{j\in
S_{1}}\frac{e^{\epsilon^{\prime}}}{e^{\epsilon^{\prime}}+1}}$
$\displaystyle\leq\log\frac{\prod_{j\in
S}\frac{e^{\epsilon^{\prime}}}{e^{\epsilon^{\prime}}+1}}{\prod_{j\in
S}\frac{1}{e^{\epsilon^{\prime}}+1}}=|S|\epsilon^{\prime}\leq
N_{+}\epsilon^{\prime}=\epsilon.$

Since this event occurs with probability at least $1-\delta$, the overall
procedure is $(\epsilon,\delta)$-DP. ∎

####  4.1.1 The flipping probability and calculation of $N_{+}$

As in the proof of Theorem 4.1, $N_{+}$ is the upper bound on
$S=\\{i:s_{j}\neq s_{j}^{\prime}\\}$, where $s=sign(W^{T}u)\in\\{-1,+1\\}^{k}$
and $s^{\prime}=sign(W^{T}u^{\prime})\in\\{-1,+1\\}^{k}$ for neighboring data
vectors $(u,u^{\prime})$. $N_{+}$ also determines the flipping probability in
DP-SignRP-RR, which is important for the utility. Next, we analyze $N_{+}$.
The following is a useful lemma that describes some statistical properties of
the absolute value of bivariate normal random variables, which might be of
independent interest. The proof can be found in Appendix.

######  Lemma 4.2.

Let $\begin{pmatrix}X\\\ Y\end{pmatrix}\sim
N\begin{pmatrix}\sigma_{x}^{2}&\rho\sigma_{x}\sigma_{y}\\\
\rho\sigma_{x}\sigma_{y}&\sigma_{y}^{2}\end{pmatrix}$. Denote
$r=\sigma_{x}/\sigma_{y}$. Then we have:

1\.
$Pr(|X|>|Y|)=\frac{1}{\pi}\left[\tan^{-1}\left(\frac{r-\rho}{\sqrt{1-\rho^{2}}}\right)+\tan^{-1}\left(\frac{r+\rho}{\sqrt{1-\rho^{2}}}\right)\right]$.
When $r\leq 1$, the maximum is achieved at $\rho=0$, i.e.,
$\max_{\rho}Pr(|X|<|Y|)=\frac{2}{\pi}\tan^{-1}(r)$.

2\. The conditional expectation:

$\displaystyle\mathbb{E}\left[|X|\big{|}|X|>|Y|\right]=\sigma_{x}\sqrt{\frac{\pi}{2}}\cdot\frac{\frac{r-\rho}{\sqrt{1+r^{2}-2r\rho}}+\frac{r+\rho}{\sqrt{1+r^{2}+2r\rho}}}{\tan^{-1}\left(\frac{r-\rho}{\sqrt{1-\rho^{2}}}\right)+\tan^{-1}\left(\frac{r+\rho}{\sqrt{1-\rho^{2}}}\right)}.$
(24)

3\. The conditional tail probability: for any $r>0$, $\rho\in(-1,1)$, for any
$t>0$,

$\displaystyle
Pr(|X|>t\big{|}|X|>|Y|)\leq\exp\left(-\frac{t^{2}}{2\sigma_{x}^{2}}\right).$
(25)

With Lemma 4.2, we have the following result on the maximum of a group of
Gaussian variables.

######  Lemma 4.3.

Let $X_{1},...,X_{p}$ be iid $N(0,\sigma_{x}^{2})$ variables. Let $Y\sim
N(0,\sigma_{y}^{2})$ be another Gaussian random variable with arbitrary
dependence structure with $X_{i}$’s. Let $r=\sigma_{x}/\sigma_{y}\leq 1.$ Then

$\displaystyle
P_{+}(r,p)\mathrel{\mathop{:}}=Pr(\max_{i=1,...,p}|X|>|Y|)\leq\int_{0}^{\infty}2p[2\Phi(t)-1]^{p-1}[2\Phi(rt)-1]\phi(t)dt,$
(26)

where $\phi(x)$ and $\Phi(x)$ are the standard Gaussian pdf and cdf,
respectively.

###### Proof.

By Lemma 4.2 and independence, we know that $Pr(\max_{i=1,...,p}|X|>|Y|)$
reaches its maximum when $X_{i}$ is independent of $Y$, i.e., when
$\rho(X_{i},Y)=0$, $\forall i=1,...,p$. Since $|X_{i}|$ follows a half-normal
distribution with cdf being
$\operatorname{erf}(\frac{x}{\sqrt{2}\sigma_{x}})$, we have

$\displaystyle Pr(\max_{i=1,...,p}|X_{i}|\leq
t)=\operatorname{erf}\left(\frac{t}{\sqrt{2}\sigma_{x}}\right)^{p}=\left[2\Phi\left(\frac{x}{\sigma_{x}}\right)-1\right]^{p},$

and probability density function
$g(x)=2p[\Phi(\frac{x}{\sigma_{x}})-1]^{p-1}\frac{1}{\sqrt{2\pi}\sigma_{x}}e^{-\frac{x^{2}}{2\sigma_{x}^{2}}}$.
When $Y$ is independent of all $X_{i}$’s (which gives the upper bound), we
have

$\displaystyle Pr(\max_{i=1,...,p}|X|>|Y|)$
$\displaystyle=\int_{0}^{\infty}2p\left[\Phi\left(\frac{x}{\sigma_{x}}\right)-1\right]^{p-1}\frac{1}{\sqrt{2\pi}\sigma_{x}}e^{-\frac{x^{2}}{2\sigma_{x}^{2}}}Pr(|Y|<x)dx$
$\displaystyle=\int_{0}^{\infty}2p\left[\Phi\left(\frac{x}{\sigma_{x}}\right)-1\right]^{p-1}\frac{1}{\sqrt{2\pi}\sigma_{x}}e^{-\frac{x^{2}}{2\sigma_{x}^{2}}}\operatorname{erf}\left(\frac{x}{\sqrt{2}\sigma_{y}}\right)dx$
$\displaystyle=\int_{0}^{\infty}2p[2\Phi(t)-1]^{p-1}[2\Phi(rt)-1]\phi(t)dt,$

with a proper change of variables. This gives an upper bound as shown above. ∎

In Lemma 4.3, $P_{+}(r,p)$ is an increasing function in both $r$ and $p$. In
Figure 4, we plot the $P_{+}(r,p)$ with different $r$ and $p$ values. We see
that when $r$ is as small as 0.1, $P_{+}(r,p)$ is smaller than 0.4 when $p$ is
as large as $10^{6}$.

Figure 4: $P(r,p)$ in (26) in Lemma 4.3 against $r\leq 1$ at different $p$.
The red curve ($p=1$) also equals $Pr(|X|>|Y|)$ in Lemma 4.2.

Equipped with Lemma 4.3, we can bound $N_{+}$ in Algorithm 6, the largest
number of projected signs that are possible to change when $u$ is replaced by
any neighboring data vector $u^{\prime}$.

######  Lemma 4.4 (Binomial tail bound).

Let $X\sim Binomial(n,p)$ and denote $\mu=\mathbb{E}[X]=np$. For any $\eta>0$,
it holds that

$\displaystyle Pr(X\geq(1+\eta)\mu)\leq\exp(-\frac{\eta^{2}\mu}{\eta+2}).$

######  Proposition 4.5 (Bounding $N_{+}$).

Suppose $u\in[-1,1]^{p}$ and $\beta\leq\|u\|$. Denote $r=\frac{\beta}{\|u\|}$
and $F_{\|u\|,p}=P_{+}(\frac{\beta}{\|u\|},p)$ as (26) in Lemma 4.3. Denote
$s=sign(W^{T}u)\in\\{-1,+1\\}^{k}$ and
$s^{\prime}=sign(W^{T}u^{\prime})\in\\{-1,+1\\}^{k}$ for $u^{\prime}$ that is
$\beta$-neighboring to $u$, and $S=\\{i:s_{j}\neq s_{j}^{\prime}\\}$. Then,
with probability $1-\delta$,

$\displaystyle|S|\leq
N_{+}(\|u\|,\delta,k,p)=\min\\{F_{\|u\|,p}k+\frac{1}{2}\Big{[}\log(1/\delta)+\sqrt{(\log(1/\delta))^{2}+8F_{\|u\|,p}k\log(1/\delta)}\Big{]},k\\}.$
(27)

######  Remark 4.2.

Since $F_{\|u\|,p}=P_{+}(r,p)$ is an increasing function in $r=\beta/\|u\|$,
$N_{+}$ would be smaller if $\beta/\|u\|$ is smaller. That is, the signs of
$W^{T}u$ and $W^{T}u^{\prime}$ are less likely to be different when the
difference between neighboring data, $\beta$, is relatively small compared
with the data norm $\|u\|$.

Figure 5: The upper bound on $N_{+}(\|u\|,\delta,k,p)$ in Proposition 4.5
against data norm $\|u\|$ at different $\beta$. In the simulation, $p=1024$,
$k=512$ and $\delta=10^{-6}$.

###### Proof.

Consider a single Gaussian projection vector $w$ with iid $N(0,1)$ entries.
Since $w^{T}u=\sum_{i=1}^{p}u_{i}w_{i}$ and each $w_{i}\sim N(0,1)$, we know
that $\begin{pmatrix}\beta w_{i}\\\ x\end{pmatrix}\sim
N\begin{pmatrix}\beta^{2}&\rho_{i}\beta\|u\|\\\
\rho_{i}\beta\|u\|&\|u\|^{2}\end{pmatrix}$ where
$\rho_{i}=\frac{u_{i}}{\|u\|}$ is the correlation coefficient. Since
$|w^{T}(u-u^{\prime})|\leq\beta\max_{i=1,...,p}|w_{i}|$ by Definition 2.3 of
$\beta$-neighboring (and more generally, when
$\|u-u^{\prime}\|_{1}\leq\beta$), we have

$\displaystyle Pr(\max_{u^{\prime}\in
Nb(u)}|w^{T}(u-u^{\prime})|\geq|w^{T}u|)=Pr(\beta\max_{i=1,...,p}|w_{i}|\geq|w^{T}u|).$

Note that, $\beta\max_{i=1,...,p}|w_{i}|\geq|w^{T}u|$ is a necessary condition
for the event that there exists a neighbor such that $sign(w^{T}u)\neq
sign(w^{T}u^{\prime})$. Denote
$I=\mathbbm{1}\\{\beta\max_{i=1,...,p}|w_{i}|\geq|w^{T}u|\\}$. Applying Lemma
4.3 with $r=\beta/\|u\|\leq 1$ yields

$\displaystyle\mathbb{E}[I]=Pr(\beta\max_{i=1,...,p}|w_{i}|\geq|w^{T}u|)\leq
F_{\|u\|,p}=\int_{0}^{\infty}2p[2\Phi(t)-1]^{p-1}[2\Phi(rt)-1]\phi(t)dt$ (28)

as given by (26). Let $I_{j}$ be the corresponding indicator function w.r.t.
each column in the projection matrix $W$. Denote $N_{+}=\sum_{j=1}^{k}I_{j}$,
and by the above reasoning, we know that $|S|\leq N_{+}$ where $S$ is defined
in the theorem. Since the columns of $W$ are independent, $N_{+}$ follows a
$Binomial(k,\mathbb{E}[I])$ distribution with $k$ trials and success
probability $\mathbb{E}[I]$ bounded as above. Applying Chernoff’s bound on
binomial variable (Lemma 4.4), we obtain

$\displaystyle
Pr(N_{+}\geq(1+\eta)F_{\|u\|,p}k)\leq\exp(-\frac{\eta^{2}F_{\|u\|,p}k}{\eta+2}).$

Setting the RHS to $\delta$ gives
$\eta=\frac{\log(1/\delta)+\sqrt{(\log(1/\delta))^{2}+8F_{\|u\|,p}k\log(1/\delta)}}{2F_{\|u\|,p}k}$.
Therefore, with probability $1-\delta$,

$\displaystyle N_{+}(\|u\|,\delta,k,p)\leq
F_{\|u\|,p}k+\frac{1}{2}\Big{[}\log(1/\delta)+\sqrt{(\log(1/\delta))^{2}+8F_{\|u\|,p}k\log(1/\delta)}\Big{]}.$

In addition, $N_{+}\leq k$ trivially. The proof is complete. ∎

In Figure 5, we plot the bound on $N_{+}(\|u\|,\delta,k,p)$ derived in
Proposition 4.5 against $\|u\|$ with various $\beta$ and fixed $p$, $k$ and
$\delta$. As expected, $N_{+}(\|u\|,\delta,k,p)$ shrinks rapidly as the data
norm $\|u\|$ increases. Since $N_{+}(\|u\|,\delta,k,p)$ is decreasing in
$\|u\|$ (because $F_{\|u\|,p}$ decreases with $\|u\|$), we know that for all
$u$ with $\|u\|\geq m$, the $|S|$ in Proposition 4.5 would be upper bounded by
$N_{+}(m,\delta,k,p)$ with high probability, as used in Algorithm 6 and the
proof of Theorem 4.1. Also, in DP-SignRP-RR, the probability of flipping the
true SignRP, $\frac{1}{e^{\epsilon/N_{+}}+1}$, would be smaller when the data
norm (or, its lower bound $m$) is large compared with $\beta$.

####  4.1.2 Utility in angle estimation by DP-SignRP-RR

Define the DP-SignRP-RR estimator of the angle between two data points $u$ and
$v$ as

$\displaystyle\hat{\theta}_{RR}=\pi(1-\hat{P}_{RR}),$ (29) where
$\displaystyle\hat{P}_{RR}=\frac{(e^{\epsilon^{\prime}}+1)^{2}}{(e^{\epsilon^{\prime}}-1)^{2}}\frac{1}{k}\sum_{j=1}^{k}\mathbbm{1}\\{\tilde{s}_{1j}=\tilde{s}_{2j}\\}-\frac{2e^{\epsilon^{\prime}}}{(e^{\epsilon^{\prime}}-1)^{2}}.$

We have the following result on the utility.

######  Theorem 4.6.

Let $\rho=\cos(u,v)$ and $\theta=\cos^{-1}(\rho)$. Run Algorithm 6 with
$N_{+}$ given in Proposition 4.5 and define the DP-SignRP-RR angle estimator
by (29). We have $\mathbb{E}[\hat{\theta}_{RR}]=\theta$. As
$k\rightarrow\infty$, the following holds:

$\displaystyle\hat{\theta}_{RR}\rightarrow N(\theta,\frac{V_{RR}}{k}),$

where

$V_{RR}=\theta(\pi-\theta)+\frac{2\pi^{2}e^{\epsilon/N_{+}}}{(e^{\epsilon/N_{+}}-1)^{2}}+\frac{4\pi^{2}e^{2\epsilon/N_{+}}}{(e^{\epsilon/N_{+}}-1)^{4}}.$

###### Proof.

Let $s=sign(W^{T}u)\in\\{-1,+1\\}^{k}$,
$s^{\prime}=sign(W^{T}u^{\prime})\in\\{-1,+1\\}^{k}$. We denote the collision
probability of non-private SignRP as

$P_{SRP}=Pr(s_{1j}=s_{2j})=1-\frac{\cos^{-1}(\rho)}{\pi}=1-\frac{\theta}{\pi}.$

Hence, the collision probability of DP-SignRP-RR can be computed as

$\displaystyle\tilde{P}\mathrel{\mathop{:}}=Pr(\tilde{s}_{1j}$
$\displaystyle=\tilde{s}_{2j})=Pr(s_{1j}=s_{2j},\text{both change sign or not
change sign})$ $\displaystyle\hskip 158.99377pt+Pr(s_{1j}\neq s_{2j},\text{one
sign changes})$
$\displaystyle=P_{SRP}[(\frac{e^{\epsilon^{\prime}}}{e^{\epsilon^{\prime}}+1})^{2}+(\frac{1}{e^{\epsilon^{\prime}}+1})^{2}]+2(1-P_{SRP})\frac{e^{\epsilon^{\prime}}}{(e^{\epsilon^{\prime}}+1)^{2}}$
$\displaystyle=P_{SRP}\frac{(e^{\epsilon^{\prime}}-1)^{2}}{(e^{\epsilon^{\prime}}+1)^{2}}+\frac{2e^{\epsilon^{\prime}}}{(e^{\epsilon^{\prime}}+1)^{2}},$

which increases linearly in $P_{SRP}$. Thus, it holds that

$\displaystyle\mathbb{E}[\hat{P}_{RR}]=\frac{(e^{\epsilon^{\prime}}+1)^{2}}{(e^{\epsilon^{\prime}}-1)^{2}}\tilde{P}-\frac{2e^{\epsilon^{\prime}}}{(e^{\epsilon^{\prime}}-1)^{2}}=P_{SRP}=1-\frac{\theta}{\pi},$

which implies
$\mathbb{E}[\hat{\theta}_{RR}]=\pi\left(1-(1-\frac{\theta}{\pi})\right)=\theta$.
To compute the variance, we first estimate $\theta=\cos^{-1}(\rho)$ by

$\displaystyle\hat{\theta}=\pi(1-\hat{P}_{RR}).$

Then according to the Central Limit Theorem (CLT), for the sample mean of iid
Bernoulli’s, as $k\rightarrow\infty$, we have

$\displaystyle\frac{1}{k}\sum_{j=1}^{k}\mathbbm{1}\\{\tilde{s}_{1j}=\tilde{s}_{2j}\\}\rightarrow
N(\tilde{P},\frac{\tilde{P}(1-\tilde{P})}{k}).$

As a result, we have $\hat{\theta}\rightarrow N(\theta,\frac{V_{RR}}{k})$,
where

$\displaystyle V_{RR}$
$\displaystyle=\frac{\pi^{2}(e^{\epsilon^{\prime}}+1)^{4}}{(e^{\epsilon^{\prime}}-1)^{4}}\Big{[}(1-\frac{\theta}{\pi})\frac{(e^{\epsilon^{\prime}}-1)^{2}}{(e^{\epsilon^{\prime}}+1)^{2}}+\frac{2e^{\epsilon^{\prime}}}{(e^{\epsilon^{\prime}}+1)^{2}}\Big{]}\Big{[}\frac{e^{2\epsilon^{\prime}}+1}{(e^{\epsilon^{\prime}}+1)^{2}}-(1-\frac{\theta}{\pi})\frac{(e^{\epsilon^{\prime}}-1)^{2}}{(e^{\epsilon^{\prime}}+1)^{2}}\Big{]}$
$\displaystyle=\frac{\pi^{2}(e^{\epsilon^{\prime}}+1)^{4}}{(e^{\epsilon^{\prime}}-1)^{4}}\Big{[}(1-\frac{\theta}{\pi})\frac{(e^{\epsilon^{\prime}}-1)^{2}}{(e^{\epsilon^{\prime}}+1)^{2}}+\frac{2e^{\epsilon^{\prime}}}{(e^{\epsilon^{\prime}}+1)^{2}}\Big{]}\Big{[}\frac{\theta}{\pi}\frac{(e^{\epsilon^{\prime}}-1)^{2}}{(e^{\epsilon^{\prime}}+1)^{2}}+\frac{2e^{\epsilon^{\prime}}}{(e^{\epsilon^{\prime}}+1)^{2}}\Big{]}$
$\displaystyle=\frac{\pi^{2}\theta}{\pi}(1-\frac{\theta}{\pi})+(1-\frac{\theta}{\pi})\frac{2e^{\epsilon^{\prime}}}{(e^{\epsilon^{\prime}}-1)^{2}}+\frac{\theta}{\pi}\frac{2e^{\epsilon^{\prime}}}{(e^{\epsilon^{\prime}}-1)^{2}}+\frac{4e^{2\epsilon^{\prime}}}{(e^{\epsilon^{\prime}}-1)^{4}}$
$\displaystyle=\theta(\pi-\theta)+\frac{2\pi^{2}e^{\epsilon^{\prime}}}{(e^{\epsilon^{\prime}}-1)^{2}}+\frac{4\pi^{2}e^{2\epsilon^{\prime}}}{(e^{\epsilon^{\prime}}-1)^{4}}.$

We conclude the proof by replacing $\epsilon^{\prime}=\epsilon/N_{+}$. ∎

Theorem 4.6 says that $\hat{\theta}_{RR}$ is an unbiased estimator of $\theta$
and asymptotically normal. Compared with the variance in (10) of the estimator
from SignRP, we see that $\hat{\theta}_{RR}$ incurs an extra variance (i.e.,
utility loss) of
$\frac{\pi^{2}}{k}\Big{[}\frac{2e^{\epsilon/N_{+}}}{(e^{\epsilon/N_{+}}-1)^{2}}+\frac{4e^{2\epsilon/N_{+}}}{(e^{\epsilon/N_{+}}-1)^{4}}\Big{]}$.
This quantity increases as $\epsilon$ gets smaller, illustrating the utility-
privacy trade-off of DP-SignRP-RR.

Optimal projection dimension $k^{*}$. In Theorem 4.6, note that the variance
$V_{RR}$ does not always decrease with larger $k$. In particular, in
Proposition 4.5 since $N_{+}\asymp F_{\|u\|,p}k$, the term
$\Big{[}\frac{2e^{\epsilon/N_{+}}}{(e^{\epsilon/N_{+}}-1)^{2}}+\frac{4e^{2\epsilon/N_{+}}}{(e^{\epsilon/N_{+}}-1)^{4}}\Big{]}$
increases with $k$. Therefore, there exists an optimal $k^{*}$ that minimizes
the estimation variance. When $k$ is sufficiently large, we have the
approximation

$\displaystyle\frac{V_{RR}}{k}\approx\frac{\theta(\pi-\theta)}{k}+\frac{2\pi^{2}F_{\|u\|,p}^{2}k}{\epsilon^{2}}+\frac{8\pi^{2}F_{\|u\|,p}^{4}k^{3}}{\epsilon^{4}},$

using the approximation that $e^{x}-1\approx x$ when $x$ is small. To find the
optimal $k$ minimizing this expression, we compute the derivative and set it
as zero:

$\displaystyle-\frac{\theta(\pi-\theta)}{k^{2}}+\frac{2\pi^{2}F_{\|u\|,p}^{2}}{\epsilon^{2}}+\frac{24\pi^{2}F_{\|u\|,p}^{4}k^{2}}{\epsilon^{4}}=0\
\ \Longrightarrow\ \
k^{*}\asymp\frac{\epsilon\theta(\pi-\theta)}{F_{\|u\|,p}}.$

This analysis suggests that theoretically the optimal $k^{*}$ is larger when:
(1) $\epsilon$ is large; (2) $F_{\|u\|,p}$ is small, which is typically true
when the norm of the data is relatively large.

###  4.2 DP-SignRP-RR-Smooth Using Smooth Flipping Probability

The DP-SignRP-RR algorithm is not satisfactory in terms of privacy
preservation. For instance, when the norm of the data is not very large (e.g.,
$m=10$ and $\beta=1$), for $k=512$, $N_{+}$ can be as large as $200$ (see
Figure 5). This implies that, we need $\epsilon=400$ in order for the
probability of flipping a true SignRP to be
$\frac{1}{e^{\epsilon/N_{+}}+1}\approx 11.9\%$, which is still fairly large to
achieve a good utility in practice. Thus, the privacy protection of DP-SignRP-
RR might be too weak. Next, we develop a new algorithm that could reduce the
flipping probability of DP-SignRP-RR, thanks to the “robustness” of SignRP
brought by the “aggregate-and-sign” operation.

1 Input: Data $u\in[-1,1]^{p}$; $\epsilon>0$, number of projections $k$

2

3Output: Differentially private sign random projections

4

5Apply RP by $x=\frac{1}{\sqrt{k}}W^{T}u$, where $W\in\mathbb{R}^{p\times k}$
is a random $N(0,1)$ matrix

6Compute $L_{j}=\lceil\frac{|x_{j}|}{\beta\max_{i=1,...,p}|W_{ij}|}\rceil$ for
$j=1,...,k$

7Compute $\tilde{s}_{j}=\begin{cases}sign(x_{j}),&\text{with prob.}\
\frac{e^{\epsilon_{j}^{\prime}}}{e^{\epsilon_{j}^{\prime}}+1}\\\
-sign(x_{j}),&\text{with prob.}\
\frac{1}{e^{\epsilon_{j}^{\prime}}+1}\end{cases}$ for $j=1,...,k$, with
$\epsilon_{j}^{\prime}=\frac{L_{j}}{k}\epsilon$

Return $\tilde{s}$ as the DP-SignRP of $u$

Algorithm 7 DP-SignRP-RR-smooth using smooth flipping probability

Smooth flipping probability. We propose a novel sampling approach based on
“smooth flipping probability”. Recall the motivation of smooth sensitivity
(Definition 2.5): we may allow the use of local sensitivity at $u$ as long as
we account for the local sensitivities of all $u^{\prime}\in\mathcal{U}$,
discounted exponentially by a factor $e^{-\epsilon d(u,u^{\prime})}$ where
$d(u,u^{\prime})$ is the minimal number of “taking-a-neighbor” operations to
reach $u^{\prime}$ from $u$. Conceptually, smooth sensitivity says that, the
farther $u$ is from a high local sensitivity point, the less noise is needed
for $u$ to achieve DP.

What is the “local perturbation” for the 1-bit SignRP? Consider one projection
$x_{j}=W[:,j]^{T}u$ and $s_{j}=sign(x_{j})$. For a neighbor $u^{\prime}$ of
$u$, denote $x_{j}^{\prime}=W[:,j]^{T}u^{\prime}$ and
$s_{j}^{\prime}=sign(x_{j}^{\prime})$. Obviously, by $\beta$-adjacency
(Definition 2.3), $s_{j}^{\prime}$ is possible to be different from $s_{j}$
only if $|x_{j}|<\beta\max_{i=1,...,p}|W_{ij}|$, because
$|x_{j}-x_{j}^{\prime}|\leq\beta\max_{i=1,...,p}|W_{ij}|$. Intuitively, this
implies that projected values near zero would have larger “local sensitivity”.
More concretely,

  * •

When $|x_{j}|<\beta\max_{i=1,...,p}|W_{ij}|$, the “local sign flipping”
(analogue to the local sensitivity for noise addition) is required, since
$s_{j}^{\prime}$ may change the sign of $s_{j}$. A typical choice is the
standard randomized response (RR) strategy: keep the sign with probability
$\frac{e^{\epsilon/k}}{e^{\epsilon/k}+1}$ and flip otherwise.

  * •

When $|x_{j}|\geq\beta\max_{i=1,...,p}|W_{ij}|$, there does not exist
$u^{\prime}\in Nb(u)$ such that $s_{j}^{\prime}\neq s_{j}$. Thus, the “local
sign flipping” is not needed (i.e., locally, we do not need to apply random
sign flips). However, due to the same issue as the local sensitivity, if we do
not perturb $s_{j}$ in this case, then the algorithm does not satisfy DP.
Instead, we leverage the idea of smooth sensitivity and propose “smooth
flipping probability” which applies less perturbation for points far away from
the “high-sensitivity region” (i.e., the regime with
$|x_{j}|<\beta\max_{i=1,...,p}|W_{ij}|$). Specifically, we define
$L_{j}=\lceil\frac{|x_{j}|}{\beta\max_{i=1,...,p}|W_{ij}|}\rceil$. The
probability of keeping the sign $s_{j}$ is
$P_{j}^{(u)}=\frac{e^{\epsilon_{j}^{\prime}}}{e^{\epsilon_{j}^{\prime}}+1}$
where $\epsilon_{j}^{\prime}=\frac{L_{j}}{k}\epsilon$. In Theorem 4.7, we will
see that this flipping probability is “smooth”: for $\forall u,u^{\prime}$
that are neighbors, $P_{j}^{(u)}\leq e^{\epsilon/k}P_{j}^{(u^{\prime})}$,
which justifies its name.

Figure 6: Illustration of the smooth flipping probability, “local flipping
probability”, and the global upper bound for DP-SignRP. $\epsilon=1$, $k=1$.
$L$ is computed in Algorithm 7.

The concrete steps of DP-SignRP-RR-smooth are summarized in Algorithm 7. Note
that, the above two cases can be unified into one, since the first case
corresponds to $L_{j}=1$ which exactly recovers the flipping probability
$\frac{e^{\epsilon/k}}{e^{\epsilon/k}+1}$. In Figure 6, we provide an
illustrative example of the smooth flipping probability (red) and the “local
flipping probability” (green) discussed above. We see that the local flipping
probability is only non-zero at $L=1$, i.e., when $s_{j}$ and $s_{j}^{\prime}$
are possible to be different. The proposed smooth flipping probability is non-
zero for all $L>0$, but keeps shrinking as $L$ is larger, i.e., as the
projected value is farther from $0$.

######  Theorem 4.7.

Algorithm 7 is $\epsilon$-DP.

###### Proof.

Let us consider a single projection vector $w_{j}=W_{[:,j]}$. Denote
$x_{j}=w_{j}^{T}u$ and $x_{j}^{\prime}=w_{j}^{T}u^{\prime}$ for a neighboring
data $u^{\prime}$ of $u$, and $s_{j}=sign(x_{j})$,
$s_{j}^{\prime}=sign(x_{j}^{\prime})$. Also, let
$L_{j}=\lceil\frac{|x_{j}|}{\beta\max_{i=1,...,p}|W_{ij}|}\rceil$ and
$L_{j}^{\prime}=\lceil\frac{|x_{j}^{\prime}|}{\beta\max_{i=1,...,p}|W_{ij}|}\rceil$.
W.l.o.g., we can assume $s_{j}=1$ by the symmetry of random projection and the
symmetry of DP. Consider two cases:

  * •

Case I: $L_{j}\geq 2$. In this case, we know that $s_{j}^{\prime}=s_{j}$,
i.e., the change from $u$ to $u^{\prime}$ will not change the sign of the
projection. Thus, in Algorithm 7, we have

$\displaystyle\frac{Pr(\tilde{s}_{j}=1)}{Pr(\tilde{s}_{j}^{\prime}=1)}=\exp(\frac{L_{j}-L_{j}^{\prime}}{k}\epsilon)\frac{\exp(\frac{L_{j}^{\prime}}{k}\epsilon)+1}{\exp(\frac{L_{j}}{k}\epsilon)+1}.$

By the definition of $\beta$-adjacency, $|L_{j}-L_{j}^{\prime}|$ equals either
$0$ or $1$. When $L_{j}=L_{j}^{\prime}$,
$\frac{Pr(\tilde{s}_{j}=1)}{Pr(\tilde{s}_{j}^{\prime}=1)}=1$. When
$L_{j}-L_{j}^{\prime}=1$, we have

$\displaystyle\frac{Pr(\tilde{s}_{j}=1)}{Pr(\tilde{s}_{j}^{\prime}=1)}=\frac{\exp(\frac{L_{j}}{k}\epsilon)+\exp(\frac{1}{k}\epsilon)}{\exp(\frac{L_{j}}{k}\epsilon)+1}.$

Hence, we have
$1\leq\frac{Pr(\tilde{s}_{j}=1)}{Pr(\tilde{s}_{j}^{\prime}=1)}\leq
e^{\frac{\epsilon}{k}}$ by the numeric identity
$1\leq\frac{a+c}{b+c}\leq\frac{a}{b}$ for $a\geq b>0$ and $c>0$. Thus, by
symmetry,
$e^{-\frac{\epsilon}{k}}\leq\frac{Pr(\tilde{s}_{j}=1)}{Pr(\tilde{s}_{j}^{\prime}=1)}\leq
e^{\frac{\epsilon}{k}}$. On the other hand,

$\displaystyle\frac{Pr(\tilde{s}_{j}=-1)}{Pr(\tilde{s}_{j}^{\prime}=-1)}=\frac{\exp(\frac{L_{j}^{\prime}}{k}\epsilon)+1}{\exp(\frac{L_{j}}{k}\epsilon)+1}.$

Similarly, when $L_{j}=L_{j}^{\prime}$, the ratio equals $1$. When
$L_{j}=L_{j}^{\prime}-1$, we have
$\frac{Pr(\tilde{s}_{j}=-1)}{Pr(\tilde{s}_{j}^{\prime}=-1)}\leq\exp(\frac{L_{j}^{\prime}}{k}\epsilon-\frac{L_{j}}{k}\epsilon)=e^{\frac{\epsilon}{k}}$.
By symmetry we obtain
$e^{-\frac{\epsilon}{k}}\leq\frac{Pr(\tilde{s}_{j}=-1)}{Pr(\tilde{s}_{j}^{\prime}=-1)}\leq
e^{\frac{\epsilon}{k}}$.

  * •

Case II: $L_{j}=1$. In this case, $s_{j}$ might be different from
$s_{j}^{\prime}$. First, if $L_{j}^{\prime}=2$, then the above analysis also
applies that $\frac{Pr(\tilde{s}_{j}=1)}{Pr(\tilde{s}_{j}^{\prime}=1)}$ and
$\frac{Pr(\tilde{s}_{j}=-1)}{Pr(\tilde{s}_{j}^{\prime}=-1)}$ are both lower
and upper bounded by $e^{-\frac{\epsilon}{k}}$ and $e^{\frac{\epsilon}{k}}$,
respectively. It suffices to examine the case when $L_{j}^{\prime}=1$. In this
case, if $s_{j}^{\prime}=s_{j}=1$ then the probability ratios simply equal 1.
If $s_{j}^{\prime}=-1$, we have

$\displaystyle\frac{Pr(\tilde{s}_{j}=1)}{Pr(\tilde{s}_{j}^{\prime}=1)}=\frac{\frac{\exp(\frac{\epsilon}{k})}{\exp(\frac{\epsilon}{k})+1}}{\frac{1}{\exp(\frac{\epsilon}{k})+1}}=e^{\frac{\epsilon}{k}},\quad\frac{Pr(\tilde{s}_{j}=-1)}{Pr(\tilde{s}_{j}^{\prime}=-1)}=\frac{\frac{1}{\exp(\frac{\epsilon}{k})+1}}{\frac{\exp(\frac{\epsilon}{k})}{\exp(\frac{\epsilon}{k})+1}}=e^{-\frac{\epsilon}{k}}.$

Combining two cases, we have that
$\log\frac{Pr(\tilde{s}_{j}=t)}{Pr(\tilde{s}_{j}^{\prime}=t)}\leq\frac{\epsilon}{k}$,
for $t=-1,1$, and for all $j=1,...,k$. That is, each single perturbed sign
achieves $\frac{\epsilon}{k}$-DP. Since the $k$ projections are independent,
by Theorem 2.3, we know that the output bit vector
$\tilde{s}=[\tilde{s}_{1},...,\tilde{s}_{k}]$ is $\epsilon$-DP as claimed. ∎

Comparison with DP-SignRP-RR (Algorithm 6). In terms of algorithm design and
privacy, DP-SignRP-RR-smooth (Algorithm 7) has the following two advantages
over the standard DP-SignRP-RR method (Algorithm 6):

  1. 1.

DP-SignRP-RR-smooth does not require (assume) a lower bound $m$ on the data
norms;

  2. 2.

DP-SignRP-RR-smooth achieves $\epsilon$-DP, while DP-SignRP-RR can only
guarantee $(\epsilon,\delta)$-DP.

Regarding the second point, as mentioned in Remark 4.1, Algorithm 6 can also
achieve $\epsilon$-DP if we set the flipping probability to be
$\frac{1}{e^{\epsilon/k}+1}$. Note that this equals the flipping probability
in Algorithm 7 when $L_{j}=1$, which is the “worst” global bound on the
flipping probability. In many cases, a good proportion of $L_{j}$ $j=1,...,k$
would be greater than 1. Therefore, when both are $\epsilon$-DP, DP-SignRP-RR-
smooth requires a much smaller flipping probability than DP-SignRP-RR.

###  4.3 DP-SignRP with Rademacher Projections

At this point, it should be clear that the flipping probability of DP-SignRP
(both DP-SignRP-RR and DP-SignRP-RR-smooth) essentially depends on how
concentrated the projected data is around zero. Particularly, $N_{+}$ in
Algorithm 6, as given in Proposition 4.5, is a high probability upper bound on
a Binomial random variable with success probability
$Pr(\beta\max_{i=1,...,p}|w_{i}|\geq|w^{T}u|)$ with $w\sim N(0,1)$. In
Algorithm 7,
$L_{j}=\lceil\frac{|w_{j}^{T}u|}{\beta\max_{i=1,...,p}|W_{ij}|}\rceil$. For
both quantities, a smaller value leads to a smaller sign flipping probability
and thus better utility.

$N_{+}$ in DP-SignRP-RR. We first consider the $N_{+}$ in Algorithm 6, which
determines the flipping probability $\frac{1}{e^{\epsilon/N_{+}}+1}$.
Particularly, $N_{+}$ in Algorithm 6, as given in Proposition 4.5, is a high
probability upper bound on a Binomial random variable with success probability

$\displaystyle P_{+}=Pr\left(\beta\max_{i=1,...,p}|w_{i}|\geq|w^{T}u|\right),$
(30)

where $w$ is the $p$-dimensional projection vector. When $w_{i}$ is sampled
from the Rademacher distribution, i.e., $w_{i}\in\\{-1,+1\\}$ with equal
probabilities, the probability calculation can be simplified:

$\displaystyle
P_{+,b}=Pr\left(\beta\max_{i=1,...,p}|w_{i}|\geq|\sum_{i=1}^{p}w_{i}u_{i}|\right)=Pr\left(\beta\geq|\sum_{i=1}^{p}w_{i}u_{i}|\right)\approx
2\Phi\left(\frac{\beta}{\|u\|}\right)-1.$ (31)

Based on the central limit theorem, the normal approximation (31) is accurate
unless $p$ is very small. Recall that, when $w_{i}$’s are sampled from the
Gaussian distribution, we have already calculated an upper bound in (28),
which is re-written as below:

$\displaystyle
P_{+,g}=Pr\left(\beta\max_{i=1,...,p}|w_{i}|\geq|\sum_{i=1}^{p}w_{i}u_{i}|\right)\leq\int_{0}^{\infty}2p[2\Phi(t)-1]^{p-1}[2\Phi(\beta
t/\|u\|)-1]\phi(t)dt.$ (32)

Next, we provide a simulation study to justify the approximation and compare
different distributions in terms of their impact on the probability (30), for
$\beta=1$ as well as $\beta=0.1$. For simplicity, we simulate the data as a
$p$-dimensional vector of uniform random numbers sampled from $unif[-1,1]$. We
experiment with five different choices of $w$: the standard Gaussian, the
uniform, the “very sparse” distribution (18) with $s=1$, $s=3$, and $s=10$. We
vary $p$ from 10 to 1000. For each case, we repeat the simulations $10^{7}$
times to ensure sufficient accuracy. Figure 7 verifies that the two
approximations (31) and (32) are accurate. In Figure 8, we provide the curves
for more types of projection matrices. From both figures, we see that using
the Rademacher projection can considerably reduce (30) compared with Gaussian
(and other) projections, leading to a smaller $N_{+}$ value. This typically
implies better utility.

Figure 7: Simulations for evaluating (31) and (32), using two choices for $w$:
the Gaussian distribution and the Rademacher distribution (i.e., (18) with
$s=1$). We plot the two upper bounds (31) and (32) as black dashed curves,
which essentially both overlap with their corresponding simulations.

Figure 8: Simulations (same as in Figure 8) for evaluating (30), using five
different choices for $w$: the Gaussian, the uniform, the “very sparse”
distribution (18) with $s=1,3$ and $10$. $s=1$ is the Rademacher distribution.
The data vector is simulated by sampling each entry from $unif[-1,1]$.

$L_{j}$ in DP-SignRP-RR-smooth. Similarly, we numerically evaluate the $L_{j}$
in Algorithm 7. We run Algorithm 7 with $k=512$, which gives $512$ $L_{j}$
values. In Figure 9, we plot the proportion (or the approximated distribution)
of the values of $L_{j}$ among $k$ projections. As we see, Rademacher
projection produces the least number of small $L_{j}$ values and the largest
number of higher $L_{j}$ values. As the smooth flipping probability equals
$\frac{1}{\exp(\frac{L_{j}}{k}\epsilon)+1}$, larger $L_{j}$ leads to smaller
probability of sign flipping. Hence, Rademacher is again the best choice for
the projection matrix.

Figure 9: Simulations for evaluating $L_{j}$ in Algorithm 7, using different
choices for $w$. $s=1$ is the Rademacher distribution. Left: $p=100$, right:
$p=1000$. The $y$-axis is the proportion (normalized histogram) of the values
of all the $L_{j}$, $j=1,...,k$ computed using $k=512$ projected samples.

###  4.4 DP-SignOPORP with Smooth Flipping Probability

Similarly, we may also take the sign of OPORP studied before, and make it
differentially private. The smoothed flipping probability can also be adopted
in this case. As before, we present the variant with Rademacher projection for
conciseness. Algorithm 8 provides the general framework, covering two
variants. The first one, DP-SignOPORP-RR, is based on the standard randomized
response (RR) technique. The second variant, DP-SignOPORP-RR-smooth, is an
improved version with our proposed “smooth flipping probability”.

1 Input: Data $u\in[-1,1]^{p}$; $\epsilon>0$; Number of projections $k$

2

3Output: Differentially private sign OPORP

4

5Apply Algorithm 4 with a random Rademacher projection vector to get the OPORP
$x$

6

DP-SignOPORP-RR:

7Compute $\tilde{s}_{j}=\begin{cases}sign(x_{j}),&\text{with prob.}\
\frac{e^{\epsilon}}{e^{\epsilon}+1}\\\ -sign(x_{j}),&\text{with prob.}\
\frac{1}{e^{\epsilon}+1}\end{cases}$ for $j=1,...,k$

DP-SignOPORP-RR-smooth:

8Compute $L_{j}=\lceil\frac{|x_{j}|}{\beta}\rceil$ for $j=1,...,k$

9Compute $\tilde{s}_{j}=\begin{cases}sign(x_{j}),&\text{with prob.}\
\frac{e^{\epsilon_{j}^{\prime}}}{e^{\epsilon_{j}^{\prime}}+1}\\\
-sign(x_{j}),&\text{with prob.}\
\frac{1}{e^{\epsilon_{j}^{\prime}}+1}\end{cases}$ for $j=1,...,k$, with
$\epsilon_{j}^{\prime}=L_{j}\epsilon$

10For $\tilde{s}_{j}=0$, assign a random coin in $\\{-1,1\\}$

Return $\tilde{s}$ as the DP-SignOPORP of $u$

Algorithm 8 DP-SignOPORP-RR and DP-SignOPORP-RR-smooth

Benefit of binning. In Algorithm 8, we see that the key difference compared
with DP-SignRP methods is that, the $\frac{1}{N_{+}}$ (in Algorithm 6) or
$\frac{1}{k}$ (in Algorithm 7) factor is removed from the flipping probability
formulas, which is a significant advantage in terms of privacy. This
improvement is a result of the binning step in OPORP. By Definition 2.3, two
neighboring data $u^{\prime}$ and $u$ differ in one coordinate. For SignRP,
since each projected data is an aggregation of the whole data vector, when we
switch from $u$ to $u^{\prime}$, (in principle) all $k$ projections are
possible to change. In contrast, in OPORP, since each data entry appears in
only one bin, $u^{\prime}$ will only cause exactly one projected output to
change, leaving all other bins untouched. This provides the intuition on the
source of privacy gain of DP-SignOPORP.

######  Theorem 4.8.

Both variants in Algorithm 8 are $\epsilon$-DP.

###### Proof.

The proof follows the idea of the proofs of DP-SignRP methods, but we need to
additionally consider the empty bins. Denote $x$ and $x^{\prime}$ as the OPORP
from Algorithm 4 using a same random vector $w$, and let $s=sign(x)$,
$s^{\prime}=sign(x^{\prime})$. Suppose $u$ and $u^{\prime}$ differ in
dimension $i$, and dimension $i$ is assigned to the $j^{*}$-th bin with
$j^{*}=\lceil\pi(i)/(p/k)\rceil$, where $\pi:[p]\mapsto[p]$ is the permutation
in OPORP. For any $y\in\\{-1,1\\}^{k}$, it is easy to see that to compute
$\log\frac{Pr(\tilde{s}=y)}{Pr(\tilde{s}^{\prime}=y)}$, it suffices to look at
the $j^{*}$-th output sample because other probabilities cancel out. For the
$j^{*}$-th sample, when $s_{j^{*}}\neq 0$ and $s_{j^{*}}^{\prime}\neq 0$, by
the same arguments as in the proof of Theorem 4.7, we know that
$e^{-\epsilon}\leq\frac{Pr(s_{j^{*}})=a}{Pr(s_{j^{*}}^{\prime})=a}\leq
e^{\epsilon}$, $a\in\\{-1,1\\}$, for both variants (DP-SignOPORP-RR and DP-
SignOPORP-RR-smooth). When one of $s_{j^{*}}$ and $s_{j^{*}}^{\prime}$ equals
$0$, it is also easy to see that (assume $s_{j^{*}}=1$ and
$s_{j^{*}}^{\prime}$ is a random coin)

$\displaystyle
1\leq\frac{Pr(s_{j^{*}})=1}{Pr(s_{j^{*}}^{\prime})=1}=\frac{2e^{\epsilon}}{e^{\epsilon}+1}\leq
e^{\epsilon},\quad
e^{-\epsilon}\leq\frac{Pr(s_{j^{*}})=-1}{Pr(s_{j^{*}}^{\prime})=-1}=\frac{2}{e^{\epsilon}+1}\leq
1.$

This holds for both variants. In particular, this case corresponds to
$L_{j^{*}}=1$ for the smooth flipping probability. This proves the theorem. ∎

Multiple repetitions. In Algorithm 8 Line 7, we see that if OPORP generates an
empty bin (i.e., $x_{j}=0$), we must assign a random sign to maintain DP. This
would undermine the utility since a random coin does not provide any useful
information. Therefore, it is desirable to avoid empty bins for better
utility. One simple way is to repeat the DP-SignOPORP (with smaller $k$) for
$t>1$ times, and concatenate the output vectors. Repetition is a standard
strategy for count-sketch (Charikar et al., 2004). For example, if the target
$k=256$, we may run Algorithm 8 for $t=4$ times, each time with $256/4=64$
projected values and privacy budget $\epsilon/4$. Since we are using fewer
bins per run, the number of empty bins will be reduced. After concatenating
the 4 output vectors, we still get a 256-dimensional bit vector with
$\epsilon$-DP by the composition theorem. In the experiments, we will see that
this strategy may improve the overall performance of DP-SignOPORP.

##  5 Experiments

We present a set of experiments on retrieval and classification tasks to
demonstrate the performance of different DP-RP and DP-SignRP methods.
Specifically, we will compare the following algorithms:

  * •

Raw-data-G-OPT: the method of directly adding optimal Gaussian noise with
sensitivity $\beta$ to the original data vectors.

  * •

DP-RP-G (Algorithm 1 \+ Theorem 3.1): Gaussian DP-RP with the Gaussian
mechanism.

  * •

DP-RP-G-OPT (Algorithm 1 \+ Theorem 3.5): DP-RP with Gaussian random
projection matrix and the optimal Gaussian noise.

  * •

DP-RP-G-OPT-B (Algorithm 3): DP-RP with Rademacher random projection matrix
and the optimal Gaussian noise mechanism.

  * •

DP-OPORP (Algorithm 5): OPORP algorithm with optimal Gaussian noise.

  * •

DP-SignOPORP-RR and DP-SignOPORP-RR-smooth (Algorithm 8): Signed OPORP with
standard randomized response and smooth flipping probability, respectively.

As noted in Section 4.4, due to the feature binning procedure, DP-SignOPORP is
substantially better than DP-SignRP in terms of privacy protection. Therefore,
we present the better-performing DP-SignOPORP method in our experiments. For
conciseness, we will only present results for $\beta=1$ and
$\epsilon\in[0.1,20]$. The chosen $\epsilon$ values cover the common range of
$\epsilon$ in many DP applications (e.g., Haeberlen and Khanna (2014); Kenny
et al. (2021)). Also, we fix $\delta=10^{-6}$ for approximate
$(\epsilon,\delta)$-DP algorithms.

###  5.1 Similarity Search

We first test the methods in similarity search problems, which is an important
application of RP and SignRP in industrial applications. In this experiment,
we use two standard image retrieval datasets, MNIST (LeCun et al., 1998) and
CIFAR (Krizhevsky and Hinton, 2009). The MNIST dataset contains 60000
28$\times$28 handwritten digits as the training set, and 10000 digits for
testing. The CIFAR dataset includes 60000 natural images with size
32$\times$32 (gray-scale) in total, with a 50000/10000 train-test split. On
these two datasets, the pixel values are between 0 and 1 by nature. For both
datasets, we treat the training set as the database, and use the samples from
the test set as the queries. We set the true neighbors for each query as the
top-50 sample vectors with the highest cosine similarity to the query. To
search with DP-RP (and DP-OPORP), we estimate the cosine between a query and a
sample point by the cosine between their corresponding output noisy projected
values. For DP-SignRP (and DP-SignOPORP), we compute the Hamming distances
between the private bit vectors between the query and the database points. For
both approaches, we return the samples with highest cosine or smallest Hamming
distance to the query. The evaluation metrics are precision and recall,
defined as

$\displaystyle\text{precision}@R=\frac{\text{\\# of true positives in}\ R\
\text{retrieved points}}{R},$ $\displaystyle\text{recall}@R=\frac{\text{\\# of
true positives in}\ R\ \text{retrieved points}}{\text{\\# of gold-standard
neighbors}},$

and in our setting, the number of gold-standard neighbors per query is 50. Our
presented results are also averaged over 10 independent repetitions.

Figure 10: Retrieval recall and precision on MNIST, $\beta=1$,
$\delta=10^{-6}$.

Figure 11: Retrieval recall and precision on CIFAR, $\beta=1$,
$\delta=10^{-6}$.

Results. In Figure 10 and Figure 11, we plot the precision and recall of DP-RP
DP-OPORP algorithms on MNIST and CIFAR, respectively. In each plot, we fix a
number of projections $k$ and plot the metrics against $\epsilon$. We observe
the following:

  * •

As a result of the optimal Gaussian mechanism, DP-RP-G-OPT substantially
outperforms the prior method, DP-RP-G, in terms of search precision and recall
at all $\epsilon$. DP-RP-G-OPT-B further improves DP-RP-G-OPT considerably,
demonstrating that the Rademacher projection matrix should be suggested for
DP-RP.

  * •

DP-OPORP achieves very similar utility (almost overlapping curves) with the
best DP-RP variant, DP-RP-G-OPT-B, in this privacy regime. In practice, DP-
OPORP might be more favorable because of its computational efficiency. These
two methods provide much higher precision and recall than the Gaussian
mechanism applied to the original data. On CIFAR, DP-OPORP performs slightly
better than DP-RP-G-OPT-B, which may partially be explained by the extra
variance reduction factor $\frac{p-k}{p-1}$ of DP-OPORP as in Theorem 3.9 and
Theorem 3.10.

###  5.2 SVM Classification

The RP and SignRP methods can be used to train machine learning models. We
evaluate the performance of DP-SignRP-RR in classification problems trained by
Support Vector Machine (SVM) (Cortes and Vapnik, 1995). We the algorithms on
the WEBSPAM dataset from the LIBSVM website (Chang and Lin, 2011). We apply
the “max normalization”, i.e., divide each data column by its largest
magnitude such that the data entries are bounded in $[0,1]$. As the WEBSPAM
dataset was generated from 3-grams (character $n$-grams), the data vectors are
very high-dimensional and extremely sparse. Thus, this dataset reveals a
serious disadvantage of adding noise directly to the original data, because
adding noise this way generates fully dense data vectors. In order to conduct
the experiments, we only used 10K data samples for training and another 10K
samples for testing and remove all features that are empty. By this
preprocessing, the data dimensionality of the WEBSPAM dataset is reduced from
the original 16 million to “merely” 250K. On the other hand, RP-type of
methods (including OPORP) does not suffer from this problem because with $k$
RP samples we obtain a dataset of only $k$ dimensions.

Figure 12: SVM classification on WEBSPAM, $\beta=1$, $\delta=10^{-6}$.

We report the test accuracy for various DP methods in Figure 12. The
conclusions are similar to those in the retrieval tasks: (i) DP-RP-G-OPT-B and
DP-OPORP attain the highest accuracy among all full-precision RP-type
algorithms, and are significantly better than Raw-data-G-OPT. This experiment
again confirms the effectiveness of DP-RP and DP-OPORP for data privatization.

###  5.3 Results for DP-SignOPORP

Figure 13: Retrieval on MNIST with DP-SignOPORP-RR and DP-SignOPORP-RR-smooth
(in the caption, “-s” stands for “-smooth”. For DP-OPORP and Raw-data-G-OPT,
we let $\delta=10^{-6}$.

Figure 14: Classification accuracy on Webspam with DP-SignOPORP-RR and DP-
SignOPORP-RR-s. For DP-OPORP and Raw-data-G-OPT, we let $\delta=10^{-6}$.

In Figure 13, we plot the precision and recall of DP-SignOPORP-RR (with
standard randomized response), and DP-SignOPORP-RR-smooth (with smooth
flipping probability). In this figure, we present the results with repetition
$t=2,4$ which yield good overall performance. As we can see, (i) the proposed
smooth flipping probability considerably improves the standard randomized
response technique, and (ii) DP-SignOPORP, in general, provides better search
accuracy than DP-OPORP when $\epsilon<10\sim 15$. This range of $\epsilon$ is
common in the use cases of DP for providing reasonable privacy protection.
Also, we note that using a smaller $t$ (repetitions) typically performs better
when $\epsilon$ is relatively small, but worse when $\epsilon$ is large.

In Figure 14, we report the results on SVM classification. For this task, we
plot DP-SignOPORP with $t=1$. We again observe the advantage of DP-SignOPORP
over DP-OPORP, and the advantage of the smooth flipping probability over the
standard randomized response. Specifically, when $\epsilon\approx 5$, the test
accuracy of Raw-data-G-OPT is around 60% (for WEBSPAM this is almost the same
as random guessing), but DP-SignOPORP can achieve 95% accuracy with $k=1024$.

##  6 iDP-SignRP Under Individual Differential Privacy (iDP)

We provide additional algorithms and evaluation on the so-called “individual
differential privacy” (iDP, Definition 2.6) (Soria-Comas et al., 2017), a
relaxation of standard DP which aims at improving the utility of private
algorithms. iDP treats the dataset $u$ as the “ground truth” to be protected.
The “indistinguishability” requirement is only cast on $u$ and its neighbors
specifically, instead of on any possible dataset. Therefore, operationally, in
the noise addition mechanisms for example, iDP essentially follows the local
sensitivity (Definition 2.4) when computing the noise level, which can be much
smaller than that required by the standard DP. iDP has achieved excellent
utility for computing robust statistics at small $\epsilon$ (Soria-Comas et
al., 2017). While iDP does not provide the same level of privacy protection as
the “worst-case” standard DP, it might be sufficient in certain application
scenarios, e.g., data publishing/release, when the procedure is non-
interactive and the released dataset is indeed the target that one is
interested in privatizing.

For the DP algorithms that have been discussed previously in this paper, we
first note that, for DP-RP and DP-OPORP, the local sensitivity at any
$u\in\mathcal{U}$ equals the global sensitivity. In other words, iDP does not
help improve DP-RP and DP-OPORP. Also, we will soon discuss the reason why
SignRP can be much better than SignOPORP under iDP. Therefore, we will mainly
investigate the SignRP algorithms under iDP.

We propose two iDP-SignRP methods, based on noise addition and sign flipping,
respectively. Both approaches share the same key idea of iDP, that is, many
signs of the projected values do not need perturbations. This can be seen from
Figure 6, where the “local flipping probability” is non-zero only in the
regime when the projected data is near $0$ (i.e., $L=1$ in Algorithm 7). Since
in other cases the local flip probability is zero, perturbation is not needed.
As a result, out of $k$ projections, only a fraction of the projected values
needs to be perturbed. This significantly reduces the noise injected to SignRP
and boosts the utility by a very large margin.

###  6.1 iDP-SignRP-G by Gaussian Noise Addition

In Algorithm 9, we present the iDP-SignRP-G method for one data vector $u$. We
use the “local flipping probability” (e.g., in Figure 6) to choose which
projections are perturbed before taking signs. After applying random
projection to get $k$ projected values, we do the following steps:

  1. 1.

We compute noise-indicators $(I_{1},...,I_{k})$ for each projected value in
$x=\frac{1}{\sqrt{k}}W^{T}u$ using Algorithm 10. Denote
$\mathcal{A}=\\{I_{j}:I_{j}=1,j=1,...,k\\}$ and $N_{+}=|\mathcal{A}|$. This is
the maximal number of different signs of $x$ and $x^{\prime}=W^{T}u^{\prime}$,
$\forall u^{\prime}\in Nb(u)$.

  2. 2.

We compute the sensitivity
$\Delta_{2}=\beta\max_{i=1,...,p}\|W_{[i,\mathcal{A}]}\|$, where
$W_{[i,\mathcal{A}]}$ denotes the $i$-th row of $W$ indexed at $\mathcal{A}$,
which is an $N_{+}$-dimensional vector.

  3. 3.

We use the optimal Gaussian mechanism (Theorem 3.5) to compute $\sigma$, with
$\Delta_{2}$ computed above and privacy parameters $(\epsilon,\delta)$.

  4. 4.

For $j=1,..,k$, if $j\notin\mathcal{A}$, we take $\tilde{s}_{j}=sign(x_{j})$;
if $j\in\mathcal{A}$, we take $\tilde{s}_{j}=sign(x_{j}+G)$ where $G\sim
N(0,\sigma^{2})$ is a Gaussian noise. Finally we output
$\tilde{s}=[\tilde{s}_{1},...,\tilde{s}_{k}]$.

1 Input: Data $u\in[-1,1]^{p}$; Privacy parameters $\epsilon>0$,
$\delta\in(0,1)$; Number of projections $k$

2

3Output: Differentially private sign random projections

4Apply RP by $x=\frac{1}{\sqrt{k}}W^{T}u$, where $W\in\mathbb{R}^{p\times k}$
is a random Rademacher matrix

5For every projected value in $x$, compute $(I_{1},...,I_{k})$ by Algorithm 10

6Let $\mathcal{A}=\\{I_{j}:I_{j}=1,j=1,...,k\\}$ and
$\tilde{N}_{+}=|\mathcal{A}|$

7Compute sensitivity $\Delta_{2}=\beta\sqrt{\frac{\tilde{N}_{+}}{k}}$

8Compute $\sigma$ by Theorem 3.5 with $\Delta_{2}$ and privacy budget
$\epsilon$ and $\delta$

9Compute $\tilde{s}_{j}=\begin{cases}sign(x_{j}),&j\notin\mathcal{A}\\\
sign(x_{j}+G),&j\in\mathcal{A}\end{cases}$, where $G\sim N(0,\sigma^{2})$ is
iid Gaussian noise

Return $\tilde{s}=[\tilde{s}_{1},...,\tilde{s}_{k}]$

Algorithm 9 iDP-SignRP-G (DP-SignRP with Gaussian noise)

1 Input: Data $u\in[-1,1]^{p}$; one projected value $z$; adjacency parameter
$\beta$

2Output: Indicator $I$ w.r.t. projection $w$ for data vector $u$

3

4$I=0$

5If $\beta/\sqrt{k}\geq|z|$

6 $I=1$

7End If

Algorithm 10 Compute noise-indicator of iDP-SignRP-G for one projection

Let’s explain the intuition behind DP-SignRP-G. Since a neighboring data
vector $u^{\prime}$ only differs from $u$ in one dimension by at most $\beta$,
for each single projection $w$, when
$\beta\max_{i=1,...,p}|w_{i}|\leq|w^{T}u|$, there is no neighbor $u^{\prime}$
of $u$ that may change the sign of the projected value of $u$, i.e.,
$sign(w^{T}u^{\prime})\neq sign(w^{T}u)$. In other words, when
$\beta\max_{i=1,...,p}|w_{i}|\leq|w^{T}u|$, no noise is needed for this
projected value to attain iDP. This is the reason why we call the output of
Algorithm 10 a “noise-indicator”. Consequently, in step 4 of iDP-SignRP-G it
suffices to add Gaussian noise only to those projected values $x_{j}$ with
$j\in\mathcal{A}$, instead of to all $k$ projections as in DP-RP-G-OPT.

######  Theorem 6.1 (iDP-SignRP-G).

Algorithm 9 is $(\epsilon,\delta)$-iDP for data $u$.

###### Proof.

For a data vector $u$, let $Nb(u)$ be its neighbor set with vectors that
differ from $u$ by at most $\beta$ in one dimension. Denote
$x=\frac{1}{\sqrt{k}}W^{T}u$ and
$x^{\prime}=\frac{1}{\sqrt{k}}W^{T}u^{\prime}$. Let $(I_{1},...,I_{k})$ be the
noise-indicators from Algorithm 10 and $\mathcal{A}=\\{i:I_{j}=1\\}$,
$\tilde{N}_{+}=|\mathcal{A}|$. Consider the two sets separately:

  * •

For $j\in[k]\setminus\mathcal{A}$, by the condition $\beta/\sqrt{k}\leq|z|$,
we know that $\forall u^{\prime}\in Nb(u)$, it holds that
$sign(x_{i})=sign(x_{i}^{\prime})$.

  * •

For $j\in\mathcal{A}$, consider the sub-vector $x_{\mathcal{A}}$. Adding iid
Gaussian noise to $x_{\mathcal{A}}$ according to Theorem 3.5 with
$\Delta_{2}=\beta\sqrt{\frac{\tilde{N}_{+}}{k}}$ ensures the
$(\epsilon,\delta)$-DP of $x_{\mathcal{A}}$. By the post-processing property
of DP, we know that $sign(x_{\mathcal{A}})$ is also $(\epsilon,\delta)$-DP.
Thus, for any $Q\in\\{-1,1\\}^{N_{+}}$, we have
$Pr(sign(x_{\mathcal{A}})=Q)-e^{\epsilon}Pr(sign(x^{\prime}_{\mathcal{A}})=Q)\leq\delta$,
$\forall u^{\prime}\in Nb(u)$.

Combining two parts, we have for any $Q\in\\{-1,1\\}^{k}$,

$\displaystyle
Pr(sign(x)=Q)-e^{\epsilon}Pr(sign(x^{\prime})=Q)=Pr(sign(x_{\mathcal{A}})=Q)-e^{\epsilon}Pr(sign(x^{\prime}_{\mathcal{A}})=Q)\leq\delta,$

for all $u^{\prime}\in Nb(u)$. By the symmetry of DP (on the sub-vector
$x_{\mathcal{A}}$), we also know that
$Pr(sign(x^{\prime})=Q)-e^{\epsilon}Pr(sign(x)=Q)\leq\delta$. This proves the
$(\epsilon,\delta)$-iDP by Definition 2.6. ∎

###  6.2 iDP-SignRP-RR by Randomized Response

1 Input: Data $u\in[-1,1]^{p}$, privacy parameters $\epsilon>0$, $0<\delta<1$,
number of projections $k$

2

3Output: Differentially private sign random projections

4

5Apply RP by $x=\frac{1}{\sqrt{k}}W^{T}u$, where $W\in\mathbb{R}^{p\times k}$
is a random Rademacher matrix

6For every column in $W$, compute $(I_{1},...,I_{k})$ by Algorithm 10

7Let $\mathcal{A}=\\{I_{j}:I_{j}=1,j=1,...,k\\}$ and
$\tilde{N}_{+}=|\mathcal{A}|$

8Compute $\tilde{s}_{j}=\begin{cases}sign(x_{j}),&j\notin\mathcal{A}\\\
sign(x_{j}),&j\in\mathcal{A}\ \text{with prob.}\
\frac{e^{\epsilon^{\prime}}}{e^{\epsilon^{\prime}}+1}\\\
-sign(x_{j}),&j\in\mathcal{A}\ \text{with prob.}\
\frac{1}{e^{\epsilon^{\prime}}+1}\end{cases}$ for $j=1,...,k$, with
$\epsilon^{\prime}=\epsilon/\tilde{N}_{+}$

Return $\tilde{s}$ as the DP-SignRP of $u$

Algorithm 11 iDP-SignRP-RR

Similar to Section 4, we also have an iDP-SignRP-RR method with pure
$\epsilon$-DP by random sign flipping, as summarized in Algorithm 11. After we
apply random projection $x=\frac{1}{\sqrt{k}}W^{T}u$, we call the same
procedure as in iDP-SignRP-G to determine set $\mathcal{A}$ representing the
projected values that need perturbation for iDP. For $j\notin\mathcal{A}$, we
use the original $\tilde{s}_{j}=sign(x_{j})$. For $j\in\mathcal{A}$, we keep
$sign(x_{j})$ with probability
$\frac{e^{\epsilon^{\prime}}}{e^{\epsilon^{\prime}}+1}$ and flip the sign
otherwise, where $e^{\epsilon^{\prime}}=\epsilon/\tilde{N}_{+}$ with
$\tilde{N}_{+}=|\mathcal{A}|$.

######  Theorem 6.2.

Algorithm 11 achieves $\epsilon$-iDP for data $u$.

###### Proof.

The high-level proof idea is similar to that of Theorem 6.1. For
$u\in[-1,1]^{p}$ let $u^{\prime}$ be an $\beta$-neighboring data. Let
$s=sign(W^{T}u)\in\\{-1,+1\\}^{k}$,
$s^{\prime}=sign(W^{T}u^{\prime})\in\\{-1,+1\\}^{k}$, and denote $\tilde{s}$
and $\tilde{s}^{\prime}$ as the randomized output of $s$ and $s^{\prime}$ by
Algorithm 11, respectively. Consider $\mathcal{A}$ in Algorithm 11. By
Algorithm 10, we know that for $j\notin\mathcal{A}$,
$Pr(\tilde{s}_{j}=\tilde{s}_{j}^{\prime})=Pr(s_{j}=s_{j}^{\prime})=1$,
$\forall u^{\prime}\in Nb(u)$. For projections in $\mathcal{A}$, denote
$S=\\{j\in\mathcal{A}:s_{j}\neq s_{j}^{\prime}\\}$ and
$S^{c}=\mathcal{A}\setminus S$. For any vector $y\in\\{-1,+1\\}^{k}$, we
further define $S_{0}=\\{j\in S:s_{j}=y_{j}\\}$, $S_{1}=\\{j\in S:s_{j}\neq
y_{j}\\}$, $S^{c}_{0}=\\{j\in S^{c}:s_{j}=y_{j}\\}$ and $S^{c}_{1}=\\{j\in
S^{c}:s_{j}\neq y_{j}\\}$. Since the $k$ projections are independent, by
composition we have

$\displaystyle\log\frac{Pr(\tilde{s}=y)}{Pr(\tilde{s}^{\prime}=y)}$
$\displaystyle=\log\frac{\prod_{j\notin\mathcal{A}}Pr(\tilde{s}_{j}=y_{j})\prod_{j\in
S^{c}_{0}}\frac{e^{\epsilon^{\prime}}}{e^{\epsilon^{\prime}}+1}\prod_{j\in
S^{c}_{1}}\frac{1}{e^{\epsilon^{\prime}}+1}\prod_{j\in
S_{0}}\frac{e^{\epsilon^{\prime}}}{e^{\epsilon^{\prime}}+1}\prod_{j\in
S_{1}}\frac{1}{e^{\epsilon^{\prime}}+1}}{\prod_{j\notin\mathcal{A}}Pr(\tilde{s}_{j}^{\prime}=y_{j})\prod_{j\in
S^{c}_{0}}\frac{e^{\epsilon^{\prime}}}{e^{\epsilon^{\prime}}+1}\prod_{j\in
S^{c}_{1}}\frac{1}{e^{\epsilon^{\prime}}+1}\prod_{j\in
S_{0}}\frac{1}{e^{\epsilon^{\prime}}+1}\prod_{j\in
S_{1}}\frac{e^{\epsilon^{\prime}}}{e^{\epsilon^{\prime}}+1}}$
$\displaystyle\leq\log\frac{\prod_{j\in
S}\frac{e^{\epsilon^{\prime}}}{e^{\epsilon^{\prime}}+1}}{\prod_{j\in
S}\frac{1}{e^{\epsilon^{\prime}}+1}}=|S|\epsilon^{\prime}\leq\tilde{N}_{+}\epsilon^{\prime}=\epsilon,$

which proves the $\epsilon$-iDP according to Definition 2.6. ∎

The number of projections that requires noise addition, $\tilde{N}_{+}$, is
also tightly related to the $P_{+}(\|u\|,p)$ (Proposition 4.5 and (26)).
Particularly, $\tilde{N}_{+}$ would be small when the data has a relatively
large norm compared with the change in neighboring data $\beta$. Therefore,
both iDP-SignRP methods would have better utility when the data norm is large.
The reduction from $k$ to $\tilde{N}_{+}$ also leads to smaller Gaussian noise
or smaller flipping probability for the values that need to be perturbed.
Specifically, note that in Algorithm 9, the optimal Gaussian mechanism is
deployed with sensitivity $\Delta_{2}=\beta\sqrt{\frac{\tilde{N}_{+}}{k}}$,
instead of $\Delta_{2}=\beta$ as in (13) for DP-RP-G-OPT.

iDP-SignOPORP. Similarly, we can also apply iDP to the SignOPORP method.
Basically, we only need to replace $x$ in Line 3 in both Algorithm 9 and
Algorithm 11 by the OPORP of $u$. However, we note that this iDP-SignOPORP
procedure is considerably worse than iDP-SignRP in performance. This is
because, by the binning step in OPORP, the average scale of each projected
value becomes much smaller. This implies that in Algorithm 10, the magnitude
of $z$ would be much smaller, so a lot more projected values will require
perturbation, which leads to a utility loss. This illustrates the superiority
of SignRP under iDP: since each RP aggregates the whole data vector, SignRP is
more robust to a small change in the data. Hence, less noise is needed.

###  6.3 Empirical Results on iDP

Figure 15: Retrieval on MNIST with iDP-SignRP, $\beta=1$, $\delta=10^{-6}$.

Figure 16: SVM on WEBSPAM with iDP-SignRP, $\beta=1$, $\delta=10^{-6}$.

To demonstrate the empirical gain in utility of iDP-SignRP, we conduct the
same set of experiments as in Section 5. Figure 15 reports the precision and
recall on MNIST, and Figure 16 presents the SVM test accuracy on WEBSPAM. As
we can see, iDP-SignRP achieves very high utility even when $\epsilon<0.1$. We
see that the curves of iDP-SignRP are almost flat. This is because only a
small fraction of projected values are perturbed, so the untouched projected
values already provide rich information for search and classification. In
other words, the experimental results illustrate that the SignRP itself is
already very strong in protecting the individual differential privacy. In
other words, SignRP itself is already a strong method to protect the privacy
of each specific dataset with respect to the individual DP, e.g., in non-
interactive data publishing tasks.

##  7 Conclusion

The concept of differential privacy (DP) has been widely accepted as an
elegant mathematical framework for protecting data privacy. In practice,
however, deploying DP algorithms often leads to considerably worse performance
(utility). For example, if we directly add noise to high-dimensional data
vectors, the required noise level (i.e., the variance of the noise random
variables) is often quite high which can severely degrade the performance of
the subsequent tasks. Furthermore, inserting noise to the original data
completely destroys data sparsity. For example, in text data or data for
commercial advertising CTR models, for each data vector, typically only a very
small fraction of the coordinates are non-zero. Adding noise to the original
dataset can easily generate dense vectors in millions or even billions
dimensions. Therefore, DP algorithms based on random projections (RP), which
is an effective tool for dimension reduction, can be desirable. This is our
motivation.

Our key contribution is the observation that the signs of the randomly
projected data vectors can be very stable when the original data vectors are
perturbed. That is, we let $x=\sum_{i=1}^{p}u_{i}w_{i}$, where $u$ is the
original $p$-dimensional data vector and $w$ is a projection vector. The sign
$sign(x)=sign\left(\sum_{i=1}^{p}u_{i}w_{i}\right)$ can be changed if $u$ is
modified to be $u^{\prime}$, with a probability which depends on the choice of
the distribution of $w$. Our study reveals that such (sign-flipping)
probability can be quite low (e.g., $<0.1$), under the common definition of
“neighbors” in DP. This is the basis for our work.

In this study, we have developed two lines of strategies for taking advantage
of this sign-flipping probability. By leveraging the idea of smooth
sensitivity, we propose a “smooth flipping” strategy which satisfies the
rigorous definition of DP. The algorithm we recommend is named DP-SignOPORP by
using a variant of the count-sketch for generating the projection vectors. In
a recent work, Li and Li (2023a) proposed “one-permutation + one random
projection” (OPORP) which improves the original count-sketch in two aspects:
(i) fixed-length binning, and (ii) normalization. In this study, we have
observed that DP-SignOPORP noticeably outperforms other DP-RP algorithms.

We have also exploited the other direction for utilizing the sign-flipping
probability of random projections, by leveraging the concept of “individual
differential privacy” (iDP) and “local sensitivity”. The proposed “iDP-SignRP”
algorithms perform remarkably well, in that they are able to achieve excellent
utility even at very small $\epsilon$ values (e.g., $\epsilon<0.5$). Although
iDP does not strictly satisfy DP, it is anticipated that iDP might be still
useful for certain applications such as releasing datasets.

The family of DP-RP and DP-SignRP algorithms can be conveniently used in
training AI models for protecting the privacy of input features. A notable use
case would be the embedding-based retrieval (EBR), which is nowadays widely
adopted in commercial applications. Embeddings are trained/stored and then
might be shared across different countries/companies/business units. For
example, it is common that embeddings trained from one model might be used as
the input feature data for other models. Understandably, privacy alarms might
be triggered in those applications.

## Acknowledgement

The authors would like to thank colleagues from Microsoft Research: Janardhan
Kulkarni, Yin Tat Lee, Sergey Yekhanin, for helpful discussions.

## References

  * Abadi et al. (2016) Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS)_ , pages 308–318, Vienna, Austria, 2016\.
  * Achlioptas (2003) Dimitris Achlioptas.  Database-friendly random projections: Johnson-lindenstrauss with binary coins.  _J. Comput. Syst. Sci._ , 66(4):671–687, 2003\.
  * Agarwal et al. (2018) Naman Agarwal, Ananda Theertha Suresh, Felix X. Yu, Sanjiv Kumar, and Brendan McMahan.  cpSGD: Communication-efficient and differentially-private distributed SGD.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pages 7575–7586, Montréal, Canada, 2018.
  * AlOmar et al. (2021) Eman Abdullah AlOmar, Wajdi Aljedaani, Murtaza Tamjeed, Mohamed Wiem Mkaouer, and Yasmine N. El-Glaly.  Finding the needle in a haystack: On the automatic identification of accessibility user reviews.  In _Proceedings of the Conference on Human Factors in Computing Systems (CHI)_ , pages 387:1–387:15, Virtual Event / Yokohama, Japan, 2021.
  * Balle and Wang (2018) Borja Balle and Yu-Xiang Wang.  Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising.  In _Proceedings of the 35th International Conference on Machine Learning (ICML)_ , pages 403–412, Stockholmsmässan, Stockholm, Sweden, 2018\.
  * Beigi et al. (2020) Ghazaleh Beigi, Ahmadreza Mosallanezhad, Ruocheng Guo, Hamidreza Alvari, Alexander Nou, and Huan Liu.  Privacy-aware recommendation with private-attribute protection using adversarial learning.  In _Proceedings of the Thirteenth ACM International Conference on Web Search and Data Mining (WSDM)_ , pages 34–42, Houston, TX, USA, 2020.
  * Berlioz et al. (2015) Arnaud Berlioz, Arik Friedman, Mohamed Ali Kâafar, Roksana Boreli, and Shlomo Berkovsky.  Applying differential privacy to matrix factorization.  In _Proceedings of the 9th ACM Conference on Recommender Systems (RecSys)_ , pages 107–114, Vienna, Austria, 2015.
  * Bingham and Mannila (2001) Ella Bingham and Heikki Mannila.  Random projection in dimensionality reduction: Applications to image and text data.  In _Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)_ , pages 245–250, San Francisco, CA, 2001.