Decentralized Sporadic Federated Learning: A Unified Algorithmic Framework with Convergence Guarantees
Authors: Shahryar Zehtabi
Dong-Jun Han
Rohit Parasnis
Seyyedali Hosseinalipour
Christopher Brinton
Venue: ICLR 2025 Spotlight (2025)
Keywords: Decentralized Federated Learning
Sporadicity
Unified Algorithmic Framework
Convergence Analysis
Primary area: learning theory

Abstract: Decentralized federated learning (DFL) captures FL settings where both (i) model updates and (ii) model aggregations are exclusively carried out by the clients without a central server. Existing DFL works have mostly focused on settings where clients conduct a fixed number of local updates between local model exchanges, overlooking heterogeneity and dynamics in communication and computation capabilities. In this work, we propose Decentralized Sporadic Federated Learning ($\texttt{DSpodFL}$), a DFL methodology built on a generalized notion of *sporadicity* in both local gradient and aggregation processes. $\texttt{DSpodFL}$ subsumes many existing decentralized optimization methods under a unified algorithmic framework by modeling the per-iteration (i) occurrence of gradient descent at each client and (ii) exchange of models between client pairs as arbitrary indicator random variables, thus capturing *heterogeneous and time-varying* computation/communication scenarios. We analytically characterize the convergence behavior of $\texttt{DSpodFL}$ for both convex and non-convex models and for both constant and diminishing learning rates, under mild assumptions on the communication graph connectivity, data heterogeneity across clients, and gradient noises. We show how our bounds recover existing results from decentralized gradient descent as special cases. Experiments demonstrate that $\texttt{DSpodFL}$ consistently achieves improved training speeds compared with baselines under various system settings.

