Don't Waste the Noise: Importance-Guided Perturbation Allocation under Joint Global and Local Constraints

Melika Shirian; Kianoosh Vadaei

cs.LGOct 1, 2026

Don't Waste the Noise: Importance-Guided Perturbation Allocation under Joint Global and Local Constraints

Authors: Melika Shirian, Kianoosh Vadaei

Organizations: Independent Researcher

Abstract

Adversarial optimization under a shared $\ell_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 $\ell_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- $L_{1}$ 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	$\Delta_{\mathrm{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.

\Delta_{\mathrm{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- $\ell_{1}$ budget $b$	$4/255$
Capacity mean $\mu_{E}$	$12/255$
Capacity std. $\sigma_{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.

	$\lambda=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

\lambda

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- $\ell_{1}{\times}255$	$\ell_{\infty}{\times}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-

\ell_{1}

and

\ell_{\infty}

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	$\Delta$	95% CI	$p_{\mathrm{Holm}}$
CIFAR-10	WRN-94-16	APGD-CE	9.34	[8.76, 9.93]	$2.22\times 10^{-262}$
CIFAR-10	WRN-94-16	APGD-DLR	7.70	[7.15, 8.23]	$2.08\times 10^{-208}$
CIFAR-10	WRN-94-16	PMA	8.13	[7.58, 8.70]	$4.09\times 10^{-224}$
CIFAR-10	WRN-28-10	APGD-CE	9.44	[8.77, 10.11]	$3.86\times 10^{-212}$
CIFAR-10	WRN-28-10	APGD-DLR	7.45	[6.85, 8.05]	$3.91\times 10^{-160}$
CIFAR-10	WRN-28-10	PMA	7.79	[7.19, 8.41]	$7.86\times 10^{-171}$

Appendix

Table 21: Full paired main-result statistics.

\Delta

\mathrm{ASR}_{\mathrm{ours}}-\mathrm{ASR}_{\mathrm{baseline}}

in percentage points.

p_{\mathrm{Holm}}

is the globally Holm-corrected exact McNemar

p

-value.

			Conventional $\ell_{1}$ ASR (%)			Capacity-limited ASR (%)
Dataset	Model	$N$	$\ell_{1}$ -APGD	FMN- $\ell_{1}$	Ours	Adapted $\ell_{1}$ -APGD	Adapted FMN- $\ell_{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

\ell_{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	Max mean- $\ell_{1}$ excess	Max cap excess
APGD-CE	$3.07\times 10^{-8}$	$2.98\times 10^{-8}$
APGD-DLR	$2.89\times 10^{-8}$	$2.98\times 10^{-8}$
PMA	$5.68\times 10^{-8}$	$2.98\times 10^{-8}$
Ours	$3.26\times 10^{-8}$	$2.98\times 10^{-8}$

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.

Explore similar work

Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses
Jun 18, 2026Zhuoyu Cheng, Kohei Hatano, Eiji TakimotoConvex Loss Convex Optimization
Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan · RIKEN AIP, Japan · Department of Informatics, Kyushu University, Japan
Distributed Learning with Adversarial Gradient Perturbations
May 5, 2026Nawapon Sangsiri, Yufei TaoBounded Adversary Optimality
CUHK
Tail-Weight Control and Localized Generalization in Nearly Low-Rank Adversarial Classification
Sep 20, 2026Kunyu Wang, Dehan Wang, Wenjun ChenAdversarial Training Adversarial Examples
The Chinese University of Hong Kong · Columbia University

Jun 18, 2026, cs.LGJ/K move · Enter open · S save

Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex 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

Convex Loss Convex Optimization Nonconvex Bounded Adversary Regret

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses

Distributed Learning with Adversarial Gradient Perturbations

Tail-Weight Control and Localized Generalization in Nearly Low-Rank Adversarial Classification