Abstract: Differential privacy provides a rigorous framework for ensuring that the outputs of data-driven systems do not reveal too much sensitive information about individuals in their input. For statistical estimation, practical private algorithms should ideally combine strong accuracy guarantees, computational efficiency, robustness, and minimal reliance on user-specified assumptions. In this talk, I will present algorithmic techniques for private multivariate estimation that achieve strong error guarantees without requiring prior information about the data, by leveraging robustness against data poisoning attacks. I will highlight the deeper connection between differential privacy and robustness that underlies these results. Finally, I will discuss how this connection also reveals inherent limitations for designing computationally efficient estimators, as well as new directions to overcome them.
This talk is based on the following joint works:
- Covariance-aware private mean estimation without covariance estimation: Brown, Gaboardi, Smith, Ullman, Zakynthinou (NeurIPS 2021)
- From robustness to privacy and back: Asi, Ullman, Zakynthinou (ICML 2023)
- Tukey depth mechanisms for practical private mean estimation: Brown, Zakynthinou (ongoing, 2025)
Bio: Lydia Zakynthinou is an assistant professor of Computer Science at Johns Hopkins University and a member of DSAI. Before joining JHU, she was a FODSI postdoctoral fellow at the Simons Institute for the Theory of Computing, UC Berkeley, hosted by Michael I. Jordan. She received her Ph.D. in Computer Science from Northeastern University, advised by Jonathan Ullman and Huy Nguyen, and her M.S. in Logic, Algorithms, and Theory of Computation, as well as her B.S. in Electrical and Computer Engineering, from the National Technical University of Athens, Greece. Her research focuses on the theoretical foundations of trustworthy machine learning and statistics, with an emphasis on data privacy. She is also a committee member of the Learning Theory Alliance, a community-building initiative.