Locally Differentially Private Sparse Vector Aggregation

Introduction

Federated analytics and learning allow a cloud provider to learn useful statistics and train machine learning models using data aggregated from a large number of users (e.g., browsing history, shopping records, movie ratings). Since many of these data types are privacy-sensitive, a line of recent work has focused on enabling privacy-preserving federated analytics . A central primitive in privacy-preserving federated analytics is called vector mean estimation. Suppose $n$ users each have a real-valued vector $v_{i}\in[-1,+1]^{d}$, and the collection of all users’ vectors is called the input configuration, henceforth denoted $\mathbf{v}=(v_{1},\ldots,v_{n})\in^{d\cdot n}$. The server wants to estimate the mean of the users’ vectors, without compromising each individual user’s privacy. Frequency estimation can be viewed as a special case of vector mean estimation where each user has a binary vector $v_{i}\in\{0,1\}^{d}$ indicating whether the user owns each of the $d$ items in some universe, the server wants to estimate the frequency of each item. Besides frequency estimation, vector mean estimation is a key building block in numerous applications, such as frequent item mining , key-value data aggregation , linear regression , federated learning model update , (stochastic) gradient descent , and so on. Many of these applications are being considered and deployed by companies such as Google , Apple , and Microsoft .

In this context, a standard privacy notion is local differential privacy (LDP) . Informally, LDP (Def. 7) requires that if a single user changes its input, the distribution of server’s view in the protocol changes very little. In other words, the transcript observed by the server cannot allow the server to accurately infer any single individual’s input. Two commonly-studied notions of LDP include user-level LDP (Def. 10) and event-level LDP (Def. 8). In event-level LDP, we want that the distribution of the server’s view be close under two neighboring input configurations $\mathbf{v}\in^{d\cdot n}$ and $\mathbf{v}^{\prime}\in^{d\cdot n}$ that differ in exactly one coordinate (which may correspond to a single event for a single user). In user-level LDP, we want that the distribution of the server’s view be close under two neighboring input configurations $\mathbf{v}$ and $\mathbf{v}^{\prime}$ that differ in the contribution of a single user, possibly involving all $d$ coordinates of that particular user. Unless otherwise noted, throughout this paper, we consider an information-theoretic notion of privacy, i.e., privacy should hold without relying on any computational assumptions.

In numerous practical applications, each user’s vector $v_{i}\in^{d}$ is sparse. We say that a vector $v_{i}\in^{d}$ is $k$-sparse iff at most $k$ coordinates are non-zero. We are most interested in the case when $k\ll d$. For example, imagine that the universe consists of the URLs of all websites in the world, and each user’s vector denotes whether a user has visited each URL. Another example is from natural language processing: imagine that the universe is all possible bags-of-words of size three, where as a user’s input contains all occurrences that appeared in their emails. In such examples, $k$ is much smaller than the universe size $d$. Sparsity has also been leveraged as an algorithmic technique in the (non-private) federated learning literature. For example, Konecny et al. showed that sparsifying the gradient vectors could result in algorithms that significantly reduce communication while maintaining accuracy.

In some cases, the universe may even be too large to efficiently enumerate, e.g., the space of all possible URLs. In such cases, instead of writing down an estimate of the entire mean vector $\bar{v}:=\frac{1}{n}\sum_{i=1}^{n}v_{i}$, we want the server to instead be able query an estimate of $\bar{v}_{x}$ for any $x$ of its choice (e.g., the fraction of users that has visited a specific URL of interest).

Due to the prevalence of sparse vectors in real-world applications, we ask the following important question:

Can we achieve locally differentially private $k$-sparse vector mean estimation with efficient communication and small error?

In a recent workshop on Federated Learning and Analytics hosted by Google , this was raised as an important open question of interest to Google.

The most naïve approach is to apply the standard randomized response mechanism to each coordinate — henceforth we refer to this approach as “naive perturbation”. For the case of event-level LDP, naive perturbation achieves $\widetilde{O}(\frac{1}{\epsilon\cdot\sqrt{n}})$ $L_{\infty}$-error with high probability where $\epsilon$ is the privacy budget and $\widetilde{O}(\cdot)$ hides (poly-)logarithmic factors. While this simple mechanism actually achieves asymptotically optimal error in light of well-known lower bounds , it has a high $O(d)$ communication cost.

One interesting question is whether we can achieve succinct communication that is independent or only logarithmically dependent on the universe size $d$ for sparse vectors. Several prior works have explored this question for $1$-sparse vectors, i.e., assuming that each user holds exactly one item out of a large universe of $d$ items. The latest results in this line of work showed how to achieve asymptotically optimal error while paying only logarithmic bandwidth — note that in the $1$-sparse case, event-level LDP is the same as user-level LDP up to constant factors.

In comparison, the more general case of $k$-sparsity is less understood, and currently we do not have matching upper and lower bounds for schemes with succinct (e.g., logarithmic) communication. Although some prior schemes achieve communication that is succinct in the universe size $d$ under even user-level differential privacy, they suffer from $\Omega(\sqrt{d})$ error, thus making them unsuitable for our motivating scenarios where $d$ can be very large. Other works combine sampling and a $1$-sparse mechanism: this approach achieves better asymptotic error than while still maintaining succinct communication, but their asymptotic error is a $\sqrt{k}$ or $k$ factor away from optimal, depending on whether we care about user- or event-level LDP.

1 Our Contributions and Results

We give the first locally private constructions for vector mean estimation that achieve succinct communication and optimal error (up to polylogarithmic factors). Our contributions include new upper- and lower-bounds, as well as an empirical evaluation of our algorithms.

We devise new schemes that satisfy $\epsilon$-LDP (either user-level or event-level) with the following desirable properties:

Communication efficiency: Our mechanisms have communication cost that is independent of the universe size $d$, and depends only on $k$, i.e., the maximum number of non-zero coordinates per user.

Optimal error. Our schemes satisfy (nearly) optimal error for any $\epsilon$-LDP mechanism.

Specifically, we prove the following theorems. Although not explicitly stated below, all of our upper bounds below assume the existence of a pseudorandom function (PRF) with parameter $\lambda$; however, the PRF is needed only for measure concentration and not needed for privacy.

There exists an $\epsilon$-user-level-LDP mechanism for the $k$-sparse mean vector estimation problem that achieves $O(\log k+\lambda)$ per-client communication, and with probability at least $1-\beta-{\sf negl}(\lambda)$, it achieves $O\left(\frac{1}{\epsilon}\sqrt{\frac{k\log(n/\beta)\log(d/\beta)}{n}}\right)$ $L_{\infty}$-error. Moreover, the mechanism is non-interactive, i.e., it involves only a single message from each client to the server.

There exists a non-interactive $\epsilon$-event-level-LDP mechanism for the $k$-sparse mean vector estimation problem that achieves $O(k\log k+\lambda)$ per-client communication, and with probability at least $1-\beta-{\sf negl}(\lambda)$, it achieves $O\left(\frac{1}{\epsilon}\sqrt{\frac{\log(d/\beta)}{n}}\right)$ $L_{\infty}$-error.

Bassily et al. showed that any event-level LDP mechanism for mean estimation (even when $k=1$) has to suffer from at least $\Omega(\frac{1}{\epsilon}\sqrt{\frac{\log d}{n}})$ error. In light of their lower bound, our event-level LDP mechanism achieves optimal error. In fact, it turns out that our user-level LDP mechanism also achieves (nearly) optimal error but to show this we will need to prove a new lower bound as mentioned shortly below.

