Recent computer science master’s graduate Mahbod Majid has been awarded a 2023 Faculty of Mathematics Graduate Research Excellence Award. The prestigious recognition comes with a $5,000 cash prize and is conferred annually to two graduate students in the Faculty of Mathematics who have authored or co-authored an outstanding research paper.
Mahbod’s paper, titled “Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism” and co-authored with his graduate advisor Professor Gautam Kamath and Professor Samuel Hopkins at MIT, was presented at STOC 2022, the 54th ACM Symposium of Theory of Computing, one of two top conferences in theoretical computer science.
Among the most basic of statistical tasks is estimating the mean of a distribution or population. Estimating this parameter is important not only in and of itself, but it is also an important building block in more complex machine learning procedures. However, estimating the mean of a distribution is much more difficult when preserving the privacy of the data is desirable or essential. If statistical techniques are applied without consideration for privacy, information can be leaked about the data.
This is of paramount concern if the dataset contains sensitive information, such as a person’s medical and health records or other confidential information. For this reason, much research has been conducted to develop what are known as differentially private estimation algorithms — mathematically rigorous ways to obtain information about a dataset by describing the patterns within it while withholding information about individuals.
Mahbod’s paper solved a core problem in private statistical estimation, one that has been open for several years.
“This is the first algorithm for mean estimation that is simultaneously computationally efficient, with an optimal number of samples while subject to pure differential privacy,” Professor Kamath explained. “Previously developed algorithms had achieved two out of three of these goals at any given time, but Mahbod’s elegant solution satisfies all three simultaneously. It is not only a nearly-optimal solution for the most fundamental statistical task under strong privacy constraints, but it also closes a long-standing gap in our understanding of private multivariate statistics.”
Since Mahbod’s paper was presented in 2022, it has attracted the attention of researchers in adjacent fields and inspired several follow-up works. Moreover, his solution shows interesting new connections between privacy and robustness of statistical estimation algorithms.
Mahbod Majid is currently a first-year PhD student in the Machine Learning Department at Carnegie Mellon University’s School of Computer Science. His research interests are in algorithms, theoretical machine learning, sum-of-squares optimization, differential privacy, and high dimensional statistics.
To learn more about this award-winning research, please see Samuel B. Hopkins, Gautam Kamath, Mahbod Majid. 2022. Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC ’22), June 20–24, 2022, Rome, Italy.
