Stability and Generalization for Decentralized Markov SGD

1 Introduction

Stochastic gradient methods form the backbone of modern large-scale machine learning, owing to their simplicity and scalability [Li et al., 2014; Lin et al., 2018]. In many practical applications, however, data samples are not independently drawn at each iteration. Instead, they are generated sequentially by a stochastic process, such as a Markov chain, which introduces temporal dependence into the training procedure. This phenomenon naturally arises in reinforcement learning [Wai et al., 2018; Doan et al., 2020], recommendation systems [Li et al., 2010], and distributed data collection [Lopes and Sayed, 2007; Duchi et al., 2011; Chen et al., 2014; Madry et al., 2017; Shah and Avrachenkov, 2018], where i.i.d. sampling is either infeasible or prohibitively expensive.

In parallel, the increasing scale of data has driven the adoption of decentralized optimization architectures, where multiple workers collaboratively train a shared model using local computations and limited communication [Nedic and Ozdaglar, 2009; Sundhar Ram et al., 2010]. Decentralized stochastic gradient descent (D-SGD) and its variants [Lian et al., 2017; Lian et al., 2018] have attracted significant attention due to their robustness, communication efficiency, and suitability for large networks. While the optimization properties of decentralized algorithms are now relatively well understood [Shi et al., 2015; Yuan et al., 2016; Lian et al., 2017; Koloskova et al., 2020; Sun et al., 2021; Yuan et al., 2023], their statistical behavior-particularly generalization-remains less explored under realistic sampling assumptions.

∗Corresponding author.

Recent progress has begun to address these challenges from different perspectives. Stability-based analyses have established rigorous generalization guarantees for stochastic gradient methods under Markovian sampling, highlighting the role of algorithmic stability in controlling the discrepancy between empirical and population risks [Wang et al., 2022]. Separately, decentralized SGD with Markov chain sampling has been studied primarily from an optimization viewpoint [Sun et al., 2022; Sun et al., 2023; Koloskova et al., 2020], focusing on convergence rates and consensus errors. More recently, stability and generalization properties of decentralized stochastic gradient descent (ascent) (SGDA) algorithms have been investigated under standard i.i.d. sampling assumptions [Sun et al., 2021; Zhu et al., 2022; Bars et al., 2024; Zhu et al., 2023; Zeng and Lei, 2025]. Despite these advances, a unified theoretical understanding of decentralized stochastic gradient methods under Markovian data dependence is still lacking. In particular, existing works either (i) analyze Markov chain sampling in centralized settings, (ii) study decentralized algorithms assuming independent samples, or (iii) focus on optimization performance without addressing generalization. As a result, fundamental questions remain open:

Can one obtain sharp generalization guarantees for decentralized SGD and SGDA when data are generated by Markov chains?

Motivated by these gaps, this paper investigates the theoretical foundations of decentralized stochastic gradient descent and descent-ascent algorithms with Markov chain sampling, and aims to provide a rigorous characterization of their generalization behavior. Building on the stability framework, we develop novel stability bounds for both decentralized SGD and SGDA under Markovian data dependence. Our analysis explicitly captures the interplay between algorithmic stability, network consensus, and the mixing properties of the underlying Markov chains. We generalize stability-based generalization theory for Markov chain stochastic gradient methods to decentralized settings, and complement prior studies on decentralized optimization by providing statistically meaningful guarantees. To the best of our knowledge, this is the first work to systematically study the stability and generalization of decentralized SGD and SGDA under Markovian sampling.

1.1 Differences and Technical Challenges

Unlike existing analyses of decentralized SGD under i.i.d. sampling [Richards and Rebeschini, 2020; Sun et al., 2021; Zhu et al., 2022; Bars et al., 2024; Zeng and Lei, 2025], this work allows each worker to access data through a Markov chain, which introduces temporal dependence and breaks the sample-wise independence typically used in stability arguments. Compared with centralized Mc-SGD [Wang et al., 2022], decentralization further introduces consensus dynamics, leading to an additional error accumulation through network disagreement. A key technical challenge is to control the interaction between these two effects without imposing mixing-time or spectral assumptions on the Markov chain. This is resolved by exploiting aggregation identities that depend only on the update structure, rather than on the specific sampling mechanism. As a result, i.i.d.-type stability bounds can still be recovered in the decentralized Markovian setting.

