ReLIZO: Sample Reusable Linear Interpolation-based Zeroth-order Optimization
Authors: Xiaoxing Wang
Xiaohan Qin
Xiaokang Yang
Junchi Yan
Venue: NeurIPS 2024 poster (2024)
Keywords: Zero-order Optimization; Linear Interpolation; Reusing Strategy;
Primary area: optimization

Abstract: Gradient estimation is critical in zeroth-order optimization methods, which aims to obtain the descent direction by sampling update directions and querying function evaluations. Extensive research has been conducted including smoothing and linear interpolation. The former methods smooth the objective function, causing a biased gradient estimation, while the latter often enjoys more accurate estimates, at the cost of large amounts of samples and queries at each iteration to update variables. This paper resorts to the linear interpolation strategy and proposes to reduce the complexity of gradient estimation by reusing queries in the prior iterations while maintaining the sample size unchanged. Specifically, we model the gradient estimation as a quadratically constrained linear program problem and manage to derive the analytical solution. It innovatively decouples the required sample size from the variable dimension without extra conditions required, making it able to leverage the queries in the prior iterations. Moreover, part of the intermediate variables that contribute to the gradient estimation can be directly indexed, significantly reducing the computation complexity. Experiments on both simulation functions and real scenarios (black-box adversarial attacks neural architecture search, and parameter-efficient fine-tuning for large language models), show its efficacy and efficiency. Our code is available at https://github.com/Thinklab-SJTU/ReLIZO.git.

ReLIZO: Sample Reusable Linear Interpolation-based Zeroth-order Optimization
Xiaoxing Wang", Xiaohan Qin", Xiaokang Yang, Junchi Yan Dept. of CSE & School of AI & Moe Key Lab of AI, Shanghai Jiao Tong University [figurel_wx) _ galaxy-1, xkyang, yanjunchi) @sjtu.edu.cn
Abstract
Gradient estimation is critical in zeroth-order optimization methods. which aims obtain the descent direction by sampling update directions and querying function evaluations. Extensive research has been conducted including smoothing and linear interpolation. The former methods smooth the objective function, causing a biased gradient estimation, while the latter often enjoys more accurate estimates, the cost of large amounts of samples and queries at each iteration to update variables. This paper resorts the linear interpolation strategy and proposes to reduce the complexity of gradient estimation by reusing queries in the prior iterations while maintaining the sample size unchanged. Specifically, model the gradient estima- tion as a quadratically constrained linear program problem and manage to derive the analytical solution. innovatively decouples the required sample size from the variable dimension without extra conditions required, making it able to leverage the queries in the prior iterations. Moreover, part of the intermediate variables that contribute to the gradient estimation can be directly indexed, significantly reducing the computation complexity. Experiments on both simulation functions and real scenarios (black-bor -bxx adversarial attacks neural architecture search, and parameter- efficient fine-tuning for large language models), show its efficacy and efficiency. git
Our code is available at wtthttt://// gi thub. wonm/Thinkkaa--SJ//RReee.
1 Introduction
Zeroth-order optimization (ZO) aims to estimate the gradients by only function evaluations and solve optimization problems by the descent method. has been successfully applied to many fields, including science 41 25), finance (35, and artificial intelligence (37 45 47). where the optimization functions are usually black-box without available gradients w.r.t. the variables. Typical ZO methods iteratively perform three major steps [35]: 1) estimate the gradient by sampling directions to update the variable and querying the function evaluation, 2) rectify the descent direction through momentum, element- wise sign operation, stochastic variance reduced algorithms, etc., and 3) update the variables according to the descent direction. Wherein, the first step, i.e. gradient estimation, is critical since it provides the essential direction to update variables, which have been explored by many recent works 30
Gradient estimation methods in ZO can be roughly categorized into two groups 5 linear interpo- lation technique 4 30 and smoothing strategy [39 [2]. The former proposes sample set of linearly independent directions to form an invertible matrix and compute the gradient through linear interpolation. Though such methods can get better descent directions, the sample size of directions should be the same as the dimension of variables, leading to an intractable complexity of building an invertible matrix and computing the matrix inversion the dimension increases. A recent work (30
Equal contribution; i Corresponding author. This work was partly supported by NSFC (92370201, 62222607) and Shanghai Municipal Science and Technology Major Project under Grant 2021SHZDZX000..
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

makes the sample size in linear interpolation strategy independent of the dimension of variables yet involves an extra orthogonal requirement of the sampled vectors. The latter group proposes to estimate the gradient by sum of directional derivatives along random directions e.g. Gaussian and uniform on a unit sphere. Such methods are simple to implement and the sample size directions are independent of the variable dimension. However, it provides gradient estimation of smoothed version of the objective function (35), which differs from the original one with a bound w.r.t a smoothing parameter [39]. Additionally, the prior work [5] shows that smoothing methods require significantly more samples than linear interpolation strategies to obtain an accurate estimation The work [28] leverages information theory showing that under the Lipschitz continuous gradient assumption. ZO methods require sample complexities growing polynomially with the variable dimension.
Overall, the prior gradient estimation methods require large amounts of samples at each iteration to update variables. Nevertheless, in many real scenarios, one query of function evaluation can require large amounts of resources such as tasks in AutoMI. and reinforcement learning, which significantly restricts the acceptable sample size at each iteration and thus slow down the convergence of ZO methods. Consequently, it has been urgently demanded to reduce the number of queries while ensuring the convergence of ZO methods.
To this end, we delve into the ZO pipeline and observe that the magnitudes of steps to update variables are limited, making it possible to reuse the queries in the prior iterations. It is hoped that such a reusing strategy can be explored to significantly reduce the number of queries of function evaluation while maintaining the sample size unchanged at each iteration. However, it is hard to be directly applied to the prior gradient estimation methods. On one hand, for smoothing strategies, it is hard to guarantee the reused samples ohey the demanded distribution, which will further increase the gradient estimation bias. On the other hand, methods based on linear interpolation techniques require large computation complexity since building an invertible matrix needs to compute the null space of reused samples. Additionally, another work (30 requires orthogonal sampled vectors, which can hardly be satisfied by the prior samples, making it impossible to reuse the samples.
This work refers to Taylor's 's expansion and proposes to estimate gradients through linear combination of limited direction samples and their queried function evaluations. We then model the gradient estimation as a quadratically constrained linear program (QCLP) and derive the analytical solution. Our method can reduce the required sample size (decoupled from the variable dimension) for linear interpolation strategies without the orthogonal condition required. Consequently. it supports to reuse the queries in the prior iterations. Moreover, part of the intermediate variables that contribute to the gradient estimation can be directly indexed from the computation in the prior iterations, significantly reducing the computation complexity during the ZO process. Theoretical analysis is performed to show that our method can be regarded as a general version of the traditional linear interpolation strategy and has a similar convergence rate. In summary, our contributions lie in:
1) We introduce to reuse the prior queries to speed up the Zo procedure. Unlike recent works that cannot reuse the queries due to the requirements of sampled vectors to be orthogonal in linear interpolation strategies or obey a specific distribution in smoothing techniques, we introduce to estimate the gradient with an arbitrary number of sampled vectors without orthogonal condition, making it possible to leverage the queries in the prior iterations. To the best of our knowledge, this work is the first that attempts to reuse queries to speed up the ZO procedure.
2) We model the gradient estimation in ZO as a QCLP and derive the analytical solution by Lagrange multiplier. Theoretical analysis also proves that our method has similar convergence rate as conventional linear interpolation techniques. Moreover, after combining our gradient estimator based on QCLP with the reusing strategy, part of the intermediate variables that contribute to the analytical solution can also be directly indexed from the computation in the prior iterations, significantly reducing the complexity when the sample size is much lower than the variable dimension. Overall, our method is more efficient than linear interpolation-bant based methods with comparable accurate estimation of the gradient.
3) We conduct extensive experiments to show the efficacy and efficiency of our method. We first compare our method with recent ZO methods on the CUTEst, showing that it has faster convergence speed and better solutions. Ablation studies show that the performance drop is negligible even with more than 50% reuse rate. We then conduct experiments on the black-box adversarial attack task, showing that it has lower attack loss and 5% better attack success rate compared to peer ZO solvers
2

---

with similar final & distortion. Our method is further applied to the Neural Architecture Search (NAS) on NAS-Bench-200 outperforming other ZO solvers with 39% less number of queries.
2 Related Work
Zeroth-order optimization. There are typically two types of gradient estimation in ZO algorithms:
one-point estimation [38 13 (5) and multi-point estimation [1 39 22 [9]. Since multi-point estimation more accurate, some works [33 [2] made further research on ZO convex problems. As for the non-convex setting, the prior works (39 22 proposed ZO-GD and its stochastic counterpart ZO-SGD. ZO algorithms have been widely employed in various scenarios, such as black-bo box adversarial attacks [T]] 271. AutoML 47 and transfer learning 44). It is worth noting that the gradient estimation is the most critical part of ZO solvers, which is the focus of the above methods.
Gradient estimation via smoothing strategy. Methods based on the smoothing strategy 3 36 estimate gradients by averaging over several directional derivatives by sampling the direction from either Gaussian distribution [39] uniform distribution
[20] unit sphere. Referring the prior smoothing strategy based ZO algorithms [39 22). ZO-signSGD [34] yields faster convergence
but only guarantees converge to neighborhood of solution, and ZO-AdaMM 12
uses adaptive
momentum to enhance the optimization.
Gradient estimation via linear interpolation. Methods based on linear interpolation 15 estimate gradient by solving linear programming. Conn al. [T3] derived the eтror bounds between the true function value and interpolating polynomials, including linear and quadratic approximation models. Berahas et al.[4) showed that linear interpolation gives better gradients than Gaussian smoothing in derivative-free optimization. The prior work [5] derived bounds on the sample size and the sampling radius, showing that smoothing strategy requires significantly more samples to obtain an accurate estimation than linear interpolation. Kozak et al. [30] approximated the gradient by finite differences computed set of orthogonal random directions, which special case of linear interpolation. This work also focuses the scope of linear interpolation due its more accurate estimation of gradient than smoothing techniques.
Remarks, Our approach has few constraints on the sample size, similar to the smoothing techniques. Meanwhile, we estimate the gradients by solving linear program problem, similar to the linear interpolation strategies. Overall, our approach enjoys the efficiency of smoothing techniques while maintaining estimation accuracy.
3
The Proposed ReLIZO Method
Similar to the prior ZO methods
22 12 we consider the problem of finding a point x" E Rdd Rdd - IR is black-box and satisfies the following
such that f(x") min, f(x). The function
assumptions:
Assumption 3.1. 0 < (x f(=*) < oo, where x0 is the initial point.
Assumption 3.2. The function f continuously differentiable, and V is L-Lipschitz continuous for Vz Rdd.
3.1 Rethinking Gradient Estimation QCLP
Consider the Taylor's expansion of function f:
f(v)= - f(x) Vf(x) Ty (y- -)) +ly -
(I)
The remainder can be omitted in many scenarios. For large-scale applications it can be hard to compute the number of function evaluations required to construct quadratic models.
Given random vectors candidate updates the variable A, Rexd denote the i-th row of it as A The corresponding function evaluation (f(r + ( can be queried and compose A5 R", whose entries D; f(x A f(z), Vi I,..., n. According Eq. we can have the equations follows:
(2)
3

---

In this work, we mainly focus on the case where n < d, hoping to obtain approximately accurate gradients with fewer queries. To this end, we estimate the direction of gradient f(()) as g(x) by linearly combining the sampled vectors { yielding g(z) Ag a, where a E IK" represents the coefficients of the linear combination. The inner product of normalized g(x) and V f(r) increases when their directions are getting closed, which can be formulated as:
arg max ((x) Vf(x)
T A V(())
[x)x Va A.A a
9
Substitute Eq. 2 into Eq. 3
and define A, = A E R"x", We can model the estimation of gradient direction as quadratically constrained linear program (QCLP):
arg max a As, s.t. a 1z0=1.
We employ the Lagrange multiplier method to address the QCLP problem 44. The Lagrangian function is defined as: L(a, X) = A X(a Aga - 1), where À is the Lagrange multiplier. Taking partial derivatives w.r.t. and setting it to zero, we have ØL de A 2XAza 0 and a 2X Dy. yielding the direction of a A ' Consequently, we obtain the estimated direction of the gradient:
= æ A
(5)
Finally, we initialize the magnitude of the descent direction σ with learning rate 77 and adopt the line search strategy to update og to satisfy the Armijo-Goldsee condition 2 [3
3.2 Reusing the Queries in the Prior Iterations
Unlike recent works unable to reuse the queries due to the requirements of sampled vectors to be orthogonal in linear interpolation strategies (30] or to obey specific distribution in smoothing techniques [39], our method has few constraints on the sampled vectors Ag, making it possible to reuse the queries in the prior iterations.
Suppose - is the variable and Az,-, is the n random vectors at (k- - 1)-th iteration. We have the queried function values at points (Ix-1 + A #x-1 V The estimated descent direction is 1( with step 0- After updating the variable at 1-th iteration, we have Iı = -t- -0 (==(() 1). Since (r+= has also been queried, we have n + queried points and can collect n + random vectors for with known queries at k-th iteration as:
Å 19
(-Ok-19(
Ai my 1im1.
(6)
Distances between and the prior queried points are || rk- = 1ox 17 .)ll and
||æg (# A ) = |o 19 + A #x Il, Vi (1 (1....,1) n).
According to Taylor's expansion in Eq. 1 the remainder o(y x) will be non-negligible as lly - x
increases. Therefore, we introduce a reusable distance bound b to filter out the samples far away from the current point Fk, i.e., the reused vectors are obtained by:
A. = (A A.,
||| < b).
After getting the reusable queries, we then randomly sample another V vectors {py} to build Agg E nnd for gradient estimation k-th iteration:
(,)) "ام
b4 A
(8)
Overall, in the k-th iteration, only n - A Sec. shows that the sample size increases, even reusing 80% prior queries can also find good solutions.
22 new queries should be conducted. The ablation study in
Discussion on the reusable distance bound b: ZO methods estimate the directional derivative by difference and restrict the distances between the samples and current point to small value, which has the same order as the stepsize (initial learning rate) 17 O ( previous works (Table 1 in (29). In our method, the reusable distance bound & restricts the distances between the reusable samples and current point, which should has the same order of magnitude as the stepsize. Then we choose
b ~ O Ablation studies in Fig. show that 2nj works pretty well in different optimization tasks with different sample sizes N. thus set 2n by default.

---

Algorithm ReLIZO
Input: A Black-bos box function fz)); Sample size at each iteration n; Reusable distance bound b; Number of iterations K; Learning rate 7)-
Output: The best solution x that minimizes (x)).
1: A zg 0;
2: for = 0 - do
3: Collect the reusable vectors from the last iteration and get As, by Eq 6 and Eq.
4: Sample another n - | vectors P and build Drg E 1xx by Eq.
5: Query the function evaluation for newly sampled vectors f ( Pj Vpj E P: Compute Ar, by Eq.
6:
7: Obtain the estimated gradient direction g(z)) x A by Eq. 5
8: Initialize the magnitude of descent direction or as 77 and update o% by the backtracking line
search;
9: Update the variable: #k+1
2k o+g(
10: end for
11: Return the solution z and the best solution x² satisfying f(x*) 2 f(x)), Wk (O,...,K) K}.
3.3 Reducing the Computation Complexity by Indexing
Eq. shows that the estimated direction is related the inverse of A, = A When the sample size is much smaller than the dimension of variables, i.e., n <<< d. the computation complexity of
A, ((ndd) dominating the complexity of matrix inversion ( Nevertheless, the complexity can be significantly reduced when large number of rows of A is reused.
We denote Art-1 A A which has been computed in the (k: - 1)-th iteration. In the k-th iteration, A in Eq. is the reused samples. In the following, we introduce an efficient strategy to compute ArT
7
First, we define Az, E (n-xxd to denote the vector differences between 2k-1 and all n + reusable points including (Ix-1 + A xx-1
U (I Hence, we get Ary- = A Az, A
2k as:
A Amt
A
0
A Az_
F
o
Without losing generality, we suppose Ar, has ny rows and the i-th row of it reuses the ry-th row vector A and [n.)) Since g(xx-1) = A F6-1 a, we have:
N 0k-1a A A
A
(10)
Rixd
where AR #k-1 A first dimension. Then, can derive A ArT as follows:
#k-1 ... Ann E RRaxxd and the subtraction should be broadcast among the
AT 24
oi (lgg )11
RT
R
T 1
a
Tk
gixi
R Xmg
R
Rlang
where the addition and subtractions should broadcast among the corresponding dimensions. Note that R #R-1
ART and AR = A A can be directly indexed from Azz-ı (Eq. 9h. that has been computed in the prior iterations. Hence, we can simplify Eq. TT A' AT 24 of (1lg(((x1)))1
A 24
(R.R) OK-1
A
a Oa-ok-IAA _a]T,
24
where R [m,, rny) is the index of reusing vectors in A A E X denotes index R rows and R columns from A AR_ R denotes to index R rows from A and a E Rax1 is the solution to QCLP problem sampled vectors P E [R(n-n))xd Anx = Any can be obtained by:
Hence, by reusing n& vectors A", and newly
A ArT rT
A PT PP
A
(11)
P
5

---

Consequently, the complexity of computing Azg can be reduced to O + (n - ny md)dd), which decreases the reuse rate me increases. The overall computation complexity analyzed and compared with other 70 methods in Appendix B The algorithm flow is shown in Alg. D
3.4 Convergence Analysis
We start the analysis with lemma that estimates the distance between the estimated gradient in our method and the projected exact gradient of the function.
Lemma 3.1. Let satisfies Assumption
3.1 and
3.2
For every E N, Any E Raxd and || |l <
Lbyn
Az. (
Az.
(x+))]
(12)
Then derive the distance bound between the estimated gradient and the exact gradient of the function.
Lemma 3.2. Let the SVD Az. UAVT, A (A.a A Pk. denotes the spectral radius of A Based on Lemma 3.1 we huve:
PkL26nn
[1{(xx) - ([(xx)| < [+|]
(13)
4
where En [V
1 == V=V
Consequently, we can derive the following proposition:
-(02-r) have: 1.66'
Proposition 3.3. Suppose is convex and 3 E [0, 1) satisfying pk S
f(xx) f(x*)
C
O
0 2
(14)
0y2
which yields sublinear convergence. Proof can be found in Appendix A Furthermore, our experi- mental results demonstrate that our method can converge in many scenarios, including simulation benchmarks and real-world applications.
3.5 Relationship with Linear Interpolation Methods
We show that our method can be regarded as a general version of the linear interpolation strategy.
First, consider the situation where = d and the matrix A, is nonsingular, the estimated gradient by our method in Eq. and be simplified as g(x) x A A,A A A formulation to the gradient estimated by linear interpolation strategy (5).
A which has a similar
Second, consider a more general situation where singular value decomposition (SVD) is denoted as A, UAVT. Then A₂ A,A = UAATUT and the estimated gradient by our method in Eq. 5aaan transformed as:
d, the matrix A, can be singular, and its
g(x) x AT A VATU (UAA CLAATUTY UT)
VA (AA
(15)
Since U and V are orthonormal, have (VA (AVAATAAATT> (UTT)- A.. showing that VA (AT(AA))-UT is the veeudo-inverse of A,. Consequently, method can be regarded as a general version of the linear interpolation strategy.
Moreover, in the spacial case where A. is orthonormal, AAT = E. is identity matrix, and Eq. 15 can be simplified as g(x)) VA VATU-AA AJ A, consistent with the gradient estimation in
Experiment
4.1 Protocols
To demonstrate the efficacy and efficiency our method, we conduct experiments on both simulation benchmarks and real-worl world scenarios. First, we test on the CUTEst (24), of the most popular

---

20 SGD
20 SGD
20-50 20-56D
20 SGD
Tureton 7140
Zd.igrdGG
AMMMM
Tunchin Ditue 7ho
3030
20-iggn5D
NM
20-
20-M5sMM
MM
RaUZO
Itarodin
Soration
Koration
Iorstion
140
(a) BROYDNBDLS((=500) (b) COATING(d=134)
(c) SROSENBR(d=500) (d) BOXPOWER(:=1000)
Figure Illustration of the optimization procedure of different solvers on four problems. Each solver conducts 500 iterations to update the variables. The dimension of variable d is shown in the bracket in the title of each figure. We run each solver at each setting three times and plot the average performance and standard deviation as the line and shadow.
benchmarks for derivative-free optimization containing over 1,500 problems, many of which are parametrized to allow for variable dimensions through user-sclectable parameters. Specifically, utilize the PyCUTEst [21] a Python interface, to import the optimization problems from the CUTEst and solve them by multiple ZO solvers implemented ourselves the PyTorch platform. Second, we conduct experiments on the black-box adversarial attack task, a real-world application for ZO solvers. The task attempts to search additive noises for each pixel of inputs confuse pretrained neural network, which is one of the most popular scenarios for ZO solvers. Third, we apply our method to the Neural Architecture Search (NAS) task, aiming to search for the best neural architecture. Since querying once in NAS task consumes large amounts of resources, we conduct experiments on NAS-Bench-201 [18) which can directly query the performance of 15,625 architectures on three datasets including CIFARIO, CIFARI00, and ImageNet- 1oefeet--61166 120. Finally, we conduct experiment on large-scale neural network training by tine-tuning large language models (LLMs), demonstrating the applicability of our proposed ReLIZO.
4.2 Experiments on the Simulation Benchmark
We compare the performance of our method with baselines four problems from the CUTEst optimization benchmark, containing an ill-conditioned or singular type problem (BOXPOWER), a nonlinear optimization test problem (SROSENBR), and a problem coming from application scenarios (COATING). The dimension of variables ranges from 50 to 1000 to evaluate the effectiveness of our method on both low-dimension and high-dimension problems. The baselines include ZO-SGD (22), ZO-signSGD [34]] and ZO-AdaMM [12) implemented by ourselves on the PyTorch platform. Each solver updates the variables 500 times and samples 8 random directions each iteration update the variables. We also utilize grid search to obtain the best learning rate for each problem. The candidate learning rate 77 ranges from (0.0001, 0.0002. 0.0005, 0.001, 0.002, 0.005, 0.01, 0.02, 0.05, 0.1, 0.2. 0.5). As for our method, the total sample size at each iteration is set as 8, and the reusable distance bound is set as 21,, where 7) is the learning rate obtained by the grid search. The variables are initialized as the default values in CUTEst for all solvers. Experiments at each setting are repeated three times, and the results are shown in Fig. [ We observe that our method has a faster convergence speed and achieves better solutions to different problems. Moreover, the standard deviation of our method among three replications (shadows Fig. is much lower than other methods, showing that our method can stably find good solutions.
Ablation Study about sample size N and reusable distance bound b. To evaluate the impact of sample size at each iteration and reusable distance bound, we run our method for 500 iterations on different sample sizes ranging from (6. 8, 10, 20, 50, 100, 200} and reusable distance bounds ranging from (0, 7) 27,, 5n)) where 17 is the learning rate at each iteration. Note that we set the sample size smaller than the dimension of variables. Results are shown in Fig. 2 The x-axis indicates the sample size, the y-axis shows the optimal value found by our solver after 500 iterations, and colors indicate different reusable distance bounds. For each setting, we conduct three replication experiments and plot the average performance and standard deviation the nodes and lines. We also illustrate the # reused queries in Fig.
reusing rates
2 as the floats in the boxes beside the scatters. According to the
total sample size
7

---

bm
bno b-20
12
10-
10-
BBC
30
30
50
100
Numbberr Samples the Step,
Number Samples Step,
(a) BROYDNBDLS (d=50)
(b) SROSENBR (d=500)
Illustration of the best function value found by our method in 500 iterations under different settings of sample size N and reusable distance bound b. We conduct three replication experiments at each setting and plot the average performance and standard deviation as nodes and lines. We also illustrate the reusing rates as the floats in the boxes beside the scatters.
Figure 2:
results, we have three observations: 1) A larger reusable distance bound b has a larger reusable rate, and larger sample size will also lead to larger reusable rate. 2) As the sample size increases, large reusable distance bound can also find good solutions, demonstrating the rationality of reusing queries. 3) the standard deviation of performance is pretty small when N > 6 and b 5n, showing that can stably find good solutions. Experiments and analysis on extreme conditions (e.g. small N and large d) in Appendix C.1 also demonstrate the robustness and scalability of ReLIZO.
4.3 Experiments on Black-Box Adversarial Attacks
ZO methods are popular solutions to black-box adver- sarial attacks, and conduct experiments to show the effectiveness of our ReLIZO. We focus on universal adversarial perturbation against images [27] [1] and attack a well-trained DNN model on the CIFAR-10
18
ReLiZO
16
20-AdaMM
Z0-SMD
14-
20-SGD
dataset. Supported by B and [2], we consider the optimization problem as: argmin
12
Z0-signSGD
EM EE f(x, +
6) + +|51| s.t. (x: + 6) E 0.5, Vi, where f(z; + 6) denotes the black-box attack loss for im- age i, A >>> 0 is regularization hyperparameter be- tween minimizing the attack loss and the l distor- tion. We normalize the pixel values to [-0.5, 0.5)4, and we specify the loss function for untargeted attack as f(x') = maxj#t (Z('', max ((x)) x}. where 2(x')x denotes the prediction score of class given the input æ', and > 0 governs the gap between
10000
Iteration
Figure 3: Attack loss of universal attack.
the confidence of the predicted label and the true label In experiments, we set 0, and the attack loss if reaches the minimum value 0 as the perturbation succeeds to fool the network.
We conduct experiments the CIFAR- 10 test dataset. Similar to the settings in Z0-AdaMM (12), we randomly select 100 images, ensuring that these images are initially correctly classified by the model. We conduct adversarial attacks on these selected images and compare the perfor- mance of our proposed ReLIZO method with 4 existing methods: ZO-SGD 222. ZO-signSGD 34, ZO-SMD 19), and ZO-
Table Summary of attack success rate using differ- ent zeroth-order optimization methods with the final & distortion remains relatively consistent. The result is based on universal attack against 100 images under T 20000 iterations.
Methods ZO-SGD
Attack success
Final & distortion
77%
1.34
ZO-signSGD
80%
1.36
AdaMM 12] We conduct a linear search
ZO-SMD
85%
1.38
for the learning rate of each approach to maintain consistency in the & distortion when employing each method for the at-
Z0-AdaMM
87%
1.37
ReLIZO
92%
1.37
8

---

Table 2: Top-1 test classification accuracy (%) WAS-Bench-200 The first block shows the performance gradient- based methods quoted from the paper of block shows the performance of various ZO methods, which are implemented by ourselves the Py platform. The performance of the methods based on ZO optimizers is averaged over three independent trials.
The second
CIFAR-10
CIFAR-100
ImageNeet-1-11
Methods
valid
test
valid
test
valid
test
ENAS
37.51
53.8910.58
13.37.1..35
13.96.12.33
15.06.11.95
14.84.12.10
RSPS
80.42:13.58
84.0743.61
52.12=5.55
52.31
27.2243.24
26,28:3.00
DARTS- V1 32
39.77=00.00
54.30=0.00
15.03=0.00
15.61=0.00
16.43=00.0
16.32:t0.00
DARTS V2
32
39.77=0.00
54.30=0.00
15.03=0.00
15.61=0.00
16.43:0.00
16.32210000
GDAS 17
89.89=0.08
93.61=0.09
71.34=:0.4
70.70=10.30
41.59:11.33
41.71:10.88
SETN 16
84.04+0.28
87.64+0.00
58.86+00.06
59.05+0..2
33.06+00002
32.52+0.21
70-AdaMM 12
85.97+2.228
89.59+2.25
63.24+4.68
63.28+4.86
35.43+4.07
35.63+4..73
2O-SGD 22
18.18+1.26
91.60+1.15
67.59+1.51
67.49+1.05
39.83++1880
39.79+1.83
20-signSGD
34
85.94+4.37
89.74+3.64
61 61.8928.82
62.41+8.91
35.23+6.82
35.28+7.51
ReLIZO (ours)
19.50=1.53
69.00 92.45+1.84
69.03+1198
42.09
42.31+3.87
tacks, and compared the loss and the attack success rate on this basis. Fig. illustrates the overall loss curves, while Table [ the success rates of the adversarial attacks for each method over = 20000 iterations. compared to other ZO methods. Simultaneously. it achieves the highest attack success rate (more than 5% improvement) under condition where the lz distortion remains relatively consistent. This result fully demonstrates the effectiveness of our method.
we can see, our ReLIZO method exhibits the fastest rate loss reduction
4.4 Experiments on Neural Architecture Search
AutoML, including neural architec- ture search R2
40
51
50
49.
46
Table 3: Number of queries and the search cost (seconds) dur-
53) and hyper- parametrrr optimization tasks 7
ing the NAS procedure on the search space of NAS-Bench- 201.
48), has attracted wide attention due to its efficacy in reducing labor costs. Zero-order opti- mization is an effective algorithm for solving AutoML tasks [47,, which can be modeled as bi-level optimization.
43 26
Methods #Queries Cost (s)
70-AdaMM Z0-SGD
20- 20-signSGD
ReLIZO
19550
19550
19550
11885
63044
63429
69659
55005
Table reports the performance of our method on the
a popular benchmark in the The first block shows the performance of gradient- methods which is obtained from the paper [18]. The second block shows the performance of various 7O methods, in- cluding Zo-AdaMM, ZO-SGD, Z0-signSGD and ours. Specifically, similar to DARTS, we iteratively train the operation weights by the SGD optimizer and train the architecture parameters by the ZO optimizer for 50 epochs on the CIFARIO dataset. To query the performance of one sampled direction, we update the architecture parameters by the direction and return the loss after training the operation weights for 10 iterations. The accuracy of discovered architectures on three datasets is directly indexed from the benchmark. For each ZO optimizer, we conduct three replication experiments and report the averaged accuracy and standard deviation in Table 2 We observe that our method surpasses other ZO methods in performance. We also report the number of queries of each ZO optimizer during the whole search process and the search time in Table 3 Our method is much faster than other 70 optimizers with fewer queries. Notice that the queries in Table 3 are used to train the architecture parameters, while the cost consists of training operation weights and architecture parameters, making the reduction cost lower than the reduction of queries.
NAS task 332 17 [1..
4.5 Experiments on Parameter Efficient Fine-tuning
Compared to gradient-based methods, 70 methods are well-suited for black-box optimization problems where gradients with respect to the variables are unavailable. Additionally, 70 methods more memory efffiee-efficient than gradient-based methods since they do not require backward pass,

---

Table Zero-order optimizers with different parameter efficient fine-tume -un-itiig methods on OPT-1.3b model (with 1.3 billion parameters) on the Stanford Sentiment Treebank v2 (SST2) task.
Fine-Tuning
LoRA
Tunnng
Prompt-Tuning
Methods
Acc
Memory
Acc
Memory
Acc
Memory
Acc
Memory
SGD
91.1
44.1 GB
93.6
44.1 GB
93.1
42.9 GB
92.8
50.6 GB
ZO-SGD
90.8
28.7 GB
90.1
19.7 GB
91.4
20.7 GB
84,4
18.8 GB
ZO-SGD-Sign
87.2
31,4 GB
91.5
19.7 GB
89.5
20.7 GB
72.9
18.8 GB
70-Adam
84.4
31.4 GB
92.3
19.7 GB
91.4
20.7 GB
75.7
18.8 GB
ReLIZO (ours)
93.4
35.7 GB
93.1
19.9 GB
91.8
20.7 GB
90.1
18.9 GB
making them applicable to network training, as demonstrated by recent works 55). Specifically, DeepZero [TO] introduces a principled ZO framework for deep learning that is computational-gin graphh graph- free and can scale to deep neural network training with performance comparable to first-order methods. The work (55) also applies ZO methods to large language model (LLM) fine-tuning, highlighting their memory efficiency and introducing a ZO-LLM benchmark.
To illustrate the applicability of ReLIZO in network training, we adopt it for fine-tuning an OPT-1.3) model (with 1.3 billion parameters) on the Stanford Sentiment Treebank v2 (SST2) task with a batch size 128, following the methodology of 70-LLM (55). The results, shown in Table Saolle/ioe inddcate that ReLIZO outperforms other ZO methods across various fine-tuning schemes, including full parameter fine-tuning (FT), LoRA, Prefix-tuning, and Prompt-tuning. Notably, ReLIZO even surpasses SGD in the FT scheme while requiring significantly less memory, demonstrating its promising potential.
5 Conclusion, Limitations and Future Work
This work handles gradient estimation in zeroth-order optimization by modeling it as quadratically constrained linear program problem, with analytical solution derived via the Lagrange multiplier method. Our method ReLIZO, decouples the required sample size from the variable dimension without the requirement of orthogonal condition in the recent linear interpolation works, making possible to leverage the queries in the prior iterations. We also show that part of the intermediate variables contributing to the gradient estimation can be directly indexed, significantly reducing the computation complexity. We further perform theoretical analysis of the convergence of ReL.IZO and show the relationship with the prior linear interpolation methods. The efficacy and efficiency have been shown in extensive experiments, including simulated benchmarks, NAS, and black-box adversarial attack tasks.
Limitations and Future work. Compared to the gradient- based methods, ZO methods require multiple queries of function evaluation at each iteration, which restricts their applications in real- world scenarios such as neural network training. Our ReLIZO can reduce the required number of queries by the reusing strategy. potentially broadening the scope of applications of ZO. which can be explored in future work. However, in cases where the consumption of one query is negligible, the profit due to the reusing technique decreases, causing a relative increase in the cost of solving the QCLP. We leave these problems in future work.
Impact Statements
This paper presents work whose goal is to advance the field of Machine Learning. Note that zeroth- order optimization is an effective method for black-box adversarial attacks as we have shown in Section 4.3 Its purpose is to evaluate the robustness of machine learning models, but we should also be aware of the impact this may have on Al safety. There are many potential societal consequences of our work, yet none of which we think must be specifically highlighted here.
10

---

References
[1] Alekh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. In Colt, pages 28 40. Citeseer, 2010.
[2] Larry Armijo. Minimization of functions having lipschitz continuous first partial derivatives. Pacific Journal of mathematics, 16(1):1-3, 1966.
[3] Anastasia Bayandina, Alexander Gasnikov, Fariman Guliev, and Anastasia Lagunovskaya. Gradient-free frree two-points optimal method for non smooth stochastic convex optimization prob- lem with additional small noise. arXiv preprint (tti::1700.0382... 2017.
[4] Albert S Berahas, Liyuan Cao, Krzysztof Choromanski, and Katya Scheinberg. Linear inter- polation gives better gradients than gaussian smoothing in derivative-free optimization. arXiv preprint 1rXiv:1905.13044 2019.
[5] Albert S. Berahas, Liyuan Cao, Krzysztof Choromanski, and Katya Scheinberg. theoretical and empirical comparison of gradient approximations in derivative- optimization. Found. Comput. Math., 22(2):507-560, 2022.
[6] Albert Berahas, Liyuan Cao, and Katya Scheinberg. Global convergence rate analysis of generic line search algorithm with noise. SIAM Journal on Optimization, 31(():1489-1555 1518, 2021.
[7] James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal Of Machine Learning Research, 2012.
[8] Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks, In 2017 ieee symposium on security and privacy (sp). pages 39-57. leee, 2017.
[9] Richard G Carter. On the global convergence of trust region algorithms using inexact gradient information. SIAM Journal on Numerical Analysis, 28(1):251-26)) 1991.
[10] Aochuan Chen, Yimeng Zhang, Jinghan Jia, James Diffenderfer, Konstantinos Parasyris, Jiancheng Liu, Yihua Zhang, Zheng Zhang, Bhavya Kailkhura, and Sijia Liu. Deepzero: Scaling up zeroth-order optimization for deep model training. In ICLR, 2024.
[11] Pin-Yu Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In AISEC, pages 15-26, 2017.
[12) Xiangyi Chen, Sijia Liu, Kaidi Xu, Xingguo Li, Xue Lin, Mingyi Hong, and David Cox. Zo- adamm: Zeroth-order adaptive momentum method for black-box optimization. NeurIPS, 32, 2019.
[13] Xin Chen, Yujie Tang, and Na Li. Improve single-point zeroth-order optimization using high-pass and low-pass filters. In ICML, volume 162, pages 3603-3620 2022.
[14] Minhao Cheng, Thong Lc, Pun-Yu Chen, Jinfeng Yi, Huan Zhang, and Cho-Jui Hsich. Query-efficient hard-label black-box attack: An optimization-ban based approach. arXiv preprint 0rXiv:1807.04457 2018.
[15] Andrew R Conn, Katya Scheinberg, and Lufs N Vicente. Geometry of interpolation sets in derivative free optimization. Mathematical programming, 111:141-172, 2008.
[16] Xuanyi Dong and Yang. One-shot neural architecture search via self-evaluated template network. In ICCV, pages 3680-3689. IEBE, 2019.
[17] Xuanyi Dong and Yi Yang. Searching for robust neural architecture four GPU hours. In CVPR, pages 1761-1770 Computer Vision Foundation/ / IEEE, 2019.
[18] Xuanyi Dong and Yi Yang. Nas-bench-201: Extending the scope of reproducible neural architecture search. In ICLR. OpenReview.net, 2020.

---

[19] John C Duchi, Michael Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, (1)):7788 2015.
[20] Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex opti- mization in the bandit setting: gradient descent without a gradient. arXiv preprint cs/0408007, 2004.
[21] Jaroslav Fowkes, Lindon Roberts, and Árpád Bürmen. Pycutest: an open source python package of optimization test problems. J. Open Source Softw., 7(78))4377, 2022.
[22] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, (3(4))2341-2366 2013.
[23] Allen A Goldstein. On steepest descent. Journal of the Society for Industrial and Applied Mathematics, Series A: Control, 3(1):147-151, 1965.
[24] Nicholas I. M. Gould, Dominique Orban, and Philippe L. Toint. Cutest: constrained and unconstrained testing environment with safe threads for mathematical optimization. Comput. Optim. Appl., 60535554-557, 2015.
[25] Genetha Anne Gray, Tamara G. Kolda, Ken Sale, and Malin M. Young. Optimizing an empirical scoring function for transmembrane protein structure determination. INFORMS Comput., 16(4):406 -188 2004.
[26] Frank Hutter, Holger H. Hoos, and Kevin Leyton- Sequential model-based optimization for general algorithm configuration. In LJON, 2011.
[27] Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In International conference on machine learning, pages 2137-2146. PMLR, 2018
[28] Kevin G. Jamieson, Robert D. Nowak, and Benjamin Recht. Query complexity of derivative-free optimization. In NeurlPS, pages
2012.
[29] Kaiyi Ji, Zhe Wang, Yi Zhou, and Yingbin Liang. Improved zeroth-order variance reduced algorithms and analysis for nonconvex optimization. In ICML, pages 3100-3109. PMLR, 2019.
[30] David Kozak, Cesare Molinari, Lorenzo Rosasco, Luis Tenorio, and Silvia Villa. Zeroth-order optimization with orthogonal random directions. Math. Program., (111)::119-11111 2023.
[31] Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence, UAI 2019, Tel Aviy, Israel, July 22-25, 2019, volume 115 of Proceedings of Machine Learning Research, pages 367-377. AUAI Press, 2019.
[32] Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: differentiable architecture search. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA USA, May 6-9, 2019. OpenReview.net, 2019.
[33] Sijia Liu, Jie Chen, Pin-Yu Chen, and Alfred Hero. Zeroth-order online alternating direction method of multipliers: Convergence analysis and applications. In International Conference Artificial Intelligence and Statistics, pages 288-297. PMLR, 2018
[34] Sijia Liu, Pin-Yu Chen, Xiangyi Chen, and Mingyi Hong. signsgd via zeroth-order oracle. In International conference on learning representations. International Conference on Learning Representations, ICLR, 2019.
[35] Sijia Liu, Pin-Yu Yu Chen, Bhavya Kailkhura, Gaoyuan Zhang, Alfred O. Hero III, and Pramod K. Varshney. primer on zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications. IEEE Signal Process. Mag., 37(5):43-54, 2020.
12

---

[36] Alvaro Maggiar, Andreas Wachter, Irina S Dolinskaya, and Jeremy Staum. A derivative-free trust-region algorithm for the optimization of functions smoothed via gaussian convolution using adaptive multiple importance sampling. SIAM Journal on Optimization, 28(2):1478-1507, 2018.
[37] Dhruv Malik, Ashwin Pananjady, Kush Bhatia, Koulik Khamaru, Peter L. Bartlett, and Martin J. Wainwright. Derivative-free methods for policy optimization: Guarantees for linear quadratic systems. J. Mach. Learn. Res., 21:21:1-21:51, 2020.
[38] Arkadij Semenović Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. SIAM J. OPTIM, 1983.
[39] Yurii Nesterov et al. Random mrdieett-free minimization of convex functions. Technical report, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE), 2011.
[40] Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In ICML, pages 4095-4104. PMLR, 2018.
[41] Luis Miguel Rios and Nikolaos V. Sahinidis. Derivative-free optimization: a review of al- gorithms and comparison of software implementations. J. Glob. Optim., 56(3):1247-1293, 2013.
[42] Hao-Jun M Shi, Yuchen Xie, Richard Byrd, and Jorge Nocedal. A noise-tolerant quasi-newton algorithm for unconstrained optimization. SIAM Journal on Optimization, 32(1):29-55 2022.
[43] Jasper Snoek, Hugo Larochelle, and Ryan P. Adams. Practical bayesian optimization of machine learning algorithms. In NeurlPS, 2012.
[44] Yun-Yun Tsai, Pin-Yu Chen, and Tsung-Yi Yi Ho. Transfer learning without knowing: Repro- gramming black-box machine learning models with scarce data and limited resources. In International Conference Machine Learning, pages 9614-9622 PMLR, 2020.
[45] Anirudh Vemula, Wen Sun, and J. Andrew Bagnell. Contrasting exploration in parameter and action space: A zeroth-order optimization perspective. In AISTATS, volume 89 of Proceedings of Machine Learning Research, pages 2926-2935, PMLR, 2019.
[46] Xiaoxing Wang, Xiangxiang Chu, Yuda Fan, Zhexi Zhang, Bo Zhang, Xiaokang Yang, and Junchi Yan. ROME: robustifying memory-efficient NAS via topology disentanglement and gradient accumulation. ICCV, pages 5916-5926. IEEE, 2023.
[47] Xiaoxing Wang, Wenxuan Guo, Jianlin Su, Xiaokang Yang, and Junchi Yan. Zarts: On zero- order optimization for neural architecture search. Advances in Neural Information Processing 2022.
Systems,
[48] Xiaoxing Wang, Jiaxing Li, Chao Xue, Wei Liu, Weifeng Liu, Xiaokang Yang, Junchi Yan, and Dacheng Tao. Poisson process for bayesian optimization. In AutoML, volume 224 of Proceedings of Machine Learning Research, pages 3/1-20, 2023.
[49] Xiaoxing Wang, Zhirui Lian, Jiale Lin, Chao Xue, and Junchi Yan. DIY your easynas for vision: Convolution operation merging, map channel reducing, and search space to supernet conversion tooling. IEEE Trans. Pattern Anal. Mach. Intell., 45(1 I): 13974-119999 2023.
[50] Xiaoxing Wang, Jiale Lin, Juanping Zhao, Xiaokang Yang, and Junchi Yan. Eautodet: Efficient architecture search for object detection. In ECCV, volume 13680 of Lecture Notes in Computer Science, pages 668-684, 2022.
[51] Xiaoxing Wang. Chao Xue, Junchi Yan, Xiaokang Yang. Yonggang Hu, and Kewei Sun. Mergenas: Merge operations into one for differentiable architecture search. In IJCAI, pages 3065-3072, 2020.
[52] Yining Wang, Simon Du, Sivaraman Balakrishnan, and Aarti Singh. Stochastic zeroth-order optimization in high dimensions. International conference on artificial intelligence and statistics, pages 1356-1365. PMLR, 2018.
13

---

[53] Beichen Zhang, Xiaoxing Wang, Xiaohan Qin, and Junchi Yan. Boosting order- peeerrigeg and transferabilitty for neural architecture search: joint architecture refined search and fine- tuning approach. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 5662-5671, 2024.
[54] Yan Zhang, Yi Zhou, Kaiyi Ji, and Michael M. Zavlanos. A new one- one-point oracle for black-box learning and control. Autom., 136: 10006, 2022.
[55] Yihua Zhang, Pingzhi Li, Junyuan Hong. Jiaxiang Li, Yimeng Zhang, Wenqing Zheng, Pin- Yu Chen, Jason D. Lee, Wotao Yin, Mingyi Hong, Zhangyang Wang, Sijia Liu, and Tianlong Chen. Revisiting zeroth-order optimization for memory-efficient LLM fine-tuning: benchmark. In ICML, 2024.
14

---

A Convergence Analysis
A.1 Proof of Lemma 3.1
Lemma 3.1 Let f be a function satisfying Assumption 3.1 and 3.2
For every E N, Az, E B
and A < b, we have:
Lb
( A., (=(=))) <
Proof. We start with the Taylor's expansion of function f defined in Eq.
((x) f(x A.) f(x) / A (
A (Vf(x + Vf(x))dt
(Assumption 3.2
AT Lidt
thus
LI|A,1" 1
[g)) vf(x))I <
With the condition | |l < b, we then derive that
Lbvn
Ar,, (g(zx) vf((x)))]
2
which completes the proof.
A.2 Proof of Lemma
Lemma 3.2 Let the SVD of A.. UAVT, A=1 = (Ar, AI. Pk denotes the spectral radius of
A, Based on Lemma 3.1 we have:
[19(.x) - [(xx)]1 {r\V + P6
where
ΣS
11, w= V-VV(((
|
Without losing generality, omit the subscript h: in proof. g(x) AJ A-A--A, and A5 = A.g(r) = (z) Vf(x)) + A, Vf(x), we define
Proof.
E = Ae(g(r) vf(=)),
then we have:
(l V((x)] = | 1 A V/(z)]
= A A. 1 - VZ A
where Idxd denotes an identity matrix with d rows and columns. Suppose the SVD of A, UAVT, substitute to A --1AA11 - Az. we have:
AJ 1 A daxd VA T (AA - - 1uxd
pnxn
0
v
VT - 1dxd V
...
VT A vid-uVT
15

---

Then, we can simplify 119(z) - V f()) as:
(19(z) - vf(x)l] VVT'">>"V +
| ((أ) + + ATA"")
where (zr 2) denotes the inner product of vectors and According to the definition of inner product and the SVD of A2 = UAVT, we have:
= "/"
Moreover, denote VV))(x then | | (1x))1
Σjzn uz. we define
d n
Cj 0z
VV x3
Therefore,
(1(x)) - -
<>] - E' p||
where p the spectral radius of A According to Lemma 3.1 we have:
(1((x)) V/(x)| <r\V/<(>>> + pL263n
A.3 Proof of Proposition 3.3
Proposition 3.3 Suppose is convex function and 3 A [0, 1) satisfying Pk: -
1260n
we have:
C
[(xx) - f(x)) k(1 0)2
13 with Pk I 4(02 [(=)]
Proof. Based on Lemma 3.2 we substitute Eq.
then we have
13ban
l1g(xx)
(f(x)) < 0 f(x))l
This condition also referred norm condition and is introduced and studied in in the context of trust-region methods with inaccurate gradients. This then yelids
f()x] < [|<(xx))| < + 0) [<)(<))]
(16)
by using Stuchy-Schward inequality. Note that our iteration also satisfies the Armijo condition
f(*++1) f(xx) (1
(17)
where e e (0, 1) is constant, and σ is the magnitude of descent direction found by using Armijo backtracking line search. By (16), we have
f(x++1) < [(xx) () f (1 ( f(z))
Assumption A.I. (Convexity and bounded level sets of f) The function is convex and has bounded level sets, i.e.,
I - D for all x with f(x) S f(x)),
where x" is global minimizer of f. Let f = f(x").
16

---

By Assumption A.1
we have
((x)) f(xx) S (T(a) (ox - x²)
V (v || x=1l
x D. V
Let 24 f(xx) f*, thus
2k Ek+1 = f(xx) - [(
2 c10k(1 - V
c1 (1 -0)22
D22
which implies
2/
2k+1
2k
2k+1
c10x 0)2
Zk++1
Zk
2k
1)2
k
1
c1
2)
2i 1i
k-1
c1
0)2
2i o3
2k
20
21-1
2
20
1
D
thus
D
2x = f(xx)((x))))))))){))) f+ e1 (1 - 01=0)=
(18)
Moreover, in line with the assumption in (30]. we set the minimum step size in the algorithm. In fact, the previous works [6] and 42) have shown that the convex case, the number failed line searches be bounded w.r.t Thus mainly focus on the case when (7) holds. In this case,
define D² then (88 implies o
D
D
C
24 f cI - -)- 21 0z
kaci 0)²
k(1
-0)2
which shows a sublinear convergence rate. Similar to the prior ZO works (Table 1 in (29), we set the minimum step size -O))) to guarantee the correctness of the assumptions, thus the convergence rate our method
D2
k(1 0)2 ~ 0 d )
f(xx) - f(x)) <
0
(19)
kegg(1 0)2
B Comparison of Computation Complexity
The algorithm flow is shown in Alg. [ Suppose n is the sample size, d is the dimension of variables. and n < d. For the k-th iteration, suppose ny vectors are reused from the prior iterations and n&g vectors are newly sampled. The computation complexity includes two parts: querying function evaluations for newly sampled vectors, and computing gradient estimation by Eq. 5 For the former, denote the complexity of querying function evaluation once O(c(d)), where c(-) could be linear, polynomial, etc.. Then querying n ny times requires O((n ng (c() computation resources. As for the latter, Eq. requires compute Ar, with complexity O((n nx)nd), the inverse of matrix Ag, with complexity O(r²), and the matrix multiplication of A A,,7 Ay with complexity O(n² + nd). Since < d, the overall computation complexity for the k-th iteration is On'' + (n - n.. mnd + (n- )c(d). Table compares the computation complexity in one iteration of our method with prior smoothing and linear interpolation methods. Except for our methods, others do not support the reusing strategy.
17

---

Table Comparison of computation complexity in one iteration between various ZO methods.
Methods
Computation Complexity
ZO-SGD 22
O + nc(d))
70-signSGD
+ Ond + ne(d))
ZO-AdaMM
Conventional Linear Interpolation (n=d) [5]
O de(d))
Linear Interpolation w/ orthogonal vectors (30
O Ondd nc(d))
ReLIZO (ours)
O + (n mx)nnd + (n -n))cd))
Table 6: Comparison of various ZO methods on small sample size N 2.
Methods
ARGTRIGLS CHNROSNB COATING BOXPOWER SROSENBR BROYDNBDLS
ZO-SGD
22
6.03
376.32
2007.45
361.72
2706.39
116.9
Z0-signSGD
66.33
224.94
1431.66
48.85
1398.44
91.39
20-AdaMM 12
3.27
50.23
994.63
33.13
355.32
3.83
ReLIZO (ours)
2.38
44.38
831.5
27.44
115.48
0.65
Table Comparison various ZO methods on large dimension d.
SROSENBR
d=1000
d=5000
d=10000
ZO-SGD 22
293.81
45432.77(35091.77
79998870 83)
ZO-signSGD
34
883.52(867.00 .2)
79)
(1449968449628.88
ZO-AdaMM
47.54(31.04)
32071.75(21730.71
87781.39(41666.55
ReLIZO (ours)
16.50(0)
10341.04(0)
47120.87(0)
BOXPOWER
d=1000
d=10000
d=20000
ZO-SGD (2
11.10(2.11)
118.05(28.13)
248.02(67.03)
ZO-signSGD 34
37.74(28.75)
325.92(236)
713.91(532.92)
ZO-AdaMM 12
20.88(11.89)
235.39(145.477
471.19(290.2)
ReLIZO (ours)
8.99(0)
89.92(0)
180.99(0)
C Supplementary Experiments
C.1 Experiments Extreme Conditions
Experiments on small sample size N: We set 2 and compare ReLIZO and other methods on six PyCUTEst optimization tasks. The results are reported in Table showing that ReLIZO also surpasses other baselines. We analyze that the methods based on smoothing strategy utilize Monte Carlo sampling to estimate the expectation of various directional derivatives and small N will lead biased estimation as shown in [5). In contrast, our ReLIZO computes the projection of gradient on space generated by arbitrary numbers of sampled directions by solving the QCLP, and thus can also work pretty well under a small N.
Experiments on large dimension d: We conduct experiments on two PyCUTEst optimization tasks with an adjustable variable dimension. Each optimizer updates the variables 500 times and samples random directions at each iteration to update the variables. We also utilize grid search to obtain the best learning rate for each optimizer for different tasks. The best solution obtained by each optimizer are reported in Table [ and the values in the brackets report the gap between each baseline and ReLIZO.. The results show that the improvement of ReLIZO is increasing as d increases for each optimization task. We analyze that the sample size N becomes relatively small compared to the dimension as increases, our method computes the projection of gradient on a space generated by N sampled directions by solving the QCLP, and thus can also work pretty well even if N <<< d.
18

---

C.2 Discussion on the Line Search
We adopt line search adaptively adjust the stepsize to ensure fast convergence rate. Our experimental results show that there are few queries from line search during the whole optimization process most cases. Specifically, there are queries from line search NAS task and several optimization tasks in PyCUTEsst including CHNROSNB, SROSENBR, and BOXPOWER. We report the number of queries in each task in Table X where '#L.S' denotes the number of queries from line search, '#Queries' denotes the number of actual queries including #LS during the optimization procedure, '#Reused' denotes the number of reused queries, T" denotes the total queries required by other methods without reusing strategy (N is the sample size per iteration and T is the number of iterations).
Table Number of queries from line search, total queries, reused samples during the optimization process.
ARGTRIGLS CHNROSNB COATING BOXPOWER SROSENBR BROYDNBDLS NAS-Bench-201
#LS
115
77
90
#Queries
3689+115
2294+0
3780+77
2715+0
2526+0
1353+90
11885+0
#Reused
311
1706
220
1285
1474
2647
7665
N x
4000
4000
4000
4000
4000
4000
19550
C.3 Ablation Studies on Other Problems
Results of ablation studies on another two problems MANCINO and ARGTRIGLS are shown in
Fig.
40
b=0
2e2g
bwg bwg
b=20
40
10
20
20
Camplessie Step.
(a) MANCINO (d=100)
(b) ARGTRIGLS (d=200)
Figure 4: Illustration of the best function value found by our method in 500 iterations under different settings of sample size N and reusable distance bound b. We conduct three replication experiments at each setting and plot the average performance and standard deviation as nodes and lines. We also illustrate the reusing rates the floats in the boxes beside the scatters.
We also report the optimization procedure of our method at different settings of reusable distance bound b in Fig. and sample size in Fig. 6
C.4 Improved Sampling Strategy with Momentum
The ability of ReLIZO sample new vectors from an arbitrary distribution can be considered one of its strengths compared to other ZO methods. In contrast, smoothing-based ZO methods have to rely on Gaussian or uniform distributions with mean of zero. We introduce an effective sampling strategy inspired by SGD with momentum. Specifically, we propose sampling momentum strategy where the sampling probability in the current iteration follows a distribution defined as
Table 9: Comparison of ReLIZO and ReLIZO-m m NAS tasks.
Method
vaalR CIFAR10-test
CIPAR100-valid
CIFAR 100-test
ImageNNt-116 Notte6-120ttssss
ReLiZO
89.50
92.45
69.00
69.03 69.63
42.09
42.31
Re m
90.71
93.41
70.40
42.79
43.22
19

---

3 100-
(a) BROYDNBDLS (d=50)
(b) MANCINO (d=100)
(c) COATING (d=134)
300
186
(d) ARGTRIGLS (d=200)
(e) SROSENBR (d=500)
(f) BOXPOWER (d=1000)
Figure 5: Illustration of the optimization procedure of our method at different settings of reusable distance bound b. The sample size fixed as 8.
4:20
35-
208
(a) BROYDNBDLS (d=50)
(b) MANCINO (d=100)
(c) COATING (d=134)
205
155
(d) ARGTRIGLS (d=200)
(e) SROSENBR (d=500)
(f) BOXPOWER (d=1000)
Figure 6: Illustration of the optimization procedure of our method with sample size n. The reusable distance bound is fixed as 21y.
p(x,) = (gN()-1,,)) + (1 - at) (0, a). with N() denoting a Gaussian distribution, 9t-1 is the estimated gradient in the last iteration, the momentum parameter, and the standard deviation. The results of this approach, labeled as ReLIZO-m, are presented Table 9
C.5
Additional Experimental Results on the Reusable Distance Bound b
In Fig. 5 we observe relative performance drop (slightly slower convergence) when the reusable distance bound b > However, this does not imply that the reuse strategy is ineffective in this case. The ARGTRIGLS problem is characterized by rugged landscape with numerous local minima. In this case, as shown in Fig. 4bb), even with b = and a sample size n 8, the reuse rate of ARGTRIGLS exceeds 90%, whereas reuse rates for other problems are generally below 50% (e.g. MANCINO with d=100 in Fig. aa). SROSENBR with d=500 in Fig. b)). This high reuse rate indicates that number of new queries during optimization is relatively small, contributing to observed decrease in convergence speed. To address this issue, we can employ simple strategies such as reducing the reusable distance bound Table 10 illustrates that performance improves as decreases.
20

---

Table 10: The objective value and total reuse rate of different reusable distance bound b.
reusable distance bound
b 0
b 0.01I)
b 0.05m
0.1
b b= 0.5m
b 7)
objective value (iter=500)
0.133
0.162
0.298
0.495
3.768
8.158
objective value (iter=2000)
0.053
0.063
0.166
0.311
1.834
3.825
total reuse
0%
16.6%
72.4%
82.3%
94.7%
96.8%
Moreover, setting an upper bound for the reuse rate each iteration can also help. Table 11 reports the performance when the maximum reuse rate in each iteration is restricted to 50%. We observe that with & 0.05r and 2000 iterations, there minimal performance degradation, even with reuse rate of approximately 30%.
Table 11: The objective value of different reusable distance bound with a restricted maximum reuse rate.
reusable distance bound
= 0
= 0.01n
= 0.05n)
= 0.1v)
b = 0.5l)
b =
objective value (iter=500)
0.133
0.164
0.183
0.255
0.312
0.341
objective value (iter=2000)
0.053
0.046
0.054
0.063
0.075
0.074
total reuse rate
0%
11.4%
34.2%
41.9%
47.9%
48.9%
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer:
[Yes]
Justification: The main claims are clearly presented in the abstract and introduction, and further elaborated and substantiated throughout the subsequent sections of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Refer Sec 5
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
22

---

Justification:
Refer to Appendix A
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proof' can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: In paper, we provide detailed descriptions of each step of the algorithm, the pseudocode, and all settings required to replicate the experiments. Additionally, we commit to making the code publicly available by the time of the camera-ready submission.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
23

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
Open source upon acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu http:///ggiddeeeeeouuuuumbbbbi ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Refer Sec
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Refer to Sec
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Refer to Sec and Appendix C.1 (e.g. the training epochs and the clock time of experiments are provided.)
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://///errrppp.ppppp/l/////// ittiha/eeeeccccccceeeeeeeeee
Answer: [Yes]
Justification: This paper conforms, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Refer to Sec
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
25

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The creators and original owners of all assets used in the paper are properly credited, and the licenses and terms of use are explicitly mentioned and fully respected.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the batasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
26

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "BYO12EN68o", "reviewer": "Reviewer_YYyS", "summary": "This study introduces a novel gradient estimation algorithm that operates solely on forward function evaluations. The method employs a Quadratically Constrained Linear Program (QCLP) to determine the optimal linear approximation of sample vectors. The authors present performance enhancement strategies, including sample reuse and efficient inverse matrix computation within the QCLP framework. Empirical evaluations conducted on black-box adversarial attacks and neural architecture search demonstrate the proposed algorithm's superiority over existing zeroth-order methods.", "questions": "See weakness.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed method is natural. Approximating the gradient using linear combinations of samples and formulating as the QCLP is an intuitive idea, and the auxiliary techniques employed in this study are both judicious and pertinent to the research objectives.\n\n2. The paper is well-written and easy to follow.", "weaknesses": "1. Zeroth-order gradient estimation has a relatively limited impact. While the proposed zeroth-order gradient estimation method demonstrates superiority over existing algorithms in its class, its overall impact on solving underlying optimization problems may be constrained. This limitation is exemplified in the NAS evaluation, where ReLIZO does not consistently achieve optimal performance.\n\n2. According to my interpretation, in ReLIZO algorithm, obtaining new samples from the input space in each iteration is random and arbitrary. I feel there might be more effective strategies to sample new vectors based on known information. Could the authors comment on this?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful and valuable comments. We hope to address your concerns by answering your questions below.\n\n**Q1:** Zeroth-order gradient estimation has a relatively limited impact. This limitation is exemplified in the NAS evaluation, where ReLIZO does not consistently achieve optimal performance.\n\n**A1:** Thank you for highlighting the inherent limitations of zeroth-order (ZO) methods. Though it is true that ZO methods generally face these constraints, they offer significant advantages over gradient-based methods in black-box optimization scenarios where gradients with respect to variables are not available. Additionally, ZO methods tend to be more memory-efficient, since they do not require backward propagation. This makes them suitable for large-scale tasks such as fine-tuning large language models (LLMs), as demonstrated in recent work [1]. We applied our method to fine-tune an OPT-1.3b model (with 1.3 billion parameters) on the Stanford Sentiment Treebank v2 (SST2) task, and the results are summarized in the table below:\n\n| Optimizer     | Fine-tune Acc | Fine-tune Memory cost |\n| ------------- | ------------- | --------------------- |\n| SGD           | 91.1          | 44.1 GB               |\n| ZO-SGD        | 90.8          | 28.7 GB               |\n| ZO-SGD-Sign   | 87.2          | 31.4 GB               | \n| ZO-Adam       | 84.4          | 31.4 GB               |\n| ReLIZO (ours) | 93.4          | 35.7 GB               |\n\nRegarding NAS tasks, DARTS and GDAS are two classic gradient-based methods with distinct settings. DARTS trains all parameters in the supernet at each iteration, whereas GDAS samples a sub-network from the supernet at each iteration and trains only the parameters within that sub-network. Our experiments employed DARTS's settings. The results in Table 2 demonstrate that all ZO methods outperform DARTS, and ReLIZO surpasses all other ZO methods, highlighting the effectiveness of our approach.\n\n[1] Zhang Y, Li P, Hong J, et al. Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark[C], ICML 2024.\n\n**Q2:** In ReLIZO algorithm, new samples in each iteration is random and arbitrary. There might be more effective strategies to sample new vectors based on known information. \n\n**A2:** Thank you for your suggestion. The ability of ReLIZO to sample new vectors from an arbitrary distribution can be considered one of its strengths compared to other ZO methods. In contrast, smoothing-based ZO methods have to rely on Gaussian or uniform distributions with a mean of zero. We appreciate your insight and introduce an effective sampling strategy inspired by SGD with momentum. Specifically, we propose a sampling momentum strategy where the sampling probability in the current iteration follows a distribution defined as $p(x_t) = \\alpha N(g_{t-1}, \\sigma) + (1-\\alpha)N(0, \\sigma)$, with $N()$ denoting a Gaussian distribution, $g_{t-1}$ is the estimated gradient in the last iteration, $\\alpha$ as the momentum parameter, and $\\sigma$ as the standard deviation. The results of this approach, labeled as ReLIZO-m, are presented in the table below:\n\n\n| Method   | CIFAR10-valid | CIFAR10-test | CIFAR100-valid | CIFAR100-test | ImageNet-16-120-valid | ImageNet-16-120-test |\n| -------- | ------------- | ------------ | -------------- | ------------- | --------------------- | -------------------- |\n| ReLIZO   | 89.50         | 92.45        | 69.00          | 69.03         | 42.09                 | 42.31                |\n| ReLIZO-m | 90.71         | 93.41        | 70.40          | 69.63        | 42.79                 | 43.22                | \n\nThese experimental results demonstrate that incorporating an effective sampling strategy can significantly enhance performance. We plan to explore this approach in greater depth in future work.", "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": "", "extra_scores": {}}, {"review_id": "p44YTsT8ME", "reviewer": "Reviewer_VWEi", "summary": "The paper introduces ReLIZO, a novel zeroth-order optimization method leveraging linear interpolation to estimate gradients efficiently. It reduces the complexity of gradient estimation by reusing prior queries without additional conditions on sample size, decoupling it from variable dimension constraints. ReLIZO models gradient estimation as a quadratically constrained linear program, solving it analytically to reduce computation complexity. Experimental results demonstrate ReLIZO's efficacy in various scenarios, including black-box adversarial attacks and neural architecture search, showcasing faster convergence and better solutions compared to existing methods.", "questions": "In Figure 5, the results for the ARGTRIGLS problem indicate that any reusable distance bound leads to a performance drop. What is the specific structure of this problem? Does this suggest that the reuse strategy may be ineffective in certain special cases?", "limitations": "The authors have adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "* The paper is well-written, with clear and easy-to-follow explanations.\n* The paper introduces a method for estimating gradients using arbitrarily sampled vectors without requiring orthogonal conditions or adherence to a specific distribution, enabling the reuse of queries to accelerate the zeroth-order (ZO) optimization process.\n* Extensive experiments on simulation benchmarks and real-world applications validate the method’s performance.\n* The paper highlights that ReLIZO can be viewed as a generalized version of traditional linear interpolation methods, capable of handling both equal and smaller sample sizes compared to variable dimensions. This demonstrates ReLIZO's theoretical soundness and enhanced flexibility in gradient estimation.", "weaknesses": "* The effectiveness of reusing queries depends on the choice of the reusable distance bound, which might require fine-tuning for different applications, adding complexity to its implementation.\n* While the method reduces the number of function queries, the process of solving the quadratically constrained linear program might introduce additional computational overhead for large $n$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful and valuable comments. We hope to address your concerns by answering your questions below.\n\n**Q1:** The effectiveness of reusing queries depends on the choice of the reusable distance bound, which might require fine-tuning for different applications, adding complexity to its implementation.\n\n**A1:** In our method, the reusable distance bound $b$ restricts the distances between reusable samples and the current point and should be of the same order of magnitude as the step size. Following previous ZO research (Table 1 in [1]), we set the step size $\\eta$ to $O(\\frac{1}{d})$ to ensure convergence.Thus, we choose $b \\sim O(\\frac{1}{d})$. \nAblation studies presented in Fig. 2 (in the main paper) and Fig. 4 (in the appendix) demonstrate that setting $b = 2\\eta$ performs well across different optimization tasks and sample sizes $N$.\n\nAs you noted, the reusable distance bound $b$ plays a critical role in balancing speed and accuracy. A larger $b$ can increase the reuse rate, reduce the number of queries, and accelerate the process. However, it also introduces a larger residual term $o(y-x)$ in the first-order Taylor expansion, leading to an increase in relative error. Therefore, the value of $b$ must be adjusted according to the specific application. From this perspective, an adaptively adjustable reusable distance bound $b$ during the optimization process would be ideal, and we plan to explore this in future work.\n\n[1] Ji, Kaiyi, et al. \"Improved zeroth-order variance reduced algorithms and analysis for nonconvex optimization.\" ICML 2019.\n\n**Q2:** While the method reduces the number of function queries, solving the quadratically constrained linear program (QCLP) may introduce additional computational overhead for large values of $n$.\n\n**A2:** As the sample size $n$ increases, the cost of solving the QCLP also tends to increase. However:\n- On one hand, in zeroth-order optimization, the sample size $n$ is typically small compared to the dimension $d$ and satisfies $n\\ll d$ in high-dimension optimization problems to ensure efficiency (e.g. in black-box adversarial attacks, the variable dimension $d=3072$ while the sample size $n=10$). The performance of ZO methods in such extreme cases where $n\\ll d$ is crucial for assessing their scalability and robustness. Our experiments, detailed in Appendix C.1, demonstrate the effectiveness of our method even under these conditions.\n- On the other hand, Sec. 3.3 introduces a strategy for indexing some intermediate variables that contribute to gradient estimation, significantly reducing the computational complexity of solving the QCLP. We also provide a detailed analysis and comparison of the computation complexity of various ZO methods in Appendix B and Table 4, showing that our ReLIZO method is more computationally efficient than other linear interpolation-based methods. Furthermore, as the sample size $n$ increases, the number of reusable queries also increases with the same step size and reusable distance bound, leading to additional time savings compared to other ZO methods that do not support query reuse.\n\n**Q3:** In Figure 5, the results for the ARGTRIGLS problem indicate a performance drop with any reusable distance bound. What is the specific structure of this problem? Does this suggest that the reuse strategy might be ineffective in certain special cases?\n\n**A3:** ARGTRIGLS is a specialized academic problem designed to evaluate optimization algorithms. It is a variable dimension trigonometric problem in least-squares form, expressed as a sum of $n$ least-squares groups, each containing $n+1$ nonlinear elements. This problem is a variant of Problem 26 in [1], which can be written  as follows: \n\nGiven $f_i:\\mathbb{R}^n\\rightarrow\\mathbb{R}$ \n$$f_i(x) = n-\\sum_{j=1}^n cos(x_j) +i (1-cos(x_i)) - sin(x_i)$$\nand initial point $x^0= (\\frac{1}{n},\\cdots,\\frac{1}{n})$, solve\n$$\\min\\\\\\{ \\sum_{i=1}^n f_i^2(x):x \\in \\mathbb{R}^n\\\\\\}$$\n\nIn Figure 5, we observe a relative performance drop (slightly slower convergence) when the reusable distance bound $b\\geq \\eta$, However, this does not imply that the reuse strategy is ineffective in this case. The ARGTRIGLS problem is characterized by a rugged landscape with numerous local minima. In this case, as shown in Figure 4(b), even with $b=\\eta$ and a sample size $n=8$, the reuse rate of ARGTRIGLS exceeds 90%, whereas reuse rates for other problems are generally below 50% (e.g.  MANCINO with d=100 in Figure 4(a), SROSENBR with d=500 in Figure 2(b)). This high reuse rate indicates that the number of new queries during optimization is relatively small, contributing to the observed decrease in convergence speed.\n\nTo address this issue, we can employ simple strategies such as reducing the reusable distance bound $b$. The table below illustrates that performance improves as $b$ decreases:\n\n|reusable distance bound|$b=0$|$b=0.01\\eta$|$b=0.05\\eta$|$b=0.1\\eta$|$b=0.5\\eta$|$b=\\eta$|\n|-|-|-|-|-|-|-|\n|objective value (iter=500)|0.133|0.162|0.298|0.495|3.768|8.158|\n|objective value (iter=2000)|0.053|0.063|0.166|0.311|1.834|3.825|\n|total reuse rate|0%|16.6%|72.4%|82.3%|94.7%|96.8%|\n\nMoreover, setting an upper bound for the reuse rate in each iteration can also help. The following table reports the performance when the maximum reuse rate in each iteration is restricted to 50%. We observe that with $b\\leq0.05\\eta$ and 2000 iterations, there is minimal performance degradation, even with a reuse rate of approximately 30%:\n|reusable distance bound|$b=0$|$b=0.01\\eta$|$b=0.05\\eta$|$b=0.1\\eta$|$b=0.5\\eta$|$b=\\eta$|\n|-|-|-|-|-|-|-|\n|objective value (iter=500)|0.133|0.164|0.183|0.255|0.312|0.341|\n|objective value (iter=2000)|0.053|0.046|0.054|0.063|0.075|0.074|\n|total reuse rate|0%|11.4%|34.2%|41.9%|47.9%|48.9%|\n\nAs discussed in A1, an adaptively adjustable reusable distance bound $b$ aligned with the optimization process would be advantageous in this context. We plan to explore this approach in future work.", "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": "", "extra_scores": {}}, {"review_id": "F8CI8pjUts", "reviewer": "Reviewer_zPFv", "summary": "From my understanding, this paper give a zero-th order algorithm with application to popular vision tasks neural architecture search and black-box adversarial attacks. The authors derive a closed-form solution after modeling the gradient estimation as a quadratically constrained linear program problem. The key idea is to try to decouple the required sample size from the variable dimension without extra conditions required, making it able to leverage the queries in the prior iterations. The speedup is further technically achieved by directly indexing some of the intermediate variables that contribute to the gradient estimation. The theoretical studies are given for its convergence speed and its cost-effectiveness is verified on benchmarks.", "questions": "I wonder if the proposed method could really facilitate the community of NAS? as zero-order optimization is not common in NAS.", "limitations": "No.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Clear motivation with clearly derived approach, and it is a new zero-th order algorithm indeed and the authors also contextualize well the proposed method with related work discussion.\n2. Strong empirical performance on representative vision tasks with rich testbeds and settings.\n3.  The approach by its design, could enjoy the efficiency of smoothing techniques while maintaining estimation accuracy. Table 4 in the appendix is informative.\n4.  The paper gives comprehensive results and technical details in both main paper and appendix.", "weaknesses": "1. As remarked by the authors, it has few constraints on the sample size, similar to the smoothing techniques; and it requires the estimation of the gradients which involves solving a linear program problem.\n2. As a zero-th order algorithm, it may still not be suited for large-scale application e.g. network training.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful and valuable comments. We hope to address your concerns by answering your questions below.\n\n\n**Q1:** As noted by the authors, the method imposes few constraints on sample size, similar to smoothing techniques, but requires gradient estimation through solving a linear program, which could be a potential limitation.\n\n**A1:** Our approach indeed leverages the strengths of both linear interpolation-based and smoothing-based zeroth-order (ZO) methods, as highlighted in Remark (line 142). By solving a QCLP to estimate gradients, our method achieves higher accuracy compared to smoothing-based methods while maintaining lower computational costs than linear interpolation-based methods.\nSec 3.3 also shows that part of the intermediate variables contributing to the gradient estimation can be directly indexed, significantly reducing the computation complexity of ReLIZO. Further analysis of the total computational complexity is provided in Section B and Table 4 in the appendix. Additionally, since optimization problems are often high-dimensional with a typically small sample size at each iteration (i.e. $n \\ll d$), ReLIZO remains competitive in terms of speed.\n\n**Q2:** As a zeroth-order algorithm, is ReLIZO suitable for large-scale applications, such as network training?\n\n**A2:** Compared to gradient-based methods, ZO methods are well-suited for black-box optimization problems where gradients with respect to the variables are unavailable. Additionally, ZO methods are more memory-efficient than gradient-based methods since they do not require backward propagation, making them applicable to network training, as demonstrated by recent works [1,2]. Specifically, [1] introduces DeepZero, a principled ZO framework for deep learning that is computational-graph-free and can scale to deep neural network training with performance comparable to first-order methods. [2] also applies ZO methods to large language model (LLM) fine-tuning, highlighting their memory efficiency and introducing a ZO-LLM benchmark.\n\nTo illustrate the applicability of ReLIZO in network training, we adopt it for fine-tuning an OPT-1.3b model (with 1.3 billion parameters) on the Stanford Sentiment Treebank v2 (SST2) task, following the methodology of [2]. The results, shown in the table below, indicate that ReLIZO outperforms other ZO methods across various fine-tuning schemes, including full parameter fine-tuning (FT), LoRA, Prefix-tuning, and Prompt-tuning. Notably, ReLIZO even surpasses SGD in the FT scheme while requiring significantly less memory, demonstrating its promising potential.\n\n| Optimizer     | FT       | LoRA     | Prefix-Tuning | Prompt   | FT Memory cost |\n| ------------- | :--------: | :--------: | :-------------: | :--------: | :--------------: |\n| SGD           | 91.1     | 93.6     | 93.1          | 92.8     | 44.1 GB        |\n| ZO-SGD        | 90.8     | 90.1     | 91.4          | 84.4     | 28.7 GB        |\n| ZO-SGD-Sign   | 87.2     | 91.5     | 89.5          | 72.9     | 31.4 GB        |\n| ZO-Adam       | 84.4     | 92.3     | 91.4          | 75.7     | 31.4 GB        |\n| **ReLIZO (ours)** | **93.4** | **93.1** | **91.8**      | **90.1** | 35.7 GB     | \n\n[1] Chen A, Zhang Y, Jia J, et al. DeepZero: Scaling Up Zeroth-Order Optimization for Deep Model Training[C], ICLR 2024.\n\n[2] Zhang Y, Li P, Hong J, et al. Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark[C], ICML 2024.\n\n\n**Q3:** I wonder if the proposed method could really facilitate the community of NAS? As zero-order optimization is not common in NAS.\n\n**A3:**  Recent studies [4,5,6] have explored zeroth-order optimization methods for solving bi-level optimization problems, including NAS task, where gradients of the parameters in the upper-level objective function are typically unavailable. These works highlight the limitations of gradient-based methods for NAS and demonstrate that ZO methods can outperform gradient-based approaches by providing more accurate gradient estimations of architecture parameters in the upper-level objective function. Nevertheless, this work aims to introduce a brand-new zero-order optimization algorithm and we apply it to NAS tasks to evaluate its performance on bi-level optimization problem.\n\n[4] Wang X, Guo W, Su J, et al. Zarts: On zero-order optimization for neural architecture search[J]. NeurIPS, 2022.\n\n[5] Xie L, Huang K, Xu F, et al. ZO-DARTS: Differentiable architecture search with zeroth-order approximation[C]. ICASSP, 2023.\n\n[6] Aghasi A, Ghadimi S. Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing[J]. arXiv preprint arXiv:2404.00158, 2024.", "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": "", "extra_scores": {}}]

Author rebuttal:
## General Responses

Dear Area Chair and Reviewers, 


We sincerely thank you for the time and effort you dedicated to the reviewing process. We are delighted that reviewers acknowledged the novelty of rethinking the gradient estimation in ZO method as a QCLP and our resuing strategy (YYyS, VWEi, zPFv), clear motivation and intuitive derived approach (YYyS, zPFv), extensive experiments (VWEi, zPFv) and that the paper is well-written (YYyS, VWEi, zPFv). To further address the comments and questions posed by reviewers, we have also conducted additional analyses and experiments, including:

- Thanks to the valuable suggestion on sampling new vectors based on known information proposed by reviewer YYyS, we highlight the strength of ReLIZO in sampling new vectors from an arbitrary distribution compared to other ZO methods. We introduce an effective sampling strategy inspired by SGD with momentum, which brings further performance improvement in NAS task.
- As pointed out by reviewer VWEi, the reusable distance bound $b$ is a crucial parameter in the ReLIZO method and can be sensitive to specific problems. To address this issue, we conduct experiments on different reusable distance bounds $b$ and demonstrate that setting an upper bound for the reuse rate in each iteration can significantly reduce performance drops in sensitive cases.
- Regarding the relatively limited impact of ZO methods as concerned by reviewers YYyS and zPFv, we demonstrate that ZO methods are well-suited for black-box optimization problems where gradients with respect to the variables are unavailable. Additionally, ZO methods are more memory-efficient than gradient-based methods since they do not require backward propagation, making them applicable to network training, as evidenced by recent works [1,2]. To illustrate the applicability of ReLIZO in network training, we adopted it for fine-tuning an OPT-1.3b model (with 1.3 billion parameters) on the Stanford Sentiment Treebank v2 (SST2) task, following the methodology of [2]. The results indicate that ReLIZO outperforms other ZO methods across various fine-tuning schemes, including full parameter fine-tuning (FT), LoRA, Prefix-tuning, and Prompt-tuning. Notably, ReLIZO even surpasses SGD in the FT scheme while requiring significantly less memory, demonstrating its promising potential.

For each reviewer, we have posed a rebuttal addressing the concerns, including the specific results of the additional experiments mentioned above. We look forward to your reply and are more than happy to respond to any further comments. Once again, thank you for your valuable comments and support.

&nbsp;

With sincere appreciation and best regards,

The Authors

&nbsp;

[1] Chen A, Zhang Y, Jia J, et al. DeepZero: Scaling Up Zeroth-Order Optimization for Deep Model Training[C], ICLR 2024.

[2] Zhang Y, Li P, Hong J, et al. Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark[C], ICML 2024.

Meta-review: This paper studies how to more efficient and effective estimate the gradient proxy in zeroth order optimization. The proposed approach -- gradient estimation through a quadratically constrained linear program -- utilized all historical information and the derived gradient admits a neat form. Both solid theory and rich empirical studies are included. All concerns have been well addressed in the rebuttal. We recommend to accept this paper.

The authors are required to polish the paper as promised in the rebuttal and is also suggested to discuss how to parallelize the proposed zeroth order optimization algorithm, for example, can it cast into the general parallelization framework?

references:
- A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order
Decision: Accept (poster)