DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity
Authors: Zhen Qin
Zhuqing Liu
Songtao Lu
Yingbin Liang
Jia Liu
Venue: ICLR 2025 Poster (2025)
Keywords: Decentralized optimization
Bilevel optimization
Convex optimization
Heterogeneous data distributions
Multi agent learning
Primary area: optimization

Abstract: Decentralized bilevel optimization (DBO) provides a powerful framework for multi-agent systems to solve local bilevel tasks in a decentralized fashion without the need for a central server. 
However, most existing DBO methods rely on lower-level strong convexity (LLSC) to guarantee unique solutions and a well-defined hypergradient for stationarity measure, hindering their applicability in many practical scenarios not satisfying LLSC. 
To overcome this limitation, we introduce a new single-loop DBO algorithm called diminishing quadratically-regularized bilevel decentralized optimization (DUET), which eliminates the need for LLSC by introducing a diminishing quadratic regularization to the lower-level (LL) objective. 
We show that DUET achieves an iteration complexity of  $O(1/T^{1-5p-\frac{11}{4}\tau})$ for approximate KKT-stationary point convergence under relaxed assumptions, where $p$ and $\tau $ are control parameters for LL learning rate and averaging, respectively.
In addition, our DUET algorithm incorporates gradient tracking to address data heterogeneity, a key challenge in DBO settings. 
To the best of our knowledge, this is the first work to tackle DBO without LLSC under decentralized settings with data heterogeneity.
Numerical experiments validate the theoretical findings and demonstrate the practical effectiveness of our proposed algorithms.

Published as a conference paper at ICLR 2025
DUET: DECENTRALIZED BILEVEL OPTIMIZATION WITHOUT LOWER-LEVEL STRONG CONVEXITY
Zhen Qin', Zhuqing Liu², Songtao Lu Yinghin Liang", Jia Liu
i Department of Electrical and Computer Engineering, The Ohio State University
$ Deppartment of Computer Science and Engineering, University of North Texas o Department of Computer Science and Engineering, The Chinese University of Hong Kong
ABSTRACT
Decentralized bilevel optimization (DBO) provides powerful framework for multi-agent systems to solve local bilevel tasks in a decentralized fashion without the need for central server. However, most existing DBO methods rely on lower-level strong convexity (LLSC) to guarantee unique solutions and a well- defined hypergradient for stationarity measure, hindering their applicability in many practical scenarios not satisfying LLSC. To overcome this limitation, we introduce a new single-loop DBO algorithm called diminishing bilevel decentralized optimization (DUET), which eliminates the need for LLSC by introducing a diminishing quadratic regularization to the lower-level (LL) objective.
seaadraticallyrrgulariii
We show that DUET achieves an iteration complexity of O(1/T>-6p-#* for approximate KKT-stationary point convergence under relaxed assumptions, where and T are control parameters for LL learning rate and averaging, respectively. In addition, our DUET algorithm incorporates gradient tracking to address data heterogeneity, key challenge in DBO settings. To the best of our knowledge, this is the first work to tackle DBO without L.SSC under decentralized settings with data heterogeneity. Numerical experiments validate the theoretical findings and demonstrate the practical effectiveness of our proposed algorithms.
INTRODUCTION
In recent years, Decentralized Bilevel Optimization (DBO) over networks has gained significant attention. Consider a DBO problem, where the agents form peer-to-peer network represented by an undirected connected graph g (N. L). Here A and L are the sets of agents (nodes) and edges, respectively, with [W| = m. Each agent i can share information with neighboring agents Ni (i' e : (i, E C} and has access to a local dataset of size n. The goal is for all agents to collaboratively solve the following decentralized bilevel optimization problem:
m
min X.ERPI y.ES(x:) m
Σ fe (x) 1=1
s.t. S(x;) = arg min
Vi; x; = =x,, if ((,T)
y,EBP2
where x; E RPI and y, E RP= are parameters to be trained for the UL and LL subproblems at agent i, respectively. In this paper, we assume that the UL objective T 1 >m fi (x,, y.) ) non-convex and the LL objectives g, (x; y:), Vi, are convex but not strongly convex (i.e., not LLSC). respectively. In the absence of LLSC, the LL solution could be a set-valued map S(x,) (i.e., non-unique optimal solutions to the I.I. problem). The consensus constraints x; x in ensure that the local copies neighboring agents i and are equal to each other, hence "consensus" among the agents. The L.L. variable y, is influenced by the UL variable x, chosen from the feasible set X (i.c., x, E X).
DBO provides an effective framework for solving multi-agent, nested optimization problems, where each agent solves a local bilevel task while coordinating with others in a network without relying on a central server. This approach proves particularly beneficial in scenarios such as multi-agent
TThis work completed while S. La senior research scientist at IBM Research in the U.S.

---

Published as a conference paper at ICLR 2025
pretraining finetuningg (Rajeswaran al. 2019 Poon & Peyré 2021 Liu & Liu 2021 Hashemi et al. 2024) for Large Language Models (LLMs), which faces significant challenges in private finetuning data environments, thereby making collaboration critical for successful iie-tuning. This framework is also useful in multi-agent meta learning (Rajeswaran et al. 2019 Liu & Liu (021). and reinforcement learning (Zhang al. 2020 Lu et al. 2022), where decentral liaaton reduces communication costs and enhances privacy. DBO problems share the same structure as their centralized counterpart and involve an upper-level (UL) objective function dependent on the optimal parameter values of lower-level (LL) objective. Even in the centralized case, bilevel optimization is inherently challenging without lower-level strong convexity (LLSC). Several algorithmic approaches have been proposed for centralized bilevel optimization without LLSC. These include using the sequential averaging method (SAM) (Sabach & Shtern 2017 Liu et al. 2023a Li et al. 2020), penalty methods (Lu & Mei 2023). and employing the value function approach Yao et al. 2024).
Despite the progress in LLSC-less centralized bilevel optimization, designing efficient algorithms for LLSC-less DBO turns out to be from& simple extension of the centralized counterpart. Instead, LLSC-less DBO is a new area with a collection of new challenging and important problems, which warrant drastically different algorithmic designs. To date, LLSC-less DBO remains under-explored and this gap in the literature is largely due to the fact that most of the algorithmic ideas for centralized bilevel optimization cannol be directly applied to DBO. The first key reason is that, instead of solving a single L.I problem, DBO involves multiple I.I. tasks across different agents, making centralized techniques inapplicable. Another major challenge is the data heterogeneity across agents, where each agent works with its own distinct dataset. This further complicates coordination among agents, making it difficult for centralized bilevel optimization approaches to be effective in DBO.
To solve DBO problems without LLSC, a natural starting point is to leverage the decentralized network-consensus approach (Nedic & Ozdaglar 2209),, where agents collaboratively solve a global learning task to reach a consensus. However, two fundamental challenges arise when applying
network-consensus methods to DBO: (1) Most existing DBO methods (see, e.g., (Chen et al. 2022
2023: Lu et al., 2002; Niu et al.) 2023 Liu et al. 2022b Qiu et al. 2023 Liu et al. 2023b). heavily
rely on the assumption of LLSC to guarantee a well-defined Hessian inverse in the upper-level (UL)
hypergradient evaluation and the uniqueness of the LL solution, both of which may break down in
the absence of LLSC. Excerbating the situation is the fact that the norm of the UL hypergradient is the most widely used stationarity measure for bilevel optimization. Without well-defined UL hypergradient in the absence of LLSC, it is not even clear what should be used as a stationarity measure in DBO; (2) Without LLSC, the lack of uniqueness in LL solutions complicates coordination in decentralized network-consente central server. Aggregating information from agents becomes more difficult, as the LL solution may shift randomly, resulting in oscillations and poor convergence in DBO.
approaches, where agents must exchange their updates without a
These challenges motivate to design new efficient network-consenssu based algorithms for DBO without LLSC. Toward this end, we propose a novel approach called diminishing quadratically- regularized bilevel decentralized optimization (DUET). To our knowledge, none of the existing works has considered solving LLSC-less DBO problems, particularly in decentralized environments with data heterogeneity. Our major contributions are summarized as follows:
We propose DUET, single-loop algorithm that integrates gradient tracking and consensus updates to avoid the computational complexity of conventional double-loop structure in bilevel optimization, while ensuring convergence in decentralized settings with data heterogeneity. To our knowledge, this is the first algorithm with provable convergence for DBO without LLSSC
New Single-Loop Algorithm for LLSC-less DBO:
New Stationarity Measure for LLSC-less DBO Convergence: We propose to use the approxi- mate KKT stationarity as the convergence measure of DBO solution quality our algorithm and provide a detailed convergence rate analysis based on this new measure. We establish state-of of art finite-time convergence rates of D(1/T1-39-44 44) and -11/T1-6p-4' #*) corresponding to the dual variables being bounded and unbounded, respectively. Here, t and p control the LL learn- ing rate and averaging, respectively. Moreover, we note that this new approximate KKT-based stationarity measure is general for all DBO problems, which could be of independent theoretical interests. Most notably, the convergence of our DUET algorithms is proved by establishing new descent lemma for the Lyapunov function (cf. Lemma D]. which resolves the difficulty resulting from the inapplicability of using the standard descent lemma in the absence of L.SSC.
2

---

Published as a conference paper at ICLR 2025
New Augmented LL Objective: We propose new augmented LL objective function that allows us to relax several restrictive assumptions made in existing works on LLSC-less bilevel optimization. Notably, our approach does not require strong convexity for the UL objective at each agent, Lipschitz continuity of second-order derivatives, or a bounded dataset.
Handling Decentralization with Data Heterogeneity: Without gradient heterogeneity assump- tions, our algorithm overcomes the challenges of consensus errors DBO with data heterogeneity, ensuring agents can synchronize their updates effectively without relying on LLSC.
2 RELATED WORK
In this section, we provide an overview of two closely related lines of works: 1) DBO and 2) centralized bilevel optimization without LLSC, thus putting our work into comparative perspectives.
1) Decentralized Bilevel Optimization (DBO): Numerous studies have focused on solving decen- tralized bilevel optimization problems on graphs with LLSC.
One line of work focuses on achieving consensus only for the UL variables, where algorithms are often designed with the hypergradient norm as a stationarity measure. [Lu et al. (2022b) introduced local full-gradient-basee algorithm with variance reduction and gradient tracking to achieve (n/e) sample complexity and (l1/e) communication complexity, where is the size of the dataset at each agent. Furthermore, momentum information is leveraged (Gao et al.) 2023 Qiu et al. 2023) to enable single-loop algorithmic architecture by slightly trading off convergence rate performance. To address data heterogeneity, NNu et al.] (2023) introduced a single-loop algorithm for mnnconvex-strongly convex bilevel optimization that handles heterogeneity without requiring bounded hypergradients. In collaborative learning, Zhang et al. (2023) proposed COBO, an SGD-based algorithm that scales with clients and outperforms federated learning baselines in heterogeneous settings. Another line of works enforce consensus on the LL variables refer to Appendix
Despite these advancements, all aforementioned DBO methods assume LLSC. In contrast, our work departs from this assumption, addressing decentralized bilevel optimization without LLSC under non-i.i.d. data, thus filling critical gap the literature.
2) Centralized Bilevel Optimization without LLSC:
In recent years, centralized bilevel optimization without LLSC has also received increasing attention. For example, Chen al. (2024a) employed an c- stationary point for the hyper-objective as convergence metric to guantify algorithmic and proposed a first-order bilevel algorithm with a convergence rate of (lx*² / where is Lipschitz constant and k is the condition number, though it required PL conditions for LL objectives. Liu et al. (2022a)
presents a first-order algorithm for non-convex bilevel optimization that avoids Hcssian computations, ensures practical efficiency with non-asymptotic convergence guarantees, and introduces modified KKT condition with a stationarity measure to address bilevel problem challenges. [u & Mei (2023)
reformulated the LL convex bilevel problem constrained min-max problem and used the classic penalty method, achieving convergence rate of O(1/e*) to find e-KKT points. [Jiang et al. (2023) tackled "simple bilevel" problem and proposed a double-loop algorithm utilizing the condition gradient method to approximate nonlinear LL convex functions with linear inequality constraints, achieving a convergence rate of O(1/²).. The stochastic variant in Cao et al. (2023) extends this method to both stochastic and finite-sum settings. with rates matching the standard conditional gradient method. More recently. Yao et al.) (2024) introduced a calue-funccion-bare based proximal Lagrangian approach for constrained LL convex bilevel problems, achieving convergence rate of ( (22))/2, where controls the penalty parameter decay. Additional related works are discussed in Appendix[B
The most related work on centralized LLSC-less bilevel optimization is in Liu et al. (203a), which reformulated the I.L. convex bilevel problem as a constrained problem using first-order stationarity condition. By employing the KKT condition as the stationarity measure, they proposed single-loop method that averages the UL and LL objectives, achieving a convergence rate of O (1/T113p-33) where p and 7 control the decreasing LL learning rate and the averaging parameter. While both our work and Liu et al. (202aa) reformulate the bilevel problem as constrained optimization and use aggregation function for solving LL problem, work differs from Liu et al. (2023a) in the following key aspects: Liu et al.] (2023a) required strong convexity of the UL objectives, which limits their approach's applicability in real-world scenarios where UL. objectives often nonconvex. In contrast,
3

---

Published as a conference paper at ICLR 2025
Algorithm
Setting
Lower Level
Upper Level
Het. Data
FOPM (Lu Mei
2023)
Centralized
Convex
Nonconvex
NA
CG-BiO Ciang et all
(223))
Centralized
Convex
Nonconvex
NA
F*BA (Chen et al. 2024a)
Centralized
Nonconvex, PL
Nonconvex
NA
SBCGF (Cao et al. 2023)
Centralized
Convex
Nonconvex
NA
LV-HBA Yao al.
2024]
Centralized
Convex
Nonconvex
NA
sI-BAMM Liu al. 2025a
Centralized
Convex
Strongly Convex
NA
INTERACT Liu al. 2022b)
Decentralized
Strongly Convex
Nonconvex
i.i.d
DIAMOND
Qiu et al. (023))
Decentralized
Strongly Convex
Nonconvex
L.d
Prometheus
Liu al. 202.5)
Decentralized
Strongly Convex
Nonconvex
i.id
SLDBO Dong et al.
2024)
Decentralized
Strongly Convex
Nonconvex
non-i.i.
LoPA NNu et al.
2023)
Decentralized
Strongly Convex
Nonconvex
non-i.id
DUET (Ours)
Decentralized
Convex
Nonconvex
non-i.i.
Table 1: Summary of bilevel optimization algorithms.
our method can be applied to non-convex UL objective by employing different aggregation function that sequentially averages the LL objective with a diminishing quadratic regularizer. 2) Although both approaches employ the KKT condition the stationarity measure, measure applies to the decentralized setting by accounting for consensus errors and aggregating the stationarity measure across subproblems from agents with non-i.i.d. data distributions. In contrast, the KKT-based stationarity measure Liu et al. (023a) cannot handle data hetergeneity.
In summary, while the aforementioned existing works addressed centralized bilevel optimization without LLSC, they cannot be generalized to address the decentralized setting with heterogeneous data challenges in a straightforward fashion. In contrast, our work tackles LLSC-less DBO and relaxes several assumptions typically made in the bilevel optimization literature. For easy reference, we summarize the most relevant bilevel optimization algorithms in Table !
3 THE DIMINISHING AAADRAATICALLY-REGLLAAARI OPTIMIZATION ALGORITHM (DUET)
BILEVEL
Problem Reformulation for a New Stationarity Convergence Metrie: In the LLSC DBO literature, the uniqueness of the LL solution (x:) ensures that the hypergradient norm of each agent's UL objective &' (xx) fx y? (x:))
)) is well-defined. Consequently, the hypergradient norm 21 _i
of the overall UL objective + (x:)
im1 T (x,) is also well-defined. This norm has been widely used as a measure for stationarity in previous works (e.g.. Ghadimi & Wang 2018); Liu al. 2022b 2023b); Dong al. (2024) : Lu & Mei (2023)) However, in the absence of LLSC, the and thus not invertible. In decentralized settings, this problem is further exacerbated by the inconsistent updates across agents, which leads to the conventional
Hessian matrix of the LL problem is nor
stationarity measure being ill-defined. This motivates us to develop a new stationarity measure that handles both the absence of LLSSC and the consensus errors among agents at the same time.
Toward this end, inspired by Wolfe-duality, we first reformulate the LLSC-less DBO problem into an equivalent constrained optimization problem. Instead of directly solving for yī (x:), we replace the LL problem by introducing the LL-stationary condition (i.e., Vyg((x y) 0) as constraints:
min X.ERPI ERPP
Σ fo (x),
S.L. (y 0, Vi;
x; X if (i, (3)
The reformulation in Problem is equivalent to the original Problem ① because the I.L-stationarity both necessary and sufficient for the IL--ommiallity when the L.I. problem (x,, y:) is convex in y; for any fixed x,, which is satisfied in our problem setting. Our key rationale behind converting the original bilevel optimization problem in I into an equivalent conventional constrained optimization problem in (3) is to facilitate the of the KKT conditions, for which the KKT stationary condition can naturally serve as a new stationarity measure, hence resolving the conundrum of lacking a well-defined hypergradient norm as the stationarity measure in the absence of LLSC.
We now state the KKT conditions for Problem (3) for which the Lagrangian function can be written L(x, y, v) E y:)
>m (x, where v,, Vi, dual variables
m
4

---

Published as a conference paper at ICLR 2025
associated with the constraints. Then, KKT solution (x,xy, vJ), if exists, satisfies the following:
Vxfi xx) V (X,, vE) vI 0, Vi, m VyJe (x), V (X7, Y7) V 0, Vi,
(Stationarity of Problem 3
(Stationarity of Problem 3
Vygh (x, = =0, Vi, x x = (E,
(Primal Feasibility of Problem (Primal Feasibility of Problem
Note that the dual feasibility and complementary slackness conditions in this KKT system are implied by the primal feasibility condition and hence can be omitted. For convenience, we define the KKT stationarity residual for primal-dual pair (x, Vr. v.) as KKT(X,, V:. == || [(x, Ys. v:)1l? which will be used as part of our stationarity convergence metric defined later. Note that when LLSC holds, it is not difficult to show that the V = 0 and only if KKT(x,; yı. Va) = 0 for some y, E I This fact will serve as a "bridge" to connect the above KKT staionarity and the hypgradients induced by the diminishing /r-qudrratic regularization described next.
2) The Diminishing quaQuaaaii Regularization: To address the challenge of lacking LLSC in our algorithm design, our basic idea is to augment the LL objective function by introducing quadratic regularizer that is controlled by sequence of diminishing regularization parameters, thereby reviving the LLSC in each iteration. These regularization parameters are carefully selected to ensure that the augmented problems converge the original problem, thereby leading to solution to Problem (3). Specifically, at iteration we define the augmented L.. objective function as follows:
the (Ni,,, Vi.)) = (xha + (1 (Xi,,,
where (x.,,. = //2 ||x,,|| 1 Ilyc.ell Here, the norm || || represents the l norm. X and Vi.t are the variables corresponding to agent i at iteration L. Here {ur) where μr >> 0, VI, is the diminishing sequence of regularization parameters, which ensures that tht, (x. is strongly convex for any x. This augmentation also leverages the connection between the KKT condition and the norm of the pe-induced hypergradient, allowing us to replace the LL objective ( by Vi, (xx,, Vt,t), facilitating the solution to Problem (3). Thanks to the strong convexity of the quadratic regularizor, vif (x,,,,) -) has unique minimizer for any given variable,, which is denoted as yi (x:).
Next, we define the approximate UL objective as f,, m Σ. Di (x,,)), where )j,, (xx,)) & (x (Xx.))). Similar to conventional bilevel optimizaiton with LLSC, for differentiable me (xi,),, the hypergradient V (xi,)) can be derived by the chain rule, the implicit func- tion theorem, and the augmented LL function as: V pr (xx,))
Vxfi (X Vi,r, (xs,))
th ie (x,,,, (x),)) vi,u (x1,), where Vi,p (xx,)) E R2 is the solution of the linear system: vi Viga (xi+) = [V yy vit (Xi,,,
(x),))).
After introducing the regularization in 4 can adopt the approximate KKT condi-
tion by replacing the LL objective with Vi Vt.), and thus consider KKT(X,, yt. Vz) =
||V L(x,, Yr, v2) < at time l. Here x, : [x] 11....... x m. and similarly for y, and Vz.
3 To address the consensus constraint x; = Xxy, (i, L in Problem we adopt the network consensus approach (Nedic Ozdaglar (009). where consensus weight matrix M E mm is used to mix and aggregate information at each iteration. The element [M];; represents the weight assigned for the information from the j-th agent at the i-th agent. Each agent uses the weights in its corresponding row in the M E Rm to aggregate the information from its neighbors. For consensus to be reached asymptotically, the matrix M should satisfy certain properties: (1) Doubly Stochastic: E = = [M], = 1; (2) Symmetric: [M] [M]; for all j E :: and (3) Sparsity Pattern Adhering to the Network Topology: [M];j > 0 if (i,.j) N and [M] ij 0 otherwise for all i.j E L. These properties ensure that the eigenvalues of M are real and fall within the interval (-1, 1], thus being sortable. Then, we order the eigenvalues of M as: -1 < >m (M) < .... < (M) < > (M) = 1. The second-largest eigenvalue in magnitude of M. denoted as X - max (M) (Am...m... (M))}. will play an important role in our step size selection and thus convergence rate in our proposed DUET algorithm.
3) Consensus Mechanism:
5

---

Published as a conference paper at ICLR 2025
4) The Proposed Algorithm:
Algorithm 1 The DUET Algorithm at Each Agent i.
With the preliminaries in 1)-3), we are ready to present our diminishing quadratically- regularized bilevel decentralized optimization (DUET) method, This method is specifically de- signed to address the challenges of bilevel optimization without
Set parameter pair (Xi,0; Va,0) = (xo.Yo, Vo). for / 1, ,T do
Update local models (x,,e-1 V...--...,.......... Vi,++1) 1 as in Eqs. (5)
Compute the (dxx d dyy) local estimator as in Eq. (6)
Track global gradients (h hyy h) as in Eq. end for
LLSC in decentralized environments with data heterogeneity. Our DUET method draws inspiration from the centralized SOBA approach (Dagréou al. 2022), which features a single-loop structure that is easier to implement and reduces the computational complexity compared to traditional double- loop methods. However, fundamentally different from SOBA, DUET builds on the augmented LL objective function in ( enabling us to address DBO problems without LLSC. The procedure of our algorithm DUET can be organized into three key steps:
Step (Update Local Models): In each iteration t, each agent i updates its local variables as:
Yic+1 = Prg Vir - -.hh") Vi,41 X1,41 Σ [M] PEN,
tp (5)
where dzz, Be and ?) are step-sizes for updating xs, Y; and v, variables, respectively, and Pr denotes a projection operator defined as Pr[y] := arg min le'll llq - all min(y, (TT where r > 0 is the radius. r and r are projection parameters of y, and v, variables, respectively (to be defined in the next subsection). First, the UL variable X1,++ is updated by aggregating the UL information from its neighbors and adjusting based on the local gradient h& which induces consensus among the agents the network. The L.I. variable yi,++1 is updated through a projected local gradient descent step, reflecting the agent's 's progress in solving its local optimization problem. Finally, the dual variable Vi,t+1 is updated using a projected gradient ascent step to ensure that the necessary optimality conditions of the LL problem are maintained. We also employ the projection steps of yi, and Vi, is to ensure that the sequences {y,,} } and (v.,} are bounded with radii rf and r respectively. Later we will show that, based on increasing r and r with respect the boundedness of yi,-- and varribbiaeles results in the boundedness of variiibba,, hence ensuring convergence.
Step 2 (Local Gradient Estimate): In the local gradient estimator step, each agent computes its local gradients to update its variables:
d V (Na,,, Yet),
d
Vy (x.,) - V2
yyy (x.,, Vist.
d VxJi (x.. V2 tht (Xi,, Yia)aa
We update Yı.t using the gradient of the augmented I.L objective wi (x,e) while the gradients for Vi,, and X are derived using the KKT conditions. This ensures that the LL solution meets optimality constraints and that the UL problem is solved efficiently.
Step 3 (Gradient Tracking in Upper-Level Parameters): In this step, each agent i updates its tracked gradient hy by averaging the gradients from neighboring agents and correcting the local estimates:
h
Σ
MM 1-1 d d h = d
h = dit.
PEN
The purpose of gradient tracking for the UL variables is to further reduce consensus error and accelerate convergence even under non-i.i.d data distributions. On the other hand, since the LL variables yi. and Vi, are updated locally without consensus requirements, gradient tracking is not needed for the LL variables.
To conclude the discussion of the DUET's algorithmic design, we summarize the per-agent algorithm of DUET in Algorithm
4 THEORETICAL CONVERGENCE RATE ANALYSIS
In this section, we will establish the theoretical convergence rate for the proposed DUET algorithm. Before state our main convergence result, we first present several needed assumptions as follows.

---

Published as a conference paper at ICLR 2025
Assumption 1 (Boundedness and Smoothness of the UL Objectives). The UL objectives f. satisfies: (a) For any E [m]. the UL objective f((x..) has a uniform lower bound denoted by fagi and (b) For any E [m]] the UL objective f; is twice differentiable and Lipschitz continuous with Lipschitz constant of I-fo-- The first-order derivatives V VxJe('- VxJi(xi, ) V VyJi,,,y.), ViJ((x,,)) are Lipschitz confinuous with respective Lipschitz constants Ti "''ssaa" Tiyrys" T'fiya"
Assumption 2 (Convexity and Smoothness of the LL Objectives), The LL objective Ii satisfies: for any E [m]] and any x,, the LL. objective gi(x.") -) is convex; and (b) for any E [m], the LLL objective De is twice differentiable and the derivatives VyDi and 9i. V Vy Lipschitz continuous in (X,, Y:) with respective Lipschitz constants 1 and
Liggys' Fggiyya
The smoothness and boundedness assumptions in Assumptions 1 and 2 are standard in the literature of bilevel optimization (Ghadimi & Wang 2018 Ji et al., 2021: Liang 2023 Dagréou et al. 2022, Ji et al. 2024, Kong al.) [2024] He et al. 2024). Unlike many works, however, do not assume LLSC, which significantly complicates the thcoretical analysis. Under the above assumptions, the augmented LL objective vi (x;,)) is Ov..- - strongly convex with Te. Mo 14,, where Tbe 1 by the definition of function hŞ. Hence, v (x, has a unique minimizer, denoted by Yi,u, (xx). To this end, we introduce the following convergence metric help us approach the KKT condition as the ju-regularized problem converges to the original problem as f4 shrinks to zero.
Specifically, for each {x,, Yt, ) at time i, we define
I1(,,, Yr. vo) == E1 V (&:)l + El|x - 1 2 101 Elyy? -vll Eli v.l.
(8)
Stationarity Error
Consenaus Error
Lower Lower=Level Error
Level
Dual Multiplier Error
where X,
ΣE X Y1
yy Vi m. y
(yi. 1 -im.pp V
Iv......, V mi and JA [vi.,...... 3 Vm.ju TT @ is the Kronecker product. Note that the first term in (8) quantifies the convergence of X, to a stationary point of the global objective. The second term measures the consensus error among local copies of the UL. variables. The third and fourth terms quantify the optimality gap in the LL problem's primal variable y: and dual variable va. respectively, across all agents. Thus, 11(x,, Yt, Vz) S. e for small e-value implies that the algorithm achieves three goals simultancously: i) approximate KKT stationarity convergence of Problem (3) ii) consensus of UL varvabiblles, and iii) optimal solutions to the LL yr-variables and dual V va-variables.
With Assumptions
and 2
we also define the following parameters that will be used in our algorithm:
B1 = Is.00 + (Irriy r(); A1 := 1-1² +
1 +
(1-A)3
r 2λ mm + > m 1xx;,o1? ry == Luyi rft
IV (0. O)I.
(9)
Jans
Japs
where x [m], are the initial points, constants Litp' Luiy' and parameter Johy are defined in Assumptions 1 and 2 and À is the second largest eigenvalue in magnitude of the network graph. B and j are the initial LL learning rate and averaging control parameter, respectively. Both 3 and µ are constants. With the above notations, we are now ready to state the main convergence rate result of DUET as follows:
Theorem 1 (Convergence Analysis for DUET). Under Assumptions 7 Aand choose =f(++1)-
Choose the step-sizes as 3e E [8(t + (5(1+1)--/4, 1)- L + Lggal with O < p < 1/6, 0 < T < 2/33 and
?) = 11) Bepe, and at (t + 1) 3r/2 33, 3.pue then holds that
10000(1111 (1/T1-50- 5p- -
minosesT IT(x,, Yt, vz) = O
Further, if Vi,t is bounded, it holds that minosesT KKT(X,, Nc. vo) = 0(1/T" 11 57 + 1/
The following result immediately follows from Theorem I
Corollary Let p = 3 and t + O. Then, DUET converges to a KKT point of Problem 3 at rate of O(1/T3), which implies that the number of communication rounds required to reach e-accuracy for our DUET method (
Moreover, if the problem instance satisfies the stronger condition that |/v (xq,) || is bounded, we can further improve the convergence result of DUET in Theorem T as follows:
7

---

Published as a conference paper at ICLR 2025
Theorem 3 (Convergence Analysis for DUET with Boundedness Assumption). Under Assumptions)
1
and 2 choose 14 ju( + 1)-P. Choose step-sizes Be E [B(t + 1)-7/4,1/ /. + T.g with
p <<<<<// 1/4,0 < < 1/11 and 1J: - 1)= 3r, and ot = (1 + 1) 30331////.p If Vi (xx,x)
1
is bounded, it then holds that:
minosisT I1(x,, Yt: vi) = 0 (1/TT) 1pp1113p--00 3p- 47)
Further, if Vi,t is bounded, it holds that minosesT KKT(Xx: Vr. vo) 01101111111111 47 + 1//20).
Similar to Theorem 1 the following result immediately follows from Theorem 3
Corollary 4. Let p = and T O. Then, DUET converges a KKT point rate of ( which implies that the number of communication rounds required to reach e-accuracy for our DUET method is ((1/ct).
Due to space limitation, we relegate the proofs of Theorems and to the Appendix. In here, several important remarks for the proofs of Theorems 1 and [ are in order:
It is worth noting that, compared to existing works on decentralized bilevel optimization, the major challenge in proving the convergence results in Theorems and 3 stems from the absence of LLSC, which breaks the standard descent lemma for the LL variable y, in convergence analysis. To address this challenge, leveraging our augmented LL objective, we establish new descent lemma for the implied UL objective function at time t, expressed in terms of X,, as follows:
Lemma (A New Descent Lemma of the Implied UL. Objective). Under Assumptions / [and] and letting Mt+1 Me S & for all t, the sequence {xi,7, Yi,t, Vi,ch generated by DUET satisfy:
4 M*+1 (x++1) tue (xx)
at 2
/ Me (x+)11 - 04t
aj Leme
|1h211 + ag acLayi 1 2
1 - x
2
20
ro Vir
m1
1=1
20rr
m
TTiiaoa || ly (xi,a)) || + T.sixa) )² I|yi,e - yiu (xx+))l
+
m
1=1
L
2
m
1 m
4/y1
|| - Vo, (xx,))] + 200r
Σ m
d hi&
171
Vy Xett, (Kett))
y (Reti)]
1
(me (we- p4+1
m
Oh:
1
m
2L
foyz
Nets
(x++1)11
2 ( (Mettet)
m
0h
where Ca1 and C42 are problem-dependeee constants provided in Lemma 12 in the Appendix.
Lemma]] I characterizes the expected per-iterate descent of the implied UL objective value, which depends on the consensus error of the UL parameters ||x; xs,e| ii) the approximation error of the LL optimal parameter l|y yp, (xx,e) ) 11 iii the approximation error of the dual parameter v| - v H. (xx,:) 112, and iv) the diminishing speed of the augmented LL objective
regularization parameter
The second challenge comes from the fact that DUET employs a decentralized consensus update mechanism for the UL model parameters as shown in ()) which inherently leads to consensus errors. Thanks to our algorithmic design DUET, the graph topology of the underlying network does not theoretically affect the convergence rate order of DUET (i.e., the T-dependence in the Big-O convergence rate result in Theorem D. Also, we achieve the ju-convergence rate, which depends on the decay rate of the step-size for LL yi-variables and the decay rate p of regularization parameter μ4. This is a new result compared to those obtained from LLSC.
We note that the augmented LL objective (4) for each agent also allows us to relax many restrictive assumptions made in traditional bilevel optimization methods (c.g., Liu et al. (2023a), etc.): i) we do not require strong convexity for the UL. objective every agent; ii) we relax the requirement of
8

---

