Streaming Algorithms for High-Dimensional Robust Statistics
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 estimation 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Stochastic OptimizationVocal Bursts Intensity PredictionSimilar Papers 제목 키워드 기반
Sub-linear RACE Sketches for Approximate Kernel Density Estimation on Streaming Data
Kernel density estimation is a simple and effective method that lies at the heart of many important machine learning applications. Unfortunately, kernel methods scale poorly for large, high dimensional datasets. Approxim…
Density EstimationCoresets for constrained k-median and k-means clustering in low dimensional Euclidean space
We study (Euclidean) $k$-median and $k$-means with constraints in the streaming model. There have been recent efforts to design unified algorithms to solve constrained $k$-means problems without using knowledge of the sp…
ClusteringOnline AUC Optimization for Sparse High-Dimensional Datasets
The Area Under the ROC Curve (AUC) is a widely used performance measure for imbalanced classification arising from many application domains where high-dimensional sparse data is abundant. In such cases, each $d$ dimensio…
imbalanced classificationVocal Bursts Intensity PredictionHistory PCA: A New Algorithm for Streaming PCA
In this paper we propose a new algorithm for streaming principal component analysis. With limited memory, small devices cannot store all the samples in the high-dimensional regime. Streaming principal component analysis …
Streaming Heteroscedastic Probabilistic PCA with Missing Data
Streaming principal component analysis (PCA) is an integral tool in large-scale machine learning for rapidly estimating low-dimensional subspaces from very high-dimensional data arriving at a high rate. However, modern d…
Astronomy