1.2 Contributions

Our main contributions can be summarized as follows.

• Stability analysis of decentralized SGD with Markovian sampling. We establish on-average stability bounds for decentralized SGD under Markov chain sampling (See Theorem 1). The resulting bounds match those of decentralized SGD under i.i.d. sampling up to the same consensus-dependent terms, showing that Markovian sampling does not incur additional stability degradation in the decentralized setting.
• Excess risk and generalization guarantees. Based on the stability analysis, we derive excess risk and generalization bounds for Decentralized Markov SGD (DMcSGD) under both smooth and non-smooth losses (See Theorem 3-4). Our results explicitly characterize the roles of network connectivity, Markov chain mixing, and stepsize selection, and recover known centralized and i.i.d.-based decentralized rates as special cases.
• Stability and generalization of decentralized SGDA with Markovian sampling. We extend the stabilitybased framework to decentralized stochastic gradient descent ascent (DMc-SGDA) for convex-concave minimax problems. We obtain on-average argument stability bounds and corresponding generalization guarantees for both weak primal-dual risk and primal population risk (See Theorem 6-7), covering smooth setting.

2 RelatedWork

Generalization Analysis of D-SGD. Recent studies have investigated the generalization behavior of decentralized learning primarily through stability-based analyses, which relate the generalization gap to algorithmic sensitivity and networkinduced perturbations. These works reveal how communication topology and consensus dynamics influence generalization, though the resulting bounds often grow with the number of iterations unless additional structural assumptions, such as strong convexity, are imposed. Representative results include stability- and complexity-based bounds for D-SGD in both smooth and non-smooth settings [Richards and Rebeschini, 2020; Sun et al., 2021], analyses of topology-dependent effects under on-average stability frameworks [Zhu et al., 2022], and improvements that recover rates comparable to centralized SGD [Bars et al., 2024]. Extensions to heterogeneous data distributions and weaker regularity conditions have also been considered [Ye et al., 2025; Zeng and Lei, 2025]. A detailed comparison of these results is provided in Table 1. Related generalization analyses have further been developed for several D-SGD variants, including asynchronous implementations [Deng et al., 2023], minibatch methods [Wang and Chen, 2024], decentralized SGDA [Zhu et al., 2023], and zeroth-order optimization schemes [Wang and Chen, 2024; Hu et al., 2025].

Markov Chain Gradient Descent. Beyond stability and generalization, Markov chain stochastic gradient methods have been extensively investigated from an optimization perspective, motivated by scenarios where independent sampling is infeasible and data are generated sequentially [Ram et al., 2009; Tadi´c and Doucet, 2011; Duchi et al., 2012]. A central theme in this line of work is to understand how the temporal dependence induced by Markovian sampling affects convergence rates. Convergence properties of SGD with Markovian sampling for convex and non-convex problems were investigated in Sun et al. [2021]. The same work also developed convergence guarantees for non-convex problems under Markovian sampling. Decentralized SGD with gradients sampled from non-reversible Markov chains was further studied in Sun et al. [2023], which characterized the impact of non-reversibility on convergence behavior. Acceleration techniques have also been considered in this setting. Doan et al. [2020] analyzed accelerated ergodic Markov chain SGD for both convex and non-convex objectives, while Doan [2022] further relaxed standard assumptions by deriving convergence rates without requiring bounded gradients.

3 Preliminaries

We study a decentralized learning setting with m computing nodes, where each node stores n training samples. The full dataset is denoted by S = {S1, S2, · · · , Sm}, and each local dataset Sr = {Z1(1), · · · ,Zk(r), · · · ,Zn(m)} consists of n samples drawn from an unknown distribution D. A learning algorithm A, such as (decentralized) SGD, maps the dataset S to a model parameter in a hypothesis space W. The performance of a model w ∈ W is evaluated through a loss function f (w;Z), which induces the population risk (expected risk) minw∈W R(w) := EZ∼D [f (w;Z)] . Since the datagenerating distribution is inaccessible, the algorithm instead minimizes its empirical analogue computed over the observed samples. In the decentralized setting, this empirical objective can be written as

