Uploaded January 2026 | Updated November 2026, 12 hours ago
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: arxiv.org/abs/2301.12250, arxiv.org/abs/2404.15409
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: arxiv.org/abs/2301.12250, arxiv.org/abs/2404.15409







