Fast Rank-1 Lattice Targeted Sampling for Black-box Optimization
Authors: Yueming Lyu
Venue: NeurIPS 2023 poster (2023)
Keywords: Black-box Optimization
Derivate-free Optimization
Kernel methods

Abstract: Black-box optimization has gained great attention for its success in recent applications.    However, scaling up to high-dimensional problems with good query efficiency remains challenging. This paper proposes a novel Rank-1 Lattice Targeted Sampling (RLTS) technique to address this issue. Our RLTS benefits from random rank-1 lattice Quasi-Monte Carlo, which enables us to perform fast local exact Gaussian processes (GP)  training and inference with $O(n \log n)$ complexity w.r.t. $n$ batch samples. Furthermore, we developed a fast coordinate searching method with $O(n \log n)$ time complexity for fast targeted sampling. The fast computation enables us to plug our RLTS into the sampling phase of stochastic optimization methods. This improves the query efficiency while  scaling up to higher dimensional problems than Bayesian optimization. Moreover,  to construct rank-1 lattices efficiently, we proposed a closed-form construction.  Extensive experiments on challenging benchmark test functions and black-box prompt fine-tuning for large language models demonstrate the query efficiency of our RLTS technique.

Fast Rank-1 Lattice Targeted Sampling for Black-box Optimization
Yueming LYU
Centre for Frontier AI Research (CFAR)
Institute of High Performance Computing (IHPC) Agency for Science, Technology and Research ST*R)
Fusionopolis Way, #16-16 Connexis, Singapore 138632 Lyu_ Yueming@cfar ata.ana......a.aa............... .et..r.edu.sgg
Abstract
Black-box optimization has gained great attention for its success in recent ap- plications. However, scaling up to nigh-dimensional problems with good query efficiency remains challenging. This paper proposes a novel Rank-1 Lattice Tar- geted Sampling (RLTS) technique to address this issue. Our RLTS benefits from random rank-1 lattice Quasi-Monte Carlo, which enables exact Gaussian processes (GP) training and inference with O(n log complexity w.r.t. n batch samples. Furthermore, we developed a fast coordinate searching method with On log n) time complexity for fast targeted sampling. The fast computation enables to plug our RLTS into the sampling phase of stochastic op- timization methods. This improves the query efficiency while scaling up to higher dimensional problems than Bayesian optimization. Moreover, to construct rank- 1 lattices efficiently, we proposed closed-fone construction. Extensive experiments on challenging benchmark test functions and black-box prompt fine-tuning for large language models demonstrate the query efficiency of our RLTS technique.
perform fast local
Introduction
Black-box optimization has gained great attention for its success in many recent applications, such as
prompt fine-tuning for large language models [Sun et al. 2022b a), policy search for robot control
and reinforcement learning [Choromanski et al. 2019 Lizotte et al., [007]] [arsce et al. 2017
Salimans al., 2017), automatic hyper-parameter
tuning in machine learning problems Snoek
et al., [012]. black-box architecture search in engineering design [Wang and Shan 2007]. drug
discovery (Negoescu et al. 201 and accelerated simulation for scientific discovery [Maddox et al.
202
Hernández-LLoatto et al. (017]. etc. Many efforts have been made for black-box optimization
in the literature, including Bayesian optimization (BO) methods [Srinivas et al. 2010 Gardner et al.
2017
Nayebi al. 2019], stochastic optimization methods like evolution strategies (ES) Back et al.
1991
Hansen 2006 Wierstra et al. 22014b Lyu and Tsang 2021 and genetic algorithms Srinivas
and Patnaik 1994 Mirjalili and Mirjalili 2019].
20199).
Bayesian optimization usually builds a global (GP) model as surrogate and provides queries by optimizing some acquisition functions (Snoek et al. 2012). Although BO achieves good query efficiency for low-dimensional problems, often fails to handle high-dimensional problems with The
large sample budgets [Eriksson et al., 2019]. The computation of GP with large number of samples itself expensive, and the internal optimization the acquisition functions challenging. Recently, Müller al. [2021], Nguyen et al. (2022) builds GP model for both the function value and the gradient and performs local Bayesian optimization. Although these methods improve the scalability of global BO, they usually cannot scale up to five hundred dimensional complex problems. This may
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

be because the learned gradient heavily depends on the accuracy of the GP model. However, achieving an accurate GP model challenging for ditheesnnnii problems. A slightly misspecified GP model may lead to a wrong estimated gradient due to the highly nonlinear acquisition functions.
On the other line, stochastic optimization methods, e.g., ES (Rechenberg and Eigen 1973 Nesterov and Spokoiny 2017]. natural evolution strategies (NES) WWerstra et al. 2014bb, CMAES Hansen 2006]. and implicit natural gradient optimizer (INGO) Lyu and Tsang 202 typically sampling form Gaussian distribution and approximate the (natural) gradient for the update of the Gaussian distribution parameters for continuous optimization. These methods can scale up higher dimensional problems compared with BO. However, the gradient approximation may have large variance, especially for high-diman nigh-dimensional problems. Thus, the update direction may not be toward the descent direction, leading to inferior query efficiency.
To address high-dimensional black-box problems with good query efficiency, we propose novel Rank-1 I Lattice Targeted Sampling (RLTS) technique. Our RLTS has a On log n) time complexity, which is fast for plugging into the sampling phase of stochastic optimization methods. In this way, our methods can improve the query efficiency of stochastic optimization methods while addressing higher-dimensional problems than BO. Our contributions are summarized follows:
We propose novel Rank-1 1 Lattice Targeted Sampling (RLTS) technique. Our RLTS builds local GP with random rank-1 lattice which enables fast exact GP training and inference with On log n) time complexity w.r.t. batch samples. Furthermore, we develop a fast coordinate search that enables target sampling with O(n log n) time complexity.
We propose closed-form subgroup rank- 1 lattice by considering the dual lattice regarding the integral approximation error of functions in Korobov space. Our rank-1 1 lattice has a more regular pattern of approximation error terms. Moreover, our subgroup rank-1 lattice capitalizes on constructing a circulant kernel Gram matrix benefit from its group property. This enables efficient O(n log n) computations in GP training/inference and fast candidate searching. In contrast, low-discrepancy QMC sequences, such as Sobol sequences or Halton sequences, lack these capabilities. In addition, our new closed-form rank- I lattice may have potential applications in downstream tasks beyond black-box optimization.
We plug our RLTS into the sampling phase at each step of stochastic optimization methods to improve query efficiency. In this way, during the optimization procedure, our RLTS sampling from an updated promising region instead of a fixed one at each step. This approach can scale up address tigh-dimensional problems.
Empirically, extensive experiments on high- nigh-dimensional challenging benchmark test func- tions and practical black-box prompt fine-tuning for large language models demonstrate the effectiveness of our RLTS technique.
2 Background
2.1 Black-box Optimization
Given proper function f(x) _d + E such that f(x) -o, black-box optimization is to minimize f(x) by using function queries only. Black-box stochastic optimization methods typically employ sampling distribution p(æ; 0) and optimizes the parameter of the distribution regarding the
relaxed problem: J(Ø)= := | [=))]
Evolution Strategies (ES) [Rechenberg and Eigen 1973 Nesterov and Spokoiny 2017] employ
Gaussian distribution N N(1, I) for sampling. The approximate gradient descent update is given as
B Σ
Ei + tee),
M441 1b
where E; (O, I) and / denotes the siep-size. The ES method performs the approximate first-order gradient descent update. As result, the convergence of ES may be slow. Several second-order gradient descent methods have been proposed to improve convergence. [Wierstra et al. [2014a] proposed the natural evolution strategies (NES), which perform the approximate natural gradient update. When Gaussian distribution.N (H, Σ) employed for sampling. The update rule of NES is

---

given in Eq. 2 and Eq.
E1+1 Ex 8 Σ
f(u, E) [ - ).)
(2)
i=1
M141 = M4 fm: + Σ c
8
(3)
where 6, ~ (O, 1) and Σ > and Σ Σ = The NES takes advantage of second-order gradient information, which improves the convergence of ES.
Lyu and Tsang [221] proposed an implicit natural gradient optimizer (INGO) for black-box opti- mization, which provides an alternative way to compute the natural gradient update. The update rule of INGO is given as in Eq. and (5.
(ax)) P (E,
E11 = Et
(x:
(2) -Hi) -1) ",,"""
(4)
nō
f(x)) (x. u.).
M1+1 = 14 1
(5)
no
where a, (H Ex), f
Ei and ō denotes the standard deviation of f(x)). The
normalization [(m)) employed to reduce the variance.
CMAES [Hansen] 2006) provides more sophisticated update rule and performs well on wide range of black-box optimization problems. All the above stochastic optimization methods rely on sampling. Thus, the sampling phase is vitally important. And a better sampling technique is promising to achieve further improvement.
2.2 Rank-1 Lattice
A rank-1 lattice is a particular case of the general lattice with simple operation for point-set construction. can used as Quasi-Monte Carlo for integral approximation [Sloan] 2000 Dick
et al. 2013]. A rank-1 lattice point set P {m) [nn) can be constructed as Hq. 66
iz mod
x
E [1....,n].
(6)
n
where 2 E 2d the so-called generating vector, and mod denotes the modulo operation.
Korobov 1960
proposes a rank-1 lattice with the generating vector having a particular form as Eq.
= [1, k, ... , bd-1j
mod n,
where k is searching over (1..... } to reduce approximation error.
searching method for the generating vector without assuming the Korobov form in Eq. (7). Recently, Lyu et al. [2020) proposed a simple closed-form subgroup-base based rank- lattice by considering the Toroidal distance the primal lattice space. The generating vector is given as Eq. 8
Sloan and Reztsov 2002 further proposed
cempoonent-by-oompone
2(n-1)
12(m-1
z = [g 9 9
:9
mod n,
where denotes the primitive root modulo the prime number n. More details of the lattice rules for numerical integration can be found the book DDick et al.) [2022).
In this paper, we proposed a closed-form subgroup rank-1 lattice by ensuring the approximation error
terms of the dual lattice have more regular pattern. In contrast, Lyu al. 2020 construct the rank-1 lattice evenly spaced in the primal lattice space.
Fast Rank-1 Lattice Targeted Sampling
3.1 Random Rank-1 Lattice Quasi-Monte Carlo Gaussian Sampling
We first show how to construct random rank-1 lattice Quasi-Monte Carlo Gassuain samples. These samples enable us to perform the black-box stochastic optimization listed in section 2.1 More importantly, the nice property of the structure of these samples facilitates a fast targeted sampling.

---

-2
(a) Our Closed-form Rank-I Lattice Sampling
(b) i.i.d Gaussian Sampling
2-
0-
(c) Our Closed-form Rank- Lattice Sampling
(d) i.i.d. Gaussian Sampling
Figure I: Illustration the our closed-form Rank-1 Lattice sampling and i.i.d. Gaussian sampling.
Given a rank-1 lattice point set P = { ". ,,,) we first construct a random shifted rank-1
lattice DDick al. 2013 Eq. 19)
T; v. mod! 1 Vi (1, (1,...,m) m).
where A Uni Prniform(0, (0, 1jd, and the mod operation denotes a modulo operation that takes the non-negative fractional part of the input number element-wise Then, we can construct random QMC Gaussian samples Eq. (10)
- (x,) Vi E [1, [1,-.-,m1,
(10)
where & -- '(-) computes the inverse cumulative density function of the standard Gaussian distribution the input element-wise. Then, the samples for Gaussian N(a, Σ) can be constructed follows:
E, = l + E
(11)
An illustration of the random QMC Gaussian samples constructed by our closed-form rank-1 lattice is shown in Figure [ We can that rank-1 lattice QMC Gassuan samples are spaced more evenly w.r.t the density.
3.2 Fast Exact GP Training and Inference with Rank-1 Lattice
This subsection will show how to perform fast exact GP training and inference using our rank- 1 lattice samples with (n logn) time complexity w.r.t n samples.
Let K2 denotes the kernel Gram matrix, i.e., K = [ho(a;; my )issss the marginal log-likelihood of GP model [Williams and Rasmussen 2006 can be formulated as Eq. (12)
L(p(y|X)) z (Ko + 2 2 log( K + 0²1) log 2n.
n
(12)
2

---

The standard GP model needs Onn²) time complexity to compute the marginal log-likelihood which is prohibitive for fast training as an inner step for stochastic optimization.
In this paper, we construct the random QMC samples based on rank-1 lattice, which enables us to perform fast GP training. Specifically, build the GP model with the rank-1 lattice the training data instead of the Gaussian samples. Define modulo kernel as Eq. (13
k xz) == Ka (Ø(z; xz)), where ka (.) is a shift-invariant kernel, and the function s(a;; æz)) is given as Eq. (14p
(13)
(xx; zz) min ((z: æz) mod 1, 1, (æ; xz)) mod 1),
(14)
where operation min(.:-) outputs the minimum among its two inputs element-wise and mod 1 output the positive fractional parts of its inputs element-wise. The nonnegative fractional part of a real number x is [ where [-] denotes the floor function.
For GP model with modulo kernel defined in Eq. [3),, the kernel Gram matrix a circulant matrix thanks to the properties of rank-1 lattice. To be concrete, for rank-1 lattice data, we have Eq. (15)
(i (i=
j) mod
j)= mod "))
(a;; 2,) = ( 2, k&
min
(15)
n
n
Then the marginal log-likelihood [(p(y) can be computed with a On log n) time complexity by Fast Fourier Transform (FFT).
Specifically, note that the kernel Gram matrix Ka + o² I is symmetric circulant matrix generated by vector & [ where Ka is a vector with its 7th element given as Eq. (16
kss = ka min 1)x mod n
(i 1)x mod n
(16)
72
72
We know that Kg + o2I can be diagonalized as K + o = 1. F where the j row and tth column element of F' is Fjk can be computed as = diag( Fka). The matrix-vector product FKA can be computed via FFT with On log n) time complexity. And matrix-vecte product F for vector can be computed via inverse FFT. More details about the properties of circulant matrices and fast computation via FFT can be found in (Gray al.) 2006).
2mjki/n, And the matrix A is the diagonal eigenvalue matrix that
Then, we achieve the fast computation of the terms in log-likelihood Eq. 17 and Eq. (8):
y (Kg + + yy (ifft(ftly))/ff (ff((k))))(()))
(17)
log( Kg + +011 Σ (A, + +²2 = 1 log (fft(ka)),
(18)
where ifft(-), fft(-) denotes the inverse FFT and FFT operation, respectively, the operator / in Eq. Eq.(17
performs divide element-wise. And the log(-) is an element-wise operation. And A; in Eq. 18 denotes the eigenvalue of kernel Gram matrix K
For inference, GP model has dlosed-form posterior mean and variance [Williams and Rasmussen 2006 given as Eq. (9) and Eq.200
m)xx) = ko (Ko + o
(19)
(x) (:) ka x) ko(x)) (Ko + -ko)).)
(20)
where (x(x) = (x,, x ..., ( xr,)]]
With rank-1 1 lattice input data, we can perform fast inference by Eq. 21 and Eq (22
((x) = Ka (x) ifft (fftt(ff()))) (ft)((()))(((())))))))))))))))))
(21)
x: Ks (x: x) (x) iift (ffff((((()))))((k)))))
(22)
Both the exact GP training and inference benefit from the structure of rank-1 lattice and FFT acceleration, which can be performed with O( log n) time complexity. deep learning toolbox, e.g., Pytorch, can be used to train the parameters of the kernel.
5

