Problem-Parameter-Free Decentralized Bilevel Optimization
Authors: Zhiwei Zhai
Wenjing Yan
Ying-Jun Angela Zhang
Venue: NeurIPS 2025 poster ()
Keywords: Decentralized bilevel optimization
problem-parameter-free
adaptive stepsizes
single-loop
Primary area: optimization

Abstract: Decentralized bilevel optimization has garnered significant attention due to its critical role in solving large-scale machine learning problems. However, existing methods often rely on prior knowledge of problem parameters—such as smoothness, convexity, or communication network topologies—to determine appropriate stepsizes. In practice, these problem parameters are typically unavailable, leading to substantial manual effort for hyperparameter tuning. In this paper, we propose \textbf{AdaSDBO}, a fully problem-parameter-free algorithm for decentralized bilevel optimization with a single-loop structure. AdaSDBO leverages adaptive stepsizes based on cumulative gradient norms to update all variables simultaneously, dynamically adjusting its progress and eliminating the need for problem-specific hyperparameter tuning. Through rigorous theoretical analysis, we establish that AdaSDBO achieves a convergence rate of $\widetilde{\mathcal{O}}\left(\frac{1}{T}\right)$, matching the performance of well-tuned state-of-the-art methods up to polylogarithmic factors. Extensive numerical experiments demonstrate that AdaSDBO delivers competitive performance compared to existing decentralized bilevel optimization methods while exhibiting remarkable robustness across diverse stepsize configurations.

Problem-Parammeer--Fre Decentralized Bilevel Optimization
Zhiwei Zhai Wenjing Yan' Ying-Jun Angela Zhang
Department of Information Engineering
The Chinese University of Hong Kong {zz024, wjyan, yjzhang)@ie. cuhk. edu hk
Abstract
Decentralized bilevel optimization has garnered significant attention due to its critical role in solving large-scale machine learning problems. However, existing methods often rely on prior knowledge of problem parameters- as smooth- ness, convexity, or communication network topologies determine appropriate stepsizes. In practice, these problem parameters are typically unavailable, leading substantial manual effort for hyperparameter tuning. this paper, we propose AdaSDBO, fully problem-parameee parameter-free algorithm for decentralized bilevel optimization with single-loop structure. AdaSDBO leverages adaptive stepsizes based on cumulative gradient norms update all variables simultaneously, dy- namically adjusting its progress and eliminating the need for problem-specife hyperparameter tuning. Through rigorous theoretical analysis, establish that AdaSDBO achieves convergence rate of Ô (+), matching the performance of well-tuned state-of-the-art methods up to polylogarithmic factors. Extensive nu- merical experiments demonstrate that AdaSDBO delivers competitive performance compared to existing decentralized bilevel optimization methods while exhibiting remarkable robustness across diverse stepsize configurations.
Introduction
Bilevel optimization is powerful framework widely applied in machine learning, artificial intel- ligence, and operations research [Camacho- Vallejo et al.) 2024, Caselli et al.] 2024). In bilevel optimization, the objective is to optimize function that itself dependent an optimization problem, creating a hierarchical structure of decision-making. This framework models numerous real-world problems where decisions one level influence outcomes another, including reinforce- ment learning [Hong al.) 20033 Thoma et al. 2024 Shen et al. 2025), meta-learning (Bertinetto) et al., 20188 Rajeswaran et al. 2019 Ji al. 2020], adversarial learning (Madry al. 2017]. hy- perparameter optimization [Pedregosa] 2016 Franceschi et al.) 2018). J and imitation learning [Arora al. 2020). The flexibility of bilevel optimization makes it an essential tool for modeling complex systems and tackling a wide range of challenges modern machine learning and optimization.
As datasets continue to grow and machine learning models become more complex, bilevel optimiza- tion increasingly necessitates decentralized computation paradigms [Kong et al. 2024). Decentralized approaches distribute computation across multiple agents that communicate only with their neighbors, thereby significantly reducing communication overhead and enhancing scalability for large-scale problems. These frameworks are particularly valuable in scenarios where centralizing data is in- feasible due to privacy concerns or infrastructure limitations [Zhang et al.] 2019 Kayaalp et al. 2022). Applications of decentralized bilevel optimization prevalent in various domains, including resource allocation [Ji and Ying 2023], collaborative makinng [Hashemi et al. 2024], and
"Corresponding Author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

distributed machine learning (Jiao et al. 2022), where agents collaboratively solve a global bilevel problem while addressing local constraints.
Given its importance, numerous studies have explored the challenges of decentralized bilevel opti- mization, focusing on algorithm design [Lu et al.
2022b] convergence analysis (Wang et al. [024 and practical applications [Lu et al. 2022a, Liu et al. 2022]. Among existing methods, double-loop frameworks have been extensively studied for their effectiveness in achieving convergence across various settings [Chen et al. 2024a 2023]. However, these approaches are computationally expensive due to their nested structure, which requires repeatedly solving lower-level problems during each upper-level iteration. This results in significant computational and communication overhead in decen- tralized settings. To address these limitations, single-loop methods have emerged as a computationally efficient alternative (Zhu et al. 2024 Dong et al. 2023]. By integrating updates for both levels into a unified process, single-loop frameworks reduce overall complexity and are better suited for real-world decentralized bilevel optimization tasks.
Despite these advancements, existing decentralized bilevel optimization methods face critical challenge: problem-specifie hyperparameter tuning (e.g., stepsizes), In particular, the selection of hyperparameters in these algorithms often relies on problem-specific information, such smoothness and strong convexity constants, the spectral gap of the graph adjacency matrix, or other topological characteristics. However, obtaining such information is typically infeasible due to physical or privacy constraints and computational limitations, especially in large-scale machine learning applications involving massive datasets. The nested structure of upper- and lower-level objectives in decentralized bilevel problems further exacerbates this challenge. As a result, extensive hyperparameter tuning remains necessary existing methods, significantly limiting their practicality in real-world scenarios. This raises fundamental question:
Can we design single-loop decentralized bilevel optimization algorithm that eliminates reliance on problem-specife parameters while achieving comparable performance to well-tuned counterparts?
1.1 Main Contributions
In this paper, we provide an affirmative answer the above question by proposing Adaptive Single-loop Decentralized Bilevel Optimization Algorithm (AdaSDBO). AdaSDBO leverages accu- mulated gradient norms dynamically adjust stepsizes per iteration, thereby eliminating the need for hyperparameter tuning. We conduct a comprehensive convergence analysis with nonconvex- strongiy-convex problem settings, showing that AdaSDBO achieves performance comparable to existing well-tuned approaches. Our main contributions are summarized as follows:
We propose AdaSDBO, the first parameter-free free method for decentralized bilevel optimization with single-loop structure. AdaSDBO employs adaptive stepsizes based on accumulated (hyper)gradient norms to update all variables simultancously. However, due to the coupling of bilevel objectives, adaptive stepsizes in a single-loop framework must carefully orchestrate the progress of primal, dual, and auxiliary variables. Additionally, network heterogeneity in decentralized settings intro- local-gradient -a--rrrert-naseeeeee adaptive stepsizes. To address these challenges, our method incorporates two key mechanisms: 1) hierarchical stepsize design, which respects the interdependence of different variables while preserving the autonomy of adaptive stepsizes; 2) stepsize tracking scheme, which synchronizes gradient accumulators, effectively managing stepsize discrepancies among agents.
duces inconsistencies
We provide a comprehensive theoretical analysis, demonstrating that our algorithm eliminates the need for mooblem-specifi hyperparameter tuning while achieving a convergence rate of Ö )). matching well-tuned counterparts ( et al., 2022 Dong et al. 2023 up to polylogarithmic factors. Our analysis is inspired by the two-stage framework [Xie et al. 2020 Ward al.) 2020). but uniquely addresses the intricate coupling between optimization variables and adaptive stepsizes in single-loop bilevel optimization. Furthermore, we conduct more rigorous analysis to control the interaction between hierarchical optimization errors and network-induced discrepancies, while preserving the barollem-prameter-fiire property.
We conduct experiments on several machine learning problems, showing that our method performs comparably with existing well-tuned approaches on both synthetic and real-world datasets. More- over, our method exhibits remarkable robustness across a wide range of initial stepsizes, validating the effectiveness of our adaptive stepsizes design.
2

---

