Adaptive Stochastic Gradient Algorithm for Black-box Multi-Objective Learning
Authors: Feiyang Ye
Yueming Lyu
Xuehao Wang
Yu Zhang
Ivor Tsang
Venue: ICLR 2024 poster (2024)
Keywords: Multi-Objective Optimization
Black-Box Optimization
Black-Box Multi-Objective Optimization
Primary area: optimization

Abstract: Multi-objective optimization (MOO) has become an influential framework for various machine learning problems, including reinforcement learning and multi-task learning. In this paper, we study the black-box multi-objective optimization problem, where we aim to optimize multiple potentially conflicting objectives with function queries only. To address this challenging problem and find a Pareto optimal solution or the Pareto stationary solution, 
we propose a novel adaptive stochastic gradient algorithm for black-box MOO, called ASMG. 
Specifically, we use the stochastic gradient approximation method to obtain the gradient for the distribution parameters of the Gaussian smoothed MOO with function queries only. Subsequently, an adaptive weight is employed to aggregate all stochastic gradients to optimize all objective functions effectively. 
Theoretically, we explicitly provide the connection between the original MOO problem and the corresponding Gaussian smoothed MOO problem and prove the convergence rate for the proposed ASMG algorithm in both convex and non-convex scenarios.
Empirically, the proposed ASMG method achieves competitive performance on multiple numerical benchmark problems. Additionally, the state-of-the-art performance on the black-box multi-task learning problem demonstrates the effectiveness of the proposed ASMG method.

Published as a conference paper at ICLR 2024
ADAPTIVE STOCHASTIC GRADIENT ALGORITHM FOR LEARNING
BLACK-BOX
Feiyang Ye! Yueming Lyu Xuehao Wang', Yu Zhang 1,5, Ivor W. Tsang233.4,
DDeaarmeet of Computer Science and Engineering, Southern University of Science and Technology AAstrallinn Artificial Intelligence Institute, University of Technology Sydney $ Centre for Frontier AT Research, Agency for Science, Technology and Research, Singapore " "Institute of High Performance Computing, Ageney for Science, Technology and Research, Singapore "Shanghai Artificial Intelligence Laboratory
6 "ccoool Computer Science and Engineering, Nanyang Technological University [feiyang, ye. sts, xuehaoxangfi, yu. zhang ust J0gmail com {Lyu.rueming Yueming, Ivor Ivor_ 8sang) a- aaa..r.......... .adu.uuu... sg
ABSTRACT
Multi-objective optimization (MOO) has become an influential framework for various machine learning problems, including reinforcement learning and multi- task learning. In this paper, we study the black-box multi-objective optimization problem, where we aim optimize multiple potentially conflicting objectives with function queries only. To address this challenging problem and find a Pareto optimal solution or the Pareto stationary solution, we propose a novel adaptive stochastic gradient algorithm for black-box MOO, called ASMG. Specifically, we use the stochastic gradient approximation method to obtain the gradient for the distribution parameters of the Gaussian smoothed MOO with function queries only. Subsequently, an adaptive weight employed to aggregate all stochastic gradients optimize all objective functions effectively. Theoretically, we explicitly provide the connection between the original MOO problem and the corresponding Gaussian smoothed MOO problem and prove the convergence rate for the proposed ASMG algorithm in both convex and non-convex scenarios. Empirically, the proposed ASMG method achieves competitive performance multiple numerical benchmark problems. Additionally, the state-of-the-an performance on the black- box multi-task learning problem demonstrates the effectiveness of the proposed ASMG method.
INTRODUCTION
colti-objeetive optimization (MOO) involves optimizing multiple potentially conflicting objectives simultancously (Deb et al., 2016; Fliege & Svaiter, 2000). In recent years, MOO has drawn intensive attention in a wide range of applications, including meta-learning (Ye et al., 2021; Yu et al., 2022), reinforcement learning (Thomas et al., 2021; Prabhakar et al., 2022), learning-to-rank (L.TR) problems Mahapatra et al. (2023a;b), and multi-task learning (Momma et al., 2022; Fernando et al., 2022; Zhou al., 2022b; Lin al., 2022; 2023; Ye et al., 2024). A typical MOO problem formulated
min F(x) = (Pi (a)), F2(x),.... ..., (x)), x
where 2 2 denotes the number of objectives, X' C Rdd and d represents the parameter dimension. The objective function F; I2 + R satisfies F (x 2 oo for 1,..., m.
Solving the MOO problem is challenging because in most cases it cannot find a common parameter that minimizes all objective functions simultaneously. Therefore, a widely adopted strategy is to find Pareto optimal solution Pareto stationary solution. To achieve this goal, a typical gradient-basee method is the multiple gradient descent algorithm (MGDA) (Désidéri, 2012). The basic idea of
"quual contribution.
Corresponding author.

---

