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

AI summary

Overview

Research area: Adversarial machine learning, specifically decision-based (hard-label) black-box adversarial attacks and zeroth-order (gradient-free) optimization.

Technical level: Advanced. The paper combines adversarial attack design with convergence-rate proofs, an unbiased gradient estimator derived from random orthonormal directions, and Nesterov-style acceleration theory.

Scope: The paper proposes two query-efficient hard-label attack algorithms, ARS-OPT and its prior-guided variant PARS-OPT, proves an O(1/T²) convergence rate under smooth convex assumptions, and reports experiments on ImageNet (Inception-v4 and Swin Transformer classifiers) and CIFAR-10 against 13 state-of-the-art baselines.

What This Paper Is About

Hard-label attacks assume the attacker sees only the model's final predicted class, never probabilities or gradients. Because the predicted label only changes near the decision boundary, these attacks must probe a narrow region, and existing ray-search methods (OPT, Sign-OPT, Prior-OPT) rely on plain gradient descent, ignoring well-known acceleration techniques such as momentum and Nesterov's accelerated gradient. This paper asks whether adding acceleration to the ray-search formulation can reduce the number of queries needed to find a minimal perturbation.

Key Contributions

1. ARS-OPT, a momentum-accelerated hard-label attack. The method estimates gradients not at the current ray direction θ_t but at an interpolated "lookahead" direction θ̃_t = (1 − α_t)θ_t + α_t·m_t, where m_t accumulates historical momentum (initialized as m_0 = θ_0). Two separate gradient estimates, g_1 and g_2, update the main sequence and the auxiliary (momentum) sequence independently.

2. PARS-OPT, a prior-enhanced variant. Transfer-based gradients from surrogate models are injected into the gradient estimation as extra search directions p_{t,i}, orthogonalized against the random directions via Gram-Schmidt. The framework supports multiple surrogates; results are reported with IncResV2 alone and with IncResV2 plus Xception.

3. A theoretical convergence guarantee. The paper constructs g_2 as an unbiased estimator of the true gradient ∇f(θ̃_t) (Theorem 4.1) and proves an O(1/T²) convergence rate under smooth convex assumptions (Theorem 4.2), compared with the O((ln T)/T) rate the paper derives for Sign-OPT (Theorem A.10).

4. State-of-the-art empirical results. The authors report that their framework outperforms 13 state-of-the-art attacks in query efficiency across ImageNet and CIFAR-10 classifiers, including CLIP. Code is released at github.com/machanic/hard_label_attacks.

Main Findings

• Accelerated convergence is provable. Under the assumptions that f is smooth and convex, that g_2(θ̃_t) is an unbiased estimator of ∇f(θ̃_t), and that ζ_t ≤ E_t[(∇f(θ̃_t)ᵀv_t)²] / (L̂ · E_t[‖g_2(θ̃_t)‖²]), Theorem 4.2 bounds the expected suboptimality gap by f(θ_0) − f(θ*) + (γ_0/2)‖θ_0 − θ*‖², yielding an O(1/T²) rate.
• The unbiased estimator is the technical core. Theorem 4.1 shows that for v = Σ sign(gᵀu_i)u_i built from an orthonormalized set of q vectors, E[ĝ] = E[(ḡᵀv̄)²]·g, and E[(ḡᵀv̄)²] = (1/d)((2/π)(q − 1) + 1). Rescaling g_1 by d / ((2/π)(q − 1) + 1) therefore recovers an unbiased estimate of the true gradient.
• Surrogate priors improve over pure random directions. On Inception-v4 with untargeted attacks at a 2K query budget, PARS-OPT with IncResV2 and Xception reaches 9.91, versus 13.42 for Prior-OPT with the same surrogates, 16.54 for QEBA, 44.53 for HSJA and 46.60 for ARS-OPT. At 10K queries the same PARS-OPT configuration reaches 3.05, compared with 3.12 for Prior-OPT (IncResV2&Xception), 3.66 for QEBA and 3.82 for PARS-OPT with IncResV2 only.
• The prior-free ARS-OPT is not uniformly the best. In the Inception-v4 untargeted column, ARS-OPT alone reports 46.60 at 2K and 9.30 at 10K, while Prior-OPT with an IncResV2 surrogate reports 18.13 and 4.03 at the same budgets. The paper's own claim that ARS-OPT "converges substantially faster" than Prior-OPT using the same estimation procedure is not visible in these particular table entries.
• Targeted attacks favor different configurations. On Inception-v4 targeted attacks at 2K queries, Prior-OPT (IncResV2&Xception) reports 42.63, PARS-OPT (IncResV2&Xception) 43.91, PARS-OPT (IncResV2) 49.37 and Prior-OPT (IncResV2) 49.84. At 20K queries, ARS-OPT-S reports the lowest listed value at 7.38, ahead of AHA at 8.12 and QEBA at 9.25.
• Variants with a ✓ marker. The tables include ARS-OPT-S and PARS-OPT-S rows carrying a ✓ in a binary "with" column, and these appear on untargeted and targeted ImageNet results. The provided text does not define what this marker or the "-S" suffix denotes.
• Baseline coverage. Thirteen baselines appear in the tables: HSJA, TA, Sign-OPT, GeoDA, Evolutionary, SurFree, AHA, QEBA, CGBA-H, SQBA, BBA, Prior-Sign-OPT and Prior-OPT. GeoDA, SQBA and BBA show "-" entries in the targeted columns, and GeoDA also reports no 15K/20K targeted results. Swin Transformer rows in the provided excerpt cover only HSJA, TA, Sign-OPT, GeoDA, Evolutionary and SurFree; the highest perturbation value there at 10K untargeted is GeoDA at 19.12 and the lowest is Sign-OPT at 9.90.
• CIFAR-10 and CLIP. The abstract and introduction state that experiments cover ImageNet and CIFAR-10 (and a CLIP-based model in the introduction), but CIFAR-10 and CLIP result tables are not contained in the provided content.

