summaries: The paper provides a convergence analysis of a class of prior-guided zeroth-order (ZO) optimization algorithms and gives a prior-guided variant of the accelerated random search (ARS) algorithm.  Contribution: 1. Provides a complete convergence on some prior-guided zeroth-order optimization algorithms. 2. Provides a prior-guided variant of the ARS algorithm. This work studies the problem of zeroth-order optimization in a deterministic setting, where the exact function values at each point can be observed but the gradient of the function is not accessible. The main approach for solving such problems is first to estimate the gradient of the function and then apply a gradient method by plugging in this estimator instead of the gradient. The main goal of this work is to provide convergence guarantee for prior guided zeroth order algorithms.  Assumptions on the objective function: The objective function is (strongly) convex and smooth.  Approach: Since the paper assumes a deterministic setting, at each step by two function evaluations and choosing a small enough perturbation term, roughly they can observe the gradient of the function towards any arbitrary direction (page 3, equation 1). Also, they assume that at each step they can observe $q$ random directions of the gradient, which are given priorly (or they estimate them by $2q$ additional function evaluations). Then, they take advantage of these $q$ given directions and $g_{I}$s to construct $g_t$, where $g_t$ is the gradient estimator at step $t$, and $I<t$.   Contributions: Their results in Theorems 3 and 4 outline the convergence guarantees and robustness to the learning rate. This work analyzes the convergence rates of several existing prior guided zero order optimization methods. The zero order methods studied use statistical methods to provide an estimate of the function gradient using only function evaluations. This works studies the trade offs between gradient estimation accuracy and function evaluations as well as the effect of learning rate selection for the various estimates. This work also proposes a prior guided version of accelerated random search and studies its convergence. All algorithms studied are then numerically compared on benchmark functions as well as black box adversarial attacks.  This paper studies the performance of zeroth order optimization algorithms where gradient estimation uses prior information. They provide a bound on the convergence analysis for such prior guided algorithms in terms of expected alignment of the gradient estimates to the true gradient. They use this framework to study historical priors and show that such a prior may counter the effects of using a sub-optimal learning rate. They also provide a new accelerated random search algorithm that incorporates prior information. 
abstractText: Zeroth-order (ZO) optimization is widely used to handle challenging tasks, such as query-based black-box adversarial attacks and reinforcement learning. Various attempts have been made to integrate prior information into the gradient estimation procedure based on finite differences, with promising empirical results. However, their convergence properties are not well understood. This paper makes an attempt to fill up this gap by analyzing the convergence of prior-guided ZO algorithms under a greedy descent framework with various gradient estimators. We provide a convergence guarantee for the prior-guided random gradient-free (PRGF) algorithms. Moreover, to further accelerate over greedy descent methods, we present a new accelerated random search (ARS) algorithm that incorporates prior information, together with a convergence analysis. Finally, our theoretical results are confirmed by experiments on several numerical benchmarks as well as adversarial attacks. Our code is available at https://github.com/csy530216/pg-zoo.
authors.name: Shuyu Cheng
authors.name: Guoqiang Wu
authors.name: Jun Zhu
references.authors: Marcin Andrychowicz Misha Denil Sergio Gomez Matthew W Hoffman David Pfau Tom Schaul Brendan Shillingford Nando De Freitas
references.title: Learning to learn by gradient descent by gradient descent
references.venue: arXiv preprint arXiv:1606.04474,
references.authors: Albert S Berahas Liyuan Cao Krzysztof Choromanski Katya Scheinberg
references.title: A theoretical and empirical comparison of gradient approximations in derivative-free optimization
references.venue: Foundations of Computational Mathematics,
references.authors: El Houcine Bergou Eduard Gorbunov Peter Richtarik
references.title: Stochastic three points method for unconstrained smooth minimization
references.venue: SIAM Journal on Optimization,
references.authors: Thomas Brunner Frederik Diehl Michael Truong Le Alois Knoll
references.title: Guessing smart: Biased sampling for efficient black-box adversarial attacks
references.venue: In Proceedings of the IEEE/CVF International Conference on Computer Vision,
references.authors: Sébastien Bubeck
references.title: Convex optimization: Algorithms and complexity
references.venue: arXiv preprint arXiv:1405.4980,
references.authors: Nicholas Carlini David Wagner
references.title: Towards evaluating the robustness of neural networks
references.venue: In 2017 ieee symposium on security and privacy (sp),
references.authors: Pin-Yu Chen Huan Zhang Yash Sharma Jinfeng Yi Cho-Jui Hsieh
references.title: Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models
references.venue: In Proceedings of the 10th ACM workshop on artificial intelligence and security,
references.authors: Shuyu Cheng Yinpeng Dong Tianyu Pang Hang Su Jun Zhu
references.title: Improving black-box adversarial attacks with a transfer-based prior
references.authors: Krzysztof Choromanski Mark Rowland Vikas Sindhwani Richard Turner Adrian Weller
references.title: Structured evolution with compact architectures for scalable policy optimization
references.venue: In International Conference on Machine Learning,
references.authors: Daniel Golovin John Karro Greg Kochanski Chansoo Lee Xingyou Song Qiuyi Zhang
references.title: Gradientless descent: High-dimensional zeroth-order optimization
references.authors: Nikolaus Hansen Andreas Ostermeier
references.title: Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation
references.venue: In Proceedings of IEEE international conference on evolutionary computation,
references.authors: Nikolaus Hansen Steffen Finck Raymond Ros Anne Auger
references.title: Real-parameter black-box optimization benchmarking 2009: Noiseless functions definitions
references.venue: PhD thesis,
references.authors: Andrew Ilyas Logan Engstrom Anish Athalye Jessy Lin
references.title: Black-box adversarial attacks with limited queries and information
references.venue: In International Conference on Machine Learning,
references.authors: Andrew Ilyas Logan Engstrom Aleksander Madry
references.title: Prior convictions: Black-box adversarial attacks with bandits and priors
references.venue: arXiv preprint arXiv:1807.07978,
references.authors: David Kozak Stephen Becker Alireza Doostan Luis Tenorio
references.title: A stochastic subspace approach to gradient-free optimization in high dimensions
references.venue: Computational Optimization and Applications,
references.authors: Niru Maheswaranathan Luke Metz George Tucker Dami Choi Jascha Sohl-Dickstein
references.title: Guided evolutionary strategies: Augmenting random search with surrogate gradients
references.venue: In International Conference on Machine Learning,
references.authors: Horia Mania Aurelia Guy Benjamin Recht
references.title: Simple random search of static linear policies is competitive for reinforcement learning
references.venue: In Proceedings of the 32nd International Conference on Neural Information Processing Systems,
references.authors: J Matyas
references.title: Random optimization
references.venue: Automation and Remote control, 26(2):246–253
references.authors: Florian Meier Asier Mujika Marcelo Matheus Gauy Angelika Steger
references.title: Improving gradient estimation in evolutionary strategies with past descent directions
references.authors: Yu Nesterov
references.title: Efficiency of coordinate descent methods on huge-scale optimization problems
references.venue: SIAM Journal on Optimization,
references.authors: Yurii Nesterov Vladimir Spokoiny
references.title: Random gradient-free minimization of convex functions
references.venue: Foundations of Computational Mathematics,
references.authors: Tim Salimans Jonathan Ho Xi Chen Szymon Sidor Ilya Sutskever
references.title: Evolution strategies as a scalable alternative to reinforcement learning
references.venue: arXiv preprint arXiv:1703.03864,
references.authors: Jasper Snoek Hugo Larochelle Ryan P Adams
references.title: Practical bayesian optimization of machine learning algorithms
references.venue: arXiv preprint arXiv:1206.2944,
references.authors: Sebastian U Stich Christian L Muller Bernd Gartner
references.title: Optimization of convex functions with random pursuit
references.venue: SIAM Journal on Optimization,
references.authors: Chun-Chen Tu Paishun Ting Pin-Yu Chen Sijia Liu Huan Zhang Jinfeng Yi Cho-Jui Hsieh Shin- Ming Cheng
references.title: Autozoom: Autoencoder-based zeroth order optimization method for attacking black-box neural networks
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
sections.heading: 1 Introduction
sections.text: Zeroth-order (ZO) optimization [18] provides powerful tools to deal with challenging tasks, such as query-based black-box adversarial attacks [7, 13], reinforcement learning [22, 17, 9], meta-learning [1], and hyperparameter tuning [23], where the access to gradient information is either not available or too costly. ZO methods only assume an oracle access to the function value at any given point, instead of gradients as in first-order methods. The primary goal is to find a solution with as few queries to the function value oracle as possible. Recently, various ZO methods have been proposed in two main categories. One type is to obtain a gradient estimator and plug in some gradient-based methods. [21] analyzes the convergence of such methods with a random gradient-free (RGF) estimator obtained via finite difference along a random direction. The other type is directed search, where the update only depends on comparison between function values at different points. Such methods are robust against monotone transform of the objective function [24, 10, 3]. However, as they do not directly utilize function values, their query complexity is often higher than that of finite difference methods. Therefore, we focus on the first type of methods in this paper. Other methods exist such as CMA-ES [11] which is potentially better on objective functions with a rugged landscape, but lacks a general convergence guarantee.
  ZO methods are usually less efficient than first-order algorithms, as they typically take O(d) queries to reach a given precision, where d is the input dimension (see Table 1 in [10]). Specifically, for the methods in [21], the oracle query count is O(d) times larger than that of their corresponding schemes using gradients. This inefficiency stems from random search along uniformly distributed directions. To improve, various attempts have been made to augment random search with (extra) ∗J.Z. is the Corresponding Author. G.W. is now with School of Software, Shandong University.
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  prior information. For instance, [14, 19] use a time-dependent prior (i.e., the gradient estimated in the last iteration), while [16, 8, 4] use surrogate gradients obtained from other sources.2 Among these methods, [14, 16, 8, 19] propose objective functions to describe the quality of a gradient estimator for justification or optimizing its hyperparameters; for example, [19] uses a subspace estimator that maximizes its squared cosine similarity with the true gradient as the objective, and finds a better descent direction than both the prior direction and the randomly sampled direction. However, all these methods treat gradient estimation and the optimization algorithm separately, and it remains unclear whether are these gradient estimators and the corresponding prior-exploiting optimization methods theoretically sound? and what role does the prior play in accelerating convergence?
  In this paper, we attempt to answer these questions by establishing a formal connection between convergence rates and the quality of gradient estimates. Further, we develop a more efficient ZO algorithm with prior inspired by a theoretical analysis. First, we present a greedy descent framework of ZO methods and provide its convergence rate under smooth convex optimization, which is positively related to the squared cosine similarity between the gradient estimate and true gradient. As shown by [19] and our results, given some finite-difference queries, the optimal estimator maximizing the squared cosine similarity is the projection of true gradient on the subspace spanned by those queried directions. In the case with prior information, a natural such estimator is in the same form as the one in [19]. We call it PRGF estimator and analyze its convergence rate.3 Our results show that no matter what the prior is, the convergence rate of PRGF is at least the same as that of the RGF baseline [21, 15], and it could be significantly improved if given a useful prior.4 Such results shed light on exploring prior information in ZO optimization to accelerate convergence.
  Then, as a concrete example, we apply the analysis to History-PRGF [19], which uses historical information (i.e., gradient estimate in the last iteration) as the prior. [19] presents an analysis on linear functions, yet still lacking a convergence rate. We analyze on general L-smooth functions, and find that when the learning rate is smaller than the optimal value 1/L in smooth optimization, the expected squared cosine similarity could converge to a larger value, which compensates for the slowdown of convergence brought by the inappropriate choice of learning rate. We also show that History-PRGF admits a convergence rate independent of learning rate as long as it is in a fairly wide range.
  Finally, to further accelerate greedy descent methods, we present Prior-Guided ARS (PARS), a new variant of Accelerated Random Search (ARS) [21] to utilize prior information. Technically, PARS is a non-trivial extension of ARS, as directly replacing the gradient estimator in ARS by the PRGF estimator would lose the convergence analysis. Thus, we present necessary extensions to ARS, and show that PARS has a convergence rate no worse than that of ARS and admits potential acceleration given a good prior. In particular, when the prior is chosen as the historical information, the resulting History-PARS is robust to learning rate in experiments. To our knowledge, History-PARS is the first ARS-based method that is empirically robust while retaining the convergence rate as ARS. Our experiments on numerical benchmarks and adversarial attacks confirm the theoretical results.
sections.heading: 2 Setups
sections.text: Assumptions on the problem class We consider unconstrained optimization, where the objective function f : Rd → R is convex and L-smooth for L ≥ 0. Optionally, we require f to be τ -strongly convex for τ > 0. We leave definitions of these concepts to Appendix A.1.
  Directional derivative oracle In ZO optimization, we follow the finite difference approach, which makes more use of the queried function values than direct search and provides better gradient approximations than alternatives [2]. In particular, we consider the forward difference method:
  gµ(v;x) := f(x+ µv)− f(x)
  µ ≈ ∇f(x)>v, (1)
  2Some work [7, 14, 25] restricts the random search to a more effective subspace reflecting the prior knowledge. But, this eliminates the possibility of convergence to the optimal solution.
  3Note that the estimator is different from the P-RGF estimator in [8]. 4In this paper, RGF and PRGF could refer to either a gradient estimator or the greedy descent algorithm with
  the corresponding estimator, depending on the context.
  Algorithm 1 Greedy descent framework
  Input: L-smooth convex function f ; initialization x0; upper bound L̂ (L̂ ≥ L); iteration number T . Output: xT as the approximate minimizer of f .
  1: for t = 0 to T − 1 do 2: Let vt be a random vector s.t. ‖vt‖ = 1; 3: xt+1 ← xt − 1L̂gt, where gt ← ∇f(xt)
  >vt · vt; 4: end for 5: return xT .
  where v is a vector with unit `2 norm ‖v‖ = 1 and µ is a small positive step. As long as the objective function is smooth, the error between the finite difference and the directional derivative could be uniformly bounded, as shown in the following proposition (see Appendix A.2 for its proof). Proposition 1. If f is L-smooth, then for any (x, v) with ‖v‖ = 1, |gµ(v;x)−∇f(x)>v| ≤ 12Lµ. Thus, in smooth optimization, the error brought by finite differences to the convergence bound can be analyzed in a principled way, and its impact tends to zero as µ→ 0. We also choose µ as small as possible in practice. Hence, in the following analysis we directly assume the directional derivative oracle: suppose that we can obtain∇f(x)>v for any (x, v) in which ‖v‖ = 1 with one query.
sections.heading: 3 Greedy descent framework and PRGF algorithm
sections.text: We now introduce a greedy descent framework in ZO optimization which can be implemented with various gradient estimators. We first provide a general analysis, followed by a concrete example.
sections.heading: 3.1 The greedy descent framework and general analysis
sections.text: In first-order smooth convex optimization, a sufficient single-step decrease of the objective can guarantee convergence (see Chapter 3.2 in [5]). Inspired by this fact, we design the update in an iteration to greedily seek for maximum decrease. Suppose we are currently at x, and want to update along the direction v. Without loss of generality, assume ‖v‖ = 1 and∇f(x)>v > 0. To choose a suitable step size η that minimizes f(x− ηv), we note that
  f(x− ηv) ≤ f(x)− η∇f(x)>v + 1 2 Lη2 := F (η) (2)
  by smoothness of f . For the r.h.s, we have F (η) = f(x)− (∇f(x) >v)2 2L when η = ∇f(x)>v
  L , which minimizes F (η). Thus, choosing such η could lead to a largest guaranteed decrease of f(x−ηv) from f(x). In practice, the value of L is often unknown, but we can verify that as long as 0 < η ≤ ∇f(x)
  >v L ,
  then f(x− ηv) ≤ F (η) < f(x), i.e., we can guarantee decrease of the objective (regardless of the direction of v if∇f(x)>v > 0). Based on the above discussion, we further allow v to be random and present the greedy descent framework in Algorithm 1. Remark 1. If vt ∼ U(Sd−1), i.e. vt is uniformly sampled from Sd−1 (the unit sphere in Rd), then Algorithm 1 is similar to the simple random search in [21] except that vt is sampled from a Gaussian distribution there. Remark 2. In general, vt could depend on the history (i.e., the randomness before sampling vt). For example, vt can be biased towards a vector pt that corresponds to prior information, and pt depends on the history since it depends on xt or the optimization trajectory.
  Theoretically speaking, vt is sampled from the conditional probability distribution Pr(·|Ft−1) where Ft−1 is a sub σ-algebra modelling the historical information. Ft−1 is important in our theoretical analysis since it tells how to perform conditional expectation given the history.
  We always require that Ft−1 includes all the randomness before iteration t to ensure that Lemma 1 (and thus Theorems 1 and 2) and Theorem 5 hold. For further theoretical analysis of various implementations of the framework, Ft−1 remains to be specified by possibly also including some randomness in iteration t (see e.g. Example 2 as an implementation of Algorithm 1).5
  5In mathematical language, if Ft−1 includes (and only includes) the randomness brought by random vectors {x1, x2, . . . , xn}, then Ft−1 is the σ-algebra generated by {x1, x2, . . . , xn}: Ft−1 is the smallest σ-algebra s.t. xi is Ft−1-measurable for all 1 ≤ i ≤ n.
  By Remark 2, we introduce Et[·] := E[·|Ft−1] to denote the conditional expectation given the history. In Algorithm 1, under a suitable choice of Ft−1, Et[·] roughly means only taking expectation w.r.t. vt. We let v := v/‖v‖ denote the `2 normalization of vector v. We let x∗ denote one of the minimizers of f (we assume such minimizer exists), and δt := f(xt)− f(x∗). Thanks to the descent property in Algorithm 1, we have the following lemma on single step progress.
  Lemma 1 (Proof in Appendix B.1). Let Ct := ( ∇f(xt) > vt )2 and L′ := L
  1−(1−L L̂
  )2 , then in
  Algorithm 1, we have
  Et[δt+1] ≤ δt − Et[Ct]
  2L′ ‖∇f(xt)‖2. (3)
  We note that L′ = L̂/(2−L/L̂), so L̂2 ≤ L ′ ≤ L̂ and L′ ≥ L.
  To obtain a bound on E[δT ], one of the classical proofs (see e.g., Theorem 1 in [20]) requires us to take expectation on both sides of Eq. (3). Allowing the distribution of vt to be dependent on the history leads to additional technical difficulty: in the r.h.s of Eq. (3), Et[Ct] becomes a random variable that is not independent of ‖∇f(xt)‖2. Thus, we cannot simplify the term E[Et[Ct]‖∇f(xt)‖2] if we take expectation.6 By using other techniques, we obtain the following main theorems on convergence rate. Theorem 1 (Algorithm 1, smooth and convex; proof in Appendix B.1). Let R := maxx:f(x)≤f(x0) ‖x− x∗‖ and suppose R <∞. Then, in Algorithm 1, we have
  E[δT ] ≤ 2L′R2
  ∑T−1 t=0 E [ 1
  Et[Ct] ] T (T + 1) . (4)
  Theorem 2 (Algorithm 1, smooth and strongly convex; proof in Appendix B.1). If f is also τ -strongly convex, then we have
  E  δT exp ( − τL′ ∑T−1 t=0 Et[Ct] )  ≤ δ0. (5)
  Remark 3. In our results, the convergence rate depends on Et[Ct] in a more complicated way than only depending on E[Ct] = E[Et[Ct]]. For concrete cases, one may need to study the concentration properties of Et[Ct] besides its expectation, as in the proofs of Theorems 3 and 4 when we analyze History-PRGF, a special implementation in the greedy descent framework.
  In the strongly convex case, currently we cannot directly obtain a final bound of E[δT ]. However, the form of Eq. (5) is still useful since it roughly tells us that δT converges as the denominator exp ( − τL′ ∑T−1 t=0 Et[Ct] ) . For History-PRGF, we will turn this intuition into a rigorous theorem (Theorem 4) since in that case we can prove that the denominator has a nice concentration property. Remark 4. If we have a lower bound of Et[Ct], e.g. Et[Ct] ≥ a > 0, then we directly obtain that E[δT ] ≤ 2L ′R2 a(T+1) for Theorem 1, and E[δT ] ≤ δ0 exp(− τ L′ aT ) for Theorem 2. These could recover the ideal convergence rate for RGF estimator and the worst-case convergence rate for PRGF estimator, as explained in Examples 1 and 2.
  From Theorems 1 and 2, we see that a larger value of Ct would lead to a better bound. To find a good choice of vt in Algorithm 1, it becomes natural to discuss the following problem. Suppose in an iteration in Algorithm 1, we query the directional derivative oracle at xt along q directions {ui}qi=1 (maybe randomly chosen) and obtain the values of {∇f(xt)>ui}qi=1. We could use this information to construct a vector vt. What is the vt that maximizes Ct s.t. ‖vt‖ = 1? To answer this question, we give the following proposition based on Proposition 1 in [19] and additional justification. Proposition 2 (Optimality of subspace estimator; proof in Appendix B.2). In one iteration of Algorithm 1, if we have queried {∇f(xt)>ui}qi=1, then the optimal vt maximizing Ct s.t. ‖vt‖ = 1 should be in the following form: vt = ∇f(xt)A, where A := span{u1, u2, . . . , uq} and ∇f(xt)A denotes the projection of∇f(xt) onto A.
  6It is also the difficulty we faced in our very preliminary attempts of the theoretical analysis when f is not convex, and we leave its solution or workaround in the non-convex case as future work.
  Note that in Line 3 of Algorithm 1, we have gt = ∇f(xt)>∇f(xt)A · ∇f(xt)A = ∇f(xt)A. Therefore, the gradient estimator gt is equivalent to the projection of the gradient to the subspace A, which justifies its name of subspace estimator. Next we discuss some special cases of the subspace estimator. We leave detailed derivation in following examples to Appendix B.3.
  Example 1 (RGF). ui ∼ U(Sd−1) for i = 1, 2, . . . , q. Without loss of generality, we assume they are orthonormal (e.g., via Gram-Schmidt orthogonalization).7 The corresponding estimator gt = ∑q i=1∇f(xt)>ui · ui (vt = gt). When q = 1, the estimator is similar to the random gradientfree oracle in [21]. With q ≥ 1, it is essentially the same as the stochastic subspace estimator with columns from Haar-distributed random orthogonal matrix [15] and similar to the orthogonal ES estimator [9]. In theoretical analysis, we let Ft−1 only include the randomness before iteration t, and then we can prove that Et[Ct] = qd . By Theorems 1 and 2, the convergence rate is E[δT ] ≤ 2L′R2 dq T+1 for smooth convex case, and E[δT ] ≤ δ0 exp(− τL′ q dT ) for smooth and strongly convex case. The bound is the same as that in [15]. Since the query complexity in each iteration is proportional to q, the bound for total query complexity is indeed independent of q.
  Example 2 (PRGF). With slight notation abuse, we assume the subspace in Proposition 2 is spanned by {p1, . . . , pk, u1, . . . , uq}, so each iteration takes q + k queries. Let p1, · · · , pk be k non-zero vectors corresponding to the prior message (e.g. the historical update, or the gradient of a surrogate model), and ui ∼ U(Sd−1) for i = 1, 2, . . . , q. We note that intuitively we cannot construct a better subspace since the only extra information we know is the k priors. In our analysis, we assume k = 1 for convenience, and we change the original notation p1 to pt to explicitly show the dependence of pt on the history. We note that pt could also depend on extra randomness in iteration t (see e.g. the specification of pt in Appendix D.1.1). For convenience of theoretical analysis, we require that pt is determined before sampling {u1, u2, . . . , uq}, and let Ft−1 also include the extra randomness of pt in iteration t (not including the randomness of {u1, u2, . . . , uq}) besides the randomness before iteration t. Then pt is always Ft−1-measurable, i.e. determined by the history. Without loss of generality, we assume {pt, u1, . . . , uq} are orthonormal (e.g., via Gram-Schmidt orthogonalization). The corresponding estimator gt = ∇f(xt)>pt · pt + ∑q i=1∇f(xt)>ui · ui (vt = gt), which is similar to the estimator in [19]. By [19] (the expected drift of X2t in its Theorem 1), we have Lemma 2 (Proof in Appendix B.3.4). In Algorithm 1 with PRGF estimator, Et[Ct] = Dt + qd−1 (1−
  Dt) where Dt := ( ∇f(xt) > pt )2 .
  Hence Et[Ct] ≥ qd holds. By Remark 4, PRGF admits a guaranteed convergence rate of RGF and is potentially better given a good prior (if Dt is large), but it costs an additional query per iteration. This shows soundness of the PRGF algorithm. For further theoretical analysis, we need to bound Dt. This could be done when using the historical prior introduced in Section 3.2 (see Lemma 3). Bounding Dt is usually challenging when a general prior is adopted, but if the prior is an approximate gradient (such case appears in [16]), it may be possible. We leave related investigation as future work.
sections.heading: 3.2 Analysis on the PRGF algorithm with the historical prior
sections.text: We apply the above analysis to a concrete example of the History-PRGF estimator [19], which considers the historical prior in the PRGF estimator. In this case, Lemma 1, Theorem 1 and Theorem 2 will manifest themselves by clearly stating the convergence rate which is robust to the learning rate.
  Specifically, History-PRGF considers the historical prior as follows: we choose pt = gt−1, i.e., we let the prior be the direction of the previous gradient estimate.8 This is equivalent to letting pt = vt−1. Thus, in Algorithm 1, vt = ∇f(xt)A = ∇f(xt)>vt−1 · vt−1 + ∑q i=1∇f(xt)>ui · ui. In this form we require {vt−1, u1, . . . , uq} to be orthonormal, so we first determine vt−1, and then
  7The computational complexity of Gram-Schmidt orthogonalization over q vectors in Rd is O(q2d). Therefore, with a moderate value of q (e.g. q ∈ [10, 20] in our experiments), its cost is usually much smaller than that brought by O(q) function evaluations used to approximate the directional derivatives. We note that when using a numerical computing framework, for orthogonalization one could also adopt an efficient implementation, by calling the QR decomposition procedure such as torch.linalg.qr in PyTorch.
  8One can also utilize multiple historical priors (e.g. the last k updates with k > 1, as proposed and experimented in [19]), but here we only analyze the k = 1 case.
  sample {ui}qi=1 in A⊥, the (d− 1)-dimensional subspace of Rd perpendicular to vt−1, and then do Gram-Schmidt orthonormalization on {ui}qi=1. To study the convergence rate, we first study evolution of Ct under a general L-smooth function. This extends the analysis on linear functions (corresponding to L = 0) in [19]. Under the framework of Algorithm 1, intuitively, the change of the gradient should be smaller when the objective function is very smooth (L is small) or the learning rate is small (L̂ is large). Since we care about the cosine similarity between the gradient and the prior, we prove the following lemma:
  Lemma 3 (Proof in Appendix B.4). In History-PRGF (pt = vt−1), we have Dt ≥ (1− L/L̂)2 Ct−1.
  When L̂ = L, i.e., using the optimal learning rate, Lemma 3 does not provide a useful bound, since an optimal learning rate in smooth optimization could find an approximate minimizer along the update direction, so the update direction may be useless in next iteration. In this case, the historical prior does not provide acceleration. Hence, Lemma 3 explains the empirical findings in [19] that past directions can be less useful when the learning rate is larger. However, in practice we often use a conservative learning rate, for the following reasons: 1) We usually do not know L, and the cost of tuning learning rate could be large; 2) Even if L is known, it only provides a global bound, so a fixed learning rate could be too conservative in the smoother local regions. In scenarios where L̂ is too conservative (L̂ > L), History-PRGF could bring more acceleration over RGF.
  By Lemma 3, we can assume Dt = (1− L/L̂)2 Ct−1 to obtain a lower bound of quantities about Ct. Meanwhile, since Dt means quality of the prior, the construction in Example 2 tells us relationship between Ct and Dt. Then we have full knowledge of the evolution of Ct, and thus Et[Ct]. In Appendix B.4, we discuss about evolution of E[Ct] and show that E[Ct]→ O( qd L′ L ) if q d ≤ L L̂ ≤ 1. Therefore, by Lemma 1, assuming Et[Ct] concentrates well around E[Ct] and hence Et[Ct]L′ ≈ q dL , PRGF could recover the single step progress with optimal learning rate (L̂ = L), since Eq. (3) only depends on Et[Ct]L′ which is constant w.r.t. L
  ′ now. While the above discussion is informal, based on Theorems 1 and 2, we prove following theorems which show that convergence rate of History-PRGF is robust to choice of learning rate.
  Theorem 3 (History-PRGF, smooth and convex; proof in Appendix B.5.1). In the setting of Theorem 1, assuming d ≥ 4, qd−1 ≤ L L̂ ≤ 1 and T > ⌈ d q ⌉ (d·e denotes the ceiling function), we have
  E[δT ] ≤ ( 32
  q + 2
  ) 2LdqR 2
  T − ⌈ d q ⌉ + 1 . (6)
  Sketch of the proof. The idea of the proof of Theorem 3 is to show that for the random variable Et[Ct], its standard deviation √ Var[Et[Ct]] is small relative to its expectation E[Et[Ct]] = E[Ct].
  By Chebyshev’s inequality, we can bound E [
  1 Et[Ct] ] in Theorem 1 with 1E[Et[Ct]] = 1 E[Ct] . In the
  actual proof we replace Ct that appears above with a lower bound Et.
  Theorem 4 (History-PRGF, smooth and strongly convex; proof in Appendix B.5.3). Under the same conditions as in Theorem 2, then assuming d ≥ 4, qd−1 ≤ L L̂ ≤ 1, qd ≤ 0.2 L τ , and T ≥ 5 d q , we have
  E[δT ] ≤ 2 exp ( −0.1 q
  d
  τ L T ) δ0. (7)
  This result seems somewhat surprising since Theorem 2 does not directly give a bound of E[δT ]. Sketch of the proof. The goal is to show that the denominator in the l.h.s of Eq. (5) in Theorem 2, exp(− τ
  L̃
  ∑T−1 t=0 Et[Ct]), concentrates very well. Indeed, the probability that exp(− τ L̃ ∑T−1 t=0 Et[Ct])
  is larger than exp(−0.1 qd τ LT ) is very small so that its influence can be bounded by another exp(−0.1 qd τ LT )δ0, leading to the coefficient 2 in Eq. (7). In our actual analysis we replace Ct that appears above with a lower bound Et.
  Remark 5. As stated in Example 2, using RGF with the optimal learning rate, we have E[δT ] ≤ 2L dqR 2 T+1 for smooth and convex case, and E[δT ] ≤ exp ( − qd τ LT ) δ0 for smooth and strongly convex
  case. Therefore, History-PRGF with a suboptimal learning rate 1 L̂ under the condition qd−1 1 L ≤ 1 L̂ ≤ 1 L could reach similar convergence rate to RGF with optimal learning rate (up to constant factors), which indicates that History-PRGF is more robust to learning rate than RGF. Remark 6. We note that the constants in the bounds are loose and have a large potential to be improved in future work, and empirically the convergence rate of History-PRGF is often not worse than RGF using the optimal learning rate (see Fig. 2).
  As a sidenote, we discuss how to set q in History-PRGF. The iteration complexity given by Theorems 3 and 4 is proportional to 1q if we ignore the constants such as 32 q +2 in Eq. (6) by Remark 6. Meanwhile, we recall that each iteration of PRGF requires q + 1 queries to the directional derivative oracle, so the total query complexity is roughly proportional to q+1q . Hence, a very small q (e.g. q = 1) is
  suboptimal. On the other hand, Theorems 3 and 4 require 1 L̂ ∈ [ q d−1 1 L , 1 L ] , so to enable robustness of History-PRGF to a wider range of the choice of learning rate, q should not be too large. In summary, it is desirable to set q to a moderate value.
  Note that if we adopt line search in Algorithm 1, then one can adapt the learning rate in a huge range and reach the convergence guarantee with the optimal learning rate under weak assumptions. Nevertheless, it is still an intriguing fact that History-PRGF could perform similarly to methods adapting the learning rate, while its mechanism is very different. Meanwhile, History-PRGF is easier to be implemented and parallelized compared with methods like line search, since its implementation is the same as that of the RGF baseline except that it records and uses the historical prior.
sections.heading: 4 Extension of ARS framework and PARS algorithm
sections.text: To further accelerate greedy descent methods, we extend our analysis to a new variant of Accelerated Random Search (ARS) [21] by incorporating prior information, under the smooth and convex setting.9
  By delving into the proof in [21], we present our extension to ARS in Algorithm 2, state its convergence guarantee in Theorem 5 and explain its design in the proof sketch in Appendix C.1.
  Algorithm 2 Extended accelerated random search framework10
  Input: L-smooth convex function f ; initialization x0; L̂ ≥ L; iteration number T ; γ0 > 0. Output: xT as the approximate minimizer of f . 1: m0 ← x0; 2: for t = 0 to T − 1 do
  3: Find a θt > 0 such that θt ≤ Et [ (∇f(yt)>vt) 2 ]
  L̂·Et[‖g2(yt)‖2] where yt, vt and g2(yt) are defined in following steps:
  4: Step 1: yt ← (1 − αt)xt + αtmt, where αt is a positive root of the equation α2t = θt(1 − αt)γt; γt+1 ← (1− αt)γt; 5: Step 2: Let vt be a random vector s.t. ‖vt‖ = 1; g1(yt)← ∇f(yt)>vt · vt; 6: Step 3: Let g2(yt) be an unbiased estimator of∇f(yt), i.e., Et[g2(yt)] = ∇f(yt); 7: xt+1 ← yt − 1
  L̂ g1(yt), mt+1 ← mt − θtαt g2(yt);
  8: end for 9: return xT .
  Theorem 5 (Proof in Appendix C.1). In Algorithm 2, if θt is Ft−1-measurable (see Appendix C.1 for more explanation), then we have
  E (f(xT )− f(x∗))(1 + √γ0 2 T−1∑ t=0 √ θt )2 ≤ f(x0)− f(x∗) + γ0 2 ‖x0 − x∗‖2. (8)
  9The procedure of ARS requires knowledge of the strong convexity parameter τ (τ can be 0), but for clarity we only discuss the case τ = 0 here (i.e., we do not consider strong convexity), and leave the strongly convex case to Appendix C.6.
  10Keys in this extension are: 1) We require Et[g2(yt)] = ∇f(yt). Thus, g2(yt) could not be the PRGF estimator as it is biased towards the prior; 2) To accelerate convergence, we need to find an appropriate θt since it appears in Eq. (8). If we set θt to the value in ARS baseline, then no potential acceleration is guaranteed.
  Remark 7. If we let g1(yt) be the RGF estimator in Example 1 and let g2(yt) = d/q · g1(yt), we can
  show that E[g2(yt)] = ∇f(yt) and θt could be chosen as q 2
  L̂d2 since
  Et [ (∇f(yt)>vt) 2 ]
  L̂·Et[‖g2(yt)‖2] = q
  2
  L̂d2 . Then
  roughly, the convergence rate ∝ q, so the total query complexity is independent of q. When q = 1, ARS baseline is recovered. For convenience we call the algorithm ARS regardless of the value of q. Remark 8. If we have a uniform constant lower bound θ > 0 such that ∀t, θt ≥ θ, then we have
  E [f(xT )− f(x∗)] ≤ ( 1 + √ γ0
  2 T √ θ
  )−2 ( f(x0)− f(x∗) +
  γ0 2 ‖x0 − x∗‖2
  ) . (9)
  Next we present Prior-Guided ARS (PARS) by specifying the choice of g1(yt) and g2(yt) in Algorithm 2 when prior information pt ∈ Rd is available. Since we want to maximize the value of θt, regarding g1(yt) we want to maximize Et [( ∇f(yt)>vt )2] . By Proposition 2 and Exam-
  ple 2, it is natural to let g1(yt) be the PRGF estimator for ∇f(yt). Then by Lemma 2, we have Et [( ∇f(yt)>vt )2] = ‖∇f(yt)‖2(Dt + qd−1 (1−Dt)), where Dt := ( ∇f(yt) > pt )2 . The remaining problem is to construct g2(yt), an unbiased estimator of ∇f(yt) (Et[g2(yt)] = ∇f(yt)), and make Et[‖g2(yt)‖2] as small as possible. We leave the construction of g2(yt) in Appendix C.2. Finally, we calculate the following expression which appears in Line 3 of Algorithm 2 to complete the description of PARS:
  Et [( ∇f(yt)>vt )2] L̂ · Et[‖g2(yt)‖2] = Dt + q d−1 (1−Dt) L̂ ( Dt + d−1 q (1−Dt)
  ) . (10) Since Dt ≥ 0, the right-hand side is larger than q2/L̂d2 (by Remark 7, this value corresponds to the value of θt in ARS), so by Remark 8 PARS is guaranteed a convergence rate of ARS.
  In implementation of PARS, we note that there remain two problems to solve. The first is that Dt is not accessible through one oracle query, since Dt = (∇f(yt) > pt) 2 = ( ∇f(yt)>pt/‖∇f(yt)‖ )2 , and ‖∇f(yt)‖ requires estimation. Fortunately, the queries used to construct g1(yt) and g2(yt) can also be used to estimate Dt. With a moderate value of q, we can prove that considering the error brought by estimation of Dt, a modified version of PARS is guaranteed to converge with high probability. We leave related discussion to Appendix C.3. The second is that Line 3 of Algorithm 2 has a subtlety that
  yt depends on θt, so we cannot directly determine an optimal θt satisfying θt ≤ Et [ (∇f(yt)>vt) 2 ]
  L̂·Et[‖g2(yt)‖2] .
  Theoretically, we can guess a conservative estimate of θt and verify this inequality, but in practice we adopt a more aggressive strategy to find an approximate solution of θt. We leave the actual implementation, named PARS-Impl, in Appendix C.4.
  In PARS, if we adopt the historical prior as in Section 3.2, i.e., letting pt be the previous PRGF gradient estimator g1(yt−1), then we arrive at a novel algorithm named History-PARS. Here, we note that unlike the case in History-PRGF, it is more difficult to derive the evolution of θt theoretically, so we currently cannot prove theorems corresponding to Theorem 3. However, History-PARS can be guaranteed the convergence rate of ARS, which is desirable since if we adopt line search in ARS to reach robustness against learning rate (e.g. in [24]), currently there is no convergence guarantee. We present the actual implementation History-PARS-Impl in Appendix C.5 and empirically verify that History-PARS-Impl is robust to learning rate in Section 5.
sections.heading: 5 Experiments
sections.heading: 5.1 Numerical benchmarks
sections.text: We first experiment on several closed-form test functions to support our theoretical claims. We leave more details of experimental settings to Appendix D.1.
  First, we present experimental results when a general useful prior is provided. The prior-guided methods include PRGF, PARS (refers to PARS-Impl) and PARS-Naive (simply replacing the RGF estimator in ARS with the PRGF estimator). We adopt the setting in Section 4.1 of [16] in which the
  prior is a biased version of the true gradient. Our test functions are as follows: 1) f1 is the “worst-case smooth convex function” used to construct the lower bound complexity of first-order optimization, as in [21]; 2) f2 is a simple smooth and strongly convex function with a worst-case initialization: f2(x) = 1 d ∑d i=1 ( i · (x(i))2 ) , where x(1)0 = d, x (i) 0 = 0 for i ≥ 2; and 3) f3 is the Rosenbrock function (f8 in [12]) which is a well-known non-convex function used to test the performance of optimization problems. For f1 and f2, we set L̂ to ground truth value L; for f3, we search L̂ for best performance for each algorithm. We set d = 256 for all test functions and set q such that each iteration of these algorithms costs 11 queries11 to the directional derivative oracle.12 We plot the experimental results in Fig. 1, where the horizontal axis represents the number of iterations divided by bd/11c, and the vertical axis represents log10 f(xcurrent)−f(x∗) f(x0)−f(x∗) . Methods without using the prior information are shown with dashed lines. We also plot the 95% confidence interval in the colored region. The results show that for these functions (which have ill-conditioned Hessians), ARS-based methods perform better than the methods based on greedy descent. Importantly, the utilization of the prior could significantly accelerate convergence for both greedy descent and ARS. We note that the performance of our proposed PARS algorithm is better than PARS-Naive which naively replaces the gradient estimator in the original ARS with the PRGF estimator, demonstrating the value of our algorithm design with convergence analysis.
  Next, we verify the properties of History-PRGF and History-PARS, i.e., the historical-prior-guided algorithms. In this part we set d = 500. We first verify that they are robust against learning rate on f1 and f2, and plot the results in Fig. 2(a)(b).13 In the legend, for example, ‘RGF’ means RGF using the optimal learning rate (L̂ = L), and ‘RGF-0.02’ means that the learning rate is set to 0.02 times of the optimal one (L̂ = 50L). We note that for PRGF and PARS, q = 10, so qd = 0.02. From Fig. 2(a)(b), we see that: 1) when using the optimal learning rate, the performance of prior-guided algorithms is not worse than that of its corresponding baseline; and 2) the performance of prior-guided algorithms under the sub-optimal learning rate such that qd ≤ L L̂ ≤ 1 is at least comparable to that of its corresponding baseline with optimal learning rate. However, for baseline algorithms (RGF and ARS), the convergence rate significantly degrades if a smaller learning rate is set. In summary, we verify our claims that History-PRGF and History-PARS are robust to learning rate if qd ≤ L L̂ ≤ 1. Moreover, we show that they can provide acceleration over baselines with optimal learning rate on functions with varying local smoothness. We design a new test function as follows:
  f4(x) =
  { 1 2r
  2, r ≤ 1 r − 12 , r > 1
  , r = √ f2(x), where x (1) 0 = 5 √ d, x (i) 0 = 0 for i ≥ 2. (11)
  We note that f4 in regions far away from the origin is more smooth than in the region near the origin, and the global smoothness parameter is determined by the worst-case situation (the region near the origin). Therefore, baseline methods using an optimal learning rate could also manifest sub-optimal performance. Fig. 2(c) shows the results. We can see that when utilizing the historical prior, the algorithm could show behaviors of adapting to the local smoothness, thus accelerating convergence when the learning rate is locally too conservative.
  11That is, for prior-guided algorithms we set q = 10, and for other algorithms (RGF and ARS) we set q = 11. 12The directional derivative is approximated by finite differences. In PARS, 2 additional queries to the directional derivative oracle per iteration are required to find θt (see Appendix C.4). 13In Fig. 2, the setting of ARS-based methods are different from that in Fig. 1 as explained in Appendix D.1, which leads to many differences of the ARS curves between Fig. 1 and Fig. 2.
sections.heading: 5.2 Black-box adversarial attacks
sections.text: In this section, we perform ZO optimization on real-world problems. We conduct score-based blackbox targeted adversarial attacks on 500 images from MNIST and leave more details of experimental settings to Appendix D.2. In view of optimization, this corresponds to performing constrained maximization over {fi}500i=1 respectively, where fi denotes the loss function to maximize in attacks. For each image i, we record the number of queries of fi used in optimization until the attack succeeds (when using the C&W loss function [6], this means fi > 0). For each optimization method, we report the median query number over these images (smaller is better) in Table 1. The subscript of the method name indicates the learning rate 1/L̂. For all methods we set q to 20. Since [8] has shown that using PRGF estimator with transfer-based prior significantly outperforms using RGF estimator in adversarial attacks, for prior-guided algorithms here we only include the historical prior case.
  We found that in this task, ARS-based methods perform comparably to RGF-based ones. This could be because 1) the numbers of iterations until success of attacks are too small to show the advantage of ARS; 2) currently ARS is not guaranteed to converge faster than RGF under non-convex problems. We leave more evaluation of ARS-based methods in adversarial attacks and further improvement of their performance as future work. Experimental results show that History-PRGF is more robust to learning rate than RGF. However, a small learning rate could still lead to its deteriorated performance due to non-smoothness of the objective function. The same statement holds for ARS-based algorithms.
sections.heading: 6 Conclusion and discussion
sections.text: In this paper, we present a convergence analysis on existing prior-guided ZO optimization algorithms including PRGF and History-PRGF. We further propose a novel prior-guided ARS algorithm with convergence guarantee. Experimental results confirm our theoretical analysis.
  Our limitations lie in: 1) we adopt a directional derivative oracle in our analysis, so the error on the convergence bound brought by finite-difference approximation has not been clearly stated; and 2) our implementation of PARS in practice requires an approximate solution of θt, and the accuracy and influence of this approximation is not well studied yet. We leave these as future work. Other future work includes extension of the theoretical analysis to non-convex cases, and more empirical studies in various application tasks.
sections.heading: Acknowledgements
sections.text: This work was supported by the National Key Research and Development Program of China (No. 2020AAA0104304), NSFC Projects (Nos. 61620106010, 62061136001, 61621136008, 62076147, U19B2034, U19A2081, U1811461), Beijing NSF Project (No. JQ19016), Beijing Academy of Artificial Intelligence (BAAI), Tsinghua-Huawei Joint Research Program, a grant from Tsinghua Institute for Guo Qiang, Tiangong Institute for Intelligent Computing, and the NVIDIA NVAIL Program with GPU/DGX Acceleration.
title: On the Convergence of Prior-Guided Zeroth-Order Optimization Algorithms