LOSCAR-SGD: Local SGD with Communication-Computation Overlap and Delay-Corrected Sparse Model Averaging

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

LOSCAR-SGD: Local SGD with Communication-Computation Overlap and Delay-Corrected Sparse Model Averaging

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cloud distributedcomputing parallelcomputing

distributed computing, parallel computing, cloud

arXiv:2605.20866v1 [cs.LG] 20 May 2026

LOSCAR-SGD: Local SGD with Communication-Computation Overlap and Delay-Corrected Sparse Model Averaging

Yassine Maziane KAUST [email protected]

Ammar Mahran KAUST [email protected]

Artavazd Maranjyan KAUST [email protected]

Peter Richtárik KAUST [email protected]

Abstract Communication is a major bottleneck in distributed learning, especially in largescale settings and in federated learning environments with slow links. Three standard ways to reduce this cost are communication compression, local training, and communication-computation overlap. Methods that combine these ingredients are used in practice and have been found to be effective for large-scale training, but there is little theory for methods that combine all three. We study a heterogeneouscompute setting in which different workers may take different numbers of local steps, and we propose LOSCAR-SGD, a Local SGD method that communicates only a sparse subset of model coordinates and continues optimizing while communication is in flight. A key ingredient is a delay-corrected merge rule that incorporates delayed synchronized information without discarding the progress made during the overlap phase. We give convergence guarantees for smooth non-convex objectives and show how sparsity, overlap, and worker heterogeneity affect the rate. To the best of our knowledge, this is the first theory for this combination of ingredients. Experiments further show that communication-computation overlap reduces training time and that the delay-corrected merge outperforms naive overwriting.

Introduction

Distributed learning enables the training of large models across many workers. The most common setup is data parallelism, where the data is split across workers, each worker keeps a copy of the model, and the workers communicate to train one shared model [Goyal et al., 2017, Li et al., 2020a, Zhao et al., 2023]. A simple baseline in this setting is synchronized Minibatch SGD: at every iteration, each worker computes one stochastic gradient, the gradients are averaged, and one global update is taken. This is simple, but it requires communication at every iteration. As models become larger and the number of workers grows, communication can become the main factor limiting training speed. Federated learning is an especially clear example of this issue, since communication often happens over the internet and is much slower than local computation [McMahan et al., 2017, Kairouz et al., 2021, Wang et al., 2021]. There are several common ways to reduce this communication cost. One is local training: instead of synchronizing after every stochastic-gradient step, workers perform several local SGD steps before they communicate. Because the local steps are simple SGD steps, this approach is often called Local SGD [Zinkevich et al., 2010], and in the federated learning literature it became popular Preprint.

Methods

Local Comm./comp. Worker-specific Compression steps overlap local-step counts ✘

✘

✔

✘

✔

✘

✔

✘

✔

✘

[Li et al., 2020b, Maranjyan et al., 2025c]

✔

✘

✔

LOSCAR-SGD (Algorithm 1)

✔

Minibatch SGD Local SGD, FedAvg [Zinkevich et al., 2010, McMahan et al., 2017]

SPARTA, LoCoDL [Beton et al., 2025, Condat et al., 2025]

Overlap-Local-SGD, CO2 [Wang et al., 2020, Sun et al., 2024]

FedProx/ GradSkip

Table 1: Comparison of representative distributed learning methods with theoretical analysis related to our setting. The columns indicate whether a method explicitly incorporates local steps, compression, communication-computation overlap, and worker-specific local-step counts. A checkmark indicates the presence of the corresponding feature. To the best of our knowledge, our method is the first analyzed method that combines all four features.

through FedAvg [McMahan et al., 2017]. Another idea is communication-computation overlap. In standard synchronized methods such as Minibatch SGD and plain FedAvg-style local training, workers may sit idle while messages are being sent, aggregated, and returned. With overlap, workers keep optimizing locally while communication is in flight, which can hide part of the communication delay and reduce training time [Wang et al., 2020, Sun et al., 2024, Kale et al., 2025]. A third idea is to reduce the amount of communicated information through compression, for example via quantization or sparsification [Alistarh et al., 2017, Wangni et al., 2018]. In local training, workers often synchronize model weights by averaging them; with sparsification, only a subset of model coordinates is synchronized [Fournier et al., 2024, Beton et al., 2025]. These techniques are each well studied in both theory and practice. There is also practical evidence that combining them can work well [Douillard et al., 2025, Ajanthan et al., 2026]. However, to the best of our knowledge, there is no theory that covers the full combination of local training, sparse synchronization, and communication-computation overlap. The problem is further complicated when workers have different computation speeds, as in heterogeneous clusters or federated settings, because different workers may perform different amounts of local work in the same amount of time. A natural way to handle this is to let different workers take different numbers of local steps so that they remain roughly aligned in time [Li et al., 2020b, Maranjyan et al., 2025b,c]. In this work, we study the data-homogeneous version of this setting and propose LOSCAR-SGD, a Local SGD-type method with infrequent sparse model averaging, communication-computation overlap, and worker-specific local-step counts. We also study a delay-corrected merge rule that preserves the progress made during the overlap phase instead of discarding it through a naive averaging overwrite. Table 1 summarizes representative methods from the literature that incorporate at least one of the ingredients discussed above and have accompanying theoretical analysis. 1.1

Contributions • We introduce a general Local SGD framework (Algorithm 1) for data-homogeneous distributed optimization that combines four ingredients in one model: local training, sparse model averaging, communication-computation overlap, and worker-specific local-step counts. • We propose a delay-corrected merge rule for sparse synchronization. When delayed synchronized information arrives, the worker should not discard the local progress it made during 2

communication. Instead of simply overwriting coordinates with a delayed average, the rule keeps the overlap progress and corrects only the synchronization disagreement. • In Section 4, we prove convergence guarantees for smooth non-convex objectives. The bounds show how sparsity, overlap, and heterogeneity affect convergence. They also show that the extra error caused by overlap-induced staleness appears as a controlled higher-order term. • Experiments in Section 5 show that communication-computation overlap reduces training time, and that the delay-corrected merge is better than naive overwriting. 1.2

Related work

Local training Local training reduces communication by performing multiple stochastic-gradient steps between synchronizations. It was popularized in federated learning by FedAvg [McMahan et al., 2017], building on earlier distributed-training ideas [Zinkevich et al., 2010, Povey et al., 2014, Moritz et al., 2015]. Federated-learning analyses in the heterogeneous-data regime include [Li et al., 2020c, Karimireddy et al., 2020, Mishchenko et al., 2022b, Douillard et al., 2023], while for our setting the most relevant theory is the homogeneous-data Local SGD line [Yu et al., 2019, Haddadpour et al., 2019, Wang and Joshi, 2021, Woodworth et al., 2020]; for broader background, see Malinovsky et al. [2022]. Compression and sparsification Another standard way to reduce communication is to transmit compressed information. Classical work studies gradient compression, sparsification, and quantization [Alistarh et al., 2017, Wangni et al., 2018, Lin et al., 2017, Beznosikov et al., 2023], but for methods based on periodic model averaging the closer references are those that sparsify the communicated model itself [Beton et al., 2025, Filippova et al., 2025, Douillard et al., 2025, Condat et al., 2025, 2026]. Communication-computation overlap Communication-computation overlap is one of the main ingredients of our method. Instead of leaving workers idle while messages are sent, aggregated, and returned, overlap lets them continue taking useful local updates while communication is in flight, which can reduce training time. This idea is studied in overlap-based local-training and distributed-training methods such as [Wang et al., 2020, Sun et al., 2024, Kale et al., 2025, Douillard et al., 2025]. Asynchronous methods Asynchronous SGD also avoids worker idling, but it does so by removing round-level synchronization altogether [Agarwal and Duchi, 2011, Recht et al., 2011, Maranjyan, 2025]. The motivation is therefore similar to overlap, but the mechanism is different. Our method is more structured: it keeps explicit rounds and a shared server message at the end of each round, while allowing controlled staleness through delayed sparse synchronization. Because only part of the model may be synchronized after a delay, the method is closer to asynchronous training than plain Local SGD, while still remaining more organized than fully asynchronous SGD. This kind of structure is useful to have, and it can even be necessary for optimal asynchronous methods, as shown in recent asynchronous-SGD theory [Tyurin and Richtárik, 2023, Maranjyan et al., 2025a,d, Maranjyan and Richtárik, 2026, Mahran et al., 2026, Sadiev et al., 2026, Tovmasyan et al., 2026]. In this sense, our method sits between Local SGD and asynchronous SGD. The closest comparison in this direction is Tyurin and Sivtsov [2026], which combines local training with asynchronous model averaging but does not include model sparsification.

Problem setup

We consider the stochastic optimization problem min {f (x) := Eξ∼D [F (x; ξ)]} , x∈Rd

(1)

where x ∈ Rd is the model parameter, ξ is a random sample drawn from a distribution D, F (x; ξ) is the sample loss, and f is the population objective. We work in a distributed, data-homogeneous setting with n workers. Each worker keeps its own copy of the model and draws data from the same distribution D. Therefore, every worker can in 3

principle solve (1) on its own. We still use multiple workers because the goal is to speed up training by parallelizing computation. We study first-order stochastic optimization, so the basic local computation at each worker is the evaluation of a stochastic gradient. We write gi (x, ξi ) for the stochastic gradient computed by worker i at point x using a fresh random sample ξi . Our goal is to measure progress over time. For that reason, we also need a simple model for computation time and communication time. Assumption 2.1 (Worker timing model). For each worker i ∈ {1, . . . , n}, one stochastic-gradient computation takes τi seconds, where τi is a positive integer. Let τ := lcm(τ1 , . . . , τn ) be the least common multiple of these computation times. We also assume that one communication phase, from the moment workers send their messages until the aggregated message is available again at the workers, takes ζ seconds, where ζ ∈ {0, τ, 2τ, . . . }. Assumption 2.1 is a modeling simplification. In a real system, computation times are not exact integers and communication delays are not perfectly constant. We do not use this assumption because we believe real systems behave in such an exact way. We use it only as a clean abstraction that puts all workers on a common time grid. Since every τi divides τ , every τ seconds is a time at which all workers can be viewed on the same clock. This lets us define rounds and count local steps without introducing much heavier timing notation. What matters for our analysis is not the integer-valued assumption itself. What matters is that different workers can complete different amounts of local work in the same amount of time, that communication takes a nonzero amount of time, and that workers may continue taking local steps during communication. These are the effects we want to capture. In practice, one can approximate this model by choosing explicit round boundaries in time. Then all local work completed before a boundary is assigned to the current round, and communication is handled after that boundary. If some worker is slightly early or slightly late, the system can either wait briefly for the current local step to finish or ignore a partially completed step. The same idea can be used during communication: one can assign a fixed communication window to the round and absorb small timing mismatches inside that window. We make the following standard assumptions on the objective: Assumption 2.2 (Lower boundedness). The objective f : Rd → R is bounded from below, i.e., there exists f ⋆ ∈ R such that f (x) ≥ f ⋆ ∀x ∈ Rd . Assumption 2.3 (Smoothness). The objective f is differentiable and L-smooth, that is, there exists L > 0 such that ∥∇f (x) − ∇f (y)∥ ≤ L∥x − y∥ ∀x, y ∈ Rd . Randomness enters our model through the random data samples used to compute stochastic gradients, as well as the random masks sampled for the coordinate sparsifier (cf. Section 3). We make the natural assumption that these sources of randomness are independent. r Assumption 2.4 (Independent Samples). The collection of all data samples {ξi,t } and all sparsification masks {Sr } across all workers, local steps, and rounds are mutually independent.

Moreover, we make the following assumptions about the stochastic gradients: Assumption 2.5 (Unbiased stochastic gradients). For every worker i and every x ∈ Rd , E [ gi (x, ξi )| x] = ∇f (x). Assumption 2.6 (Bounded variance). There exists σ 2 ≥ 0 such that for every worker i and every x ∈ Rd , E ∥gi (x, ξi ) − ∇f (x)∥2 x ≤ σ 2 . Assumption 2.7 (Bounded second moment). There exists G > 0 such that for every worker i and every x ∈ Rd , E ∥gi (x, ξi )∥2 x ≤ G2 . 4

Assumptions 2.5 to 2.7 are written worker by worker, but the constants L, σ 2 , and G2 do not depend on i because all workers optimize the same objective in the data-homogeneous setting. The next notation is only needed in the proofs. In round r, worker i performs Hi local steps, where r Hi is defined later in (5). For round r and local step index t, let wi,t denote the point at which worker i evaluates its t-th stochastic gradient in that round. We also define the active worker set at local time t by At := {i ∈ {1, . . . , n} : Hi > t}, mt := |At |. (2) So At is exactly the set of workers that still perform a local step at local time t. With the sigma-field r r r Fr,t := σ {xri }ni=1 , {wi,s , ξi,s : i ∈ As , s = 0, . . . , t − 1}, {wi,t : i ∈ At } , This sigma-field contains the history up to local time t in round r, except for the fresh samples drawn at that time. Under Assumptions 2.4 and 2.5, conditioned on Fr,t , the random vectors r r r gi (wi,t , ξi,t ) − ∇f (wi,t ),

i ∈ At ,

are independent and have conditional mean zero.

Local SGD with communication-computation overlap and infrequent sparse model averaging

Here we describe the method studied in this paper. It combines three ideas: local SGD, sparse model communication, and communication-computation overlap. The main goal is to use all the available worker computation. In particular, workers should keep taking local SGD steps instead of sitting idle while communication is happening. As explained in Section 2, the workers may have different computation times, and τ is the common clock used to define rounds. The method uses two timing parameters. The integer M ≥ 1 controls how long workers compute locally before communication starts. More precisely, the first phase of each round lasts M τ seconds. After that, the workers communicate sparse model information with the server. This communication takes ζ seconds. During those ζ seconds, workers keep computing locally. When the server response arrives, each worker merges the delayed sparse average with its current local model and starts the next round. The full method, LOSCAR-SGD, is summarized in Algorithm 1. We now walk through the main parts of one round in more detail. One round in detail At the beginning of round r ∈ N0 , worker i holds their local model xri ∈ Rd . During the first M τ seconds of the round, worker i performs Mτ τi

Ni :=

(3)

local SGD steps and reaches an intermediate iterate yir . This is the model that worker i prepares for communication. Each worker compresses yir and sends the resulting sparse message to the server. While this communication is taking place, the workers do not remain idle. Instead, they continue running SGD locally. In particular, worker i runs SGD for another Qi :=

ζ τi

(4)

steps over the next ζ seconds and reaches a newer iterate zir . So yir is the model at the moment communication starts, while zir is the model held by worker i when the server message returns. Hence, in one round, worker i performs a total of Hi := Ni + Qi

(3)+(4) M τ + ζ

τi

(5)

Algorithm 1 LOSCAR-SGD (Local SGD with Overlapped Sparse Corrected AveRaging) 1: Input: Number of workers n; worker compute times τ1 , . . . , τn ∈ N; τ ← lcm(τ1 , . . . , τn ) (least common multiple of the worker compute times) 2: integer M ≥ 1 (local-computation parameter) 3: communication duration ζ ∈ {0, τ, 2τ, . . . } 4: sparsification level K ∈ {1, . . . , d} 5: stepsize η > 0 6: Ni ← M τ /τi (#local steps before communication starts) for each worker i 7: Qi ← ζ/τi (# local steps during communication) for each worker i 8: Initialize x0i ∈ Rd for i = 1, . . . , n 9: for r = 0, 1, 2, . . . do 10: Sample a common Rand-K mask Sr ⊆ [d] 11: for all workers i = 1, . . . , n in parallel do 12: Starting from xri , run Ni local SGD steps with stepsize η to obtain yir 13: Form compressed message mri ← CSr (yir ) 14: Send mri to the server 15: While communication is in flight, run Qi further local SGD steps, using stepsize η, from yir to obtain zir 16: end for 17: Server computes n 1X r mr ← m n i=1 i 18: 19: 20:

Server broadcasts mr to all workers for all workers i = 1, . . . , n in parallel do Merge delayed average with latest local model: r r r mj + (zi,j − yi,j ), j ∈ Sr , r+1 xi,j ← r zi,j , j∈ / Sr

∀j ∈ [d]

21: end for 22: end for

local SGD steps. By construction, Ni , Qi , and Hi are integers, and Hi ≥ 1. At the same time, the server averages the sparse messages received from all workers and sends the result back. When this message arrives, each worker combines it with its current local model zir to form the next starting point xr+1 . i The algorithm is written using Ni and Qi because this makes the round structure easy to state. In practice, one does not need to precompute these numbers and force workers to stop after exactly Ni or Qi steps. Instead, workers can simply keep running local SGD, and the system can decide when communication starts. If τ is known, then starting communication after M τ seconds gives the same behavior as Algorithm 1. If τ is not known, one can instead use a time-based synchronization interval as a hyperparameter. As discussed under Assumption 2.1, the integer-time assumption is a modeling device for the analysis, not a literal implementation requirement. Compressed synchronization We use sparsification to reduce the amount of data communicated in each round. This helps keep the communication window short, which in turn reduces how stale the communicated model becomes before the merged model is formed. We fix the sparsification level K ∈ [d] := {1, . . . , d}. In every round r ∈ N0 , a mask Sr ⊆ [d] is sampled uniformly at random among all subsets of cardinality K, independently of the algorithmic history up to the start of round r and the stochastic samples drawn within round r. The same mask Sr is used by all workers in that round, so the server receives the same set of coordinates from every worker. We denote the level of sparsification and its complement by p :=

K , d

q := 1 − p . 6

(6)

We define the compressor associated with Sr by CSr (x) := ProjSr x, where ProjSr denotes the coordinate projection onto the coordinates in Sr . This operator keeps the coordinates in Sr and drops the rest. Since Sr is a uniform random subset of [d] of cardinality K, each coordinate is selected with probability p = K/d, and therefore K E [CSr (x)] = E ProjSr (x) = x. d Worker i sends the compressed message mri := CSr (yir ) = ProjSr yir . The server averages these sparse messages and broadcasts the result back to all workers: n

mr =

1X r m . n i=1 i

Since the same mask Sr is used by all workers, this is equivalent to n

ȳ :=

m = ProjSr (ȳ ),

1X r y . n i=1 i

The important point is that mr is formed from the older models yir , not from the newer models zir . When the averaged message arrives after ζ seconds, each worker combines it with its current local model zir to form the next round’s starting point xr+1 . i Merge rule At the end of round r, worker i has two relevant objects: the newest local model zir , and the delayed server message mr . The merge rule says how these two objects are combined. One possible merge rule is to overwrite the communicated coordinates with the server value: r mj , j ∈ Sr , xr+1 = i,j r zi,j , j∈ / Sr . Under this rule, the coordinates in Sr are replaced by the delayed average, while the other coordinates stay equal to the most recent local iterate zir . This rule is simple, but it throws away the progress made on the communicated coordinates during the overlap window. A better alternative is to keep that progress. This is the rule used in Algorithm 1: r r r ȳj + (zi,j − yi,j ), j ∈ Sr , xr+1 = i,j r zi,j , j∈ / Sr . Under this rule, zir is the baseline. On the communicated coordinates, we add the correction ȳ r − yir . So the worker keeps the local progress zir − yir made during communication, while still moving the communicated coordinates toward the average model. Special cases Our method combines three algorithmic ingredients: local training, sparse communication, and communication-computation overlap. Each of them can be turned off, yielding variants that are covered by existing methods in the literature; see Table 1 Setting ζ = 0 removes communication-computation overlap. Indeed, then Qi = 0 for every worker, so no local steps are taken while communication is in flight. This does not remove communication itself; rather, it specializes the model to the case in which communication contributes no extra time that could be overlapped with computation. Setting K = d removes sparsification, since then all coordinates are communicated. If, in addition, all workers have the same logical step time, τi = τ , then each worker takes the same number Ni = M of pre-communication local steps, which recovers the usual homogeneous Local SGD regime. The further special case M = 1 yields one local step per round; together with K = d and ζ = 0, this recovers synchronized Minibatch SGD. The choice τi = τ should be understood only as a specialization of the model to equal step counts per round, not as a literal requirement that the underlying hardware be homogeneous. 7

Connection to asynchronous SGD Our method is motivated by the same systems principle as asynchronous SGD [Agarwal and Duchi, 2011, Maranjyan, 2025]: workers should keep computing whenever possible instead of idling during synchronization or communication. The main difference is that our method retains an explicit round structure. During a round, workers continue optimizing while communication is in flight, but at the end of the round they all receive the same server message and update from it. In asynchronous SGD, by contrast, there is no such round-level synchronization: updates are applied whenever a worker finishes a stochastic-gradient computation, which leads to stale information. For this reason, our method is more structured than asynchronous SGD, yet it still contains a controlled form of staleness. The server message is formed from the older iterates yir , while by the time that message is used each worker has already advanced to zir . When K < d, only a subset of coordinates is synchronized in each round, which makes the method closer in spirit to asynchronous training than classical Local SGD. When K = d, this sparsity effect disappears, and the method becomes Local SGD with communication-computation overlap and delayed full-model averaging. In this sense, the method sits between Local SGD and asynchronous SGD. A closely related work is that of Tyurin and Sivtsov [2026], which allows local training and asynchronous model averaging, but does not include model sparsification.

Theory

Before we state our main result, we collect the aggregate quantities that appear in the rate. n

N̄ :=

1X Ni , n i=1

H̄ :=

SN :=

n X

1X Hi , n i=1

Ni2 ,

Hmax := max Hi , 1≤i≤n

n X

SQ :=

i=1

Q2i ,

(7)

(8)

i=1

These quantities summarize the amount and distribution of local computation in one round: N̄ and H̄ are the average numbers of pre-communication and total local steps, Hmax is the largest total number of local steps performed by any worker, and SN and SQ are the corresponding squared aggregates for the pre-communication and overlap phases. Finally, define ΨH :=

n H i −1 X X

t2 =

i=1 t=0

n X (Hi − 1)Hi (2Hi − 1)

i=1

(9)

The quantity ΨH captures the cumulative within-round drift created by taking multiple local SGD steps before the next synchronization. In particular, ΨH = 0 when every worker performs only one local step per round. We can now state the main convergence guarantee for Algorithm 1. Theorem 4.1 (Convergence guarantee). Consider Algorithm 1, initialized with x0i = x0 ∈ Rd ,

i = 1, . . . , n.

Let Assumptions 2.2 to 2.7 hold. Choose a stepsize η satisfying 0<η≤

1 , 8LHmax

D := 1 +

q . β

Then for every R ≥ 1, the average iterate x̄r := n1 R−1 1 X E ∥∇f (x̄r )∥2 ≤ R r=0

r i=1 xi , satisfies

4(f (x0 ) − f ⋆ ) 4Lησ 2 + n η H̄R +

6L2 η 2 G2 ΨH 6L2 η 2 G2 Hmax BSN + DSQ + , 1−c nH̄ nH̄

(10)

where H̄ is defined in (7), SN and SQ are defined in (8), and ΨH is defined in (9).

Interpretation The bound in (10) separates four effects. The first term is the optimization term, which scales inversely with η H̄R. Larger effective local progress per round, as captured by η H̄, reduces the required number of communication rounds R. Note, however, that the permissible stepsize η must scale with 1/Hmax to ensure convergence, meaning the effective progress η H̄ is constrained by the system heterogeneity ratio H̄/Hmax . We account for this trade-off explicitly in the wall-clock time complexity of Corollary 4.1. The second term is the stochastic noise term, and it retains the familiar 1/n variance reduction from averaging across workers that arises from Minibatch SGD [Cotter et al., 2011, Gower et al., 2019]. The third term is the intrinsic local-drift penalty. It is present even with full communication and zero delay, simply because workers take several local steps before they resynchronize. The fourth term captures disagreement caused by delayed and partial synchronization. Its SN -part comes from the fact that the communicated model is formed only after Ni local steps, while its SQ -part is the additional price of continuing local optimization during the overlap window. This term is also amplified when K is smaller, since then q = 1 − K/d is larger, which increases the constants c, B, and D. In other words, synchronizing fewer coordinates makes the residual disagreement harder to control. Two simplifications are worth keeping in mind. When ζ = 0, we have Qi = 0 for all i ∈ [n] and SQ = 0, so the overlap-induced contribution inside the fourth term disappears. When K = d, we have q = 0, and hence c = B = 0 and D = 1, so the BSN part of the fourth term vanishes and only the delay part proportional to SQ remains. The third term involving ΨH is different: it is the intrinsic local-drift term, and it remains whenever workers take more than one local step per round. Most importantly, all disagreement terms scale as η 2 . Thus, the leading stochastic term has the same η-dependence as in standard SGD, while the extra price of local training, sparsification, and overlap appears only at higher order. Special cases

Theorem 4.1 recovers several regimes of independent interest.

Special case: Minibatch SGD Classical Minibatch SGD is recovered in the homogeneous setting τi = τ by taking M = 1, ζ = 0, and K = d. Then every round contains exactly one full synchronized step, so H̄ = Hmax = 1, ΨH = 0, and the disagreement terms vanish. Only the first two terms in (10) remain, and we obtain R−1 4(f (x0 ) − f ⋆ ) 4Lησ 2 1 X E ∥∇f (x̄r )∥2 ≤ + , R r=0 ηR n

which is the standard non-convex Minibatch SGD rate [Cotter et al., 2011, Gower et al., 2019]. Special case: local SGD As discussed already in Section 3, taking τi = τ , ζ = 0, and K = d recovers homogeneous Local SGD with M local steps per round. In that regime, the SQ -part of the fourth term disappears because there is no overlap, and the BSN -part disappears because there is no compression. The only higher-order correction left in (10) is then the usual local-drift term involving ΨH . Thus, the theorem reduces to the standard picture for Local SGD: increasing M improves the leading optimization term by reducing communication frequency, but it also increases the drift within each round. Time complexity We now translate the convergence bound into round and time complexity. 9

Corollary 4.1 (Time complexity; proof in Section A.8). BS +DS Let ∆ := f (x0 ) − f ⋆ and X := ΨH + Hmax N1−c Q . Let r̂ be sampled uniformly at random from {0, 1, . . . , R − 1}, independently of the algorithmic history. Under the assumptions of Theorem 4.1, if the total number of communication rounds satisfies ! √ ∆LG X ∆LHmax ∆Lσ 2 √ + + R ≥ cR nεH̄ εH̄ ε3/2 H̄ nH̄ i h 2 ≤ ε. for a sufficiently large constant cR > 0, then E ∇f (x̄r̂ )

The corresponding bound on the wall-clock time complexity to achieve this guarantee is ! √ ∆Lσ 2 ∆LHmax ∆LG X √ O · τH + · τH + · τH , nε ε ε3/2 nH̄ τ +ζ = Pn n τ −1 is the harmonic mean of worker computation times. where τH := M H̄ i=1

The leading term in this bound keeps the standard linear-in-n minibatch speedup and depends on worker speed only through the harmonic mean τH . This leading term matches the dominant stochastic term that appears in recent asynchronous-SGD analyses such as Mishchenko et al. [2022a], Koloskova et al. [2022]. The effects of local training, sparsification, and overlap appear only through the higherorder correction terms involving X and Hmax . This is precisely the desirable regime: overlap can improve practical efficiency without changing the leading stochastic term, provided the additional disagreement terms remain controlled. For the Minibatch SGD special case above, τH = τ , and the leading term in the bound of Corollary 4.1 reduces to the standard O ∆Lσ 2 τ /(nε2 ) scaling. Thus, in the fully synchronized homogeneous regime, the time complexity is exactly the expected minibatch baseline.

Experiments

We evaluate the proposed overlap mechanism in a PyTorch logical-time simulator. Workers are separate model copies inside one deterministic process, so the experiments isolate the algorithmic effects of sparse communication, overlap, delay correction, and heterogeneous worker speeds without hardware or networking noise. The main experiments use a9a logistic regression with four workers, normalized features, batch size 256, matched initialization and seeds, and worker step times (1, 2, 3, 6) unless stated otherwise. We focus here on the sparse methods: blocking Local Sparse, Overlap overwrite, and Overlap delay-corrected; full metrics and ablations are deferred to the appendix. Figure 1 summarizes the main empirical conclusions. First, when the methods have the same round duration and communicate the same number of coordinates per round, comparing loss against rounds is sufficient: logical time and communication are common rescalings of the same index. In this matched setting, overlap improves substantially over blocking sparse averaging, and delay correction gives the best curve. This supports the intended mechanism: communication time is turned into useful local computation, and the delay-corrected merge preserves that progress instead of overwriting it. Second, the sparsity level provides the expected communication tradeoff. For the delay-corrected method, reducing the communicated fraction p shifts the curve left by orders of magnitude in logical bits while retaining similar optimization behavior, with only a mild loss penalty at the most aggressive sparsity levels. Third, when communication delay is large relative to the local compute window, the merge rule matters: delay correction clearly and consistently improves over naive overwrite. The same qualitative ordering appears in additional loss, accuracy, gradient-norm, time, and communication plots. We also ran nonconvex regularized versions of the logistic-regression experiments, but do not report them in the main paper because they did not lead to distinct conclusions. The appendix further studies the local computation budget, communication delay, and heterogeneous-data stress tests; the latter show that very large local budgets can be harmful outside the homogeneous-data 10

(a) Overlap comparison.

(b) Sparsity vs. communication.

Figure 1: Main experimental summary on a9a. (a) Overlap improves over blocking sparse averaging, and delay correction is best. (b) Smaller sparsity levels reduce the logical communication cost by orders of magnitude for the delay-corrected method. (c) Under a long communication delay, delay correction substantially outperforms overwrite. regime covered by the theory. It also includes CIFAR-10 and Tiny ImageNet neural-network experiments, where overlap improves logical-time accuracy while processed-example plots check whether the extra steps taken during communication remain useful at a fixed amount of local computation.

Conclusion

We studied local SGD with sparse model averaging, communication–computation overlap, and heterogeneous worker speeds in the data-homogeneous setting. We introduced a delay-corrected merge rule that incorporates delayed sparse synchronized information without discarding the local progress made during the overlap phase. For smooth non-convex objectives, we proved convergence guarantees and a time complexity bound showing that the leading stochastic term retains the standard linear-in-n minibatch speedup, while the additional cost of local training, sparsification, and overlap appears through higher-order disagreement terms. To the best of our knowledge, this is the first analysis that covers this combination of ingredients. The experiments support this picture. Across controlled comparisons and ablations, communication– computation overlap consistently improves over blocking sparse synchronization, and the delaycorrected merge consistently improves over naive overwrite, with the largest gains when communication delay is large. The results also show that aggressive sparsification can reduce communication by orders of magnitude with only a modest optimization penalty in the homogeneous-data regime, and that the delay-corrected variant is the most stable across different local-computation budgets. The main limitations are that the theory is restricted to the data-homogeneous setting and does not establish optimal time complexity. Extending the method and analysis to heterogeneous objectives, and understanding when overlap remains safe in that regime, is an important direction for future work.

Acknowledgments and Disclosure of Funding The research reported in this publication was supported by funding from King Abdullah University of Science and Technology (KAUST): i) KAUST Baseline Research Scheme, ii) CRG Grant ORFS-CRG12-2024-6460, and iii) Center of Excellence for Generative AI, under award number 5940.

References Alekh Agarwal and John C Duchi. Distributed delayed stochastic optimization. Advances in Neural Information Processing Systems, 24, 2011. (Cited on pages 3 and 8.) Thalaiyasingam Ajanthan, Sameera Ramasinghe, Gil Avraham, Hadi Mohaghegh Dolatabadi, Chamin P Hewa Koneputugodage, Violetta Shevchenko, Yan Zuo, and Alexander Long. AsyncMesh: Fully asynchronous optimization for data and pipeline parallelism. arXiv preprint arXiv:2601.22442, 2026. (Cited on page 2.) Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication-efficient SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems (NIPS), pages 1709–1720, 2017. (Cited on pages 2 and 3.)

Matt Beton, Seth Howes, Alex Cheema, and Mohamed Baioumy. Improving the efficiency of distributed training using sparse parameter averaging. In ICLR 2025 Workshop on Modularity for Collaborative, Decentralized, and Continual Deep Learning, 2025. URL https://openreview.net/forum?id=stFPf3gzq1. (Cited on pages 2 and 3.) Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. Journal of Machine Learning Research, 24(276):1–50, 2023. (Cited on page 3.) Laurent Condat, Artavazd Maranjyan, and Peter 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. (Cited on pages 2 and 3.) Laurent Condat, Artavazd Maranjyan, and Peter Richtárik. BiCoLoR: Communication-efficient optimization with bidirectional compression and local training. arXiv preprint arXiv:2601.12400, 2026. (Cited on page 3.) Andrew Cotter, Ohad Shamir, Nati Srebro, and Karthik Sridharan. Better mini-batch algorithms via accelerated gradient methods. Advances in Neural Information Processing Systems, 24, 2011. (Cited on page 9.) Arthur Douillard, Qixuan Feng, Andrei A Rusu, Rachita Chhaparia, Yani Donchev, Adhiguna Kuncoro, Marc’Aurelio Ranzato, Arthur Szlam, and Jiajun Shen. DiLoCo: Distributed low-communication training of language models. arXiv preprint arXiv:2311.08105, 2023. (Cited on page 3.) Arthur Douillard, Yanislav Donchev, Keith Rush, Satyen Kale, Zachary Charles, Zachary Garrett, Gabriel Teston, Dave Lacey, Ross McIlroy, Jiajun Shen, et al. Streaming DiLoCo with overlapping communication: Towards a distributed free lunch. arXiv preprint arXiv:2501.18512, 2025. (Cited on pages 2 and 3.) Anastasiia Filippova, Angelos Katharopoulos, David Grangier, and Ronan Collobert. Partial parameter updates for efficient distributed training. arXiv preprint arXiv:2509.22418, 2025. (Cited on page 3.) Louis Fournier, Adel Nabli, Masih Aminbeidokhti, Marco Pedersoli, Eugene Belilovsky, and Edouard Oyallon. WASH: Train your ensemble with communication-efficient weight shuffling, then average. 2024. (Cited on page 2.) Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General analysis and improved rates. In International Conference on Machine Learning, pages 5200–5209. PMLR, 2019. (Cited on page 9.) Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: Training ImageNet in 1 hour. arXiv preprint arXiv:1706.02677, 2017. (Cited on page 1.) Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck R. Cadambe. Local SGD with periodic averaging: Tighter analysis and adaptive synchronization. In Neural Information Processing Systems, 2019. (Cited on page 3.) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770–778, 2016. (Cited on page 40.) Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Foundations and Trends® in Machine Learning, 14(1–2):1–210, 2021. (Cited on page 1.) Satyen Kale, Arthur Douillard, and Yanislav Donchev. Eager updates for overlapped communication and computation in DiLoCo. arXiv preprint arXiv:2502.12996, 2025. (Cited on pages 2 and 3.) Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International conference on machine learning, pages 5132–5143. PMLR, 2020. (Cited on page 3.) Anastasiia Koloskova, Sebastian U Stich, and Martin Jaggi. Sharper convergence guarantees for asynchronous SGD for distributed and federated learning. Advances in Neural Information Processing Systems, 35: 17202–17215, 2022. (Cited on page 10.) Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, University of Toronto, Toronto, 2009. (Cited on page 38.)

Shen Li, Yanli Zhao, Rohan Varma, Omkar Salpekar, Pieter Noordhuis, Teng Li, Adam Paszke, Jeff Smith, Brian Vaughan, Pritam Damania, et al. Pytorch distributed: Experiences on accelerating data parallel training. arXiv preprint arXiv:2006.15704, 2020a. (Cited on page 1.) Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429–450, 2020b. (Cited on page 2.) Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of FedAvg on non-IID data. In International Conference on Learning Representations, 2020c. URL https://openreview. net/forum?id=HJxNAnVtDS. (Cited on page 3.) Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William J Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. arXiv preprint arXiv:1712.01887, 2017. (Cited on page 3.) Ammar Mahran, Artavazd Maranjyan, and Peter Richtárik. Rescaled asynchronous SGD: Optimal distributed optimization under data and system heterogeneity. arXiv preprint arXiv:2605.13434, 2026. (Cited on page 3.) Grigory Malinovsky, Kai Yi, and Peter Richtárik. Variance reduced ProxSkip: Algorithm, theory and application to federated learning. Advances in Neural Information Processing Systems, 35:15176–15189, 2022. (Cited on page 3.) Artavazd Maranjyan. First Provably Optimal Asynchronous SGD for Homogeneous and Heterogeneous Data. PhD thesis, King Abdullah University of Science and Technology, 2025. (Cited on pages 3 and 8.) Artavazd Maranjyan and Peter Richtárik. Ringleader ASGD: The first asynchronous SGD with optimal time complexity under data heterogeneity. In The Fourteenth International Conference on Learning Representations, 2026. URL https://openreview.net/forum?id=5wqTal0EuC. (Cited on page 3.) Artavazd Maranjyan, Omar Shaikh Omar, and Peter Richtárik. Mindflayer SGD: Efficient parallel SGD in the presence of heterogeneous and random worker compute times. In The 41st Conference on Uncertainty in Artificial Intelligence, 2025a. (Cited on page 3.) Artavazd Maranjyan, El Mehdi Saad, Peter Richtárik, and Francesco Orabona. ATA: Adaptive task allocation for efficient resource management in distributed machine learning. In International Conference on Machine Learning, 2025b. (Cited on page 2.) Artavazd Maranjyan, Mher Safaryan, and Peter Richtárik. GradSkip: Communication-accelerated local gradient methods with better computational complexity. Transactions on Machine Learning Research, 2025c. ISSN 2835-8856. URL https://openreview.net/forum?id=6R3fRqFfhn. (Cited on page 2.) Artavazd Maranjyan, Alexander Tyurin, and Peter Richtárik. Ringmaster ASGD: The first asynchronous SGD with optimal time complexity. In International Conference on Machine Learning, 2025d. (Cited on page 3.) Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communicationefficient learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273–1282. PMLR, 2017. (Cited on pages 1, 2, and 3.) Konstantin Mishchenko, Francis Bach, Mathieu Even, and Blake E Woodworth. Asynchronous SGD beats minibatch SGD under arbitrary delays. Advances in Neural Information Processing Systems, 35:420–433, 2022a. (Cited on page 10.) Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. ProxSkip: Yes! Local gradient steps provably lead to communication acceleration! Finally! In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 15750– 15769. PMLR, 17–23 Jul 2022b. URL https://proceedings.mlr.press/v162/mishchenko22b.html. (Cited on page 3.) Philipp Moritz, Robert Nishihara, Ion Stoica, and Michael I Jordan. Sparknet: Training deep networks in spark. arXiv preprint arXiv:1511.06051, 2015. (Cited on page 3.) Daniel Povey, Xiaohui Zhang, and Sanjeev Khudanpur. Parallel training of DNNs with natural gradient and parameter averaging. arXiv preprint arXiv:1410.7455, 2014. (Cited on page 3.) Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. HOGWILD!: A lock-free approach to parallelizing stochastic gradient descent. Advances in Neural Information Processing Systems, 24, 2011. (Cited on page 3.)

