Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGD

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\in[N]$ holds a private dataset $\mathcal{X}_{i}$ and an agent-specified loss function $F_{i}:\mathbb{R}^{d}\times\mathcal{X}_{i}\to\mathbb{R}$ that depends on the model parameter $\theta\in\mathbb{R}^{d}$ and a data point $X\in\mathcal{X}_{i}$. The goal is then to find a local minima $\theta^{*}$ of the objective function $f(\theta)\triangleq\frac{1}{N}\sum_{i=1}^{N}f_{i}(\theta)$, where agent $i$’s loss function $f_{i}(\theta)\triangleq\mathbb{E}_{X\sim\mathcal{D}_{i}}[F_{i}(\theta,X)]$ and $\mathcal{D}_{i}$ represents the target distribution of data for agent $i$.¹¹1Throughout the paper we don’t impose convexity assumption on $f(\theta)$. For convex $f(\theta)$, $\mathcal{L}$ is the global minima. For non-convex $f(\theta)$, $\mathcal{L}$ represents the collection of local minima, which is of great interest in neural network training for sufficiently good performance [20, 19]. With an additional condition such as the Polyak-Lojasiewicz inequality, non-convex $f(\theta)$ is ensured to have a unique minima [1, 75, 79]. Each agent $i$ can locally compute the gradient $\nabla F_{i}(\theta,X)\in\mathbb{R}^{d}$ w.r.t. $\theta$ for every sampled data point $X\in\mathcal{X}_{i}$. Due to the distributed nature, $\{\mathcal{D}_{i}\}_{i\in[N]}$ and $\{\mathcal{X}_{i}\}_{i\in[N]}$ are not necessarily identically distributed over $[N]$ so that the minima of each local function $f_{i}(\theta)$ can be far away from $\mathcal{L}$. This is particularly relevant in decentralized training data, e.g., Federated Learning (FL) with heterogeneous data across data centers or devices [81, 31].

In this paper, we focus on Unified Distributed SGD (UD-SGD), where each agent $i\in[N]$ updates its model parameter $\theta_{n+1}^{i}$ in a two-step process:

where $\gamma_{n}$ denotes the step size, $X^{i}_{n}$ is the data sampled by agent $i$ at time $n$ (i.e., agent dynamics), and $\mathbf{W}_{n}\!=\![w_{n}(i,j)]_{i,j\in[N]}$ represents the doubly-stochastic communication matrix satisfying $w_{n}(i,j)\geq 0$ and $\mathbf{1}^{T}\mathbf{W}_{n}\!=\!\mathbf{1}^{T}$, $\mathbf{W}_{n}\mathbf{1}\!=\!\mathbf{1}$. In the special case of $N=1$, (1) simplifies to the vanilla SGD where $\mathbf{W}_{n}=1$ for all $n$. UD-SGD covers a wide range of distributed algorithms, e.g., decentralized SGD (DSGD) [71, 80, 61, 69], distributed SGD with changing topology (DSGD-CT) [24, 43], local SGD (LSGD) in FL [55, 76], and its variant aimed at reducing communication costs (LSGD-RC) [51].

Versatile Communication Patterns $\{\mathbf{W}_{n}\}$: For visualization, we depict the scenarios of UD-SGD (1) in Figure 1. In DSGD, each agent (node) in the graph communicates with its neighbors after each SGD computation via $\mathbf{W}_{n}$, representing the underlying network topology. As a special case, central server-based aggregation, forming a fully connected network, translates $\mathbf{W}_{n}$ into a rank-1 matrix $\mathbf{W}_{n}\!=\!\mathbf{1}\mathbf{1}^{T}/N$. To minimize communication expenses, FL variants allow each agent to perform multiple SGD steps before aggregation [55, 67, 76], resulting in a communication interval of length $K$ and a consistent pattern $\mathbf{W}_{n}=\mathbf{W}$ for $n=mK,\forall m\in\mathbb{N}$, and $\mathbf{W}_{n}=\mathbf{I}_{N}$ otherwise. In particular, i) $\mathbf{W}\!=\!\mathbf{1}\mathbf{1}^{T}/N$ corresponds to LSGD with full agent participation (LSGD-FP) [76, 42, 51]; ii) $\mathbf{W}$ is a random matrix generated by partial agent participation (LSGD-PP) [55, 18, 74]; iii) $\mathbf{W}$ is generated by Metropolis-Hasting algorithm in decentralized setting, e.g., hybrid LSGD (HLSGD) [37, 32] and decentralized FL (DFL) [46, 77, 16]. We defer further discussion of $\mathbf{W}$ to Section F.1.

Markovian vs i.i.d. Sampling: Agents typically employ i.i.d. or Markovian sampling, as illustrated in the bottom brown box of Figure 1. In cases where agents have full access to their data, DSGD with i.i.d sampling has been extensively studied [60, 43, 61, 47]. In FL, many application-oriented LSGD variants have been investigated [51, 18, 77, 32, 37, 53]. However, these works solely focus on i.i.d. sampling, restricting their applicability to Markovian sampling scenarios.

Markovian sampling, which has received increased attention in limited settings (see Table 1), 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 [40, 63]. In HLSGD across device-to-device (D2D) networks [32, 37], random walks reduce communication costs compared to the frequent aggregations required by Gossip algorithms [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 [68, 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 high-dimensional spaces with constraints [27, 40], where acceptance-rejection methods [12] lead to computational inefficiency (e.g., wasted samples) due to multiple rejections before obtaining a sample that satisfies constraints [26, 68]. In addition, shuffling methods can be considered as high-order Markov chains [38], which achieves faster convergence than i.i.d. sampling [1, 78, 79].

Limitations of Non-Asymptotic 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 1, have made significant strides. However, these works often fall short in accurately revealing the statistical influence of each agent dynamics $\{X_{n}^{i}\}$ on the performance of UD-SGD. For instance, [71, 69] proposed the error bound $O(\frac{1/\log^{2}(1/\rho)}{n^{1-a}})$, where $a\in(0.5,1]$ and $\rho$ denotes the identical mixing rate for all agents, overlooking agent heterogeneity in sampling strategy. A similar assumption to $\rho$ 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(\tau_{mix}^{2}/(n+1))$, where $\tau_{mix}$ is the mixing time of the slowest agent. This approach, however, inherently focuses on the worst-performing agent, neglecting how other agents with faster mixing rates might positively influence the system.²²2Although 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 to some neighborhood of its stationary distribution. This naturally incurs a maximum operator, and thus convergence is strongly influenced by the slowest mixing rate, i.e., the worst-performing agent. Such an analysis fails to capture the collective impact of other agents on the overall system performance, a 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 in 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 to 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 a better understanding of convergence behaviors, as highlighted in [9, 56, 25, 39]. For vanilla SGD, [59, 17] 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, a key statistical feature in vanilla SGD’s CLT, also prominently features in high-probability bound [59], explicit finite-time bound [17] and $1$-Wasserstein distance in the non-asymptotic CLT [66]. [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, 68]. 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 metrics.

Our Contributions: We present an asymptotic analysis of the UD-SGD algorithm (1) under heterogeneous agent dynamics $\{X^{i}_{n}\}$ and a large family of communication patterns $\{\mathbf{W}_{n}\}$. Specifically,

$\bullet$  Under appropriate assumptions, all agents performing (1) asymptotically reach the consensus and find $\theta^{*}$: $\forall i\in[N]$, $\theta_{n}\triangleq\frac{1}{N}\sum_{i=1}^{N}\theta^{i}_{n}$ denotes the average model parameter among all agents, we have

Moreover, we derive the CLT of UD-SGD in the form of

Our framework addresses technical challenges in quantifying consensus error under various communication patterns and slowly increasing communication interval. This shows a substantial extension compared to previous studies [58, 43, 51], particularly in regulating the growth of communication intervals (Assumption 2.3-ii) and in proving the scaled consensus error’s boundedness (Lemma B.1). Furthermore, we reformulate UD-SGD as a stochastic approximation-like iteration and tackle the Markovian noise term using the Poisson equation, a technique previously confined only to vanilla SGD with Markovian sampling [17, 38, 52]. 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.

$\bullet$  In analyzing (3), we derive the exact form of $\mathbf{V}$ as $\frac{1}{N^{2}}\sum_{i=1}^{N}\mathbf{V}_{i}$. Here, $\mathbf{V}_{i}$ is the limiting covariance matrix of agent $i$, which depends mainly on its sampling strategy $\{X^{i}_{n}\}$. 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 finite-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) also treats recent findings in [38] as a very special case with $N=1$, where the relationship therein 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.

$\bullet$  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 (1) at large time $n$ depends solely on the left eigenvector of $\mathbf{W}_{n}$ ($\frac{1}{N}\mathbf{1}$ considered in this paper) rather than the specific communication network topology encoded in $\mathbf{W}_{n}$, but now under Markovian sampling. We extend these findings in view of CLT to a broader range of communication patterns $\{\mathbf{W}_{n}\}$ and general sampling strategies $\{X^{i}_{n}\}$.

$\bullet$  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.

Basic Notations: We use $\|\mathbf{v}\|$ to indicate the Euclidean norm of a vector $\mathbf{v}\in\mathbb{R}^{d}$ and $\|\mathbf{M}\|$ to indicate the spectral norm of a matrix $\mathbf{M}\in\mathbb{R}^{d\times d}$. The identity matrix of dimension $d$ is denoted by $\mathbf{I}_{d}$, and the all-one (resp. all-zero) vector of dimension $N$ is denoted by $\mathbf{1}$ (resp. $\mathbf{0}$). Let $\mathbf{J}\triangleq\mathbf{1}\mathbf{1}^{T}/N$. The diagonal matrix with the entries of $\mathbf{v}$ on the main diagonal is written as $\text{diag}(\mathbf{v})$. We also use ‘$\succeq$’ for Loewner ordering such that $\mathbf{A}\succeq\mathbf{B}$ is equivalent to $\mathbf{x}^{T}(\mathbf{A}-\mathbf{B})\mathbf{x}\geq 0$ for any $\mathbf{x}\in\mathbb{R}^{d}$.

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 a vector-valued function. Specifically, we consider a finite, irreducible, aperiodic and positive recurrent (ergodic) Markov chain $\{X_{n}\}_{n\geq 0}$ with transition matrix $\mathbf{P}$ and stationary distribution $\boldsymbol{\pi}$, and the estimator $\hat{\mu}_{n}(\mathbf{g})\triangleq\frac{1}{n}\sum_{s=0}^{n-1}\mathbf{g}(X_{s})$ for any vector-valued function $\mathbf{g}:[N]\to\mathbb{R}^{d}$. According to the ergodic theorem [12, 13], we have $\lim_{n\to\infty}\hat{\mu}_{n}(\mathbf{g})=\mathbb{E}_{\boldsymbol{\pi}}(\mathbf{g})$ a.s.. As defined in [13, 38], the asymptotic covariance matrix $\boldsymbol{\Sigma}_{X}(\mathbf{g})$ for a vector-valued function $\mathbf{g}(\cdot)$ is given by

where $\Delta_{n}\triangleq\sum_{s=0}^{n-1}(\mathbf{g}(X_{s})-\mathbb{E}_{\boldsymbol{\pi}}(\mathbf{g}))$. By following the algebraic manipulations in [12, Theorem 6.3.7] for asymptotic variance (univariate version), we can rewrite (4) in a matrix form such that

where $\mathbf{G}\triangleq[\mathbf{g}(1),\cdots,\mathbf{g}(N)]^{T}\in\mathbb{R}^{N\times d}$ and $\mathbf{Z}\triangleq[\mathbf{I}_{N}-\mathbf{P}+\mathbf{1}\boldsymbol{\pi}^{T}]^{-1}$. This matrix form explicitly shows the dependence on the transition matrix $\mathbf{P}$ and its stationary distribution $\boldsymbol{\pi}$, and will be utilized in our Theorem 3.3.

Model Description: The UD-SGD in (1) can be expressed in a compact iterative form, i.e., we have

at each time $n$, where each agent $i$ samples according to its own Markovian trajectory $\{X^{i}_{n}\}_{n\geq 0}$ with stationary distribution $\pi_{i}$ such that $\mathbb{E}_{X\!\sim\!\pi_{i}}[F_{i}(\theta,X)]\!=\!f_{i}(\theta)$. Let $K_{l}$ denote the communication interval between the $(l-1)$-th and $l$-th aggregation among $N$ agents, and $n_{l}\triangleq\sum_{m=1}^{l}K_{m}$ be the time instance for the $l$-th aggregation. We also define $\tau_{n}\triangleq\min_{l}\{l:n_{l}\geq n\}$ as the index of the upcoming aggregation at time $n$ such that $K_{\tau_{n}}$ indicates the communication interval for the $\tau_{n}$-th aggregation, or more precisely, the length of the communication interval that includes the time index $n$. The communication pattern follows that $\mathbf{W}_{n}=\mathbf{I}_{n}$ if $n\neq n_{l}$ and $\mathbf{W}_{n}=\mathbf{W}$ otherwise for $l\geq 1$, where the examples of $\mathbf{W}$ will be discussed in Section F.1. Note that i) when $K_{l}=1$, (6) reduces to DSGD; ii) when $K_{l}=K>1$, (6) becomes the local SGD in FL. iii) When $K_{l}$ increases with $l$, we recover some choices of $K_{l}$ 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.

