Data Science Seminar
Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators
Samson Zhou
Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators
| When | Friday, February 19, 2021, 2:00 PM – 3:00 PM (MT) |
|---|
Abstract
We introduce difference estimators for data stream computation, which provide approximations to F(v)-F(u) for frequency vectors v,u and a given function F. We show how to use such estimators to carefully trade error for memory in an iterative manner. The function F is generally non-linear, and we give the first difference estimators for the frequency moments F_p for p between 0 and 2, as well as for integers p>2. Using these, we resolve a number of central open questions in adversarial robust streaming and sliding window models.
For both models, we obtain algorithms for norm estimation whose dependence on epsilon is 1/epsilon^2, which shows, up to logarithmic factors, that there is no overhead over the standard insertion-only data stream model for these problems.
Speaker
Samson Zhou
CMU
Samson is a postdoctoral researcher at Carnegie Mellon University, hosted by David P. Woodruff. He received his PhD from Purdue, where he was advised by Greg Frederickson and Elena Grigorescu. He spent a year as a postdoctoral researcher at Indiana University, hosted by Grigory Yaroslavtsev. His research focuses on the theoretical foundations of data science, including sublinear algorithms with an emphasis on streaming algorithms, machine learning, and numerical linear algebra.
Tags: algorithms & theory statistics
Part of the Data Science Seminar. Something wrong on this page? Edit _data/talks/2021-02-19-samson-zhou.toml.