Abstract In the decentralized distributed learning, achieving fast convergence and low communication cost is essential for scalability and high efficiency. Adaptive gradient methods, such as Adam, have demonstrated strong practical performance in deep learning and centralized distributed settings. However, their convergence properties remain largely unexplored in decentralized settings involving multiple local training steps, such as federated learning. To address this limitation, we propose LoDAdaC, a unified multiple Local Training (MLT) Decentralized framework with Adam-type updates and Compressed communication (CC). LoDAdaC accommodates a broad class of optimizers for its local adaptive updates, including AMSGrad, Adam, and AdaGrad; it is compatible with standard (possibly biased) compressors such as low-bit quantization and sparsification. MLT and CC enable LoDAdaC to achieve multiplied reduction of communication cost, while the technique of adaptive updates enables fast convergence. We rigorously prove the combined advantage through complexity analysis. In ∗ Corresponding author

Published in Transactions on Machine Learning Research (04/2026)

addition, experiments on image classification and GPT-style language model training validate our theoretical findings and show that LoDAdaC significantly outperforms existing decentralized algorithms in terms of convergence speed and communication efficiency.

Introduction

In decentralized learning, multiple agents collaboratively train a model without a central server, by exchanging information exclusively with immediate (a.k.a. one-hop) neighbors. Compared to centralized distributed learning, decentralized learning has better robustness and scalability. However, communication cost can become a bottleneck in decentralized learning, especially when low-bandwidth or wireless communication is performed. This motivates the design of communication-efficient decentralized algorithms. Two widely adopted strategies to reduce the communication burden in distributed learning are Compressed Communication (CC) and Multiple Local Training (MLT). By CC, the agents transmit compressed information rather than full-precision one, significantly reducing per-round communication cost. Examples include low-bit quantization (Sun et al., 2020; Wang et al., 2018; Bernstein et al., 2018; Alistarh et al., 2017) and sparsification (Koloskova et al., 2019; Stich et al., 2018). CC also provides implicit privacy protection: by transmitting the compressed message, agents inherently obscure precise local data information, thus mitigating potential privacy risks (Kairouz et al., 2021). On the other hand, MLT, which involves performing several local updates per communication round, has gained popularity in various distributed learning settings. Prominent examples include local SGD (Haddadpour et al., 2019), SGD averaging (Zhang et al., 2015), and, notably, Federated Averaging (FedAvg) (McMahan et al., 2017), a widely employed method in federated learning (FL). Empirically, MLT significantly reduces the number of communication rounds required to achieve a target convergence threshold. Moreover, from a privacy perspective, MLT further enhances security by reducing the frequency and amount of sensitive information exchanged among agents, thus limiting potential data leakage (Li et al., 2020; Kairouz et al., 2021). Both CC and MLT have been explored in vanilla and momentum SGD (Singh et al., 2021; Sun et al., 2022), and it is shown in (Singh et al., 2021) that multiplied reduction of communication can be achieved. However, adaptive (i.e., Adam) stochastic methods (Kingma & Ba, 2014) exhibit significantly faster convergence than vanilla or momentum SGD on training deep learning models and are now the workhorse for training language models. Hence, it is natural to ask the following question: Can CC and MLT be applied in decentralized adaptive stochastic methods to simultaneously achieve multiplied reduction of communication and fast convergence? 1.1

(Q)

Contributions

This work provides an affirmative answer to the question (Q). We propose LoDAdaC, a Local trainingbased Decentralized framework with Adaptive gradient updates and Compressed communication. Our local update scheme includes both the vector and matrix variants of AdaGrad (Duchi et al., 2011), Adam (Kingma & Ba, 2014), AMSGrad (Reddi et al., 2016), and the recently proposed Adam-Mini (Zhang et al., 2024). The integration of CC and MLT enables a multiplied reduction of communication cost while adaptive gradient updates further yield fast convergence. A central technical contribution of our work lies in resolving the core analytical challenge introduced by the interaction of MLT, CC, adaptive gradient updates, and decentralized communication: their coupling makes it difficult to derive a unified upper bound on the consensus error and stationarity violation. In particular, local adaptive gradient updates introduce nonlinearity and dynamically varying gradient scaling, which complicate the analysis even in centralized settings (Wang et al., 2022b). When combined with decentralized model aggregation, these properties pose significant technical obstacles to convergence analysis. Our analysis carefully disentangles the coupling, leading to tight convergence guarantees under mild conditions and offering the first such results for this challenging setting. By performing K local updates per communication round and utilizing a compression operator that compresses one unit of message to 1 − η unit with η ∈ (0, 1), our algorithm needs a total communication cost of O( 1−η Kϵ4 ) to produce an ϵ-stationary solution, thus yielding 2

Published in Transactions on Machine Learning Research (04/2026)

multiplied reduction of communication cost. Notably, the result applies uniformly across different choices of compressors and adaptive updates. In addition, we conduct numerical experiments on two representative tasks, i.e., image classification and language model training, to validate the effectiveness of LoDAdaC. Though our complexity result has the same order dependence on ϵ as achieved by existing non-adaptive stochastic methods such as SQuARMSGD, our numerical results demonstrate that LoDAdaC achieves significant speed up by adaptive gradient updates and significant communication reduction from combining MLT and CC. Specifically, our experiments illustrate that: (i) LoDAdaC equipped with adaptive gradient updates significantly outperforms the baseline decentralized algorithm SQuARM-SGD (that employs momentum gradient update) in terms of convergence speed; (ii) The joint use of MLT and CC reduces the total communication cost dramatically, achieving reductions of over 99% in some scenarios (e.g., see the results yielded by LoDAdaC with K = 50 and Topk=30% in Figures 3a and 3b), with nearly no sacrifice of accuracy. These empirical findings align closely with our theoretical results. 1.2

Problem formulation and technical assumptions

We consider decentralized nonconvex stochastic optimization in the form of n

min f (x) :=

x∈Rd

1X fi (x), with fi (x) = Eξi ∼Di [Fi (x, ξi )] . n i=1

(1)

Here, n agents, connected via a communication graph G, collectively minimize the objective function f as the average of local functions {fi }, each of which is defined as an expectation over a data distribution Di . Each agent i ∈ {1, 2, . . . , n} exclusively accesses its local function fi and stochastic gradients ∇Fi (x, ξi ), and collaboration occurs through communication with immediate neighbors. To perform decentralized computation, each agent i ∈ {1, 2, . . . , n} maintains a local copy xi of the decision variable x. Let X = [x1 , x2 , . . . , xn ] ∈ Rd×n . The problem (1) can be equivalently reformulated as n

1X fi (xi ), s.t. X = XW, X∈Rd×n n i=1 min

(2)

where W is a mixing (a.k.a. gossip) matrix that governs how agents aggregate local information. Under Assumption 2(iii) given below, imposing the constraint X = XW is equivalent to requiring x1 = · · · = xn , i.e., X lies in the consensus subspace. Throughout the paper, we make the following standard assumptions. Assumption 1 For each i ∈ {1, 2, . . . , n}, the function fi is L-smooth, i.e., ∥∇fi (x)− ∇fi (y)∥≤ L∥x − y∥, for any x, y ∈ Rd , and f is lower bounded, i.e., f ∗ := minx f (x) > −∞. Assumption 2 For the mixing matrix W, it holds (i) W is doubly stochastic, i.e., W ≥ 0, W1 = 1 and 1⊤ W = 1⊤ ; (ii) Wij = 0 if i and j are not neighbors to each other; (iii) Null(W − I) = span{1} and ⊤ ρ := ∥W − J∥2 < 1, where 1 is an all-one vector, I is the identity matrix, and J = 11n . Assumption 2 encodes the standard structural conditions required for decentralized averaging. First, the doubly stochastic property ensures that the mixing operation preserves the network average. Second, the condition Wij = 0 for any non-neighboring agents i and j enforces that communication occurs only between neighboring nodes in the underlying graph G, thereby respecting the locality of the decentralized architecture. Most importantly, the spectral condition ρ = ∥W − J∥2 < 1 guarantees contraction toward consensus and serves as the key quantity controlling the consensus-error recursion in our analysis. Intuitively, smaller values of ρ correspond to faster information propagation across the network and hence more rapid agreement among agents. The specific choice of the mixing matrix W depends on the communication topology, and several standard constructions have been proposed in the literature (Koloskova et al., 2019; Mancino-Ball et al., 2023; Nedić et al., 2018). In particular, Xiao & Boyd (2004) showed that one can design an optimal mixing matrix that minimizes ρ while satisfying the constraints in Assumption 2. 3

Published in Transactions on Machine Learning Research (04/2026)

1.3

Notations and definitions

We define [T ] = {0, 1, . . . , T − 1} and use ∥·∥ to denote the Euclidean norm for vectors and the Frobenius norm for matrices. The spectral norm of a matrix A is denoted by ∥A∥2 . For two vectors a and b of √ the same dimension, ab and a ◦ b denote componentwise division and multiplication, respectively, while c applies the square-root operation elementwise to a nonnegative vector c. X⊥ = X(I − J) denotes the consensus error matrix and x = n1 X1 for the average of all local decision variables. Et takes the expectation over the random samples {ξit }i∈{1,2,...,n} conditional on the t-th iterate, while E takes the full expectation. Definition 1.1 We call Q an η-compression operator, if it holds EQ ∥x − Q[x]∥2 ≤ η 2 ∥x∥2 for some η ∈ [0, 1) and all x ∈ Rd . The expectation in the above definition is taken with respect to the internal randomness of the compressor, conditioned on the input x. For deterministic compressors, such as Top-k sparsification, the inequality holds deterministically. Our analysis relies only on the contractive-error property in Definition 1.1 and does not require additional assumptions such as unbiasedness. Examples of η-compression operators include Randomk (Stich et al., 2018), Top-k (Aji & Heafield, 2017), and the rescaled quantizations (Chen et al., 2023a); see more examples in (Chen et al., 2023a; Koloskova et al., 2019). When η = 0, Q simplifies to the identity operator. Definition 1.2 We say that X is an ϵ-stationary point, in expectation, of the decentralized problem (2) if E ∥∇f (x)∥2 + E n1 ∥X⊥ ∥2 ≤ ϵ2 . This notion jointly controls stationarity of the averaged model and network disagreement; both must be small for decentralized learning to be practically meaningful.

Related work

In this section, we review existing works on distributed stochastic gradient methods (SGMs) in either a centralized or a decentralized setting for solving nonconvex problems. Additionally, we review methods developed for distributed learning with MLT and CC. 2.1

Centralized or decentralized (stochastic) adaptive gradient methods

Adaptive SGMs are among the most popular stochastic algorithms for training nonconvex deep learning models. In practice, adaptive SGMs such as AdaGrad (Duchi et al., 2011), Adam (Kingma & Ba, 2014), and AMSGrad (Reddi et al., 2016) are more effective compared to a nonadaptive SGM. Efforts have been made to integrate adaptive gradient updates into distributed optimization. Hou et al. (2018) propose a distributed Adam for convex problems, while (Chen et al., 2020; Zhao et al., 2022) introduce locally adaptive algorithms for centralized distributed training. The compressed centralized distributed Adam variants are explored in (Chen et al., 2021; 2023a). A centralized distributed AMSGrad is studied in (Li et al., 2022), and a compressed version is presented in (Wang et al., 2022a). The decentralized Adam variant, DADAM, was introduced in (Nazari et al., 2022), providing convergence results for both convex and nonconvex problems. However, subsequent analysis by (Chen et al., 2023b) reveals that DADAM may not converge to a stationary point in nonconvex settings. To address this limitation, (Chen et al., 2023b; Wang et al., 2025; Liu et al., 2025) propose some other decentralized adaptive gradient methods. Despite these advancements, distributed learning with multiple local adaptive gradient updates has been explored only in a centralized setting. Xie et al. (2019) propose AdaAlter, which employs local adaptive updates on the client side. Similarly, Reddi et al. (2020) extend FedAvg by incorporating three types of local adaptive gradient updates to improve optimization performance. More recently, FedLADA (Sun et al., 2023) introduces momentum-corrected adaptive updates, and FedAMS, along with its corrected variant FedCAMS (Wang et al., 2022b), stabilizes local AMSGrad updates to ensure convergence. However, decentralized distributed learning with multiple local adaptive gradient updates remains unexplored. Though Gao 4

Published in Transactions on Machine Learning Research (04/2026)

& Huang (2020) attempt to study a decentralized distributed method with multiple local Adam updates, they conduct analysis only to the case without first-order momentum. In addition, their convergence rate results in Corollary 1 and Corollary 2 are obtained by implicitly assuming β2 = 0, i.e., no second-order momentum either. 2.2

MLT in distributed learning

MLT is a simple yet remarkably effective communication-saving strategy in distributed learning, where clients perform several local updates—rather than a single one—between successive communication rounds. A foundational method that employs MLT in centralized distributed learning is FedAvg, with numerous extensions including FedAvg with local momentum (Hsu et al., 2019), server momentum (Sun et al., 2024), and adaptive FedAvg (Reddi et al., 2020). Recent theoretical advancements have clarified why MLT effectively reduces communication complexity in centralized distributed learning (Kairouz et al., 2021; Li et al., 2020). These results have been rigorously established across a wide range of local update strategies, including standard SGD (Haddadpour et al., 2019; Spiridonoff et al., 2021; Stich, 2018; Yu et al., 2019), momentum-based methods (Karimireddy et al., 2020; Sun et al., 2024), and adaptive gradient methods (Reddi et al., 2020; Xie et al., 2019). In decentralized distributed learning, early work has primarily focused on algorithms using simple local SGD updates. For example, Xing et al. (2020) propose a decentralized federated learning framework for medical applications, operating without a central server in a dynamic peer-to-peer network. Similarly, Lalitha et al. (2019) explore decentralized learning using a Bayesian-inspired belief update mechanism over connected networks. Further analyses in (Koloskova et al., 2020; Sun et al., 2022; Wu et al., 2025; Li et al., 2019) have demonstrated that incorporating MLT with multiple local SGD updates can also reduce communication complexity in a decentralized distributed setting. 2.3

MLT+CC in distributed learning

Combining MLT and CC, while simultaneously retaining their respective benefits, is notably challenging. In a centralized distributed setting, several recent algorithms successfully integrate these strategies, including CompressedScaffnew (Condat et al., 2022), LoCoDL (Condat et al., 2025), FedCOM (Haddadpour et al., 2021), FedPAQ (Reisizadeh et al., 2020), and Qsparse-Local-SGD (Basu et al., 2019). They leverage the advantage of both MLT and CC, achieving a multiplied reduction of communication complexity. Despite these developments, few algorithms leveraging MLT+CC have been proposed in the context of decentralized distributed learning. Extending theoretical guarantees to the decentralized setting introduces substantial challenges due to the absence of a central coordinator. Complications arise from network topology constraints, the need for peer-to-peer communication, and heterogeneity in local data and model states. These factors make the convergence analysis significantly more intricate and have historically limited the rigorous understanding of MLT+CC in decentralized settings. Among decentralized MLT+CC methods, each individual one covers only part of the design space. DFedAvgM from (Sun et al., 2022), SQuARM-SGD from (Singh et al., 2021), and LM-DFL from (Chen et al., 2024) are closely related to our method. DFedAvgM extends decentralized FedAvg by incorporating momentum-based local updates and CC. However, DFedAvgM is unable to reduce the order of total communication rounds through MLT and can only mitigate the effect from local variance of stochastic gradients when no momentum is applied. In addition, using CC will hurt the complexity result of DFedAvgM to obtain an ϵ-stationary point unless the compression error is controlled in O(ϵ4 ), which is a too-restrictive assumption. Without relying on such restrictive assumptions, a general convergence result is established to LM-DFL that incorporates both MLT and CC. However, LM-DFL is also unable to reduce the order of total communication rounds through MLT. SQuARM-SGD achieves multiplied communication reduction, but its analysis is tailored to momentum SGD and additionally assumes a symmetric mixing matrix. Compared to existing decentralized methods combining MLT and CC, our contribution transcends a specific optimizer instantiation by providing a unified algorithmic framework and a generalizable convergence analysis template. Notably, we establish the first rigorous convergence guarantees for federated learning scenarios 5

Published in Transactions on Machine Learning Research (04/2026)

MLT Methods

CC AG

PD-SGD (Ge & Chang, 2023)

✗

LSGT (Li et al., 2019)

✗

DFedAvgM (Sun et al., 2022)

✓

✗

SQuARM-SGD (Singh et al., 2021)

✓

✗

LM-DFL (Chen et al., 2024)

✓

✗

LoDAdaC (this paper)

✓

#Iter

CommCost

1 nϵ4 1 nϵ4 4 ∗ max{ ϵK4 , Kϵ } s2 1 nϵ4 3 4 max{ K 31ϵ4 , Kϵ4s }∗ 1 nϵ4

1 nKϵ4 1 nKϵ4 4 max{ 1−s , (1−s)ϵ }∗ ϵ4 s2 1−η nKϵ4 (1−s)K 2 s4 ∗ max{ K1−s } 4 ϵ4 , ϵ4 1−η nKϵ4

MLTsave CCsave ✓

−

✓

−

✗

✓

✗

✓

Table 1: Comparison between the proposed method and selected approaches that use MLT for nonconvex decentralized distributed learning. “CC” indicates whether compressed communication is employed; “AG” denotes the use of adaptive gradient updates; “#Iter” specifies the number of total iterations (per agent) to obtain an ϵ-stationary point of problem (2), see Definition 1.2; “CommCost” refers to the total communication cost, where each communication round incurs a unit cost in the absence of compression; “MLTsave” indicates whether the number of communication rounds can be theoretically reduced by employing MLT; and “CCsave” reflects whether the total communication cost can be effectively reduced by compression. Here, the O(·) notation is omitted in the table, ϵ is assumed to be sufficiently small, and the number of local stepsK is at most O(ϵ−1 ). ∗ s refers to the compression error given in (Sun et al., 2022), satisfying EQ ∥x − Q[x]∥2 ≤ s2 d. employing adaptive gradient methods such as Adam. Moreover, our convergence analysis relies exclusively on the contractive-error property of the compression operator, thus naturally extending to accommodate potentially biased compressors, including Top-k sparsification. Lastly, our proof technique explicitly decouples the intricate interactions among adaptive gradient updates, MLT steps, and decentralized communication, effectively addressing the core analytical challenge of simultaneously ensuring stationarity and consensus in decentralized distributed training. Detailed comparisons are summarized in Table 1. We notice that the complexity result of our method is in the same order as that of SQuARM-SGD. However, with adaptive gradient updates, our method is able to achieve significantly faster empirical convergence, in particular for training GPT-style language models; see Section 4.

Decentralized adaptive methods with MLT and CC

In this section, we introduce a unified decentralized framework that integrates multiple local adaptive gradient updates with compressed communication. It is named LoDAdaC. Also, we provide convergence guarantees for the proposed algorithm under general nonconvex settings. 3.1

A unified algorithmic framework

We present the pseudocode of our framework in Algorithm 1. For simplicity, we take a single randomly sampled data point ξit at each iteration. All our theoretical results remain valid by taking a mini-batch of samples. In addition to Assumptions 1–2, we make the following assumption, which is standard in the analysis of both distributed and non-distributed adaptive SGMs (Chen et al., 2019; 2023b; Kingma & Ba, 2014; Reddi et al., 2018; Xu et al., 2023). Assumption 3 The random samples {ξit }i,t≥0 are independent. For each t and i ∈ {1, 2, . . . , n}, it holds Et [git ] = ∇fi (xti ). In addition, there are constants B and B∞ such that ∥git ∥ ≤ B, ∥git ∥∞ ≤ B∞ for any i ∈ {1, 2, . . . , n} and any t, and ∥∇fi (x)∥ ≤ B, ∥∇fi (x)∥∞ ≤ B∞ for all x. The unbiasedness condition Et [git ] = ∇fi (xti ) is standard in the literature of stochastic methods (Lan, 2020). The bounded gradient condition in Assumption 3 is stronger than the bounded-variance assumptions often used for non-adaptive methods; it can be restrictive for modern deep networks with heavy-tailed gradients. Nevertheless, similar assumptions are made in prior work such as (Chen et al., 2023b) for the convergence 6

Published in Transactions on Machine Learning Research (04/2026)

analysis of adaptive methods. Extending the present adaptive+MLT+CC analysis under weaker conditions, such as generalized smoothness or bounded-variance assumptions, is an important direction for future work. Algorithm 1: A Local training-based Decentralized framework with Adaptive gradient updates and Compressed communication (LoDAdaC) Input: α > 0, 0 ≤ β1 < 1, δ > 0, 0 ≤ γ ≤ 1, a maximum number T of communication rounds, a number K of local training steps per communication round, a η-compression operator Q, d-dimension vector-value functions {rt }, and a mixing matrix W; −1 −1 0 0 0 0 0 0 0 2 Let x1 = x2 = · · · = xn = x1 = x2 = · · · = xn = x , and set mi , and ui to 0 for each i. 3 for t = 0, 1, · · · , T K − 1 do 4 for all agents i ∈ {1, 2, . . . , n} in parallel do 5 Obtain one random sample ξit and compute a stochastic gradient git ← ∇Fi (xti , ξit ); 6 Let mti = β1 mt−1 + (1 − β1 ) git ; i t 0 1 7 Let ui = rt (gi , gi , . . . , git ); 1

t+ 12

i = xti − α √ t−1

Update xi

if mod(t + 1, K) = 0, then

= xti + Q[xi Set xt+1 i

t+ 21

+δ

;

Pn t+ 1 − xt+1 ). − xti ] and xt+1 = xi 2 + γ( j=1 Wji xt+1 j i i

else

t+ 12

Update xt+1 = xi i

= xti . , and xt+1 i

The condition in line 9 of Algorithm 1 indicates that neighbor communication happens every K iterations, namely, K local updates are performed Pn per communication round. In addition, we only need to communicate the compressed vectors to obtain j=1 Wji xt+1 j , as explained below. For each i = 1, 2, . . . , n, let agent i 0 maintain a vector yi and initialize it as yii = x0i . Then, for all t ≥ 0, let yit+1 = yit , if mod(t + 1, K) ̸= 0, h 1 P t+ t+ 1 n and yit+1 = yit + j=1 Wji Q xj 2 − xtj otherwise. This way, we have xt+1 = xi 2 + γ yit+1 − xt+1 and i i thus enable the reduction of communication cost by only communicating compressed message. With appropriate parameter β1 and vector function rt , the local update of LoDAdaC in line 8 of Algorithm 1 encompasses several well known optimizers as special cases. As we demonstrate in Section 3.2, our theoretical results apply to all optimizers listed in Table 2. Optimizer

Description

Vanilla SGD

β1 = 0 and rt ≡ 0, i.e., uti = 0 for all i and t

Momentum (Heavy-ball) SGD

β1 ∈ (0, 1) and rt ≡ 0, i.e., uti = 0 for all i and t

AMSGrad

b ti = β2 u b t−1 u + (1 − β2 )git ◦ git , i −1 b i = 0, and β2 ∈ (0, 1) u

Adam

uti = β2 ut−1 + (1 − β2 )git ◦ git , with β2 ∈ i

Adam-mini Averaged AdaGrad

b ti }, uti = max{ut−1 ,u i h √

√ TK , 1 T K+1 h √ t−1 K t t t ui = β2 ui +(1 −β2 )mean(gi ◦gi ), with β2 ∈ √T TK+1 ,1 Pt 1 s s uti = t+1 s=0 gi ◦ gi

Table 2: Representative optimizers of Algorithm 1 with specific selections of β1 and rt 3.2

Convergence analysis

In this subsection, we establish the convergence rate results of Algorithm 1. We first derive a consensus error bound in Lemma 3.1. This bound is essential because it explicitly characterizes the relationship between 7

Published in Transactions on Machine Learning Research (04/2026)

the consensus error and key algorithmic parameters, including the step size α, MLT steps K, compression error η of Q, and the spectral gap ρ of the communication graph. Such a characterization allows us to rigorously analyze how MLT and compression impact the convergence speed. Then we establish a bound in Theorem 3.1 on the objective gradient at averaged points. This bound enables us to show the final convergence rate results of our algorithm with several specific choices of popular adaptive updates. All proofs are given in the appendix. 2

) K−1 Lemma 3.1 Under Assumptions 1–3, let 0 < γ ≤ (1−ρ)(1−η . Then the sequence {xt }Tt=0 generated by 100 Algorithm 1 satisfies

T K−1 56 80 15 1 X h t 2i 2 2 ≤ α nK C, where C := B 2 δ −1 . E X⊥ + T K t=0 γ(1 − ρ) γ(1 − ρ) 1 − η 2

(3)

Theorem 3.1 Suppose that Assumptions 1–3 hold and ∥uti ∥∞ ≤ Bu for all t ≥ 0 and i ∈ {1, 2, . . . , n}, for some Bu > 0. Let C denote the constant defined in (3) and α, γ > 0 satisfy α≤

δ √ , 48L Bu + δ

γ≤

(1 − ρ)(1 − η 2 ) . 100

(4)

K−1 Then the sequence {xt }Tt=0 generated by Algorithm 1 satisfies TX K−1 α αT K α2 L2 β12 B 2 √ E ∥∇f xt ∥2 ≤ E f x0 − f ∗ + √ 4 Bu + δ t=0 8 Bu + δ δ(1 − β1 )2   2 TX K−1 n 2 2 p X 1 αβ1 B∞ 1 1   q + 4 Bu + δ + αL E  −q  2 (1 − β1 ) n i=1 t=0 ut−2 +δ ut−1 +δ i i 6L2 2 24 T KB 2 + α T nK 3 C + α2 L nδ nδ √ TX K−1 3 2 2 2 √ 2 Bu + δ α β1 L B Bu + δ αL 1 1 2 3 √ + + √ α T nK C + + . n δ δ(1 − β1 )2 δ 2 δ 2 δ t=0

(5)

t For each optimizer # condition ∥ui ∥∞ ≤ Bu , ∀ t, ∀ i for some constant " listed in Table 2, we are able to show the 2 PT K−1 1 Pn 1 1 √ t−2 − √ t−1 is bounded; see Lemma A.7. Thus by Theorem Bu and that E i=1 t=0 n ui

+δ

3.1, we specify the choice of α and obtain the convergence rate of Algorithm 1 by different ways of defining the second momentum term uti in line 7 of Algorithm 1. Theorem 3.2 Under Assumptions 1–3, let δ = O(1) be a universal positive constant and C be the constant defined in (3). Choose T and K such that α and γ > 0 satisfy α=

4θ

2 + δ) n(B∞ √ ≤ min TK

(

) δ p ,1 , 2 +δ 48L B∞

γ≤

(1 − ρ)(1 − η 2 ) , 100

(6)

K−1 where θ = O(1) is a constant. Then for the sequence {xt }Tt=0 generated by Algorithm 1 with any optimizer in Table 2, we have

T K−1 1 X 1 f (x0 ) − f ∗ + 1 n nKC √ E ∥∇f (xt )∥2 + ∥Xt⊥ ∥2 = O + + . T K t=0 n TK T nT K 8

(7)

Published in Transactions on Machine Learning Research (04/2026)

3.3

Linear speed up, topology independence, and communication reduction

Based on the convergence rate results in Theorem 3.2, we discuss how the number n of agents, the number K of local updates, and compression ratio 1 − η affect the iteration complexity and communication complexity of our algorithm to produce an ϵ-stationary point in expectation. Linear speed up and topology-independent step size. By (7) and the definition of C in (3), if n3 K 3 T =Ω , (8) (1 − ρ)8 (1 − η 2 )4 1 1 = O( √nT then nKC ), TnK = O( √nT ), and we obtain T K K

T K−1 2 1 1 X 1 t t 2 √ E ∥∇f x ∥ + ∥X⊥ ∥ = O . T K t=0 n nT K

(9)

Letting τ be selected from {0, . .. , T K − 1} uniformly at random, we have from (9) that 1 . Hence, to obtain an ϵ-stationary point in expectation, the total E ∥∇f (xτ )∥2 + n1 ∥Xτ⊥ ∥2 = O √nT K number of local iterations per agent is T K = Θ nϵ14 . (1−ρ)2 (1−η 2 ) 1 , the chosen T will satisfy (8) and the first Given K, we have T = Θ nKϵ 4 ; when ϵ = O nK inequality in (6) holds. Thus in this case, we obtain a linear speed up with respect to n, and the step size α = Θ(nϵ2 ) and is independent of ρ and η. For a small 0, we can further reduce the enough ϵ > 1 (1−ρ)2 (1−η 2 ) ν order of communication rounds by picking K. Suppose ϵ = O for some ν ∈ (0, 1). Then n −3−ν we can choose K = Θ ϵ−1+ν and T = Θ ϵ n , which satisfies (8). This way, compared to performing a Multiplied reduction of communication cost.

single local update, i.e., K = 1, we reduce the number of communication rounds by an order of ϵ−1+ν . In addition, by using an η-compression operator, our algorithm only needs 1 − η of communication amount as compared to using no compression. Therefore, the total communication volume required by our algorithm is Θ nϵ1−η 3+ν , achieving multiplied reduction of the total communication cost.

Numerical experiments

In this section, we demonstrate the efficacy of the proposed framework over a set of numerical experiments. We consider three standard benchmarks, including training a convolutional neural network LeNet5 (LeCun et al., 1998) on the FashionMNIST dataset (Xiao et al., 2017), a ResNet architecture Fixup-ResNet-20 (Zhang et al., 2019) on the CIFAR-10 dataset (Krizhevsky et al., 2009), and a small-scale 10.7M parameter GPT model, from nanoGPT (Andrej, 2022), on the tiny-shakespeare dataset. We will show the performance of LoDAdaC equipped with the following adaptive gradient updates: AdaGrad, Adam, and AMSGrad on homogeneously distributed training data. We will compare LoDAdaC against SQuARM-SGD (Singh et al., 2021), which incorporates compressed communication and local training with a momentum-based SGD. Our methods improve over SQuARM-SGD with the addition of an adaptive update. We provide an additional comparison against DADAM (Nazari et al., 2022), which represents methods with decentralized and compressed communication but always with a single local update per communication round. A final experimental baseline for comparison is CDProxSGT (Yan et al., 2023), which represents non-adaptive methods with no local updates, for the sake of completeness. We implement all of these methods in PyTorch. For FashionMNIST and CIFAR-10, we run our experiments on a CPU server. This server has two-way 64-core (256 threads) AMD EPYC 7742 CPUs at 2.25GHz and 2TB DDR4 memory. For tiny-shakespeare on nanoGPT, we run the experiments on a separate server with 4 NVIDIA A100 GPUs. Both test systems have Python 3.12.3 and PyTorch 2.7.0+cu126 installed, running on top of Ubuntu 24.04.2 LTS. The code and experimental scripts for our methods are publicly available at https://github.com/DecentralizedMethods/LoDAdaC. 9

Published in Transactions on Machine Learning Research (04/2026)

0 25

Epochs

0 20

0 25

0 20

0 15

Epochs

10 5

0 10

Epochs

0 15

0 10

0.0

10 4

10 3

10 2

DistributedAMSGrad DistributedAdaGrad DistributedAdam DADAM SQuARM-SGD CDProxSGT

0.5

10 1

1.0

100 Consensus Error

Training Loss

1.5

101

80 Test Accuracy

DistributedAMSGrad DistributedAdaGrad DistributedAdam DADAM SQuARM-SGD CDProxSGT

2.0

7 6 5 4 3

10 4

0 60

Epochs

0 60

0 50

0 40

Epochs

0 30

0 60

0 50

0 40

0 30

0 20

0 10

10 2

10 6

2 Epochs

100 Consensus Error

DistributedAMSGrad DistributedAdaGrad DistributedAdam DADAM SQuARM-SGD CDProxSGT

8 Validation Loss

DistributedAMSGrad DistributedAdaGrad DistributedAdam DADAM SQuARM-SGD CDProxSGT

8 7 6 5 4 3 2 1

Training Loss

(a) CIFAR-10 optimizer comparison.

(b) tiny-shakespeare optimizer comparison.

Figure 1: Optimizer Comparison: Plotted above are the training loss, test accuracy, and consensus error of CIFAR-10 (top) and the training loss, validation loss, and consensus error of tiny-shakespeare (bottom) with training done on all of the various optimizers.

We will compare training loss, test accuracy, and consensus error, as well as validation loss for the GPT model. We will compare these values relative to the number of communication rounds and the communication volume. We ran a significant parametric study, evaluating possible parameters within: local updates K = [1, 2, 5, 10, 20, 50], optimizers = [AdaGrad, Adam, AMSGrad, DADAM, SQuARM-SGD, CDProxSGT], Top-k compression = [30%, 40%, 50%, 60%, None], agents = [4, 9, 16], topology = [ring, 2D-grid], data distribution = [IID, Dirichlet(1.0), Dirichlet(0.5)]. We will show a representative selection of these results below on CIFAR-10 and tiny-shakespeare, with FashionMNIST and the rest of the results appearing in the appendix. We use a batch size of 64 for the CIFAR-10 and FashionMNIST datasets and a batch size of 128 for training the GPT model. We initialize the learning rate to 0.001 for AdaGrad, Adam, and AMSGrad on CIFAR-10 and FashionMNIST and use β values of β1 = 0.9, β2 = 0.999 for Adam and AMSGrad. We use a learning rate of 0.0001 on tiny-shakespeare. We tune the learning rate to 0.01 for SQuARM-SGD on CIFAR-10 and FashionMNIST and 0.005 on tiny-shakespeare — higher learning rates, such as the recommended learning rates of 0.1 and 0.2 from (Singh et al., 2021), did not converge with a number of tests when using our Top-k compression operator. 4.1

Optimizer Comparison

We first compare the performance of different optimizers with n = 4 agents with a fixed local updates per communication of K = 20 and Top-k compression of 40% and 50% for CIFAR-10 and tiny-shakespeare, respectively. We display these results in Figures 1a and 1b. We compare against SQuARM-SGD, DADAM, and CDProxSGT as our baselines for this set of experiments. Similar results are plotted for other values of K in the appendix in Figure 7. We observe that SQuARM-SGD is slightly slower to converge on CIFAR-10 with the given hyperparameters, but it achieves a similar test accuracy. CDProxSGT converges significantly slower and does not achieve an equivalent test accuracy in the given number of epochs. The performance of both non-adaptive methods in terms of validation loss is significantly worse on the GPT model, a known issue of training language models with non-adaptive momentum SGD methods (Zhao et al., 2025). We note that across these experiments, 10

Published in Transactions on Machine Learning Research (04/2026)

1.0

0.5

Consensus Error

Training Loss

1.5

Test Accuracy

K=1 K=2 K=5 K=10 K=20 K=50

2.0

50 40 30

101

20 00 0

00 0

Communication Rounds

00 0

30 00 0

Communication Rounds

25 00 0

20 00 0

15 00 0

10 00 0

50 00

0 00

Communication Rounds

00 20

0 00 10

00 50

(a) CIFAR-10 reduction in communication rounds.

3.0 2.5 2.0

10 3

00 00 20

00 00

Communication Rounds

00 00 15

00 00 10

0 50

Communication Rounds

10 2 10 4

00 00

00 00 15

00 10

1.5

100 10 1

2.0

3.5

2.5

101 Consensus Error

3.0

4.0

Training Loss

3.5

Validation Loss

K=1 K=2 K=5 K=10 K=20 K=50

4.0

Communication Rounds

(b) tiny-shakespeare reduction in communication rounds.

K=50,Top-k=30% K=10,Top-k=40% K=2,Top-k=60% K=1,Top-k=None

10 4

10 3

10 2

10 1

Scaled Communication Volume

80 70 60 50 40 30 20 10

100 Consensus Error

2.00 1.75 1.50 1.25 1.00 0.75 0.50 0.25 0.00

Test Accuracy

Training Loss

Figure 2: Number of Local Updates: Plotted above are the training loss, test accuracy, and consensus error of CIFAR-10 (top) and the training loss, validation loss, and consensus error of tiny-shakespeare (bottom) with training done using the Adam optimizer across a number of possible K values from 1 to 50.

10 2

10 4

100

10 1

10 1 10 3 10 2 Scaled Communication Volume

100

10 4

10 1 10 3 10 2 Scaled Communication Volume

100

10 4 10 3 Scaled Communication Volume

10 2

(a) CIFAR-10 reduction in communication volume.

3.0 2.5 2.0

101

4.0

100

3.5

Consensus Error

Training Loss

3.5

Validation Loss

K=50,Top-k=30% K=10,Top-k=40% K=2,Top-k=60% K=1,Top-k=None

4.0

3.0 2.5

10 5

10 4 10 3 Scaled Communication Volume

10 2

10 2 10 3 10 4

2.0

1.5

10 1

10 5

10 4 10 3 Scaled Communication Volume

10 2

10 5

(b) tiny-shakespeare reduction in communication volume.

Figure 3: Communication Volume: Plotted above are the training loss, test accuracy, and consensus error of CIFAR-10 (top) and the training loss, validation loss, and consensus error of tiny-shakespeare (bottom) with training done using the Adam optimizer across a number of possible K and top-k values.

AdaGrad and Adam are generally most performant overall, though the performance of all methods contained within our framework is relatively similar. As such, we will focus on Adam in subsequent results. 11

Published in Transactions on Machine Learning Research (04/2026)

Consensus Error

25 0

Epochs

20 0

15 0

10 0

100

0 25

Epochs

101

0 20

Epochs

0 15

0 10

0.0

DistributedAdam:N=4,Ring DistributedAdam:N=9,Ring DistributedAdam:N=16,Ring

0.5

1.0

1.5

102

Test Accuracy

Training Loss

2.0

90 80 70 60 50 40 30 20 10

DistributedAdam:N=4,Ring DistributedAdam:N=9,Ring DistributedAdam:N=16,Ring

(a) CIFAR-10 with Adam agent scaling with ring topology.

10 1

10 2

Consensus Error

100

Epochs

25 0

Epochs

0 15

0 10

0.0

DistributedAdam:N=4,Grid DistributedAdam:N=9,Grid DistributedAdam:N=16,Grid

20 0

0.5

15 0

1.0

10 0

1.5

101

Test Accuracy

Training Loss

2.0

90 80 70 60 50 40 30 20 10

DistributedAdam:N=4,Grid DistributedAdam:N=9,Grid DistributedAdam:N=16,Grid

Epochs

(b) CIFAR-10 with Adam agent scaling with grid topology.

Figure 4: Larger Agent Counts and Differing Topology: Plotted above are the training loss, test accuracy, and consensus error of CIFAR-10 with training done using the Adam optimizer when scaling to 4, 9, and 16 agents on ring topology (top) and 2D grid topology (bottom). All experiments were run with K = 20 local updates per communication round.

4.2

Number of Local Updates

Our next set of experiments analyzes the effect of the number of local updates per communication round on training performance. Figures 2a and 2b give results with Adam training on CIFAR-10 and tiny-shakespeare using Top-k compression of 40% and 50%, respectively. We plot training loss, test accuracy/validation loss, and consensus error against the total number of communication rounds for K = 1 to K = 50. We run all experiments to the same number of epochs, which gives a reduction in communication rounds proportional to K. For CIFAR-10, we note only a 1% loss in maximum test accuracy with K = 50 local updates per communication compared to the baseline K = 1 instance. On tiny-shakespeare, we likewise observe less than a 1% degradation of minimum validation loss when comparing K = 50 to K = 1 local updates per communication. We observed similar results with the same experiments on FashionMNIST in Figure 6 in the appendix.

4.3

Communication Volume

We continue our experiments by giving the relative proportion of communication volume used by our framework with a selection of K and Top-k values, as compared to a K = 1 baseline without compressed communication. Figures 3a and 3b give such a comparison using Adam on CIFAR-10 and tiny-shakespeare. We overall observe a significant reduction in communication volume at a relatively low cost to optimization quality. On CIFAR-10, we observe no loss in quality between K = 2 with Top-k = 60% to K = 50 with Top-k = 30%, despite a reduction in communication volume of 50×. Comparing K = 50 with Top-k = 30% to the baseline with no compression or local updates, we note that we use only about 0.6% of the communication volume. The maximum test accuracies across all experiments are within a few percent of the baseline. We observe similar results on tiny-shakespeare when considering validation loss instead of test accuracy. 12

Consensus Error

10 1 10 2

0 00 00 12 00 00 14 00 00 16 00 00 10

00 80

00 60

00 40

00 16

Communication Rounds

00 00

00 80

00 60

0 20 00 0 40 00 0 60 00 0 80 00 0 10 00 00 12 00 00 14 00 00 16 00 00

100

10 3

0.0

0.5

1.0

101

Training Loss

1.5

80 70 60 50 40 30 20 10

K=1 K=2 K=5 K=10 K=20 K=50

2.0

Test Accuracy

Published in Transactions on Machine Learning Research (04/2026)

Communication Rounds

(a) CIFAR-10 with non-IID data following a Dirichlet α = 1.0 distribution.

50 40 30 20

00 16

Communication Rounds

0 00

00 00

Communication Rounds

00 00

0 00

00 60

00 40

00 0 40 00 0 60 00 0 80 00 0 10 00 00 12 00 00 14 00 00 16 00 00

Communication Rounds

10 1

0.0

100

0.5

101

Consensus Error

1.0

Training Loss

1.5

Test Accuracy

K=1 K=2 K=5 K=10 K=20 K=50

2.0

(b) CIFAR-10 with non-IID data following a Dirichlet α = 0.5 distribution.

Figure 5: Non-IID Data: Plotted above are the training loss, test accuracy, and consensus error when using the Adam optimizer on CIFAR-10 with non-IID data across K values from 1 to 50. We distribute data following a standard Dirichlet distribution process using α = 1.0 (top) and α = 0.5 (bottom).

4.4

Larger Agent Counts and Differing Topology

We demonstrate the linear scaling of our method by running experiments with 4, 9 and 16 agents in a ring and a 2D grid communication topology. Given in Figure 4 are plots of training loss, test accuracy, and consensus error for CIFAR-10 when using Adam optimizer. Similar results for AdaGrad and AMSGrad are displayed in Figure 10 in the appendix. We set K = 20 for all tests with Top-k = 40% compression. The 2D grid topology is defined as 3 × 3 for 9 agents and 4 × 4 for 16 agents. Note that the ring and grid topologies are equivalent for 4 agents. We observe relatively consistent results across all optimizers, with near-linear scaling in most cases. Minimum achieved training loss and maximum test accuracy are also relatively close, similar to as we previously observed in Figure 2 across varying K values. 4.5

Heterogeneous Training Data

Our final experiments examine non-IID (independent and identically distributed) training data, emulating the client drift due to heterogeneity often observed in real decentralized environments. We use a Dirichlet distribution to partition training data. We run experiments with Dirichlet(α) = [0.5, 1.0], using CIFAR-10, Adam optimizer, local updates K = [1, 2, 5, 10, 20, 50], and Top-k = 40%, with results shown in Figure 5. Our experiments were run for approximately 5× the number of communication rounds as the related IID tests shown in Figure 2a. We note that in the less skewed setup with Dirichlet parameter α = 1.0, our method achieves convergence and test accuracies similar to those in Figure 2a, though convergence occurs more slowly. Consensus error is also significantly more variable, as expected. However, the tests with larger numbers of local updates still convergence to the same test accuracies of the baselines given by our optimizer comparison in Figure 1a in significantly fewer communication rounds. With a more skewed Dirichlet parameter of α = 0.5, we note a more reduced rate of convergence, with many tests failing to reach an adequate test accuracy. Further experiments with lower α parameters down to α = 0.1 showed correspondingly slower convergence with many tests failing to converge at all. Overall, these tests empirically demonstrate that our method offers some resilience towards heterogeneous training data, though other methods will likely be required if class label distributions are very significantly skewed. 13

Published in Transactions on Machine Learning Research (04/2026)

Conclusions and Discussions

We propose a local training based decentralized algorithmic framework with adaptive local update and compressed communication. The local update of our framework encompasses several well-known optimizers as special cases, including vanilla SGD, momentum SGD, Adam, AMSGrad, AdaGrad, and Adam-Mini, and the established convergence results apply to all these optimizers. To the best of our knowledge, this is the first work to provide theoretical convergence guarantees for adaptive stochastic methods in MLT-based decentralized nonconvex optimization. Our empirical experiments further highlight the compounded benefits of integrating MLT with CC, demonstrating significant reductions in communication overhead without compromising convergence speed or accuracy. Our current analysis relies on a bounded-gradient assumption, and our language-model experiments are limited to a small-scale transformer benchmark. Extending the framework to weaker assumptions, stronger data heterogeneity, and larger language models is a natural direction for future work.

Acknowledgements The authors would like to thank three anonymous reviewers for their valuable comments. This work is partly supported by NSF grant DMS-2208394, ONR grant N000142212573, and also by IBM through the IBM-Rensselaer Future of Computing Research Collaboration.

References A. F. Aji and K. Heafield. Sparse communication for distributed gradient descent. In EMNLP 2017: Conference on Empirical Methods in Natural Language Processing, pp. 440–445. Association for Computational Linguistics (ACL), 2017. D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic. Qsgd: Communication-efficient sgd via gradient quantization and encoding. Advances in neural information processing systems, 30, 2017. K. Andrej. NanoGPT. https://github.com/karpathy/nanoGPT, 2022. Last Accessed March 2025. D. Basu, D. Data, C. Karakus, and S. Diggavi. Qsparse-local-sgd: Distributed sgd with quantization, sparsification and local computations. Advances in Neural Information Processing Systems, 32, 2019. J. Bernstein, Y. Wang, K. Azizzadenesheli, and A. Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning, pp. 560–569. PMLR, 2018. C. Chen, Shen, H. Huang, and W. Liu. Quantized adam with error feedback. ACM Transactions on Intelligent Systems and Technology (TIST), 12(5):1–26, 2021. C. Chen, L. Shen, W. Liu, and Z.-Q. Luo. Efficient-adam: Communication-efficient distributed adam. IEEE Transactions on Signal Processing, 2023a. L. Chen, W. Liu, Y. Chen, and W. Wang. Communication-efficient design for quantized decentralized federated learning. IEEE Transactions on Signal Processing, 72:1175–1188, 2024. X Chen, M Hong, S Liu, and R Sun. On the convergence of a class of adam-type algorithms for non-convex optimization. In 7th International Conference on Learning Representations, ICLR 2019, 2019. X. Chen, X. Li, and P. Li. Toward communication efficient adaptive gradient method. In Proceedings of the 2020 ACM-IMS on Foundations of Data Science Conference, pp. 119–128, 2020. X. Chen, B. Karimi, W. Zhao, and P. Li. On the convergence of decentralized adaptive gradient methods. In Asian Conference on Machine Learning, pp. 217–232. PMLR, 2023b. L. Condat, I. Agarskỳ, and P. Richtárik. Provably doubly accelerated federated learning: The first theoretically successful combination of local training and communication compression. Preprint, arXiv:2210.13277, 2022. 14

Published in Transactions on Machine Learning Research (04/2026)

L. Condat, A. Maranjyan, and P. Richtárik. LoCoDL: Communication-efficient distributed learning with local training and compression. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=PpYy0dR3Qw. J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011. H. Gao and H. Huang. Adaptive serverless learning. arXiv preprint arXiv:2008.10422, 2020. S. Ge and T.-H. Chang. Gradient tracking with multiple local sgd for decentralized non-convex learning. In 2023 62nd IEEE Conference on Decision and Control (CDC), pp. 133–138. IEEE, 2023. F. Haddadpour, M. M. Kamani, M. Mahdavi, and V. Cadambe. Local sgd with periodic averaging: Tighter analysis and adaptive synchronization. Advances in Neural Information Processing Systems, 32, 2019. F. Haddadpour, M. M. Kamani, A. Mokhtari, and M. Mahdavi. Federated learning with compression: Unified analysis and sharp guarantees. In International Conference on Artificial Intelligence and Statistics, pp. 2350–2358. PMLR, 2021. L. Hou, R. Zhang, and J. T. Kwok. Analysis of quantized models. In International Conference on Learning Representations, 2018. T. H. Hsu, H. Qi, and M. Brown. Measuring the effects of non-identical data distribution for federated visual classification. Preprint, arXiv:1909.06335, 2019. P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, et al. Advances and open problems in federated learning. Foundations and trends® in machine learning, 14(1–2):1–210, 2021. S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. T. Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International conference on machine learning, pp. 5132–5143. PMLR, 2020. D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. Preprint, arXiv:1412.6980, 2014. A. Koloskova, S. Stich, and M. Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, pp. 3478–3487. PMLR, 2019. A. Koloskova, N. Loizou, S. Boreiri, M. Jaggi, and S. Stich. A unified theory of decentralized sgd with changing topology and local updates. In International conference on machine learning, pp. 5381–5393. PMLR, 2020. A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. 2009. A. Lalitha, O. C. Kilinc, T. Javidi, and F. Koushanfar. Peer-to-peer federated learning on graphs. Preprint, arXiv:1901.11173, 2019. Guanghui Lan. First-order and stochastic optimization methods for machine learning, volume 1. Springer, 2020. Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998. L. Li, Y. Fan, M. Tse, and K. Lin. A review of applications in federated learning. Computers & Industrial Engineering, 149:106854, 2020. X. Li, W. Yang, S. Wang, and Z. Zhang. Communication efficient decentralized training with multiple local updates. stat, 1050:21, 2019. 15

Published in Transactions on Machine Learning Research (04/2026)

X. Li, B. Karimi, and P. Li. On distributed adaptive optimization with gradient compression. In International Conference on Learning Representations, 2022. W. Liu, A. Panda, U. Pandey, C. Brissette, Y. Shen, G. Slota, N. Wang, J. Chen, and Y. Xu. Compressed decentralized momentum stochastic gradient methods for nonconvex optimization. Transactions on Machine Learning Research, 2025. ISSN 2835-8856. URL https://openreview.net/forum?id=RqhMQHHkB4. G. Mancino-Ball, Y. Xu, and J. Chen. A decentralized primal-dual framework for non-convex smooth consensus optimization. IEEE Transactions on Signal Processing, 71:525–538, 2023. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communication-efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp. 1273–1282. PMLR, 2017. P. Nazari, D. A. Tarzanagh, and G. Michailidis. Dadam: A consensus-based distributed adaptive gradient method for online optimization. IEEE Transactions on Signal Processing, 70:6065–6079, 2022. A. Nedić, A. Olshevsky, and M. G. Rabbat. Network topology and communication-computation tradeoffs in decentralized optimization. Proceedings of the IEEE, 106(5):953–976, 2018. S. Reddi, S. Kale, and S. Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018. S. Reddi, Z. Charles, M. Zaheer, Z. Garrett, K. Rush, J. Konečnỳ, S. Kumar, and H. B. McMahan. Adaptive federated optimization. In International Conference on Learning Representations, 2020. S. J. Reddi, A. Hefny, S. Sra, B. Poczos, and A. Smola. Stochastic variance reduction for non-convex optimization. In International conference on machine learning, pp. 314–323. PMLR, 2016. A. Reisizadeh, A. Mokhtari, H. Hassani, A. Jadbabaie, and R. Pedarsani. Fedpaq: A communicationefficient federated learning method with periodic averaging and quantization. In International conference on artificial intelligence and statistics, pp. 2021–2031. PMLR, 2020. N. Singh, D. Data, J. George, and S. Diggavi. Squarm-sgd: Communication-efficient momentum sgd for decentralized optimization. IEEE Journal on Selected Areas in Information Theory, 2(3):954–969, 2021. A. Spiridonoff, A. Olshevsky, and Y. Paschalidis. Communication-efficient sgd: From local sgd to one-shot averaging. Advances in Neural Information Processing Systems, 34:24313–24326, 2021. S. U. Stich. Local sgd converges fast and communicates little. Preprint, arXiv:1805.09767, 2018. S. U. Stich, J.-B. Cordonnier, and M. Jaggi. Sparsified sgd with memory. Advances in neural information processing systems, 31, 2018. J. Sun, X. Wu, H. Huang, and A. Zhang. On the role of server momentum in federated learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 15164–15172, 2024. T. Sun, D. Li, and B. Wang. Decentralized federated averaging. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(4):4289–4301, 2022. X. Sun, N. Wang, C. Chen, J. Ni, A. Agrawal, X. Cui, S. Venkataramani, K. El Maghraoui, V. V. Srinivasan, and K. Gopalakrishnan. Ultra-low precision 4-bit training of deep neural networks. Advances in Neural Information Processing Systems, 33:1796–1807, 2020. Y. Sun, L. Shen, H. Sun, L. Ding, and D. Tao. Efficient federated learning via local adaptive amended optimizer with linear speedup. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(12): 14453–14464, 2023. N. Wang, J. Choi, D. Brand, C Chen, and K. Gopalakrishnan. Training deep neural networks with 8-bit floating point numbers. Advances in neural information processing systems, 31, 2018. 16

Published in Transactions on Machine Learning Research (04/2026)

Y. Wang, L. Lin, and J. Chen. Communication-compressed adaptive gradient method for distributed nonconvex optimization. In International Conference on Artificial Intelligence and Statistics, pp. 6292–6320. PMLR, 2022a. Y. Wang, L. Lin, and J. Chen. Communication-efficient adaptive federated learning. In International conference on machine learning, pp. 22802–22838. PMLR, 2022b. Z. Wang, J. Zhang, X. Wu, and M. Johansson. From promise to practice: Realizing high-performance decentralized training. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=lo3nlFHOft. T. Wu, Z. Li, and Y. Sun. The effectiveness of local updates for decentralized learning under data heterogeneity. IEEE Transactions on Signal Processing, 2025. H. Xiao, K. Rasul, and R. Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. Preprint, arXiv:1708.07747, 2017. L. Xiao and S. Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1): 65–78, 2004. C. Xie, O. Koyejo, I. Gupta, and H. Lin. Local adaalter: Communication-efficient stochastic gradient descent with adaptive learning rates. Preprint, arXiv:1911.09030, 2019. H. Xing, O. Simeone, and S. Bi. Decentralized federated learning via sgd over wireless d2d networks. In 2020 IEEE 21st international workshop on signal processing advances in wireless communications (SPAWC), pp. 1–5. IEEE, 2020. Y. Xu, Y. Xu, Y. Yan, C. Sutcher-Shepard, L. Grinberg, and J. Chen. Parallel and distributed asynchronous adaptive stochastic gradient methods. Mathematical Programming Computation, 15(3):471–508, 2023. Y. Yan, J. Chen, P.-Y. Chen, X. Cui, S. Lu, and Y. Xu. Compressed decentralized proximal stochastic gradient method for nonconvex composite problems with heterogeneous data. In International Conference on Machine Learning, pp. 39035–39061. PMLR, 2023. H. Yu, S. Yang, and S. Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 5693–5700, 2019. H. Zhang, Y. N. Dauphin, and T. Ma. Fixup initialization: Residual learning without normalization. In International Conference on Learning Representations, 2019. S. Zhang, A. E. Choromanska, and Y. LeCun. Deep learning with elastic averaging sgd. Advances in neural information processing systems, 28, 2015. Y. Zhang, C. Chen, Z. Li, T. Ding, C. Wu, D. P. Kingma, Y. Ye, Z.-Q. Luo, and R. Sun. Adam-mini: Use fewer learning rates to gain more. Preprint, arXiv:2406.16793, 2024. R. Zhao, D. Morwani, D. Brandfonbrener, N. Vyas, and S. M. Kakade. Deconstructing what makes a good optimizer for autoregressive language models. In The Thirteenth International Conference on Learning Representations, 2025. W. Zhao, X. Jiao, M. Hu, X. Li, X. Zhang, and P. Li. Paddlebox: Communication-efficient terabyte-scale model training framework for online advertising. In 2022 IEEE International Conference on Big Data (Big Data), pp. 1401–1408. IEEE, 2022.