Abdurakhmon Sadiev, Artavazd Maranjyan, Ivan Ilin, and Peter Richtárik. Ringmaster LMO: Asynchronous linear minimization oracle momentum method. arXiv preprint arXiv:2605.18174, 2026. (Cited on page 3.) Weigao Sun, Zhen Qin, Weixuan Sun, Shidi Li, Dong Li, Xuyang Shen, Yu Qiao, and Yiran Zhong. CO2: Efficient distributed training with full communication-computation overlap. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=ZO5cn4IfaN. (Cited on pages 2 and 3.) Zhirayr Tovmasyan, Artavazd Maranjyan, and Peter Richtárik. Rennala MVR: Improved time complexity for parallel stochastic optimization via momentum-based variance reduction. arXiv preprint arXiv:2605.08871, 2026. (Cited on page 3.) Alexander Tyurin and Peter Richtárik. Optimal time complexities of parallel stochastic optimization methods under a fixed computation model. In Advances in Neural Information Processing Systems, volume 36, pages 16515–16577, 2023. (Cited on page 3.) Alexander Tyurin and Danil Sivtsov. Birch SGD: A tree graph framework for local and asynchronous SGD methods. In The Fourteenth International Conference on Learning Representations, 2026. URL https: //openreview.net/forum?id=KBdVCipTBM. (Cited on pages 3 and 8.) Jianyu Wang and Gauri Joshi. Cooperative SGD: A unified framework for the design and analysis of communication-efficient SGD algorithms. Journal of Machine Learning Research, 22:1–50, 2021. (Cited on page 3.) Jianyu Wang, Hao Liang, and Gauri Joshi. Overlap local-SGD: An algorithmic approach to hide communication delays in distributed SGD. arXiv preprint arXiv:2002.09539, 2020. (Cited on pages 2 and 3.) Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al. A field guide to federated optimization. arXiv preprint arXiv:2107.06917, 2021. (Cited on page 1.) Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparsification for communication-efficient distributed optimization. Advances in Neural Information Processing Systems, 31, 2018. (Cited on pages 2 and 3.) Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcmahan, Ohad Shamir, and Nathan Srebro. Is local SGD better than minibatch SGD? In International Conference on Machine Learning, pages 10334–10343. PMLR, 2020. (Cited on page 3.) Hao Yu, Sen Yang, and Shenghuo 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, pages 5693–5700, 2019. (Cited on page 3.) Yanli Zhao, Andrew Gu, Rohan Varma, Liang Luo, Chien-Chin Huang, Min Xu, Less Wright, Hamid Shojanazeri, Myle Ott, Sam Shleifer, et al. Pytorch fsdp: experiences on scaling fully sharded data parallel. arXiv preprint arXiv:2304.11277, 2023. (Cited on page 1.) Martin Zinkevich, Markus Weimer, Lihong Li, and Alex Smola. Parallelized stochastic gradient descent. In J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 23. Curran Associates, Inc., 2010. URL https://proceedings.neurips. cc/paper_files/paper/2010/file/abea47ba24142ed16b7d8fbf2c740e0d-Paper.pdf. (Cited on pages 1, 2, and 3.)

Contents 1

Introduction

1.1

Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2

Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Problem setup

Local SGD with communication-computation overlap and infrequent sparse model averaging

4 Theory

Experiments

Conclusion

A Proofs

A.1 Within-round dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

A.2 Exact evolution of the average . . . . . . . . . . . . . . . . . . . . . . . . . . . .

A.3 Variance reduction by worker averaging . . . . . . . . . . . . . . . . . . . . . . .

A.4 Within-round drift bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

A.5 Disagreement recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

A.6 One-round descent inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

A.7 Proof of Theorem 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

A.8 Proof of Corollary 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

B Additional Experimental Details

B.1 External experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

B.2 Merge-rule comparison across regimes . . . . . . . . . . . . . . . . . . . . . . . .

B.3 Sparsity-level ablation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

B.4 Ablation on the local computation budget . . . . . . . . . . . . . . . . . . . . . .

B.5 Effect of communication delay . . . . . . . . . . . . . . . . . . . . . . . . . . . .

B.6 CIFAR-10 neural-network experiments . . . . . . . . . . . . . . . . . . . . . . . .

B.7 Tiny ImageNet neural-network experiments . . . . . . . . . . . . . . . . . . . . .

Proofs

This section collects the proofs of the main technical results. A.1

Within-round dynamics

At the beginning of round r, worker i holds a model xri ∈ Rd . Its local trajectory within the round is r := xri , wi,0

r r r r wi,t+1 = wi,t − ηr gi (wi,t , ξi,t ),

t = 0, 1, . . . , Hi − 1.

(11)

We define r yir := wi,N , i

r zir := wi,H . i

(12)

We also define the round averages n

x̄r :=

1X r x , n i=1 i

ȳ r :=

1X r y , n i=1 i

z̄ r :=

1X r z . n i=1 i

(13)

The delay-corrected merge is xr+1 = ProjSr ȳ r + zir − yir + (I − ProjSr )zir = zir + ProjSr (ȳ r − yir ), i

(14)

where Sr ⊆ [d] is a uniformly random subset of cardinality K, shared by all workers. A.2

Exact evolution of the average

We now state and prove our first lemma, characterizing the exact evolution of the average x̄r . Lemma A.1 (Exact evolution of the average). For every round r, x̄r+1 = z̄ r = x̄r − ηr Gr , where Gr :=

Hmax X−1

ḡtr ,

ḡtr :=

t=0

1 X r r gi (wi,t , ξi,t ). n

(15)

(16)

i∈At

Proof. Averaging the corrected merge formula gives n (13) 1 X

x̄r+1 =

n i=1

xr+1 i

(14)

= =

n 1 X r zi + ProjSr (ȳ r − yir ) n i=1 n n 1X r 1X zi + ProjSr (ȳ r − yir ) n i=1 n i=1 ! n X 1 z̄ r + ProjSr (ȳ r − yir ) n i=1

z̄ r + ProjSr (0) = z̄ r .

Next, (12) r (11) r zir = wi,H = xi − ηr i

H i −1 X t=0

r r gi (wi,t , ξi,t ).

(17)

Averaging over i, we get n

z̄ r

1X r z n i=1 i

(13)

n n Hi −1 1X r 1X X r r xi − η r gi (wi,t , ξi,t ) n i=1 n i=1 t=0

(17)

n H −1

(13)

x̄r − ηr

(2)

x̄r − ηr

i 1X X r r gi (wi,t , ξi,t ) n i=1 t=0

Hmax X−1

1 X r r gi (wi,t , ξi,t ) n

t=0 (16)

i∈At

x̄ − ηr Gr .

Combining the two identities proves the claim. A.3

Variance reduction by worker averaging

For i ∈ At , define

r r r εri,t := gi (wi,t , ξi,t ) − ∇f (wi,t ),

(18)

and further let ε̄rt

1 X r εi,t . n

(19)

i∈At

Plugging (18) into (19) gives ε̄rt

(18)+(19)

(16)

1 X r r r gi (wi,t , ξi,t ) − ∇f (wi,t ) n i∈At 1 X r ḡtr − ∇f (wi,t ). n i∈At

Lemma A.2 (Variance reduction at local time t). Under Assumption 2.4 (independent samples) and Assumption 2.6 (bounded variance), for every round r and local time t, we have mt E ∥ε̄rt ∥2 Fr,t ≤ 2 σ 2 n and Hmax X−1 H̄ E ∥ε̄rt ∥2 {xri }ni=1 ≤ σ 2 . n t=0

Proof. Conditioned on Fr,t , the vectors {εri,t , i ∈ At }, are independent and conditionally mean zero. Therefore,   2 X r 2 (19) 1 1 X r 2 r E ∥ε̄t ∥ Fr,t = 2 E  εi,t Fr,t  = 2 E ∥εi,t ∥ Fr,t , (20) n n i∈At

i∈At

because the cross terms vanish. By Assumption 2.6, we have E ∥εri,t ∥2 Fr,t ≤ σ 2 . 17

Plugging this into (20), and recalling that mt = |At |, we get mt E ∥ε̄rt ∥2 Fr,t ≤ 2 σ 2 . n

(21)

Summing the above inequality over t ∈ {0, . . . , Hmax − 1} and using Hmax X−1

(2)

t=0

Hmax X−1

|At |

t=0 (2)

Hmax X−1

|{i ∈ {1, . . . , n} : Hi > t}|

t=0

Hmax n X−1 X t=0

= =

n Hmax X X−1 i=1 n X

1(Hi > t)

i=1

1(Hi > t)

t=0 (7)

Hi = nH̄,

(22)

i=1

we obtain

Hmax X−1

∥ε̄rt ∥2

t=0

(21) 1 Fr,t ≤ 2 n

Hmax X−1

! mt

(22) H̄

σ2 =

t=0

σ2 .

Taking conditional expectation with respect to {xri }ni=1 and using the tower property, we obtain Hmax X−1 t=0

A.4

X−1 H̄ Hmax E E ∥ε̄rt ∥2 Fr,t {xri }ni=1 ≤ σ 2 . E ∥ε̄rt ∥2 {xri }ni=1 = n t=0

Within-round drift bounds

Define n

uri := yir − xri ,

vir := zir − yir ,

ūr :=

1X r u , n i=1 i

v̄ r :=

1X r v . n i=1 i

(23)

Lemma A.3 (Within-round local drift). Let Assumption 2.4 (independent samples) and Assumption 2.7 (bounded second moment) hold. Then, for every round r, worker i, and local time t ∈ {0, . . . , Hi }, we have r E ∥wi,t − xri ∥2 {xrj }nj=1 ≤ ηr2 t2 G2 , (24)

" n X i=1 " n X

# ∥uri − ūr ∥2

{xrj }nj=1

∥vir − v̄ r ∥2

{xrj }nj=1

≤ ηr2 G2 SN ,

(25)

≤ ηr2 G2 SQ .

(26)

i=1

Moreover, n H i −1 X X r E ∥wi,t − xri ∥2 {xrj }nj=1 ≤ ηr2 G2 ΨH . i=1 t=0

(27)

Proof. We begin with the identity (11)

r wi,t − xri = −ηr

t−1 X

r r gi (wi,s , ξi,s ).

(28)

s=0

Using Cauchy-Schwarz, we obtain (28)

r ∥wi,t − xri ∥2 = ηr2

t−1 X

2 r r gi (wi,s , ξi,s )

≤ ηr2 t

s=0

t−1 X

r r ∥gi (wi,s , ξi,s )∥2 .

(29)

s=0

