[Theory] UC Theory Seminar: a reminder

[Alexander Razborov]

 Samuel Hopkins, PhD
Massachusetts Institute of Technology
 
 
 
 
 
Tuesday, May 16, 2023 at 3:30pm
Kent Chemical Laboratory, Room 120 (New Room)
 
 
Title: Robustness Implies Privacy in Statistical Estimation
 
Abstract:   We study the relationship between adversarial robustness and differential privacy in high-dimensional algorithmic statistics. We give the first black-box reduction from privacy to robustness which can produce private estimators with optimal tradeoffs among sample complexity, accuracy, and privacy for a wide range of fundamental high-dimensional parameter estimation problems, including mean and covariance estimation. We show that this reduction can be implemented in polynomial time in some important special cases. In particular, using nearly-optimal polynomial-time robust estimators for the mean and covariance of high-dimensional Gaussians which are based on the Sum-of-Squares method, we design the first polynomial-time private estimators for these problems with nearly-optimal samples-accuracy-privacy tradeoffs. Our algorithms are also robust to a constant fraction of adversarially-corrupted samples. Joint work with Gautam Kamath, Mahbod Majid, and Shyam Narayanan, to appear in STOC 2023.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20230515/a3a171b1/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.png
Type: image/png
Size: 80549 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20230515/a3a171b1/attachment-0001.png>