Matrix Factorization for Practical Continual Mean Estimation Under User-Level Differential Privacy
This work addresses the challenge of maintaining accurate running mean estimates in sequential data streams while protecting user privacy, offering a more practical solution for applications where approximate differential privacy is acceptable.
The paper tackled the problem of continual mean estimation under user-level differential privacy by introducing a novel matrix factorization method, achieving asymptotically lower mean-squared error bounds compared to previous pure differential privacy approaches.
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.