Sum Estimation under Personalized Local Differential Privacy
Authors: Dajun Sun
Wei Dong
Yuan Qiu
Ke Yi
Graham Cormode
Venue: NeurIPS 2025 poster ()
Keywords: Differential Privacy
Sum Estimation
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: People have diverse privacy requirements. This is best modeled using a personalized local differential privacy model where each user privatizes their data using a possibly different privacy parameter.  While the model of personalized local differential privacy is a natural and important one, prior work has failed to give meaningful error bounds. In this paper, we study the foundational sum/mean estimation problem under this model. We present two novel protocols that achieve strong error guarantees. The first gives a guarantee based on the radius of the data, suiting inputs that are centered around zero. The second extends the guarantee to the diameter of the data, capturing the case when the points are situated arbitrarily. Experimental results on both synthetic and real data show that our protocols significantly outperform existing methods in terms of accuracy while providing a strong level of privacy.

Sum Estimation under Personalized Local Differential Privacy
Dajun Sun'
Wei Dong2* Yuan Qiu Ke Yi Graham Cormode'
Hong Kong University of Science and Technology NNayyang Technological University
Southeast University University of Warwick
dsunad@connect... surrct..ust.. .kk wei_dong@ntu. edu.sg yuanqiuβseu. edu.
yikeêcse. ust.hk hk cormode@@arwicck ac, uk
Abstract
People have diverse privacy requirements. This is best modeled using personal- ized local differential privacy model where each user privatizes their data using a possibly different privacy parameter. While the model of personalized local differential privacy is a natural and important one, prior work has failed to give meaningful error bounds. In this paper, we study the foundational sum/mean estimation problem under this model. We present two novel protocols that achieve strong error guarantees. The first gives guarantee based on the radius of the data, suiting inputs that are centered around zero. The second extends the guarantee to the diameter of the data, capturing the case when the points are situated arbitrarily. Experimental results on both synthetic and real data show that our protocols signif- icantly outperform existing methods in terms of accuracy while providing strong level of privacy.
Introduction
Sum/mean estimation under differential privacy (DP) is fundamental building block in privacy- preserving machine learning 51.. statistical analysis (14), and query processing [19 22]. Among the various models of DP, the local model (LDP) has attracted much attention, assumptions and is easy to implement in distributed setting. In this model, each user privatizes their own data, usually by adding some noise, and sends the noisy result to an untrusted analyst. However, existing work on LDP assumes that all users adopt the same privacy parameter (s p) when privatizing their data, which is an overly simplistic assumption. In practice, people have diverse privacy requirements: Conservative users might be unwilling to share data, while more liberal ones are happy to contribute. Indeed, many apps give users the option of sharing or not sharing their data, which can be considered the most coarse-graine -raiined personalized privacy.
makes no trust
In this paper, we consider a fine-grained and more quantitative personalized LDP model where each user is allowed to set their privacy parameter 4 (u) to any positive real number, with smaller values corresponding to higher privacy requirement.
particular, we adopt zero-concentrated DP, where (u) corresponds to the parameter (the formal definition is given in Section B). We study the sum estimation problem under such a setting: Let 2 {Wu,.... un be the set of users. We model the given instance
function I U [B]d where [B] {0.... (o...., B) and [[(()) l| B for all u, i.., each user u holds a d-dimensional non-negative intuger-valued vector I(u) in a ball of radius B. This is without much loss of generality: real-valued vectors can be translated, scaled, and rounded with negligible precision loss as long as B is sufficiently large, say, 232 In this paper, we focus on estimating the core function of Sum(I) Σueu I(u); mean estimation results follow easily.
(())
"Corresoonding authors.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

In an LDP protocol, each user privatizes their own data by themselves using local randomizer, so it automatically translates to this personalized setting. For instance. each user can apply the Gaussian mechanism to I(u), which adds a Gaussian noise with scale O
17
to each coordinate [TO 38 35
(()))
However, this simple solution may fail miserably. First, as B is a priorí upper bound on the norm, it must be set conservatively large, resulting in excessive noise. Meanwhile, the norms of data in typical instances are much smaller than B, so some instance-specific error, e.g., one that is proportional to the radius rad(I)= = maX [[(2]l22 222 or the diameter w(I) = a, Et/ [[[(us) - ((ug)]l2 would be more desirable. Second, this solution is susceptible highly conservative users with very small & ((u). who may just as well be removed from the analysis.
An effeetive approach to addressing both issues is to truncate/clip the data before adding noise. Given a threshold т, we truncate the data on the lg norm, i.e., set [u,, r) = min (()((l, 7) [[x))ll2" Then satisfies the LDP requirement for u. However, is
[())
adding a Gaussian noise with scale O (m)
not clear how select a good 7 in the personalized LDP model. More critically, even if a best could be found, applying the same 7 to all users would still yield sub-optimal results. Consider the following 1D example.
Example 1.1. Suppose user i has (scalar) data I(w.) = i with privacy parameter (u:) (n + +1 /)²/n, for i = I,...,I, n, representing a typical case where users with larger data values also have stronger privacy requirements. Directly applying the Gaussian mechanism corresponds to B, and incurs total error of above returns min (inn[(())T)) + (O, @(u) Using the notation (x))+ == max (2, 0), the total error is
O(ByR). More generally, the truncation mechanism
E (I... +)+
(wz)²
where the first term is the truncation bias and the second is the total error of the noise. Even with the optimal 7 = n ni (which is not clear how to obtain without knowledge of the users' private data), both the bias and the noise term are On22/2)
In Section 4 we present a protocol that achieves an &a error of
minseR 20 (IZm. (IT(w)l2- /v)(()
T(x) I(u)]la
((VVnd)
(2)
in d dimensions. It has a similar form to (I. but with two key differences: First, instead of uniform truncation threshold 7 for all users u, we make it proportional to (Q) Intuitively. this allows us to obtain more information about more liberal users. truncates more aggressively on conservative users (such as u, in Example 1.1p, but this also reduces the noise they introduce to the final estimate. Second, our protocol automatically selects the optimal scaling factor s, in one round and in a DP fashion. These two improvements allow us to reduce the error significantly. When applied to the instance in Example the uniform-privacy LDP setting where (-)) p. degenerates into (rad((I) /dd/p)) achieved
1.1
2 is ((n4/3) achieved by n/5/6, Also, note that in
denotes the k-th largest &a norm in I. This matches the dependen bound of the LDP protocol [18]. addition to the &g error, our protocol also achieves a similar error guarantees in terms of loc. which allows us to solve some related problems like frequency estimation, range counting, and quantiles in the personalized LDP model.
by |
| (ddj)) /vP, where
(k) ||]]|[=)
2
Example 1.2. Next, consider variant of Example 1.1 where the users' data are clustered away from the origin: I(u;) = B/2 + for i = 1,..., n (assuming B >> n.) On this instance, the error bound becomes ((B no better than the naive Gaussian mechanism.
In Section 5 we present another protocol that achieves the following diameter-dependent error bound:
Ô (min.eR2o 20
1 (s (w)/2 < (I)) + svndd
Since (I) < 2 (I) on any instance I, while (I) could much smaller than rad such a diameter-dependent bound is more preferable, especially for datasets that are clustered away from
'The Ô notation hides logarithmic factors.
2

---

the origin. For the instance in Example 1.2 we have (I) = while rad (T) = B + and (3) is Onn4/3), matching what we can achieve on the instance in Example 1.1
Furthermore, in the
uniform- uniform-privacy LDP setting. (3) degenerates into (w((), //n/p),, achieved by wII) 22/p.
matching the diameter-dependent bound of the LDP protocol in [8].
Related Work
Providing personalized privacy protection is a well motivated problem due to the diversity of users. In fact, this issue was studied even before DP became the primary privacy model. For example, Xiao and Tao [B4] defined notion of personalized privacy in the context of k-anonymity, which was later extended to other related privacy models 337
30]. However, these models do not provide privacy
protection as rigorous as differential privacy 26 39
The model of personalized differential privacy (also known heterogeneous differential privacy) was initialized under the central model of DP by Jorgensen et al. (20] where a trusted central data curator holds and analyzes users' data. They designed a general-propose sampling mechanism and extended the inverse sensitivity- bbase exponential mechanism (27 6 to PDP, but without formal guarantees on the utility. Recent work by Sun et al. [31 provides the first result on sum estimation and private query answering with rigorous utility guarantees. Some baseline ML problems such as support vector machine and linear regression have been studied in (24). Additionally, [[5] studies how to track the privacy consumption of each user over multiple queries.
Personalized differential privacy under the local model has also been studied for federated learning 25 36), point-of-interest recommendation 77,, mean estimation (35) and statistical histograms (38 However, these works simply use the naive Gaussian mechanism that adds a noise with scale B
V (w) for each (v)) For this to succeed, they have to use small B and assume that the norms of all data are much smaller than B.
There are also some other interesting papers that do not study the PDP model directly, but nevertheless have a "personalized" flavor. For example, [33 28 consider personalized privacy setting where each user determines which part of its data is public or private, and then provide (standard) DP protection only on the private part. Zhang et al.
40 points to another interesting direction called (29] studies the notion called per-record DP, where each user has different privacy level depending the content of his record.
multi-analyst DP. Recent work by Seeman et al.
3 Preliminaries
We consider the local model of differential privacy where each user retains their data I(u), and only sends ([)))) to the analyzer, where MM.) is called local randomizer, which must satisfy (local) DP. Each user u has a possibly different privacy parameter (u),, where l - R is called the privacy specification, known to the analyzer. Define Pmin == min (uu) and Pmax := max (u))
There are several versions of DP. In this paper, we adopt zero- Cor-Cooncettrated Differential Privacy (CDP) (.) which is more suitable for high-dimensional data. naturally fits the personalized setting: Definition 3.1 (Personalized local zCDP (PLCDP)). For a given privacy specification C a local randomizer M satisfies O- PP-CLDP if for any user u, any I(u), I'()), and any 1,
Da ([(I())))M(((((
S a a (uu,,
where Da (-Il-) denotes the a- RéRén divergence between the distributions of the two random variables.
is known that the privacy guarantee provided by CDP is sandwiched between that of pure DP and approximate DP, with their parameters roughly related for achieving PLCDP adds Gaussian noise with proper scale to each coordinate of the data:
θ(vp) D. The canonical mechanism
Lemma 3.1 (Gaussian Mechanism 9). Under the constraint that [[[(x)]|2 B for all u, the
B² randomizer M that outputs M([(u)) = I(u) +N (0, 24(n) -lxx)) satisfies -PPLCDP.
In one-round protocol, the analyzer A collects M()(w)) for all u E and outputs (((M(I(() (w))).) It is also possible for a protocol to run over multiple rounds, in which case the privacy consumption
3

---

accumulates. For simplicity, we only state and prove (in Appendix A.1 1 à 2-round version; extension more rounds is straightforward.
Lemma 3.2 (Adaptive composition), Let M1(-) and M2( y) be local randomizers such that (-) satisfies & 1--PLCDP and M2( y) satisfies 22-PLCDP for any y. Then the 2-round protocol that collects (Mi(I(u)) in the first round and (M)([(u), v(u)), in the second round satisfies (41 + -PLCCPP where y(u) may depend on (Mi (M))),))))
Note that if M2(:.3) does not depend on y, then the composition is non-adaptive, and the two randomizers be run in the same round.
We also need the following tail bound of the Gaussian distribution for utility analysis:
Lemma 3.3 (Gaussian tail). X ~ NNO o then Pr [ o 22 3 S B for any 0 <<
Radius-Dependent Protocol
In this section, we present one-round PLCDP protocol that achieves the following guarantee: Theorem 4.1. For any i the local randomizer defined in Algorithm satisfies 4-PLCDP. For any B, the analyzer run Algorithm 2 to obtain an estimate of Sum(I) with an Eg error at most
(
min sERsO
Σ [ s/20(u)
I(u)
+ 4
2ndtin
21d
(4)
[[u
B
and an loo error at most
(E - 2b)( +
I(u)
21d
min
+ 4s4
2nthn
(5)
eER
[[u)]l2
with probability at least
B, where = log (B
Amax
Below, we describe randomizer and analyzer, while giving some intuition why they achieve the error bounds Theorem 4.1, with the formal proof in Appendix A.2
Our local randomizer invokes the truncation mechanism on user u with truncation threshold Tuu) $ 22). order find an optimal up to a constant factor, we try logarithmic number of possible values from Smin
/2pmin" More precisely, letting t we try 8; 2 Smin for i 0, 1, ...,, i.e., invoke instances of the
to 8max
/2praax
log
Smaa
log
B
Sant
Pmiin
truncation mechanism concurrently with (u) = 2 v
((u), Pmaae" while splitting the privacy budget using the non-adaptive version of Lemma 3.2 The details are given in Algorithm T
After receiving the noisy truncated vectors from all users, the analyzer adds them up respectively. remains for the analyzer to pick one out of the t noisy truncated sums that achieves near-optimal technique [13] For each dimension, we subtract a term proportional the noise scale from each noisy sum and take the maximum. The details are given in Algorithm| 2 The intuition that this can find an optimal is as follows. We know that that the optimal should balance the bias and noise. A small introduces large bias but small noise, it is unlikely to be the maximum. A large has small bias but large noise, so subtracting a term proportional to the noise scale turns into an underestimate. Between these two extremes, the underestimate where the bias matches the noise has the best chance to become the maximum.
error. For this, we use a "subtract-mar
Remark.
As stated, the randomizer in Algorithm sends out message of size Ô(d). Using the lossless compression technique in [16), this be compressed to ((1) with negligible loss in the privacy and utility. On the other hand, instead of reporting a value for all 8,, each user may sample only one scale and send the corresponding truncated value. This will not affect the asymptotic
accuracy of the algorithm but can reduce communication by factor of log
Panas B.
Omin
Below, we discuss two applications of our radius-dependent protocol, which will also be useful in our diameter-dependent protocol in Section

---

Algorithm 1: LocalSum-R (Randomizer)
Input: I(u). 2, B,
1 f- log
Panax B
Pmin
for i f .....,t do
Let 8 + PPmaa Tz(u) t s /2/20(1)))
Define [uu min (u))le Ti Tu) I(]
2
[u) [(u)) + (0, of t- ldxa);
end
7 return (i.(
Algorithm 2: LocalSum-A A (Analyzer)
Input: (I.) 4, B, B,
t + log (V Prnxx B
Pmin
for +- 0,1,.... do
f V2pmms
Sum, (I) + SI) - 8: 2nthh / 2td 1;
5 &end
return Sum such that Sum max/max, Sum, (T) 0}, where Sum; is the jth
coordinate of (I);
Histogram (frequency estimation). In the histogram problem, each user holds an element I(u) e [B], and the goal is to obtain private histogram from which we can estimate the number of occurrences of any i E [B). By taking I(uu as one-hot vector in B dimensions, the histogram problem becomes sum estimation problem, and the foo error bound (5) provides a guarantee on the maximum error on the estimated frequency of any i E [B]. For this special case, (5) can be further simplified as:
Corollary 4.2. Given 4, B, B, I(u) E [B), Algorithms 7 and return private histogram such that for all [B), the frequency of i can be estimated with error at most
o ky n log
log B log fraax
Pmax log
Pmin
B
where k is the smallest index such that Et_ (uu)) non-decreasing order of &b (u:).
2
assuming the users are ranked in the
Note that when (u) p. we have 1p, and the error degenerates to ((/n/p). matching the ervor bound in the standard LDP model 22
Range counting and quantiles. The range counting problem has the setup above, but are interested in counting the number of elements in any range [L, R| C [B]. Note that the histogram problem the special case where L R. The range counting problem can be reduced to log B instances of the histogram problem by decomposing the universe [B] in hierarchical fashion. The following theorem summarizes the result, with details given Appendix A.3 A.4
Theorem 4.3, Given & 8, B, I(u)= E [B), with probability at least 1 - B, all range counting queries over [B] can be answered with error
log log Pman
k n log
Pmax Punin
log
Pmin log*
(6)
under 4-PLCDP, where k is as defined in Corollary 4.2

---

Finally, using range counting queries in the form of 11, we can do a binary search on [B] to find any quantile (e.g,, the median) upproximately. Then (6) becomes the rank error of the returned quantile (e.g., the returned median is ranked at 2 +
5 Diameter-Dependent Protocol
The protocol above achieves error that scales with the radius, i.e., the maximum &g norm, which only works well for datasets that are around the origin. For the general case, it is more desirable to achieve error that scales with the diameter (II) rather than rTd( In this section, we design such a PLCDP protocol, although it requires two rounds.
Our solution is to first shift the dataset towards the origin such that the radius of the shifted dataset is roughly the diameter of the original dataset. That is, the shifted dataset should be concentrated around the origin, and it preserves the diameter of the original dataset. Then we can apply the previous (radius) sum algorithm to the shifted dataset and shift the result back.
To achieve this goal, we need to find an interior point (in our case, the median) on each dimension independently, using the PLCDP quantile selection algorithm described above. Since this is done on all the d dimensions, privacy parameters need to be further divided into parts. Below is the guarantee that follows directly from Theorem 4.3
dlog B log aima
"min k2 log* B for some constant with probability at least 1 3, we can find an interior point in each dimension while preserving -PPI.DP
Corollary 5.1. Given 3, 4 I(u) [B] if ed log fuax log B
Puiin
However, in high dimensions, doing such a shift in each dimension may 'expand' the dataset and result in a radius of ((Vdww))) Consider the following example. Example 5.1. Consider dataset consisting d unit vectors in d-dimensional space, the diameter is v2. Obviously, in every single dimension 1 is an interior point, but shifting with (1, I,... 1) results in radius of Vd-L.
The reason is that the values in each dimension may be skewed. In order to preserve the diameter of I in high dimensions, we perform random rotation to 'balance' the values before estimating the median. The rotation is done by f(u) == H HDI(w) (u), where H is the x d Hadamard matrix, and D d x d diagonal matrix whose diagonal entry is independently and uniformly drawn from { 1- +1] }. This process can be done via public randomness and does not need additional communication. The following Lemma (3) says the rotated data is likely to be more 'balanced':
Lemma 5.2
Let H and D be defined as above. Then, for any x E Rd and any B O,
4d
Pr
2 ||0|||2
2 log
< B.
For any pair of users u1, u2, by setting æ I(w1)-I(wuu) the above lemma says with high probability, the maximum distance between their rotated data each dimension [i(u1) I(x)) | is greater
than /2 log B [[(()) - 1( To make this hold simultaneously for all pairs of points, we apply a union bound and the distance bound will become O
O //og nd (T)). thus the radius of the shifted B
data i, is ((Vdw(I). After estimating the sum of the rotated data, should rotate this result back by multiplying (HD) which decreases the & norm by factor of Va so the additional Vd factor here will be eliminated finally.
The whole process of sum estimation can be formulated as follows:
1. Each user does a random rotation on their data using public information H, D, denote the rotated data as i(u).
2. Apply the median selection protocol on each dimension using the technique described in Section 4 with privacy & and failure probability 3 Note for original data such that
[[u)]]2 B, the rotated data will have [[(u))]2 - dB and its coordinate will lie in (dB).

---

3. Analyzer receives messages from users and returns the estimated median of each dimension; denote the median vector as m E [dB] where the jth coordinate m []] represents the estimated median of dimension j.
4. Each user shifts the rotated data towards the median and splits the shifted data into neg- ative/positive parts. Let the shifted data be [u = I(u) - m and define the nega- tive part I,- (u) min(1. 0) (on each coordinate) whereas the positive part is + (u) (a), (on each coordinate). This is to ensure each part contains only non-negative values as required by our sum estimation protocol.
5. Each user applies the sum protocol described in Section on i, and I separately, with privacy budget 4 and failure probability 4.2 sending the results to the analyzer.
6. The analyzer determines the best estimation of negative/positive part, denoted as Sum(i,) and Sum(I!). then combines the information above to give final sum estimation
Sum(I) (HD)-* (Sum(t;) Sum(t,) + n m
In Appendix A.5 we prove the following error bound of the protocol above:
dlog B log Roox k2 log' B for some large
Theorem 5.3. Given 4, B, B, d, assume 2 cd log Paus log
Pmim
enough constant Then with probability at least 1 B, the &g error of sum estimation is greater than
(V
0
nd log B
min sERgo
I(s <
td 3 ndtln
where:
[log dB,
Piaxx
Pmii
Experiments
In this section, we report the experimental results comparing new protocols against the baseline method, which adds Gaussian noise of scale x after truncating each user's data by a uniform
/
threshold r. As there is currently no method for choosing a good т, we give this baseline method the unfair advantage of using the optimal (selected in non-private manner). We call this baseline the Naive Optimal. Note that this baseline is always no worse than the naive method that adds a Gaussian
noise of scale /o(u) without truncation, which is used in prior work [25] 36] 35 38), since the
latter is the special case of the former with r = B. The corresponding codes and data are provided in the GitHub repository 2
6.1 Setup
Datasets. We performed experiments on both synthetic and real-world datasets. Synthetic datasets are used to demonstrate the scalability of our mechanisms and to examine the effect of different input distributions, varying numbers of users n, and different data dimensions d. Specifically, for users' data (2z) we tried two different distributions: In Normal Data, each coordinate of each user's 's data is independently drawn from normal distribution with mean 1,000 and standard deviation 100. The sampled values are rounded to the nearest integer. In Uniform Data, each coordinate of each user's s data is uniformly drawn from {0, I.., 1000). For both input distributions, we examined various user counts 103. 10 10a, 109, with default of 103, We also tested different dimensionalities E {32, 64, 128, 256, 512). with a default value of 128. We set B 1,000,000, which a sufficiently large upper bound for all datasets.
The real-world data we used the MNIST (train) dataset 12], which consists of 60,000 images of handwritten digits, where each image is represented by a vector of dimension 28 28 784 and each coordinate an integer ranging from 255. We perform sum estimation for each digit separately and treat each image an individual's 's data. In order to apply the Hadamard matrix, we
7

---

add zeros to the end of each vector to pad the dimension to d = 1024 and we set B = 255vd = 8,160.
Data
Result 22 Norm
Technique
Relative b Er)or(())
Time(s)
Nuive
51.24
0,02
Normal Data
9.04 x 10
Radius Sum
9.75
0.93
Diameter
0.14
Naive
52.67
0.02
Uniform Data
5.65 x
Radius Sum
7.39
1,03
Diameler Sum
3.10
16.50
Naive
85.77
0.02
MNIST Digit
4.39 107
Radrus
41.84
0,92
Diameter Sum
6,54
25.40
Table 1: Summary results under default setting, where n 10t and = 128 for synthetic data.
where we randomly divide the users into two groups: conservative, representing users with high privacy concern; and liberal, representing users with moderate concern. The fraction of users in the conservative and liberal groups are set to 0.05 and 0.95, respectively. The privacy level for the users in the conservative and liberal groups are drawn uniformly random from the ranges [1_ and [1. 100), respectively, which are reasonable values in the local model of DP according to [
Privacy Specification. We used similar privacy specification in
Experimental Parameters. All experiments are done on desktop PC equipped with an M2 Pro CPU and 16GB memory. We set the probability parameter 3 = 0.1. Each experiment is repeated 20 times and we record the average running time and relative error compared to the true sum. We discard the top/lower 10% errors before computing the average error.
Nalve Optimal
Radius Sum
Diameter Sum
Relative Emar
10
10->
10
10'
-0
10
10
10a
10"
Normal Data
Uniffrm Data
Varying number of users
Figure 1: Effect of varying number of users the relative & error of different mechanisms.
6.2 Results
summarrzes the results of different mechanisms under the default setting. Our diameter sum mechanism achieves the best performance with acceptable relative error in all cases. In contrast, the naive mechanism always provides poor utility. On the other hand, our diameter sum mechanism always provides improvements compared to the radius sum mechanism, and this improvement becomes essential on the MNIST dataset, whereas the radius sum has a more then 40% error thus loosing utility. Regarding the running time, although there is a large gap between the total running times different mechanisms, all them can be efficiently executed on commodity hardware.
Synthetic Data. Figure shows the results on the synthetic data varying number of users n. As grows up, the relative eтrоr of our radius/diameter sum mechanism decreases roughly linearly in yn. This is because for a fixed input distribution and privacy specification, the optimal noise scale chosen by our algorithms roughly remains unchanged. So the error stated Theorem 4.1 and Theorem 5.3 roughly grows at the rate of vn. Since the E2 norm of Sum is proportional to n, thus the relative error will decrease proportional to vn. Meanwhile, the relative error the naive mechanism roughly remains as a constant when n changes. This is because as n grows up, the portion of users with small privacy parameter (thus high error) is fixed. So the total error also grows linearly in and the relative error remains unchanged.
8

---

Figure 2 shows the effect of varying data dimension d. We can see as d increases, the enror of all mechanisms also increase. The intuition is that the optimal noise scale 8 is proportional to vd. Since the noise vector has d dimensions, the &g norm of each noise vector proportional to d. As the & norm (T proportional to vd, the relative error roughly increases at the rate of Vd.
Nalve Optimal
Radius
Diameter Sum
10
10a
Relative 12 Error
10-1
10-1
10-1
10"1:
32
64
128
256
512
32
64
12.
256
512
Normal Data
Unitorm Data
Varying number of dimensions
Figure 2: Effect of varying input dimension d on the relative & error of different mechanisms.
MNIST. Figure 3 shows the accuracy and running time of different mechanisms the MNIST dataset. Similar to before, the naive mechanism provides the worst performance with almost 100% relative error which makes it meaningless. However, this time our radius sum mechanism also provides poor utility. This is because each digit in the MNIST dataset has its own pattern, thus an error that scales with the radius of the dataset indeed significantly overestimates the sensitivity of each digit and leads to an undesirable error. Fortunately, our diameter sum algorithm is capable of automatically finding the intrinsic pattern of each digit, which the median vector we find in step 3 of the algorithm. Thus it can provide a small error that only scales the diameter of each digit (the variety within the same class). The result different digits varies slightly, but the diameter mechanism provides high accuracy in general. All these mechanisms can be executed efficiently.
Naive Optimal
Radius Sum
Diameter Sum
107
Relative 12 Error
Time(s) 10-1
3
2
6
Digits
Digits
Different digits
Figure 3: MNIST dataset, different digits.
7 Limitations and Future Directions
In this paper, we have considered personalized LDP model where the privacy parameter, i.e., ((u) is known to the analyst. In situations where there is direct relationship between the user's data and their privacy requirement, such as income data, revealing (u) would breach privacy. There have been some recent proposals 4 [29] on how to model such setting where both the data and privacy parameters are to protected, and would be interesting to see if our techniques can be extended to this case.
Another interesting direction is to provide confidence interval (confidence regions in high dimen- sions), instead of just sum estimate, which would allow the analyst to make decisions with more statistical reliability. Note that the confidence interval itself must also be differentially private. For the naive Gaussian method, this is easy since the analyst knows precisely the distribution of the noise. However, this is more challenging for our method, and any truncation based approach, because the truncation bias depends on the private data.

---

Acknowledgments and Disclosure of Funding
This work is supported by HKRGC under grants 16205422, 16204223, and 16203924. Wei Dong supported by the NTU-NAP Startup Grant (024584-0000) 100000000011))- and the Singapore Ministry of Education Tier I Grant (RG19/25). Yuan Qiu supported by the Start-up Research Fund of Southeast University under grant RF10280 028625150. Graham Cormode is supported by in part by EPSRC grant EP/V044621/1. We would also like to thank anonymous reviewers who have made valuable suggestions on improving the presentation of the paper.
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[2] Alessandro Acquisti and Jens Grossklags. Privacy and rationality in individual decision making, IEEE security privacy, 3(1):26-33, 2005.
[3] Nir Ailon and Bernard Chazelle. The fast johnson-lindenstrun transform and approximate nearest neighbors. SIAM Journal computing, 3911:002-322, 2009.
[4] Mohammad Alaggan, Sébastien Gambs, and Anne-Marie Kermarrec. Heterogeneous differential privacy. arXiv preprint arXiv: I 504406998, 2015.
[5] Pathum Chamikara Mahawaga Arachchige, Peter Bertok, Ibrahim Khalil, Dongxi Liu, Seyit Camtepe, and Mohammed Atiquzzaman. Local differential privacy for deep learning. IEEE Internet of Things Journal, 7(7):5827-5842, 2019.
[6] Hilal Asi and John C Duchi. Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms. Advances neural information processing systems, 1411166661117, 2020.
[7] Ting Bao, Lei Xu, Lichuang Zhu, Lihong Wang, and Tielei Li. Successive point-of-interest recommendation with personalized local differential privacy. IEEE Transactions on Vehicular Technology, 70(10):10477-10488 2021.
[8] Abhishek Bhowmick, John Duchi, Julien Freudiger, Gauray Kapoor, and Ryan Rogers. Pro- tection against reconstruction and its applications in private federated learning. arXiv preprint arXiv.1812.00994, 2018.
[9] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of cryptography conference, pages 635-658. Springer, 2016.
[10] Rui Chen, Haoran Li, A Kai Qin, Shiva Prasad Kasiviswanathan, and Hongxia Jin. Private spatial data aggregation the local setting. 2016 IEEE 32nd International Conference on Data Engineering (ICDE), pages 289-300. IEEF, 2016.
[11] Graham Cormode, Cecilia Procopiue, Divesh Srivastava, Entong Shen, and Ting Yu. Differ- entially private spatial decompositions, 2012 IEEE 28th International Conference on Data Engineering, pages 20-31. IEEE, 2012.
[12] Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-142, 2012.
[13] Wei Dong, Juanru Fang. Ke Yi, Yuchao Tao, and Ashwin Machanavajhala. R2t: Instance- optimal truncation for differentially private query evaluation with foreign keys. In Proceedings of the 2022 International Conference on Management of Data, pages 759-772, 2022.
[14] Cynthia Dwork and Adam Smith. Differential privacy for statistics: What we know and what we want to learn. Journal of Privacy and Confidentiality, 1(2), 2010.
[15] Hamid Ebadi, David Sands, and Gerardo Schneider. Differential privacy: Now it's getting personal. Acm Sigplan Notices, 500 (0(1):69-8 81, 2015.
10

---

[16] Vitaly Feldman and Kunal Talwar. Lossless compression of efficient private local randomizers. In International Conference on Machine Learning, pages 3208-3219, PMLR, 2021.
[17] Bugra Gedik and Ling Liu. Protecting location privacy with personalized k-anonymity: Archi- tecture and algorithms. IEEE Transactions on Mobile Computing, 7(1):1-18, 2007.
[18] Ziyue Huang, Yuting Liang, and Ke Yi. Instance-optimal mean estimation under differential privacy. Advances in Neural Information Processing Systems, 14:25993-26000) 2021.
[19] Noah Johnson, Joseph P Near, and Dawn Song. Towards practical differential privacy for sql queries. Proceedings of the VLDB Endowment, 11(5):52--33, 2018
[20] Zach Jorgensen, Ting Yu, and Graham Cormode. Conservative or liberal? personalized differential privacy. In 2015 IEEE 31St international conference on data engineering, pages 1023-1034. IEEE, 2015.
[21] Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals, 2017.
[22] los Kotsogiannis, Yuchao Tao, Xi He, Maryam Fanaeepour, Ashwin Machanavajjhala, Michael Hay, and Gerome Miklau. Privatesql: a differentially private sql query engine. Proceedings of the VLDB Endowment, (((1))11711-1844 2019.
[23] Tejas Kulkarni, Graham Cormode, and Divesh Srivastava. Answering range queries under local differential privacy. arXiv preprint arXiv: 1812 2018
[24] Haoran Li, Li Xiong, Zhanglong Ji, and Xiaoqian Jiang. Partitioning based mechanisms under personalized differential privacy. In Advances in Knowledge Discovery and Data Mining: 21 Pucific-Asia Conference, PAKDD 2017, Jeju, South Korea, May 23-26, 2017, Proceedings, Part I 121, pages 615-627. Springer, 2017.
[25] Junxu Liu, Jian Lou, Xiong, Jinfei Liu, and Xiaofeng Meng. Cross-silo federated learning with record-leve personalized differential privacy. arXiv preprint 162551
[26] Ashwin Machanavajjhala, Daniel Kifer, Johannes Gehrke, and Muthuramakrishman Venkita- subramaniam. 1-diversity: Privacy beyond k-anonymity, ACM Transactions on Knowledge Discovery from Data (TKDD), 1(1): es, 2007.
[27] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pages 94-103. IEEE, 2007.
[28] Xuying Meng, Suhang Wang, Kai Shu, Jundong Li, Bo Chen, Huan Liu, and Yujun Zhang Towards privacy preserving social recommendation under personalized privacy settings. World Wide Web, 22:2853-28811 2019.
[29] Jeremy Seeman, William Sexton, David Pujol, and Ashwin Machanavajjhala. Privately an- swering queries on skewed data via per-record differential privacy. Proc. VLDB Endow. 1711))3138-3150, 2024.
[30] Yanguang Shen, Hui Shao, and Yan Li. Research on the personalized privacy preserving distributed data mining. In 2009 Second International Conference on Future Information Technology and Management Engineering, pages 436-439, IEEE, 2009.
[31] Dajun Sun, Wei Dong, Yuan Qiu, and Ke Yi. Personalized truncation for personalized privacy. Proceedings of the ACM on Management of Data, 2(6):1-25 2025.
[32] Dajun Sun, Wei Dong, and Ke Yi. Confidence intervals for private query processing. Proceedings of the VLDB Endowment, 173))373-385, 2023.
[33] Wei Wang, Lei Chen, and Qian Zhang. Outsourcing high-dimensional healthcare data to cloud with personalized privacy preservation. Computer Networks, 88:136-148, 2015.
[34] Xiaokui Xiao and Yufei Tao. Personalized privacy preservation. In Proceedings of the 2006 ACM SIGMOD international conference on Management of data, pages 229-240, 2006.
11

---

[35] Qiao Xue, Youwen Zhu, and Jian Wang. Mean estimation over numeric data with personalized local differential privacy. Frontiers of Computer Science, 16:1-10, 2022.
[36] Ge Yang, Shaowei Wang, and Haijie Wang. Federated learning with personalized local differ- ential privacy. In 2021 IEEE 6th International Conference Computer and Communication Systems (ICCCS), pages 484 489. IEEE, 2021.
[37] Xiaojun Ye, Yawei Zhang. and Ming Liu. A personalized (a. k)-anonymity model. In 2008 The Ninth International Conference Web-Age Information Management, pages 341-348 IEEE, 2008.
[38] NIE Yiwen, Wei Yang, Liusheng Huang, Xike Xie, Zhenhua Zhao, and Shaowei Wang. A utility-opimiized framework for personalized private histogram estimation, IEEE Transactions on Knowledge and Data Engineering. 31(4):655-66) 669, 2018.
[39] Mingxuan Yuan, Lei Chen, and Philip S Yu. Personalized privacy protection in social networks. Proceedings of the VLDB Endowment, 4(2):141-150) 2010.
[40] Shufan Zhang and Xi He. Dprovdb: Differentially private query processing with multi-analyst provenance. arXiv preprint 1rXXi:2309.1024000 2023.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
In Section 7 we discuss the limitations of this paper and possible future
directions.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model cell-speciiiiatinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: All theorems inside this paper clearly state their assumptions and the complete proof' be found in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
In S clearly state the experiment settings improve reproducibility, In the meanwhile, all the experimental results align with our theoretical analysis, thus supporting our claims.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
14

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification:
Data,
code, and instructions
are
provided
at
http://giihbcoomm/sssmiiialllppp
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed run reproduce the results. See the NeurIPS code and data submission guidelines (https
//ipss.ccppbbll.. wwtpccccpppccccceecce. guides/eee/eee CodeSuomissseseeeeee ssiooiiiiiii for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: This paper does involve training models, but the experimental settings clearly described in Section 6
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We demonstrate the statistical significance of our results using standard metrics in the area of differential privacy.
To be specific, for the sum estimation problem, we do not treat the data as random samples drawn from some underlying distribution, so the only randomness comes from the DP mechanism. Our algorithms allow a failure probability (denoted by the parameter 3), which is set to 0.1 in our experiments. Meaning that with at most 10% probability, the real error may exceed our theoretical bound. We repeat each experiment 20 times, discard the top/lower 10% errors, and then compute the average of remaining emrors.
15

---

Meanwhile, how to provide differentially private confidence intervals is an interesting research problem [32 21] and not clear how provide CI in our personalized LDP setting. This may be our future work.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative eτror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The required information are provided in Section 6
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: This paper conforms with the NeurlPS Code of Ethics. We use publicly available datasets properly.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- cration due to laws or regulations their jurisdiction).
10. Broader Impacts
16

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theoretical paper that aims to design mechanisms to protect users' privacy under various privacy demands. On the other hand, these mechanisms cannot be maliciously used to have negative social impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
This paper does not involve models and does not face the risk of misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We use several public datasets and cite them properly.
Guidelines:
17

---

The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The codes used in this paper are provided and documented.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
18

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question:
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core content of this paper does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our L.LM policy for what should or should not be described.
19

---

A Appendix A: Proofs
A.1 Proof of Lemma 3.2
According to Lemma 2.2 19. suppose P and Q are distributions on x O. Let P and Q' denote the marginal distributions on Ω induced by P and Q respectively. For æ E Ω, let PK and Q' denote the conditional distributions on @ induced by P and Q respectively, where x specifies the first coordinate. Then
D, (P'IIQ)) + min D. (PHI) (PII)) & D, (P'IIQ) + max D, (P)))
ZEQ
zEi
In our case, let P be the distribution of M2([[u), y())) and Q be the distribution M2 y (u)). Here y (u) denotes the information obtained from (M1 (I(u)) except for changing user u output from Mi (I(u)) to Mi (u)). Then we have
D. QP D. (MM m (.((()))
I(a)
S (2) (M(
= {u) + (2(2))
Here the second line follows from the post-processing property in Lemma 2.2 of (9. where y(u) can be viewed as post-processing of (Mi (I())))..
A.2 Proof of Theorem
Privacy is straightforward. According to Lemma 3.1 each iteration of the for-loop in Algorithm | preserves (w)) CDP. Since this holds for any u, according to the definition of PLCDP, each iteration will be + -PLCDP Then the whole process will be Φ-PL.DPP according basic composition.
Next we prove the utility. We first show that with high probability, the Sum, (I) we obtain in each round under-estimates SI. Conditioned on this, taking max for Sum(I] can only reduce the error.
We should note that the truncated sum is always smaller than the true sum, that is:
Σ min (o, Sav / (
Sum Sum (I)
I(u) 30.
[(()(()
The noisy sum Su)(T,) consists of n i.i.d. Gaussian noises (N ls? laxa), which can be viewed as single Gaussian (0, nuts? d. According to the Gaussian tail bound in Lemma 3.3 with probability at least 1- the magnitude of noise added on any coordinate of Sum(I.) in any round i is no greater than 8; 2nt In 2td 3
which is the amount subtracted by the server in line Algorithm
Conditioned on this, have for any iteration
0 Sum (I) ~ (T, A Sum(I).
Here < b means alj} b[j] for each coordinate j. That is, each coordinate of any Sum; is underestimation of the real sum at that coordinate.
Then show for any choice of R20, our error is no greater than the value stated in equation for that First note we only need to consider without reducing the truncation error.
n since a larger will increase the noise
PPmin
When = 0, the value Equation
Sum (I) 12, and clearly
Summ(1) (I) I|2 < |Sum(D)]l..
20

---

For any other s, we can always find an such that s:/2 <
Then
0, siv (1))
Sum(T,) - Sum (I)
Σ min
I(u)
[T(u)ll2
vv20(u)
Σ min
0,
I(u)
[[(x)]
meaning the truncation error for Sum(I,) smaller compared to using the truncation threshold. This further implies
sv20(u)
[T) - Sum(T)ll <
Σ min(0,
1)I(u)
[[(u]l2
Thus with probability at least 1 we have:
2td
|/Su;; (I) Sum(T)]l2 (Im + N (0, nto? laxa) ssi 2nd In
Sum(II
B
2td B
z Sum(()) Sun(D))22 + 2 2ndt In
s sv20(u [
2td
min
I(u)
+ 1
2ndt In
3
Additionally, since STm(T) is obtained by taking the maximum on each coordinate of under-estimates, we have
[Iu Sum(I)]l2 < [|Sum, (I) Sum
The above inequality holds for any s, so the actual error of Algorithm 2 should be no greater than the minimum of them. The foo bound can be obtained similarly, by observing that
24d
[Sum; (I) SSmm(1) = (im + V (0, nts? 1axa) - s./ 2nt In
1 Sum(I)
B
21d
(Lm Sum(I) + +22;
2nt In
B
Σ min 0, sv/20(u) [Tu)) 1|
24d
I(u)
+ 48
2nd In
B
A.3 Answering All Range Queries using Hierarchical Histograms
Here we describe in detail how to adopt the hierarchical histogram approach in 23 together with our PLCDP randomizer/analyzer described in Section 4 to answer all range counting queries. We consider the single-dimension setting, where users' values are integers in [B]. Our target is to construct (private) hierarchical structure that can answer arbitrary range counting queries efficiently and accurately. For clarity, let us assume B+ 1 is a power of 2; otherwise we can just use [log( B (B+1) in place of each log(B B 1) in the following discussion.
Figure 4 provides a graphical illustration of the hierarchical structure when privacy is not involved. In the lith level of the hierarchical structure the highest level and log (B + 1) the lowest level), the range [0, B] is divided into 2 disjoint bins, each with length 1)) Each user encodes his/her value I(u) into a frequency vector H₂ E {0, 1]2" indicating which interval his value belongs to. Say,
Hx(w))) [1.
if I(u) [j (l) (j - (log(B-1)-1 1]:
0, otherwise.
21

---

[0,3]
[0.1]
[2,3]
[0,0]
[1,1]
[2,2]
[3,3]
Figure 4: An example with B 3. In the hth level, the frequency vector HA has dimension 2 Summing up all the H,, (u)s is for all users will give a histogram of that level.
easy to see user's data at any level in the hierarchy one-hot. Under such construction, summing all the (u)'s in each level for all users will give histogram for that level.
To make the whole process preserve 4-PLCDP, we invoke Algorithm 22 obtain private sum for each level h = 0, l,., log(B B + 1). On the user side, we invoke the LocalSum-r Algorithm with specially designed inputs H, (u), 4', By 8², dz. Here Hz(u) is constructed as above, with dimension d, = 2 for the /th level; ('(u) =
log(B+Tji 3' log[B+T] as the privacy/failure probability allocated for each level; and / for the failure probability for the whole process. For the value By since the lg norm of Hy(u) (u) is exactly 1, we set By
4(u)
For each level h, LocalSum-r(HH,, (u), 2 1h, 8", d))) returns a set of t' vectors, where t' is invariant across different levels. We denote the result returned
[log (V Penax B3, [log
Pmax
Piin
by LocalSum-r(Hn,(C Φ', By Bi, d(,) as (H)a(u))i Hi which corresponds to truncated noisy values log(B-1)
different noise scales. And then (H,s()))( }
contains all the required information to build the whole noisy hierarchical histogram, where the inner index i represents different noise scales in that level and the outer index represents different levels of the hierarchical structure. Details are shown in Algorithm 3
4=0
On the server side, as described in Algorithm 4 invoke LocalSum-ale (HH, 8 By By B' d( for each level with (H){ obtained from the user side and parameters D', B₁ 3r, d' defined the same as above.
The above procedure will provide us noisy histogram for each level. Then order to select the desired quantile, we should use binary search to find the smallest m such that the (noised) frequency of [0, m| is greater than 5. Note any interval [0, m] can be covered with most log(B B + 1) bins inside the hierarchical structure (to be more specific, at most one bin from each level). Thus the noisy frequency of (0, m] is at most log B 1) times of the maximum error for each bin. Below the detailed algorithm.
The median selection process can be done in one round with a single message, which divided into segments where each segment corresponds to a noisy frequency vector. For each level, the user should send L' (log (max) message segments and thus Ollog B log fmax Punin.
message segments in
Pmin
total. The average length of these message segments will be O(B).
To reduce communication complexity, one may apply the sampling technique as in 23 say, each user only randomly picks one level in the hierarchical structure join. This optimization can reduce the number of message segments by factor of log B. While this will save privacy it does introduce additional variance, as the final result needs to scaled back by multiplying log B. The overall effect of sampling is to increase the rank error by a factor of Vlog B. This is acceptable for our setting when n is large, since what we require any interior point: we don't really care about the rank error long it remains between the minimum and maximum.
22

---

Algorithm 3: LocalHist-r
Input: [(u) 2, B.
8 + log B+ 4
8
+
t' + [log
(Bg(
Pmin
for h 0, ,..., log( B + do
dh 2h:
Define (u) {0. 1 such that
Hn f1,
(() E * 2log(B-1)-A, 1,-0,,,,+11 2log + -
0,
otherwise
(H) LocalSum - (H), 1','''',
end
loo( (+)(
return
(Ha(()))
h=0
Algorithm 4: LocalHist-a
Input: (u) 1og(B-1)
.b, B,
h=0
38 f Tog B4 Φ'
Tog (B+T): + -[log
Bmax
Pmnt
2 for h + 0, 0......, log(B + do
d' 2h:
Sum, + LocalSum ((Hn; &'1,,'",,
end
return {Sump, h== /
(og(
In parallel, one may apply the lossless compression technique as in [66, which reduces the size of each message segment from O(B) to O(log B + /Pmax). The intuition is as follows: since DP definitely induces loss of information, there no need to send the full information at the beginning. Instead, can send seed which has much smaller size, and expand it via pseudorandom generators to recover the result. Given an exponentially strong pseudorandom generator and an algorithm that properly chooses it is demonstrated in [16] that one can reduce the message size significantly while preserving utility. Such reduction requires rejection sampling and thus leads to additional computational costs at the user side. Note this compression technique parallel with sampling, thus applying both, the communication cost can be reduced to O(log Pmin
be done in lmaa
message segments in total, whereas each segment has size O(log B + VPmaax).
A.4 Proof of Theorem 4.3
We start by analyzing the Eo error of the histograms in each level. Consider the /ith level, according Theorem 4.1 the foc error of Sum, is greater than
< min 8y 2/220 12
21' s
min #E
(") + + 2nt'nn
HH (2)l2
gr
where t', (u), Φ', 3', dr are defined as in Algorithm 3
Notably, in the special case of median selection/historran construction, we always have H [,)l2)
furthermore, the dimension d' the histograms at each level bounded by + 1. Then the guarantee in Equation 7 reduces to
2B + 1)
min A #ERg0
Σ 1(s 1(s/200
2/ (u) 1) + 4/ 2nt'ln
(8)
8'
23

---

With the increase of the noise increases but the bias reduces when it hits of Equation non-decreasing order, Equation (8) is equivalent to finding
So the minimum
22)(w))
( must be obtained at 8
for some u. Assume values d are ranked in
(w)
4
2B (B++1
min eE|n]
i
2nt'In
(9)
20 (
8r
Let be the minimum & such that Σi=1
D'(z)) 2 1. We show minkej]]
8 Vor(us))
S 4k' in
Lemma A.I As result, the loo error of the histogram at each level is bounded by O nnt'l with probability B. By taking union bound, this leads to an error of
UB
k!)
Br
o (neenn B'B log
k
8
which holds simultaneously for histograms in all levels.
To move from the error of histograms to the error of range queries, we should note that each range query can be obtained by summing at most 2 log B entries the histograms. Thus the error cach query is bounded by
o (Inein B'B log B 8r
k' log B
Finally, plug in the values t' and 3 chosen in the previous subsection. For k' note that K' s vlog Bk, where & is the smallest index such that E ((u)) 2 1. The error therefore bounded by
o
log B log
Pmus Prnm
Pmax
log
k log?
Pmin
B
Below we complete the proof of Lemma A.1
Lemma A.1. Assume values in & are ranked in non-decreasing order and pmin t Let k be the smallest index such that Eim / ((u)) 2 1, then
min <E|n]
i +
S 8k
/ ((,)) (ui)
Proof. Let i" argmin, Vo(u.) and let M max(i"
Consider i' = M We have by definition
1
i'
> M > 2
So i' ( < 1. Since + is ordered, all ((u)) with < are greater than ((u)). As result,
we have
Σ (bu)) if ((1)) / <1
which means & 2 On the other hand, we have
min
i
< 2M 8i' 8k
sE(n]
(m:)
which completes the proof.

---

A.5 Omitted details in Section
Before going to the proofs, we first briefly introduce the intuition behind the proof. First of all, with high probability Step I can provide 'good rotation' such that for any pair of users' data, Lemma 5.2 holds. Then with high probability Step 2&3 can find an interior point of the rotated dataset on each dimension. Conditioned on these two events, with high probability the radius of the shifted data I, (T)) Note that when rotating back by multiplying (H D) in the last step, the l norm of the result will be decreased by factor of va so the additional vd factor here will be eliminated finally. That is,
perform the sum algorithm safely.
Since the shifted data involves randomness depending on both random rotation and median selection, to obtain a deterministic error bound as stated in Theorem 5.3 we aim to characterize the worst case. This happens when the shifted data is obtained by subtracting the minimum (maximum) value of each dimension. We denote such datasets as (I,"" respectively. These datasets are the 'worst' in the sense that their positive/negative part has the largest radius and leads to the largest error, which is proved Lemma A.2 We further analyze the error on these worst case instances in Lemma [A.3] Finally, combining all the above arguments and adding up the error of positive/negative parts leads to a complete proof of the main theorem. Below we first present the two lemmas.
For clarity of expression, we denote EIr(T) to be the enror of Algorithm 2 when invoked on dataset
& I with privacy parameter 4 failure probability & 4 domain bound Bv and dimension d. To be
specific, define
(1 (1uw)ll--s min =ERzo
+
I(u) [T Mu)]l
Sid
Err(T)
+ av
2ndAIn
(10)
B
where [log dB,
Piaax
Paii
Lemma A.2. Given i, conditioned on the fact that Steps 2-3 correctly find an interior point on each
dimension, we have
Err( Err(i,")
where i is obtained by subtracting the minimum value of each dimension so that all values inside are non-negative. The same property also holds for Err(I,) )
Proof. First of all, it is easy to see (u) s I (u) (on each coordinate) for any u. This is because, for each coordinate of i (u). its corresponding value in I (u) is either 0 (moved to negative part) or smaller (since i subtracts the minimum each dimension). And this further implies
[ (u)lla < (1)]2.
To show Err(ī;)= z Em[(i:",, only need to prove the former has smaller bias for any (scale), that is
Σ -
(u)
< Σ (w)ll2
vVo(w)/2 + -
| (w)ll
| (w)
2
Indeed we can show a stronger statement:
SV ((u)/2
(0, SV (2u)22
Σ max 0,
it (u) S Σ max 0.
i!'(u)
|| (u)ll2
|| (u)
Because for any max 0, negative.
"y (ww/2 [[]] (w]lz
max 0,
sy (
and all items are non-
[|I. "(w)ll
For the i, counterpart, one may construct i- by subtracting the maximum value each dimension and then taking absolute so that all values inside non-negative.
25

---

Lemma A.3. Conditioned on the fact that the rotated data satisfies Lemma 5.2 for all pairs of points,
- (Vabo
nd min sE
Σ
I(s L(oV <
td nntlln B
B
with probability at least 1 where = [log dB
Lmax
The same bound also holds for Err(1,").
Pmin
Proof. We only prove the statement for Err Err(I,") ) as the other part follows similarly. According the definition Equation (TO), we have
(1
(
E 0
min 2
[ (v0)llss//(1)///
+
td ndtln
[
(u)lla
3
(11)
Considering the truncation error term
Eu
sv /(u/2/2
(u) (w)lla
we have
(w)) + [t((w)
(1)ll
(88 < ( (v)lar)a)
nd Σ (Ss) ( dlog nd )w(D)) d 3
w(D)
3
Here the second line is because when the rotation is 'good', the radius of i is no greater than nd " gives the
nd /d))/log 3. Plugging it back Equation (11 and substituting s' d d
desired result. Note this error expression only related to the original data and does not involve the randomness rotation and shift.
Below the complete proof of Theorem 5.3
Proof. Privacy follows from the composition theorem, so we focus on utility here.
With probability at least J. the rotation satisfies Lemma 5.2 for all pairs of points. Further,
according Theorem 4.3 with (another) probability least 1 & can find an interior point in
each dimension. This means that Lemma A.2 A.3 hold together with probability at least 1 S.
[Sum(1) Sum
=I =||Sum(I] (HD)-1 (Sum(I;)) Sumi(;) + n m) l|2
=Il -HDD) -1 (umm(1;) - Sum(i;)) - Sum(1,) Sum(1z)) 1|2
1
- Va
Err(i:)) + Err(i,))
1
< Vd
EEr(i+)) Eir(i,")
(v (Voog
nd
Σ 1( 1(o < (()))((I) + / Indlln td
=0
min
(
sE3g0
26

---

where the third line is because
STm(II= = (HD) - Sum(I)
(HD) (Sum((.) + n m
(HD) (Sum(I,) Sum(i,) + n m
The forth line is because multiplying by (HD) decreases & norm by a factor of va And
the last line comes from applying Lemma A.3 twice on both I and I,", each consumes failure
probability of 4. Combining all arguments together with probability at least 1 3 the error bound holds.
Dividing the above error by leads to the mean estimation emror:
log log emax
Corollary A.4. Given 4 B. B, d, if n ed log Pmax log B Φ-PLCDP Algorithm that estimates the mean of with &g error at most
emin log B, there
log nd B
td 3
O
min #ER20
((8 < (I) + Indtln
Th
with probability at least
B, where [og dB,
Panax
Panin
The whole process is two-round protocol, where the first round finds interior point and does the shift, and the second round computes the sum estimation. As discussed in the previous section, without loss utility, the communication cost of the first round can reduced to O(d log Bpmax) message segments per user, whereas each message has size Olog B + /Pmax). And for the second round, each user sends Olog Bddmax) message segments, each with length (cd) (or Ollog d /Pmax) if d too large).
Pmii
Pmin
27


Reviews:
[{"review_id": "4OsfkG7aex", "reviewer": "Reviewer_fj6z", "summary": "This paper considers a specific local differential privacy (LDP) framework, coined personalised LDP, where each user can set his/her individual privacy parameter. The authors are studying mean/sum estimation problems under this framework and provide two estimation protocols with theoretical foundations. Experiments illustrate the benefits of their approach.", "questions": "See above", "limitations": "N/A", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n* The paper is well-written, clear and sufficiently motivated.\n* The problem is relevant to the community, and up to my knowledge, the proposed protocols and their theoretical insights are new.\n* Related work is sufficient.\n\n**Questions**\n* Could the authors comment on the optimality of their error upper bounds for the two protocols?", "was_revised": false, "final_justification": "", "rebuttal": "Reply to Question \\#1:\n\nWe agree that optimality is an important theoretical question to consider.  However, the answer is quite nuanced, depending on the precise notion of optimality. \n\nWorst-case optimality: Consider a particular user $u$, and the following instances the user may have: $(B,0,...,0), (0,B,...,0),..., (0,0,...,B)$.  Since LDP requires all of them to be $\\Phi(u)$-indistinguishable, the user must injects a noise of scale $\\Omega(\\frac{B}{\\sqrt{\\Phi(u)}})$ on each coordinate (this can be formalized by standard lower bound arguments). Thus the worst-case error for the sum of all users' data is $\\Omega(B\\sqrt{d\\cdot\\sum_{i=1}^n \\frac{1}{\\Phi(u_i)} })$.  Our algorithms incur an error no more than this on any instance, so it is worst-case optimal.  However, this bound can also be achieved by a trivial mechanism that simply adds an $O(\\frac{B}{\\sqrt{\\Phi(u)}})$ Gaussian noise on each coordinate, which is very large on typical instances.  So worst-case optimality is not very meaningful, either theoretically or practically. \n\nA much stronger notion of optimality is instance optimality.  However, for any instance $\\mathbf{I}$, there always exists a trivial mechanism $M(\\cdot) \\equiv \\mathrm{Sum}(\\mathbf{I})$ that achieves 0 error on this instance (while incurs large errors on other instances).  This means that instance optimality is unattainable.\n\nSeveral prior works [13,18,A] has then introduced various relaxed notions of instance optimality, but they have not considered the personalized LDP model.  It would be an interesting direction to first extend these optimality notions to this model, and then see if our protocols are optimal with respect to any of them.\n\n\n[A] Dick, Travis, et al. \"Subset-based instance optimality in private estimation.\" International Conference on Machine Learning. PMLR, 2023."}, {"review_id": "gCOfB9gHEE", "reviewer": "Reviewer_EmUR", "summary": "This paper provides two protocols for sum/mean estimation in a personalized local differential privacy model, specifically where each user is allowed to set their own privacy parameter to any positive real number. The first protocol has error which scales with the radius or maximum $l_2$ norm of the user's dataset, and the second protocol scales with the diameter of the data. Their results are numerically supported by comparison with a baseline method of adding a user dependent Gaussian noise after the truncating each user's data by a uniform threshold.", "questions": "1. It would be interesting to see a theoretical comparison of the naive optimal protocol (section 6) with the radius/diameter dependent protocols, and for which distributions the latter ones are expected to significantly outperform the naive protocol. Are these distributions expected to be similar to various real world/synthetic datasets?\n2. Do the protocols described achieve optimal error, if known? It would be helpful to have a discussion regarding the optimality of the described protocols within the first two sections.\n3. The formatting of the description of the radius and diameter dependent protocols are inconsistent. It would improve clarity to follow a similar format for both the sections, ideally using the algorithm environment since it is more standard.", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is clearly written, and provides detailed proofs with corresponding analysis. The main contribution of this work is to introduce and analyze an interesting model of local differential privacy. The radius dependent protocol under the assumption of a uniform privacy parameter for all users reduces to the optimal mean estimation bounds in prior work by (Huang et. al., 2021. \"Instance-optimal mean estimation under differential privacy\"). The diameter dependent protocol naturally generalizes this protocol by applying the previous radius dependent guarantee to a 'shifted' origin such that the radius of the shifted dataset is approximately the diameter of the original one. \n\nThe numerical results compare the new protocols to a naive optimal protocol, which appears in previous work. However, this choice of baseline could be better justified. It would also be helpful to see a more formal analysis of the cases where the diameter dependent protocol is expected to perform better than the radius dependent protocol.", "was_revised": true, "final_justification": "My questions were adequately addressed, so I will be keeping my current score", "rebuttal": "Reply to Question \\#1:\n\nWe agree that doing a theoretical comparison under some common distributions can complement our experimental observations.  \n\n\nWe have done some analyses on 1D data for the following two distributions (please let us know if you are interested in other distributions):\n\n(1) Uniform data in the range $[0,n]$.\n(2) Gaussian data with mean $n$ and variance $O(n)$.\n\nUnder the same privacy specification as in our experiments (say, 5\\% privacy parameters are uniform in $[\\frac{1}{n}, 1]$ while the remaining are uniform in $[1, 100]$).\nWe can show that, for both data distributions, the error of the naive optimal protocol is $O(n^2)$ while our radius-dependent protocol has error $\\widetilde{O}(n^{5/3})$.  For Gaussian data, our diameter-dependent protocol further reduces the error to $\\widetilde{O}(n^{3\\over 2})$ because the data is clustered away from the origin. \n\n\nFrom these observations, it is evident that for common real-world data distributions, our methods outperform the naive optimal protocol. Furthermore, the performance gap becomes even more pronounced as the data becomes more concentrated.\n\nFinally, we would like to emphasize that the naive optimal protocol assumes that the optimal truncation threshold is given, which is not easy to obtain under privacy constraints. \n\n\nReply to Question \\#2:\n\nPlease see our response to Reviewer \\#1 Q1.\n\nReply to Question \\#3:\n\nWe agree.  We'll rewrite our diameter-dependent protocol using the algorithm environment to improve clarity."}, {"review_id": "L6YYuJrZwd", "reviewer": "Reviewer_Ku3C", "summary": "This paper studies the problem of sum/mean estimation under personalized LDP, where the users have different privacy parameters (given by a function $\\Phi(u)$ for user $u$). They consider specifically the zero-concentrated variant of personalized LDP and assume the elements are in $[B]$. Their methods are based on truncating the elements and adding noise with scale proportional to the truncation threshold to each element. The truncation threshold is of the form $s\\sqrt{\\Phi(u)}$ for each user $u$, where the universal factor $s$ is determined by the \"subtract-max\" technique [13] which involves running $\\log(B\\sqrt{\\rho_{\\text{max}}/ \\rho_{\\text{min}}})$  instances of the truncation mechanism each with a different $s$ ($s$ ranging from from $1/\\sqrt{2\\rho_{\\text{max}}})$ to $B/\\sqrt{2\\rho_{min}})$, and finding the noisy sum that approximately achieves the best balance among the bias and noise. They also give a method with diameter-dependent error, which applies the shift-and-rotate technique from [18] together with the truncation protocol mentioned above.", "questions": "- Maybe the authors can highlight any contributions/insights in the paper that are not obvious but are of importance/interest. E.g. why the truncation threshold function is of this particular form, and what insights it brings, etc., or anything else they want to highlight.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "strengths:\n- This paper studies an important problem.\n- The presented methods are natural.\n\nweaknesses/comments\n- The paper might not be easy to read for those not familiar with the related work or DP mean estimation. However, for those who are familiar with these works, they would probably notice that the method presented in this paper uses a combination of existing techniques. In particular, the presented results - one being radius-dependent, the other being diameter-dependent - are consequences of extending the methods in [18] to the personalized privacy setting.\nThus, there is not much novelty in terms of the techniques presented in this paper, which is not a big issue per se, but as it stands there does not appear to be other noteworthy insights/interesting points. \n- I do not have a problem with the results in the paper in general, but this paper appears borderline to me.\n- Also, this submission appears to be a few lines over the 9-page limit which violates the NeurIPS formatting requirements. Taken this into account, I am leaning more toward the negative end of the border.", "was_revised": true, "final_justification": "My impression of the paper remains largely the same.", "rebuttal": "Reply to Weakness \\#1:\n\nThe shift-and-truncate framework in [18] is a standard approach for addressing the sum estimation problem, which is not the focus or contribution of our work.\n\nIn this paper, we consider the personalized local DP setting, where the error depends on both users' **data** and users' **privacy**. The main challenge lies in determining **how** to perform truncation in a way that balances the effects of these two factors.\n\nTo address this, we propose a novel searching strategy that optimizes over both dimensions simultaneously by considering the noise scale $s$. In contrast, [18] relies on a pre-computed quantile for truncation and does not involve any optimization procedures.\n\nFurthermore, the method in [18] cannot be extended to our setting because the target quantile (and thus the truncation threshold) cannot be computed while adhering to the personalized DP requirements. A comparable baseline is the *naive optimal protocol* used in our experiments, which assumes we already know (in a non-private manner) the optimal truncation threshold. Even with this unrealistic advantage, the naive optimal protocol is outperformed by our approach, highlighting the effectiveness and significance of our new strategy.\n\nReply to Weakness \\#3:\n\nWe sincerely apologize for our oversight. A minor change was made to the paper shortly before the submission deadline, and we did not realize it caused the paper to exceed the 9-page limit. We'll definitely fix this problem and hope this will not be the reason for rejection. Thanks!\n\nReply to Question \\#1:\n\nThanks for the comment. As we have explained in our response to Weakness \\#1, the main idea and contribution of this paper lie in the proposed searching strategy that considers $\\mathbf{I}(u)$ and $\\Phi(u)$ simultaneously. That's why the truncation threshold is of the form $\\tau_i(u) =s_i \\sqrt{2\\Phi(u)} = 2^{i}\\sqrt{\\frac{ \\Phi(u) }{\\rho_{\\max}}}$.\nWe will emphasize the core contributions of our work and provide additional explanations to clarify the insights behind them."}, {"review_id": "XEj3n5U59J", "reviewer": "Reviewer_bB2d", "summary": "Private sum estimation protocols generally aim to balance a bias term caused by clipping with a term caused by the noise ensuring differential privacy. The best choice of the clipping parameter (and, in some cases, the center of the clipping ball) is highly data dependent. Methods such as Coinpress have been devised to address this tradeoff in the central model of DP.\n\nThis paper addresses local differential privacy (LDP) with individual privacy budgets (personalized DP). It suggests a protocol that refines the baseline of choosing a global clipping threshold used for by all local randomizers. The idea is to release each number with multiple clipping thresholds (splitting the privacy budget evenly), spaced geometrically such that a logarithmic number of thresholds covers all relevant thresholds within a constant factor.\n\nThere is also a 2-round algorithm that is able to get a bound in terms of the diameter of the dataset, mirroring past work on adaptive mean estimation.", "questions": "- Instead of releasing a report for every chosen threshold, did you consider sampling a random one? This might give a better privacy-utility trade-off, in particular for pure DP\n- Did you consider what your techniques can do in the context of shuffling or secure aggregation?\n- Is there a reason you did not include the inverse sensitivity-based exponential mechanism of [20] as a baseline?", "limitations": "Most limitations are adequately discussed, but the limitations of LDP algorithms for ML applications could have deserved some discussion.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Sum (and mean) estimation is a key part of many machine learning algorithms, with private variants used in stochastic gradient descent. The proposed algorithm is rather nice and offers a nontrivial guarantee.\n\nOn the other hand, for many ML applications the amount of noise of LDP protocols is simply too large, and this is inherent to LDP. Therefore cryptographic techniques such as shuffling and secure aggregation are used to get closer to central model utility guarantees without collecting data. As such, the proposed protocol might have limited impact in machine learning.", "was_revised": true, "final_justification": "In view of the discussion, in particular the fact that there are no attractive alternatives in the central model, I am now more positively inclined.", "rebuttal": "Reply to Question \\#1:\n\nIn our protocol, we consider $t= \\log \\left( \\sqrt{\\frac{\\rho_{\\max} }{\\rho_{\\min}}} B \\right) $ thresholds and wants to find the best among them, which requires releasing all the $t$ results and thus we have to divide privacy into $t$ parts.\n\nIf we opt not to report each threshold and instead randomly select one, we can save privacy by a factor of $t$. However, the risk of choosing a suboptimal threshold can result in significant overhead, ultimately becoming the dominating factor.\n\nConsider the data in Example 1.1, our radius protocol achieves an error of $O(n^{4\\over 3}\\log (nB))$ with constant probability. However, if we randomly choose a threshold, the error is likely to exceed $(nB)^{2\\over 3}$ with constant probability, which is considerably larger in general.\n\n\nReply to Question \\#2 and Weakness \\#1:\n\nWe agree that the LDP model introduces larger noise compared to other DP models.  However, because of its simplicity, both the research community and the industry [B] have invested a lot of effort in studying LDP, and this work is therefore important to NeurIPS to fully understand what can (and what cannot) be achieved under this model. In particular, the sum estimation problem under LDP has been extensively studied as a foundational problem [C,D,references in the paper].\n\nYou are right that secure computation can often reduce the noise, by using cryptographic techniques to hide some intermediate results against a computationally bounded adversary, at the expense of higher computation/communication cost and implementation complexity. On the other hand, an LDP protocol reveals all intermediate results to a computationally unbounded adversary.  This two approaches are in some sense orthogonal and can be often combined [E], yielding a trade-off between cost and noise. This is a promising direction to combine our LDP protocol with secure computation.\n\nHowever, our technique cannot be applied to the shuffle model. The key reason is that differing privacy parameters among users negate the`hiding among the crowd' effect, which is essential for the utility amplification of the shuffle model.\n\n\n[B] Cormode, Graham, et al. \"Privacy at scale: Local differential privacy in practice.\" Proceedings of the 2018 international conference on management of data. 2018.\n\n[C] Liu, Junxu, et al. \"Cross-silo federated learning with record-level personalized differential privacy.\" Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security. 2024.\n\n[D] Duchi, John, and Ryan Rogers. \"Lower bounds for locally private estimation via communication complexity.\" Conference on Learning Theory. PMLR, 2019.\n\n[E] Kairouz, Peter, Ziyu Liu, and Thomas Steinke. \"The distributed discrete gaussian mechanism for federated learning with secure aggregation.\" International Conference on Machine Learning. PMLR, 2021.\n\n\nReply to Question \\#3:\n\nThe exponential mechanism (EM) requires computing a utility score (which depends on users' private data) for each possible output. In the central model, this score can be directly computed by the central server.\n\nHowever, in the local DP model, calculating utility scores necessitates interactions between users. Consequently, the computed utility scores must include DP noise.\nThis makes EM meaningless in the LDP model since its utility guarantee is highly sensitive to the accuracy of the utility scores.\nTo the best of our knowledge, no prior work has successfully applied the exponential mechanism in the local DP model."}]

Author rebuttal:

Meta-review: Summary: This paper considers a specific local differential privacy (LDP) framework, coined personalised LDP, where each user can set his/her individual privacy parameter. The authors are studying mean/sum estimation problems under this framework and provide two estimation protocols with theoretical foundations. Experiments illustrate the benefits of their approach.

Strength: (1) This paper studies an important problem. (2) The method is well written and well motivated. 

Weakness: (1) No experiments on real data and no comparison with previous work. 

Based on the importance of the work and all reviewers agree to accept the paper. My suggestion is accept.
Decision: Accept (poster)