Some adversarial attacks change only a handful of pixels, but they may set those pixels to any value. These are called $l_0$ attacks, after the count of altered pixels. Defending against them is expensive. The adversarial training recipe that works best, retraining on attacked images, needs about 20 attack steps per training image. The cheaper one-step version tends to collapse: the model abruptly loses all robustness, a failure known as catastrophic overfitting. In the $l_0$ case this happens because a single gradient step picks the wrong pixels to attack (Understanding and Improving Fast Adversarial Training against $l_0$ Bounded Perturbations). We propose a different route. An $l_0$-attacked image has exactly the structure that compressed sensing calls "manifold plus sparse deviation": a natural image $G(z)$ produced by a generative model, plus a sparse vector $\nu$ of corrupted entries (Modeling Sparse Deviations for Compressed Sensing using Generative Models). If a fast network can estimate where $\nu$ is nonzero, the attacked pixels can be erased and filled in from the generator. All other pixels are passed through untouched. That turns a hard adversarial problem into a missing-data problem that a lightly trained classifier can handle.
The sparsity-prior literature supplies the key design choice, and its known failures shape it. Pure sparsity priors cannot model natural images well, and pure generative priors hit a "ceiling": they cannot reproduce details outside the generator's range (Compressed Sensing using Generative Models). So we put each prior where it fits. Sparsity models the perturbation. The generative model is used only to inpaint the few flagged pixels. Because unflagged pixels are never replaced, the ceiling error is confined to the masked region instead of spreading over the whole image. The method runs as a single forward pass, so it avoids the inference cost of iterative purification.
Core Claim
A single-pass front end has two parts: an encoder that outputs a latent code and a per-pixel corruption mask, and a generator that inpaints the masked pixels. We train it on clean data with cheap synthetic sparse corruptions plus one-step attacks through the whole pipeline. Paired with a classifier trained by one-step $l_0$ adversarial training, it should match or beat the best fast $l_0$ defense under fully adaptive Sparse-AutoAttack. We expect it to stay stable over long training and to cost no more total GPU time. A matched variant that replaces the generator with a learned linear dictionary should do clearly worse. That comparison is a direct test of the claim that the linear sparsity prior is the bottleneck for this kind of defense.
Research Program
The pipeline takes an input $x$ and an encoder $E$ produces $(z, m) = E(x)$, where $m \in [0,1]^N$ estimates which of the $N$ pixel entries are corrupted. The classifier sees
$$\tilde{x} = (1 - m) \odot x + m \odot G(z),$$
where $G$ is the generator and $\odot$ is elementwise product. This is an amortized, one-pass version of the Sparse-Gen objective. Sparse-Gen jointly optimizes $z$ and an $\ell_1$-sparse $\nu$ with gradient descent and random restarts. We replace that non-convex per-image search with a learned prediction and use $\nu$ only through its support, meaning which pixels are corrupted, not their values.
Training has three stages. First, $G$ and $E$ are trained on clean images. Then $E$'s mask head learns to find randomly placed corrupted pixels with random values, which requires no attack loop. Finally, the whole pipeline and the classifier are fine-tuned with one-step sparse attacks computed end to end through the mask and the inpainting. We use the mask-and-magnitude parameterization of sPGD (Towards Efficient Training and Evaluation of Robust Models against $l_0$ Bounded Adversarial Perturbations) and the smoothing from Fast-LS-$l_0$.
The analysis asks why this might prevent the location-driven collapse. Our hypothesis is that the mask head flattens the "craggy" loss surface over pixel locations: wherever the attacker places pixels, the mask covers them. To test this, we track mask recall on adversarial pixels and the classifier's loss sensitivity over training. If collapse is still coming, these should show it beforehand.
Baselines
The do-nothing reference is a standard classifier with no defense. sPGD drives its robust accuracy to nearly 0% on CIFAR-10. The strongest existing method is Fast-LS-$l_0$, which combines soft labels, TRADES and N-FGSM noise. It reports 63.0% robust accuracy under Sparse-AutoAttack on CIFAR-10, matching 20-step training in under one sixth of the time (Understanding and Improving Fast Adversarial Training against $l_0$ Bounded Perturbations). The file does not state its pixel budget, so we will rerun it at our budgets. We also include the multi-step reference sTRADES, reported at 61.7% robust accuracy at a 20-pixel budget on CIFAR-10 (Towards Efficient Training and Evaluation of Robust Models against $l_0$ Bounded Adversarial Perturbations).
All methods use the same classifier backbone and data, and the same hyperparameter-tuning budget. Our total wall-clock time, including generator pretraining, counts against our method. Beating the strongest baseline means higher Sparse-AutoAttack accuracy at equal or lower total GPU hours, at several pixel budgets.
Three ablations isolate the key ingredient. In the first, a DDL-style learned overcomplete dictionary with sparse coding (Denoising Dictionary Learning Against Adversarial Perturbations) replaces $G$, with everything else unchanged; this tests the sparsity-prior limitation directly. In the second, we drop the mask and pass the full projection $G(E(x))$, roughly the autoencoder projection of Enhancing the Adversarial Robustness via Manifold Projection; this should expose the ceiling effect as lost clean accuracy. In the third, the classifier gets no adversarial training at all, which shows how much of the robustness comes from the front end alone.
Why not just…?
Why not just use a median filter? For isolated outlier pixels, median filtering is the classical fix, and it is a genuine threat to this proposal. Its weakness should be that an adaptive attacker can cluster pixels so that the local median itself is corrupted. We include median and wavelet filtering as front ends under the same adaptive attack. If either matches our pipeline, the generative component is not needed, and we will report that.
Why not just run Fast-LS-$l_0$ alone? It already reaches 63.0%. Its authors say they cannot guarantee their smoothing functions are optimal for the non-convex $l_0$ space. It also leaves the location-selection failure in place rather than removing it. The head-to-head comparison and a 1000-epoch stability run settle this. A training-dynamics view shows that one-step defenses can look stable early and still collapse later (A Training-Dynamics View of Catastrophic Overfitting: Understanding and Prevention).
Why not just use diffusion purification? DiffPure adds noise and then denoises with a diffusion model, the class of models that generate images by gradually removing noise (Diffusion Models for Adversarial Purification). It needs many network evaluations per image. Iterative purification based on a variational autoencoder (VAE), a generative model that compresses images into a latent code, runs about 102x slower than a forward pass (Adversarial Purification with the Manifold Hypothesis). Diffusion noise is also spread across all pixels, while large-magnitude sparse pixels may survive it. We run DiffPure under the same sparse attacks and report both accuracy and latency.
Proposed Experiments
We evaluate on CIFAR-10, CIFAR-100, GTSRB (where physical stickers motivate sparse attacks) and ImageNet-100. On ImageNet-100, the reported 360-to-44-hour reduction gives a cost reference. Metrics are clean accuracy, Sparse-AutoAttack accuracy across pixel budgets, total training GPU hours, inference latency, and mask precision and recall on adversarial pixels.
The decisive check is a fully adaptive attack. Sparse-AutoAttack and sPGD differentiate through the relaxed mask, use straight-through gradients for any hard threshold, and run an expectation over any randomness. If robustness falls well below Fast-LS-$l_0$ under this attack, the claim fails. A second check is the dictionary ablation: if the linear dictionary performs as well as the generator, the sparsity-prior argument fails. A third is long training: if the method collapses where Fast-LS-$l_0$ does not, the location-smoothing hypothesis is wrong.
References
- Understanding and Improving Fast Adversarial Training against $l_0$ Bounded Perturbations
- Modeling Sparse Deviations for Compressed Sensing using Generative Models
- Compressed Sensing using Generative Models
- Towards Efficient Training and Evaluation of Robust Models against $l_0$ Bounded Adversarial Perturbations
- Denoising Dictionary Learning Against Adversarial Perturbations
- Enhancing the Adversarial Robustness via Manifold Projection
- A Training-Dynamics View of Catastrophic Overfitting: Understanding and Prevention
- Diffusion Models for Adversarial Purification
- Adversarial Purification with the Manifold Hypothesis