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_cc_2024_Conference
Published: 2024-05-14 14:35:04

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.

Main paper: 
 introduction: 
 Privacy is one of the major concerns in modern data analysis. Correspondingly, differential privacy (DP) [1] has emerged as a standard framework of privacy protection. Various statistical problems have been analyzed with additional DP requirements [2] [3] [4] . Among all these problems, mean estimation is a fundamental one [5] [6] [7] [8] , which is not only useful in its own right [9] , but also serves as a building block of many other tasks relying on estimating gradients, such as private stochastic optimization [10] [11] [12] [13] [14] [15] and machine learning [16] [17] [18] . 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 [19] [20] [21] and federated learning [22] [23] [24] [25] [26] , a user has multiple samples. We hope to regard them as a whole for privacy protection.In recent years, a flurry of works focus on user-level DP [27] [28] [29] [30] . The most popular one is the Winsorized Mean Estimator (WME) proposed in [28] , which takes a two-stage approach. In the first stage, WME identifies an interval, which is small but contains the ground truth µ 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 [31] . The convergence rate has been established in [28] under some ideal assumptions. Despite the merit of the two-stage approach from the theoretical perspective, this method may face challenges in many realistic settings. Firstly, [28] assumes that users are balanced, which means that users have the same number of items. Nevertheless, in federated learning applications, it is common for clients (each client is regarded as a user here) to possess different numbers of samples [32] [33] [34] . Secondly, this method is not suitable for heavy-tailed distributions, which is also common in reality [35] [36] [37] [38] . 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 [39] , 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 [40] to determine the noise strength carefully.Our method has the following advantages. Firstly, our method adapts well to imbalanced datasets, since the threshold T i 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 [41] [42] [43] . Consequently, many recent works focus on unified methods for item-level DP and robustness to cope with both attacks simultaneously [44] [45] [46] [47] .To the best of our knowledge, our method is the first attempt to unify robustness and DP at user-level.The main contribution is 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 case with balanced users, we provide a theoretical analysis, which shows that our method makes a slight improvement for bounded distributions and a significant improvement for heavy-tailed distributions over the two-stage approach.• 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 effectiveness of the proposed method for imbalanced users and heavy-tailed distributions. 