Published as a conference paper at ICLR 2025
the derivatives by fi, Jy being Lipschitz continuous with respect to x; and y,. respectively; and (iii) we also relax the requirement of bounded dataset of (x,,y) These relaxations make our approach more flexible and practical in decentralized settings with data heterogeneity.
Discussions: As mentioned carlier, in this paper, we have tried avoid imposing any extra restrictive assumptions in the absence of LLSC. However, is interesting and insightful to compare the performance of our DUET algorithu with those who do make extra assumptions. For example, it turns out that the sl-BAMM method (Liu et al.) 2023a). which assumes a UL strongly convex (ULSC) objective, can be generalized to the decentralized setting as baseline for comparisons in our experiments. We name this extension as decentralized sI-BAMM with gradient tracking (DSGT). DSGT adopts the same single-loop framework as DUET bUETbut utilizes different augmented LL objective function, which follows Liu et al. (023a) to aggregate the UL and LL objectives for every agent as follows: ei (xx,., Vv.e) == (x,,, Vi.1) + (1 (X,,,,.. For DSGT, we make the following extra ULSC assumption for every agent:
Assumption 3 (ULSC Assumption for DSGT). (a) For any i E [m]] and fixed x,, UL objective
(x(x..) is f -strongly convex. (b) For any i E [m]]. the derivatives V Ji. V are Lipschitz continuous in yi) with respective Lipschitz constants L
Tigg l feyys
With Assumption we can show the following convergence result for sI-BAMM (the proof of Theorem ii similar to the proofs of Theorem [ [and hence omitted for brevity.)
Theorem 5 (Convergence Analysis for DSGT). Under Assumptions
7 and 3 choose Ht jt + 1) Choose the step-sizes as Bg E [B(t + 1)--1/4, 11/L (0)///,1/LL_,, + Lygal with p E (0, 1/6), (0, 2/33/)3) and 1/t (t. + 1)-5/2 and at (t + 1) B.pa. It then holds that minogesT [Ix,, Yr, v.) = 1(10((111)) 1 5p #T). Further, if Vi, is bounded, it holds that minosesT KKT(X,, Yt, v,) = 0(1/7 5p- 4r + 1//220)
We also notice recent work called LV-HBA Yao et al. 2024), which considers more generic case where the lower-level problem includes equality or inequality constraints g(x, and pro- poses a value function-based proximal Lagrangian method to enforce the constraints with provable rate of ((1/K() (22)//).. However, this convergence rate and our convergence rate are not comparable due to different stationary measure. Our stationary measure is define in Eq (8) In contrast, the stationary measure R& of IV-HBA is defined (x.,, 2)) + Nxxz(x,y, y. 2)), where y)x, is the UL objective, f(x, y) is the LL objective and (x, y, z) is truncated proximal Lagrangian value function. Cą is penalty parameter. (s(s) denotes the normal cone to Ω at
following: Rs
dist (O, (VF y), + C (x),(x,)),
5 NUMERICAL EXPERIMENTS
In this section, we conduct numerical experiments to verify our theoretical results for DUET. Due to the lack of existing algorithms for solving decentralized bilevel optimization problems without LLSC assumption, we compare the convergence performance of DUET and DSGT.
1) A Pedagogical Example: We first verify the convergence results under the ULSC and non- LLSC cases using five-agent communication networks, with the network edge connection probability Pc 0.5. The decentralized bilevel optimization problem is defined as the following: minxeR" |X-
+ + |lyi
e|l² y = (yī. arg min x=) 1 ||y1ll= x y2, where denotes the all-one vector with dimensionality being clear from the context. As shown in Figs. [(a) and [[b] the gradients of x, y. reach zero when using our DUET algorithm, suggesting they can converge to the global optimal solution without the LLSC assumption. Note that we use "GT=1" and "GT=0" to denote the adoption of gradient tracking the algorithm or otherwise, respectively. As shown in Figs. ((a) and [(b] the gradients of x. y converge more rapidly when gradient tracking is adopted. However, as observed in Fig. [(d) DSGT tends to select an LL solution y E S(x) that also yields a good value for the UL objective function (i.e., fi +)), which is due to the ULSC assumption. In contrast, as shown in Fig.
I(c) DUET tends to choose an LL solution y E S(x) that has a good LL objective value, which is more relevant in DBO problems.
2) Decentralized Meta-learning Problems with Real-World Data: Next, we evaluate our DUET algorithm on decentralized meta-learning problems with heterogeneous datasets. Following

---

Published as a conference paper at ICLR 2025
Der Bhot
24T 0714
Salt 2h12 2907 thet
phod
HEST (ha1
Timee0
Timels
Temats)
(a) The gradient of x.
(b) The gradient of y.
(c)
LL objective value.
(d) UL objective value.
Figure 1: The gradients of the variables x and y, and the objective values of the UL and L.I. problems.
2-4
(a) i.id
(b) non-i.id.
(a) i.i.d
(b) non.i..d
Figure 2: Test accuracy on the meta-learning problem with a 5-agent network on MNIST.
Figure 3: Test accuracy on random graphs and the meta-learning problem on MNIST.
the experimental settings in Qiu et al. (023). we use the MNIST dataset to train m personalized classifiers. In this setup, represents the common parameters shared across all agents, while 0 corresponds to task-specific parameters for each agent. The cross-entropy loss is employed as the main objective function for ft. To prevent overfitting on local samples, incorporate quadratic regularization term in the UL objective function f,, affecting the parameters 0. We set m = and allo- cate 12,000 samples to each node in communication network generated by the random Erd6s-Rénge graphs. In the scenario with i.i.d. data, all agents have access to the same global dataset. We compare our proposed algorithms with the baseline DSGD. In Fig. 2(a) the DUET algorithm demonstrates superior performance by achieving the highest testing accuracy, along with fast convergence. Notably, its testing accuracy is 6% higher than that of the standard baseline based on decentralized stochastic gradient descent. This performance highlights the ad vanttagge of DUET in collaborative training across multiple learners and in tailored adaptation at each node.
In contrast, in the non-i.i.d. data scenario, we adopt a data partitioning strategy, where each agent accesses data consisting of 95% from two specific labels and 5% randomly selected from other labels. This strategy ensures significantly diverse label distributions and high data heterogeneity across nodes. In the non-i.i.d. data scenario, we compare DUET and DSGT by focusing on their configurations with gradient tracking (GT=1) and without gradient tracking (GT=0). This ablation study examines the benefits of incorporating gradient tracking. As shown in Fig. 2(b) both testing accuracy is higher for all algorithms that include gradient tracking. Specifically, the DUET and DSGT algorithms with gradient tracking significantly outperform their counterparts without gradient tracking, illustrating the effectiveness of gradient tracking in enhancing model performance in environments with heterogeneous data. We further evaluate the impact of edge connection probability Pe on the performance of DUET and DSGT in both i.i.d. and non-i.i.d. settings with five-agent network. Using Pe E {0.3, 0.5, 0.7} and the same learning rates as before (Fig. 3) we observe only a slight improvement convergence with higher Pe indicating that our DUET algorithm is robust to different edge connection probabilities and adaptable to various network configurations. To further validate our algorithm, additional experiments on decentralized hyperparameter optimization and decentralized meta learning are presented in Appendix F..3 and
6 CONCLUSION
In this paper, we explored decentralized bilevel optimization (DBO) problems that do not require lower-level strong convexity (LLSC). To address this challenge, we proposed a single-loop DBO algorithm called quadratically regularized bilevel optimization (DUET) and established its theoretical convergence rate performance. Additionally, we adopted a single-loop structure in DUET to more effectively manage the challenges posed by nested structures, and we incorporated gradient tracking to tackle data heterogeneity. We also conducted numerical experiments to validate the effectiveness and efficiency of our proposed DUET algorithm.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The work has been supported in part by NSF grants CAREER CNS-2110259, CNS-2112471, ExpandA1-2324052 SINGS-214825) ECCS-2413528, DARPA Young Faculty Award D24AP00265, ONR grant N00014-24-1-2722, and AFRL grant PGSC-SC-111374-119
REFERENCES
Jincheng Cao, Ruichen Jiang, Nazanin Abolfazli, Erfan Yazdandoost Hamedani, and Aryan Mokhtari. Projection-free methods for stochastic simple bilevel optimization with convex lower-level problem. arXiv preprint arXiv:2308. 2308.07536, 2023.
Jincheng Cao, Ruichen Jiang, Erfan Yazdandoost Hamedani, and Aryan Mokhtari. An accelerated gradient method for convex smooth simple bilevel optimization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL [ net/forum? a JBV
Lesi Chen, Jing Xu, and Jingzhao Zhang. On finding small hyper-gradients in bilevel optimization: Hardness results and improved analysis. In Shipra Agrawal and Aaron Roth (eds.). Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pp. 947-980. PMLR, 30 Jun-03 Jul 2024a. URL /tpp https//22//cccee22
html
Pengyu Chen, Xu Shi, Rujun Jiang, and Jiulin Wang. Penalty-based methods for simple bilevel optimization under hölderian error bounds. In The Thirty-eighth Anmual Conference on Neural Information Processing Systems, 2024b. URL htthhttps/// http:///ppeeeveeeeeeeeeeee
/ttps:///peeeeeeeww wwt het/forummii.
6012
X. Chen, M. Huang, S. Ma, and K. Balasubramanian. Decentralized stochastic bilevel optimization with improved per-iteration complexity. In Proceedings of the 40th International Conference Machine Learning, volume 202, pp. 4641-4671. P0M...1...L...... 2023.
Xuxing Chen, Minhui Huang, and Shiqian Ma. Decentralized bilevel optimization. Optimization Letters, 2022. URL httthttt: www.atiscchccccc..r...o.... ottg//oopssss:::2222222222
M. Dagréou, P. Ablin, S. Vaiter, and T. Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. In Advances in Neural Information Processing Systems, volume 35, pp. 26698-26671 10. Curran Associates, Inc., 2022.
Youran Dong, Shiqian Ma, Junfeng Yang, and Chao Yin. A songle-loop algorithm for decentralized bilevel optimization, 2024. URL
221p:///...r//a///.1.....11 08945
Hongchang Gao, Bin Gu, and My T Thai. On the convergence of distributed stochastic bilevel optimization algorithms over a network. In International Conference on Artificial Intelligence and Statistics, pp. 9238 9281. PMLR, 2023.
Saced Ghadimi and Mengdi Wang. Approximation methods for bilevel programming, arXiv preprint arXiv: /002.//80.02222 02246. 2018
Diba Hashemi, Lie He, and Martin Jaggi. Cobo: Collaborative learning via bilevel optimization.
In The eighth Annual Conference on Neural Information Processing Systems, 2024. URL net/ forumriruiioooo d= TapfU
/ fictps://openree
Yutong He, Jie Hu, Xinmeng Huang, Songtao Lu, Bin Wang, and Kun Yuan. Distributed bilevel optimization with communication compression. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference Machine Learning. volume 235 of Proceedings of Machine Learning Research, pp. 17877-17920. PMLR, 21-27 Jul 2024. URL httptttpp//pprrcedingg mlr. wlr.ppess/w235///
Kaiyi ji and Yingbin Liang. Lower bounds and accelerated algorithms for bilevel optimization. Jour- nal of Machine Learning Research, 24(22):1-56 2023. URL http:://// / fmlr. owtpp/prrg/ppapape//epop
v24 424/21-2 21-0949-- html
11

---

Published as a conference paper at ICLR 2025
Kaiyi Ji. Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 4882 4892. PMLR, 18-24 Jul 2021. CRLLhttps:/// http::s//proceedingg ngs. mlr....rr... wttp.r..pee////1//522222 html
Kaiyi Ji, Mingrui Liu, Yingbin Liang, and Lei Ying. Will bilevel optimizers benefit from loops. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22 Red Hook, NY, USA, 2024. Curran Associates Inc. ISBN 9781713871 1088.8
Ruichen Jiang, Nazanin Abolfazli, Aryan Mokhtari, and Erfan Yazdandoost Hamedani. conditional gradient-based based method for simple bilevel optimization with convex lower-level problem. In Proceedings of International Conference on Artificial Intelligncce and Statistics, pp. 10305-10323, 2023.
Boao Kong, Shuchen Zhu, Songtao Lu, Xinmeng Huang, and Kun Yuan. Decentralized bilevel optimization over graphs: Loopless algorithmic update and transient iteration complexity, arXiv preprint arXiv:2402.00 0061070.......... 2024.
Junyi Li, Bin Gu, and Heng Huang. Improved bilevel model: Fast and optimal algorithm with 00690
theoretical guarantee, 2020. URL BRLLbbtss://axxiii org/ http///b////////// http://twwxvv.//////////0...00
Bo Liu, Mao Ye, Stephen Wright, Peter Stone, and Qiang Liu. Bome! bilevel optimization made easy: A simple first-order approach. Advances in neural information processing systems, 35: 17248-17262, 2022a.
Risheng Liu, Yaohua Liu, Wei Yao, Shangzhi Zeng, and Jin Zhang. Averaged method of multipliers for bi-level optimization without lower-level strong convexity. In Proceedings of International Conference on Machine Learning, pp. 21839-21866, 2023a.
Y. Liu and R. Liu. Boml: A modularized bilevel optimization library in python for meta-learning In 2021 IEEE International Conference on Multimedia & Expo Workshops (ICMEW), pp. 1-2. IEEE, 2021.
Zhuqing Liu, Xin Zhang, Prashant Khanduri, Songtao Lu, and Jia Liu. Interact: Achieving low sample and communication complexities in decentralized bilevel learning over networks. Proceedings of the Twenty-Thire Third International Symposiun Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, pp. 61-70, 2022b.
Zhuqing Liu, Xin Zhang, Prashant Khanduri, Songtao Lu, and Jia Liu. Prometheus: Taming sample and communication complexities in constrained decentralized stochastic bilevel learning. In Proceedings of the 40th International Conference on Machine Learning, pp. 22420-22453, 2023b.
Songtao Lu, Siliang Zeng, Xiaodong Cui, Mark Squillante, Lior Horesh, Brian Kingsbury, Jia Liu, and Mingyi Hong. stochastic linearized augmented lagrangian method for decentralized bilevel optimization. Advances in Neural Information Processing Systems, 2022.
Zhaosong Lu and Sanyou Mei. First-order penalty methods for bilevel optimization. arXiv preprint arXiv:2301.01716. 2023.
Roey Merchav and Shoham Sabach. Convex bi-level optimization problems with nonsmooth outer objective function. SIAM Journal on Optimization, 33(4):31 14-3142, 2023. doi: 10.1137/
22M1533608. URL https: /tttpp:://oo...o /tt. http:/oo.ooo.oooo//ooo/oooo htt///1..113///// 1137 533608
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions Automatic Control, 54(1):48-6) 61, 2009, doi: 10.1 10.1009TAC.2208.200955
Yurii Nesterov. Lectures Convex Optimization, volume 137. Springer, 2018.
Youcheng Niu, Jinming Xu, Ying Sun, Yan Huang, and Li Chai. Distributed stochastic bilevel optimization: Improved complexity and heterogeneity analysis, 2023.
Clarice Poon and Gabriel Peyré. Smooth bilevel programming for sparse regularization. Advances in Neural Information Processing Systems, 34:1 14115443-5555 2021.
12

---

Published as a conference paper at ICLR 2025
Peiwen Qiu, Yining Li, Zhuqing Liu, Prashant Khanduri, Jia Liu, Ness B Shroff, Elizabeth Ser- ena Bentley, and Kurt Turck. Diamond: Taming sample and communication complexities in decentralized bilevel optimization. In JEEE INFOCOM 2023-IEEE Conference Computer Communications, pp. 1-10. IERE, 2023.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. Advances in neural information processing systems, 32, 2019.
Shoham Sabach and Shimrit Shtern. first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2):640-660, 2017.
Sepideh Samadi, Daniel Burbano, and Farzad Yousefian. Achieving optimal complexity guaran- tees for a class of bilevel convex optimization problems. 2024 American Control Conference (ACC), pp. 2211, 2023. https://aaap www.nticccholla..oooom wtw.:/aaaa..rrooooouuu....
264305773
Shuoguang Yang, Xuezhou Zhang, and Mengdi Wang. Decentralized gossip-based stochastic bilevel optimization over communication networks. Advances in neural information processing systems, 35:238 252, 2022.
Wei Yao, Chengming Yu, Shangzhi Zeng, and Jin Zhang. Constrained bi-level optimization: Proximal lagrangian value function approach and hessian-frre algorithm. arXiv preprint arXiv:2401.16164, 2024.
Haifeng Zhang, Weizhe Chen, Zeren Huang, Minne Li, Yaodong Yang, Weinan Zhang, and Jun Wang. Bi-level actor-critic for multi-agent coordination. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 7325-7332, 2020.
Yihan Zhang, My Thai, Jie Wu, and Hongchang Gao. On the communication complexity of decentralized bilevel optimization. arXiv preprint 1321
13

---

Published as a conference paper at ICLR 2025
A
NOTATION
We summarize our notation in the following table.
Notation
Definition
NV
Set of nodes.
Set of edges.
m
Number agents.
i-th agent.
T
Total iteration numbers. t-th iteration.
Step size for updating Step size for updating y.
B
Step size for updating v.
p
Averaging control parameter.
Learning rate control parameter for updating y.
1
Regularization parameter for the LL objective.
L
Lipschitz constant of the UL objective fú, see Assumption
Lises Lisg
Lipschitz constants for V Vx. and V Vxfi(xx, see Assumption
Liyyy Lifiya
Lipschitz constants for Vy). and Vy,f(x,, (), see Assumption
840
Uniform lower bound of the UL objective /í. see Assumption)
Ligyy1
Logiy2
Lipschitz constants for V Vy see Assumption
Ligigy1'
Lgigg?
Lipschitz constants for V see Assumption
Lighyy'' Ligiyya
Lipschitz constants for V Vyylis see Assumption
Strongly convex constant of the augmented L.L. objective 3/4 (X;, :)
gi
LL objective, convex and smooth, see Assumption 2
UL objective, bounded and smooth,
Assumption
M
Consensus weight matrix M N for the decentralized network.
Second largest eigenvalue of the consensus matrix M.
X,,1
UL variable for agent i iteration t.
Vi.1
LL variable for agent at iteration
Vi.t
Dual variable for agent i at iteration L.
Gradient of the Lagrangian function.
V O
Gradient of the total UL objective.
Table 2: Notation Table
Also, we formally define the communication complexity a decentralized algorithm as follows:
Definition 1. (Communication Complexity) The communication complexity is defined the total number of communication rounds needed to converge to an e-stationary point. In each round, every node can send and receive veclor-valued information to and from its neighboring nodes.
B EXPANDED RELATED WORK
1) Decentralized Bilevel Optimization (DBO): One line of works enforce consensus on the LL variables. For example, Chen al. (2022) employed hypergradient estimation with gradient track- ing for both deterministic and stochastic algorithms, achieving convergence rates of O(1/K) and O(L/VK for nonconvex UL and strongly-convex LL problems. However, enforcing LL consensus adds a costly inner subroutine for decentralized Hessian inverse operation, significantly increasing the communication costs. Lu et al. (2022) explored stochastic bilevel optimization algorithms with primal-dual updates and demonstrated linear convergence speedup with respect to the number of nodes in homogeneous data settings. However, this method does not extend to non-i.i.d. environments, which are common in decentralized systems. For non-i.i.d. data, Yang et al. (2022) introduced gossip protocol-based decentralized bilevel algorithm that achieves linear speedup while accounting for the communication graph's 's spectral gap. Additionally, Dong et al. (2024) proposed single-loop algorithm that does not require gradient heterogeneity assumptions. Similarly, /Zhang et al.) (202))
14

---

Published as a conference paper at ICLR 2025
introduced decentralized stochastic bilevel gradient descent algorithms for heterogeneous settings, illustrating how communication for hypergradient estimation affects convergence.
2) Centralized Bilevel Optimization without LLSC: Merchav & Sabach (2023) addressed convex bilevel optimization problems with nonsmooth outer objectives, introducing a generalized sub- gradient method to the bilevel setting and achieves sub-linear convergence rates for outer and inner objectives under mild assumptions. They additionally improves to a linear rate for strongly convex outer objectives while allowing for nonsmoothness. In contrast, our work specifically deals with smooth UL objectives. [Chen et al. (2024b) proposed a penalty-based algorithm that leverages Hölderian error bounds to achieve convergence rates of (11/²), assuming convex UL objective. Cao et al. (2024) introduced an accelerated gradient method specifically designed for bilevel problems with a convex lower-level problem, achieving convergence rates of O(1/VE) for smooth convex objectives. [Samadi et al.] (2023) achieved optimal complexity guarantees for class of convex bilevel problems using advanced regularization techniques and strong convexity assumptions. While their works (Merchav & Sabach 2023] [Cenn al. 2024b Cao et al. 2024 Samadi et al. (2023) assume UL convexity, our work focuses on non-convex UL objectives, broadening the applicability to more general problem settings.
C PROOF OF MAIN RESULTS
Before diving into our theoretical analysis, we first introduce the following notations.
Let {az, be, ce, de be sequence of decreasing positive constants. The general form of potential function is given by
V ae (xx (x.) Sol dellx x + dra 8 kill?
+ belly: yp (x:) + ca -ellvevv (x)
We also introduce the following notations:
X = [x m IT.
Xi,
Y1 ly
Ve = vT...
m.
The proofs of the theorem involve four major steps, which include: (1) upper-bounding the descent of the total UL objective; (2) controlling both LL solution and multiplier errors in the descent of the total UL objective; (3) controlling both the consensus steps and the gradient tracking steps; and (4) combining all results from the previous steps and choosing suitable coefficients {a,, bb, ct de ) for the Lyapunov function to prove the convergence guarantec.
Step 1: Upper-bounding the descent of the total UL objective. We begin by analyzing the descent of the total upper-level objective p.. (Xt), which is the average of the individual UL objectives Φi ja (x.). Our goal is to establish an upper bound on the change this objective between iterations
t and + 1. The descent of the approximate overall UL objective is 4y, (Xt) = E Di (Xt).
where Ti (&,) J, ( (x.)))
Lemma 2. Suppose Assumptions holds. Let p4+1 I 14 S for all k. Then the sequence of Xi,t, Yia, Vi generated by our algorithm satisfy
p (x++1) Ppr (Xi)
V. (xx))?=
04
of Lo
12
on anL
1
Σ Xx
xx,e!*
2
2
20
ro? Vm
m
Vis
+
20,r
Σ
(Lyrgg llvi (xxre)l + D
|y
y/. (xx,,) 12
1=1
air
+
Vys
Viee - - (xx,)))
m
15

---

Published as a conference paper at ICLR 2025
1
+
2
h
m
1
m
2
X Miets (Xc+1) y
| (8e+1) ||
(mue ( Hr
m
The
1
lly (R++1))l Syys
Me+1 (He -letl
2
m
The
where both Cel and Coz are constants given by
C+1 b Iaiya Lups (Irign + Tnprys) Ber + Tnb oi
C42 == Liys Siya + Luys (Letyr + LL(ixo) Ove + Li "bp
Proof. We decompose the difference Me-1 (X++1) - T) Me
(xx) into two terms:
Φ Mes (8e+1)=
$ Mi (Xx)
=fi (8411) (Xc+1) - S1 (Ze, (xi)
=fa (Zeti. (R(+1)) fo (Ret1, (Re+1)) + fi (Re41,yp (Re+1)) - fo (Ze. (xx))
By the smoothness of fx(..-) and
inequality, we have
m
Sa (Ret (Re+1)) - Ji (X1+1, (Ret1))
m
m
Vyy (Zetz, (Xe11) Speln (x++1) - ym, (Re+a))
m
1
fiy2 ly (Xe+1) yi, (81+1)112
m
V (Xet11 (8e+1)) | (Re+1) - Vū, (8c+1)]]
17
T.s1y2 lyyper (8(42) yic (x1+2)11
777
2
V (X++1, (8e+1))
yiets (Zeta)]
Metz (w=-Mett)
m
The
Pt
2 flyz p (x++1)11
(u-- (K4-Het) U1+11 2
(10)
m
The
Me
where the last inequality follows from (x) -x) (x)] S 2||x)(x0]| M2+1-
la-n'l x¹
with / Me and
oh,
Next, let Laya Co1 ||v;, (x+)]| + Cos, we have
1
me (Xe+1) &p. (Xx) =
i (x++1)
mc (x+)
1=1
[f (Xe+1,8), (Xe+1)) - fo (X,, (x:))]
m
16

---

Published as a conference paper at ICLR 2025
1
m
Laye ||x
(xt)
Xx+1
xx)
x,11²
(11)
m
20 Pp
We apply the gradient descent update step
X++1 x; -a;lix
(12)
Incorporating
12
into
we get
Mr (x++1)
Ppz (xx)
of
< - O22
V (Rt), lixe
+
hix 1
20 Vite
i=1
at
/ pe (xx))1
ake
a Lo
||
1| + ||
ai
|
2 Mr (xx) - -h2l'
2
2
2
We could further get
Lu (8++1) - Due (xx)
S
Q4 / (xx)112
a1
a L
||
2
2
20
+ 2
04
V (x,)
1
V Mi
(xx,1)
+
1
VTl (xx,1) h
m
m
o Lom
<
02
V4 (x,)]1²
|
2
20
PM
+
04
VΦ M4
(8i)
1
V VΦL
(Xi,)
+ Ort
V Me (Xi,t) -h%
m
i=1
i=1
04 2
/ (x+)11
att
af Lo
||bb|| + ag aLLor 1
Σ
||xc xx,=11
2
20
ro Vel
Vpc
i=1
1 m
+
atj
(xx,)
h
m
Now, we consider the last term of this equation,
1
m
V t (xx,e)
- h4
Φ p4 i=1
(xx,))
h
m
m
m
i=1
1
1
1
<
V c
(xx,e)
+ 2
h
1=1
2 m
m
VΦ Me
(xx,)) - -di:tl" +
m
m
x
The desired result follows from the inequality (E==aah ax²² Sr Er oz. By the definition of of (x.).
we get Vại Mr (xx+) = Vxfi (N (xx,)) V2 Vay time (xi, yfu (xx,)) va. (xx,),, which implies that
IV Me (xi,)) - d
Vol i4 (x,,) - Vxfi (X,)). + VZy Uie (xires vo.e) vssell
< Vxfi (x.,.." (xx,.) - Vxfi (x.,,,
[VV Mpr (i.e) VZy W', (X yiu (xxx))] vi, (xx,))
17

---

Published as a conference paper at ICLR 2025
+ V Uee (xL, vi.)) [vs. Via (xs,,)]] ||
$ (1r + Luwya li (xx,))l || - yie. (xx,,)) + Lays Vv.c Vie (xx,))l
We now combine all terms and upper-bound the total descent of the UL objective:
p.- (x++1) -uy (xx)
s at / (xee112
(
04
of Tapee
[
+
or Trpe ro Upe
X - xx,e|
2
2
20
m
+ m
200r
m
(Lyss V/ (xx, + =
|8 Fig (xx,
04 Vy
VE.e
Vin (x(x))1
m
2
+ 20pr
d
h
1=1
1 m
2
VyJi
(2441, iens (Re+1)
yieess (Reti)| /|
(uu Het1
772
The
He
2L s.ya pyyp (x++1)l1
[i pe+1
14
Step Controlling both LL solution and multiplier errors.
In this step, we analyze the errors arising from the LL variables y,. (xx,.) and the multiplier vyu (x,,).
These errors contribute to the overall descent of the upper-level (UL.) objective function, as discussed in Lemma 2 The boundedness of yū. (xt,) and v (x4,) will be key to understanding the impact of these errors.
Lemma 3. For Yú, (x),,) and vū, (x,,),, we have (recall that To and ry are defined in P)):
(a) ly (xx, S r
Lisn 1(-11 Owws
1)
oani
(b) (x,,))) S Ol O122 1 ), for any X satisfying |x S r/ 0 00 owm.
1
The assumption that [|x;,I|| S r bounded relative to ow.. further supporting the use of the bounds for yj, (xx,e) and vj, (xx,)).
will be proven later, but for now, it ensures that X1, is
Proof. (a) By the L,,, -Lipschitz continuity of f; and o -strong convexity of wit in Assumption we can deduce that
fi (xx,,))) S Lico and I (xi,) via (xx.))] '
Tvee
For v (xx,c) = Dyy Uei (xs,es Vie (xx,,)) Vy.f (Xq, (Xc.)),, we have
L
|| (xxx))) < VV Uns (x,,, (xx.)))
||Vy (Xi,,, (xx+)) || S
(b) Assume ||xxeel I r.. By the optimality of y (xx.)) and Lemme 11 (a), we take x" and have
Luys |xx, - Oll + lyy (0)]
Iy (xx,))l
18