Table 1 compares our results with prior works, and show how we achieve asymptotical improvements. Notice that our event-level scheme consumes more bandwidth than the user-level scheme, partly because the optimal error bound for event-level LDP is more stringent than for user-level LDP. It is an open question whether we can further reduce the bandwidth for event-level LDP while still preserving optimality in errorThroughout, we assume that the number of queries made by the server into the estimated mean vector is polynomially or subexponentially bounded in the security parameter (denoted $\lambda$) of the PRF, depending on whether the PRF has polynomial or subexponential security. In cases where the server does not query the entire universe $d$, we take $L_{\infty}$ error over the queries that are actually made.

Lower bound for k𝑘k-sparse LDP vector mean estimation.

We extend the proof technique of Bassily and Smith and prove a new lower bound for any user-level LDP mechanism for vector mean aggregation. Our new lower bound almostly tightly matches the upper bound in Theorem 1 (up to a logarithmic gap in $n$), showing our user-level LDP upper bound achieves nearly optimal error.

Any $(\epsilon,o(\frac{\epsilon}{n\log n}))$ user-level LDP mechanism for vector mean aggregation must suffer from at least $\Omega\left(\frac{1}{\epsilon}\sqrt{\frac{k\log(d/k)}{n}}\right)$ error in expectation.

Empirical evaluation.

We implemented our algorithms and the anonymized source code can be found at https://github.com/DPSparseVector/dp-sparse, and we plan to open source it upon the publication of the paper. We evaluated our algorithms using both synthetic and real-world datasets. With the synthetic dataset, we could more easily control the parameters $k$, $d$, and $n$, and we could plot the asymptotical behavior of our algorithms. In comparison with prior communication-efficient works, our algorithms achieve a $5.0\times$ reduction in $L_{\infty}$ error and a $29.6\times$ reduction in mean square error for both event- and user-level LDP, for a typical choice of parameters, e.g., $n=10^{5}$, $d=10^{5}$, $k=64$ and $\epsilon=1.0$. At the same time, our algorithms consume insignificant communication cost. The report size is smaller or up to a few times larger than a TCP/IP packet headers (20 bytes).

We also tested our algorithms on several real-world datasets. Experiment shows a $1.8\times$ to $7.3\times$ reduction in $L_{\infty}$ error and a $3.1\times$ to roughly $114.3\times$ reduction in mean square error compared to prior schemes.

Additional contributions.

Besides the commonly considered user-level and event-level LDP, as a by-product of our upper bound constructions, we come up with a communication-efficient LDP mechanism under a more generalized $L$-neighboring notion. Two input configuations $\mathbf{v}=(v_{1},\ldots,v_{n})\in^{d\cdot n}$ and $\mathbf{v}^{\prime}=(v^{\prime}_{1},\ldots,v^{\prime}_{n})\in^{d\cdot n}$ are said to be $L$-neighboring, iff they are otherwise identical except for one user’s coordinates $v_{i}$ and $v^{\prime}_{i}$, and moreover, $\|v_{i}-v^{\prime}_{i}\|_{1}\leq L$. Roughly speaking, a mechanism satisfies $(\epsilon,\delta)$-LDP for $L$-neighboring input configurations if the server cannot $(\epsilon,\delta)$-distinguish two $L$-neighboring input configurations (under the standard distance notion of $(\epsilon,\delta)$-differential privacy). Note that the commonly known user- and event-level LDP notions are special cases of the above more generalized notion, for $L=2k$ and $L=2$, respectively. Therefore, introducing the generalized $L$-neighboring notion allows us to study user- and event-level LDP under a more unified lens; and indeed we use it as an intermediate stepping stone to get our main results (Theorems 1, 2, and 3). We believe that this generalized $L$-neighboring notion can be of independent interest in some practical applications. For example, Abadi et al. considered a gradient clipping technique where each user would clip its gradient vector to a smaller range (thus pruning excessively large or small values) before sending it to the server. This technique allows them to more tightly bound the $L_{1}$ norm of each user’s contribution.

Technical Roadmap

In this section, we give an informal technical overview of our results.

For simplicity, we first focus on the special case of designing a frequency estimation mechanism that satisfies event-level LDP. Recall that the frequency estimation problem is a special case of our general formulation of vector mean estimation. In frequency estimation, each client $i\in[n]$ has a binary vector $v_{i}\in\{0,1\}^{d}$, denoting whether the client owns each item from a universe of $d$ items. The server wants to estimate the frequency of each item. Once we understand how to design an event-level LDP mechanism for frequency estimation, we can later extend our techniques to 1) support user-level LDP; and 2) support the more general case of vector mean estimation where the client’s vector is from a real domain.

Recall that prior works have proposed $1$-sparse frequency estimation mechanisms that achieve optimal error, that is, $\widetilde{O}(\frac{1}{\epsilon\sqrt{n}})$ error, incurring only logarithmic communication. In our problem, each client owns $k$ items rather than $1$. Therefore, a strawman idea is through a $k$-fold repetition of the $1$-sparse scheme. Specifically, each client can pretend to be $k$ virtual clients, and each virtual client owns only one item. Imagine that we run a $1$-sparse scheme over these $kn$ virtual clients. Since each client acts as $k$ virtual clients, its communication cost is $\widetilde{O}(k)$ which is independent of the universe size $d$. The resulting $L_{\infty}$ error would be $\widetilde{O}(\frac{1}{\epsilon\sqrt{kn}})$ over all $kn$ virtual clients. In reality, we want to take the mean over the $n$ real clients. After renormalizing, the actual error is $\widetilde{O}(\frac{\sqrt{k}}{\epsilon\sqrt{n}})$.

This strawman scheme gives non-trivial bounds, but does not achieve optimal $\widetilde{O}(\frac{1}{\epsilon\sqrt{n}})$ error.

Our idea.

We devise a new scheme that combines the elegant ideas behind the $1$-sparse mechanism by Wang et al. with a new random binning idea. Our approach is as follows:

Each client $i\in[n]$ does the following:

Sample two random hash functions $h_{i}:[d]\rightarrow[k]$ and $s_{i}:[d]\rightarrow\{-1,1\}$.

Let $\{x_{1},\ldots,x_{k}\}\in[d]^{k}$ denote the $k$ items belonging to client $i\in[n]$. For each $j\in[k]$, place $x_{j}$ into the hash bin indexed $h_{i}(x_{j})$. Note that in total, there are $k$ hash bins per client.

For each hash bin $j\in[k]$, compute $B_{i,j}:=\sum_{x\in{\sf bin}_{j}}s_{i}(x)+{\sf Lap}(\frac{1}{\epsilon})$ where ${\sf Lap}(\frac{1}{\epsilon})$ denotes Laplacian noise of average magnitude $\frac{1}{\epsilon}$.

Send to the server the tuple $(h_{i},s_{i},\{B_{i,j}\}_{j\in[k]})$ where $h_{i}$ and $s_{i}$ denote the description of the two hash functions.

Server does the following to estimate the fraction of clients that own an arbitrary item $x^{*}\in[d]$:

For each client $i\in[n]$, compute $j^{*}=h_{i}(x^{*})$.

Output $\frac{1}{n}\sum_{i\in[n]}B_{i,j^{*}}\cdot s_{i}(x^{*})$.

As mentioned later, to get our desired bounds, we need the hash functions $h_{i}$ and $s_{i}$ to be pseudorandom — however, we stress that the pseudorandomness assumption is needed only for load-balancing among the hash bins and not for proving privacy. In other words, our scheme satisfies information-theoretic LDP. Specifically, to sample a pseudorandom function (PRF), the client samples a random seed whose length is related to the strength of pseudorandomness and independent of $d$. To send the description of the hash function to the server, the client sends the pseudorandom seed to the server.

Informal utility analysis.

To gain intuition, we present an informal analysis of our scheme. The formal proofs (for the more generalized vector mean estimation scheme) are deferred to Section 2. Note that understanding the utility analysis also helps to understand why the scheme works.

Henceforth, we use ${\sf bin}^{i}_{j}$ to denote the set of items client $i$ places into its $j$-th bin (and when it is clear from the context which client $i$ we are referring to, we may omit $i$). Let $C_{i,j}=\sum_{x\in{\sf bin}^{i}_{j}}s_{i}(x)$ be the true aggregated “count” of the $j$-th bin belonging to the $i$-th client. Suppose that the server wants to know the frequency of item $x^{*}\in[d]$. To do this, the server computes the summation $\sum_{i\in[n]}B_{i,h_{i}(x^{*})}\cdot s_{i}(x^{*})=\sum_{i\in[n]}C_{i,h_{i}(x^{*})}\cdot s_{i}(x^{*})+\sum_{i\in[n]}{\sf Lap}(\frac{1}{\epsilon})$ — note that here we have not normalized the sum with the $\frac{1}{n}$ factor yet, we can defer this step to the end. The second part of the summation $\sum_{i\in[n]}{\sf Lap}(\frac{1}{\epsilon})$, is the summation of $n$ independent ${\sf Lap}(\frac{1}{\epsilon})$ noises, and thus its magnitude is roughly $\widetilde{O}(\frac{\sqrt{n}}{\epsilon})$. The first part of the summation $\sum_{i\in[n]}C_{i,h_{i}(x^{*})}\cdot s_{i}(x^{*})$ can be further decomposed into two sources of contributions:

Each client $i$ who owns $x^{*}$ contributes one $+1$ term to the summation because $(s_{i}(x))^{2}=1$.

For each client $i$ and each item $x\neq x^{*}$ owned by the client such that $h_{i}(x)=h_{i}(x^{*})$, it contributes $s_{i}(x)\cdot s_{i}(x^{*})$ to the summation, which is a random choice of $-1$ or $+1$ assuming that $s_{i}(\cdot)$ is a random oracle.

Thus, 1) corresponds to to the true count of the item $x^{*}$, whereas 2) is can be viewed as the result of a random walk of expected length $O(n)$, i.e., a random noise of magnitude roughly $\widetilde{O}(\sqrt{n})$. In particular, the length of this random walk is upper bounded by the total load of the hash bins $\sum_{i\in[n]}|{\sf bin}^{i}_{h_{i}(x^{*})}|$, which is $O(n)$ assuming that each $h_{i}$ is a random oracle.

Summarizing the above, the estimated count is the true count plus roughly $\widetilde{O}(\frac{\sqrt{n}}{\epsilon})$ noise. Finally, when the server normalizes the above sum by $\frac{1}{n}$ to compute the average, the resulting error becomes $\widetilde{O}(\frac{1}{\epsilon\sqrt{n}})$. Note that in Theorem 2, the precise expression for the error bound has an extra $\log\frac{d}{\beta}$ term which we ignore here, where $\beta$ is the failure probability for the error bound. Specifically, the $\log d$ term arises from taking a union bound over the universe of $d$ elements and the $\log\frac{1}{\beta}$ term comes from a precise measure concentration bound on the error — we defer these precise calculations to the subsequent technical sections.

At this point, it is helpful to observe that in this construction, the error comes from two sources — this observation will later help us to generalize the scheme to user-level LDP:

Noise component: the first source of error is the sum of $n$ independent ${\sf Lap}(\frac{1}{\epsilon})$ noises, one for each ${\sf bin}^{i}_{h_{i}(x^{*})}$ where $i\in[n]$;

Colliding items component: the second source of error is the random contribution of either $+1$ or $-1$ from each element $x\neq x^{*}$ that each client $i$ places into its bin ${\sf bin}^{i}_{h_{i}(x^{*})}$.

In the above, we assumed that the hash functions $h_{i}$’s and $s_{i}$’s are random oracles. In practice, we instantiate the hash functions using pseudorandom functions.

Informal privacy analysis.

We now give an informal privacy analysis, while deferring the formal proofs to Section 2. We want to show that the scheme satisfies $\epsilon$-event-level-LDP. Fix the hash functions $h_{1},\ldots,h_{n},s_{1},\ldots,s_{n}$, and consider two input configurations $\mathbf{v},\mathbf{v}^{\prime}\in\{0,1\}^{d\cdot n}$ that differ in only one position. Let $C_{i,j}=\sum_{x\in{\sf bin}_{i,j}}s_{i}(x)$ be the true aggregated “count” of the $j$-th bin belonging to the $i$-th client, when the input configuration is $\mathbf{v}$; and let $C^{\prime}_{i,j}$ be the corresponding quantity when the input configuration is $\mathbf{v}^{\prime}$. It must be that all $C_{i,j}$ and $C^{\prime}_{i,j}$ are the same everywhere except for one bin $j^{*}$ corresponding to one client $i^{*}$. Moreover, for the only location where they differ, it must be that $|C_{i^{*},j^{*}}-C^{\prime}_{i^{*},j^{*}}|\leq 1$. Having observed this, it is not too hard to show that adding Laplacian noise of average magnitude $\frac{1}{\epsilon}$ to each bin suffices for achieving $\epsilon$-event-level-LDP.

2 Extension: a User-Level LDP Mechanism for Frequency Estimation

One trivial way to obtain user-level LDP is to directly use the aforementioned warmup scheme, and simply apply standard privacy composition theorems to reset the parameters. Specifically, to achieve $\epsilon$-user-level-LDP, we would need to plug in a privacy parameter of $\frac{\epsilon}{k}$ when invoking the warmup scheme. This results in an error bound of $\widetilde{O}(\frac{k}{\epsilon\sqrt{n}})$ which is an $\widetilde{O}(\sqrt{k})$ factor away from optimal.

Another strawman idea for each client to randomly sample $1$ item out of its $k$ items, apply the $1$-sparse mechanism to the sampled items, and finally, renormalize the estimate accordingly . Unfortunately, it is not hard to show that the resulting error would again be $\widetilde{O}(\frac{k}{\epsilon\sqrt{n}})$, an $\widetilde{O}(\sqrt{k})$ factor away from optimal. Note also that if a client has strictly fewer than $k$ items, it needs to first pad its input to $k$ with filler items, and then apply the the sampling and $1$-sparse mechanism.

Our approach.

Our approach is to generalize our warmup mechanism. Suppose we want to achieve $(\epsilon,\delta)$-LDP under $L$-neighboring input configurations. Recall that two input configurations $\mathbf{v}=(v_{1},\ldots,v_{n})\in\{0,1\}^{d\cdot n}$ and $\mathbf{v}^{\prime}\in(v^{\prime}_{1},\ldots,v^{\prime}_{n})\in\{0,1\}^{d\cdot n}$ are $L$-neighboring iff they differ in only one user’s contribution $v_{i}$ and $v^{\prime}_{i}$, and moreover, $|v_{i}-v^{\prime}_{i}|_{1}\leq L$. Note that user-level LDP is simply a special case where $L=k$. In other words, we want the server’s view to be $(\epsilon,\delta)$-close for two input configurations $\mathbf{v}=(v_{1},\ldots,v_{n})\in\{0,1\}^{d\cdot n}$ and $\mathbf{v}^{\prime}\in(v^{\prime}_{1},\ldots,v^{\prime}_{n})\in\{0,1\}^{d\cdot n}$ under the distance notion of the standard $(\epsilon,\delta)$-differential privacy definition . In our reasoning below, we will carry around the parameter $L$, and at the end, we can plug in $L=k$ to get the user-level LDP result. However, as noted earlier in Section 1, the more general scheme parametrized by $L$ can be of independent interest.

Our generalized scheme is almost the same as the warmup scheme, except with the following modifications:

Each client now has $b$ hash bins rather than $k$ bins as in the warmup scheme. For now, we leave the choice of $b$ unspecified, and work out the optimal choice later.

Each client $i\in[n]$ now computes the noisy sum $B_{i,j}$ as $B_{i,j}:=\sum_{x\in{\sf bin}_{j}}s_{i}(x)+{\sf Lap}(\frac{1}{\epsilon^{\prime}})$ where

Informal privacy analysis.

Consider two $L$-neighboring input configurations $\mathbf{v}$ and $\mathbf{v}^{\prime}$, and fix all hash functions $h_{1},\ldots,h_{n}$ and $s_{1},\ldots,s_{n}$. Let $C_{i,j}:=\sum_{x\in{\sf bin}^{i}_{j}}s_{i}(x)$ be the true “count” of ${\sf bin}^{i}_{j}$ under $\mathbf{v}$ and let $C^{\prime}_{i,j}$ be the corresponding quantity under $\mathbf{v}^{\prime}$. Now, consider the vectors ${\bf C}=\{C_{i,j}\}_{i\in[n],j\in[b]}$ and ${\bf C}^{\prime}=\{C^{\prime}_{i,j}\}_{i\in[n],j\in[b]}$. We want to show that $|{\bf C}-{\bf C}^{\prime}|_{1}\leq\min(L,O(\sqrt{{bL\cdot\log\frac{b}{\delta}}})$ with probability $1-\delta$. If so, adding the aforementioned noise is sufficient for achieving $(\epsilon,\delta)$-LDP under $L$-neighboring. Now, $|{\bf C}-{\bf C}^{\prime}|_{1}\leq L$ is easy to see. Therefore, it suffices to show that $|{\bf C}-{\bf C}^{\prime}|_{1}\leq O(\sqrt{{bL\cdot\log\frac{b}{\delta}}})$ with probability $1-\delta$. Due to standard measure concentration bounds, when we change $\mathbf{v}$ to $\mathbf{v}^{\prime}$, for any fixed ${\sf bin}^{i}_{j}$, it holds that $|C_{i,j}-C^{\prime}_{i,j}|\leq O(\sqrt{\frac{L\cdot\log\frac{b}{\delta}}{b}})$ with probability $1-\frac{\delta}{b}$. Taking a union bound over all $b$ bins, we have that $|{\bf C}-{\bf C}^{\prime}|_{1}\leq O(\sqrt{{bL\cdot\log\frac{b}{\delta}}})$ with probability $1-\delta$.

Informal utility analysis and optimal choice of b𝑏b.

As in the earlier event-level LDP scheme, the error in the final summation $\sum_{i\in[n]}B_{i,h_{i}(x^{*})}\cdot s_{i}(x^{*})$ — without normalizing it with the $1/n$ factor yet — comes from two sources:

Noise component. The noise component consists of the summation of $n$ independent ${\sf Lap}(\frac{1}{\epsilon^{\prime}})$ noises where $\epsilon^{\prime}=\frac{O(\epsilon)}{\min(L,\sqrt{bL\log\frac{b}{\delta}})}$. Thus, the total noise is roughly $O(\frac{1}{\epsilon}\cdot\sqrt{n}\cdot\min(L,\sqrt{bL\log\frac{b}{\delta}}))$.

Colliding items component. The contribution from all colliding elements can be viewed as a random walk of length that is equal to the number of colliding elements in all $n$ bins $\{{\sf bin}^{i}_{h_{i}(x^{*})}\}_{i\in[n]}$. The number of colliding elements is concentrated around its expectation $\frac{nk}{b}$ with high probability, and thus the colliding items component results in roughly $\widetilde{O}(\sqrt{\frac{nk}{b}})$ error.

The total error is minimized when the noise component is roughly equal to the contribution from colliding elements, and we derive the optimal choice of $b$ as

Finally, observe that for $L=1$, i.e., for event-level-LDP, the optimal choice of $b=O(k)$. This shows that our event-level-LDP scheme in Section 2.1 is also a special case of the above more generalized scheme.

3 Generalizing to Real-Valued Vectors

In the more general case, each client $i$ holds a real-valued vector $v_{i}\in^{d}$, with at most $k\ll d$ non-zero coordinates. For example, each non-zero coordinate may represent the rating a user has given to a movie that it has watched. Chances are, each user has watched relatively few ($k$) movies out of the entire universe of $d$ movies.

It is not difficult to generalize the aforementioned schemes (Sections 2.1 and 2.2) to real-valued vectors. The only modification is the following: each client $i$ now computes $B_{i,j}$ as follows for $j\in[b]$ where $b$ denotes the number of bins per client:

where $v_{i,x}$ denotes the $x$-th coordinate of the client’s vector $v_{i}$, and the choice of $\epsilon^{\prime}$ is the same as before. Note that since our event-level-LDP scheme (Section 2.1) is a special case of the scheme in Section 2.2, the above works for the event-level-LDP scheme too.

The proof of the above generalized scheme is similar in spirit to the binary case but requires more careful calculation. In the subsequent technical sections, we directly prove the real-valued case, since this is the more general form.

4 Our Lower Bound

The framework in Bassily and Smith provides a lower bound for the event-level LDP under 1-sparse setting. Our event-level LDP upper bound tightly matches the lower bounds and therefore closes the case for event-level LDP. We observe that it is not hard to extend Bassily and Smith ’s proof to user-level-LDP, and the resulting lower bound matches the error achieved by our earlier upper bound. We defer the detailed presentation of the lower bound to Section 6.

5 Additional Related Work

. Privacy-preserving frequency estimation is a fundamental primitive in federated analytics. Earlier works in this space focused on the case when the universe size $d$ is small, and these works often suffer from per-client communication cost proportional to $d$. For example, RAPPOR and its variants encode each client’s item with one-hot encoding and performs coordinate-wise randomized response (RR) , which suffers from at least $d$ communication cost. Various subsequent works focused on how to compress the communication especially when the universe size $d$ is large, but each client has only one non-zero coordinate (i.e., the $1$-sparse case). Some of these algorithms achieved optimal estimation error and using only logarithmic bandwidth.

When each user can have up to $k$ items, one approach is to ask users to sample one item to report (e.g., ) using the $1$-sparse protocol (reviewed above) as a black-box. This approach introduces an error that is a $\sqrt{k}$ factor away from optimal for user-level LDP, and a $k$ factor away from optimal for event-level LDP.

Vector mean estimation under LDP.

For vector mean estimation under LDP, a few earlier works . showed how to achieve optimal error for the dense case when $d\approx k$, absent communication constraints. Bhowmick et al. showed how to achieve asymptotically optimal accuracy when $\epsilon>1$, but they require $\Omega(d)$ communication. Following works, such Harmony , Wang et al. , Li et al. and Zhao et al. improve the utility compared to . However, all of the above works focused on the dense case and did not consider sparse vectors. Chen et al. achieved optimal error and succinct communication for the $1$-sparse case. The PrivKVM work proposed an interactive protocol for vector mean estimation but it suffers from at least $\sqrt{d}$ error; the approach was later improved but the protocol is still interactive.

Computational differential privacy.

Our work focuses on an information theoretic notion of privacy. An orthogonal line of work considered computational differential privacy (CDP) in distributed analytics . Some of these works showed how to compute distributed summation with error comparable to central DP, relying on cryptographic assumptions. Recently, Bagdasaryan et al considered frequency estimation under CDP assuming $1$-sparsity, with the extra assumption that the frequency vector must be sparse too. For the more general setting of $k$-sparsity that we consider, it is not known how CDP can further improve the acccuracy in comparison with LDP, while still preserving succinct communication. We leave this as an open question.

Sparse vector data releasing under central-DP.

Previous works discussed a related setting that a single entity wishes to differentially privately release a $k$-sparse vector $v\in[0,u]^{d}$ ($u$ can be large). The neighboring notion is also defined by $L_{1}$ distance – a neighboring input pair $v\sim v^{\prime}$ iff. $\|v-v^{\prime}\|_{1}\leq 1$. For example, the newest work on this line – the ALP mechanism showed how to privately encode the $k$-sparse vector with $O(k\log(d+u))$ bits with $L_{\infty}$ decoding error of $O(\frac{\log d}{\epsilon})$. However, the encoding-decoding processes of these works are biased. Although this is acceptable in one-time data releasing, it is not suitable for mean estimation because the biased error will add up $n$ times. Therfore, there is no concentration property on the final estimation error. We implemented the ALP mechanism under event-level LDP and the mean estimation error is much worse than the simple $k$-fold repetition scheme. It is unclear how to debias these schemes to fit the need of mean estimation.

Preliminaries and Definitions

Differnetial privacy was first proposed by Dwork et al. . and has since become a de facto privacy notion.

We say the distributions of two random variables, $X$ and $X^{\prime}$ are $(\epsilon,\delta)$-close iff they have the same domain $D$ and for every subset $S\subseteq D$,

A function $f$ is $(\epsilon,\delta)$-DP w.r.t. some neighboring relation $\sim$ on its input domain iff for every pair $v,v^{\prime}\in\text{Domain}(f)$, s.t. $v\sim v^{\prime}$, the distributions of $f(v)$ and $f(v^{\prime})$ are $(\epsilon,\delta)$-close.

If a function $f$ is $(\epsilon,0)$-DP, we also say that $f$ is $\epsilon$-DP for short (w.r.t. the neighboring relation $\sim$).

2 Sparse Vector Mean Estimation

Consider $n$ clients, indexed by the set $[n]=\{1,2,\dots,n\}$. Each client has a real-value vector $v_{i}\in^{d}$. Also, each vector $v_{i}$ is $k$-sparse, i.e., it has at most $k$ non-zero coordinates. Different clients may have different non-zero coordinates. We use the notation $\mathbf{v}:=(v_{1},\dots,v_{n})$ to denote all clients’ inputs, and we also refer to $\mathbf{v}$ as an input configuration. A server wants to estimate the mean vector, $\bar{v}=\frac{1}{n}\sum_{i\in[n]}v_{i}$ through a non-interactive mechanism.

In a non-interactive mechanism, each client sends a single message to the server, and the server then computes an estimate of the mean vector $\bar{v}=\frac{1}{n}\sum_{i\in[n]}v_{i}$. Both the clients and the server can make use of randomness in their computation.

Henceforth, let $\sim$ denote some symmetric neighboring relation defined over two input configurations $\mathbf{v}\in^{d\cdot n}$ and $\mathbf{v}^{\prime}\in^{d\cdot n}$.

A non-interactive mechanism ${\mathcal{M}}$ satisfies $(\epsilon,\delta)$-LDP w.r.t. the neighboring relation $\sim$, iff for any two input configurations $\mathbf{v}\in^{d\cdot n}$ and $\mathbf{v}^{\prime}\in^{d\cdot n}$ such that $\mathbf{v}\sim\mathbf{v}^{\prime}$, it holds that

where $\textsf{view}_{{\mathcal{M}}}(\mathbf{v})$ is a random variable representing the server’s view upon input configuration $\mathbf{v}$; in particular, the view consists of all messages received by the server.

If a mechanism satisfies $(\epsilon,0)$-LDP, we also say that it satisfies $\epsilon$-LDP (w.r.t. to some neighboring relation $\sim$).

We say that a mechanism satisfies $(\epsilon,\delta)$-event-level-LDP, iff it satisfies $(\epsilon,\delta)$-LDP w.r.t. the following neighboring relationship: two input configurations $\mathbf{v}=(v_{1},\ldots,v_{n})\in^{d\cdot n}$ and $\mathbf{v}^{\prime}=(v^{\prime}_{1},\ldots,v^{\prime}_{n})\in^{d\cdot n}$ are considered neighboring, iff they differ in at most one position (i.e., one coordinate contributed by one user).

We say that a mechanism satisfies $(\epsilon,\delta)$-user-level-LDP, iff it satisfies $(\epsilon,\delta)$-LDP w.r.t. the following neighboring relationship: two input configurations $\mathbf{v}$ and $\mathbf{v}^{\prime}$ are considered neighboring if they differ in at most one user’s contribution.

We say that a mechanism satisfies $(\epsilon,\delta)$-LDP for $L$-neighboring, iff it satisfies $(\epsilon,\delta)$-LDP w.r.t. the following $L$-neighboring notion: two input configurations $\mathbf{v}$ and $\mathbf{v}^{\prime}$ are considered $L$-neighboring, iff the two vectors are otherwise identical except for at most one user’s contribution $v_{i}$ and $v^{\prime}_{i}$; and further, for the user $i$ where the two vectors differ, it must be that $\|v_{i}-v^{\prime}_{i}\|_{1}\leq L$.

For the case of $k$-sparse binary vectors where each client’s $v_{i}\in\{0,1\}^{d}$, the following simple facts hold. A mechanism satisfies $(\epsilon,\delta)$-LDP for $1$-neighboring, if and only if it is $(\epsilon,\delta)$-event-level-LDP. A mechanism satisfies $(\epsilon,\delta)$-LDP for $k$-neighboring, if and only if it satisfies $(\epsilon,\delta)$-user-level-LDP. More generally, for the case of $k$-sparse real-valued vectors where each client’s $v_{i}\in^{d}$, the following facts hold. If a mechanism satisfies $(\epsilon,\delta)$-LDP for $2$-neighboring, it must also satisfy $(\epsilon,\delta)$-event-level-LDP. If a mechanism satisfies $(\epsilon,\delta)$-LDP for $2k$-neighboring, it must also satisfy $(\epsilon,\delta)$-user-level-LDP.

Throughout the paper, unless otherwise noted, we use $L_{\infty}$-error to characterize the utility of our vector mean estimation mechanism. Specifically, $L_{\infty}$-error takes the maximum absolute error over all $d$ coordinates.

For the special case where $k=1$, Bassily and Smith proved the following lower bound on the error of any $(\epsilon,\delta)$-event-level-LDP mechanism — note also that for the case $k=1$, event-level and user-level LDP are the same up to a constant factor.

Suppose that $k=1$. For any $\epsilon=O(1)$ and $0\leq\delta\leq o(\frac{\epsilon}{n\log n})$, any non-interactive mechanism that satisfies $(\epsilon,\delta)$-event-level-LDP must incur expected $L_{\infty}$ error of magnitude at least

Sparse Vector Mean Estimation

We give a unified algorithm that can be parametrized to achieve either event-level or user-level LDP, or LDP under $L$-neighboring. Our proposed algorithm is presented in Algorithm 1.

In the above algorithm, the clipping algorithm is needed only if we want to achieve $(\epsilon,0)$-DP under user-level LDP — see Section 4.4 for more details. For all other cases, we achieve $(\epsilon,\delta)$-LDP.

Further, in the above algorithm, we assumed that the server computes the entire mean vector. However, when the universe size $d$ is very large (e.g., the space of all possible URLs), the server may not want to write down the entire mean vector. Instead, it may wish to query $\hat{v}_{x}$ for a specific item $x\in[d]$, e.g., the frequency of a specific URL. In this case, the server need not iterate through every $x\in[d]$, it only needs to invoke Line 13 for the items $x\in[d]$ that it cares about.

In the above algorithm, we assumed that the client is transmitting real-valued numbers to the server. In practice, we can truncate and discretize real-valued numbers before transmitting, and ensure that the per-client communication cost is only $O(b\log k)$. The additional error introduced in the discretization process is asymptotically absorbed by the existing error terms, and therefore this step does not introduce any additional asymptotical error. See Appendix 8.1 for details.

Assuming $nk/b\geq\log(5d/\beta)$. Assuming the hash functions $h$ and $s$ are random oracles. Algorithm 1 satisfies $L$-neighboring $(\epsilon,\delta)$-LDP. With probability at least $1-\beta$, the algorithm 1 outputs an estimation $\hat{v}$ with $L_{\infty}$ error of $O\left(\left(\sqrt{\frac{k}{b}}+\frac{\Delta}{\epsilon}\right)\sqrt{\frac{\log(d/\beta)}{n}}\right)$. The per-client communication cost is $O(b\log k)$.

Note that in practice, we can instantiate $h$ and $s$ with pseudorandom functions (PRFs) rather than random oracles. As mentioned earlier, the computational assumption here is not needed for the privacy but only for measure concentration.

We present the privacy-related proof in Section 4.2 and the utility-related proof in Section 4.3. For the communication cost analysis, see the discussion in Appendix 8.1.

2 Privacy Analysis

Notice that the general $L$-neighboring LDP notion captures the requirement of event-level LDP($L=2$) and user-level LDP($L=2k$). Therefore, we only need to prove our algorithm is $L$-neighboring LDP and instantiate with corresponding $L$ value for event- and user-level LDP. For now, we take the bin number $b$ as an unspecified variable and we will provide the optimal selection of $b$ later in the utility section.

Given two neighboring input configuration $\mathbf{v},\mathbf{v}^{\prime}$, from which one client’s inputs are different, denoted as vectors $v,v^{\prime}$. Then, $\|v-v^{\prime}\|_{1}\leq L$. We wish to bound the $L_{1}$ difference for the “raw bin values” $B_{1},\dots,B_{b}$ and $B^{\prime}_{1},\dots,B^{\prime}_{b}$ generated by two independent invocations of the client’s algorithm.

Given any two neighboring vectors $v,v^{\prime}$. Taking the randomness of $h$ and $s$, if $\Pr[\sum_{j\in[b]}|B_{j}-B^{\prime}_{j}|\geq\Delta]\leq\delta$, then adding Laplacian noise of ${\sf Lap}(\frac{\Delta}{\epsilon})$ ensures the two invocations of the client-side algorithm’s output distributions are $(\epsilon,\delta)$-close.

The proof is simple that one can compute the privacy budget loss in each bin and the total budget will be bounded by $\epsilon$. We defer the proof to the appendix 8.2.

For any $h,s$, rewrite $\sum_{j\in[b]}|B_{j}-B^{\prime}_{j}|=\sum_{j\in[b]}\left|\sum_{l\in[d],h(l)=j}s(l)(v_{j}-v^{\prime}_{j})\right|$. With absolute inequality, the $s(l)$ term can be removed and the above expression is at most $\sum_{j\in[b]}\sum_{l\in[d],h(l)=j}|v_{j}-v^{\prime}_{j}|$, which is exactly $L$. This proves the privacy property when $L\leq k^{\frac{1}{3}}$ where we set $\Delta=L$.

Assuming $L/b\geq\log(2b/\delta)$. Consider any two neighboring vectors $v,v^{\prime}\in[-1,+1]^{d}$ such that $\|v-v^{\prime}\|_{1}\leq L$. We have that $\Pr\left[\sum_{j\in[b]}|B_{j}-B^{\prime}_{j}|>3\sqrt{bL\log(2b/\delta)}\right]\leq\delta$.

Using the condition that $\mu=\frac{L}{b}\geq\log(b/\delta)$, we have $\frac{\frac{9}{2}\mu}{2\mu+2\sqrt{\mu\log(2b/\delta)}}\geq\frac{9}{8}\geq 1$. Therefore, $\Pr\left[|Z|\geq 3\sqrt{\mu\log(2b/\delta)}\right]\leq\delta/b$. Taking the union bound over all $b$ bins, we have the total difference in all bins are at most $3\sqrt{bL\log(2b/\delta)}$ with probability at least $1-\delta$. ∎

By Claim 13 and Lemma 14, setting the noise parameter to $\Delta=3\sqrt{bL\log(2b/\delta)}$ is enough to achieve $(\epsilon,\delta)$-privacy under $L$-Neighboring LDP, assuming $L/b\geq\log(2b/\delta)$. In practice, when we search for the optimal $b$, we will carefully set $b$ such that the condition $L/b\geq\log(2b/\delta)$ is held.

3 Utility Analysis

We first provide the simplified version of the utility part for the main theorem for general parameter settings – bin number $b$, clipping range $\eta$ and the noise parameter $\Delta$. The full proof is deferred to Appendix 8.3. Then, we will discuss how to choose the optimal $b$ to achieve the best utility under different scenarios.

Clipping error.

Laplacian noise error.

Finally, we look at the absolute error term introduced by adding Laplacian noise. It turns out that the error’s distribution is the same as the distribution for the mean of $n$ i.i.d. Laplacian variables with parameter $\frac{\Delta}{\epsilon}$. Using the concentration bound for Laplacian noise and taking the union bound over all $x\in[d]$, the maximal error is bounded by $O\left(\frac{\Delta}{\epsilon}\sqrt{\frac{\log(d/\beta)}{n}}\right)$ with probability $1-O(\beta)$.

Combine the above arguments. By taking the union bound and setting the constants appropriately, we can conclude that the $L_{\infty}$ error is $O\left(\left(\sqrt{\frac{k}{b}}+\frac{\Delta}{\epsilon}\right)\sqrt{\frac{\log(d/\beta)}{n}}\right)$ with probability $1-\beta$. ∎

4 Achieving (ϵ,0)italic-ϵ0(\epsilon,0)-user-level LDP

Evaluation

To evaluate our approach, we implement it with C++, compile it with gcc4.8 and the C++11 standard. We use 40-bit random seeds to generate the hash functions. For simplicity, we directly use 32-bit floating numbers to store and transmit real values.

Datasets.

We evaluate the algorithms for both synthetic and real-world datasets. For the synthetic dataset, we assume there are $10^{5}$ users, each with a vector of dimension $d$ and sparsity $k$. We first randomly sample the non-zero coordinates according to Zipf’s distribution with a suitable degrading parameter ($s=1.4$). We choose the Zipf’s distribution because it naturally appears in real-world data analytics. For each sampled non-zero coordinate, the actual value is sampled from a Gaussian distribution with mean $\mu=1$ and standard deviation $\sigma=0.3$. Then the values are clipped to $$.

For the real-world dataset experiment, we downloaded three open-sourced datasets from Kaggle, including an online cloth shopping dataset , a clothing renting dataset and a movie rating dataset , where each record describes one activity (purchase, rent, or rating, respectively). Table 3 gives more information about the datasets. We select those records with client feedback ratings and normalize them to $$. Given the sparsity parameter is$k$, for clients with more than$k$records, we randomly sample$k$ records.

Metrics.

We consider both utility and communication cost fixing the privacy level (i.e., fixing $\epsilon$ and $\delta$). To measure utility, we use the $L_{\infty}$ error and the mean square error (MSE). Given $\hat{v}=\frac{1}{n}\sum_{i\in[n]}v_{i}$ as the true mean vector and $\bar{v}$ as the estimation vector, they are defined as:

For the communication cost, we measure the per-client communication cost: We sum up the byte-length of all the reports from the clients and compute the average report size.

Evaluation Roadmap.

We split the experiments into three groups: user-level LDP setting, event-level setting LDP, and the $L$-Neighboring setting. Within each group, we measure different methods varying three parameters: sparsity $k$, privacy budget $\epsilon$ (in most cases, we use $\delta=0$; but when $\delta>0$, e.g., for the naive perturbation scheme with Gaussian noise, we always use $\delta=10^{-5}$), and dimension size $d$. We mainly compare our proposed method with the $k$-fold repetition-plus-1-sparse mechanism (referred as $k$-fold repeition), the sampling + 1-sparse mechanism (referred as sampling), the naive pertubation mechanism (with Gaussian Noise ), Harmony and PCKV . We run the experiment 10 times and report the average error and the average communication cost.

2 Performance under User-level LDP

User-level LDP is the more standard setting in LDP analytics. Existing methods are mostly designed for user-level LDP. We first compare our method against existing ones in this setting.

We plot the $L_{\infty}$ error results in Figure 1(a) and the MSE results Figure 1(d). In our theoretical analysis, we prove that the $L_{\infty}$ error of our algorithm scales with $\sqrt{k}$. The sampling + 1-sparse method’s error scales with $k$, and other algorithm cannot utilize the sparsity. The figures show that our method has the smallest estimation error for the whole region when $k$ ranges from 1 to 1024. The error of the sampling solution and the naive perturbation mechanism scales with $k$ and they perform worse than PCKV and Harmony when the sparsity $k$ is larger than $\sqrt{d}$.

Varying privacy budget ϵitalic-ϵ\epsilon.

Varying dimension d𝑑d.

In many use cases, the domain size (vector length) can be extremely huge, such as all possible products on Amazon, all possible URL and all geographical location on the earth. In this experiment, we only measure the top 100 coordinate with the largest absolute mean value. This is actually inspired by a real use case where the domain size is sufficiently and the server only wishes to compute the value for a limited keys (e.g. website access analysis). The results are shown in Figure 1(b) and Figure 1(e). Our method provides an important feature – its utility and communication cost decouple from the domain size. Our method can maintain a stable estimation error even with very large dimension $d$, while using minimum communication cost. The naive perturbation scheme needs to communicate $O(d)$ bits between the clients and the server. In the very dense case, where $k\approx d$, PCKV and Harmony has slightly better estimation error because our method has the extra $\sqrt{\log n}$ term in the error. However, in the more sparse case, all other methods fail to provide any meaningful guess. The noticeable drop in the large $d$ region of the error curves for PCKV and Harmony is because they basically output a meaningless zero vector.

3 Performance under Event-level LDP

The results are plotted in Figure 2. Theoretically (from Table 1), our method is better than other methods by at least a polynomial gap $\sqrt{k}$ in terms of the $L_{\infty}$ error. The following experiments verify the theoretical results.

The results are shown in Figure 2(a) and Figure 2(d). The results matches our theoretical results that our methods are not scale with $k$ in event-level LDP. It also outperforms other methods for the whole range.

Varying privacy budget ϵitalic-ϵ\epsilon.

The results The results are shown in Figure 2(b) and Figure 2(e). The higher privacy budget are beneficial to all methods’ utility performance. Our algorithm still has the best estimation performance for the whole range.

Varying dimension d𝑑d.

The results are shown in Figure 2(c) and Figure 2(f). Again, our algorithm has decoupled from the dimension $d$ and it has much smaller error estimation than other methods.

4 Performance under L𝐿L-Neighboring LDP

The neighboring distance $L$ provides a better way to describe the middle ground between user-level LDP and event-level LDP. Our algorithm has theoretical $L_{\infty}$ error of $\min\{O(L),O((kL\log(1/\delta)^{\frac{1}{4}})),\\ O(\sqrt{k\log n})\}\cdot O(\frac{1}{\epsilon}\sqrt{\frac{\log d}{n}})$. In the experiment, we fix the sparsity $k=64$ and vary the neighboring $L_{1}$ distance from $1$ to $128$. In the case when $L\ll k$, the parameter configuration with $O((kL\log(1/\delta))^{\frac{1}{4}})$ error growing factor should have asymptotically advantage over the configuration with $O(\sqrt{k\log n})$ growing factor. However, in practice, we realize that the latter scheme(the algorithm with clipping) has a much smaller constant factor. Hence, in the case when $k$ is not large enough, we only see the optimized clipping scheme dominates the unclipped scheme. The mixed strawman solutions, including $k$-fold repetition scheme and sampling scheme, can only adapt to either event-level LDP or user-level LDP. PCKV and Harmony cannot fully utilize the relaxed privacy as a way to improve the estimation error. The naive perturbation mechanism has worse scaling factor than our method, but in the turning point where $L=\sqrt{k\log n}$, it roughly matches the error of our method.

5 Real-world Dataset Experiments

We compile the Clothing, Renting and Movie dataset to the sparse vector mean estimation problem. The description of the datasets can be found in Table 5. Our method achieves best accuracy in both event-level LDP setting and user-level LDP setting by a magnitude of gap. Specifically, compared to our method, the strawman scheme has an extra $\sqrt{k}$ factor in the $L_{\infty}$ error, which is roughly 2.4, 3.3 and 8.0 in the three datasets correspondingly. The Harmony and PCKV schemes do not output very meaningful estimation in the experiments because their algorithms have error scaled with the dimension $d$.

Lower Bound

In a previous work , Bassily and Smith showed a lower bound of $\Omega\left(\frac{1}{\epsilon}\sqrt{\frac{\log d}{n}}\right)$ on the $L_{\infty}$ error under the 1-sparse case with the constraints of $(\epsilon,o(\frac{1}{n\log n}))$-LDP (Theorem 11). The 1-sparse case can be seen as a special case for the general $k$-sparse vector mean estimation under event-level LDP. Our algorithm for event-level LDP matches this lower bound, making the error bound tight in the event-level LDP case.

We observe that it is not hard to extend the framework and prove a lower bound of $\Omega\left(\frac{1}{\epsilon}\sqrt{\frac{k\log(d/k)}{n}}\right)$ on the $L_{\infty}$ error of $k$-sparse vector mean estimation under the user-level LDP. For completeness, we present the full proof below.

In the lower bound proof, each client $i$ has a $k$-sparse input vector $v_{i}\in\mathcal{S}:=\{v\in\{0,1\}^{d}:\|v\|_{1}=k\}$, where the special case $k=1$ is essentially the one-item frequency estimation problem . Note that since this setting is a special case of real-valued mean vector estimation, the lower bound applies to mean vector estimation more generally.

Each client $i$ applies an $(\epsilon,\delta)$-differentially private (where any two inputs in $\mathcal{S}$ are neighboring) algorithm $\mathcal{Q}_{i}(\cdot)$ independently to produce $\mathbf{z}_{i}=\mathcal{Q}_{i}(v_{i})$ in some report space $\mathcal{Z}$. The server computes $\widehat{v}:=\mathcal{A}(\mathbf{z}_{1},\ldots,\mathbf{z}_{n})$, which estimates $\frac{1}{n}\sum_{i}v_{i}$. Then the following lower bound holds.

Let $0<\epsilon=O(1)$ and $0<\delta=o(\frac{\epsilon}{n\log n})$. Suppose for each client $i$, the (randomized) algorithm $\mathcal{Q}_{i}:\mathcal{S}\rightarrow\mathcal{Z}$ is $(\epsilon,\delta)$-differentially private, where any two inputs in $\mathcal{S}$ are considered as neighboring. Moreover, $\mathcal{A}:\mathcal{Z}^{n}\rightarrow\mathcal{S}$ is a (potentially randomized) aggregator function.

Then, there exists some distribution $\mathcal{P}$ on $\mathcal{S}$ (depending on $\mathcal{Q}_{i}$’s and $\mathcal{A}$) such that if every client $i$ independently generates a report $\mathbf{z}_{i}=\mathcal{Q}_{i}(v_{i})$, where $v_{i}$ is sampled from $\mathcal{P}$ independently, the expected error of estimating $\overline{v}:=\frac{1}{n}\sum_{i}v_{i}$ has the following lower bound:

${\mathbf{E}}[\|\mathcal{A}(\mathbf{z}_{1},\ldots,\mathbf{z}_{n})-\overline{v}\|_{\infty}]\geq\min\left\{\Omega\left(\frac{1}{\epsilon}\sqrt{\frac{\log|\mathcal{S}|}{n}}\right),1\right\}$,

where $\log|\mathcal{S}|=\log{d\choose k}\geq k\log(d/k)$.

Plugging in the definition of $\mathcal{S}$, the following corollary gives our main lower bound for user-level-LDP.

Observing that if $L=2k\leq\sqrt{d}$, then any two inputs in $\mathcal{S}$ has $L_{\infty}$ distance at most $L$. Hence, in this case, ${\mathbf{E}}[\|\mathcal{A}(\mathbf{z}_{1},\ldots,\mathbf{z}_{n})-\overline{v}\|_{\infty}]\geq\min\{\Omega(\frac{1}{\epsilon}\sqrt{\frac{L\log d}{n}}),1\}$

Proof roadmap.

Just like Bassily and Smith, our goal is to find a “hard” joint distribution $\mathcal{P}$ on the clients’ inputs $\mathbf{v}=(v_{1},\dots,v_{n})$, such that the expected $L_{\infty}$ estimation error is large for any $(\epsilon,\delta)$-user-level LDP algorithm, Here, the expectation is taken over the randomness coming from the input sampling and the algorithm. We construct the distribution $\mathcal{P}$ as following. First, a vector $V\in\{0,1\}^{d}$ is sampled uniformly at random from a candidate set $\mathcal{S}$ that includes all binary $k$-sparse vectors in $\{0,1\}^{d}$. Next, each client’s input $v_{i}$ is sampled i.i.d from a distribution $\mathcal{P}_{V}^{(\eta)}$ (using the same $V$ for all users) as follows:

where $U$ is drawn uniformly from $\mathcal{S}$. The distribution $\mathcal{P}_{V}^{(\eta)}$ is an instance of an $\eta$-degrading channel. To prove that any $(\epsilon,\delta)$-LDP algorithm has large error with respect to $\mathcal{P}_{v}^{(\eta)}$ for at least one $v\in\mathcal{S}$, we view the problem as an encoding-decoding process, then bound the error using Fano’s inequality. Each client $i$ generates a report $\mathbf{z}_{i}=\mathcal{Q}_{i}(v_{i})$. The joint reports $\mathbf{z}:=(\mathbf{z}_{1},\mathbf{z}_{2},\ldots,\mathbf{z}_{n})$ are viewed as a noisy encoding of $V$. In an attempt to recover $V$, the server aggregator function $\mathcal{A}$ is applied to produce the mean estimation $\mathcal{A}(\mathbf{z})$. Then, to decode the original $V$, the server removes the bias introduced by the degrading channel then rounds the estimation $\mathcal{A}(\mathbf{z})$ to the nearest binary vector $\widehat{V}$. A decoding error occurs if $\widehat{V}\neq V$.

The lower bound proof relies on two bounds on the probability of decoding error. On one hand, the differential privacy of each $\mathcal{Q}_{i}$ implies that the mutual information $I(V;\mathbf{z})$ is small, which means that the decoding error probability is large by Fano’s inequality. On the other hand, a small $L_{\infty}$-error estimation of the mean vector implies that the original $V$ can be recovered from $\mathcal{A}(\mathbf{z})$ with high probability. These effects limit the decoding error probability and give us a lower bound on the mean vector estimation error. That is, for small enough $\delta=o(\frac{\epsilon}{n\log n})$, we find a distribution $\mathcal{P}$ over candidate set $\mathcal{S}$ that implies a lower bound of $\Omega(\frac{1}{\epsilon}\sqrt{\frac{\log|\mathcal{S}|}{n}})$ on the $L_{\infty}$-error of mean vector estimation. By considering $k$-sparse vectors in $\{0,1\}^{d}$, (for which $|\mathcal{S}|={d\choose k}$), we obtain the lower bound of $\Omega\left(\frac{1}{\epsilon}\sqrt{\frac{k\log(d/k)}{n}}\right)$.

In the interest of space, we defer the detailed lower bound proof to Appendix 9.

Acknowledgments

This work is in part supported by a Packard Fellowship, NSF awards under the grant numbers 2128519 and 2044679, a grant from ONR and a gift from Cisco. T-H. Hubert Chan was partially funded by the Hong Kong RGC under the grants 17200418 and 17201220.

References

Appendices

Additional Preliminaries

Assume the distribution of $X$ and $X^{\prime}$ are $(\epsilon_{1},\delta_{1})$-close. If for any of $x\in Domain(X)$, the posterior distribution of random varaible $Y$ conditioned on $X=x$ and random variable $Y^{\prime}$ conditioned on $X^{\prime}=x$ are $(\epsilon_{2},\delta_{2})$-close, then the distribution of $(X,Y)$ and $(X^{\prime},Y^{\prime})$ are $(\epsilon_{1}+\epsilon_{2},\delta_{1}+\delta_{2})$-close.