# Sparse and Imperceptible Adversarial Attack via a Homotopy Algorithm

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 34 references that are in the map.
- First posted on arXiv 10 Jun 2021.

## Builds on (most cited first, 19 of 19)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [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)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Learning Deep Features for Discriminative Localization](https://mlsanity.com/paper/1512.04150/) (2015)
- [Deep Neural Networks are Easily Fooled: High Confidence Predictions for Unrecognizable Images](https://mlsanity.com/paper/1412.1897/) (2014)
- [One pixel attack for fooling deep neural networks](https://mlsanity.com/paper/1710.08864/) (2017)
- [Generating Adversarial Examples with Adversarial Networks](https://mlsanity.com/paper/1801.02610/) (2018)
- [Attacks Which Do Not Kill Training Make Adversarial Learning Stronger](https://mlsanity.com/paper/2002.11242/) (2020)
- [Geometry-aware Instance-reweighted Adversarial Training](https://mlsanity.com/paper/2010.01736/) (2020)
- [Towards the first adversarially robust neural network model on MNIST](https://mlsanity.com/paper/1805.09190/) (2018)
- [Sparse and Imperceivable Adversarial Attacks](https://mlsanity.com/paper/1909.05040/) (2019)
- [SparseFool: a few pixels make a big difference](https://mlsanity.com/paper/1811.02248/) (2018)
- [Structured Adversarial Attack: Towards General Implementation and Better Interpretability](https://mlsanity.com/paper/1808.01664/) (2018)
- [LG-GAN: Label Guided Adversarial Network for Flexible Targeted Attack of Point Cloud-based Deep Networks](https://mlsanity.com/paper/2011.00566/) (2020)
- [GreedyFool: Distortion-Aware Sparse Adversarial Attack](https://mlsanity.com/paper/2010.13773/) (2020)
- [A Survey on Nonconvex Regularization Based Sparse and Low-Rank Recovery in Signal Processing, Statistics, and Machine Learning](https://mlsanity.com/paper/1808.05403/) (2018)
- [Learning Diverse-Structured Networks for Adversarial Robustness](https://mlsanity.com/paper/2102.01886/) (2021)
- [Structured Sparse Regression via Greedy Hard-Thresholding](https://mlsanity.com/paper/1602.06042/) (2016)

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

- [Learning to Break Deep Perceptual Hashing: The Use Case NeuralHash](https://mlsanity.com/paper/2111.06628/) (2021)
- [Backdoor Attack with Sparse and Invisible Trigger](https://mlsanity.com/paper/2306.06209/) (2023)
- [IG2: Integrated Gradient on Iterative Gradient Path for Feature Attribution](https://mlsanity.com/paper/2406.10852/) (2024)
- [BruSLeAttack: A Query-Efficient Score-Based Black-Box Sparse Adversarial Attack](https://mlsanity.com/paper/2404.05311/) (2024)
- [GSE: Group-wise Sparse and Explainable Adversarial Attacks](https://mlsanity.com/paper/2311.17434/) (2023)
- [Towards Robust Vision Transformer via Masked Adaptive Ensemble](https://mlsanity.com/paper/2407.15385/) (2024)
- [Human Imperceptible Attacks and Applications to Improve Fairness](https://mlsanity.com/paper/2111.15603/) (2021)
- [Interpreting Vulnerabilities of Multi-Instance Learning to Adversarial Perturbations](https://mlsanity.com/paper/2211.17071/) (2022)
- [SAIF: Sparse Adversarial and Imperceptible Attack Framework](https://mlsanity.com/paper/2212.07495/) (2022)
- [Web Artifact Attacks Disrupt Vision Language Models](https://mlsanity.com/paper/2503.13652/) (2025)
- [Sparse and Transferable Universal Singular Vectors Attack](https://mlsanity.com/paper/2401.14031/) (2024)
- [S-CFE: Simple Counterfactual Explanations](https://mlsanity.com/paper/2410.15723/) (2024)
- [Towards Interpretable Adversarial Examples via Sparse Adversarial Attack](https://mlsanity.com/paper/2506.17250/) (2025)
- [A Versatile Framework for Designing Group-Sparse Adversarial Attacks](https://mlsanity.com/paper/2510.16637/) (2025)
- [Sparse patches adversarial attacks via extrapolating point-wise information](https://mlsanity.com/paper/2411.16162/) (2024)

## Abstract (arXiv)

Sparse adversarial attacks can fool deep neural networks (DNNs) by only perturbing a few pixels (regularized by l_0 norm). Recent efforts combine it with another l_infty imperceptible on the perturbation magnitudes. The resultant sparse and imperceptible attacks are practically relevant, and indicate an even higher vulnerability of DNNs that we usually imagined. However, such attacks are more challenging to generate due to the optimization difficulty by coupling the l_0 regularizer and box constraints with a non-convex objective. In this paper, we address this challenge by proposing a homotopy algorithm, to jointly tackle the sparsity and the perturbation bound in one unified framework. Each iteration, the main step of our algorithm is to optimize an l_0-regularized adversarial loss, by leveraging the nonmonotone Accelerated Proximal Gradient Method (nmAPG) for nonconvex programming; it is followed by an l_0 change control step, and an optional post-attack step designed to escape bad local minima. We also extend the algorithm to handling the structural sparsity regularizer. We extensively examine the effectiveness of our proposed homotopy attack for both targeted and non-targeted attack scenarios, on CIFAR-10 and ImageNet datasets. Compared to state-of-the-art methods, our homotopy attack leads to significantly fewer perturbations, e.g., reducing 42.91% on CIFAR-10 and 75.03% on ImageNet (average case, targeted attack), at similar maximal perturbation magnitudes, when still achieving 100% attack success rates. Our codes are available at: https://github.com/VITA-Group/SparseADV_Homotopy.