Query-Efficient Black-box Adversarial Attacks Guided by a Transfer-based Prior

Introduction

Despite the significant success of deep learning models on various tasks , the security and reliability of these models have been challenged in the presence of adversarial examples . The maliciously crafted adversarial examples aim at causing misclassification of a target model by applying human imperceptible perturbations to natural examples. It has garnered increasing attention to study the generation of adversarial examples (i.e., adversarial attack), which is indispensable to discover the weaknesses of deep learning algorithms . Adversarial attacks therefore serve as a surrogate to evaluate robustness , and consequently contribute to the design of more robust deep learning models .

Adversarial attacks are predominantly categorized into white-box attacks and black-box attacks according to different accessibility to the target model. Getting access to the model architecture, parameters and especially gradients, an adversary can adopt various gradient-based methods to generate adversarial examples under the white-box setting, such as the fast gradient sign method (FGSM) , projected gradient descent method (PGD) , etc. By contrast, under the more challenging black-box adversarial setting, the adversary has no or limited knowledge about the target model, and therefore needs to generate adversarial examples without any gradient information. In various real-world applications, the black-box setting is more practical than the white-box counterpart .

Tremendous efforts have been made to develop black-box adversarial attacks . A common idea of these techniques is to utilize an approximate gradient instead of the true but unknown gradient for generating adversarial examples. The approximate gradient can either stem from the gradient of a surrogate white-box model (termed as transfer-based attacks) or be numerically estimated by the zeroth-order optimization algorithms (termed as query-based attacks).

In transfer-based attacks, adversarial examples produced for a surrogate model are probable to remain adversarial for the target model due to the transferability . Recent methods have been introduced to improve the transferability by adopting a momentum optimizer or performing input augmentations . However, the success rate of transfer-based attacks is still far from satisfactory. This is because that there lacks an adjustment procedure when the gradient of the surrogate model points to a non-adversarial region of the target model. In query-based attacks, the true gradient can be estimated by various methods, such as finite difference , random gradient estimation and natural evolution strategies . Although these methods usually result in a higher attack success rate compared with the transfer-based attack methods , they inevitably require a tremendous number of queries to perform a successful attack. The query inefficiency primarily comes from the under-utilization of priors, since the current methods are nearly optimal to estimate the gradient .

To overcome the aforementioned problems and improve black-box adversarial attacks, we propose two prior-guided random gradient-free (PRGF) algorithms based on biased sampling (BS) and gradient averaging (GA), respectively, which can utilize a transfer-based prior for query-efficient black-box attacks. The transfer-based prior originated from the gradient of a surrogate white-box model contains abundant prior knowledge of the true gradient. Despite the same goal, the two proposed methods utilize the transfer gradient in different ways. Specifically, our first method, abbreviated as PRGF-BS, provides a gradient estimate by querying the target model with random samples that are biased towards the transfer gradient and acquiring the corresponding loss values. Our second method, denoted as PRGF-GA, performs a weighted average of the transfer gradient and the gradient estimate provided by the ordinary random gradient-free (RGF) method . Under the gradient estimation framework, we provide theoretical analyses on deriving the optimal coefficients of controlling the strength of the transfer gradient in both algorithms.

Furthermore, our methods are flexible to integrate other prior information. As a concrete example, we incorporate the commonly used data-dependent prior into our algorithms along with the transfer-based prior. We also provide theoretical analyses on how to embrace both priors appropriately. Besides, we extend our methods to the scenario that multiple surrogate models are available, as studied in , in which we can further boost the attack performance with a more effective transfer-based prior. Extensive experiments demonstrate that both of our methods significantly outperform the previous state-of-the-art methods in terms of black-box attack success rate and query efficiency, verifying the superiority of our algorithms for black-box attacks.

This paper substantially extends and improves the conference version . We additionally propose a new PRGF algorithm based on gradient averaging and integrate it with the data-dependent prior. We also consider the scenario that multiple surrogate models are available and provide a subspace projection method to extract a more effective transfer-based prior. Besides, we conduct additional experiments by comparing more methods, using different surrogate models, and considering another dataset, to show the superiority of our methods. Overall, we make the following contributions:

We propose to improve black-box adversarial attacks by incorporating a transfer-based prior given by the gradient of a surrogate model. The transfer-based prior provides abundant prior information of the true gradient due to the adversarial transferability.

We develop two prior-guided random gradient-free (PRGF) algorithms to utilize the transfer-based prior, based on biased sampling and gradient averaging, respectively. Theoretical analyses derive the optimal coefficients of integrating the transfer-based prior.

We demonstrate the flexibility of our algorithms by incorporating the widely used data-dependent prior and considering multiple surrogate models.

We validate that the proposed methods can improve the success rate of black-box adversarial attacks and reduce the requisite numbers of queries significantly compared with the state-of-the-art methods.

The rest of the paper is organized as follows. Section 2 reviews the background and related work on black-box adversarial attacks. Section 3 introduces the gradient estimation framework. Section 4 and Section 5 present the proposed PRGF algorithms, and their extensions with data-dependent priors and multiple surrogate models. Section 6 presents empirical studies. Finally, Section 7 concludes.

Background

Note that formulation (1) corresponds to an untargeted attack. We present our framework and algorithms based on untargeted attacks for clarity, while the extension to targeted ones is straightforward.

An adversarial example can be generated by solving the constrained optimization problem as

where $f$ is a loss function on top of the classifier $C(x)$, e.g., the cross-entropy loss. Several gradient-based methods have been proposed to solve this optimization problem. The typical projected gradient descent method (PGD) iteratively generates adversarial examples as

2 Black-box Attacks

In contrast to white-box attacks, black-box attacks have no or limited knowledge about the target model, which can be challenging yet practical in various real-world applications. We can still adopt the PGD method to generate adversarial examples, except that the true gradient $\nabla_{x}f(x,y)$ is usually replaced by an approximate gradient. Black-box attacks can be roughly divided into transfer-based attacks and query-based attacks. Transfer-based attacks depend on the gradient of a surrogate white-box model to generate adversarial examples, which are probable to fool the black-box model due to the transferability . Some query-based attacks estimate the gradient by the zeroth-order optimization methods, when the loss values could be accessed through queries. Chen et al. propose to estimate the gradient at each coordinate by the symmetric difference quotient as

where $\sigma$ is a small constant and $e_{i}$ is the $i$-th unit basis vector. Although query-efficient mechanisms have been developed , the coordinate-wise gradient estimation inherently leads to the query complexity being proportional to the input dimension $D$, which is prohibitively large with a high-dimensional input space, e.g., $D\approx 270$,$000$ for ImageNet . To improve query efficiency, the approximated gradient $\hat{g}$ can be obtained by the random gradient-free (RGF) method as

3 Attacks based on both Transferability and Queries

There are also several works that utilize both the transferability of adversarial examples and the model queries for black-box attacks. A local substitute model can be trained to mimic the black-box model with a synthetic dataset, in which the labels are given by the black-box model through queries . Then the black-box model can be evaded by the adversarial examples crafted for the substitute model based on the transferability. A meta-model can reverse-engineer the black-box model and predict its attributes (e.g., architecture, optimization procedure, and training samples) through a sequence of model queries. Given the predicted attributes of the black-box model, the attacker can find similar surrogate models, which exhibit better transferability of the generated adversarial examples against the black-box model. All of these methods use queries to obtain knowledge of the black-box model, and train/find surrogate models to generate adversarial examples, with the purpose of improving the transferability. However, we do not optimize the surrogate model, but focus on utilizing the gradient(s) of a (multiple) fixed surrogate model(s) to obtain a more accurate gradient estimate.

Although a recent work also uses the gradient of a surrogate model to improve the query efficiency of black-box attacks, it focuses on a different attack scenario, where the adversary can only acquire the hard-label outputs, but we consider the adversarial setting that the loss values can be accessed. Moreover, this method controls the strength of the transfer gradient by a preset hyperparameter, but we obtain its optimal value through theoretical analyses based on the gradient estimation framework. It is worth mentioning that a similar but independent work also uses surrogate gradients to improve zeroth-order optimization, but they do not apply their method to black-box adversarial attacks.

Gradient Estimation Framework

Before we delve into the details of the proposed methods, we first introduce the gradient estimation framework in this section, which builds up the foundation of our theoretical analyses.

The key problem in black-box adversarial attacks is to estimate the gradient of a target model, which can then be used to carry out gradient-based attacks. The goal of this work is to estimate the gradient $\nabla_{x}f(x,y)$ of the black-box model $f$ more accurately to improve black-box attacks. We denote the gradient $\nabla_{x}f(x,y)$ by $\nabla f(x)$ in the sequel for notation clarity. We assume that $\nabla f(x)\neq 0$ in this paper. The objective of gradient estimation is to find the best estimator that approximates the true gradient $\nabla f(x)$ by reaching the minimum value of the loss function as

where $\hat{g}$ is a gradient estimator given by any estimation algorithm, $\mathcal{G}$ is the set of all possible gradient estimators, and $L(\hat{g})$ is a loss function to evaluate the performance of the estimator $\hat{g}$. Specifically, we let the loss function of the gradient estimator $\hat{g}$ be

Methods

In this section, we present the two proposed prior-guided random gradient-free (PRGF) methods, which are variants of the ordinary random gradient-free (RGF) method. Recall that in RGF, the gradient is estimated through a set of random vectors $\{u_{i}\}_{i=1}^{q}$ as in Eq. (5) with $q$ being the total number. Directly using RGF without prior information (i.e., sampling $u_{i}$ from an uninformative distribution such as a uniform distribution) will result in poor query efficiency as demonstrated in our experiments. Therefore, we propose to improve the RGF estimator by utilizing the transfer-based prior, through either biased sampling or gradient averaging.

We denote the normalized transfer gradient of a surrogate model as $v$ such that $\|v\|_{2}=1$, and the cosine similarity between the transfer gradient and the true gradient as

We will introduce the two PRGF methods in Section 4.1 and Section 4.2, respectively. As the true value of the cosine similarity $\alpha$ is unknown, we develop a method to estimate it efficiently, which will be introduced in Section 4.3.

Rather than sampling the random vectors $\{u_{i}\}_{i=1}^{q}$ from an uninformative distribution as the ordinary RGF method, our first proposed method samples the random vectors that are biased towards the transfer gradient $v$, to fully exploit the prior information. For the gradient estimator $\hat{g}$ in Eq. (5), we further assume that the sampling distribution $\mathcal{P}$ is defined on the unit hypersphere in the $D$-dimensional input space, such that the random vectors $\{u_{i}\}_{i=1}^{q}$ drawn from $\mathcal{P}$ satisfy $\|u_{i}\|_{2}=1$. Then, we can calculate the loss of the gradient estimator $\hat{g}$ in Eq. (5) by the following theorem.

(Proof in Appendix A.1) If $f$ is differentiable at $x$, the loss of the gradient estimator $\hat{g}$ defined in Eq. (5) is

Specifically, $\mathbf{C}$ can be decomposed as $\sum_{j=1}^{D}\lambda_{j}v_{j}v_{j}^{\top}$, in which $\{\lambda_{j}\}_{j=1}^{D}$ and $\{v_{j}\}_{j=1}^{D}$ are the non-negative eigenvalues and the orthonormal eigenvectors of $\mathbf{C}$, satisfying $\sum_{j=1}^{D}\lambda_{j}=1$. In our method, we propose to sample $u_{i}$ that are biased towards the transfer gradient $v$ to exploit its prior information. So we specify an eigenvector of $\mathbf{C}$ to be $v$, and let the corresponding eigenvalue be a tunable coefficient. For the other eigenvalues, we set them to be equal since we do not have any prior knowledge about the other eigenvectors. To this end, we let

where $\lambda\in$ controls the strength of the transfer gradient that the random vectors $\{u_{i}\}_{i=1}^{q}$ are biased towards. We can easily construct a random vector with unit length while satisfying Eq. (10) as (proof in Appendix A.2)

where $\xi_{i}$ is sampled uniformly from the $D$-dimensional unit hypersphere. Hereby, the problem becomes optimizing $\lambda$ that minimizes $L(\hat{g})$. Note that when $\lambda=\frac{1}{D}$ and $\mathbf{C}=\frac{1}{D}\mathbf{I}$, such that the random vectors are drawn from the uniform distribution on the hypersphere, our method degenerates into the ordinary RGF method. When $\lambda\in[0,\frac{1}{D})$, it indicates that the transfer gradient is worse than a random vector, so we are encouraged to search in other directions by using a small $\lambda$.

To find the optimal $\lambda$ that leads to the minimum value of the loss $L(\hat{g})$, we plug Eq. (10) into Eq. (9), and obtain the closed-form solution as (proof in Appendix A.3)

where $a_{l}=\frac{1}{D+2q-2}$ and $a_{r}=\frac{2q-1}{D+2q-2}$ (recall that $\alpha$ is the cosine similarity defined in Eq. (8)).

It can be proven (in Appendix A.4) that $\lambda^{*}$ is a monotonically increasing function of $\alpha^{2}$, and a monotonically decreasing function of $q$ (when $\alpha^{2}>\frac{1}{D}$). It indicates that a larger $\alpha$ or a smaller $q$ (when the transfer gradient is not worse than a random vector) would result in a larger $\lambda^{*}$, which makes sense since we tend to rely on the transfer gradient more when (1) it approximates the true gradient better; (2) the number of queries is not enough to provide much gradient information.

We summarize the PRGF-BS algorithm in Algorithm 1. Note that when $\lambda^{*}=1$, we do not need to sample $q$ random vectors because they all equal to $v$, and we directly return the transfer gradient $v$ as the estimate of $\nabla f(x)$ (Step 3-5), which can save many queries.

2 PRGF with Gradient Averaging

In this section, we propose an alternative method to incorporate the transfer gradient $v$ based on gradient averaging. The motivation is as follows. We observe that the RGF estimator in Eq. (5) has the form $\hat{g}=\frac{1}{q}\sum_{i=1}^{q}\hat{g}_{i}$, where multiple rough estimates are averaged. Indeed, the transfer gradient itself can also be considered as an estimate of the true gradient. Thus it is reasonable to perform a weighted average of the transfer gradient and the RGF estimator.

In particular, we first obtain the ordinary RGF estimator defined in Eq. (5) with the sampling distribution $\mathcal{P}$ being the uniform distribution on the $D$-dimensional unit hypersphere, which is denoted as $\hat{g}^{U}$. Then we normalize $\hat{g}^{U}$ and perform a weighted average of the normalized transfer gradient $v$ and the normalized RGF estimator $\overline{\hat{g}^{U}}$ as

where $\mu\in$ is a balancing coefficient playing a similar role as $\lambda$ in PRGF-BS.

Given the gradient estimator in Eq. (13), we also aim at deriving the optimal $\mu$ that minimizes the loss of the estimator $L(\hat{g})$. We let $\beta=\overline{\frac{1}{q}\sum_{i=1}^{q}(u_{i}^{\top}\nabla f(x)\cdot u_{i})}^{\top}\overline{\nabla f(x)}$ be the cosine similarity between $\frac{1}{q}\sum_{i=1}^{q}(u_{i}^{\top}\nabla f(x)\cdot u_{i})$ and the true gradient $\nabla f(x)$, where $\{u_{i}\}_{i=1}^{q}$ are sampled from the uniform distribution. As discussed in Section 2.2, the RGF estimator $\hat{g}^{U}\rightarrow\frac{1}{q}\sum_{i=1}^{q}(u_{i}^{\top}\nabla f(x)\cdot u_{i})$ when $\sigma\rightarrow 0$, and consequently $\beta\rightarrow\overline{\hat{g}^{U}}^{\top}\overline{\nabla f(x)}$ as the cosine similarity between the ordinary RGF estimator and the true gradient. Recall that $\alpha=v^{\top}\overline{\nabla f(x)}$ is the cosine similarity between the transfer gradient and the true gradient. Then we have the following theorem on the loss of the gradient estimator in Eq. (13).

(Proof in Appendix A.5) If $f$ is differentiable at $x$, the loss of the gradient estimator defined in Eq. (13) is

where $\sigma$ is the sampling variance to get $\hat{g}^{U}$.

Theorem 2 indicates that we can achieve the minimum value of $L(\hat{g})$ by optimizing $\mu$. We can calculate the closed-form solution of the optimal $\mu$ as (proof in Appendix A.6)

It should be noted that we have $\mu^{*}<1$, which means that we always need to take $q$ queries to get $\hat{g}^{U}$. However, when $\mu^{*}$ is close to $1$, the improvement of using $\hat{g}=\mu^{*}v+(1-\mu^{*})\overline{\hat{g}^{U}}$ instead of directly using $v$ as the estimate is marginal. But the former requires $q$ more queries than the latter. To save queries, we use the transfer gradient $v$ as the estimate of $\nabla f(x)$ when it approximates $\nabla f(x)$ well. Thus we preset a threshold $c\in(0,1)$ such that when $\mu^{*}\geq c$, we return $v$ directly as the gradient estimate. We summarize the overall PRGF-GA algorithm in Algorithm 2.The actual implementation of PRGF-GA is slightly different from Algorithm 2, which will be explained in Appendix B.

Comparisons between PRGF-BS and PRGF-GA. Because the two proposed methods utilize the transfer-based prior in different ways, we are interested in the loss (in Eq. (7)) of the gradient estimators given by different methods, as well as the improvements over the ordinary RGF estimator and the transfer-based prior. To this end, we show the loss curves of gradient estimators given by RGF, transfer gradient, PRGF-BS, and PRGF-GA, respectively, w.r.t. different $\alpha$, in Fig. 1. PRGF-GA can get a lower loss value than PRGF-BS with a given $\alpha$, indicating that PRGF-GA can utilize the transfer-based prior better. This is also verified in the experiments.

3 Estimation of Cosine Similarity

To complete our algorithms, we need to estimate the cosine similarity $\alpha=v^{\top}\overline{\nabla f(x)}=\frac{v^{\top}\nabla f(x)}{\|\nabla f(x)\|_{2}}$, where $v$ is the normalized transfer gradient. Note that the inner product $v^{\top}\nabla f(x)$ can directly be estimated by the finite difference method as

with a small $\sigma$. Hence, the problem is reduced to estimating the norm of the gradient $\|\nabla f(x)\|_{2}$.

where $\mathbf{W}=[w_{1},...,w_{S}]$ denotes the matrix consisting of the $S$ random vectors $\{w_{s}\}_{s=1}^{S}$. Based on Eq. (18), the norm of the gradient $\|\nabla f(x)\|_{2}$ could be computed easily if both g\big{(}\mathbf{W}^{\top}\nabla f(x)\big{)} and g\big{(}\mathbf{W}^{\top}\overline{\nabla f(x)}\big{)} can be obtained.

Suppose that we utilize $S$ queries to estimate $\|\nabla f(x)\|_{2}$. We draw a set of $S$ random vectors $\{w_{s}\}_{s=1}^{S}$ independently and uniformly from the $D$-dimensional unit hypersphere, and then estimate $w_{s}^{\top}\nabla f(x)$ based on Eq. (17). Given the estimated $w_{s}^{\top}\nabla f(x)$, we can obtain g\big{(}\mathbf{W}^{\top}\nabla f(x)\big{)} directly.

By plugging Eq. (19) into Eq. (18), we can obtain the estimate of the gradient norm as

To save queries, we estimate the gradient norm periodically instead of in every iteration, since usually it does not change very fast in the optimization process.

Extensions

In this section, we extend our algorithms for incorporating the data-dependent prior and adopting multiple surrogate models to give the transfer-based prior.

The commonly used data-dependent prior is proposed to reduce the query complexity, which suggests that we can utilize the structure of the inputs to reduce the input space dimension without sacrificing much accuracy of gradient estimation. The idea of reducing the input dimension has already been adopted in several works , which has shown promise for query-efficient black-box attacks. We observe that many works restrict the adversarial perturbations to lie in a linear subspace of the input space, which allows the application of our theoretical framework. Specifically, we focus on the data-dependent prior proposed in . Below we introduce how to incorporate it into RGF, PRGF-BS, and PRGF-GA appropriately.