Taking conditional expectation and using the tower property together with Assumption 2.7, we get r r r r (30) , ξi,s )∥2 Fr,s {xrj }nj=1 ≤ G2 . E ∥gi (wi,s , ξi,s )∥2 {xrj }nj=1 = E E ∥gi (wi,s Substituting into (29), we obtain (29)+(30) 2 2 2 r ≤ ηr t G . E ∥wi,t − xri ∥2 {xrj }nj=1

(31)

Summing (31) over i and t, we get n H n H i −1 i −1 X X X X r (31) (9) E ∥wi,t − xri ∥2 {xrj }nj=1 ≤ ηr2 G2 t2 = ηr2 G2 ΨH . i=1 t=0

i=1 t=0

Next, by definition, (23)

(12)

(11)

r uri = yir − xri = wi,N − xri = −ηr i

N i −1 X

r r gi (wi,t , ξi,t ).

(32)

r r ∥gi (wi,t , ξi,t )∥2 .

(33)

t=0

Using Cauchy-Schwarz again, we obtain (32) ∥uri ∥2 = ηr2

N i −1 X

2 r r gi (wi,t , ξi,t )

≤ ηr2 Ni

t=0

N i −1 X t=0

Taking conditional expectation and using (30), we get (33)+(30) 2 2 2 ≤ ηr Ni G . (34) E ∥uri ∥2 {xrj }nj=1 P n Recall that ūr := n1 i=1 uri . Since the variance of the vectors {uri }ni=1 can be bounded by their second moment, i.e., n n 1X r 2 1X r ∥ui − ūr ∥2 ≤ ∥u ∥ , (35) n i=1 n i=1 i we obtain E

" n X

# ∥uri − ūr ∥2

{xrj }nj=1

(35)+(34)

n X

≤

ηr2 G2

(8)

ηr2 G2 SN .

i=1

Ni2

i=1

Finally, by definition, (23)

(12)

(11)

r r vir = zir − yir = wi,H − wi,N = −ηr i i

H i −1 X

r r gi (wi,t , ξi,t ),

(36)

t=Ni

which contains exactly Qi = Hi − Ni terms. Using (36) and Cauchy-Schwarz, we obtain (36) ∥vir ∥2 = ηr2

H i −1 X

2 r r gi (wi,t , ξi,t )

t=Ni

≤ ηr2 Qi

H i −1 X t=Ni

r r ∥gi (wi,t , ξi,t )∥2 .

(37)

Taking conditional expectation and using (30) and (4), we get (37)+(30)+(4) 2 2 2 E ∥vir ∥2 {xrj }nj=1 ≤ ηr Qi G .

(38)

Using n X

∥vir − v̄ r ∥2 ≤

i=1

n X

∥vir ∥2 ,

(39)

i=1

which is an analogue of the bound (35) applied to the vectors {vir }ni=1 , we obtain # " n n X X (39)+(38) r n 2 2 r r 2 ≤ ηr G Q2i E ∥vi − v̄ ∥ {xj }j=1 i=1

i=1 (8)

ηr2 G2 SQ .

This proves (24)–(27). A.5

Disagreement recursion

Define the disagreement related to the vectors {xri }ni=1 and {yir }ni=1 as X r :=

n X

∥xri − x̄r ∥2 ,

Y r :=

n X

∥yir − ȳ r ∥2 .

(40)

i=1

Analogously, define the disagreement quantities U r :=

n X

∥uri − ūr ∥2 ,

V r :=

n X

∥vir − v̄ r ∥2 ,

Z r :=

∥zir − z̄ r ∥2 .

(41)

i=1

n X

Lemma A.4 (Disagreement recursion). Fix any parameters α > 0 and β > 0, and define c := q(1 + α)(1 + β),

1 B := q(1 + β) 1 + , α

D := 1 +

q . β

Then, under Assumption 2.4 (mutual independence) and Assumption 2.7 (bounded second moment), for every round r, we have E X r+1 {xri }ni=1 ≤ cX r + ηr2 G2 BSN + DSQ . (42)

Proof. By Lemma A.1, we have x̄r+1 = z̄ r . Therefore, for each worker i, xr+1 − x̄r+1 i

(14)

= =

zir + ProjSr (ȳ r − yir ) − z̄ r zir − z̄ r − ProjSr (yir − ȳ r )

(23)

(yir − ȳ r ) + (vir − v̄ r ) − ProjSr (yir − ȳ r ) (I − ProjSr )(yir − ȳ r ) + (vir − v̄ r ).

= =

(43)

Because yir and zir are deterministic functions of the initial points x0i , historical masks, and data samples up to round r, Assumption 2.4 ensures that the mask Sr is independent of {yir , zir }ni=1 . Its conditional distribution remains uniform and each coordinate is not selected with probability q = 1 − p. For any fixed vectors a, b, we have E ∥(I − ProjSr )a + b∥2 = q∥a∥2 + 2q ⟨a, b⟩ + ∥b∥2 . Applying this with

a = yir − ȳ r ,

b = vir − v̄ r , 20

and using (43), we get E ∥xr+1 − x̄r+1 ∥2 {yir , zir }ni=1 = i

q∥yir − ȳ r ∥2 + 2q ⟨yir − ȳ r , vir − v̄ r ⟩ + ∥vir − v̄ r ∥2

q∥(yir − ȳ r ) + (vir − v̄ r )∥2 + p∥vir − v̄ r ∥2

q∥zir − z̄ r ∥2 + p∥vir − v̄ r ∥2 .

(44)

Summing (44) over i, we obtain E X r+1 {yir , zir }ni=1

n X

∥zir − z̄ r ∥2 + p

i=1 (41)

n X

∥vir − v̄ r ∥2

i=1

qZ + pV .

(45)

Next, using the identity

zir − z̄ r = (yir − ȳ r ) + (vir − v̄ r ) which follows from (23), we estimate qZ r + pV r . For any vectors a, b, we can estimate q∥a + b∥2 + p∥b∥2

q∥a∥2 + 2q ⟨a, b⟩ + (q + p)∥b∥2

q∥a∥2 + 2q ⟨a, b⟩ + ∥b∥2 q ∥b∥2 , q(1 + β)∥a∥2 + 1 + β

≤ where we used the inequality

2q ⟨a, b⟩ ≤ qβ∥a∥2 + Applying (46) with

a = yir − ȳ r ,

(46)

q ∥b∥2 . β

b = vir − v̄ r ,

and summing over i, gives r

qZ + pV

≤ =

q q(1 + β)Y + 1 + β q(1 + β)Y r + DV r . r

Vr (47)

It remains to control Y r . Since (23)

yir − ȳ r = (xri − x̄r ) + (uri − ūr ), using Young’s inequality leads to Yr

(41)

n X

∥yir − ȳ r ∥2

i=1

n X

∥(xri − x̄r ) + (uri − ūr )∥2

i=1

≤ (40)+(41)

n X 1 r r 2 r r 2 (1 + α)∥xi − x̄ ∥ + 1 + ∥ui − ū ∥ α i=1 1 r (1 + α)X + 1 + U r. α

(48)

Combining (45), (47), and (48), we obtain (45) E X r+1 {yir , zir }ni=1 = qZ r + pV r (47)

≤

q(1 + β)Y r + DV r

(48)

1 q(1 + β)(1 + α)X r + q(1 + β) 1 + U r + DV r α cX r + BU r + DV r .

≤

(49)

Finally, taking conditional expectation with respect to {xri }ni=1 and using (25)–(26), we get (49)

E X r+1 {xri }ni=1

cX r + BE [ U r | {xri }ni=1 ] + DE [ V r | {xri }ni=1 ]

≤

(25)+(26)

cX r + ηr2 G2 (BSN + DSQ ).

≤

(50)

This proves (42). Corollary A.1 (Accumulated disagreement bound). Assume x0i = x0 for all i, so that X 0 = 0, and assume ηr ≡ η for all r. If c = q(1 + α)(1 + β) < 1, then R−1 X

η 2 G2 BSN + DSQ E [X ] ≤ R 1−c r=0

(51)

for every R ≥ 1.

Proof. Let δ r := E [X r ]. Taking full expectation in (42), and using ηr ≡ η, gives (42)

δ r+1 ≤ cδ r + C, 2

(52)

where C := η G (BSN + DSQ ). Since x0i = x0 for all i, we have X 0 = 0,

δ 0 = E X 0 = 0.

We now prove by induction that, for every r ≥ 0, δr ≤ C

r−1 X

cj ,

(53)

j=0

where the sum is interpreted as 0 when r = 0. For r = 0, (53) gives δ 0 ≤ 0, which holds since δ 0 = 0. Suppose now that (53) holds for some r ≥ 0. Then (52)

(53)

δ r+1 ≤ cδ r + C ≤ cC

r−1 X

cj + C = C

j=0

r X

cj + C = C

j=1

r X

cj .

j=0

Thus (53) holds for all r ≥ 0. Since c < 1, we have r−1 X

cj ≤

j=0

1 , 1−c

and therefore

η 2 G2 (BSN + DSQ ) C = . 1−c 1−c Summing (54) over r = 0, . . . , R − 1, we get (53)

δr ≤

R−1 X

E [X r ]

r=0

R−1 X

δr

r=0 (54)

≤

η 2 G2 (BSN + DSQ ) . 1−c

This proves (51). 22

(54)

A.6

One-round descent inequality

Define ¯ r := 1 ∇ t n

r ∇f (wi,t ),

ḡtr :=

i∈At

1 X r r gi (wi,t , ξi,t ), n

Gr :=

Hmax X−1

ḡtr .

(55)

t=0

i∈At

Lemma A.5 (One-round descent). Let Assumption 2.3 (smoothness), Assumption 2.4 (independent samples), Assumption 2.5 (unbiasedness), Assumption 2.6 (bounded variance), and Assumption 2.7 (bounded second moment) be satisfied. Then for every round r, we have H̄ E f (x̄r+1 ) {xri }ni=1 ≤ f (x̄r ) − ηr − 2Lηr H̄Hmax ∥∇f (x̄r )∥2 2 2 L Hmax 1 + 4Lηr Hmax X r + ηr n σ2 + Lηr2 H̄ n 2 3 2 ΨH + L ηr G 1 + 4Lηr Hmax . (56) n

Proof. By Lemma A.1, we have (15)

x̄r+1 = x̄r − ηr Gr . Hence, by L-smoothness of f (Assumption 2.3), f (x̄r+1 )

≤

f (x̄r ) − ηr ⟨∇f (x̄r ), Gr ⟩ +

Lηr2 ∥Gr ∥2 . 2

(57)

Taking conditional expectation given {xri }ni=1 , we obtain (57) Lηr2 E f (x̄r+1 ) {xri }ni=1 ≤ f (x̄r ) − ηr E [ ⟨∇f (x̄r ), Gr ⟩| {xri }ni=1 ] + E ∥Gr ∥2 {xri }ni=1 . (58) 2 Step 1: lower bound the inner-product term. E [ ḡtr | Fr,t ]

Using unbiasedness, we get

Assumption 2.5

¯ rt , ∇

(59)

and hence E [ ⟨∇f (x̄r ), Gr ⟩| {xri }ni=1 ]

(59)+(55)

Hmax X−1

¯r ∇f (x̄r ), ∇ t

{xri }ni=1 .

(60)

t=0

Further, ¯ rt ∇f (x̄r ), ∇

(55) 1

r ∇f (x̄r ), ∇f (wi,t ) .

(61)

i∈At

Using the inequality 1 1 ∥a∥2 − ∥a − b∥2 , 2 2 r with a = ∇f (x̄r ), b = ∇f (wi,t ), and then using L-Lipschitz continuity of ∇f (cf. Assumption 2.3), we obtain 1 L2 r r ∇f (x̄r ), ∇f (wi,t ) ≥ ∥∇f (x̄r )∥2 − ∥wi,t − x̄r ∥2 . (62) 2 2 Plugging (62) into (61), and using mt = |At |, we get mt L2 X r ¯ rt ∇f (x̄r ), ∇ ∥∇f (x̄r )∥2 − ∥wi,t − x̄r ∥2 . (63) ≥ 2n 2n ⟨a, b⟩ ≥

i∈At

Taking conditional expectation and summing over t, E [ ⟨∇f (x̄ ), Gr ⟩| {xri }ni=1 ]

Hmax X−1

1 2n

(60)+(63)

≥

−

! mt

∥∇f (x̄r )∥2

t=0

n H i −1 2 X X

r L E ∥wi,t − x̄r ∥2 {xri }ni=1 2n i=1 t=0

H̄ ∥∇f (x̄r )∥2 2 n Hi −1 r L2 X X − E ∥wi,t − x̄r ∥2 {xri }ni=1 , 2n i=1 t=0

(64)

where in the last step we have used the identity Hmax X−1

n (2) X

mt =

t=0

(7)

Hi = nH̄.

i=1

Next, using the decomposition r r wi,t − x̄r = (xri − x̄r ) + (wi,t − xri ),

Young’s inequality

∥a + b∥2 ≤ 2∥a∥2 + 2∥b∥2 ,

and Lemma A.3, we get r E ∥wi,t − x̄r ∥2 {xri }ni=1 ≤ 2∥xri − x̄r ∥2 + 2ηr2 t2 G2 .

(65)

Summing over i and t, we obtain n H i −1 X X r E ∥wi,t − x̄r ∥2 {xri }ni=1

n H i −1 X X

(65)

≤

2∥xri − x̄r ∥2 + 2ηr2 t2 G2

i=1 t=0

n H i −1 X X

∥xri − x̄r ∥2 + 2ηr2 G2

i=1 t=0 (9)

n X

n H i −1 X X

i=1 t=0

Hi ∥xri − x̄r ∥2 + 2ηr2 G2 ΨH

i=1

≤

2Hmax

n X

∥xri − x̄r ∥2 + 2ηr2 G2 ΨH

i=1 (40)

2Hmax X r + 2ηr2 G2 ΨH .

(66)

Substituting (66) into (64), we get E [ ⟨∇f (x̄r ), Gr ⟩| {xri }ni=1 ]

L2 Hmax r L2 ηr2 G2 H̄ ∥∇f (x̄r )∥2 − X − ΨH . 2 n n

≥

Step 2: upper bound the quadratic term. (55)+(19)

Let us write

Hmax X−1

¯r + ∇ t

t=0 2

(67)

Hmax X−1

ε̄rt .

t=0 2

Using Young’s inequality ∥a + b∥ ≤ 2∥a∥ + 2∥b∥ , we get     2 2 Hmax Hmax X−1 X−1 ¯ rt ε̄rt {xri }ni=1  . E ∥Gr ∥2 {xri }ni=1 ≤ 2E  ∇ {xri }ni=1  + 2E  t=0

t=0

(68)

First, let’s bound the first term on the right-hand side of (68). Using the Jensen’s inequality bound Hmax X−1

≤ Hmax

Hmax X−1

∥at ∥2 ,

t=0

and arguments identical to those leading to (66) (we repeat the same decomposition and apply Lemma A.3), we obtain the bound   2 Hmax 2 X−1 4L2 Hmax 4L2 ηr2 G2 Hmax ¯ rt E ∇ {xri }ni=1  ≤ 2H̄Hmax ∥∇f (x̄r )∥2 + Xr + ΨH . (69) n n t=0 Second, we bound the second term on the right-hand side of (68). We first explain why the cross terms vanish. Recall that 1 X r r r ε̄rt = gi (wi,t , ξi,t ) − ∇f (wi,t ) . n i∈At

r By Assumption 2.5, and since wi,t is Fr,t -measurable, we have E [ ε̄rt | Fr,t ] = 0. (70) r Moreover, for any s < t, the vector ε̄s is Fr,t -measurable, since it depends only on randomness revealed before time t. Therefore, E [ ⟨ε̄rs , ε̄rt ⟩| {xri }ni=1 ] = E [ E [ ⟨ε̄rs , ε̄rt ⟩| Fr,t ]| {xri }ni=1 ] = E [ ⟨ε̄rs , E [ ε̄rt | Fr,t ]⟩| {xri }ni=1 ] (70)

= 0. (71) This shows that the sequence {ε̄rt } is a martingale difference sequence, and hence different-time noise terms are orthogonal in conditional expectation. Now expand the squared norm:   2 Hmax X−1 E ε̄rt {xri }ni=1 

 =

E

Hmax X−1

t=0

 ∥ε̄rt ∥2 + 2

⟨ε̄rs , ε̄rt ⟩ {xri }ni=1 

0≤s<t≤Hmax −1

t=0 Hmax X−1

E ∥ε̄rt ∥2 {xri }ni=1

t=0

E [ ⟨ε̄rs , ε̄rt ⟩| {xri }ni=1 ]

0≤s<t≤Hmax −1 (71)

Hmax X−1

E ∥ε̄rt ∥2 {xri }ni=1 .

(72)

t=0

Finally, applying Lemma A.2, we obtain   2 Hmax X−1 E ε̄rt {xri }ni=1 

(72)

t=0

Hmax X−1

E ∥ε̄rt ∥2 {xri }ni=1

t=0 Lemma A.2

≤

Hmax X−1 t=0

= (22)

mt 2 σ n2

2 Hmax X−1

σ n2

t=0

σ2 H̄ · nH̄ = σ 2 . n2 n

Combining (68), (69), and (73), we obtain 2 8L2 Hmax E ∥Gr ∥2 {xri }ni=1 ≤ 4H̄Hmax ∥∇f (x̄r )∥2 + Xr n 8L2 ηr2 G2 Hmax H̄ ΨH + 2 σ 2 . + n n 25

(73)

(74) (75)

Step 3: conclude.

Substituting (67) and (75) into (58), and collecting terms, yields H̄ − 2Lηr H̄Hmax ∥∇f (x̄r )∥2 E f (x̄r+1 ) {xri }ni=1 ≤ f (x̄r ) − ηr 2 2 L Hmax σ2 1 + 4Lηr Hmax X r + Lηr2 H̄ + ηr n n 2 3 2 ΨH + L ηr G 1 + 4Lηr Hmax , n which is (56). A.7

Proof of Theorem 4.1

Theorem 4.1 (Convergence guarantee). Consider Algorithm 1, initialized with x0i = x0 ∈ Rd ,

i = 1, . . . , n.

Let Assumptions 2.2 to 2.7 hold. Choose a stepsize η satisfying 0<η≤

1 , 8LHmax

where Hmax is defined in (7). Choose the sparsification coefficient K ∈ {1, . . . , d}, let q =1− K d as in (6), and choose parameters α > 0 and β > 0 such that c := q(1 + α)(1 + β) < 1. Further, define 1 q B := q(1 + β) 1 + , D := 1 + . α β Pn r := 1 r Then for every R ≥ 1, the average iterate x̄ i=1 xi , satisfies n R−1 1 X E ∥∇f (x̄r )∥2 ≤ R r=0

4(f (x0 ) − f ⋆ ) 4Lησ 2 + n η H̄R +

6L2 η 2 G2 ΨH 6L2 η 2 G2 Hmax BSN + DSQ + , 1−c nH̄ nH̄

(10)

where H̄ is defined in (7), SN and SQ are defined in (8), and ΨH is defined in (9).

Proof. Taking full expectation in Lemma A.5, and using ηr ≡ η, gives (56) H̄ r+1 r E f (x̄ ) ≤ E [f (x̄ )] − η − 2Lη H̄Hmax E ∥∇f (x̄r )∥2 2 L2 Hmax σ2 +η 1 + 4LηHmax E [X r ] + Lη 2 H̄ n n 2 3 2 ΨH +L η G 1 + 4LηHmax . n

(76)

Since η ≤ 8LH1max , we have 4LηHmax

1 , 2

≤

(77)

and therefore, (77)

1 + 4LηHmax 26

≤

3 2

(78)

and H̄ − 2Lη H̄Hmax = H̄ 2

1 − 2LηHmax 2

(77) H̄

≥

(79)

Using (79) and (78) in (76), we obtain E f (x̄r+1 ) ≤

η H̄ E ∥∇f (x̄r )∥2 4 3 L2 Hmax σ2 3 ΨH + η E [X r ] + Lη 2 H̄ + L2 η 3 G2 . 2 n n 2 n E [f (x̄r )] −

(80)

Rearranging (80), we get 3 L2 Hmax E [f (x̄r )] − E f (x̄r+1 ) + η E [X r ] 2 n 3 ΨH σ2 + L2 η 3 G2 . +Lη 2 H̄ n 2 n Summing (81) over r = 0, . . . , R − 1, we obtain η H̄ E ∥∇f (x̄r )∥2 ≤ 4

R−1 η H̄ X E ∥∇f (x̄r )∥2 4 r=0

(81)

≤

R−1 X

(81)

E [f (x̄r )] − E f (x̄r+1 )

r=0 R−1 3 L2 Hmax X + η E [X r ] 2 n r=0

3 σ2 ΨH + RL2 η 3 G2 n 2 n 0 R f (x ) − E f (x̄ ) +RLη 2 H̄

R−1 3 L2 Hmax X E [X r ] + η 2 n r=0

+RLη 2 H̄ By Assumption 2.2 (lower-boundedness), we get f (x0 ) − E f (x̄R ) ≤

σ2 3 ΨH + RL2 η 3 G2 . n 2 n

f (x0 ) − f ⋆ .

(82)

(83)

Moreover, since X 0 = 0, ηr ≡ η, and c < 1, Corollary A.1 gives R−1 X

E [X r ]

Corollary A.1

≤

r=0

η 2 G2 (BSN + DSQ ) . 1−c

(84)

Substituting (83) and (84) into (82), we get R−1 η H̄ X E ∥∇f (x̄r )∥2 ≤ 4 r=0

f (x0 ) − f ⋆ + +RLη 2 H̄

3 L2 G2 Hmax BSN + DSQ Rη 3 2 n 1−c

σ2 3 ΨH + RL2 η 3 G2 . n 2 n

Dividing (85) by Rη H̄/4, we obtain R−1 1 X E ∥∇f (x̄r )∥2 ≤ R r=0

4(f (x0 ) − f ⋆ ) 6L2 η 2 G2 Hmax BSN + DSQ + 1−c η H̄R nH̄ +

4Lησ 2 6L2 η 2 G2 ΨH + . n nH̄

Finally, reordering the terms gives (10). 27

(85)

A.8

Proof of Corollary 4.1

Here we provide the proof of Corollary 4.1. Proof. Under the assumptions of Theorem 4.1, we have h E

∇f (x̄r̂ )

R−1 i 1 X h ∆ ηLσ 2 L2 G2 X 2 E ∥∇f (x̄r )∥ ≤ c0 · + c1 · + c2 · η 2 . R r=0 n η H̄R nH̄

For the variance term to satisfy c1 ηLσ n

εn 2 > 0. For the ≤ 3ε , we require η ≤ 3c11 Lσ 2 when σ

√

1 εn √H̄ when X > 0. The disagreement drift term to satisfy c2 η 2 L nGH̄ X ≤ 3ε , we require η ≤ √3c 2 LG X largest stepsize satisfying these conditions as well as the stepsize bound from Theorem 4.1 is ( ) √ 1 1 εn εnH̄ 1 √ , ,√ , η̂ = min 4c1 Lσ 2 4c2 LG X 8LHmax

where the terms involving σ 2 and X are understood to evaluate to +∞ when these quantities are zero. ∆ 0∆ To ensure the remaining term satisfies c0 ηH̄R ≤ 3ε , we must have R ≥ 3c . Substituting the εη̂ H̄ evaluated components of η̂ directly yields the explicit round boundary: ! √ ∆LHmax ∆Lσ 2 ∆LG X √ + R ≥ cR + nεH̄ εH̄ ε3/2 H̄ nH̄

for an appropriate absolute constant cR > 0. To convert this round complexity to wall-clock time complexity, we multiply the total elapsed rounds T = τH := Pn n τ −1 , we obtain the stated bound: R by the round duration, T = M τ + ζ. Using H̄ i=1

! √ ∆Lσ 2 ∆LG X ∆LHmax √ · τH + · τH + · τH . nε ε ε3/2 nH̄

Additional Experimental Details

We empirically evaluate sparse local SGD with communication–computation overlap mainly on binary classification problems from LIBSVM, and additionally on CIFAR-10 and Tiny ImageNet image classification with neural networks. The goal of the experimental section is to quantify the separate effects of local computation, sparse synchronization, and overlap under heterogeneous worker speeds. We compare five methods: • Sync SGD: no local drift, no sparsity, and no overlap. • FedAvg-Full: local drift with full model averaging. • Local Sparse: local drift with sparse model averaging. • Overlap overwrite: local drift, sparse model averaging, and communication–computation overlap. • Overlap delay-corrected: local drift, sparse model averaging, overlap, and corrected merging. The last two methods are our proposed overlap variants. The dense baselines, Sync SGD and FedAvg-Full, provide reference points for the cost of local drift and sparse communication, while Local Sparse isolates the additional effect of blocking sparse synchronization. 28

Setup. We use binary logistic regression with labels mapped to {−1, +1}. Given n workers, the training data are split into worker shards using a fixed seed when partitioning is enabled. All methods are run with the same initialization, data split, worker partition, and random seeds. For an example (x, y), the logistic loss is ℓ(w; x, y) = log 1 + exp −yx⊤ w

(86)

where w ∈ Rd denotes the model parameter. We consider the finite-sum objective F (w) =

n X mi

mi ,

(87)

i 1 X ℓ(w; xi,r , yi,r ) + R(w). Fi (w) = mi r=1

(88)

i=1

where

Fi (w),

n X

i=1

When studying the nonconvex setting, we use the coordinate-wise Geman–McClure regularizer R(w) = λ

d X

wj2 , 2 w + θ2 j=1 j

(89)

with λ and θ specified in each experiment. This regularizer introduces nonconvexity while preserving a simple logistic-regression structure, allowing us to evaluate the methods using both predictive and stationarity-based metrics. We also ran the same comparisons in this nonconvex regularized setting, but do not report those plots because they were qualitatively similar to the logistic-regression results and did not add separate conclusions. Features are standardized using training-set statistics when normalization is enabled. Metrics. We report training accuracy, validation accuracy, and the full training gradient norm ∥∇F (w)∥. Accuracy measures predictive performance, while the gradient norm measures optimization progress and is especially relevant in the nonconvex regularized setting. We plot performance as a function of communication rounds and cumulative logical time. Round-based plots measure progress per synchronization event, whereas logical-time plots capture the main motivation for overlap: reducing idle communication time by allowing workers to compute while sparse messages are in flight. For the CIFAR-10 and Tiny ImageNet experiments, we also plot against cumulative processed examples. This axis ignores simulated communication time and counts how many training examples have been consumed by the logical workers. It therefore serves as a proxy for the number of stochastic-gradient steps and, approximately, for the amount of local computation or floating-point work used by each method. These plots answer a different question from the logical-time plots: whether the overlap methods only look better because they can process more mini-batches during communication delays, or whether those extra mini-batch updates remain useful when methods are compared after consuming the same amount of data. For multi-seed experiments, curves show the mean across seeds, with shaded regions indicating variability across runs. Implementation. The experiments are implemented in a PyTorch-based logical-time simulation framework. The framework is not a real distributed system: workers, communication, and delays are simulated deterministically inside one process. This design lets us isolate algorithmic effects such as local computation, sparsity, communication delay, worker-speed heterogeneity, and communication–computation overlap without noise from hardware scheduling or networking. Each worker is represented by a separate PyTorch model copy, and the simulator explicitly tracks the round states xri , yir , and zir . In round r, worker i starts from xri , performs Ni local SGD steps to obtain yir , sends a sparse masked model vector, and, for the overlap methods, continues for Qi additional steps to obtain zir . The server averages the sparse messages on a shared random mask, and workers then merge the incoming sparse average either by overwrite or by delay correction. Logical time is controlled by integer worker step times τi . For overlap experiments, the simulator computes τ = lcm(τ1 , . . . , τn ), uses a local compute window of length M τ , and takes the communication delay ζ to be a multiple of τ . This gives per-worker step counts Ni = M τ /τi before communication and Qi = ζ/τi during communication, so faster workers naturally perform more local computation within the same logical-time window. The codebase separates timing, mask 29

sampling, compression, communication accounting, and merge rules, and includes engines for the proposed overlap methods, blocking Local Sparse, dense FedAvg-Full, and Sync SGD. Experiments are driven by YAML configurations and record optimization metrics, validation metrics, worker disagreement, processed examples, cumulative logical time, and logical communication cost in both coordinates and bits. Experimental organization. We first compare all five methods on LIBSVM binary classification tasks to quantify the cost of local drift, the cost of sparse synchronization, and the benefit of overlap. We then focus on the sparse methods, Local Sparse, Overlap overwrite, and Overlap delaycorrected, to isolate the impact of the two proposed overlap mechanisms. Finally, we perform ablations over the sparsity level, local computation budget, communication delay, and worker heterogeneity. We also include CIFAR-10 and Tiny ImageNet neural-network experiments to check that the same qualitative behavior appears beyond logistic regression. B.1

External experiments

We begin with a controlled sparse-communication experiment on a9a, comparing only Local Sparse, Overlap overwrite, and Overlap delay-corrected. This experiment isolates the effect of using the communication window for additional local computation, since all three methods use the same sparsity level and the same logical round duration. We use n = 4 workers with heterogeneous step times (τ1 , τ2 , τ3 , τ4 ) = (1, 2, 3, 6),

(90)

so that τ = lcm(τ1 , . . . , τn ) = 6. All methods are run for 20 communication rounds with learning rate η = 0.1, batch size 256, sparsity level p = 0.3, and no regularization, i.e., λ = 0. The training set is normalized using training-set statistics, and 10% of the training data is used for validation. For Local Sparse, each round consists of a compute window of length 18 followed by a communication window of length 6, during which workers block. For the two overlap methods, we set M = 3 and ζ = 6, giving the same round duration M τ + ζ = 3 · 6 + 6 = 24.

(91)

In this controlled comparison, the three sparse methods also communicate the same number of coordinates per round. Since they have the same round duration and the same per-round communication volume, comparing performance as a function of communication rounds is already sufficient: logical time and logical communication cost are common rescalings of the round index. We nevertheless include time- and communication-based plots as consistency checks. Thus, the pre-communication compute phase is identical across the three methods, while the overlap methods additionally exploit the communication window for local updates. Under these timings, the pre-communication local steps are 18 18 18 18 (N1 , N2 , N3 , N4 ) = , , , = (18, 9, 6, 3). 1 2 3 6 During communication, the overlap methods perform the additional steps 6 6 6 6 (Q1 , Q2 , Q3 , Q4 ) = , , , = (6, 3, 2, 1). 1 2 3 6

(92)

(93)

Therefore, any improvement of the overlap methods over Local Sparse comes from replacing idle communication time by useful local computation. The comparison between Overlap overwrite and Overlap delay-corrected then measures the benefit of correcting the merge rather than simply overwriting the synchronized coordinates. Across all reported metrics and plotting parametrizations considered in this experiment, we observe the same clear ordering: Overlap delay-corrected

outperforms

Overlap overwrite

outperforms

Local Sparse.

The separation is significant: for accuracy metrics the delay-corrected variant reaches higher values earlier, while for loss and gradient-norm metrics it decreases the objective and stationarity measure 30

faster. The same qualitative behavior has also been observed in many additional settings, including nonconvex regularized objectives, very heterogeneous worker-speed profiles, compute-dominated regimes in which local steps are expensive relative to communication, and communication-dominated regimes in which communication delay is the main bottleneck. This ordering has a simple interpretation. Local Sparse wastes the communication window by waiting, so it performs fewer useful local updates within the same logical round duration. Overlap overwrite uses this window for additional computation, which explains its consistent improvement over the blocking baseline, but it then discards part of this progress on the synchronized coordinates by overwriting them with a delayed sparse average. Overlap delay-corrected keeps the useful overlap drift and only corrects the disagreement induced by sparse synchronization, so it benefits from the extra computation without paying the full cost of stale overwriting. The empirical hierarchy therefore matches the mechanism predicted by the method: overlap is valuable, and delay correction is needed to fully exploit it. The accuracy plots in Figure 2 show this ordering on both training and validation accuracy, Figure 3 shows the same behavior for stationarity, and Figure 4 confirms that the loss comparison is unchanged when rounds are rescaled by logical time or communication cost.

(a) Training accuracy versus round.

(b) Training accuracy versus round, log scale.

(d) Validation accuracy versus round, log scale.

Figure 2: Accuracy comparison for the controlled sparse-overlap experiment on a9a. The delaycorrected overlap rule reaches higher accuracy earlier than overwrite, and both overlap rules improve over the blocking local-sparse baseline. 31

Figure 3: Training gradient norm for the controlled sparse-overlap experiment on a9a. The stationarity metric follows the same ordering as the accuracy plots: delay correction makes the fastest progress, followed by overwrite and then blocking local sparse averaging.

(a) Training loss versus logical time.

(b) Validation loss versus logical time.

(d) Validation loss versus communication cost.

Figure 4: Loss curves under equivalent resource parametrizations for the controlled sparse-overlap experiment. Since all three sparse methods use the same round duration and per-round communication volume, logical time and communication cost preserve the round-based ordering.

B.2

Merge-rule comparison across regimes

We next isolate the effect of the delayed merge rule by comparing only the two overlap variants, Overlap overwrite and Overlap delay-corrected, across three additional settings. Within each setting, the two methods use the same data split, sparsity level, communication schedule, worker speeds, and random seeds; the only difference is how the delayed sparse average is merged after the overlap phase. This comparison is designed to answer a direct question: when communicationcomputation overlap is used, should the incoming delayed average overwrite the synchronized coordinates, or should it be corrected to preserve the local progress made while communication was in flight? All three settings use a9a logistic regression with 20 rounds, learning rate η = 0.1, batch size 256, sparsity level p = 0.3, normalized features, and no regularization. The settings differ only in the 32

local-computation budget, communication delay, and worker-speed profile:

setting long compute, short delay short compute, long delay very heterogeneous speeds

M 8 2 2

ζ 6 24 20

(τ1 , τ2 , τ3 , τ4 ) (1, 2, 3, 6) (1, 2, 3, 6) (1, 2, 10, 20).

Across all three settings, delay correction gives lower training and validation loss than overwrite. The size of the advantage is not identical across regimes: in the long-compute, short-delay setting the gain is small but persistent; in the short-compute, long-delay setting it is large and visible throughout training; and under very heterogeneous worker speeds it is moderate. This variation is useful, because it shows that delay correction is not only helpful in an especially favorable configuration. Even when the two merge rules are close, the corrected rule consistently avoids the loss incurred by discarding overlap-phase progress on synchronized coordinates. The three regimes are shown in Figures 5 to 7; each figure places the training and validation losses side by side so that the text and plots can be read together.

(a) Training loss.

(b) Validation loss.

Figure 5: Long-compute, short-delay regime (M = 8, ζ = 6, worker times (1, 2, 3, 6)). Delay correction gives a small but persistent improvement over overwrite on both training and validation loss.

(a) Training loss.

(b) Validation loss.

Figure 6: Short-compute, long-delay regime (M = 2, ζ = 24, worker times (1, 2, 3, 6)). This is the regime with the largest gap: overwrite discards a substantial amount of overlap-phase progress, while delay correction preserves it. 33

(a) Training loss.

(b) Validation loss.

Figure 7: Very heterogeneous worker-speed regime (M = 2, ζ = 20, worker times (1, 2, 10, 20)). Delay correction keeps a moderate advantage over overwrite, showing that the corrected merge remains useful when worker speeds vary substantially.

B.3

Sparsity-level ablation

We now vary the sparsity level p, which controls the fraction of model coordinates communicated at each synchronization. The goal is to understand the communication-accuracy tradeoff induced by sparse parameter averaging. We use the same a9a logistic-regression setup with n = 4 workers, worker times (1, 2, 3, 6), 20 rounds, learning rate η = 0.1, batch size 256, normalized features, and no regularization. The local-computation and delay parameters are fixed to M = 4 and ζ = 6, while the sparsity level is varied over

p ∈ {0.001, 0.01, 0.1, 1.0}.

We report training loss as a function of cumulative logical total bits in Figure 8, separately for Local Sparse, Overlap overwrite, and Overlap delay-corrected. This ablation is best read horizontally, at a fixed communication budget. Reducing p shifts the curves left by orders of magnitude, because each communication round transmits fewer coordinates. At the same time, the shape of the loss curve changes only mildly: even very sparse communication continues to make steady progress. Thus, on this homogeneous-data a9a experiment, aggressive sparsification is highly communication-efficient. For example, the curves with p = 0.001 and p = 0.01 reach losses close to the denser settings while using far fewer total bits. There is still a tradeoff. Larger p communicates more of the model and therefore can slightly reduce the final loss after the same number of rounds, especially when comparing the endpoints of the curves. However, this improvement is expensive in communication: the p = 1.0 curve corresponds to dense parameter averaging and lies far to the right. The main conclusion is therefore that sparsity buys a large reduction in communication cost with only a modest optimization penalty in this setting. The conclusion is consistent across the three sparse methods, and the delay-corrected overlap rule remains at least as good as overwrite while preserving the same communication savings. 34

(a) Local Sparse.

(b) Overlap overwrite.

Figure 8: Sparsity-level ablation on a9a. We vary p ∈ {0.001, 0.01, 0.1, 1.0} with M = 4, ζ = 6, worker times (1, 2, 3, 6), and otherwise identical training settings. Smaller p dramatically reduces the cumulative number of communicated bits while preserving a similar loss trajectory, showing that sparse parameter averaging gives a strong communication-accuracy tradeoff in this homogeneous-data regime.

B.4

Ablation on the local computation budget

We next study the effect of the local computation budget M . We vary M ∈ {1, 4, 16, 64} and plot the training loss against cumulative logical time in Figure 9. All runs use a9a logistic regression with 20 rounds, learning rate η = 0.1, sparsity level p = 0.3, communication delay ζ = 6, batch size 256, normalized features, no regularization, and worker times (1, 2, 3, 6). All curves start from the same initial model at logical time zero. This initial point is not shown because the horizontal axis is logarithmic, and log(0) is undefined. We keep the raw time values rather than artificially shifting or transforming the data to display the initial point. Consequently, the first visible point for larger values of M appears later, since one communication round has a larger logical duration. 35

(a) Local Sparse.

(b) Overlap overwrite.

Figure 9: Ablation on the local computation budget. The blocking local-sparse baseline is sensitive to the local computation budget in early logical time, while the overlap methods are more stable. The delay-corrected rule gives the strongest collapse across the tested budgets.

For the blocking Local Sparse baseline, the early training-loss trajectory is sensitive to M . Small values of M synchronize more frequently and therefore spend a larger fraction of logical time in blocking communication. Larger values, especially M = 16 and M = 64, amortize this communication cost over more local computation and reach lower training loss faster in logical time. However, all tested values eventually approach a similar loss floor. The overlap methods show a weaker dependence on M . For Overlap overwrite, the curves for different values of M are much closer than for the blocking baseline. This suggests that once communication is overlapped with local computation, the local computation budget has a smaller effect on training-loss decrease per unit logical time. The remaining differences are mostly visible in the early phase, while the curves nearly coincide as training progresses. The strongest invariance is observed for Overlap delay-corrected. Across M ∈ {1, 4, 16, 64}, the loss curves almost collapse when plotted against cumulative logical time. This behavior is consistent with the delay-corrected merge preserving the useful local progress made during the communication window. In this regime, small values of M do not suffer the same logical-time penalty observed in the blocking baseline, while larger values of M do not introduce a visible training-loss penalty. Overall, this ablation suggests that the blocking sparse method is sensitive to M mainly through communication amortization. Communication–computation overlap reduces this sensitivity, and the delay-corrected rule gives the most stable training-loss behavior across local computation budgets. In all cases, the methods reach nearly the same final training-loss floor, so the main effect of M is on early progress in logical time rather than final training loss. This conclusion is for the datahomogeneous regime studied here. In strongly data-heterogeneous regimes, a large value of M can be harmful for all methods, because workers may take many consecutive steps toward different local objectives before their models are realigned. This client-drift effect is especially important when the data split is highly non-i.i.d., and it should be controlled separately when choosing the local computation budget. 36

B.5

Effect of communication delay

We next vary the communication delay ζ to test when overlap becomes most valuable. This experiment compares the same three sparse methods as in Section B.1: Local Sparse, Overlap overwrite, and Overlap delay-corrected. The point is different from the merge-rule-only comparison in Section B.2. Here we ask how the amount of time spent in communication changes the value of overlapping computation with communication, and how much of that value is lost if the delayed sparse average is merged by overwriting. We do not plot the case ζ = 0. When ζ = 0, communication is instantaneous, so the overlap phase has length zero and the overlap methods perform no extra local steps while messages are in flight. In that regime, overwrite and delay correction coincide with the blocking local-sparse update, and all three curves are identical under the same seed. The informative cases are therefore the positive-delay regimes shown in Figure 10, where the communication window creates both an opportunity for useful extra computation and a stale-merge effect that must be handled. For the moderate-delay case ζ = 12, the two overlap methods already improve over Local Sparse throughout most of training. The delay-corrected rule is consistently best, although its margin over overwrite is relatively small by the end of training. This suggests that when the communication window is long enough to make overlap useful but not dominant, the main gain comes from avoiding idle time, while delay correction provides an additional but more modest improvement. The larger-delay case ζ = 48 makes the mechanism much clearer. Local Sparse falls behind because it waits through a long communication window at every round, whereas both overlap methods turn that same time into additional local optimization. Among the overlap methods, delay correction gives the lowest training loss across the run and has a visibly larger advantage over overwrite than in the ζ = 12 case. This is consistent with the interpretation of the corrected merge: as ζ increases, workers make more progress during communication, so a naive overwrite discards more useful work on the synchronized coordinates. Delay correction preserves this overlap-phase progress and therefore benefits more strongly when communication delay is large.

(a) Moderate delay, ζ = 12.

(b) Large delay, ζ = 48.

Figure 10: Training loss versus cumulative logical time for the communication-delay ablation. The zero-delay case is omitted because all three methods coincide when ζ = 0. For positive delay, overlap improves over blocking local sparse averaging, and the delay-corrected merge is consistently strongest; the advantage is especially pronounced when the communication delay is large. A heterogeneous-data stress test. The preceding delay ablation should not be read as saying that longer communication delay is always beneficial. To illustrate the limitation, we also run an intentionally difficult non-i.i.d. experiment with a label-Dirichlet partition with concentration parameter α = 0.03. This creates strongly heterogeneous worker objectives. The run uses a9a logistic regression with 40 rounds, learning rate η = 0.3, sparsity level p = 0.01, M = 1, ζ = 96, and worker times (1, 2, 3, 6). This is an extreme communication-dominated regime: before communication, the workers take (N1 , N2 , N3 , N4 ) = (6, 3, 2, 1) local steps, while during the communication window the overlap methods take (Q1 , Q2 , Q3 , Q4 ) = (96, 48, 32, 16) additional local steps. 37

The result in Figure 11 is negative for overlap. Both overlap methods improve very quickly at the beginning, because the long communication window gives them many extra local updates. However, with such heterogeneous data these extra updates are not simply useful progress toward the global objective: each worker is also pulled strongly toward its own local objective. After this fast initial phase, the overlap curves plateau below Local Sparse; in particular, delay correction performs worst because it is designed to preserve the progress made during communication, and in this non-i.i.d. setting that progress can be biased toward local optima. The blocking local-sparse method is slower initially, but by waiting through communication it takes far fewer local steps between synchronizations and eventually reaches better train and validation accuracy. This experiment is outside the scope of our theory, which is developed for the data-homogeneous setting where all workers optimize the same objective. Its role is therefore mainly diagnostic. It shows that aggressive overlap can fail when communication is extremely slow, sparsity is very high, and the data partition is strongly heterogeneous. In such regimes, one would need additional mechanisms, such as smaller learning rates, less aggressive overlap, stronger synchronization, or an analysis that explicitly controls client drift under heterogeneous objectives.

(a) Training accuracy.

(b) Validation accuracy.

Figure 11: Negative stress test with strongly heterogeneous data and very slow communication. The data are partitioned by a label-Dirichlet split with α = 0.03, and the overlap methods use M = 1, ζ = 96, and p = 0.01. The overlap methods make rapid initial progress but then plateau below the blocking local-sparse baseline, indicating that too many local steps during communication can drive the methods toward poor local optima when worker objectives are highly heterogeneous. B.6

CIFAR-10 neural-network experiments

We also test the sparse overlap methods on CIFAR-10 image classification [Krizhevsky et al., 2009]. The goal is to check whether the behavior observed for logistic regression persists for a non-linear model trained with the same logical-time simulation framework. The model is a convolutional classifier trained with cross-entropy loss. We use the same three sparse methods as above and run all methods with matched initialization, data split, and random seed. The CIFAR-10 data are split into training, validation, and test sets, with validation held out from the training set. To focus on optimization and communication effects rather than client drift, all logical workers sample from the same training distribution. Training uses random crops with padding 4, random horizontal flips, weight decay 5 · 10−4 , dropout 0.1, batch size 256, evaluation batch size 512, and 10% validation data. The runs use four logical workers with step times (1, 2, 3, 6), learning rate 0.05, seed 11, target budget 400 epochs, and simulated 32-bit communicated values. We consider two communication regimes. The normal regime uses sparsity p = 0.25, localcomputation parameter M = 4, and communication delay ζ = 6. The communication-stress regime uses more aggressive sparsity and a longer delay, with p = 0.10, M = 2, and ζ = 24. The stress regime is designed to make communication a larger part of the logical-time budget. Figures 12 and 13 show the CIFAR-10 results. In both regimes, overlap improves training and validation accuracy as a function of logical time. The advantage is clearer in the communicationstress setting, where blocking communication is more expensive. The processed-example plots provide a complementary check. Because overlap workers keep taking mini-batch steps while sparse communication is in flight, an overlap method can process more examples by a fixed logical time than blocking Local Sparse. Plotting against cumulative processed examples removes this timing advantage and compares methods after they have consumed the same amount of training data, which 38

also roughly equalizes the number of local SGD steps and the amount of local compute. On this axis, the methods are much closer, especially in the normal regime. Importantly, the overlap variants do not lag behind or become unstable when compared this way. Thus the additional local steps taken during communication are not merely buying speed by spending extra computation in a harmful way; they appear to remain useful optimization steps. Together with the logical-time plots, this supports the same interpretation as in the logistic-regression experiments: overlap turns communication waiting time into productive local training, and the main gain is in elapsed logical time rather than in changing the amount of data needed to reach a given accuracy.

1.0

Local Sparse Overlap delay-correction Overlap overwrite

0.8

0.7

Val Accuracy

Train Accuracy

0.6 0.6

0.4

0.5 0.4 0.3 0.2

0.2

Local Sparse Overlap delay-correction Overlap overwrite

0.1 0

5000

10000

15000 20000 Cumulative Logical Time

25000

30000

35000

(a) Training accuracy versus logical time. 0.9

5000

10000

15000 20000 Cumulative Logical Time

25000

30000

35000

(b) Validation accuracy versus logical time.

Local Sparse Overlap delay-correction Overlap overwrite

Train Accuracy

0.8 0.7 0.6 0.5 0.4 106 Cumulative Processed Examples

107

Figure 12: CIFAR-10 convolutional-network experiment in the normal communication regime, with p = 0.25, M = 4, and ζ = 6. The overlap methods improve over blocking sparse averaging in logical time, while the processed-example curves show that this extra overlapped computation does not reduce accuracy at a fixed amount of data processed. 39

1.0

Local Sparse Overlap delay-correction Overlap overwrite

0.8

0.7

Val Accuracy

Train Accuracy

0.6 0.6

0.4

0.5 0.4 0.3 0.2

0.2

Local Sparse Overlap delay-correction Overlap overwrite

0.1 0

5000

10000

15000 20000 Cumulative Logical Time

25000

30000

35000

(a) Training accuracy versus logical time.

5000

10000

15000 20000 Cumulative Logical Time

25000

30000

35000

(b) Validation accuracy versus logical time.

Local Sparse Overlap delay-correction Overlap overwrite

0.9

Train Accuracy

0.8 0.7 0.6 0.5 0.4 0.3 105

106 Cumulative Processed Examples

107

Figure 13: CIFAR-10 convolutional-network experiment in the communication-stress regime, with p = 0.10, M = 2, and ζ = 24. The larger communication delay makes the logical-time benefit of overlap more pronounced, while the processed-example plot checks that the additional local steps remain useful when compared at the same number of consumed training examples. B.7

Tiny ImageNet neural-network experiments

We additionally evaluate the sparse overlap methods on Tiny ImageNet to test the same mechanisms on a larger image-classification problem. Tiny ImageNet contains 200 image classes at resolution 64 × 64. We use the official training split for optimization, hold out 10% of it for validation, and reserve the official validation split for final test evaluation. All images are normalized using ImageNet statistics. The model is a ResNet-18-style convolutional network trained from scratch [He et al., 2016]. Because the input images are 64 × 64, we replace the standard ImageNet stem by a 3 × 3 convolution with stride 1 and remove the initial max-pooling layer. We use GroupNorm instead of BatchNorm, since BatchNorm running statistics are not naturally synchronized by our sparse parameter-averaging implementation. The final classifier is replaced by a 200-class linear layer, and dropout is disabled. All methods use the same training recipe: 100 effective epochs, batch size 128, SGD with momentum 0.9, weight decay 5 · 10−4 , initial learning rate 0.1, and cosine decay to zero. Training uses random crops with padding 4 and random horizontal flips; evaluation uses deterministic 64 × 64 images without augmentation. As in the CIFAR-10 experiments, we use four logical workers with step times (1, 2, 3, 6) and a shared data partition, so each worker samples from the same training distribution. We compare Local Sparse, Overlap overwrite, and Overlap delay-corrected under two communication regimes. The normal regime uses p = 0.25, overlap parameters M = 4 and ζ = 6, and the corresponding blocking baseline uses compute window 24 and communication time 6. The communication-stress regime uses stronger sparsification and delay, with p = 0.10, overlap parameters M = 2 and ζ = 24, and the corresponding blocking baseline uses compute window 12 and communication time 24. Figures 14 and 15 show the results. The main conclusion is again that overlap is the dominant effect. In the normal regime, both overlap variants improve substantially over blocking sparse averaging in 40

logical time and in rounds, while the processed-example plot shows that the methods have similar sample efficiency once the extra computation performed during communication is accounted for. In the communication-stress regime, the logical-time gap becomes much larger: blocking Local Sparse spends so much time waiting that it reaches much lower training and validation accuracy within the same time budget. The processed-example plot is more surprising. This axis removes the wall-clock advantage of overlap, but it does not equalize the number of sparse merge operations. In the stress regime, the overlap methods perform the same pre-communication steps as Local Sparse, and then two more such blocks of local computation during communication. Thus, for a comparable number of processed examples, Local Sparse has applied roughly three times as many sparse averaging operations. We did not expect Local Sparse to be worse on this axis, and we do not yet fully understand the effect. One plausible explanation is that, with only p = 0.10 communicated coordinates and a deep network, very frequent partial-coordinate merges can perturb the optimization trajectory, while the overlap methods implicitly use a larger local-computation window between sparse synchronizations. Unlike the logistic-regression merge-rule ablations, Tiny ImageNet shows little separation between Overlap overwrite and Overlap delay-corrected. The two overlap curves are nearly indistinguishable in the stress regime, and overwrite is slightly ahead in some normal-regime curves. Thus, these experiments should be read primarily as evidence for the robustness of communication–computation overlap on a more demanding neural-network task, rather than as evidence that one sparse merge rule dominates on every architecture and training recipe.

Local Sparse Overlap delay-correction Overlap overwrite

0.8

0.6

0.6 Train Accuracy

Train Accuracy

Local Sparse Overlap delay-correction Overlap overwrite

0.8

0.4

0.2

0.0

0.0 0

200

400

600 Round

800

1000

1200

10000

15000 20000 Cumulative Logical Time

25000

30000

35000

(b) Training accuracy versus logical time.

(a) Training accuracy versus round. Local Sparse Overlap delay-correction Overlap overwrite

0.5

5000

0.8

Local Sparse Overlap delay-correction Overlap overwrite

0.7

0.4

Train Accuracy

Val Accuracy

0.6 0.3 0.2

0.5 0.4 0.3 0.2

0.1

0.1 0.0 0

5000

10000

15000 20000 Cumulative Logical Time

25000

30000

106 Cumulative Processed Examples

35000

107

(d) Training accuracy versus processed examples.

Figure 14: Tiny ImageNet experiment in the normal communication regime, with p = 0.25, M = 4, and ζ = 6. Both overlap variants improve over blocking sparse averaging in logical time and in rounds. When plotted against processed examples, the curves are much closer, indicating that the main benefit is the use of communication time for additional useful computation. 41

0.8

0.6

0.5

0.4 0.3

0.2

0.1

0.1 0.0

0.0 0

200

400

Round

600

800

1000

0.8

Local Sparse Overlap delay-correction Overlap overwrite

0.5

5000

10000

15000 20000 Cumulative Logical Time

25000

30000

35000

(b) Training accuracy versus logical time.

(a) Training accuracy versus round. 0.7

0.4

Local Sparse Overlap delay-correction Overlap overwrite

0.6 Train Accuracy

Val Accuracy

Local Sparse Overlap delay-correction Overlap overwrite

0.7

Train Accuracy

0.8

Local Sparse Overlap delay-correction Overlap overwrite

0.7

0.3 0.2

0.5 0.4 0.3 0.2

0.1

0.1 0.0

0.0 0

5000

10000

15000 20000 Cumulative Logical Time

25000

30000

35000

106 Cumulative Processed Examples

107

(d) Training accuracy versus processed examples.

Figure 15: Tiny ImageNet experiment in the communication-stress regime, with p = 0.10, M = 2, and ζ = 24. The longer communication delay makes the advantage of overlap much larger: both overlap variants substantially outperform blocking local sparse averaging in logical time and also remain ahead when compared by processed examples.

Record · ID 216798 · SHA-256 7c28ff66ab1a9131
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.