Technical Summary: Differential Privacy for Symmetric Log-Concave Mechanisms

Problem Statement

The paper addresses the challenge of minimizing the noise added to database query results to achieve $(\epsilon, \delta)$-differential privacy while maintaining high utility (low error). While the Laplace and Gaussian mechanisms are standard tools for adding symmetric noise, existing literature has largely focused on finding the minimal scale parameter for these fixed distributions. A critical gap exists in the lack of necessary and sufficient conditions for $(\epsilon, \delta)$-differential privacy for general symmetric log-concave noise distributions, particularly in multidimensional settings. Furthermore, there is a need to determine if optimizing the choice of the noise distribution itself (beyond just its scale) can yield significantly lower mean squared errors (MSE) compared to fixed mechanisms like Laplace or Gaussian.

Methodology

The authors extend the theoretical framework for differential privacy by deriving conditions for mechanisms that add noise distributed according to symmetric log-concave densities.

1. Theoretical Derivation (1D Case):

   • The paper establishes a necessary and sufficient condition for $(\epsilon, \delta)$-differential privacy for mechanisms returning $q(d) + sX$, where $X$ follows a symmetric log-concave density $f(x) = e^{-\psi(x)}$ (with $\psi$ even and convex).
   • This condition (Lemma 1) is formulated in terms of the cumulative distribution function (CDF) $F$, the global sensitivity $\Delta$, the scale $s$, and a threshold $t$ derived from the likelihood ratio bound.
   • The authors analyze the properties of these mechanisms, distinguishing between MLR-bounded mechanisms (where the likelihood ratio is bounded, e.g., Laplace, Logistic) and MLR-unbounded mechanisms (where the ratio grows unbounded, e.g., Gaussian).

2. Extension to Multidimensional Case:

   • The 1D condition is generalized to $\mathbb{R}^n$ for mechanisms adding noise vectors distributed according to $\|\cdot\|$-spherically symmetric log-concave densities.
   • A key result (Lemma 8) shows that if the global sensitivity is defined using the same norm $\|\cdot\|$ that defines the spherical symmetry of the noise, the privacy condition reduces to the 1D case.
   • The authors specialize this to Subbotin distributions (also known as generalized normal or exponential power distributions). They prove that a vector of independent Subbotin$_p$ random variables, when paired with the $p$-norm for sensitivity definition, satisfies the multidimensional condition (Theorem 9).

3. Optimization Strategy:

   • Instead of fixing the distribution family (e.g., always using Gaussian), the authors propose optimizing the parameter $p$ of the Subbotin$_p$ family based on the dimensionality of the query result.
   • They numerically optimize the scale $s$ and the shape parameter $p$ to minimize the $l_2$-error (MSE) for a given $(\epsilon, \delta)$ and query dimension.

Key Contributions

1. Necessary and Sufficient Conditions

The paper provides the first necessary and sufficient conditions for $(\epsilon, \delta)$-differential privacy for the entire class of symmetric log-concave mechanisms (Lemma 1). This generalizes previous results which were limited to the Gaussian distribution (Balle and Wang, 2018).

2. Closed-Form Bounds for Specific Mechanisms

Using the general condition, the authors derive closed-form necessary and sufficient bounds for the scale $s$ for:

• Laplace Mechanism: $s \ge \frac{\Delta}{\epsilon - 2\log(1-\delta)}$ (Theorem 3).
• Logistic Mechanism: A new closed-form bound involving $\epsilon$ and $\delta$ (Theorem 4).
• Gaussian Mechanism: The paper confirms the existing condition (Theorem 5) as a special case of their general framework.

3. Utility Separation Theorem

The authors prove that for mechanisms supported on $\mathbb{R}$ that are MLR-unbounded (like the Gaussian), the required scale $s$ approaches infinity as $\delta \to 0$ for any fixed $\epsilon$ (Theorem 6). Conversely, MLR-bounded mechanisms (like Laplace and Logistic) can achieve $(\epsilon, 0)$-differential privacy with finite scale. This implies that for small $\delta$, MLR-bounded mechanisms can achieve arbitrarily smaller variances than MLR-unbounded ones for the same $\epsilon$.

4. Multidimensional Optimization via Subbotin Mechanisms

The paper demonstrates that the optimal noise distribution depends on the dimensionality of the query. By treating the Subbotin parameter $p$ as an optimization variable alongside the scale $s$, the authors show that:

• The optimal $p$ varies with the number of columns (dimensions) in the data table.
• Optimizing $p$ yields significantly lower $l_2$-errors compared to using fixed Laplace ($p=1$) or Gaussian ($p=2$) mechanisms, especially as dimensionality increases.

Results

• Variance Comparisons: Empirical analysis shows that for a significant range of privacy parameters (e.g., $\epsilon \ge 0.05, \delta \le 0.001$), the Laplace and Logistic mechanisms exhibit smaller variance than the Gaussian mechanism.
• Multidimensional Experiments: In experiments estimating the mean of a high-dimensional vector (with dimensions $m \in \{10, \dots, 2000\}$), the authors numerically optimized the Subbotin parameter $p$.
  • For $\epsilon = 1$, the optimal $p$ values ranged from 2 to 7.5 as dimension increased.
  • For $\epsilon = 0.01$, the optimal $p$ values ranged from 3.5 to 13.
  • The resulting Subbotin$_p$ mechanisms consistently produced smaller $l_2$-errors than the standard Gaussian mechanism and its denoised versions (James-Stein and soft-thresholding).
• Scale Behavior: The optimal scale for log-concave mechanisms is shown to be linear in the global sensitivity $\Delta$ (Lemma 2).

Significance and Claims

The paper claims to provide a fine-grained tailoring of noise distributions to the dimensionality of query results. By moving beyond fixed mechanisms (Laplace/Gaussian) to a family of Subbotin mechanisms, the authors demonstrate that one can simultaneously select the optimal noise distribution and its scale to minimize error.

The authors note that while high-dimensional random vectors often concentrate on a sphere (suggesting Gaussian-like behavior), the choice of norm and distribution type still critically impacts the privacy-utility trade-off. The work is presented as a method to implement general optimization under $(\epsilon, \delta)$-differential privacy, complementing other relaxations like Concentrated Differential Privacy.

Correction Note: The paper includes a prominent update stating that Lemma 8 and Theorem 9 are invalid. Consequently, the results in Section 4 (The Multidimensional Case) and the corresponding conclusions regarding the optimization of Subbotin mechanisms in high dimensions are invalidated. The theoretical contributions regarding the one-dimensional case (Sections 1–3) and the specific bounds for Laplace, Logistic, and Gaussian mechanisms remain as presented, but the claims regarding the multidimensional optimization of Subbotin$_p$ mechanisms are retracted.