Timezone: »

 
Poster
Streaming Algorithms for High-Dimensional Robust Statistics
Ilias Diakonikolas · Daniel Kane · Ankit Pensia · Thanasis Pittas

Wed Jul 20 03:30 PM -- 05:30 PM (PDT) @ Hall E #1120
in Poster Session 2 »

We study high-dimensional robust statistics tasks in the streaming model. A recent line of work obtained computationally efficient algorithms for a range of high-dimensional robust statistics tasks. Unfortunately, all previous algorithms require storing the entire dataset, incurring memory at least quadratic in the dimension. In this work, we develop the first efficient streaming algorithms for high-dimensional robust statistics with near-optimal memory requirements (up to logarithmic factors). Our main result is for the task of high-dimensional robust mean estimation in (a strengthening of) Huber's contamination model. We give an efficient single-pass streaming algorithm for this task with near-optimal error guarantees and space complexity nearly-linear in the dimension. As a corollary, we obtain streaming algorithms with near-optimal space complexity for several more complex tasks, including robust covariance estimation, robust regression, and more generally robust stochastic optimization.

Keywords: T: Learning Theory
[ Slides]  [ Poster]  [ Paper PDF] 

Author Information

Ilias Diakonikolas (University of Wisconsin-Madison)
Daniel Kane (UCSD)
Ankit Pensia (University of Wisconsin-Madison)
Thanasis Pittas (University of Wisconsin-Madison)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors