Online estimation of robust statistics, namely quantiles, is of great interest in several applications where high-rate data streams must be processed as quickly as possible and discarded, being their storage usually unfeasible. Fast and accurate estimation is challenging when considering the additional constraint of diferential privacy, which leads to the well-known privacy-utility trade-of. Recent approaches further require the use of a minimal amount of space (even a single memory variable), so as to reduce the complexity. In this paper we present three diferentially-private streaming algorithms for frugal estimation of a quantile, based on diferent modifications of the Frugal-1U algorithmD:P-Frugal-1U-L, DP-Frugal-1U-G, and DP-Frugal-1U- . We specifically provide a theoretical analysis and experimental results.
CEUR Workshop
ISSN1613-0073 next, we design three DP versions of the algorithm based respectively on the Laplace mechanism, the Gaussian mechanism and on zero-concentrated DP; • we validate the theoretical results through simulations, considering diferent families of statistical distributions, including heavy-tailed ones.
The rest of this paper is organized as follows. Sectio2nprovides the necessary definitions and notation used throughout the manuscript. Section3 introduces theFrugal-1U algorithm whilst Section 4 presents our analysis and three corresponding DP algorithms. We present the experimental results in section 5 and draw our conclusions in Section6.
In this Section, we briefly recall the definitions and notations that shall be used throughout this paper. We begin by giving a formal definition of quantiles.
Definition 1. (Lower and upper -quantile) Given a set of size over ℝ, let () be the rank of the element , i.e., the number of elements in smaller than or equal t o. Then, the lower (respectively upper) -quantile item ∈ is the item whose rank () in the sorted set is ⌊1 + ( − 1)⌋ (respectively ⌈1 + ( − 1)⌉ ) for 0 ≤ ≤ 1 .
The accuracy related to the estimation of a quantile can be defined either as rank or relative accuracy. In this paper, we deal with algorithms that provide rank accuracy, which is defined as follows. Definition 2. (Rank accuracy) For all item s and a given tolerance , return an estimated rank ̃ such that |(̃) − ( )| ≤ .
Next, we introduce the main concepts underlying DP. We focus on the so-called central model of DP. Actually, two definitions are possible, as follows.
Definition 3. (Unbounded diferential privacy, also known as the add-remove model1[2] [13]) Two datasets and ′ are considered neighbors if ′ can be obtained from by adding or removing one row. Under unbounded DP, the sizes of and ′ are diferent (by one row): |\ ′| + | ′\ | = 1.
Definition 4. (Bounded diferential privacy, also known as the swap or the update/replace model12[] [14]) Two datasets and ′ are considered neighbors if ′ can be obtained from by changing one row. Under bounded DP, the sizes of and ′ are equal:|\ ′| = 1 and | ′\ | = 1.
budget.
Definition 5. ( -diferential privacy) A function which satisfies DP is called a mechanism; we say that a mechanism ℱ satisfies pure DP if for all neighboring datasets and ′ and all possible sets of outputs , it holds that PPrr[[ℱℱ(()′∈)∈] ] ≤ . The parameter in the definition is called the privacy parameter or privacy
The parameter is strictly related to the desired amount of privacy. In practice, there is trade-of going on, since smaller values of this parameter provide higher privacy but at the cost ofulteilsisty and vice-versa. In this context, utility refers to the possibility of using the obtained results for further investigations, namely statistical analyses. Therefore, the trade-of may be understood considering that setting to a small value require the mechanisℱmto provide very similar outputs when instantiated on similar inputs (so, higher privacy, obtained by injecting more noise which in turn undermines utility); on the contrary, a large value provides less similarity of the outputs (so, less privacy but increased utility). Besides pure DP, a diferent notion, called approximate (or, alternative,ly,) DP, is also available. Definition 6. ((, ) -diferential privacy) A mechanism ℱ satisfies ( , )-DP if for all neighboring datasets and ′ and all possible sets of outputs , it holds thatPr[ℱ () ∈ ] ≤ Pr [ℱ ( ′) ∈ ] + , where the privacy parameter0 ≤ < 1 represents a failure probability. probability no guarantee holds. As a consequenc e, is required to be very small.
The definition implies that (i) with probability 1 − it holds that PPrr[[ℱℱ(()′∈)∈] ] ≤ and (ii) with In order to define a mechanism, we need to introduce the notion of sensitivity. In practice, the sensitivity of a function reflects the amount the function’s output will change when its input changes. Formally, given the universe of datasets, denoted b y, the sensitivity of a function , calledglobal sensitivity, is defined as follows. the global sensitivity o f is ( ) = between two datasets , ′.
max, ′∶ (, ′)≤1 | () − ( ′)|, where (, ′)represents the distance
We now define two mechanisms, respectively the Laplace and the Gaussian mechanism. The former must be used with pure DP, the latter with approximate DP.
Lap (
Definition 8. (Laplace mechanism) Given a function ∶ → ℝ mapping a dataset in to a real number, ℱ () = () + ) satisfies -DP. ()
denotes sampling from the Laplace distribution with center 0 and scale , whilst is the sensitivity of .
Definition 9. (Gaussian mechanism) Given a function ∶ → ℝ mapping a dataset in to a real number, ℱ () = () + ( 2) satisfies
(, ) -DP, where 2 = 2 2 ln(1.25/) and is the sensitivity of . ( 2) denotes sampling from the Gaussian (normal) distribution with center 0 and varian c2e. 2
The Gaussian mechanism also satisfies a stronger notion of privacy, known a szero-concentrated diferential privacy ( -zCDP); its definition uses a single privacy paramete r , and lies between pure and approximate DP. Moreove r,-zCDP has been shown to be equivalent (i.e., it can be translated) to standard notions of privacy.
Definition 10. ( -zCDP) A mechanism ℱ satisfies zero-concentrated DP if for all neighboring dataset s and ′ and all ∈ (1, ∞) , it holds that (ℱ ()‖ℱ ( ′))≤ , where (‖) = the Rényi divergence. −1 1 ln ∼
() ( () ) is
It can be shown that -zCDP can be converted to(, ) -DP as follows. If the mechanismℱ satisfies Gaussian mechanism can be adapted to work with-zCDP as follows. -zCDP, then for > 0 it also satisfies (, ) -diferential privacy for = + 2 √ log(1/). Moreover the ( 2) where 2 = 2
2 Definition 11. ( -zCDP Gaussian mechanism) Given a function ∶ → ℝ mapping a dataset in to a real numberℱ, () = () +
satisfies -zCDP, where is the sensitivity of .
We briefly introduce the concept of utility, which quantifies how much a DP result is useful for a subsequent data analysis. Therefore, the analysis to be performed plays a key role here, since DP results afected by a significant error may or may not be useful to the analyst. One way to overcame the dependence from the analysis is the use of the related concept of accuracy, which is the distance between the true value computed without DP and the DP released value. Therefore, accuracy is often used in place of utility, because more accurate results are generally more useful for an analysis. The so-called(, ) -accuracy framework1[5] can be used to measure accuracy. Here,represents an upper bound on the absolute error committed, whilstis the probability to violate this bound.
mapping a dataset ∈ to a real number, and a DP mechanism ℳ ∶ → ℝ , ℳ is (, ) -accurate if Pr [‖ () − ℳ () ‖∞ ≥ ] ≤ .
It can be shown [15], starting from the Cumulative Distribution Function for the Laplace distribution
Lap(), that the Laplace mechanism is(, ) -accurate with
= ln (
(
Regarding the Gaussian and the-zCDP mechanisms, we did not find in the literature a corresponding derivation for the value; as an additional contribution, here we derive their analytical form. We start by considering the Cumulative Distribution Function for the normal distribu tio(n ), which is
Therefore, we need to solve, taking into account tha0t < < 1 , the following equation, with regard to : obtaining It follows that the Gaussian mechanism i(s, ) -accurate with
Pr [ > ] = 1 − 1 erfc [− 2 √2
. = (− √2 erfc−1(2(1 − ))) 2 .
√2
(
Among the many algorithms that have been designed for tracking quantiles in a streaming setting, Frugal [11] besides being fast and accurate, also restricts by design the amount of memory that can be used. It is well-known that in the streaming setting the main goal is to deliver a high-quality approximation of the result (this may provide either an additive or a multiplicative guarantee) by using the lowest possible amount of space. In practice, there is a tradeof between the amount of space used by an algorithm and the corresponding accuracy that can be achieved. SurprisinFgrluyg,al only requires one unit of memory to track a quantile. The authors Forfugal have also designed a variant of the algorithm that uses two units of memory. In this Section, we introduce the one unit of memory version, which is calledFrugal-1U. Algorithm1 provides the pseudo-code forFrugal-1U.
The algorithm works as follows. Firs t̃,is initialized to zero (however, note that it can be alternatively initialized to the value of the first stream item, in order to increase the speed of convergence of the estimate towards the value of the true quantile). This variable will be dynamically updated each time a new item arrives from the input strea m, and its value represents the estimate of the quantile being tracked. The update is quite simple, since it only requires̃to be increased or decreased by one. Specifically, a random number0 < < 1
is generated by using a pseudo-random number generator
(the call(
in the pseudo-code) and if the incoming stream item is greater than the estimate , then the estimate ̃ is increased, otherwise if the incoming stream item is smaller than the estimate ̃ and >
, then the estimate ̃ is decreased. Obviously, the algorithm is really fast and can process an incoming item in worst-cas(e1) time. Therefore, a stream of length can be processed in worst-case()
time and (
Despite its simplicity, the algorithm provides good accuracy, as shown by the authors. The proof is
challenging since the algorithm’s analysis is quite involved. The complexity in the worst cas(e)is ,
since items are processed in worst case(
Algorithm 1 Frugal-1U
Require: Data stream , quantile , one unit of memory ̃
Ensure: estimated quantile valuẽ
1: =̃ 0
2: for each ∈ do
3: = (
Finally, the algorithm has been designed to deal with an input stream consisting of integer values distributed over the domain[ ] = {1, 2, 3, … , } . This is not a limitation though, owing to the fact that one can process a stream of real values as follows: fix a desired precision, say three decimal digits, then each incoming stream item with real value can be converted to an integer by multiplying i1t0b3yand then truncating the result by taking the floor. If the maximum number of digits following the decimal point is known in advance, truncation may be avoided altogether: lettingby the maximum number of digits following the decimal point, it sufices to multiply by10 . Obviously, the estimated quantile may be converted back to a real number dividing the result by the fixed precision selected or 1b0y .
In this Section, we analyze theFrugal-1U algorithm and design DP variants of it. As shown in Section 3, the algorithm is quite simple. In order to estimate a quantil,ethe current estimate ̃ is either incremented or decremented by one based on the value of the incoming stream ite m. The increments are applied with probabilit yand the decrements with probability1 − .
Our DP versions of the algorithm are based on the definition of bounded DP (see Definition 4), in which two datasets and ′ are considered neighbors if ′ can be obtained from by changing one row. Owing to our choice, we need to analyze the impact of changing one incoming stream item with a diferent one on the quantile estimate ̃ . The following Lemma is our fundamental result to then obtain DP versions of Frugal-1U.
Lemma 1. Under bounded DP, the global sensitivity of theFrugal-1U algorithm is 2.
Proof. Let be the item to be changed, and ≠ the item replacing . There are a few symmetric cases to consider. Let be the -th stream item, so that the length of the strea m is equal to − 1 before the arrival of and equal to immediately after. Moreover, denote by ̃ −1 the estimate of the quantile before the arrival o f and by ̃ after seeing the item . Suppose that the arrival o f causes ̃ to increase by one with regard t o ̃ −1 , i.e., ̃ = ̃ −1 + 1. Substituting with therefore can lead to the following cases: eithe r ̃ = ̃ −1 − 1 or ̃ = ̃ −1 + 1. Therefore, the estimate is unchanged or it is increased by 2. Similarly, assuming that the arrival ocfauses ̃ to decrease by one with regard to ̃ −1 , i.e., ̃ = ̃ −1 − 1, then there are, symmetrically, the following cases: eit h ẽ r= ̃ −1 + 1 or ̃ = ̃ −1 − 1. Therefore, the estimate is unchanged or is decremented by 2. It follows that the global sensitivity of the algorithm ismax, ′∶ (, ′)≤1 | () − ( ′)| = 2.
Since the global sensitivity is 2D,P-Frugal-1U-L, a pure DP (see Definition 5) variant of the algorithm can be obtained by using the Laplace mechanism. We are now in the position to state the following theorem.
Theorem 1 (DP-Frugal-1U-L.) Frugal-1U can be made -DP by adding to the quantile estimate returned by the algorithm noise sampled from a Laplace distribution as follo w=s̃: +̃ (
Finally, we designDP-Frugal-1U- , a -zCDF version of the algorithm.
Theorem 3 (DP-Frugal-1U -). Frugal-1U can be made -zCDF by adding to the quantile estimate returned by the algorithm noise sampled from a Gaussian distribution as followℱs:() = ()+ ( 2) where 2 = 2
.
Proof. It follows straight from Lemm1a and Definition 11.
Finally, we remark here that, contrary to many DP algorithms that initialize a data structure or a sketch using suitable noise, it is not possile to initialize the quantile estimateForfugal-1U using the noise required by one of the proposed mechanisms. The reason is two-fold. First, the algorithm processes integer items, so that its initial estimate must be an integer as well whilst, in general, the noise is a floating point value. But, even assuming that we initialize the estimate to an integer value related to the noise (perhaps taking its floor or the ceiling), this will not help in any way since, by design, the algorithm adapts dynamically to the observed input items and converges to the estimated quantile. Therefore, the second reason is that the noise added will be silently discarded by the algorithm when converging to the quantile estimate. As a consequence, the noise must be added only after the algorithm termination to the returned estimated quantile.
In this section we present and discuss the results of the experiments carried out fForugal-1U-L, Frugal-1U-G, Frugal-1U- . The experiments are limited to our algorithms owing to the fact that, to the best of our knowledge, there are no other frugal algorithms for the estimation of quantiles designed for the central model of diferential privacy. The source code has been compiled using the Apple clang compiler v15.0 with the following flags: -Os -std=c++14 (it is worth recalling that on macOS the flag -Os optimizes for size and usually on this platform the resulting executable is faster than the executable obtained by compiling using the -O3 flag). The tests have been carried out on an Apple MacBook Pro laptop equipped with 64 GB of RAM and a 2.3 GHz 8-core Intel Core i9. The experiments have been repeated ten times for each specific category of test and the results have been averaged; the seeds used to initialize the pseudo-random generators are the same for each experiment and algorithm being tested.
The tests have been performed on eight synthetic datasets, whose properties are summarized in Table 1. The experiments have been executed varying the stream length, the quantile, the privacy bud g,et, and . Table2 reports the default settings for the parameters.
We plot the relative error between the true quantile and the DP quantile estimate released by the algorithms under test, by allowing one parameter to vary whilst keeping the values of the others at their defaults. In all of the figures, the distribution used is the normal (later we compare the results obtained when varying the distribution as well). As depicted in Figure1a, the relative error decreases as expected when the privacy budgeintcreases, meaning that the utility (see Section2) of the released value increases whe nincreases. Therefore, a good tradeof between privacy and utility is reached for0.5 ≤ ≤ 1 . and the stream size. As shown, the two quantities do not afect the security of the released quantile. Finally, Figure1d depicts the throughput measured in updates/s.
Next, we analyzeFrugal-1U-G. Increasing , the probability of failure, provides as expected slightly less privacy, as shown in Figur2ea. By varying the computed quantile, a similar behaviour is observed. In Figure2b, slightly less privacy is associated to higher quantiles. Finally, the impact of the stream size is depicted in Figure2c, in which a fluctuating behaviour can be observed, even though the interval of variation is tight.
RegardingFrugal-1U- , Figure3a shows that, as expected, the relative error decreases when the privacy budget increases, and the utility increases correspondingly. A good privacy-utility tradeof is reached for0.5 ≤ ≤ 1 . Figure3b and 3c, related respectively to the relative error for varying quantile and stream size, present the same behaviour illustrated for the Gaussian mechanism. This is 100 10 not surprising since this mechanism adds Gaussian noise (though the way noise is derived is of course diferent).
We now turn our attention to what happens when we vary the distribution, including heavy-tailed instances. Figure4 provides the results forFrugal-1U-L, Frugal-1U-G and Frugal-1U- . As shown, the relative error between the true quantile and the DP quantile estimate released by one of the algorithms varies with the distribution. However, for our proposed algorithms, as expected (since the global ● ●
● G U l10.2 a g u r F 0.1 0.0 0.01 0.4Relative error - quantile: 0.99 - length: 10M - distribution: normal 0.4 Relative error length: 10M distribution: normal ρ: 1 0.4 Relative error - quantile: 0.99 - distribution: normal - ρ: 1 0.3 ρ u -l10.2 a g u r F 0.1 sensitivity is just 2) the algorithms can be used independently of the actual distribution, with the notable exception related to the Cauchy distribution (which can be considered adversarial for our algorithms based on Frugal-1U as discussed in [11]).
Our results show that, having fixed a distribution, the behaviour of our algorithms basedFornugal1U does not depend on the seed used to initialize the pseudo-random number generator used to draw samples from the distribution. In this sense, our algorithms are robust.
Finally, we analyze th(e, ) -accuracy (Definition 12) of Frugal-1U-L. Fixing = 0.04 , = 1 and
taking into account that the global sensitivity oFfrugal-1U is = 2 , by using equation(
ForFrugal-1U-G, using Eq. (
In this paper, we proposed DP algorithms for tracking quantiles in a streaming setting. Our algorithms are DP variants of the well-knowFnrugal-1U algorithm, characterized by the property of requiring just a tiny amount of memory to process a stream whilst guaranteeing surprising accuracy for quantile estimates. In particular, foFrrugal-1U we gave corresponding -DP, (, ) -DP, and -zCDF algorithms after proving that the global sensitivity ofFrugal-1U is equal to 2. Finally, we also showed that the proposed algorithms achieve good accuracy in the experimental results.
The author(s) have not employed any Generative AI tools. Cham, 2017, pp. 347–450. URL: https://doi.org/10.1007/978-3-319-57048-8_7. doi:10.1007/ 978-3-319-57048-8_7. [15] J. P. Near, X. He, Diferential privacy for databases, Foundations and Trends® in Databases 11 (2021) 109–225. URL: http://dx.doi.org/10.1561/1900000066. doi:10.1561/1900000066.