Zeroth-Order Optimization with Trajectory-Informed Derivative Estimation
Authors: Yao Shu
Zhongxiang Dai
Weicong Sng
Arun Verma
Patrick Jaillet
Bryan Kian Hsiang Low
Venue: ICLR 2023 poster (2023)
Keywords: zeroth-order optimization
derivative estimation
finite difference

Abstract: Zeroth-order (ZO) optimization, in which the derivative is unavailable, has recently succeeded in many important machine learning applications. Existing algorithms rely on finite difference (FD) methods for derivative estimation and gradient descent (GD)-based approaches for optimization. However, these algorithms suffer from query inefficiency because many additional function queries are required for derivative estimation in their every GD update, which typically hinders their deployment in real-world applications where every function query is expensive. To this end, we propose a trajectory-informed derivative estimation method which only employs the optimization trajectory (i.e., the history of function queries during optimization) and hence can eliminate the need for additional function queries to estimate a derivative. Moreover, based on our derivative estimation, we propose the technique of dynamic virtual updates, which allows us to reliably perform multiple steps of GD updates without reapplying derivative estimation. Based on these two contributions, we introduce the zeroth-order optimization with trajectory-informed derivative estimation (ZoRD) algorithm for query-efficient ZO optimization. We theoretically demonstrate that our trajectory-informed derivative estimation and our ZoRD algorithm improve over existing approaches, which is then supported by our real-world experiments such as black-box adversarial attack, non-differentiable metric optimization, and derivative-free reinforcement learning.

Published as a conference paper at ICLR 2023
ZEROTH-ORDER OPTIMIZATION WITH TRAJECTORY- INFORMED DERIVATIVE ESTIMATION
Yao Shu* Zhongxiang Dai*, Weicong Sng, Arun Verma, Dept. of Computer Science, National University of Singapore, Republic of Singapore (shuyao, , daí mhongxhg ang, sngwei cong, arun) @comp musseddu sg
Patrick Jaillet' & Bryan Kian Hsiang Low
Dept. of Electrical Engineering and Computer Science, MIT, USA
Dept. of Computer Science, National University of Singapore, Republic of Singapore jai fillletton @mit edu, Lowkh @ww.p @comp.cooppooooooooooooo rus. edu.sg
ABSTRACT
Zeroth-order (ZO) optimization, in which the derivative is unavailable, has recently succeeded in many important machine learning applications. Existing algorithms rely on finite difference (FD) methods for derivative estimation and gradient de- scent (GD)-base) bbsed approaches for optimization. However, these algorithms suffer from query inefficiency because many additional function queries are required for derivative estimation in their every GD update, which typically hinders their deployment in real-world applications where every function query expensive. To this end, we propose a snjjector-iiffomeer derivative estimation method which only employs the optimization trajectory (i.c., the history of function queries during optimization) and hence can eliminate the need for additional function queries estimate a derivative. Moreover, based on our derivative estimation, we propose the technique dynamic virtual updates, which allows us to reliably perform multiple steps of GD updates without reapplying derivative estimation. Based on these two contributions, we introduce the zeroth-order optimization with trajectory-informed derivative estimation (ZoRD) algorithm for query- query-efficieet ZO optimization. We theoretically demonstrate that our craeectoy-iiffomen derivative estimation and our ZoRD algorithm improve over existing approaches, which is then supported by our real-world experiments such as black-box adversarial attack, non-differentiable metric optimization, and derivative-free reinforcement learning.
INTRODUCTION
Zeroth-order (ZO) optimization, in which the objective function to be optimized is only accessible by querying, has received great attention in recent years due to its success many applications, e.g., black-box adversarial attack (Ru et al. 2020), non-differentiable metric optimization (Hiranandani ct al. 2021), and derivative-Fii free reinforcement learning (Salimans et al. 2017). In these problems, the derivative of objective function is either prohibitively costly to obtain
non-existent, making infeasible to directly apply standard derivative- algorithms such as gradient descent (GD). In this regard, existing works have proposed to estimate the derivative using the finite difference (FD) methods and then apply GD-based algorithms using the estimated derivative for ZO optimiza- tion NNsterov and Spokoiny 2017 Cheng al.) 2021 These algorithms, which we refer as GD with estimated derivatives. have been the most widely applied approach to ZO optimization especially for problems with high- sigh--imnnsional input spaces, because of their theoretically guaran- teed convergence and competitive practical performance. Unfortunately, these algorithms suffer from query inefficiency, which hinders their real-world deployment especially in applications with expensive-to-query objective functions, e.g., black-box adversarial attack.
Equal contribution.

---

Published as a conference paper at ICLR 2023
Specifically, one of the reasons for the query inefficiency of existing algorithms GD with estimated derivatives is that in addition to the necessary queries (i.e., the query of every updated input ! the FD methods applied in these algorithms require a large number of additional queries to accurately estimate the derivative at an inpul (Berahas et al., 2022). This naturally begs the question: Can we estimate derivative without any additional query? A natural approach to achieve this is to leverage the optimization trajectory, which is inherently available as a result of the necessary queries and their observations, to predict the derivatives. However, this requires non-trivial method simultaneously (a) predict a derivative using only the optimization trajectory (i.e., the history of updated inputs and their observations), and (b) quantify the uncertainty of this prediction to avoid using inaccurate predicted derivatives. Interestingly, the Gaussian process (GP) model satisfies both requirements and is hence a natural choice for such a derivative estimation. Specifically, under the commonly used assumption that the objective function is sampled from GP (Srinivas et al.] (0TO), the derivative at any input in the domain follows a Gaussian distribution which, surprisingly, can be calculated using only the optimization trajectory. This allows to (a) employ the mean of this Gaussian distribution as the estimated derivative, and (b) use the covariance matrix of this Gaussian distribution to obtain a principled measure of the predictive uncertainty and the accuracy of this derivative estimation, which together constitute our engjectory-iffomme derivative estimation (Sec.Ba 3.1.
Another reason for the query inefficiency of the existing algorithms GD with estimated deriva- tives is that every update in these algorithms requires reapplying derivative estimation and hence necessitates additional queries. This can preclude their adoption of large number of GD updates since every update requires potentially expensive additional queries. Therefore, another question arises: Can we perform multiple GD updates without reapplying derivative estimation and hence without any additional query? To address this question, we propose a technique named dynamic virtual updates (Sec. 3.2). Specifically, thanks to the ability of our method to estimate the derivative at any input in the domain while only using existing optimization trajectory, we can apply multi-step GD updates without the need to reapply derivative estimation and hence without requiring any new query. Moreover, we can dynamically determine the number of steps for these updates by inspecting the aforementioned predictive uncertainty at every step, such that we only perform an update if the uncertainty is small enough (which also indicates that the estimation error is small, see Sec. 4.1
By incorporating our aforementioned trajectory-informe derivative estimation and dynamic virtual updates into GD-based algorithms, we then introduce the zeroth- order optimization with trajectory- informed derivative estimation (ZoRD) algorithm for query-efficient ZO optimization. We theo- retically bound the estimation error of our trajectory-informed derivative estimation and show that this estimation error is non-increasing in the entire domain as the number of queries is increased and can even be exponentially decreasing in some scenarios (Sec. 4.1). Based on this, we prove the convergence of our ZoRD algorithm, which improves over the existing ZO optimization algorithms that rely on the FD methods for derivative estimation (Sec. 4.2). Lastly, we use extensive experiments, such as black-box adversarial attack, oon-differentiabee metric optimization, and derivative- free rein- forcement learning, to demonstrate that (a) our trajectory-infommes derivative estimation improves over the existing FD methods and that (b) our ZoRD algorithm consistently achieves improved query efficiency compared with previous ZO optimization algorithms (Sec.
2
PRELIMINARIES
2.1 PROBLEM SETUP
Throughout this paper, we use V and Ø₂ to denote, respectively, the total derivative (i.c., gradient) and partial derivative w.r. the variable æ. We consider the minimization of a black-box objective function f x + R, in which X' c Rdd is a convex subset of the d-dimensional domain:
min f(x) =EX
(1)
Since we consider Z0 optimization, the derivative information is not accessible and instead, we are only allowed to query the inputs in X. For every queried input x E X', we observe corresponding noisy output of y(z) f(x) + Ç, in which Ç is a zero-mean Gaussian noise with a variance of o
In practice, it is usually necessary to query every updated input to measure the optimization performance and select the hest-performing input. We refer to these queries necessary queries.
2

---

Published as a conference paper at ICLR 2023
Standard (Projected) GD with Estimated Derivatives
Algorithm 1:
Algorithm 2: ZoRD (Ours)
1: Input: In addition to the parameters Algo. set
1: Input: Objective function f: X' - IR, initialization æc. iteration number T, learning rates [ projection function (x
the steps of virtual updates (Vo)==1
2: for iteration t ,., do
3: 22,0 f- 2t-1
4: for iteration T =1, -,.... V₂ do
2: for iteration f ,,...,, T do
5: Dt,r < Px (Tt, ne,--1 V
3: ((x-11) R ( with 2
6: end for
4: Et + Px (#t-1 7h- (g()))1))
7: Query 2;, = 2t,r to yield y(xx))
5: Query o; to yield v(x,,)
8: Update ( using optimization trajectory
6: end for
9: end for
7: Return arg mig Fr v()
10: Return arg min ((x)
Ç <~N(0, *N(00.0), )²) Besides, we adopt common assumption on f which has already been widely used in the literature of Bayesian optimization (BO) (Srinivas et al. 2010 Kandasamy et 2018): we assume that I' is sampled from a Gaussian prucess (GP). A GP (P(jj-),,( k(;;)) )), which characterized by a mean function ju(-) and covariance function k(( ),, is stochastic process in which any finite subset of random variables follows a multi-variate Gaussian distribution (Rasmussen and Williams (006). In addition, following the common practice of GP and BO, we assume w.l.o.g. that μ(æ)) 0 and k(x, x²) S (Vx, x' E X We also assume that the kernel function is differentiable, and that [0=00,,kzz,z) ==>=====1= S x Yas X for some k > 0. This is satisfied by most commonly used kernels such as the squared exponential (SE) kernel (Rasmussen and Williams 2006).
2.2 ZO OPTIMIZATION WITH ESTIMATED DERIVATIVES
To solve (T). GD with estimated derivatives (c.g.. Algo. has been developed FFaxxman al. 2005; Ghadimi and Lan 2013 Nesterov and Spokoiny 2017 Liu et al. 201 8a b). Particularly, these algorithms first' estimate the derivative of f (line of Algo. 1 and then plug the estimated derivative into GD-based methods to obtain the next input for querying (lines 4-5 of Algo. In these algorithms, the derivative is typically estimated by averaging the finite difference approximation of the directional derivatives for f along certain directions, which we refer to as the finite difference (FD) method in this paper. For example, given a parameter À and directions {u, ) the derivative f at any X' can be estimated by the following FD method (Berahas et al. 2022
y(a + Xua)) y(x)
Vx(x) R g(x)
The directions /= are usually sampled from the standard Gaussian distribution (Nesterov and Spokoiny 2017) or uniformly from the unit sphere (Flaxman et al., 2005), or set as the standard basis vectors with at one of its coordinates and 0 otherwise (Lian al.) 2016). As mentioned before, existing FD methods typically require many additional queries (i.e., x + > to achieve an accurate derivative estimation in every iteration of Algo. (Berhhas et al. p.22p. making existing ZO
optimization algorithms (Flaxman et al. 2005 Nesterov and Spokoiny 2017 query-inefficient.
3 ZO OPTIMIZATION VIA TRAJECTORY-INFORMER DERIVATIVE ESTIMATION
To improve existing GD with estimated derivatives (e.g., Algo. T). we propose the ZoRD algorithm (Algo. 2 which achieves more query-efficient ZO optimization thanks to our two major contributions. Firstly, we propose a derived GP-based derivative estimation method which only uses the optimization trajectory and consequently does not require any additional query for derivative estimation (Sec. 3.1pp Secondly, thanks to the ability of our method to estimate the derivative at any input in the domain without any additional query and to measure the estimation error a principled way, we develop the technique of dynamic virtual updates to further improve the query efficiency of our ZoRD (Sec.
3.1 TRAJECTORY DERIVATIVE ESTIMATION
To begin with, if a function f follows GP, then its derivative V also follows a GP (Rasmussen and Williams| 2006). This is formalized by our Lemma] I below (proof in Appx. B.I.. which then provides us principled way to estimate the derivative at any input in the domain.
3

---

Published as a conference paper at ICLR 2023
Lemma (Derived GP for Derivatives). If a function f follows GP: f GP of then
Vf GP (Vp(),
where (.? denotes the cross partial derivative w.r. the first and second arguments of (',.))
I Follows the Posterior GP. As discussed Sec. 2.1 we assume that f ~ GP(u()) ((:,))
So, in every iteration of our Algo. conditioned on the current optimization trajectory D _ (er, yr) )r=) f follows the posterior GP: f ~ GP (Hi-1(), of-(())))))))))))) with the mean function 4--1(-) and the covariance function o7-1(:, defined as below (Rasmussen and Williams 2006):
14-1 (x)) - ki (a)) (K,-1 +2 y:-1 (2, x') - k (x, x²) (x=) ( K.-1 (a')
(3)
where v A |u- and k (x) [k(2, az, )=));= are (t -)-dimension row vectors, and K;-1 - ik 2.,) -| a (t- 1) (t- didimennion matrix. Define 07-1(x) & of (z,
the posterior distribution at x is Gaussian with mean (z= and variance o
ff Follows the Derived GP for Derivatives. Substituting 3 into Lemma
we have that
Vf ~ GP (V
(4)
x' are in which the mean (x) at and the covariance 1 (z, x²)
V V/t- A 0z (z) (K + o²1) y1-1 z-
(5)
10, x') 0_ x') 02 (z)
+ o 11)))
in which 1z) e (0_k(z, xz- )[=1 is 1 1) d-dimensional matrix and 0-02. z²) is a d-dimensional matrix. Therefore, Vpt (x) is d-dimensional vector and do? (xx, x' is d x d-dimensional matrix. We refer to this GP (4) followed by V as the derived GP for derivatives.
So, define (z) _ (0, æ) we have that for any input a: E X, the derivative V (x) at æ follows d-dimensional Gaussian distribution: fx(x) ~ -V(V)t,1 (xx), | (x)). This allows us to (a) estimate the derivative V (x) at any imput x X using the posterior mean V of the
derived GP for derivatives
(6) and (b) employ the posterior covariance matrix dož_ (ax) to obtain principled measure of the uncertainty for this derivative estimation, which together constitute our novel derivative estimation. Remarkably, our derivative estimation only makes use of the naturally available optimization trajectory Di-1 and does not need any additional query. which is in stark contrast to the existing FD methods (e.g.. 2b) that require many additional queries for their derivative estimation. Moreover, our principled measure of uncertainty allows to perform dynamic virtual updates (Sec. 3.2) and theoretically guarantee the quality of our derivative estimation (Sec. 4.1)
Vs(x) & (x)-
3.2 DYNAMIC VIRTUAL UPDATES
Note that derived GP-based derivative estimation (6) can estimate the derivative any input within the domain. As a result, in every iteration of our ZoRD algorithm, for a step т 2 1, after reach the
performing GD update using the estimated derivative at #t,r-1 (i.e., 1 input Øt,r (line 5 of Algo. 2) we can again estimate the derivative at Ør,r (i.e., 1 )) and then perform another GD update reach 11, without requiring any additional query. This process can be repeated for multiple steps, and can further improve the query efficiency of our ZoRD. Formally, given the projection function (x) arg min | =
V--1 =||2 /2 and learning rates [V- we perform the following virtual updates for V, steps (lines 4-6 of Algo. 2
Ct.F Px ( 7 7
1,
and then choose the last V,,v; to query (i.c., line 7 of Algo. D Importantly, these multi step virtual GD updates only feasible in our ZoRD (Algo. 2 because our derivative estimator )6) does not
4

---

Published as a conference paper at ICLR 2023
require any new query in all these steps, whereas the existing FD methods require additional queries to estimate the derivative in every step.
The number of steps for our virtual updates (i.c., Vi) induces intriguing trade-off: An overly small V may not be able to fully exploit the benefit of our derivative estimation (6) which is free from the requirement for additional queries, yet an excessively large V2 may lead to the usage of inaccurate derivative estimations which can hurt the performance (validated in Appx. D.2) Remarkably, (4) allows us to dynamically choose V, by inspecting our principled measure of the predictive uncertainty (i.e., - (z)) for every derivative estimation. Specifically, after reaching the input Lt,r. we continue
the virtual updates (to reach +(,,++1) if our predictive uncertainty is small, i.e., if | ( >)2 s where e a confidence threshold; otherwise, we terminate the virtual updates and let V, = T since the derivative estimation at Dt,r is likely unreliable
4 THEORETICAL ANALYSIS
4.1 DERIVATIVE ESTIMATION ERROR
To begin with, we derive theoretical guarantee on the error of our derivative estimation at any æ.
Theorem 1 (Derivative Estimation Error). Let E (0,1) and 3 - / 2(vd+ ( ln(1/))) For any x E X and any 2 1, the following holds with probability of at least -6, 6,
[V)() Vpr(z))l22 S Bv (1))
Thm. (proof in Appx. B.2
has presented an upper bound on the error of our derivative estimation (6) any æ E X' in terms of y [ which is measure of the uncertainty about our derivative estimation at æ (Sec. 3.T. This hence implies that the threshold applied to our predictive uncertainty [ (Sec. 3.2) also ensures that the derivative estimation error is small during our dynamic virtual updates. Next, we show in the following theorem (proof in Appx. [B3) that our upper bound on the estimation error from Thm. iss non-increasing as the number of function queries is increased.
Theorem (Non-Increasing Error). For any æ E X and any 2 1, we have that
| 1|2 - | |00. (a))
Let& 5 E 1). Define r - maX v [00 112 ( 2 given the B3 in Thm.
we
then have that E [1/ 1], and that with probability of at least 1 8,
S B 1/1100/ [V(+))VV((}]]
S Krrr"
Thm. shows that our upper bound on the derivative estimation error (i.e., /v (x)0) Thm. is guaranteed to be -occircceas in the entire domain as the number of function queries is increased. Moreover, in some situations (i.e., when r < 1), our upper bound on the estimation error even exponentially decreasing. Of note, characterizes how fast the uncertainty about our derivative estimation (measured by / O|0o7 (x) )l2) is reduced across the domain. Since GD--baed algorithms usually perform a local search in neighborhood (especially for the problems with high-dimensional input spaces), all the inputs within the local region are expected to be close to each other (measured by the kernel function k). Moreover, as the objective function is usually smooth in the local region continuous), reducing the uncertainty of the derivative an input æ; (i.e., by
(x)ll2 from
(i.e., its derivatives querying 2;)) is also expected to decrease the uncertainty of the derivatives at the other inputs in the same local region (i.e., decrease / VIāaa (x: 112) So, r < 1 is expected to be a reasonable condition that can be satisfied in practice. This will also be corroborated by our empirical results (e.g., Figs. [ and 2), which demonstrates that the error of our derivative estimation (6) is indeed reduced very fast.
Our GP-based Method (6) vs. Existing FD Methods. Our derivative estimation method based on the derived GP 6 is superior to the traditional FD methods (e.g., ( in number of major aspects. (a) Our derivative estimation error can be exponentially decreasing in some situations (i.c., when 1 in Thm. 2). which is unachievable for the existing FD methods since they can only
The first step of GD update reach 21,1 always performed, i.e., V
5

---

Published as a conference paper at ICLR 2023
attain polynomial rate of reduction (Berahas et al. 2022). (b) Our method (6) does not need any additional query to estimate the derivative (but only requires the optimization trajectory), whereas the existing FD methods require additional queries for every derivative estimation. (c) Our method (6) is equipped with principled measure of the predictive uncertainty and hence the estimation error for derivative estimation (i.e., via v|do (2>)]> 12- Thm. I which is typically unavailable for the existing FD methods. (d) Our method (6). unlike the existing FD methods, makes it possible to apply the technique of dynamic virtual updates (Sec. (.2) thanks to its capability of estimating the derivative at any input in the domain without requiring any additional query and measuring the estimation error in
a principled way (Thm.
4.2 CONVERGENCE ANALYSIS
To analyze the convergence of our ZoRD, besides our main assumption that f is sampled from a GP (Sec. 2.1,, we assume that f is L--ppchittz continuous for Le 0. This is a mild assumption since it has been shown that a function f sampled from a GP is Lipchitz continuous with high probability for commonly used kernels, e-g-, the SE kernel and Matérn kernel with v > 2 (Srinivas et al. 2010).
We also assume that f is Lipchitc smooth, which is commonly adopted in the analysis GD-based algorithms (J Reddi et al. 2016). We aim prove the convergence of our ZoRD for nonconvex
by analyzing how fast it converges to a stationary point (Ghadimi and Lan 2013
Liu et al.
2018a).
Specifically, we follow the common practice of previous works (J Reddi al. 2016 Liu et 2018b
to analyze the following derivative mapping:
GG A ( - Px - Te. (T ))) /m..-
(8)
The convergence of our ZoRD is formally guaranteed by Thm. B beloo (proof in Appx. B.4.
Theorem 3 (Convergence of ZORD). Let d E (0, 1). Suppose our ZORD (Algo. 2 is run with V2 = V and mh, = 11 S 1/ L., for any and r. Then with probability of at least
when r < 1,
V-1
(0)())) -f(x"))
202²2
(2L 1/n)aar
mit EST
Σ
G 5
TV
T(1 - r2)
T(1 (11-)
==0
where & A KV d + 2(
In (VT/O). When r = 1, we instead have 2 2a² + (2L + 1/n)a.
In the upper bound of Thm. 3. the term I represents the convergence rate of (projected) GD when the true derivative is used and asymptotically goes to 0 T increases; the term 2 corresponds to the impact of the error of our derivative estimation (6) on the convergence. In situations where r < 1 which is a reasonably achievable condition as we have discussed in Sec. 4.1 the term ② will also asymptotically approach 0. This, remarkably. suggests that the impact of the derivative estimation error on the convergence vanishes asymptotically and our ZoRD algorithm is guaranteed to converge to a stationary point (i.e., minest 7 Σ =r= |Gr,r 1l2 approaches 0) at the rate of ((1/T) when < 1. This is unattainable by existing ZO optimization algorithms using FD-based derivative estimation (Nesterov and Spokoiny] 2017 Liu et al.) 2018b). because these methods typically converge to a where
stationary point at the rate of O177 + const.) with constant learning rate. Even when the term 2 becomes a constant independent of T, our Thm. 3 is still superior to the convergence of these existing works because our result (Thm. 3 is based on the worst-case analysis whereas these works are typically based on the average-case analysis, i.c., their results only hold in expectation over the randomly sampled directions for derivative estimation. This means that their convergence may become even worse when inappropriate directions are used, e.g., directions that are nearly orthogonal to the true derivative which commonly happens in high--imenssonal input spaces. In addition, given a fixed T, our ZoRD enjoys a query complexity (i.e., the number of queries in T iterations) of O(T), which significantly improves over the (nTT) of the existing works based on FD (n in Sec. 2.2
The impacts of the number of steps of our virtual updates (i.e., V) are partially reflected in Thm. Specifically, larger V improves the reduction rate of the term ① because larger number of virtual GD updates (without requiring additional queries) will be applied in our ZoRD algorithm. This is also unachievable by existing ZO optimization algorithms using bD-based derivative estimation since they require additional queries for the derivative estimation in their every GD update. Meanwhile, larger V may also negatively impact the performance of our ZoRD since it may lead to the use of those estimated derivatives with large estimation errors (Sec. 3.2 However, this negative impact has

---

Published as a conference paper at ICLR 2023
3
6
12
2-
Derivative
0-
-2-
-2
-5
-5
-5
5
-5
Function Queries
Vp
Figure 1: Our derived GP for derivative estimation curve and its confidence interval denote the mean Vuc
4
with different number of queries. Green
a
and standard deviation of the derived GP.
= 0.5
a=
A 0.5
A= 0.1
Cormre Siibaity
0oo0000yo00e
Eusiidean Dibtrree
Ookine Simikaity
1.00
Eusiddai Distrrce
Cosire Similaity
1.00
Eucldhenn Ditarree
Ooenn Simbarity
Eusiieen Disurro
0.75
0.75
FD
FD
0.50
0.50
00000000000
0.25
20
60
0.00
20
40
80
80
20
40
60
40
60
Querria
Total
(b)
Figure 2: Comparison of the derivative estimation errors of our derived GP-based estimator (6) (GP) and the FD estimator, measured by cosine similarity (larger is better) and Euclidean distance (smaller is better). Each curve is the mean + standard error from five independent runs.
only been implicitly accounted for by the term @ because this term comes from our Thm. which is based on a worst-case analysis and gives a uniform upper bound on the derivative estimation error for all inputs the domain X.
EXPERIMENTS
In this section, we firstly empirically verify the efficacy of our derived GP-based derivative estimator (6) in Sec. 5.1 and then demonstrate that ZoRD outperforms existing baseline methods for ZO
optimization using synthetic experiments (Sec. 5.2) and real-world experiments (Secs. 5.3 5.4).
5.1 DERIVATIVE ESTIMATION
Here we investigate the efficacy of our derivative estimator (6) based on the derived GP for derivatives (4) Specifically, we sample function f (defined on one-dimensional domain) from GP using the SE kernel, and then use a set randomly selected inputs as well as their noisy observations (as optimization trajectory) calculate our derived GP for derivatives. The results (Fig. D illustrate number of interesting insights. Firstly, in regions where (even only a few) function queries are per- formed (e.g., g., in the region of [-3, 0)), our estimated derivative (i.e., V 1 (ar) (6) generally aligns with the groundtruth derivative (i.e., (x=)) and our estimation uncertainty (i.e., characterized by
-|(0,;_,(>)|] shrinks compared with other un-queried regions. These results hence demonstrate that our (4) is able accurately estimate derivatives and reliably quantify the uncertainty of these estimations within the regions where function queries are performed. Secondly, as more input queries
are collected (i.e., from left to right in Fig. 1). the uncertainty / / (xx)]| in the entire domain
decreased in general. This provides an empirical justification for our Thm. 2 which guarantees non-increasing uncertainty and hence non- iep-increasing estimation error. Lastly, note that with only 12 queries (rightmost figure), our derivative estimator already able accurately estimate the derivative in the entire domain, which represents a remarkable reduction rate of our derivative estimation error.
Next, we compare our derivative estimator (6) with the FD estimator (Sec. 2.2 Specifically, using the Ackley function with d = 10 (see Appx. C.2 we firstly select an input and then follow the
1n FD method (2) to randomly sample n directions u. := from the standard Gaussian distribution, to construct input queries { Au; hi= (see Sec. 2.2 Next, these queries and their observations
(a) used as the optimization trajectory to apply our derivative estimator (6) and (b) used by the FD method to estimate the derivative following (2). The results are shown in Fig. 2 (for two different
values of A). in which for both our derived Ga-ba estimator (6) and the FD estimator, we measure the cosine similarity (larger is better) and Fuclidean distance (smaller is better) between the estimated
7

---

Published as a conference paper at ICLR 2023
5.00
Optimlyy thg (o
Cptinalty Gup the s0a
Oytimsty Cop (ng 500000
Oytimaily Cap (ing s0300)
4.75
G-
2250
4.30
4.2
18-
PGP
4.00
0.1
40
66
1480
3.75
codoenee
1.00
3.50
100
150
100 Quario
150
100
200
100
200
300
400
Quaries
Quuries
Queres
(a) Ackley (d = 20)
(b) Ackley (d 40)
(c) Levy (d 40)
(d) Levy (d 100)
Figure: 3: Optimization of Ackley and Levy functions with different dimensions. The x-axis and y- axis denote the number of queries and log-scaled optimality gap (i.e., log (f(xT) f(x*)) achieved after this number of queries. Each curve is the mean + standard error from ten independent runs.
Table I:
Comparison of the number of required queries to achieve a successful black-box adversarial attack. Every entry represents mean + standard deviation from five independent runs.
Dataset
Metric
GLD
RGF
PRGF
TuRBO-1
TuRBO-10
ZoRD
# Queries Speedup
1780#222
1192::260
1236::14
654:70
747:600
248::50
MNIST
7.2x
4.8x
5.0x
2.6x
3.0x
1.0x
# Queries
9641175
1155
4133
6381: 1.7x
708-105
384.559
CIFAR-10
Speedup 2.5x
9.4x
10.8
1.8x
1.0x
derivative and the true derivative Zo- The figures show that our derivative estimation eπrоr enjoys faster rate of reduction compared with the FD method, which corroborates our theoretical insights from Thm. 2 (Sec.F 4.1 positing that our estimation error be rapidly decreasing. Subsequently, to further highlight our advantage of being able to exploit the optimization trajectory and hence to climinate the need for additional function queries (Sec. 4.1 we perform another comparison where our derived GP-based estimator (6) only utilizes 20 queries from the optimization trajectory (sampled using the same method above) for derivative estimation. The results (Fig. 2p) show that even with only these 20 queries (without any additional function query), our derivative estimator (6) achieves comparable or better estimation errors than FD using as many as 80 additional queries. Overall, the results in Fig. 2 have provided empirical supports for the superiority of our derived GP-based derivative estimation (6. which substantiates our theoretical justifications in Sec.
5.2 SYNTHETIC EXPERIMENTS
Here we adopt the widely use Ackley and Levy functions with various dimensions (Eriksson et al. 2019) to show the superiority of our ZoRD. We compare ZoRD with number of representative baselines for ZO optimization, e.g., RGF (Nesterov and Spokoiny (017) which uses FD for derivative estimation, PRGF (Cheng et al. 20221) which is recent extension of RGF, GLD (Golovin et al. (020)) which is a recent ZO optimization algorithm based on direct search, and TuRBO (Eriksson et al. 2019) which is highly performant Bayesian optimization (BO) algorithm. We also evaluate the performance of a first-order optimization algorithm, i.e., GD with true derivatives. More details are in Appx. C.2 The results are shown in Fig. 3 where ZoRD outperforms all other ZO optimization algorithms. Particularly. ZoRD considerably outperforms both RGF and PRGF, which can be attributed our two major contributions. Firstly, our derivative estimator (6) used by ZoRD is more accurate and more query-efficient than the FD method adopted by RGF and PRGF, as theoretically justified in Sec. Sec. [and empirically demonstrated Sec. 5.1 Secondly, our dynamic virtual updates (Sec. 3.2) can perform multi-step GD updates without requiring any additional query, which further improves the performance optimization algorithm that is able to converge to comparable final performance to that of the GD with true derivatives in every figure of Fig.
ZoRD (validated in Appx. D.2). Moreover, ZORD is the only ZO
5.3 BLACK-BBOX ADVERSARIAL ATTACK
We further compare our ZoRD with other ZO optimization algorithms in the problem of black-bor box adversarial attack images, which is one of the most important applications of ZO optimization in recent years. In black-box adversarial attack (Ru et al. 2020), given a fully trained ML model and an image 2, we intend to find (through only function queries) small perturbation be added
8

---

Published as a conference paper at ICLR 2023
25
GL0
2.0
2010
Improvettnnn
1.5
0.
200
200
400
600
200
400
800
200
600
Gueries
Cueries
Quertes
Quurties
(a) Precision
(b) Recall
(c) F1 Score
(d) Jaccard index
Figure 4: Optimization of different con-differentiable metries on the Covertype dataset. The rraxis and y-axis denote, respectively, the number of queries and the improvement on the non-differentiable metric. Each curve is the mean standard error from five independent experiments.
such that the perturbed image practice from (Cheng et al. 2021), ). we randomly select an image from MNIST (Lecun et al. 1998)
will be incorrectly classified by the ML model. Following the
(d = 28 28) or CIFAR-1 10 (Krizhevsky al. 2009) (d 32 32), and aim to add perturbation
with an Loe constraint to make trained deep neural network misclassify the image (more details in Appx. C.3) Tab. summarizes the number of required queries achieve a successful attack by different algorithms (see results on multiple images in Appx. D.3) The results show that in such high- nigh-dimensional ZO optimization problems, our ZoRD again significantly outperforms the other algorithms since it requires a considerably smaller number of queries to achieve a successful attack. Particularly, our ZoRD substantially more query-efficient than RGF and PRGF which rely on the FD methods for derivative estimation, e.g.. for CIFAR-10 10, the number of queries required by RGF and PRGF are 9.4x and 10.8x of that required by ZoRD. This further verifies the advantages of our trajectory-infonet in Sec. (.1) and dynamic virtual updates (as demonstrated in Appx. D.2). Remarkably, our ZoRD also outperforms BO (i.e., TuRBO-1/10 which correspond to two versions of the TuRBO algorithm (Eriksson et al. 2019)) which has been widely shown to be query-efficient in black- -bx adversarial attack (Ru al. 2020). Overall, these results showcase the ability of ZoRD to advance the other ZO optimization algorithms in challenging real-world ZO optimization problems.
derivative estimation (as justified theoretically in Sec. [4.1 and empirically
5.4 NON-DIFTERENTIABLE METRIC OPTIMIZATION
Non-differen dindeifferentialee metric optimization (Hiranandani et al. 2021 Huang al., 2021), which has received surging interest recently, can also be cast as a '00 optimization problem. We therefore use it to further demonstrate the superiority of our ZoRD to other 70 optimization algorithms. Specifically, we firstly train a multilayer perceptron (MLP) (d = 2189) on the Covertype (Dua and Graff 2017) dataset with the cross-entropy loss function. Then, we use the same dataset fine-tune this MLP model by exploiting ZO optimization algorithms to optimize non- non-differentiable metric, such as precision, recall, Fl score and Jaccard index (see more details in Appx. Here we additionally compare with the evolutionary strategy (ES) which has been previously applied for non non- con-differentiable metric optimization (Huang et al. 2021). Fig- f illustrates the percentage improvements achieved by different algorithms during the fine-tuning process (i.e., (f(mz) f(TT)) 100% / [(xo)) The results show that our ZoRD again consistently outperforms the other ZO optimization algorithms in terms of both the query efficiency and the final converged performance. These results therefore further substantiate the superiority of ZoRD in optimizing high-dimensional non-differentiable functions.
CONCLUSION
We have introduced the ZoRD algorithm, which achieves query-efficient 70 optimization through two major contributions. Firstly, we have proposed a novel derived GP-based method (6) which only uses the optimization trajectory and hence eliminates the requirement for additional queries (Sec. 3.1 to estimate derivatives. Secondly, we have introduced novel technique, i.e., dynamic virtual updates, which is made possible by our Ga-based derivative estimation, to further improve the performance of our ZoRD (Sec. 3.2). Through theoretical justifications (Sec. 4 and empirical demonstrations (Sec. 5). we show that our derived GP-based derivative estimation improve over existing FD methods and that ZoRD D outperforms various 70 optimization baselines.

---

Published as a conference paper at ICLR 2023
7 REPRODUCIBILITY STATEMENT
For our theoretical results, we have discussed all our assumptions in Sec. 2.1 & Sec. 4.2 and provided our complete proof's Appx. B For our empirical results, have provided our detailed experimental settings in Appx. C and included our codes in the supplementary materials (i.e., the zip file).
ACKNOWLEDGMENTS
This research is part of the programme DesCartes and supported by the National Research Founda- tion, Prime Minister's Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme.
REFERENCES
Binxin Ru, Adam D. Cobb, Amo Blaas, and Yarin Gal. Bayesopt adversarial attack. In Proc. ICLR, 2020.
Gaurush Hiranandani, Jatin Mathur, Harikrishna Narasimhan, Mahdi Milani Fard, and Sanmi Koyejo. Optimizing black-box metrics with iterative example weighting. In Proc. ICML, 2021.
Tim Salimans, Jonathan Ho, Xi Chen, and Ilya Sutskever. Evolution strategies as a scalable alternative to reinforcement learning. AKIi:1703.03864 2017.
Yurii E. Nesterov and Vladimir G. Spokoiny. Random gradient- minimization of convex functions. Found. Comput. Math., 17(2):277-56,, 2017.
Shuyu Cheng, Guoqiang Wu, and Jun Zhu. On the convergence of prior-guided zeroth-order optimization algorithms. In Proc. NeurlPS, 2021.
Albert S. Berahas, Liyuan Cao, Krzysztof Choromanski, and Katya Scheinberg. A theoretical and empirical comparison of gradient approximations in derivative-free optimization. Found. Comput. Math., 2202),507-560, 2022.
Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proc. ICML, 2010.
Kirthevasan Kandasamy, Akshay Krishnamurthy, Jeff Schneider, and Barnabás Póczos. Parallelised Bayesian optimisation via Thompson sampling. Proc. AISTATS, 2018.
Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian processes for machine learning. Adaptive computation and machine learning. MIT Press, 2006.
Abraham Flaxman, Adam Tauman Kalai, and H. Brendan McMahan. Online convex optimization in the bandit setting: Gradient descent without gradient. In Proc. SODA, 2005.
Saced Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2368, 2013.
Sijia Liu, Bhavya Kailkhura, Pin-Yu Yu Chen, Pai-Shun Ting, Shiyu Chang, and Lisa Amini. Zeroth- order stochastic variance reduction for nonconvex optimization. In Proc. NeurIPS, 2018a.
Sijia Liu, Xingguo Li, Pin- Yu Chen, Jarvis D. Haupt, and Lisa Amini. Zeroth-order stochastic projected gradient descent for nonconvex optimization. In Proc. GlobalSIP, 2018b.
Xiangru Lian, Huan Zhang, Cho-Jui Hsich, Yijun Huang, and Ji Liu. A comprehensive linear speedup analysis for asynchronous stochastic parallel optimization from zeroth-order first-order. In Proc. NIPS, 2016.
Sashank J Reddi, Suvrit Sra, Barnabas Poczos, and Alexander Smola. Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization. Proc. NIPS, 2016.
David Eriksson, Michael Pearce, Jacob R. Gardner, Ryan Turner, and Matthias Poloczek. Scalable global optimization via local Bayesian optimization. In Proc. NewrIPS, 2019.
10

---

Published as a conference paper at ICLR 2023
Daniel Golovin, John Karro, Greg Kochanski, Chansoo Lee, Xingyou Song, and Qiuyi (Richard) Zhang. Gradientless descent: High- nigh-diimensionl zeroth-order optimization. In Proc. ICLR, 2020.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, pages 2278-2324, 1998.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Chen Huang, Shuangfei Zhai, Pengsheng Guo, and Josh M. Susskind. Metricopt: Learning optimize black-box evaluation metrics. In Proc. CVPR, 2021.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http::
ics. uussuuciedd..
Sebastian U Stich, Christian L Muller, and Bernd Gartner. Optimization of convex functions with random pursuit. SIAM Journal on Optimization, 23(2):1284-1309 2013.
Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In Proc. ICML, 2017.
Zhongxiang Dai, Haibin Yu, Bryan Kian Hsiang Low, and Patrick Jaillet. Bayesian optimization meets Bayesian optimal stopping. In Proc. ICML, 2019.
Zhongxiang Dai, Bryan Kian Hsiang Low, and Patrick Jaillet. Federated bayesian optimization via thompson sampling. In Proc. NeurlPS, 2020.
Benjamin Letham, Roberto Calandra, Akshara Rai, and Eytan Bakshy. Re-examining linear embed- dings for high-dimensional Bayesian optimization. In Proc. NeurIPS, 2020.
Andrew Ilyas, Logan Engstrom, and Aleksander Madry. Prior convictions: Black-box adversarial attacks with bandits and priors. In Proc. ICLR, 2019.
Florian Meier, Asier Mujika, Marcelo Matheus Gauy, and Angelika Steger. Improving gradient estimation in evolutionary strategies with past descent directions. arXivv1910005268, 2019.
Niru Maheswaranathan, Luke Metz, George Tucker, Dami Choi, and Jaseha Sohl-Dickstein. Guided evolutionary strategies: Augmenting random search with surrogate gradients. In Proc. ICML, 2019.
Shuyu Cheng, Yinpeng Dong, Tianyu Pang, Hang Su, and Jun Zhu. Improving black-box adversarial attacks with transfer-based prior. In NeurlPS, 2019.
Beatrice Laurent and Pascal Massart. Adaptive estimation of quadratic functional by model selection. Annals of Statistics, pages 1302-1338, 2000.
Sayak Ray Chowdhury and Aditya Gopalan. No-regret algorithms for multi-task Bayesian optimiza- tion. In Proc. AISTATS, 2021.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2014.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proc. ICLR, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Proc. CVPR, 2016.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. OpenAl Gym. arXiv:1606.0155 2016.
M. D. McKay, R. J. Beckman, and W. J. Conover. A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics, 21(2): 239-245 1979.
Jian Tan, Niv Nayman, and Mengchang Wang. CobBO: Coordinate backoff Bayesian optimization with two-stage kernels. MxXiv22011005147 2021.
Hong Qian and Yang Yu. Derivative-free reinforcement learning: A review. Frontiers Comput. Sci., 15(6):553336 2021.
11

---

Published as a conference paper at ICLR 2023
APPENDIX A RELATED WORK
Various types of algorithms have been proposed in the literature to solve ZO optimization problems, e.g., direct search, Bayesian optimization (BO) and GD-based algorithms with estimated derivatives. Particularly, direct search, e.g., (Stich et al. 2013 Golovin et al. 2020), relies on the comparison of function values at different inputs for the updates, which can be query-inefficiie
in practice owing to its indirect utilization of function values. In contrast, Bayesian optimization (BO) directly utilizes the function values to model the objective function using Gaussian process (GP) and iteratively selects the inputs to query by trading off sampling potentially optimal inputs (i.e., exploitation) and inputs that can improve the GP belief of the objective function over the entire imput domain (i.e., exploration) Chowdhhur and Gopalan 2017 Srinivas et al. 2010: Dai et al. 2019 2020). However, in ZO optimization problems with high-dimensional input spaces, BO algorithms typically suffer from query inefficiency and large computational complexity (Rasmussen and Williams| 2006; Letham et al., 2020: Eriksson et al., 2019), which significantly hinders their real-world applications. Therefore, GD-based algorithms with estimated derivatives, which inherit the advantage of GD-based algorithms in optimizing functions with high-dimensional input spaces, have been more widely applied in practice. For these algorithms, the derivatives commonly estimated using the finite difference (FD) approximation (which requires additional function queries) of the directional derivatives along selected directions, in which the directions (2005), Gaussian vectors (Nesterov and Spokoiny] 2017). or standard bases (Lian et al. (0166) (Sec. 2.2 More recently, some works have incorporated a time-dependent prior (i.c., the estimated derivative in the previous iteration) into existing FD methods to improve the quality of its derivative estimation Myas et al., 2019, Meier al. 2019 Cheng et al., (02T). Nevertheless, such prior is also estimated by the FD method (i.e., in the previous iteration) and can hence be biased owing to the its estimation error, which may even lead larger derivative estimation errors in practice due to compounding errors. Another line of work has taken the surrogate derivatives from other sources to help reduce the derivative estimation error of existing FD methods (Maheswaranathan et al. 2019 Cheng et al. 2019). However, these surrogate derivatives may generally be unavailable in practice. Importantly, these existing FD methods require additional function queries for every derivation estimation during optimization, which will significantly increase the query complexity of Zo optimization algorithms which employ these FD methods for derivative estimation.
be randomly sampled unit vectors Flaxman al.
APPENDIX B PROOFS
B.1
PROOF OF LEMMA I
According to Rasmussen and Williams (206)). if function f follows from Gaussian process, its derivative also follows a Gaussian process determined by its mean E[.] and covariance Cov(:,) i.. i.e.
Vf ~ GP (L [V Cov(V v))
So, to prove Lemma I we only need to derive the mean and the covariance of the Gaussian process above for function J that is sampled from another Gaussian process, i.e., f ~ of Specifically, for the mean E [V,,, we have
E V = VB Vu.
(10)
where the first equality derives from the interchangeability of the expectation and derivative operation based on the Leibniz integral rule. The second equality comes from the fact that E [f] = μ.
For the covariance Cov(V. Vf), we have
Cor(V/()) vf(z)) (a) E
-V -[V -V/+)) B[V(()
E
V (J(=) - E[(()))) (J(=') - --(-==(())))
B 0.000 (f(=) - -I(()))) (((==)))(((=))))))) =(((=)))
(II)
-
" (1(=) [[(=)=B[[==]) ((((=))))(((())))>)))))))))))))) -E(((=)))
@ (z,
12

---

Published as a conference paper at ICLR 2023
Notably, (6) and (d) also derive from the interchangeability of the expectation and derivative operation based on the Leibniz integral rule. Besides, (e) is obtained based on Cov(f, f) = o (²)))) This finally completes proof.
B.2 PROOF OF THEOREM 1
To begin with, we introduce the following concentration inequality for standard multi variate Gaussian distribution:
Lemma B.1 (Laurent and Massart 2000)), Let Ç (0, and (0, 1) then
P [1ll12 V mm m+ 1m++2(vm)) ((Vm+1))n(/ ln 2 11-6 8.
(12)
Define Ç f (0o) 1/2 (z) (x)())), according Lemma ! we then have that C follows a standard multi-vann vulti-variate Gaussian distribution, i.c.,
OO.
(13)
Let 8 E (0, 1). By substituting the result above into Lemma B.1 the following holds with probability of at least 8:
[V(()) (n((2)122 (00)(zr)) - 1/2 <|p
s (002(2))
(14)
d+
(1000(()111
= 10))
with 8 2 V d + 2(vd + 1) In(1/6) and the first inequality is from the Sauchy-Schwarz inequality,
which completes our proof.
B.3 PROOF OF THEOREM 2
We first introduce the following lemmas.
Lemma B.2 (Chowdhury and Gopalan (021 For any E IR and any matrix A, the following hold
I A (AAT +021) A (AT
(15)
Lemma B.3 (Sherman- Morrison formula). For any invertible square matrix A and column vectors u, U, suppose A uv is invertible, then the following holds
Ahherman-Morrioon
A A-'uv
uv
A
(A + uv
=
(16)
1 v
Preparation. We then introduce some additional notations and representations for proof of Thcorem 2 Following the common practice in (Chowdhury and Gopalan 202I), we let the kernel be defined by (xx), i.e., k(æ, x') = (w)) (x')), ). and d(x) _ (æ)). then further define the (1 x d) d)-dimensional Jacobian matrix (xx) A [Ø(x) ((x)))== and N [xb(=)))==> The matrix K, and the covariance matrix dof (z) defined on the optimization trajectory D; in our Sec. 3.1 can be reformulated as
K, V. v.
(17)
00 (x: = d(x) Tx(x) - (xx) (K, + o²I)
-1 ((((x))
13

---

Published as a conference paper at ICLR 2023
Based the reformulation above, define V, - v + II can further reformulate do? (a) below
(x) as
007 (a) (a) (()) ((x)) x1(x;) (K, + o²1) Φ1(x))
( <(x) T ((x)) x(x) T p, (v. v. Q²1) -1 v. ((x)
( <(x) [I Vr (v. T v. + o²)) -1 v. 6(x)
(18)
@ (2)(()))
(V,V, V + + (v)
((x))
)>)(x)
((x).
Note that (b) is obtained by exploiting the fact that K, V v, and di (a:) x(x) T Tr In addition, (d) comes from Lemma B.2 by replacing the matrix A in Lemma B.2 with the matrix v
First Part. We then prove the first half part of our Theorem 2 i.e., the following Lemma B.4
Lemma B.4 Increnncrggsnng Variance Norm). For any E X and any t 2 1, we have that
[100 S |00 (
(19)
Proof. Based on our additional notations and representations, we have
(x)
(a) 0²6(x)) V ((x:)
(b) d²)(x)] ( 1T o'I+ ((.))(a)) 6(x)
@ ) T + +
((x)
( 0²)(z) [V o² (1 (1x)) / (xx) T V (ax)))a))))) (V,
@ 00 (x) 0² (1+ + ((x)) T V x(x) T (an))))))) ((z)
(1
( 3 000 10)-1(x).
(20)
Note that (a) follows from the aforementioned definition of V. and (b) comes from the fact that V W + ((:)))((())))
Similarly, (c) uses the definition of V.-1. In addition, equality (d) derives from Lemma B.3 by letting A V and u = = ()x)) and (e) follows
from the reformulation of do?_ x in [8] Finally, (f) derives from the positive semi-definite property of ((x) V (xx 2 (x))
((x) as well the fact that 1 (+)()))) V 0.
That is, for any column vector z we have that
((x) (=, V=l1((>= (δ(x;) ( (Z (V
||o(0,) V [
(21)
0.
So, ((x) (V=) ( TV ((x) is positive semi-definite. Following similar way, we
also able to verify that 1 1+ (xx)) V (xx,) > by showing that (xx;)" VV 2 0 using the decomposition of V from the Principle Component Analysis (PCA). Since dof(ar) < of_1())
equivalent to [d) < | we then complete the proof of first half part of our
Theorem
Second Part. To prove the rest of our Theorem 2 we firstly introduce the following lemmas.
Lemma B.S. For any E X and any t 2 1, the following holds
V. & V
(22)
14

---

Published as a conference paper at ICLR 2023
Proof. For any column vector 2, have
z (V, Ve-1) = ((x)))))) (b(x,)) T x) (v(x)))
(23)
| T=1
0.
The first equality comes from the intermediate result in 20 So. V, V.- is positive semi semi-definite.
i... Vt-1 < V,. This can also indicate that V, < V 1-1 which thus completes our proof. O
Lemma B.6 (Lower Bound of Variance Norm). For any x E and any 2 1, the following holds
1/(1 + 1/02) (a))ll - [0)
(24)
Proof. We firstly show that
v. 1/2 (x))(())
V. 1/2
(a)
V 1/2 (xx)
[1(x)) T V 1/2
(xx) T V 1/2
(1)) V. 1/2 '/2,'''' 1/2 (xx))
((x)
(25)
((x)) (v))VVV11 Vzl
2 ((x) (oo (xx))
vxx) (xx))//
1/0²
Note that (a) derives from the Seapyy-Swwarrzzzzeee
As for (b) and (c), they have exploited 1/2 v.1/2 is row vector. In addition, (e)
the fact that (v7
+b(x) V.
1/2 and (xx) (((x))[a
follows from Lemma B.5 Finally, (g) results from V I/a² and (h) derives from the assumption
that k(x, x) < 1 (V2 E X)) in Sec. 2.1 Alternatively, we can restate the result above as
v 1/2 (a))(())
V
(26)
We then complete proof on the first inequality in Lemma B.6 using the following inequality:
do?
T (V d²)(2))TT
+ (12)) d(x)
[I V (2:3
V 1/2)
1/2 v (-1
x(x)
g (x) TV
1/2
I V r-1 ((:)) Tv.
V 1-1
1/2
((x)
(27)
1-1
(4)
> ) T V (w)) (1+
(c) 0o (x) (1 (1+1/0²
where (a) derives from 200 and (c) comes from the inversion of matrix product. Finally (d) follows from the result in 26 and (e) exploits the reformulation of (x))
According to Lemma B.4 and Lemma B.6 the following holds for any x E N and any / 2 1,
| (x I12
1
1. [ (x)
(28)
1 1/02
15

---

Published as a conference paper at ICLR 2023
Based on the definition of in our Theorem 2 therefore also have
max #EX,121
/ [10o
[o0 (2))1 [1/v1+1/02.1
(29)
As result, for every iteration i of our Algo. 2 have
v /100 - Vv 1002-
S r² v (100
(30)
r' V110000 k(z, 2') ='m===l
Srk
where the last incquality derives from our assumption of x') ==xx=====lly S n² (Vx E X)
in our Sec. 2.1 By substituting the result above into Theorem complete our proof of Theorem
B.4 PROOF OF THEOREM 3
Preparation.
Following the definition of the derivative mapping on the true derivative V (xxr)) in g we defined the following derivative mapping on our estimated derivative V (xtt,
G
Lt.r It.++
Et.-
Pxx 1/t, (3t,))))
(31)
M
ne.
By re-arranging it, we have the following update rule that has reformulated
Et,++ Lt,r Gr,,
(32)
Based on our definition of the derivative mappings in (31 and 8 we introduce the following lemmas:
Lemma B.7 (General Projection Inequalities). Given Px(x:) = arg mingex
sEx || - ==11// /2 and
domain X, for any x, æ', we have
- Px(x))l22 S 1 Px(x')1l2 (Px(xx) Px(('))) (l2 I | x' 2'112-
(33)
(34)
Proof. For 33 as Px(x)) E X (V'') and Px(x)) = arg min SEx || - x112 /2, we then naturally have 33
For (4), since Px(x) is the optimum of h(z)) |æ 21/// according to the optimality condition of the convex projection function (=x)) within the domain 2 E X (Boyd and Vandenberghe 2014). we then have the following inequality for any Px(x')= X:
Vh(z)* (Px(x') - 2) 2. 0.
(35)
By taking Vh(z)
with Px(x)) into the inequality above, we have
(xx - =;) (Px(a') (x 0.
(36)
By exchanging and x! in the result above, we achieve the following similar result: x')
(Px(x') -0) (Px(x) Px(x'))
(37)
By summing 36 and 37
(x x') (Px(x)-Px(x') > Px (x(x'))
(38)
Based on the Seuchy-Schward inequality. finally achieve
34 using
[Px(x)) - Px(xx') 11 < (æ: x²) (Px(x) - Px(x'))
(39)
1 x - x'11, Px(xx)) Px(x')12
where both sides need to be divided by Ppxx Px ||2 complete our proof.
n
16

---

Published as a conference paper at ICLR 2023
Lemma B.8 (Inequalities for Derivative Mappings), Given 31
and for every and have
G 2
V P Grr
(40)
|G 12 V ff
(41)
| G4.
V V4-1
Vf(
(42)
Proof. For (40) let Dt,7 = 02,5 11, V 14 ( we then have
- Px (Z 2112 - (xi, &er) (Px(x).)) -xx(((t,))
(a)
[ 31,r+1l22 uh, Vu-i (x (20 - x1.+1))
(43)
(b) 2
Mh.5 G Ne. ( GG, T
2
(c)
where (a) results from the fact that #1,r+1 Px (æt,r Mhr (xt,)) based on our 7 and
(b) derives from the definition of G. in (31) In addition, (c) is based on the following result by substituting a Et,r and x' Tt.- into (38)
[xx(m..)) (x (a... ) (Px( - (xt,)) - 0.
(44)
Finally, by dividing ni. on the both sides of the last inequality in 43) we finish the proof for (40).
For (4)), following the same proof above, can also obtain achieve the following inequality for the projected derivative G,,::
GGr ff( Gu. I [Vf I|Gr,rll
(45)
We complete the proof for 41 by dividing | llz on the both sides of the inequality above.
For 42 define x 1,,+1 Fi,r nt. Tt. Gt,,, we have
Gr,
G
(a)
1
| 0e,4+1 - -
1/t,7
| 2/,rt1l12
1/0.7
1
|Pxxxi mh.r (Ho-1(0L,r)) Px( ne.r V f((,,)))
(46)
T/.7
(d)
1
Bt,r V ( (Iirr Mt. (
Mt.5
Viu-i ( v V
where (a) comes from the definition of G.,- and G in 31 and 8 respectively. In addition, (c)
derives from and Finally. (d) results from (34
Proof. Since the objective function f is assumed to be L, L.-Lipschitz smooth (Sec. 4.2 we have the following inequality for any Ft,r X' our ZoRD algorithm:
f(x1r+1) -f(x,))) S Vf(x()) (xI, - xz,7) + I.
2 1 I1,r
(47)
17

---

Published as a conference paper at ICLR 2023
Let 8' (0,1). 1). Define 3 & / 2(va
(n(1/"), by substituting 32) into the inequality above, + 2
the following inequality holds with probability of at least 8':
f( +( - f(x1,7)
(a)
nerr (I(()))) O,,t Lonhr
Gr.5 1|
(b) T V/t:1( f((r))))) Ge.t - Thrr V/ (xx,)) GZ,,
+ Lashirr
| 1
2
(V - ff (2),,)) (Ge, - -Gtr)
(Vt) GG,
1/t.7
M1rr (2) GG,r + LoN
|
2
(d)
S 1/,77
(V--1(2 Vf (f( GG,T
-G,,
+ -11 -
11000-/(aaa Vf(x,,)) [G
2
T|rr V Gr. +
Gt,
(c)
S 1h,r
(1V V (30t,))12 +
V (2re,)) (V/((a))))) |
27,T - Lotihr
[ 1|2
2
SS n 3 + ner 1or"
n1. 2
Ge.r 1
(48)
where (d) derives from the Cauchy-Schward Schwarz inequality and (c) follows from the Lemma B.7 Finally, (f) result from the bounded derivative estimation error in Theorem 2 and the fact that f is L. Lipschitz continuous (i.e., [ | S The for any X') and 1),, 1/ L. (Vr).
For every iteration t our ZoRD algorithm, we in fact will apply the virtual updates 7 for V/ times (see Algo. 2) Therefore, for probability 2 - V,8', have
V 1
V--1 [f(z),)) f(I(,++1 + +Te (2:282,21 L.NxBrt]]
G 1,
Nt.
V
V
0=
T=0
(49)
2 14-1
[f(=,-1 f(xx)))
(K2 L.33rr
where the first inequality results from (88 by re-arranging it and then sum it up over T.
However, in order prove the convergence of our ZoRD algorithm to stationary point, need to consider the derivative mapping of G., instead (refer to our Sec. 4.2). So, for any т, we propose the following inequality:
|G, =
Gt,r - Ger + +G..T
Gt,r - Ge.l + G
(50)
1 V.
< krr' +
G
where the first inequality is from the Cauchy- Senchy-Schwar.... inequality and the second inequality comes from 422. Finally, by taking the result above into (49
we have
Va-1
2 1f(x--1 f(xx))] + ner || 12 V.
2
(N232, + Lon(Br") K3r
ne.r
V
(51)
18

---

Published as a conference paper at ICLR 2023
Then, substituting Vi V and M/. for any t, 7 into the result above, the following inequality
holds with probability of at least VT8 when r <
T
V-1
(a)
T
2 (f (1 - f(x()) + 27 2 02, + (2mLe + 1)x3r²
n
11
_
Σ
T
t=1
(b)
TV (f(2)) f(xr)) + 21y(1 ,2T)
k² 3²
T(1 ,²)
+ (2 1)(1--+))
T(1 r)) KBBr
(
TV (f(z)) - f(x")) + 2npr
(2y + 1)
T(1 - (2) T(1-r)
(52)
Note that (b) derives from the summation of the geometric sequence about and (c) comes from x" - arg min f(x). When r = 1, the following holds with probability of at least 2 - VT8 accordingly;
T
(2 + 23,2 + (21 + 1)xB3r)
Σ
T Σ
S
(53)
2
[s(o)) [(xr) + 20Tx2 8² + (21 1)x3.
TV
Finally, 6 = VT8 E (0, 1), the following holds with probability of at least 1 6,
T
Σ
GG 11 S T Σ
GG.
(54)
+
where ① and @ can be defined as below with a & xx d xx
2(v 1))nn///
2/П1
1
TV [f( f(xr))
(55)
[2a2p/ [T(1 r²) + (2L + 1/m)ar/ - r)] (r < 1),
12a² + (2L + 1/n)a
(r=1) 1).
19

---

Published as a conference paper at ICLR 2023
APPENDIX C EXPERIMENTAL SETTINGS
C.I GENERAL SETTINGS
Derived GP. Among all our experiments in Sec. [ apply the derivative estimation in Sec. 3.1 for every iteration and every step r of our ZoRD algorithm, we use the derived GP 4 based on the Matérn kernel with v 2.5 and fit this derived GP using 150 queries that achieves the smallest Euclidean distance with input Et,- from the optimization trajectory. This is because we only need to model the objective function f in the vicinity of input øt,r precisely rather than the entire domain, so as to achieve an accurate derivative estimation at input Zt,r.
Confidence Threshold. Among all our experiments in Sec. | the confidence threshold c of our dynamic virtual updates (Sec. is set to be 0.35 in order realize good trade-off between query efficiency and accurate derivative estimation in practice, which can already allow our ZoRD to achieve compelling empirical results consistently (see our Sec. 5). In light of this, 0.35 would be a reasonably good choice in practice, especially when there is no prior knowledge about the objective functions. When we have prior knowledge about the smoothness of the objective functions, can likely make better choice for c: Intuitively, smooth objective functions usually can be modeled by the Gaussian process effectively (Rasmussen and Williams 2006). so an accurate derivative estimation from our derived GP is also likely to be achieved. In this scenario, a large confidence threshold can be applied to fully exploit the benefit of our derivative estimation that is free from the requirement for additional queries and consequently results in an improved query efficiency in practice.
Baselines. In addition, among all our experiments in Sec. 5 we consistently use 10, X 0.01 and directions {u: | that are randomly sampled from a unit sphere for the derivative estimation of the FD method (2) applied in the RGF and PRGF algorithm. Moreover, following the common practice of (Berahas et al. 2022 Cheng et al., 2021), we conduct orthogonalizaaion on these randomly selected directions via the Gram-Schmidt procedure. As for the ES algorithm (e.g., the one applied in (Salimans et al., 2017)), we apply the same n. À and [u:} in RGF and PRGF for their update in every iteration.
Domain Transformation. Following the practice that has been used in (Eriksson et al. 2019), for all our experiments, we firstly re-scale the input domains into [0, 10)4 to ease the optimization and then re-scale the updated inputs back to the original domains for querying.
C.2 SYNTHETIC EXPERIMENTS
Let input x = [ 1s the Ackley and Levy function applied in our synthetic experiments are given below,
d
1
f(x) = -00
-0.2
7
x
exp
cos (2TT;)) + 20 exp(1), (Ackley)
i=1
f(x) sin? (TWI) Σ (w; 1)² [1 10 sin² (Tw; + 1)] + (wa - 1)² [1 + sin" (2Twa)) (Levy)
(56)
where w. 1 (z; 1)/4 14/4//t for any i= 1,... Ackley function achieves its minimum (i.e.. min [=) = 0) at .= = 0, and Levy function achieves its minimum (i.e., min f(x) = 0) at xt 1. Note that the Ackley and Levy function for the synthetic experiments in our Sec. 5.2 are defined within the domain [-20, 20 and [-7.5, 7.5] respectively. To give better understanding of these two synthetic functions, we provide a 3D illustration of these two synthetic functions with = 2 in our Fig. 5 As shown in Fig. 5 these two synthetic functions are highly nonconvex and therefore have local minimums within their domains.
To compare our ZoRD algorithm with other ZO/FO optimization baselines in Sec. 5.2 we firstly employ TuRBO of 300 queries to find good initialization for all other ZO/FO optimization algorithms in Fig. because of the nonconvexity of these synthetic functions shown in Fig. 5 We then
20

---

Published as a conference paper at ICLR 2023
-15
4
13
-10
11
9
7
5
775
-5
-7.5_s.0pp _75_
0.0
0.0
5.0
2.5
10
5.0
7.5
7.5
(a) Ackley function (d 2)
(b) Levy function (d 2)
Figure 5: The 3D illustration of Ackley and Levy synthetic function with 2.
apply these ZO/FO optimization algorithms with a query budget of 200 for = 20, 40, and a query budget of 400 for d 100 compare their query efficiency. We the same Adam optimizer (Kingma and Bal 2015) with a learning rate of 0.1 and exponential decay rates 0.9, 0.999 for RGF, PRGF, GD, and our ZoRD algorithm, for faster convergence compared with standard GD.
C.3 BLACK-BOX ADVERSARIAL ATTACK
For the black-box adversarial attack experiment on the MNIST dataset, we use the same fully trained deep neural networks from (Cheng et al. 2021) and adopt a Los constraint of || |a=]|>> S 0.3 on input perturbation a. For the black-box adversarial attack experiment fully train ResNet-18 18 (He et al.) 2016) on CIFAR- 10 using stochastic gradient descend (SGD) with cosine annealed learning rate from 0.1 to 0, momentum of 0.9 and weight decay of 5 10-4 for 200 epochs, and adopt a L constraint of || | I 0.2 on the input perturbation æ. Note that we use the same loss function (Cheng et al. (202]) for these two experiments. Meanwhile, to apply RGF, PRGF and our ZoRD, we adopt Adam optimizer with the same learning rate of 0.5 and the same exponential decay of 0.9, 0.999.
the CIFAR- 10 dataset, we
C.4 NON-DIFFERENTIALLE METRIC OPTIMIZATION
The Covertype dataset used in Sec. 5.4 is classification dataset consisting of 581,012 samples from 7 different categories. Each sample from this dataset 54-dimensional vector of integers. this experiment, we randomly split the dataset into training and test sets with each containing 290,506 samples. The MLP classifier applied in Sec. 5.4 consists
layers with 30 and 14 hidden neurons respectively, leading to 2189 parameters in total (i.c., d 2189). We first train this MLP classifier on the training dataset of Covertype using the L-BFGS algorithm with the cross-entrons loss function for 300 epochs, and then apply 70 optimization algorithms fine-tune the non-differentiable metrics (i.e., using these metrics as the new loss functions). including precision, recall, F1 score and Jaccard index. To obtain the results of ES, RGF, PRGF and our ZoRD algorithm in Sec. 5.4] we apply the same Adam optimizer with learning rate of 0.2 (for precision and recall) 0.01 (for Fl score and Jaccard index) and exponential decay rates of 0.9, 0.999. Note that standard BO algorithms (including TuRBO) fail to achieve any percentage improvements (i.e., achieving 0% in the y-axis Fig. in this experiment according to our five independent runs, which is likely due to their aggressive exploration in the input domain of such high dimension. In light of this, we do not include them in our comparison since all other methods are able achieve certain improvements.
trained MLP directly on
C.5 DERIVATIVE- REINFORCEMENT LEARNING
Our Serivative-free RL experiments aim to learn controllers (which outputs policies) that maximize the rewards/return for several environments in the OpenAl Gym (Brockman et al. (016) without using true derívatives. Specifically, need to optimize the parameters (i.e., a:) of neural network
21

---

Published as a conference paper at ICLR 2023
Table 2: OpenAl Gym environment properties and their respective network dimensions.
Acrobot
Swimmer
Lunar
Bipedal
Walker2D
HalfCheetah
[
6
8
24
17
17
A
3
2
4
6
6
d
213
222
244
404
356
356
d 20
d 40
d 80
d 160
Sinterity
1.00
000000
Eucideen Deleroe
Cosino Similadt
1.00
Euc lssan Dislanpa
Cosine Similrity
1.00
Eucidtean Distance
Similaity
1.00
Eucideen Disterie
0.75
0.75
0000000
0.75
00000000000000000000000000000000
0.75
-0-
FD
0.50
0.50
0.25
00000
0.25
0.25
000000000000
0.25
000000000
0.00
0.00
0.00
0.00
20
40
25
80
60
100
100
200
Total Queries
Total Queries
Total Queries
Total Queries
(a) Results under various input dimension d and fixed Matérn(y
2.5)
Matérnfu= 0.3)
Matéen(u=11 1.5)
Matéru(
Si
1.00
Euelóeen Distence
Cosine Simliarty
Buclddsan Dietanse
Codine Simbarky
1.00
Euclidean Distance
Cosine Similarit
1.00
Eueloeen Distennce
0.75
a
0.75
00000
0.75
0.75
Lon00
-2
0.50
0.50
0.50
0.50
GP
0.25
0.25
0.25
0.5
000000
0.00
0.00
50
100
100
60
100
50
100
Queries
Total Queries
Total
(b) Results under various kernels and fixed input dimension
80
Figure 6: Comparison of the derivative estimation errors of our derived GP-based estimator (GP) and the FD estimator under various input dimensions and kernels. Similarly, each result is reported with the mean + standard error from five independent runs.
(MLP) controller with hidden layers, where each hidden layer has 10 hidden neurons and one bias term. We adopt a T. constraint of || on the parameters We a softmax output layer for the policies that deal with discrete action spaces, and a tanh output layer for the policies that deal with continuous action spaces. The dimension of neural network parameters (represented column vector) d is determined by the dimensions of both the observation |S] and the action space |A| of an environment, as detailed in Tab.
In order to search for policies that are robust to different random state initializations, we use the vectorized API of OpenAI Gym, and our observed function value y(z) given the network parameters is an averaged return of 32 parallel environments. We also fix the seed of OpenAl Gym for all queries, which ensures that we are evaluating on a fixed set of 32 state initializations and that our results can be reproduced. We first initialize sample of 500 points from Latin Hypercube (MeKay ctt al. 1979) to find good initial input, and then proceed to apply ZO optimization algorithms (i.c., ES, RGF, PRGF, and our ZoRD) with the same query budget of 1000 this initial input. For all these ZO optimization algorithms, we employ the same Adam optimizer with a learning rate of 1.0 and exponential decay rates of 0.9, 0.999. Considering the prohibitive noise in RL experiments, use 300 queries from the optimization trajectory that has the smallest Euclidean distance with an input needing to be updated. Of note, we conduct 10 trials in total where each trial differs from each other by both the OpenAl Gym seed and the Latin Hypercube initializations.
APPENDIX D MORE RESULTS
D. MORE RESULTS ON DERIVATIVE ESTIMATION
Besides the comparison in Fig. g we provide additional comparison between our derived GP-based estimator 66) and the FD estimator 2 under various input dimensions in Fig. (la) and various kernels
22

---

Published as a conference paper at ICLR 2023
2.5
Optimality Gap llog scale)
Optimality Gap (log scale)
2.75
2.0
2.50
1.5
2.25
1.0
RBF
* RGF
mC!
+ MIGF
2.00
0.5
Ze00y--00
Z:ADic-u4 4.4
1.75
ZoRD)-00f)
50
100
150
200
50
150
200
Queries
# Queries
(a) Ackley (d = 40)
(b) Levy (d = 40)
Figure 7: Comparison our ZoRD algorithm using different confidence thresholds e for its dynamic virtual updates, where the r-axis and the y-axis denote the number of function queries and the log- scaled optimality gap (i.e., log (f(xT) f(x")) achieved with this number of queries, respectively.
in Fig. b(bb using the Ackley function. We adopt the same setting in Sec. 5.2 Interestingly, Fig. (b) show that under various imput dimensions and GP kernels, our derived GP-based estimator 6
still able to achieve faster reduction rates compared with the FD estimator. Of note, all the function queries applied in our derived GP-based estimator from the optimization trajectory whereas the FD estimator requires additional function queries for its derivative estimation. So, Fig. (())(b) also show that our derived GP method is still able to achieve improved query efficiency for accurate derivative estimation than FD method under various input dimensions and GP kernels because our method avoids the requirement of additional queries for derivative estimation. Interestingly. the objective funetion (i.e., the Ackley function) is not truly sampled from the GPs based these kernels. This therefore means that though we have assumed that we need the prior knowledge about the GP in which the objective function is sampled from (Sec. 2.T). such assumption does not really need be satisfied for our derived GP-based method to achieve accurate derivative estimation in practice. More interestingly, we notice that Matérn(y 0.5) and SE kernel will achieve slightly worse derivative estimation, indicating that the choice of GP kernels may impact the quality of our derived GP-based derivative estimation. However, practice, our derived GP method based on Matérn(u 2.5) kernel, which has been widely adopted in our experiments, is already able to provide us with good derivative estimation for ZO optimization as confirmed by the results in our other experiments.
D.2 MORE RESULTS ON SYNTHETIC EXPERIMENTS
In this section, compare ZoRD with more baselines in Fig. Notably, mainly compare ZoRD with CobBO (based on the code implementation provided by (Tan et al.] (021)) since CobBO generally performs better than other baselines, e.g., TPE, ATPE, and BADS according to (TTn et al., 2021). As shown in the results in Fig. & our ZoRD algorithm is still able to outperform the other benchmark BO algorithm (i.c., CobBO).
We then investigate the impacts of the dynamic virtual updates (Sec. 3.2 on our ZoRD algorithm. In particular, we apply the same setting in Appx. C.2 to optimize the Ackley and Levy function with d = 40 under various confidence thresholds e for our dynamic virtual updates. Fig. 7 illlsttrates the results. As shown in both Fig. a) and (b), our ZoRD algorithm using the technique of dynamic virtual updates (i.c., >> 0) can consistently achieve improved query efficiency compared with the one not using the technique of dynamic virtual updates (i.e., e e= 0). This indicates the essence of dynamic virtual updates in helping improve the query efficiency of our ZoRD algorithm. Such result actually corroborates our theoretical insights about virtual updates (Sec. H.2). Remarkably, our ZORD algorithm without the technique of dynamic virtual updates (i.e., = 0) is still able to achieve both improved query efficiency and better converged performance compared with RGF and PRGF, which further verifies the superiority of our derived basba derivative estimation. More interestingly, both Fig. aa) and Fig. b)) have verified that there indeed exists a trade-off for the confidence threshold as have discussed in Sec. 3.2 The confidence threshold can not be overly
23

---

Published as a conference paper at ICLR 2023
3.00
Opemallyy Cop dop comm)
Ostmann Gap 00 sook))
Optime by Gatp (tg sOaM)
2.75
Oylratty 000
2.00
4.5
2.00
1.100
06.0
0680
150
160
1.5
150
250
300
400
Qunrees
Queres
Oueeress
(a) Ackley (d = 20)
(b) Ackley (d = 40)
(c) Levy (d 40)
(d) Levy (d 100)
Figure 8: Additional comparison between our ZoRD and other baselines. The r-axis and y-axis denote the number of queries and log-scaleds optimality gap (i.e., log (f(rr) f(xx)) achieved after this number of queries. Each curve is the mean standard error from ten independent runs.
1.0
1.0
0.8
Success Rate
Success Rate
0.6
0.6
0.4
0.4
RDF
RDF
PRDF
PAGF
0
ZuhD
0.0
0.0
0
500
1000
1500
2000
500
1000
1500
2000
# Queries
# Queries
(a) Success rate on MNIST
(b) Success rate on CIFAR-10
Figure 9: Comparison of the success rate achieved by various ZO optimization algorithms on the 15 images selected from MNIST and CIFAFR-10 dataset. Note that the r-axis and the y-axis denote the number of queries and the success rate (within the range of [0, 1)) achieved after this number of queries, respectively.
small or excessively large in order to achieve the best query efficiency of our ZoRD algorithm, e.g., 0.3 for Ackley (d 40) and e 0.4 for Levy (d 40).
D.3 MORE RESULTS ON BLACK-BOR ADVERSARIAL ATTACK
Besides the comparison in our Sec. Sec.5.3) we also compare the success rate achieved by different ZO optimization algorithms the 15 images selected from MNIST or CIFAR-IO in Fig. 9 Note that we adopt the same settings in Appx. C.3 for this comparison. Considering the large computational complexity of TuRBO- 1/10 algorithm for hard-to-attack images which usually undesirable in practice, we drop the comparison with them in this experiment. Fig. 9 shows that under the same query budget, our ZoRD algorithm is able to achieve considerably improved success rate over other ZO optimization algorithms. These results therefore further support the superior query efficiency of our ZoRD algorithm in real-world challenging problems.
D.4 MORE RESULTS FOR DERIVATIVE-FREE REINFORCEMENT LEARNING
Recent years have also witnessed a surging interest in derivative-fiee free reinforcement learning (Salimans) al. 2017; Qian and Yu 202I), where ZO optimization algorithms widely applied. In light of this, we also demonstrate the superiority of our ZoRD algorithm in the problem of derivative-fres reinforcement learning. Specifically, we adopt the setting Sec. C.5 to experiment different RL environments. Tab. summarizess the comparison among different ZO optimization algorithms under
"Bayesian optimization algorithms, including TuRBO- 1/10, are widely known to suffer from the prohibitive computational complexity when they need large number of function queries for optimization, e.g., T 1000 [Rasmussen and Williams 2006).
24

---

Published as a conference paper at ICLR 2023
Table 3: Comparison of the rewards (larger better) achieved by various ZO optimization algorithms in different RL environments. Each result is reported with the mean + standard deviation from ten independent runs.
Algorithm
Acrohot
Swimmer
Lunar
BipedalWalker
Walker2D
HalfCheetah
ES
16.22+100
176.0+:56.8
-94.7424.4
33..7427.3
340.4=143.0
1042.4#753.9
RGF
-83.0+5..6
213.2+66.1
193.8+19.1
-30.3+-00.3
368.44223.1
1129,3+748.5
PRGF
-86.3+99.9
218.6+66.2
1100.1+16.0
-29.9+35.22
344.6+152.3
1083.3+722.22
ZoRD
-73.3:12.44
280.5:177.6
45.11:38.3
12.9:
729.1+304.2
1950,5::576.1
the same query budget of 1000. As BO algorithms usually suffer from the prohibitive computational complexity for large T (Rasmussen and Williams 2006) and GLD has never been applied in RL, we mainly compare our ZoRD algorithm with ES, RGF and PRGF, which also belongs to the same type of ZO optimization algorithm: GD with estimated derivative. Remarkably, Tab, shows that under the same query budget, our ZoRD algorithm can consistently enjoy improved performance (i.e., highest rewards) than the other ZO optimization algorithms in different RL environments. This further supports the superiority of our ZoRD algorithm to other FD-based ZO optimization algorithms.
APPENDIX E DISCUSSIONS
E.1 ZoRD Vs. FD-BASED ZO OPTIMIZATION
Of note, the novelty of our work in fact lies in its way of exploiting the GP assumption to help design an improved derivative estimation and hence an improved ZO optimization algorithm, which to the best of knowledge has not been explored theoretically yet in the field of ZO optimization via GD with estimated derivative. That is, at this moment, it is still not known in the literature how existing FD methods can utilize such an assumption achieve better derivative estimation (i.e., their derivative estimation quality will remain the same), even when they make the same assumption as us. In light of this, the comparison between our derived GP method and the FD method in Sec. 4 is not only necessary but also meaningful to show the advantage of exploiting such an assumption in ZO derivative estimation. Importantly, our empirical results further show that such an assumption is in fact not restrictive for our ZoRD to achieve compelling performance in practice. For example, Fig. and Fig. 6 have shown that our derived GP-based method is able to achieve smaller derivative estimation error than the FD method when the objective functions are not designed to be sampled from a GP with the kernel that we had applied for our derivative estimation. Moreover, the results in our Sec. 5.2 5.3 5.4 have shown that our ZoRD is capable of achieving competitive optimization performance for real-world optimization problems where the objective functions are also not designed to be sampled from GP with the kernel that we had used for ZoRD.
Meanwhile, the theoretical challenges of our work lie in the theoretical guarantee on the derivative estimation error of our unique derived GP-based method for any input the domain as well as the convergence analysis based on such unique derivative estimation, which to the best of our knowledge have not been studied in the literature. This means that our Thm. and Thm. 2 have provided new developments in the analysis of gradient estimation eтror and our Thm. 33 will be the first convergence result for GD using our unique derivative estimation method. Interestingly, the bound in our Thm. 3
also improves over the standard ones from (Nesterov and Spokoiny 2017 Liu et al. 201 2018b) in several aspects, as discussed in our Sec. 4.2
E.2 ZoRD VS. BO
Our ZoRD algorithm and standard BO algorithms (e.g., GP-UCB) have in fact applied the same GP assumption for their algorithm design. That is, however, where the similarity ends. Of note, our ZoRD exploits such an assumption to derive a specific GP (i.e., 44) for derivative estimation, which then employed for local exploitation via (projected) GD update. In contrast, BO algorithms utilize such assumption to construct their acquisition functions for global optimization that can trade off between exploitation and exploration. In practice, the exploration of BO algorithms is usually query-inefficient, especially for problems with high-dimensional input spaces, and therefore GD with
25

---

Published as a conference paper at ICLR 2023
71 6
Function Value
0-
-2
-2
5
-5
-5
0
5
2-
2
Derivative
0-
0
-2
0
2
0
2
2
0
2
Function Queries
Ground Truth
Approximation
Figure 10: Comparison of local derivative estimation (in the input domain of [0, 3) in our ZoRD and global function approximation (in the input domain of [-6, 6)) in BO under various number of random function queries.
estimated derivatives (especially our ZoRD) is preferred to realize better optimization performances in these problems (see our Sec. (.2)). So, our ZoRD and BO algorithms belong to two different types of ZO optimization algorithms (i.e., GD-type vs. BO-type), where their theoretical analyses are in fact not comparable. In particular, GD-type and BO-type ZO optimization algorithms apply different metries for their theoretical analyses, e.g., the derivative estimation error as well as the convergence to stationary point (in the nonconvex case) for GD-type ZO optimization algorithms vs. the global asymptotic convergence terms of the regret for BO-type ZO optimization algorithms. So, is more reasonable to compare the theory (including the theoretical challenge, the new developments, and the novelty of the convergence result) of our ZoRD with other GD-type ZO optimization algorithms. e.g., the ones using FD methods for their derivative estimation (Nesterov and Spokoiny 2017 Liu ctt al. 2018b). as what we have discussed in Sec.
In addition, in contrast to using the GP model the objective function within the entire domain for global exploration in BO, our derived GP in ZoRD will be applied to estimate the derivative of the objective function for local exploitation by GD shown in Sec. 3.1 As GD typically optimizes in local region, our derived GP only needs to estimate the derivative locally, which is known to be much simpler than modeling the objective function within the entire domain in BO especially for objective functions in sigh-dimensional input spaces. In light of this, the derived GP for derivative estimation (4) in our ZoRD algorithm advances the standard GP in BO in the following aspects:
1. Improved Query Efficiency for Estimation. The derived GP in ZoRD algorithm requires fewer function queries to provide accurate derivative estimation. We provide a visual example in Fig. I0, in which sample one-dimensions function f from a GP prior GO( k(x, x)) using the standard SE kernel and then randomly select the same number of queries from the input domain of [-6, 6] and [0, 3] for standard GP and our derived GP, respectively. As illustrated in Fig. 10 function in local region (i.e., x E [0, 3)) is usually smoother than its counterpart the entire domain (i.c., x E [- 6)). As a result, with only 4 function queries, our derived GP can already provide accurate estimation to the derivative of this objective function whereas standard GP requires more than 8 function queries to model this objective function accurately in the entire domain.
2. Reduced Computational Complexity. Comparing and (5) both the derived GP for derivative estimation in our ZoRD algorithm and the standard GP in BO enjoy compu- tational complexity of Onz²) with n function queries. However, as a consequence of the improved query efficiency of our derived GP, it is able require fewer function queries (i.e.,
26

---

Published as a conference paper at ICLR 2023
smaller n) for accurate derivative estimation and hence enjoy reduced computational complexity in practice especially when a large number of queries (e.g., n > 1000) are applied to the standard GP in BO.
As introduced in our Appx. 1.50 function queries for our derived GP can already help our ZoRD algorithm achieve remarkable results in practice (refer to the experiments in our Sec.
C
27


Reviews:
[{"review_id": "b8mcTf2-qr", "reviewer": "Reviewer_9AgD", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a zeroth order method that reduces the number of queries made as compared to methods that use finite difference to estimate the gradient. The authors propose using Gaussian Processes to estimate the trajectory of observations, thus giving them access to the gradient at any given point. Given the assumption that the underlying blackbox function is sampled from a gaussian process, the authors prove convergence by showing that the gradient estimation error is non-increasing as the number of queries go up.", "summary_of_the_review": "The paper is clearly written, nicely motivated and well structured. My main concern/question is around the assumption that f is sampled from a GP. How restrictive is this assumption in general? It seems like most heavy lifting in terms of providing a benefit over prior work is due to this assumption, while the algorithm itself is not entirely novel. Would this be an accurate understanding? Can the authors comment a bit more on this? Since the topic is quite far from my area of expertise, I am unable to provide more critical feedback than the above. Having said that, I think the paper makes a solid contribution and the paper is well drafted. Hence, I am leaning towards acceptance. ", "strength_and_weaknesses": "Strengths\n\n- Clear writing \n- Simple proposed approach\n\nWeaknesses\n\n-  Might have limited novelty ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_cnZ16zO3n", "reviewer": "Reviewer_Z3aD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Based Gaussian process, this paper develops a zeroth-order optimization algorithm which requires fewer function queries to estimate the gradient than previous zeroth-order methods. Additionally, a so-called dynamic virtual update schemes is incorporated. Theoretically, the proposed method is shown to obtain gradient with exponentially diminishing error; and the convergence result of the algorithm is attained. Empirical studies with synthesized data and real-world data corroborate the theoretical analysis and demonstrated the superior performance of the presented approach over existing zeroth-order optimization approaches.", "summary_of_the_review": "1.\tFor different problems, is there any guidance for the selection of confidence threshold c. \n2.\tMore intuitive explanations on why the gradient error decreases at exponential rate are expected.\nThe code to reproduce the numerical results is currently unavailable.", "strength_and_weaknesses": "Strength:\n1.\tA novel algorithm is developed.\n2.\tThe theoretical analysis is solid--- the bound of the gradient error is given, and the convergence rate is obtained.\n3.\tEmpirical results show the proposed algorithm outperforms previous ones by a substantial margin.\nWeaknesses:\n1.\tRelated studies on advanced zeroth-order methods that aim to reduce the gradient error or improve query efficiency are not introduced.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JkmJ82o4wFu", "reviewer": "Reviewer_wx9Z", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the zeroth-order optimization where the gradient information is infeasible or very expensive to access, and only function values are available. Different from most one or two-point zeroth-order estimation, this paper assumes the function f is sampled from Gaussian process as in Bayesian optimization literature and then develops a trajectory-based zeroth-order method with some posterior information such as mean and covariance functions (both of which are constructed using previous trajectory information). Some error analysis of gradient estimator and convergence of the proposed algorithm are also provided. In experiments, they show that the proposed method admits a better gradient estimation and is more query efficient, compared to some zeroth-order and Bayesian optimization methods. ", "summary_of_the_review": "Overall, I like the approach and the idea of using GP to the zeroth-order optimization, which enables to explore more trajectory-based information to accelerate the convergence. The algorithms seem to be effective in the experiments.  However, the technical and algorithmic novelty is not clear to me. I tend to marginally reject this work, but I am very willing to adjust my score based on other reviewers' comments and the authors' response. ", "strength_and_weaknesses": "Pros:\n\n1. Zeroth-order optimization has become an important topic as in many new applications such as adversarial learning, hyperparameter optimization of black-box or complex systems. This paper provides an interesting solution motivated by Bayesian optimization.\n\n2. The presentation is overall good. The proposed method admits feasible mean and covariance function information due to the Gaussian process assumption, which is useful to make the design flexible, e.g., including the so-called virtual updates to improve the query efficiency. The idea is simple and intuitive. \n\nCons:\n\n1. The comparison to existing two-point or one-point finite-difference (FD) zeroth-order estimation is not fair, because the proposed method relies on a Gaussian process assumption, whereas existing FD types of methods do not. In my opinion, the authors should provide a more detailed comparison to existing Bayesian optimization based methods, which, however, seems to be quite missing in the current writing. Correct me if I miss anything for the reading. \n\n2. There are no sufficient algorithmic and theoretical comparison to GP or Bayesian optimization based methods. Only some are found at the end of the appendix. Therefore, the technical novelty of this work is not that clear to me. For example, what is the algorithmic difference compared to existing GP or Bayesian optimization methods? What is the theoretical challenges compared to such studies? Are there any new developments that cannot be handled by existing analysis? These points so far are not that clear to me. In terms of the theoretical analysis (e.g., Theorem 3), is this the first convergence result for GP based optimizer? How does this bound compare to existing GP-based algorithms? What is the best possible tradeoff achieved by $V$ even in this worst-case analysis? It seems Theorem 3 may not be easy to convey this due to the complicated form. \n\n3. More experiments on the comparison to GP or Bayesian optimization based approaches should be provided. For example, for the non-differentiable metric optimization experiment, why no GP or Bayesian optimization algorithms are included for comparison? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster