Streaming Algorithms

Follow this topic Ask about this topic

Streaming algorithms study how to process data as it arrives without storing or repeatedly revisiting the entire dataset, which matters when data is too large, fast-changing, or costly to retain. Core approaches include sketches, sampling, and coresets for compact summaries, alongside online optimization and state-tracking methods for tasks such as PCA, clustering, regression, and reinforcement learning. Current work also applies these ideas to real-time systems, where memory, computation, communication, and latency are tightly constrained. A central challenge is balancing accuracy and formal guarantees against limited resources, especially when the data distribution changes or the stream contains outliers.

Latest papers

61 papers9 papers in the last four weeks, up 80% on the four weeks before. 0.1% of all new papers.

Robust Streaming PCA
Feb 8, 2019Daniel Bienstock, Minchan Jeong, Apurv Shukla +1Principal Component Analysis Streaming Algorithms
Graduate School of AI KAIST

Feb 8, 2019J/K move · Enter open · S save

Robust Streaming PCA

Daniel Bienstock, Minchan Jeong, Apurv Shukla, Se-Young Yun

Graduate School of AI KAIST

Principal Component Analysis Streaming Algorithms Spectral Methods Non-Stationary Time Series

Open paper AskPDF arXiv

We consider streaming principal component analysis when the stochastic data generating model is subject to perturbations. While existing models assume a fixed covariance, we adopt a robust perspective where the covariance matrix belongs to a temporal uncertainty set. Under this setting, we provide fundamental limits on convergence of any algorithm recovering principal components. We analyze the convergence of the noisy power method and Oja's algorithm, both studied for the stationary data generating model, and argue that the noisy power method is rate-optimal in our setting. Finally, we demonstrate the validity of our analysis through numerical experiments on synthetic and real-world datasets.