Sharpness-Aware Black-Box Optimization
Authors: Feiyang Ye
Yueming Lyu
Xuehao Wang
Masashi Sugiyama
Yu Zhang
Ivor Tsang
Venue: ICLR 2025 Poster (2025)
Keywords: Black-box Optimization
Sharpness-Aware Minimization
Primary area: optimization

Abstract: Black-box optimization algorithms have been widely used in various machine learning problems, including reinforcement learning and prompt fine-tuning. However, directly optimizing the training loss value, as commonly done in existing black-box optimization methods, could lead to suboptimal model quality and generalization performance. To address those problems in black-box optimization, we propose a novel Sharpness-Aware Black-box Optimization (SABO) algorithm, which applies a sharpness-aware minimization strategy to improve the model generalization. Specifically, the proposed SABO method first reparameterizes the objective function by its expectation over a Gaussian distribution. Then it iteratively updates the parameterized distribution by approximated stochastic gradients of the maximum objective value within a small neighborhood around the current solution in the Gaussian distribution space. Theoretically, we prove the convergence rate and generalization bound of the proposed SABO algorithm. Empirically, extensive experiments on the black-box prompt fine-tuning tasks demonstrate the effectiveness of the proposed SABO method in improving model generalization performance.

Published as a conference paper at ICLR 2025
SHARPNESS-AWARE BLACK-BOX OPTIMIZATION
Feiyang Yel.2.+, Yueming Lyu Xuehao Wang',
Masashi Sugiyama Yu Zhang!. Ivor W. Tsang2.3.4.
! Department of Computer Science and Engineering. Southern University of Science and Technology
2 "Australian Artificial Intelligence Institute, University of Technology Sydney "Centre for Frontier AI Research, Agency for Science, Technology and Research, Singapore
" "Institute of High Performance Computing, Agency for Science, Technology and Research, Singapore
"RIKEN Center for Advanced Intelligence Project
"Graduate School of Frontier Sciences, The University of Tokyo
"College of Computing and Data Seience, Nanyang Technological University [fciyang, ye. s xuchaowang yu. zhang ust @mgmail con
sugiek @k. u-tokyo.... ac. ip Muyuinu Ivor. Ivor.Tsang]ecfar asstar. edw.rrredu...
ABSTRACT
Black-box optimization algorithms have been widely used in various machine learn- ing problems, including reinforcement learning and prompt fine-tuning. However, directly optimizing the training loss value, commonly done in existing black-box optimization methods, could lead to suboptimal model quality and generalization performance. To address those problems in black-box optimization, we propose a novel Sharpness- Black-box Optimization (SABO) algorithm, which ap- plies sharpness-aware minimization strategy to improve the model generalization. Specifically, the proposed SABO method first reparameterizes the objective func- tion by its expectation over Gaussian distribution. Then it iteratively updates the parameterized distribution by approximated stochastic gradients of the maximum objective value within a small neighborhood around the current solution the Gaussian distribution space. Theoretically, we prove the convergence rate and generalization bound of the proposed SABO algorithm. Empirically, extensive ex- periments on the black-box prompt fine-tuning tasks demonstrate the effectiveness of the proposed SABO method in improving model generalization performance.
INTRODUCTION
Black-box optimization involves optimizing one objective function by using function queries only. In this work, we study the black-box optimization problem (Jones et al. 1998), which is formulated as min F(xx), s.t. x E
where X' Rd, and d represents the parameter dimension. The objective function F Rd + R. which satisfies F(x)) > -oo (lower bounded), can only be queried to obtain function values and we cannot get the gradient of w.r.t. æ. In this work, we focus on the online setting for black-box optimization, where different from the offline setting (Chen et al.) 2022 Qi et al. (022). we do not have a prior dataset containing the variable æ and its corresponding objective value.
Black-box optimization has drawn intensive attention in wide range of applications, such as deep reinforcement learning (Salimans et al. 2017 Conti et al. 2018), black-box adversarial attacks of deep neural networks (Ilyas et al. 2018 8 Dong et al. 2019), etc. Recently, black-box optimization has shown increasing power on real-world natural language processing tasks, especially with the emergence of large language models (LL.Ms). Since common practice is to release LLMs as a service and allow users to access it through their inference APIs. In such a scenario, called seeguaggd-Modll-as-----
(LMaaS) (Sun et al. 2022bb at 2023). users cannot access tune model parameters but can only tune their prompts without model backpropagation to accomplish language tasks of interest, which directly increase the demand of black-box optimization methods.
"quual contribution. Corresponning author.

---

Published as a conference paper at ICLR 2025
Although black-box optimization algorithms have been successfully applied various learning tasks, most existing works directly optimize the training loss value (Sun et al. 2022b). which may lead to suboptimal model quality and generalization performance. Since the training loss landscape is complex and has many local minima with different generalization abilities (Zhang et al. 202T), the learned model may suffer from the overfitting problem, causing poor generalization performance (Foret et al. 2021). Hence, reducing the performance gap between training and testing is an important research topic in deep learning (Neyshabur et al. 2017). Recently, there have been many works exploring the close relationship between loss geometry and generalization performance, and it has been observed that flat minima often imply better generalization (Dziugaite & Roy |017] Chatterji] et al. 2019: Petzka et al. 2021). This inspires us to design a black-box optimization algorithm to improve the model generalization by finding the flat minima.
Sharpness-aware minimization (SAM) (Foret et al., 2021) is state-of-the-art method to seek flat minima in white-box cases by solving min-max optimization problem. SAM minimizes the maximum objective value within a small neighborhood around current solution. Since SAM considers the geometry of the Euclidean parameter space, uses the Euclidean ball to define the neighborhood. In SAM, each update consists of two forward- -aadddb computations: one for computing the perturbation and the other for computing the actual update direction. SAM has been proven to perform better than SGD and its variants (K (won al. 2021 ZZhaagg et al.) 2022 Zhao al. 2022
Kim et al.) [022] Jiang et al. 2023 Liu et al.) 2022) yield significant performance gains in various fields such as computer vision and natural language processing (Bahri et al.) [022 Foret et al. 2021).
However, SAM and its variants rely on the availability of true gradients or stochastic gradients w.r.t. the variable æ, so they are inapplicable black-box optimization.
To take advantage of SAM to improve the generalization performance of black-box optimization, we propose a Sharpness- Aware Black-box Optimization (SABO) algorithm. Specifically, SABO first reparameterizes the objective function via its expectation over a Gaussian distribution. which can help to optimize the objective by only accessing the function value (Wierstra et al. 2014 Lyu Tsang 202T). Then the SABO method seeks to identify the robust minimum region over the space of Gaussian distributions, which is different from SAM that finds the flat minimum over the parameter space. To achieve that, the SABO method iteratively updates the parameterized distribution via a search direction obtained by approximated stochastic gradients for the maximum objective value within small neighborhood around the current solution in the space of Gaussian distributions. Theoretically, we analyze the convergence rate and provide generalization error bound for the proposed SABO algorithm. Empirically, we verify the convergence result of the proposed algorithm on the synthetic problems, and extensive experimental results on a black-box prompt fine-tuning problem demonstrate the effectiveness of the proposed SABO method. Our contributions are summarized as follows.
We propose the SABO algorithm for black-box optimization. To the best of our knowledge, we are the first to design a stochastic gradient approximation algorithm to improve the model generalization in black-box optimization by using the sharpness-aware minimization strategy.
Theoretically, we prove that the proposed SABO algorithm possesses convergence rate O log T
in a full-batch function query setting and O VT in a mini-batch function query setting, respec- tively. Moreover, we provide a generalization error analysis for the proposed SABO method.
Empirically, we verify the convergence result of the SABO algorithm on the synthetic numerical problems. Moreover, extensive experiments black-box prompt fine-tuning tasks demonstrate the effectiveness of the proposed SABO method in improving the model generalization performance.
Notation and Symbols. We denote by || llz and || Il=o the la norm and the loo norm for vectors, respectively. -1r denotes the Frobenius norm for matrices. S+ denotes the set of positive semi- definite matrices. For square matrix X, diag(X) represents vector with diagonal entries in X, and if x is a vector, diag(x) represents a diagonal matrix with x as its diagonal entries. We define || = (X, YX) for positive semi-definite matrix Y E S or non-negative vector Y, where (5-) denotes the inner product under the Frobenius norm for matrices and inner product under the la norm for vectors. y denotes the elementwise division operation when X and Y are vectors (for the diagonal matrix), and the elementwise division operation for diagonal elements in X and Y when they are diagonal matrices.
2

---

