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 \(\mathtt{G} = (\mathtt{V}, \mathtt{E})\), \[\refstepcounter{equation} \label{Prob_DOP} \begin{align} \min_{{\boldsymbol{x}}_1, {\boldsymbol{x}}_2, \ldots, {\boldsymbol{x}}_d \in \mathbb{R}^n} & \quad \sum_{i=1}^d \mathbb{E}_{\zeta_{i} \sim \mathcal{P}_{i}} F_{i}({\boldsymbol{x}}_i, \zeta_{i}), \\ \text{s.t.} & \quad {\boldsymbol{x}}_{i}={\boldsymbol{x}}_{j}, \quad \forall(i, j) \in \mathtt{E} . \end{align}\tag{1}\] Here, the node set \(\mathtt{V}= \{1, \ldots, d\}\) stands for the collection of agents, and the edge set \(\mathtt{E}\) represents the communication links between agents. Each agent \(i\) is associated with a local cost function \(F_{i}(\cdot, \zeta_{i})\) and a local data distribution \(\mathcal{P}_{i}\). The expectation-form cost function is denoted by \(f_i({\boldsymbol{x}}) := \mathbb{E}_{\zeta_{i} \sim \mathcal{P}_{i}} F_{i}({\boldsymbol{x}}, \zeta_{i}),\) which is assumed to be locally Lipschitz continuous, nonconvex and possibly nonsmooth.

The optimization problem 1 has wide applications in wireless edge computing [1]–[3], multi-agent target seeking [4], [5], privacy-preserving systems [6], [7] and distributed learning [8], [9]. 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 [10]–[13] and sparsification operators [14]–[20], 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 [21], S-NEAR-DGD [22], QDSG [23], [24] and IC-GT [25]. 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 [21] proves that the expected deviation from the optimal solution gradually vanishes. S-NEAR-DGD [22] and IC-GT [25] show that, with fixed step-sizes, the iterates converge linearly in expectation to a neighborhood of the optimum. QDSG [23], [24] 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 [26] 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 [27]–[31] 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 [27]. Moreover, SPARQ-SGD [33] is an event-triggered variant of CHOCO-SGD that reduces the number of communication rounds. SQuARM-SGD [28] can be interpreted as CHOCO-SGD with local-update Nesterov momentum, which guarantees ergodic convergence in expectation for smooth objective functions. C-GT [30] and BEER [29] incorporate gradient-tracking into decentralized SGD with difference-based contractive compression to handle heterogeneity across multi-agents, and [34] adopts a compression technique together with a momentum-based adaptive learning rate to accelerate empirical convergence. DoCoM [31] and MoTEF [35] integrate communication compression with momentum tracking and error feedback, showing improved theoretical and empirical performance under arbitrary data heterogeneity. DEF-ATC [36] 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, [37] 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, [38] proposes DP-CSGP, which couples compressed stochastic gradient push with node-level \((\varepsilon,\delta)\)-differential privacy guarantees and provides utility bounds for general smooth nonconvex objectives.

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 [39] (hereafter referred to as non‑Clarke‑regular functions). However, the existing convergence analyses in the above-mentioned works predominantly assume that each \(f_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 [40], [41] 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 [42]), the outputs of the AD algorithm may not belong to the Clarke subdifferential [39] of such a loss function. To tackle this issue, [43] 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 [43]–[49] leverage the ordinary differential equation (ODE) approach [50]–[53] 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, \[\refstepcounter{equation} \label{Eq_Framework} {\boldsymbol{Z}}_{k+1} = \underbrace{(1-\theta_k) {\boldsymbol{Z}}_k + \theta_k {\boldsymbol{Z}}_k {\boldsymbol{W}} + \theta_{k} {\boldsymbol{E}}_{k+1}({\boldsymbol{W}}-\Sigma)}_{\text{Local aggregation with compression}} \underbrace{ - \eta_k ({\boldsymbol{H}}_k + \Xi_{k+1})}_{\text{descent step}}.\tag{2}\] Here, \({\boldsymbol{Z}}_k = [{\boldsymbol{z}}_{1,k}, \ldots, {\boldsymbol{z}}_{d,k}] \in \mathbb{R}^{m\times d}\) denotes the collection of local variables (including the local variables \(\{{\boldsymbol{x}}_{i, k}\}_{i\in [d]}\) and auxiliary variables corresponding to specific subgradient methods), \({\boldsymbol{W}}\) is a mixing matrix, \({\boldsymbol{H}}_k \in \mathbb{R}^{m\times d}\) represents the collection of noiseless update directions of all agents, and \(\Sigma\) is a diagonal matrix which conforms to the mechanism of communication compression. \(\{{\boldsymbol{E}}_{k+1}\}\) and \(\{\Xi_{k+1}\}\) are two sequences of random variables defined on probability space \((\Omega, \mathcal{F}, \mathbb{P})\), which correspond to the compression error and evaluation noise on \({\boldsymbol{H}}_{k}\), respectively. Furthermore, \(\{\eta_k\}\) and \(\{\theta_{k} \}\) are two-timescale step-sizes corresponding to the descent step and the local average. Typically, they are required to satisfy \(\eta_{k}/\theta_{k}\to 0\), as \(k\) goes infinity.

In 2 , the \(i\)-th term of \({\boldsymbol{Z}}_k {\boldsymbol{W}} + {\boldsymbol{E}}_{k+1}({\boldsymbol{W}}-\Sigma)\) 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 \(\theta_k\)-reallocation step together with a descent step is incorporated to produce the next iterate \({\boldsymbol{Z}}_{k+1}\).

