Hiding Numerical Vectors in Local Private and Shuffled Messages

1 Introduction

With the enacting of increasingly rigid regulations on data privacy (e.g., the General Data Protection Regulation [Voigt and Von dem Bussche, 2017] in the Europe Union, the California Consumer Privacy Act, and the Civil Code of the People's Republic of China), local differential privacy (LDP) has become the de facto notion for data privacy preservation over the Internet. It originates from the classical notion of differential privacy in the database community [Dwork, 2008] without the trust of the data aggregator or other third parties. LDP allows every user/agent to sanitize their personal data locally (e.g., on mobile devices, IoT sensors or edge servers) and provides information-theoretically rigorous privacy protection. Currently, many giant internet service providers (such as Apple [Greenberg, 2016], Google [Erlingsson et al., 2014] and Microsoft [Ding et al., 2017]) are deploying LDP for regulation compliance when collecting and analyzing user data. As a remedy to the unacceptable error barrier due to stringent LDP

∗Corresponding author.

constraints, researchers recently introduce shuffle model [Erlingsson et al., 2019] where messages from users are permuted (by a shuffler, e.g., anonymous channels) before sent to the aggregator. The linkage between users and their messages are cutted off and messages could hide in the crowd, [Erlingsson et al., 2019] show privacy is amplified with shuffling, thus a lower privacy level can be adopted locally to satisfy a relatively higher privacy level as in the analogised central model.

Plenty of user data are in the form of numerical vectors. Let xi denote the numerical vector of user i. For simplicity but without loss of generality, xi can be assumed as a d-dimensional s-sparse ternary vector [Wen et al., 2017; Ye et al., 2019; Sun et al., 2019; Gu et al., 2020], that is:

This work studies the problem of numerical vector aggregation within the local and shuffled differential privacy framework. Many real-world data aggregation tasks could be formulated as this problem, such as gradient estimation in federated learning and sensitive key-value data aggregation for user profile/usage analyses in online services.

1.1 Federated Gradient Estimation

Federated learning [Koneˇcn`y et al., 2016] studies machine learning systems in the distributed setting so that each party keeps its own data locally for privacy preserving. At each gradient descent iteration for training/updating a machine learning model, locally computed gradients xi from participating parties (e.g., from n mobile users) need to be averaged by the federation server (e.g., a parameter server):

For communication efficiency, local gradients are usually discretized and sparsified [Wen et al., 2017; Wangni et al., 2018].

The original work [Koneˇcn`y et al., 2016] deems sharing gradient to be more privacy-resistant than sharing raw data, but a recent work demonstrates that the gradient xi is also privacy risky [Zhu et al., 2019] and local raw data might be derived with confidence from several transmitted gradients. This calls for rigid privacy protection on local gradients.

1.2 Key-value Data Aggregation

We refer to key-value data as any paired (key, value) mappings, where the key j ∈ [1, d] is an index and the value xj is numerical. Note that, the value is deemed as 0 when and only when the corresponding key is missing from or not defined in key-value data. For any existing or defined keys, their corresponding values are binary as {-1, 1}. For example, a user might represent preferences on watched movies as key-value data, in which movies the user likes are assigned with value 1 and movies the user unlikes are assigned with value -1.

Common analysis on key-value data includes estimating both unconditional mean statistics and conditional mean statistics. The unconditional mean estimation about the key j is xj = 1n ∑ni=1 xij , and the conditional mean estimation about the key j is:

1.3 Existing Results

Within the framework of ϵ-LDP, theoretical minimax lower bounds for many statistical estimation problems have been established, such as multinomial distribution estimation [Duchi et al., 2013], logistic regression/generalized linear model estimation [Duchi et al., 2018] and sparse covariance matrix estimation [Wang and Xu, 2019]. Specifically, the work of [Duchi et al., 2018] derives minimax lower bounds for multi-dimensional mean estimation for numerical vectors with bounded ℓ1-norm or ℓ2-norm. However, an s-sparse numerical vector with bounded ℓ1-norm or ℓ2-norm is a special case of [Duchi et al., 2018] with identical absolute non-zero entries. Whether it holds the same bounds as the general case or has tighter bounds is still an open question. Recently, for a broad family of ϵ-LDP estimation problems that can be cast as a mean estimation one, the work of [Błasiok et al., 2019] studies sample complexity lower bounds under certain error tolerance α, but their sample complexity result for s-sparse numerical vectors has at least a 1/α gap to ours result of minimax optimal sample complexity.

Practically, plenty of ϵ-LDP mechanisms have been proposed for statistical data estimation, such as multinomial distribution estimation on categorical data [Duchi et al., 2013; Erlingsson et al., 2014; Kairouz et al., 2016; Wang et al., 2020b], and one-dimensional mean estimation on numerical values [Wang et al., 2019; Sun et al., 2020]. For ϵ-LDP numerical vector or key-value data aggregation, existing approaches deal with both dense numerical vectors (e.g., in [Nguyˆen et al., 2016; Duchi et al., 2018]) and sparse numerical vectors (e.g., in [Ye et al., 2019; Sun et al., 2019; Gu et al., 2020]). Specifically, the works of [Ye et al., 2019; Sun et al., 2019] uniform-randomly select one dimension from [1, d] and transform the multi-dimensional estimation problem to a one-dimensional numerical/categorical problem. The work of [Gu et al., 2020] follows a similar paradigm, but randomly selects one non-empty dimension from s dimensions. However, as we will show in Section 4, these mechanisms are sub-optimal.

To mitigate the high noise needed for LDP, [Erlingsson et al., 2019] introduces a trusted shuffler to hide private views in the crowd. Recent works [Balle et al., 2020; Ghazi et al., 2020] propose sending multiple unary/binary messages with distributed noise to the shuffler for achieving centralized differential privacy (CDP), while other works [Cheu et al., 2019; Balle et al., 2019] study privacy amplification effects for achieving a lower level of LDP and a higher level of CDP simultaneously via shuffling. Specifically, [Balle et al., 2019; Wang et al., 2020a; Liu et al., 2021] utilize the technique of privacy blanket for privacy amplification on binomial/multinomial distribution estimation. This work further show domain-independent privacy amplification is achievable for sparse numerical vector.

1.4 Our Contributions

Minimax Lower Bounds. The MSE lower bound of ϵ-LDP s-sparse numerical vector mean estimation is O( ds nϵ2 ). Our proof considers s-sparse numerical vectors that are decomposable, hence reduces the bounding procedure to cases of multiple multinomial distribution estimations.

An Optimal Mechanism. Since existing approaches are sub-optimal, we design a mechanism that matches the minimax lower bound. The mechanism has computational complexity of O(s) and communication complexity of O(log s).

Domain-independent Privacy Amplification. For the shuffle model of s-sparse numerical vector aggregation, the proposed optimal mechanism satisfies centralized (√14 ln (2/δ) s·eϵ+2s-1 n-1 , δ)-differential privacy. The privacy loss ϵc in CDP is independent of domain size d, thus fits federated learning of large models. In turn, when privacy budget ϵc is given, we derive local parameter for optimal utility and show the proposed mechanism is asymptotic near-optimal in terms of user population.

The remainder of the paper is organized as follows. Section 2 provides preliminary knowledge on local differential privacy and minimax risk framework of statistical estimation. The minimax lower bound on the ϵ-LDP numerical vector aggregation problem is then given in Section 3. Next, Section 4 reviews the design of existing mechanisms and shows their sub-optimality, and then propose a new mechanism and prove its optimality. Section 5 shows the proposed mechanism enjoys domain-independent privacy amplification in the shuffle model, and prove its asymptotic optimality. Later, Section 6 demonstrates the superior performance of the proposed mechanism against existing mechanisms. Finally, Section 7 concludes the paper.

2 Preliminaries

2.1 Differential Privacy

For datasets D, D′ that are of the same size and differ only in one element, they are called neighboring datasets. The centralized differential privacy with budget/level (ϵ, δ) is as follows.

Definition 1 ((ϵ, δ)-CDP [Dwork, 2008]). Let DK denote the output domain, a randomized mechanism K satisfies ϵdifferential privacy iff for any neighboring datasets D,D′ , and any outputs z ⊆ DK,

Let K denote a randomized mechanism for sanitizing a single user data, the LDP with privacy budget ϵ is as follows. Definition 2 (ϵ-LDP [Duchi et al., 2013]). Let DK denote the output domain, a randomized mechanism K satisfies local ϵ-differential privacy iff for any data pair x, x′ ∈ X s , and any output z ∈ DK,

2.2 Local Private Minimax Risks

Assuming samples {x1 , x2 , ..., xn } that are n i.i.d. drawn from a distribution P ∈ P. Let Kϵ denote the set of all possible mechanisms K = {K1 , ..., Kn } that satisfy ϵ-LDP for every sample in {x1 , x2 , ..., xn }. Taking as input the samples, some mechanism K ∈ Kϵ produces a list of sanitized views {z1 , z2 , ..., zn }. If the parameter estimator:

is derived from these private views while having no access to input samples {xj }nj=1 , the minimax MSE risk (under privacy budget ϵ) is then:

3 Minimax Lower Bounds

The Assouad's method [Yu, 1997] is a common tool for lower bounding via multiple hypothesis testings. It defines a hypercube V = {-1, 1}d (d ∈ N), then defines a family of distributions {Pν}ν∈V indexed by the hypercube, where each Pν is defined on one common space. It's said that the distribution family induces a 2τ -Hamming separation for the loss ||·||22 , if there exists a vertex mapping (a function κ : θ(P) ↦→ {-1, 1}d ) satisfying:

Assume that the nature first uniform-randomly chooses a vector V ∈ {-1, 1}d , and the samples {x1 , ..., xn } are drawn from the distribution Pν with V = ν. These samples are then taken as input into ϵ-LDP mechanisms K. The literature [Duchi et al., 2018] gives an ϵ-LDP version of Assouad's method as follows.

Lemma 1 (Private Assouad bound [Duchi et al., 2018]). Let P+j = 1 2d-1 ∑ν:νj=1 Pν and P-j = 1 2d-1 ∑ν:νj=-1 Pν , we have

where B∞(X s ) denote the collection of function γ with supremum norm bounded by 1 as:

and maximum possible discrepancy FB∞(X s ),P is defined as:

We consider numerical vectors that can be decomposed the into s buckets, each bucket has ds indexes with only one non-zero entry. We then define a hypercube of length d and construct a class of 2δ2 s2 d2 -hamming separated probability distributions. Guided by Lemma 1, we bound the maximum possible marginal distance FB∞(X s ),P under the value of 8δ2 s d . Theorem 1 gives the final lower bounds for the problem of local private numerical vector mean estimation.

Theorem 1. For the numerical vector aggregation problem, for any ϵ-LDP mechanism, there exists a universal constant c > 0 such that for all ϵ ∈ [0, 1],

To understanding the minimax rate, we can consider the non-private error rate of decomposable numerical vector aggregation, which is E||ˆ θ - θ||22 ≤ ∑di=1 E|| ˆ θi -θi||22 ≤ 4s n . Thus the enforcement of local ϵ-LDP causes the effective sample size decreasing from n to nϵ2 /d.

4 Optimal Mechanism

Let j- and j+ denote events that the j-th element of x (i.e. xj) equals to -1 and 1 respectively, a numerical vector x could be represented in the set form as:

Existing works on ϵ-LDP numerical vector aggregation can be categorized into two types, they do dimension sampling in a data-agnostic manner (e.g., the PrivKV in [Ye et al., 2019; Sun et al., 2019]) or a data-dependent manner (e.g., the PCKV in [Gu et al., 2020]).

The PrivKV Mechanism. The seminal work [Ye et al., 2019] on ϵ-LDP key-value data aggregation propose to firstly randomly sample a dimension (from the domain of keys) j ∈ [1, d], then applies an ϵ-LDP categorical mechanism on the corresponding (key,value) pair that takes a value from {(j, 0), (j, 1), (j,-1)}, where (j, 0) means that the key is empty in the key-value data. Essentially, the PrivKV mechanism is equivalent to dividing the population of n into d groups, and each group is employed to estimate [j+ ∈ Yx] and [j- ∈ Yx] for each j ∈ [1, d] with privacy budget ϵ. Since the minimax lower error bound for estimating frequencies on population of n′ with privacy budget ϵ and domain size d′ is Θ( d′ n′ ϵ2 ) [Duchi et al., 2018], the estimation error of [j+ ∈ Yx] and [j- ∈ Yx] is hence Θ( d nϵ2 ), as n′ = nd and d′ = 3. Therefore, its total estimation error of frequencies or mean values of d-dimensional vector is O( d2 nϵ2 ). It has a gap of ds from the optimal error rate in Theorem 1. Similar methodology and result also hold for the following-up works in [Sun et al., 2019; Liu et al., 2021].

The PCKV Mechanism. The work of [Gu et al., 2020] proposes to sample one key from existing s keys in a keyvalue data. Afterwards, an ϵ-LDP categorical mechanism is applied to the corresponding 1-sparse numerical vector, which is equivalent to categorical data with domain size of around 2d. Recall that the minimax lower error bound for estimating frequencies on population of n′ with privacy budget ϵ and domain size d′ is Θ( d′ n′ ϵ2 ), the total estimation error of scaled [j+ ∈ Yx] and [j- ∈ Yx] in the PCKV mechanism is hence Θ( d nϵ2 ), as n′ = n and d′ = 2d. Due to the previous sampling procedure, the scale factor is s and the total variation error is amplified by s2 , thus the total estimation error of [j+ ∈ Yx] and [j- ∈ Yx] in the PCKV mechanism is O( ds2 nϵ2 ). It has a gap of s from the optimal error rate in Theorem 1.

4.1 Our Design

The paradigm of dimension sampling & categorical randomization fails to achieve optimal statistical rate for ϵ-LDP numerical vector aggregation. Therefore, we consider randomizing the numerical vector as a whole with the exponential mechanism [McSherry and Talwar, 2007], and propose the Collision mechanism.

If defining event domain as: Y = {1-, 1+, 2-, 2+, ..., d-, d+}, we have Yx as a subset of Y with size s. Define the output domain as Z = {1, 2, ..., t}, the Collision mechanism probabilistically outputs one item z ∈ Z. The outputting probabilities are based on whether each item has collision with hashed events in Yx. The Collision mechanism is formally given in Definition 3.

Definition 3 ((d, s, ϵ, t)-Collision Mechanism). Given a random-chosen hash function H : Y ↦→ Z, take an s-sparse numerical vector Yx ⊆ Y as input, the Collision mechanism randomly outputs an element z ∈ Z according to following probability design:

The normalization factor is Ω = s · eϵ + t - s. An unbiased estimator of indicator [jb ∈ Yx] for b ∈ {-1, 1} and j ∈ [1, d] is (for s ≥ 2):̂

The privacy guarantee of the mechanism is given in Proposition 1, which is obvious as s ≥ #{H(y) | H(y) for y ∈ Yx}. The utility-optimality guarantee of the mechanism is given in Theorem 2. For ϵ = O(1), its computational complexity is bounded by t∗ ≈ s + 2s - 1 + s · eϵ = O(s), and communication complexity is log2(2s-1+s·eϵ ) = O(log s).

Proposition 1. The (d, s, ϵ, t)-Collision mechanism in Definition 3 satisfies ϵ-LDP for numerical vector data.

Theorem 2. Given privacy budget ϵ = O(1), with optimal choice of the parameter t∗ , the mean estimation error of (d, s, ϵ, t)-Collision mechanism for numerical vector is O( ds nϵ2 ).

Proof. Since [H(jb) = z] are Bernoulli random variables, we have the mean squared error:

Taking the previous formula as a function of continuous t, actually the function is convex when d ≥ t ≥ s. Choosing approximate optimal t∗ at around 2s -1+ s · eϵ , we then have (with eϵ ≈ ϵ + 1):

5 Privacy Amplification in Shuffle Model

When semi-trusted shufflers lie between users and the aggregator, the aggregator only observes the multi-set of private views {z1, z2, ...zn}, thus the privacy level of some LDP mechanisms is amplified (w.r.t. CDP). For binary domain of private views Z = {1, 2} generated from randomized response, [Cheu et al., 2019; Balle et al., 2019] show the observed frequencies of z ∈ Z satisfies (√14 ln (2/δ) eϵ+1 n-1 , δ)-CDP, since about 2(n-1) eϵ+1 users response uniform randomly, they contributed B( 2(n-1) eϵ+1 , 0.5) Binomial random noises to the frequencies.

Similarly, in the Collision mechanism with private view domain Z = {1, 2, ..., t}, about n-1 s·eϵ+t-s users response uniform randomly, they contributed B( n-1 s·eϵ+t-s , 1/t) Binomial random noises to each frequency of z ∈ Z. As a result, the Collision mechanism also satisfies (√14 ln (2/δ) s·eϵ+t-s n-1 , δ)- CDP. The formal guarantee of privacy amplification of the Collision mechanism is presented in Theorem 3.

Proof. Since private views with hash functions are randomly shuffled and the final estimator is derived from them, to prove the final estimator is (√14 ln (2/δ) s·eϵ+t-s n-1 , δ)-CDP, it is enough to show that the distribution of observed private views with hash functions satisfies CDP. Further because the hash functions are randomly chosen from some universe, we only need to show the frequency distribution of observed private views satisfies CDP. The frequency distribution is noised by N ∼ B(n - 1, t s·eϵ+t-s ) users, each user contributed with uniform-random t-multinomial distribution in the output domain. Then, according to the tail bounding result on this noise distribution with multiplicative Chernoff bound or Bennett's inequality (the privacy blanket theorem in [Balle et al., 2019]), such a noise distribution satisfies

With optimal choice of t ≈ 2s - 1 + s · eϵ in LDP, the privacy amplification bound is thus independent of the domain size d. Alternatively, when the privacy level in the CDP is given as (ϵc, δ), we have Ω = s · eϵ + t - s = ϵ2c (n-1) 14 ln2/δ , then the numerical vector estimation error bound is a function of t with constant Ω as:

6 approximately minimizes the error, which is also independent of the domain size d.

With the optimal choice of t in terms of CDP, when the numerical vector is highly sparse (i.e. d ≫ s) and the user population is large, we have the asymptotic estimation error in the shuffle setting as:

which nearly matches the optimal error rate in the centralized differential privacy setting (the sensitivity is 2s).

6 Experiments

The statistical efficiency of the proposed Collision mechanism for ϵ-LDP numerical vector aggregation is evaluated in this section. Competing mechanisms include the PrivKV mechanism [Ye et al., 2019], the PCKV mechanism with general randomized response as the base randomizer (denoted as PCKV-GRR), and the PCKV mechanism with unary encoding as the base randomizer[Gu et al., 2020] (denoted as PCKV-UE). Since the performances of all these mechanisms are data-independent, it is enough to utilize synthetic datasets for fair evaluation. The parameters of synthetic datasets are listed as follows (default values are in bold form), covering most cases encountered in real-world applications:

1. Number of users n: 10,000, 100,000.
2. Dimension d: 256, 1024.
3. Sparsity parameter s: 4, 8, 16, 32.
4. Privacy budget ϵ: 0.001, 0.01, 0.1, 0.2, 0.4, 0.8, 1.0, 1.5, 2.0, 2.5, 3.0.

During each simulation, the numerical vector of each user is independent-randomly generated, the non-zero entries are uniform-randomly selected from d dimensions, and each dimension has an equal probability of being -1 or 1.

6.1 EvaluationMetric

Previous theoretical results focus on the mean squared error: ∑j∈[1,d] ||ˆxj - xj||22 . Here we evaluate mechanisms with metrics on frequency estimators of [jb ∈ YX] (including TVE and MAE), which are basic statistics for both the unconditional and conditional mean estimation in Equation (1) and Equation (2). The total variation error (TVE) is defined as:

and the maximum absolute error (MAE) is defined as:

Since the 1s -scaled frequencies lie in the d dimensional probability simplex, the estimated frequencies are projected into the ∆d-simplex as in [Wang and Carreira-Perpin´an, 2013]. All experimental results are the mean natural logarithm value of 10 repeated simulations.

6.2 Effects of Sparsity s

Assume that there are n = 100, 000 users, and the dimension is d = 256. When the number of non-zero entries in numerical vectors varies from 4 to 32, the TVE/MAE error results are presented in Figure 1 and Figure 2 respectively. The PCKVUE mechanism improves upon the PrivKV in the extreme sparse cases, but for other cases (e.g., s = 32), the PCKV-UE and the PrivKV mechanism have similar performances. The Collision mechanism outperforms all competing mechanisms in all cases significantly, and averagely reduces more than 60% errors. As the sparsity parameter s gets larger, the performance gaps get larger.

6.3 Effects of Dimension d

Assume that there are n = 100, 000 users, but the dimension now becomes d = 1024. When the number of non-zero entries in numerical vectors still varies from 4 to 32, the results of TVE and MAE are shown in Figure 3 and Figure 4 respectively. Compared to cases of d = 256 (i.e. TVE results in Figure 1 and MAE results in Figure 2), it is easy to observe that the TVE/MAE value grows with around √d.

6.4 Effects of Number of Users n

Assume that there are only n = 10, 000 users, and the dimension is d = 256. When the number of non-zero entries in numerical vectors varies from 4 to 32, the results of TVE and MAE are listed in Figure 5 and Figure 6 respectively. Compared to the case of n = 100, 000 (i.e. Figure 1 and Figure 2), the TVE/MAE value is about √100000/10000 times larger (i.e. decreases with around √n).

6.5 After Shuffling

Considering the privacy budget is amplified in the shuffle model, typically when the number of users is n = 100000, privacy budget in CDP is ϵc = 0.5 and δ = 1/n, the local privacy budget in the Collision mechanism is scaled to around 2.0 with optimal t. In these region with large local privacy budget, the performance of the Collision is far better than other approaches. Besides, the privacy amplification of PrivKV/PCKV scales poorly with dependance on the domain size, thus when CDP budget (ϵc, δ) is given and the domain is relatively large, the performance gap grows.

6.6 Experimental Summary

Through experimental evaluation, we can conclude that the Collision mechanism outperforms existing approaches in all cases. Their performance gaps also support our previous theoretical analysis on error bounds (MAE errors usually have magnitude proportional to the root of mean squared error).

7 Conclusion

Within the framework of distributed differential privacy, this paper studied the problem of numerical vector statistical estimation, which has its applications in federated learning and key-value data aggregation. We provided tight minimax error bounds of O( ds nϵ2 ) for local differential private mean estimation on numerical vectors. Our proof relies on a novel decomposition technique for data domain with sparse structure and an application of the local private version of Assouad methods. Given that existing approaches are suffering gaps form the optimal error bounds, we further design an optimal mechanism for the problem, and then give an efficient implementation with linear computation/communication complexity. To further break the error bounds, we consider numerical vector estimation in the shuffled differential privacy, and show the proposed mechanism has the advantages of domain-independent privacy amplification and near-optimal utility. Experimental results show averagely 60% error reduction of the optimal mechanism when compared with current approaches.

Acknowledgements

We would like to thank anonymous reviewers for their helpful comments. This work is supported by National Key Project of China (No. 2020YFB1005700), National Natural Science Foundation of China for Joint Fund Project (No. U1936218), Project of Guangzhou University (No. RQ2021006), and the Pazhou lab, Guangzhou, China.