related work: 
 User-level DP. [22] applies a brute-force clipping method [17] for user-level DP in federated learning. [27] made the first step towards optimal rates under user-level DP, which analyzed discrete distribution estimation problems. The popular method WME was proposed in [28] , which uses the idea of twostage approaches [47] [48] [49] . The two-stage method for user-level DP has also been extended to stochastic optimization problems [50, 51] . [52] analyzes mean estimation for boolean signals under user-level DP in heterogeneous settings. There are also some works focusing on black-box conversion from item-level DP to user-level counterparts. [29] analyzed general statistical problems, which shows that a class of algorithms for item-level DP problems having the pseudo-globally stable property can be converted into user-level DP algorithms. Following [29] , [53] expanded such transformation for any item-level algorithms. [30] extends the works to smaller m. It is discussed in [51] that these black-box methods have suboptimal dependence on ϵ. [54] [55] [56] studies user-level DP under local model.From robustness to DP. Robustness and DP have close relationships since they both require the outputs to be insensitive to minor changes in input samples. There are three types of methods for conversion from robust statistics to DP. The first one is propose-test-release (PTR), which was first proposed in [57] , and was extended into high dimensional cases in [58] . The second choice is smooth sensitivity [40] , which calculates the noise based on the "smoothed" local sensitivity. For example, [59] designed a method to protect trimmed mean with smooth sensitivity. The third solution is inverse sensitivity [5, 60, 61] , which can achieve pure differential privacy (i.e. δ = 0). All these methods require a detailed analysis of the sensitivity. For some recently proposed high dimensional estimators [62] [63] [64] , the sensitivity is usually large and hard to analyze. As a common method for robust statistics [39] , Huber loss minimization has been widely applied in robust regression [65, 66] , denoising [67] and robust federated learning [68] . Huber loss has also been used in DP [69, 70] for linear regression problems.After the initial submission of this paper, we notice an independent work [71] , which also studies mean estimation under user-level DP (which is called person-level DP in [71] ). [71] considers directional bound, which requires that the moment is bounded in every direction. However, we consider non-directional bound, which bounds the ℓ 2 norm of a random vector. We refer to Section 1.3.1 in [71] for further discussion.Our work is the first attempt to 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. 
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 Ω as the space of all datasets, and Θ as the space of possible outputs of an algorithm. Definition 1. (Differential Privacy (DP) [1] ) Let ϵ, δ ≥ 0. A function A : Ω → Θ is (ϵ, δ)-DP if for any measurable subset O ⊆ Θ and any two adjacent datasets D and D ′ ,EQUATIONin which D and D ′ are adjacent if they differ only on a single sample. Moreover, A is ϵ-DP if (1) holds with δ = 0.Definition 1 is about item-level DP. In this work, we discuss the case where the dataset contains multiple users, i.e. D = {D 1 , . . . , D n }, with the i-th user having m i samples. Considering that the sample sizes of users are usually much less sensitive [72] , throughout this work, we assume that the local sample sizes m i are public information. Under this setting, user-level DP is defined as follows. Definition 2. (User-level DP [28] ) Two datasets D, D ′ are user-level adjacent if they differ in items belonging to only one user. In particular, ifD = {D 1 , . . . , D n }, D ′ = {D ′ 1 , . . . , D ′ n }, in which |D i | = |D ′ i | = m ifor all i, and there is only onei ∈ [n] such that D i ̸ = D ′ i , then D and D ′ are user-level adjacent. A function A is user-level (ϵ, δ)-DP if (1) is satisfied for any two user-level adjacent datasets D and D ′ . Since m i , i = 1, . . . , N are public information, in Definition 2, it is required that |D i | = |D ′ i |, 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 f asEQUATIONin which d H (D, D ′ ) = n i=1 1(D i ̸ = D ′ i ) denotes the Hamming distance. The global sensitivity of f is GS f = sup D LS f (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 [40] . 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 [40] that if W ∼ N (0, (S 2 (D)/α 2 )I), then the final output f (D) + W is (ϵ, δ)-DP for the following (α, β) pair: EQUATION 
the proposed method: 
 This section introduces the algorithm structures. Details about parameter selection are discussed together with the theoretical analysis in Section 5 and 6, respectively. For a dataset D = {D 1 , . . . , D n }, in which D i ⊂ R d is the local dataset of the i-th user, denote m i = |D i | as the sample size of the i-th user. Denote N as the total number of samples, then N = n i=1 m i . We calculate the user-wise mean first, i.e. y i (D) = (1/m i ) x∈Di x. Consider that users can be unbalanced, we assign a weight w i for the i-th user. The new proposed estimator (before adding noise) isEQUATIONin which w i is the normalized weight of user i, i.e. n i=1 w i = 1. ϕ i is the Huber loss function:EQUATIONT i is the connecting point between quadratic and linear parts of Huber loss. For balanced users, w i and T i are the same for all users. For imbalanced users, w i and T i are set differently depending on the per-user sample sizes. The general guideline is that w i increases with m i , while T i decreases with m i . The final output needs to satisfy user-level (ϵ, δ)-DP requirement. Hence, we setEQUATIONin which Clip(v, R c ) = v min (1, R c / ∥v∥) is the function that clips the result into B d (0, R c ).The clipping operation is used to control the worst case sensitivity. W denotes the noise added to the estimated value. In this work, we use Gaussian noise W ∼ N (0, σ 2 I). The clipping radius R c is determined by the knowledge of the range of µ. Given a prior knowledge ∥µ∥ ≤ R, then we can set R c = R. Actually, similar to [47] , our analysis shows that R c can grow exponentially with n without significantly compromising the accuracy. The noise parameter σ 2 needs to be determined carefully through a detailed sensitivity analysis. Now we comment on the implementation. As has been discussed in [68] , minimizing multidimensional Huber loss can be implemented by a modification of an iterative Weiszfeld's algorithm [73, 74] . The overall worst-case time complexity is O(nd/ξ), in which ξ is the desired precision. Moreover, for bounded support, with high probability, the algorithm requires only one iteration with time complexity O(nd). Details can be found in Appendix A. 
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 i are equal for all i. Therefore, throughout this section, we omit the subscript and use m to denote the local sample size. Now w i = 1/n for all i. T i are also the same for all users, denoted as T in this section. Let X be a random vector, whose statistical mean µ := E[X] is unknown. Given a dataset D = {D 1 , . . . , D n }, the goal is to estimate µ, while satisfying user-level (ϵ, δ)-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, defineEQUATIONin which ȳ(D) = (1/n) n i=1 y i (D) is the overall average. A small Z(D) indicates that the userwise means y i are concentrated within a small region. If Z(D) is large, then there are some outliers. The sensitivity is bounded separately depending on whether the user-wise means are well concentrated. Throughout this section, we use LS(D) to denote the local sensitivity of Clip(μ 0 (D), R c ), in which the subscript f 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 i in (5) for all i. It requires that all y i 's are not far away from their average.EQUATION)The proof of Lemma 1 is shown in Appendix B. Here we provide some intuition. From the definition (2), local sensitivity is the maximum change of μ0 (D) after replacing some y i with y ′ i . To achieve such maximum change, the optimal choice is to move y i sufficiently far away in the direction of μ0 (D) -y i . The impact of y i on μ0 (D) is roughly Z(D)/(n -1), while the impact of y ′ i is roughly T /(n -1). Since y i and y ′ i are at opposite direction with respect to μ0 (D), the overall effect caused by replacing y i with y ′ i is upper bounded by (T + Z(D))/(n -1). 2) A few outliers. Now we consider a 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. Lemma 2. For a dataset D, if there exists a dataset D * such that d H (D, D * ) ≤ k, in which d H is the Hamming distance (see Definition 3), andZ(D * ) < (1 -2(k + 1)/n) T , then LS(D) ≤ 2T /(n-k).The proof of Lemma 2 is shown in Appendix C. The intuition is that since there exists a well concentrated dataset D * with d H (D, D * ) ≤ k, D contains no more than k outliers. At least n -k other user-wise mean values fall in a small region. To achieve the maximum change of μ0 (D), the optimal choice is to replace an outlier y i with y ′ i , such that y i -μ0 (D) and y ′ i -μ0 (D) have opposite directions. Each of them has an effect of roughly T /(n -k) on μ0 (D), thus the overall change is 2T /(n -k).3) Other cases. For all other cases, since ∥Clip(μ 0 , R c )∥ ≤ R c always hold, the local sensitivity can be bounded by LS(D) ≤ 2R c . From the analysis above, we now construct a valid smooth sensitivity. DefineEQUATION∆(D) can be viewed as the number of outliers. Based on Definition 5, the smooth sensitivity is given byEQUATIONEQUATIONin which β is determined in (3). Then we show that S(D) is a valid smooth sensitivity, and the privacy requirement is satisfied.Theorem 1. With σ = S(D)/α, in which α is determined in (3), W ∼ N (0, σ 2 I), the estimator μ defined in (6) is (ϵ, δ)-DP.To prove Theorem 1, we need to show that S is a valid smooth sensitivity, i.e. two conditions in Definition 4 are satisfied. The detailed proof is provided in Appendix D.In the analysis above, all results are derived for a general dataset D. In the remainder of this section, we analyze the performance of estimator (6) for randomly generated samples.Let X be a random vector generated from distribution P with an unknown statistical mean µ := E[X]. We make the following assumption:Assumption 1. X is supported on B d (0, R) = {u| ∥u∥ ≤ R} ⊂ R d .The mean squared error is analyzed in the following theorem.EQUATION)The proof of Theorem 2 is shown in Appendix E. With the selection rule of T in Theorem 2, it is shown that with high probability, ∆(D) = 0, 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 μ0 (D), while the second term is the error caused by noise W. The condition n > (4/β) ln(nR c /T ) is necessary, since it ensures that G(D, k) = 2R c (Definition 5 (c)) occurs only for sufficiently large k, thus e -βk is small, and does not affect the calculation of S(D) in (11) . A lower bound on the number of users n has also been imposed for the two-stage method [28] .For the simplest case with bounded support and balanced users, the two-stage approach in [28] is already nearly optimal (Corollary 1 in [28] ). Therefore, improvement in polynomial factors is impossible. Nevertheless, we still improve on the logarithm factor. The main purpose 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.Now we analyze the heavy-tailed case. Instead of requiring X ∈ B d (0, R), we now assume that X has p-th bounded moment. Assumption 2. Suppose that µ ∈ B(0, R), and the p-th(p ≥ 2) moment of X -µ is bounded, i.e. E[∥X∥ p ] ≤ M p .In Assumption 2, higher p indicates a lighter tail and vice versa. We then show the convergence rate of mean squared error in Theorem 3. Theorem 3. Let R c = R, andEQUATIONEQUATION)The proof of Theorem 3 is shown in Appendix F. Here we provide an intuitive understanding. From the central limit theorem, each user-wise mean y i (D) is the average of m i.i.d variables, thus it has a 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 T is designed based on the high probability upper bound of Z(D) to ensure that with high probability, ∆(D) is small. Regarding the result, we have the following remarks. Remark 1. Here we comment on small and large m limits. If m = 1, the right hand side of (14) becomes O(1/n+(d/n 2 ϵ 2 ) 1-1/p ), which matches existing analysis on item-level DP for heavy-tailed random variables [49] . For the opposite limit, with m 1-2/p ≳ n 2/p ln(nd), 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 constant factor. Remark 2. Now we compare (14) with the two-stage approach. Following the analysis in [28] , it can be shown that the bound of mean squared error in [28] isÕ((d/(n 2 ϵ 2 ))(1/m + m 4/p-2 n 6/p)) (we refer to Appendix G for details). Therefore, we have achieved an improved rate in (14) .The theoretical results in this section are 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 our method avoids the clipping process. In federated learning applications, it is common for gradients to have heavy-tailed distributions [35] [36] [37] [38] , 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 it in the next section.Question: Does the paper provide open access to the data and code, with sufficient instructions 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. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
analysis: imbalanced users: 
 Now we analyze the general case where m i , i = 1, . . . , n are different. Recall that for balanced users, we have defined Z(D) in ( 7) that finds the maximum distance from y i (D) to their average ȳ(D). For imbalanced users, instead of taking the maximum, we define Z i separately for each i:EQUATIONin which ȳ(D) = n i=1 w i y i (D) is the average of samples all over the dataset. From now on, without loss of generality, suppose that users are arranged in ascending order of m i , i.e. m 1 ≤ . . . ≤ m n . DefineEQUATION)Similar to the case with balanced users, we analyze the sensitivity for datasets with no outliers, a few outliers, and other cases separately.1) No outliers. We show the following lemma.Lemma 3. If h(D, 1) ≤ min i (T i -Z i (D)), then LS(D) ≤ h(D, 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 2, we find a neighboring dataset D * that is well concentrated and then bounds the local sensitivity. The formal statement is shown in the following lemma. Lemma 4. For a dataset D, if there exists another datasetD * such that h(D * , k + 1) < min i (T i - Z i (D * )), then LS(D) ≤ 2 max i (w i T i )/ n-k-1 i=1 w i .The proof of Lemma 4 is shown in Appendix I, which just follows the proof of Lemma 2.3) Other cases. Finally, for all cases not satisfying the conditions in Lemma 3 and 4, we can just bound the local sensitivity with 2R c , i.e. LS(D) ≤ 2R c .Similar to the case with balanced users, now we defineEQUATIONin which k 0 is any integer, and can be viewed as a design parameter. Correspondingly, the smooth sensitivity G(D, k) is defined as follows. We still use the same settings of α and β as in the case with balanced samples. With smooth sensitivity calculated using (11) , the privacy requirement is satisfied:EQUATIONEQUATIONTheorem 4. Let W ∼ N (0, (S(D) 2 /α 2 )I), in which S(D) = max k e -βk G(D, k), then the estimator μ is (ϵ, δ)-DP.Now we analyze the convergence of the algorithm. We begin with Assumption 3. Intuitively, this assumption requires that the users can not be too unbalanced. At least half samples belong to users whose sample sizes are not very large.Assumption 3. Suppose there exists a constant γ ≥ 1.Let k c = min{i|m i > γN/n}, then n i=kc m i ≤ N/2.In Assumption 3, γ can be viewed as the degree of imbalance. For a better explanation, we provide the following examples:• If users are balanced, then γ = 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 n, γ is approximately√ 2.In general, γ is large if users are highly imbalanced. Under Assumption 3, the convergence of mean squared error is shown in Theorem 5.Theorem 5. Let the weights of users in (4) be w i = m i ∧m c /( n j=1 m j ∧m c ), in which m c = γN/n. Moreover, letEQUATIONin which C T > 16 2/3. In (17) , k 0 = ⌊n/8γ⌋.With the parameters above, if n > 8γ(1 + (1/2β) ln(N n)), then under Assumption 1 and 3,EQUATION)The proof of Theorem 5 is shown in Appendix J. If users are balanced, then γ = 1, with N = nm, (20) reduces to (12) . From (20) and Assumption 3 it can be observed that our method is much less sensitive to a single large m i . As long as m i are not very large for most users, the convergence rate of mean squared error is not affected. There are two intuitive reasons. Firstly, w i is upper bounded by m c /( n j=1 m j ∧ m c ), thus the worst-case sensitivity is controlled. Secondly, T i are set adaptively to achieve a good tradeoff between sensitivity and bias. With larger m i , smaller T i is used, and vice versa. We refer to Appendix G for comparison with the two-stage approach.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [Yes] Justification: Details are provided in the paper. Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a 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, or as supplemental material. 
