Paper deep dive
Decentralized Stochastic Subgradient-type Methods with Communication Compression for Nonsmooth Nonconvex Optimization
Siyuan Zhang, Nachuan Xiao, Xin Liu
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 97%
Last extracted: 7/5/2026, 11:17:57 AM
Summary
The paper proposes a general framework called DESC (Decentralized Stochastic Subgradient-type methods with Communication Compression) to address nonsmooth nonconvex decentralized optimization problems. The framework unifies various methods using either unbiased compression or contractive compression with error compensation. By relating iterates to continuous-time differential inclusions, the authors establish global convergence for methods in the framework, even for non-Clarke-regular functions (common in neural networks with ReLU/Leaky ReLU). The work extends existing methods like QDGD and CHOCO-SGD to the nonsmooth regime and introduces new variants like momentum-based and sign-based decentralized stochastic subgradient methods.
Entities (12)
Relation Signals (5)
DESC → addresses → nonsmooth nonconvex optimization
confidence 100% · We propose a general framework that unifies various decentralized stochastic subgradient-type methods... for nonsmooth nonconvex optimization.
DESC → unifies → unbiased compression
confidence 100% · Our framework (DESC) provides a unified decentralized update scheme with compression, which covers two mainstream compression approaches: unbiased compression and contractive compression
DESC → unifies → contractive compression
confidence 100% · Our framework (DESC) provides a unified decentralized update scheme with compression, which covers two mainstream compression approaches: unbiased compression and contractive compression
QDGD → iscoveredby → DESC
confidence 90% · the nonsmooth extensions of common decentralized stochastic gradient-type methods... such as QDGD [51]
CHOCO-SGD → iscoveredby → DESC
confidence 90% · the nonsmooth extensions of common decentralized stochastic gradient-type methods... such as CHOCO-SGD [32]
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In this paper, we consider the nonsmooth nonconvex decentralized optimization problem, where inter-agent communication is compressed. We propose a general framework that unifies various decentralized stochastic subgradient-type methods with unbiased compression and contractive compression with error compensation. By relating the consensus-error iterates and the averaged iterates to the trajectories of continuous-time differential inclusions, we establish global convergence for all methods encompassed by our framework when the objective functions are nonsmooth and lack Clarke regularity. Based on our framework, we further develop several compression-based methods, including decentralized stochastic subgradient methods utilizing sign-based regularization and gradient-tracking momentum. Preliminary numerical experiments empirically support our theoretical results and highlight the communication-accuracy trade-off of the newly developed methods.
Tags
Links
- Source: https://arxiv.org/abs/2607.01755v1
- Canonical: https://arxiv.org/abs/2607.01755v1
Trouble viewing inline? Open PDF directly →
Full Text
141,042 characters extracted from source content.
Expand or collapse full text
Decentralized Stochastic Subgradient-type Methods with Communication Compression for Nonsmooth Nonconvex Optimization Siyuan Zhang, Nachuan Xiao, Xin Liu Abstract In this paper, we consider the nonsmooth nonconvex decentralized optimization problem, where inter-agent communication is compressed. We propose a general framework that unifies various decentralized stochastic subgradient-type methods with unbiased compression and contractive compression with error compensation. By relating the consensus-error iterates and the averaged iterates to the trajectories of continuous-time differential inclusions, we establish global convergence for all methods encompassed by our framework when the objective functions are nonsmooth and lack Clarke regularity. Based on our framework, we further develop several compression-based methods, including decentralized stochastic subgradient methods utilizing sign-based regularization and gradient-tracking momentum. Preliminary numerical experiments empirically support our theoretical results and highlight the communication-accuracy trade-off of the newly developed methods. Keywords: Nonsmooth optimization, decentralized optimization, communication compression, stochastic subgradient-type method, conservative field, Lyapunov function. 1 Introduction In this paper, we consider the following decentralized optimization problem (DOP) over an undirected connected network =(,) G=( V, E), min1,2,…,d∈ℝn _ x_1, x_2,…, x_d ^n ∑i=1dζi∼iFi(i,ζi), _i=1^dE_ _i _iF_i( x_i, _i), (DOP) s.t. i=j,∀(i,j)∈. x_i= x_j, ∀(i,j)∈ E. Here, the node set =1,…,d V=\1,…,d\ stands for the collection of agents, and the edge set E represents the communication links between agents. Each agent i is associated with a local cost function Fi(⋅,ζi)F_i(·, _i) and a local data distribution iP_i. The expectation-form cost function is denoted by fi():=ζi∼iFi(,ζi),f_i( x):=E_ _i _iF_i( x, _i), which is assumed to be locally Lipschitz continuous, nonconvex and possibly nonsmooth. The optimization problem (DOP) has wide applications in wireless edge computing [20, 16, 41], multi-agent target seeking [59, 49], privacy-preserving systems [30, 12] and distributed learning [70, 24]. By eliminating the need for a central server, decentralized optimization effectively mitigates inherent issues in traditional centralized optimization, such as server failures, privacy leakage, and communication bottlenecks. However, high-dimensional variables and limited bandwidth resources necessitate the development of more communication-efficient methods. One way to alleviate the communication overhead is communication compression, which transmits compressed messages between the agents using compression operators. Mainstream compression operators include quantization operators [1, 62, 69, 25] and sparsification operators [2, 58, 52, 23, 73, 50, 7], both of which were originally developed in distributed optimization with a central server to compress high-dimensional gradients. Nowadays, communication compression has been widely used in decentralized settings. One line of research employs randomized unbiased compression operators to transmit inexact information directly, including QDGD [51], S-NEAR-DGD [27], QDSG [35, 21] and IC-GT [54]. These methods typically assume that the compression operators are variance-bounded—either absolutely or proportionally to the squared norm of the input variables—and that the objective functions are (strongly) convex and smooth. Under such assumptions, QDGD [51] proves that the expected deviation from the optimal solution gradually vanishes. S-NEAR-DGD [27] and IC-GT [54] show that, with fixed step-sizes, the iterates converge linearly in expectation to a neighborhood of the optimum. QDSG [35, 21] establishes that the iterative sequence converges almost surely to a solution under properly chosen diminishing step-sizes and consensus parameters. In addition, to mitigate the imprecision introduced by compression, DCD-SGD and ECD-SGD [60] employ difference compression and extrapolation compression techniques. A concise comparison of representative decentralized stochastic gradient-type methods with unbiased compression is provided in Table 1. Another line of work [31, 56, 72, 38, 68] focuses on employing randomized contractive compression operators in conjunction with (implicit) error-compensation mechanisms to achieve efficient communication while maintaining convergence. CHOCO-SGD [32] is a decentralized stochastic gradient descent method that combines difference-based contractive compression with error compensation. The authors show that CHOCO-SGD attains a convergence rate close to that of the centralized counterpart even under arbitrarily high compression ratios, for objectives that are either strongly convex [32] or nonconvex but Lipschitz smooth [31]. Moreover, SPARQ-SGD [57] is an event-triggered variant of CHOCO-SGD that reduces the number of communication rounds. SQuARM-SGD [56] can be interpreted as CHOCO-SGD with local-update Nesterov momentum, which guarantees ergodic convergence in expectation for smooth objective functions. C-GT [38] and BEER [72] incorporate gradient-tracking into decentralized SGD with difference-based contractive compression to handle heterogeneity across multi-agents, and [40] adopts a compression technique together with a momentum-based adaptive learning rate to accelerate empirical convergence. DoCoM [68] and MoTEF [28] integrate communication compression with momentum tracking and error feedback, showing improved theoretical and empirical performance under arbitrary data heterogeneity. DEF-ATC [43] studies decentralized learning with bounded-distortion compression operators, a class that subsumes contractive compression operators as a special case. It also generalizes the existing difference-based compression scheme with error feedback. A concise comparison of representative decentralized stochastic gradient-type methods with contractive compression is summarized in Table 2. More recently, [39] develops a robust compressed push-pull method (RCPP) for smooth nonconvex objectives over general directed graphs by combining gradient tracking with compression. To incorporate privacy constraints into communication-efficient decentralized learning over directed graphs, [74] proposes DP-CSGP, which couples compressed stochastic gradient push with node-level (ε,δ)( ,δ)-differential privacy guarantees and provides utility bounds for general smooth nonconvex objectives. Method Update scheme Step-sizes Conditions on fif_i Conditions on compressed operator QDGD [51] GD Two diminishing scales α=Θ(K−(1−δ)/4)α= (K^-(1-δ)/4), ε=Θ(K−3(1−δ)/4) = (K^-3(1-δ)/4) Smooth, strongly convex Unbiased quantizer; absolute or relative second-moment bound S-NEAR-DGD [27] GD Constant Strongly convex, Lipschitz gradients Inexact communication model with random distortion QDSG [35, 21] GD Diminishing (subgradient-type) Convex / strongly convex, possibly nonsmooth Random/adaptive quantization; resolution-dependent quantization error IC-GT [54] GT Constant Smooth, strongly convex Inexact communication noise; probabilistic quantization or additive channel noise Our work (DESC) GD/GT GD-M ηk=o(1/logk) _k=o(1/ k), three-timescale ηk,θk,γk\ _k, _k, _k\ Path-differentiable, coercive Unbiased compression operator (Assumption 3.2) Table 1: A brief comparison of decentralized stochastic gradient-type methods with unbiased compression. Here, “GD”, “GT”, and “GD-M” are abbreviations of “gradient descent”, “gradient tracking”, and “gradient descent with momentum”, respectively. Method Update scheme Step-sizes Conditions on fif_i Conditions on compressed operator CHOCO-SGD [32, 31] GD Strongly convex: ηk=4μ(a+k) _k= 4μ(a+k); smooth nonconvex: fixed η=Θ(n/K)η= ( n/K) Smooth strongly convex, or smooth nonconvex Contractive compressor applied to model differences SPARQ-SGD [57] GD Strongly convex: ηk=8μ(a+k) _k= 8μ(a+k); smooth nonconvex: fixed η=n/Kη= n/K Smooth strongly convex, or smooth nonconvex Contractive compressor with event-triggered communication SQuARM-SGD [56] GD-M Constant / standard SGD-type schedule with local momentum Smooth nonconvex Contractive compressor with error compensation C-GT [38] GT Constant Smooth strongly convex Contractive compressor in gradient-tracking communication BEER [72] GT Constant Smooth nonconvex, arbitrary heterogeneity Contractive compressor on model and tracking differences DoCoM [68] GT-M Constant Smooth nonconvex; PL for linear convergence Contractive compressor with momentum tracking and EF MoTEF [28] GT-M Constant Smooth nonconvex, objective bounded below Contractive compressor with momentum tracking and EF Our work (DESC) GD/GT GD-M ηk=o(1/logk) _k=o(1/ k), three-timescale ηk,θk,γk\ _k, _k, _k\ Path-differentiable, coercive Contractive compression operator (Assumption 3.4) Table 2: A brief comparison of decentralized stochastic gradient-type methods with contractive compression. Here, “GD”, “GT”, “GD-M”, and “GT-M” are abbreviations of “gradient descent”, “gradient tracking”, “gradient descent with momentum”, and “gradient tracking with momentum”, respectively. Decentralized optimization methods with communication compression are intrinsically well-suited for the distributed training of neural networks, as billions of parameters need to be transmitted across the agents. In modern deep neural network architectures, widely adopted nonsmooth activation functions, such as ReLU and leaky ReLU, have become essential building blocks. The use of these activations gives rise to nonsmooth loss functions that lack Clarke regularity [17] (hereafter referred to as non‑Clarke‑regular functions). However, the existing convergence analyses in the above-mentioned works predominantly assume that each fif_i is convex or smooth nonconvex (at least differentiable), thus precluding various important applications in the distributed training of nonsmooth neural networks. A limited number of works [36, 67] study the convergence of proximal-type compression-based algorithms for decentralized composite optimization problems. Nevertheless, objective functions of these problems are still weakly convex, and hence Clarke-regular, which is essentially distinct from the nonsmoothness arising in non–Clarke-regular loss functions. Consequently, whether we can establish convergence theories for decentralized compression-based methods in nonconvex nonsmooth optimization, especially in the training of nonsmooth neural networks, is a question worth exploring and contemplating. When training nonsmooth neural networks, the subgradients of the loss function are always computed using the automatic differentiation (AD) algorithm, which is widely adopted in various popular machine learning packages, such as TensorFlow, PyTorch, and JAX. Utilizing the chain rule, the AD algorithm constructs generalized subgradients through the composition of Jacobians of each network block. However, as the chain rule fails for non‑Clarke‑regular functions (see examples in [10]), the outputs of the AD algorithm may not belong to the Clarke subdifferential [17] of such a loss function. To tackle this issue, [11] introduces the conservative field, a generalization of the Clarke subdifferential applicable to a broad class of functions referred to as path-differentiable functions. Path-differentiable functions are sufficiently general to encompass a wide range of objective functions in real-world applications, particularly the loss functions of nonsmooth neural networks. More importantly, the conservative field admits chain rules for path-differentiable functions and thus contains the output of the AD algorithm. Based on the concept of conservative field, several recent works [11, 19, 65, 33, 46, 66, 71] leverage the ordinary differential equation (ODE) approach [4, 3, 14, 22] to study the behavior of stochastic subgradient-based methods for non-Clarke-regular functions. However, extending these results to multi-agent settings with communication compression is nontrivial, particularly in the consensus analysis and the construction of appropriate differential inclusions. 1.1 A general framework for decentralized stochastic subgradient-type methods with communication compression In this paper, we consider a general framework for decentralized stochastic subgradient-type methods with communication compression (DESC) in nonsmooth optimization, k+1=(1−θk)k+θkk+θkk+1(−Σ)⏟Local aggregation with compression−ηk(k+Ξk+1)⏟descent step. Z_k+1= (1- _k) Z_k+ _k Z_k W+ _k E_k+1( W- )_Local aggregation with compression - _k( H_k+ _k+1)_descent step. (DESC) Here, k=[1,k,…,d,k]∈ℝm×d Z_k=[ z_1,k,…, z_d,k] ^m× d denotes the collection of local variables (including the local variables i,ki∈[d]\ x_i,k\_i∈[d] and auxiliary variables corresponding to specific subgradient methods), W is a mixing matrix, k∈ℝm×d H_k ^m× d represents the collection of noiseless update directions of all agents, and Σ is a diagonal matrix which conforms to the mechanism of communication compression. k+1\ E_k+1\ and Ξk+1\ _k+1\ are two sequences of random variables defined on probability space (Ω,ℱ,ℙ)( ,F,P), which correspond to the compression error and evaluation noise on k H_k, respectively. Furthermore, ηk\ _k\ and θk\ _k\ are two-timescale step-sizes corresponding to the descent step and the local average. Typically, they are required to satisfy ηk/θk→0 _k/ _k→ 0, as k goes infinity. In (DESC), the i-th term of k+k+1(−Σ) Z_k W+ E_k+1( W- ) can be interpreted as the weighted aggregation performed by agent i on the variables transmitted by its neighbors, which are perturbed by compression errors. Further, a θk _k-reallocation step together with a descent step is incorporated to produce the next iterate k+1 Z_k+1. The flexibility in choosing k+1 E_k+1 and k H_k allows this framework to encompass a wide range of decentralized methods with communication compression. Throughout this paper, we focus on two important sub-frameworks developed from (DESC) by choosing different k+1 E_k+1 and corresponding Σ . We first introduce the following sub-framework for developing decentralized stochastic subgradient-type methods with unbiased compression, k+1=(1−θk)k+θkk+θkk+1(−Diag())−ηk(k+Ξk+1),k+1=C(k,k+1)−k:=[C(1,k,k+1)−1,k,…,C(d,k,k+1)−d,k]. \ aligned Z_k+1&=(1- _k) Z_k+ _k Z_k W+ _k E_k+1( W-Diag( W))- _k( H_k+ _k+1),\\ E_k+1&=C( Z_k, ω_k+1)- Z_k:=[C( z_1,k, ω_k+1)- z_1,k,…,C( z_d,k, ω_k+1)- z_d,k].\\ aligned . (DESC-Unb) Here, C(⋅,):ℝm×Ω→ℝmC(·, ω):R^m× ^m is an unbiased compression operator, i.e. [C(,)]=E_ ω[C( x, ω)]= x. k+1\ E_k+1\ is a martingale difference sequence with respect to ℱk=σ(i:i≤k)F_k=σ(\ Z_i:i≤ k\). As shown later in Section 4, with specific choices of k H_k, (DESC-Unb) yields variants of several decentralized stochastic subgradient-type methods with unbiased compression. For instance, as we set k=k Z_k= X_k, k+Ξk+1∈[DF1(⋅,ζi,k+1)(i,k),…, H_k+ _k+1∈[D_F_1(·, _i,k+1)( x_i,k),…, DFd(⋅,ζi,k+1)(i,k)]D_F_d(·, _i,k+1)( x_i,k)], and C to be a randomized quantization operator Q, (DESC-Unb) reduces exactly to the nonsmooth version of QDGD [51], a decentralized SGD method with quantization: i,k+1∈(1−θk+θk(i,i))i,k+θk∑j∈i(i,j)Q(j,k,k+1)−ηkDFi(⋅,ζi,k+1)(i,k), x_i,k+1∈(1- _k+ _k W(i,i)) x_i,k+ _k _j _i W(i,j)Q( x_j,k, ω_k+1)- _kD_F_i(·, _i,k+1)( x_i,k), (QDGD+) where iN_i denotes the neighbors of agent i, DFi(⋅,ζi,k+1)D_F_i(·, _i,k+1) is a conservative field for function Fi(⋅,ζi,k+1)F_i(·, _i,k+1) that describes how Fi(⋅,ζi,k+1)F_i(·, _i,k+1) is differentiated. Additionally, based on (DESC), we introduce another sub-framework for contractive compression, k+1=(1−θk)k+θkk+θkk+1(−d)−ηk(k+Ξk+1),k+1=^k+1−k,^k+1=^k+γkC(k−^k,k+1). \ aligned Z_k+1&=(1- _k) Z_k+ _k Z_k W+ _k E_k+1( W- I_d)- _k( H_k+ _k+1),\\ E_k+1&= Z_k+1- Z_k,\\ Z_k+1&= Z_k+ _kC( Z_k- Z_k, ω_k+1).\\ aligned . (DESC-Con) Here, C(⋅,):ℝm×Ω→ℝmC(·, ω):R^m× ^m is a contractive compression operator, i.e. [‖C(,)−‖2]≤(1−α)‖2,α∈(0,1].E_ ω[\|C( x, ω)- x\|^2]≤(1-α)\| x\|^2,α∈(0,1]. ^k+1=[^1,k+1,…,^d,k+1] Z_k+1=[ z_1,k+1,…, z_d,k+1] is the collection of local copies, where each ^i,k+1 z_i,k+1 is an inexact copy of i,k z_i,k held by the neighbors of agent i. γk\ _k\ is a diminishing sequence, and −k+1- E_k+1 is essentially an compression error term that captures the discrepancy between the desired difference k−^k Z_k- Z_k and the compressed term γkC(k−^k,k+1) _kC( Z_k- Z_k, ω_k+1). The update formula of k E_k and ^k Z_k can be further illustrated by the following error-compensation mechanism Δk=k−k−1+(−k),⊲ error-compensation^k+1=^k+γkC(Δk,k+1),⊲ compression and update−k+1=Δk−γkC(Δk,k+1).⊲ compression error \ aligned _k~&= Z_k- Z_k-1+(- E_k), 76.82234pt error-compensation\\ Z_k+1~&= Z_k+ _kC( _k, ω_k+1), 77.39153pt compression and update\\ - E_k+1~&= _k- _kC( _k, ω_k+1). 77.9607pt compression error\\ aligned . Similarly, as demonstrated in Section 4, with different choices of k H_k, (DESC-Con) corresponds to various decentralized stochastic subgradient-type methods with contractive compression. For instance, when we choose k=k Z_k= X_k, k+Ξk+1∈[DF1(⋅,ζi,k+1)(i,k),…,DFd(⋅,ζi,k+1)(i,k)] H_k+ _k+1∈[D_F_1(·, _i,k+1)( x_i,k),…,D_F_d(·, _i,k+1)( x_i,k)], (DESC-Con) is a nonsmooth version of CHOCO-SGD [31, 32]: ^j,k+1=^j,k+γkC(j,k−^j,k,k+1),j∈i,i,k+1∈i,k+θk∑j∈i(i,j)(^j,k+1−^i,k+1)−ηkDFi(⋅,ζi,k+1)(i,k). \ aligned x_j,k+1&= x_j,k+ _kC( x_j,k- x_j,k, ω_k+1), j _i,\\ x_i,k+1&∈ x_i,k+ _k _j _i W(i,j)( x_j,k+1- x_i,k+1)- _kD_F_i(·, _i,k+1)( x_i,k).\\ aligned . (CHOCO-SGD+) 1.2 Contributions The main contributions of our paper are three-fold. • Unification Our framework (DESC) provides a unified decentralized update scheme with compression, which covers two mainstream compression approaches: unbiased compression and contractive compression with error compensation. Moreover, the proposed framework (DESC) incorporates vanilla stochastic subgradient descent (SGD) along with various SGD-based acceleration techniques, including momentum and gradient-tracking, into the update scheme. In particular, we show that the nonsmooth extensions of common decentralized stochastic gradient-type methods with communication compression fit into our framework, such as QDGD [51], CHOCO-SGD [32], BEER [72] and C-GT [38]. • Convergence We establish the global convergence of (DESC) by connecting the consensus-error iterates and averaged iterates to the trajectories of the delicately constructed noiseless differential inclusions. To the best of our knowledge, this is the first work that rigorously proves global convergence to critical points for a wide range of existing decentralized compression-based methods in nonsmooth nonconvex optimization, especially in the training of nonsmooth neural networks. • Development Based on our (DESC), we develop decentralized compression-based variants of momentum SGD and SignSGD with theoretical guarantees. Preliminary numerical experiments demonstrate the efficiency of these methods and highlight the potential of our framework for designing decentralized stochastic subgradient-type methods with communication compression. 1.3 Organization The rest of this paper is organized as follows. Section 2 introduces the notations and preliminary concepts used throughout the paper. Section 3 presents our proposed framework, provides a detailed consensus analysis, and establishes its global convergence. Section 4 demonstrates that our framework covers nonsmooth extensions of existing methods and enables the development of new methods with convergence guarantees. Section 5 exhibits the results of preliminary numerical experiments. In the last section, we draw conclusions and discuss possible future research directions. 2 Preliminary 2.1 Notations The operator ⟨⋅,⋅⟩ ·,· represents the standard inner product, while ∥⋅∥\|·\| represents the ℓ2 _2-norm of a vector or the spectral norm of a matrix. ∥⋅∥1\|·\|_1 stands for the ℓ1 _1-norm of a vector, and ∥⋅∥F\|·\|_F refers to the Frobenius norm of a matrix. Let (,δ):=~∈ℝn:‖~−‖2≤δ2B( x,δ):= \ x ^n:\| x- x\|^2≤δ^2 \ denote the ball centered at x with radius δ. For a given set ,dist(,):=miny∈‖−‖Y,dist( x,Y):= _y \| x- y\| represents the distance between x and a set Y. The convex hull and d-fold Cartesian product of Y is denoted by convconv\,Y and dY^d, respectively. The notation ⊗ stands for the Kronecker product. The symbol ⊙ denotes the Hadamard product, Δm:=(λ0,…,λm):λi≥0,∑i=0mλi=1 _m:=\( _0,…, _m): _i≥ 0, _i=0^m _i=1\ stands for the simplex of dimension m. For any positive sequence ηk \ _k \, let λη(0):=0,λη(i):=∑k=0i−1ηk _η(0):=0, _η(i):= _k=0^i-1 _k, and Λη(t):=supk∈ℕ: _η(t):= \k : . t≥λη(k). .t≥ _η(k) \. More explicitly, Λη(t)=p _η(t)=p, if λη(p)≤t<λη(p+1) _η(p)≤ t< _η(p+1). The set-valued mapping sign : ℝn⇉ℝnR^n ^n is defined by (sign())i=−1,i<0;[−1,1],i=0;1,i>0.(sign( x))_i= cases\-1\,& x_i<0;\\ [-1,1],& x_i=0;\\ \1\,& x_i>0. cases For any N>0,N>0, let [N]:=1,…,N[N]:=\1,…,N\. The notation ℝ+R_+ represents the set of all nonnegative real numbers. Notations d 1_d and i e_i stand for a vector of all 11’s and [0,…,1,…,0]⊤[0,…,1,…,0] , where 11 is the i-th component. For two integers i and j, i∧j:=mini,ji j:= \i,j\. Let (Ω,ℱ,ℙ)( ,F,P) denote the probability space. We use σ()σ( X) to denote the sigma-algebra generated by the random variable X. We say that ℱkk∈ℕ \F_k \_k is a filtration if ℱk \F_k \ is a collection of σ-algebras satisfying ℱ0⊆ℱ1⊆⋯⊆ℱ∞⊆ℱF_0 _1 ·s _∞ . A sequence of random variables ξk\ _k\ is a martingale with respect to a filtration ℱk\F_k\, if ξk\ _k\ is adapted to the filtration ℱk\F_k\ and [ξk+1|ℱk]=ξkE[ _k+1|F_k]= _k, for all k∈ℕk ; ξk\ _k\ is a supermartingale with respect to ℱkF_k, if ξk _k is adapted to ℱk\F_k\ and [ξk+1|ℱk]≤ξkE[ _k+1|F_k]≤ _k, for all k∈ℕk . Moreover, a sequence of random variables ξk\ _k\ is a martingale difference sequence with respect to ℱk\F_k\, if ξk\ _k\ is adapted to the filtration ℱk\F_k\ and [ξk+1|ℱk]=0E[ _k+1|F_k]=0 holds for all k∈ℕk . In addition, we denote the set of agent i’s neighbors by iN_i, and i+:=i∪iN_i^+:=N_i∪\i\. We define the summation function f of (DOP) as f():=1d∑i=1dfi().f( x):= 1d _i=1^df_i( x). (2.1) 2.2 Mixing matrix The mixing matrix W conforms to the topology of the communication network and plays an important role in aggregating local information from neighboring agents. Generally, we assume the mixing matrix W is defined to satisfy the following properties, which are standard in the literature. Definition 2.1. [34, Section 1] Given a connected graph =(,) G=( V, E), we say ∈ℝd×d W ^d× d is a mixing matrix of G, if it satisfies 1. W is symmetric. 2. W is doubly stochastic, namely, W is nonnegative and d=⊤d=d W 1_d= W 1_d= 1_d. 3. (i,j)=0 W(i,j)=0, if and only if i≠ji≠ j and (i,j)∉(i,j)∉ E. Given a graph G, various approaches can be used to select its corresponding mixing matrix, such as the Laplacian-based constant edge-weight matrix [63] and the Metropolis constant edge-weight matrix [64]. For further details on choosing the mixing matrix, we refer the reader to [44, 55]. Proposition 2.2 is a direct corollary of [47, Perron-Frobenius Theorem], which characterize the spectral property of a mixing matrix W. Proposition 2.2. For any mixing matrix ∈ℝd×d W ^d× d associated with a connected graph G, all eigenvalues of W lie in (−1,1](-1,1], and W has a single eigenvalue equal to 11 with the all-ones vector d 1_d as its right eigenvector. 2.3 Set-valued mapping, Clarke subdifferential and conservative field A set-valued mapping Φ:ℝn⇉ℝm :R^n ^m is a mapping from ℝnR^n into the set of subsets of ℝmR^m. The graph of Φ is defined by graphΦ=(,)∣∈ℝn,∈Φ().graph =\( x, z) x ^n, z∈ ( x)\. Φ is said to have a closed graph (or be graph-closed), if graphΦgraph is a closed subset of ℝn×ℝmR^n×R^m. It is locally bounded, if for any ∈ℝn x ^n, there exists a neighborhood U_ x of x such that sup∈Φ(),∈U‖<+∞. _ z∈ ( y), y∈ U_ x\| z\|<+∞. In addition, Φ is convex-valued (resp. compact-valued), if Φ() ( x) is a convex (resp. compact) subset of ℝmR^m for any ∈ℝn x ^n. For δ>0δ>0, we define Φδ():=⋃∈(,δ)(Φ()+(,δ)) ^δ( x):= _ y ( x,δ)( ( y)+B( 0,δ)) where “+” denotes the Minkowski sum. Definition 2.3 (Clarke subdifferential [18]). For any given locally Lipschitz continuous function f:ℝn→ℝf:R^n , and for any ∈ℝn x ^n, the generalized directional derivative of f at x along the direction ∈ℝn d ^n is defined by f∘(;):=lim sup→,t↓0f(+t)−f()t.f ( x; d):= _ y→ x,t 0 f( y+t d)-f( y)t. The Clarke subdifferential of f at ∈ℝn x ^n, denoted by ∂f()∂ f( x), is given by ∂f():=∈ℝn:f∘(;)≥⟨,⟩,∀∈ℝn.∂ f( x):= \ u ^n:f ( x; d)≥ u, d ,∀ d ^n \. Notice that ∂f∂ f is a set-valued mapping that is convex-valued, graph-closed, and locally bounded. Based on the concept of generalized directional derivative, we now present the definition of Clarke regular functions. Definition 2.4 (Clarke regular [18]). We say that f is Clarke regular at ∈ℝn x ^n, if for every direction ∈ℝn d ^n, the one-sided directional derivative f∗(;):=limt↓0f(+t)−f()tf^*( x; d):= _t 0 f( x+t d)-f( x)t exists, and equals the generalized directional derivative, i.e. f∗(;)=f∘(;).f^*( x; d)=f ( x; d). Next, we present a brief introduction to concept of a conservative field, which is used to describe the output of the AD algorithm applied to nonsmooth neural networks. Definition 2.5 (Conservative field [11]). Let D:ℝn⇉ℝnD:R^n ^n be a nonempty set-valued mapping. We say that D is a conservative field if it is compact-valued and graph-closed, and for any absolutely continuous loop γ:[0,1]→ℝnγ:[0,1] ^n satisfying γ(0)=γ(1)γ(0)=γ(1), it holds that ∫01max∈D(γ(t))⟨γ˙(t),⟩dt=0. _0^1 _ v∈ D(γ(t)) γ(t), v =0. (2.2) It is worth noting that any conservative field is locally bounded [11, Remark 3]. We now introduce the definition of the path-differentiable function corresponding to a conservative field. Definition 2.6 (Path-differentiable). Let D:ℝn⇉ℝnD:R^n ^n be a conservative field. A function f is said to be path-differentiable for D if there exists 0∈ℝn x_0 ^n such that f()=f(0)+∫0t⟨γ˙(s),v(s)⟩ds,f( x)=f( x_0)+ _0^t γ(s),v(s) , for any absolutely continuous curve γ with γ(0)=0γ(0)= x_0 and γ(t)=γ(t)= x and some measurable selection v(s)∈D(γ(s))v(s)∈ D(γ(s)). We also say that D is a conservative field for f, denoted by DfD_f. Proposition 2.7 (Corollary 1 of [11]). Let Df:ℝn⇉ℝnD_f:R^n ^n be a conservative field for a path-differentiable function f:ℝn→ℝf:R^n . Then Df()=∇f()D_f( x)=\∇ f( x)\ for almost every ∈ℝn x ^n. Furthermore, ∂f∂ f is a conservative field for f, and ∂f()⊆conv(Df())∂ f( x) \,(D_f( x)) holds for all ∈ℝn x ^n. Proposition 2.7 reveals that ∂f∂ f is the smallest convex-valued conservative field for f. Therefore, the concept of a conservative field can be regarded as an extension of the Clarke subdifferential. More importantly, when the conservative field Df()D_f( x) is convex-valued, the condition ∈∂f() 0∈∂ f( x) implies that 0∈Df()0∈ D_f( x). Remark 2.8. The class of path-differentiable functions is general enough to encompass most objective functions encountered in real-world problems. Notably, the well-known Clarke regular functions [17] and semi-algebraic functions [75] are both path-differentiable. As discussed in [19], an important subclass of path-differentiable functions is the class of definable functions, namely, functions whose graphs are definable in an o-minimal structure. In fact, most activation and loss functions used in deep neural networks are definable, including sigmoid, softplus, ReLU, leaky ReLU, hinge loss, and others. Owing to the invariance of definability under finite summation and composition [19], any neural network built from definable blocks has a definable loss function and a definable conservative field, thereby making its loss function path-differentiable. The following proposition shows that the definability of both f and its conservative field DfD_f implies the nonsmooth Morse–Sard property [9]. Proposition 2.9 (Theorem 5 of [11]). Let f be a path-differentiable function that admits DfD_f as its conservative field. Suppose that both f and DfD_f are definable over ℝnR^n. Then the set f():∈Df() \f( x): 0∈ D_f( x) \ is finite. Finally, based on the concept of a conservative field, we introduce the definition of critical points for the optimization problem (DOP). Definition 2.10. Let f in (2.1) be a path-differentiable function that admits DfD_f as its convex-valued conservative field. A point ∈ℝn×d X ^n× d is said to be a DfD_f-critical point of (DOP) if it satisfies the consensus condition =1ddd⊤ X= 1d X 1_d 1_d and ∈Df(1dd). 0∈ D_f( 1d X 1_d). Similarly, ∈ℝn×d X ^n× d is called a Clarke-critical (or ∂f∂ f-critical) point of (DOP), if it satisfies the same consensus condition =1ddd⊤ X= 1d X 1_d 1_d and ∈∂f(1dd). 0∈∂ f( 1d X 1_d). 2.4 Stochastic approximation and differential inclusion ODE approaches [4, 13, 22, 19] are powerful tools for analyzing convergence in stochastic approximation, particularly for the iterates of stochastic subgradient-type methods. These approaches characterize the convergence of the iterates via the asymptotic behavior of the dynamics of the associated differential inclusion. We first recall some basic definitions related to differential inclusions. Definition 2.11. Let Φ:ℝn⇉ℝn :R^n ^n be a set-valued mapping. An absolutely continuous curve γ:ℝ+→ℝnγ:R_+ ^n is called a solution (or trajectory) of the differential inclusion ˙(t)∈Φ(), x(t)∈ ( x), (2.3) with initial condition γ(0)=0γ(0)= x_0, if γ′(t)∈Φ(γ(t))γ (t)∈ (γ(t)) for almost all t∈ℝ+t _+. Definition 2.12 (Lyapunov function). Let ℬ⊂ℝnB ^n be a closed set. A continuous function ψ:ℝn→ℝψ:R^n is said to be a Lyapunov function for the differential inclusion (2.3) with a stable set ℬB, if for any solution γ to (2.3) and any t>0t>0, it holds that ψ(γ(t))≤ψ(γ(0)).ψ(γ(t))≤ψ(γ(0)). Moreover, for γ(0)∉ℬγ(0) , it holds for all t>0t>0 that ψ(γ(t))<ψ(γ(0)).ψ(γ(t))<ψ(γ(0)). Consider iterates k\ x_k\ generated by the following update scheme: k+1∈k−cηk(Φδk(k)+υk+1), x_k+1∈ x_k-c _k ( _k( x_k)+ _k+1 ), (2.4) where ηk\ _k\ is a non-summable positive sequence of step-sizes, δk\ _k\ is a nonnegative sequence, and υk+1 _k+1 is a random noise term added when evaluating Φ(k) ( x_k). The continuous-time interpolated process u:ℝ+→ℝnu:R_+ ^n induced by (2.4) is given by u(λη(k)+s)=k+k+1−kηks,s∈[0,ηk).u( _η(k)+s)= x_k+ x_k+1- x_k _ks, s∈[0, _k). where λη(0):=0 _η(0):=0 and λη(k):=∑i=0k−1ηi _η(k):= _i=0^k-1 _i, for k≥1k≥ 1. The following Lemma 2.14 plays an important role in demonstrating the convergence properties of (2.4), integrating results from [65, Lemma 2.20], [4, Theorem 3.6, Proposition 3.27]. In their proof, they show that the interpolated process above is a perturbed solution of differential inclusion (2.3). For further details, interested readers are referred to [3] and [4]. Assumption 2.13. 1. The sequence k\ x_k\ is uniformly bounded, and limk→∞δk=0 _k→∞ _k=0. 2. There exists a locally Lipschitz continuous Lyapunov function ψ:ℝn→ℝψ:R^n for the differential inclusion ddt∈−Φ(), d xdt∈- ( x), (2.5) with a stable set ℬB. Moreover, the set ψ():∈ℬ\ψ( x): x \ is a finite subset of ℝR. 3. For any T>0T>0, it holds that lims→+∞sups≤i≤Λη(λη(s)+T)‖∑k=siηkυk+1‖=0. _s→+∞ _s≤ i≤ _η( _η(s)+T) \| _k=s^i _k _k+1 \|=0. Lemma 2.14. Suppose Assumption 2.13 holds. Let 0X_0 be a compact subset of ℝnR^n, and let the sequence xk\x_k\ be generated by the update scheme (2.4) with x0∈0x_0∈X_0. Then it follows that limk→∞dist(xk,ℬ)=0, _k→∞dist (x_k,B )=0, and the sequence ψ(k)\ψ( x_k)\ converges to ψ(∗)ψ( x^*), where ∗∈ℬ x^* . 3 Convergence Guarantees for General Framework In this section, we establish the global asymptotic convergence properties for (DESC). Section 3.1 discuss about the relationship between k Z_k and k H_k in the framework (DESC), and introduces basic assumptions for (DESC). Section 3.2 relates the consensus-error iterates to the trajectories of a noiseless continuous-time differential inclusion, and demonstrates the consensus properties of two sub-frameworks. In Section 3.3, we connects the averaged iterates to another continuous-time differential inclusion, and establish the global convergence to the stable set of corresponding differential inclusion. 3.1 Basic assumptions In the nonsmooth setting, a common choice for noiseless update directions k H_k is k∈[Φ1(1,k),…,Φd(d,k)], H_k∈[ _1( z_1,k),…, _d( z_d,k)], where each Φi _i is a set-valued mapping, such as the Clarke subdifferential ∂fi∂ f_i or a conservative field DfiD_f_i discussed in Section 2.3. This choice naturally yields a stochastic subgradient descent method with communication compression. To encompass a broader class of subgradient-type methods, we introduce a family of set-valued mappings Φi()i=1d\ _i( z)\_i=1^d that possess a “Lyapunov property” to constrain k H_k. Furthermore, we specify the form of the evaluation noise Ξk+1 _k+1 and the step-sizes used in framework (DESC). Assumption 3.1. (1) There exists a sequence ϵk⊆ℝ+\ _k\ _+ and a family of locally bounded and graph-closed set-valued mappings Φi,i∈[d] _i,i∈[d] such that 1dkd∈conv(1d∑i=1dΦiϵk(i,k)),∀k∈ℕ. 1d H_k 1_d \, ( 1d _i=1^d _i _k( z_i,k) ), ∀ k . (3.1) Moreover, k\ H_k\ is bounded and ϵk\ _k\ is diminishing whenever k\ Z_k\ is bounded. (2) The differential inclusion ddt∈−Φ():=−conv(1d∑i=1dΦi()), d zdt∈- ( z):=-conv\, ( 1d _i=1^d _i( z) ), (3.2) admits a locally Lipschitz continuous Lyapunov function ψ:ℝm→ℝψ:R^m , whose stable set is denoted by A, and ψ():∈\ψ( z): z \ is a finite subset of ℝR. (3) The evaluation noise Ξk+1\ _k+1\ is a martingale difference sequence, and it is uniformly bounded whenever k\ Z_k\ is bounded. (4) The sequences of step-sizes ηk\ _k\ and θk\ _k\ satisfy the following conditions: ∑i=0∞ηk=+∞,limk→+∞ηkθk=0,limk→+∞θklog(k)=0,limk→+∞θk2ηklog(k)=0. _i=0^∞ _k=+∞, _k→+∞ _k _k=0, _k→+∞ _k (k)=0, _k→+∞ _k^2 _k (k)=0. (3.3) Moreover, the sequence γk\ _k\ satisfies γ0=1,limk→∞γklog(k)=0,limk→∞θkγk=0. _0=1, _k→∞ _k (k)=0, _k→∞ _k _k=0. (3.4) Assumption 3.1-(1) uses a family of set-valued mappings Φi\ _i\ to characterize the relationship between the averaged update direction 1dkd 1d H_k 1_d and local variables i,ki∈[d]\ z_i,k\_i∈[d]. Note that we do not require each column of k H_k to belong to Φi(i,k) _i( z_i,k), but instead merely restrict the averaged update direction to lie in the convex hull of the Minkowski sum of ϵk _k-neighborhoods of the set-valued mapping’s images. This yields a very general assumption, which enables the development of decentralized SGD-type methods within our framework. Assumption 3.1-(2) is frequently employed in the literature, e.g., [4, 14, 8, 19, 11, 29]. It captures the descent property of ψ along trajectories of the differential inclusion (3.2), while the property that ψ():∈\ψ( z): z \ is finite corresponds to the weak Sard property in [19, Assumption B], which holds when f is a definable function under the selection Φ:=∂f :=∂ f and ψ:=fψ:=f. Assumption 3.1-(3) and (4) impose mild technical conditions on the evaluation noise Ξk+1\ _k+1\, and allow for a flexible choice of three-timescale step-sizes ηk,θk,γk\ _k, _k, _k\. One simple choice is ηk=o(1/logk) _k=o(1/ k), θk=ηk(ηklog(k))−s, _k= _k( _k (k))^-s, γk=ηk(ηklog(k))−3s/2 _k= _k( _k (k))^-3s/2 with s∈(0,12)s∈(0, 12). In the following, we stipulate the standing assumptions on unbiased compression and contractive compression, and present several typical examples. Assumption 3.2 (Unbiased compression operator). For a compression operator C(⋅,⋅):ℝm×Ω→ℝmC(·,·):R^m× ^m, we assume that C is unbiased and satisfies a linear growth bound, that is, there exists a constant β>0β>0 such that [C(,)]=,‖C(,)‖≤β‖,∀∈ℝm,a.s. in Ω.E_ ω[C( x, ω)]= x, \|C( x, ω)\|≤β\| x\|, ∀ x ^m,\ a.s. in . (3.5) Example 3.3 (Random quantization [1]). For any ∈ℝm x ^m and precision level s∈ℕ+s _+, the random quantization operator QsQ_s, which is an unbiased compression operator, is defined as Qs():=‖2sign()⊙ζ(,s),Q_s( x):=\| x\|_2sign( x) ζ( x,s), where ζ(,s)=[ζ1(x1,s),…,ζm(xm,s)]⊤,ζi(xi,s)=l+1s, with probability s|xi|‖−l,ls, otherwise,ζ( x,s)=[ _1(x_1,s),…, _m(x_m,s)] , _i(x_i,s)= cases l+1s,& with probability s|x_i|\| x\|-l,\\ ls,& otherwise,\\ cases for some integer l satisfying ls≤|xi|‖<l+1s ls≤ |x_i|\| x\|< l+1s. Assumption 3.4 (Contractive compression operator). For a compression operator C(⋅,⋅):ℝm×Ω→ℝmC(·,·):R^m× ^m, we assume there exists α∈(0,1]α∈(0,1] such that [‖C(,)−‖2]≤(1−α)‖2,∀∈ℝm.E_ ω[\|C( x, ω)- x\|^2]≤(1-α)\| x\|^2, ∀ x ^m. (3.6) Assumption 3.4 is a mild condition, which requires the deviation ‖C(,)−‖2\|C( x, ω)- x\|^2 to be proportional to the squared norm of x. Indeed, this assumption has been widely adopted in the literature [26, 58, 52]. Example 3.5. 1. Random-k compression operator: (C(,))i:=i, if i∈ω,0, otherwise, (C( x, ω) )_i:= \ array[]l x_i,& if i∈ω,\\ 0,& otherwise, array . where ∈ℝm x ^m and ω⊆[m]ω [m] is a random subset with |ω|=k|ω|=k. This operator satisfies Assumption 3.4 with α=kmα= km. 2. Top-k compression operator (C(,))i:=iπ(i)≤k, if i≤k,0, otherwise, (C( x, ω) )_i:= \ array[]l x_i 1_π(i)≤ k,& if i≤ k,\\ 0,& otherwise, array . where ∈ℝm x ^m and π is a permutation of [m][m] such that π(i)π(i) denotes the position of |i|| x_i| in the ordering of |j|j=1m\| x_j|\_j=1^m. This operator satisfies Assumption 3.4 with α=kmα= km. 3.2 Consensus analysis In this subsection, we investigate the consensus property of the framework (DESC). With the notations :=1ddd⊤ P:= 1d 1_d 1_d and ⟂:=d− P_ := I_d- P, k∈ℝm×d Z_k ^m× d admits the following orthogonal decomposition, k=k+k⟂. Z_k= Z_k P+ Z_k P_ . Here, ⟂,k:=k⟂ Z_ ,k:= Z_k P_ measures the dissimilarity of the local variables across all agents at the k-th iteration, which is referred to as the consensus-error sequence. Assumption 3.6. The sequence k\ Z_k\ in (DESC) is bounded. Assumption 3.6 is a standard global stability condition in ODE-based analyses of nonsmooth optimization, and has been widely adopted in the literature [4, 3, 11, 19, 15]). In practice, it is also considered as a mild condition. Proposition 3.7 (Consensus: unbiased compression). Suppose Assumption 3.1, 3.2 and 3.6 hold. For any sequence k\ Z_k\ generated by (DESC-Unb), it satisfies limk→+∞‖⟂,k‖=0. _k→+∞ \| Z_ ,k \|=0. Proof. By straightforward algebraic calculations, we have ⟂,k+1 Z_ ,k+1 =[k((1−θk)d+θk)]⟂+θkk+1(−Diag())⟂−ηk(k+Ξk+1)⟂ =[ Z_k((1- _k) I_d+ _k W)] P_ + _k E_k+1( W-Diag( W)) P_ - _k( H_k+ _k+1) P_ (3.7) =⟂,k((1−θk)d+θk)+θkk+1(−Diag())⟂−ηk(k+Ξk+1)⟂ = Z_ ,k((1- _k) I_d+ _k W)+ _k E_k+1( W-Diag( W)) P_ - _k( H_k+ _k+1) P_ =⟂,k−θk[⟂,k(d−)+ηkθkk⟂]+θk[k+1(−Diag())⟂−ηkθkΞk+1⟂], = Z_ ,k- _k[ Z_ ,k( I_d- W)+ _k _k H_k P_ ]+ _k[ E_k+1( W-Diag( W)) P_ - _k _k _k+1 P_ ], where the second equality follows from ⟂((1−θk)d+θk)=((1−θk)d+θk)⟂. P_ ((1- _k) I_d+ _k W)=((1- _k) I_d+ _k W) P_ . Let Φ():=(d−) ( Z):= Z( I_d- W), υk+1:=k+1(−Diag())⟂−ηkθkΞk+1⟂ _k+1:= E_k+1( W-Diag( W)) P_ - _k _k _k+1 P_ and δk:=ηkθk‖k⟂‖ _k:= _k _k\| H_k P_ \|. Then (3.7) can be rephrased as ⟂,k+1∈⟂,k−θk(Φδk(⟂,k)+υk+1). Z_ ,k+1∈ Z_ ,k- _k( _k( Z_ ,k)+ _k+1). (3.8) By Assumption 3.6 and 3.1, k\ H_k\ is uniformly bounded and limk→∞ηkθk=0 _k→∞ _k _k=0, which implies that δk\ _k\ diminishes to 0. Let ψ():=12‖(d−)12‖F2ψ( Z):= 12\| Z( I_d- W) 12\|_F^2 and ℬ:=|(d−)=0B:=\ Z| Z( I_d- W)=0\. For any solution (t) Z(t) to the differential inclusion ddt∈−Φ() d Zdt∈- ( Z), it holds that dψ((t))dt=⟨∂ψ()∂,d(t)dt⟩=⟨(t)(d−),−(t)(d−)⟩≤0. dψ( Z(t))dt= ∂ψ( Z)∂ Z, d Z(t)dt = Z(t)( I_d- W),- Z(t)( I_d- W) ≤ 0. When (0)∉ℬ Z(0) , it holds that dψ((t))dt|t=0<0 dψ( Z(t))dt|_t=0<0. Hence, ψ()ψ( Z) is a Lyapunov function of ddt∈−Φ() d Zdt∈- ( Z) and ℬB is a stable set. Moreover, ψ()ψ( Z) is coercive and locally Lipschitz continuous, and ψ():∈ℬ=0\ψ( x): x \=\0\, which verifies Assumption 2.13-(2). In addition, one can check that [υk+1|ℱk]=[k+1(−Diag())⟂−ηkθkΞk+1⟂∣ℱk]=0.E[ _k+1|F_k]=E [ E_k+1( W-Diag( W)) P_ - _k _k _k+1 P_ _k ]=0. and υk+1\ _k+1\ is uniformly bounded, which follows from the definition of k+1 E_k+1 and Assumption 3.1-(4). According to [3, Proposition 4.4], a uniformly bounded martingale difference sequence υk+1\ _k+1\ together with θk\ _k\ of order o(1/log(k))o(1/ (k)) is a special case of Assumption 2.13-(3). By applying Lemma 2.14, we can conclude that the sequence ‖⟂,k(d−)12‖\\| Z_ ,k( I_d- W) 12\|\ converges to ψ()|∈ℬ=0ψ( Z)|_ Z =0. This implies that ⟂,k\ Z_ ,k\ converges to the consensus space |=d⊤,∈ℝm\ Z| Z= z 1_d , z ^m\. By the definition of ⟂,k\ Z_ ,k\, we further achieve that limk→+∞‖⟂,k‖=0 _k→+∞ \| Z_ ,k \|=0, which completes the proof. ∎ Proposition 3.7 describe the consensus property of the sub-framework (DESC-Unb). To reveal the analogous properties in sub-framework (DESC-Con), we introduce some useful Lemmas 3.8-3.10, whose proof is shown in Appendix 6.1 and 6.2. Lemma 3.8. Suppose that positive sequences γk\ _k\ and θk\ _k\ satisfy limk→+∞γklog(k)=0,limk→+∞θkγk=0,∑k=1∞θk=+∞. _k→+∞ _k (k)=0, _k→+∞ _k _k=0, _k=1^∞ _k=+∞. Then, for any a∈(0,1]a∈(0,1], we have limk→+∞∑i=1k(∏j=ik(1−aγj))C0θi−1=0. _k→+∞ _i=1^k ( _j=i^k(1-a _j) )C_0 _i-1=0. Lemma 3.9. Let υk\ _k\ be a scalar martingale difference sequence with respect to the filtration ℱk\F_k\, which is uniformly bounded. Let a∈(0,1]a∈(0,1], and γk\ _k\ be a sequence satisfying limk→+∞γklog(k)=0,∑k=1∞γk=+∞. _k→+∞ _k (k)=0, _k=1^∞ _k=+∞. Then it follows that limk→+∞(γkυk+1+∑i=1k−1γi(∏j=i+1k(1−aγj))υi+1)=0. _k→+∞ ( _k _k+1+ _i=1^k-1 _i ( _j=i+1^k(1-a _j) ) _i+1 )=0. Utilizing above tools, the following lemma shows that the compression error k E_k is bounded and converges to zero almost surely. Lemma 3.10. Suppose Assumption 3.1, 3.4 and 3.6 hold. For any k\ Z_k\ generated by (DESC-Con), it follows that almost surely, limk→+∞‖k‖=0. _k→+∞\| E_k\|=0. Proof. We first observe that k+1 E_k+1 in (DESC-Con) can be rewritten as k+1=γk(C(k−^k,k+1)−(k−^k))−(1−γk)(k−^k). E_k+1= _k(C( Z_k- Z_k, ω_k+1)-( Z_k- Z_k))-(1- _k)( Z_k- Z_k). Let k+1:=C(k−^k,k+1)−(k−^k) S_k+1:=C( Z_k- Z_k, ω_k+1)-( Z_k- Z_k), and ℱk:=σ(j,j,Ξj|j≤k)F_k:=σ(\ ω_j, Z_j, _j|j≤ k\) denote the σ-algebra at the k-th iteration. Straightforward calculations yield (‖k+1‖|ℱk) (\| E_k+1\||F_k) ≤ ≤ γk[‖k+1‖|ℱk]+(1−γk)‖k−^k‖ _kE[\| S_k+1\||F_k]+(1- _k)\| Z_k- Z_k\| ≤ ≤ γk1−α‖k−^k‖+(1−γk)‖k−^k‖ _k 1-α\| Z_k- Z_k\|+(1- _k)\| Z_k- Z_k\| ≤ ≤ (1−(1−1−α)γk)‖k(θk−1−(θk−1+1)d)+θk−1(k−1(−d)−ηk−1θk−1(k−1+Ξk))‖ (1-(1- 1-α) _k)\| E_k( _k-1 W-( _k-1+1) I_d)+ _k-1( Z_k-1( W- I_d)- _k-1 _k-1( H_k-1+ _k))\| ≤ ≤ (1−(1−1−α)γk)(1+θk−1−λdθk−1)‖k‖+(1−(1−1−α)γk)C0θk−1 (1-(1- 1-α) _k)(1+ _k-1- _d _k-1)\| E_k\|+(1-(1- 1-α) _k)C_0 _k-1 where the second inequality follows from Jensen’s inequality and the definition of a contractive compression operator, C0:=supk≥0‖k−1(−d)−ηk−1θk−1(k−1+Ξk)‖<+∞C_0:= _k≥ 0\| Z_k-1( W- I_d)- _k-1 _k-1( H_k-1+ _k)\|<+∞ as Assumption 3.6 holds, and λd _d is the smallest eigenvalue of W. In addition, one has (1−(1−1−α)γk)(1+θk−1−λdθk−1)=1−μkγk(1-(1- 1-α) _k)(1+ _k-1- _d _k-1)=1- _k _k where μk:=(1−1−α)−θk−1γk(1−λd)−(1−1−α)(1−λd)θk−1>0 _k:=(1- 1-α)- _k-1 _k(1- _d)-(1- 1-α)(1- _d) _k-1>0 as k is sufficiently large. Combining Lemma 3.8 and [53, Theorem 1], we know limk→∞‖k‖ _k→∞\| E_k\| exists and hence k\ E_k\ is bounded almost surely. This result also yields that k Z_k and k S_k is bounded almost surely. By carrying out the calculation further, we obtain ‖k+1‖ \| E_k+1\| ≤γk[‖k+1‖|ℱk]+γk(‖k+1‖−[‖k+1‖|ℱk])+(1−γk)‖k−^k‖ ≤ _kE[\| S_k+1\||F_k]+ _k(\| S_k+1\|-E[\| S_k+1\||F_k])+(1- _k)\| Z_k- Z_k\| (3.9) ≤(1−(1−1−α)γk)‖k‖+(1−(1−1−α)γk)C1θk−1+γk(‖k+1‖−[‖k+1‖|ℱk]) ≤(1-(1- 1-α) _k)\| E_k\|+(1-(1- 1-α) _k)C_1 _k-1+ _k(\| S_k+1\|-E[\| S_k+1\||F_k]) where C1:=supk≥0‖^k(−d)−ηk−1θk−1(k−1+Ξk)‖<+∞C_1:= _k≥ 0\| Z_k( W- I_d)- _k-1 _k-1( H_k-1+ _k)\|<+∞. With the notations υk:=‖k‖−[‖k‖|ℱk−1] _k:=\| S_k\|-E[\| S_k\||F_k-1] and a:=1−1−α∈(0,1)a:=1- 1-α∈(0,1), one can recursively iterate (3.9) to obtain ‖k+1‖≤∏i=1k(1−aγi)‖1‖+∑i=1k(∏j=ik(1−aγj))C1θi−1+∑i=1k−1(∏j=i+1k(1−aγj))γiυi+1+γkυk+1.\| E_k+1\|≤ _i=1^k(1-a _i)\| E_1\|+ _i=1^k ( _j=i^k(1-a _j) )C_1 _i-1+ _i=1^k-1 ( _j=i+1^k(1-a _j) ) _i _i+1+ _k _k+1. Since υk\ _k\ is a uniformly bounded martingale difference sequence under Assumption 3.6, and (γk,θk)(\ _k\,\ _k\) are two time-scale sequences of order o(1/log(k))o(1/ (k)), we can apply Lemmas 3.9 and 3.8 to derive limk→+∞γkυk+1+∑i=1k−1γi(∏j=i+1k(1−aγj))υi+1=0, _k→+∞ _k _k+1+ _i=1^k-1 _i ( _j=i+1^k(1-a _j) ) _i+1=0, and limk→+∞∑i=1k(∏j=ik(1−aγj))θi−1=0. _k→+∞ _i=1^k ( _j=i^k(1-a _j) ) _i-1=0. Together, these facts yield that limk→+∞‖k‖=0. _k→+∞\| E_k\|=0. This completes the proof. ∎ Proposition 3.11 (Consensus: contractive compression). Suppose Assumption 3.1, 3.4 and 3.6 hold. Then the sequence k\ Z_k\ generated by (DESC-Con) satisfies limk→+∞‖⟂,k‖=0. _k→+∞ \| Z_ ,k \|=0. Proof. To begin with, it is straightforward to check that ⟂,k+1 Z_ ,k+1 =[k((1−θk)d+θk)]⟂+θkk+1(−d)⟂−ηk(k+Ξk+1)⟂ =[ Z_k((1- _k) I_d+ _k W)] P_ + _k E_k+1( W- I_d) P_ - _k( H_k+ _k+1) P_ (3.10) =⟂,k((1−θk)d+θk)+θkk+1(−d)⟂−ηk(k+Ξk+1)⟂ = Z_ ,k((1- _k) I_d+ _k W)+ _k E_k+1( W- I_d) P_ - _k( H_k+ _k+1) P_ =⟂,k−θk[⟂,k(d−)+ηkθk(k+Ξk+1)⟂+k+1(−d)⟂]. = Z_ ,k- _k[ Z_ ,k( I_d- W)+ _k _k( H_k+ _k+1) P_ + E_k+1( W- I_d) P_ ]. Let Φ():=(d−) ( Z):= Z( I_d- W), υk:=0 _k:=0 and δk:=ηkθk(‖k‖+‖Ξk+1‖)+2‖k+1‖ _k:= _k _k(\| H_k\|+\| _k+1\|)+2\| E_k+1\|. Lemma 3.10 together with Assumption 3.1 implies limk→∞δk=0 _k→∞ _k=0. Then (3.10) can be rewritten as ⟂,k+1∈⟂,k−θk(Φδk(⟂,k)+υk+1), Z_ ,k+1∈ Z_ ,k- _k( _k( Z_ ,k)+ _k+1), (3.11) Let ψ():=12‖(d−)12‖F2ψ( Z):= 12\| Z( I_d- W) 12\|_F^2, and ℬ:=|(d−)=0B:=\ Z| Z( I_d- W)=0\. Analogously to the proof of Proposition 3.7, we can verify each condition in Assumption 2.13 holds and apply Lemma 2.14 to obtain desired result. ∎ 3.3 Global convergence and main results According to consensus properties shown in Propositions 3.7 and 3.11, we can deduce that the cluster points of the sequence k\ Z_k\ generated by (DESC-Unb) and (DESC-Con) coincide with those of the sequence kdd⊤d\ Z_k 1_d 1_d d\. As a result, we proceed to analyze the convergence properties of kd\ Z_k 1_dd\. Proposition 3.12 describes the relationship between 1dkd 1d Z_k 1_d and the averaged updated direction 1dkd 1d H_k 1_d via the set-valued mapping Φ . Proposition 3.12. Suppose Assumption 3.1 and 3.6 hold. For any sequence k\ Z_k\ generated by the sub-framework (DESC-Unb) or (DESC-Con), there exists a nonnegative diminishing sequence ϵ~k\ ε_k\ such that 1dkd∈Φϵ~k(1dkd). 1d H_k 1_d∈ ε_k( 1d Z_k 1_d). (3.12) Proof. Let ϵk⋆=‖⟂,k‖ε _k= \| Z_ ,k \|. From the definition of ⟂ P_ , it follows that ‖i,k−1dkd‖≤‖k⟂‖=ϵk⋆ \| z_i,k- 1d Z_k 1_d \|≤ \| Z_k P_ \|=ε _k. For brevity, denote k:=conv(1d∑i=1dΦiϵk+ϵk⋆(1dkd))C_k:=conv\,( 1d _i=1^d _i _k+ε _k( 1d Z_k 1_d)). According to Assumption 3.1(1), one attains that 1dkd∈conv(1d∑i=1dΦiϵk(i,k))⊆k. 1d H_k 1_d \, ( 1d _i=1^d _i _k( z_i,k) ) _k. (3.13) It remains to show that there exists a nonnegative diminishing sequence ϵ~k\ ε_k\ such that k⊆Φϵ~k(1dkd).C_k ε_k( 1d Z_k 1_d). (3.14) We proceed by contradiction. Suppose there exists δε>0 _ >0 and a subsequence kj⊂ℕ+\k_j\ _+ such that supdist(,Φδε(1dkjd)):∈kj>0. \dist ( y, _ ( 1d Z_k_j 1_d) ): y _k_j \>0. (3.15) Since k\ Z_k\ is uniformly bounded, without loss of generality, assume that kj\ Z_k_j\ converges to some ~∈ℝn×d Z ^n× d. By the closedness of the graph and the local boundedness of Φi _i, we obtain limj→+∞supdist(,Φi(~d)):∈Φiϵkj+ϵkj⋆(kjd)=0. _j→+∞ \dist ( y, _i( Z 1_dd) ): y∈ _i _k_j+ε _k_j( Z_k_j 1_dd) \=0. Based on Jensen’s inequality, it follows that limj→+∞supdist(,Φ(1d~d)):∈kj=0. _j→+∞ \dist ( y, ( 1d Z 1_d) ): y _k_j \=0. which contradicts (3.15). This completes the proof. ∎ Lemma 3.13. Suppose that step-sizes θk\ _k\ and ηk\ _k\ satisfy ∑k=0∞ηk=+∞,limk→+∞ηkθk=0,limk→+∞θklog(k)=0,limk→+∞θk2ηklog(k)=0, _k=0^∞ _k=+∞, _k→+∞ _k _k=0, _k→+∞ _k (k)=0, _k→+∞ _k^2 _k (k)=0, and let υk\ _k\ be a uniformly bounded martingale difference sequence with respect to filtration ℱk:=σ(j,j,Ξj|j≤k)F_k:=σ(\ ω_j, Z_j, _j|j≤ k\). Define υ^k:=ηkθkυk _k:= _k _k _k. Then, for any T>0T>0, we have lims→+∞sups≤i≤Λη(λη(s)+T)‖∑k=siθkυ^k+1‖=0. _s→+∞ _s≤ i≤ _η( _η(s)+T) \| _k=s^i _k _k+1 \|=0. The proof of Lemma 3.13 is provided in Appendix 6. Based on Proposition 3.12 and Lemma 3.13, we establish recursion relations for 1dkd\ 1d Z_k 1_d\ and derive the global convergence of framework (DESC) in Theorem 3.14. Theorem 3.14. Suppose Assumption 3.1 and 3.6 hold, and let the sequence k\ Z_k\ be generated by the sub-framework (DESC-Unb) or (DESC-Con). Then limk→∞dist(k,∈ℝm×d:=⊤,∈)=0, _k→∞dist( Z_k,\ Z ^m× d: Z= z 1 , z \)=0, Moreover, the sequence ψ(i,k)\ψ( z_i,k)\ converges for each i∈[d]i∈[d]. Proof. Combining Proposition 3.12 with the update schemes in (DESC-Unb) and (DESC-Con), we derive the following recurrence relations for 1dkd\ 1d Z_k 1_d\: Unbiased compression: 1dk+1d 1d Z_k+1 1_d ∈1dkd−ηkΦϵ~k(1dkd)+θk1dk+1(−Diag())d−ηk1dΞk+1d. ∈ 1d Z_k 1_d- _k ε_k( 1d Z_k 1_d)+ _k 1d E_k+1( W-Diag( W)) 1_d- _k 1d _k+1 1_d. (3.16) Contractive compression: 1dk+1d 1d Z_k+1 1_d ∈1dkd−ηkΦϵ~k(1dkd)−ηk1dΞk+1d. ∈ 1d Z_k 1_d- _k ε_k( 1d Z_k 1_d)- _k 1d _k+1 1_d. (3.17) For update scheme (3.16), we define δk:=ϵ~k _k:= ε_k and υk+1:=θkηk1dk+1(−Diag())d−1dΞk+1d _k+1:= _k _k 1d E_k+1( W-Diag( W)) 1_d- 1d _k+1 1_d. Then (3.16) can be rewritten as 1dk+1d∈1dkd−ηkΦδk(1dkd)+ηkυk+1, 1d Z_k+1 1_d∈ 1d Z_k 1_d- _k _k( 1d Z_k 1_d)+ _k _k+1, (3.18) where δk _k tends to 0 as k→∞k→∞, υk\ _k\ is a martingale difference sequence. We aim to apply Lemma 2.14 again to derive the asymptotic convergence of iterates 1dkd\ 1d Z_k 1_d\. It is easy to see Assumption 2.13-(1) holds vacuously and Assumption 2.13-(2) is equivalent to Assumption 3.1-(2). However, since υk\ _k\ in (3.18) is not uniformly bounded, we need to check whether Assumption 2.13-(3) holds. Denoting υ^k=ηkθkυk _k= _k _k _k, Lemma 3.13 gives us lims→+∞sups≤i≤Λη(λη(s)+T)‖∑k=siηkυk+1‖=lims→+∞sups≤i≤Λη(λη(s)+T)‖∑k=siθkυ^k+1‖=0. _s→+∞ _s≤ i≤ _η( _η(s)+T) \| _k=s^i _k _k+1 \|= _s→+∞ _s≤ i≤ _η( _η(s)+T) \| _k=s^i _k _k+1 \|=0. Applying Lemma 2.14, we conclude that any cluster point of 1dkd\ 1d Z_k 1_d\ lies in A, and the sequence of function values ψ(1dkd)\ψ( 1d Z_k 1_d)\ converges. Combining Proposition 3.7, we know any cluster point of k\ Z_k\ coincides with a cluster point of 1dkdd⊤\ 1d Z_k 1_d 1_d \, and limk→∞ψ(zi,k)=limk→∞ψ(1dkd)) _k→∞ψ(z_i,k)= _k→∞ψ( 1d Z_k 1_d)). For update scheme (3.17), we define δk:=ϵ~k _k:= ε_k and υk+1:=1dΞk+1d _k+1:= 1d _k+1 1_d. Then (3.17) can be reformulated as 1dk+1d∈1dkd−ηkΦδk(1dkd)+ηkυk+1. 1d Z_k+1 1_d∈ 1d Z_k 1_d- _k _k( 1d Z_k 1_d)+ _k _k+1. (3.19) Similar to the proof of (DESC-Unb), one can easily verify that Assumption 2.13 holds. Combining Lemma 2.14 with Proposition 3.11, we deduce that any cluster point of k\ Z_k\ lies in ∈ℝm×d:=⊤,∈\ Z ^m× d: Z= z 1 , z \ and the sequence ψ(k,i)\ψ( z_k,i)\ converges for each i∈[d]i∈[d]. The proof is completed. ∎ 4 Developing Decentralized Stochastic Subgradient-type Methods with Communication Compression and Convergence Guarantees In this section, we demonstrate that framework (DESC) encloses a wide range of decentralized stochastic subgradient-type methods with communication compression in nonsmooth optimization. Some of the methods are nonsmooth extensions of the existing approaches, while others are newly developed based on our framework (DESC). More importantly, we establish convergence results for these decentralized methods for the minimization of nonsmooth definable functions, with applications to the training of nonsmooth neural networks. 4.1 Decentralized SGD-type methods with communication compression Stochastic nonsmooth extension of QDGD. QDGD [51] is a decentralized SGD method with unbiased compression originally designed for smooth optimization. When the objective function is nonsmooth and the evaluation noise is present, we replace ∇fi(i,k)∇ f_i( x_i,k) with a stochastic subgradient i,k∈DFi(⋅,ζi,k+1)(i,k) g_i,k∈ D_F_i(·, _i,k+1)( x_i,k), and employ diminishing sequences θk\ _k\ and ηk\ _k\ instead of constant θ and η. The stochastic nonsmooth extension of QDGD can then be compactly written as k=[1,k,…,d,k]∈[DF1(⋅,ζi,k+1)(i,k),…,DFd(⋅,ζi,k+1)(i,k)],k+1=C(k,k+1)−k,k+1=(1−θk)k+θkk+θkk+1(−Diag())−ηkk. \ aligned G_k&=[ g_1,k,…, g_d,k]∈[D_F_1(·, _i,k+1)( x_i,k),…,D_F_d(·, _i,k+1)( x_i,k)],\\ E_k+1&=C( X_k, ω_k+1)- X_k,\\ X_k+1&=(1- _k) X_k+ _k X_k W+ _k E_k+1( W-Diag( W))- _k G_k.\\ aligned . (QSDGD+) Here, C is an unbiased compression operator. θk\ _k\ is a diminishing sequence of step-sizes with respect to the local average. Nonsmooth extension of CHOCO-SGD. CHOCO-SGD [31, 32] is a decentralized SGD method that combines contractive compression with error compensation. We introduce a nonsmooth extension of CHOCO-SGD, given by the following update scheme: k=[1,k,…,d,k]∈[DF1(⋅,ζi,k+1)(i,k),…,DFd(⋅,ζi,k+1)(i,k)],^k+1=^k+γkC(k−^k,k+1),k+1=k+θk^k+1(−d)−ηkk. \ aligned G_k&=[ g_1,k,…, g_d,k]∈[D_F_1(·, _i,k+1)( x_i,k),…,D_F_d(·, _i,k+1)( x_i,k)],\\ X_k+1&= X_k+ _kC( X_k- X_k, ω_k+1),\\ X_k+1&= X_k+ _k X_k+1( W- I_d)- _k G_k.\\ aligned . (CHOCO-SGD+) Here, C is a contractive compression operator. The two-timescale sequences γk\ _k\ and θk\ _k\ replace the constant θ and γ=1γ=1 used in CHOCO-SGD. With the notation k+1:=γkC(k−k^,k+1)−(k−k^) E_k+1:= _kC( X_k- X_k, ω_k+1)-( X_k- X_k), we can reformulate (CHOCO-SGD+) as k=[1,k,…,d,k]∈[DF1(⋅,ζi,k+1)(i,k),…,DFd(⋅,ζi,k+1)(i,k)],k+1=(1−θk)k+θkk+θkk+1(−d)−ηkk. \ aligned G_k&=[ g_1,k,…, g_d,k]∈[D_F_1(·, _i,k+1)( x_i,k),…,D_F_d(·, _i,k+1)( x_i,k)],\\ X_k+1&=(1- _k) X_k+ _k X_k W+ _k E_k+1( W- I_d)- _k G_k. aligned . Nonsmooth extension of BEER and C-GT. BEER [72] and C-GT [38] utilize an auxiliary variable k Y_k to track the stochastic gradient of the global objective function, and perform contractive compression-based communication on both k X_k and k Y_k simultaneously. We consider a nonsmooth extension of BEER: k=[1,k,…,d,k]∈[DF1(⋅,ζi,k+1)(i,k),…,DFd(⋅,ζi,k+1)(i,k)],k+1=k+θk^k+1(−d)−ηkk,k+1=k+θk^k+1(−d)+k+1−k,^k+1=^k+γkC(k−^k,k+1),^k+1=^k+γkC(k−^k,k+1),0=0, \ aligned G_k&=[ g_1,k,…, g_d,k]∈[D_F_1(·, _i,k+1)( x_i,k),…,D_F_d(·, _i,k+1)( x_i,k)],\\ X_k+1&= X_k+ _k X_k+1( W- I_d)- _k Y_k,\\ Y_k+1&= Y_k+ _k Y_k+1( W- I_d)+ G_k+1- G_k,\\ X_k+1&= X_k+ _kC( X_k- X_k, ω_k+1),\\ Y_k+1&= Y_k+ _kC( Y_k- Y_k, ω_k+1),\\ Y_0&= G_0,\\ aligned . (BEER+) where C is a contractive compression operator. The main differences between BEER and BEER+ are the choice of k G_k and the use of slowly diminishing and two-timescale sequences θk,γk\ _k\,\ _k\ instead of fixed values. With the notation k+1:=γkC(k−^k,k+1)−(k−^k) E_k+1:= _kC( X_k- X_k, ω_k+1)-( X_k- X_k), the update scheme of k\ X_k\ becomes k+1=(1−θk)k+θkk+θkk+1(−d)−ηkk. X_k+1=(1- _k) X_k+ _k X_k W+ _k E_k+1( W- I_d)- _k Y_k. In addition, the iterates of the nonsmooth extension of C-GT are given as follows: k=[1,k,…,d,k]∈[DF1(⋅,ζi,k+1)(i,k),…,DFd(⋅,ζi,k+1)(i,k)],k+1=k+θk~k+1(−d)−ηkk,k+1=k+θk~k+1(−d)+k+1−k,~k+1=^k+γkC(k−^k,k+1),^k+1=(1−αx)^k+αx~k+1,~k+1=^k+γkC(k−^k,k+1),^k+1=(1−αy)^k+αy~k+1,0=0, \ aligned G_k&=[ g_1,k,…, g_d,k]∈[D_F_1(·, _i,k+1)( x_i,k),…,D_F_d(·, _i,k+1)( x_i,k)],\\ X_k+1&= X_k+ _k X_k+1( W- I_d)- _k Y_k,\\ Y_k+1&= Y_k+ _k Y_k+1( W- I_d)+ G_k+1- G_k,\\ X_k+1&= X_k+ _kC( X_k- X_k, ω_k+1),\\ X_k+1&=(1- _x) X_k+ _x X_k+1,\\ Y_k+1&= Y_k+ _kC( Y_k- Y_k, ω_k+1),\\ Y_k+1&=(1- _y) Y_k+ _y Y_k+1,\\ Y_0&= G_0,\\ aligned . (C-GT+) where αx∈(0,1] _x∈(0,1]. Compared to BEER+, C-GT+ includes an additional step of weighted average between the current ~k+1 X_k+1 and the previous ^k X_k. With the notation k+1:=γkC(k−^k,k+1)−(k−^k) E_k+1:= _kC( X_k- X_k, ω_k+1)-( X_k- X_k), the update scheme of (^k,k)\( X_k, X_k)\ can be rewritten as ^k+1=^k+αxγkC(k−^k,k+1),k+1=(1−θk)k+θkk+θkk+1(−d)−ηkk. \ aligned X_k+1&= X_k+ _x _kC( X_k- X_k, ω_k+1),\\ X_k+1&=(1- _k) X_k+ _k X_k W+ _k E_k+1( W- I_d)- _k Y_k.\\ aligned . Decentralized heavy-ball SGD with Nesterov momentum and communication compression. Heavy-ball SGD [48] accelerates the descent by introducing momentum, which helps dampen oscillations in regions with small gradients or high noise. Nesterov momentum [45] further provides a “look-ahead” mechanism in the update rule, leading to faster convergence in many optimization problems. Motivated by the nonsmooth heavy-ball SGD proposed in [33, 66], we integrate unbiased and contractive compression with nonsmooth heavy-ball SGD equipped with Nesterov momentum. This leads to two novel methods, which are formalized as the following update schemes: (DSM-Unb) and (DSM-Con). k=[1,k,…,d,k]∈[DF1(⋅,ζi,k+1)(i,k),…,DFd(⋅,ζi,k+1)(i,k)],k+1x=C(k,k+1)−k,k+1y=C(k,k+1)−k,k+1=(1−θk)k+θkk+θkk+1x(−Diag())−ηk(k+ρk),k+1=(1−τηk)[(1−θk)k+θkk+θkk+1y(−Diag())]+τηkk+1. \ aligned G_k&=[ g_1,k,…, g_d,k]∈[D_F_1(·, _i,k+1)( x_i,k),…,D_F_d(·, _i,k+1)( x_i,k)],\\ E^x_k+1&=C( X_k, ω_k+1)- X_k,\\ E^y_k+1&=C( Y_k, ω_k+1)- Y_k,\\ X_k+1&=(1- _k) X_k+ _k X_k W+ _k E^x_k+1( W-Diag( W))- _k( Y_k+ρ G_k),\\ Y_k+1&=(1-τ _k)[(1- _k) Y_k+ _k Y_k W+ _k E^y_k+1( W-Diag( W))]+τ _k G_k+1.\\ aligned . (DSM-Unb) Here, C is an unbiased compression operator. θk\ _k\ stands for diminishing step-sizes corresponding to the local average. In the update step of k+1 Y_k+1, the local aggregation based on unbiased compression is used as an inertial direction, while k+1 G_k+1 serves as a descent direction. τ>0τ>0 is the heavy-ball momentum parameter and ρ≥0ρ≥ 0 is the Nesterov momentum parameter. k=[1,k,…,d,k]∈[DF1(⋅,ζi,k+1)(i,k),…,DFd(⋅,ζi,k+1)(i,k)],^k+1=^k+γkC(k−^k,k+1),^k+1=^k+γkC(k−^k,k+1),k+1=k+θk^k+1(−d)−ηk(k+ρk),k+1=(1−τηk)[k+θk^k+1(−d)]+τηkk+1. \ aligned G_k&=[ g_1,k,…, g_d,k]∈[D_F_1(·, _i,k+1)( x_i,k),…,D_F_d(·, _i,k+1)( x_i,k)],\\ X_k+1&= X_k+ _kC( X_k- X_k, ω_k+1),\\ Y_k+1&= Y_k+ _kC( Y_k- Y_k, ω_k+1),\\ X_k+1&= X_k+ _k X_k+1( W- I_d)- _k( Y_k+ρ G_k),\\ Y_k+1&=(1-τ _k)[ Y_k+ _k Y_k+1( W- I_d)]+τ _k G_k+1.\\ aligned . (DSM-Con) Here, C is a contractive compression operator. θk,γk\ _k\,\ _k\ are two-timescale diminishing sequences of step-sizes. The sequence k\ Y_k\ is updated by a local aggregation with contractive compression combined with a heavy-ball momentum step. Parameters τ,ρτ,ρ are defined analogously to (DSM-Unb). Decentralized sign-regularized SGD with communication compression. SignSGD [5, 6] is a notable variant of SGD. It replaces the full gradient with its sign, aiming to normalize the update direction and reduce communication costs in distributed optimization. Motivated by DSignSGD proposed in [71], we present two decentralized sign-regularized SGD methods with communication compression. k=[1,k,…,d,k]∈[DF1(⋅,ζi,k+1)(i,k),…,DFd(⋅,ζi,k+1)(i,k)],k+1x=C(k,k+1)−k,k+1y=C(k,k+1)−k,k+1=(1−θk)k+θkk+θkk+1x(−Diag())−ηksign(k+ρk),k+1=(1−τηk)[(1−θk)k+θkk+θkk+1y(−Diag())]+τηkk+1. \ aligned G_k&=[ g_1,k,…, g_d,k]∈[D_F_1(·, _i,k+1)( x_i,k),…,D_F_d(·, _i,k+1)( x_i,k)],\\ E^x_k+1&=C( X_k, ω_k+1)- X_k,\\ E^y_k+1&=C( Y_k, ω_k+1)- Y_k,\\ X_k+1&=(1- _k) X_k+ _k X_k W+ _k E^x_k+1( W-Diag( W))- _ksign( Y_k+ρ G_k),\\ Y_k+1&=(1-τ _k)[(1- _k) Y_k+ _k Y_k W+ _k E^y_k+1( W-Diag( W))]+τ _k G_k+1.\\ aligned . (SignDSGD-Unb) Here, C is an unbiased compression operator, and the sign map serves as a regularizer of the Nesterov momentum term k+ρk Y_k+ρ G_k. Parameters τ,ρτ,ρ, and θk\ _k\ are defined analogously to (DSM-Unb). k=[1,k,…,d,k]∈[DF1(⋅,ζi,k+1)(i,k),…,DFd(⋅,ζi,k+1)(i,k)],^k+1=^k+γkC(k−^k,k+1),^k+1=^k+γkC(k−^k,k+1),k+1=k+θk^k+1(−d)−ηksign(k+ρk),k+1=(1−τηk)[k+θk^k(−d)]+τηkk+1. \ aligned G_k&=[ g_1,k,…, g_d,k]∈[D_F_1(·, _i,k+1)( x_i,k),…,D_F_d(·, _i,k+1)( x_i,k)],\\ X_k+1&= X_k+ _kC( X_k- X_k, ω_k+1),\\ Y_k+1&= Y_k+ _kC( Y_k- Y_k, ω_k+1),\\ X_k+1&= X_k+ _k X_k+1( W- I_d)- _ksign( Y_k+ρ G_k),\\ Y_k+1&=(1-τ _k)[ Y_k+ _k Y_k( W- I_d)]+τ _k G_k+1.\\ aligned . (SignDSGD-Con) Here, C is a contractive compression operator. Step-sizes θk,γk\ _k\,\ _k\, and parameters τ,ρτ,ρ are defined similarly to (DSM-Con). Decentralized stochastic momentum tracking with contractive compression. Based on our framework (DESC-Con), we modify compression term and the update rule for the momentum variables in DoCoM [68], and propose a novel decentralized momentum-tracking method with contractive compression. k=[1,k,…,d,k]∈[DF1(⋅,ζi,k+1)(i,k),…,DFd(⋅,ζi,k+1)(i,k)],^k+1=^k+γkC(k−^k,k+1),k+1=k+θk^k+1(−d)−ηkk,k+1=(1−τηk)k+τηkk+1,^k+1=^k+γkC(k−^k,k+1),k+1=k+θk^k+1(−d)+k+1−k,0=0. \ aligned G_k&=[ g_1,k,…, g_d,k]∈[D_F_1(·, _i,k+1)( x_i,k),…,D_F_d(·, _i,k+1)( x_i,k)],\\ X_k+1&= X_k+ _kC( X_k- X_k, ω_k+1),\\ X_k+1&= X_k+ _k X_k+1( W- I_d)- _k Y_k,\\ V_k+1&=(1-τ _k) V_k+τ _k G_k+1,\\ Y_k+1&= Y_k+ _kC( Y_k- Y_k, ω_k+1),\\ Y_k+1&= Y_k+ _k Y_k+1( W- I_d)+ V_k+1- V_k,\\ V_0&= G_0.\\ aligned . (DSGTM-Con) Here, C is a contractive compression operator. k V_k represents the collection of momentum variables, and k Y_k serves as the collection of momentum-tracking variables incorporating compression-based aggregation. θk,γk\ _k\,\ _k\ are two-timescale diminishing sequences of step-sizes. 4.2 Convergence Guarantees In this part, we demonstrate that all methods discussed in Section 4.1 fit into our framework (DESC), and hence inherit global convergence guarantees to DfD_f-critical points in the minimization of nonsmooth definable functions. Throughout this section, we impose several assumptions on the original problem (DOP) and the methods in Section 4.1. Assumption 4.1. (1) For each i∈[d]i∈[d], ζi _i is drawn randomly and independently from iP_i, F(⋅,ζi)F(·, _i) is definable and admits a definable conservative field DFi(⋅,ζi)D_F_i(·, _i). (2) The summation function f()f( x) is proper. (3) The step-sizes ηk\ _k\ and θk\ _k\ satisfy ∑i=0∞ηk=+∞,limk→+∞ηkθk=0,limk→+∞θklog(k)=0,limk→+∞θk2ηklog(k)=0. _i=0^∞ _k=+∞, _k→+∞ _k _k=0, _k→+∞ _k (k)=0, _k→+∞ _k^2 _k (k)=0. Moreover, the sequence γk\ _k\ is diminishing and satisfies γ0=1,limk→∞γklog(k)=0,limk→∞θkγk=0. _0=1, _k→∞ _k (k)=0, _k→∞ _k _k=0. Remark 4.2. As illustrated in Remark 2.8, definable functions are sufficiently general to enclose the loss functions of nearly all neural networks. Furthermore, [11] states that the result yielded by AD algorithms is contained in a definable conservative field of definable loss function. Hence, Assumption 4.1-(1) is reasonable and mild. Based on [11, Corollary 4], conservativity remains invariant under both expectation and summation, and definability is also invariant under the same operations. As a result, we can define the conservative field for each fif_i as Dfi():=ζi∼iDFi(⋅,ζi)(),D_f_i( x):=E_ _i _iD_F_i(·, _i)( x), (4.10) and a definable and convex conservative field for f as Df():=conv(1d∑i=1dDfi()).D_f( x):=conv\, ( 1d _i=1^dD_f_i( x) ). Methods k Z_k k H_k k+1 E_k+1 QSDGD+ k X_k [k|ℱk]E[ G_k|F_k] C(k,k+1)−kC( X_k, ω_k+1)- X_k DSM-Unb [k] [ smallmatrix X_k\\ Y_k smallmatrix ] [k+ρkτ((1−θk)k+θkk)−τk+1|ℱk]E [ smallmatrix Y_k+ρ G_k\\ τ((1- _k) Y_k+ _k Y_k W)-τ G_k+1 smallmatrix|F_k ] [C(k,k+1)−k(1−τηk)(C(k,k+1)−k)] [ smallmatrixC( X_k, ω_k+1)- X_k\\ (1-τ _k)(C( Y_k, ω_k+1)- Y_k) smallmatrix ] SignDSGD-Unb [k] [ smallmatrix X_k\\ Y_k smallmatrix ] [sign(k+ρk)τ((1−θk)k+θkk)−τk+1|ℱk]E [ smallmatrixsign( Y_k+ρ G_k)\\ τ((1- _k) Y_k+ _k Y_k W)-τ G_k+1 smallmatrix|F_k ] [C(k,k+1)−k(1−τηk)(C(k,k+1)−k)] [ smallmatrixC( X_k, ω_k+1)- X_k\\ (1-τ _k)(C( Y_k, ω_k+1)- Y_k) smallmatrix ] CHOCO-SGD+ k X_k [k|ℱk]E[ G_k|F_k] γkC(k−^k,k+1)−(k−^k) _kC( X_k- X_k, ω_k+1)-( X_k- X_k) BEER+ k X_k [k|ℱk]E[ Y_k|F_k] γkC(k−^k,k+1)−(k−^k) _kC( X_k- X_k, ω_k+1)-( X_k- X_k) C-GT+ k X_k [k|ℱk]E[ Y_k|F_k] γkC(k−^k,k+1)−(k−^k) _kC( X_k- X_k, ω_k+1)-( X_k- X_k) DSM-Con [k] [ smallmatrix X_k\\ Y_k smallmatrix ] [k+ρkτ(k+θk^k+1(−d))−τk+1|ℱk]E [ smallmatrix Y_k+ρ G_k\\ τ( Y_k+ _k Y_k+1( W- I_d))-τ G_k+1 smallmatrix|F_k ] [γkC(k−^k,k+1)−(k−^k)γkC(k−^k,k+1)−(k−^k)] [ smallmatrix _kC( X_k- X_k, ω_k+1)-( X_k- X_k)\\ _kC( Y_k- Y_k, ω_k+1)-( Y_k- X_k) smallmatrix ] SignDSGD-Con [k] [ smallmatrix X_k\\ Y_k smallmatrix ] [sign(k+ρk)τ(k+θk^k+1(−d))−τk+1|ℱk]E [ smallmatrixsign( Y_k+ρ G_k)\\ τ( Y_k+ _k Y_k+1( W- I_d))-τ G_k+1 smallmatrix|F_k ] [γkC(k−^k,k+1)−(k−^k)γkC(k−^k,k+1)−(k−^k)] [ smallmatrix _kC( X_k- X_k, ω_k+1)-( X_k- X_k)\\ _kC( Y_k- Y_k, ω_k+1)-( Y_k- Y_k) smallmatrix ] DSGTM-Con [k] [ smallmatrix X_k\\ Y_k smallmatrix ] [kτk−τk+1|ℱk]E [ smallmatrix Y_k\\ τ V_k-τ G_k+1 smallmatrix|F_k ] [γkC(k−^k,k+1)−(k−^k)γkC(k−^k,k+1)−(k−^k)] [ smallmatrix _kC( X_k- X_k, ω_k+1)-( X_k- X_k)\\ _kC( Y_k- Y_k, ω_k+1)-( Y_k- Y_k) smallmatrix ] Table 3: Specific choices of k Z_k, k H_k, k+1 E_k+1 for each method in Section 4.1. Lemma 4.3 (Theorem 5 and 9 in [11]). Let Assumption 4.1 hold. Then, (1) f is a Lyapunov function for Df()D_f( x), whose stable set is :=∈ℝn:∈Df()A:=\ x ^n: 0∈ D_f( x)\. (2) f():∈Df()\f( x): 0∈ D_f( x)\ is a finite set. Lemma 4.4 (Proposition 4.5 in [66]). Let Assumption 4.1 hold. Then, (1) ψ(,):=f()+12τ‖2ψ( x, y):=f( x)+ 12τ\| y\|^2 is a locally Lipschitz Lyapunov function for the differential inclusion d(,)dt∈−conv(1d∑i=1d[+ρDfi()τ−τDfi()]) d( x, y)dt∈-conv\,( 1d _i=1^d[ smallmatrix y+ρ D_f_i( x)\\ τ y-τ D_f_i( x) smallmatrix]) with stable set :=(,):∈Df(),=0A:=\( x, y): 0∈ D_f( x), y=0\. (2) ψ(,):=f()+1τ‖1ψ( x, y):=f( x)+ 1τ\| y\|_1 is a locally Lipschitz Lyapunov function for the differential inclusion d(,)dt∈−conv(1d∑i=1d[sign(+ρDfi())τ−τDfi()]) d( x, y)dt∈-conv\,( 1d _i=1^d[ smallmatrixsign( y+ρ D_f_i( x))\\ τ y-τ D_f_i( x) smallmatrix]) with stable set :=(,):∈Df(),=0A:=\( x, y): 0∈ D_f( x), y=0\. Lemmas 4.3 and 4.4 present the Lyapunov functions corresponding to different differential inclusions, which is a key to verifying that the methods in Section 4.1 satisfy Assumption 3.1. Proposition 4.5. Suppose Assumption 4.1 holds, then we have 1. (QSDGD+), (DSM-Unb) and (SignDSGD-Unb) fit into sub-framework (DESC-Unb). 2. (CHOCO-SGD+), (BEER+), (C-GT+), (DSM-Con), (SignDSGD-Con) and (DSGTM-Con) fit into sub-framework (DESC-Con). 3. All the aforementioned methods satisfy Assumption 3.1. In Table 3, we show the specific choices of k Z_k, k H_k, k E_k for each method in Section 4.1, thereby verifying the first two items of Proposition 4.5. In Table 4, we illustrate the specific choices of Φi _i, ψ, A and ϵk _k for each method in Section 4.1. Combining with the local boundedness of DFi(⋅,ζi)D_F_i(·, _i), Lemma 4.3, and Lemma 4.4, we can directly verify that all the methods satisfy Assumption 3.1. Methods Φi _i ψ A ϵk _k QSDGD+ DfiD_f_i f ∈ℝn:∈Df()\ x ^n: 0∈ D_f( x)\ 0 DSM-Unb [+ρDfi()τ−τDfi()] [ smallmatrix y+ρ D_f_i( x)\\ τ y-τ D_f_i( x) smallmatrix ] f()+12τ‖2f( x)+ 12τ\| y\|^2 (,):∈Df(),=0\( x, y): 0∈ D_f( x), y=0\ ‖k−k+1‖\| X_k- X_k+1\| SignDSGD-Unb [sign(+ρDfi())τ−τDfi()] [ smallmatrixsign( y+ρ D_f_i( x))\\ τ y-τ D_f_i( x) smallmatrix ] f()+1τ‖1f( x)+ 1τ\| y\|_1 (,):∈Df(),=0\( x, y): 0∈ D_f( x), y=0\ ‖k−k+1‖\| X_k- X_k+1\| CHOCO-SGD+ DfiD_f_i f ∈ℝn:∈Df()\ x ^n: 0∈ D_f( x)\ 0 BEER+ DfiD_f_i f ∈ℝn:∈Df()\ x ^n: 0∈ D_f( x)\ 0 C-GT+ DfiD_f_i f ∈ℝn:∈Df()\ x ^n: 0∈ D_f( x)\ 0 DSM-Con [+ρDfi()τ−τDfi()] [ smallmatrix y+ρ D_f_i( x)\\ τ y-τ D_f_i( x) smallmatrix ] f()+12τ‖2f( x)+ 12τ\| y\|^2 (,):∈Df(),=0\( x, y): 0∈ D_f( x), y=0\ ‖k−k+1‖\| X_k- X_k+1\| SignDSGD-Con [sign(+ρDfi())τ−τDfi()] [ smallmatrixsign( y+ρ D_f_i( x))\\ τ y-τ D_f_i( x) smallmatrix ] f()+1τ‖1f( x)+ 1τ\| y\|_1 (,):∈Df(),=0\( x, y): 0∈ D_f( x), y=0\ ‖k−k+1‖\| X_k- X_k+1\| DSGTM-Con [τ−τDfi()] [ smallmatrix y\\ τ y-τ D_f_i( x) smallmatrix ] f()+12τ‖2f( x)+ 12τ\| y\|^2 (,):∈Df(),=0\( x, y): 0∈ D_f( x), y=0\ ‖k−k+1‖\| X_k- X_k+1\| Table 4: Specific choices of Φi _i, ψ, A and ϵk _k for each method in Section 4.1. By applying Theorem 3.14, we establish the convergence guarantees for above-mentioned methods. Theorem 4.6. Suppose Assumption 4.1 holds, and the sequence k\ X_k\ (and k\ Y_k\, if defined) is generated by one of (QSDGD+), (DSM-Unb), (SignDSGD-Unb),(CHOCO-SGD+), (BEER+), (C-GT+), (DSM-Con), (SignDSGD-Con) and (DSGTM-Con). Assume that the sequence k\ X_k\ (and k\ Y_k\, if defined) is bounded. Then, any cluster point of k\ X_k\ is a DfD_f-critical point of (DOP), and the sequence f(i,k):k∈ℕ\f( x_i,k):k \ converges for each i∈[d]i∈[d]. 5 Numerical Experiments In this section, we present preliminary numerical experiments to evaluate the performance of our proposed framework, which encompasses efficient decentralized stochastic subgradient-type methods with communication compression. Our numerical comparisons are two-fold: first, we compare existing methods with their nonsmooth extensions under our framework; second, we compare these nonsmooth extensions with newly developed methods adapted to our framework. All numerical experiments are conducted on a platform equipped with two Intel(R) Xeon(R) Gold 5317 CPUs (@@ 3.00GHz and 512GB RAM) and eight NVIDIA GeForce RTX 4090 GPUs, running Ubuntu 20.04. All decentralized algorithms are implemented in Python 3.8 and PyTorch 1.13.1, using NCCL 2.14.3 (CUDA 11.7) as the communication backend. 5.1 Testing problem and implementation details We train ResNet-20 [61] models in a decentralized manner on the CIFAR-10 image classification task. It is worth noting that the ResNet-20 neural network employs ReLU as its activation function, resulting in a non-Clarke-regular but definable loss function. Setup. In the first group of numerical comparisons, the decentralized network topology is configured as a ring structure with 8 agents, consistent with the experimental setup in [31, 56]. In the second comparison group, we use an Erdős-Rényi (E.R.) random graph topology [42] with 8 agents to evaluate the performance in a more general decentralized network setting. The mixing matrix is chosen as the classical Metropolis constant edge weight matrix [64]. Moreover, we split the original dataset evenly into 8 parts, distributing each part to one agent as its local dataset. At the beginning of each training epoch, we reshuffle the local dataset of each agent and form batches of size 128128. Training is stopped at epoch 200. All compared methods are executed five times with varying random seeds. Furthermore, the choices for the unbiased compression operator and the contractive compression operator in our experiments are as follows: • Unbiased compression: The 88-bit random quantization operator Q28Q_2^8 from Example 3.3. • Contractive compression: The RandomRandom-10%10\% and TopTop-10%10\% sparsification operators from Example 3.5 and rescaled 88-bits random quantization operator 11+mind/216,d/28Q28 11+ \d/2^16, d/2^8\Q_2^8 (abbreviated as rescaled Q28Q_2^8). Implementation details. A common strategy for updating ηk\ _k\ is to decay it at specific milestones while keeping it constant otherwise. Meanwhile, θk\ _k\ remains constant, and γk\ _k\ is typically fixed to 1.01.0 in existing works [31, 56, 72] under the smooth setting. To meet the requirement in Assumption 4.1, namely that the sequences (ηk,θk,γk)\( _k, _k, _k)\ form a three-timescale scheme and are of order o(1log(k))o( 1 (k)), we propose another update strategy for (ηk,θk,γk)\( _k, _k, _k)\. Empirically, starting with initial η0 _0, we warm up ηk\ _k\ in the first five epochs to obtain ηwarm _warm in both strategies. 1. Strategy 1: ηk(1) _k^(1) =ηwarm ,5≤k⋅number of batches per epoch<100,0.1ηwarm ,100≤k⋅number of batches per epoch<180,0.01ηwarm ,180≤k⋅number of batches per epoch≤200, = θk(1) θ^(1)_k ≡θ0,γk(1)≡1.0. ≡ _0, γ^(1)_k≡ 0. This means the step size is decayed by a factor of 0.1 at the 100th and 180th epochs. 2. Strategy 2: ηk(2) _k^(2) =ηk(1),5≤k⋅number of batches per epoch<100,ηk(1)log(k−100+e)1.01,100≤k⋅number of batches per epoch<200, = θk(2) θ^(2)_k =θ0ηk(2)/(ηk(2)log(k))s,s∈(0,12), = _0η^(2)_k/(η^(2)_k (k))^s,s∈(0, 12), γk(2) γ^(2)_k =θk(2)/(θk(2)log(k))s,s∈(0,12). =θ^(2)_k/(θ^(2)_k (k))^s,s∈(0, 12). By default, we set s=0.25s=0.25 in our experiments. Additionally, the fine-tuned hyper-parameters η0 _0 and θ0 _0 for different methods and compression operators are presented in Table 5 and 6. The momentum parameter τ in DSM-Unb(Con), DSGTM-Unb(Con) and SignDSGD-Unb(Con) is set as τ=0.1η0τ= 0.1 _0 by default. Compression operator Method Learning rate η0 _0 Consensus step-size θ0 _0 Rescaled Q28Q_2^8 CHOCO-SGD(+) 0.06 0.2 BEER(+) 0.06 0.2 DSGTM-Con 0.15 0.2 DSM-Con 0.06 0.2 SignDSGD-Con 0.00005 0.2 RandomRandom-10%10\% CHOCO-SGD(+) 0.075 0.075 BEER(+) 0.02 0.02 DSGTM-Con 0.02 0.02 DSM-Con 0.2 0.075 SignDSGD-Con 0.0002 0.075 TopTop-10%10\% CHOCO-SGD(+) 0.1 0.15 BEER(+) 0.06 0.2 DSGTM-Con 0.1 0.15 DSM-Con 0.1 0.15 SignDSGD-Con 0.00005 0.15 Table 5: Tuned hyper-parameters of CHOCO-SGD+, BEER+, DSGTM-Con, DSM-Con and SignDSGD-Con for training ResNet-20 on CIFAR-10, corresponding to the ring/E.R. topology with 8 agents. Compression operator Method Learning rate η0 _0 Consensus step-size θ0 _0 Q28Q_2^8 QSDGD+ 0.1 0.15 DSGTM-Unb 0.05 0.0075 DSM-Unb 0.05 0.075 SignDSGD-Unb 0.0001 0.15 Table 6: Tuned hyper-parameters of QSDGD+, DSGTM-Unb, DSM-Unb and SignDSGD-Unb for training ResNet-20 on CIFAR-10, corresponding to the ring/E.R. topology with 8 agents. 5.2 Performance comparison between existing methods and their nonsmooth extensions under our framework Figures 2(a), 2(b) and 2(c) present the numerical performance of the following comparison pairs: • CHOCO-SGD vs. CHOCO-SGD+, • BEER vs. BEER+ • QSDGD 111QDGD was originally proposed in [51]. We derive QSDGD by replacing the full gradient with stochastic gradients. vs. QSDGD+ In each pair, the former represents the original method from the existing literature, using Strategy 1 to update the step-sizes, while the latter (marked with a ”+”) is its direct nonsmooth extension adapted to our framework, using Strategy 2 for step-size updates. Within each pair, the hyper-parameters (including θ0 _0 and η0 _0) are set identically. (a) The comparison between CHOCO-SGD and CHOCO-SGD+ with the Random-10%10\% operator. (b) The comparison between BEER and BEER+ with the rescaled Q28Q_2^8 operator. (c) The comparison between QSDGD and QSDGD+ with the Q28Q_2^8 operator. As shown in Figure 2(a)-2(c), the nonsmooth extensions of existing methods based on our framework demonstrate performance comparable to their original counterparts when training nonsmooth neural networks. Moreover, we observe that when using the Random-10%10\% operator, the original CHOCO-SGD exhibits loss spikes and abrupt declines in test accuracy, while CHOCO-SGD+ behaves more stably and smoothly compared to the original version. 5.3 Performance comparison between nonsmooth extensions of existing methods and the newly developed methods under our framework In this part, we conduct numerical comparisons organized into the following three groups, each of which utilizes Strategy 2 for updating step-sizes. • GD-based methods with contractive compression: CHOCO-SGD+, DSM-Con and SignDSGD-Con; • Gradient-tracking-based methods with contractive compression: BEER+ and DSGTM-Con; • Methods with unbiased compression: QSDGD+, DSM-Unb, SignDSGD-Unb and DSGTM-Unb. In the first two experimental groups, we evaluate their performance over three contractive compression operators, including the TopTop-10%10\% operator, the RandomRandom-10%10\% operator, and the rescaled Q28Q_2^8 operator. In the last experimental group, we utilize the Q28Q_2^8 operator as our unbiased compression operator. Furthermore, we incorporate vanilla DSGD [37] as the baseline algorithm. (d) Numerical results of GD-based methods with contractive compression (TopTop-10%10\% operator). (e) Numerical results of Gradient-tracking-based methods with contractive compression (TopTop-10%10\% operator). (f) Numerical results of methods with unbiased compression (Q28Q_2^8 operator). (g) Numerical results of GD-based methods with contractive compression (rescaled Q28Q_2^8 operator). (h) Numerical results of Gradient-tracking-based methods with contractive compression (rescaled Q28Q_2^8 operator). (i) Numerical results of GD-based methods with contractive compression (RandomRandom-10%10\% operator). (j) Numerical results of Gradient-tracking-based methods with contractive compression (RandomRandom-10%10\% operator). From Figures 2(d), 2(g), and 2(i) (a)-(b), it can be observed that SignDSGD-Con and DSM-Con outperform the extended versions of CHOCO-SGD in terms of both training loss and test accuracy, and they are closer to the baseline method, vanilla DSGD. From Figures 2(d), 2(g) and 2(i) (c)-(d), we can infer that, with a smaller communication budget, CHOCO-SGD+ achieves higher test accuracy, followed by the two newly developed methods. However, with a slightly larger communication budget, SignDSGD-Con and DSM-Con perform better. Furthermore, from Figures 2(e), 2(h) and 2(j), we conclude that DSGTM-Con matches the uncompressed baseline in both test accuracy and training loss, while consistently reducing communication costs by 1/31/3, demonstrating consistently better overall performance than BEER+ across all evaluated metrics. Figure 2(f) shows that, among unbiased compression methods, SignDSGD-Unb and DSM-Unb achieve the highest test accuracy, while QSDGD+ and DSGTM-Unb exhibit slightly inferior performance. Notably, QSDGD+ attains competitive accuracy and lower training loss with single-node communication costs below 10410^4 MB. However, as the communication budget increases, DSM-Unb emerges as the top-performing method. Based on the comprehensive numerical comparisons, we demonstrate that our framework exhibits significant potential for developing methods that balance communication efficiency and accuracy. 6 Concluding Remarks In this paper, we design a unified framework (DESC) for developing decentralized stochastic subgradient-type methods with communication compression. By configuring different compression errors and selecting diagonal matrix Σ as either Diag()Diag( W) or d I_d, our framework can adapt to two variants suitable for unbiased or contractive communication compression, respectively. Moreover, (DESC) employs a family of set-valued mappings Φii∈[d]\ _i\_i∈[d] to characterize the general relation between update direction and iterates, which unifies a broad class of acceleration techniques, such as Heavy-ball momentum, Nesterov momentum, and gradient tracking. By introducing slowly diminishing sequences θk\ _k\ (and γk\ _k\) to regulate modified local average and the update of local copies, we establish the consensus properties and global asymptotic convergence for our framework (DESC). In particular, we demonstrate that a wide range of decentralized stochastic subgradient-type methods with communication compression fit into our proposed framework, including the nonsmooth extensions of QDGD, CHOCO-SGD, BEER, and others. Therefore, our theoretical results provide, for the first time, global convergence guarantees for these compression-based decentralized SGD-type methods in nonsmooth nonconvex optimization. Further, we develop several compression-based methods based on (DESC), such as DSM-Unb(Con), SignDSGD-Unb(Con), DSGTM-Con, demonstrating the significant potential of (DESC) in developing practical methods. Preliminary numerical results validate our theoretical results and showcase the high efficiency of these methods within the framework. Finally, several topics warrant future study to further understand the behavior of decentralized stochastic subgradient-type methods with communication compression in nonsmooth optimization. For instance, it would be valuable to explore whether, under random initialization, the iterates of our framework (DESC) almost surely converge to a Clarke-critical point, i.e., excluding potential spurious critical points within the set of DfD_f. Besides, another interesting direction is to investigate the development of nonsmooth Adam-like compression-based algorithms based on our framework, aiming to achieve a better trade-off between communication compression and accuracy. References [1] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication-efficient sgd via gradient quantization and encoding. Advances in neural information processing systems, 30, 2017. [2] Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. Advances in Neural Information Processing Systems, 31, 2018. [3] Michel Benaïm. Dynamics of stochastic approximation algorithms. In Seminaire de Probabilites XXXIII, pages 1–68. Springer, 2006. [4] Michel Benaïm, Josef Hofbauer, and Sylvain Sorin. Stochastic approximations and differential inclusions. SIAM Journal on Control and Optimization, 44(1):328–348, 2005. [5] Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. Signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning, pages 560–569. PMLR, 2018. [6] Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signsgd with majority vote is communication efficient and fault tolerant. arXiv preprint arXiv:1810.05291, 2018. [7] Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. Journal of Machine Learning Research, 24(276):1–50, 2023. [8] Wei Bian and Xiaoping Xue. Subgradient-based neural networks for nonsmooth nonconvex optimization problems. IEEE Transactions on Neural Networks, 20(6):1024–1038, 2009. [9] Jérôme Bolte, Aris Daniilidis, Adrian Lewis, and Masahiro Shiota. Clarke subgradients of stratifiable functions. SIAM Journal on Optimization, 18(2):556–572, 2007. [10] Jérôme Bolte and Edouard Pauwels. A mathematical model for automatic differentiation in machine learning. Advances in Neural Information Processing Systems, 33:10809–10819, 2020. [11] Jérôme Bolte and Edouard Pauwels. Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning. Mathematical Programming, 188(1):19–51, 2021. [12] Kallista Bonawitz, Peter Kairouz, Brendan McMahan, and Daniel Ramage. Federated learning and privacy: Building privacy-preserving systems for machine learning and data science on decentralized data. Queue, 19(5):87–114, 2021. [13] Vivek S Borkar. Stochastic approximation: a dynamical systems viewpoint, volume 48. Springer, 2009. [14] Vivek S Borkar and Vivek S Borkar. Stochastic approximation: a dynamical systems viewpoint, volume 9. Springer, 2008. [15] Camille Castera, Jérôme Bolte, Cédric Févotte, and Edouard Pauwels. An inertial newton algorithm for deep learning. The Journal of Machine Learning Research, 22(1):5977–6007, 2021. [16] Claudio Cicconetti, Marco Conti, and Andrea Passarella. A decentralized framework for serverless edge computing in the internet of things. IEEE Transactions on Network and Service Management, 18(2):2166–2180, 2020. [17] Francis H Clarke, Yuri S Ledyaev, Ronald J Stern, and Peter R Wolenski. Nonsmooth analysis and control theory, volume 178. Springer Science & Business Media, 2008. [18] Frank H Clarke. Optimization and nonsmooth analysis, volume 5. SIAM, 1990. [19] Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason D Lee. Stochastic subgradient method converges on tame functions. Foundations of Computational Mathematics, 20(1):119–154, 2020. [20] Shuiguang Deng, Hailiang Zhao, Weijia Fang, Jianwei Yin, Schahram Dustdar, and Albert Y Zomaya. Edge intelligence: The confluence of edge computing and artificial intelligence. IEEE Internet of Things Journal, 7(8):7457–7469, 2020. [21] Thinh T Doan, Siva Theja Maguluri, and Justin Romberg. Convergence rates of distributed gradient methods under random quantization: A stochastic approximation approach. IEEE Transactions on Automatic Control, 66(10):4469–4484, 2020. [22] John C Duchi and Feng Ruan. Stochastic methods for composite and weakly convex optimization problems. SIAM Journal on Optimization, 28(4):3229–3259, 2018. [23] Ilyas Fatkhullin, Igor Sokolov, Eduard Gorbunov, Zhize Li, and Peter Richtárik. Ef21 with bells & whistles: Practical algorithmic extensions of modern error feedback. arXiv preprint arXiv:2110.03294, 2021. [24] Yuanqi Gao, Wei Wang, and Nanpeng Yu. Consensus multi-agent reinforcement learning for volt-var control in power distribution networks. IEEE Transactions on Smart Grid, 12(4):3594–3604, 2021. [25] Samuel Horvóth, Chen-Yu Ho, Ludovit Horvath, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning. In Mathematical and Scientific Machine Learning, pages 129–141. PMLR, 2022. [26] Xinmeng Huang, Yiming Chen, Wotao Yin, and Kun Yuan. Lower bounds and nearly optimal algorithms in distributed learning with communication compression. Advances in Neural Information Processing Systems, 35:18955–18969, 2022. [27] Charikleia Iakovidou and Ermin Wei. S-near-dgd: A flexible distributed stochastic gradient method for inexact communication. IEEE Transactions on Automatic Control, 68(2):1281–1287, 2022. [28] Rustem Islamov, Yuan Gao, and Sebastian U. Stich. Near optimal decentralized optimization with compression and momentum tracking. CoRR, abs/2405.20114, 2024. [29] Cédric Josz and Lexiao Lai. Lyapunov stability of the subgradient method with constant step size. Mathematical Programming, 202(1):387–396, 2023. [30] Harsh Kasyap and Somanath Tripathy. Privacy-preserving decentralized learning framework for healthcare system. ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM), 17(2s):1–24, 2021. [31] Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. arXiv preprint arXiv:1907.09356, 2019. [32] Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, pages 3478–3487. PMLR, 2019. [33] Tam Le. Nonsmooth nonconvex stochastic heavy ball. Journal of Optimization Theory and Applications, 201(2):699–719, 2024. [34] Xin Liu Lei Wang. A variance-reduced stochastic gradient tracking algorithm for decentralized optimization with orthogonality constraints. Journal of Industrial and Management Optimization, 19(10):7753–7776, 2023. [35] Jueyou Li, Guo Chen, Zhiyou Wu, and Xing He. Distributed subgradient method for multi-agent optimization with quantized communication. Mathematical Methods in the Applied Sciences, 40(4):1201–1213, 2017. [36] Yao Li, Xiaorui Liu, Jiliang Tang, Ming Yan, and Kun Yuan. Decentralized composite optimization with compression. arXiv preprint arXiv:2108.04448, 2021. [37] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Advances in neural information processing systems, 30, 2017. [38] Yiwei Liao, Zhuorui Li, Kun Huang, and Shi Pu. A compressed gradient tracking method for decentralized optimization with linear convergence. IEEE Transactions on Automatic Control, 67(10):5622–5629, 2022. [39] Yiwei Liao, Zhuorui Li, Shi Pu, and Tsung-Hui Chang. A robust compressed push-pull method for decentralized nonconvex optimization. arXiv preprint arXiv:2408.01727, 2024. [40] Wei Liu, Anweshit Panda, Ujwal Pandey, Christopher Brissette, Yikang Shen, George M. Slota, Naigang Wang, Jie Chen, and Yangyang Xu. Compressed decentralized momentum stochastic gradient methods for nonconvex optimization, 2025. [41] Zeyu Meng, Hongli Xu, Min Chen, Yang Xu, Yangming Zhao, and Chunming Qiao. Learning-driven decentralized machine learning in resource-constrained wireless edge computing. In IEEE INFOCOM 2021-IEEE Conference on Computer Communications, pages 1–10. IEEE, 2021. [42] Asaf Nachmias and Yuval Peres. Critical random graphs: diameter and mixing time. 2008. [43] Roula Nassif, Stefan Vlaski, Marco Carpentiero, Vincenzo Matta, and Ali H Sayed. Differential error feedback for communication-efficient decentralized learning. IEEE Transactions on Signal Processing, 2025. [44] Angelia Nedić, Alex Olshevsky, and Michael G Rabbat. Network topology and communication-computation tradeoffs in decentralized optimization. Proceedings of the IEEE, 106(5):953–976, 2018. [45] Yurii Evgen’evich Nesterov. A method of solving a convex programming problem with convergence rate o\ (kˆ2\ ). In Doklady Akademii Nauk, volume 269, pages 543–547. Russian Academy of Sciences, 1983. [46] Edouard Pauwels. Incremental without replacement sampling in nonconvex optimization. Journal of Optimization Theory and Applications, 190(1):274–299, 2021. [47] S Unnikrishna Pillai, Torsten Suel, and Seunghun Cha. The perron-frobenius theorem: some of its applications. IEEE Signal Processing Magazine, 22(2):62–75, 2005. [48] Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computational mathematics and mathematical physics, 4(5):1–17, 1964. [49] Shi Pu, Alfredo Garcia, and Zongli Lin. Noise reduction by swarming in social foraging. IEEE Transactions on Automatic Control, 61(12):4007–4013, 2016. [50] Xun Qian, Peter Richtárik, and Tong Zhang. Error compensated distributed sgd can be accelerated. Advances in Neural Information Processing Systems, 34:30401–30413, 2021. [51] Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, and Ramtin Pedarsani. An exact quantized decentralized gradient descent algorithm. IEEE Transactions on Signal Processing, 67(19):4934–4947, 2019. [52] Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. Ef21: A new, simpler, theoretically better, and practically faster error feedback. Advances in Neural Information Processing Systems, 34:4384–4396, 2021. [53] H. Robbins and D. Siegmund. A convergence theorem for non negative almost supermartingales and some applications**research supported by nih grant 5-r01-gm-16895-03 and onr grant n00014-67-a-0108-0018. In Jagdish S. Rustagi, editor, Optimizing Methods in Statistics, pages 233–257. Academic Press, 1971. [54] Suhail M Shah and Raghu Bollapragada. A stochastic gradient tracking algorithm for decentralized optimization with inexact communication. arXiv preprint arXiv:2307.14942, 2023. [55] Wei Shi, Qing Ling, Gang Wu, and Wotao Yin. Extra: An exact first-order algorithm for decentralized consensus optimization. SIAM Journal on Optimization, 25(2):944–966, 2015. [56] Navjot Singh, Deepesh Data, Jemin George, and Suhas Diggavi. Squarm-sgd: Communication-efficient momentum sgd for decentralized optimization. IEEE Journal on Selected Areas in Information Theory, 2(3):954–969, 2021. [57] Navjot Singh, Deepesh Data, Jemin George, and Suhas Diggavi. Sparq-sgd: Event-triggered and compressed communication in decentralized optimization. IEEE Transactions on Automatic Control, 68(2):721–736, 2022. [58] Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. Advances in neural information processing systems, 31, 2018. [59] Ichiro Suzuki and Masafumi Yamashita. Distributed anonymous mobile robots: Formation of geometric patterns. SIAM Journal on Computing, 28(4):1347–1363, 1999. [60] Hanlin Tang, Shaoduo Gan, Ce Zhang, Tong Zhang, and Ji Liu. Communication compression for decentralized training. Advances in Neural Information Processing Systems, 31, 2018. [61] Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. Advances in neural information processing systems, 29, 2016. [62] Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Terngrad: Ternary gradients to reduce communication in distributed deep learning. Advances in neural information processing systems, 30, 2017. [63] Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1):65–78, 2004. [64] Lin Xiao, Stephen Boyd, and Sanjay Lall. Distributed average consensus with time-varying metropolis weights. Automatica, 1, 2006. [65] Nachuan Xiao, Xiaoyin Hu, Xin Liu, and Kim-Chuan Toh. Adam-family methods for nonsmooth optimization with convergence guarantees. arXiv preprint arXiv:2305.03938, 2023. [66] Nachuan Xiao, Xiaoyin Hu, and Kim-Chuan Toh. Convergence guarantees for stochastic subgradient methods in nonsmooth nonconvex optimization. arXiv preprint arXiv:2307.10053, 2023. [67] Yonggui Yan, Jie Chen, Pin-Yu Chen, Xiaodong Cui, Songtao Lu, and Yangyang Xu. Compressed decentralized proximal stochastic gradient method for nonconvex composite problems with heterogeneous data. In International Conference on Machine Learning, pages 39035–39061. PMLR, 2023. [68] Chung-Yiu Yau and Hoi-To Wai. Docom: Compressed decentralized optimization with near-optimal sample complexity. arXiv preprint arXiv:2202.00255, 2022. [69] Hantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Ji Liu, and Ce Zhang. Zipml: Training linear models with end-to-end low precision, and a little bit of deep learning. In International Conference on Machine Learning, pages 4035–4043. PMLR, 2017. [70] Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of reinforcement learning and control, pages 321–384, 2021. [71] Siyuan Zhang, Nachuan Xiao, and Xin Liu. Decentralized stochastic subgradient methods for nonsmooth nonconvex optimization. arXiv preprint arXiv:2403.11565, 2024. [72] Haoyu Zhao, Boyue Li, Zhize Li, Peter Richtárik, and Yuejie Chi. Beer: Fast o(1/t)o(1/t) rate for decentralized nonconvex optimization with communication compression. Advances in Neural Information Processing Systems, 35:31653–31667, 2022. [73] Shuai Zheng, Ziyue Huang, and James Kwok. Communication-efficient distributed blockwise momentum sgd with error-feedback. Advances in Neural Information Processing Systems, 32, 2019. [74] Zehan Zhu, Heng Zhao, Yan Huang, Joey Tianyi Zhou, Shouling Ji, and Jinming Xu. Dp-csgp: Differentially private stochastic gradient push with compressed communication. arXiv preprint arXiv:2512.13583, 2025. [75] Stanisław Łojasiewicz. Ensembles semi-analytiques. 1965. Appendix 6.1 Proof of Lemma 3.8 Proof. A straightforward calculation shows that, for any N∈ℕ∗N ^*, aγk+∑i=Nk∏j=ik(1−aγj)aγi−1+∏j=N−1k(1−aγj) ~a _k+ _i=N^k _j=i^k(1-a _j)a _i-1+ _j=N-1^k(1-a _j) (6.1) = = aγk+∑i=N+1k∏j=ik(1−aγj)aγi−1+∏j=Nk(1−aγj)aγN−1+∏j=Nk(1−aγj)(1−aγN−1) ~a _k+ _i=N+1^k _j=i^k(1-a _j)a _i-1+ _j=N^k(1-a _j)a _N-1+ _j=N^k(1-a _j)(1-a _N-1) = = aγk+∑i=N+1k∏j=ik(1−aγj)aγi−1+∏j=Nk(1−aγj) ~a _k+ _i=N+1^k _j=i^k(1-a _j)a _i-1+ _j=N^k(1-a _j) = = aγk+∑i=k∏j=ik(1−aγj)aγi−1+∏j=k−1k(1−aγj) ~a _k+ _i=k^k _j=i^k(1-a _j)a _i-1+ _j=k-1^k(1-a _j) = = 1 ~1 We also note that ∑i=1N−1∏j=ik(1−aγj)aγi−1=∏j=N−1k(1−aγj)−∏j=0k(1−aγj). _i=1^N-1 _j=i^k(1-a _j)a _i-1= _j=N-1^k(1-a _j)- _j=0^k(1-a _j). (6.2) Since limk→+∞θkγk=0 _k→+∞ _k _k=0, for any ε>0 >0, there exists N0∈ℕ∗N_0 ^*, such that θkγk<ε _k _k< , for all k≥N0k≥ N_0. Combining (6.1) and (6.2), we obtain ∑i=1k(∏j=ik(1−aγj))C0θi−1 ~ _i=1^k ( _j=i^k(1-a _j) )C_0 _i-1 = = C0a∑i=1N0−1∏j=ik(1−aγj)aγi−1θi−1γi−1+C0a∑i=N0k∏j=ik(1−aγj)aγi−1θi−1γi−1 ~ C_0a _i=1^N_0-1 _j=i^k(1-a _j)a _i-1 _i-1 _i-1+ C_0a _i=N_0^k _j=i^k(1-a _j)a _i-1 _i-1 _i-1 ≤ ≤ C0amax1≤i−1≤N0−1θi−1γi−1[1−∏j=0N0−2(1−aγj)]∏j=N0−1k(1−aγj)+C0a[1−aγk−∏j=N0−1k(1−aγj)]ε C_0a _1≤ i-1≤ N_0-1 \ _i-1 _i-1 \ [1- _j=0^N_0-2(1-a _j) ] _j=N_0-1^k(1-a _j)+ C_0a[1-a _k- _j=N_0-1^k(1-a _j)] Taking the limit as k→∞k→∞ and using the fact that ∏j=N0−1k(1−aγj)→0 _j=N_0-1^k(1-a _j)→ 0, we have limk→∞∑i=1k(∏j=ik(1−aγj))C0θi−1=C0aε _k→∞ _i=1^k ( _j=i^k(1-a _j) )C_0 _i-1= C_0a Since ε>0 >0 is arbitrary, the desired result follows. ∎ 6.2 Proof of Lemma 3.9 Proof. Let zk=γkυk+1+∑i=1k−1γi(∏j=i+1k(1−aγj))υi+1z_k= _k _k+1+ _i=1^k-1 _i ( _j=i+1^k(1-a _j) ) _i+1 and z0=0z_0=0. Define ρk,i:=γi∏j=i+1k(1−aγj) _k,i:= _i _j=i+1^k(1-a _j) and ρk,k:=γk _k,k:= _k. Then there exists K>0K>0 such that, for all k≥i≥Kk≥ i≥ K, we have |ρk,i|≤γi| _k,i|≤ _i and aγi<1/2a _i<1/2. Without loss of generality, we assume that ρk,i≥0 _k,i≥ 0, for all k≥i≥Kk≥ i≥ K. From the definition of zkz_k, it follows that zk=∑i=1kρk,iυi+1,k≥1.z_k= _i=1^k _k,i _i+1, k≥ 1. Since the martingale difference sequence υk\ _k\ is uniformly bounded, it is sub-Gaussian. Thus, there exists a constant M>0M>0 such that, for all k≥0k≥ 0 and all w∈ℝnw ^n, [exp(⟨w,υk+1⟩)|ℱk]≤exp(M2‖w‖2).E [ ( w, _k+1 ) |F_k ]≤ ( M2\|w\|^2 ). Therefore, for any s>K,T>0,w∈ℝns>K,T>0,w ^n and C>0C>0, let Zi+1:=exp⟨Cw,∑k=siρΛγ(λγ(s)+T),kυk+1⟩−MC22∑k=siρΛγ(λγ(s)+T),k2‖w‖2,Z_i+1:= \ Cw, _k=s^i _ _γ( _γ(s)+T),k _k+1 - MC^22 _k=s^i _ _γ( _γ(s)+T),k^2\|w\|^2 \, where λγ(0):=0,λγ(i):=∑k=1iγk _γ(0):=0, _γ(i):= _k=1^i _k, and Λγ(t):=supk≥0:t≥λγ(k) _γ(t):= \k≥ 0:t≥ _γ(k)\. Then, for any i≥si≥ s, [Zi+1|ℱi]≤ZiE[Z_i+1|F_i]≤ Z_i, so Zii≥s\Z_i\_i≥ s forms a supermartingale. Hence for any δ>0δ>0, and C>0C>0, it holds that ℙ(sups≤i≤Λγ(λγ(s)+T)⟨w,∑k=siρΛγ(λγ(s)+T),kυk+1⟩>δ) ( _s≤ i≤ _γ( _γ(s)+T) w, _k=s^i _ _γ( _γ(s)+T),k _k+1 >δ ) (6.3) = = ℙ(sups≤i≤Λγ(λγ(s)+T)⟨Cw,∑k=siρΛγ(λγ(s)+T),kυk+1⟩>Cδ) ( _s≤ i≤ _γ( _γ(s)+T) Cw, _k=s^i _ _γ( _γ(s)+T),k _k+1 >Cδ ) ≤ ≤ ℙ(sups≤i≤Λγ(λγ(s)+T)Zi+1>exp(Cδ−MC22∑k=sΛγ(λγ(s)+T)ρΛγ(λγ(s)+T),k2‖w‖2)) ( _s≤ i≤ _γ( _γ(s)+T)Z_i+1> (Cδ- MC^22 _k=s _γ( _γ(s)+T) _ _γ( _γ(s)+T),k^2\|w\|^2 ) ) ≤ ≤ exp(MC22‖w‖2∑k=sΛγ(λγ(s)+T)ρΛγ(λγ(s)+T),k2−Cδ). ( MC^22\|w\|^2 _k=s _γ( _γ(s)+T) _ _γ( _γ(s)+T),k^2-Cδ ). Here, the last inequality is followed by Doob’s maximal inequality and the fact [Zs+1]≤1E[Z_s+1]≤ 1. Since C is arbitrary, we may set C=δM‖w‖2∑k=sΛγ(λγ(s)+T)ρΛγ(λγ(s)+T),k2C= δM\|w\|^2 _k=s _γ( _γ(s)+T) _ _γ( _γ(s)+T),k^2 to obtain that ℙ(sups≤i≤Λγ(λγ(s)+T)⟨w,∑k=siρΛγ(λγ(s)+T),kυk+1⟩>δ)≤exp(−δ22M‖w‖2∑k=sΛγ(λγ(s)+T)ρΛγ(λγ(s)+T),k2).P ( _s≤ i≤ _γ( _γ(s)+T) w, _k=s^i _ _γ( _γ(s)+T),k _k+1 >δ )≤ (- δ^22M\|w\|^2 _k=s _γ( _γ(s)+T) _ _γ( _γ(s)+T),k^2 ). From the arbitrariness of w and the fact that ρΛγ(λγ(s)+T),k≤γk _ _γ( _γ(s)+T),k≤ _k, we can further deduce that ℙ(sups≤i≤Λγ(λγ(s)+T)‖∑k=siρΛγ(λγ(s)+T),kυk+1‖>δ)≤exp(−δ22M∑k=sΛγ(λγ(s)+T)γk2)≤exp(−δ22MTγk′),P ( _s≤ i≤ _γ( _γ(s)+T) \| _k=s^i _ _γ( _γ(s)+T),k _k+1 \|>δ )≤ (- δ^22M _k=s _γ( _γ(s)+T) _k^2 )≤ (- δ^22MT _k ), which holds for some k′∈[s,Λγ(λγ(s)+T)]k ∈[s, _γ( _γ(s)+T)]. Let n0:=infj∈ℕ:Λγ(jT)>Kn_0:= \j : _γ(jT)>K\. For each j≥n0j≥ n_0, there exists kj∈[Λγ(jT),Λγ((j+1)T)]k_j∈[ _γ(jT), _γ((j+1)T)] such that ℙ(supΛγ(jT)≤i≤Λγ(jT+T)‖∑k=Λγ(jT)iρΛγ(λγ(s)+T),kυk+1‖>δ)≤exp(−δ22MTγkj).P ( _ _γ(jT)≤ i≤ _γ(jT+T) \| _k= _γ(jT)^i _ _γ( _γ(s)+T),k _k+1 \|>δ )≤ (- δ^22MT _k_j ). Therefore, ∑j=n0∞ℙ(supΛγ(jT)≤i≤Λγ(jT+T)‖∑k=Λγ(jT)iρΛγ(λγ(s)+T),kυk+1‖>δ)≤∑j=n0∞exp(−δ22MTγkj)<+∞. _j=n_0^∞P ( _ _γ(jT)≤ i≤ _γ(jT+T) \| _k= _γ(jT)^i _ _γ( _γ(s)+T),k _k+1 \|>δ )≤ _j=n_0^∞ (- δ^22MT _k_j )<+∞. (6.4) The last inequality folows from the fact that limk→+∞γklog(k)=0 _k→+∞ _k (k)=0. Let ℰjE_j denote the event supΛγ(jT)≤i≤Λγ(jT+T)‖∑k=Λγ(jT)iρΛγ(λγ(s)+T),kυk+1‖>δ. \ _ _γ(jT)≤ i≤ _γ(jT+T) \| _k= _γ(jT)^i _ _γ( _γ(s)+T),k _k+1 \|>δ \. By the Borel-Cantelli lemma and (6.4), we can conclude that ℙ(⋂j=1+∞⋃l=j+∞ℰl)=0P ( _j=1^+∞ _l=j^+∞E_l )=0, which indicates that limj→+∞supΛγ(jT)≤i≤Λγ(jT+T)‖∑k=Λγ(jT)iρΛγ(jT+T),kυk+1‖=0. _j→+∞ _ _γ(jT)≤ i≤ _γ(jT+T) \| _k= _γ(jT)^i _ _γ(jT+T),k _k+1 \|=0. (6.5) For any j≥n0j≥ n_0, zΛγ(jT+T)=(∏k=Λγ(jT)Λγ(jT+T)(1−aγk))zΛγ(jT)+∑k=Λγ(jT)Λγ(jT+T)ρΛγ(jT+T),kυk+1.z_ _γ(jT+T)= ( _k= _γ(jT) _γ(jT+T)(1-a _k) )z_ _γ(jT)+ _k= _γ(jT) _γ(jT+T) _ _γ(jT+T),k _k+1. Since ∏k=Λγ(jT)Λγ(jT+T)(1−aγk)≤∏k=Λγ(jT)Λγ(jT+T)exp(−aγk)≤exp(−aT), _k= _γ(jT) _γ(jT+T)(1-a _k)≤ _k= _γ(jT) _γ(jT+T) (-a _k)≤ (-aT), we attain that ‖zΛγ(jT+T)‖≤exp(−aT)‖zΛγ(jT)‖+‖∑k=Λγ(jT)Λγ(jT+T)ρΛγ(jT+T),kυk+1‖. \|z_ _γ(jT+T) \|≤ (-aT) \|z_ _γ(jT) \|+ \| _k= _γ(jT) _γ(jT+T) _ _γ(jT+T),k _k+1 \|. (6.6) Together with (6.5), we can conclude that limj→+∞‖zΛγ(jT+T)‖=0 _j→+∞\|z_ _γ(jT+T)\|=0. Finally, for any i such that Λγ(jT)<i≤Λγ(jT+T) _γ(jT)<i≤ _γ(jT+T), it holds that ‖zΛγ(jT+T)‖ \|z_ _γ(jT+T)\| =‖(∏k=iΛγ(jT+T)(1−aγk))zi+∑k=iΛγ(jT+T)ρΛγ(jT+T),kυk+1‖ = \| ( _k=i _γ(jT+T)(1-a _k) )z_i+ _k=i _γ(jT+T) _ _γ(jT+T),k _k+1 \| ≥exp(−2aT)‖zi‖−‖∑k=iΛγ(jT+T)ρΛγ(jT+T),kυk+1‖ ≥ (-2aT)\|z_i\|- \| _k=i _γ(jT+T) _ _γ(jT+T),k _k+1 \| ≥exp(−2aT)‖zi‖−‖∑k=Λγ(jT)Λγ(jT+T)ρΛγ(jT+T),kυk+1‖−‖∑k=Λγ(jT)iρΛγ(jT+T),kυk+1‖ ≥ (-2aT)\|z_i\|- \| _k= _γ(jT) _γ(jT+T) _ _γ(jT+T),k _k+1 \|- \| _k= _γ(jT)^i _ _γ(jT+T),k _k+1 \| ≥exp(−2aT)‖zi‖−2supΛγ(jT)≤i≤Λγ(jT+T)‖∑k=Λγ(jT)iρΛγ(s)+T,kυk+1‖, ≥ (-2aT)\|z_i\|-2 _ _γ(jT)≤ i≤ _γ(jT+T) \| _k= _γ(jT)^i _ _γ(s)+T,k _k+1 \|, where the first inequality follows from 1−aγk≥exp(−2aγk)1-a _k≥ (-2a _k), when k≥Kk≥ K, and from the fact that ∑k=Λγ(jT)Λγ(jT+T)γk≤T _k= _γ(jT) _γ(jT+T) _k≤ T. As a result, we have supΛγ(jT)≤i≤Λγ(jT+T)‖zi‖≤exp(2aT)(‖zΛγ(jT+T)‖+2supΛγ(jT)≤i≤Λγ(jT+T)‖∑k=Λγ(jT)iρΛγ(s)+T,kυk+1‖). _ _γ(jT)≤ i≤ _γ(jT+T)\|z_i\|≤ (2aT) (\|z_ _γ(jT+T)\|+2 _ _γ(jT)≤ i≤ _γ(jT+T) \| _k= _γ(jT)^i _ _γ(s)+T,k _k+1 \| ). (6.7) Combining (6.5), (6.6), and (6.7) together, we achieve that lim supk→+∞‖zk‖≤limj→+∞supΛγ(jT)≤i≤Λγ(jT+T)‖zi‖=0. _k→+∞\|z_k\|≤ _j→+∞ _ _γ(jT)≤ i≤ _γ(jT+T)\|z_i\|=0. This completes the proof. ∎ Proof of Lemma 3.13 Proof. Due to the uniform boundedness of martingale difference sequence υ^k+1\ _k+1\, it follows that υ^k+1\ _k+1\ is sub-Gaussian. That is, there exists M>0M>0 such that for any ∈ℝn y ^n, [exp(⟨,υ^k+1⟩)|ℱk]≤exp(M2‖2).E [ ( y, _k+1 )|F_k ]≤ ( M2 \| y \|^2 ). For any ∈ℝn y ^n and C>0C>0, define Yi+1:=exp[⟨C,∑k=siθkυ^k+1⟩−MC22∑k=siθk2‖2].Y_i+1:= [ C y, _k=s^i _k _k+1 - MC^22 _k=s^i _k^2 \| y \|^2 ]. Then, for any i≥0i≥ 0, we have [Yi+1|ℱi]≤YiE[Y_i+1|F_i]≤ Y_i. Hence, for any δ>0δ>0 and any C>0C>0, it holds that ℙ(sups≤i≤Λη(λη(s)+T)⟨,∑k=siθkυ^k+1⟩>δ)=ℙ(sups≤i≤Λη(λη(s)+T)⟨C,∑k=siθkυ^k+1⟩>Cδ) ( _s≤ i≤ _η( _η(s)+T) y, _k=s^i _k _k+1 >δ )=P ( _s≤ i≤ _η( _η(s)+T) C y, _k=s^i _k _k+1 >Cδ ) ≤ ≤ ℙ(sups≤i≤Λη(λη(s)+T)Yi>exp(Cδ−MC22∑k=sΛη(λη(s)+T)θk2‖2)) ( _s≤ i≤ _η( _η(s)+T)Y_i> (Cδ- MC^22 _k=s _η( _η(s)+T) _k^2 \| y \|^2 ) ) ≤ ≤ exp((M2‖2∑k=sΛη(λη(s)+T)θk2)C2−Cδ), ( ( M2 \| y \|^2 _k=s _η( _η(s)+T) _k^2 )C^2-Cδ ), where the last inequality follows from Doob’s maximal inequality and the fact that [Ys+1]≤1E[Y_s+1]≤ 1. Then, by choosing C=δM‖2∑k=sΛη(λη(s)+T)θk2C= δM \| y \|^2 _k=s _η( _η(s)+T) _k^2, we obtain ℙ(sups≤i≤Λη(λη(s)+T)⟨,∑k=siθkυ^k+1⟩>δ)≤exp(−δ22M‖2∑k=sΛη(λη(s)+T)θk2).P ( _s≤ i≤ _η( _η(s)+T) y, _k=s^i _k _k+1 >δ )≤ ( -δ^22M \| y \|^2 _k=s _η( _η(s)+T) _k^2 ). By taking =∑k=siθkυ^k+1‖∑k=siθkυ^k+1‖ y= _k=s^i _k _k+1 \| _k=s^i _k _k+1 \|, we deduce ℙ(sups≤i≤Λη(λη(s)+T)‖∑k=siθkυ^k+1‖>δ)≤exp(−δ22M∑k=sΛη(λη(s)+T)θk2),P ( _s≤ i≤ _η( _η(s)+T) \| _k=s^i _k _k+1 \|>δ )≤ ( -δ^22M _k=s _η( _η(s)+T) _k^2 ), We claim that ∑k=sΛη(λη(s)+T)θk2≤Tθk′2ηk′ _k=s _η( _η(s)+T) _k^2≤ T _k ^2 _k for some k′∈[s,Λη(λη(s)+T)]k ∈[s, _η( _η(s)+T)]. Suppose for contradiction that it fails. Then, for all k∈[s,Λη(λη(s)+T)]k∈[s, _η( _η(s)+T)], ηk∑k=sΛη(λη(s)+T)θk2>Tθk2. _k _k=s _η( _η(s)+T) _k^2>T _k^2. Summing over k gives ∑k=sΛη(λη(s)+T)ηk∑k=sΛη(λη(s)+T)θk2>T∑k=sΛη(λη(s)+T)θk2, _k=s _η( _η(s)+T) _k _k=s _η( _η(s)+T) _k^2>T _k=s _η( _η(s)+T) _k^2, which contradicts the definition of λη _η and Λη _η, since T≥∑k=sΛη(λη(s)+T)ηkT≥ _k=s _η( _η(s)+T) _k. Hence the claim holds. Consequently, there exists k′∈[s,Λη(λη(s)+T)]k ∈[s, _η( _η(s)+T)] such that ℙ(sups≤i≤Λη(λη(s)+T)‖∑k=siθkυ^k+1‖>δ)≤exp(−δ22MTθk′2ηk′).P ( _s≤ i≤ _η( _η(s)+T) \| _k=s^i _k _k+1 \|>δ )≤ ( -δ^22MT _k ^2 _k ). For each j≥0j≥ 0, there exists kj∈[Λ(jT),Λ((j+1)T)]k_j∈[ (jT), ((j+1)T)], such that ∑j=0+∞ℙ(supΛη(jT)≤i≤Λη(jT+T)‖∑k=siθkυ^k+1‖≥δ) _j=0^+∞P ( _ _η(jT)≤ i≤ _η(jT+T) \| _k=s^i _k _k+1 \|≥δ ) ≤ ≤ ∑j=0+∞exp(−δ22MTηkj−1θkj2)≤∑k=0+∞2exp(−δ22MTθk2ηk)<+∞. _j=0^+∞ ( -δ^22MT _k_j^-1 _k_j^2 )≤ _k=0^+∞2 ( -δ^22MT _k^2 _k )<+∞. Here the last inequality holds from the fact that limk→+∞θk2ηklog(k)=0 _k→+∞ _k^2 _k (k)=0. According to Borel-Cantelli Theorem, we obtain that limj→+∞supΛη(jT)≤i≤Λη(jT+T)‖∑k=Λη(jT)iθkυ^k+1‖=0. _j→+∞ _ _η(jT)≤ i≤ _η(jT+T) \| _k= _η(jT)^i _k _k+1 \|=0. Finally, for any jT≤s≤jT+TjT≤ s≤ jT+T, sups≤i≤Λη(λη(s)+T)‖∑k=Λη(jT)iθkυ^k+1‖ _s≤ i≤ _η( _η(s)+T) \| _k= _η(jT)^i _k _k+1 \| ≤ ≤ 2supΛη(jT)≤i≤Λη(jT+T)‖∑k=Λη(jT)iθkυ^k+1‖+supΛη((j+1)T)≤i≤Λη((j+2)T)‖∑k=Λη(jT+T)iθkυ^k+1‖. 2 _ _η(jT)≤ i≤ _η(jT+T) \| _k= _η(jT)^i _k _k+1 \|+ _ _η((j+1)T)≤ i≤ _η((j+2)T) \| _k= _η(jT+T)^i _k _k+1 \|. Then we achieve that lims→+∞sups≤i≤Λη(λη(s)+T)‖∑k=siθkυ^k+1‖=0, _s→+∞ _s≤ i≤ _η( _η(s)+T) \| _k=s^i _k _k+1 \|=0, which completes the proof. ∎