Published as a conference paper at ICLR 2024
MGDA is to iteratively update the variable æ via common descent direction for all the objectives through a convex combination of gradients from individual objectives. Various MGDA-based MOO algorithms (Yu et al.. 2020; Liu et al., 2021; Fernando et al., 2022: Zhou et al., 2022b) have been proposed to adjust the multiple gradients to seek a common descent direction that simultaneously decreases all the objectives. Those gradient-bas based MOO algorithms have been successfully applied in a wide range of applications, especially for multi-task learning (MTL) (Sener & Koltun, 2018; Zhang& & Yang, 2022).
However, in many MOO-based learning problems, the gradient of the objective F(x) w.r.t the variable æ cannot be explicitly calculated, making problem (1) a black-box MOO problem (Wang & Shan, 2004; Zilinskas, 2014). For instance, many large models such large language models (LLMs) (Devlin et al., 2018; Raffel et al., 2020; Yu et al., 2023) are released in the service and are only allowed for access with APIs (Brown et al., 2020). In such scenarios, users can only query the large models without accessing gradients to accomplish tasks of interest (Sun et al., 2022b;a), and gradient-based MOO methods are no longer applicable since they all rely on the availability of true gradients or stochastic gradients w.r.t. the variable æ. Several kinds of approaches have been widely studied for black-box MOO, such as Bayesian optimization (BO) (Konakovic Lukovic et al., 2020; Zhang & Golovin, 2020) and genetic algorithms (GA) (Laumanns et al., 2002; Wang & Shan, 2004; Chen et al., 2012; Arricta et al., 2018). Among those methods, BO methods are good at dealing with low-dimensional expensive black-box MOO problems, while GA is to explore the entire Pareto optimal set, which is computationally expensive for machine learning problems, and usually lacks convergence analysis. Therefore, those limitations motivate to design algorithm for black-box MOO that can effectively reach a Pareto optimal solution or a Pareto stationary solution for relatively high-dimensional learning problems with affordable evaluations and convergence guarantee.
To achieve that, in this paper, we propose a novel Adaptive Stochastic Multi-objective Gradient (ASMG) algorithm for black-box MOO by taking advantage of gradient- based MOO methods. Specifically, the ASMG method first smoothes each objective to their expectation over a Gaussian distribution, leading to Gaussian smoothed objectives. Then iteratively updates the parameterized distribution via a common search direction aggregated by the approximated stochastic gradients for all smoothed objectives. We explore the connections between the MOO and the corresponding Gaussian smoothed MOO and provide a convergence analysis for the proposed ASMG algorithm under both convex and non-convex scenarios. Moreover, experiments on various numerical benchmark problems and black-box multi-task learning problem demonstrate the effectiveness of the proposed ASMG method.
The main contributions of this work are three-fold: (i) We propose novel ASMG algorithm for black-box multi-objective optimization. To the best of our knowledge, we are the first to design stochastic gradient algorithm for black-box MOO with theoretical convergence guarantee. (ii) Theoretically, we explicitly provide the connection of the Pareto optimal and stationary conditions between the original MOO and the corresponding Gaussian-smoothed MOO. Moreover, we prove the convergence rate for the proposed ASMG algorithm in both convex and non-convex cases. (iii) Empirically, the proposed ASMG algorithm achieves competitive performances on multiple numerical benchmark problems. Moreover, the state-of state-of-the-art performance on blck-box multi-task learning problems demonstrates the effectiveness of the proposed ASMG method.
Notation and Symbols. 11. 11- and || llso denote the I norm, l2 norm, and too norm for vectors, respectively. || || denote the Frobenius norm for matrices. n denotes an m-dimensional simplex. S denotes the set of positive semi-definite matrices. & denotes the elementwise division operation when X and Y are vectors, and the elementwise division operation for diagonal elements in X and Y when they are diagonal matrices. For square matrix X, diag ()) is a vector with diagonal entries in X, and if x is a vector, diag(x) ) a diagonal matrix with x as its diagonal entries. Define ||x||y := (X, XX for a matrix Y E St or a non- negattvee vector Y, where ( denotes the inner product under the 12 norm for vectors and the inner product under the Frobenius norm for matrices.
BACKGROUND
In this section, we introduce useful concepts of MOO and stochastic gradient approximation strategies for black-box optimization.
2

---

Published as a conference paper at ICLR 2024
2.1 MULTI-OBIECTIVE OPTIMIZATION
In MOO (Deb et al., 2016), we are interested in finding solutions that can not be improved simultane- ously for all the objectives, leading to the notion of Pareto optimality, which is defined follows for the problem (1).
Definition 2.1. For any two point æ æ2 X. we define that æ dominates 22 (((x)) S (x22)) holds for i 1,..., m, and (x1) (x2) holds for some A point x" X is called Pareto optimal if it not dominated by any other point in X. The set of all Pareto optimal solutions forms the Pareto set. The set of objective values F(a=) for all the Pareto optimal is called the Pareto front.
We then present the sufficient condition for determining Pareto optimal.
Proposition 2.2. For MOO problem (1). if all objective F((x) for for = 1...., m are convex functions and there exists X A mm11 such that x arg ming X XF F(x). then x* is Pareto optimal.
The above proposition implies that the minimizer of any linearization is Pareto optimal (Zhou et al., 2022b). In the general nonconvex cases, MOO aims find the Pareto stationary solution (Fliege et al., 2019). If point à is a Pareto stationary solution, then there is no common descent direction for all For the Pareto stationary condition, we have the following proposition according to Proposition 1 in Zhou et al. (2022b).
Fa(x)'s (i I,...; m)
Proposition 2.3. For MOO problem (I), (i) we say x² E X is a Pareto stationary solution if there A.("())) I 0; (ii) we say x² E X is e-accurate Pareto VFF
exist - such that stationary solution if minx
where X A mn-1
2.2 STOCHASTIC GRADIENT APPROXIMATION STRATEGIES
Inspired by evolution strategy, the stochastic gradient approximation method (Wierstra et al., 2014; Lyu & Tsang, 2021) for black-box optimization, instead of maintaining a population of searching points, iteratively updates a search distribution by stochastic gradient approximation.
The stochastic gradient approximation strategies employed in black-box optimization typically follow general procedure. Firstly, a parameterized search distribution is utilized to generate batch of sample points. 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, when denotes the parameters of the search distribution pe (œ) and f(x) denotes a single objective function for sample æ, the expected fitness under the search distribution can be defined as (() = (m) [f().. Based on this definition, we can obtain the Monte Carlo estimate of the search gradient
J = 1 N f(x 1 Vo
1 .
where N denotes the number of samples, and æy denotes the j-th sample. Therefore, the stochastic gradient V (O) provides a search direction in the space of search distributions.
3 METHODOLOGY
In this section, we introduce the proposed ASMG algorithm. Firstly, we formulate the black-box MOO as a min-max optimization problem and solve Section 3.1. Then in Section 3.2, we derive the update formula of parameters in the search distribution under the Gaussian sampling.
3.1 BLACK-BOX MULTI-OBIECTIVE OPTIMIZATION
We aim to minimize the MOO problem (1) with only function queries. Due to the lack of gradient information in black-box optimization, we use the stochastic gradient approximation method. Specifi- cally, the objective of the original MOO is smoothed to the expectation of F(x) under a parametric search distribution po(x) (x) with parameter 0, i.e., (0) Eo (z)) (x(()) for i 1,..., m. Then the optimal parameter 0 is found by minimizing the following smoothed MOO problem as
((0) (O),
(8))
(3)
3

---

and A = The matrix A is of size m x m, which is Published as a conference paper at ICLR 2024
By following Wierstra al. (2014); Lyu & Tsang (2021), the search distribution is assumed to be a Gaussian distribution, i.c. (o(x) = Ni μ., Σ) where Ii denotes the mean and E denotes the covariance matrix, and correspondingly 0 includes i and Σ, i..., 0 {Me, Σ}. We denote J((0) = J1, Σ) for = 1, 1,..., m. This Gaussian-smootherr MOO method can effectively estimate stochastic gradients, and enable more accurate search direction for the distribution to address high-dimensional black-box MOO problems. The connection between this Gaussian smoothed MOO problem (3) and problem (1) is shown in Section 4.
Here we aim to derive an update formulation for 0. To optimize all the Gaussian smoothed objective functions effectively, inspired by MGDA, we can find a parameter 0 to maximize the minimum decrease across all smoothed objectives in each iteration as
max min (J,(0.) (O) max min (VoJ. -0, sE(m]
0
rE(m]
where Vo):(0,) VoE.o [F(())] denotes the derivative of ()) w.r.t. 0 (M, at 0, {ee In Eq. (4), the first-order Taylor expansion is used to derive the approximation with an assumption that the variable is close to 0,. To further make this assumption hold, we add a regularization term to maximize (pollolp,, into Eq. (4), and then the objective function to update 0 is formulated
B1
m Σ (V --00)))))0)))) 1 (I. 3.
min e AEEA
max
0.)
f=1
Note that problem (5) is convex w.r.t. θ and concave w.r.t. À for Gaussian distribution pe. Then using Von Neumann- Fan minimax theorem (Borwein, 2016), we can switch the order of the min and max operators, leading an equivalent problem
max AEEA
min Σ
m
AVo.) 0.) + 3.
1 (l.(pollpo.)
(6)
1=1
By solving the inner problem of problem (6), we can obtain the update formulations for μa and Σ in the (-th iteration as
Me+1 Me B,E, Σ V
- + 23c I
where V (0,) and ((,) denote the derivative of (0) w.r.t. I and Σ at t4 and Σ = Σg respectively. To obtain those two gradients, the following theorem, we prove that we only need function queries.
Theorem 3.1. (Wierstra et al., 2014) The gradient of the expectation of an integrable function Fx(x) under Gaussian distribution pe := NN,, Σ) with respect to the mean and the covariance Σ can be expressed as
V Bp [F(())] = Ep Σ (x [)F((x)),
(8)
1
Ex (F(xa)]
Eo ( ( (x- 1)(x - -E------)
(9)
2
According to Theorem 3.1, to calculate the gradients, need to calculate the inverse covariance matrix, which computationally expensive in high dimensions, and hence to reduce the computational cost, we assume that the covariance matrix Σ is diagonal matrix.
Then substituting Eq. (7) into problem (6), can be approximated by the following quadratic programming (QP) problem
m
m
min MEA
Σ
Mpp
+
2
(10)
where pf (..)) and h
The detailed derivation is put in the Appendix A. Problem (10) is obviously convex and the objective function of problem (10) can be simplified to ATAT where X = (Xf....,A... (2(h
diag(E,VeLl) V.J,
(((p)) )) ....... (Pmm)T independent of the dimension of μ. Therefore, the computational cost to solve problem (10) is negligible since m is usually very small. Here we use the open- source CVXPY Y library (Diamond & Boyd, 2016 6) solve it.
4

---

Published as a conference paper at ICLR 2024
3.2 UPDATE FORMULATIONS FOR GAUSSIAN SAMPLING
Since P and h in problem (10) and the update formulation of 1a and Σ in Eq. (7) need to calculate expectations of the black-box function. However, those expectations do not have analytical forms, and we estimate them by Monte Carlo sampling.
Specifically, according to Theorem 3.1, the stochastic approximation of P and h using Monte Carlo sampling are given as
p Σ
E, (2, - (F)(()) - F((1)),
(11)
N
h 1 Σ
N
[diag( uo) - -1)((())
(12)
2N
where æ denotes the j-th sample and inspired by Lyu & Tsang (2021), subtracting F: (14) is used to improve the computational stability while keeping them as unbiased estimations. By incorporating Theorem 3.1 into Eq. (7), the updated formulations for μ and E using Monte Carlo sampling are rewritten as
Pe+1 Mr Br Σ
Th
EE = + 23, Σ NO
(13)
where the stochastic gradients 9f and G are formulated
g
Σ, (zz (F,(())))) F((e)),
(14)
N
G
I 2N
diag Σj (diaa((1)) (m) (4) T (B)(()))) R (.())))]
(15)
Note that of is an unbiased estimator for the gradient V (0,) as proved in Lemma B.4. To avoid the scaling problem, in practice, we can employ monotonic transformation for the aggregated objective, more details can be found in Appendix E.
To ensure the convergence, the sequence of weighted vector {A* { convergent sequence (Zhou et al., 2022b; Fernando al., 2022: Liu & Vicente, 2021). However, directly solving problem (10) in each iteration cannot guarantee that. Moreover, since solving the composite weights X depends on p and ht, which are related to stochastic gradients of and G the estimation of the composite stochastic gradient may contain some bias, i.e. E m E * To generate stable composite weights sequence and reduce the bias caused by the correlation of weights and the stochastic gradients, we apply a momentum strategy (Zhou et al., 2022b) to A. Specifically, in k-th iteration, we first solve problem (10) to obtain Xx. and then update the weights by A (1 1 A
Jt=0 is usually required to be
Σ |
7 where "/ is a coefficient and Y 10. To preserve the advantage of maximizing the minimum decrease across all the Gaussian smoothed objectives, the coefficient "t. is set as I at the beginning and then decays to 0 as ( - +o. In Lemma B.5, we show that the bias caused by solving X decreases to zero as 7 + O.
The complete algorithm is shown in Algorithm 1. Since the computational cost associated with solving problem (10) in each iteration is negligible, the computational cost for the ASMG method per iteration is the order of Om.Nd).
4 CONVERGENCE ANALYSIS
In this section, we provide a comprehensive convergence analysis for the proposed ASMG method. All the proofs are put in Appendix C. Firstly, we make a standard assumption for problem (3). Assumption 4.1. The functions J,(O), ................................ (0) are H-Lipschitz and L-smoothness w.r.t. 0 = (v, Σ} E O, where θ = (n.) Σ μ E Rd Σ S+}.
The smoothness assumption in Assumption 4.1 is widely adopted in MOO (Zhou et al., 2022b; Fernando et al., 2022). Then, we provide a boundedness result for the covariance matrix Σ.
Theorem 4.2. Suppose that the gradient G. are positive semi-definite matrix, Lee, G, > {I for i= 1, I,..., m, where & > 0 and that the covariance matrix is diagonal matrix. Then for Algorithm
1, we have Ex 1 &E B.t
5

---

Published as a conference paper at ICLR 2024
Algorithm 1 The ASMG Method
Require: number of iterations T, step size 8, number of samples N.
1: Initialized 0g = (10. Eo) and 700 = 1;
2: for = 0 to T do
3: Take i.i samples 2j I), for E (1,....N}
4: Set =; pr + Σ 2j for j E fl.....NH NN:
5: Query the batch observations [F] [z) (...)......).................).. ( Pm (mi (.)
6:
Query the batch observations { (M)),, (mi);
7:
Compute pi & Σラ E (xx (F)((()))) - Fi(m.));
8:
Compute h 2N E)= (i=]ddaa(((())))
(1) mi) "x" - (1) R((O))::
9:
Compute X by solving the QP problem (10);
10:
Update the weights for the gradient composition X = - -1) ;x²:
11:
Compute the stochastic gradients 9f and G according to Eqs. (14) (15), respectively;
12: Set pu+1 = Pr B, Ei= Ef and set E,+1 = Σ, + 23, E G.
end for
14:
return 0r = (JUT, Σr).
Theorem 4.2 establishes the upper bound for Σ throughout the optimization process and is useful to analyze the convergence properties in the non-convex scenario as shown in Section 4.2.
4.1 CONVEX CASES
In this section, we assume that each objective in problem (1), i.e., (i .m), is convex w.r.t Φ. Note that the proposed ASMG algorithm approximates the gradients of the objectives the Gaussian smoothed MOO problem, i.c., problem (3). It is necessary study the relation between the optimal solutions of the original MOO problem (1) and the corresponding Gaussian-smoothed MOO problem (3), and put the results in the following proposition.
Proposition 4.3. Suppose po pa( is Gaussian distribution with O {1,, Σ} and the functions (xx i= 1,..., m are all convex functions. Let Je( = Ep [Fi Then for any E m and μ² E X, we have E (F) F.((²) S > A (J Σ) - J,('", 0)). where 0 denotes a zero matrix with appropriate size and J&(p" 0) F((H)).
When f= is Pareto-optimal solution of problem (1), Proposition 4.3 implies that the distance to the Pareto-optimal objective values of the original MOO problem is upper-boundes by that of the Gaussian smoothed MOO problem. Then the following theorem captures the convergence μ for convex objective functions.
Theorem 4.4. Suppose that (i= m)) is convex function, J+(0) is c-strongly convex μ1, Ge is positive semi-definite matrix such that ŞT 3 G < of with & 2 Eo E St, and Eg = RI where R > 0. If S and the sequence {pt} generated by Algorithm satisfies that the distance between the sequence } and the Pareto set is bounded, iee. 1| 114-="1l S D where μ1 denotes a Pareto optimal solution of problem (1), then with Assumption 4.1, we have
Eg Σn
X( Σ.) J.(,", 01)] =
1 3T
log
+7). (16)
T
T
Based Theorem 4.4 and Proposition 4.3, when 3= 01) and 7 OTT-1), we have
Ez Σn ( 0 o(logT) T
(17)
t=
Therefore, the proposed ASMG algorithm possesses a convergence rate O log in convex cases. Note that Theorem 4.4 does not require each objective function F,(x) to be differentiable. Hence, Theorem 4.4 holds for non-smooth convex functions {F)())). If (() is c-strongly convex, then (+) is also c-strongly convex (Domke, 2020) and Theorem 4.4 holds.

---

Published as a conference paper at ICLR 2024
4.2 NON-CONVEX CASES
In many practical problems, the objective functions of problem (1) are non-convex, and we aim to find Pareto stationary solution. Similar Proposition 4.3, have the following result to reveal the relation between Pareto stationary solutions of problems (1) and (3).
Proposition 4.5. Suppose po(æ;) is a Gaussian distribution with 0 {u, E. and P((x)) (i 1,..., ..)) is a Lg-Lipschitz smooth function. Let Jz(0) - Epp [F(())] and E be diagonal ma- trix. If 1x" is a Pareto stationary solution of problem (3) and there exists X E A such that then we have Ei=1 N F S 1.2.ldiagg Σ)]l and this implies that μ² is c-accurate Pareto stationary solution of problem (1) with L (eIldiagEE))
EE X. (.VuJi(("")
According to Proposition 4.5, a Pareto stationary solution of problem (3) is a e-accurate Pareto stationary solution of problem (I). The following theorem establishes the convergence of the proposed ASMG method under the non-convex case.
Theorem 4.6. Suppose that J,( (i = 1,..., ,m) is bounded, i.e., [](00] Σ B, G4 is positive
semi-definits matrix such that ςI 3 G; I bl with b 2 E > O, Eo E St and Eo 3 RI with R > 0. If 3 S RLVa'
then with Assumption 4. we have
1 Σ
E2
||
V AiJi((
3T + +
(18)
T
According Theorem 4.6, if 3 O(T = the proposed ASMG method possesses
a (T-+) convergence rate to reach a Pareto stationary solution for problem (3), which is a c-accurate
Pareto stationary solution of problem (1). According to Theorem 4.2, when 8 = O(T b). diagonal entries of Σr converge to zero T and hence 0, leading to Pareto stationary solution
for problem (1).
RELATED WORKS
Several kinds of approaches have been studied for black-box optimization, such Bayesian opti- mization (BO) (Srinivas et al., 2009; Lyu et al., 2019), evolution strategies (ES) (Back, 1991; Hansen, 2006), and genetic algorithms (GA) (Srinivas & Patmaik, 1994). BO-based methods are inefficient in handling high-dimensional problems and GA methods lack convergence analysis. ES-based methods are better for relatively high-dimensional problems and have been applied in many applications such as reinforcement learning (Liu al., 2019) and prompt learning (Sun et al., 2022b;a). Al- though BO achieves good query efficiency for fow-dimensional problems. it often fails to handle nigh-dimensional problems with large sample budgets (Eriksson et al., 2019). The computation of GP with a large number of samples itself is expensive, and the internal optimization of the acquisition functions is challenging.
Among ES-based methods, CMA-ES (Hansen, 2006) is a representative one. It uses second-order information to search candidate solutions by updating the mean and covariance matrix of the likelihood of candidate distributions. The CMA-ES method is widely adopted in many learning tasks (Won et al., 2017: Sun et al., 2022b;a; Han et al., 2023). Though is designed for single-objective black-box optimization, it is also applied to black-box multi-task learning (Sun et al., 2023), where all objectives are aggregated with equal weights. Therefore, we consider CMA-ES as an important baseline method in our experiments.
6 EMPIRICAL STUDY
In this section, we empirically evaluate the proposed ASMG method on different problems. The experiments are conducted on single NVIDIA GeForce RTX 3090 GPU,
6.1 SYNTHETIC PROBLEMS
We compare the proposed ASMG method with CMA-ES (Hansen, 2006), ES (Salimans et al., 2017), BES (Gao& & Sener, 2022), and MMES (He et al., 2020) methods the following three d-dimensional
7

---

Published as a conference paper at ICLR 2024
synthetic benchmark test problems:
F(æ)= =
10
20-1)
I - 0.01,,
10 a- az + 0.01).
(19)
1=1
i=1
F(x)=
d
x
0.1
1 >
d
x 0.11²).
(20)
2(11)
1 10d + Σ
الانك (110 x² - 1ocos(22 10 10 x.))
= F(x)=
10
x
c0
(21)
i=1
Test problems (19)-(21) are called the shift 1 /1-eliipsodd, shift 1 -ellipsoidd and mixed ellipsoid- rastrigin 10, respectively.
For the baseline methods, by following Sun et al. (2023), we aggregate multiple objectives with equal weights to become a single objective. The results are evaluated by calculating the Euclidean distance between the solution æ and the optimal solution set P, i.e., & (2, P). Due the page limitation, the details of the evaluation metric and implementation are put in Appendix F.I.
0
Loguet
-2
OHAES
CHAES
-3
BCS
RC:
RES
MPES
HGMG
(XK10?
Iteration. T(x10"
Iteration. TXK10')
(a) Shift (1 Elllssipo
(b) Shift ( Ellippsoid..
(c) Mixed Cllipsoid-Rastriginn 10.
Figure 1: Results the synthetic problems with 50 samples (i.e., N = 50).
Results. Figure shows the results on those three d-dimensional synthetic problems with 50 samples (i.e., N = 50) and d= 100. The proposed ASMG method approximately achieves linear convergence rate in the logarithm scale and can arrive at solutions with a high precision, i.c., 10 on three cases. The CMA-ES method can converge with high precision on problem (19) but only achieve 10-1 precision on problem (20). The MMES method also cannot reach high precision on these problems. Moreover, the CMA-ES and MMES methods fail problem (21) and the ES and BES methods fail on all three problems. The results show that it could be challenging for ES and BES optimize non-smooth or non-convex test functions without adaptively updating mean and covariance. Those results consistently demonstrate the effectiveness of the proposed ASMG method.
6.2 BLACC--OOX MULTI-TASK LEARNING
In this section, we apply the proposed ASMG method to black-box multi-task learning. Multi-task learning (MTL) (Caruana, 1997; Zhang & Yang. 2022) is widely adopted paradigm and aims train a single model to handle multiple tasks simultaneously. Given m tasks, task i has a training dataset D. Let (D, M4)) denote the average loss on D; for task using the model M with parameter Φ. Then MTL can be formulated as a MOO problem with m objectives as min (Ci...,, ). For the conventional MTL setting, the model M available for backward propagation, allowing the optimization problem to be solved using the gradients of the model parameters, i.e., C, However, many practical scenarios, such as multi-task prompt tuning for extremely large pre-trained models (Sun et al., 2023), part of the model M remains fixed in the service and is only accessible through an inference API. This results the gradient of the objectives L, with respect to the local parameters & being unavailable. For cases where the gradients of task losses with respect to the learned parameter & cannot be explicitly calculated in MTL, we refer to black-box MTL.
Problem Formulation. We consider specific black-box MTL problem, where our focus is to learn a shared prompt for all tasks using pre-trained vision-languagg models (Sun et al., 2023; Wang et al., 2023; Liu et al., 2023). Following the setup in Liu et al. (2023), et al., 2021) as the base model. In this context, our model M can be expressed as M = {Ma. p). where M, represents the fixed CL.P model, and p E TRD is the token embedding of the prompt. Note
employ the CLIP model (Radford
8

---

Published as a conference paper at ICLR 2024
that the CLIP model is treated black-box model, making it impossible to calculate the gradient of the token embedding p in the text encoder using backward propagation. Inspired by Sun et al. Id and employ a fixed randomly initialized matrix A R PDx to project
(2022b;a), we optimize v onto the token embedding space instead of directly optimizing the prompt p. Consequently, the corresponding black-box MTL problem can be formulated as
min (Ci {Me. Av)),..., (Dmi (MM. (MM,Av))
(22)
The details of the CLIP model with token embedding and the loss function C; are put in Appendix F.2.
Baselines. The proposed ASMG method is compared with (i) the zero-shot setting, which evaluates the model on the downstream datasets that were not seen during the training phase without prompt tuning (Radford al.. 2021); (ii) four ES-based black-box optimization methods, i.c., ES (Salimans et al.. 2017), BES (Gao & Sener, 2022), MMES (He et al., 2020) and CMA-ES (Hansen, 2006), where we simply transform multiple objectives into one single objective by equal weights; (iii) the ASMG-EW method, where we fix the weighted vector as X for ASMG during optimization. The implementation details are put in Appendix F.2.
m
Table I:
Results on the Office-31 1 and Office-home datasets. Each experiment is repeated over random seeds and the mean classification accuracy (%) is reported. The best result across all groups is in bold and the best result in each comparison group is underlined.
Office-31
Office-home
Method
D
W
Avg
CI
Pr
Avg
Zero-shot
73.68
79.51
66.67
73.28
73.06
51.68
83.79
81.41
72.48
Dimension d
256
ES
75.10
80.05
71.67
75.61 #1.18
71.16
47.96
80.33
80.90
70.09
BES
72.65
80.60
73.52
75.59
68.94
45.97
81.53
68.97
MMES
75.90
83.33
76.67
78.63
71.85
49.26
82.10
81.37
71.1420.00
CMA-ES -ES
76.24
87.98
75.93
80.05 11.34
69.26
50.09
85.73
82.13
21.80
ASMG-EW
76.52
83.88
77.22
79.21 1:000
70.02
47.13
80.23
79.50
69.22 29.222.11
ASMG
77.83
86.61
80.56
81.67
74.26
53.52
86.23
83.03
74.26 #1.06
Dimension d'
5:12
ES
75.95
81.69
75.37
77.67 20.01
70.78
48.39
82.06
20.60
BES
75.73
82.51
74.81
77.68
69.39
48.18
82,94
80.29
20.20.00.5
MMES
76.01
84,70
77.22
79.31 10.54
70.40
50.45
85. 10
82.56
12.13
CMA-ES
87.16
77.22
20.38
70.46
50.02
86.26
82.02
22.19
ASMG-EW
78.01
84,70
76.67
79.79
69.20
46.91
80,51
80.68
69. 20.33
ASMG
78.63
87.43
78.33
81.47 20.37
73.50
52.84
85.88
83.78
74.00
Dimension d'
1024
ES
72.59
78.14
74.81
75.1841.91
70.34
47.38
82.59
80.54
70.21
BES
72.14
79.51
71.67
74.44.0.4
70.27
48.25
79.94
80.00
69.62 st
MMES
77.09
81.42
75.74
78.092005
71.03
49.19
84.29
71.61
CMA-ES
76.87
87.16
77.59
80.54.0.41
71.28
50.92
85.73
82.49
72.61
ASMG-EW
77.15
82.51
77.78
79. 1.4
69.20
47.09
81.36
80.86
69 20.55
ASMG
76.30
87.70
80.19
81.4020.9
73.18
51.82
85.84
83.21
73.51 #0.07
Results. Table presents experimental results on the Office-31 and Office-home datasets for three different dimensions of z. We can see that the ASMG method consistently outperforms all baselines in terms of average classification accuracy across different settings, highlighting its effectiveness. When comparing ASMG with ASMG-EW, the results demonstrate the effectiveness of adaptive stochastic gradient. Notably, even in the high-dimensione good performance. Remarkably, ASMG achieves the highest average classification accuracy when d = 256, surpassing zero-shot by 8.4% on Office-3/ and 1.8% on Office-home. This further validates the effectiveness of the proposed ASMG method.
setting (i.c., d = 1024), our method maintains
CONCLUSION
In this paper, we propose ASMG, a novel and effective adaptive stochastic gradient-based method for solving the black-box MOO problem. Specifically, we smooth the black-box MOO problem to Gaussian smoothed MOO and we propose a novel adaptive stochastic gradient approximation approach to solve it. Theoretically, we explore the connections between the MOO and the corre- sponding Gaussian smoothed MOO, and we provide convergence guarantee for ASMG under both convex and non-convex scenarios. Moreover, empirical studies on synthetic problems and black-box MTL demonstrate the effectiveness of the proposed ASMG method.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
This work is supported by National Key R&D Program China 20222I0010330,, NSFC key grant under grant 62133600, NSFC general grant under grant 62076118, and Shenzhen fundamental research program JCY JCY120210332105500000
REFERENCES
Aitor Arrieta, Shuai Wang, Ainhoa Arruabarrena, Urtzi Markiegi, Goiuria Sagardui, and Leire Etxeberria. Multi-objective black-box test case selection for cost-effectively testing simulation models. In Proceedings of the genetic and evolutionary computation conference, pp. 1411-1418, 2018.
Thomas Back. A survey of evolution strategies. In Proc. of Fourth Internal. Conf. Genetic Algorithms, 1991.
Jonathan M Borwein, A very complicated proof of the minimax theorem. Minimax Theory and its Applications, 1(1):21-27, 2016.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 13:1877-1 2020.. 2020.
Rich Caruana. Multitask learning. Machine learning, 28:41-75, 1997.
Guodong Chen, Xu Han, Guiping Liu, Chao Jiang, and Ziheng Zhao. An efficient multi-objectio optimization method for black-box functions using sequential approximate technique. Applied Soft Computing, 12(1):14-22 2012.
Kalyanmoy Deb, Karthik Sindhya, and Jussi Hakanen. Multi-objective optimization. In Decision sciences, pp. 161-200. CRC Press, 2016.
Jean-Antoine Désidéri. Multiple-gradient descent algorithm (mgda) for multiobjective optimization. Comptes Rendus Mathematique, 350(5-6):313 3188 2012.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: /810.0800. 2018.
Steven Diamond and Stephen Boyd. CVXPY: A Python modeling language for convex optimization. Journal of Machine Learning Research, 17(83)11-5, 2016.
Justin Domke. Provable smoothness guarantees for black-box box variational inference. In International Conference on Machine Learning, pp. 2587-2596. PMLR, 2020.
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.
Heshan Devaka Fernando, Han Shen, Miao Liu, Subhajit Chaudhury, Keerthiram Murugesan, and Tianyi Chen. Mitigating gradient bias in multi-objective learning: A provably convergent approach. In The Kleventh International Conference on Learning Representations, 2022.
Jörg Fliege and Benar Fux Svaiter. Steepest descent methods for multicriteria optimization. Mathe- matical methods of operations research, 51:479-494, 2000.
Jörg Fliege, A Ismael F Vaz, and Luís Nunes Vicente. Complexity of gradient descent for multiobjec- tive optimization. Optimization Methods and Software, 34(5):949-995 959, 2019.
Katelyn Gao and Ozan Sener. Generalizing gaussian smoothing for random search. In International Conference Machine Learning, pp. 7077-7101. PMLR, 2022.
Chengeheng Han, Liqing Cui, Renyu Zhu, Jianing Wang, Nuo Chen, Qiushi Sun, Xiang Li, and Ming Gao. When gradient descent meets derivative-free optimization: match made in black-box scenario. arXiv preprint arXiv:2305. 10013, 2023.
10

---

Published as a conference paper at ICLR 2024
Nikolaus Hansen. The ema evolution strategy: comparing review. Towards 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.
Mina Konakovic Lukovic, Yunsheng Tian, and Wojciech Matusik. Diversity-guides multi-objective bayesian optimization with batch evaluations. Advances in Neural Information Processing Systems, 111177008-1720, 2020.
Marco Laumanns, Lothar Thiele, Eckart Zitzler, Emo Welzl, and Kalyanmoy Deb. Running time analysis of multi-objective evolutionary algorithms on simple discrete optimization problem. In Parallel Problem Solving from Nature-PPSM VII: 7th International Conference Granada, Spain, September 7-11, 2002 Proceedings 7, pp. 44-53. Springer, 2002.
Baijiong Lin and Yu Zhang. Libmtl: A python library for deep multi-task learning. Journal of Machine Learning Research, 24(1-7):18, 2023.
Baijiong Lin, Feiyang Ye, Yu Zhang, and Ivor Tsang. Reasonable effectiveness of random weighting: A litmus test for multi-task learning. Transactions on Machine Learning Research, 2022.
Baijiong Lin, Weisen Jiang, Feiyang Ye, Yu Zhang, Pengguang Chen, Ying-Cong Chen, Shu Liu, and James Kwok. Dual-balancing for multi-task learning. arXiv preprint arXiv:2308. 02.3308..2299 /2029, 2023.
Bo Liu, Xingchao Liu, Xiaojie Jin, Peter Stone, and Qiang Liu. Conflict-aversee gradient descent for multi-task learning. Advances in Neural Information Processing Systems, 11188888-18999 2021.
Guoqing Liu, Zhao, Feidiao Yang, Jiang Bian, Tao Qin, Nenghai Yu, and Tie- Yan Liu. Trust region evolution strategies. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4352-4359, 2019.
Suyun Liu and Luis Nunes Vicente. The stochastic multi- gulti-gradient algorithm for multi-objective optimization and its application to supervised machine learning. Annals of Operations Research, pp. 1-30, 2021.
Yajing Liu, Yuning Lu, Hao Liu, Yaozu An, Zhuoran Xu, Zhuokun Yao, Baofeng Zhang, Zhiwei Xiong, and Chenguang Gui. Hierarchical prompt learning for multi-task learning. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10888-10898, 2023.
Yueming Lyu and Ivor W Tsang. Black-box optimizer with stochastic implicit natural gradient. In Machine Learning and Knowledge Discovery in Databases. Research Track: European Conference, ECML PKDD 2021, Bilbao, Spain, September 13-17, 2021, Proceedings, Part III 21, pp. 217-232. Springer, 2021.
Yueming Lyu, Yuan Yuan, and Ivor W Tsang. Efficient batch black-bon optimization with determin- istic regret bounds. arXiv preprint arXiv: 10041, 2019.
Debabrata Mahapatra, Chaosheng Dong, Yetian Chen, and Michinari Momma. Multi-label learning to rank through multi-objective optimization. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023, Long Beach, CA, USA, August 6-10, 2023, pp. 4605 4616, 2023a.
Debabrata Mahapatra, Chaosheng Dong, and Michinari Momma. Querywise fair learning to rank through -bjti--o optimization. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. KDD 2023, Long Beach, CA, USA, August 6-10, 2023, pp. 1653-1664, 2023b.
Michinari Momma, Chaosheng Dong, and Jia Liu. A multi-objectivv/muuii--aa learning framework induced by pareto stationarity. International Conference on Machine Learning, pp. 15895-15907. PMLR, 2022.
11

---

Published as a conference paper at ICLR 2024
Prakruthi Prabhakar, Yiping Yuan, Guangyu Yang, Wensheng Sun, and Ajith Muralidharan. Multi- objective optimization notifications using offline reinforcement learning. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 3752-3760, 2022.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pp. 9748-8763. PMLR, 2021.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. The Journal of Machine Learning Research, 21 21(55:548--5511 2020.
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. In International conference on machine learning, pp. 1278-1286. PMLR, 2014.
confeeeee
Kate Saenko, Brian Kulis, Mario Fritz, and Trevor Darrell. Adapting visual category models to new domains. In European conference on computer vision, pp. 213-226. Springer, 2010.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever, Evolution strategies as scalable alternative reinforcement learning. arXiv preprint arXiv:1703.03864, 2017.
Ozan Sener and Vladlen Koltun. Multi-task learning as multi-objective optimization. Advances in neural information processing systems, 31, 2018.
Mandavilli Srinivas and Lalit M Patnaik. Genetic algorithms: A survey, computer, 27(6):17-26, 1994.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process opti- mization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.399 2009.
Tianxiang Sun, Zhengfu He, Hong Qian, Yunhua Zhou, Xuan-Jing Huang, and Xipeng Qiu. Bbtv2: towards a gradient-free future with large language models. In Proceedings of the 2022 Conference on Empirical Methods Natural Language Processing, pp. 3916-3930, 2022a.
Tianxiang Sun, Yunfan Shao, Hong Qian, Xuanjing Huang, and Xipeng Qiu. Black-box tuning for language-model-ase as-sevvice.. In Proceedings of ICML, 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 Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pupers), pp. 11156-11172. 2023.
Philip S Thomas, Joelle Pineau, Romain Laroche, et al. Multi-objective spibb: Seldonian offline
policy improvement with safety constraints in finite mdps. Advances in Neural Information Processing Systems, 34:2004-2017, 2021.
Hemanth Venkateswara, Jose Eusebio, Shayok Chakraborty, and Sethuraman Panchanathan. Deep hashing network for unsupervised domain adaptation. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5018-5027, 2017.
Gary Wang and Songqing Shan. An efficient pareto set identification approach for multi-objective optimization black-box functions. In International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, volume 46946, pp. 279-291, 2004.
Zhen Wang, Rameswar Panda, Leonid Karlinsky, Rogerio Feris, Huan Sun, and Yoon Kim. Multitask prompt tuning enables parameter-efficee efficient transfer learning. arXiv preprint 0rX1v:2303.02861 2023.
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) (511)949-999) 2014.
12

---

Published as a conference paper at ICLR 2024
Jungdam Won, Jongho Park, Kwanyu Kim, and Jehee Lee. How to train your dragon: example-guided control of flapping flight. ACM Transactions on Graphics (TOG), 36(6):1-13, 2017.
Feiyang Ye, Baijiong Lin, Zhixiong Yue, Pengxin Guo, Qiao Xiao, and Yu Zhang. Multi-objective meta learning. Advances in Neural Information Processing Systems, 34:21338-21351, 2021.
Feiyang Ye, Baijiong Lin, Xiaofeng Cao, Yu Zhang, and Ivor Tsang. first-order multi-gradinn algorithm for multi-objective bi-level optimization. arXiv preprint arXiv:2401.09255, 2024.
Longhui Yu, Weisen Jiang, Han Shi, Jincheng Yu, Zhengying Liu, Yu Zhang, James T Kwok. Zhenguo Li, Adrian Weller, and Weiyang Liu. Metamath: Bootstrap your own mathematical questions for large language models. arXiv preprint arXiv:2309. /200..222444. 2023.
Runsheng Yu, Weiyu Chen, Xinrun Wang, and James Kwok. Enhancing meta learning via multi- objective soft improvement functions. In The Eleventh International Conference on Learning Representations, 2022.
Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn. Gradient surgery for multi-task learning. Advances in Neural Information Processing Systems, 33: 5824-5836, 2020.
Richard Zhang and Daniel Golovin. Random hypervolume scalarizations for provable multi-objective black box optimization. In International Conference Machine Learning, pp. 11096-11105. PMLR, 2020.
Yu Zhang and Qiang Yang. A survey on multi-task learning. IEEE Transactions on Knowledge and Data Engineering. 34(12):5586- 5609, 2022.
Kaiyang Zhou, Jingkang Yang, Chen Change Loy, and Ziwei Liu. Conditional prompt learning for vision-language models. In Proceedings of the IEEE/CVF Conference Computer Vision and Puttern Recognition, pp. 16816-16825, 2022a.
Shiji Zhou, Wenpeng Zhang, Jiyan Jiang, Wenliang Zhong, Jinjie Gu, and Wenwu Zhu, On the convergence of stochastic multi-objective gradient manipulation and beyond. Advances in Neural Information Processing Systems, 35:38103-3811 155, 2022b.
Antanas Zilinskas. A statistical model-based algorithm for "black-box multi-objective optimisation. International Journal of Systems Science, 45(1):82-93, 2014.
13

---

Published as a conference paper at ICLR 2024
APPENDIX
A PROOF OF THE RESULT IN SECTION 3.1
A.1 PROOF OF UPDATED RULE
The objective of the inner minimization of problem (6) can be rewritten as
m
A VoJ,
+ kP (po.) = p T
X V (((e)) + Σ A
31
i=1
+
tr M Σ) + (μ - mi) Σ (μ (4) + log
d
(23)
2
Σ
where (O.) and (O,) denotes the derivative w.r.t μ and Σ taking at μ == br and Σ = Ee. respectively. We can the above problem is convex with respect to μ and Σ. Taking the derivative w.r.t μ and and setting them to zero, we can obtain that
1
X; (O,) + E
(1 me)= =0
(24)
Br
_ |ا - - - --11=0.
1
X {. +
(25)
23
Substituting the above equalities into the regularization term of the objective of the outer optimization problem we have
Σ
KL (00,)
=
tn tr(x,
+ (1 - (1-11:) 1 (11 11:) + log
d
(26)
23
Σ
m
1
m76
tr
I 2 Σ [.
2 (11- me)) [E + 2
Σ
V
(..))
23,
1
m
log
Σ
(27)
2,8g
2,3
i=1
m
m
A ( E
-7(m 10:))
Σ
A V.V,, (.)
23
d
log( I 23, Σ
(28)
23
2,3
T=1
Q:
Σ A (0.), E 3-E, E,
- mn)
Σ X; V.V J.()
(29)
23.
where Qe is given below.
m
Q. = log( 23
X, (.J,)())))) 2,3
Σ V. Eg
(30)
m
=log([ [ 2,, Σ -.)33E Σ (.))))(
(31)
Since E, and (e,) are both diagonal matrix, we denote diag E, Em X (.J(((())))
(vl...., 1f) in 1-th iteration, then we have
d
d d
Q = log [ (1+3,
23 Σ (og(1+2280))) -23c0))))) = Σ -28((0))+0(32(111))
(32)
14

---

Published as a conference paper at ICLR 2024
where the last equality is due to the Taylor expansion. Note that (v)( decrease to zero when
& + We can approximate Qe by Σ (v)). Then substituting Eqs. (24) (29) and Qr into
the outer optimization problem of problem (6), we have
m
(. 0: ))
+ (L(pollpo.) B
1
(33)
m
m
A J. p1 11)
E, )
(I.(pollpoo)
(34)
31
Qr
V.V (.))) p- ph
+
(35)
2
2
Br
m
m
m
A.Vild(())) E. Σ Ao V (ud((()))
Be
E. Σ A
E. Σ A V (1.)
2
(36)
Therefore, the outer optimization problem is equivalent to the following problem
min
X, (o)) + 2 diag(E) E, Σ (..))
(37)
AMEAm-
where we reach the result in Eq. (10).
A.2 PROOF OF THEOREM 3.1
We now provide the proof of the gradient of pp [F((a)] w.r.t and E.
V p. Epn
[. (x)
log(p(x;; μ. E)]
(38)
1
-Ep (x) 1
a 11) E (x 14)
(39)
2
=Eyo Σ - (x)))
(40)
We further have
1 Vx [F((x)] = Ep (x) Vx log(p(<: μ1, Σ))
(41)
= -E [Fi (2) [x) 10 (x 11) - (x u) - log det [Σ)]
(42)
Bo (>= 1-- (x
1x 10) T E 1) Fi(())
(43)
where we reach the conclusion.
B TECHNICAL LEMMAS
In this section, we introduce the following technical lemmas for analysis. The proof of all technical lemmas is put in Appendix D.
Lemma B.1. Suppose Σ and Σ are two d-dimensional diagonal matrix and is a d-dimensional vector, then we have Σ> S ||||||||||| and || || F.
Lemma B.2. Given a convex function I (x) for Gaussian distribution with parameters == =11, Σ let J(0)= [f Then J(0) is convex function with respect to O.
Lemma B.3. Suppose that the gradient G; are positive semi-definite matrix and satisfies {I - G, v bI. Then for algorithm 1, we have the following results.
(a) The (diagonal) covariance matrix ΣT satisfies
1
1
Σr 3
26 IT 31 11=1
+
E
2
IT 311 + 11
15

---

Published as a conference paper at ICLR 2024
Va (b) |Ei|| F 26 11--118 Bi"
(c) |E EellF S
b
25 (E 8.)3
Lemma B.4. Suppose the gradient estimator d for the i-th objective in t-th iteration as
o Σ (FF((1 + Σع 2) F((p:),,
where: z ~ 1). Suppose assumption 4.1 holds, the gradient G₁ are positive semi-definite matrix and satisfies EI 3 G. 3 bI and Σn 3 RI, where &. b, 2 0. Then we have
(a) g is an unbiased estimator of the gradient V VpB [F(()))
(b) 11 S 1E-(21-11 Ba)z
(d+4)2
(c) V= = |1 ( CI where C = max( 0 E E0 blo)) N
Lemma B.5. Suppose A
then we have V=
-=1N7111 S 2
Lemma B.6. Suppose assumption 4.1 holds, if gi...., I'm are unbiased estimates of Vi,Ji(O))..... (m.) Further suppose that each gradient variance is bounded by Vzlgil E=lllg - ((0)ll S 6, -....... m and let V=[X-] E=[ E= [x]I) Then for any gradient descent algorithm updated with composite gradient q: = Em == Nit with X E mm we have following inequality in 1-th iteration,
(a) 1B2l-q.1 Eg > ,. S VIIIE V 10
4.1 2H / V= D XV (b) EE TH V.
(c) E211|:112 1 J. S Σ + 4
C PROOF OF THE RESULT IN SECTION 4
In this section, we provide the proof of the result in Section 4.
Theorem 4.2 can be directly obtained by Lemma B.3 (a).
C.I PROOF OF THE PROPOSITION 4.3
From the definition of Je, E), we know that F((()) = Ji(H"" 0). Note that F((x)) is convex function, we have that
(1( F. (. S Ea-Nin, (F. = (1, E).
(44)
It follows that
F((n)= Fi(e') Ji Σ) ,))
(45)
Then we have
172
m
( $ Σ E)
(46)
where we reach the conclusion.
C.2 PROOF OF THE PROPOSITION 4.5
Note that
Σ m A
J II| = 0, we have
1=
m
m vVF((()) Σ V. (( + Σ A V V Ji(H')
m
\FF("))|
(47)
VF((())
X V Jelue)
(48)
16

---

Published as a conference paper at ICLR 2024
It follows that
m
X (F (1) S
Σ X IVF(())) J((x")1
(49)
i=1
N VF((")) - -B VF)
(50)
A (ll-E()))) (F((a)))-F(((m))) (F(
(51)
1=1
- Li Bee-NiH ,,100 -==1"
(52)
12 L
(53)
where the equality in Eq. (50) is due to vn- Jz(²") = BEWNNNH .o) VP.(2) in Rezende et al. (2014).
C.3 PROOF OF THEOREM 4.4
We denote q: = - m
- Xggh, then the update rule of μ can be represented as p+41 = pe + B.
According to assumption 4.1, the function J:(O) is L-smooth w.r.t {1s Σ). then we have
(H Ex) A (Jilues, Ex) + a. E,) E.g. + L
2 E
(54)
Since (z) is convex function, we have (+) is convex w.r.t 0 {u, Σ3 } by Lemma B.2, together with (0) is e-strongly convex w.r.t la we obtain
J(.).) S Ji(,", 00 + V (0.) (mr - 11) + V E Ji(,.) T
2 | -=1113 (55)
Note that V 1 J(,,) = M V(00) + VzJJ(,,) E. we have
J.( S J1(1' .0) + V (O,) (m- - -=" + 2V -
c
Ms 1e111. (56)
2
Substituting Eq. (56) into Eq (54), we have
X.4(Me+1, En) S AM 0) + VV (0:)) (m: (u--"") +
E₁
".gg + BA |E 2 16 - 11 111 (57)
3 J.. E.)
Let A, = >m (J.( E,) J, .)) and 3e S 1,1 we have
Ex[Ai] < E.
X (O.)) T (#=- x=') + B,E_
V (J:; E.g.
+
Ez E 12 + E2
(O.)
TT]] - -1lm: - 51111=11112 (58)
2
Note that
11 - 11 112 E- - |1 11" =/=""
(59)
= =1114 - 101 3-- - -11m + 3,E,q: - 41" 112 E
(60)
= =1114 - 10113--- (1114 - 11 10113,,1 + Be (14: (2,.))) + + 1 (E.g..9)) 9i)
(61)
= -,3.q T (mI - -1²)= - -3,(5,,) (2(i)) qr.
(62)
Therefore we have
1
||Mt+1 11 1=11,11) + B (Egq,) gr
-q. (Mt+ -μ²²=
(1 1 1011 3
(63)
233,
(1lm4 1
10112
x-- || 11" 1112)-1) + 8 Σ, |F q: 12
(64)
2,3
17

---

Published as a conference paper at ICLR 2024
where the inequality is due to Br 2 0 and Lemma B.1. Note that we have
m
m
Ez
(0.) + q:)) T (mz [r)] s l
Ez
X (i(e)) + [.119]
(65)
==1
m E2 Σ
S D
1.V (: + q.133
(66)
-=1
m
S D
(67)
where the first inequality is due to the Sauchy-SShwarl inequality, the second inequality is due to f4 < D and the last inequality is due to Lemma B.6 (a). Then we have
Fe
V p (0a)) T (m4 -x="]]
(68)
= Eg
q: (+u - 1²)) + \ (.((.)) + (:)T(Hp - μ²)
(69)
1
< 23
Ex [1ke 1= -='12,,1 |14+1 - 1= [2 +] 3. |l E, 1e D.
V (
(70)
where the inequality is due to Eq. (64) and Eq. (67). Note that
m
E&
Σ (o,) T E. s E. II Σ (
Er 1F S HHEell
(71)
where the first inequality is due to Lemma B.1 and the second inequality is due to the Lipschitz continuous assumption of the function J(( By using Lemma B.1 and Lemma B.6 (b), we further
have
2
E
(u Ex) E.q. S |E F
2H
V V
- Ez
(0.)
(72)
Then substituting Eqs. (70) (71) (72) into Eq. (58) and multiplying Be on both sides of the inequality, we have
1,1 S 1 - 14 10" 1
cB
|| 11 E,
||:
11
1=112+ + +.. Eell
2
+ -2213312,111 FF B,D)
V2 V= Σ
V V=(0
+
Ex [| 1
2
+ B& 1 - F
N n (0.)11
(73)
cBt
< E. 3e1l 1 12112,/1 - || - 1111 |33111
|| 14 -11112 + 33 Exllr
2
8 (d 4)²
(2H E B,D) [1
V_ V=
8 ( B2)
m
+ E.llr Σ
V=lا + 4H
V_ X
Σ V V
(74)
18

---

Published as a conference paper at ICLR 2024
where the second inequality is due to Lemma B.4 (b) and Lemma B.6 (c). We further obtain that
cB3
E2 pl 11" -1 21 11 11'1
|
14 1x"113
(75)
2
0
cBt
| 11" 1|3 1 1
-
1| 10011² 112
2
2
0=
+
|1400 - 1e" 1="1 - lleer u¹
1
(76)
xT-11
cBt:
||:e 1= "122, E1= NC0
M|c
-te²11
+ +1150 DD
(77)
2
t=0
1
cBI
Me 1 11111
cBt
4 1²'l(]
+ +1 11
(78)
2
D2
(79)
where the second inequality is due to the update rule of Eg and || - 1ell < D. and the third
inequality is due to Cauchy-Schwarz inequality and G. 3 I. Let C' = max( q
| ol we have
T-1
3.HV Vd
Hd 4)2
Σ B S 1 12
2 Σ k= 3K
8 k= Bk)
1=0
+ (GH Egllr + +,DD)
V=(A+] Σ
V [ + >
V [ot
(80)
1=1
T-1 +E
BUVV (
$ 12 11=DD
2E 21
3R EE=188
( BB))
3 V vd Em V=(2
+ (G B.DD
2 >
DV=10f +
(81)
2 >i= 8k
3.HVd
1 + 4)2
< 31E7'11E77 +
21 3k
8E EE k=1 Bx)2
2Cm N
3r
+ H.r3, ()GHB D)V
(82)
2NE Ei= 8c
where the first inequality is due to Eq. (79) and Lemma B.3 (a), the second inequality is due to Lemma B.3 (b) and Lemma B.5, and the third inequality is due to Lemma B.4 (c).
Therefore, we have
T-1
E D2
T-1
B.HV
B.H + 4)2 1k
Σ
E. [A.]
T 0=0
T3.
T
2
3k
1=
20m
3 3evdH + 4)
+
D)V
(83)
N
2N Eim 3k
Let 3, = f and Yt- = 77 Since we have ET- 1 < 11+ + log(T), we obtain
T
DE =0 (01
log T
+7).
E2
X( E.) J((H',)))
T
t=
m=
(84)
where we reach the conclusion.
19

---

Published as a conference paper at ICLR 2024
C.4 PROOF OF THEOREM 4.6
We denote q: Ei=1 X. then the update rule of μa can be represented as p++1 = a4 + B3 E.
According to assumption 4.1, the function J((0) L-smooth w.r.t {u.. E), then we have
X,J((M+11 Ex) S S ((((p)E)) + B WJ E.) E.gt + 2 E
L
(85)
Let B, = E, Ex= ; - J. E,)) then we have
Bi S 1
X (.,))
q:)
Eg 1
(86)
$ 2HB.VRR
V= X
1= B. VdRE
\ (.))))
LR
E |
(87)
2
LRRdRR
V X-
V- 19 +
Σ
V=
2
1=1
LBRRR -,3 VdR
Ezll
X JJ (.)
(88)
where the first incquality is due to Lemma B.I, the second incquality is due to || S Eo F s VdR and Lemma B.6 (b), and the last inequality is due Lemma B.6 (c). Let Be LRVd' and rearrange Eq. (88) we obtain
BI B.VRR
dR E
LB m
X
(..)111
& B, 4H+H d3,
V A
V
+
V [
2
2
(89)
So have
7
2B. VdR
77
L /.R m
E
|||
XV (0)1111
V [ Σ
2 [0t]. (90)
Note that we have
T-1
-(J((0=))))
= Σ
(1 - + +> (XT--1,(0,)) - -
I=U
t=
(91)
T-1
X - (1 - - 7 |B 2B
(92)
Σ
x BBBB.
(93)
11
20

---

Published as a conference paper at ICLR 2024
where the first inequality is due to the update rule of X and [J:(0)] - B. Then we have
T-1
m
T
m
Σ
B
=
E
E2
-01(0+)))-1(000
Σ
E
(J.( E.)
Ji(4+11, E++1))
(94)
T-1
m18
T-1
M X
2B + Σ E2
E|1e]]
(95)
t=0
1=0
T-1
T-1
$ 2m B
Σ t=
2B
Σ 1=
H E - Edlr,
(96)
where the first inequality is due to Eq. (93) and the Lipschitz continuous assumption of the function (O). Substittiing Eq. (96) into Eq. (90), we have
Σ
T-1
2mB E
2B + EE
H E1-1
Eelle
VdRT
LP9 ddR dR
811
V + V [
V=
(97)
According to Lemma B.3 (c), B.4 (c), and B.5. We know that |E Eelle S
25 8x)2
V [9 <
C where C' = max & ES 1loo), and V [A]] < 27/²
Then we have
bi.d 2mB 2TBDT-1 "t 2B ΣtO H
m
+ A Σ V ((0))1 s
25 &6)
VdRT
2m
CH L)2LVdRm
(98)
N
2N
Let B. = = and = we obtain
1I =0 =0
T-1
1
+ 7 +
(99)
T 0
3T
1=1
where we reach the conclusion.
D PROOF OF TECHNICAL LEMMAS
In this section, we provide the proof of lemmas in Appendix B.
D.1 PROOF OF LEMMA B.1
Since E and Σ are both diagonal matrix. Denote diag Σ) and â diag Σ). Then we have
d
Σ> 2 = Σ (0.2)) < _(a))
Σ
(z.)² = ||||| ||a| ||
(100)
1=1
1=1
We further have
ΣΣ (o,or))
(a.)
Σ
1o
(101)
i=1
i=1
Then reach the conclusion.
21

---

Published as a conference paper at ICLR 2024
D.2 PROOF OF LEMMA B.2
For À E [0, 1]. we have
)))))) + (1 - ())(())) = 1/0 + + + (1- - A) -/0 + +I =)
(102)
= B|AS(HI +
+ Σラ =)]
(103)
2 Elf (akl + +1 (1- ( +1 (1=)))))))
(104)
= = + (1-1))8),
(105)
where we reach the conclusion.
D.3 PROOF OF LEMMA B.3
(a): Since have Σ Σ,- 23 -i= XOO and X' E A We obtain
Σ + 2b 1 - Σ E + 2
(106)
Summing up it over 0, ..,, T
have
Σn 2b
3 = E,
2 E
+ 2
I.I.
(107)
Therefore, we have
1
1 Σx 1
(108)
26 Σ 31 + 2g
25 11=1 31 + En
(b): We have
Vd
E S
$
(109)
25 31 + 0
2 >
311
2 >1=11 Be
F
(c): We have
-23,E, E N
E++1 - -Eelle =||
Eille S
(110)
Σ, + +B, Em N.G.
I 23,E, Σm N.
< 23 |
F
(111)
Since |E
Vdd
and
Σm X S bvd. Then we have
28 RE &r
b3,d2
E1+1 - Egll v
(112)
25 11E1118
D.4 PROOF OF LEMMA B.4
(a). We first show that of is unbiased estimator of V F pe. (ar)).
E= = Ez |> =Fi(u + Σ z]] - Ez [x, (F.)))
(113)
= Ex,E, *F + -x²²]] x)]
(114)
EE ,z) 12 1x (x))
(115)
(116)
22