PRGF-BS. For PRGF with biased sampling, we consider incorporating the data-dependent prior into the algorithm along with the transfer-based prior. Similar to Eq. (10), we let one eigenvector of $\mathbf{C}$ be $v$ to exploit the transfer-based prior, and the others are given by the orthonormal basis in the subspace to exploit the data-dependent prior, as

By plugging Eq. (21) into Eq. (9), we can similarly obtain the optimal $\lambda$ as (proof in Appendix A.8)

where $A^{2}=\sum_{j=1}^{d}(v_{j}^{\top}\overline{\nabla f(x)})^{2}$, $a_{l}=\frac{A^{2}}{d+2q-2}$, and $a_{r}=\frac{A^{2}(2q-1)}{d}$. Note that $A$ is unknown, which should also be estimated. We use a method similar to the one for estimating $\alpha$, which is detailed in Appendix C.

where $\xi_{i}$ is sampled uniformly from the $d$-dimensional unit hypersphere.

The PRGF-BS algorithm with the data-dependent prior is similar to Algorithm 1. We first estimate $\alpha$ and $A$, and then calculate $\lambda^{*}$ by Eq. (A.8). If $\lambda^{*}=1$, we use the transfer gradient $v$ as the estimate. Otherwise, we sample $q$ random vectors by Eq. (23) and get the gradient estimate by Eq. (5).

PRGF-GA. We similarly incorporate the data-dependent prior into the PRGF-GA algorithm. In this case, we first get an ordinary subspace RGF estimator $\hat{g}^{S}$ instead of the ordinary RGF estimator, by sampling $\xi_{i}$ uniformly from the $d$-dimensional unit hypersphere and letting $u_{i}=\mathbf{V}\xi_{i}$. Then we normalize $\hat{g}^{S}$ and obtain the averaged gradient estimator in a similar manner to Eq. (13) as

To derive the optimal $\mu$ that minimizes the loss $L(\hat{g})$, we define $\overline{\nabla f(x)}_{T}=(\sum_{j=1}^{d}v_{j}v_{j}^{\top})\overline{\nabla f(x)}$ as the projection of $\overline{\nabla f(x)}$ onto the subspace corresponding to the data-dependent prior. We also need $A^{2}=\sum_{j=1}^{d}(v_{j}^{\top}\overline{\nabla f(x)})^{2}=\|\overline{\nabla f(x)}_{T}\|^{2}$. We let $\beta=\overline{\frac{1}{q}\sum_{i=1}^{q}(u_{i}^{\top}\nabla f(x)\cdot u_{i})}^{\top}\overline{\nabla f(x)}$ be the cosine similarity between $\frac{1}{q}\sum_{i=1}^{q}(u_{i}^{\top}\nabla f(x)\cdot u_{i})$ and the true gradient $\nabla f(x)$, in which $\{u_{i}\}_{i=1}^{q}$ lie in the subspace. We have the following theorem on the loss of the gradient estimator in Eq. (24).

(Proof in Appendix A.10) Let $\alpha_{1}=v^{\top}\overline{\nabla f(x)}_{T}$. If $f$ is differentiable at $x$ and $A^{2}>0$, the loss of the gradient estimator define in Eq. (24) is

where $\sigma$ is the sampling variance to get $\hat{g}^{S}$.

Based on Theorem 3, we calculate the optimal solution of $\mu$ by minimizing Eq. (25) as (proof in Appendix A.11)

2 Multiple Surrogate Models

The idea of utilizing multiple surrogate models has been adopted in for improving transfer-based black-box attacks. They show that the adversarial examples generated for multiple models are more likely to fool other black-box models with the increased transferability. In our algorithms, we can also utilize multiple surrogate models to extract a more effective transfer-based prior, which can consequently enhance the attack performance.

Assume that we have $M$ surrogate models. For an input $x$, we denote the gradients of these surrogate models at $x$ as $\{g^{(m)}\}_{m=1}^{M}$, where the gradients are not normalized for now. A simple approach to obtain the transfer-based prior is averaging these gradients directly, as $v=\overline{\frac{1}{M}\sum_{m=1}^{M}g^{(m)}}$. Despite the simplicity, this approach treats the gradients of surrogate models with equal importance and neglects the intrinsic similarity between different surrogate models and the target model. It has been observed that the adversarial examples are more likely to transfer within the same family of model architectures , indicating that we could design an improved transfer-based prior by leveraging more useful surrogate models/gradients.

Specifically, we denote the $M$-dimensional subspace spanned by $\{g^{(m)}\}_{m=1}^{M}$ as $\mathbf{G}$. The best approximation of the true gradient $\nabla f(x)$ that lies in $\mathbf{G}$ is the projection of $\nabla f(x)$ onto the subspace $\mathbf{G}$. Therefore, we first get an orthonormal basis of $\mathbf{G}$ by the Gram–Schmidt orthonormalization method, denoted as $\{v^{(m)}\}_{m=1}^{M}$. Then the projection of $\nabla f(x)$ onto $\mathbf{G}$ can be expressed as

in which the inner product $\nabla f(x)^{\top}v^{(m)}$ can be approximated by the finite difference method as shown in Eq. (17). Hence, we let the transfer-based prior be $v=\overline{\nabla f(x)_{\mathbf{G}}}$. With $v$ obtained by multiple surrogate gradients, we then perform PRGF-BS or PRGF-GA attacks with the same algorithms.

Experiments

Note that when counting the total number of queries in our methods, we include the additional queries of estimating the cosine similarity $\alpha$.

2 Performance of Gradient Estimation

We now conduct several ablation studies to show the performance of gradient estimation. All experiments in this section are performed on the Inception-v3 model on ImageNet.

Performance of gradient estimation. Second, we verify the effectiveness of the derived optimal $\lambda$ in PRGF-BS and $\mu$ in PRGF-GA (i.e., $\lambda^{*}$ in Eq. (12) and $\mu^{*}$ in Eq. (15)) for gradient estimation, compared with any fixed $\lambda,\mu\in$. To this end, we perform attacks against Inception-v3 using PRGF-BS with $\lambda^{*}$ or PRGF-GA with $\mu^{*}$, and at the same time calculate the cosine similarity between the estimated gradient and the true gradient. In both methods, $\lambda^{*}$ and $\mu^{*}$ are calculated using the estimated $\alpha$ instead of its true value. Meanwhile, along the PGD updates, we also use fixed $\lambda$ or $\mu$ to get gradient estimates, and calculate the corresponding cosine similarities. Note that $\lambda^{*}$ and $\mu^{*}$ do not correspond to any fixed value, since they vary during iterations.