with RSr denoting the corresponding local empirical risk at node/machine r.

Although A(S) may fit the training data well, good empirical performance does not necessarily translate to good population performance. This motivates the study of the expected gap between the population and empirical risks evaluated at the algorithm output, namely

which we refer to as the generalization error. Beyond generalization, we are also interested in how far the learned model is from the optimal population solution.

Definition 1. The excess generalization error of the learned model, ϵexcess := ES,A [R(A(S)) -R(w∗ )], where w∗ is denote the minimizer of R(·). This term can then be expressed as

As before, the underlying distribution D is unknown, and learning algorithms operate on a finite dataset distributed across m workers. The corresponding empirical objective is therefore given by

In contrast to standard minimization, minimax learning involves two coupled variables, which makes generalization more nuanced. To streamline notation, we write the (possibly randomized) output of algorithm A as A(S) = (Aw(S),Av(S)). We focus on two notions of performance that will be used throughout the paper [Farnia and Ozdaglar, 2021; Lei et al., 2021b; Zhu et al., 2023].

Definition 2 (Weak Primal-Dual (PD) Risk). The weak Primal-Dual population risk ∆w (Aw, Av):

The weak PD empirical risk ∆wemp (Aw, Av):

The weak PD generalization error of the model:

Definition 3 (Primal Risk). The primal population and empirical risks of A(S):

The primal generalization error is defined as

The excess primal population risk of the model:

3.1 Decentralized SGDwithMarkov Sampling

We consider a decentralized optimization framework based on stochastic gradient descent, originally proposed in Lian et al. [2017], and adopt its projected variant to handle constrained parameter domains. In this setting, a network of m

where w⋆ be the minimizer of RS(·).

Remark 1. Since E [RS (w∗ )] = E [R(w∗ )] and the empirical risk minimizer satisfies RS(w∗S ) ≤ RS(w∗ ), the last item is guaranteed to be non-positive. Consequently, most theoretical analyses can be reduced to concentrating on the first two terms, the generalization error and the optimization error.

We now turn to decentralized minimax learning problems, which naturally arise in adversarial learning and robust optimization [Goodfellow et al., 2014; Madry et al., 2017]. In this setting, the objective depends on a pair of variables: a primal variable w ∈ W ⊂ Rd and a dual variable v ∈ V ⊂ Rd . Given a loss function f : W × V × Z → [0,∞), the population-level minimax objective is defined as

nodes cooperatively solves a learning problem while maintaining local model copies. Communication between nodes is governed by a weighted graph, through which neighboring nodes exchange information at each iteration. At a high level, each iteration of the algorithm consists of two stages. First, nodes perform a consensus operation by aggregating model information from their neighbors. Subsequently, each node updates its local model using a stochastic gradient computed from a data sample generated by a local Markov chain, followed by a projection step to ensure feasibility. This procedure naturally extends decentralized SGD to scenarios where data are not independently sampled.

The complete procedure, referred to as Decentralized Markov Stochastic Gradient Descent (Ascent), is summarized in Algorithm 1. For each node i, the algorithm initializes local primal (and dual) variables and iteratively updates them using a combination of communication and stochastic gradient steps. After T iterations, the network outputs the averaged primal (and dual) iterates. The communication structure of

Algorithm 1 Decentralized Markov Stochastic Gradient Descent (Ascent)

Input: Initialize ∀i,w0 (i) = w0 , (v0 (i) = v0 ), stepsizes {ηt}Tt=1 ,weight matrix P and the iteration number T .

• 1: for t = 1, 2, · · · , T do
• 2: for i = 1, 2, · · · ,mdo
• 3: Sample Zjt(i) via a Markov chain

• 7: end for
• 8: end for

the decentralized network is encoded by a matrix P ∈ Rm×m , which specifies how information is mixed across nodes. The matrix P is assumed to satisfy the following properties: (1) P is symmetric; (2) all entries satisfy Pij ∈ [0, 1]; (3) P is doubly stochastic, i.e., 1TmP = 1Tm and P1m = 1m.

