Limits of Personalizing Differential Privacy Budgets

Edwige Cyffers, Juba Ziani

May 2026

During my stay at the Simons Institute, I discovered that heterogeneous privacy budgets were quite popular, because of their nice interplay with data markets and incentives. However, I could not really convince myself that they were a good strategy. After some unsuccessful discussions with several participants, I was lucky to find an interested ear in Juba, who started to investigate this question with me. I am really happy to quantify this intuition in this paper: personalizing privacy budgets is often not worth the pain, but we also characterize when the gain is the largest.
Profile image

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.

Bibtex

@misc{cyffers2026limits,
  title = {Limits of Personalizing Differential Privacy Budgets},
  author = {Cyffers, Edwige and Ziani, Juba},
  year = {2026},
  eprint = {2605.13503},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.13503},
  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.}
}