---

Published as a conference paper at ICLR 2025
Lays
||<,,e|| + 1ly (0) 0ll
Luny1 ||<s,el|| +
(yy (0)) (0,00
Ove
Jue
Toyy a +
where the second inequality follows from the strong convexity of the (Xi,))) +), the last inequality follows from the optimality of yz (0).
Lemma 4. For any i [m], the sequence of Xi,ts Vi,t, Vi,t generated by our algorithm satisfy
1 - Nic (x
$ - 01 3r) I|ys.  yua (xs,))1 (23) Osine
1
Tuvus
and
||ve,11- - Vie (xx,0]1 < movn) llva,e Vie (xs,,))12
+ 27 (Irggra llv (xx+))l + Iisrys) ||ya,e - Vi, (xx,))
Ovee
if we choose Bi S oone thom and 17: S Love
Proof. We begin by analyzing the update for the LL solution, ya,+1- Recall that the update is performed via projected gradient step:
Vi,+1 Prylyv, - V. Pi (x.))
where P.y. denotes the projection onto the feasible set with radius ry. This projection ensures that yi,+1 = yi.++1 (xi,++) remains bounded, preventing it from diverging. To analyze the error [y y4, (xx,))l we decompose the update step:
lyy.441 - yj, (xx,)) Prrr ly.. - VyVy (x,,). - 8y, (xx.))l
Since the projection is non-expansive, i.e., does not increase distances, and ||y;e (xx,e) 11 s r by Lemma 3 we have:
ly yi, (x & llyr., - th (x - yi, (x,,
Next, we expand the right-hand side:
||ya441 yp, (xx::)l2 < yy, - yp, yy, (xxx)] 23, (ye. - yj, (xix), Vytha (Xi,) + 38 VVyya (x..)
To bound the inner product term, by the ow,, -strong convexity and L smoothness of ui (x, since Vp (xi,e, Vi, (xs,))) 0, Theorem 2.1.12 in (Nesterov 2018 implies that
(yi. ym, (XLL)) , Vy (x.,))
(yr. yp, (XLLe), the (x,),, the (Xi,,, (xx,))))
Oven Teaie
1
Ilye, yi, (x,))l + own Lun
VV (X.,) V1.011
Ovve + Lodme
Hence, when 0 < Br 5 OwHi thmms
we have
[yett Yr (1
19

---

Published as a conference paper at ICLR 2025
20 vus Loine Be) I1ys, Mns (xx,t)1
1
a ous + Legee
23
Jvve
+
-
83
2ir Litie
B8 1185.
Sh. (xx,))|
2
1
8 |
Ovee + Livpe
Jeme
+
Lowya
which implies the desired result since 2 S own, then:
S 1. This inequality shows that the error in Vi, contracts as long as the step size 3g is chosen appropriately, ensuring the progress of the algorithm toward the optimal solution yú, (xx,e).
Lep
Now, we proceed to bound the error in the multiplier V4,++ = (x.++((,,++)) by using Vyy Vin, (xi,,y (x..))) y (x..) = VyJi (xLe, (xx,)). As with the previous projection for yi.+1, the non-expansiveness property of the projection operator P,y[-] gives us:
Vi.++1 The (x
= -PPgglliee - ni ([V) 4/m t/n (x.). Vi. Vyfi (x..) vi. (xx,,)]
< Via - Vn (Xi,)) Th ([V Vi (xia) Vi.. - Vysi (x.,)
(13)
where the inequality holds because V (xl S r by Lemma 3 Next, we expand the right-hand side, which gives:
Va,e Via (xx,)) 17t ([V the (X Vit)] Va,t V (x.))
Va,t Vin (xx,)) - 1). [Vy Uim (xa)) [Vee= - vin (xx+)
[Vy Pin (xi)) - Vyy (Xi,) (xxx)) yie (xi,) TI [Vyst 3,. (xx,))) VyJs (x.,,.
(14)
Hence, by Cauchy- inequality, for all 2 O, we incorporate
14 into 13 and have
Vi,e4 - Vju (x
<(1 + ||[I- n7. Vey tiee (x.e)) [va,e - -vi (xx.))
+ 1 + _ mee x || V Vu (x,e)) - Voy the (x (xx, vn (x01)
+ (Vy.i f (xi,t, yu. (xx,)) VyJi (xi,) (1.))
When ?7 S 1/ Ly by the o. strongly convexity of ph (Xx,, +), since the spectral norm is monotone, we have
[[T -h n1 Vzy the (Xi,, (est1a) [Ve. vi, (xx+)] S (1 (19 1Ive - vi, (xx,))l-
Next, by Lipschitz continuity of V tyy (x, :) and fi :), we get
|| 2 by the (x,)) - V2 yy thme (xc,,) (Xx,,)) vin (xa,) + V (X4,1 (xx.)) Vyfi Yx,))l
[uyyya live, (xx,,)) + L(tyy)) I|ya. - -Y (xx,))l-
Taking & no we have
Verti - vie (xx.t)l
< (1 m. (1 mmo Il vie (xx1)))
+ 11 Te
n (Luggr lia (xxs,)) + Lisss) I|xse - yt, (xx.)))1²
which implies the desired result since vi S Taine S ne/
20

---