We show the average cosine similarities of different fixed values of $\lambda$ in Fig. 2(a), and those of different fixed values of $\mu$ in Fig. 2(d). The first observation is that when a suitable value of $\lambda$ (or $\mu$) is chosen, the proposed PRGF-BS (or PRGF-GA) provides a better gradient estimate than both the ordinary RGF method with uniform distribution (when $\lambda=\frac{1}{D}\approx 0$ or $\mu=0$) and the transfer gradient (when $\lambda=1$ or $\mu=1$). The second observation is that adopting $\lambda^{*}$ (or $\mu^{*}$) brings further improvement upon any fixed $\lambda$ (or $\mu$), demonstrating the effectiveness of our theoretical analyses.

Gradient estimation across attack iterations. Finally, we aim at examining the effectiveness of the transfer-based prior across attack iterations. We show the average $\lambda^{*}$ and $\mu^{*}$ over all images w.r.t. attack iterations in Fig. 2(b) for PRGF-BS, and in Fig. 2(e) for PRGF-GA, respectively. The curves show that $\lambda^{*}$ and $\mu^{*}$ decrease along the iterations. Besides, Fig. 2(c) and Fig. 2(f) show the average cosine similarity between the transfer and the true gradients, and that between the estimated and the true gradients w.r.t. attack iterations, in PRGF-BS and PRGF-GA. All of these results demonstrate that the transfer gradient is more useful at beginning, and becomes less useful along the iterations. However, the estimated gradient in either PRGF-BS or PRGF-GA can remain a higher cosine similarity with the true gradient, which facilitates the adversarial attacks consequently. The results also corroborate that we need to use the adaptive $\lambda^{*}$ or $\mu^{*}$ in different attack iterations.

3 Results on ImageNet

Besides, we compare the attack performance with various state-of-the-art attack methods, including the natural evolution strategies (NES) , SPSA , AutoZoom , bandit optimization methods (BanditsT and BanditsTD) , and $\mathcal{N}$ATTACK . For all methods, we restrict the maximum number of queries for each image to be $10$,$000$. We report a successful attack if a method can generate an adversarial example within $10$,$000$ queries and the size of perturbation is smaller than the budget (i.e., $\epsilon=\sqrt{0.001\cdot D}$).

Table I shows the results, where we report the success rate of black-box attacks and the average/median number of queries needed to generate an adversarial example over successful attacks. We have the following observations. First, compared with the state-of-the-art attacks, the proposed methods generally lead to higher attack success rates and require much fewer queries. Second, the transfer-based prior provides useful prior information for black-box attacks since PRGF based methods perform better than the ordinary RGF method. Third, using a fixed $\lambda$ in PRGF-BS or a fixed $\mu$ in PRGF-GA cannot exceed the performance of using their optimal values, although they already lead to comparable performance with the state-of-the-art methods. Fourth, the results also prove that the data-dependent prior is orthogonal to the proposed transfer-based prior, since integrating the data-dependent prior leads to better results. Fifth, PRGF-GA requires slightly fewer queries than PRGF-BS in most cases, which are consistent with the loss curves in Fig. 1.

Here we conduct an ablation study to investigate the effectiveness of adopting different surrogate models. We use the ResNet-v2-152 model as the the surrogate model in the above experiments. We additionally consider Inception-v4 , ResNet-v2-152 + Inception-v4, and ResNet-v2-152 + Inception-v4 + Inception-ResNet-v2 as the surrogate models. Note that the latter two include multiple surrogate models. We adopt the subspace projection method introduced in Section 5.2 to get the transfer-based prior when multiple surrogate models are available. Besides, we also compare this method with the equal averaging method that directly averages the gradients of multiple models (only in the case of using ResNet-v2-152 + Inception-v4).

We show the attack performance of PRGF-BS, PRGF-GA, PRGF-BSD, and PRGF-GAD with different surrogate models in Table II. It is easy to see that adopting multiple surrogate models can significantly improve the attack success rates and reduce the number of queries. When using three surrogate models, the median number of queries is less than $100$ for all target models, which validates the effectiveness of the transfer-based prior. Besides, it can be noted that the subspace projection method performs better than the equal averaging method, because the subspace projection method can obtain the transfer-based prior which approximates the true gradient best in the subspace.

Another observation from the results is that adopting a similar surrogate model of the target model can enhance the attack performance. In particular, ResNet-v2-152 is better than Inception-v4 as the surrogate model for attacking the ResNet-50 models. On the other hand, Inception-v4 is better than ResNet-v2-152 for attacking the Inception-v3 model. It is reasonable since the gradients of models within the same family of model architectures would be similar, which has been verified in showing that the adversarial transferability is higher across similar model architectures.

Finally, we find that the data-dependent prior becomes less useful with a more powerful transfer-based prior obtained by multiple surrogate models. Specifically, PRGF-BSD and PRGF-GAD require more queries than PRGF-BS and PRGF-GA when using two or three surrogate models. The reason is as follows. For PRGF-BS and PRGF-GA without the data-dependent prior, it is more likely to obtain $\lambda^{*}=1$ or $\mu^{*}=1$ with the more effective transfer-based prior, such that we do not need to perform $q$ queries to estimate the gradient. However, in PRGF-BSD and PRGF-GAD, $\lambda^{*}$ and $\mu^{*}$ are less probable to be $1$ due to that sampling in the data-dependent subspace can also improve the gradient estimate, and therefore we need $q$ more queries to get the estimate. Although the data-dependent prior helps to give a more accurate gradient estimate, the cost of $q$ more queries degrades the efficiency of attacks.

4 Results on CIFAR-10

In this section, we show the results of black-box adversarial attacks on CIFAR-10. Similar to the experiments on ImageNet, we compare the performance of PRGF-BS and PRGF-GA with three baselines — RGF, PRGF-BS with the fixed $\lambda=0.05$, and PRGF-GA with the fixed $\mu=0.5$, as well as four other attacks — NES , SPSA , BanditsT , and $\mathcal{N}$ATTACK . Since the image resolution in CIFAR-10 is not very high (i.e., $32\times 32\times 3$), we do not adopt the data-dependent prior. We also restrict the maximum number of queries for each image to be $10,000$. Note that hundreds of queries could be sufficient due to the lower input dimension of CIFAR-10, but we adopt the maximum $10,000$ queries to make it consistent with the setting on ImageNet.

The black-box attack results of those methods against ResNet-50 , DenseNet-121 , and SENet-18 are presented in Table III. It can be seen that with the maximum number of $10,000$ queries, all attack methods can achieve near $100\%$ attack success rate. Nevertheless, our proposed methods (especially PRGF-GA) require much less queries to successfully generate adversarial examples, which demonstrates the query efficiency of our proposed methods.

Fig. 4 shows the average number of queries for successfully misleading the black-box model by reaching a desired success rate. For a given attack success rate, our methods require much less queries, indicating that they are much more query-efficient than other baseline methods.

Conclusion

In this paper, two prior-guided random gradient-free algorithms were proposed for improving black-box attacks. Our methods can utilize a transfer-based prior given by the gradient of a surrogate model through biased sampling and gradient averaging, respectively. We appropriately integrated the transfer-based prior with model queries by the derived optimal coefficient in both methods under the gradient estimation framework. Furthermore, we extended the proposed methods by incorporating the data-dependent prior and utilizing multiple surrogate models. The experimental results consistently demonstrate the effectiveness of our methods, which require much fewer queries to attack black-box models with higher success rates compared with various state-of-the-art attack methods. We released our codes at https://github.com/thu-ml/Prior-Guided-RGF.

Acknowledgments

This work was supported by the National Key Research and Development Program of China (No. 2020AAA0104304), NSFC Projects (Nos. 61620106010, 62061136001, 61621136008, 62076147, U19B2034, U1811461, U19A2081), Beijing NSF Project (No. JQ19016), Beijing Academy of Artificial Intelligence (BAAI), Tsinghua-Huawei Joint Research Program, Tsinghua Institute for Guo Qiang, Tsinghua-OPPO Joint Research Center for Future Terminal Technology and Tsinghua-China Mobile Communications Group Co., Ltd. Joint Institute.

References

Appendix A Proofs

If $f$ is differentiable at $x$, the loss of the gradient estimator $\hat{g}$ defined in Eq. (5) is

Rigorously speaking, we assume $\nabla f(x)^{\top}\mathbf{C}\nabla f(x)\neq 0$ in the statement of the theorem (and also in the proof), since when $\nabla f(x)^{\top}\mathbf{C}\nabla f(x)=0$, both the numerator and the denominator of the fraction above are zero. When $\nabla f(x)^{\top}\mathbf{C}\nabla f(x)=0$, $u_{i}^{\top}\nabla f(x)=0$ holds almost surely, which implies that $L(\hat{g})=\|\nabla f(x)\|^{2}$ regardless of the value of $\sigma$. In fact, this case will not happen almost surely. In the setting of black-box attacks, we cannot even design a $\mathbf{C}$ with trace 1 such that $\nabla f(x)^{\top}\mathbf{C}\nabla f(x)=0$ since $\nabla f(x)$ is unknown.

First, we derive $L(\hat{g})$ based on the assumption that the single estimate $\hat{g}_{i}$ in Eq. (5) is equal to $u_{i}^{\top}\nabla f(x)\cdot u_{i}$, which will hold when $f$ is locally linear.

Assume that the single estimate $\hat{g}_{i}$ in Eq. (5) is equal to $u_{i}^{\top}\nabla f(x)\cdot u_{i}$. We have

Since $\hat{g}_{i}=u_{i}^{\top}\nabla f(x)\cdot u_{i}$, and $u_{i}^{\top}u_{i}\equiv 1$, we have

Plug them into Eq. (A.2) and we complete the proof. ∎

Next, we prove that if $f$ is not locally linear, as long as it is differentiable at $x$, then by picking a sufficiently small $\sigma$, the loss tends to be that of the local linear approximation.

If $f$ is differentiable at $x$, let $L_{0}$ denote the right-hand side of Eq. (A.1), then we have

Since $f$ is differentiable at $x$, we have

By combining the two lemmas above, our proof for Theorem 1 is complete. ∎

A.2 Proof of Eq. (11)

Suppose that $v$ is a fixed random vector and $\|v\|_{2}=1$. Let the $D$-dimensional random vector $u$ be

where $\xi$ is sampled uniformly from the unit hypersphere. We need to prove that

A.3 Proof of Eq. (12)

Let $\alpha=v^{\top}\overline{\nabla f(x)}$. Suppose that $D\geq 2$, $q\geq 1$. After plugging Eq. (10) into Eq. (9), the optimal $\lambda$ is given by

After plugging Eq. (10) into Eq. (9), we have

To minimize $L(\lambda)$, we should maximize

Note that $F(\lambda)$ is a quadratic rational function w.r.t. $\lambda$.

Since we optimize $\lambda$ in a closed interval $$, checking$\lambda=0$,$\lambda=1$and the stationary points (i.e.,$F^{\prime}(\lambda)=0$) would suffice. By solving$F^{\prime}(\lambda)=0$, we have at most two solutions:

where $\lambda_{1}$ or $\lambda_{2}$ is the solution if and only if the denominator is not 0. Given $\alpha^{2}\leq 1$ and $D\geq 2$, $\lambda_{2}\notin(0,1)$, so we only need to consider $\lambda_{1}$.

First, we figure out when $\lambda_{1}\in(0,1)$. We can verify that $\lambda_{1}=1$ when $\alpha^{2}=0$ and $\lambda_{1}=0$ when $\alpha^{2}=1$. Suppose that $\alpha^{2}\in(0,1)$. Let $J$ denote the numerator in Eq. (A.8) and $K$ denote the denominator. We have that when $\alpha^{2}>\frac{1}{D+2q-2}$, $J>0$; otherwise $J\leq 0$. We also have that when $\alpha^{2}<\frac{2q-1}{D+2q-2}$, $J<K$; otherwise $J\geq K$. Note that $J/K\in(0,1)$ if and only if $0<J<K$ or $0>J>K$. Hence, $\lambda_{1}\in(0,1)$ if and only if $\frac{1}{D+2q-2}<\alpha^{2}<\frac{2q-1}{D+2q-2}$.

Case 1: $\lambda_{1}\notin(0,1)$. Then it suffices to compare $F(0)$ with $F(1)$. We have

Hence, $F(0)\geq F(1)$ if and only if $\alpha^{2}\leq\frac{q}{D+2q-2}$. It means that if $\alpha^{2}\geq\frac{2q-1}{D+2q-2}$, then $\lambda^{*}=1$; if $\alpha^{2}\leq\frac{1}{D+2q-2}$, then $\lambda^{*}=0$.

Case 2: $\lambda_{1}\in(0,1)$. After plugging Eq. (A.8) into Eq. (A.7), we have

Now we prove that $F(\lambda_{1})\geq F(0)$ and $F(\lambda_{1})\geq F(1)$. Since when $0<\lambda<1$, both the numerator and the denominator in Eq. (A.7) is positive, we have $F(\lambda)>0$, $\forall\lambda\in(0,1)$. Since the numerator in Eq. (A.9) is non-negative and $F(\lambda_{1})>0$, we know that the denominator in Eq. (A.9) is positive. Hence, we have

Hence in this case $\lambda^{*}=\lambda_{1}$.

We will prove that $\lambda^{*}$ is a monotonically increasing function of $\alpha^{2}$, and a monotonically decreasing function of $q$ (when $\alpha^{2}>\frac{1}{D}$).

To find the monotonicity w.r.t. $\alpha^{2}$, note that $\lambda^{*}=0$ if $\alpha^{2}\leq\frac{1}{D+2q-2}$ and $\lambda^{*}=1$ when $\alpha^{2}\geq\frac{2q-1}{D+2q-2}$. When $\frac{1}{D+2q-2}<\alpha^{2}<\frac{2q-1}{D+2q-2}$, we have

When $\alpha^{2}<\frac{1}{D}$ or $\alpha^{2}>\frac{1}{D}$, a larger $\alpha^{2}$ leads to larger values of both $\alpha^{2}D(D+2q-2)$ and $-2\frac{(D-1)(q-1)}{\alpha^{2}D-1}$, and consequently leads to a larger $\lambda^{*}$. Meanwhile, by the argument in the proof of Eq. (12), when $\frac{1}{D+2q-2}<\alpha^{2}<\frac{2q-1}{D+2q-2}$, the denominator of Eq. (A.8) is positive, hence $\alpha^{4}D(D+2q-2)-2\alpha^{2}Dq+1<0$. By Eq. (A.10), when $\alpha^{2}<\frac{1}{D}$, $\lambda^{*}<\frac{1}{D}$; when $\alpha^{2}=\frac{1}{D}$, $\lambda^{*}=\frac{1}{D}$; when $\alpha^{2}>\frac{1}{D}$, $\lambda^{*}>\frac{1}{D}$. We conclude that $\lambda^{*}$ is a monotonically increasing function of $\alpha^{2}$.

To find the monotonicity w.r.t. $q$ when $\alpha^{2}>\frac{1}{D}$, Eq. (12) tells us that when $q\leq\frac{\alpha^{2}(D-2)+1}{2(1-\alpha^{2})}$, $\lambda^{*}=1$; else, $0<\lambda^{*}<1$. In the latter case, we rewrite Eq. (A.10) as

We have $(\alpha^{2}D-1)(D-1)>0$, and as explained before, the denominator is positive for any $q$ such that $0<\lambda^{*}<1$. Hence, when $\alpha^{2}>\frac{1}{D}$, $\lambda^{*}$ is a monotonically decreasing function of $q$. ∎

A.5 Proof of Theorem 2

If $f$ is differentiable at $x$, the loss of the gradient estimator defined in Eq. (13) is

where $\sigma$ is the sampling variance to get $\hat{g}^{U}$.

As in Eq. (5), $\hat{g}^{U}=\frac{1}{q}\sum_{i=1}^{q}\hat{g}_{i}^{U}$ and $\hat{g}_{i}^{U}=\frac{f(x+\sigma u_{i})-f(x)}{\sigma}\cdot u_{i}$, where $u_{i}$ is sampled from the uniform distribution on the $D$-dimensional unit hypersphere. First, we derive $L(\hat{g})$ based on the assumption that $\hat{g}_{i}^{U}$ is equal to $u_{i}^{\top}\nabla f(x)\cdot u_{i}$, which will hold when $f$ is locally linear.

Assume that $\hat{g}^{U}=\frac{1}{q}\sum_{i=1}^{q}(u_{i}^{\top}\nabla f(x)\cdot u_{i})$ (then $\beta=\overline{\hat{g}^{U}}^{\top}\overline{\nabla f(x)}$). We have

Together with $v^{\top}\nabla f(x)=\alpha\|\nabla f(x)\|_{2}$ and $\|v\|_{2}=1$, we have

Next, we prove that if $f$ is not locally linear, as long as it is differentiable at $x$, then by picking a sufficiently small $\sigma$, the loss tends to be that of the local linear approximation. Here, we redefine the notations as follows. We make the dependency of $\hat{g}^{U}$ on $\sigma$ explicit, i.e., we use $\hat{g}^{U}_{\sigma}$ to denote it. Meanwhile, we define $\hat{g}^{U}_{0}\triangleq\frac{1}{q}\sum_{i=1}^{q}(u_{i}^{\top}\nabla f(x)\cdot u_{i})$ as the RGF estimator under the local linear approximation. We define $\hat{g}_{\sigma}=\mu v+(1-\mu)\overline{\hat{g}^{U}_{\sigma}}$ and $\hat{g}_{0}=\mu v+(1-\mu)\overline{\hat{g}^{U}_{0}}$. Then we have the following lemma.

By combining the two lemmas above, our proof for Theorem 2 is complete. ∎

A.6 Proof of Eq. (15)

Note that $F(\mu)$ is a quadratic rational function w.r.t. $\mu$.

Since we optimize $\mu$ in a closed interval $$, checking$\mu=0$,$\mu=1$and the stationary points (i.e.$F^{\prime}(\mu)=0$) would suffice. By solving$F^{\prime}(\mu)=0$, we have two solutions:

where $\mu_{2}$ is the solution only when $\alpha\neq\beta$. Then we have

A.7 Proof of Eq. (16)

Let $\beta=\overline{\frac{1}{q}\sum_{i=1}^{q}(u_{i}^{\top}\nabla f(x)\cdot u_{i})}^{\top}\overline{\nabla f(x)}$, we need to prove

where $D$ and $q$ are the input dimension and the number of queries to get $\hat{g}^{U}$, respectively.

Here, the first equality is because that $\nabla f(x)^{\top}\hat{g}_{0}^{U}=\frac{1}{q}\sum_{i=1}^{q}(u_{i}^{\top}\nabla f(x))^{2}\geq 0$ and the second equality is because that we have $\min_{b}\|\overline{\nabla f(x)}-b\hat{g}_{0}^{U}\|^{2}=1-(\overline{\nabla f(x)}^{\top}\overline{\hat{g}_{0}^{U}})^{2}=1-\beta^{2}$. Intuitively, the two approximations work well because that the variances of $\beta$ and $\|\hat{g}_{0}^{U}\|_{2}$ are relatively small.

A.8 Proof of Eq. (22)

Let $\alpha=v^{\top}\overline{\nabla f(x)}$, $A^{2}=\sum_{j=1}^{d}(v_{j}^{\top}\overline{\nabla f(x)})^{2}$. Suppose that $\alpha^{2}\leq 1$, $d\geq 1$, $q\geq 1$. After plugging Eq. (21) into Eq. (9), the optimal $\lambda$ is given by

The proof is very similar to that in Appendix A.3. After plugging Eq. (21) into Eq. (9), we have

To minimize $L(\lambda)$, we should maximize

Note that $F(\lambda)$ is a quadratic rational function w.r.t. $\lambda$.

Since we optimize $\lambda$ in a closed interval $$, checking$\lambda=0$,$\lambda=1$and the stationary points (i.e.,$F^{\prime}(\lambda)=0$) would suffice. By solving$F^{\prime}(\lambda)=0$, we have at most two solutions:

where $\lambda_{1}$ or $\lambda_{2}$ is the solution if and only if the denominator is not 0. $\lambda_{2}\notin(0,1)$, so we only need to consider $\lambda_{1}$.

First, we figure out when $\lambda_{1}\in(0,1)$. We can verify that $\lambda_{1}=1$ when $\alpha^{2}=0$ and $\lambda_{1}=0$ when $A^{2}=0$. Suppose $\alpha^{2}\neq 0$ and $A^{2}\neq 0$. Let $J$ denote the numerator in Eq. (A.13) and $K$ denote the denominator. We have that when $\alpha^{2}>\frac{A^{2}}{d+2q-2}$, $J>0$; otherwise $J\leq 0$. We also have that when $\alpha^{2}<\frac{A^{2}(2q-1)}{d}$, $J<K$; otherwise $J\geq K$. Note that $J/K\in(0,1)$ if and only if $0<J<K$ or $0>J>K$. Hence, $\lambda_{1}\in(0,1)$ if and only if $\frac{A^{2}}{d+2q-2}<\alpha^{2}<\frac{A^{2}(2q-1)}{d}$.

Case 1: $\lambda_{1}\notin(0,1)$. Then it suffices to compare $F(0)$ and $F(1)$. We have

Hence, $F(0)\geq F(1)$ if and only if $\alpha^{2}\leq\frac{A^{2}q}{d+q-1}$. It means that if $\alpha^{2}\geq\frac{A^{2}(2q-1)}{d}$, then $\lambda^{*}=1$; if $\alpha^{2}\leq\frac{A^{2}}{d+2q-2}$, then $\lambda^{*}=0$.

Case 2: $\lambda_{1}\in(0,1)$. After plugging Eq. (A.13) into Eq. (A.12), we have

Now we prove that $F(\lambda_{1})\geq F(0)$ and $F(\lambda_{1})\geq F(1)$. Since when $0<\lambda<1$, both the numerator and the denominator in Eq. (A.12) is positive, we have $F(\lambda)>0$, $\forall\lambda\in(0,1)$. Since the numerator in Eq. (A.14) is non-negative, and $F(\lambda_{1})>0$, we know that the denominator in Eq. (A.14) is positive. Hence, we have

Hence in this case $\lambda^{*}=\lambda_{1}$.

A.9 Explanation on Eq. (23)

To avoid approximation, one can choose the subspace as spanned by $\{v_{1}^{\prime},v_{2},...,v_{d}\}$ instead of $\{v_{1},v_{2},...,v_{d}\}$ to ensure that $v$ is orthogonal to the subspace. Then $u$ can be sampled as

where $\mathbf{V}^{\prime}=[v_{1}^{\prime},v_{2},...,v_{d}]$ and $\xi$ is sampled uniformly from the $d$-dimensional unit hypersphere. Note that here the optimal $\lambda$ is calculated using $A^{\prime 2}=v_{1}^{\prime\top}\overline{\nabla f(x)}+\sum_{j=2}^{d}(v_{j}^{\top}\overline{\nabla f(x)})^{2}$. However, in practice, it is not convenient to make the subspace dependent on $v$, and the computational complexity is high to construct an orthonormal basis with one vector ($v_{1}^{\prime}$) specified.

A.10 Proof of Theorem 3

Let $\alpha_{1}=v^{\top}\overline{\nabla f(x)}_{T}$. If $f$ is differentiable at $x$ and $A^{2}>0$, the loss of the gradient estimator define in Eq. (24) is

where $\sigma$ is the sampling variance to get $\hat{g}^{S}$.

The rest of the proof is the same as that of Theorem 2. ∎

A.11 Proof of Eq. (26)

The proof is very similar to that in Appendix A.6. To minimize $L(\mu)$, we should maximize

Note that $F(\mu)$ is a quadratic rational function w.r.t. $\mu$.

Since we optimize $\mu$ in a closed interval $$, checking$\mu=0$,$\mu=1$and the stationary points (i.e.$F^{\prime}(\mu)=0$) would suffice. By solving$F^{\prime}(\mu)=0$, we have two solutions:

where $\mu_{2}$ is the solution only when $\alpha\neq\beta$. Then we have

Let $\beta=\overline{\frac{1}{q}\sum_{i=1}^{q}(u_{i}^{\top}\nabla f(x)\cdot u_{i})}^{\top}\overline{\nabla f(x)}$, in which $\{u_{i}\}_{i=1}^{q}$ lie in the subspace, we further need to prove

where $d$ is the subspace dimension, $q$ is the number of queries to get $\hat{g}^{S}$, and $A^{2}=\sum_{i=1}^{d}(v_{i}^{\top}\overline{\nabla f(x)})^{2}$.

Appendix B Actual Implementation of PRGF-GA

Note that in the PRGF-GA algorithm, the optimal coefficient $\mu^{*}$ in Eq. (15) is calculated by minimizing the loss $L(\hat{g})$ of the gradient estimator defined as $\hat{g}=\mu v+(1-\mu)\overline{\hat{g}^{U}}$, where $v$ is the normalized transfer gradient and $\hat{g}^{U}$ is the ordinary RGF estimator. Since the loss $L(\hat{g})$ is a deterministic scalar whose computation requires taking expectation w.r.t. the randomness of $\hat{g}^{U}$, $\mu^{*}$ is a precomputed scalar which does not depend on the value of $\hat{g}^{U}$. However, since $\mu$ is not concerned with the estimation process to get $\hat{g}^{U}$, we can actually obtain the value of $\hat{g}^{U}$ first and let $\mu$ depend on it, which could be beneficial when $\hat{g}^{U}$ exhibits high variance.

To this end, we need to calculate $\mu$ that leads to the best gradient estimator given the values of $v$ and $\hat{g}^{U}$. We first assume that $v$ and $\overline{\hat{g}^{U}}$ are almost orthogonal with high probability, which is true in a high dimensional input space. (Without this assumption, we could perform Gram–Schmidt orthonormalization.) The problem is to find a vector in the subspace spanned by $v$ and $\overline{\hat{g}^{U}}$ that approximate the true gradient $\nabla f(x)$ best. This can be simply accomplished by projecting $\nabla f(x)$ onto the subspace, as

Therefore, the optimal $\mu$ can be expressed as

$v^{\top}\nabla f(x)$ and $\overline{\hat{g}^{U}}^{\top}\nabla f(x)$ can be estimated by the finite difference method shown in Eq. (17). We summarize the actual implementation of PRGF-GA in Algorithm 3.

Appendix C Estimation of A𝐴A

Suppose that the subspace is spanned by a set of orthonormal vectors $\{v_{1},...,v_{d}\}$. Now we want to estimate

where $h(x)=\sum_{j=1}^{d}v_{j}^{\top}\nabla f(x)\cdot v_{j}$ is the projection of $\nabla f(x)$ to the subspace. We can estimate $\|\nabla f(x)\|_{2}^{2}$ using the method introduced in Section 4.3. Here, we introduce the method to estimate $\|h(x)\|_{2}^{2}$.

With $g(x_{1},...,x_{S})=\frac{1}{S}\sum_{s=1}^{S}x_{s}^{2}$, we have

Appendix D Additional Experiments