WorksComputer Science
Propose with the Gradient, Accept with the Loss: One Hedged Attack for Pixel-Sparse Robustness
Abstract
A pixel-sparse adversary may change a few pixels of an image to any value. Robustness to such attacks is currently measured with an ensemble, sparse-AutoAttack (sAA), because its members fail in different places: sparse projected gradient descent (sPGD) trusts a first-order model that a full pixel change breaks, and sparse random search (Sparse-RS) ignores the gradient even where it is informative. We show that both attacks are local searches, each a proposal distribution plus an acceptance rule, and ask what such a search can learn from the gradient. A Taylor bound says what to measure, and measurements at the states the search visits give five rules. The sign of the gradient is its most reliable use at a single pixel and sets a new pixel's value. Its ranking of candidate pixels should be followed loosely, and its ranking of the pixels to remove, which is often more reliable, can be followed more closely. A pixel should not be proposed twice before a move is accepted, and acceptance should be decided by the loss alone. These rules define Gradient-guided Random Search (GRS), which runs once and costs one forward and one backward pass per step. On 13 CIFAR-10 configurations and 5 ImageNet models, GRS matches or beats the best single member of sAA and is within one point of sAA itself or stronger on 17 of 18 settings, and it is significantly stronger than sAA on 8. It uses 3 instead of up to 7 forward-pass units, and on CIFAR-10 it runs 3.7 to 5.0 times faster than the members of sAA run in full.
Introduction
A pixel-sparse adversary may change at most pixels of an image, and each changed pixel may take any value in the image domain. This threat model is hard to evaluate: the constraint set is non-convex, a single admissible pixel change is not small, and the first-order tools of and attacks [21, 31] have no direct counterpart. For these reasons the current evaluation standard, sparse-AutoAttack (sAA) [52], is an ensemble. It runs two white-box attacks, sparse projected gradient descent (sPGD) with a projected and with an unprojected gradient, and one black-box attack,
sparse random search (Sparse-RS) [14], and it counts a point as broken if any member breaks it. At 10k iterations the ensemble costs up to 7 units of 10k forward passes per point: 3 for each sPGD run (a backward pass counts as two) and 1 for Sparse-RS, with later numbers of the cascade run only on points still unbroken. Its members are not redundant: on the models we study, each of the three is the best one somewhere, and each is far behind the ensemble somewhere (Figure 1 and Table 1).
Figure 1. Robust accuracy minus that of sAA on the 18 main settings (symmetric log scale; below 0 is stronger than sAA; grey band ±1 point). Filled: GRS differs significantly from sAA (exact McNemar, ). GRS costs 3 units per point, sAA up to 7.
| model | proj | unproj | Sparse-RS | sAA | GRS | sAA GRS | -zero | PGD | GreedyPixel | ||
| Std. PRN-18 | 5 | 8.7 | 18.6 | 6.8 | 5.7 | 6.0 | 14/20 | 5.0 | 26.7 | 23.5 | 61.1 |
| Std. PRN-18 | 10 | 0.2 | 4.0 | 0.1 | 0.1 | 0.1 | 1/1 | 0.1 | 3.2 | 6.2 | 36.8 |
| Gowal PRN-18 | 20 | 9.4 | 15.7 | 7.2 | 6.3 | 4.6* | 49/15 | 3.8 | 23.3 | 23.7 | 49.3 |
| Sehwag RN-18 | 20 | 10.0 | 14.6 | 9.2 | 7.6 | 5.0* | 67/16 | 4.2 | 23.4 | 21.4 | 50.5 |
| Cui WRN-28 | 20 | 9.1 | 15.2 | 6.5 | 5.6 | 3.4* | 27/5 | 2.9 | 20.1 | 27.6 | 48.6 |
| Wang WRN-28 | 20 | 8.7 | 14.2 | 5.8 | 5.2 | 3.1* | 26/5 | 2.6 | 18.8 | 25.7 | 48.2 |
| XCiT-S12 | 20 | 9.7 | 14.2 | 16.3 | 8.9 | 8.5 | 15/11 | 7.4 | 28.3 | 23.4 | 60.9 |
| Rade PRN-18 | 20 | 9.3 | 8.5 | 13.3 | 7.5 | 7.9 | 21/29 | 6.4 | 31.3 | 20.6 | 58.0 |
| Sehwag RN-18 | 20 | 6.3 | 5.8 | 10.9 | 4.7 | 6.4† | 15/50 | 3.9 | 26.9 | 15.1 | 58.4 |
| Wang WRN-28 | 20 | 10.7 | 12.4 | 13.5 | 9.0 | 7.5* | 28/13 | 6.2 | 37.1 | 29.5 | 69.4 |
| Rebuffi WRN-28 | 20 | 15.4 | 19.5 | 18.2 | 13.7 | 11.8* | 26/7 | 11.1 | 35.4 | 24.4 | 63.1 |
| sAT PRN-18 | 20 | 75.4 | 75.0 | 35.2 | 35.2 | 34.8 | 66/58 | 31.9 | 78.4 | 75.7 | 73.5 |
| sTRADES PRN-18 | 20 | 84.0 | 80.5 | 61.4 | 61.3 | 58.0* | 100/33 | 56.3 | 85.8 | 85.1 | 83.3 |
Table 1. CIFAR-10 at 10k iterations, robust accuracy (%) on 2000 evaluation points (1000 for WRN-28 and XCiT). Lower is a stronger attack; bold: strongest single attack in the row (unions such as sAA excluded); : points broken only by GRS/ only by sAA; */†: GRS significantly stronger/weaker than sAA (exact McNemar, ). sAA is the union of its three members.
This paper asks why the ensemble is needed and whether a single attack can replace it. Our starting point is that every pixel- attack, white-box or black-box, is a local search over the pair (which pixels, which values). A proposal distribution suggests a candidate from the current state, and an acceptance rule decides whether to move to it. Seen this way, the two kinds of member of sAA misuse the gradient in opposite ways. sPGD accepts every iterate, so it has to trust first-order magnitudes, and it collapses where they mislead. On the models trained with sparse adversarial training (sAT) and its TRADES [50] variant (sTRADES) [52] it leaves 75– 84% of the points unbroken, against 35–61% for Sparse-RS (Table 1). Sparse-RS chooses pixels blindly and fills them with random values, so it is slow where the gradient is informative. On an ImageNet XCiT it leaves 40.3% unbroken at , against 30.5% for sPGD (Table 2). Neither attack sets a newly added pixel directly to the corner of its box given by the sign of the gradient, which is the most reliable first-order quantity at a single pixel. sAA hedges between the two behaviours by running all three members.
| model | proj | unproj | Sparse-RS | sAA | GRS | 3 seeds | sAA GRS | -zero | PGD | GreedyPixel | ||
| Std. RN-50 | 20 | 23.9 | 42.7 | 20.0 | 17.6 | 17.2 | 26/22 | – | 15.0 | – | – | – |
| Std. RN-50 | 50 | 3.7 | 21.9 | 5.3 | 2.6 | 3.3 | 6/13 | 3.6±0.5 | 2.0 | 5.7 | 48.2 | 42.2 |
| Std. RN-50 | 100 | 0.3 | 6.6 | 1.7 | 0.3 | 0.9† | 0/6 | – | 0.3 | – | – | – |
| Salman RN-18 | 20 | 14.4 | 19.7 | 12.7 | 11.4 | 10.5 | 19/10 | – | 9.5 | – | – | – |
| Salman RN-18 | 50 | 5.3 | 7.6 | 6.5 | 4.2 | 4.0 | 10/8 | 4.2±0.2 | 3.2 | 5.5 | 26.7 | 19.0 |
| Salman RN-18 | 100 | 1.3 | 2.2 | 4.1 | 1.3 | 1.3 | 9/9 | – | 0.4 | – | – | – |
| Salman RN-50 | 20 | 27.2 | 33.1 | 19.8 | 19.1 | 20.3 | 22/34 | – | 16.9 | – | – | – |
| Salman RN-50 | 50 | 10.5 | 16.2 | 9.5 | 7.6 | 7.7 | 15/16 | 7.9±0.5 | 6.1 | 8.1 | 36.6 | 34.1 |
| Salman RN-50 | 100 | 4.5 | 6.3 | 5.7 | 3.7 | 3.0 | 14/7 | – | 2.3 | – | – | – |
| Wong RN-50 | 20 | 21.4 | 25.7 | 17.9 | 16.9 | 16.9 | 21/21 | – | 14.8 | – | – | – |
| Wong RN-50 | 50 | 10.6 | 12.7 | 9.3 | 7.6 | 6.7 | 15/6 | 7.0±0.3 | 6.1 | 6.9 | 29.7 | 31.5 |
| Wong RN-50 | 100 | 4.8 | 6.1 | 6.8 | 4.6 | 3.4* | 17/5 | – | 2.9 | – | – | – |
| XCiT-S12 | 20 | 48.0 | 50.5 | 51.2 | 46.1 | 44.6* | 32/17 | – | 42.9 | – | – | – |
| XCiT-S12 | 50 | 30.5 | 33.3 | 40.3 | 28.4 | 26.4* | 50/30 | 26.5±0.2 | 23.4 | 37.2 | 55.1 | 58.6 |
| XCiT-S12 | 100 | 15.9 | 15.8 | 34.0 | 14.7 | 14.5 | 30/28 | – | 11.7 | – | – | – |
Table 2. ImageNet validation images 1000–1999 at 10k iterations, robust accuracy (%). Lower is a stronger attack; bold, and */† as in Table 1. 3 seeds: mean ± sd of GRS. -zero, PGD and GreedyPixel at only.
We make the hedge explicit and put it inside one run. A Taylor bound (Lemma 1) shows that the first-order prediction for a full pixel change carries an error of the size of the local curvature. Whether the gradient can be trusted is therefore a ratio of predicted gain to curvature, which can be measured rather than assumed. We measure it at the states a search actually visits, on 12 CIFAR-10 and 5 ImageNet models, and the measurements give five design rules (§ 4). Accept a move only if the true loss improves. Choose pixels to add from a tempered gradient ranking, whose top is unreliable on robust ImageNet models, and pixels to drop from a colder ranking, because a pixel’s current contribution is often far more reliable than a candidate’s predicted gain. Set a new pixel’s value from the gradient’s sign, and spend no further steps on values. Do not propose a pixel twice before the next move is accepted. The attack that follows these rules, Gradient-guided Random Search (GRS, § 5), is a random search like Sparse-RS whose moves are drawn from the gradient and accepted by the loss. It costs one forward and one backward pass per step, the same as sPGD.
Our contributions are:
a local-search view of pixel- attacks, with elementary bounds that separate the two ways of failing and bound the cost of a tempered proposal (Sec. 3);
a measurement of what the gradient can be trusted for at the states a search visits, which turns into five design rules and one attack (§ 4 and § 5);
an evaluation on 13 CIFAR-10 configurations (12 models) and 5 ImageNet models at three budgets, against the sAA members, -zero [9], PGD [10] and GreedyPixel [46] (§ 6): on 17 of 18 main settings GRS matches or beats the best single member and is within one point of sAA or stronger, and it is significantly stronger than sAA on 8, at 3 instead of up to 7 units;
an ablation of the design choices, in which greedy acceptance has by far the largest effect, and diagnostics that explain most of the differences between models (§ 7).
Related work
Sparse adversarial attacks. Adversarial examples [43] with few changed pixels were first found by greedy saliency methods (the Jacobian-based saliency map attack, JSMA [35], GreedyFool [18]), by evolutionary search (the one-pixel attack [42]) or by relaxations of the constraint: Carlini and Wagner [6] prune an solution, SparseFool [34] linearizes the decision boundary, PGD [10] projects onto the ball, -zero [9] minimizes a smooth surrogate of the norm, boundary attacks [4, 36] minimize it directly, and EAD [8] and -APGD [12] attack the relaxation. The relaxations take a dense gradient step and then make it sparse, so they trust the first-order model for exactly the full pixel changes where Lemma 1 says it can fail. SparseFool and -zero also minimize the size of the perturbation rather than succeed within a fixed budget, and at the budgets used for evaluation -zero and PGD leave 1.8 to 5.8 times as many points unbroken as sAA on the RobustBench CIFAR-10 models (Table 1).
Sparse-PGD [51, 52] is the strongest white-box attack for a fixed pixel budget. It relaxes the set of changed pixels to continuous mask logits, alternates projected gradient steps on the mask and on the pixel values, and redraws the mask when progress stalls. It accepts every iterate, so it has no defence against a misleading gradient: on sAT and sTRADES, which are trained against sPGD itself, it leaves far more points unbroken than Sparse-RS (Table 1). Neither of its projected and unprojected variants is the stronger one on every model, which is why sAA runs both. Among black-box attacks, Sparse-RS [14] extends the Square Attack [2] to a random search over pixel sets with greedy acceptance and a shrinking number of swapped pixels, and also covers patches [5, 26]; Pixle [37] instead rearranges pixels. Greedy acceptance makes Sparse-RS robust to gradient masking, but it chooses pixels uniformly and gives each a random value, so it needs many queries where the gradient would point the way, and on ImageNet at it is behind the projected sPGD on three of five models, by 9.8 points on XCiT (Table 2). GreedyPixel [46] sets pixels one at a time in an order fixed by gradient saliency at the clean input and never revises that order. sAA [52] combines two sPGD variants with Sparse-RS in the spirit of AutoAttack [11]; sAT and sTRADES apply adversarial training [31] with sPGD. The ensemble covers each member’s failures at up to 7 units per point, but no member combines the gradient’s guidance with greedy acceptance.
Local search and tempered proposals. Greedy acceptance of random swaps is hill climbing [1, 24]. Proposing moves in proportion to the exponential of a score uses the Boltzmann weights of Metropolis sampling and simulated annealing [27, 33], and forbidding recently tried moves is tabu search [20]. Drawing distinct pixels in proportion to is done with the Gumbel-top- trick [28].
Gradient masking and ensembles. Adding a gradient-free attack to an ensemble is the standard remedy for gradient masking [3, 7, 11, 44, 45]. Certified defences [25, 30] bound robustness from below, attacks from above. For attacks our analysis locates the failure in the acceptance rule rather than in the gradient itself. With greedy acceptance on the true loss the search never moves to a worse state, and a misleading gradient lowers its acceptance rate by a bounded factor (Proposition 3), so one run can be both fast and safe.
Pixel- attacks as local search
Setting. An input has channels, pixels and label . Write for the logits and for the margin, so the attack succeeds exactly when . A state consists of a support , the set of changed pixels, and a value for each . The value lives in the box , so that the perturbed pixel stays in , and the adversarial input is on . Every attack in this paper repeats two steps: build a candidate from the current state, and apply an acceptance rule to decide whether becomes the new state. sPGD relaxes to continuous mask logits and takes projected gradient steps on mask and values, so its candidate is a deterministic function of the gradient, and it accepts every iterate. Sparse-RS swaps uniformly chosen pixels, gives each new pixel a uniformly random corner of its box, and keeps the candidate only if its loss decreases (the margin, or the cross-entropy on robust models).
Let be the gradient at the current input and its restriction to pixel . Two first-order scores will matter. The add score is the predicted decrease of the margin from adding a pixel at its best value. That value is the best-response corner : in channel it equals if and otherwise. The drop score is the predicted contribution of a pixel , the first-order decrease of the margin it currently provides.
Single-pixel moves are not small. A pixel changes by in every channel, so , and the first-order model has an error of the size of the local curvature rather than a vanishing one. Let be a Lipschitz constant of the gradient of with respect to pixel ’s coordinates on . Step-by-step proofs of all statements in this section and the next are in Sec. D.
Lemma 1 (first-order reliability). Adding pixel at value , with the rest of the state fixed, changes the margin by with .
Two consequences follow. Lemma 1 certifies that adding pixel at lowers the margin if . It certifies the predicted order of two pixels if their add scores differ by more than . So whether the gradient can be trusted depends on the ratio , and gradient masking is the extreme case . We do not estimate ; § 4 measures reliability directly, as the correlation between first-order predictions and true margin changes.
A local model. To compare search strategies we use a simple additive model. A set of helpful pixels exists, the margin is when values are at their best, and the attack succeeds once , with and . The search starts from a support with helpful pixels. Real margins are close to additive at the states we probe: the Pearson correlation between the sum of an add and a drop and the corresponding swap is 0.95–1.00 (Table 9).
Table 9. Reliability before step 1000 (CIFAR-10 test points 1000–1999, ImageNet validation images 0–499; 64 unbroken points per state): Spearman of the add score with the true add gain (loc), Pearson of the first-order with the true margin change of an add (lin), Spearman of the drop score with the true drop loss (drop), fraction of adds whose best-response corner is the best of the corners (br; chance 0.125), Pearson of the sum of an add and a drop with the swap (add.), and acceptance ratios of three proposals: tempered over Sparse-RS before steps 100 and 1000, uniform locations with best-response fill over Sparse-RS (fill), and tempered over uniform locations with the same fill (temp.).
| model | loc | lin | drop | br | add. | ratio100 | ratio1000 | fill | temp. |
| Std. PRN-18 | 0.00 | -0.09 | 0.14 | 0.23 | 0.95 | 1.8 | 1.0 | 1.21 | 0.79 |
| Gowal PRN-18 | 0.28 | 0.19 | 0.17 | 0.31 | 0.99 | 4.5 | 2.2 | 1.48 | 1.50 |
| Sehwag RN-18 | 0.26 | 0.19 | 0.25 | 0.33 | 0.99 | 4.7 | 2.3 | 2.14 | 1.09 |
| Cui WRN-28 | 0.22 | 0.17 | 0.07 | 0.29 | 0.99 | 2.9 | 2.5 | 1.82 | 1.36 |
| Wang WRN-28 | 0.24 | 0.19 | 0.07 | 0.29 | 0.99 | 4.0 | 2.4 | 1.60 | 1.53 |
| XCiT-S12 | 0.24 | 0.18 | 0.37 | 0.26 | 0.98 | 3.8 | 2.1 | 1.29 | 1.66 |
| Rade PRN-18 | 0.27 | 0.28 | 0.44 | 0.35 | 0.99 | 10.2 | 4.6 | 2.97 | 1.54 |
| Sehwag RN-18 | 0.21 | 0.14 | 0.40 | 0.36 | 0.99 | 10.8 | 4.1 | 2.61 | 1.57 |
| Wang WRN-28 | 0.22 | 0.19 | 0.39 | 0.31 | 0.99 | 8.4 | 3.9 | 2.50 | 1.55 |
| Rebuffi WRN-28 | 0.11 | 0.10 | 0.36 | 0.30 | 0.99 | 5.4 | 2.1 | 1.31 | 1.58 |
| sAT PRN-18 | -0.24 | -0.29 | -0.15 | 0.13 | 1.00 | 0.6 | 0.9 | 0.90 | 1.04 |
| sTRADES PRN-18 | -0.17 | -0.13 | -0.14 | 0.11 | 1.00 | 0.6 | 0.8 | 0.84 | 1.00 |
| Std. RN-50 | -0.17 | -0.21 | 0.43 | 0.21 | 0.99 | 1.6 | 1.3 | 1.20 | 1.10 |
| Salman RN-18 | 0.07 | -0.05 | 0.64 | 0.18 | 1.00 | 1.8 | 0.5 | 1.10 | 0.45 |
| Salman RN-50 | 0.06 | 0.01 | 0.65 | 0.15 | 1.00 | 2.2 | 0.8 | 1.06 | 0.80 |
| Wong RN-50 | 0.12 | -0.01 | 0.64 | 0.19 | 1.00 | 1.2 | 0.6 | 1.22 | 0.48 |
| XCiT-S12 | 0.12 | 0.04 | 0.63 | 0.23 | 1.00 | 4.3 | 1.6 | 1.16 | 1.37 |
Table 9.
Proposition 1 (accepting every step). (a) If for every pixel, Lemma 1 certifies a decrease of margin for no single-pixel add, so an attack that accepts every iterate gets no descent certificate from it. (b) If the gradients carry no information about , so that the sequence of supports is independent of a uniformly random , each evaluated support succeeds with probability at most .
Proposition 2 (greedy acceptance of blind proposals). Under the additive model, greedy single-swap search with uniform proposals succeeds after an expected steps, whatever the gradient says.
For , , , and , Proposition 1(b) bounds a blind attack that accepts every step to one success in about steps, whereas Proposition 2 gives greedy uniform search about 300. Greedy acceptance is what keeps a search alive when the gradient carries no information.
What the gradient can be trusted for
The bounds of Sec. 3 turn reliability into something we can measure. We measure it at the states a search actually visits. We run a probe search on held-out points and stop it before steps 100 and 1000. The probe proposes adds and drops at and sets each added pixel at its best-response corner, as GRS does, but uses neither Rule 3 nor Rule 5 below. The points are CIFAR-10 test points 1000–1999, on which no setting was tuned and nothing is evaluated, and ImageNet validation images 0–499, which are also used for the selection in Sec. A but never for evaluation. At each stopped state we evaluate, with forward passes, the true change of the margin for every single add at its best-response corner, for every single drop, and for samples of value changes and swaps, and we compare them with the first-order predictions. Figure 2 and Table 9 and Table 10 (appendix) summarize the results for 12 CIFAR-10 and 5 ImageNet models. Each finding below becomes a design rule.
Figure 2. Reliability at the states the search visits. Left: acceptance rate of a tempered gradient proposal (add and drop at , best-response fill) divided by that of Sparse-RS’s proposal (uniform swap, random corner), before steps 100 and 1000; log scale. Above 1 the gradient helps; on sAT, sTRADES and the robust ImageNet CNNs it does not before step 1000. Right: before step 1000, Spearman correlation of the add score with the true gain of an add (x-axis) and of the drop score with the true loss of a drop (y-axis), one marker per model. Colour shows which sAA member is stronger on the evaluation points: blue where the better sPGD run beats Sparse-RS, orange where Sparse-RS wins. (IN): ImageNet.
Table 10. Proposal concentration and drop quality before step 1000 (same states as Table 9). Kurtosis of the standardized add score; percentage of the add proposal’s mass on the top 1% of outside pixels; effective number of outside pixels (perplexity) of the add proposal; single-swap acceptance predicted from additivity with both sides at / / uniform; mean margin increase caused by the dropped pixel at / / uniform (lower is better); predicted single-swap acceptance with a uniform add and a uniform / drop. –: not computed.
| model | kurtosis | top 1% (%) | pixels at | acceptance / 4 / unif. | drop cost / 4 / unif. | uniform add: unif. / cold drop |
| Std. PRN-18 | 20 | 4.1 | 625 | 0.004 / 0.002 / 0.002 | 2.307 / 2.356 / 2.380 | – |
| Gowal PRN-18 | 28 | 4.6 | 521 | 0.086 / 0.018 / 0.012 | 0.263 / 0.263 / 0.267 | 0.012 / 0.015 |
| Sehwag RN-18 | 24 | 4.7 | 492 | 0.082 / 0.021 / 0.014 | 0.190 / 0.203 / 0.210 | – |
| Cui WRN-28 | 31 | 4.8 | 503 | 0.066 / 0.023 / 0.018 | 0.235 / 0.231 / 0.232 | – |
| Wang WRN-28 | 31 | 4.5 | 533 | 0.089 / 0.020 / 0.015 | 0.237 / 0.240 / 0.243 | – |
| XCiT-S12 | 19 | 3.8 | 671 | 0.077 / 0.018 / 0.012 | 0.141 / 0.154 / 0.161 | – |
| Rade PRN-18 | 11 | 3.3 | 737 | 0.125 / 0.019 / 0.011 | 0.238 / 0.253 / 0.263 | – |
| Sehwag RN-18 | 13 | 3.4 | 718 | 0.100 / 0.015 / 0.009 | 0.323 / 0.349 / 0.362 | – |
| Wang WRN-28 | 11 | 3.2 | 739 | 0.098 / 0.022 / 0.014 | 0.231 / 0.249 / 0.258 | – |
| Rebuffi WRN-28 | 14 | 3.4 | 725 | 0.101 / 0.024 / 0.017 | 0.195 / 0.204 / 0.212 | – |
| sAT PRN-18 | 22 | 4.2 | 608 | 0.011 / 0.027 / 0.028 | 0.438 / 0.337 / 0.322 | – |
| sTRADES PRN-18 | 14 | 3.5 | 715 | 0.029 / 0.027 / 0.026 | 0.336 / 0.237 / 0.221 | 0.026 / 0.013 |
| Std. RN-50 | 55 | 5.5 | 1018 | 0.031 / 0.051 / 0.052 | 0.111 / 0.124 / 0.133 | 0.052 / 0.071 |
| Salman RN-18 | 410 | 24.0 | 2 | 0.235 / 0.147 / 0.156 | 0.032 / 0.044 / 0.051 | 0.156 / 0.198 |
| Salman RN-50 | 303 | 18.5 | 2 | – / 0.150 / 0.126 | 0.037 / 0.050 / 0.058 | 0.126 / 0.185 |
| Wong RN-50 | 250 | 21.5 | 2 | 0.206 / 0.131 / 0.137 | 0.038 / 0.052 / 0.061 | 0.137 / 0.198 |
| XCiT-S12 | 128 | 8.7 | 20 | 0.259 / 0.112 / 0.091 | 0.021 / 0.028 / 0.033 | 0.091 / 0.138 |
Table 10.
Rule 1: accept with the loss, never with the gradient. First-order magnitudes are poor predictors everywhere. Before step 1000, the Pearson correlation between the predicted and the true margin change of an add is 0.10–0.28 on the nine RobustBench CIFAR-10 models and −0.21 to 0.04 on ImageNet. On the standard CIFAR-10 model and on sAT and sTRADES it is negative (−0.09, −0.29 and −0.13), and on sAT and sTRADES even the rankings are reversed (Figure 2, right, bottom left), so there the gradient is misleading rather than merely uninformative. Acceptance must therefore be decided by the true loss, which costs one forward pass that the attack pays anyway, and never by a first-order prediction. With greedy acceptance the search never moves to a worse state; this is the guarantee sPGD gives up. Accepting every candidate instead leaves 9.1–29.2 points more unbroken (§ 7).
Rule 2: choose pixels to add from a tempered ranking. Let standardize a score over the allowed pixels, so that it has mean 0 and variance 1 under the uniform distribution , and let the proposal be with temperature .
Proposition 3 (tempered proposals). Let be the set of moves that improve the current state and with . Under greedy acceptance, the acceptance probability satisfies
and
The proposition is stated for single moves drawn from one side; for a swap whose add and drop are drawn independently, is the product of the two sides’ ratios and the exponents add. Since , the normalizer satisfies (it equals for Gaussian scores) and vanishes only as . If the score is informative on average over the improving moves, that is , the tempered proposal is accepted more often than a uniform one. If the score is uninformative or misleading (), acceptance stays at least times that of uniform proposals, a factor that tends to 1 as grows. A tempered proposal therefore sits between Sparse-RS () and sPGD’s fragile top-1 choice (, which never hits when the top move is not improving), and it pays a bounded price when the gradient is wrong.
How closely may the add ranking be followed? On ImageNet its top is unreliable. On Salman RN-18 and Wong RN-50, the top 0.1% of outside pixels by has a mean predicted margin change of −0.07 to −0.08 but a mean true change of +0.02 to +0.05 (Table 11): the pixels with the largest gradients are also the most non-linear. The standard-
Outside pixels binned by the rank of their add score , at the states of Table 9 before step 1000: mean predicted and true margin change of adding the pixel at its best-response corner (negative is good).
| model | bin | predicted | true |
| Salman RN-18 | top 0.1% | −0.074 | +0.020 |
| Salman RN-18 | 0.1–1% | −0.029 | +0.012 |
| Salman RN-18 | 1–10% | −0.007 | +0.016 |
| Salman RN-18 | rest | −0.000 | +0.003 |
| Wong RN-50 | top 0.1% | −0.079 | +0.053 |
| Wong RN-50 | rest | −0.001 | +0.006 |
| Gowal PRN-18 | top 0.1% | −0.461 | −0.072 |
| Gowal PRN-18 | rest | −0.019 | +0.005 |
| Sehwag RN-18 | top 0.1% | −0.564 | −0.110 |
| Sehwag RN-18 | rest | −0.049 | −0.013 |
Table 11. Outside pixels binned by the rank of their add score , at the states of Table 9 before step 1000: mean predicted and true margin change of adding the pixel at its best-response corner (negative is good).
ized scores are heavy-tailed, with a kurtosis of 250–410 on the robust ImageNet CNNs against 11–31 on CIFAR-10 (Table 10). As a result, at already 18–24% of the proposal mass on those models falls on the top 1% of pixels (3–5% on CIFAR-10), and at the proposal effectively chooses among one to three pixels out of 50 126. Per step, a colder proposal is still predicted to be accepted more often on most models (Table 10). Over a full run, however, the coldest add is the worst setting we tried on ImageNet: with Rules 3 and 5 in place, an add at leaves 13.0% and 11.0% of the selection images unbroken, against 7.4% and 7.8% at (Table 4). A cold add keeps proposing the few top-ranked pixels, so per-step acceptance is not the right criterion, and the add side stays warm: . Even at , a proposal that follows the add ranking on both sides is accepted less often than Sparse-RS’s on all three robust ImageNet CNNs before step 1000 (Figure 2, left), which is why the drop side needs a different rule.
| variant | Salman | Wong | vs GRS | vs Sparse-RS |
| GRS (value steps 25%) | 10.6 | 9.6 | – | 32/24 |
| official Sparse-RS | 11.0 | 10.8 | 24/32 | – |
| Sparse-RS proposal inside our code | 10.6 | 9.2 | 23/21 | 26/16 |
| no value steps | 10.6 | 9.4 | 19/18 | 27/18 |
| best-response fill, uniform add/drop | 9.8 | 9.4 | 28/23 | 27/14 |
| cold drop (), add at | 10.0 | 9.2 | 21/16 | 31/18 |
| cold drop, uniform add | 8.8 | 8.2 | 30/14* | 33/9* |
| drop at , uniform add | 8.6 | 8.4 | 27/11* | 34/10* |
| tabu, cold drop, uniform add | 8.8 | 8.0 | 27/10* | 30/5* |
| tabu, cold drop, add at (GRS) | 7.4 | 7.8 | 28/3* | 38/5* |
| tabu, cold drop, add at | 13.0 | 11.0 | 20/39† | 21/32 |
Table 4. Selection on ImageNet validation images 0–499 (not used for evaluation), , 10k steps, seed 0, robust accuracy (%) on Salman RN-50 and Wong RN-50. Lower is a stronger attack; bold: best value in the column. b/c: points broken only by the variant / only by the reference (GRS or the official Sparse-RS), pooled over both models; */†: variant significantly stronger/weaker than the reference (exact McNemar, ). All variants except the first two take no value steps.
Rule 3: choose pixels to drop from a cold ranking. The drop score behaves differently (Figure 2, right). Before step 1000 its Spearman correlation with the true loss from removing a pixel is 0.63–0.65 on the four robust ImageNet models and 0.43 on the standard one, against only 0.06–0.12 for the add score at the same states: the ImageNet markers sit high on the vertical axis and close to zero on the horizontal one. On CIFAR-10 it separates the models by colour: it is at least 0.36 on the five models where sPGD beats Sparse-RS and at most 0.25 on the seven where Sparse-RS wins, with a rank correlation of 0.94 with the Sparse-RS–sPGD gap (, ). A reliable score over only pixels is wasted at . On the four robust ImageNet models the pixel dropped at costs 35–37% less margin than a uniformly chosen one, while at the saving is only 13–14%, and with a uniform add a cold drop raises the predicted single-swap acceptance by 27–52% (Table 10). Each side’s temperature should match the reliability of its score: .
Rule 4: set values by the sign at add time, and spend no steps on values.
Proposition 4 (best-response fill). Let for adding pixel at have a -Lipschitz gradient, let be the best-response corner and a uniformly random corner. Then .
Choosing a value needs only the signs of the gradient at one pixel, whereas choosing a location needs to order pixels, each with an error of the size in Lemma 1. The value is the more reliable use of the gradient, and the data agree (Table 9). Before step 1000 the best-response corner is the true best of the corners in 26–36% of cases on the RobustBench CIFAR-10 models and 15–23% on ImageNet (chance is 12.5%). With uniform locations, adds at that corner are accepted 1.3–3.0 times as often as adds at a random corner on the RobustBench CIFAR-10 models and 1.06–1.22 times on ImageNet, but not on sAT and sTRADES (0.84–0.90). Once a pixel’s value is set when it is added, further sign steps on all values only compete with swaps for the budget: a variant that spends a quarter of its steps on them is no stronger (Table 4), so every step goes to a swap.
Rule 5: do not propose the same pixel twice while the gradient is unchanged. The gradient, and with it both rankings, stays fixed until a move is accepted. With heavy-tailed scores a tempered proposal keeps returning to the same few pixels between acceptances, and a cold drop over pixels does the same. A tabu list [20] prevents this: every pixel proposed as an add or a drop is excluded until the next acceptance, and the whole list is cleared when either side has fewer than free pixels. This restores coverage without warming the proposal. With the tabu list the tempered add is 1.4 and 0.2 points stronger than a uniform add on the two selection models; without it, it is 1.2 and 1.0 points weaker (Table 4). On the evaluation points, removing the tabu list costs 1.1–2.0 points on the robust ImageNet CNNs and 4.0 on sTRADES (§ 7).
The attack: GRS
Algorithm 1 and Figure 3 put the five rules together. The state is a support of pixels and a value for each of them. One step costs one forward and one backward pass through the model, the same as sPGD, and the gradient at the accepted state drives the next proposal. The gradient is that of sPGD’s adaptive loss [11, 52], written as an objective to decrease: when and (cross-entropy) otherwise, so near the decision boundary and the scores of Sec. 3 apply with . Scores are standardized over the allowed pixels, and distinct pixels are drawn in proportion to with the Gumbel-top- trick [28]. The number follows Sparse-RS’s schedule: a fraction of that starts at and halves at fixed iteration marks, rescaled to the iteration budget. A point stops as soon as it is misclassified, and every success is re-checked with a fresh forward pass.