Published as a conference paper at ICLR 2025
This shows that the error in the multiplier Vi, also contracts over iterations, provided that the step size Th is chosen appropriately.
By the above lemmas, Lemma 5. Suppose Assumptions hold. For any i E [m)] the the sequence of Xi,t. Viet Via generated by algorithm satisfy
now proceed to analyze the enror of LL and multiplier variables.
8 $112 (Kaatzi)l |xx,e x,,++11 +
ssn. (xx.) - Vinss (XLe+1)
2L S
(4T Me+11
2
The
Me
and
2 (Lvi ll (xxx)) + Lv2) |xc,1 x1.4111?
|in (x51,) - Vieai (xx11t1))
(Crl | (x1et1))l + Issipa) I|rinss (xL.011)
2
+Cvz Vyyti (x4,e41 (84,441))) 2 ( - Ml+1 )²
)
where both Cv1 and Cv2 constants given by
Cv1 :=: 2 (Inigy2 + Iistyrs)) /oh, Cv2 Cx2:=
: ( + Iegiys)) /0h:
Proof. By the triangle inequality, and Lemma I1 yin (xx,,e) yiets (xs,++1)
a) and 13 a) with ví' = se and μ = Me+1
yiu (Xi.e) yiu (xi,+1)l + I/r (Xce41) Spers (XLe+1)
2 y (x5(etz)
Lug1 ||xi, - X1,1+1ll +
Ue 14+1
Jehe
The
Pt
Then with ye' = sh and μ = Me+1, we have
|/v (Xie)= Vinn (XLe+1) s li (xi:,) vū, (xi + |vv (xi:+1) Vieis (xx,e-))
Lvv live, (xx.)) || + Liv2)
|x2,,0 - -x,,t1ll
((on) Mikelliess (x + Iistsa) | (xs,et1)
+
+Cve | (x1e41: (x1141)))l)
(4 (44_lttt H4+11
Building upon the aforementioned lemmas, we can now proceed to analyze the iteration wise differences in the errors of LL and multiplier variables.
Lemma 6. Then for any i E [m], the sequence of Xit, Viat Viat generated by our algorithm satisfy
Vr,e11 Yiem (x))++1))² I|ya, - y", (xx,))l
S 2 Braw.. I|yce - -Y (xx.t)l1 (1 (1+ 5 Showw )
1
2,9 oen + Iepre 88 |1b5912
- | 21 2 24 yirm (xi,e+ ||
2L2
1yy
(Ni
M4+1
+
3,00
oR, B:0
21

---

Published as a conference paper at ICLR 2025
and
Vi,011 Vieta (x8,011) - l/ vie (xs,))l
2 ni lIvi Vi (xx 6 (Lv1 llv (x(e)) + Lv2)²
1
1|x,, xi,
+ 3tp (Trisors 11 (xxx)ll + Issiys) llxiee Yiu (xx,))
Jepu
1t He41
((Cr) | (xiitti)l + Esfiys) I1sinss (xiet1)
+
14 mor
+ Cv2 Boal/Vysi
(x (x))-1))1
Proof. By
inequality, is easy to check that for any e >> O, we have
I1y,441 ypm. (xx,+1)ll
-Ilyi,+1- -Y (xx,)) + yi, (xx,1) ypres (x1,++)) 11?
5(1+ + + [yi,++1 - yū. (xI, + (1 = >lly (xi,e) - Mpens (xi,++))l
Taking 3. by Lemma 4 and Lemma
have
1yr,++1 - Vuee (x1,++1)12
||yE, yi (xx,))l (1 1 1 Br0
$10
2B Jvv + Love
B
|1bs'11
2L2
2
11
||x1,1 xx,1+112
Brown
8 yires (xiitt))
(
Hi ( Mc+1 ( )
Brow which implies the desired result since Bro S 1 when Br S 2/(owm. + Lvn)). Similarly, for any O, by Cauchy-Schwarc inequality,
1+
Ht
V Vits (x),++1)122
=I| =|[vi,e-1 Vi, (x1,e) + vū, (Xi,e) Vies (x)1++1)1
5(1 + 6)1lve441 - vt, (xx,))12 (1 + Ill,,, (xa,) - Vieia (x1,41))12.
Taking 8 = : by Lemma
Fand and Lemma we have
V1,441 vieee (xx,)+2))
2 s l|va,e vin (xs,,)l?
2 ( (Irz llv (xx,e)l + Tiva) (1+ movm)) || x1,4+11/
+
2n (+ mmomee)) (Lorne lin (xs:e)l + Lifeys) Ilxcce - 8i, (xx,))l
+2 2 ((Cml Vinea (xxet1)) + Levvs) Ilmmns (xiet1))
22

---

