Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGD
Authors: Jie Hu
Yi-Ting Ma
Do Young Eun
Venue: NeurIPS 2024 poster (2024)
Keywords: Distributed Optimization
Agent Dynamics
Federated Learning
Central Limit Theorem
Efficient Sampling
Primary area: learning_theory
TL;DR: We provide an asymptotic analysis of the Unified Distributed SGD, including decentralized SGD and various Federated Learning algorithms, to study the impact of agents' sampling strategies on the overall convergence of the large-scale system.

Abstract: Distributed learning is essential to train machine learning algorithms across *heterogeneous* agents while maintaining data privacy. We conduct an asymptotic analysis of Unified Distributed SGD (UD-SGD), exploring a variety of communication patterns, including decentralized SGD and local SGD within Federated Learning (FL), as well as the increasing communication interval in the FL setting. In this study, we assess how different sampling strategies, such as *i.i.d.* sampling, shuffling, and Markovian sampling, affect the convergence speed of UD-SGD by considering the impact of agent dynamics on the limiting covariance matrix as described in the Central Limit Theorem (CLT). Our findings not only support existing theories on linear speedup and asymptotic network independence, but also theoretically and empirically show how efficient sampling strategies employed by individual agents contribute to overall convergence in UD-SGD. Simulations reveal that a few agents using highly efficient sampling can achieve or surpass the performance of the majority employing moderately improved strategies, providing new insights beyond traditional analyses focusing on the worst-performing agent.

Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGD
Yi-Ting Ma Department of Electrical and Computer Engineering North Carolina State University {jhu29, yma42,
Jie Hu
Do Young Eun
edu
Abstract
Distributed learning is essential to train machine learning algorithms across hetero- geneous agents while maintaining data privacy. We conduct an asymptotic analysis of Unified Distributed SGD (UD-SGD), exploring variety of communication pat- terns, including decentralized SGD and local SGD within Federated Learning (FL), well the increasing communication interval in the FL setting. In this study, we assess how different sampling strategies, such as i.i.d. sampling, shuffling, and Markovian sampling, affect the convergence speed of UD-SGD by considering the impact of agent dynamics on the limiting covariance matrix as described the Central Limit Theorem (CLT), Our findings not only support existing theories on linear speedup and asymptotic network independence, but also theoretically and empirically show how efficient sampling strategies employed by individual agents contribute to overall convergence in UD-SGD, Simulations reveal that few agents using highly efficient sampling can achieve or surpass the performance of the majority employing moderately improved strategies, providing new insights beyond traditional analyses focusing on the worst-perforiing agent.
Introduction
Distributed learning deals with the training of models across multiple agents over a communication network in a distributed manner, while addressing the challenges of privacy, scalability, and high- dimensional data 11 55). Each agent i E [N] holds private dataset X, and an agent-specified loss function F, Rdd x X R that depends on the model parameter 0 E Rd and data point X XG. The goal then to find local minima 0* of the objective function (0) A 1 EN f:()), where agent i's loss function f=( 2 Ex=D, (F:(O, X)] and D; represents the target distribution of data for agent z Each agent can locally compute the gradient (F, E IRd w.r.t for every sampled data point X E Xr Due to the distributed nature, {Di JE[N] and (ei] necessarily identically distributed over [N] so that the minima of each local function fi( can be far away from L. This is particularly relevant decentralized training data, e.g., Federated Learning (FL) with heterogeneous data across data centers devices [8]] 31)
N
not
In this paper, we focus on Unified Distributed SGD (UD-SGD), where each agent i [N] updates its model parameter 0/ in two-step process:
Local update: 8% 7 = 8 7n+1 (.
(la)
'Throughout the paper we don't impose convexity assumption (0). For convex f()), L is the global
minima. For non-convex f()), represents the collection local minima, which of great interest neural network training for sufficiently good performance (20 [9]. With an additional condition such as the
inequality, non-conve, (0) is ensured to have unique minima
75 78
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Aggregation: 0%+1 Σÿ= w wn(t.)) n41/2
(1b)
where "n denotes the step size, X is the data sampled by agent i at time (i.e., agent dynamics), and
W = Ww,, (1,))))) represents the doubly-stochastic communication matrix satisfying wn (i. 2
0 and 1 W, = -. In the special case of N =1, ( simplifies to the vanilla SGD where
W,, n = 1 for all n. UD-SGD covers a wide range of distributed algorithms, e-g., decentralized SGD
(DSGD) 77 80 61 68). distributed SGD with changing topology (DSGD-CT) [4 43 local SGD
(LSGD) in FL [55 76). and its variant aimed at reducing communication costs (LSGD-RCC [1
Versatile Communication Patterns [Wn): For visualization, we depict the scenarios of UD-SGD ① in Figure I In DSGD, each agent (node) in the graph communicates with its neigh- bors after each SGD computation via W.. rep- resenting the underlying network topology. As a special case, central server-based aggregation, forming a fully connected network, translates Wn into a rank-1 matrix W,, n = 11 /N. To minimize communication expenses, FL variants allow each agent to perform multiple SGD steps before aggregation [55 67 76.. resulting in communication interval of length K and con- sistent pattern W, n = W for n = mK, Vm E N. and W, n IN otherwise. In particular, i) W 11 /N corresponds to LSGD with full agent participation (LSGD-FP) 76 random matrix generated by partial agent participation (L) 555 I8 by Metropolis-Hasse decentralized FL (DFL) 46 77 16.. We defer further discussion of W to Appendix
Communication pattern Wn
Malli i
X
Heterogeneous sampling strategy x
X
8e58
dataset X2
dataset X
Figure GD-SGD algorithm with communi- cation network of N = 5 agents, each holding potentially distinct datasets; e.g., agent j (in blue) samples X3 i..dd and agent (in red) samples X; via Markovian trajectory.
42 511: ii) W is a
74; iii) W is generated
algorithm in decentralized setting, e.g., hybrid LSGD (HLSGD) (37 32 and
Markovian vs i.i.d. Sampling: Agents typically employ i.i.d. or Markovian sampling, as illustrated in the bottom brown box of Figure I In cases where agents have full access to their data, DSGD with FL., many application-orientel LSGD 53 However, these works solely focus on i.i.d.
i.id sampling has been extensively studied 60 43
47
variants have been investigated [51 18 77
32
37
sampling, restricting their applicability to Markovian sampling scenarios.
Markovian sampling, which has received increased attention in limited settings (see Table D is vital where agents lack independent data access. For instance, in statistical applications. agents with an unknown a priori distribution often use Markovian sampling over i.i.d. sampling 44 63). In
HLSGD across device-to-devin compared to the frequent aggregations required by Gossip algorithms
(D2D) networks 33 37. random walks reduce communication costs
[38] 28 4]. For single-agent scenarios, vanilla SGD with Markovian noise, as applied in a D2D network, has shown improved communication efficiency and privacy 669 28 35]. In contrast, for agents with full data access, Markov Chain Monte Carlo (MCMC) methods can be more efficient than i.i.d. sampling, especially in nigh-dimensional spaces with constraints 407 where acceptance-rejecteo
methods [12] lead to computational inefficiency (e.g., wasted samples) due to multiple rejections before obtaining a sample that satisfies constraints [26, 69). In addition, shuffling methods can be considered as high-order
Markov chains (38) which achieves faster convergence than i.i.d. sampling 1 79 78
Limitations of Non-Asympiotic Analysis on Agent's Sampling Strategy: Recent studies on the non-asymptotic behavior of DSGD and LSGD variants under Markovian sampling, as summarized in Table [] have made significant strides. However, these works often fall short in accurately revealing the statistical influence of each agent dynamics {X;} J on the performance of UD-SGD. For instance,
), where E (0.5, 1] and denotes the identical mixing rate for all agents, overlooking agent heterogeneity in sampling strategy. A similar assumption to p is also evident in 42 More recent contributions from [80 72 have attempted to relax these constraints by considering a finite-time bound of O + 1)), where Twni is the mixing time of the slowest agent. This approach, however, inherently focuses on the porst-performing agent, neglecting how other agents with faster mixing rates might positively influence the system Such an analysis fails to capture the collective impact of other agents on the overall system performance,
71 68 proposed the error bound O 1/ log" (1/)))
2 Although improving the finite-time upper bound to distinguish each agent may not be the focus of the aforementioned works, their analyses require every Markov chain to be close some neighborhood of its

---

