Robust Streaming, Sampling, and a Perspective on Online Learning

A young and rapidly growing field of theoretical computer science is that of robust streaming. The general subject of streaming faces many use cases in practice, coming up in problems like network traffic analysis and routing, reinforcement learning, database monitoring, server query response, distributed computing, etc. A nascent subfield of streaming concerns streaming algorithms that are robust to adversarially prepared streams, which can be found to have substantial practical grounding. For example, an adversary could submit a small amount of carefully chosen traffic to produce a denial-of-service attack in a network routing system; a robust routing algorithm in this setting would have immense practical use. We investigate this new field of robust streaming and in particular the formalization of robust sampling, which concerns sampling from an adversarially prepared stream to recover a representative sample. Throughout this survey, we also highlight, explore, and deepen the connection between the field of robust streaming and that of statistical online learning. On the surface, these fields can appear distinct and are often researched independently; however, there is a deep interrelatedness that can be used to generate new results and intuitons in both places. In this work we present an overview of statistical learning, followed by a survey of robust streaming techniques and challenges, culminating in several rigorous results proving the relationship that we motivate and hint at throughout the journey.