A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacy
Authors: Puning Zhao
Lifeng Lai
Li Shen
Qingming Li
Jiafei Wu
Zhe Liu
Venue: NeurIPS 2024 poster (2024)
Keywords: differential privacy
robustness
huber loss
Primary area: privacy

Abstract: Privacy protection of users' entire contribution of samples is important in distributed systems. The most effective approach is the two-stage scheme, which finds a small interval first and then gets a refined estimate by clipping samples into the interval. However, the clipping operation induces bias, which is serious if the sample distribution is heavy-tailed. Besides, users with large local sample sizes can make the sensitivity much larger, thus the method is not suitable for imbalanced users. Motivated by these challenges, we propose a Huber loss minimization approach to mean estimation under user-level differential privacy. The connecting points of Huber loss can be adaptively adjusted to deal with imbalanced users. Moreover, it avoids the clipping operation, thus significantly reducing the bias compared with the two-stage approach. We provide a theoretical analysis of our approach, which gives the noise strength needed for privacy protection, as well as the bound of mean squared error. The result shows that the new method is much less sensitive to the imbalance of user-wise sample sizes and the tail of sample distributions. Finally, we perform numerical experiments to validate our theoretical analysis.

A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacy
Puning Zhao Zhejiang Lab pnzhao@zhej ianglab. com
Lifeng Lai University of California, Davis 1flai@ucdavis.ed
Li Shen Sun Yat-Sen University ma mathshen 1gm com
Qingming Li Zhejiang University 1 imquzju. u. edu. edu. cn
Jiafei Wu Zhejiang Lab wujiafei
Zhe Liu" Zhejiang Lab zhe. jangzaaajannaab com
com
Abstract
Privacy protection of users' entire contribution of samples is important distributed systems. The most effective approach is the two-stage scheme, which finds small interval first and then gets a refined estimate by clipping samples into the interval. However, the clipping operation induces bias, which is serious if the sample distribution heavy-tailed. Besides, users with large local sample sizes can make the sensitivity much larger, thus the method is not suitable for imbalanced users. Motivated by these challenges, we propose a Huber loss minimization approach mean estimation under user-level differential privacy. The connecting points of Huber loss can be adaptively adjusted to deal with imbalanced users. Moreover, it avoids the clipping operation, thus significantly reducing the bias compared with the two-stage approach. We provide a theoretical analysis of our approach, which gives the noise strength needed for privacy protection, as well as the bound of mean squared error. The result shows that the new method is much less sensitive to the imbalance of user-wise sample sizes and the tail of sample distributions. Finally, we perform numerical experiments to validate our theoretical analysis.
Introduction
Privacy is one of the major concerns in modern data analysis. Correspondingly, differential privacy (DP) [T] has emerged as a standard framework of privacy protection. Various statistical problems have been analyzed with additional DP requirements (2/5). Among all these problems, mean estimation is a fundamental one (.. which is not only useful in its own right [10), but also serves building block of many other tasks relying estimating gradients, such private stochastic optimization (16 and machine learning (7H23). Existing research on DP mean estimation focuses primarily on item-level cases, i.e. each user contributes only one sample. However, in many practical scenarios. especially in recommendation systems (24 and federated learning (27-32), user has multiple samples. We hope to regard them as whole for privacy protection.
In recent years, a flurry of works focus on user-level DP 33 The most popular one is the Winsorized Mean Estimator (WME) proposed in (34), which takes two-stage approach. In the first stage, WME identifies an interval, which is small but contains the ground truth μu with high probability. In the second stage, WME clips user-wise averages to control the sensitivity and then calculates the final average with appropriate noise. This method can be extended to high dimensionality by Hadamard transform 37). The convergence has been established in (34 under some ideal
Conresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

assumptions. Despite the merit of the two-stage approach from the theoretical perspective, this method may face challenges in many realistic settings. Firstly, [3] assumes that users are balanced, which means that users have the same number of items. Nevertheless, in federated learning applications, common for clients (each client is regarded as user here) to possess different numbers of samples (38]40) Secondly, this method is not suitable for heavy-tailed distributions, which is also common in reality [41]46]. For heavy-tailed distributions, the interval generated in the first stage needs to be large enough to prevent clipping bias, which results in large sensitivity. As a result, stronger additive noise is needed for privacy protection, which significantly increases the estimation error. These drawbacks hinder the practical application of user-level DP. We aim to propose new solutions to address these challenges.
Towards this goal, in this paper, we propose a new method, which estimates the mean using Huber loss minimizer [47], and then adds noise for privacy protection. A challenge is that to determine an appropriate noise strength, it is necessary to conduct a thorough analysis of the local sensitivity that considers all possible datasets. To overcome this challenge, we divide datasets into three types, including those with no outliers, a few outliers, and many outliers, and analyze these cases separately. Based on the sensitivity analysis, we then use the smooth sensitivity framework (48) to determine the noise strength carefully.
Our method has the following advantages. Firstly, our method adapts well imbalanced datasets, since the threshold T; of Huber loss are selected adaptively according to the sample size per user, which leads to a better tradeoff between sensitivity and bias. Secondly, our method performs better for heavy-tailed distributions, since we control sensitivity by penalizing large distances using Huber loss, which yields a smaller bias than the clipping operation. Apart from solving these practical issues, it worths mentioning that our method solves robustness (to model poisoning attacks) and privacy issues simultaneously. In modern data analysis, it is common for a system to suffer from both poisoning and inference attacks at the same time (1)) Consequently, many recent works focus on unified methods for item- DP and robustness to cope with both attacks simultaneously 552 To the best of our knowledge, our method is the first attempt to unify robustness and DP at user-
The main contributions are summarized as follows.
We propose the Huber loss minimization approach, which finds the point with minimum Huber distance to all samples. Our method is convenient to implement and only requires linear time complexity.
For the simplest that our method makes a slight improvement for bounded distributions and a significant improvement for heavy- distributions over the two-stage approach.
with balanced users, provide theoretical analysis, which shows
For imbalanced users, we design an adaptive strategy to select weights and connecting points in Huber loss, which makes our method much less sensitive to the imbalance of local sample sizes of users.
We conduct experiments using both synthesized and real data, which also verify the effec- tiveness of the proposed method for imbalanced users and heavy-tailed distributions.
2
Related Work
User-level DP. [27 applies brute-force clipping method (18) for user-level DP in federated learning.
333 made the first step towards optimal rates under user-level DP, which analyzed discrete distribution estimation problems. The popular method WME was proposed in (34), which uses the idea of two- stage approaches (55)57]. The two-stage method for user-level DP has also been extended to stochastic optimization problems (58 60 analyzes mean estimation for boolean signals under lser- DP in heterogeneous settings. There are also some works focusing on black-box conversion from level DP to lser- counterparts. (35) analyzed general statistical problems, which shows that a class of algorithms for item-level DP problems having the pseudo- -looball stable property can be converted into user-level DP algorithms. Following (35), [61] expanded such transformation for any item-level algorithms. (36) extends the works to smaller m. It is discussed in (59) that these
black-box methods have suboptimal dependence on e. 622 64 studies leerl DP under local model.
2

---

From robustness to DP. Robustness and DP have close relationships since they both require the outputs to be insensitive minor changes in input samples. There are three types of methods for conversion from robust statistics to DP. The first one is propose-test-reeasee (PTR), which was first proposed in [65], and was extended into high dimensional cases [66]. The second choice is smooth sensitivity [48], which calculates the noise based on the "smoothed" local sensitivity. For example, (67) designed method to protect trimmed mean with smooth sensitivity, The third solution is inverse sensitivity 66,68,69 69], which can achieve pure differential privacy (i.e. 6 = 0). All these methods require a detailed analysis of the sensitivity. For some recently proposed high dimensional estimators [70 72). l. the sensitivity is usually large and hard analyze. As a common method for
robust statistics [47). Huber loss minimization has been widely applied in robust regression [73 74
denoising [75 and robust federated learning [76]. Huber loss has also been used in DP 77 78 for
linear regression problems.
Concurrent work. After the initial submission of this paper, we notice an independent work (79]
which also studies mean estimation under user-level DP (which is called person-level DP (79) ). [79
considers directional bound, which requires that the moment is bounded in every direction. However, we consider non-directional bound, which bounds the & norm of a random vector. We refer to Section 1.3.1 in (79] for further discussion.
Our work is the first attempt use the Huber loss minimization method in user-level DP. With an adaptive selection of weights and connecting points between quadratic and linear parts, our method achieves a significantly better performance for imbalanced users and heavy-tailed distributions.
3 Preliminaries
In this section, we introduce definitions and notations. To begin with, we recall some concepts of DP and introduce the notion of user-level DP. Denote Q as the space of all datasets, and θ as the space of possible outputs of an algorithm.
Definition 1. (Differential Privacy (DP) (T) Let c, 2 O. A function A 52 O (c,8)-DP ffr any measurable subset O C O and any two adjacent datasets DD and D',
P(A(D) E O) S e P(A(D)) E E +
in which D and D' are adjacent if they differ only single sample. Moreover, A is D-DP if holds with
Definition about item-level DP. In this work, discuss the case where the dataset contains multiple users, i.c. == {Di...., Dn J. with the i-th user having m. samples. Considering that the sample sizes of users are usually much less sensitive (80), throughout this work, we assume that the local sample sizes m, are public information. Under this setting, user-level DP is defined as follows.
Definition 2. (User-level DP (344) Two datasets D, D' are user-level adjacent if they differ in items belonging to only one user. In particular, if {Di....,Dy D' (D...... D', J. in which
|Da = | = m, for all i, and there is only one E [n]] such that D; o D' then D and D' are user-level adjacent. A function A is user-level (e, 8) if (T) satisfied for any two user-level adjacent datasets 'D and D'.
Since m, = I,...,N. N are public information, in Definition 2 it is required that [D,] = DD], which means that two adjacent datasets need to have the same sample sizes for all users. We then state some concepts related to sensitivity, which describes the maximum change of the output after replacing a user with another one:
Definition 3. (Sensitivity) Define the local sensitivity of function as
LSy(D) (D
sup
[I{(D) FDD')I.
in which d (D, DD) Σ 1(D; + D.) denotes the Hamming distance. The global sensitivity of f is GS, supp (D).
Adding noise proportional to the global sensitivity can be inefficient, especially for user-level problems. In this work, we use the smooth sensitivity framework (8).
3

---

Definition 4. (Smooth sensitivity) Sy is S-smooth sensitivity of f, if for any D, Sy(D) z
(D)(D); (2) for any neighboring D and D', (2(D) S S,
The smooth sensitivity can be used to determine the scale of noise. In this work, the noise follows Gaussian distribution. It has been shown in [48) that if W ~ (O, (D) (I), then the final output f(D) + W is (e, (eP for the following (a, () pair:
if d=1
if d d>1, B B=
B=
2
if d=1
if d>1.
5 2
a(
Notations. Throughout this paper, |-|l denotes the l norm by default. S b means that S Cb for some absolute constant C, and 2 is defined conversely. a babbl b 5 and b 2% a.
4 The Proposed Method
This section introduces the algorithm structures. Details about parameter selection are discussed to- gether with the theoretical analysis in Section Saanio respectively. For dataset D = {D...... D J. in which Dj C Red is the local dataset of the i-th user, denote my = [Pj as the sample size of the i-th user. Denote N as the total number of samples, then N E m,- We calculate the user-wise mean first, i.e. (D) = (1/m;) ExED, x. The new proposed estimator (before adding noise) is
(D(D) = arg min
(s)
(4)
in which we is the normalized weight of user i, i.e. the same for all i. oi is the Huber loss function:
E. Wi
If users are balanced, then w;
oi (i T; Is - yll TT?
|s - yl1
if
< Ti if s y > T.
ss
(5)
T, is the connecting point between quadratic and linear parts of Huber loss. For balanced users, w) and T; are the same for all users. For imbalanced users, w; and T; are set differently depending the per-user sample sizes. The general guideline is that w; increases with m,, while T; decreases with m,. The final output needs satisfy user-level (c, 8)DDP requirement. Hence, set
(6) in which Clip(v, R.) = v min (1, R [[vl]) is the function that clips the result into O, R.). The clipping operation used control the worst case sensitivity. W denotes the noise added to the estimated value. In this work, we use Gaussian noise W ~ (0, o²I). The clipping radius R. is determined by the knowledge of the range of μ.. Given prior knowledge ||ا/|| R. then we can set R. = R. Actually, similar to (55). our analysis shows that R can grow exponentially with n without significantly compromising the accuracy. The noise parameter o² needs be determined carefully through a detailed sensitivity analysis.
(D) = Clip(po(D)) R.) + W,
Now we comment the implementation. As has been discussed in 766 minimizing multi- dimensional Huber loss can be implemented by modification an iterative Weiszfeld's algo- rithm (8 82). The overall worst-case time complexity is O(nd/E, in which & is the desired precision. Moreover, for bounded support, with high probability, the algorithm requires only one iteration with time complexity ((d)). Details can be found in Appendix A
5 Analysis: Balanced Users
In this section, to gain some insights, we focus on the relatively simpler case and assume that all users have the same number of items, i.e. m. are equal for all i. Therefore, throughout this section, we omit the subscript and use m to denote the local sample size. Now w; = 1/n for all i. T; are also the same for all users, denoted as T in this section. Let X be a random vector, whose statistical mean μ := [[X] is unknown. Given dataset D (Di.... D,). the goal is to estimate μ. while

---

satisfying user-level (e, 8)-DP. We present the sensitivity analysis for the general dataset D first, and then analyze the estimation error for a randomly generated dataset. To begin with, define
(D) = max (D): - ((D)I,,
(7)
:E[n]
in which y(D) - (1/n) (() is the overall average. A small ((D indicates that the user- wise means y; are concentrated within small region. If (DD is large, then there are some outliers. The sensitivity bounded separately depending on whether the user-wise means are well concentrated. Throughout this section, we use (D) to denote the local sensitivity of (lop(Ao(D).)) Re), in which the subscript in (2) is omitted.
1) No outliers. We first bound the local sensitivity for the case with Z(D) < (1 - 2/n)T, in which T represents T; in (5) for all i. It requires that all y:'s ss's are not far away from their average.
Lemma 1. 1f (D) < (1 - 2/nn)T, then
T ((D) S
LS(D)
(8)
n
The proof of Lemmal] is shown in Appendix Here we provide some intuition. From the definition
(). local sensitivity is the maximum change of fv (D) after replacing some y: with y/- To achieve such maximum change, the optimal choice is to move y, sufficiently far away in the direction of Ao (D) yy, The impact of y, on (D) is roughly Z(D)/(n 1), while the impact of y is roughly T - 1). Since y; and y are at opposite direction with respect to An the overall effect caused by replacing y, with y is upper bounded by (T + Z (n- 1).
2) A few outliers. Now we consider more complex case: Z(D) is large, and the dataset is not well concentrated, but the number of outliers is not too large. Formally, assume that there exists another dataset D whose Hamming distance to D is bounded by k, and D is well concentrated. Then we have the following lemma to bound the local sensitivity.
For a dataset D. if there exists a dataset D such that du (D, (D,D*) S k, in which du is the Hamming distance (see Definition B. and (DD") (1 21k + 1)/n) T, then LS(D) 2T /T/(n- (n- k).
Lemma 2.
The proof of Lemma 2 is shown in Appendix C The intuition that since there exists a well concentrated dataset D with dæ (D, D*) k. D contains no more than & outliers. At least k other user-wise mean values fall optimal choice is to replace an outlier y, with y'. such that y; Ao (D) and y' - (D) have opposite directions. Each of them has an effect of roughly T/(n- - k) on (D)), thus the overall change is 2T 2T/(n k).
small region. To achieve the maximum change of (D), the
3) Other cases. For all other cases, since |/Clip(βo, R.)l S R2 always hold, the local sensitivity can be bounded by T.S(D)= < 2R..
From the analysis above, we now construct valid smooth sensitivity. Define
A(D) = min { 113D", (DD, Z(D* <
(9)
A(D) can be viewed as the number of outliers. From Df is well concentrated, with Z(D) < T/2 then A(D) 0. Now we define ((D, k) as follows.
Definition 5. (a) If (DD) < (1 - 2/n)T, k- = O, then G(D,0) = (T (())
(b) If conditions in (a) are not satisfied, and (DD) exists, if S n/4 A(D),
2T
G(D, k) n
(10)
A(D)
(c) If conditions in (a) and (b) are not satisfied, then G(D,k) = 2R.
Based on Definition 5 the smooth sensitivity is given by
S(D) max e 9k G(D,k) k),
(11)
in which / is determined in 3 Then we show that S(D) is valid smooth sensitivity, and the privacy requirement is satisfied.
5

---

Theorem 1. With o S(D)/a, in which a is determined in 3 W ~ (0,0 o²I), the estimator j defined in 66) (c. ().P.
To prove Theorem 1 we need to show that S is valid smooth sensitivity, i.e. two conditions in Definition 4 are satisfied. The detailed proof is provided in Appendix [
In the analysis above, all results are derived for general dataset D. In the remainder of this section, we analyze the performance of estimator (6) for randomly generated samples.
5.1 Bounded Support
Let X be a random vector generated from distribution P with an unknown statistical mean == E We make the following assumption:
Assumption 1. X is supported B₂(0, R) {ul ||||| R) C Rd
The mean squared error is analyzed in the following theorem.
Theorem 2. Let Re R. and T Cy + 1))/vm with Or 16/2/3. If (4/8) In(noo/T), then
R²
dR
B [IIADD) - m1]
mn²e² ln(mdd) In 8'
(12)
The proof of Theorem 2 is shown in Appendix B With the selection rule of T in Theorem 2 is shown that with high probability, A(D) O, indicating that D is expected to be well concentrated around the population mean The smooth sensitivity S(D) can then be bounded. The first term in the right hand side of (12) is the non-private estimation error, i.e. the error of (D))D,, while the second term the error caused by noise W. The condition n > (4/B) In(RR,/T) is necessary, since ensures that G(D, k) = 2R. (Definition (c)) occurs only for sufficiently large k, thus 9Bk is small, and does not affect the caleulation of S(D) in (I1). A lower bound on the number of users has also been imposed for the two-stage method (34].
For the simplest case with bounded support and balanced users, the two-stage approach in 34 already nearly optimal (Corollary in (34).. Therefore, improvement in polynomial factors impossible. Nevertheless, we still improve on the logarithm factor. The main purpose of Theorem 2 to show that our improvement on heavy-tailed distributions and imbalanced users is not the cost of hurting the performance under the simplest case with bounded distributions and balanced users.
5.2 Unbounded Support
Now we analyze the heavy-tailed case. Instead of requiring X E Ba R), we now assume that X has p-th bounded moment.
Assumption 2. Suppose that E B(0, R), and the p-th (p 2 2) moment of X is bounded, i.e. |||X||| S Mp.
In Assumption 2 higher indicates lighter tail and vice versa. We then show the convergence rate of mean squared error in Theorem
Theorem 3. Let Rs R, and
{VL..
( In 3(d+1) + 1)
2(3m) -1 - In 3(d (d++1)
T CT max
(13)
with == (d/(nc) and Cr > 8MB. Ifn > 8(1 + (1/3) In(n/2T)))) then under Assumption
2
E
|| (o(D))=11? 111 +
dIn(nd)
+
d
1-
In Inn(nd)
In 1
(14)
mn?e²
m2
The proof of Theorem is shown in Appendix F Here we provide an intuitive understanding. From the central limit theorem, each user-wise mean (D) is the average of m i..d variables, thus it has

---

Gaussian tail around the population μ.. However, since X is only required to have p-th bounded moment, the tail probability away from μ is still polynomial. The formal statement of the tail bound is shown in Lemma 13 in the appendix. Then the threshold 7 is designed based on the high probability upper bound of ((D to ensure that with high probability, A(D) is small. Regarding the result, we have the following remarks.
Remark 1. Here we comment on small and large in limits. If = 1, the right hand side of 14 (d/n222)1-1/p)) which matches existing analysis on item-level DP for haave- becomes O(1 /n (d
random variables 577. For the opposite limit, with ml-2/v Z n In (n(dd), then the convergence rate is the same as the case with bounded support, indicating that the tail of sample distribution does not affect the error more than a conslant factor.
Remark 2. Now we compare (14) with the two-stage approach. Following the analysis in (34)
can be shown that the bound of mean squared error in (34] is ((d/(n22)))1//m) + 4/9 2n p/))
(we refer to Appendix Gfor details). Therefore, we have achieved an improved rate in (1).
The theoretical results in this section summarized as follows. If the support is bounded, our method has the same convergence rate as the existing method. For heavy-tailed distributions, our approach significantly reduces the error, since method avoids the clipping process. In federated learning applications. it is common for gradients to have heavy-tailed distributions (41. thus our method has the potential of improving the performance of federated learning under DP requirements. Apart from heavy-tailed distributions, another common characteristic in reality is that users are usually imbalanced. We analyze in the next section.
6 Analysis: Imbalanced Users
Now we analyze the general case where m,, ix.i=1. l,..., n are different. Recall that for balanced users, we have defined (D) in ( that finds the maximum distance from (D) to their average (DD) For imbalanced users, instead of taking the maximum, we define Z, separately for each i:
- (DD) = - (D)Il,
(15)
in which y(D) = E.= (D) the average of samples all over the dataset.
From now on, without loss of generality, suppose that users are arranged in ascending order of mi i.e. my S ... S mn. Define
M(D.)) Li=n-ke k+1 w/ (T, ws:
(16)
Σ wy
Similar to the case with balanced users, analyze the sensitivity for datasets with no outliers, few outliers, and other cases separately.
1) No outliers. We show the following lemma.
Lemma 3. h(D 1) < min(T; (D)).. then LS(D) S 1))
The general idea of the proof is similar to Lemma 1 However, the details become more complex since now the samples are unbalanced. The detailed proof is shown in Appendix H
2) A few outliers. Similar to Lemma and then bounds the local sensitivity. The formal statement is shown in the following lemma.
2.
we find a neighboring dataset D that is well concentrated
Lemma 4. For a datasel D, if there exists another dataset D* such that (DD", k 1) < min, -
Z, (D")), then LS(D)) < 2 (w.T)/ Di
k-- k=
Wi.
The proof of Lemma 4 is shown in Appendix D which just follows the proof of Lemma 2
3) Other cases. Finally, for all cases not satisfying the conditions in Lemma and we can just bound the local sensitivity with 2R,,, i.c. LS((D) I 2R.-
Similar to the case with balanced users, now we define
A (D) min(k (D (D,
= ks h(D"",oo
(17)
in which ho any integer, and can be viewed as a design parameter. Correspondingly, the smooth sensitivity G(D, k) is defined as follows.
7

---

Definition 6. (a) If S min(I; - Z,(D)), then G(D.0) h(D.1);
(b) If the conditions in (a) are not satisfied, and (D) exists, then for all k S ko - A(D) - 1,
2maxw;Ti
icIn]
G(D,k)
(18)
((-A(D)--A
2i=1
(c) If the conditions both (a) and (b) are not satisfied, then G(D,k) 2R..
We still the same settings of a and 33 as in the case with balanced samples. With smooth sensitivity calculated using (TT). the privacy requirement satisfied:
Theorem 4. Let W ~ NO, (S(D))/aa) in which S(D) = maxe 8h GDD, k). then the estimator is (y.
Now we analyze the convergence of the algorithm. We begin with Assumption 3 Intuitively, this assumption requires that the users can be too unbalanced. At least half samples belong users whose sample sizes are not very large.
Assumption 3. Suppose there exists a constant 7 2 1. Let he minfi/m; > yN/n}, then Re m, - N/2.
In Assumption 3 7 can be viewed the degree of imbalance. For better explanation, we provide the following examples:
If users are balanced, then 7 1;
If the i-th user has ki samples (which means that the number of items belonging to each user is linear in its order), then for large is approximately v2.
In general, 7 is large if users are highly imbalanced. Under Assumption squared error shown in Theorem 5
3 the convergence of mean
Theorem 5. Let the weights users in be Wi mrAme/ myAme). which m. = 7N/n. Moreover, let
12 1IIn(Nn((+11)
T: Cry
(19)
mi A me
in which CT > 16/2/33 In 17 Ro = |n/8y].
With the parameters above, in > 8y(1 + (1/28) In (NN))), then under Assumption 7 and
(D) - μl S R²
dR²
In (Nnd) In 8'
(20)
N
Nne
The proof of Theorem is shown in Appendix J If users are balanced, then = 1, with N = nm, (00 reduces [2) From (20) and Assumption Bt can be observed that our method much less sensitive to single large m, As long as m, are not very large for most users, the convergence rate of mean squared error is not affected. There are two intuitive reasons. Firstly, w; is upper bounded by me/ (Ej=1 my A m.), thus the worst-case sensitivity is controlled. Secondly, T; are set adaptively to achieve a good tradeoff between sensitivity and bias. With larger m,, smaller T; is used, and vice versa. We refer to Appendix for comparison with the two-stage approach.
7 Numerical Examples
In this section, we show numerical experiments. We compare the performance of our new Huber loss minimization approach (denoted as HI.M) versus the two-stage approach proposed (34), called Winsorized Mean Estimator (denoted as WME).

---

7.1 Balanced Users
Here all users have the same sizes of local datasets. In the following experiments. we fix e = 1 and 5 1005. For fair comparison, the parameter T for our method well as 7 in (34] are both tuned optimally for each case. Figure I shows the curve of mean squared error. Let the number of users be either 1, 000 and 10, 000. In each curve, is fixed, while the number of samples per user m varies from to 1, 000. The results are plotted in logarithm scale. Figure Figure[Ta)-(C show the results of uniform distribution in [-1,1], 1], Gaussian distribution (0, 1), and the Lomax distribution, whose pdf is [x) = a/(1 + x:) )r)=t (we use a = 4 in Figure (c)) Figure 1 (d)-(f) shows the corresponding experiments with dimensionality d = 3. Finally, Figure (g) and (h) show the results using the
IPUMS dataset [83] for total income and salary, respectively, which are typical examples of data following heavy-tailed distributions.
1E% PARRE
10
(U% 1-000
10
LN 1-0000
357
IUN I-1
10
20
10/
1044
10
10
32
(a) Uniform, d
(b) Gaussian, d
(c) Lomax, d
(d) Uniform, ==
101
We. 1-12
Var
10
300
10
30
10
100
10'
30
(e) Gaussian, d
(f) Lomax, =
(g) IPUMS. total income
(h) IPUMS, salary
Figure 1: Convergence of mean squared error with balanced users.
Figure 1 (a) and (b) show that for one-dimensional uniform and Gaussian distribution, the Huber loss minimization approach has nearly the same performance as the two-stage method. Our explanation is that uniform and Gaussian distributions are symmetric, with no tails or light tails, thus the clipping operation does not introduce additional bias. However, for heavy-tailed and skewed distribution, such as Lomax distribution, our new method has a significantly faster convergence rate than the two-stage method. These results agree with the theoretical analysis, which shows that our method reduces the clipping bias. With higher dimensionality, Figure d)) show that the advantage of the practical performance of our method becomes more obvious.
7.2 Imbalanced Users
Now show the performance with unbalanced users. For some 7 2 let 8; [N(i/)) for i = O,..., n, and m, = s; S;-1 for = l....,, n. It can be shown that Assumption Bs satisfied with 7. Therefore, according the analysis in Section 6 we let w; = my A Am/ Σ, ,, m, A me, with m. = >NN/n, and T, = A/ /m, A m. in which A is tuned optimally for each case. The selection of T, may be slightly different from (19) in Theorem 5 In Theorem 5 T; is sclected to minimize the theoretical upper bound. To ensure that the analysis is mathematically rigorous, the upper bound of estimation error is larger than the truth. Therefore, the optimal value of T; in practice is slightly different from that derived in theories. Note that such parameter tuning does not require additional privacy budget since in each experiment, T; are hyperparameters that is fixed before knowing the value of each sample. They are not determined adaptively based on the data. Figure 2 shows the growth curve of mean squared error with respect to 7.
From Figure 2 can be observed that with the increase of 7, the two-stage method degrades, while the Huber loss minimization approach performs significantly more stable.

---

0.0004
HAM POTOOS
6:00375
8,0000
0-00000
F-20000
200603
USC VISEUE
2,000
80003
380600
8.0002
6.3003
6.30005
(a) Uniform.
(h) Gaussian.
(c) Exponential.
(d) IPUMS total income.
Figure 2: Growth of mean squared enror with degree of imbalance 7
8
Conclusion
In this paper, we have proposed new approach to mean estimation under user-level DP based on Huber loss minimization. The sensitivity bounded for all possible datasets. Based on the sensitivity analysis, we use the smooth sensitivity framework to determine the noise added to the result. We have also derived the bound on the mean squared error for various cases. The result shows that our method reduces the error for heavy-tailed distributions, and is more suitable to imbalanced users. It is promising to extend our approach to more learning problems, such as calculating average gradients in federated learning.
The limitations of our work include: (1) There are some requirements on the minimum number of users n. while entirely removing this condition is impossible, to make our method more practical, we expect that it can be somewhat weakened. (2) The case with local sample sizes m, also being private has not been analyzed. We will leave these two points as future works.
Limitations:
Acknowledgement
The work of L.Shen is supported by the STI 2030- Projects (No. 20212I0201405), The work of Z.Liu is supported by the National Natural Science Foundation of China NN.62132008 and U22B2030), Natural Science Foundation of Jiangsu Province (BK20220075). The work of L.Lai is supported by the National Science Foundation under grants ECCS-20-00415 and CCF-22-32907.
We thank Prof.Gautee Gautam Kamath for his fruitful discussions.
References
[1] Dwork, C.,, F. McSherry, Nissim, al. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY. USA, March 4-7, 2006. Proceedings 3, pages 265-284. Springer, 2006.
[2] Dwork, C., G. N. Rothblum, S. Vadhan. Boosting and differential privacy. In 2010 IEEE 5 Annual Symposium Foundations of Computer Science, pages 51-60. IEEE, 2010.
[3] Kasiviswanathan, S. P., H. K. Lee, K. Nissim, et al. What can learn privately? SIAM Journal on Computing, 40(3):793-83) 2011.
[4] Dwork, C., A. Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trendy in Theoretical Computer Science, 9(3-4):211 21::)1171077, 2014.
[5] Wang, S., L. Huang, Y. Nie, et al. Local differential private data aggregation for discrete distribution estimation. IEEE Transactions on Purallel and Distributed Systems, 30(9):2046- 2059, 2019.
[6] Huang, Z., Y. Liang, K. Yi. Instance-optimal mean estimation under differential privacy. Advances Neurul Information Processing Systems, 34:25993-26009 2021.
[7] Asi, H., V. Feldman, K. Talwar. Optimal algorithms mean estimation under local differential privacy. In International Conference on Machine Learning, pages 1046-1056. PMLR, 2022.
[8] Hopkins, S. B., G. Kamath, M. Majid. Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism. Proceedings of the 54th Annual ACM SIGACT Symposium Theory of Computing, pages 1406-1417. 2022.
10

---

[9] Nguyên, T. T., X. Xiao, Y. Yang, et al. Collecting and analyzing data from smart device users with local differential privacy. arXiv preprint arXiv: 05053, 2016.
[10] Sun, C., Y. Fu, Zhou, et al. Personalized privacy-preserving frequent itemset mining using randomized response. The Scientific World Journal, 2014, 2014.
[1I] Chaudhuri, K., C. Monteleoni, A. D. Sarwate. Differentially private empirical risk minimization.
Journal of Machine Leurning Research, 12(3). 2011.
[12] Bassily, R., A. Smith, A. Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foundations of computer science, pages 464-473. IEEE, 2014.
[13] Bassily, R., V. Feldman, K. Talwar, et al. Private stochastic convex optimization with optimal rates. Advances in neural information processing systems, 32, 2019.
[14] Feldman, V. T. Koren, K. Talwar. Private stochastic convex optimization: optimal rates in linear time. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 439-449, 2020.
[15] Asi, H., V. Feldman, T. Koren, et al. Private stochastic convex optimization: Optimal rates in 11 geometry. In International Conference on Machine Learning. pages 393-403, PMLR, 2021.
[16] Cheu, A., M. Joseph, J. Mao, et al. Shuffle private stochastic convex optimization. In Interna- tional Conference on Learning Representations. 2022.
[17] Shokri, R., V. Shmatikov. Privacy- preaeeving deep learning. In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, pages 1310-1321. 2015.
[18] Abadi, M., A. Chu, I. Goodfellow, et al. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages -18. 2016.
[19] McMahan, H. B., D. Ramage, K. Talwar, et al. Learning differentially private recurrent language models. arXiv preprinl arXiv:1710.0690 2017.
[20] Dan, H.-C., B. Lu. M. Li. Evaluation of asphalt pavement texture using multiview stereo reconstruction based on deep learning. Construction and Building Materials, 412:134837, 2024.
[21] Dan, H.-C., P. Yan, J. Tan, et al. Multiple distresses detection for asphalt pavement using improved you only look once algorithm based on convolutional neural network. International Journal of Pavement Engineering, 25(1):2300 169, 2024.
[22] Wang, X., Y. Wang, Y. Su, et al. Ensguard: A novel acceleration framework for adversarial ensemble learning. IEEF Transactions on Computer-Aided Design of Integrated Circuits and
Systems, 43(10):3088-311 -1011 2024.
[23] Mo, K., P. Ye, X. Ren, et al. Security and privacy issues in deep reinforcement learning: Threats and countermeasures. ACM Computing Surveys, 56(6):1-39, 2024.
[24] Huang, R., H. Zhang, L. Melis, et al. Federated linear contextual bandits with user-level differential privacy. In International Conference on Machine Learning, pages 14060-14095. PMLR, 2023.
[25] Li, T., Song, C. Fragouli. Federated recommendation system via differential privacy. In 2020 IFEE international symposium on information theory (ISIT), pages 2592-2597, IEEF, 2020.
(26) McSherry, F., I. Mironov. Differentially private recommender systems: Building privacy into the netflix prize contenders. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 627-636. 2009.
[27] Geyer, R. C., T. Klein, M. Nabi. Differentially private federated learning: A client level perspective. arXiv preprint arX1v:1712.07557, 2017.
[28] McMahan, H. B., G. Andrew. U. Erlingsson, et general approach to adding differential
privacy to iterative training procedures. arXiv preprint
2018.
[29] Wei, K., J. Li, M. Ding, et al. Federated learning with differential privacy: Algorithms and performance analysis. IEEE transactions on information forensics and security, 15:3454-3469, 2020.
[30] Kairouz, P., B. McMahan, B. Avent, al. Advances and open problems federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-210, 2021.

---

[31] Fu, J., Y. Hong, X. Ling, et al. Differentially private federated learning: A systematic review. arXiv preprint arXiv:2405.088 08099, 2024.
[32] Feng, J., Y. Wu, H. Sun, et al. Panther: Practical secure 2-party neural network inference. IEEE Transactions on Information Forensics and Security, 2025.
[33] Liu, Y., A. T. Suresh, F. X. X. Yu, al. Learning discrete distributions: user vs item-level privacy. Advances in Neural Information Processing Systems, 33:20965-2099 2020.
[34] Levy, D.. Z. Sun, K. Amin, et al. Learning with user-level privacy. Advances in Neural
Information Processing Systems, $4:12466-12477 12479, 2021.
[35] Ghazi, B., R. Kumar, P. Manurangsi. User-level differentially private learning via correlated sampling. Advances Neural Information Processing Systems, 34:20172-20121 2021.
[36] Ghazi, B., P. Kamath, R. Kumar, al. User-level differential privacy with few examples per user. Advances in Neural Information Processing Systems, 36, 2023.
[37] Yarlagadda, K., Hershey. Hadamard matrix analysis and synthesis: with applications to communications and signal/image processing, vol. 383. Springer Science & Business Media, 2012.
[38] Li, T., M. Sanjabi, A. Beirami, et al. Fair resource allocation in federated learning. In International Conference on Learning Representations. 2019.
[39] Duan, M., Liu, X. Chen, et al. Self-balaneing federated learning with global imbalanced data in mobile systems. IEEE Transactions on Parallel and Distributed Systems, 32(1):59-77 2020.
[40] Gong, B., T. Xing, Z. Liu, et al. Adaptive client clustering for efficient federated learning over non-iid and imbalanced data. IEEE Transactions on Big Data, 2022.
[41] Gurbuzbalaban, M., U. Simsekli, L. Zhu. The heavy-tail phenomenon in sgd. In International Conference on Machine Learning, pages 1964-3975 PMLR, 2021.
[42] Simsekli, U., L. Sagun, M. Gurbuzhalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference on Machine Learning, pages 5827-5837. PMLR, 2019.
[43] Zhang. J., S. P. Karimireddy, A. Veit, et al. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 13:15383-153993 2020.
[44] Nguyen, T. D., T. H. Nguyen, A. Ene, al. Improved convergence in high probability of clipped gradient methods with heavy tailed noise. Advances in Neural Information Processing Systems, 18:24191-24222 2023.
[45] Ke, Z., Y. Yin. Tail risk alert based on conditional autoregressive var by regression quantiles and machine learning algorithms. arXiv preprint arXiv:24/2.06193, 2024.
[46] Zhang, J., Z. Xu. Exponential calibration for correlation coefficient with additive distortion measurement errors. Statistical Analysis and Data Mining: The ASA Data Science Journal, 14(3):271-289, 2021.
[47] Huber, P. J. Robust statistics, vol. 523. John Wiley & Sons, 2004.
[48] Nissim, K., S. Raskhodnikova, A. Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium Theory of computing, pages 75-84. 2007.
[49] Wang, 7.,, Y. Huang, M. Song, et al. bissoning-assistee property inference attack against federated learning. IEEE Transactions Dependable and Secure Computing, 2022.
[50] Lyu, W., S. Zheng, I.. Pang, et al. Attention-enhancing backdoor attacks against bert-based models. In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 10672-10690. 2023.
[51] Lyu, W., L.. Pang. Ma, et al. Trojvim: Backdoor attack against vision language models. European Conference on Computer Vision, 2024.
[52] Liu, X., W. Kong, S. Kakade, et al. Robust and differentially private mean estimation. Advances in neural information processing systems, 34:3887-3901, 2021.
[53] Liu, X., P. Jain, W. Kong, et al. Label robust and differentially private linear regression: Computational and statistical efficiency. Advances Neural Information Processing Systems, 36, 2023.
12

---

[54] Qi, T., H. Wang, Y. Huang. Towards the robustness of differentially private federated learning. In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 38, pages 1991 1-19919. 2024.
[55] Li. M., T. B. Berrett, Y. Yu. On robustness and local differential privacy. The Annals of Statistics, 51(2:717-737, 2023.
[56] Smith, A. Privacy-preseringg statistical estimation with optimal convergence rates. In Pro- ceedings of the forty-third annual ACM symposium on Theory of computing, pages 813-822. 2011.
[57] Kamath, G., V. Singhal, Ullman. Private mean estimation of heavy-tailed distributions. In Conference on Learning Theory, pages 2204 2235. PMLR, 2020.
[58] Bassily, R., Z. Sun. User-level private stochastic convex optimization with optimal rates. In International Conference on Machine Learning, pages 1838-1851, PMLR, 2023.
[59] Liu, D., H. Asi. User-level differentially private stochastic convex optimization: Efficient algorithms with optimal rates. In International Conference on Artificial Intelligence and Statistics, pages 4248. PMLR, 2024.
[60] Cummings, R., V. Feldman, A. McMillan, et al. Mean estimation with user-level privacy under data heterogeneity. Advances in Neural Information Processing Systems, 139-29151,, 2022.
[61] Bun, M., M. Gaboardi, M. Hopkins, et al. Stability is stable: Connections between replicability, privacy, and adaptive generalization. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing. pages 520-527. 2023.
[62] Acharya, J., Y. Liu, Sun. Discrete distribution estimation under user-level local differential
privacy. In International Conference on Artificial Intelligence and Statistics, pages 8561 8561-8585. PMLR, 2023.
[63] Zhao, L. Shen, R. Fan, et al. Learning with user-level local differential privacy. arXiv preprint 1055 2024.
[64] Ma, Y. K. Jia, H. Yang. Better locally private sparse estimation given multiple samples per user. arXiv preprint arXiv:2408.cm 04311, 2024.
[65] Dwork, C., J. Lei. Differential privacy and robust statistics. In Proceedings of the forty-first anmual ACM symposium on Theory of computing, pages 371-380. 2009,
[66] Liu, X., W. Kong, S. Oh. Differential privacy and robust statistics in high dimensions. In Conference on Learning Theory, pages 1167-1246. PMLR, 2022.
[67] Bun, M., T. Steinke. Average-case averages: Private algorithms for smooth sensitivity and mean estimation. Advances in Neural Information Processing Systems, 32, 2019.
[68] Asi, H., J. Ullman, L. Zakynthinou. From robustness to privacy and back. In International Conference Machine Learning, pages 1111-1166. PMLR, 2023.
[69] Asi, H., J. C. Duchi. Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms. Advances in neural information processing systems, 13:14006-14117, 2020.
[70] Diakonikolas, I., G. Kamath, D. Kane, al. Robust estimators in high- digge-iimsssons without the computational intractability. SIAM Journal on Computing, 48(2):742- 864, 2019.
[71] Diakonikolas, I., G. Kamath, D. M. Kane, et al. Being robust (in high dimensions) can be practical. In International Conference on Machine Learning, pages 999-1008 PMLR, 2017.
[72] Diakonikolas, I. D. M. Kane. Algorithmic digh-diimes robust statistics. Cambridge university press, 2023.
[73] Hall, P., M. Jones. Adaptive m-estimation in nonparametric regression. The annals of statistics, pages 1712-1720 1728, 1990.
[74] Zhao, P.,, Z. Wan. Robust nonparametric regression under poisoning attack. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 17007-17015. 2024.
[75] Sardy, S., P. Tseng, A. Bruce. Robust wavelet denoising. IEFE transactions on signal processing, 1et:1114611222. 2001.
13

---

[76] Zhao, P., F. Yu, Z. Wan. A huber loss minimization approach to byzantine robust federated learning. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 2024.
[77] Avella-Medina, M., C. Bradshaw, P.-L. Loh. Differentially private inference via noisy optimiza- tion. The Annals of Statistics, (165)226772292, 2023.
[78] Song, S., T. Steinke, O. Thakkar, al. Evading the curse of dimensionality in unconstrained private glms. International Conference on Artificial Intelligence and Statistics, pages 2638- 2646. PMLR, 2021.
[79] Agarwal, S., G. Kamath, M. Majid, et al. Private mean estimation with person-level differential privacy. arXiv preprint arXiv:2405.2040) 2024.
[80] Wei, K., J. Li, M. Ding, al. User-level privacy- mrivacy-rreeerving federated learning: Analysis and performance optimization. IEEE Transactions on Mobile Computing, 21(9):3388-3400 2021.
[81] Weiszfeld, E., Plastria. On the point for which the sum of the distances to n given points is minimum. Annals of Operations Research, 167:7-41, 2009.
[82] Beck, S. Sabach. Weiszfeld's method: Old and new results. Journal of Optimization Theory and Applications, 164:1 164:1-40, 2015.
[83] Ruggles, S., S. Flood, M. Sobek, al. IPUMS USA: Version 15.0 [dataset], 2024.
[84] Sun, L., J. Tian, G. Muhammad. Fedke: Personalized federated learning with robustness against model poisoning attacks in the metaverse for consumer health. IEEE Transactions on Consumer Electronics, 2024.
[85] Sun, L.,, J. He. An extensible framework for ecg anomaly detection in wireless body sensor monitoring systems. International Journal of Sensor Networks, 29(2):001-110, 2019.
[86] Zhang, Y., L. O. Wijeratne, S. Talcbi, al. Machine learning for light sensor calibration. Sensors, 21(18):625,, 2021.
[87] Lary, J., L. O. H. Wijeratne, G. K. Zewdie, et al. Machine learning, big data, and spatial tools: A combination to reveal complex facts that impact environmental health. In Geospatial Technology for Human Well-Being and Health, pages 219-241. Springer, 2021.
[88] Tropp, J. A., et An introduction matrix concentration inequalities. Foundations and Trends@ in Machine Learning, 8(1-2):1-230, 2015.
14

---

A Comments About Algorithm Implementation
In this section, we describe the algorithm for Huber loss minimization. In particular, we solve
arg min
w.
(21)
From 5 can be shown that
E ua min
(1, ||e-y.l Yi T. ||e-yii vill
c
(22)
E to min
The algorithm can be designed from above equation. Suppose that the algorithm starts from Co- The update rule is
En wa min
7: vill
y: yill
Ck+1
(23)
E Wy min
||a,
23
iteratively until the norm of update ||cg+1 cjall between two iterations is less than Ç.
provide brief analysis on the computational complexity as follows.
Worst case. [22 has shown that the Weiszfeld's algorithm for calculating geometric median needs O(1/E) steps achieve precision E. The proof can also be used to our algorithm (23). Moreover, from 23). each step requires ((nd) time, in which d is the dimensionality of y:, thus the overall time complexity is O(nd/E).
Common case. From the analysis Section and for bounded support, with high probability, (DD < T holds for balanced users, and (,(D)) T; holds for imbalanced users. In this case, can just calculate the result within one step:
w.ys
(24)
Therefore the time complexity (nd)).
B Proof of Lemmal 1
Now the users are balanced.
and 5 becomes
Ao DD( arg min Σ yls.y,
(25)
and
s - y
if Is y < ss - y > T.
d(s
(26)
T
y|l
T
if
In this section, we prove strengthened version of Lemma continuity as Definition 7. (Modulus of continuity) Define
for future usage. Define the modulus of
wD,
sup [lāo(D) - Ao(DD))
(27)
D':dn (D.
From the definition, wDD,0) is just the local sensitivity LS(D). Then we show the following lemma.
Lemma 5. IDD) < (1 2k 3k/n)T, then
KT + Z(D))
wDD, k))
(28)
n k
15

---

Let k = 0, then Lemma reduces to Lemma] Lemma
The remainder of this section shows the proof of
According to 27 w ((D, k) is the supremum change after replacing all items belonging to k users.
Denote D'' dataset such that di (D, D*) I k. Let 7 be the set of users such that D3 # D/- Throughout this section, we denote y, (D) and y (i())) for simplicity.
From 25
(D() = arg min
Σ iET
ofs oss +
Σ y(s
(29)
iE[n]/
Let Vá be the gradient of & with respect to the first argument. Define
g(s)
Σ
Vo(s, + Σ Vo)s,
(30)
IE!
iE/n]M
then
((ao(D')) O,
(31)
and
s(po(D)) = Σ vo) +
Σ Vo(ioD).
iE!
Σ Vo(Ho(D).y)) vo( Σ
Vo(Ro(D),x.)
iel
iE(m)
vo(Ro(D).
VD(.)(
(32)
EE
E
in which the last step comes from
25
Then show the following lemma.
Lemma 6. If (D) - T, then (D( y, in which y (1/n) E Y
Proof. The proof has two steps.
(I) y is minimizer of ET= d(s, y:). From (26).
if - y; <T T --xl if s y: TT Vols,yr) {
s-y.
(33)
in which the second step holds because || -vll < Z < T. Moreover, En ((s,y,) is convex, thus y a minimizer.
(2) y is the unique minimizer. The Hessian
a o(y.y.) 2 1 - yıl S T) = n.
(34)
Therefore Σin y.) is strong convex around y, and thus y is unique.
From 30
k Voly. +
(g(()(
Vo(v.y))l
< KT Σ 1 -vil
< k(T + Z(D).
(35)
16

---

Moreover, for s satisfying |s - 155ll ST TT-22 - Z.
Vg(() Σ (ss
Σ Vob(s,,)
i=++1
Σ
1[|s- I)
i=k+1 (n I,),,
(36)
in which the last step holds because
||s y:ll - ||s y11 + 11 yil || S T Z(D) + Z(D) =T.
(37)
Let L be path connecting Lo (D) and io (D)) Then
/ gg(s) ds
(lo(Ao(D)) (0000
N (n k) min (1) (a((D)) (T-(("))II--("") Z(D))
(38)
Note that from
31 and
(35
- ((Po(D S K(T + Z(D)).
(39)
From the condition 7(D) < (1-2k: 222n//) Lemma 1 (m-h)) (T- K(T Z(D)) Hence,
38
and
39
yields
((T+((D))
[lAo(D)) AAo S
(40)
n- k
C Proof of Lemma 2
Denote D' dataset adjacent D user-level. Then it remains to bound (D)) Aa (D')l Recall that in the statement of Lemma 2 we have required that there exists a dataset D such that ((D)) (1 2(k + 1)/n)T, and du (D, D k. Denote 7 as the set of users such that D and D have different values, while D and D' differ at user u. Now we discuss two cases.
Case 1. & 1. In other words, D and D' differ at user that is the same between D and D*. In this case, D' has & + I users that are different from D Without loss of generality, suppose that I = {1, .1.....A. f.,, while k 1. D", D and D' can be written as follows:
D* (Di Dn).
(41)
D (D..... D2. D Dr))
(42)
D' = (D)...., D'+11 D Dn).
(43)
For convenience of expression, denote y; = (D) and y! (D))). In this section, define (1(s) as follows:
k+1
91 (s) Σ
Vo(s,y)) + Σ Vols,y.).
(44)
1=1
*=
then
(i(Ao(D')) = O,
(45)
and
(1oo(D)) (D((o(D),)]) +
Σ Vol(o(D).
i=k+2
= Σ (o(io(D).))) + Σ Volūo(D).
i=k+1
(V)(RO(D), ((41) (o(
(o(Ao(D),N' - Vo(io(D))
(46)
17

---

Therefore
(Po())
IA3 3V
T + (D) - yk+1ll
T (Do) Ao +ly(("))))))))) - yk+1ll
IA
T wD", (D",)) k) + (D*).
(47)
(a) comes from (33 By taking gradient over 8, we have Vo((s min yll)- (b) comes
from Lemma which states that (D) = y.
For all s satisfying |s (D(D)) - T - Z(D") - w (D*,
k+1
(s)
Σ
v'o(s,(')
Σ vi)
k=++
1(|s - yvll ST)
z (n 1)I,
(48)
which the last step holds because
||s
ysll
$ Is - Po(D) + (l - y lly - -.
< T - Z(D") - w(D" k) + w(D" ,A) Z(D")
T.
(49)
Then
1/ (s)dss
(lgı(ão - 9i (Po(
(n k min (D) - ( Z(D") w("", kk),
(50)
which the line connecting Ao (D) and (D')
From 45) and (47
1.91 (Ao 91 (Ro <T (D'",, Z(D))
(51)
From the condition Z(D") < (1 - 2(k: + 1)/n/ in Lemma
(n h - - (DD" > T' + (D' k) + Z(D").
(52)
Hence
19 (D)) 9I (Ao (D))) < (n - k - 1)(T 2(D") (D"", k)).
(53)
From
50 and
53). the second element in the minimum bracket in 50)) will not take effect. Hence,
( (D)'l < T - Z(D") - (D' k).
(54)
54 will be useful in the analysis of the second case. From 50 and 53 we can also get
T + (D", k) + Z(D*)
[D) (Do
<
n k
n
(T +DD)),
(55)
(n (n-k k 1)(n - k)
in which the last step uses the bound w(D", k) in Lemma ( (D')l for the first case.
Now we have bounded
Case 2: u E In other words, D and D' differ in a user that is different between D and Dr. Without loss of generality, suppose that I = {1, k). and k. D³, D and D' can be written as follows:
D'
(56)
D (D D'. Dr4...... Dzh.
(57)
D' (D),.... D/-1, D% D Dr-1...... D.}.
(58)
18

---

In order to bound [IAo(D) - Ao((D)) |I, we construct a temporary dataset Diemp as follows:
D4-1: Diamp (D)..... : Da..... Dn).
(59)
Define
(2(s) Σ Vo(s,y') + vo(s.
Vo(s.y.).
(60)
Then (2(Ao(D') 0, and
92()o(D)) = Vo(Aa(D).>1) - (D)
(61)
From
33
( (Ano S 2T.
(62)
Now we bound (D) - (D())) Corresponding to (54). we get
(Dremp)) Ao (D)ll < -
1),
(63)
and
Ao (Ptemp)
Ao (D))
< <T Z(D") WD" k-
(64)
Denote L as the line connecting Ak D
and AD')). For all s E L, ||s -oo (a(eeem)) s TT-Z(D")
w(D", k - 1). Corresponding to 48
for all s E L,
Vg2(s) = (n IJI. I.)..
(65)
Therefore
- -22((((()))((((( 2 (n-h)) 1 Ao (D')ll
(66)
From 62 and (66).
2T
lIAo(D) - ~
(67)
11
Combine case and 2, we get
n(T + Z(D"))
2T
LS(D)
< max
(n k: 1) k) n
27
(68)
n- k
The last step comes from the requirement that Z(D*) < (1 - (1-2(k + 1)/n)T. The proof is complete.
D Proof of Theorem 1
Two requirements on smooth sensitivity are shown in Definition i.e.
(1) For any D, S(D) 2 LS(D);
(2) For any neighboring D and D'. D'D)(D) < e S(D")
It has been shown in (48) that based on (1) and (2), the final result is (c.P). In the remainder of this section, we show that both requirements (1) and (2) are satisfied.
For (1), from Lemma I and LS(D) < G(D, 0) if the corresponding conditions are satisfied. If these conditions not satishidd since |[Clip( (D),, R&)ll I R, always hold, the sensitivity can always be bounded by 2R, Hence LS(D) < G(D,0) holds for all D. From (II). G(D,O) < S(D). Therefore the requirement (1) satisfied.
For (2), it suffices to show that G(D,k) S G(D', l + 1). From Lemma 2 if A(D)) exists, and k + 1 < n/4 - - A(D'), then
2T
G(D',k+1)
(69)
n1 n- - A(D)
19

---

From the definition of A in ② since D and D' are adjacent, A(D) Σ A(D) + 1 holds. Therefore,
the condition & + n/4 A(D yields k S n/4 - 1 (D). Use Lemma 2 again, we get
2T
G(D,k)
n k - A(D)
21
n K 1- A(D)
G(D',k:+)
(70)
If the conditions in Lemma 2 are not satisfied, i... (D') does not exists or k ++1> n/4-1-A(2)) then G(D', + 1) = 2Rc. thus G(D, k) & G(D', k + 1) holds.
Now we have shown that no matter whether the conditions in Lemma holls, we always have G(D,k) k) G(D', k + 1). From (TT). can be easily shown that S(D) S e (S(()).
E Proof of Theorem 2
In this section, we analyze the practical performance of the estimator for a random dataset.
Notation. Throughout this section, for convenience, we just denote Z = Z(D), Y, (D(D) and Y (D) for simplicity. We use capital letters here since random, thus Y, and Y are random variables.
From Lemma 11 in Section K for i 1,..., n1
3ma2
P( - H|ll > t) S (d 1)e
32R7
(71)
Recall that Z max; Y 8 If Y - la|| S 1/2 for all i, then Y - All s t/2 also holds, thus Z < Therefore
P(Z 1) < Σ
Y
wll 1 2
i=1
S n(d 1)e
(72)
Define
128
Zo
In(mn3 (d+ 1)).
(73)
3m
Then
P(Z Zo) 5 mm?
(74)
Recall that
R Vm
T CT In(mn (d + 1));
(75)
with Cr > 16/2/3. Then with probability at least 1 - 1/ 1mmm?), 2 S T/2 holds, thus
S(D) = max e 3h G(D,))
Bk 2T kSn/4-1
k 2R. tnz
max
max
(76)
Note that in the statement of Theorem
required that > (4/3) This yields
2R. m3/4 -B8/4 2T / n, and -Bk2T k) decreases with k. Therefore
S(D) < 21
(77)
n
20

---

It remains to bound the estimation error. The mean squared enror of mean estimation can be decomposed in the following way:
E [A(D) m1l)
E |IClip(@o (D), R) W =l|]]
E [|Clip(Ao (D): R) 14l?] + [|[[W]]
E
(D) u1l 1(Z < 2o) +E
+ ||
1(2 & 20)
+E
|Clip((oo It) - 1l| 1(2> > 2o)
+E
| 1(2 > Zo)
1 + 12 + 13 + I4.
(78)
(a) holds because E. W DJ = 0 for any D, thus (D) - μ and W are uncorrelated. Now we bound these four terms separately.
Bound of 11. From Lemma for Z < Rln(nd)/ m m., Z < T holds, thus (o(D) = Y. For convenience, denote Y as i.d copy Y ,, i = .,..,,, n and X an mni copy Xij. 1, ...... n.
j = ,,..., m. Then
R
2
R m
in(nd) )
4
E
p
71
E
1
||Y
11 12]
E
||X - 10117]
mm
R²
(79)
mn
Bound of Iz.
(0)
(D)1 < Zo)
d
T2
5
a²
(6)
T2d
5
n²a²
(e)
dR²
1 In 3 In 5"
(80)
mn2.2
(a) holds because W NO, (I)) (b) comes from (7). (c) comes from
Bound of Tz. From 74
Is < 4R (Z > %o)
4R²
(81)
mn=
Bound of 44-
1
<
(D)1( > Zo)
a²
dR²
P(Z Zo)
a
dRt 1
V2
In
(82)
mn?22
21

---

Now all four terms in 78 have been bounded. Therefore
[I((D)
ull?]
x
R
dR² mn?e²
1 8" In(mn' d) In
(83)
mn
The proof is complete.
Proof of Theorem
3
In this section, following Appendix Define
E we still denote Y; y; and Y y(D) for simplicity.
1 In
3(d
4Mg (3m))-1v=- In 3(d
ro max
2M
(84)
m
in which (dd(nc). From the statement of Theorem
T > 4ro. From Lemma 13
Vd
P(IY;: all > ro) S セー=
(85)
716
Define
nout E1(11 nll ro).
(86)
Then nour follows a Binomial distribution with parameter (n. p) with S 1/n. E[nous] S 1. This indicates that with the increase of n, the number of outliers is still bounded by O(1) with high probability.
Lemma 7. A(D,k) < Nont for k < n/4 Thmtt 1.
Proof. From the dataset D. construct DD* follows. Let (Di.... DR) such that D D, || pll & ro, and D; is an arbitrary set with mean value μ.. In other words, denote Y as the mean value in DJ, then
( Y, if Y M S ro
Y
(87)
pb if
Y; p ro-
Then (D, Poutt Let Y (L/n) Diz
Y Note that
Z(D") max
Y ml max Y all < 2ro =T
(88)
k)) can be bounded using Definition Since R. R, for t: 2 n/4 -out - 1, G(D,k) k) S 2R.
Therefore, for sufficiently large n, if nout < n/88 then
A maxe 3k G(D,k)
27
W
max
max
e -((a/4--ouu
k<n/4 Moonttnoot- Rout 17 - nout
2T
max
k<n/ nautt 11 K Pout
8T
(89)
3n
(a) holds since Theorem requires that n > 8(1 + (1/8) thus the -B(a/1-nout 1) s
2T/n.
22

---

Then the mean squared error of á can be bounded by
E [I((D) - =11 = (P), Rt + W - m=]
E [[Clip(A((D) (D), - u!l? + BI| W|]
E
[Clip(Ao(D) (D), R) 141 1 (nout <
1 m)
+ E
[|] ? 1 (oott
<
1
+E [[Clip(Ao Ao (D), Rt 14l2 [
2
+
E
W
1
2
n
1 + 12 + 13 + 14.
(90)
From Chernoff inequality,
P( > 5 -nv
env
(91)
Thus
1 8ev d I16
nout
(92)
which decays faster than any polynomial. Therefore, Is and I4 can be neglected in asymptotic analysis. Now bound I and 1z.
Bound of J. Note that
(D) ull S (Ioo(D) (D("")l + |00 -1]l
(93)
Since Z(D*) < T. (o( = =Y', then
(Boo(D)) m|]]]
E ||| || - - [011]]
E
tr(Var] Y + ||| - nll
V2
rov,
(94)
mn
in which the last step uses Lemma 14
From Lemma 1
(Iāo(D) - Ao (DD))l
< w (D', Routt)
nout (T + Z(D"))
Bout
3T Nout
(95)
Dout
The expectation can be bounded by
T nout
27
E [I]ão(D) - AD((D))1 (Bout <
I E
2
72
E
f
2ucl
n
7.2
(96)
n
Therefore
T2
I <
+ 22
(97)
mm
Bound of 1z-
23

---

[
nout
11
d
(nout
<
8
11
dT
In
(98)
8
a²
n
8'
in which the last step uses and 89
Combine all terms, the final bound on the mean squared error
d7
E [IA(D) 111"]
In
+ rguu
e²
d72
In
n²c2
mn
1
d
[In(nd)
+ mr 2-2 -nieed In In((nd)):
In
(99)
n2
mm
m
in which the second step uses T > complete.
4rp (from
13 and (84 and vd/(ne).. The proof is
G Comment on Two-stage Approach
In this section, we provide a brief comment on the two-stage approach WME in 334
1) For heavy-tailed distributions. We follow the steps of Appendix D.4 in
34 defined a (T, 7) concentration, which requires that there exists point with probability - 7 - cll S T for all i, in which Y, is the i-th user-wise average. use capital letter here to denote that it is random variable.
From Appendix D.4 in 34 7 1/(mii²e2 used. From Lemma 13 let 11(mmn we have
1
3(d +1) V .AM (3m) - --- In
3(d + 1)
Y pl| S max
2M
In
(100)
with probability at least 1 - v, in which Y is iid with Y,, i I,..., The value of r can be obtained by taking union bound for
In(mn&d) + m - (mm3)) In(mm
(101)
Follow other parts of Appendix D.4 in 34 can get
1 d d'nn'(man (mmd) In
BillA 1 S
m 2 In(nmd)
(102)
n²22
mn
Moreover, (34] has already shown the tightness of the mean squared error for the bounded case. For heavy-tailed distributions, following Appendix D.4 in (34), it can also be shown that the bound (102) tight.
2) For imbalanced users. For simplicity, we focus on the one dimensional problem. With the two-stage approach, for users with different my the final estimate will be
Σ m.Ll(a,o
(103)
in which [[a means clipping on (a, b). The sensitivity determined by the user with maximum m,,
Let Mmax max; mi, Then the sensitivity if m a)/n.
From 34 now suppose that m, are the same for all except one that is significantly larger. Then R InNN,, - 47, the sensitivity scales as (Rmmaa/ /n InnN. Denote To = mMmmxx/ N as the ratio between maximum m; and average m,. Then the mean squared error induced by privacy mechanism is
R2 n In N.
R² Inn
E 2
(104)
N
Nne
24

---

H Proof of Lemma 3
Following the proof of Theorem 2 in Appendix denote y; y:(D), y yi(DD) and (1/n) Ex=1 Yi- The proof begins with the following lemma.
Lemma 8. If (D) for all then (D( y.
Proof. We just need to prove that y is a minimizer of Σi=1 ws)r Since Z, < Ti for all i,
(y,(y,y:) = Yr-
(105)
Then
W Voi = Σ waly - y:) = 0.
(106)
Now we derive the sensitivity. Without loss of generality, we assume that first l users are replaced by others. Define
g(s) Σ wy Vo(s,y) + Σ
w&Vo(s.y.).
(107)
iE/uJV
then (D)) 0, and g(Pa(D))
w/ (o((((D))
Σ w/ ((Vo(P((D).)))
=
TE!
Σ
W (D))
Σ
w. (VVo((((D).x)) + Σ wy Vo(p((D))
iel
iET
W. VolNo (D),y))
w. ()())((D))))))
(108)
Eel
iE!
Recall that max;
|
y:ll- From Lemma (D) yssl
if Zz T. for all then
1 -y.l < Z,
(109)
thus
(o)() - Σ (T; + Zz).
(110)
From [07
Vg(s) Σ
V ( y1) + Σ w/ (2p(s.)))
IET
iEInIV
Σ
w; --ll $ T:))
(111)
For all satisfying ||s yl1 < min; (T) Zz), ||s -vll < Ti always holds, thus
Vg(s)=
Σ wi
-=
N Σ Wi I.
(112)
/E[nJV
Under condition ((D,1) min([) Zx))),
[iao - (D) s Eiel W. (T₁ Z,(D))
(113)
N Σtel Wi
Recall that we have assumed D' (D).... D/., DK.1..... Dn}. J. i.e. first k users are replaced by others. Actually, the replaced users can be arbitrarily selected from n users. Therefore, a simple generalization yields:
Eier W; (T; + Z((D))
wDD <
max -g
N
-iiE W/
(114)
The proof is complete.
25

---

I Proof of Lemma 4
Similar to the proof of Lemma in Appendix
C analyze two cases.
For the first case, u & I, in which u and 7 have the same definition in Appendix 5 without loss of generality, suppose DD and "D' differ in the first l users, while 'D and D'' differ in the (k + 1)-th user. Then
M (T + Z++ ++++11 (D") + w(D", ,k))
li²) (D(
<
(115)
N .i=1 Wi
k++
From Lemma
and the condition 1(D",, k + 1) < ( )x(D")) in Lemma
(D" k) - hD"", k) < min(T; - Z,(D")) )) - TT++1 Zk+ (D*),
(116)
thus
2m
(lAo(D)) - (D)l
(117)
N - Wi
For the second case, following steps in Appendix
2m Tk
(lAo(D') - PD( -
(118)
N
-i=1 11
Taking maximum, we have
2maxw; Ti xE(n
LS(D) N - (k + 1))
(119)
J Proof of Theorem 5
Similar to the proof of Theorem Denote
denote Z; = Zi),, Y, = (D) and = (1/n) Σ Y..
No
m, A me.
(120)
then from the statement in Theorem 5 W;; = m, Me/Ne. From the statement of Theorem that m. >N/n.
recall
The proof starts with the following lemma.
Lemma 9, With probability (n+ + 1)/(Nn?),,or all i,
32 R2 In 1))
( No +
Z, <
vmm)
(121)
3
From now on, denote a, as the right hand side of 121..
Proof. From Lemma
P(| nlll 1) < (d+ I)e
3x.2
32122
(122)
and
3mpt²
P Hlll > f) < (d+ I)e
32R2
(123)
Recall that Z, = / Y./l. Therefore
32122
P(U 12: > ai))
P
Y xl| >
In (n(Nn((d+1) 1))
3N
32R² 3m,
+
P
||Y,
All >
In(Nn + 1))
i=l
+ n
2
N
n+1
(124)
Nn²
26

---

The proof of Lemma 9 is complete.
Since Z; S dg < T; for all i, from Lemma 8
(D(D) = Y. Moreover, we show that A(D) = 0, in
which A defined in (17p. This needs the following lemma.
Lemma 10. For n/(81), if Z S a, for all i, in which o; is the right hand side of 121 then
(D, kb) min(7, 7z).
(125)
iE(n)
Proof. Recall T, in 19 let
A= R=CPRvIn(Nn((d111
(126)
then T, = A/ Am; A me thus
A
min(T, Z,)
min
ai
v M, A me
A
32R22
min
2
In(Nn2 1))
m, me
3m;
A
A
min
v my A me
2
A
2 m
A
(127)
V yN
Now we provide an upper bound of h(D, k):
(a)
> n
i k+1 W:TTi + a;)
k(D,k)
Di=1 Wi
nn-
n
(m² A m.) + ai)
i
E1 my me
i im k41 (mg A me)
Amm
2/m²
No
km
k.A /me
N
Kv
3n
N
N
A
(128)
>N
(a) comes from (6),, and that Z, & a; for all i. (b) uses the condition k < n/(8).
Combine 127 and 128 125
holds. The proof of Lemma 10 is complete.
27

---

Now it remains to bound of G(D, k). From Lemma 10 if Z; S a, for all i, then A(D) = 0, since
h(D", ko) min, (I; Z.). Then for all kp
max, w.T.
G(D,k)
E Wy
max:(m; m.
X k-1 my me
A
2 No (k 1)mc
(6)
2A m
1 N (k + 1) 2
2
4Amc
N (1 27 k+1
16A
3N Mm
16A
Y
(129)
Nn
(a) comes from Definition 6 Note that A(D) 0. For k - Ko 1, G(D, is h(D,1) if h(D,1) 1) min(T: (D) holds, max; w:Ti/(E/= n- w:). can be shown that the former one is less than the latter, thus (a) holds. For (b), from Assumption B
N
N
N₂ = Σ my A m. 2 N
Σ
m& 2
N
(130)
2
2
t=1
kang N/n
(c) holds because 7(k + 1)/n S sko/n S 1/8.
From 129 the smooth sensitivity can be bounded by
16A4 V Nn
S(D) < max
2Re -5hk
(131)
Recall that Ko [n/(8))]. In Theorem 5 is required that 87(1 + (1/28) In(Nn)), thus kn (223),/223), and -
-kk 1/ /Nn. Therefore, the second term (131) does not dominate. This result indicates that as long as Z, < a; for all i,
S(D) < 16A 7
(132)
3
Nn
Now we bound the mean squared error. Denote as the event such that Z, S a, for all Then
E [IA(D)) - ml]]]
s E [loo(D) 11l2 1(F)) [w] 1(E)
E [IC)ip(Ao(D); R) nl| 1(59) + E [[]])
+ +
(133)
28

---

Bound of 11.
7 = E
Y nl| I(F)
s E Y 1
tr Var Σ ws Yi
Σ w R²
my
(m A me)
n²
m.
Ei my A mc))
1
(m A Am))
1
Ne
2
s
(134)
N
Bound of 22-
([S( d
a
2 d
A² Y a²
Nn
dR²²
In(Nn d) In Nne
(135)
Bound of Iz.
I3 < PR
< 4 n+1
(136)
Nn2
Bound of LT-
dR
4 <
d
In
(137)
a
8 N'
1a and 1 converges to zero faster than any polynomial. Therefore
R
dR² (n(N2 In 5
E [IA(DD - mll
+
(138)
mn
No
K
Common Lemmas
Lemma 11. (Concentration inequality of bounded random vector) Given random vector X supported at Ba R), and E[X] X..... Xm are m i.i.d copies of X. Denote X as the sample mean, i.e. X (1/m) Σ ビ Xj. Then
P( X All > t) S (d+ 1)e
3m
(139)
Proof. We use the following lemma.
29

---

Lemma 12. (188. Lemma 1.6.2) Let U1...., be independent centered random vectors with dimension Assume that each one is uniformly bounded, i.e. for j 1. m
E -0
(140)
and with probability
| s L.
(141)
Let クド==
U
and define
7Z)) Σ
E
(142)
Then for all t O,
12/2
Z t) (d + 1)
(143)
7(Z) Lt/3
Now prove Lemma 11 based on Lemma 12 Let U X, n. Since |X,|| R. ||l||
R
holds, |X, μ4ll s 2R always holds, and (Z) 4mlt Hence
1²/2
P[| > t) S (d+ exp
(144)
4mR? + R
Hence
P[|
11|l > t) (d+ 1) exp
8mR2
4
Rim
3
3mt?
S
(d+1) 1xep
(145)
32R
Lemma 13. (Concentrated inequality of unbounded random vector) Given a random vector X. E 14, and [|| -nll"] Mp. X1...,, Xm are m i.idd copies of X. Denote X the sample mean. Then with probability at least - v,
1 In
3(d +1)
..4M (3m)# - - In 3(d+1)
x- S max
2M
(146)
Proof. We still use Lemma 12 Pick > 0, whose exact value will be determined later. Define
U, = (X, x) - all < r),
(147)
and
V, = (X, - H)]({ - All > r).
(148)
Then
X
M U
m
1
Σ V
(149)
m7
j=1
and
P P[| 1lll SP SP
>
+
1
Σv
m
V
(150)
m
m
This definition of Z is only used in this section.
30

---

Let Z = EØ= Uz. Then from 1122.
(Z) =E E
Σ U
S <mBlIx 1419 = mM
(151)
Note that |Uز||
always holds. Therefore, from Lemma
12
12/2
X[] >)) < 1)
mM +
frrt
t2
31
$ 1)
min
(152)
4r
4mM
and
1 m2
 U
>
P[[[Z] > mt)
m
mt²
3mt
s (d 1)
-min
4r
4MP
2
(d 1)e
424 + (d + 1)e
47
(153)
Now have bounded the first term in 150). For the second term in 150).
P
P(U 0})
m
j=1
mP all > r)
P.rr
(154)
Therefore, from
150
153
and 154
P P[
m|| > 1) S (d 1)e 4nd + (d 1)e
+ Mpmr
(155)
To make the right hand side of 155 to be no more than v, we let each term to be no more than v/3. Note that now has not be determined. Therefore, we let the third term equals v/3 first, thus
3.
r
(156)
Then we let
3(d+1) + 1) 4M, (3m) (am)1-1 - In 3(d 1)
t = max
2M
In v
(157)
m
With (566) and 155 all three terms in the right hand side of 115 will be no more than v/3. Therefore, with probability at least 1 v.
X | < max 2M In 3(d + 1) AM, (3m) } 1,, In 3(d+1)
(158)
The proof is complete.
31

---

Lemma 14. (Bias caused by outliers) Given a random vector X. E μ. and E || plll - Mr
Xi...., Xm are m i..d copies of X. Denote X as the sample mean, and
{
X
if
| S ro
(159)
if
X
μ1 > To:
which
ro = max
2Mp'
In
3(d + 1)
AMp (3m) - 2
v In 3(d 3(d+1)
(160)
m
V
then
[X mll - Cyrou
(161)
for some constant Op that depends only on p.
Proof. From 159..
=
X 10/1 S ro)] /PP[| all ro)-
(162)
Thus
B[ - 11) 1l1 S ro))
(163)
Note that X
E = Hence
E E[X+| - 1)) X All ro)l
(164)
Therefore
||| - mll $ E|| |||| 1( X 1|1 > ro]
P( X - 14 10 X - /|| > ro) > t)dt
X 1|| > ro) [ P[ X ||| > t)dt
roP([
TOV
P
P ul| > rk)) di,
(165)
in which the last step uses Lemmal 13 and
3(d 1)
2-hv 4M4 (3m) _ -2 (2- w) - In 3(d+
Tk maxx
2M In
2 -ーhu
(166)
From Lemma
P( X r|ll > rk) S Av, thus
|[[ - Alll s rov +
2 * rkk) Σ
2 krk
k=1
2 Th
= Tnv
(167)
7o
A=
From 166
and (160).
Fk
3(++
+ k 1n
<
(168)
ro
In
3(d+1)
thus
2
In
8
|[ - mll
S Tov
Σ
2
k(1 1/m)
1:2
k(1 1/p)
In
3(++1)
Cyrovs
(169)
for some constant Cp that depends only on p. The proof is complete.
32

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA]. .
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] "provided proper justification is given (c.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
general, answering
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
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 contribution (i.e. proposing a new Huber loss minimization approach which is more suitable to realistic cases, and providing theoretical analysis) has been made clear in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
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
be expected to generalize other settings.
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]
33

---

Justification: It is explained at the end of conclusion section.
Guidelines:
The answer NA means that the paper has no 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 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 (e.g., independence assumptions, noiseless settings, model vell-specification, asymptotic approximations only holding locally). The authors should reflect 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 few datasets 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 is low or images are taken in low lighting. Or speech-to-text 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 fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, 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 a complete (and correct) proof?
Answer: [Yes]
Justification: Proofs shown in the appendix, and intuition is provided in the paper.
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 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]
Justification: Experiment details are explained in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
34

---

If the paper includes experiments, a No answer to 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.
If 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 to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is 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 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Codes are provided.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (tttps://nips.co.
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7 ctaipsscc/public/guiiee gwtp://ggeee/eeeeeeeoeee www.eeumisssiiiicooooooo..oo...e Policcy 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 new proposed method and baselines. 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).
35

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
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:
Details are provided the paper.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to 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
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We provide error bars in figures. Since experiments are repeated 1000 times, the eтror is relatively low, thus the error bar may be too small to be visible for some cases.
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.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-simma 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 are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables 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 exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The experiments need little computational resources.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
36

---

The paper should provide the amount of compute required for each of the individual experimental runs as 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 ht
Answer: [Yes]
Justification: Our paper does not violate code of ethics.
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- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is foundational and theoretical research and not tied to particular applications.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 tied to particular 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 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 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 intended and functioning correctly, harms that could arise when the technology is being used as 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
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)?
Question:
Answer: [NA]
Justification: This paper has such risks.
Guidelines:
37

---

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 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 challenging, and many papers do not require this, but 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 (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: This paper uses IPUMS dataset. We cite them the paper.
Guidelines:
The answer NA that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, 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 (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paper swi th code. com hinndataseess has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- ce-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 s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
38

---

Justification:
This paper does not involve crowdsoureing.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor 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 as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending 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 we 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 the institution conducting the review.
39


Reviews:
[{"review_id": "WDnhd0Zlsr", "reviewer": "Reviewer_Bmi5", "summary": "Overall, the method proposed by the authors is interesting and effectively addresses the issue of privacy protection for users with imbalanced data. Compared to existing methods, the authors' approach is more robust and is supported by mathematical proofs.", "questions": "1. The authors' discussion lacks comprehensiveness. For instance, the statement \"The most effective approach is the two-stage scheme, which finds a small interval first and then gets a refined estimate by clipping samples into the interval\" is not fully substantiated. It would be beneficial to explore whether there are any end-to-end methods or approaches that integrate both stages. If such methods exist, a comparison should be provided. If they do not, an explanation should be offered as to why this research direction has not been pursued by others.\n\n2. The authors should clearly explain why they chose the Huber loss, highlighting its advantages. Furthermore, they should clarify whether their proposed method involves any deep innovation beyond the simple use of the Huber loss, or if it merely employs the Huber loss without additional enhancements.\n\n3. The authors' work bears similarities to \"Private Mean Estimation with Person-Level Differential Privacy.\" The authors should discuss the distinctions between their work and this paper.\n\n4. The authors should clarify whether their method has practical applications and specify the scale of data it can handle. Additionally, a complexity analysis of the method should be conducted.", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed method demonstrates significant innovation and holds substantial practical value. \n\n2. The writing is clear, the arguments are well-structured, and the mathematical foundations are solid.", "weaknesses": "I have a generally positive view of this paper, though I have some questions and concerns that I hope the authors can address thoroughly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable comments.\n\n**Q1.The authors' discussion lacks comprehensiveness. For instance, the statement \"The most effective approach is the two-stage scheme, which finds a small interval first and then gets a refined estimate by clipping samples into the interval\" is not fully substantiated. It would be beneficial to explore whether there are any end-to-end methods or approaches that integrate both stages. If such methods exist, a comparison should be provided. If they do not, an explanation should be offered as to why this research direction has not been pursued by others.**\n\nThe two-stage approach [1] is currently the most standard approach for user-level DP. To the best of our knowledge, before this work, there are no methods that integrate both stages. Follow-up research focus on different assumptions or different statistical problems, but they still use the localization-refinement two stage framework.\n\nRegarding why an end-to-end method is not pursued by others, we think that it is challenging to design a method that is adaptive to local sensitivity of data. It is necessary to finish a thorough analysis of the sensitivity that consider all possible cases. The user-wise mean concentrate around the true mean $\\mu$ with high probability since the averaging operation within each user already reduces the variance. As a result, the local sensitivity is not large with high probability. However, extreme cases may happen, such that user-wise averages are far away from each other. Despite that these cases happen with low probability, the analysis of local sensitivity becomes significantly harder. Therefore, it is not straightforward to design an estimator that rigorously ensure $(\\epsilon, \\delta)$-DP. It has been mentioned in the paragraph 3 in the introduction. We will explain further in revision.\n\n**2.The authors should clearly explain why they chose the Huber loss, highlighting its advantages. Furthermore, they should clarify whether their proposed method involves any deep innovation beyond the simple use of the Huber loss, or if it merely employs the Huber loss without additional enhancements.**\n\n(1) Why Huber loss: Huber loss combines $\\ell_2$ and $\\ell_1$ loss, and strikes a tradeoff between bias and sensitivity. Huber loss minimizer is a widely used method for robust statistics. Moreover, robustness can be converted to DP.\n\n(2) Advantages: as has been discussed in multiple places in the paper, there are two advantages of our work: improved performance for heavy tailed distributions, and suitability to imbalanced datasets. \n\n(3) Innovation beyond the use of Huber loss. Huber loss was defined for scalars. In eq.(4) in the paper, Huber loss is defined for multi-dimensional vectors. Apart from the generalization to high dimensions, a more important technical novelty is the analysis of local sensitivity and the design of noise, which is the main challenge.\n\n**3.The authors' work bears similarities to \"Private Mean Estimation with Person-Level Differential Privacy.\" The authors should discuss the distinctions between their work and this paper.**\n\nThe paper [2] is indeed an important independent work that worths discussion. However, this paper is posted on arXiv after the NeurIPS submission deadline. Therefore, we are not aware of this paper at the time of submission.\n\nActually [2] has already provided fruitful discussion in its updated version (see Section 1.3.1, arXiv 2405.20405). It has mentioned that [2] uses a directional bound, while we use a non-directional bound. Our assumption is slightly weaker than [2]. By some necessary rescaling, our Theorem 3 matches Theorem 4.1 in [2]. \n\nWe would like to comment further on the difference of methods. [2] still uses the two-stage method, with some refinements to handle the tails. Instead, our method is a direct Huber loss minimization approach, which is relatively easier to implement and requires less computation time. ([2] has not analyzed the time complexity. However, based on our understanding, the time complexity is not linear.)\n\n**4.The authors should clarify whether their method has practical applications and specify the scale of data it can handle. Additionally, a complexity analysis of the method should be conducted.**\n\n(1) Practical applications. As discussed in the last paragraph of the conclusion, for practical applications in federated learning, the remaining issue is that the method requires $n\\gtrsim d$. $d$ is the number of model parameters here. In modern deep learning applications, $d$ is usually large, thus this condition is not satisfied. There are several potential solution: sparse DP mean estimation methods, and top-k gradient selection in federated learning.\n\n(2) Complexity. It has been discussed in line 154-158 in the paper. Further discussions have been provided in Appendix A.\n\n\nReferences\n\n[1] Levy et al. Learning with user-level privacy. NeurIPS 2021. (Ref.[27] in the paper)\n\n[2] Agarwal et al. Private Mean Estimation with Person-Level Differential Privacy. arXiv:2405.20405", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oiLivAFv2q", "reviewer": "Reviewer_BDM5", "summary": "The paper proposes a user-level differential private mean estimation based on minimizing weighted huber loss. The authors conduct theoretical and empirical assessments, showing that the proposed method is more robust to user-wise sample imbalance as well as heavy-tail distributions compared to the Winsorized mean estimator proposed in [0]", "questions": "* Could the author compare the results in the balanced user case with existing literature, such as [1] and [4]? For example, a result similar to Theorem 2 has been derived in Theorem 4.1 of [1].\n* What is the purpose of tuning $T_i$ in Section 7.2 when Theorem 5 already provides an optimal choice for $T_i$? Does this parameter tuning require an additional privacy budget?", "limitations": "The authors address the limitation of this work in section 8.\n\n\n\n[0] Levy, Daniel, et al. \"Learning with user-level privacy.\" Advances in Neural Information Processing Systems 34 (2021): 12466-12479.\n\n[1] Narayanan, Shyam, Vahab Mirrokni, and Hossein Esfandiari. \"Tight and robust private mean estimation with few users.\" International Conference on Machine Learning. PMLR, 2022.\n\n[2] Avella-Medina, Marco, Casey Bradshaw, and Po-Ling Loh. \"Differentially private inference via noisy optimization.\" The Annals of Statistics 51.5 (2023): 2067-2092.\n\n[3] Song, Shuang, et al. \"Evading the curse of dimensionality in unconstrained private glms.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2021.\n\n[4] Liu, Daogao, and Hilal Asi. \"User-level differentially private stochastic convex optimization: Efficient algorithms with optimal rates.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2024.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "* The construction of smooth sensitivity and its analysis in both balanced and imbalanced user settings seem novel. \n* The proposed method is thoroughly analyzed, providing both error upper bounds and empirical evaluations.", "weaknesses": "* Some claims in this paper might need more elaboration:\n    > Line 57-58: “To the best of our knowledge, our method is the first attempt to unify robustness and DP at user-level”\n\n    The definition of robustness should be clarified in the paper. Is it referring to robustness against heavy-tailed data, arbitrary outliers, or specific types of attacks? Therefore, it would be beneficial for the authors to explicitly define both robustness and outliers.\n\n    > Line 93-94: “To the best of our knowledge, Huber loss minimization has not been applied to DP”\n    \n    Please see section 3.2.1 in [2]. Additionally, as a side note, gradient clipping for generalized linear loss is well-known to be connected to Huber loss [3].\n\n* As the author also pointed out (line 347), the proposed algorithm requires the sample size of each local user as input to determine the Huber loss parameter $T$, which is a strong assumption.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for these valuable comments.\n\n# Reply to weaknesses\n\n**The definition of robustness should be clarified in the paper. Is it referring to robustness against heavy-tailed data, arbitrary outliers, or specific types of attacks? Therefore, it would be beneficial for the authors to explicitly define both robustness and outliers.**\n\nThe robustness refers to arbitrary model poisoning attacks. The robustness of Huber loss minimizer has been already widely analyzed in existing works (In particular, [5] analyzes the robustness to Byzantine attacks in federated learning, which is relatively simpler compared with this paper). Therefore, we do not repetitively discuss the robustness of Huber loss minimizer in this paper. Following your comments, we will clarify these in our revised version.\n\n**Line 93-94: “To the best of our knowledge, Huber loss minimization has not been applied to DP”**\n\n**Please see section 3.2.1 in [2]. Additionally, as a side note, gradient clipping for generalized linear loss is well-known to be connected to Huber loss [3].**\n\nThanks for bringing this paper into our attention. There are indeed some works that uses Huber loss minimization in DP. [2] discuss the linear regression problem. Despite different from ours, we will change the statement in the paper. \n\nGradient clipping can be viewed as minimizing Huber loss, as is shown in Section 5.1 in [3]. This \"Huber loss minimization\" and ours have different meanings. In [3], the Huber loss approximates the population risk of DP optimization. In our paper, we do not focus on the optimization problem. Instead, we work on mean estimation, and there are no loss functions to approximate here.\n\n**As the author also pointed out (line 347), the proposed algorithm requires the sample size of each local user as input to determine the Huber loss parameter, which is a strong assumption.**\n\nOur experience is that it is common to assume the knowledge of sample sizes in distributed learning. For example, in [6], eq.(2), the weight is determined  by the proportion of samples of each client. \n\nWhile we agree that it is worthwhile to extend our work to the case that $m_i$ are also private, current setting is already practical. In distributed scenarios (especially federated learning), sample sizes of each client are usually not sensitive (see [7] for a review). It is fine if our knowledge of the sample size of local user is not very accurate. Our analysis can be easily generalized to the case in which we know an upper bound and a lower bound of the local sample size, such that the ratio of the upper bound to the lower bound is not large than a certain constant. Then rate of convergence of the overall mean squared error remains the same.\n\n# Reply to questions\n\n**Q1. Could the author compare the results in the balanced user case with existing literature, such as [1] and [4]? For example, a result similar to Theorem 2 has been derived in Theorem 4.1 of [1].**\n\n**Compared with [1] and [4], we (1) improve the performance for heavy-tailed distributions and (2) generalize to imbalanced users.** As discussed in line 225-227, for balanced users with bounded distributions, existing methods are already nearly optimal, and polynomial improvement is impossible. In our paper, the goal of Theorem 2 is to show that our improvement on heavy-tailed distributions and imbalanced users is not at the cost of hurting the performance under the simplest case with bounded distributions and balanced users. \n\nWe will add discussions of these two papers in our revised version.\n\n**Q2. What is the purpose of tuning $T_i$ in Section 7.2 when Theorem 5 already provides an optimal choice for $T_i$? Does this parameter tuning require an additional privacy budget?**\n\n(1) In Theorem 5, $T_i$ is selected to minimize the theoretical upper bound. To ensure that the analysis is mathematically rigorous, the upper bound of estimation error is larger than the truth. Therefore, the optimal $T_i$ is different from that derived in theories. \n\n(2) The parameter tuning does not require additional privacy budget since in each experiment, $T_i$ are hyperparameters that is fixed before knowing the value of each sample. They are not determined adaptively based on the data.\n\nWe will add these discussions in the revised version.\n\n# References\n\n[1] Narayanan, Shyam, Vahab Mirrokni, and Hossein Esfandiari. \"Tight and robust private mean estimation with few users.\" International Conference on Machine Learning. PMLR, 2022.\n\n[2] Avella-Medina, Marco, Casey Bradshaw, and Po-Ling Loh. \"Differentially private inference via noisy optimization.\" The Annals of Statistics 51.5 (2023): 2067-2092.\n\n[3] Song, Shuang, et al. \"Evading the curse of dimensionality in unconstrained private glms.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2021.\n\n[4] Liu, Daogao, and Hilal Asi. \"User-level differentially private stochastic convex optimization: Efficient algorithms with optimal rates.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2024.\n\n[5] Zhao, Puning et al. A huber loss minimization approach to byzantine robust federated learning. AAAI 2024. (Ref.[62] in the paper)\n\n[6] Wei, Kang, et al. \"Federated learning with differential privacy: Algorithms and performance analysis.\" IEEE transactions on information forensics and security 2020.\n\n[7] Fu, Jie, et al. \"Differentially private federated learning: A systematic review.\" arXiv:2405.08299.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VBw1gcctBw", "reviewer": "Reviewer_zYzW", "summary": "The paper proposes a user-level differentially private mechanism utilizing Huber loss minimization for mean estimation. This approach is robust to heavy-tailed distributions and addresses data imbalance across different users.", "questions": "See Weaknesses.", "limitations": "Limitation section is adequately provided", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written and easy to follow overall.\n- The differentially private version of Huber loss minimization for mean estimation is an interesting contribution.", "weaknesses": "- It is unclear whether the convergence results (Theorem 5) are generally applicable to generic $w_i $'s. Using $m_i \\land m_c$ seems somewhat unclear. What if the server (in federated learning) wants to compute the mean with $w_i = \\frac{m_i}{\\sum m_j}$?\n- It would be beneficial to provide a detailed analytical comparison with WME, extending beyond Section G.\n- An intuitive explanation of $\\gamma$ is required. Does $\\gamma$ measure imbalance? If so, how?\n- The inequality in (10) appears to have a typo.\n- $\\lambda$ in Theorem 4 needs a definition.\n- The figures are too small, making it difficult to check the results. What does the gray line in Figure 2(b) represent?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable comments.\n\n# Reply to weaknesses\n\n**1. It is unclear whether the convergence results (Theorem 5) are generally applicable to generic $w_i$'s. Using $m_i\\wedge m_c$ seems somewhat unclear. What if the server (in federated learning) wants to compute the mean with $w_i=m_i/\\sum m_j$?**\n\nIf we use $w_i=m_i/\\sum m_j$, then the sensitivity will be too large if there are some users with large number of items. As a result, we must add a strong noise for privacy protection, which will hurt the performance. Using $m_i\\wedge m_c$ ensures that the method is not severely affected by a single user with many items. This has been explained in line 299-305 in the paper.\n\n**2. It would be beneficial to provide a detailed analytical comparison with WME, extending beyond Section G.**\n\nThanks for this comment. In Appendix G we have already shown that WME has worse rate than our method. The analysis in WME in [1] is based on $(\\tau, \\gamma)$-concentration. For our two main improvements, i.e. heavy-tailed distributions and imbalanced users, both the first and second one inevitably lead to large $\\tau$. \n\nHere we list the our results and compare with WME here. For convenience, we omit the logarithm factors and non-private terms here.\n\n(1) Heavy-tailed, balanced users. For $n$ users with $m$ samples per user, under $p$-th order bounded moment,\n\nOurs: $\\frac{d}{mn^2\\epsilon^2}+(\\frac{d}{m^2n^2\\epsilon^2})^{1-1/p}$ (from eq.(14))\n\nWME: at least $\\frac{d}{n^2\\epsilon^2}(\\frac{1}{m}+m^{4/p-2}n^{6/p})$ (from eq.(102))\n\n(2) Bounded support, imbalanced users. For $N$ total number of samples belonging to $n$ users,\n\nOurs: $\\frac{d\\gamma}{Nn\\epsilon^2}$ (from eq.(20))\n\nWME: $\\frac{d\\gamma_0^2}{Nn\\epsilon^2}$ (from eq.(104) multiplies a factor $d$)\n\nFrom the definition of $\\gamma$ (Assumption 3) and $\\gamma_0=nm_{max}/N$ (line 689), it is easy to prove that $\\gamma_0>\\gamma$. Moreover, the quadratic dependence $\\gamma_0^2$ is reduced to linear dependence $\\gamma$. \n\nWe will make these comparison clearer in our revised paper.\n\n**3. An intuitive explanation of $\\gamma$ is required. Does $\\gamma$ measure imbalance? If so, how?**\n\nYes, $\\gamma$ measures the imbalance of users. Note that users are arranged in ascending order of $m_i$ (line 264-265). Therefore, from Assumption 3,  for users whose number of items are more than $\\gamma$ times of the average number of items, the sum of items of these users are less than $1/2$. With small $\\gamma$, users are nearly balanced, as the sizes of most of users are not much larger than the average sizes. On the contrary, with large $\\gamma$, users are highly imbalanced. It means that the size of many users are much larger than the average size.\n\nExamples: \n\n(1) If users are balanced, then $\\gamma=1$;\n\n(2) If the $i$-th user has $ki$ items (which means that the number of items of user is linear in its order), then for large $n$, $\\gamma$ is approximately $\\sqrt{2}$.\n\n**4. The inequality in (10) appears to have a typo.**\n\nThanks for finding this typo. This should be a equal sign here.\n\n**5. $\\lambda$ in Theorem 4 needs a definition.**\n\nThanks. Here $\\lambda$ is the smooth sensitivity $S(D)$. We will change the notation in the revised paper.\n\n**6. The figures are too small, making it difficult to check the results. What does the gray line in Figure 2(b) represent?**\n\nThanks for this suggestion. We will make figures larger. In figure 2(b), we make a mistake of including other number of users without changing the legends. The corrected legends are:\n\norange dashed curve -> WME, n=2000;\n\nbrown dashed curve->WME, n=5000;\n\ngray dashed curve->WME, n=10000;\n\nred dashed curve-> WME, n=30000;\n\nblue solid curve-> HLM, n=2000;\n\nthe two curves that appears to overlap at the bottom are HLM n=5000 and HLM n=10000, respectively.\n\nWe refer to the global response for the corrected figure.\n\n# References\n\n[1] Levy et al. Learning with user-level privacy. NeurIPS 2021.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for the reviews. We are encouraged that reviewers have positive views on the mathematical solidness, practical value (Reviewer Bmi5), novelty (Reviewer BDM5) and presentation (Reviewer zYzW) of this paper. 

The detailed feedbacks of each review are provided below. We are looking forward to your replies, so that we can engage in further discussions.

Regarding the weakness 6 raised by reviewer zYzW: There are some issues in Figure 2(b) in the paper. We have attached the revised figure here.

Meta-review: While the reviewers are positive about the paper,  I (the AC) took a more close look at the paper. Huber loss minimization (and its connection to clipping) is not new in the DP literature. See Figure 1 in https://arxiv.org/pdf/2006.06783 . Also, see in the context of high dimensional linear regression (see https://proceedings.mlr.press/v30/Guha13.pdf#page=23.21). While the connection to federated learning with user level DP may be somewhat new, the paper is missing comparison to a reasonably large body of prior research. (See the citations in the papers mentioned.) In light of this, while we recommend acceptance, we also request the authors to carefully compare and disambiguate the claims made from prior research.
Decision: Accept (poster)