Stable Estimators for Fast Private Statistics
A discussion on developing fast and near-optimal differentially private algorithms for fundamental statistical tasks, addressing challenges in high-dimensional data and existing methods.
A Google TechTalk, 2024-11-13, presented by Gavin Brown
Privacy in ML Seminar. ABSTRACT: The literature on differentially private estimation contains a range of approaches for many fundamental tasks. However, most existing algorithms have significant drawbacks, such as requiring strong prior bounds on the data or suffering in high dimensions. For many problems, 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 least squares. The analysis focuses on stabilizing a greedy, but carefully tuned, 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
Seminar notes & discussion
No public seminar notes on this lecture yet.