# Algorithms for bounding contribution for histogram estimation under user-level privacy

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 50 references that are in the map.
- First posted on arXiv 7 Jun 2022.

## Builds on (most cited first, 22 of 22)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [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)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Beyond Inferring Class Representatives: User-Level Privacy Leakage From Federated Learning](https://mlsanity.com/paper/1812.00535/) (2018)
- [Differentially Private Learning with Adaptive Clipping](https://mlsanity.com/paper/1905.03871/) (2019)
- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [Generative Models for Effective ML on Private, Decentralized Datasets](https://mlsanity.com/paper/1911.06679/) (2019)
- [A General Approach to Adding Differential Privacy to Iterative Training Procedures](https://mlsanity.com/paper/1812.06210/) (2018)
- [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)
- [Differentially Private Assouad, Fano, and Le Cam](https://mlsanity.com/paper/2004.06830/) (2020)
- [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)
- [Federated Learning of N-gram Language Models](https://mlsanity.com/paper/1910.03432/) (2019)
- [Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction](https://mlsanity.com/paper/1812.11476/) (2018)
- [Differentially Private SQL with Bounded User Contribution](https://mlsanity.com/paper/1909.01917/) (2019)
- [Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication](https://mlsanity.com/paper/1802.04705/) (2018)
- [Tight and Robust Private Mean Estimation with Few Users](https://mlsanity.com/paper/2110.11876/) (2021)
- [Differentially private anonymized histograms](https://mlsanity.com/paper/1910.03553/) (2019)

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

- [PrE-Text: Training Language Models on Private Federated Data in the Age of LLMs](https://mlsanity.com/paper/2406.02958/) (2024)
- [Fine-Tuning Large Language Models with User-Level Differential Privacy](https://mlsanity.com/paper/2407.07737/) (2024)
- [Private Federated Multiclass Post-hoc Calibration](https://mlsanity.com/paper/2510.01987/) (2025)
- [DP-LAC: Lightweight Adaptive Clipping for Differentially Private Federated Fine-tuning of Language Models](https://mlsanity.com/paper/2605.10272/) (2026)

## Abstract (arXiv)

We study the problem of histogram estimation under user-level differential privacy, where the goal is to preserve the privacy of all entries of any single user. We consider the heterogeneous scenario where the quantity of data can be different for each user. In this scenario, the amount of noise injected into the histogram to obtain differential privacy is proportional to the maximum user contribution, which can be amplified by few outliers. One approach to circumvent this would be to bound (or limit) the contribution of each user to the histogram. However, if users are limited to small contributions, a significant amount of data will be discarded. In this work, we propose algorithms to choose the best user contribution bound for histogram estimation under both bounded and unbounded domain settings. When the size of the domain is bounded, we propose a user contribution bounding strategy that almost achieves a two-approximation with respect to the best contribution bound in hindsight. For unbounded domain histogram estimation, we propose an algorithm that is logarithmic-approximation with respect to the best contribution bound in hindsight. This result holds without any distribution assumptions on the data. Experiments on both real and synthetic datasets verify our theoretical findings and demonstrate the effectiveness of our algorithms. We also show that clipping bias introduced by bounding user contribution may be reduced under mild distribution assumptions, which can be of independent interest.