---

Algorithm Fast Coordinate Search
Input: Number of iterations T, weight vector w, and generating vector z -- za] for
rank-1 lattice X.
Initialization: Initialize x" by uniformly sampling from grids {0, n n 5 for t= 1:T do
for q= 1:d do
Compute e² = if (0)) o m(k o w)) by 27.
Get the index i of the minimum elements in c², and set z 8" 2y mod
end for end for Return: x
"
3.3 Fast Coordinate Search for Targeted Sampling
This subsection shows how to perform fast coordinate search for targeted sampling. A rank-1 lattice with n points is contained grid {0, //- ..... ==1]d, We thus perform a coordinate descent search from the index set {0, 1, ... , to minimize the GP posterior mean in Eq. 19
Let k(,,)) = (-) be a shift-invarian kernel with decomposition structure as Eq. 23
k(x;, x²) = ka (ø(x" =)) = 11 -2 ka (o(x; - =xg));
(23)
where zi.. By denotes the 4th element x², æ, respectively. We can perform coordinate search by fixing all the components except the 9th one as the current working component for index searching. Formally, let (Ke + o² y. Then, we have the GP posterior mean function given Eq. (4):
m(x") K% (a (k's C w))
(24)
where @ denotes the element- product, and &% (ar))) denotes vector with 7th element given as ki;= ka ( xg:)), and X qi denotes the element in -tw and :th-column of the rank-1
lattice matrix X [x1," mn). The vector KA denotes the remainder vector with its 8th elemmnt given as Eq.
RA ka(d(1 - X xx))) Ti
xx)))
(25)
To optimize the 9th component o. of x", we fix the other components of xx and the corresponding vector K3. We find 2 by solving the subproblem given in Eq. (26
arg min E (0, 1-
6A (x)
kK' @ ww)
(26)
Directly enumerate computation of the problem 26 needs O(n²) time complexity. In our paper, we can perform a fast computation with (n log n time complexity thanks to the rank- lattice X. Specially, when X is rank-1 1 lattice with the generating vector z [Z,,-.. =a]. then the (m-1)2, mod n forms a circulant matrix, and the
matrix K [k* (0), k21 Lag mod n ...... k%
problem 26 can be accelerated via FFT by Eq.
27
== K
(k3 w) iff((f((k) (0)) o fitk'ss @ w)).
(27)
where fft(-) and ifft(.) denote the FFT and inverse FFT operation. Then, we can achieve 2 by the index it of the minimum element vector e KTT (R's & w)) and set or
mod
We present the algorithm of the fast coordinate search in Algorithm [ The Algorithm return a targeted sample with a small prediction value in fast manner. We can use the targeted sample to accelerate the stochastic optimization. Finally, we present our overall stochastic optimization backbone algorithm because of its simple implementation and fewer hyperparameters. One can plug our RLTS into other stochastic optimization methods to improve query efficiency.
algorithm in the Algorithm 2 We choose INGO (Lyu and Tsang 2021)
'The first element of KA is set k: (0) 2

---

Algorithm 2 Rank-1 Lattice Targeted Sampling
Input:
Number of batch samples n,, step-size and 1/s number of internal iterations T for Fast Coordinate Search, and initial variance o². Initialize M4 0 and Σg = Iº
Initialization:
while Termination condition not satisfied do
Sample a shift vector A uniformly from [0, 1]
Construct shifted rank-1 lattice X = - ... 2nn by Eq. 9 Construct QMC Gaussian Samples E1. En by Eq
Set E, p4 Σ e, for i (1,...n).
Query the batch observations (.f(,)).... f(Em))
Compute Ō std(f(()).. ....... f(. (E,))
Compute ÿ0 = ((.
_G) for i [I....n). Set y,
Perform fast exact GP training with rank-1 lattice X and y by Eq. 17 and Eq. (18)
Get targeted grid sample x' by Algorithm with T steps.
Get targeted Gaussian sample 5 -- + mod 1)
Query the observation ((
0 - y: E, 1 c, T x
Σ Set M4+1 H, 1
Set 1+1
if f(E") minke (1, m) f(E,) then
Set M = (1 11 141 + + end if end while
3.4 Closed-form Rank-1 Lattice Construction
This subsection will show how to construct our closed-form rank- lattice for fast sampling. For Var, y E [0, 1]d and a >> define reproducing kernel as Eq. (88
K(x, v) Σ KEZ4
%a exp
exp (2rik
(x v)).
(28)
where 12 -1 and %a (k) I1 Va (ke)) with Yar (k) given as follows:
{1 [|k]
if = 0 if A: + O.
Toa (k)
(29)
Korobov space is reproducing kernel Hilbert space (RKHS) associated with the kernel in Eq. denoted as He.
28
Our closed form of the generating vector is given as Eq
30
= [ g 2(m-1)
(4
mod n.
(30)
where g denotes the primitive root modulo the prime number n, and (2d 1)((n - 1). Then, our close-form rank-1 lattice can be achieved by Eq. 6
Given point set P (01,-.. ;n), the square worst case integral approximation error for f e H is defined as Eq. 31:
1 カ-1
PHH:P)
sup Il, S1
L (0.1j
f(x) )a
f (a,)
(31)
j=0
We further show that our rank- lattice constructed by Eq. 30 has a regular worst-case error pattern Theorem [ The proof is given in the Appendix.
Theorem 1. Let n. be prime number such that (2d - 1))(n 1). Suppose the integrand function
E H+. Il HL. constructed by Eq. 30) is given as Eq. 32
the square worst-case integral approximation error of rank-1 lattice P
(HH::) = 3,1 (he @ .... 26-2 2
(h o .... G R d- - 1 ..... @ (d-1) -1)) + +. C(a, 1).
(32)

---

OAMSS
OME
1108
2008
100
10h0n 1901E
2H0RE
750
10.03
71066
28000
20003
50000
8000
T50:0
10/8
1093
2500
3000
(a) Roscabrock-din-50
(b) Rastrigia10-dim-500
(c) Nesterov-din-30
4000 S000 T5D0S 280000 20000 10000
5000 79:00 TUMEE T0000 20006 X0000
100
-a000 19080
203006 250000 140300
(d) Rosenbrock-din-500
(e) Rastrigin10-din-500
(f) Nesterov-din-500
Figure 2: Cumulative min objective value v.s. the number of query evaluations on 50-dimensional
and 500-dimensional benchmark test functions.
where denotes the element-wise product, symbol denotes the vector with elements all ones, and h' F'ry with F the discrete Fourier matrix, i.e., Fj exp(2xi ik and F denotes the matrix after permutation of the rows of F such that the jth row of F equals to the jth row of F. where j ig sim-11
mod n. And 7- = h:,.... ".....,,a :Ya]T with *tk = na (S(a, k. +)+++ ((a, =-k: )) for 2 no <(a, 1), where ((,-)) denotes the Hurwitz zeta function.
E {1,... .. n 1} and inn = 1+
oh Remarks: The term H h oh 2d-2 2
(h o.. oh...-h---i 1do-
ch hh (d 11
has regular pattern because of (g), g0 a=t ,
2(n-1)
(ad 2d-2)(n-1)
mod forms a subgroup of ... n - 1} mod n. According to the Lagrange's theorem in group
2u
2d
9 22
theory [ummmit and Foote 2004 the vector h .... @ 2d-2 has 2d
a-1 different elements.
4 Experiments
We replace the i.i.d. Gaussian sampling of the INGO [yu and Tsang. 2021 with RLTS. We evaluate our RLTS by comparing it with the standard INGO and the CMAES [Hansen 2006]. In all the experiments. we keep the number of batch samples and the initialization the same for RLTS, INGO and CMAES. For all the methods, we initialize the O. For INGO and RLTS, we set the step-size parameter 3 0.2 in all experiments. For RLTS, set the parameter 1 in all experiments.
4.1 Evaluation on Benchmark Functions
We first evaluate our RLTS on challenging benchmark test functions: Rosenbrock, Rastrigin, and Nesterov. Rastrigin and Rosenbrock are smooth multi-mode functions, and Nesterov is non-smooth function. These functions are very challenging benchmarks for black-box optimization. We offset the optimum by setting æ x of the functions. This increases the distance between the optimum and the initial point = O, which makes the test problems more challenging. We implement INGO by ourselves. For CMAES, we use the publicly available code We initialized Σ for all the methods.
Phtpss/pyypi.or//poojetttmm/

---

CAMSS
20.00
1200
0
2010
40000
60300
352
J083
20000
Humber
(a) DBpodia
(b) SS2
(c) SNLI
4.0
24
1.5
130
1.
04
032
2004
LAGES
8000
30000
4000
KBM
28583
1000
(d) News
(e) MRPC
(I) RTE
Figure 3: Hinge loss v.s. the number of query evaluations on different black-box fine-tuning models.
We evaluate RLTS on 50 and 500-dimensional problems. The batchsize of all the methods
set to 200 and 2000 for 50 and 500-dimensional problems, respectively. All the experiments are performed in ten independent runs. The experimental results are shown in Figure 2 From Figure 2 we can observe that RLTTS consistently converge faster than INGO on all the test functions on both 50-dimensional and 500-dimensional cases. It shows that our RLTS significantly improves the query efficiency of INGO, which verifies the effectiveness of RLTS. Moreover, we can see that RLTS outperforms CMAES on all the test functions on both 50-dimensional and 500-dimensional cases. In addition, we see that CMAES converge slowly on the 500-dimensional benchmark problems, while RLTS converges faster.
4.2 Evaluation on Black-box Prompt Fine-tuning Tasks
Prompt fine-tuning of large language models is a promising direction to achieve expertise models efficiently for downstream tasks. We evaluate our RLTS on black-box prompt fine-tuning tasks.
We employ the deep model in [Sun et al. 2022a with publicly available code as the backbonn model for black-box prompt fine-tuning. It has 24 layers. For each layer, we set the dimension of the continuous prompt to 500. Thus, the total dimension is 24 x 500. We employ the hinge loss of training data the black-box objective. Six benchmark datasets for different language tasks employed for evaluation: DBpedia, SS2, SNLI, AG's News, MRPC and RTE. The SST2 [Socher et al. 2013) dataset is dataset for the sentiment analysis task. AG's News and DBPedia datasets [Zhang et al. 2015) are used for topic classification tasks. SNLI [Bowman et al.) 2015) and RTE [Wang el al. 2019 are employed for natural language inference. MRPC dataset Dooan and Brockett 2005 is used for the paraphrasing task.
In all the experiments, keep the number of batch samples and the initialization the same for RLTS, INGO and CMAES. We set the number of batch samples to 2000. Specifically, our RLTS employs 1999 rank-1 lattice QMC Gaussian samples and one sample from targeted sampling. INGO employs 1999 rank-1 lattice QMC Gaussian samples and one Gaussian sample. CMAES employs 2000 Gaussian samples. We initialize the μ = 0 and Σ 0.21 for all the methods. For INGO and RLTS, we set the step-size parameter 3 = 0.2 in all experiments. For RLTS, we set the parameter ? 1 in all experiments. All the experiments are performed in five independent runs with seeds in {1. 2,3,, 4, 5). The layer-wise coordinate descent update approach in [Sun et al. 2022a is employed for all the methods.
Panps://gituubcco//uuusm// 1wtp://///////mm1/9//////// Box- Tuning

---

220002
700003
13500
10005
10003
6.
1003
20,00
500n
1285
2000
5000 160.5
(a) Rosenbrock-din-500
(b) Rastrigin10-dim--00
(c) Nestcro--dim-500
Figure 4: Cumulative min objective value v.s. the number of query evaluations on 500-dimensional benchmark test functions.
The experimental results of mean objective std v.s. the number of queries are shown in Figure From Figure we can observe that our RLTS decreases the objective significantly faster than INGO and CMAES on all six fine-tuning tasks, which shows the superior query efficiency of our RLTS.
4.3 Additional Comparison with High-dimensional Bayesian Optimization
We further compare our RLTS with the high-dimensional BO method TuRBO [Eriksson et al. 2019 We evaluate RLTS on the three benchmark functions: the Rosenbrock function, the Rastrigin function, and the Nesterov function. We offset the optimum by setting x = a 5 of the test functions. 2000. The batch size of
The dimension is set 500. The number of initial points of TuRBO is both RLTS and TuRBO is set to 2000. The maximum number of queries is set to 50,000. We employ the default box boundary for TuRBO, i.e., 5, 10 The initial parameter μa of RLTS is set to μ and Σ is set to Σ = I. For TuRBO, we employ the official code provided in the paper [Eriksson al. 2019]. All the methods are performed in three independent runs.
The convergence performance regarding the number of query evaluations is shown in Figure We observe that RLTS converges faster than TuRBO the benchmark test problems, demonstrating that RLTS improves query efficiency.
We further report the running time of RLTS and TuRBO the same machine for evaluation. The results are shown in Table T achieving around 300 times speedup regarding running time. The computation time of Bayesian Optimization usually grows cubically fast as the number of queries increases. In contrast, our RLTS reduces the expensive (n²)) operation to O(n logn) n) time complexity, which enables a fast plug-in of the ES-type algorithms.
We can observe that RLTS performs significantly faster than TuRBO,
Table Running time on benchmark test functions. Symbol (s) denotes seconds.
Rosenbrock
Rastrigin10
Nesterov
RLTS
83.62(s)
84.04(s)
83.46(s)
TuRBO
25927.39($)
25941. (694).6((s)
25697.87($)
5 Conclusion
We proposed novel Rank-1 Lattice Targeted Sampling technique in this paper. Our RLTS has log time complexity w.r.t. batch samples, which fast for plugging into stochastic optimization methods to improve query efficiency while scaling to high--dimessional problems. Empirically, we plugged our RLTS into the sampling phase of INGO, significantly improving the query efficiency on benchmark test functions and black-box prompt fine-tuning tasks. Moreover, we proposed a closed-form rank-1 1 lattice by analyzing the integral approximation error of functions in Korobov space. Our closed-for ffom rank- I lattice provides an efficient way for QMC Gaussian sampling, with properties enabling fast exact GP training and inference with a O(n log time complexity, which is critical for our RLTS to be a fast internal step for stochastic optimization. In addition, our closed-form rank-1 lattice is a fundamental tool that may have potential applications beyond the black-box optimization task.
10

---

Acknowledgement
We thank the anonymous reviewers for their valuable comments and helpful suggestions.
References
Thomas Back, Frank Hoffmeister, and Hans-Paul Schwefel. survey evolution strategies. In Proceedings of the fourth international conference on genetic algorithms, volume 2. Morgan Kaufmann Publishers San Mateo, CA, 1991.
Juan Cruz Barsce, Jorge A Palombarini, and Ernesto C Martínez. Towards autonomous reinforcement learning: Automatic setting of hyper-parameters using bayesian optimization. Computer Conference (CLEI), 2017 XLIII Latin American, pages 1-9. IEEE, 2017.
Samuel R Bowman, Gabor Angeli, Christopher Potts, and Christopher D Manning. A large annotated corpus for learning natural language inference. Proceedings of the 2015 conference empirical methods natural language processing, 2015.
Krzysztof Choromanski, Aldo Pacchiano, Jack Parker-Holder and Yunhao Tang. From complexity to simplicity: Adaptive es-active subspaces for blackbox optimization. arXiv: 04268, 2019.
Josef Dick, Frances Y Kuo, and Ian H Sloan. High-dimensional integration: the quasi-monte carlo way. Acta Numerica, 22:133-288 388, 2013.
Josef Dick, Peter Kritzer, and Friedrich Pillichshammer. Lattice Rules. Springer, 2022.
Bill Dolan and Chris Brockett. Automatically constructing corpus of sentential paraphrases. In Third International Workshop on Paraphrasing (IWP2005), 2005.
David Steven Dummit and Richard M Foote. Abstract algebra, volume 3. Wiley Hoboken, 2004.
David Eriksson, Michael Pearce, Jacob Gardner, Ryan Turner, and Matthias Poloczek. Scalable global optimization via local bayesian optimization. Advances in neural information processing systems, 32, 2019.
Jacob Gardner, Chuan Guo, Kilian Weinberger, Roman Garnett, and Roger Grosse. Discovering and exploiting additive structure for bayesian optimization. In Artificial Intelligence and Statistics, pages 1311-1319, PMLR, 2017.
Robert M Gray al. Toeplitz and circulant matrices: A review. Foundations and Trends@ in Communications and Information Theory, 2(3):155-2399 2006.
Nikolaus Hansen. The ema evolution strategy: a comparing review. In Towards new evolutionary computation, pages 75-102. Springer, 2006.
José Miguel Hernández-LLoato James Requeima, Edward O Pyzer-Knapp. and Alán Aspuru-Guzik. Parallel and distributed thompson sampling for large-scale accelerated exploration of chemical space. In International conference on machine learning, pages 1470-1479. PMLR, 2017.
Nikolai Mikhailovich Korobov. Properties and calculation of optimal coefficients. In Doklady Akademii Nauk, volume 132, pages 1002-1012, Russian Academy of Sciences, 1960.
Daniel J Lizotte, Tao Wang, Michael H Bowling, and Dale Schuurmans. Automatic gait optimization with gaussian process regression. In IJCAI, volume 7, pages 9444949, 2007.
Yueming Lyu and Ivor W Tsang. Black-box optimizer with stochastic implicit natural gradient. In Machine Learning and Knowledge Discovery in Databases. Research Track: European Conference, ECML PKDD 2021, Bilbao, Spain, September 13-17, 2021, Proceedings. Part III 21, pages 217-232. Springer, 2021.
Yueming Lyu, Yuan Yuan, and Ivor Tsang. Subgroup-based rank-1 lattice quasi-monte carlo. Ad- vances in Neural Information Processing Systems, 33:6269-6223 -2880, 2020.

---

Wesley Maddox, Qing Feng, and Max Balandat. Optimizing high-dimensional physics simulations via composite bayesian optimization. arXiv preprint arXiv:2111.14911, 2021.
Seyedali Mirjalili and Seyedali Mirjalili. Genetic algorithm. Evolationary Algorithms and Neural Networks: Theory and Applications, pages 43-55, 2019.
Sarah Müller, Alexander Rohr, and Sebastian Trimpe. Local policy search with bayesian optimization. Advances in Neural Information Processing Systems, 34:20708-20722 2021.
Amin Nayebi, Alexander Munteanu, and Matthias Poloczek. A framework for bayesian optimization in embedded subspaces. In International Conference on Machine Learning, pages 4752-4761. PMLR, 2019.
Diana M Negoescu, Peter Frazier, and Warren B Powell. The knowledge-gradient algorithm for sequencing experiments in drug discovery. INFORMS Journal Computing, 23(3)3446-333, 2011.
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):227-566, 2017.
Quan Nguyen, Kaiwen Wu, Jacob Gardner, and Roman Garnett. Local bayesian optimization via maximizing probability of descent. Advances in neural information processing systems, 35: 13190-13202, 13202, 2022.
Ingo Rechenberg and M. Eigen. Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. PhD thesis, 1973.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies scalable alternative to reinforcement learning. arXiv preprint arXiv:1703.03864, 2017.
I Sloan and A Reztsov. Computation, 71(237):263 273, 2002.
construction of good lattice rules. Mathematics of
Ian Sloan. Multiple integration is intractable but not hopeless. The ANZIAM Journal, 42(1):3-8, 2000.
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. In NewrlPS, pages 2951-2959, 2012.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Ng, and Christopher Potts. Recursive deep models for semantic compositionality over sentiment treebank. In Pruceedings of the 2013 conference on empirical methods in natural language processing, pages 1631-1642, 2013.
Mandavilli Srinivas and Lalit Patnaik. Genetic algorithms: A survey, computer, 27(6):17-26. 1994.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In ICML, 2010.
Tianxiang Sun, Zhengfu He, Hong Qian, Yunhua Zhou, Xuanjing Huang, and Xipeng Qiu. Bbtv2: Towards a gradient-free future with large language models. In Proceedings of EMNLP, 2022a.
Tianxiang Sun, Yunfan Shao, Hong Qian, Xuanjing Huang, and Xipeng Qiu. Black-box tuning for la seeeiiice.. In Proceedings of ICML, 2022b.
Alex Wang. Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman, Glue: A multi-task benchmark and analysis platform for natural language understanding. In 7th International Conference Learning Representations, ICLR, 2019.
Gary Wang and Songqing Shan. Review of metamodeling techniques in support of engineering design optimization. Journal of Mechanical design, 17904)3370-380 2007.
12

---

Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jürgen Schmidhuber. Natural evolution strategies. The Journal of Machine Learning Research (JMLR), 15(1):949-981) 2014a.
Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jürgen Schmidhuber. Natural evolution strategies. The Journal of Machine Learning Research, 15(1):949-98) 9800 2014b.
Christopher KI Williams and Carl Edward Rasmussen. Gaussian processes for machine learning. volume 2. MIT press Cambridge, MA, 2006.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. Advances in neural information processing systems, 28, 2015.
13

---

Appendix
A Proof of Theorem 1
Theorem 1. Let n. be a prime number such that (2 (1lnn-1). 1). Suppose the integrand function
E Hk. ll I 1. the square worst-case integral approximation error of rank-1 lattice dP constructed by Eq. (g. is given as Eq.333v 33:
(HH,;:) = 1 ....o.
(h' o d- 1) 2 1 (d-1) 1)) + Cla, 1),
(33)
where @ denotes the element-wise product, symbol 1 denotes the vector with elements all ones, and h' = F with F as the discrete Fourier matrix, i.e., F = exp(2ri and F' denotes the matrix after permutation of the rows of F such that the jth row of F equals to the 3th row of F, where j = ig 1i 1 E (1....
20-1 mod n. And 7 = [T,,--' mm] with T - - (S(a,, +) +((a, m=h)) )) for }} and in = 1 ((ar 1), where ((;-)) denotes the Hurwitz zeta function.
To prove our main Theorem 1, we begin with several Lemma. Lemma 1, For Va. y E [0, 1]4 and a > 1, define reproducing kernel as Eq.
K(x, y) E
exp (2Tik (xc v)) 7a (k) exp
(34)
kE2d
where (k) = II Ya (kz) with Ya (k) given in Eq.
[1 =
(a
{ ik--a ikk
(35)
Let [x1, Ix.] be rank-1 lattice constructed by the generating vector with prime number n. Then, for vf E H4, llf S 1 associated with the reproducing kernel (q. we have the square worst-case integral approximation error of Eq.
2
Joap f(x)dx
sup JeHu, If Ifll (Hz;P)
EE
Σ REL-MO0
(a(k)
(36)
where I denote the dual lattice defined in
37 37
L+ == =k|k z 0 (mod n),, k E 2d).
(37)
Proof. Given a point set P far1,". Fn), the worst approximation for Vf Hv. [ll < is
fEH. $1 Maar f(æ)dx 1
(HHp:))
sup
Σ f
(zz))
(38)
1=0
2
(5 (5 K(x, 1 n-1
sup JeHe.llfll,
Σ
K (2)
(39)
n ==0
n-1
sup JeHe.ll/llee
11fllme Voare K(x, .d
Σ
K (Izz.
(40)
n
Ht.
1=0
= -Ja Joir K(x, yddxdy Σ
K K(x, xF
+
K (xx x.))
10.1e
nz
j=1
i-j=1
(41)
14

---

Then, from the definition of the reproducing kernel K (æ. y) in Eq. 34), we know that
Jone SOAP (xx, yddrdy-
1oo.1u /
Ta (k) exp 22ik T (æ y) drdy
(42)
[0.1)4 KEZd
= = Σ
Ta (k:)
1 S exp 2 (or (x--))
v) dxdy
kE24 k40
(43)
=1+ (k)) 0=1
(44)
kEZ k
In addition, the second term Eq. as follows
2
K(x, F. dd
(45)
[0.1]
j=1
2
(a(k) exp
(2rik T (x x3)) dæ
(46)
[0,1j
keza
2
(0)
2
Σ
Ta To(k))
/ 10.11
exp 2 (x xz))) do
(47)
11
j=1
j=1
kE2 1
2
(0)
2
Σ
Σ
Ya (k)
(48)
11 1=1
n 1=
kE? 1eyl0
(49)
Moreover, from the definition of rank-1 1 lattice p with prime and generating vector z, we have the third term in Eq.44] as follows
K (x),
(50)
n
1
To exp 22ri T (a: (x;))
(51)
n²
f,1=
kEZ4
n
2 j)lk 2
Σ
Ta (k))epp exp
(52)
11
i-=1
KEZd 1E0
2mi(i -j)k'
=1 Σ
Ta
exp
(53)
112
n
kE24 1off
1,f=1
1+ Σ
Ya (k)
exp
2mijk
z
(54)
n
kE24 Oof
j=1
Put Eq.444.
(4
Eq.
49 and Eq.
together, we know that
1
2nijkT
(He; P)
Σ Ya (k)
Σ
exp
(55)
n
1=1
Note that for prime number n, we have
2wijk
[1
if T =====0 mod n
exp
n
0
otherwise
(56)
follows that
e (Hz;
sup seme.llflxx 51
Moape f(z)dx
Σ (x))
Σ
7a(k),
(57)
1=0
KEL ROL
15

---

where L = [k|k' 2 0 (mod n)) k E 3d} denotes the dual lattice.
Lemma 2. Given a prime n, construct a rank-1 lattice P = = Lnd by the generating vector
(2 zal, then we have that
n- EII E
exp 2 2
Kujzz
e²
exp
(58)
i= [E((I,..)
where function x(+) on domain
{1,-.. n given 59.
x(k:) + no ((a,1) 1)
ifk= =1 otherwise
(59)
no (S(a, (n) + c(a, ==
where ((--)) denotes the Hurwitz zeta function.
Proof. From Lemma 1 know that
2Ti h æij
(HH;:)) = Σ (k)
exp
(60)
kEZ
1=0
2mi k x
=
Yal (k)pp
(61)
1=0 kEZd
2 kujzi
Ta(ki) exp
(62)
KE
kujzi
E
Σ
(a())) exp
2mi
(63)
== kE(l.m))
qisk, mod
Now, we check the term Ekeet m) (En med a Va (qi)). From the definition of the function (.).), for vk, E [I,...,,,) we have that
+ 2 2 m= (mn)a
if otherwise
x(k:) Σ (a))))
(64)
Em=o (K, 14-may mnja Em=0 (n=ke
4 mod
Note that series Em
(mn)a Em=
(kutmnjo and Em= (n-kstmxjo can be rewritten as
m n ((a,
(65)
(mn)ar
n2
m=1
1
1
h n
na C(a,
(66)
(ks + mn)
n
l
+ m)m
((a, ki
Σ
(67)
k; mn)a
n- + +m)n
n
m==
m=0
where <(,) :) denotes the Hurwitz zeta function.
Plug them into 14.1 we know that
( 11
2 (a, 1) no
if = otherwise
x(k:)=
(a()))
(68)
na (S(a, R ) <(a, *=k))
kk mod
Plug Eq. 68 into Eq. 63 we have that
EII Σ exk 2 Kijzs
(Hi; -
(69)
== i1 m)
16

---

Lemma 3. Let n be a prime number. Let m Pul be vector with " k E {1.-.. n where X(-) is defined in Lemma 2 error of rank-1 lattice P constructed by generaling vector 2 [.,... " zd] can be rewritten in matrix form as Eq.770)
x(k) for
The square worst-case integral approximation
-1 1 O 1 -1)
e (Hui P
(70)
where 2 denotes the element-wiss product, symbol denotes the vector with elements all ones, and h' F"rry with F as the discrete Fourier matrix, i.e., jk exp(2ri ), and F' denotes the matrix
after permutation of the rows of F such that the jth row of F equals to the jth row of F, where
j = j7441 mod n.
Proof. Define h' as Eq. 71
h' Flyy
(71)
where F as the discrete Fourier matrix, i.e., Fjx= exp(2ni w. and F' denotes the matrix after permutation of the rows of such that the jth row of F equals to the jth row of F, where j j mod n, and g denotes the primitive root modulo n.
From Lemma 2 we know that
= = -1 -
ΣII Σ
x(ki) 2
(2mi Ridkz
(72)
== =1
Note that 7 [7,, ... ["]] is vector with 7 x1k) for k E f1,... nn), it follows that
(Hz;P) = +1 -1
po .... F
(73)
= =-1 + -1 1
0 .... 0... h
(74)
T
hh" o.... hd_1_
(75)
Lemma 4. Let be prime number such that (2d 1) 1). Let
m ?ol be vector
with 7t x(k) for le E [1,...,7) where x(-) is defined in Lemmal
Given a rank-1 1 lattice P
constructed by generating vector in Eq. (30,, then have Eq. 76)
1 (h ..... o hd-1 1) = T 1h C ..... h 26-2 1) + (h
h 2d-2
-1 1)
+ (h 1)
(76)
where 2 denotes the element-wise product, symbol denotes the vector with elements all ones, and h' = F'ry with F as the discrete Fourier matrix, i.e., Fjk exp(2ni ik and F denotes the matrix
after permutation of the rows of F such that the jth row of F equals the jth row of F, where si0-13
] = mod n, and denotes the primitive root modulo n.
Proof. Note that h' F is permutation of h. From the definition of permutation F' we know
that the jth row of F' cquals to the 7th row of F with jg 22-1 mod n. Note that (2d-1)) (n 1)
1(=-1)
and n is a prime number, we know {1,g 1(m=1) ...
(24 (24-2)(-- (m-
modulo n forms a subgroup of
{1.--.. n }} modulo n. Thus, we know {h" h ",,,... 1..,h22 2d forms a group, and h" = h 2d Furthermore, we know that h² is permutation of h such that 7th row of F equals to the 5th row of F' with j ig 1 (h 3 ... h d =1 (h .... 2d-1)
(m-)((=))
mod n. Thus, we know that
(77)
17

---

Note that h = h 2d It follows that
1 O d-1
1) =11=11p (h² c
h 2d -1)
(78)
=1 (h"
2d
① 12 -
(79)
In addition, we have that
hhd ④ h
2d 1, -1)
(80)
(h" C 2d- h²) 1 "h" O ... 2 h
2
1 + +1
(81)
= =1T(h" 2d 2 11) -1 1hhh 3 ...
2
+ +1
(82)
=1'(h"
h
24 h²) 1 - 1 (h C
h 2) + + +
1 h +1
(83)
=1 2d h 1) 11- 1h
h
2d-2 1) 1 1h 1)
(84)
follows that
1 (h o-. Oh 2d-2 oh 1) = (h" o ... 2d-
1, - + (h o ... 3 h 2d-2 1)
+ +1 t 1)
(85)
Plug Eq. 85 into Eq. 79.. we know that
1 (h ha-1 1) hh ....
2 1, 11) +1 1Th .... hd 1)
+ 1 -1)
(86)
Lemma 5. Let n be prime number such that (2d - 1) 1). Let 7
m 7al be a vector
with 7h = (k) for k E (1,...,n), where x(-) defined Lemma
Given a rank-1 lattice P
constructed by generating vector in Eq. (30). then we have Eg. 87)
(Thh ④ ... ② h 2d-2 1) = T (h 2 d-1 1) + (h ② .... 2d-2 -1)
+ +(h o 1, .... h 2d-2-
2 1)
(87)
where @ denotes the element-wise product, symbol denotes the vector with elements all ones, and h' F'ry with F the discrete Fourier matrix, i.e., Fş exp(2ni and F' denotes the matrix
after permutation of the rows of F such that the jth row of F equals to the 5th row of F, where 16m-12 j =ig mod n, and g denotes the primitive root modulo n.
Proof. Similar to the proof Lemma 4 we have that
(h @ h d-1 1,
3 h
2d-2 1)
(88)
= o.. d-1 o
2d--2)
T (h .... 1..... -
1T
(89)
= =1h ④ ... à h 2 - 1 T (h 2 .... h T (h'
④ ... 1 h 2d-2 1
(90)
=1 o h 2d-2) -1 -T 1 (h
o.. oh
11 1 (h d
Oh.
2d 2)
TT
(91)
-1T = ④ h 2d-2 -1)
1) - 1 TT hh
1
(h o ... 3 h 2d 1) (92)
follows that
T T(h ② ...
h 2d - 1) = (h. ④ ... h d-1 - 1) + + T (h ④ ... ....... 2d-2 -1)
+ (h" o ... 3 h d-1 1 ... 2 h 2d-2 -1)
(93)
18

---

Lemma 6. Let n. be prime number such that (2d - (n 1). Let Y
m 7ml be a vector Given rank- lattice P
with T x(k) for k E (1.....1) where x(-) defined in Lemmal 2
constructed by generating vector in Eq. 30), then we have Eq. 94
1 (h 2 ....3 2 h 2d-2 - 1) 1 ((h'
h 1) h (h (d-
....00. O hohle
1))
+ 21 T (h Q... hd-1 -
(h"
(94)
where denotes the element-wise product, symbol denotes the vector with elements all ones, and
h' F'ry with F the discrete Fourier matrix, i.e., F5 = =xxp(2ri and F' denotes the matrix
after permutation of the rows of F such that the jth row of F equals to the jth row of F, where
k5mm12
j = jg mod n, and g denotes the primitive root modulo n.
Proof. Plug Eq. (6 in Lemma 4 into 88)
/ in Lemma 5 we know that
1 oh - = 21 (h .....Of
1 (h- -1 (1 Oh. 2d-2 - 1
+ (h t o h d-1 1, o 2 2d-22 -1)
(95)
Now check the last two terms in Eq 195) Note that
(h h h"
h 2d-2 1)
(h 3... 2 hddd2 10 1)
(96)
② ..... 2 h - - (h" 1), haa 3 ... @ h 2d-2 1)
(97)
(h ..... h d-1 - h1, h2 .... ... 3 h hddd 1)
(98)
(h @ (h O.... d- 1), h"
h 2d-2 -1)
(99)
= =1 ((h ① ... 2 h d- 1) 2 h (h" ④ 3 h 2d-2 - 1))
(100)
follows that
1 (h" .... h 2d-2 1) 21 (h
h
1) 1 (h - 1)
+ +1 ((h
h h-- - 1 hD o Oh* o ... 2d-22_ 1))
(101)
Because (h 0 h
h 2d forms group, and h h 2-2-1
with a modulo period 2d - 1, we
know that
hd h 2d h (d-1) ... ....@h h
(102)
Plug Eq.
102
into Eq. 101 we have that
1
(h 0
h
2d
1) 21 (h ... ... dd- 1) - 1 1(h² - 1)
1 ((h ① .... 11) hd 3 (h d-1
h h- 1))
(103)
Now, we ready prove our main Theorem
Proof. From Lemma 3
we know that
(Ha; P) = -1 (k'o...ohtt))
(104)
From Lemma
6 we know that
(h ①
d=-1_ 1)
1 T (h @ ... 0..00h24 2d 2__ -1 -1 (h' 2 .... hdd (4-11) h (h-1- 3 .... h (d-1) - 1))
-
hd
2
+ 1 (h 1)
(105)
2
19

---

Plug Eq. 105 into Eq. 104
we have that
é² (Hbi; P)
1 1 (h
h2--2_ o..0 -1) -1)hh" (h (h- ....0 o h (d-1))1
2n
+ 2n
(hh"
(106)
Note that h Fry and denotes the discrete Fourier matrix, we have that
1 1 1) 1 Fry= = =by--1
(107)
(108)
where b = [0, 10,0,...,,0 ,0,
Note that the th element 7 is nn n ((ax 1), where ((:,)) denotes the Hurwitz zeta function. It follows that
2 n2 S(a; 1)
2 n2 S(a,1)
(109)
Plug Eq. 109 into Eq. [166. we achieve the result in Theorem
(H<4; P)
1 1
.... 2 2d= 1 (h' O... h------- - -1))) o Oh (d-(d11)-1) 1))
....0
2n
1
+ na
((x,1)
(110)
B Benchmark Test Functions
The benchmark test functions employed in section 4.1 are listed in Table which contains multi-mode functions and non-smooth functions that are challenging for optimization.
Table 2: Test functions
name
function
Rosenbrock
110( - x2?) (1 xzi²²)
Nesterov
102 1/+
r++1 |
Rastrigin
10d + Σ Σí=
(x?
10 cos (2TT:;))
20

---

C Training Time and Fast Coordinate Search Time
Ramb-1 Lattice DP
Fast Coordiaate Search
50
1.6
1.4
40
1.2
Time (3)
30
1.0
0.8
20
10
0.4
0.2
3.0
1.0
0.8
1.0
Mumber Samples
lc6
Number of Samples
les
(a) Training Time (seconds)
(b) Fast Coordinate Search Time (seconds)
Figure 5: Training Time and Fast Coordinate Search Time (seconds) v.s. the number of samples
We provide the training time of our rank- lattice GP and the time of our fast coordinate search for targeted sampling in Figure [[a] and Figure [(b] respectively. The dimension of the rank-1 lattice data is set to
50. The number of samples n is set to the parameter in {1783, 5347, 10099, 51283, 100189, 501139, 1000099). The number of samples n is a prime num- ber such that (2d - (n 1) to achieve our closed-form rank-I I lattice construction. The number of epochs of training is set to 2000. The number of iterations of fast coordinate search is set to T = 50. All the experiments are performed in 50 runs on a single NVIDIA A40 Card.
We report the mean value + std in Figure S The standard deviation of the time is small. From Figure 5(a) can that it takes around 50 seconds for our rank-1 GP training with one million lattice data. Moreover, our fast coordinate search for targeted sampling takes around 1.5 seconds to optimize rank-1 lattice GP posterior prediction conditioned on one million lattice data.
D Additional Experiments of Black-box Prompt Fine-tuning
3.4
OOL
DMG3
02
0.
(a) DBpedia
(b) SS2
(c) SNLI
2.5
2.50
24
CANIS
3.74
1.90
1.25
123
1.00
122
0.5
03
623
050
(.5
022
6. 2120 1583 TE00 THED 1908 1180
2500
120
THE
1209 SIEE ST96
18C2 106
SERO 1188 SIDSC SIMEE
(d) AG's News
(e)
MRPC
(I) RTE
Figure 6: Hinge loss v.s. the number of query evaluations on different black-box fine-tuning models.
21

---

We provide additional experimental results of black-box prompt fine-tuning for large language models. We employ the deep model (Sun al., 2022a] as the backbone. has 24 layers. For each layer, we set the dimension of the continuous prompt to 50. Thus, the total dimension is 24 x 50. We employ the hinge loss of training data as the black-box objective.
In all the experiments, we keep the number of batch samples and the initialization the same for RLTS, INGO and CMAES. We the number of batch samples 200. Our RLTS employs 199 rank-1 lattice QMC Gaussian samples and one sample from targeted sampling. INGO employs 199 rank-1 lattice QMC Gaussian samples and one Gaussian sample. CMAES employs 200 Gaussian samples. We initialize the μ for all the methods. For INGO and RLTS, we set the step-size parameter 0.2 in all experiments. For RLTS, we set the parameter rj 1 in all experiments. All the experiments are performed in five independent runs with seeds in {1. 2, 3, 4,
The experimental results of mean objective + std the number of queries shown in Figure 6 From Figure 66] we can observe that RLTS decreases the loss consistently faster than INGO and CMAES on all benchmark datasets. More importantly, RLTS decreases the loss significantly faster than INGO, Note that RLTS employs INGO as the backbone algorithm, which shows that RLTS improves the query efficiency of INGO.
22


Reviews:
[{"review_id": "n6QqoHGcOa", "reviewer": "Reviewer_AfkS", "summary": "This paper proposes a novel Rank-1lattice targeted sampling (RLTS) strategy to significantly reduce the GP training & inference time complexity and also enable $O(n\\log(n))$ time complexity in order to find a targeting reference point at each iteration. Combined with the evolution strategies, the method proposed in this paper is proven to be efficient in handling high-dimensional problems. The effectiveness of the method is also demonstrated in some benchmark testing functions and a prompt fine-tuning task.", "questions": "(1) What is the overall query complexity of Algorithm 2 or how much overall query complexity can RLTS saves compared with INGO? Even if it is a plug-in version of INGO such a result will be helpful for readers to understand the advantage of RLTS over INGO quantively.\n\n(2) How does the author define \"time complexity\" and \"query complexity\" in this paper? Are they share the same definition or not? If time complexity refers to the computation cost of solving a concrete optimization sub-problem in the overall algorithm while the query complexity refers to the total number of zeroth-order information that we need, then there is a inconsistency between the motivation and the contribution claimed by the author. (The motivation of using rank-1 sampling seems to target at reducing time complexity while the experiment try to demonstrate that rank-1 sampling can actually reduce query complexity).", "limitations": "There no limitation in this paper.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "(1) The rank-1 lattice sampling strategy reduces the computational/time complexity of GP training/inference significantly in several aspects, which should be interesting to the community\n\n(2) The author also provides a theoretical result to show that the approximation error of this new sampling method is comparable to the integral approximation error.\n\n(3) The effectiveness of the new approach is supported by sufficient experiments.", "weaknesses": "(1) Some notation is confusing, for example, $x_i$ in eq(10) and $x_i$ in line 8 of algorithm 2 are different but share the same notation.\n\n(2) For better presentation, the author can consider claiming the assumptions explicitly (for example in sec 3.3 the kernel is required to have a decomposition structure in order to make sure the coordinate searching works)\n\n(3) In GP training, in addition to considering the complexity of computing the value of likelihood, isn't it also important to consider the complexity cost in optimizing the likelihood? Such a result seems to be missing in the paper.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe sincerely appreciate the reviewer's constructive advice and valuable comments.  Our detailed responses to the reviewer's questions are presented as follows:\n\n\nQ1. “ In GP training, in addition to considering the complexity of computing the value of likelihood, isn't it also important to consider the complexity cost in optimizing the likelihood?”\n\nA1.  In GP training, each gradient descent step typically requires computing the likelihood value (forward pass), resulting in a time complexity of $O(n^3)$.  The backward usually share the same time complexity.  Consequently, the total training complexity is $O(Mn^3)$, where M represents the number of gradient descent steps. This renders standard GP impractical as a plug-in due to its high cost.  In practice, M is often a small constant, and the training complexity is primarily determined by the term related to the number of samples n.\n\nTo achieve fast training, it becomes crucial to reduce the complexity of likelihood computation. Our technique successfully reduces this complexity from $O(n^3)$ to $O(n \\log n)$, resulting in a more efficient $O(Mn \\log n)$ training complexity. This enhancement enables efficient integration with ES-type algorithms. Without our speedup technique, the entire algorithm would be prohibitively expensive.\n\nQ2 “ What is the overall query complexity of Algorithm 2 or how much overall query complexity can RLTS saves compared with INGO? Even if it is a plug-in version of INGO such a result will be helpful for readers to understand the advantage of RLTS over INGO quantively.”\n\nA2. Thanks for the reviewer's suggestion.   In this work, we empirically evaluate RLTS on various benchmark test problems and real-world fine-tuning tasks.   Our experiments demonstrate that RLTS significantly improves query efficiency compared with INGO.   We plan to investigate the convergence rate with respect to the number of queries in our future work.\n\nQ3 “...  then there is a inconsistency between the motivation and the contribution claimed by the author. (The motivation of using rank-1 sampling seems to target at reducing time complexity while the experiment try to demonstrate that rank-1 sampling can actually reduce query complexity).”\n\nA3.  We respectfully disagree with the above comment.  Our main objective is to improve the query efficiency (e.g., the query of the API call in a language model), as stated in the abstract and our contribution statement (third point).  However, directly applying GP as a plug-in poses challenges due to the large training and inference complexity and huge searching cost. The reviewer can refer to Table 1 in our rebuttal file to observe the huge time cost of the GP-based high-dimensional BO baseline TuRBO[3].  Thus, it becomes crucial to develop a method that addresses these issues concurrently. To tackle this, we develop RLTS. Our RLTS reduces the predominant  $O(n^3)$ operation in GP training/inference to $O(n \\log n)$, and supports a fast searching algorithm. Empirically, our RLTS significantly improves the query efficiency compared with INGO, CMAES, and TuRBO.  We firmly believe that RLTS presents an important and valuable technique contribution to the field. \n\n[3]  Eriksson et al., \"Scalable global optimization via local Bayesian optimization\", NeurIPS 2019. \n\n\n"}, {"review_id": "4YuiCp1c2A", "reviewer": "Reviewer_RbGC", "summary": "For the setting of black-box optimization where only function queries are available, this paper propose a rank-1 lattice targeted sampling technique to scale up to high-dimensional problems with good query efficiency. Based on the special structure, this paper use FFT/IFFFT to do fast coordinate search with O(n\\log n) time complexity. ", "questions": "See the Weaknesses", "limitations": "No", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors have a clear background introduction for black-box optimization. Meanwhile, introducing the lattice structure to optimization is new to me. Finally, applying FFT/IFFT with the Lattice structure to get an O(n\\log n) time complexity is also impressive. ", "weaknesses": "The narrative of this paper assumes that the readers have good knowledge of Lattice, but I think that many readers don't have this kind o knowledge. Some concept appears without explanation such as \"dual lattice\". As a result, it is better to give a more detailed introduction to Lattice, including why this kind of structure can work in the machine-learning context.\n\nMeanwhile, the concept of mod 1 is not clear --- what is the meaning of nonnegative fractional part??? What is the value of a decimal mod 1? Also, what is the correlation between \"spaced more evenly \" with fast targeted sampling? \n\nFinally, this paper gives a new and interesting structure to reduce complexity, but it doesn't either provide strong convergence results and a strong theoretical verification or provide any meaningful experiments.  \n\n\n\n\n, ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe sincerely appreciate the reviewer's constructive advice and valuable comments.  Detailed responses to the reviewer's questions are given below. \n\nQ1. Some concept appears without explanation such as \"dual lattice\". \n\nA1.  Thanks for the reviewer’s suggestion. We will revise the paper accordingly. \nThe definition of the dual lattice is given in Eq.(38) in the Appendix of our submission.  It is used for the analysis of approximation errors. \n\nQ2. ” Why this kind of structure can work in the machine-learning context?”\n\nA2. Rank-1 Lattice belongs to  Quasi-Monte Carlo(QMC) family. QMC methods are used to approximate integrals or expectations by sampling points in a way that ensures more even coverage of the integration domain compared to traditional random sampling. This improved coverage can lead to more accurate and stable estimates, which in turn can translate into smaller prediction errors when used in the context of Gaussian Processes.\n\nTraditional i.i.d. random sampling may produce regions with very sparse data points, which might miss important features of the function being modeled.  QMC methods can provide a more systematic exploration of such regions, leading to more accurate extrapolation and potentially smaller prediction errors.\n\nIn our work, we leverage our rank-1 Lattice to approximate the expectation (gradient approximation), resulting in a more accurate gradient.  Additionally, rank-1 lattices tend to exhibit low GP posterior prediction errors, enhancing the precision of the surrogate model.  This, in turn, empowers our RLTS approach to effectively identify strong candidates. \n\nWe would like to emphasize that our subgroup rank-1 lattice capitalizes on constructing a circulant kernel Gram matrix because of its group property. This enables efficient O(n log n) computations in GP training and inference, as well as fast candidate searching. In contrast, low-discrepancy QMC sequences, such as Sobol sequences or Halton sequences, lack these capabilities.\n\nQ3.  What is the meaning of a nonnegative fractional part?\n\nA3.  Given a real number $x$, the nonnegative fractional part of $x$ is  $x- \\lfloor x \\rfloor $, where $ \\lfloor \\cdot \\rfloor$ denotes the floor function. \n\nQ4.  What is the value of a decimal mod 1?\n\nA4.  Given a real number $x$,  the operation $x$ mod 1 equals $x- \\lfloor x \\rfloor $. \nWe will state it more clearly in our paper.  \n\nQ5. What is the correlation between \"spaced more evenly \" with fast targeted sampling? \n\nA5. A point set that is more evenly spaced helps mitigate very sparse regions, thereby leading to reduced worst-case approximation errors and yielding more accurate and stable estimates. By utilizing our Rank-1 lattice in conjunction with the inverse cumulative density function, we can effectively create evenly spaced points within a Gaussian ball. This helps to reduce the GP posterior prediction error and offers a more precise surrogate for facilitating fast targeted sampling with good candidates. \n\n\n\n\n\n\n\n"}, {"review_id": "fKNQ5QO3kM", "reviewer": "Reviewer_8XeQ", "summary": "This paper studies high-dimensional black-box optimization. In order to achieve high efficiency, this paper proposes a Rank-1 Lattice Targeted Sampling (RLTS) technique, using random rank-1 lattice Quasi-Monte Carlo, to perform fast local exact Gaussian processes (GP) training and inference with O(n log n) complexity w.r.t. n batch samples. In addition, this paper developed a fast coordinate searching method with O(n log n) time complexity for fast targeted sampling, improving the query efficiency while scaling up to high dimensional problems. The authors also proposed a closed-form construction to construct rank-1 lattices efficiently. ", "questions": "Please see the above.", "limitations": "The Paper Checklist Guidelines in https://neurips.cc/public/guides/PaperChecklist encourage authors to discuss the limitation, especially in a separate \"Limitations\" section if possible. But I was unaware of a detailed discussion on the limitations in the paper.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is generally well-structured, and the presentation is clear to the readers. The proposed sampling method for the Black-box optimization problem is novel in this area, which leads to low time complexity and scalability to high dimensional problems. The authors also provide theoretical analysis to show the error pattern of their rank-1 lattice construction. The authors further conduct an empirical evaluation to verify the effectiveness and efficiency of the proposed method on realistic tasks compared to other approaches. ", "weaknesses": "Since my evaluation of this submission is an educated guess, I would like to modify my rating according to other reviewers' feedback and the authors' response to other reviewers' questions. I have one question regarding this work: In this experiment section, the authors demonstrate the comparison between different approaches via the number of evaluations. Can the authors explain if RLTS still has a faster convergence than other compared methods in terms of physical time? \n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for dedicating time and effort to review our paper.  Your support is greatly appreciated.  \n\nQ1.  Can the authors explain if RLTS still has a faster convergence than other compared methods in terms of physical time?\n \n\nA1. We further compare our RLTS with the high-dimensional BO method,  TuRBO[3]. The experimental convergence results regarding the number of queries and the computational time comparison are shown in Figure 1 and Table 1 in the rebuttal file, respectively.  We can observe that RLTS converges significantly faster than TuRBO.  Remarkably,  RLTS achieves around 300 times speedup compared with TuRBO regarding the computational time.   \n\n[3] Eriksson et al. Scalable Global Optimization via Local Bayesian Optimization, NeurIPS 2019.\n\n"}, {"review_id": "SL8wov0dZA", "reviewer": "Reviewer_RzD5", "summary": "The paper presents the Rank-1 Lattice Targeted Sampling (RLTS) technique as a solution to the challenge of efficiently scaling up black-box optimization in high-dimensional problems. The primary objective of this technique is to enhance the query efficiency while ensuring fast Gaussian process (GP) training and targeted sampling. Additionally, the authors derive a closed-form rank-1 lattice that facilitates rapid lattice sampling. By leveraging these contributions, the paper addresses the need for efficient and scalable optimization methods in high-dimensional settings.", "questions": "- Although the paper mentions the complexity of the RLTS technique as $n \\log(n)$, it does not provide a comprehensive analysis of the overall computational costs. For instance, the targeted search (Algorithm 1) exhibits a time complexity of $O(T d n \\log(n))$, and Algorithm 2 involves computationally expensive cubic operations, such as computing the Cholesky decomposition or the square root of the covariance matrix denoted as $\\Sigma^{1/2}$, for calculating the weights $w$ (as shown in Equation 25) and updating $\\Sigma$. These operations contribute to an overall time complexity of $O(n^3)$ of a sigle iteration of Algorithm 2. Given these complexities, the question arises regarding the specific contribution of the RLTS speed-up to the efficiency of the overall algorithm.\n- Could the authors please provide a more detailed explanation of the derivation process for equations 18 and 19? The absence of a thorough explanation and references raises concerns regarding the steps involved in combining the Fourier transform of $y$ with the Fourier transform of the kernel $k$. Alternatively, if a reference exists that explains the derivation, kindly provide the appropriate citation.\n- It would be beneficial for the authors to conduct a comprehensive comparison study to evaluate and elucidate the strengths and limitations of their method relative to existing BO techniques in high-dimensional settings. It is also improtant to demonstrate that the RLTS addresses the high-dimensionality problem.\n- I would appreciate clarification from the authors regarding the stationarity requirement in the paper. While they assert that the kernel $k_\\Delta$ should be stationary (shift invariant or translation invariant), it seems that the stationarity property should be satisfied by the function $\\phi$ instead. Since the kernel $k_\\Delta$ depends on the distance between data points, which is determined by the output of the $\\phi$ function.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The authors of this paper address a crucial issue regarding the performance of Quasi-Monte Carlo methods in high-dimensional problems. They emphasize the challenges associated with effectively applying these methods in such scenarios, as high-dimensional optimization poses significant difficulties and requires a larger number of samples for accurate results. To overcome these challenges, the authors propose an alternative method that aims to enhance efficiency and mitigate the slow convergence of traditional Monte Carlo methods in high dimensions. Their proposed approach offers a solution to improve the performance of Quasi-Monte Carlo methods in high-dimensional optimization tasks.", "weaknesses": "- While the paper explores important concepts, it could benefit from improved cohesion and clarity in terms of presenting technical details and providing necessary context.\n   - The paper lacks in-depth descriptions of certain important details. For instance, a more comprehensive discussion on lattice methods and low-discrepancy sequences like Sobol sequence, would provide a solid introduction to the topic and enable readers to grasp the advantages of the rank-$1$ lattice approach more clearly. While the advantages of rank-$1$ lattices might be apparent to the authors, it is crucial to explicitly explain these benefits to the readers, ensuring that the significance of this method is clearly conveyed.\n   - Another aspect that requires clarification is the initial set of points, denoted as $x \\in \\mathcal{X}$, and the input box boundaries of the problem. The paper does not explicitly discuss how these initial points should be obtained or provide information regarding the problem's boundaries. Moreover, the process of obtaining the observed values $y$ is only mentioned in Algorithm 2, leaving questions regarding the data acquisition process in the main text.\n- The paper acknowledges the challenges faced by Bayesian optimization (BO) when applied to high-dimensional problems. However, the paper lacks a thorough comparison between the proposed RLTS technique and existing BO methods designed for addressing such problems, such as 1) trust regions, 2) structured kernels, 3) subset of active dimensions, or random projections [1, 2, 3]. The paper have not clearly articulated the unique features or advantages that make the RLTS approach competitive with established BO methods. Without explicit confirmation or evidence, it is unclear whether the proposed method performs better, equally, or worse than existing BO techniques in high-dimensional scenarios. Consequently, the comparative performance and potential advantages of the proposed RLTS technique in relation to BO methods remain uncertain.\n- The paper does not provide sufficient details regarding their experimental setup, which raises questions about key aspects such as the selection of parameter $T$, the number of data points $n$ involved in the problem, and the specifics of Gaussian process (GP) training. In order to substantiate their claim of accelerated methods, it would be beneficial for the authors to include plots that demonstrate the performance with respect to both time and iterations.\n\n[1] Binois, Mickael and Wycoff, Nathan, \"A survey on high-dimensional Gaussian process modeling with application to Bayesian optimization\", 2022, https://arxiv.org/abs/2111.05040 \\\n[2] Diouane, Youssef and Picheny, Victor and Riche, Rodolophe Le and Perrotolo, Alexandre Scotto Di, \"TREGO: a trust-region framework for efficient global optimization\", 2023, https://arxiv.org/abs/2101.06808 \\\n[3] Eriksson, David and Pearce, Michael and Gardner, Jacob and Turner, Ryan D and Poloczek, Matthias, \"Scalable global optimization via local Bayesian optimization\", 2019, https://arxiv.org/abs/1910.01739", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's constructive advice and detailed comments. However, we respectfully disagree that some of the comments may stem from a misunderstanding.  We will kindly clarify the reviewer's misunderstanding first. Afterward, we will provide thorough and detailed responses to the reviewer's questions.\n\n### Addressing Potential Misunderstandings\n\nM1. \"Another aspect that requires clarification is the initial set of points, and the input box boundaries of the problem. The paper does not explicitly discuss how these initial points should be obtained or provide information regarding the problem's boundaries. ....\"\n\nC1. Our RLTS replaces the Gaussian sampling in stochastic optimization (or Evolutionary Strategy)  via the inverse cumulative density function. The stochastic optimization (or ES) methods can deal with unconstrained problems. They do not require additional box boundary information like Bayesian Optimization. In our experiments, all the problems are unconstrained optimization problems. The initial parameter $\\boldsymbol{\\mu}$ of RLTS, INGO, and CMAES is set to $\\boldsymbol{\\mu}=\\boldsymbol{0}$ in all the experiments. The initial covariance matrix $\\boldsymbol{\\Sigma}$ is set to $\\boldsymbol{\\Sigma=I}$. The detailed experimental setup can be found in the Appendix of our submission. \n\nM2. \"Algorithm 2 involves computationally expensive cubic operations such as computing the Cholesky decomposition or the square root of the covariance matrix denoted as $\\Sigma^{1/2}$, for calculating the weights $w$ (as shown in Equation 25) and updating $\\Sigma$. These operations contribute to an overall time complexity of $O(n^3)$ of a sigle iteration of Algorithm 2.  ...\"\n\nC2. $w={(K_\\theta+\\sigma^2 I)}^{-1}$ in Eq.(25) can be computed via FFT as $w=\\text{ifft}(\\text{fft}(y)/\\text{fft}(k_\\Delta))$ shown in Eq.(22), time complexity is $O(n\\log n)$ instead of $O(n^3)$. In addition, the size of $\\Sigma^{1/2}$ is $d\\times d$. The time complexity to compute $\\Sigma^{1/2}$ is $O(d^3)$ instead of $O(n^3)$. In our experiments, we employ the diagonal matrix $\\Sigma$ instead of the full matrix with an $O(d)$ time complexity.   Overall, the RLTS does not involve the time-consuming $O(n^3)$ operation, which is crucial to be a plug-in of ES-type algorithms for improving query efficiency. Otherwise,  the algorithm will be too computationally expensive.\n\n### Responses to Reviewer's Questions\n\nQ1 “... Given these complexities, the question arises regarding the specific contribution of the RLTS speed-up to the efficiency of the overall algorithm.”\n\nA1. As clarified in our response C2, RLTS does not involve the $O(n^3)$ operation. Additionally, we have observed that Algorithm 1 demonstrates rapid convergence with a small T, and we maintain T=5 consistently across all experiments. Empirically, we showcase in Table 1 of the rebuttal file that RLTS achieves a remarkable 300 times speedup compared to TuRBO [3], as suggested by the reviewer.\nIt is essential to remark that our RLTS effectively reduces the time complexity of the predominant operation from $O(n^3)$ to $O(n \\log n)$, rendering plug-in Evolution Strategies (ES)-type algorithms computationally viable. Without our speedup technique, the overall algorithm would be prohibitively expensive. Furthermore, our RLTS significantly improves the query efficiency compared with the baselines on various benchmark test functions and extensive real-world fine-tuning tasks.\n\nQ2. “Could the authors please provide a more detailed explanation of the derivation process for Eq. 18 and 19?” \n\nA2.  The derivation is based on the circulant matrix's diagonalization and eigenvalue formula.  For a $n\\times n$ sized circulant matrix $C$ generated by a vector $c$, we can diagonalize $C$ as  $C= \\frac{1}{n}F^* \\Lambda F$, where  the $j^{th}$ row and $k^{th}$column element of $F$ is $F_{jk}=e^{-2 \\pi jk \\boldsymbol{i}/n}$. The matrix $\\Lambda$ is a diagonal matrix with diagonal elements as the eigenvalues. $\\Lambda$ can be achieved by $\\Lambda=diag(Fc)$. The matrix-vector product $Fc$ can be computed by FFT, and the matrix-vector product $\\frac{1}{n}F^*b$ for a vector $b$ can be computed by the inverse FFT.  More details about the circulant matrix can be found in the review book [4].\n\nNote that the kernel Gram matrix $K_\\theta + \\sigma^2 I$ is a symmetric circulant matrix generated by vector $k_\\Delta$,  we know $(K_\\theta + \\sigma^2 I)^{-1}y= \\frac{1}{n}F^*\\Lambda_k^{-1}Fy$, where $\\Lambda_k=diag(F k_\\Delta)$.  Then, we can easily achieve Eq.(18) and Eq.(19).    Also, we clean a typo in Eq.(19), the RHS of Eq.(19) should be  $\\boldsymbol{1}^\\top \\log( \\text{fft}(k_\\Delta) )$ instead of $\\boldsymbol{1}^\\top \\text{fft}(k_\\Delta) $, where $\\log(\\cdot)$ is an elementwise operation. \n\n[4] Robert M. Gray. Toeplitz and Circulant Matrices: A review. \n\nQ3.  “It would be beneficial for the authors to conduct a comprehensive comparison study to evaluate and elucidate the strengths and limitations of their method relative to existing BO techniques in high-dimensional settings. ...”.\n\nA3. Thanks for the reviewer’s suggestion. We compare our RLTS with the high-dimensional BO method TuRBO [3] suggested by the reviewer.    Experimental details can be found in our overall response. The convergence performance regarding the number of queries is shown in Figure 1.  We can observe that RLTS converges significantly faster than TuRBO on the benchmark test problems.\n\n The running time comparison is shown in Table 1 in the rebuttal file. RLTS performs remarkably faster than TuRBO, achieving around 300 times speedup regarding running time.  The computational time of Bayesian Optimization usually grows cubically fast as the number of queries increases.  In contrast,  our RLTS reduces the expensive $O(n^3)$ operation to $O(n \\log n)$ time complexity,  which enables a fast plug-in of the ES-type algorithms.  Without our speedup technique, the whole algorithm will be too expensive. \n\n"}]

Author rebuttal:
# Overall Response

We sincerely appreciate all reviewers’ constructive advice and valuable comments. We first present an overall response regarding the common concerns raised. Subsequently, we provide detailed responses to each reviewer’s specific questions. 

### Clarification

In this work, our main objective is to improve the query efficiency (e.g., the query of the API call in a language model). However, directly applying GP as a plug-in poses great challenges due to the large training and inference complexity, as well as the vast candidate searching cost. The reviewers can refer to Table 1 in our rebuttal file to observe the vast time cost of the GP-based high-dimensional BO baseline TuRBO[3]. Thus, it becomes crucial to develop a method that addresses these issues simultaneously. To tackle this, we develop RLTS. Our RLTS reduces the predominant $O(n^3)$ operation in GP training/inference to $O(n \log n)$, and supports a fast searching algorithm.  Empirically, our RLTS significantly improves the query efficiency compared with INGO, CMAES, and TuRBO.  

We would like to emphasize that our subgroup rank-1 lattice capitalizes on constructing a circulant kernel Gram matrix benefit from its group property. This enables efficient O(n log n) computations in GP training/inference, as well as fast candidate searching. In contrast, low-discrepancy QMC sequences, such as Sobol sequences or Halton sequences, lack these capabilities.  We firmly believe that RLTS presents an important and valuable technique contribution to the area. Moreover,  our new closed-form rank-1 lattice may have potential applications in downstream tasks beyond black-box optimization. 


### Comparison with High-dimensional BO

We compare our RLTS with the high-dimensional BO method TuRBO [3] suggested by the reviewer. We evaluate RLTS on the three benchmark functions employed in our submission: the Rosenbrock function, the Rastrigin10 function, and the Nesterov function.  The dimension is set to 500. The number of initial points of TuRBO is set to 2000. The batch size of both RLTS and TuRBO is set to 2000. The maximum number of queries is set to 50,000. We employ the default box boundary for TuRBO, i.e.,  $[-5,10]^d$.    The initial parameter $\mu$ of RLTS is set to $\mu=0$, and $\Sigma$ is set to $\Sigma=I$, the same setting in our submission. For TuRBO, we employ the official code provided in the paper [3]. All the methods are performed in three independent runs.

The convergence performance regarding the number of queries is shown in Figure 1 in the rebuttal file. We can observe that RLTS converges faster than TuRBO on the benchmark test problems, demonstrating that RLTS improves query efficiency. 

We further report the running time of RLTS and TuRBO on the same machine for evaluation. The results are shown in Table 1 in the rebuttal file. We can observe that RLTS performs significantly faster than TuRBO, achieving around 300 times speedup regarding running time. The computation time of Bayesian Optimization usually grows cubically fast as the number of queries increases. In contrast,  our RLTS reduces the expensive $O(n^3)$ operation to $O(n \log n)$ time complexity,  which enables a fast plug-in of the ES-type algorithms. 

In addition, subsets of active dimensions and random projections are techniques for reducing the effective dimension. These techniques are orthogonal to ours. They can be combined to improve performance further. 

[3] Eriksson et al.    Scalable Global Optimization via Local Bayesian Optimization, NeurIPS 2019.


Meta-review: This paper considers the block optimization problem. The proposed approach is essentially a zeroth-order approach, using function value to estimate the hessian information for acceleration. To ensure the efficiency, the hessian information is used rank-1 matrix to approximate. The idea looks reasonable and straightforward. 

The overall feedback is positive for this paper. The authors solved the concerns in experiment and the computational complexity pointed out in review. We decide to accept this paper. But this paper's theoretical justification can be stronger, e.g., 

- discuss the convergence rate, 
- whether converge to the global optimum.

The theoretical supports can refer to the zeroth order optimization literature.
Decision: Accept (poster)