Pareto-Improving Adversarial Attacks with Primal-Dual Regularization

Transferable adversarial attacks are arguably the most practical black-box threat model. Under the same perturbation budget, stronger transfer attacks attain higher attack success rate (ASR), yet their imperceptibility also tends to degrade. Under such a fixed-budget protocol, transferability and imperceptibility therefore appear to trade off against each other. We argue that this conflict is an artifact of fixed-budget evaluation, not an intrinsic trade-off. When attacks are compared on the ASR--imperceptibility Pareto frontier obtained by sweeping ε, stronger transfer attacks already attain better imperceptibility at matched ASR than weaker ones. To exploit this latent advantage, we introduce the stealthy transfer attack ST, a plug-in primal-dual wrapper that adds an L_infty saturation regularizer to the standard constrained objective and resolves it through a two-step primal-dual update: a projected primal step on the perturbation coupled with an L_1-ball projection on a dual variable that absorbs the regularizer through Fenchel duality, requiring no auxiliary models or handcrafted perceptual priors. Empirically, ST extends the Pareto frontier across different base attacks and additional surrogate architectures. At ε{=}16/255, average imperceptibility gains over each base attack are 17% on LPIPS and 14% on NIQE while ASR is preserved or improved. At matched high-ASR levels, the strongest ST variants further Pareto-dominate dedicated stealth-oriented transfer attacks, confirming that the latent imperceptibility advantage of strong transfer attacks can be unlocked by a primal-dual optimization wrapper without sacrificing transferability. Code will be made available at https://github.com/AndssY/ST.