Prometheus: Endowing Low Sample and Communication Complexities to Constrained Decentralized Stochastic Bilevel Learning
Authors: Zhuqing Liu
Xin Zhang
Prashant Khanduri
Songtao Lu
Jia Liu
Venue: Submitted to ICLR 2023 (2023)

Abstract: 	In recent years, constrained decentralized stochastic bilevel optimization has become increasingly important due to its versatility in modeling a wide range of multi-agent learning problems, such as multi-agent reinforcement learning and multi-agent meta-learning with safety constraints. However, one under-explored and fundamental challenge in constrained decentralized stochastic bilevel optimization is how to achieve low sample and communication complexities, which, if not addressed appropriately, could affect the long-term prospect of many emerging multi-agent learning paradigms that use decentralized bilevel optimization as a bedrock. In this paper, we investigate a class of constrained decentralized bilevel optimization problems, where multiple agents collectively solve a nonconvex-strongly-convex bilevel problem with constraints in the upper-level variables. Such problems arise naturally in many multi-agent reinforcement learning and meta learning problems. In this paper, we propose an algorithm called Prometheus (proximal tracked stochastic recursive estimator) that achieves the first $\mathcal{O}(\epsilon^{-1})$ results in both sample and communication complexities for constrained decentralized bilevel optimization, where $\epsilon>0$ is the desired stationarity error. Collectively, the results in this work contribute to a theoretical foundation for low sample- and communication-complexity constrained decentralized bilevel learning.

Under review as a conference paper at ICLR 2023
PROMETHEUS: ENDOWING Low SAMPLE AND COM- MUNICATION COMPLEXITIES TO CONSTRAINED DE- CENTRALIZED STOCHASTIC BILEVEL LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
In recent years, constrained decentralized stochastic bilevel optimization has be- come increasingly important due to its versatility in modeling wide range of multi-agent learning problems, such as multi-agent reinforcement learning and multi-agent heta-leaming with safety constraints. However, one eeder-explored and fundamental challenge in constrained decentralized stochastic bilevel optimiza- tion is how to achieve low sample and communication complexities, which, if not addressed appropriately, could affect the long-term prospect of many emerging multi-agent learning paradigms that use decentralized bilevel optimization as a bedrock. In this paper, we investigate a class of constrained decentralized bilevel optimization problems, where multiple agents collectively solve a nonconvex- strongly-convex bilevel problem with constraints in the upper-level variables. Such problems arise naturally in many multi-agent reinforcement learning and meta learn- ing problems. In this paper, we propose an algorithm called Prometheus (proximal tracked stochastic recursive estimator) that achieves the first O 1) results in both sample and communication complexities for constrained decentralized bilevel opti- mization, where is a desired stationarity error. Collectively, the results in this work contribute to theoretical foundation for low sample- and communication- complexity constrained decentralized bilevel learning.
INTRODUCTION
In recent years, the problem of constrained decentralized bilevel optimization has attracted increasing attention due to its foundational role in many emerging multi-agent learning paradigms with safety or regularization constraints. Such applications include, but are not limited to, safety- cefet-cconttraieed multi- agent reinforcement learning for autonomous driving (Bennajeh et al. 2019), multi-agent meta-learning (Poon Peyré| (02T), and rank-constrained decentralized matrix com- pletion for recommender systems (Pochmann & Von Zuben| 2022). etc. As its name suggests, defining feature of constrained decentralized bilevel optimization is "decentralized," which implies that the problem needs to be solved over network without any coordination from centralized server. As a result, all agents must rely on communications to reach a consensus on an optimal solution. Due the potentially unreliable network connections and the limited computation capability at each agent, such network-consensus approaches for constrained decentralized bilevel optimization typically call for low sample and communication complexities. To date, however, none of the existing works on sample- and Communication-effinn considered domain constraints (c.g.. Gao et al.) (2022); Yang et al. (2022): Lu al. (2022): Chen et al.) (2022b) and Section for detailed discussions). In light of the growing importance of constrained decentralized bilevel optimization, our goal in this paper is to fill this gap by developing sample- and communication-ccficccn consensus-based algorithms that can effectively handle domains constraints.
decentralized bilevel optimization in the literature
Specifically, this paper focuses on a class of constrained decentralized multi-task bilevel optimization problems, where we aim to solve decentralized nonconvex- wwwprreeesssroogyyoooooee bilevel optimization problem with i) multiple lower-level problems and ii) consensus and domain constrains on the upper level. Such problems naturally arise in -oouttticcottrrineed bi-level model for integrated natural gas and electricity system (Li et al. 2017). multi multi-agent actor-critic reinforcement learning (Zhang et al. 2020) and constraint meta-learning (Liu et al. 2019). In the optimization literature, natural

---

Under review as a conference paper at ICLR 2023
approach for handling domain constraints is the proximal operator. However, will be shown later, proximal algorithm design and theoretical analysis for constrained decentralized bilevel optimization problems is much more complicated than those of unconstrained counterparts and the results are very limited. In fact, in the literature, the proximal operator for constrained bilevel optimization has been under-explored even in the single-agent setting, not to mention the more complex multi-agent settings. The most related works in terms of handling domain constraints can be found in (Hong al. 2020 Chen et al. 2022a Ghadimi & Wang 2018). which rely on direct projected (stochastic) gradient descent to solve the constrained bilevel problem. In contrast, our work considers general domain constraints that require evaluation of proximal operators each iteration. Also, these works only considered the single-agent setting, and hence their techniques are not implementable over networks. Actually, up until this work, unclear how to design proximal algorithms to handle domain constraints for decentralized bilevel optimization. Moreover, it is worth noting that existing methods for hyper-gradiens approximation in both single- and either based on first-order Taylor-typs type approximation approaches (Khanduri al. [02T]] Ghadimi & Wang 2018: Hong et al. 2020), implicit differentiation (Ghadimi & Wang [0188] Gould et al. 2016]] Ji et al. 2021), ) iterative differentiation (Franceschi et al.) [017]] Maclaurin al.) [015 et al.
bilevel optimization are
2021). all of which suffer from high communication and sample complexities that are problematic in
decentralized settings over networks.
The main contribution of this paper is that we propose a series of new proximal-type algorithmic techniques overcome the challenges mentioned above and achieve low sample and communica- tion complexities for constrained decentralized bilevel optimization problem. The main technical contributions of this work are summarized below:
We propose a decentralized optimization approach called Prometheus (proximal tracked stochastic recursive estimator), which is a cleverly designed hybrid algorithm that integrates proximal operations, recursive variance reduction, lower-level gradient tracking, and upper-level consensus techniques. We show that, to achieve an e-stationary point, Prometheus enjoys convergence rate of O(LTT), where T is the maximum number of iterations. This implies (EE-1) communication complexity and O O(vnke-1 n) sample complexity per agent.
We propose a new hyper-gradient estimator for the upper-level function, which leads to a far more accurate stochastic estimation than the conventional stochastic estimator used in (Khanduri et al.] [222]] Ghadimi & Wang] 2018 Hong et al., 22220] Liu al., (002). We show that our new hyper- hyper-gradient stochastic estimator has a smaller variance and outpertorms existing estimators both theoretically and experimentally. We note that our proposed estimator could be of independent interest for other bilevel optimization problems.
We reveal an interesting insight that the variance reduction in Prometheus is not only suffi- cient but also necessary in the following sense: a noon-varianc--rdducee special version of Prometheus could only achieve a much slower (1IvVT) convergence to constant error-ball rather than e-stationary point with arbitrarily small e-tolerance. This insight advances our under- standing and state of the art of algorithm design for constrained decentralized bilevel optimization.
The rest of the paper is organized as follows. In Section we review related literature. In Section we provide the preliminaries of the decentralized bilevel optimization problem. In Section 4 we provide details on our proposed Prometheus algorithm, including the convergence rate, communication complexity, and sample complexity results. Section 5 provides numerical results verify our theoretical findings and Section concludes this paper.
RELATED WORK
In this section, we first provide a quick overview of the fate-off-thearr on single-agent constrained bilevel optimization well as decentralized bilevel optimization.
1) Constrained Bilevel Optimization in the Single-Agent Setting: As mentioned in Section I various techniques have been proposed to solve single-agent bilevel optimization, such utilizing
full- gradient- brasdd techniques (e.g., AlD-based methods (Rajeswaran et al., 2019 Franceschi et al.
2018; Ji et al. 2021), ITD-based methods (Pedregosal |016 Maclauri et al. 2015 [J et al. [02
stochastic gradient- based techniques (Ghadimi & Wang] [0088] | Khanduri et al.) [2021] 2uo Guo & Yang Khanduuauurri
2021), STORM-base b-sed techniques (Cutkosky & Orabona 2019), and VR-based techniques (ang
2

---

Under review as a conference paper at ICLR 2023
et al. 2021>. However, none of these existing works have considered domain constraints. To our knowledge, the only works that considered domain constraints in the single-agent setting can be found in (Hong et al., 2020 Chen et al. 2022a: Ghadimi & Wang 2018). In (Ghadimi & Wang 2018), the authors proposed a double-loop a algorithm called BSA, where in the inner loop the lower level problem is solved to sufficient accuracy, while in the outer loop projected (stochastic) gradient descent is utilized to update the model parameters. The double-loop structure of BSA led to slow convergence. In (Hong al. 2020), a two-timescale single loop stochastic approximation (TTSA) algorithm based on projected (stochastic) gradient descent was proposed to solve the constrained bilevel optimization problems. However, TTSA has to choose step-sizes of different orders for the upper and lower level problems to ensure convergence, which leads to suboptimal complexity results. Later (Chen et al. 2022a), an algorithm called STABLE algorithm proposed to utilize a momentum-based gradient estimator and combines the Moreau-envelop-bane based analysis to achieve an ( cample-complcxity As mentioned in Section | however, the methods in (Ghadimi & Wang 8 Hong et al. 2020 Chen et al. 2022a) consider only simple constraints. Moreover, the aforementioned methods are not applicable in the decentralized setting.
2) Decentralized Bilevel Optimization: Decentralized bilevel optimization has also received in- creasing attention in recent years. For example, Yang et al. (2022), et al. (2022) and [Chen et al. (2022b) respectively proposed stochastic gradient (SG)-type decentralized algorithms for bilevel optimization and achieve an (()=)) cample-communication complexity. The VRDBO method in (Gao et al., 2022) employed the momentum based techniques for decentralized bilevel optimization to achieve better O complexity results. However, VRDBO updates upper- and lower-level variables in an alternating fashion. As will be shown later, our Prometheus algorithm updates upper-level and lower-level variables simultaneously, which renders a much lower implementation complexity than VRDBO. Besides, Prometheus achieves O(ynke + n) sample complexities, which is near-optimal sample complexity and outperforms existing decentralized bilevel algorithms. worth noting that, the in aforementioned works, consensus requirements exist on both lower- and upper-level subproblems. To certain extent, such formulation can be viewed as multiple agents collaboratively solving the same bilevel optimization problem. In contrast, our work only has a con- sensus requirement in the upper-level subproblem, which implies multiple different lower-level tasks. This is more wractically-relevaa and a more appropriate formulation for multi-agent reinforcement learning, multi-agent meta-leaming, etc. We note that the most related work on decentralized bilevel optimization is (Liu et al. (0022), which also considered multiple lower-level tasks. However, the INTERACT method in (Liu al. 2022) is unconstrained and cannot handle non-smooth objectives considered in our work. In contrast, we propose a special proximal operator X,, to address this challenge. Last but not least, we note that none of the aforementioned works on decentralized bilevel optimization took domain constraints into consideration. For clearer comparisons, we summarize and compare the complexity results of all algorithms mentioned above in Table !
PROBLEM FORMULATION AND MOTIVATING APPLICATIONS
1) Network Consensus Formulation for Decentralized Bilevel Optimization: Consider an undi- rected connected network G = (N, C) that represents a pecr-to-peer network, where A and L are the sets of agents (nodes) and edges, respectively, with [W| = m. Each agent i has local computation ca- pability and can share information with its neighboring agents denoted as N, & {i' E N (i, i') C}. Each agent i has access to a local dataset of size n. All agents in the network collaboratively solve the following constrained decentralized bilevel optimization problem:
m Σ (((x)) A(x;)) A
min X:EX m
If (x
(x(( + h(x,)]
mn
1=1
s.t. (x,) = arg min g( yz) ya Vi; x; =xx,, if (1, (1)
y.ERPS
where X C R is convex constraint set, and x, E X' and E R are parameters to be trained for the upper-level and lower-level subproblems at agent i, respectively. Here, ((x,) (x,, (x.)) = 1 "ー f (x;;; E.g) is the local objective function, and h(x,) is a convex proximal function (possibly non-differentiable) for regularization. The equality constraints x; = X ensure that the local copies at connected agents and i' are equal each other, hence the name "consensus form."
3

---

Under review as a conference paper at ICLR 2023
Table 1: Comparisons among algorithms for bilevel optimization problems. Sample complexities (both upper and lower) as defined in the sense of achieving an e-stationary point defined in (2) is the size of dataset each agent.
Algorithms
Constriants
Samp. Complex.
Comm. Complex.
Decentralized
BSA Ghadini & Wang 2018
()
SUSTAIN
Khanduri
O(c
RSVRB
Guo & Yang
2021
x
((e=1-9)
x
VRBO Yang et
2021
O(c-1-9)
AID BiO /TT. BiO Ji et al.
2021
x
((nc=t)
TTSA Hong st
2020
Ole 6/2)
STABLE
Chen et al.
2022
O(e=²)
DSBO
Yang al.
2022
x
O(c
((c)))
SPDB
Lu at
2022
O(e=7)
O(e=))
DSBO
Chen al.
20226
x
O(e**)
O(c=3)
VRDBO Gao al.
2022
x
O( (1))1.))
O(e
INTERACT Liu et al.
2022
x
O(ne-t)
O(e7))
INTERACT-VR Liu
2022
O(yTKe +x)
O(eT))
Promethous [Ours.]
Olyake" + m)
O(("))
Next, we define the notion of e-stationarity point for Problem I for convergence performance
characterization. We say that {x,, Y., Vi E [m]] is an e-stationarity point if it satisfies:
E|| - 1 & X1I E||x x 1ix-181 18
EEIyy 11
S,
Saddle point error
Consensus error
lower problem error
..... TJT, and X is proximal point that will be defined later in Section The first term in 2 quantifies the convergence of the x to a proximal point of stationarity of the global objective. The second term in measures the consensus error among local copies of the upper variable, while the last term in (2 quantifies the (aggregated) error in the lower problem's 's iterates across all agents. Thus, - 0 implies that the algorithm achieves three goals simultaneously: i) consensus of upper variables, ii) stationary point of Problem ([. and iii) solution to the lower problem. As mentioned in Section [ two of the most important performance metrics in decentralized optimization are the sample and communication complexities.
where X 1 > X. A lyT ..... TJ and y*
2) Motivating Applications: Problem ( arises naturally from many interesting real-world applica- tions. Here, we present two motivating applications to showcase its practical relevance:
Multi-ageni meta-learning (Rajeswaran et al. 2019): Meta-learning (or learning to learn) is to find model that can adapt multiple related tasks. A popular meta-learning framework is the model-agnostic meta learning (MAML). which minimizes an upper objective of empirical risk on all tasks. Consider a multi-agent meta-learning task with m lower level problems and m agents collectively solve this meta-learning problem over network. This problem can be formulated as:
THn Σ S (x))((x)) s.t. yi (x) E argmin 9 (x. ; = 1...., m. XEA
y:ERP2
Here, agent has a local dataset with n samples, x E X' is the constrained (e.g., due safety) model parameters shared by all agents, and y, are task specific parameters solved by each agent.
Decentralized min-max optimization (uang et al. 2022): Another application of the constrained decentralized bilevel optimization in (1) is the decentralized nonconvex strongly-concave min-max optimization problem, which is typically seen in, e.g., multi-agent reinforcement learning (Zhang et al.) 2021). fair multi-agent machine learning (Baharlouei et al.) 2019). and data poisoning attack (Liu et al. 2020b). A decentralized min-max optimization problem is special case of decentralized bilevel optimization problem because:
min max
Σ (x,,y)) min Σ (x,yx (x))) (i)) argmin -f (x,y1), Vi. S,ER"2
(xx))((x))))
V.CRP2
1=1
4

---

Under review as a conference paper at ICLR 2023
SOLUTION APPROACH
In this section, we first present the Prometheus algorithm for solving the constrained decentralized bilevel optimization problems in Problem (I) in Sections 4.1
4.2 Then, we provide its theoretical convergence guarantees in Section 4.3 Lastly, we will reveal key insight on the necessity of using
the proposed variance reduction techniques Section [44 Due to space limitation, we relegate the
proof's and the notation Table. 2 to supplementary material.
4.1 PRELIMINARIES
To present the Prometheus algorithm, we first introduce several basic components preparation.
1) Setwork-Consensse Matrix: Our Prometheus algorithm is based on the network conneessusss mixing approach: in each iteration, every agent exchanges and aggregates neighboring information through a consensus weight matrix M E R= We define À as the second largest eigenvalue of the matrix M. Let M se represent the element in the i-th row and the i'-th column in M. The choice of
M should satisfy the following properties: (a) doubly stochastic:
D Σ [M] = 1;
(b) symmetricc: [M] = [M Vi E NN; and (c) network-definer sparsity: [ > 0 if (i,4)) E otherwise [M] ,2 = O, Vi, E.
2) Stochastic Estimators: In Prometheus, we need to estimate the stochastic gradient of the bilevel problem using the implicit function theorem. We note that in the literature of bilevel optimization with stochastic gradient, a commonly adopted stochastic gradient estimator is of the form (Khanduri
al. 202T, Ghadimi & Wang 2018 Hong al. 2020
Liu al. 2022):
Vexi, Vel(
V 9 (x,,,, C (
(4)
Lg
where H., A (T((K))) (I- V (e Here, K 440,... ..... K 1} is integer-valuess random variable uniformly chosen from {0,.... K 1}. can be shown that Hr, k is a biased estimator for the Hessian inverse [ "xy9(xxy:0) (x] -1 - (I- V first term in the Taylor approximation, thus resulting large variance and could eventually increase the communication complexity of decentralized bilevel optimizaiton.
predefined parameter and k(K) ~
by
())* However, this estimator has the limitation that it only incorporates the
To address this issue, in this paper, we propose a new stochastic gradient estimator as follows:
H.D = H; 11 Viyg (t.
k(K) 3'
1 Vzyg Yiei (?')
H = 1+
Lg
Lg
p'=1p=1
Lg Vayg (xe.)) ()) H Vy /x...
(5)
Compared to the conventional estimator, the key difference in our new estimator lies in the matrix H. The new Hessian inverse estimator is inspired by ideas stochastic second-order optimiza-
tion (Agarwal et al. 2016). Similar technique to estimate the Hessian inverse can also be found in Koh & Liang] 2). However, our Hessian inverse estimator differ from Koh & Liang (017))
in the following key aspects: (i) In Hessian inverse estimator, we multiply the hessian term V 72, y: { by 1/ Ly as it ensures that L/Lg x V2,g(r, y: {) will have eigenvalue less than 1. Otherwise, the power series of the Hessian Inverse will not converge. In comparison, Koh & Liang
(2017) does not have 1/L,, term because the authors assume w.l.o.g. that the Hessian V Ve,g((., y) < 1, which implies that the authors implicitly assume L. 1. (ii) Koh & Liang) (207)) only designed for solving a conventional single-level minimization problem with loss function L(-). In comparision, our proposed stochastic estimator can be used in bilevel learning especially for solving non-smooth regularizers in the upper-level problems. Note that our H: is in a recursive form that is able to capture the entire Taylor series at once without increasing the sample complexity. Thanks this recursive form, H utilizes O(k2) samples, as opposed to only O(k) samples in the conventional much smaller variance and eventually much lower
H. -esssian inverse estimator, thus leading communication complexity. It is worth noting that although our H, estimator leverages more training samples, the computation cost is the same as that of H due the recursive structure in (5). In Sections 4.3 and [5] we will theoretically and numerically demonstrate the smaller variance of our new estimator over the conventional one.
5

---

Under review as a conference paper at ICLR 2023
4.2 THE Prometheus ALGORITHM.
Our Prometheus algorithm is an advanced triple-hybrid of proximal, gradient tracking, and variance reduction techniques. The procedure of Prometheus can be organized into three key steps:
Step I (Local Proximal Operations): In each iteration t, each agent i performs the following for the upper-level variables:
proximal operations cope with the domain constraint
X (x,,) = arg x x x1,t) + _||x - -|,l| + h(x));
where 7 >
0 is a proximal control parameter and ug,r is an auxiliary vector. The proximal
update rule is motivated by the SONATA method (Scutari & Sun 2019) used in decentralized minimization.
Step (Consensus Update in Upper-Leve Variables): Next, each agent updates the upper and lower model parameters Xg, as follows:
X1 = Σ
[M]xx,, (xx,( - xx,)), Y1,+1 = Via BV
VEN;
where a and /3 are constant step-sizes for updating x- and y-variables, respectively. Note that updating X in Eq. 7 is local weighted average at agent i and plus local update in the spirit of Frank- Wolfe given a proximal point. The right-hand side of Eq. 7 performs a local stochastic gradient descent update for the y-variable at each agent i.
Remark 1. The used auxiliary proximal operator X,, and the resultant local update (xx, (x.,,) x;,{) in the consensus step play an important role helping us alleviate the non-smooth objective challenge. It will be difficult to achieve convergence guarantees in decentralized learning if we
X1,+1 = (x.,
a,;,) = argmin|| (X,, - , instead. See proof details Lemma xEX
and 7 in our Appendix.
Step 3 (Local Seriance-Reduced Stochastic Gradient Estimate): In the local gradient estimator step, each agent estimates its local gradients using the following stochastic gradient estimators:
V (((x,, # E Vi(xia, Eo), if mod g) 0,
(8a)
ts, Ejes.. (V, (xi, Eis) - Vs (x
1
Vg(Xi,))8..)) = =1 En Vo(xianiitiss)) (x S.,. Ejes., (Vg (X,,) Si) -Vg (x.1111
if mod(t, g) = =0,
dx(x))))))))
(8b)
Here, S is the sample mini-batch in the t-th iteration, and q is pre-determined inner loop iteration number. The local stochastic gradient estimation a recursive estimator that shares some structural similarity with those in SARAH (Nguyen et al., 2017). SPIDER (Fang et al. 2018), and PAGE (Li et al. (02T)) used for traditional minimization problems.
Step 4 (Gradient Tracking in Upper-Level Parameters): Each agent i updates Ui,t and Vi, by averaging over its neighboring tracked gradients:
Σ
1 - 11xx-111
Va, = d((x,,)))). (9)
PEN,
To summarize, we illustrate the Prometheus algorithm in Algorithm T
4.3 CONVERGENCE PERFORMANCE ANALYSIS OF THE Prometheus ALGORITHM
Now, we focus on the convergence performance analysis for the proposed Prometheus algorithm. Before presenting the main convergence results, we first state several technical assumptions:
Assumption 1, For all Ç supp (mg) where supp(æ) the support of n, X, X C RPI ,y E R the lower-level function g has the following properties: i) g(x, y: is Hy strongly convex with
Bg > O, Vxg y: is LypLichhitzz continuous with L, > 0: ii) (x, y; 1)12 < Cgny for some Cgsy > 0, V2 xx. and 9x, y: are Lipschitz continuous with constants L > and Tog,, respectively.