Published as a conference paper at ICLR 2025
2 BACKGROUND
Stochastic Gradient Approximation The stochastic gradient approximation method (Wierstra et at. 2014,
a Lyu & Tsang, 202T Ye al. (2024) is representative strategy for solving black-box optimization problems, which instead of maintaining a population of searching points, iteratively updates search distribution by stochastic gradient approximation. The general procedure stochas- tic gradient approximation methods is to first generate a batch of sample points by parameterized search distribution. Then the sample points allow the algorithm to capture the local structure of the fitness function and appropriately estimate the stochastic gradient to update the distribution.
Specifically, the stochastic gradient approximation method reparameterizes F(x) as
(()) = (m) = F p()) 0)dæ,
where A denotes the parameters of density p(æ; 0) or pe and F(x) is also referred to as the fitness function for Based on this definition, obtain the Monte Carlo estimation of the search gradient as
V 1 Σ
where zy denotes the j-th sample and N denotes the number of samples. Therefore, the stochastic gradient [(O provides a search direction in the space of search distributions.
Sharpness-Aware Minimization SAM (Foret et al. 2021) attempts to improve generalization by finding flat minima. This is achieved by minimizing the worst-case loss within some perturbation radius. Mathematically, is formulated as the following minimax optimization problem:
min max F(x +)), #EX Sp
where F: 12 RR is the objective function, denotes variables that can represent model parameters. > O is positive constant, and is the perturbation whose magnitude is bounded by p² By taking the first-order approximation of F(x+ +c) over F(x)), a solution of for the maximization subproblem can be obtained as
م² (())
<(x)
(5)
[VF(2)]2
Then problem (4) can solved by performing the gradient descent method for the minimization subproblem Ø++1 2; V.V.F F(x; + <(xx)), where 3, represents the step size in the i-th iteration. Note that this gradient implicitly depends on the Hessian of F(x:) because <(x: is a function of æc To accelerate the computation, common approach in SAM-based methods (Foret et al.) [202]; Kim et al.] 2022] Jiang et al. (2023) is to apply a first-order gradient approximation,
so obtain the update rule for SAM as 1 3t 3, V Fx) viewed as constant w.r.t. C.
== where E; E(x;) is
METHODOLOGY
In this section, introduce the proposed SABO algorithm. Firstly, formulate the sharpness- aware black-box optimization as min-max optimization problem and solve it in Section [.]] and in Section
3.2 we derive the update formula of parameters in the search distribution. The detailed derivations in this section are put in Appendix A
3.1 SHARPNESS-AWARE BLACK- BOX OPTIMIZATION
Suppose we are given training set D with i.i.d. samples {(,, v.). The main objective is defined as
1 Σ
F(x; D) = D
1(:; (X),
(6)
(XD
3

---

Published as a conference paper at ICLR 2025
where æ denotes model parameters, [D] denotes the number of data in the dataset D, and (æ;; (X, y)) denotes the loss function (e.g., the pross-entropy loss for classification). To simplify the notation, we define Fxx) := F(x::)
In black-box optimization, we aim at minimizing the objective function F(x), with only function queries. Due to the lack of gradient information, first apply the stochastic gradient approximation method (Wierstra et al. 2014] Lyu & Tsang 2021). D. We denote by the parameters of the search distribution pa and define the expected fitness of F(x) under the parametric search distribution Then the optimal parameter 0 can be found by minimizing the
(o))) as J() = (=)
reparameterized objective )()..
Inspired by SAM (Foret al. 2021), attempt to improve generalization by finding flat minima of 9. However, for the reparameterized objective ( the geometry of the corresponding distribution space not Euclidean but a statistical manifold, where the distance between two probability distributions is defined by some statistical distance, e.g., Kullback-eebler (KL) divergence. Therefore, instead of restricting the perturbation in an Buclidean ball, restrict the perturbation distribution to be inside a small neighborhood of the unperturbed distribution w.r.t. the KL divergence (Amari 2016). The proposed optimization problem for black-box optimization is formulated as
min max J(0 + 5).
(7)
0 SEC(O)
where C(0) {ō (L PP) S p²) p is a positive constant, and J(0 + ((++*)=En-por Ex-pos [F(x)] Note that C(O) defines the neighborhood around a given distribution pe in the distribution space, which is different from the neighborhood of SAM that is defined in the parameter space. Here p defines the size of the neighborhood.
Generally, problem 7 is applicable to any family of distribution po- For computational consideration, the search distribution assumed to be a Gaussian distribution, i.c., pe(x) = (N μe, Σ) where μ denotes the mean and Σ denotes the covariance matrix, and correspondingly O includes μ and E, ie.. 0 = [ } In this work, we assume that the covariance matrix Σ is a diagonal matrix. For a perturbation 5 = {6 6z.) where dy is digaonal matrix, the perturbed distribution is Gaussian distribution p (x) = Nxx μ + -
We need to solve problem 7 to derive the update formulation for O. By using the first-order Taylor expansion, the maximization subproblem can be approximated as a quadratically constrained linear programming problem:
max J + 5) (
max (V))(0)) SEC(O)
(8)
The corresponding Lagrangian of problem 8 is
A() (V)J(O), + A(KT.(Po (po) ) p²),
where À is the Lagrange multiplier. We can see that problem p is convex with respect to 6. Therefore, by setting the derivatives w.r.t. 5μ and dz to zero, we can obtain ō as
2ΣV
(0) (()),
(0), (z)
(10)
2V-1-2V-J00
As shown in Eq. (10). to calculate the perturbation, we need to calculate the inverse covariance matrix, i.e., Σ-1, which is computationally expensive for high-dimensional problems. Therefore, assuming that Σ is diagonal matrix can significantly reduce the computation cost. Then by plugging 6,,(0) and (0) into the neighborhood constraint, i.c., C(O), we can determine the optimal À as
(O))B + 0.5 0.5 Σ (O))
(11)
Based on Eqs. 10 and 11). we obtain the approximated closed-fon foom solution 6(0) for a given 0. With 8(0), the minimization subproblem of problem (7) can be reformulated
J(e 5(0)).
(12)
To solve problem 12). in the f-th iteration, add regularization term 3. KL llp)) to problem 12 enforce 0 to be close to 0,, and obtain Q by solving the following problem
1 KL(pollpe.)
0 = arg min J(O + ((0)) J(O,) + B.
(13)
4

---

Published as a conference paper at ICLR 2025
Following standard --sed methods (Foret al. 2021). treat 6(0,) as constant ó, instead of a function of 0, to accelerate the computation. Then by using the first-order Taylor expansion, problem 13) can be approximated as
1 <L(pollPo.)
0+1 arg min 0. VoJ + 6,)) +
(14)
0
3
By solving problem
14 we can obtain the update formulations for and Σ in the t-th iteration as B, v. 6z), ا Σ,- 2 J + 6t),
M++1 = 14
(15)
where [O 6t) and J(O, 5.) denote the derivative of (()) w.r.t and E at μ 0. + 8pp
and Σ E, + 5z,, respectively.
3.2 UPDATE FORMULATIONS FOR SABO
The gradients of the reparameterized objective O0) w.r.t and Σ rely on the expectations of the black-box function and can obtained with only function queries (Wierstra et al. 2014) (see Theorem in Appendix A.4). Hence, we estimate them by Monte Carlo sampling. Specifically, the stochastic approximation of the gradients ( and (s,( are given as
g.
Σ
N E, (x') 1851-Mi11 (i)(((() F(Hi)),
(16)
N N
G¹ 2N
1 Σ j=1 diag [diag pe) ma) E () ())(())))
-(((a)))((u))]]] F(w))]].
(17)
where xz, denotes the j-th sample sampled from the distribution Nxx Me: E.). Note that g is an unbiased estimator for the gradient (0) as proved in Lemma C.5 and inspired by Lyu & Tsang
(2021), we subtract F(u,) ) to improve the computational stability while keeping them as unbiased estimations. To avoid the scaling problem, in practice,
employ a monotonic transformation
strategy and the details can be found Appendix
Then according Eq. 1T)) obtain the perturbation 5, in the t-th iteration 2E,G; 1 Eigh, X 2G
5:
(18)
where À is approximated by v E + 0.55| E 9.1.2. Similarly, the gradients V T( and (e, + 5t) can be approximated as follows:
8.)
N Σ Σ (x, (.) F(P:))
(19)
G. = 2N E diag E--1 [diag (diag((;; - pr) ( -
1
(20)
where Σ, = E, &o, T. = pr + 8p and xy denotes the j-th sample sampled from the distribution
A(x p., Σ.). Then the updated formulations for and Σ are rewritten as
p++1 μr B, E.gr. ET1 Σ, + 23,
(21)
The entire algorithm shown in Algorithm [ To avoid the scaling problem, in practice, we can employ monotonic transformation for the objective, more details can be found in Appendix F For the proposed SABO method, the computation cost per iteration is of order ((N)).
Mini-batch SABO. In Algorithm I we assume full access to the objective function F F(x:; D), while in practice, a full-batch function query might be costly. Therefore, we can perform mini-batch function query. Specifically, in each iteration, query the expected fitness by mini-bated of data and approximate F( D) by
1 E
F(x; B)
|B (x,)es 1(:; (X, K.u)),
(22)
where [B] denotes the number of data in the mini-batch B. The corresponding expected fitness of F(x; B) under the distribution po(x)) formulated as (O; B) [ [F(x;; B)]. Then similar to
the full-batch function query setting, we approximate the gradients V ((, 13) and (z,)(O,, B), where the detailed formulations can be found in Appendix [ The entire SABO algorithm with
mini-batch function queries is shown in Algorithm 2 Appendix B
5

---

Published as a conference paper at ICLR 2025
Algorithm 1 SABO
Require: Neighborhood size p. learning rate Br
1: Initialized 0g = (40. Mo)
2: for 0 to T do
3: Take i.i.d. samples zj ~ (0, 1) and set a + E 2 for E (I,...,N].
4: Query the batch observations { )..... )))
5:
Compute the gradient 9 via Eq. (16) and compute the gradient G2 via Eq.
6:
Compute À = V + 0.5| 2 g
7:
Compute fc. and ōz. via Eq. 18);
8:
Take i.i.d. samples 2j ~ NO0 for j f1....,NJ: N);
9:
Set æ; 1r + pu. + (E, + 8x, 2 2 for j NJ.
10:
Query the batch observations {F 2 )......... Fx
11:
Compute the gradient gr via Eq. 19 and compute the gradient G. via Eq. 20
12:
Set p4+1 = p4 3, Le and set - t+1 =2 + G3,
13:
end for
14:
return 0- = (HT, Er).
ANALYSIS
In this section, we provide comprehensive theoretical analyses for the proposed SABO method with all the detailed proofs in Appendix D
4.1 CONVERGENCE ANALYSIS OF SABO
Firstly, make assumption for the reparameterized objective function.
Assumption 4.1 The function F(x) ) is Lp-Lipschitz w.r.f. C. The function ((0) satisfies that (O) L-Lipschitz w.r.t. 0 (1, Σ} E O, where {u, Σ μ E Rd Σ E S+
Note that the proposed SABO algorithm approximates the gradients of the reparameterized objective function. is necessary to study the relation between the optimal solutions of the original objective functions F(x) and J(Ø), and we put the results in the following proposition.
2021) Suppose pa po(ar) a Gaussian distribution with {uu, E} and (x) is convex function. Let ( = Ep [(r)), and J(p", ,0) F(p"). Then we have
Proposition 4.2 (Lyu & Tsang
F(P) F(4") S [1, Σ) - Hp. (p²,))
(23)
where 0 denotes a zero matrix with appropriate size.
The convexity assumption of the objective function in Theorem 4.3 has been widely adopted in the area of stochastic gradient approximation black-box optimization (Beyer) 2014; Wierstra et al.) 2014: Lyu & Tsang, 2021: Ye 2023). Since the Gaussian- smoohh approximation function is always an upper bound of the true target function in convex cases, i.e., F(2) < (F(()))[((<))) When 4=" is an optimal solution of minimization problem min, F(z), Proposition 4.2 implies that the difference between the objective value at μ and the optimal objective value of the original problem apperebounded by that the expected objective function. Then for Algorithm the following theorem captures the convergence of μ for convex objective function.
Theorem 4.3 Suppose that F(x) is convex function,, J(O) is c-strongly convex w.E.t μ4, the gradient
estimator Ge (W.rtt the covariance matrix) is positive semiidefinite matrix such that {I = G, N el with & 2 0, Eo E St, and Eg 1 RI where R > Suppose the sequence {pr} generated by Algorithm Saaamm/ssaan satisfies that the distance between the sequence {1u} and the optimal solution of La F(ar) is bounded, iee, 1|m - 1=1l || < D, Vx)xJ((()) < H, Br = O(1), and < 2 satisfies
O 1) then with Assumption 4.1 we have
1 Σ
E [[ Σe) - J(p, [0] = O log I
(24)
7 1=0

---

Published as a conference paper at ICLR 2025
Based on Theorem 4.3 and Proposition 4.2 when Br O(1 and p 0(
have
VT
E (F((4))) F(x")1 = 0 log T
(25)
T
Therefore, the proposed SABO algorithm with full-batch function query possesses convergence
rate O lo for the convex objective function. Additionally, in Theorem 4.3 when 3 = O(1) and
(1), the proposed SABO algorithm still maintains a convergence rate O(T- $). The detailed
discussion is provided in Remark D.I
For the mini-batch setting, we make an additional assumption for the objective function F(æ; D).
Assumption 4,4 It is assumed that the datasets 'D and B are i..dd sampled from a data distribution P(X, y), and the variance of the mini-butch estimation of the objective function is bounded, i.e.,
[[: (3) EF B)] S E and [[F(<; -EF(x) 2 S ED.
Note that for the standard stochastic gradient descent (SGD) method (Shamir & Zhang 2013), the unbiased estimation and bounded variance assumptions were made for the approximated gradient. However, in black-box optimization, the gradient of the objective function F(xx) w.r.t. x: is unavailable. Hence only make assumptions for the batch estimations F(x; B3) and F(x; D).
Then we have the following result for the mini-batch estimation.
Proposition 4.5 Suppose Assumption 4.4 holds, then have EF(x:B) EF(x:D), and [[[(:; B)- - F( 3 < E?, where e² = (cB +
Then with Assumption 4.4 the following theorem shows the convergence of μ for Algorithm P
Theorem 4.6 Suppose that F(x) is convex function, J(0) is c-strongly convex w.r.t. μ., the gradient
estimator Gt (w.r.t. the covariance matrix) is positive semi semi-definite matrix such that &I 1 G. - el with & > 0, Eg E St, and Eg 3 RI where R > O. Suppose the sequence {ui} generated by Algorithm satisfies that the distance between the sequence { and the optimal solution of F(xx) Jd bounded, ie., ||p |= < D, V x, (())llr S H, B, (1)), and 2 satisfies 0(1).
Then with Assumptions 4. and we have
E [J E.) - J(,, 00] =
(26)
Based on Theorem 4.6 and Proposition 4.2 the proposed SABO algorithm with mini-batch function query possesses convergence rate (TT 2).
Remark 4.7
Note that in Theorem 4.3 and Theorem 4.6 the convergence results do not require the
objective function F(x) be strongly convex differentiable. Hence, the convergence holds for non-smooth convex function F(x) (as long as (() being a e-strongly convex function w.r.l. Ja).
4.2 GENERALIZATION ERROR ANALYSIS
In this subsection, we analyze the generalization bound of the proposed SABO algorithm. Specifically, we bound the expectation of the objective function over the Gaussian perturbation.
We denote by (X, y) data pair drawn from a data distribution P(X, y) and by F(x; (X, v)) the corresponding loss of parameter on (X, y). So we have F(æ; (X, y)) = l(x; (X.v)). We define the population loss over the data distribution P(X, y) as Ep(x,)) [ax; (X, v))] and the empirical loss over dataset S, which consists of M i.i.d. samples drawn from P(X,)) y), as F(x;S) M EM ((x; (X,, y1)). Then we have following result.
Theorem 4,8 Let the loss function F(x; (X,v)) be convex function w.r.t. then for any p Rd. with probability at least K, we have
0² + +og( M
E Ep(x,) (((;
max E Epo.s [F(x;)]] + SEC(e)
(27)
2(M 1)
7

---

Published as a conference paper at ICLR 2025
where pe N(,, Σ), ((0) {6 (I(po+sslpo)) p²). and S denotes the training that consists of M i..dd samples drawn from data distribution P(X,3) y)-
Theorem 4.8 provides a generalization bound for the proposed SABO algorithm. Compared with the generalization bound of SAM presented in Appendix A. of Foret et al. (202T), Theorem [4.8 has an asymptotically identical order in the complexity term. However, the expected generalization loss the right-hand side of Eq. (27 is different in that we reparameterize the objective function and have perturbation of 0 in its neighborhood of statistical manifold, i.e., 5 E C()), while SAM bounds the generalization loss averaged over a spherical Gaussian perturbation on parameters.
5 RELATED WORKS
Black-Box Optimization. Many methods have been proposed for black-box optimization, including
Bayesian optimization (BO) methods (Srinivas al. 2010; Gardner al., 2017: Nayebi al.
2019). stochastic optimization methods such as evolution strategies (ES) (Hansen
2006
Wierstra
al. 2014 Lyu & Tsang 202I). and genetic algorithms (GA) (Srinivas & Patnaik 1994 Mirjalili
2019). Among those methods, BO achieves good performance for www-dimensional problems, but
often fails handle high- nigh-dimensional problems through a global surrogate model, as shown in (Friksson et al. 2019) and (Nguyen et al. 2022). As result, TuRBO (Friksson et al., (219) and
GIBO (N guyen et al., 2022) try address this problem with the local BO approach. (Ziomek Ammar 2023) further showed that decomposition is important for alleviating the tigh-ddmenniioal problems in BO. Although BO is not our main focus, we further compare our method with these local Bayesian optimization methods the black-box prompt fine-tuning problem, and the corresponding exploration shown in Appendix [H. GA method is computationally expensive for machine learning problems and usually lacks convergence analysis. The stochastic optimization methods such CMA- ES (Hansen 2006) and INGO (Lyu & Tsang 2021) can scale up to higher-dimensional problems compared with BO. Hence we mainly consider stochastic optimization methods as baseline methods in our experiments.
Sharpness-Awan Minimization. SAM has been widely studied for improving the model gener- alization. Among previous works on SAM (Kwon et al., 202T Zhuang et al.) 2022 Zhao et al.) 2022, Jiang et al., 2023] Tahmasebi et al. 2024), the most relevant method to our approach is the FSAM method (Kim et al. 2022) which also finds the worst-case objective function via a statistical manifold instead of the Euclidean space. However, the loss function of the model studied FSAM is predictive distribution conditional on both model parameters and data, while in our case, we consider the parameter as a Gaussian distribution. The bSAM method (Möllenhoff & Khan (022) builds connection between the SAM objective and Bayes objective by Fenchel biconjugate of the loss function. Möllenhotf & Khan 2022) shares a similarity with our work in developing SAM w.r.t. the expected loss. However, The bSAM method relies the derivation of a convex lower bound of the expected loss by the Fenchel biconjugate and the perturbation is still w.r.t. each point inside the expected loss as standard SAM. Hence FSAM and bSAM different from the proposed SABO method. Additionally, like other variants of SAM, FSAM and bS AM are both inapplicable to black-box optimization. The STABLEOPT method (Bogunovic al. 2018) proposes a SiM-like optimization formulation in the Bayesian optimization area. They aim to improve the robustness w.r.t. the adversarial perturbation of the return point by a GP-based optimization. Their method relies on GP surrogate model that is expensive for training and inference. In addition, it is challenging for the proposed adversarial robust GP-based optimization to handle high- dige-hiimnsional problems. In contrast, our work aims to improve the generalization property in high-dimensional black-box optimization.
EMPIRICAL STUDY
In this section, we empirically evaluate the proposed SABO method, and compare it with four representative black-box methods, i.e., CMA-ES (Hansen 2006), MMES (He et al. 2020). BES (Gao
& Sener 2022). and INGO (Lyu & Tsang 2021). All the experiments are conducted on a single NVIDIA GeForce RTX 3090 GPU.
8

---

Published as a conference paper at ICLR 2025
6.1 SYNTHETIC PROBLEMS
To verify the convergent results of the proposed SABO method in Section We compare the proposed SABO method with baseline methods on minimizing four d-dimensional synthetic benchmark test functions, i.e., ellipsoid function, 1 -ellipsoid function, different powers function, and Levy function. All the test functions are listed in Appendix G.1
The results are evaluated by calculating the Euclidean distance between the solution æ and the optimal solution x², i..., & = x x= x=112. We then assess the baseline methods using varying dimensions, i.e. d {200, 500, 1000}. Due to the page limitation, the implementation details and more detailed experimental results are put in Appendix G.1
2.5
L.0
065-5
D4A-E5
CRAES
KD0
PCD
$480
$483
-35
2480
$A3D
meratin 7,000N
(a) Ellipsoid.
(b) 1 -Ellipsoid.
(c) Different Powers.
(d) Levy.
Figure Results on the four test functions with problem dimension 500 and N 50.
Result. Figure shows the results four d-dimensional synthetic problems with d 500 and
population size N = 50. The proposed SABO method approximately achieves a linear convergence rate similar to the INGO method. This is reasonable these two methods have the same theoretical convergent rate, i.e., O {o according to Theorem 4.3 and Theorem 5 in Lyu & Tsang (0021) Since the SABO method perturbs the main objective in each iteration, its practical convergence speed is slightly slower than INGO. The CMA-ES method and MMES methods can converge on the ellipsoid problem and the different powers problem, but they do not converge as fast SABO and INGO methods. Moreover, CMA-ES -ES and MMES methods fail on the / -ellipsoid problem and
Levy problem. The BES method fails all test problems. This shows that it could be challenging for BES to optimize non-smooth or high- high-dimensional test functions without adaptively updating mean and covariance. These results demonstrate the superiority of the SABO method in optimizing high-dimensional problems, and verify our theoretical convergence results.
6.2 BLACK-BOX PROMPT FINE-TUNING
Black-box prompt fine-tuning large language models (Ding et al. 2023 Sun al. 2022b a 2023 is promising direction to achieve expertise models efficiently for downstream tasks. In such an LMaaS setting, we cannot access the model parameter and can only tune their prompts without backpropagation. We evaluate the proposed SABO method in improving generalization performance on the black-box prompt fine-tuning task.
Datasets. We conduct experiments six language understanding benchmark datasets: SST-2 expeererii
(Socher et al. 2013) and Yelp polarity (Zhang et al., (015)) for sentiment analysis, AG's News (Zhang
al.] 2015) for topic classification, MRPC (Dolan & Brocketi, 2005) for paraphrase, RTE (Wang
et al. 2018) and SNL/ (Bowman et al. 2015) for natural language inference. Each dataset contains a classification task. The statistics of six datasets are summarized in Table of (Sun et al.) 2022b).
By following (Sun et al. 2022b), the testing accuracy is used to measure the performance of all the methods on the SS7-2, AG's News, RTE, SNLJ, and Yelp P. datasets, and the F1 score is used to measure the performance on the MRPC datasets.
Implementation Details. Following Sun et al. (202bb). we employ a fixed randomly initialized matrix A RR project vector ga onto the token embedding space DR Then

---

Published as a conference paper at ICLR 2025
Table Performance (%) on SST-2, AG's News, MRPC, RTE, SNLI and Yelp P. datasets. We report the mean and standard deviation over 3 random seeds. The best result across all groups is highlighted in bold and the best result in each group is marked with underlined.
Methods
SST-2
AG's News
MRPC
RTE
SNLI
Yelp P.
Zero-shot
79.82
76.96
67.40
51.62
38.82
89.64
Dimension d 200
CMA-ES
85.7410.3
82.09
74.98
11.0212.11
34.27
90.57
MMES
83, 83.9840.75
80. 80.52=0..0
76.34444.44
48 20.5000.45
40.39+1.83
90,9 90,94
83.52
75.44 75.44_0.31
79.23
53.00 10.29
38.73
89.65
INGO
=3.57
76.47=0.03
78.8 78.87=0.20
53. =0.007=0.00
86
89, 29.84
SABO
20.88
82 82.22 00.41
79.35..0.12
53.67..0.17
10.15
20.50
Dimension
500
CMA-ES
82.50 16.1220.50
77.10
52.71
41.34:11.99
91.1920.84
MMFS
85. 05.28
81.67 =0.80
77.31
48.74 sa
42.07
91.39
BES
83.56 83.56+.0.05
75.93=2..1 17
79.21+
62.95
38. 38.6440.28
89.62=0.07
INGO
84.29
76.54_0.20
79.09
53 18.19
38.91
89.90=0.13
SABO
87.31 17.31
82. 65 .09
79.62.0.07
53.55
42.29
91.83.0.1
Dimension d 1000
CMA-ES
86.8520.57
82.21 121=:0 111:0.00
78.98
02.35
38.40
90.4620.02
MMES
84.98
80.86 1.95
76.4310.54
49.22
39.8219.43
91.6310.20
BES
83.11+0.11
75. 666
79.09
63.1940.11
38.57+0015
89.61 =0.04
INGO
04.3
76.35_a.24
78.97=a.0s
53.07
39.05.an.o6
=0.05
SABO 87.96 20.83
82.77
79.68..0.2
53.31
40.32
91.96
optimize the vector v Rd instead of directly optimizing the prompt p RDD. The pre-trained
ROBERTALARGE model (Liu et al. 2019)) is used as the backbone model. The matrix A is sampled
from the normal distribution as deseribed in Sunn et al. (2022a). i.c., (N(0, (g), where de is the
standard deviation of word embeddings in RoBERTaLARGEE The templates and label words in Table 1 of Sun et al. (2022b) used conduct the shot baseline.
For CMA-ES, MMES, BES, INGO, and SABO methods, we employ the cross-entropy loss of training data the black-box objective for six datasets and optimize the vector with 100 iterations. The Gaussian distributions are initialized as pa = O and Eg = I, and the population size N is 100. We perform a grid search for hyperparameters of INGO, SABO, and BES methods. Specifically, we search the learning rate 33 over {0.1, 0.5, 1, 5 for INGO, SABO, and BES, the neighborhood size p over {10, 50, 100, 500} for SABO, and the spacing e over {0.1, 1, 10] for BES. Additionally, we evaluate the performance of all methods on different dimensions of specifically E {200, 500, 1000}. All the experiments are performed in three independent runs, and the experimental results of mean objective + std are reported.
Results. Table 1 presents experimental results on these six benchmark datasets for three different dimensions of the vector v. We can see that the SABO method consistently outperforms all baselines in terms of testing classification accuracy or testing Fl scores across different settings, highlighting its effectiveness in improving generalization performance. Notably, even in the high-dimensional setting (i.e.,& d 1000), our method maintains good performance. Moreover, = 1000, SABO achieves the best performance on SST-2, AG's News, MRPC, and Yelp P. datasets. The SABO method also achieves the best performance on RTE and SNLI datasets with d 200 and d = 500, respectively.
see that when
CONCLUSION
In this work, we have introduced SABO, a novel black-box optimization algorithm that improves generalization by utilizing a sharpness-aware minimization strategy. Theoretically, we provide convergence guarantee for the proposed SABO algorithm in both full-batch function query and mini-batch function query settings. Additionally, we prove the generalization bound for the proposed method. Empirical studies on synthetic numerical problems verify the convergence properties of the proposed method. Moreover, extensive experimental results on black-box prompt fine-tuning problems demonstrate the effectiveness of the proposed SABO method improving the generalization performance.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
This work is supported by National Key R&D Program of China 20222D01 60300 and NSFC key grant under grant no. 62136005. Dr. Yueming Lyu is supported by Career Development Fund no. C243512014 and no. C233312007 of the Agency for Science, Technology and Research. Prof. Sugiyama was supported by the Institute for Al and Beyond, UTokyo and by a grant from Apple, Inc. Any views, opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and should not be interpreted as reflecting the views, policies or position, either expressed or implied, of Apple Inc.
REFERENCES
Shun-ichi Amari. Information geometry and its applications, volume 194. Springer, 2016.
Dara Bahri, Hossein Mobahi, and Yi Tay. Sharpness-awan aware minimization improves language model generalization. In Annual Meeting of the Association for Computational Linguistics, 2022.
Hans-Georg Beyer. Convergence analysis of evolutionary algorithms that are based on the paradigm of information geometry. Evolutionary Computation, 22(4):679-709, 2014.
Ilija Bogunovic, Jonathan Scarlett, Stefanie Jegelka, and Volkan Cevher. Adversarially robust optimization with gaussian processes. Advances in neural information processing systems, 31, 2018.
Samuel R Bowman, Gabor Angeli, Christopher Potts, and Christopher D Manning. A large annotated corpus for learning natural language inference. arXiv preprint 1508..0500000 05326, 2015.
Niladri S Chatterji, Behnam Neyshabur, and Hanie Sedghi. The intriguing role of module criticality in the generalization of deep networks. arXiv preprint arXiv: 1iXX::9122000288 2019.
Can Chen, Yingxueff Zhang, Jie Fu, Xue Steve Liu, and Mark Coates. Bidirectional learning for
offline indinite-width model-based optimization. Advances in Neural Information Processing Systems, 35:29454 29467, 2022.
Edoardo Conti, Vashisht Madhavan, Felipe Petroski Such, Joel Lehman, Kenneth Stanley, and Jeff Clune. Improving exploration in evolution strategies for deep reinforcement learning via population novelty-seeking agents. Neural Information Processing Systems, 2018.
Ning Ding, Yujia Qin, Guang Yang, Fuchao Wei, Zonghan Yang, Yusheng Su, Shengding Hu, Yulin Chen, Chi-Min Chan, Weize Chen, al. Parameter- efficieent fine-tuning of large-scale pre-trained language models. Nature Machine Intelligence, 5(3):220-233 235, 2023.
Bill Dolan and Chris Brockett. Automatically constructing a corpus of sentential paraphrases. In Third International Workshop Paraphrasing, 2005.
Yinpeng Dong, Hang Su, Baoyuan Wu, Zhifeng Li, Wei Liu, Tong Zhang, and Jun Zhu. Efficient decision-based black-box adversarial attacks on face recognition. In IEEE/CVF Conference on Computer Vision and Patlern Recognition, 2019.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703. 1000. 2017.
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.
Clara Fannjiang and Jennifer Listgarten. Autofocused oracles for model-based design. Advances in Neural Information Processing Systems, 13:12945-1 2020.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimization for efficiently improving generalization. In International Conference on Learning Representations, 2021.
11

---

Published as a conference paper at ICLR 2025
Katelyn Gao and Ozan Sener. Generalizing gaussian smoothing for random search. In International Conference on Machine Learning, pp. 7077-7101. PMLR, 2022.
Jacob Gardner, Chuan Guo, Kilian Weinberger, Roman Garnett, and Roger Grosse. Discovering and exploiting additive structure for bayesian optimization. In Artificial Intelligence and Statistics, 2017.
Nikolaus Hansen. The ema evolution strategy: a comparing review. Towards a new evolutionary computation: Advances in the estimation of distribution algorithms, pp. 75-102, 2006.
Xiaoyu He, Zibin Zheng, and Yuren Zhou. Mmes: Mixture model-based evolution strategy for
large-scale optimization. IEEE Transactions on Evolutionary Computation, 25(2):320-333, 2020.
Andrew lyyas Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In International Conference on Machine Learning. 2018.
Weisen Jiang, Hansi Yang, Yu Zhang, and James Kwok. An adaptive policy to employ sharpness- aware minimization. In International Conference on Learning Representations, 2023.
Donald R Jones, Matthias Schonlau, and William J Welch. Efficient global optimization of expensive black-box functions. Journal of Global optimization, 13:455-492 1998.
Minyoung Kim, Da Li, Shell X Hu, and Timothy Hospedales. Fisher SAM: Information geometry and sharpness aware minimisation. In International Conference on Machine Learning, 2022.
Aviral Kumar and Sergey Levine. Model inversion networks for model-based optimization. Advances in neural information processing systems, 33:5126-5137, 2020.
Jungmin Kwon, Jeongseop Kim, Hyunsco Park, and In Kwon Choi. Asam: Adaptive sharpness- awwrre minimization for scale-invariant learning of deep neural networks. In International Conference Machine Learning, 2021.
Tianyi Lin, Zeyu Zheng, and Michael Jordan. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems, 35: 26160-26177 75, 2022.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv: 1907. / 1692, 2019.
Yong Liu, Siqi Mai, Xiangning Chen, Cho-Jui Hsieh, and Yang You. Towards efficient and scal- able sharpness-ave aware minimization. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2022.
Yueming Lyu and Ivor W Tsang. Black-box optimizer with stochastic implicit natural gradient. In European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databuses, 2021.
David A McAllester. Pac-bayesian model averaging. In Annual Conference on Computational Learning Theory, 1999.
Leland McInnes, John Healy, and James Melville. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint 1rX:::180..03426. 2018. 2018
Seyedali Mirjalili. Evolutionary algorithms and neural networks. In Studies in computational intelligence, volume 780. Springer, 2019.
Thomas Möllenhoff and Mohammad Emtiyaz Khan. Sam as an optimal relaxation of bayes. In The Eleventh International Conference Learning Representations, 2022.
Amin Nayebi, Alexander Munteanu, and Matthias Poloczek. A framework for bayesian optimization in embedded subspaces. In International Conference on Machine Learning, 2019.
Yurii Nesterov and Vladimir Spokoiny. Random gradient- free minimization convex functions. Foundations of Computational Mathematics, 17(2):577556, 2017.
12

---

Published as a conference paper at ICLR 2025
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring generaliza- tion in deep learning. In Neural Information Processing Systems, 2017.
Quan Nguyen, Kaiwen Wu, Jacob Gardner, and Roman Gamett. Local bayesian optimization via maximizing probability descent. Advances in neural information processing systems, 35: 13190-13202 2022.
Henning Petzka, Michael Kamp, Linara Adilova, Cristian Sminchisescu, and Mario Boley. Relative flatness and generalization. In Neural Information Processing Systems, 2021.
Han Qi, Yi Su, Aviral Kumar, and Sergey Levine. Data-driven offline decision-making via invariant representation learning. Advances in Neural Information Processing Systems, 35:13226-13233 2022.
Shogo Sagawa and Hideitsu Hino. Gradual domain adaptation via normalizing flows. arXiv preprint arXiv:2206. 1122206.1144 11491, 2022.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as scalable alternative to reinforcement learning. arXiv preprint arXiv:/703.0366 2017.
Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In International Conference Machine Learning. 2013.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Conference on Empirical Methods in Natural Language Processing, 2013.
Mandavilli Srinivas and Lalit M Patnaik. Genetic algorithms: A survey. Computer, 27(6):17-26. 1994.
Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimiza- tion in the bandit setting: no regret and experimental design. In International Conference on Machine Learning, 2010.
Tianxiang Sun, Zhengfu He, Hong Qian, Yunhua Zhou, Xuan-Jing Huang, and Xipeng Qiu. Bbtv2: towards gradient-free future with large language models. In Conference on Empirical Methods in Natural Language Processing, 2022a.
Tianxiang Sun, Yunfan Shao, Hong Qian, Xuanjing Huang, and Xipeng Qiu. Black-box tuning for -anguagg-moodellas---seevvve- In International Conference on Machine Learning, 2022b.
Tianxiang Sun, Zhengfu He. Qin Zhu, Xipeng Qiu, and Xuan-Jing Huang. Multitask pre-training of modular prompt for chinese few-shot learning. In Annual Meeting of the Association for Computational Linguisties, 2023.
Behrooz Tahmasebi, Ashkan Soleymani, Dara Bahri, Stefanie Jegelka, and Patrick Jaillet. A universal class of sharpness- minimization algorithms. In International Conference on Machine Learning, pp. 17418-47440, PMLR, 2024.
Brandon Trabucco, Aviral Kumar, Xinyang Geng, and Sergey Levine. Conservative objective models for effective offline model-based optimization. In International Conference on Machine Learning, pp. 10358-10368. PMLR, 2021.
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, arXiv preprint 100.0:1804.07411. 2018.
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-980, 2014.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mniss a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 2017.
13

---

Published as a conference paper at ICLR 2025
Feiyang Ye, Yueming Lyu, Xuehao Wang, Yu Zhang, and Ivor Tsang, Adaptive stochastic gradient algorithm for black- box multi-objective learning. In The Twelfth International Conference on Learning Representations, 2024.
Haishan Ye. Mirror natural evolution strategies. arXiv preprint arXiv:2308. 00469, 2023.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. In Neural Information Processing Systems, 2015.
Yang Zhao, Hao Zhang, and Xiuyuan Hu. Penalizing gradient norm for efficiently improving generalization in deep learning. In International Conference on Machine Learning. 2022.
Juntang Zhuang, Boqing Gong, Liangzhe Yuan, Yin Cui, Hartwig Adam, Nicha Dvorekk, Sekhar Tatikonda, James Duncan, and Ting Liu. Surrogate gap minimization improves sharpness-aware training. In International Conference on Learning Representations, 2022.
Juliusz Krzysztof Ziomek and Haitham Bou Ammar. Are random decompositions all we need in high dimensional bayesian optimisation? International Conference on Machine Learning, pp- 43347-43368. PMLR, 2023.
14

---

Published as a conference paper at ICLR 2025
A ADDITIONAL MATERIAL FOR SECTION 3
A.1 DETERMINE THE PERTURBATION 6
The Lagrangian of problem (8) is
()) (O)) 5) + (PKLlpo)))) p²)
(28)
6 V ((0)) - trōo (()x)))((B.))))
A ir ( + 0z)) + 5 E
Σ
(29)
6, + log
d
Ap?
( + dz)
Taking the derivative ,n and 8y and setting them to zero, we can obtain that
V J(0) - AΣ 1
8, =0
(30)
( 1115 :=55)) E = 0.
(31)
Note that Σ is a diagonal matrix. Therefore, we can achieve that
6,((0) = EV 1 (0),
(32)
2EVrJ(()
6x XΣ-I - (0)
(33)
A.2 DETERMINE THE OPTIMAL À
Note that we have
Σ
KL(ro+5llpe)
tr(E-1) (E+dg)) + +6,5 80 + log
(34)
2
[ + 5555
1
[
tr(l (E)((){E+0 + dz)) + + x 2-14 1-16 10 + log
(35)
2
A
[E+ + 8z))
1
+ + 8, + ②
tr(
(36)
2
where
2 Q =
ー こ() + log(1 2 (())
(37)
Since E and (0) are both diagonal matrix, we denote diag (V = (6* (r",,..,o"), then
we have
Q = log(
II
ot)) + Σ
d
2 v²
d log(1 -
2 (0)) 2
2
Σ
d
2
(v0)2 -0(
(10)3).
A
x
22
i=1
1=1
i=1
(38)
We denote diag( (()) (6) ..... )a), then we have 8' rd and
d
2 tr( {z)(0)0)
Σ1 (oo)-1- Zo ot) Σ
2
8/(
1
2
2
(6)
o 4 (o())))) (39)
x
i=1
Then substituting (0) and (z) into the inequality KL ((pp)) s p², we can obtain that
(T.ppo+llpo)
2 2 X2
1
(+)ı + 1 (.))))
tosp
(40)
where 0 ((06))))))
00 ). Let the equality holds and solve Eq. 40), we have
A =
[()} + 0.55 V (()
(41)
15

---

Published as a conference paper at ICLR 2025
A.3 UPDATE RULE FOR 0,
Note that we have
(0 0., VoJ + 5.)) + KT (pollpo.)
31
(μ m4) T [J.(O - 6.) + tr((E (Σ - E,)Vx + 5.))
+
1
tr tr( E) + (n m.) T Σ, ( - m.) + log
23,
Σ
where [ and VzJ + 5,) denotes the derivative w.r.t. fr and E taking at = p + 6 and Σ E, ōz., respectively. We
the above problem is convex with respect to μ and E. Taking the derivative w.r.t. and E and setting them to zero, we can obtain that
V V + 8.) + Σ,
Mc) = 0, (H
(42)
Bt
VxJ(0: + 6,) +
[ E 3- O.
(43)
2/3
Therefore, we obtain the update rule for 02 as
Pt- 4 3,E, [(: +.),
(44)
Σ +28 +
(45)
A.4 THE GRADIENTS OF J(0)
To obtain the gradients the reparameterized objective J(0) w.r.t. μ and E, we use the following theorem to show that only function queries are needed.
Theorem A.1 Wieerstra et 2014) The gradient of the expectation of an integrable function F(xx) under Gaussian distribution po == N(p, Σ) with respect to the mean and the covariance Σ can be expressed as
V(J(O)= = Epo E 1 (x F))(F))
(46)
VE) Ey (E- (xr 1x) - - -()))(())
(47)
B MINI-BATCH SABO
For the proposed SABO with mini-batch function query, the stochastic approximation of the gradients V (O,) and (z,(()) using Monte Carlo sampling are given as
N
M
ge
ΣΣ
E (I/) - (F)a v/)) F( (X,,
(48)
NM
j=1 1=1
M Σ
G 2N M
diag Σ. diag((ar' (o) - T 1
F=
x (X( - Fiuss (X,, v/D))
(49)
where x', denotes the j-th sample sampled from the distribution N(x pt: E,), and (X,, vo) denotes the i-th data in the mini batch dataset B', Then by setting 6, = [ xε; 2G
2E.G; }, the gradients
16

---

Published as a conference paper at ICLR 2025
Algorithm 2 Mini-batch SABO
Require: Neighborhood size p. learning rate Br, batch size M
1: Initialized 0g = (44. Eo)
2: for 0 to T do
3: Take i.i.d. samples z/ (N, 7) and set ærj = + E 2/ for E (I,...,N}
4: Sample a batch of data B";
5: Query the batch observations {< B',,,.., Fa B))
6: Set the gradient g, via Eq. (88 and set the gradient G², via Eq. 49
7: Compute = V G + 0.5| 2 g/1:::
8:
Compute 64, X Eigh and ox, = x -
2E.G; {I...., N};
9:
Take i.i.d. samples 2j ~ (N( for
10:
Set z, μr + 6n. + (E, + 8z, 2 2, for j E [1....,N];
11:
Sample a batch of data B:
12:
Query the batch observations (a)1; B) ..... F B)); Set the gradient via Eq. (50) and set the gradient G, via Eq. 51
13:
Set pe+1 = Mr
15:
Set E E,² 2,3,
16: end for
return 0r (NUT, Σr).
V J(O + 5,) and VzJ((e + 5t) can also approximated
91 NM
S (ay (F(x((( (X,, F(Pes (.).))
(50)
N M
G. = 2
diag
Σ [diag ((x, - (T) - TE,1 -1)
(F(zy; (X,, v:)) F(pes (X,, y.)i)]
(51)
where E; E, + SE P. = u4 + 8p,, 2y denotes the j-th sample sampled from the distribution
N(n p.. Σ.), and (X,, ys) denotes the i-th data in the mini-bated dataset B. Then we can update O by Eq. 21.. The entire algorithm SABO with a mini-batch function query is shown in Algorithm 2
C TECHNICAL LEMMAS
In this section, we introduce the following technical lemmas for analysis. The proof of all technical lemmas is put in Appendix E
Lemma C.1 Suppose Σ and Σ are two d-dimensional diagonal matrix and z is a d-dimensional vector, then we have [x < ||||||=|| and ΣΣ
Er El[r.
Lemma C.2 Given convex function F(x), for Gaussian distribution with parameters 0 (M, Σi }, let J(0) == [F(==)][(())], Then J(O) a convex function with respect to O.
Lemma C.3 Suppose that the gradient G, are positive semi-definite matrix and satisfies ET - G: Σ
bI. Then for algorithm and 2, we have the following results.
(a) The (diagonal) covariance matrix Ex satisfies
2b B.I., Ex
25 1111111
(b) The Frobenius norm for the covariance matrix E, satisfies EElle <
vdd
17

---

Published as a conference paper at ICLR 2025
Lemma C.4 For given o denote the approximated gradients of V (O.) and ((i) by gi and G₁ respectively. Then for Algorithm ] and Algorithm 2 if S Ld 3
then the perturbation satisfies,
11 S 2 l| and | || S
where is a positive constant.
Lemma C.5 Algorithm
suppose the gradient estimator ge in 1-th iteration as
= *F((m) + F((:))
(52)
where 2 ~ (O, Then gi is an unbiased estimator of the gradient V uu [I [F(x)]
Lemma C.6 In Algorithm 7
suppose the gradient estimator gt in 1-th iteration as
g. - -- ===(((( =F + +Zi F(ar)),
(53)
where 1). Suppose that Assumption 4.1 holds, p 3/ the gradient G. is positive semi-definite matrix and satisfies &I 3 G. 3 bl and Eo RI, where b, R 2 0. Then we have
Li
(1 2pr (d 4)²
E |
9.
(54)
2 2 3k)
where r' is a positive constant.
Lemma C.7 In Algorithum
2 suppose assumption 4.4 holds and the gradient estimator gi in t-th
iteration as
gi E, 22,32((F1 (F((+++ 2) F(u B)),
(55)
where z I). Then gf is unbiased estimator of the gradient Ep [F(x)).
Lemma C.8 Algorithm 2 suppose the gradient estimator in t-th iteration as
g. Š (F((F. + - -
(56)
where z ~ ~N(00,), Suppose that Assumption 4.1 and Assumption 4.4 hold, Ld G. positive semi-definite matrix and satisfies {1 G. - bl and Eo RI, where &, R 2 Then we have
2 the gradient
L2 - (d 4)2
2(d 4)=²
Σ 9
(57)
66(Σ 3k)
3
where r' is a positive constant, e² === =25 + 25B.
D PROOF OF THE RESULT IN SECTION 4
In this section, we provide the proof of the result in Section
D.1 PROOF OF THE PROPOSITION 4.2
Note that F(x) is a convex function, we have
F(μ)= = (())=)) < (F(((())))((())) J(, E).
(58)
Since F(u*) = J(, 0), follows that
F(u) F(1)) S J(n. Σ) - J))
(59)
where reach the conclusion.
18

---

Published as a conference paper at ICLR 2025
D.2 PROOF OF THEOREM 4.3
The update rule of can be represented as Pr41 B.E.g. Since F(x) is convex function, we have J(0) is convex w.r.t. 0 = {n. Σ+} by Lemma w.r.t. l we obtain
C.2
together with J(0) is c-strongly convex
J(O,) S J(H" + (0,) T
(Mr 14--M 1²) + x J(,))
Σ
2 | 1=11
(60)
Note that V ((,) V (z)( + VZJ((,) - have
+ ? =1lme -11111
J(O,) s J(, 00) +
(61)
Let A, J( E,) [ 0), we have
cBt
B.E[Al S E,E, I J(.)) (+ 2,
11+e - 1=11.
(62)
2
Note that
114- 16" 10'13,, E || 11 10"1(2,
= -I1e4 - 1e 1|2,1 - 111e - B. - 11 11,12,,1
(63)
= =Ilmet - 1=11 1/ || (1114t - 10 1/2/", 28 (p+ ,,, ( gi))
(64)
23.9. T (14- 11") (Eigi) gt-
(65)
Therefore we have
8, (Eigt) gb.
g. (m 1²)
23, (11 14" 1211 -111411 -x" ="'12,,)) +
(66)
2
According to Lemma
C.5 we have Eg: VnJ(O, + 6c). Then we have
E [(.)))(0)) 9:)² T (m- [²)]
[[(V ((,,) VnJ 5,))
( (Hu - --*)]
+ --))+55.) gi) T() 4²)]
(67)
< 1|m- 1= V [(O.) [(. + +5)1ll
(68)
1oel
(69)
$ DL,,
(70)
where the first inequality is due to the Cauchy-Schwand inequality, the second inequality is due
to || 41ll
||
< D and Assumption 4.1 the last inequality is due to Lemma C.4 and U2
max(2 2
E
[|,, 4rl E, ||r). Then we have
E V (0.)) [mu (m4-1²))
(71)
Ex [ (m: - -("==")=- + (V - (m:
T [²)]
(72)
<
E- ||||4: - 1e 112. || 11" -011 (:(Egg)))) gil + DLp,U,,
(73)
2B
where the inequality due to Eq. (66). Eq. (70). and Be 2 0. Note that
E (()) Σ,
< E V V. ( E S H E.
(74)
where the first inequality is due to Lemma C.1 and the second inequality is due to the Lipschitz
continuous assumption of the function J(Ø). Then substituting Eq. (73) and Eq. (74 into Eq. 62 and multiplying 3r on both sides of the inequality, we have
c pr 11 2,8 H E
B. S Blll 11 11
|1 nm x
2
(75)
+ DLLiUr + 3 || Σ 1tll
19

---

Published as a conference paper at ICLR 2025
We further obtain that
cgt
1e -=' -114411 - pe 10"11z,-11
Fe - pe 111
(76)
2
T-1
cBA 1 11"113
| - se || || 11 "=11
(77)
1=
+
I - 1e 1= E01 - PT 1¹
"²1lE, E 2
(78)
|14 1e 112..G.
11+4 141
+ 1120 -0
(79)
2
cB l| 1011
cBt
|
1 1=1 11?
+ 12, D1
(80)
2
DD
(81)
where the second inequality is due to the update rule of E, and | - -='l S D, and the third incquality is due to Cauchy-Schward inequality and G, I fT. Then we have
B S
2
D2
2H E.Ir + DIP.U + 8. 11 g.l1?
(82)
2H 2H Vd
+ DLp,U, + LE (1+ 2pr 2pr') + 4)2
< <1
2 Σ Bk
20 3x)
(83)
where the first inequality is due to Eq. 81 and Eq. 75 and the second inequality is due to Lemma
C.6 and | ler < R². According to C,3 (b), we have U2 S max
2v/a4
4ryd
(25 Di
8x)
25
9x
Therefore, there exists a constant t", when t > t" -.,1 S Ei Bx)
2v22
Denote Et'o
Arp.va
28 Eh-1
by constant r. Then if T > 1", we have
T-1
ES 1|p22
2H3VVd
L3.R3 (1-2(r1 (d (
T Σ E(A, <
T3
T
2 2
k=1 Bk
2 Et= k== 3x
(84)
T
D/2DLppd's
DLT
+
+ T3,
T
B,(26 1112E1111 1x)
Let Br = and Pt
Pg VIa
we can obtain that
E D2D2
2V/DLppo's V
DLT
Σ
[[A:]
(85)
T 1-0
TB
2Et
T3
0=
where C /d L R2 (1 (1+22 2pr")) (d + 2)2. Since we have ΣT 1 $ 1 log (T), we obtain
- Σ B( E.) J(u .0] = = Σ
E[A.] = 0 ( )
log
(86)
T
t=0
where we reach the conclusion.
Remark D.1 In Theorem 4.3 if we set 8 (1) and p 0 )r), then the third term in right-
side of Eq. 84 has convergence rate of O Lo set 3 O(1) and p O1), then
20

---

Published as a conference paper at ICLR 2025
the third term in right-hand side of Eq. (84) has convergence rate of O( (T))) since have
E 3 S 2VT. Then we obtain
T-1
T-1 Σ
1
log T
1
E [[ Σe) J(H 00 = T
B[A:] = O
+
(87)
T
T
T
VT)
1=
1=0
This implies T Et- E [14++ Ex) J(x", 0)] O (}
D.3 PROOF OF THE PROPOSITION
Since the datasets and are i..d. sampled from one data distribution P(X.y) y). We have ((xx))r(F((; (X, y))l = (x: [3]] = E[F D)J. We obtain that
(2; | -
(3) BF D)1 2 (88)
D.4 PROOF OF THFOREM 4.6
Note that for SABO with mini-batch function query, the update rule of μ can be represented as M4+1 H4 D.g. Let B, = J(4. Σ,) -J(H" 0). then by using Eq. (61). we have
cBt ||
B. < B, ndr (O.) ( (m -+]"] B (0.)
12
(89)
2
cB₁
BE J( T (1:: [u==)")] 23, H E
1|
/ 11?
(90)
2
where the second inequality is due Lemma C.I and Lipschitz continuous assumption of the function (0). Note that
p4: pe. x-- ||++1 11 1|
111l - 11" ||3 111ee - Br - 10111 Σ,
(91)
111se - 11 ||'51 - (1114 - 1=11 """ss-- 115,1- -2e (mt - 1= pg,)())+ +
(Eig..g)) gh))
(92)
2,09. (Mi - w²) (Zii))))) gt.
(93)
It follows that
g. (1 11) = 1
31 (Egi)) gt
2,3 (11p 11" 13113,-- 11 11" 11,.))
(94)
1
Ι 23.
(11 - 1 1²1ls, "| || - 1 || 1) 3r
||
gt
(95)
where the inequality is due to 3g 2 0 and Lemma C.I V [0, + 5.). Therefore
According to Lemma
C.7
= we have Ege
[V g.) T..TT(H.) (m1 =1")]
[ [0,
[="] + BB 6.) - (m [²]
(96)
< I|me 1 (l - [n. + +.)ll
(97)
< 6
(98)
s DLp
(99)
where the first inequality is due the Cauchy-Schwarc inequality, the second inequality is due to
11 < D and smoothness assumption of the function J(0), the last inequality is due to Lemma
C.4
and U.- = max(2v 2 || 4r| E.]l). Then we have
F. (O,(( T (14: - |1)
(100)
= Ez [g. (M4 - -1²) + (V ((.)) T [1")]
(101)
1
< Ex pr 4 w"'1e,-- || 4 [|,,,1]] + 3, Σ
|EE|Et
gil2 DLp,U
(102)
23,
21

---

Published as a conference paper at ICLR 2025
where the inequality is due to Eq. (95) and Eq. (99) multiplying Be on both sides of the inequality, we have
Then substituting Eq. 1022
into Eq.
900 and
cBt
[. S Bllm 10 1""
|1 1
11
14
12
+
23 H
EEllr
(103)
+ +DLpUU +
| |B
Σ g: 12.
We further obtain that
cBt
p4 1e 1=" x.² - -111411 - 11 11"12 1لا
14 - 1 1==1?
(104)
2
T-1 1
cB:
114 - 1e" 10'12,- -114--1 11 11'1 |ل
1/ - 112
(105)
2 t=
2
[100 1=1 ""1 - -1|ee 1e"
1=11
(106)
T-1
c
| 1e $1 113....
111|
11 11
+ 10 11
(107)
2
2
cBt || 11 11
cBt
||
1 1=1
+ 120 De
(108)
2
2
(109)
where the second inequality is due to the update rule of E, and ||,, -='l inequality is due to Cauchy-Sehhe Schwarz inequality and G. 1 IT. Then we have
S D, and the third
B.E[BA] &
10
11 2 +
2 E, 1| + DL + 8 E gill
(110)
2H Vd DLP.U,+ 28, Σ
(1 + 4)
E 1| +
2 Et km1 BB
3
1=0
(1 + 2pr') (dd + 4)3 Σ 1|F
(111)
6E(Σ 1 3k)
T-1
2 Et= 3k + DLp.U,+ + 2,37 + 4)d+e2
2H
< 12
D2 11 +
Σ
3(25 1 3x)
1=
(1 + 2pr") + 4)2
(112)
6E( B&)
where the first inequality is due to Eq.
(003 and Eq. (109)
the second inequality due to Lemma C.3
(b) and Lemma C.8 and the third inequality is due to E
lle S Rd and Lemma C.3 (b). According
to C.3 (b), we have U. S max(
2vZat
4rv
Therefore, there exists a constant 1*,
(2C E/ BL)
35ΣT DE)
when 1. > 1" U, <
2
Denote Ei--1
Arpivd 28 &h=ii Be
by a constant T. Then if > 1",
(28 E1_ A=)
we have
1 1D
2H3.Vd LZR (1 + 2pr') + 3)
Σ
E[B.]
Tie
T
28 E1 8k
+
39 Ei_0 Bk
t=
(113)
T
2 2/2DLp,di
T-1
Σ
23 + 4)d
DLT
-
+
+ TB.
T
3(2 B4)
t=0
22

---

Published as a conference paper at ICLR 2025
Let 3 B and Pt p. have
1 |
2Hvd
13 + 2pr +
+4) 4)2
E[B[]
T
TB
T
25t
(114)
T-1
2.2
2(d + 4)
DLL TB
)
T
V2
Vt
T
3
Since we have Et=1 7
1
S 1 + lTg(T) and
Σi=1 7
S
2v 2v
we obtain
1
T-1
{
log T
1
T Σ E
D,) E.)
Σ
E[B,] 0
+
(115)
T
vT)
1=
where we reach the conclusion.
D.5 PROOF OF THROREM 4.8
Using PAC-Bas AAC-BBaesi bound (McAllester 1999) and following (Dziugaite & 2017, for any prior distribution p and any posterior distribution q that may be dependent on finite dataset S, where data set S with M i.i.d. samples drawn from data distribution P(X,v), we have
(T<al)p) + log( )
Vg. Bg(m) (p( (X, vi)l S Byta) F(x; +
(116)
2(M -) 1)
Set the posterior distribution as q= po = : Σ). Denote the set MM))) = {8 | KL pop) KL(ps] po+s) S p²). We can choose .M(). Then, we know that for the prior distribution the following inequality holds with a probability at least 1 K.
KL(pollp) + log( M
E E (m) [E( (F(x; (X, s pp)( [F(;SS] +1
(117)
2(M - 1)
Note that for any density p, q, we have KL(pllg) 2 O. Thus, we know M(() C(0). It follows that
KL (pp) + log( 41
(oo(#) x)]] [Fao))
(118)
2(M 1)
NT.(polloo+b + log( M
max ps ((x 6EC(O)
K
6EM(0)
2(M
(119)
p² + log( M
max ps [F(x;)]] SEC(O)
(120)
2(M
Note that F(x; (X, y)) is convex function w.r.t. æ, we know that Er(x [F(w; (X, v))] is convex function w.r.t. It follows that
(F(X [x)) (X, Ex(x.)) [Fu E (F(E
(121)
(pp [r [f (X, y))l]
(122)
Finally, we know that with probability of least 1 K, the following inequality holds.
p² + log( M 2(M 1)
Ep(x,)) (F(x; max Epo+s [F( Sec(o)
(123)
E PROOF OF TECHNICAL LEMMAS
In this section, we provide the proof of lemmas in Appendix C Note that Lemma C. and Lemma 2 can be directly obtained by Lemma B. and Lemma B.2. in (Ye et al. 2024). respectively.
23

---

Published as a conference paper at ICLR 2025
E.1 PROOF OF LEMMA
(a): Since we have 2 D;= + 2.. We can obtain that
Σ, + 2b3 - -. +
2.BII.
(124)
Summing it over t = 0, ...... T 1, we have
T
T
ΣΦ + 2b
3 = Σ
+ 2
3T..
(125)
1=1
Therefore, we have
ET =
(126)
2b Et=1 3,1 + Σ
25 _ |= BBI + E
(b): We have
1
Vd
|E/|E I
(127)
2 2 3 + E
25 2 311
2 Σi= 33.
F
E.2 PROOF OF LEMMA
C.4
In Algorithm ! and Algorithm
for given 0,, the perturbation ö, satisfies
pE.g
PV2Σ Σ g!
0p. x Eig' =
(128)
0.5 9f
| gill
Therefore, we have |1ōm |1 S pV/2 E ||r. For òΣ,, we have
GE,G E,
E.
85.- XE, 2G I- E.
(129)
Note that 3
2p EG.
Therefore, can obtain that
2p |
|0 IF I |Eelle
(130)
If dd there exist constant r> 0, I - > & holds. Therefore we have ||83, || S
2pr [. P.
E.3
PROOF OF LEMMA C.5
We have
Eg [g/1 = Eg E FF + Σx 2)] - Ex E., =F()))]
(131)
= Eg E F( + Σ;²²]
(132)
EnnN E.) Er (x F())
(133)
= V [F(x)]}
(134)
where we reach the conclusion.
E.4 PROOF OF LEMMA C.6
Denote the diagonal elements of Σ and Σ by and ã respectively. Then have
اا o. t o (F t o 22,) - 2
(135)
24

---

Published as a conference paper at ICLR 2025
Note that Σ =Ep' -2G',, we have of or. Since we have
N
g. = E
It.
gr,ll
(136)
N j=1
j=1
It follows that
N
E
E|
gtli
E
00.-
0z + 6 02,) F(
(137)
N
j=1
N
Σ
E
||
(F
o7 0z2) F(
(138)
/=1
1 N
Σ
E
[1>]|
(139)
Note that
Σ. E, + dz, E, E
(140)
Note that 3 S
2p |EG, IF Then if p o 2pr' or holds. Therefore, we have
vd there exist constant r' 0, the inequality ã. s
+ 2pr'
| S + +1+ 2pr I
(141)
100 Ilmin + 2(E Ba)E
where I| mmmmn denotes the minimum element in the input. Noticed that B_ [||=||1] d + 4 as shown in (Nesterov & Spokoiny 2017), we obtain
L2p + 2pr')( 4)2
gell2
(142)
25(2)-1 Bx)
where we reach the conclusion.
E.5 PROOF OF LEMMA
We have
E'gll = E[ 2 =F + 2) B|z, 1 F F B)]
(143)
EE E 2F + x z;) E, E_ x FF D)1
(144)
E2|E, =F Σ 2)]
(145)
-Enn((u E.)
E 1 14: F(z))
(146)
Vukpo, (z)),
(147)
where the second equality is due Proposition 4.5
E.6 PROOF LEMMA C.8
Denote the diagonal elements of Σ and Σ by and o respectively. Then we have
/ gt.
2 t o, (F न o B); F)
(148)
Note that --1 1+1 Σ,1 2XG we have o, S o, Since we have
E b
gf
B
gh.
Σ 12
(149)
N
N
25

---

Published as a conference paper at ICLR 2025
It follows that
N
g
E
gel2
S
E
oō,²
0z + + @ 2): - F(Ae; BB)]1
(150)
N
j=l
N
-
Σ
||
o 02; F( B3)
(151)
N
/=1
1 o zy11² + |3
$
E
||
(
1
(152)
where the third inequality is due Proposition 4.5 Since Σ, - 3-
GE and 2 |E
2p
Then if
Va have 2
there exist constant r' > 0, the inequality ã. S ot + 2pr a holds. Therefore,
1 + 2pr'
1o s 2pr')
I
(153)
100 min + 2(E Bx)
where -| mm denotes the minimum element in the input. Noticed that E=11|2|||| d + 4 as shown in (Nesterov & Spokoiny 2017), we obtain
B B
1 <
E
(1 + 2pr') L
<||>/|
2ca
||2
(154)
N
3
1 (1 + 2pr') + 4)²
2(d + 4)e²
+
(155)
69 65(E==1 3k)
3
where we reach the conclusion.
F UPDATED RULE UNDER TRANSFORMATION
To avoid the scaling problem, we can employ monotonic transformation for the objective F(x), i.c. ((F(w))) f(w)) where f and â denote mean and stand deviation of function values F(x,), j ..... N. Then by applying this rescaling strategy, the update rule for μ4, and E, in (-th iteration can be written as
N
F(xr,) ft - (o:) (x)
Po+ = ur
S. E
(156)
N
j=1
B1
F(x,) N
Dx1
diag
E "'"(diag((x; (2)) (ao) TG,))
(157)
1=1
where Σ, = E, + Sz., po: = Mr + 8 and Φ, denotes the j-th sample sampled from the distribution
N(x pr, Σ.).
G ADDITIONAL MATERIALS FOR SECTION 6
In this section, we provide additional experiments and more implementation details of Section 6
26

---

Published as a conference paper at ICLR 2025
G.1 SYNTHETIC PROBLEMS
The four numerical benchmark test functions employed in Section 6.1 are listed as follows:
26 1)
F(w)= =
10
(158)
i=1
F(x) Σ
-(111)
10 2-1
x
(159)
2+4 i-1
F(w) = V
22
(160)
1=1
F(x) = sin?(Trw)) + Σ [w 1) + 10sin + 1)) + (wa 1) sin? sinn((2wwa))
(161)
where W,
E {1. dI.....d.
Test functions 158 161 are called the ellipsoid function, 1 -ellipsoid function, different powers function and Levy function, respectively.
Implementation Details. For all the methods, we initialize from the uniform distribution Uni 1], and set Eg I. For the INGO, BES, and SABO methods, 0.1. According SABO method. We set the spacing setting from He et al. (2020) for the MMES method. We then assess these methods using varying dimensions, 1.c., d E 200, 500, 1000). For d = 200, we assess these methods using varying sample sizes, i.., E {10, 50, 100). The mean value over independent runs is reported.
fixed step size of assumption in Theorem 4.3 set م 100/ / T for the proposed for the BES method and employ the default hyperparameter
Results. Figure and 3 show the results four test functions with problem dimensions 200 and d = 1000, respectively. Figure 4 and [ show the results on 200-dimensional test functions with sample size N = 10 and N 100, respectively. Combining these results with the result from Figure we observe consistent performance for the proposed ASBO method. It achieves a similar convergence result the INGO method, they have the same theoretical convergent rate. In some cases, i.e., 3 (d) and Figure|[ih (d), it converges slightly faster than INGO. The CMA-ES method and MMES method both work for cllipsoid and different powers functions, but fail in ( -ellipsoid and Levy functions.
most cases, they converge slower than INGO and SABO. With a large sample size, ie., N 100, the CMA-ES method can maintain fast converge rate according to Figure The BES method fails to achieve high precision
test functions. It diverges in ellipsoid, 1 ellipsoid, Levy functions, and only achieves a low precision in the different power functions. These results demonstrate the superiority of the SABO method in optimizing high-dimensional problems, and verify our theoretical convergence results in Section
PIES
P965
PMES
MHES DE5
165
DES
DE5
RCO
ELCO
Reooen. 1X300
(a) Ellipsoid.
(b) l -Eliipsoid.
(c) Different Powers.
(d) Levy.
Figure 2: Results on the four test functions with problem dimension d = 200 and N 50.
27

---

Published as a conference paper at ICLR 2025
24
0.4
CKC-5 FRES
CHi-65
CRABS
D44-15
107E5
2t5
$480
5450
5450
23
10
(a) Ellipsoid.
1 -Ellipsoid
Different Powers.
(d) Levy.
Figure 3: Results on the four test functions with problem dimension = 1000 and N = 50.
20
2.5
3.0
-15
CHAESS
CRAES
-1.
CHARS
-25
IN50
SABO
5480
5480
SARD
(a) Ellipsoid.
(b) -Ellisood.
(c) Different Powers.
(d) Levy.
2
Figure Results on the four test functions with problem dimension 200 and N 10.
LO00
BED
R00
RG0
-10
5A50
$AB0
SABD
5A20
tratton Tixdo)
kendon.
Bensoon
TIX10)
(a) Ellipsoid.
(b) 1 -Ellipsood.
(c) Different Powers.
(d) Levy.
Figure 5: Results on the four functions with problem dimension 200 and N 100.
H ADDITIONAL RESULTS ON SYNTHETIC PROBLEMS
We conduct additional experiments to compare the proposed SABO method and GFM method Lin et al. al.22), For GFM, we employ default hyperparameter setting from|Lin al. (2022). We set its smoothing parameter d 0.2 and conduct experiments on the step-size over (0.001, 0.0005, 0.0001). The initial point is set the same as SABO.
The results are shown in Figure 6 with problem dimension d = 200 and N = 50. The GFM method can converge slowly for the Ellipsoid problem. It fails in the 1, -Ellipsoo problem and cannot achieve high precision for Different Powers and Levy problem. This shows that it could be challenging for GFM optimize non-smooth or -igh-dimensional test functions without adaptively updating mean and covariance. The proposed SABO method takes advantage the second-order information, which gains great acceleration for solving these problems.
28

---

Published as a conference paper at ICLR 2025
Table Performance (%) on SST-2, AG's News, MRPC, RTE, SNLJ, and Yelp P. datasets. We report the mean and standard deviation over 3 random seeds. The best result across all groups is highlighted in bold and the best result in each group is marked with underlined.
Methods
SST-2
AG's News
MRPC
RTE
SNLI
Yelp P.
Zero-shot
79.82
76.96
67.40
51.62
38.82
89.64
Dimension d 200
GIBO TurBo
83.53+0.15
75.79
79.21
53.07
38. 38.7340.09
89.63 89.63.0008
83.30
79.01 1166
69.5948.51
46.57
00.69 40.27 40.27
90.1610.19
SABO
87.88 40.53
82.22 10.41
79.35
53.67
40.72 10.15
91.50
Dimension d 500
GIBO
83.49.0.09
15.7010.05
79.03
52.9510.17
38. 38.711 10.16
89.65
TurBo
84.52
80.03 1.97
12.34
48.01 10.59
38.82 10.34
10.40
SABO
87.31
82.65
79.62+0.07
53.55
42.29
91 91.83
22.48
Dimension d
1000
GIBO
83.45
75.67
79.15.0.0
52.9540.17
38.87
89.65.0.04
TurBo
85.90
82.36
77.30+0.86
50.30
39.87 1.00
90.1440.20
SABO
87.96 10.83
82.77 10.41
79.68 20.23
53.31
40.32 00.27
91.96 10.41
-1.
-3.
0.001
SPM
GRM 0.0e5
3PM FiS0ES
GPM 0.00
DTN 0.0001
GIN 0.000
-15
28
(a) Ellipsoid.
(b) 1 -Ellipsoid
(c) Different Powers.
(d) Levy.
Figure Results on the four test functions with problem dimension 200 and N
H.1 ADDITIONAL RESULTS ON BLACK-BOL -BX PROMPT FINE-TUNING
We conduct an additional experiment on the black-box prompt fine-tuning task to compare the proposed SABO method with high- high-ddmeensionl BO methods, i.e., TuRBO (Eriksson et al.) 2019) and GIBO (gguyen et al. 2022) methods discussed in Section We employ the default setting of TuRBO- from He et al. (2020) for the TuRBO method, and the default setting from Nguyen ett al. (2022) for the GIBO method. The results six benchmark datasets reported in Table 2 According to the results, the SABO method consistently outperforms these two baselines, highlighting its effectiveness.
H.2 SYNTHETIC IMAGE CLASSIFICATION PROBLEM
We conduct experiments synthetic image classification problem to empirically evaluate the per- formance of the proposed mini-batch SABO method. Specifically, we apply black-box optimization methods train model to classify the images accurately. Moreover, following Foret al. (2021). we conduct additional experiments on the noisy label setting. Particularly, we train the model on corrupted version of the Fashion-MNIST dataset, where some of its training labels are randomly flipped according to different noise rates, while the testing set clean. To construct problems with different dimensions, we first adopt UMAP (MeInnes al. 2018) reduce the dimension of Fashion-MNIST to 8 while preserving the class discriminability (Sagawa & Hino 2022). and
Foret
then employ fixed randomly initialized matrix P R to project the extracted features
29

---

Published as a conference paper at ICLR 2025
Table 3: Performance (%) on Fashion-MNIST dataset with noise labels. The best result across all groups is highlighted in bold and the best result in each group is marked with underlined.
Methods
noise=0%
noise=20%
noise=40%
noise=60%
noise=80%
Dimension d 100
CMA-ES
76.68 0.44
77.25
75. 75.71
70.81 11.00
57.86113.65
MMES 76.20
0.33
74.46-t..22
71.12#2.224
15.992-1.30
BES
76.26
67. 67.60=Eo.72 73.5
55. 55.14-6.20
45.65=4.33
INGO
76.68
75.16:bo.55
71.26:to.74
61. 61.70
46. 16.755.1.38
SABO
78.10
77.41 77.41:Lo.68
77.10
73.41 1..33
66.45 1o.43
Dimension d = 1000
CMA-ES
76.75
73.21 73.21+0.52 04.85=b0.06
67. 67.32
50.00=t..9
MMES
75.85 32.39
73.73
72.51
56.60 56.60=2.772
BES
76. 76.18
72.45-t0.44
66.6442..99
58. 58.74+1.50
46.99..4.30
INGO
7o.73
71.8
69. 69.7510.73
63.18 14.04
41.80111.36
SABO
76.87
77.73 to.85
74.97
73.81 1.26
61.96
d-dimensional space. After preprocessing, linear layer is used classifier. Therefore, the total number of the trainable parameters d 10 d.
Datasets. Fashion-MNIS (iao et al. 2017) is a image classifications dataset. It contains 60, 000 training samples and 10, 000 test samples, each representing 28 x 28 28-pixel grayscale image of fashion items from 10 different classes.
Implementation Details. For fair comparison, set the same population size, number of batch samples, and the initialization for CMA-ES (Hansen) (006), INGO (Lyu & Tsang, 202T). BES (Gao & Sener, 2022), and SABO. The population size and the number of batch samples N 100 and Eo 0.5I. For BES, INGO and SABO methods, we search the learning rate 3 over {0.1, 0.5, 5).. Moreover, we perform grid-search on over {100, 500, 1000, 5000} for SABO. We employ the default hyperparameter setting from He et al. (2020) for the MMES method. For the BES method, we perform grid-search on the spacing over {0.1, 10). The cross coss-entropy loss is used as the training objective. All experiments are repeatedly run with three independent seeds and the mean and standard deviation are reported.
to
2048, respectively. The Gaussian distributions are initialized with μ40 = 0 and
Results. Table 3 shows experimental results Fashion-MNIST dataset with different d and different noise rates. We can see that the SABO method consistently outperforms all baselines across different noise rates and dimensions, highlighting its effectiveness. These results show that the proposed SABO method can achieve good robustness performance and demonstrate the effectiveness of the proposed SABO method in improving model generalization performance.
I DISCUSSION WITH OFFLINE BLACK-BOS OPTIMIZATION
The typical black-bor optimization problem we studied in this work can also be called the online black-box optimization problem. Since we have access to the objective function F, the problem can be solved in an online iterative manner, where each iteration the solver proposes new æ and queries the objective function for feedback in order inform better solution proposals the next iteration.
The offline black-box optimization (Chen et al. 2022 Qi et al. 2022) is different from the research line of standard online black-box optimization. In offline black- box optimization, access the true objective F is not available. Instead, the offline black-box optimization algorithm is provided access to static dataset D {z,, F(x,)) } of the variable 2; and its corresponding objective value F(x,). Therefore, the basic settings of offline black- back-bbx optimization and online black-box optimization are different.
30

---

Published as a conference paper at ICLR 2025
Moreover, the challenges of offline black-box optimization and online black-box optimization also different. Offline black-bor optimization focuses on producing query candidates by a surrogate model trained with prior static dataset (Trabucco et al., 202T] Kumar & Levine 2020). The goal is to produce a good query set based on the fixed model at one time without considering query feedback update, exploration and exploitation balance in the long term. Along this line, Kumar & Levine (2020) proposed a model-based offline optimization by training a conditional generative model that conditions the objective value. In Fannjiang & Listgarten (2020), the authors formulated the problem as non-zero-sum game and proposed an alternating ascent- ascent-descent algorithm for model- offline optimization. Trabucco et al. (2021) proposed the conservative objective models, which presents technique similar to adversarial training that avoids overestimation of out-of-distribution inputs. In contrast to offline black-box optimization, standard online black-box optimization needs balance exploration and exploitation, which focuses on long-term convergence performance. As a result, offline black-box optimization is not suitable for our online prompt fine-tuning tasks.
J DISCUSSIONS ABOUT THE SOCIETAL IMPACT AND LIMITATIONS
This work only focuses on black-bo optimization in deep learning, so it has no negative societal impact. The main theoretical analysis in this work focuses convex black-box functions. It is technically challenging to analyze non-convex cases considering both the black-box nature and the sharpness-awes aware properties, and we leave this one of our future work. Additionally, the SABO method employs a standard Monte Carlo sampling for gradient approximation. Other sampling techniques might be more efficient, but those are out of the scope of this work. We will study it in the future.
31


Reviews:
[{"review_id": "1codtv28Hn", "reviewer": "Reviewer_SM7t", "summary": "The authors strive to introduce SAM to the black-box optimization algorithm, and propose a new algorithm called Sharpness-Aware Black-box Optimization (SABO). SABO reparameterizes the objective function using its expectation over a Gaussian distribution and iteratively updates the parameterized distribution based on approximated stochastic gradients of the maximum objective value within a small neighborhood. The authors provide theoretical guarantees for SABO's convergence rate and generalization bounds. Also, they give empirical experiments to validate its effectiveness in improving model generalization performance on black-box prompt fine-tuning tasks and synthetic numerical problems.", "questions": "See Weakness", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is clearly written, well organized and easy to follow.\n2. I think the whole topic is intriguing and worthy to probe, and the authors give some interesting insights.\n3. It is valuable to find that the proposed method could be effective in prompt tuning.", "weaknesses": "1. My primary concern is the motivation regarding the introduction of SAM in black-box optimization. In other words, can we safely use the proposed method in black-box optimization? The implicit premise of SAM relies on the smoothness of the mapping function. However, black-box optimization may deal with highly complex, non-smooth, or potentially noisy objective landscapes, scenarios much more complicated than optimizing neural networks. In my opinion, it is crucial for the authors to clarify the scope of which minimizing the maximization of the neighborhood region is appropriate for black-box optimization.\n\n2. I noticed that in the algorithm, the authors use two different samples to separately calculate the ascent and descent gradients. Could the authors give some explanations here given that we always keep the same batch in SAM?\n\n3. The essence of SAM involves two main steps: first, a maximization step using gradient ascent based on the current parameters with a step size of rho/||g||; and second, a minimization step using gradient descent based on the maximized parameters with a step size equal to the learning rate. What are the results of applying this procedure in the current black-box optimization?\n\n4. The convergence analysis mostly relies on the assumption of convexity of F(x), which I think could be less useful.\n\n5. Some minor mistakes: (1) Line 121, SAM is proposed by [Foretet al., 2021] not [Kwon et al., 2021].\n(2) Eq 6. nabla_F(x + epsilon_t) should be rewrite as nabla_F(x)|x = epsilon_t", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2ncdNgeKLf", "reviewer": "Reviewer_xCwT", "summary": "This paper combines ideas from sharpness aware minimization (SAM) in machine learning with black-box optimization problems to propose a new algorithm called Sharpness-Aware Black-box Optimization (SABO). The goal of SABO is to improve the generalization performance of models by finding flat minima in the loss landscape, which are believed to lead to better generalization. The authors provide theoretical analysis of SABO's convergence rate and generalization bound, and they demonstrate its effectiveness through experiments on synthetic problems and black-box prompt fine-tuning tasks.", "questions": "- in the setup on line 177, you claim that for computational consideration you can assume the search distribution to be Gaussian. Is that a fair simplification? How sensitive is SABO to this choice of distribution and would it make more sense to sample the local parameter space in some way that captures the nature of the posterior rather than with a naive Gaussian?\n - related to above (line 180), is it fair to assume that the covariance matrix is diagonal. This seems optimistic and is essentially assuming no correlation between parameters, correct? And then your perturbations $\\delta$ also have diagonal covariance. I understand that, as you point out in line 195, removing this assumption would make the problem computationally substantially more difficult.  Theoretically, how much of a sacrifice does this assumption make? and are there any other means you can use to not lose this amount of information?", "limitations": "", "rating": 10, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This is an interesting paper that combines ideas from sharpness aware minimization (SAM) with black box optimization. SAM has already proven to be a very useful technique to improve generalization in training ML models and the authors present an intuitive motivation for applying these ideas to BBO. SABO is a creative combination of SAM techniques and black box optimization methods. \n\nThis paper has a strong theoretical analysis of SABO, including convergence rate and generalization error bounds. These theoretical results are then empirically validated on synthetic and real-worl black-box prompt fine-tuning models. \n\nThe paper is very well-written and logically structured. The authors do a good job motivating their approach and everything is presented in a clear understandable manner.", "weaknesses": "Overall, I see no major weaknesses for this paper and some of these points raised here are covered in the questions below which might clear up these apparent weaknesses. For example, in eqn (8) there is a dependence on the parameter $\\rho$. The performance of SABO would be sensitive to the neighborhood size $\\rho$ in (8) and tuning this parameter would be critical for successful application of this technique. It would be nice to see methods which can automatically adapt this parameter in a useful way to reduce dependence on manual tuning. \n\nThe authors do not mention in detail the increased computational cost of the sharpness-aware updates in SABO. One way to decrease computational cost, the authors assume the covariance matrix $\\Sigma$ is diagonal. This seems like a fairly naive assumption and one I would assume is too simplistic in general. To address this problem in SAM for traditional ML settings, variants of SAM have been introduced. Could similar techniques be applied here?\n\nThe authors focus on Gaussian distributions for the search distribution. Is that a fair simplification? How effective or sensitive is SABO with other types of distributions that are likely to occur for parameters; e.g. heavy-tail distributions, or other posteriors that are more informative.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "y8tVuLPuh2", "reviewer": "Reviewer_WkhT", "summary": "The paper introduces the Sharpness-Aware Black-Box Optimization (SABO) algorithm, enhancing model generalization in black-box optimization tasks by incorporating sharpness-aware minimization principles. Unlike traditional methods that may lead to poor generalization by focusing solely on training loss, SABO optimizes a Gaussian parameter distribution, finding \"flat\" minima that improve robustness. Through reparameterization and stochastic gradient approximation, SABO adapts Sharpness-Aware Minimization (SAM) for use without gradient information, making it suitable for black-box settings. Theoretical results demonstrate SABO's convergence and generalization bounds, and empirical evaluations on synthetic problems and prompt fine-tuning tasks show that SABO outperforms existing methods in high-dimensional settings, positioning it as a powerful tool for black-box optimization in machine learning.", "questions": "Please see weakness", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper is novel in that it extends sharpness-aware minimization (SAM) principles, typically used in gradient-based settings, to black-box optimization where gradients are unavailable.\n- This paper is supported by rigorous theoretical analysis, including convergence rates and generalization bounds in both full-batch and mini-batch settings. \n- The empirical results highlight SABO’s practical value and potential to improve generalization in real-world applications where direct gradient access is unavailable.", "weaknesses": "- Due to its reliance on iterative updates to a Gaussian distribution, along with stochastic gradient approximations and KL divergence constraints, this method may incur higher computational costs per iteration compared to some existing black-box optimization methods, especially in high-dimensional settings. A discussion of the time complexity for various black-box optimization algorithms would strengthen the paper.\n\n- This paper introduces additional hyperparameters (e.g., neighborhood size for KL divergence) that require careful tuning to achieve optimal performance. Discussing the sensitivity of these hyperparameters would improve the analysis.\n\n- Although the proposed method is evaluated on prompt fine-tuning tasks, the backbone model used in the experiments may not be sufficiently representative. Evaluating it on a larger model, such as LLaMA-7B, would provide a stronger assessment of its effectiveness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kdoHJbXISs", "reviewer": "Reviewer_vnYS", "summary": "This paper studies Sharpness-Aware Minimization in the context of black-box optimization. It introduces Sharpness-Aware Black-Box Optimization (SABO), which is the first to design a sharpness-aware minimization strategy specifically for black-box optimization. The key contributions include the formulation of the SABO algorithm, convergence results, generalization bounds, and extensive empirical validation through experiments on both synthetic benchmark functions and black-box prompt fine-tuning tasks.", "questions": "- Could you provide a table showing how selecting the neighborhood size $\\rho$ affects both convergence and performance?\n- What specific $\\rho$ would you recommend to ensure stability?\n- Could the authors include a comparison of computational usage against other methods in Table 1?\n- Could the authors provide a comparison of your theoretical and empirical results with the paper Lin et al. [2022]?\n- See the Weakness part.\n\nTianyi Lin, Zeyu Zheng, and Michael Jordan. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems, 35:26160–26175, 2022.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written and easy to follow.\n- The proposal of integrating SAM techniques into black-box optimization is interesting. They show clearly how to achieve the update algorithm. The paper provides proofs for the convergence rate and generalization bounds.\n- Comprehensive experiments are conducted on synthetic benchmarks and real-world tasks (black-box prompt fine-tuning for large language models). Results show that SABO outperforms other methods.", "weaknesses": "- The paper lacks evidence that SABO can find flat minima, even though this is their motivation for improving model generalization.\n- The paper lacks a strong motivation for why we need Sharpness-Aware Minimization for black-box optimization, aside from the fact that it may help improve generalization. Could the authors identify the problems that existing black-box optimization methods encounter and demonstrate how SABO addresses these issues?\n- Assumption 4.1 is narrow because it includes both L-smoothness and H-Lipschitz conditions; typically, we only assume one of them. For example, the simple function $f(x) = x^2$ satisfies L-smoothness but does not satisfy H-Lipschitz.\n- In Theorem 4.3, the assumption is too strong for real applications in neural networks. The result in Lin et al. [2022] is more general.\n- Theorem 4.6 is not strong because the assumptions are overly restrictive, which limits the practical applicability of this theorem.\n- The empirical convergence results of SABO in synthetic problems do not show much improvement over INGO.\n- The empirical results in Table 1 are not very significant, showing only around a 0-1\\% improvement, even for datasets with low accuracy such as RTE and SNLI.\n\nTianyi Lin, Zeyu Zheng, and Michael Jordan. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems, 35:26160–26175, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)