Table 1: Comparison of recent works in distributed learning: We classify the communication patterns into seven categories, i.e., DSGD, DSGD-CT, LSGD-FP, LSGD-PP, LSGD-RC, HLSGD and DFL. We mark 'UD-SGD' when all aforementioned patterns are included and the detailed discussion on {W referred to Appendix F.T Abbreviations: "Asym." 'Asymptotic', 'D.A.B' 'Differentiating "Linear Speedup', 'A.N.I." = 'Asymptotic Network Independence'
Agent Behavior', L.S.' =
Reference
Analysis
Sampling
Communication Pattern
DSGD D.A.B.
L.S.
A.N.I.
Asym.
i.d.
Asym.
Lid.
LSGD-RC
V
/
N/A
A
Non-Asym.
i.d.
DSGD-CT
x
61
Non-Asym.
Lid.
DSGD
x
18
53
Non-Asym.
i.d.
ISGD-PP
X
N/A
37
32
Non-Asym.
Lid.
HLSGD
X
77
16
Non-Asym.
i.d.
DFL
x
x
7
80
68
Non-Asym.
Markov
DSGD
x
x
x
42
72
Non-Asym.
Markov
LSGD-FP
x
N/A
69
28
Non-Asym.
Markov
N/A (single agent)
N/A
N/A
N/A
38
Asym.
Markov
N/A (single agent)
N/A
N/A
N/A
Our Work
Asym.
Markov
UD-SGD
crucial aspect in large-scale applications where identifying and managing the worst-performing agent is challenging due to privacy concerns or sporadic unreachability. Since agents distributed learning have the freedom to choose their sampling strategies, it's vital to understand how each agent's improved sampling approach contributes to the overall convergence speed of the UD-SGD algorithm. This understanding is key enhancing system performance, particularly in large-scale machine learning scenarios where agent heterogeneity is a defining feature.
Rationale for Asymptotic Analysis: Recent trends in convergence analysis have leaned towards non-asymptotic methods, yet it's crucial to recognize the complementary role of asymptotic analysis for better understanding of convergence behaviors, as highlighted in [ 56, 25 B9]. For vanilla SGD, [59[ [7] emphasized that central limit theorem (CLT) is far less asymptotic than it may appear under both i.i.d. and Markovian sampling. Notably, the limiting covariance matrix. key statistical feature in vamilla SGD's s CLT, also prominently features in high-pu seeh--rbbbbbltty bound [59], explicit finite-time
bound [17 and 1-Wasserstein distance in the non-asymptotic CLT [666] 38 further underscored
this by numerically showing that the limiting covariance matrix provides a more precise depiction of
convergence than the mixing rates often used in finite-time upper bounds (26] 69) Moreover, they
argued that finite-time analysis may not suitably apply to certain efficient high-order Markov chains, due to the lack of comparative mixing-rate metries.
Our Contributions: We present an asymptotic analysis of the UD-SGD algorithm I under hetero- geneous agent dynamics (XH} and large family of communication patterns { J. Specifically,
Under appropriate assumptions, all agents performing (T) asymptotically reach the consensus and find 0": E [N], On, e N Σ 0f denotes the average model parameter among all agents, we have
lim |10 -00 10,=00 +=000
00, lim 00, 0- =0 a.s.
Moreover, we derive the CLT of UD-SGD in the form of
On
-1/2 0*) diat.
N (0, V).
Our framework addresses technical challenges in quantifying consensus error under various commu- nication patterns and slowly increasing communication interval. This shows substantial extension compared to previous studies [58 43 51], particularly in regulating the growth of communication
stationary distribution. This naturally incurs a maximum operator, and thus convergence is strongly influenced by the slowest mixing rate, ie.. the worst perft-ner agent.
3

---

intervals (Assumption 2.3 ii) and in proving the scaled consensus error's boundedness (Lemma B.Ij. Furthermore, we reformulate UD-SGD as a stochastic upproximation-lia iteration and tackle the Markovian noise term using the Poisson equation, technique previously confined only to vanilla The key here is to devise the noise decomposition that separates the consensus error among all agents from the error caused by the bias from the Markov chain, which aligns with the target distribution only asymptotically at infinity, not at finite times.
SGD with Markovian sampling 17 38 52
In analyzing 33) we derive the exact form V as Nz Σnn V;. Here, V is the limiting covariance matrix of agent i, which depends mainly on its sampling strategy } This allows us to show that improving individual agents' sampling strategy can reduce the covariance in CLT, which in turn implies a smaller mean-square error (MSE) for large time n. This is a significant advancement over previous Lnite-sample bounds that only account for the worst-performing agent and do not fully capture the effect of individual agent dynamics on overall system performance. Our CLT result (3) very special case with N 1, where the relationship therein
also treats recent findings in [38] between the sampling efficiency of the Markov chain and the limiting covariance matrix in the CLT of vanilla SGD, can carry over to our UD-SGD.
We demonstrate that our analysis supports recent findings from studies such as [42], which exhibited linear speedup scaling with the number of agents under LSGD-FP with Markovian sampling; and 62. 61, which examined the notion of 'asymptotic network independence" for DSGD with i.i.d sampling, where the convergence of the algorithm (I) large time n depends solely the left eigenvector of W., ( considered in this paper) rather than the specific communication network topology encoded in Wn. but now under Markovian sampling. We extend these findings in view of CLT to a broader range of communication patterns {W,) and general sampling strategies {X,}
We conduct numerical experiments using logistic regression and neural network training with several choices of agents' sampling strategies, including a recently proposed one via nonlinear Markov chain [25]. Our results uncover a key phenomenon: a handful of compliant agents adopting highly efficient sampling strategies can match or exceed the performance of the majority using moderately improved strategies. This finding is crucial for practical optimization in large-scale learning systems, moving beyond the current literature that only considers the worst-performing agent in more restrictive settings.
2 Preliminaries
Basic Notations: We use ||v|| to indicate the Euclidean norm of a vector v E I2 and |M]] to indicate the spectral norm of a matrix M E Raxd The identity matrix of dimension is denoted by Ia, and the all-one (resp. all-zero) vector of dimension N is denoted by 1 (resp. 0). Let & 11 /N. The diagonal matrix with the entries of v the main diagonal is written diag(v). We also use "2" for Loewner ordering such that A > B is equivalent to x² x"AA- B)x 2 0 for any x E Rd.
Asymptotic Covariance Matrix: Asymptotic variance is a widely used metric for evaluating the second-order properties of Markov chains associated with a scalar-valued test function in the MCMC literature, e.g., Chapter 6.3 [12), and asymptotic covariance matrix is its multivariate version for vector-valued function. Specifically, we consider finite, irreducible, aperiodic and positive recurrent (ergodic) Markov chain {Xn]n20 with transition matrix P and stationary distribution ा, and the
estimator (g) A 1
D g(X.) for any vector-valued function g [N] - Rd. According to ==0 131. we have lim Ar (g) E,, (g) a.s., As defined in [ 38), the
the ergodic theorem [12
asymptotic covariance matrix Σx (g) for a vector-valued function g()) is given by
Σx (g) A lim n Var(An,g) lim n=o
(A.A7)
4
n-
where A, En (g(,)) - (g)). By following the algebraic manipulations in 112 Theorem
6.3.7] for asymptotic variance (univariate version), we can rewrite ( in a matrix form such that
Σx (g) = GD diag( ④T) [Z IN + 1 7 G,
where G A [g( B(N)]= E Nxd and Z A [I - P 1n This matrix form explicitly shows the dependence on the transition matrix P and its stationary distribution म, and will be utilized in our Theorem 3

---

Model Description: The UD-SGD in ① can be expressed in compact iterative form, i.e., we have
8 0
-ド= N wn(i, +++1 + FF X()),
(6)
at each time n. where each agent i samples according to its own Markovian trajectory {x 1220 with stationary distribution π, such that Ex-,, [F, X = f()).. Let K2 denote the communication interval between the (1 - 1- and 1-th aggregation among N agents, and ny _ E Km be the time instance for the I-th aggregation. We also define In - mins ny 2 n as the index of the upcoming aggregation at time such that K=, indicates the communication interval for the Tw-th aggregation, or more precisely, the length of the communication interval that includes the time index n. The communication pattern follows that W. I, if n o Tht and W.. W otherwise for I 12 1, where the examples of W will be discussed in Appendix F.1 Note that i) when K₁ 1. ( reduces DSGD; ii) when K₁ K > 1, (6) becomes the local SGD FL. iii) When Ki increases with 4, we recover some choices of K2 studied in [51] beyond LSGD-RC with i.i.d. sampling. This increasing communication interval aims to further reduce the frequency of aggregation among agents for lower communication costs, but now under a Markovian sampling setting and a wider range of communication patterns. We below state the assumptions needed for the main theoretical results.
i eare Assumption 2.1 (Regularity of the gradient). For each is L-smooth in terms of 0, i.e., for any 0,, 02 E Rd, [[VF;(01. - (F,((2,,)) S L| B2ll-
[N] and X X2, the function F()
(7)
In addition, we assume that the objective function f is twice continuously differentiable and p-strongly convex only around the local minima 0- E C, i.e.,
- H ł pla-
(8)
Assumption 2.1 imposes the regularity conditions on the gradient V F () and Hessian matrix of the objective function f(-). as is commonly assumed in [10 45 29 38). Note that (7) requires per-sample Lipschitzness of F; and is stronger than the Lipschitzness of its expected version Vfi which is commonly assumed under i.i.d sampling setting [73
50 30 However, we remark that this in line with previous work on DSGD and LSGD-FP under Markovian sampling as well 771 42 80. because V (0, X) is no longer the unbiased stochastic version of V (0) and the effect of { has to be taken into account in the analysis. The local strong convexity at the minimizer is commonly assumed to analyze the convergence of the algorithm under both asymptotic and non-asymptotic
analysis 10 29 38
45
52 80).
Assumption 2.2 (Ergodicity of Markovian sampling). {X+) is an ergodic Markov chain with stationary distribution ni such that Ex-m, (0, X)] = f()),, and is independent from [X2)m20.) #i.
The ergodicity of the underlying Markov chains, stated in Assumption 2.2, is commonly assumed in the literature (26 69 80 42 38) This assumption ensures the asymptotic unbiasedness of the loss function F, -), which takes i.i.d. sampling as a special case.
Assumption 2.3 (Decreasing step size and slowly increasing communication interval). i) For bounded communication interval KT, < K, Vn, we assume the polynomial step size '/n 1/n" and a (0.5, 1]; Or ii) If K,, + oc as + 00, we assume 7nn = 1/n and define = = kg.K L+1 where the
sequence (Kih20 satisfies Σn The < 00, Kr,, = o(>7 1/2 and lim4 Thu+1 Mm1+++ 1.
In Assumption 2.3 the polynomial step size "nn is standard in the literature and it has the property Σn 7n = x., En The < x: 17 38 Inspired by (51), we introduce 7ha to control the step size within each 1-th communication interval with length K2 to restrict the growth of K₁. Specifically,
Σn th < 0o and K,, = o(% 1/2(L+)) ensure that 7h + 0 and Ky, does not increase too fast in limy-voo /
1 sets the restriction practical forms of Ki suggested by [5I], including K₁ ~ log(l) and K; ~ log log(1), also satisfy Assumption li). We defer to Appendix the mathematical verification of these two types of Ki, together with the practical implications of increasing communication interval Ki.
the increment from ny to 1441- Several
Remark 1. In Assumption 2.3 we incorporate an increasing communication interval along with a step size I/n 1/n. This complements the choice of step size Ttn in 157 Assumption 3.3), where In = 11/n for a E (0.5, 1). It is important to note, however, that the increasing communication interval specified in (51) Assumption 3.2] is applicable only in i.i.d sampling, Under the Markovian
5

---

sampling framework, the expression V loses its unbiased and Martingale difference properties. Consequently, the Martingale CLT application as utilized by (5T] does not directly extend
to Markovian sampling. To address this, we adapted techniques from [29 58) to accommodate the
increasing communication interval within the Markovian sampling setting and various communication
patterns. This adaptation necessitates "Io =1/n, specification not covered in 157y. Exploring more general of K₁ that could relax this assumption is outside the scope of our current study.
Assumption 2.4 (Stability on model parameter). We assume sup,, ||0 ll < co almost surely Vi [N]-
Assumption 2.4 claims that the sequence of {6% } always remains in a path-dependent compact set. It is to ensure the stability of the algorithm that serves the purpose of analyzing the convergence, which is often assumed under the asymptotic analysis of vanilla SGD with Markovian noise [23 29 [2). As
mentioned in [58] 70), checking Assumption 2.4 is challenging and requires case-by-case analysis, even under i.idd sampling. Only recently the stability of SGD under Markovian sampling has been studied in [9] but the result for UD-SGD remains unknown in the literature. Thus, we analyze each agent's 's sampling strategy in the asymptotic regime under this stability condition.
Assumption 2.5 (Contraction property of communication matrix). i). {Wa Jn20 is independent of the sampling strategy {X, In2o all i E [N] and is assumed to be doubly-stone stochasticc for all n; ii). At each aggregation step ny, W nu is independently generated from some distribution Pny such that [T wP.,,, W W] J|| S C < 1 for some constant C1-
The doubly-stochastiiitt of Wn in Assumption 2.5 is widely assumed in the literature [54, 24 43 80). Assumption 2.. is a contraction property to ensure that agents employing UD-SGD will asymptotically achieve the consensus, which is also common in 7 24, 80). Examples of W that satisfy Assumption 2.3 ii., e.g., Eatropolii-Hassting matrix, partial agent participation in FL., are
deferred to Appendix| F.1 due to space constraint.
3 Asymptotic Analysis of UD-SGD
N Σ 6; represent the consensus among all the agents at time n, we establish the asymptotic consensus of the local parameters H as stated in Lemma 3.1 Lemma 3.1. Under Assumptions 2.7 2.3 2.4 and 2.5 the consensus error 6 0,, diminishes to zero at the rate specified below: Almost surely, for every agent i E [N).
Almost Sure Convergence: Let 8, - 1
1 0z - { (1()) under Assum. 2.3 i),
(n)) under Assum.
2.3 it.
Lemma 3.1 indicates that all agents asymptotically reach consensus at a rate of 0(%)) (or (.).))
This finding extends the scope of [58, Proposition 1]. incorporating considerations for Markovian sampling. FL settings, and increasing communication interval K2. The proof, detailed in Appendix B primarily tackles the challenge of establishing the boundedness of the sequences (--- (7,-1 - (n))) almost surely for all i E [N]. This is specifically analyzed in Lemma B. Next, with additional Assumption 2.2 are able to obtain the almost sure convergence of 0₂ to 0
0
} (or
E L.
Theorem 3.2. Under Assumptions 2.7 2.5 the consensus 0₂ converges to L almost surely, i.e.
lim sup,, inf inf--ec 1|0,, - 6' =0 a.s.
(10)
Theorem 3.2 achieved by decomposing the Markovian noise term VP,(O, X;) Vf(())) using the Poisson equation technique as discussed in 6 29 17). into a Martingale difference noise term, along with additional noise terms. We then reformulate (6) into an iteration akin to stochastic approximation, as depicted in (56). The subsequent step involves verifying the conditions on these noise terms under our stated assumptions. Crucially, this theorem also establishes that UD-SGD ensures an almost sure convergence of each agent to local minimum 0* E C, even in scenarios where the communication interval K2 gradually increases. in accordance with Assumption 2.3 ii). The detailed proof of this theorem is provided in Appendix C
Central Limit Theorem: Let U, é Ex (VF,((",)) represent the asymptotic covariance matrix
(defined in (5) associated with each agent E [N), given their sampling strategy (X%) and function
U, We assume the polynomial step-size On //// /nn, a (0.5, 1 and 7/4 > 0. In the case of = 1, we further assume 7. > 1/2p, where μ is defined in (8) For notational simplicity, and without loss of generality, our remaining CLT result stated while
VF.(0", :). Define U
conditioning on the event that {0, + 0²) for some 0* e L.

---

Theorem 3.3. Let Assumptions
2.7
2.5 hold. Then, 1/2 (0,- 0²) diet.
In
(0, V),
(11)
where the limiting covariance matrix V is in the form of
V So Mi dt.
(12)
Here, we have M- = - a E (0.5, 1), or M = Ia/27 - H if - 1, where H is defined in (
Moreover, let 8, = 1 - 0s and V = H For a E (0.5, 1), we have
vn(On (*) dist. (O. V'),
(13)
The proof, presented in Appendix D addresses the technical challenges in deriving the CLT for UD-SGD, specifically the second-order conditions in decomposing the Markovian noise term, which is not present in the i..d. sampling case [58 43 51). We decompose V (f,, X (....) into three parts in (48) using Poisson equation: + 1 S The consensus error 8r 8,, embedded in noise terms e and S1+1 is a new factor, whose characteristics have been quantified in our Lemma 3.1 but are not present in the single-agent scenario analyzed as application of stochastic approximation in [22 (9). The specifics of this analysis are expanded upon in Appendices [D. to D.3 We require 7. >> 1/2μ for a= 1 to ensure that the largest eigenvalue of M negative, as this is a necessary condition for the existence of V in (12) (otherwise integration diverges). In the case where there only one agent (N =),, V and V reduce the matrices specified in the CLT result of vanilla SGD
29 38 52). In addition, for a special case of constant communication interval in Assumption 2.3 and i.i.d. sampling as shown Table we recover the CLT of LSGD-RC in [1]
See Appendix E for detailed discussions.
Theorem 3.3 has significant implications for the MSE of {0..} for large time n, i.e., E| - 0 ||3
Inn Σ Ve; = 7, Tr( (r((), where e; the d-dimensional vector of all zeros except at the i-th entry. This indicates that smaller limiting covariance matrix V, according to the Loewner order, results in a smaller trace V and consequently a reduced MSE for large Consideration for smaller V will be presented in the next section, where agents have the opportunity to improve their sampling strategies.
Σx e [0 (0, - O*""")e R
Remark 2. Studies by [62 671 have shown that in DSGD with a fixed doubly-stond caobh--toochattic matrix W, the influence of communication topology diminishes after transient period. Our Theorem 3.3 extends these findings to Markovian sampling and a broader spectrum of communication patterns as in Table This extension is based on the fact that the consensus error, impacted primarily by the communication pattern, decreases faster than the CLT scale O( TT)) and is thus not the dominant factor in the asymptotic regime, suggested by Lemma 3.7
Remark 3. Recent studies have highlighted linear speedup with increasing number of agents N in the dominant term of their finite-sample error bounds under DSGD CT with i.i.d. sampling (43) and LSGD-FO FC with Markovian sampling [42]. However, our Theorem 3.3 demonstrates this phenomenon under more diverse communication patterns and Markovian sampling in Table 7 Iii the leading term
N in our CLT. Specifically, scales with 1/N, i.e. V=V/N, where V= N Ei= V, denotes the average limiting covariance matrices across all N agents and V;= M Me dl, suggesting
that the MSE E[ 8- [|2]] will be improved by L/N. A similar argument also applies to V in (13)
i.e., V /N, where V E. V and V H HUH
Impact of Agent's Sampling Strategy: In the literature, the mixing based technique has been widely used in the non-asymptotic analysis in SGD, DSGD and various LSGD variants in FL i.e., for each agent i E [N] and some constant C,
26 69
80
V (0, X V [:(0)]] S C|
(14)
where 9; is the mixing rate of the underlying Markov chain. However, typical non-asymptotic analyses often rely on A max; P; among N agents, i.e., the worst- porst-performing agent in their finite-time bounds 880 72). assume identical mixing rate across all N agents [42 68).
In contrast, Remark 3 highlights that each agent holds its own limiting covariance matrices V, and V which are predominantly governed by the matrix U, capturing the agent's sampling strategy
7

---

{X and contributing equally to the overall performance of UD-SGD. For each agent i, denote by U. and U. the asymptotic covariance matrices associated with two candidate sampling strategies {X.) and {Y respectively. Let V-X and V be the limiting covariance matrices of the distributed system in (12). where agent i employs {X2} and (Y respectively, while keeping other agents' sampling strategies unchanged. Then, we have the following result.
Corollary 3.4. For agent i, if there exist two sampling strategies {X) and {K such that U = Uj, we have VX > VY.
Corollary 3.4dirretly follows from the definition of Loewner ordering, and Loewner ordering being closed under addition (i.e., A > B implies A A +C> B+ C). It demonstrates that even single agent improves its sampling strategy from {X*] to {Y.). it leads to an overall reduction in V (in terms of Loewner ordering), thereby decreasing the MSE and benefiting the entire group of N agents. The subsequent question arises: How do we identify an improved sampling strategy ( over the baseline {
This question has been partially addressed by [57 48 38, which qualitatively investigates the 'efficiency ordering' of two sampling strategies. In particular, [38. Theorem 3.6 (i) shows that sampling strategy } is more efficient than {X,, if and only if [x(g) ; Ey for any vector-valued function g()) E IRd, Consequently, in the UD-SGD framework, employing a more
efficient sampling strategy {Yr)} over the baseline {X; by agent leads to Ex.(VF
> Ey: :)), thus satisfying U t U. This finding, as per Corollary 3.4 implies an overall improvement in UD-SGD.
For illustration purposes, we list few examples where two competing sampling strategies follow efficiency ordering: i) When an agent has complete access to the entire dataset (e.g., deep learning), shuffling techniques like single shuffling and random reshuffling are more efficient than i.i.d. sampling ii) When an agent works with a graph-like data structure and employs random walk, e.g.. agent i in Figure [. using non-backtracking random walk (NBRW) more efficient than simple random walk (SRW) 48 iii) A recently proposed self-repellent random walk (SRRW) is shown to achieve near-zero sampling variance, indicating even higher sampling efficiency than NBRW and SRW 22 This random-wall walk- based sampling finds a particular application in large-scale FL within D2D networks (e.g., mobile networks, wireless sensor networks). where each agent acts as an edge server or access point, gathering information from the local D2D network [37 32). Employing random walk over local D2D network for each agent constitutes the sampling strategy.
38 78
Theorem 3.3 and Corollary 3.4 not only qualitatively compare these sampling strategies but also allow for quantitative assessment of the overall system enhancement. Since every agent contributes equally to the limiting covariance matrix V of the distributed system as in Remark 3 a key application scenario is to encourage a subset of compliant agents to adopt highly efficient strategies like SRRW, potentially yielding better performance than universally upgrading to slightly improved strategies like NBRW. This approach, more feasible and impactful in large-scale machine learning scenarios where some agents cannot freely modify their sampling strategies, is unique aspect of our framework not addressed in previous works focusing on the worst porss-performing agent [80
68 72).
Experiments
In this section, we empirically evaluate the effect of agents' sampling strategies under various communication patterns in UD-SGD. We consider the I--regularized binary classification problem
1 N N
B
min f(0) A
Σ f((0), with f((0)
1 B
log [+ xi.) yts (0" = K
(15)
where the feature vector Xi.j and its corresponding label Vi. are held by agent i, with penalty parameter A set to 1. We use the ijcnnl dataset 14] with 22 features in each data point and 50k data points in total, which is evenly distributed to two groups with 50 agents each (N 100 agents
Note that SRRW is nonlinear Markov chain that depends the relative visit counts of each node in the graph. While application single-agent optimization has been studied in [3)] expanding the theoretical examination of SRRW to multi-agent scenarios is beyond the scope of this paper. However, we can still numerically evaluate the performance of UD-SGD with multiple agents on general communication matrices using SRRW a highly efficient sampling strategy in Section
8

---

1.54
Tir MERA 1N00
40 201W
MSE 1
10.
MSE 10.
5338A
MSE
10
43
12.
186 1960 1969 2018 anido Number of steps (1)
Namber of steps (r)
Number of steps (r)
10-1
Lid strceee STW
DIL
10"1
MSE E10
10
MSE F
10
SAM
MSE
10-5
Mauthe cntt
Malling La9ar
surool
10
100
307
30 307
1.5
301
Numberat of steps In)
Number stegs (n]
Number of steps On)
Figure 2: Binary classification problem. From left to right: (a) Impact of efficient sampling strategies on convergence. (b) Performance gains from partial adoption of efficient sampling. (c) Comparative advantage of SRRW over NBRW in a small subset of agents. (d) Asymptotic network independence of four algorithms under UD-SGD framework with fixed sampling strategy (shuffling, SRRW). (e) Different sampling strategies in the DSGD algorithm with varring topology (DSGD-VT), (f)
Different sampling strategies in the DFL algorithm with increasing communication interval.
in total) and each agent holds B 500 distinct data points. Each agent in the first group has full access to its entire dataset, and thus can employ i.i.d. sampling (baseline) or single shuffling. On the other hand, each agent in the other group has graph-like structure and uses SRW (baseline), NBRW or SRRW with reweighting to sample its local dataset with uniform weight. In this simulation, we assume that agents can only communicate through communication network using the DSGD algorithm. This scenario with heterogeneous agents, as depicted in Figure T is of great interest in large-scale machine learning [37 (2). In addition, we employ a decreasing step size "n- = 1/nn in our UD-SGD framework ( because it is typically used for the strongly convex objective function and is tested to have the fastest convergence in this simulation setup. Due to space constraints, we defer detailed simulation setup, including the introduction of SRW, NBRW, and SRRW, Appendix G.
The simulation results are obtained through 120 independent trials. In Figure 2(a) we assume that the first group of agents perform either i.d.d. sampling or shuffling method, while the other group of agents all change their sampling strategies from baseline SRW to NBRW and SRRW, as shown the legend. This plot shows that improved sampling strategy leads to overall convergence speedup since NBRW and SRRW are more efficient than SRW [3 25 Furthermore, illustrates that SRRW is significantly more efficient than NBRW in this simulation setup, i.c., SRRW > NBRW > SRW in terms of sampling efficiency. While keeping the second group of agents unchanged, we can see that shuffling method outperforms i.i.d. sampling with smaller asymptotic MSE. However, shuffling method may not perform perfectly for small time n due to slow mixing behavior in the initial period, which is also observed in the single-agent scenario in 665 38). The error bar therein also indicates that the random- waak sampling strategy has a significant impact on the overall system performance and SRRW has smaller variance than NBRW and SRW.
In Figure 2(b) we let the first group of agents perform iid.d sampling while only changing a portion of agents in the second group to upgrade from SRW to SRRW, e.g., 30 SRW 20 SRRW in the legend means that there are 30 agents using SRW while the rest 20 agents in the second group upgrade to SRRW. We observe that more agents willing to upgrade from SRW to SRRW lead to smaller asymptotic MSE. as predicted by Theorem 3.3 and Remark 3 This improvement in MSE reduction doesn't 't scale linearly with more agents adopting SRRW because each agent holds its own dataset that are not necessarily identical, resulting in different individual limiting covariance matrices V.
While maintaining i.i.d. sampling for the first group of agents, we compare the performance when the second group of agents in Figure empploy NBRW or SRRW. Remarkably, the case with only 10 agents out of 50 agents in the second group adopting far more efficient sampling strategy (40 SRW, 10 SRRW) through incentives or compliance already produces a smaller MSE than all 50 agents using slightly better strategy (50 NBRW). The performance gap becomes even more pronounced

---

when 20 agents upgrade from SRW to SRRW (30 SRW, 20 SRRW). We show that the performance of distributed system can be improved significantly when a small proportion of agents adopt highly efficient sampling strategies.
Figure 2 empirically illustrates the asymptotic network independence property via four algorithms
under our UD-SGD framework: Centralized SGD (communication interval K = L, communication
matrix W 11 11²/N); LSGD-FP (FL with full client participation, K 5. w 111/N) DSGD- VT (DSGD with time-varying topologies, randomly chosen from doubly stochastic matrices); DFL (decentralized FL with fixed MH- olH-generated W and increasing communication interval K; log())) after 1-th aggregation). We fix the sampling strategy (shuffling, SRRW) throughout this plot. All four algorithms overlap around 1000 steps, implying that they have entered the asymptotic regime with similar performance where the CLT result dominates, implying the asymptotic network independence the long run.
Figure [2e) and 2(f) show the performance of different sampling strategies in DSGD-VI VT and DFL. algorithms terms of MSE. Both plots consistently demonstrate that improving agent's sampling strategies (e.g., shuffling > iid sampling, and SRRW > NBRW > SRW) leads to faster convergence with smaller MSE, supporting our theory.
Furthermore, in Appendix G.2, by training 5-layer CNN and ResNet- 18 model collaboratively through a 10-agent network. The result is illustrated in Figure 3 where SRRW outperforms NBRW and SRW as expected. In summary, find that upgrading even small portion of agents to efficient sampling strategies (e.g., shuffling method, NBRW, SRRW under different dataset structures) improves system performance in UD-SGD. These results consistent in binary and image classification tasks, underscoring that every agent matters in distributed learning.
we simulate an image classification task with CIFAR-10 dataset 44
5 Conclusion
In this work, we develop an UD-SGD framework that establishes the CLT of various distributed algo- rithms with Markovian sampling. We overcome technical challenges such as quantifying consensus error under very general communication patterns and decomposing Markovian noise through the Poisson equation, which extends the analysis beyond the single-agent scenario. We demonstrate that even if only a few agents optimize their sampling strategies, the entire distributed system will benefit with a smaller limiting covariance in the CLT, suggesting a reduced MSE. This finding challenges the current established upper bounds where the worst-performing agent leads the pack. Future studies could pivot towards developing fine-gra mre-grained finite-time bounds to individually characterize each agent's 's behavior, and theoretically analyze the effect of SRRW in UD-SGD.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their constructive comments. This work was supported in part by National Science Foundation under Grant Nos. CNS- 200-200,423, IIS-1910749, and 2SS-2424484,
References
[1] Kwangjun Ahn, Chulhee Yun. and Suvrit Sra. Sgd with shuffling: optimal rates without component convexity and large epoch requirements. In Proceedings of the 34th International Conference on Neural Information Processing Systems, pages 17526-17535, 2020.
[2] Noga Alon, Itai Benjamini, Eyal Lubetzky, and Sasha Sodin. Non-backtracking random walks mix faster. Communications in Contemporary Mathematics, 9(04):555-66 603, 2007.
[3] Christophe Andrieu, Éric Moulines, and Pierre Priouret. Stability of stochastic approximation under verifiable conditions. SIAM Journal on control and optimization, 44(1):283-312, 2005.
[4] Ghadir Ayache, Venkat Dassari, and Salim El Rouayheb. Walk for learning: A random walk approach for federated learning from heterogeneous data, IEEE Journal on Selected Areas in Communications, 41(4):929-94) 2023.
10

---

[5] Anna Ben-Hamou, Eyal Lubetzky, and Yuval Peres. Comparing mixing times on sparse random graphs. In Proceedings of the Twenty-Ninth Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1734-1740. SIAM, 2018.
[6] Albert Benveniste, Michel Métivier, and Pierre Priouret. Adaptive algorithms and stochastic approximations, volume 22. Springer Science & Business Media, 2012.
[7] Pascal Bianchi, Gersende Fort, and Walid Hachem. Performance of a distributed stochastic approximation algorithm. JEEE Transactions Information Theory, 59(11):7405-771) 2013.
[8] Patrick Billingsley. Convergence of probability measures. John Wiley Sons, 2013.
[9] Vivek Borkar, Shuhang Chen, Adithya Devraj, loannis Kontoyiannis, and Sean Meyn. The ode method for asymptotic statistics in stochastic approximation and reinforcement learning. arXiv preprint arXiv:2 14427, 2021.
[10] V.S. Borkar. Stochastic Approximation: A Dynamical Systems Viewpoint: Second Edition. Texts and Readings in Mathematics. Hindustan Book Agency, 2022.
[11] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al. Distributed opti- mization and statistical learning via the alternating direction method of multipliers. Foundations and Trends@ in Machine learning, 3(1):1-122, 2011.
[12] Pierre Brémaud. Markov chains: Gibbs fields, Monte Carlo simulation, and queues, volume 31. Springer Science & Business Media, 2013.
[13] Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng. Handbook of markov chain monte carlo. CRC press, 2011.
[14] Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM transactions intelligent systems and technology (TIST), 2(3):1-27, 2011.
[15] VijaySekhar Chellaboina and Wassim M Haddad. Nonlinear dynamical systems and control: A Lyapunov-based approach. Princeton University Press, 2008
[16] Vishnu Pandi Chellapandi, Antesh Upadhyay, Abolfazl Hashemi, and Stanislaw H Zak. On the convergence of decentralized federated learning under imperfect information sharing. arXiv preprint arXiv: 10695, 2023.
[17] Shuhang Chen, Adithya Devraj, Ana Busic, and Sean Meyn. Explicit mean square error bounds for monte-carlo and linear stochastic approximation. In International Conference Artificial Intelligence and Statistics, pages 4173-4183. PMLR, 2020.
[18] Wenlin Chen, Samuel Horváth, and Peter Richtárik. Optimal client sampling for federated learning. Transactions on Machine Learning Research, 2022.
[19] Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. Artificial intelligence and statistics, pages 192-204, 2015.
[20] Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high-dimensional non- convex optimization. In Advances in neural information processing systems, volume 27, 2014.
[21] Burgess Davis. On the intergrability of the martingale square function. Israel Journal of Mathematics, 8:187-190, 1970.
[22] Bernard Delyon. Stochastic approximation with decreasing gain: Convergence and asymptotic theory. Technical report, 2000.
[23] Bernard Delyon, Mare Lavielle, and Erie Moulines. Convergence stochastic approximation version of the em algorithm. Annals of statistics, pages 94-128 1999.

---

[24] Thinh Doan, Siva Maguluri, and Justin Romberg. Finite-time analysis of distributed td (0) with linear function approximation on multi-agent reinforcement learning. In International Conference Machine Learning, pages 1626-1635. PMLR, 2019.
[25] Vishwaraj Doshi, Jie Hu, and Do Young Eun. Self-repellent random walks on general graphs- achieving minimal sampling variance via nonlinear markov chains. In International Conference on Machine Learning. PMLR, 2023.
[26] John C Duchi, Alekh Agarwal, Mikael Johansson, and Michael I Jordan. Ergodic mirror descent. SIAM Journal on Optimization, 22(4):154--1578 2012.
[27] Martin Dyer, Alan Frieze, Ravi Kannan, Ajai Kapoor, Ljubomir Perkovic, and Umesh Vazirani. A mildly exponential time algorithm for approximating the number of solutions to a multi- dimensional knapsack problem. Combinatorics, Probubility and Computing, 2(3):271-284, 1993.
[28] Mathieu Even. Stochastic gradient descent under markovian sampling schemes. In International Conference on Machine Learning, 2023.
[29] Gersende Fort. Central limit theorems for stochastic approximation with controlled markov chain dynamics. ESAIM: Probability and Statistics, 19:60-80, 2015.
[30] Yann Fraboni, Richard Vidal, Lactitia Kameni, and Marco Lorenzi. A general theory for client sampling in federated learning. In International Workshop on Trustworthy Federated Learning in conjunction with IJCAI, 2022.
[31] Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ramchandran. An efficient framework for clustered federated learning. In Proceedings of the 34th International Conference on Neural Information Processing Systems, pages 19586-19597, 2020.
[32] Yuanxiong Guo, Ying Sun, Rui Hu, and Yanmin Gong, Hybrid local SGD for federated learning with heterogeneous communications. In International Conference on Learning Representations, 2022.
[33] P. Hall, C.C. Heyde, Z.W. Birnbauam, and E. Lukacs. Martingale Limit Theory and Its Application. Communication and Behavior. Elsevier Science, 2014.
[34] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[35] Hadrien Hendrikx. principled framework for the design and analysis of token algorithms. In International Conference on Artificial Intelligence and Statistics, pages 489. PMLR, 2023.
[36] Roger A. Horn and Charles R. Johnson. Topics in Matrix Analysis. Cambridge University Press, 1991.
[37] Seyyedali Hosseinalipour, Sheikh Shams Azam, Christopher G Brinton, Nicolo Michelusi, Vancet Aggarwal, David Love, and Huaiyu Dai. Multi-stage hybrid federated learning over large-scale d2d-enabled fog networks. JEEE/ACM Transactions on Networking, 2022.
[38] Jie Hu, Vishwaraj Doshi, and Do Young Eun. Efficiency ordering of stochastic gradient descent. In Advances in Neural Information Processing Systems, 2022.
[39] Jie Hu, Vishwaraj Doshi, and Do Young Eun. Accelcrating distributed stochastic optimiza- tion via self-repellent random walks. In The Twelfth International Conference on Learning Representations, 2024.
[40] Mark Jerrum and Alistair Sinclair. The markov chain monte carlo method: an approach to approximate counting and integration. Approximation Algorithms for NP-hard problems, PWS Publishing, 1996.
[41] Thomas Kailath, Ali H Sayed, and Babak Hassibi. Linear estimation. Prentice Hall, 2000.
12

---

[42] Sajad Khodadadian, Pranay Sharma, Gauri Joshi, and Siva Theja Maguluri. Federated rein- forcement learning: Linear speedup under markovian sampling. International Conference on Machine Learning, pages 10997-1 1057, 2022.
[43] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pages 5381-5393, 2020.
[44] Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, 2009.
[45] Harold Kushner and G George Yin. Stochastic approximation and recursive algorithms and applications, volume 35. Springer Science Business Media, 2003.
[46] Anusha Lalitha, Shubhanshu Shekhar, Tara Javidi, and Farinaz Koushanfar. Fully decentralized federated learning. In Advances in neural information processing systems, 2018.
[47] Batiste Le Bars, Aurélien Bellet, Mare Tommasi, Erick Lavoie, and Anne-Marie Kermarrec. Refined convergence and topology learning for decentralized sgd with heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pages 1672-1702. PMLR, 2023.
[48] Chul-Ho Lee, Xin Xu, and Do Young Eun. Beyond random walk and metropolis-hasting samplers: why you should not backtrack for unbiased graph sampling, ACM SIGMETRICS Performance evaluation review, 40(1):319 -300, 2012.
[49] Jure Leskovec and Andrej Krevl. Snap datasets: Stanford large network dataset collection, 2014.
[50] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference on Learning Representations, 2020.
[51] Xiang Li, Jiadong Liang, Xiangyu Chang, and Zhihua Zhang. Statistical estimation and online inference via local sgd. In Proceedings Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 1613-1661, 02-05 Jul 2022.
[52] Xiang Li, Jiadong Liang, and Zhihua Zhang. Online statistical inference for nonlinear stochastic approximation with markovian data. arXiv preprint arXiv:2302.07690 2023.
[53] Yunming Liao, Yang Xu, Hongli Xu, Lun Wang, and Chen Qian. Adaptive configuration for heterogeneous participants in decentralized federated learning. In IEEE INFOCOM 2023. IEEE, 2023.
[54] Adwaitvedant S Mathkar and Vivek S Borkar. Nonlinear gossip. SIAM Journal Control and Optimization, 1435)1155511557 2016.
[55] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. coammunication-effccenn learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR, 2017.
[56] Sean Meyn. Control systems and reinforcement learning. Cambridge University Press, 2022.
[57] Antonietta Mira. Ordering and improving the performance of monte carlo markov chains. Statistical Science, pages 340-350, 2001.
[58] Gemma Morral, Pascal Bianchi, and Gersende Fort. Success and failure of cianptattoo-iiffuiinn algorithms with decaying step size in multiagent networks. IEEE Transactions on Signal Processing, 65(1 11:27)8-2299 2213, 2017.
[59] Wenlong Mou, Chris Junchi Li, Martin J Wainwright, Peter L Bartlett, and Michael I Jordan. On linear stochastic approximation: Fine-grained ruppert and non-asymptotic concentration. In Conference on Learning Theory, pages 2947-2997. PMLR, 2020.
13

---

[60] Giovanni Neglia, Chuan Xu, Don Towsley, and Gianmarco Calbi. Decentralized gradient methods: does topology matter? In International Conference on Artificial Intelligence and Statistics, pages 2348- 2358. PMLR, 2020.
[61] Alex Olshevsky. Asymptotic network independence and step-size for distributed subgradient method. Journal of Machine Learning Research, 23(69)11-33) 2022.
[62] Shi Pu, Alex Olshevsky. and Ioannis Ch Paschalidis. Asymptotic network independence in distributed stochastic optimization for machine learning: Examining distributed and centralized stochastic gradient descent. JEEE signal processing magazine, 37(3):114-1) 122, 2020.
[63] Christian P Robert, George Casella, and George Casella. Monte Carlo statistical methods, volume 2. Springer, 1999.
[64] Sheldon M Ross, John J Kelly, Roger Sullivan, William James Perry, Donald Mercer, Ruth M Davis, Thomas Dell Washburn, Earl V Sager, Joseph B Boyce, and Vincent L. Bristow. Stochastic processes, volume 2. Wiley New York, 1996.
[65] Itay Safran and Ohad Shamir. How good is sgd with random shuffling? In Conference on Learning Theory, pages 3250-3284. PMLR, 2020.
[66] R. Srikant. Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application TD Learning. arXiv e-prints, page 1rXiv:2401.15719, January 2024.
[67] Sebastian U Stich. Local sgd converges fast and communicates little. In International Conference on Learning Representations, 2018.
[68] Tao Sun, Dongsheng li, and Bao Wang. On the decentralized stochastic gradient descent with markov chain sampling. IEEE Transactions on Signal Processing, PP, 07 2023.
[69] Tao Sun, Yuejiao Sun, and Wotao Yin. On markov chain gradient descent. In Advances in neural information processing systems, volume 31, 2018.
[70] M Vidyasagar. Convergence of stochastic approximation via martingale and converse Iyapunov methods. arXiv preprint arXiv:2205.0130: 2022.
[71] Hoi-To Wai. On the convergence of consensus algorithms with markovian noise and gradient bias. In 2020 59th IEEE Conference on Decision and Control (CDC), pages 4897-4902. IEEE, 2020.
[72] Han Wang, Aritra Mitra, Hamed Hassani, George Pappas, and James Anderson. Federated tem- poral difference learning with linear function approximation under environmental heterogeneity. arXiv preprint arXiv:2302. 022222222222.2....2222222222. 2023.
[73] Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H. Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. In Advances in Neural Information Processing Systems, volume 33, pages 761 7611-7623, 2020.
[74] Shiqiang Wang and Mingyue Ji. unified analysis of federated learning with arbitrary client participation. In Advances neural information processing systems, 2022.
[75] Stephan Wojtowytsch. Stochastic gradient descent with noise machine learning type part i: Discrete time analysis. Journal of Nonlinear Science, 33(3):45, 2023.
[76] Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai. Brian Bullins, Brendan Mcmahan, Ohad Shamir, and Nathan Srebro. local sgd better than minibatch sgd? In International Conference Machine Learning, pages 00334-10344 PMLR, 2020.
[77] Hao Ye, Le Liang, and Geoffrey Ye Li. Decentralized federated learning with unreliable communications. IEEE Journal of Selected Topics in Signal Processing, 16(3):487-500, 2022.
[78] Chulhee Yun, Shashank Rajput, and Suvrit Sra. Minibatch vs local SGD with shuffling: Tight convergence bounds and beyond. In International Conference on Learning Representations, 2022.
14

---

[79] Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Open problem: Can single-shuffte sgd be better than reshuffling sgd and gd? Proceedings of Thirty Fourth Conference on Learning Theory, volume 134, pages 3653-468.. PMLR, Aug 2021.
[80] Sihan Zeng, Thinh T Doan, and Justin Romberg. Finite-time convergence rates of decentralized stochastic approximation with applications in multi-agent and multi-task learning. /EEE Transactions on Automatic Control, 2022.
[81] Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data, arXiv preprint 1806::88060000 2018.
15

---

A Discussion of Assumption 2.3
A.1 Suitable choices of K;
When wet let K2 ~ log(!) (resp. K2 ~ log log())))) as suggested by [51] trivially satisfies
Kr, = 1/2(+111(1+11)) o(n 1/((=+1))))))))))))))(())))))/ since by definition KT, < K, log(n nn) (resp. log log(n)), and log(n) ) (resp. log log(n) = o(n')) for any c O. Besides, Σn t/ En 2 x 2 Σn n (]]((++]) En n 11(.- To ensure Σn nh < co, is sufficient to have 2 2(L+1)e-2 or equivalently, e 1/2(L + 1). Since e can be arbitrarily small to satisfy the condition.
Σn ni < 30 is satisfied. When K₁ ~ log((), we can rewrite the last condition as
1/
1
Kt+1
74+1 +
log(1 + +1) + L+1
11 1mar+1
KL+1
m +1
log(l) +
(16)
Ki+1
+ )
log(1 + 1) + L+1
1 +
log(!) +1
where have nı log((!) such that K4+1/n log(1 (1 1)/ log(!!) + 0 and log(l + 1)/ log(l) + 1 as I + co, which leads to limn-+co 7m. Pm-11/mm++7 = 1. Similarly, for K₁ ~ log log(U), we
have ny log log([]'_ log(s)) such that Ki-1/m /nu log log(! + 1)/ log log([I'-- log(s)) 0 and log log(1 + 1)/ log log(1) + as + oc, which also leads to lima-to 0m ///t1///1j110 //111+111111111
A.2 Practical implications of Assumption 2.3 ii)
In this assumption, we allow the number of local iterations to go to infinity asymptotically. In distributed learning environments such as mobile, IoT, and wireless sensor networks, where nodes are often constrained by battery life, increasing communication interval in Assumption 2.3 plays a crucial role in balancing energy costs with communication effectiveness. communicate more frequently early leading to faster initial convergence to the neighborhood of 8" Then, we slow down the communication frequency between agents to conserve energy, leveraging the diminishing returns accuracy improvements from additional communications.
allows agents to
Consider the scenario where devices across multiple clusters collaborate on a distributed optimization task, utilizing local datasets. Devices within each cluster form a communication network that allows a virtual agent to perform heterogeneous Markov chain trajectory via random walk, or an i.i.d. sequence in complete graph with self-loops, depending on the application context. Each cluster features an edge server that supports the exchange of model estimates with neighboring clusters. By performing K local updates before uploading these to the cluster's edge server, the model benefits from reduced communication overhead. As the frequency of updates between devices and edge servers decreases optimized by gradually increasing K K-w effectively lower communication costs, particularly as the model estimation 6, is close to 8*.
B Proof of Lemma 3.1
Let A IN - J E RNNN and JI J. @ Ia E NdxNNd, where @ is the Kronecker product. Let θ, = [01)T .... (TT) E R.dd Then, motivated by (58). we define a sequence Φn و NihnT1 O E Nd in the increasing communication interval case (resp. 6,, --1 J O in the bounded communication interval case), where 7/+1 is defined in Assumption 2.3 ii). JI =
On N (11" I,)O,, represents the consensus error of the model.
We first give the following lemma that shows the pathwise boundedness of on-
2.3 2.4 and 2.5 hold. For any compuct set Ω C Rd the sequence on satisfies sup,, B @m. 0 (0,EE)) co.
Lemma B.I. Let Assumptions 2.7
Lemma B.I and Assumption 2.3 ii) imply that for any n 2 0, E - =
w [1] Øn 11 (()en))
< Cn for some constant C' that depends on C₁ and Ω. Along with Assumption 2.4 such that [[]] O, is always bounded per each trajectory, it means
[| O, 1nggn-1(9,60) En) O(7m)
16

---

Let {9m Im20 be sequence of increasing compact subset of R N' such that Um Jm IR No. Then, we know that for any 2
IJ On (0 (0) (
(17)
17 indicates either one of the following two cases:
there exists some trajectory-dependent index m' such that each trajectory {O,, Jn20
always within the compact set 9m', i..., (0 = 1 (satisfied by the construction of increasing compact sets {9'm Jm2a and Assumption 2.4 and we have [ (nn.) such that lim e, = O:
On will escape the compact set S2m eventually for any m 0 in finite time such that 1 (1ge-1100 Emmm 0 when n is large enough.
We can see the second case contradicts Assumption 2.4 because we assume every trajectory { h20
within some compact set. Therefore, (17) for any m 2 O is equivalent to showing [T_ e, =
O (m)) and lim J1 G O. Under Assumption 2.3
obtain similar result J 6,,
0 (Yn) by following the same steps as above, which completes the proof Lemma 3.1
Proof of Lemma
B.
We begin by rewriting (6) in the matrix form,
OnII = Wn (On To+1 VF X.,)),
(18)
where X, (X,, n X2 ... X and VF(O., X,) A ( nJ X VFN(ON ( E Ei Oz E Rdd and we have 10 0 = @ L,),, E Ndd
RNd Recall On N
Case 1 (Increasing communication interval Kr ): By left multiplying 18) with (11 & La). along with Yn+1 7/+11
KL+1 in Assumption 2.3 ii), have the following iteration Fe41
VF Xn)
N (11 @ LL)0
(11 8 L.) - m1t1 N (112 & Ia)
(19)
N
KL+1
where the equality comes from (11T s I,) = (11 La) N (11 2 Ia). With 18 we have
and 19
1
aafi
(11T L1)0at1
N
VF(On, X,)
Wn
(11 & L1) On Mat1 Wn N (117 &Ia)
N
K Tats
=J W, & LIJ O, Tn 1m+1 (J (,, @ Ia) VF(O,, Xn)
(20)
k!++1
-] Wn 8 Ia) n VF(O,,,
L+1
Tat1
where the second equality comes from W,, - N (11" @ La) = (W, - -1
and (J_ W, @ L))J J W I. J W, Ig. Let an & ///// dividing both sides of 20 by 72 gives
VF(O,, x,)
Dat1 = C W, & I2)
On
(21)
KK-11
17

---

Define the filtration 1n2 as Fn a
o Xo. W. 11
X1. W1." Xn-1, Xn)
Recursively computing (1
w.r. the time interval [ny, R441 gives
ni+1
nt41-1
0ni11
II
0k
J
II
W &
La
k=m++1
k=n
n1-1-1 1
m141-1
VF X
II d
J
II
W
& Ld
(22)
K
Li=k+1
k=
7a-+1
A1-1-1
Mm++1 7j+42
VF X&)
(J1 Wm, @ Om
(J mi @ La)
K[+1
where II is the backward multiplier, the second equality comes from J_ W.J. = J1 Wn
and W IN for k & {ni). In Assumption 2.5 we have ||Ew~P [WJJ J_ W||
E WW WTW - J] I C₁ <1. Then,
Ell 511lmm41112
2
11
Dny EW
Wn, @ La)² (J_ Way @ La) pn.
0m++++
m141-1
Thit1
VF X²)) K
2E
Pnj (J1 W 8 Ia)² (J W.W, m. I
Fru
117k+2
+
Σ
7o-+1
(J1 Wa, 2 Ia)
VF Xx)
Fm
7K+2
K
k=m
2
7m1+1
EW
Ew
[W"", n. J1 Wn. 2 [a)] On
my
7m1+1+1
(23)
7141111
-2
Mm++1
E
Iu (WT J W., & La)
V R: X
Fni
M1111+11
KL+1
k=n
1ny+1
R141
OF X.)
+
E
(J W. & Ia)
Fm
M1441+1
KL-1
A=RI
Mor+1
Ci Cill@nel1
+2
Mm++1
Cilloni |E
Σ
VF Xx)
F
K
k=
I+1
+
Tnu+1
CEE
Ri41
Σ
VF
Fr
KL+1
K=RI
where the first inequality comes from JJJ J_ and 7k+2 M1 for k [my, M4+1 Then, we analyze the norm of the gradient [Qx. Xx)ll in the second term on the RHS of 23 conditioned nı such that SUP (.. nz: X
Frg By Assumption 2.4
assume On, within some compact set Ω time < Cp for some constant Cp. For n nr + and any
X E X1 x Xe X X XN. we have
VF X)I| & ( X) VF X) + (F X)||-
Considering N
VF mpy X)I1
we
have
supx /F X)I1
supx
(0 X²I1 < NC2 such that || ( X)|l VNCo. In addition,
18

---

have
N
VF X) - 2F(OR,, X) =
VE: m1 x1) - VPi(On x*))
i=1
N
L (2110 -02, 12
(24)
i=1
$
Σ
1my+1 2 )1
S +1 C2NI2
such that |VF m1, X) VF(O... X)1I S 7m CavNL. L. Thus, for any X,
|VF(On, x)]| S (1 mm 11)) VNCa.
(25)
For n = n4 + and any X, we have
|V X) S (V +2, X) - +| I
Similar to the steps in 24). we have
VVF X) x)(
Im L VF,
X
(26)
= -
VF VF +11l
Then, (F X)|| S (1 + 22+ supx ( m1+ X and, together with 25 have
VF + m2 X|| S (1 Tm L) mi++1 ))
(27)
By induction,
V (O m0 X) S I1 (1 + Tn. L) NC for m E [1, K1+1 - 1].
The next step is to analyze the growth rate of ITm + 7msts)) L.). By x S e for x 2 0, we have
II + tol+ S e 7atts.
For step size 7n 1/n, have I. Exe Ports I. 1/(m++)) < <1E 1/8 L(log(m)+
1) such that 11 + )o < (em)4 Then,
L-+ VF(OR, X
m+1-
1
K++1-1
VNeCCa
Σ m
K
L+ 1+1
KL+1
(28)
I+1
S SVNee
where the last inequality comes from Ikmn-1 m < Ket1(K41 - 1)2 KL+1 We can see the sum of the norm of the gradients are bounded by - which only depends on the compact set at time n T4g-
Let 81 E 1). Since from Assumption 2.3 ii), lim 7 Mo4411 = 1, there exists some large enough such that ( Thyt1
10141 )
82 (61 + 1)/2 < 1 for any > la- Note that 51
depends only on C and is independent of F,, Then, let Ö. = VNee Ca. we can rewrite (33 as
Blllom 11 [m flm 1 28, Co + 81 8,
(29)
<52llom, 112 Man
where My satisfies Ma 80h/(1 81) + 8, C2 which is derived from rearranging (29 as Ma 2 (01 @m) 112 + 28, Cn 2m + 6,07 and upper bounding the RHS. Upon noting that I (0 s L, (0yen), we obtain
|m 1| Issm 19, ea)
S E3E
[| || 12 11 (0,60)] + Ma.
(30)
19

---

The induction leads to B[ 12 1 nysm, Eo
S
82
m441 nio Billdnig I (0, (0,
M/(1 82) < 2o for any 1 2 lo- Besides, for m E (ni, m441), by following the above steps
23 applied to (21), we have
E|| pm Fral 1
+1
11 112 +
Mmu+1
2
E
VF Xx)
Fm
7m++1
1m++1
K[41
Ammm
(31)
+1
VF O Xx)
+
E
F
7m+1
K
By 28 already show that kkm
conditioned Frg. Therefore, E mm 1 10, oo for m E (ni, (141) This completes the boundedness analysis of Elloon (0,
K
Case (Bounded communication interval Kr I K): In this case, we do not need the auxiliary step size ?/2 and can directly work "n 1/n" for (0.5, 1]. Similar to (20), we have
1 (111 @ 11) (J+ W, @ Ia) (7, 110, (I,
O
(32)
and let bn A ma/ dividing both sides of above equation by 7x+2 gives
2n+1 (J Wn, @ Ia) (on, VF xn))
(33)
Then, by following the similar steps in 22 and 23 obtain
2
M141
0m 112 1
+o
1m 11 + 2m E Ci
Σ k=
VF(Ok, Xx)
Fri
7n-=++1/
(34)
+ E
Σ
VF(Ox,
X&)
F
Also similar to
25
28
can bound the of the norm of the gradients
R141-1
k
VF X²))
<
(1+
(1+))) VNCa.
(35)
A==
k=
L=
Now that K2 is bounded above by K, II (1 Ys+1 I.) s el Liim rot1 < c CIE Tots = Then, we further bound (35) as
Ok.
m441-1 VF X S SVNKCRCo.
(36)
k=
The subsequent proof is basically a replication (29) (31 and therefore omitted.
C Proof of Theorem 3.2
We focus on analyzing the convergence property of 0, which is obtained by left multiplying 18) with N (1T Iz), i.e.,
1
on+1 = N (1T @ 12)0
(37)
1 (1T VL) X.).
O 7+11 N
where the second equality comes from Wn being doubly stochastic and + (1T @ LaW,, 1 W. @ I,) + (1" & Ia)-
For self-contained purpose, we first give the almost sure convergence result for the stochastic approximation that will be used in proof.
20

---

Theorem C.1 (Theorem 2 [23 Consider the stochastic approximation in the form of
n+t 8n + In+1h(Bn)) + In+1C++I + 7n41n++1
(38)
Assume that
Cl. w.p.1, the closure of 102 is compact subset of R
C2. {ra is decreasing sequence of positive number such that En Yn2 0c;
C3. w.p.1, limp-+20 En=1 On exists and is finite. Moreover, lim I' = 0.
C4. vector-valued function continuous on R and there exists continuously differentiable function V Bd R such that (VV(0). for all R Besides, the interior of V(C) is empty where L _ (0 TR (VV(O),)(O)) 0}.
Then, w.p.I, lim sup, d(On,, L) O.
We rewrite
37
onl1 On 7n+1 (1 LL) Xa)
N
[ (.(( VI(OW)
On - 7n+1 V((mo)) - 7n+1
N 1=1
(39)
N x
Σ
VR
1 Σ V..)))
we have 7n+1
N
N
and work on the converging behavior of the third and fourth term. By definition of function v.((),,
N
I'
(((())) - ((()))) =
N -V(0))
(40)
By the Lipschitz continuity of function V,,., X) in
we have
N Σ LIIo 0m ||a/l S N
On N aar & L.oo.
L VN
1 0,
(41)
where the second inequality comes from the Cauchy Cauchy-Schwarzz inequality. In Appendix we have shown lim, o, = O almost surely such that lim,- fn almost surely.
Next, we further decompose the fourth associated with the same state space X. define the operator Ph
(39.. For an ergodic transition matrix and function
p²z) & Eyex (* y)y for the
k-step transition probability (* y). Denote by Pi.... PN the underlying transition matrices of all N agents with corresponding stationary distribution πi, ........ NT.. Then, for every function V FF -) X; + Rd, there exists corresponding function mg (-) X - Rd such that
mg (z) - P. (x) = F f..)
(42)
The solution of the Poisson equation (42) has been studied in the literature, e.g., self-contained purpose, we derive the closed- mg: (I) from scratch. First of all, we can obtain function mg: (x) in the recursive form as follows.
For
mgg (I)
VF.00' - (IT
(43)
is not hard to check that satisfies Note that by induction we get
p 1 (P. 1(TT)))* V
(44)
21

---

Then, we can further simplify
43). and the closed-form expression of mp (x) is given
mgi (z)
P; I(T,)) (z. Vs((0')
yEA:
+
Σ
[P] - (Z: Vfi(0')) +...
yE
(45)
8
Σ
Σ
[.. 1(T:)²'"
(c. .9) vf((('))
yEA;
Σ
-
(C.V)(VE - vf(()'))
yEA;
where the fourth equality comes from Note that the so-called 'fundamental matrix' (I P. 1(TT,)²) exists for every ergodic Markov chain X from Assumption 2.2 Since function VA, is Lipschitz continuous, we have the following lemma.
Lemma C.2. Under assumption (Al), functions mg (z) and P P.mo (x) are both Lipschitz continuous in O' for any x E Nx
Proof. By (45 for any 01, 02 E Ied and x Xr have
mof (x) mag (z)) -
Σ
(I - P. + 1(T,)) (I, (VF((()))) - VVF,(F
ME
(46)
SC,
max yEA:
(F. VF. v)ll + V.)(0)) v
<(C,L + 1) 8i1l,
where the second inequality holds for a constant C2 that is the largest absolute value the entry in the matrix (I - P. + ) Therefore, mo= (z) is Lipschitz continuous in 0¹. Moreover, following the similar steps as above, we have
P Pm (x) P.moa (x)
Σ DE
P.( - Σ Pi y)m
DEA
Σ p1( (mog(u)
mag (1))
VEN.
(47)
Σ Pi v) |moa (v) may (v)
De
< [x| | (v) - mmg (w)l |X 1)110 - 0
such that P.mg: (I) is also Lipschitz continuous in 0;, which comletes the proof.
Now with 42 we can decompose VF:(O) X;)
v)((0())
V,, X Vi((0))) =ma; (X - P P.mp (X:) -ag (X() Pamgy (Xp=1)
chat
Pimas (Xi-1) Pamge (X:)
(48)
wh+1
Pamar +1 (X))
Pormo (Xx)
sh
22

---

Here ( is Martingale difference sequence and we need the martingale convergence theorem in Theorem
Theorem C.3 (Theorem 6.4.6 (64) For an Fn-Martingale Sn, set Xn-1 -n S 1sp52
1- If for some
= a.s.
(49)
then Sn converges almost surely.
We want to show that En T 1 Bllle + [[F
such that Σ Yne, converges almost surely As we can see in (45). with Lemma C.2 and Assumption 2.4 for a sample
by Theorem C.3 path (9,, within compact set 92), sup, Ilmm; (x)]l < and sup, [| (+) surely for all Nr This ensures that e is an L2-bounded martingale difference sequence, i.c. sup, ||ellll S sup,, (l)ma; (X4+1) ++++1)++110 |||||||,mm P.m.g (x;)Il) S Da < co. Together with Assumption 2.3
almost
we get
Σ the Bllle 113 Dn Σ m- 30 a.8.
(50)
and thus En Tne converges almost surely. Next, for the term v/ we have
p Σ k=0
Σ 1 v k=0
(1411 - 7x) + 7or0 - 11+12 p+1
(51)
As is shown before, for a given sample path, m,g (x) is bounded almost surely for all n and E X such that sup,, || almost surely. Since lim, (7n+1 -"n) O, we have lim,,- (7n+1 - -Y,),, = 0. Note that there exists path-dependent constant C' (that bounds ||,)]) such that for any m,
(r4+1 - mw
SC
Σ (nh 7k+1) C(1m 7n-1) Cim-
(52)
Since limn-roe Yn = 0, there exists a positive integer M such that for all n 2 m 2 M, Tm < <//C
for every > 0. Therefore, o - ) Jp20 is Cauchy sequence and - (7x+1 7k T converges by Cauchy convergence criterion. The last term of
and Σi=m (7++1 - 1 0c
(5T) tends to zero. Therefore, ce ( (v) v converges and is finite.
For the last term gi Lemma leads to
C"
C"
10
0
0 S
O 10 - Onll- VN
(53)
for the Lipschitz constant C' of (m) However, the relationship between 0n, and 0 is not obvious in the D-SGD and FL setting due to the update rule (18) with communication matrix W.. unlike the classical stochastic approximation shown in (38). We come up with the novel decomposition of E,, which takes the consensus error into account, to solve this issue, i.c.
t Pamos (X)) P. Pamo., 12 (xx)
Pime, (X;) P.mo; (X:)
(54)
+ Pame (X.) Pimo, (xx))
23

---

Using the Lipschitzness property of (.mo(X) in Lemma C.2 we have
(1 - 0n+1ll + 110z11 0n + 100 -02ll)
N
C'
an11 N
1
(11? @ Ia) Ox+1
+ C"
On
N (111 O,)
1
VN
+C
10z+1 0z1
[1 || + || 0,l) C" |0 0n!
- (1T s V.. N
1
Xm|||
VN (131 + | O, (]) Ch
(55)
In Appendix B we have shown lim,-+00 J. On 0 almost surely. Moreover, | (1 %
Va) x,)ll Il is bounded per sample path. Therefore, limn-soe N Σ || = such that lim Ei=1 sm+1 almost surely.
To sum up, we decompose (39 into
N (c + v - 2/+1 + Sh+1)
01+1= = = - nn+1 (f,n - Mat1an Mnt1
Σ
(56)
N
Now that limp-roc En=1 1 EN Tne and lim En N 1i=17441 (ut v v converge N and are finite, limm Tn O, lim, N i= di 0, all the conditions of C3 in Theorem C.I are satisfied. Additionally, Assumption 2.4 correspons to C1, Assumption [.3 meets C2, and C4 is automatically satisfied when choose the 1yaрunov function V(0) f(0). Therefore, sup, infg- ec | - 0 0.
1
D Proof of Theorem 3.3
To obtain Theorem 3.3 need to utilize the existing CLT result for general SA in Theorem D.I and check all the necessary conditions therein.
Theorem D.1 (Theorem 2.1 (2)). Consider the stochastic approximation iteration assume
Cl. Let 8 be the root of function h, i.e., h(0*) O, and assume lim,, On = 0 Moreover, assume the mean field is twice continuously differentiable in a neighborhood of 0 and the Jacobian H 2 Vh(0") ) Hurwitz, i.e., the largest real part of its eigenvalues < 0;
C2. The step size En Ya Do, En 7 oc, and either (i). log(7n-1/7m) o(Tn), or (ii). "n// for some 7 > B/2
C3. sup,, || < oo almost surely for any E [N];
C4. (a) {en nen is an F Fa-Mariingale difference sequence, i.e., B[en|Fn-ill = 0, and there exists > such that sup.20 E [[ [Fn-1] oo;
(b) Blent1e4411 = U+D + D where U is symmetrie positive semi definit matrix and
D (A) 0 almost surely,
(57)
lim, E
m k=
D
0.
C5. Let =r + .T is F., Fa-adapted, and
(1)
o
a.s.
(58)
7
Σ k=
r
(2)
= o(1) a.s.
24

---

Then,
(0n )*)
dist. No0 V),
(59)
7n
n-000
where
VH + HV -
in case C2 (i), in case C2 (i).
(60)
V(L + 22, 27, = -2 U
Note that the matrix U the condition C4(b) of Theorem D.I was assumed to be positive definite in the original Theorem 2.1 [29]. It was only to ensure that the solution V to the Lyapunov equation (60) positive definite, which was only used for the stability of the related autonomous linear ODE (e.g.. Theorem 3.16 [IS] Theorem 2.2.3 [36]) However, in this paper, we do not need strict positíve definite matrix V. Therefore, we extend U to be positive semi-definite such that V is also positive
semi-definite (see Lemma D.2 for the closed form of matrix V). Such kind of extension does not change any of the proof steps in [29]
D.1 Discussion about C1-C3
Our Assumption 2.1 corresponds to CI by letting function h(0)= - -V therein. We can also let
T4 in Theorem 3.3 large enough to satisfy C2. The typical form of step size, also indicated in [2)]. is polynomial step size "/n ~ > //nn for E (0.5, 1]. Note that a E (0.5, 1) satisfies C2 (i) and a = satisfies C2 (ii). Assumption 2.4 corresponds C3
D.2 Analysis of C4
To check condition C4, we need analyze the Martingale difference sequence {er Recall en ma:; (Xx) - P., (Xn=1) such that there exists constant C,
E
[1
2+ |F
S CIE
[|mma (xx)) 2+7 + P| (X 1)1= 2+
Fr
-C Σ Pi(X Y) mm: (r) |+ + +C
| P.mp: (X (x 24
(61)
YEX:
Since [|mm (Y)ll < almost surely by Assumption 2.4 and X is finite state space, all time
we have
Σ Pi((i-)))) [|mo (Y) 2+T <0 0.8.
(62)
Yea
and there exists another constant C' such that by definition of P.ma: (X% 1), have
P.mgg (X: (Xt= 1l| 2+ C P, Y) Ima (Y) 2+r oo a.s.
(63)
YEAi
Therefore, Bille [tT < 00 a.s. for all and C4.(a) is satisfied.
We now turn to C4.(b). Note that for any # j. have Elei (( [F Ble/
(((()T1TIIAA = due to the independence between agent and j. and Bleh+11 [Fn] = 0. Then, we
have
Fn
E
(64)
n+1
N
n++
N22
The analysis of E[ee) (c 1 is inspired by Section 4 29 and Section 4.3.3 22
where they constructed another Poisson equation to further decompose the noise terms therein Here, expanding
*Theorem D.1 slightly modified terms of condition C3, which is mentioned a special case in Section 2.2 (29 For the sake of mathematical simplicity, we stick to condition C3 the proof.
'However, we note that 20 2 considered the Lipschitz continuity of function Fg (2:) defined in 668 an assumption instead of conclusion, where we give detailed proof for this. We also obtain matrix U. an explicit form, which coincides with the definition of asymptotic covariance matrix and was not simplified in
(29] The discussion the improvement of U, is outlined in Section 3.2, which was not the focus of 29 22 and covered therein.
25

---

gives
E c (1 Fal =Blma; (X,, maa (x,) [Fn) + Pamog (X (Pomos (X T
El/mg
[x) (P:ma) (X T - -Pomps (X (x
Frl
Σ P, P. ymgg (y)mog (v)²
-P, -P,mp: (X (Pempg (x==
DEA.
(65)
Denote by
G.(0",) x) - Σ P. y) (y)mg (v)² P.ma (x) (P (Pamp NEX,
(66)
and let its expectation w.r.t the stationary distribution n, be gi()') A R (G((0,, we can construct another Poisson equation, i.c..
E 1c )' Fr]
Σ
x
X
(67)
-G x - (((())
=P0 (x--1) - Pippj 03 ( (x=
for some matrix- valued function yp² Rd Xr - Rdddd Following the similar steps shown we can obtain the closed- expression
42)
455
pg (x) = Σ
[I
- + +(T+))² (I, (r,)),((0',c) g:((").
(68)
yEA:
Then, decompose
65 into
Go x = (0)) ge (0 (0))
+ Po: (x P PiPig (X n-
+ Pog (X
S (Xr
U.
D
D
((2.)
D (2,6) k.
(69)
Let U S D
D
D
D (2,a)
and D (2,b)
N2 (2,))
N2
1=1 In
N
1=
in
NZ Σ
D in we want to prove that D satisfies the first condition in C4, and D (2.a)
D (2.0)
meet the second condition in C4.
We now show that for all i, G. x) Lipsehitz continuous in 0c E for some compact subset Q Rd. For any x E X, and 0i 03 E Q2 we can get
Ima (x)mmo (x)²² møs (x) (mg (I
- =l|ma; (1)) (w) may (z))² (mo: (z)- (z)) (x)
(70)
< <||ma; (z)) ma: (x))l (m)) (x) ||mag (x)
<C||0i f2ll.
for some constant C, where the last inequality comes from ||mag (x)] oc since of Ω and the Lipschitz continuous function mg= (z). Similarly, we can get [P,ma (z)-P.mp- (x)]l x C' --1l- Therefore, G2(0', ,z) and (0') are Lipschitz continuous in 0* E Ω for any E Xz
For the sequence (D( i.nnnoo by applying Theorem 3.2 and conditioned on lom O, 0 for an optimal point 6" E L, we have lim,- (l.((%)) g, (0*) < lim,- C| l* = 0. This
implies D (1) 0 for every i [N] and thus ( 0
almost surely, which satisfies the
s.n first condition in (57).
in n20. we use Burkholder inequality (e.g., Theorem 2.10 33 21) such that for p 2 and some constant Cp,
For the Martingale difference sequence (D (2.a)
p/2
E
(2.a) im
< C,
Σ D (2.a) 2
(2.a)
(71)
26

---

By the definition 666 and Assumption 2.4, for a sample path, sup,, ||G; as well as sup,, (g.((")) lI oo, which leads sup, llyee (a) oo for any X, because of (68).
(e... =>|l < oc for any E X.
Then, we have sup, D (2.0) || - C < oo for the path-dependent constant C. Taking 1 and we have
a
(2.0) | F
lim In Cp To 220
x lim C,CrvV= a.s. n=000
(72)
Thus, Lebesgue dominated convergence theorem gives
lim Th Cy 100000
Σ
I ID km
1|2
E
lim Yn Cpp 10000
[D
(2 1,8
1|2
0
and we have limn- 7n [1 E
(2.0) in
||]
=0 O.
For the sequence (D
(2,6)
In20. we have
1,
D (2 i
Pog (X 11
sbz_ (Xi-1) + pp;
s/g (X;)
k=1
(og (X -6, (X 1 (X (x) (X Poz (Xb=1)
=
k=1
+ Pog (Xx)
vpbg (X.).
(73)
Since G, x)) and gi (0)) are Lipschitz continuous in 0 Ω2 po (z) is also Lipschitz continuous in 8 and is bounded. We have
D (2
Σ Pog (X
Pb. 1x
+ pb (X6) + 1 (xx)
Σ Peg (x
sb.. (X
Di
(74)
D2D Dank + D1
k=1
where 11.%/ (xi) + 11 (X < Dj for a given sample path, D2 is the Lipschitz constant of ph (x), and Fx x'I| S
Do for any x² E ll and X E X'. Then,
Yn
Σ D
(2.6) i
s D2D Σ Tk + + D1 as n +
(75)
because 7/n satisfied.
Ex=1 7kk
O(n (2n) by assumption 2.3
Therefore, the second condition of C4 is
D.3 Analysis of C5
We now analyze condition C5. The decreasing rate of each term in (56) has been proved in Appendix C Specifically, by assumption 2.4 there exists a compact subset for given sample path, and
we have shown that ( On,) a.s., which implies
(r o(v7n) a.s.
For 1. E c in the case of increasing communication interval, N Σm ci = 0
N
Mh,), by Assumption 2.3-ii), we know (in + mT)//TH = TTe + v K' = o(1) such that | E = o(van) almost surely. On the other hand, in the case of bounded communication interval, $ EN eh O(m)) such that || 1 ΣN &hll m( a.s.
27

---

Since sup,, | < oo almost surely, we have sup, 1l N E Ex=o (v) v(+1))l
supp ll N Ei=1 (v) r/t1ill < 20 almost surely. Then, /Tp 1 N Ei=1 Ex=o
"/++ill 0 TD) leads to V N Ei o 1 ) (11 a.s.
N Li=l= Sn and r Ei= (vt 2/41) From above, we that C5 in Theorem D. satisfied and we show that all the conditions in Theorem D. have been satisfied.
Let (1) rn
(A) ト
D.4 CLosed Form of Limitimg Covariance Matrix
Lastly, we need to analyze the closed form expression of U in C4 (b) of Theorem D.1 Recall that
N=
Σ N
Dim1 U, and U; 9: g0())) in (69 We now give the exact form of function gi()) as
follows:
T
9:(0") Σ Ti(x)
ma- ma- (2) (z)²
Pi x)mo- Pi(o,)))mo())
Σ NEN
P, y) (v)
BEX
F.((0, X.) - ((LOS)
Σ VP,( -
4
T
( X.) V(110') IVVE((0' x.) -5,-~Va ((((0)))
E
=B EE
(VF((0" X²) VS((0')) (VFI xx) V
-VA(00) )
E
(VE(00, (x) - V(((0'))
80
VF (x)) - V1.(0') (VF.(0", -
+
(Cv(VV) Xo), VF (xo))
Cov(VF.(0) Xo), VR(0", X.)) + Cov(V X.),, VB(00, Xx))),
E(FF(O,)))
(76)
where the second equality comes from the recursive form of mg: (x) in 45 and that the process {X,)nzo is in its stationary regime, i.e., Xo n.; from the beginning. The last equality comes from rewriting
X2), FF X2)) in a matrix form. Note that gi()") is exactly the asymptotic covariance matrix of the underlying Markov chain {X) n. Jn20 associated with the test function -. By utilizing the following lemma, we can obtain the explicit form of V as defined in (60).
Lemma D.2 (Lemma D.2.2 AT). If all the eigenvalues of matrix M have negative real part, then for every positive semi-definite matrix U there exists unique positive semi-definite matrix V satisfying U MV VMT The explicit solution V given as
V
Ml UM(") dt.
(77)
D.5 CLT of Polyak-Rupper Averaging
We now consider the CLT result of Polyak-Ruppert averaging 0, Er=1 similar way by verifying that the conditions in the related CLT of Polyak-Rupae averaging for the stochastic approximation satisfied. The additional assumption is given below.
1 0g. The steps follow
28

---

C6. For the sequence (r in (38
(1) 1/2 Σ k= 'kk + 0 with probability 1.
Then, the CLT of Polyak-Rupper averaging is as follows.
assume CI, C3, C4, C5 in Theorem D.3 (Theorem 3.2 of (2)). Consider the iteration 38
Theorem D.I are satisfied. Moreover, assume C6 is satisfied. Then, with step size "nn ~ n for
E (0.5, 1). we have
vn(O, - -0) dist.
No,, V),
(78)
where = UH
Discussion about C1 and C3 can be found in Section D.1 Condition C4 has been analyzed in Section
D.2 and condition C5 has been examined Section D.3 The only condition left to analyze is C6,
which is based on the results obtained in Section D.3 In view of (56). ra rn (A) so C6 is equivalent to
(1)
N E Sn+1.
N (sk+1)
1/2
k
N
+0 w.p.l.
(79)
k=
In Section D.3. we have shown that
On,), N = Note that by Assump-
tion 2.3 we consider bounded communication interval for step size "nn ~ 7t/n" t for a E (0.5, 1), and hence, Th = O(),) such that
ra
(A)
= =(mm). We then know that
On''
Σ S.l = O(n'o))
(80)
such that
1/2
(4k+z)
= o(1),
(81)
which proved (79) and C6 verified. Therefore, Theorem D.3 proved under our Assumptions 2.1
E
Discussion on the comparison of Theorem 3.3 to the CLT result in [51]
As byproduct of our Theorem 3.3 we have the following corollary.
Corollary E.1. Under Assumptions 2.1 we have
2.5
for the sub-sequence {n1l1o where Ki K for all 1
Onn -0)
dist. 1
NO0, V')
(82)
Proof. Since K; K for all I, have my K1. There is existing result showing the CLT result of the partial sum of a sub-sequence (after normalization) has the same normal distribution as the partial sum of the original sequence.
Theorem E.2 (Theorem 14.4 of (8). Given sequence of random variable 02,02. with partial sum S. A En On such that Sn Sn dist., (0, V). Let nı be some positive random variable taking integer value such that On, is on the same space as On. In addition, for some sequence {br going to infinity, ni/bi + for a positive constant c. Then, I Sn,
dist. N0, V).
1030
From Theorem B.2 and Theorem 3.3
have 1 ynu
Σl= (Ong - -0) dist. N(0, V').
1420
29

---

Recently, [5]] studied the CLT result under the LSGD-FP algorithm with i.i.d sampling (with slightly different setting of the step size). We are able recover Theorem 3.1 of [5T] under the constant communication interval while adjusting their step size to make fair comparison. We state their algorithm below for self-contained purpose. During each communication interval n E (ni, m(+1].
0
71 VE, x VVR X;))
if (n, m411),
0
(83)
1= (02
if = m141-
N
The CLT result associated with Theorem E.3 (Theorem 3.1 of 51
83
given below.
Under LSGD-FP algorithm with i.i.d. sampling, we have
m
(Omz 0¹)
dist. NO,,vV)),
(84)
1000
where v 2 oo to (E
[ Ki kTt).
Note that v = 1 for constant K. We can rewrite 84 as
fm
ynn
(mn
0²)
1nn
0²) VK-
(Onx 0*)
(85)
1
Vi
R=1
such that
1
0 0*) dist. N(O, V'). K
1
(86)
11000
Note that the step size in (83) keeps unchanged during each communication interval, while ours in (I) keeps decreasing even in the same communication interval. This makes our step size decreasing
faster than theirs. To make a fair comparison, we only choose a sub-sequence {n in (86) such
that it is 'equivalent' to see that our step sizes become the same at each aggregation step. In this case, we again use Theorem E.2 obtain
Onx. - 8t)
diet. N(O, V'),
(87)
KI ==1
1
K
such that
Σ ==1
(Onk, 0²) VK
Σ (Onxs - 0²) dist.
NO, V').
(88)
L-400
Therefore, our Corollary E. also recovers Theorem 3.1 of [51] under the constant communication interval K, but with more general communication patterns and Markovian sampling.
F Discussion on Communication Patterns
F1 Examples of Communication Matrix W
In the decentralized learning such as D-SGD, HLSGD and DFL, W at the aggregation step can be generated locally using the Metropolis Hasting algorithm based on the underlying communication topology, and is deterministic (62 43 80) Specifically, each agent exchanges its degree d, with its neighbors j E (i),, forming the weight W(i.j) = [1n] 1/d,) for j (()) and ii, = E (i, this case, W is doubly stochastic and
Metropolis Hasting Algorithm:
symmetric. By Perron-Frobenius theorem, its SLEM X (W) < 11. Then, | J| = IW2 - J|| = X)) < 1, which satisfies Assumption 2.5
fi). is worth noting that this algorithm
robust time-varying communication topologies.
Client Sampling in FL: For LSGD-FP studied
76
W = 11"//N trivially satisfies
Assumption 2.5-ii). For LSGD-PP on the other hand, only a small fraction of agents participate in each aggregation step for consensus (50 30). Denote by a randomly selected set of agents (without replacement) of fixed size |S| E {1,2, .N at time and Ws plays role of aggregating 0
30

---

for agent i E S. Additionally, the central server needs to broadcast updated parameter pn+1 to the newly selected set S' with the same size, which results in a bijective mapping a (for S 8' and [N]/S - N /S") and a corresponding permutation matrix Ts-s' Then, the communication matrix becomes W -s--s: 5 Specifiiially Ts-s: otherwise. Besides, W (i.
T/|S| for i,j E S. Ws( j = a(i)) and (t. 1 for i $ S, and Ws(i,j) 0 otherwise. Note that Ws s is now random matrix, since S is a randomly chosen subset of size [S]. Clearly, for each choice of S. Wg is doubly stochastic, symmetric and W Ws. Taking the expectation of Ws s w.r. the randomly selected set S gives Es [s[Ws][i,t] = -- ([S) - 1)/N
for i E [ and [s[Wsl((.))
(|S) 1)/N(N 1) for & j. Note that Es W has all
positive entries. Therefore, we use the fact T for permutation matrix T such that [E]] W
Jl Es.s' (WT Ts.s Ws] J|l Es WW Wsl Jll = EEs W J
by
Perron-Frobenius theorem and eigendecomposition, which satisfies Assumption 2.5 ii).
F.2 Discussion on partial client sampling
The commonly used partial client sampling algorithm in the FL literature 50 30 is FedAvg as follows:
1. At time the central server updates its global parameter O,, TST Eies Of from the agents in the previous set S. Then, the central server selects a new subset of agents S' and broadcasts f, to agent i E S", i.e., 0% = On;
2. Fach selected agent computes K steps of SGD locally and consecutively updates its local parameter 0 01+1'' 00, according to (Tab;
3. Each selected agent i E S' uploads * k to the central server.
Then, the central server repeats the above three steps with la+k and new set of selected agents.
In our client sampling scheme, at the aggregation step n, the design of Ws results in 0 [8) Ejes 0% for a selected agent E S, and 0 6% for unselected agent S. Mean- while, the central server updates the global parameter 0, = 8 for i E S. Then, the permutation matrix Tss ensures that the newly selected agent i S' will use 0, as the initial point for its subse- quent SGD iterations. Consequently, from the selected agents' perspective, the communication matrix W T Ws corresponds step I in FedAvg. As we can observe. both algorithms update the global parameter identically from the central server's 's viewpoint, rendering them mathematically cquivalent regarding the global parameter update.
We acknowledge that under the i.i.d sampling strategy, the behavior of unselected agents in our algorithm differs from FedAvg. Specifically, unselected agents are idle in FedAvg, while they continue the SGD computation in our algorithm (despite not contributing to the global parameter update). Importantly, when an unselected agent is later selected, the central server overwrites its local parameter during the broadcasting process. This ensures that the activities of agents when they are unselected have no impact on the global parameter update.
To our knowledge, the FedAvg algorithm under the Markovian sampling strategy remains unexplored in the FL literature. Extrapolating the behavior of unselected agents in FedAvg from i.i.d sampling to Markovian sampling suggests that unselected agents would remain idle. In contrast, our algorithm enables unselected agents to continue evolving X These additional transitions contribute to faster mixing of the Markov chain for each unselected agent and a smaller bias of Fi X relative to its mean field (0), potentially accelerating the convergence.
G Additional Simulation
G.1 Simulation Setup in Section 4
This simulation is performed on PC with an AMD R9 5950X, RTX 3080 and 128 GB RAM. In
this simulation, we assume that agents follow the DSGD algorithm ① In Figure 2(a] 2(c) each
'I Appendix F2 we will discuss the mathematical equivalence between our client sampling strategy and the commonly used one in the FL literature [50 30)
31

---

agent holds disjoint local dataset (non-ow overlaappg data points for every agent). while we distribute the ijennl dataset [1] with more varied distribution among 100 agents by leveraging Dirichlet distribution with the default alpha value of 0.5 in Figure 2(d) 2(
Moreover, we assume that all agents are distributed over communication network. In order to create this network among 100 agents and the graph-like dataset structure held by each agent, we utilize connected sub-graphs from the real-world graph Facebook in SNAP [49]. All 100 agents collaborate together to generate deterministic communication matrix W [Wyy] with Metropolis Hasting For j. [M], we have
algorithm of the following form:
min
1 d
11 if agent j is the neighbor of agent i, J
W6
0
otherwise,
Wa JE[N]
Wi.
where d; represents the degree of agent in the graph. The communication interval K is set 1, as is the usual choice in DSGD 771 80 61 68
For the first group of agents, we assume they have full access to their datasets, thus performing iid. sampling or single shuffling. In particular,
ii.d. sampling employed by agent means that the data point X is independently and uniformly sampled from its dataset X, at each time n.
Single shuffling, by its name, only shuffles the dataset once and adheres to that specific order throughout the training process.
On the other hand, within the second group of agents, we assume that they hold graph-like datasets. Now, we introduce simple random walk (SRW), non- non-backtracking random walk (NBRW), and self-repellent random walk (SRRW) in order:
SRW refers to the walker that chooses one of the neighboring nodes uniformly at random.
NBRW, as studied in 2 48 5) is variation of SRW, which selects one of the neighbors uniformly at random, with the exception of the one visited in the last step.
SRRW, recently proposed by 225, is designed with nonlinear transition kernel K K[x]
[0, 1] N of the following form:
Paplog/pg) Ene(M Puc(Ta/pss=a'
Kij[x] A
Vi,j E [N],
(89)
where matrix = [Pyj] is the transition kernel of the baseline Markov chain and μ [ is its corresponding stationary distribution. Additionally, denotes the force of self repellence, and larger a leads to stronger force of self repellence, thus higher sampling efficiency [25] Corollary 4.3]. Moreover, vector IR- is in the interior of probability simplex, representing the empirical distribution, in other words, the visit frequency of each node in the graph. The update rule of this empirical distribution in the following form:
Xa+1 = X,, + B5x1(6x.... - x,).
(90)
where 3n (n + 1)- is the step size of SRRW iterates. b = 1 was original proposed in 25 and is recently extended h E (0.5, 1) in (39. In this simulation, we use SRW as the baseline Markov chain of SRRW, and in turn μ is proportional to the degree distribution. We also assume Xo = 1/N, i.e., each node has been visited once, and choose the step size Bn = (n + 10.8, force of self repellence Section 4].
20 according to the suggestion in [39
Since SRW, NBRW, and SRRW all admit the stationary distribution that is proportional to degree distribution, in order to obtain unfirom target in (13), we need to reweight the gradient computed by each agent in order to maintain an asymptotic unbiased gradient. Thus, agent i should modify its
SGD update from aaa to the following:
0 0 1/2
0;
Yn+1 (., VE(E
91
32

---

dir Jnto adt 1s dars
050
23
2.8
aiti adt 2 dwrk
2 2. tavy
training 1055
training loss
trainingg loss
0.55
0:2
0.1
0.5
Rambar do
Numbe ronnnds 94
Number
Figure 3: Image classification experiment. From left to right: (a) Comparison of various sampling strategies in image classification problem using 5-layer neural network. (b) Train a 5-layer CNN model with different number of total agents (clients) to show the linear speedup effect. (c) Train ResNet-18 model with different sampling strategies among 10 agents with participation ratio 0.4.
G.2 Image Classification Task
In this part, perform the image classification task through 5-layer neural network, where the CIFARIO dataset 44] with 50k image data is evenly distributed to 10 agents. Each agent possesses 5k images, which are further divided into 200 batches, each batch with 25 images.
The Convolutional Neural Network (CNN) model used in this simulation encompasses:
Two convolutional layers (i.e., nn. Conv2333, 6, 5) and nn. Conv2d(6, 16, 5)), each followed by
ReLU activation functions to introduce non-linearity and max pooling (i.e., mn..xxPuo22d(2. 2)) to reduce spatial dimensions.
Three fully connected (linear) layers, concluding with softmax output to handle the multi-class classification problem.
Similar to the simulation setup in Section 4 among the 10 participating agents, five have unrestricted access to their respective data allocations, enabling them to utilize the shuffling method to iterate through their batches. The other five agents are designed to simulate limited data access scenarios. Their data access is structured using five distinct graph topologies extracted from the SNAP dataset collection [49], each graph simulating unique communication pattern among the batches (nodes) of data. Within these topologics, agents adopt one of three random walk strategies SRW, NBRW, and SRRW, all with importance reweighting to sample the batches for training.
Local model training conducted for five epochs at each agent before aggregating the updates at a central server- process repeated for total of 200 communication rounds. Each epoch consists of a full traversal the local dataset of agents in the first group, or 200 batches sampled for training the second group of agents. To mimic realistic conditions, we also introduce partial agent participation where only 40% of agents are selected randomly to transmit their updates in each round, reflecting the intermittent communication in real-world FL deployments. Lastly, the selection of the step size 3n for SRRW iterates (90) is a critical aspect of our experiments. In this simulation, we experiment with various values of be E {0.501, 0.6, 0.7, 0.8, 0.9] to determine the most advantageous setting for maximizing the benefits of the SRRW strategy. Based on our findings, the best choice for the SRRW
step size is b- 0.501, in other words, 3, (n + 1) 0.501
The simulation result is quantified by averaging the training loss across ten repeated trials for each configuration. As depicted in Figure 3(a) the training results are consistent with our previous findings Figure 2(a) in the context of the FL framework and the training neural networks: the use of a more effective sampling approach, even for a portion of the agents, results in significant enhancements in the overall training of the model, and this improvement is further enhanced through the highly efficient sampling strategy SRRW.
In Figure ((b and 3(c) we perform image classification experiments in the FL setting with partial client participation. Only 4 random agents will participate in the training process at each aggregation phase. In Figure 3bb we fix the sampling strategy (shuffling, SRRW with
10) and test the linear speedup effect for the 5-layer CNN model by duplicating 10 agents to N agents with N E (10, 20, 30, 40), keeping the same participation ratio 0.4. As can be seen from the plot, the training loss is inversely proportional to the number of agents, i.e., at 200 rounds, the training loss 0.52 for 10 agents, 0.23 for 20 agents, 0.18 for 30 agents, and 0. 12 for 40 agents. In Figure(3(e)
extend the current simulation from 5-layer CNN model to ResNet-18 18 model [34] in order to
33

---

numerically test the performance of different sampling strategies in more complex neural network training task. By fixing the shuffling the first group of agents, we observe that improving Markovian sampling from SRW to NBRW, then to SRRW, gives accelerated training process with smaller training loss.
H Limitations
Our study provides crucial insights into the identification of nuanced agents' sampling behaviors in UD-SGD, where improving each agent's s sampling strategy speeds up overall system performance without additional computational burden except the additional storage for the visit counts used for sampling their datasets. Our UD-SGD is scalable in terms of larger datasets as the sampling strategy (i.e., random walk) utilized by each agent leverages only local information for its dataset. However, our work has two limitations that should be acknowledged.
1. Assumption 2.4 posits that the parameter trajectory {fn.] } almost surely bounded, which is a strong assumption. This is crucial for guaranteeing the well-defined nature of all related quantities. Some mechanisms such as projections onto a compact subset 455 Chapter 5.1]. truncation-based method with expanding compact subsets can do the trick to ensure that the iteration always bounded (3 As mentioned in our discussion after Assumption [2.4 only recently the stability of SGD under Markovian sampling has been guaranteed to hold for some class of objective function f [9], while the discussion on stability issue under multi-agent scenario with Markovian sampling remains open problem and we do not pursue to remove this stability assumption in this paper.
2. Asymptotic analysis: The main results of our work, i.c., almost sure convergence and central limit theorem in distributed optimization, are based on asymptotic analysis and might not accurately represent the sample performance of each contributing agent in the system. The of-e-oof-hhearr finite-sampe analysis in the literature only focuses on the worst- porss-performing agent that cannot capture the nuanced differences between agents' sampling strategies, with the explanation detailed in Footnote 2 Thus, finite-sample error bound that distinguish every agent's 's dynamics still unknown and regarded as a future direction.
Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and the introduction clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. The claims made match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The 'Limitations' section is provided in Appendix H
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
All the theorems, formulas, and proofs in the paper have been numbered and cross-referenced. All assumptions have been clearly stated or referenced in the statement of any theorems. The complete and correct proofs have been provided in appendices.
Justification:
4. Experimental Result Reproducibility
34

---

Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The detailed simulation setups have been provided Appendix G
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: We do provide clean source codes, but detailed instructions perform the experiment have been provided in Appendix G
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The full details have been provided in Appendix
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
However, error bars are intentionally omitted in Figure 2 in the main body to avoid cluttered plot and deliver the main message.
Justification: We plot the error bars in Figure 2(a)
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: We specify the platform that runs the simulation Appendix G.1
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We fully obey the NeurIPS Code of Ethics.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work mainly aims demonstrate how the improvement of partial agents' sampling strategies can accelerate the overall system's 's performance. It advocates for improving common wealth and has no negative social impact.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks.
35

---

12. Licenses for existing assets
Question:
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We have cited correctly the datasets ijenn and CIFAR-IO used for experiments in our paper.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects. 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
36


Reviews:
[{"review_id": "R0HHthx4Yu", "reviewer": "Reviewer_Evbf", "summary": "This paper conducts an asymptotic analysis of Unified Distributed SGD (UD-SGD), which has a generalized communication patterns (modelled with a doubly stochastic communication matrix). The paper investigates several different sampling strategies, such as i.i.d. sampling, shuffling, and Markovian sampling", "questions": "I have no further question.", "limitations": "No negative societal impact.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- Rigorous theory: I went through most of the proofs in the appendix and as far as I can tell the theory is sound.\n- Well presented: Despite the heavy derivation I find this paper easy to follow as the proof strategies and theoretical insights are discussed clearly in the main exposition.", "weaknesses": "Empirical results are quite sparse. Not that this is a big problem for a theory paper, but maybe some additional studies would make it more interesting. I have some suggestions:\n- Are all of the results obtained using the same communication matrix (referring to line 982 in appendix G1)? Since the theory is generic for all double stochastic W maybe the authors could present the average result over 5 random W?\n- How was local data allocated to each client? The text said each client holds 500 data points from a bigger dataset -- are they iid? If so, it might be interesting to investigate non iid local data (using Dirichlet distribution, which is a common setting in FL)\n- How does client dropout (also a common setting in FL) affect the theory and empirical results?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Q1: Are all of the results obtained using the same communication matrix (referring to line 982 in appendix G1)? Since the theory is generic for all double stochastic W maybe the authors could present the average result over 5 random W?\n\nWe thank the reviewer for the question and the suggestion. To clarify, we didn’t use the same communication matrix throughout all simulation results in the current manuscript. For the simulation in Section 4, we indeed used a fixed doubly stochastic matrix $\\\\mathbf{W}$ (with expression in line 982), as pointed out by the reviewer. \n\nIn the simulation in Appendix G.2, we have conducted the experiment in the FL setting with partial client participation. In this scenario, at each aggregation phase, only 4 random agents (clients) out of 10 upload their model parameters to a central server. This results in a random communication matrix $\\\\mathbf{W}\\_{\\\\mathcal{S}}$, determined by a random set of participating clients $\\\\mathcal{S}$ at each aggregation phase. The detailed expression of this random matrix has been provided in Appendix F.1. We admit that the random nature of the matrix $\\\\mathbf{W}\\_{\\\\mathcal{S}}$ was not explicitly explained in the simulation setup in Appendix G.2. To improve clarity, we will revise the description around lines 374-376 in the main body and explicitly point out in Appendix G.2 that the communication matrix in the FL setting with partial client participation is stochastic.\n\nTo accommodate the reviewer’s suggestions, we also simulate 5 random W setting under the decentralized SGD scenario (namely DSGD with time-varying topologies (DSGD-VT)), where at each aggregation phase, we randomly pick a communication matrix $\\\\mathbf{W}$ from a set of 5 doubly stochastic matrices. We perform the same configuration of sampling strategies as in Section 4, where the first group of agents perform shuffling or i.i.d. sampling while the rest of agents conduct simple random walk (SRW), non-backtracking random walk (NBRW), and self-repellent random walk (SRRW). The result is shown in Figure 1(c) in the rebuttal pdf file (could be found in author rebuttal). We observe the same numerical trend as other algorithms in the current manuscript (DSGD with fixed $\\\\mathbf{W}$ in Section 4, FL with partial client participation in Appendix G.2), where improving agent’s sampling strategies leads to faster convergence with smaller MSE.\n\n> Q2: How was local data allocated to each client? The text said each client holds 500 data points from a bigger dataset -- are they iid? If so, it might be interesting to investigate non iid local data (using Dirichlet distribution, which is a common setting in FL)\n\nThanks for raising the question about IID and Non-IID data distribution. First, our theory is applicable to both IID and Non-IID data settings. Regarding the simulation in Section 4, as pointed out in lines 340 – 341 in the current manuscript, the ijcnn1 dataset (50k data points with binary classes) was shuffled and then evenly split among 100 agents, with each agent receiving 500 data points. Thus, each agent held a disjoint local dataset such that they didn’t have overlapped data point with other agents, resulting in Non-IID data. In our original simulation, the distribution of labels was relatively balanced, with the number of label '1' for each agent ranging from 40 to 60.\n\nWe agree that investigating more diverse data distributions would provide valuable insights, especially in federated learning. To address this, we conduct additional simulations in our rebuttal, where the data is allocated to agents using a Dirichlet distribution with the default alpha value of 0.5, which ensures a more varied distribution of labels among agents. For the binary classification problem, Figure 1(a) in the rebuttal pdf file indicates that the number of data with label '1' ranges from 0 to 350 across different agents, forming the Non-IID data. We simulate DSG and DFL based on this imbalanced dataset and the results are shown in Figure 1 (c) & (d). The plots demonstrate that our asymptotic analysis is invariant to data distribution with the same trend for different combinations of sampling strategies.\n\n> Q3: How does client dropout (also a common setting in FL) affect the theory and empirical results?\n\nThank the reviewer for pointing out the dropout phenomenon. In terms of client dropout, we believe that the reviewer refers to the following behavior: \n\n*The client temporarily exits the training process and will rejoin the training in the future with some probability (Bernoulli dropout).*\n\nThis is usually modeled as ‘partial client participation’ in FL. In our original submission, we have discussed this scenario in both theory (in Appendices F.1 and F.2) and in experiment (only 4 random participants out of 10 agents at each aggregation in Appendix G.2). Even under this client dropout effect, the random communication matrix $\\\\mathbf{W}$ generated by this ‘client dropout’ effect still satisfies our assumption 2.5. Therefore, our UD-SGD framework guarantees the convergence to the set of local minima because every agent equitably contributes to the learning process in the long run. In Figure 4 of our original submission, as well as Figure 2(b) in the rebuttal pdf file, we have shown that in the FL with partial client participation, our main message in this paper still holds: efficient sampling strategies employed by individual agents improve the overall convergence in UD-SGD.", "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": "RrozDmEvav", "reviewer": "Reviewer_WSiF", "summary": "This paper studies the asymptotic convergence behavior of federated learning under the UD-SGD framework with Markovian data. The authors establish a new central limit theorem that considers the strategy of every agent, which goes beyond the existing bounds that only focus on the worst-performing agent. Their theory emphasizes the importance of every individual and also explains linear speedup and asymptotic network independence.", "questions": "1. What is the main technical challenge when utilizing Poisson equation to prove Theorem 3.3? Specifically, what is new compared with the analysis in reference [23] and [30]?\n2. Do the authors believe the current asymptotic analysis technique could be extended to (federated) reinforcement learning? I saw some finite-sample analyses for federated RL in your references like [72].", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper established theories for a more general federated learning framework and gives a refined analysis to encode the behavior of every agent into their bound.\n2. The new asymptotic analysis could explain linear speedup scaling with the number of agents and asymptotic network independence.\n3.  The new analysis shows that upgrading only a small group of agents could benefit the whole system and the authors conduct experiments to validate it.\n4. The paper is well-written.", "weaknesses": "1. As the author mentioned, Assumption 2.4 seems strong and finite-sample analysis is preferred,\n2. As far as I could see in the experiments, the author only implemented DSGD but the UD-SGD framework has more algorithms.\n3. The linear speedup scaling with the number of agents and asymptotic network independence are only mentioned in theory but do not have empirical justification.\n4. The experiments for neural networks are somewhat toy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Q1: What is the main technical challenge when utilizing Poisson equation to prove Theorem 3.3? Specifically, what is new compared with the analysis in reference [23] and [30]?\n\nThe main technical challenge in utilizing the Poisson equation to prove Theorem 3.3 lies in addressing the consensus error in the decomposed noise terms for each agent. Specifically: \n\n---\n*We decompose $\\\\nabla F\\_i (\\\\theta\\_n^i,X\\_n^i )-\\\\nabla f\\_i (\\\\theta\\_n^i)$ into three parts in (48) using Poisson equation: $e\\_{n+1}^i,\\\\nu\\_{n+1}^i,\\\\xi\\_{n+1}^i$. The consensus error $\\\\theta\\_n^i-\\\\theta\\_n$ embedded in noise terms $e\\_{n+1}^i$ and $\\\\xi\\_{n+1}^i$ is a new factor, whose characteristics have been quantified in our Lemma 3.1 but are not present in the single-agent scenario analyzed as an application of stochastic approximation in references [23] and [30].*\n\n---\nWe will replace the explanation of technical challenges around lines 259-261 in our original submission with above contents. Full explanations are provided below for the completeness. All line numbers and equation numbers are referred to our original submission.\n\nAs mentioned in lines 754 – 756, for the noise term $\\\\xi\\_{n+1}^i$, directly following the analysis in [23] and [30] leads to a one-step error for all agents, as expressed in (53). In a single-agent scenario (like SGD), this one-step error is simply $-\\gamma_n\\\\nabla F$. However, in a multi-agent scenario, this one-step error cannot be directly analyzed due to the model parameters $\\\\Theta\\_n$ of all agents being multiplied by the communication matrix $\\\\mathbf{W}$ in (18). To overcome this issue, we decompose this one-step error among all agents into two parts in (54): the consensus error among all agents and the one-step error of the average solution among all agents. Although separating the error into consensus error and error between the average and target solution has been done similarly in [1], our approach in quantifying the consensus error in Lemma 3.1 handles broader classes of communication patterns within our UD-SGD framework, instead of DSGD in optimization in [1]. We can separate the effect of the consensus error and utilize our Lemma 3.1 on the speed of consensus error to obtain the condition on $\\\\xi\\_{n+1}^i$ in (55). Similarly, for the noise term $e\\_{n+1}^i$, we follow a similar logic in decomposing its covariance in (73). This separation of the consensus error allows us to derive (75), ensuring that we can rigorously analyze the covariance structure and account for the multi-agent interactions. \n\n[1] Zeng, Sihan, Thinh T. Doan, and Justin Romberg. \"Finite-time convergence rates of decentralized stochastic approximation with applications in multi-agent and multi-task learning.\" IEEE Transactions on Automatic Control 68, no. 5 (2022): 2758-2773.\n\n> Q2: Do the authors believe the current asymptotic analysis technique could be extended to (federated) reinforcement learning? I saw some finite-sample analyses for federated RL in your references like [72].\n\nYes, we believe that our asymptotic analysis can be extended to Federated RL. Our analysis is based on transforming the UD-SGD framework into a stochastic approximation setting, which includes both optimization algorithms (SGD) and RL algorithms (TD learning and Q-learning). This structural compatibility allows for an extension to RL. \n\nTo extend our asymptotic analysis to Federated RL, we need to make the following adaptations: Replace the gradient $-\\\\nabla F\\_i$ in our UD-SGD framework with the TD error from the Bellman equation, denoted as $g\\_i (\\\\cdot)$ in Algorithm 1 of [72]; Adjust the CLT in Theorem 3.3 by replacing $-\\\\nabla^2 F\\_i$ with $\\\\nabla g\\_i$ to reflect the gradient of the TD error. This adaptation should yield the statistical properties of Federated RL, providing insights into the asymptotic performance of each agent rather than focusing solely on the worst-performing agent, as done in some finite-sample analyses like [72]. \n\nA notable caveat in RL is that Markovian samples are derived from a given behavioral policy, which is often uncontrollable. While our analysis can still evaluate the contribution of each agent to the overall system performance, the improvements from efficient sampling strategies, as discussed in our paper, cannot be directly extrapolated from optimization setting to the RL context.\n\n> Other concerns: As far as I could see in the experiments, the author only implemented DSGD but the UD-SGD framework has more algorithms. The linear speedup scaling with the number of agents and asymptotic network independence are only mentioned in theory but do not have empirical justification. The experiments for neural networks are somewhat toy.\n\nWe appreciate the reviewer's request for more empirical results to support our theory. To address your concerns, we conducted additional experiments shown in Figures 1–3 of the rebuttal:\n\n- In Figure 1(c), we simulate DSGD with a randomly chosen communication matrix from 5 doubly stochastic matrices at each aggregation phase. In Figure 1(d), we test the DFL algorithm with increasing communication interval $K(l) = \\\\max\\\\{1,⌈log⁡(l)⌉\\\\}$ after $l$-th aggregation phase. Moreover, we trained a ResNet-18 model with different sampling strategies, as shown in Figure 2(b). These results demonstrate that improved sampling strategies lead to faster convergence with smaller MSE.\n\n- To numerically test the linear speedup, We conducted image classification on a 5-layer CNN for the CIFAR-10 dataset with partial client participation. We varied the number of agents from 10 to 40. As shown in Figure 2(a), training loss inversely proportional to the number of agents confirms the linear speedup.\n\n- In Figure 1(b), we observe that all four algorithms (Centralized SGD, DSGD with time-varying topologies, FL with full client participation, and DFL with increasing communication interval) reach similar performance around 1000 steps, indicating asymptotic network independence.", "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": "PfBADdJDls", "reviewer": "Reviewer_ds2S", "summary": "This paper provides an asymptotic analysis of Unified Distributed SGD (UD-SGD) under heterogeneous agent dynamics and a large family of communication topology. It shows that under certain assumptions: i) regularity of the gradient, **ii) Ergodicity of Markovian sampling**, iii) decreasing step size and intervals not increasing so fast, iv) stability on model parameter v) contraction property of douly-stochastic communication matrix, UD-SGD algorithm guarantees that every agent parameter $\\theta_n$ converges to the same minimum value $\\theta^*$ with some variance matrix $V$ and the mean value of all agents $\\overline{\\theta}=\\sum_{i=1}^n\\theta_i$ also converges to $\\theta_i$ with some variance matrix $V'$.", "questions": "Same as the weakness.", "limitations": "Same as the weakness.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Although some previous works discuss the asymptotic analysis for distributed learning, most of them focus on some specific algorithm under a given communication topology and i.i.d sampling. This work is more general. It discusses the asymptotic analysis for more diverse communication topologies with the Markov sampling method.\n2. In order to discuss the theoretical properties of a general distributed learning framework under diverse communication topologies, the author introduce the Unified Distributed SGD (UD-SGD). The clear definition for a unified version of DSGD helps readers better understand the universality of this property.\n3. Let $V_i$ be the limiting covariance matrix of agent i and $V$ be the covariance matrix of the mean of all agents ($V=\\frac{1}{n^2}\\sum_{i=1}^{n} V_i$). The author provides the exact for of $V$.\n4. The provides numerical experiments on logistic regression and neural networks with different sampling strategies to support their theory part.", "weaknesses": "1. In line 26, the authors claim that $\\mathcal{L}$ represents the collection of local minima of objective function $f$. In line 246, the authors claim that $\\theta^*\\in \\mathcal{L}$. Since when $f$ is non-convex, $\\mathcal{L}$ do not have a single element and $\\theta^*$ could have a lot of selections. How could we ensure that the convergence of consensus $\\theta_n$ is unique? And how to choose $\\theta^*$? Will that be the global minima?\n2. The asymptotic analysis Theorem 3.3 is mainly based on Assumption 2.2, which assumes that the dynamic agent $\\{X_{n}^i\\}$ is an ergodic Markov chain. Could the author give some sampling strategies that satisfy this property and are now widely used in DSGD? What are the advantages of Markov sampling compared with the i.i.d sampling method?\n3. In figure 2 of the experimental section, the authors only compare the performance of different Markov sampling methods. Could the author also compare with the iid sampling and sampling shuffle strategies?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Q1: In line 26, the authors claim that $\\\\mathcal{L}$ represents the collection of local minima of objective function $f$. In line 246, the authors claim that $\\\\theta^*\\\\in\\\\mathcal{L}$. Since when $f$ is non-convex, $\\\\mathcal{L}$ do not have a single element and $\\\\theta^*$ could have a lot of selections. How could we ensure that the convergence of consensus $\\\\theta_n$ is unique? And how to choose $\\\\theta^*$? Will that be the global minima?\n\nAs mentioned in Footnote 1 of our current manuscript, our non-convex setting only concerns the (possibly many) local minima, which is a common scenario in deep learning. We believe that the reviewer’s confusion comes from our wording ‘an optimal point $\\\\theta^*\\\\in\\\\mathcal{L}$’ around line 246. Here $\\\\theta^*$ refers to a local minima rather than a global minima. In our UD-SGD framework, we ensure that all agents reach a consensus and converge to one of the local minima. Each run of the algorithm may converge to different local minima depending on the initialization and the stochastic nature of the updates. To avoid confusion, we will revise the wording from “an optimal point” to “a local minimum” in line 246. This should make it clear that we are discussing convergence to a local minima rather than a global minima.\n\nOur CLT result is conditional on the algorithm converging to a specific local minima $\\\\theta^*$. Given that $\\\\lim_{n\\\\to\\\\infty} \\\\theta\\_n=\\\\theta^*$, we derive the CLT for this particular $\\\\theta^*$. Without knowing the exact local minima to which the algorithm converges, it is impossible to compute the limiting covariance, which indicates the performance at the converging point. We appreciate the reviewer’s feedback and will add the following clarification to line 252 in the revision: ‘For notational simplicity, and without loss of generality, our remaining results are stated while conditioning on the event that $\\\\{\\\\theta\\_n\\\\to\\\\theta^*\\\\}$ for some $\\\\theta^*\\\\in\\\\mathcal{L}$’. \n\nLastly, we mentioned in Footnote 1 that additional condition like the PL inequality is required to guarantee convergence to a global minima because the PL inequality ensures that every local minima is also a global minima. This simplifies the landscape of the objective function. However, our current work focuses on local minima and does not pursue the PL inequality.\n\n> Q2: The asymptotic analysis Theorem 3.3 is mainly based on Assumption 2.2, which assumes that the dynamic agent is an ergodic Markov chain. Could the author give some sampling strategies that satisfy this property and are now widely used in DSGD? What are the advantages of Markov sampling compared with the i.i.d sampling method?\n\nMetropolis-Hasting Random Walk (MHRW) and Simple Random Walk (SRW) are the most popular sampling strategies in DSGD, which satisfy the ergodic Markov chain property (e.g., Section 2.1 in [1], Section 2 in [2]). Specifically, MHRW with uniform target distribution has the following transition probabilities:\n$$P(X\\_{n+1}=j | X\\_n=i) \\\\triangleq P\\_{ij} = \\\\min \\\\{\\\\frac{1}{d\\_i},\\\\frac{1}{d\\_j}\\\\} ~~\\forall i \\\\neq j, P\\_{ii}= 1-\\\\sum\\_{j\\\\neq i} P\\_{ij}$$\nFor SRW, the transition probability is $P\\_{ij}=1/d\\_i$ for $j\\\\in Neighbor(i)$ and $P\\_{ii}=0$, with the stationary distribution proportional to the degree of each node. \n\nRegarding the advantages of Markovian sampling over iid sampling, we have emphasized in lines 61 - 72. For the sake of completeness, here is a brief summary: \n\n- **Handling Limited Data Access:** Markovian sampling is particularly useful when agents have limited or sequential access to data, making i.i.d. sampling infeasible. For example, Fog learning considers a multi-layer hybrid learning framework consisting of heterogeneous devices, where each agent is treated as an edge server of the next-layer network [3]. This contributes to the graph-like structure of the dataset held by each agent, where i.i.d. sampling is infeasible.\n\n- **Efficiency in High-Dimensional Spaces:** In high-dimensional data spaces (such as constraints), Markov Chain Monte Carlo (MCMC) methods, such as those employing Markovian sampling, are more computationally efficient and effective compared to i.i.d. sampling, which can be costly and less practical because multiple rejections can happen before obtaining a sample generated by i.i.d. sampling that satisfies constraints.\n\n\n> Q3: In figure 2 of the experimental section, the authors only compare the performance of different Markov sampling methods. Could the author also compare with the iid sampling and sampling shuffle strategies?\n\nThank you for the suggestion. In the current manuscript, we have included a comparison between i.i.d. sampling and shuffle methods, which was mentioned in lines 357 – 359 with details deferred to Figure 3 in Appendix G.1 due to space constraints. In particular, we fixed the second group of clients who perform Markovian sampling and varied the sampling strategies for the first group of clients. The results indicate that the shuffle method outperforms i.i.d. sampling in terms of MSE. This finding is consistent with existing literature (e.g., [2]), which shows that the shuffle method has zero asymptotic variance, in contrast to the positive variance associated with i.i.d. sampling. We will put this comparison from Appendix back to Section 4 if our paper is accepted (with one extra page for the camera-ready version).\n\n[1] B. Johansson, M. Rabi, and M. Johansson. \"A randomized incremental subgradient method for distributed optimization in networked systems.\" SIAM Journal on Optimization 20, no. 3 (2010): 1157-1170.\n\n[2] J. Hu, V. Doshi, and D.Y. Eun. \"Efficiency ordering of stochastic gradient descent.\" NeurIPS, 2022.\n\n[3] S. Hosseinalipour, C.G. Brinton, V. Aggarwal, H. Dai, and M. Chiang. \"From federated to fog learning: Distributed machine learning over heterogeneous wireless networks.\" IEEE Communications Magazine 58, no. 12 (2020): 41-47.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all three reviewers for their comments and for the time and effort they put into reading, understanding and evaluating our paper. In particular, we appreciate the question to make our technical contribution much clearer (Reviewer WSiF), and we should conduct more experiments to support our theory (Reviewer Evbf, WSiF, ds2S). We carefully consider all questions, concerns and comments provided by reviewers and address all of them appropriately. We provide detailed responses to each review separately and we believe that our responses address all of the reviewers' concerns. We also upload a PDF file containing figures of additional simulation results, which will be included in our revision. When we respond to each reviewer, we specify whether the figure comes from our original submission or from our additional experiments in the rebuttal. 

Now, we explain our additional experiments in the PDF file. Fig. 1 shows the extra simulation settings in the binary classification problem with Non-IID data, and Fig. 2 includes more experiments on the image classification problem. Specifically,

---
1. We perform additional binary classification simulations on the IJCNN1 dataset with more varied distribution among 100 agents by leveraging Dirichlet distribution with the default alpha value of 0.5 (see Fig. 1(a) for the data distribution). We follow the same setup as in Section 4 of our original submission, i.e., we split 100 agents into two groups, where the first group of 50 agents leverages either iid sampling or shuffling, while the second group utilizes three Markovian sampling methods: SRW, NBRW, and SRRW (with hyperparameter $\\alpha=20$). All 100 agents exchange model parameters through a communication matrix $\\mathbf{W}$. 

    In Fig. 1(b), we empirically show the asymptotic network independence property via four algorithms under our UD-SGD framework: 
    - Centralized SGD (communication interval $K=1$, communication matrix $\\mathbf{W}=\\mathbf{1}\\mathbf{1}^T/N$);
    - LSGD-FP (FL with full client participation, $K=5$, $\\mathbf{W}=\\mathbf{1}\\mathbf{1}^T/N$);
    - DSGD-VT (DSGD with time-varying topologies, $K = 1, \\mathbf{W}$ randomly chosen from $5$ doubly stochastic matrices);
    - DFL (decentralized FL with fixed $\\mathbf{W}$ and increasing communication interval $K(l)=\\max\\{1,log(l)\\}$ after $l$-th aggregation).

    *We fix the sampling strategy (shuffling, SRRW) throughout this plot.* All four algorithms overlap around 1000 steps, implying that they have entered the asymptotic regime with similar performance where the CLT result dominates, implying the asymptotic network independence in the long run.

    Fig. 1(c) & (d) show the performance of different sampling strategies in the DSGD-VT and DFL algorithms in terms of MSE (over 120 independent trials). Both plots consistently demonstrate that improving agent’s sampling strategies (e.g., shuffling > iid sampling, and SRRW > NBRW > SRW) leads to faster convergence with smaller MSE, supporting our theory.
---
2. We perform additional image classification experiments on the CIFAR-10 dataset in the FL setting with partial client participation. We follow the same setup as in Appendix G.2 of our original submission, i.e., 50k image data are evenly distributed to 10 agents, 5 agents in the first group (iid sampling or shuffling) and 5 in the second group (Markovian sampling). Each agent possesses 5k *disjoint* images, which are further divided into 200 batches, each batch with 25 images. Only 4 random agents will participate in the training process at each aggregation phase. In Fig. 2(a), *we fix the sampling strategy (shuffling, SRRW with $\\alpha=10$)* and test the linear speedup effect for the 5-layer CNN model (structure given in lines 1028 - 1033 in our original submission) by duplicating 10 agents to $N$ agents with $N\\in\\{10,20,30,40\\}$, keeping the same participation ratio 0.4. As can be seen from the plot, the training loss is inversely proportional to the number of agents, i.e., at 200 rounds, the training loss is 0.52 for 10 agents, 0.23 for 20 agents, 0.18 for 30 agents, and 0.12 for 40 agents. In Fig. 2(b), we extend the current simulation in Appendix G.2 from 5-layer CNN model to ResNet-18 model in order to numerically test the performance of different sampling strategies in a more complex neural network training task. By fixing the shuffling in the first group of agents, we observe that improving Markovian sampling from SRW to NBRW, then to SRRW, gives accelerated training process with smaller training loss. 

We eagerly anticipate feedback from the reviewers and are happy to offer further details and clarifications as needed!

Meta-review: All reviewers agree that this is a good paper. It introduces theoretical advancements in a generalized distributed learning framework, offering a refined analysis that captures the behavior of individual agents. The new asymptotic analysis effectively explains linear speedup with the number of agents and demonstrates asymptotic network independence. The findings also show that upgrading even a small subset of agents can positively impact the entire system, a result validated by the experiments. Consequently, the paper is recommended for acceptance.
Decision: Accept (poster)