Preserving Target Distributions With Differentially Private Count Mechanisms

1. Problem Statement

Data holders (e.g., census bureaus, public health departments) often need to publish tables of counts (e.g., number of cases per state) while preserving individual privacy via Differential Privacy (DP). Standard DP mechanisms (like Laplace or Geometric noise) add independent noise to each count to protect individual entries.

However, this approach creates a significant statistical bias when researchers ask count distribution questions. These are questions that do not rely on specific category names but rather on the shape of the count distribution (e.g., "What fraction of counties have zero homicides?" or "What is the average number of students per counselor?").

• The Issue: Standard mechanisms distort the distribution of counts. For instance, the Geometric mechanism tends to inflate the number of zero counts.
• The Conflict: Existing methods prioritize Accuracy of Counts (minimizing error for specific categories) but sacrifice Accuracy of Distribution. Splitting the privacy budget to publish a separate privatized distribution and a privatized count table leads to inconsistency between the two products.
• The Goal: Develop a unified mechanism that publishes a table of privatized counts which simultaneously satisfies:
  1. Accuracy of Distribution: The output distribution matches the true input distribution in expectation.
  2. Accuracy of Counts: Minimizes error for specific category queries.
  3. Runtime: Must be computationally efficient for large datasets.

2. Methodology: A Two-Stage Framework

The authors propose a two-stage framework to achieve these goals, dividing the total privacy budget $\epsilon_t$ into $\epsilon_1$ (for distribution) and $\epsilon_2$ (for counts).

Stage 1: Distribution Privatization

The data holder first computes the true distribution of counts $\zeta$ (the proportion of categories having count $i$). They then privatize this distribution to create a target distribution $z$.

• Novel Mechanism: The authors introduce the Cyclic Laplace Mechanism.
  • Unlike standard Laplace noise added independently to bins, this mechanism adds correlated noise: $V_i = \zeta_i + L_i - L_{i+1}$, where $L_i$ are independent Laplace variables and $L_n = L_0$.
  • Benefit: This "cyclic" structure ensures that the cumulative sum of the distribution remains stable, significantly reducing the variance of cumulative errors compared to standard Laplace mechanisms. It is proven to satisfy $\epsilon$-DP.

Stage 2: Constructor Algorithm

The goal is to construct a transition matrix $T$ (an $n \times n$ matrix where $T_{i,j}$ is the probability of outputting $j$ given input $i$) such that:

1. $T$ satisfies $\epsilon_2$-DP.
2. $T$ has a fixed point at $z$ (i.e., $zT = z$). This ensures that if the input data follows distribution $z$, the output data will also follow $z$ in expectation.

To solve this, the authors develop a mathematical theory based on $\epsilon$-scales:

• $\epsilon$-scales: These are probability vectors where the DP constraint binds for every adjacent pair of entries (either $s_i = e^\epsilon s_{i+1}$ or $s_i = e^{-\epsilon} s_{i+1}$).
• Polytope Representation: The set of valid fixed-point mechanisms forms a convex polytope $F$. The authors prove that any mechanism in $F$ can be represented as a conic combination of $\epsilon$-scales.
• Representation Polytope ($R_F$): They map the high-dimensional space of transition matrices to a lower-dimensional representation space using a scale matrix $\Psi$. This allows them to characterize the extreme points of the feasible set.
• Algorithms:
  • Optimal Constructor (Small $n$): Uses standard linear programming (Simplex/Interior Point) to minimize count error (e.g., Mean Squared Error) within the fixed-point polytope $F$.
  • Heuristic Constructor (Large $n$): An $O(n^2)$ greedy algorithm (Algorithm 1) that builds the transition matrix by iteratively adding "single-peaked" $\epsilon$-scales. It selects columns to fill based on a selector function $\kappa$ (e.g., "Sandwich," "Max Probability") to ensure the fixed-point constraint is met efficiently.

3. Key Contributions

1. Cyclic Laplace Mechanism: A new distribution privatizer specifically designed for count distributions that outperforms general-purpose histogram mechanisms (like Hierarchical or Wavelet-based methods) in preserving distributional accuracy.
2. Mathematical Theory of Fixed-Point Mechanisms:
   • Defined the concept of $\epsilon$-scales as fundamental building blocks for DP count mechanisms.
   • Characterized the extreme points of the fixed-point polytope $F$ using a representation polytope $R_F$.
   • Proved that extreme points of $F$ can be represented by a relatively small number of $\epsilon$-scales, enabling efficient algorithmic construction.
3. Efficient Constructor Algorithms:
   • Developed a heuristic constructor (Algorithm 1) that runs in $O(n^2)$ time, making it practical for large $n$ where standard linear programming fails.
   • Developed a "Two-Stage Unfixed Optimum" constructor (Algorithm 2) for baseline comparison, which finds the optimal mechanism without the fixed-point constraint.
4. Empirical Validation: Comprehensive experiments demonstrating the trade-offs between the three performance criteria.

4. Experimental Results

The authors tested their framework on three datasets: synthetic Binomial data, US County homicide counts (highly skewed), and US School teacher counts.

• Accuracy of Distribution:
  • Fixed-point methods significantly outperform all unfixed baselines.
  • Example: On the Binomial dataset with $\epsilon_t = 0.48$, switching from the best unfixed baseline to a fixed-point method reduced Wasserstein distance by 94% (from 0.64 to 0.04).
• Accuracy of Counts:
  • Enforcing a fixed-point constraint does degrade count accuracy slightly compared to unfixed baselines (which have a larger feasible space).
  • However, the degradation is moderate (often a few percentage points). For example, on crime data, count error increased by only 5.7% while distribution error dropped by 74%.
• Runtime:
  • Standard linear programming solvers (Simplex/Interior Point) become impractical for large $n$.
  • The proposed heuristic constructor achieves runtimes comparable to the fastest unfixed baselines (e.g., Truncated Geometric), handling $n=2000$ in under 10 seconds.
• Budget Allocation:
  • The authors provide a "rule of thumb" for splitting the privacy budget ($f = \epsilon_1 / \epsilon_t$) based on the total budget, showing that as $\epsilon_t$ decreases, a larger fraction should be allocated to the distribution privatizer.

5. Significance

This paper addresses a critical gap in differential privacy: the preservation of global statistical properties (distributions) alongside local properties (individual counts).

• Practical Impact: It enables organizations to release data products that are consistent and useful for policy-making questions (e.g., "What percentage of schools are understaffed?") without requiring separate, inconsistent data releases.
• Theoretical Advancement: The introduction of $\epsilon$-scales and the geometric characterization of fixed-point mechanisms provide a new algebraic framework for designing DP mechanisms, moving beyond simple noise addition to structured matrix construction.
• Trade-off Management: The study demonstrates that it is possible to achieve high distributional accuracy with only a marginal cost to count accuracy and runtime, making the approach highly viable for real-world deployment.