Better Privacy Guarantees for Larger Groups

Technical Summary: Better Privacy Guarantees for Larger Groups

Problem Statement
This paper addresses an open problem posed by Pujol and Desfontaines [2023] regarding the design of private histograms for fixed, disjoint groups. Standard differential privacy mechanisms typically add noise of a fixed magnitude to every count, providing uniform absolute privacy but resulting in significantly smaller relative errors for large groups compared to small ones. The core question is whether one can "spend" this surplus accuracy differently: allowing the error in a group to scale proportionally with its count ($x_i$) to provide stronger privacy guarantees (a smaller privacy budget) for members of larger groups.

The paper investigates this under the add-or-remove-one adjacency model. The goal is to find a mechanism where the privacy budget $v(n)$ depends only on the group count $n$, is non-increasing, and satisfies count-dependent group-wise zero-concentrated differential privacy (zCDP). This requires bounding the Rényi divergence in both directions for every order $\alpha > 1$ between neighboring datasets.

A critical technical hurdle identified is the boundary condition at zero. The original formulation required the expected absolute error to be strictly less than $r x_i$. At $x_i = 0$, this implies $E|\hat{x}_i| < 0$, which is impossible. Furthermore, relaxing the inequality to $\leq$ while maintaining finite two-sided Rényi divergence across the $0 \leftrightarrow 1$ edge leads to a contradiction (forcing the output at count 1 to be deterministic, violating the error bound).

Methodology and Repaired Formulation
To resolve the boundary issue, the authors propose a "repaired" utility requirement:
$$E|\hat{x}_i - x_i| < r \max\{x_i, 1\}$$
This maintains the relative error target for all positive counts while introducing a fixed absolute tolerance at zero, making the problem feasible.

The paper employs two primary methodological approaches:

1. Feasibility (Upper Bound): The authors specialize an existing "shifted-transformation" framework (Finley et al. [2026]). They transform the count space via a logarithm with a shift $c$ (i.e., $\log(x_i + c)$), add fixed-variance Gaussian noise, and apply a deterministic drift before exponentiating and clipping.

   • Key Innovation: Unlike standard log-normal mechanisms that use a drift of $-\sigma^2/2$ to ensure mean-unbiasedness, this mechanism uses a drift of $-\sigma^2$. This specific drift is chosen to minimize the expected absolute multiplicative error, which aligns with the paper's utility metric.
   • Privacy Mechanism: By working in log-space with equal variance, the mechanism ensures that the Rényi divergence between adjacent counts is finite for all orders $\alpha$, avoiding the "tail obstruction" where unequal variances cause infinite divergence in one direction.

2. Impossibility (Lower Bound): The authors prove that no mechanism satisfying the repaired utility and count-dependent zCDP requirements can achieve a privacy budget decay rate faster than the inverse-square of the count.

   • Two-Count Argument: A test between two specific counts establishes the $n^{-2}$ exponent.
   • Many-Count Argument: By utilizing a "hidden offset" random variable and information-theoretic arguments (relating expected absolute error to mutual information), the authors derive a tighter lower bound on the leading coefficient of the privacy budget.

Key Results

• Optimal Asymptotic Rate: For any fixed $0 < r < 1$, the optimal privacy budget $v(n)$ decays as $\Theta_r(n^{-2})$.

  • Upper Bound: The shifted-log Gaussian mechanism achieves $v(n) = O_r(n^{-2})$. Specifically, as $n \to \infty$, $v(n) \approx \frac{1}{2\sigma^2 n^2}$.
  • Lower Bound: Any mechanism satisfying the requirements must have $\liminf_{n \to \infty} n^2 v(n) \geq \frac{(1-r)^6}{128r^2(1+r)^2}$. This confirms the inverse-square rate is intrinsic and not an artifact of the construction.

• Leading Coefficients: The paper narrows the gap between the best possible upper and lower bounds for the leading coefficient $C^*$ in the limit of small $r$ and large $n$:
  $$\frac{\pi}{4e^2} \leq C^* \leq \frac{1}{\pi}$$
  The ratio between these bounds is approximately 2.995, indicating the bounds are within a factor of three.

• Failure of Unequal-Variance Gaussian: The paper demonstrates that a naive mechanism releasing $N(n, r^2 n^2)$ (Gaussian noise with variance proportional to the square of the count) fails the zCDP definition. While it has the correct error scale, the unequal variances between adjacent counts cause the Rényi divergence in one direction to become infinite for sufficiently high orders $\alpha$, violating the "all-orders" requirement of zCDP.

• Trivial Case: At $r=1$, a data-independent release (e.g., always outputting $0.5$) satisfies the repaired criterion with zero privacy loss ($v \equiv 0$).

Significance and Claims
The paper claims to provide the first mechanism-independent proof that the inverse-square rate is optimal for this specific formulation of group-wise privacy.

• Feasibility: It establishes that the "repaired" formulation is solvable and provides a concrete, composable mechanism (shifted-log Gaussian) that achieves the optimal rate.
• Optimality: It proves that no mechanism, regardless of complexity or correlation structure, can improve upon the $n^{-2}$ decay rate.
• Precision: By employing many-count information arguments, the paper significantly tightens the bounds on the leading constant compared to previous two-count analyses, reducing the uncertainty to a factor of less than three.

The authors explicitly state that determining the exact value of the optimal coefficient $C^*$ remains an open question. They also note that their results apply to fixed, disjoint groups; overlapping or data-dependent groups would require separate sensitivity analysis. The mechanism is biased (due to the $-\sigma^2$ drift) but is calibrated specifically to minimize expected absolute error, not to be unbiased.