Published in Transactions on Machine Learning Research (04/2026)

Convergence analysis of compressed decentralized algorithms with multiple local adaptive gradient updates under nonconvex settings

In this section, we give a complete analysis of our decentralized algorithmic framework. We write the updates of Algorithm 1 in the more compact matrix form for all t ∈ [T K], Mt = β1 Mt−1 + (1 − β1 )Gt ,

(10)

Update U ≥ 0,

(11)

Mt Yt = √ , Ut−1 + δ

(12)

Xt+ 2 = Xt − αYt ,

(13) i

− Xt ,

(14)

+ γXt+1 (W − I),

(15)

t+ 12

if mod(t + 1, K) = 0, then Xt+1 = Xt + Q X t+ 12

Xt+1 = X else, X

t+1

t+ 12

t+1

, X

=X,

(16)

where Gt = g1t , g2t , . . . , gnt , Mt = mt1 , mt2 , . . . , mtn , X = [x1 , x2 , . . . , xn ] , Q [X] = [Q[x1 ], Q[x2 ], . . . , Q[xn ]] . We let x=

1 1 1 t X1, X = XJ = x1⊤ , mt = Mt 1, yt = Yt 1, Y = YJ. n n n

First we establish bounds on the sequence {Mt }, {Ut } and {Yt }. Lemma A.1 Under Assumption 3, it holds that for any t ∈ [T K], √ √ √ 1 nB ≤ nB, ∥Yt ∥≤ nBδ − 2 , ∥Mt ∥≤ 1 − β1t+1 ∥mti ∥≤ B,

∥m ∥≤ B,

t ∥Y⊥ ∥≤

√

nBδ − 2 ,

∥mti ∥∞ ≤ B∞ , ∀ i ∈ {1, 2, . . . , n}.

(17) (18)

Proof. From the update of m, i.e., mti = β1 mt−1 + (1 − β1 ) git , we have that for any t ≥ 0 and each i i ∈ {1, 2, . . . , n}, ∥mti ∥= ∥β1 mt−1 + (1 − β1 )gti ∥≤ β1 ∥mt−1 ∥+(1 − β1 )∥gti ∥≤ β1 ∥mt−1 ∥∞ +(1 − β1 )B, i i i where the second inequality holds from ∥git ∥≤ B by Assumption 3. Recursively applying the inequality above and noticing m−1 = 0, we obtain i ∥mti ∥≤ 1 + β1 + β12 + . . . + β1t (1 − β1 )B = 1 − β1t+1 B ≤ B. √ Hence, it holds ∥mt ∥≤ B and ∥Mt ∥≤ 1 − β1t+1 nB. Now by Ut ≥ 0, we immediately have ∥Yt ∥= √ t 2 t 2 t 2 1 2 t 2 √ M ≤ nBδ − 2 , and ∥Y⊥ ∥ = Yt − Y = ∥Yt ∥ − Y ≤ nB δ . t−1 U

+δ

In addition, we have that for any t ≥ 0 and each i ∈ {1, 2, . . . , n}, ∥mti ∥∞ = ∥β1 mt−1 + (1 − β1 )gti ∥∞ ≤ β1 ∥mt−1 ∥∞ +(1 − β1 )∥gti ∥∞ ≤ β1 ∥mt−1 ∥∞ +(1 − β1 )B∞ , i i i where the second inequality follows from ∥git ∥∞ ≤ B∞ by Assumption 3. Recursively applying the inequality above and noticing m−1 = 0, we obtain i ∥mti ∥∞ ≤ 1 + β1 + β12 + . . . + β1t (1 − β1 )B∞ = 1 − β1t+1 B∞ ≤ B∞ . □

The proof is then completed. The next lemma shows the bound of the consensus error of X. 18

Published in Transactions on Machine Learning Research (04/2026)

) Lemma A.2 Under Assumptions 1–3, let ρb = 1 − ρ, 0 < γ ≤ (1−ρ)(1−η , and Q be an η-compression 100 operator with η ≥ 0. Then, the following statements hold:

(i) For any r ∈ [T ], it holds 2 h i 2 γ ρb γ ρb 2 (r+1)K X⊥ ≤ 1+ 1− E XrK ⊥ 16 2 2 16 2 γ ρb +2 1+ γ 1+ E XrK − X(r+1)K α2 K 2 nB 2 δ −1 . +4 1+ 16 ρb γ ρb

(19)

(ii) For any r ∈ [T ], it holds E

i h γ ρb 4 rK 2 ≤ 4γ 2 1 + E X ⊥ 16 1 − η 2 2 3 + η2 γ ρb + (1 + 8γ) 1 + E XrK − X(r+1)K 4 16 16 4 + 3 1+ +2 1+ α2 K 2 nB 2 δ −1 . γ ρb 1 − η2

X(r+1)K − X(r+2)K

(20)

(iii) It holds T K−1 56 80 15 1 X h t 2i 2 2 E X⊥ ≤ α nK C, where C := + B 2 δ −1 . T K t=0 γ ρb γ ρb 1 − η 2 If in addition γ = Θ((1 − ρ)(1 − η 2 )), we have C := Θ

B2 (1−ρ)4 (1−η 2 )2

(21)

Proof. (i) From the update rules (13)–(16), we have, for all s ∈ [K − 1], XrK+s+1 = XrK+s − αYrK+s , and for the final step in the block of size K, we conduct the compressed communication step. First, using (18) and the inequality (a + b)2 ≤ (1 + η1 )a2 + (1 + η1−1 )b2 for any η1 > 0, we have ∥XrK+s+1 ∥2 = ⊥

XrK ⊥ −α

s X

2 rK+i Y⊥

i=0 −1 2 2 ≤(1 + η1 )∥XrK ⊥ ∥ +(1 + η1 )α

s X

2 rK+i Y⊥

i=0 −1 rK 2 2 2 ≤(1 + η1 )∥X⊥ ∥ +(1 + η1 )K α nB 2 δ −1 ,

(22) , ∀s ∈ [K − 1].

Next, we analyze the case of s = K − 1. By (15), it holds that (r+1)K

X⊥

= X(r+1)K− 2 − X(r+1)K J + γX(r+1)K (W − I).

Noticing X(r+1)K J = X(r+1)K− 2 J from (14)–(15), and J(W − I) = 0, we have (r+1)K

X⊥

= X(r+1)K− 2 − X(r+1)K− 2 J + γ(X(r+1)K − X(r+1)K− 2 J)(W − I) 1

= X(r+1)K− 2 (I − J)((1 − γ)I + γW) + γ(X(r+1)K − X(r+1)K− 2 )(W − I). 19

(23)

Published in Transactions on Machine Learning Research (04/2026)

c = (1 − γ)I + γW. For any η2 > 0, it then holds Denote W (r+1)K

X⊥

2 1 γ X(r+1)K − X(r+1)K− 2 (W − I) 2 2 1 c + 4 1 + η −1 γ 2 X(r+1)K − X(r+1)K− 12 , ≤(1 + η2 ) X(r+1)K− 2 (I − J)W 2

1 c ≤(1 + η2 ) X(r+1)K− 2 (I − J)W

+ 1 + η2−1

(24)

where the second inequality follows from ∥W − I∥2 ≤ 2. Recalling ρb = 1 − ρ and by (I − J)J = 0, we have 1 c X(r+1)K− 2 (I − J)W 1

≤(1 − γ) X(r+1)K− 2 (I − J) + γ X(r+1)K− 2 (I − J)W =(1 − γ) X(r+1)K− 2 (I − J) + γ X(r+1)K− 2 (I − J)(W − J) 1

≤(1 − γ) X(r+1)K− 2 (I − J) + γρ X(r+1)K− 2 (I − J) 1

=(1 − γ ρb) X(r+1)K− 2 (I − J) .

(25)

Substituting (25) into (24), we obtain (r+1)K

X⊥

≤(1 + η2 )(1 − γ ρb)2 X(r+1)K− 2 (I − J)

1 + 4 1 + η2−1 γ 2 X(r+1)K − X(r+1)K− 2

t For the first term in the RHS of (26), using the bound ∥Y⊥ ∥≤ 1

X(r+1)K− 2 (I − J) (r+1)K−1

= X⊥

(r+1)K−1

√

≤ (1 + η1 ) XrK ⊥

(26)

nBδ − 2 , we have

2 X(r+1)K−1 − αY(r+1)K−1 (I − J) 2

+ 1 + η1−1 α2 K 2 nB 2 δ −1 .

For the second term in the RHS of (26), using the bound ∥Yt ∥≤ X

− αY⊥

(22)

(r+1)K

−X

(r+1)K− 12

= X

(r+1)K

√

−X

(27) 1

nBδ − 2 , we have

+α

K−1 X

rK+i

i=0

≤(1 + η1 ) X

(r+1)K

−X

+ (1 + η1−1 )α2

K−1 X

rK+i

i=0

≤(1 + η1 ) X(r+1)K − XrK

+ 1 + η1−1 α2 K 2 nB 2 δ −1 .

(28)

Plugging (27)–(28) back into (26), we arrive at (r+1)K

X⊥

2 + 4 1 + η2−1 γ 2 (1 + η1 ) X(r+1)K − XrK + (1 + η2 )(1 − γ ρb)2 + 4 1 + η2−1 γ 2 1 + η1−1 α2 K 2 nB 2 δ −1 .

≤(1 + η2 )(1 − γ ρb)2 (1 + η1 ) XrK ⊥

(29)

Published in Transactions on Machine Learning Research (04/2026)

ρ ρ Let η1 = γ16b and η2 = γ2b . By the definition of γ, 0 < γ ρb < 1, we then have 2 γ ρb γ ρb 2 1− , (1 + η2 )(1 − γ ρb) (1 + η1 ) ≤ 1 + 16 2 2 γ ρb 4 1 + η2−1 γ 2 (1 + η1 ) ≤ 4 1 + γ 1+ , 16 ρb 16 . (1 + η2 )(1 − γ ρb)2 + 4 1 + η2−1 γ 2 1 + η1−1 ≤ 2 1 + γ ρb

(30) (31) (32)

We then complete the proof of (19) by using the inequalities (30)-(32) in (29). (ii) From (14) and Definition 1.1, for any η3 > 0, it holds that i h 2 2 1 E X(r+2)K − X(r+1)K = E X(r+2)K−1 + Q X(r+2)K− 2 − X(r+2)K−1 − X(r+1)K h i 2 1 1 1 =E X(r+2)K−1 − X(r+2)K− 2 + X(r+2)K− 2 − X(r+1)K + Q X(r+2)K− 2 − X(r+2)K−1 h i 2 1 1 ≤(1 + η3 )E X(r+2)K− 2 − X(r+2)K−1 − Q X(r+2)K− 2 − X(r+2)K−1 1

+ (1 + η3−1 )E X(r+2)K− 2 − X(r+1)K 1

≤(1 + η3 )η 2 E X(r+2)K− 2 − X(r+2)K−1

+ (1 + η3−1 )E X(r+2)K− 2 − X(r+1)K

For the second term in the RHS of (33), using the bound ∥Yt ∥≤ 1

X(r+2)K− 2 − X(r+1)K

= α2

K−1 X

√

(33)

nBδ − 2 , we obtain 2

≤ α2 K 2 nB 2 δ −1 .

Y(r+1)K+i

(34)

i=0

For the first term in the RHS of (33), by X(r+2)K−1 = X(r+1)K and ∥Yt ∥≤ have (r+2)K− 12

E X

−X

(r+2)K−1

=E X

(r+1)K

−α

K−1 X

√

nBδ − 2 , for any η4 > 0, we 2

(r+1)K+i

−X

(r+1)K

i=0 (r+1)K

≤(1 + η4 )E X

−X

(r+1)K

+ (1 + η4−1 )E

K−1 X

(r+1)K+i

i=0

≤(1 + η4 )E X(r+1)K − X(r+1)K

+ (1 + η4−1 )α2 K 2 nB 2 δ −1 .

(35)

Substituting (34)–(35) into (33), we have 2

E X(r+2)K − X(r+1)K 2 ≤(1 + η3 )η 2 (1 + η4 )E X(r+1)K − X(r+1)K + (1 + η4−1 )α2 K 2 nB 2 δ −1 + (1 + η3−1 )α2 K 2 nB 2 δ −1 .

(36)

We now bound X(r+1)K − X(r+1)K . By (23), we have that for any η5 > 0, 2 (r+1)K (r+1)K E X −X 2 (r+1)K (r+1)K− 12 (r+1)K− 12 (I − J)(W − I) =E X −X (γ(W − I) − I) + γX 2 2 (r+1)K− 12 2 (r+1)K −1 (r+1)K− 21 ≤ (1 + η5 ) (1 + 2γ) E X + 1 + η5 4γ E X⊥ −X

(37)

Published in Transactions on Machine Learning Research (04/2026)

where we have used JW = J in the equality and ∥γ(W − I) − I∥2 ≤ γ∥W − I∥2 +∥I∥2 ≤ 1 + 2γ and ∥W − I∥2 ≤ 2 in the inequality. For the first term in the RHS of (37), we know from (28) that for any η1 > 0, 1

X(r+1)K − X(r+1)K− 2

≤ (1 + η1 ) X(r+1)K − XrK

+ 1 + η1−1 α2 K 2 nB 2 δ −1 .

(38)

For the second term in the RHS of (37), we know from (27) that (r+1)K− 21

X⊥

= X(r+1)K− 2 (I − J)

≤ (1 + η1 ) XrK ⊥

+ 1 + η1−1 α2 K 2 nB 2 δ −1 .

Plugging (38) and (39) into (37), we have 2 (r+1)K (r+1)K E X −X 2 2 2 −1 2 −1 1 + η α K nB δ + ≤ 1 + η5−1 4γ 2 (1 + η1 ) XrK ⊥ 1 2 2 + (1 + η5 ) (1 + 2γ) (1 + η1 ) X(r+1)K − XrK + 1 + η1−1 α2 K 2 nB 2 δ −1 .

(39)

(40)

Combining (40) and (36), we arrive at E X(r+2)K − X(r+1)K

2 ≤(1 + η3 )η 2 (1 + η4 ) 1 + η5−1 4γ 2 (1 + η1 ) XrK ⊥ 2

+ (1 + η3 )η 2 (1 + η4 ) (1 + η5 ) (1 + 2γ) (1 + η1 ) X(r+1)K − XrK + (1 + η3 )η 2 (1 + η4 ) 1 + η5−1 4γ 2 1 + η1−1 α2 K 2 nB 2 δ −1 2 + (1 + η3 )η 2 (1 + η4 ) (1 + η5 ) (1 + 2γ) 1 + η1−1 α2 K 2 nB 2 δ −1

+ (1 + η3 )η 2 (1 + η4−1 )α2 K 2 nB 2 δ −1 + (1 + η3−1 )α2 K 2 nB 2 δ −1 .

(41)

2 (1−ρ)(1−η 2 ) γb ρ Let η3 = η4 = η5 = 1−η and 0 < η, ρb < 1, we have 4 , and η1 = 16 . By γ ≤ 100

3 + η2 γ ρb (1 + η3 )η (1 + η4 ) (1 + η5 ) (1 + 2γ) (1 + η1 ) ≤ (1 + 8γ) 1 + , 4 16 γ ρb 4 (1 + η3 )η 2 (1 + η4 ) 1 + η5−1 4γ 2 (1 + η1 ) ≤ 4γ 2 1 + , 16 1 − η 2 16 , (1 + η3 )η 2 (1 + η4 ) 1 + η5−1 4γ 2 1 + η1−1 ≤ 1 + γ ρb 16 2 −1 2 (1 + η3 )η (1 + η4 ) (1 + η5 ) (1 + 2γ) 1 + η1 ≤ 2 1 + , γ ρb 4 (1 + η3 )η 2 (1 + η4−1 ) + (1 + η3−1 ) ≤ 2 1 + . 1 − η2 2

(42) (43) (44) (45) (46)

We complete the proof of (20) by using the inequalities (42)-(46) in (41). h i 2 (r+1)K r rK 2 rK (iii) Denote Ω = E X⊥ +E X − X . Then, since 0 < η < 1, the two inequalities in (19) and (20) imply Ωk+1 ≤ A0 Ωk + A1 , 22

(47)

Published in Transactions on Machine Learning Research (04/2026)

where 2 γ ρb 4 2 γ ρb 3 + η2 + 4γ 2 , 4γ 1 + max 1− + (1 + 8γ) 16 2 1 − η2 ρb 4 80 15 A1 = α2 K 2 nB 2 δ −1 . + γ ρb 1 − η 2

A0 =

(48) (49)

By ρb = 1 − ρ, it holds that γ≤

(1 − ρ)(1 − η 2 ) ≤ min 100

7b ρ(1 − η 2 ) 2b ρ(1 − η 2 ) , 2 2 ρb + 32b ρ + 64 + 48b ρ + 16b ρη 128 + 2b ρ2 (1 − η 2 )

(50)

2 7b ρ(1−η 2 ) 2b ρ(1−η 2 ) ρ b ργ 4 Notice that γ ≤ + 4γ 2 1−η yields 1 − γ2b implies 2 ≤ 1 − 8 , and γ ≤ 2 2 2 +32b 128+2 b ρ (1−η ) b ρ ρ +64+48 b ρ+16b ρη 2 2 3+η b ρ γ 4γ 1 + 2 + 4 (1 + 8γ) ≤ 1 − 8 . Thus b ρ γ ρb ρbγ γ ρb A0 ≤ 1 + < 1. 1− ≤1− 16 8 16 From x0i = x0 = x0i , ∀ i ∈ {1, 2, . . . , n}, we have ∥X0⊥ ∥2 = 0 and X0 = 0. By (36) with r = −1 and (46), we have 2 4 2 ≤2 1+ A1 . E X0 − XK α2 K 2 nB 2 δ −1 ≤ 1 − η2 γ ρb Thus, multiplying both sides of (47) by Ar−k and summing it over k = 0, 1, . . . , r − 1 gives 0 Ωr ≤Ar+1 Ω0 + 0

r−1 X

Ar−k A1 ≤ Ω0 + 0

k=0

16 A1 γ ρb

2 16 A1 + E X 0 − X K γ ρb 16 4 18 ≤ A1 + 2 1 + A1 . α2 K 2 nB 2 δ −1 ≤ γ ρb 1 − η2 γ ρb

(51) (52)

Summing up the above inequality for all r = 0, 1, . . . , T − 1, we obtain T −1

1 X h rK 2 i 18 E X⊥ ≤ A1 . T r=0 γ ρb Summing (22) with η1 = 1 over s ∈ {0, 1, . . . , K − 2}, we derive that, for all r ∈ [T + 1], K−1

1 X 2 2 2 2 −1 ∥XrK+s ∥2 ≤ 2∥XrK . ⊥ ∥ +2K α nB δ ⊥ K s=1 This implies K−1

1 X 2 2 2 2 −1 ∥XrK+s ∥2 ≤ 3∥XrK . ⊥ ∥ +2K α nB δ ⊥ K s=0 Thus, we have T K−1 T −1 K−1 T −1 56 1 X 1 X 1 X 1 X 2 2 2 2 2 −1 E∥Xt⊥ ∥2 = E∥XrK+s ∥ ≤ 3E∥XrK ≤ A1 . ⊥ ∥ +2K α nB δ ⊥ T K t=0 T r=0 K s=0 T r=0 γ ρb

(53)

Published in Transactions on Machine Learning Research (04/2026)

□

This completes the proof. To prove the convergence of our algorithm, we define an auxiliary sequence as follows z t = xt +

β1 xt − xt−1 , ∀ t ∈ [T K], 1 − β1

(54)

with x−1 = x0 . The lemma below shows the difference of two consecutive z-points. Lemma A.3 Let {z t } be defined in (54). It holds that for all t ∈ [T K],   n n X β1 α 1 αX 1 gt   q q q i z t+1 − z t = − − , mt−1 ◦ i 1 − β1 n i=1 n i=1 ut−1 + δ ut−2 + δ ut−1 + δ i

(55)

where u−2 = 0. i Proof. By (12)–(16) and (W − I)J = 0, we have n

xt+1 = xt −

mti αX q . n i=1 ut−1 + δ

(56)

Thus by (54), we have β1 β1 xt+1 − xt − xt − xt−1 1 − β1 1 − β1 1 β 1 = xt+1 − xt − xt − xt−1 1 − β1 1 − β1     n n t−1 X mti α m β 1  αX 1 − −  q q i − = 1 − β1 n i=1 ut−1 + δ 1 − β1 n i=1 ut−2 + δ i i     n n t−1 t−1 t X X β1  α β1 mi + (1 − β1 ) gi  m 1  α  q q i − − − = 1 − β1 n i=1 1 − β n t−1 1 ui + δ ut−2 + δ i=1 i   n n X β1 α X t−1  gt 1 1 − α q i = mi ◦ q −q , 1 − β1 n i=1 n i=1 ut−1 + δ ut−2 + δ ut−1 + δ

z t+1 − z t = xt+1 − xt +

□

which is the desired result. Lemma A.4 Under Assumptions 1 and 3, it holds that for all t ∈ [T K], n

1X n i=1

2 L2 ∇fi xti − ∇fi xt ≤ ∥Xt⊥ ∥2 , n

(57)

and α2 L2 β12 B 2 ∥∇f z t − ∇f (xt )∥2 ≤ . δ(1 − β1 )2 Proof. First, by the L-smoothness of fi for each i ∈ {1, 2, . . . , n} and Young’s inequality, we have n

1X n i=1

n 2 L2 X t ∇fi xti − ∇fi xt ≤ ∥x − xt ∥2 , n i=1 i

(58)

Published in Transactions on Machine Learning Research (04/2026)

which indicates (57) by the definition of Xt⊥ . Also, by the L-smoothness of f , it follows (54) ∥∇f z t − ∇f (xt )∥2 ≤ L2 ∥z t − xt ∥2 = 2

n L2 β12 α2 X mt−1 i q ≤ (1 − β1 )2 n i=1 t−2 ui + δ

α X mt−1 q i n i=1 ut−2 + δ

L2 β12 = (1 − β1 )2

(56)

L2 β12 ∥xt − xt−1 ∥2 (1 − β1 )2

≤

α2 L2 β12 B 2 , δ(1 − β1 )2

where the last inequality holds by ∥mt−1 ∥≤ B from (18). This completes the proof. i

□

Lemma A.5 Under Assumptions 1–3, it holds that TX K−1

h E

z t+1 − z t

t=0



T K−1 n 2 2β 2 α2 B∞  X 1X ≤ 1 E  (1 − β1 )2 n i=1 t=0

+ 2α

1 q

ut−2 +δ i

−q

6L2 24 T KB 2 + E nδ nδ

1 ut−1 +δ i

"T K−1 X



# 2 Xt⊥

t=0

(59)

  6 + E δ

"T K−1 X

∇f (x )

# .

t=0

Proof. By (55) and Young’s inequality, we have TX K−1

h E

z t+1 − z t

t=0

  ≤E 2

TX K−1

β1 α 1 1 mt−1 ◦  q −q 1 − β1 n i=1 i t−2 t−1 u +δ u +δ

t=0





n X

T K−1

αX gt q i n i=1 ut−1 + δ

 X + E 2 t=0

 2   

  .

(60)

To bound the first term in the RHS of (60), we obtain from (18) that

TX K−1 t=0

≤

TX K−1 t=0

2 ≤B∞

  2 n 1 X t−1  1 1  m ◦ q −q n i=1 i t−2 t−1 u +δ u +δ i

 2 n 1X 1 1  mt−1 ◦ q −q i n i=1 t−2 t−1 u +δ u +δ 

TX K−1 t=0

1 1X 1 q −q n i=1 ut−2 +δ ut−1 +δ i i 25

(61)

Published in Transactions on Machine Learning Research (04/2026)

To bound the second term in RHS of (60), we have 

TX K−1

n 1X

t=0

n i=1

TX K−1

n X

 2E 

  ≤2E 

git q

 

ut−1 +δ i

git − ∇fi (xti ) + ∇fi (xti ) − ∇f (xt ) + ∇f (xt )

1 n i=1

t=0



ut−1 +δ i

  

2 2 TX K−1 TX K−1 n n 1 X (git − ∇fi (xti )) 1 X ∇fi (xti ) − ∇fi (xt ) q q ≤6E + n i=1 n i=1 t=0 t=0 ut−1 + δ ut−1 +δ i i

TX K−1 t=0

1 X ∇f (xt ) q n i=1 ut−1 + δ

2 TX K−1 TX K−1 n n 1 X (git − ∇fi (xti )) 1X q ≤6E + n i=1 n i=1 t=0 t=0 ut−1 + δ i

TX K−1 t=0

 =

6  E n2 t=0 

i=1

T K−1

1X ∇f (xt ) q n i=1 ut−1 +δ i

n TX K−1 X

∇fi (xti ) − ∇fi (xt ) q ut−1 +δ i

git − ∇fi (xti ) q ut−1 +δ i n





TX K−1

   + 6E  2

t=0

n X

1 n i=1

∇fi (xti ) − ∇fi (xt ) q ut−1 +δ i

  



∇f (xt )  X 1X  q + 6E   n t−1 t=0 ui + δ i=1 "T K−1 n # "T K−1 # n X X X 1X 6 6 2 2 ≤ 2 E git − ∇fi (xti ) + E ∇fi (xti ) − ∇fi (xt ) n δ δ n t=0 i=1 t=0 i=1 "T K−1 # n X X 6 1 2 + E ∇f (xt ) δ n t=0 i=1 "T K−1 "T K−1 # # X X 6 6L2 6 2 t 2 t 2 ≤ 2 4nT KB + E X⊥ + E ∇f (x ) , n δ nδ δ t=0 t=0

(62)

where in the last inequality, we have used (57), and the equality holds because *

+ (git − ∇fi (xti )) gjt − ∇fj (xtj ) q Et , q ut−1 +δ ut−1 + δ j i * + Et [git − ∇fi (xti )] Et [gjt − ∇fj (xtj )] q q = , = 0, ∀i ̸= j, t−1 u + δ ut−1 + δ j i from the fact that g1t , g2t , . . . , gnt are conditionally independent of each other. Plugging (61) and (62) into (60), we complete the proof. □ 26

Published in Transactions on Machine Learning Research (04/2026)

Lemma A.6 Suppose Assumptions 1 and 3 hold, and ∥uti ∥∞ ≤ Bu for all t ≥ 0 and i ∈ {1, 2, . . . , n}. It holds *

+ n t X 1 g  q i Et  ∇f z t , n i=1 ut−1 + δ i

1 L2 ≥ √ ∥∇f xt ∥2 − n 2 Bu + δ

√

(63)

Bu + δ 1 + √ δ 2 δ

∥Xt⊥ ∥2 −

α2 β12 L2 B 2 δ(1 − β1 )2

√

Bu + δ 1 + √ δ 2 δ

Proof. By Assumption 3, it holds that + * + n n t X 1X g ∇fi (xti ) 1 i t t   q q = ∇f z , Et ∇f z , n i=1 ut−1 + δ n i=1 ut−1 + δ i i * + n 1 X ∇fi (xti ) − ∇f (xt ) q = ∇f z t − ∇f (xt ), n i=1 ut−1 +δ i * + n 1 X ∇f (xt ) t t q + ∇f z − ∇f (x ), n i=1 ut−1 + δ i * + + * n n t X ∇fi (xi ) − ∇f (xt ) 1 1 X ∇f (xt ) t t q q + ∇f (x ), + ∇f (x ), . n i=1 n i=1 ut−1 + δ ut−1 + δ *

(64)

Next we bound each of the four terms in the RHS of (64). For the first term in the RHS of (64), we use Young’s inequality and (58) to have *

+ n 1 X ∇fi (xti ) − ∇f (xt ) q ∇f z − ∇f (x ), n i=1 ut−1 +δ i n 2 1 X 2 ∇f z t − ∇f (xt ) + ∇fi xti − ∇fi xt ≥− √ 2n δ i=1 n 1 X 2 2 ≥− √ ∇f z t − ∇f (xt ) + L2 xti − xt 2n δ i=1 2 2 2 2 (58) α β1 L B 1 L2 t 2 ∥X ∥ , ≥ − √ + ⊥ n 2 δ δ(1 − β1 )2 t

(65)

where we have used ut−1 ≥ 0 in the first inequality. For the second term in the RHS of (64), we have i * ∇f z

1 X ∇f (xt ) q − ∇f (x ), n i=1 ut−1 + δ

(66)

√

∇f x Bu + δ 2 √ − ∇f z t − ∇f (xt ) δ 4 Bu + δ 2 √ t 2 (58) ∇f x α β12 L2 B 2 Bu + δ ≥ − √ − , δ 2 (1 − β1 )2 4 Bu + δ ≥−

(67)

Published in Transactions on Machine Learning Research (04/2026)

where the first inequality follows from Young’s inequality and ut−1 ≥ 0. For the third term in the RHS i of (64), we have from Young’s inequality that * + n 1 X ∇fi (xti ) − ∇f (xt ) t q ∇f (x ), n i=1 ut−1 + δ i

n X

√

2 ∇f x Bu + δ ∇fi xti − ∇fi xt − √ − δ 4 Bu + δ ! √ 2 n ∇f xt 1X L2 Bu + δ t 2 xi − xt ≥ − √ − n i=1 δ 4 Bu + δ 2 √ ∇f xt L2 Bu + δ =− √ − ∥Xt⊥ ∥2 . nδ 4 Bu + δ

1 ≥ n i=1

(68)

Since ∥uti ∥∞ ≤ Bu for all t ≥ 0 and i ∈ {1, 2, . . . , n}, the last term in the RHS of (64) can be bounded as * + n 1X ∇f xt 1 t q ≥√ ∥∇f xt ∥2 . (69) ∇f x , n i=1 ut−1 + δ Bu + δ i

□

Substituting (65)– (69) into (64) and rearranging terms yields the desired result. Now we are ready to show the main convergence result.

Theorem A.1 Suppose that Assumptions 1–3 hold, Q is an η-compression operator, and ∥uti ∥∞ ≤ Bu for all t ≥ 0 and i ∈ {1, 2, . . . , n}. Let C denote the constant defined in (21), α, γ > 0 satisfy α≤

δ √ , 48L Bu + δ

γ≤

(1 − ρ)(1 − η 2 ) . 100

(70)

Then, it holds TX K−1 α αT K α2 L2 β12 B 2 √ E ∥∇f xt ∥2 ≤ E f x0 − f ∗ + √ 4 Bu + δ t=0 8 Bu + δ δ(1 − β1 )2   2 TX K−1 n 2 2 p 1X αβ1 B∞ 1 1   q 4 Bu + δ + αL E  −q +  2 (1 − β1 ) n t−2 t−1 t=0 ui + δ ui + δ i=1 24 6L2 2 + α2 L T KB 2 + α T nK 3 C nδ nδ √ TX K−1 3 2 2 2 √ αL2 1 1 Bu + δ α β1 L B Bu + δ √ + + √ + α2 T nK 3 C + . n δ δ(1 − β1 )2 δ 2 δ 2 δ t=0

Proof. By the L-smoothness of f , we have L t+1 2 f z t+1 ≤ f z t + ∇f z t , z t+1 − z t + z − zt , 2 which together with (55) gives *

f z

t+1

+ n 1X git L t+1 2 q ≤f z − α ∇f z , + z − zt n i=1 ut−1 + δ 2 i +  * n X β1 1 α 1  . + −q ∇f z t , mt−1 ◦  q 1 − β1 n i=1 i t−2 t−1 u +δ u +δ t

(71)

Published in Transactions on Machine Learning Research (04/2026)

Take expectation, sum up over t, and rearrange terms of the above inequality. Noticing z 0 = x0 , we have

+ n TX K−1 h i t X g 1 2  ≤ E f x0 − f z T K + L E q i α E  ∇f z t , z t+1 − z t n i=1 ut−1 + δ 2 t=0 t=0 i + *  TX K−1 n X 1 αβ1 1 1  . −q + E  ∇f z t , mt−1 ◦  q 1 − β1 t=0 n i=1 i t−2 t−1 u +δ u +δ TX K−1

*

(72)

Below we bound the inner-product terms on the RHS of (72). First,

+ *  TX K−1 n X β1 1 1 1   E  ∇f z t , mt−1 ◦  q −q 1 − β1 t=0 n i=1 i t−2 t−1 ui + δ ui + δ *  + TX K−1 n X β1 1 1 1   = E  ∇f xt , mt−1 ◦  q −q 1 − β1 t=0 n i=1 i t−2 t−1 ui + δ ui + δ *  + TX K−1 n X 1 1 1 β1  . + E  ∇f z t − ∇f xt , mt−1 ◦  q −q 1 − β1 t=0 n i=1 i t−2 t−1 u +δ u +δ i

(73)

For the first term in the RHS of (73), we use Young’s inequality to have

β1 1 − β1 ≤

TX K−1 t=0

 + n X 1 1 1   E  ∇f xt , mt−1 ◦ q −q i n t−2 t−1 t=0 u +δ u +δ i=1

TX K−1

1 E 8 Bu + δ √

TX K−1 t=0

∇f xt 

√ 2

i 

n X

1 2β1 Bu + δ  1 1 E mt−1 ◦  q −q (1 − β1 )2 n i=1 i t−2 t−1 u u +δ +δ i

1 ≤ √ 8 Bu + δ +

*

TX K−1

h E

∇f xt

 2   

t=0

 n X Bu + δ 1 1 1  E q −q (1 − β1 )2 n i=1 t−2 t−1 u +δ u +δ

2 2β12 B∞

√

  ,

(74)

Published in Transactions on Machine Learning Research (04/2026)

where in the last inequality, we have used ∥mt−1 ∥∞ ≤ B∞ by Lemma A.1. For the second term in the RHS i of (73), it holds + *  TX K−1 n X β1 1 1 1   −q E  ∇f z t − ∇f xt , mt−1 ◦  q 1 − β1 t=0 n i=1 i t−2 t−1 u +δ u +δ i

≤

TX K−1

h 2i 1 √ E ∇f z t − ∇f xt 8 Bu + δ t=0   2  √ TX K−1 n 2 X 2β1 Bu + δ  1 1 1   + E −q mt−1 ◦ q  i 2 (1 − β ) n t−2 t−1 1 t=0 u +δ u +δ i=1 i



√ TX K−1 n 2 TK Bu + δ 1 X  α L2 β12 B 2 2β12 B∞ ≤ √ + E (1 − β1 )2 n i=1 8 Bu + δ δ(1 − β1 )2 t=0 2

1 1 q −q ut−2 +δ ut−1 +δ i i

  ,

(75)

where in the last inequality, we have used (58) and ∥mt−1 ∥∞ ≤ B∞ by Lemma A.1. Plugging (74) and (75) i into (73), we obtain  + * n T K−1 X αβ1 X  1 1 1 t−1   m ◦ q −q E ∇f z t , 1 − β1 t=0 n i=1 i ut−2 + δ ut−1 + δ i

α ≤ √ 8 Bu + δ +

TX K−1

h E

∇f xt

t=0

2 4αβ12 B∞

√

Bu + δ (1 − β1 )2

TX K−1

n 1X

t=0

n i=1

αT K α2 L2 β12 B 2 + √ 8 Bu + δ δ(1 − β1 )2  1 1  E q −q t−2 t−1 ui + δ ui + δ

  .

(76)

Now plugging (59), (76) and (63) after taking full expectation into (72) and rearranging terms gives

3α 6Lα2 √ − δ 8 Bu + δ

TX K−1

αT K α2 L2 β12 B 2 E[∥∇f xt ∥2 ] ≤ E f x0 − f z T K + √ 8 Bu + δ δ(1 − β1 )2 t=0   2 TX K−1 n 2 2 p X αβ1 B∞ 1 1 1   q + 4 Bu + δ + αL E  −q  (1 − β1 )2 n t−2 t−1 t=0 ui + δ ui + δ i=1 "T K−1 #! 2 X 6L 24 2 T KB 2 + E Xt⊥ + α2 L nδ nδ t=0 √ √ ! TX K−1 2 L Bu + δ 1 α2 β12 L2 B 2 Bu + δ 1 t 2 +α + √ E[∥X⊥ ∥ ] + + √ . n δ δ(1 − β1 )2 δ 2 δ 2 δ t=0 2

3α Plug (21) into the inequality above, notice 8√B − 6Lα ≥ 4√Bα +δ , and rearrange terms. We obtain the δ u +δ u desired result and complete the proof. □

Published in Transactions on Machine Learning Research (04/2026)

To prove Theorem 3.2, we only need to consider the following three settings of {Ut } n o b t = β2 U b t−1 + (1 − β2 )Gt ◦ Gt with U b −1 = 0, Ut = max U b t , Ut−1 ; AMSGrad : U Adam : Ut = β2 Ut−1 + (1 − β2 )Gt ◦ Gt ; AdaGrad : Ut =

(77) (78)

t X

1 Gs ◦ Gs ; , t + 1 s=0

(79)

t t bt = u b1 , u b2 , . . . , u b tn , Ut = ut1 , ut2 , . . . , utn . U

(80)

where

Notice that when β1 = 0 and β2 = 1, AMSGrad reduces to the vanilla SGD, and when β1 ∈ (0, 1) and β2 = 1, it reduces to the momentum SGD. Consequently, our theoretical guarantees on AMSGrad naturally extend to these two special cases as well. Adam-Mini (Zhang et al., 2024) can be regarded as a special case of Adam by using a constant scalar (instead of a vector) for each block of variables as the second momentum. Therefore, the results on Adam also hold for Adam-Mini. Below we bound ∥uti ∥ and the summation of the difference between the consecutive terms in the sequence oT K−1 n √ 1 for the three optimizers in (77)-(79). Ut +δ t=0

Lemma A.7 Let u−2 = 0 for all i = 1, 2, . . . , n. Under Assumption 3, for all t ≥ 0 and i ∈ {1, 2, . . . , n}, i the following statements hold. 2 (i) For AMSGrad in (77), it holds ∥uti ∥∞ ≤ B∞ , and TX K−1 t=0

d . δ

(81)

4 T Kd(1 − β2 )2 B∞ . δ3

(82)

1X 1 1 q −q n i=1 t−2 t−1 ui + δ ui + δ

≤

2 (ii) For Adam in (78), it holds ∥uti ∥∞ ≤ B∞ , and TX K−1 t=0

1 1X 1 q −q n i=1 ut−2 +δ ut−1 +δ i i

≤

2 (iii) For Adagrad in (79), it holds ∥uti ∥∞ ≤ B∞ , and TX K−1 t=0

1X 1 1 q −q n i=1 t−2 t−1 ui + δ ui + δ

≤

4 2dB∞ . 3 δ

(83)

2 2 b −1 Proof. (i) Noticing u = 0 and ∥git ◦ git ∥∞ ≤ B∞ , we have ∥b uti ∥∞ ≤ 1 − β2t+1 B∞ for each i ∈ {1, 2, . . . , n} i t−1 t t and t ≥ 0. By ui = max{b ui , ui }, it holds ∥uti ∥∞ ≤ max{∥b uti ∥∞ , ∥ut−1 ∥∞ } ≤ max{∥b uti ∥∞ , ∥b ut−1 ∥∞ , ∥ut−2 ∥∞ } i i i t t−1 −1 0 ≤ max ∥b ui ∥∞ , ∥b ui ∥∞ , . . . , ∥b ui ∥∞ , ∥ui ∥∞ , 2 2 2 t+1 t+1 t 2 ≤ max 1 − β2 B∞ , 1 − β 2 B∞ , . . . , (1 − β2 ) B∞ , ∥u−1 B∞ , i ∥∞ = 1 − β2 where the equality holds because β2 ∈ (0, 1] and u−1 = 0. i 31

Published in Transactions on Machine Learning Research (04/2026)

In addition, we have TX K−1 t=0

≤

TX K−1 t=0

≤

TX K−1 t=0

1 1 1X q −q n i=1 t−2 t−1 ui + δ ui + δ n

1X 1 1 q −q n i=1 ut−2 +δ ut−1 +δ i i n X

1 1 √ n i=1 δ

−q

ut−2 +δ i

n 1 1 X √ ≤  q t=0 n δ i=1 ut−2 +δ i  n T K−1 1 X X  1 = √  q n δ i=1 t=0 ut−2 +δ i n 1 X 1 q ≤ √ n δ i=1 u−2 i +δ

+δ

1 − √ t−1 ui

ut−2 +δ i

+δ

∞

−q

1 ut−1 +δ i

∞

1 ut−1 +δ i

(84)





TX K−1

1 where √ t−2

1 q

− q ut−1 +δ i

  1

 − q 1

1 ut−1 +δ i

  1

d , δ

≤ √1δ holds because ut−2 ≥ 0 and ut−1 ≥ 0, and the equality holds because i i

ut−1 is nondecreasing with t for each i ∈ {1, 2, . . . , n}. i 2 2 (ii) Noticing u−1 = 0 and ∥git ◦ git ∥∞ ≤ B∞ , we have ∥uti ∥∞ ≤ 1 − β2t+1 B∞ . i For all t ≥ −1, it holds 2

p =

uti + δ

−p ut−1 +δ i

d X

p j=1

d X

[β2 ut−1 + (1 − β2 )gti ◦ gti ]j + δ i (1 − β2 ) [ut−1 − gti ◦ gti ]j i

p j=1

≤

[β2 ut−1 + (1 − β2 )gti ◦ gti ]j + δ i

[ut−1 + δ]j ( i

−p

1 [ut−1 + δ]j i 2

[β2 ut−1 + (1 − β2 )gti ◦ gti ]j + δ + i

[ut−1 + δ]j ) i

4 d(1 − β2 )2 B∞ , δ3

2 2 where the last inequality follows from 0 ≤ [ut−1 ]j ≤ B∞ and 0 ≤ [gti ◦gti ]j ≤ B∞ . Then the desired inequality i holds. Pt 1 s s t t 2 t 2 (iii) By uti = t+1 s=0 gi ◦ gi and ∥gi ◦ gi ∥∞ ≤ B∞ , it holds ∥ui ∥∞ ≤ B∞ . For all t ≥ 1, it holds 2

p t−1 ui

+δ

−p t−2 ui

= +δ

d X

p t−1

[ t ut−2 + 1t gt−1 ◦ gt−1 ]j + δ i i i

j=1

d X

1 t

p t−1 j=1

[ t ut−2 + 1t gt−1 ◦ gt−1 ]j + δ i i i

[ut−2 − gt−1 ◦ gt−1 ]j i i i

[ut−2 ]j + δ( i

p t−1

dB 4 ≤ 2∞ , t δ3

−p

1 [ut−2 ]j + δ i 2

[ t ut−2 + 1t gt−1 ◦ gt−1 ]j + δ + i i i

[ut−2 ]j + δ) i

Published in Transactions on Machine Learning Research (04/2026)

2 2 where the last inequality follows from 0 ≤ [ut−2 ]j ≤ B∞ and 0 ≤ [gt−1 ◦ gt−1 ]j ≤ B∞ . Then i i i

TX K−1 t=0

≤

1X 1 1 q −q n i=1 t−2 t−1 ui + δ ui + δ

TX K−1 t=1

1X 1 1 q −q n i=1 t−2 t−1 ui + δ ui + δ

4 2dB∞ . 3 δ

□

The proof is then completed. Now, we prove Theorem 3.2, with its complete statement given as follows.

Theorem A.2 Suppose that Assumptions 1–3 hold, and Q is an η-compression operator. Let δ = O(1) be a universal positive constant, C be the constant defined in (21), and α, γ > 0 satisfy

α=

4θ

( ) p 2 + δ) n(B∞ δ (1 − ρ)(1 − η 2 ) p √ ≤ min , ,1 ,γ ≤ 2 +δ 100 TK 48L B∞

(85)

where θ = O(1). Then, the following statements hold. (i) For AMSGrad in (77), it holds T K−1 1 X t 2 1 t 2 E ∥∇f (x )∥ + ∥X⊥ ∥ T K t=0 n 1 1 2 =O √ dB 3 (B∞ + L + 1) f (x0 ) − f ∗ + LB 2 B∞ + LB 2 + T K ∞ nT K nKC 2 3 n 2 2 nKC 4 2 + L B∞ (1 + L + B∞ ) + L B (1 + B∞ ) + (1 + B∞ ) . T TK T

(ii) For Adam in (78) with β2 ∈

h √

(86)

√ T K , 1 , it holds T K+1

T K−1 1 X t 2 t 2 1 E ∥∇f (x )∥ + ∥X⊥ ∥ T K t=0 n 1 1 2 =O √ f (x0 ) − f ∗ + LB 2 B∞ + LB 2 + dB 7 (B∞ + L + 1) TK ∞ nT K nKC 2 3 n 2 2 nKC 4 2 + L B∞ (1 + L + B∞ ) + L B (1 + B∞ ) + (1 + B∞ ) . T TK T

(87)

(iii) For AdaGrad in (79), the relation (87) holds as well. 2 Proof. From Lemma A.7, it holds that ∥uti ∥∞ ≤ Bu , ∀ t, ∀ i with Bu = B∞ for all the three optimizers in (77)-(79).

Published in Transactions on Machine Learning Research (04/2026)

Dividing both sides of (71) by √αT2K 4

B∞ +δ

√ = θ nT K and rearranging terms, we have

T K−1 1 X α2 L2 β12 B 2 1 E ∥∇f xt ∥2 ≤ √ f (x0 ) − f ∗ + T K t=0 2δ(1 − β1 )2 θ nT K  p TX K−1 n 2 2 +δ p 4β12 B∞ B∞ 1 1X 1 2 + δ + αL E  q + 4 −q B  ∞ 2 T K(1 − β1 ) n i=1 t=0 ut−2 +δ ut−1 +δ i i ! p 2 +δ p p B∞ 24 2 α2 L2 nK 2 C 1 6αL 2 +δ 2 +δ + 4αL B∞ B + 4 B∞ + √ + nδ n δ δ 2 δ !! p 2 +δ p B∞ α2 β12 L2 B 2 1 2 +δ . + 4 B∞ + √ δ(1 − β1 )2 δ 2 δ

Adding (21) to the above inequality and replacing α by obtain

√ √ 2 4θ n B∞ +δ √ TK

  

≤ 1 in the resulting inequality, we

T K−1 2 2 1 16θ2 nL2 β12 B 2 (B∞ 1 + δ) 1 X t t 2 E ∥∇f x ∥ + ∥X⊥ ∥ ≤ √ f (x0 ) − f ∗ + 2 T K t=0 n 2T Kδ(1 − β ) θ nT K 1   2 p TX K−1 n 2 2 2 X p 4β B B∞ + δ 1 1 1  2 + δ + L E q + 1 ∞ 4 B∞ −q   T K(1 − β1 )2 n t=0 ut−2 +δ ut−1 +δ i=1 i i ! p 3 2 2 2 2 2 +δ 2 B 24 + δ) 64L nK Cθ (B 1 6L 16θ ∞ ∞ 2 L(B∞ + δ) B 2 + + √ + +√ δ TK δ δ nT K 2 δ ! ! p 3 2 2 2 +δ B∞ 1 + δ) 64nθ2 (B∞ + δ) 2 β12 L2 B 2 16nK 2 Cθ2 (B∞ + √ . + + 2 TK δ(1 − β1 ) δ TK 2 δ

(88)

We now substitute the results in Lemma A.7 to the above inequality. (i) For AMSGrad, we have 

TX K−1

 E

t=0

n i=1

(ii) For Adam, we know from β2 ∈ 

TX K−1

 E

t=0

n 1X

h √

1 q

ut−2 +δ i i

√ TK , 1 T K+1

−q

1 ut−1 +δ i

  d  ≤ = O(d). δ

that 2

n X

1 1 1 q −q n i=1 ut−2 +δ ut−1 +δ i i

 4  T Kd(1 − β2 )2 B∞ 4 = O(dB∞ ). ≤ δ3

(iii) For Adagrad, we have TX K−1 t=0

1X 1 1 q −q n i=1 ut−2 +δ ut−1 +δ i i

≤

4 2dB∞ 4 = O(dB∞ ). δ3

□

Therefore, we obtain the desired results. 34

Published in Transactions on Machine Learning Research (04/2026)

The matrix-form adaptive gradient updates

It should be noted that our theoretical results extend to matrix-form adaptive gradient updates, where the d-dimension real-valued functions {rt } are replace by some d×d dimension real-valued functions {rt }. Under this formulation, we update the second-momentum matrices Ui as Uti = rt (gi0 , gi1 , . . . , git ) and the model − 1 t+ 1 + δ 2 mti . parameter by xi 2 = xti − α Ut−1 i Our theoretical results apply to the matrix-form adaptive gradient method, provided that maxr,s ∥[Uti ]rs ∥ is uniformly bounded for all i ∈ {1, 2, . . . , n} and t ≥ 0, and that the summation 2 PT K−1 1 Pn 1 1 t−2 + δ)− 2 − (Ut−1 remains bounded. + δ)− 2 i t=0 i=1 (Ui n A notable example of this framework is the matrix-form AdaGrad method, where Uti is updated as Uti =

t 1 X gi gi⊤ , for each agent i = 1, . . . , n. t + 1 s=0

2 for all r ∈ {1, 2, . . . , d} and s ∈ For this choice of {Uti }, it is not difficult to show that |[Uti ]rs |≤ B∞ {1, 2, . . . , d}, and TX K−1 t=0

1 1 1X (Ut−2 + δ)− 2 − (Ut−1 + δ)− 2 i i n i=1

≤

4 2d2 B∞ . δ3

(89)

Therefore, our theoretical results extend naturally to the matrix-form AdaGrad method.

Examples of η-compression operators

In this section, we provide a few concrete examples of compression operators that are η-compression operators. More examples can be found in (Chen et al., 2023a; Koloskova et al., 2019). j k |x| Example C.1 QSGD (Alistarh et al., 2017) compresses x ∈ Rd by Qsgd (x) = sign(x)∥x∥ s ∥x∥ + ξ where s 1 d ξ is uniformly on ndistributed o[0, 1] , s is a parameter about compression level. Then Q(x) := τ Qssgd (x) with √ τ = 1 + min d/s2 , d/s is an η-compression operator with η = 1 − τ1 .

Example C.2 Qsparse (x) (Stich et al., 2018) randomly selects k out of d coordinates from x, or the k coordinates with the largest values in magnitude from x. Then Qsparse (x) is an η-compression operator with η = d−k d . Example C.3 Qgossip (x) (Koloskova et al., 2019) sets Qgossip (x) = x with probability p ∈ [0, 1] and Qgossip (x) = 0 with probability 1 − p. Then Qgossip (x) is an η-compression operator with η = 1 − p.

Additional Numerical Experiments

We include a suite of additional numerical results in this section. These results were omitted from the main body of the paper for space considerations. We expand on the results presented in the main body in several ways. Figure 6 includes all omitted FashionMNIST results using the same experiment setup as shown in Figures 1, 2, and 3 for CIFAR-10 and tiny-shakespeare. However, we note that we omit CDProxSGT optimizer comparisons in this supplement, as its results were not competitive in most experiments, as observed in Figure 1. SQuARM-SGD otherwise represents methods with non-adaptive updates. We also include additional experiments using expanded parameter settings. Figure 7 repeats the optimizer comparisons demonstrated in Figure 1 with a wider variety of local update counts. Figure 8 repeats the experiments comparing the effect of local update counts on communication rounds shown in Figure 2 with Adam’s update, while comparing AdaGrad’s and AMSGrad’s adaptive updates as well. Figure 9 compares 35

Published in Transactions on Machine Learning Research (04/2026)

varying values of Top-k compression for all three optimizer variants. We do not show training loss or consensus error with these figures for space and clarity, while noting that theses plots would otherwise be consistent with those shown in Figures 1, 2, 3, and 6. D.1

FashionNMIST Results

7.5

5.0

Consensus Error

10 4

2.5

Epochs

10 3

0.0

7.5

0.0

17 .5

15 .0

Epochs

12 .5

10 .0

7.5

5.0

2.5

0.0

0.5

DistributedAMSGrad DistributedAdaGrad DistributedAdam DADAM SQuARM-SGD

1.0

10 2

5.0

Training Loss

1.5

90 80 70 60 50 40 30 20 10

2.5

DistributedAMSGrad DistributedAdaGrad DistributedAdam DADAM SQuARM-SGD

2.0

Test Accuracy

In Figure 6, we plot the results for the same experiments on FashionNMIST as performed and displayed for CIFAR-10 and tiny-shakespeare in Figures 1, 2, 3 in the main body of the paper. For these results, Top-k compression of 30% is used. The primary observations in this figure are consistent as with the prior results. We generally observe little to no degradation of accuracy and loss performance, even when including local updates and Top-k compression. In particular, FashionMNIST suffers less in terms of quality impacts when including compression and minimizing communication relative the two other test datasets.

Epochs

Consensus Error

10 3

00 15

0 00

Communication Rounds

10 2

10 4

50 00 10 00 0 15 00 0 20 00 0 25 00 0 30 00 0 35 00 0

0.5

1.0

1.5

Training Loss

2.0

10 1

90 80 70 60 50 40 30 20 10

K=1 K=2 K=5 K=10 K=20 K=50

Test Accuracy

(a) FashionMNIST optimizer comparison.

Communication Rounds

Training Loss

2.0 1.5 1.0 0.5 10 3

10 2

10 1

Scaled Communication Volume

100

101

90 80 70 60 50 40 30 20 10

100 Consensus Error

K=50,Top-k=30% K=10,Top-k=40% K=2,Top-k=60% K=1,Top-k=None

Test Accuracy

(b) FashionMNIST reduction in communication rounds.

10 1 10 2 10 3 10 4 10 5

10 3

10 2

10 1

Scaled Communication Volume

100

10 3

10 1 10 2 Scaled Communication Volume

100

Figure 6: Convergence performance for FashionMNIST: Plotted above are the training loss and test accuracy of FashionMNIST. The top row compares optimizer performance with Top-k 30% compression and a local update count of K = 20. The middle row demonstrates the reduction in communication rounds based on the number of local updates with Top-k compression of 30%. The bottom row compares the total communication volume scaled relative to the uncompressed baseline with no local updates.

Published in Transactions on Machine Learning Research (04/2026)

D.2

Additional Optimizer Comparisons

In the main body of the paper, Figures 1a and 1b compare optimizer performance for a fixed value of K = 20. Figure 7 repeats these experiments with additional values of K = 2, 5, 10, 50, still using 4 agents. Shown are test accuracy/validation loss with compression values of 30%, 40%, and 50% for FashionMNIST, CIFAR10, and tiny-shakespeare, respectively. We overall again observe consistent results as with Figure 1, where Adam outperforms other optimizers on FashionMNIST and tiny-shakespeare and AdaGrad outperforms other optimizers on CIFAR-10. Likewise, SQuARM-SGD consistently lacks in generalization performance on the GPT language model with the tiny-shakespeare dataset. D.3

Additional Number of Local Updates Comparisons

In Figure 8, the experiments using Adam in Figures 2a, 2b, and 6b are repeated with the AdaGrad and AMSGrad adaptive updates. For each optimizer and benchmark dataset, we plot the accuracy or validation loss that results with local updates of K = 1, 2, 5, 10, 20, 50. Again, we use Top-k compression values of 30%, 40%, and 50% for FashionMNIST, CIFAR-10, and tiny-shakespeare. Likewise, we note that accuracy performance is minimally affected by the number of local updates used in these tests. D.4

Additional Top-k Compression Comparisons

We fixed Top-k compression values for each dataset for the bulk of the experiments demonstrated thus far, to avoid a parametric explosion in the number of results presented. Figure 9 demonstrates that a different choice of Top-k compression in the same order of what was used has minimal impact on the overall optimizer performance and resultant appearance in plots. In Figure 9, we fix K = 20 and vary Top-k to 30%, 40%, 50%, and 60% for each of our optimizers (Adam, AdaGrad, AMSGrad) and dataset (FashionMNIST, CIFAR-10, tiny-shakespeare). We observe a reduction in total used communication volume scaling linearly with Top-k percentages, as expected, while accuracy and validation loss are relatively consistent across all tests. D.5

Additional Scaling Comparisons

In Figure 10 we present scaling results for AdaGrad and AMSGrad, as was presented for Adam in Figure 4 in the main body of this paper. We fix K = 20 and run with 4, 9, and 16 agents across both ring and 2D grid topologies. As with Adam, we note minimal impact to the maximum achieved test accuracy after 250 epochs, demonstrating near-linear speedup for our approach.

DistributedAMSGrad DistributedAdaGrad DistributedAdam DADAM SQuARM-SGD

3.5 3.0 2.5

Epochs

60 0

40 0

30 0

20 0

10 0

2.0

25 0

Epochs

20 0

15 0

10 0

DistributedAMSGrad DistributedAdaGrad DistributedAdam DADAM SQuARM-SGD

Validation Loss

4.0

50 0

80 70 60 50 40 30 20 10

17 .5

15 .0

Epochs

12 .5

7.5

10 .0

5.0

2.5

DistributedAMSGrad DistributedAdaGrad DistributedAdam DADAM SQuARM-SGD

Test Accuracy

90 80 70 60 50 40 30 20 10

0.0

Test Accuracy

Published in Transactions on Machine Learning Research (04/2026)

DistributedAMSGrad DistributedAdaGrad DistributedAdam DADAM SQuARM-SGD

3.0 2.5

0 40

0 30

0 20

Epochs

2.0

3.5

Epochs

0 15

0 10

DistributedAMSGrad DistributedAdaGrad DistributedAdam DADAM SQuARM-SGD

Validation Loss

4.0

90 80 70 60 50 40 30 20 10

.0 15

.0 Epochs

7.5

5.0

2.5

DistributedAMSGrad DistributedAdaGrad DistributedAdam DADAM SQuARM-SGD

Test Accuracy

90 80 70 60 50 40 30 20 10

0.0

Test Accuracy

(a) K = 2: FashionMNIST, CIFAR-10, and Shakespeare optimizer comparison.

DistributedAMSGrad DistributedAdaGrad DistributedAdam DADAM SQuARM-SGD

3.0 2.5

0 40

0 30

0 20

Epochs

2.0

3.5

Epochs

0 15

0 10

DistributedAMSGrad DistributedAdaGrad DistributedAdam DADAM SQuARM-SGD

Validation Loss

4.0

90 80 70 60 50 40 30 20 10

.0 15

.0 Epochs

7.5

5.0

2.5

DistributedAMSGrad DistributedAdaGrad DistributedAdam DADAM SQuARM-SGD

Test Accuracy

90 80 70 60 50 40 30 20 10

0.0

Test Accuracy

(b) K = 5: FashionMNIST, CIFAR-10, and Shakespeare optimizer comparison.

2.5

60 0

Epochs

50 0

40 0

30 0

2.0

20 0

Validation Loss

3.0

10 0

0 25

Epochs

3.5

0 20

.5 17

.0 15

Epochs

7.5

5.0

2.5

0.0

DistributedAMSGrad DistributedAdaGrad DistributedAdam DADAM SQuARM-SGD

4.0

90 80 70 60 50 40 30 20 10

Test Accuracy

(d) K = 50: FashionMNIST, CIFAR-10, and Shakespeare optimizer comparison.

Figure 7: Additional optimizer comparisons: Plotted above are accuracy (for FashionMNIST and CIFAR-10) and validation loss (for tiny-shakespeare) for the tested optimizers across a range of local update counts K. For each subplot, FashionMNIST is on the right, CIFAR-10 is in the middle, and tiny-shakespeare is on the right.

Communication Rounds

0 00

K=1 K=2 K=5 K=10 K=20 K=50

Communication Rounds

90 80 70 60 50 40 30 20 10

00 15

K=1 K=2 K=5 K=10 K=20 K=50

Test Accuracy

90 80 70 60 50 40 30 20 10

Test Accuracy

Published in Transactions on Machine Learning Research (04/2026)

90 80 70 60 50 40 30 20 10

Test Accuracy

70 60 50 40 30 20

30 00 0

Communication Rounds

25 00 0

20 00 0

15 00 0

10 00 0

50 00

30 00 0

Communication Rounds

25 00 0

20 00 0

15 00 0

10 00 0

50 00

Test Accuracy

(a) AdaGrad (left) and AMSGrad (right) on FashionMNIST with Top-k compression of 30%.

(b) AdaGrad (left) and AMSGrad (right) on CIFAR-10 with Top-k compression of 40%.

Training Loss

3.5 3.0 2.5 2.0

K=1 K=2 K=5 K=10 K=20 K=50

4.0 Validation Loss

K=1 K=2 K=5 K=10 K=20 K=50

4.0

1.5

3.5 3.0 2.5 2.0

Communication Rounds

00 20 00

00 15 00

0 50 00

10 00

Communication Rounds

20 00

00 15 00

00 10 00

0 50 00

1.0

Figure 8: Additional number of local updates comparisons: Plotted above are accuracy (for FashionMNIST and CIFAR-10) and validation loss (for tiny-shakespeare) using AdaGrad (left) and AMSGrad (right), comparing across a range of local update values K.

Published in Transactions on Machine Learning Research (04/2026)

40 K=20,Top-k=30% K=20,Top-k=40% K=20,Top-k=50% K=20,Top-k=60%

20 10 3

90 80 70 60 50 40 30 20 10

10 2 Scaled Communication Volume

K=20,Top-k=30% K=20,Top-k=40% K=20,Top-k=50% K=20,Top-k=60% 10 3

Test Accuracy

60 40 K=20,Top-k=30% K=20,Top-k=40% K=20,Top-k=50% K=20,Top-k=60%

10 2 Scaled Communication Volume

10 3

10 2 Scaled Communication Volume

(a) Adam (left), AdaGrad (middle), and AMSGrad (right) on FashionMNIST with varying Top-k compression.

60 50 40 K=20,Top-k=30% K=20,Top-k=40% K=20,Top-k=50% K=20,Top-k=60%

30 20 10

10 4

Test Accuracy

10 3 10 2 Scaled Communication Volume

80 70 60 50 40 30 20 10

80 70

K=20,Top-k=30% K=20,Top-k=40% K=20,Top-k=50% K=20,Top-k=60% 10 4

Test Accuracy

60 50 40 K=20,Top-k=30% K=20,Top-k=40% K=20,Top-k=50% K=20,Top-k=60%

30 20 10

10 3 10 2 Scaled Communication Volume

10 4

10 3 10 2 Scaled Communication Volume

(b) Adam (left), AdaGrad (middle), and AMSGrad (right) on CIFAR-10 with varying Top-k compression.

3.0 2.5 2.0

K=20,Top-k=30% K=20,Top-k=40% K=20,Top-k=50% K=20,Top-k=60%

4.0 3.5 3.0 2.5 2.0

1.5 10 4 10 3 10 2 Scaled Communication Volume

4.0 Validation Loss

Training Loss

3.5

K=20,Top-k=30% K=20,Top-k=40% K=20,Top-k=50% K=20,Top-k=60%

Validation Loss

4.0

3.5

K=20,Top-k=30% K=20,Top-k=40% K=20,Top-k=50% K=20,Top-k=60%

3.0 2.5 2.0

10 4 10 3 10 2 Scaled Communication Volume

10 5 10 4 10 3 Scaled Communication Volume

Figure 9: Additional Top-k compression comparisons: Plotted above are accuracy (for FashionMNIST and CIFAR-10) and validation loss (for tiny-shakespeare) using Adam (left), AdaGrad (middle), and AMSGrad (right), comparing across a range of Top-k compression values.

Published in Transactions on Machine Learning Research (04/2026)

10 0

15 0

20 0

25 0

0 25

Consensus Error

10 1

0 20

Epochs

100

25 0

0 15

Epochs

0 10

0.0

DistributedAdaGrad:N=4,Ring DistributedAdaGrad:N=9,Ring DistributedAdaGrad:N=16,Ring

20 0

0.5

15 0

1.0

101

10 0

1.5

Test Accuracy

Training Loss

2.0

90 80 70 60 50 40 30 20 10

DistributedAdaGrad:N=4,Ring DistributedAdaGrad:N=9,Ring DistributedAdaGrad:N=16,Ring

Epochs

(a) AdaGrad agent scaling with ring topology.

Consensus Error

Epochs

0 25

0 20

Epochs

25 0

Epochs

20 0

15 0

10 0

0.0

100

DistributedAdaGrad:N=4,Grid DistributedAdaGrad:N=9,Grid DistributedAdaGrad:N=16,Grid

0.5

1.0

101

1.5

Test Accuracy

Training Loss

2.0

90 80 70 60 50 40 30 20 10

DistributedAdaGrad:N=4,Grid DistributedAdaGrad:N=9,Grid DistributedAdaGrad:N=16,Grid

(b) AdaGrad agent scaling with grid topology.

0 25 25

0 20 0 20

0 15 0

0 10

0 25

10 1

0 20

Epochs

100

Consensus Error

25 0

Epochs

20 0

15 0

10 0

0.0

DistributedAMSGrad:N=4,Ring DistributedAMSGrad:N=9,Ring DistributedAMSGrad:N=16,Ring

0.5

1.0

1.5

Test Accuracy

Training Loss

2.0

90 80 70 60 50 40 30 20 10

DistributedAMSGrad:N=4,Ring DistributedAMSGrad:N=9,Ring DistributedAMSGrad:N=16,Ring

Epochs

100

Epochs

0 10

10 1

Consensus Error

0 25

Epochs

0 20

0 15

Epochs

0 10

0.0

DistributedAMSGrad:N=4,Grid DistributedAMSGrad:N=9,Grid DistributedAMSGrad:N=16,Grid

0.5

1.0

101

1.5

Test Accuracy

Training Loss

2.0

90 80 70 60 50 40 30 20 10

DistributedAMSGrad:N=4,Grid DistributedAMSGrad:N=9,Grid DistributedAMSGrad:N=16,Grid

(d) AMSGrad agent scaling with grid topology.

Figure 10: Additional Scaling Results: Plotted above are the training loss, test accuracy, and consensus error of CIFAR-10 when scaling to 4, 9, and 16 agents using ring topology and 2D grid topology with the AdaGrad and AMSGrad optimizers. All experiments were run with K = 20 local updates per communication round.

Record · ID 10325 · SHA-256 8e6306ef64764deb
Conceptio Open Knowledge Archive — every document is proof-bundled with source, license, and retrieval metadata.