2.1 imposes the regularity conditions on the gradient $\nabla F_{i}(\cdot,X)$ and Hessian matrix of the objective function $f(\cdot)$, as is commonly assumed in [10, 45, 29, 38]. Note that (7) requires per-sample Lipschitzness of $\nabla F_{i}$ and is stronger than the Lipschitzness of its expected version $\nabla f_{i}$, which is commonly assumed under i.i.d sampling setting [73, 50, 30]. However, we remark that this is in line with previous work on DSGD and LSGD-FP under Markovian sampling as well [71, 42, 80], because $\nabla F_{i}(\theta,X)$ is no longer the unbiased stochastic version of $\nabla f_{i}(\theta)$ and the effect of $\{X^{i}_{n}\}$ 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].

The ergodicity of the underlying Markov chains, as stated in 2.2, is commonly assumed in the literature [26, 68, 80, 42, 38]. This assumption ensures the asymptotic unbiasedness of the loss function $F_{i}(\theta,\cdot)$, which takes i.i.d. sampling as a special case.

In 2.3, the polynomial step size $\gamma_{n}$ is standard in the literature and it has the property $\sum_{n}\gamma_{n}=\infty$, $\sum_{n}\gamma^{2}_{n}<\infty$ [17, 38]. Inspired by [51], we introduce $\eta_{n}$ to control the step size within each $l$-th communication interval with length $K_{l}$ to restrict the growth of $K_{l}$. Specifically, $\sum_{n}\eta^{2}_{n}<\infty$ and $K_{\tau_{n}}=o(\gamma_{n}^{-1/2(L+1)})$ ensure that $\eta_{n}\to 0$ and $K_{\tau_{n}}$ does not increase too fast in $n$. $\lim_{l\to\infty}\eta_{n_{l}+1}/\eta_{n_{l+1}+1}=1$ sets the restriction on the increment from $n_{l}$ to $n_{l+1}$. Several practical forms of $K_{l}$ suggested by [51], including $K_{l}\sim\log(l)$ and $K_{l}\sim\log\log(l)$, also satisfy 2.3-ii). We defer to Appendix A the mathematical verification of these two types of $K_{l}$, together with the practical implications of increasing communication interval $K_{l}$.

