ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization

Introduction

The development of gradient-free optimization methods has become increasingly important to solve many machine learning problems in which explicit expressions of the gradients are expensive or infeasible to obtain . Zeroth-Order (ZO) optimization methods, one type of gradient-free optimization methods, mimic first-order (FO) methods but approximate the full gradient (or stochastic gradient) through random gradient estimates, given by the difference of function values at random query points . Compared to Bayesian optimization, derivative-free trust region methods, genetic algorithms and other types of gradient-free methods , ZO optimization has two main advantages: a) ease of implementation, via slight modification of commonly-used gradient-based algorithms, and b) comparable convergence rates to first-order algorithms.

Due to the stochastic nature of ZO optimization, which arises from both data sampling and random gradient estimation, existing ZO methods suffer from large variance of the noisy gradient compared to FO stochastic methods . In practice, this causes poor convergence performance and/or function query efficiency. To partially mitigate these issues, ZO sign-based SGD (ZO-signSGD) was proposed by with the rationale that taking the sign of random gradient estimates (i.e., normalizing gradient estimates elementwise) as the descent direction improves the robustness of gradient estimators to stochastic noise. Although ZO-signSGD has faster convergence speed than many existing ZO algorithms, it is only guaranteed to converge to a neighborhood of a solution. In the FO setting, taking the sign of a stochastic gradient as the descent direction gives rise to signSGD . The use of sign of stochastic gradients also appears in adaptive momentum methods (AdaMM) such as Adam , RMSProp , AMSGrad , Padam , and AdaFom . Indeed, it has been suggested by that AdaMM enjoy dual advantages of sign descent and variance adaption.

Considering the motivation of ZO-signSGD and the success of AdaMM in FO optimization, one question arises: Can we generalize AdaMM to the ZO regime? To answer this question, we develop the zeroth-order adaptive momentum method (ZO-AdaMM) and analyze its convergence properties in both convex and nonconvex settings for constrained optimization.

Theoretically, for both convex and nonconvex optimization, we show that ZO-AdaMM is roughly a factor of $O(\sqrt{d})$ worse than that of the FO AdaMM algorithm, where $d$ is the number of optimization variables. We also show that the Euclidean projection based AdaMM-type methods could suffer non-convergence issues for constrained optimization. This highlights the necessity of Mahalanobis distance based projection. And we establish the Mahalanobis distance based convergence analysis, which makes the first step toward understanding adaptive learning rate methods for nonconvex constrained optimization.

Practically, we formalize the experimental comparison of ZO-AdaMM with $6$ state-of-the-art ZO algorithms in the application of black-box adversarial attacks to generate both per-image and universal adversarial perturbations. Our proposal could provide an experimental benchmark for future studies on ZO optimization. Code to reproduce experiments is released at the anonymous link https://github.com/KaidiXu/ZO-AdaMM.

Related work

Many types of ZO algorithms have been developed, and their convergence rates have been rigorously studied under different problem settings. We highlight some recent works as below. For unconstrained stochastic optimization, ZO stochastic gradient descent (ZO-SGD) and ZO stochastic coordinate descent (ZO-SCD) were proposed, which have $O(\sqrt{d}/\sqrt{T})$ convergence rate, where $T$ is the number of iterations. Compared to FO stochastic algorithms, ZO optimization suffers a slowdown dependent on the variable dimension $d$, e.g., $O(\sqrt{d})$ for ZO-SGD and ZO-SCD. In , the tightness of the dimension-dependent factor $O(\sqrt{d})$ has been proved in the framework of ZO stochastic mirror descent (ZO-SMD). In order to further improve the iteration complexity of ZO algorithms, the technique of variance reduction was applied to ZO-SGD and ZO-SCD, leading to ZO stochastic variance reduced algorithms with an improved convergence rate in $T$, namely, $O(d/T)$ . This improvement is aligned with ZO gradient descent (ZO-GD) for deterministic nonconvex programming . Moreover, ZO versions of proximal SGD (ProxSGD) , Frank-Wolfe (FW) , and online alternating direction method of multipliers (OADMM) have been developed for constrained optimization. Aside from the recent works on ZO algorithms mentioned before, there is rich literature in derivative-free optimization (DFO). Traditional DFO methods can be classified into direct search-based methods and model-based methods. Both the two type of methods are mostly iterative methods. The difference is that direct search-based methods refines its search direction based on the queried function values directly, while a model-based method builds a model that approximates the function to be optimized and updates the search direction based on the model. Representative methods of developed in DFO literature include NOMAD , PSWarm , Cobyla , and BOBYQA . More comprehensive discussion on DFO methods can be found in .

Preliminaries: Gradient Estimation via ZO Oracle

The ZO gradient estimate of a function $f$ is constructed by the forward difference of two function values at a random unit direction:

where $\mathbf{u}$ is a random vector drawn uniformly from the sphere of a unit ball, and $\mu>0$ is a small step size, known as the smoothing parameter. In many existing work such as , the random direction vector $\mathbf{u}$ was drawn from the standard Gaussian distribution. Here the use of uniform distribution ensures that the ZO gradient estimate (1) is defined in a bounded space rather than the whole real space required for Gaussian. As will be evident later, the boundedness of random gradient estimates is one of important conditions in the convergence analysis of ZO-AdaMM.

The rationale behind the ZO gradient estimate (1) is that although it is a biased approximation to the true gradient of $f$, it is unbiased to the gradient of the randomized smoothing version of $f$ with parameter $\mu$ , i.e.,

AdaMM from First to Zeroth Order

Consider a stochastic optimization problem of the generic form

We specify the algorithmic framework of AdaMM by AMSGrad , a modified version of Adam with convergence guarantees for both convex and nonconvex optimization. In the algorithm, the descent direction $\mathbf{m}_{t}$ is given by an exponential moving average of the past gradients. The learning rate $r_{t}$ is adaptively penalized by a square root of exponential moving averages of squared past gradients. It has been proved in that AdaMM can reach $O({1}/{\sqrt{T}})$In the paper, we could omit $\log(T)$ in Big $O$ notation. convergence rate. Here we omit its possible dependency on $d$ for simplicity, but more accurate analysis will be provided later in Section 4 and 5.

Here we assume that $\mathbf{m}_{0}=\mathbf{0}$, $\mathbf{v}_{0}=\mathbf{0}$ and $0^{0}=1$ by convention, and let $\hat{\mathbf{g}}_{t}=\hat{\nabla}f_{t}(\mathbf{x}_{t})$ by (1) with $f_{t}(\mathbf{x}_{t})\mathrel{\mathop{:}}=f(\mathbf{x}_{t};\boldsymbol{\xi}_{t})$.

Why is ZO-AdaMM difficult to analyze?

The convergence analysis of ZO-AdaMM becomes significantly more challenging than existing ZO methods due to the involved coupling among stochastic sampling, ZO gradinet estimation, momentum, adaptive learning rate, and projection operation. In particular, the use of Mahalanobis distance in projection step plays a key role on convergence guarantees. And the conventional variance bound on ZO gradient estimates is insufficient to analyze the convergence of ZO-AdaMM due to the use of adaptive learning rate. In the next sections, we will carefully study the convergence of ZO-AdaMM under different settings.

Convergence Analysis of ZO-AdaMM for Nonconvex Optimization

In this section, we begin by providing a deep understanding on the importance of Mahalanobis distance used in ZO-AdaMM (Algorithm 1), and then introduce the Mahalanobis distance based convergence analysis for both unconstrained and constrained nonconvex optimization. Our analysis makes the first step toward understanding adaptive learning rate methods for nonconvex constrained optimization. Throughout the section, we make the following assumptions.

A1: $f_{t}(\cdot)\mathrel{\mathop{:}}=f(\cdot;\boldsymbol{\xi}_{t})$ has $L_{g}$-Lipschitz continuous gradient, where $L_{g}>0$.

A2: $f_{t}$ has $\eta$-bounded stochastic gradient $\|\nabla f_{t}(\mathbf{x})\|_{\infty}\leq\eta$.

then Algorithm 1, initialized by $\mathbf{x}=[0.5,0.5]^{T}$, using the Euclidean projection $\Pi_{\mathcal{X}}(\cdot)$ converges to a fixed point $[0.5,0.5]^{T}$ rather than a stationary point of (6).

Proof: The proof investigates a special case of Algorithm 1, projected signSGD; See Appendix 2.1.

Proposition 1 indicates that replacing the Mahalanobis distance based projection in Algorithm 1 with Euclidean projection will lead to a divergent algorithm, highlighting the importance of using Mahalanobis distance. However, the use of Mahalanobis distance based projection complicates the convergence analysis, especially in constrained optimization. Accordingly, we define a Mahalanobis based convergence measure that can simplify the analysis and can be converted into the traditional convergence measure.

Let $\mathbf{x}^{+}=\mathbf{x}_{t+1}$, $\mathbf{x}^{-}=\mathbf{x}_{t}$, $\mathbf{g}=\mathbf{m}_{t}$, $\omega=\alpha_{t}$ and $\mathbf{H}=\hat{\mathbf{V}}_{t}^{1/2}$, the projection step of Algorithm 1 can be written in the generic form

The gradient mapping $P_{\mathcal{X},\mathbf{H}}(\mathbf{x}^{-},\mathbf{g},\omega)$ yields a natural interpretation: a projected version of $\mathbf{g}$ at the point $\mathbf{x}^{-}$ given the learning rate $\omega$, yielding $\mathbf{x}^{+}=\mathbf{x}^{-}-\omega P_{\mathcal{X},\mathbf{H}}(\mathbf{x}^{-1},\mathbf{g},\omega)$. We note that different from , the gradient mapping in (8) is defined on the projection under the Mahalanobis distance $D_{\mathbf{H}}(\cdot,\cdot)$ rather than the Euclidean distance.

With the aid of (8), we propose the Mahalanobis distance based convergence measure for ZO-AdaMM:

which corresponds to the squared Euclidean norm of gradient in a linearly transformed coordinate system $\mathbf{y}_{t}=\hat{\mathbf{V}}_{t}^{1/4}\mathbf{x}_{t}$. As will be evident later, the measure (10) can be transformed to the conventional measure $\|\nabla f(\mathbf{x}_{t})\|^{2}$ for unconstrained optimization.

2 Unconstrained nonconvex optimization

We next demonstrate the convergence analysis of ZO-AdaMM for unconstrained nonconvex optimization. In Proposition 2, we begin by exploring the relationship between the convergence measure (10) and ZO gradient estimates; See Appendix 2.2 for proof.

where $\mathbf{x}_{R}$ is picked uniformly randomly from $\{\mathbf{x}_{t}\}_{t=1}^{T}$, and $\hat{\mathbf{g}}_{t}=\hat{\nabla}f_{t}(\mathbf{x}_{t})$ by (1).

A3: $f_{t}$ is $L_{c}$-Lipschitz continuous.

Under A3, $\max\{d,T\}\geq 3$, and given $\delta\in(0,1)$, then with probability at least $1-\delta$,

Suppose that A1 and A3 hold. Given parameter settings in Proposition 2 and 3, then with probability at least $1-1/(T\sqrt{d})$, ZO-AdaMM yields

3 Constrained nonconvex optimization

To analyze ZO-AdaMM in a general constrained case, one needs to handle the coupling effects from all three factors: momentum, adaptive learning rate, and projection operation. Here we focus on addressing the coupling issue in the last two factors, which yields our results on ZO-AdaMM at $\beta_{1,t}=0$. This is equivalent to the ZO version of RMSProp with Reddi’s convergence fix in . When the momentum factor comes into play, the scenario becomes much more complicated. We leave the answer to the general case $\beta_{1,t}\neq 0$ for future research. Even for SGD with momentum, we are not aware of any successful convergence analysis for stochastic constrained nonconvex optimization.

It is known from SGD that the presence of projection induces a stochastic bias (independent of iteration number $T$) for constrained nonconvex optimization. In Theorem 2, we show that the same challenge holds for ZO-AdaMM. Thus, one has to adopt the variance reduced gradient estimator, which induces higher querying complexity than the estimator (1); See Appendix 2.5 for proof.

Suppose that A1-A2 hold, $\hat{\mathbf{v}}_{0}^{1/2}\geq c\mathbf{1}$, $f_{\mu}(\mathbf{x}_{1})-\min_{\mathbf{x}}f_{\mu}(\mathbf{x})\leq D_{f}$, $\alpha_{t}=\alpha\leq\frac{c}{L_{g}}$, $\mu=\frac{1}{\sqrt{Td}}$, and $\beta_{1,t}=0$ in Algorithm 1, then the convergence rate of ZO-AdaMM under (9) satisfies

where $\mathbf{x}_{R}$ is picked uniformly randomly from $\{\mathbf{x}_{t}\}_{t=1}^{T}$, $\mathcal{G}(\mathbf{x})$ has been defined in (9), and $f_{\mu}$ is the smoothing function of $f$ defined in (2).

where $\mathcal{I}_{t}$ is a mini-batch containing $b$ stocahstic samples at time $t$, and $\{\mathbf{u}_{i,t}\}_{i=1}^{q}$ are $q$ random direction vectors at time $t$. We present the variance of (15) in Lemma 1, whose proof is induced from [14, Proposition 2] by using $\|\nabla f_{t}\|_{2}^{2}\leq d\|\nabla f_{t}\|_{\infty}^{2}=d\eta^{2}$ in A2.

Suppose that A1-A2 hold, then for $\mu\leq 1/\sqrt{d}$, the variance of (15) yields

Extended Analysis of ZO-AdaMM

Suppose that $\alpha_{t}=\alpha/\sqrt{t}$, $\beta_{1,t}=\beta_{1}/t$ with $\beta_{1,1}=\beta_{1}$, $\beta_{1},\beta_{2}\in[0,1)$, $\gamma\mathrel{\mathop{:}}=\beta_{1}/\sqrt{\beta_{2}}<1$ and $\mathcal{X}$ has bounded diameter $D_{\infty}$, then ZO-AdaMM for convex optimization yields

where $f_{t,\mu}$ denotes the smoothing function of $f$ defined by (2), $\hat{v}_{t,i}$ denotes the $i$th element of the vector $\hat{\mathbf{v}}_{t}$ defined in Algorithm 1, and $\hat{\mathbf{g}}_{1:T,i}\mathrel{\mathop{:}}=[\hat{g}_{1,i},\ldots,\hat{g}_{T,i}]^{\top}$.

We remark that Proposition 4 would reduce to [18, Theorem 4] by replacing ZO gradient estimates $\hat{\mathbf{g}}_{1:T,i}$ and $\hat{v}_{t,i}$ with FO gradients ${\mathbf{g}}_{1:T}$ and $v_{t}$. However, it was recently shown by that the proof of [18, Theorem 4] is problematic. To address the proof issue, in Proposition 4 we present a simpler fix than [39, Theorem 4.1] and show that the conclusion of [18, Theorem 4] keeps correct. In the FO setting, the rate of AdaMM under A2 for constrained convex optimization is given by $O(d/\sqrt{T})$ [19, Corollary 4.4]. Here A2 provides the direct $\eta$-upper bound on $|g_{t,i}|$ and $\hat{v}_{t,i}^{1/2}$, and we consider worst-case rate analysis without imposing extra assumptions like sparse gradientsThe work showed the lack of sparsity in gradients while generating adversarial examples.. In the ZO setting, we need further bound $|\hat{g}_{t,i}|$ and $\hat{v}_{t,i}$ and link $R_{T,\mu}$ to $R_{T}$, where the former is achieved by Proposition 3 and the latter is achieved by the relationship between $f_{t}$ and its smoothing function $f_{t,\mu}$ shown in Lemma A1-(a), yielding $f_{t}(\mathbf{x}_{t})-f_{t}(\mathbf{x}^{*})\leq f_{t,\mu}(\mathbf{x}_{t})-f_{t,\mu}(\mathbf{x}^{*})+2\mu L_{c}$. Thus, given $\mu\leq d/\sqrt{T}$ and assuming conditions in Proposition 3 hold, then the rate of ZO-AdaMM becomes $R_{T}\leq 2\mu L_{c}+R_{T,\mu}=O(d^{1.5}/\sqrt{T})$, which is $O(\sqrt{d})$ worse than the AdaMM.

Comparison with other ZO methods

Since the existing convergence analysis for different ZO methods is built on different problem settings and assumptions. The direct comparison over the convergence rates might not be fair enough. Thus, in Table 1 we compare ZO-AdaMM with others ZO methods from $4$ perspectives: a) the type of gradient estimator, b) the setting of smoothing parameter $\mu$, c) convergence rate, and d) function query complexity.

Table 1 shows that for unconstrained nonconvex optimization, the convergence of ZO-AdaMM achieves worse dependency on $d$ than ZO-SGD , ZO-SCD and ZO-signSGD . However, it has milder choice of $\mu$ than ZO-SGD, less query complexity than ZO-SCD, and no $T$-independent convergence bias compared to ZO-signSGD. Also, for constrained nonconvex optimization, ZO-AdaMM yields the similar rate to ZO-ProxSGD , which also implies ZO projected SGD (ZO-PSGD). For constrained convex optimization, the rate of ZO-AdaMM is $O(d)$ worse than ZO-SMD but ours has the significantly improved dimension-dependency in $\mu$. We also highlight that at the first glance, ZO-AdaMM has a worse $d$-dependency (regardless of choice of $\mu$) than ZO-SGD. However, even in the FO setting, AdaMM has an extra $O(\sqrt{d})$ dependency in the worst case due to the effect of (coordinate-wise) gradient normalization when bounding the distance of two consecutive updates. Thus, in addition to comparing with different ZO methods, Table 1 also summarizes the convergence performance of FO AdaMM. Note that our rate yields $O(\sqrt{d})$ slowdown compared to FO AdaMM though bounding ZO gradient estimate norm requires stricter assumption.

Applications to Black-Box Adversarial Attacks

In this section, we demonstrate the effectiveness of ZO-AdaMM by experiments on generating black-box adversarial examples. Our experiments will be performed on Inception V3 using ImageNet . Here we focus on two types of black-box adversarial attacks: per-image adversarial perturbation and universal adversarial perturbation against multiple images . For each type of attack, we allow both constrained and unconstrained optimization problem settings. We compare our propos ed ZO-AdaMM method with $6$ existing ZO algorithms: ZO-SGD, ZO-SCD and ZO-signSGD for unconstrained optimization, and ZO-PSGD, ZO-SMD and ZO-NES for constrained optimization. The first $5$ methods have been summarized in Table 1, and ZO-NES refers to the black-box attack generation method in , which applies a projected version of ZO-signSGD using natural evolution strategy (NES) based random gradient estimator. In our experiments, every method takes the same number of queries per iteration. Accordingly, the total query complexity is consistent with the number of iterations. We refer to Appendix 4 for details on experiment setups.

Universal adversarial perturbation

Conclusion

In this paper, we propose ZO-AdaMM, the first effort to integrate adaptive momentum methods with ZO optimization. In theory, we show that ZO-AdaMM has convergence guarantees for both convex and nonconvex constrained optimization. Compared with (first-order) AdaMM, it suffers a slowdown factor of $O(\sqrt{d})$. Particularly, we establish a new Mahalanobis distance based convergence measure whose necessity and importance are provided in characterizing the convergence behavior of ZO-AdaMM on nonconvex constrained problems. To demonstrate the utility of the algorithm, we show the superior performance of ZO-AdaMM for designing adversarial examples from black-box neural networks. Compared with $6$ state-of-the-art ZO methods, ZO-AdaMM has the fastest empirical convergence to strong black-box adversarial attacks that require the minimum distortion strength.

References

Appendix

Smoothing Function and Random Gradient Estimate

If $f$ has $L_{g}$-Lipschitz continuous gradient, then

Proof: We refer readers to [30, Lemma 4.1] for the detailed proof of a)-b) except the Lipschitz continuity of $f_{\mu}$ and (18). Suppose that $f$ is $L_{c}$-Lipschitz continuous, based on the definition of $f_{\mu}$ in (2), we obtain

where the first equality holds due to (2), Jensen’s inequality and Lipschitz continuity of $f$, and the last equality holds since $(1/\alpha(d))\int_{B}\|\mathbf{u}\|_{2}^{p}d\mathbf{u}=\frac{n}{n+p}$ [30, Lemma 6.3.a]. $\square$

In Lemma A1, it is clear from (20) and (21) that the ZO gradient estimate (1) becomes unbiased to the true gradient $\nabla f$ only when $\mu\to 0$. However, if $\mu$ is too small, then the difference of empirical function values is also too small to represent the function differential . Thus, the tolerance on the smoothing parameter $\mu$ is an important factor to indicate the convergence performance of ZO optimization methods. It is also known from (22) that regardless of the value of $\mu$, the variance of the ZO gradient estimate is always proportional to the dimension $d$. This is one of reasons for the dimension-dependent slowdown in convergence of ZO optimization methods. This also introduces technical difficulties for analyzing the effect of adaptive learning rate on the convergence of ZO-AdaMM in nonconvex optimization.

Proof for Nonconvex Optimization

Let us consider a special case of Algorithm 1 with the average ZO gradient estimate $\hat{\nabla}f(\mathbf{x})=\frac{d}{q\mu}\sum_{i=1}^{q}\left\{[f(\mathbf{x}+\mu\mathbf{u}_{i})-f(\mathbf{x})]\mathbf{u}_{i}\right\}$ under $\beta_{1,t}=\beta_{2}\to 0$, $\mu\to 0$ and $q\to\infty$. The conditions of $\beta_{1,t}=\beta_{2}\to 0$ enables Algorithm 1 to reduce to ZO-signSGD in , and the conditions of $\mu\to 0$ and $q\to\infty$ makes the ZO gradient estimate unbiased to $\nabla f(\mathbf{x})$ and its variance close to [14, Proposition 2]. As a result, we obtain $\hat{\mathbf{g}}_{t}\to\nabla f(\mathbf{x}_{t})$, and Algorithm 1 becomes signSGD ,

Let $f(\mathbf{x})=-2x_{1}-x_{2}$ in (6). We then run (23) at $x_{1}=x_{2}=0.5$, which yields

where $\mathcal{X}$ encodes the constraint $|x_{1}+x_{2}|\leq 1$.

It is clear that the updating rule (24) will converge to $\mathbf{x}=[0.5,0.5]^{T}$ regardless of the choice of $\alpha_{t}$. The remaining question is whether or not it is a stationary point. Recall that a point $\mathbf{x}^{*}$ is a stationary point if it satisfies the following conditions:

Since the gradient at $[0.5,0.5]^{T}$ is $^{T}$, and the inequality (25) at $\mathbf{x}=[0.6,0.4]^{T}\in X$ does not hold, given by $\langle^{T},[0.6,0.4]^{T}-[0.5,0.5]^{T}\rangle=-0.1<0$. This implies that $\mathbf{x}^{*}=[0.5,0.5]^{T}$ is not a stationary point of problem (6).

Next, we apply the Mhalanobis distance $\hat{\mathbf{V}_{t}}=\operatorname{diag}(\nabla f(\mathbf{x}_{t})^{2})$ to (23),

Similar to (23), we then consider the impact of fixed point $\mathbf{x}_{t+1}=\mathbf{x}_{t}$ on (26). By the definition of projection operator, we have

The optimality condition of (27) is given by

It thus means that $\mathbf{x}_{t}$ is a stationary point by (25). $\square$

2 Proof of Proposition 2

Before proving the main result Proposition 2, we first prove a few auxiliary lemmas.

Given $\{\mathbf{x}_{t}\}$ from Algorithm 1, consider the sequence

Proof of Lemma 2.1: The proof follows from Lemma 6.1 in by setting $\beta_{1,t}=\beta_{1}$.

Proof of Lemma 2.2: By smoothness of function $f$, we can have

Summing $t$ from $1$ to $T$ and take expectation, we get

Assume $\|\hat{g}_{t}\|_{\infty}\leq G_{zo},\,\forall t\in[T]$ and $m_{0}=0$, By ZO-AdaMM update rule, we have

Proof of Lemma 2.3: By Lemma 2.1, we have

The upper bound on $\|\mathbf{m}_{t}\|_{\infty}$ can be proved by a simple induction. Recall that $\mathbf{m}_{t}=\beta_{1,t}\mathbf{m}_{t-1}+(1-\beta_{1,t})\mathbf{\hat{g}}_{t}$, suppose $\|\mathbf{m}_{t-1}\|\leq G_{zo}$, we have

Then since $\mathbf{m}_{0}=0$, we have $\|\mathbf{m}_{0}\|\leq G_{zo}$, which completes the induction.

Sum $t$ from 1 to $T$ and take expectation over randomness of $\mathbf{\hat{g}}_{t}$, we have

where the last inequality follows from following facts.

1. Since $\mathbf{\hat{v}}_{t}=\max(\mathbf{\hat{v}}_{t-1},\mathbf{v}_{t})$, we know $\mathbf{\hat{v}}_{t}$ is non-decreasing. Given the fact that $\alpha_{t}$ is non-increasing (by our choice), we have $\alpha_{t-1}/\mathbf{\hat{v}}_{t-1,i}-\alpha_{t}/\mathbf{\hat{v}}_{t,i}\geq 0$. Thus, following inequality holds.

Assume $\gamma\mathrel{\mathop{:}}=\beta_{1}/\beta_{2}<1$, ZO-AdaMM yields

Comment:This is an important lemma for ZO-AdaMM, it shows the squared update quantity is not dependent on size of stochastic gradient, thus giving a tighter dependency on $d$ compared with .

Proof of Lemma 2.4: By the update rule, we have

where the second inequality is due to Cauchy-Schwarz and $\gamma=\beta_{1}/\beta_{2}<1$.

Proof of Proposition 2: Substitute (41) and (2.3) into (30), we get

Rearrange and assume $f_{\mu}(\mathbf{z}_{1})-\min_{\mathbf{z}}f_{\mu}(\mathbf{z})\leq D_{f}$, we get

Set $\alpha_{t}=\alpha=1/\sqrt{Td}$ and divide both sides by $T\alpha$, uniformly randomly pick $R$ from 1 to $T$,

Since $\mathbf{\hat{V}}_{0,ii}^{1/2}\geq c,\,\forall i\in[d]$. By Lemma A1, we have

Substituting into $\mu$ finishes the proof. $\square$

3 Proof of Proposition 3

Let $\xi=4\log\frac{dT}{\delta}$, and by the assumption of $\max(d,T)\geq 3$ we have $1+\log\xi\leq\xi/2$. Thus, we obtain from (46) that

Recall that the ZO gradient estimate $\hat{\mathbf{g}}_{t}$ is given by the form

By Lipschitz of $f$ under A2, the $i$th coordinate of the ZO gradient estimate (48) is upper bounded by $dL_{c}|u_{i}|$. Since $\mathbf{u}$ is drawn uniformly randomly from a unit sphere, by (47) we have

Also, since $|\hat{g}_{t,i}|\leq dL_{c}|u_{i}|$, based on (49) we obtain that

Substituting $\xi=4\log\frac{dT}{\delta}$ into (50), we have

Then by the union bound and (51), we have

which implies the inequality (12). $\square$

4 Proof of Theorem 1

The idea is to prove a similar result as Proposition 2 conditioned on the event in Proposition 3 ($\max_{t\in[T]}\{\|\hat{\mathbf{g}}_{t}\|_{\infty}\}\leq 2L_{c}\sqrt{d\log({dT}/{\delta})}$). Thus, the proof follows the same flow as Proposition 2. The difference is that (40) does not hold conditioned on the event and more efforts are need to bound the corresponding term in (40). Denote the event that $\max_{t\in[T]}\{\|\hat{\mathbf{g}}_{t}\|_{\infty}\}\leq 2L_{c}\sqrt{d\log({dT}/{\delta})}$ to be $U(\delta)$, we need to upper bound

By Proposition 3, we know $P(U(\delta))\geq 1-\delta$ and using the fact that $E[\cdot|A]=\frac{E[\cdot]-E[\cdot|A^{c}]P(A^{c})}{P(A)}$ for any event $A$ and its complimentary event $A^{c}$, we have

where the first inequality is due to $\|\nabla f_{\mu}(x_{t})\|_{\infty}\leq\eta$ and $\hat{v}_{t-1}^{1/2}\geq\hat{\mathbf{v}}_{0}^{1/2}\geq c\mathbf{1}$, the second inequality is due to (1) and Lipschitz continuity of $f(\mathbf{x};\boldsymbol{\xi})$.

Replacing (40) with (2.4) and going through the rest of the proof of Proposition (2), one can finally get

Since in the event of $U(1/Td^{0.5})$, we have

Substituting the above inequality into (2.4), we get the desired result. $\square$

5 Proof of Theorem 2

To proceed into proof of Theorem 2, we give a few technical lemmas for the properties of (8).

For any symmetric $\mathbf{H}\succeq 0,\mathbf{g},\omega$, we have

Proof of Lemma 2.5: By definition of $\mathbf{x}^{+}$, the optimality condition of (7) is

Let $\mathbf{x}_{1}^{+}$ and $\mathbf{x}_{2}^{+}$ be given by (7) with $\mathbf{g}$ replaced by $\mathbf{g}_{1}$ and $\mathbf{g}_{2}$, with $H\succ 0$, we have

where $\lambda_{\min}(\mathbf{H})$ is the minimum eigenvalue of $\mathbf{H}$.

Proof of Lemma 2.6: By definition of $\mathbf{x}^{+}$, the optimality condition of (7) is

Summing up the above two inequalities, we get

Further, by (60) and Cauchy-Schwarz, we also have

which gives (59). This completes the proof. $\square$

The following lemma characterizes the difference between projected points if different distance matrices are used in ZO-AdaMM.

Assume $\mathbf{V}_{t}^{1/2}\geq c\mathbf{I}$, ZO-AdaMM yields

Proof of Lemma 2.7: Recall the optimality condition of (7) is

which implies (by using Cauchy-Swartz on the left hand side and then squaring both sides)

where (a) is due to $\hat{v}_{t,i}^{1/2}\geq\hat{v}_{t-1,i}^{1/2}$ and (b) is due to Lemma 2.6 by treating $\mathbf{g}_{1}=\nabla f_{\mu}(\mathbf{x}_{t}),\,\mathbf{g}_{2}=0,\,\mathbf{x}^{-}=\mathbf{x}_{t},\,H=\mathbf{\hat{V}}_{t}^{1/2}$. Substituting (8) into LHS of the above inequality and rearrange, we get (61). This completes the proof. $\square$

Now we are ready to prove our main theorem.

We start with standard decent lemma in nonconvex optimization. By Lipschitz smoothness of $f_{\mu}$, we have

We need to upper bound RHS of the above inequality and split out a descent quantity.

where the inequality is by Lemma (2.5) and some simple substitutions.

Further, for the last term in RHS of (2.5) we have

Next, we bound the three terms in RHS of (2.5).

Let’s bound term $A$ first, with the assumption $\mathbf{\hat{V}}^{1/2}\geq c\mathbf{I}$, by Lemma 2.6, (8) and Cauchy-Schwartz inequality, we have:

Substituting the above bounds for A and C, into (2.5) and (2.5), using Young’s inequality on term B, we have

What remains is to bound the term $B2$ which is given by Lemma 2.7.

where the second inequality is by (8) and Lemma (2.6)

Summing over $t$ from 1 to $T$, setting $\alpha_{t}=\alpha$, and dividing both sides by $T(\alpha-\frac{L_{g}\alpha^{2}}{2c^{2}})$, we get

where the last inequality holds since $\sum_{k=1}^{T}\beta_{2}^{T-k}\leq 1/(1-\beta_{2})$.

Uniformly randomly picking $R$ from $1$ to $T$ and substituting (2.5) into (2.5) finishes the proof. $\square$

Proof for Convex Optimization

We follow the analytic framework in [18, Theorem 4] Based on Lemma A1, we obtain that $f_{t,\mu}$ defined in (2) (with respect to $f_{t}$) is convex. The convexity of $f_{t,\mu}$ yields

Further, recall that $\Pi_{\mathcal{X},\sqrt{\hat{\mathbf{V}}_{t}}}(\mathbf{x}^{*})=\arg\min_{\mathbf{x}\in\mathcal{X}}\|\hat{\mathbf{V}}_{t}^{1/4}(\mathbf{x}-\mathbf{x}^{*})\|^{2}=\mathbf{x}^{*}$, where for ease of notation, let $\|\cdot\|$ denote the Euclidean norm. Applying [18, Lemma 4] to ZO-AdaMM, we obtain that

Rearranging the above inequality, and using the Cauchy-Schwarz inequality $2\langle\mathbf{a},\mathbf{b}\rangle\leq c\|\mathbf{a}\|^{2}+\cfrac{1}{c}\|\mathbf{b}\|^{2}$ for $c>0$, we obtain

Taking the sum over $t$ for (3.1), we obtain

where we have used the facts that $\beta_{1,t}\leq\beta_{1}$ and $1/(1-\beta_{1,t})\leq 1/(1-\beta_{1})$.

We next bound term $A$ in (3.1). Based on (4), we can directly apply [18, Lemma 2] to obtain that

Furthermore, we bound term $B$ in (3.1). Based on (4), we obtain that

where we have used the fact that $\mathbf{v}_{t}\leq\hat{\mathbf{v}}_{t}$ given in Algorithm 1. The last term in (3.1) can be further derived via (4),

where the first inequality holds due to Cauchy-Schwarz inequality and $\beta_{1,T-k}\leq\beta_{1}$ for $\forall k$, the second inequality holds due to $1-\beta_{1,j}\leq 1$, and the third inequality holds due to $\sum_{j=1}^{T}\beta_{1}^{T-1-j}\leq 1/(1-\beta_{1})$ and $\beta_{2}^{T-j}\hat{g}_{j,i}^{2}\leq\sum_{j=1}^{T}\beta_{2}^{T-j}\hat{g}_{j,i}^{2}$. Based on (3.1), we then applies the proof of [18, Lemma 2], which yields

Substituting (83) and (86) into (3.1), we obtain that

We remark that it was shown in that the proof in to bound the term $C$ is problematic. Compared to , we propose a simpler fix to bound $C$ when $0<\beta_{1,t}\leq\beta_{1,t-1}\leq 1$. We rewrite $C$ in (3.1) as

Further, the first term in RHS of (3.1) can be bounded as

where the inequality (a) holds since $\beta_{1,t}\leq\beta_{1,t-1}\leq\beta_{1}$ and $1/(1-\beta_{1,t})-1/(1-\beta_{1,t-1})\leq 0$, and the inequality (b) holds due to $\|x_{t}-x^{*}\|_{\infty}\leq D_{\infty}$ and $\frac{\hat{v}_{t,i}^{1/2}}{\alpha_{t}}-\frac{\hat{v}_{t-1,i}^{1/2}}{\alpha_{t-1}}\geq 0$. Substituting (3.1) into (3.1), we obtain that

where the last inequality holds since $\hat{v}_{t+1,i}^{1/2}\geq\hat{v}_{t,i}^{1/2}$ and $\alpha_{1}\geq\alpha_{T}$.

We highlight that although the proof on bounding $C$ in [18, Theorem 4] is problematic, the conclusion of [18, Theorem 4] keeps correct.

Substituting $C$ and $D$ into (3.1), we obtain that

In (3.1), since $\sqrt{\cdot}$ is a concave function, the Jensen’s inequality yields

Substituting (93) into (3.1) and (79), we complete the proof.

Supplementary Material of Experiments

It is known that DNN-based image classifiers are vulnerable to adversarial examples—one can carefully craft images with imperceptible perturbations (a.k.a. adversarial perturbations or adversarial attacks) that can fool image classifiers even under a black box threat model, where details of the model are unknown to the attacker .

We focus on two problem settings of black-box adversarial attacks: per-image adversarial perturbation and universal adversarial perturbation. Let ($\mathbf{x},t$) denote a legitimate image $\mathbf{x}$ with the true label $t\in\{1,2,\ldots,K\}$, where $K$ is the total number of image classes. And let $\mathbf{x}^{\prime}=\mathbf{x}+\boldsymbol{\delta}$ denote an adversarial example, where $\boldsymbol{\delta}$ is the adversarial perturbation. Our goal is to design $\boldsymbol{\delta}$ for a single image $\mathbf{x}$ or multiple images $\{\mathbf{x}_{i}\}_{i=1}^{M}$. Spurred by , we consider the optimization problem

In problem (96), if $M=1$, then it becomes our first task to find per-image adversarial perturbations. If $M>1$, then the problem corresponds to the task of finding universarial adversarial perturbations to $M$ images. Problem (96) yields a constrained formulation for the design of black-box adversarial attacks. Since some ZO algorithms are designed only for unconstrained optimization (see Table 1), we also consider the unconstrained version of problem (96) ,

The experiments of generating black-box adversarial examples will be performed on Inception V3 under the dataset ImageNet . We will compare the proposed ZO-AdaMM method with $6$ existing ZO algorithms, ZO-SGD , ZO-SCD and ZO-signSGD for unconstrained optimization, and ZO-PSGD , ZO-SMD and ZO-NES for constrained optimization. The first $5$ methods have been summarized in Table 1, and ZO-NES refers to the black-box attack generation method in , which applies a projected version of ZO-signSGD using natural evolution strategy (NES) based random gradient estimator. In all the aforementioned ZO algorithms, we adopt the random gradient estimator (15) and set $b=1$ and $q=10$ so that every method takes the same query cost per iteration. Accordingly, the total query complexity is consistent with the number of iterations.

In Fig. A1, we show the influence of exponential averaging parameters $\beta_{1}$ and $\beta_{2}$ on the convergence of ZO-AdaMM, in terms of the converged total loss while designing the per-image (ID $11$ in ImageNet) and universal adversarial attack. As we can see, the typical choice of $\beta_{2}>0.9$ is no longer the empirically optimal choice in the ZO setting. In all of our experiments, we find that the choice of $\beta_{1}\geq 0.9$ and $\beta_{2}\in[0.3,0.5]$ performs well in practice. In Table A1 and A2, we present the best learning rate parameter $\alpha$ founded by greedy search at each experiment, in the sense that the smallest objective function (corresponding to the successful attack) is achieved given the maximum number of iterations $T$.

2 Per-image black-box adversarial attack

We consider the task of per-image adversarial perturbation by solving problems (96) and (99), where $M=1$ and $\lambda=10$. In ZO-AdaMM (Algorithm 1), we set $\mathbf{v}_{0}=\hat{\mathbf{v}}_{0}=10^{-5}$, $\mathbf{m}_{0}=\mathbf{0}$, $\beta_{1t}=\beta_{1}=0.9$, $\beta_{2}=0.3$ and $T=1000$. Here the exponential moving average parameters $(\beta_{1},\beta_{2})$ are exhaustively searched over $\{01,0.3,0.5,0.7,0.9\}^{2}$; see Fig. A1-(a) & (b) in Appendix 4 as an example. In ZO-AdaMM, we also choose a decaying learning rate $\alpha_{t}=\alpha/\sqrt{t}$ with $\alpha=0.01$. For fair comparison, we use the decaying strategy for all other ZO algorithms, and we determine the best choice of $\alpha$ by greedy search over the interval $[10^{-4},10^{-2}]$; see Table A1 in Appendix 4 for more results on selecting $\alpha$.

3 Universal black-box adversarial attack

In this experiment, we solve the constrained problem (96) for designing a universal adversarial perturbation $\boldsymbol{\delta}$, where we attack $M=10$ images with the true class label ‘brambling’ and we set $\lambda=10$ in (96). The setting of algorithmic parameters is similar to Appendix 4.2 except $T=20000$. For ZO-AdaMM, we choose $\alpha=0.002$, $\beta_{1}=0.9$, and $\beta_{2}=0.3$, where the sensitivity of exponential moving average parameters $(\beta_{1},\beta_{2})$ is shown in Fig. A1-(c). For the other ZO algorithms, we greedily search $\alpha$ over $[10^{-2},10^{-4}]$ and choose the value that achieves the best convergence accuracy as shown in Table A2.

In Fig. A2, we visualize the pattern of universal adversarial perturbation obtained from different methods. As we can see, the resulting universal perturbation pattern identifies the most discriminative image regions corresponding to the true label ‘brambling’. We also observe that although each method successfully generates the black-box adversarial example, ZO-AdaMM yields the strongest attack that requires the least distortion strength.