Published as a conference paper at ICLR 2025
DECENTRALIZED SPORADIC FEDERATED LEARNING: A UNIFIED ALGORITHMIC FRAMEWORK WITH CON- VERGENCE GUARANTEES
Shahryar Zehtabi
Dong-Jun Han Yonsei University djjeeoosei.ac.. ac..o.seiii.c...........
Rohit Parasnis
Purdue University biehtabb@@urdde... edu
MIT rohit100emit. edu
Seyyedali Hosseinalipour
Christopher G. Brinton
University at Buffalo (SUNY)
Purdue University cgbêpurdue edu
elipourebuffalo..
ABSTRACT
Decentralized federated learning (DFL. captures FL settings where both (i) model updates and (ii) model aggregations are exclusively carried out by the clients with- out central server. Existing DFL works have mostly focused settings where clients conduct a fixed number local updates between local model exchanges, overlooking heterogeneity and dynamics in communication and computation ca- pabilities. In this work, we propose Decentralized Sporadic Federated Learning (DSpodFL)), DFL methodology built generalized notion of sporadicity in both local gradient and aggregation processes. DSpodFL subsumes many exist- ing decentralized optimization methods under unified algorithmic framework by modeling the per-iteration (i) occurrence of gradient descent at each client and (ii) exchange models between client pairs as arbitrary indicator random variables, thus capturing heterogeneous and time-varying compuration/commuiiccca narios. We analytically characterize the convergence behavior of DSpodFL L for both convex and non-convex models and for both constant and diminishing learn- ing rates, under mild assumptions on the communication graph connectivity, data heterogeneity across clients, and gradient noises. We show how our bounds re- cover existing results from decentralized gradient descent as special cases. Exper- iments demonstrate that DSpodFT L. consistently achieves improved training speeds compared with baselines under various system settings.
sce-
INTRODUCTION
Traditional works in federated learning (FL) have focused conventional "star topology" con- figuration where clients are connected directly to a central server (Konečný et al.) 20166] Bonawitz et al. 2019). In this setup (Fig. Tab. FL iterates between (i) client-side local model updates, typically via stochastic gradient descent (SGD) on local datasets, and (ii) server-side model aggregations. However, central server may not always be present/feasible for synchronization, e.g., in the grow- ing body of direct peer-to-peer networks (Brinton et al. 2024). To address this, recent research has proposed decentralized federated learning (DFL) (Koloskova et al. 2020), replacing the server's role in FL aggregations with distributed optimization techniques (Nedić et al. 2018). This introduces new challenge DFL as clients need reach consensus while optimizing their local models via gradient descent (Figs. lb 1d). 'ooardds this end, clients exchange models with their neighbors over the decentralized topology form aggregations through gossip protocols (Huang et al., 2022).
FL settings are often dominated by heterogeneity and dynamics in various dimensions, including client processing capabilities, communication capabilities, and local dataset statistics varying across clients and over time (Li et al. 2020). This causes (i) computing gradients at every iteration to be costlier (e.g., in terms delay) at clients with weaker/slower processing units, and (ii) higher trans- mission delays for clients with low-quality communication links (e.g., lower available bandwidth or transmit power), among other impacts (Wang et al. 202T). Existing works in centralized FL have addressed these issues by letting the number of local SGD steps between aggregations vary across

---

Published as a conference paper at ICLR 2025
( mod
Vk mod D = 8/ vi mad D - D
A =
1000
dynamic
haterogeneous
local updarte
inter-dlient pommunication
(a) FL with central server
(b) DGD
(c) DFedAvg
(d) RG
(e) DSpodFL (Ours)
Figure I: Illustrations of centralized FL (Fig. la and different consensus-based decentralized optimization algorithms (Figs. [b Te In decentralized gradient descent (DGD, Fig. Tb.. local updates and inter-elient com- munications occur every iteration of training. Fig. [gg[[eddepicss decentralized local SGD, DFedAvg. where communications occur only every D-th iteration. Communication and computation operations are carried out in a deterministic pattern (solid lines, thickness representing relative frequency) in Figs. [b and Ic Random- ized gossip (RG, Fig. [d) adopts sporadic communications for aggregations. DSpodFL in Fig. Tc considers sporadicity in both communications and computations (dashed lines), where the number of local SGDs and the
period of model aggregations are heterogeneous across clients and vary over time.
clients (Marajjyan et al. 2022). and also over training rounds Yang et al. 2022), i.e., to deal with differing and/or varying capabilities while maintaining convergence guarantees.
Motivation and key challenges. In the fully decentralized setting, by contrast, there has not yet been a comprehensive study of how different forms of heterogeneity and dynamics jointly impact the FL performance. Integrating these factors into DFL. makes the analysis challenging because there are multiple client aggregators without a central coordinator which must reach consensus under the following conditions: (i) the aggregation periods across the system become heterogeneous as they depend on the number of local SGDs conducted by each client's neighbors prior to sharing; and (ii) these periods become time-varying depending on dynamics in coammunniiatio//ooppttttti
resource
availability of clients/links. Most existing DFL algorithms (Koloskova et al. 2020; Sun et al. 2022 Mishchenko et al.] 2022) have not taken these factors into account, resulting in longer times to achieve target accuracy in the presence of heterogeneous and vireingrying resources. We thus aim to answer the following key question in this paper:
How can we integrate heterogeneity and dynamics of local SGDs and aggregations into decentral- ized FL to capture the impact of resource availability while maintaining convergence guarantees?
Contributions. We answer this question by developing a generalized algorithmic framework for DFL that allows local model aggregations and transmissions to happen after any arbitrary number of local updates. We refer to this as sporadicity in client participation. which enables capturing the impacts of heterogeneity and dynamics in DFL. Our methodology, Decentralized Sporadic Federated Learning (DSpodFL.), encapsulates the joint effects of (i) sporadicity in local client computations and (ii) sporadicity in inter-client communications arising from resource variations over clients and time. In doing so, DSpodFL captures the impact of different numbers of local SGDs and different aggregation periods across clients, and allows for these values vary over the training process, not constraining them to any prefixed deterministic pattern. We make the following novel contributions:
Sporadic DFL framework capturing resource heterogeneity and dynamics: We formulate DSpodFL. by modeling the occurrences of (i) a local SGD step at each client and (ii) an exchange of models between pair of clients in each training iteration as arbitrary indicator random vari- ables. This enables clients to conduct these processes intermittently according to their available resources without delaying DFL training. As illustrated in Fig. T DSpodFL (Fig. [e subsumes multiple decentralized optimization methods from existing research (Fig. 1b ld which can be
seen as handling special cases of our generalized notion of sporadicity.
Convergence analysis under mild assumptions for convex and non-convex settings: We analyt- ically characterize the convergence behavior of DSpodFL for both strongly-convex and non- convex loss functions, under mild assumptions on the network graph, data heterogeneity, and gradient noises. We conduct our analysis for both constant (Thms. 4. 4.12) and diminishing learning rates (App. G revealing conditions under which zero optimality/stationns achieved. The introduction of sporadicity to DFL makes the analysis challenging, since both local SGDs and model aggregations occur without any predetermined pattern. We show how our results recover the convergence rates of existing DFL algorithms under special cases of sporadicity.
gap can be
2

---

Published as a conference paper at ICLR 2025
Properties of Algorithmic Framework
Assumptions and Theoretical Results
Dynamic
General.
Loose
Last
Convex &
Paper
Fully Decen.
Sporadic SGDs
Sporadie Aggr.
Resource
Data
Graph
Iterates
Non-Convex
Het.
Het
Conn.
Conv.
Analysis
Koloskova el al. (2020)
Maranjyan ct al. 2022)
v
v
Yang ct al. 2022)
Sun et al. 2022
Mishchenko el al. 2022)
Ours
consider more general/milder data heterogeneity assumption based on two parameters and Ç. These assumptions are not restricting the gradient norms a constant bound.
"In Assumptions 4.1 (c) and 4.2 (b)
"In Assumption 4.4 we neither require the underlying network graph to be static, nor B-connected.
"Discussed in Sec. A.5, and Appendix F.4 proof of Theorem 4.11 on convergence of convex models).
Table I: Summary of eight key properties of our paper compared to representative related works.
Experiments in keterogeneous and time-varying DFL. settings: Our numerical experiments demon- strate that DSpodFI. L. reaches target accuracies with significantly smaller delays compared to DFL. baselines. Further, we find that DSpodFLL consistently outperforms the baselines as the degrees of data heterogeneity, resource heterogeneity and dynamics, and the network properties vary.
2 RELATED WORKS
Table summarizes key contributions of our work relative to closely related literature in centralized and decentralized FL. To the best of our knowledge, our work is the first to consider sporadic SGDs and aggregations simultaneously, capturing heterogeneous and time-varying resources in the fully decentralized setting. Below, we discuss related works along DFL's two key processes.
Local SGDs. Several works in centralized FL (Li et al. 2019 Lin et al. 2019; Karimireddy al., 2020 Woodworth et al. 2020: Mishchenko et al. 2022) proposed algorithms with multiple local up- dates between consecutive model aggregations, assuming fixed number of local SGDs across clients. In Maranjyan et al. (2022), an FL. method is proposed where at each round of training, the number of SGD steps differs for each client considering resource heterogeneity. However, the varying number of local SGD steps across clients remains fixed throughout the training process. To alleviate this issue, Anarchic FL was proposed Yang al. (2022); similar our notion of sporadicity, each client chooses when to conduct computationscoommiicc
freely on its own throughout the training process, generalizing all prior work discussed above. Compared these works in centralized FL, we focus on sporadicity in the decentralized setting. This introduces new challenges to our analysis, including dealing with multiple client aggregators and the consensus process among the clients.
A few recent works have also considered decentralized counterparts of fixed local SGD methods (Wang& & Joshi 2018 [un et al.], 2022] Nguyen et al.) [023] Liu et al., a 20224) without considering the heterogeneity and dynamics of client resources. Compared to these works, our focus is on the sporadic case in DFL, modeling heterogeneous number local SGD steps for different clients and allowing them to be time-varying decentralized fixed local SGD as a special case. We will further show in Sec. [ how our convergence results (Thms. 11 4.12) recover DGD--ike methods when there is no sporadicity in SGDs. Finally, we note that our contribution takes the consideration of sporadic SGDs a step further, by analyzing the joint effects of sporadic SGDs and sporadic aggregations in DFL.
well. As result, DSpodFL subsumes prior methods in
Consensus strategies. Sporadicity in communications for distributed consensus formation has been studied in randomized gossip (RG) algorithms. Several works [Boyd et al. (2006); Even et (2021)
Pu & Nedič (202T) study gossip algorithms with two clients conducting consensus at each iteration, while (Koloskova al.) 2019 Kong al.) 202T]] Chen et al., [02T; Zhu et al. [022] allow more general mixing matrices. Saha et al. (2024) further deals with privacy constraints while implement- ing gossip communications. In another direction, [Srivastava
Nedic (20TT); Lian et al. (2018); Bornstein et al.] (2022) have studied asynchronous DFL., where the communication delay between inter-client model exchanges can be modeled as sporadic aggregations. The authors of Koloskova et al. (2020) unify several existing DGD algorithms, under similar generalized data heterogeneity and graph connectivity assumptions that we consider in our analysis. However, none of these works work
in sporadic aggregations have considered sporadic SGDs in their methodology. making among the first to analyze the efficacy of the joint consideration of sporadic SGDs and aggrega- tions. A contemporary of our work Even al. 2024) has also unified several DFL algorithms, but
3

---

Published as a conference paper at ICLR 2025
for the asynchronous setting without consideration for time variations in resource heterogeneity, In this respect, compared to all prior works, our modeling using general indicator random variables (See. (..I. enables us to jointly incorporate heterogeneous and virying resource availability of clients. This approach leads to more generalized results accompanied by new challenges in studying convergence, making both our algorithmic framework and analysis unique.
DECENTRALIZED SPORADIC FEDERATED LEARNING
In this section, we formalize our DSpodFL L algorithmic framework and the notion of sporadicity. A summary of notation used throughout this paper can be found in Appendix A
3.1 DSPODFL: DECENTRALIZED FL WITH SPORADICITY
We consider a DFL system with m clients M := (1,... m) and series of training iterations A: = 1,... K. The clients are connected through a time-varying communication graph ((A) = (()) where (i.j) E (()) if clients and j can directly communicate at iteration k. Define G = EM. as graph such that {A)) C & for all l 2 0. The goal of DFL is for clients to discover the globally optimal model l" arg minggz= F()) for given global loss function F()). To do so, each client i E M updates its own version 0, of the model by (i) conducting SGDs on its local loss (() and (ii) mixing its model with those received from its neighbors. We have
1 Σ F((O), F(0)
F((0)
E (().))
(1)
m
iEM
(x,))ED,
in which Dj is the local dataset of client i E .M, (x, y) denotes a data point with features x and label y. and ((x.u) (6) is the loss incurred by ML model on a data point (x, y).
Goal and motivation. Eq. T is the conventional objective function of FL, which we consider opti- mizing for the decentralized setting under sporadicity. Specifically, we aim for each client to arrive Om 0*. This means that the clients need reach consensus through the local exchange process alongside implementing local SGD (Nedic) 2020). Due to heterogeneity and time variance in immmunication/computaaii resources, we allow for autonomy in the number of SGDs conducted and in the periods between model sharing across client pairs. This will make the process particularly challenging to analyze too.
at 0₁
Algorithmic framework. DSpodFL L achieves the above goal by modeling sporadicity in client par- ticipation for DFL, decoupling the number of SGD iterations conducted by client from the time between model exchanges with its neighbors and the resulting consensus mixing process. Specifi- cally, at each iteration k, client i's update modeled in the following generalized manner:
(k++1) 8(*)
Σ ri (0(h)
g(0))
(k) 13
(N) (k)
g
JEM
Sporadic SGD
Sporadic aggregation
where ((4) is the vector of model parameters of client i at iteration k. and g. (8) VF(( + (
is the local stochastic gradient with SGD noise (k) In Eq. 2 m E [0, is random indicator variable, capturing the sporadicity in SGD iterations, which is 1 if the client performs SGD in that iteration. Similarly, a(h) e (0,
binary random variable capturing the sporadicity in model aggregations, which indicates whether the link (i, being used for communications iteration k or not (6(5) ((h)) and o5.) = 0). Ti E [0, 1] is the mixing weight assigned to link (i, for which the only requirement is that the mixing matrix R [riglicussm is doubly stochastic. For example, with the Metropolis- Hasttigl heuristic (Boyd al. 2004), Tiy = 1/(1 max ([NG). (W5I)) when j E N,. and 0 if j & M, in which N; is the set of neighbors of client i in the physical graph g (M,E). Setting rn = 1 Σyem Ti and noting that rú = Tja i.e., R. being symmetric, completes the design of doubly stochastic mixing matrix R. The full pseudocode of DSpodFL implementing Metropolis- Hastiigss mixing weights is given in Appendix B
The update rule of Eq. with two different sporadicity terms u and 0% each capturing both heterogeneous and varying characteristics, has not been considered the DFI. literature.
4

---

Published as a conference paper at ICLR 2025
3.2 KEY TAKEAWAYS FROM DSPCDFL
Interpreting sporadicity. The novelty of DSpocFL L in the integration of the two sporadicity termss (i.e, of and o/ to model the impacts of resource heterogeneity and dynamics in DFL. Specifi- cally, client may set v(th 0 for computation efficiency in iterations where computing new SGD not feasible or does not significantly benefit the statistical/iffrrncce performance of the decen- tralized system. Similarly, a pair of clients can set 622 = 0 for communication efficiency when using link (i,j) too costly at iteration k relative to local resource availability and/or expected performance impact. These two key parameters w(4) and a can vary arbitrarily over the training process according to decisions made by clients independently over time. This incorporation of spo- radicity increases the degrees of freedom DSpodFL L accounts for, thereby distinguishing it from the literature in Sec. (See Appendix P.2 for further remarks).
Unifying existing work. By introducing these two sporadicity terms, DSpodFL subsumes other decentralized learning algorithms, including those shown in Fig. T Specifically, DSpodFT. reduces to DGD (Fig. lb), DFedAvg (Fig. |c). and RG (Fig. I for specific configurations of ef and - However, these two sporadicity terms introduce several novel challenges when analyzing conver- gence due their creation of uncorrelated aggregation periods in DFL, which address in Sec.
(Fig.le).
3.3 MATRIX FORM OF UPDATES IN DSPODFL
To facilite our convergence analysis, we can rewrite the update rule given in Eq. 2 compactly as
θ (k+1) ( (k) a (z) (+))
where (*) and ((+) are matrices with their rows comprised of (e!*)yT and (g. "0T",, respectively, i m. Here, ( (i) + ((k), where ((()) (respectively, ((+) is the matrix whose i-th row is (VF.(((")))
and (kk is diagonal matrix with wfth) as its diagonal entries, for clients
(respectively, (c. (c) for usiS m. The elements of p(t) = (p()) 12sismm are defined as (k) Pij rig (k),
i
(k) Pij
= =1 E o i=
(k),
(4)
JEM
Note that the random matrix ((k), by definition, doubly stochastic and symmetric with non- negative entries, i.e., p 1 and (P(k))T= -0l))==p())) p(k) Finally, in our analysis, will find it useful define a row vector g(k) the average of model vectors g(h) ...., oft? across clients. Using Eq
g(++1) = g()) (M) gr(().
(ggg(())
(5)
where (B)( -0 (1/m) ΣiEM g
(1) (1)
4
CONVERGENCE ANALYSIS
4.1 DEFINITIONS AND ASSUMPTIONS
Assumption 4.1 (Convex loss functions) For analysis in the strongly conver case, we assume the local loss function F; at each client E M is (a) By-smooth and (b) pu-strongly convex. Also, (c) the gradient diversity is measured via > and 4 2 0 as (() (F)( I 5, + Çi l|0 0- for all 0 E R We define 3 maxie M Bi, μ milliEM Hi. ô maxieM o; and maxie G.
For the non-convex analysis in Sec. 4.5 we will replace Assumptions
&b)& with the following:
Assumption 4.2 (Non-convex loss functions) The local loss function F, at each client i E .M is (a) B.-sthoth. Also, (b) the gradient diversity across clients is measured via 6, > 0 and Ç; 2 0 as || (0)) < 8; Gi G]VVF())) for all 0 E R M. We let B = maxie M Br 8 max ò; and ( maxia Et-
Assumption 4.3 (Random variables) For all E M and all k 2 0. (a) The gradient noise ( of each client is zero mean with bounded variance o? We also let 0² = maxie o?. (b) Gradient noise vectors ! are uncorrelated across the clients, as are the indicator variables v The indi- cator variables of8) are also uncorrelated among the network links. (c) Random variables (k) and
(k) uncorrelated for all clients.
5

---

Published as a conference paper at ICLR 2025
Assumption 4.4 (Asymptotic graph connectivity) Denote the asymptotic graph union of under- lying time-varying communication network graphs by G = (M, limx UK (t)) We assume that 9 is connected, and for every edge (i.j) E G. (i,j) E ((k) for infinitely many iterations k.
More detailed mathematical expositions of our assumptions are provided in Appendix C In Assump- tions
4.22 (b) we do not make the stricter assumption of Ç found in some works on DFL (Sun et al. 2022 Mishchenko et al., (0022. The addition of this proximal term makes our analytical
bounds tighter as they only require a constant bound at optimal/stationary points (Lin et al. 2021). is milder than similar assumptions made in prior works, e.g., static connected graphs Mishchenko al. 2022] Wang & Nedié 2023) or B-connected graphs (Nedic &
Assumption 4.4
(Sun et al.
2022
Ozdaglar 2009).
Table I summarizes this comparison along these and other dimensions.
Definition 4.5 We define {()) as the collection of random variables of", o and for all i E M, [) E e(r), and 0 S r S With this, the expected consensus rate (Koloskova eer al. 2020) can be characterized via p(h) the spectral radius of the expected mixing ma- trix, Egm ((() 11, Eg all ( 6) 11),, which present/prove in Lemma D.4 (c) and Appendix E.4 (c) respectively!
Definition 4.6 (Indicator variables) The expected values of variables (k)
v. and 0. are defined as (2)
B ot dlt)
E
in which d(x) E (0, 1] captures client i's probability of conducting SGD, and (1k) E (0, 1] captures the probability of link (i,j) being used for communication, iteration k. We also define d(t)
maxiem deh) and d minieM d! Note that the probability distributions of these indicator variables can be time-varying, allowing for an arbitrary range of profiles for us and e(6)
4.2
AVERAGE MODEL ERROR AND CONSENSUS ERROR
To characterize the convergence behavior of DSpodFL, we first provide an upper bound on the average model error Ega, []0(++1) 11 (Lemma 4.7 and also upper bound the consensus error
Bg | (k+1)
1,, 0(++1))
[2] (Lemma 4.8). at each iteration
Lemma 4.7 (Average model error) (See Appendix F.1 F. for the proof.) Let Assumptions 4.1 and 4.3 hold. For each iteration & 2 O, we have the following bound on the expected average model error: (b)
Eg (N) [1[0k+1) 8- 9111 S 011 (1t) Eg (1(((())
8* 111 + 01 Eg |||
(k)
1 0(k)
where @11 = 11 20 (1 ua (k) (1)) + 20.(4) (1 (e) (1 d(in))
$12 (1 - (1+1ua (k)) (2) ((4) d² and w/(0) 20 (1 + (1) d(k) )8² + ( o
maj
In Lemma 4.7 the upper bound the expected error iteration I + is expressed in terms of the scaled expected error B [[]((>) 0'111, the scaled consensus error 2 Rgix 1) ())) - 1,, ((k) (which will be analyzed in Lemma 4.8), and the scalar wi all at iteration k. We can see that this bound captures the impact of sporadicity in local SGDs at devices,
through ((k) and (b) It recovers the bound for DGD when (((k) = i.c., making is = 1 for
(k)
all i M (e.g., Lemma 5-b Zchtabi al. (2022)).
Lemma 4.8 (Consensus error) (See Appendix F2 for the proof.) Let Assumptions 4.1 4.3 and 4.4
hold. For each iteration & 2 O, we have the following bound on the expected consensus error:
E
1, 7 a
(M)
Eg
000) 10 + (k)
Fg
[
1, x()) [2 + w2
'Our notation of [gun|o] |o] denotes the full expectation operator with respect to the random variables in matrix _(h), i.c., Rgu-u) [eqoo |=(k))]] = Eeco) [R [-- (..-Fet [Eqoo| [o ( (|( J].
NNot that (k) and o(h) are thus Bernoulli random variables for each k. However, the expectation changes
over time, i.e. varying (*)) and ((4) making (+) and o({) dynamic Bernoulli variables.

---

Published as a conference paper at ICLR 2025
(1-d21))) 22 = m(aaa)) ) d (3 [ 8² + )²), and p(h)) defined Definition 4.5 1-21n
where d2 3 31+
I-pley med (al (5² +22+ (1- (. 22 1+
13 200) d (a (<²
33
Lemma 4.8 captures the impact of sporadicity in model exchanges, through p( (which is smaller when the mixing matrix is better connected), and in SGDs. also shows how gradient diversity
(c, 8) makes the bound larger. It reduces to a bound for DGD when (a) Ç = 0 and (b) ( = 1 (i.e.,
d 1 for all i), in turn forcing (k) 0 (e.g., see Lemma 5-c in Zehtabi et al. 2022)).
4.3 SUFFICIENT CONDITION FOR CONVERGENCE
We observe that the the average model error and consensus error from Lemmas 4.7 and 4.8 are cou- pled. We next characterize their joint evolution and provide condition for DSpodFI convergence.
Definition 4.9 (Error vector) We denote the error vector at iteration k as y(8), defined as the con- catenation of the average model error and the consensus error:
000
B
Bga-n)
E Bga
|0
1m 1m
(6)
Using this definition, it follows that
1k++) I (k)
+ 4 (b)
(7)
with (a) = ( 125 and (1) = (1) 2/ 1 Recursively expanding the inequalities in
(k)
Eq. 7 gives us explicit relationship between the expected model error and consensus error at each iteration, and their initial values, which will be useful in Theorem(4.1.
k
(k+1) < o (1:0)
c (kr) o (r(-1)__ (())
(8)
where we have defined + (k:a) (k) $ (10) for > 8, and (l:kk) ((k), Note that
(0) = [1|0(0) 0- [ - 0(0) pTp.
From Eqs. 7 and 8 can apply linear system theory to identify sufficient condition for conver-
gence of DSpodFLi L: that the spectral radius of matrix (**) is less than one, i.c., p( (k)) 1. In the following proposition, we show this can be enforced through appropriate choice learning rate.
Proposition 4.10 (Spectral radius) (See Appendix F.3 for the proof.) Let Assumptionns 4.1 4.3 and 4.4 hold. If the learning rate satisfies the following condition for all k 2 0:
(k)
min
1-g(() VI BIRR 422+282' 12 +2222
1/3
1- 504
2/3
x 2d max
min
2d
then we have pl (k))
ffror all 2 in which pl-) denotes the spectral radius of a given matrix,
and ((k) is given in Eq. 7 The exact value of p()(()) is given in Appendix F33
Proposition 4.10 implies that limm- & 0 in Eq, which means the consensus and average model errors will converge. The exact convergence rate depends on the choice of learning rate (R)
4.4 MAIN THEOREM AND DISCUSSIONS FOR CONVEX CASE
We characterize the convergence bound of DSpodFL for the convex case in the following theorem.
Theorem 4.11 (Strongly-conver convergence result) (See Appendix for the proof.) Let As- sumptions 4.1 4.3 and 4.4 hold, and suppose constant step size a (R) a >> 0 satisfying the con-
ditions outlined in Proposition 4.10 employed. Let ý maxosksk ((k) be the maximum expected
spectral radius of the mixing probabilities from Definition 4.5 and dmin minogeçk.ieM d.hh) be the minimum of the SGD probabilities. Then, we can rewrile Eq, 8 as
(K-)) < p( K+ (0)
pl + V
(9)
7

---

Published as a conference paper at ICLR 2025
(b(k) from Eq. for r all lo (given the bounds prc)) P. d S 1 and d(h)) 2 dminh, and v(h) the error vector. This means for large enough K, we have
in which v (k) and +
+ poa)) (1 duin)) 8² ad
lim (K+1) S
(10)
K K00
2A
max 3 31 0²)
where A - (T 1o) with lo, 12 that Proposition 4.10 ensures pl ()
being constant scalars defined in Appendix F3
Note
<
Discussion on convergence. The bound in Eq. indicates that by using a constant step size, DSpodFL obtains geometric convergence rate (i.e.. ((p(#)))) as in other DFL methods (Mishchenko et al. 2022, |022, Nedic & Ozdaglar 2209)), Eq. chJaaaccttess the asymptotic optimality gap as op. We observe that this bound holds for any choice of time-varying SGD and ag- gregation probabilities, d!A) and big through 5(A) (see Appendix P.I., respectively. Additionally, the optimality gap is reduced by (1) choosing smaller learning rate a and (ii) having system with larger minimum SGD probability dmnin As discussed after Lemma (.7 in the conventional DFL setting where SGDs occur at every iteration, we have dmii
this setting, the optimality gap in Eq. I0 would be proportional to showing that DSpodFL recovers well-known results of DGD-like algorithms (Maranjyan et al. 2022) this special case of no sporadicity local updates.
Diminishing learning rate. When diminishing step size (k) is used, DSpodFLL achieves zero optimality gap with sub-linear convergence rate OIn K/ /K), matching the rate achieved by existing DGD-based methods (Nedić& & Olshevsky 2014). See Appendix proofs and discussion.
Effects of sporadicity terms. Both p( ()) (from Proposition 1.10) and the first term the optimality gap vector given Eq. 10 can be made smaller by choosing a larger dmnn minlogss K.i. d(t) which will result in a faster convergence rate and lower average model error. Also, the communi- cation probabilities ((()) affect the bounds through the spectral radius parameter ý (exact relationship given Appendix E.4). To elaborate, increasing the frequency of communications will lower the spectral radius term leading to faster convergence and smaller gap for the consensus error. How- ever, this is not always desirable since choosing d, and by solely based on the convergence rate can result in longer iteration lengths, due to susource-limitee clients. As will see in Sec. choosing d, and bıj considering resource availability leads to speedup in achieving performance targets.
4.5 ANALYSIS FOR NON-CONVEX CASE
Our discussion so far has revolved around strongly convex loss functions. For the non-convex case, we follow similar roadmap for our analysis as in Sec. S.2. 4.44 The detailed supporting lemmas and propositions can be found in Appendix Ultimately, we arrive the following theorem:
Theorem 4.12 12( (Non-convex convergence result) (See Appendix H.7 for the proof.) Let Assump- tions 4.2 4.3 3nd 4.4 hold, and suppose a constant learning rate ox (P] -x with > 0 satisfying the
constraints given in Proposition G.6 employed. Let p maxosksK ((8) )) for the spectral radius and dmin minostsk
d())) for the local SGDs. Then,
((
(0( -1. 5 + + a'ugws + Omin )min) ans
< ws a1K+1)
Kil
K1l
in which F* = minGER= F(B) is the globally optimal loss, and wi = 211 Pgg -/- ](1
1
83 (1+Ta) wa (16 o2). ws = T2)82 and ws Adwar Also, the 2m
w2 m(1 m(1-a)(1-f +)
conditions on the constant scalars I; are la, rí P4, and I3 > 0. Letting K + oc, we obtain Eg 1> ( a azwywz + dmin) )w1 + aw'
Er
lim K-
K+1
W1
Discussion. Theorem 4.12 shows that many takeaways from Theorem 4.11 extend to the non-convex
case. Specifically, Theorem 4.12 generalizs results existing DFL works by capturing the effect of sporadicity with non-convex losses. As Theorem 4.11 by setting dmnn minogeg d(4) = 1, work recovers well-known convergence guarantees in DGD when there is sporadicity in SGDs Koloskova et al. (2020) (see Appendix. P..] for further discussion). Additionally, the sta- tionarity gap, which is bounded regardless of the d, values, be reduced by choosing smaller
8

---

Published as a conference paper at ICLR 2025
DFedAvg
DGD
DSpodFL (Ours)
RG
Sporadic SGDs
0.6
0.6
0.5
0.6
0.44
ACCUNNT
0.4
02
0.1
0.0
7500
2000
(a) FMNIST, IID.
(b) FMNIST, Non-IID.
(c) CIFARIO, IID.
(d) CIFARIO. Non-IID.
Figure 2: Accuracy vs. latency plots. DSpodFL, L achieves the target accuracy much faster with less delay,
emphasizing the benefit of sporadicity in DFL. for SGD iterations and model aggregations simultaneously.
learning rate a and/or larger minimum SGD probability dmin- One key difference from Theo- rem i. that Theorem 4.12 provides sub-linear convergence (i.c., O()/K)) of average gradient norms as opposed to geometric convergence of models' last iterates across clients. We also provide analysis for the diminishing learning rate case in Appendix
5 NUMERICAL EVALUATION
Models and datasets. To evaluate our methodology, we consider image classification tasks using the Doshion-MNIST (FMNIST) (Xiao et al.) 2017) and CIFAR1O (Krizhevsky al. 2009) datasets. We use FMNIST to train the Support Vector Machine (SVM) model (Cortes & Vapnik 1995). while CIFARIO is adopted for training VGG11 (Simonyan & Zisserman 2015).
Settings. By default, we consider = 10 clients connected via random geometric graph (RGG) with radius 0.4 (Penrose 2003). We adopt a constant learning rate a = 0.01, and use a batch size of 16. The SGD probability di for each client and exchange probability bij for each link domly chosen according to either the Beta distribution Beta(a, 3). uniform distribution U[0, 1] or b
Bimodal Truncated Gaussian distribution (.5(N)o.11 (1,,, of) +Noo.. (12, oğ)). and are held constant over iterations A. Choosing a B for the Beta distribution results in an inverted bell-shaped distribution, which corresponds to scenarios where the clients and communications links exhibit significant heterogeneity. For FMNIST, we use di b, ~ Beta(0.5, 0.5). and for CIFARIO, we use d,. bij ~ (eta 0.8). We consider two different data distribution scenarios: (i) IID, where each client receives samples from all 10 classes in the dataset, and (ii) non-IID, where each client re- ceives samples from just 1 class for the FMNIST dataset, and from 3 classes for CIFAR 10. Unless stated otherwise, our experiments are done under the non-IID setup. We measure the test accu- racy of each scheme achieved over the average total delay incurred up iteration k. Specifically, (k) (k)
Trotal Ternna + Tproe, in which T/ramx E (1/ING)) Σ, b2)) /b,,)/// (1/I.) Σ, 1/bu) and Tproe = -ii,, oi /d.//L/ 1/d]] are the per-client transmission delays incurred across links and processing delays incurred across clients in iteration k, respectively (see Appendix P.3 for further discussion). For a fair comparison, we determine the aggregation frequency D for the DFedAvg algorithm (depieted in Fig. based these di, i.e., D [(1/m) E.e 1/d.]. We conduct the experiments based on a cluster of three NVIDIA A100 GPUs with 40GB memory. We run the experiments multiple times in each setup, and present the mean and 1-sigma standard deviation.
Baselines. We compare DSpodFL with four baselines that are tailored to decentralized settings: (a) Distributed Gradient Descent (DGD), where SGDs and local aggregations occur every iteration (Nedic & Ozdaglar 2009); (b) the Randomized Gossip (RG) algorithm (Koloskova et al. 2020), which is equivalent Sporadic Aggregations (with constant SGDs); (c) Sporadic SGDs (with con- stant aggregations); and (d) Decentralized Federated Averaging (DFedAvg) (Sun et al. 2022). Note that all these baselines can be viewed as special cases of DSpodFL as elaborated in Fig.
Accuracy vs. delay comparisons. Fig. 2 compares the test accuracies of different schemes in terms of overall delay. By allowing for sporadicity in both SGDs and aggregations, DSpodFL. outperforms all baselines for both data distributions and models/datasets. In the IID setups of Figs. 22 and 2c] the performances of the baselines are reasonably similar. Meanwhile, our DSpodFL is able to significantly outperform those algorithms by an accuracy margin of 10 20% in the initial stages of training. The gain of DSpodFL becomes more significant for non-IID data distributions as shown in Figs. abland 2d Inter-client communications become more crucial in non-III setups, each client has access only to a small portion of the distribution of the whole dataset. Depending on the baseline and dataset, DS is able to achieve 10 40% improvement in accuracy for particular delay.

---

Published as a conference paper at ICLR 2025
DFedAvg
DGD
DSpodFL (Ours)
RG
Sporadic SGDs
0.7
S
Cette 190
MEC wit.eeerr T 500
1 S S
0.4
3.3
0.4
0. 3.8 riduss the RGG
40
0.4
0.6
0.8
numberot book
rumbe of
a-
(a) Varying number of la- (b) Varying the radius of (c) Varying the number of (d) Varying a B in the bels per elient.
random geometric graph. clients m in the network. Beta(a, 3) distribution.
abandd 3e client and link capabilities d. and by are sampled from a uniform distribution 2((0, 1]. The overall results confirm the advantage of DSpodFL.
Figure 3: Effects system parameters on FMNIST. In Figs. 3a 3b
Effects of system parameters. In Fig. 3 we study the accuracy reached by certain training delay
as system parameters are varied. In contrast Fig. 2 where client/link capabilities were sampled are sampled from uniform distribution. In Fig. 3a we see how increasing number of labels possessed by each client (moving from non-IID to IID) improves the achieved accuracy of all methods. Further, DSpodFL, outperforms the baselines for each data distribution. In Fig. (3b] we see that increasing the radius of the underlying RGG (which controls the density of connections) improves the achievable accuracy for all baselines. Again, DSpodFL performs the best for all choices of radii, confirming the benefit of integrating the notion of sporadicity in both communications and computations. Fig. 3c depicts the impact of the number of clients in the system. DSpodFL obtains the largest improvement as the size of the network increases, whereas the baselines are more likely to suffer from resource bottlenecks if weak nodes are added. Finally, in Fig. 3d we analyze the effects of parameters a = B in the Beta distribution, heterogeneity across clients. Note that increasing
from Beta distribution, for completeness, Figs. 3a 3c
which control the communication/comppaaaa these parameters to brings the distribution closer to uniform. We see that DSpodFL is robust to the underlying resource distribution, and the gap between our approach and other baselines become more significant when levels of heterogeneity in client/link resources are higher, i.e., lower a B.
Generalization of results to various settings. In Fig. E we provide experimental results where some of the default system parameters that were used for Figs. 2 and 3 are changed. In Fig. 4a a total of 50 clients are considered for the decentralized system. The results illus- trate that the improvements become more pro- nounced with m 50, confirming the trend seen with increasing m in Fig. Ba] In Fig. [4b] Bimodal Truncated Gaussian distribution is used to generate probabilities de and bij. which for small values of variance when the means of the two modes are far from each other, gives heterogeneous clients. We see that when vary- ing /4, wider margin of improvement (15%) with lower where u4 = μl and μ12 1- μa is achieved. This confirms that DSpodFL is most advantageous relative to the baselines under higher levels of heterogeneity, similar to how the improvements under the inverted bell-shaped Beta distribution were more pronounced than those under the uniform distribution Fig. 3d
U.S
0.4
00
(a) Varying number of (b) Varying # in d,, bij bels per client in network 0.5(NN 0.01) of m 50 clients.
No..j pc, 0.01)).
Figure 4: Scalability larger clients and robustness against distributions on FMNIST.
Additional results. In Appendix O we report experimental results when time-varying SGD and aggregation probabilities are used, as well as under other configurations of resource heterogeneity.
6 CONCLUSION AND LIMITATIONS
We proposed DSpodFI, a DFL algorithmic framework that generalizes the notion of sporadicity to fully decentralized scenarios. By considering (i) sporadic gradient computations and (ii) sporadic client-to-client communications simultaneously, our approach tackles the challenges in heteroge- neous and time-varying resource settings and subsumes well-known decentralized optimization al- gorithms. We analyzed the convergence behavior DSpodFL, and showed how our results recover existing DGDelike algorithms under special cases of sporadicity. Through experiments, we demon- strated the advantage of DSpodPL compared to DFL baselines. Future work could consider further validating DSpodFI, on larger datasets and more expansive set of tasks beyond image elassification.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported part by the National Science Foundation (NSF) under grants CNS- 2146171 and CPS-2313109, the Office of Naval Research (ONR) under grant N00014-22-1-2005, and the Air Force Office of Scientific Research (AFOSR) under grant FA9550-24-110088.
REPRODUCIBILITY STATEMENT
We use open-source datasets detailed in 5 Complete code for training and testing is available in the supplementary material. Pseudo-code of our algorithm is given in Appendix The assump- tions for our theoretical results are outlined in Sec. Sec. and the proofs of our Lemmas, Propositions and Theorems (Sees. 4.2 4.5) are given in Appendices H
REFERENCES
Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp. Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečný, Stefano Mazzocchi, Brendan McMahan, et al. Towards federated learning scale: System design. Proceedings of machine learning and systems, 1: 374-388, 2019.
Marco Bornstein, Tahseen Rabbani, Evan Z Wang. Amrit Bedi, and Furong Huang. Swift: Rapid de- centralized federated learning via wait-free model communication. In The Eleventh International Conference on Learning Representations, 2022.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, (0(2):223-311, 2018.
Stephen Boyd, Persi Diaconis, and Lin Xiao. Fastest mixing markov chain on a graph. SIAM review, 46(4):667-689 2004.
Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE transactions on information theory, 52(6):2508-2553 -5300, 2006.
Christopher G Brinton, Mung Chiang, Kwang Taik Kim, David J Love, Michael Beesley, Morris Repeta, John Roese, Per Beming, Erik Ekudden, Clara Li, et al. Key focus areas and enabling technologies for 6g. arXiv preprint arXiv:2412.070299 2024.
Yiming Chen, Kun Yuan, Yingya Zhang, Pan Pan, Yinghui Xu, and Wotao Yin. Accelerating gossip sgd with periodic global averaging. In International Conference on Machine Learning, pp. 1791- 1802. PMLR, 2021.
Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20(3)2273-277, 1995.
Mathieu Even, Raphaël Berthier, Francis Bach, Nicolas Flammarion, Pierre Gaillard, Hadrien Hen- drikx. Laurent Massoulié, and Adrien Taylor. continuized view on nesterov acceleration for stochastic gradient descent and randomized gossip. In Advances in Neural Information Process- ing Systems, pp. 1-32, 2021.
Mathieu Even, Anastasia Koloskova, and Laurent Massoulié, Asynchronous sgd on graphs: a unified framework for asynchronous decentralized and federated optimization. In International Confer- ence on Artificial Intelligence and Statistics, pp. 64-72. PMLR, 2024.
Yan Huang, Ying Sun, Zehan Zhu, Changzhi Yan, and Jinming Xu. Tackling data heterogeneity: A new unified framework for decentralized sgd with sample-induced topology. In International PMLR, 2022.
Conference on Machine Learning, pp.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International conference machine learning, pp. 5132-5143. PMLR, 2020.

---

Published as a conference paper at ICLR 2025
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Confer- on Machine Learning, pp. 5381-5393. PMLR, 2020.
Anastasiia Koloskova, Tao Lin, Sebastian Urban Stich, and Martin Jaggi. Decentralized deep learn- ing with arbitrary communication compression. In Proceedings of the 8th International Confer- ence on Learning Representations, number CONF, 2019.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arKiv: 2016.
Lingjing Kong, Tao Lin, Anastasia Koloskova, Martin Jaggi, and Sebastian Stich. Consensus control for decentralized deep learning. In International Conference Machine Learning, pp. 5686- 5696. PMLR, 2021.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Tian Li. Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE signal processing magazine, 37(3):50-60, 2020.
Xiang Li, Wenhao Yang, Shusen Wang, and Zhihua Zhang. Communication-efficieni local decen- tralized sgd methods. arXiv preprint arXiv:1910.09 09166 2019.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized study for decentralized parallel stochastic
algorithms outperform centralized algorithms? gradient descent. Advances in neural information processing systems, 30, 2017.
Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In International Conference on Machine Learning, pp. 3043-3052. PMLR, 2018.
Frank Po-Chen Lin, Seyyedali Hosseinalipour, Sheikh Shams Azam, Christopher G Brinton, and Nicolo Michelusi. Semi-decentralized federated learning with cooperative d2d local model ag- gregations. IEEE Journal on Selected Areas in Communications, 39(12)3851-3366 2021.
Tao Lin, Sebastian Urban Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini- batches, use local sgd. In Proceedings of the 8th International Conference on Learning Repre- sentations, 2019.
Yue Liu, Tao Lin, Anastasia Koloskova, and Sebastian U Stich. Decentralized gradient tracking with local steps. Optimization Methods and Software, pp. 1-28, 2024.
Artavazd Maranjyan, Mher Safaryan, and Peter Richtárik. Gradskip: Communication-accell accelerated local gradient methods with better computational complexity. arXiv preprint urXiv:22 16402, 2022.
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally! In International Con- ference Machine Learning, pp. 15750-15769. PMLR, 2022.
Angelia Nedic. Distributed gradient methods for convex machine learning problems in networks: Distributed optimization. IEEE Signal Processing Magazine, 37(3):92-101, 2020.
Angelia Nedić and Alex Olshevsky. Distributed optimization over time-varying directed graphs. IEEE Transactions on Automatic Control, 60(3))601-615 2014.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimiza- tion. IEEE Transactions Automatic Control, 54(1):48-61, 2009.
Angelia Nedić, Alex Olshevsky, and Michael G Rabbat. Network topology and communication- computation tradeoffs in decentralized optimization. Proceedings of the IEEE, 106(5):953-99 976, 2018.
12

---

Published as a conference paper at ICLR 2025
Edward Due Hien Nguyen, Sulaiman A Alghunaim, Kun Yuan, and César A Uribe. On the perfor- mance of gradient tracking with local updates. In 2023 62nd IEEE Conference on Decision and Control (CDC), pp. 13099-4312 IEEE, 2023.
Mathew Penrose. Random geometric graphs, volume 5. OUP Oxford, 2003.
Shi Pu and Angelia Nedić. Distributed stochastic gradient tracking methods. Mathematical Pro- gramming, 187:409-557 2021.
Guannan Qu and Na Li. Harnessing smoothness to accelerate distributed optimization. IEEE Trans-
actions on Control of Network Systems, 5(3):1245-1260, 2017.
Rajarshi Saha, Mohamed Seif, Michal Yemini, Andrea J. Goldsmith, and H. Vincent Poor. Privacy intermittentllycooneeeed networks. IEEE
preserving semi-decentralized mean estimation
Transactions on Signal Processing, pp. 1-14, 2024. doi: 10.1109/TSP:202444479999.
K. Simonyan and A Zisserman. Very deep convolutional networks for large-scale image recognition. In 3rd International Conference on Learning Representations (ICLR 2015). Computational and Biological Learning Society, 2015.
Kunal Srivastava and Angelia Nedic. Distributed asynchronous constrained stochastic optimization.
IEEE journal of selected topics in signal processing. 5(4):772-790, 2011.
Tao Sun, Dongsheng Li, and Bao Wang. Decentralized federated averaging. IEEE Transactions on Pattern Analysis and Machine Intelligence, 428443428, 2022.
Sundhar Ram, Angelia Nedić, and Venugopal V Veeravalli. Distributed stochastic subgradient projection algorithms for convex optimization. Journal of optimization theory and applications, 147:516-545, 2010.
Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of communication-effiienn sgd algorithms. arXiv preprint arXiv: 1aoe::888.07555 07576, 2018.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. A novel framework for the analysis and design of heterogencous federated learning. IEEE Transactions on Signal Processing, 69:5234-5244 5249, 2021.
Yongqiang Wang and Angelia Nedié. Decentralized gradient methods with time-varying uncoor- dinated stepsizes: Convergence analysis and privacy design. IEEE Transactions Automutic Control, 2023.
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcma- han, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pp. 10334-10343. PMLR, 2020.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mniss a novel image dataset for benchmark- ing machine learning algorithms, 2017.
Ran Xin, Usman A Khan, and Soummya Kar. An improved convergence analysis for decentralized online stochastic non-convex optimization. IEEE Transactions Signal Processing, 69:1844 1842- 1858, 2021.
Haibo Yang, Xin Zhang, Prashant Khanduri, and Jia Liu. Anarchic federated learning. Interna- tional Conference on Machine Learning, pp.
PMLR, 2022.
Shahryar Zehtabi, Seyyedali Hosseinalipour, and Christopher G Brinton. Event- weent-triggere decentral- ized federated learning over resource-constrained edge devices. arXiv preprint arXiv:2211.1266 2022.
Tongtian Zhu, Fengxiang He, Lan Zhang, Zhengyang Niu, Mingli Song, and Dacheng Tao. Topology-awe -wware generalization of decentralized sgd. In International Conference Machine Learning, pp. 27479-27503. PMLR, 2022.
13

---

Published as a conference paper at ICLR 2025
A NOTATION
Arguments for functions are denoted with parentheses, c.g. f(r) implies x is an argument for function f- The iteration index for a parameter is indicated via superseripts, e.g., (A)) is the value of the parameter ht at iteration k. client indices are given via subscripts, e.g., h/ refers parameter belonging to client i. We write graph 9 with a set of nodes (clients) V and a set of edges (links) 3 9 = (V,E).
We denote vectors with lowercase boldface, e.g., x, and matrices with uppercase boldface, e.g., All vectors Rdx1 column vectors, except in certain cases where average vectors x E IRixd and optimal vectors w E 1x are row vectors. (x, x') and (X, X') denote the inner product of two vectors x, x' of equal dimensions and the Frobenius inner product of two matrices X, X' of equal dimensions, respectively, Moreover, ||x|] and |X|] denote the 2-norm of the vector x, and the Frobenius norm of the matrix X, respectively. The spectral norm of the matrix X written as pXX).
B ALGORITHM PSEUDOCODE
Algorithm Decentralized Sporadic Federated Learning (DSpodFL)
1: Input: K, {g = (M,,
(u/-0 heM.DsKK to
2: Output: (0(K+1)) DiEM
3: & + O. Initialize 010), 10!0) t 3.em 10,1) -0)em 10g +) -
4: while k: S K do
5: for all E M
6: 9: +- 0, aggr; 0
(k)
7:
then
8:
sample bicc- <!
D;
g. (k) + VE(0 (k)
9:
end if
11:
for all
j E E!tt do
if
yy then
(k)
Ti - 11(1 max (WW (g(
aggr (k) + aggr (k)
+ rij (0) 0,4))
15:
end if
16:
end for
17:
end for
18:
for all i
EM do 0 glx+1)) g%
+ aggr (k)
(k)) (k)
19:
20:
end for
21: A: ++1
22:
end while
C ASSUMPTION STATEMENTS
In this section, we state the mathematical inequalities that follow from the assumptions made in Sec. 4.1 which are used in our subsequent Lemmas and Propositions.
Assumption
a
B,-smoothness:
- 3,, 0'1 S 3 8'||.
b
s,rStn convexity: (VF)(0) VE((0') 0²) 2 m:|0 0' > m|| 0'1
c
o,, G-gradient diversity: [VF VF((0)] < 6, 0 0*1 8 + ( [|0 0-
14

---

Published as a conference paper at ICLR 2025
for all (8',0) E I" x R" and all i M, where μ min 14, B m. Pi.
8 = max,eM d and Ç = maxieM Çt-
Note that these measures are related to each other via the inequalities S < 8 < B 0 S < 3, and - < S 23 (see Appendix E.Ip. We will also find the relationship F(0)= - F(0) (VF()'), 8 8*) "1o' 012 useful in our treatment of smoothness.
Assumption 4.2
Note that is possible make this assumption even for convex models instead of Assump- tion 4.1 c
since smoothness implies that V < 0110 0*] || However, we choose to
use Assumption 4.1 instead of Assumption 4.2 (b) for convex models, since a less strict assumption.
Assumption
Zero mean and bounded variance of stochastic gradient noise: E (2 [e O,
a
[|
E
(k)
[2] S of o²
where o² maxieM of. for all i E M and all 2 O.
(k) Let us define SGD noise vectors 6 and ey indicator variables us and o and
(b)
f. and ul.g Then for all + j. and (#, # (1, we have:
E Egg [(e (8) o0 [1))] (E
(N) B. L (efx))), Ega [ot (w) = E
E g Iu! 1 BBgeo Loggolyy (1f
E
Egto
(a(k) [(0)
1. Lg = Bgg 2
( Beas u = =E 1 B (o
Assumption 4.4
This assumption implies that if ((k)
lsajsm and R = [rysl as defined in Eqs. 4 l are the doubly- doubly-stochastic mixing matrices assigned to ((k) and g, respectively,
Ip (8)
we have
(k) e (A) 1,,00 ;(0) || | - 1,, 0()) 1
Re(k) (k) I, 11 S s 1 (b) 1,,, o(k) ||?
with pr 1, where pr denotes the spectral radius of the matrix R
m 1m 1
C.I GRADIENT DIVERSITY ASSUMPTIONS CONVEX AND NON-CONVEX MODELS
In this section, we will discuss why we change the gradient diversity assumption when we treat non-convex models, i.e., move from Assumption 4.1 (c) Assumption (b2
We note that if we are dealing with strongly-conver models, i.e., we make Assumption 4.1
for u-strongly convex models, the inequality in Assumption (b) for data heterogeneity
much stronger assumption than Assumption 4.
(c) To show this, we first note that making the
3-smoothness assumption (made in both Assumptions 4.1 (a) and 4.2 a) implies that
[[)]] s 3||e 0*11,
where 8* is point where VF(#*) = 0, i.e., a globally optimal point for convex models and stationary point for non-convex models (note that we present and prove this result in Lemma D.I
(b)). Then, since we have [[)], & 8, + ((O]] according to Assumption 4.2 conclude that
(b) we can
[[VF VFL(I) < ||F
(VF))) (VE (0)
+1+
S <6 + +) 0*
We observe that defining & = 6, and C = (1 (1+ (1+ G)B > O, Assumption 4.1 (c) is implied with
parameters 8/ and C. The converse necessarily true though, i.e., Assumption 4. does
imply Assumption 4.2 (b)
D INTERMEDIARY LEMMAS
Lemma D.1 (Gradient bounds) (See Appendix E.1 for the proof.) Let Assumption 4.1 hold. We
have
15

---

Published as a conference paper at ICLR 2025
(a) The global loss function F(0) is 3-smooth and p-strongly convex. i.e.
[VV - V (6)) = B 10 - 0'1,, (VF(() - ul10 011
(b) The gradients of the global and local loss functions, and the gradieni of the local loss function at the optimal point are bounded as
|VF(()] S 3/10 0011, |[VE;(0)) S 25 -0) []V S 6,.
02).
Part-(ar (a) Lemma D.1 outlines the smoothness and convexity behaviour of the global loss function based on the measures of local loss functions, and part providde upper bounds on the gradients. Note how these show that we are not making the bounded gradients assumption for all R", but only bounded local gradients at the globally optimal point 0*
Next, we provide upper bounds on the expected Frobenius norms of the following quantities related to SGD noises.
Lemma D.2 (Expected value SGD noise average and deviation) (See Appendix E.2 for the proof.) Let Assumption 44.3 hold. For every iteration k 2 O, the average SGD noise and their deviation from this average can bounded as
Egg0
<
(R) max
12 //m,
Eg(an
1 - 1mE
S mdd (k)
o²
in which (
-h D
(K) (N)
E
U/S
Note that by setting dndx in D.2 we get back the well-known estimation bounds for these quantities (e.g., see Lemma in Pu & Nedič (202I)).
Next, we find an upper bound on the expected deviation of the gradients from their average (similar the second quantity in Lemma D.2).
Lemma D.3 (Gradient deviation bound) (See Appendix E.3 for the proof.) Let Assumption 4.1
hold. For euch iteration k 0, we have the following bound on the expected error of gradients from their average
Egm
1m Vo Vo -
< max
(d(k)
mā² + (52 ( +28²) Eza-n
|00(0)
1 mm 00h) 12
+ m (5² + 20² (1 (1-dml)) Bzn || ||ow0) - -011()
which (k) is matrix whose rows are comprised of gradient vectors (F(( and (1) (k)
1. Em (F((O())) )u
Finally, we analyze the behaviour of the random mixing matrix p(k) defined in Eqs. and
Lemma D.4 (Expected mixing matrix) (See Appendix E.4 for the proof.) Let Assumption 4.4 hold. For each iteration 2 we have
(a) The expected mixing matrix, denoted as R Rk), is irreducible and doubly-stochastic: Ev [P] e (A)
[[((0]
(N)
(K)
0/3 Tij
(k)
i i j
Isijsm"
1 Σm
j=1 sj
(k)
Tij
i i= j
(b) Eva (P(()) (R (+)² + R (A),
where R (1) is a matrix whose rows and columns sum to zero. Thus, R (k) will be irreducible and doubly-stochastic.
16

---

Published as a conference paper at ICLR 2025
(c) Ega || ( - 11m S Eg [|0 1m 0245 ||]
in which g(k) is the spectral radius of the matrix R(A).
1 1 17
E PROOFS OF INTERMEDIARY LEMMAS
E. PROOF OF LEMMA D.I
a
First, we use Eq. 1
triangle inequality and the smoothness property given in Assumption 4.1
to get
-
=
1
Σ (V)((0) - VF3(O))
(V) VF
m
j=1
m m
B, 18
0'1 B1e
0'l S 3 | l'll
Next, using Eq. 1 and the strong convexity property of Assumption 4.1 (b)
we have
(VF(0)- - VF(0), = 1 Σ (Fz(0) - VF,(0'), - 0¹)
psll
0'12
m j=1
5-1
= 0 0' 1² 2 p/00 0'112.
bb) Since V0((0) = 0 by definition, we can use the results of part (a) of this lemma to show that
|F) || s 3 110 1'
Once again noting that VF())) 0, we next use the gradient diversity bound outlined in Assump- tion to get
|E( 5,
(11)
Finally, using Eq. and Assumption 4.1 (a)
we write
|| < - + $2 22 0-1 + +6?)
finishing the proof.
To explain the statement written after Assumption 4.1 on how these measures relate to each other, we first have
# p4
<
8 < 3,
which μ4 S B, is a well-known fact (see Bottou et al. 3, < B follow from the definitions given in Assumption 4.1 Moreover, if we upper-bound the we will have
(2018) as a reference), and μ S μa and
gradient diversity term [[V - (())) without using Assumption 4.1 (c)
[VF((0) - F < (F - V - VFF()))))))
(( -FF < 6, + 8, | - 8 | 8, + (B + B) ||e 1*
<
(12)
in which we used the triangle inequality, Assumption 4. aa) and the results of Lemma (b) Now comparing Eq. 12 with the assumption made in 4.1 (c) for the same expression, conclude that
S Br +
< 233
17

---

Published as a conference paper at ICLR 2025
E.2 PROOF OF LEMMA D.2
We start by finding upper bound for the average SGD noise, by expanding the terms using their definitions and employing the properties given in Assumption 4.3 and Definition 4.6
Eg(u)
cook)
||
=
Eg(N)
U
E
Eg(
m
m
(8)
m
im
1=1
172
E (k)
(1)
1/3
(8)
2
172
(k) (1)
E (k)
Ej {5
(R)
771 2
772 2
(4)
m
E
(R)
1=1
m
m
(K)
(R)
(1)
m
2
E 2/
1/3
E
2)
(2)
E (i0
j=1
m
(k)
(K)
1
(k)
d
m
E
(1)
EE
(4)
m²
m
Next, we found an upper bound for deviance of the enror matrix from its average, using simi- is the Frobenius norm for matrices, Assumption 4.3 and
lar approach as above. Noting that || Definition implies that
Eq(s)
v ((A)
1mm 1
Eg(())
V (A6) E(A)
- ( (1)))((
ImE + 1. (
2
(k) EO(H) ) + Becs m (T() 27
Eq(x)
c 2
(k) (R)
glg (
2E
(k) 0.
E (()
(A:)
(k))
E
1=1
2
E.
(k)
E (1)
(8)
[000 )
+ mlgg
|
1=1
1=1
1
m
(k) 1
1
E (k)
IE (1)
77
m7
2
(K)
(1)
(k)
(1)
E (4)
E
000
1/
E
(4)
E
(k)
m7
1=1
8+1
m
0
< (m-
1) (k)
0²
<
mdl
E.3 PROOF OF LEMMA D.3
Noting that
(k) (A)
1m Ve 10
2 _
v + v ((()))))
1m Vo (A)
18

---

Published as a conference paper at ICLR 2025
according to Young's inequality, we first find an upper bound for each of the two terms above is the Frobenius norm for matrices, we have
separately. For the first term, noting that ||
|(N)p())) v(A) Ve
// (R)
VF
000h) v/
(10)
VF, ( VF (0! ||? (A)
vF(
= Σ
og + Si [8(+0) - 8+ 1) 2 (K)
i=1
(6. + 54 ( - glk) || + Si g(a) 001) og
[=1
S
83 + <? (05)) - g000) Σ
m
2 + < ||
0+
(0)) c.
where Assumption 4.1 (c) triangle inequality and Young's 's inequality were used for the inequalities, is the Frobenius norm for matrices, using
respectively. For the second term, again noting that || || Eq. and the triangle inequality, we can write
(k) ( - 1m Vu
1
m
(k)
(K) 1/3
Ve
(6)
m
m72
VF, (o)))) ((1))
m j=1
1 vF ( 1 p
VF,
Continuing from there and using Young's s incquality and Assumption 4.1 (a)
we have
VF, 0 of VF, (((K)
21!4) + VF, (0(A)
b(()) V (O (
bofool' VEE ( - -V vE0 )|² (())) + VFg (0l+) vEJ(OT) (P!! )
)o(())) - VAF
(B((B))) (/ + VF, (0(k) ) VFy (0)
m m
m
j=1
+ 343 (01i) - (1)(()) (0f5)) )|²
| (/45)
3
8361 (ii 8655 || m000) + |3 Φ(h) 0t1? (1.h) + + -20 o(a)))
m
+ |3 ((A) 0 (22.10)
3
|1!900 - 0100|/ (,60 + |0()) 0. || ( (u,4)) + (m 2n (10 (k)
m
1=1
1=1
g(() | ((m))
3
m
(((h))
g(a)
(k)
m
g(()
0 og
<<
m
+
m
m
+
(o(N)
0-11?
m
+
m
(8)
2
y (R)
1=1
1=1
1=1
1=1
19

---

Published as a conference paper at ICLR 2025
S 6,39)
Σ
m
((4)) g(k) 12 ( +692 000 - 0- 1
Σ
m
(4)
Σ
m
(1)
m
< 6,3
m7
(0!*) - 0/01 + +|0000 -011²
1 |
m
(k)
(8)
Vi
m
where for the last three inequalities used the properties of the binary indicator random variables E {0, 13. Now, by combining the two components together we get
(b)
(1)
1m Vo (K)
=2 ((0 - v( ( 2 + 2 (()) 1m V 1
8 + (c + 2 |!!0) - - ||
< 6
i=1
(1) )) pow) 0r
+
2 +282
1 - Σ
0
Finally, we have to take the expected value of the above inequality to conclude the proof. Towards this, we multiply uf inside the parentheses and use Definition 4.6 to get
1m Vu 19
(k) (k)
$ 6
m
o7 + (s? + 2,52)
|10000 @(x) (²)
B Beges ( [u]+] + (2 [rf") [n]]0]]
1=1
+2,82
E (1)
0,
(R)
1
E
[
E
(M)
Σ
m
B
(o8911)
m
m
jml
|1004] - 0-1]]]
Eg(x-1) 1)
10000 - ouh) -0400 (²])
Σ
03 +
(c² + 223
Ega-11
d5t)) + C2dt (8)
+28²
d(())
1
(k)
d
((
E Eg(e..)
|ow - 0+ &112
m
1
s
6
(b)
82 + (G2 + 2,82)
Bgtk
||0000 g 8/001p9]
1=1
1- 1 + Σ (16) 1)) B
[1ow ( 0- 0-1]]]
+ G + 2,3
==1
[ - 1 060 [|]
< <6d(A) max
md² + (s2 + +282) Eg
+m (<+ (2+283 282 (1 (1- 1 + (m - 1 1e( 1) Ean-n |000)-001(
0-
20

---

Published as a conference paper at ICLR 2025
[0(h) m [(k) |3]
= (d(t)
md² + (5² + 2,82) Rg
+ m <² + 2,22
(1-
1 m
(1
min
Bg(--
|| [(C)) 1-11]
|0 m ((x) |9]
S Gd
ma² + (5² + +2,32) Eg(t-1)
(5² + 2,3²
(1-d d (k
| 0-
1011]
+
where the last four lines are algebraic manipulations to simplify the bound.
E.4 PROOF OF LEMMA D.4
(a) We take the expected value of the matrix ((k) by looking at its individual elements. Using Eq.
and Definition 4.6 we have
Fiy B
(1)
i
# j
E
V
[A)]
E
(1))
Pio
(8)
I5issm
Σラ= riy
1si
mm
(R)
i=
15ism
oi Téj
i i
sm
R
i=j j
15ism
Similar the proof of the previous part, take the expected value of (P(K)TTP() (P(k) by looking at its individual elements. Again, using Eq. 4nnd Definition 4.6 Assumption 4.3 implies that
(b)
if é *
j
m
Σ 1=1
(k)
(k) Pij
E E000
= BBa
(2)(())) rarty 01 Uij
(k)
+ -11-
m Σ
Fig
ri + -11
(A)
m 2
rig
ri r (1)
9=1
BBaa)
(1) (K) Tarty a Vig
+
2 -
Σ
0/ + 0/1
Tay Teg
9=1
m
m Σ
E
Σ
(R) Tu 02
+
rig
(1)) 14
+ +r (roao(1))
g=l aptin
(reg (k)
+ +rra (K))
reg rest
Σ
rarly
E
(0)
(k)
E
(6)
1=1
+
2 -
Σ
riq
o/g
[5(0]]
0/
+ rgg
E
(00
(000))
ray (00)
-2r
E (/
[600
q=1
21

---

Published as a conference paper at ICLR 2025
m d
m
(1) rub
Σ
((0) iq
rig +b// r33))
b rey
26/5) rtj
rij
+
1=1
q=1
On the other hand,
i
j:
m
m
m
Σ
Pit Pig
(k)
(k)
E
Tanuo a
(k) (1)) 1/
+
1
rig (kk)
g=1
m
m +
= =Bom
2 (k)
11
+ 1 2
Σ
Tig in
(8) (000)
1=1
g=1
m Σ
Bvw
21
2 (k)
+ 1 -
Fag vig
(A)
Fig aa Dig
(R) (R)
Us
39 1/g
q=1
m
Σ
(M)
(k) 51
+1 1 2
Fig (())
E
3g
(R)
Nag Fig
E
(A)
24
E 6/0
(K)
1=1
1
(1:) 2
(k)
(k) (1:)
11
12
+
-
Dig Tig
3g
Vig Dig
it
Pit
1=1
Finally, comparing the above expression with the elements of (R()))? we get
E Exa
(p(t))
27 =
Bo(
Σ
Pal
(k) Pii
1=1
1si.sm
26 (k)
(1
2
i
(k)
(R(4) 2 + +R,
(k) & R(
+
m -
2b (1 Dt
i i=
I5ism
which R (k) matrix whose rows and columns sum to zero
c In order to prove this inequality, we expand the left-hand side Frobenius norm by its columns and use the results of part of this lemma. We have
| 1 (
1, 1m0 ||]
Σ
p
1 1m ||
Ega
p (()) 0.²0 p(k) mm |
E Σ ((K)) (0.00 - -0,00 mm
Eg(
0 0/hh 1mm) (pps)) "pa)) (0ga)) 0f+ 1mm)
E Eg(h)
E Ego 1)
(A) - g(h) 1m
Bepas ((())((ss] (0 - ( 1m
E)
((()) g(k) 1m
T
R
(M) (0(A)) 06h11 1mm)
22

---

Published as a conference paper at ICLR 2025
S
Σ
m
00000
0/40
1m
|
S Bga-1
- 1 1
|lou)
Note how we used the double stochasticity of P(k) in the second line.
F PROOFS OF MAIN RESULTS
F.1 PROOF OF LEMMA
Using Lemma D.1 b) on 0(k), the average model parameters at iteration k. we get
VF. (th) )1
s (22||00))
1|² + 6?
8-
(13)
Now, 0f0 < ak) S at3. we can write
[1ktz) - 001p² = ((K) (())
g (k) 8+) 1
= =1(0(0) aa(1) Vo (K) 0r 2
-2 (0(t) a (1) Vv
(k)
0-, "0 (o(t)) + (aa4t) 2
/col
$ (1 + (ta (86)) (k) VF (F((((() (B()))
8-1
1 (1
(a(4)) 2
Σ F: (
VF. (0.4)) o
uarl))
m
2 (BL+) v (A)
0 a (1) colk)
+ (a(3s) 2 (2) 1
<(1 +1+ +
( (1 ) ) 91100 | -
2 + my
(k))
(1+ (1)
33 g(a) (
(k)
(1 (1+ (a))
Σ
82 g(t) - 001| + 82
+ m4
=0
2 200() - (a Vr
0" a (
) + (alat) 2
) (
= -[1++ (t) (1-pa("))
2 (a(
(1+
Σ 83 (1-2/% -0f
[0(c] 8r 2
my
1=1
(1))
(1 + (a) (k)
Σ
37 (o( - -(t) / w1!0)
(A)
I + ua))))
Σ 0² (1- (1- (1)
m/
mp
1=1
1=1
2 (B0)) a vo -a(
(k)
0+ a (
+ (a)t)) 2 (k))k)
2
in which the relationship in first four lines follow from ii Eq. 5 (ii) g
v (k)
for all
i E M, (iii) Young's inequality, (iv) Lemma 10 in Qu & Li (011 7). Assumption
4.1
(a) and Eq 13
Next, we take the expected value of the above inequality and use Definition 4.6, Assumption and
Lemma D.2 to get
|oc++)) -
< Brcss (1 +
(1- m
Eg (t)
+ (h)
(1+ ualli) Σd
B2 (1 (1- -,())
Egu-n | g- 27
mfe
23

---

Published as a conference paper at ICLR 2025
(1 + )))l
Σ
m
8 R 1(( 11
||0.5) 0 1|]
2
R (gg u [
mys
+ my
(k)
(1+ paa
E %/
[1 - r
1=1
2ggu Dumen (0L6) ((() Vo (8) 00 (a()
Bpu ( + (alet) 2 "Bges
)
| ||]
(1 + (1+mactt) (1-waelt) 2 +
(x(())
(1 wo(l))
Σ
132 (1 - 1 g(t1)
my
i=1
|| (0l5) - 0-1 0010]
Bg
+ (1k))
m (1 + woa)))
Egu ||000) -g(A) 19)
Σ
mf
2=1
(k(
+ (ale)) ? dittooo
(1+ (c)(h)
Σ
8 (1 (1- -.(tt)
+ my
m
1=1
2Ega ((00)) (x) Vo (N)
0,, a Eg( | + (al Egcs) ( |1? [2
1 mk)
(1=natth - (ma)())) (1 )²)
(a(a))
(1 + ))al))
(1-dff d 322
1
E Ega 1) [ - 001("]
+ (1 + =allt) (k)
d 32
E Eg -
- 1m 1mm 3160119
mp
+ 2x(A))
(alt)) 2 doliooo
(1+ palti) (1
d min)
8² +
a
m
F.2 PROOF OF LEMMA 4.8
Using Eqs.
3 and
we first expand the left-hand side norm, and then use Young's inequality to get
0 (1+1) 1m g(0++)) 2 |p(ti (N) - 0()) - (1)) (v 1m ||
< (())
(A)) 1()))) - ax) (V(K) 1m (o))) 1
(k( (p(() 1m)))) al()) (Vir)pr(A) 1m V (t). v(()p(()) 1m)
(astt) V((6) (({) Immo(A)] |
1+ 1- p(()
- - 1 |?
2
(14)
+ (1+ 2g(k)
1 pins] ) (art)) //| | 1m Ve 1/11
(k) (p(k)
- -1 - (k)
(vi - 1m Vor ").
Im - 1m 1mm v(()
m
+(a10)) v
1m Em
24

---

Published as a conference paper at ICLR 2025
Next, we take the expected value of the above inequality and use Lemmas D.2 D.3 and get
D.4 (c)
Eg
- 0iktt -Imokttu 1|]
(((t))) - 1
<
1+ ptk
2 p Bgu-)) -
1 1m0 1 2
+3 + 75(k)
d (a(tt)
)²
2
mo²² "mm²²
(5² + 233) Eg(--)) | - 1 -000) 0 11]
p(k)
+ m (s² + 23²² (1 (1- ((hi BE(--) [10te] 8r 1711))
( (p()) O(M k) (k) (v(r) 1m (T(
-2a (1) (B)))
Im - mm v(()
B B(bo))
m
+ m (a()))
max maxo0
1 + ((k)
1 1 p(k)
max (altt) 2 (5² + +288)
1ggu-1)) |0000] 1m 0
+ 3
x(k)
1 + p(()
(ath)) 2 (s² + 2,3 (1 (1- min
Egu- | (800-89 8. 0-11"]
+ 3
mad
1 p(())
3 + x(A)
+ m (al(tt)
(K)
0² 0²)
max
p(k)
F.3 PROOF OF PROPOSITION 4.10
Step 1: Setting up the proof. We want to find the conditions under which we will have p(p(())
<
1. As we have a (A)
[ and p( (b)) max { [
where
x(A) are the
eigenvalues of the matrix (*) for 1, we need to show that max [1((a) Therefore, we first write the eigenvalue equation of the matrix as
(k)
1/2
< 1.
(a (a-011) 2 (A (^- 2 1 -0
(k)
X² - (olh + 2 x +
011 02
(8)
12 22 =
(k) (k)
Since this is a quadratic equation in the form of ax² +b++ = O. we know that i < 0, and a, 0 and the determinant is positive, we will have max |
}
bt 4ac Therefore, we 2a
solve for
0 dac < 1 as follows
2a
VB2 4ac < b 2a +
4a (a + c) + 4a2 0 = a+b+c>0. 0.
Now, rewriting the above inequality in terms of the actual coefficients, we get
(k) (k) (1k) (k)
Φ12 221 > O = (1-0(t) (1 122 > Φ12 021 (15)
(k) (K)
(k)
(k) (k)
Pii 022 + Φ11 022
Furthermore, note that = 1 > 0, =
(0
(1) + 022
< 0 and 62 4uc
(011)
222
(M) 2
+
(K) (K) (8 P21 > 0 hold by definition, so we only need to check for
Φ1 22 1
(k) (k)
(k) (k) > O.
21
(16)
Eqs. 15 and 16 lay out the necessary conditions in order get (+)) <.
Step 2: Simplifying the conditions. Starting off with the more important of the two, we first
solve for Eq. 15 In order simplify this inequality, we choose have (i) 0 Φ < 1 and (ii)
(k)
25

---

always replace their values with new upper bounds for them. Furthermore, note that (1)) the Published as a conference paper at ICLR 2025
(k) 922
(k) S 1 for the main diagonal entries. For Pi1 as defined in Lemma 4.7 we have
0
+ ua(() ( 2
2,3
P11
(k)
(1-d d
(1
(17)
ua(k)
nr2
To better characterize the condition on a (k) based on the above inequality, we put the following constraints on (b) and (*) to get
(k)
Constraints 1: (())
1
(A)
2
[(]]]
-
2,32
1
(1+14+) (rx(t)²² -1,
112
(R)
0
where r(k)_ > 1 and ((k) > 0 are scalars. The above condition requires the learning rate (*) to be power-bounder which is something we want to avoid. Thus, if the right-hand side of the inequality is non-positive, this condition only requires us to choose a non-negative value for the learning rate, which is sensible. So, we have
2
(1+1(A)
(1(4))
-50
122
(R)
(A)
2,02
1
(())
2,32
+
1
1
S 0
112
(k)
12
(k)
r (k)
32
1
32
1
1
122
(b)
R22
I
(A)
S (H)
2ga
S 1
1
g
10
2
2
1
1
S
S
[(]]
32
1
2 n22
2,32
< (k)
min
1
[()
S max
1,
112
1
r(A
(k)
We observe that we found a lower and upper bound for the choice of 1 (k)
Next, in order simplify
Pií as defined in Lemma 4.7 we can use Eq. 17 to write
+ pa (k) (Ha 2
2,3²
Constraint 2:
1
(A)
2
1 + (a))
2²
(R)
in which r/(² 2 ensures that the constraint is satisfied, since we solved for Eq.
17 and found the
conditions on (8), r(()) and r(()) do Hence, for the bounds defined in Lemma
4.7
we get
11 [1+
(k)
dunax
92
Φ
2 (1+r(()) (TTh) S
-1) (1- Palk)
1 T(O))
(k) P12
(k)
mp
()) <
(b) P (1+14 (1-d
(k)
82 +
(a))
dmaxx
min
m
and there are changes to the upper bounds of Ø2 622 and w/t
(k) which were defined in Lemma Note that matrix (kk) and vector (k) in Eq. 7 were used as upper bounds, therefore we can
(k)
4.8
term d(h) was intentionally not interchanged with its lower bound. Consequently, with this new
(k) value for @1 we continue as
$ 0 = (
(k)
P 2(1 + (1+++)) (T! -1) (1)-0)))))
32
26

---

Published as a conference paper at ICLR 2025
Finally, we check the next conditions on 922 (K) for 011 + P12 and 021 the lower bound is O, but for (1))
(R) defined in Lemma 4.8 i.e., 0 < 922
(R) 1. Note that
922 it 1+ Therefore, the lower-bound
condition of 222 > 0 is already met. For the upper-bound condition 022 < 1, noting that we have 3+
< 1, we can write 222
3+ to enforce this constraint. We have
4
1 1+ ((0)
(k)
3+ p(k))
0 a (k) S
1 1- --p(k)
1
22
2
4
[(k)
v1 p(h) v (22+2 2,82
2V
Step 3: Determining the constraints. Now that we have made sure that (i) 0 < off S 1 and (ii)
0 < 02 < 1 in the previous step, we can continue to solve Eq. 15 For the left-hand side of the inequality, we have
(k)
(1 (1-011) v(11) (1
(K)
2 (R)
1 + (+))
(I -1 1)
82 a2a(()
1 2222
622
(k)
0
2 (1 1 r (8)
(8)) (r - 1)
1
1
1 ((k)
kkj
Now, putting this back to Eq. 15
we get
2
1 + ((()) (r! -1)
1
1
(K)
1
plk)
012 021
(k)
[R]
4
1 + p((k))
(/t B2
(k(
3md
(k)
1 + p(k)
(52 + +232
(1- ( )) (a1t))
max
1 plk)
mp
2 + (k))
(T! -1) (1
1
1 - p(k)
pi(k
4
(T()) / r(17
(1 - (1-
(A)
Vid v 1 + p(00
/ 52 2/2 (1 - d(t)
Finally, we solve for Eq. 16 Noting that by solving Eq. (k)
15 we made sure that 1 1-
-022 +
(kk
o 022
2 22
O, we can write
e> 0
Pi1 022 Φ12 21
(k) (k)
(2) (A)
> 0
Φ11
(k)
+ 92 - 1>> 0
2
+ r(ti)
(T( -1) (1
32 (k) + 1+ ((K)
1
1>0 0
T
2
# (1 + k(k)
(k)
(T -1) (1 (1- r
(1 + +(+ )
32
27

---

Published as a conference paper at ICLR 2025
Step 4: Putting all the constraints together. Reviewing all the constraints on (*)) from the begin- ning of this appendix, we can collect all of the constraints together and simplify them as
(1k) < min
(k)
1
1 (((k
14
1
2V 3dmnxx
V1+ p(k)
V(2 + 2,82
2 2(1+
(T!*)
- 1) (1
122
(1 + p(N)
4 (1 + r(())
(I?.. -1) [ r $2
[((a) 1 1
14 (1 p(K)
/1+ p(a) V/2 252 (1 1-ddiin
V6dmax
(k)
1
- p(k)
1e 11 + p(h)
min
2 (K)
v1 + p(k)
v(2 + 2,52"
4 (1+1 (114) -1)
1 To
g2
pIAT (1 - p())
2
v 1 + (TA))
v 2,32
2,32 (1- ((())
while satisfying
2 1,
(ik) > 1,
max 0, min {1,
2,8² n22
(1
1
11
(k) S max
1,
2B2 112
1
1
(18)
r!k)
r
(k)
Note that one of the terms in the above minimization funetion was trivially removed since 1+p(2)
2
1. In order to simply the condition on (A) further, we take the minimum of these terms with respect to each variable separately to get
r (k)
H #1 ((0))
a (k)
< min
min (
min
((A)
4 1 + + (T!4) -1) (1 lot
82
/r -1 11 1- (1 - k(k))
(19)
v Virlth (b) v 1 + ((k)
62 + 2,32 (1 (k)
1 - ((A)
1
2 (k(
1 + p(0)
V22 + 2,82
Solving for the inner minimization in Eq. 19 first
using (k) by defining q
Vi- F (1-2(0)
4 (1++((+)
8²
and
we have
Vodik)s 1+0000 /c2+20' (1 (k)
a(
min
((k) (k) -
1 << S ST (R)
c -0) 11)
(20)
v V/(42) 1; 1 > 1T(1) (k)
4 (11 < ci
28

---

Published as a conference paper at ICLR 2025
in which 1 is due to Eq. 18 We can see that in Eq. 20 one of the expressions is increasing
with respect to (8) and the other one is decreasing. Thus, we find the optimal value for it 1 (g( as
V Tr2 (22(k) - 3
12
2/3 +
(R) (k)
C2
ci (1))(())
(K)
2/3
VBdind / + p(k) /1(())) / 52
2,32 (1
d(l)
"inn
1 (1 + +
+ (k(
+ +1
1
(1 - (1-p(h)
4 (1+I(*))
1
82
(1 + (10) /3 x² 2,32
2/3
Dmaxk
+1 1
(T+)(t) (1 ((4) (1 (1
2 1 - 1
rb
Choosing n
(k)) we get
(T()) - -1 1- (kk (1 - -(())
1 (11 + x)(k))
2
min ry
4 11 r(,)
(T!!.) -1) (1-
min
B22
/dd max
V 2003 / + 2 (1 a
2222
1 (1 g(6))
ci C2
(k) (N)
2/3
(k)
2
1/3
( 1 + ((()) (1
(k)
32
(k)
min
1/3
2/3
1
661 ((1+T (1)) (52
2,32 (1
(k)
(b) 3
mln
Note that by making this minimization over (k) the dependency on ((k) was removed as well. Moving on to the second minimization in Eq. 19 using (+). we note that finding the optimal value
(*()) would be analytically cumbersome due to the conditions that need to be satisfied for it; First,
r 0, and second, min {1, 2.a n² (1-d ((b))
1) < (k) max 1,
2. μ. (1- d - }
Thus, in order to get more intuitive upper bound for (k), settle for possible suboptimal value for If we choose r which is the only point satisfying the conditions Eq. 18 and also does not rely the value of (k)
get
1/3
2/3
((()
(k)
min
p²
12 (2 2,32
1 1- ((((
1
2V (h)
VI 1 + p(0) 2 + 2,9
29

---

Published as a conference paper at ICLR 2025
Step 5: Obtaining p( ((()), We established p (8)) < 1 in the previous steps. The last step is to
determine what p (((k) is. We have
Pi1 + 22 + V (011
(k)
(k) - 922
(k)
2
(01))
(K) 92
(k)
P (D(A))
-b
B- 4ac
4
@11
12 21
2a
2
$11
02
(k)
+ V
1/11
(k)
022
2
+ 10 1221
(K) (k)
1
2
(+ (+) (T -1) (1-
1
32c + 1 1+ ((0))
2
1
14
1 +
I [k)
2
+ 3
1 + k(
1 - plk)
(()
max
(alt1)² ?
"(22 + 259)
(1 (1_
2 (
1 + (()) (Tr4) -1) (1
1
B Ba
2
1
rik)
+ x(k)
+ 7Tk)
(alti) (c2 + 2,32) 2
d(b}
2
p(k)
max
1 1+ ((h)))
dltt 32
(a(tt)² (5² + 2,82 (1-d d )) 1/2
a (k) 1 + ((K)
((())
mdl (K)
+ 4
1 p(k)
max
mp
3 + g(k)
1 (1+T)+) (T! -1) (1 -1)
1
3²a
4
/1
[k)
3 + p(k)
d(R)
(5² + 239 (a(tt))
2 11-
p(k)
1 (k)
2
+ r(()) (I((A) -1) (1- -1)(1-
1
(a(a))
2
2
#
1 + (())
- p(k) max (s² + 2,33 (als)) 2) 2
3
+ ((a)))
(k)
82
+ ((k)
(bb) 2 (5² + 2/3² 2332 (1- - (a(h) 3 1/2
+ 12
1 p0k]
mmxx
1
Therefore, ((((k) follows as (()(
3+
(k)
+ (a
+
1 (= p(h)
-((1()) + (a.))) C(k) (a(A))) where (Ak)
# (T 1)(1
1 1
)82 B(0) 1 dluxx (5² + 2,32) and C()) 24 0² (+)(0)
# 1-200) (d 2 (s² + 2.3 duld ))-
The value for the constant 1 1 was given in step
F,4 PROOF OF THEOREM
Note that by the properties of spectral radius, we have that l I1 S p( -I. Now, using Eq. g we can write
E E
[[rk+1]
00 1,, 0 (1)+1))p00)00 [e]
| - 00112
K
S x( K+1
Σ
p + K
v V.
Eg00)
E
1 (K+)))
||000 1m 000 ||
We emphasize that the time index A in (k) and y (k) was dropped, since we are using a constant learning rate, and substituting the bounds for all) I and d(i) 2 dmnn and g(k) < p. This
30

---

Published as a conference paper at ICLR 2025
results in the constant matrix ((4)
+ and the constant vector (p) V Focusing on the term
Σx K
(($)
K
K-r-------
V V get
K+1
k
80 p())
Σ
p +
K
v v
Σ
p K
Σ
p
T
Σ
v
L
p(
p (b)
Putting the above inequalities together concludes the proof of Eq. 9 Finally, noting that p(
following 4.10 We can let K + to get Eq. 10 Note that
p 2 2.Ao, where A =
(T; - 1)(1 T/ with Fo, r being constant scalars defined in Appendix F3
We also note that Eqs. 9 and 10 are derived for the consensus error and the average model error themselves, i.e., their last iterates. As summarized in Table this is improvement over existing works with sporadic aggregations (Koloskova et al. 2020 Lian et al.) [017)] [Sundhar Ram et al,, 2010) where only the Cesaro sums (i.e., the rumning averages of the iterates) of these error terms bounded.
G NON-CONVEX ANALYSIS
In this appendix, we analyze the convergence our methodology when non-convex loss functions utilized. Our approach will be entirely different than the done in Sec. [ as we will be using the non-convexity assumption (Assumption 4.2) instead of strong convexity (Assumption 4.1).
We will still characterize the expected consensus error Eg (I++) 0(++)) [1]] but trary to what was done in Sec. 4 instead of the distance of the average model from the optimal solution, we will analyze the norm of the average model gradients (gg()) [] (F(+++)))) As an alternative to Lemma 4.7 first provide upper bound the average model performance each iteration for the non-convex case, i.e., |B [F ([((+t))) in Lemma G.3 Then, as an alternative to Lemma 4.8 we also calculate an upper bound on the consensus error for non-convex models, i.c.,
Egm0] (f+1) 0(++1))) [1"]
in Lemma G.4
We first need two preliminary Lemmas, each of which will be useful in the proof of Lemmas G.3 and G.4 respectively.
Let Assumptions 4.1 [a) 4.1 [c] and M. hold. The following upper bounds related to the gradient of the global loss function can be obtained in terms of the gradient norms Egu-1> F and the consensus
Lemma G.1 (Gradient bounds for non-convex models) (See Appendix H.1
error E (k)
010)
(a) E Eg VF p
2
$
d(l) ()) VF +
max
(k-1)
m (())
2 + 2(1
(k)
dui)))² )82
(b) Eg
V
- (2
) |
g
||| 1 (k)
1m (k)) ((k)
[3 + (1 min )82
(k)
)82
2m
(k) 2
(c) !
Eg
(2))
Ve
S
[1 + 21
+
g(4)
maxx
Eg(k-1) (A)) 1,
(())
[] 2(1 - (k) )82
Next, find upper bound the expected deviation of the gradients from their average for non-convex models, similar to Lemma D.3 which was derived for strongly convex models.
Lemma G.2 (Gradient deviation bound for non-convex models) (See Appendix H.2 for the proof)) Let Assumption 4.2 hold. For each iteration k > we have the following bound the
31

---

Published as a conference paper at ICLR 2025
expected enror of gradients from their average
l 1m Vo "11
0 m 0(k)) 19
(g (A)
8d
8
|| VF | (((k) (12 + 2m0²
2mm2 Bgt 1)
in which (k) is matrix whose rows comprised of the gradient vectors V VF(O and Vo
1 E VF(
Now, we can continue with our key lemmas for the non-convex case. Similar to the con- vex case, we first derive counterparts for average model enror and consensus error, i.e., Lem- mas 4.7 and 4.8 for convex models, respectively. we first provide an upper bound on the aver- age model performance Eg [F((k+())))) (Lemma G.3 and also upper bound the consensus error Egu (k+1) 1 0(+++)1) I"] (Lemma G.4 at each k.
Lemma G.3 (Average model performance for non-convex models) (See Appendix H.3 for the proof.) Let Assumptions (4. and 4.3 hold. For each iteration k 2 we have the following bound on the expected average model performance:
Eg( [k) [F(((+)))]
Eg
o 1
+
P12 E Eg(t-)> (| 1(k 121 + V/
(k)
1.40) )a and 1i (k) = (8))(( [(1 miu (1 + ( + (k) daax o² 112
where (k)
Q11 = = - (1
d (A)
min ) B(1 252
(8),
ged a (1) + (1)
(())
In Lemma G.3 the upper bound on the expected error at iteration & + 1 is expressed in terms of the expected performance Eg [F(- the scaled gradient norms @ Egu-.) [II (((k)) 2 the scaled consensus error Φ12 Eg 1 ||| (A) 1, k) 1² (which will be presented in Lemma G.4
(k)
and scalar v/(), all at iteration k. We next bound the consensus error in the following lemma.
Lemma G.4 (Consensus error for non-convex models) (See Appendix H.44for the proof.) Let As- BeaaudxxHHHffe sumptions 4.2 4.3 and 4.4 hold. For each iteration k 2 O, we have the following bound on the
expected consensus error:
Egw - 1, 0(++)) < 0221 2
Ega-n [I(())
|1 1 Ezu-D B=n-v||(@(()) - 1m a(k) 12++
22
where 22 16 1(00) (k)
T- pLay mnddu (
1+
L+2(0) (b) --ii
(a (k)) 3² and wi
022
8
8² + o²), where (()) is defined in Definition 4.5 and Lemma D.4 ((a(1)) 2 ((h) (16 1-p
1
From this point forward, our analysis method will differ from the one done in Sec. 4 Instead of forming an error vector like Eq, and analyzing their joint behavior, we first expand the consensus error recursively to get the next lemma.
Lemma G.5 (Explicit consensus error for non-convex models) (See Appendix 11.5 for the proof.)
Let Assumptions 4.2 and 4.4 hold. If the learning rate (k) satisfies (k) < [)) 4B del (14))))
1-
with (k) 1,
then for each iteration & 2 0, we have the following bound on the expected consensus error:
EgM (k++1) 1 0 11+1))
(k:0) 10 2
(0)0)
2
Σ/= 22
1k)++)
0 Egi-- VF(()))
(kT+1)
22
12
where (kar) I 122 and the values of 021 22 and w/
(8)
(k)
(k)
given in Lemma G.4
32

---

Published as a conference paper at ICLR 2025
Finally, use the upper bound derived in Lemma G.5 in Lemma G.3 to derive the following proposition.
Proposition G.6 (Explicit average model performance for non-convex models) (See
Ap-
pendix H. the proof.) Let Assumptions 4.2 and 4.3 hold. If a non-increasing learning rate is used, i.e., (k++1) S aak), which also satisfies the following condition
(k)
1
1 ((a)
2/2 -
(
((R)
min
(8) < min
2/3 [
4 d (1 + p(k)
2
3
01+25 25² 1
(k)
(r(
1
1
<2 (1
(1-di
daain
1 - k-((k)
4T (R)
V 111 +T
(k)
d C,B
v + p(R)
then for each iteration & 2 0 we have the following bound on the expected average model perfor-
mance:
Eg [F(((++1))]
S
F(O(O))
Ex
P Rgi
[|V
a W2 (0) 1m 100) ? + Er== k-1
(0)
(1 uwy
(r) (r)
+ Ex
U/2
in which
w (k) (2 - (1 (1
1
(1 (r(
wh
d (1+r
and the
m1115(0) (11 (1-
(k) and //(²) were given in Lemmas G.3 and G.4 values of v1
H PROOFS FOR NON-CONVEX ANALYSIS
H.1 PROOF OF LEMMA G.1
a For this deviation term, we use Eq. and triangle inequality to write
VF(O Ve 10 =
1 m
VF((O())) VP((O!")) yo!
m
V.:(O(()) (o) |
m
(F(())))) - (F((
2
VRI(0
0
1
87 g(()) B(()
2
5 + 5
VE(B 12)
m
m
=1
-0)=
1 m
3
g())
1
(M)
2 m
m
07 <7
0
m
where in the line second to last, smoothness and gradient diversity (Assumptions 4.2 were used. Taking the expected value of the above inequality concludes the proof.
(a) and 4.2 (b)
b Second, for this inner product term, we have
(VF(O()) Ve k1)
V (((H))
Ve (K)
VF(O(H)) VE(OCH))
VE(OMAD)
+ (VE(O(A)), VF(O(()) - ()(
1
2 VF(E(R) Fo
1
$
+
2
33

---

Published as a conference paper at ICLR 2025
Now, taking the expected value of this inequality and using part (a) of this lemma, we get
Bg (Vr(Ot)) (v
s 3 ()
8² Pdlles
|0000)
1m g(b) 12]
+
E Rg(0-1))
2m
+ <2 (1
d
||
Egu--1>
min
+ (1
(
8²
min
< 5-2 222
( - (1-d(
VF(O(A))
()
Be Pdinax
1 B(6) 17] -
||0|h)
(1 dblnn) 8².
+
E Ez(-11)
2m
c
Finally, for the norm term, we have
2
Ve (k) -V
VVF((+))]
| | -V 1
<
2
Taking the expected value of this inequality and utilizing part (a)
of this lemma
[7]
B²
a
[0(0) (k) 1m 16.00 19]
Eg
Vo
S Ega-n
+
Eg (4-11)
2
+ 2 (1
-
E E
VF(O [|]] + 2 (1 d 82
$ 1 + 25² (1-d(2)) 1g V
32 dall
|0 1, x(k) 2
+
Egga-1)
m
+2 1
(bb
8².
Amnn
H.2 PROOF OF LEMMA G.2
We have using the definition of Frobenius norms matrices and triangle inequality that
1m
Σ V (o(
V.
(F((
)0 (0)
(F
)0
)FF(())))
(M)
(F (1) -VF
+ V1 - 00.0011
m m
- (1) + ( ( (1) + | (0 1| 10000
m
- - 1/00000
+
34

---

Published as a conference paper at ICLR 2025
113
172
83 00
- ((())
||
(1)
88 +, VF (0())) o.60)
u + +
m
VF ((65) /|² og() + + ((6) 1
+
87 + 67
1 (1)
08 + <? VF ((b)) 11²) m5!
4
+ 2
i=1
+ Σ
63 + 53
v (
/1²)
(4)
+
Σ
B3 [(a) 0 (K))
j=1
j=1
33 g(())
g(h)
| ? +2 o0 27
VF V ((() (10 ((t))
88
1=1
m
(<2) VF ( || + 8² m
I 8,32)
( - Bwl Σ 1=1
of 16
(1))
where in the sixth line above, smoothness and gradient diversity assumptions of Assumption 4.2 were used. We next take the expected value of the expression above and use uncorrelatedness or random variables of Assumption 4.3
(b) and Definition 4.6 to get
(4) 27
E ggo
(k) (k)
1m Vu
S 8.02
m
E Bg( 1)
(1( - -
E mea 1
(8)
1=1
+1
(2
(16) )1)
+ 8²2
Σ
E (2)
1/3
(K)
< 8,32
m
(k-1
(((()) -0(k) ||
d((a) + 16 (
|| VE (occ) /E((EL)) |1|
+ 82
Σ
i=1
1=1
< (832((k)
Egi
00()) 1 Tik) 27
+ 1 1md
(t)
|||F((t4)) (1142) 119
+ 82
max
max
|0(0)) 1, 5163 ||²
= (a(k)
3 B'Egu-D)
+ 2m E
+ 2m8²
max
H.3 PROOF OF LEMMA G.3
We have
- 8 g(a) - o
)(TU+1)) < <F(TU)) + (Vr(Ow)) 0)0-)) -o(k)
2
F(O())) + (VF(O())) - (1) gv(h))
+ 8 (1) goll
2
-F(O()) - (t) (VF(EL()), (t)
(1)
aa (1)
(FF(0()),
+ 3 ( (a())) 2 2
Voa (k)
2
3
(k)
2
| + 3 s(att) ()(((o))
/ (votk) .co(k))
+
2
in which the relationship in each of the three lines follow from (i) Smoothness (Assumption 4.2 (a) (k) for all M. Next, we take the expected value of the above
(ii) Eq.
(iii) (k)
-x(1) + c;
35

---

Published as a conference paper at ICLR 2025
inequality and use Assumptions 4.3 and Lemmas D.2 and G.1 to get
Egi ((((ktt))]
F((())] (1)) ( 5² (1- dmiua )
E Ega 1) | [1]]
s Egu 1)
8
dmaxx
(85 14) (ggt-1)) ||0m00 1m mm/ ||]]
+ + (b) (1 - d 0²
+
2m
+ 1 1 2c² (1- dmann) }] (al()) B Bg(R-1)
|E( ||]
3
dmnx
2 E Eg (a(ti)
||0(0]- - -Imoruu/
+
+ 28 ( 1 -
d²((a ((alt)
+ 3
( (a())
2
d o²
max
m
< (g [
(1k)
1
5²
(1 dmin) - 3 (1
(1+2) + 2c² (1 d )) (k))
E Eg(--1)
| VET
2
3 diiax
||0 m B(h) 11 19]
(k)
(1 21+)a((()) (A) Bggx
2m
1)
+ (k)
(1-dmit ) (1 (1+) 82
13
(a))))
d dmnax
2
m
H.4 PROOF OF LEMMA G.4
Note that we proved similar bound for the case of convex models in Lemma 4.8
Thus, we start
from Eq. [4] derived in the proof of that lemma in Appendix 4.8] We take the expected value of the inequality in Eq. and use Lemmas D.2 G.2 and D.4 (c) to get
Ego0
o (k++)_
1m 1i 27
1 1+ p(k)
(1))
|lw - 1m |
2
1 + (TA)
dhii (astt))²
|1000 1m
Amooss 17]
+8
3 B
1 - x((K)
+ 2m5 2 F Fa(k 1) |VF(((A)) (8()) )(())) + 2mn2
( (D()) 1()) - (k) (Vit)
-2a (1) Bgw
1m vo (1)
1 1m 15: (() g()) [(0)
4m
m
+ m (a(t))
d(R) 0²
1 + p(()
+ 8 1 + p(()
1- p(k) d(k)) (a44)² G² Eg(t-1)
||(()) 1m 066) 19
<
2
+ 16
1 (((h)
1 1 p(k) malti (a(t))
2
2 (1-1)
VF ((()) ||]
+ m (all)))
2 (A)
16
1 + p(k)
8² + o²
max
1- pla)
36

---

Published as a conference paper at ICLR 2025
H.5 PROOF OF LEMMA G.5
We expand the bound derived in Lemma G.4 to get
[((++)))
1m 0(++1) 27 S
gg(
II 22
(0) lm 0 ||
02 La
||
@ )1
+ w5!
22
#=++1
We need to make sure that the consensus error diminishes over the iterations. Towards this goal, we have
ensure that d/22 < 1 for all k 2 0. Using the definition of P22 from Lemma G.4
(k)
+ (())
((a)
((k)
+ 1 - p(k) d (a (2)) g2 <
(1k)
2
4,v diiss + p(:)
We will find it useful later in the proof of Proposition straint
G.6 to define the following equivalent con-
1- p(k)
(K) S
T > 1.
[(k)
(K) (1 + ((0)
48
This results in 922 < 1+p000
1- 7(0)
(r(2)))
H.6 PROOF OF PROPOSITION G.6
Step 1: Recursively expanding consensus error. We substitute the upper bound derived in
Lemma G.5 in Lemma G.3 get
Ega
F(
<
E
11
F(((t))]
E
10/2
(k)
1:0)
(0) -1 010)
22
22
(k- 1:++1)
921
(1)
E 1-11)
V ((()) )19
+ [5)
+ (i(())
< R (1
P(O(())
Ø11
(K)
(-1)
|F 1|]
+
2:f00 12
1:0)
m 000) 2
+ 1
(k)
k-1
(k-1+)11)
22
Egr
|F(( 11/
+ 112
A-1
2
1 + 1) (r)
+ +/) (R)
Now, summing both sides of the inequality from to k: K, we get
[((OU+H1)]
< F(0
| |?]
K
(k-1:0) 1:0)
[0) - 1m 0000 /?
+
12
22
k=
(8)
(k (111++1) (r)
V F. (tr)
[|]
12
22
021 11
k-1
(K)
(k 1:
(7)
+
2
+
0=
F=0
0=
37

---

Published as a conference paper at ICLR 2025
= =
K
19
+ 1 - 1 B6)) /|3
K
1:0)
11
12
22
k=0
21 E
(r)
VF
(FF(0())
(Kr))
(k) (k- 11++1) 12 22
k=
K
K
(k) (x-1:)11)
12 22
k=
k=
F(
(k)
(N)
K
(r) (r- 1:8+13
B V 21
|]
P11
021
P12 022
r=1+1
(K)
||> ||/
+ 100000 m00 2 K
(k) (k-1:0) 12 122
P11
k=
K
(r) (r- 11++1)
2
112 Q22
1++1
0
Step 2: Simplifying using non-increasing learning rate. Using the definitions of 0 and 22 from Lemmas G.3 and G.4 non- non-increasing learning rate means that the upper bounds for ((k) and (k)
222 is non- non-increasing as well, knowing that a!!²) I and p(k) < 1. Thus, we have
Eg(K)
[(((k+i1)]]
S )(((())
K
P11
(k)
P2
(k)
P12
(k-1)
1)
Σ
K
02
(
(k+1)) r-1-k
E
r=
||E 11]
2
K
211 E
E
+ (0) 1
000)
112
22
A=
K-1
(k) (k+1)
K
(((+1))
1-1-
(8)
1/2 12
822
k+1
K-1
K-1-k
S F( - Σ
$11
(k)
22
(k)
12
(k+1)
222
((+1))
B 1)
V
K=
==0
$11 Eg(K-1)
||F
+
(0)
1
8
12
(0)
k=
K-1-k
(k) (k+1)
Σ
(
(k)
+
222 0/2
02
+
D=
0=
S F(
Σ
$11
(k)
(k) (k+1)
1/
(k+1))
Rggi
K=0
0 || |||] +
Φ11
E
1
012
(0)
K +
(k) (k+1)
Σ
00/2 (b()t1))
==
0=
38

---

Published as a conference paper at ICLR 2025
R-1
(k) (k+1)
=(((0))
Σ
(k)
21
12
E Ege
| ||
(k+1)
k=0
22
1
mm ((0)
2 02
K
(R) (k+1)
E
(K-1)
(F(C()))
(0)
Σ
2/2 12
(k+1)
22
k=0
1 22
(k)
K-
(k) (k)
$ F(((
Σ
(k)
21 112
Ega-1)
P11
1 22
km0
10 - 1m ((0)
2
K
(k) (k)
(K)
|
12
2/2
12
11 Bgi 1)
kk)
422
1 22
K
(k)
Step 3:
We need to ensure that the gradient descents result in lowering the average model loss.
Thus, we need to make sure that Φ1 > 0 and @1
> 0. Using the definitions of Φ
1- d
from Lemmas G.3 we first solve for @11 > 0 to get
(k)
1 5² (1
+ 2c² (1
dut
(a) 0
- (1
0< (k)
3 1 1 2ç
d(lb)
Note that the above inequality implicitly assumes the following constraint as well
2/
1
2² (1
(k) dinn 1 2
which alternatively is equal to
r > 1.
min
((A) 2
Next, to solve for (1)
(k) (e)
0, we need two extra constraints on (8), The first one follows
1-022
(A)
[(]
(k)
1,
(k)
2,3
which results in Φ11 2 (A))
1
1
The second constraint on a would be
r
(k)
a (k)
(k) > 0,
28
which implies 01 (k)
(k)
pa(e)
mmax
+ (k) (k),
Using the previous two results and the upper bound
2m
for 02 derived in Lemma G.5
continue as
(k)
1
(())
(1-
(k) (k)
(K)
I-(k)
(K)
2
(T(()))
P2i P12
39

---

Published as a conference paper at ICLR 2025
a (k)
1
1
p(k)
2
(R)
2
(8) 2
2
+ plk)
8 (K))
16
me
(b)
(altt))²
(22)
a (1) (1 1 (
max
2m
V (1-
1
12
1 - p(k)
a (b)
6
4 1 + (k)
V 1 + p(k)
{,3dmuxx
Finally, setting the following constraint
(1- ( (1-
1 p(0)
(k)
r > 1,
4v2 V + r(a
v1 + p(k)
{Bdmax
obtain
(k)
21
(k)
112
(k)
(b)
1
(1
1
1 (1))))
111
1
222
(k)
2
1
2
H.7 PROOF OF THEOREM 4. 12
We are given that a constant learning rate (*) = a is being used, and we have that p(k) S p with I maxoşAsK pott) for the spectral radius and a!!)) > dinin with duuin minogAgK (:4)) for SGD probabilities. Thus, we can simplify the results of Proposition G. get
EgIN) [[(OK+U)]] s ((00))
K
||| V | ||
wja
E
r
1m 60/0 l|
+ aw0
+ awwgbzK - +2(K + +1).
Therefore, if the learning rate satisfies
T3
1
1
To
1
< min
23 I 43 +
p' 2T 3
+ 1t2
(1- -- -
v 1-1 1 CB VI+p
To 1- P
4V21 I +1%
then we have
K
17
1
F F(B())
F* + 0
1m00o0 aw2
K
E 2
1)
awi (K + 1)
+ Oow2ts + 12(K + 1)
< 1
F (0(0)) - F+
1 0(0)
W2
+ a² W2 + (1 dmin) Jwy + aws
W1
a(k + 11)
k: + 1
where W1
(11 )1 (1 )1
+
W2
B² 8'd (1+Ta))
W3 = mdmax (16 T-p + 0²),
m(1 (1-+))
w4 = (1+Tz))' and W333
3dmaz 2 2m
Also, the conditions on the constant scalars I, with 0 5i55
are To, [ı, T2, P4 and 33 > 0.
40

---

Published as a conference paper at ICLR 2025
I DIMINISHING LEARNING RATE POLICY FOR CONVEX MODELS
In this appendix, we do the convergence analysis of our methodology under a diminishing learning rate policy, ie., when (k++1) < (*) for all k 2 O. We will show that convergence to the globally optimal point is possible if the frequency of SGDs, i.e., dftt) is increasing over time. Thus, few preliminary lemmas are first required, to re-derive the counterpart of Proposition 4.10 for the increasing d strategy.
Proposition I.1 (Spectral radius with diminishing learning rate) (See Appendix 1.1 for the proof.) Let Assumptions
4.1
4.3 and 4.4 hold. If the SGD probabilities are chosen as dfa
1 - ThS (k) (k) with 0 S 12
(k)
(A) and Mmin = minseM !i (8) and the learning rate satisfies the
(k)
following condition for all k
[(K)
1
1 (-p(k)
1
min
2/3 v1 p(k) v 2
1/3
1 11-p(k p(k)
2/3
(k) r g2 (52 + 2
(1+
23
a
then we have pl (b) < 1 for all k 2 O, in which pl-) denotes the spectral radius of a given matrix, and (b() is given in the linear system of inequalities of Eq.
7 pl (()())) is given by
p( (1))
()) where h(a(1)) = 1-5000 + A (R)
B (a())²
1- pin) a((( + )1)) (((N)) and A(A) Biin r())
(1+T (T2
21-p(k (5² + 2 and (+)) = 12 (1 14 (5² + m 2 The value I- (k) for (k) given in Appendix J.1 and 0 <T 1/(1 28 muin/ n²) is an arbitrary scalar value.
1)5². B(R) = 3 (+
1
Proposition I.1 implies that lim T (1:00 = 0 in Eq. However, note that this is only the asymptotic behaviour of (k:00) and the exact convergence rate will depend on the choice of the learning rate (R)) Furthermore, noting that the first expression in Eq. 8 asymptotically ap- proaches zero, Proposition [.] also implies that the optimality gap is determined by the terms Σ (k:rr (r--)) + (A),, and can be made zero if the learning rate (k) satisfies certain con- ditions, which we will discuss in Theorem 1.5
Proposition 1.1 outlines the necessary constraint on the learning rate (k) each iteration k: 0. We next provide corollary to Proposition [.] in which we show that under certain conditions, the above-mentioned constraint needs to be satisfied only on the initial value of the learning rate, i.e, (0).
Corollary 1.2 (Constraint diminishing learning rate initialization for convex models) (Corollary to Proposition [.1) If the learning rate (k) is non non-inonenn con-increasing, i.e., a ( S (k), the SGD probabilities are determined as d:a) = 1 ( with 0 S 5 नमक and Tmin = minge Ti for all k 2 O, and we have constant aggregations probabilities b(k) bij. then the constraints in Proposition 1.7 simplify to
1/3
(0) min
Ti
1 1-
1
1 Ā 2/3
2//3 VI
5 +
23
6 (6(52 2m 8a
(1+ri)
2,3
This also results in time-invariant scalars A Akk B B(k) and C (((k), where these quantities were defined in Proposition [.
In the above Corollary, we obtained the constraints on the initial value of the learning rate, i.e., (0) that lead to the spectral radius of ((k) being less than 1, i.e., p (A)( < 1. Note that since
41

---

Published as a conference paper at ICLR 2025
the learning rate diminishing, i.e., lim (k) 0, it follows that d 1 k and lim d = 1, which means that all clients will basically do SGDs at every iteration for large enough values of
Two final building blocks are necessary for the proof of Theorem 1.5 We present these in the following lemmas.
Lemma 1.3 (Bound for product in summation form) (See Lemma I in Zehtabi et al. (2022) for the proof.) Let {Gr) T be a scalar sequence where 0 < G. S 1, Vr 2 0. For any Z 1, we have
(1-1
P D
Next, outline another crucial lemma for our analysis.
Lemma 1.4 (Bounds for learning-rate-based quantities) (See AppendixU.2foor the proof.) Let / + k/7 be used, which satisfies the properties
diminishing learning rate (K) (0
(++1) < (k),
(K)
(a())
<x
(21)
k=0
k=0
1.1 for the SGD probabilities, i.e. a!!)) the aggregation proba-
Under the setup of Proposition bilities are constant, ie., Uig big for all i E MM and (i.5) E E(), then the following bounds hold
(a) En al1) 2 (0)
(v 1V1+ 11
(b) 1(a 2 (R)
(r(2
(c) Σ
per b(ai0))
< (0)) 44
2(++1)
In
/ 1+
In
2 1+4 --ع
[ 1+
1+
where (k)( and the constant (kk) were defined in Proposition 1.1
Using Corollary 1.2 and Lemmas and 1.4 our main theorem follows.
Theorem L.5 (Strongly-convex convergence result with a diminishing learning rate) (See Ap-
pendix J.3 for the proof.) Let Assumptions 4.7 4.3 and 4.4 hold. If a diminishing learning rate
policy (k) ()) / k/n, with > O satisfying the conditions outlined in Corollary 1.2 is
employed, and the SGD probabilities are set to a(()) = ((1 d(()) )/a (a)
(k) for all E M,
while aggregation probabilities are constant values, i.e., 1 big for all i M and
(i,j) E g(),, then we can rewrite Eq. 8 gas
(K+1) < o
20)
22 22(1+po (0) (0))(1) (a)
+ (alo))²
K
+ +0 11 )
82 + m
30
+ +0
VK
V
m 3 1+ 02
+ o2
1-p
(22)
Letting K + 00, we get
lim 1/ (K+1) = 0.
(23)
K
Note that the last condition implies lim
42

---

Published as a conference paper at ICLR 2025
1.5 indicates that by using a diminishing learning rate policy of a a (0) / / + k/7, DSpodFL achieves sub-linear convergence rate of (Inn//V /K),,, and Eq. 23 shows that asymptotic zero optimality gap as k + oo can be achieved.
The bound in Eq. 22 of Theorem
However, it is worth noting that choosing the SGD probabilities based on the learning rate, i.e., ((h) = (a)/// /a(0) for all E M and 2 0, only of theoretical value in this paper. This is because our motivation of introducing the notion of SGD probabilities was to capture compu- tational capabilities of heterogeneous clients in real-world settings, therefore, is an independent uncontrollable parameter and cannot be chosen based on the learning rate.
Finally, note that setting system to conduct SGD at each iteration as l + co. This result is akin to Wang & Nedič (2023), in which an increasing similarity between the learning rates of clients is needed for convergence, despite them being initially uncoordinated.
at()
a (0) equivalent to having all clients the decentralized /
J PROOFS FOR DIMINISHING LEARNING RATE POLICY FOR CONVEX MODELS
J.1 PROOF OF PROPOSITION
Let the SGD probabilities df
be chosen the following for all i E M:
(R) 1/i "/i (R),
(k)
(k) M
(k) 6E.M
m
(b)
Tmax
max SEM
min !
where (R) is the learning rate with diminishing policy, i.e., limg- (R) 0. Based on this relationship that we put between the SGD probabilities and the learning rate, we first rewrite the bounds for matrices (k) and (R) which were given in Lemmas 4.7 and 4.8 We have
2 (ash))) 2
(R)
o(() = 1- (x) (1 (aa - (1a())))
(1
(1+ (t) 8²,
+
1
(x)) g2
1 = ( (++ (1 m (8))
mu
1 + p(k)
21 3
x(6)
m
n/ a(t)) (a((t))
(5² 2,3
miin ((()
(A)
(24)
(K)
1 + (Kk)
1 1 5(k)
(1 - (tt) (40) (+)) (a(t)) 2 (s² + 2,3
222
3
1 p(()
2
0²
(a)t))
(1 (aalttt 82 + +((1
1
(k) m (1
(a(t)) a
2
1 ((k)
82 + 022
4/2
p(k)
The important difference with the terms in Eq. 24 and the corresponding ones outlined in Lemmas
4.7 and 4.8 is the fact that we get a (a!)))" factor for w)(h)) and (h This factor will help us show
in Theorem I.5 that zero optimality gap can be reached, which follows mainly from Eq. 21
Next, we do an analysis similar to the proof of Proposition 4.10 which was given in Appendix F3
Step 1: Setting up the proof. We skip repeating the explanations for this step, as they are exactly
the same as step 1 in Appendix F3
Step 2: Simplifying the conditions. Recall that we have to ensure (i) 0 <
P11 (k)
< and (ii)
0
022 < 1. For o/fk) as defined in Eq. 24 we have
(k)
(k) Φ
1 (M))) (Ha)
2,3
m
(k)
< 1
(1 + ((((())))) (xh)) 2
(25)
42
43

---

Published as a conference paper at ICLR 2025
We then put the following constraint on (*) to get tighter lower bound for Eq. 25
We have
(())
2 (k)
Constraint 1: a
na
r(A) (1+
(2)
1,
1
where r > O is a scalar. In order to avoid a positive lower-bound on the learning rate a (8), we find the conditions under which the right-hand side of the above inequality is negative. We have
2,327um qumin
(8)
((
(1+I(*)
+ (r
2 - 110
112
2
2
(I(N)
2 +
2,8
Mmin
(b)
(()) 1 < 0,
1+
42
41
(1+
2/9%
(N) 2,82
Mmnin
(((h) 1) (I +1)
0
-1
<<<<1 11(h) =11(///
1
112
2.3 [K]
1
Next, in order to simplify
011
(k) further, add another constraint using Eq.
25
to parameterize the
lower bound in Eq. 25 We have
1 + (a( - -
2,52n
(R)
Mmii (k)
+ (a(())
1²
1 + (k) - ( 2
2/8 mmin
2
(1)
Constraint 2:
(k) (k)
(())
T > 1,
1 + (k)
n22
25 is satisfied. Hence, we can update the in which 1/ > 1 makes sure that the constraint in Eq. entries of matrices (k)) and y (k) as
(k) (K)
(k) $11
2mmin
(1 (1+11)) (1) (P!A)) - -1) Saai)
S
1
11 p(()) 82
+ 2(k)
B2 1
012 1
(R)
21
(k)
S 3
1 - p(k) m (a(t)) (²2 2 T(())
mp
1 1+ ((A)
1 + ((h)
(k)
(a41) (62 + +263)
22
2
3
1 p(k)
w1th) < (a(t)))
2
2
1 +
(x)
(k)
82
w < m (a(t))
3
1 p(a) p(p) p(k) 82 + 02)
1
7 were used as upper bounds, therefore we can always replace their values with new upper bounds for them. Consequently, with this new value for (8) we continue as
Note that matrix o (A) and vector y (*) in Eq.
(k)
P
11
(k) (()) 20 (1+1(*)
[k)
-1) g2
Finally, we check the next condition 0 < (A)
I 1. Noting that we have 3+
< 1, we can enforce
3+
< 1 by setting 2
We have
22
1 + ((k)
3
((R)
0 (+)
1
1- p(k)
1
2
22
4
2/3 + p0A)
52 + 2,8
Step 3: Determining the constraints. Having made sure that (i) < $11 < 1 and (ii) 0 < d22 S 1
(k)
in the previous step, we can continue to solve Eq. [5] For the left-hand side of the inequality, we have
2m (()
(1-010) (1- 0l =
(1+r4*) (I -1) 82a (K)
(1 2
2m min
(k) ((k)
(1+1()) (r(4) -1) 32a (K)
1 1- p(k)
44

---

Published as a conference paper at ICLR 2025
Now, putting this back to Eq. 15 we get
2m
(N)
r(a)
(1/5)-1) 3² (8)
(8)
1-p(h)
(k) (k)
1 22
4
(1 + (++)()) 92 ((Ab)
3m 1 p(())
(² + 27 r(a))90 182)
(alti)) 27
(k)
mp
--((k)
1
(k) (()) Memin
1 p00(
(1+14+3) (1ga) -1) sl
1
4
(k) (k)
(154)-1) (1 (1- )2
1 Mmin
(k)
6 (1 + plk) (sa + 20
(k) (k) gz
Finally, we solve for Eq.
16 i.e.
c
01 222
(k) (k)
Φ 22 > 0. Noting that by solving Eq.
(k) (k)
15 we
made sure that 1
111
(k)
22
k)
+
111 222
(k)
12
22
0, we can write
c>0 0 +
911
(k)
+ 022
-1>0 0
(k) (k)
(A)
- 1) 33 1+ (())
21min
1 (1+ (T
1
1 >> 0
1
p (1 ((K)
(N)
4mmin
(k)
(k)
(T( (1+
- 1) $2
in which we have used the value of (1) itself, but the lower bound of 02
Step 4: Putting all the constraints together. Reviewing all the constraints on (k) from the beginning of this appendix, we can collect all of the constraints together and simplify them as
a (R) < min
(k)
1 1- ((R)
1
P
2/3
v1 p(h)
V 072++77 2,32
r(
(k) (())
1 + (1))
(1/ 1) g2
2mmin
(k) (2)
(I()) -1) (1 - p(i)) 2
10 (1 + p(0))
mmin
4n min
(k) ((k)
1 + (++1(1) (k)
(T. - 1) 32
6 (1 + p(k)) (5² 2miin
(k) ((k)) 22
(())
p(k)
/1 (1 + ((())
min
j 2v3 / 1 + p(R)
VC2 + 23
(k) T(( 4m
(k)
1 r (1)
(r(2) - 1) "2"
(16) (k)
(T!e)
(k) - (1 p(A)) )²
n Muiu
6 (1+ + p(k)) (sa 1 (k) 82)
15
(26)
while satisfying
max (-1.0) = 0 << T() < min
1
1,
2 2, ynin
2,92
(N]
1
1 +
(27)
n²
[((]] > 1,
(k)
0
5
Mun
a (1))
45

---

Published as a conference paper at ICLR 2025
Note that one of the terms in Eq. 26 was trivially removed since 1+g obtain
1. Consequently, we
((k)
- -p(k))
# (1 + p())
(*) min- ((k)
min
p
2/3 V + pik)
V/2 + 2,22
(k) mmmin 1
1 (++1]) (k)
(115) - 1) g2
(k) {()))
(I - (1 plA))2
Miin
6 6 + x(0) (52 + 2mnn 1
(K) (1)) 82
(28)
28 using r by defining a(b)
First, we focus on minimizing the inner expression in Eq.
Viii ret (1-P0))) and (k) (4) r1 (1+r(*)) 8 We can see that one of the above
6(1+p()) (542 ())
m(1+,30))
expressions is increasing with respect to ( and the other one is decreasing. Thus, we have
(k) 1 < 2 2 1 (R)
1
<
2
(k)
[ 2 12
1
(3)
(r
in which r > 1 is due to Eq.
27
Hence, we find the optimal value for it, i.e., (*)))
as
v (rz(*)
3
I r2(k) (K)
2/3 +
c
(k) C
(k)
2/3
(1 61+ p(h)) (52 + 21 2m
(k) (1k) 8
11 (1 + p(k)
+ r3 (x(())
16
+1 1
(6) (8) - (1-r( Mmin
(k)
1 (1+)( g²
3 33(2== min p((h) g2
1/3
2/3
1 7(0)
1
+ 1.
2n mmm
(k) (()) B
B
(1 - x(h)) (1 + ((())
We choose (k)
= r (k:
(see the explanation given in related step of Appendix
F.3 to get
2
(k)
(b)
(k)) - (1 p()))) 2
(1 + ((0))
Umin
min r
4m/ (2)
(1+
(I(K)
-1) 132"
6 6611 + p(0) (5² + 2m (() 8s?
# (1 + p(k)
(k) (k)
2/3
(aft)))
2
1/3
4 r
(k) (k)
1 (1+ (k))
8²
(b)
1/3
1
1
7000
2/3
6 (52 2m
(k) 2m
8a) 1
(1+ (+()
2
p
(k) Note that in the process of minimizing Eq. 28 over 2 two out of the three dependencies on 7minn and two out of four dependencies on (k) were removed. Hence, we get
(R)
(k)
1 1 (k))
1
a (k)
min
2/3 / 1 + p(o) V 2
1/3
1 (1-)()) ((0)
2/3
1
(22
+ 21
(k)
p g2
(1+ (1+
28
46

---

Published as a conference paper at ICLR 2025
(k) Finally, we make remark that we do not minimize over Tmin here, as we take it given deter- (k) (k))
ministic value based on the choice of (k) 1 - 11/
Step 5: Obtaining p(((k)) We established p( (K)) < 1 in the previous steps. The last step is to
determine what p ((((k) is. We have
P (0()))
v +
4ac
(k) Pn
+ 022
+
V
P11 + 0
(
(k)
- 4
11
022
(N)
11 221
(k)
2a
2
(k)
+ 22
(k)
+ (ol1) (k) (k)
(ill
@222
2
+4012 Q21
(h) (K)
2 p(a) 1
1 + ( (I!N) -1) (²a(1)) + 1+ ++2+((
2 I-I-D(A) p(a) (a()))2 (52 23
1
1
2 mmin
(k) (R)
(1+1(+)) (I!+) - 1) (aa())
1 1+ p(R) 1()(k)
+2 2
11
1 + p(())
(c2 + (62+ 2,39) )
- -p(ie (a(tt)
3
1 - ((()
$²
(A) 1 + ((k)
--R(R) m (alh)) 2
(c2 + 21
(k) ((()) B2
1/2
+
1
3 + p(h)
(k) (k)
+ 3 1 + p(
Mmin
(1+17 (1+1(1)
(1)) (I!aa) -1) 8² 82a
(alt)) (52 + 2,89
4
2 1 p(k)
1 - g(k)
2 (k) (kk
(1+ (T - 1) B²ca
2
2
1
2
1 - pck} (a())) 2 (S2+
1 p(k)
+ 2,32)
(1+1%) 1+()))
B²
1- p(R) (a1))) 3 (s2 + 2mmm (())) ,32
+ p(k)
1/2
+ 12
1
1
3 3+ ((R)
A (k) (R)
+ B(() (a:t0))
4
1
1
p(()
2 (Al))(()) + BW (A (a(t))))) + (alk))))
+ 2
2
J.2
PROOF OF LEMMA I.4
(a)
Since (A))
(0)
we have
V1+4
(
(0))
k
(0 dx (0)
(
k
v 1 +
dr 1+
q=r
b
Based on the equation p( 1 (k) = (((( given Proposition
I.1 (k((a()) was given as
()) = 1- 0
+ Aa (k) (k) - B BB(a")) (a))))
4
1
1 (1-
2 (Aall)) + B(alt)))) + c((N))
2
2
47

---

Published as a conference paper at ICLR 2025
Further note that since we established 0 I p(((1)) < 1 in Proposition L1 it would mean 0 ((a(k)) S 1. Using triangle inequality, we have
M(a(k) 1 p Aa B B(al1))² - (211))201A00" (Aalt) + +B (((a(tt))))
-(AAalt)
vC (a!*)
3/2
2
2 2Aa
2
(0)
k-
(afr-1)) 2
1+ r-1
7
ΣS Lar h(a(1))
2k(k)
q= (1)
r=1
(a 2
14 _
2A(M)
(0
(V +
1+
a (0)
4
1+ 1+ m=1
(1 k 3 x1+5)
7
a (0)
1+
(A
(145)
+ #
1 +
(1 (1+2) dr
$ (00)
1
4k(k]
k 1
VI+
(1+?) (v1+ + k v1 =
Focusing only on the integral and defining u(x) = v 1 5. we have
1 + 7) dx
h-1 27 (1 + 11 du(x))
(v 1 + 1
u(x) (u(k) u(x))
1
1 + E
(7 + 1)
+ u(k) u(x)) du(x)
((k)
u(x))
11
u(k: - 1)
u(k) u(1)
+ In u(k)= u(k - 1)
u(k)
u(1)
2 1)
u(k 1) 1))(k)
2 11)
1
In u(k) u(k: -1) u(k)
ln + In
u(k)
w(k)
u[k 1)
1(7+1)
1
In
1 + ?
+ In
V1+
k x
1
+
7+k-1
Putting everything back together concludes the proof.
48

---

Published as a conference paper at ICLR 2025
J.3
PROOF OF THEOREM 1.5
First, using the fact that (b(k)| || get
S p p((((k)) -Il for each iteration 2 O, we can rewrite Eq. 8 to
Bgw [[(tt)) - 10
|0:00 1+
II 9=0
p (p(r)
Bgg
1 (k+1)
m 0(+++))11 [2]
|| (0)
1 010) ||
k
2(1 2(1-d manee
(1 + ua u) 82 ++++
II p (8(())
(a(r-11)²
aa (0)
(p(
3 12 + +o2
(29)
where the (k) matrix was written using Eq. 24
Next, in order to obtain Eq. 22 when k: + co, we need to simplify each of the three terms in Eq.
29
The easiest one to show the last term, i.e., (k)), Based Eq, 24 both of its entries v/(h) and 12 [k]
have factor (x) multiplied by value that can be upper-bounded by constant. Thus, we have
(1) 2
T2(++ua (0)
(1-d1)) max
8 + a2
Ha!
1 &
3 g + t
m
Regarding the first and the second term, i.e., IT pl (0101) and Ex= p( (a()))((((-11))) (a(r-1))² respectively, we have
k I
II (1 (1- ((a) s Eg=o h(alo)))
9=
9=0
{
Σ II p ( (B(())
(al--1)
II (1--Maal))) (a(--1))
(a((-1))2
g= h(ald))
in both of which Lemma 1.3 was used, since S ((((k))
< 1. Next, we employ Lemma I.4 on the O(Ink)
above expressions. The proof easily follows. Note that In
V
K DIMINISHING LEARNING RATE POLICY FOR NON-CONVEX MODELS
In this appendix, we do the convergence analysis of our methodology under a diminishing learning rate policy, i.e., when (k+1) < a (k) for all l 2 0. We will show that convergence to a stationary point with zero optimality error is possible if the frequency of SGDs, i.e., d(d), is increasing over time.
First, we rewrite the coefficients of and vs (K) with 1 S ú S 2, using the fact that the SGD probability is chosen d! 1 " (k)
(k).
Corollary K.1 (Average model performance and consensus error simplifications) (Corollary
Lemmas G.3 and G.4) Let Assumptions 4.2 4.3 and and hold. the SGD probabilities are chosen
as (k)
1/ (k) with < 1)
(k)
s (2) and V = minjeM then the quantities in
Lemma
simplify
(k) = (k) - (ma + 3(1 + miin (k))) (( = 2m (k) (1 and (k) [mmin (1 + (k)
11
+
30
2m
(1))
Similarly, the quantities in Lemmu G.4 also simplify
1 16 (()+
(k)
-i (2(
022
(k)
(t
2
1-
Jint 3 (a
1 (K)
and
2/2 m(16] (((())
(k)
| 82 + (a
1-
49

---

Published as a conference paper at ICLR 2025
Next, using the simplified results derived in Corollary K.1 we further simplify the results of Propo- sition G.6 to arrive at the following Proposition.
Proposition K.2 (Stationary point for non-convex models with diminishing learning rate) (See Appendix L. I for the proof.) Let Assumptions (.2 and 4.3 hold. If the SGD probabilities are
chosen as de 1 - mi
(k) (*) and a non-inet non-increasing learning rate is used, i.e. a (l++1) S ( then
the constraints on the learning rate given in Proposition G.6 are simplified to
((0)
(k) min
23 (T(K)
4, 43v1 pil)
(k) 7mmi + B 1 + 2 2
(R)
Mmann
(1
(1(())))
1 1 p(0)
4v2r V
CB / p(K)
where Manin minieM M/ (2) Consequently, for each iteration k 2 get the following bound on the expected aaverage model performance:
(k)
Egu [((((+1))]
F(B(O))
Σ of
(' E [| +
a (0) (0) - 1 0(0)
||
+ -r=
k-1
ar wiy (r) (r)
+ Σt 16(1)
in which wi (k) _
(T/ ) W2
(k)
8 (1-(4
and the values of (h and
ml1 (00)
2 were given in Corollary K.1
Note that the conditions laid out for the learning rate in Proposition K.2 have to be satisfied for all iterations 1: 2 O. As one last step, we outline the sufficient conditions under which we can derive a single constraint on the initial value of the learning rate.
Corollary K.3 (Constraint on diminishing learning rate initialization for non-convex models) (Corollary to Proposition K.2) If the learning rate ( is non-innneenn non-increasing, i.e., (k+11) (*)), the
SGD probubilities are determined as d( - (k) with 0 S тι- S बto and 1ymin = min T)s
for all 2 and we have constant aggregations probabilities b(h) bij. then the constraints in Proposition K.2 simplify to
(1- #2)
(0) < min
1-8 1 29 I7 43/147 To 5d + +3(1+ mm))) 4/2T1/1+T's
r3
1-2
CB vT+p Jr
This also results in time-invariant scalars A = (k), B = (M)) and C C((), where these quantities were defined in Proposition K.2
With Corollary K.3 we have most of the ingredients required to prove the main Theorem. We will just need two extra upper bounds on summations involving the learning rate, as presented in the next Lemma.
Lemma K.4 (Bounds for powers of learning rate sums) (See Appendix for the proof.) Let diminishing learning rate (#) (0) //1 + 1e/7 be used, which satisfies the properties in Eq. 2/ Under the setup of Proposition K.2 for the SGD probabilities, i.e., d(h)) if the aggregation proba-
bilities are constant, ie.. ((h)) biy for all i e M and (i. g(k), then the following bounds hold
(a) Db
(al0))² s (a(0)) 2 (1 + +k/)))
(b) Eier (al0)) - (a(0)) (1+27).
50

---

Published as a conference paper at ICLR 2025
Theorem K.S (Non-convex convergence result with diminishing learning rate) (See Ap-
pendix L.3 for the proof.) Let Assumptions (42 4.3 and 4.4 hold. If a diminishing learning rate
policy al R / k/7 with y 0 satisfying the conditions outlined in Corollary K.3 is employed, and the SGD probabilities are set to d!!t)
((1 - )alh) for all M. while aggregation probabilities are set to constant values, i.e., b2g bij for all i M and (1,5) E (k), then we have
F(O(O) - F.
2 Eg
(1-1
VF(O6>))|
0
Er= ((r)
2w1
al0)
VK
==
(0) (0) Indio/p
+ W2tlig (al01)
1
W12
(1 + 27) O
(30)
VK
VK
In K
W4a (0)
1 70
in which F+ mineeg" F()), and the values of scalars w, with s S given in Ap- pendix H.7 On letting + oo, we obtain
lim
Σ r=0
E
IIF(OM) O.
(31)
0 atr)
Eq. 30
Theorem K.5 illustrates the convergence rate that be achieved when diminishing
learning rate policy used train non-convex models. We recover the well-known OIn K/ KK) rate for DGD methods here. Furthermore, letting K + oo in Eq. 30 we observe in Eq. 31 that the stationarity gap becomes zero.
L PROOFS FOR DIMINISHING LEARNING RATE POLICY FOR NON-CONVEX MODELS
L.1 PROOF OF PROPOSITION K.2
Considering the fact that the learning rate is diminishing, we can simplify the learning rate con- straints in Proposition G.6 Using the updated coefficients derived in Corollary K.1 we rewrite the constraints from Appendix G.5 and Step 3 in Appendix H. get
ii)
1 - p(K)
(k) 22
(k))
<
1
4 1 + P68J.
((K)
a (k)
<
( >
(k)
4 4 / + pIk)
1 1 p(k)
02
2
1
(T
(k) 2
(R)
> 0
(k)
1/4
+ 31 + 2 )
1
a (1)
2
7
r
[
(k)
+ 3(1 +
Mmin
(K)
>
1
(1))
2
2
51

---

Published as a conference paper at ICLR 2025
(iii)
(()
(k)
r > 0
2,3
12 2m
(k)
g
(1 +
1)
(a(
2
Miin (1 + r )0 +
)0²
_Bo 2m
(a(t)) 2
(iv)
(k) (b)
(K)
P21 01 >0 0
111
(K)
16(1 ((u) x2 (a ) 33 + +r/
1
1
1
a (R)
> 0
2
[ [k)
(1 - 2(o) ?
1
1
(198))
(1 (1- 13
(1 ( 2 (1-p(h)
(k) <
4v2v1 1 p
1 1 1/
)
(1 (1-
((a))
(k) <
r(k)
4 > 1
(k)
4v
1 +
piki
CBV
+ (
(k)
21
(k)
(R)
1
1
(1
1
a(k)
1
22
(K)
2
r
(r(33))
2
Putting together all of these constraints concludes the proof.
L.2
PROOF OF LEMMA K.4 4
a
2 s (a000)) 2 + (alet) dx do=d=(oo (al11)² + /" (alo)) dx
(a()))
1 1+ x/7
= = + (a/0))
2
7In + k/7) = (a)00) ) 2 (1 (1+ In 71 711(1++k/))
(1++k/)))) k/7)).
b
k
(atti) - (a(0)) + i (afo)) 3
(a((at))) dx = (aa10) + %/² *k (a 3
(1 + 21/1) 3/2 de
0=
= (al))) 2 (a)))) 3
(111 v1+ (1-v S (a(0) 3
1
7
(1 (7)
L.3 PROOF OF THEOREM K.5
For each iteration k 2 0. (i) the learning rate being diminishing, (ii) the fact that d( 1 - ((1
) //100)/00)))))))/))) 10) (k) and (iii) (/4)) bi which results in p(t)) م. results in Proposition K.2 implying
k
E B F(orktD)) < F()))) wi
|
+ (0) w2
e (0)
1 σ
k-
(r)
+ W2
+
$1
0=
0=0
52

---

Published as a conference paper at ICLR 2025
(k) Substituting the values of 1/( and 222
from Corollary K.1
then rearranging the inequality and
dividing it by Σ ar1), we get
1
B E Bg
VF(00>)1
F(B(O))
F
Σx=0 alr)
w1 Σ r= alrr)
r=0
h (a(r)) 2
102 +
(0) 1m)
(r())
W4
in which w1
= )/1 -2- (Ta)*)
w2
m(1-p)(
(14T')
W3
m116 o²) and
1-4
mua (1 + +3)302 + 3o² ((
W1
2m
Finally, using Lemmas I.4 (a)
and
K.4
we conclude that
E
V
F(BlO)) - F
Er=o ((r)
200)
W11 - -1)
+ t w
1000
1m 1m0
wwwws (ww (1+27)++ + ws ((+r)((((k)))/
M NON-CONVEX ANALYSIS UNDER THE PL CONDITION
In this appendix, we make the convergence analysis of our developed framework when non-convex ML models satisfying the PL condition are employed. Our approach will be quite similar to Sec. with the key difference that we will use the milder Polyak-Lojasiewicz (PL) condition (Xin et al.
2021 (Assumption M.T) instead of strong convexity (Assumption 4.1 (b) to make this generaliza- tion.
Assumption M.1 (PL. inequality) The global loss function F meets the PL condiiioo ||)()) > 2μ (F(0) - F*) with some μ > 0, where F is the optimal value of F.
Under this assumption, we further know that F satisfies the quadratic growth condition (QG- condition) ||0 1²1 < (2/)))F((0 F*). where 8 is the nearest point to the optimal solution of the minimization problem under consideration. This will also be useful in our analysis.
We will still characterize the expected consensus error || (R++1) ( but con- trary to what was done in Sec. 4 the distance of the average model from the optimal solution will
be captured via [ [F(((++)) - F*). As an alternative to Lemma 4.7 we first provide an upper bound on the expected error in the average model at each iteration for the non-convex case, i.e., Egos ((((++1))- - F*], in Lemma M.3 Then, as alternative to Lemma 4.8 we also calculate an
upper bound on the consensus error for non-convex models, i.e., Ego | (k+1) 1 0(++1) [2] in Corollary M.4
We first need a preliminary Lemma which will be useful in the proof of Lemma M.
Lemma M.2 (Gradient bounds under the PL condition) (See Appendix N.I for the proof.) Let (a) 4.1 (c) and M. Thold. The following upper bounds related to the gradient of
Assumptions 4.1
the global loss function can be obtained in terms of the optimality error Egu- 1) (F((k))) - Fnd
and
the consensus error [y - 11,
(a) E
|1| (F())) V. (k) 2
4
(1
d (K)
min E --
(F(O(K)) Eg =F*] +
P
p((4)
E () (k) 1()
0(k) 11
(B) )
(b) -
E (V (((+)) Vo )3 5 -u(1
28a (1
(k) B (F((())) F+] +
a
g2((e
B 1) (k) , [+t) 13 + (1 (() )22
2m
53

---

Published as a conference paper at ICLR 2025
(c) 3
Ve 10 |11
2 5
(3
2d
1 Fr] +
P
1) ||
1. ((k)
[|] 2(1
(min )52
Now can continue with the key lemma and corollary.
Lemma M.3 (Average error for non-convex models satisfying the PL condition) (See Ap-
pendix N.2 for the proof.) Let Assumptions 4.1 [a) 4.1 cc) and M. hold. For each iteration
2 O, we have the following bound on the expected average model error
E E (F(0(N+1)) F*] (k) E Eg (F((())
F*] + @12 E g [||@ 1,, 1110)
(k)
where (111 -1 + 28 (3 2d (k) (a(t))) - 20
1 (1 d )) 012
gd 2m
a (k) (1 +
f
(3 and
w1th (k))
((h) min) )8² (k)) (a))))(((1)))
d(bb min
)8²
+
dmaxo² m
Similar to our discussion around Lemma 4.7 note again how the coefficients simplify when (k)
1, which is essentially equivalent to the conventional DFL setup where clients perform SGDs at every iteration, i.e.,
for all i E M.
We next bound the consensus error at each iteration, i... Egas (k+1) - 1m 11 which measures the deviation of ML model parameters of clients from the average non-convex ML model.
Corollary M.4 (Consensus error for non-convex models satistying the PL condition)
(Corollary to Lemma 4.8) Let Assumptions 4.1 (a) 4.1(c) 4.3 4.4 and M.] hold. For each
iteration is 2 we have the following bound on the expected consensus error
Eg || (k+1) - 1m
2 Bgn- (F(())(((())) - +0 Bg 11|@ - 00k 1+
2
where 221
p 1-p midiix (a (S2 (1
6 1+
(k)
22
(k) 1+p(a)
+ +3 1-p(y) piny
d
(a (2)) )² (52 + 2,3), and 1/2 = ( dd 1+
82 + o?) 1-
2
Proof. Lemma 4.8 states that Eg (1+11) - 1(k+
(k)
E 1g [|] 0r 1²1
S 21
O2 E () [|| (k) 1()) 11 1/2 Now, using the PL condition (Assumption M. we know
that (10(k) - 1-1 (T((()) - F*). Hence, we get Φ21
(k) + 1 2
Corollary M.4 is almost the same as Lemma with the only difference being in Ø2 Note again
that 2 0 in the conventional DFL setup, where (a) Ç 0 and (b) d(i) 1, resulting d!
for all E M.
Let us denote the error vector at iteration & with une
(R) defined as
E3 Eg (0 F=
Eg ( m Ø(k)
(32)
With this definition, putting the results of Lemmas 4.7 and 4.8 system inequalities:
together form the following linear
Putting the results of Lemma inequalities:
M.3 and Corollary M.4 together form the following linear system of
(k+1) < (k) (k)
+ (4)
(33)
with (k) = [0b 151,5<2 and (A) = lo 2y ( Recursively expanding the inequalities in
(k)
Eq. 33 gives an explicit relationship between the expected model enror and consensus error at each iteration and their initial values:
U nd
(k+1) < (1:0) (k)
+
Σ
s (kar) (p (r-1) (p)
(34)
54

---

Published as a conference paper at ICLR 2025
where we have defined (k:ss) o ((k-))))...))))
((() for k > and @ $
In order for us formalize the convergence bound of DSpodFL, we have to show that the spectral radius of matrix (*) given in Eq. 33 is less than one, i.e., p ( < This part was outlined in
Proposition M.5 in the main text.
Proposition M.5 (Spectral radius under the PL condition) (See Appendix N.3 for the proof.) Let M. hold. If the learning rate satisfies the following
Assumptions 4.1 a
4.1
c
4.4 and
condition for all
k
2g
(1
dmin)
112
5 (11 + p(())
a (k)
min
10
(3 2d(nin)) )
33.
8p
2 2²
((bb)
2
d(t))
1
p(ck)
min
by 20
V p(0)
1
2ga
(k)
then have p( for all k O. in which p(-) denotes the spectral radius of given matrix, and ((k) is the linear system of inequalities of governing the dynamics of optimal-
ity and consensus errors. p( follows as (( = 3+ aa) + ((k)) (a(k)) +
(1- 2(A(()) + (a() (a( where A = 2y (1 (1- 20a
2² (1 (2h) )),
(A)) 3 1+g(0)) T- (5² + 2,32) and ((k) 72 (k)
"c2 2 d
5h
T- piyy
Proposition M.5 enables us to guarantee convergence of DSpodFL, when non-convex models are
used. The argument follows along the lines of the things we discussed in Sec. 4.4 Proposition M.5
implies that lim; (A:0) = 0 in Eq. 34 However, this is only the asymptotic behavior of $ (A:0)) and the exact convergence rate will depend on the choice of the learning rate (*(), Furthermore,
since the first expression in Eq. asymptotically approaches zero, Proposition
M.5 also implies
that the non-negative optimality gap is determined by the terms Σ Φ (brr) (p
(k) and
can be either zero or a positive value depending on the choice of (A))
Proposition M.5 outlines the necessary constraint on the learning rate (k) at each iteration 2 0.
We next provide a corollary to Proposition M.5 in which we show that under certain conditions, the above-mentioned constraint needs to be satisfied only on the initial value of the learning rate, i.e, (0)
Corollary M.6 (Constraint on learning rate initialization under the PL condition) (Corollary to Proposition M. If the learning rate (N) is non-incredn non-increasing and the probabilities of SGDs (h)
(k) and aggregations by are constant, i.e., a (k-1) (k), d!Ah) di Dig bij, for all k 2 0, and have then the constraints in Proposition M.5 simplify to
22a
1
(1 dmii))
12
(0) min
10 (3 -2dmin)
B3
8/l
1
202 n22
(1 dmin))
1-
122 - 2 (1
dmin))
6 2d
32 V
+²+ 2,32 (1 - dmin)
Theorem M.7 (Non-convex result under the PL condition) (Proof is similar to the proof of The- (F4) Let Assumptions (. (a) (c) an3|4.3] 4.4 M. hold. Let
orem 4.17 given in Appendix (:4)
a constant learning rate (k) a with a > 0 satisfying the conditions of Proposition M.5 be employed, and the probabilities of SGDs and aggregations be time-invariant, i.e., d.hh d, and
(1k) bij, for all 2 O. Then, the convergence rate is geometric, specifically K+1 with an optimality gap
55

---

Published as a conference paper at ICLR 2025
1 (1 .8
duan )02
2 41 dmiu) 02+ +
o²
lim K0000
Un
(1-1))
m
(35)
A
ma 3 (3 + 0²)
for 2 given in Lemma M.3 and Corollary M.4 and Vnc defined in Eq. p(
32
Proposition M.S
ensures
We that the optimality gap in Eq. 35 be decreased by choosing smaller learning a and a larger minimum SGD probability dmin- similar to the argument made for Theorem 4.11
N PROOFS FOR NON-CONVEX ANALYSIS UNDER THE PL CONDITION
N.1 PROOF OF LEMMA M.2
a For this deviation term, we have
V - Vo 1
VF((O())) v0,105
==1
(O(A)) )o )o(
m
(F((O(())
)F((O!+)) ||
V FF,(0 (o(it)))
m
m
0
m
3
Ø(k)
8!{01 12
+
2
m
B7 g(k) 0012 +
m
171
=1
=D
g(h) 0(00
(1)
(K)
2 m
m
2,8
F(O())
FT)) 0 (1- (
where in the last two lines, (i) Smoothness (Assumption 4.1 (a) and Lemma D.I (b) and (ii) PL con- dition (Assumption M.I) was used, respectively. Taking the expected value of the above inequality concludes the proof.
(b) Second, for this inner product term, we have
(VF(O())
Ve (1)
VF(O())
(R) VF(O(H) VE(O()))
VE(OMA)))
+ (VE(O(A)) VF(0(()) - ())
(F((
+ VF( Fo
$ 2
56

---

Published as a conference paper at ICLR 2025
Now, taking the expected value of this inequality and using part (a) of this lemma alongside the PL condition (Assumption M.I). we get
- Eg s VFF(B()),
) - -B
[(((C)))
F*
B² di
|10(0) 1m 0(k) |3]
Bg((-1)
2m
+ 2,32
(1 duh
Eg(- F((BCi)) - -F*)
+ 1 dmin)
8²
I -H (1
232 (1-d!")
+ B d
|0 1 -m 19]
(m))
Eg(--1)
F(((()) Fr
122 k) VF( + VF( V
2m
+ (1
(k)
0².
min
Finally, for the norm term, we have
(1)
|| < VF ||
- 1
2
Taking the expected value of this inequality and utilizing part (a) of this lemma alongside the PL condition (Assumption p.I]]
E 2
Vo
21
2 11
E g 1)
[(((()))
- F.]
Pdln
| 1 0(A) ||2)
())
11
m
4B2
(1-d
d(ti
1g(t-1) (((((A)) Fr* + (1 d 6²
+
1
2B²
Egi 1) F(((())) - F+ + 32 (1t)
||0m0) 1m Ø(k)
19]
<
(3-
(x(
min
Egi
1
m
(b) min
8²
N.2 PROOF OF LEMMA M.3
Using Lemma D.1 1 b on Ō(4), the average model parameters at iteration k, and then employing
Assumption M. we get
||2 s 38810 (00) 0-1|²= s
2,32
H (F(OLH) FT))
Now, we can write
F(g(k+1)) F" S F( + (VF(O(H)) g(++1) g(h))
((()) giu+t))?? F
2
= (VE(T(+)) (a (1))) (A)
+ (k) (b)))) 1 pr
= =(((()) - E² ( (Vr() ), Vo (1)
(1))
(VF(T())), ),
( (x))) 2
Vo (1) 2
(k)
+
2
2
+ 8
(k) (a
2
(
in which the relationship in each of the three lines follow from (i) Smoothness (Assumption 4.1 (a)
(ii) Eq. (iii) g(" = ((( + (k) for all E .M. Next, we take the expected value of the above
inequality and use Assumption 4.3 and Lemmas D.2 and M.2 to get
57

---

Published as a conference paper at ICLR 2025
Bg(+)
[(((kt)))
- F+ 2 (g((-1) F(((h)) - -F
-alkk)
1- 2.32
(1
(1-d)
(1k)
Bg(-1)) [(((())) - F+]
1e
miu
B Bddnndx
a (A) Bg(t-1) |00 - 1m 1m0w 19 + + (1-d 82
d
+
2m
2
3 - (0
2 (altt)
B F(((kt) - rt]
+
11
B8 Bdnnax
(k)
2
E E
|0(0) | -1 -1n0 23 (1- d 8² (aa(1)))
m
2 (k)
σ²
a (R)
+
max
m
+ 2,33
33 - 2d )
(a!1))
- -ua (h) (1 (1- ( (mi))) ) Bgit (F(0())) F+
23²
1²2
1
82 d
Fzu-1)) |1 - 1m 1000119 = (k) (1- (8) 6²
(k)
(1+230
+ 230 (8)
2m
(
(a()t)
2
4 (111 d 8² + dmaxxo2
+
2
N.3 PROOF OF PROPOSITION M.5
We will do an analysis similar to the proof of Propositions 4.10 and I.1 which were given in Ap-
pendices F3 and respectively.
Step 1: Setting up the proof. We skip repeating the explanations for this step, as they are exactly the same as step I in Appendix F3
Step 2: Simplifying the conditions. Recall that we have to ensure (i) 0 < o11 < and (ii)
0
22
(k)
< 1. For o!! defined in Lemma M.3 we have
1
(1
20a (k)
1
I11 < 1 +
(k) <
n
min
(k) min
112
233 3
2d
2,32
We can see that we got a requirement for d(b) here, and should be lower bounded. Therefore, contrary to when strongly convex models were being used that d(a) could have had any value for all
i E M and & 2 0, when using a non-convex model this is no longer the case, and (( have to be 2²
larger than a threshold 1
To put this into better context, note that 1
23 2. and thus
2zz-
the best possible scenario we can allow d > 2
We then put the following constraint on (k) to get more compact form for (()) defined in Lemma M.3
We have
23a Constraint 1: (k) S T 2 (1-
(1 at (AA))
n²²
0 < (R) <1,
233 (3 (d)
Note that although the above constraint has to satisfied for (1),, we also obtain an upper bound for the condition for theoretical analysis purposes. We have
422
I
(k) <
(k)
<
233
2,3
58

---

Published as a conference paper at ICLR 2025
Hence, we can update &11 and (k)
P12 as defined in Lemma M.3 as the follows
ol S 1 - (1- (1 2.3²
112 (1 (1-d dlin) )) pa (k)
(R) 12
Pdiaax
(1+14 (h))
2m
Note that other entries of matrices (k) and (p((k) remain the same as initially given in Lemma M.3 and Corollary M4 Moreover, since matrix ((k) and vector (e) in Eq. 33 were used upper bounds, therefore we can always replace their values with new upper bounds for them. Conse-
quently, with this new value for P11 we continue as
111 >0
(8)
((k)
(1
2
1
d
Finally, we check the next condition 0 <
922
(K)
S 1. Noting that we have 3+
< 1, we can enforce
22
(k)
S 1 by setting (k)
022 < 3+
We have
1
+ (k)
3 + plk)
- p(k)
(k)
0 S (k) 2
22
< 4
2
2 3d
v1+ + p(k)
V + 2,3
Step Determining the constraints. Having made sure that (i) < (AA) I and (ii) 0 < 2ي S
in the previous step, we can continue to solve Eq. 15 For the left-hand side of the inequality, we have
2,32
(1 (1-01 (1 622
p()))
1
(1
min
maa
1
222
(k)
112
(1
2,32
p (k)
(()))
)
(1
2
2²2
4
Now, putting this back to Eq.
15
we get
(1 (1-1(²)) (1
2,32
(1-di) (1-d )) ka)
1- pp(
(k)
222
4
1112
211
B (b)
(1+ (++r()) (k2) (a)
1 1 pi(k) md (K)
6 1 + p(()
(altt)
2 ((2 + 282 (1- dua
2m
max
[1 (1-1773) (1-
2132
(1
μa (R)
1 p(k)
42
4
((k) - ((()) 1
2.9
(b) <
vsa
2 2v 3d
1
/1 + piA) 3C
+
233
d
mii
(k)
Finally, we solve for Eq.
16
i.e., c =
11 22
(k)
11 22
(k)
(k)
> O. Noting that by solving Eq.
15 we
made sure that 011
(k)
d22
k))
(k)
022
(k)
11 221
(k) (K)
0, we can write
(k)
c>0 0
+
P11 + 00
> 0
1 1-
(1-14)
1 1- 114)) ) (1-
2,32
1
min)
(k)
pa (k)
1 ((K)
>>>
2
2
+ ((k)
(2)
2/1 1 1
(1-m(()) p(()))
202
(1
(b) min
in which we have used the value of ((() itself, but the lower bound of (122
59

---

Published as a conference paper at ICLR 2025
Step 4: Putting all the constraints together. Reviewing all the constraints (*)) from the beginning of this appendix, we can collect all of the constraints together and simplify them as
(ak) min T 4² (1
20a (1
(1
2²
2
3 200
1 (1 r(b))
(1-22
20a x²a
1 d
))
1
p(k))
2 (K)
v 1 + p(k)
2 + 2,52
1 (x))]
1 k(k) μ
1
2
1
min
4²
2 3ddu
1 11 (k)
VI + p(ki
3C
+
2
1
min
(k)
1 + p()))
(36)
1 m(())
2,82
(k) min
2/1
((()) R2
(1-
20a n
1
(b)
1 + (((
min
2,33
3 2d)
2/0
(1
r (k)
1
(1
2.8
1
d (k)
min
1 p(k)
v + p(R)
V 2,82
2 3d
1 2 /dd (k)
1- I(( 1-
1 1- p(R) P
2 n²2
1 (k)
(k) v1 + ((k) 3C
1 +
29a x
1
min
(k)
while satisfying
0 < 1 1
36 was trivially removed since (+ 2
Note that of the terms in Eq. last two terms, we have
< 1. Furthermore, for the
((K)
- p(k) 1
(a)
2 3d
v + p(0)
VC2 + 2,5
2 3d
v1 + p(R) V6
1 --1(()) 1 1 ((k) 4
2
of (k)
n12
min
(b)
2 (r())
(() V1 + p(k)
BC
1 +
23²
(k) d dnin
1
1
(lk)
(k)
2 dd)
V1+ + p(k)
<V d
1 1
We found a lower bound for (a), and an upper bound for (b). Since the constraint on (k) includes the minimum of these two terms, showing that the upper bound for (b) is less than the lower bound for (a), will constitute the fact that the (b) < (a). We have
(()
d2
1
5 d
5
((A)
6
ri
(k)
6.9
1
63
Therefore, choosing (4) = ri will give us tightest possible bounds. However, in order to get simpler expressions for the first two terms in Eq. 36 which would give us better intuition, we choose
60

---

Published as a conference paper at ICLR 2025
the infimum of ( for them, i.e., 1/5, obtain
122 (1-
2 (1 (())
a (k) < min
n=
5
1 + p(()
1033 (3 2d
4 2μ
1
2
1
mmn
1sa
7(kk)
1
2g2
1
6/ 2d
1 + p())
1 +
20a ç²
1
(k) min
Step 5: Obtaining (()b()). We established p( (b)) < 1 in the previous steps. The last step is to determine what p ( (k)) is. We have
111 + 22 + (011 + +022
(k)
(e)
(k)
2 - (1
(K)
(k) (k)
o( (B(())
-b+ + 12
4ac
022 - 12
2a
2
Q11
P22
(k)
+
P11 022
(k)
40
(k) (k)
P21
-
(1 (1- -1-)
(1-
2ga
1 (()))
(ace(h)
+ 1+p(h)
+
+3
(a(t))
(52 + 2,32
a
2
1-pinj
2
1
1- 1- -11- (1-1
)1) (1
2,32
(1-
)ma(th)
+ p(K)
min
2
112
2
2
1 + p(k)
- p(k) (ali)) (ale))(((2
(s2 +
232) ((E+)9P)
ma( max (a(*))² (s2 + 2,3² (1- )) 1/2
82 dmax
(1 (1)) (k) 6 1 + ()(h)
2m
11 p(ae
+ g(k)
1
1 - r(,)) (1
2,32
(1 ( mac mc((h)
31 + p(A)
2 1 piaj (altt) (c2 + 2,8²)
4
2
112
1 - g(k)
(1 (())) (1
2,32
122 (1
( wc) (b)
+
2
2
+ p(h)
(a(h)) 2 ((2 + +222)
- pik)
(a(t)) )² (52 + 2,32 (1- d( 1) 1/2
12,32
(1+141))
1 ((N)
4
1 p(k)
3+ ((K)
A (1)) a (A)
+ B((k) (a(
4
1
1 p(k)
2 (AWW))( + B(() BB
(a(t))))) 2 + (al())
+ 2/
O FURTHER EXPERIMENTS
0.1 ACCURACY VS. DELAY WITH UNIFORM DISTRIBUTION
In the experiments we provided in Fig. 2 the SGD and aggregation probabilities were sampled from Beta distribution, e.g., d(²) .b3 Beta(a, 3). In this section, we investigate sampling these probabilities from the uniform distribution, denoted as (() 1).
61

---

Published as a conference paper at ICLR 2025
DFedAvg
DGD
DSpodFL (Ours)
RG
Sporadic SGDs
0.8
0.6
0.6
accuracy
accuracy
0.4
0.4
0.2
0.2
0.0
0
5000
10000
10000 overall delay T
20000
overall delay т
(a) FMNIST, Non-IID.
(b) CIFARIO, 10, Non-III..
Figure 5: Accuracy vs. latency plots obtained in different setups where the SGD and aggregation probabilities are sampled from the uniform distribution (0, 1]. DSpodFL achieves the target accu- racy much faster with less delay, emphasizing the benefit of sporadicity in DFL for SGD iterations and model aggregations simultaneously.
DFedAvg
DSpodFL (Ours)
Sporadic 5GDs
acc. after = 500
acc afteer 500
0.5
509
0.4
0.4
0.4
acc after
0.3
0.2
0.2
0.2
0.1
number labels
radius of RGG
number clients
(a) Varying number of labels per client.
(b) Varying the radius of the ran- dom geometric network graph.
(c) Varying the number of clients m in the network.
Figure 6: Effects of system parameters on FMNIST, where client and link capabilities d, and bij. sampled from a Beta distribution Beta(0.5, 0.5). The overall results confirm the advantage of DSpodFL in various settings.
We have provided experimental results for only the non-llI cases in Fig. []] under exactly the same setup outlined in Sec. 5 It can be observed that the findings discussed in Sec. [ also hold here. In other words, our DSpodFL. method outperforms the baselines in terms of accuracy per overall delay.
We will explain the intuitive reason of why DSpodFL is outperforming other baselines in both Figs. [ and 5 Let G = (M,E) E) be given network graph, and assume there exits two paths between nodes and J. Let one of these paths have a communication cost & times more than the other path, where k > 1. In our DSpodFL method, the path with lower cost will be utilized roughly times more than the other path, thus resulting lower communication overhead while still preserving information flow between nodes and j. Meanwhile, other methods, especially DGD and DFedAvg methods, do not take this into account.
O.2 EFFECTS OF SYSTEM PARAMETERS WITH BETA DISTRIBUTION
In the experiments we provided in Fig. specifically Figs. 3a
3b and 3c
the SGD and aggregation u(0, 1]. In this section,
probabilities were sampled from uniform distribution, e.g., investigate sampling these probabilities from the Beta distribution, denoted Beta(0.5, 0.5).
62

---

Published as a conference paper at ICLR 2025
DFedAvg
DGD
DSpodFL (Ours)
RG
Sporadic 5GDs
acc. after -500
0.6
after 5000
0.6
acc after r= 5000
0.5
0.4
0.4
0.2
0.3
10
10
labels
graph connectivity
clients
(a) Varying number of labels per (b) Varying the radius of the ran- client.
(c) Varying the number of clients m in the network.
dom geometric network graph.
Figure Effects of system parameters on CIFARIO. In figures, client and link capabilities and by are sampled from Beta distribution Bcta(0.8, 0.8). The overall results confirm the advantage of DSpodFL. various settings.
DFedAvg
DGD
DSpodFL (Ours)
RG
Sporadic SGDs
0-0
ovenal
overall
(a) FMNIST, IID.
(b) FMNIST, Non-IID.
(c) CIFARIO, IID. (d) CIFARIO, Non-IID.
Figure 8: Accuracy vs. latency plots when SGD and aggregation probabilities are time-varying. DSpodFL achieves the target accuracy much faster with less delay, emphasizing the benefit of sporadicity DFL for SGD iterations and model aggregations simultaneously.
We have provided experimental results for only the non-lID cases in Fig. under exactly the same setup outlined in It can be observed that the findings discussed in Sec. also hold here. In other words, the performance gain of our DSpodFL method compared to the baselines is robust regardless of the variation in system parameters, i.e, (i) data heterogeneity level, (ii) level of graph connectivity level and (iii) number of clients in the system.
O.3 EFFECTS OF SYSTEM PARAMETERS ON CIFARIO
In both Sections 5 and O.2 analyzed the effects of system parameters the FMNIST dataset. Here, we will provide similar experimental results for the CIFARIO dataset. Note that while an SVM model
the VGG11 model. We sample the SGD and aggregation probabilities from the Beta distribution, i.e., a(()) Beta(0.8, 0.8) and ((() (0.8, 0.8), respectively.
trained the FMNIST dataset, for CIFARIO
The results in Fig. are carried out the non-lll) regime as well, under the setup described in Sec.5) Again, the findings discussed in Sec. (ladd can be validated here, showing that DSpodFL outperforms the state-of-the-art
various settings. This demonstrates that our results hold regardless of the dataset in question and the ML model being used, adding yet another dimension of robustness to our methodology.
O.4 DYNAMIC SGD AND AGGREGATION PROBABILITIES
In the experiments done in Sec. 5 the SGD and aggregations probabilities where set constant values for clients, i.e., (k d, and (k) by, for all 2 0. In this section, we conduct exper- iments by letting these probabilities be time-varying. This setup corresponds situations where the computation/commuiicaiii
resources of clients vary over time. To be specific, we change prob- abilities (a))) and (1) every 1000 iterations of model training. However, that still randomly
63

---

Published as a conference paper at ICLR 2025
IID
Non-III
Algorithm
Iter. 1000
Iter. 2500
Iter. 3500
Iter. 5000
Iter. 10000
Iter. 15000
DGD
0.80
0.81
0.82
0.72
0.73
0.75
DFedAvg
0.79
0.81
0.81
0.39
0.41
0.41
RG
0.80
0.82
0.82
0.60
0.65
0.64
Sporadic SGDs
0.77
0.80
0.80
0.70
0.74
0.74
DSPodFL
0.77
0.80
0.80
0.63
0.67
0.70
Table 2: Accuracy vs. iteration results for experiments in Fig.
done for the FMNIST dataset.
IID
Non-IID Iter. 6000
Algorithm
Iter. 1500
Iter. 3000
Iter. 4500
Iter. 3000
Iter. 9500
DGD
0.73
0.73
0.74
0.77
0.80
0.81
DFedAvg
0.73
0.74
0.75
0.56
0.70
0.76
RG
0.72
0.74
0.74
0.73
0.80
0.80
Sporadic SGDs
0.74
0.74
0.75
0.71
0.76
0.79
DSpodFL
0.72
0.73
0.73
0.65
0.72
0.76
Table 3: Accuracy iteration results for experiments in Fig, done for the CIFAR10 dataset.
sample them from the same distribution, i.e., Beta 0.5) for FMNIST and Beta (0.8, 0.8) for CIFAR1O.
It can be observed that the findings discussed in Sec. also hold here. In other words, our DSpodFL, method outperforms the baselines terms of accuracy per overall delay regardless of time- variation in SGD and aggregation probabilities.
0.5 ACCURACY VS. ITERATION
We have provided the accuracy vs. iteration results for the experiments done in Fig. In Tables and 3
we give the results for several sampled iterations.
We observe that given enough time, i.c., after sufficient epochs, the achievable accuracy for DSpodFL matches the achievable accuracy for the other baselines. The accuracy for DSpodFL being slightly lower than DGD at some iterations is due to the fact that gradient and consensus op- erations occur at every iteration for all devices DGD, without taking resource availability into account. In DSpodFL, on the other hand, at each iteration some devices do not compute gradients and/or some of the links are not utilized for communications, Thus, not unexpected for accuracy of DSpodFI L to be lower than DGD across the iterations, since it is actually designed to achieve faster convergence in terms the actual physical delay incurred as seen Fig. 2 Regard- less, the final achievable accuracy is the same for all baselines, they all fit within the DSpodFL, framework, and we theoretically prove the paper that all these algorithms will converge to the same global MI. model.
O.6 DECOMPOSING ACCURACY VS. DELAY RESULTS
In Tables 4 and 5 have decomposed the results from Fig. into their processing and transmis- sion delay components. We have reported how long it takes for different algorithms to achieve a specific accuracy in terms of 1) processing delay, 2) transmission delay and 3) overall delay. We can see that to reach a certain accuracy, DSpodFL strikes the best balance between transmission and processing delays, leading to better overall delay. Specifically, it obtains similar processing delay to the Sporadic SGDs algorithm and transmission delay to RG, which are the best baselines in those respective categories. Note that the reported delays below are in units of time.
O.7 RESULTS WITH TRUNCATED GAUSSIAN DISTRIBUTION
In Fig. we have further explored the performance of DSpodFL under truncated Gaussian distri- bution Nj (u, to generate probabilities d, and bij. which for small values of variance o² gives
64

---

Published as a conference paper at ICLR 2025
IID, with aceuracy
0.75
Non-IID, with accuracy 0.40
Algorithm
Process.
Transm.
Overall
Process.
Transm.
Overall
DGD
4605.26
1915.95
6521 .22
2470.37
1027.76
3498.14 14
DFedAvg
5947.19
88.82
6036.01
221418.66
3070.60
224489.26
RG
6130.19
331.40
6461.58
9180.18
451.15
9631.18
Sporadic SGDs
591.84
7614.84
8206.68
127.38
1270.18
1397.56
DSpodFL
593.69
893.32
1487.00
257.68
430.96
688.65
Table 4:
Decomposition accuracy vs. delay results in Fig. for the FMNIST dataset into their processing transmission delay components.
IID, with accuracy =
0.65
Non-IID, with accuracy = 0.30
Algorithm
Process.
Transm.
Overall
Process.
Transm.
Overall
DGD DFedAvg
3462.06
2571.64
6033.70
2250.12
8807.37
11057.49
2784.81
482.01
3266.83
9627.35
2065.34
11692.70
RG
3462.06
614.68
4076.74
2250.12
161.15
2411.27
Sporadic SGDs
440.73
2888. 25
3328.98
160.13
13081.37
13241.50
DSpodFL
628.97
990.24
1619.21
327.27
647.24
974.51
Table 5: Decomposition of accuracy vs. delay results Fig. for the CIFAR10 dataset into their processing transmission delay components.
the setting of relatively homogeneous and static clients. Fig. 9a demonstrates accuracy vs. latency when using this distribution with a mean and standard deviation 0.5, and Fig. pbl shows result for different o², We see wider margin of improvement with a relatively larger o². This confirms that DSpodFL is most advantageous relative to the baselines under extreme levels of heterogeneity and dynamics, similar to how the improvements under the inverted bell-shaper beta distribution are more pronounced than those under the uniform distribution as seen in Fig. 3d We have also ex- perimented with fixing the variance of the truncated Gaussian distribution and varying its mean in Fig. 9c
O.8 FURTHER GENERALIZATION AND SCALABILITY VERIFICATION
In Fig. 10 present further experimental results under different settings than the setup given in the main text. In Fig. 10a we analyze the effect of graph connectivity on the overall performance when total of
50 clients are present in the network. We observe that the improvement
gap between DSpodF L and other baselines becomes even more significant compared to Fig. 3bb
In Figs. Tob and 10c isolate the effect of varying bij and d, separately, in contrast Fig. where both the SGD probabilities d, (i.e., computation capabilities) and aggregation probabilities by (i.e., communication capabilities) were varied together. The results are show that DSpodFI more robust to variations in bij or d; compared to the baselines, respectively. In Figs. 10b (and TOch. while the heterogeneity in computational (communication) resources is preserved across the whole experiment, moving from = 3 0.5 to regime to a homogeneous one in terms of communication (computational) resources. Thus, the Sporadic SGDs (Sporadic Aggregations) component of DSpodFL, i.c., green curve (red curve), becomes key to improvement over other baselines when communication (computational) resources are homogeneous.
3d
B brings us from a heterogeneous
0.9 EFFECT OF LEARNING RATE
We vary the learning rate the range a E (0.0001, 0.01, 0.1] our experiments. Fig. II present the test accuracy results for our DSpodFL algorithm and other baselines, when they reach a total delay of r = 500 for FMNIST and т = 5000 for CIFAR1O. For FMNIST, we observe that the best performance of the baselines is lower than DSpodFL. algorithm with learning rates = 0.01 or a 0.1. For CIFAR1O, we make a similar observation where the best performance of the baselines is lower than DL with learning rates 0.001 and 0.01.
65

---

Published as a conference paper at ICLR 2025
DFedAvg
DGD
DSpodFL (Ours)
RG
Sporadic 5GDs
0.50
0.6
after 500
acc. after 500
0.5
0.45
accurcy
0.4
0.40
0.2
0.35
0.30
10000
15000
0.2
0.3
0.4
0.5
0.0
0.2
0.4
0.8
overall delay
(a) (0.0 (0.5)*).
(b) N1 )²))
(c) (e)NNo 1J,, (0.5)*).
Figure 9: We investigate the FMNIST, Non-IlD setup from Figs, 2 and 3 using Truncated Gaussian Distribution to sample SGD and aggregation probabilities d and bij. respectively. We denote this distribution as No.1j )²), which only has values the interval [o, 1].
DFedAvg
DGD
DSpodFL (Ours)
RG
Sporadic SGDs
0.6
0.4
acc. after 500
0.5
acc. after 500
acc. after 500
0.4
0.2
0.1
0.1
0.2
0.4
radius of the RGG
a=
a=
(a) Varying the radius of RGG where 50.
(b) Varying fixing Beta(o, ().
B for by while (c) Varying 3 for d, while 0.5 for d, in fixing
0.5 for by in
Beta(o, ().
Figure 10: Further investigation of DSpodFL's generalization to various setups.
REMARKS
P.1 EFFECT OF COMMUNICATION SPORADICITY ON ANALYTICAL BOUNDS
We will make a remark about this in two parts:
Effect of by on the spectral radius g(*); As mentioned in Sec. 4.4 " "Discussion on conver- gence", the probabilities by affect the bounds through the spectral radius of the expected mixing We can refer to the elements of
matrix, i.., ((k) p(R (k) (1/m)1mm14 from Definition 4.5
matrix (k) in Appendix (b), given as
26 (k) (1 ((())
1i 15ijsm
itj
R (R)
R (
+
2 (k) (1 b(4
r
i=j
18i5m
where (+) defined in Lemma D.4
(a) as
( Tsj
i i
(k)
15tj5m
rtj
i=
15:.5m
As we can see, the values of ((6) directly affect (R) and hence the communication sporadicity parameters (/4) affect all the convergence bounds and learning rate constraints through g(k), the spectral radius of R (k) - (1/m)),,.
From the definition of (k), we can draw some intuitions the relation between B and p(k); If b
(k) 0 for all (i,7) E E, will have diagonal (k), meaning that ((()) 1. On the other
66

---

Published as a conference paper at ICLR 2025
DFedAvg
DGD
DSpodFL (Ours)
RG
Sporadic 5GDs
5000
0.
0.2
0.0
(a) FMNIST, IID.
(b) FMNIST, Non-IID.
(c) CIFARIO, IID.
(d) CIFARIO, Non-IID.
Figure 11: Effect of the learning rate a.
extreme, if Di 1 for all (i,j) E &, we will have the main diagonal of RR R², meaning that ((k) p.. This would be the lowest achievable spectral radius p(A), as is utilizing all the communication links as frequently as possible. All other cases of (k) result in p(h) between these two extremes, with higher connectivity decreasing p(k)
2. Effect of (()) on the analytical bounds: Based on the relationship between bg and p(k), we can establish the connection between (/) and the convergence bound. We can see in Propositions 4.10
and G.6 (convex and non-convex cases) that if أ (one possible scenario being that all (k) as explained in the previous paragraph) the constraint the learning rate becomes ( 0.
Intuitively, no learning rate can make DSpodFL converge if none of the communication links are ever utilized. On the other hand, having all b(4) 1 results in the minimum achievable Ø allowing
a larger learning rate to be chosen based on the constraints given in Propositions 4.10 and G.6 In
other words, the connectivity of the graph induced by (k) increases. larger step sizes can be tolerated while still guaranteeing convergence Theorems 4.1 and 4.12
P.2 PERFORMANCE SUPERIORITY OF DSFODFL
Our performance improvements the baselines SGDs and aggregations. In decentralized FI., resource availability is often heterogeneous and dy- namic, as discussed in Sec. [ there are (i) variations in computation capabilities clients, causing bottlenecks in assuming consistent participation in SGD computations, and (ii) variations in link bandwidth, causing bottlenecks during model aggregation. Referring Algorithm Tin Appendix DSpodFL overcomes these limitations as follows:
from sporadic operations of both local
Client conducts an SGD in iteration only if (/A (line 7). which has probability d; proportional to its processing availability. Consider that multiple clients may possess overlapping data distributions. In such scenarios, the system can benefit from more fre- quent SGD updates from the clients with the highest resource availability, as they provide information representative of multiple clients and finish iterations faster.
Link (i.j) used for model sharing in iteration l only if og) = (line 12 which has a probability by proportional to its bandwidth availability. DSpodFL takes advantage the fact that model information can propagate through the system rapidly over the fastest links in the graph. For example, if link (i,j) has low bandwidth, our method will make client i's relevant local update information reach client j more rapidly through series of other high bandwidth links.
Unlike DSpodFL, the baselines evaluated Sec. 5 work under (a) fixed SGDs and/or (b) fixed aggregations. DGD assumes local SGDs and aggregations at every iteration, RG employs constant SGDs (but sporadic aggregations). Sporadic SGDs assumes constant aggregations, and DFedAvg is DGD with decreased communication frequencies.
67

---

Published as a conference paper at ICLR 2025
P.3 COMPARISON METRICS FOR EXPERIMENTS
As outlined in Sec. [ the average total delay Trotal iteration is defined as the sum of aver- (k)
(A)
(k) age processing delay Tproe and average transmission delay Ttrans up to iteration k. At each iter- ation, depending on whether a client i computed SGDs or not, i.e., o(4)) E {0, 1]. there will be processing delay incurred to finish the computation proportional 1/d! Similarly, depend- ing on o E {0, }}, some of the links (i,j) in the network graph will be utilized for commu- nications, incurring a transmission delay proportional to 1 1/0 (k) for that link. In order to obtain comparable result regardless of the size, connectivity and the topology of the underlying graph, we normalize (i.e., average) both processing and transmission delay to obtain Tprocs Ttrans- For- (k) mally, these are defined as Ttrans |E (1/ING E, 0/4)) /bbgl/L (1/ING)) E, 1/bby] and (k) Tproc - 1>x=1 w0² /d:]/IE 1/d.]. Finally, we define Ttotal Ttrans + Tproc as the average total delay as metric to compare DSpodFL with the baselines.
(k)
(R) (R) (k)
(A) Having explained the average total delay Ttotal Ttrans pproc above, can now see what happens to different baselines under our proposed heterogeneity framework, and how d, and by translate to the speed of client and link, respectively. In DGD, we have that computations and
(k)
(k)
communications occur at every iteration, i.c., e, = 0/6)) = 1 for all E M, (i,j) E and k 2 0. ij
(k) Thus, we will have that Ttrans = |E (L/IA E; 1/bul//E" (L/ING)) E, 1/byl = 1 and
(R) = -5 -- 1 1/d.//LEm 1/4] = 1, and thus each iteration of training will incur a total average Tproc
delay of Tootal 2 for this baseline. For DFedAvg. we still have Tfrde 1 as SGDs oceur at every iteration. But since aggregations occur every 1) iterations, i.c., clients conduct 1) consecutive iterations of local SGD steps before communications, will have Tirons 0 for D iterations and then Tirans = 1 for the next iteration. This deterministic cycle will then continue for DFedAvg.
(R)
(k)
In RG and the Sporadic SGDs baselines, we only have one of these operations occurring at every iteration, i.e., computations and communications, respectively. This means that in RG, we have (k) is deterministic but Pij is stochastic, and for Sporadic SGDs, have deterministic
(d)
(k) biz(k) = but stochastic u/(h) Thus, for RG we will have Tooaa Tirans 1 < 2 implied by
(k)
(k) = 1+ Tproe < 2 implied by Ttrans = 1. Tproe = 1, and for Sporadie SGDs, we will have that Trotal
_(k)
Tproe
However, note that in DSpodFL, both computation and communication operations are carried out in a stochastic way, and thus each iteration of training requires less delay incurred on the whole decentralized system to start the next round of training. Note however, that less computation and communication might come at the cost of losing performance at each iteration, but our motivation in DSpodFL. was to prove that in fact if we evaluate these algorithms based on their total delay, it can outperform existing baselines. The intuition is that due to the data distribution of clients available in the network, their processing capabilities, the graph topology and the link bandwidth capabilities, is not necessary to over utilize all of these resources at every iteration for fast convergence. In fact, resource-aware approach like DSpodFL. L, takes a step at optimally utilizing the resources to achieve the same final solutions in shorter amount of time.
P.4 CONVERGENCE RATE COMPARISON WITH RELATED WORK
Convergence rate in Big O notation. First, we note that as outlined in Table I of Sec. D we pro- vide convergence for last iterates of model parameters when dealing with strongly-convex models in our paper, in contrast to the majority of existing literature which only provide convergence for average iterates (Koloskova et al. 2020). Therefore when dealing with strongly-conve models, we can compare our theoretical results only for the DGD baseline because the DGD-like algorithms given in Mishchenko et al. (2022); Maranjyan et al. (2022) are among the few to show convergence for the last iterates of model parameters as well. According to Theorems 3.6, 5.5, 5.7 and D.1 in Mishchenko et al. (2022) and Theorems 3.5, 4.5 and B.2 in Maranjyan et al. 2022). the conver- gence rate of the algorithms ProxSkip, Decentralized Scaffnew, SplitSkip (Mishhhenko et al. 2022). GradSkip, GradSkip+ and VR-GradSkip+ (Maranjyan al. (022)) are all geometric, i.e., 0px))
68

---

Published as a conference paper at ICLR 2025
with 0 p 1 (note that most of these algorithms are FL algorithms, and not decentralized FL algorithms). This rate agrees with the rate we provide Eq. 9 of Theorem 4.11
When dealing with non-convex models, Ozdaglar (009) for DGD, Koloskova et al. (2020) for RG and Sun et al.
compare rate with all the baselines. Nedic & (202)) for DFedAvg. Since for all (i,j) &,
DGD special case of RG with sporadicity in aggregations, i.e., bjj
we will compare our work with the more recent paper Koloskova et al. (2020). For DGD and RG,
Lemma 17 Koloskova al. (2020) shows the convergence upper bound before tuning the constant learning rate a, which
B[F(D F* - + O(a) + O
a(K +1)
For DFedAvg, Theorem in Sun et al. (2022)
with zero momentum (0 = 0) obtains the bound
[[F(B())) - F
+ + + +(a))) O(a").
ax a(K + 1) We observe that by setting dmni recovered. Recall that as discussed in Fig. of our paper, all of these baseline algorithms fit within the general framework of DSpodFL with d, - for all clients E M. That is why we can substitute dmnin in Theorem 2 to compare Nedic & Ozdaglar (2009): Koloskova et al. (2020); Sun et al. (2022).
Theorem 4.12 of our paper, these convergence rates are
analytical results with the ones provided in
Comparison of convergence bound for non-convex models with Koloskova et al. 2022). Let us examine the bound derived in the proof of Lemma 16 Koloskova et al. (2020) before tuning the learning rate, i.e.,
Bf(;00) - f L L + 2( + + n/2 (T 1)n n
Σ |V t=
+ n 64
2(T + 1)
Translating these parameters to the setup of our paper, we have
T k,, F. 0 0,7 + 3, 0 + m, 1,p + p, M - 0. As consequence, the bound in Koloskova et al. (2020) using the notation and setup of our paper becomes
2(K +1) Σ II
a + 128 EF(0()) F*
_0²
I-p 82)
(K + 1)a
m
1
Now, we compare this with the non-asymptotic bound we obtain for non-convex models in Theo- which is
rem 4.12
W1
K
(VF
F(O(0)) F
1
32
| (0) ?
K +1
alK +1
1
1
m
-
K +1
Ti
1 1+T,
(16
1+0
+ +
_o 2m a.
a + (1 11) dmin )8 +
1-
where we used the fact that dmaa
We can see how our bound compares with the one derived in Koloskova et al. 2020 The exact value Wi in our paper depends on the arbitrarily chosen scalars To..... but we have in general that wi 2. For common terms that analysis has with Koloskova et al. (2020), we see how their coefficients both our bound and the one in Koloskova al. 2020) are proportional to (T-ø] and (o² + 0²)0), with slight differences in the value of q. Furthermore, for the term proportional to a. both our bound and Koloskova al. 2020 are proportional Ao²
also very similar. For example, for the term proportional to a observe that 8²
2m
However, we can observe that our bound consists of two extra terms compared to Koloskova et al. ?
2020). The first one, 1+t. 1- m(1-p) K+1 is capturing the effect of different model ini-
82
(!)
m
tializations for the clients. The second one, (1 + T1) dmmnndd )o2 is capturing the effect of sporadic
69

---

Published as a conference paper at ICLR 2025
SGDs in DSpodFL framework. We observe that if all clients conduct SGDs at every iteration, i.e., dhh) for all M and k 2 0, this term becomes equal to zero, giving us the bound for non-sporadic methods outlined Koloskosa et al. (2020). Therefore, as we have claimed in Sec. 4.5 of our paper, our convergence bounds recover well-known results in the literature the degenerate case of dmai = 1.
70


Reviews:
[{"review_id": "YA46pAgBwK", "reviewer": "Reviewer_PFSw", "summary": "This work proposes a generalized framework for analyzing the challenges of federated learning in a decentralized setting. Such challenges include heterogeneity in the updates of individual clients, and communication constraints for achieving consensus in a decentralized setup (which is more challenging that the typical \"star\" topology with a central PS). The term \"sporadicity\" in the title refers to varying frequencies of both -- local updates at clients (limited by computational capacity), and inter-client communication (limited by network capacity). The work proposes a unifying framework for analyzing the effect of this sporadicity on the convergence rate.", "questions": "I have a few concerns, and I would be very glad if these are addressed:\n\n1. Will taking into account the correlation between inter-client communication improve the guarantee, instead of each client independently making a decision for itself. In general, sporadic communications are often correlated.\n\n2. Referring to Def. 4.6, why are the indicator variables not defined as Bernoulli random variables? It seems like they are modeled as Bernoulli variables, but it is not explicitly mentioned anywhere. \n\n3. In the aggregation step, the clients need to know which nodes communicate to it? In other words, is a blind aggregation where the identity of the participating clients is anonymized, possible? \n\nAlso, some recent works in communication sporadicity is missing: For example, in this work: https://ieeexplore.ieee.org/document/10705313, communication sporadicity is considered in conjunction with privacy constraints, although in a semi-decentralized setting. Privacy is an important aspect of federated learning, and so the paper will benefit with some discussions on the privacy implications of the current algorithm.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The algorithm framework proposed in eq (2) that considers the effect of both kinds of sporadicity as mentioned above is one of the primary contributions of the paper. This is further formulated as a matrix update in eq. (3), and the consensus weights are chosen the mixing matrix is doubly stochastic.\n\nThe unifying approach to analyze computation and communication sporadicity is definitely an important step towards analyzing decentralized algorithm. The work has been placed well (and compared with) in the context of existing literature. The convergence analysis is quite comprehensive, and aligns with the standard analysis techniques of works in this line. The analytical contribution of the paper is definitely commendable.", "weaknesses": "I have some important concerns which I list here in the \"Weaknesses\" section. Other minor concerns or questions are mentioned in the next section. I would appreciate it if the authors could clarify the following concerns:\n\n1. My major concern is that it is not really clear where the gain of DSpodFL is coming from? The work shows improvements in numerical simulations, in which the X-axis in the total latency. Is the primary intuition behind the improved performance of DSpodFL just the fact that frequent communications are not necessary, which other decentralized algorithms do? Is the benefit of DSpodFL over other algorithms quantified/discussed anywhere in the paper?\n\n2. Are the weights $r_{ij}$ need to be known beforehand? For example, in Metropolis-Hastings mixing, the future topology of the graph needs to be known -- an assumption that may not hold true for federated learning when the network is dynamically changing (for mobile clients, for example), and it is not easy to know the union of all edge sets and determine the weight. How are they chosen in the simulations?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PH31jGVnm2", "reviewer": "Reviewer_ryLC", "summary": "The paper considers decentralized optimization with nodes having varying communication time and computation resources that might also change in time. The paper analyzes convergence rate of proposed framework for strongly convex and non-convex functions and evaluates effectiveness of the framework in experiments.", "questions": "1. Paper mentions that (Even et al 2024) did not consider time variations in resource heterogeneity and I would like to ask you to elaborate on this. In my understanding asynchronous communication allows for resource heterogeneity. \n\n2. What if in proposition 4.10, d_{max}^{k} = 0 for some k? I think it is allowed by the framework and it would mean that you have to divide by zero? \n\n3. in line 360 you state that lim_{k ->0} \\Phi(k:0) = 0 is enough to prove that consensus error and average error converges to zero, however even in this case, it depends on convergence of $\\Psi^{(k)}$ that might be non zero or might even diverge. Can you clarify on that? \n\n4. Why does the matrix R have to be doubly stochastic if you anyways renormalize the matrix P later to be doubly stochastic?\n\n5. I did not understand how exactly result (10) recovers (Koloskova (2020)) (comment in lines 386 and 387), could you provide a more detailed derivation of this result? also, (Koloskova (2020)) allows for local steps in decentralized SGD, meaning that d_{min} = 0 at those steps, could you compare your result with (Koloskova (2020)) for that local decentralized SGD? Same for the non-convex functions. \n\n6. How does $w_1, w_2, w_3, w_4, w_5$ depend on the key parameters of the problem (parameters from Assumptions 4.2-4.4). Is there a way to simplify the convergence rate, e.g. by using O-notation? \n\n7. What does “average total delay occurred ip to iteration k\" mean? Is it total simulated time? \n\n8. In experimental comparison, how exactly are the baseline algorithms implemented under the proposed heterogeneity of communication and computation? How does d_i and b_{ij} translate to the speed of the node?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper proposed framework is general and allows for varying resource availability. The paper compares its framework with the baselines.", "weaknesses": "1. The proposed framework does now allow for the slow gradient computation, as gradients cannot be delayed. This is because the framework does not allow for computation and communication sporadicity being correlated (per assumption 4.3.), and according to (2) each gradient has to be computed at the latest local model $\\theta_i$. This means that if some node computed the gradient for a long time, and in the meantime local model is being updated due to the communication on this node occurring, the node has to drop its previous computations and start computing its gradient from scratch on the new model so that it can return the gradient at the latest model.\n\n    There are two possible solutions to this: either allow for communication and computation being correlated (i.e. while node computes, no communication happens), or allow for the gradients to be delayed.\n\n    To me this is a big limitation of the framework.\n\n3. Only asymptotic convergence is proven (i.e. when the number of iterations K goes to infinity), while previous frameworks such as (Even 2024) give convergence bound for any number of iterations K. \n\n\n4. Paper has several flows in presentation: e.g. first it states that framework the paper analyzes is (2), but then actual analyzed algorithm is in equations (3)-(4) that is not equivalent to (2) (difference comes from re-normalization of the diagonal element p_{ii}^k).\n\n5. Convergence rate derived for non-convex functions is hard to understand, as it depends on some parameters $w_1, w_2, w_3, w_4, w_5$ that are defined only in appendix. \n\n6. Paper does not tune the learning rate, but uses the same learning rate for different algorithms - that might give advantage to some algorithms. \n\n7. Experimental comparison to (Even 2024) is missing. Is there a specific reason why you excluded that baseline from comparison?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JYkUne6wch", "reviewer": "Reviewer_soQ2", "summary": "This paper studies decentralized federated learning setting, where a central server is lacking and the agents may perform a stochastic number of local iterations. Furthermore, the peer-to-peer communication also happen in a random fashion. The authors propose a method called DSpodFL, which combines consensus and local gradient descent while allowing stochasticity. The main contribution lies in the algorithm setup/flexibility, convergence analysis using indicator random variable to model stochasticity and allowing for milder assumptions for both convex and nonconvex cases.", "questions": "For the expectation calculations, some of them seems to be conditioned on past realizations, a filtration should be setup to rigorously justify the steps. If this is not the case, please explain. \n\nHow much information is necessary by each of the agents to calculate the learning rates? \n\nWhy should all agents use the same learning rates?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The algorithm allows for a very general stochasticity capturing varying communication and computation cost and allows for heterogeneity in agents' capabilities. The algorithm is also written in a very clean fashion. The proofs appear to be mostly right.", "weaknesses": "The proofs in the appendix lacks explanation for the steps.\n\nMy main complaint is that while this is a good first step towards allowing different kinds of stochasticity, the proposed algorithm misses the mark in the sense that the value it converges to is not the original optimal solution. There has been a long line of literature in distributed optimization tackling the same setup (without multiple local steps) by including additional error correction terms, (almost) exact convergence can be achieved. A simple counting of the activation frequencies as in the following paper could help reduce the error term in the limit. Because of this, I'm not sure how useful the proposed method would be for any real applications, especially with large amount of heterogeneity in the activations. I'm marginally willing to accept the paper due to its innovative computation framework. \n\nRam, S. Sundhar, A. Nedić, and Venugopal V. Veeravalli. \"Asynchronous gossip algorithms for stochastic optimization.\" Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference. IEEE, 2009.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0anFayE5Q8", "reviewer": "Reviewer_aSDE", "summary": "The author present DSpodFL, a unified framework of decentralized federated learning. DSpodFL allows each client to take local update and communication intermittently according to its available resources. And DSpodFL framework also involves some existing decentralized federated learning algorithms. The authors provided the convergence analysis of DSpodFL in convex and nonconvex settings.", "questions": "1. The proposed frame can unify existing algorithms including DGD, DFedAvg and RG. If we can obtaining the convergence analysis of these existing analysis **directly** from Theorem 4.11 and 4.12? And if the convergence rates of the existing algorithms obtained from Theorem 4.11 and 4.12 **match** the existing convergence analysis? Please present the detailed steps.\n\n2. Figure 2(b) only show the convergence curves when $\\tau\\in[0,10000]$, and DSpodFL only achieve the test accuracy of about **0.6** during this period. So can the authors provide convergence curves of these algorithms with a larger $\\tau$ such as 20000 or 30000? Similarly, can the authors provide the convergence curves of Figure 2(c) with a larger $\\tau$?\n\n3. How do the algorithms including DSpodFL perform in test accuracy with respect to wall-clock time?\n\nI will update the scord according to the response during the discussion period.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. A unified algorithm framework.\n\n2. Making clients able to take local update and communication according to its available resources.\n\n3. Convergence analysis in both convex and nonconvex scenarios.", "weaknesses": "See questions", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XIwO5XKxV8", "reviewer": "Reviewer_VTdm", "summary": "This paper develops a generalized algorithmic framework, DSpodFL, for decentralized federated learning (DFL), which effectively integrates the heterogeneity and dynamics of local stochastic gradient descents (SGDs) and aggregation processes. The convergence of DSpodFL is analyzed for both strongly convex and nonconvex loss functions. Additionally, numerical experiments on various datasets demonstrate the advantages of the proposed method.", "questions": "Perhaps $p_{ii}^k = 1 -\\sum_{j \\in M} r_{ij} \\hat v_{ij}^k + r_{ii} \\hat v_{ii}^k $ in equation (4)?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1.\tThe investigated problem is novel, as the authors address the combined effects of sporadic local client computations and inter-client communication, an aspect previously unexplored in DFL.\n\n2.\tThe presentation of the paper is clear. The authors provide rigorous convergence results for both strongly convex and nonconvex settings, which are well-justified.\n\n3.\tThe numerical experiments are sufficient and effectively showcase the advantages of the proposed DSpodFL framework.", "weaknesses": "1.In Section 3.3, why the random matrix $P^k$ is doubly stochastic and symmetric? This is not immediately clear, and providing a proof and an illustrative example would enhance understanding.\n\n2.In Assumption 4.1, the gradient diversity is measured by $ || \\nabla F(\\theta) - \\nabla F_i(\\theta) ||$, while in Assumption 4.2, it is measured by $ ||\\nabla F_i(\\theta) ||$.What is the rationale behind this distinction?\n\n3.In the analysis with a diminishing learning rate, why does exact convergence require an increasing frequency of SGDs over time? Moreover, the dependence of SGD probabilities on the stepsize seems unrealistic. Why does this requirement not apply when using a constant stepsize?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)