Exactly Minimax-Optimal Locally Differentially Private Sampling

Summary

Consider the following setting: A public domain $\mathcal{X}$, a family of distributions $\mathcal{P}$ over $\mathcal{X}$, and a mechanism $M$ which give a distribution $P \in \mathcal{P}$ releases an element $x \in \mathcal{X}$, such that $M$ is $\epsilon$-pure local DP with respect to the input, that is - the output will have similar distribution for any two distribution inputs $P, P' \in \mathcal{P}$. Can we expect the output distribution - that is, the distribution of output elements $x$ given an input distribution $P$ - to be accurate in any way, where accuracy is measured by some $f$-divergence between the distribution of outputs and the input distribution. At first, this seems like a hopeless task, since the mechanism has to maintain privacy even against distributions that share no support. Surprisingly, as this paper proves, there is some hope and things are not that bleak. This setting was first considered by [1], who proposed optimal mechanisms for finite and continuous domains, with respect to some given reference distribution, for KL-divergence. This paper removes the dependence on a given reference distribution, and instead provides an intuitive algorithm that is optimal for the finite case and does not depend on the choice of $f$. It extends these results to the continuous case, for a family of distributions that are point-wise bounded from above and below by some reference distribution up to scale. Finally, it provides numerical evaluations for the continuous case, which demonstrate the improved utility. [1] Hisham Husain, Borja Balle, Zac Cranko, and Richard Nock. Local Differential Privacy for Sampling. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, pages 3404–3413. PMLR, June 2020.

Strengths

This paper is clearly written. Its contribution lays both in its conceptual framing as well as in its theoretical results.

Weaknesses

Though many of the ideas and proofs in this work are novel, the results can be viewed as a generalization of previously known results as mentioned in the summary. Though the results achieved in this paper are optimal, they are still quite weak. This is not surprising. As discussed in the summary, the very fact that we can learn anything in this setting is already surprising, given that (in the finite domain setting) the output given two different singleton distributions must be indistinguishable. As a result, the output distribution is heavily skewed towered the uniform distribution. The main motivation for this setting is somewhat unclear. Since each user has access to a single distribution, we want to maintain privacy w.r.t. the user's distribution, and so we release a single element, the output is useful only under some assumption on the relation between the users' distributions.

Questions

See above

Rating

6

Confidence

4

Soundness

4

Presentation

4

Contribution

2

Limitations

N/A

Summary

The paper considers the problem of sampling from a user's distribution under local differential privacy (LDP). Namely, a client has a distribution P in some set of distributions, where the set is known to a data curator. The client wants to perturb P to get Q, such that a sample from Q sent to the data curator satisfies LDP with respect to P (i.e., for any P, P' the probability of sampling a certain outcome differs by at most $e^\epsilon$ multiplicatively), but also minimizes a given f-divergence between P and Q. The authors give lower bounds on the f-divergence achievable for a given LDP guarantee in two settings, one where the set of distributions is over a discrete support, and another where the set of distributions is over a continuous support, but is lower and upper bounded by some constants times a base measure. They also give an explicit perturbation in these settings that exactly matches the lower bound, i.e. is an optimal solution to the problem. They also discuss why in the continuous setting the lower/upper bound assumption is necessary to get meaningful bounds (in particular, to avoid two disjoint point distributions being in the support), show how to extend their results to a setting where clients only have samples from their distribution, and perform experiments showing that their perturbation achieves better divergence bounds than the previous work "Local Differential Privacy for Sampling".

Strengths

* The paper gives matching upper and lower bounds for a very general form (i.e. for arbitrary f-divergence, rather than a specific divergence) of a natural and important problem of generating private samples with LDP * The assumptions for the settings where the authors derive optimal results are well-justified - in the continuous setting, the authors demonstrate that their assumption (10) is somewhat necessary to derive any meaningful results, and the authors discuss how to extend to a more practical setting of clients having samples rather than distributions * Numerical results support the theoretical results and make them easier to contextualize, specifically they demonstrate significant improvements in the bounds over the past work

Weaknesses

* While the proofs of Theorems 3.1 and 3.3 in the appendix are far from trivial, given knowledge of the randomized response mechanism, it's not clear to me that the optimal bounds are as surprising as the authors suggest. See Questions for more detail. * The introduction suggests one of the major improvements of the paper over [35] is avoiding the optimality depending on the choice of reference distribution. However, it seems that once we relax reference distribution to measure as the authors do, in both settings the authors consider, there is a natural choice of reference measure to apply the approach of [35] to. It also seems like the results could be retrieved just shifting the lower and upper bounds on the probabilities that [35] uses. While the authors justify the assumptions in the continuous setting that lead to an easy choice of reference distribution, and a lot of work goes into proving optimality of the authors' suggested mechanisms, it's seems both Theorems 3.1 and 3.3 are achievable via a slight variation of the technique in [35], which suggests limited originality/significance for the algorithmic techniques in the paper.

Questions

* In the discrete setting, we could sample from P and then apply a randomized response to the sample. This seems to achieve the same f-divergence bound (7) in the extreme case where P is a point distribution. This mechanism might be worse for non-extreme distributions, but for the minimax f-divergence this might now matter. Is this mechanism also minimax optimal? If so, in the continuous case is the following mechanism minimax optimal? We sample from P, with some probability p keep the sample, otherwise sample from the distribution with pdf proportional to the base measure h. p can be chosen to be the largest value that preserves LDP.

Rating

6

Confidence

3

Soundness

4

Presentation

2

Contribution

3

Limitations

Yes

Summary

This paper addresses the problem of sampling under local differential privacy (LDP) requirements, focusing on the privacy-utility trade-off (PUT). It defines the fundamental PUT of private sampling in the minimax sense, using f-divergence as the utility measure. The authors characterize the exact PUT for both finite and continuous data spaces and propose sampling mechanisms that are universally optimal for all f-divergences. The numerical experiments demonstrate the superiority of these mechanisms over existing baselines, showcasing their empirical utilities.

Strengths

1. The paper presents a novel approach to analyzing the privacy-utility trade-off (PUT) in locally differentially private (LDP) sampling, utilizing f-divergence as the utility measure. 2. The authors offer optimal mechanisms for both finite and continuous data spaces, given certain assumptions. Figure 2 provides a clear visualization that enhances understanding of the proposed mechanisms.

Weaknesses

The constant $r_P$ does not have a closed form, requiring calculation through approximate methods. This introduces potential approximation errors that could degrade the privacy or utility guarantees. See question 1.

Questions

1. In practice, would the approximation error of calculating $r_P$ degrade the $\epsilon$-LDP guarantee to $(\epsilon,\delta)$-LDP with $\delta>0$? 2. Is the mechanism $Q^*_{k,\epsilon}$ uniquely optimal? 3. Is there a typo on line 127: there may be no $r_P>0$ such that (6) **does not** sum to one?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

NA

Summary

This paper considers the issue of protecting probability distributions with local differential privacy when they are sampled. This problem has been recently studied in view of potential applications to generative models. In particular, the paper studies mechanisms that, given a distribution, produce a "sampler", i.e., a sampling mechanism that can be seen as an obfuscated version of the original distribution and which is used to produce samples in replacement of the original distribution. The paper investigates the privacy-utility trade-off of the proposed method, where utility is measured in terms of f-divergence between the original distribution and the sampling distribution.

Strengths

+ The proposed method is shown to be *universally optimal*, i.e., the produced sampling mechanism minimizes any f-divergence wrt the original distribution + For finite data spaces, the paper presents a closed-form expression for the utility of both the proposed mechanism and the baseline method proposed in [35], allowing for an exact comparison of the utilities.

Weaknesses

- The paper should justify better, in the introduction, why inferring a distribution presents a privacy risk. In general, in the DP literature, we want to protect an individual data point, not the distribution that can be inferred from the data collection.

Questions

Can you please explain why knowing a distribution presents a privacy risk? In general, the problem in privacy consists in protecting the individual data point, while allowing statistics to be derived, including the inference of the distribution from which the data points are drawn.

Rating

7

Confidence

4

Soundness

4

Presentation

3

Contribution

4

Limitations

The limitations are discussed. In particular, the paper points out that there are other notions of utility (distances between distributions) that could be considered.