# Scaling up the randomized gradient-free adversarial attack reveals overestimation of robustness using established attacks

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Mar 2019.

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

- [Advances in adversarial attacks and defenses in computer vision: A survey](https://mlsanity.com/paper/2108.00401/) (2021)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Explainable Deep Learning in Healthcare: A Methodological Survey from an Attribution View](https://mlsanity.com/paper/2112.02625/) (2021)
- [Traversing the Local Polytopes of ReLU Neural Networks: A Unified Approach for Network Verification](https://mlsanity.com/paper/2111.08922/) (2021)
- [Adversarial Training Should Be Cast as a Non-Zero-Sum Game](https://mlsanity.com/paper/2306.11035/) (2023)
- [Understanding and Achieving Efficient Robustness with Adversarial Supervised Contrastive Learning](https://mlsanity.com/paper/2101.10027/) (2021)
- [NatADiff: Adversarial Boundary Guidance for Natural Adversarial Diffusion](https://mlsanity.com/paper/2505.20934/) (2025)
- [Over-parameterization and Adversarial Robustness in Neural Networks: An Overview and Empirical Analysis](https://mlsanity.com/paper/2406.10090/) (2024)
- [A General Framework for Property-Driven Machine Learning](https://mlsanity.com/paper/2505.00466/) (2025)
- [Tight Robustness Certificates and Wasserstein Distributional Attacks for Deep Neural Networks](https://mlsanity.com/paper/2510.10000/) (2025)
- [Quantitative Linear Logic for Neuro-Symbolic Learning and Verification](https://mlsanity.com/paper/2605.13845/) (2026)

## Abstract (arXiv)

Modern neural networks are highly non-robust against adversarial manipulation. A significant amount of work has been invested in techniques to compute lower bounds on robustness through formal guarantees and to build provably robust models. However, it is still difficult to get guarantees for larger networks or robustness against larger perturbations. Thus attack strategies are needed to provide tight upper bounds on the actual robustness. We significantly improve the randomized gradient-free attack for ReLU networks [9], in particular by scaling it up to large networks. We show that our attack achieves similar or significantly smaller robust accuracy than state-of-the-art attacks like PGD or the one of Carlini and Wagner, thus revealing an overestimation of the robustness by these state-of-the-art methods. Our attack is not based on a gradient descent scheme and in this sense gradient-free, which makes it less sensitive to the choice of hyperparameters as no careful selection of the stepsize is required.