Limits of Personalizing Differential Privacy Budgets

• URL: http://arxiv.org/abs/2605.13503v1
• Date: Wed, 13 May 2026 13:24:50 GMT
• Title: Limits of Personalizing Differential Privacy Budgets
• Abstract summary: We show that personalized privacy budgets come with major limitations and that for mean estimation, the dominant factor is not full personalization, but rather choosing the right effective privacy budget.<n>We quantify the constant-factor improvement in settings with mixed private and public datasets and in private datasets with two levels of privacy requirements.
• Score: 10.338341376480116
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A key technical difficulty in differential privacy is selecting a privacy budget that satisfies privacy requirements while maximizing utility. A natural and well-studied workaround is to use personalized privacy budgets, which may differ across agents. In this paper, we show that personalized budgets come with major limitations and that for mean estimation, the dominant factor is not full personalization, but rather choosing the right effective privacy budget. This can be achieved through a simple thresholding operator that we describe. Compared with this thresholding baseline, the gains obtained by fully personalized mechanisms are limited. In particular, we precisely quantify the constant-factor improvement in settings with mixed private and public datasets and in private datasets with two levels of privacy requirements. We also establish upper bounds and identify regimes of maximal gain for arbitrary privacy requirements.

Related papers

• PrivATE: Differentially Private Average Treatment Effect Estimation for Observational Data [49.35645194884526]
  We introduce PrivATE, a practical ATE estimation framework that ensures differential privacy.<n>We design two levels (i.e., label-level and sample-level) of privacy protection in PrivATE to accommodate different privacy requirements.<n>PrivATE effectively balances noise-induced error and matching error, leading to a more accurate estimate of ATE.
  arXiv  Detail & Related papers  (2025-12-16T16:30:07Z)
• A General Framework for Per-record Differential Privacy [10.959311645622632]
  Per-record Differential Privacy (PrDP) addresses this by defining the privacy budget as a function of each record.<n>Existing solutions either handle specific privacy functions or adopt relaxed PrDP definitions.<n>We propose a general and practical framework that enables any standard DP mechanism to support PrDP.
  arXiv  Detail & Related papers  (2025-11-24T11:44:10Z)
• High-Dimensional Asymptotics of Differentially Private PCA [4.168157981135696]
  In differential privacy, statistics of a sensitive dataset are privatized by introducing random noise.<n>It remains unclear if such high noise levels are truly necessary or a limitation of the proof techniques.<n>This paper explores whether we can obtain sharp privacy characterizations that identify the smallest noise level required to achieve a target privacy level.
  arXiv  Detail & Related papers  (2025-11-10T16:17:16Z)
• Private Hyperparameter Tuning with Ex-Post Guarantee [98.43027866582979]
  " Utility-first" privacy mechanisms prioritize a desired level of utility and then determine the corresponding privacy cost.<n>We extend the work of Wu et al. [ 2019] and Liu and Talwar [ 2019] to support any sequence of private estimators.<n>We demonstrate that hyper parameter tuning for these estimators, including the selection of an optimal privacy budget, can be performed without additional privacy cost.
  arXiv  Detail & Related papers  (2025-08-21T02:42:23Z)
• Optimal Allocation of Privacy Budget on Hierarchical Data Release [48.96399034594329]
  This paper addresses the problem of optimal privacy budget allocation for hierarchical data release.<n>It aims to maximize data utility subject to a total privacy budget while considering the inherent trade-offs between data granularity and privacy loss.
  arXiv  Detail & Related papers  (2025-05-16T05:25:11Z)
• Enhancing Feature-Specific Data Protection via Bayesian Coordinate Differential Privacy [55.357715095623554]
  Local Differential Privacy (LDP) offers strong privacy guarantees without requiring users to trust external parties. We propose a Bayesian framework, Bayesian Coordinate Differential Privacy (BCDP), that enables feature-specific privacy quantification.
  arXiv  Detail & Related papers  (2024-10-24T03:39:55Z)
• Mean Estimation Under Heterogeneous Privacy Demands [5.755004576310333]
  This work considers the problem of mean estimation, where each user can impose their own privacy level. The algorithm we propose is shown to be minimax optimal and has a near-linear run-time. Users with less but differing privacy requirements are all given more privacy than they require, in equal amounts.
  arXiv  Detail & Related papers  (2023-10-19T20:29:19Z)
• Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Free [13.198689566654103]
  This work considers the problem of mean estimation under heterogeneous Differential Privacy constraints. The algorithm we propose is shown to be minimax optimal when there are two groups of users with distinct privacy levels.
  arXiv  Detail & Related papers  (2023-04-27T05:23:06Z)
• Algorithms with More Granular Differential Privacy Guarantees [65.3684804101664]
  We consider partial differential privacy (DP), which allows quantifying the privacy guarantee on a per-attribute basis. In this work, we study several basic data analysis and learning tasks, and design algorithms whose per-attribute privacy parameter is smaller that the best possible privacy parameter for the entire record of a person.
  arXiv  Detail & Related papers  (2022-09-08T22:43:50Z)
• Privately Publishable Per-instance Privacy [21.775752827149383]
  We consider how to privately share the personalized privacy losses incurred by objective perturbation, using per-instance differential privacy (pDP) We analyze the per-instance privacy loss of releasing a private empirical risk minimizer learned via objective perturbation, and propose a group of methods to privately and accurately publish the pDP losses at little to no additional privacy cost.
  arXiv  Detail & Related papers  (2021-11-03T15:17:29Z)
• Private Reinforcement Learning with PAC and Regret Guarantees [69.4202374491817]
  We design privacy preserving exploration policies for episodic reinforcement learning (RL) We first provide a meaningful privacy formulation using the notion of joint differential privacy (JDP) We then develop a private optimism-based learning algorithm that simultaneously achieves strong PAC and regret bounds, and enjoys a JDP guarantee.
  arXiv  Detail & Related papers  (2020-09-18T20:18:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.