# Adversarial Risk and Robustness: General Definitions and Implications for the Uniform Distribution

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

## Key facts

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

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

- [Robust Learning Meets Generative Models: Can Proxy Distributions Improve Adversarial Robustness?](https://mlsanity.com/paper/2104.09425/) (2021)
- [Planting Undetectable Backdoors in Machine Learning Models](https://mlsanity.com/paper/2204.06974/) (2022)
- [Virtual Homogeneity Learning: Defending against Data Heterogeneity in Federated Learning](https://mlsanity.com/paper/2206.02465/) (2022)
- [The Many Faces of Adversarial Risk](https://mlsanity.com/paper/2201.08956/) (2022)
- [On the Existence of the Adversarial Bayes Classifier (Extended Version)](https://mlsanity.com/paper/2112.01694/) (2021)
- [Overparameterized Linear Regression under Adversarial Attacks](https://mlsanity.com/paper/2204.06274/) (2022)
- [Learning and Certification under Instance-targeted Poisoning](https://mlsanity.com/paper/2105.08709/) (2021)
- [The Need for Ethical, Responsible, and Trustworthy Artificial Intelligence for Environmental Sciences](https://mlsanity.com/paper/2112.08453/) (2021)
- [Robust Optimal Classification Trees Against Adversarial Examples](https://mlsanity.com/paper/2109.03857/) (2021)
- [It Is All About Data: A Survey on the Effects of Data on Adversarial Robustness](https://mlsanity.com/paper/2303.09767/) (2023)
- [Adversarially Robust PAC Learnability of Real-Valued Functions](https://mlsanity.com/paper/2206.12977/) (2022)
- [Domain Invariant Adversarial Learning](https://mlsanity.com/paper/2104.00322/) (2021)
- [SoK: Pitfalls in Evaluating Black-Box Attacks](https://mlsanity.com/paper/2310.17534/) (2023)
- [On the Computability of Robust PAC Learning](https://mlsanity.com/paper/2406.10161/) (2024)
- [Improved Estimation of Concentration Under ℓp-Norm Distance Metrics Using Half Spaces](https://mlsanity.com/paper/2103.12913/) (2021)
- [Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks](https://mlsanity.com/paper/2205.06127/) (2022)
- [On the Role of Randomization in Adversarially Robust Classification](https://mlsanity.com/paper/2302.07221/) (2023)
- [Trustworthy Actionable Perturbations](https://mlsanity.com/paper/2405.11195/) (2024)
- [Enhancing Robustness of Neural Networks through Fourier Stabilization](https://mlsanity.com/paper/2106.04435/) (2021)
- [Deadwooding: Robust Global Pruning for Deep Neural Networks](https://mlsanity.com/paper/2202.05226/) (2022)
- [On the Hardness of Robustness Transfer: A Perspective from Rademacher Complexity over Symmetric Difference Hypothesis Space](https://mlsanity.com/paper/2302.12351/) (2023)
- [Attacking Bayes: On the Adversarial Robustness of Bayesian Neural Networks](https://mlsanity.com/paper/2404.19640/) (2024)
- [Lower Bounds on Cross-Entropy Loss in the Presence of Test-time Adversaries](https://mlsanity.com/paper/2104.08382/) (2021)
- [Image classifiers can not be made robust to small perturbations](https://mlsanity.com/paper/2112.04033/) (2021)
- [When are Local Queries Useful for Robust Learning?](https://mlsanity.com/paper/2210.06089/) (2022)
- [Selecting Models based on the Risk of Damage Caused by Adversarial Attacks](https://mlsanity.com/paper/2301.12151/) (2023)
- [Faster Repeated Evasion Attacks in Tree Ensembles](https://mlsanity.com/paper/2402.08586/) (2024)
- [On the (Un-)Avoidability of Adversarial Examples](https://mlsanity.com/paper/2106.13326/) (2021)
- [Adversarial Example Detection in Deployed Tree Ensembles](https://mlsanity.com/paper/2206.13083/) (2022)
- [Certifying Global Robustness for Deep Neural Networks](https://mlsanity.com/paper/2405.20556/) (2024)

## Abstract (arXiv)

We study adversarial perturbations when the instances are uniformly distributed over 0,1n. We study both "inherent" bounds that apply to any problem and any classifier for such a problem as well as bounds that apply to specific problems and specific hypothesis classes. As the current literature contains multiple definitions of adversarial risk and robustness, we start by giving a taxonomy for these definitions based on their goals, we identify one of them as the one guaranteeing misclassification by pushing the instances to the error region. We then study some classic algorithms for learning monotone conjunctions and compare their adversarial risk and robustness under different definitions by attacking the hypotheses using instances drawn from the uniform distribution. We observe that sometimes these definitions lead to significantly different bounds. Thus, this study advocates for the use of the error-region definition, even though other definitions, in other contexts, may coincide with the error-region definition. Using the error-region definition of adversarial perturbations, we then study inherent bounds on risk and robustness of any classifier for any classification problem whose instances are uniformly distributed over 0,1n. Using the isoperimetric inequality for the Boolean hypercube, we show that for initial error 0.01, there always exists an adversarial perturbation that changes O(√n) bits of the instances to increase the risk to 0.5, making classifier's decisions meaningless. Furthermore, by also using the central limit theorem we show that when n→ ∞, at most c · √n bits of perturbations, for a universal constant c< 1.17, suffice for increasing the risk to 0.5, and the same c · √n  bits of perturbations on average suffice to increase the risk to 1, hence bounding the robustness by c · √n.