# On the Minimal Adversarial Perturbation for Deep Neural Networks with Provable Estimation Error

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 57 references that are in the map.
- First posted on arXiv 4 Jan 2022.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [You Only Look Once: Unified, Real-Time Object Detection](https://mlsanity.com/paper/1506.02640/) (2015)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [DeepFool: a simple and accurate method to fool deep neural networks](https://mlsanity.com/paper/1511.04599/) (2015)
- [Ensemble Adversarial Training: Attacks and Defenses](https://mlsanity.com/paper/1705.07204/) (2017)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Distillation as a Defense to Adversarial Perturbations against Deep Neural Networks](https://mlsanity.com/paper/1511.04508/) (2015)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Adversarial Examples Are Not Easily Detected: Bypassing Ten Detection Methods](https://mlsanity.com/paper/1705.07263/) (2017)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [Minimally distorted Adversarial Examples with a Fast Adaptive Boundary Attack](https://mlsanity.com/paper/1907.02044/) (2019)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [On Detecting Adversarial Perturbations](https://mlsanity.com/paper/1702.04267/) (2017)
- [Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Robustness Verification](https://mlsanity.com/paper/2103.06624/) (2021)
- [A Dual Approach to Scalable Verification of Deep Networks](https://mlsanity.com/paper/1803.06567/) (2018)
- [Decoupling Direction and Norm for Efficient Gradient-Based L2 Adversarial Attacks and Defenses](https://mlsanity.com/paper/1811.09600/) (2018)
- [Orthogonalizing Convolutional Layers with the Cayley Transform](https://mlsanity.com/paper/2104.07167/) (2021)
- [Preventing Gradient Attenuation in Lipschitz Constrained Convolutional Networks](https://mlsanity.com/paper/1911.00937/) (2019)
- [Analysis of classifiers' robustness to adversarial perturbations](https://mlsanity.com/paper/1502.02590/) (2015)
- [CNN-Cert: An Efficient Framework for Certifying Robustness of Convolutional Neural Networks](https://mlsanity.com/paper/1811.12395/) (2018)
- [Fast Minimum-norm Adversarial Attacks through Adaptive Norm Constraints](https://mlsanity.com/paper/2102.12827/) (2021)
- [Augmented Lagrangian Adversarial Attacks](https://mlsanity.com/paper/2011.11857/) (2020)

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

- [Defending From Physically-Realizable Adversarial Attacks Through Internal Over-Activation Analysis](https://mlsanity.com/paper/2203.07341/) (2022)
- [Robust-by-Design Classification via Unitary-Gradient Neural Networks](https://mlsanity.com/paper/2209.04293/) (2022)
- [Transcending Adversarial Perturbations: Manifold-Aided Adversarial Examples with Legitimate Semantics](https://mlsanity.com/paper/2402.03095/) (2024)
- [Benchmarking the Spatial Robustness of DNNs via Natural and Adversarial Localized Corruptions](https://mlsanity.com/paper/2504.01632/) (2025)
- [Leveraging Knowledge Graphs and LLMs for Structured Generation of Misinformation](https://mlsanity.com/paper/2505.24479/) (2025)
- [Exploiting Edge Features for Transferable Adversarial Attacks in Distributed Machine Learning](https://mlsanity.com/paper/2507.07259/) (2025)

## Abstract (arXiv)

Although Deep Neural Networks (DNNs) have shown incredible performance in perceptive and control tasks, several trustworthy issues are still open. One of the most discussed topics is the existence of adversarial perturbations, which has opened an interesting research line on provable techniques capable of quantifying the robustness of a given input. In this regard, the Euclidean distance of the input from the classification boundary denotes a well-proved robustness assessment as the minimal affordable adversarial perturbation. Unfortunately, computing such a distance is highly complex due the non-convex nature of NNs. Despite several methods have been proposed to address this issue, to the best of our knowledge, no provable results have been presented to estimate and bound the error committed. This paper addresses this issue by proposing two lightweight strategies to find the minimal adversarial perturbation. Differently from the state-of-the-art, the proposed approach allows formulating an error estimation theory of the approximate distance with respect to the theoretical one. Finally, a substantial set of experiments is reported to evaluate the performance of the algorithms and support the theoretical findings. The obtained results show that the proposed strategies approximate the theoretical distance for samples close to the classification boundary, leading to provable robustness guarantees against any adversarial attacks.