Asynchronous Distributed Bilevel Optimization
Authors: Yang Jiao
Kai Yang
Tiancheng Wu
Dongjin Song
Chengtao Jian
Venue: ICLR 2023 poster (2023)

Abstract: Bilevel optimization plays an essential role in many machine learning tasks, ranging from hyperparameter optimization to meta-learning. Existing studies on bilevel optimization, however, focus on either centralized or synchronous distributed setting. The centralized bilevel optimization approaches require collecting massive amount of data to a single server, which inevitably incur significant communication expenses and may give rise to data privacy risks. Synchronous distributed bilevel optimization algorithms, on the other hand, often face the straggler problem and will immediately stop working if a few workers fail to respond. As a remedy, we propose Asynchronous Distributed Bilevel Optimization (ADBO) algorithm. The proposed ADBO can tackle bilevel optimization problems with both nonconvex upper-level and lower-level objective functions, and its convergence is theoretically guaranteed. Furthermore, it is revealed through theoretic analysis that the iteration complexity of ADBO to obtain the $\epsilon$-stationary point is upper bounded by $\mathcal{O}(\frac{1}{{{\epsilon ^2}}})$. Thorough empirical studies on public datasets have been conducted to elucidate the effectiveness and efficiency of the proposed ADBO.

Published as a conference paper at ICLR 2023
ASYNCHRONOUS DISTRIBUTED BILEVEL OPTIMIZA- TION
Yang Jiao Tongji University
Kai Yang" Tongji University
Tiancheng Wu Tongji University
Dongjin Song University of Connecticut
Chengtao Jian Tongji University
ABSTRACT
Bilevel optimization plays an essential role in many machine learning tasks, rang- ing from hyperparameter optimization to meta-learning Existing studies on bilevel optimization, however, focus on either centralized or synchronous dis- tributed setting. The centralized bilevel optimization approaches require collect- ing a massive amount of data to single server, which inevitably incur significant communication expenses and may give rise to data privacy risks. Synchronous dis- tributed bilevel optimization algorithms, on the other hand, often face the straggler problem and will immediately stop working if few workers fail to respond. As a remedy, we propose Asynchronous Distributed Bilevel Optimization (ADBO) al- gorithm. The proposed ADBO can tackle bilevel optimization problems with both nonconvex upper-level and lower-level objective functions, and its convergence is theoretically guaranteed. Furthermore, it is revealed through theoretical analysis that the iteration complexity of ADBO to obtain the e-stationary point is upper bounded by ( ). Thorough empirical studies on public datasets have been con- ducted to elucidate the effecttiveness and efficiency of the proposed ADBO.
INTRODUCTION
Recently, bilevel optimization has emerged due its popularity in various machine learning ap- plications, e.g., hyperparameter optimization (Khanduri et al. 2021 Liu et al. (021a), meta- learning (Likhosherstov et [222 Ji al. 2020). reinforcement learning (Hong et al. 2020 Zhou & Liu 2022), and neural architecture search (Jiang et al. 2020: Jiao et al. 2022b). In bilevel opti mization, one optimization problem is embedded or nested with another. Specifically, the outer opti- mization problem is called the upper-level optimization problem and the inner optimization problem called the lower-level optimization problem. A general form of the bilevel optimization problem can be written as,
min F(x, y) s.t. y = arg min f(x y') v'
x. y.
where F' and f denote the upper-level and lower-level objective functions, respectively. æ R and 1mth are variables. Bilevel optimization can be treated as a special case of constrained optimization since the lower-level optimization problem can be viewed as a constraint the upper- level optimization problem (Sinha et al. 2017).
The proliferation of smartphones and Internet Things (IoT) devices has generated plethora of data in various real-world applications. Centralized bilevel optimization approaches require collect- ing a massive amount of data from distributed edge devices and passing them a centralized server for model training. These methods, however, may give rise to data privacy risks (Subramanya & Riggio 202I) and encounter communication bottlenecks (Subramanya & Riggio 2021). To tackle these challenges, recently, distributed algorithms have been developed to solve the decentralized
"Corresponding author.

---

Published as a conference paper at ICLR 2023
bilevel optimization problems Yang al. 2022 Chen et al. 2022b Lu et al. 2022 Tarzanagh
jet al. (2022) and et al. (2022) study the bilevel optimization problems under federated setting. Specifically, the distributed bilevel optimization problem can be given by
min F(x,y) y)
Σ G.
s.t. y arg min fax y²) Σ (
3/'
var. 2, y, where N is the number of workers (devices), G; and gi denote the local upper-level and lower-level objective functions, respectively. Although existing approaches have shown their success in resolv- ing distributed bilevel optimization problems, they only focus on the synchronous distributed setting. Synchronous distributed methods may encounter the straggler problem (Jiang et al. 202I) and its speed is limited by the worker with maximum delay (Chang al. 2016). Moreover, synchronous distributed method will immediately stop working if a few workers fail to respond (Zhang & Kwok) 2014) (which common large-scale distributed systems). The aforementioned issues give rise to the following question:
Can we design an asynchronous distributed algorithm for bilevel optimization?
To this end, we develop an Asynchronous Distributed Bilevel Optimization (ADBO) algorithm which single-loop algorithm and computationally efficient. The proposed ADBO regards the lower-level optimization problem as a constraint to the upper-level optimization problem, and uti- lizes cutting planes to approximate this constraint. Then, the approximate problem solved in an asynchronous distributed manner by the proposed ADBO. We prove that even if both the upper- level and lower-level objectives are nonconvex, the proposed ADBO is guaranteed to converge. The iteration complexity of ADBO is also theoretically derived. To facilitate the comparison, we not only present a centralized bilevel optimization algorithm Appendix A but also compare the con- vergence results of ADBO to dfate-of-theaat art bilevel optimization algorithms with both centralized and distributed settings in Table I
Contributions. Our contributions can be summarized as:
1. We propose a novel algorithm, ADBO, to solve the bilevel optimization problem an asyn- chronous distributed manner. ADBO is single-loop algorithm and is computationally efficient. To the best of our knowledge, is the first work in tackling asynchronous distributed bilevel opti- mization problem.
2. We demonstrate that the proposed ADBO can be applied to bilevel optimization with nonconver upper-level and lower-level objectives with constraints. We also theoretically derive that the iteration complexity for the proposed ADBO to obtain the e-stationary point is upper bounded by (
Our thorough empirical studies justify the superiority of the proposed ADBO over the existing state-of-the-art methods.
RELATED WORK
The bilevel optimization problem was firstly introduced by Bracken & McGill (173).. In recent years, many approaches have been developed to solve this problem and they can be divided into three categories (Gould et al.) 2016). The first type of approaches assume there an analytical solution the lower-level optimization problem (i.e., o(x) arg miny f(x, y')) (Zhng et al. 2021). ). In this case, the bilevel optimization problem can be simplified to a single-level optimization problem (i.e,, ming F (æx ((x)). Nevertheless, finding the analytical solution for the lower-level optimization problem is often very difficult, if not impossible. The second type of ap- proaches replace the lower-level optimization problem with the sufficient conditions for optimality (e.g., KKT conditions) (Biswas & Hoyle 2019 Sinha et al. (017). Then, the bilevel program can be reformulated lem could be hard to solve since it often involves large number of constraints (Ji et al., 2021 Gould al. 2016). The third type of approaches are gradient-based methods (Ghadimi & Wang 2018| et al. 2020; Liao et al. 2018) that compute the hypergradient (or the estimation of hy- OF
Bilevel optimization:
single-level constrained optimization problem. However, the resulting prob-
pergradient), i.e., (F.
dy and use gradient descent to solve the bilevel optimization Dm
6y
2

---

Published as a conference paper at ICLR 2023
problems. Most of the existing bilevel optimziation methods focus centralized settings and re- quire collecting a massive amount of data from distributed edge devices (workers). This may give rise to data privacy risks (Subramanya & Riggio 202T and encounter communication bottlenecks (Subramanya & Riggio
2021).
Asynchronous distributed optimization: To alleviate the aforementioned issues in the centralized setting, various distributed optimization methods can be employed. Distributed optimization meth- ods can be generally divided into synchronous distributed methods and asynchronous distributed methods (Assran et al. 2020). For synchronous distributed methods (Boyd et al. 201T), the master needs to wait for the updates from all workers before it proceeds to the next iteration. Therefore, may suffer from the straggler problem and the speed is limited by the worker with maximum delay (Chang et al.) 2016). There are several advanced techniques have been proposed to make the syn- chronous algorithm more efficient, such as large batch size, warmup and so on (Goyal et al. 2017, You et al. 2019, Huo et al.
2021 Liu & Mozafari 2022 Wang et al. 2020). For asynchronous
distributed methods (Chen et al. 2020 Matamoros 2017), the master can update its variables once it receives updates from workers, L.c., active workers (1 S S N, where N is the number of all workers). The asynchronous distributed algorithm is strongly preferred for large scale distributed systems in practice since it does not suffer from the straggler problem (Jiang et al.) (021). Asyn- chronous distributed methods (Wu al., 2017: Liu al., (017) have been employed for many real-world applications, such as Google's DistBelief system (Dean et al.) 2012), the training of 10 million YouTube videos (Le 2013), federated learning for edge computing (Lu et al.) 2019 Liu
et al. 2021c). Since the action orders of each worker are different in the asynchronous distributed setting, which will result in complex interaction dynamics ạJiang al., 202T), the theoretical analy- sis for asynchronous distributed algorithms is usually more challenging than that of the synchronous distributed algorithms. In summary, the synchronous and asynchronous algorithm have different ap- plication scenarios. When the delay of each worker is not much different, the synchronous algorithm suits better. While there are stragglers in the distributed system, the asynchronous algorithm is more preferred. So far, existing works for distributed bilevel optimization only focus on the synchronous setting (Tarzanagh et al.. 2022 Li et al.] 2022; Chen et al.) 2022b), how to design an asynchronous algorithm for distributed bilevel optimization remains under-explored. To the best of our knowledge, this is the first work that designs an asynchronous algorithm for distributed bilevel optimization.
3 ASYNCHRONOUS DISTRIBUTED BILEVEL OPTIMIZATION
In this section, we propose Asynchronous Distributed Bilevel Optimization (ADBO) to solve the distributed bilevel optimization problem in asynchronous manner. First, we reformulate problem in Eq. (2) as a consensus problem (Matamoros) 2017) Chang et al. (011)).
min F((x;): (y:) 1y v, 2) s.t.
Σ G vi)
2 u 1,..., ,N
N
(3)
{v.), = arg min f(v, (v x')
Σ (v ==1
V. (./),z'
=,,,i,=,,... N
var. (x.) (8.) 2,
where 2; E R² and y, E Rm are local variables in zth worker, v E RDd and z E RR are the con- sensus variables in the master node. The reformulation given in Eq. (3) is consensus problem which allows to develop distributed training algorithms for bilevel opumization based on the pa- rameter server architecture (Assran et al. 2020). As shown Figure 13 in parameter server ar- chitecture, the communication is centralized around the master, and workers pull the consensus variables v, z from and send their local variables w., y; to the master. Parameter server train- ing is well-known data-parallel approach for scaling up machine learning model training on multitude of machines (Verbraeken et al. 2020). Most of the existing bilevel optimization works in machine learning only consider the bilevel programs without upper-level and lower-level con- straints (Franceschi et al.) 2018 Yang et al. 2021 Chen et al. 2022a) or bilevel programs with only ueper-level (or lower-level) constraint (Zhang et al. 2002 Mehra & Hamm 2021). On the contrary, we focus on the bilevel programs (i.e., Eq. (3)) with both lower-level and upper-level constraints,
which is more challenging. By defining Φ(v) = arg min ( gi(v, v() vl = z', =1.r.,N7
3

---

Published as a conference paper at ICLR 2023
{y:} z
and h(o, (3:),) =
o(v)]l, we can reformulate problem in Eq. (3
as:
min
F((a:).(y)) U, 0, Σ Gi v:)
s.t.
2, -,=,ii=,,..
(4)
h(v 22 2)) (a,), (yi 2,
To better clarify how ADBO works, we sketch the procedure of ADBO. Firstly, ADBO computes the estimate of the solution lower-level optimization problem. Then, inspired by cutting plane method, set of cutting planes is utilized to approximate the feasible region of the upper-level bilevel optimization problem. Finally, the asynchronous algorithm for solving the resulting problem and how to update cutting planes are proposed. The remaining contents are divided into four parts, i.e,, estimate solution to lower-level optimization problem, polyhedral approximation, asynchronous algorithm, updating cutting planes.
3.1 Estimate of Solution to Lower-level Optimization Problem
A consensus problem, ie., the lower-level optimization problem in Eq. 3 needs to be solved in a distributed manner if an exact ((v) is desired. Following existing works (Li et al. 2022 Gould et al. 2016 Yang et al. 2021) for bilevel optimization, instead of pursuing the exact Φ(v), an estimate of o(v) could be utilized. For this purpose, we first obtain the first-order Taylor approximation of (z {u(}) with respect to v, i... for given point 8, Fe(U, (v(1) v). Then, similar to many works that use K steps of gradient descent (GD) to approximate the optimal solution of lower-level optimization problem (Ji et al.) 2021 Yang et al. [02T]] Liu et al. 2021b), utilize the results after K communication rounds between workers and master to approximate ((v). Specifically, given (i(v. (y(T), the augmented Lagrangian function of the lower-level optimization problem in Eq. (3) can be expressed as,
(w, (v.)) + Ve (v()) (v ((
Op(u, (v(). ((p:))
Σ
Th (.,.v/)) v/) vo (v) 2') 1 oo 2²11²)
(5)
where sp, E R is the dual variable, and μ penalty parameter. In (k: + 1)th iteration, we have, (1) Workers update their local variables as follows,
v yh Ml V V (v(,)), 2/. {sp,,))),
(6)
where Bl the step-size. Then, workers transmit the local variables y(,441 to the master.
(2) After receiving updates from workers, the master updates variables follows,
2/411 = 2 20, [v1,,,+ : 2/, (P).,))),
(7)
ii PL. Thp V p. [v A z {sp.,:)))
(8)
where and Thp are step-sizes. Next, the master broadcasts E and 44, to workers.
As mentioned above, we utilize the results after K communication rounds to approximate d(v), i.e.
{34 - K- Th V Vp (v( #/. ((),,))) K-1
0(v) =
(9)
2/ EK-1 T V Vz ( 2. (p)x))
3.2 Polyhedral Approximation
Considering ((v) in Eq. (9), the relaxed problem with respect to the problem in Eq. 44 is.
min F((x)),(u).. v, v, Σ G, y:)
s.t.
z,=,,i=l...
(10)
2()
(2,), (v.),
4

---

Published as a conference paper at ICLR 2023
where > 0 is constant. Assuming that h(v, {,,), 2) is convex function with respect to (v. }3 x), which is always satisfied when we set K = 1 in Eq. (10) according to the opera- tions that preserve convexity (Boyd et al.] 2004). Since the sublevel set of convex function is convex (Boyd et al. 2004), the feasible set with respect to constraint h(v (y: z) S & is a convex set. In this paper, inspired by the cutting plane method (Boyd & Vandenberghe 2007 Michalka 2013] Franc et al., [011;; Yang et al.) (2144), a set of cutting planes is utilized to approximate the feasible region with respect to constraint h(v, {y: z) S in Eq. (I0). The set of cutting planes forms polytope, let p' denote the polytope in (l + 1)th iteration, which can be expressed as,
N
p' (a To
Σ
b y + Gj my S 0, 1=1, [P]))
(11)
where ai E R", b E RTm C E 1 and R' are the parameters in h cutting plane, and [P*] denotes the number of cutting planes in pt. Thus, the approximate problem in (t + 1)th iteration can be expressed as follows,
min
F( (, Σ
2)
G. vi)
1=1
s.t.
2; = U, 1,,..., N
(12)
ajo+ > by, + ci Tz + 5,,
var.
(.,), (y:). 2,
The cutting planes will be updated to refine the approximation, details are given in Section 3.4.
3.3 Asynchronous Algorithm
In the proposed ADBO, we solve the distributed bilevel optimization problem in an asynchronous manner. The Lagrangian function of Eq. (12) can be written as:
N Σ b y: c + 0, (x: v), (13)
Ip (2), yi)
E
a T
where \ E 0, E I are dual variables, Lp is simplified form of (.((=:)((v))) u,2 ( (0.)).
The regularized version (Xu et al. 2020) of Eq. (13) is employed to update all variables as follows,
(p v, x, 2.(4) = Lp
|
10111
(14)
where ei and c₁ denote the regularization terms in (t + 1)th iteration. In each iteration, we set that [P'| S M, Vt. of n 2 S1. ce no((+1) E2 are two nonnegative non-increasing sequences, where and are positive constants, and constants S1 S2 meet that 0 << 9 S 1/mac, S1/ToC, c= (44Ma//1x +4Na4/ 2)1e=//))) (e, 0'3, 04 are introduced in Section 4p.
Following (Zhang Kwok 2014), to alleviate the staleness issue ADBO, we set that master updates its variables once it receives updates from S active workers at every iteration and every worker has to communicate with the master at least once every T iterations. In (t + 1)th iteration, let º (+1 denote the index set of active workers, the proposed algorithm proceeds as follows.
(1) Active workers update the local variables as follows,
at xt x
V
(1x) (. ),0% 28 1,.1.)) (HO)))) ),ie 2
(15)
L (p ). j. o 2 ).10 1
y H+
yt
Bl
(16)
v
where & denotes the last iteration during which worker was active, The and My are step-sizes, Then, the active workers transmit the local variables x and y to the master.
(2) After receiving the updates from active workers, the master updates the variables as follows,
+1 w² no V.I.p((aa 1. + 1,0", 2 (O)).
(17)
1+1 =z' -1 V. 1.(0l 1, 1,041 _, (N)))))))
(18)
5

---

Published as a conference paper at ICLR 2023
1 X + nA V (p(2 2 ")att 2 1, x +1 ((1T,1(0))
(19)
0 { 0 + + Vo.
[, ++1
), ( j,ttt 2 (M (+1 (0 e
(20)
0% & Q
where Tes T2, TJx and 1e are step-sizes. Next, the master broadcasts vt+1 . ااا 0 and (
(
to
worker i, E 2++1 (i.e., active workers). Details are summarized in Algorithm
3.4 Updating Cutting Planes
Every Kpre iterations (Kpre > 0 is a pre-set constant, which can be controlled flexibly), the cutting planes updated based on the following two steps (a) and (b) when t < Ti:
(a) Removing the inactive cutting planes,
pi+1 {
Drop(P', if Xt+1 and X = 0 P otherwise
(21)
where epi represents the 9th cutting plane in Pt and Drop(P', cpt) represents the 8th cutting plane epi is removed from Pt. The dual variable set (N++) will be updated as follows,
(x+1) Drop(fX"), Ar). X, and Xi =
(22)
(X), otherwise
where {x+1} and { represent the dual variable set in (t + 1)th and t iterations, respectively. Drop( Drop(()"), At) represents that X removed from the dual variable set (X*).
(b) Adding new cutting planes. Firstly, we investigate whether (0*+1 ( "), is feasible for the constraint h(v, {y;), S.. We can obtain
according to ((v++)) in
Eq. 99. (w'-1, (3) 4+ } 11) is not feasible solution to the original problem (Eq. (10 new
cutting plane ophtre will be generated to separate the point (v*+1, (,y ++ = from the feasible
region of constraint h(v, {y:},²) Se. Thus, the valid cutting plane (Boyd & Vandenberghe 2007
aiJo Em b Yi + + c + K4 S must satisfy that,
N
a a En b + + + Ki S ((v.vu)) z) satisfies =()
(23)
a a + E b. y + + T2 + > 0
Since h(v {y:), 2) a convex function, we have that,
ah( 1 (-1)
wi+1
))
h(v, 2) 1. {, (, ++ ah(v" 11 ( 1
{v.}
0y:
z4+1
ah(w (v) 1
82
(24)
23 we have that a valid cutting plane (with respect to point (0 ( } (TT) can be expressed as,
Combining Eq. 24
with Eq.
ah(o"t1 {y: 1,2++1
1)
Ov
h(v't1 (2/-1), 2
ah(e" < 1. 111
{
{
S E. (25)
z411
Bh(w (v] )
dz
For brevity, we utilize ep to denote the new added cutting plane (i.e., Eq. polytope pi+ will be updated as follows,
25
Thus the
Add(p'+1 .chhel)) if h( (ult1) 211) >
pi+1_
(26)
pi+l otherwise
where Add(pt+1 cpt cpt+1 represents that new cutting plane optt1 is added to polytope pi+1, The dual variable set {} 4 is updated as follows,
(x+1) Add(()+1))
X X h(u*+! (. 111 x(-1)))
(27)
(X+1). otherwise
1+1 where Add([X(+1) 1++ / represents that dual variable X p is added to the dual variable set {x++). Finally, master broadcasts the updated p*+1 and {X++1 to all workers. The details of the proposed algorithm summarized in Algorithml

---

Published as a conference paper at ICLR 2023
Algorithm ADBO: Asynchronous Distributed Bilevel Optimization
Initialization: master iteration ( (=0, variables {w}} (y.). v", =", {AP), (0.) and polytope P" repeat
for active worker do updates variables x; y, ++1 according to Eq. 15 and 16
end for
Active workers transmit their local variables to master;
for master do
updates variables v 22 ( 10t+1) according to Eq. end for
17
18
19
and (20):
master broadcasts variables to active workers; if (t + 1) mod kpree == 0 and Ti then master computes o(v++1) according to Eq. 9
master updates pi+ and (X++) according to Eq. (1
(2
(6
and
27
master broadcasts pi+11 and (X++] to all workers;
end if
=
until termination.
4 DISCUSSION
Theorem (Convergence) As the cutting plane continues to be added to the polytope, the optimal objective value of approximate problem in Eq. (12) converges monotonically. The proof of Theorem is presented in Appendix
Definition (Stationarity gap) Following (Xu et al. 2020 La et al. 2020 Jiao et al. 2022a the
stationarity gap of our problem at t iteration defined
V m. Lp ku J. (x
[ Lp he x (x))))))))
V v.lp((a))
V
(28)
(z
(Vo. (o 2 (1))
Definition (e-stationary point) (fx)) [e
( an e-stationary point > 0) of
differentiable function L.p. if V|' S.c. T(c) is the first iteration index such that G| <
i.e., T'E) = min(t || SJ.
Assumption (Smoothness/Gradieen Lipschitz) Following (J al. 2027). we assume that Lp has Lipschitz continuous gradients, i.e.,for any w, w', assume that there exists L > O satisfying that,
(w - (pp(w')| < L|lw [|| - w'll.
(29)
Assumption (Boundedness) Following (Qian et al. 2019). we assume that variables are bounded, iee., ||x,|| 3 a1, ||i||² < 01 11 S 02 | 02 || S 03, 10,100,122 < a4. And assume that before obtaining the e-stationary point (i.e. L 5 T(e) - 1), the variables in master satisfy that _ -0111 || -111-=2" 2/1 + E 11,11/+11 -f 2 G. where 0 > 0 is a relative small
constans. The change of the variables in master is upper bounded within iterations: 21 -|=--=²-<pp
|| 112
Σ, T
1 12 1 1.T,,,,,IkSS
(30)
where ki > 0 is constant.
Theorem (Iteration complexity) Suppose Assumption and hold, we set the step-sizes as ni Maegy
"h 7/- - 1/2 LL N
MrL mASs"
1/ < min| Lt24 No.k and n1 S 2-202
?"
For given e, we have:
4Na1, 1 A(d7 + Mo(N-S) (d thar(T - 1))de (T + 2)))
4Ma3
T()) T(m)=O(max(
7 no²
(31)
where 033, C44 7, hig Tı, d. de and d7 constants. The detailed proof is given in Appendix
B

---

Published as a conference paper at ICLR 2023
5 EXPERIMENT
In this section, experiments are conducted on two hyperparameter optimization tasks (i.e., data hyper-cleaning task and regularization coefficient optimization task) in the distributed setting to evaluate the performance of the proposed ADBO. The proposed ADBO is compared with the state- of-the-art distributed bilevel optimization method FEDNEST (Tarzanagh et al. 2022). In data hyper-
cleaning task, experiments are carried out MNIST (LeCun et 1998)) and Fashion MNIST (Xiao) ctt al., 2017) datasets. In coefficient optimization task, following (Chen et al. 2022a). experiments
conducted on Covertype (Blackard & Dean
1999) and IJCNNI (Prokhorov 2001 datasets.
5.1 DATA HYPER- -EEERCCG
Following Ji al. 2021 Yang al. 2021) compare the performance of the proposed ADBO and distributed bilevel optimization method FEDNEST on the distributed data hyper-cleaning task (Chen et al. 2022b) on MNIST and Fashion MNIST datasets. Data hyper-cleaning involves training a classifier in a contaminated environment where each training data label is changed to a random class number with a probability (i.e., the corruption rate). In the experiment, the distributed data hyper-cleaning problem is considered, whose formulation can be expressed as,
min F(zb, un) = Σ
Σ
[(x)
un M/)
D
(32)
s.t. w arg min f(t, w')
Σ
Σ (x;:;;)ED
T w') + C, 2 ((x))((xx)
D
w t/, w
var.
where D and Dyyal denote the training and validation datasets on 8th worker, respectively. (x,, denote the jth data and label. a(.) is the sigmoid function, L is the cross-entropy loss, C,, is regularization parameter and N is the number of workers in the distributed system. In MNIST and Fashion MNIST datasets, we set N = 18, S = 9 and = 15. According to Cohen et al. (202T), we assume that the communication delay of each worker obeys the heavy-tailed distribu- tion. The proposed ADBO is compared with the state-of-the-art distributed bilevel optimization method FEDNEST and SDBO (Synchronous Distributed Bilevel Optimization, i.e., ADBO without asynchronous setting). The test accuracy versus time is shown in Figure I and the test loss versus time is shown in Figure 2 We can observe that the proposed ADBO is the most efficient algorithm since 1) the asynchronous setting is considered in ADBO, the master can update its variables once receives updates from S active workers instead of all workers; and 2) ADBO is a single-loop algo- rithm and only gradient descent/ascent is required at each iteration, thus ADBO computationally more efficient.
5.2 REGULARIZATION COFFFICIENT OPTIMIZATION
Following (Chen et al. 2022a), we compare the proposed ADBO with baseline algorithms FEDNEST and SDBO on the regularization coefficient optimization task with Covertype and JJCNN datasets. The distributed regularization coefficient optimization problem is given by,
min F(b, w) = Σ
Σ
L(x;
w. Uy)
Dral
(E
N
(33)
s.1. w = arg min szb, w w
Σ
Σ (x)
C(x, T (0',y;)= + Σ (wg)2
DF
var.
w w,
where R" Rm and L respectively denote the regularization coefficient, model parameter, and logistic loss, and w' [w/ ..., w, In Covertype and IJCNN1 datasets, we set N 18, S = 9, т and N = 24, 5 12, obeys the heavy-tailed distribution. Firstly, compare the performance of the proposed ADBO, SDBO and FEDNEST in terms of test accuracy and test loss on Covertype and IJCNNI datasets,
15, respectively. We also assume that the delay of each worker
Codess available in httpt:tpp//// thub. com/ 1C..233mmm on6251
8

---

Published as a conference paper at ICLR 2023
which are shown in Figure and 4 is seen that the proposed ADBO is more efficient because of the same two reasons we gave in Section 5.1
0.a
ABSO S080 FEINEST
102 30t.ccursg
0.5
1.5
FEDNEST
04
tast
ADDO FEDNIST
ABDC 5080 PEDNEST
0.2
02
0.5
0.0
503
100
0.2
200
402
000
1000
6.0
000
200
0000
1000
(a) MNIST
(b) Fashion MNIST
(a) MNIST
(b) Fashion MNIST
Figure 1: Test accuracy vs time on (a) MNIST Figure 2: Test loss vs time on (a) MNIST and
and (b) Fashion MNIST datasets.
(b) Fashion MNIST datasets.
0.9
ACDO
A25O
1e2t actursc
0.5
0.8
5D 50 PEDNEST
0.8
PEDNEST
5000
0.4
20.
ADDO 5080 MEDNEST
1.25
1.30
0.4
202
480
600
000
200
400
5:00
500
1020
400
600
809
203
462
800
1000
Lime 16)
Uma (4)
Lime (6)
Uma (3)
(a) Covertype
(b) JJCNNI
(a) Covertype
(b) JJCNNI
Figure 3: Test accuracy vs time on (a) Cover- Figure 4: Test loss vs time on (a) Covertype and
type and (b) IICNNI datasets.
(b) IJCNNI datasets.
Best acouroc
0.5
0.8
0.9
5050
ADBO
PEDNEST
2.50
1.75
ADBO 5000 REDREST
1.50
ADGO
ADGO
5080
SDA0
FEDWIEST
0.5
FESNIEST
0.2
0
203
420
600
800
200
400
500
500
1020
0
200
400
500
502
200
400
500
800
1000
time
Ume (4)
Uma
(a) Covertype
(b) JCNNI
(a) Covertype
(b) LJCNN1
Figure 5: Test accuracy vs time on (a) Cover-
Figure 6: Test loss vs time on (a) Covertype and (b) IJCNNI datasets when there are stragglers in distributed system.
type and (b) JJCNNI datasets when there are stragglers in distributed system.
We also consider the straggler problem, ie.. there exist workers with high delays (stragglers) in the distributed system. In this case, the efficiency of the bilevel optimization method with the syn- chronous distributed setting will be affected heavily. In the experiment, we assume there are three stragglers in the distributed system, and the mean of (communication + computation) delay of strag- glers is four times the delay of normal workers. The results on Covertype and IJCNN1 datasets are reported in Figure 5 and [6] It is seen that the efficiency the synchronous distributed algorithms (FEDNEST and SDBO) will be significantly affected, while the proposed ADBO does not suffer from the straggler problem since it is an asynchronous method and is able to only consider active workers.
6 CONCLUSION
Existing bilevel optimization works focus either on the centralized or synchronous distributed set- ting, which will give rise to data privacy risks and suffer from the straggler problem. As rem- edy, we propose ADBO in this paper to solve the bilevel optimization problem in an asynchronous distributed manner. To our best knowledge, this is the first work that devises the asynchronous distributed algorithm for bilevel optimization. We demonstrate that the proposed ADBO can effec- tively tackle bilevel optimization problems with both nonconvex upper-level and lower-level objec- tive functions. Theoretical analysis has also been conducted to analyze the convergence properties and iteration complexity of ADBO. Extensive empirical studies on real-world datasets demonstrate the efficiency and effectiveness of the proposed ADBO.
9

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The work of Yang Jiao, Kai Yang and Chengtao Jian was supported in part by the National Natural Science Foundation of China under Grant 61771013, in part by the Shenzhen Institute of Artificial Intelligence and Robotics for Society (AIRS), 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. We thank Haibo Zhao for providing the experiment results in meta-learning.
REFERENCES
Mahmoud Assran, Arda Aytekin, Hamid Reza Feyzmahdavian, Mikael Johansson, and Michael G Rabbat. Advances in asynchronous parallel and distributed optimization. Proceedings of the IEEE, 108(L1):2013-2031, 2020.
Luca Bertinetto, Joao Henriques, Philip Torr, and Andrea Vedaldi. Meta-learning with differen- tiable closed-form solvers. In International Conference Learning Representations, 2018.
Arpan Biswas and Christopher Hoyle. literature review: Solving constrained non-linear bi-level optimization problems with classical methods. In International Design Engineering Technical Conferences and Computers and Information Engineering Conference, volume 59193, pp- V02BT03A025, American Society of Mechanical Engineers, 2019.
Jock A Blackard and Denis J Dean. Comparative accuracies of artificial neural networks and dis- criminant analysis in predicting forest cover types from cartographic variables. Computers and electronics in agriculture, 24(3):131-151, 1999.
Stephen Boyd and Lieven Vandenberghe. Localization and cutting-plane methods. From Stanford EE 364b lecture notes, 2007.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge uni- versity press, 2004.
Stephen Boyd, Neal Parikh, and Eric Chu. Distributed optimization and statistical learning via the alternating direction method of multipliers. Now Publishers Inc, 2011.
Jerome Bracken and James T McGill. Mathematical programs with optimization problems in the constraints. Operations Research, (1)::377444, 1973.
Tsung-Hui Chang, Mingyi Hong. Wei-Cheng Liao, and Xiangfeng Wang, Asynchronous distributed ADMM for large-scale optimization- Part I: Algorithm and convergence analysis. IEEE Trans- 2016.
actions Signal Processing, 64(12):3118-33
Tianyi Chen, Yuejiao Sun, Quan Xiao, and Wotao Yin. A single-timescale method for stochastic bilevel optimization. In International Conference on Artificial Intelligence and Statistics, pp- 2466-2488. PMLR, 2022a.
Xuxing Chen, Minhui Huang, and Shiqian Ma. Decentralized bilevel optimization. arXiv preprint ntn::2206.567700 2022b.
Yujing Chen, Yue Ning. Martin Slawski, and Huzefa Rangwala. Asynchronous online federated learning for edge devices with Non-IID data. In 2020 IEEE International Conference on Big Data (Big Data), pp. 15-24. IEEE, 2020.
Alon Cohen, Amit Daniely, Yoel Drori, Tomer Koren, and Mariano Schain. Asynchronous stochastic optimization robust to arbitrary delays. Advances in Neural Information Processing Systems, 34: 9024-9035, 2021.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc' aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, et al. Large scale distributed deep networks. Advances in neural information processing systems, 25, 2012.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta- veta-learning for fast adaptation of deep networks. In International conference on machine learning, pp. 1126-1 1 135. PMLR, 2017.
10

---

Published as a conference paper at ICLR 2023
Vojtech Franc, Sören Sonnenburg, and Tomás Werner Cutting plane methods in machine learning. Optimization for Machine Learning, pp. 185-218 2011.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning In International Conference on Machine Learning, pp. 1568-1577. PMLR, 2018.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:/802.022465 2018.
Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo. On differentiating parameterized argmin and argmax problems with application to bi-level optimization. arXiv preprini arXiv:1607.0544 0044470..747. 2016.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint arXiv: 000.1276670.77. 2017.
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration com- plexity of hypergradient computation. In International Conference on Machine Learning, pp- 3748-3758 PMLR, 2020.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. arXiv preprint arXiv:2007.055/7.. 2020.
Zhouyuan Huo, Bin Gu, and Heng Huang. Large batch optimization for deep learning using new complete layer-wise adaptive rate scaling. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 7883-7890, 2021.
Kaiyi Ji, Jason D Lee, Yingbin Liang, and H Vincent Poor. Convergence of meta-learning with task- specific adaptation over partial parameters. Advances Neural Information Processing Systems, 13:11490-10 1500, 2020.
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference Machine Learning, pp. 4882 4892. PMLR, 2021.
Chenhan Jiang, Hang Xu, Wei Zhang. Xiaodan Liang, and Zhenguo Li. Sp-nas: Serial-to-paralle backbone search for object detection. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 11863-11872 2020.
Jiyan Jiang, Wenpeng Zhang, Jinjic Gu, and Wenwu Zhu. Asynchronous decentralized online learn- ing. Advances in Neural Information Processing Systems, 14:20085520115 2021.
Yang Jiao, Kai Yang, and Dongjin Song. Distributed distributionally robust optimization with non- convex objectives. arXiv preprint arXiv:2210.07588, 2022a.
Yang Jiao, Kai Yang, Dongjing Song, and Dacheng Tao. Timeautoad: Autonomous anomaly de- tection with self-supervised contrastive loss for multivariate time series. IEEE Transactions on Network Science and Engineering, 963:110041119, 2022b.
Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A near-optimal algorithm for stochastic bilevel optimization via double-momentum. Advances in Neural Information Processing Systems, 34:30271-30283 2021.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science. 15326266) 2015.
Quoc Le. Building legel features using large scale unsupervised learning. 2013 IEEE international conference acoustics, speech and signal processing, pp. 8595-8598. IEFE, 2013.
11

---

Published as a conference paper at ICLR 2023
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11))2278-2 -3224, 1998.
Junyi Li, Feihu Huang, and Heng Huang. Local stochastic bilevel optimization with momentum- based variance reduction. arXiv preprint arXiv:2205.0 20000000000 2022.
Renjie Liao, Yuwen Xiong, Ethan Fetaya, Lisa Zhang, KiJung Yoon, Xaq Pitkow, Raquel Urta- sun, and Richard Zemel. Reviving and improving recurrent back-propagation. In International Conference on Machine Learning, pp. 3082-3091 PMLR, 2018.
Valerii Likhosherstov, Xingyou Song, Krzysztof Choromanski, Jared Q Davis, and Adrian Weller. Debiasing a first-order heuristic for approximate bi-level optimization. In International Confer- ence on Machine Learning, pp. 6621-6630. PMLR, 2021.
Risheng Liu, Xuan Liu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A value-function-base interior-point method for non-convex bi-level optimization. In International Conference Ma- chine Learning, pp. 6882 6882-6892. PMLR, 2021a.
Risheng Liu, Yaohua Liu, Shangzhi Zeng, and Jin Zhang. Towards gradient- based bilevel optimiza- tion with non-convex followers and beyond. Advances in Neural Information Processing Systems, 34:8662-8675, 2021b.
Rui Liu and Barzan Mozafari. Communicationn-efficeeee distributed learning for large batch opti- mization. In International Conference on Machine Learning, pp. 13925-13946, PMLR, 2022.
Yaohua Liu, Cameron Nowzari, Zhi Tian, and Qing Ling, Asynchronous periodic event-triggered coordination multi-agent systems. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pp.
IEEE, 2017.
Yinghui Liu, Youyang Qu, Chenhao Xu, Zhicheng Hao, and Bruce Gu. Blockchain asyn- chronous federated learning in edge computing. Sensors, 21(10):3335, 2021c.
Songtao Lu, Ioannis Tsaknakis, Mingyi Hong, and Yongxin Chen. Hybrid block successive ap- proximation for one-sided non-convex min-max problems: algorithms and applications. 1EEE Transactions on Signal Processing. 68:3676-366 -6911, 2020.
Songtao Lu, Xiaodong Cui, Mark Squillante, Brian Kingsbury, and Lior Horesh. Decentralized bilevel optimization for personalized client learning. In ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5543-5547. IEEE, 2022.
Yunlong Lu, Xiaohong Huang, Yueyue Dai, Sabita Maharjan, and Yan Zhang. Differentially pri- vate asynchronous federated learning for mobile edge computing in urban informatics. 1EEE Transactions Industrial Informatics, 16(3):2134-214) 21433, 2019.
Javier Matamoros. Asynchronous online ADMM for consensus problems. In 20/7 IEEE Interna- tional Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5875-5879. IEEE, 2017.
Akshay Mehra and Jihun Hamm. Penalty method for inversion-free deep bilevel optimization. In Asian Conference on Machine Learning, pp. 347-362. PMLR, 2021.
Alexander Michalka. Cutting planes for convex objective nonconvex optimization. Columbia Uni- versity, 2013.
Yurii Nesterov. Introductory lectures on convex optimization: basic course, volume 87. Springer Science & Business Media, 2003.
Danil Prokhorov. Ijenn 2001 neural network competition. Slide presentation IJCNN, 1(97):38, 2001.
Qi Qian, Shenghuo Zhu, Jiasheng Tang, Rong Jin, Baigui Sun, and Hao Li. Robust optimization over multiple domains. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4749.4746, 2019.
12

---

Published as a conference paper at ICLR 2023
J. Ross Quinlan. Simplifying decision trees. International journal of man-machine studies, 27(3): 221-234, 1987.
Aniruddh Raghu, Maithra Raghu, Samy Bengio, and Oriol Vinyals. Rapid learning feature reuse? towards understanding the effectiveness of maml. In International Conference on Learning Rep- resentations, 2019.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with im- plicit gradients. Advances in neural information processing systems, 32, 2019.
Ankur Sinha, Pekka Malo, and Kalyanmoy Deb. A review on bilevel optimization: from classical to evolutionary approaches and applications. IEEE Transactions on Evolutionary Computation, 22 (2):276-295, 2017.
Tejas Subramanya and Roberto Riggio. Centralized and federated learning for predictive vnf au- toscaling in multi-domain 5g networks and beyond. IEEE Transactions on Network and Service Managemens, 18(1):63-78, 2021.
Davoud Ataee Tarzanagh, Mingchen Li, Christos Thrampoulidis, and Samet Oymak. Fednest: Fed- erated bilevel, minimax, and compositional optimization. arXiv preprint arXiv:2205.0221 2022.
Joost Verbraeken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan Rellermeyer. A survey on distributed machine learning. Acm computing surveys (csur), 53(2): 1-33, 2020.
Tong Wang, Yousong Zhu, Chaoyang Zhao, Wei Zeng, Yaowei Wang, Jinqiao Wang, and Ming Tang. Large batch optimization for object detection: Training coco 12 minutes. European Conference on Computer Vision, pp. 481-496 Springer, 2020.
Tianyu Wu, Kun Yuan, Qing Ling, Wotao Yin, and Ali H Sayed. Decentralized consensus optimiza- tion with asynchrony and delays. IEEE Transactions Signal and Information Processing over Networks, 4(2):293-307, 2017.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: A novel image dataset for bench- marking machine learning algorithms. arXiv preprint arXiv: 1708.07747, 2017.
Zi Xu, Huiling Zhang, Yang Xu, and Guanghui Lan. A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems. arXiv preprint arXiv:2006.0200 2020.
Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. Ad- vances Neural Information Processing Systems, 34:13670-13663 13682, 2021.
Kai Yang, Jianwei Huang, Yihong Wu, Xiaodong Wang, and Mung Chiang. Distributed robust optimization (DRO), part Framework and example. Optimization and Engineering. 15(1):35- 67, 2014.
Shuoguang Yang. Xuezhou Zhang, and Mengdi Wang. Decentralized gossip- stochastic bilevel optimization over communication networks, arXiv preprint 1XXx:22266.18700. 2022.
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training bert in 76 minutes. arXiv preprint / 190400994.0222.. 2019.
Ruiliang Zhang and James Kwok. Asynchronous distributed ADMM for consensus optimization. In International conference on machine learning, pp. 1701-1709. PMLR, 2014.
Yihua Zhang, Guanhuan Zhang, Prashant Khanduri, Mingyi Hong, Shiyu Chang, and Sijia Liu. Revisiting and advancing fast adversarial training through the lens of bi-level optimization. arXiv preprint arXiv:2 12376, 2021.
Yihua Zhang, Guanhua Zhang, Prashant Khanduri, Mingyi Hong, Shiyu Chang, and Sijia Liu. Re- visiting and advancing fast adversarial training through the lens of bi-level optimization. In Inter- national Conference Machine Learning, pp. 26693-2677 PMLR, 2022.
Ziyuan Zhou and Guanjun Liu. Romfac: robust mean-field actor-critic reinforcement learning against adversarial perturbations on states. arXiv preprint arXiv:2205.07229, 2022.
13

---

Published as a conference paper at ICLR 2023
A CUTTING PLANE METHOD FOR BILEVEL OPTIMIZATION
In this section, a cutting plane method, named CPBO. is proposed for bileve optimization. Defining (xx) arg min (ax y²) and h(x,2) y) 1y <(x) ||?
we can reformulate problem in Eq. dI as:
min F(x; y) h(x, =0
s.t.
(34)
var. 2, y-
Following the previous works (Li et al. optimization, it is not necessary to get the exact di (()), and the approximate (xx) is given as follows. Firstly, as many work do (Ji et al. 2021 Yang et al. (02T), we utilize the K steps of gradient descent (GD) to approximate Φ(z). And the first-order Taylor approximation of fxx y') with respect to æ considered, i.e., for given point a: [xx, 10' (ar, y') fa y') (ac 2:). Thus, we have,
2022, Gould al., 2016 Yang al. 2021 in bilevel
<(x) = 3 Σn K
7 v.y az, yk),
(35)
where 7) is the step-size. Considering the estimated ((x) in Eq. (5p. the relaxed problem with respect to problem in Eq. 34 is considered as follows,
min F(x, y) s.t. h(x,z) SE
(36)
var. 2, y.
Assuming that h(x y) is a convex function with respect to (x: y). which is always satisfied when we set K = 1 in Eq. (35) according to the operations that preserve convexity (Boyd et al. 2004). Since the sublevel set convex function is convex, we have that the feasible set of (æ. y), ie.,
rrlaaz_
{(x, y) E R x h(x, y) <c
(37)
a convex set. We utilize a of cutting plane constraints (i.e., linear constraints) to approximate the feasible set rellaz The set of cutting plane constraints forms polytope, which can be expressed follows,
b where ai R by ERm and fe ER are parameters in 7ch cutting plane, and represents the number of cutting planes in P. Considering the approximate problem, which can be expressed as follows,
P= (=((2 y) R" x"
a b, y 10..........1)
(38)
min F(x. y)
s.t. at x+tb bi T y S 0, 1=1, 1=1,-.;17 IP'
(39)
var. x. y.
where P is the polytope in (t + 1)th iteration, and |P| denotes the number of cutting planes in p'. Then, the Lagrangian function of Eq. (39) can be written as,
(x y. (Ar)) = F(z, y) + Σ x(aa T x + y+m),
(40)
where A is the dual variable. The proposed algorithm proceeds as follows in (t + 1)th iteration:
If < Tr, the variables are updated as follows,
r- = x' nh V Lp (z' 3 (Df))
(41)
41 3' - - V Ly tt v²' (x1))
(42)
X = X n4 VA, (x0 +1 +1 (11), 1=1,"., P'),
(43)
where 7a. My and nA. the sizes.
And every kpre iterations (kpro > 0 is a set constant, which can be controlled flexibly) the cutting planes will be updated based on the following steps:
14

---

Published as a conference paper at ICLR 2023
Table I: Convergence results of bilevel optimization algorithms (with centralized and distributed
setting).
Method
Centralized
Synchronous (Distributed)
Asynchronous (Distributed)
AID-BiO Ghadimi & Wang 2018
O (
NA
NA
AID-BiO
Ji ct al.
2021
(
NA
NA
ITD-BiO
al. 2021
((1)
NA
STABLE Chen
ul.
2022a
((+)²
NA
NA
stocBio Ji et al. 202
O(2)
NA
NA
VRBO Yang al. 2021
(
NA
NA
FEDNEST Tarzanagh et al. 2022
NA
NA
SPDB [Lu al., [0222
O )
NA
DSBO Yang al. 2022
NA
)
NA
Proposed Method
(
NA
Stochastic optimization algorithm.
(a) Removing the inactive cutting planes, that is,
p {
Drop(P', ip ,p'), X and X; p', otherwise
(44)
where epi represents the tth cutting plane in P', and Drop(P', cpt) represents removing the 4th cutting plane ept from pt. And the dual variable set {X* will be updated follows,
(r",( XT+1 and Ai = 0
(45)
(*), otherwise
where {1++1} } and { respectively represent the dual variable set in (t + 1)th and 9th iteration. And Drop((X', }. Xf) represents that X is removed from the dual variable set (X*).
(b) Adding new cutting planes. Firstly, we investigate whether (a*+1.y/* + is feasible solution to the original problem in Eq. (36). If (x:+11 y is not a feasible solution to the original problem, that is h(*++1, + > E, new cutting plane is generated to separate the point (a*+1, y from Z Zrelar that is, the valid cutting plane a, T,+b, +
I 0 must satisfy that,
{
x + bi ytKI < O, V(x, y) E Zreiaz a a +b; 4 +k > 0
(46)
Since h(x, y) is a convex function, we have that,
0h(2n +1 (1) Ohi(w
x
1)
( 2 h(x0+1, 1 x(+1) + +
x
(47)
(12)
y
By
ahia ++1 +1
x y
1)
According to Eq. (47), h(x++1, ( +)+
Dp
S is valid
Bh(ar .y dy
y
cutting plane at point (+1 y 1(11) which satisfies Eq. this cutting plane. Thus, we have that,
446
For brevity, we utilize cp/t1 denote
Add(p opttt) if h(x ((+))> pt+ if h(x )1 Se
pt+1_
(48)
where Add( cp(+1 represents that new cutting plane cptta is added polytope pi+1 And the dual variable set is updated as follows,
(x+1)= of
Add((x+1), ) if 1(xt+1,, - >E
(49)
(N41), h(x +1) Se
15

---

Published as a conference paper at ICLR 2023
Algorithm 2 CPBO: Cutting Plane Method for Bilevel Optimization
Initialization:
iteration O, variables æ². y², {NP) and polytope Po.
repeat
if / < Ti then
updating variables x'+1, y +1 and A 1 according to Eq. (41p.
422
and (33
if (t 1) mod Apr == 0 then
updating the polytope p according to Eq. 444 and 48
updating the dual variable set {X++}} according to Eq. 45
and 49
end if
else
updating variables x1 and + according to Eq. 50 and 51
end if
== + 1; until termination.
0.6
3.0
CP8O
VR80
2.5
0.4
stacBI
0.3
CP30
2.0
Test
VR80
0.2
STABLE
0.1
sto3300
1.0
0.0
0
time
(a) test accuracy vs time
(b) test loss vs time
Figure 7: Comparison of (a) test accuracy vs time, (b) test loss vs time on Covertype dataset.
where Add(()+1)) A+1 (p++1)) represents that new dual variable A pi+i is added to [X+1).
Else if 2 Ti, the polytope TTi and dual variables will be fixed. Variables æ, y will be updated as follows,
x ++1 xx 1/0 V VoL y²). y st1 = yy 1 V V 2²)
(50)
(51)
where Lp(x, v) F(x, v)
Σ [max((, aj + * And details of the proposed
algorithm are summarized in Algorithm the proposed method and state-of oftthe-rrt methods are summarized in Table
2 The comparison about the convergence results between
A. EXPERIMENT
To evaluate the performance of the proposed CPBO, experiments carried out two applica- tions: 1) hyperparameter optimization, 2) meta-learning, In hyperparameter optimization, we com- pare CPBO with baseline algorithms stocBio (Ji et al. 2021) STABLE (Chen al., 2022a). VRBO Yang et al. 202T)), ) and AID-CG (Grazzi et al. 2020) on the regularization coefficient optimiza- tion task (Chen et al. 2022a) with Covertype (Blackard & Dean 1999) and JCNN1 (Prokhorov 2001) datasets. We compare the performance of the proposed CPBO with all competing algorithms in terms of both the test accuracy and the test loss, which are shown in Figure and g meta- learning, we focus on the bilevel optimization problem in (Rajeswaran et al. 2219). And we compare the proposed CPBO with baseline algorithms MAML (Finn et | 7) iMAML (Rajeswaran et al.) 2019). and ANIL (Raghu et al. 2019) on Omniglot (Lake et al. 2015) and CIFAR-FS (Bertinetto et al. 2018) datasets. And the comparison between the proposed method with the baseline algo- rithms shown in Figure 9 and 10 It is seen that the proposed CPBO can achieve relatively fast convergence rate among all competing algorithms since 1) the iteration complexity of the proposed method is not high; every step in CPBO is computationally efficient.
201
16

---

Published as a conference paper at ICLR 2023
1.4
CP60
0.9
1.2
test accuracy
0.8-
CP80
STABLE
0.7-
STAGLE
0.8
AID-CG
stocBio
AD-CG
0.6
0.5
0
10
15
20
5
10
25
20
time (s)
time (s)
(a) accuracy time
(b) test loss vs time
Figure Comparison of (a) test accuracy vs time, (b) loss time on IJCNNI dataset.
1.00
0.8
IMAML
0.95
0.6
MAML
ANIL
0.90
0.4
IMAM
0.85
ANI
0.80
500
1000 time (s)
1500
2000
time (s)
(a) accuracy time
(h) test loss time
Figure 9: Comparison of (a) test accuracy time, (b) test loss vs time Omniglot dataset.
A.2 DISCUSSION
Definition A.1 (x, y) is e-stationary point of a differentiable function Ly. V L y)11 + 1V, y)1 <.
Assumption A.1 (Smoothness/Gradte Lipschitz) Following (Ji et al. 2021 assume that Lp has Lipschitz continuous gradients, i.e., for any w. w', we assume that there exists L > satisfying that,
[Q - Vi,(w')I S -||w- - w'|l
(52)
Assumption A.2 (Boundedness) Following Qian al. 2019 assume that variables have boundedness, ie.. ||:||² S 31, |/ < 32.
A.2 and setting the step-sizes as The < 2. fl 2. the iteration complexity (also the gradient complexity) of the proposed algorithm to obtain e-stationary point is bounded by (
Theorem (Iteration Complexity) Under Assumption A.7
Proof of Theorem 3-
According to Assumption A.I and Eq. 50 when t 2 Ti, we have,
L,(x011,10 ,yy < (x0, y') + V y') x r0t1 x²) + 1 x012
(53)
< L,(x' v²) nz V (at 1²)1 + Line | Lx ,'),,
Similarly, according Assumption A.I and Eq. 5 have,
(x )²+l) < (1 y²) (0)=+++l""))+)
V (zx , y v¹ + 2 11 121
(54)
s 1,( .y) - 7y V Vy 12 + bry- | (x
17

---

Published as a conference paper at ICLR 2023
CRSO
0.65
IMANL
MAMI
ANIL
1.1
1.0
0.50
0.9
500
1000
1500
2000
time (s)
Lime (s)
accuracy time
(b) test loss vs time
Figure 10: Comparison of (a) test accuracy time, (b) test loss vs time on CIFAR-FS dataset.
Combining Eq. (53 with Eq. 54
we have,
Im )[ (x' y +1) +1
Lmg
(Nw 2
o y3)11 s Ep(a', y²) (2x t1
2
(55)
Lny > 0. And we set According to the setting of 7w. Ty. we have that Lon > 0. fl
constant d = min Imp fl
Loy
2 }. thus we can obtain that,
2
L.plar y²) Explas (I 11
VoLp 8'112 VV y')11
(56)
Summing both sides of Eq.
56 for 1 (Ti, T 1}. we obtain that,
T T T
(p ,.")),))) ) Lg (T T-Ti)d
(1 1²)11 + 1, w')(
(57)
Ti)d
have that the number of iterations required by Algorithm 2 to return an e-stationary point is bounded by
where L; min Lp (x.y). Combining Eq. (57) with Definition A.1
0 (n( 1 i
Tı).
(58)
B PROOF OF THEOREM 2
In this section, we provide complete proofs for Theorem 2 our problem.
Firstly, we make some definitions about
Definition B.1 Following (Xu al. 2020), the stationarity gap 8th iteration is defined as:
(V (ot
VG
(59)
(Vo, (o))
18

---

Published as a conference paper at ICLR 2023
And also define:
(VG').. = Va, Ve..cpeeee11100)oo.ee40000011
(VG*),. - V.. Vw
(VG"), - (.
(60)
(VG*)= [=l_(((eehh((dd)))""""<2111111
(VG")A, Va2euu(eeeki00tteos::44400000000
(VG"),, Vo. (4
follows that,
PP'
VVG P
x(V)))
(61)
Definition B.2 At 8th iteration, the stationarity gap w.r (px( (, is defined
as:
av W4
(62)
We further define:
(Vē').. = Va. [.l
(VG') )2 = V (M.
(Vō*). V, (,.,,
(63)
(Vō*)= (=2,(((ee)(((0))))00040011
(Vō*),, (..
(Vō').. Va, 222
follows that,
PP (V(V)" 211
(64)
Definition B.3 In the proposed asynchronous algorithm, for the 7th worker in thh iteration, the last iteration where this worker was active is defined as i.. And the next iteration this worker will be active defined as T. For the iteration index set which 4th worker is active during T₁ + + iteration, it is defined as (T) And the jth element in V.(T) is defined as ūz(j).
Then, provide some useful lemmas used for proving the main convergence results in Theorem 2
19

---

Published as a conference paper at ICLR 2023
Lemma Let sequences Ti= '// m/ n/2
2
suppose
nglo
Assumption I and 2 hold, we can obtain that,
Lp(1 +1 J.ly
1, ,-' "ooltt"J,'"
(MNHO)) Lp
N
Σ (
= m/ x ( - 1| + Σ
( my
I1.. +1 wfl 3N L2
Σ
-
+( L 1 -
+ L
o/ |||| 111
2
(65)
Proof of Lemma 1:
Utilizing the Lipschitz properties in Assumption 1, we can obtain that,
Lp((xft) 1+1 abr www...)))........... (e)
Lp((=ft)
11 -
(1 , ", ("
$ (ox)) (o ,z", + - | -
(66)
Summing up the above inequalities in Eq. 66). we can obtain that, ++1 hhhhh (1))))))))
(67)
(,) x!) + -x(1))
Combining V V., (1x (1) o 1. v., (p (x with Eq. 15). we have that,
(a/t1 2/1 Vo, L,
-- <
x
12
(68)
Next, combining the (1) Le. ( H. 1 a (
inqquality with Assumption 1, 2, we can get,
1+1 x/, Va, Lp (1 (1
Ip'|
< $11100 x 1| (1|0
= ||
Σ || - 112) 113)
2
3L'
(1
- Σ ||
2
(69)
Thus, according to Eq.
67
68
and 69
we can obtain that,
(pp(12 (0((a(t1))00 ).(
(11) (0))
( _²,, ,2, (1)))(0))
1P'
1+1
+
aN T
( -|
-
2
2
(70)
20

---

Published as a conference paper at ICLR 2023
Similarly, using the Lipschitz properties in Assumption 1, we have,
Lp Lp((0} }.lvt + ),ot -001101)))0110) ('(()))())))
(71)
(V Ixp (100) ut) lly -.l1.).
Combining Vn n. (p(t ), vh, 22,00 vz (v/)) 00 , (Af)), )0 with Eq. (6). we can obtain that,
y y Vv, Lppapt Jel ta - w/1l
1
|| yf 11?
77
(72)
Then, combining the Cauchy-Schwarz inequality with Assumption 1, 2, we can get the following inequalities,
(utt) v Vy. Tupl (2)) }.(v v² ((A)) v. T (1af ).(el ),0% 1..
(P'
2111,t1 - v111 + 1a (1|= - 211| 1 + +|0 1 11 1|2 +||11 - 21 1|
Σ
| X 113)
i=1
S & (+1 yf 1/2 |oo - -n/ft==:ll" 31,77k (1 1|bb't1-b")) +||
Σ |
(73)
Thus, combining Eq.
with 73 we have,
T.p ((x
2' (M))((0) - [,p 1. 2², ((())((0)
N
Σ (
will || Σ
(74)
i=1
iPl
+ 7N
(1 || 2 1|
Σ -(11).
Combining the Lipschitz properties in Assumption with Eq. 17 we have,
(p 41 +1 J,0 ((1)(())) Lp((
(+1 J. ),00==² ({))))))(
s (VoLp(fa ", (()),(())), w -
(75)
< 4 -0
Similarly, combining the Lipschitz properties in Assumption 1 with Eq. 18). have,
Lp (p(1xtt2), (. +1 - +1 (+ (21)),(0))
u ,2,, ((((0))1(00)))
21 < (V (1=x }.(2)" ++ | (111), -2)+ 2
(76)
< 4 +++ 111
By combining Eq.
70
74
75
76
we conclude the proof of Lemma 1.
21

---

Published as a conference paper at ICLR 2023
Lemma 2 Suppose Assumption 1 and 2 hold, Vt 2 T1. we have:
3.1%
,z++1 .1x
1.(0
(((0+1))) }) Lp(( x², xx((()))(0))
N
L+
1
1
1
x ++1 1 11?
201
20g
+(
[+1_
1
IP'
1.2
1
|z.
N
y
++1
y 1|
%
20g
L46rk, N
P'
L
)110 ++1 - 00112
2
1/6
201
20s
(77)
+(
IP'1L2
)| ++ =111 2010
Σ
N
10 0 1-
2
2/
201
2ng
|P|
+( N2
|
++1 - X/1
| + (2
c
c2
+ 2no
10
10.+1-0:1
0:
2
+ 2 (11A 11-1
Σ
1
1-1
Σ
N
119119)
2
2
where 01 > 0 and 03 > O are constants.
Proof of Lemma 2:
According to Eq. 19 in (t + 1)th iteration, AA E A, it follows that:
(1t1- X V Vn, [p(( ).(l J, e+ , 241
(A) =0. 0.
(78)
Let À Xi. we can obtain:
Iv (allllt"""(((tt (.lltt), 2111 (())((0))) - (1541 -1 -2/41 0.
(79)
Likewise, in thh iteration, we can obtain:
_ 11,
1
(80)
Since (f 0,, is concave with respect X and follows from Eq.
79) and
Eq. (8). 11 2 7j, we have,
(1
[. 1 ( (0)) Tzp((ttt)), (,(0t ),,0t1 2211 ()))((0))
V Vx [{== (.(x 1,0 ++| (1)),(0;)), -x)
<
(V (1
()))
11)
+ m (2f - X1 1-1 X+1 - x)))
(81)
Denoting o/ = 1+1 A1 (2j x we can get the following equality,
V V (1 (1tp::/40000000.......0000004441
-x)
(,4.0(10004443(100))320022006110 (16)
(40.001.000000000000000001111111 - x (1c).
(82)
22

---

Published as a conference paper at ICLR 2023
First, we put attention on the (1a) in Eq.
82
(1a) can be expressed follows,
(v (1 ).(y -
(0))
(V Lp(( a
++ J.(y, ), 1101::1000000001/010000000111111 (,100)))))1)))) -
11
2 (11)
- -111
(83)
Combining Stucch-Schwarre inequality with Assumption 1, we can obtain,
(V ( 4+1 11
(+1 1 + -(1))100) V T (t) (2)) X 11)
(1 1+1 2 + l1y! , 1111+
|1 X|11?
201
(84)
where a1
0 is constant. Combining Eq.
883
with Eq.
84
can obtain that,
1p
},(1%
1 (x).(00) v T (M)) 1/+1
P'
++1
xz 1 + ||
||
X|11?
11 - ~11
2
(85)
Then, we focus on the (16) in Eq. expressed as follows,
82
According to Cauchy-Schward inequality, (16) can be
( ((. ".(00 wft (+1)
20g |
(86)
where 02 0 is a constant. Next, we focus on the (1c) Eq. 82 Defining Lí' L + +
according to Assumption and the trigonometric inequality, Vdr. we have,
= http::/fhhhh.p..................
< +
< -
(87)
Following from Eq. 87) and the strong coneavity of [(((a)))uu)),, wen X Nes-
terov 2003 Xu et al. 2020), we can obtain that,
V (p of 1.
a 'n's || - T
(88)
In addition, the following inequality can be obtained,
- -1)
+1
X|I22
|0
++
112
+
1 11
111
(89)
2x
2nx
23

---

Published as a conference paper at ICLR 2023
Combining Eq.
88
(82 (85
(86).
(88)
889
I
and setting 02 7/ have:
L1 L
Lp((2)
(+1
J,ly, 1,0t1 (((+))1(0))
Lp
J.(y J, 1 (A.).(0
1
N
(1|00)
++1
- 2311 +
-|
201
+(2
--1-c 2
4-1 Σ 11--119-112119)
+ 24a
1
P
Σ
| 1 111
2mx
(90)
According to Eq.
20 in (t + 1)th iteration, 40 E θ it follows that,
0 0 - no V (f ",("/('),""" , 2+ A(1 ((*+*).)0))) }.(0()), 0 0-000-0000 0-0,+)) = 0. (91)
Choosing = -O, we can obtain,
1 _ =0, 00) 0 =0.
, (,,,)((*1 Vo. In(aat )ol(tt)) "x ", ,,t't
(92)
110
Likewise, in h iteration, we have,
(vo. (o
(0) 1) 0,+1 0 = =0.
(93)
Since I. [,,((a)), (1) is concave with respect to 0, and follows from Eq. 933
(1
1 (,(00)))))))))))))) - (b( 1,ott 2111 , ),((
Vo, Lp Lo
4 2411 (,,10))))))
(Vo, T
1 14 + Vo.
",. 0!)
+ + (0) 0: 0 0)))
(94)
Denoting 1 0 0 (0) 1 have that,
Σ Vo, ((
hthp::/:"hhhh......////////////1 0,, -0))
Vo. Lp(
1+1 h:0,::/:h1.....00..ddeheh0a44411 0. -0:)(a)) (2a)
(26)
1), 0 (2c).
(95)
We firstly focus on the (2a) in Eq. 955. we can write the (2a) as
Vo, ((
(x(+1), ).)))) Vo. (f - 0.)
= <VVo. [pp((p 1+1
(2 +1 (()
0, 0!)
-o 2
(110 +1 111- - -ي- 0 (((12)
(96)
24

---

Published as a conference paper at ICLR 2023
And combining the Cauchy-Schwve Schwarz inequality with Assumption 1, we can obtain,
oV, Lp((a; bu
),
, [(++1 -o,
((N)) 0 0!)
= (Vo. (f((
3.10% + =+1 -00 (1,,, 0 01)
L
211 1lo| y/ +||l))+||=*+11--
2 0 1!.
203
(97)
where a3 > 0 is a constant. Thus, we can get the upper bound of (2a) by combining Eq. 96 with Eq. 997). that is,
Vo. Ip (f=
1+1 1,0
.12 1 1
(
Vo.
(2]). 0. 01)
122 2ay
(1|00 x +1y 1lyl - (| 11)+ 1
ic 1
-c
(110,
1 00113
و -عا -ي 1
(98)
Next we focus on the (2b) in Eq.
95
According to Cauchy-Schwarr inequality we can write (26)
as,
M
22 (A1..0))-- "1,,::,00000.....,,00000..).11") eft1)
Ve ba 2. 1)>
204 || 11
(99)
where a₁ > 0 is a constant. Then, we focus on the (2c) in Eq. (5)). Defining L L + cg.
according to Assumption I and the trigonometric inequality, we have,
1| T. ( (ui),o", of (() (1) (M),))
(100)
S - "1.
Following Eq. 1100 and the strong concavity of [[,(( w.r. O,, the upper bound of (2c) can be obtained, that is,
Vo..T(((a)) (tt.::.))......))).... (e11,109---
Vo, (1110:11hhheee.11.000000000dddd1 (1, !))1
L'
d Tz' 10 1123)
(101)
In addition, the following inequality can also be obtained,
N
0 -0:-0:11
0,, 01)
<
10
0:1
1
1|
+ 2no 10 -1-11
1
2no
2nd
(102)
Combining Eq.
94.
94
955
188)
199
(01). 102
22 < L Lo-
and setting as = 110, we have,
1+1 Lp((x)
2+1
1++ 1.10
})- LP (1 3.13%
11.. },2r 11 1 ).())))
10
N (1|a +1
==11 + l10
++ wf(l + ||
20g
Ca +(
cl
N
10001
0
S
Σ
N
110
전ニヒ Σ
10 -111
2
2010
(103)
25

---

Published as a conference paper at ICLR 2023
By combining Lemma 1 with Eq.
(90)
and Eq.
(103)
we conclude the proof of Lemma
Lemma 3 Firstly, we denote 5
S and F
as,
8/+1=
4
Pl
|
-1112
4 1-1
IP
|
11?
(104)
77A
c1
++1
7A
ci
i=1
1=1
$211
4
|10 0/11
2
1-1
-1
Σ
NV
110
110++111
(105)
110
C2
==1
F+t
Ip
++1 1, (3
,, ++
h+t1, [(1 }: 10
[x|11]
51+1
+ S
IP'
|P'|
N
N
7
Σ
|
x|12
si
Σ || |
7
Σ
1
+1
0
11.
2nA
2no
(106)
Defining 05 = max
1,2, 11,1+
NT.2, 14 2 Tú, we have,
Ft
( L-a
DA
1 2
no o
++1 22
8/P' 22
8NZ2
|| 1+1 - -
2/
2
(e(c))²
+( Ltas
1
nA
IP'
20
8P
8N1.2
| 4+1 u111
2
1/
v(cc))²
1=1
+ L+os
2
1
+
11
1P'
Mol L2
8'''/2"
SNT.2
4+1
(107)
Ltos
1
n1
p
L2
1
8P''L"
SNL
|| 2012
2/
no (c)))
pp'
0111+ $ -- DD'
6r N
Σ
||
2111
1
Σ
|10
Σ ||
10yA
2
10ne
N
N
110
1|+
|
Σ 10111
7o
Proof of Lemma
1 Let 01
and substitute them into the Lemma 2 1I 2 Ti, we have,
7 0g
no
Lp (((( 2 1,(3
(zx
1.10 +1
1)
- L,
(( 0" 2'(1
< [+
1 p 1r.
to
1
|=f11_xf11
+(
[+1
1
+
1 +oo
N
++ 12
2 m
p
+(
1 P
L2
+no
2 123 || - 0+112+ 2nd
|| X1
1111
2
(108)
+(
L+6TKy N
tno
1 |1. ||| ++| -241 21 2710
100 0 |12
2
V/
2
|P'
+
(rkk NL
-111
+
-
10 0 |
ax
7/0
N Σ
Σ (1
112-1111111)1
According to Eq. 19 in (t + 1hth iteration, it follows that:
(x
(>s - x - J/ VA,
),0t! 1 (A)).(O)) ( --x-"))= =0. (109)
Similar to Eq.
109p. in th iteration, we have,
-x- 1-1 nA Ip "0 1.00 (1)0-)))) -x²) =0 (110)
26

---

Published as a conference paper at ICLR 2023
Thus, Vt 2 Tı, by combining Eq. (109) with Eq. (110) we can obtain that,
ttt1 , x1t
1x
(v (taat +orl(++)),0 } (
(111)
Since we have that,
TA ( 1
1 14)
24p 1
MII
|0
- 11 113 (112)
27
it follows from Eq.
and
Eq. 112 that,
2ny || +1
-
X11
|
knd | X; 11-
2mpa
12
Σ (11,:+1=::1
N
+1
= + 1 y [13) + -0 -1-1)11-11 + 11//+1->111 -x11?
26
of
ei
(| -
- 2113
Vx, Epp(
Vn. (X
+ |oftt11
2
V (at http::/.ww.....kk......aaa/.aaaa M 11(00-11--1 1)122
-
(113)
where bf > 0. According to the setting that of I L1', we have of L, "n'to] T 1
5. ',,"
2 2
2L,'
Multiplying both sides of Eq. 113 by W
we have,
11
1112
||{
112
m 2c
72
|
x111112
||
4b Tン
|1
|
x112
7 -
ci
(114)
N
4r
Σ
++1
+
||y!
++1
y ||
-0
- 11))
Setting 1f = si 2
in Eq. 114) and using the definition of St. V1 2 Ti, we have,
1t+1_ St
P'1
P'
1 2 +
Σ
2
+
4 (
c 111+++1+111/// 21112
71
c
nx² 2441
N
- -
Σ (1)
(110
+1 -0 + 1 +1 - 13)) + +||))+||+++++)) - -1112+1122+ - -2- -11)))
.
1=1
(115)
27

---

Published as a conference paper at ICLR 2023
Similarly, according Eq.
20 it follows that,
21 1+1 0 0:
Vo (1 +1 ). w h10.4//44.444414.....4.000044111 ()-0))00000111111
(Vo, (1
/ [,1.444.00000.100000.00000000111 01
{ 11 0
Vo. ||0
(116)
In addition, since
1 1+1 0,+1 0:) 20p
222
10
01112+ + 20ee
|| 113
2njo
1
0 -0--0- 0 011
(117)
it follows that,
11
27p |
+ ||2
-
0 0 1|2
2mp
2np
265 (110g ar!11
1.
|1
y 12) 0 11 - 1/11 1 +1 [ 11-1(11100 2" 2/1
6
10 0|11
2
+
5-
(110) +1 1 - (2) -
0
Istch 1 0 1112 +
++1 1|2
2
20o
Vo. I, (11)
(1)
Vo.
2/, (1)),10-11)11
V L,p
-x)( Vo. I, [, (A1) ",0"0,000000,,""00000000000000""
(118)
According to the setting of < L2', we have
L2' T <
L/' c 5 5
-. Multiplying
21.2"
both sides of Eq.
118 by mor
have,
100
+1
011
1
10
c2
1
0 11-1
|||0
46h .
1
11 no 1110 0 1
(119)
ne
AL
- 211
+ || ++
+1)
021 1| || - xz 11112).
Setting b/
in Eq. (119) and utilizing the definition of S3, we have that, 2
5 -S
S
2-2
| 2+
Σ
(
1 1
011
62
Ne
0/2
c/
N
110 ne
4
0
-
(1|a
4+1
201112
w 1 -01 221
no
(120)
Based on the setting of of and cb obtain that 3A
2
T
2
Defining as max(1, 1 122 NT2) Combining the definition of F++1 with Eq. 115 and
28

---

Published as a conference paper at ICLR 2023
Eq.
120
Vt
T1, can obtain that,
F++
F
( L 2
DA
1.2
7o
201
8NZ2 (c
TIM
++1 x
1/2
2
mx
+(
Ltas
1
+
7A
|P
+
90
4 1
+
8/
18 1+1 U111
1/
n)(e))²
no (c())))
+(
Loos
2
1
+
La
Tol
+1
22
8/P'
(c))))
SNL
++1
001
(121)
Lt
1
P
L23
L
8P
S2
)|
11
2
m/
2
male)) )a
No (c²))
Ip'
(P'
6rk NZ
Σ
|
1112
1ome Σ
110
01112 --i-ct
Σ
||
10yx
2
p
N
10
1|
4
4 | 1
10111
2
of
which concludes the proof of Lemma 3.
Proof of Theorem 1: First, we set that,
4/P' (7- 22) nx(c1)2 + 4N -N(Y-2)L2
+ no(NN - 1 (0++11))
45
dg where constant y satisfies that 7 > 2 and 2/1-2)1² 4N(y-2)L*
(122)
(c()))
2
2
ag 2
thus have that of 0, VI.
n) na(c
nolch)
According to the setting of n/a nyy n n/ and c.. cb. we have,
L L+aG
1
11
PP'
L2
70 O ++1 L2
8P''
L2
SNL2
d
(123)
2
2
2
(T(2))
M
no (c))²
L+a5
45
JA
P
L
1/0
L
P/2' L2
8NL2
-a6.
(124)
2
ml
2
2
[M(c))²
ne (c²)²
L L+a0
1
11X
P
L
n1
Q --1
LL
8|P'|L2
8NL2
dg.
(125)
2
7/6
2
2
(x(2
no
(ct)
L+00
1
7X
P
L
No
+
8/P'|L2
8NL
2
1/2
2
2
no (c²)²²
ag.
(126)
Combining Eq.
123).
(14),
125
126
with Lemma 3
11 2 Ti. we can obtain that,
06
(1|
(1|a
1+1
+
11 ++1
11(l²) + 11 - v011 + || - 20112
-
P' Σ
N
1
6rk N
|
- 1
10nu Σ
110 0
10yx
2
(127)
N Σ
<
F
pt+1 +
||
110
N
110 2
Utilizing the definition (VG*) )r and combining it with trigonometric inequality, Cauchy-Schwarl inequality and Assumption and 2, we can obtain that,
pt 1
II(V )m.
11 < 2 - +66 -1 11 || e+1
-2-11=
(128)
29

---

Published as a conference paper at ICLR 2023
Utilizing the definition of (VG'), y,, and combining it with trigonometric inequality and Cauchy- Schwarz inequality, follows that,
P'' - +6 (1 (10 = 11 + 11
(129)
$ nu= 1l
Utilizing the definition of (VG"), )n and combining it with trigonometric inequality and Cauchy- Schwarz inequality, have that,
|K
(11= x bfll))+ no= 1221110 || - 00113.
(130)
Using the definition of (VG*)= and combining with trigonometric inequlll and Cauchy-Schward inequality, it follows that,
I((V')=11<211
Σ E(1a 20112+ +1112+11x++ y11l3) +/ll3)+||o+t1 - -0113 11 2 2=112.
(131)
Using the definition of (VG*), )x2 and combining it with trigonometric inequality and Cauchy- Schwarz inequality, we can obtain the following inequality,
|I 3.
|1
-111 + 3(( (2))3)111
+3I2
Σ (1
(+1 ot 12 | +1 utll +1 - - =21
(132)
Combining the definition of (VG*), )e with Cauchy-Schward incquality and Assumption 2, we have,
[(VV Je.11
< 3 n00 0 2-3.2
Σ (| - 12 11++ |1
N
y 13) -0(12) +3(2--1-4- 10:12
1 1 +3322
Σ (1|æ -x +1 - -
1=1
+3L2rki (1/o 12 -
1
Σ || -11)) + -
(133)
In sight of the Definition B.2 as well as Eq. obtain that,
128
129
130
131
132
and Eq.
133
we can
18812
P II(V)*)
_, 12- |2+1((0²* |1
5 Tm
+3NT.2
|| - 2 +( 1 +3N1.2
Σ - 21
+(4+3/p L2)
||
x 12 (4+3/
||01 v?
N+3
11
00
12.++155 N - 133111
11-
p
133+157k, NL > -1,1+++
Σ 3((c) 3((c)-1)2 (1)13)111112
1=1
-1100 0 0 3((5 01
( 11000111
-
(134)
30

---

Published as a conference paper at ICLR 2023
Let constant ag denote the lower bound of ag (ag > 0), and we set constants d1, d2, d3. da that,
di 2k T + (4+3M -T
+ To
24+33 +3k, T (N),,N
(135)
11 2 p(s))
1/1= (na))
d2 = 2k, T+ (4+3M + 3K, TNN)
( +3k, (UG,,,NN.E TN) 2
2
(136)
"y 2as)) )
"y (ag)²
d3 2+ (2+15k 43MM) 2
N 11) 11
(137)
no (
770 (a)))
d4 2+ 2+(T1, 1 m 2
2 + P 1
(138)
17 2ap))))
7== (ap))
where hir is a positive constant. Thus, combining Eq. we can obtain,
134 with Eq. 135
Eq. 136)..
137
138
>> -
+ ==1
Σ do(a
3 $10 1+1 - yf
=1
N
+da(a))2|1 - 0'112+da(a5 || - 21112+
Σ
3
110, - -
1=1 no=
p'
PDj
+1 ( 1111++ Σ (( (((1-1122 -2 11121111111
mx²
1=1
(139)
N
Σ 3(1c 1 1/2 - (c ()))))) 0 1 + 2 +3N 22)
Σ || - =1
2hrT +3k 3kTTN12
| m || + ( To=
- 3NT22
Σ | 2112
The
2krT NI2)
y9 (+1 y112
Let dřg denote a nonnegative sequence, i.e., d²
1100gT41NN We
(ix d20f, dang, 1-300 PKLNE
denote the upper and lower bound of d as dz and ds. respectively. And we set the constant k 2 +3NI.) def بي +3N13),
satisfies hn 2 max dal +3NL2) dg प +3N12) }. where The and Fy are the upper bounds of n
and My respectively. We can obtain the following inequality by combining Eq. (39) with the definition of dz.
N a6
Σ
(11
(+1
x
P+|lyt* +1 - y/ + 1/ - [|/++=ll+/+111 22
1=1
IP'|
6rk 2
|| | 111l + 10r Σ 110, :5 - -0,112
107a
N Σ 3d3 (1c2- -1p2 (c/ (cb-11)))) 1
+ Σ
3d3 (cc)
-c) +
+ +ell( ( -2x +3N12)
|| - 1 dy ( 2 +3k NL2)
| =
+ob6( 2 +3N
|| 2112 dg
2h + m
|10 ++1 1/2
(140)
31

---

Published as a conference paper at ICLR 2023
Combining the definition of d3 with Eq. 127 and according the setting |||i|| 0z, 100:11 S a1 and dg 2 d3 ds. Vt 2 Tı, thus, have,
d' V
S F -
pu+1 +
-c- May + 2/2 --- Nos + 7/
A s Ma3
2
2
of
+ 90
2
Nay + (c'
(c- 12 (c)))) + 3dg Σ
102 (C 13))a
N
N
(141)
1
10
01112
1
Σ
0 1+1 1
10700
10me
iM
+ do n/2"
||
x
ds (2hrr + 3k, NL2)
|
x
+ t
2 3NI.2 "10
|
y
1
de 2hhF + 3k NI.))
10
v11
Denoting (c) as l | 1 S 4. 2 2}. Summing up Eq. (41 from t = =
to (e),, we have,
F(+ Σ d:ll V/ 1=
$ FT1+2_
L +
4
[ 1) + 2 Ma3 + 27
S
Maz² + 3d)
1)
N T++(())
+ 2 o
+ + ) +
o
Na
+ I No,2 + Σ Σ 3dg ((c) 1---- 1/2 (c 1))
(c
of
2
2no
i=1 t=Ti+2
22 + - Mag² 2 + 2
+1
T T+) N
Ti Te-T(e) N
Na.² 2
+ Iorne
Σ
Σ
1 vr
1 Ione Σ
Σ 110, 1+1 - -111
|=1++2 1=1
2 F=1
Ti+ T++ N
T+) N
+ds( 2, + +3NL²
Σ
Σ
|
-0/1²
ds
2 Te
Σ
Σ
| 1 2
me
t=
1= +2
N
(c) N
+ 2 + 3NT.2
Σ
2k. ds y 11122
Σ
1
1=1 +2 i=1
[=
(142)
where d3 max - A2 |. max
f (1 -62 and L=
min (
)oo (M))))))
which satisfy that, 11 2 T 2
Fet > L
c
Mag
4 1
Nou
7 Mog²
7
No
G
Ti+2
Mog²
2
_
T+t2
No. 2 (143)
1/2
c
110
2
211x
2110
2
2
For each worker i, we have that T, - f S r, thus,
T T+)
Σ 3ds ( 111 - (0 -112)ass
1
(d 1.100-133 - -(-2 (cb
ST
Σ
(144)
(())))(())) 21+2500)54++10))
< (r)
Since the idle workers do not update their variables in each master iteration, for any t &that satisfies
رx -) 1) < t (x()), we have 0 0 00 And for & VT(T), we have ||0 0 0.
32

---

Published as a conference paper at ICLR 2023
Combining with 0,(5) - ( 1) S
obtain that,
T(()() N Σ Σ - +
0:113
Σ
10.00)
00:15)-11
((
Ti ++
T T (+) N
((e)+r-1 N
Σ
Σ
0 ++
11 7 Σ
Σ
0 1+1 0:
(145)
1
[c)++
Ti (e) N
ST
Σ Σ
0
r+ 0111
+ 4T 1)Nas.
+2+==
Similarly, for any that satisfies ú ()(j-)) 1) < 1 < (,()) we have σ - x (100)- - 8,66)1 And
fort & (T).,, we have ||х] x 1|2 0. /1 y -11 Combining with 0.(1) - 11) s we can get that,
Ti (() Σ -
E
b.(5)
x;
6.(5)-1
(T(O). T ++3550
T (+)) N
+(6)+T-1 N Σ
7 Σ
Σ
x
11
Σ
x
x011
(146)
t= [=
(=f(e))1 i=1
T: (+)) N
S T Σ Σ
[+1
x 112 + 4 Na
1= 1= +2+=l
T T(+ N
Σ Σ 1l
Σ
616) 9,00) 112
y
t= t= +2
350:()
+(ee Σ Σ
+())+r-1 N
y
1+
12 +T Σ
Σ 11 ++1 -
(147)
1=11i
t= (())
T+()( N
S Σ
Σ
1yt + w111 + (T)
[=T: +2
follows from Eq.
142
144),
145
146 that,
T T++
Σ dg
1
t=T++2
< pfi+2
I, + -/2 ( + - Ma3 + S Mag 2n1 Mo3² + (d5(ct) Ma3
+ N/ 1 + $ No, + No + 2n1 NNo²² 2 + 3rd (c))( + - Moz² 2 + - No
T1
+(
2Nas + 4ds 3N 1-3N2 + ddol - + 3NN
5no
-1)
(148)
where d and kig are constants. Constant dg is given by.
dg = max(d1, d2, dy. da, + + NL
30r neac
(1- NL
2 max (di, d2, dg, d4,
30 Tk NL2
307
(149)
Thy goon
33

---

Published as a conference paper at ICLR 2023
Thus, obtain that,
(()) 1
T3 T(e)
T++{(()
Σ
IVG
<
Σ
10 <
Σ
V=VVv < thttaT( 1).
doag
1=
1
1=2+22
(150)
And it follows from Eq. 150 that,
(d dd+kar(T - 1))de
(151)
T+)
Σ %
According to the setting of ci, cz we have,
1
2
(152)
dg 4(7 - (M + Nne) (t + 1) no(N-8)L2
2
Summing up %
from t = Ti 2 + T()), it follows that,
Tc) Σ
Ti Ti+T(c)
2
Σ
t=i++2 (M 1) 20(N-8)64
1=
(()
Σ
(153)
t= Ti +2 4(7 [17=2))
uoiN 8962 (141)
(T (T+)(()) +2)
4(- 2 NNo 2o1N-800 8122
The second inequality in Eq.
153 is due to that Vt 2 Ti + 2, we have,
No Ne N
(MA NNo) No 1t+1))
2
(154)
Te+f(e)
Σ 2 -
The last inequality in Eq. (153) follows from the fact that
1=11+ (1+1)
Thus, plugging Eq. 153 into Eq.
151
obtain:
1 (d +ktTT(( 1))d
(4(7-2)L + NNo) + Jo To(N
(d +hat (T 1))de
2
T, (e)
(7i + 7()) (7, 2)
Σ 1
tm T1+2
(155)
Let constant d, =(7 - (M + Nne), and according to the definition of T(c), we have:
-)( Ti T() > A(d7 + 2
(d + HhaT(T - 1))ds (Ti + 2
(156)
Combining the definition of VG and V with trigonometric inequality, we then get:
VG VG
V0ll
Σ |
M + Σ c 11.
(157)
34

---

Published as a conference paper at ICLR 2023
Table 2: Step-sizes of all variables in the experiments.
Datasets
T
f/y
T/o
7
1)0
MNIST
0.001
0.02
0.001
0.02
0.1
0.001
Fashion MNIST
0.001
0.02
0.001
0.02
0.1
0.001
CIFAR-10
0.001
0.02
0.001
0.02
0.1
0.001
Covertype
0.01
0.02
0.01
0.02
0.1
0.01
IICNNI
0.01
0.005
0.01
0.005
0.1
0.01
Australian
0.001
0.02
0.001
0.02
5
0.001
P
N Mll2
If 2 ( (4Mpa 4No4 )a 22, then we have
Σ
|c
Σ
1eb-10:11
Vi
Combining
2
with Eq. 156 we can conclude that there exists a
T(e)~O(max( 4Ma3 4Na1, 1
A(d7 Bo(N S)
(d +kar(T - 1))de
+ (Ti + 2)²)
n)²
(158)
such that ||V S which concludes our proof.
C PROOF OF THEOREM 1
Assuming that there are cutting planes added every k iteration, i.e.
po 2 pk ... pnnk.
(159)
Let R* denote the feasible region of problem in Eq.
12 in hth iteration, and let R' denote the
feasible region of problem Eq. TO). we have that,
R P2R 2 ... R. 2 R'.
(160)
Let F((x("), (y.*), b0 kmr) denote the optimal objective value of the problem in Eq. 12 in kth iteration and let F* denote the optimal objective value of the problem in Eq. (10.. According to Eq. 1600, we have that,
F((xf*) (.vl"" 3,000 200))=)=))))0)0)) F((x) "( J.(."") 2tt)) S.(o)
(161)
And we can obtain that,
F F((a!! 0e (.())) 00 200) 2 F(w (y ju kxa) 2...
F F F( ku wunk vkka
2 2.8.
(162)
is from Eq. 162 that the sequence F(( (. 1 is monotonically non-
increasing, When nk + oc, the optimal objective value of the problem in Eq. converges (8 1).
12
monotonically
35

---

Published as a conference paper at ICLR 2023
D DETAILS OF EXPERIMENTS
D.1 ADDITIONAL RESULTS
In this section, additional experiment results on CIFAR-10 Krizhevsky al. 2009) and Australian Quinlan 1987) datasets are reported in Figure 11 and Figure 12 It is seen from Figure and Figure that the proposed ADBO also achieves faster convergence rate.
D.2 DETAILS OF EXPERIMENTS
In this section, provide more details of the experimental setup in this work. In data hyper-cleaning task, experiments are carried out on MNIST, Fashion MNIST and CIFAR-10 datasets. Following (Ji al. 2021), we utilize the same model in data-hypercleaning task for MNIST, Fashion MNIST and CIFAR-I0 datasets, and SGD optimizer is utilized, And the step-sizes are summarized in Table
2 In MNIST and Fashion MNIST datasets, we set N 18, S 9, T 15. And in CIFAR-10 dataset, we set N 18, S 9. T = 5. We set that the (communication computation) delays of each worker obey log- normal distribution LN(3.5, 1).
In regularization coefficient optimization task, experiments are carried out on Covertype, UCNNI and Australian datasets. Following (Chen et al. [022a], we utilize the same logistic regression model, and SGD optimizer is used. And the step-sizes are summarized in Table 2 In Covertype dataset, we set N = 18, S 9, T = 15; IJCNNI dataset, we set and in Australian dataset, we set N = 4, S = 2, T 5. In the experiments that consider straggler problems, three stragglers are set in the distributed system, and the mean of (communication computation) delay of stragglers is four times the delay of normal workers.
24, = 12, r = 15;
2.6
ADBO
accuracy
2.4
SD6D
0.3
test lo55
FEDNEST
2.2
0.2
ADBO
2.0
SDBO
FEDNEST
1.8
200
400
600
800
0
200
400
600
80D
time
time (s)
(a) test accuracy vs time
(b) test loss vs time
Figure 11: (a) Test accuracy vs time and (b) Test loss vs time on CIFAR-10 dataset on distributed data hyper-cleaning task.
0.9
ADBO SDBD
0.8
0.8
test loss
FEDNEST
0.7
0.6
Lest
SDBO FEDNEST
0.4
50
100
150
200
0
50
100
150
200
time (s)
time
(a) test accuracy vs time
(b) test loss vs time
Figure 12: (a) Test accuracy vs time and (b) Test loss vs time on Australian dataset on distributed regularization coefficient optimization task.
Codes are available http:///gggthhoooocc//////emmmms
36

---

Published as a conference paper at ICLR 2023
E PARAMETER SERVER ARCHITECTURE
In this section, we give the illustration of the parameter server architecture, which is shown in Figure 13 In parameter server architecture, the communication is centralized around a of master nodes (or servers) that constitute the hubs of a star network, and worker nodes (or clients) pull the shared parameters from and send their updates the master nodes.
Masters (or Servers)
variables: v,4
Communication
Workers (or Clients)
Local
Local variables:
Local Data
Figure The illustration parameter server architecture.
37


Reviews:
[{"review_id": "mH57OFy-vSH", "reviewer": "Reviewer_KFzJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an algorithm that solves bilevel optimization problem in an asynchronous distributed manner. The iteration complexity for the algorithm to obtain $\\epsilon$-stationary point is upper bounded by $\\mathcal{O}(\\frac{1}{\\epsilon^2})$. Empirical results show that under asynchronous setting, the proposed algorithm outperforms state-of-art distributed bilevel optimization algorithm. ", "summary_of_the_review": "I think this paper is marginally below the acceptance threshold. Please see the weakness part for my reasoning. I think the authors need to revise the written to make the problem formulation/algorithm more neat and easier to follow.", "strength_and_weaknesses": "Strength:\n1. Strong empirical results with theoretical analysis\n\nWeakness:\n1. Redundant formulation compare to other bilevel paper, which makes it hard to read, especially when explaining how cutting plane works.\n2. Insufficient references. There are works on asynchronous distributed optimization that are not included in this paper. For example, https://ieeexplore.ieee.org/ielaam/6884276/8350883/7903733-aam.pdf. There are also many works asynchronous federated learning, and probably needed to be included here.\n3.  What is the value of $\\tau$ in the experiment?\n4. In the appendix, I don't quite follow the logic from eqn 57 to eqn 58. Can you please explain more?\n5. I don't understand from optimization perspective, why this algorithm can outperform other algorithms in asynchronous setting. From Theorem 2, the larger $S$ is, then the less number of iterations is needed. For experiment, what if you run other synchronous algorithms (e.g. SDBO) in the same setting of ADBO, i.e. that the master problem will update its variable once it receives updates from $S$ workers. Will ADBO still outperform SDBO? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "GSqTmE8cYN", "reviewer": "Reviewer_4Y6m", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed an asynchronous method for distributed bilevel optimization. The proposed method can tackle both nonconvex upper-level and lower-level objective functions. Convergence analysis has been provided.", "summary_of_the_review": "The paper proposed an interesting method. But I would appreciate it if the authors could address my above concerns.", "strength_and_weaknesses": "Strengths:\n1. The proposed method is clearly explained and theoretically analyzed. \n2. Experiments have some promising results.\n\nWeaknesses\n1. The reason for asynchrony should be better explained, possibly with some real-world use cases. Actually, it has been observed that asynchrony may not be the best choice in distributed training, because it uses out-of-date (i.e., stale) gradients to update models. This staleness often results in degraded performance. Therefore, several state-of-the-art methods still use synchronous methods to achieve strong empirical performance, with some simple tricks such as large batch size, warmup, layerwise adaptive learning rates, and gradient compression (see reference [1-5] from below). I think this tradeoff between synchrony and asynchrony should be properly discussed.\n2. Following the first point, the authors is encouraged to consider how to resolve the staleness issue due to asynchrony. This could further enhance this paper.\n3. The experiments are conducted on two applications of bi-level optimization: hyper-cleaning and regularization coefficients optimization. I think bi-level optimization has received great attention these days mainly because of some emerging applications such as meta-learning, neural architecture search and etc. The authors are encouraged to consider these applications (e.g., meta-learning, neural architecture search) in the experiments.  \n\nReference:     \n[1] Goyal, Priya, et al. \"Accurate, large minibatch sgd: Training imagenet in 1 hour.\" arXiv preprint arXiv:1706.02677 (2017).   \n[2] You, Yang, et al. \"Large batch optimization for deep learning: Training bert in 76 minutes.\" arXiv preprint arXiv:1904.00962 (2019).   \n[3] Huo, Zhouyuan, Bin Gu, and Heng Huang. \"Large batch optimization for deep learning using new complete layer-wise adaptive rate scaling.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 9. 2021.    \n[4] Liu, Rui, and Barzan Mozafari. \"Communication-efficient Distributed Learning for Large Batch Optimization.\" International Conference on Machine Learning. PMLR, 2022.    \n[5] Wang, Tong, et al. \"Large Batch Optimization for Object Detection: Training COCO in 12 minutes.\" European Conference on Computer Vision. Springer, Cham, 2020.    ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2EtGsYB6eo", "reviewer": "Reviewer_9ja2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Bilevel optimization problems, in which one optimization problem is nested within another, occur in multiple machine learning applications such as hyperparameter optimization. The paper considers a generic distributed bilevel optimization problem and proposes a novel asynchronous distributed algorithm. The proposed algorithm is guaranteed to converge to an \\eps-stationary point in O(1\\eps^2) iterations in a distributed setting. ", "summary_of_the_review": "Overall, the paper tackles an interesting problem and the proposed algorithm is novel and provides the first general framework for solving distributed bilevel optimization problems in an asynchronous setting. The empirical analysis, while limited, also shows promising results.", "strength_and_weaknesses": "Strengths:\n+ The paper addresses a timely problem and provides a novel algorithm.\n+ It’s interesting that the centralized version of the same algorithm also yields the optimal convergence rate in the centralized setting.\n\nWeaknesses:\n- The paper is a bit dense and I feel that the presentation could be improved significantly. Currently section 3 serves as a large unbroken block of equations, and readability would be improved if it were broken down further. For instance, divide the main algorithm into phases and describe the steps to estimate \\phi(v) [Equations 5-9] and the steps to describe and generate the cutting planes separately. Even the paragraph on page 2 regarding the reformulation as a consensus problem feels out of place there - I would much rather see it at the beginning of section 3.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster