Efficient Algorithms for Locally Private Estimation with Optimal Accuracy Guarantees

Abstract:

Locally Differentially Private (LDP) reports are commonly used for collection of statistics and machine learning in the federated setting with an untrusted server. We study the efficiency of two basic tasks, frequency estimation and vector mean estimation, using LDP reports. Existing algorithms for these problems that achieve the lowest error are neither communication nor computation efficient in the high-dimensional regime. In this talk I’ll describe new efficient LDP algorithms for these tasks that achieve the optimal error (up to lower order terms) and are efficient in both theory and practice.
Based on joint works with Hilal Asi, Jelani Nelson, Huy Nguyen and Kunal Talwar.

Bio:

Vitaly Feldman is a research scientist at Apple ML Research working on foundations of machine learning and privacy-preserving data analysis. Vitaly holds a Ph.D. from Harvard and was previously a research scientist at Google and IBM Research. His work on understanding of memorization in learning was recognized by the 2021 Caspar Bowden Award for Outstanding Research in Privacy Enhancing Technologies and his research on foundations of adaptive data analysis was featured in CACM Research Highlights and Science. His works were also recognized by the COLT Best Student Paper Award in 2005 and 2013 and by the IBM Research Best Paper Award in 2014, 2015 and 2016. He served as a program co-chair for COLT 2016 and ALT 2021 conferences and as a co-organizer of the Simons Institute Program on Data Privacy in 2019.