Gossip Matrix. Let λ1 ≥ λ2 ≥ · · · ≥ λm denote the eigenvalues of P, and define γ := 1 - λ = 1 - max{|λ2(P)|, |λm(P)|} [Sun et al., 2021; Zhu et al., 2022; Deng et al., 2023; Bars et al., 2024; Wang and Chen, 2024; Zeng and Lei, 2025]. The quantity λ ∈ [0, 1) characterizes the speed at which consensus is achieved across the network. In particular, smaller values of λ correspond to faster information mixing. A fully connected network yields λ = 0, in which case P reduces to the uniform averaging matrix.

Update Order. Following existing decentralized SGD schemes [Lian et al., 2017], the update at each node can be organized according to two distinct patterns. In the Gradientthen-Consensus (GtC) variant, each node first performs a local stochastic gradient step and subsequently mixes the updated parameters with its neighbors:

In contrast, the Consensus-then-Gradient (CtG) variant reverses this order. Nodes first aggregate information through the gossip matrix and then apply a stochastic gradient update using locally sampled data:

From an optimization viewpoint, GtC and CtG exhibit similar convergence behavior, enabling communication and computation to be overlapped in practice. Their difference becomes pronounced in stability and generalization analysis: the CtG update relies solely on local gradients, which magnifies the effects of data heterogeneity and network disagreement. Consequently, establishing stability guarantees for CtG typically requires more refined analysis or stronger structural assumptions [Sun et al., 2021; Deng et al., 2023; Zeng and Lei, 2025; Le Bars et al., 2023].

Markov Chain Sampling. We now summarize the basic concepts of finite-state, time-homogeneous Markov chains that are relevant to our analysis. These notions formalize the dependence structure induced by Markovian data sampling.

Definition 4. A stochastic process {Xk}k≥1 taking values in a finite state space {1, 2, . . . , n} is called a time-homogeneous Markov chain with transition matrix H ∈ Rn×n if Pr (Xk+1 = j | X0, . . . ,Xk = i) = Pr (Xk+1 = j | Xk = i) = Hi,j, for all states i, j ∈ {1, 2, . . . , n} and k ≥ 0.

Let πk denote the distribution of Xk, viewed as a row vector. Then πk = πk-1H = π0Hk , where Hk denotes the k-step transition matrix. A Markov chain is said to be irreducible if every state can be reached from any other state in a finite number of steps. A state is aperiodic if it does not exhibit deterministic cyclic behavior, and the chain is aperiodic if all states are aperiodic. Under irreducibility and aperiodicity, the chain admits a unique stationary distribution π∗ satisfying π∗ = π∗H and mini π∗ i > 0. Moreover, the transition matrix

Mixing Behavior. An important quantity governing the statistical behavior of Markov chain sampling is the mixing time, which measures how quickly the distribution of the chain approaches its stationary distribution. Mixing properties provide explicit bounds on the deviation between πk and π∗ a s a function of k, and play a central role in controlling the bias introduced by Markovian dependence. Following [Sun et al., 2018; Sun et al., 2023], we will characterize this deviation through matrix-based bounds that are well suited for stability analysis.

4 Main Results

This section presents our main theoretical results and the assumptions required for our analysis.

Assumption 1 (L-Lipschitz). For any Z ∼ D and w, ˜w ∈ W, the loss function f(w;Z) satisifies

Remark 2. This condition ensures that perturbations in the model parameters induce proportionally bounded changes in the loss. In particular, whenever the gradient exists, its norm is uniformly bounded by L.

Assumption 2 (β-Smoothness). For any Z ∼ D and w, ˜w ∈ W, the loss function has Lipschitz-continuous gradient:

Remark 3. Smoothness guarantees regular variation of the gradient field and plays a key role in controlling the propagation of perturbations along the optimization trajectory. We next formalize the assumptions on the sampling mechanism employed at each worker.

Assumption 3. Each worker accesses data through a finitestate, time-homogeneous Markov chain that is irreducible and aperiodic. All workers are assumed to employ Markov chains with a common transition matrix H and the same sationary distrubtion. 1

Remark 4. Such Markovian sampling schemes have been widely studied in the literature [Sun et al., 2018; Mao et al., 2020; Doan et al., 2020; Sun et al., 2023]. For example, Markov chain-based SGD has been proposed for pairwise learning problems, including AUC maximization, bipartite ranking, and metric learning [Lei et al., 2020; Lei et al., 2021a; Yang et al., 2021]. In these settings, model updates are driven by data pairs generated via an auxiliary Markov chain, which satisfies irreducibility and aperiodicity under mild conditions. Similar assumptions also arise in decentralized consensus optimization over multi-agent networks, where the Markov chain state space coincides with the finite set of agents and a common transition matrix is shared across nodes.

1 This assumption is introduced primarily to simplify exposition. The analysis can be extended to heterogeneous Markov chains across workers with additional technical effort.

Assumption 4 (Reversibility). The Markov transition matrix satisfies H = HT .

Reversibility enables a clean characterization of mixing behavior and will be used to derive explicit stability bounds.

4.1 Generalization Analysis for DMc-SGD

We adopt an on-average notion of argument stability [Lei and Ying, 2020; Zhu et al., 2022; Wang and Chen, 2024; Zeng and Lei, 2025], which measures the expected deviation between algorithm outputs when a single training example is replaced.

Definition 5. (On-Average Argument Stability) Let S = (S1, · · · , Sm) and ˜ S = ( ˜ S1, · · · , ˜ Sm) be two independent datasets drawn from D. Let Srk denotes denote the dataset obtained by replacing the k-th sample at the r-th worker in S with the corresponding sample from ˜ S. A (possibly randomized) algorithm A is said to be ℓ1 on-average argument ϵ-stable if

Lemma 1. (Generalization via On-Average Stability. [Lei and Ying, 2020]). Let A be ℓ1 on-average argument ϵ-stable and suppose Assumption 1 holds. Then,

This result reduces the analysis of generalization error to that of stability. We now present explicit stability bounds for DMc-SGD under convexity.

Theorem 1 (Stability Bounds for DMc-SGD). Assume that f(w; Z) is convex and L-Lipshitz.

• (Smooth Case) If f(w;Z) is β-smooth and η ≤ 2/β, then after T iterations of DMc-SGD,

• (Non-smooth Case) Without smoothness, DMc-SGD remains on-average ϵ-stable with

Remark 5. Compared with stability bounds for centralized SGD with Markovian sampling [Wang et al., 2022], Theorem 1 contains an additional consensus error term that captures the effect of decentralized communication. This term naturally arises in decentralized optimization and is absent in the centralized setting. More importantly, when compared with decentralized SGD under i.i.d. sampling [Sun et al., 2021; Zeng and Lei, 2025], the stability bound obtained here has exactly the same form and order. In particular, the result is derived without imposing any assumptions on the underlying Markov chain, such as mixing-time or spectral conditions. This shows that Markovian sampling does not lead to worse stability guarantees than i.i.d. sampling for decentralized SGD.

The key technical ingredient behind this result is the identity ∑nk=1 I{jt=k} = 1, where I{·} denotes the indicator function. Since this property is independent of the specific sampling mechanism, the argument is not tied to Markov chain sampling. As a consequence, the same stability analysis applies to other non-i.i.d. sampling schemes, such as particle filtering or SGLD-based sampling. A detailed comparison with existing stability results is summarized in Table 2.

The stability bounds in Theorem 2 explicitly depend on the stepsize sequence, revealing how the choice of learning rate mediates the effect of decentralization. In particular, smaller stepsizes mitigate the amplification of instability caused by imperfect consensus across the network. To make this dependence more transparent, we specialize the general bounds to two commonly adopted stepsize schedules.

Corollary 1 (Stability under Smooth Losses). Suppose f(w;Z) is convex and satisfies both the Lipschitz and smoothness conditions.

• (Constant Stepsize) If the stepsize ηt = η ≤ 2/β, the average stability parameter satisfies ϵ ≤ 4η2 βLT 1-λ + 2ηLT mn .
• (Decreasing Stepsize) If the stepsize ηt = 1 t+1 ≤ 2/β, then ϵ ≤ 4βLCλT T+1 + 2L ln(T+1) mn .

The next result addresses the non-smooth setting, where stability exhibits a qualitatively different dependence on the iteration horizon.