The flexibility in choosing \({\boldsymbol{E}}_{k+1}\) and \({\boldsymbol{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 2 by choosing different \({\boldsymbol{E}}_{k+1}\) and corresponding \(\Sigma\). We first introduce the following sub-framework for developing decentralized stochastic subgradient-type methods with unbiased compression, \[\refstepcounter{equation} \label{eq:uncom} \left\{ \begin{align} {\boldsymbol{Z}}_{k+1} & = (1-\theta_k) {\boldsymbol{Z}}_k + \theta_k {\boldsymbol{Z}}_k {\boldsymbol{W}} + \theta_{k} {\boldsymbol{E}}_{k+1}({\boldsymbol{W}}-\mathrm{Diag}({\boldsymbol{W}})) - \eta_k ({\boldsymbol{H}}_k + \Xi_{k+1}), \\ {\boldsymbol{E}}_{k+1} & = C({\boldsymbol{Z}}_{k}, {\boldsymbol{\omega}}_{k+1})-{\boldsymbol{Z}}_{k} := [C({\boldsymbol{z}}_{1,k}, {\boldsymbol{\omega}}_{k+1}) - {\boldsymbol{z}}_{1,k}, \ldots, C({\boldsymbol{z}}_{d,k}, {\boldsymbol{\omega}}_{k+1})-{\boldsymbol{z}}_{d,k}].\\ \end{align} \right.\tag{3}\] Here, \(C(\cdot, {\boldsymbol{\omega}}): \mathbb{R}^m \times \Omega \to \mathbb{R}^m\) is an unbiased compression operator, i.e. \(\mathbb{E}_{{\boldsymbol{\omega}}}[C({\boldsymbol{x}}, {\boldsymbol{\omega}})]={\boldsymbol{x}}\). \(\{{\boldsymbol{E}}_{k+1}\}\) is a martingale difference sequence with respect to \(\mathcal{F}_{k}= \sigma(\{{\boldsymbol{Z}}_{i}: i\leq k\})\). As shown later in Section 4, with specific choices of \({\boldsymbol{H}}_{k}\), 3 yields variants of several decentralized stochastic subgradient-type methods with unbiased compression. For instance, as we set \({\boldsymbol{Z}}_{k}={\boldsymbol{X}}_{k}\), \({\boldsymbol{H}}_{k}+ \Xi_{k+1} \in [D_{F_1(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k}), \ldots,\) \(D_{F_d(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k})]\), and \(C\) to be a randomized quantization operator \(Q\), 3 reduces exactly to the nonsmooth version of QDGD [21], a decentralized SGD method with quantization: \[\refstepcounter{equation} \label{unb:dsgd0} {\boldsymbol{x}}_{i,k+1} \in (1-\theta_k +\theta_k {\boldsymbol{W}}(i,i)){\boldsymbol{x}}_{i,k} + \theta_k \sum_{j\in \mathcal{N}_i}{\boldsymbol{W}}(i,j) Q({\boldsymbol{x}}_{j,k}, {\boldsymbol{\omega}}_{k+1}) - \eta_k D_{F_i(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k}),\tag{4}\] where \(\mathcal{N}_{i}\) denotes the neighbors of agent \(i\), \(D_{F_i(\cdot,\zeta_{i,k+1})}\) is a conservative field for function \(F_i(\cdot,\zeta_{i,k+1})\) that describes how \(F_i(\cdot,\zeta_{i,k+1})\) is differentiated.

Additionally, based on 2 , we introduce another sub-framework for contractive compression,

\[\refstepcounter{equation} \label{eq:contractive} \left\{ \begin{align} {\boldsymbol{Z}}_{k+1} & = (1-\theta_k) {\boldsymbol{Z}}_k + \theta_k {\boldsymbol{Z}}_k {\boldsymbol{W}} + \theta_{k} {\boldsymbol{E}}_{k+1}({\boldsymbol{W}}-{\boldsymbol{I}}_{d}) - \eta_k ({\boldsymbol{H}}_k + \Xi_{k+1}),\\ {\boldsymbol{E}}_{k+1} & = \hat{\boldsymbol{Z}}_{k+1} -{\boldsymbol{Z}}_k,\\ \hat{\boldsymbol{Z}}_{k+1} & =\hat{{\boldsymbol{Z}}}_{k} + \gamma_k C({\boldsymbol{Z}}_{k}-\hat{{\boldsymbol{Z}}}_{k}, {\boldsymbol{\omega}}_{k+1}).\\ \end{align} \right.\tag{5}\] Here, \(C(\cdot, {\boldsymbol{\omega}}): \mathbb{R}^m \times \Omega \to \mathbb{R}^m\) is a contractive compression operator, i.e. \(\mathbb{E}_{{\boldsymbol{\omega}}}[\|C(\boldsymbol{x}, {\boldsymbol{\omega}})-\boldsymbol{x}\|^2] \leq(1-\alpha)\|\boldsymbol{x}\|^2, \alpha \in (0,1].\) \(\hat{\boldsymbol{Z}}_{k+1}= [\hat{\boldsymbol{z}}_{1,k+1}, \ldots, \hat{\boldsymbol{z}}_{d,k+1}]\) is the collection of local copies, where each \(\hat{\boldsymbol{z}}_{i,k+1}\) is an inexact copy of \({\boldsymbol{z}}_{i, k}\) held by the neighbors of agent \(i\). \(\{\gamma_k\}\) is a diminishing sequence, and \(-{\boldsymbol{E}}_{k+1}\) is essentially an compression error term that captures the discrepancy between the desired difference \({\boldsymbol{Z}}_{k}- \hat{\boldsymbol{Z}}_k\) and the compressed term \(\gamma_k C({\boldsymbol{Z}}_{k}-\hat{{\boldsymbol{Z}}}_{k}, {\boldsymbol{\omega}}_{k+1})\). The update formula of \({\boldsymbol{E}}_{k}\) and \(\hat{\boldsymbol{Z}}_{k}\) can be further illustrated by the following error-compensation mechanism \[\left\{ \begin{align} \Delta_k ~& = {\boldsymbol{Z}}_{k}-{\boldsymbol{Z}}_{k-1}+(-{\boldsymbol{E}}_{k}),\triangleleft \text{ error-compensation} \\ \hat{\boldsymbol{Z}}_{k+1} ~& =\hat{{\boldsymbol{Z}}}_{k} + \gamma_k C(\Delta_k, {\boldsymbol{\omega}}_{k+1}),\triangleleft \text{ compression and update} \\ -{\boldsymbol{E}}_{k+1} ~& = \Delta_k - \gamma_k C(\Delta_k, {\boldsymbol{\omega}}_{k+1}).\triangleleft \text{ compression error} \\ \end{align} \right.\] Similarly, as demonstrated in Section 4, with different choices of \({\boldsymbol{H}}_{k}\), 5 corresponds to various decentralized stochastic subgradient-type methods with contractive compression. For instance, when we choose \({\boldsymbol{Z}}_{k}={\boldsymbol{X}}_{k}\), \({\boldsymbol{H}}_{k}+ \Xi_{k+1} \in [D_{F_1(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k}), \ldots, D_{F_d(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k})]\), 5 is a nonsmooth version of CHOCO-SGD [27], [32]: \[\refstepcounter{equation} \label{con:dsgd0} \left\{ \begin{align} \hat{{\boldsymbol{x}}}_{j, k+1} & = \hat{{\boldsymbol{x}}}_{j, k} + \gamma_k C({\boldsymbol{x}}_{j, k}-\hat{{\boldsymbol{x}}}_{j, k}, {\boldsymbol{\omega}}_{k+1}), \quad j \in \mathcal{N}_{i}, \\ {\boldsymbol{x}}_{i, k+1} & \in {\boldsymbol{x}}_{i,k} + \theta_{k} \sum_{j\in \mathcal{N}_{i}} {\boldsymbol{W}}(i,j) (\hat{\boldsymbol{x}}_{j, k+1} - \hat{\boldsymbol{x}}_{i, k+1}) -\eta_{k}D_{F_i(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k}).\\ \end{align} \right.\tag{6}\]

1.2 Contributions↩︎

The main contributions of our paper are three-fold.

• Unification

  Our framework 2 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 2 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 [21], CHOCO-SGD [32], BEER [29] and C-GT [30].

• Convergence

  We establish the global convergence of 2 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 2 , 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 \(\langle\cdot, \cdot\rangle\) represents the standard inner product, while \(\|\cdot\|\) represents the \(\ell_2\)-norm of a vector or the spectral norm of a matrix. \(\|\cdot\|_{1}\) stands for the \(\ell_1\)-norm of a vector, and \(\|\cdot\|_{\mathrm{F}}\) refers to the Frobenius norm of a matrix. Let \(\mathbb{B}({\boldsymbol{x}}, \delta):=\left\{\tilde{{\boldsymbol{x}}} \in \mathbb{R}^n:\|\tilde{{\boldsymbol{x}}}-{\boldsymbol{x}}\|^2\leq \delta^2\right\}\) denote the ball centered at \({\boldsymbol{x}}\) with radius \(\delta\). For a given set \(\mathcal{Y}, \operatorname{dist}({\boldsymbol{x}}, \mathcal{Y}):= \min_{y \in \mathcal{Y}}\|{\boldsymbol{x}}-{\boldsymbol{y}}\|\) represents the distance between \({\boldsymbol{x}}\) and a set \(\mathcal{Y}\). The convex hull and \(d\)-fold Cartesian product of \(\mathcal{Y}\) is denoted by \(\mathrm{conv}\,\mathcal{Y}\) and \(\mathcal{Y}^d\), respectively. The notation \(\otimes\) stands for the Kronecker product. The symbol \(\odot\) denotes the Hadamard product, \(\Delta_m:= \{(\lambda_0, \ldots, \lambda_m): \lambda_i \geq 0, \sum_{i=0}^{m}\lambda_i =1\}\) stands for the simplex of dimension \(m\).

For any positive sequence \(\left\{\eta_k\right\}\), let \(\lambda_{\eta}(0):=0, \lambda_{\eta}(i):=\sum_{k=0}^{i-1} \eta_k\), and \(\Lambda_{\eta}(t):=\sup \left\{k \in\mathbb{N}:\right.\) \(\left. t \geq \lambda_{\eta}(k)\right\}.\) More explicitly, \(\Lambda_{\eta}(t)=p\), if \(\lambda_{\eta}(p) \leq t<\lambda_{\eta}(p+1)\). The set-valued mapping sign : \(\mathbb{R}^n \rightrightarrows \mathbb{R}^n\) is defined by \[(\operatorname{sign}({\boldsymbol{x}}))_i= \begin{cases}\{-1\}, & {\boldsymbol{x}}_i<0;\\ {[-1,1],} & {\boldsymbol{x}}_i=0;\\ \{1\}, & {\boldsymbol{x}}_i>0.\end{cases}\]

For any \(N>0,\) let \([N]:=\{1, \ldots, N\}\). The notation \(\mathbb{R}_{+}\) represents the set of all nonnegative real numbers. Notations \({\boldsymbol{1}}_{d}\) and \({\boldsymbol{e}}_{i}\) stand for a vector of all \(1\)’s and \([0, \ldots, 1, \ldots, 0]^{\top}\), where \(1\) is the \(i\)-th component. For two integers \(i\) and \(j\), \(i \land j:= \min\{i,j\}\). Let \((\Omega, \mathcal{F}, \mathbb{P})\) denote the probability space. We use \(\sigma({\boldsymbol{X}})\) to denote the sigma-algebra generated by the random variable \({\boldsymbol{X}}\).

We say that \(\left\{\mathcal{F}_k\right\}_{k \in \mathbb{N}}\) is a filtration if \(\left\{\mathcal{F}_k\right\}\) is a collection of \(\sigma\)-algebras satisfying \(\mathcal{F}_0\subseteq \mathcal{F}_1\subseteq \cdots \subseteq \mathcal{F}_{\infty} \subseteq \mathcal{F}\). A sequence of random variables \(\{\xi_{k}\}\) is a martingale with respect to a filtration \(\{\mathcal{F}_{k}\}\), if \(\{\xi_{k}\}\) is adapted to the filtration \(\{\mathcal{F}_{k}\}\) and \(\mathbb{E}[\xi_{k+1} | \mathcal{F}_{k} ] = \xi_{k}\), for all \(k \in \mathbb{N}\); \(\{\xi_{k}\}\) is a supermartingale with respect to \({\mathcal{F}_{k}}\), if \({\xi_{k}}\) is adapted to \(\{\mathcal{F}_{k}\}\) and \(\mathbb{E}[\xi_{k+1} | \mathcal{F}_{k}] \leq \xi_{k}\), for all \(k\in\mathbb{N}\). Moreover, a sequence of random variables \(\{\xi_{k}\}\) is a martingale difference sequence with respect to \(\{\mathcal{F}_{k}\}\), if \(\{\xi_{k}\}\) is adapted to the filtration \(\{\mathcal{F}_{k}\}\) and \(\mathbb{E}[\xi_{k+1} | \mathcal{F}_{k} ] = 0\) holds for all \(k\in \mathbb{N}\).

In addition, we denote the set of agent \(i\)’s neighbors by \(\mathcal{N}_{i}\), and \(\mathcal{N}_{i}^{+}:= \mathcal{N}_{i} \cup \{i\}\). We define the summation function \(f\) of 1 as \[\label{Eq95defin95f} f({\boldsymbol{x}}) := \frac{1}{d} \sum_{i = 1}^d f_i({\boldsymbol{x}}).\tag{7}\]

2.2 Mixing matrix↩︎

The mixing matrix \({\boldsymbol{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 \({\boldsymbol{W}}\) is defined to satisfy the following properties, which are standard in the literature.

Given a graph \(\mathtt{G}\), various approaches can be used to select its corresponding mixing matrix, such as the Laplacian-based constant edge-weight matrix [55] and the Metropolis constant edge-weight matrix [56]. For further details on choosing the mixing matrix, we refer the reader to [57], [58].

Proposition 2 is a direct corollary of [59], which characterize the spectral property of a mixing matrix \({\boldsymbol{W}}\).

2.3 Set-valued mapping, Clarke subdifferential and conservative field↩︎

A set-valued mapping \(\Phi: \mathbb{R}^{n} \rightrightarrows \mathbb{R}^m\) is a mapping from \(\mathbb{R}^n\) into the set of subsets of \(\mathbb{R}^m\). The graph of \(\Phi\) is defined by \[\operatorname{graph} \Phi = \{ ({\boldsymbol{x}},{\boldsymbol{z}}) \mid {\boldsymbol{x}}\in \mathbb{R}^n, {\boldsymbol{z}}\in \Phi({\boldsymbol{x}})\}.\] \(\Phi\) is said to have a closed graph (or be graph-closed), if \(\operatorname{graph} \Phi\) is a closed subset of \(\mathbb{R}^n\times \mathbb{R}^m\). It is locally bounded, if for any \({\boldsymbol{x}}\in \mathbb{R}^n\), there exists a neighborhood \(U_{{\boldsymbol{x}}}\) of \({\boldsymbol{x}}\) such that \[\sup_{{\boldsymbol{z}}\in \Phi({\boldsymbol{y}}), {\boldsymbol{y}}\in U_{{\boldsymbol{x}}}} \| {\boldsymbol{z}}\|< + \infty.\] In addition, \(\Phi\) is convex-valued (resp. compact-valued), if \(\Phi({\boldsymbol{x}})\) is a convex (resp. compact) subset of \(\mathbb{R}^m\) for any \({\boldsymbol{x}} \in \mathbb{R}^n\). For \(\delta>0\), we define \[\Phi^\delta({\boldsymbol{x}}):=\bigcup_{{\boldsymbol{y}} \in \mathbb{B}({\boldsymbol{x}}, \delta)}(\Phi({\boldsymbol{y}})+\mathbb{B}({\boldsymbol{0}}, \delta))\] where “+” denotes the Minkowski sum.

Notice that \(\partial 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.

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.

It is worth noting that any conservative field is locally bounded [43]. We now introduce the definition of the path-differentiable function corresponding to a conservative field.

Proposition 7 reveals that \(\partial 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 \(D_f({\boldsymbol{x}})\) is convex-valued, the condition \({\boldsymbol{0}} \in \partial f({\boldsymbol{x}})\) implies that \(0 \in D_f({\boldsymbol{x}})\).

The following proposition shows that the definability of both \(f\) and its conservative field \(D_f\) implies the nonsmooth Morse–Sard property [62].

Finally, based on the concept of a conservative field, we introduce the definition of critical points for the optimization problem 1 .

2.4 Stochastic approximation and differential inclusion↩︎

ODE approaches [44], [50], [53], [63] 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.

Consider iterates \(\{{\boldsymbol{x}}_{k}\}\) generated by the following update scheme: \[\label{Eq95stable95random} {\boldsymbol{x}}_{k+1} \in {\boldsymbol{x}}_k - c\eta_k\left( \Phi^{\delta_k}({\boldsymbol{x}}_k) + \upsilon_{k+1} \right),\tag{8}\] where \(\{\eta_k\}\) is a non-summable positive sequence of step-sizes, \(\{\delta_{k}\}\) is a nonnegative sequence, and \(\upsilon_{k+1}\) is a random noise term added when evaluating \(\Phi({\boldsymbol{x}}_k)\). The continuous-time interpolated process \(u: \mathbb{R}_{+} \rightarrow \mathbb{R}^n\) induced by 8 is given by \[u(\lambda_{\eta}(k) +s) = {\boldsymbol{x}}_{k} + \frac{{\boldsymbol{x}}_{k+1}-{\boldsymbol{x}}_k}{\eta_{k}} s, \quad s \in [0,\eta_{k}).\] where \(\lambda_{\eta}(0):=0\) and \(\lambda_{\eta}(k):= \sum_{i=0}^{k-1} \eta_{i}\), for \(k \geq 1\).

The following Lemma 14 plays an important role in demonstrating the convergence properties of 8 , integrating results from [45], [50]. In their proof, they show that the interpolated process above is a perturbed solution of differential inclusion ?? . For further details, interested readers are referred to [51] and [50].

3 Convergence Guarantees for General Framework↩︎

In this section, we establish the global asymptotic convergence properties for 2 . Section 3.1 discuss about the relationship between \({{\boldsymbol{Z}}_k}\) and \({\boldsymbol{H}}_{k}\) in the framework 2 , and introduces basic assumptions for 2 . 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 \({\boldsymbol{H}}_{k}\) is \[{\boldsymbol{H}}_{k} \in [\Phi_{1}({\boldsymbol{z}}_{1,k}), \ldots, \Phi_{d}({\boldsymbol{z}}_{d,k})],\] where each \(\Phi_{i}\) is a set-valued mapping, such as the Clarke subdifferential \(\partial f_i\) or a conservative field \(D_{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 \(\{\Phi_i({\boldsymbol{z}})\}_{i=1}^{d}\) that possess a “Lyapunov property” to constrain \({\boldsymbol{H}}_{k}\). Furthermore, we specify the form of the evaluation noise \(\Xi_{k+1}\) and the step-sizes used in framework 2 .

Assumption 15-(1) uses a family of set-valued mappings \(\{\Phi_{i}\}\) to characterize the relationship between the averaged update direction \(\frac{1}{d}{\boldsymbol{H}}_k {\boldsymbol{1}}_d\) and local variables \(\{{\boldsymbol{z}}_{i,k}\}_{i\in [d]}\). Note that we do not require each column of \({\boldsymbol{H}}_{k}\) to belong to \(\Phi_i({\boldsymbol{z}}_{i,k})\), but instead merely restrict the averaged update direction to lie in the convex hull of the Minkowski sum of \(\epsilon_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 15-(2) is frequently employed in the literature, e.g., [43], [44], [50], [52], [64], [65]. It captures the descent property of \(\psi\) along trajectories of the differential inclusion ?? , while the property that \(\{\psi({\boldsymbol{z}}): {\boldsymbol{z}} \in \mathcal{A}\}\) is finite corresponds to the weak Sard property in [44], which holds when \(f\) is a definable function under the selection \(\Phi:= \partial f\) and \(\psi:= f\).

Assumption 15-(3) and (4) impose mild technical conditions on the evaluation noise \(\{\Xi_{k+1}\}\), and allow for a flexible choice of three-timescale step-sizes \(\{\eta_k, \theta_k, \gamma_k\}\). One simple choice is \(\eta_{k} = o(1/\log k)\), \(\theta_{k}=\eta_{k}(\eta_{k}\log(k))^{-s},\) \(\gamma_k = \eta_{k}(\eta_{k}\log(k))^{-3s/2}\) with \(s\in(0,\frac{1}{2})\).

In the following, we stipulate the standing assumptions on unbiased compression and contractive compression, and present several typical examples.

Assumption 18 is a mild condition, which requires the deviation \(\|C(\boldsymbol{x}, {\boldsymbol{\omega}})-\boldsymbol{x}\|^2\) to be proportional to the squared norm of \({\boldsymbol{x}}\). Indeed, this assumption has been widely adopted in the literature [15], [16], [66].

3.2 Consensus analysis↩︎

In this subsection, we investigate the consensus property of the framework 2 . With the notations \({\boldsymbol{P}}:= \frac{1}{d}{\boldsymbol{1}_{d}} {\boldsymbol{1}}_{d}^\top\) and \({\boldsymbol{P}}_{\perp}:= {\boldsymbol{I}}_{d}- {\boldsymbol{P}}\), \({\boldsymbol{Z}}_{k}\in \mathbb{R}^{m \times d}\) admits the following orthogonal decomposition, \[{\boldsymbol{Z}}_{k} = {\boldsymbol{Z}}_{k}{\boldsymbol{P}} + {\boldsymbol{Z}}_{k}{\boldsymbol{P}}_{\perp}.\] Here, \({\boldsymbol{Z}}_{\perp, k} := {\boldsymbol{Z}}_{k} {\boldsymbol{P}}_{\perp}\) 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 20 is a standard global stability condition in ODE-based analyses of nonsmooth optimization, and has been widely adopted in the literature [43], [44], [50], [51], [67]). In practice, it is also considered as a mild condition.

Proposition 21 describe the consensus property of the sub-framework 3 . To reveal the analogous properties in sub-framework 5 , we introduce some useful Lemmas 22-24, whose proof is shown in Appendix 6.1 and 6.2.

Utilizing above tools, the following lemma shows that the compression error \({\boldsymbol{E}}_{k}\) is bounded and converges to zero almost surely.

3.3 Global convergence and main results↩︎

According to consensus properties shown in Propositions 21 and 25, we can deduce that the cluster points of the sequence \(\{{\boldsymbol{Z}}_k\}\) generated by 3 and 5 coincide with those of the sequence \(\{ {\boldsymbol{Z}}_k \frac{{\boldsymbol{1}}_d {\boldsymbol{1}}_d^\top}{d}\}\). As a result, we proceed to analyze the convergence properties of \(\{{\boldsymbol{Z}}_k \frac{{\boldsymbol{1}}_d}{d}\}\). Proposition 26 describes the relationship between \(\frac{1}{d}{\boldsymbol{Z}}_{k}{\boldsymbol{1}}_d\) and the averaged updated direction \(\frac{1}{d} {\boldsymbol{H}}_{k}{\boldsymbol{1}}_d\) via the set-valued mapping \(\Phi\).

The proof of Lemma 27 is provided in Appendix ¿sec:appendix:claim3?. Based on Proposition 26 and Lemma 27, we establish recursion relations for \(\{\frac{1}{d} {\boldsymbol{Z}}_{k}{\boldsymbol{1}}_d\}\) and derive the global convergence of framework 2 in Theorem 28.

4 Developing Decentralized Stochastic Subgradient-type Methods with Communication Compression and Convergence Guarantees↩︎

In this section, we demonstrate that framework 2 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 2 . 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↩︎

4.1.0.1 Stochastic nonsmooth extension of QDGD.

QDGD [21] 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 \(\nabla f_{i}({\boldsymbol{x}}_{i,k})\) with a stochastic subgradient \({\boldsymbol{g}}_{i, k} \in D_{F_i(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k})\), and employ diminishing sequences \(\{\theta_{k}\}\) and \(\{\eta_{k}\}\) instead of constant \(\theta\) and \(\eta\). The stochastic nonsmooth extension of QDGD can then be compactly written as \[\refstepcounter{equation} \label{unb:dsgd} \left\{ \begin{align} {\boldsymbol{G}}_{k} &= [{\boldsymbol{g}}_{1,k}, \ldots, {\boldsymbol{g}}_{d,k}] \in [D_{F_1(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k}), \ldots, D_{F_d(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k})], \\ {\boldsymbol{E}}_{k+1} & =C({\boldsymbol{X}}_{k}, {\boldsymbol{\omega}}_{k+1}) - {\boldsymbol{X}}_{k},\\ {\boldsymbol{X}}_{k+1} & = (1-\theta_k) {\boldsymbol{X}}_k + \theta_k {\boldsymbol{X}}_k {\boldsymbol{W}} + \theta_k {\boldsymbol{E}}_{k+1}({\boldsymbol{W}}-\mathrm{Diag}({\boldsymbol{W}})) - \eta_k {\boldsymbol{G}}_k. \\ \end{align} \right.\tag{20}\] Here, \(C\) is an unbiased compression operator. \(\{\theta_{k}\}\) is a diminishing sequence of step-sizes with respect to the local average.

4.1.0.2 Nonsmooth extension of CHOCO-SGD.

CHOCO-SGD [27], [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: \[\refstepcounter{equation} \label{con:dsgd} \left\{ \begin{align} {\boldsymbol{G}}_{k} &= [{\boldsymbol{g}}_{1,k}, \ldots, {\boldsymbol{g}}_{d,k}] \in [D_{F_1(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k}), \ldots, D_{F_d(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k})], \\ \hat{{\boldsymbol{X}}}_{k+1} & = \hat{{\boldsymbol{X}}}_{k} + \gamma_k C({\boldsymbol{X}}_{k}-\hat{{\boldsymbol{X}}}_{k}, {\boldsymbol{\omega}}_{k+1}),\\ {\boldsymbol{X}}_{k+1} & = {\boldsymbol{X}}_k + \theta_k \hat{{\boldsymbol{X}}}_{k+1} ({\boldsymbol{W}}-{\boldsymbol{I}}_{d}) - \eta_k {\boldsymbol{G}}_k.\\ \end{align} \right.\tag{21}\] Here, \(C\) is a contractive compression operator. The two-timescale sequences \(\{\gamma_k\}\) and \(\{\theta_{k}\}\) replace the constant \(\theta\) and \(\gamma =1\) used in CHOCO-SGD. With the notation \({\boldsymbol{E}}_{k+1}:= \gamma_k C({\boldsymbol{X}}_{k}- \hat{{\boldsymbol{X}}_{k}}, {\boldsymbol{\omega}}_{k+1})-({\boldsymbol{X}}_{k}- \hat{{\boldsymbol{X}}_{k}})\), we can reformulate 21 as \[\left\{ \begin{align} {\boldsymbol{G}}_{k} &= [{\boldsymbol{g}}_{1,k}, \ldots, {\boldsymbol{g}}_{d,k}] \in [D_{F_1(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k}), \ldots, D_{F_d(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k})], \\ {\boldsymbol{X}}_{k+1}& = (1-\theta_k) {\boldsymbol{X}}_k + \theta_k {\boldsymbol{X}}_k {\boldsymbol{W}} + \theta_k {\boldsymbol{E}}_{k+1}({\boldsymbol{W}}-{\boldsymbol{I}}_{d}) - \eta_k {\boldsymbol{G}}_k. \end{align} \right.\]

4.1.0.3 Nonsmooth extension of BEER and C-GT.

BEER [29] and C-GT [30] utilize an auxiliary variable \({\boldsymbol{Y}}_{k}\) to track the stochastic gradient of the global objective function, and perform contractive compression-based communication on both \({\boldsymbol{X}}_{k}\) and \({\boldsymbol{Y}}_{k}\) simultaneously. We consider a nonsmooth extension of BEER:

\[\refstepcounter{equation} \label{con:dsgt} \left\{ \begin{align} {\boldsymbol{G}}_{k} &= [{\boldsymbol{g}}_{1,k}, \ldots, {\boldsymbol{g}}_{d,k}] \in [D_{F_1(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k}), \ldots, D_{F_d(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k})], \\ {\boldsymbol{X}}_{k+1} & = {\boldsymbol{X}}_k + \theta_k \hat{\boldsymbol{X}}_{k+1}({\boldsymbol{W}}-{\boldsymbol{I}}_{d}) - \eta_k {\boldsymbol{Y}}_k, \\ {\boldsymbol{Y}}_{k+1} & = {\boldsymbol{Y}}_k + \theta_k \hat{\boldsymbol{Y}}_{k+1}({\boldsymbol{W}}-{\boldsymbol{I}}_{d}) + {\boldsymbol{G}}_{k+1} -{\boldsymbol{G}}_{k}, \\ \hat{\boldsymbol{X}}_{k+1} & = \hat{\boldsymbol{X}}_{k} + \gamma_{k}C({\boldsymbol{X}}_{k}-\hat{\boldsymbol{X}}_{k}, {\boldsymbol{\omega}}_{k+1}), \\ \hat{\boldsymbol{Y}}_{k+1} & = \hat{\boldsymbol{Y}}_{k} + \gamma_{k}C({\boldsymbol{Y}}_{k}-\hat{\boldsymbol{Y}}_{k}, {\boldsymbol{\omega}}_{k+1}), \\ {\boldsymbol{Y}}_{0} & = {\boldsymbol{G}}_0,\\ \end{align} \right.\tag{22}\] where \(C\) is a contractive compression operator. The main differences between BEER and BEER+ are the choice of \({\boldsymbol{G}}_{k}\) and the use of slowly diminishing and two-timescale sequences \(\{\theta_{k}\}, \{\gamma_{k}\}\) instead of fixed values. With the notation \({\boldsymbol{E}}_{k+1}:= \gamma_k C({\boldsymbol{X}}_{k}-\hat{{\boldsymbol{X}}}_{k}, {\boldsymbol{\omega}}_{k+1})-({\boldsymbol{X}}_{k}-\hat{{\boldsymbol{X}}}_{k})\), the update scheme of \(\{{\boldsymbol{X}}_{k}\}\) becomes \[{\boldsymbol{X}}_{k+1} = (1-\theta_{k}){\boldsymbol{X}}_k + \theta_k {\boldsymbol{X}}_{k}{\boldsymbol{W}} + \theta_{k} {\boldsymbol{E}}_{k+1}({\boldsymbol{W}}-{\boldsymbol{I}}_{d}) - \eta_k {\boldsymbol{Y}}_{k}.\] In addition, the iterates of the nonsmooth extension of C-GT are given as follows: \[\refstepcounter{equation} \label{con:dsgt(cgt)} \left\{ \begin{align} {\boldsymbol{G}}_{k} &= [{\boldsymbol{g}}_{1,k}, \ldots, {\boldsymbol{g}}_{d,k}] \in [D_{F_1(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k}), \ldots, D_{F_d(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k})], \\ {\boldsymbol{X}}_{k+1} & = {\boldsymbol{X}}_k + \theta_k \tilde{\boldsymbol{X}}_{k+1}({\boldsymbol{W}}-{\boldsymbol{I}}_{d}) - \eta_k {\boldsymbol{Y}}_k, \\ {\boldsymbol{Y}}_{k+1} & = {\boldsymbol{Y}}_k + \theta_k \tilde{\boldsymbol{Y}}_{k+1}({\boldsymbol{W}}-{\boldsymbol{I}}_{d}) + {\boldsymbol{G}}_{k+1} -{\boldsymbol{G}}_{k}, \\ \tilde{\boldsymbol{X}}_{k+1} & = \hat{\boldsymbol{X}}_{k} + \gamma_{k}C({\boldsymbol{X}}_{k}-\hat{\boldsymbol{X}}_{k}, {\boldsymbol{\omega}}_{k+1}), \\ \hat{\boldsymbol{X}}_{k+1} & = (1-\alpha_x) \hat{\boldsymbol{X}}_{k} +\alpha_x \tilde{\boldsymbol{X}}_{k+1}, \\ \tilde{\boldsymbol{Y}}_{k+1} & = \hat{\boldsymbol{Y}}_{k} + \gamma_{k}C({\boldsymbol{Y}}_{k}-\hat{\boldsymbol{Y}}_{k}, {\boldsymbol{\omega}}_{k+1}), \\ \hat{\boldsymbol{Y}}_{k+1} & = (1-\alpha_y) \hat{\boldsymbol{Y}}_{k} + \alpha_y \tilde{\boldsymbol{Y}}_{k+1}, \\ {\boldsymbol{Y}}_{0} & = {\boldsymbol{G}}_0,\\ \end{align} \right.\tag{23}\] where \(\alpha_x \in (0,1]\). Compared to BEER+, C-GT+ includes an additional step of weighted average between the current \(\tilde{\boldsymbol{X}}_{k+1}\) and the previous \(\hat{\boldsymbol{X}}_{k}\). With the notation \({\boldsymbol{E}}_{k+1}:= \gamma_k C({\boldsymbol{X}}_{k}-\hat{{\boldsymbol{X}}}_{k}, {\boldsymbol{\omega}}_{k+1})-({\boldsymbol{X}}_{k}-\hat{{\boldsymbol{X}}}_{k})\), the update scheme of \(\{(\hat{\boldsymbol{X}}_{k}, {\boldsymbol{X}}_{k})\}\) can be rewritten as

\[\left\{ \begin{align} \hat{\boldsymbol{X}}_{k+1} & = \hat{\boldsymbol{X}}_{k} +\alpha_{x} \gamma_{k} C({\boldsymbol{X}}_{k} -\hat{\boldsymbol{X}}_{k}, {\boldsymbol{\omega}}_{k+1}),\\ {\boldsymbol{X}}_{k+1} & = (1-\theta_{k}){\boldsymbol{X}}_k + \theta_k {\boldsymbol{X}}_{k}{\boldsymbol{W}} + \theta_{k} {\boldsymbol{E}}_{k+1}({\boldsymbol{W}}-{\boldsymbol{I}}_{d}) - \eta_k {\boldsymbol{Y}}_{k}.\\ \end{align} \right.\]

4.1.0.4 Decentralized heavy-ball SGD with Nesterov momentum and communication compression.

Heavy-ball SGD [69] accelerates the descent by introducing momentum, which helps dampen oscillations in regions with small gradients or high noise. Nesterov momentum [70] 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 [46], [48], 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: 24 and 25 .

\[\refstepcounter{equation} \label{unb:dsm} \left\{ \begin{align} {\boldsymbol{G}}_{k} &= [{\boldsymbol{g}}_{1,k}, \ldots, {\boldsymbol{g}}_{d,k}] \in [D_{F_1(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k}), \ldots, D_{F_d(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k})], \\ {\boldsymbol{E}}^{x}_{k+1} & =C({\boldsymbol{X}}_{k}, {\boldsymbol{\omega}}_{k+1})-{\boldsymbol{X}}_{k},\\ {\boldsymbol{E}}^{y}_{k+1}& =C({\boldsymbol{Y}}_{k}, {\boldsymbol{\omega}}_{k+1})-{\boldsymbol{Y}}_{k},\\ {\boldsymbol{X}}_{k+1} & = (1-\theta_k) {\boldsymbol{X}}_k + \theta_k {\boldsymbol{X}}_k {\boldsymbol{W}} + \theta_k {\boldsymbol{E}}^{x}_{k+1}({\boldsymbol{W}}-\mathrm{Diag}({\boldsymbol{W}})) - \eta_k ({\boldsymbol{Y}}_k +\rho {\boldsymbol{G}}_{k}), \\ {\boldsymbol{Y}}_{k+1} & = (1-\tau \eta_k)[(1-\theta_k) {\boldsymbol{Y}}_k + \theta_k {\boldsymbol{Y}}_k {\boldsymbol{W}} + \theta_k {\boldsymbol{E}}^{y}_{k+1}({\boldsymbol{W}}-\mathrm{Diag}({\boldsymbol{W}}))] + \tau \eta_k {\boldsymbol{G}}_{k+1}.\\ \end{align} \right.\tag{24}\] Here, \(C\) is an unbiased compression operator. \(\{\theta_{k}\}\) stands for diminishing step-sizes corresponding to the local average. In the update step of \({\boldsymbol{Y}}_{k+1}\), the local aggregation based on unbiased compression is used as an inertial direction, while \({\boldsymbol{G}}_{k+1}\) serves as a descent direction. \(\tau >0\) is the heavy-ball momentum parameter and \(\rho \geq 0\) is the Nesterov momentum parameter.

\[\refstepcounter{equation} \label{con:dsm} \left\{ \begin{align} {\boldsymbol{G}}_{k} &= [{\boldsymbol{g}}_{1,k}, \ldots, {\boldsymbol{g}}_{d,k}] \in [D_{F_1(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k}), \ldots, D_{F_d(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k})], \\ \hat{\boldsymbol{X}}_{k+1}&= \hat{\boldsymbol{X}}_{k}+\gamma_{k}C({\boldsymbol{X}}_{k}-\hat{\boldsymbol{X}}_{k}, {\boldsymbol{\omega}}_{k+1}),\\ \hat{\boldsymbol{Y}}_{k+1}& = \hat{\boldsymbol{Y}}_{k}+\gamma_{k}C({\boldsymbol{Y}}_{k}-\hat{\boldsymbol{Y}}_{k}, {\boldsymbol{\omega}}_{k+1}),\\ {\boldsymbol{X}}_{k+1} & = {\boldsymbol{X}}_k + \theta_{k} \hat{{\boldsymbol{X}}}_{k+1}({\boldsymbol{W}}-{\boldsymbol{I}}_{d}) - \eta_k ({\boldsymbol{Y}}_k + \rho {\boldsymbol{G}}_k),\\ {\boldsymbol{Y}}_{k+1} & = (1-\tau \eta_{k})[{\boldsymbol{Y}}_k + \theta_{k} \hat{{\boldsymbol{Y}}}_{k+1}({\boldsymbol{W}}-{\boldsymbol{I}}_{d})] + \tau \eta_{k}{\boldsymbol{G}}_{k+1}.\\ \end{align} \right.\tag{25}\] Here, \(C\) is a contractive compression operator. \(\{\theta_{k}\}, \{\gamma_{k}\}\) are two-timescale diminishing sequences of step-sizes. The sequence \(\{{\boldsymbol{Y}}_{k}\}\) is updated by a local aggregation with contractive compression combined with a heavy-ball momentum step. Parameters \(\tau, \rho\) are defined analogously to 24 .

4.1.0.5 Decentralized sign-regularized SGD with communication compression.

SignSGD [71], [72] 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 [49], we present two decentralized sign-regularized SGD methods with communication compression.

\[\refstepcounter{equation} \label{unb:signdsgd} \left\{ \begin{align} {\boldsymbol{G}}_{k} &= [{\boldsymbol{g}}_{1,k}, \ldots, {\boldsymbol{g}}_{d,k}] \in [D_{F_1(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k}), \ldots, D_{F_d(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k})], \\ {\boldsymbol{E}}^{x}_{k+1} & =C({\boldsymbol{X}}_{k}, {\boldsymbol{\omega}}_{k+1})-{\boldsymbol{X}}_{k},\\ {\boldsymbol{E}}^{y}_{k+1}& =C({\boldsymbol{Y}}_{k}, {\boldsymbol{\omega}}_{k+1})-{\boldsymbol{Y}}_{k}, \\ {\boldsymbol{X}}_{k+1} & = (1-\theta_k) {\boldsymbol{X}}_k + \theta_k {\boldsymbol{X}}_k {\boldsymbol{W}} + \theta_k {\boldsymbol{E}}^{x}_{k+1}({\boldsymbol{W}}-\mathrm{Diag}({\boldsymbol{W}})) - \eta_k \mathrm{sign}({\boldsymbol{Y}}_k+ \rho {\boldsymbol{G}}_{k}), \\ {\boldsymbol{Y}}_{k+1} & = (1-\tau \eta_k)[(1-\theta_k) {\boldsymbol{Y}}_k + \theta_k {\boldsymbol{Y}}_k {\boldsymbol{W}} + \theta_k {\boldsymbol{E}}^{y}_{k+1}({\boldsymbol{W}}-\mathrm{Diag}({\boldsymbol{W}}))] + \tau \eta_k {\boldsymbol{G}}_{k+1}. \\ \end{align} \right.\tag{26}\] Here, \(C\) is an unbiased compression operator, and the sign map serves as a regularizer of the Nesterov momentum term \({\boldsymbol{Y}}_k+ \rho {\boldsymbol{G}}_{k}\). Parameters \(\tau, \rho\), and \(\{\theta_k\}\) are defined analogously to 24 .

\[\refstepcounter{equation} \label{con:signdsgd} \left\{ \begin{align} {\boldsymbol{G}}_{k} &= [{\boldsymbol{g}}_{1,k}, \ldots, {\boldsymbol{g}}_{d,k}] \in [D_{F_1(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k}), \ldots, D_{F_d(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k})], \\ \hat{\boldsymbol{X}}_{k+1}& = \hat{\boldsymbol{X}}_{k}+\gamma_{k}C({\boldsymbol{X}}_{k}-\hat{\boldsymbol{X}}_{k}, {\boldsymbol{\omega}}_{k+1}),\\ \hat{\boldsymbol{Y}}_{k+1}& = \hat{\boldsymbol{Y}}_{k}+\gamma_{k}C({\boldsymbol{Y}}_{k}-\hat{\boldsymbol{Y}}_{k}, {\boldsymbol{\omega}}_{k+1}),\\ {\boldsymbol{X}}_{k+1} & = {\boldsymbol{X}}_k + \theta_{k} \hat{{\boldsymbol{X}}}_{k+1}({\boldsymbol{W}}-{\boldsymbol{I}}_{d}) - \eta_k \mathrm{sign}({\boldsymbol{Y}}_k + \rho {\boldsymbol{G}}_k),\\ {\boldsymbol{Y}}_{k+1} & = (1-\tau \eta_{k})[{\boldsymbol{Y}}_k + \theta_{k} \hat{{\boldsymbol{Y}}}_{k}({\boldsymbol{W}}-{\boldsymbol{I}}_{d})] + \tau \eta_{k}{\boldsymbol{G}}_{k+1}.\\ \end{align} \right.\tag{27}\] Here, \(C\) is a contractive compression operator. Step-sizes \(\{\theta_k\}, \{\gamma_k\}\), and parameters \(\tau, \rho\) are defined similarly to 25 .

4.1.0.6 Decentralized stochastic momentum tracking with contractive compression.

Based on our framework 5 , we modify compression term and the update rule for the momentum variables in DoCoM [31], and propose a novel decentralized momentum-tracking method with contractive compression.

\[\refstepcounter{equation} \label{con:dsgtm} \left\{ \begin{align} {\boldsymbol{G}}_{k} &= [{\boldsymbol{g}}_{1,k}, \ldots, {\boldsymbol{g}}_{d,k}] \in [D_{F_1(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k}), \ldots, D_{F_d(\cdot,\zeta_{i,k+1})}({\boldsymbol{x}}_{i,k})], \\ \hat{{\boldsymbol{X}}}_{k+1} & = \hat{{\boldsymbol{X}}}_{k} + \gamma_k C({\boldsymbol{X}}_{k}- \hat{{\boldsymbol{X}}}_{k}, {\boldsymbol{\omega}}_{k+1}),\\ {\boldsymbol{X}}_{k+1} & = {\boldsymbol{X}}_k + \theta_k \hat{\boldsymbol{X}}_{k+1} ({\boldsymbol{W}}-{\boldsymbol{I}}_d) - \eta_k {\boldsymbol{Y}}_k,\\ {\boldsymbol{V}}_{k+1} & = (1-\tau \eta_{k}){\boldsymbol{V}}_{k} + \tau \eta_{k} {\boldsymbol{G}}_{k+1},\\ \hat{{\boldsymbol{Y}}}_{k+1} & = \hat{{\boldsymbol{Y}}}_{k} + \gamma_k C({\boldsymbol{Y}}_{k}- \hat{{\boldsymbol{Y}}}_{k}, {\boldsymbol{\omega}}_{k+1}),\\ {\boldsymbol{Y}}_{k+1} & = {\boldsymbol{Y}}_k + \theta_k \hat{\boldsymbol{Y}}_{k+1} ({\boldsymbol{W}}-{\boldsymbol{I}}_d)+ {\boldsymbol{V}}_{k+1} -{\boldsymbol{V}}_{k}, \\ {\boldsymbol{V}}_0 & = {\boldsymbol{G}}_0.\\ \end{align} \right.\tag{28}\] Here, \(C\) is a contractive compression operator. \({\boldsymbol{V}}_k\) represents the collection of momentum variables, and \({\boldsymbol{Y}}_{k}\) serves as the collection of momentum-tracking variables incorporating compression-based aggregation. \(\{\theta_{k}\}, \{\gamma_{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 2 , and hence inherit global convergence guarantees to \(D_{f}\)-critical points in the minimization of nonsmooth definable functions. Throughout this section, we impose several assumptions on the original problem 1 and the methods in Section 4.1.

Based on [43], 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 \(f_{i}\) as \[\label{eq:defin95cons} D_{f_i}({\boldsymbol{x}}) := \mathbb{E}_{\zeta_{i}\sim \mathcal{P}_{i}} D_{F_i(\cdot, \zeta_{i})}({\boldsymbol{x}}),\tag{29}\] and a definable and convex conservative field for \(f\) as \[D_f({\boldsymbol{x}}) := \mathrm{conv}\,\left(\frac{1}{d} \sum_{i = 1}^d D_{f_i}({\boldsymbol{x}}) \right).\]

Lemmas 31 and 32 present the Lyapunov functions corresponding to different differential inclusions, which is a key to verifying that the methods in Section 4.1 satisfy Assumption 15.

In Table 3, we show the specific choices of \({\boldsymbol{Z}}_{k}\), \({\boldsymbol{H}}_{k}\), \({\boldsymbol{E}}_{k}\) for each method in Section 4.1, thereby verifying the first two items of Proposition 33. In Table 4, we illustrate the specific choices of \(\Phi_{i}\), \(\psi\), \(\mathcal{A}\) and \(\epsilon_k\) for each method in Section 4.1. Combining with the local boundedness of \(D_{F_i(\cdot, \zeta_{i})}\), Lemma 31, and Lemma 32, we can directly verify that all the methods satisfy Assumption 15.

By applying Theorem 28, we establish the convergence guarantees for above-mentioned methods.

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 [73] 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 [27], [28]. In the second comparison group, we use an Erdős-Rényi (E.R.) random graph topology [74] 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 [56]. 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 \(128\). 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 \(8\)-bit random quantization operator \(Q_{2^8}\) from Example 17.

• Contractive compression: The \(\mathrm{Random}\)-\(10 \%\) and \(\mathrm{Top}\)-\(10 \%\) sparsification operators from Example 19 and rescaled \(8\)-bits random quantization operator \(\frac{1}{1+ \min\{d/2^{16}, \sqrt{d}/2^8\}}Q_{2^8}\) (abbreviated as rescaled \(Q_{2^8}\)).

Implementation details. A common strategy for updating \(\{\eta_{k}\}\) is to decay it at specific milestones while keeping it constant otherwise. Meanwhile, \(\{\theta_k\}\) remains constant, and \(\{\gamma_k\}\) is typically fixed to \(1.0\) in existing works [27]–[29] under the smooth setting. To meet the requirement in Assumption 29, namely that the sequences \(\{(\eta_{k}, \theta_{k}, \gamma_{k})\}\) form a three-timescale scheme and are of order \(o(\frac{1}{\log(k)})\), we propose another update strategy for \(\{(\eta_{k}, \theta_{k}, \gamma_{k})\}\). Empirically, starting with initial \(\eta_0\), we warm up \(\{\eta_k\}\) in the first five epochs to obtain \(\eta_{\text{warm}}\) in both strategies.

1. Strategy 1: \[\begin{align} \eta_{k}^{(1)} & = \begin{cases} \eta_{\text{warm }}, & 5 \leq k\cdot \text{number of batches per epoch} < 100,\\ 0.1\eta_{\text{warm }}, & 100 \leq k\cdot \text{number of batches per epoch} < 180,\\ 0.01 \eta_{\text{warm }}, & 180 \leq k\cdot \text{number of batches per epoch} \leq 200,\\ \end{cases}\\ \theta^{(1)}_k & \equiv \theta_0, \quad \gamma^{(1)}_k \equiv 1.0. \\ \end{align}\] This means the step size is decayed by a factor of 0.1 at the 100th and 180th epochs.

2. Strategy 2: \[\begin{align} \eta_{k}^{(2)} & = \begin{cases} \eta_{k}^{(1)}, & 5 \leq k\cdot \text{number of batches per epoch} < 100,\\ \frac{\eta_{k}^{(1)}}{\log(k-100 +e)^{1.01}}, & 100 \leq k\cdot \text{number of batches per epoch} < 200,\\ \end{cases}\\ \theta^{(2)}_{k} & =\theta_0 \eta^{(2)}_{k}/(\eta^{(2)}_{k}\log(k))^{s}, s \in (0, \frac{1}{2}), \\ \gamma^{(2)}_k & = \theta^{(2)}_{k}/(\theta^{(2)}_{k}\log(k))^{s}, s \in (0, \frac{1}{2}).\\ \end{align}\]

By default, we set \(s = 0.25\) in our experiments. Additionally, the fine-tuned hyper-parameters \(\eta_0\) and \(\theta_0\) for different methods and compression operators are presented in Table 5 and 6. The momentum parameter \(\tau\) in DSM-Unb(Con), DSGTM-Unb(Con) and SignDSGD-Unb(Con) is set as \(\tau= \frac{0.1}{\eta_0}\) by default.

5.2 Performance comparison between existing methods and their nonsmooth extensions under our framework↩︎

Figures 1, 2 and 3 present the numerical performance of the following comparison pairs:

• CHOCO-SGD vs. CHOCO-SGD+,

• BEER vs. BEER+

• QSDGD ¹ 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 \(\theta_0\) and \(\eta_0\)) are set identically.

As shown in Figure 1-3, 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\%\) 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 \(\mathrm{Top}\)-\(10\%\) operator, the \(\mathrm{Random}\)-\(10\%\) operator, and the rescaled \(Q_{2^8}\) operator. In the last experimental group, we utilize the \(Q_{2^8}\) operator as our unbiased compression operator. Furthermore, we incorporate vanilla DSGD [75] as the baseline algorithm.

From Figures 4, 7, and 9 (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 4, 7 and 9 (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 5, 8 and 10, we conclude that DSGTM-Con matches the uncompressed baseline in both test accuracy and training loss, while consistently reducing communication costs by \(1/3\), demonstrating consistently better overall performance than BEER+ across all evaluated metrics.

Figure 6 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 \(10^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 2 for developing decentralized stochastic subgradient-type methods with communication compression. By configuring different compression errors and selecting diagonal matrix \(\Sigma\) as either \(\mathrm{Diag}({\boldsymbol{W}})\) or \({\boldsymbol{I}}_d\), our framework can adapt to two variants suitable for unbiased or contractive communication compression, respectively. Moreover, 2 employs a family of set-valued mappings \(\{\Phi_{i}\}_{i\in[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 \(\{\theta_{k}\}\) (and \(\{\gamma_{k}\}\)) to regulate modified local average and the update of local copies, we establish the consensus properties and global asymptotic convergence for our framework 2 . 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 2 , such as DSM-Unb(Con), SignDSGD-Unb(Con), DSGTM-Con, demonstrating the significant potential of 2 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 2 almost surely converge to a Clarke-critical point, i.e., excluding potential spurious critical points within the set of \(D_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.

Appendix↩︎

6.1 Proof of Lemma 22↩︎

6.2 Proof of Lemma 23↩︎

Proof of Lemma 27↩︎

References↩︎