Dobrushin Coefficients of Private Mechanisms Beyond Local Differential Privacy

Technical Summary: Dobrushin Coefficients of Private Mechanisms Beyond Local Differential Privacy

Problem Statement
The paper addresses limitations in using Local Differential Privacy (LDP) as the sole metric for quantifying privacy in discrete Markov kernels (privacy mechanisms). While LDP is widely adopted, the authors note two primary issues:

1. Over-restrictiveness: In statistical applications like parameter estimation, achieving stringent LDP guarantees (small $\epsilon$) can lead to extreme degradation in estimation performance (high minimax risk).
2. Counter-intuitive behavior with zero probabilities: The standard LDP definition yields an infinite privacy cost if a mechanism assigns zero probability to any output for a given input ($K_{Y|X=x}(y) = 0$). This treats mechanisms with significant randomization (e.g., $K_1$ in the paper's example) identically to identity mappings or trivial mechanisms (e.g., $K_2$) if they both contain zero entries, failing to distinguish between "noisy" and "deterministic" behaviors in terms of privacy leakage.

To address these issues, the authors investigate Dobrushin coefficients (contraction coefficients of the Total Variation distance) for mechanisms that satisfy Pointwise Maximal Leakage (PML) rather than strict LDP. PML is a pointwise adaptation of maximal leakage that depends on the data distribution $P_X$. The authors specifically analyze mechanisms where the input distribution $P_X$ has a minimum probability mass bounded away from zero by a constant $c > 0$ (i.e., $\min_x P_X(x) \geq c$). This framework allows for the analysis of mechanisms with zero-probability assignments that would otherwise be deemed "infinitely private" (or infinitely leaking) under LDP.

Methodology
The paper employs information-theoretic tools to derive bounds on the contraction of $f$-divergences through privacy mechanisms.

• Definitions: The authors define $(\epsilon, c)$-PML as a constraint where the PML is bounded by $\epsilon$ for all input distributions in the set $Q_X(c) = \{P_X : \min_x P_X(x) \geq c\}$. This generalizes LDP, as LDP corresponds to the limit $c \to 0$.
• Contraction Coefficients: The core object of study is the Dobrushin coefficient $\eta_{TV}(\epsilon, c)$, defined as the supremum of the contraction of the Total Variation (TV) distance over all kernels satisfying $(\epsilon, c)$-PML.
• Reduction to Binary Outputs: The authors prove that to find the maximal Dobrushin coefficient, it is sufficient to consider mechanisms with binary output spaces ($|Y|=2$). This simplifies the optimization problem significantly.
• Inequalities: The derivation utilizes Binette's inequality (a generalization of the reverse Pinsker inequality) to extend the TV bounds to general $f$-divergences (such as Relative Entropy and Hellinger divergence).

Key Contributions and Results

1. Achievable Bounds on Dobrushin Coefficients:
   The paper derives a tight upper bound on the Dobrushin coefficient $\eta_{TV}(\epsilon, c)$ for any kernel satisfying $(\epsilon, c)$-PML. The bound is given by:
   $$\eta_{TV}(\epsilon, c) \leq \min\left( \frac{e^\epsilon - 1}{e^\epsilon(1 - Nc) + 1}, 1 \right)$$
   where $N$ is the size of the input alphabet.

   • Regime Analysis: The authors show that if $\epsilon \geq \log(2/Nc)$, the contraction coefficient is 1 (no contraction occurs). If $\epsilon < \log(2/Nc)$, the coefficient is strictly less than 1, indicating privacy-induced contraction.
   • Recovery of LDP: As $c \to 0$, the bound recovers the known result for $\epsilon$-LDP: $\eta_{TV} \leq \frac{e^\epsilon - 1}{e^\epsilon + 1}$.
   • Mechanism Construction: The paper provides explicit constructions of mechanisms (specifically binary-output mechanisms) that achieve these bounds, demonstrating that the bounds are achievable.

2. Extension to General $f$-Divergences:
   Using Binette's inequality, the authors extend the TV bounds to general $f$-divergences. They derive strong data processing inequalities (SDPIs) for Relative Entropy and Hellinger divergence under $(\epsilon, c)$-PML constraints. These bounds depend on the TV contraction factor and the extremal ratios of the output distributions.

3. Application to Minimax Risk:
   The derived bounds are applied to private minimax estimation risk. Using Le Cam's two-point method and the tensorization property of $f$-divergences, the authors show that the sample complexity required to achieve a certain risk level increases by a factor proportional to the inverse of the private Dobrushin coefficient. Specifically, if the coefficient is 1, the sample complexity matches the non-private setting; if it is less than 1, the effective sample size is reduced.

Significance and Claims
The paper claims to provide a more nuanced framework for analyzing privacy mechanisms than LDP alone. By introducing the parameter $c$, the authors can quantify privacy leakage for mechanisms that contain zero-probability entries, which are excluded or treated pathologically under standard LDP.

• Tighter Bounds: For mechanisms satisfying LDP, the proposed bounds are tighter or more adaptable than previous results when the input distribution is known to have a minimum mass $c$.
• Beyond LDP: The framework extends the analysis of contraction coefficients to the entire class of discrete kernels, including those that do not satisfy any finite LDP guarantee.
• Operational Interpretation: The results link the theoretical contraction coefficients directly to the degradation of statistical estimation performance, offering a tool to quantify the "cost" of privacy in terms of increased risk or sample complexity.

The authors emphasize that their work recovers existing LDP results as a special case while offering a continuous interpolation between uniform distribution constraints and the full LDP regime, thereby addressing the "over-restrictive" nature of LDP in specific statistical contexts.