# Matrix Factorization for Practical Continual Mean Estimation Under User-Level Differential Privacy

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 36 of its 56 references that are in the map.
- First posted on arXiv 29 Jan 2026.

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

- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Finite Sample Differentially Private Confidence Intervals](https://mlsanity.com/paper/1711.03908/) (2017)
- [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)
- [Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams](https://mlsanity.com/paper/2202.08312/) (2022)
- [(Amplified) Banded Matrix Factorization: A unified approach to private training](https://mlsanity.com/paper/2306.08153/) (2023)
- [Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning](https://mlsanity.com/paper/2211.06530/) (2022)
- [Learning discrete distributions: user vs item-level privacy](https://mlsanity.com/paper/2007.13660/) (2020)
- [Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation](https://mlsanity.com/paper/2001.03618/) (2020)
- [The Power of Factorization Mechanisms in Local and Central Differential Privacy](https://mlsanity.com/paper/1911.08339/) (2019)
- [Tight and Robust Private Mean Estimation with Few Users](https://mlsanity.com/paper/2110.11876/) (2021)
- [Mind the Privacy Unit! User-Level Differential Privacy for Language Model Fine-Tuning](https://mlsanity.com/paper/2406.14322/) (2024)
- [Constant matters: Fine-grained Complexity of Differentially Private Continual Observation](https://mlsanity.com/paper/2202.11205/) (2022)
- [Correlated Noise Provably Beats Independent Noise for Differentially Private Learning](https://mlsanity.com/paper/2310.06771/) (2023)
- [Discrete Distribution Estimation under User-level Local Differential Privacy](https://mlsanity.com/paper/2211.03757/) (2022)
- [Scaling up the Banded Matrix Factorization Mechanism for Differentially Private ML](https://mlsanity.com/paper/2405.15913/) (2024)
- [Federated Linear Contextual Bandits with User-level Differential Privacy](https://mlsanity.com/paper/2306.05275/) (2023)
- [A Smooth Binary Mechanism for Efficient Private Continual Observation](https://mlsanity.com/paper/2306.09666/) (2023)
- [User-Level Differential Privacy With Few Examples Per User](https://mlsanity.com/paper/2309.12500/) (2023)
- [User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates](https://mlsanity.com/paper/2311.03797/) (2023)
- [Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries](https://mlsanity.com/paper/2403.00028/) (2024)
- [Banded Square Root Matrix Factorization for Differentially Private Model Training](https://mlsanity.com/paper/2405.13763/) (2024)
- [ULDP-FL: Federated Learning with Across Silo User-Level Differential Privacy](https://mlsanity.com/paper/2308.12210/) (2023)
- [Mean Estimation with User-level Privacy under Data Heterogeneity](https://mlsanity.com/paper/2307.15835/) (2023)
- [Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGD](https://mlsanity.com/paper/2505.12128/) (2025)
- [Private Mean Estimation with Person-Level Differential Privacy](https://mlsanity.com/paper/2405.20405/) (2024)
- [Continual Mean Estimation Under User-Level Privacy](https://mlsanity.com/paper/2212.09980/) (2022)
- [Continual Release Moment Estimation with Differential Privacy](https://mlsanity.com/paper/2502.06597/) (2025)
- [Improved Communication-Privacy Trade-offs in L2 Mean Estimation under Streaming Differential Privacy](https://mlsanity.com/paper/2405.02341/) (2024)
- [Count on Your Elders: Laplace vs Gaussian Noise](https://mlsanity.com/paper/2408.07021/) (2024)

## Abstract (arXiv)

We study continual mean estimation, where data vectors arrive sequentially and the goal is to maintain accurate estimates of the running mean. We address this problem under user-level differential privacy, which protects each user's entire dataset even when they contribute multiple data points. Previous work on this problem has focused on pure differential privacy. While important, this approach limits applicability, as it leads to overly noisy estimates. In contrast, we analyze the problem under approximate differential privacy, adopting recent advances in the Matrix Factorization mechanism. We introduce a novel mean estimation specific factorization, which is both efficient and accurate, achieving asymptotically lower mean-squared error bounds in continual mean estimation under user-level differential privacy.