Methodology in Plain English

Instead of asking "which direction reduces the perturbation at the current point," the algorithm first takes a step in the direction it has been moving and asks the question there. This mirrors Nesterov's accelerated gradient: maintain two running sequences — the current ray direction θ_t and a momentum vector m_t — and evaluate the gradient at a blended point between them.

Each iteration has three steps. First, form the lookahead direction θ̃_t by interpolating between θ_t and m_t, with a coefficient α_t chosen as the positive root of α_t² = ζ_t·γ_t·(1 − α_t), a choice dictated by the convergence proof. Second, estimate two gradients at that lookahead point. The first, g_1, is a biased but cheap estimate (from the Sign-OPT or Prior-OPT style procedure); the second, g_2, is a rescaled version of the same finite-difference signal that the theory shows is unbiased, with the scaling factor d / ((2/π)(q − 1) + 1). Third, update θ_{t+1} = θ̃_t − (1/L̂)g_1(θ̃_t) and m_{t+1} = m_t − (ζ_t/α_t)g_2(θ̃_t).

Function values f(θ) come from binary search along a ray. The sign of the directional derivative requires only a single query, which is what makes the sign-based estimate v_t cheap. In PARS-OPT, the search directions are not purely random: the gradients of a differentiable surrogate function h(θ, λ) from one or more surrogate models are added, then the whole set is orthogonalized by Gram-Schmidt so the directions remain independent. Setting the number of priors s to zero reduces PARS-OPT exactly to ARS-OPT. Gradient norms are clipped, and for targeted attacks θ_0 is initialized toward an image from the target class in the training set. The published algorithm is described as a practical approximation of an idealized version for which Theorem 4.2 holds.

Why This Matters

Research impact. The paper moves hard-label attack research beyond "better gradient estimation" toward "better optimization of the same gradient estimates," showing that acceleration is a separate and complementary axis of improvement. It also supplies a reusable unbiased estimator from orthonormalized random directions, together with an explicit convergence-rate comparison (O(1/T²) versus O((ln T)/T) for Sign-OPT).

Real-world applications (drawn from the paper's framing of deployed services that expose only a top-1 label):

• Auditing commercial cloud vision APIs, where only the predicted class is returned to the caller.
• Assessing biometric recognition systems, which typically respond with a match decision rather than a score.
• Penetration testing and vulnerability discovery on proprietary ML services protected by "security-through-obscurity."
• Designing and evaluating defenses by measuring how few queries an adversary actually needs to break them.

Industry relevance. Query budgets are a direct proxy for monetary and rate-limit cost in commercial ML services, so reducing the number of queries translates into cheaper and stealthier audits. Because the method requires no gradients or confidence scores, it applies to any deployed classifier that exposes a label, including hosted CLIP-style models.

Future Directions

• Explaining the role of priors versus acceleration. The reported numbers show PARS-OPT with strong surrogates performing best on untargeted ImageNet, while ARS-OPT alone is weaker than Prior-OPT at the same budgets, so the relative contribution of momentum versus prior information deserves clearer separation.
• Characterizing the "-S" variants and the binary column. The tables introduce ARS-OPT-S and PARS-OPT-S with a ✓ marker that the provided text does not define or analyze.
• Closing the gap between idealized theory and practice. Theorem 4.2 applies to an idealized version of Algorithm 1, while the practical algorithm uses estimated quantities such as D̂_t and ‖∇̂f_t‖² that require extra finite-difference queries; quantifying that gap is an open question.
• Extending beyond the smooth convex regime. The convergence guarantee assumes smoothness and convexity, and it is proven for the ℓ₂ ray-search formulation; behavior under non-convexity, under

Authors’ abstract

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.