Published as a conference paper at ICLR 2025
+Cv2 Vyss ( (xLe+1)) )))
(1
) ver
2
Me Me++
This desired result follows since M
I when S 11/T
Step 3: Controlling both the consensus steps and the gradient tracking steps.
In this step, we are focusing on controlling both the consensus steps and the gradient tracking steps within our decentralized algorithm. The goal is to show that the iterates contract over time, which means that both the decision variables x; and the gradient tracking variables h converge as the algorithm progresses. This lemma proves that the discrepancy between these variables across agents reduces over iterations, thus guaranteeing convergence.
Lemma 7 (Iterates Contraction). The following contraction properties of the iterates hold:
X - 1 @ 84+1 122 2 S1 411+4) x112+ +1+
)ai - 1 Ø3 11
11
and [ 11 h (
(1
)|dd** - dd
12
where I and l2 are arbitrary positive constants. Additionally, we have
[|x+11 - x,I 10xx) 4a,
10 lilll + 4a,mm 12.11.
And also,
Ily+11 - - 18
The first inequality states that the deviation of the iterates X from their consensus value 1 @ X (where 18 represents the averaging operator) is bounded by a factor that depends on the previous deviation, scaled by the contraction factor X, and the gradient tracking error. The second inequality bounds the change in the gradient tracking variables h2 between iterations and /. + 1, showing that it contracts over time. depending on the contraction factor and the difference in the gradient correction steps d'+11 d' These two contraction results help ensure that the iterates (both the decision variables and the gradient tracking variables) converge towards their consensus values over time.
Proof. We begin by analyzing the iterates of X(+1- The idea is to show that the deviation of X from its average consensus value 1 & X1+1 contracts over iterations. Define M M In- First for the iterates Xt, we have the following contraction:
|Mx
x 2|
MM 1 & x2)1 < X2||x
1.
(15)
This is because 1 X x, is orthogonal 1, which is the eigenvector corresponding the largest eigenvalue of M, and À max(| Amm Recall that x; xx-1 - a hence,
xx 1 2
Mx a-
(x,-1 04-1 1
(a)
< (1 [x]
8 x 1 +(1++11+ +
2 1/
3 h
1
(6)
(1+1))2 X 1 10x + (1 + 4
)a [
1 h 112
where (a) is because of triangle inequality and (b) is from 15) Next, we analyze the gradient tracking steps. The goal here is to show that the deviation of the gradient tracking variables from their consensus value also contracts over time. Using the update rule for ht we have
h 11
23

---

Published as a conference paper at ICLR 2025
=| M|hh> + - d
10
(h*
d - d d1
<(1 + 1)
18 1 113 (1 +
]|d' - dx - -1@ 2 (d - dx 1)
12
<(1 (1++1)1 12)2111
18
(1
I[
- [11 2 II)(dd d% "1²
12
(2)
3 + 22) 11 x || (1
+
1
||dx
1
(16)
12
where (a) is due to | - (11 2 1 1
From 16 letting 12 1-À we can further have
-
12) 18 h
112
+ (1+
+
) 11
[22
<>|lb>
2
||dy 112
Then we have
hh4 - 16 1 1
(A
| - -dx
(17)
By using | lh4
1 & 12 + n 1 2 and
can immediately deduce that
|
Σ (
dg- + r2||d21??
According to the updating mechanism detailed in
we have
| 111
Mx, 04- 1t h x,- 112
-I(M- 1)x(-1 -1 112
$2 (M- T)x, 2| + 20 1/ 1-
-2 - I)(x, 1 x1)1 20 [h<-11-
<8 (xi-1 - 2 x, 1)12 + 4a 1
t-1 11 11 mm?-mm(hhh 111b=11132 112.
Also,
lly: y1-1l1 = -1P
y1-1l 2| < 1yy-1 3. h/ y1-1 - 5, 11b 11,
where the first inequality holds because || 2 S Sry s S rly by the algorithm setting, implying the non-expensive property.
Lemma 8. Let Ta be defined as (9) Then, the following inequality holds:
|x < 2
This lemma states that the squared norm of the vector x is bounded by r2, which is of the order
0
Proof. By Assumption 2 we have
[Vxf( yo,) - Vx veeyvelll
(xll(x + (x [Vsell
24

---

Published as a conference paper at ICLR 2025
5.0 + (Hoigi = 131 = 00
Jam
and
1 Σ
|
S
S Bi = 00
==1
Here we also prove that
||d V (x No.ell $ VV - (0,000 + (V,00)
< Layy x||x ([xx,l)) S Lay (r22 + + + (y,05 S B2 Ō
and
d fi - V S Lso + (Loryaar) BB 0 Ove
We deduce that
m
4m
Σ Extra + mBB & (1+ (1-A)² B2m.
b+1
Σ
1 1
1
From X1,++1 EVEN, M achi", we have
m
1x.141-x41 -
m
Σ
[M]xxr, - achh" Σ
-
at i
NeN;
PEA:
m
m
M X Σ
M 11-
Ja 00-1hh=-11
K'N
PEN;
m
Σ
-
1
m
| h 111
PEN:
where the second inequality is due to the Cauuhh-Sehwand inequality. Now we have
M
Σ
M
M - (x. x1-1)
PEN:
Xi
Xi,-- (x: - x1
Moreover, we have
Σ
M M
Σ
M (X: -x--1)
PEN.
PEN,
Σ
M
Σ
M
+ 1|xe -x 11-
MEN:
PEN;
M M
M M 81-1
MEN,
PEN.
Σ
Σ
M
Σ
M
m |x; 81-1
PEN:
25

---

Published as a conference paper at ICLR 2025
and
Xg,r Xi,-11 - -(x+- x)11
| xi,1-11² 1 + ||, - -x--112-- 2
Xi Xi,- 8,-1)
1=1
1=1
X - x1,1-112 mm 1 - 111
Then we obtain
M E (M
VEN;
PEN:
2
| xi,--11² + (1 --2)m |x: x1-
2
X - Xi,1-1
1|2 1 (1 -22) m2)ma? |xx
Now we have that
X1,++1 - xx,e|l
1 X2
m
x1,1-111
ma
|| 2
+
a
2 h
A
1
A
1 - X?
| xi.--11
ma | 1 113
2
m
m
a--1
h
4.
b
1
We set \ = 1-x2 + i-x +
16
and have
m
x1,+1
xx.el
X1,1 x1,1-111 11 + >x X1
m
$ X Σ
|3,00
x1
a
< A Bi m
a
X1 Bim3.ji
(t 1) 11
where (1+1)-33/) 3
3r
Bepi3 3, and E az < 3p
1
log(t + 11. Then we have
(14))(
m
m
m
e 2 <2 2
Xi,t - xx,ol + >
|x
i=1
i=1
1-1
< 2t Σ Σ
Xi,
1 2 + 2 > xx,ull
#=0 t=1
i=1
26

---

Published as a conference paper at ICLR 2025
12
s 2X BmmBB
+ > |x91
(t+ (1+1)((1+77t))
i=1
S 2X1 BB + |x??1
>
1=1
which implies |
Σn=
x| 2 S r =0( where To defined in
We now analyze the contraction properties of the iterates x,+1 and h respectively, as generated by the algorithm. Specifically, we aim to track how the differences between successive iterations decrease over time.
Lemma 9.
|x441 X1+111 |
1112
S -(1+)))--1)11x- 10 +(1 +1+ 1
2,11
)a aalllh - 1 1 hill?
where 1 is an arbitrary positive constant.
[ [h - 1 1
|
-18-1 18 1
S ((1 ((1+ 1)]lb & hall + (1 T (L3, ||x+11 - xxll2 + (111g I1?),
where le is also an arbitrary positive constant.
Proof. We start by examining the difference in the updates between iterations for both x, and h
Using the smoothness assumptions (A (Assumption) 2. we first bound the difference between successive updates of dx, which are defined as the gradient of the objective function:
||d[+ - d 2 S L), [|x+1 - x, 2 L7,, Ily++1 yell² s L2, ||x++1 x+11 + L,,, 3 b 112
Applying the results from Lemma 7 we have:
||++1 - X X++1l² ||
<(1 (1 <1+4))7 s x1, +
T, )o 1b
b
1
which reflects the contraction behavior of the consensus steps for the decision variable x,, Similarly, the contraction property for h the gradient tracking variable, follows:
| ++ 1 < 11
<(1 + 11
T 143, ||: - of (1
Finally, we combine the two bounds to obtain the iterative contraction propertics for both x and h
[ 11 || & 1 2
+ 1 2 11 7
- 1 2
[lh(t1 - 18 - 1
< ((1 -1))))))-)(_h33 1 1 12 +
[L3 ||x xxll2 + 27118,111h)1)) (19).
To
Step 4: Choosing suitable coefficients such that the descent of Lyapunoy function well controlled.
27

---

Published as a conference paper at ICLR 2025
The purpose of Step 4 is to identify suitable decreasing coefficients {ar,bu Ct, de and well- chosen averaging parameter 14, such that the descent of the Lyapunov function is well-controlled and can be bounded by summable series. This ensures the algorithm converges under the framework provided by the potential function.
In this lemma, define potential function V2 that tracks the overall progress of the algorithm and analyze its behavior over iterations. We then establish an upper bound on the difference between Ve+1 and V₁, showing that the Lyapunov function V. decreases each step, guided by well-chosen coefficients that control the descent rate.
Lemma 10 (Potential function). We assume that {a,, by, e2 de)) be sequence of decreasing positive constants, where Vi =- [Rt, (n, (xx)) Sol + dellx, @ x, 12 + drae|lb' @
12112 belly: Yi. (x,)]12 + cellve Vi, (xx)]1
V4+1 Vi
11+101
| He (xx C1 1 C2/1x; - 18 & x11 + Cs I1yr y%, (xx)
+ C4 || - Viu. (x+)11 + Cbllb - 1 2 lill Co 1bil1
Vy Xc-1, (xe+1)) || yo (x1,141)
20141
( (ni-Wet pet1 He
+
Th
m
20++1 Ie L
byy
(x++1))1? (Me ML+1 2
m
Rh
y (xx,0t2)l
m
24bb+1
Me Me+1
2
+
ohe 3,
14
6ct+1
pet1 ) Me 1M-Mit1) Hh
2
((Cra llnllliin (XeLtt)
T(siya) Ilries (xxe+1)
1=1
+Gvr
Vy.li
(xi441, (x1=+1))ll
where
0-=
Ctt
arLame
+ 4a,m 6
40,m +
6ct+1 (Krs llvi, (xxWi) + Lvz))
2
20
B,0
Vus
de+ 1044 L3, 4amm,
O4 NeLape +8
6be+1 Uys
60c+1 (Iwi Il (xix))l || + Lu2) )²
C2 a++1 ro2 m Viue
Biog Vpc
+ de+1 () - 1)+
de de+100+111 1.7,,
1
C3 ax 14:10 (Lrnos llve, (xxe))l + 1esres) m
be+1
30t+17t (Eotyrs Vin (xx,i)l + Lstiz)) )²)
3,0
2
Owie
OcT
C++1
C4 d+4l
2
(6b,-1 P9l Psl
6c1+1
(Iv1 l| (xr.e) || + Lvz) 2
C5 4a/
3,03 Jut
1
+
de det1a a + de+100+1 (A -1)+ x d 1.- 4a?.
x
Cs d1410++1
1
L2 fig 35 bit1
[+ (1+
1
[ )
(22)
223
1
88
x
2
Ovmn + Lon
28

---

Published as a conference paper at ICLR 2025
Proof.
V4+1- - Ve
-0++ [(8ee1) (8c+1)) - (x,, (x.)) + (at+1 - (x:))
+ det1 [[|8011 - ② Xx+1
11 ||x: - 18 x, [1-] + (de+1 do)l(xx - 1 @ x,l1²
+ de+1a [||b 1+1 h
|lh4 - @ l1
(de+10e+1 de(r))
11
lidl?
bi+1
ye+1 Sett1 (x(+1) )
||
|
||y:- y1y (xx
+ (bi+1 - be) |1yr1 - vū. (xi))1
Ve+1 V vptti (xe+1) || v (x+) 012
+ (ct+1 - at) 1lve v2. (xx))1
Cr+1
Sait1 [( pc+1 (8++1)) - -fxx,, (x,))
+ de+1 [||x+1
8 Xx+1
11 ||x: - 1 @ xx [|
+ 14+10041
[[lb -1
80 litt112
||h
1 6 h [1]]
+ be+1
Yis+1 Yie. (xix+1)
Σ
|| yi. (xx,,)] 1|
+ Cc+1
Vi++1 - V (xie+1)
I| vi, (xx,)))
1=1
By combining the estimates from the above lemmas, we have
V(+1 - Vi
<ai+1
at / ue (x,)]1 - a23
a? Lo
hi
+
Orp Lo
- xx,e xx
2
2
20
ro Vus
Vue
1=1
m
ar"
(wixar ll (xc,e)l + Lirrac) )² "Iyy,e - Ymu (x),
+ m
1=1
arrL
1 m
Vyi
Vivee V/. (xx,))| + 2apr
m Σ d -
m
yf Xe411 Yies (xe+1)
Yiens (Xe+1)
(e (we Me+1
The
Hh
1
m
1y fiys fiys
2L
(x++1)l1
He+1
27
2 The
m
He
6L2 wyy
+ b11
3rowm || 8ms (xx,)]l
+
||x - xx,4+112 -x,,111,4+111
2
3ro3 o
1=1
1
+
233,
B8
|
2
Jwen + Loiive
24
yiru (xc,.+11)
2)
Ntt Mo+1 -Mott Me
oi Bro
+ G411
Σ
2 no ||vee- - Vi, (Xc,,))1 1=1
29

---

Published as a conference paper at ICLR 2025
6 (Lvi ll (xx,1)l + lv22)
+
lixce x1,++112
+ 3mp
(Liigre Vi (xxxi)l + Liyss) Ilysc - yne (xx,,))
Jehe
6
) 2 [ minl)
((Cr)) || (2810422l + ((sys) |/ (xx,
+
27 1)
+Cv²
Vyrli (Xist (XLeHI)
+ di+1
((1 + (1)AA² - 1))lX, - 1 2 X 1| + (1 + 1 +
Jaiilna 1 @ =2l??
[1
+ di+104+1((1 ((1 + 12)12= - ->)llh - 1 121l2
1
+ d1410041 + b |L ||x(+1 (xxxxxa)) xil1 + ++ B 1 1
Rearranging it, have
Vi-1 Ve
a? Lope
01+104
| pu: (xx)]| ac+1
on
||b& 11
2
20 wu
at
Lebi
+ Oc+1
Xx - xel12
ra Upp
m
(Drwa 1i (xsx))l + Lifre)) Iyea - ypp (xx+))?
+ 0c+1
m
Oer T22 syy
m
m
+ 0c+1
Vive Vie (xx,))l + 20 laer
Ed
d li
m
yy Ntet (8e+1)) /| ype. (Retiil
(u-
+ 04+1
m
Tbe
He
i=1
1
2L Lyya Ily 1111 (x(+1)11
(Mee
M4t1 2
+ 0++1
m
R,
bet1
Σ
||ya, yi. (xx.))1
6b
L2
U/yl
Σ
|
xx,etal?
2
3,03 Vus
bi+1
(1+5 g30
23, Oetine + Lim
B2
24bi+1
Me Matt Me
+
h, Be
i=1
C++1
Vise - -vi (xs.
2
1=1
6c4+1 (Ivr Vivz, (xs;,)l + Lrw2) l|xi, - x1.+1112
+
mos Vec
30e+17h (Eesya llv7, (xx,e)l + Lssyz) ) Ilyes yin (xx,))
+
i=1
30

---

Published as a conference paper at ICLR 2025
m
6ct+1
Me "=-Mett) y ? ((Cm) |/vir (xcatt) /| I(Syys) /1s (XL0+1)
+
oim
+Gv2
Vyli (Xie41: (x1s++))
(11 [11+11)²² 1))[xx - 1 2 x+112+ + (1 + +. Jaiiling & h
+ de+1
+ de+10141(11 + 12)1a= 11)l1h - 8 1
1 + de+ 1e+10041 + (L7 ||x|1 - -x11 + 117 9.
1
Rearranging it, we have
V411 - V/2
s 41+100
V /ur (2x)]1 ac-1
a1
a Laze
2
2
20 pp
anLan
+ at+1 ro por m
|x - 80 2112
1 m
2
I. 0by1
m Σ d
Va,e Vie (xxx))l
201+1000
a
m
(Larya || V/ (xxxe)l + L Lifewa)) ) I| - Vin (xx1))1?
+ ac+1
i=1
6b241 22y
Geo+1 (bvr [va, (xx,))l + Live) ||x,,, x2.t2112
Brog Vue
mo Vec
be+1 Beo 2
3ee+17t (Leyyz Ilvin (xxe))l + L(re)) ( I1ycc - -Yh, (xx,)))
i=1
b+t
1
+
1 Sro
2B3 Jpine
1
B7 > |n 1|2
2
+
m
Ct+l
Vase Via (x
2
Vyyi (x41,, youre (Xet1))
ue4s (x++1) ||
m
(Is
(w- 14t1
+ +.++1
Th.
He
i=1
m 2L 2 Siya
Iy muess (xx+1)112
2
[ie Me+1
+ 0:+1 m
Rh |iniis (x(ettt)
m 24br+1
(ML (Me-Metz)
Me+1
2
The 3r0mm
14
m
604+1
Me Pe- (1-11(11
(CCvslyvnn Viees (x + Tusisz)
Vinee (xx
H
Vyds +Gve
(xx.C+i, (xx,+1)))
((1 + [2)22 1))|x, 8 x111 2 + (1 + 1 Jai b 1 2 hill?
+ det1
+ de410441 ((1 12)x² 1)1lb - 1 60 h221
31

---

Published as a conference paper at ICLR 2025
1 + a1+1 + T. ) ||x+1 xxel + 1 Be11h))))
Since llz (x,,)]l is of order O ((-)),, ) to simplify the proof, we take l| (xx,))l as its maximal value over all m agents at iteration t. By further calculating the terms from the previous result, we have
V - Vi
414100
on Lopu
|1
04+1
2
2
20 4/pe
acLoge
m
+ ac+1
Xx - 1 @ x112 2 + 2a++1au4
dit h
ro?
m i=1
(Loins |l Vie (xx,t)l + Lisixa) )² 2 I|y= Viv (x:) 2
+ de+ 10+1
m
b1+1
3co+171 (Lesgra Vl (xx,)) + ((tys) )
Br
11ye
Vū. (xx))1
Ovne
+ ac+1
Ost
- 1191 ||ve
Vin (x:)]1
C++1
11
Min Vive l|ve Via (xx) ?
m
2
1 bi+1 11+581001 )
m
233 Oein + Iuyn
B3
i=1
601+1 12
604+1
(Lv1 llvie (xS(,e) || + Lv2)
+
+
||x: - xe+1ll 1|
B103
Vuc
Vyfe Xx-11: Frets (ke+1)) 2as+1
[ut pe+1
m
The
201+1
Lesiyally ly (Xc+1)l12 (Iu M+t1" (Mtt)
+
oh
24h++1
Mie (xLet2)l
( (bee - He+t1
Th 3,0
60
M Met1 )
((Cvi //lll/ie (xxeet))
+ Lisive) I1s (Xxen1)
+
1=1
+Cv2
Vyzli (x14411) (x1c+1))l)
+ de+1
(11 + 11)x2 (11+
1))[x, - 8 x: + (1 7, )a?lll 1 8 h4
+ de+10441(11 + 12)x²
11)lb - 18 R4 112
+ d 1e-1a + +
To (43, -eel-xel'' + L2, 83 [b211)))
Then, we obtain the following expression:
V-11 Vv
a, Lopss
a1+104
V (x:)]1 ac+1
at
|
2
2
20
+ at+1
||x - 1 E xell" + 2a1+
Σ d h
ra? pye
+ 0141 m
(Losyall (xx.))l + L (
)2 Ilye yi, (xx)
32

---

Published as a conference paper at ICLR 2025
-
b1+1
Bro
30s+17l
(Liigye ll (xix)) + L1ssz)) 2 )
11se - yis (xx)11
b+11
1 1+ 33
23, Jenu
Σ
m
+ +-um
i=1
+ ac+1
Oct
m
Pys
llve
Vin (xx)]1
ct+1
2
||ve
Vic (xt) ||
6b1+1 Vyy +
Br4+1 (Irv ll (xi,e)) || + TIv2)
+
B10 Pipe
n1.5 tiee
(8 (xt - -1 2 x2 4a; doa 10 lidel?? + 4a h 13)
m
20++1
yy 11 (xe+1)
ypets (xx,++)) ||
pe Met1
m
Ohe
14
20x+1 L 11ya
lly (xc+1)11?
[e Me+1
2
Th
H4
m
24b++1
yieu (xL,+2)
(
Me Het1 2
hn 3,0
ue
6ct+1
M M+ Met1 ) ((Cra Ilyines (xxetz) /| + (((yz) Iiyies (xxe+z)
1=1
Vy.fi (Xie411N (xise1))l) 2
+Cve
(1 [11 (1++2)2²= - 1))lx 1 2 x,112 + (1 + 1 >a?llbb -1 & h
+ de+1
1
+ de+10441(1) + -2))x=12)11-- -1)llh - & 122
+ 11+104111++ 12 (L), || -
xel1 + Lg 33 [b,,1
Then, we obtain the following expression:
V441 Vi
a0+1
1 pr (2
2
at LiLov
6be+1 L
40²m m
Uyy
a++1
3,03 Bm
Vit
60t+1 (Ivz
|| Mi
(xx.0)) + Lvz)
40pm m
|| |
mo
a aoLaa
66r-1 bin
60 (Lrs
|| ir (xx+)) + Liz))
+
a++1
ro?
2
8
3,0 te
x ||x, - 1 1885 x111
1
+
aet m
(Iraas llvp (xxx))l + T2aa))
bet1
3044171 (Iwgyyz Il (xxre)ll + Tisiva) )²)
2
ye -o. (xxill² bt+1 (1 [1 2
1
810 )
23,
88
11b11111
owne + Lives
33

---

Published as a conference paper at ICLR 2025
+
a1-1
O4T
Ct+1 nov))) Iiee -vi, (xx)][2+ 2a
Σ d h
m
6bb+1 Uyy +
L2
Goe+1 (Ivv ll (xx.e) /| + 1vz2
+ 4
|1n
2 h
Beo Vpc
no
20z+1
Vyli Re41,NMiis (X++1)
Mieya (xLe+1)
[e - M6+1
Ohe
Ptt
i=1
m
20 L Siya ly (x++1)11 ( (He H4+1
2
m
Pt
y Vuen (xx,142)
24bi+1
2
Ui uet1
of Bro
Me
m
(14 (1-14t1) G04+1
2
((Czz Vinen (xx,442
Tssyss) I/si (xi14z)
11
Vy (x114218 (x((+1))1))
+Cv2
+ d++1
((1 +1++1222 1)][ 00 x, x + (1
1 )aa hil?
+ d++1a++1100 ((1 + 12)12 1) 1 2
1
+ d14100+1111
+ by
| - x, 12 8 19)1) [T,),
For algorithm 1 with D m de
h&ll"
0, we have
Ve+1 - 1/
11t
V pr (12
01+1
a2
2
of Louue
20
Aa.
6be41 1.2
Bro
4a²m
600+1 (Lv1 ll (xx,)) Lv2)²
110
114110041
(1+TT)
1
12,
4a/m
||
T2
acLame
6b++1 T.2
Get+1 (Iv1 Vv (xxxt)] + Inx2) 2
+ Or+l ro
+8
Bio
me tive
1 -det1 (1++1)x--1) 8de+100+11 (1+
13/aa) 1Ix: - 1- 63 x112
Ts
1
+ (1+110e - (Tatsay 1|, (xxx0)l + T.frez??
b141
3c4+1
(Iwbora llv (xc,a)l + I(wa)) ²)) 1|x 87, (xx))l
3,0
2
Oer
c++1
m1 llve - vÿn (xx))1
+
att1
m
2
66b 12m
60rp1 (Lvi ll (xi,))l + Luz)
+
4a,
BBog Vuee
+ det1
[1
ar + de410041 ((1 + 12) X2 -1)
T,
34

---

Published as a conference paper at ICLR 2025
d1410041
1+ 12)
Li 4a² llb - 1 1 h
+
(d+1acc1
1+
1
Li, B3 but1 (300))))))
(23,
2
1 Ove. + Ludee
B² ))
l1b2) 11?
12
1
20++1
VyJi
(x
Viess (Zet1))
y (xestzi]
(He (Hu- 1et1
m
Oh,
Ht
201+1
Liya ly (x(+1)l1?
Me Me+1
R
24b++1
y me (xxittil
(u-- 14+11 2
[et -1-1
Rn B,0
ue
664+1
(M (--lett) )
((Crllvvin (xx + E(sys) I1 (x5,0_)
+
CCv2 Vydi (x (x8,)11))1)
Then, it holds that
Vi+1 V/
04+100
| n1 (xx) 11 1 1 + C3 Ilye
yin (xx)
+ C4 v
vih, (x:)|| + Csslb's 1 60 12
Co Co 11
20441
Vyfe X (xe+z))
Fitez (xx,44))
( Mc+1
The
F+
20 4 fiyz lly m (8++1)11
(ee Mu+1 2
m
H4
y (xittti)l
m
24h++1
- He
Het1 2
+
oi Br0wm
Me
m
6c++1
He Me+1 )
((Cos Ilvans (xxnote) + ((iye) Ilriee (X(e+1)
+Gvv
Vyfii
(x (x))
where
a
af agLome
+ 4a7m
6b L
Uy1
+ 4apm
6ctt1 (Ivz l| (xx,))l + Lvz) 2
2
20
3,03 vm
T1o5 pm
Pys
1
+ d1+10++1
1
L 4a²m.
12
a.
6br+1
66
vyy + 6c4+1 (Ivz |l (xx,1) || + Luze) )²
C2 = a++1
+8
ro?
Vuu m
Brog
+ di+1 ((1 + 11)2211) + 8d1410441 (1+ Tg L2
1 - (Trpar llvi, (xx,e)ll Tos (Leree Vi (xxx))l + 1(iss) )²)
C 41410u5 m
be+1 Br0 2
30
ovm
35

---

Published as a conference paper at ICLR 2025
C4 a++1 m
acT
1
G++1
2 nhp
[b) lin
+ 60c+1 (Lv1 V Mr
(xxx) ll + Lvz)
C3 = dai
Bro 8ipe
12) - + do+10c+1 (1+ T/² L3, 40,,
+ det1
[+ [1)
al + de+100+1 ((1 + 12) 12
C6 = =d+100+11 1
(1+b)) T2)
1
13,208 -bbt1 1 2 23r0vm )33
bit1
B7
Obve + Iisiie
Step 5: Step-size calculations.
To ensure convergence, we choose step-sizes carefully by setting 4 = 12 = - 1, which simplifies
several terms. Under this setting. we have 1 + +. = 1+ ト/- = T-x and (1 + 11)22 - 1 X 1.
Using these values, we proceed to calculate each of the constants C1 through Cs. which represent various components that contribute the change the Lyapunov function.
Lo
6b(+1 Vys + 4a,m
6CH+1 (Ivr ll (xx,))l + Tww2) 2
C -14+
at
40²m
2
20
3
no VnL
Vue
+ 1 X
d++100+
127.11 4a,m,
04 ae +8
6bc+ 6bi+1 pyl
6ct+1 (Iv1 |l (xx,e) || + Lize) )
C2 a++1 ro?
Vius m71
Bi03 Uue
+ de+1 (X - 1)
de 10+100+1000 I.J., 1-
1
C3 a+ axr = (Eraeys 11 (xx,))ll + 1
bi+1
304+17t (Iebgra Via (xxi)l + Lssys)) )))
3:0
2
C4 a++1
O+r
I2
1/11
C+1
2 "erure
m
60t+1 (bvi I| Me
(xxx)) l| + Lu2)2
Os 4a²
B10 Nime
mio Dime
1
det1is + de41a441 (A- (1+1)+ 1- det1art1bi 4a?
Co = de+1100+
1
17, beti
(1+ Brow )
(1+
1+2B:o0
1
(3.8 Tvue + -uaiue
1
82
Next, we set the unified form as follow:
B. E
B(t B(t+1) 1)--1)
I
.7 Cn bet1
3:0 My.
Ca
at+1
mo Mpe?
De
Lova
ce+1
ce+1
where
C++1
2
C++1
5
cn
bt+1
Br
Vie"
Ca
a++1
Also, we set
7: (t + 1) -/2 3c:
0; (t+1) 33/22 3e14."
at+1 = (t + 1)
b (t + 1) 1) 1/2 4/re"
G+1 (1+ + 1) Dum
d+t (1 1/-8
36

---

Published as a conference paper at ICLR 2025
Gy 11+1)
Ca = (t+
o ppe"
For C1, we have
= -141
at
a Lope
+ 4a,m
6bt 6bt+1
2
20
Br0 Vol
604+1 (Lv1 Vir (xx,,)l + Lvz))
4a/10 m
1- de+
1 L4,, 4a,m
1/100 Oue
O1+10%
1 10-10/ta + 1- A det10442 4u²m
2
20 Via
6bit1anIzyy
40mm m
a++1
Ca
+ 604+1 (Ivl ll (xxx)] Trx2)
Caal+1 Brog
By further simplification and applying chosen step-size settings, we derive:
1)- -1=-(((+)) + 24m(t + 1--1))2- (Treys + (Ivr Ivv (xxx)) + Trv2))
Ci C=
(1+ + -1=-2(1
G Tam Ar B2
L3 (t + 1)377/1 13 p4
+ (t + 1)
+ 4m
/8
20 Vus
1 X
As we can see, the dominant term for C1 is -tt + 1) 5r/2 Bepee, which smaller than 0. This indicates that C1 contributes to the overall decrease in the Lyapunov function.
Next, for C2. we have
On LaLe +
6bt+1 I2 B10g P/
6c1+1 (Iv1 | (xx,e)) + Ivve)
C2 = at+1
+
ro² Vpr
+ d++1 (A - 1)
de+10++110 12,
= =d++1 ro? Vpr m
On Tao
+ 8
attl
6b141arL3
+ 6 (Ivl V (xx,))l + Lxz)²
at
1a00+1310 mm.
+ det1 (2 - 1) +8
d1+100+1113 1.2
Simplifying further, we obtain:
Luy: (t 1351/2 M4 + 1
8L2
C2 (t 1) /8 (A (A-1)
h1
1) 137/8 Bip
rmo? Vzc
- (1 + 1) 1/2 ( (48 + 48 (Lv1 l|v (xx,))l + Luz2²
1
+ Br
The leading term is - (1 + 1) 7/8 ensuring that C2 is negative.
For C3, we have
1
Cs a1+10rr (Lwiers ll (xx,))l + I
m
be+1
3041171
(Lerss ll (xx,e)l + b(syz) )²
3,00..
2
Owee
bi+1 3r0wn.
304+1Tt (Lwyya llv (xcee)l + Lsyyz)
+
2
Joine
1
+ a0+1000-
(Iwways llvi, (xx.))l + Tesico)
m
661+177 (Logga ll (xcx))l + L
1
bet1B107
37

---

Published as a conference paper at ICLR 2025
20
(Lowwa ll (xxxe)l + Lisre)) b Browus
1 1:00mm m
2
6C&+176
(Evsoe li (xxe))) + Lisys)) 2
)
1 1-ca Cn
20++1044
(Evwya live (xxxe)) + I(ree)))
Cn C1 m
bi+1
Bro
2
After simplification, we have:
C3 = 2( (t + 1) 7/2
-7/2 3:0
x - + (1 + 1)- (6 (6 (Tryyo ll (xxe)l + T.Saya) )²
+ 2r + (1+1) 12 (Traag Il (xi,t) || + T.sexa)
Ond m
which is negative as well, with the dominant term -tt + 1/2
For Ca, the calculation proceeds similarly:
201+1 Ore 12
c++1
C++1
C₁ = dx+1 m vy:
11 Vnn"
1 D m
Then
5h C+=
PeL
(1- (t 1) -37/2 1)-31/2
ensuring C4 is negative with its dominant term being - (t + 1) 3r 33.
For Cg. we have
66441
+ 6a4+ (Lvz || (xx,e)l + I 2
Cs = 4a²
B10g vo
1
x dit1az
+ d1+10141 (A -11+ 1- de+10441 4aū
ac+1 4a
191 1.0 th
+ 6 (Lv1 llvllv (xxxe)l + Liz) 2
Co
On
1
1
dit1a} +
de+10/+1 () 1)+ + 1- de+104+13) 407.
Then we have
C = 24(t + 1) 7r/2 Bell Liay + (Lv1 [lvi (xx+))l + I
1 1 1 (t+ (++ 25r 18 32 + (A 1) (t 13r B.pu + 1 L3, (t (t 1)37737//8
4
1)+11)2550
/8 3.
As we can see, Cs should be the same order as the order of -(1 + -113//1 3:148 which is smaller than O.
Finally, for Co, we have
2233 (23
1
Co I 1 12 b,4
(1+ showwn)
Join + L
12 dr+ d1+1011111
-3 Jvme
br+l
+ bet188
Twme
bet1 80mm
Live
Oven
Lovee
38

---

Published as a conference paper at ICLR 2025
Then get
C6 -2 (++ (1+1)-5/20) Wac
Bbm B2
L2, (t+
25r/8
B 1 + 1t+ T/2
Ovie + Lini +
Jeme
Liins
1 11 (1+ 1/2 Blo Vie
As we can see, C6 should be the same order as the order of -(t + 1) 7/2 B., which is smaller than Step 6: Proof of Theorem.
is helpful to find suitable coeffcients 0,+1, b1+1, C++1, d++1 such that C1 to Cg < and all of the sequences involving 14, M++1 (denoted by A B C. respectively) are summable. Achieving this would allow us to conclude convergence using Lemma 10 First, we establish the following inequality for the change in the potential function Vı:
V++ V, S A, + By, + C₁
By the definition of potential function, we get V/2 2 0 for all t. This implies that the potential function bounded from below, and can write:
20
VT S Vo + Σ (A + B C.)
Since the sequences A/ By and C are summable, we can conclude that:
VT O(1) as T + oc.
Next, applying Lemma
we have the following summation over the interval f T' to = 2T' +
27+1
dr+1 Cie
V ur
xx) 12
C1 |1 C2 x - 1 2 21 Ca ||y: - - (x+))l
2
t=
C4
- - - Col
O().
Since the constants C1 through Cg are all strictly negative, the terms on the left- side are non-
negative, and thus, the overall sum remains bounded. Note that E² (1+1) > 2T &
-'-1-1 I-s [T 1)
Now, by lower- boundigg the coefficients, according to different step size strategies and the coefficients of Lyapunov function, we can get the estimates on
min OSES
(IVV pc (&1) |
||x;
x212
||ye yt, (xx)]²
l|ve VjJ. (xx)
& h
By choosing suitable upper bounds for the parameters and 7. conclude that the desired con- vergence holds, completing the proof. To further lead the convergence rates as measured by the KKT residual, due to the optimality of yt, (x,) and the definition of v (x.) there exists a positive constant C. independent of I, such that:
KKT Ve)
<C ( (x:)11 + 1|x: 1 xxxx 1|y. vi. (xx]]²+ + l|ve vh. (xx))l + p3
D SUPPORTING LEMMAS
Now, we present the technical lemmas that would be useful throughout our main result.
To establish the convergence result of DUET we first characterize the Lipschitz continuity of y (x:)
in x; and v (x:) in x,, without any boundedness assumption of Jy Yz).
39

---

Published as a conference paper at ICLR 2025
Lemma 11. Suppose assumptions holds, the the follow statement holds.
(a) For any i E [m]] the function yi (xs) is Lipschitz continuous in X i.e, for all X;, X/+
Luyy |xx; xill,
(x;) (7(x1)1 -
Jeti
where both Luys pb + (1 Layy and Jve mo + (1 1))o 9. are constants,
(b) For any E [m]] the fimction v (x:) satisfies
V Vy (x,, y (xx))
(x,) = V Un (x.. (xx,)
Vy. (xx,
J
and for all Xi, x/y
v (Tvall ( Tuv2)
|xc; - x/1l,
6n
where both Lv1 = Lessa Lupss + I and Liz == L lige Luns + ligs Ss are constants.
Proof. (a) By the optimality of yip to LL problem, we have V (x), y (xx)) = 0. Thus y (x()))
(x,, (x. (x.))
+ (y y (x)) Vy (x, y (x))) = O.
Multiplying the above equation by (x:) (7(x), by the o. strongly convexity of (x,xx)) and buy -moothhees of (: y)) we have
1 yy (x:) (x)
(x
(x,) (x4, -1x)) xx
Tupy | x4I1 (x:)) (x))l-
Then the conclusion follows immediately from the above inequality. (b) First, by the Tw strongly convexity of (x, and Cauchy- -Shhwarz inequality, we have
Tyn (x) - (xi), V2 yy Uu (x,, (x.)) (x.))
(x:), Vy (x. y (x:)) (x) (x:))
which implies the conclusion.
Second, the definition of vī (x:) implies that Vyy My (x:, (x))) (xx)) VyJi (xi Thus
V th (x4) (x)( [x,)
Vyfi (x y. Vy.i (x,,
+ [ 2h (x,, (xx) VA
(x,).
By (a), the ov.- strongly convexity of (x..)) and Lipschitz continuity of V Vy and VyJi we have
ov (x,) (x))l
L ||x: xill + L (x:)) - (x+ii)
(x+))l (Troyyr ||x; xx1l Troyua Iy (xx) -y (x))l)
|2 -x1Il (117( (Leyya + own Lessnn Liiy + owrlessss>
which implies the desired result.
40

---

Published as a conference paper at ICLR 2025
Next, we have lemma that characterizes the smoothness of (x:) fi (x,, y1 in x,, without any boundedness assumption of (x,,, Yi), where (x;))) Vxfi (x,, (x Vay oh (xx)) (x,).
Lemma 12. Suppose all assumptions holds, for any i [m]] and x; E ERP: we have
[ V (xx)] (Ca1 [1)) 0g
+ C42) ||2, xill,
where both C#1 =- Libns Lussa + Luns (bugsr + Luwaya) Je + Lix 2z and Caz == Lig S
Luys (Liign + (isixa)) our Lis o are constants.
Proof. Recall that vx(xx) = [V by u/ (x,, (3,,7((x))) Vyfi (xx))( and v = Vxfi (x,, - [V 1//0 (xx: (xx))) v (x:). Thus
(xx) - V (xx) = =Vxfi (x:: y (xx)) Vx.f (x (xx))
+ Vyy Ui (x/,, y (xx)) vi (xx) - 22 ( (xxs).
First, by Lipschitz continuity of Vxli, we have
Vxx (x(i)) - Vxfi (x (x4)) s S |x; - xx-l + Li (x,))x)) - y (xx)
Second, note that
V Ry (X,, f/ (x()) vi (xx) [V the (xs, y (xx))) (xx)))
= V Uh (x,.)) yp (x4)) [v] (x() - (x:)]
+ V // (x4, y (xx)) - Vxy the (x; y (xx)) vx
Thus, by Lipschitz continuity of 2 yy // and Lemma
we have
vi (x,)]l [| Uu (x/, (x<)) v (x)) [V2 th (x,, (x,
Layy v (x²) v
(x))]l (L |[x xill + Lorzyz (1yx((x))) y2 (xx)I)
Lags (Lw1 | (x:) + Liv2)
||xc x11l
+ +lv%((x;) (Leny ||x x:ll + Luw (1) yi (xx)))
where Lay is constant given by Layys pllthass + (1 (1) [ It implies the desired result since
Legs Iii + Inpaya Leyy Us + Letryr 2 = I2ggns Innaaa + Lunn (Irayo + Inpaya) oen + Tuway 2 and
Buys Live + Iosivc benn oen + Lifi og = Lagn Tsp + Lonn (Iepigs + Lipica) Jwn + L.sime ppp
Next lemma characterize the smoothness of (x,) and (x,)) in i when the LL problem has multiple minimizers.
Lemma 13. Suppose assumptions holds, let 0 S HS 1/2 and μ² < 24,, the follow statements hold. (a) For any i [m]]
(x.) - -(x((( (xx) < Vyhu (x,, y (xx))
|/ - 11
y (xx)
Tb:
The
41

---

Published as a conference paper at ICLR 2025
(b) For any i E [m]]
-v)( (xx))l =
Lrive) y (xx)]
(n')2
+ V (xi, (x(,,)) 1l 1e-n" 1²'
(10)2
where both Cv1 = 2 [Iiigga + Iigiys)) /0h, and Cv2 == 2 (Liiyo + I ) /oh, are
constants.
Proof. (a) Recall that yi = (xi) satisfies i V Vi,d + (1 Vygi Vi,p) 0. Thus (n- 1 V (i,) + pl [V (xx, Mi,a) - Vyhi (x.
+ (4' u) yyi (i.) + (1 ve) Vygi (i,) - y (xi N 0,
which imply that
n¹ [Vyhs (i.)) - V Vy 3 ]] + (1 - n²) V (xx) yi yi.e)) )} P I- Vyh (i.)) = (p' yy (xi:
= =(4' 1i) Vyh (x.. (4' 1))
Since hx(x;;,) is -he strongly convex, we have
(Vyhe (i.) Vyrhe (i.)) Niw - vip) 2 Th, 11yi. - -Vi Similarly, since gi (x;,.) is convex, we get
yy (xs, (i,p) - Vygi (x;; Vipe Ni. - sipp ) 2 0.
Combining the above inequalities, we have
0 S plon,,lli I1y. -i. < 1 14 (Vytii (Xis Miu) Pi. - viw)
(1-1)
Since 0 S 4 S 1/2, we get 1/(1 - 11) S and then
n'on, yi 112 s 2 (xi: 1l 11 - w'll 11yi - Virrll
= 211y2, || - w'll 11 - -i
which implies the desired result. (b)The definition of vi., = (x,) says that J (x))) = Vy (xi, yz (x:)). Thus we have
Vyr (X), (w)) (Vī Vine)) + (n - te (x;, Vxc)) vi
= -yyf (x,) Vi (x..)
Multiplying the above equation by Vi Vinus by the oup-- strongly convexity of th (xx, :), we get vhuell
oewll Vi 112 < V by (xx( vio) Vyy (x., y22) 1ll ||v IIvi
+ Vy (x,) - Vy Vi,e)) lIv - viaalll-
Note that by the definition of 1/2 we have
Vyy (X,, (i,r) =(1- n²) V2 / hi vi,u) + n¹ [V hi (X,, - -Vzyh: (x:. ) (4' 14) V gy (xir (1 - n²) [V Pi (xi. Vyy (xi, )i
V VyyVulls Uu (xk:
Since μ¹ s 2p < 1, we get
ow, 11 vi
42

---

Published as a conference paper at ICLR 2025
LMwy + L Ile - H² l| + (Llusys + Leneee) lrri - -ii l1vi + EsyallDin - -Vipel
(Tiaagra + Ingyys)) | + [ssrya] I1yi, Nipell (Imaga + Iigays) || 11 - 1'll-
By (a), since obey = ono on, when on: = O, we have
2 211y;
110 اil (e²)²
li - -viprll S (Lussga + Lggiors)
lI + [iaa
Lheya + +Lgeys)
1K v²
Vi
The
H
Since μ² 2p, Lemma 11 limplies that
V yy yZ uoh
2 fi (x)
p p'llvi, S n²
The
Hence get the desired result.
Finally, we present the lemma that characterizes the Lipschitz properties of the approximate gradient by using (x,, y:)ll I f.o from Assumption 1.
Lemma 14. For any i [m].
[V - Vf(((,,))) - L3,, ||x; x,11 + L,3,,, lly; yill",
where 1,, 412 + 4I p o 1yyn
+ +4
1/ 12 1in + 2 1/ o Da and D7
AL2 Sixa
+ +AL2 4
vyy oi
1 12y + + 12 12
+ 412 1 -12
1/y1
vay2"
Proof. Recall that
fi(x,y))) = Vxfi(x.,,) (x) V Wi (x):y,) Vas
where V. e 1 is define as:
v
Then, we have
V [V - v()()
S 2|| Vxf y1) Vxfi(x
+ 21/V 2 (xi, yi) V (x,, y:) (V,
V2y oi (x 1V2 yyy
$ 2/ ( y1) Vxfí
2// (xi, y:) V
+ V xy (x)
2 y1)
(x)
V yy d (x,,
Then we have the following:
[xx,)(x))))) Vx v!)l < Lin ||x - x112 + Lisi lly: y'll-
Vy.f(x((. (V,
s Liy ||x; - x(il I lly: y'll
Furthermore, we have
|| V th (s)
- V2 vi (x(x < Tenan ||x; - -x,1 + Ixway 1yy: - -Vlll-
43

---

Published as a conference paper at ICLR 2025
V th (x).))) - V ti (xl, y'll Lewis ||x; - -x/ll + Luyse l y'll
Assuming that || V (xi, y:)1l S Luy and [xx S Lig. then we have
| (x;, v:) v(((((,)\\1''
- 4LL,,, /:x1 ||x,- - x'11
+ + Jina lly: - y'll2
1 1.g.y. ||x: x ? Al o²
1
+ 4
4L oyy
1.),yy lly: - y'll
1
+ 4 03
1 Pay
||x xx11
+
1s0
L Vayz
lly: - -''ll
1
+ 4T, 1.10 O'
12 1
|x;
-x1I| 4T 4
12
T lly: yill
ob
Thus we have
VV v.) (x( x2)l
1
1
1
2 (4L) fim + +44
-े
13
+
4
1.0
Leny
+ 442yy
1.0
L3 )wm ||x; - xX,l
Vp
1
(Iva + 4L2
Siva
vy1
0 4//
+
4/-
L2
1:0
L2
Vayz
+ 4L2
L2
00
L2 paya) lly: -1ll
- 1,7,, ||x - x|11 + 127,0 11yc-I''1"
where
1
1
1 L2 Li
1/, = AL2 fix1 + +L
Viyi
siy
+
4
L3,
Vxay
+ +4 12
1
1
f:2 = 4I,
fime
4
oz
L2
fiya
+
4
1/o
I2
Uxyz
+ AI2
110
o.
E ADDITIONAL EXPERIMENTAL DETAILS AND RESULTS
All numerical experiments were conducted on MacBook Pro equipped with an Apple M3 Pro chip, featuring 12-core CPU with 6 performance cores and 6 efficiency cores, and 36GB of memory.
E. A PEDAGOGICAL EXAMPLE
In this section, we present the results of a pedagogical example using the DUET and DSGT algorithms. For the DUET algorithm, set the LL learning rate to 0.005, with p 1 and
1 For the 10
DSGT algorithm, the LL learning rate is set to 0.001, with p I5 and 1
40
The following figures illustrate the norm of the variables x and y during the optimization process.
E.2 DECENTRALIZED META-LEARNING PROBLEMS WITH WORLDWORLD DATA:
In this section, we present more details for decentralized meta-lea problems with World Data. At each node, we construct neural network classifier comprising input layer, single hidden layer with 32 neurons using a sigmoid activation function, and a linear layer as final output layer param- eterized by 8. The hidden layer parameters x shared across all nodes to ensure global consensus, while the output layer parameters & are tne-tumed locally to adapt to the specific data available at each node. The objective functions f. and 9i are: fe(x, 0) (igg) by In(y, (x, 0; sty)) + 3 [[01|] and g; gx(x, 0) = Eisg (sgg.ba)) D, bij In(y, (a, 0; st))), where (sig, bij) represents the j-th sample at node i, with 8tj as the feature vector and bi as the corresponding label. Here, = 0.1 denotes the regularization coefficient, and yj (x, 0; 8t5) denotes the output of the neural network.
44

---

Published as a conference paper at ICLR 2025
DUBI Gim1
OUTT. (770
BLET 07-0
0607: STm1
E52T 6Tm1
0561: (7md
D501. 01eg
Time(s)
Timels)
(a) The norm of
(b) The norm of
Figure 4: The norms of x and y.
The decentralized stochastic gradient descent (DSGD) approach is used as baseline for i.idd case that updates 0 first by gradient descent and then uses the updated 0 to calculate the gradient of subsequently updating x via SGD.
We compare the performance of DUET and DSGT in both i.i.d. and non-i.i.d settings. Figures and 6 iillustrate the train loss and accuracy results for both settings.
DUST
3.8
DMOT
DA0D
2.55
2.00
DUTT. ESGD
0.52
260
400
666
302
1008
235
402
2020 cde
602
(a) Train loss.
(b) Train accuracy.
Figure 5: Comparisons between DUET and DSGT in the i.i.d. data scenario on the meta-learning problem with 5-agent network on MNIST.
DIET
06
BIET
BAAT
1-8
633
DUST GT
1.7
83
250 530
730 18E0 1250 1500 3750 3000
250
3300 3750 2000 500
750
3300 3350
(a) Train loss.
(b) Train accuracy.
Figure 6: Comparisons between DUET and DSGT in the non-i.i.d data scenario on the meta-learning problem with 5-agent network on MNIST.
In Figure the DUET algorithm demonstrates superior performance by achieving the highest training accuracy, along with fast convergence. For the non-i.i.d. case (Figure 66), the algorithms with gradient tracking handle the heterogeneity the data well, with better performance.
Figure shows shows the label distributions of data heterogeneity across different nodes, highlighting the strong non-i.i.d. nature of the data used in our experiments. This visual representation of non-i.i.d. data distribution provides clear understanding of the varying degrees of heterogeneity.
For a 10-agent network (Figure 8) and 50-agent network (Figure in the i.i.d case. DUET continues perform effectively and demonstrates the best performance among the tested methods DSGT and
45

---

Published as a conference paper at ICLR 2025
Agent
Agent 2
Agent 3
Agent 4
Agent 5
Count
0123456789 Labels
0123456789
0123456789 Labels
0123456789 Labels
0123456789
Labels
Labels
Figure 7: Label distributions of data heterogeneity across nodes for non-iid case on the meta-lcarning problem with a 5-agent network on MNIST.
baseline DSGD, maintaining robust convergence and accuracy even in larger, more complex network settings.
DUST: 1
DSOT: UT
35
Trah Accurscy
2
1,93
LISE DAG 19SE
1.00
03
0.89
053
0100
E500
E5CD
250
500
L8B6 1906
2000
530
2000
01
500
1500
3526
2006
(a) Train loss.
(b) Train accuracy.
(c) Test accuracy.
Figure 8: Comparisons between DUET and DSGT in the i.i.d. data scenario on the meta-learning problem with 10-agent network on MNIST.
122
BUET AT
B567.
1.75
Trol Accunsyy
1.32
0.
1953 LOSS
0.0
5.75
0.53
DSKI
1000
1000
530
2000
1500 2000
500
3200 2500 2000
(a) Train loss.
(b) Train accuracy.
(c) Test accuracy.
Figure 9: Comparisons between DUET and DSGT in the i.i.d. data scenario on the meta-learning problem with 50-agent network on MNIST.
The following table summarizes the parameter settings for the DUET, DSGT and DSGD algorithms under both i..dd and non-i.i.d. cases, illustrating the diverse configurations tested in our experiments. E.3 DECENTRALIZED HYPERPARAMETER OPTIMIZATION WITH REAL- WORLDW DATA:
In this section, explore the hyperparameter optimization problem, which is formulated as bilevel optimization task. Specifically, we employ softmax regression (with parameters y;) as the classifier and introduce hyperparameters to weight samples for training.
Let Dar.; and D as the training and validation sets for agent i. We define E(y;; uy vi) as cross-entropy loss function, where y; denotes the classification parameters and (u: vi) are the data pairs. The LL problem minimizes the sofumax regression loss over the training dataset, and the LL objective function is formulated as follows: (x, y:) E(u, (i..., [x(x)) eyy u, v.), where x; is the hyperparameter that penalizes the objective for different training sample.
Simultancously. the UL problem aims to improve the performance of the regression model the validation dataset by fine-tuning the hyperparameters. The UL. objective is defined as:
46

---

(0.5, ;) Published as a conference paper at ICLR 2025
Setting
Algorithm
UL Learning Rate
I.I. Learning Rate
Parameters (14, p)
DUET
10
0.01
(0.1, )
III
DSGT
0.5
0.00001
(0.5, +
DSGD
0.01
DUET
0.1
0.0001
(0.1, +
non-lII
DSGT
0.001
0.001
Table 3: Parameter settings for DUET, DSGT, and DSGD under iid and non-iid conditions the meta-learning problem on MNIST.
u, u, v.) + - p(x.(xx))) (x.)). where 10 is the reg- ularization parameter. This regularizer is non-convex and is applied in distributed manner. To evaluate the proposed method, we use the FashionMNIST dataset, which consists of images of clothing categories and serves an alternative to the classic MNIST dataset. For each agent, the dataset is split into training, validation, and testing sets, each containing 5000 samples. We compare the performance of DUET and DSGT algorithms in terms of test accuracy and Fl score, utilizing 10-agent communication network with a connection probability p. 0.5.
yi) = (. (x,);::
As show in Figure TO the analysis of F1 score and test accuracy reveals similar trends across the three algorithms, indicating consistency between the metrics evaluating performance. DUET achieves the best results in both F1 score and test accuracy, with the fastest convergence and highest stability across epochs. DSGT follows closely, showing competitive performance but slightly behind DUET. In contrast, DSGD, which lacks gradient tracking, exhibits slower convergence, lower overall performance in both metrics. These results highlight the effectiveness of gradient tracking in DUET and DSGT, with DUET emerging as the most robust and generalizable approach. The similar trends in FI score and test accuracy further validate the reliability of these algorithms' performance decentralized optimization.
0.7
0.8
045
0,04
0.3
SUFT, 07
TUET, 6T
15
L25
175
75
LE5
L75
Epochs
Ehochs
(a) Test accuracy.
(b) F1 Score
Figure 10: Comparisons between DUET and DSGT on the hyperparameter optimization problem with 10-agent network on FashinMNIST.
The following table summarizes the parameter settings for the DUET, DSGT, and DSGD algorithms on the hyperparameter optimization problem with 10-agent network on FashinMNIST.
Algorithm
UL Learning Rate
LL Learning Rate
Parameters (14, p)
DUET
0.001
0.1
(0.1, !)
DSGT
0.01
(0.9,
DSGD
0.01
0.01
Table 4: Parameter settings DUET, DSGT, and DSGD on the hyperparameter optimization problem with 10-agent network on FashinMNIST.
47


Reviews:
[{"review_id": "4hEgVd0EkT", "reviewer": "Reviewer_Psor", "summary": "This paper addresses decentralized bilevel optimization (DBO) in multi-agent systems without relying on lower-level strong convexity (LLSC), a common but limiting assumption. The authors propose DUET, a novel single-loop algorithm that introduces diminishing quadratic regularization to the lower-level objective, thus bypassing the need for LLSC. DUET achieves convergence to an approximate KKT-stationary point with a defined iteration complexity and incorporates gradient tracking to handle data heterogeneity across agents. This work is the first to address DBO without LLSC in decentralized settings with heterogeneous data, with both theoretical analysis and numerical experiments supporting DUET’s effectiveness.", "questions": "Could you provide experimental results on other problems or datasets? This would help further demonstrate the effectiveness of the proposed method.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1 The paper is well-written, providing clear explanations in the methodology section where each step addresses specific challenges, along with comparisons to existing problems and methods.\n\n2 The authors compare the convergence rate and other results, clearly demonstrating improvements over current methods.\n\n3 They propose using approximate KKT stationarity as the convergence measure for DBO solution quality, offering a detailed analysis of the convergence rate based on this new measure, which will aid in further research on this topic.", "weaknesses": "1 The real-world data experiments are limited to decentralized meta-learning problems on the MNIST dataset, which I believe may not be sufficiently comprehensive.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7AaM5dBDEx", "reviewer": "Reviewer_KZ3e", "summary": "This work presents a decentralized bilevel optimization (DBO) algorithm, termed DUET, designed to solve local bilevel tasks in multi-agent systems without requiring a central server. Unlike traditional DBO methods that rely on the lower-level strong convexity (LLSC) assumption to ensure unique solutions and a well-defined hypergradient, DUET eliminates the need for LLSC by introducing diminishing quadratic regularization to the lower-level objective.", "questions": "Please refer to the Weaknesses. Additionally, the readability of this work is quite poor, with an excessive number of notations. Could you improve the manuscript’s readability and overall presentation?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "1. A single-loop algorithm for LLSC-less DBO is proposed in this work.\n\n2. The proposed algorithm can be used to handle the challenges of consensus errors in DBO with data heterogeneity.", "weaknesses": "After reading this work, I have some major concerns.\n\n1. What is the need for this algorithm in the ML community? This question arises from two main points: 1) Although this work avoids the strong convexity assumption, it still relies on the convexity assumption, whereas objectives in ML are often non-convex. Could you provide additional theoretical analyses that do not depend on convexity assumptions? 2) This work emphasizes the deterministic setting of the algorithm. While the deterministic setting is indeed important in optimization, I am curious about the challenges in analyzing convergence rates under a stochastic setting in the proposed algorithm. In ML, stochastic gradient descent is far more commonly used than deterministic approaches.\n\n2. The relaxed stationarity (KKT-stationarity) is employed in this work without adequate justification. It is essential to provide a clear rationale for this relaxation, as it may result in significantly different solutions compared to the original problem. The stationarity measures are somewhat different from the traditional bilevel optimization works.\n\n3. In Corollary 2, in addition to discussing the number of communication rounds required for the proposed algorithm to converge, it is also essential to analyze the number of bits needed during this process. Can you provide some comparisons about the communication complexity between the proposed method with the existing distributed bilevel optimization methods in the experiments?\n\n4. The experimental results are not sufficiently convincing, as only a limited set of results is provided. Additionally, the experiments are conducted on a small-scale distributed system with only a few clients. I have concerns about the scalability of the proposed method, especially given its deterministic setting. Specifically: 1) Could the authors provide additional experimental results on a larger-scale distributed system? 2) The tasks addressed in the experiments are quite limited. I am curious if the proposed algorithm can be applied to more complex tasks, such as bilevel NAS (e.g., DARTS).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lid0E94xSJ", "reviewer": "Reviewer_D8W2", "summary": "To address the limitations of most existing decentralized bilevel optimization (DBO) methods, which predominantly rely on lower-level strong convexity (LLSC), this paper proposes a single-loop DBO algorithm named Diminishing Quadratically-Regularized Bilevel Decentralized Optimization (DUET). This algorithm circumvents the necessity for LLSC by incorporating a diminishing quadratic regularization into the lower-level objective. DUET achieves an iteration complexity of $\\mathcal{O}(1/T^{1-5p-\\frac{11}{4}\\tau})$ for approximating KKT-stationary point convergence under more lenient assumptions, where $p$ and $\\tau$ serve as control parameters for the lower-level learning rate and averaging, respectively. Additionally, DUET integrates gradient tracking to effectively tackle data heterogeneity, a significant hurdle in DBO scenarios.", "questions": "1. The update mode of Algorithm 1 is similar to the algorithm of [5], so I want to know the distinctions between these two algorithms. Furthermore, I am curious about whether the step of updating the optimal multiplier mirrors the step of solving the linear system within the hypergradient, given that the descent direction for the multiplier $v$, as proposed in this paper, aligns closely with the gradient descent step used for solving the linear system in the hypergradient. Considering this, I question whether the assumption of boundedness concerning the multiplier $v$ and the resolution of the linear system presented in Theorem 3 can be consolidated into a singular assumption.\n\n2. The rationale behind the utilization of the projection parameters $r_v^t$ and $r_y^t$ remains ambiguous (line 301).\n\n3. The definitions of $\\otimes$ and $\\bar{\\beta}, \\bar{\\mu}$ are not clearly articulated (lines 347 and 362).\n\n4. To enhance the understanding of Theorem 5, a comparative analysis with other algorithms is recommended.\n\n5. For other questions, please see the weaknesses above.\n\n\n[5] Liu, Risheng, et al. \"Towards extremely fast bilevel optimization with self-governed convergence guarantees.\" arxiv preprint arxiv:2205.10054 (2022).", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper proposes DUET, a single-loop algorithm that integrates gradient tracking and consensus updates to avoid the computational complexity of conventional double-loop structure in bilevel optimization while ensuring convergence in decentralized settings with data heterogeneity, which is the first algorithm with provable convergence for DBO without LLSC.\n\n2. Without gradient heterogeneity assumptions, the proposed algorithm overcomes the challenges of consensus errors in DBO with data heterogeneity, ensuring agents can synchronize their updates effectively without relying on LLSC.", "weaknesses": "1. My primary concern is the presentation of this paper. For instance:\n\n1-1. It is imperative to delineate the feasible region for $p$ and $\\tau$ in line 81;\n\n1-2. The definitions of communication costs and communication complexity must be elucidated in lines 105 and 117;\n\n1-3. In line 138, it is noted that several methods exist which offer enhanced complexity solutions for simple bilevel problems, as evidenced by references [1, 2, 3, 4];\n\n1-4. The formulation of the decentralized bilevel optimization problem should be introduced earlier in the paper, ideally in the Section introduction;\n\n1-5. A precise definition of $\\nabla \\mathcal{L}$ is essential and should be provided in line 231. Furthermore, given that $\\nabla \\mathcal{L}$ is a matrix (since $x$ may be a matrix), it is crucial to specify the type of norm to be used (F-norm or 2-norm); moreover, similarly, the definition (vector or matrix) of $\\nabla \\Phi$ in line 347 is also important.\n\n1-6. The definitions of $x_{i,t}$ and $y_{i,t}$ remain ambiguous in line 242. Here, I assume that these represent the vectors $x_{i}$ and $y_{i}$ at the $t$-th iteration;\n\n1-7. The explanation of the solution $v_{i,\\mu_t}^*(x_{i,t})$ to the linear system and the multiplier $v_t$ could potentially lead to confusion among readers.\n\n1-8. The citation format in the References section is incorrect. For example, the second reference and the reference on line 557 lack the publication location of the article, while the reference on line 574 omits the article's page numbers.\n\nTypo:\n\n1. line 402, \"for all $k$\" should be \"for all $t$\".\n\n[1] Merchav, Roey, and Shoham Sabach. \"Convex Bi-level Optimization Problems with Nonsmooth Outer Objective Function.\" SIAM Journal on Optimization 33.4 (2023): 3114-3142.\n\n[2] Chen, Pengyu, et al. \"Penalty-based Methods for Simple Bilevel Optimization under H\\\"{o} lderian Error Bounds.\" arXiv preprint arXiv:2402.02155 (2024).\n\n[3] Cao, Jincheng, et al. \"An Accelerated Gradient Method for Simple Bilevel Optimization with Convex Lower-level Problem.\" arXiv preprint arXiv:2402.08097 (2024).\n\n[4] Samadi, Sepideh, Daniel Burbano, and Farzad Yousefian. \"Achieving optimal complexity guarantees for a class of bilevel convex optimization problems.\" 2024 American Control Conference (ACC). IEEE, 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RQXnmMeP8I", "reviewer": "Reviewer_7zfE", "summary": "This paper considers decentralized bilevel optimization (DBO) without using lower-level strong convexity (LLSC). \n\nTo tackle this problem, the authors first propose a novel convergence metric called LLSC-less convergence. On top of this, they propose DUET that uses local updates and gradient tracking based communication updates to solve the DBO problem. The authors further provide a rigorous theoretical analysis of DUET, and obtain a finite-time convergence analysis which reveals the number of communication rounds to find an eps-stationary point is O(eps^{-3.5}) and O(eps^{-2.5}) under different settings. Besides, the authors also provide an extension of their algorithm -- DSGT, in which an additional assumption, upper-level strong convexity, is imposed. Similar results are obtained for DSGT. \n\nSome numerical experiments are conducted to showcase the efficiency of the proposed algorithms over existing ones.", "questions": "1. Can the authors provide some insights on the lower bound of this problem? For example the current O(eps^{-2.5}) seems not to be optimal, and it would be interesting to study the lower bound of DBO under the LLSC-less metric.\n\n2. Is it correct to claim the complexity results are O(eps^{-3.5}) and O(eps^{-2.5}) in Corollary 2 and 4? Technically speaking \\tau cannot be 0 and thus the logic \"\\tau --> 0 leads to -3.5 and -2.5\" complexity seems a little bit problematic.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. (Weaker assumptions) The assumptions used in the paper are standard and do not impose strong convexity in the lower-level problem.\n\n2. (Novel metric) The authors propose a novel metric to characterize the convergence of DBO problems without LLSC.", "weaknesses": "1. (Novelty of the theory) Although the proposed metric and algorithm are novel, the analysis used to obtain the final convergence is quite standard in distributed optimization and bilevel optimization literature.\n\n2. (Simple experiments with incomplete context) The experimental settings are relatively simple -- A Pedagogical Example and MNIST dataset are so simple that they may not well represent the non-convex nature of lower-level non-convexity in many bilevel optimization problems. Some important details about the experiments setup are missing -- for example it would be better if the architecture of the neural network in the meta learning experiments is reported, otherwise the readers need to go through the code to figure it out.\n\n3. (Unclear Table 1) Most of the algorithms in Table 1 use the eps-stationary convergence metric while this paper uses LLSC-less. However, this is not directly visible in this table. Meanwhile, the centralized settings may be moved to the appendix, as this paper mainly focuses on the distributed setting. \n\n4. (Misleading name) The name of the extended version of DUET, DSGT, might be a little misleading -- as it refers to distributed stochastic optimization with gradient tracking in the distributed optimization literature. It would be better if the authors could use another name for the extended version of their algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)