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

arXiv: https://arxiv.org/abs/2405.13453 · HTML: https://mlsanity.com/paper/2405.13453/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 88 references that are in the map.
- First posted on arXiv 22 May 2024.

## Builds on (most cited first, 30 of 38)

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Federated Learning with Differential Privacy: Algorithms and Performance Analysis](https://mlsanity.com/paper/1911.00222/) (2019)
- [Differentially Private Federated Learning: A Client Level Perspective](https://mlsanity.com/paper/1712.07557/) (2017)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Fair Resource Allocation in Federated Learning](https://mlsanity.com/paper/1905.10497/) (2019)
- [A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks](https://mlsanity.com/paper/1901.06053/) (2019)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [The Heavy-Tail Phenomenon in SGD](https://mlsanity.com/paper/2006.04740/) (2020)
- [A General Approach to Adding Differential Privacy to Iterative Training Procedures](https://mlsanity.com/paper/1812.06210/) (2018)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Private Mean Estimation of Heavy-Tailed Distributions](https://mlsanity.com/paper/2002.09464/) (2020)
- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Differential privacy and robust statistics in high dimensions](https://mlsanity.com/paper/2111.06578/) (2021)
- [Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation](https://mlsanity.com/paper/1906.02830/) (2019)
- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [Learning discrete distributions: user vs item-level privacy](https://mlsanity.com/paper/2007.13660/) (2020)
- [Instance-optimal Mean Estimation Under Differential Privacy](https://mlsanity.com/paper/2106.00463/) (2021)
- [Optimal Algorithms for Mean Estimation under Local Differential Privacy](https://mlsanity.com/paper/2205.02466/) (2022)
- [Attention-Enhancing Backdoor Attacks Against BERT-based Models](https://mlsanity.com/paper/2310.14480/) (2023)
- [Differentially private inference via noisy optimization](https://mlsanity.com/paper/2103.11003/) (2021)
- [From Robustness to Privacy and Back](https://mlsanity.com/paper/2302.01855/) (2023)
- [Federated Recommendation System via Differential Privacy](https://mlsanity.com/paper/2005.06670/) (2020)
- [Collecting and Analyzing Data from Smart Device Users with Local Differential Privacy](https://mlsanity.com/paper/1606.05053/) (2016)
- [Shuffle Private Stochastic Convex Optimization](https://mlsanity.com/paper/2106.09805/) (2021)

## Built on by (most cited first, 11 of 11)

- [Towards User-level Private Reinforcement Learning with Human Feedback](https://mlsanity.com/paper/2502.17515/) (2025)
- [Fed-SB: A Silver Bullet for Extreme Communication Efficiency and Performance in (Private) Federated LoRA Fine-Tuning](https://mlsanity.com/paper/2502.15436/) (2025)
- [Journey into Automation: Image-Derived Pavement Texture Extraction and Evaluation](https://mlsanity.com/paper/2501.02414/) (2025)
- [Learning with User-Level Local Differential Privacy](https://mlsanity.com/paper/2405.17079/) (2024)
- [Locally Private Sampling with Public Data](https://mlsanity.com/paper/2411.08791/) (2024)
- [Locally Optimal Private Sampling: Beyond the Global Minimax](https://mlsanity.com/paper/2510.09485/) (2025)
- [Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates](https://mlsanity.com/paper/2408.09891/) (2024)
- [Distribution-Aware Mean Estimation under User-level Local Differential Privacy](https://mlsanity.com/paper/2410.09506/) (2024)
- [Consistent Estimation of Numerical Distributions under Local Differential Privacy by Wavelet Expansion](https://mlsanity.com/paper/2509.19661/) (2025)
- [Privately Estimating Black-Box Statistics](https://mlsanity.com/paper/2510.00322/) (2025)
- [Preserving Expert-Level Privacy in Offline Reinforcement Learning](https://mlsanity.com/paper/2411.13598/) (2024)

## Abstract (arXiv)

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.