Position:  PhD Candidate

Current Institution:  Massachusetts Institute of Technology

Abstract:  Differentially Private Identity and Equivalence Testing of Discrete Distributions

We study the fundamental problems of identity and equivalence testing over a discrete population from random samples. Our goal is to develop efficient testers while guaranteeing differential privacy to the individuals of the population. We provide sample-efficient differentially private testers for these problems. Our theoretical results significantly improve over the best known algorithms for identity testing and are the first results for private equivalence testing. The conceptual message of our work is that there exist private hypothesis testers that are nearly as sample-efficient as their non-private counterparts. We perform an experimental evaluation of our algorithms on synthetic data. Our experiments illustrate that our private testers achieve small type I and type II errors with sample size sublinear in the domain size of the underlying distributions. Specifically, the sample complexity of our private identity tester significantly outperforms the sample complexity of recently proposed methods for this problem.

Bio:
Maryam Aliakbarpour is a PhD candidate in the Department of Electrical Engineering and Computer Science at MIT, conducting research under the supervision of Professor Ronitt Rubinfeld. She received a master’s degree in EECS from MIT and a bachelor’s degree in computer engineering from Sharif University of Technology. Her research interest is in sublinear algorithm learning theory and property testing, in particular property testing of distributions. She conducted several research projects on the topic, including differentially private testing of distribution testing and learning junta distributions incrementally improving visualizations of datasets. She eceived the Neekeyfar Award from the MIT Office of the Dean for Graduate Education at MIT in 2013. She was also awarded the silver medal in Iranian National Olympiad in Informatics 2008.