Efficient Locally Private Algorithms for Estimation Problems

Abstract: In federated computation, user data is distributed over many devices which each communicate to some central server for downstream analytics and/or machine learning tasks. Already in the classical setting, there are many desiderata to be balanced in the system from accurate aggregation to low communication and fast runtime for the users and the server. Adding to the already delicate balancing, privacy concern necessitates new methods that are efficient and accurate while preserving the privacy of individual data. In this talk, we will focus on two basic tasks underlying many applications: computing the histogram of user data and estimating their mean. While the problems are well-studied, a lot of recent works have been devoted to developing efficient and optimally accurate algorithms beyond asymptotic behavior. We will describe new algorithms achieving near-optimal error, fast runtime, and low communication for these tasks. This is based on joint work with Hilal Asi, Vitaly Feldman, Jelani Nelson, and Kunal Talwar.

Bio: Huy Nguyen is an associate professor at Northeastern University. He received his MEng from MIT in 2009 and PhD from Princeton in 2014 under the supervision of Moses Charikar. In 2016, he joined Khoury College at Northeastern University. His research interests include algorithms for data streams and massively parallel computation, discrete and continuous optimization, differentially private algorithms, and machine learning.