Birch SGD: A Tree Graph Framework for Local and Asynchronous SGD Methods
Authors: Alexander Tyurin
Danil Sivtsov
Venue: ICLR 2026 Poster (2026)
Keywords: asynchronous sgd
optimal time complexity
nonconvex optimization
parallel methods
stochastic optimization
unified framework
Primary area: optimization

Abstract: We propose a new unifying framework, Birch SGD, for analyzing and designing distributed SGD methods. The central idea is to represent each method as a weighted directed tree, referred to as a computation tree. Leveraging this representation, we introduce a general theoretical result that reduces convergence analysis to studying the geometry of these trees. This perspective yields a purely graph-based interpretation of optimization dynamics, offering a new and intuitive foundation for method development. Using Birch SGD, we design eight new methods and analyze them alongside previously known ones, with at least six of the new methods shown to have optimal computational time complexity. Our research leads to two key insights: (i) all methods share the same iteration rate of $\mathcal{O}\left(\frac{(R + 1) L \Delta}{\varepsilon} + \frac{\sigma^2 L \Delta}{\varepsilon^2}\right)$, where $R$ the maximum ``tree distance'' along the main branch of a tree; and (ii) different methods exhibit different trade-offs---for example, some update iterates more frequently, improving practical performance, while others are more communication-efficient or focus on other aspects. Birch SGD serves as a unifying framework for navigating these trade-offs. We believe these results provide a unified foundation for understanding, analyzing, and designing efficient asynchronous and parallel optimization methods.

Published as a conference paper at ICLR 2026
BIRCH SGD: A TREE GRAPH FRAMEWORK FOR LOCAL AND ASYNCHRONOUS SGD METHODS
Alexander Tyurin AXXX, Moscow, Russia Applied AI Institute, Moscow, Russia
Danil Sivtsov
AXXX, Moscow, Russia
Applied Al Institute, Moscow, Russia
ABSTRACT
We propose a new unifying framework, Birch SGD, for analyzing and designing dis- tributed SGD methods. The central idea to represent each method as weighted directed tree, referred to as a computation free. Leveraging this representation, we introduce general theoretical result that reduces convergence analysis to studying the geometry of these trees. This perspective yields purely graph-based based inter- pretation of optimization dynamics, offering new and intuitive foundation for method development. Using Birch SGD, we design eight new methods and analyze them alongside previously known ones, with at least six of the new methods shown to have optimal computational time complexity. Our research leads to two key in- sights: (i) all methods share the same "iteration rate" of O (R++))L4EE + o² LA e²) where R the maximum "tree distance" along the main branch of tree; and (ii) dif- ferent methods exhibit different trade-offs- for example, some update iterates more frequently, improving practical performance. while others are more communication- efficient or focus on other aspects, Birch SGD serves as a unifying framework for navigating these trade-offs. We believe these results provide unified foundation for understanding, analyzing, and designing efficient asynchronous and parallel optimization methods.
INTRODUCTION
Optimization is central to machine learning (MI), data science (DS), and federated learning (FL. (Konečný et al., 2016; Bottou et al., 2018; Kairouz et al., 2021). In these domains, stochastic optimization techniques such as stochastic gradient descent (SGD) (Robbins & Monro, 1951) and its adaptive variants (Adam, AdamW, etc) (Kingma & Ba, 2015; Loshchilov & Hutter, 2019) have become the standard approach for tackling large-scale problems (Schmidt et al., 2021). Due to the rising computational demands of modern functions, the theoretical foundation of distributed algorithms supporting a large number workers (e.g., CPUs, GPUs, servers) important (Mayer & Jacobsen, 2020; Kairouz et al., 2021; Douillard et al., 2023).
We consider distributed optimization problems with smooth nonconvex optimization functions:
min f()) xERd
In nonconvex settings, the goal is to find an etaationnayy point, meaning we want to find a random vector ह such that E [| f [+] < E (Nemirovskij & Yudin, 1983; Murty & Kabadi, 1985). The function f Rdd + R satisfies the following standard assumptions:
Assumption 1.1. f is differentiable and I-smooth: [V v S L| vll Vx, y Rd..
Assumption 1.2. There exist f E IR such that f(x) 2 f for all x E Rd.
We focus on problems where workers are limited to computing stochastic gradients. Each worker has access to unbiased stochastic gradients, denoted by fz(=: whose variance is bounded by access the same data, which is practical
r². In the context of ML, this implies that all workers when training large language and computer vision models. In such scenarios, privacy is not a critical concern, and devices can sample data from the Internet shared datasets (Goodfellow et al., 2016).
Assumption 1.3, For all x E Rd, stochastic gradients V fx; E) are unbiased and --vvriincc- bounded, i.e., (x; = V ( and Re[] ([r;; E) V [2] d², where σ² > 0.

---

Published as a conference paper at ICLR 2026
1.1 RELATED WORK
One worker and optimal oracle complexity. With single worker, the most standard optimization
method is the Vanilla SGD algorithm, which updates the iterate as w = w 7 > f (w* :nn" where {n²}} are i..d., wº E I2 is a starting point, is step size, and A == f(w") - f Arjevani et al. (2022); Carmon al. (2020) showed that Vanilla SGD is optimal in terms of oracle complexity, which is given by ④ (LA/c + o² LA/(2 for finding an e-stationary point.
Multiple workers and optimal time complexity. Consider now that we have n workers computing stochastic gradients asynchronously and in parallel. In this setup, there are numerous ways to construct distributed SGD method. The most well-known celebrated and recent approaches include Synchronized SGD (Minibatch SGD), Local SGD (Zinkevich et al., 2010; Stich, 2019), Asynchronous SGD (Recht et al., 2011), 1), Picky SGD (Cohen et al., 2021), Rennala SGD (Tyurin & Richtárik, 2023), and Ringmaster ASGD (Maranjyan et al., 2025). The multi-worker setup is rich and versatile, offering numerous ways to design distributed SGD methods.
One may naturally ask which method offers the best theoretical performance. In distributed settings, the standard oracle complexity becomes less informative, as workers compute stochastic gradients in parallel with varying speeds. A more suitable comparison uses the h:-fixed compulation model (Mishchenko et al., 2022), where each worker i needs at most h4 seconds to compute a gradient. In this model, Mishchenko et al. (2022); Koloskova et al. (2022) showed that Asynchronous SGD outperforms Synchronized SGD. Its time complexity is further improved by Rennala SGD (Tyurin & Richtárík, 2023) and Ringmaster ASGD (Maranjyan et al., 2025), both optimal under this and the more general universal computation model (Tyurin, 2025) (see Section A). However, as we will discuss in more detail later, other factors come into play, such as communication complexity, support for A1 Reduce, peak bandwidth, and model update frequency.
These developments raise several important questions. Rennala SGD and Ringmaster ASGD are known to be optimal, yet differ in design and structure, each with distinct advantages and trade-offs. This leads to our central questions: Are there other optimal methods? Can we develop a unified framework that encompasses all distributed SGD methods and offers theoretical guidance? ? What fundamental properties make these methods optimal? And, given different system constraints, which method should one choose?
1.2 CONTRIBUTIONS
New framework: Birch SGD (Section 2). We propose Birch SGD, unifying framework that captures a wide range of distributed SGD methods, The key idea is that SGD methods can be represented using weighted directed trees, which we refer to as computation trees (see Figure 1). We develop a new theoretical result, Theorem 2.4, that reduces the analysis of SGD methods to analyzing of the structure of these computation trees. The proofs become purely geometric and topological in nature, offering geometric intuition for the design of new methods. Moreover, this geometric viewpoint Icads to tighter time complexity guarantees even for Local SGD (FedAvg) approaches (McMahan et al., 2017), as we illustrate in Section H.
Eight new methods (Table and Section 3). Using Birch SGD, we identify eight new methods in addition to those already known. For the first time, we prove that at least six of these newly discovered methods are computationally optimal, matching the lower bound (Tyurin & Richtárik, 2023). We compare all methods across several dimensions, including computational and communi- cation complexity, A Reduce compatibility, peak bandwidth, and model update frequency. Our improvements: i) newly developed Async-Local SGD and Async-Batch SGD provably improve the communication complexity of Ringmaster ASGD while preserving asynchronicity; ii) we introduce Cycle SGD, which provably reduces peak bandwidth compared to all existing methods; iii) we propose a key modification to the family of local methods and design Local SGD and for the first time in the literature, achieve the optimal time complexities within this family and improve upon the classical approach (see Section H); iv) for multi-cluster settings, we introduce Local-Async SGD and Nested Local-Async SGD, incorporating a carefully designed synchronization mechanism that guarantees optimality in computational time complexity; v) we develop a flexible meta-algorithm, Meta Local SGD, which supports arbitrary synchronization strategies, while incorporating a "Hard
SGD that,
Asynchronous SGD with a key modification; see Alg.7.
2

---

Published as a conference paper at ICLR 2026
Algorithm 1 Birch SGD framework
Input: starting point w Rd, step size 7 2 0
Initialize the set of computed points: V = [
(and the set of edges = for k = 0, 1,2..... do
Choose any point Whase V from which to compute new point
Choose any point Wgradd V at which to compute stochastic gradient
Compute the new point:: w Whase -VV (Wgradi
17 ~ Dş
Add w to the set of computed points V
(and add the edge with weight (Wase: = +++ (ugad 7)) to the set edges E)
end for
February Aquze, Igor Grabar. 1904.
Figure 1: A possible computation tree G' for SGD method after four steps and beyond.
Sync" mechanism to guarantee convergence rates and to temper overly chaotic synchronization. As byproduct, we prove that frequent model updates of fully asynchronous methods can lead to faster convergence and improve optimal Rennala SGD.
Insights and Guidelines (Section 4). We observe that there no silver bullet-each method has its own advantages and disadvantages. Some methods update the iterates more frequently, making them more appealing practice, while others prioritize communication efficiency, support A1 AllReduce, or focus on different aspects. Through our new framework, we uncover insights that provide deeper intuition and simpler perspective on asynchronous, local, and parallel optimization methods.
Birch SGD: A GENERAL VIEW OF SGD METHODS
We begin our work by observing that various SGD methods, including Vanilla SGD, Asynchronous SGD, Local SGD, among others, can be constructed in the manner described in Algorithm
Let us explain it. Initially, any SGD method starts at some point w E IR4, computes stochastic gradient w and then finds a new point w = wd (w which added to the set V of computed points. In the next step, there are four options for choosing the subsequent point 2 w² = w² y f for i E {0, 1}. This process continues indefinitely, and the number of possible choices, and hence methods, grows exponentially (see example in Figure 1).
Note that any instance of Algorithm 1, after any steps, can represented by a weighted directed tree G= (V, E), called computation tree, where V is the set of computed points and E is the set of edges with weights given by the stochastic gradients used to compute the new points. Our main idea now is to take any computation for the corresponding SGD method. Intuitively, the structure of the tree, e.g., number of branches, length branches. the tree distance between Wgrad and Whase in Alg. 1 when we calculate new point should be related to the convergence speed of the method.
G and analyze its structure provide convergence guarantees
Example. Consider Local SGD from Figure 4. There, we illustrate two global steps of the method with 2 workers. In the first round, they compute M1 and M2 = 2 local steps (first figure in Figure 4). During these steps, worker first calculates V f==" 1/1 0.0g finds 21 00.1 rº V 7/1 0.0g then calculates V ff(2111 ( and .,2 d f[= 0,1, .m) 1. Similar steps are performed by worker Then, via parameter-server or AllReduce, LocalSGD aggregates the stochastic gradients and performs the global step d (VVf(=
fz :7) 0.1 )+ ff(= U.0) + ff(22 2 M2 0.1))
to obtain the global point x4 from which the second global steps will start. The step of
3

---

Published as a conference paper at ICLR 2026
finding x* is equivalent the steps x² 20 VVf(= :71 m7) x² =x' -V 0,1, 0.1) x :7) x²² fV 0.1 ; ?7 ") and æ² = x f(22 (2221 1/22 This how construct the second figure in Figure 4, which is geometric representation of the first global step. Then, the workers compute Mi 1 and M2 = 3 local steps, accordingly, and synchronize again (third figure in Figure 4) find
x². from which the third global steps will start.
2.1 MAIN THEORETICAL RESULT ON CONVERGENCE RATES
Before we state our main theorem, we need to introduce sequences and definitions that characterize the structure of computation trees G.
Definition 2.1 (Main Branch and Auxiliary Sequence). For a given computation tree G, we call a sequence {2*) Te2:0 main branch if it forms a path in G starting the initial node w = x². That is, for each A 2 O, the node w is a direct successor of 2 in G. By the construction of tree G, if {=*) 1220 is a main branch, then for each k 2 0 there exists a unique pair (=*, g*), where 2² E V and 5* ~ Dg, such that x++1 = x² - - <V (*). The sequence ((= (1)", {=)], which generates the main branch {z J620. is called an auxiliary sequence.
Although there may be several possible choices and any of them can be chosen in general, the selection of the main branch is typically unique and straightforward in all reasonable SGD methods, as it forms the backbone of the tree".
Let us consider an example. In Figure 1, we can take a main branch {=*)
J420 as fol- lows: x² = w x w², x² = w x
w x² w", x6 10. Accordingly. the
auxiliary sequence is given by
(20 54)
(wo n7)) (z) (t) (w: 1t)
(w2 n7) 5
(w (w".n")
(w", 177). See Figure
Figure 2: Visualization.
Intuitively, the convergence rate should depend on the distance between x² and sh When these points are close (e.g., x² )*), the stochastic gradient is computed near the update point, typically yielding descent on average. In contrast, if they are far apart, the gradient at 2* may poorly approximate the local behavior of f at x² making the update direction irrelevant. Thus, it is crucial to define a suitable distance metric that is both easy to evaluate for any point pair and directly related to the convergence speed of the SGD method. We propose the following:
Definition 2.2. For all y, E V, the tree distance dist(y, z) between and z is the maximum number of edges to the common closest ancestor of y and z.
As an example, consider Figure 2, where dist(w w²) max max(4, 4, because the common ancestor is w the number of edges from w" to w is 4, and the number of edges from w to w is It left to define the representation of a point E V.
Definition 2.3. For all E V, the representation repr(y) is the multiset of stochastic gradients applied n get y. In other words, there exist {(m), ,x*), )..,..., (m², {²)} =: repr(y) for some p > 0 such that y = " Ej (f(m", k²).
We define the representation of points understand how all points are related. An important relation that we need is that repr(z) S repr(y), which essentially means that all stochastic gra- dients used to compute x are also used to compute y. For instance, in Figure 2, repr(w") (w²,"²)) ,/2), which allows to track (w"", ,,7²), (wo n/2), (w² :7?), (w=2, )/ and repr(w: (wpr(w") [(w", ,7"), (w²
the path from from the starting point w to wD and w and show that repr(w") C repr(w").
'A fitting analogy is the Git distributed version control system, which also has central main branch.
4

---

Published as a conference paper at ICLR 2026
V/(an)
J
Figure 3: A general representation of the step x*+1 = x ['= : gl) that shows how x and z are
related.
Theorem 2.4 (Main Theorem). Let Assumptions 1.1, 1.2, and 1.3 hold. Consider any SGD method represented by computation tree = (V, E). Let {x* T120 be main branch of and {(z", ehh) )=20 be the corresponding auxiliary sequence (see Def. 2.1) that satisfy the following
conditions:
Condition For all k: 2 &h statistically independent of {x++11 2t41, ;-))==
Condition The representation of t contained within that of x², i.e., repr(2*) repr(a*)
for all k > 0. Equivalently, all stochastic gradients used in the computation of zk are also utilized in calculating z².
Condition 3: There exists constant R E [0, oo] such that dist(æ ,²)) S R for all k 0.
Then 2 K k= [[*)(= S s for all K 2 4(R+1)LA
LL with step size 7
min 2L 2RL 10- where A = =(x*)= - f
Assumptions 1.1, 1.2, and 1.3 are well-known and standard in the analysis of stochastic optimization methods (Lan, 2020; Arjevani et al., 2022). Let explain the conditions of the theorem.
Condition 1. The first condition condition requires that g* is independent of [xx++1 [ (
which is a weak assumption. In Vanilla SGD, where A.++ = x² - >>Vs(>"; g*), ), it is standard to assume that each ş is an independent sample. Our condition generalizes this other SGD variants. It guarantees that the stochastic gradient V f-; <*) is not used in computing x² or zt. Notably, this remains true even in methods like Local SGD, where gradients may be reused.
The second condition is also weak in any reasonable and effective SGD method. Figure illustrates that there exists p 2 0 such that
Condition 2.
* 0 Σ (((())))
Σ Vf(w;(),,t 2 ()(()))) Σ ()()))))
(WSE)SS*
Amp
where S the set of points and random variables used to compute z starting from x..
Computing each stochastic gradient is time-consuming, so it is desirable to utilize as many computed gradients as possible, including {V [W: () Once (=* c*) has been used to compute k++ the first condition prevents further use (V (w:: (w.(() in subsequent iterations because ** depends & for all (w, E 5t Thus, it is reasonable to assume that if SGD method employs the stochastic gradient ; to compute x++1, then it has already used the gradients [V ()) (w. in previous iterations fully leverage all available information. In other words,
all stochastic gradients used in the computation of z² are also utilized in calculating A This is equivalent to the second condition repr(2*) S repr(z*).
Condition 3.
This condition is arguably the most important in Theorem 2.4 because it determines the In fact, iteration rate O ((++))LA/e + LL///) depends
iteration rate of the main branch
on R supazo dist(a" 2²).
Vanilla SGD (Section E. For instance, consider the simplest method, the classical stochastic gradient descent (Vanilla SGD) method: *+1 w
where wo is starting point and are {n²} are i..d. random variables. Taking = = z² = " and gl = nn for all 2 0. Clearly, all conditions of Theorem 2.4 are satisfied: ş* is independent of {(xi+1, repr(x*) = repr(=*) for all l 2 0, and R = We get the iteration rate O (LA/e oZL0/e) The corresponding tree is in Figure 15.
-
(,0fH1,2+1,, gi41 (5+1.g))) 1-1
5

---

Published as a conference paper at ICLR 2026
Conversely, if SGD method is overly non-conservative, leading a large tree distance R. between x² and 2 the iteration rate correspondingly increases. The further the maximum tree distance R between x² and 2 the more iterations required to achieve the desired accuracy
Proof novelties. In Section D.I, we outline the key novelties, challenges, and the intuition guiding our choice of conditions. Although our proof in Section D.2 is compact- which view as strength rather than a limitation-its unifies a broad class of methods and provides new insights. Notably, right the beginning, we introduce distinct approach to handling the staleness term || - which naturally arises from the update xf+1 x > I (= <+) in asynchronous and local methods. This treatment fundamentally differs from prior work, as it analyzes staleness through geometric graph reasoning. Moreover, using our framework, we later present our version of Local SGD, which yields tighter guarantees compared to the classical Local SGD (see Sections and H), further validating both our framework and proof technique.
EXISTING AND NEW ALGORITHMS: SUMMARY AND COMPARISON
In this section, we consider examples of distributed methods. We will show that all of them can be represented by computation trees and analyzed using Theorem 2.4. The detailed analysis of each method is provided in Section E.
Rennala SGD (Section E.2). Consider Rennala SGD, which can be written
B w w y Σ vf(w";n
(2)
where workers collaboratively calculate the batch of size B (see Alg, 4). This method pro- duces a computation tree constructed as follows: x1 x Vzx : ....,,"' I B
fx (2BB1)))) ..... where B is a batch size (see Figure 16) and {c*) are i...d. from Dę. Notice that the computation tree is equivalent (2) because " w/, 222 w² etc. Here, all conditions of Theorem 2.4 are satisfied for the main branch {a*} with the auxiliary sequence {(2 {*)} such that 20 =
y fz g =B = xB -VV fz B. B.)) (.)......2 222 2
B = rº, 22B-1 B.B. etc, and _ = 0.0 cB-1 0 c 11. etc. However, unlike Vanilla SGD, R = B- because dist(x", ; = 0, dist( 21) = 1 I,..., dist(r B-1 BB-1)=
=B
B 1, dist(r 2B 0, etc. Thus, the iteration rate is O (BLA/E + l
Ringmaster ASGD (Section E.4). This an Asynchronous SGD method with the update rule
wh+1 " V :nn--")
(3)
where 8 is delay such that 8t < 1, where G 2 is hyperparameter (see Alg. 7). We take x² " for all l O. Thus, the corresponding auxiliary sequence is defined by 2 R-* w and k* = n 55 for all k 2 0. Constructing the computation tree (Figure 17), we can show that the conditions of Theorem 2.4 hold with R = max+2u 8² < G and the iteration rate is O (GLA/S + LA/??))
Previously, we presented Rennala SGD and Ringmaster ASGD that can be analyzed using Theorem 2.4. This raises the question: Which method is most effective, and how should one choose the appropriate one? In the following sections, we discuss different factors one should consider when selecting method, and present new algorithms. The discussion here is summarized in Table 1. Before we begin, it is important to note that the iteration complexity in Theorem 2.4 does not reflect the true wall-clock performance. It serves as intermediate result used to derive the time complexities presented below.
Computational complexity. One way to compare the methods complexity under the he-fixed computation model (see Sec. 1.1, A, and F). With proper choice of the corresponding parameters, i.c., and Ringmaster ASGD are optimal in terms of wall-clock time with the time complexity O (mmin 10/1n En 1/h.)- (LA/E o2 r' provided that communication times are negli- gible. In the worst-case scenario, the "very bad function" (Arjevani et al., 2022), all these methods perform equally well. Next, we discuss the strengths and weaknesses of the methods that are not captured by the h;- fixed computation model.
analyze their time
max(1, [== both Rennala SGD

---

Published as a conference paper at ICLR 2026
Table 1: Summary of distributed optimization methods from Sections and E. In this table, we compare methods across different metrics. A v/ indicates favorable property in the corresponding metric. As can be seen, each method has its own advantages and disadvantages. Therefore, for any practical setup, one should choose the most suitable method based on the specific requirements. For all methods, we use the parameters from the theorems of Section when deriving the metrics.
Method (Sec. I)
Optimal Computational
Complexity (Sec. F)
Communicatinn Com- plesity with Equal Times
Optimal Total Complexity (Sec. I)
AlllReduce
Updote" Frequeccy
Randwidth
Prak
Rernale (Alg. 4)
(Tyurin & Richsirik, 2023)
x
t
Ringmastor ASGD (Ale.
(Maranjyan 2025)
111
Local SGD (Alg. (aew)"
/
/
x
/
11
Cycle SGD (Alg. (new)
11
=
Asyno LocaliBatch SGD (Alp 9 and Sec. (.7) (new)
+4
x
11
(Nested) Local-Adyn: SGD (Aig. 12 and 14) (new)
t1
Dusl-Phossss SKDD (Alg. 18) (new)
+ +
x 11
Mata Local sap!!! (Alg. 16) (new)
methed support Recluee? Asynchroncus SGD-Bite methods de support their gredy updste Cyde synchronizes only subset
workers; this, cannot say dedinitively. We also cunset say dellmitively case Local Aoyne SGD because local asynchronms steps cunsot implemented with
Redue, while the global steps can be. This is an abstract methodd where all metrles (Computaional Complexity, Communication Complexny, etc) depend on the chosen struggy.
Similar to Al13educe duce, here we also can not say detinitell since Local Aoyne SGD and Nested Local Asyno SGD are specially designed multi cluser learning methods. This is slightly less fornal metrie that indicates how oftes sigorithm upditess in leratolmedet Renale 5CD tsks the workers to compute stochastic gradient at the updates
point, Soction
less frequealy.
Fingmaster ASGO updates itenutes inmediatlly. other methods someediess
the
the Ronnala SGD, Ringmaster ASSD, Local SGD, and Asyne Local S3D methods, warkers can sun communication simuliaecussl:: thus, their peak bandwidth
in (in) when n S // In the Cydle SGU method, the wurkers communicate in cincaler manner, so the pesk bandwidth is O when n S " "/r, which is smaller. recognize that Local SGD stopping critesion 2 M. in Alg. and the atalysis in Sec. E.3, F, Gi which leads the optintal contunatiinal time complexities with propar cheice
known
literaraes, what
our version novel the better time complexit compared classical vession (Sec.
We report the temm wir. communication time under the (h, rifftedd conputation model from Section Cl.
2. Number of model updates. At the same time, comparing (3) and (2) reveals that Rennala SGD computes B stochastic gradients at the same point, while Ringmaster ASGD both computes and "explores" more by immediately updating the model as in (3). This feature makes Ringmaster ASGD more practically appealing. In fact, this intuition can be formalized using a simple two-dimensional strongly convex quadratic function f : R + R such that f(z y) = p=z² /22 Ly² /2 for all x, E R. For this function, we prove that Rennala SGD requires θ (0"/on x h x 1//x)) seconds to achieve an e-solution under the fi-fixed computation model with h; = h for all E [m2]. while Ringmaster ASGD needs Ô (h x 4/n), which is a² ee/en seconds less (see formal result in Section J). This is the first result showing that Ringmaster ASGD/ASynchronoos SGD can be strongly better than Rennala SGD.
3. Communication complexity. Communication delays are major bottleneck in real-world dis- tributed systems. Thus, minimizing communication and synchronization overhead is crucial. Ring- master ASGD is the least efficient in this regard, requiring frequent communication and lacking AllReduce support due to its asynchronous design. In a simple model where sending one stochas- tic gradient takes 7 seconds and all workers have identical speed h; h, the time complexity of Ringmaster ASGD is Ω (T (LA/E + of LLLA/ne)) + h (LA/E + #LD/ne") In contrast, Rennala SGD achieves O (TLA/E+ + h (LA/= + + LLL4/==)) (see Sec. G), which is better when 7 and o²/2 are large.
This is the point where we asked ourselves if it is possible to design method that has the optimal computational time complexity of Rennala SGD and updates the iterates more frequently than it. It turns out this method well-known and is called Local SGD:
Local SGD (Section E.3). We consider the classical Local SGD strategy, where each worker i E [n] performs M, local steps, after which the server aggregates the results (see Alg. 5). Unlike most previous approaches, however, the number of local steps M, may vary across workers. Moreover, the server waits for a specific condition before aggregating: Σ M, = B. This strategy is adaptive to fluctuations in the number of local steps performed by individual workers, as the server ensures the total number of steps across all workers reaches the target sum Σi= M; = B, where B is hyperparameter. An example of the computation tree is shown in Figure 4. In Section E.3,
7

---

Published as a conference paper at ICLR 2026
Pyge- 1
Sync. via server or Al Allueduce
RESENNN
WISH 1
After two global steps
Wilrdd
Figure 4: An evolution of Local SGD computation tree with B = 4 and 2 workers, each performing local steps over global steps. In the first round, they compute M1 2 and M2 = 2 local steps (first figure), after which they synchronize (second figure). In the second round. they compute M1 = 1 local steps and synchronize again (third figure). Note that the maximum distances
and M2
:7) 1 to x33 and [=22"" :7/2 :72)2) to x", are dist(x., 21 0.1) and dist(x 22 22.2). when applying V [=)"""
equal to B - 2i=1 M, = 3. Notice that each stochastic gradient is used 2 times in the tree.
establish the iteration rate of Local SGD as O (BLA/s + oLL//2). This result follows directly from Theorem 2.4 via simple geometric argument. In fact, looking at Figure 4 reveals that all the conditions of Theorem 2.4 are satisfied. The only minor difficulty is to show that suP=20 dist(2 ,2 s B 1, which is guaranteed by the condition > M, B.
What is novel in our version of Local SGD is that it achieves better theoretical guarantees within the family of Local SGD approaches (see Section H). Moreover, our stopping condition and the choice of B together ensure its optimality under the h;-fixed computation model (see Theorem F.6).
Async-Local SGD (Section E.6). Another idea leverage the practical benefits of Ringmaster ASGD, while at the same time reducing the communication overhead, is to use Ringmaster ASGD with local steps. The idea is run M local steps on each worker instead of immediately sending the computed stochastic gradients to the server in an asynchronous fashion (See Figure 5). We formalize this algorithm and prove the iteration rate in Section E.6. Moreover, in Sections F and G. suggest an optimal choice of parameters that leads to optimal computational complexity and reduced communication complexity, which better than that of Ringmaster ASGD, We get as similar result with new method, Async-Batch SGD (Section E.7).
Qual-Process SGD (Section E. We took a step further and developed new local method inspired by Local SGD and Async-Local SGD. It is the first local method to achieve the optimal time complexity in the distributed setting, where workers have varying computation and communication times (see Section I). However, unlike Local SGD, it is not A1 www.eeeeuuieeeeeeeeeeee
Peak bandwidth. Another critical factor is the peak bandwidth. The number of workers the parameter-servee or the A.1 Reduce operation can synchronize may be limited when the number of workers huge. Notice that the worst-case peak bandwidth of Rennala SGD, Ringmaster ASGD, Local SGD, and Async-Local SGD is θ (n).
Cycle SGD (Section E.5). To mitigate this issue, we propose a new method called Cycle SGD. Similar to Local SGD, each worker performs local steps. However, once the workers finish computing the initial stochastic gradients (V v7?) only the first group of s workers sends their gradients to the server, where is hyperparameter. The server then aggregates these gradients and performs the update wt = " - Σi= f= v?)). Meanwhile, the first s workers begin computing their local steps starting from w while the remaining workers continue their current local computations. Next, the second group of workers sends their locally computed vectors, and this process continues in circular manner. A computation tree presented in Figure 18. The peak bandwidth of Cycle SGD is which is smaller than θ (n) when o o²/c
O (s) with min mmax /x 1,,
Optimization with clusters. Consider a setup with many clusters of workers, where intra-cluster communication (e.g., InfiniBand) is fast and inter-cluster communication (e.g., Ethernet) is slow.
8

---

Published as a conference paper at ICLR 2026
3.3
1.2
of
FIe of"
x²
1.2
Figure 5: An example of the computation tree for Async-Local SGD with M = 2. In this example, the first worker is significantly faster: before the second worker completes its first set of local steps. x² + 2 + 2.2 the first worker already completes two rounds of local updates and sends the cor- responding stochastic gradients, (V](>"; m/ m/,"), (= "))")) and (VI(x²; m/ 200), S "n :
Local-Async SGD (Section E.8) We run Asynchronous SGD within each cluster and synchronize clusters after fixed number of local steps. This setup is feasible due fast intra-cluster links, while slower inter-cluster links necessitate infrequent synchronization. In Section E.8, we formalize this method, Local-Async SGD, and establish its iteration rate. Section F proves it achieves optimal computational time complexity. A key novelty lies in the synchronization mechanism (see Alg. 12).
Nested Local-Async SGD (Section E.9) Our framework extends to a two-level hierarchy: within each cluster, servers with 4-8 GPUs run Asynchronous SGD locally, synchronize at the server level, and then synchronize across clusters. Analyzing such setup using classical optimization tools would be highly challenging. In contrast, our framework enables a straightforward analysis through geometric graph reasoning.
6. Flexible synchronization and Meta Local SGD (Section E.1 We noticed that in all previous methods, the workers are synchronized in a predefined manner or rule. We want to add more flexibility the synchronization process. Our idea is that the server (or the workers themselves, in a decentralized setup) can select any subset of workers based on any strategy (e.g., randomly or according to current communication speeds), gather their computed stochastic gradients, update the global model, and ask these workers to continue performing local steps from the new point. However, such "anarchic synchronization" can result in computation tree with a large R the selected strategy is not chosen carefully. To ensure that R is bounded, in our meta-algorithm (Algorithm 16), we track the current distances } } to the head of the main branch and the local steps (M. performed by each worker. Then, by tracking the value d; - Σ M, for all i E [n] and comparing it to parameter B, we compulsorily synchronize (Hard Sync) all workers for which d: + Σ M, = B. This way, we can ensure that R is bounded by B, and the iteration rate of this method is O (BLA/s o² L./e).
4 INSIGHTS AND GUIDELINES
All proposed methods share the same iteration rate of O ((R+1)LA/E + o2L4/E²) where R is con- trolled by a method-specific hyperparameter and, at the same time, R is the largest tree distance between = and z²a For Rennala SGD, R B - 1, where denotes the batch size; for Ringmaster ASGD, R = B 2--1, where B is the delay threshold; for Local SGD, R B-1, 1, where B corresponds to the number of local steps; for Cycle SGD, = " where s is the group size, etc. In all these methods, R can be controlled, and to achieve the best possible computational and communication guarantees, one should always choose R = @ (o²/c) (see Sections and F). We believe this is a fundamental principle underlying all parallel optimization methods, and it should be considered guiding rule when developing new algorithms. This choice is also theoretically justified: by taking R = θ (o²2/8 /a), the iteration rate does not change asymptotically: O ((R+1)LA/= + o² LL/e²) O (LA/E /L/// Larger values of allow the methods to be more fharalle-frriendly... For instance, a large It enables Ringmaster ASGD consider stochastic gradients with larger delays, while large Rt in Local SGD allows the method to run more local steps. However, taking R > <²/= results in a worse iteration rate, suggesting that the corresponding method operates in overly "anarchic" asynchronous regime, which may lead to performance degradation. Geometrically, the theory suggests that, to achieve good performance, the tree distance between * and & in Figure should not exceed o² o²/e.

---

Published as a conference paper at ICLR 2026
Notice that there is no single "best" method in Table I, which we believe is another fundamental law. Each method has its own strengths and weaknesses, and one should develop or choose the most appropriate method for the specific task. This process becomes easier with the help of our new framework, Birch SGD, and insights.
While primary focus is training large-scale language and vision models, where the i.i.d. assumption is usually appropriate, we acknowledge that non-i.id. scenarios are also important and should be investigated in future work, where may be necessary add additional assumptions such as first-order and second-order similarity of the functions (Arjevani & Shamir, 2015; Mishchenko et al., 2022). Moreover, it would be interesting to extend our framework methods with preconditioning (Kingma & Ba, 2015) and non- Non-Euclidean geometry (Jordan et al.).
We hope our observations will support the future development and analysis of asynchronous optimiza- tion methods. Building on these insights, we designed at least eight new methods using our proposed Birch SGD framework and the main result, Theorem 2.4. By reducing the analysis and design of these methods to computation trees, our entire development becomes purely graph-geometrical, offering new and simpler view on asynchronous optimization methods.
5 SUMMARY OF EXPERIMENTAL RESULTS
In Section C, provide detailed comparison of methods on logistic regression, image clas- sification with ResNet18 (He et al., 2016), and next-token prediction with GPT2 (Radford al., 2019). When communication times are negligible (Fig. 6). as expected from Table and the previous discussion, Ringmaster ASGD and Async-Local SGD converge faster on the lo- gistic regression problem. However, when communication times are large (Fig. 7), Ringmas- ter ASGD becomes less practical due to its frequent updates. Synchronized SGD exhibits the worst performance across all setups. Rennala SGD and Local SGD are more stable, while Asyno- Local SGD performs well due to its effective balance between frequent updates and local steps.
202 COTTLLES SAN odee your semoid dett wit
Aariada LED EESOEEEEE ALSO genche
4.13
Figure 6: Computation times h, 1 or 10 ran-
Figure 7: Computation times h4 10, commu- nication times т; 100.
domly, communication times 7; = O.
ACKNOWLEDGEMENTS
The work supported by the grant for research centers in the field of Al provided by the Ministry of Economic Development the Russian Federation in accordance with the agreement 10000CC11922PPFF000 and the agreement N:139-0--2025-033
REFERENCES
Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. Advances Neural Information Processing Systems, 28, 2015.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, pp. 1-50, 2022.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223-111, 2018.
10

---

Published as a conference paper at ICLR 2026
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):71-120, 2020.
Alon Cohen, Amit Daniely, Yoel Drori, Tomer Koren, and Mariano Schain. Asynchronous stochastic optimization robust to arbitrary delays. Advances in Neural Information Processing Systems, 34: 9024-9035, 2021.
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.08100 2023.
Mathieu Even, Anastasia Koloskova, and Laurent Massoulié. Asynchronous SGD on graphs: unified framework for asynchronous decentralized and federated optimization. In International Conference on Artificial Intelligence and Statistics, pp. 64-72. PMLR, 2024.
Hamid Reza Feyzmahdavian, Arda Aytekin, and Mikael Johansson. An asynchronous mini-batch algorithm for regularized stochastic optimization. IEEE Transactions on Automatic Control, 61 (12):3740-377 3754, 2016.
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT Press, 2016.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. unified theory SGD: Variance reduc- tion, sampling, quantization and coordinate descent. In International Conference on Artificial Intelligence and Statistics, pp. 680-690. PMIR, 2020.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local sgd: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics, pp. 3556-3564. PMLR, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition (CVPR), pp. 770-778, 2016.
Yan Huang, Ying Sun, Zehan Zhu, Changzhi Yan, and Jinming Xu. Tackling data heterogeneity: A new unified framework for decentralized sgd with sample-induced topology. arXiv preprint arXiv:2207.03730, 2022.
Rustem Islamov, Mher Safaryan, and Dan Alistarh. AsGrad: A sharp unified analysis of asynchronous- SGD algorithms. In International Conference on Artificial Intelligence and Statistics, pp. 657. PMLR, 2024.
Keller Jordan, Yuchen Jin, Vlado Boza, You Jiacheng, Franz Cecista, Laker Newhouse, and Jeremy Bernstein. Muon: An optimizer for hidden layers in neural networks, 2024. URL https://elllrjorrdnn. github. io/posts/muon, 6.
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. Ad- vances and open problems in federated learning. Foundations and Trends@ in Machine Learning. 14(1-2):1-210, 2021.
Ahmed Khaled, Othmane Sebbouh, Nicolas Loizou, Robert M Gower, and Peter Richtárik. Unified analysis of stochastic gradient methods for composite convex and smooth optimization. arXiv preprint arXiv:2006. 1573, 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian U. Stich. A unified theory of decentralized SGD with changing topology and local updates. Proceedings of the 37th International Conference Machine Learning, 2020.

---

Published as a conference paper at ICLR 2026
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.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492, 2016.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. Technical report, University of Toronto, Toronto, 2009.
Guanghui Lan. First-order and stochastic optimization methods for machine learning. Springer. 2020.
Yann LeCun, Corinna Cortes, and Burges. MNIST handwritten digit database. ATT Labs [Online]. Available: http://aaw.eccn..o/oee//////////
2, 2010.
Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. Advances in Neural Information Processing Systems, 28, 2015.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization, In International Confer- on Learning Representations, 2019.
Ruichen Luo, Sebastian U Stich, Samuel Horváth, and Martin Takáč. Revisiting LocalSGD and SCAFFOLD: Improved rates and missing analysis. In International Conference on Artificial Intelligence and Statistics, 2025.
Artavazd Maranjyan, Alexander Tyurin, and Peter Richtárik. Ringmaster ASGD: The first asyn- chronous SGD with optimal time complexity. arXiv preprint arXiv:2501.16168 2025.
Norm Matloff. Introduction to discrete-event simulation and the simpy language. Davis, CA. Dept of Computer Science. University of California at Davis. Retrieved on August, 2(2009): 2008.
Ruben Mayer and Hans-Arno Jacobsen. Scalable deep learning on distributed infrastructures: Challenges, techniques, and tools. ACM Computing Surveys (CSUR), 53(1):1-37, 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas Communication-efficinnn learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. arXiv preprint arXiv:1609.0777 160900884, 2016.
Konstantin Mishchenko, Francis Bach, Mathieu Even, and Blake Woodworth. Asynchronous SGD beats minibatch SGD under arbitrary delays. Advances in Neural Information Processing Systems, 2022.
Katta G Murty and Santosh N Kabadi. Some NP-complete problems in quadratic and nonlinear programming. Technical report, 1985.
Arkadij Semenovië Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 188)99 2019.
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.
Herbert Robbins and Sutton Monro. stochastic approximation method. The Annals of Mathematical Statistics, pp. 400-407, 1951.
12

---

Published as a conference paper at ICLR 2026
Robin M Schmidt, Frank Schneider, and Philipp Hennig. Descending through crowded valley- benchmarking deep learning optimizers. In International Conference on Machine Learning, pP- 9367-9376. PMLR, 2021.
Suvrit Sra, Adams Wei Yu, Mu Li, and Alex Smola. Adadelay: Delay adaptive distributed stochastic optimization. In Artificial Intelligence and Statistics, pp. 957-965. PMLR, 2016.
Sebastian U Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations, 2019.
Sebastian Stich and Sai Pranceth Karimireddy. The error-feedback framework: SGD with delayed gradients. Journal of Machine Learning Research, 21(237):1-36, 2020.
Alexander Tyurin. Tight time complexities in parallel stochastic optimization with arbitrary computa- tion dynamics. In International Conference on Learning Representations, 2025.
Alexander Tyurin and Peter Richtárik. Optimal time complexities of parallel stochastic optimization methods under fixed computation model. Advances Neurul Information Processing Systems, 36, 2023.
Alexander Tyurin and Peter Richtárik. On the optimal time complexities in decentralized stochastic asynchronous optimization. Advances in Neural Information Processing Systems, 37, 2024.
Alexander Tyurin, Marta Pozzi, Ivan Ilin, and Peter Richtárik. Shadowheart SGD: Distributed asynchronous SGD with optimal time complexity under arbitrary computation and communication heterogeneity. Advances in Neural Information Processing Systems, 37, 2024.
Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of communication--fficieell sgd algorithms. arXiv preprint vrXiv:1808.07577 2018
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and Vincent Poor. Tackling the objective
inconsistency problem in heterogeneous federated optimization. Advances in neural information processing systems, 33:761 1-7623, 2020.
Xuyang Wu, Sindri Magnusson, Hamid Reza Feyzmahdavian, and Mikael Johansson. Delay-adaptive step-sizes for asynchronous learning. In International Conference on Machine Learning, 2022.
Martin Zinkevich, Markus Weimer, Lihong Li, and Alex Smola. Parallelized stochastic gradient descent. Advances in Neural Information Processing Systems, 23, 2010.
13

---

Published as a conference paper at ICLR 2026
CONTENTS
1
Introduction
1.1
Related work
1.2
Contributions
2
Birch SGD: A General View of SGD Methods
2.1
Main theoretical result on convergence rates
3 Existing and New Algorithms: Summary and Comparison
Insights and Guidelines
5 Summary of experimental results
10
Additional Discussion
16
A.1 Discussion of the computational time complexities
16
A.2 More related work
16
A.3 Relation other frameworks
17
Notations
17
Experiments
17
C.1 Setup
17
C,2 Experiments with logistic regression
18
C.3 Experiments with ResNet18 and image classification
21
C.4 Experiments with GPT2 and token prediction
22
C.5 Experiments with Cycle SGD and peak bandwidth
22
C.6 Sensitivity the choice of B Rennala SGD
23
C.7 Parameters of the experiments
24
D Proof of Theorem 2.4
26
D.I Proof technique and reasons for choosing the conditions
26
D.2 Full proof
26
E Detailed Description of Algorithms and Iteration Rates
29
E.1 Vanilla SGD
................................
29
E.2
Rennala SGD
................................
30
E.3
Local SGD
32
E,4
Ringmaster ASGD
34
E.5
Cycle SGD
35
E,6
Async-Local SGD
37
14

---

Published as a conference paper at ICLR 2026
E.7
Async-Batch SGD
38
E.8 Local-Async SGD
39
E.9
Nested Loynl-Async SGD
41
E,10
Meta Local SGD
43
E.11
Dual-Process SGD
46
Computational Time Complexities of Algorithms under -ixed Computation Model
48
E1 Rennala SGD
48
F2 Ringmaster ASGD
49
E3
Local SGD
50
E44
Local-Async SGD
50
E55
Nested Asyne SGD
51
F6
Async-Local SGD
F7
Cycle SGD
53
F88
Dual-Process SGD
Total Time Complexities of Algorithms under (h, -ixed Computation Model
55
G.1
Rennala SGD
55
G.2 Local SGD
55
G.3
Cycle SGD
56
G.4 Async-Local SGD
56
G.5 Ringmaster ASGD
57
H Comparison Between Our Local SGD and the Canonical Local SGD
57
I Total Time Complexities of Algorithms under (h,, Ty -Fixed Computation Model
58
L.1 Dual-Process SGD
59
J Performance of Rennala SGD and Ringmaster ASGD Quadratic Function
61
15

---

Published as a conference paper at ICLR 2026
A ADDITIONAL DISCUSSION
A. DISCUSSION OF THE COMPUTATIONAL TIME COMPLEXITIES
In this section, we extend our discussion about the computational time complexities of the methods discussed in the main part of the paper.
To compare parallel and asynchronous methods, Mishchenko (2022) proposed using the hy-fixed computation model. The idea is to assume that worker requires at most h2 seconds to calculate one stochastic gradient for all E [n] = .I,...: n < hn). The authors considered Synchronized SGD, an iterative process defined as w** wh E ff(="; n,"",, where each worker calculates one stochastic gradient, synchronize, and a parameter server aggregates them to update the iterate". Using the h; h--fixed computation model, can be easily shown that Synchronized SGD converges after
(without loss of generality, hn S h2 S
LA (
o² LA
max hy x iE
nE²
seconds, because the method waits for the slowest worker, whose time is max4e(x) h; hn-
Algorithm 2 Asynchronous SGD
Input: point w E Rd, stepsizes NY& 2 0 Workers start computing stochastic gradients at w for & 0,..... do Gradient V ; :--6" arrives from worker
Update: w++1 w yk V v ; :np-8"
k-8"
Worker i begins calculating w+1
end for
Mishchenko et (2022); Koloskova et al. (2022) provided new analyses of Asynchronous SGD (see Algorithm 2) and Cohen et al. (2021) developed Picky SGD to show that this time complexity can be improved to
(
(L
LA
ne²
where the dependence on (h,) is harmonic instead of being based on the maximum. It turns that this complexity can be further improved to
))
min mEjm
1
LA
o² LLLA me²
(5)
which achieved by the Rennala SGD method (Tyurin Richtárik, 2023). Moreover, Tyurin Richtárik (2023) proved matching lower bound demonstrating that both this complexity and Rennala (2025) developed a new optimal Ringmaster ASGD method, which is essentially Asynchronous SGD with a key modification. Additionally, under the universal computation model, Tyurin (2025); Maranjyan et al. (2025) showed that both Rennala SGD and Ringmaster ASGD remain optimal when computation times arbitrary, time-varying, and random.
SGD are optimal. Recently, Maranjyan
A.2 MORE RELATED WORK
Our focus is on the homogeneous setting, where all workers have access to the same data distribution or dataset. The heterogeneous data setting is equally important, especially in federated learning (FL) (Konečný et al., 2016) due to privacy constraints. In this context, many other methods have been
AAternattvely, there no physical parameter server, and all workers perform an Allreduce. 'Note that min g(m) g(n) for any function g N R
me(r)
16

---

Published as a conference paper at ICLR 2026
proposed, including Asynchronous SGD (Mishchenko al., 2022: Koloskova al., 2022), Asgrad (Islamov et al., 2024), PIAG (Wu et al., 2022), and Malenia SGD (Tyurin & Richtárik, 2023). Notably, Tyurin & Richtárik (2023); Tyurin (2025) showed that Malenia SGD is optimal under both the fixed and universal computation models, without requiring assumptions of bounded gradients or gradients dissimilarity.
In the homogeneous setting, numerous other works have studied asynchronous SGD methods, in- cluding (Lian al., 2015; Feyzmahdavian al., 2016; Stich & Karimireddy, 2020; Sra et al., 2016). However, these methods typically require the assumption that the delays in the indices of stochastic gradients are bounded (on average in (Sra et al.. 2016)). As result, their theoretical guarantees in terms of computational time complexity are weaker than those in (Cohen et al., 2021: Koloskova al., 2022; Mishehenko et al., 2022; Tyurin & Richtárik, 2023; Maranjyan al., 2025), which do not rely on such assumptions.
A.3 RELATION TO OTHER FRAMEWORKS
There were several previous approaches to unify SGD methods. Gorbunov et al. (2021) proposed using parametric assumption unify the analysis of local methods, Wang al. (2020) unified FedAvg- like methods, Wang & Joshi (2018) 8) proposed Cooperative SGD to analyze different synchronization mechanisms through mixing matrices, Huang et al. (2022) analyzed general sample-wise Push-Pull framework in the heterogeneous setting using two-level augmented graphs, and Khaled et al. (2020); Gorbunov al. (2020) analyzed SGD methods with variance-reduction and compression techniques. These approaches are related to, but not directly comparable with ours, and, to the best of our knowledge, our approach is new and orthogonal.
Another interesting work that analyzes SGD methods is (Even et al., 2024). Their work and ours both use graphs; however, we use graphs in completely different, orthogonal, and unrelated contexts. In their case, nodes represent computers (GPUs, CPUs, servers), and edges represent communication links. In our case, nodes represent points of an algorithm, (directed) edges indicate how one point is calculated from another, and the graphs evolve with every iteration. Similarly, Huang et al. (2022) also use a graph abstraction but with a different meaning for nodes and edges: in their case, nodes correspond to devices and iterates of data samples, edges represent both communication and computation links, and the number of nodes is fixed from the beginning since every node corresponds one sample or worker. These different and orthogonal approaches. Another important difference is that they compare methods using iteration complexities, whereas we use time complexities in Table which is a more robust and suitable metric for asynchronous and parallel methods.
B NOTATIONS
N = (1,2,...) ||^||| the output of the standard Euclidean norm for all x E Rd; (x. y)
Σ J,9i is the standard dot product; y O(J) exist C > such that g(z) < C' f(=) for all
E Z:g = {(f)= exist such that g(z) 2 C. x f(z) for = E 2; = O(J) : = O() and
(()); +() the same as g 2(f) but up to logarithmic factors; V b == max(a, 6}.
C EXPERIMENTS
C.1 SETUP
The experiments were prepared in Python. The distributed environment was simulated with the Simpy Python library (Matloff, 2008). There are two hardware setups:
CPU Setup: Intel(R) Xeon(R) Gold 6348 CPU 2.60GHz 52 cores (for logistic regression experiments)
GPU Setup: 2 x Nvidia A100 80 Gb, CPU: Intel(R) Xeon(R) Platinum 8358 CPU @ 2.60GHz 128 cores (for ResNet18 18 and GPT2 experiments)
17

---

Published as a conference paper at ICLR 2026
The distributed environment is simulated with the help of Simpy. To compare the methods, consider different computation and communication scenarios by taking different computation times {ht} and communication times { of the workers.
For each task, we perform a grid search to identify the best parameters and report the top results across all runs of each algorithm. The individual grid search parameters drawn from set of values specified in Section C.7. We plot the convergence rates against the elapsed time.
We evaluate the convergence speeds of all algorithms in four regimes:
Classical: h; = 10 and T; for all E [n:] All workers have the same computation times, and the communication times ignored.
Slow Communications: h; = 10 and = 100 for all i E [n]. The communication takes time.
Heterogeneous Computations: h2 random choice( {1, 10}) and т; for all i [nx] All workers have the different computation times randomly sampled from the set 10).
Heterogeneous Communications: h; 10 and т; random (hoice([1,100)) for all i e [n]]. All workers have the different communication times randomly sampled from the set (1,10) 10).
This setup allows to observe how different algorithms perform across various regimes and to compare their convergence behaviors under differing computational and communication conditions.
C.2 EXPERIMENTS WITH LOGISTIC REGRESSION
We begin our experiments with one the simplest ML problems-logiste regression on the MNIST dataset LeCun et al. (2010). In this setting, we evaluate three different numbers of workers: n {16, 64, 256). We use the standard linear model with the logistic loss.
Starting with = 16 workers, we perform grid search over the parameters specified in Table 2 across all four regimes. The corresponding results are shown Figure (Figure 8a), all algorithms perform similarly. However, Rennala SGD and Local SGD underperform slightly due to the inability to interrupt an already initiated local step, resulting in occasional update losses. In the slow communications setup (Figure 8b), Rennala SGD, Local SGD, and Async-Loca SGD perform better, as they aggregate local steps and reduce communication overhead. contrast, Synchronized SGD and Ringmaster ASGD perform poorly due to excessive communication. In both the heterogeneous computations (Figure 8c) and heterogeneous communications (Figure 8d) regimes, Async-Local SGD and Ringmaster ASGD achieve the fastest performance. Synchronized SGD, as expected, is the slowest because it is not robust to heterogeneous computations and communications.
the classical setup
For 64 (grid search parameters in Table results shown in Figure and n 256 (grid search parameters in Table 4, results shown in Figure 10), we observe behavior similar to the 16 case across all four regimes.
18

---

Published as a conference paper at ICLR 2026
50 yoe EINOS 9e134
fervace VESTECTEES BHOTE
5
g
1000
(a) Classical regime: h, = 10, =
(b) Slow Communications regime: h4 10, 7, = 100
Rrand Lou bwrl2
0x.3%
Pryal Lecd UrD petl Entt bahld lea!
4x
(c) Heterogeneous Computations regime: random choice((1,
Heterogeneous Communications regime: 10. random choice([1,100)
Figure 8: Comparison of different optimization algorithms across various distributed computing regimes with n = 16. Each plot shows the convergence behavior in terms of loss versus simulated wall-clock time.
1.10
VORAETEES CLICK prosttO 211004 Syeshre 5S5
SED GOLLS 21
froe Sed ped
2200
(a) Classical regime: h = 10, = 0
(b) Slow Communications regime: h4 10, T. 100
Memocice ynu s15o0 b-10004 Mot
2000
3000
22000
(c) Heterogeneons Computations regime: lt: random choice((1,
(d) Heterogeneows Communications regime: lo: 10.
random choice([1,100)
Figure 9: Comparison of different optimization a algorithms across various distributed computing regimes with n 64. Each plot shows the convergence behavior in terms loss versus simulated wall-clock time.
19

---

Published as a conference paper at ICLR 2026
SCD SETRESS BHOTA
4410
EATTAR SED VORUEERILD BOIAAN
AeroLAce CRIVAL Mi-1
Auy LA BITICOA
Onadl Sacond
806
1800
(a) Classical regime: hr 10, 0
(b) Slow Communications regime: 1a 10,
100
Lock Seo ROVILS 20120 prove B0
Auc tou pe kustle
(c) Heterogeneous Computations regime: random (1,
Heterogeneous Communications regime: 10. random choice((1,100)
Figure 10: Comparison of different optimization algorithms across various distributed computing regimes with n = 256. Each plot shows the convergence behavior terms of loss versus simulated wall-clock time.
20

---

Published as a conference paper at ICLR 2026
C.3 EXPERIMENTS WITH RESNET18 AND IMAGE CLASSIFICATION
We test the algorithms on the CIFARIO (Krizhevsky et al., 2009) image recognition task with the R (He al., 2016) deep neural network. For ResNet18, we similarly report the best convergence results from grid search over the parameters listed in Table 5, using a setup with n = workers, Results for all algorithms across the four regimes are presented in Figure 11.
The conclusions largely mirror those from the logistic regression experiments, with few additional observations. In the classical setup (Figure Ia), Ringmaster ASGD outperforms all other methods. We believe that this is due to the frequent updates of the method. In the slow communications regime (Figure 11b), the trends are consistent with those observed in the MNIST experiments: Ringmaster ASGD becomes slower, while methods that are less communication-intensii achieve better performance. the heterogeneous communications (Figure I regime, Async-Local SGD has the best performance due to the good balance of frequent model updates and local steps.
wath SCD wil SVEWS BAST Loua wHOLRD
Ringnace FASS velokia 2-1t Syrchron Setryra LE0
10300
(b) Slow Communications regime: h, 10, T4
(a) Classical regime: hi 10,
100
lice Bitr
crmmome MG20 Weth 8e13 stediiaal p.L.
20m
4000
(c) Heterogeneous Computations regime: h4
(d) Heterogeneous Communications regime:
random choice [1, 10)).
h 10, random_ 1andom_choico((1110)) 100))
Figure 11: ResNet18 8 experiments with = 8
21

---

Published as a conference paper at ICLR 2026
C.4 EXPERIMENTS WITH GPT2 AND TOKEN PREDICTION
We also evaluate the algorithms on the Wikitext-2 (Merity et al., 2016) next token prediction task with GPT2 (Radford et al., 2019). For GPT2, evaluate all four regimes using a setup with workers. To achieve faster and more robust convergence, we use the AdamW normalization strategy only in these experiments with GPT2. The resulting convergence curves are shown in Figure 12. Once again, the results are similar to those of the previous experiments. Due to hardware limitations, a narrower grid search range is used; therefore, possible that convergence could be further improved with a more extensive search.
Bolt Far pr AND SEMBOSTT
MEDONORRRRE Regraater 1655 w.8.0MMOII Bod2 Sunchroraee DOMMA0R
1x17
*x10
107
2002
bwordd
200
3905
(a) Classical regime: h 10,
(b) Slow Communications regime: 14
10,
100
653 co
1AT SED INSRRSOIEES AAUL
Aigranee Ne yn aonniiiiii Syetrwneed yell 000l0800125
SPH DHMcOvdd
1500
20000
2500
300
4x12
(c) Heterogeneous Computations regime:
h;
Heterogeneous Communications regime: h4 10, random random_choicee((1. 100))
random (L) T
Figure 12: GPT-2 experiments with 8
C.5 EXPERIMENTS WITH Cycle SGD AND PEAK BANDWIDTH
Laca BUTELES 6-224
Riypmatee AOOD yod (313 Bozt
wh-
2005 2000 2000
1006 1537
3000
70%
3006
Figure 13: Comparison of methods in the setup, where the communication time depends on the number of synchronized workers. It takes h, 10 seconds to compute stochastic gradient, and the communication time is 1.5 x l seconds, where l the number of synchronized workers.
In Figure 13, present the comparison of Cycle SGD with other methods to verify the advantageous theoretical property of Cycle SGD. For this particular regime, when the computational times are the same, all methods except Cycle SGD require all the 64 workers to synchronize at the same time, leading to high peak bandwidth. At the same time, Cycle SGD synchronizes only 8 workers and
'Inttead of the SGD step u k+1 w ~ where g is a descent direction, use the Adam W strategy with g².
22

---

Published as a conference paper at ICLR 2026
reduces the communication time and the total time complexity, which observe in Figure 13 with logistic regression on the MNIST dataset.
C.6 SENSITIVITY TO THE CHOICE OF B IN Rennala SGD
ferrik 6620 femk mit exh12
100
Sha beconce
Figure 14: Slow Communications regime: h2 10, T, 100
In this section, we aim to understand the sensitivity of the choice of the value B in Rennala SGD. From the proof of Theorem E.2, we know that R == supx20 dist(x 2² O(B). By increasing B O(R), can examine whether the method starts slow down. This slowdown is expected due to the discussion in Section 4. In Figure 14, we present our results on logistic regression problem on the MNIST dataset and 100 workers, where we see that if take B too large, the method slows down accordingly.
23

---

Published as a conference paper at ICLR 2026
C.7 PARAMETERS OF THE EXPERIMENTS
Table 2: Experimental configuration for logistic regression on MNIST with n 16 workers.
Parameter
Value
Batch size
Optimizer
SGD
Number of workers
16
Algorithm-specifie configurations:
Synchronized SGD
7 range: [2 [2-6,24)
Rennala SGD
range: [2 15,
[2-15, 3- set: (128, 256, 512, 1024)
Local SGD
range: [2-15,2-1 2-33
set: (128, 256, 512, 1024]
Ringmaster ASGD
Y range: [2-15 2 set: (128, 256, 512, 1024)
Async-Loccl SGD
7 range: [2-10, 2-
B set: (64, 128, 256, 512, 1024)
M set: [1, 2, 4, 8)
Table 3: Experimental configuration for logistic regression on MNIST with = 64 workers.
Parameter
Value
Batch size
Optimizer
SGD
Number of workers
64
Algorith configurations:
Synchronized SGD
? range: [2 22-2,21
Rennala SGD
7 range: [2-15, 2-33 set: (1024, 2048, 4096)
Local SGD
? range: [2-15, 2-33 set: (1024, 2048, 4096)
Ringmaster ASGD
range: [2-15, 2-]
set: [5i2, 1024, 2048, 4096]
Async-Local SGD
range: [2-10, 21)
set: (64, 128, 256, 512, 1024, 4096)
M set: [1, 2, 4, 8)
24

---

Published as a conference paper at ICLR 2026
Table 4: Experimental configuration for logistic regression on MNIST with = 256 workers.
Parameter
Value
Batch size
Optimizer
SGD
Number of workers
256
Algorithm-specific configurations:
Synchronized SGD
range: [2-5.20 24]
Rennala SGD
range: [2-15 2--3
B set: (1024, 2048, 4096, 8192, 16384)
Local SGD
range: [2-15, 2-- 2-
B set: (1024, 2048, 4096, 8192, 16384)
Ringmaster ASGD
range: [2-15, 22-1
set: (512, 1024, 2048, 4096, 8192)
Async-Local SGD
range: [2 10 _2"]
set: (128, 256, 512, 1024, 4096, 8192)
M set: {1, 2, 4, 8)
Table 5: Experimental configuration for ResNet18 with n workers.
Table 6: Experimental configuration for GPT-2 with n workers.
Parameter
Value
Parameter
Value
Batch size
16
Batch size
32
Optimizer
SGD 8
Optimizer
AdamW
Number of workers
Number of workers
8
Algorithm-specifii configurations:
Algorithm-specific configurations:
Synchronized SGD
range: [2 3-6,5 2-
Synchronized SGD
7 range: [2 11, 10]
Rennala SGD
range: 2 2-3
Rennala SGD
range: [2-11, 2 10]
set: (16, 32, 64)
B set: {16, 32, 64)
Local SGD
range: 2- 2-3
Local SGD
range: [2-11 2 2
set: {16, 32, 64)
B set: { [16, 32, 64)
Ringmaster ASGD
range: 2-33
Ringmaster ASGD
y range: [2-11 2 2-10]
B set: (16, 32, 64)
B set: (16, 32, 64)
Asyne-Local SGD
range: 2 2-3
Async-Local SGD
y range: [2-11, 2- -00
B set: ( (16, 32, 64)
B set: {16, 32, 64)
M set: {2, 4, 8)
M set: {2, 4)
25

---

Published as a conference paper at ICLR 2026
D PROOF OF THEOREM 2.4
D.1 PROOF TECHNIQUE AND REASONS FOR CHOOSING THE CONDITIONS
Before we state the main theorem and provide the proof, let us explain the intuition, the novelty, and how we identified the conditions of the theorem. The proof of the result is given in Section D.2 and relatively compact. We believe that the simplicity of our result, together with its ability to unify methods, constitutes an important contribution to the optimization community. While the initial part of the proof follows the same structure as in most related works, starting from (7), our treatment of the staleness term | - 1|,,, which naturally arises from the step x*+1 xx > is novel.
After many attempts to develop universal theory, let us illustrate how we arrived at our conditions.
Looking at Figure 3, which provides all possible relations between I² and z², one can easily get
|
211|
Vf(che))-
E Vf(w; {)
(w.
First, we noticed that any reasonable method should utilize E(w.s)es Vf(w; {) in the computation of * before applying (=(==; (see the previous discussion about Condition 2 in Section 2. leading to the following identity:
This implies ((w:)) (w.,e)) S {(=":<))
11* - 211 1=
Σ v((()ee)) JESt
=
for some set S* C {p...., 1} such that S S* = ip.....k. 1}. The identity says that the distance is roughly proportional to the number 55t of stochastic gradients applied after x" and before 2t, which is rightly bounded by the tree distance from x² to the common ancestor x", i... it is bounded by kp....,k 1}1 since S {p. k 1}.
Under Condition 2, notice that Kp..... k 1H = max(1(p. 1,), 111,1s*1) where we use S {p...., h }} and Definition 2.2. Thus, to get a bound for ||I* - 2*11, it is natural to introduce Condition 3, which allows to conclude that | I d s R. It remains to use classical mathematical tools to obtain
=: dist(x", 2*,,
k-1
E || - =* 111"]] $ 2- Σ
[[V[()))
+ Ro?
j=k-R
where the first term will be canceled by the corresponding term -E [| from (6).
D.2 FULL PROOF
Theorem 2.4 (Main Theorem). Let Assumptions 1.1, 1.2, and 1.3 hold. Consider any SGD method
represented by computation tree G = (V, E). Let x Jx20 be a main branch of and [(2*, gk <x)2 be the corresponding auxiliary sequence (see Def. 2.1) that satisfy the following conditions: Condition 1: For all k 2 0, & is statistically independent of {xx+11 zi+1 k-)
Condition 2: The representation of 2h is contained within that of wh, i.e., repr(=*) C (epr(x*),ee for all 2 0. Equivalently, all stochastic gradients used in the computation of z are also utilized in calculating k
Condition 3: There exists a constant R. E oo] such that dist(x 22 x²)) I R for all k 2 0.
1 Then R EK E [[[V (()))( & S for all K 2 4(R+1)LA + B02LD with step size =
minf 21' 2RL 1 where A f(x²)- f
Proof. As the beginning, the analysis is standard. Using Assumption 1.1. we have
f(*h+1)< > - ~V vf(a + In²
2 |[
26

---

Published as a conference paper at ICLR 2026
for g.411 =x* /Vf((= (*). Due to Condition 1 of the theorem and the variance decomposition equality,
T,72
E& [](x S f((()) >(V[(=)) VS(+t)) +
E&
2
5
[5((= *) |1 + 4
7 (V)(z)) (V V)(=t)
-
[V
2 2
2
Ind0²
x ||?
2
2
where E& [ is the expectation conditioned on (a*, )² In the last inequality, we use Assumption 1.3. Rewriting the dot product and using y I 21. we obtain
Ex [1(x+
$ f(x")) 7
2 (IV](a²))) V |[V - V/(+t)]13) + In?
||
InP0²
+
2
2
In202
$ f(²") 7
2 || | 4 | ? ||v/(=t) - vs(ct)]
(6)
2
In the rest the proof, we focus on Vf(x*) v )f( ||² Using Assumption 1.1, we obtain
Vf(**) f || - L | 11.
Notice that there exist E tO...., }} and the closest common ancestor xp such that
V = - (((=)))) - Σ ()(
x² = x²
i=p
and
p-1 V[(w:{) = x² (w.E)ESk
1 = x2
Σ
Σ v)( 0=0
Σ vs(w;
(w.))
where 5 the set of points and random variables used to compute z* starting from xp (see Figure 3). Moreover, due to Condition 3, we have dist(x **)) I max(k p, | < R, meaning 2 k R.
In total,
#2p2k-1 R.
(8)
which we use later. Condition 2 assumes
repr(z*) = ((*t [wu (w:
C repr(a*)) {(21: {(
where If is the multiset union operation. Thus
{ww; (w. S ((
and
)
kk -
(((())))) Σ vf(w; =->
Vf(2')))
(9)
(w.
JESK
where 5 is set such that 5* C fp.....k
A 1}. Substituting (9) to (7),
|[[(z)) - v $ [v((ele))
JESk
27

---

Published as a conference paper at ICLR 2026
Next, using Young's 's inequality || y/l2 = 2 ||x/11 + +2 for all x, E Rd, we get
E f\V - S 2
v(()))
+ +
Σ -(T(()))--v()))) jESt
JES
Since ę is statistically independent of {(x , 2tt , 5 for all E St (Condition 1) and using Assumption 1.3,
E -
< 21
Σ
+2L2 0²
jES
Jensen's incq.
21,272
|
Σ
E [|
+ +2127215540
jESa
Due to 5* C (p.....,k k-1) 13 and (8):
k-1
E -
- [|] s 2
Σ j=k-R
[[| + 2
E
Substituting this inequality to (6) and taking the full expectation, we obtain
LyZ0²
E [[a < E [[(x)]
I
[|>
1T
[|>)((=)))
111
2
4
2
2 2
2L272R R
Σ
E
||
+2L372R00
j=kーR
< E [[(x*)]
I
|
|| -
2.
[|<
+ TT7202
2
k-1
Σ
||
|||
(10)
j=kーR
because 7 S 2RT.
1 Note that Σ Σk=0 ビj=
|
LE' ||
s <R E [|
Thus,
summing (10) for k = o,..., K - and substituting S",
E | -
< f(x)) - fr Σ
E
|
Σ
E [|]
KL
k=0
k=0
K-1
+ 1.273 3 R²
E
k=
K
f((x0) - fr - 2
Σ k=
E
|1"
+ KL7202
because 7 2L. Finally, since E If(x K) f-| 20,
K
E V |1
24 K
+ 2L
K
k=
is left use that y = min
(
2T: 2RL ) } and the bound on K from the theorem statement. [.
28

---

Published as a conference paper at ICLR 2026
E DETAILED DESCRIPTION OF ALGORITHMS AND ITERATION RATES
In this section, we provide a detailed description together with theoretical analysis of the algorithms from the main part.
E. Vanilla SGD
We start we the celebrated Vanilla SGD algorithm, which formally can be implemented in the following way:
Algorithm 3 Vanilla SGD
1: Input: starting point w Rd, step size
2: for ==0 0, 2....... do
3: Sample 1/ De
(1/) are ii.d))
4: Compute stochastic gradient V ((w";))"
5: Update w = w -V fV("""
6: end for
The corresponding computation tree can defined by the recursion
w wk+
f(w"; n²*)
(II)
for all k 2 0.
Figure 15: The computation tree of Vanilla SGD
While the iteration rate of Vanilla SGD is well-known (Lan, 2020), we prove its convergence using new framework for clarity.
Theorem E.1. Let Assumptions 1.1, 1.2, and 1.3 hold. Consider the computation tree (11) of Vanilla
SGD. Then, {x*h Jazo is main branch with x² = w {(z ck ] is the corresponding auxiliary sequence with (
gh) (w r)²) (see Def. 2.1), and * Σ Ek=0 E [[[ foror all
4LA
80 LA
K >
82
with step size y min a
Proof. Indeed, {-*} J220 and ((**,**))sr satisfy Def. 2.1 (see Fig. 15). Moreover, all conditions of Theorem 2.4 are fulfilled: Condition holds because the sequence (77*) } is i.i.d., we have repr(=*) repr(x*) since vt 2h, and consequently, supa20 dist( 0.
29

---

Published as a conference paper at ICLR 2026
E.2 Rennala SGD
We now apply Theorem 2.4 to Rennala SGD. The iteration rate of Rennala SGD is also well-known (Tyurin & Richtárik, 2023), but we provide a proof for completness. Rennala SGD can be formally described as follows:
Algorithm 4 Rennala SGD (Tyurin Richtárik, 2023)
1: Input: point w E R stepsize > O, batch size B E N
2: Workers start computing stochastic gradients w
3: for k == 0....... K do
4: g.º = for all E [n]:
5: while b < B do
6: Wait for the moment when stochastic gradient computed by worker ;)) is computed by worker 7/~ Dg
7:
Gradient ff(w==;;
8:
8 = then
9:
Update of o. (f(w"=;;) locally in worker i b+1
10:
11:
else
12:
Ignore v((wk--6;)
end if
14:
Worker begins calculating gradient at w
end while
16:
Aggregate: gt = E; ;=1 o
(e.g, via AllReduce)
17:
Update: w++ = w* -79
end for
To use Theorem 2.4, we have construct the computation tree of Rennala SGD. It can constructed in the following way:
a' = -==>>>V[2"" 7V)(2";5") x B+ B fxx
-ー 2B
(12)
-B
Vl 22B-1)
where { are i.i.d. from De. See also a visualization in Figure 16. One can easily show that w' x². ww = xº 2² x 21
etc.
TAM goN
Figure 16: The computation tree of Rennala SGD
Theorem E.2.
Let Assumptions 1.1, 1.2, and 1.3 hold. Consider the computation tree (12) of Rennala SGD, then (x* J2z0 is a main branch, {(z*, ((, } with (z* (=*,g*) (xBLk/B) ek) is the
corresponding auxiliary sequence, and RR Σ K- E [(*))() for all
4BLA
S02LA
K 2
82
with step size y min 2BL: ).
Proof. Clearly, {a* Ja20 a main branch and ((* {*)) is the corresponding sequence by the construction in (12). Moreover, & independent of [(++1 24t1 {)) in (12) because {E+ are i...d. (Condition is satisfied). Next, notice that
repr(2") repr(=") = 0. repr(=') repr(== 0 C repr(a!).
30

---

Published as a conference paper at ICLR 2026
repr( (=B-1==B-B000 repr(x") = 0 _ repr(x (
because 2 = x. for all Next,
repr(=") repr(x"))
repr(= (+1)) repr(a (a²)) - (epr(a
repr(22 2B-1) = repr(xx)) S repr(x22-1)
because 26 BB for all B k 2B, where repr(x repr(x ..... repr(x 3 repr(x22-1) due to (12). We can continue and show that repr(**) S repr(**) for all & 2 0 (Condition 2 satisfied). is left to notice that
sup dist(x * 2*) S B -11 1. k20
because
dist(x", 0,
dist(x', ,-)( = dist(x' xx²) 1,
dist(x B-1 , BB1 = dist(x B -1 x00) B 1,
dist(x B B) dist(z" x) 0,
Bist(x 2.,B++1,B+1] BB+) dist(x B+1 x BB 1,
The maximum tree distance between =e and x is 1. Thus, -- in Condition 3.
31

---

Published as a conference paper at ICLR 2026
E.3
Local SGD
The Local SGD method is described in the following algorithm:
Algorithm 5 Local SGD
Require: Initial model w step size y, parameter B
1: for == 1, 1,2.... do
2: Broadcast -º to all workers
3: for each worker i E [n] in parallel do
4: Worker starts Loca LSGDWorker 7) from Algorithm
5: end for
6: Wait for the moment when Σ;= M4 =
(MM) from Locals@DWorker(ff ())
7: Ask workers stop' stop'running Local www.sssweewwew........... M,-1
8: Aggregate y Ei= E5=0 ff(2, (f...,.... ;
RJ). from the workers (c.g, via AllReduce)
9: Update w w - Di=1 -M V5(z) ; RJ)
end for
Algorithm Locaa1sdoorker ?) worker round i
0.0
2
2: M; +0
3: while True do
4: kI K.M.
- fVe K. (n t
7V
k.M. De
5: MM. Mj +1
6: end while
One key change compared to the previous work is that individual local steps M; are not predefined. Moreover, the server tracks the sum Σ M, and waits for the moment Σ M, B before collecting the locally calculated gradients. With proper choice of B, we will prove the optimal computational time complexity of the method in Section F.
The corresponding computation tree of Local SGD can be constructed in the following way. Define N₂ := B and take 0. Then
k. k.O
K.U, [xx
2. 24
4.2
k.
[V #. ; k.1)
2,
(13)
2 2,
R.M,
k.M, -1
V
f(
R.M. :n R.
"Alternatively, allow the workers to finish computing their stochastic gradients without waiting for them (since AllRee be in parallel), but discard these gradients in subsequent iterations, they no longer relevant. This approach may introduce delay before the workers begin their next local steps.
Another option is to allow the workers to finish computing their stochastic gradients without waiting for them, and send these gradients in the next iteration. If some gradients are still not computed by then due delays, simply discard them.
32

---

Published as a conference paper at ICLR 2026
for all i E [n]. and
Nx+1 =x /VI((
x N. -- /=
;111
K.M
N - MWa (2 k.0 2//2
k.0),
(14)
M =x N
V f
R. R,M2
:172
R.M2
x Ne41
x NotDiii M,
f2 K.M
k. R.M 1).
Repeat the previous steps with k k starting N++1 One can easily show that w xB w² 2B w Algorithm 5.
x. N See illustration in Figure 4. x kB ..... where w is the sequence from
Theorem E.3. Let Assumptions I.I, 1.2, and 1.3 hold. Consider the computation tree ((13) and (14)) of Local SGD, then {at }=20 main branch and K
Ek= E [IV] for all
K 2 4BLA
SO
E
with step size 7 min 2BL }
Although the proof may seem technical due to the heavy notation in (14), it actually straighttorward when you refer to Figure 4. This figure clearly shows that all conditions of Theorem 2.4 are satisfied with R B 1 because Ei= Mr B in every global iteration. The condition Ei= M, B
helps to insure that the maximum tree distance sup dist(z x 2t) $ -
Proof. Clearly, (a* 1220 is a main branch by Definition 2.1. The corresponding auxiliary sequence
can be inferred from (14): (2 (z] .7 0.00 ).... (2 (M (Mi) (2).A4, ./1 O.M1) and etc. Con- dition is satisfied because ()) are i.i.d., and by the construction (14). Condition of Theorem 2.4 holds because the same stochastic gradients used for computing 2 also used for z², shown in Figure 4. This can be formally verified using (14) and (13). It left to notice that
sup dist(x" 2 < B - k20
because the maximum number of edges the common closest ancestor can not exit B 1.
33

---

Published as a conference paper at ICLR 2026
E.4 Ringmaster ASGD
Algorithm 7 Ringmaster ASGD (Maranjyan al., 2025)
1: Input: point w E RRa stepsize y > 0, delay threshold E N
2: Set k: = 0
3: Workers start computing stochastic gradients at w
4: while True do
5: Gradient V f =-** 88" :17 5*) arrives from worker i
6: if 8 < G then
Update: w w - fW 1at : k-64
7:
8: Worker begins calculating at u R+1
(orf) } are iid.)
9:
Update the iteration number k k
10:
else
Ignore the outdated gradient ff(w*-
Worker begins calculating at w 178 8th
12:
13:
end if
14:
end while
In this method, main branch can be defined
x w
(15)
and the auxiliary sequence is defined as (h) = (x x=5")) for all k 2 0.
Figure 17: The computation tree of Ringmaster ASGD
Theorem E.4. Let Assumptions 1.1, 1.2, and 1.3 hold. Consider the computation free of Ringmaster ASGD, then {x* Jk20, defined in (15), is main branch and K E [IIVf( I e for all
4GLA
2
82
with step size min{ 2GL To-L
Proof. Condition is satisfied because (nt-0" are i.i.d., x² w and 2* = kk- do not depend on g* = ni k-8 Condition is satisfied because repr(=*) repr(wkk-0") repr(w") = repr(x*). Condition 3 satisfied with R
8h
because
dist(x x²k) = dist( - = 8h S 1,
where the second equality due to the number of edges between at and 6-8 and the last incquality due to the fact that 8 is bounded by B in Algorithm 7.
34

---

Published as a conference paper at ICLR 2026
E.5
Cycle SGD
We now present new method, called Cycle SGD:
Algorithm 8 Cycle SGD
Require: Initial model w", step size 7, group size s 1: Partition workers into groups of size
G[n/s] = [[[n/s] 1)s + 1, .. G1 = (1......... $). G2 {s + 1......................... 2s).
in a circular manner.
2: Broadcast w all workers and assign the local variables 2, w and M, 0 for all E [n]
3: while True do
4: for group index y = 1 to [n/s] do
5: for each worker E [n] in parallel do
6:
M,+1 Mi V f( :ng ))
M.
Mi
De 1/5
7:
M, = M4
8:
end for
9:
Aggregate EiEG, Σ S= rf)) from the workers of group Gg only
10:
Server aggregates and updates the model:
M.
w
Vf
x
j=0
11: Broadcast w*+1 to all workers of group and assign the local variables 2. =w++1 and
M, for all E Gg
12:
== -=r+1
end for
14: end while
This method operates similarly Local SGD, with workers performing local steps. However, key difference that only workers synchronize at each step, rather than all n workers. This strategy can be advantageous in scenarios where reducing peak bandwidth is desirable, A visualization the corresponding computation tree is in Figure 18. For this algorithm, the first Σi=1 M; nodes of the main branch can be defined as
-
Mi I -1
TV M1-1, 1,, M11))
(16)
T E1sl Mi+1
Eis M; [=((:nn
Eis Mr
Eis
Mi
f= M. Ma- 11 111111 Mo-1)
Notice that Eia M. = w., where we capture and unroll all stochastic gradients from the first group. The next nodes of the main branch can be defined in similar way going through groups circularly. Theorem E.5. Let Assumptions 1.1, 1.2, and 1.3 hold. Consider the computation tree of Cycle SGD (Alg. 8), then (x. )22, defined in (16), is main branch and 1 K- E [=* S for all
K Σk-1
8n2 LA
802 LA
K
88
22
with step size 7 min T Ao
35

---

Published as a conference paper at ICLR 2026
Figure 18: An example of Cycle SGD computation tree.
Proof. Once again, the proof is geometric. As an example, consider Figure 18 together with Algorithm 8. One can easily show that Conditions and 2 are satisfied similarly to the proof of Theorem 5. However, the maximum tree distance is different since we synchronize the workers in circular manner.
First, the number of local steps M4 S T gradient in the inner loop and synchronizes every loops.
2n because each worker computes one stochastic
Next, the maximum tree distance between a point x² the main branch and the corresponding point of the auxiliary sequence z² at most 2n Let us explain this step. Consider any æ² and 2 and their closest common ancestor w (in Figure 18, for instance, take x. 22
2,2 and xي accordingly).
The number of edges from = to w never exceeds 2n due to the bound on the number of local steps. The number edges from =² to w never exceeds 2n because, while one worker performs local
steps, other workers grow the main branch by most [ (n 1) 2n(n-1) points before the worker that computed * is synchronized".
Thus, we can take R
2n in Condition of Theorem 2.4.
'For instance, see Figure 18, where, hefore the algorithm applies V from the second worker, the main branch grows by two edges, from x to x due gradients computed by the first worker.
36

---

Published as a conference paper at ICLR 2026
E.6
Async-Local SGD
The following algorithm is a mixture of Asynchronous SGD and Local SGD, which we formalize in the following way.
Algorithm 9 Async-Local SGD
1: Input: point x0 IR.,, stepsize y > 0, delay threshold B N, number of local steps
2: Set k k==0 0
3: Workers start running local steps at w with Alg. for M steps
4: while True do
5: Sum y -p= Vf(e,, The arrives from some worker is
6: Find the tree distance 8t dist(w", 22.))
(delay 8 of *-* at which point worker is started local steps)
7:
if 8 B then
Update: w = w - Epen -- V
8:
9:
Worker starts running local steps w+1 with Alg. 10 for M steps Update the iteration number k = k +
10:
11:
else
M-1 VI Ignore the outdated sum Ep=
12:
Worker starts running local steps w with Alg. 10 for M steps
14:
end if
end while
Algorithm 10 Local 1 sGDworkerwwwwrrwoooooo.... 7, M) in worker
1: O.... do
2: for p ==
3: _pt1
- ~VV((=() df De
4: end for
5: Send to the server 7 EnHo" vf(+fn!!
.M 1, then this method reduces to Ringmaster ASGD (Alg. 7). Taking M 1, we can improve the time complexity of Ringmaster ASGD by decreasing the number of times when workers synchronize with the server. For this method, it is natural to take main branch as
f f( )
M x M-
~ [2 -1-11: :1:
(17)
x: M(k M(k-1)+1 x ((k- V
Mk I: MK MM
; M-1)
and so on. Notice that x0 = W = w etc.
Theorem E.6. Let Assumptions 1.1, 1.2, and 1.3 hold. Consider the computation tree of Async-Local K
SGD (Alg. 9), then {a* Jazo. defined (17), is main branch and H Σk=0 E for all
[[V]f(>>)1 <
B M I)LA
S02LA
K
E
c²
37

---

Published as a conference paper at ICLR 2026
with step size y min 4(B+ 1I 4--2
Proof. Similar to the previous proofs, Condition 1 is satisfied for the main branch (x J:20 because all random variables {nj} in (17) are i.i.d., and x0 and 2i do not depend on n/. Points M-1 and .M-1 do not depend on 1/, M-11 and so on. Conditions 2 satisfied because stochastic gradients Fi
used to compute z are also used to compute the corresponding point on the main branch for all p E {O..... M - } and k 2 0 (see Figure 5). Condition 3 is satisfied with = B + M due to the inequality 8 dist(w = < B in Algorithm 9 and the fact every worker calculates M stochastic gradients, which ensures that the tree distance between 2fe and the corresponding point from the main brain branch is at most B 1, the tree distance between 2 and the corresponding point from the main brain branch is at most B 2, ..., the tree distance between
+ M -
M and the corresponding point from the main brain branch is at most + M - 2. Fi
E.7 Async-Batch SGD
This method does the same steps as Async-Local SGD with the only difference that the workers calculate mini-batches instead of local steps:
Algorithm 11 BatchhsGDWorker((.... M) in worker
2: for O...MM M - do
3: Calculate (=(=:nn)) The Dę
4: 2p+1 =
5: end for
6: Send to the server Enro vf(=f;n))
One can easily show that these methods share the same theoretical guarantees (Sections E.6, F, and G) as Async-Local SGD.
38

---

Published as a conference paper at ICLR 2026
E.8
Local-Async SGD
One way to interpret the following algorithm is that the workers are partitioned into groups, with each group running Asynchronous SGD. Then, certain points, all workers synchronize, and start running Asynchronous SGD at a new point. One of the important novelties here is the condition Eg=1 my B, which, with a proper B, leads the optimal computational time complexity (Section F).
Algorithm 12 Local-Async SGD
Require: Initial model w", step size n, parameter B, group partitions Gl.... Ge for == 0, 1, 2.... do
2: Broadcast wx to all groups
3: for each worker g E [s] parallel do
4: Group g starts AsynccronoussSiiGrouugg
7)) from Algorithm 13
5: end for
6: Wait for the moment when Eg=1 m, B ((mA) from AsyachronouSSDDGnooddeef ())
7: Ask the groups to stop' 9 running AsycchoonuuSGGGruuull.,
8: Aggregate 7 >g=1 E5= Vi(wg :ng) from the groups
5m,-1
(mn)) are i...d)
9: Update w = wh Eタ=1 E ff(D) mg)
10: end for
Algorithm 13 AsynchoonousSiDDiiouuuu,, 7) in group
Input: point 9 E Rdd, stepsize 7 >
Set my = ()
Workers from group start computing stochastic gradients at 2g
while True do Gradient ff(uu mh, 6" m²) arrives from worker i with delay 8m, ;1
Update: ig mu+1 tig - V flng m, 1g myy
Worker i begins calculating stochastic gradient at ug m
Update the iteration number my mg end while
For this method, it is natural to take main branch of the computation tree
x! o
fCp 0-80 ;n))
/V(
1-8
17 m 1
(18)
2
x mp-1
E1sl -
-VVf(e
0-80
::?))
2 2y
26-1 mp-1
7V -1
;11 m
Alternatively, allow the workers finish computing their stochastic gradients without waiting for them (since AllRuce can run parallel), but discard these gradients subsequent iterations, they are no longer relevant. This approach may introduce delay before the workers begin their next local steps.
Another option is to allow the workers to finish computing their stochastic gradients without waiting for them, and send these gradients in the next iteration. If some gradients still not computed by then due delays. simply discard them.
39

---

Published as a conference paper at ICLR 2026
where that x
E
x
w. and {ug] is defined in Algorithm 13.
9/1 finb
of
vf
Vyld
Figure 19: An example of Local-Async SGD computation tree with two groups and B 5. One group performs mh = 3 steps of Asynchronous SGD, while the other performs 722 = 2 steps. Note that the maximum tree distance is dist(r* xx of u1-²") when applying ff(e--" : to x². and equals B - 1 = mi + ma = 4. Then, the groups synchronize and continue from x.5
Theorem E.7. Let Assumptions 1.1. 1.2, and 1.3 hold. Consider the computation free of Local-Async SGD (Alg, 12), then }=20 defined in (18), main branch and K -K-1 E [II S for all
4BLA
802LA
K
g2
with step size min 4BL 40-1
Proof. The proof closely follows that of Theorem E.3, with the only difference being that the auxiliary branches Algorithm 13 are constructed using asynchronous steps rather than local steps
(compare Figure 4 and Figure 19). As in Theorem E.3, the condition Σg=1 my = B ensures that supx20 dist(x *) s B-1.
40

---

Published as a conference paper at ICLR 2026
E.9 Nested Local-Async SGD
In this section, we formalize a hierarchical version of Algorithm 12. Our framework, Theorem 2.4, is flexible enough to support such two-level structure, where each cluster consists of servers equipped with (4-8) GPUs. The GPUs run Asynchronous SGD, the servers synchronize within their clusters, and finally, the clusters synchronize with each other.
In the following algorithm, all workers are partitioned into {Git} groups, where is the cluster index and is the server index within the cluster. The set G.3 contains the indices of the workers (GPUs).
Algorithm 14 Nested Local-Async SGD
Require: Initial model w step size 7, parameters B,, global parameter B, group partitions {Gi}} for == 0, 1, ..... do
2: Broadcast w to all clusters
3: for each cluster in parallel
4: Set ! = w
5: for p. = 0,2,, do
6: Broadcast w to all local groups
7: for each server j in parallel do
8:
Group G.y starts AyynchonoouSSGGGGouutttu" :)) from Algorithm 13
9:
end for
Cluster waits for the moment when Σ3 maj = B:
Ask the groups in cluster to stop running AsyichronouSSDCCnoupttp"""" ;?)
Update wiit1 w y Ej D -I vf(opp injpp)) end for
12:
13:
14:
end for
15:
Wait for the moment the total number of local steps in the clusters starting from the last
broadcast is B
Ask all groups in all servers stop running AyynchoonouSGDGGronnlf ?
17:
Update w = - - -i w w >; Ex E3 E V ingge)
18:
end for
Algorithm 15 AyynchronousSGGGrrrupuuu.. in group Gij
Input: point o E Rdd stepsize >
Set m,y
Workers from group Gij start computing stochastic gradients o
while True do
Gradient f
miyps
gmiiss
misps) Tajps
arrives from worker i with delay Sm
Update: Uijp:
maip: Pijp
miip; " Uij:
majrs Majp: +1
Worker begins calculating stochastic gradient at v kipp
Update the iteration number mijp, -Mips + end while
We believe that analyzing this algorithm directly using classical optimization tools would be chal- lenging due to heavy notations. However, using framework and geometrical graph reasoning, we can easily prove the iteration rate of this algorithm. As in all previous cases, a main branch x can be defined by taking each component of the sum Σ, En- E, Em ff( e-8' applying each stochastic gradient to x² x² -0 7 fV ffoo). and so on.
:nfa)) and
Theorem E.8. Let Assumptions 1.1, 1.2, and 1.3 hold. Consider the computation of Nested K E [> for all
Local-Async SGD (Alg. 14), then 1/4 ΣE k=0
4BLA
K >
e2
41

---

Published as a conference paper at ICLR 2026
with step size y min 4BL 46 } for the main branch {x*} (slightly informally) defined above.
Proof. Similarly to the previous proofs, Conditions 1 and 2 are satisfied by the construction of the algorithm. Using geometric graph reasoning, Condition 3 is satisfied with I S B due to the requirement that "the total number of local steps in the clusters starting from the last broadcast is B." This ensures that the distance between the points of the main branch and the corresponding points of the auxiliary sequence defined by v. does not exceed B.
Remark E.9. One can see that the converge rate does not depend on [B.). Theoretically. it is sufficient take B; oo. However, practically, may better take B; < co to ensure that the GPUs synchronize more often and share information with others, but can lead to communication overhead and less efficient utilization of the GPUs.
42

---

Published as a conference paper at ICLR 2026
E.10
Meta Local SGD
Compared to previous algorithms, Meta Local SGD is abstract meta-method, includes one abstract step: "Wait if needed and take any set of workers S." This step is not explicitly defined, allowing users apply any strategy they prefer. It may be random, where the algorithm chooses a uniformly random subset; may follow a condition as in Local SGD, where the algorithm waits until Di=1 M2 B; may be based on the current communication speeds of the workers, where the algorithm selects the workers with the fastest communication speeds at the current optimization moment.
However, as we explain in the main part, this can lead to a computation tree with a large R. That why we check the condition max d, + E:=1 M; B in the algorithm, where {d:} are the current distances to the head of the main branch and (Mi) are the local steps performed by each worker. If this condition is satisfied, we can take any set of workers S. Otherwise, we find a set of workers S {j E [n] dj + +i== M, = B} and ask them to send their calculated stochastic gradients. The latter case is required to synchronize workers with "very old stochastic gradients". Intuitively, if we do not synchronize them, their stochastic gradients may become too outdated and harmful to the optimization process.
Algorithm 16 Meta Local SGD
1: Input: point w E Rd, stepsize y >> 0, parameter B E N
2: Set an auxiliary distance variable d; = 0 for all i E [n]
3: Workers start running local steps at w" with Alg. 17
4: for & = 0, 10.1,...d do
5: if maxxe[m] dy + Ex= M, < B then
6: Wait if needed and take any set of workers S (Here, we not specify the selection method, could random or based on the current communication speeds. One can choose any strategy.)
(Soft Sync)
7: else
8: Find set of workers S (j E [n] E M, B}
(Hard Sync)
9: end if
10:
Ask workers from S to send the calculated stochastic gradients and stop the loops in Alg. 17
Receive y Eies 0 m=(=)
12:
Update: w++1 = Σ (=(''n))
13: Worker from start running local steps at #h1 with Alg. 17
Set d; 0 for all S
15:
Update d; = di + EEes Mj for all illigs
16: end for
Algorithm 17 LocalsGDWorker(u, ?) in worker
1: z = w
2: M;
3: while True do
4: Calculate Vf(2 :
Mr Mi), yy Dz
5: if max]e[n] dj + Eis M, < then
6:
2 Mi+1 Mi
24 V f fzz MM
7:
M, M, M +1
8:
end if
9:
end while
main branch in the computation tree can be defined follows. Assume that S (ir,... ..., ,p. is the set of workers participating in iteration k. Then, the computation tree with the main branch {x²*)
43

---

Published as a conference paper at ICLR 2026
can be constructed
x² dd 7V [sl it)))
x² 1z V (2), :
x Mi, Mi V f( M11 :
M,1 )) 7771
(19)
- M, +1 - Mi - > ;mbpp)
2i M, x ش Me,-1 -1 7/V fZipp
Mipc -1 Mipk )
Tipp
Notice that the end of each iteration block can be written
wt --11 My
w x شو M,, +E Mr,
and so on.
1,1
1,2
21
11
Wit of
2,1
2,2
2
x²
x²
3
I
1.1 222
1.2
Figure 20: An example of the computation tree for Meta Local SGD with two workers. In this example, the first worker completes its first set of local steps, x." - 22 1.1
22 1.2 and sends the stochastic gradients, which are used calculate x and x2. similar sequence of steps is repeated by the first worker to produce x² + 22 + 2.2 followed by z and x4, At the same time, the second worker has only completed . + 21 -> 21 and has not yet synchronized or sent the corresponding stochastic gradients. At this moment in time, the number of local steps is M2 2 and d2 because d2 is the number of edges between the current main branch head x and the point x", where the local branch of the second worker started, At the same time, M1 0 and di 0, because the first worker has just started the third set of local steps at x and has not yet calculated local stochastic gradients.
Theorem E.10. Let Assumptions 1.1, 1.2, and 1.3 hold. Consider the computation tree of Meta Local SGD (Alg. 16), then {a* Jk20, defined in (19), is main branch and 1 K-1 E [[] < for all
K
4BLA
B0
K>
62
with step size 7 min JBL ).
Proof. Similarly to the previous proofs, it is clear that Conditions and from Theorem 2.4 are satisfied for the main branch (19).
It remains to show that dist(æ:* ,²²) < B for all k: > 0. In the algorithm, track two key sets of variables: {d,} and {M,). The variable M, denotes the current number local steps performed by worker i, while represents the number of edges between the current end of the main branch and the point where worker began its local updates. When worker & S, the distance de increases as follows: d, d; + Ejes Mj, since the workers in S extend the main branch with their accumulated local updates.
44

---

Published as a conference paper at ICLR 2026
The algorithm is constructed that the quantity caxje(n) dj -i= Mr remains bounded by B throughout the entire optimization process, ensuring that Condition is satisfied with = B. To clarify, assume that i S in Algorithm 16. In the worst-case scenario, all other workers j E S. with j * i, apply their local updates, increasing the tree distance from worker i's branch to the main branch by most Ljes.jzt My. Thus, the updated tree distance becomes most
d; + Ejg(n),ss My. Since worker has also performed Mj local steps, the tree distance bounded by d; + Ejelm) Mj M; v B.
45

---

Published as a conference paper at ICLR 2026
E.11 Dual- Caal-Process SGD
We now present new method, Dual-Process SGD, which is very similar to Local SGD. In fact, when communication is free, the two methods are equivalent. However, Local SGD requires all workers to send the of stochastic gradients only at the end of each round. In contrast, in Dual-Process SGD, workers do not wait until the end of the round; instead, they begin communicating sequentially as possible.
Initially, each worker waits for the first stochastic gradients with index 0 and immediately sends them available. Then, while these are being transmitted, the workers continue their local computations. After the server receives the gradients with index O, the workers begin sending the next batch of stochastic gradients, starting from index up the latest index they have computed at that moment. This process continues until the server has received a total of B stochastic gradients, accumulated through the communicated sums. This logic is implemented in Algorithm 19.
Algorithm 18 Dual-Process SGD
Require: Initial model w step size Y parameter
1: for k = 0, 1, 2.... do
2: Broadcast " to workers
3: for each worker i E [n] in parallel do
4: Worker starts Maa.PPoocesssccaaassoooeeeee 7) from Algorithm 19
5: end for
6: Start receiving the sum from the workers
7: Wait for the moment when the total of received gradients E M, B
8: Ask workers stop running Dua maallprrcsssttcollllaatrrreeerer
9: Update w+11 w E Σ Mi-1 Vf( :1 (d)
end for
Algorithm 19 DuaalPrrcssiccaalSSoeeeetrr worker round A:
k.0
1:
2
2: M, = M, = M₁ =
3: Launch in parallel the following two processes:
4: Process 1:
5: while True do
6: Calculate ( 5,, k.M,
11 TB K.M, De
7: A.M.+ M.M.
7V f(= k Mr M.M
;
8: MM M, +
9: end while
10:
11: Process 2:
12: while True do
13: Wait until at least one new stochastic gradient is computed Process
14: Set temporary variable M, MM;
Mi-1
15:
Send
Vf(= (.)))
j=M;
Wait until the transmission complete
17:
Update M, = M;
end while
The computation tree of Dual Process SGD defined in (13) and (14) is similar to Local SGD.
Theorem E.11. Let Assumptions 1.1, 1.2, and 1.3 hold. Consider the computation tree ((13) and
(14)) of Process SGD, then (x²*) 3z0 main branch and [ & E for
[[V
46

---

Published as a conference paper at ICLR 2026
all
4BLA
S0
K 2
6
with step size 7 min 2BL T
Proof.
The proof is exactly the same as Theorem E.3 since the computation tree of Dual-Process SGD is similar to Local SGD.
47

---

Published as a conference paper at ICLR 2026
F COMPUTATIONAL TIME COMPLEXITIES OF ALGORITHMS UNDER h -FXED COMPUTATION MODEL
To compare methods, consider the hi-fixed computation model (Mishchenko et al., 2022). In this model, it is assumed that
worker i takes no more than h, seconds to compute a single stochastic gradient
(20)
and
< h1 S h2
hnn
(21)
without loss of generality.
Note that it is possible to consider the universal computation model (Tyurin, 2025) and capture virtually all possible computation behaviors of the workers. While the hy-fixed computation model may seem more restrictive, turns out that all optimal methods (Maranjyan al., 2025) in the universal computation model are also optimal in the hy-fixed computation model. Thus, for simplicity, we stick to the h computation model.
F.1 Rennala SGD
Theorem F.1 (Rennala SGD). Consider Theorem E.2 and its conditions. Under the h;-fixed computa- tion model (20), the computational time complexity of Rennala SGD (Alg. 4) is
LA
0² LLLA
min mE(n]
(22)
h4
m
im
with B max
We start with the following lemma. Lemma F2. Let define
-1
m
TR (R( = 2 min
(B + m)
(23)
me(n)
h4
Under the lu-fixe computation model (20), the time required to calculate x² ..... xB of the main branch is at most Tk( (B) seconds, the time required to calculate BB1 ,..... 2B at most Ta (B) seconds, and
Proof. The idea of Rennala SGD (Alg. 4) is pretty simple. Notice that all workers calculate stochastic gradients the same point in parallel until the server collects batch of size B (condition ensures that). Since they work in parallel, under the fixed computational model, after t seconds the workers will calculate
Σ max -
1.0}
(24)
h. the number of stochastic gradients computed by worker in seconds. We subtract because at most one stochastic gradient be can be ignored due to the condition 0 in Alg.
stochastic gradients because
Notice that
-1 (B+ +
m
TB =
Σ hi
+m*)
for some m² E [n]. Substituting it to (24), we get
max
TR(B) h;
- 1,0 2 Σ max
{
TR(BB)
1,0 2 Σ
m
TR(B)
m
h4
h,
i=
48

---

Published as a conference paper at ICLR 2026
n TR( i=1 h, -2m" = 2( + m²) 2m" 2 B.
Thus, after (B) seconds, the server collects B stochastic gradients, which is equivalent to calcu- lating x¹ ...., _ of the main branch. The same argument can be applied to the next point of the main branch, and so on.
Proof of Theorem F.I. Due to Theorem E.2, we know that 1
Σ
K--
E
S E for [VV
K
K=
4BLA
S02
K
E²
From Lemma F.2, we know that the time required calculate most TR( (B) seconds, the time required to calculate x B+
of the main branch is at 21 is at most (R(B) seconds, and so
on. Thus, the total time find an e-stationary point .....
K o TR(B)
LA
LL
))
=
[R(B)=
+
B
Using the choice of B,
-1
K
LA
o
TR(B)
B
=
mE(N]
min
hi
(B
m)
-1
m
LA
0
min
mE(n]
m7
h
m
F.2 Ringmaster ASGD
Theorem F.3 (Ringmaster ASGD). Consider Theorem E.4 and conditions. Under the hi-fixed computation model (20), the computational time complexity of Ringmaster ASGD is
LA
LA
min mE(n)
h4
m
i=1
with B = max
We use Lemma 4.1 from (Maranjyan et al., 2025).
Lemma F.4. ((Maranjyan et al., 2025)) Let the workers' computation times satisfy the hę-fixed computation model ((20) and (21)). Let B be the delay threshold of Alg. 7. The time required to complete any B consecutive iterate updates of Alg.
most
m (1E1)
R m
TA(B): = min mm|
1
(25)
Corollary F.5. In view of Lemma F.4, Under the fxxfixeed computation model (20), the time requived
calculate x1 ..., of the main branch most (B)) seconds, the time required calculate x B+1 ....,,2.
2B is al most (B) seconds, and so on.
Proof of Theorem F33. The proof of Theorem F.3 is similar the proof of Theorem F.1. From Corollary F.5, we know that the time required to calculate x ...., x.. of the main branch is at most T^(B) seconds, the time required to calculate B+1 ,...,,"" 2B is at most TA (B) seconds, and so on. Thus, the total time to find an e-stationary point is
(TA(B)
LA
P'LA
O'LA
1)
TA(B) x B
= o
min mEim]
m im
ha
m
49

---

Published as a conference paper at ICLR 2026
F.3 Local SGD
Theorem F.6 (Local SGD). Consider Theorem E.3 and its conditions. Under the h;s lu--ixee computation
model (20), the compulational time complexity of Local SGD (Alg. 5)
)
0² L2LA
min mE(n]
+
h4
mE?
with B = =mmax {
:1
Lemma F.7. Let us define
m
(B) = 2 min mE(n)
(B m)
(26)
h4
Under the he-fixed computation model (20), the time required to calculate x² x of the main branch is at most (B) seconds, the time required calculate B4 2B is at most (BB)) seconds, and so on.
Proof. The idea is the same in Lemma F.2. All workers calculate stochastic gradients in parallel, with the only difference being that the points at which they compute the stochastic gradients differ due to the local steps. the server can stop the workers, then after seconds is possible to collect
Σ h4
(27)
stochastic gradients. it is infeasible to stop the calculations (see footnote 7), then after seconds is possible to collect
Σ max {[=t] Tr -1,0 1,0 }
(28)
where subtract because Similarly to Lemma F.2, substituting Ti (B) into (27) and (28), one can show that (B(B) is sufficient collect B Ei M4, stochastic gradients, or, in other words, calculate x1 .... 2 of the main branch. The same argument can be applied to the next B points of the main branch, and so on.
stochastic gradient can be ignored if it is nonrelevant.
Proof of Theorem F6. The proof essentially the same as the proof of Theorem F.I.
F.4
Local-Async SGD
Theorem F.8 (Local-Async SGD). Consider Theorem E.7 and its conditions. Under the hi-fixed computation model (20), the computational time complexity of Local-Async SGD (Alg. 12) is
m
LA
LLLA m
min mm(n)
m
with B max { -
}
Lemma F.9. Let define
( = min
Σ
(B + m)
(29)
m
Under the h fixex computation model (20), the time required to calculate x' ..... 2B of the main branch is at most (B) seconds, the time required to calculate x B++1 seconds, and
2n at most Tr (B)
50

---

Published as a conference paper at ICLR 2026
Proof. The idea is the same in Lemmas F.2 and F.7. All workers calculate stochastic gradients in parallel, with the only difference being that the points at which they compute the stochastic gradients differ due to the asynchronous steps in the groups. Similarly, time to calculate B Eg=1 my stochastic gradients in Algorithm 12, or, equivalently, to calculate
show that (B)(B) is sufficient
x', ..... r'...., x of the main branch. The same argument be applied the next B point of the main branch.
Proof of Theorem F88. The proof essentially the same the proof of Theorem F.I.
F.5 Nested Local-Async SGD
Theorem F.10 (Nested Local-Async SGD). Consider Theorem E.8 and its conditions. Under the hx-fixed computation model (20), the computational time complexity of Nested Local-Async SGD (Alg. 14) is
))
m
LA
o² LA
min mm(n)
+
m
h4
me²
with B max {
[[2
and B; 00 for all [n].
Proof. The proof essentially the same the proof of Theorem F.I.
F.6
Async-Local SGD
Theorem F.11 (Async-Local SGD). Consider Theorem E.6 and its conditions. Under the ha-fixed computation model (20), the computational time complexity Async-Local SGD (Alg. 9) is
m
LA
LLLA
min mEim]
hi
ms²
and M max with B max {[ o² 1
o2 1]
nc
Lemma F.12. Let define
m
(B, == min me(n)
(B Mm)
(30)
hi
Under the li-fixed computation model (20), the time required calculate x² branch is at most TAL (B, .M) seconds, the time required to calculate x B+1 x 28 is at most (AL(B, M) seconds, and so on.
B of the main
Proof. Let fix B and M 1. Note that
[ his (B + Mm)
m
1 hi
TAL (B, := min
=
(B Mm*)
(31)
mE
for some m² E [n], which depends B and M.
For any &: 2 1, consider the sequence x ...., B++B on the main branch. Using a proof by contradic- tion, assume that it requires algorithm can progress up to B- after TAL(B, M) seconds.
than TAI (B, .M) seconds to calculate 2++ ,...,, k+B Thus, the
In Algorithm 9, each worker computes M stochastic gradients and sends their sum to the server. The server then performs the update k+1 w 7 Enso f v²,)) which equivalent to
1t is possible to take B, < 00, but the computational time complexity may decrease due to less utilization of workers. For simplicity, in this theorem, take B, See also Remark F.9.
51

---

Published as a conference paper at ICLR 2026
extending the main branch by M points. Therefore, after seconds, the main branch will have progressed by at least
Σ max M
M,O
(32)
Mhh
points (which is less than B by assumption). This is because worker requires at most M/, seconds compute M stochastic gradients before sending them to the server. Note that during any B consecutive updates on the main branch, the server may ignore M gradients from each worker at most once, because 8 can be 2 B most once during -1 consecutive updates. This explains the subtraction of M in the formula.
Substituting TAI. [B, M) to (32).
Σ
max M
TAL. (B, M)
M,
m Σ
max M
{M
(B, Mh,
MM.}
Mh;
1=1
TAI M)
m
(B, M)
M
Mm
2M
Mh;
h;
1=1
because [x] 2 x
1 for all æ E R. Using (31),
Σ max {
M {M]
(B, M)
-M.0 2 + Mm²) 22Mm 2 B.
Mh;
Thus, after TAL (B, M) seconds, the server collects B stochastic gradients. It is equivalent to calculating x+1 hht which contradicts the assumption.
Proof of Theorem F.11. Due to Theorem E.6, we know that K EK
E [[ S for
4(B + M I)LA
SA 2²
K
E
From Lemma F.2, know that the time required calculate x² xb of the main branch is at most (B, M) seconds, the time required to calculate x B+1 2B is at most TAI(B, M) seconds, and so on. Thus, the total time find an e-stationary point is
K B) o (Ta(BB,M)
[T.( + M)
2 ))
o (B,
Be
B²a
Using the choice of B and M, we obtain M < B and
K o [R((B)
LA
LALA
(A) x
B
=
8
Bea
-1
m
LA
d² dLLA
min me(a
(B Mm)
+
h
E
Bea
-1
LA
=0
min me(n]
Σ h4
(B MB)
x
8
because B 2 d Since M < d²
+ and B < o²
+ 1,
K
d2
mo²
LA
0 [R(B)= x
= o
min mEin|
+
+
m
B
h
-1
0²
LA
=0
min
+ m
x
mein]
h4
52

---

Published as a conference paper at ICLR 2026
1
m
-1
LA
1
min me [m]
me?
hs
where we use that m S n for all m E [n].
F.7 Cycle SGD
Theorem F.13 (Cycle SGD), Consider Theorem E.5 and its conditions. Under the hy-fixed computa- fion model (20), the computational time complexity of Cycle SGD (Alg. 8) is
LA
LA
))
max hi kE(n)
me?
with min max
n
Proof. According to Theorem E.5, K k=
Σ K-1 E [|V (
S for
8n LA
802LA
K
g2
In the beginning, the algorithm has "warm-up", where, in the first iteration of the inner loop, the server collects 8 stochastic gradients from s workers, which is equivalent to calculating x'...., of the main branch. Then, the server collects 2s stochastic gradients from the next group of workers because they calculated 8 stochastic the previous iteration. Starting from the th iteration, each group of workers will return x [ stochastic gradients in every subsequent iteration. Every iterations takes at most max h; seconds, because they work parallel and calculate one stochastic iE
gradient.
Thus, the total time to calculate ,',...,,2? K and find an etstatoonary point
max h4 x sE|n)
max bas X iE(n)
"warm-up" up" phuse
12
nLA
LA
max h4 (E(n)
x
+ max h4 x
+
(E(n]
ns²
nLA
LALA
max hy x
(E(n)
ng²
because LA > without loss of generality (if LA
1 then I: is an 5 e-stationary point). Finally,
nLLA
σ² LA
LA
o²
LaLA
max h; X sE/m]
=0
max h x (Eln)
n
ne²
due to the choice of
F.8
Dual-Procc Peal-Proesss SGD
Theorem F.14 (Docl-Process SGD). Consider Theorem E. 1 and its conditions. Under the fi-fixed computation model (20), the computational time complexity of Dual-Process SGD (Alg. 18) is
LA
م ms²
min mE(n)
h4
{
with B = =max
53

---

Published as a conference paper at ICLR 2026
Proof. The proof is essentially the same the proof of Theorem F.6 since Dual- Process SGD is equivalent to Local SGD if the communication times are ignored.
54

---

Published as a conference paper at ICLR 2026
G TOTAL TIME COMPLEXITIES OF ALGORITHMS UNDER ( -FIXED COMPUTATION MODEL
To compare the communication complexities and the total time complexities the methods, we now assume that it takes seconds to send vector from worker parameter server and seconds to send a vector from the server to the workers in the centralized setting. Alternatively, it takes seconds send vector all other workers the decentralized setting. Moreover, assume that all workers have the same computational performance: worker takes h seconds to compute a single stochastic gradient for all E [nz]. We refer this the (h, T) --fxed computation model.
Note that it is possible to assume that each worker has its own communication time bound and computation time bound h4 and consider (h,, Ti) fixed computation model (Tyurin et al., 2024). However, for simplicity, we assume т, = T and h; = h for all i E [nt]. See Section I for a more general case (h,, T3) Ti)-fixed computation model.
G.1 Rennala SGD
Theorem G.1. Consider Theorem E.2 and its conditions. Under (h, T)-fixed computation model, the total time complexity of Rennala SGD (Alg. 4) is
LA
LA
LA
+ h
ns²
with B max {
Proof. Note that the communication between of vectors happens every calculated stochastic gradients, which is equivalent to every B updates of the main branch. Thus the total number of communications is
K B
where 0
(BLL
BBA
+
LLA
due to Theorem E.2. The total communication complexity is
K
BLA
a²
-
(
LA
0 T
B
x
e2
T
where we use the choice of B. It left to take into account the computation factor, which is the same as in Theorem F.I.
LA
LL
(22) 0
hx
ng²
5
under the (h, ffixxed computation model.
G.2 Local SGD
Theorem G.2. Consider Theorem E.3 and its conditions. Under (h, T)xfxed computation model, the total time complexity Local SGD (Alg. 5) is
LA
LA
d'LA
+ h
ng?
with B max .1)
Proof. The proof essentially the same the proof of Theorem G.I.
n
55

---

Published as a conference paper at ICLR 2026
G.3 Cycle SGD
Theorem G.3. Consider Theorem E.5 and its conditions. Under (h, --xxed computation model, the total time complexity of Cycle SGD (Alg. 8)
LA
LA
LA
o² LA
n
+ h
x
ng?
with min max
n= o²
111
n
Proof. Similarly to the proof of Theorem F.13, one can show that the total time complexity is
K
(T + +(T +(++h)
8 :1
"warm up" phuse
because every worker from group 8 sends one vector Σ/1 Substituting the choice of 8, one can get the final result.
(x( to the server the inner loop.
G.4 Async-Local SGD
Theorem G.A. Consider Theorem E.6 and its conditions. Under (h, -)-fxedd computation model, the total time complexity Async-Local SGD (Alg. is
LA
LA
LA
T
+
h
E
ns²
with B max {[=² and M max
o² ne
1)
Proof. Under (h, --ieed computation model, all workers send the sums of M stochastic gradients at the same time. According to Theorem E.6, the server should collect
0 (B+ (B+M- oFLA -1A)== o E
LA
LA
E²
stochastic gradients, where the last equality due the choice of B and due B M. Since the workers work in parallel and have the equal performance, only θ (min M: n))
B
@ min max { 1, a² Me .n) workers will participate in optimization. Thus, every worker, which participates in optimization, has to send
LA min B
T²LA
) -0
-0
LA
LLLA nE²
MLA
+
nn
min (
stochastic gradients. Such worker calculates M stochastic gradients and only then sends the sum; thus, the maximum number of communications by one worker is
LA
LLLA
LA
Mng² +
Me
For every communication, the worker needs to send M stochastic gradients, which takes h seconds, and sends a sum, which takes T seconds. Thus, the total time complexity is
o (1+ Mh)
LA
LLLA
LA
(33)
M
Mns
Substituting the choice of M, we get the final result.
56

---

Published as a conference paper at ICLR 2026
G.5 Ringmaster ASGD
Theorem G.5. Consider Theorem E.4 and its conditions. Under (h, -)-fxed computation model, the total time complexity Ringmaster ASGD is
LA
LA
LA
o²LA
h
(34)
ng²
8
ne²
{
with B max
Proof. The proof repeats the proof of Theorem G.4. The only difference is that the workers send M =
stochastic gradients. Substituting M = 1 to (33), we get the final result.
Remark G.6. While (34) only an upper bound, using the same steps as in the proof of Theorem G.4, can easily show that the total time complexity of Ringmaster ASGD is lower bounded by
LA
LLLA
LA E
o LA
Ω
T
E
NE²
+ h
nE²
(35)
from Theorem E.4 is tight. As far as we know, this is the current state-of-the-art iteration rate of Asynchronous SGD-like method (Maranjyan et al., 2025; Mishchenko et al., 2022; Koloskova et al., 2022: Cohen et al., 2021).
assuming that the iteration rate θ
[LA
L'LA) 6²
H COMPARISON BETWEEN OUR Local SGD AND THE CANONICAL Local SGD
In this section, we show that our version of Local SGD (Algorithm 5) achieves a better time complexity than the classical Local SGD. Although focus in this section only on Local SGD, we expect similar improvements to extend to other new methods from Table 1. The purpose of this section is to highlight the tightness of the Birch SGD framework, using Local SGD case study.
In Section G.2, we prove that our version of Local SGD yields the total time complexity
(--2))
LA +
LA
o²
LA
(36)
n
We now illustrate that this result is provably better than the best theoretical result for the canonical version of Local SGD (Algorithm 20) known
Algorithm 20 Local SGD (FedAvg) (McMahan al., 2017)
Require: initial model z0 step size y, # of local steps K 1: for k == 0, 2..... do
2: Broadcast * to all workers
3: for each worker i [1,...,mn] n) in parallel do
4: k.0
x
5: for O,... K do k.j
6:
2,
*J++1
zi
7 f( kJ kJ)
7:
end for
8:
end for x k++
1 K.K
9:
end for
To the best of our knowledge, the state-of-the-are analysis of Algorithm 20 in the nonconvex setting provided by Koloskova et al. (2020); Luo et al. (2025). Under Assumptions 1.1, 1.2, and 1.3, with proper 7, they establish the slate-of-the-e iteration complexity
θ LA
Lo
A
LoA
E
nK
K1/2ga/2
57

---

Published as a conference paper at ICLR 2026
for finding an e-staionnary point for all K 2 1. Next, under (h, r)-fixed computation model, this iteration complexity yields the time complexity
(
LA
Lo 2Kg²
A
Lod
LA E
Lo nK
Lo Kàg
T:
hk
Kšo
(up to constant factors) because in each iteration the workers communicate, which takes T seconds, and each worker (in parallel) computes K stochastic gradients, which takes h x K seconds. Ignoring non-negative terms,
LA
LoA
KLA 8
Lo n
Lo c
T P
+h
Kig
and T is lower bounded by
L'00 23
LA
LA
o²
LA
Th
+ h
(37)
ng?
for all K 2 1 due to the AM-GM inequality. Notice that (36) S (37). However, (37) can be arbitrarily
larger due the first term. Indeed, for sufficiently large n, we have
(
LA
LA
(36) θ
TT
+
h
while
(
LA
LA
(37) -
Note that the latter expression has 1/23/2 dependency, whereas our result has a 1/2 dependency, Thus, our result provably tighter.
Note that we obtain the time complexity (36) for several other new methods, including Async-Local SGD, Async-Batee Batch SGD, and Dual-Process SGD.
I TOTAL TIME COMPLEXITIES OF ALGORITTMS UNDER (hi, -IXEE COMPUTATION MODEL
We now assume that each worker has its own communication time bound т; and computation time bound h; and consider the (h;, Fii-fded computation model (Tyurin et al., 2024). It takes т; seconds to send vector from worker i to parameter server and seconds to send vector from the server to worker in the centralized setting. Alternatively, it takes r; seconds to send a vector to all other workers in the decentralized setting.
This setting reduces to hę-fixed computation model when T; = for all i E [n], and reduces to (h, -fiix computation model when h; h and T. = for all [n.] Without loss of generality, we assume that max (/1, 7 S ... S (h, }. Otherwise, the workers can be sorted according to these inequalities.
Notice that Rennala SGD, Local SGD, and Cycle SGD wait for the slowest worker by the designs. If ma T3 + oo, then their total complexity tends to Thus, they are suboptimal under the (h,, T.) -fxxed computation model. Ringmaster ASGD is suboptimal even under the ffixed computation model. Async-Local SGD and Async-Batch Batch SGD are optimal under the (h, fixeed computation model, but conjecture that they suboptimal under the (h, T;) ffxedd computation model.
We now prove that Dual-Process SGD is optimal under the (h,, Ti) ffxed computation model within the family of methods that communicate either with a server (centralized setting) or with each other (decentralized setting).
58

---

Published as a conference paper at ICLR 2026
1.1 Sual-Process SGD
Theorem I.1 (Dual-Process SGD), Consider Theorem E.11 and its conditions. Under the (hi, Ta rixxfxxed
computation model, the total time complexity of SGD (Alg. 18) is
LA
O min mEjD)
max
max naxx Fmnh
he
8
with B max
This complexity optimal for distributed methods without compression communicating with server (centralized setting) or with each other (decentralized setting) (Tyurin et al., 2024; Tyurin & Richtárik, 2024). Notice that is robust slow communications, Indeed, if Tn + oo, then this complexity will ignore worker due to the min operation.
mefr [n]
Lemma 1.2. Let us define
m
T(B) = min
max max Tail
(38)
mE(N]
h4
Under the (hi, TT)=-fxee computation model, the time required to calculate x² ..... x of the main branch is at most 3T(B) seconds, the time required to calculate B+1 seconds, and
2B is at most 3T (B)
Proof. Notice that
T(B) -4 max max Tm }.
Σ
B
for m² E [m]. The idea is similar in Lemmas F.2 and F.7. All workers caleulate stochastic gradients in parallel. For all 2 0, after seconds the first m workers can calculate at at least
Σ max
{
[ h.
1.0).
(39)
stochastic gradients, where we subtract 1 because at most one stochastic gradient can be ignored. Substituting (BB) into (39), we have
m
{ T(B)
m
T(B)
T(B)
Σ max
1,0
m
2m
h1g
14
h1g
i=1
Recall that max maxx(hi,7 m1 S ... I max feax Tm- }. Thus,
1
T(B) 2 2
Tm +
B > 2h +2
Σ
B
h4
h4
for all S m", and
Σ max
m
{
T(B)
1,0
Σ
m
+
2
m
B
2m 2 B.
h;
h
hr
Thus, by the time T(B), the first m workers can calculate stochastic gradients.
Next, need to estimate the communication time. It takes most maxie(m") T; S max Tm < T(B) seconds to receive vector from the server (in the decentralized set- ting, we do not account this time). Similarly, it takes at most max;g[m-] Ti S T(B) seconds to send a vector the server (in the decentralized setting, to send vector to other workers). Thus, one round in Alg 18 takes at most 3 x T(B) seconds, which is equivalent to calculating x² r'..... x the main branch. The same argument be applied to the next B point of the main branch, and
n
59

---

Published as a conference paper at ICLR 2026
Proof of Theorem 1.I. The proof is similar the proof of Lemma F.2. Due to Theorem E.2, we know
that # E K E [[VV((>*)] e for
4BLA
LA
K
8²
Using Lemma 1.2, the total time to find an E-stationary point
LA
LZLA
o T(B)
B -
((B) x
E
+
B
Using the choice of B,
K T(B)=
m
-1
0²
LA
o
0
min mE(")
max max Jmnh
h:
8
60

---

Published as a conference paper at ICLR 2026
J PERFORMANCE OF Rennala SGD AND Ringmaster ASGD ON A QUADRATIC FUNCTION
In this section, formally prove that the convergence of Ringmaster ASGD can be provably faster than Rennala SGD due to the frequent model updates.
Theorem J.1. Consider Rennala SGD (Alg. 4) and Ringmaster ASGD (Alg. 7) with the optimal parameters B from Sec. F. Then, there exists j-strongly convex function and corresponding stochastic gradients that satisfy Assumptions 1.1, 1.2, and 1.3 with e'/e 2 n, such that Rennala SGD, with any step size y, requires
L 11
x
h
seconds to find E-stationary point under the hi-fixed computation model (20) with h; = h for all i [n]. At the same time, there exists step size for Ringmaster ASGD such that it requires at most
L
h
1
seconds to find e-stationary point.
Proof. In this construction, we take f IR2 - such that
uzz Ly² 2
f(w (x. u))
(40)
for all x, y R. Moreover, we assume that the stochastic gradients V fw; {) are equal the true gradient V [w(); thus, there is no randomness. Note that priori, both methods do not have this information and therefore must choose = e even though the effective variance zero.
By the design of Rennala SGD, its algorithm is equivalent the following steps:
wh f+1 = w² - BBV f(w')
(41)
because the workers calculate B gradients in every global round. Each round takes
B n
0²
+
nE
seconds, because the workers have the computation speed and B - (a") in Theorem F.1.
It is well known that the sequence (41) requires
L
iterations (up logarithmic factors) find e-solution or e-stationary point with the function (40), even when the step size y can be tuned. Thus, the computational time complexity of Rennala SGD is
L
x h
11
seconds.
Consider now the steps of Ringmaster ASGD w.r.t. the first argument x. In this algorithm, we take 7 2mm In the case when the computation time is equal for all workers, the first n steps are
x² = 1.0 muoo - -
x² = x¹ -yuu (1 -2714)xx
ra n- ooci (1 ny)ux=
61

---

Published as a conference paper at ICLR 2026
because the workers start calculating the same point and return the gradients the same time. Notice that 0 I x² Σ ... Σ x² Σ x Then, the first worker starts calculating at x' the seconds worker starts calculating at æ², and so on. Therefore, the next steps
x r+ +1 x²" -uur
= =(1 1-17/))x0 7p(1 xu)== (1 (n 1)7/4 + )²²
x=+2 m= -ypa?
(1 (n 1)7l x2)2)00 7H(1 27 = = (1- (n 2)7/4 3)²22)=²
x x 2n-1 - -yux= -1 (1-20714+ + n(n + 1)
7 11
x - -yy)) x.
2
For = 1/2Ln, we have < an < ... < r+ S x S ... S x² < x² Using mathematical induction, assume that kkn .... x² for some
and x I (1 (1-nypl nyp)" x0 for all p k
which is true for k = 2 (base case). We now prove it for h + Ringmaster ASGD calculates Fn+1 as follows:
kn+1 wn ypu (h- 11)++1
which ensures that kn++1 < (1 - yu)a S kn and kn+1 2 (((-1))t1 7ux 2 for
7 1/2tm. We continue:
x knt2 knt1 qux (k- (1-
which ensures that
kn+z < kn-11 yaa kn < (1 7p)x quo 271)
and x An+2 > (k - 1)m+2 (h 1)+22 Continuing, we have
x (k+1)a = (k+1)m-1 yuat
One can show that
(k+1) I (1 (n - 1)yu)a - yukkk & (1 ny
and (1++1)m znn yuo 0. We have proved the next case, &o + 1, of the mathematical induction.
Thus, the sequence {2.m) 1p22 monotonically decreases with the rate
p S (1 - nnyp)) 20.
Using the same reasoning, function but with instead of μ..
show the similar result holds for the second argument of the
Recall that it takes h seconds to caleulate -d because workers work in parallel, it takes h seconds to calculate 2n and so on. Thus, the computational time complexity of Ringmaster ASGD
L
x
1
with step size
62


Reviews:
[{"review_id": "QVG9PA65HT", "reviewer": "Reviewer_sATR", "summary": "This paper presents a unified framework to frame, analyze, and design distributed SGD algorithm. Basically, the framework models any distributed SGD algorithm as a weighted directed tree. The convergence properties of the algorithm only rely on the geometric properties of the directed tree. The authors provide a unified analysis and discussed many concrete examples, including both old and new distributed SGD variants.", "questions": "1. From algorithm 1, it is hard to tell why local SGD can be treated as an instance of birch SGD. I did not see any part of the algorithm to handle the communication (ie averaging gradients or parameters).\n2. The convergence rate is established in terms of the main branch? If so, then K is not the gradient computation times as in previous literature. As shown in figure 10, the main branch only has 5 iterates but there are total 10 gradient computations.\n3. In table 1, why does local SGD listed as new? It is not a new algorithm.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- The idea of framing distributed SGD algorithms as a directed tree is very novel and interesting.\n- The unified convergence analysis is also solid and clean.", "weaknesses": "The writing is not super clear. From algorithm 1, it is hard to tell why local SGD can be treated as an instance of birch SGD. I did not see any part of the algorithm to handle the communication (ie averaging gradients or parameters).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kr9cZ7eEVN", "reviewer": "Reviewer_ZST5", "summary": "The paper proposes a unified theoretical framework for analyzing stochastic gradient based optimization method. The tree visualization is interesting. By using Lipschitz smoothness to bound how wrong the stale gradients can be the authors propose a unified analysis for convergence guarantees.", "questions": "What about non-iid data? Could we add a measure of heterogeneity in the analysis?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The unified framework provides a helpful tool to analyze many different implementations of SGD. The paper is clearly written with many helpful visualizations. The convergence guarantee theory is based on topology alone and seems quite powerful.", "weaknesses": "How tight is Theorem 2.4? It would be interesting to include some numerical experiment where R grows over time and show that it fails. Or include some correlated noise. I suspect that would be less harmful.\n\nIt seems quite conservative to use the upper bound on R rather than an average distance. I suspect most of the proof will go through using average distance but changing to a weaker convergence guarantee (in expectation maybe). \n\nSome of the new methods (cycle SGD) was not tested in numerical studies. When they do get added, please also include the total time, as some of them need to keep track of/communicate additional meta data/information and might take time in distributed settings. Though this part could be tricky to simulate.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "32j6nbfGCY", "reviewer": "Reviewer_s9uQ", "summary": "The paper proposes a unified framework to represent various distributed SGD algorithms in the form of a computation tree. Each branch of the tree captures different versions of the model (potentially at different workers) and how they are updated with fresh or stale gradients. Some of the algorithms that are subsumed in the framework include local SGD, asynchronous SGD, and several other variants of these methods. The paper provides a unified analysis that matches previous results for these algorithms and sometimes gives improved analysis and optimal communication/computation complexity bounds.", "questions": "- In local SGD and its variants, gradients are aggregated using AllReduce to update all models. Where does this step appear in the computation graph? At first glance, each edge seems to represent a single stochastic gradient (per-sample or mini-batch) rather than an average of gradients from multiple workers. However, upon closer reading and examining Figure 4, it appears that edges can represent averages of multiple gradients computed at different model versions. Is the gradient variance (now reduced due to taking the average) captured by $\\eta$? How does the aggregation step of local SGD occur in the computation graph?\n\n- Related to the above question, where does the number of workers appear in the convergence bound? Which term(s) explicitly depend on the number of workers?\n\n- The framework subsumes asynchronous SGD and its variants. A crucial aspect affecting these algorithms and their analysis is gradient staleness—the mismatch between the model index at which the gradient is computed and the model updated using this gradient. I initially thought $R$ would capture a bound on this staleness, but I don't understand how it does this based on the distance metric dist(x,z) defined in the paper. Please clarify.\n\n- How does this paper relate to https://arxiv.org/abs/2207.03730? That paper also models local SGD variants using a computation graphs with edges representing stochastic gradient computations?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The elegance of the unified framework and analysis is a clear strength of this paper. Even if the bounds are not improved or new algorithms are not proposed, a unified representation is valuable for researchers working in this field to put algorithms in perspective.\n- The addition of experimental results to complement the theory is well appreciated. Since this is a theory-focused paper, I do not have high expectations about the size and scale of experimental results. Nevertheless, I appreciated that the authors included these comparisons.", "weaknesses": "- The paper introduces eight new local SGD methods. While presented as a strength, this seems excessive and might confuse system designers choosing an algorithm. The insights section doesn't clearly guide which method to use under different communication and computation constraints. The comparisons in Section 3 are somewhat informative but could be clearer. Can you identify specific regimes—such as (1) communication-delay-bounded, (2) compute-bounded, and (3) bandwidth-bounded—and recommend the best algorithm for each?\n\n- While the writing is generally clear, it needs improvement in organization and conciseness. I suggest spending more time explaining the computation graph structure, specifically how the number of workers $M$ relates to the tree branches. Currently, the paper gives minimal explanation of this aspect (see my question below) and jumps too quickly to theoretical results and new algorithm proposals.\n\n- The writing comes across as overselling and condescending. I recommend toning down some claims to avoid alienating readers. For example, \"virtually all local SGD algorithms\" sounds too strong—please clarify which algorithms are not covered. The paper frequently uses adjectives and superlatives that add little information.\n\n- The results apply only to homogeneous data distributions across workers and would not hold in heterogeneous data settings (like federated learning). I don't consider this a major weakness since the paper provides a valuable unified framework and analysis for the homogeneous setting. However, I would like the authors to clearly acknowledge this limitation and provide some ideas on whether and how the framework could be extended to heterogeneous data settings.\n\n- The literature review is mostly thorough but omits other papers that provide unified analyses of different SGD algorithms, such as https://arxiv.org/pdf/1808.07576, https://arxiv.org/abs/2007.07481, https://arxiv.org/abs/2011.02828, https://arxiv.org/abs/2207.03730. I suggest broadening the literature survey to cover more key papers in the field rather than limiting references to papers from a few selected authors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)