Technical Summary: Limits of Personalizing Differential Privacy Budgets

Problem Statement

In Differential Privacy (DP), selecting an appropriate privacy budget ($\epsilon$) is a fundamental challenge: a smaller $\epsilon$ ensures stronger privacy but degrades the utility (accuracy) of the computation. While classical DP imposes a uniform budget across all participants, a natural extension is personalized (or heterogeneous) DP, where each agent $i$ has a distinct privacy requirement $\epsilon_i$. This approach is motivated by the fact that agents have varying privacy attitudes and that personalization theoretically expands the space of feasible algorithms, potentially improving the privacy-accuracy trade-off.

However, fully personalized mechanisms (e.g., affine estimators that reweight data points based on individual $\epsilon_i$) are complex to audit, communicate, and adapt. A simpler alternative is a thresholding estimator, which discards data points with overly stringent privacy requirements and applies a single, carefully chosen privacy budget to the remaining data.

The central question addressed in this paper is: Does the complexity of full personalization yield significant gains in utility (specifically for mean estimation) compared to the simpler thresholding baseline? The authors investigate whether the "marginal value" of full personalization is substantial or if the gains are modest in most practical regimes.

Methodology and Model

The authors focus on the problem of mean estimation for a distribution $P$ with bounded support $[-1/2, 1/2]$, given $n$ i.i.d. data points where each point $x_i$ has a specific privacy budget $\epsilon_i$.

Estimators Compared

1. Optimal Affine Estimator (Fully Personalized):

   • This is the best-known estimator for heterogeneous DP. It uses a weighted average of the data points: $\hat{\mu} = \sum w_i x_i + Z$, where $Z$ is Laplace noise.
   • The weights $w_i$ are optimized to minimize the Mean Squared Error (MSE).
   • The optimal strategy involves "clipping" privacy levels: a threshold $\tau$ is selected, and effective privacy levels are set to $\bar{\epsilon}_i = \min(\epsilon_i, \tau)$. Weights are proportional to these clipped levels ($w_i \propto \bar{\epsilon}_i$), and the noise scale is determined by the maximum sensitivity relative to the clipped budgets.
   • The MSE is characterized as:
     $$\text{MSE}_{\text{aff}}(\epsilon) = \inf_{\tau>0} \left( \frac{q_\tau}{4s_\tau^2} + \frac{2}{s_\tau^2} \right)$$
     where $s_\tau = \sum \min(\epsilon_i, \tau)$ and $q_\tau = \sum \min(\epsilon_i, \tau)^2$.

2. Unique-Threshold $\epsilon$ Estimator (Simplified Baseline):

   • This estimator selects a single global threshold $\epsilon$.
   • It discards all data points where the individual requirement $\epsilon_i < \epsilon$.
   • It applies a uniform privacy budget $\epsilon$ to the remaining $n_\epsilon$ data points.
   • The MSE is minimized over the choice of $\epsilon$:
     $$\text{MSE}_{\text{thr}}(\epsilon) = \inf_{\epsilon>0} \left( \frac{1}{4n_\epsilon} + \frac{2}{\epsilon^2 n_\epsilon^2} \right)$$

Metric

The performance is measured by the Distributionally-Robust Mean-Squared Error (worst-case MSE over distributions with bounded support). The authors analyze the approximation ratio $\frac{\text{MSE}_{\text{thr}}}{\text{MSE}_{\text{aff}}}$ to quantify the loss in utility when using the simple thresholding approach instead of the optimal affine mechanism.

Key Contributions and Results

The paper provides precise bounds on the performance gap between the thresholding estimator and the optimal affine estimator across three distinct regimes:

1. Public and Private Data Combination

• Setting: A mixture of $n_1$ private data points (budget $\epsilon_1$) and $n_2$ public data points (effectively $\epsilon_2 = \infty$).
• Result: The thresholding estimator achieves a 2-approximation to the optimal affine estimator.
• Insight: The gap is tight and approaches 2 only in a narrow region where the variance contributions of the private and public parts are balanced. In most other configurations, the ratio is close to 1, indicating negligible gain from personalization.

2. Two Finite Privacy Levels

• Setting: Data points have one of two finite privacy budgets, $\epsilon_1 < \epsilon_2$.
• Result: The approximation ratio degrades from 2 to 4.
• Insight: The authors provide a counterexample showing the ratio can exceed 2. However, they prove that the ratio is bounded by 4 regardless of the specific values of $\epsilon_1, \epsilon_2$ or the data counts. This implies that even in this slightly more complex setting, the thresholding approach captures the vast majority of the utility.

3. Arbitrary Number of Privacy Levels ($m$ levels)

• Setting: Data points have $m$ distinct privacy levels ($0 < \epsilon_1 < \dots < \epsilon_m$).
• Result: No constant-factor approximation is possible in general.
  • Lower Bound: The authors construct a specific instance where the ratio grows quadratically with the number of levels: $\Omega(m^2)$. Specifically, if $m \approx \log_2 n$, the ratio is $\Omega((\log_2 n)^2)$.
  • Upper Bound: They prove that for any instance, the ratio is bounded by $\min((1 + \log_2 n)^2, m^2)$.
• Insight: While the gap can theoretically grow with the number of privacy levels, the growth is limited (quadratic in $m$ or logarithmic in $n$). The "worst-case" scenarios require specific, somewhat contrived distributions of privacy levels and data counts.

Significance and Claims

The paper argues that the dominant factor in achieving high utility in heterogeneous DP is choosing the right effective privacy budget rather than implementing full personalization.

• Modest Gains: In the most common and practical scenarios (combining public/private data or handling two levels of privacy), the gains from fully personalized affine estimators are limited to constant factors (at most 4x).
• Practicality of Thresholding: The thresholding estimator offers significant practical advantages: it is easier to audit, allows for clearer communication of privacy guarantees, and adapts more simply to changes in the user base. It also provides "free" privacy to agents who are more generous with their data.
• Theoretical Limits: While the paper establishes that the gap can grow with the number of privacy levels ($m$), the authors note that optimal personalized estimators are not even known for $m > 2$ in the general case. Thus, the thresholding approach remains a robust, near-optimal heuristic for mean estimation.

The authors conclude that for mean estimation, the complexity of full personalization is often not justified by the marginal utility gains, suggesting that simpler thresholding strategies are sufficient for most regimes of interest. They conjecture that similar takeaways may hold for broader learning tasks, though this remains an open area for future research.