Does the Soft-Boundary Advantage Survive Outside the L∞ Ball?

An adversarial evasion attack searches for a small change to an input that makes a classifier give the wrong answer. "Small" is always measured in some norm. The L∞ norm caps the largest change to any single pixel, the L2 norm caps total energy, and the L1 norm caps the summed absolute change, which favors sparse edits. The standard attack takes a gradient step and then snaps the input back inside the allowed ball. Constrained Gradient Descent (CGD) showed that for L∞, replacing this snap-back with a soft penalty that tightens gradually finds more adversarial examples, and finds them faster, than Auto-PGD. Its authors state plainly that L2, L1 and L0 were never tested. The theory that would predict behavior under other norms, such as the accelerated rates for steepest descent and adversarial training under general norms in Faster margin maximization rates, comes with no experiments at all. So we have a strong empirical result in one geometry and untested theory in the others.

This proposal extends the soft-boundary attack to general Lp balls and asks a sharper question than "does it still win." We want to know why it wins. Our hypothesis is that the gain comes from how badly the projection step destroys gradient information, and that this damage depends on the norm. If that is right, we can predict ahead of time, for each norm and budget, whether a soft boundary is worth using, and we can check the prediction on CIFAR-10 and ImageNet.

Core Claim

The CGD paper attributes the failure of clipping to an artificial "wall." The wall makes the logits of competing classes oscillate as the attack alternately favors one wrong class and then another. The shape of that wall depends on the norm.

Projecting onto an L∞ box clips coordinates one at a time. Once a pixel hits the bound, its gradient component is effectively zeroed, and it stays zeroed. Projecting onto an L1 ball soft-thresholds: it shrinks every coordinate and sets many to exactly zero. That is also a coordinate-killing, non-smooth operation. Projecting onto an L2 ball only rescales the perturbation along its own direction, which keeps the direction and keeps every coordinate alive.

We therefore predict that the soft-boundary advantage will be large for L∞ and L1 and small or absent for L2. We further predict that across norms and budgets, the size of the advantage tracks one measurable quantity: the fraction of the proposed gradient step that the projection removes. The claim is falsifiable in two ways. A large CGD gain under L2 would refute it. So would a gain that fails to correlate with removed gradient mass.

Research Program

We first build a norm-general soft-boundary attack. At iteration $t$, the attack minimizes

$$\ell_{\text{MD}}(x+\delta) + \lambda \max\big(0, \|\delta\|_p - \tau_t\big),$$

where $\delta$ is the perturbation, $\ell_{\text{MD}}$ is CGD's minimal-difference multi-class loss, $\lambda$ weights the boundary penalty, and $\tau_t$ is a threshold that starts above the budget $\varepsilon$ and decays to $\varepsilon$ on CGD's schedule. The update direction is steepest descent with respect to the chosen norm. That means the sign of the gradient for L∞, the normalized gradient for L2, and a step on the few largest-magnitude coordinates for L1. This is the norm-matched geometry analyzed by Wang et al.. We reuse that paper as a method source; we do not test its rates, which assume convex, bilinear settings that deep networks violate.

A single final projection guarantees that every reported adversarial example lies inside the ε-ball. This matters because a soft penalty alone can leave perturbations slightly over budget, and any over-budget example would make the comparison unfair.

Second, we instrument every attack run with a "removed-mass" statistic: the norm of (proposed step minus projected step), divided by the norm of the proposed step, averaged over iterations. We record it alongside the logit-oscillation count CGD used to diagnose the wall. This turns the qualitative story in the CGD paper into a quantity we can correlate with attack gains.

Third, we sweep norms (p equal to 1, 1.5, 2, 4 and ∞) and several budgets per norm. The intermediate values of p let us test whether the effect varies smoothly with geometry rather than just switching between three special cases.

Baselines

The naive reference point is plain projected gradient descent with a fixed step size and projection onto the correct Lp ball. It shows how much any refinement buys.

The strongest existing competitor is Auto-PGD run with the projection matched to each norm. CGD beat it at L∞, finding 0.9–4.2% more adversarial examples on CIFAR-10 and 8.6–13.6% more on ImageNet, while running 11.4–18.8% faster, according to Constrained Gradient Descent. Auto-PGD is therefore the method that must be beaten outside L∞. For L2 and L1 on these defenses, we found no reported result on Lacuna for either CGD or Auto-PGD, so our runs establish those numbers.

The original L∞ CGD, reproduced, serves as an anchor. We expect to recover gains in the published range; failing to do so would indicate a problem with our implementation.

The key ablation keeps our norm-matched steepest-descent direction and the minimal-difference loss, but replaces the soft decaying boundary with hard projection at every step. This isolates the boundary treatment from the loss and the step geometry.

All methods get the same defended models, test images, iteration budget, number of random restarts, and an equal hyperparameter-tuning budget on a held-out split of 1,000 images. Wall-clock time is measured on the same hardware. Beating Auto-PGD means a higher success rate at an equal iteration count, with the gap exceeding the spread over restart seeds, reported for each norm separately.

Why not just…?

Why not just run Auto-PGD with the right projection and stop? Auto-PGD may well be enough under L2, and our hypothesis predicts exactly that. It is a real competitor, not a strawman. The experiment settles the question for each norm: if Auto-PGD matches the soft-boundary attack everywhere, including L1, the claim fails. That negative result would be worth reporting, because it would say CGD's advantage is specific to box constraints.

Why not just give PGD more iterations or restarts? Extra compute can mask an optimization pathology without curing it. We therefore report success-versus-iteration curves out to several times the default budget. If hard projection catches up given enough iterations, the soft boundary is only a speedup rather than a stronger attack. The oscillation counts will show whether the pathology persists regardless of budget.

Why not just use a fixed Lagrangian penalty, with no decaying threshold? A fixed penalty weight is simpler, but it trades off budget violation against attack strength in a way that must be retuned for every model. The CGD paper introduced dynamic thresholding precisely because its authors judged the plain penalty inadequate. We include this variant as a second ablation, under the same tuning budget, to test whether the schedule matters outside L∞.

Proposed Experiments

We run on CIFAR-10 (all 10,000 test images) and ImageNet (the 50,000 validation images, subsampled only if the compute budget forces it). The defenses are CGD's nine defended models where available, plus defenses trained against L2 and L1 attacks, so each norm is tested against models built to resist it. Metrics are success rate at the budget, robust accuracy, iterations to first success, wall-clock time, removed mass, and logit oscillations.

The first decisive check is the per-norm ordering of gains. Our hypothesis predicts that the advantage over Auto-PGD is large at p = 1 and p = ∞ and near zero at p = 2.

The second is a rank correlation, pooled across all norms, budgets and models, between removed mass under hard projection and the soft-boundary gain. A strong positive correlation supports the mechanism. A flat relationship means the L∞ result arises from something other than gradient destruction, such as the minimal-difference loss alone. The hard-projection ablation would then reveal this by matching CGD.