Corollary 2 (Stability under Non-smooth Losses). Suppose f(w; Z) is convex and L-Lipschitz.

• (Constant Stepsize) If the stepsize ηt = η ≤ 2/β, the average stability we get ϵ ≤ 2Lη√T + 4ηL√T √1-λ + 4ηLT mn .
• (Decreasing Stepsize) If the stepsize ηt = 1 t+1 ≤ 2/β, the average stability we have ϵ ≤ 2L+4L√Cλ+ 2L ln T mn .

The above corollaries characterize the stability of the final iterate produced by DMc-SGD. However, in general convex optimization, performance guarantees are often stated for a weighted average of iterates rather than the last iterate. Following standard practice in decentralized optimization [Sun et al., 2023], we therefore consider the stepsize-weighted average ¯wT = ∑Tt=1 ηtwt /∑Tt=1 ηt. The next theorem establishes generalization guarantees for this averaged solution.

Theorem 2 (Generalization of Averaged Iterates). Suppose f(w; Z) is convex, satisfying Lipschitz property. (Smooth Case) If f(w; Z) is β-smooth and the stepsize ηt = η ≤ 2/β, the generalization error we get

(Non-smooth Case) If the stepsize ηt = η, then

We are now ready to combine the optimization and generalization results to obtain explicit excess risk bounds for DMcSGD. The following results characterize how decentralization and Markovian sampling jointly influence the statistical performance of the averaged iterate.

Theorem 3 (Excess Risk under Smooth Case). Assume that the loss function f(w;Z) is convex, L-Lipschitz and βSmooth, and that Assumptions 4 holds. Consider DMc-SGD initialized at w0 = 0, and let {wt }Tt=1 denote the iterates generated with the constant stepsize ηt = η ≤ 2/β. If we select T = O(mn) and η = 1 √T logT , then

The next theorem addresses the non-smooth regime, where the interaction between stepsize selection and network effects leads to a different scaling behavior.

Theorem 4 (Excess Risk under Nonsmooth Case). Suppose that the loss function f(w;Z) is convex, L-Lipschitz , and that Assumptions 4 holds. Let DMc-SGD run for T iterations with a constant stepsize ηt = η. If we choose T = O ( m2 n2 1-λ )

Remark 6. In the smooth case, the excess risk consists of two distinct components: a network-dependent term scaling as 1/(γ log T), which reflects the effect of imperfect consensus, and a Markovian sampling term governed by the mixing property of the underlying chain through log(1/λ(H)). When γ = 1, the bound reduces to the known excess risk rate of centralized Mc-SGD [Wang et al., 2022].

In the non-smooth regime, the slower rate arises from the combined effect of non-smoothness and decentralized communication, leading to a stronger dependence on both the network spectral gap γ and the sample size mn. Nevertheless, the resulting bound remains consistent with existing excess risk guarantees for Mc-SGD. We note, however, that the existing analysis [Wang et al., 2022] reports a O(1/√n) rate in the non-smooth case, whereas a careful derivation yields a sharper O(log n/n3/2 ) dependence (up to logarithmic factors involving the Markov chain mixing). A detailed discussion of this discrepancy is provided in the appendix F. Overall, these results indicate that Markovian sampling does not introduce an additional statistical penalty beyond what is already induced by decentralization and non-smoothness, and that its effect is explicitly captured through the mixing characteristics of the Markov chain.

4.2 Generalization Analysis for DMc-SGDA

We now extend the stability-based generalization analysis to decentralized stochastic gradient descent ascent applied to minimax optimization problems. Let ( ¯wT , ¯vT ) denote the output of DMc-SGDA after T iterations, where the averaged primal and dual variables are defined a

Our goal is to characterize how decentralized communication and Markovian sampling affect the generalization behavior of DMc-SGDA in minimax settings. We first impose some tandard definitions and assumptions [Lei et al., 2021b; Farnia and Ozdaglar, 2021; Ozdaglar et al., 2022; Zhu et al., 2023].

