Timezone: »

Mean Estimation with User-level Privacy under Data Heterogeneity
Rachel Cummings · Vitaly Feldman · Audra McMillan · Kunal Talwar

A key challenge for data analysis in the federated setting is that user data is heterogeneous, i.e., it cannot be assumed to be sampled from the same distribution. Further, in practice, different users may possess vastly different number of samples. In this work we propose a simple model of heterogeneous user data that differs in both distribution and quantity of data, and we provide a method for estimating the population-level mean while preserving user-level differential privacy. We demonstrate asymptotic optimality of our estimator within a natural class of private estimators and also prove general lower bounds on the error achievable in our problem. In particular, while the optimal non-private estimator can be shown to be linear, we show that privacy constrains us to use a non-linear estimator.

Author Information

Rachel Cummings (Columbia University)
Vitaly Feldman (Google Brain)
Audra McMillan (Apple)
Kunal Talwar (Apple)

More from the Same Authors