Adversarial optimization under a shared ℓ1 budget requires deciding not only how much perturbation to use, but also where that limited budget should be spent. This allocation problem becomes particularly important when individual input coordinates are subject to local magnitude constraints, which restrict the extent to which perturbation can be concentrated on a small number of locations. We introduce an importance-guided allocation mechanism that uses a fixed clean-gradient prior to steer perturbation toward model-sensitive regions while leaving the feasible perturbation set unchanged. A centered allocation objective encourages perturbation at above-average importance locations and discourages unnecessary expenditure elsewhere, thereby redistributing rather than enlarging the available budget. Across ten robust model--dataset configurations under a common capacity-limited threat setting, the proposed method improves attack success over matched APGD- and PMA-based baselines by 2.52 to 17.70 percentage points. Allocation analysis shows that these gains are accompanied by substantially greater perturbation mass in high-importance regions without increased global ℓ1 consumption. Mechanism ablations further show that centered non-uniform redistribution provides part of the benefit, while model-derived importance yields an additional improvement. These results identify perturbation allocation as a distinct and practically relevant dimension of adversarial optimization under shared-budget, locally constrained threat models.
Figures & tables
Figure 1: Overview of importance-guided perturbation budget allocation. The capacity-limited threat model determines which perturbations are feasible through a shared mean- L1 budget, coordinate-wise capacities, and image-range bounds. Independently, a clean-gradient importance prior is normalized and centered to guide where the perturbation budget is spent. The allocation signal changes the optimization preference without changing the feasible perturbation set.
Figure 2: Qualitative example of importance-aware perturbation allocation. The clean-gradient importance map provides a fixed spatial prior, while the perturbation-magnitude maps show how different mechanism variants distribute perturbation under identical constraints. Ours exhibits stronger alignment with regions emphasized by the importance prior, whereas removing, randomizing, or reversing the guidance changes the resulting allocation pattern.
Dataset
Model
N
CIFAR-10
WRN-94-16
9,368
CIFAR-10
WRN-28-10
7,500
CIFAR-10
XCiT-S12
9,006
CIFAR-100
WRN-28-10
7,383
CIFAR-100
XCiT-S12
6,734
CIFAR-100
WRN-70-16
7,522
Table 1: Evaluation panel. N is the number of clean-correct inputs attacked in each configuration; all methods within a row use the same evaluation population.
Dataset
Model
N
APGD-CE
APGD-DLR
PMA
Ours
Δbest
CIFAR-10
WRN-94-16
9,368
8.64
10.28
9.84
17.98
+7.70
CIFAR-10
WRN-28-10
7,500
10.81
12.80
12.47
20.25
+7.45
CIFAR-10
XCiT-S12
9,006
15.08
17.03
17.03
22.52
+5.49
CIFAR-100
WRN-28-10
7,383
22.54
28.44
27.59
35.41
+6.97
CIFAR-100
XCiT-S12
6,734
25.10
30.62
30.83
33.35
+2.52
CIFAR-100
WRN-70-16
7,522
20.15
25.38
24.82
32.53
+7.15
Table 2: Conditional ASR (%) under the common capacity-limited threat model. Δbest is Ours minus the highest-ASR matched APGD/PMA baseline in the same configuration.
Figure 3: Paired ASR improvement over the highest-ASR matched APGD/PMA baseline in each configuration. Horizontal bars show 95% paired confidence intervals; full statistics are reported in Appendix L .
Dataset
Model
APGD-CE
APGD-DLR
PMA
Ours
CIFAR-10
WRN-94-16
11.12
10.84
11.05
30.36
CIFAR-10
WRN-28-10
11.09
10.83
11.05
29.14
CIFAR-10
XCiT-S12
10.72
10.61
10.69
25.19
CIFAR-100
WRN-28-10
11.31
11.08
11.17
24.96
CIFAR-100
XCiT-S12
11.03
11.02
11.17
22.77
CIFAR-100
WRN-70-16
11.20
11.08
11.13
26.22
Table 3: Perturbation mass (%) in the highest-importance 10% of spatial locations. Uniform spatial allocation corresponds to approximately 10% .
Figure 4: Cumulative perturbation mass over importance-ranked locations. Locations are ordered from highest to lowest clean-gradient importance; the dashed diagonal denotes uniform allocation.
Variant
CIFAR-10
CIFAR-100
ImageNet
NoMask
10.2
23.9
24.0
Uncentered
3.9
13.7
20.4
RandomMask
14.2
28.2
29.2
InvertedMask
14.5
25.9
23.4
SmoothMask
17.6
34.4
36.2
Ours
19.6
37.9
36.8
Table 4: Mechanism ablations, conditional ASR (%). RandomMask reports the mean over five spatial permutations.
Figure 5: Mechanism ablation: allocation versus attack effect. Randomized guidance captures part of the benefit of non-uniform redistribution, while the model-derived prior provides an additional gain.
Appendix figures & tables21 assets
Supplementary material from the paper’s appendix.
Appendix
Projection
CIFAR-10
CIFAR-100
ImageNet
Sequential
19.6
37.9
36.8
Exact
19.4
37.7
37.2
Appendix
Table 5: Projection-operator control. Values are conditional ASR (%) on the reference ablation populations.
Capacity structure
CIFAR-10
ImageNet
Heterogeneous envelope
19.6
36.8
Uniform 12/255 cap
19.6
36.8
No local cap
18.3
40.4
Appendix
Table 6: Local-capacity structure control. Values are conditional ASR (%). The heterogeneous envelope is the main setting.
Dataset
Model
Dataset size
Clean acc. (%)
Clean-correct
Evaluated
Coverage
CIFAR-10
WRN-94-16
10,000
93.68
9,368
9,368
complete
CIFAR-10
WRN-28-10
10,000
92.16
9,216
7,500
partial
CIFAR-10
XCiT-S12
10,000
90.06
9,006
9,006
complete
CIFAR-100
WRN-28-10
10,000
73.83
7,383
7,383
complete
CIFAR-100
XCiT-S12
10,000
67.34
6,734
6,734
complete
CIFAR-100
WRN-70-16
10,000
75.22
7,522
7,522
complete
Appendix
Table 7: Main evaluation populations. Clean accuracy and clean-correct counts are computed on the full corresponding test or validation set. “Evaluated” denotes the number of clean-correct images included in the reported attack run.
Dataset
Model
N
CIFAR-10
WRN-28-10
1,000
CIFAR-100
WRN-28-10
1,000
ImageNet
Swin-L
500
Appendix
Table 8: Reference populations used for the ablation studies.
Parameter
Value
Global mean- ℓ1 budget b
4/255
Capacity mean μE
12/255
Capacity std. σE
2/255
Capacity mode
heterogeneous envelope
Capacity quantile range
[10−3,1−10−3]
Optimization steps
50
Appendix
Table 9: Reference hyperparameters for the proposed allocation-guided optimizer.
Component
Version / configuration
Python
3.12.13
PyTorch
2.10.0+cu128
Torchvision
0.25.0+cu128
CUDA
12.8
cuDNN
91002
RobustBench
1.1
Appendix
Table 10: Recorded experimental software environment.
λ=0
0.1
0.2
0.35
Dataset
ASR
Top-10
ASR
Top-10
ASR
Top-10
ASR
Top-10
CIFAR-10
10.2
10.70
17.9
24.27
20.3
26.57
20.6
28.21
ImageNet
24.0
10.49
32.6
16.35
36.8
18.95
40.8
21.18
Appendix
Table 11: Lambda sensitivity on the available reference runs. Top-10 mass is the fraction of perturbation magnitude assigned to the highest-importance 10% of spatial locations.
Figure 6: Lambda sensitivity. Left: ASR as a function of allocation weight. Right: perturbation mass assigned to the top- 10% importance region. Increasing λ produces progressively stronger importance concentration, but attack effectiveness is non-monotonic.
CIFAR-10
CIFAR-100
ImageNet
Variant
ASR
Top-10
ASR
Top-10
ASR
Top-10
NoMask
10.2
10.70
23.9
10.74
24.0
10.49
Uncentered
3.9
10.31
13.7
10.58
20.4
10.46
RandomMask
14.24 (0.19)
13.68
28.18 (0.16)
13.40
29.24 (0.09)
13.63
InvertedMask
14.5
8.24
25.9
9.26
23.4
10.44
SmoothMask
17.6
24.74
34.4
20.90
36.2
18.03
Appendix
Table 12: Core mechanism ablations. ASR is in percent; Top-10 is perturbation-mass share in the highest-importance 10% of locations. RandomMask reports the mean over five randomized priors, with the ASR standard deviation in parentheses.
CE
Margin
DLR
Prob. Margin
Dataset
NoMask
Guided
NoMask
Guided
NoMask
Guided
NoMask
Guided
CIFAR-10
10.2
19.6
11.7
23.1
11.9
22.3
11.8
18.6
CIFAR-100
23.9
37.9
28.0
41.5
29.5
42.0
28.5
38.2
ImageNet
24.0
36.8
24.0
30.2
24.4
39.2
26.6
43.8
Appendix
Table 13: Objective ablation. Each pair compares an objective without allocation against the same objective augmented by the centered raw importance prior. Values are conditional ASR (%).
Variant
CIFAR-10
CIFAR-100
ImageNet
NoMask, 50 attack steps
10.2
23.9
24.0
Ours, 50 + 1
19.6
37.9
36.8
Ours, 49 + 1
19.6
37.9
36.8
Appendix
Table 14: Compute-matched control. “Raw 49+1” uses 49 iterative attack gradients plus one clean-gradient computation.
Variant
CIFAR-10
CIFAR-100
ImageNet
Sequential projection
19.6
37.9
36.8
Exact projection
19.4
37.7
37.2
Appendix
Table 15: Projection control, conditional ASR (%).
Variant
CIFAR-10
ImageNet
Heterogeneous envelope
19.6
36.8
Uniform 12/255 cap
19.6
36.8
No local cap
18.3
40.4
Appendix
Table 16: Local-capacity structure control, conditional ASR (%).
Dataset
Method
Top-10 (%)
Importance corr.
Effective spatial frac.
Spatial Gini
CIFAR-10
APGD-CE
10.98
0.096
0.842
0.244
APGD-DLR
10.76
0.064
0.815
0.270
PMA
10.93
0.088
0.842
0.245
Ours
28.23
0.692
0.403
0.623
CIFAR-100
APGD-CE
11.18
0.121
0.839
0.247
APGD-DLR
11.06
0.086
0.792
0.290
Appendix
Table 17: Dataset-level macro-averaged allocation diagnostics. Top-10 is the fraction of absolute perturbation mass in the highest-importance 10% of spatial locations.
Dataset
Variant
Top-1
Top-5
Top-10
Top-20
CIFAR-10
NoMask
1.16
5.44
10.70
21.05
InvertedMask
1.35
5.03
8.24
12.78
SmoothMask
2.71
12.69
24.74
46.23
Ours
3.12
14.72
29.06
57.35
CIFAR-100
NoMask
1.16
5.44
10.74
21.24
InvertedMask
1.29
5.24
9.26
15.64
Appendix
Table 18: Cumulative perturbation-mass share (%) after including the most-important spatial locations. A uniform allocation would yield approximately 1% , 5% , 10% , and 20% at the corresponding checkpoints.
Figure 7: Cumulative perturbation mass after ordering locations from highest to lowest clean-gradient importance. The dashed diagonal corresponds to uniform allocation.
Dataset
Method
Mean- ℓ1×255
ℓ∞×255
LPIPS
DISTS
SSIM
CIFAR-10
APGD-CE
4.000
11.49
0.00223
0.06037
0.98126
APGD-DLR
3.999
11.86
0.00255
0.06406
0.97999
PMA
4.000
10.81
0.00226
0.06066
0.98217
Ours
3.907
16.78
0.00296
0.07555
0.95456
CIFAR-100
APGD-CE
4.000
11.45
0.00257
0.06383
0.97816
APGD-DLR
3.997
12.27
0.00300
0.06826
0.97576
Appendix
Table 19: Dataset-level macro-averaged perturbation diagnostics. Mean- ℓ1 and ℓ∞ are multiplied by 255. Lower LPIPS/DISTS and higher SSIM indicate greater perceptual similarity.
Dataset
Method
Backward evals.
Forward evals.
Runtime (s)
CIFAR-10
APGD-CE
50
53
2.86
APGD-DLR
50
53
2.88
PMA
50
102
4.08
Ours
51
103
4.06
CIFAR-100
APGD-CE
50
53
2.42
APGD-DLR
50
53
2.44
Appendix
Table 20: Computational accounting for the main methods. Runtime is the recorded mean attack runtime in seconds; it is intended for within-experiment comparison rather than as hardware-independent benchmarking.
Dataset
Model
Baseline
Δ
95% CI
pHolm
CIFAR-10
WRN-94-16
APGD-CE
9.34
[8.76, 9.93]
2.22×10−262
CIFAR-10
WRN-94-16
APGD-DLR
7.70
[7.15, 8.23]
2.08×10−208
CIFAR-10
WRN-94-16
PMA
8.13
[7.58, 8.70]
4.09×10−224
CIFAR-10
WRN-28-10
APGD-CE
9.44
[8.77, 10.11]
3.86×10−212
CIFAR-10
WRN-28-10
APGD-DLR
7.45
[6.85, 8.05]
3.91×10−160
CIFAR-10
WRN-28-10
PMA
7.79
[7.19, 8.41]
7.86×10−171
Appendix
Table 21: Full paired main-result statistics. Δ is ASRours−ASRbaseline in percentage points. pHolm is the globally Holm-corrected exact McNemar p -value.
Conventional ℓ1 ASR (%)
Capacity-limited ASR (%)
Dataset
Model
N
ℓ1 -APGD
FMN- ℓ1
Ours
Adapted ℓ1 -APGD
Adapted FMN- ℓ1
Ours
CIFAR-10
WRN-94-16
9,368
84.03
81.18
18.01
32.55
22.88
17.98
CIFAR-100
WRN-70-16
7,522
88.86
82.82
32.03
49.19
43.23
32.53
ImageNet
Swin-L
1,000
44.50
33.90
39.50
69.00
16.50
36.00
Appendix
Table 22: Descriptive results under separately parameterized conventional and capacity-limited ℓ1 threat settings. Because the global budget parameterizations differ, changes between the two column groups must not be interpreted as the isolated causal effect of adding local capacities.
Method
Violations
Max mean- ℓ1 excess
Max cap excess
Image-low excess
Image-high excess
APGD-CE
0
3.07×10−8
2.98×10−8
0
0
APGD-DLR
0
2.89×10−8
2.98×10−8
0
0
PMA
0
5.68×10−8
2.98×10−8
0
0
Ours
0
3.26×10−8
2.98×10−8
0
0
Appendix
Table 23: Constraint-validity summary across the ten main model–dataset configurations. Numerical residuals are maximum observed floating-point excesses above the corresponding constraints.
We study adversarial bandit optimization in which the loss functions may be non-convex and non-smooth. In each round, the learner selects an action and observes only the loss incurred at that action. The loss consists of an underlying convex and β-smooth component and an adversarial perturbation that may be chosen after observing the learner's action. The perturbations are subject to a global budget controlling their cumulative magnitude over time. This framework extends the globally budgeted, post-action perturbation model from underlying linear losses to general convex and β-smooth losses. For this broader class, we establish expected regret guarantees that explicitly characterize the effect of the perturbation budget. To establish these guarantees, we modify a standard bandit optimization algorithm and develop an analysis that controls the additional regret caused by the perturbations. In the absence of perturbations, our results reduce to regret guarantees for the standard bandit convex optimization setting with β-smooth losses.
Zhuoyu Cheng, Kohei Hatano, Eiji Takimoto
Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan · RIKEN AIP, Japan · Department of Informatics, Kyushu University, Japan
Privacy concerns in distributed learning often lead clients to return intentionally altered gradient information. We consider the problem of learning convex and L-smooth functions under adversarial gradient perturbation, where a client's gradient reply to a server query can deviate arbitrarily from the true gradient subject to a distance bound. Our study focuses on two fundamental questions: (i) what is the smallest achievable sub-optimality gap (i.e., excess error in optimization) under such responses, and (ii) how many queries are sufficient to guarantee a given sub-optimality gap? We establish tight feasibility thresholds on the sub-optimality gap and provide algorithms that achieve these thresholds with provable query complexity guarantees.
Empirical ramp fitting can assign weight to pure-noise features even when the population optimum ignores them. We quantify this gap for norm-constrained adversarial classification with Gaussian signal and noise. The variance cost relative to normalized signed mean separates into two factors: selecting observations inside the active margin window and the curvature induced by the norm constraint. Changing the tail variance leaves the activewindow probability unchanged but changes the second factor. With positive attack budget and a signal-only predictor of risk below one half, we prove a uniform quadratic tail-deletion bound, including at zero tail variance. Sufficiently accurate approximate global empirical minimizers admit exact fixeddimensional asymptotic covariances in the low-risk regime with isotropic principal covariance. For positive tail variance at most principal variance, the product exceeds one; an additional moment condition transfers it to expected excess ramp and robust classification risks. A wide window analysis characterizes when this ordering reverses. Controlled experiments test the decomposition, and a separate contamination study examines its scope outside the Gaussian training model.
Kunyu Wang, Dehan Wang, Wenjun Chen
The Chinese University of Hong Kong · Columbia University