SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization
Authors: Shuchen Zhu
Boao Kong
Songtao Lu
Xinmeng Huang
Kun Yuan
Venue: NeurIPS 2024 poster (2024)
Keywords: non-convex optimization
decentralized bilevel optimization
transient iteration complexity
Primary area: optimization
TL;DR: We develop a unified single-loop primal-dual algorithm framework for decentralized bilevel optimization with the state-of-the-art non-asymptotic convergence rate.

Abstract: This paper studies decentralized bilevel optimization, in which multiple agents collaborate to solve problems involving nested optimization structures with neighborhood communications. Most existing literature primarily utilizes gradient tracking to mitigate the influence of data heterogeneity, without exploring other well-known heterogeneity-correction techniques such as EXTRA or Exact Diffusion. Additionally, these studies often employ identical decentralized strategies for both upper- and lower-level problems, neglecting to leverage distinct mechanisms across different levels. To address these limitations, this paper proposes SPARKLE, a unified single-loop primal-dual algorithm framework for decentralized bilevel optimization. SPARKLE offers the flexibility to incorporate various heterogeneity-correction strategies into the algorithm. Moreover, SPARKLE allows for different strategies to solve upper- and lower-level problems. We present a unified convergence analysis for SPARKLE, applicable to all its variants, with state-of-the-art convergence rates compared to existing decentralized bilevel algorithms. Our results further reveal that EXTRA and Exact Diffusion are more suitable for decentralized bilevel optimization, and using mixed strategies in bilevel algorithms brings more benefits than relying solely on gradient tracking.

SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization
Shuchen Zhu"
Boao Kong" Peking University
Songtao Lu IBM Research songtaa0iib. com
Peking University shuchenzhuāstu, pku, edu. on
kongboaodstu. pku edu. en
Xinmeng Huang University of Pennsylvania x xinmengh@eas upenn edu
Kun Yuan Peking University
kunyuan@pku edu. cn
Abstract
This paper studies decentralized bilevel optimization, in which multiple agents col- laborate to solve problems involving nested optimization structures with neighbor- hood communications. Most existing literature primarily utilizes gradient tracking to mitigate the influence of data heterogeneity, without exploring other well-known pearrogennityy-oorettio techniques such EXTRA or Exact Diffusion. Addi- tionally, these studies often employ identical decentralized strategies for both upper- and lower-level problems, neglecting leverage distinct mechanisms across different levels. To address these limitations, this paper proposes SPARKLE a unified Single-loop Primal-dual AlgoRithm frameworK for decentraLized billvel optimization. SPARKLI offers the flexibility to incorporate various heterogeneity- correction strategies into the algorithm. Moreover, SPARKLE allows for different strategies to solve upper- and lower-level problems. We present a unified conver- gence analysis for SPARKLE, applicable to all its variants, with state-of-the-art convergence rates compared to existing decentralized bilevel algorithms. Our results further reveal that EXTRA and Exact Diffusion are more suitable for de- centralized bilevel optimization, and using mixed strategies in bilevel algorithms brings more benefits than relying solely on gradient tracking.
1 Introduction
Numerous modern machine learning tasks, such reinforcement learning [25], meta-learning [4], adversarial learning [36], hyyer-paramette optimization [19], and imitation learning [3], entail nested optimization formulations that extend beyond the traditional single-level paradigm. For instance, hyper-parameter optimization aims to identify the optimal hyper- hyper-parameters for specific learning task in the upper level by minimizing the validation loss, achieved through training models in the lower-level process. This nested optimization structure has spurred significant attention towards Stochastic Bilevel Optimization (SBO). Since the size of data samples involved in bilevel problems has become increasingly large, this paper investigates decentralized algorithms over a network of agents (nodes) that collaborate to solve the following distributed bilevel optimization problem:
min (xx) = fl, (x))
fllz, v² (x)).
(upper-level)
(la)
'Equal Contribution
1 'Coreepooding Author: Yuan. Kun Yuan also affiliated with National Engineering Labratory for Big Data Analytics and Applications, and AI for Science Institute, Beijing, China.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

8.t. v²(x)= = argmin (9(0,)) v) == 1 Σ gi v) VER*
(lower-level)
(Ib)
In this formulation, each agent i holds private upper-level objective function fs RP and strongly convex lower-level objective function 9s R x RR + defined as:
x R - R
[1 u) = D (a, v: gı y) D (C
where D, and D,, represent the local data distributions at agent i. This paper does not make any assumptions about these data distributions, implying there might be data heterogeneity across agents.
Linear speedup and transient iteration complexity. A decentralized stochastic algorithm achieves linear speedup if its iteration complexity decreases linearly with the network size n. Additionally, the transient iteration complexity refers to the number of transient iterations a decentralized algorithm must undergo to achieve the asymptotic linear speedup stage. The fewer the transient iterations, the faster the algorithm can achieve linear speedup. This paper aims to develop decentralized stochastic bilevel algorithms that can achieve linear speedup with as few transient iterations as possible.
I Limitations in previous works. A significant challenge in decentralized bilevel optimization lies in accurately estimating the hyper-gradient (<)x) through neighborhood communications. Several studies have emerged effectively address this challenge, such as those by [9, 33, 52, 16, 21, 40, 57, 29]. However, existing works suffer from several critical limitations:
Stringent assumptions and inadequate convergence analysis. Many existing studies rely on stringent assumptions to ensure convergence. For instance, references [9, 10, 33, 21, 52] assume bounded gradients, while reference [29] assumes bounded data heterogeneity (also known as bounded gradient dissimilarity). These restrictive assumptions do arise in centralized bilevel optimization, implying their potential unnecessity. Moreover, some of these works suffer from inadequate convergence analysis, unable clarify the transient iteration complexity [9, 33, 10] or provide a sharp estimation of the influence of network topologies [52, 21].
Limited exploration of various heterooeeniity-cooreettiin techniques. Several concurrent stud- ies [16, 57, 40] have utilized Gradient Tracking (GT) [50, 13, 38] to remove the assumption of bounded data heterogeneity. However, it remains uncertain whether GT is the most suitable mechanism for decentralized bilevel optimization. Many other techniques are also useful for addressing data heterogeneity in single-level decentralized optimization, such as EXTRA [45] and Exact-Diffusion (ED) [56, 30, 54] (which is also known as D2 [46]). Even within GT, there are variants including Adapt-Then-Combll
GT (ATC-GT) [50], non-ATC-GT [38], and semi- ATC-GT [13]. It remains unexplored whether these techniques for mitigating data heterogeneity converge and even outperform GT when employed in decentralized bilevel algorithms.
Unknown effects of employing different upper- and lower-level update strategies. In bilevel optimization, the challenges in solving the upper- and lower-level problems differ substantially. For instance, the upper-level problem (1a) is non-convex, whereas the lower-level problem (1b) is strongly convex. Moreover, estimating the gradient at the lower level is considerably simpler compared to estimating the hyper-gradien at the upper level. Understanding the roles of updates at each level is crucial to develop more efficient algorithms. However, most existing algorithms employ the same decentralized methods to solve both the upper- and lower-level problems. For example, references [9, 52, 29] utilize decentralized gradient descent (DGD) for updates both levels while [57, 40, 16] leverage GT, overlooking the potential advantages of mixed strategies.
To address these limitations, several critical questions naturally arise: Should each heterogeneity- correction mechanism listed in [50, 13, 38, 56, 30, 54, 46] be explored one-by-one? Should we consider combining any two of these techniques to update the upper and lower-level problems, respectively? It evident that examining each individual
wwwpoogeeeeeittyyreettte technique, and even exploring their combinations, would involve an unbearable amount of effort.
Main results and contributions. This paper addresses all the aforementioned limitations without exhaustively exploring all heterogeneity-correee coooreecitttooorectoonn techniques. Our main results are as follows.
A unified decentralized bilevel framework. To avoid examining each single heterogeneity- correction technique, we propose SPARKLE, unified Single-loop Primal-dual Algo

---

Table 1: Comparison between different decentralized stochastic bilevel algorithms. K denotes the number of (upper-level) iterations; 1 denotes the spectral gap of the mixing matrix (see Assumption 2): b² bounds the gradient dissimilarity; E is the target stationarity such that Σi=0 (=)))((""))))))) < E; and @ are the dimensions of the upper- and lower-level variables, reflecting per-round communication costs. Assumptions of bounded gradient, Lipschitz continuity, and bounded gradient dissimilarity abbreviated BG, LC, and BGD, respectively. We also list the best-known results single-level GT, EXTRA, and ED at the bottom.
Algorithms
Assumption
A. Rate.
A. Comp.1
1
A. Comm.
Tran, Iter,"
Loopless
DSBO (9]
LC
(pp lggo + 9 los( +++ 15g
N.A.
No
MA-DSBO [10)
LC
(og(
N.A.
No
SLAM [33]
Rzz (og(E)
N.A.
ViR
MDBO [21]
8G
nat Tog(S)
(m-p)
No
Gossip DSBO [52]
8G
nat Tog(()
L log( +
(1-n)
No
LoPA [40]*
BGD
N.A.
Yes
D-SOBA [29]
BGD
W2?
pig
108
(2-0p= (1
n3
Yos
SPARKLE-GT (ours)
None
Vnk
optig
(1-p)²1
(1=p)%/3
Yes
SPARKLE-EXTRA (ours)
optig
Vnk
[1 [1=p)²
SPARKLE-ED (ours)
None
[I-p]²
n
Yes
Single-level GT [2. 28)
None
622
ne3
maN
[1-p1 (1-0/7
n²
Yos
Single-level EXTRA [2]
None
VaR
m23
m12
(2-p)
Yes
Single-tevel ED [2]
Thee convergence rute when K -+ 2o (smaller is better).
evaluations per agent to achieve e-accuracy when e + (smaller is better). 4 The communication costs per agent to achieve e-stationarity when e -3 (smaller is betler).
1 The number of gradien//accchinn/lees
The transient iteration complexity to achieve lincar speedup (smaller is better). "N.A." means that the algorithm cannot
achieve linear speedup or the transient time cannot be accessed from existing convergence analysis.
Additional assumptions beyond Assumption 1.
LoPA solves the personalized problem. where the lower-level objectives are local to agents. a > measures relative sparsity of the mixing weights W., Wy. W.. which can be very small in certain cuses. Here pin Tran. Iter. denotes the smallest spectral gap W., Wy. y. W.. See more discussions in Appendix C.2.3.
frameworK for decentraLized billEel optimization. By specifying certain hyper- parameters, SPARKLE can be tailored to SPARKLE-EXTRA, SPARKLE-ED, and SPARKLE-GT which employ EXTRA [45], ED [56, 30), multiple GT variants [50, 13, 38), respectively, to facilitate the upper and lower-level problems. Additionally, SPARKLE is the first algorithm enabling distinct updating strategies across different levels; for example, can utilize GT in the upper- level but ED in the lower-level, resulting in a brand new SPARKLE-GT-ED algorithm.
schemes. We provide unified convergence analysis for SPARKLE, which immediately applies to all SPARKLE variants with techniques. The analysis does not require restrictive assumptions bounded used in [29]. Moreover, our analysis demonstrates the provable superiority of SPARKI KLE compared to existing algorithms, as evidenced by the convergence rates listed in Table 1. Most importantly, our analysis sis shows that both SPARKLE-EXTRA and SPARKLE-ED outperform SPARKLE-GT (see Table 1), implying that GT is not the best scheme for decentralized bilevel optimization.
A unified and sharp analysis of various heterogeeneity
distinct heterogeneity-correee
such as gradient boundedness used in [9, 10, 33, 21, 52] or data-heterogenete
Mixing strategies outperform employing GT alone. We demonstrate how optimization at different levels affects convergence rates. Our theoretical analysis suggests that the updating strategy at the lower level is crucial in determining the overall performance in decentralized bilevel algorithms. Building upon this insight, we establish that incorporating the ED or EXTRA strategy in the lower-level update phase leads to better transient iteration complexity than relying solely on the GT mechanism in both levels as proposed in [10, 16, 40], see Table for more details.
Comparable performance with single-level algorithms. We elucidate the comparison between bilevel and single-level stochastic decentralized optimization. On one hand, we demonstrate that the convergence performance of all our proposed algorithms is not inferior to their single-level counterparts (see the bottom part in Table 1). On the other hand, by considering specific lower-level loss functions, our bilevel results directly yield the non asymptoti convergence of corresponding
3

---

Table 2:
The transient iteration complexity of SPARKLE with mixed updating strategies at various levels. The smaller the transient iteration complexity is, the faster the algorithm will achieve its linear speedup stage. The first row and column respectively indicate the updating strategy for the upper- and lower-level problems. Please refer to Appendix B.3 for more implementation details and Appendix C.2.4 for proofs.
upper
ED
EXTRA
GT
lower
ED
[1
(1 p)
EXTRA
GT
max
max
(1 [1-pp= 11-))/3
maX
p) [1- 07873
single-level algorithms. This is the first result demonstrating bilevel optimization essentially subsumes the convergence of the single-level optimization.
Our main results are listed in Table 1. All SPARKLE variants achieve the state-of-the-ar asymp- totic rate, asymptotic gradient complexity, asymptotic communication cost, and transient iteration complexity under more relaxed assumptions compared to existing methods.
Related works. A significant challenge in decentralized bilevel optimization accurately estimating the hyper-gradient (x)),, necessitating solving global lower-level problems and estimating Hessian inversion. To this end, various decentralized techniques have been applied in bilevel optimization, including Neumann series in [52]. JHIP oracle in [9], HIGP oracle in [10], and augmented Lagrangian- based communication in [33]. Additionally, reference [29] proposes a single-loop algorithm utilizing decentralized SOBA. To enhance algorithmic robustness against data heterogeneity, recent studies have employed Gradient Tracking (GT) in both lower- and upper-level optimization. However, existing works built upon GT suffer from several limitations. Results of [16, 9] concentrate solely on deterministic cases, while reference [40] addresses personalized problems in the lower-level, which do not require achieving global consensus in the lower-level problem. Moreover, [9, 10] introduce computationally expensive inner loops for GT steps. None of these works can establish smaller transient iteration complexity than D-SOBA for decentralized SBO, even though the latter algorithm won.geeneittycoocctiooo correction technique.
employs no heterogeneity
The unified framework for single-level decentralized optimization has been extensively studied in the literature. References [1, 49, 26) propose frameworks for decentralized composite optimization in deterministic settings, while [2] investigates a framework under stochastic settings. However, none of these works can be directly applied to decentralized bilevel algorithms. Several studies [21, 57] utilize variance reduction techniques to accelerate the convergence of stochastic decentralized bilevel algorithms. Our proposed SPARKLE framework is orthogonal to variance reduction; it can also incorporate auriance-reducee gradient estimation to achieve improved convergence rates. More relevant works on decentralized optimization and bilevel optimization are discussed in Appendix A.
Notations. We use lowercase letters to represent vectors and uppercase letters to represent matrices. We introduce (a (a.:....,.. .n. == [=] ..., x. E TR for brevity. Variables with overbar denote the average over all agents. For example, _² = E'= z//nn We denote A A 1, for matrix A R where 1, E I_" denotes the n-dimensional vector with all entries being one. For a function f(ar, RP x Rº + R, we use [z, v) TRP, (2f(z, y) E IR9 to represent its partial gradients with respect to x and y, respectively. Similarly, V12 (rr y) E Rexq, /22/ (a. y) E R represent the corresponding Jacobian and Hessian matrix. We use the notation & to denote inequalities that hold up to constants related to the initialization of algorithms and smoothness constants.
2 SPARKLE: A unified framework for decentralized bilevel optimization
This section develops SPARKLE, a unified framework for decentralized bilevel optimization, and discusses its numerous variants by specifying certain saper--arrmeters..
2.1 Three pillar subproblems in decentralized bilevel optimization.
When solving the upper-level problem (la), is critical to obtain the hyper-gradien V$(x), which can be expressed as [22]
vΦ(z)= ()((z,((x)) Vieg(z, (x)) [Vi2gla (x))] (2)(z,v(())).
(3)

---

Evaluating this hyper- gradierrdienttt is computationally expensive due to the inversion of the Hessian matrix. This evaluation becomes even more challenging over a decentralized network of collaborative agents. First, the inverse of the Hessian matrix cannot be obtained by simply averaging the local Hessian inverses due to D V229i (ar (x))]= & 1 ( averaging operation cannot be realized through decentralized communication. To overcome these challenges, one can introduce an auxiliary variable 2" +x) [22g((, y² (=)) -V) y (x)) [12]. which is the solution to a quadratic problem
(x))) Second, the global
(x)
argmin ZERV
Ving (1, v,, (x)) /2 (z, y (1))
(4)
2
Once (x) is derived by solving (4), we can substitute it into (3) to achieve (T()).
Following this idea, solving the distributed bilevel optimization problem (1) essentially involves solving three subproblems, where h y (x), 2) = 2² T222 (1, y (x))z V2f((z.y")))
x² = argmin
((),)((x))
(upper-level)
(5a)
5" (x) ar argmin yERv z" (x) argmin
( v):
(lower-level)
(5b)
n
Σ n
he(r, v" (1),
(auxiliary-level)
(5c)
=ER
Given the variable x, one can achieve yy (xx by solving the lower-level problem in (5b). With y (x) determined, (x) can be obtained by solving the auxiliary-Ievel problem in (5c). Subsequently, with 2 (x) available, one can directly compute the hyper-gradien and solve the upper-level problem in (5a) using gradient descent. This constitutes the primary methodology to solve problem (1).
bilevel algorithm essentially solves three subproblems listed in (5), each formulated as single-level decentralized optimization problem. Nevertheless, primary approaches may suffer from nested loops in algorithmic development. A few recent studies [12, 11, 57, 29] propose to solve each problem in (5a)-(5c) approximately with one single iteration, leading to practical single-loop bilevel algorithms. For example, applying a D-SGD step [43] to each of (5a)-(5c) yields the D-SOBA method [29]. while further leveraging the GT technique leads to decentralized bilevel methods in [9, 16, 57, 21].
However, it is less explored whether numerous other segrrggeneity-oorecttinn techniques [50, 13, 38, 56, 30, 54. 46] beyond GT can be incorporated into algorithmic design to achieve even better performance in bilevel optimization. To avoid exploring each case individually, we next introduce a general framework that unifies all these techniques for solving single-level problems.
2.2 A unified framework for decentralized single-level optimization.
In this subsection, consider solving the single-level problem minzere Ei= fi(x)) over network of n nodes. For each k-th (k 0) iteration, we let æ denote the local z-variable maintained by the i-th agent. Furthermore, we associate the topology with a weight matrix W [u,y]ūيe e gax= in which waj E (0, 1) if node j is connected to node otherwise way O. We use bold symbols to denote stacked vectors or matrices across agents. For example, x² = col ... x E _R and W W @ Ip. where & denotes the Kronecker product operator.
A unified framework with moving average. Building on the formulation in [1, 2], we develop unified primal-dual framework with moving average for decentralized optimization: d d + Bx (6)
+++ (1 r) + Ög ++1 = Cx* *+1 Bd*,
Here x* denotes the primal variable, d denotes the dual variable introduced to mitigate the influence of hattahhteroggneity.. g* stacks all (stochastic) gradients evaluated at o for < < < n, r" denotes the momentum introduced to boost training with coefficient 0 [0, 11, and a > 0 is the learning rate. Matrices A, B, C E I pm are adapted from the mixing matrix W, which determine how agents communicate with each other. See Appendix B.1 for more detailed motivations.
Framework (6) unifies various decentralized techniques in the literature. For instance, by letting 0 = 1 and specifying A, B, C delicately, framework (6) reduces to ED, EXTRA, and numerous GT
5

---

Algorithm SPARKLE: A unified framework for decentralized stochastic bilevel optimization
Require: Initialize x = =y z = r O, do
= dg
d
0, learning rate 0rky Se, Nes Os.
for k 0,1,... ; K - do
y g++ = Cyyt - BxArra B
d d B Byy ++
> lower-level update
g.
zt *++1 = =C, A.A.p - -B.d.
d d + B, +
> auxiliary-level update
p+1 (1- (1-0s)r* 0x)rr* +0:u;
> momentum update
x = C,x² - agA,r Artt B.d
d d + B,x
> upper-level update
end for
variants, see Table and Appendix B.1 for more details. Framework (6) is closely related to the unified decentralized method developed in [1, 2]. The primary difference lies in the incorporation of the momentum variable r", which can help improve the transient iteration complexity of the framework (6) and relax the smoothness condition for bilevel algorithms [11]. A detailed comparison between framework (6) and that proposed in [1, 2] is provided Appendix B.2.
2.3 A unified framework for decentralized bilevel optimization.
By utilizing the unified framework (6) to approximately solve each subproblem in (5) with only one iteration, we achieve SPARKLE, unified single-loop framework for decentralized bilevel optimization. In particular, we independently sample data E, ~ D C ~ Dg. within each node at iteration k and evaluate stochastic gradients/lccobian/HHeee
as follows
t = F. (f J Cr
b =
of V2G.(2
H = Gat,,
Next we stack the descent directions for variables of each level as follows
lower-level stochstic gradient:
v* col(ef ... u
auxilliaryIeveel stochstic gradient:
pd = col( 2F ..,... 2 6%).
upper-level stochstic gradient:
u (1f - J =
k+1 .... 1he Jh At+1..
The SPARKLE algorithm is detailed in Algorithm 1. In this algorithm, we utilize different dual variables d, and communication matrices A., B., C, for each variable E {x, y, 2} to optimize their respective objective functions. We momentum r² only for updating the upper-level variable, which is sufficient to enhance convergence of bilevel algorithms and relax the smoothness condition.
Versatility in decentralized strategies. SPARKLE is highly versatile, supporting various decentral- ized strategies by allowing the specification of different communication matrices A,, B., and C,, 1/2, and C, W for any s e fax, y. 2), SPARKLE will utilize EXTRA to update variables y. and z, resulting in the SPARKLE-EXTR. variant. Other variants can be achieved by setting A,, B,, and C, according to Table 3. These variants can be implemented more efficiently than listed in Algorithm 1, see Appendix B.3.
For example, by setting A, B, (I w)
Flexibility across optimization levels. SPARKLE supports different optimization and communi- cation mechanisms for each level of (5), which can be directly achieved by choosing different A,, B. and C, matrices for each level s E {ar, y, 2.. J. For example, SPARKLE can utilize GT to update the upper-level variable x while employing ED to update the auxiliary- and lower-level variables and z. Throughout this paper, we denote SPARKLE using the decentralized mechanism L for the lower-level and auxiliary variables, and U for the upper-level in Algorithm 1, by SPARKLE- L- or simply SPARKLE-L if L U. In addition, SPARKLE even supports utilizing different mixing matrices W.. W y. W. across levels.
3 Convergence analysis
In this section, we establish the convergence properties of the SPARKLE framework and examine the influence of different decentralized techniques utilized across optimization levels.

---

Table 3: SPARKLE facilitates different decentralized techniques by specifying A., B., C, for se (2, v, 2). We denote the stacked local variables and the associate gradients estimates by y, 2) and g(s). respectively. update rule refers specific algorithmic recursion each level. See derivations Appendix B.2.
Algorithms
A
B,
C₁
The specific update rule at the k-th iteration.
ED
W
(I W
W,
g W. (25 - - a (g(st+)) - g(s*1))
EXTRA
I [I W W
g++ W. (28 - - -a (g((st)l) g(s*))
ATC-GT
W I -- W W s
W. (s - -ht), h = W. (h + +g( - -)(s)))
Semi-ATC-GT
W, I I- W
W s Was -ahh, h, W. (h. + +g((*+1) - -g(st))
Non-ATC-GT
I I I- W W s W.s -ah h W.h + g(sh+1) g(s*)
3.1 Assumptions
Before presenting the theoretical guarantees, we first introduce the following assumptions used throughout this paper.
Assumption 1. There exist constants Pa Lg,0, L, Ln lgg2 such that for any S i S
1. fe. Vga Vag. are Lf,1, Lg Lipschitz continuous, respectively;
2. 22fi (I, (x)) S for any x E IR:3
3. gı(2, is M4 -trronnyy convex with respect for any fixed æ E R..
Moreover, we define L max L1,11 4, _ and L/ Pgg
Assumption 2. For each E {z, y, 2}. the corresponding mixing matrix W. E g2xx is non-negative, symmetric and doubly stochastic, ie.,
W. W.T. W,1, 1 (W.)iy 20, visi,j
and the corresponding communication graph is strongly-comneeted, i.e., its eigenvalues satisfy 1 1= (W,) >2(W.) ... (W,) and p(W.) max (I>2 (W.)l
The value p(W)) referred as the spectral gap in the literature [34. 53. 31] of W., which measures the connectivity of the communication graph. It would approach 0 for sparse networks. For example, it holds that p(W.) = @(1/n²) for the matrix W, induced by a ring graph.
Assumption 3. For any E {x, y, 2), we assume the communication matrices As, B,, Cg used in SPARKLE polynomial functions of W.. Furthermore, assume A,, C. are doubly stochastic, and N.) Span(1,, }. In addition, we assume all eigenvalues of the augmented matrix
C,
B2 B, -B
Lg =
T
are strictly less than one in magnitude, where C. 2 C. - - 1 and L, - 1
We remark that Assumption mild and is satisfied by all choices listed in Table 3. See more discussions in Appendix C.2.2.
Assumption 4. We assume FZ, E), VG, v) and G, v:E) to be unbiased estimates of (z. (2, y). and V2 (z, y) with bounded variances of o² g. o respectively.
3.2 Convergence theorem
Under the above assumptions, we establish the convergence properties as follows. Proof details can be found in Appendix C.
This is more relaxed than Lipschitz continuous ft. bounded V2fi 57, 57, 33. 11].
7

---

Theorem 1. Under Assumptions 1 4, there exist proper constant step-sizes a, B, Y and momentum coefficient such that the SPARKLE framework listed Algorithm will converge as follow:
K
R² VnK
σ²
ob K
B V
+ K (6 + 62,1)
122d211
n
K+1
K
k=0
x
8212
ot
+
18 K 1y.3
6,, k 62.3)
1 K
(KCa + Co)
1 K'
K
where a - m f.1. 9. g,2h, 18g,1; are constants depending only on W.: A.. BR, C. for E {a. 2), and Ca, Cg constants independent of K. See Lemma 17 for their detailed values.
In the deterministic scenario with 0, SPARKLE converges at the rate O(1/K), see the formal theorem and derivation in Appendix C.3. This recovers the rate in [15] under even milder assumptions. Unlike reference [15], which only considers GT in the deterministic setting, SPARKLE a unified bilevel framework for the more general stochastic setting.
I Linear speedup. According Theorem 1, SPARKLE achieves an asymptotic linear speedup as approaches infinity, which applies to all SPARKLE variants regardless of the decentralized strategies employed and whether they are utilized different optimization levels. Furthermore, the asymptotically dominant term x/0//(vnl matches exactly with the single-node bilevel algorithm SOBA [12] when n = 1, implying the tightness of Theorem in terms of the asymptotic rate.
K
Remark 1. We establish an upper bound for the consensus error
x
K
Please refer to Lemma 19 Appendix C.2. for more details.
3.3 Transient iteration complexity
With the non-asymptotic rate established in Theorem 1, we can derive the transient iteration complex- ity of SPARKLE as follows. The proof is in Lemma 18.
Corollary 1. Under the same assumptions as in Theorem 1, the transient iteration complexity of SPARKL SPARKLFEwill with the influence of and a² omitted for brevity-in iss on the order of
max nn in"5m,n' n"8,,, n==2,, n=8,,,n,, nå n8 n
(8)
where 6,, å, only depend W a. As, B., Ca s E U., Their values are in Lemma 18.
We obtain the transient iteration complexity of each variant of SPARKLE by applying Corollary 1. Corollary 2. For SPARKLE-ED and SPARKLE-EXTRA, if we choose W, = W., it holds that
8 O ((1 ((W
8, 0, ((1 -== = 0 p(W,,, -2),
8, = o (11 ((1-(Ww.)) -3)
8 p(W,)) (w)))=²)
(9)
Furthermore, if we choose W. -w = W and denote - p(Wa), the transient iteration complexity derived in (8) can be simplified as n² /(1- 2) Corollary 3. For SPARKLE-GT and its variants with semm/non-ATC--GT, we let W, W..
8, = 0 ((1 (11 -00-pp1p p(W2)) 2),,
by= = d₂ = =0 ((1- ((W))(W,))) w)))))2)
8_- = O ((1 ((11-(WW))) -),
6 0000(1111 - -))
Furthermore, we let W. = -w W and denote p - p( (WW)), the transient iteration complexity derived in (8) can be simplified as pax(n)/11-p),,1 n/(1 /))1
Remark 2 (SOTA transient iterations). Comparing with algorithms listed in Table 1, all SPARKLE variants achieve smaller transient iteration complexity, implying that they can achieve linear speedup much faster than the other algorithms, especially over sparse network topologies with 1 - O.
Remark (GT is not the best technique for decentralized SBO). While GT is widely adopted the literature [16. 21, 57] to facilitate decentralized SBO, a comparison of Corollary and 3 reveals that both SPARKLE-EXTI iteration complexity. This implies that EXTRA and ED better than GT for decentralized SBO.
and SPARKL PPA--LEEEDD outperform SPARKLE-GT in terms of transient

---

3.4 Different strategies across optimization levels
Corollary clarifies how different update strategies for x. y, and impact the transient iterations through constants {6,,6.} for E {a, y; =). Since by = 62 and 6, 8, when W,, W (Lemma 18), we naturally employ the same strategy to update y and z. The following corollary studies the utilization both ED and GT in SPARKLE. See the transient iterations complexity of other mixed strategies in Appendix C.2.4 and Table 2.
Corollary 4. For SPARKLE-ED-GT which uses ED to update y and 2 and GT to update I, if
W
W We and we denote p = ((W,)) 2), it then holds that
8
8 =
which implies that the transient iteration complexity (8) can be simplified as n n²/(1 11 p)
Remark 4 (Mixed strategies outperform employing GT only). Comparing Corollary 3 and 4, we find that using ED to update y and 2 will lead smaller 8, and 82, which improves the transient iteration complexity compared to employing GT only in all optimization levels (see Corollary 3).
3.5 Different topologies across optimization levels
In SPARKLE, we can utilize different topologies across levels. Theorem 1 and Corollary have clarified the influence of using different topologies across levels through the constants {6,, 8,) for s E fxr, y, z]. For instance, when substituting {6,, 8,) established (9) into (8), SPARKLE-ED has the following transient iteration complexity:
max(n" (1 p(W,)) n2(11 (W),))-
where W is the mixing matrix for updating v, while Wg is for updating y and z. As long as (1 p W )) S (n(1-p( p(W,)) holds, SPARKLE-ED retains the transient iteration complexity of n1 (W,)) ), which allows for the utilization of a sparser network topology when updating thereby reducing communication overheads. Consequently, the ratio of the communication volume per round for the variables x and y can be significantly less than one, See Appendix C.2.3 for discussion on how to different topologies across levels in other SPARKLE variants.
3.6 Recovering single-level decentralized optimization
Previous works typically study single-level and bilevel optimization separately. By taking Ge v, 5) = 2/ and Fz(z, y, Φ) = Fi( Φ) into (2), the decentralized SBO problem (1) re- duces to stochastic single-level optimization. By setting z² = 0, y* = 0, uē = Vifi(z ( SPARKLE reduces the single-level framework (6), whose convergence can be naturally guaranteed by Theorem 1. Please refer to Appendix C.4 for the detailed proof and results. This is the first result demonstrating that bilevel optimization essentially subsumes the convergence of single-level optimization.
4 Numerical experiments
In this section, we present experiments validate our theoretical findings. We first explore how update strategies and network structures influence the convergence of SPARKLE. Then we com- pare SPARKLE to the existing decentralized SBO algorithms. Additional experiments about decentralized SBO problem with synthetic data are in Appendix D.1.
Hyper-cleaning on FNSH dataset. We consider a data hyper-cleaning problem [44] on a corrupted FashionMNIST dataset [48]. Problem formulations and experimental setups can be found in Appendix D.2. Firstly, we equip SPARKLE with different decentralized strategies in different optimization levels and then compare them with D-SOBA [29], MA-DSBO-GT [10], and MDBO [21] using the corruption rate p == 0.1, 0.2, 0.3, respectively. As is shown in Figure 1, all the SPARKLE-bban algorithms generally achieve higher test accuracy than D-SOBA, while ED and EXTRA especially outperform GT. Meanwhile, using mixed strategies (i.e., SPARKLE-ED-GT and
achieves similar test accuracy with SPARKLE-ED and SPARKLE- EXTRA and outperform SPARKLE--T,, respectively. These observations match with the theoretical results in Corollary 2-4 and Remark 4.

---

05
1006
SIAOO EXTRA
SNIC EXTMACT
JIMOS
WARG ECTRL
EXTTNA
HATRAD
0P000 PSTRA
JEHEO EXTM
05
250
500
700
1000
2250
1500
3750
2000
500
2300
350
250
2000
40
1000
350
2000
2500
3000
2000
Figure The test accuracy on hyper-cleaning with various SPARKLE based algorithms using different corruption rates (Left: 0.1, Middle: = 0.2, Right: = 0.3.)
SARPARICL EXTRMA Faxditopo Waried appa sfy?
(spaPANKCE EXTTR, Poord tapa Vasted tuporttz
V000
SNAM DEXTRA
MD30
100
02
p-00
2-
p=0
Figure 2: Test accuracy of SPARKLE-EXTRE on hyper-cleaning (Left: fixed graph for x and varying graph for y, 2; Right: fixed for y, 2 and varying for x))
The upper-level loss against samples gener- ated by one agent of different algorithms in the policy evaluation. (Left: 10, Right: n = 20.)
Figure 3:
Next, we test SPARKLE-EXTRE with two communication strategies including fixed topology for updating and varying topology for y. 2, and fixed topology for updating y, 2 and varying topology for x. As illustrated in Figure 2, maintaining fixed topology for z while reducing the connectivity of the topology for y and = will deteriorate the algorithmic performance. Conversely, preserving the topology for and while decreasing the connectivity for æ: has little impact on the performance. This suggests that the influence of the network topology for y and z on the algorithm dominates over the topology for which is consistent with discussion in Section 3.5. We also numerically examine the influence of moving average on convergence, see discussions in Appendix D.2.
Distributed policy evaluation in reinforcement learning. We consider multi-agent MDP problem in reinforcement learning on a distributed setting with n E (10, 20} agents respectively, which can be formulated as a decentralized SBO problems [52]. Here, we compare SPARKLE with existing decentralized SBO approaches including MDBO [21] and the stochastic extension of SLDBO [16]
over Ring graph. Figure 3 illustrates that SPARKLE converges faster and achieves a lower sample complexity than the other baselines, especially when n = 20, which shows the empirical benefits of SPARKLE in decentralized SBO algorithms with large number of agents and sparse communication modes. More experimental details are in Appendix D.3.
Decentralized meta-learning. We investigate decentralized meta meta-learning on minilmageNet [47] with multiple tasks [18], formulating it as decentralized bilevel optimization problem. This approach minimizes the validation loss with respect to shared parameters as the upper-level loss, while the training loss is managed by task specific parameters at the lower level. Additional details about the experiment can be found in Appendix D.4. Our method, SPARKLE, is benchmarked against D-SOBA [29] and MAML [18], demonstrating significant improvement in training accuracy.
Conclusions and limitations
This paper proposes SPARKLE, unified single-loop primal-dual framework for decentralized stochastic bilevel optimization. Being highly versatile, SPARKLE can support different decentralized mechanisms and topologies across optimization levels. Morcover, all SPARKLE variants have been demonstrated to achieve state-of-the-art convergence rate compared to existing algorithms. However, SPARKLE currently supports only strongly-convex problems in the lower-level optimization. Its compatibility with generally-convex lower-level problems remains unknown. Additionally, the condition number of the lower-level problem significantly impacts the performance, as is the case with existing bilevel algorithms. We aim to address these limitations in future work.
10

---

6
Acknowledgment
The work of Shuchen Zhu, Boao Kong, and Kun Yuan is supported by Natural Science Foundation of China under Grants 92370121, 12301392, and W2441021. This work is also supported by Open Project of Key Laboratory of Mathematics and Information Networks, Ministry of Education, China. No. KF202302.
References
[1] S. A. Alghunaim, E. Ryu, K. Yuan, and A. Sayed. Decentralized proximal gradient algorithms with linear convergence rates. IEEE Transactions on Automatic Control, 66(6):2787-2794, 2020.
[2] S. A. Alghunaim and K. Yuan. A unified and refined convergence analysis for non-convex decentralized learning. IEEE Transactions on Signal Processing, 2022.
[3] S. Arora, S. Du S. Kakade, Y. Luo, and N. Saunshi. Provable representation learning for imitation learning via bi-level optimization. In International Conference Machine Learning, pages 367-376. PMLR, 2020.
L. Bertinetto, J. Henriques, P. Tom, and A. Vedaldi. Meta-learning with differentiable closed-form solvers. In International Conference on Learning Representations (ICLR), 2019. International Conference on Learning Representations, 2019.
[5] T.-H. Chang, M. Hong. and X. Wang. Multi-agent distributed optimization via inexact consensus admm. IEEE Transactions on Signal Processing, 63(2):482-44 497, 2014.
[6] J. Chen and A. H. Sayed. Diffusion adaptation strategies for distributed optimization and learning over networks. IEEE Transactions Signal Processing, 6088))428944355, 2012.
T. Chen, Y. Sun, Q Xiao, and W. Yin. single-timescale method for stochastic bilevel optimization. In International Conference on Artificial Intelligence and Statistics, pages 2466-2488. PMLR, 2022.
[8] T. Chen, Sun, and W. Yin. Closing the gap: Tighter analysis altemating stochastic gradient methods for bilevel problems. Advances in Neural Information Processing Systems, 11-25294-25301 2021.
[9] X. Chen, M. Huang, and S. Ma. Decentralized bilevel optimization. arXiv preprint arXiv:2206.05670 2022.
[10] X. Chen, M. Huang, S. Ma, and K. Balasubramanian. Decentralized stochastic bilevel optimization with improved per-iteration complexity. In International Conference on Machine Learning, pages 4641-4671. PMLR, 2023.
[11] X. Chen, T. Xiao, and Balasubramanian. Optimal algorithms stochastic bilevel optimization under relaxed smoothness conditions. arXiv preprint arXiv:2306. 230..:230...066.. /2067, 2023.
[12] M. Dagréou, P. Ablin, S. Vaiter, and T. Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. Advances in Neural Information Processing Systems, 11-26698-267105 2022.
[13] P. Di Lorenzo and G. Scutari. Next: In-network nonconvex optimization. JEEE Transactions on Signal and Information Processing over Networks, 202):120-136, 2016.
[14] Domke, Generic methods for optimization- modeling. In Artificial Intelligence and Statistics, pages 318-326. PMLR, 2012.
[15] J. Dong, Z. Cao, T. Zhang, J. Yc, S. Wang, F. Feng, L. Zhao, et al. Eflops: Algorithm and system co-design for high performance distributed training platform. In 2020 IEEE International Symposiun High Performance Computer Architecture (HHPAA), pages 610-622, 2020.
[16] Y. Dong, S. Ma, J. Yang, and C. Yin. single-loop algorithm for decentralized bilevel optimization. arXiv preprint (tt:2311.0094, 2023.
[17] C. Duchi, Agarwal, and M. Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic control, 57(3):592-66 -666, 2011.
[18] C. Finn, P. Abbeel, and S. Levine. Model-agnostic meta- neta-learning for fast adaptation of deep networks. International Conference Machine Learning, pages 1126 1126-1135, 2017.

---

[19] L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference Machine Learning, pages 1568-1577. PMLR, 2018.
[20] B. Gao, Y. Yang, and xiang Yuan. Lancbio: dynamic lanczos- bilevel optimization via krylov subspace, arXiv preprint arXiv:2404.03331, 2024.
[21] H. Gao, B. Gu, and M. T. Thai, On the convergence of distributed stochastic bilevel optimization algorithms over network. In International Conference on Artificial Intelligence and Statisticx, pages 9238-9281. PMLR, 2023.
[22] S. Ghadimi and M. Wang. Approximation methods for bilevel programming. arXiv:1802.022 2018.
arXiv preprint
[23] R. Grazzi, L. Franceschi, M. Pontil, and S. Salzo. On the iteration complexity of hypergradient computation. In International Conference on Machine Learning, pages 7748-3758, PMLR, 2020.
[24] 7. Guo, Q. Hu, I., Zhang, and T. Yang. Randomized stochastic variance-reduced methods for multi-task stochastic bilevel optimization. arXiv preprint
2021.
[25] M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1):147-188) 180, 2023.
[26] D. Jakovetić. A unification and generalization of exact distributed first-order methods. IEEE Transactions Signal and Information Processing over Networks, 5(1):31-46, 2018.
[27] K. Ji, J. Yang, and Y. Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pages 4882-4892. PMLR, 2021.
[28] A. Koloskova, T. Lin, and S. U. Stich. An improved analysis of gradient tracking for decentralized machine learning. Advances in Neural Information Processing Systems, 34:11422-11435, 2021.
[29] B. Kong, S. Zhu, S. Lu, X. Huang, and K. Yuan. Decentralized bilevel optimization over graphs: Loopless algorithmic update and transient iteration complexity. arXiv preprint arXiv:2402.03167, 2024.
[30] Z. Li, W. Shi, and M. Yan. A decentralized moximal-grrdien method with network independent step-sizes and separated convergence rates. IEEE Transactions on Signal Processing, July 2019. carly acces. Also available arXiv: 1XXiv110440770 170.07807.
[31] X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and J. Liu. Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 5330-538 5340, 2017.
[32] T. Lin. P. Karimireddy, S. Stich, and M. Jaggi. Quasi-global momentum: Accelerating decentralized deep learning on heterogeneous data. In International Conference on Machine Learning, 2021.
[33] S. Lu, S. Zeng, X. Cui, M. Squillante, L. Horesh, B. Kingsbury, Liu, and M. Hong. A stochastic linearized augmented lagrangian method for decentralized bilevel optimization. Advances in Neural Information Processing Systems, 35:30638-30650, 2022.
[34] Y. Lu and C. De Sa. Optimal complexity in decentralized training. In International Conference on Muchine Learning, pages 7111-7123, PMLR, 2021.
[35] D. Maclaurin. D. Duvenaud, and R. Adams. Gradient-basse hyperparameter optimization through reversible learning. International Conference on Machine Learning, pages 2113-2122. PMLR, 2015.
[36] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
[37] A. Nedié, A. Olshevsky, and M. G. Rabbat. Network topology and communicationn-compaaaii tradeoffs in decentralized optimization. Proceedings of the IEEF, 106(5):953-97,, 2018.
[38] A. Nedic, A. Olshevsky, and W. Shi. Achieving geometric convergence for distributed optimization over time-narying graphs. SIAM Journal Optimization, 27(4):2597-233, 2017.
[39] A. Nedic and A. Ozdaglar. Distributed subgradient methods for multi- optimization. IEEE Transac- tions Automatic Control, 54(1):48 61, 2009.
12

---

[40] Y. Niu, J. Xu, Y. Sun, Y. Huang, and L. Chai. Distributed stochastic bilevel optimization: Improved complexity and heterogeneity analysis. arXiv preprint vrXiv:2312.14600, 2023.
[41] G. Qu and N. Li. Harnessing smoothness to accelerate distributed optimization. IEEE Transactions on Control Network Sysiems, 5(3):1245-122) 2018.
[42] O. Russakovsky. J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, al. Imagenet large scale visual recognition challenge. International Journal of Computer Vision, 115:211 252, 2015.
[43] A. H. Sayed. Adaptive networks. Proceedings of the IEEE, 102(4))460-49) 2014.
[44] A. Shaban, C.-A. Cheng, N. Hatch, and B. Boots. Truncated back-prepagation for bilevel optimization. In The 22nd International Conference Artificial Intelligence and Statistics, pages 1723-1732. PMLR, 2019.
[45] W. Shi, Ling, G. Wu, and W. Yin. EXTRA: An exact first-order algorithm for decentralized consensus optimization. SIAM Journal on Optimization. 25(2):444-966, 2015.
[46] H. Tang, X. Lian, M. Yan, C. Zhang, and J. Liu. D²: Decentralized training over decentralized data. In International Conference on Machine Learning, pages 4848 44844856, 2018.
[47] O. Vinyals, C. Blundell, T. Lillicrap, D. Wierstra, al. Matching networks for shot learning. Advances in Neural Information Processing Systems, 29, 2016.
[48] H. Xiao, K. Rasul, and Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms.. arXiv preprint arX1v:1708.07777,200 2017.
[49] J. Xu, Y. Tian, Y. Sun, and G. Scutari. Distributed algorithms for composite optimization: Unified framework and convergence analysis. IEEE Transactions on Signal Processing, 69:3555-3570, 2021.
[50] Xu, Zhu, Soh, and Xie. Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes. In IEEE Conference on Decision and Control (CDC), pages 2055-2060, Osaka, Japan, 2015.
[51] Yang, K. Ji, and Y. Liang. Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems, 34:13670-111 13682, 2021.
[52] S. Yang, X. Zhang, and M. Wang- Decentralized gossip-based stochastic bilevel optimization over communication networks. Advances in Newral Information Processing Systems, 35:238-252, 2022.
[53] K. Yuan, A. Alghunaim, and X. Huang. Removing data heterogeneity influence enhances network topology dependence of decentralized SGD. Journal of Machine Learning Research, 24(280):1 2023.
[54] K. Yuan, S. Alghunaim, Ying, and A. H. Sayed. On the influence of hias-correction on distributed stochastic optimization. IEFE Transactions on Signal Processing, 2020.
[55] K. Yuan, Q Ling, and W. Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3): 1835-18833-18855 -8544 2016.
[56] K. Yuan, B. Ying, X. Zhao, and A. H. Sayed. Exact difusion for distributed optimization and learning - Part I: Algorithm development. IEEE Transactions on Signal Processing, 67(3):708 - 723, 2018.
[57] Y. Zhang, M. T. Thai, J. Wu, and H. Gao. On the communication complexity of decentralized bilevel optimization. arXiv preprint arXiv:2311. 2023.
13

---

Appendix for "SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel
Optimization"
Contents
More related works
15
More details of SPARKLE
15
B.1 Primal-dual deviation
15
B.2 Specific instances
16
B.3 Implementation details
17
C Convergence analysis
18
C.I Proof of Theorem
18
C.I.1
Notations
18
C.1.2 Basic transformations
19
C.1.3
Proof sketch
22
C.1.4
Technical lemmas
23
C.I.5
Descent lemmas for the upper-level
23
C.1.6 Descent lemmas for the lower- and auxiliary-level
30
C.1.7 Consensus error analysis
35
C.1.8 Proof of the main theorem
47
C.2
Analysis of consensus error and transient iteration complexity
54
C.2.1
Consensus Error
56
C.2.2 Essential matrix norms for analysis
59
C.2.3 Theoretical gap between upper-level and lower-level
59
C.2.4 The transient iteration complexities of some specific examples in SPARKLE.
60
C,3
Convergence analysis deterministic scenarios
C,4 Degenerating to single-level algorithms
62
Experimental details
64
D.1 Synthetic bilevel optimization
64
D.2 Hyper-cleaning on FaSHionMNIST dataset
65
D.3 Distributed policy evaluation in reinforcement learning
68
D.4 Decentralized meta-learning
69
14

---

A More related works
Bilevel optimization. Bilevel optimization presents substantial difficulties compared to single-level optimization due to its nested structure. Estimating hyper-gradient (+(x) of the upper level involves solving lower-level problems and estimating the Hessian inverse, which requires additional calcu- lations. Many algorithms and techniques have been proposed to solve the challenge. Approximate Implicit Differentiation (AID)-based algorithms [14, 22, 23, 27] leverage the implicit gradient form of ( which entails solving linear system to obtain the Hessian-inversee- -eectrr product. Similarly, [8, 25] utilize the Neumann series to handle the Hessian inverse. Iterative Differentiation (ITD)- algorithms [19, 35, 14, 23, 27] iterative methods solving the lower-level problem and then es- timate the hyper-gradient through automatic differentiation. However, these approaches introduce inner steps, leading extra computational overhead and memory spaces. [12] proposes single- level algorithm called SOBA, which approximating the Hessian-inverse-veeton product by solving a quadratic programming problem. A recent work [20] utilizes the Krylov subspace technique and the Lanczos process to approximate it in deterministic scenarios. For stochastic bilevel optimization, various methods have been employed improve the convergence rate, such as momentum [7. 11] and variance reduction [51, 27, 24].
Decentralized optimization. Decentralized optimization is developed to deal with large-scale optimization problems, where datasets distributed among multiple agents. Without central server, each agent only gets access to its own local data and communications are limited to its neighbors in network. Compared with centralized algorithms, decentralized ones preserve data privacy, and are more robust to contingencies in the communication network. However, due to the absence of central server, decentralized optimization requires communication among agents, posing greater challenges for convergence, especially in the presence of severe data heterogeneity. To tackle this issue, various algorithms have emerged, such decentralized gradient descent [39, 55], diffusion
strategies [6]. dual averaging [17]. EXTRA [45], Exact Diffusion (a.k.a. D²) [56. 30, 46], gradient tracking [50, 13, 38], and decentralized ADMM [5]. In stochastic scenarios, common method for decentralized optimization is the decentralized stochastic gradient descent (DSGD), which has gained a lot of attentions recently. It has been proved to achieve linear speedup asymptotically and shares the same asymptotic rate with centralized stochastic gradient descent [31].
B
More details of SPARKLE
B.1 Primal-dual deviation
Here we provide a detailed motivation the update framework (6) for decentralized single-level algorithms. First, we rewrite the single-level distributed optimization problem in the following equivalent form:
min a.ERd
Σ Ls (xa), s.t. 31 n
1
n
Fns
(10)
where each f. smooth and possibly non-convex. To simplify the notation, we assume that d 1 without loss of generality. Now we introduce three symmetric matrices A, B, D such that A is doubly stochastic communication matrix with p(A) < 1, and B, D satisfy NullB = NullD Span(1,, }. In general, B (D) determines the topology of a connected graph GB (Gp) over agents. The constraint Br (Dz 0) is equivalent to:
F; xi Fi, 2y are adjacent in 9B (Gp).
To simplify the derivation, we additionally assume that A, B, D are pairwise commutative. Then for Fn), we have:
Fn Br
Dr = 0 + = =z.
Therefore, (10) can be equivalently reformulated as
min f(Ax), s.t. Ba 0.
(II)
z
15

---

We construct the augmented Lagrangian function of the problem (11) as follows:
Lp(2, d) f(Ax) + (d, Ba) + - Drrl?
where denotes the primal variable, d denotes the dual variable Lagrangian multiplier associated with the consensus constraint, || |z] serves as the penalty term measuring the deviation from Da 0, or equivalently Bæ 0; p > is the penalty coefficient. Though the introduction of matrices A, D is essentially a matter of equivalent substitution, it enhances the universality of the algorithm framework get.
Following classical primal-dual methods, we alternately perform gradient descent on æ and gradient ascent on d in the k--th iteration:
++ -² a (AAVS(Az") Ba + pDPx*), d=ti = dt ++1
where a, denote the step-sizes. By making the change of variables
* = = d = V Adt B= VaBB, C = -app? ā A?
we obtain
gh+1 3 - - Bdd d+t1 d Ba*+1
(12)
One should note that the definition implies that A, C are doubly stochastic communication matrices under appropriate selections of a, p. Finally, thanks to the introduction of noving-averann iteration of (12), we can obtain the framework (6) which serves as the foundation for our algorithm design. See more details in Section 2.3.
B.2 Specific instances
Relation to some existing single-level algorithm frameworks According to (12), our framework
single-level is
x k+1
Cx* -AA - Bd d d = d ++1
k+1 ,k 0,
(13)
where a is the siep- g* denotes the estimated gradient at the k-th iteration, d serves as the dual variable.
Replacing C with CA, we get UDA[1] and equivalently, SUDA [2]:
x k+1 CAX*
Ag Bd d d Bx* . 0, 1,...
Therefore, following SUDA, we can also recover some common state-of-the-art heterogeneity methods as follows by selecting specific A, B, C. First, from (13) we get
x
x ++1 = C(x++1 - xx*) aA (g
g*) - B (d1+1 d*)
C (x xt) aA k+l -g") 3²x
Thus, for k: 2 we have
x+2 (I- B + +C)x* x+1 Cxx aA (g++1 g*)
with x Cx AA.
Some specific instances geneity methods.
We next show that how to choose A, B, C to get some common hetero-
ED: Taking A = W. B = (I - 1/2 and C = W, we get ED:
x* x+2 W (2x*+1 x* (g k+1 g*))
with = W (x ag").
16

---

EXTRA: Taking A = I, = (I- / with C = W, we get EXTRA:
x ++2 = W - xx) a (g*+1 ++1 -g"),
and x = Wx ago.
Adapt-then-combine gradient tracking (ATC-GT): The iteration of ATC-GT is x++1 W (x* -ah") ) h+ w (h* + g+1 -g")
with h Wg Wxx (zf = x.). follows that for k 2
x*+2 Wxt+1 Wx*+ w aW -h Wh*).
Then we obtain
++ 2W w - a (g 1g* -g").
with x' - W2g Thus, we can take A W2 B W)?, - W to
implement ATC-GT.
Semi-ATC-GT: The iteration Semi-ATC-GTis
x x++ W (x* ah") hh+t Wh g k+
with h Wg x Wx" (xf ... 2.)) Like ATC-GT, we have
k+2 2wx W2x* aW (g*+1 g*).
with x w2x" a Wg Thus, we can take A W.B (I W)²C W to implement Semi-ATC-GT.
Non-ATC-GT: The iteration of Non-ATC-GT
++1 -Wx oh hht Wh +
+g k+l
with h Wg 0 Wxx (xf ... = x.)) We have
k+2 2W**+1 = (g (g g*)
with x W2x0 ag Thus, we can take I, (I- C= W to implement Non-ATC-GT.
B.3
Implementation details
Given the update method L, update the lower-level variable y at the k-th (k 0) iteration as
follows. For brevity, define y; vl, u. 0, (W
V.
A+1 = EE 1 (Wy)is (2 k-1 - Be (ut v/ 1)-
if = ED
V
*+1 = - (W (2 yj - Br ( Vi k-1
i EXTRA
Vn
R+1 Ee=ı(Wy) (V) B2o of ΣØ= Wy) (of + k+1 of
if GT others
(14)
Similarly, update the auxiliary variable at the k-th (k: 2 0) iteration follows. For brevity, define 2; 2. P. 0, ho = ( (W2)ppJ. Note that we use the same method L to update as we do for the lower-level variable y.
(2a)- k-1 7k (1) -1,-- 1111 - (W2)as k+1 = (W=r())) (22) -1 7k (p. -111
++1 = Σラ
if = ED
if EXTRA
th E (E) - -naht) kt1 Σラ= (Wz)is (ht + + k+1 -pt)
L. GT others
(15)
Given the update method U, update the upper-level variable a at the k-th (k: 2 0) iteration as follows. For brevity, define x; z9tt (Ww)(WW)rr
17

---

k+1 Σラ (Wo) (20 - x -- are (1: k+t x
if = ED
1 (Wa)is (2 - 23j -1 - Ox (r+ k+1 r() (Wa)es (3f - oull9) .1/-t 1 1 (W
if EXTRA if - GT
+1 -
others
(16)
Then the practical implementation of SPARKLE with mixed strategies is
Algorithm 2 SPARKLE-L-U
Require: Initialize 2 5/ 2 = r! = 0, step-sizes ous, Bk. Yk. 0g.
for k 0. K - 1, each agent i (in parallel) do Update y/ ++1 according to (14);
Update k+1 according to (15);
++1 (1 0x)r Ozu
Update a, k+I according to (16).
end for
C Convergence analysis
C.1 Proof of Theorem 1
C.1.1 Notations
We use lowercase letters to represent vectors and uppercase letters to represent matrices. Stacked vectors [z]] ..., x T1T is denoted by (o TI, for brevity. We denote block diagonal matrix with diagonal block (1 < < 1) by b M. and a diagonal matrix with diagonal elements d1 S i k) by diag d1, ..., d The Kronecker product operator is denoted by & For variable
of to represent its components at k-th iteration and i-th agent.
Moreover, we use an overbar above an iterator to denote the average over all agents. For example, j Ei= 2 /n. Upright bold symbols are used to denote stacked vectors or matrices across agents. For example, x := col a/ .... xh x := col( xh ...,.* (n times), Wa := Wa & dam)(z) Denote the 2-norm of matrix by ||
Next, define following ofields which will be used in our convergence analysis:
Fx a (y" y k+1 z"
2
k+1
xx
0 ...., xt r
x
Us (y ...... x+ 20 2h x x no
rh) r²)
Gk = a (y" ,..,, zo zt x²
and denote [[[]]x]] by Ex. [[c] by Ex, Bl-|GK] by Eg for brevity. Define
+x)) = Σ ben (z, (2,
Σ Vefi (afl(t
Then, for l 0, 1..., define:
k+1
Σ
n
2 22 (at My ((((tt)
Σ Vifa (a* (3*
For convenience, we define x x0,y-1 y 10 (5 20= z!
18

---

C.1.2 Basic transformations
We begin with conducting SUDA-like [2] transformations, which is fundamental of the following proofs.
Firstly, we define t to track the averaged stochastic gradients among agents as follows
(d By + 3A, (2 y²),
t B. B.z²) + 7 (x" ght1).
(17)
th (d B,x*) + A V V (x*).
where
(x(* gktl) col 122 ) V2fi ) imm
(x( col ( y (z())) - V Viggi y (x (x*))) 22+ J==1'
Then the iteration of y, z, in Algorithm 1 can be written
y k+1 (C,, - BByy* 1 BA, [v V2g(x* ++*) ,htt1 k+1 t + Byy + SAy [Vgg(**+1 , ) - V V2g(x* y
iteration of y
(18)
k+1 (C, D² t -A, [pt - 1x** , r(+
iteration of
N+1 t +B2z* + 7A |p p+ 1 , gb+tt - (x* gh+tt] (19)
x k+1 (C2 - B x - - aA [ {ズ(
iteration of x
(20)
k+1 th + B + aA, (Ø(*))))= -
Next, we present the transformation of the matrices A, B, C. For a communication matrix W. for the variable a E {xr y, =} satisfying Assumption 2, there exists an orthogonal matrix such that:
[ U.
0
w = U.A.U
0
Ag
Vn
where A, diag(Aai) )2 UT E Rax(n-1) satisfies 0.ÚJ Ia 1 and 1, 0. Then follows that:
1 - L & (s) ú, [dim(s)
{
1 & Laim(s))
W. = U.A.U
Vn
An
Ú
where dim(s) denotes the dimension of the corresponding variable, A, A, 8 Ldim(s) Rdd(-- x)x (n U E Rldim(s) () (dim(()))) is an orthogonal matrix, and Ü, = Ü. X
Idim(s) E [sdim((s)nn (i x(dim(ss) 1)1 satisfies:
U U. (nm)))) ú.ú, In
11
@ ldim(s):
(1 T & ldim(s)) U. = 0.
Now we add subscript for W.. Then, as As, B C, can be expressed a polynomial of W, for s E {x, y, 2 according to Assumption 2, we have the orthogonal decomposition:
A, = U,A,A U.
1 & lam(()
ú,
Tdim(s)
Vn
& Tdim(a)
Vn
Asa
UT
= - =
2 4am((s)
Ú
0
Vn
& Ldim(s)
(21)
n
2
sb
U
-.=U, U. =
69 (dim(e)
Ú,
Tdim()) O
0
Vn
1
Iaim(s)
Aac
UT
19

---

where
A.n- diag Hingshing &lam(s)) A.b diag Himy (aim))))> Asc
diag Noe,sting
Fimg Blam(s))
Moreover, each Ast is positive definite because of the null space condition in Assumption 2. Then, multiplying both sides of (18), (19) and (20) by U. Ug, U respectively, we get:
UU [Ugyhtz= = (Âyr- U y - U - Buya U [v= - V2g(x* ,5)] iter. of y: : U Uy t + 23 U y* + Ba U [V2g(xtt) stt!)) Vag(x* y²)],
(22)
U UTa (Azc- 1 - A U [p* - -xx(xx (***x,
iter. of
U U = U. th + - ! (x 54-2) -x(("", s
___
(23)
Ugx = (Anc
- U. - anna UT [ritt - -
iter. of x:
(24)
U. U = U + UNx + uā
-
Then, due to Eq. (17), we have:
(1 @ La (1 2 la) (B, BBy") + BA, V2g(x ,x1)
(25)
= ~n/V2g(2 3²h).
(IT 8 Tat = (1 T & Ia) (d - B.z²) + + Axpp(x* sltl))
(26)
(I + Veli(t* , s/ttt]].
=7
(1 8 La)t = (1 T @ la) (d - B,x*) + aA aA,
(27)
= (1fi(=+.v'(tt)) - ( y² (8+ 2
Substituting (25). (26), (27) into (22), (23), (24), respectively. Then use (21) and the structure of Ü, U., Ün we have
gitl= -3*=-3"*
iter. y: :
Ú y = =(Ayo- - A 1
th - AAya ÚJ [v* - -V2g(*" ,"),, U y y th + A U,y" " + +BAaaU ÚJJ V2g(xtttl.gi - Veg(x" ,8"]
x+1
y y -
-J k
gh+l = z² - -p==
iter. of z:
x = =(Aze AZ,) x² - 0. - 7 UJ [pt (x*,
( -Ú, t + A2, ÜJ x² + + (x (iagttittttt ,htz) - p (xx (xt,
gh+1 = - -ar+11
Ú x++++= = (A A Th - arمn -ad UJ ppit2 50()t)
iter. x:
Ú 1 M++1 U x t + 13 * + +adza 0 ( -0(())]
20

---

The above three equations are equivalent to:
U y
A
yee
A
ybb
U yyy
yb
A yb t
Ayb
I
A Agb UT
(28)
A ya
U [vr v2g(x*, 5²)
3
A yh
Aya
Ug
[2g g(tl) Vog(x*
U. ++
A
A
- AAb
U
A 2b
Azb
Agb A U.
(29)
Aza
[p* p (x* gk+1)]
p
(x*+1 yh
p x (xt skt
x A U t
0c
A
Ab
U A A th
Axb
I
Aza ÜT
k+1 (x++
(30)
Ú
( (
26
Fors E {x,y, 2), define:
sk
Agc A Aob
-ab
cx =
M. =
U.
ab
Then (28), (29), (30) respectively equivalent to:
Aya Ü [vt V2g(x* xt)]
k+1 y
M, - B
V2g(x ,rht1) - V2g(x* [4)]
yb ya
Aza
D - -p*(x* 54-1)
k+1
M,C, -
U.
(x gk22) p* z(tt1]
Aga UJ
k+t (x(+))
M -a
A TT
( (
Assumption 2, 3 imply that all eigenvalues of
diag(0, A.c - A diag (0, Ast
diagf0, Ast diag/0, 1,..,
(31)
- -[U
-
U.
[[ 1.
][
C.
B2
- B, I 1
][
U,
UT
B.
U.
are strictly less than one magnitude. Thus by symmetrically exchanging columns and rows of the matrix, we know that equivalently, all eigenvalues of
Asc Aab
A
-Aah
and M. A
A3
Asb
(32)
T
Aab
T ? Taim(s)
are strictly less than one in magnitude..
Then according to Lemma 3, for s E (x. y, 2). M, has the similarity transformation:
M, O,T,O,1,
where O is invertible and | < 1. Moreover, we define e = =0,'e It yields
A ÚJ [vk V2g(x*, ,
1++ 1)
r e
,
(33)
A A ya Ú ( - V2g(x*,
21

---

Aza U [ - , skt1]]
eh+1 = r -
(34)
[p (xh+1 gxtt) p px sktt)]
zb
A Ago Uh
pktt (x*+
o- = T 2 20,
(35)
A Aza &
マのイ - (x+)
Then, for {x, 2), the consensus emros between different agents have the upper bound of:
||st -ss==s11²= = S || = |0,,19166111
(36)
Thus, we can define:
A x² ||0 2 +
11
to measure the consensus error during the iteration.
We also define
I || 2/ + yd (
to measure the estimation accuracy of the lower- and auxiliary-level problems.
C.1.3 Proof sketch
Before proceeding with the formal proof, we first present the structure of the proof in Appendix C.
Bounded by each other
Descent of x
Σ B| pk
Descent of y
Σ E ++1 g
3² (
Σ [x
Σ E [
Descent
Σ Ell
11
Consensus of y
Σ 1
Σ E
Ix]
Consensus of 2
Σ 1
Consensus of x
Σ 1
Hlper-gradien estimation
Σ B E
Hyper-gradient estimation
Σ
E 1
k+1
Lemma 17
Variance
Σ E
11122
22

---

C.1.4 Technical lemmas
Lemma 1. Suppose Assumptions I hold, know (Z(x), VI 2² (x) and y (2) defined above
are T T, Tage, Tuge- Lipschitz continuous respectively with the constants satisfying:
Lvo S L 2. Lm T.g.T..000
+ 2L. g.0.
T 1 1.
T.g.212 9 1.0
Mg
12
21 1111 2022
21 T1 1.0 b.2 +
T.2 1.,,1
9. T. 1.
L S L4,1 +
+
Mg
19
V.
Ly: 5 L.
Pg
Toga1
1.1.011.22
L S V1+ Lz.
+
Mg
1g
And we also have:
[|>((x)] S
Vz EP.
Mg
Proof. See Lemma 2.2 in [22] and Lemma B.2 in [11].
Lemma Suppose that g(x) is y-sttrongy convex and L-smooth. Then for any x and < μ+L we have
1 - vVg(x) x=1 S (1 -aa) || 10==x11 x²11.
where x = argmin g(x))
Proof. See Lemma 10 in [41].
Lemma 3. Given diagonal matrices A, B, I (n-1 ()=1()) and
A la B Cola D
M
Suppose that the eigenvalues of M are strictly less than one in magnitude. Then there exist an invertible matrix O and a matrix with [|] 1, such that M has the similarity transformation:
M -
Proof. See Lemma 1 in [2].
Remark 5. Asserting the existence T with |[T]| < <1, Lemma only guarantees the convergence SPARKLE. However, to obtain precise non-asymptotic convergence rate, one must construct appropriate O and F, See more details in Appendix C.2.2.
C.1.5 Descent lemmas for the upper-level
In this subsection, we estimate the upper bound of the errors induced by the moving average in hyper-gradient estimation, as well as the upper bound of [|] based on Ig. Ag-
Lemma 4. Suppose Assumptions 1- hold. We have:
Een ( < (A + nTx),
20
(38)
Exu* -au=~
<201 (A, + nlx)
23

---

Proof. Cauchy Schwartz inequality implies that:
E VΦ (x*)
<5
Vife (2 V/ v/+ Vifa (a*, ge || + Σ
Vifa (x* ( - Vifa (I 1=""."((") ("*)))
am1
V 129 (I,, vft (2, - 21
+
12% (( Vig (#*, g]++1)) =
+
+5 Σ [[Vige 129 (=*, (/,httt ii (5t yy (x* ))) 11
$10 $10 (L),, + n² 11,00) (11x 1exxt=**pp x+112 + ||y g 1|2 + || -
+ +1012,1 (1|At1- -o-iti-zt z/t2|1² 12 1|+ + ||z - 2, 111))²)
$20I² (Ax + +l(x).
For the term || V (=² we have:
EBa | s Exu" - - (x+)|| -x)
2012 (At + 1b +11)
A
Lemma 5. Suppose that Assumptions 1- 4 hold. We have
|| Ex
[1 =
Ex[u"1]'
71
k=
(39)
K
1,,
<90
E 2
1
E
E
112) - 3(K + 1)n
07.1
30 g.2
9.2
k=0
Proof. For k 2 0, Cauchy Schwartz inequality implies that
Ex
[|Iu*
Ex[u [
<E
VIf((at w/ -tt -ifiail )1
|| V (1 u/t ,ct) Vi2gicat, )) 2f 111 112
+ Ex
Ino f.1 22 11 112
Sno f.1 + 30
(|zz k+1 1²+111 + ||z 4++1 + 1|2)+
9.2
||zh+| - zk+112 + |z xx 112 + 1.7,0
Snaj, j,1 30
19
Then taking expectation and summation both sides, get
E ||u
E& [u
k=
K
4,0
<90²
1
El 2 +111 + 3(K 1)n
0f.1 + 302 0.2
9.2
22
k=
24

---

Since samples among agents are independent, it follows that
Ex || E&
[1]]
E&
I|u
[x((=[13))
n
R==
Taking expectations, get the conclusion.
Lemma 6. Suppose that Assumptions 4, and Lemmas 4, 5 hold.
1
(40)
2L74
have
K
E
|
k=U
① (
inf +
+ 10
L +
to?
9.2
E2
A
+ I7
30
(K
+1
0f,1 +
20
g.2
L
f.0
11
11
k= 0
(41)
Proof. The Lrs-smoothness of indicates that
Ex (x*+1)] -(#")
< <(V((=)) ( (- '1) + Lvga²
Ex Ex
Lva E |
= =(V((=") - En [ aBE pxtt1}} +
[u^] E& [x(b)t]]).
2
Then, due to Eg [u+] = (Bx p+ - (1 0) we have:
E, 2 (x++1] (
a
VD(#") - Eg i7 ||?
α | |11
2
2
Lve a 2E "E 1|2
(Ex ja* Ea 11
+
2
a (4(T*) - Es || +
a + Lva
a² 1R || ||2 a(1 - 0)
| [pk+1] - 1
2
2
2
20
+ a(1 - 0)
(|1
F& ||
+ 1|2) + E& ||
1 - E2 1112
20
29
a
V (**)
Eg [ 11 +
a 2
+
Lva
2 E 112
+ a8
Ex|l - E [1^11
E
2
2
2
+ a(1 0)
(1
- Ex || +1 1|
20
where the first equality uses ( Ex + = |
+ 1Bx|=*+1]1" - 1|
En Ex|=++1]]1 and
Eg =x | 1112 + Eg |
1|2
En 1112.
Taking expectation and summation, and using S 2L we get
inf Φ- - (FFo)
α - a K
al
K
(42)
E 2
E
Ex
Ex Ex(a
2 k=0
2
k=
k=0
Since samples of different agents are independent, we have
1 Exllu
Eg t
E2 [1+
En [1
n
25

---

Combining it with the conclusion of Lemma 4 and 5, we get from (42) that
E
12
k=0
<)(00) - inf 1 + a K
al
K
E
(+* - Ex Ex< [1
+
Exs Eu - Bx(xd1112)
2
2
k=0
k=0
0o?
K
A
3al
(K +1) (07, + 22002
2
< inf + + 10a
+
E
+ I
+
k=
Lemma 7. Suppose that Assumptions 1-4 hold, then we have
K
E
Ex
(x(*)))
1 0
(x( /|(
+ Σ
E
[E { 11
k==
2T
0)2
K-1
E
||x -
x*]]"]] + (1 010 > E3 |utt
Eg [u']]]
0
Proof. We define u
1 for brevity. From the definition of Ex, we have
b Fx (xxx=11)] 1)
Ex [r*] - V (x*-111) }11²² -EE-1 ||re Ex- [r 11|?]
= -Ea-1
(43)
BB [r*] 2 (** 11²)
-E
0 Ex-1 || k- ER [u 111
Jensen's inequality implies that
- Ex [| [r -
|,a ~ 112)
<(1 - -
(5Φ(x - ( 12]
+ SE
[x [1 (x++))
+ 01 - 8)
(44)
||at (x* 11/ + 2
| (E((t)/1
<(1 - E)E,
2(1 0)2 +
Ex
Substituting (43) into (44). , and taking expectation and summation on both sides, we get:
K
Ex [r*] - (
E
k= 0
K
E 1r0 5 1)/ 11( - E
Ex fr k-1 - (0((t))
Ex [ut] E (ext) 11²)
+ 28
E
k=0
2(1 0)2 k
Σ
E
(
-
+ +
0)02
Σ
||u - Ea.
A=U
26

---

[r 4 /) -11
Finally, note that x x², r O, and E-1 Ey. Subtracting BE
0
from both sides of this equation, we get:
(x((*)) |
E
Ex [r
(r+t]]
k==0 0
0
(x*))) ||
FR [x([n*] (x(x)) |
+ Σ
2I (1 - 0)
K-1
K
E
| - x*11
+ (1 - 010
Σ
E
|u
E&
0
k=
k=0
Lemma 8 (Descent lemma). Suppose that Assumptions 1- 4 and Lemmas 4, 5 hold. If
a²
0)
32 a 10
(45)
then we have
K
((0o) inf
K
A
(V 12
+ (T, + (0(1 - 00) + Ioood2) 09.2)
+ T
k=0
(1
0)2
+ (K + 1) (0(1 - 0) Looal?) (o + x²O2
9.2)
+
Proof. The Lvo -moothhossssss of indicates that
[x(0(5++1)) (5*))
Looa2
<(V((=*); -a | +
R& ||
2
a (Vo(5" Ea( {イ -a ( Lvo a BE 1
a 2 --
- 2 ||a|
v0( + Lvo a E |
S
Taking expectation and summation on both sides, we get:
(
(46)
K
<2($(=0) inf +)
Σ L [+ -00==))()2)) + Σ
Lvoa |
k=0
Define auxiliary series m as:
m = 50 =0, = 0)m* +0V0(.*)
Note that
Ex 11 pb+ 1 Ex | Eg 11
(47)
< 2 Ex |o++11+ (= + 2 (F*))) + 8 12t E,u
Then using the Jenson's Inequality, we get:
[g m x 1|2 [[1 () m 0(E V2(2+))11
< (1 - 0)||>* m 112 + 0 E4 02(2")12
27

---

It follows that for l 2 0
E Egg k+l m 11
<(1 B m 1| + (1 0002 - Re 1B--1u
ORI|EAu* v
where for brevity define ū= 1 = 0.
Taking the summation on both sides from 0 K, we get
K
Σ OE plt m 122 2
Σ OE BB||Br m
11 E||EKT K+2 m 12
K-1 + Σ (1-0))82111 1
0 -
O=
k=
(48)
On the other hand, due to the definition of m and Jenson's Inequality, we have:
|| - (=+)))1 II(1 (m ())
(1 0)² VD(E*-1) -
$ (1 0)]lm² V )/ + (1 0)2
L 2
0
Taking the summation, we get
0)2
Σ - - (D((=))1 s Im v 1112 +
L
2 11211
k=
(49)
K
(1 0)2
= -1-
L 2
0
k=
Combining (48) and (49), we obtain:
DE B
K
OE W
m 122 + Σ
p|lm ++1 \1
k=0
k=0
K
K-1
/E (E
Σ
-
k=0
k=
2)2
2
L 211 |1 + 2(1 - -
0)v (x") 1|²
<2
BE
) +2 Σ
1 + 1 -
0 Ltaa") ) (1 11-00""lla"-Baa"" A)
- 1
K-
2(1 / (x9) 1|
LEsa² (2E|IE[(*+H)) 2 2E 2=
R=0
(50)
where the last inequality uses (47).
1 (45) indicates that 4
0
a2
2
<
Subtracting
0
8'
K
(1
0)2
L2
2²
0
28

---

from both sides of (50), we have:
K
k=0
K
K-1
44
B
Ex
+ 8 Σ (1
0)02
1 + 4(1 - 0);|v (51)
k=0
0
+
k=
Substituting (47), (51) into (46), we get:
aE V 1 \
K inf @) + ><< (a + 2L (|( \ + Σ
K
<2(((x))
El
km0
km0
K
+
2 2 20 Ex 1 11
k=0
<2(2(T)) inf 4) + 5a Σ
B V2( (1
// (=9) 1|2
K
K-1 1
+ Σ (10 (1 - 2Tvoo 02 - E
+
a
Σ
E \
2 k=0
k=
(52)
where the last inequality uses a S TOL
Subtracting a/2 EK= (++ from both sides of (52), and substituting (38), (39) into it, we
get:
K
2 aE (
k=
Ax
<2($(x)) inf ②) + 1
E
I
5 0
0) (F9) 1|2
n
km
(10g (1 0) + 2L 2
K
+
0
90
(Blzz* k+1 z 12 + E1 x - 2. 112)
n
9.2
k=0
(10g (1 0) + 22
07.1 + 30 27.0
+
g2. g2.3(K + 1)m
n²
9.2
mg
<2(((2o) - inf 4) + 1100LL' + (10a((1 0) + 2L 22 28²))
2
K
k
E
I
k=0
+ +3(K + +1) (100aa -0) + 20) 0 07 + 30 9.2
17,0
n2
+5 a (1 0 (s") 1
0
29

---

2
Finally, multiplying on both sides, we get:
B B| (Ta) inf +b
02
Au
+ 1,2 (0(10(1)) LVBa07
9.2
Σ
EE
+
Ix
a
71
k=0
K +1 1
0)2
(0(1 - 0) + IFOOO(? (0î,1 + =x200 +
|
112
n
C.1.6 Descent lemmas for the lower- and auxiliary-level
The following lemmas present the error analysis of the estimation of y (x*) and 2 i.e. the term Ig:
Lemma (Estimation error of y" (x)). Suppose Assumptions 1- 4hold, and:
19g B S
(53)
321 9.
Then we have the estimation error of y
K
1100 - - )1
E Billy* +1
- (+*))1
k=U
4
6a Liy
6
10 nr
+
|1
$
1100 3² v²(x0) )1
+
B|| 1
I
E
8pg
32p23
9.
n
4K 3o
11/1g
and
Σ
[1g h+1 - 111
0m=0
T.2
48T22 9.1
48 r,2
K
9.1
4
Σ
E (110211316
1 11115111))))
+
I
E
k=1
k=1
3(K + 1).32
32 g.1
0 9.1
11
1/ 11
n
Pg
(54)
Proof. For each & 2 0, due to the independence of samples, we have:
Eg 1llggh+11
1¹ (*** 119 ExllE** 3ot 1/" (**
V2gi (x).))) uf) 17
1
1
Vegilat wtt) (1*²) + B
1=1
12
n1
+ 32 0.11
<
29 h 3h - 5 (x*))
V 29 ( (x*,g") (290(at,
11
n1
7
30

---

Then.
Es 11 ++
3² )1²)
1 +
gt
==
V 29r (i* 5²) y¹ (+t))
2
n
2
)
+ g2 0.
1 +
Σ
V 29 (
+8) - V29i vft1)
i=1
8pg
+
(1
81,))
'¹ (11))1
2
g²
+
1ig11
| - 1x
||y* - 52112)
+
g2 9.1
314g
n
n
n
S (1 8pn)
[[1
(1+
8p4
110h - 30 51 (a^-1))² 1)1 + (1 2
31g ) 110 - y" 11
2
2
|xx* - 12 11y - -5²113
52 T..
8²
1
+
L
3pg
n
n
n
BPg
3
1
11
1-
(x
+
L 1| - -
2
814g
33
||x*
10 n
Ily*
111
1.11 + g2
12
n
n
where the first and the third inequality is due to the Jenson's inequality, the second inequality holds Ptg according to Lemma 2 and the fact that 3 I 32T, S 32,,) and the last inequality uses
8pg < 3. Taking the summation and expectation on the both sides, we get:
K
Blg E Bill+*
(* 1)1
Elllgtt y 212))
2
R=
<B y² (I |12
K
E
3a²
38 || + L y
Lg.1
||x -x-x x11
Ily 5²113)
+
o g2 n
9.1
B1d
Ug
n
n
k=
Using (36) and the fact that x², y is consensual. it follows that:
K+1
B of
3a 2 B
|1
<2100" y (+
I 11
2
k=0
K 33
1|0 ||
+ 11 y) 11 11
2K 2KB002 0g.1
L
E
Pg
9,1
n
n
(55)
On the other hand,
Ex
||gh+1
n
82
V 20 (at :::)
+ o
i=1
(1+
/'
1
528²
Σ
(V (x/))))
V2gi(T (00((=";"'))
+ +1/2gga**00 (h) - Veg(t" ( ((()))))))
+ g2
g.1
2,8 1
(||x x+112 2 + Ilx 1² 21| (x+))1 + 2115 s²1 + 32 02
n g.
n
31

---

where the second inequality uses 229 " v((x)) = 0.
Note that B expectation and summation, we get:
Subtracting 2,32 1. 11,11bb
701l on both sides, and taking
$.1
K
E [1
[1]
k=0
4,8² L
8,32
28² n 2i
E (1|x*
x1111 +
11y*
y²113) +
9.1 B y (xx))11
n
4 1 K
8.3 I2
g.1
K
E {
+
Elly - y )1
kml
kmm
2(K + 1),82
9.1
n
46 g.1
2(K + 1)332
E (10, 1 +
[0,11?11=?1??) +00e||++
0g
n
ua²
+ +8,821 12
100
(*9 |2
L 1|
BPg
8 p
K
6
||0 |0 112 + O 1211 12
4 KKS Ba 9.1
+ +8,322
L
E
P
naga
1=1
82 B
48I2
48a 4 12
K
4
Σ
|1 110,1111e;)
L
>
B||
1|2
n1
43
"**
k=1
A=1
KK + 1)882
32
9.1 10000 (1
8.1
+
72
Ngg
where the second inequality holds since x", y are consensual, the third inequality uses (55), and the last inequality holds since B < 327
Lemma 10 (Estimation error of (x)). Suppose that Assumptions 1- 4hold, and
1
nI2 n4gg
g.1 1.1
7 < min
(56)
Mg
23 360
g.2
9.2
We have:
K
ElI
- 1
k=
K
9a² L
E
| 112
?212
0=
K
x22 110
||0_| 2 |
K
6 ||
+ 72k
+ 72
y
n
km
k=
31122112
6(K + 1)7
+
72k 'E' [[|s
+
303
+ 111
Pg7
Pg
12
k=0
Proof. For each 1 2 0, note that
2/
k 1" (x*)) (
- (2f2 ( (*+)), we have:
n
Eg [1tt =,
k+1 *
(a v/ *+1 )
" = k+1
32

---

7 n
V 22 (a v ) (Et - + -
n
o2fi -
1/ (**))
T
n
2001
(xt W/ )(# - -=/²)= + 2
V 220h (x* ,y (x*))²)
(2 v/+1 2,-11
Then we have:
- -2a =xt1 |
Ex Ex(2tt]
|| 1
<(1 714g
1- n
V220 ( /
V
(E* (#+ =2t1)
+ +372
(1+
1
1
V2Ji( 10' (+*1))
YHkyg
1=1
1+ _
1
+ +3?
92 (a*,, ( vz*(²)) - V220((0, o/+ [] 2b41
Y//y
71
+3y2
1+ 1
_11
1
(at
Mi + +=* 18-4-12- 2t)
7/4y
71
5(1 + 714) - -194))
> )11=>
112
67
L, 1|z
=1
12 f.0
+ L3 ( ||x* (11**x**1 x²11
||y+t1 y (=*)))
+ P4
+
1
n
n
<(1 711g)
(1
7iHgg)
||
- =1112+ + (1
2
|| - 112 +
6y 12
1| 2%1
2
M49
12y
[2 1
1.0
+ L7,11 ( | ||**~ - 11
Ily+t1 - 1ht 1|2
11 +1 y² (I (13)
+ 0g
n
<(1
724
2111 211 + La
||
+
6Y L2 1|z - -z z11
2
YH4
ugg
12ty
L2.21 1.0
|x** -
x
ly 11
L7,11
|1ght1
8a (I* )13
ag
n2
where the first and third inequality uses Jensen's 's inequality and Cauchy Schwartz inequality, the second inequality holds due to Assumption and 724 < the last inequality holds since 2 (x) is L. Lipschitz continuous.
Moreover, the independence of samples implies that
E
+++1
Ex
12
11
- =
H
(H,
+ n
(b - Es 1+1)
12
i=1
273
1z
k 1
+
2
273
Zz 1|
L3,0
30 9.2
+ ||
2/112 +
+ 07
n1
12?
As y satisfies
60 9.27
B7 L, g.1
60 9.27
7Pg
n
112
n
33

---

we get:
[x11=
11 - 2 [x - = + Ex -
$ (1 (H4g)
3
|| = + 3a Li 1|50|122 + 12y
7Hg
Hg
9.1
1|z - -1211
+
27²
n
30 9.2
1
p
+ to
+
127
L2 1
+
13,11
| x+12 (1x**
||y ky
gkt111
118 ++
31" (2b))13)
Fg
n
n
Taking expectation and summation on both sides, we get
7
E|
21
2x 112
3
k=
3 L2
12y
El|z* 2
272
1
]
<B1150
2.112+ +
12
n,2
30
+
YHyy
n
n
9.2
12
k=
K
12y
T T2
xx*
x ||
Ily
33++1 112
+ 1
E
+ 11 k++
3" (3 )1
Mg
k=0
follows that
K+1
E||
&
==11 112
k=
K
9a
2
E1
2212g
km
xx Oz ? 2 1 1 ||)1
R² 10y17
kak+1pp 112
+ 72k 2
E
72k2 2
n
n
k=1
k=0
K
yr |+ + 311=211
6(K + 1)?
L
+
Σ
72k
'E [[ght1
+
30 g.2
+ f.1
1g
k=0
since 2 2. and z consensual.
Then, we combine the results in Lemmas 9, 10 and give upper bound of B[[x]:
Lemma 11. Suppose that Lemmas 9 and 10 hold. Then we have:
9a?L2 72
438k4a² a²
K
AE
31
B[4
L2
E||T*11 112 + 510k
E
B2
Pgg
k=0
k=0
6(K + 1)7
L7.0
4
4Ko
302 9.2
00,1
73
1100
12
+
nn
2
124lg
57)
Remark 6. Here T- = 1150 -1=0-20110 x x
36 (T- 1112
The aim of introducing this term is to
simplify the subsequent proofs of other lemmas.
34

---

Proof. Lemma 10 implies that:
E
2+ 11?
K
9ax² 1.
11
12
k=0
k² 02 2
|0_
K
k²
O y
k
+ 72k
2
E
+ 72k2
2
k=1
k=
31
6(K 1)
L
+ Σ
72x E [lggtt
o [+*
30
+
9.2
2
Then, using Lemma 9, we have:
K
K+1
K+1
B[TN]
= Σ E|E
=f11 + x²
y² 11?
k=
k=
K
9a L2
E E11
km0
+ 72k
Σ
E
Ox | +
+ 72k2
K
E
x
v
2 71
1|?
k=1
k=0
6(K + 1)y
30
1.0
+ f11
73x
1/" (f9)
6
L y
+1
ng
9.2
B1gg
32
31
K
100 1 1 2
O v 1| |
4K 4Ko2 0..1
+ 7
I E
13
9.1
Mgy
M
n
12/49
K
9a² L?
438k* 4 a
K
A
3 3|
+
B| 11 2 +
510x
7210 22
12
Pa?
k=
k=
6(K + 1)y
L
4Ko B
30 g.2
+ 07.1
+ 73
1750
3² (09)1²
ng
m2
814
C.1.7
Consensus error analysis
In this subsection we aim to bound the consensus errors of y, 2, x (i.e. the terms ||@/]|?, ||e][] [2,, and 12).
Lemma 12 (Consensus error of y). Suppose that Assumptions 1-4 hold, and
(1 IT, 10,, 11 | | 12
8² <
(58)
8L2 9,1
We have
K-1
0 112
E
<3
||A 11 11 1|_ E [||x* - x11112 1
[
k=
k==
(59)
|0
3(K 1)
11 ya 1
2F
Σ
1P
no
3
,0,11 A=
1
|Tyl|
g.1
1
[
35

---

Proof. Firstly, the term ||e 1|2 can be deformed as
1 11
A [eivy Vog(s* sx))
A [va B.|v11]
30, 1
- ,,0," 4
Ayo U, (oR(x*+)) 18t - VoR(X* 1891]
A Ava OJ A [Bein Vog(x*. ,(,)
( ,(t3)) 228(2* sty]
Aga U (vt Bu(v')] ||. [r (rret..005' 8o,
Axa U. [vm - }]
+
(0,'
U, [B1 Vog(x* ,81] Uy [2R(x*11 gt, PaR(x*,st)
ooy Ava U -
29
due to (33). Then, for the first term in the right-hand side of (60), we have:
Aya ÜJ
ER [v4] 22g(** .+))
Bx
r reo
_
T
12g(x*11,, , - V2g(x* (5))
1 9 11
Aga UJ y
Ex [v Veg(x* yth) [2g(xk+1 ( ,k+l1 - V V2g(x* r*)]
A
|8 y
112
Vag(x* y*) Vag(x* y+ )|(
1
|
ya
8 0 7
112
+
111
vb
1
A ya
E [1 ,htt) Veg(x* )
182 1
11
T 111665511 +
y
||Aya 2 (1|x x + lly x²1
[
8 11 12
+ 1- | 1
| 1 1/ RR [||xkt] - xt112 + || - 111
(61)
where the first inequality uses the Jenson's inequality, the second inequality hold since ||ú || S 1. For the second term, we have:
A ya UJ (vt Tyt-Ex [v] ]127 < ||0,, ||0=11 11 12o 9.1-
0-1
(62)
For the third them, we have:
/
ÿT x - -va-i 1}
(r,,,,00011
r
80-1
Aya
ÜT
= 0.
(63)
O
36

---

Next, for the last term, we have:
Aya U [v[v"] Vag(x* 559
Aya U,, (vt- Be[v"1] 1)
B.
O
,0,²
yo U, [2g((**) ,ytt) V2g(x* ,541
0
Aya U [Bslv*]- -Vgg(-- ,5:)
$2 y B
A Agu U V2g(x*+1 , Vag(x* [41]
|| Aya U. |ra Ba|v']] 12
1 , I + 2
89 |1 L Ex ||xx x011² + 11y* - y011²]]
1 10, 1 96 || LLg Es [|xx 11 + l|ghtt - y s411
+ 2
1
+ 2
5"
(64)
Taking expectations both sides of (60), and plugging (61), (62), (63), (64) into it, we obtain:
E
[1
[[]]
y
8a1
11
2
y
A 26 11
Aly yal
L 1B [|xx - xx* + || - -x11 + IT ||]
1 Fry
8
110
-12
2
1 r
yal
2 L2
E |||x* - 122 + l1y* - y"h || + 233110 y || Aya 1| no g.1
Taking summation over k and using ||x* - x-1 < | |11@51|2 Ily 501 = 10 1 12 we get:
(1
Il)
Σ
E
[|
"
k=
K O 112
2
||A wb
|
ya
12
[||* - x12 + 1|gkt1 - 1
1- [T
1=
B
O y 112
+ +llle
Elie
2 Σ
ya 1/ ||00,1111655 11 110
1
k=0
+ +(KK + 1) Oz ||
|no 9.1
yal
K 8 0 112
2
A
12 yal
1
+ +|1 -
- 1
1- T
k=
1- |
Elleg|12
Elle+ 11
Σ
[ 16 ||0 |1|8,11
O 2
+ 2(K + 1) || yal n
9.11
T I)
where the last inequality uses 62
812 9.
10 1 12 A ya 12
follows that
K+1
321 1 1|
E
[
<3
| 2b
|2 Aya 1| 2 Lg E |||
x2112 + || - 11
[ y )
k=
k==
|0, 12
3(K-
11
ya 112
2 2E[|e9912
Σ
E
[
+
no 0.1
3
O 11
1 1-
|r
1 T
K=
37

---

Lemma 13 (Consensus error of 2). Suppose that Assumptions 1- 4 hold, and y satisfies
6y 0 1 10 10
|
1?
(2L2 + +2(1 (T21)) 1- T-
(65)
22
4
We have
K+1 Σ
[1
1=
16 9.1
(1
[
1 A 1
2 6 2
Σ
E
[||a*
- 211
[1))
r2
k=U
8 0 1 ||2
A 2b
1 |
12
K
E
L7
L2
1.00
12
||x
xt11
(1 [T )2
9.2
11
(66)
8 8,
|
K Σ k=0
1
E
f.1 + 1
1 1
-
(1- |++
9.2
|0 |
1|
T22
16(K + 1)ny?
rell
My
0
9.2
+ of.1
K
B(IIO,, 12
110, [0,,1|1|6++111)
3 0=
2
k=
Proof. Firstly, Eq. (34) implies that:
Aza T. Ex - px** ,x*tt
1h+1 =r
70.1
A Aza UJ [p (xh+1, gk+2) p² (x* sk+1]]
Aza ÜJ
Ex - pd
+ 1
Then using Cauchy Schwartz inequality, we get
+++1
11
A. Ex - p²(ttxx+1)
||
< r.e.
,0,1
Aza U.
1 1ight,55429 ,.+22 D² (xe ((+11 }]
Asa Ü.
Bx(p"1 -p*] 1| -2 r- 70.1
ÜJ Exlp"1 p+]] o1]) (67)
0.1
Aza 0
Ex ip" - (xet, (xxxx,55 gb+1))
0.1
A 2b Aza U. [p ti (x++11 1 pk+z) p² (set y
A.a Ú
Ex - p*]
+7
0
38

---

To obtain the upper bound of the right-hand side of the above equation, we first estimate some individual terms as follows. Note that:
Ex [ (x*", s
Ex
22 Mi )) Valilet, 1/ - (V220 gft,, V2li(1 ||
n
V (xx V/ (= =+)1] +3 >
Ex
- - (oc(((""ttt)))e g(tt))=+|?
+ +-3
Σ
Es V2 ) - V2 2 )1
2m1
1.0
S6L 1 (1|2 =²1 1 2 +
Lg
+ b7,1 (1xx* x11 + -lyttt - 113)
(68)
and
Bx gbtz) - p*(* )1²
Ex
V2 ( ) (2fi ,g+t2 -V229 ( V2fi("", g2t11112
<3
E& 2229 12 k+1 / - V V ,(+t1))
1m1
+
ER| 32 (*t,, 1 11 + > Ex | V (2fi(E ,gh22) - V2fi(t , 11
i=1
<3E
13,1 + L2 g.2
1.0
(1x
-0--1-*1122 1|² + || - r + L3 L3 1|** - 11
(69)
Then we present the bound of the right-hand side of (67). For the first term, we have the following evaluations:
A UJ
[x - (x*,, ,
Ex
r k
A 26
[p Not (xet+) 22+2) - pd (xt 5 }]
0 3 112
A
Fe [p*] - pd (x+ )(t1) |
ER
1- || ||
2b 20 UJ
[p ++ (x+++1 2 p* (xt sk+1]]
0 |1 A 112
<>|lle 12
[B (x* y |1
T=ll
2 11000
11|211 A
[|lp
(**++ g2+ - (x* |
1 T2ll
(70)
where the first inequality use Jensen's ' inequality and the second inequality use || < 1.
39

---

For the second term, since z", yh+1 Uk we have:
Ex 1pd p 2
Aza
Ex
0
0
0
1 |
s0
| [p*] - -p* 11/
(71)
|1 [ s0
[[|I""|P0 :no
< || || 1|
(11* 2²12 + 11 2111 +
f.1
02 + nof
11
For the third term, we have:
Aga U Eslp' - p*] 11 O,
2
T 70
(72)
since ea E Us.
Next, for the last two terms, we have:
Ú. Ex [p"] p* (x*, ,h+11
Ex
O
[p (x , x p² gk+1]]
(73)
0
|| A sa
EE
[p"]
p * +
+ 0 |1 A
|
| 1
[II k (x ghtz)
p² (x** |1
Aza Ú
[x
p*]
Ex
0-1
|0 10-11' A
EE
||B [p*] - [=1]
(74)
Taking the expectation E, on both sides of (67) and plugging (70), (71), (72), (73) and (74) into it, we obtain:
Ex
[|ee
2-
0
A 20
T|
T
Ex
E& - p² px(* (xxxxx+++]])
0
||
[|Ip
(x++t( 1 x - (x* |121
1
|=
+2
||||| Aza
|I 1D*
=1212
<|
+ 12m 2 2100 11 112 20 1|
1.0
0.2 + 07.1
112
12, |0_ 1 A
(I2 9.1
+ +(1
| )
ER |||0 1 + 1| - -
1- |T-ll
6r
1 1|
L2
1.0
17,1
Ex ||
|0,11
|
6, 0 11 26
|1 za 1|
I3,0
12 + T.2
Eg |||**|]
x+112 + 1| 1
1 T
122
0- 6,
|
2b
12
L2, B.
[||x**
x 1
9.1
40

---

where the second inequality uses (36), (68), (69), and (71).
Thanks to
67
0
1- T2
(2T.2 + 2(1 [T=1)))))))
[2
4
we have:
Eg [1 [199
+
3 T
|6
12 (1
T. 10
10 11
En
[[|2* - 20.1
4
T=
L
+
0 11
sall
Mg 9.2
+ 07,1
|
x3 1
11
110 yll |11 + (13))
4
1
11 2h
13 + 1 9.2
En [||x
x*112 + 1| [6
|==
12
6y 2
0
|| 26
L2 L. Es [||x* - 112
1
Taking summation and expectation on both sides, we get:
1 (1-10) (+l
||e
<E||o2112 - [||o5+11?
(2,, + (1 01
||2 K
E
[l|a* -2
k=
1- T+|l
E[|
113)
L2 113
12n 1 1 3a 1
0g2 + oot1
6y 67 26
1221|
20
K Σ
17 + L2g
7000
+ 12 Lig
|x 12
1 |T=]
ng
A==
6- 0 1
1
I2 1.0
T,2 + T
11 Skt2
r
k=0
Thus,
K+1 E ||
16> ( + (1 2l) 9.
9.1
0 1
s0
1|2 K
Σ E [||z* - - +
2E[ 21
(1
|
1 T=
k=0
0 || A
11
A 20
2
I.2.0
2b
E
LJ + Lg
12
12,113
|x - x²/1
(1- [ 11)
22
k==
A go.
L2
Σ
L3
+ I2
||
11 81+2112
(1-1r
)
9.2
22
41

---

|0 | Aza 2
T
+ 16(K + 1)m??
2.2 + t
1
Txll
Mg
R²
+ |10 /| l 113).
3 0|011 2
k=0
Lemma 14 (Consensus error of z)). Suppose that Assumptions 1- and Lemmas 4, 5, and 7 hold. We have
K+1
Σ
B ?
E
km
E 60 12
2a Oa
12
[ - 0
za
4 1 x2)
F
(1
[z
12
6na (
K + 1)] O
112
1 - A
127.0
1 [
(++
1
|T
f
+
30
3.2
H2
(75)
2
Aza
80L2
0
180
0+
A + mld
1-
|z
T
T
9.2
k=
2T.02 1-
1|
2(1 - 0)2
K-1
+
||A 2b
+
Σ
E
|
x+
x+11
(1 [r
82
k=
Proof. Firstly, the term || 112 can be deformed as
A Azo UJ
[+tt - (+((t)]
F26
a0
1 A UJ
( -
U.
En Ex|r+t11 {
2 -0
Azo Ú.
( - (
|021
A.n U
+a aa
P T a0,"
Aza U.. [T (rttl) [tt
- 2
U. En(r {
Aza ÜJ [r+|r++1] -
+ 20²
0
0,
A And Ü.T (のイt)+)) 5
(76)
due to Eq. (35).
42

---

Then, for the first term of the right-hand side of (76), we use Jensen's 's Inequality and get:
Aza U
E3 (rrrt1] (x+*
Eg
rē a0,
U
( - {Φ((*)
0
Aze U
BB ( -
Ex
U
( (x((*)
(77)
ab
2
0
||
mall 11
Bx(rA-11 11 {x((*)) /1
B&
I
|13
A m0
1
112
{ 11
ER
For the second term in the right-hand side of (76), have:
Eg
0
A Aza
UJ
[x+t++
k+|]
][
0 1 2 Ex 1
0
(78)
0
|| 2 [u
111
Like (72), we have:
( (r.et
Aza Ú [[x[r*]]]- - - 1>] = 0.
Ex
(79)
Next, for the last term, we have:
Ea O Aen. U.
Bi [tt - -2(xt)
Aza U [Ex[T**]]
[
r(+1]
.0.1
Ara ي.
o (x))
0a"" 1 |Amll P
F 22 | /r
11 - p
+ a O |1 A
E
|
(
(80)
Taking the expectation on both sides of (76), and plugging (77), (78), (79), (80) into it, we obtain:
Ex Ex 1 112
< r 21 + 20 1 0
Am
R&
[u+*
u 1|2
+ 2n 2 0 -
Ex
[E
( +
(1 (x{))))
43

---

Taking expectation and summation on both sides, we obtain:
(1 (1- 2
1
2L
0
12
K
<B||e_112 - e +1
E x g - 1x
+
2n |n²1 10 1| 1
V (x)
/1
+
Σ
K
E
| [1
1 |
0
k=0
2a 2 00, || ma 11
2
0)2
K-1
+
18
||
|x
x+1
|TaIl
0
+
2a 1a20
112
+
2a
||
O
1 ||
A 113
8(1
0)
Σ
K
E
[u*]
u²
1
k=
2a
10 1
|
A
||
[ 0
( /19
B1
124
1
1 -
7000
+ +6(K + 1) 01
(
+
30
r
9.2
m2
800
1 -
K
+ + +0210, |12||Azall 2
T&ll
+ 180
0
|
9.2
E | nla
km
2L | + 1
A 2
|| 112
+
2(1
0)
K
|
x+11 11
B2
k=U
where the first inequality uses T.- Lipschitz.continuigg continuity of V Lemma and the second inequality uses Lemma 4, Lemma 5 and
||z ++1
z 112 s DR,
|
z 2111 S ntg-
Hence we get
K+1
k=0
E
2 1|
2a 0z | 1
1 0
क x ||²
+
|z
(1-
|
0
6na20(K
+ +1)100-1121 1| A 1|2
1
|z
0
1
1-0 0
| )
(OPA)
+
30
9.2
L
122
1.0
a²1 0 || ||
80L
1 0
+ 180
0
2
Σ k=0
E I + nIx)
|
1
Tell
1-
| m
2L2a2
||
||~-|
2(1
0)2
x
k+1
x
1²1
(1 1
0
k=0
The following lemma gather the consensus analysis of xr together:
Lemma 15. Take
3x3 32 |0, |1
O
112
|0 1 |A PA
|A 22, 16-21² (2x² -.-)
7
(1 [ 11
(1 [
44

---

1+ (1 8)
| 10 |
1x²
A
|T=1) 1)
olll 10,1i|0, 10, |I
IIA wb
+ 16L2 (2x² L 7 1= 1 P
12 =3x L
(1 [= 11)
Suppose that Assumptions 1- 4 and Lemmas 12, 13, 14 hold, and a, 8 satisfy
(1 aIll
a² 2
24x²
13
80L2 + 180(1 - [T+II) (0
T-1
1-8 22
(82)
n23²= 1
1 g.1
We have:
B[Au]
(83)
32L
s(n
+ 48k 2 12g. 72
B
R
11
Ily y1"
+(K + 1)1233
R=0
O |1 O
Ame aa
8012
K Σ k=
180
(
03.2
F/nTa
1 |x
1
|
O0. 1=.1
(
+ (1
I (=11)0022)
B|m/A]
1 ||==||
1 |T=ll
1) 11,1,111110 A ya
2xd O |
2 2
+
g1 +
|ra
K
O2 |B| 2
2x a
110
O 11
||
T=
(1 T 12
10.10100 11 AAa
12
+ 16(K + 1)ny²
9.2 + +
1 1 ||
+ 24(K 1)nx")== 2²00
0
1 1- 0
1
1
O, 1
| 1
Li
g.2 - 07,11
[+
Proof. Adding (59), (66) and (75) together, we get:
K+1
K+1
K+1 ||0.|
x² o.,
Elll
x² 10,,11
Σ
Σ k=0
B||
k=D
K
8 O
1 112
<
A 2.2
||
x112 + 1 s*11]]
k=0
O.,I"
R [|
3x3 (K + 1) O 11
11 A ya
2n 2 O
no 9.1
T
16 1 (1
22)
12 | 2
E [11a 2t11²
(1 | II)
x² x Σ O(JO., || 1|0,11 1(**)
A=0
87 (2n# + L L
O
00 1 |
Asa 2
Σ [| ++1 x511]] -x
(1
T=
x6 |0 0 11
|
K
Σ km0
E |
k+2
-+
T-1
45

---

+ 16(K + 1)my? |0 |
1
Am 1
L7.0
2 O
E
[T:]
1'
9.2
+ 0j,1
+
T2ll
11
2x
| 10
1--0
< |r]
|[
0
6nx²a20(0 20(K -1]1
|||
O
10 '1 1|
1 0
Li.0
0
0/
30
1-1
Mg
||a|| 1
SOL
K
180
(
0.22
Σ k=
A + nlal
|T=|l
1-
|T=
1
|T
2x
T.2
|0, 1 |
||A
+
2(1 - 0)²
K
Σ
x
k+z
x* 113
82
3 K+1
Σ
E
xx/p>x+110000 xf
||011|
4
k=0
K
32T 3
(m
18x Ly. 172 )a
Σ
E|| 112 72
y )1 +3((K 1):39
Bg
k==
O
O 11 Aza 12
80L
188
1 -
Σ kmD
B|m
I- [z
[
| 10 10.1
167² 1L, + (1
T
T=1)) 9.2)
B[n/s]
|
|
3x (K + 1) /110,1111100 11 1 | yall 11?
2x O 0
PB
e
O.
"E|
no +
|Tyاll
|Ty
|T,|l
O² B
2x
110
1
11
A
11?
1-
VΦ x ||
1- T=
0
|0. 1 ||
A 11?
+ 16(K + 1)ny²
1
|
11
9.2
+
24(K + 1)nk2220
1- 0
1-0 0
100
O
11
A
1|
12
9.2 + 07.1
||
1
where the second inequality uses (54) and
x²a 2
|
Azall
11
80L2 [x
1
The 22 52
+ 180
0
02
1-
12
Hence:
E[AN]
4 k=
K Σ
3213.112
<(m - 48k² Ly.11) )a
E E
1100
yx") |12 + +3KK + 1)m282 0.11
Mg
k==0
0 1 11 A zza 12222
(
807.2
1
+
(1- |
+ 180
0+
0.2
E [nTxs]
T
|T
k=0
10
1 sall 1
(L2 + (1
T=11)02.2 9.2
K
+
E[[Tg]]
1
T
Tell
3x 3x + 1) 1
112
A
yall ||2
2 6 1
2 0
no g.1 +
|Tyll
1-
|TyI
[r
x 02 |E 60 12
2k 2
0
||21
1
T1-
27
+ (x))
(1
r
2
46

---

|= 1 A ?
L
+ 16(KKK 1)m??
9 + 0/11
1- 0
10 0 - -12
A xa 1
( [
+ 24(K 1)mx2200
(0+
[1 0 + 07.1
|T
C.1.8 Proof of the main theorem
Before giving the final result of the convergence analysis, we present the following Lemma that combines the results in the analysis of I and Ag:
Lemma 16. Suppose that Assumptions 1- 4 and Lemmas 6, 11, 15 hold. Ifa, 3, y, satisfy
(1 |-,11
a²
16 Oz
10 1
1 A
801. + 180 (o 1-11.-1 (1 [ [Tx11)00
1-0
2040
B2n2= 1/2 $ 1024L2
(84)
g.1
(1 1|)))
72 <
256 |0
A |22 |
+ (1 [r21))
2040x4
and
4(m + 48x2 L8nx2Ly-1200 40
19a2L3
438k*aa
L3
)
L
to?
9.2
1
1020k
72112
B²
n
4080.4*
(85)
then we have:
K
(n($(5o)- -if +) - 0(K 1)(0),1 + +2202g))
> E[A + ntk) Sx-(m + I n2)a
0=
12222.
n (((()))) inf
+
+
+ +0(K + +) 1 + x² x202222)
12
p2
50
0
1
1,,
1|
+
no 8.1
+ k 12 (K + 1)02
T
6
,0,
|
1I 1
R O |E 1
+
T
Tell
Tal
10
113
Amal 11
1
0
+
(1
0
11 10:111100 ||2
Azal 1
+ +(K + 1)x4,2
(o7 + N2022 9.2)
1- -
1-0
1 1 A I'
1
+ (K + 328 220
0+ 1- -T
(0) + +100222)
1- T
(K + 1
+ n1|l=||?
(118²= y
Kog 3 Mg
+
(0 + +10022)
+ k
+
Hg
8F4
47

---

Proof. Combining (57) and (83), we obtain
K
E
R
B|nlk]
1020
k=0
K
1281
9. 1228
<4(m
48k L. )2
2
E
11
+
1150
)1
12(K + 1)m123223 9.1
Mg
k=
10 |1
|1 A 12a2
80L
0
K Σ
+ 180
0
R B(
[z2l
r
k=
4|10 || | 11
(L2
+ (1
| 11)0222) 9.2)
K
9.1
B[nI
|Tell
Txll
3K
1)110
11
11
A
8k²
[
80
8
8
1
no 9.1
4x 2 10
8K2
10 12
O
11
||
7 x
Tall
(1
0
|0,1 10
A 1|
+ 64(K + 1)
1- r=
9.2 n1
0
+ f.1
1 1 B
1z0 -1 11 1|2
(17.0
+ +96(K + 1)mk²
a²0
0+ 1 ||
0
9.2 + of
1
Mg
1
9a² L2
438k 4 a²
p2 L.y
Σ k=
K
111
Σ
E3 [AN]
3nl
3n|1==11
1020
1212
1020x
Ma7
k=
(K + 1) 67
17,0
73
4
4Ko2
302
j.1
+
1150
y"
(1*))
9.1
1020x4 Pg
12
1020
Bpg
Pg
(86)
Subtracting the term
2
12
O
121
A 20
807.2
0
K
180
0+
E[nlk]
1 Tz
||T>||
9.2
4
O|
1 1
1 16 2
(L2
+ (1
K
K
9.1
E[
E
A
1- T=
1 T=
2
k=-1
k=
from both sides of (86) and using the restriction of a, y in (84), we can get:
1
Σ
[[ +
E[m/k]]
2040k4
K
128L2
<4(m + 48k 12 12
El 1+11 +
9.1
1150 -
yy'(=")1
+ 12(K + 12
Mg
k=0
12k2 + 1) +
1 |121
A ya 12
8k 8
2
n1 9.1
T
T-
4x ||, | 80 1
8K
||0,
| 11
11
A Anal 112
1
0
V (x9)
+
Txll
[T 11)
0
| | z0 1|
L3
+ 64(K + ?)m?
1- [.
21
02
9.2
+
of.1
1-8
|0
| -
11
A
T
+ 966( + 2
(+
g.2 + 07
1 - |
1
Tx
48

---

9a
438x a²
K
(K (K+1) + 1)
by
D
L
13 11
30 9.2
0311
1020I
12
8"
1020xa
Mg
1ig
k=0
1
31||=211
1
4K g.
73m
1150
y y00x"))1
3
1020
Mg?
1020k
B34
Hg
9a L..
43
bgg )
K
< 4(m + 488 Ly Ly-nn)a n2)a²
+
Bl| R+1 11?
1020k
12
B2
km0
12x 3
(K
O
A 1
122
8K2
10 y)
+ 12(K + 1)12(8200
+
11 9.1
9,1
|Tyl
1
T Fy
8|10 1
4x 4x2 2 12
8x²a² 11
O 1
11
[
T 129
+
+
4 o
1- T+
1 1
x
(1 - 1T21))
|0=|| 10=12210 || 1
10: 11
1 0²
+ 64(K + 1)m?
+ t
1 |
m
9.2
+ 96(K + 1)nx²
0
1
|0 110 11
12
(L
og + 07,1
|
Tx
11
18y
1
0
+
(K + 1)
1020
11
9.2
+ 0/11
1
3n
311|221 2|
1
8 B14g
4Koa.
+
73
11y
(1=))
1020
Pg?
1020ke
Fg
where the second inequality holds since
128L2 g.
1
12.3
1
<
Mg
833k
Then taking (41) into the concern, we know:
K
BEAN +
Elmlu]
2040k 4
<40
4(m + 48k Ly 72)a²
9a² 12
438x a²
(1
002
Σ
B|A + nlal
1020x
12
k=0
+
1(m + 18k2 T.g m2)aa
9aa L2.
438k 4 àa
n(D(2))
inf +)
1020
7210
32
a
99 L
438k a
L3.0
+ +120(K + 1) 4(m + 48x L.y. w2)a
L.y
0 + 20 0.2
1020
B244
12k² (
O,
0 112
A 11
Sk²
100,
12(K
10 02.1
1
||Tl|
g.1
1
|r
4k
e 2
8k²
|0
O
1 0
(+
(1 T=
|0.|| O
|| A 1
L5,0
+ 66((4KK-- + 1)my?
0g2 oř,1
||=
+ 966(K + 1)nnaaat
0
1-0 ||T
| O0 1 |
, + of,1
T.I
113
18y
+ +(K + 1)
o + 07.1
Bg
1020x4
1
1
31
Mgy
+
1020
1
73x2 1
Bpgg
1150 y
4Ko 3
M9
49

---

Since
438k'
by )
0
40 4(m + 48x² L,- +
+
1
$
1020
12213
B2
4080
follows that
K
E + nnla
km0
10 (m + x² LL 12)= + (a2t3.
a²
n n(((To)) - inf ))
2
+
B2 b.y
12
a T2222
k²a² I
+ AKK + 1) R² (m + R² Lg 1/2 )2)
(0) =2o0222 9.2)
12
82112 8'
R 3983(K (K + 1 1 1 11
12
x , 2| 201
3 + 1)0 9.1
T
9.1
[T,
110 =
K + 26
x 0 1
T==
T
(1- [
0
+
K
10
11 : || || sell Pn
Y
[K + 1)(0),1 + +k00g,))
Pg
1-
10 1 112
Aza 112n
(K + 1)x
0 1- T
(0).1 + +2,0g,2)
r
n| n|12211
(1
Ko²
I|2
8
Pg7
B1gg
bgg
Then, finish the proof of this lemma.
Finally, we can give the proof of Lemma 17, which is a detailed version of Theorem 1: Lemma 17 (Detailed version of Theorem 1). Suppose that Assumptions /- 4 hold. Then there exist constant step-sizes a, B, Y. 6, such that
El V (x*))l
K
+ R 1
A ym
$
|00
1
20
V Vnk
Fvl
r
K
| || || || |||||
+ R2
||y'll
K
|10,11210, 1 A
11 9b
0
|
O 11
||
12 111
+
20
m11
T
n11
|
K
|10,11 O |1 ya
11 26
11350"
1 A I 11
+
14
+
1 T
r=
|0
||
11
K (NCo + +Co)
1 K'
[2
where a = max 9. Jg.2), Ca. Co are defined as:
|0 0 Azal L
Aza
A 1sb
L
C. =Lo +
+x*
+
My
1/2
+ |0, 10,, ||| x I9g1
||OlII|
||l|
|A
10g02.1
11
1
+
x²
11g
nT2 g.1
50

---

10 0 A.
L2 (1
+ # L
|
|1 |1
| |
1
r-1
022
C
+ 0.2 +1
nl. 9.1
1,2
Proof. Take 11 = 12 + (0(1 0) + LV
and use the conclusion of Lemmas and 16,
get:
K Σ
El| (2("))1
K+1
k=
(En)
inf +
(0(1 - 0) + Lvoaf") (of,) + x2
+ (1 0)2
0(K - V (5 ||
aKK K + 1)
LL'
k²a²
$(50) $
0
L1
[m
Ly.
L.y
+ (o).1 R 0z.2)
B3g
a(K 1)
A 8
1011
|1
La 72 2
+ 1.1
0g +
ITy
L1
10 ||
01 ||
e 1
x 2
(87)
K+1
m11
n(1
|T=I])
n(1
|T
(x*)
11
Azal
1 1-
11
(K + 1)(1 2 I))
10.1 11 | 1
+ L1
(o). + 220 (2.22
1 |==|l
7
+ Linh 000
0
1 0
|0.|| 10.1:1100
A
(0ū,1 + 15 22
1 ||all]
1|
Tg.1 11glg
+ Lix"
11:0 n (2"))
+
(K 1)Hoo
3H 1)
Define:
n n
00 V2gi (To, 00) V2g( b0)1
C
E [[] 20. 01) (220 + ([V2ge(To. [1) V2g (To, T1 )}
V V
+
V (2o y¹ (āo)) (20 3 (302)11
E - n
Vo x ?
Then we take:
01
1
Kg²t
(88)
P 1)
02,2
RI0 O0 | OF || A 1202
0,2
R13K||O, | y | A 103
51

---

110
0,
k:21 O y
| gal 1
11302
86
2.1
1- |
k13K 10 || |2 1 220
n11
| I1)
k
1 O 1|2 A | 56 11
9.1
|| I
0yb,2
Olls
|
| 96
11
0'zb22
O
||
PIA
11:
0.b,2
6
||
||
17 11
n
01
Ko²
00
K 2,
and
1 -1
Co
+
01
0g
VI-
1
=
Ca +
k
01
0yy
0g.3
022,3
0'yh22
0lah22
0kxhh22
02,2
0a
- (w'a),
0 (w'a),
(89)
52

---

It yields L1 O and (45), (53), (56), (40), (58), (65), (82), (84), and (85) hold. It implies that the restrictions on the step-sizes a, B, y, in all previous lemma conditions hold. Thus all previous lemmas hold. We obtain:
K+1
4 (To) inf +
0 (o
Eo
1
10,
1
A ya
17 B2 2011
+
0z.1 +
ak
0K
n
1
| 9 1?
0
EE|
1: O0 1 2
+ K
n²1
T Ill
n²1
Tell)
n11 rx
1|2
7
(o + +x2022 22002))
744g_
0
||0
11 A mal 112
n. 022
0
(0) + 22)2)))))))
|
TT
1|
1
T 9.1
100
V (1'))|
(K + 1)pa
B (K
+1
npg
1
x a
0 1
11
Aya
112
K2 g.2)
+
0K
+
ak
n
+
y
9,1
,0 111 , 1 A yal
||
112
0
|
26 1|2
yb
12
K
R
a
(1 T |
(1
| |]
n
1 10 |3 A ya
113C0
12 2| 10 1 A
A 2b
11:58
K(1 T Ill
K(1
T=
10
||10, , 1 Azu za
1
1::00
26
K(1
12 2 10 1 x 11
12
10 10 1
20 || Raa
(o + 12022)
1 T=
(1
n
Can
R² R022
K²01 (o), + 20022 g.2)
K
+ K 9.2)
K +
+
on +
K
01 K
|0,1 - |0 v 11 yal
112
9.2
K
9.1 +
|r I|
0g22KK
10, 10 1 || A ya
1
11
10
12 9.3
T
k
(1 |T 11)
y.3k K
|0 1 11 am ||
1
112
2
zb
g.1
0
(1 12
0= K
110,,111100 1| | gol!
||
|AAAA yb
11
K | y II)
agb,2K
12 12 10_112|000 1|
za | 2b
11250
K a
+ 22622
K(1
Il)
R:
O0 10 1 .r 11 A |AAI1 mb
11250
+ axb22
K[1
axb.2K
|0.131 1 A
+ 12
(07 +x30g22)
|
0z.2K K
|0, | |1 A
2 + 0z K + 4
+ k. 2
02
(o) + 02202
B₂K'
53

---

where the last inequality uses (89).
Finally, substituting (88) and (89) into the last inequality, get:
(
K +
0=
K 0
10y12210,
A gaa
10
1
O
1
K
y
+
V Vnk
K3
O
||
o
+
|ryIl
K
|10 9 12 11 V 11 yo
| y/h
1|2
k |0=1|>1100 |
n(1
|T 11)
n(1
[r=1)²
||0 1 8
1 11 A
|
|0 0 - 11 20 | 1
yh
*
|
||0 20 -1 1|21 [| Aza
1 26
11
$1
$7
+
K + (nCa + xxCC)) K
1 1
2
where σ maxx(Tf.a 1g,1 0g.2).
Remark 7. From the proof of Lemma 17, the impact of the moving average technique variance reduction becomes evident. The term oo² absorb a² a2m)'², which includes the high order term a' o² Additionally, compared to y. 2, the quadratic term related to o² of has an extra term 0 multiplied in the numerator Oo²2. These details reduce the impacts of noise terms related to æ. confirming the conclusion that terms related to y, z dominate the rate in precious sections. Notably, taking 0 < 1 indispensable our proof. we take rate (see the first inequality of (87)), since the coefficient a² //2 a² //2 O(1). This would not guarantee the convergence of SPARKLE.
there would be a constant term o. in the convergence
C.2 Analysis of consensus error and transient iteration complexity
From Lemma 17, immediately obtain the transient time complexity of Algorithm 1. Here omit the impacts of the condition number K.
Lemma 18. The transient time complexity of Algorithm has upper bound of:
|0
2
2
(100
12 2
max
||Aga 11: n
||Azall?
Ty
Txll
|0 |11 $
|0
2
||Aral1?,n
||Agall.
|ryl
(90)
0
O
||
O
| 2
11 A
||Agall.n
T=
O
|1
|
||| |--1
|
Proof. According to lemma 17, SPARKLE achieves linear speedup if:
| y || 1210
1121 12 $ +
|
$
r
K
3/
54

---

|10 1
|ryll
K
|0 10
11
10 10 - A
1
+
n21
[
n(1
r )
K
,0 1 || ya
11 ub
11
10 110 11
1
21
Tyl
[
|0 11
A
A 26 50
+
+ (Ca + Ca)
[
K
K
It holds when K satisfies:
10 1
| Ayal
1
1
1 |r
K
VnK
|00 10 1 1
11
1
[
K
VnK
10,112100
1 A
ya
n(1
T
K
Vnk
|
O
K S 1
VnK
|0_1 10 0 || Aga
| | 76 113
1
K 2
n21
|T
Vnk
|0, 1
A ya
121
yb
11
1 K VnK
1
O
2
0 1 |||||
A
2
I 7 11350
1 1
N K Vnk
00.
10
||
A T
|2| 26 11
1 1
1
K VnK
1 < 1
(Ca Ca)
K
Vnk
Then get:
| 0 1 |T
[10. 11
K R max
nd
1A
1|Azal1",
1- [.
||0. 10
2
|0, || 111 |1
n²
||
||Aylll
1- [
T
|0
|11
10 1 |1
za AA
||Azall.n
T
00
O
55

---

C.2.1 Consensus Error
Lemma 19. Suppose that Assumptions 1- 4 hold. Then there exist constant step-sizes o, B, 8, such that Lemma 17 holds and
K
k
x
x*1
I|y
1
K
n
R=0
n Sk
|021
A 1?
10
1 y
11
A 112)
K
1 - y/l
where SK denotes the the asymptotic rate when K + co.
Proof. Suppose B, 7, and 0 satisfy the constraints given in (88) and (89), which ensures that
Theorem (Lemma 17) holds.
For clarity, we define the constants:
9a² L23
a2
Oo 9.2
01 2212
P2g y':
02 = 10
L +
n
Then there exist a, 3, 7, and 0 that satisfy the constraints in (88) and (89), and also:
< 0.01L 02 S 11122
(91)
We take such values for step-sizes in the following proof. We proceed by substituting (41) into (57). yielding:
((a))
inf +
K-1
30 n
17,00
EL
<4c1
+ C2
k
K
0f.1 + 20
9.2
a
71
K
A
31
+ 510k 4
E
Mg9
k=
6(K + 1)y
37
4
4Ko د B 11phg
30
+
f.1
2
73x*
1100
(1
ng
p2
B14
Subtracting C2 Σ k=
-1 [[ from both sides, we get:
$ (0))
inf +
L7,0
A
| 1|?
E
K
07.1
+
0
+ K
E
m2
k=
Ky
T22 .0
1
Ko
0
+
0
xx
11000
- y (x
(1))
3
9:2
2
BBg
11/1g
Substituting (57) into (41), we obtain:
K
+++ 2
E
F
4
k=
(To)
inf
+
+ C2
E
A
C2C1
Σ k=
1|
a
k=
K
3| 112
6(K + 1)r
I:2
+ 02
510k
4
30
07
9.2
2
k=
4Ko?, , n2/lg
+73k
11
112
Bpg
+ 30
T.7.0
(K 1)
of.1
+
20 9.2
22
56

---

Subtracting C201 Ex= k=0
1| from both sides, we get
K
E
|
k=
(5n)
inf Φ
Ak
0 K
1000
jj
0g22
ni
n
R=0
1
Kg
1..0
1
Ko nigg
pg
Pt
9.22
f11
+ xt
B1g
1000
y2 (t
Taking
a²
10>13 A
2T2221 2.1 + (1 - -|T==Il00
m7s =
IT
1
T
1 - |Tzll
and combining previous results with (83), we obtain
K
E [Aa
S(n
x² L2 3 72 0 2
E
kM2
(2
+ Kn 8 2 7/3 Σ E| E(n
32 K
x²
1|
,
10.1 2B 60
ya
no
r Wl
|r
R2 21 | 2
x 0 12 y
12
20
T
0(1
[T 1
10 11 20 11
Knn²
(N20g + o%,1)
10 ; |[ I)2
|1 112
+ Knn2202
(x2002 n.2 + +7,
(1
K
4 2 [In + m)))²=))aa +
| + k - (+0))1 + K22 9.1
1==
+n (m + LZ. 12) + 773
+ n
K (o+ + x200g2)
+
1
+
Ky
(n² (n20g g.2 +
Pby
Mg
Ko²
3.2 O v || 110 y
|| yu. 112
+x*
+
g.l
3
no
84g
nlgg
1 |
N²
O
1 1
Apoll
(x))) ||
0(1
21,0,, R:
9
||0_ P
80 12
A21 O | 2
1-
r
[
||0.1|21
|| 12
+ Knn?
(n 9.2 + o7.1)
Tell
|0,1
||21|A mna
+ Knn. 202
x
(R202 9.2 + +7,))
x 1))
(88) and (89) imply that
| 10 | 11?
7 S 2
2
122 S 13?
(1
[
(m + x² 2 y
1/2) )2)
S x1
173 S
57

---

where 7,, 72 are defined in Lemma 15.
Then taking az ,8 7, 0 such that (88), (89), (91) hold and x [mn + x² 12. 12) 17s is sufficiently small constant, we can derive the following result:
K
E
K
R=0
K77255
+ 1/2322 9.1
n
+ [mn + K² ly 12) + 173
ak +
(0),1 + 2002)
+
+
Y
(N202
9.2 + +0%11)
Mg
1g
02 g.1 3
x² 2²
O
A
ya 112
+ [m + x² by 12 + 173] 6²
BigK K
+
9.1
x²a² 0, 0 1 11
k2 12 y
E |
|0 - 2012
x 1 1 2012
(K(1 |T,|]
(1
Kn
(1 T Kn
(1
r 12
Kn
|0
10 1 22
0 1 11
ra !1?
(n:02 9.2 + 07,) + +Raa2
(n² 2
1 |
(1 r )
K0 12a
+ 10 9.1
+ 1
[m] + x² LL 12)a n3
K
K
0
+ k a
999011 m.l
02
+ [m
+ x² 2 02 + ns
(o) + +n200 9.2)
(Re 9,2 + oo,))
No
1
0 1= || A va 11?
ya
rry
9.1
K(1 - |
10
1 9 || go!l
| 113
$ O2 1 19-11210 20
1 2b 1::6
K(1 T
K(1 [=
1 00 11
|2 11368
K(1 T
|2.12||0 |
N a
(N (N'gg2 + o7,1)
1- T
| 1
+ n² 20
(N302 o7,1)
(1
From (88) and (89), we can determine the asymptotic orders for a, 3, and when K
+ 0c
a=
V Ko²)
B 8-0
Ko²) --OVi''
n
7= 0 (vv
Ko²) (Ko2))
n
0 8=0
km
n Ko²
Then we get
K
Dx
2
1 1 |0, 1 111
yo
K
K
K
K=
where Sx denotes the the asymptotic rate when K + 0o.
Then using (36) and the definition of Ag, we get
x 1|
111
n
n
O
1|2
A
1
11 11
A 112
K
K
r
58

---

In particular, the corresponding result of SPARKLE variants that using EXTRA, ED or GT is
x
x
lly
1
1
E
K
+
K
n
K
Py
1 Pz
k=0
where Pys Pz spectrum gaps of relevant mixing matrices.
C.2.2 Essential matrix norms for analysis
Common eederogeneityycorrettton algorithms, including ED, EXTRA and GT, satisfy Assumption
3, according to transformations (31), (32) and discussions in [2, Appendix B.2]. Then Lemma 3 ensures that [[]] 1. From Lemma 18, the transient time complexity depends on the coefficients A 1|2. ||A, I|2, and ||T]] The solution of these matrices constructive. Table presents the upper bounds of these coefficients with different communication modes. Please refer to [2. Appendix B.2] for more details about the construction of these matrices and the computation of relevant norms. It is required that W is positive definite for ED, EXTRA, and denote the smallest nonzero eigenvalue of W by p. can view as a constant. Otherwise we replace W with II (1 (11-17 t) W for some constant t E (0, (e.g. t 1/2).
11 112 1
Substituting values of |O&Il. 0 '1, sall || II, ||T,|| into (90). we obtain the explicit transient iteration complexity for some specific examples of Algorithm 1, which are listed in Table 2. Note that all GT variants exhibit the same transient iteration complexity.
Table 4: Upper bounds of coefficients for different heterogeenettycooreciiin modes in Lemma 18, where notation O is omitted for |||| and | |-1-
Mode
A
B
C
||0]
|0-1
||
| '1
|
ED
W
(I
W)
W
1
p-
P
(1 (1-p) p)
vp
EXTRA
(I
W)
W
p
1
(1-p) p) 1
vp
ATC-GT
W2 I-
W
W
1
1
Ø²
(1 (1- p)
1+p
2
Semi-ATC-GT
W
I-
W
W
1
1
p
(1 - p)
1+2
Non-ATC-GT
I
W
W
1
1
1
(1 p)
1+e
C.2.3 Theoretical gap between upper-level and lower-level
Note that ||Asall < 1. We rewrite the upper bound of the transient iteration complexity in Lemma 18
as
maxin 8g. n n2s,, n² n20z. ndy, nd nd
(92)
where
2 |0, 10,111100
|00 O 11) 2
||0, |10.1100,""
A 11..8
|A 1,,11,..
|
1 [,,
1 |-
T-
11 $
|
|
|10.1110: 11
8,
8.
T.
|
10 1
|
A-71
(93)
Suppose that the communication matrices and heterogeneity methods for updating x, y, z, i.e.
| |o,1 = | 11.1 |0
| |
||
[
|
||A me
Ayoll
A 11.
|| = -|
59

---

Then we have
5x 2 6, = 62, 8, 2 8, =8,-
(94)
Now we fix the update strategies for y, z. (94) implies that we can appropriately increase 6z. 8, while keeping the transient iteration complexity (92) unchanged (at most scaled by constant factor). For example, we can use moderately sparser communication network for updating than y. 2. We illustrate this point with three examples: SPARKLE-ED, SPARKLE-EXTRA and SPARKLE-GT (variants), where y, 2 share the same communication matrix W
SPARKLE-ED, SPARKLE-EXTRA. From Table have
= (11 )) ((
=
_ = (1- 0
( -1-
-)
Substituting these values into (92), we get the transient iteration complexity is bounded by
max {n² (1 p (W+)) n (11111ppp))) ((W)))
SPARKLE-ED will keep the transient iteration complexity n² - p w, (the dominated
term) if
(1 - (-P(W))) vn(1 ([([11p(W;)))) -
(95)
SPARKLE-GT variants: Results in Table imply that
6 O ((1 (( )) = 6, 0 (1-p(W,))) (W,))
((1
8, O ((1-p
- (11-
Following the same argument as before, we have the following upper bound of the transient iteration complexity of SPARKLE-GT
max n1 (1-1-p1 P(W))(W.))) =))= n p(W,))= n(1 - pl (W,))
we get the constraints of the spectral gap 1 p W that maintains the transient iteration complexity max n - ((W,)) n(1 ((W,, ))
(1 - p W 2) S max [ - ( (W,) ,) (
n 1/2
p ( -))-+
(96)
Denote the communication times per agent of W a, W, by cz. cy respectively. For example, we have
C = 2, Cy = n 1 when taking Ring Graph for x (i.e. [W..] [aak * 0 li jl E (0, 13 ). and
Complete Graph for y (i.e. W, = 1,
Then for each agent, the communication cost per round is OC.,p cgg). If we take = Cg cx/Cy to measure the relative sparsity the two communication matrices, and consider cy = 0(1), then for each agent, the communication cost per round is O(ap + q). (95) and (96) theoretically provide the range of the sparsity (connectivity) degree of W. a relative to W From (95) and (96), we can set < 1, while maintaining the transient iteration complexity for SPARKLE-GT, SPARKLE-ED. SPARKLE-EXTRA.
C.2.4 The transient iteration complexities of some specific examples in SPARKLE.
Now we compute the transient iteration complexities of each SPARKLE-L-U algorithm, where L, U E {GT (variants), ED, EXTRA). For brevity, here we assume that W. = W, W z, use the same heferogeneity-coreetio
method to y, and denote the spectral gap 1 p ((W, by 1 p.
Substituting the results in Table into (92) and (93), we get
8, = ( (1 p)3
5, = 6, = ( (0(--0p
(1 p1-p)} p)3
for any L, U {GT (variants), ED, EXTRA].
8, =0 (1 - 2)2
0
(1 3/2
(1 pp)3//
60

---

for U {GT (variants), ED, EXTRA) respectively, and
( ,0 (1 p)²
8 =0 (11 p)8/3
0 (1-p) p)3
for I = (GT (variants), ED, EXTRA] respectively.
Combining the above results, we can directly obtain Table 2, the transient iteration complexities of SPARKLE with mixed heterogeneity-correecii techniques in different levels.
C.3 Convergence analysis in deterministic scenarios
The following lemma gives the convergence rate of Algorithm without a moving average when there no sample noise:
Lemma 20. Suppose that Assumptions 1-4 hold. If o² then there exist a, 3, r and 0 1 such that
K K
k=0
|1
1 y || A
2
yb
(2
$
+
K
O2
|
12
A 20
1
26
1
$
1 |ryll
K
K
10, 1 Amo |
11
1
+
Ca
CaK'
1
Tz
where Co is series of overheads which defined below.
Proof. Note that o² implies that L, = O(T2) when a = =O(L=b). Thus (87) implies that:
E (2
+ (Fo) inf $
a(K + +1)
(a=Li..
a2 12
/ ]
(3))) inf +
1
* + k2 12 12)= +
(97)
12
32
a(K + 1)
O 1 20
x² 0 2
2
2
n(K () |
n(K + 1)(1
T2ll)
n(K + 1)(1
||
1,2
(K +1 + K + By4
110o - (12))
61

---

Then we aim to choose the stepsize a, 3, Define:
10
A
IL
A |||A
Co =1 + x
L2 9.1
110
| 1g
A
A
+ k²t Lg,1
Pg
T
||
O
sa
|0
A
K L
zb
|r
0yb,2
13
||
11 46
112
1
2
0zh,2
1
12
||
A
16
T
022b22
00
12 A
A
126
Then there exist
= θ Co +
a 2b,2
+ و yb22 + xxbb,2
+
. - (
such that (45), (53), (56), (40), (58), (65), (82), and (84) hold. Then all previous lemmas hold.
Then from (97) we have:
K
K
+
k=0
110,,1111000 |1
11
K
aK
K[1 - T
a=2 12
| 1 11 A za
| zb
11855
a0 1 11 A
|
11
ma
K(1
T
K(1
T
$
16
|
|
1 || A ya
1
12400
O2 0 1
A 20
12
24
y
yb
+
26
K
K
11
12|
11356
1
+
mb
+ Ca
Tx
K
K"
C.4 Degenerating to single-level algorithms
We consider the bilevel problem with the following upper- and lower-level loss function the i-th agent:
|lr| 2
F.(x. y. 6) F((x, b)) G.(
Actually, this optimization problem with respect to is single-level, since we have z" = 0, y = 0, we get the following single-level algorithm framework for decentralized stochastic single-level algorithm. As we discuss in previous sections, it can recover various heterogeneity-coorcctin algorithms, including GT, EXTRA and ED, by selecting specific A Bz, C..
w/ (i <tt) by induction. By taking
62

---

Algorithm 3 SPARKLE: degenerating to single-level decentralized stochastic algorithms
Require: Initialize x = 0, d% 0, learning rate O'..
for k 0,1, K - 11-11 do
x x++1 = C2x² - A B. d = dh + B,x
end for
In this case, we have 2x = 0. Vu = 0. Notice that Ly- = 0, L = It gives
82 10y121100 y 11 pm
11 11
10
10 ||
1/ 0
(1 r
(1
+ a (1
(1 0)2
110
1
|1 A
1211A_
0
5
82 1
72
If we take
T
S min
1
0 x
0
|0
0
and 0 1, + 0, 7 + 0, then (45), (53), (56), (40), (58), (65), (82), and (84) hold. Thus all previous lemmas hold. Then (87) transforms into
K+1 Σ
k=
f(xo) inf
1
0)²
+ n
(0(1 8) + att)
0/.1
|V (x9) ||
a(K + 1)
0(K + 1)
(50) inf f
|00, |E 2
+ m
+
-a j.1
a(K + 1)
n(K + 1)
a² O0 |
2
0 n
Σ
(=))) ||
n11
[ ( +1)
0
1-0 0
|0,, 12
0
11 A Amll
11
+
20
0 1- |
07.1
T
It follows that
Σ
{
K + 1
(To) inf f
ao 11
+
0 1
12
A
za
1 11
( ((K+1)) +1) n
(f(wu) - inf f
-
1
0/1
a(K +
n
(1
T 1))
|0 60 1|2
|0,1 11
07.1
n(K 1)(1 I2l)
(aa) inf f
a0 /
1
||
A
a(K + +
n
a² a2110,,, |2|| 1| 1
113
|
2
1 11 A na
12 mb
112
(K + 1) T-
n01
[ 11)
(98)
63

---

Like (88), we take
0
Azall
0
Co
+
20
Tx
T
01
Ko
02
K
O
2 ||0
||2
A
maa
113007
|
03
|0 0
|
11
11
n2
|
04
K
12
1
Ana
12
1bb
1
1
a=
θ
Co
+
+
01
02
a3
04
Substituting these values into (98), we get
K
2
Ff Vkk
10,10110=7110
|0
1202
K 2/3 Co
K
Tzll
K
k=
O0, |
.m
| 2b
1
|0
A xm
A 11
K K-4/5 4/5
(1- 1+
K
n21
rx
Like Lemma 18, we get the transient iterating complexity for Algorithm 3
n 0 1001110
|
[|Ama]]:;
||Azall. Mlm [I
T=
[
Substituting the value relevant norms in Table 4, we get the transient iteration complexity for GT, EXTRA, ED are
o 0(max (1 p)2 (1 (1-p)8/3
n
1)
3 p)2
n
0
(1
p)
respectively, where := p ( These upper bounds are the same as the state-of-the-ard results shown in Table 1. It indicates that analysis accurately captures the impacts of updates each level on the convergence results.
D Experimental details
In this section, we provide the details of our numerical experiments discussed in Section 4. We also provide addition experimental results which are not mentioned in the main text due to the space limitation. For all GT variants, focus one typical representative, ATC-GT, in experiments, which we denote as GT for brevity. All experiments described in this section were run on an NVIDIA A100 server.
D.1 Synthetic bilevel optimization
Here, we consider problem (1) whose upper- and lower level loss functions on the i-th agents (1 < i N) denoted as:
[|A,21 - ball?].
fa 3) = EAA.b.
9. (x v) -EA..
|| 2212 + Cr |1v [101
64

---

305
(0 Fully connected, severe heterogeneity
127
(60 2D Torus, severe Interogencity
39
(60 Adjusted ring, severe becoregenetyy
SPAOKLE ED
SWAKLE-0T
127
SPARKIL
30
SAMMLEE 61
SAADILE ED
SPARKLE EXETAM
SPAAN F- E-CXTRA
SPNAKL
10
13
10
22-4
number of gradiom eniuasion
number gradient volustiora
number of grudeet eraizatons
122
(40 Pully corneoted, mid heterogenety
(4) 2D ToNus, mild heterogeneity
10
(0 (QAdjustedd ring, mid Ieteroenneiyy
0-500A
0.523A
0.50BA
SCHAVLE 62
SPARKL
SPAAKLE-SD
S-AISLE EXTRA
IK. E51
SPMOKU2-XXT1A
234
40
mumber grodert PvAkustons
number of gradec sollaation
rumber ofg.ssiitteaeooo ongosiinneoouuttii enakuntion
The estimation error of D-SOBA, SPARKLE-GT, SPARKLE-ED, and SPARKLE- EXTRA under different networks and data heterogeneity.
Figure 4:
where x E ERD.y yy E RRK and Cr denotes a fixed regularization parameter. For each agent i, we firstly generate the local solution 4i as y = yy + <i and x A'" + &.. where x ~ (0, Ix) is a randomly generated vector, each element of A is independently sampled from N/0,99 9). The observation (A., 6;) on agent is generated in a streaming manner by A; A + -i b. x + th, in which each element of o; R KxD and v E R² are independently generated by (0) The terms & ~ (0, of kk) and C ~ NOO, (00,0% (D) control the heterogeneity of data distributions across different agents.
We set D 20, K 10, og = 0.001, C, 0.001. Then we set on 0.5 to represent severe heterogeneity across agents and 0 = 0.1 for mild heterogeneity. We run D-SOBA, SPARKLE-GT, SPARKLE-ED, and SPARKLE-EXTRA over Ring. 2D-Torus [37], and fully connected networks with N = 64 agents. The moving-average term 0 = 0.1 and the step-size at the I-th iteration are 0g = 3 = 7 = 1/(500 0.014). The batch size is 10.
Fig. 4 illustrates the averaged estimation error Σ> 1 | 10002"" =11 - of the mentioned algorithms with different communication topology and data heterogeneity. It is observed that SPARKLE with ED, EXTRA, GT achieve better convergence performances with decentralized communication networks. Meanwhile, SPARKLE-ED and SPARKLE-EXT sparsity of network topology than SPARKLE-GT. All the results are consistent with our theoretical results.
more robust to data heterogeneity and the
D.2 Hyper-cleaning on FashionMNIST dataset
Here, we consider data hyper-clean problem [44] FashionMNIST dataset [48]. The FashionM- NIST dataset consists of 60000 images for training and 10000 images for testing and we randomly split 50000 training images into a training set and the other 10000 images into validation set.
The data hyper-cleaning problem aims to train a classifier from a corrupted dataset, in which the label of each training data is replaced by random class number with a probability p (i.e. the corruption rate). It can be considered as a stochastic bilevel problem (1) whose upper- and lower-level loss functions on the i-th agents (1 < i < n) are formulated as:
Se(x, v)
1
Σ
L(((E))))CE))
(E)) ma!
g( v)
Σ
D
(
65

---

number of gradlent evalustion
3000
SRARKLE
SNAKKE EXTRA
number of gradient evaluutions
2500
SPAPLLE
SPARKLE EXTRA
2500
SPARKLE-EINGT
2000
SPARO E-ED-GT
2000
1,000
1500
1.000
1000
500
0.50
0.35
0.50
0.55
accuracy
accuracy
Figure 5: Hypergradient evaluation times for required test accuracy in hyper-cleaning problem. (Left: p 0.2; Right: p = 0.3)
where & denotes training model while y denotes its parameters, L denotes the cross-entropy loss function and (xx) = (1 + + is the sigmoid function. D and D' val denotes the training and validation set of the i-th agent, respectively. C >> 0 is fixed regularization parameter.
Data generation and experiment settings. In this experiment, we let be two-layer MLP network with a 300-dim hidden layer and ReLU activation while denotes its parameters. For 1 S i S 10, we sample probability distribution P. randomly by Dirichlet distribution with parameters a = 0.1. The training and validation images with label i are sent to different agents according the probability
distribution P,. Then D!!)) and ()
pat are generated sufficiently heterogeneous [32]. We set C' 0.001.
The batch size is set to 50.
Convergence performances with different corruption rates. We set the moving-averagg term 0₂ = 0.2 and run D-SOBA [29], MA-DSBO-GT [10], MDBO [21] SPARKLE-GT, SPARKLE-ED, Adjusted Ring graph with n = 10 agents and = 0.1, 0.2, 0.3 separately. The step-sizes for all the algorithms are set to
SPARKLE-EXTRA SPARKLE-ED-GE and SPARKLE EEEEEE-
Oi 3x 7 0.03 and the term yj in MDBO is set to 0.5. The weight matrix of Adjust Ring
W = [ satisfies:
a
j = i
Waj
a
if (j i) +1,
2
0, else.
Moreover, we run SPARKLE with ED in the lower level and auxiliary variable and gradient tracking in the upper level (i.e. SPARKLE-ED-COE and auxiliary variable and gradient tracking in the upper level (i.e. SPARKLE-EXTRA-GT) and compare their test accuracy with the other four algorithms.
well SPARKLE with EXTRA in the lower level
Figure shows that SPARKLE LE-ED and SPARKLE-EXE SPARKLE-CO G. Meanwhile, SPARKLE-EXTRA accuracy, as do those for SPARKLE-ED and SPARKLE BEARKLE-ED-GT, which matches our theoretical results in transient iteration analysis. Figure presents the times of gradient evaluation for different test accuracies of these algorithms at = 0.2, 0.3, demonstrating similar results.
outperforms in different cases than SPARKLE-EXTRA-
achieve similar test
Influence of network topology. We set the corruption rate 0.3, the step sizes ag = 3 = 7 0.02, and the moving-averagge term 0g 0.2. Then we run SPARKLE-EXTRA and SPARKLE-
EXTRA-GT on network containing π 10 nodes with different topologies in the following two
cases:
Fixed upper, varied lower: z communicates through a five-peer graph; z communicate through different adjusted rings with p 0.647, 0.828, 0.924, 0.990.
Fixed lower, varied upper: y. z communicate through five-peer graph; æ communicates through different adjusted rings with p 0.647, 0.828, 0.924, 0.990.
66

---

(6)SPARKLE-EXTRA; Fixed topo X; Varied topo of (BJSPARKLE-EXTRA: Fixed topo y, Z; Varied topo of X
test accuracy
test accuracy
0.6
0.5
8.00
0.5
5.00
0.7
5.0
0.4
0.4
0.1
0.3
0.3
p=
0.647
A0E
00.924
0.2
p
0.647
AIE
200
200
p=
0.924
p= 0.828
0.990
0.828
p= 0.990
500
1000
1500
2000
2500
3000
3500
0
500
1000
1500
2000
2500
3000
3600
number of gradient evaluations
number of gradient evaluations
(G)SPARKLE-EXTRAGOT; Fixed topo Varied topo y (6)SPARKLE-XXRA-GG) Fixed topo y; Varied topo of
0.8
0.8
0.7
0.7
accuracy
0.6
test accuracy
0.8
0.5
0.5
0.4
0.4
0.79
0.3
0.3
0.5
300
170
300
0.647
0.924
==
0.647
0.924
0.828
0.990
0.828
0.990
500
1000
1500
2000
2500
3000
3600
500
1000
1500
2000
2500
3000
3500
number of gradient evaluations
number of gradlent evaluations
Figure 6: The average test accuracy of SPARKLE-EXTRA and SPARKLE-EXTRA.GT on hyper- cleaning with different communicating strategy of x,
Table 5: Mean and standard deviation of the average accuracy of last 40 iterations during 10 trials with different moving-average terms
Algorithm SPARKLE-GT 0.7080 1 0.0215
0.05
= 0.2
0 0.3
0.7045 1 0.0126
0.7064
0.0113
SPARKLE-ED
0.7096 + 0.0074
0.7113 +: 0.0047
0.7110
0.0081
SPARKLE-EXTRA
0.7190 + 0.0103
0.7277 + 0.0090
0.7243 + 0.0028
SPARKLE-ED-GT
0.7064 + 0.0063
0.7178 + 0.0037
0.7162
0.0041
SPARKLE-EXTRA-GT
0.7198 + 0.0051
0.7262
0.0058
0.7247
+ 0.0048
The weight matrix five-peer graph [wiglaxn satisfies:
0.2,
(j 1)%n = 0, +1,
wij 0, else.
Figure shows the average test accuracy of both SPARKLE-EXTRA and SPARKLE-EXTRA-GT over 10 trials. indicates that the test accuracy decays with increasing spectral gap topologies related to y, while the topology of is fixed during the whole iterations. However, such convergence gap becomes milder when the topologies of y, 2 are fixed and that of x varies. This phenomenon supports our theoretical findings, which suggest that the transient iteration complexity is more sensitive to the network topologies of y, than to that of x.
Influence of moving-average iteration on convergence. run SPARKLE- SPARKLE-ED. SPARKLE-EXTRA SPARKLE-ED-GT, and SP.RKLE. EXTRA-GT on an Adjusted Ring graph with n = 10 agents, = 3x 3000 iterations. We obtain the average test accuracy the last iterations over 10 trials, and present the mean and standard deviation during the different trials in Table 5. We can observe that most algorithms achieve the highest test accuracy when 0 = 0.2, which may prove that suitable can benefit the test accuracy in hyper-cleaning problems.
Moreover, for 03 0.05, 0.2, 0.3, we
0.03 and p 0.3
67

---

4.0
SPARKLE ED
MOBO
SPARKLE ED
MDBO
3.5
SPARKLE-EXTIN
Single-level
2.5
SPARKLE-
Single-level
3.0
SLDBO
SLDBO
2.0
test loss
2.5
test loss
2.0
2.5
1.5
1.0
1.0
0.5
0.0
250
750
1750
250
750
1250
1750
sample
sample
Figure 7: The test loss against samples generated by one agent of different algorithms in the policy evaluation. (Left: 20, Right:
10.)
Table 6: The average training loss of the last 500 iterations for 10 independent trials in the distributed policy evaluation.
Algorithm
N = 10
20
SPARKLE-ED
0,2781 1.09 x 10 3
0.3198 = 3.21 x 10 3
SPARKLE-EXTRA
0.2743 0.88 x 10-3
0.3207
2.94 x 10-3
MDBO
1.0408 + 4.51 x 10-3
1.3293 = 8.38 X 10-3
SLDBO
0.4132 1.18 x 10
0.8374 = 2.47 X 10
Single-level ED
0.2948 0.92 x 10-3
0.3164 -3.12 10-3
D.3 Distributed policy evaluation in reinforcement learning
Following the result of [52]. we consider multi-agent MDP problem in reinforcement learning distributed setting with n agents, Denote S as the state space. Suppose that the value function each state S is linear function V(s) o x. where o, E R is a feature and E R is parameter. To obtain the optimal solution x", we consider the following Bellman minimization problem:
min PER
F(x)
( x ES [r'(8, + x
71
S
1=1
FES
where (s, 8') denotes the reward incurred from transition to s' on the i-th agent, y E (0, denotes the discount factor. The expectation is taken over all random transitions from state to s'. It can be viewed as a bilevel optimization problem with the following upper- and lower-level loss:
fa(z,)) y) 2|5]
Σ(o yz)?
g, 9) = Σ (y. - Es (00
SES
where y = (y1,... ) E Rl In our experiment, we set the number of states |S] = 200 and m = 10. For each s E S, we generate its feature &, U 1im The non-negative transition probabilities are generated randomly and standardized to satisfy Eves Ps,s 1. The mean reward (iss s') are independently generated from the uniform distribution [0, 1]. In each iteration, the stochastic reward r' (s, s') ~ (s, s'), 0.02?).
For = 10. 20, we run SPARKLE-BI E-LEEEEDDEE and SPARKLE-EXTRA as well as existing decentralized SBO algorithms MDBO [21] and SLDBO [16] (here we use the stochastic gradient instead of deterministic gradient) over Ring graph. For MDBO, the number of Hessian-invers estimation iterations is set to 5. The step sizes are 0.03 for methods. Figure illustrates upper-level loss against samples generated by one agent for 10 independent trials. Table 6 shows the average training loss of the last 500 iterations for 10 independent trials of the four decentralized SBO algorithms as well as single-level ED [56] (For bilevel algorithms, training loss means the upper-level loss here).
68

---

0.7
0.7
D-SOBA
Decentskieed MAMI
0.3
0.3
SPARCIE-ED
0.1
0.1
Decert MAML
4000
6000
10000
12000
14000
10000
12000 14000
Smmgg))
Figure 8: The accuracy on training and testing set of different algorithms for the meta-learning problem.
Both Figure 3 and Table 6 demonstrate that SPARKLE-ED and SPARKLE-EXTRA converge faster than other methods.
Finally, we create fixed "test set" with 10000 sample generated from S. Figure 7 shows the loss on the test set of SPARKLE-ED, SPARKLE-EXTRA, SLDBO, MDBO and single-level ED algorithm, demonstrating the superior performance of SPARKLE compared to other decentralized SBO algorithms.
D.4 Decentralized meta-learning
We consider a meta-learning problem as described in [18]. There are R tasks = R}. Each task T, has its own loss function L(r, ys E), where & represents stochastic sample drawn from the data distribution D.. denotes the task-specific parameters and x denotes the global parameters shared by all the tasks. In meta-learning problem, we aim find the parameters (x".3i. ... .... .V&) that minimizes the loss function across all R tasks, i.e.,
n M EEDD (x)
min [xx, VI. vR) 2.y1. MR
(102)
The problem (102) can be formulated as a decentralized SBO problem with heterogeneous data distributions across N nodes. For 1,2, ,N, let Dirain and D denote the training and validation datasets for the s-th task T. received by node respectively. We can then address the meta-learning problem by minimizing (1), with the upper- and lower-level loss functions defined as:
1
f((. =
Σ
E
[L E).
R
s=1
gx(x.v)
1
[I( vo. {)] R(v.)]
R
where denotes the cross-entropy loss and R(y.) C. ||va|| 2 a strongly convex regularization function.
In this experiment, we compare SPARKLE-ED with D-SOBA [29] and MAML [18] a decentralized communication setting over a 5-way 5-shot task across a network of N = nodes connected by Ring graph. The dataset used is minilmageNet [47], derived from ImageNet [42], which comprises 100 classes, each containing 600 images of size 84 x 84. We set R 2000 and partition these classes into 64 for training, 16 for validation, and 20 for testing. For the training and validation classes, the data is split according to a Dirichlet distribution with parameter a 0.1 [32]. We utilize a four- CNN with four convolution blocks, where each block sequentially consists of a 3 x convolution with 32 filters, batch normalizationm, ReL.U activation, and 2 2 max pooling. The batch size 32, and C, 0.001. The parameters of the last linear layer are designated as task-specific, while the other parameters are shared globally. For SPARKLE and D-SOBA, the step-sizes
69

---

3 y = 0.1 and a = 0.01. For MAML, the inner step-size is 0.1 and the outer step-size is 0.001, and the number of inner-loop steps repeat the experiment only once due to the time limitation. Figure 8 shows the average accuracy on the training dataset for all nodes, as well as the test accuracy of the three algorithms. We observe that SPARKLE-ED outperforms other algorithms, demonstrating the efficiency of SPARKLE in decentralized meta-learning problems.
For all algorithmss the task number is 32. And we only
70

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Refer to Abstract and Introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Refer to Section Conclusions.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
71

---

Justification:
Refer to Section Assumptions for our assumptions, and Appendix for detailed
proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
Refer to Appendix.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
72

---

Answer: [No]
Justification:
We may consider making data and code openly accessible when it is deemed
necessary.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (htips:/nnips.ccpubbiec quides/Codeeuumissiioooooll
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: wttpgggideeeCooettiiiiiiooooroie
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Refer to Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We show error bars in experiments where we consider them essential.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
73

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Refer to Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://ennis..ccuuuuiiehhhicccie
Answer:
[Yes]
Justification:Our research conforms, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of our work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
74

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: There is no such risk in the paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We comply with the licenses of existing assets used in the paper and provide necessary references.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paperswitheode. com/datasets wtw.sitthoooeeccmaaattttttttttt has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
75

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
76


Reviews:
[{"review_id": "ME0UEeBNmy", "reviewer": "Reviewer_E8rC", "summary": "This paper studies a primal-dual framework for decentralized bilevel optimization. It unifies several heterogeneous correction techniques (gradient tracking and EXTRA). It also provides a shared rate analysis that applies to all variants and avoids several assumptions like gradient boundedness. Several other insights include deploying ED/EXTRA at lower level is more beneficial than using GT across both upper/lower levels.", "questions": "See weakness.", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- This paper is overall well written with clear introduction of the bilevel optimization problem and shows the comparison of many different approaches and how they fit under the unified framework. An unified convergence rate is provided and discussed in detail when specializing in different settings. \n- Several interesting insight is provided, including the benefit of using EXTRA and ET compared to GT.", "weaknesses": "- The unification of several algorithms seems a superficial contribution. One just have to make a few unifying notations to unified these into the same framework. Probably the more non-trivial part is a unified analysis of the unified algorithm, but the paper doesn't seem to make the case that analyzing the unified algorithm is more difficult or more challenging than analyzing the individual algorithms. \n\n- The rate analysis in Theorem 1 contains many  numerical constants like 16/3, 14/3, which doesn't seem to be tight. Can the author comment all on the tightness of these constants. \n\nDue to the above reasons, I would say the paper's contribution is marginal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the invaluable comments. We have thoroughly addressed all questions. Should there be any additional concerns or inquiries, we are more than willing to provide further clarification.\n\n1. **Contribution of our work**\n\nWe appreciate the reviewer’s insightful feedback. However, we respectfully disagree that SPARKLE represents a superficial contribution. We clarify this point in Section **Novelty and contribution of our work** of **Global Rebuttal**.\n\n2. **It is non-trivial to establish a unified decentralized bilevel framework**\n\nThe reviewer commented that \"the unification of several algorithms seems a superficial contribution,\" which we respectfully disagree with. Existing single-level decentralized algorithms like EXTRA, ED, and GT have significantly different update rules and recursions (**Table 3**).  They cannot be unified by simply \"making a few unifying notations.\" To effectively unify these algorithms, our approach transforms each of them into a primal-dual formulation, extracts the principal structures behind their different recursions, and finally introduces unifying notations. \n\n3. **Challenges in our analysis**\n\nThis paper provides a novel analysis for a **unified** algorithmic framework, offering **improved convergence rates** and operating under **more relaxed assumptions** compared to existing literature. We have addressed significant challenges to achieve these results. \n\n- [**Unified analysis**] SPARKLE unifies ED, EXTRA, and many GT varints. It allows different update strategies and network topologies across different levels. This unified and general framework poses significant challenges for analysis: (1) The analyses of ED, EXTRA, and GT provided in literature are drastically different from one another, necessitating the identification of the fundamental mechanisms and core principles that can unify their analysis. (2) Since the SPARKLE framework is a unifying structure, the specific properties endowed by certain algorithms or network topologies cannot be  leveraged, forcing the analysis to rely solely on the basic properties, which significantly complicates the proof. (3) The SPARKLE framework is based on a primal-dual structure, whereas existing works which are primarily focus on DGD and GT, rely on the primal structure. This necessitates the development of new analytical techniques for decentralized primal-dual bilevel algorithms, further adding to the complexity of the analysis.\n\n\n- [**Improved rates**] \nAll SPARKLE variants achieve state-of-the-art convergence rates compared to existing algorithms. Specifically, SPARKLE is theoretically proven to have shorter transient stages and better robustness to network topologies, surpassing the results achievable in existing works.\n(1) Key steps in our proof involve transforming primal-dual forms (Section C.1.2, Appendix) and reformulating the SPARKLE update rules (Equations 33-35). We address consensus biases for each variable $s \\in \\{x, y, z\\}$ and their gradients in aggregated vectors. Analyzing the coupled consensus errors collectively allows us to obtain tighter bounds compared to related works.\n(2) While our bilevel algorithms can be reduced to single-level ones under certain trivial lower-level loss functions (Section C.4, Appendix), deriving single-level convergence rates directly from the bilevel analysis is challenging. It requires precise estimation of each update procedure. For more details, please refer to **Comment**.\n\n- [**More relaxed assumptions**] Our theoretical analysis achieves state-of-the-art convergence rates under more relaxed assumptions compared to existing algorithms.  Unlike some related works[2-6], we do not assume that the upper-level loss functions $f_i$ and lower-level loss functions $g_i$ are Lipschitz continous. We handle the bias of gradient estimation through additional steps, which only require high-order Lipschitz constants. Besides, we utilize heterogeneity correction techniques such as EXTRA, ED, and GT to remove the assumptions on bounded gradient dissimilarity. Please refer to **Comment** for more discussions.\n\n4. **Numerical Constants in Theorem 1.**\n\nThe focus of our paper is to provide a new unified decentralized bilevel framework that yields **brand new algorithms**, and achieves **state-of-the-art** asymptotic rate, gradient complexity, communication cost, and transient iteration complexity under **more relaxed assumptions** compared to existing methods. Establishing tight bounds for all constants is beyond the scope of our work. Notably, our convergence rate, while potentially not tight for every constant, outperforms the algorithms listed in Table 1 of our paper in terms of $K$, $n$, and $\\rho$.\n\nWe guess the reviewer is asking whether the influcne of the condition number on our convergence rate is tight or not. Here are some discussions:\n\n- **[Tight bound in the dominant term]** The term $\\kappa^5$ in the dominant term $\\kappa^5 \\sigma/\\sqrt{nK}$ represents state-of-the-art result among single-loop decentralized bilevel algorithms, which is consistent with those presented in [1]. \n\n- **[Probably untight bound in the higher-order terms]** The condition number associated with the higher-order terms, such as $\\kappa^{\\frac{16}{3}}$, represents our best effort to provide a tight upper bound. However, we acknowledge that these terms may not be optimal, as we have not conducted a comprehensive analysis of the lower bound. It is important to note that many existing works in this field do not provide a detailed analysis of the influence of $\\kappa$. Instead, the impact of $\\kappa$ is often treated as a trivial constant hidden in the Big-O notation [2-5 of Global Rebuttal Reference].  In comparison to these works, our research represents a significant step towards a better understanding of how the condition number influences the convergence rate.\n\n\n[1]  Optimal algorithms for stochastic bilevel optimization under relaxed smoothness conditions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pnm9klcUzN", "reviewer": "Reviewer_4NJf", "summary": "The paper introduces SPARKLE, a unified framework for decentralized stochastic bilevel optimization that addresses several limitations in existing approaches. SPARKLE incorporates various heterogeneity-correction techniques, including EXTRA, Exact Diffusion, and Gradient Tracking, and allows for different strategies in upper and lower-level problems. This flexibility enables SPARKLE to outperform previous methods, achieving state-of-the-art performance in terms of convergence rate, gradient complexity, communication cost, and transient iteration complexity. Notably, the framework demonstrates that EXTRA and Exact Diffusion are more suitable for decentralized bilevel optimization than Gradient Tracking. SPARKLE provides a unified convergence analysis applicable to all its variants without requiring restrictive assumptions like bounded gradients or data heterogeneity. Through numerical experiments, the paper demonstrates that SPARKLE achieves better performance compared to existing decentralized bilevel optimization algorithms.", "questions": "1.Over an undirected time-invariant graph with non-negative, symmetric and doubly stochastic mixing matrices, do the algorithms SPARKLE with GT, EXTRA, and ED have different ranges of application? If so, how do their application ranges differ in the context of decentralized bilevel optimization?\n\n2.Can the convergence rate of SPARKLE be improved beyond the results presented in Table 1, considering that the algorithm without momentum step in reference [27] achieves comparable convergence results in single-level scenario? In the absence of the momentum step, how would the convergence results of Algorithm 1 be affected?  If the primal-dual framework is removed, how would the convergence results of Algorithm 1 be affected? \n\n3.Could the paper provide a detailed comparison of the computational time and communication rounds required to achieve specific test accuracy or loss thresholds among the SPARKLE algorithms with different heterogeneity-correction techniques in experimental results?", "limitations": "1.By requiring strong convexity in the lower-level problem, SPARKLE excludes a wide range of practical scenarios where the lower-level optimization may be non-convex or only generally convex. This constraint substantially narrows the scope of decentralized bilevel optimization problems that SPARKLE can effectively address.\n\n2.The performance of SPARKLE is significantly impacted by the condition number of the lower-level problem. This sensitivity could limit its effectiveness in certain problem scenarios.\n\n3.The experiments seem to lack a comparison with single-level algorithms, which could provide valuable insights into the relative performance of SPARKLE in the distributed policy evaluation in reinforced learning. While the study demonstrates SPARKLE's superior performance against other decentralized stochastic bilevel optimization (DSBO) approaches like MDBO and SLDBO, it fails to benchmark against established single-level methods.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The SPARKLE framework's unified approach to decentralized bilevel optimization, incorporating multiple heterogeneity-correction techniques (EXTRA, Exact Diffusion, and Gradient Tracking), reveals an important insight: Gradient Tracking (GT) is not the optimal choice in some situations. \n\n2.The authors demonstrate its superiority of SPARKLE in several theoretical aspects of decentralized bilevel optimization, achieving state-of-the-art results across multiple performance metrics. The framework exhibits faster convergence rates, lower gradient complexity, reduced communication costs, and improved transient iteration complexity compared to existing methods.\n\n3.Extensive experimental results show SPARKLE consistently outperforming existing methods across various benchmark problems and real-world scenarios, particularly in terms of convergence rates. This empirical evidence strongly supports SPARKLE's practical utility and efficiency in solving complex optimization tasks in decentralized settings.", "weaknesses": "1.Although the paper proposes mixing strategies to handle heterogeneity, it does not provide a strong motivation or clear explanation for the necessity and benefits of these mixing strategies over choosing a single strategy, such as EXTRA or ED. This lack of clarity can make it difficult for practitioners to understand the rationale behind the proposed approach and its potential advantages.\n\n2.The primal-dual approach employed in SPARKLE incurs increased communication and storage overhead per communication round compared to non-primal-dual methods, due to the necessity of maintaining and updating dual variables in addition to primal variables across the decentralized network.\n\n3.The paper appears to lack an explicit analysis of consensus error, a crucial metric for evaluating solution agreement across nodes in decentralized networks. This omission represents a significant gap in the framework's evaluation, potentially limiting our understanding of SPARKLE's effectiveness in achieving consistent solutions in distributed optimization scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the invaluable comments. We have thoroughly addressed all questions. Should there be any additional concerns or inquiries, we are more than willing to provide further clarification.\n\nResponse to Weakness:\n\n1.**Motivation for the necessity and benefits of  mixing strategies over choosing a single strategy.**\n\n**[Motivation]** Bilevel optimization presents distinct challenges for the upper- and lower-level problems, with the upper-level often being non-convex and the lower-level strongly convex. This difference motivates us to explore whether using different update strategies for each level could provide advantages over the uniform gradient tracking (GT) strategy throughout all optimization levels used in existing approaches. To our knowledge, this question has not been addressed in prior literature.\n\n\n**[Benefits]** Whether mixing strategies would bring in benefits should be discussed in separate cases. \n\n- Before our work, existing works utilize DGD or GT in decentralized bilevel algorithms. Compared to these works, we find algorithms with mixing strategies such as SPARKLE-GT-ED converges **faster** than emplying GT alone, see Table 2 in the paper. \n\n- On the other hand, our results in Table 2 further shows that mixing strategies will achieve the **same** convergence rate as single strategy if ED or EXTRA is utilized. \n\nWith these results, we can conclude that mixing strategies may not necessarily bring in benefits compared to the best single strategy such as EXTRA and ED (which is proposed by us).  \n\n**[Contributions]** The main aim of this paper is to showcase the general SPARKLE framework rather than advocate for mixing strategies specifically. Our goal is to highlight the power of SPARKLE in analyzing mixing-strategy algorithms, which was not possible with previous methods. Our key findings are:\n\n- We have clarified the theoretical performance of mixing strategies, and that mixing strategies may not always offer advantages, which is still significant. Prior to our work, it was unclear whether mixing strategies would be beneficial. \n\n- We reveal that the performance of both single-strategy and mixing-strategy algorithms depends largely on the lower-level optimization (Theorem 1 and Corollary 4). \n\n\n2.**Extra overhead brought by the primal-dual approach.**\n\nWe agree that primal-dual methods introduce additional storage overhead due to the presence of dual variables. However, the communication costs per iteration may not necessarily increase. Dual variables of  EXTRA and ED can be eliminated from the recursion, see the recursions in Table 3 as well as Section B.2 (Appendix). It is observed in Table 3 that only the primal variables needs to be communicted for SPARKLE-EXTRA and SPARKLE-ED, make it as communication-efficient as primal approaches like D-SOBA. \n\n\n\n3.**Lacking an explicit analysis of consensus error.** \n\nWe provide a brief analysis of consensus errors in **Comment**. The asymtocic consensus error for SPARKLE variants using EXTRA, ED or GT is given by\n\n$\\frac{1}{K}\\sum_{k=0}^K\\mathbb{E}\\left[\\frac{\\|\\mathbf{x}^k-\\bar{\\mathbf{x}}^k\\|^2}{n}+\\frac{\\|\\mathbf{y}^k-\\bar{\\mathbf{y}}^k\\|^2}{n}\\right]\n=\\mathcal{O}\\left( \\frac{n}{K}\\left(\\frac{1}{1-\\rho_y}+\\frac{1}{1-\\rho_z}\\right)\\right),$\n\nwhere $\\rho_y,\\rho_z$ are spectrum gaps of relevant mixing matrices.\n\nRe Questions:\n\n**Q1: Application of EXTRA, ED and GT.** \n\nEXTRA, ED and GT can be used for the same applications. However, bilevel algorithms based on GT incurs more communication overhead (refer to the detailed update rules in Table 3) and suffers from longer transient iterations compared to the other two. For this reason, we will recommend using SPARKLE-EXTRA or SPARKLE-ED for decentralized bilevel optimization problems. \n\n\n**Q2: The influence of each algorithmic component.**\n\n**[Momentum cannot be removed]** The momentum step, or moving average, is essential for mitigating hyper-gradient estimation errors. These errors arise from sampling variance and estimation inaccuracies in the lower-level solution $y^\\star(\\bar{x}^k)$ and auxiliary-level solution $z_\\star^k$, which differ from single-level optimization. Properly selecting the moving average parameter $\\theta$ helps reduce these negative effects and ensures SPARKLE's convergence. Without the moving average (i.e., $\\theta=1$), convergence cannot be guaranteed. For more details, please refer to **Remark 6** (lines 829-836, Appendix) and our proof.\n\n\n**[Primal-dual framework cannot be removed]** The primal-dual framework is crucial for formulating heterogeneity correction methods and deriving specific algorithms, as detailed in Table 3. It enables the recovery of algorithms by defining the matrices $A, B, C$. This framework is vital for the basic transformation in Section C.1.2 and for establishing SPARKLE's convergence under Assumptions 1, 2, and 4. \n\n\n**Q3:Detailed comparison of the computational time and communication rounds.**\nWe thank the reviewer for the suggestion. In the data-hyperclean problem, we obtain the average of required gradient computation time to achieve specific test accuracy for SPARKLE with different communication strategy as well as D-SOBA, MDBO and MA-DSBO-GT as Figure 1 in the pdf document. It can be observed that SPARKLE needs less computation to achieve a given test accuracy than D-SOBA and MA-DSBO-GT. And SPARKLE with EXTRA in lover level communication outperforms than other strategies.\n\nResponse to Limitations:\n**1.**Please refer to Section 2 in **Global Rebuttal**.\n\n**2.Lacking  a comparison with single-level algorithms.** \n\nWe thank the reviewer for the suggestion. We have taken single-level EXTRA alglrithms into the comparsion of different algorims in the distributed policy evaluation. Table 1 shows the average loss of different algorithms of the last 500 iterations for 10 independent trials. And we can observe that SPARKLE has similar convergenve performance as single-level algorithms.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Fbl1cLXPVu", "reviewer": "Reviewer_AnxT", "summary": "This paper introduces SPARKLE, a unified single-loop primal-dual framework for decentralized stochastic bilevel optimization. SPARKLE is highly versatile, which can incorporate various heterogeneity-correction techniques and allows for different strategies to solve upper- and lower-level problems. The authors provide a unified convergence analysis for SPARKLE and its variants, showing state-of-the-art convergence rates compared to existing decentralized bilevel algorithms. Theoretical findings are supported by numerical experiments.", "questions": "1. The authors use the same decentralized mechanism for the lower-level and auxiliary variables. Can lower-level and auxiliary variables use different decentralized mechanisms?\n2. Could the authors provide more explanation on why SPARKLE can support utilizing different mixing matrices across levels? Are there any applications for such scenarios?\n3. The authors only show the upper level loss in the policy evaluation experiment. What about the test accuracy?", "limitations": "As the authors stated, SPARKLE supports only strongly-convex problems in the lower-level optimization, and the condition number of the lower-level problem significantly impacts the performance.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The proposed method SPARKLE in this paper is highly versatile, which can support various decentralized mechanisms and topologies across optimization levels. This paper has a comprehensive theoretical analysis for all SPARKLE variants, demonstrating that they achieve state-of-the-art convergence rates compared to existing decentralized bilevel algorithms. In addition, the authors show that the convergence performance of SPARKLE variants is comparable to their single-level counterparts, and that employing mixing strategies outperforms using GT alone.", "weaknesses": "1. In Line 303-304, the authors claim that all the SPARKLE-based algorithms generally achieve higher test accuracy than D-SOBA, while ED and EXTRA especially outperform GT. However, in Figure 1, particularly in the middle and right figures, the test accuracies are very similar, making such claims insufficiently supported. Additionally, such small differences might be due to randomness.\n2. The baseline algorithms used in different experiments are different. It is unclear why the authors did not use the same baselines. Furthermore, just one or two existing decentralized SBO algorithms in the hyper-cleaning or distributed policy evaluation experiments is not enough to evaluate the performance of SPARKLE. More state-of-the-art decentralized SBO algorithms need to be added.\n3. It would be important for this paper to evaluate more diverse and larger-scale tasks, including non-linear models such as neural networks (e.g., ResNet), applied to various bilevel problems (e.g., meta-learning).\n4. The authors did not provide the code to reproduce the experiments, raising concerns about reproducibility and making it difficult for other researchers to verify their results.\n\nMinor:\n1. In Assumption 1, it would be clearer to specify the variable with respect to which the function is Lipschitz continuous.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the invaluable comments. We have thoroughly addressed all questions. Should there be any additional concerns or inquiries, we are more than willing to provide further clarification.\n\nRe Weakness:\n\n1. Thanks for this concern. In fact, the second line of Table 5 in the manuscript (Page 62) also gives the average test accuracy and standard deviation of SPARKLE with different communication strategies when $p=0.3, \\theta=0.2$ on 10 independent trials, corresponding to the right subfig of Fig 1. The test accuracy of SPARKLE with ED and EXTRA is higher than GT for 1~2% with an acceptable standard deviation. Thus we can claim that for a suitable $\\theta$, there is a **REAL** benefit with ED and EXTRA and it is not from the stochastic.\n\n2. Thank you for the comment. We involved MA-DSBO and MDBO algorithms as another baselines in the hyper-cleaning problem which is shown in Table 1 in the manuscript. The stepsize $\\alpha,\\beta,\\gamma$ for MA-DSBO and MDBO and the moving-average term of MA-DSBO are the same as that of SPARKLE and D-SOBA. The inner and outer iteration of MA-DSBO is set to 5 and the number of Hessian-inverse\nestimation iterations of MDBO is set to 5. The average test accuracy is shown in Figure 1, which shows that SPARKLE outperforms than MA-DSBO and MDBO. And the other algorithms in Table 1 is not involved into the comparsion as DSBO, Gossip DSBO and SLAM suffer from a worse transient complexity and has beaten by different decentralized SBO algorithms, and LoPA requires a personal lower-level problem, which is not match the hyper-cleaning problem.\n\n3. Thanks for this comment. Here we consider a meta-learning problem in decentralized scenario with $N=8$ nodes and Adjust-ring grouph. We consider a 5-way 5-shot task on miniImageNet dataset and compared SPARKLE with D-SOBA and MAML with decentralized communication. For D-SOBA and SPARKLE, the step-size $\\beta,\\gamma=0.1$ and $\\alpha=0.001$. For MAML, the inner step-size is 0.1 and the outer stepsize is 0.001, and the number of inner-loop steps as 3. For all algorithms, the task number is set to 32. And we only repeat the experiment only once due to the time limitation. The accuracy in training and test dataset for the three algorithms is shown in Figure 4 in the pdf document. It can be observe that SPARKLE out performs than the other two algorithms.\n\n4. Thanks for this comment. As SPARKLE is based on stochastic gradient decend, we think the experiments in the manuscript is not different to achieve. Thus we did not offer the code of SPARKLE. However, we will consider release the code soon. \n\n\n\n\n\n**Minor** :We thank the reviewer for the suggestion. The Lipschitz continuity is for both $x$ and $y$.\n\nRe Questions:\n\n1. SPARKLE permits the use of different decentralized mechanisms for lower-level and auxiliary variables. As noted in Corollary 1, we have $\\delta_y = \\delta_z$ and $\\hat{\\delta_y} = \\hat{\\delta_z}$  when $\\mathbf{W}_y = \\mathbf{W}_z$ ( See more details in Section **3.4. Different strategies across optimization levels** and Lemma 18).  Given that the influence with respect to $y$ and $z$ is identical  ($n^3,n$ terms), we employ the same decentralized mechanisms for both variables for simplicity. However, different decentralized mechanisms can be used for $y$ and $z$—for instance, applying EXTRA to $y$ and GT to $z$. The theoretical transient iteration complexities for these configurations can be readily computed using Lemma 18. In SPARKLE, the primary differences lie between the variables $x,y$  and $x,z$, rather than between  $y,z$. Therefore, we focus on scenarios where mixing strategies are applied to $x,y$, while maintaining a uniform strategy for $y,z$.\n\n2. Each mixing matrix $\\mathbf{W}$ represents a communication graph or topology. \nFormally, we can directly use different mixing matrices $\\mathbf{W}_x,\\mathbf{W}_y,\\mathbf{W}_z$, which corresponds to different communication topologies. Our key finding regarding the use of different mixing matrices is that some SPARKLE variants, such as SPARKLE-ED, can maintain the transient iteration complexity (up to a constant factor) even when the communication topology for the upper-level variable $x$ is sparser within certain ranges. In other words, by fixing the communication graphs for $y,z$ and using the same communication graphs for both $y,z$, while applying a sparser communication graph for $x$, the transient iteration complexities will remain the same as if the same communication graph were applied to $x$ along with $y,z$. This implies that a sparser communication graph for $x$ can reduce communication costs while preserving the same transient iteration complexity. Please refer to more detailed discussions in Section **3.5. Different topologies across optimization levels** and Section **C.2.2 Theoretical gap between upper-level and lower-level, Appendix**. We provide upper bounds for the relative sparsity of the topology for $x$ compared to $y,z$ to ensure that the transient iteration complexity remains unchanged.\n\n\n\n\nThere are many practical scenarios where using different communication topologies for $x,y,z$ is beneficial. For instance, when the dimension of $x$ is larger than that of $y$, or when the computational overhead for computing the gradient of the upper-level function $f$ is higher than that of the lower-level function $g$, employing a relatively sparser communication topology for $x$ compared to $y$ can reduce communication time and costs.\n\n\n\n3. We thank the reviewer for the valuable comment. As the policy evaluation experiment is a reinforce learning problem with a synthetic dataset, it is hard to provide a \"test accuracy\". To verify the test performance of SPARKLE, we made a fixed \"test set\" with 10000 sample. The generation of test sample is same to training sample. And the averange test loss of different algorithms is shown in Figure 3, which illustrate the better test performance of SPARKLE.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2uBQWmczBy", "reviewer": "Reviewer_ehMq", "summary": "This paper proposes SPARKLE, a single-loop primal-dual framework for solving bilevel optimization in the decentralized setting. Specifically, multiple devices collaborate to solve bilevel optimization problems and exchange information via communications over a network. From a theoretical angle, the authors prove that SPARKLE algorithm achieves better transient iteration complexity and handle gradient dissimilarity more effectively under weaker assumptions than previous works. From an empirical angle, the authors conduct experiments to show that their algorithm has better performance than existing results.", "questions": "I wonder if the authors have any responses to the weaknesses I listed above.", "limitations": "1. Novelty. One major concern is the limited novelty of this paper, as mentioned in the weakness section.\n\n2. There are also some limitations mentioned by the authors. For example the lower-level problem is strongly convex, and it is unclear if the condition number is optimal in the upper bounds. I agree that these are the common limitations of existing decentralized bilevel optimization works, and are interesting to explore.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The authors provide a single-loop primal-dual framework for solving decentralized bilevel optimization. The technical contributions and the claims are sound, and the experiments can support the claims from an empirical perspective.\n\n2. Moreover, the framework unfies many state-of-the-art strategies used in distributed optimization, like ATC, GT, EXTRA, momentum, etc, and obtains best results as compared to existing works.", "weaknesses": "1. Novelty. The novelty of this paper seems a little limited. There are already many existing works proposing various algorithms for solving decentralized bilevel optimization problems, as listed in Table 1 of this paper. I am not sure if the improvement on the transient time and communication complexity over previous works is significant enough to make this work pass the bar of acceptance. The authors may want to clarify this a bit.\n\n2. Presentation. The authors also mention that there are mixed strategies in this paper like ATC, GT, EXTRA, auxiliary-level updates, momentum update, and so on. The organization of the techniques might not be easy for a layman to follow. It would be better if the authors can highlight the reasons and benefits of using these techniques in a table.\n\n3. Experiments. Many important baselines are missing in the figures of Section 4. Some figures have standard deviation of 10 trials while some do not.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the invaluable comments. We have thoroughly addressed all questions. Should there be any additional concerns or inquiries, we are more than willing to provide further clarification.\n\nRe Weakness:\n\n**1. Novelty.**\n\nWe respectfully disagree that our work has limited contributions. SPARKLE is a unified framework that **yields brand new algorithms**, and achieves **state-of-the-art** convergence rates under **more relaxed assumptions** compared to existing methods. Please refer to the global response for the clarification of the contribution.\n\nAdditional clarifications on the reviewers' specific concerns are provided below.\n\n**[Transient iteration complexity is critical for decentralized optimization]** Transient iteration complexity is critical for both theoretical and empirical reasons.\n\n- From a theoretical standpoint, transient iteration complexity is key for assessing decentralized algorithms' performance compared to centralized methods and distinguishing between different decentralized algorithms. Without analyzing transient iteration complexity, many decentralized bilevel algorithms would seem to have similar performance based solely on asymptotic convergence rates, potentially aligning with centralized approaches. However, this overlooks the discrepancies evident in practical performance. By examining transient iteration complexity, we can identify more effective algorithms with shorter transient iterations, aligning theoretical insights with empirical results.\n\n- From an empirical perspective, decentralized bilevel algorithms can only achieve their asymptotic convergence rate after a sufficiently large number of iterations. However, practical scenarios often allow only a limited number of algorithmic iterations due to constraints on time or computational resources. Consequently, these algorithms typically exhibit a decentralization-incurred slowdown in convergence, as illustrated in Fig. 1 from reference [1]. Evidently, the transient iteration complexity provides a more practical representation of decentralized algorithms' performance in real-world applications.\n\n**[Transient iteration complexity reflects the impact of the network topology]** Decentralized optimization relies on communication networks, unlike centralized optimization with fully-connected networks. While the asymptotic  rate remains unaffected, the transient iterations are influenced by network topology. Sparsely-connected network has $\\rho \\to 1$, which hence enlarges the transient iterations. By comparing the transient iteration complexity between SPARKLE and existing baselines, we find that SPARKLE is more robust to sparse topology. \n\n**[Communication complexity is critical for decentralized optimization]**  In distributed systems, communication often takes more time than computation, especially with high-dimensional data. SPARKLE improves on existing methods by allowing different correction techniques and communication topologies for the upper and lower levels. Specifically, some SPARKLE variants, like SPARKLE-ED, can use sparser communication for the upper-level variable x without affecting transient iteration complexity. This reduces communication costs while maintaining efficiency, making SPARKLE more time-efficient compared to other algorithms.\n\n\n\n\n**[More relaxed assumptions]** SPARKLE achieves the best transient time under the most relaxed assumptions (Table 1). We emphasize that the bounded gradient (BG), Lipschitz continuity (LC), and bounded gradient dissimilarity (BGD) assumptions for the upper-level function $f$ and the lower level function $g$ in other works may not hold in typical applications. For example, we consider $f(x,y)=\\frac{1}{n}\\sum_{i=1}^n f_i(x,y)$ with $f_i(x,y):=\\frac{1}{2}x^\\top A_i x$, where $A_i$ are different positive semi-definite matrices and $x\\in \\mathbb{R}^p$. The gradients (w.r.t. $x$) $A_i x$, and gradient dissimilarity $(A_i-\\frac{1}{n}\\sum_{j=1}^n A_j)x$ are unbounded for $x\\in\\mathbb{R}^p$.  This highlights the significance of our theoretical improvement in transient time.\n\n**[Sharp analysis]**   This is the first result showing that bilevel optimization essentially subsumes the convergence of single-level optimization. \n\n\n\n\n**2.Presentation.**\nWe thank the reviewer for the comment. Here is a brief introduction of the benefits. We will soon provide a detailed table.\n\nGT/ED/EXTRA: correct data heterogeneity, improve transient stage\n\nmomentum:   guarantee convergence, enable relaxed assumptions\n\nmixed network topology:   save communication cost\n\n**3.Experiments**\n\nThanks for the comment. Here are our responses.\n\n**Baselines**: We involved MA-DSBO and MDBO algorithms as another baselines in the hyper-cleaning problem which is shown in Table 1 in the manuscript. The stepsize $\\alpha,\\beta,\\gamma$ for MA-DSBO and MDBO and the moving-average term of MA-DSBO are the same as that of SPARKLE and D-SOBA. The inner and outer iteration of MA-DSBO is set to 5 and the number of Hessian-inverse estimation iterations of MDBO is set to 5. The average test accuracy is shown in Figure 1 (supplementary PDF), which shows that SPARKLE outperforms than MA-DSBO and MDBO. And the other algorithms in Table 1 is not involved into the comparsion as DSBO, Gossip DSBO and SLAM suffer from a worse transient complexity and has beaten by different decentralized SBO algorithms, and LoPA requires a personal lower-level problem, which is not match the hyper-cleaning problem.\n\n**Standard deviation**: Thanks for the comment. The standard deviation of the last 40 iterations in the hyper-cleaning with $p=0.3$ is shown in Table 5 in the manuscript. And we will added the standard deviation in the other scenarios soon. Table 1 shows the average loss of different algorithms of the last 500 iterations for 10 independent trials in the policy evaluation in the distributed policy evaluation of reinforced learning.\n\n\n[1] Exponential Graph is Provably Efficient for Decentralized Deep Training", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely appreciate the detailed feedback provided by all reviewers. Here we present our response to the common concerns raised by multiple reviewers and results of newly added experiments.

 **1.Novelty and contribution of our work.**

SPARKLE yields **brand new algorithms**, and achieves **state-of-the-art rates** under **more relaxed assumptions** compared to existing methods. In particular, SPARKLE implies the following novel results. 

- [**SPARKLE yields new algorithms utilizing EXTRA and ED**] Before SPARKLE, existing bilevel algorithms primarily employ decentralized gradient descent (DGD) and gradient tracking (GT) in algorithm development. SPARKLE expands this paradigm by incorporating EXTRA and ED methods to address data heterogeneity, resulting in novel decentralized bilevel algorithms—SPARKLE-EXTRA and SPARKLE-ED—**which were not previously considered in the existing literature**. Furthermore, theoretical analysis demonstrates that SPARKLE-EXTRA and SPARKLE-ED exhibit superior convergence complexities compared to existing algorithms.

- [**SPARKLE yields new algorithms with different update strategies across optimization levels**]  SPARKLE is the first algorithm framework that introduces mix strategies for solving upper-level, lower-level, and auxiliary-level problems. For example, it allows the use of GT to update the lower-level variable $y$, while ED is used for the upper-level variable $x$ and the auxiliary-level variable $z$. This approach yields novel decentralized bilevel algorithms such as SPARKLE-ED-GT and SPARKLE-EXTRA-GT. In contrast, existing literature on decentralized bilevel optimization primarily utilizes **the same strategy** across the upper and lower optimization levels.

- [**SPARKLE yields new algorithms with different network topologes across optimization levels**] SPARKLE is the first algorithm framework that propose using different network topologies and mixing matrices for solving upper-level, lower-level, and auxiliary-level problems. Given that the dimensions of variables can vary significantly across different levels, exploring how diverse mixing matrices can reduce communication costs represents an essential novel contribution. By using different weight matrices, all SPARKLE variants are more efficient in communication costs, see Table 1 in our paper.  In contrast, existing literature on decentralized bilevel optimization primarily utilizes **the same mixing matrix** across the upper and lower optimization levels.

- [**State-of-the-art convergence rates and complexities**] As demonstrated in Table 1 of our paper, all SPARKLE-derived algorithms achieve state-of-the-art convergence rates and complexities compared to existing baselines. Specifically, all SPARKLE variants exhibit: (1) Lower asymptotic computational and communication costs; (2) Shorter transient stages; (3) Most importantly, greater robustness to network topologies. For instance, it is known that the ring topology has $1 - \rho$ on the order of ${1}/{n^2}$. When utilizing this topology, the transient stages of MDBO, Gossip DSBO, and D-SOBA are on the order of $n^{19}$, $n^{11}$, and $n^{11}$, respectively. In contrast, SPARKLE variants have a transient stage of $n^7$, which is significantly shorter than existing baselines.

- [**More relaxed assumptions**] As shown in Table 1 of our paper, the convergence of existing algorithms relies on **stringent assumptions**, including bounded gradients, bounded gradient dissimilarity, or functional Lipschitz continuity. In contrast, SPARKLE does not depend on any of these assumptions.

In summary, we hope to emphasize that our main contribution extends beyond demonstrating how different approaches fit under a unified framework. Our work also: (1) Derives novel algorithms; (2) Provides improved analysis and convergence rates; (3) Offers fresh insights into decentralized bilevel optimization. 

**2. Limitation: Strongly convex lower-level function and impact of the condition number**

While we have acknowledged the following limitations in the paper, we can provide additional discussions: 

- **[Lower-level strong convexity]** We agree that our work does not address the more general case where the lower-level loss function is merely convex. **This limitation is common in most existing research**, as there are currently no decentralized bilevel algorithms specifically designed for cases with generally convex lower-level loss functions. In fact, such problems are significantly challenging as the lower-level problems might not have unique solutions, and the final objective function could be non-differentiable [1]. Addressing these issues requires fundamentally different approaches, which are beyond the scope of this work. 

- **[Condition number]** We agree that the condition number will impede the convergence significantly, **which is a common limitation in most existing research**. However, it is important to note that most related works treat the condition number as a constant and obscure its effect using Big-O notation [2-5]. Our analysis offers a more detailed understanding of how $\kappa$ affects the convergence rates. To mitigate the influence of the condition number, Nesterov acceleration can be used to accelerate the solving of the lower-level optimization problem. We will leave it as the future work. 

**3. Experiments.**

The results are shown in the PDF document in this global rebuttal. Please refer to more details in individual rebuttals.

[1]On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis. 

[2]Decentralized stochastic bilevel optimization with improved per-iteration complexity.

[3]A stochastic linearized augmented lagrangian method for decentralized bilevel optimization. 

[4]Decentralized gossip-based stochastic bilevel optimization over communication networks.

[5]Decentralized bilevel optimization over graphs: Loopless algorithmic update and transient iteration complexity.

Meta-review: This paper studies the decentralized bilevel optimization problem and focuses on mitigating the influence of data heterogeneity. It proposes SPARKLE, a unified single-loop primal-dual algorithm framework that offers the flexibility to incorporate various heterogeneity-correction strategies into the algorithm, and allows for different strategies to solve the upper- and lower-level problems. A unified convergence analysis is established. Overall, this paper investigates an important problem and the technical contributions are solid. Therefore, I recommend to accept.
Decision: Accept (poster)