Provable Robustness for Streaming Models with a Sliding Window

Aounon Kumar, Vinu Sankar Sadasivan, Soheil FeiziarXiv 2023 · DOI · arXiv

In the domain of machine learning, "robustness" typically refers to a model's resilience against small, adversarial perturbations to static inputs, such as images. However, real-world applications—ranging from autonomous vehicle sensor processing to high-frequency algorithmic trading—often involve continuous data streams. In these scenarios, the assumption of independent inputs fails; data points are highly correlated, and adversaries can strategically time their attacks.

A recent study from researchers at the University of Maryland, titled "Provable Robustness for Streaming Models with a Sliding Window," addresses this gap. The paper introduces the first mathematical framework for certifying the performance of models processing data streams, ensuring that robustness guarantees do not degrade as the stream length increases.

The Challenge of Streaming Robustness

Standard provable robustness techniques, such as randomized smoothing, are designed for static tasks. Applying them to streaming data presents three primary challenges:

  1. Correlated Inputs: A single data point may influence multiple consecutive decision windows.
  2. Adaptive Adversaries: Unlike static attackers, a streaming adversary can observe past model outputs to decide when to inject noise, potentially "saving" their perturbation budget for high-impact moments.
  3. Infinite Horizon: Most sequential proofs weaken as the sequence grows, eventually providing "vacuous" (useless) guarantees for long-term streams.
The streaming threat model where an adversary perturbs inputs within a sliding window.

Methodology: Efficient Randomized Smoothing

The researchers focus on models utilizing a fixed-size sliding window ($w$), where the model's prediction at any time step depends only on the most recent $w$ inputs. To defend these models, they employ a specialized version of Randomized Smoothing.

While traditional smoothing requires thousands of noised evaluations per input—a prohibitive cost for real-time streams—this paper proposes Single-Sample Smoothing. By adding a single noise vector to the input, the authors prove a guarantee for the average performance across the entire stream. Using Jensen’s Inequality and total variation distance properties, they derived a bound showing that performance degradation is proportional to the window size ($w$) and the average noise added by the attacker ($\epsilon$), crucially remaining independent of the stream length ($t$).

Experimental Evaluation

The approach was evaluated on two real-world streaming tasks: UCI HAR (Human Activity Recognition) using 6-D sensor data, and a Speech Commands dataset modified to simulate continuous audio for keyword detection.

Key Findings

  • The Window Size Trade-off: Theory and experiments both indicate that robustness is inversely tied to the model's memory. Smaller sliding windows ($w$) lead to more robust models, creating a trade-off between temporal context and defensibility.
  • Budget Flexibility: The certificate holds even against adversaries who strategically allocate their perturbation budget, whether they spread noise evenly or concentrate it on specific frames.
  • Empirical Validation: The researchers tested their models against a custom "Streaming Attack." In all trials, the empirical performance remained above the theoretical "floor" established by their certificates.
Impact of window size $w$ on certified accuracy across different perturbation budgets $\epsilon$.

Conclusion and Future Directions

This work provides a foundational step toward securing real-time AI systems. By proving that average-case guarantees can be maintained over infinite streams with minimal computational overhead, the authors make provable robustness viable for high-frequency applications.

Future research may look to extend these proofs to Recurrent Neural Networks (RNNs) or LSTMs, which possess "infinite" hidden state memory, and to refine the mathematical bounds to provide even tighter, more predictive certificates for safety-critical systems.

Summary updated

Abstract

The literature on provable robustness in machine learning has primarily focused on static prediction problems, such as image classification, in which input samples are assumed to be independent and model performance is measured as an expectation over the input distribution. Robustness certificates are derived for individual input instances with the assumption that the model is evaluated on each instance separately. However, in many deep learning applications such as online content recommendation and stock market analysis, models use historical data to make predictions. Robustness certificates based on the assumption of independent input samples are not directly applicable in such scenarios. In this work, we focus on the provable robustness of machine learning models in the context of data streams, where inputs are presented as a sequence of potentially correlated items. We derive robustness certificates for models that use a fixed-size sliding window over the input stream. Our guarantees hold for the average model performance across the entire stream and are independent of stream size, making them suitable for large data streams. We perform experiments on speech detection and human activity recognition tasks and show that our certificates can produce meaningful performance guarantees against adversarial perturbations.
BibTeX
@misc{kumar2023provable,
  author = {Aounon Kumar and Vinu Sankar Sadasivan and Soheil Feizi},
  title = {{Provable Robustness for Streaming Models with a Sliding Window}},
  year = {2023},
  eprint = {2303.16308},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2303.16308},
}
Figure