# Online Adversarial Attacks

arXiv: https://arxiv.org/abs/2103.02014 · HTML: https://mlsanity.com/paper/2103.02014/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 47 references that are in the map.
- First posted on arXiv 2 Mar 2021.

## Builds on (most cited first, 30 of 35)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Rethinking the Inception Architecture for Computer Vision](https://mlsanity.com/paper/1512.00567/) (2015)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Practical Black-Box Attacks against Machine Learning](https://mlsanity.com/paper/1602.02697/) (2016)
- [Ensemble Adversarial Training: Attacks and Defenses](https://mlsanity.com/paper/1705.07204/) (2017)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Black-box Adversarial Attacks with Limited Queries and Information](https://mlsanity.com/paper/1804.08598/) (2018)
- [Threat of Adversarial Attacks on Deep Learning in Computer Vision: A Survey](https://mlsanity.com/paper/1801.00553/) (2018)
- [Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samples](https://mlsanity.com/paper/1605.07277/) (2016)
- [Adversarial Attacks and Defences: A Survey](https://mlsanity.com/paper/1810.00069/) (2018)
- [MMA Training: Direct Input Space Margin Maximization through Adversarial Training](https://mlsanity.com/paper/1812.02637/) (2018)
- [Tactics of Adversarial Attack on Deep Reinforcement Learning Agents](https://mlsanity.com/paper/1703.06748/) (2017)
- [The Space of Transferable Adversarial Examples](https://mlsanity.com/paper/1704.03453/) (2017)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [Stealthy and Efficient Adversarial Attacks against Deep Reinforcement Learning](https://mlsanity.com/paper/2005.07099/) (2020)
- [Black-box Adversarial Attacks on Video Recognition Models](https://mlsanity.com/paper/1904.05181/) (2019)
- [Stateful Detection of Black-Box Adversarial Attacks](https://mlsanity.com/paper/1907.05587/) (2019)
- [MagNet and "Efficient Defenses Against Adversarial Attacks" are Not Robust to Adversarial Examples](https://mlsanity.com/paper/1711.08478/) (2017)
- [Secretaries with Advice](https://mlsanity.com/paper/2011.06726/) (2020)
- [Adversarial Example Games](https://mlsanity.com/paper/2007.00720/) (2020)
- [Prophet Inequalities with Limited Information](https://mlsanity.com/paper/1307.3736/) (2013)
- [Real-Time Adversarial Attacks](https://mlsanity.com/paper/1905.13399/) (2019)
- [Competitive Analysis with a Sample and the Secretary Problem](https://mlsanity.com/paper/1907.05350/) (2019)
- [ReMASC: Realistic Replay Attack Corpus for Voice Controlled Systems](https://mlsanity.com/paper/1904.03365/) (2019)
- [Prophet Secretary](https://mlsanity.com/paper/1507.01155/) (2015)

## Built on by (most cited first, 3 of 3)

- [Adversarial Learning in Real-World Fraud Detection: Challenges and Perspectives](https://mlsanity.com/paper/2307.01390/) (2023)
- [Provable Robustness for Streaming Models with a Sliding Window](https://mlsanity.com/paper/2303.16308/) (2023)
- [Bridging Optimal Transport and Jacobian Regularization by Optimal Trajectory for Enhanced Adversarial Defense](https://mlsanity.com/paper/2303.11793/) (2023)

## Abstract (arXiv)

Adversarial attacks expose important vulnerabilities of deep learning models, yet little attention has been paid to settings where data arrives as a stream. In this paper, we formalize the online adversarial attack problem, emphasizing two key elements found in real-world use-cases: attackers must operate under partial knowledge of the target model, and the decisions made by the attacker are irrevocable since they operate on a transient data stream. We first rigorously analyze a deterministic variant of the online threat model by drawing parallels to the well-studied k-secretary problem in theoretical computer science and propose Virtual+, a simple yet practical online algorithm. Our main theoretical result shows Virtual+ yields provably the best competitive ratio over all single-threshold algorithms for k<5 -- extending the previous analysis of the k-secretary problem. We also introduce the textitstochastic k-secretary -- effectively reducing online blackbox transfer attacks to a k-secretary problem under noise -- and prove theoretical bounds on the performance of Virtual+ adapted to this setting. Finally, we complement our theoretical results by conducting experiments on MNIST, CIFAR-10, and Imagenet classifiers, revealing the necessity of online algorithms in achieving near-optimal performance and also the rich interplay between attack strategies and online attack selection, enabling simple strategies like FGSM to outperform stronger adversaries.