# Theoretical Analysis of Adversarial Learning: A Minimax Approach

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2018.

## Built on by (most cited first, 30 of 31)

- [Improving Robustness using Generated Data](https://mlsanity.com/paper/2110.09468/) (2021)
- [Robust Prompt Optimization for Defending Language Models Against Jailbreaking Attacks](https://mlsanity.com/paper/2401.17263/) (2024)
- [Exploring Memorization in Adversarial Training](https://mlsanity.com/paper/2106.01606/) (2021)
- [Adversarial Robustness with Semi-Infinite Constrained Learning](https://mlsanity.com/paper/2110.15767/) (2021)
- [The Many Faces of Adversarial Risk](https://mlsanity.com/paper/2201.08956/) (2022)
- [Exploring the Relationship between Architecture and Adversarially Robust Generalization](https://mlsanity.com/paper/2209.14105/) (2022)
- [Mixed Nash Equilibria in the Adversarial Examples Game](https://mlsanity.com/paper/2102.06905/) (2021)
- [Federated Adversarial Learning: A Framework with Convergence Analysis](https://mlsanity.com/paper/2208.03635/) (2022)
- [Outlier-Robust Wasserstein DRO](https://mlsanity.com/paper/2311.05573/) (2023)
- [Toward Learning Robust and Invariant Representations with Alignment Regularization and Data Augmentation](https://mlsanity.com/paper/2206.01909/) (2022)
- [Distilling Out-of-Distribution Robustness from Vision-Language Foundation Models](https://mlsanity.com/paper/2311.01441/) (2023)
- [Nash Equilibria, Regularization and Computation in Optimal Transport-Based Distributionally Robust Optimization](https://mlsanity.com/paper/2303.03900/) (2023)
- [Understanding Noise-Augmented Training for Randomized Smoothing](https://mlsanity.com/paper/2305.04746/) (2023)
- [Towards Understanding the Mechanism of Contrastive Learning via Similarity Structure: A Theoretical Analysis](https://mlsanity.com/paper/2304.00395/) (2023)
- [On adversarial robustness and the use of Wasserstein ascent-descent dynamics to enforce it](https://mlsanity.com/paper/2301.03662/) (2023)
- [Exploring Adversarial Robustness of Deep State Space Models](https://mlsanity.com/paper/2406.05532/) (2024)
- [AdAUC: End-to-end Adversarial AUC Optimization Against Long-tail Problems](https://mlsanity.com/paper/2206.12169/) (2022)
- [Generating Less Certain Adversarial Examples Improves Robust Generalization](https://mlsanity.com/paper/2310.04539/) (2023)
- [Wasserstein Distributionally Robust Nonparametric Regression](https://mlsanity.com/paper/2505.07967/) (2025)
- [Attack Transferability Characterization for Adversarially Robust Multi-label Classification](https://mlsanity.com/paper/2106.15360/) (2021)
- [AdvCat: Domain-Agnostic Robustness Assessment for Cybersecurity-Critical Applications with Categorical Inputs](https://mlsanity.com/paper/2212.13989/) (2022)
- [Non-Asymptotic Bounds for Adversarial Excess Risk under Misspecified Models](https://mlsanity.com/paper/2309.00771/) (2023)
- [Minimax rates of convergence for nonparametric regression under adversarial attacks](https://mlsanity.com/paper/2410.09402/) (2024)
- [Finding Dynamics Preserving Adversarial Winning Tickets](https://mlsanity.com/paper/2202.06488/) (2022)
- [Provable Robust Saliency-based Explanations](https://mlsanity.com/paper/2212.14106/) (2022)
- [On Achieving Optimal Adversarial Test Error](https://mlsanity.com/paper/2306.07544/) (2023)
- [Tropical Decision Boundaries for Neural Networks Are Robust Against Adversarial Attacks](https://mlsanity.com/paper/2402.00576/) (2024)
- [Robust Ranking Explanations](https://mlsanity.com/paper/2307.04024/) (2023)
- [Robust optimization for adversarial learning with finite sample complexity guarantees](https://mlsanity.com/paper/2403.15207/) (2024)
- [Adversarial generalization of unfolding (model-based) networks](https://mlsanity.com/paper/2509.15370/) (2025)

## Abstract (arXiv)

Here we propose a general theoretical method for analyzing the risk bound in the presence of adversaries. Specifically, we try to fit the adversarial learning problem into the minimax framework. We first show that the original adversarial learning problem can be reduced to a minimax statistical learning problem by introducing a transport map between distributions. Then, we prove a new risk bound for this minimax problem in terms of covering numbers under a weak version of Lipschitz condition. Our method can be applied to multi-class classification problems and commonly used loss functions such as the hinge and ramp losses. As some illustrative examples, we derive the adversarial risk bounds for SVMs, deep neural networks, and PCA, and our bounds have two data-dependent terms, which can be optimized for achieving adversarial robustness.