Reveal-or-Obscure: A Differentially Private Sampling Algorithm for Discrete Distributions

1. Problem Statement

The paper addresses the challenge of Differentially Private (DP) sampling from an unknown discrete distribution $P$ over a finite alphabet $[k] = \{1, \dots, k\}$.

• Goal: Given a dataset $X^n$ of $n$ i.i.d. samples drawn from $P$, generate a single representative sample $Y$ such that the output distribution $Q$ is close to $P$ (measured by Total Variation distance), while satisfying $\epsilon$-differential privacy.
• Context: Unlike full distribution learning, which requires significant data, the goal here is to release a single sample. This is a foundational step for generating synthetic datasets.
• Challenge: Existing methods (e.g., Raskhodnikova et al. [5]) typically add explicit noise (like Laplace noise) to the empirical counts and project them back to a probability simplex. These methods often suffer from high sample complexity, especially as the privacy budget $\epsilon$ increases.

2. Methodology

The authors propose two algorithms: ROO (Reveal-or-Obscure) and DS-ROO (Data-Specific ROO).

A. Reveal-or-Obscure (ROO)

ROO achieves privacy not by perturbing the data directly, but by randomly deciding whether to "reveal" the empirical distribution or "obscure" it with a uniform distribution.

• Mechanism:
  1. With probability $q$, the algorithm ignores the dataset and samples $y$ uniformly from the alphabet $[k]$ (Obscure).
  2. With probability $1-q$, the algorithm selects a sample $y$ uniformly at random from the input dataset $X^n$ (Reveal).
• Privacy Logic: The randomness of choosing between the true data and a uniform distribution creates uncertainty for an adversary regarding whether a specific individual's data influenced the output.
• Theoretical Bounds:
  • The algorithm satisfies $\epsilon$-DP if $q$ is chosen such that:
    $$\epsilon = \log\left(1 + \frac{k(1-q)}{nq}\right)$$
  • The accuracy (Total Variation distance $\alpha$) is bounded by:
    $$\alpha = q\left(1 - \frac{1}{k}\right)$$
  • Sampling Complexity: Solving for $n$ yields:
    $$n = \frac{k(1-\alpha) - 1}{\alpha(e^\epsilon - 1)}$$
  • Key Insight: The complexity scales with $1/(e^\epsilon - 1)$. For larger $\epsilon$ (lower privacy), the required sample size $n$ decreases exponentially, offering a significant improvement over previous bounds that scale linearly with $1/\epsilon$.

B. Data-Specific ROO (DS-ROO)

The vanilla ROO uses a fixed $q$ based on the worst-case scenario (where an alphabet element is missing from the dataset). DS-ROO adapts $q$ based on the specific dataset's properties to improve utility.

• Adaptive Parameter: Let $m$ be the minimum count of any symbol in the alphabet within the dataset ($m = n \cdot \min_x \hat{P}(x)$).
• Mechanism:
  • If $m=0$ (worst case), DS-ROO behaves exactly like ROO.
  • If $m > 0$, the algorithm computes a specific probability $q_m$ that is strictly lower than the fixed $q$ used in ROO.
  • The algorithm calculates $q_m$ recursively using derived inequalities (Equations 10–13 in the paper) to ensure $\epsilon$-DP is maintained for all neighboring datasets.
• Intuition: If the dataset is "rich" (all symbols appear frequently, i.e., high $m$), the empirical distribution is robust. The algorithm can afford to obscure the data less (lower $q_m$), thereby preserving more utility (accuracy) while maintaining the same privacy guarantee.

3. Key Contributions

1. Novel ROO Algorithm: Introduced a sampling mechanism that achieves DP without explicit noise addition to counts. Instead, it relies on a probabilistic mixture of the empirical distribution and a uniform distribution.
2. Improved Complexity Bounds: Proved that ROO achieves a strictly better sampling complexity bound than the state-of-the-art algorithms (specifically [5] and [1]).
   • Previous bounds: $O(k / (\alpha \epsilon))$.
   • ROO bound: $O(k / (\alpha (e^\epsilon - 1)))$.
   • This represents an exponential improvement in sample efficiency for moderate-to-high $\epsilon$.
3. DS-ROO Generalization: Proposed a data-adaptive version that lowers the obscuring probability ($q$) when the dataset is dense (high minimum count $m$).
   • Proved that DS-ROO satisfies $\epsilon$-DP.
   • Demonstrated empirically that DS-ROO achieves significantly lower Total Variation distance (better accuracy) than both vanilla ROO and the state-of-the-art method for the same privacy budget.
4. Theoretical Proofs: Provided rigorous proofs for privacy guarantees and derived the recursive conditions for the adaptive probability $q_m$.

4. Results and Empirical Evidence

• Sampling Complexity: Theoretical analysis confirms that for $\epsilon > 0$, the sample complexity of ROO is strictly lower than that of Raskhodnikova et al. [5] and the SubRR algorithm [1].
• Accuracy Comparison (Fig. 3):
  • Experiments were conducted with $k=9$ and $n=1000$.
  • DS-ROO vs. ROO: DS-ROO consistently achieved a lower $\alpha$ (higher accuracy) across various $\epsilon$ values.
  • DS-ROO vs. State-of-the-Art: DS-ROO outperformed the algorithm from [5] by a significant margin.
• Behavior of $q_m$:
  • As the minimum count $m$ increases, the required obscuring probability $q_m$ decreases.
  • In high-privacy regimes (low $\epsilon$), $q_m$ decreases slowly.
  • In low-privacy regimes (high $\epsilon$), $q_m$ drops rapidly toward zero, meaning the algorithm relies almost entirely on the true data when privacy constraints are loose and data is abundant.

5. Significance

• Efficiency: The work demonstrates that privacy can be achieved more efficiently by "obscuring" the source of the sample rather than "perturbing" the data values. This shifts the paradigm from noise injection to probabilistic selection.
• Practicality: The DS-ROO algorithm offers a practical way to improve the utility of synthetic data generation without increasing the privacy cost. It is particularly effective for datasets where the underlying distribution is not extremely sparse.
• Foundational Step: By solving the single-sample problem with improved bounds, this work lays the groundwork for generating larger, high-quality synthetic datasets for sensitive domains like healthcare and finance, where data scarcity and privacy are critical constraints.

In summary, the paper presents a theoretically sound and empirically superior approach to differentially private sampling, leveraging a "reveal-or-obscure" strategy to minimize the data requirements for achieving a given level of privacy and accuracy.