Locally Optimal Private Sampling: Beyond the Global Minimax

AI summary

Overview

• Research area: Privacy-preserving machine learning, specifically locally private sampling under local differential privacy (LDP) and functional LDP (FLDP).
• Technical level: Advanced. The paper is heavy on minimax theory, f-divergences, trade-off functions, and convex conjugates.
• Scope: The paper characterizes the local minimax risk of private sampling in a neighborhood around a fixed reference distribution (P_0), shows it is governed by the corresponding global minimax risk on a restricted class, and derives closed-form locally optimal samplers that outperform prior global samplers.

What This Paper Is About

When a client holds a dataset modeled as an empirical distribution (P), the goal of locally private sampling is to release a single sample from a distribution close to (P) in (f)-divergence while satisfying LDP. Prior work by Park et al. (NeurIPS'24) solved this in a global minimax sense by taking the worst case over an entire class of distributions, which is pessimistic. This paper takes a local view: it measures the worst-case risk only over distributions (P) that lie in a neighborhood (N_\gamma(P_0)) around a fixed reference distribution (P_0), which can represent public data available to the client.

Key Contributions

1. Global minimax risk under functional LDP. The authors characterize the exact global minimax risk of private sampling under the general functional LDP framework and derive optimal samplers for both continuous and discrete domains. This generalizes the pure-LDP framework of Park et al. to approximate LDP and Gaussian LDP (GLDP), and the optimal samplers are independent of the choice of (f)-divergence.

2. Local minimax formulation. They introduce a local minimax problem that minimizes (f)-divergence over all (P \in N_\gamma(P_0)) for a given (P_0) and (\gamma \geq 1), defined via the (E_\gamma)-divergence (hockey-stick divergence). They prove this local minimax risk is fully determined by the global minimax risk when the distribution class is restricted to the neighborhood around (P_0).

3. Closed-form locally optimal samplers. Building on the global results, they derive closed-form expressions for local minimax-optimal functional samplers (Theorem 4.1) and a pointwise-optimal private sampler under pure LDP (Theorem 5.1) that achieves the local minimax risk, enabling direct comparison with the global samplers of Park et al.

4. Empirical validation. They numerically show their local minimax samplers consistently—often substantially—outperform the global samplers of Park et al. across privacy regimes, under both pure LDP ((\varepsilon=1)) and (\nu)-GLDP ((\nu=1.5)). Experiment code is publicly available.

Main Findings

• Local risk equals restricted global risk. The local minimax risk over (N_\gamma(P_0)) is exactly the global minimax risk when the distribution class is restricted to that neighborhood. The global solution of Theorem 3.4 directly yields the local solution of Theorem 4.1.

• The optimal global sampler is a mixture. Under functional LDP, the minimax-optimal sampler has density (q^_g(P)(x) = \lambda^ p(x) + (1-\lambda^) h(x)): it samples from (P) with probability (\lambda^) and from a reference distribution (h) with probability (1-\lambda^). A larger (\lambda^) gives outputs closer to (P); sampling from (h) supplies the randomness needed for privacy.

• Discrete case uses the uniform distribution. When (\mathcal{X}=[k]) and (\tilde{\mathcal{P}}=\mathcal{P}([k])), the optimal sampler is (\mathbf{Q}^_{k,g}(P) = \lambda^{k,g} P + (1-\lambda^*{k,g}) \mu_k), a mixture of (P) and the uniform distribution (\mu_k) on ([k]).

• Pure LDP closed form. For pure LDP, (\lambda^*{c_1,c_2,g\varepsilon} = \frac{e^\varepsilon - 1}{(1-c_1)e^\varepsilon + c_2 - 1}). This reproduces the minimax risk previously derived by Park et al. (Theorem 3.3 in their work), confirming the framework generalizes the earlier result.

• Instantiation of the local sampler. Setting (c_1 = 1/\gamma), (c_2 = \gamma), and (h = p_0) in the global sampler gives the locally minimax-optimal functional LDP sampler.

• A pointwise-better pure-LDP sampler. Under pure LDP, the authors construct a different sampler using clipping: (q(x) = \mathrm{clip}!\left(\frac{1}{r_P}p(x);\ \frac{\gamma+1}{\gamma+e^\varepsilon}p_0(x),\ \frac{(\gamma+1)e^\varepsilon}{\gamma+e^\varepsilon}p_0(x)\right)), where (r_P) is a normalizing constant. This sampler is pointwise better than the one obtained by simply instantiating the functional LDP result with (g = g_\varepsilon).

• Empirical gains. Local minimax samplers yield distributions significantly closer to the original than global minimax samplers, under both pure LDP and GLDP. Unlike the public-data setting of Zamanlooy et al., where access to public data does not necessarily reduce the minimax risk, here it does.

• Comparison to prior sampler families. Park et al. identified a linear sampler (from randomized response) and a non-linear sampler (from clipping) and showed the non-linear one is pointwise better. This paper develops two analogous families of locally minimax-optimal pure-LDP samplers and likewise shows one is pointwise better than the other.

Methodology in Plain English

The researchers set up a minimax problem: they look for a privacy-preserving sampling algorithm that minimizes the worst-case (f)-divergence between the true distribution and the released distribution. In the global version, the worst case is taken over an entire class of distributions, which is often a degenerate (worst-case) distribution. In the local version, the worst case is taken only over distributions close to a fixed reference (P_0), where "close" is measured by the (E_\gamma)-divergence being zero—meaning the likelihood ratio between any (P) in the neighborhood and (P_0) stays within ([1/\gamma, \gamma]), which also implies a bound on total variation distance of (1 - 1/\gamma).

They first solve the global problem in the more general functional LDP framework, which covers pure LDP, approximate LDP, and GLDP through a trade-off function (g). The optimal samplers turn out to be simple mixtures of the input distribution and a reference distribution, with the mixing weight (\lambda^) found by minimizing an explicit expression involving the convex conjugate (g^) of the trade-off function. They then show that the local problem is just the global problem with the input class shrunk to the neighborhood (N_\gamma(P_0)), so the local solution follows directly. Finally, recognizing that the local sampler inherited from the functional LDP result is not pointwise optimal, they construct a sharper sampler under pure LDP by clipping the density ratio to lie between the bounds (\frac{\gamma+1}{\gamma+e^\varepsilon}p_0(x)) and (\frac{(\gamma+1)e^\varepsilon}{\gamma+e^\varepsilon}p_0(x)), and normalizing.

Why This Matters

Impact on research. The paper moves private sampling theory beyond the pessimistic worst-case (global minimax) formulation toward a local analysis that better reflects realistic data distributions. By generalizing from pure LDP to functional LDP—covering approximate and Gaussian LDP—it unifies and extends the state of the art. The finding that the local minimax risk is exactly the restricted global minimax risk gives a clean theoretical bridge between the two views, and the closed-form samplers are independent of the choice of (f)-divergence, making them broadly applicable.

Real-world applications (as motivated by the paper):

• Personalized collaborative learning, where individual models are trained collaboratively and public data may reflect privatized information shared by other users.
• Private sampling with public data, where a client's public dataset (represented by (P_0)) improves the privacy-utility trade-off.
• Private generative modeling, producing realistic synthetic data under strong privacy guarantees.
• Fine-tuning of large language models with privacy-preserving sampling.

Industry relevance. LDP is already deployed by Google, Apple, and Microsoft for on-device data randomization. Some prior work has also studied private sampling in the context of fine-tuning large language models. Because the samplers are closed-form and require only a mixture or a clipping operation, they are straightforward to implement within existing LDP pipelines.

Future Directions

• Extending the neighborhood. The paper notes that the zero-(E_\gamma) neighborhood can be generalized by relaxing (E_\gamma(P|P_0) = 0) to (E_\gamma(P|P_0) \leq \zeta), and further to any (f)-divergence with a twice-differentiable (f). Developing optimal samplers for these relaxed neighborhoods is a natural next step.

• Continuous vs. discrete generality. The authors state all subsequent results after Theorem 3.6 can be extended to general sample spaces, but present them in the continuous setting for clarity. A full treatment of general spaces and the required decomposability conditions remains open to formalize.

• Practical deployment studies. The experiments compare against global samplers under fixed settings ((\varepsilon = 1) pure LDP; (\nu = 1.5) GLDP). Testing the local framework on larger-scale and real-world datasets, and across wider privacy regimes, would clarify practical benefits.

• Choosing and learning (P_0). Since the local framework hinges on a reference distribution (P_0), understanding how (P_0) is selected or estimated in practice—and how sensitive the results are to that choice—is an open question for applied settings.

Target Audience

Researchers and practitioners working on differential privacy, particularly those interested in private data generation, locally private sampling, and minimax theory for distribution estimation. The mathematical level is advanced, so readers should be comfortable with (f)-divergences, trade-off functions, convex conjugates, and minimax analysis. Privacy engineers and applied scientists implementing LDP mechanisms may also benefit from the closed-form samplers and the public-data interpretation.

Authors’ abstract

We study the problem of sampling from a distribution under local differential privacy (LDP). Given a private distribution $P \in \mathcal{P}$, the goal is to generate a single sample from a distribution that remains close to $P$ in $f$-divergence while satisfying the constraints of LDP. This task captures the fundamental challenge of producing realistic-looking data under strong privacy guarantees. While prior work by Park et al. (NeurIPS'24) focuses on global minimax-optimality across a class of distributions, we take a local perspective. Specifically, we examine the minimax risk in a neighborhood around a fixed distribution $P_0$, and characterize its exact value, which depends on both $P_0$ and the privacy level. Our main result shows that the local minimax risk is determined by the global minimax risk when the distribution class $\mathcal{P}$ is restricted to a neighborhood around $P_0$. To establish this, we (1) extend previous work from pure LDP to the more general functional LDP framework, and (2) prove that the globally optimal functional LDP sampler yields the optimal local sampler when constrained to distributions near $P_0$. Building on this, we also derive a simple closed-form expression for the locally minimax-optimal samplers which does not depend on the choice of $f$-divergence. We further argue that this local framework naturally models private sampling with public data, where the public data distribution is represented by $P_0$. In this setting, we empirically compare our locally optimal sampler to existing global methods, and demonstrate that it consistently outperforms global minimax samplers.