Definition 6. Let ρ ≥ 0. A function f(w, v) : W ×V ↦→ R is said to be ρ-strongly-convex-strongly-concave (ρ-SC-SC) if, for any v ∈ V, the mapping w ↦→ f(w, v) is ρ-stronglyconvex and, for any w ∈ W, the mapping v ↦→ f(w, v) is ρ-strongly-concave. The special case ρ = 0 corresponds to convex-concave objectives.

Assumption 5. For all w ∈ W, v ∈ V and Z ∈ Z, ∥∇wf(w, v;Z)∥2 ≤ L, ∥∇vf(w, v;Z)∥2 ≤ L.

Assumption 6. For any Z, the mapping (w, v) ↦→ f(w, v;Z) is β-smooth in the sense that, for all (w, v) and ( ˜w, ˜v),

To quantify the sensitivity of DMc-SGDA, we adopt an onaverage notion of argument stability that simultaneously accounts for perturbations in both the primal and dual variables. Definition 7 (Dencentralized Argument Stability for Minmax Problems). Let S and S(rk) be constructed as in Definition 5. A randomized algorithm A is said to be on-average ϵ-argument-stable for minimax problems if 1 mn ∑mr=1 ∑nk=1 E[ ∥Aw(S) -Aw (Srk)∥2 + ∥Av(S) - Av (Srk)∥2 ] ≤ ϵ.

We will establish explicit stability bounds for DMc-SGDA applied to convex-concave objectives.

Theorem5. (Stability of DMc-SGDA) Consider DMc-SGDA run for T iterations on a convex-concave objective, i.e., for every Z ∈ Z the mapping (w, v) ↦→ f(w, v;Z) is convex in w and concave in v. Assume W = Rd and Assumption 5 holds. Then the algorithm output is on-average ϵ-argument stable, where ϵ can be bounded as follows.

Smooth regime. If Assumption 6 holds and the stepsizes satisfy ∑Tt=1 ηt ≤ 1/ (2β), then

Non-smooth regime. Without Assumption 6, a valid bound is

Remark 7. This theorem exhibits the same stability structure as decentralized SGDA under i.i.d. sampling [Zhu et al., 2023] in the smooth regime, with comparable dependence on the stepsize sequence and the network connectivity. Moreover, we provide stability guarantees for the non-smooth setting, which has not been explicitly addressed in prior work. Compared with centralized SGDA or Mc-SGDA [Lei et al., 2021b; Wang et al., 2022], the above bounds contain an additional consensus-related term that arises from decentralized communication.

The following results characterize the generalization behavior of DMc-SGDA under different performance metrics.

Theorem 6 (Generalization Error of DMc-SGDA). Consider DMc-SGDA with a constant stepsize η run for T iterations, and define Aw(S) = ¯wT and Av(S) = ¯vT . Suppose Assumption 5 holds, W = Rd , and for every Z the function (w, v) ↦→ f(w, v;Z) is convex-concave. (In addition, suppose the mapping v ↦→ R(w, v) is ρ-strongly concave.)

• (Smooth case) If Assumption 6 holds and the stepsizes satisfy ∑Tt=1 ηt ≤ 1/ (2β), then

• (Non-smooth case) In the absence of smoothness, the same quantity can be bounded as

We next characterize the population-level performance of DMc-SGDA in terms of the weak primal-dual (PD) risk. Throughout, let Dw and Dv denote the diameters of the feasible sets W and V, respectively.

Theorem 7 (Weak PD Population Risk). Consider DMcSGDA run with a constant stepsize ηt = η for T iterations, and let ( ¯wT , ¯vT ) denote the averaged iterates. Suppose that Assumptions 3-6 hold, and that for every Z the function (w, v) ↦→ f(w, v;Z) is convex-concave. If T = mn and η = (T log(T))-1/2 , then

5 Conclusion

We investigated the stability and generalization of decentralized stochastic gradient methods with Markovian sampling. Our analysis shows that, despite temporal dependence and decentralized communication, i.i.d.-type stability and generalization guarantees can still be obtained under appropriate conditions. The results extend naturally to decentralized minimax optimization and highlight the robustness of stabilitybased analyses beyond independent sampling.

Acknowledgements

This work is supported in part by the National Natural Science Foundation of China (Grant Nos. 62522610, 62376278), and NUDT Foundational Research Funding (JS25-02).