In traditional machine learning and optimization, we assume unrestricted access to a static dataset. We can loop over the data for hundreds of epochs, compute global statistics like variance or gradients, and revisit any data point at will. However, real-world applications—ranging from ICU monitoring to real-time network routing—generate continuous, high-volume data streams where these assumptions collapse. As highlighted by Hammer et al., high-velocity streams break the independent and identically distributed (i.i.d.) assumption and exceed available random-access memory, forcing a shift toward incremental, real-time adaptation.
Under a single-pass streaming constraint, an algorithm encounters each data point exactly once. Once a sample passes, it must be discarded immediately due to privacy laws or physical storage limits (Kim et al.). Crucially, decisions made on each point are irrevocable: a discarded point cannot be recovered, and a stored point cannot be easily pruned later without violating memory bounds (Cohen et al.). The fundamental challenge is to learn or optimize effectively under this severe lack of global visibility.
The Irrevocability Dilemma and the Power of Thresholds
Why is single-pass optimization so difficult? Consider the problem of subset selection, such as maximizing a submodular function to select a representative summary or a diverse set of sensor locations. In an offline setting, a greedy algorithm can scan all items and repeatedly pick the one that provides the highest marginal gain. In a stream, however, you must decide whether to keep or reject an item immediately upon arrival, without knowing what items will arrive next (Chekuri et al.). If you accept an item too early, you fill up your limited memory with mediocre candidates; if you wait too long for perfect candidates, the stream might end, leaving you with an empty or suboptimal solution (Maiti et al.).
To resolve this dilemma, streaming algorithms rely on dynamic thresholding. Instead of comparing an incoming item to all other items, the algorithm compares it to a mathematically derived threshold that represents the "expected value" of a high-quality item. For instance, Ene et al. demonstrate that maintaining a running set of guesses for the optimal value allows an algorithm to make robust, irreversible decisions on the fly. If data arrives in a random rather than adversarial order, Norouzi-Fard et al. show that we can even break traditional theoretical approximation barriers by dynamically adjusting these acceptance thresholds as the stream progresses.
Data Summarization: Sketches and Coresets
When the goal is to train a model on a massive dataset that cannot fit into memory, storing raw data is impossible. Instead, algorithms must construct a compressed, running summary of the data—known as a sketch or a coreset—that preserves the essential geometric or statistical properties of the full dataset.
A classic example is matrix sketching. If data arrives row by row, how do we maintain a low-rank approximation without storing the full matrix? Edo Liberty introduced a deterministic "frequent directions" technique that shrinks the sketch periodically by reducing the principal components, ensuring that the approximation error decays predictably.
For more complex structures, such as tensor factorization, Chhaya et al. utilize randomized filtering to build streaming coresets, ensuring the summary remains highly representative of the underlying population while maintaining a tiny memory footprint. Similarly, for online row sampling, Cohen et al. leverage ridge leverage scores to make immediate, one-pass decisions on whether to retain a row, guaranteeing a high-quality spectral approximation even against adversarial data orderings.
Incremental Model Adaptation Without Retraining
Beyond data summarization, how do we train complex predictive models like deep neural networks or support vector machines (SVMs) when data cannot be revisited? Traditional backpropagation relies on multiple epochs over a static batch to minimize loss functions, which is entirely incompatible with infinite streams (Sahoo et al.).
To train models in a single pass, researchers reframe the learning architecture to update its internal state incrementally per instance. For example, Rai et al. reframe SVM classification as a geometric "Minimum Enclosing Ball" problem, allowing the model to update its decision boundary using each data point exactly once while maintaining a constant memory footprint.
For deep neural networks, Sahoo et al. propose attaching classifiers to every hidden layer and using a hedging algorithm to dynamically weight their contributions. This allows the network to adapt its effective depth on the fly, converging quickly on shallow representations before transitioning to deeper ones as more data streams in. When labels are scarce or weak, Vivien Cabannes demonstrates that one can design weak queries to reconstruct unbiased stochastic gradients, achieving optimal learning rates in a single interaction.
The Cost of Forgetting: Memory Bounds and Trade-offs
Operating under strict memory constraints introduces a fundamental trade-off between the amount of working memory allocated and the accuracy or reproducibility of the system. If an algorithm is forced to maintain a polylogarithmic memory footprint, it must sacrifice global context (Pawling et al.).
This "cost of forgetting" can be formally quantified:
- Irreversibility in Bandits: In multi-armed bandit settings where an arm discarded from memory can never be sampled again, Maiti et al. establish strict lower bounds on regret, illustrating the exact mathematical penalty of limited memory.
- The Reproducibility Tax: Braverman et al. show that if an algorithm must be pseudo-deterministic—meaning it uses randomness but must produce reproducible outputs at every point in time—it faces a significant memory "tax" compared to standard randomized counters.
- Streaming Inference: When performing statistical inference or hypothesis testing on streams, Wenhai Cui demonstrates that we must strategically frame the construction of test statistics to operate via sequential updates and constant memory, bypassing the need to load entire datasets.