numerical examples: 
 In this section, we show numerical experiments. We compare the performance of our new Huber loss minimization approach (denoted as HLM) versus the two-stage approach proposed in [28] , called Winsorized Mean Estimator (denoted as WME).Here all users have the same sizes of local datasets. In the following experiments, we fix ϵ = 1 and δ = 10 -5 . For a fair comparison, the parameter T for our method as well as τ in [28] are both tuned optimally for each case. Figure 1 shows the curve of mean squared error. Let the number of users n be either 1, 000 and 10, 000. In each curve, n is fixed, while the number of samples per user m varies from 1 to 1, 000. The results are plotted in logarithm scale. Figure 1(a)-(c ) show the results of uniform distribution in [-1, 1], Gaussian distribution N (0, 1), and the Lomax distribution, whose pdf is f (x) = a/(1 + x) a+1 (we use a = 4 in Figure 1(c) ). Figure 1 (d)-(f) shows the corresponding experiments with dimensionality d = 3. Finally, Figure 1 (g) and (h) show the results using the IPUMS dataset [75] for total income and salary, respectively, which are typical examples of data following heavy-tailed distributions. 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 1(d)-(f) show that the advantage of the practical performance of our method becomes more obvious.Now we show the performance with unbalanced users. For some γ ≥ 1, let s i = ⌈N (i/n) γ ⌉ for i = 0, . . . , n, and m i = s i -s i-1 for i = 1, . . . , n. It can be shown that Assumption 3 is satisfied with γ. Therefore, according to the analysis in Section 6, we letw i = m i ∧ m c / j m j ∧ m c , with m c = γN/n, and T i = A/ √ m i ∧ m c, in which A is tuned optimally for each case. The selection of T i may be slightly different from (19) in Theorem 5. 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 value of T i 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 i 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 γ.From Figure 2 , it can be observed that with the increase of γ, the two-stage method degrades, while the Huber loss minimization approach performs significantly more stable. Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: We provide error bars in figures. Since experiments are repeated 1000 times, the error 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, confidence intervals, or statistical significance tests, at 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. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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 of 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 in the text. 
conclusion: 
 In this paper, we have proposed a new approach to mean estimation under user-level DP based on Huber loss minimization. The sensitivity is 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.Limitations: 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 i also being private has not been analyzed. We will leave these two points as future works.Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [NA] Justification: The experiments need little computational resources. Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: 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?Answer: [Yes] Justification: This paper uses IPUMS dataset. We cite them in the paper.Guidelines:• The answer NA means that the paper does not use 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 is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
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 of 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 is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA]  
 
 Appendix: In this section, we describe the algorithm for Huber loss minimization.In particular, we solveEQUATIONFrom ( 5), it can be shown thatEQUATION)The algorithm can be designed from above equation. Suppose that the algorithm starts from c 0 . The update rule isEQUATION)(23) is run iteratively until the norm of update ∥c k+1 -c k ∥ between two iterations is less than ξ.We provide a brief analysis on the computational complexity as follows.Worst case. [74] has shown that the Weiszfeld's algorithm for calculating geometric median needs O(1/ξ) steps to achieve precision ξ. The proof can also be used to our algorithm (23) . Moreover, from (23) , each step requires O(nd) time, in which d is the dimensionality of y i , thus the overall time complexity is O(nd/ξ).Common case. From the analysis in Section 5 and 6, for bounded support, with high probability, Z(D) ≤ T holds for balanced users, and Z i (D) ≤ T i holds for imbalanced users. In this case, we can just calculate the result within one step:EQUATION)Therefore the time complexity is O(nd).Now the users are balanced. ( 4) and (5) becomesEQUATIONandEQUATIONIn this section, we prove a strengthened version of Lemma 1 for future usage. Define the modulus of continuity as Definition 7. (Modulus of continuity) DefineEQUATION)From the definition, ω(D, 0) is just the local sensitivity LS(D). Then we show the following lemma.EQUATION)Let k = 0, then Lemma 5 reduces to Lemma 1. The remainder of this section shows the proof of Lemma 5.According to (27) , ω(D, k) is the supremum change after replacing all items belonging to k users. Denote D ′ as a dataset such that d H (D, D ′ ) ≤ k. Let I be the set of users such that D i ̸ = D ′ i . Throughout this section, we denote y i = y i (D) and y ′ i = y i (D ′ ) for simplicity. From (25) ,EQUATION)Let ∇ϕ be the gradient of ϕ with respect to the first argument. DefineEQUATIONthenEQUATIONandEQUATIONin which the last step comes from (25) .Then we show the following lemma. Proof. The proof has two steps.(1) ȳ is a minimizer of n i=1 ϕ(s, y i ). From (26),EQUATIONin which the second step holds because ∥ȳ -y i ∥ ≤ Z ≤ T . Moreover, n i=1 ϕ(s, y i ) is convex, thus ȳ is a minimizer.(2) ȳ is the unique minimizer. The HessianEQUATION)Therefore n i=1 ϕ(s, y i ) is strong convex around ȳ, and thus ȳ is unique.From (30) ,EQUATIONMoreover, for s satisfying ∥s -ȳ∥ ≤ T -Z,EQUATIONin which the last step holds because ∥s -y i ∥ ≤ ∥s -ȳ∥ + ∥ȳ -EQUATIONLet L be a path connecting μ0 (D) and μ0 (D ′ ). ThenEQUATIONNote that from ( 31) and (35) ,EQUATIONFrom the conditionEQUATIONand ( 39) yields EQUATIONEQUATIONEQUATIONEQUATIONFor convenience of expression, denote y i = y i (D) and y ′ i = y(D ′ i ). In this section, define g 1 (s) as follows:EQUATIONthenEQUATIONandEQUATIONThereforeEQUATION(a) comes from (33) . By taking gradient over s, we have ∥∇ϕ(s, y)∥ ≤ min{T, ∥s -y∥}. (b) comes from Lemma 6, which states that μ0 (D) = ȳ.For all s satisfying ∥s -EQUATIONin which the last step holds becauseEQUATIONThenEQUATIONin which L is the line connecting μ0 (D) and μ0 (D ′ ).From ( 45) and (47) ,EQUATIONFrom the conditionEQUATIONHenceEQUATIONFrom ( 50) and ( 53), the second element in the minimum bracket in (50) will not take effect. Hence,EQUATION(54) will be useful in the analysis of the second case. From ( 50) and ( 53), we can also getEQUATIONin which the last step uses the bound of ω(D * , k) in Lemma 1. Now we have bounded ∥μ 0 (D) -μ0 (D ′ )∥ for the first case. EQUATIONEQUATIONEQUATIONIn order to bound ∥μ 0 (D) -μ0 (D ′ )∥, we construct a temporary dataset D temp as follows:EQUATIONDefineEQUATIONThen g 2 (μ 0 (D ′ )) = 0, andEQUATIONFrom (33) ,EQUATIONNow we bound ∥μ 0 (D) -μ0 (D ′ )∥. Corresponding to (54), we getEQUATIONandEQUATION)Denote L as the line connecting μ0 (D) and μ0 (D ′ ). For all s ∈ L, ∥s -μ0 (D temp )∥ ≤ T -Z(D * )ω(D * , k -1). Corresponding to ( 48), for all s ∈ L,EQUATIONThereforeEQUATIONFrom ( 62) and ( 66),EQUATION)Combine case 1 and 2, we getEQUATION)The last step comes from the requirement that Z(D * ) < (1 -2(k + 1)/n)T . The proof is complete.Two requirements on smooth sensitivity are shown in Definition 4, i.e.(1) For any D, S(D) ≥ LS(D);(2) For any neighboring D and D ′ , S(D) ≤ e β S(D ′ ).It has been shown in [40] that based on (1) and ( 2), the final result μ is (ϵ, δ)-DP. In the remainder of this section, we show that both requirements (1) and (2) are satisfied. Therefore the requirement (1) is satisfied.For (2) , it suffices to show that G(D, k) ≤ G(D ′ , k + 1). From Lemma 2, if ∆(D ′ ) exists, andEQUATION)From the definition of ∆ in ( 9), since D and D ′ are adjacent, ∆(D) ≤ ∆(D ′ ) + 1 holds. Therefore, the condition kEQUATION)If the conditions in Lemma 2 are not satisfied, i.e. ∆(D ′ ) does not exists or k+ 1 > n/4 -1 -∆(D ′ ), then G(D ′ , k + 1) = 2R c , thus G(D, k) ≤ G(D ′ , k + 1) holds.Now we have shown that no matter whether the conditions in Lemma 2 holds, we always have 11), it can be easily shown that S(D) ≤ e β S(D ′ ).G(D, k) ≤ G(D ′ , k + 1). From (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 i = y i (D) and Ȳ = ȳ(D) for simplicity. We use capital letters here since D is random, thus Y i and Ȳ are random variables.From Lemma 11 in Section K, for i = 1, . . . , n,EQUATIONEQUATION)DefineEQUATIONThenEQUATION)Recall thatEQUATIONwith C T > 16 2/3. Then with probability at least 1 -1/(mn 2 ), Z ≤ T /2 holds, thusEQUATION)Note that in the statement of Theorem 2, it is required that n > (4/β) ln(nR c /T ). This yields 2R c e -nβ/4 < 2T /n, and e -βk 2T /(n -k) decreases with k. ThereforeEQUATION)It remains to bound the estimation error. The mean squared error of mean estimation can be decomposed in the following way:EQUATION(a) holds because E[W|D] = 0 for any D, thus μ0 (D) -µ and W are uncorrelated. Now we bound these four terms separately.Bound of I 1 . From Lemma 6, for Z ≤ R ln(nd)/ √ m, Z < T holds, thus μ0 (D) = Ȳ. For convenience, denote Y as an i.i.d copy of Y i , i = 1, . . . , n and X as an i.i.d copy of X ij , i = 1, . . . , n, j = 1, . . . , m. ThenEQUATION)Bound of I 2 .EQUATION)(a) holds because W ∼ N (0, (λ 2 /α 2 )I). (b) comes from (77) . (c) comes from (3).Bound of I 3 . From (74),EQUATION)Bound of I 4 .EQUATION)Now all four terms in ( 78) have been bounded. ThereforeEQUATION)The proof is complete.In this section, following Appendix E, we still denote Y i = y i (D) and Ȳ = ȳ(D) for simplicity.DefineEQUATIONEQUATION) in which ν = √ d/(nϵ).From the statement of Theorem 3, T > 4r 0 . From Lemma 13,EQUATION)DefineEQUATION)Then n out follows a Binomial distribution with parameter (n, p) with p ≤ 1/n. E[n out ] ≤ 1. This indicates that with the increase of n, the number of outliers is still bounded by O(1) with high probability.Lemma 7. ∆(D, k) ≤ n out for k < n/4 -n out -1.Proof. From the dataset D, we construct D * as follows. Let  and D  * i is an arbitrary set with mean value µ. In other words, denote Y * i as the mean value in D * i , thenD * = {D * 1 , . . . , D * n } such that D * i = D i if ∥Y i -µ∥ ≤ r 0 ,EQUATIONEQUATIONG(D, k) can be bounded using Definition 5. SinceR c = R, for k ≥ n/4 -n out -1, G(D, k) ≤ 2R.Therefore, for sufficiently large n, if n out < n/8, thenEQUATION)(a) holds since Theorem 3 requires that n > 8(1 + (1/β) ln(n/2T )), thus the e -β(n/4-nout-1) ≤ 2T /n.Then the mean squared error of μ can be bounded byEQUATION)From Chernoff inequality,EQUATIONEQUATION)which decays faster than any polynomial. Therefore, I 3 and I 4 can be neglected in asymptotic analysis. Now we bound I 1 and I 2 .Bound of I 1 . Note thatEQUATIONEQUATIONin which the last step uses Lemma 14.From Lemma 1,EQUATION)The expectation can be bounded byEQUATIONThereforeEQUATIONBound of I 2 .EQUATIONin which the last step uses (3) and (89).Combine all terms, the final bound on the mean squared error isEQUATIONin which the second step uses T > 4r 0 (from ( 13) and ( 84)) and ν = √ d/(nϵ). The proof is complete.In this section,we provide a brief comment on the two-stage approach WME in [28] .1) For heavy-tailed distributions. We follow the steps of Appendix D.4 in [28] .[28] defined a (τ, γ) concentration, which requires that there exists a point c, with probability 1 -γ, ∥Y i -c∥ ≤ τ for all i, in which Y i is the i-th user-wise average. We use capital letter here to denote that it is a random variable.From Appendix D.4 in [28] , γ ∼ 1/(mn 2 ϵ 2 ) is used. From Lemma 13, let ν = 1/(mn 3 ϵ 2 ), we haveEQUATIONwith probability at least 1 -ν, in which Y is i.i.d with Y i , i = 1, . . . , n. The value of τ can be obtained by taking union bound for all i:EQUATIONFollow other parts of Appendix D.4 in [28] , we can getEQUATIONMoreover, [28] has already shown the tightness of the mean squared error for the bounded case. For heavy-tailed distributions, following Appendix D.4 in [28] , it can also be shown that the bound (102) is tight.2) For imbalanced users. For simplicity, we focus on the one dimensional problem. With the two-stage approach, for users with different m i , the final estimate will be From [28] , now suppose that m i are the same for all i except one that is significantly larger. Then τ ∼ R n ln n/N , b -a = 4τ , the sensitivity scales as (Rm max /N ) n ln n/N . Denote γ 0 = nm max /N as the ratio between maximum m i and average m i . Then the mean squared error induced by privacy mechanism isEQUATIONEQUATIONFollowing the proof of Theorem 2 in Appendix E, denote y i = y i (D), y ′ i = y i (D ′ ) and ȳ = (1/n) n i=1 y i . The proof begins with the following lemma. Lemma 8. If T i > Z i (D) for all i, then μ0 (D) = ȳ.Proof. We just need to prove that ȳ is a minimizer of n i=1 w i ϕ i (s, y i ). Since Z i < T i for all i, ∇ϕ i (ȳ, y i ) = ȳy i .(105) ThenEQUATIONNow we derive the sensitivity. Without loss of generality, we assume that first k users are replaced by others. DefineEQUATIONthen g(μ 0 (D ′ )) = 0, andEQUATIONRecall that Z = max i ∥ȳ -y i ∥. From Lemma 8, if Z i < T i for all i, then ∥μ 0 (D) -EQUATIONEQUATIONFrom (107),EQUATIONFor all s satisfying ∥s -ȳ∥EQUATIONUnder condition h(D, 1)EQUATIONRecall that we have assumed D ′ = {D ′ 1 , . . . , D ′ k , D k+1 , . . . , D n }, 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:EQUATION)The proof is complete.Similar to the proof of Lemma 2 in Appendix C, we analyze two cases.For the first case, u / ∈ I, in which u and I have the same definition as in Appendix 5, without loss of generality, suppose D and D * differ in the first k users, while D and D ′ differ in the (k + 1)-th user. ThenEQUATION)From Lemma 3 and the condition h(D * , k + 1)EQUATIONthusEQUATIONFor the second case, following steps in Appendix B,EQUATIONTaking maximum, we haveEQUATIONJ Proof of Theorem 5Similar to the proof of Theorem 2, denoteEQUATIONthen from the statement in Theorem 5, w i = m i ∧ m c /N c . From the statement of Theorem 5, recall that m c = γN/n.The proof starts with the following lemma. Lemma 9. With probability 1 -(n + 1)/(N n 2 ), for all i,EQUATIONFrom now on, denote a i as the right hand side of (121).Proof. From Lemma 11,EQUATIONEQUATIONEQUATION)The proof of Lemma 9 is complete.Since Z i ≤ a i < T i for all i, from Lemma 8, μ0 (D) = Ȳ. Moreover, we show that ∆(D) = 0, in which ∆ is defined in (17) . This needs the following lemma.Lemma 10. For k ≤ n/(8γ), if Z i ≤ a i for all i, in which a i is the right hand side of (121), thenEQUATIONProof. Recall T i in (19) , letEQUATIONthenEQUATIONNow we provide an upper bound of h(D, k):EQUATION(a) comes from (16) , and that Z i ≤ a i for all i. (b) uses the condition k < n/(8γ).Combine (127) and ( 128), (125) holds. The proof of Lemma 10 is complete. Now it remains to bound of G(D, k). From Lemma 10, if Z i ≤ a i for all i, then ∆(D) = 0, since h(D * , k 0 ) < min i (T i -Z i ). Then for all k ≤ k 0 -1,EQUATION)(a) comes from Definition 6. Note that∆(D) = 0. For k ≤ k 0 -1, G(D, k) is h(D, 1) if h(D, 1) ≤ min i (T i -Z i (D)) holds, or 2 max i w i T i /( n-k-1 i=1 w i ).It can be shown that the former one is less than the latter, thus (a) holds. For (b), from Assumption 3,EQUATION)(c) holds because γ(k + 1)/n ≤ γk 0 /n ≤ 1/8.From (129), the smooth sensitivity can be bounded byEQUATIONRecall that k 0 = ⌊n/(8γ)⌋. In Theorem 5, it is required that n > 8γ(1 + (1/2β) ln(N n)), thus k 0 ≥ ln(N n)/(2β), and e -βk0 = 1/ √ N n. Therefore, the second term in (131) does not dominate. This result indicates that as long as Z i ≤ a i for all i,EQUATION)Now we bound the mean squared error. Denote E as the event such that Z i ≤ a i for all i. ThenEQUATIONBound of I 1 .EQUATION)Bound of I 2 .EQUATION)Bound of I 3 .EQUATION)Bound of I 4 .EQUATIONI 3 and I 4 converges to zero faster than any polynomial. ThereforeEQUATIONK Common Lemmas Lemma 11. (Concentration inequality of bounded random vector) Given a random vector X supported at B d (0, R), and E[X] = µ. X 1 , . . . , X m are m i.i.d copies of X. Denote X as the sample mean, i.e. X = (1/m) m j=1 X j . ThenEQUATION)Proof. We use the following lemma.Lemma 12. ( [80], Lemma 1.6.2) Let U 1 , . . . , U m be independent centered random vectors with dimension d. Assume that each one is uniformly bounded, i.e. for j = 1, . . . , m,EQUATIONand with probability 1,EQUATIONLet Z = m j=1 U j2 , and defineEQUATIONThen for all t > 0,EQUATION)Now we prove Lemma 11 based on Lemma 12. Let U j = X j -µ. Since ∥X j ∥ ≤ R, ∥µ∥ ≤ R holds, ∥X j -µ∥ ≤ 2R always holds, and γ(Z) = 4mR 2 . HenceEQUATIONEQUATION)Lemma 13. (Concentrated inequality of unbounded random vector) Given a random vector X, E[X] = µ, and E [∥X -µ∥ p ] ≤ M p . X 1 , . . . , X m are m i.i.d copies of X. Denote X as the sample mean. Then with probability at least 1 -ν,EQUATIONProof. We still use Lemma 12. Pick r > 0, whose exact value will be determined later. DefineEQUATIONandEQUATIONThenEQUATIONandEQUATIONLet Z = m j=1 U j . Then from (142),EQUATIONNote that ∥U j ∥ < r always holds. Therefore, from Lemma 12,EQUATIONEQUATIONEQUATIONEQUATIONNow we have bounded the first term in (150). For the second term in (150),EQUATIONTherefore, from (150), ( 153) and (154),EQUATIONTo make the right hand side of (155) to be no more than ν, we let each term to be no more than ν/3. Note that now r has not be determined. Therefore, we let the third term equals ν/3 first, thusEQUATION)Then we letEQUATIONWith ( 156) and (157), all three terms in the right hand side of (155) will be no more than ν/3. Therefore, with probability at least 1 -ν,EQUATION)The proof is complete.Lemma 14. (Bias caused by outliers) Given a random vector X, E[X] = µ, and E [∥X -µ∥ p ] ≤ M p .X 1 , . . . , X m are m i.i.d copies of X. Denote X as the sample mean, andEQUATIONin whichEQUATIONthenEQUATION161) for some constant C p that depends only on p.Proof. From (159),EQUATIONNote that EEQUATIONin which the last step uses Lemma 13, andEQUATIONFrom Lemma 13, P(EQUATIONFrom ( 166) and (160),EQUATIONthusEQUATIONfor some constant C p that depends only on p. The proof is complete.• 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 a 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 a 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 to 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 to 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 NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.This definition of Z is only used in this section. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: I have a generally positive view of this paper, though I have some questions and concerns that I hope the authors can address thoroughly.