Table 1: Comparison between different bilevel optimization algorithms. denotes the number of (upper-level) iterations; c is the target stationarity such that E ( [TT I E, Pw measures the connectivity of the underlying graph; and L are the strongly convex and Lipschitz constants, respectively; represents the momentum parameter.
Algorithm
Loopless Convergence Rate Gradient Complexity!
Parameters?
DBO Chen et al.
2024a
log (:)
p. p.
MDBO
Gao et al. 2023
X
log (t)
pw
FSLA
Li ct
2022a
0
(++
14, I, B
AID Ji et
2022
(())
o (+)
μ4, L,
SLDBO Dong et al.
2023
(G)
o (C)
μ. p.
AdaSDBO (This paper)
0 log (T)
( log" (9)
None
The convergence rate when - oc.
The number of gradient//cobiia//eessaa evaluations per agent to achieve e-accuracy when Stepsize-related problem-specific parameters.
O.
1.2 Related Works
Decentralized Bilevel Optimization. Recent advancements in decentralized bilevel optimization have focused addressing the challenges of large-scale data and leveraging the computational benefits of parallel environments. Chen et al. [2024a] proposed DBO, a general framework that
incorporates convergence analysis while accounting for data heterogeneity across agents. Similarly,
MA-DSBO [Chen et al.] 2023 and MDBO [Gao et al.) 2023) employed a double-loop framework
with momentum techniques Liu et 2020). More recently, single-loop frameworks have emerged as efficient alternatives to double-loop methods. These approaches [Chen et al., [024bb Dagréou
al. 2022 Kong al., 2024, Zhang et al. 2023 enable approximate solutions decentralized bilevel problems within single iteration, significantly improving computational efficiency by reducing redundant computations. Such methods have made decentralized bilevel optimization
more practical and scalable for large-scale applications. [Dong et al.) [2023) further introduced SLDBO, a low-complexity single-loop decentralized bilevel algorithm that leverages gradient tracking technology. Despite these advancements, existing methods rely on fixed or uniformly decaying stepsizes. Further, they require prior knowledge of problem parameters for stepsize selection. This dependency imposes additional challenges, particularly in decentralized settings where such information is often unavailable or difficult to estimate. Further details on bilevel optimization, adaptive methods, and their applications are provided in Section
1.3 Comparisons with Prior Approaches
We compare AdaSDBO with representative bilevel optimization methods, as summarized in Table Notably, AdaSDBO adopts loopless framework while achieving a convergence rate that matches the state-of-te toite-of-thearr results, up polylogarithmic factor of log" (T). Since logarithmic factors grow significantly slower than polynomial terms, this factor is negligible relative to T, common consideration in optimization research (Yang et al. 2022 Li et al. 2024 By carefully controlling network-inden inducedd errors, AdaSDBO matches both the convergence rate and gradient complexity of its centralized counterpart AID [Ji al. 2022], while outperforming the centralized method FSLA [Li et al. 2022a] in both metrics. Compared to decentralized approaches such as DBO (Chen et al. 2024b), MDBO [Gao et al. 2023 and SLDBO [Dong et al. 2023). AdaSDBO achieves the best- known convergence rate of O and gradient complexity of O while surpassing double-loop methods in gradient complexity conplexttyuunderseeee underscoring the efficiency its single-loop framework. Most importantly, AdaSDBO is completely tuning-free frreg algorithm independent of problem parameters, which in sharp contrast to other methods that require extensive hyperparameter tuning. This advantage significantly simplifies algorithm deployment, facilitating the implementation of bilevel optimization in diverse environments.
2
Algorithm Development
2.1
Problem Model
In this paper, we consider a networked system consisting of n nodes (agents) that collectively solve the following nonconvex-stronglyy bilevel optimization problem:
3

---

min ((x) = (,,)(()))))))))))))))))))))))( = - - Σ li y (x)),
ZEBP
(I)
s.t. (x) = arg min [2, v) = 4(x, v),
vE
where f(-) represents the upper-level objective function, which is minimized with respect to æ, subject to the constraint that y (æ: a minimizer of the lower-level function I(-). Each agent has a possibly nonconvex objective function fi(:): IP x R + R and strongly convex objective function 4()) I x IR4 + R with respect to y. The agents are interconnected through a communication network modeled as a graph g (N. where N = 21,2..... ......... n is the set of nodes (agents), and S N' x N is the set of edges representing communication links. An edge (i.j) E indicates communication link between nodes and node i. We represent the weight matrix of the communication network 9 as W = (wy E [==x", where Wij = if (i.j) & E. The following assumption is made on W.
Assumption 2.1. The matrix W is doubly stochastic, i... W1 = 1, 1 1 = 17, and pw == [W-J][
2 < L, where J 11 /n is the averaging matrix with dimension. key challenge in solving the Problem expressed as:
① is the computation of the hypergradient ( which
VT(x)= = -VV (x)) V (z, y (x))) (x)),
V.
derived using the implicit function theorem [Ghadimi and Wang 2018 First, the lower-level minimizer y" (x) is typically not directly accessible, requiring iterative algorithms to approximate it with an estimate ÿ. Second, the expression in Eq. (2) involves the inversion of the Hessian matrix V, y yar, y" (z:)), which is computationally expensive, with the complexity of O(r"). Additionally, in decentralized settings, the difficulty is further exacerbated because each agent has access only to its local problem and lacks information about the global lower-level objective ((-). To overcome this challenge, we introduce the following linear system:
1 min r(x, 8. v) v Vyl,, vff
33)
2
which seeks to approximate the inversion of the Hessian matrix by v² (x:) (V V,l(z, yy ( (x,,y()) when ý approaching y y²(x), where v E V. An iterative algorithm is then employed to compute an approximate solution é to the Problem (3). Using the
approximations ÿ and 0, the x is subsequently updated based on a hypergradient estimate as:
vf g. 6) (z, 9) V. (z)
Building on this framework, solving the decentralized bilevel optimization problem T can be reformulated into three interconnected subproblems:
arg min ZER
Σ filz, y (x),
(5a)
y" v²(x)
arg min yERu
4(x, v),
(5b)
1
0 (²(x) arg min
rs ri 8d (2)), v). (5c)
v
In (5), the subproblems (5a) and (5c) depend on the optimal solution of (5b). This naturally motivates
many existing works [Chen et al. 2023 2024 to adopt nested structure, where (5b) is solved up to a certain accuracy before sequentially computing (5c) and (5a). However, these nested loops result in substantial computational overhead and implementation difficulties. To address this, single-loop framework [Dong et al., 2023) Zhu et al., 2024] has been proposed to solve the three subproblems in parallel, thereby improving computational efficiency in bilevel optimization. Nevertheless, the single-loop structure introduces significant challenges in algorithm design and convergence analysis.
Furthermore, existing decentralized bilevel optimization solutions predominantly rely problem- specific parameters for algorithm tuning, such as smoothness and strong convexity constants, the spectral gap of the graph adjacency matrix, or other topological characteristics. Obtaining such information is often impractical due to physical or privacy constraints, as well as computational in large-scale machine learning applications involving massive datasets.
In light of these challenges, this paper aims to develop a single-loop algorithm for solving Problem 5 while achieving comparable convergence guarantees without the need for hyperparameter tuning.

---

2.2 Algorithm Development
In this subsection, we propose an Adaptive Single-loop Decentralized Bilevel Optimization Algorithm (AdaSDBO) based on iterative gradient updates, as presented in Algorithm | Let F1, E IR, Vi.t E R9, and Vi,r I2 denote the iterates agent for variables æ. y, and v, respectively, the local gradients at each agent i can be expressed as:
According to Problem 5)
V (I Mi,to v(.) (.I,i Vo.e) V. V ( Vi,e)
V (r Miet v(.)) = V, V (1r,, Vi,))ss "0li(=,,.,...)
For brevity, let gf = (I Mi,e, v..)) 9h, == (z Bi.r) and Jī, == Veri yh,es v..)).
Adaptive Stepsizes Design. To eliminate the dependency on problem-specific parameters, we design the adaptive stepsizes strategy based on accumulated gradient norms. Specifically, we introduce an accumulator m as [m= [1 [m]. + ,,,,,''' 11 Using this accumulator, the dual variable y/, is updated by 01,++1 Vi, m_..1 -h,.. where "y O is a control coefficient that is independent of the problem parameters. Similarly, the accumulators m.,, and m,, are defined by the updates [m im=_cl c|2 11 1 and [m] im_, 12 119 respectively. However, the adaptive update rule for dual variable yi, cannot be directly extended to primal variable Xi, and auxiliary variable Ui.t due to their intricate interdependencies with other variables. The primary challenges are:
Luxiliary-Level Update: The update of the auxiliary variable vi,, requires the optimal solution y" of the lower-level subproblem. Since single-loop algorithms perform only one-step updates of the variable yi the suboptimality gap ||vi,++ y" || must be carefully managed to prevent error accumulation. Thus, U2 must progress faster than ye,, to maintain approximation accuracy.
Upper-Level Update: The primal variable Ji,t depends on both the optimal variables y" and v², introducing additional complexity. Errors from both the lower-level and auxiliary- updates must be considered, necessitating more conservative updates of the variable Ti, align with the slower dynamics of these levels.
To overcome these challenges, propose the following hierarchical stepsizes:
Auxiliary variable update (Nt,)): We employ stepsize inversely proportional to %
max(m" mx,+1)) resulting in the update rule 0.++1 UsŞt
Pi,--
Primal variable update (2;,)): We use a more conservative stepsize, inversely proportional to m²,441 max(m) m 11), yields the update 24,4+1 Fi mf.1j max(m) on Fi.-
Here, Yo and 7/2 > O are control coefficients.
This hierarchical stepsize design plays a critical role in balancing the progress speeds at different levels, ensuring stability and convergence in single-loop optimization. Additionally, the adaptive stepsizes based on accumulated gradient norms dynamically adjust to the local optimization geometry, enhancing the efficiency and accuracy of the algorithm without requiring goblem-sseciffe parameters.
For notational convenience, we define the stepsize variables 9, := mf,+1 max { (mā m
Wi,4+1 := m and Zi.+1 := max {mā m Correspondingly, we define the following diagonal stepsize matrices as:
Q++1 diag / U411 diag (1,441) Z+11 diagf 21,4+1 Fi-r
Additionally, define the concatenated variable matrices as: X; :===l ====I... I. ........ I. Raxx,, Yt == JTTtt......TT TER and v,==(.., vi...... " EER We also concatenate the gradient vectors as:
[...,
V (F(( [....
U.,,) "........] V,I(x,, = [... Vyh(E...
V R( vz) = [-.., (or, Mi.r U,,)):
Based on these definitions, the update rules for the primal, dual, and auxiliary variables are given by:
X1+1 W
W(x: Xx Q,1 F Ye. Ve.ve. y-- w T, (xx,
Ve+1 Py
Pu(wW) (W -ive-~oZi 7oZ R. vo))
where Pv(-) denotes the projection operation onto the set V.
5

---

Algorithm Adaptive Single-Loop Decentralized Bilevel Optimization: Procedures at Each Agent
2 [n]
1: Initialization: 22,0, Vs Us,0, m²,0- 'na00 miio 0, 7 7 7o > 0.
2: for t= 0,..
do 3: Compute the gradients:
Lh V (as, Vi.e),
Ri. v. V,, Vyle(ai,, Vi.))r, V
Ki. Vanf(Fii, Ms.c) V.V V ( 11,1)0
4: Accumulate the gradient norms:
[m ++ im,, + || 2 [m + - 11.",,,, [ = [m,,e]? 2 119 11
5: Update the primal, dual, and auxiliary variables by:
Me,+1 Vi. m -h.""
01,411 Ui.t" max(m]
0i,++1 = Zitt i,t+ max
Fi.
6: Information exchange with neighbors:
(I, y, viiet1 6 E, Wi w (I, U)i,+1,
{m" .m, m)) "r,+, + Σj wi.fmm" m",m") "r mm)++t.
7: Projection auxiliary variable on the set V: 01,+1 + Pu((ee+1).
8:
end for
Addressing Stepsize Inconsistencies. In decentralized bilevel settings, agents compute their adaptive stepsizes independently based on local private objective functions, and the coupling of multiple optimization variables within adaptive stepsizes amplifies their network-wide inconsistencies. These discrepancies can hinder convergence if not properly controlled. To formalize this, let Ie == >. Lize denote the average of all primal variables at the t-th iteration, and q: = 1 -i Oir represent the average of their respective stepsizes. We then define the stepsize discrepancy vector as Using this definition, the update rule for He can be expressed as: q. -.... 4i,t 98 ..]
(9.11)
B++1
Ya
V.....
(6)
In Eq. (6). term (a) resembles centralized gradient descent, while term (b) introduces an undesired perturbation caused by stepsize inconsistencies among agents. This perturbation can disrupt network consensus due to varying update rates and may lead to uncontrollable error growth, as term (b) represents accumulated gradient-norm discrepancies over iterations. Such stepsize inconsistencies similarly affect the updates of the dual and auxiliary variables.
To address this challenge, we incorporate stepsize tracking mechanism in Algorithm I At each iteration, the gradient-norm accumulators m m and m are tracked by:
[mf 12 Σ
Wis |m 3.411
Σ wii (Im + 110))
where b E {x,y,0) and E [n]. Let K. = [... .....,. [m 12,
and h = [.... 19
denote the concatenated gradient accumulators and corresponding norms, respectively. The above equation can then be compactly expressed as k/-1 W (kę +h)) This tracking mechanism enforces consensus on the gradient-nomi accumulators before computing the adaptive stepsizes (gi,r Ug 21,)). By synchronizing these accumulators. it effectively bounds stepsize discrepancies among agents, preventing error accumulation while preserving the adaptive nature of the updates.
It is worth noting that the additional communication overhead of our method is modest- only scalar values (the stepsize accumulators) are eeshened--sseccially compared with transmitting the primal, dual, and auxiliary variables commonly communicated in decentralized bilevel methods. Some approaches [Gao al. 2023] [Chen et al., 2023] Zhu et al., (2024) also employ gradient tracking mechanism, which involves exchanging extra tracker states with the same dimensionality as the

---

optimization variables, In contrast, our method adds only lightweight scalars for transmission, while offering robust, problem-paran parameter- free solution for decentralized bilevel optimization.
Theoretical Analysis
3.1 Technical Challenges
The analysis of ieppooem-paaaeee parameter-fiee firee decentralized bilevel optimization with a single-loop structure involves several fundamental challenges:
Interdependent Variable Updates: The coupling of bilevel objectives creates intricate interde- pendencies among the variables (x, y, v), making the convergence analysis significantly more challenging compared to single-level optimization.
Coupled Stepsize Dynamics: The adaptive stepsizes exhibit highly intertwined dynamics, forming multi-stage system in which the progress of each variable directly affects the others, requiring meticulous coordination to manage these interactions effectively.
Accumulated Stepsize Inconsistencies: Inconsistencies in adaptive stepsizes across agents disrupt network consensus, while their cumulative effect over iterations further exacerbates the challenge.
Interplay Between Optimization and Consensus Errors: The interaction between hierarchical optimization errors and network-induced discrepancies necessitates rigorous theoretical bounds to property.
guarantee convergence while maintaining the
3.2 Assumptions and Definitions
In this subsection, we present the standard assumptions and definitions used in our analysis. Assumption 3.1. For any E [n]], the objective functions fa y) and 4(x y) are twice continuously differentiable, and 4zz, y) is j--strongly convex with respect to y.
Assumption 3.2. For any i E [n]. the function fe(x, y) is L-Lisshic continuous; the gradients fi(r, y) and V1, y) gradients V. V (z, y) and V V g,4((, y) are Lt continuous.
f and L1,--iipschizz continuous, respectively; the second-order
The above assumptions are commonly adopted in prior works, including (Zhu et al. 2024 Chen et al. 2024a 2023
Dong et al.
2023
Ji et al. [2022].
Remark 3.3. Assumption
3.2 indicates that there exist constants Cfa OJu Clap and Ct such that Vz,i 8)1l < Clay and |V V 4 b s City
[V. r)1l S Cja,
y Ji (z, v)ll S Cj
Define ū;: Σm W4,r, b,= n
1 Σin1 2g,1, and recall that q:= n E fi. We then introduce the following metrics to quantify the level of stepsize inconsistency among agents:
( Gt 1)
U 1 ū, 1)
22, 2t
2 := sup
2 = sup
2 = sup
(g. 1)²
(u,-" 1)²
(2) 1)²
HE il)
iE(n],
( 1
1
(u ū1 1)
(Z =-1 1)
0 = inf
0 = inf
inf <E(m)
gr
k
(u,"" !)
(2 1)²
3.3 These metrics are guaranteed to remain bounded under Assumption 3.2 and Remark
Definition 3.4. An output 7 of an algorithm is the e-accurate stationary point of the objective function (xx) it satisfies [+())) < e, where e (0,
3.3 Theoretical Results
In this subsection, we present the main theoretical results for the proposed Algorithm [ with the proof sketch provided in Section B As outlined in Section [.2] the descent behavior of the objective function (--) is governed by three key factors: approximation errors, consensus errors, and stepsize inconsistencies. These components
bounded in the following lemmas.
To facilitate the analysis, we first define Z, = 1 Σ Fitts It = EE Wits and ün
" 0i,e- Then, let my := En= m., and m == " E my represent the average of the gradient accumulators. Additionally, denote f(z,, Dt. F,) = EE fā, De. 8x), (ā Fe) :=
7

---

1 +E=n4 4(2,, r( Dr. ; Ei=1 when the variables (x,y, y, v) achieve consensus to (3, B)
Fi Dt. T2) as the corresponding aggregated functions
From the descent lemma in Section D.2 we obtain that the approximation error (.,) fāa, Dt, 622 is attributed in terms of O (T,,, Bell(²) and V(IVor(fa Ut. U2 (P) Hence, we establish the following lemma to provide bounds for these terms associated with approximation errors during the optimization process.
Lemma 3.5 (Approximation Errors), Under Assumptions 3.7 and 3.2 for any integer ko E t),
we have Ei=ho [V,,(ag...)ll S as log((++))) +b; and Σ Lk=uo (F..F....... S ag log(t+1))+
where the constants ag bs, 06, and by are defined in Eq. (108) of Section D.8
Lemma 3.6 (Accumulated Gradients). Under Assumptions
3.7 and 3.2
the gradient accumulators
satisfy the bounds mi < O (log(t)) and 2e S O (log(t)).
Lemma 3.6 shows that the accumulated gradient norms for all variables logarithmically with respect to the iteration index t.
(z, y, v) grow at most
Lemma 3.7 (Consensus Errors). Suppose that Assumptions 2.1 3.1 and 3.2 hold. Let A. ||x, - | + lly. 1/ + V - 10,11 represent the consensus errors for all variables at the t-th iteration. Then, the time-averaged consensus error satisfies + ET A < O (log(T)/T))
Next, we provide the bounds for the terms associated with the stepsize inconsistencies in our analysis. Lemma 3.8 (Stepsize Inconsistencies) Suppose Assumptions 2.7 ancy vectors as q, [--- - 41
3.7
and 3.2 hold. Define discrep- and 2, - 2
ú, : u,,
, 1.. Then, under Algorithm
we have that T Et=o (9
F((,, vt)/
+ EEO (1,71) I, y.) / and 7 Et- (Pith)
V R(x vo) m/ 1| are
each apper-bounded by O (Iog(T)/I)
Combining the above results, we establish the convergence of Algorithm I as follows.
Theorem 3.9. Under Assumptions 2./
3.7 and 3.2 for any positive constants Ya Tv Yw. mā, m and m the iterates generated by Algord satisfy:
(Z)) $
2 ta7 log (og(T)+bb)))))) by (a)))
(+.))) -T
7/
+Cm= (1 (4(
(8(To) 4"
+ +azlog(T)+br) (a (a1lo8(T)+bi) =0 (log"
llog (T)
where Tp" = inf ((x) -00, and the constants Cun,, 01 by 07, and by are defined in Eqs. (30). 700. and (126) in the Appendix.
Remark 3.10. Theorem 3.9 implies that for any positive coefficients (Ta, Ty Yo) and positive initial
stepsizes (me my mX,)), Algorithm guarantees convergence with rate of O log This
convergence rate matches the state-of-the-arr results, up a polylogarithmic factor of log (T) which
is regarded negligible relative to T' in the optimization literature (Yang et al. [022 Li et al. 2024
Corollary 3.11. From Theorem 3.9 to achieve an e-accurate stationary point, Algorithm 7 requires
T T= log' (2)) iterations, resulting in a gradient complexity of Gc(c) = O (1 log*
In sharp contrast, the theoretical convergence of existing decentralized bilevel methods heavily relies on the correct selection of hyperparameters based on problem-specific constants. such as L. and Pw. This reliance restricts their applicability, as these parameters are unknown or difficult to determine. In comparison, our approach significantly simplifies the implementation of decentralized bilevel optimization by operating in a completely
manner.
Numerical Experiments
In this section, we evaluate the performance of Algorithm I on the hyperparameter optimization problem, as illustrated in Section F. Our algorithm is compared with several decentralized bilevel optimization methods, including SLDBO [Dong et al. 2203)). MA-DSBO [Chen al.) 2202). MDBO [Gao et al. 2023). and DBO [Chen et al. 2024a]. Experiments are conducted on both synthetic and real-world datasets, with detailed configurations and additional results provided in Section E

---

0.58
0.90
Mi-0220
DCO
DBQ miii
F-40
SLEGO (yn))
SLEGO und)
002
0.52
0,2
ACHSEBD
AcsSE00 pnd
50
100
Baritorn
230
200
50
Bandoorn
200
250
300
100
200
300
400
500
200
100
500
800
2000
(a) Synthetic (p 50)
(b) Synthetic (p = 200)
DOMNIIS((varyinn n)
FVANIS n)
Figure 1: Test Accuracy different datasets.
Accussy 1
Aruway
DBG
20
SL0D0
SLOOO
(a) Synthetic
(b) MNIST
(c) FMNIST
Figure 2: Test accuracy versus stepsize on different datasets.
4.1 Synthetic Data Experiments
For synthetic data, the data distribution at node follows (0, ,²), where the parameter r controls the level of data heterogeneity. To evaluate the advantages of AdaSDBO, we first compare different methods under low data heterogeneity conditions with r = (Experiments under higher heterogeneity conditions are presented in Figure 4 of Section E. Both algorithms compute full gradients and utilize a training dataset and a testing dataset, each containing 20,000 samples. As illustrated in Figure (a) and Figure (b), AdaSDBO achieves faster convergence than baseline methods across different data dimensions (i.e., = 50 and 200). Notably, our method consistently outperforms the double-loop frameworks DBO and MA-DSBO. These results validate both the superiority of the adaptive stepsizes design and the single-loop structure of AdaSDBO.
4.2 Real- World Data Experiments
We evaluate our method on the hyperparameter optimization task using the MNIST [LCunn et al. 1998] and FMNIST [iaoo et al. 2017] datasets. In Figure Ic) and dd), we vary the number of agents to assess scalability. The results illustrate that AdaSDBO consistently maintains a robust convergence rate across different network sizes, highlighting its scalability and robustness to variations in the number of agents. Furthermore, AdaSDBO achieves a competitive convergence rate compared to state-of-the-ar methods, further corroborating its effectiveness. Additional scalability evaluations under broader network configurations are presented in Figure g and Figure 9 of Section E.6
Figure 2 compares the test accuracy of various algorithms versus stepsizes on the synthetic, MNIST, and FMNIST datasets. All algorithms were evaluated over 1, 1,000 rounds to ensure fair comparison. To comprehensively assess robustness, the stepsizes were varied over a wide range (i.e., from 10 10-3 to 10a). It can be observed that the AdaSDBO algorithm demonstrates remarkable resilience to stepsize selection, maintaining stable performance over a substantially broader range of stepsizes compared to baseline methods. In contrast, the baseline algorithms exhibit relatively narrower regions of stable performance, underscoring the enhanced stepsize robustness of proposed parameter- method.
4.3 Decentralized Meta-Learning
We evaluate our method on decentralized meta-learning using the CIFAR- 10 dataset [McMahan al. [017]] where multiple tasks are constructed following the protocol in [Finn al. 2017| This approach minimizes the test loss with respect to shared parameters as the upper-level loss, while the training loss managed by task tasc-spec parameters at the lower level. The detailed configuration of this experiment can be found in Section E.4 To highlight the effectiveness of our approach, we compare against the state-of-the-ar SLDBO method [Dong et al.. 2023). As shown Figure TT of Section E.6 our method achieves notably better training accuracy. This improvement stems design, which allows the algorithm to automatically adapt stepsizes,
from its poobeem-arametee consistently reaching optimal convergence rates without manual tuning.

---

Conclusions and Limitations
In this paper, we proposed AdaSDBO, a parameter-free algorithm decentralized bilevel opti- mization with single-loop framework, supported by rigorous finite-time convergence analysis. AdaSDBO adaptively adjusted stepsizes without relying on prior knowledge of problem parame- ters, achieving convergence rate comparable well-tuned counterparts. Extensive experiments showed that AdaSDBO delivered strong generalization performance and climinated the need for tedious hyperparameter tuning, showcasing its potential for large-scale machine learning applications. Nevertheless, our analysis targets deterministic settings with full-gre full-gradient information and assumes a strongly convex lower-level problem. Extending the results stochastic regimes and to generally convex lower-level objectives remains an open direction. We aim to address these limitations in future work to broaden the scope of applicability of AdaSDBO.
Acknowledgements
This work is supported in part by the General Research Fund (project number 14214122, 14202723, 14207624), Area of Excellence Scheme grant (project number AoF/E--601/2-RR, and NSFC/RGC Collaborative Research Scheme (project number CRS HKUST603/22, CRS HKU702/24), all from the Research Grants Council Hong Kong.
References
Kimon Antonakopoulos, Shoham Sabach, Luca Viano, Mingyi Hong, and Volkan Cevher. Adaptive bilevel optimization. ACM/MMS Journal of Data Science, 2(2):1-29, 2025.
Sanjeev Arora, Simon Du, Sham Kakade, Yuping Luo, and Nikunj Saunshi. Provable representation learning for imitation learning via bi-level optimization. In International Conference on Machine Learning, pages 367-376. PMLR, 2020.
Luca Bertinetto, Joao Henriques, Philip HS Torr, and Andrea Vedaldi. Meta-learning with differen- tiable closed-form solvers. arXiv preprint 1805.0/80 2018.
Jerome Bracken and James T McGill. Mathematical programs with optimization problems in constraints. Operations Research, 21(1))37-44, 1973.
Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-357, 2015.
Losé-Fernando Camacho- Camacoo-Vallejo, Carlos Corpus, and Juan G Villegas. Metaheuristics for bilevel optimization: A comprehensive review. Computers & Operations Research, 161:106410, 2024.
Giulia Caselli, Manuel lori, and Ivana Ljubić. Bilevel optimization with sustainability perspective: survey on applications. arXiv preprint arXiv:2406.00 071.0.1114444 84, 2024.
Xuxing Chen, Minhui Huang, Shigian Ma, and Krishna Balasubramanian. Decentralized stochastic bilevel optimization with improved per-iteration complexity. In International Conference on Machine Learning, pages 4641-4671. PMLR, 2023.
Xuxing Chen, Minhui Huang, and Shiqian Ma. Decentralized bilevel optimization. Optimization Letters, pages 1-65, 2024a.
Xuxing Chen, Tesi Xiao, and Krishnakumar Balasubramanian. Optimal algorithms for stochastic bilevel optimization under relaxed smoothness conditions. Journal of Machine Learning Research, 25(151):1-51, 2024b.
Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. Advances in Neural Information Processing Systems, 35:26698-2677 2022.
Justin Domke. Generic methods for optimization-hase modeling. In Artificial Intelligence and Statistics, pages 318-326 PMLR, 2012.
10

---

Youran Dong, Shiqian Ma, Junfeng Yang, and Chao Yin. A single-loop algorithm for decentralized bilevel optimization. arXiv preprint arXiv:2311.08945, 2023.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7), 2011.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-leaming for fast adaptation of deep networks. In International Conference on Machine Learning, pages 1 1126-1133 1135. PMLR, 2017.
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-basse based hyperparameter optimization. In International Conference on Machine Learning, pages 165- 113.. PMLR, 2017.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference Machine Learning, pages 1568-1577. PMLR, 2018.
Hongchang Gao, Bin Gu, and My T Thai. On the convergence of distributed stochastic bilevel optimization algorithms over network. In International Conference Artificial Intelligence and Statistics, pages 9238-9281. PMLR, 2023.
Saced Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02244. 2018
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo, On the iteration com- plexity of hypergradient computation. In International Conference Machine Learning, pages 3748-3758. PMLR, 2020.
Pierre Hansen, Brigitte Jaumard, and Gilles Savard. New branch-and- bound rules for linear bilevel programming. SIAM Journal Scientific and Statistical Computing, 13(5):1194-13 1217, 1992.
Diba Hashemi, Lie He, and Martin Jaggi. Cobo: Collaborative learning via bilevel optimization. arXiv preprint arXiv:2409.055: 09539999,55,,,... 2024.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1):147-180, 2023.
Feihu Huang, Xinrui Wang, Junyi Li, and Songcan Chen. Adaptive federated minimax optimization with lower complexities. In International Conference on Artificial Intelligence and Statistics, pages 4663-467L PMLR, 2024a.
Yan Huang, Xiang Li, Yipeng Shen, Niao He, and Jinming Xu. Achieving near-optimal convergence for distributed minimax optimization with adaptive stepsizes, arXiv preprint arXiv:2406.02939, 2024b.
Kaiyi and Lei Ying. Network utility maximization with unknown utility functions: A distributed, data-driven bilevel optimization approach. In Proceedings of the Twenty-fourth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, pages 131-140 2023.
Kaiyi Ji, Jason D Lee, Yingbin Liang, and H Vincent Poor. Convergence of meta-learning with task-specific adaptation over partial parameters. Advances in Neural Information Processing Systems, 33:1 1490- 1500. 2020.
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pages 4882-4892, PMLR, 2021.
Kaiyi Ji, Mingrui Liu, Yingbin Liang, and Lei Ying. Will bilevel optimizers benefit from loops. Advances in Neural Information Processing Systems, 35:3011 11:3011-3023, 2022.
Yang Jiao, Kai Yang, Tiancheng Wu, Dongjin Song, and Chengtao Jian. Asynchronous distributed bilevel optimization. arXiv preprint 2rX 2022.

---

Mert Kayaalp, Stefan Vlaski, and Ali H Sayed. Dif-maml: Decentralized multi- agent meta-learming. IEEE Open Journal of Signal Processing, 3:71-93, 2022.
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.03167 2024.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):278-2324, 1998.
Kfir Levy. Online to offline conversions, universality and adaptive minibatch sizes. Advances in Neural Information Processing Systems, 30, 2017.
Kfir Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and accelera- tion. Advances in Neural Information Processing Systems, 31, 2018.
Jiaxiang Li, Xuxing Chen, Shiqian Ma, and Mingyi Hong. Prohlem-pparameter-free decentralized nonconvex stochastic optimization. arXiv preprint arXiv:2402.0882/, 2024.
Junyi Li, Bin Gu, and Heng Huang. A fully single loop algorithm for bilevel optimization without hessian inverse. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 7426-7434, 2022a.
Xiang Li. Junchi Yang, and Niao He. Tiada: A time-scale adaptive algorithm for nonconvex minimax optimization. arXiv preprint arXiv:2210.17478, 2022b.
Renjie Liao, Yuwen Xiong, Ethan Fetaya, Lisa Zhang, KiJung Yoon, Xaq Pitkow, Raquel Urtasun, and Richard Zemel. Reviving and improving recurrent back- nuk-propagatton. In International Conference on Machine Learning, pages 3082-3091. PMLR, 2018.
Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. Advances Neural Information Processing Systems, 33:18261-18271 2020.
Zhuqing Liu, Xin Zhang, Prashant Khanduri, Songtao Lu, and Jia Liu. Interact: Achieving low sample and communication complexities in decentralized bilevel learning over networks. In Proceedings of the Twenty-Third International Symposium Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, pages 61-70, 2022.
Songtao Lu, Xiaodong Cui, Mark S Squillante, Brian Kingsbury, and Lior Horesh. Decentralized bilevel optimization for personalized client learning. In ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages
IEEE, 2022a.
Songtao Lu, Siliang Zeng. Xiaodong Cui, Mark Squillante, Lior Horesh, Brian Kingsbury, Jia Liu, and Mingyi Hong. A stochastic linearized augmented lagrangian method for decentralized bilevel optimization. Advances in Neural Information Processing Systems, 35:30638-30654 2022b.
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. arXiv preprini 190ivv/902.09844 2019.
Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient- -based hyperparameter optimization through reversible learning. In International Conference on Machine Learning, pages 2113-2122. PMLR, 2015.
Aleksander Madry. Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 1xXi::7006.660 2017.
Yura Malitsky and Konstantin Mishchenko. Adaptive gradient descent without descent. arXiv preprint arXiv: 2019.
Naoki Marumo and Akiko Takeda. Parameter-fres accelerated gradient descent for nonconvex minimization. SIAM Journal on Optimization, 34(2):2093-2220, 2024.
12

---

Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication-efien learning of deep networks from decentralized data. Artificial Intelli- gence and Stafistics, pages 1273-1282. PMLR, 2017.
H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex opti-
mization. arXiv preprint arXiv: 2010.
Angelia Nedic, Asuman Ozdaglar, and Pablo Parrilo. Constrained consensus and optimization in multi-agent networks. IEEE Transactions on Automatic Control, (5544)9222-335 2010.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer. James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, pigh-peeformance deep learning library. Advances in Neural Information Processing Systems, 32, 2019.
Fabian Pedregosa.
Hyperparameter optimization with approximate gradient. International Conference on Machine Learning, pages 737-746. PMLR, 2016.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. Advances in Neural Information Processing Systems, 32, 2019.
Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back- proppropaggtioon for bilevel optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1732.1732. PMLR, 2019.
Han Shen, Zhuoran Yang, and Tianyi Chen. Principled penalty-based methods for bilevel reinforce- ment learning and rlhf. Journal of Machine Learning Research, 26(1 14):1-49, 2025.
Chenggen Shi, Jie Lu, and Guangquan Zhang. An extended kuhn-tucker approach for linear bilevel programming. Applied Mathematics and Computation, 162(1):51--3, 2005.
Vinzenz Thoma, Barna Pásztor, Andreas Krause, Giorgia Ramponi, and Yifan Hu. Contextual bilevel reinforcement learning for incentive alignment. Advances in Neural Information Processing Systems, 37:127399-227435 2024.
Tijmen Tieleman and Hinton. Divide the gradient by running average of its recent magnitude. coursera: Neural networks for machine learning. Technical report, 2017.
Xiaoyu Wang, Xuxing Chen, Shiqian Ma, and Tong Zhang. Fully first-order methods for decentralized bilevel optimization. arXiv preprint arXiv:2410. 19319, 2024.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. Journal of Machine Learning Research, 21(219):1-30, 2020.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint 17X8v:/708.0774: 2017.
Xingyu Xie, Pan Zhou, Huan Li, Zhouchen Lin, and Shuicheng Yan. Adan: Adaptive nesterov momentum algorithm for faster optimizing deep models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
Yuege Xie, Xiaoxia Wu, and Rachel Ward. Linear convergence of adaptive stochastic gradient descent. In International Conference Artificial Intelligence and Statistics, pages 1475-1485. PMLR, 2020.
Wenjing Yan, Kai Zhang, Xiaolu Wang, and Xuanyu Cao. Problem baoblem-parameter-frrr free federated learning. In The Thirteenth International Conference on Learning Representations, 2025.
Junchi Yang, Xiang Li, and Niao He. Nest your adaptive algorithm for parameter-agnostic nonconvex minimax optimization. Advances in Neural Information Processing Systems, 35:1 1202-11216.
2022.
Junchi Yang. Xiang Li, Ilyas Fatkhullin, and Niao He. Two sides of one coin: the limits of untuned sgd and the power of adaptive methods. Advances in Neural Information Processing Systems, 36: 74257-74288, 2023.
13

---

Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems, 34:13670-13682, 2021.
Yifan Yang, Peiyao Xiao, and Kaiyi Ji. Simfbo: Towards simple, flexible and communication-efficennn
federated bilevel learning. Advances in Neural Information Processing Systems, 36, 2024.
Yifan Yang, Hao Ban, Minhui Huang, Shiqian Ma, and Kaiyi Ji. Tuuning-rree bilevel optimization: New algorithms and convergence analysis. In The Thirteenth International Conference on Learning Representations, 2025.
Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv:1212.5701 2012.
Xi Sheryl Zhang, Fengyi Tang, Hiroko H Dodge, Jiayu Zhou, and Fei Wang. Metapred: Meta-learning for clinical risk prediction with limited patient electronic health records. Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 2487-2495, 2019.
Yihan Zhang, My Thai, Jie Wu, and Hongchang Gao. On the communication complexity of decentralized bilevel optimization. arXiv preprint arXiv:2311.11342. 2023.
Shuchen Zhu, Boao Kong, Songtao Lu, Xinmeng Huang, and Kun Yuan. Sparkle: unified single- loop puilal-dual framework for decentralized bilevel optimization. Advances in Neural Information Processing Systems, 37:62912 12229222-9777 2024.
14

---

A Additional Discussion on Related Works
Bilevel Optimization. Bilevel optimization originated with [Bracken and McGill [973] and has seen significant advances in both theory and algorithms. Early methodological approaches [Hansen et al.. 1992, Shh et al., (005) predominantly addressed these problems through constrained optimization formulations, treating the inner-level problem as a parametric constraint. Contemporary research has increasingly focused on efficient gradient-based methods, which fall into three main categories:
1) approximate implicit differentiation (AID) methods (Domke 2012 Liao et al., 2018 Ji al.
2022 Dagréou et al., 2022), which use the implicit function theorem to approximate hypergradients:
2) iterative differentiation (ITD) methods [Maclaurin al.) 2013 Franceschi et al., 2018 Grazzi
et al. 2020]. which leverage automatic differentiation; 3) Neumann series- based methods [Ji et al.
2021 Yang al.J [222]. which approximate the inverse Hessian using truncated series. However, implicit differentiation in bilevel optimization requires accurate inner problem solutions for each outer variable update, leading to high computational costs large-scale problems. To address this, the researchers proposed solving the inner problem with a fixed number of steps and computing gradients with the "backpropagation through time" technique [Shaban et al., 2019 FFanceschi et al. 2017). Nevertheless, this approach remains computationally expensive for modern machine learning models with hundreds of millions of parameters. Recently, there has been a surge of interest in using implicit differentiation to derive single-loop algorithms. Ghadimi and Wang (0018) introduced an accelerated AID method with the Neumann series. Yang et al. [2021] proposed a warm-stan strategy to reduce the number of inner steps required at each iteration. Additionally, Li et al. [2022a] introduced FSLA, a fully single-loop algorithm for bilevel optimization that eliminates the need for Hessian inversion.
Adaptive Methods. The introduction of AdaGrad [McMahan and Streeter 2010 Duchi et al. 2011] marked a milestone in adaptive gradient-based methods. Originally designed for online convex optimization, AdaGrad quickly evolved into a foundation for deep learning algorithms, spawning numerous variants such as Adadelta [Zeiler] 2012). RMSprop (Tieleman and Hinton 2017]. and Adam (Luo et al. 2019 Xie et al. 2024]. In particular, AdaGrad variants with normalized gradients, including A Levy 2017]. AcceleGrad [Levy et al.) 2018)), and AdaGrad-Nomi (Xie) et al. 2020), introduced adaptive stepsizes that eliminate the need for problem-specific parameters, establishing themselves as effective parameter- free methods. More recent refinements, such as the Lipschitzness parameter approximation [Malitsky and Mishchenko [019]] and the restart mechanisms [Marumo and Takeda| 2024]. have further enhanced both performance and robustness. Additionally,
Yang al. [2033] provided foundational insights into mainstream adaptive methods, laying the
groundwork for their applications in distributed optimization [Li et al. 2024 Yan et al. (025).
Adaptive Minimax and Bilevel Methods. Currently, some research has begun addressing adaptive
stepsize design specifically within the minimax optimization context [Li et al. 2022b] Huang et al.. 2024a b) However, minimax problems inherently possess simpler structural properties compared to bilevel optimization problems. The nested structure inherent in bilevel optimization introduces addi- tional complexities due to the coupling of variables between the upper and lower levels, significantly complicating the design of adaptive stepsizes. In centralized bilevel optimization, a few adaptive methods have been proposed. For instance, Antonakopoulos et al. [025 proposed a doublc-loop adaptive algorithm utilizing mirror descent, which still relies on the unknown strong convexity param- eter of the lower-level function. Similarly, Yang et al. [2025] introduced centralized adaptive method achieving convergence rates comparable to well-tuned methods. However, tuning hyperparameters in practice is often prohibitively expensive and becomes considerably more difficult in decentralized scenarios, thus making the ability to automatically adjust the update dynam- ics particularly crucial [Li et al., 2024). Nevertheless, achieving such adaptability in decentralized bilevel optimization remains profoundly challenging. Specifically, decentralized bilevel optimization necessitates carefully orchestrated updates across primal, dual, and auxiliary variables to manage the nested structure effectively. Additionally, the hierarchical structure of decentralized bilevel optimization introduces multiple coupled adaptive stepsizes, significantly amplifying heterogeneity across agents. Without meticulous coordination, the resulting variability can degrade convergence performance. Moreover, the decentralized setting requires simultaneously managing network-induce communication errors and hierarchical bilevel approximation errors. To achieve convergence rates matching those of optimally tuned methods, adaptive decentralized bilevel algorithms require an even more precise theoretical analysis, as these error sources interact intricately. To the best of our knowledge, remains an open and challenging question on how to leverage adaptive methods to design completely gabble-pprametter free algorithm for decentralized bilevel optimization.
based on AdaGrad-Nome
15

---

B
Proof Sketch
Lemma D.2
Lemma D.3
Lemma D.6
Lemma D.7
Lemma D.4
Lemma D.5
Lemma D.8
Lemma D.9
Theorem 3.9
Lemma D.I
Lemma D.10
Figure 3: Structure of the proof
Figure illustrates the structure of the proof. Next, we present the proof sketch for Theorem 3.9
Proof Sketch of Theorem 3.9
We start by introducing the two-stage framework outlined in Lemma to examine the progression of the gradient accumulators m, m and m... This framework divides the iterations into two cases: when the gradient accumulators are below or exceed predefined threshold. Using this structure, we derive two descent lemmas in Lemma D.I for the objective function, corresponding to these two stages of mē.
Step 1:
Step 2: Next, we derive tail bounds for two key components the descent Lemma D.I Σk=k, |[ [(x,dall
(in Lemma D.2 and Ei=k, [V [V..(xx. (in Lemma D.3 where it2
02+1
Ex41
and hy represent the cutoff points corresponding to the second stage the two-stage tramework of Lemma C.5
Step 3: Using the bounds derived in Step 2, we establish upper bounds m and ž in Lemma D.4 and Lemma D.5 respectively. Based on these results, we derive general bounds for
vIl
[V, vx)ll and Et_ k
IV.. with ko E [0, t), as
Jemko kp
m
Ao=ko
m
8k+1
shown in Lemma D.6
Step 4: We then analyze the consensus errors for the primal, dual, and auxiliary variables in Lemma D.7 By combining these results with Lemma D.6 derive the upper bounds:
(i.. [m EE [V,1(&L. and Σk=kp (e with respect to the con-
m
sensus variables 3g. Tt. and Up in Lemma D.8 where ko E (0.
Step 5: Additionally, in Lemma D.9 innossisennc errors in Lemma D.I
derive upper bound for the term associated with the By substituting the results from Lemma [D8 and obtain the bound for mi as presented in Lemmal D.10
Lemma D.9 into the Descent Lemma D.I
Step 6: Finally, by combining the results from Steps 3, 4, and 5, we establish the convergence of Algorithm based on the descent analysis in Lemma D.I
16

---

C Proofs of Supporting Lemmas
Lemma C.1 (Lemma 3.2 in [Ward et 2020 For any non-negative a1,..., 0T, and a1
have:
T Σ
z log Σa +1.
1=1
11=1
Lemma C.2. Under Assumption 3.7 and Assumption 3.2 we have the following basic properties:
1). ( Ta-ssmoth with respect to I, where T. = (T.31 Ir (1
Ciay
2
2). y" (T) is Lyp-cipccitzz continuous with respect to T, where Tyg == Ciau;
3). The gradient estimator V f (. G. is (L1,2|1|] + L.a)-Lipschhtt, continuous with respect (#. () and Liipschpc continuous with respect 0;
fz, g. 0) can be bounded (2, Cla,, ||||| + Cz.
Proof. The proofs of 1) and 2) can refer to Ghadimi and Wang 2018 For 3), under Assumption 3.2 we have:
Vi D1, 8) - (z /2. u)ll
V V 01) - V 02)1l
|e|| [V V. (8)
[I4,2|00] + T,,1) (1 - 32 + 00 Fell).
and
[V, Vf 12) V V, 9
|| - 82ll L,, T2
(9)
By Assumption 3.2 we can easily prove 4) as:
|V u)ll <
| ( || | [V, 5) S Ct.y |ا| + C
(10)
Then the proof is complete.
Lemma C.3. Under Assumption 3.1 and Assumption 3.2 we have basic properties of the linear
syseetffncctin r in Eq. as follows:
1). r(z. D. 8) is p-strongly conver and Styy-h with respect to ē; continuous with respect to (ā,
2). Ver(ā, J. 8) is [Lr2|| +
3). Vur(ī, D. 8) can be bounded as V..(( D. T)ll < City ||||| + Cfyi
4). o² (I) in Eq. 3 can be bounded as ||0* (=)]l < Ctx and v² (I, D) = arg min, r(t, 0, 0)
also be bounded as ||00 (z. T) Cta
5). Vf U) is T.p-Iipschitz continuous with respect to (). where T.f max Crulea IT,,,T.) Tu,)
V.r(z, is Lipsschhitz continuous with respect to (z, (8,0.0) where L max
Ctubi L,,1, 3:
7). o (i) is Lipiscchit continuous with respect to and v- (ū, 7) Lipsschht continuous with respect y. where Lo = (Ls, +
Csy hi. (1 + Ly) and L, L + Cr, L1.2
n²
2²
Proof. First of all, since V. V.r(E, v. 6) V (f, D). know μl 3 V v). Thus,
according to Assumption 3.1 and Assumption 3.2
we have:
V.V v. . 0. 22)
V (a, -211 S Ci,, رū 02 || (11)
17

---

Then 1) is proved.
Next, by using Lipsehitz continuity in Assumption 3.2 [V ;,, 6) V. (2,, 6)
we have:
S V 01)
(2) ū2))
S ( + (1 32ll + ll 02ll)-
(12)
Then 2) is proved.
By Assumption
3.2 we can easily prove 3) as:
Ver D. u)ll & V V +| - Ct,y ||5ا| + +Cr-
(13)
Next, for u" (ā, 9), we have:
V,r(z, v. 0 0" ",
(z. 0,
(14)
which indicates that
C₁ (15)
(f. - -
V (.,0)) < v 1 ()) 11 .) -
Since o" (x) is special case where 0r (z) 0- (σ. 18 (z)) 4) is proved.
By Lemma
we have:
f (f1,91,01) V5 02)1
< [f( 01) ff U2 f 72, 81) Vf T2. 12)
- (Z4,2||011] + Lr. - 321l 1l - 52ll) + L,,1 02/
$ ( [1 - 52ll + U - 72ll + 00 12))),
(16)
where L, = max Cr.bie LI,1, L1 Thus, 5) is proved.
For the proof of 6), we have:
VV 21, 01) V vūr 02, B2)
= V 81 - - 12))1
T1 -
= V,, ) V, , [
< V, 91) - V, V ( 72
b1 + [2
+ V (T1, M1) V 02) I|
(
1,2(11 Tzll + 11 - 22 C 1,, |6
321l + L (1|=1 -21l + +101 -72ll
Cr,41. + Ls.1 (1 T2 + || - T22l) + Ci,y |, - 621l
< L. (1 - T22l + || - --2ll + || - 02 }),
(17)
where (a) uses Assumption 3.2 (b) uses Eq. 15) and L, = = Cruhez + Lg,1 Cryp J. Then the proof of 6) is finished.
The proof of the first part of 7) can refer to Lemma 4 in Yang et al. 2024]; ;; for the second part, we have:
1 (T. 01) 6* (6, (T,
= V, V
V, (V. -V
+ ||11://///3aa0331111333333311110
Lf.1 - +
1|
1
L
Cj, L12
||
52|
(18)
1 222
Thus, the second part of 7) is proved, and the proof of Lemma
C.3 is complete.
18

---

Lemma C.4 (The Upper Bound of k= 1 12x 112). Suppose Assumption 2.1
Ex=
Assumption 3.1
and Assumption 3.2 hold. Then, the consensus error for the primal variable satisfies:
2
8 1111+00 + (2)
x
17 - - PW
Σ h=
(19)
(w-Pw)?
0=
where A 1xxo L5nl 12 is the initial consensus error for the primary variable a, which can be set to with proper initialization.
Proof. By the updating rule of the primal variable, have:
x 1/
W (x+ -- Qiti VF(x, Vr. yc. vo)) - -J -J(x - -70 (x,,, vI
(0)
S (1 N)pp ||x: 1= 1+ 1
2) pw pw729-71 [V vell
1 2)
+
1+
7 (1(7) - 9 I) A (x.:
(6)
+ PW ||x, - 16 + 2- + pw)
9,+1
2
1 Pw
2 2 [1 + pw Jow
[[(Q - F(
(20)
1 1 -P
where (a) uses Young's inequality and we take X = 1-ow in (b). 2pw
By the definition of C in Section 3.2 have:
[1( - Ge+ I) Fx., yr, vo)l S G3 [VF( Yr. v.)1
(21)
Thus, summing over h: o,....f t 1, we have:
X
18
PW
b - | + 4n
(2)
(-1
1 1 Pw
Toi1 Fx Vx)
2
PW
2
k=0
k=0
822pw (1+ 22)
t-1
<
||xo - 12
9
[F Vk)
(22)
PW
(w-ww)
k=
Thus, we can get the result in Eq. 19
and v be updated over Tr, Tr, and T3 iterations, respectively. Suppose that the sequences {m{), {m²), and (mī) are generated by Algorithm For any constants Om 2 my Cms 2 my. and Cmv 2 my the following statements hold:
Lemma C.5. Let variables
(1) Either my S Om= for any t < Tí, or 3kg < Ti such that m S Cm=, m +1 > Cm
(2) Either my < Cmu for any t < T2, or 3 T2 such that m I Cmu, m Cmv-
(3) Either m. S Cnn for any t < T3, or 3kg < T3 such that my, < Cm., m > Cmv.
The proof is analogous that of Lemma 4.1 in Ward et al. 2020]. We will demonstrate the argument for part (1) concerning m.; the proofs for parts (2) and (3) follow similarly.
Proof.
Assume that m > Cmr. Since Cm= 2 m and the sequence (mf) is monotonically increasing, there must exist an iteration kn S Ti where mi S Ome and m. > Cms. If no such k exists, then it must be that m. Cm= for all t < Ty. This completes the proof for part (1).
D
19

---

D Proofs of Theorem 3.9 and Corollary 3.11
D.1 Notation
We stack the gradient accumulators as:
m = e m2 ................................ m _ RR
m = [, ,., m,,e E 12nxy
m == [mi m....... ; E R=x
(23)
Similarly, the gradient vectors are stacked as:
Ve,,, ve) = V (Z V2222 12,1 v2.),... (n Nn vnaal
VgI( = ( Vyla(12,, v2,), ... (an,,,,,,an))))
V. vi) == VV. W1 U1 Ver2 22 U2,)) Vonn(Enty In un,))]:
VyF(x,. V 22 12.),
VyIn(En,ts vo.))
(24)
For notational simplicity, we also use g, B and g to denote Vi(x,, ve). (x,, ye). and V v, Yr, vt), respectively.
The stepsize discrepancy vectors can be defined as:
1
11
q. 99,t 4: 92.t
9n 4:
u, [ui, ū, 222 U,
n,t
8,
(25)
2, [
2 22,
Additionally, for ease of presentation, we define the following notations:
Jt
Σ n
1= Fi,t
Vitto i.
(26)
Di=1 9..t
T.
2
25.0-
We define the following metrics to represent the level of stepsize inconsistency for the primal, dual, and auxiliary variables:
( 41 1)2
[ui U1 1)
E 2x 1- 2
2 = sup
2 = sup
< = sup
(0r
iE|n).100
(zz 12
ie xe(n]
(zr 1x-1)²
(g.1t - 91 1)
(uit) 2te 1)
(3 - 2, 1)
of inf 1s00
inf kE(n),20
o inf eE(n],0200
(27)
(q. 1)
(u, 11
(z 1)2
Below, we define several preset constants for notational convenience their first use. We first define some Lipschitzness parameters for (()) as:
Le2Cre)
(1
City 1
La
L
(28)
1
1/2
C2 Li
L: max 2
+ I27
22
(29)
112
Next, we define the following constants as thresholds for parameters mi, my and my as:
8nY, I.p (1 + (2) .
Cm- == max
(30)
2o
22 (p + L1,1)
Pyltta,1 my 640 1
Cnn == max
(31)
v1+ oz
L1,1
20

---

2 (1 + (3) + Clua) 2uCinn my. 64ag 1, Cwuv
Om == max
(32)
V1+ 02
1 + Cluv
C2 = Crav Cmn-
(33)
The constant dg is defined as:
4(2 + (
n (LS.))
a0
112
8 +
10110
P
+11 2L1,1 ( + bni1) (ul))
32 pw (1 + [H)
8y (1 + (g) (u + Lr,13²
+
+
n(1 PW)?
Yolk
myJut1,1 v + o²
16(μ + Ci
nI1,255 +L
2
17/011 v1 0 4w2 (1 +1+ (g)
1
1(,)2 1V1+ 2IIIVI+ oi
2g(1 -PW)2
14p2
np
121 + () + L1,1)
PW P. + +1t (2
2 22 +29 + City )
71
npC vy To (1 pPW)
mpc 1y m8n / 1
(34)
D.2 Descent in Objective Function
Lemma D.1 (Descent Lemma). Suppose Assumption 2.7 Assumption 3.7 and Assumption 3.2 hold.
Then, no matter b1 in Lemma C.5 exists not, always have:
$ (Z(41)
Yo9xt1 (2 (2% (1+ (2) + 13)
I (T+))
(1:))1
D.
n
Vuf Dr. T2)l1
L27r V De. 12 112
2
Log (1 + (2)
Øc+1
gr+1
TxI.
(TuaCto+
V 3.)11
(q.11)
+ 2
F(xx. Vo)
2n22 11
a++1
n4++1
(35)
Additionally, if k2 in Lemma
C.5
exists, we have:
(ā++1)
Tall+11 (2 122 Loge (1 + 2)) + T.7)
7/2
< ((F.))
VV(I))1
A
7
Ya
V V Vt, 11)
Vur(Tr, Je, 02)1
27
(q.11)
A
a++1
122
ndp+1
L2
T L2
LI2Os, T.s..)
2)
| V F2l1
(36)
2p²
1t
1
a++1
where ::=
= max
1i, (2("0t + 17,2)
C02 (1/0, /C9,13,
2
V2Cies
Proof. By the smoothness of Φb we have:
((2.+)) ((x)) s (VD(T)) Re41 -x,) + La |[++1 2.112.
(37)
21

---

Noticing that the scalars qr, Ug and 2, are random variables, we then have:
Φ ((+++) (1t))
Vo(T,),
1
Vx(e v.))
(9+11)
VF(x..
9
n
nd++1
YoLo
9
(9it1)
F Vc, ve)
(38)
20(+1
Then, bound the inner-product terms the right-hand side (RHS). Firstly,
( 1
Ve.x).
1 Y..Vo. 1 VF 17. 16,) + 1 VF 17c 16,)
(āt),
1
Fx v.) VF(1T. 1ÿ. 10:)
n
n
+ 2
1
(T.))
ff Dr - V. De. 12)1
I FF(x, V.. v.) 1 n
< |
(F 17. 18,)
+ + 1 (o.,) v (T, De. 7)| Vz,,,,, Dc. 8.11
(39)
Additionally, the gradient approximation error satisfies:
[V (z,,, a)ll
( (i.) ff De, 81ll
< 15. ( 2/I Dr, v., (Tr,,, 0.)11
S 4/ V , (Z, (3:)0 V (o)
V |1
(ft) 6:)1
22
C2 T2
13,1
110c - v*()))1 110e-y'(a:1l1
20 |1 2² (x.)11
12
I L (11 - y² (++)) + +110 - v((e)l1)
(6)
L
1
5 11
V (1) - -Val(T,, v (T.))l
+
Vrr Vc) Vor Dr, 00 (f:))
n
(9)
7.2
212
V 0111
V (.re Gr 0.)1
12
112
2Ī22
||V or Hr 00 (xx))
122
(4)
1
2
2L2
L1,2 + I15,1) )² 11 - (x,))
V
(Tre 32) +
V.r 2211 +
112
122
112
[
2L
L1,20% + Lza () Vi 12
2I²
V Fe, 04)11
(40)
n12
11
112
where (a) is using 4) in Lemma C.3 and L == max 2
+ L7,1
.22 ; (b) and (c)
use the strong convexity:
(c) and (c) result from [Z, (*)) and Ver(z, yr (z), (5))
(d) uses Lemma C Then substituting Eq. (40) to Eq. (39 we have:
I
Vd())) n
F(x vi)
22

---

(0)
13
L
L
[L
+ + )1 (V Be)1
D +
+
2/12
7
1?2 Ver(Tr De, 01]1
1
V (Te, ye, 0e)1
(41)
n
2
where (a) uses Lemma C.3 and A, x 1 ly: 18ell + live 1oll 21 is the consensus eπror for primal, dual, and auxiliary variables.
For the second inner-product in Eq. 338 using Young's inequality, we we get:
(VD(2))
(9rt1) VF(x....v))
(9:t1)
+2
Ve. vo)
(42)
n4+11
8
ng++1
For the last term the RHS of Eq. (38) we have:
recalling the definition of stepsize inconsistency in Eq.
27
N/x To0
11+1 IT
(irt1)
(F(X.. 2
20++1
n
Y/ 9 (1 + (2)
11
(0)
2n7 Log (1 (2) / (Tt, Dr, 6.)1 2% F.2 Lotel (1+ Sg)
D.s
(43)
where (a) uses | (x., Yr. 12 < 2 17. 16 + 2[3( - 15, + lly:
17 11 + 1|v, and Lemma
1 12) [1 1 T, 1 2 < | 17. 1 18 = || f D1 T7 2
By plugging Eq. 441) Eq.
42 and Eq. (43) into Eq. (38), we obtain Eq. (35)
Bo (1+
Moreover, if k in Lemma C.5 exists, then for t 2 k1, we have m Cm
20
Therefore, from Eq. (35) we can get Eq. (36)
D.3 The Upper Bound E
IV vxI.
k2
Mp+1
Lemma D.2. Under Assumption rounds is T. If 22 in Lemmal C.5
3.1 and Assumption 3.2 for Algorithm 7 suppose the total iteration
exists within T iterations, for all integers t [k2, T1, we have:
V (x)(
uk+1
2nC (1r + TT,1)
8A
32 (1 (1+Gg)
( ( + Tu,1)3 (m=)
+ 2 + T1a))
+
+
12%1/ / o7
1 PW
26 - -PW)2
Tyft?
Tull
22 PW (1 + (2)
(μ + 13
2L1,1 + (1,1),)+
8 (1 + (2) (1x - I2,1
20 - _pw)?
7n/12
Tyll
7guLi,1 3o / 1 + o%
32 (1 + (2)
(1+ + LI
2L1 + L(,1)
+
)2)
7/p22
Volk
8 2 12 (1 + (2) (# + 2
F V&)
y F2 v1+
(44)
(m 22 max { {m m
kk
Proof. For hi < l < T, we have m S Cmv and m > Cmv. For any positive scalar X using
Young's 's inequality, we have:
1 1y4 - (2 (1 de+1)
1
|yet - 1y 1x:))) (1
11 (xt) - 2/" (5r+ 1112
n
Aet1
(45)
23

---

For the first term on the RHS of Eq. 45
we have:
V141 - 1y (Bx))
n
1 |Ive - U 1yp-~uu7 V (x). 1y (xx)]
n
1
llye 1y" (xx))) + My
||u L v.)
1 n
Σ
2d 2 7o wis) -0 vi+))
n
m
1 Σ 20+4170 7/1
( - 3
V Vi
71 i=1
11+1
1y"
(I+ (x+())))]]
+ " 1 1+1 v, L(x,,
20, 7/ 784((1,0...)) v ( (a()))
20,41 1 7/ g/ (2 y (3+)) V
(z,))
71
1
14,++1 - U641
20,+17 7/0
- v
71
ū,41
1
11,++1 - U141
2 1 7/0
(Vyli y une ((())
71 i=1
8,41
my 1
2 (1 + (2)
Ily- (.x())))1
V (x)x
n
n(11 + (1,2)
n
2% Urt1 1 v 1 + o
xx 1y V (xL 11lxx.1y(C (x:))1
n(p + LI,1)
ny (1 + I1,1) 1
[V - [x)) (x)))
muLt,11
(6)
My Tyuithiplin
11:: - (T,))1
n
m(u L111
V1+
mi 1 (1 + (2)
1 |V)((x)0)
# # L1,1
1y (1 + T.,1) + / +
1,), 1y
mub111
niu + L1,1)
(c)
i n(u + Le,))
- 11))())))
v1+ oz
Ty Ty (1 + (2)
| (xxx
+ TA.1
7 1 La.1) oz
27y L + oz
+
||x: - -17,
14p1
n(H + Lt,1)
(
Ty uittt n( + L1,1)
11ye - (x))21 7 /
V (x),
2n(p + L1,1)
24

---

Mo Ny Ln,1 L1,1) L1.)v++ oi 27y 27y"t11 17,1 v1+ + of
||x; - 12,
(46)
npp
n(u + Li,1)
where (a) employs Lemma 3.11 in [Bubeck et al.
2013]. (b) uses Young's inequality, (c) refers to
+ By plugging equation
Assumption 3.2 and (d) follows from mž+1 2 C.v 2
VI+oß
Eq.
46 into equation Eq. 455 we have:
Iy++1 1y" (#1+1)l12
n
1
$ (1+ x(t1)
11yc- 10k--111 12y
11ye
n
11 + L1,1
Yv 1, v1 / + oz
-(1 1
(xx,
2n(11- + L(,1)
Ty Ta, L1a)
270 12,1 v oz
(1 + )111)
+
1x:
1
ny
nln + Lr,1)
1 As+1
(0+( yy (3++1)11
(47)
By rearranging the terms in Eq. (47
we have:
1 -1 /
oz 2n(n + L1,1)
(1 + ((t1) (1+x++1)
v (x).
$ (1 + )et1)
_
1
Vo 7
1ly+ - 1y)
1 11 y 1y (T++1)l12
n
1 M++LI L1,1
Wo L1, L.1)v
+ 2% 27 L7,1 v + oā
+ (1+ + )(t1)
||x; 15,
nu
n(u + Ll,1)
+ 1+ detz
(0)) --" (1++1)11
(48)
We take det1 == To Hubke Since m > Cmv 2 Jol4a btb
in Eq. (31) we have dct1 S 1. Then,
1-b111
have:
Yy u
1 + 0
L(xxxx)))ll
2n
1 oz
(1 + )e+1)
((),
2n
1e + L1.1
(llve - 1y" (xx))) ||y 1y 10"(4++))11 + 2(μ1 + L12))
1Tx) V² (1141)l2
det1
21y I1,1 (14 + 2 / o% 4 [2 / + o
||xr - -17x11
1 L1.1 (lIve - 1y" (x())())1 Ily++1 (F(+1)11))) + 2(u + Lr,)²
Ti ū, 1 180(0x) v² (f++1)ll
21y L2,1 (M + LA,1) )2 / 1 4, Li / + o²
||x: - -1
144
n
(a)
11 + T1.11 (1ly: - 1y" 2 1y" (11+ + 2(μ + 22,1)
|| Re+1ll2
7/ ū, 1
2(M+ + LI,)33 (kra)3/1 oz ALr,(H + LI,)) oz
+
||x - 15
(49)
np
25

---

where (a) uses the Lipschitzness of y (ā). Summing the above inequality over k = k2,.... t, we
have:
Yn k++1 V1+ o²
yx)|l
2n
1 + th
2n
1== k2 -1
11 + L1,1
yy 1y (822 + 2( + L1
ūz+1 | - Fx-1| 112
m
nypla1111
k=
2(u L1,1) 51++0 o + o
+
Σ
||x 1
14
1=mk--1
(a)
11 + I
U1 11. 11 - Voli (00, -0 (Tk,
V Vyli(Ei,
n42
2(1 + L1,13 v 1 4L,, + 11,1)/ o
Σ [ 15x
+
nu
nu
2( + L2
T Y09++1 n
VF (x.. vk) - (Art1)
ūx+1
A F Yos Vis)
7yptLi,11
1=
(6)
11 + L
12422
4 L3 (1+ (2) (H + L1,1)
16 + (2) (1 pw )2
+
Us+ 1 2 4+
F Vk. v=))
177111111111
k=ka
(n + 11,13 1 2L1,1 + Lid) 1
Yk. v2)l2
ny1
4 - 13 I
8A + Li,1)
1+
142(11 (1 PW)
nup(1 pw)
(c)
(μ + 1
16 O + (2)
12
PW
(1 p2)) )2
(n + 11,13 1
(1 + I1,1) oz
nu
16 (1+
11,)3 (11 +
2L + L1,1) L1 + o3
+
+
(1- (I-PW)²
mua
1/
4-2 212 (1 + (2) (1+ T2,1)27
Nk. v2
Σ
nigHtei
k ki 111 [m++1 12 max (m m
(n + 11,1)
44
1672pw Ch (1 (2)
112
PW
7o - (1-Pw) p2)
(n L3,13 /1+ 03
2L1,1 + L,a) 03
42 (1+ 2) (1+ 11,)²
n7/H1411120
16 + (2)
(4t 13,13 / oz
2L
+1,11,1 1 0
+
60(1- pp
np
26

---

16+ (1+
16 (1
(w++ Vutt v1+03
+ 2L11 + L1,1) S o
(1 - pW)2
nu²
ny
4 y (1 + (G) (H 21,22
FF v+)l
(50)
[m 1 max (M
m
A=mii Ae2)
where (a) uses
Assumption
3.1 (b) refers to Lemma C.4 (c) results
from
VV (Vli(2i,,2211 1ilk--1)l & [m
C and [V
Us 1] s [m
2
<
On.. Then, the proof is complete.
D.4 The Upper Bound of Σ ka
I Ne
1k-11
Lemma D.3. Under Assumption rounds is If kig in Lemma C.5 exists within iterations, for all integers t E [ks. T), we have:
3.1 and Assumption 3.2 for Algorithm 7 suppose the total iteration
V R.x, Yk. v2))
ēk41
4m0 mo (n + (,xr)
nnI,2 + 11s.1
8nC (u C(yv)
+
1 / 1+
12: povoi== o²
16( + Olmv)
nL +Lo.11
2
DJ 4 Opn (1+5g)
(uttle 2L1,1
70112
P
1-PW (6(1-ww)
1912
16(μ + Civv)
nLI12C52 +T.g,11
4rm (1 (g)
(e+ Lr,1) o?
7o112 /1 11+ o2
11
2B(1 -pw)2
n122
21 / 1 + o2
2 (1 22) + LT,1)
ks
VF Vks vAail k
Ammin (A] 1,82
6472pw 13(μ + Cl (1 (2)
21 + () + Ciay )2
+
1o 70 p2)
MCI, 7 // / 0
FF Yk. vx)l
k=min(kr 11
+ (8
A(p + 4(p+
2 (nLiaC + L111
Σ
+
112
1
m
k=
1620
6472pw Cnn- Sq)
12(m
Clyy)
T221 + Cipy)
+
+
(51)
1 PW
2o -pw)2
MC No
12:00 1
Proof. For ha 1 T, have mf+1 Omn. For any positive scalar det1, using Young's inequality, we have:
1 [| 10 (T++1))
(1 + )++1)
Ve+1 1 (xx)))) (1 1+
1
l| (ix) 0² (f
det1
(52)
For the first term on the RHS of Eq. 52
we have:
Vt+1 10 11 (f++1)|12
1 P| (v: - Y, R(x,, 1 (a.))
(0)
|| -%o R,
10" (z.))
27

---

-e 7 R(x:: v:)l V 10 (x:)1
"
22 To V
Vori yir v4,e) Use
Vi,e - (ze))
n
- ++1
2 Ty
1.++1
Veri(aru Wh.tr vr,e), vs, v((e))
(53)
24+1
where (a) uses the non-expansiveness of the projection operator, established in Lemma of (edic et al. 2010 Then, for the last two terms on the RHS of Eq. (53). we have:
2% 2 Yot Vori(Fr Uhies 04 (x))
71
1
2 79
2,1+1
Vorilose Vtd) 0 (it)
71
2%
241 ( (oT V Vorleeu 07 (Zr)), use r. (2x))
n
2%
*1l (V Vo (Fs, - (1) vit uz (T))
-1 71,+
2%
W. u/ o (3x) (8:)
*141
1/+1
2%
21,4 4+1
Us 10, (Bs))
*111
2/41
27 V
V R(x,, ye,
n( + Cl
7v 2 02 C
Ri,, yr, (Tx)) V.R(x, 1z
nuC
2pCr, YoZth
4uC1 my 702
I|ve- 10 (x:)11
|/ (T,))
nl + City)
n(μ + Cl,y)
(6) NoZ711 /1 + o2
27 / σ²
R(x,, v.)l1
V R(x,, (o")
n(ju + Clnyy)
a(H + Ci,y))
1o + 02 Clun)
R, Io (o:().)
V R(x, 1y (7:), (x:))
muC 4y
2pCrny 7o
l|v. 10" (i:))1
nln + Ct,s))
(
No2 /1 + 02
V. |. Nc, v1
2uCiyn To
1| 1v 1x:)11
n(u + Clyy)
n(u C1,o)
4%,,,11 L2, /1
4 / 1 1
1o V1 o + Clyy)
X1 -1, 12 2 +
n(u + C(.r))
n(u + Cl,))
mpCinw
R(x, Nt. 10" (z:)) V. R(x, 1y" (āt), 10 1xx)))
7v 2 V o²
2μ0r 70= -1 n(u+ + C,,,)
V.. v.)
1| 1u" 1w(())))?
n( + clny)
4%,,, 1.2 1 + o
12 1 oz
7o v 02(u + Clpy)
x; 12
10 + Clyp)
n(u + Clyn)
mpCinp
28

---

(L1,ellee* (3+)ll + L1,1) lly: -
(
To v + 02
2 7o
vo)l
llve - 10 (2+)11
nlp + Olar)
n(p + C(xx)
1 T2 0
12/02111 v 1 +0 oz 7o v + oz + Ciuy)
|x,-18,11 +
n(u + Cluy)
n(u+01
npClus
(ntuaaho 1r
2 Lega
lly. - ly (x+)))
(54)
where (a) follows from Lemma 3.11 in (Bubeck et al. 2015]; (b) uses -Ila - b112 < - + ||61
since ||a b + bll2 <2 b112 + 2 2| (c) uses V R(1, (z = 0: (d) and (e)
use Lemma Plugging Eq. (54) into Eq. (53). we have:
|[ 1s (x:)11
n
1
2uC yo T02(+1
4 1 o²
<
1
1Ive-10 1x:)11
1x 1
1
+ Olu0
n(u + Ciuy)
202411
No (1 (2) VI+
+
Ros, vo)1
n
1 + Ciuy
2%0 o + 7o + Chw))
+
(nLia + Lsa ) 2 1x,()1)
+
72
1 + Clav
H
2n ToRe11
1
- 10 -v= (x))1
a + Ciuv
71
7o + oz
V R(x, yes vt)] + 4 12 1 T2V1+
oz
1xx 1Tel1
2m( + Ci,y)
nlu + Cirs)
2% 1+ 1
To 7o + + Cluu) )
2 (ntuaate L1,11 )² 2 (x:))l
a
1 + Cl.
MC
11
(55)
2xu(++C)xx++ VI+07
where (a) follows from Zes1 2 m8+1 2 Cmn 2
Combining Eq. 55) with
Eq. 52
have:
|ivet 10 (T++1)11
< (1 + 2et1)= 1
2 7ož7+1 Po
1
11v. ((ve-1u(EE)))) (x:)l
11 + Oiyy
Y0 v 1 o²
-(1 + )et1)
Vo vo)l
2m(u + C1,7)
2n I+ +
/o + 02 + Chyy))
(nLnzCts + T.p.1
+ (1 + )et1)= -
11 +1+00g Cluy
1C
1
4%0 L3 1 o²
=x - (2:))1 + (1 + Set1)
||x
17.112
nlu + C2,y)
+ 1
1
|10 - x² (1
(56)
Jet1
By rearranging the terms in Eq. (56). we have:
(1 + (x+1) 702771 /1 + o² 2n(u + Cln))
V Re Ve, v2)l
29

---

s (1+ + ) n
1
2uC yy 7024t1
l/ve 1ov--1e'6 (x:)11 -1 -
10 (12+1)1)
μ + Cruy
n
1% v 1+ 1+ oz
Yov + +z + Cluy))
(nluz Leg.1
2
+ (1 + )et1)
n
1 Cluy
10
4702,-1 L22 1+ 02
- - 1y (x+))1 + (1 + det1)
17 11 1xx+
n(u + Cluy)
1 1
(0x())) - 0² (1++1))1
(57)
det1
We now take det1
yu u+
Since že41 2 m²+1 2 C. 2
2n0 2o
in Eq. 32 we have
u+0
d++1= S 1. Then we get:
Yo 1-
1 V o
V.R(X, y., Vill
n
Yo2 o
< (1 )et1)
V R(x. Vr, vz)l
n
(0) 2( + Clyv)
||v+11 10 (1++2)11
n
4(p + Clny))
(2n- (270V1+0z
To 7vv + 0 + Clyyo)
(nluaCto + Ls.1
+
a -0 Cius
n
16 L, L + +0?
- llyy,
1y 13:)]1
1|x, 10,,11
+ +2( Olyv) (1+
1 + Ciny
L/l13, B0+1l12 112
2p 2
(0) 2( + Olun)
(llv, - 10'--1'(p (ix)) -1lve11 - (8
n
+ 1 (8rvV++0 of + 4 + 02 + City))
(nluaCts + L1.11 )² Ettllixe 1y (2
MCipx
8L2(M+ Cl 0²
2(16 + (2n
Xx: 15,
l|āt - 1141
(58)
mppCi.
1Otpp 70=1+1
where (a) multiplies both sides of Eq. 557 by 2( + Olyp) and uses Se41 S 1; (b) uses 241 2
2n0 Take summation of Eq. (58), then we have: #+00
mi+1 2 Cm= 2
2 V 1+ o²
V R. Yk. vz)l
n
V.
1
k=
2(n + Clrn)
2( + 12L
V 10 (i
Σ
E4+1ll0x - xx+1ll2
n
1C Yo
k=
1
4%v 4%0 + 02 + Ciny))
InLuzCte
+ +1s11 )²
2
n
pCln
H
8T2(1 +
Σ
a lyy 1xx(
Σ
1xx 15x11
k=
R=
30

---

2( + )luv)
8L2(1 + C2 11
\ - 10" (T 11]1++
X
1
n
nuCl
h=0
2( + )ipy) 22
1 Vk. - -oo
9
+
Σ Ek+1
No9k+1
F yk. Vi.
HC 70
Rimii
1
47 Poo/i
02(m1 + C(ap)2)
(nhiz + L1s11
2
8%vv++ +
1C
1
Σ k+1 Ily 1xx)2
k=
(a) 2( + Ciny)
1| - 1s" (Tkg (1k1-1)11
27 [1 + (2 + Clyy)?
Σ
Ek+19 2
FF(X Yk: Vk.
1n 7v
k=
1
4%v 02 + City)? )2
I + L1g.1
2
+ n
8% 1
HC
16 + CI C
m 11 1 (xx)11
muC (1-PW) Pw)
k=
64 pw L2 + (1 + (7) 1
9ot1 VF(x
npCr, (1 pW)
R=
(6) 2( Ciny)
Vikks- 10" -1) ?
16 + C
A
4-2 Che (1 (4)
1 PW
(1 )2
64h T234 C1,,)(1
21 + (2 C1 City )2 (2) V oo
+
mpC (1 -pw)2
mpC Co
IVF Yks vx)ll
4% V 1 o2 Clpu?? )2)
8% 87
m 1
(-minnki-1.ke
nnli,0te + Log.1
2
(59)
m 1+1
where (a) uses Lemma C.4 and (b) refers to Assumption 3.1 and (1 Ci (mf,,,) 12 S C.. Further, the approximation term
[| 10" (xxa 1)
satisfies:
|| 10 (ix--))1
(a)
II 01,0s, 1
2
V T' T (2 o - 1
2
i=1
+
U, - -V Vori(Ei, (T 00 (
122
(8)
2 InTu,2Cia + Lo,.) 100p----1""
4
1
5
+
( 2
11
112
31

---

412
Xxx
18kg-11 111
112
no
4 n
+ +I1s.1)
118kg-1- 1y--1-1y( 10 (1bgg-111
24,kg
112
1
S
A
4 PrapwCi O (1 Gg)
(60)
n²2
1
PW
%6 pW) )2
where
(a)
the strong convexity; (b) follows
from
Lemma
and
TTi y (Inz- 1), u (1)
= 0: (c) refers to Lemma
C.4
By plugging Eq.
(0)
into Eq.
559
have:
Yo 2 o²
Σ
Vk.
n
k=ka
4(p + Ohynn
1 + &1gs.
1oyk-1-1yy'00 (xx
mp2
8(1= + Crux)
n
11 (
1, Di-as-1)11
n4p
647 T2 Ci (1 + S9 1 21 + b)
Cigy) Cign)
mfcCt v0 (1 - -pww }
nyC y0 Cm
| Vki vx)ll
4% /1 1 ozZ + Cluy
87 V
m 12
n2
k=min 11,
nb1,2s,
2
|I Lxx, yR)l
I.g.1
11
112
mx+1
l=
164
647 Pw
C (1+ (G)
12 + Ciny)) 12(p + Cin))
+
+
(61)
PW
T (1 pw)² )2
nuCht
n422
Our next step is bounding | ly (5x Il the RHS of Eq. 61) in two cases. The first
case is m S Cms. In this case, by using strong convexity of and the definition of m we can
easily have:
nC2 mi
11ya-11- 1y (T
(62)
1
112
For the second case, when m. > Cmv, note that ky exists and K3 > k2 by Lemma
C.5
By plugging
A = T ,ubia
haa into Eq. 47) and noting A I 1, we have:
1 - 1y" (Ftkg1)))
2( + L1,1)
1yy 1y" (8
11 (Txxg 82 (1)1-1)11
7t Tk 11
22yy Ln,a + I1,1) oz
4// 122, / oz
+
+
| 2 15 211
1/
n(u + IT,1)
(4)
2(11 + L1
1ykk-2- 1y 2))1
11okk- 2 Tkg 1
+ 2( 22, oz +
4Ia,1 1 / + +
hs-2
Σ
|x 1F
2122
np
k=U
32

---

43 (2(1111))(++))))) (M+
1y - 1y 11y (Tk2
Uks 1133-1933-1 1 2, 222-2))12
7ightb1111
16 (1+ + (g)
L11) + oo
oū 2L1,1 /
ka-2
9h-1
V&. vx)l
(1 (1-PW) PPW)2
np²
np
k=0
4 + 11,1)² /1/11+00
npp(11 PW)
np(1 pw)
nC mn
4
16 1672PW C (1 (2)
(1 + L o2
2L v 1+ o
112
PW
1o ppw)
11p2
11p1
1672 111+00 (G))
211,1 I o ( L2,1)² / 0
(1 pw)
m412
14
L2 + (2) + La,))
VF Vk. v&)
(63)
111711
Jemmnn 1,22-1)
where (a) uses Lypshipsc continuous and m kg Cmu 2 Tyukia (b) refers to #+
Lemma C.4 (c) follows from Eq. 62p by replacing h3 with h2 since mik I C. and
Mi,k, -1)12 S [ 12 S C m=. By combining Eq. (62 and Eq. 663 we
obtain a general upper bound for || 1y" (#tg- as:
1
11-1-ly"a (Tka
11)12
nO2,
4 +
16 Cm (1 (1+S)) 2
2L
v 1
+
m2
112
pw
pw) )2
np²
1141
16 (1 + (G)
(n + 11,1)² + 1+0 o
2L, 2L, 0
2 (1 pw)
np
4 21 + ( (t.1)
2
| FxR, Yk. v=
Σ
(64)
m
(Ar 1,kg 1)
where define Σ 2i=m Pt for any m > n and non negativte sequence {pr}. By plugging Eq. (64
into Eq. (59) and using V 1F 24, < [mg,] 12 s C n we have:
To
V vx)l?
402 my (μ + Clmy)
(nLI2Cta + -s.11
4t
H
8(p
m
16(μ + C(wr)
(nIa,2Cs, + Ios.1
2
+
112
142
#
A
42 C2. (1 22)
( + L1,1) 22 MI.VI' 1/1+ 02
2L,11 / 02
+
PW
(611-w -2
16(u+Cigg)
472 Noww(1+1)) (1+
(1+ (2 VI+0z
2L 1+07
1412
11
2311 p2)
nya
n1j1
2 22 + (2) L1,1)
kg 2
FV v2)12
Σ
[m 12
k=min (k1 1. 12
64 12 + (1)
(1+ oZ
23223(1 + 22 + Ctep
+
npC (1 }
npp Cm To
33

---

IVF Yk, v12
4% 1 0 + Cluo
Σ
8% S
m 12
n
HC
k=minf -1,
nl
2
V (x
112
m6+11
k=ka
1645
6472PW O (1 [g))
[2(p + City) of
[2 + Cias) myp
(65)
PW
Pw)
)2
Then, the proof is complete.
D.5
The Upper Bounds of m and 3z
Supported by Lemma an2 and Lemma
D.3 we derive upper bounds of my and &t.
Lemma D.4. Suppose the total iteration rounds Algorithm i T. Under Assumption 3.1 and C.5 exists within T iterations, we have:
Assumption 3.2 k2 in Lemma
Cmv,
< k2
m
Cmu + co do Et mimmin (2) | 12 max -
Ve.
z k2.
(66)
where co, dg are defined as:
co = 20 (
n(1 8A
32 C1 (G)
(μ (u+ L.1)3 2L1,1 + L1.1)
12 1+0
Pw)
ng (1 PW)
Yyp12
Tyf
32 (1 + (2)
(1+ L3.1)
2L 2L1,1 L1,1)
87 2 (1 + (2) (1i In,1)
nz (1 -Pw )2
7/y12
7ull
mnguT. LT, 1,, 30 1 + o2
3272 (1 + (2)
(u+ 33,1)
2L1 + L1,1)
87 / (1 + (3) (1 + L1,1)²
dg
n11 - )3)
Tyl22
V/l4
m m / 1 o²
(67)
When such 12 does not exist, m S Cmu holds for any T.
Proof. According to Lemma
C the proof can be split into the following three cases:
Case 1: l2 does not exist. In this case, based on Lemma C.5 we have my I Cmu, and hence
m S C.z for any < because m. non-decreasing with
Case 2: k2 exists and la; In this case, based Lemma C.5 have m S Cmn.
Case 3: hi exists and > l:: Using telescoping, we have:
(a) m +
|1 (V,. n n(m² + m
m
[x, voll? nmb++
m +
| Lxx. Yx) mm + mm)
V N.), nm
my
+
V (xL y2) nm
m
+
k=ka
202 my (1 + Lr,1)
Cmx +
o²
34

---

8
32 C (1 (g)
(Iut L1,1)
2L1,1 (1s + L1,1)
n11 - pw)
n96(1 - pw)2
Ty14
32 (1+ (g)
((++ I,,1) +
21,,1(11 -oattuaa)))) 1unl)++
87 (1 (2) (# L1,1)
nšo(1 PW)2
Yafk
n 30 / o²
3272Pw (1 (g)
(1 L1,1
2L1,1 + Le,1)
n(1 -pw)2
Vakk?
Yuke
8 y y (1 (.2) (11 T2
F Yk. vx)
(68)
my / + oZ
kmmin (Aa))) [m 12 max m m k+13
where (a) employs (m + mh ( the proof is complete.
mi) [m [mm]]² and (b) uses Lemma D.2
Thus.
Lemma D.5. Under Assumption 3.1 and Assumption Algorithm iis T. If at least one of b2 and ky in Lemma Then we have the upper bound of 2 as:
3.2 suppose the total iteration rounds of exists, we denote Kmin == min(k2, ks).
Et S C2: aj log(t) + bb,
1
kmins
(69)
t kmia:
where a1 bi are defined as:
1+ nCi.y n. +mo ) + 4ao log (nCi + 4ag + 26g.
a1 == 6ag, b == 4ag log
nCizaa a
(70)
in which we define constants
22n
b: V2nC5s
=
1
11
Alx + (ham))
(nLIS
L3.11 )² +1 #1)
a0
11
8
1
32 PW (1 + +G9
((u+ L1,)3
211,1 1(11)
82 (1 + 2)) (1t (1+
n11 PW)
Tolk?
Nolk
mnjule, II
16(p + Ciny)
III,.C +L,11
(422pw (1 (g)
nY./12 / + o
H
21 -Pw)?
(n + 12,1² 12
1
2L |
2
1 L + (2) (1= + L1,))
mpp
np
nzn nēo 11
64 T.2 + C1,,)
(2)
21212 + (2) + )2
npp0iy 70 pW)?
nuCCi m6 0
402 (μ+ Ogyy)
mIa200 + 112
by = Cmu + Cm +
w I V+
1
8(11 + 1 m 16(u Cluy)
(ILa2C +L1,1
18%0 / +
nipu
P.
AJ
4/2 Ch. (1 St)
(M+ 2L1,1
1 PW
26 pw) )2
nua np
164
64 C2 (1 + (2)
1.2 Cipy)
1.2 Ciny)
+
n21 PW)
n [1 pw) )2
MC
12 /
35

---

4(1 + (hm)))
(nlne +
C my
+
+1
mi
412
1
mio
A(1= + Ciny))
(mIgaCse + t.s,11
2
20 (1 + La,1)
+
+1
112
M
/2
/ 1 ou
8
32 PW pw p (1+ (2))
11,13 (u
(1
2I (1= + Tu,1)
(2(1 PW)
n96 pw)
TaHk
32 1m PW (1 + (g)
(1t 13,1)
2L (u bill)
8 8 (1 + (2) (1 + L1,1)
no (1 - -PW) )²
Tyyk²
VyR
mnjuL,,1 20 v + o
(71)
When neither k2 nor k3 exists, we have &n S for all S T.
Proof. To begin with, we first show the following result as the first two lines of Eq. 68 since m and m. are positive and increasing monotonically with t, we can easily have:
0 S min [m 1 [m 13) min [m, [m,]²]]
(lm#+ 12 + [m]+ 12 m 12 [m] 121) - (mm?? + [mj] max[mm;] [m]
([m)+ 12 + [1² - (Im?7² + [m,]] (#2+1 - =2?),
(72)
where (a) uses the definition Eg == max m Similar to Eq. 68
we have:
2 x S (mm [m + (m 12 - [m,,²) | 1V,,
| Rx,,(x,, Ne, vz)
n
n
(73)
which indicates that
2 S 2t + [xL(X,))))
V. yu, v2)l
n(ă++ + +(a)
n n((++1 1 + &t)
$ 2t + V L( yz)l
V R(x, yt, v1
n nmm + +m))
nē++
S 3 + V y1
V R(x, Vr. vt)11
(74)
mm
nē++1
Note that, to simplify the proof, we define Em 0 for any m > n and non-negative sequence {pr}. According the definitions of K2 and K3 in Lemma C.5 the proof can be split into the following four cases.
Case 1: Neither k2 nor hys exists. For any E (O, max max(Cmv, Cmu) S Cz.
easily have max m m S
Case 2: ka exists but ki does not. By using the fourth line of Eq. (68) for any E (0,7), we have:
IV V + Cm²;
E++1 S m/ + mit1 S Cin
(75)
nmy k+1
where we take Σ k==
[(x) for any t 1z.
mi
Case 3: by exists but ho does not. From the second line of Eq. (74, for any E (0, T), we have:
x1)11
V R(x, vi)l
2 S 2
+
n(m²+ + m
nž
II R(xx Vk, vi)ll
kkg
a(m + my)
nēx+1
k=ks
k=ka
36

---

1y,,(x v2)l
V R(Xk: Vk, v&)ll
I mig
mia
+
rl 7 + m,m
nłk+1
k=ka
| R(xx NR. v2)
m++1 + mkks
k=
R X Vk vzlll
S Cms + Cm +
(76)
nžk+1
where we take Σi=ks
N
O for any t < k3; (a) uses the first line of Eq. (68
F+11
Case 4: Both 22 and h3 exist. From the third line of Eq. 76), for any t (0,T), we have:
V R Vk. valll
Ee+1 S 1kk
+
mike
+
nmm x+1
k=ka
k=
(0)
Ry
(
m k2
mm k-+1
k=
V VyL( v2)
V R.
Yo. Vk. vA)I
+ Cm +
nēx+1
k=ka
V [k)
V R(xk.
Yks vo)ll
= Cm + Cyr +
(77)
k=ka
where (a) uses the fourth line of Eq. 688; we take Dkg IV Nxx
0 when k2 2 K3.
m
Ei=n,
for any li- easy that the upper bound of ε in Eq. (7p is the largest among all cases. Thus, in the remaining proof, we only explore the upper bound 2, in Case 4.
((xx 0 for any 1 < k2, and Ek=ks my-1
V. y(x.
Bet1
To further explore the bound of Σ,, we need to use some auxiliary results and bounds. So we split them into three parts as follows:
Part I: An Auxiliary Bound of Σ [=/_,!"
To further explore Case 4, we begin with
common term E ko=ko ko
for any ho < t. By the strong convexity of / in Assumption 3.1
we have:
Vy V VyI
1
S
n
k=
k=
2 y V L( ValVE V F(Xe.
2 V (xx:
2 R( V&)
F
2 V y
k=
k=
S 2mm + 2t07,
(78)
which indicates that for any 2 0. llvell can be bounded as:
[2|mm4+2] 2ntC2 f
2n[ 12 2n1C7
2n (bt41 + VIC,,)
Vivll
(79)
1
Then we have:
| < 2nn 20+1 +
22nCr, Vt =: 0ē.+1 + bbi,
(80)
37

---

where à and b refer to Eq. 71
According to Lemma C.1
since mg 2 1, for any integer > 0, we
have:
VF V YR, 12
FXx,, Yk, vAll
[+1 1
k=0
yx. [mm] +1
< log
< log
Σ
InCt, 0žkt1 nOtt, bv + nos,)) )² [mm]
-1
k=0
2
< log
Σ nCi, 0ōk+1 + +nC,, bV + +nC,, + mo
+1
-ooog
Σ 20 nCI bV + nOsz + +m +1
4==
< 2 log
(L+1) (nCi,,
0ž++1 + nCi, bV[ + nC,, + m +
< 2 2log(t + 1) + 2og (nCI,,, db4t1 + nC + nC', + mū) vt) +
< 3 log(( + 1) + 2 log (nCi, üātT1 + nC b + nO,, + m + 1,
(81)
here we obtain the upper bound of Σk= completed.
vi. for any ko S in Eq.
81).
Part
Part II: A More General Bound of Σ
In Lemma D.2 we show the bound of Et
when ko exists. In Part II, we further for any potential À s T. Firstly, if 2 k2, it is easy
V [
kk=
2+1
provide a rough bound of Ek have:
V m/
Ill
k=
V VyI((x,
L yI)1
(82)
m
m
A K
Secondly, if < 12, we have:
V 1 12ll
k2 VyL(Xx
| Lxx,
m+++1
mc+1
m
k=kz
k2
11 I vx)ll2
V yn)l
k
my
m
k=
no (1 11 12 2m
V L(x+
m
m
k=
nC
[mm11) V12)
V IXx. V+)l2
mg
m k+11
Ara
nC2 m2
| [xxx
nmm
V/
(83)
m
m
k
38

---

Combining these two situations, since Crv 2 my for any S t, we have:
IV yx),
m
nC m2
| y (x),
nmg +
mg
m++1
k=
nC my
2nCr me (n + L1,1)
mmg 9
+
mg
1 /1- + d²
8A8
32 O (1 (1+ (4)
(1 L1,13 (
2L1,1 + L1,1)
+
PW
(bo(1 - pW))
32 PW (1 + (2)
(1 + Ts,1)
21, + Taa))
8y2 2 (1 + (g) (1 LG,1²
+
11 pw)
7np122
Pyll
rByut,, 2o / +
32 pw (1 + (g)
(1+ L3,1)3
2Lz, I ( L1,1)
+
(1 (1-PW) pw))
Yyp22
Yyl
12 2 (1 + (gg) (1 12
[VF((x: Yk: vx)ll
(84)
RepLi,1 / 1+ oū
[ 12 max { {m m
k=minn 1
where the second inequality uses Lemma D.2 Thus, Part II is completed.
Part III: The Bound of &n in Case 4.
Here, explore the upper bound of ž, in Case 4. Recalling Eq. (77). we have:
R( yk. vi)1
2++1 S Cmu + Crn +
Omn + Cm Oz:
nmn k+
nž
kog
(85)
fort $ kmin min(kig, ka). For kmin we have:
IV [xx
I R(x,, vx)l
2++1 S Cun + Cm +
mm
nž
k=k2
k=ks
(0) Cmv + Cm +
40 (p + +(yyy)
nL1 + L.s.1)
1 11+
8(u+ + Cz
C2 m"
16( + Ciyy)
(nL12200, 1.g.11 +11p11
+
11 12 +
mYof/?
11
A +
4 Cr (1 (2)
(μ (u+ L1,1) 2
PW
- (1-1-mm))
mup
Taje
1625
+ 6472 C (1 + (g)
1224 + Clyy)
13 + Olyy)) 12 110
+
n(1 [WW)
n - -Pw)²
HC To
16(u + Otay))
m + +.og,1
w//u2 V1+02
P
4:2 + (2)
(n+ (.,T) /1 + o2
2T 1 1 oZ
(1 pw))
nu²
74
L2 + (2) + L2,1)
V F F(x
Nk. V12)
Σ
n
m x++1
k=min(Ar (Ar 1, -13
39

---

647 D2(μ++ + (1+ (g)
21 + (g) Clus)
+
nICC 7o(1 pw)2
npC c / + 02
NR.
[
k=min
11 111
1
4(1 + Oluu)s)
( + L1111
C mi
+
8
+
+1
mi
n2
1
m
Aipt + Clan))
(nLia + +1p111
2
V VyL(X
8+
+1
122
H
m
k=
Cnu + Om= + 4Cmo + Ctyy)
(nLn,CFu + L1s11
10 1
11
8(u+ Cl Cm 16( Cimy)
[nI1,20s + +
2
+
11 122T0
+
17o1112
D
Pw O (1 (g)
(1 (1,+111)) L1,12
2h111
PW
(1
mpp
16
64 pw O (1 (g)
12 + Cluu)
17 + Clyu)
+
n(1
PW)
ngbl - pw))
(I-ww)
uCixna Vv
12 v 1+0?
4(p + )2
+
8
(b..))
+1
112
1CI,
1
32 + (2)
(n+ I1,13
21u,a + bu.1))
8 (1 + (2) (u+ + L1,13
m(1 )2)
Yyft
Yyl
mizuLe,1 v 1+
16(u C1,,))
nIa,20o +L,.11
2
n7ol1 V1 11+0 d3 44 (1 +22)
1
(e+ L1,1) /1 o2
2L11 2L1111+ of
E7(1 pw)²
1442
n4
11 + ())
+ Tu,1) (Taa))a)))))))))))))))
F Yk: vN]ll
Σ
mm 12
km -1,22
64 247 T221 + (1, + (2)
2-2T2(1 + 22) + City)
+
muc 70 }2
IuO m / o²
V&.
[m
R=min (11 1.
1
4(1 + +1nn)
[nlnaO + Lis11
C2
+
8
+1
my
MCN
my
1
4(H + O2py)
Inta:C + L.5.11
20 (u + L1,1)
+
8
+
+1
112
P.Cr
22 + 0
SAJ
3272 pw Che (1 (7) (
(M+ + LI,1)
211,1 (1+ Lt.1)
+
+
n(1 -PW)
nogh (1 p2)
7gH2
3273pw (1 + <2))
(n L1,1)3
+ 2L (u + baal)
8y 2 (1 62) (p L11)²
n1 - Pw)}
7//2²
Nyfk
nzzuLa, / oz
40

---

[V Mk, vx.)l
ag
+ bo:
kmmin(k 1,b0 1,
FF(( Yki v&2ll
40
+ a0 60
|
mimin (Ass k2)
nOI,, b+ nC + mo
ao
3 logg(t + 1) + + 2log
21+1 +
+ 2og (nCi. a) +1)
nOi,, a
+ ag + bo:
(86)
where (a) uses Lemma D.3 and the first line in Eq. (84) by replacing & with h3 - 1; (b) results
from Lemma D.2 (c) refers to Eq. (71) (d) uses Eq. (81). Since min (k2, ks) I we have
2411 2 min Cov,, C.v 2 max (640) which indicates that
(i) if Sag I 1, we have:
4ao log(Z++1) S log(Er+1) Et-1
I
S 22+11
(87)
2
(ii) if Sag 1. we have:
2++1 - 4ap log(Z++1) = 8++1 - Sap log( 2(+1) ) 2 8ap (v - log( /2442) 2 0.
(88)
Combining (i) and (ii), we have 4ao log( S 2+1- Then we obtain:
Et+1 ao 3 3lo(( + + 2 log 2++1 + nOI,, + nO + mg nCI,, a
+ 2og (nCizy +1)
au bu
nC b+ tmg nCi,aā à
S ao
3log(t 1) (2-1))+2ogg 1
+22 log (nCr,, ()) +1
+ 0g + bo
1
1 nOi, +nn + + mü nClan
2 2++1 + 3log((+ 22ogg
+ 2 2 (nCto, ai) +
+ 0g + bo
(89)
which indicates that
2141 < 6ag log(t ( + 1) + 40p log (1+ nCI,, b b+ nOs, + +mg
+ 4a log (nCi,aa) a) + 4ap + 2bo
nC/z0
(a) a1 log(t + 1) + b1,
(90)
where (a) refers to Eq. 770 Therefore, complete the proof of this lemma.
D.6 The Upper Bounds of Σ P m
Σ
L(x,))) and Σ |. R
m
Ze+1
Lemma D.6. Under Assumption 3.1 and Assumption upper bounds in terms of logarithmic functions as:
3.2
for any integer ko E 10, t), we have the
m 12 F Vk. v1
5 log(t + 1) + c2
k=kp
I LyI, II
S as log(t + 1) b2
m
km Kvp
R(x Vk. 22
a3 log(t 1) by.
(91)
2k41
k
41

---

where, referring to Eq. 770p and Eq. 71.. c2 az by, 0g, and by are defined as:
C2 == log (nC ãa, + nC,, āb + nC b + nO + mū) + 1,
42 == 160 (1 22))
L1, + 211,1 1.11) + 407213 (1 (g) (p + 11,1
(1-Pw)²
Tyl
Yoll
T 11 v o
nC2 m.
+ 2nC mi (p + L1,1)
b2
mm
m
p2ar v 11 oi
8
32 O (1 (2) 16 pw)2
(L+
(1 L11)3
21 + L.11) Yyll
+
PW
32 (1 (1+
L1,)
2L 21
)+
87 (1 (1+ (M Lr,1)² )27
1
+02
7n113
M2 1 1+
20
03 = 80( + Olan)
|n1,20 +L (
2
T0p2 /1 o2
1
P7 (1 Gg)
(1,+1,1) L1,1)² 2212)/2/// 11+00
2I, +
(1 - -pw)2
1412
n4
1 + (2) + L1,1) ) 320 P2 1i( (1, (9)
111
7o pw)
(1 + (2)(4 + Olnp)3
802
40z(u + Olnu))
Intua + (
+
+
MCC, C C.n Rvv +
112
C
n²2 m²
nm 4nC m² (μ + Cinp)
nLI,20s, + Lss11
8nC mn" (u + C Clas)
by
m
n - o/
1
1BT0N + oz
1648
64 Che (1 (g)
17(H++ Olyn)
17 + Clyy)
+
1 PW
(6 - (1-PW)²
HC To
12%0 o2
16(n OiHr))
[nL1,05s +L1
DJ
+ 4 4w
Ch. (1 (g)
7oH2
1 - PW
66 pw)
(1 + L1,1)
2L11)
16c2(H + Clnp)
|nL12Csu +L111
2
7012
/1 of
11
112pw(1+ (2)
(u+ 11, 11 1
2Lr,11 1 o
1. + 6) L1,1)
:6(1 -Pw)2
mp2
1/
2ē0
64cr P2 L23 (n + (1+ (1+
201 + (2) + )2
|C1,7700 - p2)
MCip 7m /1 +0
8b2
4ba(u + Clan)
(nlua Tof.1
2
(92)
112
1.3 12
1
Proof. Based on the results in Lemma D.5, we have the following bounds.
Part I: Bounding Σ N.)
Firstly, we bound Et Ko
FVF FFFixyye.eell M for arbitrary ko < t. Back to Eq. 81) by plugging in
m
Eq. 900 have:
VF (X Vk. 22
m 12
< 3 log(t + 1) + 2 log (nCi., ab4+1 + nCi,, b + nC,, + m,) + 1
42

---

(t + 1) + log (nCi,, da, log(t + nCI,, abi + nCi,, + + + +m)) +1
x log(( +1 + 2 log (nC,,, da (t + 1) + ,, abi + nCi,, b + nC,, + mğ) +1
< log(( + 2 log ((nCt., dan + nCi,, abi + nCi,, b + nC,, mū) (1 + 1)) +
s 5 logg(t + +) 2 log (nCI,, dai + nC ab, + nOI, b nO,, + mb) +1
log(( + 1) + C2.
(93)
where (a) results from Eq. (90 (b) refers to Eq. 99
Part II: Bounding E [V,L(xx))))
m841
Secondly, we bound Σx= (X m
We split this part into two cases using Lemma C.5
Case 1: If m2++1 I Cme, we have:
I1 [Vx((x))
1+1
k=
vkll
n(mp+11
13)
n n(C2,
(m
nC
my
nmy
S/2.
m
ml
m
m
(94)
Case 2: If m > Omu, we have b2 S t, where k2 refers to Lemma
C.5
Then based on Eq. (84).
we have:
V VxII
m
k=
nC2 m8
nmy + 2nC (μ Li,1)
mg
12 V + 06
8
32 Oi. (1 + (2)
(u+ L11)3
2L1 L1,1) Nafk
1 PW
26(1 - ]2
7ul1?
32 (1 (2)
( L3,13
2L111H + L1.1)
8 (1 + (2) (n1 L
20(1 )2
Tyll
Lu Eg / + +o
32 (1 (2)
(1+ L3,13
2L + L1a))
8 (1 + (g) (1+ 2
+
+
(1 pw)
TyH22
Yult
35 uL. | 1 o
F Yk, v1))l2
[m 12 max { (mg + m. 1
kmmin(kn,ke k2)
(4)
nC? my
nm + 2n (μ L1,1)
mi
122 /1 o?
84
32 C2, (1 2?)
(1x (u+Tag)) 14
2T. (u Tu,1)
+
1 PW
(1 - {2
Typp?
3272Pw (1 + (2)
(nu+ 33,13
2La,( + L12))
87 (1 + (2) (1+ L1,1)
20(1 p2)
Pofk
uL / 1 0z
160%3pw (1 + (2)
(n+ L3,)3
21 (1s + L1,1)
(1 pww)
Typ2
Yyfl
40,213 (1 + (22 (y + 2
log(t + 1)
26 / oz
43

---

32 (1 + (g)
(4 L1,)
Lx1)3
+ 2 + L..))
8r (1+ (2) (H + Lr,1)²
02
[-pp)= pw)
7tyl12
Yyll
rhuln, / + o
(6)
d2 log(t + 1) + b2,
(95)
where (a) uses Eq. (93). and (b) refers Eq. (95). Since the upper bound Case is larger, take Eq. (92) as our final result.
Part III Bounding
Σ
Re-1
Last, we bound Ek=ho Ni
We split this part into two cases using Lemma C.5
Case 1: If m2+1 I Cmn, we have:
R..l(x Yo, v
Ek+1
k=
V (Kx, Vk. V
n [
(mg]])
nC²
nmm b3.
(96)
20
Case 2: If 1m
Cm,, we have h3 t, where by refers to Lemma C.5
VV V, Yk. vx)ll
Ek+1
R(x Vk. v
V R(KK Vk. vz)l2
Zk+1
E
k= Kg
k=ka
n²2 122"
4nC2 my (1 + Clyv)
n + +Toga
8nC2 (u + Cl,o)
mi
11 1+02
11
/ 1+
1641
+ 64-2 Or (1 (g)
13(K + 13(M+ +Ormn)
DZ(H + Clyn)
PW
(1 ([1-ww) )2
1Cirp TM
16(μ + Cruy)
(nLu2Cta +T,ga1
DJ
4
Co. (1 + (2)
7o112
H
PW
PW pW) )2
(4 + L
2L111
16(n + Ci,y)
nTn,20 +bia
2
1112
Tij1
2opr2 /1 + 1
4Y2pw(1 +22)
L1,) 22,1) V 1+ o
x1( p2))
mp2
12p1
2 11 + (H L1,1)
|V Yk, 12
Σ
|m
k=min(ki 1,k--1
644gpw T.2(1= + Ci (1 + (2)
2 2T2 + 22) [11=+10 + Ci,z )2)
+
p2
pCr, Cm= / 1+ o?
FXX, 12
[m
k=min 11,3-11
8
4(H + (2
nIIeO + L )2
Σ
V [
112
C
1
m
k=ka-1
n²2 m
4n02, ( Olyy)
8nC2, (p + Clay)
-mi
+ 1sp.1
+
mB
1
12 / / o²
44

---

1648
64 O
(1 by)
T + Cluu)
[ + Cluu)
pw
-pw)2
p 70
12
16( + Clny)
[nL12Cse +l4g,1
A
4r O (1+ (i)
70112
11
pw
86(1
pW))
(11 + 12,11²
211,1)
)+
16(p + Cnmn)
1 +L1g.1
1422
14
Yom? /1 02
1
4n (1 + +C4)
(1 L,1)2
2L1,1 1ai1i++05
2 12 + 62) + L1,1)
20(1 -PW)2
ny²
np
noo 71
64 [2 + (1
+ (2)
21 + 6) + Cipy )2
(5 log(( + +)2)2)
pC 7o(1 p())3
1. Cmo 1 V o2
8
4(H + Olyu)2
(nli + +.(s.)
2
(a2 log(l + 1) + b2)
112
11 Crgr
1
(d)
03 log(t + 1) + b3:
(97)
where (a) allows Σ Ri V V... k=
when ko 2 ki; (b) uses C. 2 mi and Lemma D.3 (c) follows from Eq. (93) and Eq. (95); (d) refers to Eq. (22.. Since the upper bound of Case 15
Æ6-1
larger, take Eq. (97 our final result.
Thus, the proof is complete.
D.7 The Upper Bound of Consensus Errors
Lemma D.7. Suppose Assumption 2.1 Assumption 3.1 and 3.2 Then, the consensus error A satisfies:
2Au
8w2 (1 +1++ (5lo(t) + c2)
A
+
pw
pw)
k=
87g (1 + (2) log(1) + b2) 8r. (1 + (2g log(1) + by)
(98)
(1 - Pw) )2
(1- pw)?
where Ag is the initial consensus error, which can be 0 with proper initialization.
Proof. According to Lemma
C.4 we have:
2
8Y2 (1
C2)
1-1
|x41 18.41
12
12
|x0 12
(x,, YR.
v1)
I Pw
(1 - p2]
K=
k=U
(99)
With the help of Lemma D.6 we have:
FF Vk, v&)ll
VF. VL. 22
< 5og(t) +
(100)
pm
Similarly, we can get the following inequality for the dual variable:
2 Ilyo 17o 12
&n (1 + 52) log(t) + bz)
1y++1 11 I 1-PW
(101)
(1 - pw) )2
For the auxiliary variable, we have:
U++1 Pv (W -o V Ro. Wv, V.G.G
(102)
45

---

where
V.G -- To
1 (Pv 7o ve.))) Wv.).
(103)
Using Young's s inequality with parameter X, we have:
|v++1 10 1|2
- V -JGV. - -% v,,
- V.V.
< (1 v. -.v, + (1+
Voll(xe, |y (W Vot v.))) - Wv,
1 PW 1Ive JJvll?
+ Pw
|P (W (ve - - Vo ve))) Wvoll (104)
pw
Noticing that Wv: = vv( holds for the convex set V, we get:
Vi+1 10/+1/1
1 1 PW
l|ve - Jvell + 1- pw
1+ Pw
|Pv (W (v. - -02 V Vull(xe. v())) - Pv(Wv,,)
|
2
(a)
1 + PW
2 V - Jvell + + PW
PW I Z V R(x Vr.
(105)
PW
where (a) uses the non-expansiveness of the projection operator, as shown in Lemma 1 of Nedic
ct al. 2010 Then, we have:
2
1voll2 + 8 (1 +
t-1
VE 16 S 1- Pw
Vo-
Σ
2-2 2
R. va)ll
(1 pw)
k=0
(106)
Similar to the primal and the dual variable, we can bound the last term above, which completes the proof.
D.8 The Upper Bounds of Σ
Σ
Vyl((....) and Σ V..
m441
Through Lemma
Lemma
D.6 and Lemma D.7 we can derive the upper bound for (v. in the following lemma.
E Jemmaa
| (h..
Σt
V. and >i kn kg
komko
mit1
Lemma D.S. Under Assumption 2.1
Assumption 3.1 and Assumption we have the upper bounds in terms of logarithmic functions as:
3.2 for any integer ko E [0,t).
[VS(x, Tc. 02)l
1 I log(t + 1) + ba.
[m
V V DR)l1
I as log(t + 1) + bs.
mx+11
k= Km
| R(Tx, D2, ux)l
I as log(t: 1) + bb:
(107)
Ek41
R
where
8pw (3 (2) + agn + (3) + 23 (?)
01
2n²
[m )2)
213Ao
8pw L ( b27) ( b3 +()))
64
2n
pw) mm
m 21 pw) )2
8pw 17,11 (5 + ( + 2 (2)
a2
05 =
2nd
my )2)
46

---

b2
1 + Ilyo 1)) 8pw L1,1 (02) (.) + b2y (.)
65 ==
2n²
mg Pw)
mi Pw)
8pw T. (5 + (3) + 027)(( 1 + (w) + +0376(1 + (2)
03
06
2n²
m - pw) )²
b3
20
Spw L + (2) by 2(1 (1 (.)) b37 (2))
b6 = 2n²
+
(108)
m1 Pw)
m pw)2
Proof. According Lemma
we have:
IVF v.)l 2 17, 10 + + (1x
1T 2 llve 18.11 + 1|v 15 15
(109)
|V, y: || _ | 17)) 2 (1|x, 15, 2 + lly, -1 11]),
(110)
(V,,,(,,, vo) 2 V (2 1.,, 17r 1m))
1,, 1 + lly: 1ū + || - 1
(111)
Based on Eq. (6) we have [1., 17 10:)1 VF 1ū. 18) 1
|n tr Dr.
82)1
L 17:
, 1
(T 02)l and [1,, 1 Ut. 16)
(((E,, 17, 16 n rr (Tx, Uh, 6.) then according to Lemma D.6 and Lemma
D.7
we have:
VV The 1x)
5 log(t + +
+
S a4 log(l + +1 + ba,
+ k=
2n
[m
| yillk Dx)]l
a2 log(t t + 1) + b2
12
as log(t + 1) + bs.
m
2n²
m
V r Tee 02)
43 log(t + 1) + by
D
S as log(t + 1) + bb.
(112)
Es+1
2n
m
k=ko
where as, by, as, bs, no be can refer to Eq. (108) and
dj 2(11x0 1 2 yyu 15ol I| + vo
16ol?)
Bw (1 + (5 + 1) + 02)
PW
(1 pw)
+ 87gpw + (2) log(t (t 1) b2)
+ 8r (1 + (a) log(t + 1) + bz)
(1 pw) )2
(1 p2)
d2 = 2([1x0 17o 2 + Ilyu- 15ol
1 PW
8w (1 + (5 log(t + 1) + 02)
87) + (a) log(t + 1) + b2)
(113)
pw )2
Thus, the proof is completed.
D.9 The Upper Bound of Stepsize Inconsistencies
Lemma D.9. Suppose Assumption 2.1. we have:
Assumption 3.1
and Assumption
3.2 hold. For the proposed
Algorithm 4
F(( Vk. v&c
+ (5 log(l)
(5log(() + 02) (2)1 + pw)))w) pww)
(Cin + Cr ) 09, +
(Chn + Cs,, )27 )
nzz 1 - p2)
/
(1 (1+55) (22 log(t) + +2) +w pw) nūo(1 p2)
E+
VyL(Xe,N1)
5
nū
47

---

k+1
V. Vk. v&)
Ri
+ (as log(t) + ba) (2 + pw)
(lro Ss + +ct,) )1
O22 +
(114)
nžo(1 - pw)
Proof. By the definition of Pi,k in Eq.
25
we have:
9
(F(x.
n0b+1
1
2 Fxx, Yr, vill
(q--1 - -1,411
n
h,,+1
i=1
n
1 22
| F X1, Mt, v2l
19++1 g1.11
n²
1 C
Fx,, Vt,
1 n.tt2l1
(115)
n
m 12
According to Eq.
91,
we have:
(p+1
VF(x.. Vk. V&.)
n19k+1
km 0
1 + ?
F( Vk, v
9 17
n²
1 12
k=0
(2) (5 + 1) +2)
q
17x+1
(116)
2
where (a) uses Lemma D.6 Next, for the term of inconsistency of the stepsize ||qu - 1q we consider two cases due to the max operator used (i.e., m 2 m and m mž). First of all,
we derive the bound for [m 1mg 11 | 1m x 1| and |m 1m; 1| For
m 1m we have:
| 1m 2|
II(W
(J 11 II(W J)g 1|2
+ PW
(1 + pw )pw
[m - 1m
+
gg 1
2
1 PW
(a)
1 + Pw
||m
1m611² + r((1 + pww
(Cr. Ci
Cf.
2 k
Σ
1 + pw
(1 >?
2
t=0
2n(1 + PW) )Pw
Ci.y + -c,,) c...²
(117)
(1 )2
where (a) uses Lemma
C.2
For I|m
-1m 1 112 we have:
m m 1m 11
< [I - -m) 11 + [I[ - 2
+ Pw
(1+ + pw pw)pw
<
|m - -1m + 1 1--p0 Pw
|g
2
(a)
PW
||ml"
1m
nc? (1 + Pw JPw
k
Pw
k-t
2
(1 )2
1=0
48

---

2nC7, (1 + PPW)p
(118)
(--ww>
where = co do log + 02)). The inequality in (a) follows from Lemma D.4 and
Lemma D.6 Specifically, since ||bي| <
m [| - <|mmm]|| I (C + co + (5 2 + 02
follows that the magnitude of the gradient ||al|| is upper bounded by Ct For |m - 1m have:
m 1m 1|
1(W - [m 1m)] + 1(W - J)g 1
1 PW
(1 + Pw )Pw
|m - 1m
||
2
1 PW
(n)
+ PW
|mm - 11mil? + n(1 + Pw Pww
Civy Cta + Csa
Σ
+ Pw
k-t
(1 p2
2
200
2n(1 Pw Pw
(Cr, Cse + C7,)
?
(119)
(1- >w
where (a) uses Lemma
At iteration k for the case m 2 m with ||mmm 1mgm 0, we have:
1 17 2| = m m k+1 1m m 1|
II( - J) 1m mm + II(W - Jg
+ PW
(1 pw pw)
|mfmm 1m
|g
PW
+ pw)
|mmmm mmfmgl?
nC?, + +pw)pw
CL., + +Ct,
Σ 1=
1 pw
k-t
(1 p2-
11
2nC8 (1 pw)
CCa, Cs Ciz
(120)
p2)
1
For the case m < m with |m 1m/mil2 O, we have:
| 11
2n(1 + pw pw))ww
(Cee + +01z) (1 [PPww)
(
(Chy
Cip Ci + C₁
2
= -1Imī+1mk+1
1m m <
1
(121)
By summing Eq. 120
and Eq. 121 we obtain the following inequality:
2n(1 + pwwpw (Cte + +c/s)
*(t O7, + (Ciza Ct. + Ctyy )
|q-+1 17 2
(1 pw)2
(122)
Combining
Eq.
122 and Eq.
116
we
can
get
the upper
bound
for
Σ (a T ' L yk /
in Eq.
1 114
Similarly, we have:
2nC2, 1y (1 pw pp
| 1ux+1l"
(123)
pw )2
49

---

and
2n(1 pw Jpw
Cgg Cr + Ctu )
27
1s+1 12t+1l1 =
Ct +
(124)
(1 - pw! )2
Then
combine
the results in Lemma D.6
can get the upper bound for 114. Thus, the Lemma D.9 has been
we
Ei
(2x+1) R, Vis va)/nak
in Eq.
proved.
D.10 The Upper Bound of m
Lemma D.10. Under Assumption and Assumption 3.2 suppose the number of total iteration
rounds in Algorithm iis T. If there exists k < 'T' as described Lemma C.S then we have:
Cm=
k1
m S
Cn= (1((
(0((i))-0)) 7o
+ a7 log(t 1) + by) set1, t t k1
(125)
where an and by are defined as:
= as
2[²us
2
L1,C + +.s.11 )7
+
1
1 m p.
112
1
80(1 + <2) + pw)pw)
(Crz + +C,,
(((+(ann + Cc,,) }
+
O% +
nz000011 -pp)- )w)
H
(2)+11) 117) 440 (1 (1+ (g)
2
40 407 (1 (g)
+
+
PW
(1 pw )2
802 2
PW + (2)
8as (1 (2)
+ (1 )-PW)
Pw)2
4L
2L2br
2
L122 + L1s.1 )
2
b7
1
1 mm
122mng
112
1
16cz(1 + ((1 + pw)pw)
(Crz
27 C2 (am Css
+ +Csa
nz pw) )2
1
1
(1 (2) + 133) 440 (47, Lo
20o
862 (1++ (1+
pw
8b2 (1 + (
8bargpw (1 +
SnyyC L$ (1 (2)
(126)
)2
(1 )2
T
and the upper bound of 2 == max(m)) mm} refers to Lemma D.5 have m. < Cm= for any T.
When such 2ą does not exist, we
Proof. According to Lemma
the proof can be split into the following three cases:
Case 1: If m I Cmpa, for any t < T, we have the upper bound of m m S Cm...
Case 2: m > Om=, there exists
T described in Lemma C.5 Then have the upper bound
of mft11 as m6+1 < Cm= for any < kl.
Case 3: In the remaining proof, we only consider and explore the case h s < T when m. Cm=.
From Lemma D.I for 2 k1, have:
((T++1)
Tw (2 L3 Logeth (1 + C.) + +L3) A
Noe 9+41
+(x,)
21(2,)112
71
50

---

- -(2 Lo (1+ (2)) (3)
[Vz Dr, 62)
1
|ur yes 8e]
+ 112
at+1
g++1
VaL? 2/12 + "ool (L b1)))
(9.t1)
(
+ +272
VF Ne vo)
1² 1
a++1
nh++1
(127)
S Lo (1-5.)
In addition, if k2 in Lemma C.5 exists, then for t k1, have mi-1 > Cm=
and
20
(5++1)
Yo (2 L (3 (1 (9) + +L3) A.
Yole+1
S ((x))
[ +
7z
V (Tts Der 12)
L'
a6+1
112
1++1
1eL2
(L
V (ā, 121
(qr+1) n6.+1
+
+ 4
FF vo)
2p
aa 1
gr+1
(128)
which indicates that
4641
v (Tr, Te, 1))
Φ (xx) - $ (8s+1)
(2 (1+ (2) + +13)
4I
r Dt. 81)l
< 4
A
+
4²
+ 80/+1
(qrt1)
F Vo)
+
(2212 +
222 122
4L2
L1,20s
Vy,,,,
3:1l
ndh-11
1
9++1
(129)
By taking summation, we have:
9h- V [Tk Dk. 0k)l
k1
+ (kx,) )
4% (2 L3 +
Lo
(1+ (2) + L7}
< 4
AB
Yw
k Rq
4L²
Vur(TR Kk. 12
8
(
+
V F (X., Nk. V&s)
max m
40
no
k=k
2Ī2
AT.
L1,0 + +L
V y Uk )1
+
+
(130)
p2mg
max m 1+1 m
k=
For ((Tx,,, by telescoping Eq.
127 we get:
((7x)) S (00))= + To (2 L L (1 22)
+ L7) h
AB
n
k=0
122 y +
(TT Te. 0% 112
h1
(qx+1) ng
Fx..
m
max m
qo
k=0
Vaf De, 02
+ 21 200 (1 + 22)
m max (1 12 [m [2]
K=U
+ noll
(LiaOty + L1a
2
h--1
V T2)11
+
Σ
(131)
2u²
4t H
m max k+1 m.
k=o
51

---

By plugging Eq. 131 into Eq. (300, we have:
9++1 V Ds, o2)
(((o)) - 45
440 (2 (2 Lo (1
+ L3)
$ 4
AB
n
k=
4
[T De. U6)
12
(
+
FX(x Yks va
m
max[mp ++11 +
mx+11
40
19x+1
1=
k=
2T2
4L²
V (T 112
8n C2
Lo (1 C2)
+
T.
m 9
11 mm
m
max m ++ m+11
h=
(TTo)
40u
(2
L3
(1 +
2/) D3}
$
4
Y/2
n
4L2
V Tke [x)
12
8
(
VF yku V&a)
VF
1m
max(m) 11 mp+1
40
14k+1
2L
4I²
L,
2
IV 0k)l
8nYa
C m= Lo
(1 (2)
+
-b,.1
Σ
mmmg
m
11
A==
(To)
ALZ(ag log(l + 1) + b6)
4
1.2mmg
(as log(t + 1) + bs) (1+
2 L1,2 + 1.511) )
2)
+
mm
112
8(1 + (5) (ogg()) + 02 (2 + pw (w)pw)
(Crzy Ora +C/s
C7 ( + +su }
2
+
nē )
H
1
4% (2 12 Lo (1+ (2) + 13))
2Dg
8yapw (1 + (5) +1) 02)
+
+
1- PW
(1 )w)
87/ (1 + (2) log(t + 1) b2)
8y2pw + (a) log(t + 1) + by)
pw)2
(1 p2)
SnY, C2 m Lap (1+ + (2)
o
① (FF
4:4
07 log(t 1) b7.
(132)
where (a) uses Lemma D.8 and Lemma D.9
This immediately implies that
V DE. 122
② ( 4-
+ a7 log(t + + + by E141.
(133)
m
7x
Similarly, can have the upper bound of m7441
Tk Tk. 02)
m S mi
m
k=k
< Om
(4
$ -
+ ar log(t +1 bz Eet1-
(134)
7/x
Then the upper bound of m is proved.
52

---

D.11 Proof of Theorem 3.9
Here we still assume the total iteration rounds of Algorithm | is T. According to Lemma D.I the proof can be split into the following two cases.
Case 1: If my Cm=", then have:
94+1
((t)) - $ -
(2 Lo9411 (1+ (2) + +1))
8L²
[V
Ver(o De, 6(ll
S 8
A. ++
n
g++1
(qr+1)
+
16 (1+ (2) V 2f
(T,, De, B,)l + 169
FF(x vo)
n9p+1
4T.2
8T.2
T1,2Cr + L,a)
VV, 1el
+
+
(135)
122
1d
1++1
By taking the average, we have:
T-1
(T:))1
d++1
1=
8
(Tn) ((TT)
8q.
(g) (2 (1
+ L2)
T-1
<
+
A.
T
nT
t=0
+
16nY,
90
(1+
T-1
Σ
V V Tr. 12)
169 1
T-1
(q
V F(xx, yr,
2
T
T
nd+41
4
8I2
(1,205
V
+
+ L,a
122
m max m,
8T.2
V (ir(Tt Tt. 12)
1T
mi+1 max (m m
(Ja)
((TT)
8q 1 (2 L 1 (1 (2)
+ +17)
T-1
Σ A.
$ T
+
Tx
16 Ln CC2 m.
(1+ (2)
16q
T-1
9.+1
+
F (Xi,
T
T
n6++1
1=1
4I2
8L?
LI,20
2)
1
T
V
Vo 7211
+
+ +1111
T
m
y
8
Ver Dc, 12)
n
1.2mm
max m m
1=0
2
((T)) Φ
4
a7 log(t + 1) by
(136)
T
7/e
where (a) uses Lemma D.8 with ky = 0.
Case 2: If m. Cm², by Lemma C.5 there exists k To such that my $ Cm., m Cmr.
Then for / < ki when my Omz, from Eq. (35 we have:
V (1x))l
((ū)) + (x(+1))
80 80 13 Lagi (1 (3) + +D3)
[ De. 0111
<8 8
A. +
n
gt++1
53

---

(q
+ -1677a (1+ (/) V V (Tt, W1: 6t)l 167
A (xi,
ndp+1
[T.2
8T22
(1,201 + +Iza) ) 11 (T well
(137)
12
1et
1
a++1
For 1 2 hi when ma Cms, from Eq. (36). we have:
4++1 [2(2))1
((āx) - ((F++1) +
19--1(2,00 12 (20 (1 (2)
+ L3)
8I2
Vurr(Tz, Dr. 12)
I 8
D +
7/2
122
gi+1
(art1)
4
8L2
[1,201
+ L5.11 )
|1 g (Tx, 7c)l
+ 169/11
(x
+
+
ndt+1
122
1d
1
ao+1
(138)
By taking the average, we can merge < h and f 2 k as:
T [=)
k 1
T-1 Σ
1++1 ( 1
T (i:))l
T 1=0
T
t=
8
1 (Fo)) - ((TAA))
Sq.-1 1 (2 Lo (1 + (g) + L7)
hi-1
Σ A.
+
T
na
nT
1=0
16n La 90 (1 + (2)
h--1
1690 T
h1-1
(9++1)
V Vffe Dt. 1e 12)
F
n4
4
81.2
L1,20 + L5.1
2) 1 h-
| (T, 02)12
Σ
+
122
T
m max m. 111 m,+1
1=
8
k
VTr(Te, Dt. 12)1
2T
mf+1 max m m m
t=0
8
((
((TT))
80. (2 Lo (1+ () + +3))
Σ t=k1
T-1
A
T
Yv
nT
T-1
16%
VF(x
T
14++1
4
L1 + L511
2
V Vyl(Er.
+
112
41
1
m max (mb+1: mi
2 T-1
| rT Tt. Te )11
2T (=
mł+1 max m y
m
8
(T(T)) - xh
8 (2 1 I. (1+ +
(2)
+ 123)
T-1
<
Σ
A
T
Yv
nT
t=
Lop
(1 + (2)
k
1690
T
q
V (3r, ( Dt, 12)
F
T
T
nd
54

---

412
8L2
Ta
2
1 3e)1
+ L.s.1)
m
8L2
T-1
V Te, De. 01)
1.T
mi
max m 1+ m
1=0
(a)
2
(T))
4
+ log(t + 1) + by
(139)
T
7z
where (a) uses Lemma D.8 by plugging in kn = 0.
Note that Case 1 and Case 2 indicate the same result. Thus, have:
+ (To) 4
+ a7 log(T) + b7
7/
(T)o) 45
2 27 + 07 log(T) + by)
(((0))
4-
+ m
+ a7 log(T) + b7
(8)
4+
+ u7 log(T)) + by
(ar log(T) + b1)²
(((0))
4- -2))
+ +0m=
+ ar log(T) + by) (ar log(T))+ + bi)
7/a
log (T)
0
(140)
T
where (a) uses Lemma D.10 and (b) uses Lemma D.5 Thus, the proof is finished.
D.12 Proof of Corollary 3.11
Recall from Theorem 3.9 that there exists constant M such that:
(+))))) < M log
(141)
T
By setting the total number of iterations T as T' ML log" (a and assuming the constant L 12
we have:
M log (T)
log ( MN log" (
T
MN log" 4 M
(Ng((N)= log
M + llg (log (M) (²))
N Nlog' M
(log(N) + log
(M) )
ESe.
N1+ log
Here have used two key inequalities:
1. log (log ())) < 4 log (a for sufficiently small c,
1
2. log(L) + 2 log (b < L log ( M) when L 12 and is sufficiently small.
55

---

Then ensure that number iterations is:
M log'
Thus, achieve e-aceurate stationary point, the required
T ML
log" (
= -lgg log" (1)
(142)
Finally, the gradient complexity is given by:
Gc(c) 9(T) 0 log" )
(143)
Thus, the proof is finished.
E
Additional Experiments
E.1 Hyperparameter Optimization Problem
Our experiments are conducted on the following hyperparameter optimization problem:
min Σ Ji(A, XERP n
n E
s.t.
w' w²(A)
arg min
4()
WER n
where the goal is to find the optimal hyperparameter x, subject the constraint that (*( represents the optimal model given A.
E.2 Synthetic Data Experiments
For the synthetic data experiments, we follow the experimental setups of prior works [Pedregosa
2016 Grazzi et al., 2020 Chen al. 2024a For any agent i, the private objective functions and 7, are defined as:
f(A,w)=
Σ
"(yo w),
4(),w)=
Σ
1 VVE w) +
Σ e ew
2 j=1
(Fe.B.)ED;
where (xx) = log(1 + =) and represents the dimensionality of the data. A ground truth vector w" is generated and each x. E R2 sampled from normal distribution. The data distribution for & at node follows (00 22 r²), where quantifies the degree of heterogeneity across agents. The corresponding labels ye are defined as ye = x w' +0.1e, where is sampled from a standard normal distribution.
E.3 Real-World Data Experiments
For the world data experiment, we apply our method to hyperparameter optimization on the MNIST dataset [LeCun et al. 1998) and MaSHion-MNIST (FMNIST) [Xiao et al.) 2017) dataset. the functions Si and I are defined as:
Following (Gazzi et al. 2020
f((A,w) = DDA
Σ
E(x w. We).
()) D
Σ
{ w. Uc)
cp
(ED,
where = 10 and p 784 denote the number of classes and features, respectively, E Rexp is the model parameter, and & denotes cross-entropy loss. D, and D represent the training and validation sets, respectively. The batch size for each computing agent is set to 1,000.
56

---

0.99
0.99
0.98
Accuracy
0.98
0.96
DBO
0.95
DBQ
MA-DSBO
MA-DSBO
0.97
SLDBO
Ada5DBO
0.94
AdaSDBO
200
250
300
0
50
100
250
300
Iterations
Iterations
(a) Synthetic with p = 50
(b) Synthetic with
200
Figure 4: Test accuracy on synthetic dataset with 5.
0.7
MA-D5B0 53993
0.98
0.6
DBO (xw0.5393)
DBO (m (860)
0.5
0.593)
SLDBO (n-00
Accuracy
0.96
Accurs
347
200
AdaSDBO (oum0.5 9v.005393)
0.4
AdaSDBO (ou-0.4860)
D80 (3-3.5393)
0.94
(+= 4860))
MA-05B0 0s-90
MA-D5B0 4860)
SLDBO (va-1.5393)
0.2
0.92
SLDBO (v. 4860)
AdsSD80 (3-3)
0.1
AdbSDBO Iv--0 49601
0
50
100
150
200
250
300
0
50
100
Acd 200
250
300
Iterations
(a) Test accuracy
(b) Upper-level loss
Figure 5: Test accuracy and upper-level loss for synthetic dataset with different pw-
E,4 Decentralized Meta-Learning Experiments
In our decentralized meta-learning experiment, following the MAML framework [Finn al. 2017] we consider a setting involving M distinct tasks, denoted by {T,)),z Each task T, is associated with a loss function L(x. y,). where x denotes a shared embedding parameter across tasks, and By represents task-specific parameter. The objective meta-learning is identify universal parameter x= that facilitates fast adaptation to new tasks by enabling efficient fine-tuning of y using limited number of data points and update steps.
This problem naturally fits within a bilevel optimization framework. At the lower level, given a fixed æ, each task seeks the corresponding optimal adaptation parameter y by minimizing the loss its training data D The upper-level optimization then aims to select shared parameter such that the adapted models V perform well on the corresponding validation data D Let y" col ....y.................... vir
denote the collection of all task-specific solutions.
Unlike traditional centralized meta-learning, where all data is accessible at single location, we consider decentralized setup in which training and validation data for each task T, partitioned across agents. Specifically, each agent E [n] maintains its own local training dataset D i.g and validation dataset Dral for task T.. Given shared parameter the local base-learners collaboratively solve for Ve (Ir) using decentralized lower-level optimization. The upper-level meta-update of is then performed through cooperation among agents based on their local validation losses.
The decentralized bilevel optimization problem is formally expressed as:
1 M
min F(x) = 1
fig (x)),
M
57

---

2.5
DSBO (ox-0.5333
0.8
Soper-Level Level Level Loss
2.0
SLD80 9v-0-4860)
MA-D5B0 pP 4860
SLDBB (o.-0.5333)
Ada5D60
Accuracy
0.6
1.5
4880)
Upper
0.4
MA-D5B0 ( 5393)
054 80 (Pv-0 4860)
SIDBO (v-00.393)
SLD80 0a-0.4880)
0.2
AdsSDB0 (sx-05333)
0.5
Ads5DB0 (ox-04
100
200
300
400
500
0
100
200
300
400
500
Inerations
Iterations
(a) Test accuracy
(b) Upper-level loss
Figure 6: Test accuracy and upper-level loss for MNIST dataset with different pw.
0.8
0.7
2.1
SLDBO (
MA-DSBO (n-- 4880)
0.70
SLDBO (860)
4860)
81.8
Ddo 63x30.5393)
DBO 6xx4 4860)
0.55
01.5
20.4
MA-DSBO (h 5393)
MA-DSBO (ram0
0.00
SLDBO (v.005393)
SLDBO 6wm0.4860)
0.9
AdaSDBO (v 5383)
0.2
AdaSDBO 0v
0.6
200
600
800
1000
200
400
600
800
1000
Rerations
Rerations
(a) Test accuracy
(b) Upper-level loss
Figure 7: Test accuracy and upper-level loss for FMNIST dataset with different pw.
M (.
s.t. v((x)) arg min
M
where (1.g(1, D E(nnteDD L(x, 2 (x)) and 4. (z,
EieDwEDD Lix, Mq)
(1,)) with (y) denoting a strongly-conver regularizer with respect to y. The experiment was conducted over 32 batches of tasks across 1,000 iterations. Each task included a training dataset and a validation dataset, both configured for 5-way classification with 50 shots per class. Specifically, the training and validation data were distributed among different agents enable cooperative learning. For each task, 30% the data from i-th class was assigned to agent while the remaining 70% was evenly distributed among the other agents.
E.5 Configurations
All experiments were performed with using PyTorch [Paszke et al.) 2019). The network topology was configured as ring topology, where the weight matrix W (wiz) is defined as:
Wa w, W3i++1 W0.
where E (0, 1). W1.0 = wi,n, and Wn.n+1 = Wn.1- In this setup, each agent is only connected to its immediate neighbors and + for 1, n, with the indices and n + representing and 1, respectively.
58

---

0.8
0.75
0.6
Accuracy
0.60
Accuracy
MD80 SLDBO
MD80
MA-DSBO
0.30
MA-D580
0.2
SLOBO
Ada5D80
Ada5DBO
0.30
SLDBO
AdoSDB0
0.15
100
200
300
400
500
100
300
400
500
100
300
400
500
Borations
Narations
(a) MNIST with
(b) MNIST with
(c) MNIST with n 12
Figure 8: Scalability analysis the MNIST dataset under varying network sizes (n 5, 8, 12).
0.75
0.60
Accussy
0.45
Accuracy
60:45
0.30
MA-DSBO
MDBO
0.30
MA-DSBC
0.15
SLD8O
AddSDBO
0.15
SLDB0
Ada5DBO
SLDBO
AdaS
0
100
200
300
400
500
0
100
200
300
400
500
100
200
Ileratoons
300
400
500
(a) FMNIST with
(b) FMNIST with
(c) FMNIST with
12
Figure 9: Scalability analysis on the FMNIST dataset under varying network sizes (n = 5, 8, 12).
Table 2: Test accuracy on the MNIST and FMNIST datasets under different communication topologies
(n 8).
MNIST
FMNIST
Algorithms
Ring
Ladder
Random
Ring
Ladder
Random
AdaSDBO
0.908 + 0.001
0.911 + 0.001
0.913
0.001
0.774 + 0.003
0.788 + 0.003
0.790 + 0.003
SLDBO
0.871 = 0.002
0.871 + 0.001
0.871 + 0.001
0.758 + 0.002
0.758 + 0.002
0.758 = 0.001
MA-DSBO
0.850 + 0.001
0.850 1 0.001
0.850
0.002
0.709 1 0.002
0.716 0.001
0.719 1 0.002
MDBO
0.753 0.002
0.754
0.001
0.754
0.002
0.650
0.001
0.650 1 0.002
0.653 1 0.001
For all experiments, except for the accuracy versus stepsize comparison, we use the following parameter settings. For the baseline methods SLDBO and MA-DSBO, the stepsizes for updating and set 0.01, while the stepsize for updating y set to 0.02, following the optimal stepsize order described in [Dong et al.) 2023] Chen et al. 2023]. For the baseline methods DBO and MDBO, the stepsizes for updating both x and y are set 0.01. For AdaSDBO. we set 7+ Ty = Yv and initialize m = m.o o m. = 10. Vi E [n]. All experiments were conducted on host machine equipped with Intel(R) Xeon(R) W9-3475X CPU running at 2.20 GHz (maximum turbo frequency: 4.80 GHz), featuring 36 physical cores and 72 threads. The system was configured with 256 GB of DDR5 ECC RAM and a single NVIDIA(R) RTX(TM) A6000 GPU with GB of memory.
E.6 Additional Results
For the synthetic dataset, we increased the data heterogeneity parameter r to 5 and analyzed the convergence performance of different methods under two data dimensions (p = 50 and p = 200). can observed in Figure that our proposed algorithm consistently outperforms the baseline methods in both convergence and test accuracy, even as the level of data heterogeneity increases. This superior performance can be attributed the adaptive stepsizes design, which enables our algorithm to dynamically adjust stepsizes accommodate varying data distributions. Consequently, our proposed method demonstrates robust performance across different data heterogeneity settings, effectively adapting to changes in the data environment.
59

---

0.56
0.56
Training Accuracy
0.49
Test Accureey
0.42
0.42
00.35
00.35
0.28
0.28
SLDBO
SLDBO AdaSDBO
0.21
AdaSDBO
0.21
200
600
800
1000
200
400
600
800
1000
Iterations
Nterations
(a) Training Accuracy
(b) Test Accuracy
Figure 10: Performance comparison between AdaSDBO and SLDBO under the MAMI framework, where each node employs an identical CNN for 5-way, 50-shot classification on the CIFAR-10 dataset.
Table 3: Performance comparison between AdaSDBO and SLDBO under varying network sizes in the decentralized meta-learning task.
10
20
30
Algorithms
Train Acc
Test Ace
Train Acc
Test Acc
Train Acc
Test Acc
AdaSDBO
0.543 + 0.002 0.534 + 0.002 0.542 + 0.002 0.534 + 0.001
0.538 i 0.001 0.533 + 0.001
SLDBO 0.503 1 0.004 0.488 + 0.005 0.472 1 0.006 0.461 0.006 0.486 1 0.006 0.475 1 0.007
Furthermore, we assessed the performance of different methods across varying network connectivity levels (PW) the synthetic, MNIST, and FMNIST datasets. As depicted in Figure 5 Figure 6 and Figure 7 increasing the network connectivity (i.c., decrease in PW from 0.5393 to 0.4860), leads improved accuracy for all methods across the different datasets. Notably, our proposed algorithm maintains superior convergence performance compared to all baseline methods on each dataset, validating its effectiveness and reliability under different levels of network connectivity.
In Figure [8 and Figure 9 we evaluate the broader scalability of our proposed method by varying the number of nodes = 5, 8, 12 on the MNIST and FMNIST datasets. We compare AdaSDBO against several baseline algorithms, including SLDBO [Dong al., 2023), MA-DSBO [Chen et al.. 2023), and MDBO |Gao et al.) 2023). The results show that AdaSDBO achieves convergence performance competitive with these state-of-the-art methods. Furthermore, AdaSDBO maintains stable performance across different system configurations, underscoring its case of deployment nature
and practical applicability. This stability can be attributed to the of AdaSDBO, which eliminates the need for manually tuned stepsizes. In contrast, other methods in decentralized settings often suffer from sensitivity to stepsize selection due to their reliance on parameters, which typically unknown or difficult to estimate in practice. As a result, the parameter-fre property of AdaSDBO makes it particularly well-suited for real-world decentralized applications.
problem-
To assess sensitivity to network structure, we conducted experiments under three commonly used communication topologies ring, ladder, and random-aae and compared the performance of AdaSDBO with baseline methods. Structural details for these topologies are provided in the Appendix [Li ct al. 2024]. The results summarized in Table indiicate that stronger connectivity leads to faster and more stable convergence: in particular, the random topology. which has the highest connectivity, yields the fastest and most stable convergence for all methods. Across the three topologies, AdaSDBO consistently outperforms the baselines, maintaining strong performance under variations in the communication topology. This robustness is facilitated by the adaptive stepsize mechanism of AdaSDBO, which accommodates dopology-induce heterogeneity.
For the decentralized meta-learning experiment, we compared our proposed algorithm with the single-loop decentralized bilevel optimization method SIDBOO [Dong al., [023). Figure shows that AdaSDBO consistently outperforms SLDBO in both average training accuracy across all nodes
60

---

and test accuracy, demonstrating the effectiveness of our approach in decentralized meta-learning tasks. We further increase the number of agents 10, 20, and 30; the results in Table inddicate that AdaSDBO remains stable and competitive as the network scales, outerforming the baselines even in more complex settings. The superior performance of AdaSDBO stems from its problem-parameter free design, which enables stepsize selection without requiring knowledge of problem-specific parameters. Furthermore, the adaptive nature of our method allows AdaSDBO to dynamically adjust its learning dynamics and consistently achieve optimal convergence rates-evee even in decentralized settings where hyperparameter tuning particularly difficult for other methods. This advantage becomes more evident in complex decentralized meta- meta-learning tasks, further underscoring the robustness and scalability of our proposed approach.
61

---

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

---

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

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: The experimental results shown in the submitted manuscript do not depend on private datasets and can be reproduced by following the provided instructions and settings.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://miis.cc.
Phollic/guidee//odeeeuuiiss wtw.eeeesuumiisioooooooooooo for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. wttpccppppcpcpcceeeeeeeeepppeeee
www.sssoiccgyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have provided detailed descriptions of the training and test setups, as well as all experimental configurations.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The paper has provided appropriate information about the statistical signifi- cance of the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
64

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We have provided the description of the type of compute workers and memory.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: htttlp::///neuriie wtw.rpsu.p...// cc/ppublic/thiiccccueeeel......
Answer: [Yes]
Justification:
The research conducted in the paper conforms with the NeurIPS Code of
Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
65

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
All the datasets used in our experiments are publicly available.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
66

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
67

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
68


Reviews:
[{"review_id": "CN79LMQcHL", "reviewer": "Reviewer_3RRn", "summary": "The authors propose AdaSDBO -- a parameter-free single-loop algorithm for decentralized bilevel optimization. Leveraging accumulators and a hierarchical stepsize schedule, the algorithm eliminates the need for knowledge of smoothness and strong-convexity constants. Authors provide theoretical analysis showing that AdaSDBO achieves an $O\\left(\\frac{\\log^4{T}}{T}\\right)$ stationarity rate. Experiments on synthetic and real-world problems, and CIFAR-10 meta-learning demonstrate competitive performance compared to baselines.", "questions": "1. The second equation on line 174 is not informative — removing it might improve readability.\n2. What is the set $\\mathcal{V}$?\n3. Figure 2 (c & d) — in the legend description, the formula $(n = x)$ is not horizontally centered.", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The authors guide the reader through the paper step by step, explaining design choices from a high-level perspective.\n2. The algorithm is parameter-free, so practitioners can deploy the algorithm without tuning hyperparameters.\n3. The authors establish the SOTA $O(\\log^{4}T/T)$ convergence rate, although I have not checked the proofs.\n\nWeaknesses:\n1. The experiments cover only a few graph shapes, and they do not disclose how the topology of the network affects the convergence.\n2. Many deep-learning tasks are neither smooth nor strongly convex, which limits the direct relevance of the theory.", "was_revised": true, "final_justification": "This work represents a relevant contribution to the area of problem-free methods. The authors provide a clear exposition of their results and support their claims with sufficient and meaningful experiments.", "rebuttal": "**We sincerely appreciate the reviewer for recognizing our contributions and for the constructive comments. Our point-to-point responses to concerns on Weaknesses and Questions are given below.**\n\n**Reply to Weaknesses:**\n\n**1.** Thank you for your insightful comment. Following your suggestion, we have conducted additional experiments with two additional graph topologies beyond the ring: ladder and complete, using 8 agents on both the MNIST and FashionMNIST datasets. The structural details of these topologies can be found in the Appendix of [1]. A summary of the experimental results across the different topologies is provided below:\n\n**Table 1: Convergence Performance under Different Topologies ($n=8$)**\n\n---\n| Dataset |       |  &nbsp; &nbsp;&nbsp; &nbsp;MNIST   |             |      | &nbsp; &nbsp;&nbsp; FMNIST      |      |\n|----------|:------------------:|:--------------------:|:--------------------:|:-----------------------:|:--------------------:|:--------------------:|\n| Algorithms | Ring |Ladder | Complete | Ring |Ladder | Complete | \n| AdaSDBO   | $0.908\\pm 0.001$ |$0.911\\pm 0.001$| $0.916\\pm 0.001$   | $0.774\\pm 0.003$ |$0.788\\pm 0.003$   | $0.798\\pm 0.002$  |\n| SLDBO |  $0.871\\pm 0.002$  | $0.871\\pm 0.001$  | $0.872\\pm 0.001$    | $0.758\\pm 0.002$ |$0.758\\pm 0.002$   | $0.758\\pm 0.001$ |\n| MA-DSBO |  $0.850\\pm 0.001$  | $0.850\\pm 0.001$ | $0.851\\pm 0.002$   | $0.709\\pm 0.002$ |$0.716\\pm 0.001$   | $0.720\\pm 0.002$  |\n| MDBO | $0.753\\pm 0.002$ | $0.754\\pm 0.001$ | $0.764\\pm 0.001$   | $0.650\\pm 0.001$ |$0.650\\pm 0.002$   | $0.653\\pm 0.001$ |\n---\n\nAs shown in the table above, better network connectivity leads to faster convergence and improved final performance. The complete topology, having the highest connectivity, achieves the best convergence rate and stability, while the ring topology lags behind due to its minimal connectivity. \n\n**2.** Thank you for your valuable comment. We agree that many deep learning problems do not satisfy smoothness or strong convexity assumptions, particularly in realistic scenarios where both levels of the bilevel problem may be nonconvex. However, due to the inherent complexity of analyzing fully nonconvex bilevel problems, most existing theoretical works on bilevel optimization—such as [2]-[4]—primarily focus on the nonconvex-strongly-convex setting.\n\nWe acknowledge that extending the theory to fully nonconvex–nonconvex settings is a highly significant direction, but it remains a challenging open problem in decentralized bilevel optimization. In such cases, the lower-level solution may not be unique, and the upper-level objective can become non-differentiable [5]. Addressing these challenges would require the development of fundamentally different techniques, which are beyond the scope of this work. We plan to investigate this in future work, thank you once again for your insightful comment.\n\n**Reply to Questions:**\n\n**1.** Thank you for your helpful suggestion. Following your advice, we have removed this equation in the revised version to enhance clarity.\n\n**2.** Thank you for your question. The set $\\mathcal{V}$ refers to the domain of the auxiliary variable $v$, we have clarified this definition explicitly to improve readability.\n\n**3.** Thank you for pointing this out. We have adjusted the formatting in the legend of Figure 2 (c & d) to ensure that the formula is now properly horizontally centered.\n\n**References:**\n\n[1] Problem-Parameter-Free Decentralized Nonconvex Stochastic Optimization.\n\n[2] Decentralized Bilevel Optimization over Graphs: Loopless Algorithmic Update and Transient Iteration Complexity.\n\n[3] A Single-Loop Algorithm for Decentralized Bilevel Optimization.\n\n[4] SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization.\n\n[5] On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis.\n\n**Thank you once again for your thoughtful review and constructive feedback.**"}, {"review_id": "wwK2ww7aPu", "reviewer": "Reviewer_Xg2q", "summary": "This paper proposes AdaSDBO, a fully problem-parameter-free algorithm for decentralized bilevel optimization with a single-loop structure. AdaSDBO employs adaptive stepsizes based on cumulative gradient norms to simultaneously update all variables, enabling dynamic adjustment without requiring problem-specific hyperparameter tuning. Theoretical analysis in the nonconvex–strongly-convex bilevel setting shows that AdaSDBO achieves a convergence rate matching that of well-tuned state-of-the-art methods up to polylogarithmic factors. Extensive experiments validate the effectiveness and robustness of AdaSDBO across various tasks and settings.", "questions": "1. What is the rationale behind using the accumulators in Lines 178 and 181? Transmitting gradient norms can significantly increase communication overhead. Are there alternative accumulator designs that could reduce this cost?\n2. What motivated the design of the primal variable update in Line 196? Could the authors provide more explanation for the choice of the proportional terms used in the update?", "limitations": "Please refer to weaknesses.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "AdaSDBO leverages accumulated gradient norms to dynamically adjust stepsizes at each iteration, thereby eliminating the need for hyperparameter tuning. It introduces two key mechanisms: (1) a hierarchical stepsize design that accounts for the interdependence of variables while preserving the autonomy of adaptive updates; and (2) a stepsize tracking scheme that synchronizes gradient-norm accumulators across agents, effectively mitigating stepsize discrepancies in the decentralized setting. The effectiveness of AdaSDBO is supported by both rigorous theoretical analysis and comprehensive experimental results.\n\n**Weaknesses:**\n1. The stepsize tracking scheme introduces significant communication overhead due to the additional transmission of gradient norms.\n2. AdaSDBO appears to be designed for deterministic bilevel optimization and relies on full gradient information, limiting its applicability in stochastic settings.\n3. While often considered negligible, the convergence rate includes an extra $\\log^4(T)$ factor, which creates a gap compared to the optimal $O(1/T)$ rate.\n4. Each iteration requires Jacobian and Hessian computations, which can be computationally expensive for large-scale problems and may hinder scalability.\n5. The experimental evaluation is limited in scale, involving no more than 12 agents and relatively simple datasets and models.\n6. The runtime performance of the algorithm is not reported, making it difficult to assess its practical efficiency.\n7. The code is not provided, which hinders the reproducibility of the experimental results.", "was_revised": true, "final_justification": "As most of my concerns—such as the communication overhead, the scale of the experimental settings, and the practical efficiency of the algorithm—have been addressed, I increase my score by one.", "rebuttal": "**We sincerely appreciate the reviewer for recognizing our contributions and for the constructive comments. Our point-to-point responses to concerns on Weaknesses and Questions are given below.**\n\n**Reply to Weaknesses:**\n\n**1.** Thank you for your thoughtful comment. The stepsize tracking scheme is a key component of our problem-parameter-free framework. Due to the hierarchical nature of decentralized bilevel optimization, multiple coupled adaptive stepsizes naturally arise and may evolve inconsistently across agents. Without proper coordination, this variability may impair convergence. Importantly, our method employs a lightweight tracking mechanism that synchronizes scalar stepsizes across agents. The resulting communication overhead is minimal—only scalar values are exchanged—especially when compared to the cost of transmitting primal variables ($x$), dual variables ($y$), and auxiliary variables ($v$), which are commonly involved in decentralized bilevel methods.\nIn summary, our approach does not incur significant communication overhead relative to existing methods, while simultaneously offering a robust and problem-parameter-free solution to decentralized bilevel optimization.\n\n**2.** Thank you for your insightful comment. Extending the proposed methods to stochastic bilevel optimization remains a challenging direction with several open theoretical issues:\n\n- The variance in both first- and second-order gradient estimates can affect the reliability of stepsize bounds and compromise algorithmic stability.\n\n- The two-stage convergence analysis and the coupled stepsize structure adopted in our framework may require additional conditions or variance-reduction techniques to ensure convergence in the stochastic setting.\n\nIn this work, our primary aim is to establish **the first problem-parameter-free method for decentralized bilevel optimization**, which lays a solid foundation in the current literature. We are enthusiastic about extending our framework to stochastic settings in future work.\n\n**3.** Thank you for your thoughtful comment. We acknowledge that the $\\log^4(T)$ term introduces a slight theoretical gap compared to the $\\mathcal{O}(1/T)$ rate. However, in optimization research, such logarithmic factors are generally considered marginal due to their much slower growth compared to polynomial terms [1]–[4]. In our work, the presence of this logarithmic term stems from the accumulated gradient norms used for adaptive stepsize adjustment. Accordingly, it is an inherent consequence of achieving a problem-parameter-free implementation and is a common feature in similar problem-parameter-free algorithms (e.g., [1]–[5]). Given the significant practical advantages of removing the need for problem-specific tuning, this slight theoretical gap is widely regarded as acceptable and well-justified in the current literature.    \n\n**4.** Thank you for your thoughtful comment. We agree that computing the full Hessian matrix can be expensive, especially for large-scale problems. However, we respectfully clarify that our method only requires computing an approximate Hessian–vector product, rather than the full Hessian matrix, which is significantly more efficient.\n\nSpecifically, we compute the Hessian–vector product  $\\nabla^{2} \\ell(x, y)  v$ indirectly using the identity $\\nabla^{2} \\ell(x, y) v = \\nabla \\left( \\nabla \\ell(x, y)^{\\top} v \\right).$\n\nThis computation involves the following two steps:\n\n- Compute the inner product  $s := \\nabla \\ell(x, y)^{\\top} v,$ which is a scalar and only requires first-order gradient evaluations.\n\n- Compute the gradient of $s$ with respect to $y$: $\\nabla s = \\nabla \\left( \\nabla \\ell(x, y)^{\\top} v \\right) = \\nabla^{2} \\ell(x, y) v.$\n\nThis two-step process avoids forming the full Hessian explicitly and relies only on gradient-like operations. As a result, the computational overhead is much lower than directly computing or storing the full Hessian.\n\n**5.** Thank you for your constructive comment. To address this concern, we have conducted additional experiments on a more challenging decentralized meta-learning task using the CIFAR-10 dataset with a CNN model. In particular, we extended the number of agents to 10, 20, and 30—the widest setting we could support given our limited computational resources.\nWe summarize the results in the table below:\n\n**Table 1: Convergence Performance under Different Number of Agents with Decentralized Meta-Learning Task**\n\n---\n|Number of Agents||$n=10$||$n=20$||$n=30$|\n|---|:---:|:---:|:---:|:---:|:---:|:---:|\n|Algorithms|Train Acc|Test Acc|Train Acc|Test Acc|Train Acc|Test Acc|\n|AdaSDBO|$0.543\\pm0.002$|$0.534\\pm0.002$|$0.542\\pm0.002$|$0.534\\pm0.001$|$0.538\\pm0.001$|$0.533\\pm0.001$|\n|SLDBO|$0.503\\pm0.004$|$0.488\\pm0.005$|$0.472\\pm0.006$|$0.461\\pm0.006$|$0.486\\pm0.006$|$0.475\\pm0.007$|\n---\n\nThese results demonstrate that AdaSDBO remains consistently stable and competitive as the number of agents increases, outperforming the baselines even under more complex settings. We have also made every effort to add new experiments on the CIFAR-100 dataset using a ResNet-18 model with varying numbers of agents. The results, presented in the following table, confirm the sustained superior performance of our proposed method.\n\n**Table 2: Convergence Performance on the CIFAR-100 Dataset with Varying Numbers of Agents**\n\n---\n|Algorithms|&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$n=5$|&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$n=8$|\n|---|:---:|:---:|\n|AdaSDBO|$0.426\\pm0.002$|$0.417\\pm0.003$|\n|SLDBO|$0.401\\pm0.005$|$0.388\\pm0.005$|\n---\n\n**6.** Thank you for your helpful comment. To assess the practical efficiency of our algorithm, we report the total wall-clock runtime required to complete training over 500 communication rounds under different network topologies, using the MNIST and FMNIST datasets. The structural details of these topologies can be found in the Appendix of [1]. The results are summarized below:\n\n**Table 3: Total Runtime Performance under Different Topologies ($n=8$)**\n\n---\n|Dataset||&nbsp;&nbsp;MNIST|||&nbsp;&nbsp;FMNIST||\n|---|:---:|:---:|:---:|:---:|:---:|:---:|\n|Algorithms|Ring (s)|Ladder (s)|Complete (s)|Ring (s)|Ladder (s)|Complete (s)| \n|AdaSDBO|$1029.6$|$1204.2$|$1502.4$|$1609.2$|$1636.8$|$1812.6$|\n|SLDBO|$999.6$|$1200.2$|$1498.2$|$1428.0$|$1483.8$|$1794.6$|\n|MA-DSBO|$1147.2$|$1215.2$|$1512.0$|$1619.4$|$1702.2$|$1833.6$|\n|MDBO|$1185.0$|$1217.4$|$1654.8$|$1677.6$|$1783.6$|$1906.2$|\n---\n\nFrom the results, we observe that AdaSDBO incurs slightly higher total runtime than the single-loop method SLDBO. However, in terms of convergence results, we respectfully refer you to Table 1 in our response to Reviewer 3RRn due to space limitations here, which demonstrates that AdaSDBO consistently achieves superior accuracy and convergence performance compared to SLDBO.\nThis implies that AdaSDBO requires less time to reach the same level of accuracy, highlighting its improved overall training efficiency. Moreover, compared to double-loop methods, AdaSDBO remains significantly more efficient in terms of both runtime and convergence performance.\n\n**7.** Thank you for your valuable comment. We will release our complete codebase upon acceptance via GitHub, including thorough documentation, running scripts, and configuration files.\n\n**Reply to Questions:**\n\n**1.** Thank you for your thoughtful question. The accumulators in our framework serve to adaptively adjust stepsizes by accumulating the squared gradients of each variable over time. The accumulator allows the algorithm to assign smaller stepsizes to variables with consistently large gradients, and larger stepsizes to those with smaller or infrequent gradients.\nThis is particularly important in decentralized bilevel settings, where gradient magnitudes can vary significantly across agents or levels. This mechanism enhances stability and robustness without requiring manual tuning of stepsize schedules.\n\nWe agree that communication efficiency is important in decentralized settings. However, in our framework, only scalar gradient norms are transmitted as accumulators, which incurs minimal overhead compared to exchanging high-dimensional variables.\nWhile alternative designs (e.g., compressed accumulators) could reduce communication, they risk losing global coordination, which is essential in our problem-parameter-free setting to avoid divergence from inconsistent learning dynamics.\nHowever, exploring more communication-efficient schemes—such as quantized norms or partial sharing—is an interesting direction for future work.\n\n**2.** Thank you for your question. The update in Line 196 concerns the upper-level variable $x$, which must be carefully coordinated with the lower-level variables $y$ and the auxiliary variable $v$ to maintain a faithful hypergradient approximation in single-loop decentralized bilevel optimization.\n\nIn our design, the stepsize for $x$ is conservatively adapted based on the accumulated gradient norms of $x$,\n$y$, and $v$. This ensures the upper-level update does not progress too aggressively relative to the lower level, which is crucial for maintaining stability in a single-loop, problem-parameter-free setting.\nThis hierarchical coordination plays a central role in balancing progress across levels and avoiding divergence in decentralized bilevel optimization.\n\n**References:**\n\n[1] Problem-Parameter-Free Decentralized Nonconvex Stochastic Optimization.\n\n[2] Two Sides of One Coin: The Limits of Untuned SGD and the Power of Adaptive Methods.\n\n[3] How Free is Parameter-Free Stochastic Optimization?\n\n[4] Tuning-Free Stochastic Optimization.\n\n[5] Learning-Rate-Free Stochastic Optimization over Riemannian Manifolds.\n\n**Thank you once again for your thoughtful review and constructive feedback.**"}, {"review_id": "73PXyWVmne", "reviewer": "Reviewer_oJg7", "summary": "The paper introduces AdaSDBO, a novel algorithm designed for decentralized bilevel optimization that does not require prior knowledge of problem parameters. The proposed method addresses the issue of hyperparameter tuning by employing adaptive step sizes based on cumulative gradient norms. This enables the algorithm to update variables simultaneously while adjusting its progress dynamically. The paper provides a thorough theoretical analysis demonstrating that AdaSDBO achieves competitive convergence rates. Furthermore, the experimental results confirm that AdaSDBO is robust and performs well across a range of step size configurations.", "questions": "See weakness.\n\nOther questions:\n1. In Figure 2, which variable's step size is being depicted? Since the proposed method involves three distinct step sizes, how sensitive is the method to the choice of initial values for these three step sizes?\n2. The proposed method is parameter-free, but from Figure 2, it appears that the step size still has a significant impact. Could you explain why this is the case?", "limitations": "This paper focus on the algorith and analysis and does not have societal impact .", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength：\n1. The approach of eliminating the need for problem-specific hyperparameter tuning is a significant contribution to decentralized bilevel optimization. \n2. The paper includes a detailed theoretical analysis of AdaSDBO, demonstrating its convergence rate and the conditions under which the algorithm performs comparably to state-of-the-art methods. \n3. By removing the dependence on problem-specific hyperparameters, AdaSDBO could be particularly valuable in real-world applications, where such parameters are often unknown or costly to determine.\nWeakness:\n1. Although the experiments are comprehensive, it would be beneficial to see more experiments on large datasets. The experiments on MNIST, FashionMNIST and Cifar10 are not enough.\n2. In decentralized algorithms, communication overhead is a critical concern. The paper does not provide a detailed analysis of the communication complexity of AdaSDBO, which could be important for real-world applications involving distributed systems. A comparison of communication cost with other methods could be helpful.\n3. The proposed method relies on the strongly convex assumption of the lower level, which is restrictive in the real world.", "was_revised": true, "final_justification": "My concern has been solved. I will raise my score", "rebuttal": "**We sincerely appreciate the reviewer for recognizing our contributions and for the constructive comments. Our point-to-point responses to concerns on Weaknesses and Questions are given below.**\n\n**Reply to Weaknesses:**\n\n**1.** Thank you for your helpful suggestion. To further validate the effectiveness of our proposed method on more complex datasets, we have added new experiments on the CIFAR-100 dataset using ResNet-18 model with varying numbers of agents. The results are summarized below:\n\n**Table 1: Convergence Performance on the CIFAR-100 Dataset with Varying Numbers of Agents**\n\n---\n| Algorithms |  &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;$n=5$ | &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;$n=8$ |\n|-----------------|:--------------:|:------------:|\n| AdaSDBO   | $0.426\\pm0.002$ | $0.417\\pm0.003$ |\n| SLDBO     | $0.401\\pm0.005$ | $0.388\\pm0.005$ |\n---\n\nMoreover, we have made every effort to further validate the robustness of our method by adding experiments on the MNIST, FashionMNIST, and CIFAR-10 datasets, as shown below:\n\n- Added more experiments on MNIST and FashionMNIST by varying the network topology, with the corresponding structural specifications described in the Appendix of [1], as shown in the following table.\n\n**Table 2: Convergence Performance under Different Topologies ($n=8$)**\n\n---\n| Dataset |       |  &nbsp; &nbsp;&nbsp; &nbsp;MNIST   |             |      | &nbsp; &nbsp;&nbsp; FMNIST      |      |\n|----------|:------------------:|:--------------------:|:--------------------:|:-----------------------:|:--------------------:|:--------------------:|\n| Algorithms | Ring |Ladder | Complete | Ring |Ladder | Complete | \n| AdaSDBO   | $0.908\\pm 0.001$ |$0.911\\pm 0.001$| $0.916\\pm 0.001$   | $0.774\\pm 0.003$ |$0.788\\pm 0.003$   | $0.798\\pm 0.002$  |\n| SLDBO |  $0.871\\pm 0.002$  | $0.871\\pm 0.001$  | $0.872\\pm 0.001$    | $0.758\\pm 0.002$ |$0.758\\pm 0.002$   | $0.758\\pm 0.001$ |\n| MA-DSBO |  $0.850\\pm 0.001$  | $0.850\\pm 0.001$ | $0.851\\pm 0.002$   | $0.709\\pm 0.002$ |$0.716\\pm 0.001$   | $0.720\\pm 0.002$  |\n| MDBO | $0.753\\pm 0.002$ | $0.754\\pm 0.001$ | $0.764\\pm 0.001$   | $0.650\\pm 0.001$ |$0.650\\pm 0.002$   | $0.653\\pm 0.001$ |\n---\n\n- Added new experiments on CIFAR-10 by varying the number of agents in the decentralized meta-learning setup, as presented in the table below.\n\n**Table 3: Convergence Performance under Different Number of Agents with Decentralized Meta-Learning Task**\n\n---\n| Number of Agents |  | $n=10$  |  | $n=20$ | | $n=30$ |\n|------------------|:-----------------:|:----------------:|:----------------:|:----------------:|:----------------:|:---------------:|\n| Algorithms | Train Acc | Test Acc | Train Acc | Test Acc | Train Acc | Test Acc |\n| AdaSDBO               | $0.543\\pm0.002$ | $0.534\\pm0.002$|$0.542\\pm0.002$|$0.534\\pm0.001$ | $0.538\\pm0.001$ | $0.533\\pm0.001$|\n| SLDBO               | $0.503\\pm0.004$ | $0.488\\pm0.005$| $0.472\\pm0.006$ |$0.461\\pm0.006$|$0.486\\pm0.006$ |$0.475\\pm0.007$|\n---\n\nThese additional results further confirm the robustness and superior performance of our proposed AdaSDBO method across diverse settings.\n\n**2.** Thank you for your insightful comment. Through a consolidation of our theoretical analysis, we can get that the communication complexity of AdaSDBO is $\\mathcal{O}\\left(\\frac{1}{\\epsilon(1 - \\rho_W)^2} \\log^4\\left(\\frac{1}{\\epsilon}\\right)\\right)$, which matches the results of existing methods such as [2]–[4], up to logarithmic factors. Since logarithmic terms grow significantly slower than polynomial ones, they are typically considered negligible in the context of optimization theory (e.g., [1], [5]–[6]).\n\nIn sharp contrast to [2]–[4], AdaSDBO is entirely problem-parameter-free, requiring no knowledge of problem-specific constants or manual hyperparameter tuning. This makes it significantly easier to deploy and more robust in heterogeneous, real-world decentralized systems.\nCombined with its competitive communication complexity, this problem-parameter-free design underscores the practical advantages of AdaSDBO over existing decentralized bilevel methods. We have included comparisons of communication cost with existing works in our paper.\n\n**3.** Thank you for your thoughtful comment. We acknowledge that the strong convexity assumption on the lower-level problem may not always hold in real-world applications. However, this assumption remains a standard and widely adopted condition in the bilevel optimization literature [2]-[4].\n\nWe agree that extending the theory to handle nonconvex lower-level problems is an important and nontrivial direction. In such cases, the solution set may be non-unique and the overall objective may become non-differentiable [7], requiring fundamentally different algorithmic frameworks. This remains a challenging open problem in decentralized bilevel optimization. We regard this as an important direction for future research and appreciate the reviewer for highlighting this point.\n\n**Reply to Questions:**\n\n**1.** Thank you for your thoughtful question. In Figure 2 of our paper, for baseline methods, we first tune the stepsizes for each optimization variable to their optimal values, and then test sensitivity by scaling these stepsizes up or down by factors of 10. This is necessary because baseline algorithms require precise tuning of individual stepsizes to properly control the progress of different variables.\n\nIn contrast, our proposed problem-parameter-free method uses the same initial stepsize for all three variables $x$, $y$, and $v$. This simple choice is supported by our hierarchical adaptive stepsize mechanism:\n- The update for $v$ uses a stepsize inversely proportional to $\\max(m^v_{i,t+1}, m^y_{i,t+1})$,\n- The update for $x$ uses a stepsize inversely proportional to $m^x_{i,t+1} \\max(m^v_{i,t+1}, m^y_{i,t+1})$, making it more conservative,\n\nwhere $m^x_{i,t+1}$, $m^y_{i,t+1}$, and $m^v_{i,t+1}$ denote the gradient accumulators for the primal variable $x$, dual variable $y$, and auxiliary variable $v$, respectively. This structure ensures:\n- $v$ progresses no faster than $y$,\n- $x$ progresses no faster than both $y$ and $v$,\n\nthus maintaining a well-coordinated dynamic across levels and preserving the fidelity of the hypergradient approximation. As a result, our method is robust to the initial stepsize setting, and automatically adapts to reach optimal convergence performance without manual tuning.\n\n**2.** Thank you for your insightful question. Through our two-stage theoretical analysis, we have rigorously shown that our problem-parameter-free algorithm guarantees convergence to a stationary point without requiring any specific tuning of stepsize values. However, in practice, the initial stepsize value can still influence the speed of convergence. This behavior is typical of AdaGrad-norm-based adaptive methods. Specifically:\n\n- When the initial stepsize is excessively large, early gradient updates may cause the accumulated gradient norms to grow quickly, which in turn causes the adaptive stepsize to shrink prematurely. This leads to slower progress in subsequent iterations.\n\n- Conversely, when the initial stepsize is too small, the early updates are overly conservative, and the method takes longer to begin meaningful descent—even though the stepsize will eventually adapt.\n\nDespite this, convergence is still ensured in both cases due to the adaptivity of our design. The observed sensitivity only affects the rate of convergence, not the final outcome. With sufficient communication rounds, our method can still achieve optimal performance.\nImportantly, our method is robust across a much wider range of stepsize values compared to existing baselines, many of which fail to converge if the stepsizes are not properly set. This highlights the practical value of our design, which eliminates the need for manual tuning while maintaining convergence guarantees.\n\n**References:**\n\n[1] Problem-Parameter-Free Decentralized Nonconvex Stochastic Optimization.\n\n[2] On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network.\n\n[3] A Single-Loop Algorithm for Decentralized Bilevel Optimization.\n\n[4] Decentralized Bilevel Optimization.\n\n[5] How Free is Parameter-Free Stochastic Optimization?\n\n[6] Tuning-Free Stochastic Optimization.\n\n[7] On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis.\n\n**Thank you once again for your thoughtful review and constructive feedback.**"}, {"review_id": "dSdgFvvry1", "reviewer": "Reviewer_Y6eW", "summary": "This paper introduces AdaSDBO, an innovative adaptive single-loop algorithm for decentralized bilevel optimization that eliminates the need for problem-specific hyperparameter tuning. By dynamically adjusting stepsizes based on accumulated gradient norms and incorporating a hierarchical stepsize design, AdaSDBO efficiently balances updates across primal, dual, and auxiliary variables. Theoretically, the algorithm achieves a convergence rate of $\\widetilde{\\mathcal{O}}(\\log^4(T)/T)$, matching state-of-the-art methods while remaining robust to stepsize choices. Extensive experiments on synthetic and real-world datasets, including hyperparameter optimization and meta-learning tasks, demonstrate AdaSDBO’s competitive performance and superior adaptability compared to existing approaches.", "questions": "1. The algorithm has 6 hyper-parameters, which is much more than the other decentralized bilevel algorithms. Would this make algorithm hard to tune? How sensitive is performance to their choice, and do you have guidelines for setting them?\n\n2. In algorithm step 6, the communication cost seems to be 6x of the model parameters. Is the proposed algorithm communication-costly than other decentralized bilevel algorithms?\n\n3. Although the hyper-parameters doesn't reply on the problem-parameters, how about the final convergence rate? If the final convergence rate is also affected by these problem-parameters, does it mean the algorithm still need hyper-parameters tuning based on the problem-parameters to achieve similar convergence speed?\n\n4. The experiments use relatively small networks. How does the algorithm scale to hundreds or thousands of nodes?", "limitations": "The paper didn't discuss the limitation. It may worth to discussing the algorithm communication complexity, memory cost and its applicable in real world tasks.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength: The paper studied the decentralized bilevel problem and proposed a novel algorithm of which the hyper-parameter selection does not rely on problem-specific factors. The rigorous theoretical analysis is provided in the paper with clear format. Numerical experiments are provided to verify the results. Overall, the paper is well-written and with clear novelty. \n\n\nWeakness: \n- How the algorithm become problem-parameter-free is unclear. It may be better to highlight what algorithm improvement achieve this.\n- It is better to verify in numerical study that the algorithm is truly problem-parameter-free and outperforms the existing algorithms.", "was_revised": true, "final_justification": "All my concern are addressed by the authors' responses.", "rebuttal": "**We sincerely appreciate the reviewer for recognizing our contributions and for the constructive comments. Our point-to-point responses to concerns on Weaknesses and Questions are given below.**\n\n**Reply to Weaknesses:**\n\n**1.** Thank you for the helpful comment. In our work, problem-parameter-free refers to the fact that our algorithm achieves a convergence rate of ${\\mathcal{O}}(\\log^4 T/T)$ without requiring any constraints or tuning on the stepsizes for the optimization variables $x$, $y$, and $v$. This is made possible through two key algorithmic innovations:\n\n- *Hierarchical Adaptive Stepsize Design:*\nWe introduce a principled stepsize structure that automatically balances updates across the three optimization levels. Specifically, the stepsize for updating $v$ depends on the gradient magnitudes of both $v$ and $y$, while the update for $x$ is more conservatively adjusted based on the accumulated gradients of $x$, $y$, and $v$.\nThis hierarchical design ensures that $x$ and $v$ progress more slowly than $y$, preserving the stability and fidelity of the bilevel dynamics—without needing problem-specific hyperparameter tuning.\n\n- *Stepsize Tracking Mechanism:*\nDecentralized bilevel optimization naturally leads to coupled, agent-specific adaptive stepsizes, which can become inconsistent and degrade convergence in heterogeneous networks. To address this, we incorporate a stepsize tracking mechanism in which agents exchange lightweight scalar gradient accumulators. This ensures that the stepsizes for $x$, $y$, and $v$ remain globally consistent, even in the presence of heterogeneity.\n\nTogether, these components enable us to develop the first problem-parameter-free algorithm for decentralized bilevel optimization that achieves optimal convergence without any reliance on problem-specific constants or manual tuning.\n\n**2.** Thank you for the thoughtful comment. We respectfully clarify that we have already conducted a detailed numerical study to verify the problem-parameter-free nature of our algorithm, as presented in Figure 2 of the paper.\n\nIn this experiment, we compare the test accuracy of our proposed AdaSDBO algorithm against several baseline methods across a wide range of stepsize values (from $10^{-3}$ to $10^{2}$). The results clearly show that:\n\n- AdaSDBO maintains stable and competitive performance across the entire range of tested stepsizes.\n\n- In contrast, baseline algorithms exhibit much narrower windows of stability and performance, indicating a strong sensitivity to stepsize selection.\n\nThese findings highlight the robustness of AdaSDBO with respect to stepsize choices and directly support its problem-parameter-free design. Unlike existing methods that require careful tuning for each optimization variable, our approach consistently performs well without manual adjustment—further demonstrating its practical effectiveness.\n\n**Reply to Questions:**\n\n**1.** Thank you for your question. While our method introduces three adaptive stepsizes—one for each of the variables $x$, $y$, and $v$—we respectfully clarify that no tuning is required for these hyperparameters due to our hierarchical adaptive stepsize design. In simple terms, all three stepsizes can be initialized with the same value, and the algorithm will automatically adjust them throughout training:\n\n- The stepsize for updating $v$ is adaptively adjusted based on the maximum of the gradient accumulators from both $v$ and \n$y$, ensuring that $v$ does not progress faster than $y$.\n\n- The stepsize for updating $x$ is made even more conservative by incorporating the accumulators of $x$, $y$, and $v$, so that $x$ progresses slower than both $v$ and $y$, preserving the hierarchical update structure.\n\nWith this adaptive mechanism, our method is highly insensitive to the choice of the initial stepsize. This stands in contrast to existing decentralized bilevel algorithms that often require precise tuning to prevent instability or poor performance.\n\n**2.** Thank you for your insightful question. We agree that Step 6 involves synchronization of adaptive stepsizes across agents. However, this synchronization is highly efficient, as it only requires exchanging a few scalar values that track local gradient information for stepsize adjustment.\nCompared to the communication cost of transmitting full model parameters such as the primal variable $x$, dual variable $y$, and auxiliary variable $v$—which are typically high-dimensional—the added overhead from sharing scalar accumulators is negligible.\n\nTherefore, although our method includes an additional coordination step, it remains communication-efficient in practice. Moreover, this lightweight tracking mechanism ensures global consistency of stepsizes across agents, which is essential for achieving stable and problem-parameter-free convergence in decentralized bilevel optimization.\n\n**3.** Thank you for your valuable question. We respectfully clarify that while the final convergence rate of any optimization algorithm inherently depends on problem-specific properties (e.g., smoothness, convexity, curvature), our key contribution lies in the fact that our stepsize strategy does not rely on these parameters.\n\nIn our two-stage convergence analysis, we impose no constraints on the choice of stepsizes. The stepsize scheme employed in our method is inherently adaptive and optimal, allowing us to achieve the ${\\mathcal{O}}(\\log^4 T/T)$ convergence rate without requiring any knowledge of smoothness and strong convexity constants, the spectral gap of the graph adjacency matrix, or other problem-dependent parameters.\n\nThis stands in sharp contrast to problem-parameter-dependent methods, whose optimal convergence guarantees rely on carefully setting stepsizes based on such parameters. If these conditions are violated, those methods can no longer ensure optimal convergence.\n\nIn summary, while the convergence rate ultimately reflects the nature of the problem, our algorithm ensures that no hyperparameter tuning is needed based on problem parameters to attain this optimal performance.\n\n**4.** Thank you for your thoughtful question. Due to limited computational resources, we have done our best to evaluate the scalability of our algorithm on larger decentralized networks within a feasible range. Specifically, we conducted experiments on the decentralized meta-learning task with CIFAR-10 dataset using wider network sizes. The results are summarized below:\n\n**Table 1: Convergence Performance under Different Number of Agents with Decentralized Meta-Learning Task**\n\n---\n| Number of Agents |  | $n=10$  |  | $n=20$ | | $n=30$ |\n|------------------|:-----------------:|:----------------:|:----------------:|:----------------:|:----------------:|:---------------:|\n| Algorithms | Train Acc | Test Acc | Train Acc | Test Acc | Train Acc | Test Acc |\n| AdaSDBO               | $0.543\\pm0.002$ | $0.534\\pm0.002$|$0.542\\pm0.002$|$0.534\\pm0.001$ | $0.538\\pm0.001$ | $0.533\\pm0.001$|\n| SLDBO               | $0.503\\pm0.004$ | $0.488\\pm0.005$| $0.472\\pm0.006$ |$0.461\\pm0.006$|$0.486\\pm0.006$ |$0.475\\pm0.007$|\n---\n\nThese results demonstrate that AdaSDBO maintains consistently superior performance over baselines even as the number of agents increases.\nWhile this setup may not fully represent large-scale real-world systems with hundreds or thousands of nodes, such experimental scales are commonly adopted in the decentralized optimization literature [1]–[3] due to similar resource constraints. Moreover, AdaSDBO is inherently scalable due to its:\n\n- Problem-parameter-free design, which eliminates the need for manual hyperparameter adjustment across agents.\n\n- Single-loop architecture, avoiding costly nested optimization common in bilevel methods.\n\nThese properties suggest that AdaSDBO is well-suited for scaling to larger networks. \n\n**Reply to Limitations:**\n\nThank you for your constructive comment. We discuss the limitations of our method as follows:\n\n- *Communication Overhead*: Our framework requires the exchange of scalar gradient norms as accumulators, which incurs minimal overhead compared to transmitting high-dimensional variables. While more aggressive communication-saving techniques (e.g., quantized or partially shared accumulators) could further reduce cost, they risk losing the global coordination necessary for stable convergence. We consider this an interesting direction for future exploration.\n\n- *Memory Cost*: Adaptive methods like ours introduce a small additional cost for maintaining gradient accumulators. However, this cost is negligible compared to full gradient evaluations. Nonetheless, reducing memory usage remains a valuable direction for improving overall efficiency.\n\n- *Applicability to Real-World Tasks*: While our method is theoretically grounded in the nonconvex–strongly-convex setting, many real-world tasks involve fully nonconvex landscapes. Extending the framework to such general settings poses additional challenges (e.g., non-uniqueness, non-differentiability [6]) and represents an important open problem in decentralized bilevel optimization.\n\nWe have incorporated this discussion into our paper and are enthusiastic about exploring these directions in future work.\n\n**References:**\n\n[1] A Single-Loop Algorithm for Decentralized Bilevel Optimization.\n\n[2] Decentralized Bilevel Optimization over Graphs: Loopless Algorithmic Update and Transient Iteration Complexity.\n\n[3] Decentralized Bilevel Optimization.\n\n[4] Problem-Parameter-Free Decentralized Nonconvex Stochastic Optimization.\n\n[5] Fully First-Order Methods for Decentralized Bilevel Optimization.\n\n[6] On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis.\n\n**Thank you once again for your thoughtful review and constructive feedback.**"}]

Author rebuttal:

Meta-review: The paper addresses decentralized bilevel optimization and proposes AdaSDBO, a parameter-free single-loop algorithm that removes the need for problem-specific hyperparameter tuning. AdaSDBO leverages accumulated gradient norms together with a hierarchical stepsize scheme to dynamically adjust updates across agents while mitigating stepsize discrepancies in the decentralized setting. The authors provide rigorous theoretical analysis, showing that AdaSDBO achieves an $\mathcal{O}(1/T)$ stationarity rate in the nonconvex–strongly convex setting, matching state-of-the-art methods up to polylogarithmic factors. Extensive experiments on synthetic tasks, real-world problems, and CIFAR-10 meta-learning demonstrate its effectiveness and robustness. Overall, the paper is well written, with clear novelty and strong theoretical and empirical support. I therefore recommend acceptance. Below are some comments that should be clarified in the final version (they have been addressed in the rebuttal).  

- AdaSDBO is designed for deterministic bilevel optimization and relies on full gradient information, which limits its applicability in stochastic settings.  
- In decentralized algorithms, communication overhead is a critical concern. The paper does not provide a detailed analysis of AdaSDBO’s communication complexity, which could be important for real-world distributed systems. A comparison of communication costs with other methods would strengthen the work.
Decision: Accept (poster)