Stable Estimators for Fast Private Statistics
Host
Noah Golowich
MIT
Abstract:
A long line of work establishes statistical algorithms that satisfy differential privacy, a strong notion of privacy protection. Most existing algorithms have significant drawbacks, requiring prior bounds on the data or suffering in high dimensions. For many basic tasks, the best known algorithms require exponential time.
In this talk, we will discuss a new approach that leads to fast and near-optimal private algorithms for mean estimation, covariance estimation, and linear regression. The analysis focuses on stabilizing a greedy, but careful, outlier-removal process.
Based on work with Sam Hopkins, Adam Smith, Jon Hayase, Xiyang Liu, Weihao Kong, Sewoong Oh, and Juan Perdomo.
arxiv links: https://arxiv.org/abs/2301.12250, https://arxiv.org/abs/2404.15409
A long line of work establishes statistical algorithms that satisfy differential privacy, a strong notion of privacy protection. Most existing algorithms have significant drawbacks, requiring prior bounds on the data or suffering in high dimensions. For many basic tasks, the best known algorithms require exponential time.
In this talk, we will discuss a new approach that leads to fast and near-optimal private algorithms for mean estimation, covariance estimation, and linear regression. The analysis focuses on stabilizing a greedy, but careful, outlier-removal process.
Based on work with Sam Hopkins, Adam Smith, Jon Hayase, Xiyang Liu, Weihao Kong, Sewoong Oh, and Juan Perdomo.
arxiv links: https://arxiv.org/abs/2301.12250, https://arxiv.org/abs/2404.15409