2.4 claims that the sequence of $\{\theta_{n}^{i}\}$ 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, 52]. As mentioned in [58, 70], checking 2.4 is challenging and requires case-by-case analysis, even under i.i.d. 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 sampling strategy in the asymptotic regime under this stability condition.

The doubly-stochasticity of $\mathbf{W}_{n}$ in 2.5-i) is widely assumed in the literature [54, 24, 43, 80]. 2.5-ii) 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 $\mathbf{W}$ that satisfy 2.5-ii), e.g., Metropolis-Hasting matrix, partial agent participation in FL, are deferred to Appendix F.1 due to space constraint.

Almost Sure Convergence: Let $\theta_{n}\triangleq\frac{1}{N}\sum_{i=1}^{N}\theta_{n}^{i}$ represent the consensus among all the agents at time $n$, we establish the asymptotic consensus of the local parameters ${\theta_{n}^{i}}$, as stated in Lemma 3.1.

Lemma 3.1 indicates that all agents asymptotically reach consensus at a rate of $O(\gamma_{n})$ (or $O(\eta_{n})$). This finding extends the scope of [58, Proposition 1], incorporating considerations for Markovian sampling, FL settings, and increasing communication interval $K_{l}$. The proof, detailed in Appendix B, primarily tackles the challenge of establishing the boundedness of the sequences $\{\gamma_{n}^{-1}(\theta_{n}^{i}-\theta_{n})\}$ (or $\{\eta_{n}^{-1}(\theta_{n}^{i}-\theta_{n})\}$) almost surely for all $i\in[N]$. This is specifically analyzed in Lemma B.1. Next, with additional 2.2, we are able to obtain the almost sure convergence of $\theta_{n}$ to $\theta^{*}\in\mathcal{L}$.

Theorem 3.2 is achieved by decomposing the Markovian noise term $\nabla F_{i}(\theta_{n}^{i},X_{n}^{i})-\nabla f_{i}(\theta_{n}^{i})$, 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 a local minimum $\theta^{*}\in\mathcal{L}$, even in scenarios where the communication interval $K_{l}$ gradually increases, in accordance with Assumption 2.3-ii). The detailed proof of this theorem is provided in Appendix C.

Central Limit Theorem: Let $\mathbf{U}_{i}\!\triangleq\!\boldsymbol{\Sigma}_{X^{i}}(\nabla F_{i}(\theta^{*},\cdot))$ represent the asymptotic covariance matrix (defined in (5)) associated with each agent $i\in[N]$, given their sampling strategy $\{X^{i}_{n}\}$ and function $\nabla F_{i}(\theta^{*},\cdot)$. Define $\mathbf{U}\triangleq\frac{1}{N^{2}}\sum_{i=1}^{N}\mathbf{U}_{i}$. We assume the polynomial step-size $\gamma_{n}\!\sim\!\gamma_{\star}/n^{a}$, $a\!\in\!(0.5,1]$ and $\gamma_{\star}>0$. In the case of $a=1$, we further assume $\gamma_{\star}>1/2\mu$, where $\mu$ is defined in (8). For notational simplicity, and without loss of generality, our remaining CLT result is stated while conditioning on the event that $\{\theta_{n}\to\theta^{*}\}$ for some $\theta^{*}\in\mathcal{L}$.

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.i.d. sampling case [58, 43, 51]. We decompose $\nabla F_{i}(\theta_{n},X_{n}^{i})\!-\!\nabla f_{i}(\theta_{n})$ 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 [22, 29]. The specifics of this analysis are expanded upon in Appendices D.1 to D.3. We require $\gamma_{\star}\!>\!1/2\mu$ for $a\!=\!1$ to ensure that the largest eigenvalue of $\mathbf{M}$ is negative, as this is a necessary condition for the existence of $\mathbf{V}$ in (12) (otherwise integration diverges). In the case where there is only one agent ($N\!=\!1$), $\mathbf{V}$ and $\mathbf{V}^{\prime}$ reduce to 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-i) and i.i.d. sampling as shown in Table 1, we recover the CLT of LSGD-RC in [51]. See Appendix E for detailed discussions.

Theorem 3.3 has significant implications for the MSE of $\{\theta_{n}\}$ for large time $n$, i.e., $\mathbb{E}[\|\theta_{n}\!-\theta^{*}\|^{2}]\!\!=\!\sum_{i=1}^{d}\mathbf{e}_{i}^{T}\mathbb{E}[(\theta_{n}\!-\theta^{*})(\theta_{n}\!-\theta^{*})^{T}]\mathbf{e}_{i}\!\approx\!\gamma_{n}\sum_{i=1}^{d}\mathbf{e}_{i}^{T}\mathbf{V}\mathbf{e}_{i}=\gamma_{n}\text{Tr}(\mathbf{V})$, where $\mathbf{e}_{i}$ is the $d$-dimensional vector of all zeros except $1$ at the $i$-th entry. This indicates that a smaller limiting covariance matrix $\mathbf{V}$, according to the Loewner order, results in a smaller trace of $\mathbf{V}$ and consequently in a reduced MSE for large $n$. Consideration for smaller $\mathbf{V}$ will be presented in the next section, where agents have the opportunity to improve their sampling strategies.

Impact of Agent’s Sampling Strategy: In the literature, the mixing time-based technique has been widely used in the non-asymptotic analysis in SGD, DSGD and various LSGD variants in FL [26, 68, 69, 80, 42], i.e., for each agent $i\in[N]$ and some constant $C$,

where $\rho_{i}$ is the mixing rate of the underlying Markov chain. However, typical non-asymptotic analyses often rely on $\rho\triangleq\max_{i}\rho_{i}$ among $N$ agents, i.e., the worst-performing agent in their finite-time bounds [80, 72], or assume an identical mixing rate across all $N$ agents [42, 69].

In contrast, Remark 3 highlights that each agent holds its own limiting covariance matrices $\mathbf{V}_{i}$ and $\mathbf{V}^{\prime}_{i}$, which are predominantly governed by the matrix $\mathbf{U}_{i}$, capturing the agent’s sampling strategy $\{X^{i}_{n}\}$ and contributing equally to the overall performance of UD-SGD. For each agent $i$, denote by $\mathbf{U}_{i}^{X}$ and $\mathbf{U}_{i}^{Y}$ the asymptotic covariance matrices associated with two candidate sampling strategies $\{X^{i}_{n}\}$ and $\{Y^{i}_{n}\}$, respectively. Let $\mathbf{V}^{X}$ and $\mathbf{V}^{Y}$ be the limiting covariance matrices of the distributed system in (12), where agent $i$ employs $\{X^{i}_{n}\}$ and $\{Y^{i}_{n}\}$, respectively, while keeping other agents’ sampling strategies unchanged. Then, we have the following result.

Corollary 3.4 directly follows from the definition of Loewner ordering, and Loewner ordering being closed under addition (i.e., $\mathbf{A}\!\succeq\!\mathbf{B}$ implies $\mathbf{A}\!+\!\mathbf{C}\!\succeq\!\mathbf{B}\!+\!\mathbf{C}$). It demonstrates that even a single agent improves its sampling strategy from $\{X^{i}_{n}\}$ to $\{Y^{i}_{n}\}$, it leads to an overall reduction in $\mathbf{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 $\{Y^{i}_{n}\}$ over the baseline $\{X^{i}_{n}\}$?

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 $\{Y_{n}\}$ is more efficient than $\{X_{n}\}$ if and only if $\boldsymbol{\Sigma}_{X}(\mathbf{g})\succeq\boldsymbol{\Sigma}_{Y}(\mathbf{g})$ for any vector-valued function $\mathbf{g}(\cdot)\in\mathbb{R}^{d}$. Consequently, in the UD-SGD framework, employing a more efficient sampling strategy $\{Y^{i}_{n}\}$ over the baseline $\{X^{i}_{n}\}$ by agent $i$ leads to $\boldsymbol{\Sigma}_{X^{i}}(\nabla F_{i}(\theta^{*},\cdot))\succeq\boldsymbol{\Sigma}_{Y^{i}}(\nabla F_{i}(\theta^{*},\cdot))$, thus satisfying $\mathbf{U}_{i}^{X}\succeq\mathbf{U}_{i}^{Y}$. This finding, as per Corollary 3.4, implies an overall improvement in UD-SGD.

For illustration purposes, we list a 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 [38, 79]; ii) When an agent works with a graph-like data structure and employs a random walk, e.g., agent $i$ in Figure 1, using non-backtracking random walk (NBRW) is 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 [25].³³3Note that SRRW is a nonlinear Markov chain that depends on the relative visit counts of each node in the graph. While its application in single-agent optimization has been studied in [39], 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 as a highly efficient sampling strategy in Section 4. This random-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 a random walk over local D2D network for each agent constitutes the sampling strategy.

Theorem 3.3 and Corollary 3.4 not only qualitatively compare these sampling strategies but also allow for a quantitative assessment of the overall system enhancement. Since every agent contributes equally to the limiting covariance matrix $\mathbf{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 a unique aspect of our framework not addressed in previous works focusing on the worst-performing agent [80, 42, 69, 72].

In this section, we empirically evaluate the effect of agents’ sampling strategies under various communication patterns in UD-SGD. We consider the $L_{2}$-regularized binary classification problem

where the feature vector $\mathbf{x}_{i,j}$ and its corresponding label $y_{i,j}$ are held by agent $i$, with a penalty parameter $\kappa$ set to $1$. We use the ijcnn1 dataset [14] with $22$ features in each data point and $50$k data points in total, which is evenly distributed to two groups with $50$ agents each ($N=100$ agents 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 a 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 a communication network using the DSGD algorithm. This scenario with heterogeneous agents, as depicted in Figure 1, is of great interest in large-scale machine learning [37, 32]. In addition, we employ a decreasing step size $\gamma_{n}=1/n$ in our UD-SGD framework (1) 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, to Section G.1.

The simulation results are obtained through $120$ independent trials. In Figure 2, we assume that the first group of agents perform either i.i.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 in the legend. This plot shows that improved sampling strategy leads to overall convergence speedup since NBRW and SRRW are more efficient than SRW [38, 25]. Furthermore, it illustrates that SRRW is significantly more efficient than NBRW in this simulation setup, i.e., SRRW $\gg$ 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 [65, 1, 38]. The error bar therein also indicates that the random-walk sampling strategy has a significant impact on the overall system performance and SRRW has smaller variance than NBRW and SRW.

In Figure 2, we let the first group of agents perform i.i.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 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 $\mathbf{V}_{i}\!\neq\!\mathbf{V}_{j}$.

While maintaining i.i.d. sampling for the first group of agents, we compare the performance when the second group of agents in Figure 2 employ 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 a 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=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, randomly chosen from $5$ doubly stochastic matrices); DFL (decentralized FL with fixed MH-generated $\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.

Figure 2 and 2 show the performance of different sampling strategies in DSGD-VT and DFL algorithms in 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 Section G.2, we simulate an image classification task with CIFAR-10 dataset [44] by training a $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, we find that upgrading even a 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 are consistent in binary and image classification tasks, underscoring that every agent matters in distributed learning.

In this work, we develop an UD-SGD framework that establishes the CLT of various distributed algorithms 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-grained finite-time bounds to individually characterize each agent’s behavior, and theoretically analyze the effect of SRRW in UD-SGD.

We thank the anonymous reviewers for their constructive comments. This work was supported in part by National Science Foundation under Grant Nos. CNS-2007423, IIS-1910749, and IIS-2421484.