Improving the Convergence Rate of Ray Search Optimization for Query-Efficient Hard-Label Attacks

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 minimal $\ell_p$-norm perturbation required to push 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 at a future position 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. Furthermore, we derive the step size analytically, eliminating the need for expensive line-search procedures. To further accelerate convergence, we incorporate surrogate-model-based priors into ARS-OPT's gradient estimation, resulting in PARS-OPT with enhanced performance. The superiority of our approach is supported by rigorous theoretical analysis under mild assumptions. Extensive experiments on ImageNet and CIFAR-10 demonstrate that our method surpasses thirteen state-of-the-art approaches in query efficiency. The source code will be released online.