DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymptotic Convergence
Authors: Yang Jiao
Kai Yang
Chengtao Jian
Venue: ICML 2025 poster (2025)
Keywords: Distributed Algorithm
Trilevel Optimization
Zeroth-Order Optimization
Primary area: general_machine_learning->scalable_algorithms

Abstract: Trilevel learning (TLL) with zeroth order constraints is a fundamental problem in machine learning, arising in scenarios where gradient information is inaccessible due to data privacy or model opacity, such as in federated learning, healthcare, and financial systems. These problems are notoriously difficult to solve due to their inherent complexity and the lack of first order information. Moreover, in many practical scenarios, data may be distributed across various nodes, necessitating strategies to address trilevel learning problems without centralizing data on servers to uphold data privacy. To this end, an effective distributed trilevel zeroth order learning framework DTZO is proposed in this work to address the trilevel learning problems with level-wise zeroth order constraints in a distributed manner. The proposed DTZO is versatile and can be adapted to a wide range of (grey-box) trilevel learning problems with partial zeroth order constraints. In DTZO, the cascaded polynomial approximation can be constructed without relying on gradients or sub-gradients, leveraging a novel cut, i.e., zeroth order cut. Furthermore, we theoretically carry out the non-asymptotic convergence rate analysis for the proposed DTZO in achieving the $\epsilon$-stationary point. Extensive experiments have been conducted to demonstrate and validate the superior performance of the proposed DTZO.

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymptotic Convergence
Yang Jiao
Kai Yang'
Chengtao Jian
Abstract
machine learning applications, such robust hyperparame- ter optimization (Sato et al., 2021; Giovannelli et al., 2025), domain adaptation (Choe et al., 2023), machine translation (He et al., 2024), robust neural architecture search (Guo et al., 2020; Jiao et al., 2024), and so on. The general form of a trilevel learning problem can be expressed as,
Trilevel learning (TLL) with zeroth order con- straints is fundamental problem in machine learning, arising in scenarios where gradient in- formation is inaccessible due to data privacy model opacity, such as in federated learning, healthcare, and financial systems. These prob- lems are notoriously difficult to solve due to their inherent complexity and the lack of first order in- formation. Moreover, in many practical scenarios, data may be distributed across various nodes, ne- cessitating strategies to address trilevel learning problems without centralizing data servers to uphold data privacy. To this end, an effective dis- tributed trilevel zeroth order learning framework DTZO is proposed in this work to address the trilevel learning problems with level-wise zeroth order constraints in a distributed manner. The proposed DTZO is versatile and can be adapted to wide range of (grey-box) trilevel learning problems with partial zeroth order constraints. In DTZO, the cascaded polynomial approximation can constructed without relying on gradients or sub-gradients leveraging a novel cut, i.e., zeroth order cut. Furthermore, we theoretically carry out the non-asymptotic convergence sis for the proposed DTZO in achieving the E- stationary point. Extensive experiments have been conducted to demonstrate and validate the supe- rior performance of the proposed DTZO.
min (1 22, .33)
8.t. 22 arg min f (2 22's 0z) ina
s.t. 23 = arg min fa (1, x2'. xzs)
var.
21, 22 23
where fi, f2. fa denote the first, second, and third level ob- jectives, and œ E T2 32 E ERda 23 Rdda are variables. Existing trilevel learning approaches focus on scenarios where TLL problems mation available at each level. However, situations where first order information is unavailable (i.e., V11 f2, V fs are non-available), such as when black-box models are em- ployed, remain exper-ex Additionally. in trilevel learning applications, data may be distributed across various nodes, necessitating strategies address trilevel learning problems without centralizing data servers in order to uphold data privacy (Jiao et al., 2024).
be addressed with first order infor-
analy-
Complexity of Addressing TLL with Zeroth Order Con- straints: The complexity involved in solving problems char- acterized by hierarchical structures with three levels is signif- icantly greater than that of bilevel learning problems (Blair, 1992; Avraamidou, 2018). It is worth mentioning that finding a feasible solution in TLL problem is NP-hard since it necessitates addressing the inner bilevel learning problem, which is NP-hard (Ben-Ayed & Blair, 1990; Sinha et al., 2017). Existing approaches are not applicable for address- ing TLL with zeroth order constraints, as they either rely on the first order information to solve the TLL problems (Jiao et al., 2024: Sato et al., 2021) focus on single-level and bilevel zeroth order learning problems (Fang et al., 2022; Qiu et al., 2023).
1. Introduction
Trilevel learning (TLL), also known as trilevel optimization, pertains to nested optimization problems involving three levels of optimization, thus exhibiting a trilevel hierarchical structure. Trilevel learning has been widely used in many
Department of Computer Science and Technology, Tongji Uni- versity. Correspondence to: Kai Yang <kaiyang @ www.gi.cn...c.........
To this end, an effective Distributed Trilevel Zeroth Order learning (DTZO) framework is proposed in this work. Specifically, we first introduce the cascaded zeroth order polynomial approximation for the trilevel learning problems,
Proceedings of the nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
Method
Bilevel (FO)
Bilevel (ZO)
Trilevel (FO)
Trilevel (ZO)
FEDNEST (Tarzanagh et al., 2022)
((1/e)
ADBO (Jiao et al., 2023)
(11e²)
MDBO (Gao et al., 2023)
((1/e²)
FedBiOAcc (Li et al., 2023)
((1/2-5)
MemFBO (Yang et al., 2025)
0(1/e155
Fe (Qiu et al., 2023)
0(1/e)
AFTO (Jiao et al., 2024)
0(1/e))
The proposed DTZO
0(1/2)
Table Comparison of non-asymptotic convergence rates for distributed nested optimization methods under first order (FO) and zeroth order (ZO) scenarios. This work is the first to provide the theoretical guarantees for trilevel zeroth order optimization.
which consists of the inner layer and outer layer polynomial approximation. Next, how to generate the novel zeroth order cuts without using gradients or sub-gradients to gradually refine the cascaded polynomial approximation discussed. Zeroth order cut type of cutting plane that does not rely on first order information during generation. Finally, the distributed zeroth order algorithm is developed to ad- dress trilevel zeroth order learning problems (i.e.. TLL with level-wise zeroth order constraints) in distributed manner. Additionally, a novel concept of soft constraint is intro- duced in this work explain why the lower-level problem in bilevel and trilevel optimization can be approximated or relaxed to some extent. Theoretically, we demonstrate that the proposed zeroth order cuts can construct polynomial relaxation for TLL problems, and this relaxation will be gradually tightened with zeroth order cuts added. Addition- ally, we also analyze the non-asynn -onaaptptooicc convergence rate, ie., iteration and communication complexities, for the pro- posed DTZO to achieve the c-stationary point. worth highlighting that this the first work address the trilevel zeroth order optimization problems while establishing the- oretical guarantees for the proposed algorithm. Table presents a comparison of the non-asymptotic convergence results between the proposed DTZO and state-of-the-art methods. Our contributions can be summarized as follows.
posed DTZO.
2. Related Work
2.1. Distributed Zeroth Order Optimization
Zeroth order optimization is widely-used for addressing ma- chine learning problems where obtaining explicit gradient expressions challenging or impractical (Liu al., 2018c; Chen et al., 2019; Wang al., 2018b; Héliou al., 2021; Cai et al., 2021; Gao & Huang, 2020; Yue et al., 2023; Li
et al., 2022; Ren et al., 2023; Nikolakakis et al., 2022: Tu et al., 2019; Rando et al., 2024). In practical applications of zeroth order optimization, data may be distributed across different nodes. To address zeroth order optimization prob- lems in distributed manner, the distributed zeroth order optimization methods have recently gareredd significant at- tention, e.g., Lian et al. (2016); Tang al. (2020); Fang et al. (2022); Chen et al. (2024a); Akhavan et al. (2021); Sahu et al. (2018); Shu et al. (2023). Furthermore, to tackle the bilevel zeroth order optimization problems in a distributed man- ner, the federated bilevel zeroth order optimization method FedRZO., (Qiu al., 2023) has been proposed. However, how address the higher-nested zeroth order optimization problems, c.g., trilevel, in distributed manner remains under-explored. To the best of our knowledge, this is the first work that considers how to address the trilevel zeroth order optimization problems.
Different from the existing works on single-level and bilevel zeroth order learning, this work takes an initial step towards addressing trilevel zeroth order learning. To the best of our knowledge, this is the first work to address the trilevel zeroth order learning problems.
2.2. Trilevel Learning
Trilevel learning has found applications in various fields within machine lcarning. A robust neural architecture search (NAS) approach that integrates adversarial learning with NAS introduced Guo et al. (2020). The robust NAS can be viewed as trilevel learning problem, as discussed in Jiao et al. (2024). A trilevel learning problem compris- ing two levels pretraining, fine-tume fine-tuning and hyperparameter optimization, is explored in Raghu et al. (2021). In Garg et al. (2022), the trilevel learning problem, which involves data reweighting, architecture search, and model training, is
An effective framework DTZO with novel zeroth order cuts is proposed for tackling trilevel zeroth order learning problems in distributed manner. Different from the exist- ing methods, the proposed DTZO is capable of constructing the cascaded zeroth order polynomial approximation with- out using gradients or sub-gradients.
3. Extensive experiments on black-box large language mod- els (LLMs) trilevel learning and robust hyprrparameter op- timization substantiate the superior performance of the pro-
2

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
investigated. In Sato al. (2021), the robust hyperparam- eter optimization is framed trilevel learning problem, and a hypergradient-based method is proposed to address such problems. In Choe et al. (2023), a general automatic differentiation technique is proposed, which can be applied to trilevel learning problems. Additionally, a cutting plane based distributed algorithm is proposed in Jiao et al. (2024) for trilevel learning problems. Nevertheless, existing meth- ods predominantly rely on first order information to solve trilevel learning problems. This is the first framework that can be used to solve trilevel learning problems withou! relying on first order information.
where f1,5- fa.j: respectively denote the first, second, and third level objectives in 1th worker, 21 [Rd 22 R 23 E Rd are variables. The first order information of functions f1.j, f2.5. fs.j, i.e. Vfi.. V f2.5, Vfs.s, is not available in Eq. (2), corresponding to the level-wise ze- roth order constraints. To facilitate the development of distributed algorithms parameter-server architecture (Jiao et al., 2023; Assran et al., 2020), the distributed TLL with zeroth order constraints in Eq. (2) is equivalently reformu- lated as consensus trilevel zeroth order learning problem as follows.
min N fi. (..,, 23..))
22.6
s.t. F1 = 21, Vj = 1,...,
2.3. Cutting Plane Method
{0 ) 22 = arg min j= f2.5 (Z1, (Z,, L2,5 23.3)
Cutting plane methods are widely used in convex optimiza- tion (Bertsekas, 2015; Franc et al., 201 1), robust optimiza- tion (Yang et al., 2014; Bürger et al., 2013), and so on. Recently, there has been notable interest in leveraging cut- ting plane methods to tackle distributed nested optimization problems. It is shown in Jíao et al. (2023) that the nested optimization problem can be transformed into a decompos- able optinization problem by utilizing cutting plane method, which significantly facilitates the design of distributed al- gorithms for nested optimization. In Jiao et al. (2023), the cutting plane method is employed to tackle bilevel opti- mization problems in a distributed manner. Similarly, Chen et al. (2024d) utilizes the cutting plane method to address distributed bilevel optimization problems within downlink multi-cell systems. Furthermore, Jiao al. (2024) applies the cutting plane method to solve distributed trilevel op- timization problems. However, the existing cutting plane methods for nested optimization rely on the gradients or sub- gradients to generate cutting planes, which is not available in zeroth order optimization. In this work, the proposed DTZO is capable of generating zeroth order cuts for nested opti- mization problems without using gradients or sub- uub-gradients. Discussions about the novelty of the proposed zeroth order cuts are shown in Appendix J.1 and Table? 7.
(<2.''),²²²
s.t. L2,5 = z2' Vj = 1,... .NN
{a3 ) 33 2
arg min -ラ f3. (21, 23.5)) (
s.t. 03.j = 23 2 Vj = 1, .N { 3 ( ), { |- 21 22, Z3.
var.
(3)
where 11, E Rd,, 22 E ER Lz. E Rd denote the local variables in jth worker, 21 E Rd 22 E Rd 23 E Rd denote the consensus variables in the master, N denotes the number of workers.
Overview of the proposed framework. In Sec. 3.1, the construction of cascaded zeroth order polynomial approx- imation for the trilevel zeroth order learning problem is proposed, which consists of the inner layer and outer layer polynomial approximation. Then, how to gradually update zeroth order cuts to refine the cascaded polynomial approx- imation is discussed in Sec. 3.2. Finally, a distributed zeroth order algorithm is developed to effectively address the trilevel zeroth order learning problem in a distributed manner in Sec. 3.3.
In addition, this work takes an initial step toward introducing the novel concept of soft constraints in bilevel and trilevel optimization, as discussed in Section 3.1.1. To improve the readability of this work, The notations used in this work and their corresponding definitions are summarized in Table 3.
3. Distributed Trilevel Zeroth Order Learning
In the practical applications of trilevel zeroth order learning, data may be distributed across multiple nodes (Jiao et al., 2024). Aggregating data on central servers may pose signifi- cant privacy risks (Subramanya & Riggio, 2021). Therefore, it is crucial to develop an effective framework to address trilevel zeroth order learning problems in a distributed man- ner. The distributed trilevel zeroth order learning problem can be expressed as
3.1. Cascaded Zeroth Order Polynomial Approximation
In this section, how to construct the cascaded zeroth order polynomial approximation for trilevel zeroth order learning is introduced. The proposed cascaded zeroth order polyno- mial approximation consists of two key parts: 1) the inner layer polynomial approximation and 2) the outer layer poly- nomial approximation, which will be discussed below.
222 x33 s.t. 3D = arg min ΣØ=1 f2.g (x) 22'22 xxa) 2=''
min Σド=
1. INNER LAYER POLYNOMIAL APPROXIMATION
(2) In trilevel learning, the third level optimization prob- lem can be viewed as the constraint to the sec- ond level optimization problem (Jiao et al., 2024;
s.t. 33 = arg min Σjn N f2, (2), Dzg x33))
var.
31, 22 33,
3

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
Pan et al., 2024; Kwon al., 2023; Jiang et al.,
(Kautz et al., 1996; Régin, 2011; Wilson et al., 2022). This offers a new perspective on why the lower-level problem can be approximated or relaxed to some extent in bilevel and trilevel optimization (Jiao et al., 2023). For example, in bilevel neural architecture search (Liu et al., 201 rather than computing the optimal solution for the lower-level opti- mization problem, the results obtained after a single gradient descent step can be used as an approximation each itera- tion. Similarly, in bilevel meta-learning (Finn et al., 2017), the results obtained after multiple gradient descent steps can serve as an estimated optimal solution for the lower-level problem. In bilevel adversarial learning (Madry et al., 2018), which is a min-max optimization problem, the results af- ter several projected gradient descent steps are used as the approximation of the optimal solution for the lower-level problem. Moreover, in trilevel learning, AFTO (Jiao et al.. 2024) uses the results after K communication rounds to replace the optimal solution to the lower-level optimization problem in federated trilevel optimization problems. To our best knowledge, this is the first work to introduce the concept of seft constraints into bilevel and trilevel optimization.
2023), it equals the constraint (i } 21,22 22 25)
{
0, where din (in(( ), 21, 22', za) = 11
#3
arg min Σj f2,5(21, 23. x..5") s.t. = z3' Vill?. In (ms.)").zs"'
many bilevel and trilevel machine learning applications, e.g., neural architecture search in Liu et al. (201 8a), robust hyper- parameter optimization in Jiao et al. (2024), the lower-level optimization problem serves as a soft constraint (Kautz et al., 1996) to the upper-level optimization problem, i.c., this constraint (constraint Pin [ 21, =2'; 23) = in our problem) can be violated to a certain extent while still yielding a feasible and meaningful solution. Inspired by Jiao et al. (2023); Chen et al. (2024d), the cutting plane based method is utilized to construct a decomposuble poly- nomial relaxation for this constraint, which significantly fa- cilitates the development of distributed algorithms. Specifi- cally, the inner layer zeroth order cuts are utilized to ap- proximate the feasible region with respect to constraint din (0a.s): , Z2', , =3) 0. Zeroth order cuts refer to the cutting planes that do not rely first order information during generation. In this section, we focus on the con- struction of cascaded polynomial approximation, and how to generate the zeroth order cuts is discussed in detail in the next section 3.2. Consequently, the feasible region formed by inner layer zeroth order cuts in tth iteration is,
3.1.2. OUTER LAYER POLYNOMIAL APPROXIMATION
Likewise, the lower-level optimization problem in Eq. (5) can be regarded as the constraint to the upper-level op- timization problem. Defining hi"((333.) J. 31, z2' 23)
in E D3,5 +b T3.j + Eie(,a)) in 27 + d 2, +
c
Ph = [a in a 23 bb] 23, DiE Shi of
T
thi 23 + dny 22' + ttm. This constraint equals
2, 2,t,22 22²+ +db,, x2' +ej Mi, +dl
22, 23) = 0, where Pont (1225): (233)): 21, 22;
(4)
Dour (1 (1x2,)) }, (ors. }. 22,
where 2i, =b b 2 Rnd E Rd. [2]] 2. E ER 1,2,3, ay E Rd, bih E Rd, on ERd d. ER4, and e/" ER- are the parameters of 7th inner layer zeroth order cut, Enn 2 is constant. By using
arg min Σj f2.j (21, D2,5, 233,)
{22s}
}- (=22'))22²'
=I1
112.
s.t. D2.j - =2 Vjj
22
( 21, 22, 23) S Cin, 4Z
the inner layer polynomial approximation according to Eq. (4), the resulting problem can be written as.
(6)
The constraint dour { ,1, za) = 0 also serves as a soft constraint to the upper-level opti- mization problem. Outer layer zeroth order cuts are utilized to construct the polynomial approximation for the feasible region with respect to the constraint Pout @out({ ((#2,)) J. (x }. 21, Z2, 2z) = 0, that is, P = (nput (( ((x2,) 1. ) 21 22, 23) S Eoutt vl}. : (7) where
min Σj"11 fi (3 22.;; X3.1) s.t. 11,1 21, Vj= 1,... .N (02.)), 22 = arg min Σj= /2.((211 22.s' was)) /
s.t. 22,j = z2' / Vj= 11...... N (1 }, 21, x2' 23) E Pl
var.
{ (x2.j J. {x3.) } - Ø2, 23.
ngut(1x2 (f ). 12,,
#2, #2,
(5) Soft Constraint, In bilevel and trilevel optimization, the lower-level problem is typically treated as a constraint for
Σi= Ex= out 2²,- + b Ui.j + Σ out 27 +
agy.
dou 2, + equi, and &out 2 is pre-set constant. Based the upper-level problem (Liu et al., 2022; Jiao et al., 2025; Kwon et al., 2024). In this work, we provide a novel in- sight into this constraint, i.c., it is indeed a soft constraint in many bilevel and trilevel optimization applications. A soft constraint refers to a constraint that can be partially violated without rendering the optimization problem meaningless
on Eq. (7), the resulting cascaded zeroth order polynomial approximation problem can be written as,
min Σ/ (Z L2.j 23.j) s.t. xi. = 21, Vj = 1,.... ,N (war) ø1, 22, 23) E P var. (01s) (22. f #1, 22, 23,
(8)

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymptotic Convergence
where nout ERd, boy E RR, coul ER4, d.rt ERo, and equt ER! are parameters of 7th outer layer zeroth order cut.
L-Lipschitz continuous gradient. The proof is provided in Appendix C.
3.2. Refining the Cascaded Polynomial Approximation
3.2.2. GENERATING OUTER LAYER ZEROTH ORDER CUT yth iteration, (1ahgh ( 21, z3). the new outer layer ze- roth order cut will be generated to refine the outer layer polynomial approximation in Eq. (7) as follows.
For every T iteration, the zeroth order cuts will be updated to refine the proposed cascaded polynomial approximation when < T Different from the existing cutting plane meth- ods for nested optimization, the proposed zeroth order cuts can be generated without using gradients or sub-gradients, which is why we refer to them as zeroth order cuts. Specifi- cally, in t iteration, the zeroth order cuts will be updated by three key steps: 1) generating inner layer zeroth order cut; 2) generating outer layer zeroth order cut; 3) removing inac- tive zeroth order cuts, which will be discussed as follows. In addition, we demonstrate the proposed zeroth order cuts can construct relaxation for the original feasible regions in Proposition 3.1 and 3.2. To our best knowledge, this is the first work that considers how generate cutting planes without using first order information in nested optimization, more discussions about the novelty of the proposed zeroth order cuts are presented in Appendix J.1 and Table 7.
At
according to point
{x225)
{xs
{ [
CH (t
21
2
22
23
+oout (0oon((at).1 (122))) }, 22,1 z31)
S +
(Eizz E, [02 - +1 |2 15:-==1111 zill)
+ t 12 (N+1) dz) +Eutt
(11)
In Eq. (11), we have that
3.2.1. GENERATING INNER LAYER ZEROTH ORDER CUT
At thh iteration, based on point (fa4.)) h 21, zz' z$), the new inner layer zeroth order cut will be generated to refine the inner layer polynomial approximation in Eq. (4), as follows.
Gout ((r) (2]})
Doue Irfa's f bei nut
1
(12) where u = Kerzy J. (M }n Ms 22 Ms is a stan- dard Gaussian random vector. Subsequently, the new gen- erated outer layer zeroth order cut cpuat' will be added into Po i.e., Pr.. = Add(P : cppatr)
(
(
Gin (Lag))) 25)
11
z|
22'
2/
23
z/z
out
+omn(taf 1,,,,///111 23))
Proposition 3.2. The original feasible region of constraint 0 is subset of the feasible region formed by outer layer zeroth order cuts, -N
< 2 [E, |033.] 233,1 11 + ||:1 2 +||222+2=22--- 1/1'2'=''11' 122112
1+1
Dont (o (( J. { 21, 21, 23)
+|| - 2151 12) 1222 din +Ein:
(9) i.e., P = 12 (=2j=1
T 2i, Di.
T
3. >.>c
c x
where dm = (di + d2 + (N 11da +33 and
douu te SEout,Y)) when doot has L-Lipschitz con- timuous gradient. Proofs are provided Appendix C.
Gi ), 2/1, 22/ 2/5)
(in(( tutk , 1, + 22' +0 23 #
3.2.3. REMOVING INACTIVE ZEROTH ORDER CUTS
din (in(t (aa 1.2.h,,,..,,. 1,2 (x)))
To improve the effectiveness and reduce the complexity (Yang et al., 2014; Jiao et al., 2023), the inactive zeroth order cuts will be removed during the iteration process. The
(10)
where in H1 }. 22 a2 222 is a standard Gaus- sian random vector, L > 0 is a constant, and μ > 0
corresponding inner layer Pl, and outer layer Pt... will be updated as follows.
is the smoothing parameter (Kornowski & Shamir, 2024;
Ghadimi & Lan, 2013). Then, the new generated ze- roth order cut cp will be added into p i.e., Ph Add(Pt-11 " n.w).
p {{ Remove Pi,, Pm,,), if (t) < Cin, VI pt otherwise
(13)
Proposition 3.1. The original feasible region of constraint din ), 22) = 0 is a subset of the feasi- ble region formed by inner layer zeroth order cuts, i.e., Ph = ((23,)) 21, 22', 23) S Cin {l} when Oin has
pd Remove Pouts ()on,)) if ho (f) < Eoutt 1I piu otherwise
(14)
5

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymptotic Convergence
where Remove (i ((n. and Remove out Pout,)) Pout,) re- spectively represent that the 7th inner layer and outer layer zeroth order cuts will be removed from PL and Po (() ((ar, ) 21, zb z5), and h1t(()=
Ges (1 ) (2(3) Lun (ef,, las ,eg +ww.,a)) (e), ,0,, UR,3 (21)
+ +Vas,, ol of (
hp"t (( ( hes 22, z3).
where une E Vi are standard Gaussian random vectors, / > 0 is the smoothing parameter, Ta. Vi are step-sizes. Then, the updated variables x [++ [+] 2+1 will be trans- mitted to the master.
3.3. Zeroth Order Distributed Algorithm
1.5 : 222 : 3..
In this section, a distributed zeroth order algorithm is proposed. First, defining function o( (z E.>[[mxx (ng.hh ((#2.)): {.3,)) ((r22))) 21; 22; 23) - Sout: 0}}², where A > is a penalty parameter. The constrained opti- mization problem described in Eq. (8) is reformulated as unconstrained optimization problem by using the exterior penalty method (Shen & Chen, 2023; Nazari et al., 2025; Kwon et al., 2024; Shi & Gu, 2021; Boyd & Vandenberghe, 2004) as follows.
In Master. After receiving updated variables from workers, the master performs the following steps,
1. Updating consensus variables,
=t+1- = 2 17 E,,,>,,,, +i, (2))))
(22)
2141 = 2 - 112 V Vz, (fxx)))))))))))))))) (2]1),
(23)
F( J. ( Hin F2.1. 23.1) + تلا| - =11 (15)
241 = = - 113 V #3 ol (f / (zit), 23
(24)
+o((w))) ) {z:3);
where Tai 772 and 7a, are atep-sizes.
where by >0 is a penalty parameter. It is worth noting that the proposed DTZO is an expandable framework, allowing the incorporation of approaches beyond exterior penalty method, e.g., gradient projection based approaches (Xu et al., 2020) and Frank-Wole based methods (Shen et al., 2019). We chose the exterior penalty method because the lower-level problem often serves as a soft constraint (as dis- cussed in Sec. 3.1) and using exterior penalty method offers comparatively lower complexity. In addition, we theoreti- cally demonstrate that the optimal solution to the problem in Eq. (15) is a feasible solution to the original constrained problem; 2) the gap between the problem in Eq. (15) and original constrained problem will continuously decrease as At, ØJ increase. Detailed demonstrations and discussions are provided in Appendix H. In (& + 1)th iteration, the proposed algorithm proceeds as follows.
(+1) } (2 (z)+1)). Broad- 2. Computing gradient of of (m
casting the updated parameters 2 2 i = 1,2, and V a.,,, o((2))) J.
of (
= 2, 3 to workers.
Discussion: Trilevel leaming/optimization (TLL) with level- wise zeroth order constraints is considered in this work, where first order information at each level is unavailable. Note that the proposed DTZZO is versatile and can be adapted to a wide range of TLL, e.g., grey-box TLL (gradients at some levels in TLLL are available (Huang et al., 2024b)), with slight adjustments. For instance, if gradients at first level in TLL are accessible, we can use gradient descent steps to replace Eq. (16)-(18). Similarly, if the second or third level gradients are available, first order based cuts, e.g., Jiao et al. (2023; 2024), can be employed to construct the cascaded polynomial approximation. Detailed discussions and comparisons are offered in Appendix I. In addition, the proposed DTZO can also be applied to bilevel zeroth order optimization by redueing the cascaded polynomial relaxation to single-layer polynomial relaxation.
In Worker j. After receiving the updated parameters 2 and V o(fxr, hy {=1)), worker j updates the local variables
Væ.,,
as follows,
21 1. = xi. - Tk. GaL, (fai5)) {z()),
(16)
4. Theoretical Analysis
2, x22 nw. Gaz, (1x1 } {z()),
[+1
(17)
Definition 4.1. (Stationarity Gap) Following Xu et al. (2020); Jiao et al. (2023), the stationarity gap at t iteration in this problem can be expressed as,
1+1 t's Man Gas. (1 ) {z(H),
(18)
we have that,
(Vm., F((ii,)) (g
[ 20))
(=())
{V F( foi
fislan tru4 1 1- (1. "b uk
V Vz, Fe, (e)))
(V may F( (
1
g==
-20)(0115 - x1),
(19)
W.. F((a)
Gmas (1 {z(())
Ve, F(( (ed
[1 221 + )- Fa, (a1, whe a
uk.2
(20)
(25)
P
+ + Var o(t {z(1))
It is seen from Eq. (25) that,
6

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Nom-Asymplooic Convergence
Algorithm 1 DTZO: Distributed Trilevel Zeroth Order
| - ai :iاl |l ox,, Var.j ||= = S o4, Vz,, where "| denote the optimal solution. Following Cutkosky & Orabona (2019); Liu et al. (2021a); Fang et al. (2022); Sha- ban et al. (2019), we assume the optimal value Fμ > -00
Learning
Initialization:
master iteration (af,,), (a2g), (m 2f. 2g.
0, variables
repeat
Assumption 4.5. (L-smoothness) Following many work in nested optimization and zeroth order learning, e.g., Lin et al. (2024); Ghadimi & Lan (2013), we assume the gradient of function F is Lipschitz continuous with constant L < oc, that is, for any point ux w', we have that,
for local worker do updates the local variables o 2b² 23,5 ing to Eq. (16)-(21);
s+1 accord-
end for local workers transmit the updated variables to master; for master do
[V V FF(w") ) - T.| w w
(28)
updates consensus variables 21+1, 2/211 ,23 ac-
cording to Eq. (22)-(24); (+ 1, 3));
It is worth noting that Assumptions 4.4 and 4.5 are mild and commonly used in machine learning and optimization. Detailed discussions are provided in Appendix G.
computes Vo([=))
end for
master broadcasts the updated parameters and gradi- ents to workers;
Theorem 4.6. (Iteration Complexity) Under Assump- tion 4.4 and 4.5, by setting step-sizes qa. = Ti.
if (t + 1) mod T= and f < Ti then
min 8T(d+ (T.()2+4)) Sldd+44)' 1(1--1)' VT(c)-Ti 1,2,3 and letting smoothing parameter
new inner layer zeroth order cuts are generated by Eq. (9) and (10);
new outer layer zeroth order cuts are generated by Eq. (11) and (12);
0 O<KS
Vr(ei- we have that,
inactive zeroth order cuts are deleted by Eq. (13) and (14);
T(e)
o
3
Cj di max F (((( 2 tE(T))
end if
1= ( ++11 1; until termination.
(29)
where constants
d
= 4(1
+
max(8L(d) + 44,,8L(() + 4), 8L(ds 4), 2(++1))
4[d:+4] L' + (d:++33) + 4L(N +
and T =
(ab } (ar }, 21, 23, 21)112
Σ. E, V m., ((( J. (arh (ar5. ), 21, 2/2 2/ 1.
(mxx((()8) Ti > 0 is constant that controls the cascaded polynomial approximation, as discussed in Sec. 3.2. Detailed proofs of Theorem 4.6 are provided in Appendix A, with further discussions offered below.
8L(d (L( 3 (
SL(22+4)),
(26)
Point) (Lii,) ( ( }. =f, 25. 23) is the stationary point when [| = 0, and it is the e-stationary point when ||9'||- S c. Defining T(c) the first iteration when ||@'|12 ( i.e, T(c)= min || sc).
Definition
4.2.
(c-Stationary
Theorem 4.7. (Communication Complexity) The overall communication complexity of the proposed DIZO can be divided into the communication complexity at every iteration (C1) and the communication complexity of updating zeroth order cuts (C2). Specifically, the overall communication complexity can be expressed C1 + C2 = ((d) + 3dg + Ndg))N + 2NL T3 [T((2 + dz). The detailed proofs are provided in Appendix B, with discussions offered below.
Definition 4.3. (μ-Smooth Approximation) Following Ghadimi & Lan (2013); Fang et al. (2022); Kornilov et al. (2024); Rando et al. (2024), the p-smooth approximation of a function F(w): Idd + IR is given by,
Fy( 1
(2m) f F(w + pruee 11lmll du
(27)
Discussion: It is seen from Theorem 4.6 and 4.7 that the proposed framework DTZO can flexibly control the trf between the performance of cascaded polynomial approxi- mation and the iteration complexity (i.c., T(e) in Theorem 4.6) and communication complexity (i.c., C1 + C2 in Theo- rem 4.7) by adjusting single parameter Ty. Specifically. larger Ti corresponds to better cascaded polynomial ap- proximation, but it also entails higher iteration and commu- nication complexity. Consequently. if the distributed system has limited computational and communication capabilities, a smaller value of T can be selected. Conversely, if a higher
= Em [F(w + pr))
where E Rd is standard Gaussian random vector and > is the smoothing parameter.
Assumption 4.4. (Boundedness) Following many works in machine learning and optimization, e.g., Deng et al. (2020); Jiao et al. (2023); Qian et al. (2019); Lei & Tang (2018); Zheng et al. (2017); Duchi et al. (2012); Yang et al. (2024b); Khaled & Jin (2024); Chen et al. (2024b); Hazan & Minasyan (2020), the bounded domain is assumed, i.e.,
7

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplooic Convergence
quality of cascaded polynomial approximation is desired, larger value of Ti can be chosen, which demonstrates the flexibility in the proposed framework. In addition, as shown in Theorem 4.6, the iteration complexity of the proposed distributed trilevel zeroth order learning framework can be written as OEE, de) It is worth mentioning that the dimension-deepndent iteration complexity is common ze- roth order optimization, as discussed in various works, e.g.. Zhang al. (2024b;a); Duchi et al. (2015); Sun et al. (2022); Qiu et al. (2023). For instance, the iteration complexity of the wate-of-the-ar distributed bilevel zeroth order learning method (Qiu et al., 2023) is given by O(dd/²2) where d denotes the dimension of variables.
The General Language Understanding Evaluation (GLUB) benchmark (Wang et al., 201 8a) is used evaluate the pro- posed DTZO. Specifically, the experiments are carried out on: 1) SST-2 for sentiment analysis; 2) COLA for linguistic acceptability: and 3) MRPC for semantic equivalence of sentences. Details of the problem formulation and exper- imental setting are shown in Appendix F, In this task, we aim to discover effective backdoor triggers while ensuring model performance on clean inputs (i.e., inputs without trig- gers). Therefore, following Yao et al. (2024), the Attack Success Rate (ASR) when the triggers are activated and the Accuracy (ACC) on clean samples are utilized as the metrics in the experiments. The comparisons between the proposed DTZO and the state-of-the-ae distributed bilevel zeroth order learning method FedRZO,, are illustrated in Figures 1, 2, and 3. is seen from Figures 1, 2. and 3 that the proposed DTZO can effectively tackle the distributed trilevel zeroth order learning problem and achieve superior performance than FedRZO,) since the proposed DTZO is capable of addressing higher- nested zeroth order learning problems compared to FedRZOp)-
5. Experiments
In the experiment, two distributed trilevel zeroth order learn- ing scenarios, i.e., black-box trilevel learning on large lan- guage models (L.Ms)) and robust hyperparameter optimiza- tion are used to evaluate the performance of the proposed DTZO. The proposed DTZO is compared with the state-of- the-art distributed zeroth order learning method FedZOO (Fang et al., 2022) and distributed bilevel zeroth order learn- ing method FedRZO,, (Qiu et al., 2023). Moreover, to fur- ther demonstrate the effectiveness of the proposed DTZO, we also compare it against state-of-the-ar distributed bilevel and trilevel optimization methods equipped with zeroth or- der estimators (Liu et al., 2020), including FEDNEST+Z0 (Tarzanagh et al., 2022), ADBO+ZO (Jiao et al., 2023), and AFTO+ZO (Jiao et al., 2024). It is important to note that combining distributed nested optimization methods with zeroth order estimators does not provide any theoretical guarantees; these methods are included only for compara- tive evaluation. In the experiment, all the models are imple- mented using PyTorch, and the experiments are conducted on a server equipped with two NVIDIA RTX 4090 GPUs More experimental details are provided in Appendix F.
5.2. Robust Hyperparameter Optimization
Inspired by Sato et al. (2021); Jiao et al. (2024) in trilevel learning, the robust hyperparameter optimization is con- sidered in the experiment. Following the setting for non- differentiable functions as described in Qiu et al. (2023), ReLU neural networks are employed in the experiments The digits recognition tasks in Qian et al. (2019); Wang et al. (2021) with several benchmark datasets, i.e., MNIST (LeCun et al., 1998), USPS, Fashion MNIST (Xiao et al., 2017), and QMNIST (Yadav & Bottou, 2019), are utilized to assess the performance of the proposed DTZO. In addition, DTZO is also assessed on time series datasets, including MelboournPPedestrian Crop, and (WaaeeGssturllLibrary sourced from the UCR Archive (Dau et al., 2018). The aver- age across accuracy on clean samples and robustness against adversarial samples is used as the metric, more details about the experimental setting and problem formulation are pro- vided in Appendix F, We compare the proposed DTZO with the state-of-the-at art methods in Table It is seen from Table 2 that the proposed DTZO can effectively tackle the trilevel zeroth order learning problem in a distributed manner. The superior performance of DTZO, as compared to state-of- the-art methods, can be attributed to two key factors: (I) Compared to existing methods, the proposed DTZO is ca- pable of effectively addressing higher-nested zeroth order optimization problems with -symmtttiii convergence guarantees. (2) The proposed nonlinear zeroth order cuts facilitate the development of more refined cascaded poly- nomial relaxation.
5.1. Black-Box Trilevel Learning
Prompt learning is key technique for enabling LLMMs to efficiently and effectively adapt to various downstream tasks (Ma et al., 2024; Wang et al., 2024). In many practical sce- narios involving LLMs, access to first order information is restricted due to the proprietary nature of these models or API constraints. For instance, commercial LLM APIs only allow input-output interactions and do not provide visibility into gradients. Inspired by the black-box prompt learning (Diao et al., 2022) and backdoor attack prompt- based LLMS (Yao et al., 2024; Jiao et al., 2025), the backdoor attack on box LLMs is considered in the experiment, which can be expressed as a black-box trilevel learning problem. In the experiment, Qwen2-7B (Yang et al., 2024a), Llama-3.1-8P (Grattafiori et al., 2024), and Qwen-1.8H, Chat (Bai et al., 2023), are utilized as the black-box LLMs.
Within the proposed framework, the trade-off between com- plexity and performance can be flexibly controlled by ad-
8

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
100
75
65-
ASR(%)
ACC(%)
55
The proposed DTZO
The propased DTZO
FedRZObi
45
FedRZOpi
SST-2
COLA
MRPC
SST-2
COLA
MRPC
(a)
Comparisons about ASR
(b) Comparisons about ACC
Figure Comparisons about ASR and ACC between the proposed DTZO and state-of-the-art method using @0wn-11.8--Che
Table 2. Comparisons between the proposed DTZO and the state of ahe methods. Higher scores represent better performance.
Datasets
FedZOO
FEDNEST+70
ADBO+Z0
FedRZObl
AFTO+70
DTZO
MNIST
0.5289
0.5503
0,5341
0.5405
0.7501
0.7927
QMNIST
0,5245
0.5398
0.5487
0,5467
0.7389
0.7804
F-MNIST
0.4874
0.5065
0,5102
0,5023
0.6448
0.7007
USPS
0.7277
0.7354
0.7323
0.7379
0.7987
0.8513
Melbourne
0.6295
0.6454
0.6412
0.6487
0.6924
0.7250
Crop
0,5468
0,5607
0,5681
0,5645
0.6016
0.6351
UWaaeGesttureLLbarryllllll
0.6714
0.6924
0.6983
0,7002
0.7689
0.8243
justing Ti, discussed in Sec. 4. As shown in Figure 4 in Appendix F, the performance of DTZO improves as Ti increases, we can flexibly adjust Ti based on the distributed system requirements. Removing inactive cuts can signifi- cantly improve the effectiveness of cutting plane method, as discussed Jiao et al. (2024); Yang et al. (2014). In the ex- periment, we also investigate the effect of removing inactive cuts within the proposed DTZO. It seen from Figure 5 in Appendix F that pruning inactive cuts significantly reduces training time, indicating the importance of this procedure.
convergence rate with a relatively smaller μ4, because the gra- dient estimate improves when becomes relatively smaller, as discussed in Liu et al. (2020). Furthermore, to analyze DTZO's 's performance improvements, we conduct an abla- tion study comparing DTZO against its variants: DTZO(-) and DBZO. DTZO(-) replaces the proposed nonlinear cuts in DTZO with linear cuts, while DBZO removes cascaded polynomial approximation, using only single-layer polyno- mial approximation. is scen from Table 5 in Appendix F that DTZO outperforms all variants, demonstrating the ben- efits of cascaded polynomial approximation and nonlinear zeroth order cuts.
In addition, the impact of various choices of Ti on the con- vergence rate within the proposed DTZO is evaluated. As illustrated Figures and Appendix F, a smaller Ti leads faster convergence but affects the method's per- formance, resulting in higher test loss. Conversely, if better performance is required, a larger Ti can be selected, corresponding to more refined polynomial relaxation. In the proposed framework, we can flexibly adjust Ti based on various requirements. The results Figures 6 and are consistent with our theoretical analyses presented under Theorems 4.6 and 4.7.
6. Conclusion
In this work, distributed trilevel zeroth order learning (DTZO) framework is proposed to address the trilevel leam- ing problems in a distributed manner without using first order information. To our best knowledge, this is the first work that considers how to tackle the trilevel zeroth or- der learning problems. The proposed DTZO is capable of constructing the cascaded polynomial approximation for trilevel zeroth order learning problems without using gradi- or sub-gradients by utilizing the novel zeroth order cuts. Additionally, theoretically analyze the non-asymptotic convergence rate for the proposed DTZO to achieve the e-stationary point. Experiments on black-box LLMs trilevel learning and robust hyperparameter optimization demon- strate the superior performance of DTZO.
Following Qiu et al. (2023), the robustness in the proposed framework with respect to the choice of smoothing param- eter μ1 is evaluated. The experiments are conducted on the robust hyperparameter optimization task under various set- tings of smoothing parameter E {0.01, 0.001, 0.0001). It seen from Figure and 9 in Appendix F that the proposed DTZO is robust the choice of smoothing parameter μ. In addition, also note that the proposed DTZO has faster

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymptotic Convergence
Acknowledgments
Beykal, B., Avraamidou, S., Pistikopoulos, I. P., Onel, M., and Pistikopoulos, E. N. Domino: Data-driven optimiza- tion of bi-level mixed-integer nonlinear problems. Jour- nal of Global Optimization, 78:1-36, 2020.
This work was supported in part by the National Natural Science Foundation of China under Grant 12371519 and 61771013; in part by Asiainfo Technologies; in part by the Fundamental Research Funds for the Central Universities of China; and in part by the Fundamental Research Funds of Shanghai Jiading District.
Blair, C. The computational complexity of multi-leve linear programs. Annals of Operations Research, 34, 1992.
Boyd, S. and Vandenberghe, L. Localization and cutting- plane methods. From Stanford EE 364b lecture notes, 386, 2007.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Boyd, S. P. and Vandenberghe, L. Convex optimization. Cambridge university press, 2004.
Bürger, M., Notarstefano, G., and Allgöwer, F. A poly-
hedral approximation framework for convex and robust distributed optimization. IEEE Transactions on Auto- matic Control, 59(2):384 395, 2013.
References
Akhavan, A., Pontil, M., and Tsybakov, A. Distributed zero- order optimization under adversarial noise. Advances in Neural Information Processing Systems, 34:10209- 10220, 2021.
Cai, H., Lou, Y., McKenzie, D., and Yin, W. A zeroth- order block coordinate descent algorithm for huge-scale black-box optimization. International Conference on Machine Learning, pp. 1193-1203, PMLR, 2021.
Assran, M., Aytekin, A., Feyzmahdavian, H. R., Johansson, M., and Rabbat, M. G. Advances in asynchronous parallel and distributed optimization. Proceedings of the IEEE, 108(11):0013-2311 2020.
Cao, J., Jiang, R., Abolfazli, N., Yazdandoost Hamedani, E., and Mokhtari, A. Projection-free methods for stochas- tic simple bilevel optimization with convex lower-level problem. Advances in Neural Information Processing Systems, 36, 2024.
Astudillo, R. and Frazier, P. I. Thinking inside the box: A tutorial on grey-box bayesian optimization. In 2021 Winter Simulation Conference (WSC), pp. 1-15. IEEE, 2021.
Chen, J., Chen, H., Gu, B., and Deng, H. Fine line-grained the- oretical analysis of federated zeroth-order optimization. Advances in Neural Information Processing Systems, 36, 2024a.
Avraamidou, S. Mixed-integer multi-level optimization through multi- multi-parametric programming. 2018.
Chen, S., Zhang, Y.-.,, Tu, W.-W., Zhao, P., and Zhang, L. Optimistic online mirror descent for bridging stochastic and adversarial online convex optimization. Journal of Machine Learning Research, 25(17 2024b.
Bai, J., Bai, S., Chu, Y., Cui, Z., Dang, K., Deng, X., Fan, Y., Ge, W., Han, Y., Huang. F., et al. Qwen technical report. arXiv preprint 2309. 12009./6600 16609, 2023.
Chen, X., Liu, S., Xu, K., Li, X., Lin, X., Hong, M., and Cox, D. Zo-adamm: Zeroth-order adaptive momentum method for black-box optimization. Advances in neural information processing systems, 32, 2019.
Bajaj, I, Iyer, S. S., and Hasan, M. F. A trust region- based two phase algorithm for constrained black-box and grey- box optimization with infeasible initial point. Computers & Chemical Engineering, 16:306-321, 2018
Chen, X., Xiao, T., and Balasubramaniann, K. Optimal algo- rithms for stochastic bilevel optimization under relaxed smoothness conditions. arXiv preprint urXiv:2306.1200 2023.
Balashov, M., Polyak, B., and Tremba, A. Gradient pro- jection and conditional gradient methods for constrained nonconvex minimization. Numerical Functional Analysis and Optimization, 4 41(7):822-849, 2020.
Chen, X., Xiao, T., and Balasubramanian, Optimal algo- rithms for stochastic bilevel optimization under relaxed smoothness conditions. Journal of Machine Learning Research, 25(151):1-51, 2024c.
Ben-Ayed, O. and Blair, C. E. Computational difficulties of bilevel linear programming. Operations Research, 38(3): 556-560, 1990.
Bertsekas, D. Convex optimization algorithms. Athena Scientific, 2015.
Chen, X., Xiong, Y., and Yang, K. Robust beamforming for downlink multi-cell systems: bilevel optimization
10

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymptotic Convergence
perspective. In Proceedings of the AAAI Conference on Artificial Intelligence, 2024d.
Gao, H. and Huang. H. Can stochastic zeroth-order frank- wolfe method converge faster for non-convex problems? In International conference on machine learning, pp. 3377-3380 PMLR, 2020.
Choe, S. K., Neiswanger, W., Xie, P., and Xing, E. Betty: An automatic differentiation library for multilevel opti- mization. The Eleventh International Conference on Learning Representations, 2023.
Gao, H., Li, J., and Huang, H. On the convergence of local stochastic compositional gradient descent with momen- tum. In International Conference on Machine Learning, pp. 7017-7035. PMLR, 2022.
Cutkosky, A. and Orabona, F. Momentum-basee variance reduction in non-convex sgd. Advances in neural infor- mation processing systems, 32, 2019.
Gao, H., Gu, B., and Thai, M. T. On the convergence of distributed stochastic bilevel optimization algorithms over network. In International Conference Artificial Intelligence and Statistics, pp. 2338-9281. PMLR, 2023.
Dau, H. A., Bagnall, A., Kamgar, K., Yeh, C.-C. M., Zhu, Y., Gharghabi, S., Ratanamahatana, C. A., and Keogh, E. The ucr time series archive. JEEE/CAA Journal of Automatica Sinica, 6(6):1293-1305, 2018.
Garber, D. and Hazan, E. Faster rates for the frank-wolfe method over strongly-convex sets. In International Con- ference Machine Learning, pp. 541-549. PMLR, 2015.
Deng, Y., Kamani, M. M., and Mahdavi, M. Distributionally robust federated averaging. Advances in neural informa- lion processing systems, 1--1111-1112,, 2020.
Garg, B., Zhang, L., Sridhara, P., Hosseini, R., Xing, E., and
Xie, P. Learning from mistakes-a framework for neural ar- chitecture search. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 10184 10192, 2022.
Diao, S., Huang. Z., Xu, R., Li, X., Yong, L., Zhou, X., and Zhang. T. Black-box prompt learning for pre-trained language models. Transactions on Machine Learning Research, 2022.
Ghadimi, S. and Lan, G. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization, 23(4):2341 -23688 2013.
Duchi, J. C., Agarwal, A., Johansson, M., and Jordan, M. I. Ergodic mirror descent. SIAM Journal on Optimization, 22(4):1549-1578 2012.
Giovannelli, T., Kent, G. D., and Vicente, L. N. A stochastic gradient method for trilevel optimization. arXiv preprint arXhv:2505.0688 2025.
Duchi, J. C., Jordan, M. I., Wainwright, M. J., and Wibisono, A. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61(5):2788-2 22062 2015.
Grattafiori, A., Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Vaughan, A., et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21788, 2024.
Fang, W. Yu, Z., Jiang, Y., Shi, Y., Jones, N., and Zhou, Y. Communication--fficiee stochastic zeroth-order op- timization for federated learning. IEEE Transactions on Signal Processing, 70:5058-5073. 2022.
Guo, H., Hosseini, R., Zhang, R., Somayajula, S. A., Chowd- hury, R. R., Gupta, R. K., and Xie, P. Downstream task guided masking learning in masked autoencoders using lulti-level optimization. Transactions on Machine Learn- ing Research, 2024.
Finn, C., Abbeel, P., and Levine, S. Model-agnostic meta- learning for fast adaptation of deep networks. In Interna- tional conference machine learning, pp. 1126-1135. PMLR. 2017.
Guo, M., Yang, Y., Xu, R., Liu, Z., and Lin, D. When nas meets robustness: search robust architectures against adversarial attacks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 631-640, 2020.
Franc, V., Sonnenburg. S., and Werner T. Cutting plane methods machine learning. Optimization for Machine Learning, pp. (85-218,20 2011.
Franceschi, L., Frasconi, P., Salzo, S., Grazzi, R., and Pontil, M. Bilevel programming for hyperparameter optimiza- tion and meta-learning. In International conference on machine learning, pp. 1568-1577. PMLR, 2018.
Han, P., Shi, X., and Huang, Fedal: Black-box feder- ated knowledge distillation enabled by adversarial learn- ing. IEEE Journal on Selected Areas in Communications, 2024.
Gao, H. Decentralized multi-level compositional optimiza- tion algorithms with level-independent convergence rate. In International Conference on Artificial Intelligence and Statistics, pp. 4402 4410. PMLR, 2024.
Hazan, E. and Minasyan, E. Faster projection-free online learning. In Conference on Learning Theory, pp. 1877 1893. PMLR, 2020.

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
He, Y., Zhang, R., Somayajula, S. A., and Xie, P. Trans- former architecture search for improving out-of-domain generalization in machine translation. Transactions Machine Learning Research, 2024.
Jiao, Y., Yang, K., Wu, T., Song, D., and Jian, C. Asyn- chronous distributed bilevel optimization. In The Eleventh International Conference on Learning Representations, 2023.
Héliou, A., Martin, M., Mertikopoulos, P., and Rahier, T. Zeroth-order non-convex learning via hierarchical dual averaging. In International Conference Machine Learning, pp. 4192-4202. PMLR, 2021.
Jiao, Y., Yang, K., Wu, T., Jian, C., and Huang, J. Provably convergent federated trilevel learning. In Proceedings of the AAAI Conference Artificial Intelligence, vol- ume 38, pp. 12928-12993 2024.
Hong, M., Wai, H.-T., Wang, Z., and Yang, Z. A two- timescale stochastic algorithm framework for bilevel op- timization: Complexity analysis and application to actor- critic. SIAM Journal on Optimization, 33(1):147-18)) 2023.
Jiao, Y. Wang. X., and Yang, K. Pr-attack: Coordinated prompt-rag attacks on retrieval-augmented generation in large language models via bilevel optimization. arXiv preprint arXiv:2504.07717, 2025.
Jing. G., Bai, H., George, J., Chakrabortty, A., and Sharma, P. K. Asynchronous distributed reinforcement learning for lqr control via zeroth- block coordinate descent. IEEE Transactions on Automatic Control, 2024.
Huang, F., Gao, S., Pei, J., and Huang. H. Nonconvex zeroth- order stochastic admm methods with lower function query complexity. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024a.
Kautz, A., Selman, B., and Jiang, Y. A general stochastic approach solving problems with hard and soft con- straints. Satisfiability Problem: Theory and Applications, 35:573-586, 1996.
Huang. H., Li, Y.. Jiang, B., Jiang, B., Liu, L., Liu, Z., Sun, R., and Liang. S. Enhancing the resilience of Ilms against grey-box extractions. ICML 2024 Next Generation of Al Safety Workshop. 2024b.
Khaled, A. and Jin, C. Tuning-free stochastic optimiza- tion. In Forty-first International Conference on Machine Learning, 2024.
Huang, Y., Yang, K., Zhu, Z., and Chen, L. Triadic-ocd: Asynchronous online change detection with provable ro- bustness, optimality, and convergence. International Conference on Machine Learning, pp. 20382-20412. PMLR. 2024c.
Kornilov, N., Shamir, O., Lobanov, A., Dvinskikh, D., Gas- nikov, A., Shibaev, I., Gorbunov, E., and Horváth, Accelerated zeroth-order method for non smothh stochas- tic convex optimization problem with infinite variance. Advances in Neural Information Processing Systems, 36, 2024.
Ji, K., Yang, J., and Liang, Y. Bilevel optimization: Con- vergence analysis and enhanced design. In International conference on machine learning, pp. 4882-4892 PMLR, 2021.
Kornowski, G. and Shamir, O. An algorithm with optimal dimension-dependent for zero-order nonsmooth noncon- stochastic optimization. Journal of Machine Learning Research, 25(122): 2024.
Jian, C., Yang. K., and Jiao, Y. Tri-level navigator: Llm- empowered tri-level learning for time series ood gener- alization. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.
Kwon, J., Kwon, D., Wright, S., and Nowak, R. D. fully first-order method for stochastic bilevel optimiza- tion. In International Conference on Machine Learning, pp. 18083-181 13. PMLR, 2023.
Jiang, R., Abolfazli. N., Mokhtari, A., and Hamedani, E. Y. A conditional gradient-based method for simple bilevel optimization with convex lower-level problem. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 10305-10323, PMLR, 2023.
Kwon, J., Kwon, D., Wright, S., and Nowak, R. D. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. In The Twelfth Inter- national Conference Learning Representations, 2024.
Jiao, Y., Yang, K., and Song, D. Distributed distribution- ally robust optimization with non-convex objectives. Ad- vances in neural information processing systems, 35: 7987-7999, 2022a.
LeCun, Y., Bottou, I.., Bengio, Y., and Haffner, Gradient- based learning applied to document recognition. Proceed- ings of the IEEE, 86(1 86(11): 1227722222282 1998.
Jiao, Y., Yang, K., Song, D., and Tao, D. Timeautoad: Autonomous anomaly detection with self-supervised con- trastive loss for multivariate time series. IEEE Transac- tions on Network Science and Engineering, 9(3):6604- 1619, 2022b.
Lei, Y. and Tang, K. Stochastic composite mirror descent: Optimal bounds with high probabilities. Advances in Neural Information Processing Systems, 31, 2018.
12

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asympiotic Convergence
Li, J., Huang, F., and Huang. H. Communication-efficienn federated bilevel optimization with local and global lower level problems. arXiv preprint arXiv:2302.06701 2023.
Liu, S., Kailkhura, B., Chen, P.-Y., Ting, P., Chang, S., and Amini, L. Zeroth-order stochastic variance reduction for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018c
Li, J., Huang. F., and Huang, H. Communication-efice federated bilevel optimization with global and local lower level problems. Advances in Neural Information Process- ing Systems, 36, 2024.
Liu, S., Chen, P.-Y,, Kailkhura, B., Zhang, G., Hero III, A. O., and Varshney, P. K. A primer zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications. IEEE Sig- nal Processing Magazine, 37(5):43-54, 2020.
Li, W. and Assaad, M. Distributed zeroth-order stochastic optimization varying networks. arXiv preprint arXiv:2105. 12597, 2021.
Ma, H., Zhang, C., Bian, Y., Liu, L.., Zhang, Z., Zhao, P... Zhang, S., Fu, H., Hu, Q., and Wu, B. Fairness Fairness-guided few-shot prompting for large language models. Advances in Neural Information Processing Systems, 36, 2024.
Li, Z., Chen, P.-.,, Liu, S., Lu, S., and Xu, Y. Zeroth-order optimization for composite problems with functional con- straints. In Proceedings of the AAAI Conference on Artifi- cial Intelligence, volume 36, pp. 7453-7461, 2022.
Mackay, M., Vicol, P., Lorraine, J., Duvenaud, D., and
Grosse, R. Self-tuming networks: Bilevel optimization of hyperparameters using structured best-response functions. In International Conference on Learning Representations, 2018.
Lian, X., Zhang, H., Hsieh, C.-J., Huang, Y., and Liu, J. A comprehensive linear speedup analysis for asynchronous stochastic parallel optimization from zeroth-order to first- order. Advances in Neural Information Processing Sys- tems, 29, 2016.
Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. Towards deep learning models resistant to adversarial attacks. In International Conference on Learn- ing Representations, 2018.
Liang, H., Sun, B., Huang, B., Li, Y., and Yang, C. A novel chattering- discrete sliding mode controller with dis- turbance compensation for zinc roasting temperature dis- tribution control. IEEE Transactions Automation Sci- ence and Engineering, 2024.
Nazari, P., Mousavi, A., Tarzanagh, D. A., and Michailidis, G. A penalty- method for communication-efiicent decentralized bilevel programming. Automatica, 173:
Lin, S., Sow, D., Ji, K., Liang, Y., and Shroff, N. Non- convex bilevel optimization with time-varying objective functions. Advances in Neural Information Processing Systems, 36, 2024.
1 112039, 2025.
Nikolakakis, K., Haddadpour, F., Kalogerias, D., and Kar- basi, A. Black-box generalization: Stability of zeroth- order learning. Advances in Neural Information Process- ing Systems, 1-31522-315411 2022.
Liu, B., Liu, X., Jin, X., Stone, P., and Liu, Q. Conflict- averse gradient descent for multi-task learning. Advances in Neural Information Processing Systems, 34:18878- 18890, 2021a.
Pan, R., Zhang, J., Pan, X., Pi, R., Wang, X., and Zhang, T. Scalebio: Scalable bilevel optimization for Ilm data reweighting. arXiv preprint arXiv:2406. 19976, 2024.
Liu, B., Ye, M., Wright, S., Stone, P., and Liu, Q. Bome! bilevel optimization made easy: A simple first-order ap- proach. Advances in Neural Information Processing Sys- fems, 15:17248-17266 2022.
Qian, Q., Zhu, S., Tang, J., Jin, R., Sun, B., and Li, H. Robust optimization over multiple domains. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4739-4746, 2019.
Liu, H., Simonyan, K., and Yang, Y. Darts: Differentiable ar- chitecture search. International Conference on Learn- ing Representations, 2018a.
Qiu, Y., Shanbhag, U., and Yousefian, Zeroth-order meth- ods for nondifferentiable, nonconvex, and hierarchical federated optimization. Advances in Neural Information Processing Systems, 36, 2023.
Liu, R., Gao, J., Zhang, J., Meng, D., and Lin, Z. Investigat- ing bi-level optimization for learning and vision from a unified perspective: survey and beyond. IEEE Trans- actions on Pattern Analysis and Machine Intelligence, 44 (12):10045-1061) 2021b.
Raghu, A., Lorraine, J., Kornblith, S., McDermott, M., and Duvenaud, D. Meta-learning improve pre-training. Advances in Neural Information Processing Systems, 34: 123244,,,, 2021.
Liu, S., Chen, P.-Y, Chen, X., and Hong, M. signsgd via seroth-order oracle. In International Conference on Learning Representations, 2018b.
Rando, M.. Molinari, C., Rosasco, L., and Villa, S. An optimal structured zeroth-order algorithm for non-smooth
13

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
optimization. Advances in Neural Information Processing Systems, 36, 2024.
Sra, S., Yu, A. W., Li, M., and Smola, A. Adadelay: Delay adaptive distributed stochastic optimization. In Artificial Intelligence and Statistics, pp. 957-965. PMLR, 2016.
Régin, J.-C. Using hard constraints for representing soft constraints. In Integration of Al and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: 8th International Conference, CPAIOR 2011, I, Berlin, Germany, May 23-27, 2011. Proceedings 8, pp- 176-189. Springer, 2011.
Subramanya, T. and Riggio, R. Centralized and federated learning for predictive vnf autoscaling in multi-domain 5g networks and beyond. IEEE Trunsactions Network and Service Management, 18(1):63-78, 2021.
Sun, T., Shao, Y., Qian, H., Huang, X., and Qiu, X. Black- box tuning for language national Conference on Machine Learning, pp. 20841- 20855, PMLR, 2022.
language-model-as model-as- -saeel--e----ericce. In Inter-
Ren, Z., Tang, Y., and Li, N. Escaping saddle points in zeroth-order optimization: the power of two-point estima- tors. In International Conference on Machine Learning, pp. 28914-28975, PMLR, 2023.
Tang, Y., Zhang, J., and Li, N. Distributed zero-order al- gorithms for nonconvex multiagent optimization. IEEE Transactions on Control of Network Systems, 8(1):269- 281, 2020.
Sahu, A. K., Jakovetic, D., Bajovic, D., and Kar, S. Dis- tributed zeroth order optimization over random networks: A kiefer-wolfowitz stochastic approximation approach. In 2018 IEEE Conference on Decision and Control (CDC), pp. 4951-4958. IEEE, 2018.
Tarzanagh, D. A., Li, M., Thrampoulidis, C., and Oymak, S.
Fednest: Federated bilevel, minimax, and compositional optimization. In International Conference on Machine Learning, pp. 21146-21179, PMLR, 2022.
Sato, R., Tanaka, M., and Takeda, A. A gradient method for multilevel optimization. Advances in Neural Information Processing Systems, 34:7522-755 7533, 2021.
Temlyakov. Nonlinear methods of approximation. Founda- tions of Computational Mathematics, 3:33-107, 2003.
Shaban, A., Cheng, C.-A., Hatch, N., and Boots, B. Trun- cated poo-ppropagttion for bilevel optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1723-1733 PMLR, 2019.
Tu, C.-C., Ting, P., Chen, P.-Y., Liu, S., Zhang, H., Yi, J., Hsich, C.-J., and Cheng, S.-M. Autozoom: Autoencoder- based zeroth order optimization method for attacking black-box neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 742- 749, 2019.
Shen, H. and Chen, T. On penalty-based bilevel gradient descent method. arXiv preprint arXiv:2302.05185 2023.
Shen, H., Yang, Z., and Chen, T. Principled penalty-based methods for bilevel reinforcement learningg and rlhf. arXiv preprint w-x.x:2442.066880 2024.
Wang, A., Singh, A., Michael, J., Hill, F., Levy, O., and Bowman, S. Glue: A multi-takk benchmark and analysis platform for natural language understanding. In Pro- ceedings of the 2018 EMNLP Workshop BlackboxNIPP: Analyzing and Interpreting Neural Networks for NLP, pp- 353-355, 2018a.
Shen, Z., Fang, C., Zhao, P., Huang, J., and Qian, H. Com- plexities in projection-free stochastic non-convex mini- mization. In The 22nd International Conference on Arti- ficial Intelligence and Statistics, pp. 2019.
Wang. B., Wang, Z., Wang, X., Cao, Y., Saurous, R., and Kim. Y. Grammar prompting for domain domain-specific lan- guage generation with large language models. Advances in Neural Information Processing Systems, 36, 2024.
PMLR,
Shi, W. and Gu, B. Improved penalty method via doubly stochastic gradients for bilevel hyperparameter optimiza- tion. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 9621-9629 2021.
Wang, J., Chen, J., Lin, J., Sigal, L.,, and de Silva, C. W. Dis- criminative feature alignment: Improving transferability of unsupervised domain adaptation by gaussian-guided latent alignment. Pattern Recognition, 1 116: 10794,, 2021.
Shu, Y., Lin, X. Dai, Z., and Low, B. K. H. Federated zeroth- order optimization using trajectory-informed surrogate gradients. arXiv preprint arXiv:2308..04077 2023.
Wang, Y., Du, S., Balakrishnan, S., and Singh, A. Stochastic zeroth-order optimization in high dimensions. Interna- tional conference on artificial intelligence and statistics. pp. 1356-1365. PMLR, 2018b.
Sinha, A., Malo, P., and Deb, K. A review on bilevel op- timization: From classical to evolutionary approaches and applications. IEEE Transactions on Evolutionary Computation, 22(2):276-2955 2017.
Wang, Y.-.., Sadhanala, V., Dai, W., Neiswanger, W., Sra, S., and Xing, E. Parallel and distributed block-coordinate
14

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
frank-wolfe algorithms. In International Conference on Machine Learning, pp. 1548-1557. PMLR, 2016.
Yang, W., Wang. Y., Zhao, P., and Zhang. L. Universal online convex optimization with 1 projection per round. In The Thirty-eighth Annual Conference Neural Infor- mation Processing Systems, 2024b.
Wilson, E.,, Mueller, F., and Pakin, Combining hard and soft constraints in quantum constraint--satisaciin systems. In SC22: International Conference for High Performance Computing, Networking, Storage and Anal- ysis, pp. 1-14. IEEE, 2022.
Yang. Y., Xiao, P., Ma, S., and Ji, K. First-order federated bilevel learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 39, pp. 2025.
Wu, X., Sun, J., Hu, Z., Li, J., Zhang, A., and Huang, H. Federated conditional stochastic optimization. Advances in Neural Information Processing Systems, 36, 2024.
Yao, H., Lou, J., and Qin, Z. Poisonprompt: Backdoor attack on prompt-based large language models. In ICASSP 2024-2024 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 7745-7749. IEEE, 2024.
Xian, W. Huang, F., and Huang, H. Communication- efficient frank-wolfe algorithm for nonconvex decentral- ized distributed learning. In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 35, pp. 10405- 10413,20 2021.
Yue, P., Yang, L., Fang, C., and Lin, Z. Zeroth-order op- timization with weak dimension dependency. In The Thirty Sixth Annual Conference on Learning T'heory, pp. 4429-4472. PMLR, 2023.
Xiao, H., Rasul, K., and Vollgraf, R. Fashion-mnist: novel image dataset for benchmarking machine learning 2017.
algorithms. arXiv preprint
Zhang, H., Zhang, H., Gu, B., and Chang, Y. Subspace se- lection based prompt tuning with nonconvex nonsmooth black-box optimization. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. -179-4190, 2024a.
Xiao, Q., Shen, H., Yin, W., and Chen, T. Alternating pro- jected sgd for constrained bilevel optimization. In International Conference on Artificial Intelligence and Statistics, pp. 987-1023. PMLR, 2023.
Zhang, M., Shen, Z., Mokhtari, A., Hassani, H., and Karbasi, A. One sample stochastic frank-wolfe. In International Conference on Artificial Intelligence and Statistics, pp. 4012-4023. PMLR, 2020.
Xu, Z. Zhang, H., Xu, Y., and Lan, G. A unified single-loop alternating gradient projection algorithm for nonconvex-concatt and convex-nonconcave minimax problems. arXiv preprint arXiv:2006.00 020032, 2020.
Zhang, Y., Zhang, G., Khanduri, P., Hong, M., Chang, S., and Liu, S. Revisiting and advancing fast adversarial training through the lens of bi-level optimization. In In- ternational Conference on Machine Learning, pp. 26693- 26712. PMLR, 2022.
Yadav, C. and Bottou, L.. Cold case: The lost mnist digits. Advances in neural information processing systems, 32, 2019.
Yang, A., Yang, B., Hui, B., Zheng, B., Yu, B., Zhou, C.,
Li, C., Li, C., Liu, D., Huang. F., Dong, G., Wei, H., Lin, H., Tang, J., Wang. J., Yang, J., Tu, J., Zhang, J., Ma, J., Yang, J., Xu, J., Zhou, J., Bai, J., He, J., Lin, J. Dang, K., Lu, K., Chen, K., Yang, K., Li, M., Xue, M., Ni, N.. Zhang, P., Wang, P. Peng, R., Men, R., Gao, R., Lin, R., Wang. S., Bai, S., Tan, S., Zhu, T., Li, T., Liu, T. Ge, W. Deng, X., Zhou, X., Ren, X., Zhang, X., Wei, X., Ren, X., Liu, X.. Fan, Y., Yao, Y., Zhang, Y., Wan, Y., Chu, Y., Liu, Y., Cui, Z., Zhang, Z., Guo, Z., and Fan, Z. Qwen2 technical report, 2024a. URL https: / //twxiv..orr////////.. abs 2407 10671.
Zhang, Y., Li, P., Hong, J., Li, J., Zhang, Y., Zheng, W., Chen, P.-Y,, Lee, J. D., Yin, W., Hong, M., et al. Revis- iting zeroth-order optimization for memory-efficien 11m fine-tuning: A benchmark. In Forty-first International Conference on Machine Learning, 2024b.
Zheng, S., Meng, Q., Wang, T., Chen, W., Yu, N., Ma, Z.-M., and Liu, T.-Y. Asynchronous stochastic gradient descent with delay compensation. In International conference on machine learning, pp. 4120-4129. PMLR, 2017.
Zinkevich, M. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pp. 928-929-999 2003.
Yang. J., Ji, K., and Liang, Y. Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems, 34: 34:1167771 13670-13682, 2021.
Yang, K., Huang, J., Wu, Y., Wang, X., and Chiang, M. Distributed robust optimization (DRO), part I: Framework and example. Optimization and Engineering. 15(1):35- 67, 2014.
15

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
Appendix
To improve the readability of the Appendix. we have organized its contents follows: In Appendix A and B, delve into the comprehensive proofs of Theorem 4.6 (Iteration Complexity) and Theorem 4.7 (Communication Complexity). In Appendix C, the detailed proofs of Proposition 3.1 and 3.2 are provided. Furthermore, we offer the theoretical analyses about the cascaded polynomial approximation in Appendix D. Additionally, detailed discussions about the soft constraint are given Appendix E, and the discussions about Qin and Nout are also conducted in this part. In Appendix F, details of the experimental setting and additional experimental results are provided. The discussions about Assumption 4.4 and 4.5 are offered Appendix G, we show that both Assumption 4.4 and 4.5 are mild and widely-used in machine learning and optimization. In Appendix H, the reasons why choose the exterior penalty method in the proposed framework are discussed, and we demonstrate the close relationship between the original constrained optimization problem and the unconstrained optimization problem. In Appendix I, we show that the proposed framework can be applied to wide range of TLL problems, e.g., (grey-box) TLL with partial zeroth order constraints. More discussions about the cutting plane method and the choice of gradient estimator are provided in Appendix J. Lastly, the future work is discussed Appendix K.
Furthermore, enhance the readability of this work, the notations used in this work and their corresponding meanings are summarized in Table 3.
Table of Contents
A. Proofs of Theorem 4.6 (lteration Complexity)
B. Proofs of Theorem 4.7 (Communication Complexity)
C. Proofs of Proposition 3.1 and 3.2
D. Theoretical Analyses about the Cascaded Polynomial Approximation
E. Discussions about Soft Constraint and dm. Pout
F. Experimental Setting and Detailed Results
G. Discussions about Assumption 4.4 and 4.5
H. Exterior Penalty Method
TLL with Partial Zeroth Order Constraints
J. Discussions about Cutting Plane Method and Gradient Estimator
K. Future Work
16

---

L DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asympiotic Convergence
Table 3. Notations used in this work and the corresponding meanings.
Notation
Meaning
f((),, 1,2,3
hh level objective.
44, 44,Vi
5th level variable.
-,,2,,,=1,,,311 = ,,
7th level local objective in worker j.
Bi Vi - 1,2,,, = 1,,,NN
3th level local variable in worker j.
2; Vi 1,2,3
ith level global variable master.
Pin: Pout
feasible regions formed by inner and outer layer zeroth order cuts. 1 inner layer and outer layer zeroth order cuts.
I, CPout.
a in j... I,I. d, el
onn
n inner layer zeroth order cut's parameters.
a out cout
Lib Dis 5, di ete
gsh outer layer zeroth order cut's parameters.
FO)
penalty function.
F.(+)
smooth approximation of F(-).
P
smoothing parameter.
Fj.
optimal objective value of (-)
penalty parameters.
(nut)))
functions used in third level and second level constraint. gradient estimator for 7th level variable worker j
GRLLY Vi = 1, 2, = 1,
nor UEC Vi 1,3
step sizes for variables 2; 2z-
n out 2 22,22 94K33
standard Gaussian random vectors.
g
stationarity gap-
T())
iteration complexity to achieve e-stationary point.
Tı
parameter controls the trade-off between complexity and performance.
T
zeroth order cuts will be updated every T iteration.
the number of workers in distributed systems.
parameter in L-smoothness.
d, vi 1,2,3
the dimension of 7t level variable.
A. Proofs of Theorem 4.6 (Iteration Complexity)
In this section, the detailed proofs of Theorem 4.6, i.c., iteration complexity of the proposed DTZO, are offered. The iteration complexity refers to the number of iterations for the proposed algorithm obtain the c-stationary point (Jiao et al., 2023). According to Ghadimi & Lan (2013), the gradient of the smooth approximation of F, i.e., Fμ (which is given in Definition 4.3), is also Lipschitz.comie continuous with constant L,p. (0 < T,p T.), thus, we have that when 1. 2 Tí,
( - +i,
(V Vais Fa(txl,) {x())}
( - +is}
{a - }
{ V (2())
+
112
[+1 3
mV (1 ). (=()))
(ne Ger, ( (+
Ve, (ta (x())
(30)
F (21))
(nag Gas,, (2)))
(V ((ao
(May Gas,, (x)(())())))
( m (1 (2)))
Σ Σ 2 (( (x())))(2()))
17

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
According Assumption 4.5 (i.e., function F has L-Lipschitz continuous gradient) and combining it with Cauchy-Schware inequality, we have that,
T
141 2
2, ((
2 2
(F((E()))())) +
22 2+1 2/2
V z2 [(1a))))
+ 111
2+11 2/2
11
2/4 - 2/
2/ - 2/
2 2 T
V 21 F((o),))
= F(
(1 1. 1,{25)) +
22 1+1 - 2/2
V 22 (((1)
(31)
23 1+1 2/3
V2, ((ta.))
21 2
VxI F((a())) - V (((
#1 ++1 - 21
+
22 ++1 22
V V (. - (x,,(((
+ I1l
22 t+1 25
|13
++ 2/
(( - ((a
[+1 23
m 2 IV F( (x
< F(
Mz
1P.
Combining Eq. (31) with the Eq. (3.5) in Ghadimi & Lan (2013), we have that,
Fx(( ) 1=( /² L(N+1)) F(((t))) }, (2)+1))
2
< F(((a)))) J, (x1)) - Σ
3
(1/z
(I+1)n2
Vz,
F(( J. (2))) + Σ Σ
3 N
|1
2
(32)
1=1
5=
s (a }, (=(1))
Σ (12
(L+1)m
+
Σ
3
N
++1
-
+ LUNNDDE
Combining Eq. (30) with Eq. (32), we can obtain that,
T
Un (1 ).(2) {z)1)}
{V vn (x((())))
{Te Gæz, (1z(5)) }, {211)}
V w F (xf))
{ne Gas, (fzt ), {x11))}}
[ 2s, Fp (n (x(1)
N
Mes aG.,, (fa1g)) 1+11))11111---- Σ (1z, (1+1))2 3
+ L Σ Σ
||[ F (( (21))1
1=1 1=1
3 N
+ Σ
||
1) E, di
(33)
=1
(Man Gan, (1zb }, (2(1))
( y (2(1)
= =alttl
Gaz, (1x(T) ), (2(1))
V ( (2(1))
-
(ney Gas, (1x1)) ), {x11)}
V F. (( (x())
+ ΣΣ Σ
3 N
LA |Gzz, (( (2(1)122
Σ (12
3
(1+1)
V x;
F (( gb (2!))1
2
==1Ø=1
1
+ +N E,) d..
18

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
Taking expectation on the both sides of Eq. (33), we can obtain that,
B[Fa((= +++(+
< (l }. (2 - 3 N
Σ Σ
Um,
V
(1 + +1)E,d d;
(34)
Mie Bll| BlllGa.. (La) (2)))
(12z
|||
Vz, F( b (2)))
Combining the definition of Gui,,, Gaa,,' Gas., with the Eq. (3.12) in Ghadimi & Lan (2013), we have that,
1²L²
(1o,, 2(d + 4))lVm., ((aa),))
2 (di 6)²
(35)
(Ht, - 2(d + F (+))) + 1²112
(d2 + 6)²
(36)
2
+ 12L22
(1 < 2(d3 +
(dg + 6)
(37)
2
By combining Eq. (34) with Eq. (35), (36), and (37), we can get that,
ELP }, [=
3 N
+ +1) d, (F }. [211 - -Σ n2 Vo., (. + 1-NN+I
1=1j=1
N Line (2(d: + 4))4 x.,, (( -4 (d: =)6)
(38)
(L+1)O2 1. (,
that is.
(I++))02 2
Ma: Van,, Pp(( (21)) + Σ (1=
)[[ (( {=D)
< E[ 1, + LLN(N + +,),,d, d:
(39)
Lm (2(d. + 44]/V F( (21))1 + "²1² (d. + +)²)
Combining Eq. (39) with Eq. (3.8) in Ghadimi & Lan (2013), we can obtain that,
Te. (3 Ve., ). - 212 (d, + +3)²)
3
(1+1)
+ Σ (Mzz
2
IV (2))) + Σ (11= (1+1)² )[ F((ag))) (2
< Σ
(40)
<
[F (14)))
+f + E1),,d, di 222 (d: + 6)²)
3
+ Σ
Σ Enee (2(d: +
=
19

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
that is,
Mei
2L(dd + 4)m [V 1,,, P((d,)
(1+1)
(1%=
2 z. F((z) ((
(41)
N
Te, 12:1 1.3
- (2 ). (2()) F/, ((x))) (2)+1)) + Σ Σ
2 (d: + 6)3
j=1
+ nm no: (d. (3)+ + p3 L(N + 1,
3 N
According to the setting of 2 = 1,2,3, i.., 0 << 12. S sTdd+44) i 1,,,3, we have that,
Ta. 2
2L(d; + 4)m > =
=,,==1,2,3 1,
(42)
Likewise, according the setting of N2,, = 1, i.e., 0 <<<= 1/2 ZZZ+IJ1 2,,2,3, we have that,
(1++1)m2
12
> 0, = 1,2,3.
(43)
2
Combining Eq. (41) with Eq. (42) and (43), we can obtain that,
3
N
Va.,,
(. + Σ V F( (2))I)
Σ
Σ
2L(d: + 4)ma.) |1 m. F((af ( }, 11
2
min
Nmm
(d, + 4)ma, : Nx5
(L+1)
2 i = 1,2
2
3
(I+1)
Σ (1==
)// z: F F( J. (21))11
i=l
min
Mes
(Lg + 4)m 7T. (L+1)02
1,23
(44)
3
Fa((att)) ) {2(1)) - F (1 ++ ". (2]+1])+ + Σ 2
(d: 3)
T= - - 2L + 4) Nz. (L+1)m2 , = 1,2,3
min|
p² LA (d: + 3)3 + 12I(N + +1)E, di
Σ
Mes
2L, + 4)mi. nz. (L+1) i= 1,2,3
min
Summing up the inequality in Eq. (44) from 1 Ti to T(c) - 1, we have that,
20

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
-
N
3 IV, F(vi,
1
Va.., F((a))) (211)11 +
T(e)
Ti
[= T)
i=1 j=1
1=1
F (1
T1 (2
F Fu(t0
I(c)
1 T(+)
1.
min
Ne 2
2L(d; + +4)ma,
(I+ U++1)ng
i 1,2,3 (T(e) Ti)
2
N
(d: + 6)² + Σ 11 1e N (d: +3 + +22 1)E, de
Tiu 2 min
2L(d; + 4) 112 (1+1)ne 1,2,3
(45)
max tE(T))
Fu( ) {211) - Fjz
Mmu minl
2L(d; + 4)m2, 112
(L+ 11t1) ; = 1,2,3] (T(c) - Ti)
2
2
Ma L N (d; + 6)²² + Σ
# p
(d: +3)² + + I1E, de
1=1
min { Mi: (d: + 4)m 112 {
(1+1)n i 1,2,3
According to the setting of Ta, N2, = 1,2,3, we can obtain that,
Te 2L(d; + +4yle = -nm; (1 - 2L(d, + +4)mo
2
1, 2,2,
(46)
4
(L+ + 1)12,
12 (1 (L + 1)71.
Us
1/2
2
i = 1,
(47)
2
2
4
Thus, we have that,
1 -
V m.. F((x))), (2))) + F(E,,
T(c)
T (=
max Fu Fu(( (atgh-ff)) f=1z)) Fj,"
1E[Ti]
(48)
min (Mai Thoy Mays May Mm2 ]z (T(()) -T)
2na ,² 2 + 6)3 + Σ 1² 1 N(d; + 3)3 442 + 1) Σ, d
min {Mas Meys Tans T1 Nay [m
According to the setting that,
1
1
3
Tmm 1), min
1 1,2,3,
(49)
8T((c + +4) 8T(d2 + 4)' 8T(ds + 4) 2(T. + 1)' /T(c) Ti
21

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
have that,
T N
1
VV.,, ((())))(=
+ Σ I ((el,)
T(e)
Ti
t=
(=1 j=1
4
max tE[T)
Fp (f 1 {21))= FP
(T(c) - Ti)
+4( 5L(d2+4) 8T(d3+4] 2[++1]) VT(O)-1:
3 2T, 1 (2 + Σ
1e (d: +3)²
442 L(N + l)d:
3 min 8L(d++I) i SLi2++4)+ 8LJds+IJ: 2[[+1)] T(())
(50)
max Fu((aff)) (=1)) Fyx" [E[T9]
(max (8L(c) + 4), 8T, 4), 8T(ds + 4), 2(L+1)
3
-(c) -
( max Fu(tot (+(()))){({)))))))))))))))))))}) - Fi,'' (E
VT(c)- Ti
T(c) -Ti
3
11 +6²² + Σ
I...2Ndd,+3) +3)*
:=1
44² L(N + 1)d; max &L(d, + 4), 8L(d2 + 4), + 4). 2(L Σ
+ T(c)-(7
Since 112; < 5L(d 3, obtain that,
- 3 N
1
V W...y (( ((()))) + Σ
((at,,
T(c) - T
[=
f=1
max Fa((2t ( ). (=f)) F/.²) rE(Ti)
(max (8T(d1 + 8T, 8L(ds + 4), 2((t1) })
T(c)-Ti -Ti
(51)
max Fy Fu (z()) - FF,') VT(E)- -
(T(TT)
LLL'N
66²
+ Σ d
3
(de + 3)3
T(6)-
4
iml
44 LIN + 11dd (max { 8L + 8L(d2 + 4L),8L(ds + 44)
2(L
maxx
+ +v T(c) T2
3
Because of T(c) -T, 2 1, we have that - < VT(e)-
Combining with the setting of μ. i.e., n¹² S [ we
22

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
can obtain that,
T 3
V m.s (((t))),< +
Σ
V2,
T(c) - T
[=]
i=1
4max (L((d + 8Ld2 + 4), 8L(d3 + +4) 2(4+1)
max (1([T]]
Fu(t (=))) FF
3
T(e) -Ti
max 7, - Fpp 1 tE(Ti]
(d. + +6)
1
3
1
L
(d: + 3)
VT(c)- -Ti
d, + 4 T(e) Ti
T(e) Ti
1=1
1=1
8L(d) + 4), 8L(d2 4), SL + 4), 2(L 2(L+1)
4L(N + 1)dk
+ (T(e) -Ti)
(52)
max
T(e)- -Ti
4(1 + max
[LL(d1 4), + 4) (L(ss + 4), 3
((+1)
max Fu((z (213) (=(11) -Pp' LE[T]]
VT(c) Ti
12 3 (d: + +))
3
+ 1
(d. + 3)3
1
4
d, +
(T(e)- Ti
(T(E)-1i
3
((++1)]
max 8L(d + 4), 8I(22 + 8Id + 4),
+1) 4L(N + 1)d, VT(c) Ti
3
Combining the definition of stationarity gap and e-stationary point in Definition 4.1, 4.2 with Eq. (52), we have that,
p
3 N
3
V wis F((2))
T(t)
Jo
(2,
1211
+
| z.
F(
T(e)
(z, 1112
1=1 1=1
T(c) 1 3
3
V f F( (211) + Σ v F(f S (2)))
T(c)
T
t=T
i=1
f=1
4(1 + max
(d + (L2 + 4), 8L(g + 4), 2(L+))
max Fu (21)) (z())) -Fp" (E(Ti]
(53)
3
VT(c)- TT
2 3
(d, + +))
1
+ L
(de + 3)$
d; +4
VT(c)- Ti
(T(()- Ti
1=1
1=1
3
2(L + 1)
1
max
8L(di + 4), 8L(d2 + 8L, + 4),
+1
4L(N + +1d,
3
/T(c) -T Ti
Thus, we can conclude that, when
3 Σ
(a (x())) - F2." ))
T(e) 2
T + d
max (E(m
3 +Ti
(54)
we have that [T < e, where constants
d = 4(1 + max { SLL( 4), 8L(d2 + 8Ld3 + +4,, 2(L + 1)
(55)
3
23

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
G = [6) + (2, 33 4[d;44]
(56)
+4L(N + 1)d; mmax {BL(d + 8L(8 + 4), 8L + 4), 2(++1) +
B. Proofs of Theorem 4.7 (Communication Complexity)
The overall communication complexity of the proposed DTZO can be divided into 1) the communication complexity at every communication round and 2) the communication complexity of updating zeroth order cuts, which is discussed as follows.
1) The communication complexity at each iteration.
At each iteration, e.g., (L + 1)th iteration, the workers transmit the updated variables æi. 2 2tt1 to the master, resulting in communication complexity of Σ Ei d. Upon receiving these updated local variables, the master proceeds to update the global variables, Then, the master broadcasts the updated variables 21 2 xft1 and gradients
V Væ,, (( ( }, {ars.) 1,21 2t+1 21+1 2 ), 2,3 to worker j. Therefore, the cumulative communication complexity from t
T(c) is
C = (2d) + 3d2 + N.
(57)
2) The communication complexity of updating zeroth order cuts.
During every iteration T Ti), the cutting planes are updated to refine the cascaded polynomial approximation, involving two main steps:
k+1 are transmitted from worker j. 2a) Updating the inner layer polynomial approximation: In this phase, local variables 3..
while global variables =3 k+| are sent from the master in the (A + 1)th iteration. The communication complexity associated with updating the inner layer polynomial approximation can be expressed as follows:
Ti 2 j=1 T
TKds-
(58)
2b) Updating the outer layer polynomial approximation: During the (k + 1)sh iteration when updating the outer layer approximation, the worker transmits the updated variables 2, to the master. Subsequently, the master broadcasts the updated global variables I+1 to worker j. The communication complexity involved in this process can be expressed as,
Σ
N j=1 TKd2.
T
(59)
Combining Eq. (58) with Eq. (59), and considering utilizing one communication round approximate the din ( #1, #2, 23) and Dout Φ0ut( }, (#a,)), 21, 22, 23), i.e., K 1, have that the communication complexity of updating cascaded polynomial approximation is,
T C2 = 2N [T(2 da).
(60)
Consequently, the overall communication of the proposed method is C1 C2, which can be expressed as.
T
(T( + + dz)N + 2N
T T(d, + dz).
(61)
24

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
C. Proofs of Proposition 3.1 and 3.2
C.1. Proofs of Proposition
For any point ((03,)) h. 21, zz', 23) in the original feasible region, i.c, 0in(1 21, #1, ,2',=²) = O, according to the properties of L-smoothness, have that,
Pin (1l(f33)11 21, Z2' 23)
{
{2%
din (1203 3. 21, =//2 2/5)
Od (1 D
21
zf
of 22, 31, (55)
22'
z !
23
z/
}
{ {
21
z1
112
2'2
x/
23
{ }
{zts.g)
2m (12g..)) 29. =b',)
23', 2²²,2
21
2
(62)
Ø2'
2/²²
23
z/
{ }
{
Bdr (mm) hef. b. 11 .0))
T
zf
G (123),))22 2b',
22
23
{23 }
{
11
z1
112.
x2
x1
z/
According to E (f=1),) 2,,, |,,,, 2//;21)
ip (1 ), 21, 2²5 24), taking expectation on both sides of Eq. (62),
have that,
E Bloma(aa (f 21, 22,22',
{x }
{
> Elom((< 21, 250,
EI 2/ =
21
21
22
2//²
23
2/.
{o
{
0mm ((m ..
Pn (12g 21. 25² =5))
#1
(63)
8 (.
#3
2//
{ }
{2 }
z
112
x2
Z3
=1
25

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
Combining with the Cauchy-Schwarz inequality, inequaalyy we have that,
ii (133)) 21, , za]]
(23
(arss)
2 Bloia( (loml(aa 2f, = =g)1= B [ ((ag.)) 121 25', zb)+T
#1
22'
23
(64)
{
- -1 B0mn )aa oi (21 *a)
(1 2f, x1,22/ 2
ø1
112.
x2'
22
23
And according Eq. (3.6) in Ghadimi & Lan (2013), obtain that,
I1 (taggh f. 2/',,2,, x5) Ochin (arg,)), 2/1 =/, 233)
112 < 22
(65)
0((23.)) 21, R2, 23)
4
By combining Eq. (64) with Eq. (65), we have that,
Ei (1 ( z1, 22,
{ }
{arh.))
2 (0mm(123 25' +5)] +5]]+E(G.. B )a (( +5)]
22'
2/2
23
z/.
(66)
{I }
{ {2)
11
21
2
112.
x2
z//²
23
For any point belongs to the original feasible region, i.e. om (f2rg,) 21, 22', 23) that it also satisfies that,
0. according Ein 2 0, we can obtain
{
{ (
Eldin Eloin(( ( 21,
226, x5) + Gin (125), 25',
#1
2
#2
z
(67)
{
L+1 <
21
21
112 + "²
+ Eim-
2
Ø2
2//²
23
z3
According to Eq. (9), we conclude that for any point belongs to the original feasible region of constraint
din ((23,) ) 2 22' =3) 0, it also belongs to the Pt that is, the original feasible region is a subset of the feasible region formed by inner layer zeroth order cuts. Let Sj, denote the original feasible region of constraint ei. ((x3,)) J. æ Zz' 23) = 0, we can obtain that the feasible region formed by inner layer zeroth order cuts will be gradually tightened with zeroth order cuts added according to Eq. (67), that is,
Sin
p1+1 in
C
pt. in
C... p0
(68)
26

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asympiotic Convergence
C.2. Proofs of Proposition 3.2
For any point (122,), (. 21, #2, #3) in the original feasible region, i.e. Pout (( (33.5) (.3.J,=1111 22, 23) accord- ing to the properties of L-smoothness, have that,
Pone @f (122))((0ss 22,
{x22 } {
{ }
Adous ( (1=22 Joi (e
Dout ( } 21. =2, z5))
01122 , 2. 3. #2.35)
21
21
22
[22
{2 } (arh.)
[
ll
21
2{
112
22
23
2/
{x22)) }
{
{x3,,} }
(69)
Dour (( ( 21, 2/2 25))
+.G (1)
21
21
22
23
2//
{x02.)
(
{x:s.))
(
T
0 (1022111 (11.
G (t)
21
#1
22
z/
23
2/
[ }
{
[
{oo }
|ll
21
2
112
22
2/
#3
2
27

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
where Gou(() (t) is the simplified form of Ch (122g) (# =1, z/, z5)- According @u,out ( (12 (1)) ) ( 21, zi, z5), taking expectation on both sides of Eq. (69), we have that,
El (!)
Elpout (fx2,)) (a...) }. 21, 22, 23)]
{ } { }
{
2 El ((bg)): ( z1, 23. =5)] (
#1
#1
22
z/2
23
z/3
{
{2 }
{a:s.p)
{2 }
0ooa (102, J.das /aaf Joff
(70)
01(22,5 (2
w, (t)
2
21
22
z/
2/
{2225} }
{v3,}} }
{
11a
22
2/
23
2/
where ou. (1) is the simplified form of ou (1a2gsh (ach =1, =5, zB). Combining with the Cauchy-Schward inequal- ity, we have that,
Bioout ( (1 (x3.)) #1, #3)]
{ } { {x }
{
(
2 E[oout (f f z1. 25. x5)1 E[G
21
#1
22
2/
2/
80out ( 13, J
(71)
on (1)
2
0 2g 1 (23,5 -12.2,20)))
{x2,}} }
{zb_1) }
{
{
1+11|
2
21
21
112.
2/
And according to Eq. (3.6) in Ghadimi & Lan (2013), we can obtain that,
adout ((x25)) }. (ob 2/)
12= 122 (V(++((++1)(++dd))
o1 (t)
(72)
a((02.)) }. {I 21, 22, 23)
28

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
By combining Eq. (71) with Eq. (72), we have that,
Bloout (102.11 (23.sh 21, 111222 22, #3)]
{ }
(
{ }
(
2 [( { fi 22, x511 + [[
=1
22
x2
23
z/
(73)
{
{
{2z.T)
{
8 [[
|+1
2
2
112.
22
z/
23
For any point belongs the original feasible region, i.c., Pout (fx2,): {x3.)) ø1, 22, æ3) 0, according to Ein 2 we obtain that it also satisfies that,
{
{2 }
{
{ 1
E ooouu (ta hi,, x5, #5) +G) (ta2, 2,, 25)
21
21
(74)
Z2
2/2
23
z/z
Σ 2 E,
(f 1 +
According to Eq. (11), we can conclude that for any point belongs to the original feasible region of constraint dout Dout(fa2,, (fæ2.s), (m ) 21, #2, 23) 0, it also belongs the pout. that is, the original feasible region is subset of the feasible region formed by outer layer zeroth order cuts. In addition, let Sout denote the original feasible region of constraint Φout ( (.s,y), 1.1.).1.1. #2, 23) based on Eq. (74),
obtain that the feasible region formed by outer layer zeroth order cuts will be gradually tightened with zeroth order cuts added, that is,
Sout S pt+1 C pt. C .... C Pout-
(75)
D. Theoretical Analyses about the Cascaded Polynomial Approximation Problem
In this section, we theoretically analyze the connections between the original distributed trilevel zeroth order optimization problem in Eq. (2) and the cascaded polynomial approximation problem Eq. (8). To facilitate this discussion, we start by examining the distributed bilevel zeroth order optimization problem, which can be expressed as follows,
min
Σ ==1
f1,
(76)
s.t. x2 = arg min
Σ
(x1,
22'
j=1
var.
29

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
The optimization problem in Eq. (76) can be equivalently reformulated as,
min Σ (Z1.. F2,))
j=1
s.t. 21,5 ø1, vj 1, .N.
N
[x2.} ) 22
arg min Σ 22. (21, 02.5")
(77)
{ ',''' ;=1
s.t. 22.j = 22', Vj = ,,,,, N {mis}r { | 21, 22-
var.
By utilizing the proposed polynomial approximation with zeroth order cut, obtain the following zeroth order polynomial approximation problem,
N min Σ fij ( 22.))
F=1
s.t. 1i
21, Vj 1, N
(78)
2 Σ az 2 b2.j.1 22. Σ C₁,
Tz 22
+ Se,Vi
var. { ( ( 21
According to Proposition 3.1 and 3.2, can obtain the feasible region of the problem in Eq. (77) is subset of the feasible region of the problem in Eq. (78). Thus, we can conclude that the zeroth order polynomial approximation optimization problem in Eq. (78) is the relaxed problem of the distributed bilevel zeroth order optimization problem in Eq. (76).
For the distributed trilevel zeroth order optimization problem, we first define the following feasible regions.
h0 ({x2,) 1. h.2,, z2, z3) S Eout, Vl,
S
(79)
21 x1. Vj
S2
N arg min Σ J2.j (21, 22.5 xs.s))
{222}}
(02,))= f=1
112 < Eout.
(80)
far
22
s.t. x2.j = 22', Vjj
(( ) 21, z2': 23) S Ein, Vl
21 = -1. Vj
S3 =
N
arg min Σ f2. (z1, x2 x3..)
(12,' j=1
{
s.t. 22.5 22 Vj 1, ..... N
{ 11121
||
#2
(03. 103.).233 23= aig min
N Σ
fa. (z1, 22' x33.")
=1 0,
(81)
(ma.)'),2s j=1
s.t. Ø3.5 23 Vj = 1, 1,..., NN
21 = 01,fs Vj
seen from Eq. (79) and Eq. (81) that S and S3 respectively represent the feasible region of optimization problems in
30

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymptotic Convergence
Eq. (8) and Eq. (3). For any feasible solution
(+t,))((2}) of optimization problem in Eq. (3), it satisfies that,
N arg min Σ (2, D2.' $3.5) (02.)) f=1
{ 22
s.t. 22.j" = 22 Vj = , NN
112 1==0 0.
(82)
( 23 arg min Σ fa (21, 22', x3..")
(as,)' ',s'' j=1
s.b. 33.j" = z3's Vj 1, .N
Based on Proposition 3.1, we have that the feasible region of constraint Φin (1 ( 21, =2', za) = is a subset of the feasible region formed by inner layer zeroth order cuts, i.e., { ( J. 2 23| h."" (( 21, (1, =2', 23) S Sin VI}. Moreover, the feasible region formed by inner layer zeroth order cuts will be continuously tightened with zeroth order cuts added. Thus, let satisfy that,
N arg min Σ f2.5(21 22,5 (3.5)
N arg min Σ fa. (21, 222." 23.1)) tea,//az f=1 s.t. D2.5 x2', vj.
v'> j=1
s.t. 22.5 = x2' Vj 1, 1,. .
113
{ 22 23
arg min Σ fa.z (21, 22', x3.5)
(83)
(1 } 21, 23) Sein
(ora. ",2s' 1=1
s.t. 23.5 23' Vj 1,... NN
S 8.
By combining Proposition 3.1 with Eq. (83), we can obtain that 3 will continuously decrease with inner layer zeroth order cuts added. By combining Eq. (82) with Cauchy-Sehwee inequality, we can obtain that,
N arg min (m2.s")
min
Σ
fz.j (81, x2.5" , .33.))
( 22
", j=1
11
112
s.t. Ø2.5" x2 Vjj
h/t (1#3,) }. 1, 22' 23) Emi VI
N
arg min Σ f2.j (21, 22.5' x3.5)
(m2 2,22'' j=1
( }
s. æ2. 22 ,,'' Vj = 1, N
=11
82
{ ) 23= arg min Σ fs., (2,, 2z', x3.5")
{ j=1
s.1. 03,j" 23', Vj = -,.... ,
arg min Σ f2, 121, 22.5'' (3..)) (0ai')) f=1
(84)
arg min Σ f2. (²1, (21, 22.6' (
s.t. 22,5' 22' Vjj 1, .NN
tw2." h,zz' j=1
112
s.t. 02. = 22 Vj.
(mas): 23 = arg min Σ ʃa.j (21, 22', ma.)))
(1 21 22' 22) Sin. Vl
(#s ),as' j=1
s.t. æ3. = 23' Vj = ..... . N
arg min
Σ ʃa (21, 222.3' a3..))
arg min Σ (2,, (3 22.-" )ي.د))
wwa.shi,ss j=1
< 2|l (22. j=1
s.t. 02.5"
22' Vij 1,... .N.
112
s.t. D2.5 = =/ Vjj
N
( ) 23 arg min Σ
fa. (2 x2)))33)
(( 21, 22' k5) Ein,
Ein. 1I
{ 1, j=1
s.t. U3,j"' = 23' vj = 1, N
28.
31

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymptotic Convergence
By combining the definition of S2 in Eq. (81) with Eq. (84), we can get that S3 is a subset of S2, i.e., S3 E S2 when set Ein 2 0 and Sout 2 233. Based Proposition 3.2, we have that S2 is subset of S1, i.e., S2 E S1. Consequently, we can get S3 E St, indicating that the cascaded polynomial approximation problem is the relaxed problem of the original distributed trilevel zeroth order optimization problem. Moreover, this relaxation will be gradually tightened with the addition of zeroth order cuts based on Proposition 3.1 and 3.2.
E. Discussions about Soft Constraint and Piny Sout
Soft constraint. A soft constraint refers constraint that can be partially violated without rendering the optimization problem meaningless (Kautz et al., 1996; Régin, 2011; Wilson et al., 2022). It is shown in many bilevel and trilevel learning works that the lower-optimization problem often serves as soft constraint to the upper-level optimization problem. Examples are provided as follows.
In bilevel neural architecture search (Liu et al., 201 (0), rather than computing the optimal solution for the lower-level optimization problem, the result obtained after single gradient descent step can be used as an approximation of the optimal solution at each iteration.
In bilevel meta-learning (Ji et al., 2021; Finn al., 2017), instead of solving the lower-level optimization problem to optimality, the results obtained after multiple gradient descent steps can serve as approximation each iteration.
In bilevel adversarial learning (Madry et al., 2018; Zhang et al., 2022), which a min-max optimization problem, instead of solving the maximization problem to obtain the optimal solution, the results after several projected gradient descent steps used the approximation at each iteration.
In trilevel learning, AFTO (Jiao et al., 2024) used the results after K communication rounds to replace the optimal solution to the lower-level optimization problem at each iteration federated trilevel optimization problems.
In trilevel learning for masked autoencoder (Guo et al., 2024), instead of obtaining the optimal solution to lower-level optimization problems at each iteration, Guo et al. (2024) used the results after several iterations of gradient descent updates as the approximation.
In trilevel learning for enhancing out-of-domain generation in machine translation, He et al. (2024) used the results after one-step gradient descent update as the approximation for the optimal solution to the lower-level optimization problem at each iteration.
{
is seen from @in (I.3( 21, 21. xz) =
arg min Ej fa.5(z11111 (21,2z', æa.j') s.t. Va.y' = 23' Viil that Z3 (aa."")ass"
distributed optimization problem needs be solved if an exact din (( (x3. 1 z2, 23) is required. The lower-level
{23..) }
optimization problem (i.c.,
arg mig Σj (z ze', 23.3 s.t. x3.)." 23' Vi) can be regarded as a soft {=a."'/zza
constraint to the upper-level optimization problem. Inspired by many works in bilevel optimization and trilevel optimization, e.g. Ji et al. (2021); Jiao et al. (2022a); Yang et al. (2021); Franceschi et al. (2018); Liu et al. (2021b); Mackay et al. (2018); Choe et al. (2023), that utilize K steps gradient descent steps to approximate the optimal solution to the lower-level optimization problem, function @m @m.((x3.)) (( 2 22', 23) this work can also be approximated based on the solution after K communication rounds following Jiao et al. (2024). Specifically, we have the following steps in (k + 1)th iteration,
Local worker j updates the local variables as,
s+1 D3
: = x3z nu Gin.s (z1, 22, 1. 2/1),
(85)
where T/e denotes the step-size, and
tHay, a)- f1, 5.235 m U3.3 + 275(2 - =4))
Gin (21, Z2, 33.3 x3)
(86)
where u is a standard Gaussian random vector, ?o > 0 is a constant. Then, workers transmit the updated local variables, i.., a.. to the master.
32

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
After receiving the updated variables, the master updates the consensus variables follows.
k+
23
N Σ 5= 15(2 =)
(87)
where 7/= represents the step-size. Subsequently, the master broadcasts the updated variables 23 to workers. Thus, the approximated din ((#3.s 21 22, za) can be expressed as,
{03. - 0b35 + The Ei=0 Gin. (21, 22, 03.5 =5)} 23 2 + 1)= EK- Σÿ=
Z2,
(88)
E 75 - 03.5" k41)
0 also serves soft constraint to the upper-level optimization problem. According to the definition of dout ((x2,)) { J. 21, #2, #3), that is,
Likewise, constraint Pout (22.)); { , 21, 22, 23)
Pout (x2.5) {x3.) ). #1, 22, Ø3)
{x2_}}
arg min Σ //. (21, 22,5 23.5)
(89)
||
(#1,)==2==
112
s.t. 22, = 22 Vj, 11 (03.5 21, 22, #3) (3) Sini Al
the results after K communication rounds can also be utilized to compute the estimate of dour (1 b ( 21, 22, za) following previous works (Liu et al., 2018a; Jiao et al., 2024). (k + 1)th iteration, we have that,
Local worker j updates the local variables as follows,
k++ 2.
= æ².5 - Tr Gaz, (21j Fzjj 22. 2z).
(90)
where we have,
Gæa. (z1, xb. Fz 2ÿ, k3)
(91)
az + tuu 2,0., . fa.5 (= (o..)
Ux 22 xz),
1
where ux, is the standard Gaussian random vector, 9j 0 is constant, Then, worker j transmits the updated 22, to the master.
A++
After receiving the updated parameters from workers, the master updates the consensus variables as,
22 k+1 2 (2 22. = V z2Pi Σ, [max (1i ((#3.)) 21, =/, za) Ein, 011²)
(92)
Next, the master broadcasts the updated variables dour (1 ( (00.jh=10000 22, z3) can be written as,
A+1 22 to
workers.
Consequently, the approximated
dout ((x2.)) (0 #2, #3)
{x:2 2.. EK= Th Gaz, (21, ab.j :3s. 2 23)} B2 22-2++ K-1 1/ (2p)(2 222 ) Vz2!i [mxx ((x3))) x1, 23) - 0]]))
]
(93)
F. Experimental Setting and Detailed Results
In this section, we provide the details of the experimental setting. In the experiment, all the models are implemented using PyTorch, and the experiments are conducted on a server equipped with two NVIDIA RTX 4090 GPUs.
In the experiment, we compare the proposed method with the state-of-the-art distributed zeroth order learning method FedZOO (Fang et al., 2022) and state-of-the-art distributed bilevel zeroth order learning method FedRZO, (Qiu et al., 2023), which are introduced as follows. FedZOO (Fang et al., 2022) is derivative-free federated zeroth-order optimization method, which can be applied to solve the single-level optimization problems in a distributed manner. In FedZOO, clients perform several local updates based gradient estimators in each communication round. After receiving local updates, the servers will perform the aggregation and update the global parameters. FedRZO,, (Qiu et al., 2023) is designed for zeroth order bilevel optimization problems. In each communication round, FedRZO,, involves the following steps: clients first compute the estimated optimal solution to the lower-level optimization problem and the inexact implicit zeroth-ore order gradient. They then update the local parameters and transmit them to the server. Upon receiving the updates, the server aggregates them obtain the global parameters.
33

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asympiotic Convergence
100
The proposed DTZO
The propased DTZO
FedRZOpl
75
FedRZOμ
ASR(%)
95
ACC(%)
65
S5T-2
COLA
MRPC
SST-2
COLA
MRPC
(a) Comparisons about ASR
(b) Comparisons about ACC
Figure 2. Comparisons about ASR and ACC between the proposed DT7O and state-of-the-art method using Qwen2-7B.
100
The proposed DTZO
The proposed DTZO
FedRZO
85
FedRZO,)
ASR(%)
ACC(%)
75
90
H
65
SST-2
COLA
MRPC
SST-2
COLA
MRPC
(a) Comparisons about ASR
(b)
Comparisons about ACC
Figure 3. Comparisons about ASR and ACC between the proposed DTZO and state-of-the the-trrrrt method using Llama-3.1-8
F.1 Black-box Trilevel Learning
In this section, the details of the experimental setting in black-box trilevel learning are provided. Prompt learning is key technique for enabling L.MSs to efficiently and effectively adapt various downstream tasks (Ma et al., 2024; Wang et al., 2024). Inspired by the black-box prompt learning (Diao al., 2022) and backdoor attack on prompt-based LLMs (Yao et al., 2024), the backdoor attack on black-box LLMs is considered in the experiment, which can be expressed as black-box trilevel learning problem follows.
min
Σ (D
L(g, (keii p, 8i)
N
s.t. kini
= arg min Amn
Σ
Σ
L(G, [ktri' ,, 8:), yi) + Al[Atr''
D
1=1
(#:i))
(94)
s.t. p arg min
Σ (s::1))DDy
L(G, Karis Men''p' .''''p''o v1)8),.)))
var.
X, k
where G denotes the black-box LLM. kuri p respectively denote the hyperparameter, backdoor trigger, and prompt. D and Dyal denote the training and validation dataset in jth worker, and N denotes the number of workers, Vi denote the tt input sentence and label. In the experiment, Qwen2-7B (Yang al., 2024a), Llama-3, (Grattafiori al., 2024), and Qwen-1 1.88-Chat (Bai et al., 2023), are utilized as the black-box LLMSs. The General Language Understanding Evaluation (GLUE) benchmark (Wang et al., 2018a) is used to evaluate the proposed DTZO. Specifically, the experiments are carried out on: 1) SST-2 for sentiment analysis; 2) COLA for linguistic acceptability: and 3) MRPC for semantic equivalence of sentences. In the black-box trilevel learning problem, we compare the proposed DTZO with the state-of the-art distributed bilevel zeroth order learning method FedRZO, (Qiu al., 2023), which is used address the following distributed bilevel
34

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
Test Performance (%)
DTZO
1900
removing
without removing
Training time (s)
83
1400
81
900
79
400
77
1500
4500
7500
USPS dataset
MNIST dataset
T1
Figure 4. Adjusting I' flexibly control the trade-off between performance and complexity, results on USPS dataset.
Figure 5. Training time (1000 communication rounds) of with and without removing inactive cuts.
Table Experimental details.
Dataset
Ta
Taa
A
@
SST-2
0.01
0.001
0.001
0.001
0.5
COLA
0.01
0.001
0.001
0.001
0.5
MRPC
0.01
0.001
0.001
0.001
0.5
MNIST
0.01
0.05
0.1
0.001
0.5
QMNIST
0.01
0.05
0.1
0.001
0.5
F-MNIST
0.01
0.05
0.1
0.001
0.5
USPS
0.01
0.5
0.001
0.5
zeroth order learning problem.
min Σ Dj=1
Σ
L(g, [krii p. se),
D
(BL.8:)~-D N
s.t. arg min
/==1 D
Σ (B..D.DD
L(G, (kri, p', sil, v.)
s
(95)
j=1
var.
Kuri
where G denotes the black-box LLM. kui and p respectively denote the backdoor trigger and prompt. D represents the training dataset in 5th worker, |D]] represents the number of data in training dataset, and N denotes the number of workers. 8t, yi denote the 5hh input sentence and label.
F22 Robust Hyperparameter Optimization
Robust hyperparameter optimization is a widely used trilevel learning application (Jiao et al., 2024; Sato et al., 202 1), aiming to optimize hyperparameters (Ji et al., 2021; Franceschi et al., 2018; Jiao et al., 2022h; Yang et al., 2021) and train a machine learning model that is robust against adversarial attacks (Han et al., 2024). In this work, we consider the robust hyperparameter optimization, which can be viewed as trilevel zeroth order learning problem as follows.
var min Σソ (X -;
w
8.l. w = arg min MN
[X + Pj, 5/ w/) + v||w01122
(96)
s.t. arg max Ey (X) + + "0'" w') P' p, W.P.
In this task, compared to single-level optimization, bilevel optimization considers the hyperparameter optimization, which can enhance the generalization ability of the machine learning model. Compared to bilevel optimization, trilevel optimization incorporates min-max robust training, which can improve the adversarial robustness of ML. model. The digits recognition
35

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplooic Convergence
Table 5. Ablation study.
Method
F-MNIST
USPS
UWaveGestureLLbraryAlll
MelbournePedesttran
DBZO
0.5213
0.7452
0.7043
0.6436
D-ZO(-)
0.6685
0.8212
0.7921
0.7013
DTZO
0.7007
0.8513
0.8243
0.7250
tasks in Qian al. (2019); Wang et al. (2021) with several benchmark datasets, i.e., MNIST (LeCun et al., 1998), USPS, Fashion MNIST (Xiao et al., 2017), and QMNIST (Yadav & Bottou, 2019), are utilized to assess the performance of the proposed DTZO. In addition, DTZO is also assessed on time series datasets, including MelbournePcdestrian, Crop, and WWaveGestureeLibraryaal sourced from the UCR Archive (Dau et al., 2018). To evaluate the robustness of each method, the PGD-7 attack (Madry et al., 2018) with ε = 0.05 is utilized. For the state-of-the-art distributed zeroth order learning method FedZOO (Fang et al., 2022), it used address the following distributed zeroth order learning problem in this task,
min Σド= (x uf., w)
(97)
var.
where N represents the number of workers in distributed system, denotes the model parameter. Xj and v represent the training data and labels, respectively. For the state-of-the th--hhe-rt art distributed bilevel zeroth order learning method FedRZO, (Qiu et al., 2023), the following distributed bilevel zeroth order learning problem is considered in this task,
min Σド= fg (X)atr DJ var 2))
s.t. w = arg min ΣØ= (X3, w') + 6lllo112
(98)
var.
9 w
where yp and u denote the regularization coefficient and model parameter, respectively. xy and v3" represent the training data and labels, while Xya and y, represent the validation data and labels, respectively.
Within the proposed framework, the trade-off between complexity and performance can be flexibly controlled by adjusting Ti, as discussed in Sec. Specifically, if the distributed system has limited computational and communication capabilities, smaller Ti can be selected. Conversely, if higher performance required, a larger Ti can be chosen. As shown in Figure the performance of the proposed framework improves with increasing Ti, allowing for flexible adjustments based system requirements. Removing inactive cuts can significantly improve the effectiveness of cutting plane method, as discussed in Jiao et al. (2024); Yang et al. (2014), In the experiment, we also investigate the effect of removing inactive cuts within the proposed DTZO. is seen from Figure 5 that pruning inactive cuts significantly reduces training time, indicating the importance of this procedure.
In addition, the impact of different choices of Ti on the convergence rate within the proposed framework is evaluated. As illustrated in Figures 6 and 7, smaller Ti leads faster convergence but affects the method's performance, resulting in higher test loss. Conversely, if better performance is required, larger T' can be selected, corresponding to more refined polynomial relaxation. In the proposed framework, we can flexibl adjust Ti based on distributed system requirements. The results in Figures 6 and 7 are consistent with our theoretical analyses presented under Theorems 4.6 and 4.7.
Following Qiu et al. (2023), the robustness in the proposed framework with respect to the choice of smoothing parameter y evaluated. The experiments are conducted on the robust hyperparameter optimization task under various settings of smoothing parameter, μ E {0.01, 0.001, 0.0001). choice of smoothing parameter μ. In addition, we also note that the proposed DTZO has faster convergence rate with relatively smaller μ4, because the gradient estimate improves when μ becomes relatively smaller, discussed in Liu et al. (2020).
seen from Figure and that the proposed DTZO is robust the
Furthermore, to analyze DTZO's performance improvements, we conduct an ablation study comparing DTZO against its variants: DTZO(-) and DBZO. DTZO(-) replaces the proposed nonlinear cuts in DTZO with linear cuts, while DBZO removes cascaded polynomial approximation, using only single-layer polynomial approximation. is seen from Table
36

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
0.8
T5=4500
T1 =1=000
1.1
0.7
T5=600
Test Loss on AS
Ti =6500
Test Loss
T 8500
1.0
T1=8500
0.6
0.9
0.5
0.8
0.4
0.7
0.6
3000
6000
9000
3000
6000 Iteration
9000
Iteration
Figure Test loss the proposed DTZO under various setting of Ti, results on USPS dataset.
Figure Test loss AS (adversarial samples) of DTZO under various setting of Ti.
2.0
0.01
2.1
μ 0.01
0.001
0.001 == 0.0001
= 0.0001
Test loss on AS
Test Loss
1.5
1.5
1.0
1.1
0.5
0.6
1000
4000
7000
10000
1000
4000
7000
10000
Iteration
Iteration
Figure 8. Test loss of the proposed DTZO under various selting of smoothing parameter μ,, results on USPS dataset.
Figure Test loss AS (adversarial samples) of DTZO under various setting of smoothing parameter results on USPS datasct.
that DTZO outperforms all variants, demonstrating the benefits of cascaded polynomial approximation and nonlinear zeroth order cuts.
G. Discussions about Assumption 4.4 and 4.5
The assumption that the domains of optimization variables are bounded (i.e., bounded domains) mild and widely used the theoretical analyses in machine learning and optimization, e.g., Assumption Deng et al. (2020), Assumption 2.3 in Sra al. (2016), Assumption A2 in Li & Assaad (2021), Assumption Zinkevich (2003), Assumption 6.3 in Huang al. (2024c), Assumption in Eq. (4) in Duchi et al. (2012), Assumption in Yang et al. (2024b), Assumption 3.1. in Khaled & Jin (2024), Assumption in Chen et al. (2024b), Assumption in Hazan & Minasyan (2020) and on.
in Cao et al. (2024), Assumption 1 in
Let ((*i,)) { {x J. z 25, 2g) represent the optimal solution of minimizing F2 (( H. (. (.s. (2,3)))3)) N Σ fig 22. x3.5). and (œ 2 R5.5) denote
(f=t,), { >. (x denote the optimal solution of minimizing
j=1
the optimal solution minimizing fi.j (Z F2.ji W..)). Thus, we have that,
N
Σ (h "5 S
> fi ( s j=1
Eis o5g, = zbgg)
Σ j=1
(99)
Combining the definition of F((21)). (22.)) (233 221, in Eq. (15) with the fact that ولا[رر - -2il|2 >
37

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
A1[mxx (1p (Mar"(()))))))))))) (03.gh 21, 2 25)
Eout }12 2 O, we can obtain that,
N
Σ ( 22g 23,5 _/2 L(N + E,
Σ fig (o) (
( x3.) :/¹ L(N 1) E,Ed d:
I Σ flg ( 23 5/' L(N + +1) E de
(100)
s F( P11
- - LIN + E, d;
S 1
= F
By combining Eq. (100) with the fact that n² L(N + 1) E, dj is a constant, we can obtain that the Assumption 4.4 (i.e., F); is lower-boundeds is mild since the assumption that f1, (i.))) is lower-bounded is widely-used and mild (Liu et al., a0 2018b; 2022; Fang et al., 2022: Li & Assaad, 2021; Liang et al., 2024; Tang et al., 2020; Shaban et al., 2019).
According to the definition of F((11,() (.2. }. (23.) 22,,.2, i.c.,
N
= Σ S1 ( D2.j 33.)) + بدااررة 21112
(101)
+ + A hhpt (1 (. 12 Eout ))
we have that 1) term ورر | -21 satisfies the L-smoothness because the domains of variables æ1,j and 21 are bounded; e satisfies the L-smoothness because the domains of variables are bounded and there are most [#] zeroth order cuts. Moreover, the assumption that fi,J (I1. 22, z3.5) satisfies the L-smoothness is mild and widely-used (Ji et al., 2021; Gao, 2024; Gao et al., 2022: Chen et al., 2023; Li et al., 2024; Wu et al., 2024; Huang et al., 2024a; Jing et al., 2024; Chen et al., 2024c; Xiao et al., 2023; Hong et al., 2023). Consequently, we can obtain that F((11, (222)) ), ( 2, 22,23) satisfies the T-ssmoothness, i.e., Assumption 4.5 is mild.
2) term Ee [maxmax(( (u (122,) ( ;
H. Exterior Penalty Method
Exterior penalty methods are widely-used when dealing with constrained optimization problems (Boyd & Vandenberghe, 2004; Bertsekas, 2015). In this work, the exterior penalty method is utilized based on the following key reasons. 1) The lower-level optimization problem often serves as soft constraint to the upper-level optimization problem, discussed in Sec. 3.1 and Appendix E, which can be partially violated without rendering the optimization problem meaningless. We can flexibly control the importance in the upper-level and lower-level problems through adjusting the penalty parameters. For example, if the importance of the lower-level optimization problem is required to be high within the nested optimization problem, we can raise the penalty parameters. 2) The complexity of using the exterior penalty method is relatively lower. For example, if we utilize the gradient projection method, which is also widely-used in constrained optimization (Jiao et al., 2023; Xu al., 2020), we need to solve additional one constrained optimization problem with non-convex feasible regions at each iteration when performing projection, i.c.,
3
N
3
min
xi 1 +
Σ
|| +
- -2
1m1
s.l. æ1j = 21, Vj-
1,...,
(102)
Σ
3 N
out (3
2 + out T
+b
Fi
+ >
3
oot'"
2 + 2; Soout VI ci
var.
(wigh (22.}) {xa. 1 22, Ø3,
where ((af))), 1, f2(+1))) denotes the points in (t + 1)th iteration after performing zeroth order gradient descent. Thus, it is seen from Eq. (102) that the complexity of utilizing gradient projection descent method is higher than using the penalty method since it requires addressing the constrained non-convex optimization problem in Eq. (102) at each iteration.
38

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymptotic Convergence
Likewise, utilizing the Frank-Wolfe based methods (Shen al., 2019; Garber & Hazan, 2015; Zhang et al., 2020; Xian al., 2021; Wang et al., 2016; Balashov al., 2020) may also lead relatively more computational complexity since it also needs to solve one additional constrained non-convex optimization problem, i.e.
N Σ
min Σ
[+1 V v., (2 1 22. 33.5
) (xaj x
s.l. 1ij = ,1, Vjj 1,... ,N
(103)
3
od + bij. Fi.j + Σ ci
2 +
dout 2 Soout 1/
2=
1=1
(mig), (122s): : (*3.)) J: 21, 22, 23.
var.
Thus, as indicated by Eq. (103), the complexity of using the Frank- Wolfe based method is higher than that of the exterior penalty method, as it requires solving an additional constrained non-convex optimization problem in Eq. (103) at each iteration. Based on the aforementioned reasons, we chose use the exterior penalty method in this work.
In addition, we demonstrate the close relationship between the original constrained optimization problem (P1) in Eq. (8) and the unconstrained optimization problem (P2) in Eq. (15) in this work. That is, 1) the optimal solution to P2 is also feasible solution to the relaxed original problem P1; 2) the gap between the optimal objective value by utilizing the exterior penalty method ( (i... f 3 z3,y) ) in P2) and the optimal objective value in original problem Pl (i.c., (( (. )) will continuously decrease with penalty parameters increased. To enhance the readability of this discussion, the constrained optimization problem and unconstrained optimization problem are presented as follows.
Constrained eascaded polynomial approximation problem (P1):
N Σ
min
[1 02.1 F3..) 1=1
s.t. L1,j = 21, Vj = =1, 1,... N
(104)
a U 2 + bijj Fzz + Σ c,
out T
T gout 2iter Soout VI
27 +
var.
( ( ; {x3.) }. æ 22, 23.
Unconstrained optimizationn problem based exterior penalty method (P2):
N
min
= Σ (1 22 23.)) + وب -21112
(105)
+ + Au |max (max ((a2))) 22, =3) -out, 0}}²,
var.
{x1s). (x2.) fx3, /. 21, 22, #3.
3 N
1.1 23 + bb T
3 oon't x7 = t We first show that
where h11 }, (13. 2.,. 22, 23)
Σ>>
Σ c.1 1=1
1=
the optimal solution to P2 is also feasible solution to the relaxed original problem P1, and this relaxation will be gradually tightened with penalty parameters increased. Let (( J......... ( (. 1
=;) denote the optimal solution to P2 in Eq. (105). For any point ({*T,), ), { ). ( 27 =2 23 satisfies ap"((1z ). ( (0555) }. 27 22 2gg Eout, VZ
and æi = 0, Vj. since it is also the feasible solution to P2, we have that,
Σ (zi mi, 25,)) -,,,|o,,---1
+ Σ A Mmmxxfh (( (2 ) 2 23 23} - Eout, 0312
(106)
Σ (T 25) + | -
A (hppxx/ ((55,)) ( 2 z 23 ) Eout: 0)12.
39

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
According to Shen al. (2024), let C = 2 max Vigl can obtain that,
L - xill++ hf (( ( zi, 22, z3) Eout. 0]]²
N
$ Σ f1 L2 E
fig رراة (335)
(107)
j=1
s NC.
Because of | =ill 2 0 and (max(1g"1 ({ ( , z1, 2/21 (5) - Eout, 0}13 2 0, vi and according to Eq. (107), we can obtain that,
NC
و - -
Vj,
(108)
NC A
h0th (1 ( zi,
222
233)
oou S
1L.
(109)
According to Eq. (108) and Eq. (109), we can conclude that the optimal solution (f# h. b.(2 J 1. (55 to P2 is a feasible solution to the relaxed problem of the original constrained problem P1, that is,
N
Σ
fij (x 22.1 T3.1)
1=1
8.1.
| 211
NC Vj = 1,... N
(110)
h (( } (
. 25. 2z) S Eout + /
NC 1l Ae
var.
{ ). { |. { {I3.}]: 21 22, 23.
Let (( (Ta, and ((z1,) he L he respectively denote the optimal solutions to P1 and the relaxed problem of P1 (i.e., Eq. (110)), and let gap
B(10)) Σ (e
Σ
I. })-
(111)
It is seen from Eq. (110) that this relaxation will be tightened with penalty parameter oj. Ar Vj, Vi increased. Combining with Eq. (111), we can obtain that {({őý), (>+))= 2 0 will decrease when Oj. Ar, Vj. VT increase. Next, we will demonstrate the gap between the optimal objective value by utilizing the exterior penalty method ii.. Ii, (xt,;; +i,; #3,,) in P2)
and the optimal objective value in original problem P1 (i.e., N (( ( (33, })) will continuously decrease with dy Av, Vj, VI increased.
Because (f ( (. 11 is also the feasible solution to P2, and according to Σソ E.di[max (1gut ( (. ( 31, 22, Zz) Eout, 0}J² have that,
p -1112- = O.
Σ ( 22 23,1)
==
<
Σ
و zil
(n ( 27, 22, z5) Emut, 0}}²
(112)
< 0.
According to ((mi));(.)) ), ), 22,32 is feasible solution to problem in Eq. (110), obtain that,
N
Σ
fi ( ...g xb.1) 2
Σ
(113)
1=1
1=1
40

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymptotic Convergence
Table Comparisons between the proposed DTZO with the state-of-the-ar TLL methods (including Betty (Chne al., 2023), Hypergra- dient based method (Sato al.. 2021), and AFTO (Jiao et al., 2024)) based on the applicability to different TLL problems. v represents that the method can applied to this TLL problem. The proposed DTZO versatile and can be adapted to wide range of TLL problems. We use ZOC as abbreviation for zeroth order constraints.
Betty
Hypergradient
AFTO
DTZO
Non-distributed TLL without ZOC
Distributed TLL without ZOC
V
TLL with partial ZOC
TLL with level-wise ZOC
By combining Eq. (113) with Eq. (111), we can obtain that,
hhu((T (22.)
Σ (2 22.5 m3.))
N ( - Σ fl (1 (- , He t. )((
N
(114)
(10g))(\1))
By combining Eq. (114) with Eq. (112), we can obtain that,
N S
N
- -B(EO)
Σ
(
22
Σ He O.
(115)
==1
Based on Eq. (115) and B({o,}, (1+) 2 0, we can get that,
N
( x 23.)) - (Z,,
D (((e)), (a)).
(116)
By combining Eq. (116) with Eq. (110) and Eg. (111), we can conclude the gap between the optimal objective value by utilizing the exterior penalty method (i.e., Ey=ffi (zi.3: z2.j. æ3.)) P2) and the optimal objective value in original problem P1 (i.e., (f ), (xaa)))) is bounded and will decrease with penalty parameter Φj. ) Vj, VIl increased.
TLL with Partial Zeroth Order Constraints
In this work, TLL with level-wise zeroth order constraints is considered, where first order information at each level is unavailable. In addition, it is worth mentioning that the proposed framework is versatile and can be adapted to a wide range of TLL problems with partial zeroth order constraints, i.e., grey-box TLL, through slight adjustments. The reason we refer it as grey-box TLL is that the first order information for some levels in TLL is available, while for others not (Huang et al., 2024b; Beykal al., 2020; Astudillo Frazier, 2021: Bajaj et al., 2018). To further show the superiority of the proposed DTZO, compare it with the state-of-the-a art TLL methods (i.e., Betty (Choe al., 2023), Hypergradient based method (Sato et al., 2021), and AFTO (Jiao et al., 2024)) based on their applicability to TL.L problems in Table 6. In DTZO, the zeroth order cut takes center stage, driving the construction of cascaded polynomial approximations without the need for gradients or sub-gradients. Notably, zeroth order cut is not only the backbone of DTZO but also opens the door to tackling goxy-box TLL problems, seamlessly handling nested functions that combine both black-box and white-box elements. Discussions are provided as follows.

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
I.I. TLL with second and third-level zeroth order constraints
In this situation, the first order information the first-level in TLL problems is accessible. Thus, we can use the exact gradients to replace the zeroth order gradient estimator, i..., Eq. (16)-(19) can be replaced by,
++1 = zi.j - Tm, (Vai, Jis (a 25 )) + 20, (ai - z1))
(117)
2.
.++
22
Ta V æa, flr (2) 2. و3, l V va,, ol و 1 J 2/ z5),
(118)
++1 3.j z'sj
Ta V , fi,s ( 2 و3.5) - 1a V きs, of ( [ j J. 2 zz)).
(119)
By using the gradient descent steps in Eq. (119), the TLL problems with second and third-level zeroth order constraints can be effectively by the proposed framework.
1.2. TLL with first and third-level zeroth order constraints
In this situation, the first order information at the second-level in TLL problems is available. Thus, order information to generate outer layer cutting plane, e.g., f-cut (Jiao et al., 2024). By combining the outer layer first order cutting plane with the inner layer zeroth order cut, the proposed framework is capable of constructing the cascaded polynomial approximation. The generated outer layer p-cut can be expressed as.
the first
{ }
{
(23.5)
(
Voout V 1, 23, TT)TT
z1
(120)
23
z/
+oou ( hassssssss 2/. z5})
Eout +p (1 + (N l)(a2 + az) + + E || + Σi= ||=;1²²
In Eq. (120), p 0 is a parameter in p-weakly convex function, and 0; 2, is the boundness of variable Fijs Zi. as discussed in Jiao et al. (2024). By using the outer layer first order cutting plane, the TLL problems with first and third-level zeroth order constraints can be addressed by the proposed framework.
I.3. TLL with first and second-level zeroth order constraints
In this situation, the first order information at the third-level in TLL problems is accessible. Similarly, utilize the first order information to generate the inner layer cutting plane, e.g., p-cut. Through combining the inner layer first order cutting plane with the outer layer zeroth order cut, the proposed framework is capable of constructing the cascaded polynomial approximation. The generated inner layer p-cut can be expressed as,
{
{
21
21
+ Dral
22
2/
(121)
z3
z/
S Ein + P(N((N 1)a, a2 03
||
||
||=]|1]]
By using the inner layer first order cutting plane in Eq. (121), the TLL problems with second and third-level zeroth order constraints can be addressed by the proposed framework.
42

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymplotic Convergence
1.4. Trade-off between gradient-free and gradient-based methods
The proposed framework is highly adaptable, accommodating both fully gradient-unavailabe TLL and cases with partial gradient access with minimal modifications. We further discuss and compare the trade-off between gradient-free and gradient-based methods below.
1. Gradients at first-level are available. In this case, Eq. (16)-(19) can be replaced with gradient descent steps in DTZO, which introduce less noise per iteration and improve convergence rate (i.e., (()e)). However, Eq. (16)-(19) do not rely on gradients, making them more applicable to scenarios where gradients are unavailable. This represents trade-off between convergence efficiency and applicability, which can be flexibly adjusted within DTZO.
2. Gradients at second-level are available. In this case, the outer layer zeroth order cut can be replaced by first order cut. Since first order cut is generated based on gradients, introduces less noise in the generation process and can thus result in superior polynomial relaxation. In contrast, zeroth order cut exhibits broader applicability, as its generation does not depend on gradients. This represents a trade-off between outer layer polynomial relaxation and applicability, which can be effectively controlled within DTZO.
3. Gradients at third-level are available. Similar to 2), there exists a trade-off between inner layer polynomial relaxation and upplicability, We can flexibly control this trade-off by exchanging the inner layer zeroth order and first order cuts.
J. Discussions about Cutting Plane Method and Gradient Estimator
J.1. Cutting Plane Method
Cutting plane method, also called polyhedral approximation (Bertsekas, 2015), is widely used in convex optimization (Frane et al., 2011; Boyd & Vandenberghe, 2007) and distributed optimization (Bürger et al., 2013; Yang et al., 2014). The rationale behind cutting plane method is to use the intersection of finite number of half-spaces (e.g., P {==|af x S 6,, ---=1 1,... .L. where {zraae- x I br} represent half-space (Boyd & Vandenberghe, 2004)) to approximate the feasible region of the original optimization problem (e.g.. E X) The approximation can be gradually refined by generating additional half-spaces (Bertsekas. 2015). Recently, cutting plane methods have proven effective in tackling distributed nested optimization problems. By leveraging these methods, such problems can be transformed into decomosabbl optimization problems, which greatly simplifies the design of distributed algorithms for nested optimization, as discussed in (Jiao et al., 2023; 2024). In (Jiao et al., 2023), cutting plane methods are applied to solve bilevel optimization problems within distributed framework. Likewise, (Chen et al., 2024d) utilize the cutting plane method to tackle distributed bilevel optimization challenges in downlink multi-cell systems. Building on this, (Jiao et al., 2024) further extend the approach to address distributed trilevel optimization problems. However, existing cutting plane methods for nested optimization rely on the first-order information to generate cutting planes, which are not available in zeroth-order optimization.
In this work, we propose a framework capable of generating zeroth order cuts for nested optimization problems without the use of first order information. We theoretically demonstrate that the proposed zeroth order cuts are capable of constructing the cascaded polynomial relaxation without relying on first order information, and this relaxation will be gradually tightened as additional cuts are introduced. Additionally, it worth mentioning that the proposed zeroth order cuts do not require the convexity of the function and are also the first non-linear cuts in nested optimization. Compared to linear cutting planes, nonlinear cuts usually offer better approximation capabilities for complex functions (Temlyakov, 2003), providing new insights for the further development of cutting plane methods in nested optimization. Please note that simply combining the existing algorithms can not achieve this goal. To further highlight the novelty of the proposed zeroth order cut, we compare it with existing cutting plane methods used in nested optimization in Table 7.
J.2. The Choice of Gradient Estimator
is worth noting that the proposed framework is versatile, allowing for the integration of various gradient estimators. For instance, the mini-batch sampling-based gradient estimator (Liu et al., 2020; Duchi et al., 2015) can be employed to replace the two-point gradient estimator, reducing variance. Specifically, with mini-batch sampling, Eq. (10), (12) (19), (20), and
43

---

DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asympiotic Convergence
Table Comparison of the existing cutting plane methods in nested optimization.
Cutting Plane Method
Convex
Non-convex
Non-linear
Gradient Free
(Jiao et al., 2023)
(Chen et al., 2024d)
(Jian et al., 2024)
(Jiao et al., 2024)
The Proposed Zeroth Order Cut
(21) can be replaced by the following multi-point gradient estimators.
G (1a ), 21. 11.22212 ,²²,
(122)
= - Σ Pin (( + pape J: 2 + u 2/'2 +upe, (4p din(tal,gh 21, ztz = =5)pem..)
) ). z/2 z/z)
=
Pont (ar mul : farg + mul } p uul,, 2/3 1pp2))
(123)
"
Doutt (1 ( J. #1 2/2 z5. pott,p
Gan, (fzig) 122 ( z1, z z31))
(124)
= Eafis + pal 2h. w3.s) f (zi 2 aby) ( - z1),
(taf } ( (
2/. 2/// Van, o(
(125)
+ Σ 1
وb. pul 21 و33 flr ( 2b. و3. )2h
Ges,((arf ( }. (2
21. 22, 2/}) V aas, V (2
2 2/3)
(126)
Σ p=1
[fi (xi, 2bz5 وbyة + (u? f1, ( 2b. x Juf
where in K 2a. 1h, u 1 drawn from (0 I), and b represents the number of samples used in the multi- point gradient estimator.
4 u
Hue J. {ue }. ue, ue u ui uh uh
1,... are
K. Future Work
This study is the first work that considers how address the trilevel zeroth order optimization problems. The proposed framework not only capable of addressing the single-level and bilevel zeroth order learning problems but can also be applied broad class of TLL problems, e.g., TLL with partial zeroth order constraints. However, higher-level nested learning problems, specifically those with more than three levels, are not considered in this work and will be addressed in future research.
44


Reviews:
[{"review_id": "jm35AsTgjb", "reviewer": "Reviewer_1qiE", "summary": "This paper introduces DTZO, a framework for solving trilevel learning problems where gradient information is unavailable at all levels like black-box or with partial zeroth order constraints with analysis of the convergence rate and communication complexity.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We truly appreciate your insightful and valuable suggestions. We have provided a detailed response addressing each of the questions you raised.**\n\n**(Q1)** Experiments on another domain and ablation study.\n\n**(R1)** This work is the **first** to investigate solving the distributed TLL problem without relying on first-order (FO) information while providing **theoretical guarantees**. The proposed DTZO exhibits **high adaptability** which can be applied to a broader range of TLL problems, please refer to (R5) for details. To address your concerns, we have incorporated additional experimental results on another domain, i.e., continual learning, along with ablation study, as detailed below.\n\n- **Continual Learning**. In the experiment, the adversarial architecture-based continual learning task is considered, which can be formulated as a TLL problem.\n\\begin{align}\n\\min&{\\sum_j\\sum_{(x,y)\\in D_j ^B}\\frac{{L([\\theta_1,\\theta_2],x,y)}}{|D_j^B|}}\\\\\\\\\ns.t.&\\theta_1=\\mathop{\\arg \\min}\\limits_{\\theta_1'}\\sum_j\\sum_{(x,y)\\in D_j^A}\\frac{L(\\theta_1',x,y, P_1)}{|D_j^A|}\\\\\\\\\n&s.t.P_1=\\mathop{\\arg \\max}\\limits_{P_1'} \\sum_j \\sum_{(x,y) \\in D_j^A}\\frac{L(\\theta _1',x,y,P_1')}{|D_j^A|}\n\\end{align}\nThe results are reported in Table 1.1. It is seen that the proposed DTZO outperforms SOTA methods because: 1) DTZO is capable of solving higher-nested zeroth order (ZO) problems; 2) the proposed nonlinear ZO cut has superior approximation performance.\n\n- **Ablation study**. Due to character limitations, please refer to (R3) to Reviewer LX43.\n\nTable 1.1\n|Method|MNIST|USPS|\n|-|-|-|\n|FedZOO|0.6103|0.6652|\n|FedRZObl|0.6967|0.7254|\n|FEDNEST|0.7014|0.7279|\n|ADBO|0.6942|0.7316|\n|AFTO|0.9275|0.9423|\n|**DTZO**|**0.9536**|**0.9654**|\n\n**(Q2)** Additional datasets and baseline methods. \n\n**(R2)**  Due to character limitations, please see (R1) to Reviewer urFe. \n\n**(Q3)** Explanation to $T_1$.\n\n**(R3)** In the proposed framework, $T_1<\\infty$ is a constant that can be flexibly adjusted based on specific requirements. Specifically, if the distributed system has sufficient computational and communication resources, a relatively larger $T_1$ (but still **finite**) can be chosen to achieve a better cascaded polynomial relaxation. Conversely, if the resources are limited, a smaller $T_1$ can be set to reduce the iteration and communication complexity.\n\n**(Q4)** No discussion of computational limitations. Dataset and benchmark size is limited.\n\n**(R4)** Solving TLL is highly challenging, as even $\\textit{finding a feasible solution}$ for a linear TLL is **NP-hard**. The proposed DTZO is a **distributed optimization** method, making it well-suited for large-scale learning tasks due to the scalability of distributed algorithms. It decomposes large tasks into subproblems assigned to individual workers, enabling efficient problem-solving. Moreover, even in scenarios with limited computational resources, DTZO can effectively handle them due to its flexibility. By setting a smaller $T_1$, the communication and iteration complexities are reduced. Experimental results on more datasets and larger models are reported in (R2) to Reviewer LX43 and (R1) to Reviewer urFe.\n\n**(Q5)** Trade-off between gradient-free vs. gradient-based method.\n\n**(R5)** The proposed framework is highly adaptable, accommodating both fully gradient-unavailable TLL and cases with partial gradient access with minimal modifications. We further discuss and compare the trade-off below.\n\n1) **Gradients at 1-level are available.** In this case, Eq. (16–18) can be replaced with gradient descent steps in DTZO, which introduce less noise per iteration and improve convergence rate ($O(1/\\epsilon)$). However, Eq. (16–18) do not rely on gradients, making them more applicable to scenarios where gradients are unavailable. This represents a trade-off between convergence efficiency and applicability, which can be flexibly adjusted within DTZO.\n\n2) **Gradients at 2-level are available.** In this case, the outer layer ZO cut can be replaced by FO cut:\n$\\nabla\\phi_{out}{(\\\\{{x_{2,j}^t}\\\\},\\\\{{x_{3,j}^t}\\\\},\\\\{z_i^t\\\\})^{\\top}}[\\\\{x_{2,j}-x_{2,j}^t\\\\};\\\\{x_{3,j}-x_{3,j}^t\\\\};\\\\{z_i-z_i^t\\\\}]+\\phi_{out}(\\\\{{x_{2,j}^t}\\\\},\\\\{{x_{3,j}^t}\\\\},\\\\{z_i^t\\\\})\\le L/2(\\sum_{i=2}^3\\sum_j||x_{i,j}-x_{i,j}^t||^2+\\sum_i||z_i-z_i^t||^2)+\\varepsilon_{out}$. \nSince FO cut is generated based on gradients, it introduces less noise in generation process and can get a superior polynomial relaxation. In contrast, ZO cut exhibits broader applicability, as its generation does not rely on gradients. This represents a trade-off between polynomial relaxation and applicability, which can be effectively controlled in DTZO.\n\n3) **Gradients at 3-level are available.** Similar to 2), there exists a trade-off between inner layer polynomial relaxation and applicability. \n\n**(Q6)** Some ZO references are missing.\n\n**(R6)** More discussion on ZO will be added as Appendix J.3. We are happy to include any references the reviewer may suggest.", "claims_and_evidence": "The paper provides an extensive related work section discussing bilevel and single-level zeroth order methods with DZTO to address trilevel zeroth order learning problems.\n\nDTZO achieves up to a 40% improvement in performance over state-of-the-art methods from empirical results.\n\nThe authors also provide a non-asymptotic convergence guarantee.\n\nWhile the framework is theoretically flexible, no experiments explore its adaptability across diverse domains beyond LLM prompt learning and hyperparameter optimization or ablation study to explore the contribution of different optimization structures.", "methods_and_evaluation_criteria": "The benchmarking tasks (LLMs and hyperparameter optimization) are relevant applications for zeroth order learning.\n\n\nPerformance metrics such as accuracy, robustness, convergence speed, and computational efficiency are reasonable.\n\nHowever the datasets selection is limited to small or simple ones (which might also not be suitalbe for LLM benchmarking). Also other bilevel methods or other black-box optimization techniques should be tested as references given the motivation here.", "theoretical_claims": "The theoretical contribution looks correct to me at initial examination", "experimental_designs_or_analyses": "The stationarity gap and $\\epsilon$-stationary point definition are well-established in optimization. The use of penalty-based relaxation aligns with existing literature.\n\nHowever $T_1$ is not bounded, more explanation to this is desired here.", "relation_to_broader_scientific_literature": "The paper builds on existing work in bilevel optimization and extends it to trilevel settings with broader connection to black-box optimization, federated learning, and hierarchical machine learning.", "essential_references_not_discussed": "Some other zeroth order optimization methods are missing.", "other_strengths_and_weaknesses": "## Pros:\nThis paper is well-written and with theoretical contribution with well-structured proofs.\n\n## Cons:\nNo discussion of computational limitations.\nDataset and benchmark size is limited.", "other_comments_or_suggestions": "A comparison with gradient based or partial gradient based methods would help quantify the trade-off between gradient-free vs. gradient-based approaches in cases where some gradient information is available.", "questions_for_authors": "It seems the authors only talked about trade-off between performance and complexity, but not the additional computational trade-off compared to other methods?\nAlso see previous sections.", "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": "zskYAZp2Hn", "reviewer": "Reviewer_LX43", "summary": "This paper proposes a zeroth-order constrainted trilevel learning optimizer which is versatile and can be adapted to a wide range of TLL problems. The authors provide both convergence analysis and experiment validation for the proposed DTZO framework. The improvement in performance from the experiments is very significant.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We sincerely appreciate your insightful and valuable suggestions. We have provided a detailed point-by-point response to your questions below.**\n\n**(Q1)**  A table that compares the latest progress with the related analysis.\n\n**(R1)** This work is the **first** to explore solving the distributed TLL without relying on first-order information while providing **theoretical guarantees**. Per your suggestion, we have included a table comparing the non-asymptotic convergence results of the proposed DTZO with SOTA distributed nested optimization methods, under the assumption/setting where first-order information is either available (FO) or unavailable (ZO). Please note that ZO is more general and challenging than FO.\n\nTable 2.1\n|Methods|Bilevel (FO)|Bilevel (ZO)|Trilevel (FO)|Trilevel (ZO)|\n|-|-|-|-|-|\n|FEDNEST|$\\mathcal{O}(1/\\epsilon^2)$|-| -| -|\n|ADBO|$\\mathcal{O}(1/\\epsilon^2)$|-|-|-|\n|MDBO|$\\mathcal{O}(1/\\epsilon^2)$|-|-| -|\n|FedBiOAcc| $\\mathcal{O}(1/\\epsilon^{1.5})$|-|-|-|\n|FedRZObl|-| $\\mathcal{O}(1/\\epsilon^2)$|-|-|\n|AFTO|-|-|$\\mathcal{O}(1/\\epsilon^2)$|-|\n|**DTZO**|-|-|-|$\\mathcal{O}(1/\\epsilon^2)$|\n\n**(Q2)** More models and datasets, i.e. LLAMA-7B.\n\n**(R2)** Additional experiments are conducted on (1) more datasets and models in robust hyperparameter optimization, and (2) larger LLMs in black-box TLL. Specifically,\n\n(1) Due to character limitations, please refer to (R1) to Reviewer urFe.\n\n(2) Experiments are conducted using larger LLMs, i.e., Qwen-2-7B and LLAMA-3.1-8B, and the results are shown in Table 2.2.\n\nTable 2.2\n|Methods|SST-2(ASR)|SST-2(ACC)|COLA(ASR)|COLA(ACC)|MRPC(ASR)|MRPC(ACC)|\n|-|-|-|-|-|-|-|\n|FedRZObl (Qwen)|0.9147|0.6253|0.8774|0.7094|0.9384|0.7142|\n|DTZO (Qwen)|0.9647|0.7053|0.9545|0.7653|0.9571|0.7492|\n|FedRZObl (LLAMA)|0.9854|0.8591|0.8623|0.6556|0.9710|0.7454|\n|DTZO (LLAMA)|1.0|0.8968|0.9065|0.6891|0.9910|0.7866|\n\n**(Q3)** Ablation experiments.\n\n**(R3)**  **Ablation Study**. To analyze DTZO’s performance improvements, we conduct an ablation study comparing DTZO against its variants: DTZO(-) and DBZO. DTZO(-) replaces the proposed nonlinear cuts in DTZO with linear cuts, while DBZO removes cascaded polynomial approximation, using only single-layer polynomial approximation. It is seen from Table 2.2 that DTZO outperforms all variants, demonstrating the benefits of cascaded polynomial approximation and nonlinear ZO cuts. In addition, we also compare DTZO with a variant of DTZO without removing inactive cuts. It is seen from Figure 3 in page 33 that removing inactive cuts greatly enhances DTZO’s efficiency, underscoring the importance of this step.\n\nTable 2.3\n|Methods|F-MNIST|USPS| UWaveGestureLibraryAll| MelbournePedestrian|\n|-|-|-|-|-|\n|DBZO|0.5343|0.7492|0.7143|0.6536|\n|DTZO(-)|0.6685|0.8212|0.7921|0.7013|\n|DTZO|**0.7007**|**0.8513**|**0.8243**|**0.7250**|\n\n**(Q4)** Core theoretical contribution.\n\n**(R4)** Existing works focus on single-level and bilevel ZO, while tackling the trilevel ZO is under-explored and significantly more challenging (even finding a feasible solution in TLL is **NP-hard**). This work marks an **initial step** in solving TLL without first-order information. A key theoretical contribution is the **first trilevel ZO framework** and **first non-asymptotic convergence guarantee** (e.g., iteration and communication complexity) for trilevel ZO, aligning with DTZO’s superior performance in experiments, i.e., DTZO outperforms SOTA methods by handling higher-nested ZO with theoretical guarantees. Another key theoretical contribution is the construction of the **first theoretically guaranteed ZO cuts** in nested optimization, enabling cascaded polynomial relaxation without gradients. The proposed ZO cut is also the **first nonlinear** cut in nested optimization, offering better approximations for complex functions than linear cut. This advancement can also be observed in ablation study, where DTZO outperforms its variant without ZO cuts.\n\n**(Q5)** More detailed records (communication bits, training time).\n\n**(R5)** Compared to single-level and bilevel optimization, solving TLL inherently demands higher complexity. This is because 1) TLL has higher-nested structure, finding a feasible solution in TLL requires solving a bilevel optimization problem; 2) it involves more optimization variables than bilevel and single-level optimization. Per your suggestions, we provide a comparison of communication complexity and training time between DTZO and SOTA distributed TLL method. As shown in Table 2.4, DTZO achieves superior performance due to its non-asymptotic convergence guarantees and simplified optimization procedure.\n\nTable 2.4\n|Methods|Communication complexity/bits|Crop (training time/s)|UWaveGestureLibraryAll (training time/s)|\n|-|-|-|-|\n|AFTO+ZO|NA$^1$|652.3|375.2|\n|DTZO|$32T(\\epsilon)(2d_1+3d_2+3d_3)N+64 N \\lfloor \\frac{T_1}{\\mathcal{T}} \\rfloor \\mathcal{T}(d_2+d_3)$|485.5|244.6|\n\n$^1$Because this method lacks non-asymptotic convergence guarantee.", "claims_and_evidence": "The structure of the article is generally complete, and the viewpoints are reasonable.", "methods_and_evaluation_criteria": "The experiments look excellent. I have listed a few questions regarding the experiments in the questions, and I hope the authors can provide detailed answers.", "theoretical_claims": "The paper analyzes the convergence of the DTZO framework, but the introduction is not detailed enough. It would be beneficial for the authors to provide a table that compares the latest progress with the related analysis, presenting the detailed assumptions and conclusions to highlight the advantages of the current analysis. The current version does not make this clear enough.", "experimental_designs_or_analyses": "The results demonstrated by the experiments are impressive, but the data sample size is insufficient. The authors should expand the testing to include more models and datasets.", "relation_to_broader_scientific_literature": "It is also beneficial for other ZO methods.", "essential_references_not_discussed": "Enough discussions.", "other_strengths_and_weaknesses": "see above (each block)", "other_comments_or_suggestions": "see above (each block)", "questions_for_authors": "1. The performance of the proposed DTZO method in the experiments is significantly better than the baselines, which is excellent. However, I remain unclear about the source of this improvement. Could the authors design ablation experiments to verify the source of this performance boost? For example, they could identify which techniques were added during the transition from the baseline to the DTZO method and validate the importance of each technique individually.\n\n2. What is the core theoretical contribution of this paper compared to existing work? Does this result represent a theoretical improvement, or can the outstanding performance of the DTZO algorithm be reflected through theoretical analysis?\n\n3. Can the experiments be conducted on larger models, such as foundational models like LLAMA-7B? How do their results perform?\n\n4. Could the authors provide more detailed experimental records? For example, the communication bits for each method, the actual training time (in seconds), and other related details. This would help me better understand the performance of the DTZO method.", "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": "9EHOhKjYkB", "reviewer": "Reviewer_urFe", "summary": "The paper introduces DTZO (Distributed Trilevel Zeroth Order Learning), a novel framework for solving distributed trilevel learning problems with missing gradient information. This is achieved by constructing a cascaded polynomial approximation without relying on gradients or sub-gradients, leveraging zeroth-order cuts of inner and outer layers and dropping inactive zeroth-order cuts. The author also theoretically carries out the non-asymptotic convergence rate analysis for the proposed framework. Finally, the paper demonstrates the effectiveness through experiments on black-Box trilevel learning and robust hyperparameter optimization.\n\n## update after rebuttal\n\nThank authors for the comprehensive rebuttal. The added experiment results help enhance the findings of the paper and addressed my concerns. I have changed the scores accordingly.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We truly appreciate your insightful suggestions. We have provided a point-by-point reply to all your questions and hope we have successfully addressed all your concerns.**\n\n**(Q1)** In general the experimental designs and analysis are sound, which is partially discussed in Methods And Evaluation Criteria section. But dataset choice in hyper-parameter optimization lacks diversity since they are largely MNIST-related. And the treatment methods are limited, the paper only compares with 2 methods, FedZOO and FedRZO.\n\n**(R1)** Thanks for your helpful suggestions. Addressing the trilevel zeroth order optimization problem in a distributed manner is significantly challenging, as even $\\textit{finding a feasible solution}$ in a linear trilevel optimization problem is **NP-hard**. This is the **first work** to explore solving trilevel zeroth-order optimization problems in a distributed manner while providing **theoretical guarantees**. We have conducted experiments on several more complex datasets, including CIFAR-10 and CIFAR-100 (using CNN models), as well as time series datasets such as MelbournePedestrian, Crop, and UWaveGestureLibraryAll from the UCR Archive [1], as suggested. Additionally, we have incorporated more state-of-the-art distributed single-level, bilevel, and trilevel optimization methods with zeroth-order estimators [2], including FedAvg+ZO [3], FEDNEST+ZO [4], ADBO+ZO [5], and AFTO+ZO [6], as baseline methods. The experimental results are presented in Table 3.1 below. Please note that combining distributed nested optimization methods with zeroth order estimators does not provide any theoretical guarantees; these methods are included only for comparative evaluation. As shown in Table 3.1, the proposed DTZO exhibits superior performance. This can be attributed to two key factors: (1) Compared to existing methods, the proposed DTZO is capable of effectively addressing higher-nested zeroth order optimization problems with non-asymptotic convergence guarantees. (2) The proposed nonlinear zeroth order cuts facilitate the development of a more refined cascaded polynomial relaxation.\n\nTable 3.1 Experimental results on robust hyperparameter optimization.\n\n| Datasets               | FedAvg+ZO | FedZOO | FEDNEST+ZO | ADBO+ZO | FedRZObl | AFTO+ZO | DTZO        |\n| ---------------------- | --------- | ------ | ---------- | ------- | -------- | ------- | ----------- |\n| MNIST                  | 0.5196    | 0.5289 | 0.5503     | 0.5341  | 0.5405   | 0.7501  | **0.7927**  |\n| QMNIST                 | 0.5204    | 0.5245 | 0.5398     | 0.5487  | 0.5467   | 0.7389  | **0.7804**  |\n| F-MNIST                | 0.4786    | 0.4874 | 0.5065     | 0.5102  | 0.5023   | 0.6448  | **0.7007** |\n| USPS                   | 0.7211    | 0.7277 | 0.7354     | 0.7323  | 0.7379   | 0.7987  | **0.8513**  |\n| CIFAR-10               | 0.3731    | 0.3829 | 0.4034     | 0.3987  | 0.4079   | 0.4692  | **0.5147**  |\n| CIFAR-100               | 0.1967    | 0.2102 | 0.2243     | 0.2354  | 0.2321   | 0.2774  | **0.3023**  |\n| MelbournePedestrian    | 0.6214    | 0.6295 | 0.6454     | 0.6412  | 0.6487   | 0.6924  | **0.7250**  |\n| Crop                   | 0.5379    | 0.5468 | 0.5607     | 0.5681  | 0.5645   | 0.6016  | **0.6351**  |\n| UWaveGestureLibraryAll | 0.6652    | 0.6714 | 0.6924     | 0.6983  | 0.7002   | 0.7689  | **0.8243**  |\n\n\n\n\nFurthermore, we have conducted additional experiments to evaluate the proposed DTZO in three aspects: \n\n- 1) Experimental results on another domain, i.e., continual learning, please see the results in (R1) to Reviewer 1qiE.\n- 2) Ablation experiments,  please refer to (R3) to Reviewer LX43 for details.\n- 3) Experimental results when using larger LLMs, i.e., Qwen-2-7B and Llama-3.1-8B, please see (R2) to Reviewer LX43 for results.\n\n\n\n**(Q2)** The paper has good novelty and solid theoretical foundations. But experimental study is limited as mentioned above. In general, it should be above borderline acceptance.\n\n**(R2)** We appreciate your comments and support. Please refer to our modifications regarding the experimental study in (R1). We hope that our revisions have adequately addressed your concerns.\n\n\n\n**(Q3)** In Assumption 4.4. there is a typo that word \"Following\" is mis-included in the cite hyperlink.\n\n**(R3)** We sincerely appreciate your careful review and thank you for pointing it out. We have corrected it as suggested.\n\n**Reference**\n\n[1] The UCR Time Series Classification Archive, 2018\n\n[2] A primer on zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications\n\n[3] Communication-efficient learning of deep networks from decentralized data\n\n[4] FEDNEST: Federated bilevel, minimax, and compositional optimization, ICML 2022\n\n[5] Asynchronous Distributed Bilevel Optimization, ICLR 2023\n\n[6] Provably Convergent Federated Trilevel Learning, AAAI 2024", "claims_and_evidence": "Yes, the claims in the submission are supported by clear and convincing evidence. Specifically, the authors prove theoretical analysis of their polynomial approximation and zeroth-cuts methods, provide the distributed algorithm on zeroth order and provide experiment results to validate the performance of the proposed algorithm.", "methods_and_evaluation_criteria": "Yes, authors compared their methods with FedRZO on  Black-Box Trilevel Learning in LLMs. They used Qwen 1.8B-Chat as black-box LLM and GLUE benchmark for evaluation, compared the ASR and ACC performance of the 2 algorithms. The paper also compared their methods with FedZOO and FedRZO on hyper-parameter optimization. They leveraged a ReLU neural network and benchmarked on datasets including MNIST, QMNIST, F-MNIST, USPS, demonstrating the effectiveness of the algorithm.", "theoretical_claims": "Yes, the paper provides rigorous theoretical analysis for the proposed methods.  It made claims of the stationarity, boundedness, smoothness and complexity of the method and provided details in the appendix.", "experimental_designs_or_analyses": "In general the experimental designs and analysis are sound, which is partially discussed in Methods And Evaluation Criteria section. But dataset choice in hyper-parameter optimization lacks diversity since they are largely MNIST-related. And the treatment methods are limited, the paper only compares with 2 methods, FedZOO and FedRZO.", "relation_to_broader_scientific_literature": "The paper is related to broader scientific literature like distributed trilevel learning, distributed zeroth-order optimization and cutting-plane methods for bilevel/trilevel optimization.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper has good novelty and solid theoretical foundations. But experimental study is limited as mentioned above. In general, it should be above borderline acceptance.", "other_comments_or_suggestions": "In Assumption 4.4. there is a typo that word \"Following\" is mis-included in the cite hyperlink.", "questions_for_authors": "N/A", "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:

Meta-review: This paper introduces DTZO, a framework for solving trilevel optimization problems where some parameters are themselves optimal solutions for lower level optimization problems. This is achieved by constructing a cascaded polynomial approximation without relying on gradients or sub-gradients, leveraging zeroth-order cuts of inner and outer layers and dropping inactive zeroth-order cuts. The reviewers found the theoretical part of the paper to be clear, and in experiments the paper significantly improves the performance of existing solutions.
Decision: Accept (poster)