---

Under review as a conference paper at ICLR 2023
Algorithm 1 The Prometheus Algorithm at Each Agent i.
Set parameter pair (x,0 X,,o-rt,)) (x" .").
Calculate local gradients: 04,0 V (x..0 o
for t = 1, 1,..., I do Update local parameters (5,,441,,,444) in Eq. if Prometheus: then
Compute local estimators (X. (X., as in Eq. (8) end if
Prometheus-SG: then
Compute local estimators (x. (1x,,,, in Eq. (10)
end
Track global gradients (U.,+1, Vi,+1) in Eq. end for
Assumption 2. For all & E supp (my) where supp(T) is the support of T, x X.X C R the upper- level function has the following properties (x. Vy f(x, (W.It. y) are Lipschitz smooth continuous with constant Ir, 2 0, Tr,, 2 O. (x, s Cf. : for some Cj 2 0. Assumption 3. i) The stochastic gradient estimate of the upper-level function satisfies: fx y: E) fxx S of: and ii) The stochastic gradient estimate of the lower- level function satisfies: [&[[[ yxllv/l(xxyy
(x. y) S og.
We note that Assumptions e.g.. Ghadimi & Wang (2018) Khanduri et al. (202T). In addition, Assumption a) has been verified
2 and b) are standard in the literatures of bilevel optimization (see,
in (Khanduri et al. (021)..
To establish the convergence result of Prometheus, we first prove the Lipschitz-smoothness of the new gradient estimator proposed in (5). which is stated as follows:
Lemma 1. (Lipschitz-mmoothness of the new stochastic gradient estimator in (5) If the stochastic functions y)) and () satisfy Assumptions
D
then we have (i) for fixed y e
IRP,, f ()) - f x2. y: S L3 X1
X2 Vi,,, X2 E RP;; and (ii) for a fixed
x E Re! | y1: V yx:
Σ L, lly: Y2ll Vy1.22
Y2 E RP2. In the above + 60 Bey (2n
expressions, L 0 is defined as: L7 == 2L,
+ 6C
9.v 12, 2ugLo-1
K
L3
6C2 9.y 97,
K L. E5= 2. 26-1) 12 2
Remark 2. We note that the Lipschitz-smoothnes. constant I. of Lemma is smaller than that of the conventional estimator in which we denote as Tecoue here, i.e., T.g Leoon- This also shows superiority of our new estimator. Due to space limitation, we state the definition of Leone in Lemma in the appendix.
Next, we need the following Lipschitz-conie continuity properties of the approximate gradient Vx(, the lower level solution y*, and the true gradient V((x), which have been proved in the literature:
Lemma 2.
(Ghadimi & Wang
2018) Under Assumptions 2 we have [x
(((x)l S T. (x)-yll- ly (x))-y" (x2)) S Ty ||x--X X2 VV
S Th X1 X2 for all X1,1,X2 TR y E RP4, where the Lipschitz constants are defined as:
A Ls= +
Cozx + Cr₁s( Logxx + Lizee COsx) L L+ LCSEx, and Ly - Cazx
Ma
Ma
Ps
Lemma establishes the smoothness of the implicit function in T which only relies on the Assumptions [ to hold. Lastly, following the same token as in (Hong et al., 2020), we show a critical fact on the exponentially fast decay of the bias of our stochastic estimator (5), which is stated below.
Lemma 3 (Exponentially Decaying Bias). Under Assumptions H the stochastic gradient estimate
of the upper level objective in 5 satisfies [V y)
yx
Czzy Ctz (1- (1-
Ag
The assumptions and Lemmas stated next.
B above lead to the main convergence result of Prometheus which
7

---

Under review as a conference paper at ICLR 2023
Theorem 1. Under Assumption 3 if the step-sizes a a min (1-A)m
(1-A)m _
(3vB(Lett) 6+3r BUBL7 6+37 : 3L,
(1- Nyg
20 -(1 TVB(1-A) Ha(l-A) gal
2107. 91; m ,+ (1 (1 6:37].
230401322 12m(1- 27(1
1m 24m13
12m
3 $
ViOLy 3Lg
(²(1-N)²
)²
}. then the outputs of Prometheus satisfy: 81L7
24a
Toby'
14001227
2 xxx+ Blyy, x;1l 0 (
B X & x.11 E||x,
Remark 3. is worth noting that, compared to existing works on decentralized bilevel optimization, the major challenge proving the convergence results in Theorem [ stems from the proximal operator needed to solve the upper-level subproblem, which prevents the use of conventional descent lemma for convergence analysis (see Eq. (3 in the appendix). Also, compared to single-agent constrained bilevel optimization, one cannot provide theoretical convergence guarantee by using the direct projection method X = arg min - (Xi,t ru, as in (Hong et al. 2020 Chen et al. 2022a) due the gradient tracking procedure in the decentralized learning. Instead, we use a different proximal update rule as shown in (6). We will numerically show in Section [5 that Prometheus with the direct proximal operator can only converge
neighborhood of a stationary point. Further, Theorem immples the following sample and communication complexity results:
Corollary (Sample and Communication Complexities of Prometheus). Under the conditions of Theorem I to achieve an e-stationary solution, Prometheus requires that: i) the total number of communication rounds is
and ii) the total number of samples is O(ynke" + n).
4.4 DISCUSSION: THE BENEFIT OF VARIANCE REDUCTION IN Prometheus
Since the variance reduction in ( in Step of Prometheus requires full gradient evaluation, is tempting to ask what is the benefit of using the variance reduction technique. In other words, could we relinquish variance reduction (VR) in Step 3 to avoid full gradient evaluation? To answer this
question, consider changing Step 3 to the following basic stochastic gradient estimator without VR:
y.. = f( Eio);
d(, = Vg(x,,,, Vi.ei Cio)-
(10)
Interestingly, the following convergence result states that there always exists a non-vanishing constant independent of m, n, and a if (10) is used in Step 3 of Prometheus (i.e., constant only dependent on problem instance and cannot be made arbitrarily small algorithmically).
Proposition 3. Under Assumptions 1 with step-sizes a S minf 831.
1-A " 37.,' (/F((ett) 6437'
(1-A)m
6m 18 2 (T
T// x(1-)) (1- (1-A)22316
/Br}. 3 S min 1-1
(1 (1-X)*
(TT we
BL,
have the following result if 100 replaces Step 3 in Prometheus,
[E]xx 1 x B 18x 0 (117) Co,
(11)
T
where the constant C² is defined as Cy A 9(6+3r)( (( ConyCry Mg Lg
(1
40(5+4a ar o
27(1 x)
Remark 4. A key insight of Proposition is in order. The SG-type update in 110 is similar to the SG- type update in unconstrained bilevel optimization in the single-agent setting (1 et al. 202T). However, unlike the SG-type method in jli et al. (202)) that can approach zero at an O(1/VT convergence rate, the SG-type method can only approach a constant error C² at an O(1VVT) convergence rate in the constrained decentralized setting. The non-vanishing constant error C² is caused by the variance of and o² of the stochastic gradient. This make the benefit of using the variance reduction techniques to eliminate the {a,, 0g -variance in order to approach zero asymptotically.
5 NUMERICAL RESULTS
In this section, we will first conduct experiments to demonstrate the small variance of our new stochas- tic gradient estimator. Then, we will compare Prometheus" convergence with several baselines.
8

---

Under review as a conference paper at ICLR 2023
VNSI
CPA120
HHST
CRA1-00
Promatheut handhhoo D.00
Promatheut
Prometheut
amaahuu Prox bi5a.
300
10
Promithwunn
1n
DSS0
10'
500
1092
500
1000
230 Communication round
Communication
Communication round
Communication round
Figure 2: Five-agent network.
Figure 3: Ten- Ten-agent network.
1) New estimator conventional estimator: Note that the major dif- ference between the new and conventional estimators lies in how they esti- mate the Hessian inverse of the matrix A. Thus, it suffices compare the Hessian inverse approximations. The conventional estimator to estimate
Varfance
((K) p=1 the A 1! can be denoted A- cone = K p=1 (I- As), while the new es-
timator can be denoted as A- = E y==1 TT (I-)). To see the ben- efits of our estimator and due the high complexity of computing matrix inverse, here we consider a small example A = [00.25, 0.0). (0.0, 0.25]]- so that A = [[4, 0), [0, 4]]. Let A, be a random matrix obtained from A plus Gaussian noise. We use Azo and A to estimate A
Cansentioonl Extimator
Nona Extimator
Figure 1: Hessian inverse estimator comparison.
respectively. We run 10000 independent trials with K 10 and the results are shown in Fig. I We can see from Fig. [ that the new Hessian inverse estimator has a much smaller variance than the conventional one. Additional experiments on varing K and different matrix are relegated to our Appendix.
2) Convergence Performance: We verify our theoretical results of Prometheus by conducting exper- iments on a meta-learning problem tested on MNIST (LeCun et al. 1998) and CIFAR-10 (Krizhevsky) et al. 2009) datasets. Due to space limitation, we provide additional experiments on syper-parameter optimization the appendix. Due to the lack of existing algorithms for solving constrained decentral- ized bilevel optimization problem, several stripped- down version of Prometheus:
compare the convergence performance of Prometheus against
Prometheus with Stochastic Gradient (Prometheus-SGe Prometheus-SG is the SG-type algorithm discussed in Section 4.4 (x Vi.t) = f Yr.e, Ewo): di (x.,,,, = Vg(X,,, (10).
Prometheus with Direct Proximal Method (Prometheus-dir), Instead of performing x,, arg minxex [u,,, x x1,)) + | x,,l|| + h(x,)) in Prometheus, Prometheus-dir directly adds the constraints on x: _1,- = arg minxex || (xi, 112.
Proxinal Decentralized Stochastic Gradient Descent (-rrx--DGGD This algorithm is motivated by the DSGD algorithm, which can be viewed as Prometheus without using gradient tracking. Specifically, we updates local gradient u V f (x Yi,ri Ev); Vi,i Vg(x,, (' Çio).
We also note that the Prox-DSGI algorithm can be seen as a generalization of DSBO (Yang et al.] 2022). SPDB (Lu et al. dir can also be seen as an extension of the algorithm INTERACT (Liu et al. 2020a) to handle the constrained decentralized bilevel optimization problem. We compare Prometheus with these base- lines using a two- Swo-hidden-layy layer neural network with 20 hidden units. The consensus matrix is chosen 3Amas(L)
2022 DSBO (Chen et al. 2022b) with the proximal operator. Prometheus
as M I- 2L where L is the Laplacian matrix of G and >max (L) denotes the largest eigenvalue of L. Due to space limitation, we relegate the detailed parameter choices of all algorithms to the appendix. In Fig. 2
compare the performance of Prometheus, Prometheus-Sie Prometheus-dir and Prox-DSGD on the MNIST and CIFAR-10 10 datasets with with a five-agent network. The network topology can be seen in Fig. in Appendix D We note that Prometheus converges much faster than than all other algorithms in terms of the total number of communication rounds. In Fig. 3 we also observe similar results when the number of tasks (and agents) is increased 10. Our experimental results thus verify our theoretical analysis that Prometheus has the lowest communication complexity.
CONCLUSION
In this paper, we studied the constrained decentralized mmnconve--stronglyyeee tion problems. First, we proposed an algorithm called Prometheus with a new stochastic estimator. We then showed that, to achieve an e-stationary point, Prometheus achieves sample complexity of O(Kvñi + n) and a communication complexity of O(e-!) ). Our numerical studies also showed the advantages of our proposed Prometheus and verified the theoretical results. Collectively, the results in this work contribute to the state of the art of low sample- and communication cummuiicaionncompleitty constrained decentralized bilevel learning.
bilevel optimiza-
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Naman Agarwal, Brian Bullins, and Elad Hazan. Second-order stochastic optimization in linear time. stat, 1050:15, 2016.
Sina Baharlouei, Maher Nouiehed, Ahmad Beirami, and Meisam Razaviyayn. Rbackslashenyi fair inference. arXiv preprint w7Xiv:1906.12000 2019.
Anouer Bennajeh, Slim Bechikh, Lamjed Ben Said, and Samir Aknine. Bi-level decision-making modeling for an autonomous driver agent: application in the car-following driving behavior. Applied Artificial Intelligenee 33(13):1157-117, 2019.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM Iransactions on intelligent systems and lechnology (TIST), 2(3):1-27, 2011.
Tianyi Chen, Yuejiao Sun, Quan Xiao, and Wotao Yin. A single-timeseale 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 arXiv:2206.0550 05670, 2022b.
Ashok Cutkosky and Francesco Orabona. Momentum-basee variance reduction in non-convex sgd. In Advances in Neural Information Processing Systems, pp. 15210-15219, 2019.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex opti- differential estimator. Advances in Neural Information
mization via stochastic Processing Systems, pp. 689-699 2018.
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient- hyperparameter optimization. In International Conference on Machine Learning. pp. 1165-1173. PMLR, 2017.
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
Hongchang Gao, Bin Gu, and My T Thai. Stochastic bilevel distributed optimization over a network. 2022.
arXiv preprint ar arXiv:2206.11555
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246 2018
Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo. On differentiating parameterized argmin and argmax problems with application bi-level optimization. arXiv preprint arXiv: 1607:0/607. 2016.
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.
Zhishuai Guo and Tianbao Yang. Randomized stochastic variance-reduced methods for stochastic bilevel optimization. arXiv e-prints, pp. arXiv-2105, 2021.
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.05 2020.
Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Accelerated zeroth-order and first-order momentum methods from mini to minimax optimization. Journal of Machine Learning Research, 23(36):1-70, 2022.
Kaiyi Ji. Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference Machine Learning, pp. 4882-4892 PMLR, 2021.
10

---

Under review as a conference paper at ICLR 2023
Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A near-optimal algorithm for stochastic bilevel optimization via couble-momentum Advances in Neural Information Processing Systems, 34, 2021.
Pang Wei Koh and Perey Liang. Understanding black-box predictions via influence functions. In International conference muchine learning, pp. 1885-1894, PMLR, 2017.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. Available: http://yann. lecun. com/exdb/nniist, 1998.
Guoqing Li, Rufeng Zhang, Tao Jiang, Houhe Chen, Linquan Bai, and Xiaojing Li. Security- constrained bi-level economic dispatch model for integrated natural gas and electricity systems considering wind power and power-to-gas process. Applied energy, 194:696-704, 2017.
Zhize Li. Hongyan Bao, Xiangliang Zhang, and Peter Richtarik. Page: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference on Machine Learning, pp. 6286-6295, PMLR, 2021.
Mingrui Liu, Wei Zhang, Youssef Mroueh, Xiaodong Cui, Jarret Ross, Tianbao Yang. and Payel Das. A decentralized parallel algorithm for training generative adversarial nets. In Proceedings of Advances in Neural Information Processing Systems, volume 33, 2020a.
Sijia Liu, Songtao Lu, Xiangyi Chen, Yao Feng, Kaidi Xu, Abdullah Al-Dujaili, Mingyi Hong, and Una-May O' O'Reilly. Min-max optimization without gradients: Convergence and applications to black-box evasion and poisoning attacks. In International Conference on Machine Learning, pp.
6282 6293. PMLR, 2020b.
Zechun Liu, Haoyuan Mu, Xiangyu Zhang, Zichao Guo, Xin Yang. Kwang-Ting Cheng, and Jian Sun. Metapruning: Meta learning for automatic neural network channel pruning. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 3296-3305, 2019.
Zhuqing Liu, Xin Zhang, Prashant Khanduri, Songtao Lu, and Jia Liu. Interact: Achieving low sample and communication complexities in decentralized bilevel learning over networks. arXiv preprint arXiv:2207. 132883 2022.
Songtao Lu, Xiaodong Cui, Mark S 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.
Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-based hyperparameter optimization through reversible learning. In International conference machine learning, pp. 2113-2122. PMLR, 2015.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takac. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In International Conference on Machine Learning, pp. 2613-2621. PMLR, 2017.
Fabian Pedregosa.
Hyperparameter optimization with approximate gradient. In International conference on machine learning, pp. 737-746. PMLR, 2016.
Vítor O Pochmann and Fernando J Von Zuben. Multi-objective bilevel recommender system for food diets. In 2022 IEEE Congress on Evolutionary Computation (CEC), pp. 1-8. IEEE, 2022.
Clarice Poon and Gabriel Peyré. Smooth bilevel programming for sparse regularization. Advances in Neural Information Processing Systems, 14:15-5-15 2021.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. Advances in neural information processing systems, 32, 2019.
Gesualdo Scutari and Ying Sun. Distributed nonconvex constrained optimization over time-varying digraphs. Mathematical Programming. 77(11):97-5444 2019.
11

---

Under review as a conference paper at ICLR 2023
Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems, 34, 2021.
Shuoguang Yang. Xuezhou Zhang, and Mengdi Wang. Decentralized gossip-based stochastic bilevel optimization over communication networks, arXiv preprint arXiv:2206. 10870, 2022.
Haifeng Zhang, Weizhe Chen, Zeren Huang, Minne Li, Yaodong Yang. Weinan Zhang, and Jun Wang. Bi-level actor-critic for multi-agent coordination. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 7325-7332, 2020.
Xin Zhang, Zhuqing Liu, Jia Liu, Zhengyuan Zhu, and Songtao Lu. Taming communication and sample complexities in decentralized policy evaluation for cooperative multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
12


Reviews:
[{"review_id": "npQzy3n10s", "reviewer": "Reviewer_Rqm7", "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 introduces a new algorithm, Prometheus, for the composite stochastic bilevel optimization problem in the decentralized setting. In particular, the paper considers the setting where we have a distributed optimization problem on $m$ agents, each of which has a loss function of the form $l(x) + h(x)$ where $l(x)$ has bilevel, finite-sum structure and $h$ is a constraint function with an easy-to-compute proximal operator. The agents are connected to each other via a decentralized network (i.e. there is no central node to exchange iterates with, and therefore the agents have to solve a consensus problem as well during the optimization process). The bilevel optimization problem is nonconvex-strongly-convex (the outer function is nonconvex and smooth, the inner function is strongly convex), this problem has been solved before in the decentralized setting, but only with simple projection constraints (e.g. as in [1]). The algorithm introduced here, Prometheus, solves this problem in the setting where $h$ can be an arbitrary constraint but whose proximal operator is easily computed. Prometheus achieves the same communication complexity and local sample complexity as INTERACT-VR from [1], but can do so under more difficult constraints.\n\n[1] Zhuqing Liu, Xin Zhang, Prashant Khanduri, Songtao Lu, and Jia Liu. INTERACT: Achieving Low Sample and Communication Complexities in Decentralized Bilevel Learning over Networks. MobiHoc 2022", "summary_of_the_review": "I think this is a paper which is quite borderline, but for which the weaknesses outweigh the strengths. My biggest concern with this paper is that I am not sure where the difficulty is in the new proximal setting. I cannot really see it in the proof, and I don't think it is highlighted enough. Moreover, the experimental evaluation is not enough to see the benefits of some of the proposed techniques (like the new stochastic gradient estimator). The discussion on the necessity of variance reduction is somewhat flawed (for the reason outlined above), and as such I'd prefer to see that section rewritten as well.\n\n-----------------------\n\nPost-rebuttal summary: \nI thank the reviewers for their long, detailed responses. The examples given are satisfying to me, and I think there is some technical difficulty that the authors have overcome here. However, after discussion with other reviewers, I am not convinced the technical novelty here may not be enough, especially given that the Hessian estimator used is not novel. As such, I can not recommend acceptance.", "strength_and_weaknesses": "- (Strength) The introduced algorithm, Prometheus, achieves a sample complexity of $\\mathcal{O} (\\sqrt{n} K \\epsilon^{-1} + n)$. This is currently the best-known sample complexity for finite-sum stochastic bilevel optimization problems. The same can be said for the communication complexity $\\mathcal{O} (\\epsilon^{-1})$.\n\n- (Strength) The proposed algorithm can handle complex constraints through the use of the proximal operator, enabling more applications than previous algorithms.\n\n- (Strength) The authors introduce a new recursive estimator for the stochastic gradient of the bilevel problem (see eq. 5), and this new estimator seems to show some benefits in practice over the conventional estimator used by previous works.\n\n- (Weakness) The authors do not give many examples of the constraints their algorithm can solve, and their relevance to practice. The motivating examples all do not really make use of the new proximal formulation. \n\n- (Weakness) The benefits of the new recursive estimator are only illustrated in one experiment, and it is difficult to see the benefit since Figure 1 only tests out this estimator on a single matrix with fixed norm. Can you plot how the estimator performs for varying norm of ||A^-1||? How about with increasing variance? There is too little information to figure out how it performs empirically.\n\n- (Weakness) It is not clear why the ordinary inverse Hessian estimator does not work for this problem, given that it works just fine for INTERACT-VR and achieves the same rate for the unconstrained setting.\n\n- (Weakness) The discussion about the necessity of VR is a little misleading. The authors introduce a variant of Prometheus without variance reduction, and then give an upper bound for this variant that shows it does worse than the variance-reduced version. However, this is not a correct way to show the necessity of some technique-- at best, it provides some evidence for this and nothing more. The correct way would be to give a lower bound, but no such lower bound is given here.\n\n- (Weakness) The authors do not really explain why the proximal setting is significantly more difficult than the projected setting. In ordinary, non-bilevel, stochastic optimization, the extension from the projected case to the proximal case is very simple and straightforward. What is the source of difficulty here?", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "_2XFcATw28", "reviewer": "Reviewer_gfGV", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 studies constrained decentralized bilevel optimization where the inner-loop problem is finite-sum, smooth and strongly convex,  and the outer-loop problem is finite-sum, smooth and nonconvex. By combing (a) gradient tracking, (b) variance reduction and (c) a pseudo-gradient trick based on proximal operator, the paper designs a decentralized algorithm with both sample complexity and communication complexity matching the unconstrained setting.", "summary_of_the_review": "Overall, I am positive with the submission and am willing to support its acceptance if my questions can be well addressed.\n\n\n\n\n\n\n", "strength_and_weaknesses": "# Strength\n\n- I find this paper very well written. Since I am unfamiliar with the previous  literature in this topic, the clean and concise writing of this paper makes it quite easy for me to understand the intuition behind the algorithm and the key ideas in the proof.\n\n- This setting seems to be important, and hasn't been addressed by previous works. The designed algorithm looks quite reasonable and the derived complexity aligns with my intuition for finite-sum optimization and two-timescale style algorithms.\n\n# Weakness (and questions)\n\n- Since the inner-loop problem is strongly convex and smooth, one could expect that (also easy to show?) the $y_i$ variable will always stay sufficiently close to $y_i^\\star (x_i)$. This means the analysis of the proposed algorithm is very similar to the existing works for distributed composite smooth nonconvex optimization? Therefore, it is a bit unclear to me how much technical novelty the submission possesses in terms of either algorithmic design or techniques used in the analysis.\n\n- This is a rather general question about the motivation of considering general topology in decentralized optimization: Can you provide a non-artificial practical problem where the network topology is not a star and the network-consensus matrix trick is indeed deployed for the sake of distributed optimization? I'd like to see some real application with supportive reference, not just some scenario that only exists in the introduction of a theory paper. \n\n# Technical correctness\n\nI only performed a high-level check of the proofs and they look correct to me.\n\n\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": "Not applicable"}, "extra_text": {}}, {"review_id": "8mU_Di9U4e", "reviewer": "Reviewer_1rpW", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "In this work, the authors study the problem of decentralized stochastic bi-level optimization problems with upper level constraints. The authors propose Prometheus, an algorithm that combines ideas from bi-level optimization, proximal gradient computation for constrained optimization, variance reduction for stochastic optimization as well as gradient tracking for decentralized optimization. With all of the components combined, the algorithm achieves $O(1/\\epsilon)$ communication and sample complexity, a state of the art result. To demonstrate that at least some complexity is necessary, the authors showcase that even removing one component, variance reduction, can lead to solutions that do not asymptotically converge to the true solution. The theoretical results are complemented with experimental evaluations.", "summary_of_the_review": "In summary, I am in favor of accepting this work and I am open to further increasing my score if the authors address my concerns above.", "strength_and_weaknesses": "Regarding strengths, to the best of my knowledge no other work has jointly combined tools from variance reduction, decentralized optimization, proximal gradients for constrained optimization and bi-level optimization in a single algorithm. All of the tools are unified in a single analysis in order to obtain an optimal sample and complexity result.\n\nRegarding weaknesses, there are two points where additional elaboration may help make the contribution of this work clearer.\n\nIn Section 4.1.2, the authors propose a new Hessian inverse estimator that is based on the Taylor series approximation for the inverse matrix. To me it seems very similar to the Hessian inverse estimator of [1]. It also uses the same Taylor approximation formula and the same recursive update. Could the authors elaborate on the differences with [1]?\n\nIn Section 4.4, the authors highlight that variance reduction is necessary to achieve the $O(1/\\epsilon)$ convergence rates in sample and communication complexity. My understanding is that this phenomenon would also appear in a stochastic optimization problem with domain constraints. This is independent of the source of the noise (sampling of $f$ or $g$) and orthogonal to the decentralized aspect. It would be appreciated if the authors would highlight which aspects of 4.4 are unique to their problem.\n\n\n\n[1] Pang Wei Koh, Percy Liang, Understanding Black-box Predictions via Influence Functions, ICML 2017\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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject