# Continual Mean Estimation Under User-Level Privacy

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 51 references that are in the map.
- First posted on arXiv 20 Dec 2022.

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

- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [CoinPress: Practical Private Mean and Covariance Estimation](https://mlsanity.com/paper/2006.06618/) (2020)
- [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)
- [Private Hypothesis Selection](https://mlsanity.com/paper/1905.13229/) (2019)
- [Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation](https://mlsanity.com/paper/1906.02830/) (2019)
- [Learning discrete distributions: user vs item-level privacy](https://mlsanity.com/paper/2007.13660/) (2020)
- [The Price of Differential Privacy under Continual Observation](https://mlsanity.com/paper/2112.00828/) (2021)
- [Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints](https://mlsanity.com/paper/1802.08417/) (2018)
- [Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction](https://mlsanity.com/paper/1812.11476/) (2018)
- [A Primer on Private Statistics](https://mlsanity.com/paper/2005.00010/) (2020)
- [Generalization for Adaptively-chosen Estimators via Stable Median](https://mlsanity.com/paper/1706.05069/) (2017)
- [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)
- [Inference under Information Constraints II: Communication Constraints and Shared Randomness](https://mlsanity.com/paper/1905.08302/) (2019)
- [Fisher information under local differential privacy](https://mlsanity.com/paper/2005.10783/) (2020)
- [Distributed Gaussian Mean Estimation under Communication Constraints: Optimal Rates and Communication-Efficient Algorithms](https://mlsanity.com/paper/2001.08877/) (2020)
- [Discrete Distribution Estimation under User-level Local Differential Privacy](https://mlsanity.com/paper/2211.03757/) (2022)
- [Interactive Inference under Information Constraints](https://mlsanity.com/paper/2007.10976/) (2020)
- [Local differential privacy: Elbow effect in optimal density estimation and adaptation over Besov ellipsoids](https://mlsanity.com/paper/1903.01927/) (2019)
- [Inference under Information Constraints III: Local Privacy Constraints](https://mlsanity.com/paper/2101.07981/) (2021)
- [Mean Estimation from One-Bit Measurements](https://mlsanity.com/paper/1901.03403/) (2019)
- [Optimal Rates for Nonparametric Density Estimation under Communication Constraints](https://mlsanity.com/paper/2107.10078/) (2021)
- [User-Level Private Learning via Correlated Sampling](https://mlsanity.com/paper/2110.11208/) (2021)
- [Local Differential Privacy for Evolving Data](https://mlsanity.com/paper/1802.07128/) (2018)
- [Optimal distributed composite testing in high-dimensional Gaussian models with 1-bit communication](https://mlsanity.com/paper/2012.04957/) (2020)
- [Private Continual Release of Real-Valued Data Streams](https://mlsanity.com/paper/1811.03197/) (2018)
- [Identifying Participants in the Personal Genome Project by Name (A Re-identification Experiment)](https://mlsanity.com/paper/1304.7605/) (2013)

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

- [Fine-Tuning Large Language Models with User-Level Differential Privacy](https://mlsanity.com/paper/2407.07737/) (2024)
- [A Bias-Accuracy-Privacy Trilemma for Statistical Estimation](https://mlsanity.com/paper/2301.13334/) (2023)
- [A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions](https://mlsanity.com/paper/2304.06787/) (2023)
- [Online Differentially Private Synthetic Data Generation](https://mlsanity.com/paper/2402.08012/) (2024)
- [Matrix Factorization for Practical Continual Mean Estimation Under User-Level Differential Privacy](https://mlsanity.com/paper/2601.22320/) (2026)

## Abstract (arXiv)

We consider the problem of continually releasing an estimate of the population mean of a stream of samples that is user-level differentially private (DP). At each time instant, a user contributes a sample, and the users can arrive in arbitrary order. Until now these requirements of continual release and user-level privacy were considered in isolation. But, in practice, both these requirements come together as the users often contribute data repeatedly and multiple queries are made. We provide an algorithm that outputs a mean estimate at every time instant t such that the overall release is user-level varepsilon-DP and has the following error guarantee: Denoting by Mt the maximum number of samples contributed by a user, as long as tildeOmega(1/varepsilon) users have Mt/2 samples each, the error at time t is tildeO(1/√t+√Mt/tvarepsilon). This is a universal error guarantee which is valid for all arrival patterns of the users. Furthermore, it (almost) matches the existing lower bounds for the single-release setting at all time instants when users have contributed equal number of samples.