A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacy

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.

Strengths

- The paper is well-written and easy to follow overall. - 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}$? - 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

See Weaknesses.

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

Limitation section is adequately provided

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]

Strengths

* The construction of smooth sensitivity and its analysis in both balanced and imbalanced user settings seem novel. * The proposed method is thoroughly analyzed, providing both error upper bounds and empirical evaluations.

Weaknesses

* 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

* 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?

Rating

6

Confidence

3

Soundness

2

Presentation

2

Contribution

3

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.

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.

Strengths

1. The proposed method demonstrates significant innovation and holds substantial practical value. 2. 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.

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.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

NA

Official comment by reviewer BDM5

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)