Limits of Personalizing Differential Privacy Budgets
arXiv:2605.13503v1 [cs.CR] 13 May 2026
Edwige Cyffers CNRS, LAMSADE, Dauphine-PSL [email protected]
Juba Ziani Georgia Institute of Technology. [email protected]
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.
1
Introduction
Differential Privacy (DP) has become a gold standard for privacy protection, particularly for releasing population-level statistics and deploying machine learning models [18]. Differential Privacy ensures that the presence or absence of any single data point in the training data cannot affect the final model too much, thereby guaranteeing that an outside observer cannot learn too much about a specific record from the resulting model. This guarantee is controlled by a parameter ε, called the privacy budget: a smaller ε corresponds to a stronger privacy guarantee. Enforcing DP requires randomization, often achieved by injecting noise into the computation. This noise hides an agent’s data: variations in the model or statistic when one’s data is or is not included can now be attributed to the noise added to the computation, while complying with all reported privacy levels. However, it also degrades the utility and accuracy of the computation. A recurring question in DP is thus how to select the right privacy budget, in order to achieve the highest possible accuracy while maintaining satisfactory privacy constraints [30, 17]. In the classical formulation of Differential Privacy, a single privacy budget is imposed uniformly across all participants, i.e., all data points are guaranteed the same level of privacy ε. A natural extension is therefore to relax this assumption and allow individualized privacy budgets. From an optimization point of view, this enlarges the space of algorithms satisfying the privacy constraints and can therefore remove a source of suboptimality, in the same way that personalized pricing can improve profitability. This personalization of the privacy budget is also grounded in the well-studied fact that different agents have different privacy attitudes [3, 21, 27]. Exploiting individualized privacy budgets has thus emerged as a rich research field. In particular, this has been observed by [11, 15, 19, 13] for mean estimation. The affine estimator that assigns different levels of privacy to different agents in the central model through reweighting, also known as a sensitivity pre-processing step [14], vastly improves over the naive baseline that sets the noise level according to the most stringent privacy requirement. More precisely, these works i) show that when agents can have one of two possible privacy requirements, their affine estimator is optimal, ii) compute the optimal weights and affine estimator that minimize the mean-squared error of the final estimate for any potential Preprint.
privacy profile, including, e.g., the case where every single agent has a different privacy requirement, and iii) characterize the mean-squared error of the resulting estimator. However, choosing the estimator that uses all data points with the minimum privacy budget as a baseline may be too naive. Consider a setting with n agents. One agent a has a very stringent privacy budget, e.g., εa = 0.01, while all remaining agents have moderate privacy requirements, e.g., ε = 1. In this case, a learner should not add noise calibrated to the smallest privacy budget εa to the entire computation. Instead, they should discard the data of agent a and tailor the rest of the mechanism to the much more favorable privacy level ε, thereby largely reducing the amount of noise added to the computation. This suggests that another natural baseline against which to compare fully personalized mechanisms is a single privacy budget ε for all retained data points, where ε is chosen more carefully than the minimum. This leads to a natural thresholding estimator: given a set of privacy preferences from agents 1 to n, denoted by ε1 , . . . , εn , the learner chooses a threshold τ , discards the data points of all agents i such that εi < τ , and adds noise calibrated to privacy level τ to the remaining dataset—perhaps the simplest form of privacy techniques that trim part of the dataset, as seen in [10]. This is a transparent and easy-to-implement heuristic for dealing with agents with widely differing privacy preferences, and it is not hard to see that this estimator can be orders of magnitude better than the naive minimum-budget estimator. However, this raises the following question: in the simple problem of mean estimation, how much is actually gained from personalization? The thresholding operator has several advantages over personalized mechanisms: it enables easier auditing of the privacy mechanism, clearer communication of the algorithm’s privacy guarantee, and simpler adaptation to changes in the set of participating users. It also provides privacy for free to the agents who were more generous with their data. Yet, from a practical perspective, it is not clear whether the best-known affine estimator yields significant gains in the privacy-accuracy trade-off compared to the thresholding estimator proposed above and in the related literature. In particular, to the best of our knowledge, no prior work has attempted to bound the gap between this simple thresholding heuristic and the optimal affine estimator of the population mean. The question we ask is therefore the following: does personalized affine weighting provide a genuinely meaningful improvement over such thresholding, or are the gains modest in most, or even all, regimes of privacy preferences? Our results show that the gains are quite modest in most practical scenarios. Summary of contributions
Our contributions are as follows:
• Public and private data (Section 4). We first study the setting where private data can be combined with public data, and show that our simple threshold-based estimator achieves a 2-approximation to the optimal affine estimator. • Two privacy levels (Section 5). We then turn to the case of two finite privacy levels. We first show a gap with the case of a public and a private dataset, and show that one cannot achieve a 2-factor approximation in the worst case by using our threshold-based estimator. However, we show that the threshold-based estimator continues to provide a constant-factor guarantee, namely a slightly worse 4-approximation to the optimal affine estimator. • Arbitrary privacy levels (Section 6). Finally, we consider the general case with an arbitrary number of privacy levels, where we show that no constant-factor approximation is possible in general: if m privacy levels are allowed among n data points, we show that the approximation ratio between the threshold-based and the optimal affine estimator is tightly given by Ω min log2 n, m2 . Related Work While DP typically imposes uniform privacy budget across all individuals, a substantial line of research considers personalized privacy guarantees. In particular, the notion of heterogeneous differential privacy that we use in this work was originally formalized by [23, 25, 2]. This definition refines the traditional notion of DP to allow each individual or data point to be protected with a distinct privacy parameter. A core idea that allows personalized privacy guarantees in the central privacy model is “sensitivity preprocessing” [14]—simply said, allowing queries to have different sensitivities with respect to different data points. The lower the sensitivity of a given individual or data point in a computation, the better their privacy guarantee. For mean estimation, [11, 13] leverage this idea—in particular, giving different weights to different data points as a function of their privacy requirement—and study how allowing heterogeneous privacy levels can improve 2
accuracy compared to enforcing the most stringent privacy requirement uniformly across all users. Beyond mean estimation, there has been a small line of work aiming to understand heterogenous differential privacy in loss minimization contexts [9, 8, 1]. There has also been a significant line of work in mechanism design for data acquisition and data markets [16, 22, 23, 15, 19, 5]; in these settings, agents incur heterogeneous economic costs for privacy, and must be compensated for said costs either through a monetary payment or a service offered in return. There has also been work on personalized privacy accounting, where different data points may incur different realized privacy losses over time, and the goal is to track the effective privacy budget consumed by each data point [20]. Finally, a complementary and important line of work, whose goal is also to improve privacy-accuracy trade-offs in DP, studies how public or non-sensitive data can be leveraged. These works show that auxiliary public data can significantly reduce the cost of privacy in estimation and optimization tasks [4, 32, 6, 31, 26, 7]. Most of these works assume that privacy preferences and data are uncorrelated, in particular due to strong impossibility results [23, 28]. However, very recently, [12] has made the first breakthrough in over a decade in allowing heterogeneous DP while accounting for the correlation between data points and privacy requirements; this setting is outside the scope of the current paper but an important foundation for future work. Despite this rich literature, existing work primarily focuses on designing or characterizing optimal mechanisms under heterogeneous privacy constraints. In contrast, relatively little is understood about the marginal value of full personalization compared to simpler alternatives. In particular, prior analyses typically benchmark personalized mechanisms against naive baselines that calibrate noise to the most stringent privacy requirement, which can significantly underestimate the performance of simpler approaches. In this work, we revisit this question in the context of mean estimation by comparing the best-known affine estimators under heterogeneous privacy with a simple thresholding approach that enforces a single privacy level on a subset of the data. Our results show that, in most regimes of interest, the gains from full personalization are relatively limited.
2
Preliminaries for Differentially Private Mean Estimation
In this section, we introduce and motivate the definitions and tools used in the remainder of the paper. Definition 1 (Approximate Differential Privacy). A mechanism M is (ε, δ)-differentially private if, for all neighboring datasets D ∼ D′ and all measurable sets S, the following inequality holds, where the randomness is over the randomness of M: P(M(D) ∈ S) ≤ eε P(M(D′ ) ∈ S) + δ. In this definition, the dataset D is typically a set of records D = {xi }ni=1 , and the neighboring relation corresponds to replacing one record by another. For instance, D′ = {x′i }ni=1 with x1 ̸= x′1 and xi = x′i for all i > 1. Pure differential privacy corresponds to the special case where δ = 0. A simple DP mechanism is the Laplace mechanism. Definition 2 (Laplace mechanism). Let ∆ = maxx∼x′ |f (x) − f (x′ )|. The Laplace mechanism for the function f is M(x) = f (x) + η, η ∼ Lap(∆/ε), and this mechanism is (ε, 0)-DP. For personalized privacy budgets, a first attempt is to include the privacy budget within each record and consider D = {(xi , εi , δi )}ni=1 , allowing arbitrary changes in the triplet as before. Definition 3 (Arbitrary Personalized DP). A mechanism M is arbitrary personalized differentially private if, for all neighboring datasets D ∼ D′ , where (x, ε, δ) is changed into (x′ , ε′ , δ ′ ), and all measurable sets S, the following inequality holds, where the randomness is over the randomness of M: ′ P(M(D) ∈ S) ≤ emin(ε,ε ) P(M(D′ ) ∈ S) + min(δ, δ ′ ). Unfortunately, this definition is too stringent. Let ε∗ = min1≤i≤n εi and δ ∗ = min1≤i≤n δi . A well-known folklore result attributed to Kobbi Nissim, Salil Vadhan, and David Xiao1 states that 1While the result is well known to the differential privacy community, there is no public source formally stating the result
that can be cited here. We provide a proof for completeness.
3
∗
any arbitrary Personalized DP algorithm is (2ε∗ , (1 + eε )δ ∗ )-DP. In other words, the fact that some records are satisfied by larger privacy budgets does not allow the use of a less restrictive mechanism. Proof. Fix D ∼ D′ differing at the i-th record, and denote by (xi , εi , δi ) and (x′i , ε′i , δi′ ) their respective i-th records. Both datasets are also neighboring from D′′ , where all records are equal to those of D except the i-th one, replaced by (x, ε∗ , δ ∗ ). It follows that the two following inequalities must hold: ∗
P(M(D) ∈ S) ≤ eε P(M(D′′ ) ∈ S) + δ ∗ and ∗
P(M(D′′ ) ∈ S) ≤ eε P(M(D′ ) ∈ S) + δ ∗ . Combining both gives the result. Remark 1. This impossibility result is not specific to mean estimation, but holds for any differentially private algorithm. Thus, it is not possible to exploit personalized privacy budgets if these budgets can be changed arbitrarily: in that case, one is forced to align the mechanism with the most stringent privacy requirement. Taking advantage of personalization already assumes that the learner can access the privacy budget of each participant. This can be achieved by decoupling the privacy budget from the data, as is done in most related work [23, 25, 19, 14, 15, 13, 11]. Definition 4 (Heterogeneous Differential Privacy [23, 25]). Fix a vector ε = (ε(1) , . . . , ε(n) ). The mechanism M is heterogeneous ε-DP if, for all i ∈ [n], (i)
P(M(D) ∈ S) ≤ eε P(M(D′i ) ∈ S), for all measurable sets S, where D and D′i are any two neighboring datasets that differ arbitrarily only in the i-th component. We adopt this definition in the rest of the paper.
3
Model
In this work, we compare the performance of two estimators, defined formally below: one with heterogeneous privacy budgets and one with homogeneous privacy guarantees. We consider the task of estimating the mean µP of a distribution P with bounded support [−1/2, 1/2]. The learner has access to n data points drawn i.i.d. from P. In addition, each data point xi comes with its own privacy requirement. We assume that the privacy budgets {ε(i) }i take values in a finite set of at most m ≤ n distinct elements, denoted by ε1 < . . . < εm , and we denote by ni the number of participants with privacy budget εi . To ensure heterogeneous DP, any estimator that uses data point xi must satisfy ε(i) -differential privacy with respect to xi . 3.1
Mean estimation problem
Given an estimator µ̂ of the population mean µP , we define the distributionally-robust risk, or mean-squared error, as our main measure of the accuracy, or quality, of an estimator: Definition 5 (Distributionally-Robust Mean-Squared Error). sup E (µ̂ − µP )2 . P
Our work quantifies the maximum possible gains on this metric obtained by fully tailoring the privacy mechanism to personalized privacy budgets. We do so by comparing the best affine fully personalized estimator with an estimator that ensures a single privacy budget. 4
3.2
Best affine estimator
We consider the class of unbiased affine estimators, i.e. estimators based on a noisy weighted average of the data points n X µ̂w (D) = wi xi + Z , i=1
Pn
where wi ≥ 0, i=1 wi = 1, and Z ∼ Lap(η). To ensure ε-heterogeneous differential privacy for every user u, the noise scale must satisfy wi . i∈[n] ε(i)
η ≥ max
Thus, for fixed weights, the optimal noise parameter is η = max
wi
i∈[n] ε(i)
,
and designing an optimal estimator boils down to finding the optimal weights. Such a characterization of the optimal weights is given in [13], and we refer the reader to that work for detailed expressions. For our purposes, we only need to characterize the mean-squared error of the optimal affine estimator. The error comes from two sources: the variance of the data points themselves and the variance of the injected noise. The optimal affine estimator corresponds to the weights that minimize these two terms, leading to the following formula: ( n 2 ) 1X 2 wi w + 2 max (i) MSEaff (ε) := inf . (1) 4 i=1 i i∈[n] ε Pnwi ≥0 i=1 wi =1
Several previous works [13, 15, 19] obtain a more explicit characterization of this error by noting that the optimal weights are obtained by clipping the privacy levels. More precisely, the optimal affine estimator sets a threshold τ > 0, defines ε̄(i) = min{ε(i) , τ }, and ensures privacy with respect to these truncated privacy levels. Since ε̄i ≤ εi , the privacy requirements of all data points are satisfied. The weights are then set to be proportional to the clipped privacy budgets and normalized, namely min{ε(i) , τ } wi = P (i) i min{ε , τ } 1 and the noise parameter is set as before to satisfy all privacy constraints: η = P min{ε (i) ,τ } . Using i this set of weights yields an explicit formula for the mean-squared error of the optimal affine estimator.
Claim 1. For any τ > 0, define sτ :=
n X
min{ε(i) , τ },
qτ :=
i=1
n X
min{ε(i) , τ }2 .
i=1
Then MSEaff (ε) = inf
τ >0
qτ 2 + 2 2 4sτ sτ
.
(2)
The proof is straightforward and can be found in Appendix A. When the data points can have at most two privacy requirements, i.e., m = 2 with 0 < ε1 < ε2 , [13] shows that the affine estimator above is optimal in terms of mean-squared error. An immediate extension is that the affine estimator is also optimal when combining private data at a predetermined privacy level ε1 > 0 with public data, corresponding to taking ε2 → ∞. When m > 2 heterogeneous privacy levels are allowed, the optimal affine estimator may no longer be optimal among all estimators. However, we still use the optimal affine estimator as our main point of comparison, noting that it is currently the best-known estimator for mean estimation under heterogeneous privacy. 5
3.3
Unique-Threshold ε-estimator
We compare the best affine estimator with a simple and natural estimator, which we call the uniquethreshold ε operator. The key idea is to select a single privacy budget that respects the guarantees imposed by ε-heterogeneous differential privacy while minimizing the mean-squared error. Informally, this operator discards all data points with overly stringent privacy requirements, then adds noise calibrated to the remaining dataset. This estimator does not exploit heterogeneity: it provides a single, identical privacy level ε to all agents whose data is used in the mean estimation. More formally, we define the estimator as follows. Definition 6 (Unique-threshold ε estimator). Let ε be fixed. For a given Pnε, let 1(ε) be the vector whose i-th component is 1 if ε(i) ≥ ε and 0 otherwise, and let nε = i=1 1(ε)i . The threshold mechanism Mε is defined by n 1 X ∆ Mε (D) = , 1(ε)i xi + Lap nε i=1 nε ε and is ε-DP. The unique-threshold ε estimator corresponds to a choice of ε in the threshold mechanism minimizing the mean squared error. As for the affine estimator, the mean-squared error is given by 1 2 MSEthr (ε) := inf + 2 2 . ε>0 4nε ε nε
(3)
The rest of the paper compares these two estimators under different scenarios for the privacy-budget vector ε.
Limits of public-private combination 104 103
1.8
1.8
1.6
1.6
1.4
10 1 1.2
10 2 10 3 3 10
10 2
10 1 1
100
101
1.0
Gain
100
Gain
101 1.26
n1/n2
102
1.4
1.6 1.4 1.2
1.2 1.0
n1/n2 = 0.01 n1/n2 = 0.1 n1/n2 = 1 n1/n2 = 10 n1/n2 = 100 n1/n2 = 1000
1.8
1 = 0.001 1 = 0.01 1 = 0.05 1 = 0.1 1 = 0.25 1 = 0.5
Gain
4
10 2
100
n1/n2
(a)
(b)
102
104
1.0
10 3
10 2
10 1 1
100
101
(c)
Figure 1: Ratio between the unique-threshold estimator and the best affine operator for a combination of public and private data, for a fixed n2 = 1000. The heatmap shows a narrow region where the gain is significant. The outermost contour level is set to 1.01. Figures 1c and 1b correspond respectively to rows and columns of the heatmaps, making it possible to visualize the rapid decay of the gain. We first consider a scenario in which a mixture of public and private data is available. The learner has access to n1 data points with privacy requirement ε1 > 0. In addition, the learner has access to n2 public data points, for which no noise needs to be added, equivalently, ε2 = +∞. In this regime, the public data do not require noise injection to estimate the mean. Thus, for the private and public parts of the estimator to have comparable variance, one typically needs n1 ≫ n2 . At this equilibrium, the two parts contribute equally to the error, leading to a constant factor of 2. Theorem 1. Let MSEthr denote the risk of the unique-threshold estimator in the public-data regime, and let MSEaff denote the optimal affine risk. Then MSEthr ≤ 2. MSEaff 6
The proof can be found in Appendix B. This bound is tight and can be approached, when n1 n2 ≈ . 1 + 8/(n1 ε21 ) For example, the ratio is close to 1.95 for ε1 = 0.001, n1 = 104 , and n2 = 12. The ratio however drops quickly to 1 when the proportions are not following this rule, as reported in Figure 1.
5
A warm-up: two privacy budgets
In this section, we adopt nearly the same setting as in the previous section, but with finite privacy for ε2 . Thus, the learner has access to n1 data points for which they must satisfy ε1 -differential privacy, and to n2 data points with an ε2 -differential privacy requirement, where 0 < ε1 < ε2 < +∞. In this case, the approximation guarantee degrades compared to Section 4, from a factor of 2 to a factor of 4. We first give a simple counterexample violating the factor-2 guarantee, and then prove the factor-4 bound. Example 1. Consider ε = ( 21 , 1). We can compute the mean-squared errors of the two estimators using Equations (2) and (3). It is easy to verify that the unique-threshold estimator has mean-squared error 17/8, while the optimal affine estimator has mean-squared error 37/36. In particular, this implies that 17/8 MSEth (ε) ≥ > 2. MSEaff (ε) 37/36 However, we show that with two privacy levels, the approximation ratio between the unique-threshold estimator and the optimal affine estimator remains constant, independently of the value of ε. Theorem 2. Let MSEth (ε) denote the mean-squared error of the unique-threshold estimator, and let MSEaff (ε) denote the optimal affine risk. Then MSEth (ε) ≤ 4. MSEaff (ε) The full proof can be found in Appendix D. It follows a similar structure to the public-private case, with a slightly more involved characterization of the transition between the regime where τ = ε1 is optimal and the regime where τ = ε2 is optimal. Note that this factor corresponds to the improvement obtained from having four times more data, or from doubling ε in regimes where ε is small enough relative to n.
101 100
2.0 1.5 1.25
10 1
1.11.05
3.5
3.0
3.0
2.5 2.0 1.5
10 2 10 3 4 10
10 3
10 2
1/ 2
10 1
100
1.0
Gain
n1/n2
102
3.5
Gain
103
n1/n2 = 0.01 n1/n2 = 0.1 n1/n2 = 1 n1/n2 = 10 n1/n2 = 100 n1/n2 = 1000
2.5
4.0 3.5 3.0
Gain
4.0
3.0
104
2.5
2.0
2.0
1.5
1.5
1.0
10 4
10 3
(a)
10 2
1/ 2
10 1
(b)
100
1.0
1/ 2 = 0.001 1/ 2 = 0.01 1/ 2 = 0.05 1/ 2 = 0.1 1/ 2 = 0.25 1/ 2 = 0.5
10 2
100
n1/n2
102
104
(c)
Figure 2: Ratio between the unique-threshold estimator and the best affine operator for two finite privacy levels, similarly to Figure 1, keeping n2 = 1000 and ε2 = 0.03 to ensure a large gain ratio.
6
Limits of General choice of privacy budgets
Finally, we consider the general case in which there is an arbitrary number of privacy levels m ≥ 2. For all i ∈ [m], we denote by ni the number of data points with privacy requirement εi , where 7
0 < ε1 < . . . < εm . We denote by n the total number of available data points across all privacy levels. We show that the unique-threshold operator cannot guarantee a constant-factor approximation to the best-known affine estimator. We first provide a lower bound showing that no constant-factor approximation can be guaranteed when the number of privacy levels is not constant. In particular, we construct a class of privacy parameters for which the ratio grows with m, showing that the approximation ratio is not uniformly bounded by a constant independent of the problem parameters. Theorem 3. Take any m ≥ There exist privacy levels 0 < ε1 < · · · < εm and data quantities P2. m n1 , . . . , nm ∈ N with n ≜ i=1 ni = 2m − 1 such that MSEthr (ε) m2 ≥ . MSEaff (ε) 5 In particular, as m = log2 (n + 1), we obtain (log2 (n + 1))2 MSEthr (ε) ≥ . MSEaff (ε) 5 Proof Sketch. The full proof is given in Appendix E. The intuition behind our construction is as follows. The unique-threshold estimator chooses a privacy threshold ε: a smaller ε requires the learner to satisfy more stringent privacy constraints, but also allows them to use a larger number of data points nε . Since the sensitivity of the mean is 1/nε , as recalled in our preliminaries, the amount of noise required for privacy is controlled by ∆/ε = 1/nε ε. We construct an instance of the problem in which: i) nε ε = O(1) regardless of how the learner chooses ε, leading to a constant noise level and hence to a constant mean-squared error for the unique-threshold estimator; while ii) the optimal affine estimator can still exploit all privacy levels, and its variance decreases as m increases. Concretely, our construction saturates each privacy level by taking εi = 2−(i−1) and ni = 2i−1 , ensuring that ni εi and εnε remain of order O(1) regardless of the threshold chosen by the learner2 ; this forces the learner to add total noise scaling with O(1). At the same time, the affine optimum assigns smaller weights Pm to more private users and larger weights to less private ones, splitting the total privacy burden of i=1 ni εi ∼ m unevenly across agents. In particular, setting the weight εi wi = Pm
i=1 ni εi
∼
εi m
and
η = Pm
1
i=1 ni εi
∼
1 m
guarantees the desired level of privacy and ensures the privacy noise parameter scales with 1/m, leading to a variance due to noise scaling with 1/m2 . An upper bound on the approximation factor Finally, we conclude our results by showing that this bound is effectively tight. Namely, we show that for any instance withm distinct privacy levels, the approximation factor of the unique-threshold estimator is at most min (1 + log2 n)2 , m2 . Theorem Pm 4. For any m ≥ 2, for any 0 < ε1 < · · · < εm and n1 , . . . , nm ∈ N such that n = i=1 ni , we have that: MSEthr (ε) ≤ min (1 + log2 n)2 , m2 . MSEaff (ε) Proof Sketch. The proof of the Theorem can be found in Appendix E. The proof relies on the explicit MSE characterization for the affine estimator given in 2. Fix any τ > 0, and let ε̄j = min{εj , τ }. Then the affine estimator corresponding to τ has noise controlled by the total clipped quantity sτ =
m X
nj ε̄j .
j=1 2 This construction is similar to a well-known distribution in mechanism design called the equal revenue distribution [24], which ensures that, given a cdf F , x(1 − F (x)) = 1 for all x. In mechanism design, this distribution induces situations where a posted price mechanism always extracts the same revenue of 1 independently of the choice of price, and is particularly relevant in bounding the gap between simple and optimal mechanisms in single-bidder single-item auctions.
8
The unique-threshold estimator is controlled by a directly comparable quantity, namely ε∗ nε∗ . For every fixed clipping constant τ , one can always choose a threshold ε∗ among the clipped values such that sτ ε∗ nε∗ ≥ , m by the pigeonhole principle. In other words, although the affine estimator spreads its contribution across several clipped privacy levels, at least one threshold always captures at least a 1/m fraction of the total sτ . Since the threshold estimator adds noise of scale 1/(ε∗ nε∗ ), while the affine estimator corresponding to τ adds noise of scale 1/sτ , this implies that the threshold estimator loses at most a factor m in noise scale, and therefore at most a factor m2 in the resulting variance. The worst-case of (1 + log2 n)2 comes from the harmonic series Hn ∼ 1 + log2 n, and a standard argument that sτ ≤ Hn maxε εnε . Note that the bounds of Theorems 3 and 4 are tight up to constant factors. More precisely, whenever 2m − 1 ≤ n, both bounds are of the order of Ω(m2 ). Once m becomes larger than log2 n, the approximation factor saturates at order log22 n and increasing m cannot worsen the ratio as per Theorem 4. i.e., the approximation factor grows quadratically with the number of privacy levels so long as 2m ≤ n.
7
Discussion
Our work focuses on the specific problem of mean estimation, which limits the generality of our results. Indeed, in the context of mean estimation, affine estimators are optimal for m = 2; however, it is unclear whether they remain optimal for m > 2. A natural direction is therefore to characterize the optimal estimator in this regime and quantify its gap with the simple threshold-based approach. Second, while mean estimation is a canonical task and a standard proxy in the literature, extending these insights to broader learning and optimization problems remains an important challenge. A key limitation is that there is currently no theoretical characterization of near-optimal or optimal heterogeneous differentially private estimators, even for simple problems such as linear regression. Mean estimation is often used as a proxy for harder tasks. For instance, the widely used DP-Followthe-Regularized-Leader SGD minimizes the mean-squared error over the sum of gradients, even though minimizing this quantity does not translate directly into optimization guarantees [29]. We thus believe that, given the current state of the theory, mean estimation is the best available proxy for testing the advantage provided by full personalization. Another open direction is whether our takeaways are specific to the Laplace mechanism and pure differential privacy. Our results primarily rely on how privacy constraints translate into the variance of an additive noise term, suggesting that similar qualitative behavior, where the gap is controlled by the number of privacy levels m, may extend to other additive mechanisms and alternative privacy definitions, such as z-CDP or approximate DP. However, extending our analysis to these settings is not immediate. In particular, privacy notions with more favorable composition properties may allow heterogeneous privacy constraints to aggregate differently, potentially reducing the overall noise required, for example by yielding sublinear dependence on m.
8
Conclusion
Our results show that, in mean estimation under heterogeneous differential privacy constraints, relatively little is gained from full personalization. A simple thresholding estimator — discarding overly private data and applying a single carefully chosen privacy level — already captures most of the achievable utility compared to the optimal affine estimator. In particular, it achieves constant-factor approximations in natural regimes (e.g., a factor of 2 with public data and 4 with two privacy levels), and we precisely characterize when and how larger gaps can arise. When n agents and m > 2 privacy levels are present, the picture becomes more nuanced, with an approximation factor of O(log2 n) in the worst case; however, the gains remain modest. Since optimal personalized estimators are not known in more complex settings, the gains from personalization for broader learning tasks remain open. We conjecture that similar takeaways could be established beyond mean estimation. 9
9
Acknowledgments
Prof. Ziani was supported by NSF CAREER IIS-2336236 and NSF Medium IIS-2504990. Edwige Cyffers was supported by the National Research Agency under France 2030, reference “ANR-23IACL-0008”. This work was done while the authors were visiting the Simons Institute for the Theory of Computing.
References [1] Krishna Acharya, Franziska Boenisch, Rakshit Naidu, and Juba Ziani. Personalized differential privacy for ridge regression under output perturbation. Naval Research Logistics (NRL), 73(4):525–537, 2026. [2] Mohamed Alaggan, Sébastien Gambs, and Anne-Marie Kermarrec. Heterogeneous differential privacy. arXiv preprint arXiv:1504.06998, 2015. [3] Anita Allen. Unpopular Privacy: What Must We Hide? OUP Usa, New York, US, 2011. [4] Noga Alon, Raef Bassily, and Shay Moran. Limits of private learning with access to public data. Advances in neural information processing systems, 32, 2019. [5] Raef Bassily, Kate Donahue, Diptangshu Sen, Annuo Zhao, and Juba Ziani. Data sharing with endogenous choices over differential privacy levels. arXiv preprint arXiv:2602.09357, 2026. [6] Alex Bie, Gautam Kamath, and Vikrant Singhal. Private estimation with public data. Advances in neural information processing systems, 35:18653–18666, 2022. [7] Adam Block, Mark Bun, Rathin Desai, Abhishek Shetty, and Zhiwei S Wu. Oracle-efficient differentially private learning with public data. Advances in Neural Information Processing Systems, 37:113191–113233, 2024. [8] Franziska Boenisch, Christopher Mühl, Adam Dziedzic, Roy Rinberg, and Nicolas Papernot. Have it your way: Individualized privacy assignment for dp-sgd. Advances in Neural Information Processing Systems, 36:19073–19103, 2023. [9] Franziska Boenisch, Christopher Mühl, Roy Rinberg, Jannis Ihrig, and Adam Dziedzic. Individualized pate: Differentially private machine learning with individual privacy guarantees. arXiv preprint arXiv:2202.10517, 2022. [10] Mark Bun and Thomas Steinke. Average-case averages: Private algorithms for smooth sensitivity and mean estimation. Advances in Neural Information Processing Systems, 32, 2019. [11] Syomantak Chaudhuri and Thomas A. Courtade. Mean estimation under heterogeneous privacy: Some privacy can be free. 2023 IEEE International Symposium on Information Theory (ISIT), pages 1639–1644, 2023. [12] Syomantak Chaudhuri and Thomas A. Courtade. Managing correlations in data and privacy demand. In Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security, CCS ’25, page 2384–2398. ACM, November 2025. [13] Syomantak Chaudhuri, Konstantin Miagkov, and Thomas A. Courtade. Mean estimation under heterogeneous privacy demands. IEEE Transactions on Information Theory, 71(2):1362–1375, February 2025. [14] Rachel Cummings and David Durfee. Individual sensitivity preprocessing for data privacy. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 528–547. SIAM, 2020. [15] Rachel Cummings, Hadi Elzayn, Emmanouil Pountourakis, Vasilis Gkatzelis, and Juba Ziani. Optimal data acquisition with privacy-aware agents. In 2023 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pages 210–224. IEEE, 2023. 10
[16] Rachel Cummings, Katrina Ligett, Aaron Roth, Zhiwei Steven Wu, and Juba Ziani. Accuracy for sale: Aggregating data with a variance constraint. In Proceedings of the 2015 conference on innovations in theoretical computer science, pages 317–324, 2015. [17] Edwige Cyffers. Setting epsilon is not the issue in differential privacy. In Proceedings of the 39th International Conference on Neural Information Processing Systems, 2025. [18] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise to Sensitivity in Private Data Analysis, page 265–284. Springer Berlin Heidelberg, 2006. [19] Alireza Fallah, Ali Makhdoumi, Azarakhsh Malekian, and Asuman Ozdaglar. Optimal and differentially private data acquisition: Central and local mechanisms. Operations Research, 72(3):1105–1123, 2024. [20] Vitaly Feldman and Tijana Zrnic. Individual privacy accounting via a renyi filter. In Advances in Neural Information Processing Systems, volume 33, 2020. [21] Nina Gerber, Paul Gerber, and Melanie Volkamer. Explaining the privacy paradox: A systematic review of literature investigating privacy attitude and behavior. Computers and Security, 77:226–261, August 2018. [22] Arpita Ghosh and Katrina Ligett. Privacy and coordination: Computing on databases with endogenous participation. In Proceedings of the fourteenth ACM conference on Electronic commerce, pages 543–560, 2013. [23] Arpita Ghosh and Aaron Roth. Selling privacy at auction. In ACM Conference on Electronic Commerce, pages 199–208, 2011. [24] Jason D Hartline and Tim Roughgarden. Simple versus optimal mechanisms. In Proceedings of the 10th ACM conference on Electronic commerce, pages 225–234, 2009. [25] Zachary Jorgensen, Ting Yu, and Graham Cormode. Conservative or liberal? personalized differential privacy. In IEEE International Conference on Data Engineering (ICDE), pages 1023–1034, 2015. [26] Andrew Lowy, Zeman Li, Tianjian Huang, and Meisam Razaviyayn. Optimal differentially private model training with public data. In Proceedings of the 41st International Conference on Machine Learning, ICML’24. JMLR.org, 2024. [27] Helen Nissenbaum. Privacy as contextual integrity. Washington Law Review, 79, 05 2004. [28] Kobbi Nissim, Salil Vadhan, and David Xiao. Redrawing the boundaries on purchasing data from privacy-sensitive individuals. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 411–422, 2014. [29] Krishna Pillutla, Jalaj Upadhyay, Christopher A. Choquette-Choo, Krishnamurthy Dj Dvijotham, Arun Ganesh, Monika Henzinger, Jonathan Katz, Ryan McKenna, H. B. McMahan, Keith Rush, Thomas Steinke, and Abhradeep Thakurta. Correlated noise mechanisms for differentially private learning. ArXiv, abs/2506.08201, 2025. [30] Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H. Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How to dp-fy ml: A practical guide to machine learning with differential privacy. Journal of Artificial Intelligence Research, 77:1113–1201, 2023. [31] Enayat Ullah, Michael Menart, Raef Bassily, Cristóbal Guzmán, and Raman Arora. Public-data assisted private stochastic optimization: Power and limitations. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 20383–20427, 2024. [32] Jun Wang and Zhi-Hua Zhou. Differentially private learning with small public data. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04):6219–6226, April 2020.
11
A
Preliminaries: Proof of Claim 1
Since the weights sum to 1, we must have 1=
n X
wj =
j=1
n X
η min{ε(j) , τ },
j=1
hence η = 1/sτ . Therefore
min{ε(j) , τ } , sτ and the resulting worst-case mean-squared error is wj =
n
2 1X 2 qτ w + 2η 2 = 2 + 2 . 4 j=1 j 4sτ sτ Taking the infimum over τ > 0 yields the claim. In all the proofs, we use the notation MSEi to refer to the mean squared error obtained when using the threshold estimator of parameter εi : MSEi :=
B
1 2 + . 4nεi (εi nεi )2
Proof of Theorem 1
We now provide the proof of the upper bound given in Theorem 1. Let MSEpriv =
2 1 + 4n1 (n1 ε1 )2
denote the risk of the optimal estimator that uses only the n1 private samples, and let 1 4n2 denote the risk of the empirical mean on the public samples. By definition, MSEpub =
MSE2 = MSEpub . First, observe that using all n1 + n2 samples at privacy level ε1 can only improve over using the n1 private samples alone, since both the sampling variance and the privacy noise decrease. Hence MSE1 ≤ MSEpriv . It follows that MSEthr = min{MSE1 , MSE2 } ≤ min{MSEpriv , MSEpub }. Next, in the public-data regime, the optimal affine estimator is the optimal linear combination of the private estimator and the public estimator as noted in [13], and its risk is MSEaff =
MSEpriv · MSEpub . MSEpriv + MSEpub
b a Indeed, if we combine two unbiased estimators with risks a and b using weights a+b and a+b , the resulting risk is b2 a + a2 b ab = . 2 (a + b) a+b
Finally, for any a, b > 0, min{a, b} ≤ 12
2ab . a+b
Applying this with a = MSEpriv and b = MSEpub , we obtain min{MSEpriv , MSEpub } ≤ 2
MSEpriv · MSEpub = 2 MSEaff . MSEpriv + MSEpub
Combining the two inequalities yields MSEthr ≤ 2 MSEaff , and therefore
MSEthr ≤ 2. MSEaff
This concludes the proof.
C
Detailed Computation of Example
Consider ε = ( 12 , 1), The unique-threshold estimator has mean-squared error given by 1 2 1 2 min + , + = 17/8. 4 · 2 (2ε1 )2 4 ε22 P2 qτ 2 On the other hand, for any τ > 0, MSEaff (ε) ≤ 4s 2 + s2 , where sτ = i=1 min{εi , τ }, and τ τ P2 2 qτ = i=1 min{εi , τ } . It is easy to check that τ = 1 is optimal, and we obtain s1 = ε1 + ε2 = Hence MSEaff (ε) =
3 , 2
q1 = ε21 + ε22 =
1 5 +1= . 4 4
5 8 37 2 5 4 3 2 + 3 2 = 36 + 9 = 36 . 4( 2 ) (2)
Combining the two bounds gives 17 MSEth (ε) 153 8 ≥ 37 = > 2. MSEaff (ε) 74 36
D
Proof of Theorem 2
Let n = n1 + n2 . Because there are only two privacy levels, the Unique-threshold estimator has only two possible choices: either it uses all n data points at privacy level ε1 , or it uses only the n2 data points in the second group at privacy level ε2 . Hence its risk is MSEth (ε) = min{MSE1 , MSE2 }, where MSE1 =
1 2 + , 4n (nε1 )2
MSE2 =
1 2 + . 4n2 (n2 ε2 )2
Next, define
8 . n1 ε21 For two privacy levels, according to [13], the optimal affine risk is given by n1 ε21 + n2 ε22 + 8 4(n ε + n ε )2 , if ε2 ≤ Rε1 , 1 1 2 2 MSEaff (ε) = R , if ε2 ≥ Rε1 . 4(n1 + n2 R) R := 1 +
We show that in both regimes, min{MSE1 , MSE2 } ≤ 4 MSEaff (ε). 13
Case 1: ε2 ≤ Rε1 .
In this case, MSEaff (ε) =
n1 ε21 + n2 ε22 + 8 . 4(n1 ε1 + n2 ε2 )2
We now compare this quantity to MSE1 and MSE2 . If nε1 ≥ n2 ε2 , then n1 ε1 + n2 ε2 ≤ 2nε1 . Moreover, since ε2 ≥ ε1 ,
n1 ε21 + n2 ε22 + 8 ≥ nε21 + 8.
Therefore, MSEaff (ε) ≥
1 MSE1 nε21 + 8 1 = = + . 16n2 ε21 16n 2n2 ε21 4
Hence MSEth (ε) ≤ MSE1 ≤ 4 MSEaff (ε). Otherwise, n2 ε2 ≥ nε1 . Then n1 ε1 + n2 ε2 ≤ 2n2 ε2 , and n1 ε21 + n2 ε22 + 8 ≥ n2 ε22 + 8. Thus MSEaff (ε) ≥
1 MSE2 1 n2 ε22 + 8 = . + 2 2 = 16n22 ε22 16n2 2n2 ε2 4
Hence MSEth (ε) ≤ MSE2 ≤ 4 MSEaff (ε). So in all subcases of Case 1, MSEth (ε) ≤ 4 MSEaff (ε). Case 2: ε2 ≥ Rε1 .
Set ε′2 := Rε1 .
Since MSE2 is decreasing in ε2 , increasing ε2 can only help the threshold estimator. Therefore MSEth (ε1 , ε2 ) ≤ MSEth (ε1 , ε′2 ). On the other hand, once ε2 ≥ Rε1 , the affine optimum saturates: replacing ε2 by ε′2 = Rε1 does not change MSEaff . Thus MSEaff (ε1 , ε2 ) = MSEaff (ε1 , ε′2 ). Since (ε1 , ε′2 ) lies on the boundary of Case 1, we may apply the previous argument to obtain MSEth (ε1 , ε′2 ) ≤ 4 MSEaff (ε1 , ε′2 ). Combining the last three displays gives MSEth (ε1 , ε2 ) ≤ 4 MSEaff (ε1 , ε2 ). Therefore, in all cases, MSEth (ε) ≤ 4. MSEaff (ε) This concludes the proof. 14
E
Proofs for the General Case of Section 6
E.1
Proof of Theorem 3
Assume that 2m − 1 ≤ n. Let εi = 2−(i−1) and ni = 2i−1 Note that the total number of data points is given by m X ni = 2m − 1
for all i ∈ [m].
i=1
datapoints. We first upper bound MSEaff (ε). Let S :=
m X
ni εi .
i=1
For this construction, S=
m X
2i−1 2−(i−1) = m.
i=1
Consider the affine estimator assigning to each user in group i the weight εi wi = . m Then the weights sum to 1, and wi 1 max = . m i∈[m] εi Moreover, m m X 1 X i−1 −2(i−1) 2 ni wi2 = 2 2 2 < 2. m m i=1 i=1 Therefore,
m
1X ni wi2 + 2 MSEaff (ε) ≤ 4 i=1
1 m
2 ≤
5 . 2m2
We now lower bound MSEthr (ε). It suffices to consider thresholds εg+1 = 2−g , g ∈ {0, . . . , m − 1} without loss of generality. For any threshold ε > 0, let nε := {j ∈ [n] : εj ≥ ε} denote the number of selected datapoints. We have that nε = 2g+1 − 1. Thus εnε = (2g+1 − 1)2−g < 2. Now take P = δ0 , so that Xi = 0 almost surely and µP = 0. Then the threshold estimator reduces to 1 µ̂ε (X) = Zε , Zε ∼ Lap , nε ε and so 2 1 E (µ̂ε (X) − µP )2 = > . 2 (nε ε) 2 Therefore, 1 MSEthr (ε) ≥ . 2 Combining the two bounds yields MSEthr (ε) 1/2 m2 ≥ = . 2 MSEaff (ε) 5/(2m ) 5 15
E.2
Proof of Theorem 4
We now prove a comparison lemma showing that for any candidate affine solution with clipping threshold τ , one can choose a threshold whose error is worse by at most a factor min{m2 , Hn2 } ≤ min{m2 , 1 + log n2 }, where n X 1 Hn := k k=1
is the n-th harmonic number. Since the result holds for all τ , it in particular holds for the optimal τ , concluding the proof. Lemma 1. For every τ > 0, there exists a threshold ε∗ > 0 such that 1 2 2 qτ MSEthr ≤ + ∗ 2 2 ≤ min{m2 , Hn2 } + , 4nε∗ (ε ) nε∗ 4s2τ s2τ where
nε∗ := {j ∈ [n] : ε(j) ≥ ε∗ } .
Proof. Fix τ > 0, and let ε̄j := min{ε(j) , τ } for all j ∈ [n]. Reindex the coordinates so that ε̄(1) ≤ ε̄(2) ≤ · · · ≤ ε̄(n) . Since the original privacy vector takes at most m distinct values, the clipped vector (ε̄(j) )nj=1 also takes at most m distinct values. For each j ∈ [n], define uj := (n − j + 1)ε̄(j) . Let
j ∗ ∈ arg max uj ,
∗
ε∗ := ε̄(j ) .
j∈[n]
Then
uj ∗ = (n − j ∗ + 1)ε∗ .
Moreover, all indices j ≥ j ∗ satisfy ε̄(j) ≥ ε∗ , hence also ε(j) ≥ ε∗ . Therefore nε∗ ≥ n − j ∗ + 1, and so
uj ∗ ≤ ε∗ nε∗ .
Next, by maximality of j ∗ , for every j ∈ [n], uj ≤ uj ∗ ,
that is,
ε̄(j) ≤
uj ∗ . n−j+1
Summing over j yields sτ =
n X
ε̄(j) ≤ uj ∗
j=1
Thus
n X
n
X1 1 = uj ∗ = Hn uj ∗ . n−j+1 k j=1 k=1
sτ ≤ Hn uj ∗ ≤ Hn ε∗ nε∗ .
We also claim that sτ ≤ m uj ∗ . Indeed, since (ε̄j ) takes at most m distinct values, the sum sτ can be decomposed into at most m blocks, each contributing at most uj ∗ by maximality. It must then be the case that sτ ≤ m uj ∗ . Combining the two estimates, we obtain sτ ≤ min{m, Hn } uj ∗ ≤ min{m, Hn } ε∗ nε∗ . 16
It follows that
2 2 ≤ min{m2 , Hn2 } 2 . (ε∗ )2 n2ε∗ sτ
For the sampling term, every selected point satisfies ε̄(j) ≥ ε∗ , so qτ =
n X
(ε̄(j) )2 ≥ nε∗ (ε∗ )2 .
j=1
Combining this with
sτ ≤ min{m, Hn } ε∗ nε∗
gives nε∗ (ε∗ )2 1 qτ ≥ ≥ , 4s2τ 4s2τ 4 min{m2 , Hn2 }nε∗ that is,
qτ 1 ≤ min{m2 , Hn2 } 2 . 4nε∗ 4sτ
Summing the two bounds yields 1 2 + ∗ 2 2 ≤ min{m2 , Hn2 } 4nε∗ (ε ) nε∗
qτ 2 + 2 4s2τ sτ
.
Since MSEthr is the infimum over all thresholds, it is at most the left-hand side for this choice of ε∗ , which proves the claim.
17