Figure 3. Top: robust accuracy (%, lower is stronger) where the gradient misleads (sTRADES, ) and where it helps (ImageNet XCiT-S12, ); dashes: sAA; red: over 5 points above it; sPGD: better of its two runs. Bottom: one step of GRS; pixels are drawn , the standardized score.
Cost. Following [52], we count cost in forward-pass units and count a backward pass as two. sPGD and GRS therefore cost 3 units per iteration and Sparse-RS 1 unit per query, so at 10k iterations sAA costs up to 7 units of 10k forward passes per point and GRS 3.
How the settings were chosen. All settings were chosen on points disjoint from the evaluation points (Sec. A): ,
Algorithm 1 GRS: Gradient-guided Random Search
Input: image , label , budget , iterations
Settings: ,
random pixels, random in the box; tabu
margin and at
for while :
for
for
if either side has pixels outside tabu: tabu
pixels , ▷ Rule 2
pixels , ▷ Rule 3
tabu ▷ Rule 5
; for ▷ Rule 4
margin and at
if : ; tabu ▷ Rule 1
the tabu list and swap-only steps on ImageNet validation images 0–499, the rest on CIFAR-10 test points 0–999. In the ablation, the version with , no tabu list and a quarter of its steps spent on sign steps on the values is called GRS.
Experiments
Models. On CIFAR-10 [29] we use a standard PreAct ResNet-18 (PRN-18) [23], the sAT and sTRADES PRN-18 of [52] (trained at ), and nine RobustBench [13] models. Five of these are -robust: Gowal et al. [22] PRN-18, Sehwag et al. [41] ResNet-18 (RN-18), Cui et al. [15] and Wang et al. [47] WideResNet-28-10 [49] (WRN-28), and Debenedetti et al. [16] XCiT-S12 [19]. Four are -robust: Rade and Moosavi-Dezfooli [38] PRN-18, Sehwag et al. RN-18, and Wang et al. and Rebuffi et al. [39] WRN-28. On ImageNet [17] (224 × 224) we use the standard ResNet-50 (RN-50) and four -robust RobustBench models: Salman et al. [40] RN-18 and RN-50, Wong et al. [48] RN-50, and Debenedetti et al. XCiT-S12.
Evaluation setup. The evaluation points are CIFAR-10 test images 2000–3999 (1000 of them on the WRN-28 and XCiT models, 2000 otherwise) and ImageNet validation images 1000–1999. No setting was tuned on them. The budgets are and 10 on the standard CIFAR-10 model, on the robust CIFAR-10 models, and , 50 and 100 on ImageNet, always with 10k iterations or queries per attack. sPGD (projected and unprojected), Sparse-RS, -zero and PGD run from their official code with the settings of their own evaluation scripts, except for PGD’s number of restarts (Sec. B). sAA is the union of the two sPGD runs and Sparse-RS, which on every point gives the same result as the official cascade. All tables report robust accuracy, the percentage of all evaluation points that are correctly classified and not broken, so lower means a stronger attack. Comparisons are paired, with the exact two-sided McNemar test [32] on the points that only one of two attacks breaks, and two attacks are level when . GRS uses seed 0 in the tables and three seeds where stated.
Main result. We call the 13 CIFAR-10 configurations and the five ImageNet models at the 18 main settings. On 17 of them GRS is at least as strong as the best single member of sAA and within one point of sAA itself or stronger (Tabs. 1 and 2). It is significantly stronger than sAA on 8 settings, seven CIFAR-10 configurations and the ImageNet XCiT, and level with it on 9. Pooled over CIFAR-10, GRS breaks 455 points that sAA misses and sAA breaks 263 that GRS misses (); pooled over the four robust ImageNet models the counts are 90 and 60 (). GRS is never weaker than Sparse-RS on a main setting, and on ImageNet it is 1.8–13.9 points stronger. Figure 4 (appendix) shows ImageNet images that GRS breaks and neither sPGD proj nor Sparse-RS does.
Figure 4. Adversarial examples of sPGD proj, Sparse-RS and GRS on the Wong et al. RN-50 at ( of pixels). Top row: clean image and true class. Other rows: the pixels each attack changes, each drawn as a block of its new colour on a faded copy of the clean image, and the predicted class (red: not broken). GRS breaks all six images, while sPGD proj and Sparse-RS break none of them (Sparse-RS returns the clean image when it fails).
Sparsity. At and 100 (Tab. 2) GRS stays within 1.2 points of sAA or stronger, and it is significantly stronger on XCiT at and on Wong RN-50 at . A CIFAR-10 sweep over to 30 with GRS (Tab. 13) has no significant loss to sAA and three significant wins.
Other attacks. At the same budget the minimum-norm attack -zero leaves 19–37% of the points unbroken on the RobustBench CIFAR-10 models, PGD 15–30% and GreedyPixel 48–69%. On ImageNet at PGD (27–55%) and GreedyPixel (19–59%) stay far behind; GRS is level with -zero on Salman and Wong RN-50 and 1.5–10.8 points stronger on the other three ().
Seeds. On ImageNet at the standard deviation of GRS over three seeds is 0.2–0.5 points (Table 2 and Table 5). On CIFAR-10 we have three seeds of GRS on every configuration, with a standard deviation of 0.03–0.55; GRS has one seed there.
| model | GRS seeds | mean | GRS seeds | mean |
| Std. RN-50 | 3.3 / 3.3 / 4.1 | 4.2 / 4.0 / 3.4 | ||
| Salman RN-18 | 4.0 / 4.4 / 4.2 | 5.6 / 5.3 / 5.3 | ||
| Salman RN-50 | 7.7 / 7.6 / 8.5 | 10.0 / 10.5 / 10.7 | ||
| Wong RN-50 | 6.7 / 6.9 / 7.3 | 9.5 / 8.2 / 9.0 | ||
| XCiT-S12 | 26.4 / 26.3 / 26.7 | 27.9 / 27.5 / 28.6 |
Table 5. ImageNet, , robust accuracy (%) of GRS and GRS for seeds 0 / 1 / 2, and mean sample sd. Lower is a stronger attack.
Equal compute. GRS’s 3 units are a per-step cost, so Table 12 (appendix) gives the search sAA’s budget on CIFAR-10. These runs use GRS, which is level with GRS on CIFAR-10 (§ 7). Run for 23k steps (6.9 units), it is significantly stronger than sAA on 8 of 13 configurations and level on 4. Two seeds at 10k cost 6 units and beat the single 23k run on 9 of 13 configurations.
Table 12. CIFAR-10 at equal compute, robust accuracy (%), with the cost in units of 10k forward passes per point in brackets. Lower is a stronger attack; no entry is bold because the costs differ. The two-seed and 23k-step runs use GRS, which is level with GRS on CIFAR-10. b/c: points broken only by the 23k run / only by sAA, with the exact McNemar ; : 23k run significantly stronger/weaker than sAA ().
| model | sAA [7] | GRS [3] | GRS [3] | GRS 2 seeds [6] | GRS 23k [6.9] | projunproj [6] | b/c | ||
| Std. PRN-18 | 5 | 5.7 | 6.0 | 5.8 | 4.6 | 5.2 | 8.6 | 22/12 | 0.12 |
| Std. PRN-18 | 10 | 0.1 | 0.1 | 0.1 | 0.1 | 0.1 | 0.2 | 1/0 | 1.00 |
| Gowal PRN-18 | 20 | 6.3 | 4.6 | 4.3 | 3.3 | 3.6* | 9.2 | 61/8 | |
| Sehwag RN-18 | 20 | 7.6 | 5.0 | 5.3 | 4.1 | 4.4* | 9.7 | 75/12 | |
| Cui WRN-28 | 20 | 5.6 | 3.4 | 3.3 | 2.4 | 2.9* | 9.0 | 28/1 | |
| Wang WRN-28 | 20 | 5.2 | 3.1 | 3.2 | 2.8 | 2.5* | 8.7 | 29/2 | |
| XCiT-S12 | 20 | 8.9 | 8.5 | 8.9 | 7.5 | 7.6* | 9.2 | 23/10 | 0.035 |
| Rade PRN-18 | 20 | 7.5 | 7.9 | 8.1 | 6.6 | 7.3 | 7.6 | 33/29 | 0.70 |
| Sehwag RN-18 | 20 | 4.7 | 6.4 | 6.3 | 5.1 | 5.6† | 4.9 | 17/35 | 0.018 |
| Wang WRN-28 | 20 | 9.0 | 7.5 | 8.5 | 6.4 | 7.8 | 9.7 | 28/16 | 0.096 |
| Rebuffi WRN-28 | 20 | 13.7 | 11.8 | 11.9 | 10.6 | 10.7* | 14.8 | 34/4 | |
| sAT PRN-18 | 20 | 35.2 | 34.8 | 34.2 | 32.4 | 32.1* | 73.6 | 91/30 | |
| sTRADES PRN-18 | 20 | 61.3 | 58.0 | 58.0 | 55.8 | 55.3* | 80.3 | 138/17 |
Wall-clock. Table 8 (appendix) times the official code and ours on CIFAR-10 on one NVIDIA L40 at batch size 500. Per 1000 points GRS takes 138–166 s, against 527–699 s for the three members of sAA, each run on all points, a factor of 3.7–5.0. This exceeds the 7/3 unit ratio because the official Sparse-RS alone takes 277–423 s.
Table 8. Seconds per 1000 CIFAR-10 points at 10k iterations, one L40, batch 500 (lower is faster). sAA is two sPGD runs plus Sparse-RS, with the unprojected run assumed to take as long as the projected one; the ratio is sAA’s time over GRS’s.
| model | sPGD proj | Sparse-RS | GRS | sAA | ratio | |
| Sehwag RN-18 | 20 | 138 | 423 | 139 | 699 | 5.0× |
| Gowal PRN-18 | 20 | 172 | 277 | 166 | 622 | 3.7× |
| Std. PRN-18 | 5 | 117 | 292 | 138 | 527 | 3.8× |
Table 8.
Ablation and diagnostics
Components. Table 3 removes one design choice at a time on five CIFAR-10 configurations; Table 6 and Table 7 (appendix) do the same on ImageNet. Greedy acceptance (Rule 1) has by far the largest effect: accepting every candidate, as sPGD does, leaves 11.5–29.2 points more unbroken on CIFAR-10 and 9.1–24.0 on ImageNet at (), consistent with Proposition 1. Removing the tabu list (Rule 5) costs 1.1–2.0 points on the three robust ImageNet CNNs and 4.0 on sTRADES (), and at most 0.4 points elsewhere. The other CIFAR-10 variants start from GRS, which is level with GRS on CIFAR-10: pooled over all 13 configurations each breaks exactly 256 points that the other misses. Replacing the best-response fill with Sparse-RS’s random corner costs 0.9–2.5 points and is significant on all five configurations; this is the largest effect of a single change to GRS, consistent with Proposition 4. Replacing the tempered add and drop with uniform proposals costs 0.5–1.3 points and is significant on three. Removing the value steps, or taking the gradient of the cross-entropy instead of the adaptive loss, changes nothing significant.
| model | GRS full | no tabu | accept all | GRS full | uniform prop. | random corner | no value steps | cross-entropy | no gradient use | official Sparse-RS | |
| Std. PRN-18 | 5 | 6.0 | 6.1 | 17.5† | 5.8 | 6.4 | 6.7† | 6.2 | 6.0 | 7.1† | 6.8† |
| Gowal PRN-18 | 20 | 4.6 | 4.5 | 26.1† | 4.3 | 4.8 | 5.4† | 4.3 | 4.4 | 7.5† | 7.2† |
| Sehwag RN-18 | 20 | 5.0 | 5.4 | 25.6† | 5.3 | 6.1† | 6.5† | 5.2 | 5.5 | 10.1† | 9.2† |
| Sehwag RN-18 | 20 | 6.4 | 6.1 | 24.4† | 6.3 | 7.6† | 8.8† | 6.3 | 6.7 | 12.2† | 10.9† |
| sTRADES PRN-18 | 20 | 58.0 | 62.0† | 87.2† | 58.0 | 59.1† | 60.3† | 58.4 | 58.2 | 61.8† | 61.4† |
Table 3. CIFAR-10 ablation at 10k steps, robust accuracy (%). Lower is a stronger attack; bold: best variant in the row; ∗/†: significantly stronger/weaker than the full method of its group (exact McNemar, ). The GRS variants drop the tabu list or accept every candidate. Each GRS variant changes one choice of GRS (, no tabu, value steps on a quarter of its steps); “no gradient use” is Sparse-RS’s proposal inside our code.
Table 6. ImageNet evaluation images, robust accuracy (%) of GRS and GRS, with Sparse-RS and sAA for reference. Lower is a stronger attack; bold: strongest of GRS, GRS and Sparse-RS; : points broken only by GRS/ only by GRS, with the exact McNemar ; */†: GRS significantly stronger/weaker than GRS ().
| model | GRS | GRS | Sparse-RS | sAA | |||
| Std. RN-50 | 20 | 17.2 | 17.2 | 21/21 | 1.00 | 20.0 | 17.6 |
| Std. RN-50 | 50 | 3.3 | 4.2 | 20/11 | 0.15 | 5.3 | 2.6 |
| Std. RN-50 | 100 | 0.9 | 0.9 | 5/5 | 1.00 | 1.7 | 0.3 |
| Salman RN-18 | 20 | 10.5{sup}*` | 14.0 | 39/4 | 12.7 | 11.4 | |
| Salman RN-18 | 50 | 4.0{sup}*` | 5.6 | 18/2 | 6.5 | 4.2 | |
| Salman RN-18 | 100 | 1.3 | 1.8 | 9/4 | 0.27 | 4.1 | 1.3 |
| Salman RN-50 | 20 | 20.3{sup}*` | 26.0 | 64/7 | 19.8 | 19.1 | |
| Salman RN-50 | 50 | 7.7{sup}*` | 10.0 | 35/12 | 0.0011 | 9.5 | 7.6 |
| Salman RN-50 | 100 | 3.0{sup}*` | 4.6 | 22/6 | 0.0037 | 5.7 | 3.7 |
| Wong RN-50 | 20 | 16.9{sup}*` | 20.5 | 45/9 | 17.9 | 16.9 | |
| Wong RN-50 | 50 | 6.7{sup}*` | 9.5 | 28/0 | 9.3 | 7.6 | |
| Wong RN-50 | 100 | 3.4{sup}*` | 5.3 | 21/2 | 6.8 | 4.6 | |
| XCiT-S12 | 20 | 44.6 | 44.8 | 14/12 | 0.85 | 51.2 | 46.1 |
| XCiT-S12 | 50 | 26.4{sup}*` | 27.9 | 26/11 | 0.02 | 40.3 | 28.4 |
| XCiT-S12 | 100 | 14.5{sup}*` | 16.0 | 23/8 | 0.011 | 34.0 | 14.7 |
Table 6.
Table 7. ImageNet evaluation images at , robust accuracy (%) of GRS, GRS without the tabu list and GRS accepting every candidate, with Sparse-RS for reference. Lower is a stronger attack; bold: strongest in the row; */†: variant significantly stronger/weaker than GRS (exact McNemar, ).
| model | GRS | no tabu | accept all | Sparse-RS |
| Std. RN-50 | 3.3 | 3.3 | 27.3{sup}†` | 5.3 |
| Salman RN-18 | 4.0 | 5.1{sup}†` | 13.1{sup}†` | 6.5 |
| Salman RN-50 | 7.7 | 9.1{sup}†` | 22.9{sup}†` | 9.5 |
| Wong RN-50 | 6.7 | 8.7{sup}†` | 18.9{sup}†` | 9.3 |
| XCiT-S12 | 26.4 | 26.3 | 43.7{sup}†` | 40.3 |
Table 7.
On ImageNet, removing the cold drop, the tabu list and swap-only steps costs 0.9–2.8 points at ( on the three robust CNNs and 0.02 on XCiT), 3.5–5.7 points at on the robust CNNs, and 0.5–1.9 points at on the robust models. At it moves the attack from within 0.7 points of sAA to 1.4–2.4 points above it on the four CNNs, and from below Sparse-RS to above it on two of them. Without the three settings the search is less Sparse-RS early but slows down in the late phase, where one or two pixels are swapped per step (Figure 5, appendix).
Figure 5. Robust accuracy against iterations (sPGD, GRS, GRS) or queries (Sparse-RS) on three ImageNet models at , seed 0. The axis counts steps, not compute: one GRS or sPGD iteration costs 3 units and one Sparse-RS query 1. GRS has no cold drop, no tabu list and spends a quarter of its steps on values.
Diagnostics. The reliability measurements of § 4 explain most of the differences between models. The acceptance ratio between the tempered proposal and Sparse-RS’s (Figure 2, left) is 2.9–10.8 before step 100 and 2.1–4.6 before step 1000 on the nine RobustBench CIFAR-10 models, but only 0.6–0.9 on sAT and sTRADES. These are the two regimes of Proposition 3.
On the robust ImageNet CNNs the ratio falls to 0.5–0.8 before step 1000. Splitting the proposal into its parts shows why: there the tempered proposal is accepted 20–55% less often than a uniform proposal with the same best-response fill, while the fill itself still helps (Table 9). Rules 3 and 5 recover the gradient’s value there: the cold drop uses the reliable drop score, and the tabu list keeps the proposal from returning to the non-linear top of the add ranking.
An open point. On sAT and sTRADES no single-move statistic favours the gradient. The add and drop scores are negatively correlated with the truth, the best-response corner is at chance, and the tempered proposal is accepted no more often than Sparse-RS’s (Table 9). Yet GRS is level with Sparse-RS on sAT and 3.4 points stronger on sTRADES (, ), and the ablation shows that the tempered proposal, the best-response fill and the tabu list all contribute on sTRADES.
Limitations
The bounds of Secs. 3 and § 4 are per step; we do not estimate , and ReLU networks are only piecewise smooth, so the bounds explain the measurements rather than predict them. sAA breaks significantly more points on the Sehwag RN-18 and on the standard RN-50 at , and at with one of the three seeds (Table 1, Table 2 and Table 5). Three settings (, the tabu list and swap-only steps) were chosen among nine variants on two ImageNet models; their gain on the evaluation images is similar, including on the three other models (Sec. A). Finally, GRS needs gradients, so it cannot replace a black-box attack where they are unavailable.
Conclusion
A pixel- attack is a proposal and an acceptance rule, and how far the gradient can be trusted for each can be measured. GRS lets the gradient propose and the loss accept, and is within one point of the three-member ensemble or stronger on 17 of 18 settings, and significantly stronger on 8, at 3 instead of up to 7 units. Code and all per-point results will be released.
Hyperparameter selection
All settings were chosen on held-out points that are disjoint from the evaluation points of § 6.
CIFAR-10. Greedy acceptance, the add temperature , the best-response fill and the schedule were chosen on CIFAR-10 test points 0–999 of three models: the standard model at , and the Gowal PRN-18 and Sehwag RN-18 at .
ImageNet. The diagnostics of § 4 on ImageNet validation images 0–499 led us to compare nine settings of the drop temperature, the tabu list, the add temperature and the value steps on the same images, for Salman RN-50 and Wong RN-50 only (Table 4). We chose the best: cold drop, tabu list and swap-only steps with , which is GRS. On the selection images it is 3.2 and 1.8 points stronger than GRS. On the evaluation images (Table 6) the gains on the same two models are 2.3 and 2.8 points, and on the three models outside the selection comparison they are 1.6 (Salman RN-18), 1.5 (XCiT) and 0.9 points (standard RN-50, ). On CIFAR-10 the three settings together have no significant effect on any of the 13 configurations (, Table 12), and pooled over all 13 each of GRS and GRS breaks 256 points that the other misses.
Settings of the attacks
GRS. , , and with Sparse-RS’s halving schedule rescaled to the budget. New pixels take the best-response corner, proposed pixels are tabu until the next acceptance, acceptance is greedy, and the gradient is that of (§ 5). The initial support and values are random, and each point stops once it is broken. Standardized scores use the mean and variance over the allowed pixels of the point. GRS differs in three ways: , no tabu list, and with probability 0.25 a value step (a sign step of size 0.25 on all values in the support) instead of a swap.
Official attacks. sPGD proj, sPGD unproj and Sparse-RS run from the sAA repository with the arguments of its evaluation script: , , patience 3 and the adaptive loss. Sparse-RS uses with cross-entropy on robust models and with the margin loss on standard ones. -zero runs from its repository for 10k iterations with its defaults (Adam, cosine schedule) and no budget; it minimizes the number of changed features, and a point counts as broken if the returned input differs from the clean one at most pixels. PGD0 runs from the authors’ code with plus box constraints, 100 steps per restart, step size 120000/255 and restarts. GreedyPixel runs in its white-box mode (the surrogate is the target model), with its pixel order cut to the top pixels so that at most pixels change. Every success of every attack is re-checked on a fresh forward pass: the point must be misclassified, at most pixels may differ, and all values must lie in .
Additional tables and figures
Table 13. CIFAR-10 sparsity sweep with GRS (, no tabu list, value steps; 1000 evaluation points per row), robust accuracy (%). Lower is a stronger attack; bold: strongest single attack in the row; b/c: points broken only by GRS/ only by sAA, with the exact McNemar ; : GRS significantly stronger/weaker than sAA ().
| model | proj | unproj | Sparse-RS | sAA | GRS | b/c | ||
| Std. PRN-18 | 3 | 27.6 | 36.1 | 22.0 | 20.6 | 21.8 | 15/27 | 0.088 |
| Std. PRN-18 | 8 | 1.3 | 7.6 | 1.0 | 0.6 | 0.7 | 1/2 | 1.00 |
| Gowal PRN-18 | 5 | 52.8 | 57.5 | 45.5 | 44.3 | 45.2 | 20/29 | 0.25 |
| Gowal PRN-18 | 10 | 31.3 | 36.4 | 24.9 | 23.6 | 22.5 | 28/17 | 0.14 |
| Gowal PRN-18 | 15 | 17.6 | 24.9 | 11.4 | 10.8 | 9.5* | 25/12 | 0.047 |
| Gowal PRN-18 | 30 | 1.3 | 4.3 | 1.0 | 0.7 | 0.4 | 4/1 | 0.38 |
| Sehwag RN-18 | 5 | 62.0 | 61.2 | 63.6 | 59.7 | 59.6 | 19/18 | 1.00 |
| Sehwag RN-18 | 10 | 34.4 | 33.0 | 38.1 | 31.3 | 32.1 | 22/30 | 0.33 |
| Sehwag RN-18 | 15 | 15.7 | 14.8 | 20.7 | 13.2 | 14.3 | 17/28 | 0.14 |
| Sehwag RN-18 | 30 | 0.4 | 0.2 | 2.2 | 0.0 | 0.5 | 0/5 | 0.062 |
| sAT PRN-18 | 5 | 80.4 | 80.1 | 73.0 | 72.9 | 71.2* | 24/7 | 0.0033 |
| sAT PRN-18 | 10 | 78.6 | 78.1 | 59.2 | 59.2 | 57.3* | 28/9 | 0.0026 |
| sAT PRN-18 | 15 | 77.8 | 77.2 | 47.2 | 47.2 | 45.9 | 36/23 | 0.12 |
| sAT PRN-18 | 30 | 72.0 | 73.9 | 19.5 | 19.5 | 19.7 | 28/30 | 0.90 |
Proofs
Notation and assumption. Fix a state with adversarial input , a pixel and a value . Write for the perturbation that equals at pixel and elsewhere, so that adding pixel at value moves the input from to . Since , pixel of equals , and the new pixel lies in . Write for the part of the gradient that belongs to pixel , so . We assume that is differentiable along every such segment and that is -Lipschitz in pixel ’s coordinates:
ReLU networks satisfy this only piecewise, so is a local smoothness proxy. For every each coordinate satisfies , hence
The add score and the best-response corner
Lemma 2 (closed form of the add score). , and the maximum defining is attained at the best-response corner , whose channel is if and otherwise.
Proof.
=\max_{v\in B_i}\sum_{c=1}^{C}(-g_{ic})v_c
=\sum_{c=1}^{C}\max_{v_c\in[-x_{ic},1-x_{ic}]}(-g_{ic})v_c
=\sum_{c=1}^{C}\max\left(-g_{ic}(1-x_{ic}),g_{ic}x_{ic}\right)
The endpoint that attains the maximum in channel is when and when , which is .
Proof of Lemma 1 (first-order reliability)
Let for , so that and is the margin after the add.
=\int_0^1\varphi'(t),dt-\langle g_i,v\rangle
=\int_0^1\langle\nabla_i m(x'+te_i(v)),v\rangle,dt-\langle g_i,v\rangle
=\int_0^1\left\langle\nabla_i m(x'+te_i(v))-\nabla_i m(x'),v\right\rangle,dt
Bounding the integrand gives
which is the claim.
The two consequences stated after Lemma 1. At the best-response corner, Lemma 2 gives , so
For two pixels , each added at its best-response corner,
so the first-order order of the two pixels is then guaranteed to be the true order.
Proof of prop:accept (accepting every step)
Part (a). Lemma 1 certifies that an add at value decreases only if its upper bound is negative. The smallest such bound over all values of pixel is
This holds for every pixel , so no single-pixel add carries a certified decrease of , and an attack that accepts every iterate gets no descent certificate from Lemma 1.
Part (b). Condition on the support evaluated at iteration ; by assumption it is independent of , and is uniform over the subsets of size .
(At least helpful pixels iff some -subset is helpful) {#eq:25}
(Union bound; independent of ) {#eq:26}
(; count the -subsets containing ) {#eq:27}
(Expand the binomial coefficients) {#eq:28}
because {#eq:29}
The bound does not depend on , so it also holds unconditionally, and a union bound over iterations multiplies it by . □
The numerical example. For , , and ,
so a success needs on the order of iterations, the number quoted in Sec. 3.
Proof of prop:blind (greedy acceptance of blind proposals)
Suppose the current support holds helpful pixels. A single swap drops a pixel drawn uniformly from and adds a pixel drawn uniformly from the pixels outside , independently. Under the additive model the swap changes the margin by
which is negative exactly when and . Let be the probability that one step is accepted at level .
(Greedy: accept iff ; and independent) {#eq:32}
( holds unhelpful pixels; helpful pixels lie outside ) {#eq:33}
An accepted swap raises the level from to exactly , and a rejected swap leaves the state unchanged. Proposals are drawn afresh at every step, so the time spent at level is geometric with success probability . Starting from level ,
(The levels are visited in order) {#eq:34}
(Mean of a geometric distribution) {#eq:35}
(Substitute ) {#eq:36}
(Each term is largest at ) {#eq:37}
() {#eq:38}
None of these quantities involves the gradient, because the proposals do not. □
The numerical example. For , , , and the exact sum is
Proof of prop:temper (tempered proposals)
Let be the finite set of moves, the uniform distribution on it, and with and , so that sums to one.
The identity.
The lower bound.
The upper bound.
The normalizer is at least one.
so . Equality in Jensen’s inequality would require to be constant under ; has variance , so and for every finite . If under , then by the moment generating function of the standard normal, so .
The limit . On a finite set the scores are bounded, . A second-order expansion of the exponential gives
so , while and . Both bounds of Proposition 3 therefore tend to , and the tempered proposal tends to the uniform one.
Gain and price. The lower bound exceeds 1 iff , that is , which is the gain condition of § 4. If , the lower bound equals , so acceptance is at least this factor times that of uniform proposals.
Swaps. Let a swap draw its add and its drop independently, from and , and let be the uniform swap. Then
(Independence of the two draws)
(Definition of each side’s )
The identity and both bounds above used only with , so they hold for swaps with the exponent replaced by this sum: the exponents of the two sides add.
Proof of prop:fill (best-response fill)
Let , the margin change of adding pixel at value . A uniformly random corner of takes, in each channel independently, each endpoint and with probability . The best-response corner minimizes over (Lemma 2), so in each channel
(Channel-wise minimizer)
(Minimum of two numbers = their mean − half their distance )
Then
(Lemma 1 at and at )
(Linearity of expectation)
(Inner product as a sum over channels)
()
(Equation (37))
(Definition of the norm)
References
- [1]Emile Aarts and Jan Karel Lenstra, editors. Local Search in Combinatorial Optimization. Wiley, 1997. 2
- [2]Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, and Matthias Hein. Square attack: A query-efficient black-box adversarial attack via random search. In Eur. Conf. Comput. Vis., pages 484–501, 2020. 2arxiv.org/abs/1912.00049
- [3]Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In Int. Conf. Mach. Learn., 2018. 2arxiv.org/abs/1802.00420
- [4]Wieland Brendel, Jonas Rauber, Matthias Kümmerer, Ivan Ustyuzhaninov, and Matthias Bethge. Accurate, reliable and fast robustness evaluation. In Adv. Neural Inform. Process. Syst., 2019. 2arxiv.org/abs/1907.01003
- [5]Tom B. Brown, Dandelion Mané, Aurko Roy, Martín Abadi, and Justin Gilmer. Adversarial patch. arXiv preprint arXiv:1712.09665, 2017. 2arxiv.org/abs/1712.09665
- [6]Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In IEEE Symposium on Security and Privacy, 2017. 2arxiv.org/abs/1608.04644
- [7]Nicholas Carlini, Anish Athalye, Nicolas Papernot, Wieland Brendel, Jonas Rauber, Dimitris Tsipras, Ian Goodfellow, Aleksander Madry, and Alexey Kurakin. On evaluating adversarial robustness. arXiv preprint arXiv:1902.06705, 2019. 2arxiv.org/abs/1902.06705
- [8]Pin-Yu Chen, Yash Sharma, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsieh. EAD: Elastic-net attacks to deep neural networks via adversarial examples. In AAAI, 2018. 2arxiv.org/abs/1709.04114
- [9]Antonio Emanuele Cinà, Francesco Croce, Villani, Maura Pintor, Lea Schönherr, Battista Biggio, and Marcello Pelillo. σ-zero: Gradient-based optimization of ℓ0-norm adversarial examples. In Int. Conf. Learn. Represent., 2025. 2DOI
- [10]Francesco Croce and Matthias Hein. Sparse and imperceivable adversarial attacks. In Int. Conf. Comput. Vis., pages 4724–4732, 2019. 2arxiv.org/abs/1909.05040
- [11]Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In Int. Conf. Mach. Learn., 2020. 2, 5arxiv.org/abs/2003.01690
- [12]Francesco Croce and Matthias Hein. Mind the box: l₁-APGD for sparse adversarial attacks on image classifiers. In Int. Conf. Mach. Learn., pages 2201–2211, 2021. 2arxiv.org/abs/2103.01208
- [13]Francesco Croce, Maksym Andriushchenko, Vikash Sehwag, Edoardo Debenedetti, Nicolas Flammarion, Mung Chiang, Prateek Mittal, and Matthias Hein. RobustBench: A standardized adversarial robustness benchmark. In NeurIPS Datasets and Benchmarks Track, 2021. 6arxiv.org/abs/2010.09670
- [14]Francesco Croce, Maksym Andriushchenko, Naman D. Singh, Nicolas Flammarion, and Matthias Hein. Sparse-RS: A versatile framework for query-efficient sparse black-box adversarial attacks. In AAAI, 2022. 1, 2
- [15]Jiequan Cui, Zhuotao Tian, Zhisheng Zhong, Xiaojun Qi, Bei Yu, and Hanwang Zhang. Decoupled Kullback-Leibler divergence loss. In Adv. Neural Inform. Process. Syst., 2024. 6arxiv.org/abs/2305.13948
- [16]Edoardo Debenedetti, Vikash Sehwag, and Prateek Mittal. A light recipe to train robust vision transformers. In IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pages 225–253, 2023. 6arxiv.org/abs/2209.07399
- [17]Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hierarchical image database. In IEEE Conf. Comput. Vis. Pattern Recog., pages 248–255, 2009. 6
- [18]Xiaoyi Dong, Dongdong Chen, Jianmin Bao, Chuan Qin, Lu Yuan, Weiming Zhang, Nenghai Yu, and Dong Chen. GreedyFool: Distortion-aware sparse adversarial attack. In Adv. Neural Inform. Process. Syst., 2020. 2arxiv.org/abs/2010.13773
- [19]Alaaeldin El-Nouby, Hugo Touvron, Mathilde Caron, Piotr Bojanowski, Matthijs Douze, Armand Joulin, Ivan Laptev, Natalia Neverova, Gabriel Synnaeve, Jakob Verbeek, and Hervé Jégou. XCiT: Cross-covariance image transformers. In Adv. Neural Inform. Process. Syst., 2021. 6
- [20]Fred Glover. Tabu search—part I. ORSA Journal on Computing, 1(3):190–206, 1989. 2, 5DOI
- [21]Ian J. Goodfellow, Jonathan Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In Int. Conf. Learn. Represent., 2015. 1DOI
- [22]Sven Gowal, Sylvestre-Alvise Rebuffi, Olivia Wiles, Florian Stimberg, Dan Andrei Calian, and Timothy A. Mann. Improving robustness using generated data. In Adv. Neural Inform. Process. Syst., 2021. 6arxiv.org/abs/2110.09468
- [23]Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In Eur. Conf. Comput. Vis., 2016. 6arxiv.org/abs/1603.05027
- [24]Holger H. Hoos and Thomas Stützle. Stochastic Local Search: Foundations and Applications. Morgan Kaufmann, 2004. 2
- [25]Jinyuan Jia, Binghui Wang, Xiaoyu Cao, Hongbin Liu, and Neil Zhenqiang Gong. Almost tight L0-norm certified robustness of top-k predictions against adversarial perturbations. In Int. Conf. Learn. Represent., 2022. 2
- [26]Danny Karmon, Daniel Zoran, and Yoav Goldberg. LaVAN: Localized and visible adversarial noise. In Int. Conf. Mach. Learn., pages 2507–2515, 2018. 2arxiv.org/abs/1801.02608
- [27]Scott Kirkpatrick, C. Daniel Gelatt, and Mario P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671–680, 1983. 2
- [28]Wouter Kool, Herke van Hoof, and Max Welling. Stochastic beams and where to find them: The Gumbel-Top-k trick for sampling sequences without replacement. In Int. Conf. Mach. Learn., pages 3499–3508, 2019. 2, 5arxiv.org/abs/1903.06059
- [29]Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009. 6
- [30]Alexander Levine and Soheil Feizi. Robustness certificates for sparse adversarial attacks by randomized ablation. In AAAI, pages 4585–4593, 2020. 2arxiv.org/abs/1911.09272
- [31]Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In Int. Conf. Learn. Represent., 2018. 1, 2arxiv.org/abs/1706.06083
- [32]Quinn McNemar. Note on the sampling error of the difference between correlated proportions or percentages. Psychometrika, 12(2):153–157, 1947. 6pubmed.ncbi.nlm.nih.gov/20254758
- [33]Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21(6):1087–1092, 1953.
- [34]Apostolos Mdosas, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard. SparseFool: A few pixels make a big difference. In IEEE Conf. Comput. Vis. Pattern Recog., 2019.arxiv.org/abs/1811.02248
- [35]Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson, Z. Berkay Celik, and Ananthram Swami. The limitations of deep learning in adversarial settings. In IEEE European Symposium on Security and Privacy, 2016.arxiv.org/abs/1511.07528
- [36]Maura Pintor, Fabio Roli, Wieland Brendel, and Battista Biggio. Fast minimum-norm adversarial attacks through adaptive norm constraints. In Adv. Neural Inform. Process. Syst., 2021.
- [37]Jary Pomponi, Simone Scardapane, and Aurelio Uncini. Pixle: A fast and effective black-box attack based on rearranging pixels. In Int. Conf. Neural Netw., 2022.DOI
- [38]Rahul Rade and Seyed-Mohsen Moosavi-Dezfooli. Reducing excessive margin to achieve a better accuracy vs. robustness trade-off. In Int. Conf. Learn. Represent., 2022.
- [39]Sylvestre-Alvise Rebuffi, Sven Gowal, Dan Andrei Calian, Florian Stimberg, Olivia Wiles, and Timothy Mann. Data augmentation can improve robustness. In Adv. Neural Inform. Process. Syst., 2021.arxiv.org/abs/2111.05328
- [40]Hadi Salman, Andrew Ilyas, Logan Engstrom, Ashish Kapoor, and Aleksander Madry. Do adversarially robust ImageNet models transfer better? In Adv. Neural Inform. Process. Syst., 2020.arxiv.org/abs/2007.08489
- [41]Vikash Sehwag, Saeed Mahloujifar, Tinashe Handina, Sihui Dai, Chong Xiang, Mung Chiang, and Prateek Mittal. Robust learning meets generative models: Can proxy distributions improve adversarial robustness? In Int. Conf. Learn. Represent., 2022.arxiv.org/abs/2104.09425
- [42]Jiawei Su, Danilo Vasconcellos Vargas, and Kouichi Sakurai. One pixel attack for fooling deep neural networks. IEEE Transactions on Evolutionary Computation, 23(5):828–841, 2019.DOI
- [43]Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In Int. Conf. Learn. Represent., 2014.arxiv.org/abs/1312.6199
- [44]Florian Tramèr, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. In Adv. Neural Inform. Process. Syst., 2020.arxiv.org/abs/2002.08347
- [45]Jonathan Uesato, Brendan O’Donoghue, Aäron van den Oord, and Pushmeet Kohli. Adversarial risk and the dangers of evaluating against weak attacks. In Int. Conf. Mach. Learn., 2018.arxiv.org/abs/1802.05666
- [46]Hanrui Wang, Ching-Chun Chang, Chun-Shien Lu, Christopher Leckie, and Isao Echizen. GreedyPixel: Fine-grained black-box adversarial attack via greedy algorithm. IEEE Transactions on Information Forensics and Security, 20, 2025.DOI
- [47]Zekai Wang, Tianyu Pang, Chao Du, Min Lin, Weiwei Liu, and Shuicheng Yan. Better diffusion models further improve adversarial training. In Int. Conf. Mach. Learn., 2023.arxiv.org/abs/2302.04638
- [48]Eric Wong, Leslie Rice, and J. Zico Kolter. Fast is better than free: Revisiting adversarial training. In Int. Conf. Learn. Represent., 2020.arxiv.org/abs/2001.03994
- [49]Sergey Zagoryuko and Nikos Komodakis. Wide residual networks. In British Machine Vision Conference, 2016.
- [50]Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In Int. Conf. Mach. Learn., 2019.arxiv.org/abs/1901.08573
- [51]Xuyang Zhong and Chen Liu. Sparse-PGD: A unified framework for sparse adversarial perturbations generation. arXiv preprint arXiv:2405.05075, 2025. Accepted by IEEE TPAMI.arxiv.org/abs/2405.05075
- [52]Xuyang Zhong, Yixiao Huang, and Chen Liu. Towards efficient training and evaluation of robust models against l₀ bounded adversarial perturbations. In Int. Conf. Mach. Learn., pages 61708–61726, 2024.