---

Published as a conference paper at ICLR 2024
(b). Since the is the diagonal elements of Σ, then we have
| = 1 1 o o (z + +o 02,) - Fi
(117)
|
+ o 0z₂) - Fi(e)))
(118)
1 # 0z |0 0z,
(119)
H
x
2 I x
| = 12| 1:: |2)
(120)
It follows that
1 Σ
| 12
En
Egg 1p S H 10 |z
(121)
N
N
j=1
Noticed that [=][|=]|*] S (d + 4)²
and
|
(122)
Imin + 2( Bz)5
0
where || Ilman denotes the minimum element in the input. Then we have
H² + 4)2 1k))
E E| S /1 11
oo (d+ 4)2
(123)
where we reach the conclusion.
(c): We have
|ل 112 = 0 0 2 (Fi(m) 0² 0z,) F1())))12
(124)
= =10, 0 0211 2F (M: +o 22) - F2(14))2
(125)
< ||0 0 2/112H 10 1 0
(126)
< H² o, $11 x x|00 x ||
(127)
Then we obtain
Ex |11g 1
< 22
0, 113 x ||o
E||
11
(128)
< H
o,
2
x
||ا
1
(d+
(129)
Note that for N i..d samples 2j, we have
1 N
1 <
V=
E2
11
(130)
N
H²
+
4)
(131)
N
Note that we have
0 + 2b
3,1 2 0,
2 0
+ 2
3,1.
(132)
km
kml
Then, we have
110 1 113 = -110,-11 11x S -110511e + 2
3z)b.
(133)
k=1
And
1
| 113- = =l1or1lo0 5
(134)
I mm + 2( Bx)E
23

---

Published as a conference paper at ICLR 2024
where || Il denotes the minimum element in the input.
we then have
b $1330
lo 1oo + +(E k=1 Gx.b6
|0
(135)
1100
min + 2(=x=1 Bk
b
11o 11:0 - -6 |lmin
(136)
1
|| min +2(2
b 11100 mmmn 2 0, we have
100
11
0
min
1107 12ollo
11:0 I +
I '1
(137)
100
min
If 1100 '0000 1lo0 &lllou Ilmin < O, we have
||o
7 1
o,
3
$1130
(138)
Therefore, let C max( ( ( we have
H2ld +
1)²C
Σ 0
(139)
N
N
j=1
where we reach the conclusion.
D.5 PROOF OF LEMMA B.5
We have
V. [A] E& - =
-
(140)
E. 1lll1
10' 21
(141)
where we reach the conclusion.
D.6 PROOF OF LEMMA B.6
According to Lemma B.4 (a) and (c), we know that of is an unbiased estimator of the gradient ((,)) and the variance of ýf is bounded. Therefore q: >m Mgg.. the results Lemma B.6 can be directly obtained by Lemma 1, 7, and 8 in Zhou et al. (2022b).
UPDATED RULE UNDER TRANSFORMATION
To avoid the scaling problem, we can employ monotonic transformation for the aggregated objective, ie. F(x))) A F- where ý and ā denote mean and stand deviation of aggregated function values A F((xx) = Em AxF,(z,), = 1,..., .N. Then by applying this rescaling strategy, the update rule for μ4 and Σ, in t-th iteration can be written as
B
N
m 1i
(xF,(,,)) A 6¹
M1t1 = pr
azy-
p
(142)
N
1=1
3r
m E
XF((,)))
p
Ex1
Ex'
+
diag
Σ,
[diag (zz, (1)(2z -H1) -E,"
(143)
24

---

Published as a conference paper at ICLR 2024
F ADDITIONAL MATERIALS FOR SECTION 6
F.1 SYNTHETIC PROBLEMS
Evaluation Metries. The Pareto optimal set of problem (19) is P1 = f E [-0.01, 0.01]] Therefore. the result is evaluated by calculating the Euclidean distance between solution æ and the set Pj. which is denoted & = (ar Pi). We denote the Pareto optimal set of problem (20) as P2. Since the Pareto front of problem (20) is concave, the solution of the ASMG method will go to the boundary its Pareto optimal set, i.e. P2 = { x E [10.1,0.1]] C P2. Moreover, For ES and CMA-ES methods, since their optimization objective is Fi(z) F2(2), the corresponding solution set is P2. Therefore, the result of these three methods problem (20) is evaluated by
dist( (x, P2). The Pareto optimal set of problem (2l) P3 {or x 0). Therefore, the result is evaluated by 3 dist(z, Ps).
Implementation Details. For all the methods, we initialize 140 from the uniform distribution Uni 1], and set Eg = I. The ASMG method uses a fixed step size of 3 = 0.1 and 7/- = =1/(t + 1). employ the default step size from Salimans et al. (2017), i... 3 = 0.01.
For the ES method, For the BES method, we adopt the default step size from Gao Sener (2022). i.c., B = 0.01. We employ the default hyperparameter setting from He et al. (2020) for the MMES method. We then assess these methods using varying sample sizes, i.e. N E {10, 50, 100]. The mean value of & over 3 independent runs is reported.
Result. Figure 2 and 3 show the results on three 100-dimensional synthetic problems with sample sizes N = 10 and N = 100, respectively. Combining these results with the result from Figure we observe consistent performance from the proposed ASMG method, consistently achieving high precision across all three cases, i.e. 10-1 for N 10, 50, 100. The CMA-ES method shows convergence with high precision on the Shift 4 Ellipsooi problem when N = 10 and 50. However, it fails to converge when the sample size is very small, i.c.. N 10. The same performance also occurs on the Shift 14 -Ellipsoid problem for the CMA-ES method. It can achieve 10-1 precision when N = 50 and 100, but only achieve 10 precision when N 10. It still fails the Mixed EllipssoidRRastriiinn 10 problem when N = 50 and 100. The MMES method also cannot reach a high precision these problems. The ES and BES methods do not converge in any of the settings, indicating that it could be challenging for these methods to optimize these non-smooth or non-convex problems. These results show the effectiveness of the proposed ASMG method.
Figure 4 presents the results for the shift 17 elelliioo problem with a sample size of N = 100 across various problem dimensions, i.c. d {200, 500, 1000}. The CMA-ES method can still converge when d = 200, but does not converge when = 1000. In contrast, the ASMG method consistently achieves high precision across all three settings, demonstrating its effectiveness in handling high-dimensional problems.
Logui
Logur
-2
CPA-ES ES
CNAES
CKAES
B15
ASNG
AGVG
ASMG
Iteration. [xx1o?)
Iteration. T (x10P)
Iteration. T T(X10?)
(a) Shift ( Ellipsooi.
(b) Shift ( Ellipsoid.
(c) Mixed Ellipsoid-Rastriginn 10.
Figure 2: Results on the synthetic problems with 10 samples (i.e., N = 10).
25

---

Published as a conference paper at ICLR 2024
Logue
Log
-2
CIN
OMAES
ONNES
-3
BI5
44
DC1
HIES
PMES
0
3
2
3
Iteration. (x100)
Iteration. TXx10")
Iteration. T (x110
(a) Shift E-llissood..
(b) Shift 1y Elliisood.
(c) Mixed Seiisoidd-Ratrigeenn 10.
Figure 3: Results the synthetic problems with 100 samples (i.e., N = 100).
0-
Log.uC
Log
-2
CIA-ES ES
CMAES
CNAES
-3
AGMG
Iteration. [XX10
Iteration. T (x10P)
Iteration. T [(X10P))
(a) d=200.
(b) d=500.
(c) d=1000.
Figure 4: Results on the shift -ellippsod problem with = 100 and different problem dimension d.
F.2 BLACK-BOX MULTI-TASK LEARNING
Details CLIP. CLIP is a widely adopted vision-language model that trains an image encoder h-mago(-) (-) and a text encoder (-xa(-) jointly by aligning the embedding space of images and text. Given an image and a set of class names {yA Hk CLIP obtain image features himage (æ) and set of text features { (p: y/4 ) where p E R represents the token embedding of the shared prompt. The image æ is classified into the class y/s that corresponds to the highest similarity score Mimuge (a:) Mex (p: yi) among the cosine similarities between the image features and all the text features. In the zero-shot setup, the shared token embedding is transformed from the prompt "a photo of a", while in the prompt tuning setup, the token embedding of the shared prompt is optimized directly to enhance performance.
Loss function C.. In the context of multi-task learning, we consider a scenario involving m tasks, each having its own dedicated training dataset. For task i, have dataset D, {(xx, }. For each training epoch, we sample a mini-batee mani-batch B; from D; and the function L; in Eq. (22) can be formulated
(B (Me, Av))=
Σ ((M.(Au;))..)) (æ.9)EB,
where l can be cross-entropy function for classification problem and M. denotes CLIP model in our setting.
Datasets. We conduct experiments on two MTL benchmark datasets (Lin & Zhang, 2023), i.e., Office-31 (Saenko et al., 2010) and Office-home (Venkateswara et al., 2017). The Office-3/ dataset includes images from three different sources: Amazon (A), digital SLR cameras (D), and Webcam (W). It contains 31 categories for each source and total of 4652 labeled images. The Office-home dataset includes images from four sources: artistic images (Ar), clip art (CI), product images (Pr), and real-wortd images (Rw). It contains 65 categories for each source and total of 15,500 labeled images. For those two datasets, we treat the multi-class classification problem on each source as a separate task.
26

---

Published as a conference paper at ICLR 2024
Implementation Details. Following the setup of Zhou et al. (2022a), conduct experiments based on the CLIP model with ResNet-50 as the image encoder and use a prompt with 4 tokens for the text encoder where both the image and text encoders are kept frozen during the experiments. For zero-shot, we apply the default prompt "a photo of a {class)".
140 0 and Σn I as initialization. For all baseline methods except the zero-shot setting, we optimize the prompt with batch size of 64 for 200 epochs, the population size N is set as 20 for Office-3/ and 40 for Office-home, while A is sampled from the normal distribution as described in the Sun et al. (2022a), i.e. (N, )a), where a. is the standard deviation of word embeddings in CLIP. For ASMG and ASMG-EW methods, the step size is fixed 3 0.5. The coefficient y in the ASMG method is set as 7/- = 1/(t + 1). For the ES method, we employ the default step-size of ES in Salimans al. (2017), i.e., 0.01. For the BES method, we perform grid search on step size, i.e., 3 is chosen from (0.5, 0.1, 0.013. For the MMES method, we employ the default hyperparameter setting from He al. (2020). Additionally,
For all methods,
evaluate the performance of the method on different dimensions of 2, specifically d E {256, 512, 1024]. The CMA-ES method implemented using the official implementation available while we implement the ES and BES method by ourselves.
G RELATIONSHIP TO GRADIENT-BASED MOO
For previous methods on MOO, the most relevant method to our approach is gradient-based MOO methods (Yu al., 2020; Liu et al., 2021; Fernando et al., 2022; Zhou et al., 2022b), as they also aim at finding the Pareto optimal solution or the Pareto stationary solution. A typical gradient-based method is the MGDA method (Désidéri, 2012), which also solves max-min optimization problem to obtain the weights. However, the proposed ASMG method is not typical MGDA-type method. The max max-min min optimization problem proposed in MGDA-type methods related to the true gradient of the parameters. They add regularization term ||]] to control the norm of the aggregated gradient. In our case, the update is conducted on a Gaussian distribution, and we need to jointly update the mean and covariance matrix. We use Kullback-Leiblle divergence regularize the distance between two distributions, i.e. and 0.. Therefore, the form of the proposed max-min optimization, i.e. Eq. (4), differs from MGDA-type methods, and the solution process is also different. However, our max-min problem can also lead to a simple quadratic programming problem for the aggregation weights computation.
27


Reviews:
[{"review_id": "JSNJGGOfHK", "reviewer": "Reviewer_hUW7", "summary": "The paper proposes a novel algorithm called Adaptive Stochastic Gradient Algorithm for Black-Box Multi-Objective Learning (ASMG) to optimize multiple potentially conflicting objectives with function queries only. The authors provide the detailed discussion of the original MOO and the corresponding Gaussian-smoothed MOO and provide theoretical proofs for the convergence rate of the algorithm. The authors also demonstrate the effectiveness of the ASMG algorithm on various numerical benchmark problems.", "questions": "1. How does the proposed algorithm compare to other black-box multi-objective optimization methods? Since only comparison with the ES-based method is discussed in the paper. \n2. What is the computational complexity and runtime of the proposed algorithm compared with other black-box multi-objective optimization methods?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Originality: The authors provide a novel approach to black-box multi-objective optimization with the new concept of \"adaptive\" stochastic gradient approximation that has a theoretical convergence guarantee.\n\n2. Quality: The paper provides a rigorous theoretical analysis of the proposed algorithm, such as proofs of convergence rate. The authors also demonstrate the effectiveness of the algorithm on multiple numerical benchmark problems, showing that it outperforms the ES method in terms of convergence speed and solution quality.\n\n3. Clarity: The paper is well-written and easy to follow, with clear explanations of the algorithm and its theoretical properties.\n\n4. Significance: The proposed method has the ability to optimize multiple objectives simultaneously with function queries only, which is the scenario of many MOO-based learning problems, such as tasks involving large language models that are only allowed for access with APIs.", "weaknesses": "1. In the introduction, lack of discussion on advantages of the Gaussian-smoothed MOO, compared with the traditional method. \n2. Lack of comparison with more recent state-of-the-art methods. The authors only compare their algorithm with the ES-based method. \n3. Limited discussion of the algorithm's computational complexity and runtime.", "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": "BMM9mgA2Iv", "reviewer": "Reviewer_J6Rt", "summary": "This paper proposes a ASMG algorithm for black-box multi-objective optimization. It is the first to design a stochastic gradient algorithm for black-box MOO with a theoretical convergence guarantee. The authors also prove the convergence rate for the proposed ASMG algorithm in both convex and non-convex cases. Empirically, the proposed ASMG algorithm achieves competitive performances on both toy examples and CLIP models.", "questions": "1. How likely does the assumption that the covariance matrix Σ is a diagonal matrix hold?\n\n\n2. I'd like to see how likely the assumptions in Section 4, especially the convex case, hold? For example, in 6.1 SYNTHETIC PROBLEMS, the", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I think the studied topic of black-box MOO problem is very important, especially with the emergence of  large language models, multi-modality models. This is a good timing to investigate on this topic given that the most popular APIs we use (ChatGPT, etc.) are only accessible for inference.\n\nTo the best of my knowledge, this paper is the first one that designs a stochastic gradient algorithm for black-box MOO. Moreover, it comes up with a theoretical convergence guarantee. For convex case, it possesses a convergence rate $\\mathcal{O}\\left(\\frac{\\log T}{T}\\right)$. For non-convex case, it has a $\\mathcal{O}\\left(T^{-\\frac{1}{2}}\\right)$ convergence rate to reach a Pareto stationary solution.\n\nI also think the CLIP example is very important. This shows that the authors do not only want to test the proposed algorithms on toy examples. They actually would like to use it on those state of art algorithms, which I really appreciate it.", "weaknesses": "think this paper can be improved in several ways:\n\n1. More discussions about more related works, such as recent KDD papers about one important application of multi-objective optimization in learning to rank https://dl.acm.org/doi/abs/10.1145/3580305.3599870 and https://dl.acm.org/doi/abs/10.1145/3580305.3599482\n\nOne more example is the lack of discussion about the seminal work in MOO for Multi-task learning https://arxiv.org/pdf/1810.04650.pdf\n\n2. How likely does the assumption that the covariance matrix Σ is a diagonal matrix hold?", "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": "RrTWWWJ2Ow", "reviewer": "Reviewer_ZfhH", "summary": "This paper proposes a MGDA-type gradient-based algorithm for solving the problem of black-box multi-objective optimization. Inspired by the stochastic gradient approximation method in black-box optimization, the objective of MOO is replaced by the expected loss where the decision is sampled under some parametric search distribution. Then the MOO problem is transformed into the problem of finding the optimal search distribution with minimal expected loss. When assuming the search distribution to be Gaussian, the gradient of the distribution parameters (mean and variance) is accessible, making it possible to apply gradient-based MOO algorithms. The relation between the two problems and the convergence rate are analyzed. Numerical experiments are conducted to verify the effectiveness of the proposed algorithm compared to evolutionary algorithms.", "questions": "1. The proposed method assumes that the covariance matrix of the search distribution is a diagonal matrix. As I understand, this assumption indicates that the different dimensions of x are independent. Can you justify this assumption? I wonder if there is any performance gap with/without using this assumption.\n\n2. The Monte-Carlo sampling approach for calculating the expectation may bring additional computational complexity to the proposed algorithm. Can you analyze the complexity or provide some empirical results on the real running time?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The idea of applying stochastic gradient approximation method to black-box MOO problem sounds novel.\n\n2. This paper is technically sound. The analysis on the relation between the original black-box MOO problem and the smoothed version in convex/non-convex cases is interesting. \n\n3. This paper is well written in general and easy to follow.", "weaknesses": "1. The related work section only includes evolutionary methods and BO for multi-objective black-box optimization. The relevance to previous works on MOO/stochastic gradient approximation should also be clarified. A detailed discussion of technical difficulties in applying stochastic gradient approximation to black-box MOO may help better highlight the significance and technical novelty of this paper. \n\n2. The experiment considers evolutionary algorithm as the only baseline, which seems insufficient. There are also other major branches of black-box MOO algorithms, e.g., multi-objective Bayesian optimization [Zhang & Golovin, 2020] or multi-objective bandits, that should be compared.", "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": "LoQjZaXWCN", "reviewer": "Reviewer_w58H", "summary": "In this paper, the authors propose a gradient-free black-box multi-objective optimization (MOO) method with dynamic weighting of objectives, leveraging concepts developed in the gradient based multi-objective optimization literature. The proposed method achieves this by deriving a gradient-free estimates for the objective gradients with respect to the parameters of the search distribution, and solving for dynamic weights for each objective calculated based on the aforementioned estimates. The authors provide relationship between the solutions to the original MOO problem and the solutions of the Gaussian smoothed MOO problem, which the proposed method find. The authors further provide theoretical convergence guarantees for the proposed method, and provide empirical validation for the validity of the proposed method.", "questions": "* How doe the proposed method scale with the size of the parameter to be learned?\n\n* How sensitive is the proposed method to the stochasticity of the objectives (i.e. when the average over all data-points is estimated by the average of over a mini batch)?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper provides a black-box multi-objective optimization algorithm in the stochastic setting with theoretical convergence guarantees, which is a novel contribution to my knowledge.\n\n* The paper provide empirical evidence for the efficacy of the proposed method over existing methods using synthetic and real world benchmarks.\n\n* The paper is fairly easy to read, and the ideas are presented well.", "weaknesses": "* The proposed method assumes full access to the objective function, while in most applications (like in multi-task learning setup used in the experiment setup), full evaluation of objectives might not be possible or might be costly. The theoretical guarantees provided does not seem to cover this. However, the authors provide empirical evidence for the proposed method in this setting.\n\n* The setting considered might be not suitable for very large parameter spaces (i.e. when d is very large), which is the case when the decision variable is represented by a deep neural network.\n\nMinor comments:\n\n* The Pareto stationarity defined in Proposition 2.3. may not be a necessary condition for Pareto optimality when $\\mathcal{X} \\subset \\mathbb{R}^d$ (Consider when there is a global minimum for all the objectives at a boundary of  $\\mathcal{X}$)", "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)