Fast Streaming Algorithms for High-Dimensional Optimization

A fundamental problem in machine learning is to design algorithms that extract essential structure in large, dynamically growing datasets with provable statistical guarantees. The streaming model captures this challenge by requiring algorithms to process data sequentially and irreversibly using memory sublinear in the input size. While prior work has achieved near-optimal space bounds for fundamental problems such as clustering and dimensionality reduction, these guarantees often rely on costly per-update computation, limiting their relevance for large datasets. We study whether both fast update time and optimal space can be achieved simultaneously for high-dimensional geometric problems in insertion-only streams. We present a general streaming framework that combines coarse and refined sampling schemes to accelerate the update time. Applying this framework, we obtain new streaming algorithms for Euclidean $(k,z)$-clustering, $L_p$ subspace embeddings, and projection-cost preservation with near-linear update time and space independent of the stream length. In particular, we achieve an exponential improvement in $k$ in the update time for $(k,z)$-clustering compared to previous state-of-the-art streaming algorithms. For subspace embedding and projection-cost preservation, we show that the total update time achieves input-sparsity time, demonstrating that there does not necessarily exist a separation between the runtime of streaming and offline algorithms. Moreover, we do not lose additional factors in space complexity compared to previous algorithms that give the best space.