ML Security PapersImproving the Convergence Rate of Ray Search Optimization for Query-Efficient Hard-Label Attacks
Xinjie Xu 1,2, Shuyu Cheng 3, Dongwei Xu 1,2, Qi Xuan 1,2, Chen Ma 1,2
Published on arXiv
2512.21241
Input Manipulation Attack
OWASP ML Top 10 — ML01
Key Finding
ARS-OPT and PARS-OPT surpass 13 state-of-the-art hard-label black-box attacks in query efficiency on ImageNet and CIFAR-10, with a theoretical O(1/T²) convergence rate.
ARS-OPT / PARS-OPT
Novel technique introduced
In hard-label black-box adversarial attacks, where only the top-1 predicted label is accessible, the prohibitive query complexity poses a major obstacle to practical deployment. In this paper, we focus on optimizing a representative class of attacks that search for the optimal ray direction yielding the minimum $\ell_2$-norm perturbation required to move a benign image into the adversarial region. Inspired by Nesterov's Accelerated Gradient (NAG), we propose a momentum-based algorithm, ARS-OPT, which proactively estimates the gradient with respect to a future ray direction inferred from accumulated momentum. We provide a theoretical analysis of its convergence behavior, showing that ARS-OPT enables more accurate directional updates and achieves faster, more stable optimization. To further accelerate convergence, we incorporate surrogate-model priors into ARS-OPT's gradient estimation, resulting in PARS-OPT with enhanced performance. The superiority of our approach is supported by theoretical guarantees under standard assumptions. Extensive experiments on ImageNet and CIFAR-10 demonstrate that our method surpasses 13 state-of-the-art approaches in query efficiency.
Key Contributions
- ARS-OPT: a Nesterov-accelerated zeroth-order hard-label attack that estimates gradients along a momentum-informed lookahead ray direction, achieving an O(1/T²) convergence rate.
- PARS-OPT: extends ARS-OPT with transfer-based surrogate-model priors to further improve gradient estimation and query efficiency.
- Theoretical convergence guarantee under standard assumptions and empirical outperformance of 13 state-of-the-art hard-label attacks on ImageNet and CIFAR-10.
🛡️ Threat Analysis
Proposes adversarial example generation attacks (ARS-OPT, PARS-OPT) that craft minimal ℓ2-norm perturbations to cause misclassification at inference time under a hard-label black-box constraint — the core definition of an input manipulation/evasion attack.