Abstract
With the rapid growth of digital platforms, there is increasing apprehension about how personal data is being collected, stored, and used by various entities. These concerns range from data breaches and cyber-attacks to potential misuse of personal information for targeted advertising and surveillance. As a result, differential privacy (DP) has emerged as a prominent tool for quantifying a system’s level of protection. The Gaussian mechanism is commonly used because the Gaussian density is closed under convolution, a common method utilized when aggregating datasets. However, the Gaussian mechanism only satisfies approximate differential privacy. In this work, we present novel analysis of the Symmetric alpha-Stable (SaS) mechanism. We prove that the mechanism is purely differentially private while remaining closed under convolution. From our analysis, we believe the SaS Mechanism is an appealing choice for privacy focused applications.
INTRODUCTION
Privacy is fundamental to individual autonomy, rights, and personal safety. It protects individuals from harassment and discrimination, fosters trust in institutions, and encourages free speech and innovation. As the world becomes increasingly digital, we have seen a corresponding rise data breaches targeting the growing number of individual databases holding client information [@itrc22]. The public and private sectors have begun to act. Political leaders are taking actions to ensure the privacy of their citizens [@transparency11; @GDPR18], and consumers are putting pressure on companies to adopt settings and methods that focus on the privacy of their customers [@koetsier21; @minto21].
For example, in a healthcare context, an institution might want to disclose a histogram of blood glucose levels in a particular treatment group as evidence of a trials success. To prevent an adversarial agent from learning about which individuals make up the dataset, the institution can inject the dataset with differentially private noise. This provides bounds on the maximal amount of privacy that could be lost while allowing the results of the study to be made public.
Differential Privacy (DP) is a method of noise injection that allows for quantifiable guarantees about the amount of information that can be leaked when an individual participates in a machine learning dataset [@dwork06; @dwork06b]. By perturbing datasets with random noise from a carefully selected density, DP ensures that the statistical results of any analysis remain accurate while protecting the identity and sensitive information of participating clients. The differential privacy framework has been applied in various domains, from large-scale data analytic to machine learning [@abadi16]. More recently, differential privacy has had renewed focus within the field of federated learning (FL), a privacy focused branch of machine learning [@mcmahan16]. The objective of differentially private FL methods are to enhance privacy preservation while collaboratively training machine learning models across multiple decentralized devices or servers [@wei20]. In [@li19b], the authors use differentially private federated learning methods to train a machine learning model that segments images of brain tumors.
The work most similar to the results presented here are from Ito et. al. [@ito21], who use heavy tailed distributions to mask contributions by outliers in the context of filter/controller design for control systems. Our results differ in the level of privacy guaranteed by the privacy mechanism.
The contributions of this work are twofold. First we present a privacy mechanism that uses stable densities and prove that this mechanism is \(\varepsilon\)-differentially private. Second, we compare the expected distortion of our privacy mechanism against other commonly utilized privacy mechanisms.
The rest of the paper is organized as follows. Section 3 summarises the basics of differential privacy. Section 4 introduces the definition of the Symmetric alpha Stable Mechanism. Section 5 proves the privacy guarantee of the new mechanism. Section 7 provides a measure of error the mechanism introduces to statistical queries. Lastly, section 8 summarizes the results and comments on active research efforts.
BACKGROUND
In this section, we outline the background material required to derive our results.
Differential Privacy
Differential privacy is a method of obfuscation that operates on a collaboratively constructed dataset \(\mathcal{D}\) [@dwork06; @roth14]. It is common to consider such a dataset as a tabulated set of records, where each row holds a vector of client data.
Let \(f\) be a function that operates on a dataset and returns a vector of \(m\) numerical values. For example,
How many clients have blue eyes?
What is the average income?
What are the optimized parameters of a given machine learning model over all the clients?
By a slight abuse of notation, we use the same symbol \(f\) for the function regardless of the size of the dataset.
Definition 1. (Bounded Query) We call a function \(f\) a bounded query if it takes as input a dataset \(\mathcal{D}\) and returns a vector, of positive dimension \(m\), taking values in compact subsets of the real line: \[f: \mathcal{D} \to [a_i, b_i]^m, \ a_i,b_i \in \mathbb{R},\] with \(i \in \{1, 2, ..., m\}\). \[\tag*{$\blacktriangleleft$}\]
More commonly, a query \(f\) is allowed to be unbounded with differential privacy methods restricting the queries to those with finite \(\ell_p\)-sensitivity [@dwork06; @roth14]:
Definition 2. (\(\ell_p\)-Sensitivity of Query) The \(\ell_p\)-sensitivity of a query \(f\), denoted \(\Delta_pf\), is defined to be a maximum of a \(p-\)norm over the domain of \(f\), \(dom(f)\): \[\Delta_pf := \max_{\mathcal{D}_1\simeq \mathcal{D}_2} ||f(\mathcal{D}_1) - f(\mathcal{D}_2)||_p,\] for all \(\mathcal{D}_1, \mathcal{D}_2 \in dom(f)\).
\[\tag*{$\blacktriangleleft$}\]
It is evident from Definitions 1 and 2 that if and only if a query \(f\) is bounded, the sensitivity of \(f\) is also bounded. It simplifies our analysis to assume the query is bounded, which is tantamount to the assumption in the literature that the \(\ell_p\)-sensitivity is bounded.
Definition 3. (Privacy Mechanism) A privacy mechanism for the query \(f\), denoted \(\mathcal{M}_f\), is defined to be a randomized algorithm that returns the result of the query perturbed by a vector of pre-selected i.i.d. noise variables \(Y_i\), \[\mathcal{M}_f(\mathcal{D}) = f(\mathcal{D}) + (Y_1, Y_2, \dots, Y_m)^T,\] for all \(i \in \{1, \dots, m\}\).
\[\tag*{$\blacktriangleleft$}\]
It will be useful to denote the vector \(\mathcal{M}_f(\mathcal{D})\) as \(\textbf{x}\in\mathbb{R}^m\). Note that the noise variables, \(Y_i\), induce a density, which we denote \(p = p(\textbf{x})\) for \(\mathcal{M}_f\), on a given dataset \(\mathcal{D}\). While not strictly necessary, we assume the injected density is symmetric about the origin. This assumption simplifies the analysis.
Let us now consider two possible groups of clients depicted in Figure 1. In one scenario, the red client has decided to included their data in the dataset and, in the other, the red client chooses to withhold their data. Let \(\mathcal{D}_1\) and \(\mathcal{D}_2\) represent these two scenarios respectively . To proceed, let us assume the red client has allowed their data in the set and so \(\mathcal{D}_1\) is the true dataset. Denote a realization of a mechanism as \(x \sim \mathcal{M}_f(\mathcal{D}_2)\). Informally, the mechanism \(\mathcal{M}_f\) is said to be differentially private if the inclusion or exclusion of a single individual in the dataset, illustrated in red in the figure, results in roughly the same distribution over the realized outputs \(x\), \[\Pr[\mathcal{M}_f(\mathcal{D}_1) = x] \approx \Pr[\mathcal{M}_f(\mathcal{D}_2) = x].\]
The privacy mechanism aims to hinder an adversary from conclusively ascertaining the presence of the red client within the dataset. Next, we proceed to quantify this intuition.
Definition 4. (Neighboring Datasets) Two datasets, denoted by \(\mathcal{D}_1\) and \(\mathcal{D}_2\), are known as neighboring datasets if they differ in the presence or absence of exactly one client record. We denote this relation as \(\mathcal{D}_1\simeq \mathcal{D}_2\).
\[\tag*{$\blacktriangleleft$}\]
Definition 5. (Pure Differential Privacy) Let \(\mathcal{D}_1\) and \(\mathcal{D}_2\) be any neighboring datasets. Given a query \(f\) that operates on \(\mathcal{D}_1\) and \(\mathcal{D}_2\), a privacy mechanism \(\mathcal{M}_f\) is said to be \(\varepsilon\)-differentially private (\(\varepsilon\)-DP) if it satisfies \[\label{eqn:pureDP} \Pr[\mathcal{M}_f(\mathcal{D}_1) \in \mathcal{X}] \leq e^\varepsilon \Pr[\mathcal{M}_f(\mathcal{D}_2) \in \mathcal{X}]\] for some \(\varepsilon > 0\) and any subset of outputs \(\mathcal{X} \subseteq \mathcal{R}(\mathcal{M}_f(\mathcal{D}_1))\). The mechanism is defined to have no privacy (\(\epsilon = \infty\)) if, upon its application to each dataset, the supports of the resulting densities are not equal, viz. \(\mathcal{R}(\mathcal{M}_f(\mathcal{D}_1)) \neq \mathcal{R}(\mathcal{M}_f(\mathcal{D}_2))\).
\[\tag*{$\blacktriangleleft$}\]
Remark 1. We note that Eq. [eqn:pureDP] holds for each element when the density of the distributions is considered [@roth14]: \[\label{eqn:purepdf} p_1(x) \leq e^\varepsilon p_2(x), \quad \forall x \in \mathcal{R}(\mathcal{M}_f(\mathcal{D}_1))\]
The parameter \(\varepsilon\) is also referred to as the privacy budget. Smaller values of \(\varepsilon\) are, in general, associated with stronger privacy. We remark that when \(\varepsilon=0\), the definition yields perfect privacy. However, in that case, adding more client data results in no new information.
Definition 6. (Privacy Loss) The privacy loss of an outcome \(x\) is defined to be the log-ratio of the densities when the mechanism is applied to \(\mathcal{D}_1\) and \(\mathcal{D}_2\) at \(x\) [@roth14]: \[\label{eqn:plf} \mathcal{L}_{\mathcal{D}_1 || \mathcal{D}_2}(x) := \ln \frac{p_1(x)}{p_2(x)}.\] By ([eqn:purepdf]), it is evident that \(\varepsilon\)-differential privacy ([eqn:pureDP]) is equivalent to \[|\mathcal{L}_{\mathcal{D}_1||\mathcal{D}_2}(x)| \leq \varepsilon, \quad \forall x \in \mathcal{R}(\mathcal{M}_f(\mathcal{D}_1))\] for all neighboring datasets \(\mathcal{D}_1\) and \(\mathcal{D}_2\).
\[\tag*{$\blacktriangleleft$}\]
For mechanisms that are purely differential private, the privacy budget \(\varepsilon\) is the maximum over all observations \(x\), \[\label{eqn:epmax} \varepsilon = \max_{x\in\mathbb{R}}\mathcal{L}_{\mathcal{D}_1||{D}_2}(x).\]
Some mechanisms, such as the Gaussian mechanism [@dwork06b; @roth14], fail to satisfy condition ([eqn:pureDP]). The condition can be relaxed through the inclusion of an additive constant \(\delta > 0\), as in the following definition:
Definition 7. (Approximate Differential Privacy) Let \(\mathcal{D}_1\) and \(\mathcal{D}_2\) be any neighboring datasets. Given a query \(f\) that operates on \(\mathcal{D}_1\) and \(\mathcal{D}_2\), a privacy mechanism \(\mathcal{M}_f\) is said to be \((\varepsilon, \delta)\)-differentially private if it satisfies \[\label{eqn:approxDP} \Pr[\mathcal{M}_f(\mathcal{D}_1) \in \mathcal{X}] \leq e^\varepsilon \Pr[\mathcal{M}_f(\mathcal{D}_2) \in \mathcal{X}] + \delta.\] This is known as approximate differential privacy.
\[\tag*{$\blacktriangleleft$}\]
Commonly, a mechanism is defined in relation to a query over the entire dataset \(\mathcal{D}\). It is then understood that the mechanism is applied by a trusted aggregator, which collects the clients’ data prior to obfuscation. However, there does not always exist such a trusted central authority. For example, in a federated learning framework, the server is assumed untrustworthy by default. Moreover, a lack of secure communication protocols could result in an adversary gaining access to the transmission between the clients and server. To this end, a mechanism \(\mathcal{M}_f\) is said to be locally differentially (LDP) private if the mechanism can be applied locally by the clients prior to transmission to the server.
Definition 8. (Local Differential Privacy) A privacy mechanism \(\mathcal{M}^{loc}_f\) is said to be locally differentially private if, when applied to a client’s local dataset \(\mathcal{D}\), satisfies for any pair of datapoints \(v_1, v_2 \in \mathcal{D}\) the following [@kasiviswanathan11]: \[\label{eqn:LDP} \Pr[\mathcal{M}^{loc}_f(v_1) \in \mathcal{X}] \leq e^\varepsilon \Pr[\mathcal{M}^{loc}_f(v_2) \in \mathcal{X}] + \delta,\] for all \(\mathcal{X} \in \mathcal{R}(\mathcal{M}^{loc}_f)\).
\[\tag*{$\blacktriangleleft$}\]
The mechanism is called \(\varepsilon\)-LDP if \(\delta=0\) and \((\varepsilon, \delta)\)-LDP otherwise.
Selecting a Level of Privacy
Wasserman and Zhou describe in [@wasserman09] a useful connection between differential privacy and hypothesis testing. Their analysis considers the problem of client privacy from the perspective of an adversary deciding between two hypothesises. Denote by \(\mathcal{D}_1\) and \(\mathcal{D}_2\) two neighboring datasets. Let one of the following hypothesises hold:
\(H_0\) (The null hypothesis): the true dataset is \(\mathcal{D}_1\).
\(H_1\) (The alternative hypothesis): the true dataset is \(\mathcal{D}_2\).
The objective of the adversary is to determine, based on the output of a privacy mechanism \(\mathcal{M}_f\), which hypothesis is true. Denote by \(p\) the probability of a false positive, that is, the adversary chooses \(H_1\) when \(H_0\) is true. Then, denote by \(q\) the probability of a false negative, i.e., \(H_0\) is chosen when \(H_1\) is true. Wasserman and Zhou show that if a mechanism \(\mathcal{M}_f\) is \(\varepsilon\)-differentially private, then the following two statements must hold: \[\label{eqn:h0} p + e^\varepsilon q \geq 1 \textrm{ and } e^{\varepsilon}p + q \geq 1.\]
Combining the inequalities in ([eqn:h0]) yields \[\label{eqn:h2} p + q \geq \frac{2}{1 + e^\varepsilon}.\] Consider that when \(\varepsilon << 1\), which equates to high privacy, the adversary cannot achieve both low false positive and low false negative rates simultaneously. Often, it is more convenient to specify lower bounds for \(p\) and \(q\) and to use ([eqn:h2]) to determine \(\varepsilon\) than it is to state the privacy budget directly.
The Symmetric alpha-Stable Mechanism
The Gaussian density constitutes one of the main privacy mechanisms in differential privacy. One major benefit is the ease with which Gaussian perturbations fit into existing Machine Learning analyses. The Gaussian density owes its pervasiveness to its essential role in the Central Limit Theorem (CLT) [@billingsley95Thm. 27.1]. One important property is that the density is closed under convolutions. This means two Gaussian estimates can be combined and the result remains Gaussian.
We note that the Gaussian density is a member of a family of densities with this property, known as the Lévy alpha-Stable density [@levy25]. In the context of Differential Privacy, the Gaussian mechanism only satisfies condition ([eqn:approxDP]), approximate differential privacy [@dwork06b; @roth14]. In this section, we examine the privacy properties of the mechanisms based on the family of stable densities. We introduce the Symmetric alpha-Stable mechanism and prove it satisfies condition ([eqn:pureDP]), \(\varepsilon\)-DP.
The Family of Stable Densities
The family of stable densities was first studied in generality by Lévy in 1925 [@levy25] and is defined to be the class of probability densities that are closed under convolution.
Definition 9. (The Stable Family) Let \(Y_1\) and \(Y_2\) be two independent and identically distributed random variables following probability density \(Y\). The density \(Y\) is said to be stable if for any constants \(a, b > 0\) there exist constants \(c(a,b) > 0\) and \(d(a,b) \in \mathbb{R}\) such that \[aY_1 + bY_2 = cY+d.\] If \(d=0\), the distribution is known as strictly stable.
\[\tag*{$\blacktriangleleft$}\]
Aside from a few special cases, there is no known closed form for the density of a general stable density [@nolan20]. However, there are several known parameterizations of the characteristic function of a density in the stable family [@nolan20]. One common form of the characterised function is \[\label{eqn:char} \varphi(t; \alpha, \beta, \gamma, \mu) = \exp({it\mu - |\gamma t|^\alpha + i \beta \textrm{sgn}(t) \Phi(t)}),\] with \[\Phi(t) = \begin{cases} \tan(\frac{\pi \alpha}{2}) & \alpha \neq 1 \\ -\frac{2}{\pi}\log|t| & \alpha = 1. \end{cases}\] The density can then be expressed by the integral \[\label{eqn:stab} p(x; \alpha, \beta, \gamma, \mu) = \frac{1}{2\pi}\int_{-\infty}^{\infty}\varphi(t; \alpha, \beta, \gamma, \mu)e^{-ixt}dt.\] We present three example of the symmetric form, with \(\beta=0\), in Figure 2: \(\alpha=1\) (blue), \(\alpha=1.5\) (orange), and \(\alpha=2\) (green). Each graph is standardized with a location of \(\mu=0\) and a scale of \(\gamma=1\).
The two forms, \(\alpha=1\) and \(\alpha=2\), are the Cauchy and Gaussian densities respectively.
The largest challenge when working with the family of stable distributions is the lack of a closed form solution for the general density. This is, in part, due to the fact that the value at an individual point is given by the integral of an infinitely oscillating function. Denote the real part of the integrand of ([eqn:stab]) by \(q(t;x)\), then a depiction with \(x=10\) can be found in Figure 3.
![Figure 3: This graph depicts the real part of the integrand of ([eqn:stab]) (which is an oscillating function) for \alpha=1.5, \gamma=1, and \mu=0. The value of the stable density at a given point x is the integral of this oscillating function.](/files/images/sas-mech/slice_of_density.png)
For ([eqn:stab]) to constitute a probability density, the parameter \(\alpha\) is constrained to lie within the interval \((0,2]\). The value of \(\alpha\) determines the rate of decay of the tail of the density. The mean of the density is undefined for \(\alpha \leq 1\) and defined for \(\alpha > 1\). The density has infinite variance for \(\alpha \in (0,2)\) and finite variance only when \(\alpha=2\). In this work, we restrict \(\alpha \in (1, 2]\), leaving median or mode estimators for future research. The parameter \(\beta\), restricted to \((-1,1)\), is a measure related to skewness (the strict definition of skewness is not meaningful for \(\alpha < 2\)). We focus on symmetric alpha-stable (SaS) densities which are defined to be the case where \(\beta=0\): \[\label{eqn:sas} \begin{aligned} p_{SaS}(x;\alpha, \gamma, \mu) & := \\ p(x;\alpha, 0, \gamma, \mu) & = \frac{1}{2\pi}\int_{-\infty}^{\infty}e^{-|\gamma t|^\alpha - it(x-\mu)}dt. \end{aligned}\] SaS densities have a known closed form for two values of the parameter \(\alpha\): the Cauchy, for \(\alpha = 1\), and the Gaussian, for \(\alpha=2\). The last two parameters, \(\gamma > 0\) and \(\mu\in\mathbb{R}\), are the scale and location parameters respectively.
Remark 2. For stable densities, it is common for the location parameter to be denoted \(\delta\) rather than \(\mu\), to signify that it is not always equal to the expected value. In our context, we choose \(\mu\) to reserve \(\delta\) for the definition of approximate differential privacy ([eqn:approxDP]) as is common in the differential privacy literature. Because we are restricting the domain of interest to \(\alpha \in (1,2]\), we do not believe this notation will be cause for confusion.
Definition 10. (The Symmetric alpha-Stable Mechanism) For a given dataset \(\mathcal{D}\) and a query function \(f\), we define a privacy mechanism \(\mathcal{M}_f\) to be a Symmetric alpha-Stable (SaS) mechanism if each element of the vector of injected values, \(Y_i\) for \(i\in\{1,...,m\}\), is drawn independently from a SaS density
\[p_{SaS}(x; \alpha, \gamma, 0) = \frac{1}{2\pi}\int_{-\infty}^{\infty}e^{-|\gamma t|^\alpha - itx}dt.\]
\[\tag*{$\blacktriangleleft$}\]
In this section, we proceed to prove that the SaS Mechanism for \(\alpha\in[1,2)\) satisfies ([eqn:pureDP]), \(\varepsilon\)-differential privacy.
Pure-Differential Privacy of SaS Mechanism
The main difficulty in working with stable densities, other than the Cauchy and Gaussian, is that they have no known closed form and consist of the integral of an infinite sequence of oscillating intervals. In this section, we first establish the following lemmas and then we prove that the SaS Mechanism is \(\varepsilon\)-DP when \(\alpha\) is restricted to \([1,2)\).
To establish that the privacy loss is finite on a compact set, it is essential to ensure that the stable distribution possesses support over the entire real number line.
Lemma 1. (Support of SaS Density) The support of the symmetric alpha-stable density ([eqn:sas]) is \(\mathbb{R}\).
Proof. See [@nolan20Lemma 1.1]. ◻
Next, we recall a partial sum expansion described by Bergström [@bergstrom52] where the remainder term has a smaller order of magnitude (for large \(|x|\)) then the final term in the series.
Lemma 2. (Finite Series Expansion of SaS Distribution) The symmetric alpha-stable density ([eqn:sas]), with \(\alpha \in [1,2)\) and \(\gamma=1\), has the following finite series expansion: \[\label{eqn:ser} \begin{aligned} & p_{SaS}(x; \alpha, 1, 0) = \\ & - \frac{1}{\pi} \sum_{k=1}^n (-1)^k \frac{\Gamma(\alpha k+1)}{(x)^{\alpha k + 1}} \sin \bigg( \frac{k \alpha \pi}{2} \bigg) + O\bigg(x^{-\alpha(n+1)-1}\bigg), \end{aligned}\] for \(|x| \to \infty\).
Proof. The proof provided by Bergström [@bergstrom52] employs an expanded form that is satisfied for the full range \(\beta \in (-1, 1)\). We only require ([eqn:ser]) and so leave out the full form. ◻
We use the foregoing lemma to argue that the privacy loss remains bounded as the observation \(|x|\) tends to infinity. However, Eq. ([eqn:ser]) is stated for \(\gamma=1\). The next lemma states that the asymptotic behavior of the privacy loss as \(|x|\to\infty\) is independent of \(\gamma\).
Lemma 3. (No Scale Dependence in the Limit) Let \(\mathcal{D}_1 \simeq \mathcal{D}_2\) be two neighboring datasets. Denote by \(\mathcal{L}^{SaS}_{\mathcal{D}_1|| \mathcal{D}_2}(x; \gamma)\) the privacy loss of observation \(x\) for a bounded query \(f\) perturbed by a SaS Mechanism \(\mathcal{M}_f\) with scale parameter \(\gamma\). In the limit as \(|x|\) tends to \(\infty\), the behavior of the privacy loss is indistinguishably asymptotic for distinct choices of \(\gamma\): \[\lim_{|x| \to \infty} \mathcal{L}^{SaS}_{\mathcal{D}_1|| \mathcal{D}_2}(x; \gamma_1) = \lim_{|x| \to \infty} \mathcal{L}^{SaS}_{\mathcal{D}_1|| \mathcal{D}_2} (x; \gamma_2),\] for \(\gamma_1 \neq \gamma_2\).
Proof. The proof follows directly the limit as \(|x|\) is taken to \(\infty\) in equation ([eqn:sas]) with the substitutions \(\hat{t} = \gamma t\) and \(\hat{x} = x / \gamma\). ◻
With the above results, we are now in a position to state and prove our main contribution, namely, that for \(\alpha \in [1,2)\), the privacy loss for SaS densities is bounded, i.e. the SaS Mechanism is \(\varepsilon\)-differentially private.
Theorem 1. (The SaS Mechanism is \(\epsilon\)-DP) Let \(\mathcal{D}_1 \simeq \mathcal{D}_2\) be two neighboring datasets and let \(f\) be a bounded query that operates on them. Consider the SaS Mechanism, which we denote by \(\mathcal{M}_f\), with stability parameter \(\alpha\) in the reduced range \(\alpha \in [1, 2)\). Then, the mechanism \(\mathcal{M}_f\) satisfies ([eqn:pureDP]), \(\varepsilon\)-DP.
Proof. Each element of the mechanism’s output is the perturbation of the queries response by an independent sample from the uni-variate density in ([eqn:sas]). Thus, the joint density is equal to the product of the individual densities. As a result, we can write the privacy loss for a given observation vector \(\textbf{x}\) as \[% \label{eqn:sas-plf} \mathcal{L}^{SaS}_{\mathcal{D}_1|| \mathcal{D}_2}(\textbf{x}) = \ln \frac{\prod\limits_{i = 1}^m p_{SaS}(x_i; \alpha, \gamma,f(\mathcal{D}_1)_i)}{\prod\limits_{i = 1}^mp_{SaS}(x_i; \alpha, \gamma,f(\mathcal{D}_2)_i)}.\] This can be written as the sum of the log-ratios: \[\mathcal{L}^{SaS}_{\mathcal{D}_1, \mathcal{D}_2}(\textbf{x}) = \sum_{i=1}^m \ln \frac{p_{SaS}(x_i; \alpha, \gamma,f(\mathcal{D}_1)_i)}{p_{SaS}(x_i; \alpha, \gamma,f(\mathcal{D}_2)_i)}.\] Without loss of generality, let this sum be written in decreasing order of magnitudes of the terms, i.e. the first term, \(i=1\), has the largest magnitude. We now have the following bound: \[\label{eqn:sas-plf} \big|\mathcal{L}^{SaS}_{\mathcal{D}_1|| \mathcal{D}_2}(\textbf{x})\big| \leq m \Big|\ln \frac{p_{SaS}(x_1; \alpha, \gamma,f(\mathcal{D}_1)_1)}{p_{SaS}(x_1; \alpha, \gamma,f(\mathcal{D}_2)_1)}\Big|.\] Our objective is to prove that the right side of ([eqn:sas-plf]) is bounded as function of \(x_1\), which will imply, by ([eqn:purepdf]), the mechanism is \(\varepsilon\)-differentially private. We do so by first proving that the privacy loss is bounded on any compact set. Note that this is not immediate since we are dealing with the log of a ratio and have no assurance that the numerator or denominator ever vanishes. Then, we show that in the limit as \(|x|\) tends to infinity, the privacy loss tends to \(0\), and thus does not diverge.
Initially, let \(x_1\) be an element in a compact set \([a, b] \subset \mathbb{R}\). The log-ratio of the densities could become unbounded within a finite interval in two ways: the argument vanishes or diverges. Consider first the case where one of densities vanishes within the interval. However, by Lemma 1, an SaS density has support on the entire real line, \(\mathbb{R}\). Therefore, the density is strictly positive over all compact sets \([a,b] \subset \mathbb{R}\).
Then, we consider if the numerator or denominator of ([eqn:sas-plf]) could be unbounded within the interval \([a,b]\). For simplicity, let \(\mu=0\) and apply the substitution \(e^{-ix_1} = \cos(tx_1) - i\sin(tx_1)\) to the representation of the SaS density ([eqn:sas]): \[p_{SaS}(x_1;\alpha, \gamma, 0) = \frac{1}{2\pi}\int_{-\infty}^{\infty}e^{-|\gamma t|^\alpha}(\cos(tx_1) - i\sin(tx_1))dt.\] Splitting the integral we have \[\begin{aligned} p_{SaS}(x_1;\alpha, \gamma, 0) = & \frac{1}{2\pi}\int_{-\infty}^{\infty}e^{-|\gamma t|^\alpha}\cos(tx_1)dt \\ - & i \frac{1}{2\pi}\int_{-\infty}^{\infty}e^{-|\gamma t|^\alpha} \sin(tx_1)dt. \end{aligned}\] Since \(\sin(tx_1)\) is an odd function the second integral vanishes: \[\label{eqn:cos-form} p_{SaS}(x_1;\alpha, \gamma, 0) = \frac{1}{2\pi}\int_{-\infty}^{\infty}e^{-|\gamma t|^\alpha}\cos(tx_1)dt\] As \(\cos(tx_1)\) is bounded above by \(1\): \[\label{eqn:a_part} p_{SaS}(x_1;\alpha, \gamma, 0) \leq \frac{1}{2\pi}\int_{-\infty}^{\infty}e^{-|\gamma t|^\alpha}dt\] Observe that the integrand in ([eqn:a_part]) is symmetric about \(t=0\) and so we can remove the absolute value: \[\label{eqn:30} p_{SaS}(x_1;\alpha, \gamma, 0) \leq \frac{1}{\pi}\int_{0}^{\infty}e^{-(\gamma t)^\alpha}dt\] Using the substituting \(\hat{t} = (\gamma t)^\alpha\) ([eqn:30]) becomes \[\label{eqn:31} \begin{aligned} p_{SaS}(x_1;\alpha, \gamma, 0) & \leq \frac{1}{\alpha\gamma\pi}\int_{0}^{\infty}\hat{t}^{\frac{1}{\alpha}-1}e^{-\hat{t}^\alpha}d\hat{t}\\ & = \frac{\Gamma(\frac{1}{\alpha})}{\alpha \gamma\pi} \end{aligned}\] where \(\Gamma\) is the standard \(\Gamma\) function which is finite on the interval \(1/\alpha \in (1/2, 1)\) [@oeis]. Equation ([eqn:31]) states that the density \(p_{SaS}\) is bounded over the real line. It is therefore bounded on the compact subset \([a,b]\).
Next, we proceed to prove that the privacy loss remains bounded in the limit as \(|x_1|\) tends to infinity.
Recall the series expansion, for \(\gamma=1\), presented in Lemma 2. Truncate the series to a single term, i.e., \(n=1\), and consider the privacy loss after substitution in ([eqn:sas-plf]): \[\big|\mathcal{L}^{SaS}_{\mathcal{D}_1||\mathcal{D}_2}(\textbf{x})\big| \leq m\Big|\ln\frac{\big(x_1 - f(\mathcal{D}_1)\big)^{-\alpha-1} + O(x_1^{-2\alpha - 1})}{\big(x_1 - f(\mathcal{D}_2)\big)^{-\alpha-1} + O(x_1^{-2\alpha - 1})}\Big|.\] Thus, in the limit as \(|x_1|\) tends infinity, the error terms in the numerator and denominator are dominated by the first terms: \[\begin{aligned} \lim_{||\textbf{x}||\to\infty} & \big|\mathcal{L}^{SaS}_{\mathcal{D}_1||\mathcal{D}_2}(\textbf{x})\big| \leq \\ \lim_{|x_1|\to\infty} & m\Big|\ln\frac{\big(x_1 - f(\mathcal{D}_1)\big)^{-\alpha-1} + O(x_1^{-2\alpha - 1})}{\big(x_1 - f(\mathcal{D}_2)\big)^{-\alpha-1} + O(x_1^{-2\alpha - 1})}\Big| = \\ \lim_{|x_1|\to\infty} & m\Big|\ln\frac{\big(x_1 - f(\mathcal{D}_1)\big)^{-\alpha-1}}{\big(x_1 - f(\mathcal{D}_2)\big)^{-\alpha-1}}\Big| = 0. \end{aligned}\] Thus, the privacy loss converges to \(0\). By Lemma 3, the choice of \(\gamma\) does not impact the asymptotic behavior. Since this result holds for any value of \(\textbf{x}\in \mathcal{R}(\mathcal{M}_f)\), by Eq. ([eqn:purepdf]), we have proved that the SaS Mechanism is \(\varepsilon\)-DP. ◻
Although Theorem 1 establishes that the SaS Mechanism is purely differential private, it does not offer a connection between the sensitivity of the query \(\Delta f\), the scale of the noise distribution \(\gamma\), and the achieved level of privacy \(\varepsilon\). This limitation stems from the absence of a known closed-form expression for the density \(p_{SaS}\).
Before pursing into further details on these relationships, we revisit the differential privacy characteristics of two widely used privacy mechanisms for the purpose of to facilitate subsequent comparisons.
Privacy Scaling with Noise
Next we discuss two common privacy mechanisms: the Laplace mechanism and the Gaussian mechanism [@dwork06; @roth14]. After discussing these mechanisms, we proceed to study the relation between the privacy budget \(\varepsilon\) and the scale \(\gamma\) of the SaS Mechanism and to provide related numerical results.
A Point of Comparison
The Laplace mechanism is the quintessential \(\varepsilon\)-differentially private mechanism. The Laplace mechanism injects zero-mean Laplace noise into the result of a query. The Laplace density extends the exponential density to the whole real line by taking the absolute value of the observation \(x\): \[p_{Lap}(x;b) = \frac{1}{2b} e^{-\frac{|x|}{b}}.\] The parameter \(b\) controls the spread of the density. When \(b\) is taken to be \(\Delta_1 f / \varepsilon\), its was shown in [@dwork06] that the Laplace mechanism satisfies ([eqn:pureDP]), pure differential privacy.
There are a few drawbacks to choosing Laplace noise. First, note that the Laplace density is not closed under convolution. Since convolution is frequently employed by the server when aggregating client datasets, the Laplace mechanism is generally applied to entire dataset post aggregation. Modifications that extend the method to local differential privacy (see Definition 8)) have been shown to be strictly sub-optimal [@hall88; @duchi14]. Second, the Laplace density is not smooth, which is the reason it is not commonly used in some settings such as federated learning. Conveniently, the Gaussian mechanism does not suffer from either of these issues.
The Gaussian mechanism perturbs a query result with zero-mean Gaussian noise: \[p_{Gau}(x; \sigma^2) = \frac{1}{\sigma \sqrt{2\pi}} e^{-\frac{1}{2}\big(\frac{x}{\sigma}\big)^2}\] When the variance is taken to be \(\sigma^2 = 2\ln(1.25/\delta)\Delta_2^2f/\varepsilon^2\), the Gaussian mechanism satisfies ([eqn:approxDP]), approximate differential privacy [@dwork06b; @roth14]. This fact highlights the main drawback in using the Gaussian mechanism: it is not purely differentially private.
We have recalled the Laplace and Gaussian mechanisms here to underscore deficiencies that will be addressed through use of the SaS Mechanism. Firstly, the SaS Mechanism is purely differently private as opposed to the approximate differential privacy of the Gaussian mechanism. Secondly, due to its use of a stable density, the aggregation of datasets individually perturbed by SaS Mechanisms can be described as if the aggregate itself has instead been perturbed, in contrast to the Laplace mechanism.
Next, we proceed to argue that the privacy budget of the SaS Mechanism scales with the same order as the Laplace and Gaussian mechanisms. We wish to show that \[\label{eqn:scaling} \varepsilon_{SaS} \stackrel{?}{\propto} \frac{\Delta_1 f}{\gamma}\] which is similar to \[\label{eqn:other-scaling} \begin{aligned} \varepsilon_{Lap} & = \frac{\Delta_1 f}{b} \\ \varepsilon_{Gau} & \propto \frac{\Delta_2 f}{\sigma}. \end{aligned}\]
Level of Privacy afforded by SaS Mechanism
For a given problem, there are three factors to consider when setting the parameters of a mechanism: the sensitivity of the query \(\Delta f\), the scale of the noise \(\gamma\), and the privacy budget \(\varepsilon\). In this section, we study the relationship between these three quantities for the SaS Mechanism.
Theorem 1 bounds the privacy loss by considering the largest of the \(m\) dimensional query responses (see Eq. ([eqn:sas-plf])). This motivates us to focus on the case \(m=1\), i.e., we now restrict to real-valued queries, \(f(\mathcal{D}) \in [a, b] \subset \mathbb{R}\). Furthermore, in this section, when referring to the sensitivity of query \(f\) we exclusively use the \(\ell_1\)-sensitivity and denote it by \(\Delta_1\).
We begin by establishing the linear relation between sensitivity and scale. To do so, we first prove that the extremes of the privacy loss, for a given privacy budget \(\varepsilon\), occur when the query over datasets \(\mathcal{D}_1 \simeq \mathcal{D}_2\) returns values in the boundary of the range, \(\mathcal{R}(f)\), i.e. when \(f(\mathcal{D}_1) = b\) and \(f(\mathcal{D}_2) = a\) (or vice versa, \(f(\mathcal{D}_1)=a\) and \(f(\mathcal{D}_2)=b\), by symmetry of the absolute value of the query).
In order to prove that the privacy loss is maximized at the boundary of the query’s range, we first establish that the density is monotonic on each semi-infinite interval to the left and right of the location parameter \(\mu\). We give a proof for the generic symmetric stable density using the fact that the density is bell-shaped, the definition of which is recalled next [@kwasnicki20].
Definition 11. (Bell-Shaped Function) A continuous real-valued function is said to be bell-shaped if the \(n^{th}\) derivative, \(f^{(n)}\) for each \(n \in \mathbb{N}_0\), changes sign exactly \(n\) times over its domain.
\[\tag*{$\blacktriangleleft$}\]
Lemma 4. (Monotonic First Derivative) The symmetric alpha-stable density ([eqn:sas]) with location parameter \(\mu\) is monotonically increasing from \(-\infty\) to \(\mu\) and monotonically decreasing from \(\mu\) to \(\infty\).
Proof. See the proof of [@kwasnicki20Cor. 1.3] which states that all stable distributions are bell-shaped densities. Taking \(n=1\) in Def. 11, this implies that the first derivative of the density, \(f'\), changes sign exactly once. Because the density is symmetric, the change in sign must occur at the axis of symmetry and the density must then decrease monotonically to \(0\) in the limit as \(|x| \to \infty\). ◻
We now utilize Lemma 4 to prove that, out of all neighboring datasets \(\mathcal{D}_1 \simeq \mathcal{D}_2\), the maximum extreme occurs at the boundary of the query’s range \([a,b]\). Recall that the SaS Mechanism involves injecting noise with a location parameter of \(0\). Thus, the location parameter is the result of the query, \(\mu_i = f(\mathcal{D}_i)\), and is itself bounded by the range of the query. By Theorem 1, the privacy loss of the SaS Mechanism is bounded. As a result, we denote by \(x^*(\mu_1,\mu_2)\) the point at which the maximum privacy loss occurs as a function of the location parameters \(\mu_1\) and \(\mu_2\) generated by datasets \(\mathcal{D}_1\) and \(\mathcal{D}_2\) respectively.
Theorem 2. (Query Maximization Occurs at Boundary) Let \(\mathcal{D}_1 \simeq \mathcal{D}_2\) be neighboring datasets and denote by \(f\) a bounded query that operates on them and returns values in the compact set \([a, b] \subset \mathbb{R}\). Denote the SaS Mechanism’s privacy loss for an observation \(x\) by \(\mathcal{L}^{SaS}_{\mathcal{D}_1||\mathcal{D}_2}(x)\). Let the location parameters of the two densities be \(\mu_1 = f(\mathcal{D}_1)\) and \(\mu_2 = f(\mathcal{D}_2)\), with \(\mu_1 \neq \mu_2\). Then \[\mathcal{L}^{SaS}_{\mathcal{D}_1|| \mathcal{D}_2}\Big(x^*(\mu_1,\mu_2)\Big) \leq \mathcal{L}^{SaS}_{\mathcal{D}_1|| \mathcal{D}_2}\Big(x^*(b,a)\Big).\]
Proof. Without loss of generality, take \(\mu_1 > \mu_2\). Recall that the privacy loss, ([eqn:plf]), is given by the log-ratio of two densities. Consider Figure 4 and let \(p(x;\mu_1)\), in blue, and \(p(x;\mu_2)\), in orange, represent the numerator and denominator of the privacy loss respectively. Let \(\epsilon\) be a value in \([0, b-\mu_1]\).
First, we show that if the privacy loss achieves a maximum \(x^*(\mu_1, \mu_2)\), then \(\mu_1 \leq x^*(\mu_1, \mu_2)\). Observe that, by construction, \(p(x=\mu_1;\mu_1) \geq p(x=\mu_1;\mu_2)\). Consider a point to the left of \(\mu_1\). By the symmetry of SaS densities, \(p(\mu_1-\epsilon;\mu_1) = p(\mu_1+\epsilon;\mu_1)\) and because the first derivative is negative, Lemma 4, \(p(\mu_1-\epsilon;\mu_2) \geq p(\mu_1+\epsilon;\mu_2)\). Thus, \[\mathcal{L}^{SaS}_{\mathcal{D}_1|| \mathcal{D}_2}(\mu_1-\epsilon) \leq \mathcal{L}^{SaS}_{\mathcal{D}_1|| \mathcal{D}_2}(\mu_1+\epsilon).\]
Next, let \(\mu_1 < b\). Then, observe that \(p(x^*(\mu_1,\mu_2);\mu_1) = p(x^*(\mu_1,\mu_2)+\epsilon;\mu_1+\epsilon)\), illustrated by the upper two marked points in Figure 4. Similarly, by Lemma 4, \(p(x^*(\mu_1,\mu_2)+\epsilon;\mu_2) \leq p(x^*(\mu_1,\mu_2);\mu_2)\), marked by the two lower points. Thus, \(\mathcal{L}\) can only be made larger by increasing \(\mu_1\) in the direction of the bound \(b\). Likewise, if \(\mu_1 = b\), then shifting the distribution to the left can only decrease the maximum. A similar argument shows that the log-ratio cannot be decreased by shifting \(p(x;\mu_2)\) towards \(p(x;a)\) which completes the proof. ◻
Because the maximum of the privacy loss is invariant to translation, Theorem 2 additionally implies the following corollary.
Corollary 1. (Relative Location Parameter) Let \(\mathcal{D}_1\) and \(\mathcal{D}_2\) be any neighboring datasets. Consider the privacy loss of the SaS Mechanism, with \(\alpha \in (1,2)\), for a one-dimensional query \(f\), with bounded range \(\mathcal{R}(f) = [a, b]\). Denote by \(\Delta_1\) the \(\ell_1\)-sensitivity of \(f\). Then, for a given \(\alpha \in (1, 2)\) and scale \(\gamma\), \[\label{eqn:sas-delta} \max_{\mathcal{D}_1 \simeq \mathcal{D}_2}\max_{x \in \mathbb{R}} \mathcal{L}_{\mathcal{D}_1||\mathcal{D}_2}^{SaS}(x) = \max_{x \in \mathbb{R}} \ln \frac{p_{SaS}(x; \alpha, \gamma, \Delta_1)}{p_{SaS}(x;\alpha, \gamma, 0)}.\]
Proof. The result follows directly by Theorem 2 and that the maximum of the privacy loss is invariant under translation. ◻
We can now assert that there is a linear relation between the sensitivity of the query \(\Delta_1\) and the scale of the density \(\gamma\).
Theorem 3. (Linearity of Scale and Query’s Sensitivity) Let \(\mathcal{D}_1 \simeq \mathcal{D}_2\) be neighboring datasets and \(f\) be a one-dimensional query with bounded range \(\mathcal{R}(f) = [a, b]\). Denote by \(\Delta_1\) the \(\ell_1\)-sensitivity of \(f\). Let \(p_{SaS}\) be the SaS density as described in equation ([eqn:sas]). Then, the level of privacy \(\varepsilon\) remains the same if the sensitivity \(\Delta_1\) and the scale \(\gamma\) are both scaled by the same constant \(c > 0\): \[\label{eqn:lin-bound-proof} \max_{x'\in\mathbb{R}}\ln \frac{p_{SaS}(x'; \alpha, c\gamma, c\Delta_1)}{p_{SaS}(x';\alpha, c\gamma, 0)} = \max_{x\in\mathbb{R}}\ln \frac{p_{SaS}(x; \alpha, \gamma, \Delta_1)}{p_{SaS}(x;\alpha, \gamma, 0)}.\]
Proof. We proceed by contradiction. Denote by \(x^*\) the location of the optimal value on the right side of ([eqn:lin-bound-proof]). Consider the left side of ([eqn:lin-bound-proof]) in terms of the expression ([eqn:sas]): \[\label{eqn:lin-bound} \max_{x'\in\mathbb{R}} \ln \frac{\int\limits_{-\infty}^{\infty}e^{-|c\gamma t|^\alpha - it(x'-c\Delta_1)}dt}{\int\limits_{-\infty}^{\infty}e^{-|c\gamma t|^\alpha - itx'}dt} .\] The change of variables \(\hat{t} = c t\) results in the equivalent expression \[\label{eqn:lin-bound2} \max_{x'\in\mathbb{R}} \ln \frac{\int\limits_{-\infty}^{\infty}e^{-|\gamma \hat{t}|^\alpha - i\hat{t}(\frac{x'}{c}-\Delta_1)}d\hat{t}}{\int\limits_{-\infty}^{\infty}e^{-|\gamma \hat{t}|^\alpha - i\hat{t}\frac{x'}{c}}d\hat{t}}\] Denote by \(x'^*\) the location of the maximum in ([eqn:lin-bound2]) and assume that it is not equal to \(cx^*\). This leads to the following contradiction \[\label{eqn:lin-bound3} \begin{aligned} & \max_{cx'\in\mathbb{R}} \ln \frac{\int\limits_{-\infty}^{\infty}e^{-|\gamma \hat{t}|^\alpha - i\hat{t}(x'-\Delta_1)}d\hat{t}}{\int\limits_{-\infty}^{\infty}e^{-|\gamma \hat{t}|^\alpha - i\hat{t}x'}d\hat{t}} \neq \\ & \max_{x\in\mathbb{R}} \ln \frac{\int\limits_{-\infty}^{\infty}e^{-|\gamma \hat{t}|^\alpha - i\hat{t}(x-\Delta_1)}d\hat{t}}{\int\limits_{-\infty}^{\infty}e^{-|\gamma \hat{t}|^\alpha - i\hat{t}x}d\hat{t}} \end{aligned}\] which is equivalent to \[\label{eqn:lin-bound-proof-end} \max_{cx'\in\mathbb{R}}\ln \frac{p_{SaS}(x'; \alpha, \gamma, \Delta_1)}{p_{SaS}(x';\alpha, \gamma, 0)} \neq \max_{x\in\mathbb{R}}\ln \frac{p_{SaS}(x; \alpha, \gamma, \Delta_1)}{p_{SaS}(x;\alpha, \gamma, 0)}.\] ◻
Remark 3. (Normalized Form) Because the scale and sensitivity are related linearly, we can combine \(\gamma\) and \(\Delta_1\) into a single parameter \(\hat{\gamma} = \gamma/\Delta_1\) by taking \(c=1/\Delta_1\): \[\label{eqn:simple} \max_{x \in \mathbb{R}} \ln \frac{p_{SaS}(x; \alpha, \gamma, \Delta_1)}{p_{SaS}(x;\alpha, \gamma, 0)} = \max_{x' \in \mathbb{R}} \ln \frac{p_{SaS}(x'; \alpha, \hat{\gamma}. 1)}{p_{SaS}(x';\alpha, \hat{\gamma}, 0)}.\]
We use the normalized form on the right side of Eq. ([eqn:simple]) to gain an intuitive understanding of how the maximum of the privacy loss behaves as \(\alpha\) and \(\hat{\gamma}\) are allowed to vary. Figure 5 fixes \(\hat{\gamma}=1\) and illustrates how the privacy loss approaches a straight line as \(\alpha\) tends to \(2\). Note that when \(\alpha=2\), corresponding to the privacy loss of the Gaussian mechanism, the loss is unbounded, illustrating that the Gaussian mechanism is not purely differentially private. See Lemma [prop:gaus] in Appendix [appendix:A] for details.
In Figure 6, with \(\alpha\) fixed at \(3/2\), we see that as the scale of the density (noise level), \(\hat{\gamma}\), increases, the level of privacy also increases (seen in the decreasing maximum \(\varepsilon\) value; recall from [eqn:epmax] \(\varepsilon = \max_x \mathcal{L}(x)\)).
We can expand upon the visualizations in Figures 5 and 6 by incorporating the results into a contour plot as depicted in Figure 7. Note that the relationship between the privacy budget \(\varepsilon\) and the parameter \(\alpha\) is non-monotonic for a given \(\hat{\gamma}\).
Next, to derive the behavior of the privacy loss at observation \(x\) in terms of the scale, we use a special case of the second partial sum expansion discussed by Bergström in [@bergstrom52].
Lemma 5. (A Second Finite Series Expansion) The symmetric alpha-stable density ([eqn:sas]), with \(\alpha \in (1,2)\) and \(\gamma=1\), has the following finite series expansion: \[\label{eqn:series2} \begin{aligned} & p_{SaS}(x; \alpha, 1, 0) = \\ &\frac{1}{\pi} \sum_{k=0}^n (-1)^k \frac{\Gamma(\frac{k+1}{\alpha})}{k!\alpha} (x)^{k} \cos \bigg( \frac{k \pi}{2} \bigg) + O\big(|x|^{n+1}\big), \end{aligned}\] as \(|x| \to 0\)
Proof. The full form provided by Bergström [@bergstrom52] states the result for the full range \(\beta \in (-1, 1)\). In our work, we only require ([eqn:series2]) and so for brevity, leave out the full form of the series. ◻
Below we make use of the following two elementary Taylor series expansions. For any \(c \neq 0\): \[\label{eqn:ts1} \frac{1}{c + x} = \frac{1}{c} - \frac{x}{c^2} + \frac{x^2}{c^3} - \frac{x^3}{c^4} + O(x^4),\] and \[\label{eqn:ts2} \ln \frac{c + x}{c} = \frac{x}{c} - \frac{x^2}{2c^2} + \frac{x^3}{3c^3} + \frac{x^4}{4c^4} + O(x^5).\]
Using Lemma 5, we now assert a relationship between the privacy loss for a given observation \(x\) and the scale of the SaS Mechanism \(\gamma\).
Theorem 4. (Privacy of Large Scales) Let \(\mathcal{D}_1 \simeq \mathcal{D}_2\) be neighboring datasets and \(f\) a bounded query that operates on them. Denote by \(\Delta_1\) the \(\ell_1\)-sensitivity of the query \(f\). Let \(\mathcal{M}_f\) be a SaS Mechanism with \(\alpha \in (1,2)\). Let the observation \(x\) be fixed and take \(\gamma\) to be the independent variable. Then \[\label{eqn:loss_o} [\mathcal{L}^{SaS}_{\mathcal{D}_1||\mathcal{D}_2}(x)](\gamma) = O\Big(\frac{\Delta_1}{\gamma}\Big) \textrm{ as } \gamma \to \infty.\] (\(\Delta_1\) is included in ([eqn:loss_o]) in order to highlight the analogy with ([eqn:other-scaling]).)
Proof. Fix the observation \(x\), then, by Lemma 2, the maximum privacy loss for \(x\) over the datasets \(\mathcal{D}_1\) and \(\mathcal{D}_2\) is \[\label{eqn:priv-loss} [\mathcal{L}^{SaS}_{\mathcal{D}_1||\mathcal{D}_2}(x)](\gamma) = \ln \frac{\int\limits_{-\infty}^{\infty}e^{-|\gamma t|^\alpha - it(x-\Delta_1)}dt}{\int\limits_{-\infty}^{\infty}e^{-|\gamma t|^\alpha - itx}dt}.\] Let \(\hat{t} = \gamma t\), \(\hat{x} = x\Delta_1\), and \(\hat{\gamma} = \gamma/\Delta_1\) and denote \((\hat{x} - 1)/\hat{\gamma}\) and \(\hat{x}/\hat{\gamma}\) by \(x_1\) and \(x_2\). The Eq. ([eqn:priv-loss]) becomes \[\label{eqn:fracO} [\mathcal{L}^{SaS}_{\mathcal{D}_1||\mathcal{D}_2}(x)](\gamma) = \ln \frac{\int\limits_{-\infty}^{\infty}e^{-|\hat{t}|^\alpha - i\hat{t}x_1}d\hat{t}}{\int\limits_{-\infty}^{\infty}e^{-|\hat{t}|^\alpha - i\hat{t}x_2}d\hat{t}}.\] We consider the numerator first followed by the denominator. Expand the numerator in ([eqn:fracO]) using the partial sum expansion given in Lemma 5 with \(n=0\): \[p_{SaS}(x_1;\alpha, 1,0) = \frac{\Gamma\big(\frac{1}{\alpha}\big)}{\alpha} + O(|x_1|), \quad |x_1| \to 0.\] For simplicity we denote \[a(\alpha) = \frac{\Gamma\big(\frac{1}{\alpha}\big)}{\alpha},\] which gives \[\label{eqn:num_exp} p_{SaS}(x_1;\alpha, 1,0) = a(\alpha) + O(|x_1|), \quad |x_1| \to 0.\] Thus, there exist positive constants \(C\) and \(x_0\) such that \[\label{eqn:part-exp} |p_{SaS}(x_1;\alpha, 1,0)| \leq a + C|x_1|, \quad \forall |x_1| \leq x_0.\] Replace \(x_1\) by its definition in ([eqn:part-exp]), first noting that the translations in \(x\) are described by the last parameter in the notation for the SaS density: \[p_{SaS}\Big(\frac{\hat{x}-1}{\hat{\gamma}};\alpha, 1, 0\Big) = p_{SaS}\Big(\frac{\hat{x}}{\hat{\gamma}};\alpha, 1,\frac{1}{\hat{\gamma}}\Big).\] Then \[\label{eqn:another} \Big|p_{SaS}\Big(\frac{\hat{x}}{\hat{\gamma}};\alpha, 1,\frac{1}{\hat{\gamma}}\Big)\Big| \leq a + C\Big|\frac{\hat{x}-1}{\hat{\gamma}}\Big|, \ \ \forall \Big|\frac{\hat{x}-1}{\hat{\gamma}}\Big| \leq x_0.\] Note that the range restriction in ([eqn:another]) is equivalent to \(\hat{\gamma} \geq |\hat{x}-1|/x_0\). Thus, denote \(|\hat{x}-1|/x_0\) and \(C|\hat{x}-1|\) by \(\gamma_0\) and \(\hat{C}\) respectively. Then \[\Big|p_{SaS}(\frac{\hat{x}}{\hat{\gamma}};\alpha, 1,\frac{1}{\hat{\gamma}})\Big| \leq a + \hat{C} \cdot \frac{1}{\hat{\gamma}}, \quad \forall \hat{\gamma} \geq \gamma_0,\] which can be represented in big O notation as \[\label{eqn:bigo1} p_{SaS}\Big(\frac{\hat{x}}{\hat{\gamma}};\alpha, 1,\frac{1}{\hat{\gamma}}\Big) = a + O\Big(\frac{1}{\hat{\gamma}}\Big), \quad \hat{\gamma} \to \infty.\] Using the same logic, the denominator in ([eqn:priv-loss]) can be represented as \[\label{eqn:bigo2} p_{SaS}\Big(\frac{\hat{x}}{\hat{\gamma}};\alpha, 1,0\Big) = a + O\Big(\frac{1}{\hat{\gamma}}\Big), \quad \hat{\gamma} \to \infty.\] Combining ([eqn:bigo1]) and ([eqn:bigo2]), ([eqn:fracO]) can now be expressed for large \(\hat{\gamma}\) in the form \[\label{eqn:loss-o} [\mathcal{L}^{SaS}_{\mathcal{D}_1||\mathcal{D}_2}(x)](\gamma) = \ln \frac{a + O(\frac{1}{\hat{\gamma}})}{a + O(\frac{1}{\hat{\gamma}})}, \quad \hat{\gamma} \to \infty.\] Using the elementary Taylor series ([eqn:ts1]), we can rewrite the denominator as \[\label{eqn:o-exp} \frac{1}{a + O(\frac{1}{\hat{\gamma}})} = \frac{1}{a} + O\Big(\frac{1}{\hat{\gamma}}\Big) = \frac{1 + O(\frac{1}{\hat{\gamma}})}{a},\] as \(\hat{\gamma} \to \infty\). Plugging ([eqn:o-exp]) into ([eqn:loss-o]) gives \[\begin{aligned} [\mathcal{L}^{SaS}_{\mathcal{D}_1||\mathcal{D}_2}(x)](\gamma) & = \ln \frac{a + O(\frac{1}{\hat{\gamma}})}{1} \cdot \frac{1 + O(\frac{1}{\hat{\gamma}})}{a}. \\ & = \ln \frac{a + O(\frac{1}{\hat{\gamma}}) + O(\frac{1}{\gamma^2})}{a}, \end{aligned}\] as \(\hat{\gamma} \to \infty\). The squared term vanishes faster in the limit leaving \[\label{eqn:big-o2} [\mathcal{L}^{SaS}_{\mathcal{D}_1||\mathcal{D}_2}(x)](\gamma) = \ln \frac{a + O(\frac{1}{\hat{\gamma}})}{a}, \quad \hat{\gamma} \to \infty.\] Next, we use the elementary Taylor series ([eqn:ts2]) and expand to \[\label{eqn:big-lim} [\mathcal{L}^{SaS}_{\mathcal{D}_1||\mathcal{D}_2}(x)](\gamma) = \frac{O(\frac{1}{\hat{\gamma}})}{a} + O\Big(\frac{1}{\hat{\gamma}^2}\Big), \quad \hat{\gamma} \to \infty.\] Recalling that \(\hat{\gamma}= \gamma/\Delta_1\), we now have \[(\gamma) = O\Big(\frac{\Delta_1}{\gamma}\Big), \quad \gamma \to \infty.\] ◻
Theorem 4 only guarantees that the privacy of a specific observation \(x\) scales as \(O(\Delta_1/\gamma)\) for large \(\gamma\). Without additional information about the location of the maximum, which is difficult to attain due to the lack of a known closed form for the general SaS density, Theorem 4 does not allow us to conclude that the maximum over all observations in the same manor. Because of this, in Figure 8 we provide numerical results graphing the max privacy loss \(\varepsilon\) over a range of scale values \(\hat{\gamma}\) for a selection of \(\alpha\) values.
Note that because this is a log-log plot, a vertical shift, as seen with \(\alpha=1.9\), corresponds to a multiplicative scalar in the limiting behavior. We observe that as \(\hat{\gamma}\) increases, the maximum privacy loss falls off at a rate similar to that for \(\alpha=1\) (at least for practically useful values of \(\varepsilon\) and \(\hat{\gamma}\)). To this end, we take advantage of the closed form of the density when \(\alpha=1\) to provide more concrete results for that case.
Theorem 5. (Privacy Scaling: \(\alpha=1\) case) Let \(\mathcal{D}_1 \simeq \mathcal{D}_2\) be neighboring datasets and \(f\) a bounded query with \(\ell_1\)-sensitivity \(\Delta_1\) that operates on them. Take the stability \(\alpha\) parameter for the SaS Mechanism to be \(\alpha=1\). Then, the privacy budget \(\varepsilon\) as a function of the scale \(\gamma\) is given by \[\varepsilon(\gamma) = \ln \frac{\sqrt{4(\frac{\gamma}{\Delta_1})^2+1}+1}{\sqrt{4(\frac{\gamma}{\Delta_1})^2+1}-1}.\]
Proof. Consider the privacy budget \(\varepsilon\) for the SaS Mechanism when \(\alpha = 1\): \[\varepsilon := \max_{x\in\mathbb{R}} \mathcal{L}^{SaS}_{\mathcal{D}_1||\mathcal{D}_2}(x).\] As in the proof of the foregoing theorem, let \(\hat{t} = \gamma t\), \(\hat{x} = x\Delta_1\), and \(\hat{\gamma} = \gamma/\Delta_1\) in ([eqn:priv-loss]): \[\label{eqn:frac1b} [\mathcal{L}^{SaS}_{\mathcal{D}_1||\mathcal{D}_2}(x)](\gamma) = \ln \frac{\int\limits_{-\infty}^{\infty}e^{-|\hat{t}|^\alpha - i\hat{t}\frac{\hat{x}-1}{\hat{\gamma}}}d\hat{t}}{\int\limits_{-\infty}^{\infty}e^{-|\hat{t}|^\alpha - i\hat{t}\frac{\hat{x}}{\hat{\gamma}}}d\hat{t}}.\] Note that the SaS density, when \(\alpha=1\), takes the closed form \[\label{eqn:cauchy} p_{SaS}(x;1,\gamma, \mu) = \frac{1}{1+(\frac{x - \mu}{\gamma})^2}.\] Substituting ([eqn:cauchy]) into ([eqn:frac1b]) gives \[\label{eqn:cauchy-full} [\mathcal{L}^{SaS}_{\mathcal{D}_1||\mathcal{D}_2}(x)](\gamma) = \ln\frac{1 + (\frac{\hat{x}}{\hat{\gamma}})^2}{1 + (\frac{\hat{x}-1}{\hat{\gamma}})^2}.\] To find the max, we take the derivative of the right side with respect \(\hat{x}\), \[\frac{d}{d\hat{x}} \ln\frac{1 + (\frac{\hat{x}}{\hat{\gamma}})^2}{1 + (\frac{\hat{x}-1}{\hat{\gamma}})^2} = \frac{-2(\hat{x}^2-\hat{x} - \hat{\gamma}^2)}{(\hat{\gamma}^2 + (\hat{x}-1)^2)(\hat{\gamma}^2 + \hat{x}^2)}.\] This equates to \(0\) when \[\hat{x}^2 - \hat{x} - \hat{\gamma}^2 = 0.\] There are two solutions: \[\hat{x}^* = \frac{1}{2}(1 \pm \sqrt{1 + 4\hat{\gamma}^2}).\] Since the privacy loss is symmetric, we take the positive solution without loss of generality. Plugging the positive maximum location into ([eqn:cauchy-full]) gives \[\label{eqn:almost} \varepsilon(\gamma) = \ln\frac{1 + \frac{1 + \sqrt{1 + 4\hat{\gamma}^2}}{4\hat{\gamma}^2}}{1 + \frac{1+4\hat{\gamma}^2}{4\hat{\gamma}^2}}.\] Recalling that \(\hat{\gamma} = \gamma/\Delta_1\), equation ([eqn:almost]) is equivalent to the following expression after simplification, \[\label{eqn:alpha_one} \varepsilon\big|_{\alpha=1}(\gamma) = \ln \frac{\sqrt{4(\frac{\gamma}{\Delta_1})^2+1}+1}{\sqrt{4(\frac{\gamma}{\Delta_1})^2+1}-1}.\] ◻
To make claims about the limiting behavior of the privacy loss, we again invoke three elementary Taylor series: \[\label{eqn:ts3} \sqrt{1+x^2} \pm x = 1 \pm x + \frac{x^2}{2} - \frac{x^4}{8} + O(x^6),\] \[\label{eqn:ts4} \ln\frac{(1+x)}{(1-x)} = 1 + 2x + \frac{2x^3}{3} + \frac{2x^5}{5} + O(x^7),\] and \[\label{eqn:ts5} \sqrt{4x^2+1}+c = (c+1) + 2x^2 -2x^4 + O(x^5).\]
Corollary 2. (Large scale approximation) In the limit as \(\gamma\) grows without bound, when \(\alpha=1\) the privacy budget \(\varepsilon\), falls off at the following rate: \[\varepsilon(\gamma)\big|_{\alpha=1} \approx \frac{\Delta_1}{\gamma}, \ \text{ as } \gamma \to \infty.\]
Proof. The change of variables \(x = \Delta_1/(2\gamma)\) applied to Eq. ([eqn:alpha_one]) gives \[\label{eqn:why} \varepsilon(\gamma)\big|_{\alpha=1} = \ln \frac{\sqrt{\frac{1}{x^2} + 1}+1}{\sqrt{\frac{1}{x^2} + 1}-1}.\] Because \(x\) only equates to \(0\) in the limit of \(\gamma\to\infty\), and we seek the dynamics when \(\gamma\) is large but finite, we can safely multiply the argument of the logarithm in ([eqn:why]) by \(x/x\) giving \[\label{eqn:why2} \varepsilon(\gamma)\big|_{\alpha=1} = \ln \frac{\sqrt{1+x^2}+x}{\sqrt{1+x^2}-x}.\] Next, expand the numerator and denominator of ([eqn:why2]) using the elementary Taylor series ([eqn:ts3]), giving the following expression for small \(x\) after eliminating the higher order terms: \[\label{eqn:why3} \varepsilon(\gamma)\big|_{\alpha=1} \approx \ln \frac{1+x}{1-x}, \ \ \textrm{ as } x \to 0.\] This can be further simplified by appealing to the Taylor series expansion ([eqn:ts4]) yielding a first order approximation \[\label{eqn:why4} \varepsilon(\gamma)\big|_{\alpha=1} \approx 2x, \ \ \textrm{ as } x \to 0.\] Recalling that \(x = \Delta_1/(2\gamma)\) now gives \[\label{eqn:why5} \varepsilon(\gamma)\big|_{\alpha=1} \approx \frac{\Delta_1}{\gamma}, \ \text{ as } \gamma \to \infty.\] ◻
Corollary 3. (Small scale approximation) In the limit as \(\gamma\) becomes vanishing small, for \(\alpha=1\) the privacy budget \(\varepsilon\),, increases at the following rate: \[\varepsilon(\gamma)\big|_{\alpha=1} \approx 2 \ln \frac{\sqrt{2}\Delta_1}{\gamma}, \text{ as } \gamma \to 0.\]
Proof. Begin by expanding the argument of the logarithm in ([eqn:alpha_one]) using the elementary Taylor series ([eqn:ts4]), \[\ln \frac{\sqrt{4(\frac{\gamma}{\Delta_1})^2+1}+1}{\sqrt{4(\frac{\gamma}{\Delta_1})^2+1}-1} = \ln \frac{2+2(\frac{\gamma}{\Delta_1})^2 + O(\gamma^3)}{2(\frac{\gamma}{\Delta_1})^2 + O(\gamma^3)}, \quad \gamma \to 0.\] As \(\gamma\) tends to \(0\), the higher order behavior is dominated by \(\gamma^2\) and we have \[\label{eqn:somthin} \varepsilon(\gamma)\big|_{\alpha=1} \approx \ln \frac{2}{(\frac{\gamma}{\Delta_1})^2}, \quad \gamma \to 0.\] Equivalently, the expression in ([eqn:somthin]) gives \[\label{eqn:somthin2} \varepsilon(\gamma)\big|_{\alpha=1} \approx 2 \ln \frac{\sqrt{2}\Delta_1}{\gamma}, \text{ as } \gamma \to 0.\] ◻
In Figure 9, we provide numerical results along with graphs of the limiting behavior derived in Corollaries 2 and 3.
The Figure numerically confirms that, for small \(\gamma\), the SaS Mechanism, due the appearance of the logarithm in ([eqn:somthin2]), scales better than do the Laplace and Gaussian mechanisms as were recalled in ([eqn:other-scaling]).
Now that we have shown that the SaS Mechanism behaves in a similar manner to other common privacy mechanism, we move on the describe the expected error introduced to the queries result by using any of these mechanisms.
Expected Error of SaS Mechanism
It is common for methods to use the \(\ell_2\)-norm in defining such an error measure. However, the moment of the SaS densities is only defined up to \(\alpha\), and since we are considering \(\alpha < 2\), the second moment is not well defined [@nolan20]. In lieu of the \(\ell_2\)-norm, we choose to use the mean absolute deviation (MAD), also used in [@roth14]:
Definition 12. (Expected Privacy Distortion) Denote by \(f(\mathcal{D})\) and \(\mathcal{M}_f(\mathcal{D})\) the response of the query and privacy mechanism respectively. The mean absolute deviation is \[E(f(\mathcal{D}), \mathcal{M}_f(\mathcal{D})) := \mathbb{E} |f(\mathcal{D}) - \mathcal{M}_f(\mathcal{D})|,\] which is equivalent to the expectation of the absolute value of the injected noise \(Y\): \[E(f(\mathcal{D}), \mathcal{M}_f(\mathcal{D})) = \mathbb{E} |Y|.\]
\[\tag*{$\blacktriangleleft$}\]
Before we can study the error incurred under the SaS Mechanism, we need the fact that the SaS Mechanism is strictly stable.
Lemma 6. (SaS density is Strictly Stable) The SaS density ([eqn:sas]) with location parameter \(\mu=0\) is strictly stable.
Proof. Let \(Y_1\), \(Y_2\), and \(Y\) be i.i.d. SaS densities with \(\mu=0\). Let \(a\) and \(b\) be two scalar values and consider the density of the combined random variable \(aY_1 + bY_2\). Because the SaS densities are described by their characteristic functions we have the following relation \[\varphi_{aY_1+bY_2}(t) = \varphi_{aY_1}(t) \varphi_{bY_2}(t).\] Using the definition of characteristic function, we bring the constants into the argument \[\begin{aligned} \varphi_{aY_1}(t) \varphi_{bY_2}(t) & = \mathbb{E}[e^{itaY_1}]\mathbb{E}[e^{itbY_2}] \\ & = \varphi_{Y_1}(at) \varphi_{Y_2}(bt) \end{aligned}\] Expand by substituting the expression for the characteristic function of a stable distribution with \(\mu=0\) ([eqn:char]) into both functions on the right side, \[\begin{aligned} \varphi_{Y_1}(at) \varphi_{Y_2}(bt) & = \exp(|\gamma a t|^\alpha)\exp(|\gamma bt|^\alpha)\\ & = \exp{ |(a^\alpha+b^\alpha)^{1/\alpha}\gamma t|^\alpha} \end{aligned}\] Setting \(c = (a^\alpha + b^\alpha)^{1/\alpha}\) gives \(aY_1 + bY_2 = cY\). ◻
We are now equipped to determine the expected error introduced in the query by the SaS Mechanism.
Theorem 6 (Expected Distortion Due to SaS Mechanism). (Expected Distortion Due to SaS Mechanism) Let \(f\) be a bounded query that operates on dataset \(\mathcal{D}\). Denote by \(\mathcal{M}_f\) the SaS Mechanism and take the stability parameter \(\alpha\) to be restricted to the range \(\alpha\in(1,2)\). Then, the mean absolute distortion is \[\label{eqn:mad-sas} E\big(f(\mathcal{D}, \mathcal{M}_f(\mathcal{D})\big) = \frac{2\gamma}{\pi}\Gamma\big(1-\frac{1}{\alpha}\big).\]
Proof. In [@nolan20], the proof of Corollary 3.5 includes a statement that if a density \(p_Y\) is strictly stable then ([eqn:mad-sas]) holds. ◻
We now provide the expected distortions of the two most common privacy mechanisms: the Laplace and the Gaussian mechanisms [@roth14; @dwork06b], to show that each induces an error linear in the scale of the noise. The mean absolute deviation of the Laplace density is \[\mathbb{E}[|Lap(0, b)|] = \mathbb{E} [Exp(b^{-1})] = b.\] The mean absolute deviation Gaussian density is the expected value of the half-normal random variable \[\mathbb{E}[|\mathcal{N}(0, \sigma^2)|] = \sqrt{\frac{2}{\pi}}\sigma.\] Note that for each of the three densities the error is related linearly to the density’s respective scale. From ([eqn:mad-sas]) we recover the distortion of the Gaussian mechanism by taking \(\alpha=2\) and \(\gamma= \sigma/\sqrt{2}\).
Because \(\alpha\) is bound within \((1,2)\), the argument of the Gamma function in ([eqn:mad-sas]) varies between \((0,1/2)\). The Gamma function has an asymptote at \(x=0\) and reaches a local minimum in the right plane at \(x \approx 1.462\) [@oeis]. Thus, for a given \(\gamma\), the distortion in Eq. ([eqn:mad-sas]) is minimized when \(\alpha\) tends to \(2\).
CONCLUSION
In conclusion, the SaS Mechanism represents a significant advancement in the field of differential privacy. This mechanism not only provides strong guarantees of privacy but also offers distinct advantages when compared to other common privacy mechanisms. Because the SaS Mechanism is closed under convolution makes it a particularly good choice for applications seeking to implement local differential privacy, such as federated learning. Looking forward, we are actively investigating the privacy of the SaS Mechanism under other versions of Differential Privacy such as Renyi and Concentrated DP.
ACKNOWLEDGMENT
This work was supported in part by Grant Number ECCS-2024493 from the U.S. National Science Foundation.