Timezone: »
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
-
2021 : Lossless Compression of Efficient Private Local Randomizers »
Vitaly Feldman · Kunal Talwar -
2021 : Differential Secrecy for Distributed Data and Applications to Robust Differentially Secure Vector Summation »
Kunal Talwar -
2021 : Private Sequential Hypothesis Testing for Statisticians: Privacy, Error Rates, and Sample Size »
Wanrong Zhang · Yajun Mei · Rachel Cummings -
2021 : Outlier-Robust Optimal Transport with Applications to Generative Modeling and Data Privacy »
Sloan Nietert · Rachel Cummings · Ziv Goldfeld -
2021 : Nonparametric Differentially Private Confidence Intervals for the Median »
Joerg Drechsler · Ira Globus-Harris · Audra McMillan · Adam Smith · Jayshree Sarathy -
2021 : Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling »
Vitaly Feldman · Audra McMillan · Kunal Talwar -
2021 : When Is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning? »
Gavin Brown · Mark Bun · Vitaly Feldman · Adam Smith · Kunal Talwar -
2021 : A Practitioners Guide to Differentially Private Convex Optimization »
Ryan McKenna · Hristo Paskov · Kunal Talwar -
2021 : “I need a better description”: An Investigation Into User Expectations For Differential Privacy »
Gabriel Kaptchuk · Rachel Cummings · Elissa M Redmiles -
2023 : Differentially Private Heavy Hitters using Federated Analytics »
Karan Chadha · Junye Chen · John Duchi · Vitaly Feldman · Hanieh Hashemi · Omid Javidbakht · Audra McMillan · Kunal Talwar -
2023 Poster: Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime »
Hilal Asi · Vitaly Feldman · Tomer Koren · Kunal Talwar -
2022 : Low-Communication Algorithms for Private Federated Data Analysis »
Kunal Talwar -
2022 Workshop: Theory and Practice of Differential Privacy »
Gautam Kamath · Audra McMillan -
2022 Poster: Optimal Algorithms for Mean Estimation under Local Differential Privacy »
Hilal Asi · Vitaly Feldman · Kunal Talwar -
2022 Oral: Optimal Algorithms for Mean Estimation under Local Differential Privacy »
Hilal Asi · Vitaly Feldman · Kunal Talwar -
2022 Poster: Private frequency estimation via projective geometry »
Vitaly Feldman · Jelani Nelson · Huy Nguyen · Kunal Talwar -
2022 Spotlight: Private frequency estimation via projective geometry »
Vitaly Feldman · Jelani Nelson · Huy Nguyen · Kunal Talwar -
2021 : Contributed Talks Session 2 »
Saeed Sharifi-Malvajerdi · Audra McMillan · Ryan McKenna -
2021 Workshop: Theory and Practice of Differential Privacy »
Rachel Cummings · Gautam Kamath -
2021 : Opening Remarks »
Gautam Kamath · Rachel Cummings -
2021 Poster: Private Adaptive Gradient Methods for Convex Optimization »
Hilal Asi · John Duchi · Alireza Fallah · Omid Javidbakht · Kunal Talwar -
2021 Poster: Lossless Compression of Efficient Private Local Randomizers »
Vitaly Feldman · Kunal Talwar -
2021 Poster: Private Stochastic Convex Optimization: Optimal Rates in L1 Geometry »
Hilal Asi · Vitaly Feldman · Tomer Koren · Kunal Talwar -
2021 Spotlight: Private Adaptive Gradient Methods for Convex Optimization »
Hilal Asi · John Duchi · Alireza Fallah · Omid Javidbakht · Kunal Talwar -
2021 Oral: Private Stochastic Convex Optimization: Optimal Rates in L1 Geometry »
Hilal Asi · Vitaly Feldman · Tomer Koren · Kunal Talwar -
2021 Spotlight: Lossless Compression of Efficient Private Local Randomizers »
Vitaly Feldman · Kunal Talwar -
2021 Poster: Characterizing Structural Regularities of Labeled Data in Overparameterized Models »
Ziheng Jiang · Chiyuan Zhang · Kunal Talwar · Michael Mozer -
2021 Oral: Characterizing Structural Regularities of Labeled Data in Overparameterized Models »
Ziheng Jiang · Chiyuan Zhang · Kunal Talwar · Michael Mozer -
2019 Poster: The advantages of multiple classes for reducing overfitting from test set reuse »
Vitaly Feldman · Roy Frostig · Moritz Hardt -
2019 Oral: The advantages of multiple classes for reducing overfitting from test set reuse »
Vitaly Feldman · Roy Frostig · Moritz Hardt