questions: 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.

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.

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.

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.
limitations: limitations: NA
paper_summary: paper_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]
strength_weakness: strength_weakness: * Some claims in this paper might need more elaboration:
    > Line 57-58: “To the best of our knowledge, our method is the first attempt to unify robustness and DP at user-level”

    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.

    > Line 93-94: “To the best of our knowledge, Huber loss minimization has not been applied to DP”
    
    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].

* 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.
questions: 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].
* 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: limitations: The authors address the limitation of this work in section 8.



[0] Levy, Daniel, et al. "Learning with user-level privacy." Advances in Neural Information Processing Systems 34 (2021): 12466-12479.

[1] Narayanan, Shyam, Vahab Mirrokni, and Hossein Esfandiari. "Tight and robust private mean estimation with few users." International Conference on Machine Learning. PMLR, 2022.

[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.

[3] Song, Shuang, et al. "Evading the curse of dimensionality in unconstrained private glms." International Conference on Artificial Intelligence and Statistics. PMLR, 2021.

[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.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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}$?
- It would be beneficial to provide a detailed analytical comparison with WME, extending beyond Section G.
- An intuitive explanation of $\gamma$ is required. Does $\gamma$ measure imbalance? If so, how?
- The inequality in (10) appears to have a typo.
- $\lambda$ in Theorem 4 needs a definition.
- The figures are too small, making it difficult to check the results. What does the gray line in Figure 2(b) represent?
questions: questions: See Weaknesses.
limitations: limitations: Limitation section is adequately provided

Comments: title: Official comment by reviewer BDM5
Official comment by reviewer BDM5
comment: Thank you very much for your response as well as the score increase! Please let us know if you have further questions or comments.
Thank you. Since my concerns have been resolved and considering the overall quality of the paper, I would like to increase my score to 6.
Thanks for introducing this paper. We have read [1], which is improved over an existing analysis of parameter tuning in [2].

[1] Papernot, Nicolas, and Thomas Steinke. "Hyperparameter Tuning with Renyi Differential Privacy." ICLR 2022

[2] Liu, Jingcheng, and Kunal Talwar. "Private selection from private candidates." STOC 2019.

In our experiments, the parameter tuning does not lead to additional privacy leakage, since this is an experiment with synthesized data. After we change the parameters, samples are generated again. In other words, parameters for each experiment are determined before generating these samples. The parameters are not determined adaptively based on the data. Therefore there is no additional privacy leakage.

[1] and [2] analyze the case of using a fixed dataset. When we update the hyperparameters, we have to reuse the dataset. As a result, the parameters have to be determined adaptively based on the data. As a result, the privacy leakage is inevitable.

We will mention these discussions to avoid confusion.
Thank you for answering my questions, particularly the one about Theorem 2.

I have a further question:

> "The parameter tuning does not require additional privacy budget since in each experiment ... They are not determined adaptively based on the data"

Privacy leakage is still possible if the evaluation is solely on the training set. (e.g. mentioned in section 2 of https://arxiv.org/pdf/2110.03620)
Thank you for the author's response. I believe the paper makes a reasonable contribution, and I will maintain my positive score.
Thank you very much for your reply. If you have any remaining questions or suggestions for us, please let us know.
Thank you very much for the author's response, which has largely addressed my concerns. Overall, this paper demonstrates innovation and theoretical depth. Therefore, I will maintain a positive score. I hope the authors will include the discussed content in the final revised version to further improve the paper.