Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks
Authors: Shuoguang Yang
Xuezhou Zhang
Mengdi Wang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Decentralized Optimization
Federated Learning
Bilevel Optimization
Compositional Optimization

Abstract: Bilevel optimization have gained growing interests, with numerous applications found in meta learning, minimax games, reinforcement learning, and nested composition optimization. 
This paper studies the problem of decentralized distributed bilevel optimization over a network where agents can only communicate with neighbors, and gives examples from multi-task, multi-agent learning and federated learning.
In this paper, we propose a gossip-based distributed bilevel learning algorithm that allows networked agents to solve both the inner and outer optimization problems in a single timescale and share information through network propagation. We show that our algorithm enjoys the $\mathcal{O}(\frac{1}{K \epsilon^2})$ per-agent sample complexity for general nonconvex bilevel optimization and $\mathcal{O}(\frac{1}{K \epsilon})$ for Polyak-Łojasiewicz objective, achieving a speedup that scales linearly with the network size $K$. The sample complexities are optimal in both $\epsilon$ and $K$.
We test our algorithm on the examples of hyperparameter tuning and decentralized reinforcement learning. Simulated experiments confirmed that our algorithm achieves the state-of-the-art training efficiency and test accuracy.

Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks
Shuoguang Yang IEDA, HKUST yangsgBust. .hk
Xuezhou Zhang Princeton University x273929princeton.co edu
Mengdi Wang Princeton University
mengdhv@princeton..co
Abstract
Bilevel optimization have gained growing interests, with numerous applications being found in meta learning, minimax games, reinforcement learning, and nested composition optimization. This paper studies the problem of decentralized dis- tributed stochastic bilevel optimization
a network where each agent can only communicate with its neighbors, and gives examples from multi-task, multi-agen learning and federated learning. In this paper, we propose gossip-based decen- tralized bilevel learning algorithm that allows networked agents to solve both the inner and outer optimization problems in a single timescale and share information through network propagation. We show that our algorithm enjoys the O 1
Ke per-
agent sample complexity for general nonconvex bilevel optimization and O k. for Polyak-L.ojasiewicz objectives, achieving speedup that scales linearly with the network size K. The sample complexities optimal in both and K. We test our algorithm on the examples of hyperparameter tuning and decentralized rein- forcement learning. Simulated experiments confirmed that algorithm achieves the state-of-the -hrtt--rrt training efficiency and test accuracy.
Introduction
In recent years, stochastic bilevel optimization (SBO) has attracted increasing attention from the machine learning community. It has been found to provide favorable solutions to variety of problems, such meta learning and hyperparameter optimization (Franceschi al., 2018: Snell et al., 2017; Bertinetto et al., 2018), composition optimization (Wang and Liu, 2016), two-player games (Von Stackelberg and Von, 1952), reinforcement learning and imitation learning (Arora al., 2020; Hong al., 2020). While the majority of the above mentioned work focuses on algorithm designs in the classic centralized setting, such problems often arise in distributed/fedderated applications, where agents are unwilling to share data but rather perform local updates and communicate with neighbors. Theories and algorithms for distributed stochastic bilevel optimization are less developed.
Consider the decentralized learning setting where the data are distributed over agents K. 21, ,K} over communication network. Each agent can only communicate with its neighbors over the network. One example is federated learning which is often concerned with single-server- multi-user system, where agents communicate with central server to solve task cooperatively (Lan and Zhou, 2018; Ge et al., 2018). Another example is the sensor network, where sensors are fully decentralized and can only communicate with nearby neighbors (Taj and Cavallaro, 2011).
We consider the following decentralized stochastic bilevel optimization (DSBO) problem,
ManN(a)) s.t. y²(x) argmin yERdy
min F(x)
g (z, v)
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Agert
Agprt
Cemball Sorver
Agent
Ageri
Single-Server-Muuee Sulleee-Mll--ggent Network
Decentralzzed Network
Figure 1: Illustration of Distributed Network Structures. In centralized network, the agents may cooperate to solve specific task by communicating with the central server, commonly seen in federated learning.
where f²( = [f yı [²)] and (x, Eg (z, yı 5h may vary between agents. The expectations Eg++ [o] and [e] are taken with respect the random variables ç* and gh, with heterogeneous distributions across agents. We consider the scenario where each (x. is strongly convex in y. We the notation F* gin F(x), f(x, EMEK (*, v). and g(x, y) t Ekek (x, y) for convenience.
1.1 Example applications SBO
SBO was first employed to formulate the resource allocation problem (Bracken and McGill, 1973) and has since found its applications many classic operations research settings (Cramer et al., 1994;
fifieszczanski-Sobbiee
and Haftka, 1997; Livne, 1999; Tu et al., 2020; Tu, 2021), and more recently
in machine learning problems (Franceschi al., 2018; Snell et al., 2017: Bertinetto et al., 2018;
Wang and Liu, 2016). In particular, we introduce two applications that have recently attracted lot of attention, namely hyperparameter optimization and compositional optimization.
Hyperparameter Optimization takes the following form:
The problem of ryper-parameter tuning (Okuno al., 2021) often
Σ (())()))) s.t. y" (x(x) E argmin LE
Σ ( R(I, R(Z,)) JED
min ZERU RER
(2)
yER
where Dirin and Drat are two datasets used for training and validation, respectively, Rd is vector unknown parameters to optimize, (v() a convex loss over data i, and x E IRd a vector of byper-parameters for strongly convex regularizer R(x, y). For any typer-parameter æ E gd the inner-level problem solves for the best parameter y" (x:) over the training set D under the regularized training loss (v) + R(x, y). The goal is to find the hyper-parameter x E Rd whose corresponding best response y (æ) yields the least loss over the validation set D In practice, continuous hyperparameters are often tuned by a grid search which is exponentially expensive. An efficient SBO algorithm should find the optimal parameters in time increasingly polynomially with the dimension, rather than exponentially. When the training and validation sets are distributed across nodes, the problem becomes a distributed SBO.
Compositional Optimization Let g(x, Rd + Rd and fl. <): RR -> IR be two stochastic mappings. Stochastic compositional optimization (SCO) (Wang et al., 2017a) takes the form
min (Eg zEX
SCO applies to risk management (Yang et al., 2019; Ruszezynski, 2021), machine learning (Chen al., 202 and reinforcement learning (Wang al., 2017b). SCO was identified as special case of SBO by (Chen et al., 2021c). To see this, we take the inner optimization objective to be
g( y) Egg (1y (xx, ). Thus y (ar) = argmin, g (x,, becomes y (x) [b((; E)), arriving at an instance of SBO.

---

1.2 Challenges with Distributed SBO
Despite the recent rapid development distributed single-level optimization, a method appropriate to DSBO remains elusive. The major hurdle to solving DSBO lies in the absence of explicit knowledge of y" (z). so that an unbiased gradient for f., , y (a)) is not available. Recently, by applying the implicit function theorem, (Couellan and Wang, 2016; Ghadimi and Wang, 201 88 showed that the gradient of a non-distributed SBO can be expressed as
ax, y (I)) - Vay y (
(3)
providing a connection between SBO and classical stochastic optimization. Since then, various algorithms have been proposed to obtain sharp estimators for (xx and reduce the bias of the constructed gradients (Chen et al., 2021a; Hong et al., 2020; Ji et al., 2021; Yang et al., 2021). These techniques result in tight convergence analysis and give rise to algorithms widely used in applications. However, no prior algorithms can be applied to the distributed setting.
Solving Problem (1) becomes challenging in the distributed setting in several aspects:
1. Even in single-agent SBO, the lack of y" (z:) makes outer optimization nontrivial, and estimat- ing (z) requires additional stochastic approximation, weighted averaging, and sophisticated calculation.
2. Calculating the outer gradient is highly nontrivial, even when have inner solution y. Note that
1
VV
Σ
o (z,
(x,
V (2 v) V V,
(4)
K
KEA
In other words, even if the inner problem is solved, the outer gradient requires a new estimation mechanism.
3. Now we move to SBO over distributed networks. In network learning, communication between agents can be limited by the network structure and communication protocol, so taking simple average across agents may require multiple communication rounds.
Because of the above difficulties, it remains unclear how to estimate the outer gradient sharply under a distributed network. an attempt to tackle this problem, this paper studies the convergence theory and sample complexity of gossip based algorithms. In particular, we ask two theoretical questions:
(i) How does the sample complexity of DSBO scale with the optimality gap and network size?
(ūi) How is the efficiency of DSBO affected by the network structure?
In this paper, we develop gossip-based stochastic approximation scheme where each agent solves an optimization problem collaboratively by sampling stochastic first- and second-order information using its data and making gossip communications with its neighbors. addition, we develop novel techniques for convergence analysis to characterize the convergence behavior of our algorithm. To the best of our knowledge, our work is the first to formulate DSBO mathematically and propose an algorithm with theoretical convergence guarantees. Moreover, show that algorithm enjoys an (Rttr sample complexity for finding e-stationary points for nonconvex objectives, where O(-) hides logarithmic factors, and enjoys an Ö ((+)) sample complexity for Polyak- Lojjsi--ooaiiiiczz (PL) functions, subsuming strongly convex optimization. These results subsume the state-of-the- results for non- federated stochastic bilevel optimization (Chen et al., 2021c) and central- server regimes (Tarzanagh al., 2022). showing that almost no degradation induced by network consensus. Further, the above results suggest that our algorithm exhibits a linear speed-up effect for decentralized settings; that is, the required per-age per-agent sample complexities decrease linearly with the number of agents.
2 Related Works
Bilevel optimization was first formulated by (Bracken and McGill, 1973) for solving resource allocation problems. Later, class of constrained-based algorithms was proposed by (Hansen et al., 1992; Shi et al., 2005), which treats the inner-level optimality condition as constraints to the out-level problem. Recently, (Couellan and Wang, 2016) examined the finite-sum case for unconstrained strongly convex lower-lower problems and proposed gradient-basee based algorithm that
3

---

Stochastic Bilevel Optimization
BSA
stocBio
ALSET
FEDNEST
This Work
Network
Single-Ages
Central-Serve
Decentralized
Samples in ç
O
O
O
K
K2
(1-p)=])
Samples in g
(c--))
0(6-)) O((2)
O
Kc
Ke
(1-p1te =
Stochastic Compositional Optimization
SCGD
NASA
ALSET
FEDNEST
This Work
Network
Single-Agent
Central- Server
Decentralized
Samples in C O(c-4) O(c²)
O
O(c²)
O
Ki
(1-p)ar)
Samples in g (cc=)) O
O
O
Kea
O(KE²
Ke
(1-p1ze)
Table 1: Summary of per-agent sample complexities for nonconvex stochastic bilevel and compo- sitional optimization in different settings: BSA (Ghadimi and Wang, 2018), ALSET (Chen et al., 2021c), stocBio (Ji et al., 2021), FEDNEST (Tarzanagh et al., 2022), SCGD (Wang and Liu, 2016), and NASA (Ghadimi et al., 2020). Given the weight matrix W, p IW-
exhibits asymptotic convergence under certain step-sizes. For SBO, (Ghadimi and Wang. 2018) developed a double-loop algorithm and established the first known complexity results. Subsequently, various methods have been employed to improve the sample complexity, including two-timescale stochastic approximation (Hong al., 2020), acceleration (Chen al., 2021a), momentum (Khanduri et al., 2021), and variance reduction (Guo et al., 2021; Ji et al., 2021; Yang et al., 2021).
Distributed optimization was developed to handle real-world scale datasets (Dekel et al., 2012; Feyzmahdavian et al., 2016) and graph estimation (Wang et al., 2015). Centralized and decentralized systems are both important problems that have drawn significant attention. A centralized system considers the network topology where there is a central agent that communicates with the remaining agents (Lan and Zhou, 20,8), while in decentralized system (Gao and Huang, 2020; Koloskova et al., 2019; Lan et al., 2020; McMahan et al., 2017), each agent can only communicate with its neighbors by using gossip (Lian et al., 2017b strategies, with applications in multi-agent reinforcement learning (Xu et al., 2020). Variance reduction approaches (Xin et al., 2020. 2021; Lian al., 2017a) have also been applied improve the convergence rate of decentralized optimization. Random projection schemes have been studied handle large of constraints (Wang and Bertsekas, 2015, 2016; Liu et al., 2015). All of the above trials were made on vanilla stochastic optimization problems. We are the first to study the decentralized bilevel optimization problem to our knowledge. Table compares this work with prior arts under different settings.
gradient tracking (Pu and Nedić, 2021) communication
3 Problem Setup
Assumption 3.1 (Sampling Oracle SO) Agent may query the sampler and receive an indepen- dent locally sampled unbiased first- and second-order information V. (z, y: ) V fffh (x.vv "*), V n (x, y; ) Vyyg " (z, 5h), and V2ygg (e (z, v:
Assumption 3.2 (Gossip Protocol) The network gossip protocol specified by K x K symmetric weight matrix W with nonnegative entries. Each agent k may receive information from its neighbors, e.g., 24 E Ng. and aggregate them by a weighted sum ΣjeNs Wz. Further, matrix W satisfies
(i) W doubly stochastic such that Wi 1 and E3 Wis for all i, E [K].
(ii) There exists a constant p E (0, such that I|W - spectral norm of A R
= where ||A||2 denotes the
These assumptions on the adjacency matrix are crucial to ensure the convergence of decentralized algorithms and are commonly made in the literature of decentralized optimization (Lian et al., 2017b).
Assumption 3.3 Cj, T,p be positive scalars. The outer level functions ( JReK satisfy the followings.

---

(i) There exists at least one optimal solution to Prob. (1).
(ii) Both V (x, y) and V yffh (a, y) are Li-Lisschitz continuous in (æ, y) such that for all 31,32 E IRd and ,1,3/2 E B
IV (21, 81) oof 82) 11(1 z2 + 1l 32ll),
and V yf (x1. 01) (22, 12)ll - [ x2ll + llyi V22l)..
(iii) For all x E RR and y y RRA,
11 S C2 and B|ll V of (z, (0) C7.
Assumption 3.4 Let Cgs Lug Lg ug Kg be positive scalars. The inner level functions )ee satisfy the followings.
(i) For all TRdd,, (x, y) is My strongyy convex in y.
(ii) For all x E Rd and y E R g" (z, y) is twice continuously differentiable in (x.,y)
(iii (x, (I,y). n). V V (I,y). 2). and V Viyg (x, v) are Lipschitz continuous in (ar, y) such that for all Tı, x2 E Rds and yı, V2 RRd,
(V1,9()))))) (x1,2) V Vug (1r,, 82)l S Lg [ 22ll + 11y1 y/2l).
o F (I1,01) - V² (x2, 22 - L |2] - z2l + 1lv1 32ll). and V (I1,31)
II my
(x2 82) F S Lg ( |21 - æ2ll + l1 32ll).
(iv) For all Rdd E Rd, V veg (: )*,, V Viggg (x, ys )* and V Vaygg( (x have bounded second-order moments such that V g y: { I Cg.
V (x, B.... 5h 11 I Lg and 2f (x, (x.v: th Ila1 s L
V2 V (I, vi 5 has bounded second moment such that (v) For all x Rd, y R4, Lig
IE I- I V (x, y: e S K2g)², where 0 rig
T.g 1.
We defer the detailed assumptions to Section A. of the supplement.
Note that we denote by | |All max (A) the induced 2-norm for any matrix A. Here we point out that the above assumptions allow heterogeneity between functions fh and "s over the agents, and the smoothness and boundedness conditions are commonly adopted in SBO (Hong et al., 2020; Chen et al., 2021a).
4 Algorithm
As discussed in Section 1.2, the key challenge solving DSBO is that each agent only has access to its own data but is required to construct estimators for the gradients and Hessian averaged across all agents. particularly challenging to construct such estimators when limited by the network's communication protocol.
To overcome this issue, propose gossip-based based DSBO algorithm where each agent A IC iteratively updates solution pair (at, yf*) by using the combination of gossip communications and weighted-average stochastic approximation, where yÊ serves as an estimator the best response oi := v"(a) with 3, := ΣkEK 2t. The full algorithm given in Alg. 1.
Here we briefly explain the idea of our DSBO algorithm. Suppose agent would like to estimate Va yt¹) by st under Alg. Step 6. it would query the stochastic first-order information using its own data, make gossip communications with neighbors, and update its estimators by taking the weighted average of its previous estimate s/ neighbors j's estimate s/_,. and the newly sampled gradient v 1 (x/) v ) Roughly speaking, this procedure can be viewed as taking weighted average the gradients sampled by all agents over the network, except that the effect of consensus should also been taken into account.
5

---

Algorithm 1 Gossip-Based Decentralized Stochastic Bilevel Optimization
input: Step-sizes }a,}. {3r) {nt), total iterations T, sampling oracle SO, weight matrix W,
smoothness constant gg hessian sampling parameter b
= 0. y0 0, u 0, sb 0. hg 0, v = 1y for .... ,
1: for = 0,
T do
2: for k = 1.... K do
3:
Local sampling: Query SO at (ot, vt) to obtain V, (xt offst)), V. (
Vyg (x) ; vi: ;t)) Va V vi: {t), and (V (arh ui Sillerr
4:
Outer loop update: # = ΣjENi 2k, as (s - (t))
5:
Inner loop update: 3/+1 ΣJEN, Wkisii - 71 Vog (af, 3/: (t)
6:
Estimate [=f( yo): s (1 B() DEENZ Wk,s ot + 3 V. (x Ct)
7:
Estimate V [z, Ue): hi41 (1 (1))) 18)E)ea DJENS mi + Be V (2+ (t)
8:
Estimate 7 V ( ye): ub41 = -11-3i) E JEEN, uk + 3 V (x
9:
Estimate [ g2, (2,, 3:11 Set Q =
10:
for = 1, ,..,,.b,. do
11:
1,,, = (1 - Bt) Σ jEN, Wki + 36 2 1 (x) st,,),
12:
2++,, + (I (I- La 1f
end for
14:
Set qeth
I, Qt
15:
end for
16: end for
output: Iz 1/ Etex
The updates for vyf and V2.g are conducted in similar manner (Steps 7 & 8), but it requires extra efforts to evaluate [ Ny because it has no unbiased estimator. To be specific, we note that * ExEX' V - + I DEEK v - making the unbiased estimator of the desired term unavailable even if each agent has an unbiased estimator for [V - This is indeed a unique challenge for decentralized bilevel optimization. To overcome this issue, propose novel approach that each agent & constructs independent estimators (uū,)) 16 for Vyg((t vt) using
consensus and stochastic approximation. We then estimate V Vy vt)) by utilizing the following approximation.
b (i -1
I
Σ
I
1 Lg
Vigo vt
II+
I
1 rts)) Lg
i=1==1
We provide details in Steps 9 14.
Finally, each agent will compute the gradient (3) using the estimators obtained in the above procedure and update the outer solution o by using the combination of gossip communication and stochastic gradient descent (Step 4). The inner loop solution yf can be updated similarly by Step 5.
We highlight the following key features of our DSBO algorithm: (1) each agent only communicates its estimates instead of the raw data in the gossip-communication process, preserving data privacy. (2) agent l makes ([[V& )) communications with its neighbors in each round, which is much less than the total number of agents a naive approach. (3) the algorithm robust to contingencies the network. If a communication channel fails, the agents can still jointly learn provided that the network still connected. By contrast, a single-center-mulli- network would fail completely in case of a center failure.
Theory
In this section, we analyze the performance of our DSBO algorithm for both nonconvex and PI. objectives and derive the convergence rates for both cases.

---

5.1 Nonconvex Objectives
We first consider the scenario where overall the objective function F(x) nonconvex. For nonconvex objectives, given the total number of iterations T, we employ the step-sizes in constant form such that
04 - CoV 4, - T. and b ((log(T)) for all 0, ,,
(5)
where Co > 0 is small constant.
Compounded effect of consensus and SBO: As discussed earlier, to derive the convergence rate of SBO under decentralized federated setting, the key step is to quantify the compounded effect between the consensus errors induced by the network structure and the biases induced by estimating gradient within (3). Unlike the central-server or non-federated regimes, the consensus errors induced by the decentralized network structure must be handled carefully. We conduct thorough analysis to derive the contraction of consensus errors, and further show that both the bias and variance of the averaged estimator diminish to zero, establishing a nontrivial convergence argument for the desired gradient and Hessian. In particular, the estimators preserve concentration property so that their variances decrease proportionally to 1/K, suggesting that the network consensus effect does not degrade the concentration of the generated stochastic samples. To achieve the best possible convergence rate, carefully set the algorithm parameters, including the step-sizes at, 7t and averaging weights Be, to control the above consensus errors and biases.
We provide the convergence rate of Alg. in the following theorem and defer the detailed proof to Section B.7 of the supplementary material.
Theorem 5.1 Suppose Assumptions 3.1, 3.2, 3.3, and 3.4 hold. Letting Iz- K ΣkEK ati then
T-1 B B
K
SO
+
VKT
T(I
p)3
More details and proof are deferred to Section B.7 of the supplement.
Effect of consensus: In this result, the O T(I-p}>) term represents the errors induced by the consen- sus of the network. Despite the depending the network structure, this term diminishes to zero in the order of ( ( becoming a small order term when T is large. Consequently, given the network topology, the asymptotic convergence behavior of DSBO is independent of the network structure, answering question (ii) raised in Section
K
Linear speedup: Because each agent queries (bb) stochastic samples per round, clearly the required iteration and per-agent sample complexities for finding an e-stationary point such that T -t= F( < < are O Kez) and θ ( respectively. This result implies that our algorithm achieves a linear speed-up effect proportionate to the number of agents K. In other words, in the presence of more agents, each agent needs to obtain fewer stochastic samples to achieve specified accuracy. Meanwhile, our rate also matches the best-known (11 Ke²) iteration and per-agent sample complexities under the decentralized vanilla stochastic gradient descent settings (Lian al., 2018). This is the first time such result has been established for DSBO problems. seceettr-multi-us----feeeed
SBO: We point out that simplified version of our algorithm solves single-center cealle--eeee-eee multi-userrrr federredee SBO, where the central server collects information directly from each agent and calculates the gradient by employing the weighted-average stochastic approxi- mation scheme for the collected information. In such scenario, the agents no longer communicate by gossip with neighbors but synchronously receive common solution from the central server, so that the consensus effect disappears. In Theorem D.I, we show that a variant of our algorithm can indeed achieve the same O( VKT convergence rate in this setting.
5.2 PL Objectives
Next we study the case where the objective function satisfies the following p-PL condition.
Assumption 5.2 There exists constant 0 such that the objective satisfies the PL condition:
2p(F(z) - F*) < |VF(())
7

---

Note that the class of strongly convex functions is special case of PL functions. To utilize the p-PL property and achieve fast convergence, unlike the nonconvex case (5) where the step-sizes are set as constants depending on the total number of iterations T, we employ step-sizes in a diminishing form that
2
Ci
Ot (CC1 + 3. - -
and b (llog(T)) for 1 1,
C1
where C1 > O is a large constant. By following an analytical process similar to that of the nonconvex scenario, in the next result, we derive the convergence rate of Alg. 1 for p-PP. objectives.
Theorem 5.3 Suppose Assumptions 3. 3.2, 3.3, and 3.4 hold and the function satisfies the μ-PI. Assumption 5.2. Letting ëT = K ExER 2/j- then
1 KT
In
F" FF'
+0
T2(1- - p)3
The iteration and per-agent sample complexities for finding an c-optimal point E[F(TT)] - F Se are O (ke) and O kc), respectively.
Details and proof are deferred to Section C.2 of the supplement. This result shows that our algorithm achieves faster convergence rate for functions satisfying the μ-Pl. condition in terms of both iteration and sample complexities. First, as in the nonconvex scenario, the consensus error decays in the order of Ö (=()-)))) ). Dominated by O KT ), such order of consensus decaying order indicates that the network structure will not affect Alg. I's asymptotic convergence behavior under μ-PL objectives. Mcanwhile, the above result implies that Alg. 1 speeds up linearly with the number of agents and matches the optimal O(1/e) sample complexity for single-server vanilla strongly-conve stochastic optimization (Rakhlin et al., 201 1). As result, our algorithm achieves the optimal sample complexities for decentralized stochastic bilevel optimization, establishing the benchmark.
Numerical Experiments
In this section, we validate the practical performance of our algorithm in two examples: hyper- parameter optimization and policy evaluation in Markov Decision Processes (MDP), on artificially constructed decentralized ring networks. We run the experiments on single server desktop computer. We provide the details of federate hyper-parameter optimization and federated policy evaluation.
prreeepparamter Optimization We consider federated hyper-parameter optimization (2) for a handwriting recognition problem over the Australia handwriting dataset (Chang and Lin, 201 consisting of data points (w,, 21), where wi E I244 is the feature and 2; E {0, 1} indicates whether this data point belongs to category "I" or not. In our experiment, we consider the sigmoid loss function that (=) = 1/(1 + exp(-=)) and a strongly convex regularizer R(x, y) = - d ||ys l|2 We consider ring network of K agents where each agent i preserves two neighbors (i - 1) and (i+1) and conducts a gossip communication strategy with adjacency matrix w. = for E {i - 1, i, ++.
2
Before testing Alg. 1. we first randomly split the dataset for training and validation, and then allocates both training and validation dataset over K agents. We then run Algorithm for T 20000 iterations, with 200, a₂ 0.1 K/T, and B, = 7 = /0/K/T.
To provide a benchmark for comparison, we implement a baseline algorithm Decentralized Bilevel Stochastic Approximation (DBSA) algorithm, naive extension of the double-loop BSA algorithm (Ghadimi and Wang, 2018) in the decentralized setting, formally stated in Section E. of the supple- mentary materials.
We first consider K 5, test Alg. for 5 x 10t iterations, and compare its performance with DBSA. We report the validation loss against total samples in Figure 2 and observe that DSBO exhibits better performance than DBSA. In particular, Further, we observe that our algorithm outperforms the baseline algorithm DBSA in that it requires fewer samples for DSBO to achieve a certain accuracy.
To investigate the efficiency of Alg. 1 to the network structure, we test Alg. over K = 5, 10, 20, and report the details of training and validation loss in Figure 2. Further, comparing the performances of Alg. over different agents K = 5, 10, 20, we observe that Alg. converges faster when using more agents. This observation suggests that Alg. 1 exhibits speed-up effect when using more agents.
8

---

0000
14000
Validation Lese
Validation Lose
0.3
'Total Samplea
Iterattion
(a)
(b)
Figure 2: (a) Empirical averaged training loss against total samples for DSBO K = 10, 20 and DBSA K = 5. (b) Empirical averaged validation loss against iteration for DSBO K = 5, 10, 20. All figures are generated through independent simulations over the Australia handwriting dataset.
We provide additional experiments on networks of larger size (K 100) and various topologies (fully-connected and (onoomly-connected) in Section E.1 of the supplement.
Distributed Policy Evaluation for Reinforcement Learning We consider multi-agent MDP problem that arises in reinforcement learning. Let S be the state space. For any state E S, we denote the value function by (ss). We consider the scenario where the value function can approximated by a linear function such that (s)) = o x", where &, R is feature and x² E R is unknown parameter. To obtain the optimal x we consider the following regularized Bellman minimization problem
min F(x) 2
- To x s))²
#ES
where r(s, s') is the random reward incurred by transition to s', (0, 1) is the discount factor, is the coefficient for the fz-regularizer, and the expectation taken over random transitions from to s'.
In the federated learning setting, we consider a ring network of agents, Here each agent & has access to its own data with heterogeneous random reward function r* and can only communicate with its two neighbors + 1 and & 1. We denote by v (a)) ob E., I ΣkEI r*(s, 8') yo where (s, s') is the random reward function for agent k. The above problem can then be recast as bilevel optimization problem
min fl, ZERd
Σ (v)(2)))
Ala 2
2|S
SES
As pointed out by (Wang et al., 2016), the above problem is X-strongly convex.
In experiments, simulate environment with state space |S| 100 and set the regularizer parameter À = 1. We test the performance of Alg. over three cases with = 5. 10, 20 and conduct 10 independent simulations for each K. We implement baseline double-loop algorithm DSGD that first estimates y, (#x) with f samples in iteration t and then optimizes the solution 2y, We defer the implementation details of the environment and above algorithms Section E.2 of the supplement.
We first consider K = 5, run Alg. for 10 iterations and compare its performance with DSGD. We plot the empirical averaged mean square error || =² against total samples generated by all agents in Figure 2. This empirical result suggests that Alg. outperforms the DSGD. To investigate the convergence rate of DSBO, we compare the performance of DSBO over all three scenarios with K = 5, 10, 20 and plot the trajectory of the averaged log-error log(Ii - xx [|2) averaged, with one a straight line of slope -1 provided for comparison. We observe that for all four cases, the slopes of log(I[ x I|2) are close to -I, matching our theoretical claim Theorem 5.3 that Alg. converges rate of (1/t)) for strongly convex objectives.
In the above experiment, we also note that Alg. converges faster when using more agents. further demonstrate the linear speedup effect, we compute the total generated samples for finding an e-optimal solution | 2² E and plot the 75% confidence region of the log-sample against the number of agents K 5. 10, 20 in Figure 3. We observe that it takes roughly same number of samples to

---

Empirical Convergezee
Empirieal Log Convergence
75% Confilmnes Region for 10
LINES
Ioci x117
Total Samples
Log Iteration logit)
Servecs K
(a)
(b)
(c)
Figure 3: (a) Empirical averaged MS 1²2 against total samples for DSBO K 5, 10, 20
and DSGD K = 5. (b) Empirical averaged log-MSE [g - -=====11'" ==1²²)
against log-iteration log(t) for
DSBO K 5, 10, 20. (c) 75% confidence region of log- total samples for achieving || x=1 e,
with varying network sizes K = 5, 10, 20. All figures are generated through 10 independent simulations.
find a 10 6 ooptimall solution despite different number of agents being involved. This suggests that the per-node sample complexity decreases linearly with K, validating the linear speedup claim in Theorem 5.3. We provide additional numerical results for other optimality level e in Section E.2 of the supplementary material further demonstrate the linear speedup effect.
7 Conclusion
In this paper, we propose novel formulation for decentralized stochastic bilevel optimization. We develop gossip-based stochastic approximation scheme to solve this problem in various settings. We show that our proposed algorithm finds a stationary point at a rate of O VKT for nonconvex
objectives, and converges to the optimal solution at a rate of O KT for PL objectives. Numerical experiments on byper-paramett optimization and multi- federated MDP demonstrate the practical efficiency of our algorithm, exhibit the effect of speed-up in a decentralized setting, and validate our theoretical claims. In our future work, we wish to develop algorithms that achieve lower iteration complexities and enjoy lower communication costs.
Acknowledgments and Disclosure of Funding
Mengdi Wang acknowledges support by NSF grants DMS-1953686, IIS-2107304, CMMI-1653435 and ONR grant 1006977.
References
Sanjeev Arora, Simon Du, Sham Kakade, Yuping Luo, and Nikunj Saunshi. Provable representation learning for imitation learning via bi-level optimization. In International Conference on Machine Learning, pages 367-376. PMLR, 2020.
Luca Bertinetto, Joao F Henriques, Philip HS Torr, and Andrea Vedaldi. Meta-learning with differen- tiable closed-form solvers. arXiv preprint 880.::1805.08136 2018.
Jerome Bracken and James T McGill. Mathematical programs with optimization problems in the constraints. Operations Research, (1(:33774 1973.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM 2011. URL https://www.
transactions on intelligent systems and technology (TIST), 2(3):1 2011.
csie. ntu, edu. http:////bbtttoool/aaaaaaaaaeeee
Tianyi Chen, Yuejiao Sun, and Wotao Yin. A single-timescale stochastic bilevel optimization method. arXiv preprint ar 21xY:2200..0671,, 2021a.
10

---

Tianyi Chen, Yuejiao Sun, and Wotao Yin. Solving stochastic compositional optimization is nearly as easy as solving stochastic optimization. IEEE Transactions on Signal Processing, 69:4937-4948. 2021b.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Tighter analysis of alternating stochastic gradient method for stochastic nested problems. arXiv preprint 1rXii:2106.13781, 2021c
Nicolas Couellan and Wenjuan Wang. On the convergence of stochastic bi-level gradient methods. Optimization, 2016.
Evin Cramer, John E Dennis, Jr, Paul D Frank, Robert Michael Lewis, and Gregory R Shubin. Problem formulation for multidiseiplinary optimization. SIAM Journal on Optimization, 4(4): 754-776, 1994.
Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research, 13(1), 2012.
Hamid Reza Feyzmahdavian, Arda Aytekin, and Mikael Johansson. An asynchronous mini-batch algorithm for regularized stochastic optimization. IEEE Transactions on Automatic Control, 61 (12):3740-3755) 2016.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference Machine Learning, pages I 1568-1577. PMLR, 2018.
Hongchang Gao and Heng Huang. Periodic stochastic gradient descent with momentum for decen- tralized training. arXiv preprint arXiv:2008. 10435, 2020.
Jason Ge, Zhaoran Wang, Mengdi Wang, and Han Liu. Minimax-optimal privacy-preserving sparse pca in distributed systems. In International Conference on Artificial Intelligence and Statistics, pages 1589-1598. PMLR, 2018
Saeed Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 156(1):59-99, 2016.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint 1002.0220000224 2018.
Saeed Ghadimi, Andrzej Ruszczynski, and Mengdi Wang. A single timescale stochastic approxima- tion method for nested stochastic optimization. SIAM Journal on Optimization, 30(1 30(1):900-979 2020.
Zhishuai Guo, Quanqi Hu, Lijun Zhang, and Tianbao Yang. Randomized stochastic variance-reduced methods for multi-task stochastic bilevel optimization. arXiv preprint arXiv:2105.02220 2021.
Pierre Hansen, Brigitte Jaumard, and Gilles Savard. New sranch-and-bound rules for linear bilevel programming. SIAM Journal on scientific and Statistical Computing. 13(5): 194-1217, 1992.
Mingyi Hong, Hoi-To To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critie. arXiv preprint arXiv:2007.055 00.000000770.0 2020.
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pages 4882 4892. PMLR, 2021.
Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A near-optimal algorithm for stochastie bilevel optimization via double-momentum. Advances in Neural Information Processing Systems, 34, 2021.
Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. arXiv preprint 10X0v0190..09356, 2019.
Guanghui Lan and Yi Zhou. Random gradient extrapolation distributed and stochastic optimization. SIAM Journal on Optimization, 28(4):2753-2782) 2018

---

Guanghui Lan, Soomin Lee, and Yi Zhou. Communication-effccennt algorithms for decentralized and stochastic optimization. Mathematical Programming. 180(1):237-2844 2020.
Xiangru Lian, Mengdi Wang, and Liu, Finite-sum composition optimization via variance reduced
gradient descent. In Artificial Intelligence and Statistics, pages 1159-1167. PMLR, 2017a.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Advances in Neural Information Processing Systems, 30, 2017b.
Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In International Conference on Machine Learning, pages 3043-3052. PMLR, 2018.
Jialin Liu, Yuantao Gu, and Mengdi Wang. Averaging random projection: A fast online solution for large-scale constrained stochastic optimization. In 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3586-3590, 2015.
Eli Livne. Integrated aeroservoelastic optimization: status and direction. Journal of Aircraft, 36(1): 122-145, 1999.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication--ffiiienn learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pages 1273-1282. PMLR, 2017.
Takayuki Okuno, Akiko Takeda, Akihiro Kawana, and Motokazu Watanabe. On Ip-hyperparamettr learning via bilevel nonsmooth optimization. Journal of Machine Learning Research, 22(245): 1 1-47, 2021.
Shi Pu and Angelia Nedić. Distributed stochastic gradient tracking methods. Mathematical Program- ming, 187(1):409-4577 2021.
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. arXiv preprint urXiv: 109.5647, 2011.
A. Ruszezyúski and A. Shapiro. Optimization of convex risk functions. Mathematics of Operations Research, 3133):333-452, 2006.
Andrzej Ruszezynski. A stochastic subgradient method for nonsmooth nonconvex multilevel compo- sition optimization. SIAM Journal on Control and Optimization, 59(3):230--2320, 2021.
Chenggen Shi, Jie Lu, and Guangquan Zhang. An extended kuhn- approach for linear bilevel programming. Applied Mathematics and Computation, 162(1):51-63, 2005.
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. Advances in neural information processing systems, 30, 2017.
Jaroslaw Sobieszcranski-Sobiese and Raphael T Haftka. Multidisciplinary aerospace design opti- mization: survey of recent developments. Structural optimization, 14(1):1-23, 1997.
Murtaza Taj and Andrea Cavallaro. Distributed and decentralized multicamera tracking. IEEE Signal Processing Magazine, 28(3):46-58, 2011.
Davoud Ataee Tarzanagh, Mingchen Li, Christos Thrampoulidis, and Samet Oymak. Fednest:
Federated bilevel, minimax, and compositional optimization. arXiv preprint arXiv:2205.02211 2022.
Shenyinying Tu. Two-Stage Decomposition Algorithms and Their Application to Optimal Power Flow Problems. PhD thesis, Northwestern University, 2021.
Shenyinying Tu, Andreas Wächter, and Ermin Wei. A two-stage decomposition approach for ac optimal power flow. IEEE Transactions on Power Systems, 36(1):303-3 2020.
Heinrich Von Stackelberg and Stackelberg Heinrich Von. The theory of the market economy. Oxford University Press, 1952.
12

---

M. Wang and J. Liu. A stochastic compositional gradient method using markov samples. In Proceedings of the 2016 Winter Simulation Conference, pages 702-713. IEEE Press, 2016.
M. Wang, E. X. Fang, and H. Liu. Stochastic compositional gradient descent: Algorithms for minimizing compositions of expected-value functions. Mathematical Programming, 161(1-2): 2017a.
M. Wang, J. Liu, and E. X. Fang. Accelerating stochastic composition optimization. The Journal of Machine Learning Research, 18(1):3721-3743, 2017b.
Mengdi Wang and Dimitri P Bertsekas. Incremental constraint projection methods for variational inequalities. Mathematical Programming, 150(2):321-363, 2015.
Mengdi Wang and Dimitri P Bertsekas. Stochastic first-order methods with random constraint projection, SIAM Journal on Optimization, (6(1):681-77)) 2016.
Mengdi Wang, Liu, and Ethan Fang. Accelerating stochastic composition optimization. In Advances in Neural Information Processing Systems, pages 1714-1722, 2016.
Xiaohan Wang, Mengdi Wang, and Yuantao Gu. A distributed tracking algorithm for reconstruction of graph signals. IEEE Journal of Selected Topics in Signal Processing, 9(4):28 02000200-00 2015.
Ran Xin, Usman A Khan, and Soummya Kar. Variance-reduced decentralized stochastic optimization with accelerated convergence. IEEE Transactions on Signal Processing, 68:6255-6271 2020.
Ran Xin, Usman A Khan, and Soummya Kar. An improved convergence analysis for decentralized online stochastic non-convex optimization. IEEE Transactions on Signal Processing, 69:1842 1858, 2021.
Yue Xu, Zengde Deng, Mengdi Wang, Wenjun Xu, Anthony Man-Cho So, and Shuguang Cui. Voting- based multiagent reinforcement learning for intelligent iot. IEEE Internet of Things Journal, ((4):2681-269) 2020.
Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems, 34, 2021.
S. Yang, M. Wang, and E. Fang. Multilevel stochastic gradient methods for nested composition optimization. SIAM Journal on Optimization, 29(1):616-00) 659, 2019.
13

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A] - You are strongly encouraged to include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license the code and datasets? [Yes]
Did you include the license the code and datasets? [No] The code and the data
proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This an algorithmic and theoretical work justified by numerical experiments. We are not aware of any negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Complete proofs are provided in the supplement.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (cither in the supplemental material or URL)? [No] We will provide the code via github in the camera-ready version stage.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No] We provided averaged results over different random seeds and the obtained results are stable.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using cxisting assets (e.g., code, data, models) curating/releusing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A] The dataset is publicly available and
no license is required.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A] We are not releasing new assets.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] We cited the website link where data is presented.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] The data does not contain personally identifiable information or offensive content.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] We did not involve human subjects.
14

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "e5lVbo4LKS8", "reviewer": "Reviewer_s3u4", "summary": "The paper tackles the problem of Stochastic Bilevel Optimization (SBO) in a decentralized setting, using a gossip protocol for communication between the agents. The authors propose an approach based on a existing formulation of the gradient and a recent contribution (Ghadimi et al. 2020) to provide an (biased) estimate of the Hessian in a decentralized framework. They then provide a complete theoretical analysis of their method for both $\\mu$-PL and nonconvex objectives. Finally, empirical results are provided for the two problems introduced in the beginning of the paper: hyperparameter optimization and policy evaluation.", "questions": "- Is there another way of performing decentralized estimation of the Hessian over a network? If so, how would it compare to the method used here?\n- What is the motivation to only use ring networks in the experiments? These networks are often slow in terms of \"diffusion\" and are a counter-example to the robustness mentioned on l. 174.\n- I do not understand the notation on l. 139, is $\\nabla_y f^k$ only Lipschitz continuous on $x$? on $y$?", "limitations": "Privacy if briefly mentioned, although it does not seem adequate to me.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, the paper is very clear and easy to follow. SBO is thoroughly introduced and illustrated, and the main challenge of producing a decentralized approach (combining the recent formulation of the gradient with the Hessian estimation) clearly stated. Each step of the analysis is first motivated then commented, with an attention to providing easy-to-read quantities.\nEmpirical results are extensively commented and seem convincing about the validity of the approach.\n\nSome remarks:\n- Polyak-Łojasiewicz should be introduced at some point rather than be stated as \"_PL_\" from the start.\n- l. 171: ensuring data privacy just based on the fact that raw data are not communicated is quite ambitious, to say the least.\n- l. 174: it is true that the method would not collapse from a single failure in the network, but I think it is worth mentioning that the optimization objective would then be different, as the network would be missing a part of the dataset.\n\nTypos:\n- Step 9 of Algorithm 1: UnifoRm\n-  Equation (3): should be $\\nabla_x f$ rather than $\\nabla f_x$", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VPXp8nWiNN4", "reviewer": "Reviewer_UN8Y", "summary": "In this work, the authors studied the stochastic bilevel optimization problem in a decentralized way. The authors proposed a gossip-based distributed bilevel learning algorithm that solve both the inner and outer optimization problems in a single timescale. Furthermore, the sample complexities are optimal for $\\epsilon$ and $K$, and the method achieves linearly scaling in network size. Although there are many existing works for the stochastic bilevel optimization, the successful work for decentralized SBO is still limited. This work solve the DSBO by estimating the $y^*(x)$ and handled the network propagation via gossip-based methods. The proposed method each agent solves an optimization problem collaboratively by sampling stochastic first- and second-order information using its data and making gossip communications with its neighbors. In addition, the theoretical convergence guarantees are also presented, which match the state-of-the-art results for non-federated stochastic bilevel optimization and central-server regime, and suggest that the algorithm exhibits the linear speed-up effect for decentralized settings. The method is verified by the experiments on decentralized ring networks. ", "questions": "The work only consider the artificially constructed decentralized ring networks, I would suggest to evaluate the methods on multiple different networks to demonstrate the method effectiveness and scaling.  ", "limitations": "the authors adequately addressed the limitations and potential negative societal impact of their work", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of the work is the theoretical analysis and proposed method for decentralized stochastic bilevel optimization problem. As I mentioned, although there are many existing works for the stochastic bilevel optimization, the successful work for decentralized SBO is still limited. This work solve the DSBO by estimating the $y^*(x)$ and handled the network propagation via gossip-based methods. In addition, the theoretical convergence guarantees are also presented, which match the state-of-the-art results for non-federated stochastic bilevel optimization and central-server regime, and suggest that the algorithm exhibits the linear speed-up effect for decentralized settings. \n\nThe weakness of the work is the experiments. The work only consider the artificially constructed decentralized ring networks, and only run two simple examples on hyper-parameter optimization and policy evaluation in Markov Decision Processes (MDP). I would suggest to evaluate the methods on multiple different networks to demonstrate the method effectiveness and scaling. Also suggesting more practical examples for validation purpose. For example, most experiments are running using only 5 nodes, far behind the practical decentralized setting, suggest nodes from 20 to 100, and network topology from ring network to many other variations.  ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UMn5F2ACyqi", "reviewer": "Reviewer_jXmE", "summary": "This paper studies the distributed bilevel optimization over a network under the non-convex cases and strongly-convex cases. This paper first develops a gossip-based distributed bilevel learning algorithm based on the stochastic gradient descent method. Then, the authors develop the convergence analysis to characterize the convergence behavior of the stated algorithm. The algorithm achieves an $\\mathcal{O}\\left(\\frac{1}{K \\epsilon^{2}}\\right)$ sample complexity for nonconvex objectives and achieves an $\\mathcal{O}\\left(\\frac{1}{K \\epsilon}\\right)$ sample complexity for $\\mu$-PL functions, subsuming strongly convex optimization. ", "questions": "1. What is the definition of $F^*$ in Line. 229/237? \n2. The convergence result for Theorem 1 is for the $\\epsilon$-stationary point, while the result for Theorem 2 is for $\\epsilon$-optimal point, why not make them being consistent?\n3. How to determine the Matrix W in your experiment? How does the network sparsity affect the Matrix W and the convergence result?\n4. Are there any motivational examples of performing the decentralized bilevel optimization problems with strongly-convex objectives?\n5. The Distributed policy evaluation for reinforcement learning shown in Section.6 shows in Line.285 that\n\n$y_s^*(x) =\\phi_{s}^{\\top} x-\\mathbb{E}_{ s' } [ 1/K \\sum_k r^{k}( s , s' ) +\\gamma  \\phi_s^{\\top}  x  |  s] $\n\nHowever,  $ y^{*}(x)=\\underset{y \\in \\mathbb{R}^{d_{y}}}{\\operatorname{argmin}} \\frac{1}{K} \\sum_{k=1}^{K} g^{k}(x, y)$ in eqs.(1).\n\nWhat is the g function in Line 285? In eqs(1), should the $y^*$ be the solution when optimizing the lower-level $g$ function, but not the direct result of a function?\n\n6.  In Line.45, it shows that $x$ is a vector of hyper-parameters for a strongly convex regularizer $R$ and the loss function $l_i(y)$ only depends on $y$. However, eqs.(1) shows that the loss function includes both $x$ and $y^*(x)$.\n The question is: how to calculated $\\nabla_x l_{i}( y^*(x) )$ shown in Eqs.(3) without x inside? Is $\\nabla_x l_{i}( y^*(x) )$=0 ?The stated hyperparameter problem seems different from the bilevel optimization problem in (1).\n\n\n\n\n\n\n", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThis paper presents a clear problem formulation for the decentralized bilevel optimization problem motivated by several real-world applications. Besides, the proposed gossip-based distributed bilevel learning algorithm and experimental evaluations are mostly well explained.\n\nWeaknesses:\n1. This submission missed some important theoretical results of existing works. The state-of-the-art sample complexities (paper shown in Line.111 and Line.112) for the stochastic bilevel optimization problem is $\\mathcal{O}(\\epsilon^{-1.5})$, while the authors claim that the state-of-the-art sample complexity is  $\\mathcal{O}(\\epsilon^{-2})$.\n\n2. The stochastic estimator seems infeasible. In machine learning applications,  $\\nabla_{yx}^2 g$ is usually within a high-dimensional. The question is, in Algorithm 1, Line 4, how to compute the Hessian inverse with a relatively high-dimensional matrix?\n\n3. Theoretical results: Even though this paper is the first paper to explore the decentralized bilevel optimization problem. The proof techniques seem regular, and the results in both nonconvex and strongly convex cases are not attractive. First, in the case of the nonconvex objectives, the sample complexity of $\\mathcal{O}(\\epsilon^{-2})$ per client is not a surprising result, and the state-of-the-art result (single-client bilevel optimization problem) already achieves the sample complexity of $\\mathcal{O}(\\epsilon^{-1.5})$. Second, the strongly-convex objectives are not widely used in real-world applications. It would be helpful if the authors could provide some motivational examples to support the reasons for further exploring the strongly convex decentralized bilevel optimization problem.\n\n4. The experimental evaluations are weak. First, the Australia handwriting dataset and LR models are too simple. Evaluating the optimization algorithms using CIFAR10/ImageNet and deeper neural networks has become a standard requirement. Second, it would be better for the authors to provide additional experiments on different distributed network topologies (dense/ sparse). Third, the major contribution of this paper is to provide the convergence bound of the gradient norm. The authors should also provide the gradient norm comparison in the experiment section.\n\n\n\n\nMinors:\n1.Line 96: sammple --> sample\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8xzvpABzCqm", "reviewer": "Reviewer_8YY4", "summary": "This paper considers the decentralized bilevel optimization problem. It proposes a gossip-based method which overcomes the challenges in computing the hyper-gradients in decentralized bilevel optimization method. With a strongly-convex lower level problem, the method is provably convergent and achieves the optimal rate (along with linear speedup) for both the general non-convex upper level problem and the PL upper level problem.", "questions": "1. As stated in previous section, why is Assumption A. 1. (iv), which is stronger than the standard bounded variance assumption, needed in the analysis? Is it possible to relax this assumption to the more standard one?\n\n2. Can the authors explain more about the third key feature stated in line 180-183? Specifically, does the analysis demonstrate such an effect?", "limitations": "One unique challenge in decentralized bilevel optimization is the efficient computation of the upper level hyper-gradient, which requires the inverse of a large Hessian matrix. The method proposed in the paper requires a direct inversing operation done locally, which can limit the application when the local machine has limited computation power (e.g. in a federated learning setting). It would be great if a smarter decentralized algorithm can lift the requirement of directly inverting the Hessian matrix, while still enjoys the convergence guarantee.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe paper is well-written as easy to understand. The considered decentralized bilevel optimization problem is an important topic. Several unique problems and theoretical challenges arising from the decentralization in a bilevel setting are addressed by the paper, and the theoretical result is also sound and convincing.\n\nWeakness:\nHowever, I do have several concerns: 1) Assumption A.1. (iv) requires the stochastic gradients to be bounded in expectation, which is stronger than the standard bounded variance assumption widely satisfied in practice, e.g. Assumption 3 in [1]; 2) In the proposed algorithm, computing the hyper-gradient for the upper level requires inverting a matrix $v_t^k$. The matrix has a size of $d_y \\times d_y$, which is large if the network size is large. Therefore, inverting such a large matrix can be too computational intensive, especially for a local machine with limited computation power.\n\n[1] Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept