Exactly Minimax-Optimal Locally Differentially Private Sampling

We thank Reviewer NxAu for thoroughly reviewing our paper and providing valuable comments.

Response to the first weakness on comparison with previous work

We agree that a certain part of our results can be seen as a generalization of the previous work [35], as we mentioned in the "Comparison with Previous Work [35]" paragraph in Section 3.1. However, we would like emphasize that our work has non-trivial contributions beyond [35] in the following aspects:

• We prove the universal optimality of the mechanism for all $f$-divergences, whereas the previous work [35] only considered the KL divergence. Our proof involves numerous non-trivial steps relying on general properties satisfied for all $f$-divergences, not specific properties of KL divergence.

• The exact characterization of minimax loss requires a converse proof involving the derivation of the matching lower bound on the loss applicable to all possible mechanisms, not just to the mechanisms similar to [35]. By proving the matching lower bound that holds for all possible mechanisms, we have established the exact minimax optimality. Note that the previous work [35] does not provide explicit guidance on the choice of reference distribution. More specifically, the performance of their mechanism heavily depends on the choice of the reference distribution. Quite contrary, our work implicitly figures out the optimal reference measure with respect to the minimax loss.

Response to the second weakness on weak result

We agree that many existing privacy mechanisms, not limited to sampling scenarios, can be seen as skewing an original distribution towards a specific distribution (such as the uniform distribution). But the challenging part is determining how and to what extent to skew the distribution to achieve the optimal privacy-utility trade-off (PUT). The significance of our research lies in precisely determining the optimal PUT through non-trivial achievability and converse proofs.

Response to the third weakness on main motivation

Our setup has recently gained attention due to its practical applications in generative models. For example, as mentioned in the introduction, [36] uses the private sampling mechanism for fine-tuning large language models.
As mentioned by the reviewer, however, we may consider the scenario where the distributions of the users are correlated. One possible approach is to assume an underlying distribution on distributions from which each user's original distribution is drawn, and then infer such an underlying distribution given samples from the users. Also, we can formulate more general problems such as producing a distribution per user or generating multiple samples per user, which we mentioned in the introduction and the conclusion of the paper, respectively. We believe that the problem we considered is a simple yet fundamental one that serves as a stepping stone towards addressing these more general and practically interesting problems.

Response to the first weakness on alternative mechanism

We thank Reviewer 9St7 for raising an interesting point. We are truly grateful for the thoughtful review of our paper.

Before we discuss about the minimax-optimality of the proposed scheme by the reviewer, we would like to emphasize that even though a simple randomized response-based mechanism provides an alternative achievability result, proving its optimality is a highly non-trivial finding. The exact characterization of the minimax loss requires a converse proof of deriving the matching lower bound on the loss applicable to all possible mechanisms, not just to randomized response or similar mechanisms. We believe that one of the technical novelties of our work lies in this converse proof.

Now let us discuss the alternative mechanism suggested by the reviewer. As mentioned by the reviewer, for the discrete case, we can simply sample an element from the original distribution $P$ and apply the $k$-randomized response to that element. This mechanism, which we denote as $\mathbf{Q}^{\dagger}_{k,\epsilon}$, can be written as

$\mathbf{Q}^{\dagger}_{k,\epsilon}(x|P) = \frac{e^\epsilon}{e^\epsilon + k - 1}P(x) + \frac{1}{e^\epsilon+k-1} (1-P(x)).$

We can design a similar mechanism $\mathbf{Q}^{\dagger}_{c_1,c_2,h,\epsilon}(P)$ for the continuous case as follows:

• First, toss a biased coin with head probability $\gamma$.
• If head, sample from the original distribution $P$.
• Otherwise, sample from the reference distribution $\mu$ whose pdf is $h$.
• The head probability $\gamma$ is determined by $(c_1,c_2,\epsilon)$ to satisfy $\epsilon$-LDP tightly. It is given as $\gamma = \frac{e^\epsilon-1}{(e^\epsilon-1)(1-c_1)+c_2-c_1}$.

Such $\mathbf{Q}^{\dagger}_{c_1,c_2,h,\epsilon}(P)$ for the continuous case can be written as

$\mathbf{Q}^{\dagger}_{c_1,c_2,h,\epsilon}(P) = \gamma P + (1-\gamma) \mu.$

It can be shown that in both setups of Theorems 3.1 and 3.3, the aforementioned mechanism $\mathbf{Q}^{\dagger}$ is also minimax-optimal for any $f$-divergences (here, we suppress the subscripts $(k,\epsilon)$ or $(c_1,c_2,h,\epsilon)$ for notational convenience).

However, as the reviewer mentioned, $\mathbf{Q}^{\dagger}$ performs worse for non-extreme distributions. Indeed, we showed that $\mathbf{Q}^{ * }$ outperforms $\mathbf{Q}^{\dagger}$ for any distribution:

• For any $f$-divergence $D_f$ and any $P \in \tilde{\mathcal{P}}$, we have $D_f(P \Vert \mathbf{Q}^{\dagger}(P)) \geq D_f(P \Vert \mathbf{Q}^{ * }(P))$.

The above statement is a corollary of a stronger result about $\mathbf{Q}^{ * }$, which improves the results of [35] in a non-trivial way:

• For any $f$-divergence, $\mathbf{Q}^{ * }(P)$ is the projection of $P$ onto a specific $\epsilon$-close set, in which $\mathbf{Q}^{\dagger}$ also lies.

We aim to revise the paper accordingly. In particular, we will mention the alternative mechanism that achieves minimax-optimality and provide comments on it in the final version. Thank you once again for highlighting this interesting point.

Response to the second weakness on comparison with previous work

• First, as described in the response to the first weakness, the proposed mechanism $\mathbf{Q}^{ * }$ indeed generalizes the approach of [35]: $\mathbf{Q}^{ * }(P)$ corresponds the projection of $P$ onto an $\epsilon/2$-ball centered at some reference measure for any $f$-divergence. We would like to emphasize that our work has non-trivial contributions beyond [35] in the following aspects:

  1. Deriving the projection in a closed form for all $f$-divergences is not immediate from [35] which only consider KL divergence. Although the technicalities cannot be fully detailed in the rebuttal due to space constraints, showing general properties satisfied for all possible $f$, which may be non-differentiable, involves some non-trivial steps compared to [35].

  2. Finding a right reference measure is an important step to characterize the exact optimality. Although we can apply the approach of [35] with an arbitrary reference measure, proving the minimax-optimality with respect to a specific reference measure involves highly non-trivial converse techniques. Our work differs from [35] in that we implicitly figured out the optimal reference measure with respect to the minimax loss.

• Second, to the best of our knowledge, the algorithm in [35] to find a KL divergence projection for the continuous case (i.e., MBDE) only guarantees to find an approximate projection, not exact projection, even if a reference measure is given. Therefore, it is unlikely that a variation of MBDE will retrieve the exactly optimal loss for the continuous case in Theorem 3.3, even for the optimal reference measure we identified. In contrast, the proposed mechanism $\mathbf{Q}^{ * }$, which has a closed form, achieves the exactly optimal loss both for discrete and continuous cases, thereby eliminating the need for an iterative algorithm for projection as used in [35].

  In more detail, MBDE iteratively updates the candidate $Q_t$ of $\mathbf{Q}(P)$ based on $Q_{t-1}$ until convergence, employing a soft decision rule (called a weak learner) to distinguish a sample from $Q_{t-1}$ and that from $P$. For $Q_t$ to converge to the optimal one, the accuracy of the weak learner ($\frac{\gamma_P + \gamma_Q}{2}$ in [35]) must approach 1 as $t \rightarrow \infty$. However, with the aim of making $Q_t$ as close to $P$ as possible, such accuracy is expected to decrease over $t$. To the best of our understanding of [35], there is no guarantee that this accuracy will converge to 1; thus, we cannot guarantee that MBDE will find the exact projection.

Response to the first question on the approximation error

We thank Reviewer KHbV for asking a practically important question. We briefly mentioned the effect of the approximation error in calculating $r_P$ on the privacy budget in Appendix F.2, and we considered this effect in the experiment. Let us analyze the effect of this error in more detail in the following.

Consider the continuous case in Theorem 3.3, and let $q_{p,r}(x) = \mathrm{clip}\left(\frac{1}{r} p(x); bh(x), be^\epsilon h(x)\right)$, as in the RHS of equation (13). Suppose we set error tolerances $0\leq \delta_1 < 1$ and $\delta_2 \geq 0$, and for each $P \in \tilde{\mathcal{P}}$, we find $r_P$ such that $\int q_{p,r_P}(x)dx \in [1-\delta_1,1+\delta_2]$. Then, we define the pdf of $\mathbf{Q}^{ * }\_{c_1,c_2,h,\epsilon}(P)$ as $q_{p,r_P}(x) / \int q_{p,r_P}(x)dx$. Since $q_{p,r_P}(x) \in [b,be^\epsilon]$, we have $q_{p,r_P}(x) / \int q_{p,r_P}(x)dx \in \left[\frac{b}{1+\delta_2}, \frac{be^\epsilon}{1-\delta_1}\right]$, which implies that this approximated mechanism satisfies $\epsilon + \log \left(\frac{1+\delta_2}{1-\delta_1}\right)$-LDP. Thus, allowing an approximation error does not require the introduction of $(\epsilon,\delta)$-LDP but instead necessitates using a larger privacy budget. Note that to sample from $\mathbf{Q}^{ * }\_{c_1,c_2,h,\epsilon}(P)$, knowing the precise value of $\int q_{p,r_P}(x)dx$ is unnecessary; it suffices to know $q_{p,r_P}(x)$, utilizing known MCMC methods. In the experiment for the continuous case, we allowed the error tolerances $\delta_1=\delta_2=10^{-5}$, and for each given $\epsilon \in \\{0.1,0.5,1,2,5\\}$, we implemented $\mathbf{Q}^{ * }\_{c_1,c_2,h,\epsilon'}$ for $\epsilon'=\epsilon + \log \frac{1-\delta_1}{1+\delta_2}$, ensuring the actual privacy budget matched the initially given $\epsilon$. We note that there is a typo in Appendix F.2 of the manuscript, which we found after submission. In lines 961-962, the sentence

"we modify the value of $\epsilon$ by $\epsilon'=\frac{1-\delta}{1+\delta}e^\epsilon$"

should be revised as

"we modify the value of $\epsilon$ by $e^{\epsilon'}=\frac{1-\delta}{1+\delta}e^\epsilon$".

We also checked the code for the experiment and confirmed that the correct formula was used in the code.

Response to the second question on the uniqueness

A related question was raised by Reviewer 9St7. Reviewer 9St7 conjectured that a simple randomized response-based mechanism is also minimax-optimal. In conclusion, we checked that Reviewer 9St7's mechanism is also minimax-optimal, meaning our mechanism $\mathbf{Q}\_{k,\epsilon}^{ * }$ is not the unique optimal mechanism.

Specifically, Reviewer 9St7's mechanism works as follows: for the discrete case, an element is sampled from an original distribution $P$ and then subjected to $k$-randomized response. For the continuous case, the mechanism operates as follows:

• First, toss a biased coin with head probability that tightly achieves $\epsilon$-LDP.
• If head, sample from the original distribution $P$.
• Otherwise, sample from the reference distribution $\mu$ whose pdf is $h$.

We checked that in both setups of Theorems 3.1 and 3.3, this mechanism is also minimax-optimal for any $f$-divergences. However, the mechanism proposed in the paper has certain advantages over the aforementioned mechanism. Specifically, let $\mathbf{Q}^{ * }$ and $\mathbf{Q}^{\dagger}$ denote our proposed mechanism in the paper and Reviewer 9St7's mechanism, respectively. Then, we showed that $\mathbf{Q}^{ * }$ outperforms $\mathbf{Q}^{\dagger}$ in a point-wise sense, i.e., for any $f$-divergence $D_f$ and any $P \in \tilde{\mathcal{P}}$, we have $D_f(P \Vert \mathbf{Q}^{\dagger}(P)) \geq D_f(P \Vert \mathbf{Q}^{ * }(P))$. The detailed arguments can be found in the rebuttal to Reviewer 9St7.

Response to the third question on a typo

We acknowledge that the corresponding sentence might cause confusion. To clarify, the corresponding sentence can be revised as follows:

"there may be no $r_P > 0$ such that the RHS of (6) does not sum to one."

Response to the question on the motivation of protecting distribution

We thank Reviewer D3Yh for thoroughly reviewing our paper and asking an important question regarding practical motivation of protecting distribution.

Let us first introduce an equivalent definition of LDP that illustrates the operational meaning of LDP. The following equivalent definition of LDP [R1] suggests that an LDP mechanism $p_{Y|X}$ makes it difficult to infer any sensitive information $S$ about a user from $Y$, when $Y$ is provided instead of the user's data $X$.

• Theorem [R1, Thm. 14]: A conditional distribution $p_{Y|X}$ satisfies $\epsilon$-LDP if and only if

  $\displaystyle \sup_{P_X} \sup_{S:S-X-Y} \log \frac{\max_{y}\max_{s} P_{S|Y}(s|y)}{P_S(s)} \leq \epsilon$. $\cdots$ (R1)

As we can see from the above definition, LDP aims to protect any possible sensitive information hidden inside the user data $X$, and hence the variable $X$ in (R1) should represent the whole data possessed by the user that is processed to be sent to the server.

As the reviewer mentioned, many privacy studies consider the situation where each of multiple users has a single data point, and in this case, $X$ becomes such a single data point. On the other hand, in many practical scenarios, it is more natural to assume that each user possesses multiple data points, e.g., photographs and texts stored in a person's smart phone or multiple medical data hold by a hospital. Accordingly, there have been multiple studies considering the situation where each user has multiple data points. For example, [30] considers a scenario where there are $m \geq 1$ data points per user, each of which is generated in an i.i.d. manner from an underlying distribution. In this case, it is appropriate to set $X$ in (R1) to be the whole $m$-tuple of the user's data points. In our setting, the user's data is itself a distribution. Hence, the user distribution is in the place of $X$ in (R1). As mentioned in [35], this can be seen as a more general setup that includes situations where each client has multiple data points with variable number of data points, by regarding the multiple data points as the empirical distribution of the multiple data points.

One naive approach for privatizing multiple data points would be to perturb each data point of the user and send all perturbed data to the server, but it will result in significant privacy leakage due to parallel composition. Hence, developing better privacy mechanisms has gained increasing attention recently to protect the whole collection of multiple data points per user, in the context of not only LDP but also DP.

Reference:

• [R1] I. Issa, A. B. Wagner, and S. Kamath, "An Operational Approach to Information Leakage," IEEE Transactions on Information Theory, vol. 66, no. 3, pp. 1625–1657, Mar. 2020, doi: 10.1109/TIT.2019.2962804.