Meeting Utility Constraints in Differential Privacy: A Privacy-Boosting Approach

Bo Jiang, Wanrong Zhang, Donghang Lu, Jian Du, Sagar Sharma, Qiang Yan

Abstract

Data engineering often requires accuracy (utility) constraints on results, posing significant challenges in designing differentially private (DP) mechanisms, particularly under stringent privacy parameter $\epsilon$. In this paper, we propose a privacy-boosting framework that is compatible with most noise-adding DP mechanisms. Our framework enhances the likelihood of outputs falling within a preferred subset of the support to meet utility requirements while enlarging the overall variance to reduce privacy leakage. We characterize the privacy loss distribution of our framework and present the privacy profile formulation for $(\epsilon,\delta)$-DP and Rényi DP (RDP) guarantees. We study special cases involving data-dependent and data-independent utility formulations. Through extensive experiments, we demonstrate that our framework achieves lower privacy loss than standard DP mechanisms under utility constraints. Notably, our approach is particularly effective in reducing privacy loss with large query sensitivity relative to the true answer, offering a more practical and flexible approach to designing differentially private mechanisms that meet specific utility constraints.

Introduction

Differential Privacy (DP) traditionally operates on a "privacy-first" paradigm: a privacy budget $\epsilon$ is selected, noise is added accordingly, and the resulting utility is observed. However, real-world applications often demand a "utility-first" approach, where analysts require specific accuracy guarantees (e.g., "the query must be within 5% of the true value 90% of the time"). Meeting these constraints while maintaining a strict privacy budget is a significant challenge. Existing methods often rely on fixed noise distributions that are not optimized for specific accuracy regions, leading to suboptimal privacy-utility trade-offs.

The Privacy-Boosting (PB-DP) Framework

We introduce the Privacy-Boosting (PB-DP) framework, which flips the traditional script by starting with a target utility constraint and optimizing the noise distribution to minimize privacy leakage. The framework modifies a "kernel" DP mechanism (such as a Gaussian distribution) through a re-weighting process.

Methodology

The PB-DP mechanism involves three key steps:

  1. Defining Preferred Regions: A subset of the output space, $S(Q(X))$, is defined where the answer meets utility requirements (e.g., absolute or relative error bounds).
  2. PDF Boosting: The probability density function (PDF) of the noise is reshaped by applying a "boosting rate" $q$. This increases the likelihood that the noisy output falls within the preferred region.
  3. Optimization: A ternary search algorithm identifies the optimal kernel privacy level $\epsilon_0$ that minimizes total privacy loss while satisfying the utility constraint.
Visualization of different preferred region formulations: (a) data-dependent (relative error), (b) fixed preferred output region, and (c) data-independent (absolute error).

The framework is versatile, supporting various utility formulations as shown in the figure above. By increasing the overall noise variance of the base kernel, the mechanism hides individual data points more effectively, while the boosting ensures the output remains within the desired accuracy range.

Experimental Evaluation

The framework was evaluated using synthetic data to benchmark $(\epsilon, \delta)$ trade-offs across various query sensitivities ($\\Delta Q$) and the Adult Income Dataset (UCI) for local DP frequency estimation.

Key Results

  • Lower Privacy Loss: PB-DP consistently requires a smaller $\epsilon$ to meet the same utility goals compared to standard Gaussian mechanisms.
  • Composition Efficiency: The benefits of PB-DP amplify under sequential composition, making it highly budget-efficient for complex pipelines.
  • Sensitivity Resilience: The approach is particularly effective when query sensitivity is high relative to the true answer, a scenario where standard DP often fails to provide useful results.

Conclusion

The PB-DP framework offers a flexible and practical approach to meeting utility constraints in differentially private systems. While it may not be ideal for "pure" DP ($\\delta = 0$) due to the longer tails in the privacy loss distribution, its ability to optimize for specific accuracy regions provides a significant advantage in real-world data analysis. Future work includes extending the framework to other noise distributions and exploring adaptive data release scenarios.

Summary updated

Abstract

Data engineering often requires accuracy (utility) constraints on results, posing significant challenges in designing differentially private (DP) mechanisms, particularly under stringent privacy parameter $ε$. In this paper, we propose a privacy-boosting framework that is compatible with most noise-adding DP mechanisms. Our framework enhances the likelihood of outputs falling within a preferred subset of the support to meet utility requirements while enlarging the overall variance to reduce privacy leakage. We characterize the privacy loss distribution of our framework and present the privacy profile formulation for $(ε,δ)$-DP and Rényi DP (RDP) guarantees. We study special cases involving data-dependent and data-independent utility formulations. Through extensive experiments, we demonstrate that our framework achieves lower privacy loss than standard DP mechanisms under utility constraints. Notably, our approach is particularly effective in reducing privacy loss with large query sensitivity relative to the true answer, offering a more practical and flexible approach to designing differentially private mechanisms that meet specific utility constraints.
BibTeX
@inproceedings{jiang2025meeting,
  author = {Bo Jiang and Wanrong Zhang and Donghang Lu and Jian Du and Sagar Sharma and Qiang Yan},
  title = {{Meeting Utility Constraints in Differential Privacy: A Privacy-Boosting Approach}},
  booktitle = {Sp},
  year = {2025},
  doi = {10.1109/sp61157.2025.00064},
}
Figure