Birch SGD: A Tree Graph Framework for Local and Asynchronous SGD Methods

## Abstract

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 𝒪 ⁢ ( ( R + 1 ) ⁢ L ⁢ Δ / ε + σ 2 ⁢ L ⁢ Δ / ε 2 ) 𝒪 𝑅 1 𝐿 Δ 𝜀 superscript 𝜎 2 𝐿 Δ superscript 𝜀 2 \mathcal{O}\left(\nicefrac{{(R+1)L\Delta}}{{\varepsilon}}+\nicefrac{{\sigma^{2%
}L\Delta}}{{\varepsilon^{2}}}\right) caligraphic_O ( / start_ARG ( italic_R + 1 ) italic_L roman_Δ end_ARG start_ARG italic_ε end_ARG + / start_ARG italic_σ start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT italic_L roman_Δ end_ARG start_ARG italic_ε start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT end_ARG ) , where R 𝑅 R italic_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.

## 1 Introduction

Optimization is central to machine learning (ML), 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 and Monro,, 1951) and its adaptive variants (Adam, AdamW, etc) (Kingma and Ba,, 2015; Loshchilov and 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 of workers (e.g., CPUs, GPUs, servers) is important (Mayer and Jacobsen,, 2020; Kairouz et al.,, 2021; Douillard et al.,, 2023).

We consider distributed optimization problems with smooth nonconvex optimization functions:

$$ $\displaystyle\textstyle\min\limits_{x\in\mathbb{R}^{d}}f(x),$ (1) $$

In nonconvex settings, the goal is to find an $\varepsilon$–stationary point, meaning we want to find a random vector $\bar{x}$ such that
$\mathbb{E}\left[\|\nabla f(\bar{x})\|^{2}\right]\leq\varepsilon$ (Nemirovskij and Yudin,, 1983; Murty and Kabadi,, 1985). The function $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ satisfies the following standard assumptions:

###### Assumption 1.1 .

$f$ is differentiable and $L$–smooth: $\left\|\nabla f(x)-\nabla f(y)\right\|\leq L\left\|x-y\right\|$ $\forall x,y\in\mathbb{R}^{d}.$

###### Assumption 1.2 .

There exist $f^{*}\in\mathbb{R}$ such that $f(x)\geq f^{*}$ for all $x\in\mathbb{R}^{d}$.

We focus on problems where workers are limited to computing stochastic gradients. Each worker has access to unbiased stochastic gradients, denoted by $\nabla f(x;\xi)$, whose variance is bounded by $\sigma^{2}$. In the context of ML, this implies that all workers can access the same data, which is practical 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 or shared datasets (Goodfellow et al.,, 2016).

###### Assumption 1.3 .

For all $x\in\mathbb{R}^{d},$ stochastic gradients $\nabla f(x;\xi)$ are unbiased and $\sigma^{2}$-variance-bounded, i.e., ${\rm\mathbb{E}}_{\xi}[\nabla f(x;\xi)]=\nabla f(x)$ and
${\rm\mathbb{E}}_{\xi}[\|\nabla f(x;\xi)-\nabla f(x)\|^{2}]\leq\sigma^{2},$ where $\sigma^{2}\geq 0.$

###### Assumption 1.1 .

###### Assumption 1.2 .

###### Assumption 1.3 .

### 1.1 Related work

One worker and optimal oracle complexity. With a single worker, the most standard optimization method is the Vanilla SGD algorithm, which updates the iterate as
$w^{k+1}=w^{k}-\gamma\nabla f(w^{k};\eta^{k}),$ where $\{\eta^{k}\}$ are i.i.d., $w^{0}\in\mathbb{R}^{d}$ is a starting point, $\gamma$ is a step size, and $\Delta:=f(w^{0})-f^{*}.$ Arjevani et al., (2022); Carmon et al., (2020) showed that Vanilla SGD is *optimal* in terms of oracle complexity, which is given by
$\Theta\left(\nicefrac{{L\Delta}}{{\varepsilon}}+\nicefrac{{\sigma^{2}L\Delta}}
{{\varepsilon^{2}}}\right)$ for finding an $\varepsilon$-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 a 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), Picky SGD (Cohen et al.,, 2021), Rennala SGD (Tyurin and 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_{i}$-fixed computation model* (Mishchenko et al.,, 2022), where each worker $i$ needs at most $h_{i}$ 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 and Richtárik,, 2023) and Ringmaster ASGD(^1^11Asynchronous SGD with a key modification; see Alg.[7](https://arxiv.org/html/2505.09218v2#alg7).) (Maranjyan et al.,, 2025), both optimal under this and the more general *universal computation model* (Tyurin,, 2025) (see Section [A](https://arxiv.org/html/2505.09218v2#A1)). However, as we will discuss in more detail later, other factors come into play, such as communication complexity, support for AllReduce, 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

$\spadesuit$ New framework: Birch SGD (Section [2](https://arxiv.org/html/2505.09218v2#S2)). We propose Birch SGD, a unifying framework that captures virtually all 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](https://arxiv.org/html/2505.09218v2#S2.F1)). We develop a new theoretical result, Theorem [2.4](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem4), 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.

$\clubsuit$ Eight new methods (Table [1](https://arxiv.org/html/2505.09218v2#S3.T1) and Section [3](https://arxiv.org/html/2505.09218v2#S3)). 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 and Richtárik,, 2023). We compare all methods across several dimensions, including computational and communication complexity, AllReduce compatibility, peak bandwidth, and model update frequency. Our improvements: i) our 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 Dual-Process SGD, that, for the first time in the literature, achieve the optimal time complexities within this family; 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 Sync” mechanism to guarantee convergence rates and to temper overly chaotic synchronization. As a 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 [5](https://arxiv.org/html/2505.09218v2#S5)). We observe that there is no silver bullet—each method has its own advantages and disadvantages. Some methods update the iterates more frequently, making them more appealing in practice, while others prioritize communication efficiency, support AllReduce, or focus on different aspects. Through our new framework, we uncover insights that provide deeper intuition and a simpler perspective on asynchronous, local, and parallel optimization methods.

## 2 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 [1](https://arxiv.org/html/2505.09218v2#alg1).

Figure: Algorithm 1 Birch SGD framework
Refer to caption: extracted/6476381/Grabar_February_azure_1904_gtg.jpg

Let us explain it. Initially, any SGD method starts at some point $w^{0}\in\mathbb{R}^{d}$, computes a stochastic gradient at $w^{0}$, and then finds a new point $w^{1}=w^{0}-\gamma\nabla f(w^{0};\cdot),$ which is added to the set $V$ of computed points. In the next step, there are four options for choosing the subsequent point $w^{2}$: $w^{2}=w^{i}-\gamma\nabla f(w^{j};\cdot)$ for $i,j\in\{0,1\}.$ This process continues indefinitely, and the number of possible choices, and hence methods, grows exponentially (see an example in Figure [1](https://arxiv.org/html/2505.09218v2#S2.F1)).

Figure: Figure 1: A possible computation tree $G$ for SGD method after four steps and beyond.
Refer to caption: x1.png

Note that any instance of Algorithm [1](https://arxiv.org/html/2505.09218v2#alg1), after any steps, can be represented by a weighted directed tree $G=(V,E),$ called a *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 tree $G$ and analyze its structure to provide convergence guarantees for the corresponding SGD method. Intuitively, the structure of the tree, e.g., number of branches, length of branches, the tree distance between $w_{\textnormal{grad}}$ and $w_{\textnormal{base}}$ in Alg. [1](https://arxiv.org/html/2505.09218v2#alg1) when we calculate a new point should be related to the convergence speed of the method.

### 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 $\{x^{k}\}_{k\geq 0}$ a *main branch* if it forms a path in $G$ starting at the initial node $w^{0}\equiv x^{0}$. That is, for each $k\geq 0$, the node $x^{k+1}$ is a direct successor of $x^{k}$ in $G$. By the construction of tree $G,$ if $\{x^{k}\}_{k\geq 0}$ is a *main branch*, then for each $k\geq 0$ there exists a unique pair $(z^{k},\xi^{k}),$ where $z^{k}\in V$ and $\xi^{k}\sim\mathcal{D}_{\xi},$ such that $x^{k+1}=x^{k}-\gamma\nabla f(z^{k};\xi^{k}).$ The sequence $\{(z^{k},\xi^{k})\}_{k\geq 0}$, which generates the main branch $\{x^{k}\}_{k\geq 0}$, 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(^3^33A fitting analogy is the Git distributed version control system, which also has a central main branch.).

Let us consider an example. In Figure [1](https://arxiv.org/html/2505.09218v2#S2.F1), we can take a main branch $\{x^{k}\}_{k\geq 0}$ as follows:
$x^{0}=w^{0},x^{1}=w^{2},x^{2}=w^{3},x^{3}=w^{8},x^{4}=w^{9},x^{5}=w^{10}.$ Accordingly, the auxiliary sequence is given by $(z^{0},\xi^{0})=(w^{0},\eta^{0}),$ $(z^{1},\xi^{1})=(w^{1},\eta^{1}),$ $(z^{2},\xi^{2})=(w^{2},\eta^{2}),$ $(z^{3},\xi^{3})=(w^{4},\eta^{6}),$ $(z^{4},\xi^{4})=(w^{1},\eta^{3}).$ See Figure [2](https://arxiv.org/html/2505.09218v2#S2.F2).

Figure: Figure 2: Visualization.

Intuitively, the convergence rate should depend on the distance between $x^{k}$ and $z^{k}$. When these points are close (e.g., $x^{k}=z^{k}$), the stochastic gradient is computed near the update point, typically yielding descent on average. In contrast, if they are far apart, the gradient at $z^{k}$ may poorly approximate the local behavior of $f$ at $x^{k}$, 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,z\in V,$ the tree distance $\textnormal{dist}(y,z)$ between $y$ and $z$ is the maximum number of edges to the common closest ancestor of $y$ and $z$.

As an example, consider Figure [2](https://arxiv.org/html/2505.09218v2#S2.F2), where $\textnormal{dist}(w^{9},w^{4})=\max\{4,2\}=4,$ because the common ancestor is $w^{0},$ the number of edges from $w^{9}$ to $w^{0}$ is $4,$ and the number of edges from $w^{4}$ to $w^{0}$ is $2.$ It is left to define the *representation* of a point $y\in V.$

###### Definition 2.3 .

For all $y\in V,$ the representation $\textnormal{repr}(y)$ is the multiset of stochastic gradients applied to $w^{0}$ to get $y.$ In other words, there exist $\{(m^{1},\kappa^{1}),\dots,(m^{p},\kappa^{p})\}=:\textnormal{repr}(y)$ for some $p\geq 0$ such that $y=w^{0}-\gamma\sum_{j=1}^{p}\nabla f(m^{j},\kappa^{j}).$

We define the representation of points to understand how all points are related. An important relation that we need is that $\textnormal{repr}(x)\subseteq\textnormal{repr}(y),$ which essentially means that all stochastic gradients used to compute $x$ are also used to compute $y.$ For instance, in Figure [2](https://arxiv.org/html/2505.09218v2#S2.F2), $\textnormal{repr}(w^{9})=\{(w^{0},\eta^{0}),(w^{1},\eta^{1}),(w^{2},\eta^{2}),
(w^{4},\eta^{6})\}$ and $\textnormal{repr}(w^{4})=\{(w^{0},\eta^{0}),(w^{2},\eta^{2})\},$ which allows to track the path from from the starting point $w^{0}$ to $w^{9}$ and $w^{4},$ and show that $\textnormal{repr}(w^{4})\subseteq\textnormal{repr}(w^{9}).$

###### Theorem 2.4 (Main Theorem) .

Let Assumptions [1.1](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem1), [1.2](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem2), and [1.3](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem3) hold. Consider any SGD method represented by *computation tree* $G=(V,E)$. Let $\{x^{k}\}_{k\geq 0}$ be a *main branch* of $G$ and $\{(z^{k},\xi^{k})\}_{k\geq 0}$ be the corresponding *auxiliary sequence* (see Def. [2.1](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem1)) that satisfy the following conditions:
Condition 1: For all $k\geq 0,$ $\xi^{k}$ is statistically independent of
$\{(x^{i+1},z^{i+1},\xi^{i})\}_{i=0}^{k-1}.$
Condition 2: The representation of $z^{k}$ is contained within that of $x^{k}$, i.e.,
$\textstyle\textnormal{repr}(z^{k})\subseteq\textnormal{repr}(x^{k})$
for all $k\geq 0.$ Equivalently, all stochastic gradients used in the computation of $z^{k}$ are also utilized in calculating $x^{k}$.
Condition 3: There exists a constant $R\in[0,\infty]$ such that
$\textstyle\textnormal{dist}(x^{k},z^{k})\leq R$
for all $k\geq 0.$
Then $\frac{1}{K}\sum_{k=0}^{K-1}{\mathbb{E}}\left[\|\nabla f(x^{k})\|^{2}\right]\leq\varepsilon$ for all
$K\geq\frac{4(R+1)L\Delta}{\varepsilon}+\frac{8\sigma^{2}L\Delta}{\varepsilon^{
2}}$
with step size $\gamma=\min\{\frac{1}{2L},\frac{1}{2RL},\frac{\varepsilon}{4\sigma^{2}L}\}.$

Assumptions [1.1](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem1), [1.2](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem2), and [1.3](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem3) are well-known and standard in the analysis of stochastic optimization methods (Lan,, 2020; Arjevani et al.,, 2022). Let us explain the conditions of the theorem.

Condition 1. The first condition condition requires that $\xi^{k}$ is independent of $\{(x^{i+1},z^{i+1},\xi^{i})\}_{i=0}^{k-1},$ which is a weak assumption. In Vanilla SGD, where $x^{k+1}=x^{k}-\gamma\nabla f(x^{k};\xi^{k})$, it is standard to assume that each $\xi^{k}$ is an independent sample. Our condition generalizes this to other SGD variants. It guarantees that the stochastic gradient $\nabla f(\cdot;\xi^{k})$ is not used in computing $x^{k}$ or $z^{k}$. Notably, this remains true even in methods like Local SGD, where gradients may be reused.

Condition 2. The second condition is also weak in any *reasonable and effective* SGD method.

Figure: Figure 3: A general representation of the step $x^{k+1}=x^{k}-\gamma\nabla f(z^{k};\xi^{k})$ that shows how $x^{k}$ and $z^{k}$ are graph-geometrically related.
Refer to caption: x7.png

Figure [3](https://arxiv.org/html/2505.09218v2#S2.F3) illustrates that there exists $p\geq 0$ such that
$\textstyle z^{k}=x^{0}-{\color[rgb]{1,0.6015625,0.19921875}\definecolor[named]
{pgfstrokecolor}{rgb}{1,0.6015625,0.19921875}\gamma\sum\limits_{i=0}^{p-1}
\nabla f(z^{i};\xi^{i})}-{\color[rgb]{0.75390625,0.09765625,0.09765625}
\definecolor[named]{pgfstrokecolor}{rgb}{0.75390625,0.09765625,0.09765625}
\gamma\sum\limits_{(w,\xi)\in S^{k}}\nabla f(w;\xi)},x^{k}=x^{0}-{\color[rgb]{
1,0.6015625,0.19921875}\definecolor[named]{pgfstrokecolor}{rgb}{
1,0.6015625,0.19921875}\gamma\sum\limits_{i=0}^{p-1}\nabla f(z^{i};\xi^{i})}-{
\color[rgb]{0.09765625,0.09765625,0.75390625}\definecolor[named]{
pgfstrokecolor}{rgb}{0.09765625,0.09765625,0.75390625}\gamma\sum\limits_{i=p}^
{k-1}\nabla f(z^{i};\xi^{i})},$
where $S^{k}$ is the set of points and random variables used to compute $z^{k}$ starting from $x^{p}$.

Computing each stochastic gradient is time-consuming, so it is desirable to utilize as many computed gradients as possible, including $\{\nabla f(w;\xi)\}_{(w,\xi)\in S^{k}}$. Once $\nabla f(z^{k};\xi^{k})$ has been used to compute $x^{k+1}$, the first condition prevents further use of $\{\nabla f(w;\xi)\}_{(w,\xi)\in S^{k}}$ in subsequent iterations because $z^{k}$ depends on $\xi$ for all $(w,\xi)\in S^{k}.$ Thus, it is reasonable to assume that if an SGD method employs the stochastic gradient $\nabla f(z^{k};\xi^{k})$ to compute $x^{k+1}$, then it has already used the gradients $\{\nabla f(w;\xi)\}_{(w,\xi)\in S^{k}}$ in previous iterations to fully leverage all available information. In other words, all stochastic gradients used in the computation of $z^{k}$ are also utilized in calculating $x^{k}$.
This is equivalent to the second condition $\textnormal{repr}(z^{k})\subseteq\textnormal{repr}(x^{k}).$

Condition 3. This condition is arguably the most important in Theorem [2.4](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem4) because it determines the *iteration rate* of the main branch $\{x^{k}\}_{k\geq 0}$. In fact, *iteration rate*
$\mathcal{O}\left(\nicefrac{{(R+1)L\Delta}}{{\varepsilon}}+\nicefrac{{\sigma^{2
}L\Delta}}{{\varepsilon^{2}}}\right)$
depends on $R:=\sup_{k\geq 0}\textnormal{dist}(x^{k},z^{k}).$

Vanilla SGD (Section [E.1](https://arxiv.org/html/2505.09218v2#A5.SS1)).
For instance, consider the simplest method, the classical stochastic gradient descent (Vanilla SGD) method: $w^{k+1}=w^{k}-\gamma\nabla f(w^{k};\eta^{k}),$
where $w^{0}$ is a starting point and are $\{\eta^{k}\}$ are i.i.d. random variables. Taking $x^{k}=z^{k}=w^{k}$ and $\xi^{k}=\eta^{k}$ for all $k\geq 0.$ Clearly, all conditions of Theorem [2.4](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem4) are satisfied: $\xi^{k}$ is independent of $\{(x^{i+1},z^{i+1},\xi^{i})\}_{i=0}^{k-1},$ $\textnormal{repr}(x^{k})=\textnormal{repr}(z^{k})$ for all $k\geq 0,$ and $R=0.$ We get the *iteration rate* $\mathcal{O}\left(\nicefrac{{L\Delta}}{{\varepsilon}}+\nicefrac{{\sigma^{2}L
\Delta}}{{\varepsilon^{2}}}\right).$ The corresponding tree is in Figure [13](https://arxiv.org/html/2505.09218v2#A5.F13).

Conversely, if an SGD method is overly non-conservative, leading to a large tree distance $R$ between $x^{k}$ and $z^{k}$, the *iteration rate* correspondingly increases. The further the maximum tree distance $R$ between $x^{k}$ and $z^{k},$ the more iterations are required to achieve the desired accuracy $\varepsilon.$

###### Definition 2.1 ( Main Branch and Auxiliary Sequence ) .

###### Definition 2.2 .

###### Definition 2.3 .

###### Theorem 2.4 (Main Theorem) .

## 3 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](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem4). The detailed analysis of each method is provided in Section [E](https://arxiv.org/html/2505.09218v2#A5).

Rennala SGD (Section [E.2](https://arxiv.org/html/2505.09218v2#A5.SS2)).
Consider Rennala SGD, which can be written as

$$ $\displaystyle\textstyle w^{k+1}=w^{k}-\gamma\sum\limits_{i=1}^{B}\nabla f(w^{k };\eta^{k,i}),$ (2) $$

where $n$ workers collaboratively calculate the batch of size $B$ (see Alg. [4](https://arxiv.org/html/2505.09218v2#alg4)).
This method produces a computation tree constructed as follows:
$x^{1}=x^{0}-\gamma\nabla f(x^{0};\xi^{0}),\dots,x^{B}=x^{B-1}-\gamma\nabla f(x
^{0};\xi^{B-1}),x^{B+1}=x^{B}-\gamma\nabla f(x^{B};\xi^{B}),\dots,x^{2B}=x^{2B
-1}-\gamma\nabla f(x^{B};\xi^{2B-1}),\dots,$
where $B$ is a batch size (see Figure [14](https://arxiv.org/html/2505.09218v2#A5.F14)) and $\{\xi^{k}\}$ are i.i.d. from $\mathcal{D}_{\xi}.$ Notice that the computation tree is equivalent to ([2](https://arxiv.org/html/2505.09218v2#S3.E2)) because $x^{B}=w^{1},x^{2B}=w^{2},$ etc. Here, all conditions of Theorem [2.4](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem4) are satisfied for the main branch $\{x^{k}\}$ with the auxiliary sequence $\{(z^{k},\xi^{k})\}$ such that $z^{0}=\dots=z^{B-1}=x^{0},$ $z^{B}=\dots=z^{2B-1}=x^{B},$ etc, and $\xi^{0}=\eta^{0,0},\dots,\xi^{B-1}=\eta^{0,B-1},\xi^{B}=\eta^{1,0},$ etc. However, unlike Vanilla SGD, $R=B-1$ because $\textnormal{dist}(x^{0},z^{0})=0,\textnormal{dist}(x^{1},z^{1})=1,\dots,
\textnormal{dist}(x^{B-1},z^{B-1})=B-1,\textnormal{dist}(x^{B},z^{B})=0,$ etc. Thus, the *iteration rate* is $\mathcal{O}\left(\nicefrac{{BL\Delta}}{{\varepsilon}}+\nicefrac{{\sigma^{2}L
\Delta}}{{\varepsilon^{2}}}\right).$

Table: Table 1: Summary of distributed optimization methods from Sections [3](https://arxiv.org/html/2505.09218v2#S3) and [E](https://arxiv.org/html/2505.09218v2#A5). In this table, we compare methods across different metrics. A ✓ indicates a 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 [F](https://arxiv.org/html/2505.09218v2#A6) when deriving the metrics.

Ringmaster ASGD (Section [E.4](https://arxiv.org/html/2505.09218v2#A5.SS4)).
This an Asynchronous SGD method with the update rule

$$ $\displaystyle\textstyle w^{k+1}=w^{k}-\gamma\nabla f(w^{k-\delta^{k}};\eta^{k- \delta^{k}}_{i}),$ (3) $$

where $\delta^{k}$ is a delay such that $\delta^{k}\leq B-1,$ where $B\geq 1$ is a hyperparameter (see Alg. [7](https://arxiv.org/html/2505.09218v2#alg7)).
We take $x^{k}=w^{k}$ for all $k\geq 0.$ Thus, the corresponding auxiliary sequence is defined by $z^{k}=x^{k-\delta^{k}}\equiv w^{k-\delta^{k}}$ and $\xi^{k}=\eta^{k-\delta^{k}}_{i}$ for all $k\geq 0.$ Constructing the computation tree (Figure [15](https://arxiv.org/html/2505.09218v2#A5.F15)), we can show that the conditions of Theorem [2.4](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem4) hold with $R=\max_{k\geq 0}\delta^{k}\leq B-1$ and the *iteration rate* is $\mathcal{O}\left(\nicefrac{{BL\Delta}}{{\varepsilon}}+\nicefrac{{\sigma^{2}L
\Delta}}{{\varepsilon^{2}}}\right).$

Previously, we presented Rennala SGD and Ringmaster ASGD that can be analyzed using Theorem [2.4](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem4). 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 a method, and present new algorithms. The discussion here is summarized in Table [1](https://arxiv.org/html/2505.09218v2#S3.T1). Before we begin, it is important to note that the iteration complexity in Theorem [2.4](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem4) does not reflect the true wall-clock performance. Instead, it serves as an intermediate result used to derive the time complexities presented below.

1. Computational complexity. One way to compare the methods is to analyze their time complexity under the *$h_{i}$-fixed computation model* (see Sec. [1.1](https://arxiv.org/html/2505.09218v2#S1.SS1), [A](https://arxiv.org/html/2505.09218v2#A1), and [F](https://arxiv.org/html/2505.09218v2#A6)). With a proper choice of the corresponding parameters, i.e., $B=\max\{1,\lceil\nicefrac{{\sigma^{2}}}{{\varepsilon}}\rceil\}$, both Rennala SGD and Ringmaster ASGD are optimal in terms of wall-clock time with the time complexity
$\Theta(\min_{m\in[n]}[(\nicefrac{{1}}{{m}}\sum_{i=1}^{m}\nicefrac{{1}}{{h_{i}}
})^{-1}\left(\nicefrac{{L\Delta}}{{\varepsilon}}+\nicefrac{{\sigma^{2}L\Delta}
}{{m\varepsilon^{2}}}\right)])$
provided that communication times are negligible. In the worst-case scenario, on 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_{i}$-fixed computation model.

2. Number of model updates. At the same time, comparing ([3](https://arxiv.org/html/2505.09218v2#S3.E3)) and ([2](https://arxiv.org/html/2505.09218v2#S3.E2)) 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](https://arxiv.org/html/2505.09218v2#S3.E3)). 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:\mathbb{R}^{2}\to\mathbb{R}$ such that $f(x,y)=\mu x^{2}/2+Ly^{2}/2$ for all $x,y\in\mathbb{R}.$ For this function, we prove that Rennala SGD requires $\widetilde{\Theta}\left({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}
{rgb}{1,0,0}\nicefrac{{\sigma^{2}}}{{\varepsilon n}}}\times h\times\nicefrac{{
L}}{{\mu}}\right)$
seconds to achieve an $\varepsilon$–solution under the $h_{i}$-fixed computation model with $h_{i}=h$ for all $i\in[n]$, while Ringmaster ASGD needs $\widetilde{\Theta}\left(h\times\nicefrac{{L}}{{\mu}}\right),$ which is $\nicefrac{{\sigma^{2}}}{{\varepsilon n}}$ seconds less (see formal result in Section [I](https://arxiv.org/html/2505.09218v2#A9)). This is the first result showing that Ringmaster ASGD/Asynchronous SGD can be *strongly* better than Rennala SGD.

3. Communication complexity. Communication delays are a major bottleneck in real-world distributed systems. Thus, minimizing communication and synchronization overhead is crucial. Ringmaster ASGD is the least efficient in this regard, requiring frequent communication and lacking AllReduce support due to its highly asynchronous design (see Alg. [7](https://arxiv.org/html/2505.09218v2#alg7)). In a simple model where sending one stochastic gradient takes $\tau$ seconds and all workers have identical speed $h_{i}=h$, the time complexity of Ringmaster ASGD is
$\Omega\left(\tau\left(\nicefrac{{L\Delta}}{{\varepsilon}}+{\color[rgb]{1,0,0}
\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\nicefrac{{\sigma^{2}L\Delta}}{
{n\varepsilon^{2}}}}\right)+h\left(\nicefrac{{L\Delta}}{{\varepsilon}}+
\nicefrac{{\sigma^{2}L\Delta}}{{n\varepsilon^{2}}}\right)\right).$
In contrast, Rennala SGD achieves
$\mathcal{O}\left(\tau\times\nicefrac{{L\Delta}}{{\varepsilon}}+h\left(
\nicefrac{{L\Delta}}{{\varepsilon}}+\nicefrac{{\sigma^{2}L\Delta}}{{n
\varepsilon^{2}}}\right)\right),$
which is preferable when $\tau$ and $\nicefrac{{\sigma^{2}}}{{\varepsilon}}$ are large (see Section [G](https://arxiv.org/html/2505.09218v2#A7)).

This is the point where we asked ourselves if it is possible to design a method that has the optimal computational time complexity of Rennala SGD and updates the iterates more frequently than it. It turns out this method is well-known and is called Local SGD:

Local SGD (Section [E.3](https://arxiv.org/html/2505.09218v2#A5.SS3)).

Figure: Figure 4: An example of a Local SGD computation tree with $B=4$ and 2 workers, each performing local steps over 2 global steps. In first round, they calculate $M_{1}=2$ and $M_{2}=2$ local steps. In the second round, they calculate $M_{1}=1$ and $M_{2}=3$ local steps. Note that the maximum distances $\textnormal{dist}(x^{3},z_{1}^{0,1})$ and $\textnormal{dist}(x^{7},z_{2}^{1,2})$, when applying $\nabla f(z_{1}^{0,1};\eta^{0,1}_{1})$ to $x^{3}$ and $\nabla f(z_{2}^{1,2};\eta_{2}^{1,2})$ to $x^{7}$, are equal to $B-1=\sum_{i=1}^{n}M_{i}-1=3$. Notice that each stochastic gradient is used $2$ times in the tree.
Refer to caption: x8.png

We consider the classical Local SGD strategy, where each worker $i\in[n]$ performs $M_{i}$ local steps, after which the server aggregates the results (see Alg. [5](https://arxiv.org/html/2505.09218v2#alg5)). Unlike most previous approaches, however, the number of local steps ${M_{i}}$ may vary across workers. Moreover, the server waits for a specific condition before aggregating: $\sum_{i=1}^{n}M_{i}=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 $\sum_{i=1}^{n}M_{i}=B,$ where $B$ is a hyperparameter. An example of the computation tree is shown in Figure [4](https://arxiv.org/html/2505.09218v2#S3.F4).

In Section [E.3](https://arxiv.org/html/2505.09218v2#A5.SS3), we establish the *iteration rate* of Local SGD as $\mathcal{O}\left(\nicefrac{{BL\Delta}}{{\varepsilon}}+\nicefrac{{\sigma^{2}L
\Delta}}{{\varepsilon^{2}}}\right)$. This result follows directly from Theorem [2.4](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem4) via a simple geometric argument. In fact, looking at Figure [4](https://arxiv.org/html/2505.09218v2#S3.F4) reveals that all the conditions of Theorem [2.4](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem4) are satisfied. The only minor difficulty is to show that $R:=\sup_{k\geq 0}\textnormal{dist}(x^{k},z^{k})\leq B-1,$ which is guaranteed by the condition $\sum_{i=1}^{n}M_{i}=B.$

What is novel in our version of Local SGD is the stopping condition and the choice of $B$, which together ensure the optimality of Local SGD under the $h_{i}$-fixed computation model (see Thm. [F.6](https://arxiv.org/html/2505.09218v2#A6.Thmtheorem6)).

Async-Local SGD (Section [E.6](https://arxiv.org/html/2505.09218v2#A5.SS6)). Another idea to 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 to 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](https://arxiv.org/html/2505.09218v2#S3.F5)). We formalize this algorithm and prove the iteration rate in Section [E.6](https://arxiv.org/html/2505.09218v2#A5.SS6). Moreover, in Sections [F](https://arxiv.org/html/2505.09218v2#A6) and [G](https://arxiv.org/html/2505.09218v2#A7), we suggest an optimal choice of parameters that leads to optimal computational complexity and reduced communication complexity, which is better than that of Ringmaster ASGD. We get as similar result with a new method, Async-Batch SGD (Section [E.7](https://arxiv.org/html/2505.09218v2#A5.SS7)).

Figure: 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^{0}\rightarrow z^{1,1}_{2}\rightarrow z^{1,2}_{2}$, the first worker already completes two rounds of local updates and sends the corresponding stochastic gradients, $(\nabla f(x^{0};\eta^{1,0}_{1}),\nabla f(z^{1,1}_{1};\eta^{1,1}_{1}))$ and $(\nabla f(x^{2};\eta^{2,0}_{1}),\nabla f(z^{2,1}_{1};\eta^{2,1}_{1}))$.
Refer to caption: x9.png

Dual-Process SGD (Section [E.11](https://arxiv.org/html/2505.09218v2#A5.SS11)). We took a step further and developed a 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 heterogeneous time setting, where workers have varying computation and communication times (see Section [H](https://arxiv.org/html/2505.09218v2#A8)). However, unlike Local SGD, it is not AllReduce-friendly.

4. Peak bandwidth. Another critical factor is the peak bandwidth. The number of workers the parameter-server or the AllReduce operation can synchronize may be limited when the number of workers $n$ is huge. Notice that the worst-case peak bandwidth of Rennala SGD, Ringmaster ASGD, Local SGD, and Async-Local SGD is $\Theta\left(n\right).$

Cycle SGD (Section [E.5](https://arxiv.org/html/2505.09218v2#A5.SS5)). 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 $\{\nabla f(z^{0}_{i};\eta^{0}_{i})\}$, only the first group of $s$ workers sends their gradients to the server, where $s$ is a hyperparameter. The server then aggregates these gradients and performs the update $w^{1}=w^{0}-\gamma\sum_{i=1}^{s}\nabla f(z^{0}_{i};\eta^{0}_{i}).$
Meanwhile, the first $s$ workers begin computing their local steps starting from $w^{1}$, while the remaining workers continue their current local computations. Subsequently, the second group of $s$ workers sends their locally computed vectors, and this process continues in a circular manner. A computation tree presented in Figure [16](https://arxiv.org/html/2505.09218v2#A5.F16). In Section [E.5](https://arxiv.org/html/2505.09218v2#A5.SS5), we provide a formal descriptions and, using Theorem [2.4](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem4), prove that Cycle SGD converges after $\mathcal{O}\left(\nicefrac{{n^{2}L\Delta}}{{s\varepsilon}}+\nicefrac{{\sigma^{
2}L\Delta}}{{\varepsilon^{2}}}\right)$ iterations. The peak bandwidth of Cycle SGD is $\mathcal{O}\left(s\right)$ with $s=\min\left\{\max\{\lceil\nicefrac{{n^{2}\varepsilon}}{{\sigma^{2}}}\rceil,1\}
,n\right\},$ which is much smaller than $\Theta\left(n\right)$ when $\nicefrac{{\sigma^{2}}}{{\varepsilon}}\geq n.$

5. Optimization with clusters. Consider a scenario with two or more clusters of workers, where intra-cluster communication (e.g., InfiniBand) is fast, but inter-cluster communication (e.g., Ethernet) is slow.

Local-Async SGD (Section [E.8](https://arxiv.org/html/2505.09218v2#A5.SS8)) We run Asynchronous SGD within each cluster and synchronize clusters after a fixed number of local steps. This setup is feasible due to fast intra-cluster links, while slower inter-cluster links necessitate infrequent synchronization. In Section [E.8](https://arxiv.org/html/2505.09218v2#A5.SS8), we formalize this method, Local-Async SGD, and establish its iteration rate. Section [F](https://arxiv.org/html/2505.09218v2#A6) proves it achieves optimal computational time complexity. A key novelty lies in the synchronization mechanism (see Alg. [12](https://arxiv.org/html/2505.09218v2#alg12)).

Nested Local-Async SGD (Section [E.9](https://arxiv.org/html/2505.09218v2#A5.SS9)) 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 a setup using classical optimization tools would be highly challenging. In contrast, our framework enables a straightforward analysis through geometric graph reasoning.

6. Flexible synchronization. We noticed that in all previous methods, the workers are synchronized in a predefined manner or rule.
We want to add more flexibility to the synchronization process.

Meta Local SGD (Section [E.10](https://arxiv.org/html/2505.09218v2#A5.SS10)). 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 a computation tree with a large $R$ if the selected strategy is not chosen carefully. To ensure that $R$ is bounded, in our meta-algorithm (Algorithm [16](https://arxiv.org/html/2505.09218v2#alg16)), we track the current distances $\{d_{i}\}$ to the head of the main branch and the local steps $\{M_{i}\}$ performed by each worker. Then, by tracking the value $d_{i}+\sum_{i=1}^{n}M_{i}$ for all $i\in[n]$ and comparing it to a parameter $B$, we compulsorily synchronize (Hard Sync) all workers for which $d_{i}+\sum_{i=1}^{n}M_{i}=B$. This way, we can ensure that the maximum distance $R$ is bounded by $B$, and the iteration rate of this method is $\mathcal{O}\left(\nicefrac{{BL\Delta}}{{\varepsilon}}+\nicefrac{{\sigma^{2}L
\Delta}}{{\varepsilon^{2}}}\right)$. See details in Section [E.10](https://arxiv.org/html/2505.09218v2#A5.SS10).

## 4 Summary of experimental results

In Section [C](https://arxiv.org/html/2505.09218v2#A3), we provide a detailed comparison of methods on logistic regression, image classification with ResNet18 (He et al.,, 2016), and next-token prediction with GPT2 (Radford et al.,, 2019). When communication times are negligible (Fig. [7](https://arxiv.org/html/2505.09218v2#S4.F7)), as expected from Table [1](https://arxiv.org/html/2505.09218v2#S3.T1) and the previous discussion, Ringmaster ASGD and Async-Local SGD converge faster on the logistic regression problem. However, when communication times are large (Fig. [7](https://arxiv.org/html/2505.09218v2#S4.F7)), Ringmaster 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 Async-Local SGD performs well due to its effective balance between frequent updates and local steps.
Figure 6: Computation times $h_{i}=1$ or $10$ randomly, communication times $\tau_{i}=0.$
Figure 7: Computation times $h_{i}=10$, communication times $\tau_{i}=100.$

## 5 Insights, Guidelines, and Conclusion

All proposed methods share the same iteration rate of $\mathcal{O}\left(\nicefrac{{(R+1)L\Delta}}{{\varepsilon}}+\nicefrac{{\sigma^{2
}L\Delta}}{{\varepsilon^{2}}}\right),$ where $R$ is controlled by a method-specific hyperparameter and, at the same time, $R$ is the largest tree distance between $x^{k}$ and $z^{k}$. For Rennala SGD, $R=B-1,$ where $B$ denotes the batch size; for Ringmaster ASGD, $R=B-1,$ where $B$ is the delay threshold; for Local SGD, $R=B-1,$ where $B$ corresponds to the number of local steps; for Cycle SGD, $R=\nicefrac{{n^{2}}}{{s}},$ 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=\Theta\left(\nicefrac{{\sigma^{2}}}{{\varepsilon}}\right)$ (see Sections [G](https://arxiv.org/html/2505.09218v2#A7) and [F](https://arxiv.org/html/2505.09218v2#A6)). We believe this is a fundamental principle underlying all parallel optimization methods, and it should be considered a guiding rule when developing new algorithms. This choice is also theoretically justified: by taking $R=\Theta\left(\nicefrac{{\sigma^{2}}}{{\varepsilon}}\right)$, the iteration rate does not change asymptotically: $\mathcal{O}\left(\nicefrac{{(R+1)L\Delta}}{{\varepsilon}}+\nicefrac{{\sigma^{2
}L\Delta}}{{\varepsilon^{2}}}\right)=\mathcal{O}\left(\nicefrac{{L\Delta}}{{
\varepsilon}}+\nicefrac{{\sigma^{2}L\Delta}}{{\varepsilon^{2}}}\right)$. Larger values of $R$ allow the methods to be more “parallel-friendly”. For instance, a large $R$ enables Ringmaster ASGD to consider stochastic gradients with larger delays, while a large $R$ in Local SGD allows the method to run more local steps. However, taking $R>\nicefrac{{\sigma^{2}}}{{\varepsilon}}$ results in a worse iteration rate, suggesting that the corresponding method operates in an overly “anarchic” asynchronous regime, which may lead to performance degradation. Geometrically, the theory suggests that, to achieve good performance, the tree distance between $x^{k}$ and $z^{k}$ in Figure [3](https://arxiv.org/html/2505.09218v2#S2.F3) should not exceed $\nicefrac{{\sigma^{2}}}{{\varepsilon}}$.

Notice that there is no single “best” method in Table [1](https://arxiv.org/html/2505.09218v2#S3.T1), 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.

We hope these important observations will support the future development and analysis of asynchronous optimization 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](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem4). By reducing the analysis and design of these methods to computation trees, our entire development becomes purely graph-geometrical, offering a new and simpler view on asynchronous optimization methods.

## References

- Arjevani et al., (2022)
Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., and Woodworth, B. (2022).
Lower bounds for non-convex stochastic optimization.
Mathematical Programming, pages 1–50.
- Bottou et al., (2018)
Bottou, L., Curtis, F. E., and Nocedal, J. (2018).
Optimization methods for large-scale machine learning.
SIAM review, 60(2):223–311.
- Carmon et al., (2020)
Carmon, Y., Duchi, J. C., Hinder, O., and Sidford, A. (2020).
Lower bounds for finding stationary points i.
Mathematical Programming, 184(1):71–120.
- Cohen et al., (2021)
Cohen, A., Daniely, A., Drori, Y., Koren, T., and Schain, M. (2021).
Asynchronous stochastic optimization robust to arbitrary delays.
Advances in Neural Information Processing Systems, 34:9024–9035.
- Douillard et al., (2023)
Douillard, A., Feng, Q., Rusu, A. A., Chhaparia, R., Donchev, Y., Kuncoro, A., Ranzato, M., Szlam, A., and Shen, J. (2023).
Diloco: Distributed low-communication training of language models.
arXiv preprint arXiv:2311.08105.
- Feyzmahdavian et al., (2016)
Feyzmahdavian, H. R., Aytekin, A., and Johansson, M. (2016).
An asynchronous mini-batch algorithm for regularized stochastic optimization.
IEEE Transactions on Automatic Control, 61(12):3740–3754.
- Goodfellow et al., (2016)
Goodfellow, I., Bengio, Y., Courville, A., and Bengio, Y. (2016).
Deep learning, volume 1.
MIT Press.
- He et al., (2016)
He, K., Zhang, X., Ren, S., and Sun, J. (2016).
Deep residual learning for image recognition.
In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770–778.
- Islamov et al., (2024)
Islamov, R., Safaryan, M., and Alistarh, D. (2024).
AsGrad: A sharp unified analysis of asynchronous-SGD algorithms.
In International Conference on Artificial Intelligence and Statistics, pages 649–657. PMLR.
- Kairouz et al., (2021)
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al. (2021).
Advances and open problems in federated learning.
Foundations and Trends® in Machine Learning, 14(1–2):1–210.
- Kingma and Ba, (2015)
Kingma, D. P. and Ba, J. (2015).
Adam: A method for stochastic optimization.
In International Conference on Learning Representations.
- Koloskova et al., (2022)
Koloskova, A., Stich, S. U., and Jaggi, M. (2022).
Sharper convergence guarantees for Asynchronous SGD for distributed and federated learning.
Advances in Neural Information Processing Systems, 35:17202–17215.
- Konečný et al., (2016)
Konečný, J., McMahan, H. B., Yu, F. X., Richtárik, P., Suresh, A. T., and Bacon, D. (2016).
Federated learning: Strategies for improving communication efficiency.
arXiv preprint arXiv:1610.05492.
- Krizhevsky et al., (2009)
Krizhevsky, A., Hinton, G., et al. (2009).
Learning multiple layers of features from tiny images.
Technical report, University of Toronto, Toronto.
- Lan, (2020)
Lan, G. (2020).
First-order and stochastic optimization methods for machine learning.
Springer.
- LeCun et al., (2010)
LeCun, Y., Cortes, C., and Burges, C. (2010).
MNIST handwritten digit database.
ATT Labs [Online]. Available: http://yann.lecun.com/exdb/mnist, 2.
- Lian et al., (2015)
Lian, X., Huang, Y., Li, Y., and Liu, J. (2015).
Asynchronous parallel stochastic gradient for nonconvex optimization.
Advances in Neural Information Processing Systems, 28.
- Loshchilov and Hutter, (2019)
Loshchilov, I. and Hutter, F. (2019).
Decoupled weight decay regularization.
In International Conference on Learning Representations.
- Maranjyan et al., (2025)
Maranjyan, A., Tyurin, A., and Richtárik, P. (2025).
Ringmaster ASGD: The first asynchronous SGD with optimal time complexity.
In International Conference on Machine Learning. PMLR.
- Matloff, (2008)
Matloff, N. (2008).
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):1–33.
- Mayer and Jacobsen, (2020)
Mayer, R. and Jacobsen, H.-A. (2020).
Scalable deep learning on distributed infrastructures: Challenges, techniques, and tools.
ACM Computing Surveys (CSUR), 53(1):1–37.
- Merity et al., (2016)
Merity, S., Xiong, C., Bradbury, J., and Socher, R. (2016).
Pointer sentinel mixture models.
arXiv preprint arXiv:1609.07843.
- Mishchenko et al., (2022)
Mishchenko, K., Bach, F., Even, M., and Woodworth, B. (2022).
Asynchronous SGD beats minibatch SGD under arbitrary delays.
Advances in Neural Information Processing Systems.
- Murty and Kabadi, (1985)
Murty, K. G. and Kabadi, S. N. (1985).
Some NP-complete problems in quadratic and nonlinear programming.
Technical report.
- Nemirovskij and Yudin, (1983)
Nemirovskij, A. S. and Yudin, D. B. (1983).
Problem complexity and method efficiency in optimization.
- Radford et al., (2019)
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I., et al. (2019).
Language models are unsupervised multitask learners.
OpenAI blog, 1(8):9.
- Recht et al., (2011)
Recht, B., Re, C., Wright, S., and Niu, F. (2011).
Hogwild!: A lock-free approach to parallelizing stochastic gradient descent.
Advances in Neural Information Processing Systems, 24.
- Robbins and Monro, (1951)
Robbins, H. and Monro, S. (1951).
A stochastic approximation method.
The Annals of Mathematical Statistics, pages 400–407.
- Schmidt et al., (2021)
Schmidt, R. M., Schneider, F., and Hennig, P. (2021).
Descending through a crowded valley-benchmarking deep learning optimizers.
In International Conference on Machine Learning, pages 9367–9376. PMLR.
- Sra et al., (2016)
Sra, S., Yu, A. W., Li, M., and Smola, A. (2016).
Adadelay: Delay adaptive distributed stochastic optimization.
In Artificial Intelligence and Statistics, pages 957–965. PMLR.
- Stich, (2019)
Stich, S. U. (2019).
Local SGD converges fast and communicates little.
In International Conference on Learning Representations.
- Stich and Karimireddy, (2020)
Stich, S. U. and Karimireddy, S. P. (2020).
The error-feedback framework: SGD with delayed gradients.
Journal of Machine Learning Research, 21(237):1–36.
- Tyurin, (2025)
Tyurin, A. (2025).
Tight time complexities in parallel stochastic optimization with arbitrary computation dynamics.
In International Conference on Learning Representations.
- Tyurin et al., (2024)
Tyurin, A., Pozzi, M., Ilin, I., and Richtárik, P. (2024).
Shadowheart SGD: Distributed asynchronous SGD with optimal time complexity under arbitrary computation and communication heterogeneity.
Advances in Neural Information Processing Systems, 37.
- Tyurin and Richtárik, (2023)
Tyurin, A. and Richtárik, P. (2023).
Optimal time complexities of parallel stochastic optimization methods under a fixed computation model.
Advances in Neural Information Processing Systems, 36.
- Tyurin and Richtárik, (2024)
Tyurin, A. and Richtárik, P. (2024).
On the optimal time complexities in decentralized stochastic asynchronous optimization.
Advances in Neural Information Processing Systems, 37.
- Wu et al., (2022)
Wu, X., Magnusson, S., Feyzmahdavian, H. R., and Johansson, M. (2022).
Delay-adaptive step-sizes for asynchronous learning.
In International Conference on Machine Learning.
- Zinkevich et al., (2010)
Zinkevich, M., Weimer, M., Li, L., and Smola, A. (2010).
Parallelized stochastic gradient descent.
Advances in Neural Information Processing Systems, 23.

## Appendix A Additional Discussion

### A.1 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 et al., (2022) proposed using the *$h_{i}$-fixed computation model*. The idea is to assume that worker $i$ requires at most $h_{i}$ seconds to calculate one stochastic gradient for all $i\in[n]:=\{1,\dots,n\}$ (without loss of generality, $h_{1}\leq h_{2}\leq\dots\leq h_{n}$). The authors considered Synchronized SGD, an iterative process defined as $w^{k+1}=w^{k}-\frac{\gamma}{n}\sum_{i=1}^{n}\nabla f(w^{k};\eta^{k}_{i}),$
where each worker calculates one stochastic gradient, synchronize, and a parameter server aggregates them to update the iterate(^4^44Alternatively, there is no physical parameter server, and all workers perform an Allreduce.). Using the $h_{i}$-fixed computation model, it can be easily shown that Synchronized SGD converges after

$$ $\displaystyle\mathcal{O}\left(\max\limits_{i\in[n]}h_{i}\times\left(\frac{L \Delta}{\varepsilon}+\frac{\sigma^{2}L\Delta}{n\varepsilon^{2}}\right)\right)$ (4) $$

seconds, because the method waits for the slowest worker, whose time is $\max_{i\in[n]}h_{i}=h_{n}$.

Figure: Algorithm 2 Asynchronous SGD

Mishchenko et al., (2022); Koloskova et al., (2022) provided new analyses of Asynchronous SGD (see Algorithm [2](https://arxiv.org/html/2505.09218v2#alg2)) and Cohen et al., (2021) developed Picky SGD to show that this time complexity can be improved to

$$ $\textstyle\mathcal{O}\left(\left(\frac{1}{n}\sum\limits_{i=1}^{n}\frac{1}{h_{i }}\right)^{-1}\left(\frac{L\Delta}{\varepsilon}+\frac{\sigma^{2}L\Delta}{n \varepsilon^{2}}\right)\right),$ $$

where the dependence on $\{h_{i}\}$ is harmonic instead of being based on the maximum. It turns out that this complexity can be further improved(^5^55Note that $\min\limits_{m\in[n]}g(m)\leq g(n)$ for any function $g\,:\,\mathbb{N}\to\mathbb{R}$) to

$$ $\displaystyle\textstyle\Theta\left(\min\limits_{m\in[n]}\left[\left(\frac{1}{m }\sum\limits_{i=1}^{m}\frac{1}{h_{i}}\right)^{-1}\left(\frac{L\Delta}{ \varepsilon}+\frac{\sigma^{2}L\Delta}{m\varepsilon^{2}}\right)\right]\right),$ (5) $$

which is achieved by the Rennala SGD method (Tyurin and Richtárik,, 2023). Moreover, Tyurin and Richtárik, (2023) proved a matching lower bound demonstrating that both this complexity and Rennala SGD are optimal. Recently, Maranjyan et al., (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 even when computation times are arbitrary, time-varying, and random.

### 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 proposed, including Asynchronous SGD (Mishchenko et al.,, 2022; Koloskova et al.,, 2022), Asgrad (Islamov et al.,, 2024), PIAG (Wu et al.,, 2022), and Malenia SGD (Tyurin and Richtárik,, 2023). Notably, Tyurin and 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, including (Lian et al.,, 2015; Feyzmahdavian et al.,, 2016; Stich and 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 a result, their theoretical guarantees in terms of computational time complexity are weaker than those in (Cohen et al.,, 2021; Koloskova et al.,, 2022; Mishchenko et al.,, 2022; Tyurin and Richtárik,, 2023; Maranjyan et al.,, 2025), which do not rely on such assumptions.

## Appendix B Notations

$\mathbb{N}:=\{1,2,\dots\};$ $\left\|x\right\|$ is the output of the standard Euclidean norm for all $x\in\mathbb{R}^{d}$; $\left\langle x,y\right\rangle=\sum_{i=1}^{d}x_{i}y_{i}$ is the standard dot product; $g=\mathcal{O}(f):$ exist $C>0$ such that $g(z)\leq C\times f(z)$ for all $z\in\mathcal{Z};$ $g=\Omega(f):$ exist $C>0$ such that $g(z)\geq C\times f(z)$ for all $z\in\mathcal{Z};$ $g=\Theta(f):$ $g=\mathcal{O}(f)$ and $g=\Omega(f);$ $g=\widetilde{\Theta}(f):$ the same as $g=\Omega(f)$ but up to logarithmic factors; $a\vee b:=\max\{a,b\}.$

## Appendix 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:

$\bullet$ CPU Setup: Intel(R) Xeon(R) Gold 6348 CPU @ 2.60GHz 52 cores (for logistic regression experiments)

$\bullet$ GPU Setup: 2 $\times$ Nvidia A100 80 Gb, CPU: Intel(R) Xeon(R) Platinum 8358 CPU @ 2.60GHz 128 cores (for ResNet18 and GPT2 experiments)

The distributed environment is simulated with the help of Simpy. To compare the methods, we consider different computation and communication scenarios by taking different computation times $\{h_{i}\}$ and communication times $\{\tau_{i}\}$ 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 are drawn from a set of values specified in Section [C.5](https://arxiv.org/html/2505.09218v2#A3.SS5). We plot the convergence rates against the elapsed time.

We evaluate the convergence speeds of all algorithms in four regimes:

$\bullet$ *Classical*: $h_{i}=10$ and $\tau_{i}=0$ for all $i\in[n].$ All workers have the same computation times, and the communication times are ignored.

$\bullet$ *Slow Communications*: $h_{i}=10$ and $\tau_{i}=100$ for all $i\in[n].$ The communication takes time.

$\bullet$ *Heterogeneous Computations*: $h_{i}=$ random_choice($\{1,10\}$) and $\tau_{i}=0$ for all $i\in[n].$ All workers have the different computation times randomly sampled from the set $\{1,10\}.$

$\bullet$ *Heterogeneous Communications*: $h_{i}=10$ and $\tau_{i}=$ random_choice([1,100]) for all $i\in[n].$ All workers have the different communication times randomly sampled from the set $\{1,10\}.$

This setup allows us 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—logistic regression on the MNIST dataset LeCun et al., (2010). In this setting, we evaluate three different numbers of workers: $n\in\{16,64,256\}$. We use the standard linear model with the logistic loss.

Starting with $n=16$ workers, we perform a grid search over the parameters specified in Table [2](https://arxiv.org/html/2505.09218v2#A3.T2) across all four regimes. The corresponding results are shown in Figure [8](https://arxiv.org/html/2505.09218v2#A3.F8). In the *classical* setup (Figure [8(a)](https://arxiv.org/html/2505.09218v2#A3.F8.sf1)), 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 [8(b)](https://arxiv.org/html/2505.09218v2#A3.F8.sf2)), Rennala SGD, Local SGD, and Async-Local SGD perform better, as they aggregate local steps and reduce communication overhead. In contrast, Synchronized SGD and Ringmaster ASGD perform poorly due to excessive communication. In both the *heterogeneous computations* (Figure [8(c)](https://arxiv.org/html/2505.09218v2#A3.F8.sf3)) and *heterogeneous communications* (Figure [8(d)](https://arxiv.org/html/2505.09218v2#A3.F8.sf4)) 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.

For $n=64$ (grid search parameters in Table [3](https://arxiv.org/html/2505.09218v2#A3.T3), results shown in Figure [9](https://arxiv.org/html/2505.09218v2#A3.F9)) and $n=256$ (grid search parameters in Table [4](https://arxiv.org/html/2505.09218v2#A3.T4), results shown in Figure [10](https://arxiv.org/html/2505.09218v2#A3.F10)), we observe behavior similar to the $n=16$ case across all four regimes.

Figure: (a) *Classical* regime: $h_{i}=10$, $\tau_{i}=0$
Refer to caption: x12.png

Figure: (a) *Classical* regime: $h_{i}=10$, $\tau_{i}=0$
Refer to caption: x16.png

Figure: (a) *Classical* regime: $h_{i}=10$, $\tau_{i}=0$
Refer to caption: x20.png

### C.3 Experiments with ResNet18 and image classification

We test the algorithms on the CIFAR10 (Krizhevsky et al.,, 2009) image recognition task with the ResNet18 (He et al.,, 2016) deep neural network. For ResNet18, we similarly report the best convergence results from a grid search over the parameters listed in Table [6](https://arxiv.org/html/2505.09218v2#A3.T6), using a setup with $n=8$ workers. Results for all algorithms across the four regimes are presented in Figure [11](https://arxiv.org/html/2505.09218v2#A3.F11).

The conclusions largely mirror those from the logistic regression experiments, with a few additional observations. In the *classical* setup (Figure [11(a)](https://arxiv.org/html/2505.09218v2#A3.F11.sf1)), 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 [11(b)](https://arxiv.org/html/2505.09218v2#A3.F11.sf2)), the trends are consistent with those observed in the MNIST experiments: Ringmaster ASGD becomes slower, while methods that are less communication-intensive achieve better performance. In the *heterogeneous communications* (Figure [11(d)](https://arxiv.org/html/2505.09218v2#A3.F11.sf4)) regime, Async-Local SGD has the best performance due to the good balance of frequent model updates and local steps.

Figure: (a) *Classical* regime: $h_{i}=10$, $\tau_{i}=0$
Refer to caption: x24.png

### 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, we evaluate all four regimes using a setup with $n=8$ workers. To achieve faster and more robust convergence, we use the AdamW normalization strategy(^6^66Instead of the SGD step $w^{k+1}=w^{k}-\gamma g^{k},$ where $g^{k}$ is a descent direction, we use the AdamW strategy with $g^{k}$.) only in these experiments with GPT2. The resulting convergence curves are shown in Figure [12](https://arxiv.org/html/2505.09218v2#A3.F12). Once again, the results are similar to those of the previous experiments. Due to hardware limitations, a narrower grid search range is used; therefore, it is possible that convergence could be further improved with a more extensive search.

Figure: (a) *Classical* regime: $h_{i}=10$, $\tau_{i}=0$
Refer to caption: x28.png

### C.5 Parameters of the experiments

**Table 2: Experimental configuration for logistic regression on MNIST with $n=16$ workers.**
| Parameter | Value |
| --- | --- |
| Batch size | 1 |
| Optimizer | SGD |
| Number of workers | 16 |
| Algorithm-specific configurations: |  |
| Synchronized SGD | $\gamma$ range: $[2^{-5},2^{4}]$ |
| Rennala SGD | $\gamma$ range: $[2^{-15},2^{-3}]$ |
|  | B set: {128, 256, 512, 1024} |
| Local SGD | $\gamma$ range: $[2^{-15},2^{-3}]$ |
|  | B set: {128, 256, 512, 1024} |
| Ringmaster ASGD | $\gamma$ range: $[2^{-15},2^{1}]$ |
|  | B set: {128, 256, 512, 1024} |
| Async-Local SGD | $\gamma$ range: $[2^{-10},2^{1}]$ |
|  | B set: {64, 128, 256, 512, 1024} |
|  | M set: {1, 2, 4, 8} |

**Table 3: Experimental configuration for logistic regression on MNIST with $n=64$ workers.**
| Parameter | Value |
| --- | --- |
| Batch size | 1 |
| Optimizer | SGD |
| Number of workers | 64 |
| Algorithm-specific configurations: |  |
| Synchronized SGD | $\gamma$ range: $[2^{-5},2^{4}]$ |
| Rennala SGD | $\gamma$ range: $[2^{-15},2^{-3}]$ |
|  | B set: {1024, 2048, 4096} |
| Local SGD | $\gamma$ range: $[2^{-15},2^{-3}]$ |
|  | B set: {1024, 2048, 4096} |
| Ringmaster ASGD | $\gamma$ range: $[2^{-15},2^{1}]$ |
|  | B set: {512, 1024, 2048, 4096} |
| Async-Local SGD | $\gamma$ range: $[2^{-10},2^{1}]$ |
|  | B set: {64, 128, 256, 512, 1024, 4096} |
|  | M set: {1, 2, 4, 8} |

**Table 4: Experimental configuration for logistic regression on MNIST with $n=256$ workers.**
| Parameter | Value |
| --- | --- |
| Batch size | 1 |
| Optimizer | SGD |
| Number of workers | 256 |
| Algorithm-specific configurations: |  |
| Synchronized SGD | $\gamma$ range: $[2^{-5},2^{4}]$ |
| Rennala SGD | $\gamma$ range: $[2^{-15},2^{-3}]$ |
|  | B set: {1024, 2048, 4096, 8192, 16384} |
| Local SGD | $\gamma$ range: $[2^{-15},2^{-3}]$ |
|  | B set: {1024, 2048, 4096, 8192, 16384} |
| Ringmaster ASGD | $\gamma$ range: $[2^{-15},2^{1}]$ |
|  | B set: {512, 1024, 2048, 4096, 8192} |
| Async-Local SGD | $\gamma$ range: $[2^{-10},2^{1}]$ |
|  | B set: {128, 256, 512, 1024, 4096, 8192} |
|  | M set: {1, 2, 4, 8} |

**Table 5: Experimental configuration for ResNet18 with $n=8$ workers.**
| Parameter | Value |
| --- | --- |
| Batch size | 16 |
| Optimizer | SGD |
| Number of workers | 8 |
| Algorithm-specific configurations: |  |
| Synchronized SGD | $\gamma$ range: $[2^{-6},2^{-3}]$ |
| Rennala SGD | $\gamma$ range: $[2^{-6},2^{-3}]$ |
|  | B set: {16, 32, 64} |
| Local SGD | $\gamma$ range: $[2^{-6},2^{-3}]$ |
|  | B set: {16, 32, 64} |
| Ringmaster ASGD | $\gamma$ range: $[2^{-6},2^{-3}]$ |
|  | B set: {16, 32, 64} |
| Async-Local SGD | $\gamma$ range: $[2^{-6},2^{-3}]$ |
|  | B set: {16, 32, 64} |
|  | M set: {2, 4, 8} |

## Appendix D Proof of Theorem 2.4

See [2.4](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem4)

###### Proof.

As the beginning, the analysis is standard. Using Assumption [1.1](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem1), we have

$$ $\displaystyle f(x^{k+1})\leq f(x^{k})-\gamma\left\langle\nabla f(x^{k}),\nabla f (z^{k};\xi^{k})\right\rangle+\frac{L\gamma^{2}}{2}\left\|\nabla f(z^{k};\xi^{k })\right\|^{2}$ $$

for $x^{k+1}=x^{k}-\gamma\nabla f(z^{k};\xi^{k}).$ Due to Condition 1 of the theorem and the variance decomposition equality,

$$ $\displaystyle{\mathbb{E}}_{k}\left[f(x^{k+1})\right]\leq f(x^{k})-\gamma\left \langle\nabla f(x^{k}),\nabla f(z^{k})\right\rangle+\frac{L\gamma^{2}}{2}{ \mathbb{E}}_{k}\left[\left\|\nabla f(z^{k};\xi^{k})\right\|^{2}\right]$ $\displaystyle\quad=f(x^{k})-\gamma\left\langle\nabla f(x^{k}),\nabla f(z^{k}) \right\rangle+\frac{L\gamma^{2}}{2}\left\|\nabla f(z^{k})\right\|^{2}+\frac{L \gamma^{2}}{2}{\mathbb{E}}_{k}\left[\left\|\nabla f(z^{k};\xi^{k})-\nabla f(z^ {k})\right\|^{2}\right]$ $\displaystyle\quad\leq f(x^{k})-\gamma\left\langle\nabla f(x^{k}),\nabla f(z^{ k})\right\rangle+\frac{L\gamma^{2}}{2}\left\|\nabla f(z^{k})\right\|^{2}+\frac {L\gamma^{2}\sigma^{2}}{2},$ $$

where ${\mathbb{E}}_{k}\left[\cdot\right]$ is the expectation conditioned on $(x^{k},z^{k}).$
In the last inequality, we use Assumption [1.3](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem3). Rewriting the dot product and using $\gamma\leq\frac{1}{2L}$, we obtain

$$ $\displaystyle{\mathbb{E}}_{k}\left[f(x^{k+1})\right]$ $\displaystyle\leq f(x^{k})-\frac{\gamma}{2}\left(\left\|\nabla f(x^{k})\right \|^{2}+\left\|\nabla f(z^{k})\right\|^{2}-\left\|\nabla f(x^{k})-\nabla f(z^{k })\right\|^{2}\right)+\frac{L\gamma^{2}}{2}\left\|\nabla f(z^{k})\right\|^{2}+ \frac{L\gamma^{2}\sigma^{2}}{2}$ $\displaystyle\leq f(x^{k})-\frac{\gamma}{2}\left\|\nabla f(x^{k})\right\|^{2}- \frac{\gamma}{4}\left\|\nabla f(z^{k})\right\|^{2}+\frac{\gamma}{2}\left\| \nabla f(x^{k})-\nabla f(z^{k})\right\|^{2}+\frac{L\gamma^{2}\sigma^{2}}{2}.$ (6) $$

In the rest of the proof, we focus on $\left\|\nabla f(x^{k})-\nabla f(z^{k})\right\|^{2}.$ Using Assumption [1.1](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem1), we obtain

$$ $\displaystyle\left\|\nabla f(x^{k})-\nabla f(z^{k})\right\|^{2}\leq L^{2}\left \|x^{k}-z^{k}\right\|^{2}.$ (7) $$

Notice that there exist $p\in\{0,\dots,k\}$ and the closest common ancestor $x^{p}$ such that

$$ $\displaystyle x^{k}=x^{p}-\gamma\sum_{i=p}^{k-1}\nabla f(z^{i};\xi^{i})=x^{0}- \gamma\sum_{i=0}^{p-1}\nabla f(z^{i};\xi^{i})-\gamma\sum_{i=p}^{k-1}\nabla f(z ^{i};\xi^{i})$ $$

and

$$ $\displaystyle z^{k}=x^{p}-\gamma\sum_{(w,\xi)\in S^{k}}\nabla f(w;\xi)=x^{0}- \gamma\sum_{i=0}^{p-1}\nabla f(z^{i};\xi^{i})-\gamma\sum_{(w,\xi)\in S^{k}} \nabla f(w;\xi),$ $$

where $S^{k}$ is the set of points and random variables used to compute $z^{k}$ starting from $x^{p}$ (see Figure [3](https://arxiv.org/html/2505.09218v2#S2.F3)). Moreover, due to Condition 3, we have $\textnormal{dist}(x^{k},z^{k})\leq\max\{k-p,\left|S^{k}\right|\}\leq R,$ meaning $p\geq k-R.$ In total,

$$ $\displaystyle k\geq p\geq k-R,$ (8) $$

which we use later. Condition 2 assumes

$$ $\displaystyle\textnormal{repr}(z^{k}):=\underbrace{\{(z^{i};\xi^{i})\}_{i=0}^{ p-1}}_{A}\uplus\underbrace{\{(w;\xi)\}_{(w,\xi)\in S^{k}}}_{C}$ $\displaystyle\subseteq\textnormal{repr}(x^{k}):=\underbrace{\{(z^{i};\xi^{i}) \}_{i=0}^{p-1}}_{A}\uplus\underbrace{\{(z^{i};\xi^{i})\}_{i=p}^{k-1}}_{B},$ $$

where $\uplus$ is the multiset union operation. Thus

$$ $\displaystyle\underbrace{\{(w;\xi)\}_{(w,\xi)\in S^{k}}}_{C}\subseteq \underbrace{\{(z^{i};\xi^{i})\}_{i=p}^{k-1}}_{B}$ $$

and

$$ $\displaystyle x^{k}-z^{k}=-\gamma\left(\sum_{i=p}^{k-1}\nabla f(z^{i};\xi^{i}) -\sum_{(w,\xi)\in S^{k}}\nabla f(w;\xi)\right)=-\gamma\sum_{j\in\bar{S}^{k}} \nabla f(z^{i};\xi^{i}),$ (9) $$

where $\bar{S}^{k}$ is a set such that $\bar{S}^{k}\subseteq\{p,\dots,k-1\}.$
Substituting ([9](https://arxiv.org/html/2505.09218v2#A4.E9)) to ([7](https://arxiv.org/html/2505.09218v2#A4.E7)),

$$ $\displaystyle\left\|\nabla f(x^{k})-\nabla f(z^{k})\right\|^{2}\leq L^{2} \gamma^{2}\left\|\sum_{j\in\bar{S}^{k}}\nabla f(z^{j};\xi^{j})\right\|^{2}.$ $$

Next, using Young’s inequality $\left\|x+y\right\|^{2}\leq 2\left\|x\right\|^{2}+2\left\|y\right\|^{2}$ for all $x,y\in\mathbb{R}^{d}$, we get

$$ $\displaystyle{\mathbb{E}}\left[\left\|\nabla f(x^{k})-\nabla f(z^{k})\right\|^ {2}\right]\leq 2L^{2}\gamma^{2}{\mathbb{E}}\left[\left\|\sum_{j\in\bar{S}^{k}} \nabla f(z^{j})\right\|^{2}\right]+2L^{2}\gamma^{2}{\mathbb{E}}\left[\left\| \sum_{j\in\bar{S}^{k}}(\nabla f(z^{j};\xi^{j})-\nabla f(z^{j}))\right\|^{2} \right].$ $$

Since $\xi^{j}$ is statistically independent of
$\{(x^{i+1},z^{i+1},\xi^{i})\}_{i=0}^{j-1}$
for all $j\in\bar{S}^{k}$ (Condition 1) and using Assumption [1.3](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem3),

$$ $\displaystyle{\mathbb{E}}\left[\left\|\nabla f(x^{k})-\nabla f(z^{k})\right\|^ {2}\right]$ $\displaystyle\leq 2L^{2}\gamma^{2}{\mathbb{E}}\left[\left\|\sum_{j\in\bar{S}^{ k}}\nabla f(z^{j})\right\|^{2}\right]+2L^{2}\gamma^{2}\left|\bar{S}^{k}\right| \sigma^{2}$ $\displaystyle\overset{\textnormal{Jensen's ineq.}}{\leq}2L^{2}\gamma^{2}\left| \bar{S}^{k}\right|\sum_{j\in\bar{S}^{k}}{\mathbb{E}}\left[\left\|\nabla f(z^{j })\right\|^{2}\right]+2L^{2}\gamma^{2}\left|\bar{S}^{k}\right|\sigma^{2}.$ $$

Due to $\bar{S}^{k}\subseteq\{p,\dots,k-1\}$ and ([8](https://arxiv.org/html/2505.09218v2#A4.E8)):

$$ $\displaystyle{\mathbb{E}}\left[\left\|\nabla f(x^{k})-\nabla f(z^{k})\right\|^ {2}\right]$ $\displaystyle\leq 2L^{2}\gamma^{2}R\sum_{j=k-R}^{k-1}{\mathbb{E}}\left[\left\| \nabla f(z^{j})\right\|^{2}\right]+2L^{2}\gamma^{2}R\sigma^{2}.$ $$

Substituting this inequality to ([6](https://arxiv.org/html/2505.09218v2#A4.E6)) and taking the full expectation, we obtain

$$ $\displaystyle{\mathbb{E}}\left[f(x^{k+1})\right]$ $\displaystyle\leq{\mathbb{E}}\left[f(x^{k})\right]-\frac{\gamma}{2}{\mathbb{E} }\left[\left\|\nabla f(x^{k})\right\|^{2}\right]-\frac{\gamma}{4}{\mathbb{E}} \left[\left\|\nabla f(z^{k})\right\|^{2}\right]+\frac{L\gamma^{2}\sigma^{2}}{2}$ $\displaystyle\quad+\frac{\gamma}{2}\left(2L^{2}\gamma^{2}R\sum_{j=k-R}^{k-1}{ \mathbb{E}}\left[\left\|\nabla f(z^{j})\right\|^{2}\right]+2L^{2}\gamma^{2}R \sigma^{2}\right)$ $\displaystyle\leq{\mathbb{E}}\left[f(x^{k})\right]-\frac{\gamma}{2}{\mathbb{E} }\left[\left\|\nabla f(x^{k})\right\|^{2}\right]-\frac{\gamma}{4}{\mathbb{E}} \left[\left\|\nabla f(z^{k})\right\|^{2}\right]+L\gamma^{2}\sigma^{2}$ $\displaystyle\quad+L^{2}\gamma^{3}R\sum_{j=k-R}^{k-1}{\mathbb{E}}\left[\left\| \nabla f(z^{j})\right\|^{2}\right]$ (10) $$

because $\gamma\leq\frac{1}{2RL}.$ Note that $\sum_{k=0}^{K-1}\sum_{j=k-R}^{k-1}{\mathbb{E}}\left[\left\|\nabla f(z^{j})
\right\|^{2}\right]\leq R\sum_{k=0}^{K-1}{\mathbb{E}}\left[\left\|\nabla f(z^{
k})\right\|^{2}\right].$ Thus, summing ([10](https://arxiv.org/html/2505.09218v2#A4.E10)) for $k=0,\dots,K-1$ and substituting $f^{*},$

$$ $\displaystyle{\mathbb{E}}\left[f(x^{K-1})-f^{*}\right]$ $\displaystyle\leq f(x^{0})-f^{*}-\frac{\gamma}{2}\sum_{k=0}^{K-1}{\mathbb{E}} \left[\left\|\nabla f(x^{k})\right\|^{2}\right]-\frac{\gamma}{4}\sum_{k=0}^{K- 1}{\mathbb{E}}\left[\left\|\nabla f(z^{k})\right\|^{2}\right]+KL\gamma^{2} \sigma^{2}$ $\displaystyle\quad+L^{2}\gamma^{3}R^{2}\sum_{k=0}^{K-1}{\mathbb{E}}\left[\left \|\nabla f(z^{k})\right\|^{2}\right]$ $\displaystyle\leq f(x^{0})-f^{*}-\frac{\gamma}{2}\sum_{k=0}^{K-1}{\mathbb{E}} \left[\left\|\nabla f(x^{k})\right\|^{2}\right]+KL\gamma^{2}\sigma^{2}$ $$

because $\gamma\leq\frac{1}{2LR}.$ Finally, since ${\mathbb{E}}\left[f(x^{K-1})-f^{*}\right]\geq 0,$

$$ $\displaystyle\frac{1}{K}\sum_{k=0}^{K-1}{\mathbb{E}}\left[\left\|\nabla f(x^{k })\right\|^{2}\right]\leq\frac{2\Delta}{K\gamma}+2L\gamma\sigma^{2}.$ $$

It is left to use that $\gamma=\min\{\frac{1}{2L},\frac{1}{2RL},\frac{\varepsilon}{4\sigma^{2}L}\}$ and the bound on $K$ from the theorem statement.
∎

###### Proof.

## Appendix 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.1 Vanilla SGD

We start we the celebrated Vanilla SGD algorithm, which formally can be implemented in the following way:

Figure: Algorithm 3 Vanilla SGD

The corresponding computation tree can defined by the recursion

$$ $\displaystyle w^{k+1}=w^{k}-\gamma\nabla f(w^{k};\eta^{k})$ (11) $$

for all $k\geq 0.$

Figure: Figure 13: The computation tree of Vanilla SGD
Refer to caption: x32.png

While the iteration rate of Vanilla SGD is well-known (Lan,, 2020), we prove its convergence using our new framework for clarity.

###### Theorem E.1 .

Let Assumptions [1.1](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem1), [1.2](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem2), and [1.3](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem3) hold. Consider the computation tree ([11](https://arxiv.org/html/2505.09218v2#A5.E11)) of Vanilla SGD. Then, $\{x^{k}\}_{k\geq 0}$ is a main branch with $x^{k}=w^{k}$, $\{(z^{k},\xi^{k})\}_{k\geq 0}$ is the corresponding auxiliary sequence with $(z^{k},\xi^{k})=(w^{k},\eta^{k})$ (see Def. [2.1](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem1)), and $\frac{1}{K}\sum_{k=0}^{K-1}{\mathbb{E}}\left[\|\nabla f(x^{k})\|^{2}\right]\leq\varepsilon$ for all

$$ $K\geq\frac{4L\Delta}{\varepsilon}+\frac{8\sigma^{2}L\Delta}{\varepsilon^{2}}.$ $$

with step size $\gamma=\min\{\frac{1}{2L},\frac{\varepsilon}{4\sigma^{2}L}\}.$

###### Proof.

Indeed, $\{x^{k}\}_{k\geq 0}$ and $\{(z^{k},\xi^{k})\}_{k\geq 0}$ satisfy Def. [2.1](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem1) (see Fig. [13](https://arxiv.org/html/2505.09218v2#A5.F13)). Moreover, all conditions of Theorem [2.4](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem4) are fulfilled: Condition 1 holds because the sequence $\{\eta^{k}\}$ is i.i.d., we have $\textnormal{repr}(z^{k})=\textnormal{repr}(x^{k})$ since $x^{k}=z^{k}$, and consequently, $R=\sup_{k\geq 0}\textnormal{dist}(x^{k},z^{k})=0$.
∎

###### Theorem E.1 .

###### Proof.

### E.2 Rennala SGD

We now apply Theorem [2.4](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem4) to Rennala SGD. The iteration rate of Rennala SGD is also well-known (Tyurin and Richtárik,, 2023), but we provide a proof for completness. Rennala SGD can be formally described as follows:

Figure: Algorithm 4 Rennala SGD (Tyurin and Richtárik,, 2023)

To use Theorem [2.4](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem4), we have to construct the computation tree of Rennala SGD. It can be constructed in the following way:

$$ $\displaystyle x^{1}$ $\displaystyle=x^{0}-\gamma\nabla f(x^{0};\xi^{0}),\quad$ $\displaystyle\dots,\quad$ $\displaystyle x^{B}=x^{B-1}-\gamma\nabla f(x^{0};\xi^{B-1}),$ (12) $\displaystyle x^{B+1}$ $\displaystyle=x^{B}-\gamma\nabla f(x^{B};\xi^{B}),\quad$ $\displaystyle\dots,\quad$ $\displaystyle x^{2B}=x^{2B-1}-\gamma\nabla f(x^{B};\xi^{2B-1}),\quad\dots,$ $$

where $\{\xi^{i}\}$ are i.i.d. from $\mathcal{D}_{\xi}.$ See also a visualization in Figure [14](https://arxiv.org/html/2505.09218v2#A5.F14). One can easily show that $w^{1}=x^{0},w^{1}=x^{B},w^{2}=x^{2B},$ etc.

Figure: Figure 14: The computation tree of Rennala SGD
Refer to caption: x33.png

###### Theorem E.2 .

Let Assumptions [1.1](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem1), [1.2](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem2), and [1.3](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem3) hold. Consider the computation tree ([12](https://arxiv.org/html/2505.09218v2#A5.E12)) of Rennala SGD, then $\{x^{k}\}_{k\geq 0}$ is a main branch, $\{(z^{k},\xi^{k})\}_{k\geq 0}$ with $(z^{k},\xi^{k})=(x^{B\left\lfloor k/B\right\rfloor},\xi^{k})$ is the corresponding auxiliary sequence, and $\frac{1}{K}\sum_{k=0}^{K-1}{\mathbb{E}}\left[\|\nabla f(x^{k})\|^{2}\right]\leq\varepsilon$ for all

$$ $K\geq\frac{4BL\Delta}{\varepsilon}+\frac{8\sigma^{2}L\Delta}{\varepsilon^{2}}.$ $$

with step size $\gamma=\min\{\frac{1}{2BL},\frac{\varepsilon}{4\sigma^{2}L}\}.$

###### Proof.

Clearly, $\{x^{k}\}_{k\geq 0}$ is a main branch and $\{(z^{k},\xi^{k})\}_{k\geq 0}$ is the corresponding sequence by the construction in ([12](https://arxiv.org/html/2505.09218v2#A5.E12)). Moreover, $\xi^{k}$ is independent of $\{(x^{i+1},z^{i+1},\xi^{i})\}_{i=0}^{k-1}$ in ([12](https://arxiv.org/html/2505.09218v2#A5.E12)) because $\{\xi^{i}\}$ are i.i.d. (Condition 1 is satisfied). Next, notice that

$$ $\displaystyle\textnormal{repr}(z^{0})=\textnormal{repr}(x^{0})=\emptyset,$ $\displaystyle\textnormal{repr}(z^{1})=\textnormal{repr}(x^{0})=\emptyset \subseteq\textnormal{repr}(x^{1}),$ $\displaystyle\qquad\qquad\vdots$ $\displaystyle\textnormal{repr}(z^{B-1})=\textnormal{repr}(x^{0})=\emptyset \subseteq\textnormal{repr}(x^{B-1})$ $$

because $z^{k}=x^{0}$ for all $k<B.$ Next,

$$ $\displaystyle\textnormal{repr}(z^{B})=\textnormal{repr}(x^{B}),$ $\displaystyle\textnormal{repr}(z^{B+1})=\textnormal{repr}(x^{B})\subseteq \textnormal{repr}(x^{B+1}),$ $\displaystyle\quad\qquad\qquad\vdots$ $\displaystyle\textnormal{repr}(z^{2B-1})=\textnormal{repr}(x^{B})\subseteq \textnormal{repr}(x^{2B-1}),$ $$

because $z^{k}=x^{B}$ for all $B\leq k<2B,$ where $\textnormal{repr}(x^{B})\subseteq\textnormal{repr}(x^{B+1}),\dots,\textnormal{
repr}(x^{B})\subseteq\textnormal{repr}(x^{2B-1})$ due to ([12](https://arxiv.org/html/2505.09218v2#A5.E12)). We can continue and show that $\textnormal{repr}(z^{k})\subseteq\textnormal{repr}(x^{k})$ for all $k\geq 0$ (Condition 2 is satisfied). It is left to notice that

$$ $\displaystyle\sup_{k\geq 0}\textnormal{dist}(x^{k},z^{k})\leq B-1,$ $$

because

$$ $\displaystyle\textnormal{dist}(x^{0},z^{0})$ $\displaystyle=0,$ $\displaystyle\textnormal{dist}(x^{1},z^{1})=\textnormal{dist}(x^{1},x^{0})$ $\displaystyle=1,$ $\displaystyle\vdots$ $\displaystyle\textnormal{dist}(x^{B-1},z^{B-1})=\textnormal{dist}(x^{B-1},x^{0})$ $\displaystyle=B-1,$ $\displaystyle\textnormal{dist}(x^{B},z^{B})=\textnormal{dist}(x^{B},x^{B})$ $\displaystyle=0,$ $\displaystyle\textnormal{dist}(x^{B+1},z^{B+1})=\textnormal{dist}(x^{B+1},x^{B})$ $\displaystyle=1,$ $\displaystyle\vdots$ $$

The maximum tree distance between $x^{k}$ and $z^{k}$ is $B-1$. Thus, $R=B-1$ in Condition 3.
∎

###### Theorem E.2 .

###### Proof.

### E.3 Local SGD

The Local SGD method is described in the following algorithm:

Figure: Algorithm 5 Local SGD

Figure: Algorithm 6 LocalSGDWorker($w,\gamma$) in worker $i$ at round $k$

One key change compared to the previous work is that individual local steps $M_{i}$ are not predefined. Moreover, the server tracks the sum $\sum_{i=1}^{n}M_{i}$ and waits for the moment $\sum_{i=1}^{n}M_{i}=B$ before collecting the locally calculated gradients. With a proper choice of $B,$ we will prove the optimal computational time complexity of the method in Section [F](https://arxiv.org/html/2505.09218v2#A6).

The corresponding computation tree of Local SGD can be constructed in the following way. Define $N_{k}:=k\times B$ and take $k=0.$ Then

$$ $\displaystyle\begin{aligned} &z^{k,1}_{i}=z^{k,0}_{i}-\gamma\nabla f(x^{N_{k}} ;\eta^{k,0}_{i}),\\ &z^{k,2}_{i}=z^{k,1}_{i}-\gamma\nabla f(z^{k,1}_{i};\eta^{k,1}_{i}),\\ &\qquad\vdots\\ &z^{k,M_{i}}_{i}=z^{k,M_{i}-1}_{i}-\gamma\nabla f(z^{k,M_{i}-1}_{i};\eta^{k,M_ {i}-1}_{i}),\end{aligned}$ (13) $$

for all $i\in[n],$ and

$$ $\displaystyle\begin{aligned} x^{N_{k}+1}&=x^{N_{k}}-\gamma\nabla f(z^{k,0}_{1} ;\eta^{k,0}_{1}),\\ &\vdots\\ x^{N_{k}+M_{1}}&=x^{N_{k}+M_{1}-1}-\gamma\nabla f(z^{k,M_{1}-1}_{1};\eta^{k,M_ {1}-1}_{1}),\\ x^{N_{k}+M_{1}+1}&=x^{N_{k}+M_{1}}-\gamma\nabla f(z^{k,0}_{2};\eta^{k,0}_{2}), \\ &\vdots\\ x^{N_{k}+M_{1}+M_{2}}&=x^{N_{k}+M_{1}+M_{2}-1}-\gamma\nabla f(z^{k,M_{2}-1}_{2 };\eta^{k,M_{2}-1}_{2}),\\ &\vdots\\ x^{N_{k+1}}&=x^{N_{k}+\sum_{i=1}^{n}M_{i}-1}-\gamma\nabla f(z^{k,M_{n}-1}_{n}; \eta^{k,M_{n}-1}_{n}).\end{aligned}$ (14) $$

Repeat the previous steps with $k=k+1$ starting at $x^{N_{k+1}}=x^{N_{k}+B}.$ See illustration in Figure [4](https://arxiv.org/html/2505.09218v2#S3.F4). One can easily show that $w^{1}=x^{B},w^{2}=x^{2B},\dots,w^{k}=x^{kB},\dots,$ where $w^{k}$ is the sequence from Algorithm [5](https://arxiv.org/html/2505.09218v2#alg5).

###### Theorem E.3 .

Let Assumptions [1.1](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem1), [1.2](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem2), and [1.3](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem3) hold. Consider the computation tree (([13](https://arxiv.org/html/2505.09218v2#A5.E13)) and ([14](https://arxiv.org/html/2505.09218v2#A5.E14))) of Local SGD, then $\{x^{k}\}_{k\geq 0}$ is a main branch
and $\frac{1}{K}\sum_{k=0}^{K-1}{\mathbb{E}}\left[\|\nabla f(x^{k})\|^{2}\right]\leq\varepsilon$ for all

$$ $K\geq\frac{4BL\Delta}{\varepsilon}+\frac{8\sigma^{2}L\Delta}{\varepsilon^{2}}.$ $$

with step size $\gamma=\min\{\frac{1}{2BL},\frac{\varepsilon}{4\sigma^{2}L}\}.$

Although the proof may seem technical due to the heavy notation in ([14](https://arxiv.org/html/2505.09218v2#A5.E14)), it is actually straightforward when you refer to Figure [4](https://arxiv.org/html/2505.09218v2#S3.F4). This figure clearly shows that all conditions of Theorem [2.4](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem4) are satisfied with $R=B-1$ because $\sum_{i=1}^{n}M_{i}=B$ in every global iteration. The condition $\sum_{i=1}^{n}M_{i}=B$ helps us to insure that the maximum tree distance $\sup_{k\geq 0}\textnormal{dist}(x^{k},z^{k})\leq B-1.$

###### Proof.

Clearly, $\{x^{k}\}_{k\geq 0}$ is a main branch by Definition [2.1](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem1). The corresponding auxiliary sequence can be inferred from ([14](https://arxiv.org/html/2505.09218v2#A5.E14)): $(z^{0},\xi^{0})=(z^{0,0}_{1},\eta^{0,0}_{1}),\dots,(z^{M_{1}},\xi^{M_{1}})=(z^
{0,M_{1}}_{1},\eta^{0,M_{1}}_{1}),$ and etc. Condition 1 is satisfied because $\{\eta^{k,j}_{i}\}$ are i.i.d., and by the construction ([14](https://arxiv.org/html/2505.09218v2#A5.E14)). Condition 2 of Theorem [2.4](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem4) holds because the same stochastic gradients used for computing $z^{k}$ are also used for $x^{k}$, as shown in Figure [4](https://arxiv.org/html/2505.09218v2#S3.F4). This can be formally verified using ([14](https://arxiv.org/html/2505.09218v2#A5.E14)) and ([13](https://arxiv.org/html/2505.09218v2#A5.E13)).
It is left to notice that

$$ $\displaystyle\sup_{k\geq 0}\textnormal{dist}(x^{k},z^{k})\leq B-1$ $$

because the maximum number of edges to the common closest ancestor can not exit $B-1$.
∎

###### Theorem E.3 .

###### Proof.

### E.4 Ringmaster ASGD

Figure: Algorithm 7 Ringmaster ASGD (Maranjyan et al.,, 2025)

In this method, a main branch can be defined as

$$ $\displaystyle x^{k}=w^{k}$ (15) $$

and the auxiliary sequence is defined as $(z^{k},\xi^{k})=(x^{k-\delta^{k}},\eta^{k-\delta^{k}}_{i})$ for all $k\geq 0.$

Figure: Figure 15: The computation tree of Ringmaster ASGD
Refer to caption: x34.png

###### Theorem E.4 .

Let Assumptions [1.1](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem1), [1.2](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem2), and [1.3](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem3) hold. Consider the computation tree of Ringmaster ASGD, then $\{x^{k}\}_{k\geq 0},$ defined in ([15](https://arxiv.org/html/2505.09218v2#A5.E15)), is a main branch
and $\frac{1}{K}\sum_{k=0}^{K-1}{\mathbb{E}}\left[\|\nabla f(x^{k})\|^{2}\right]\leq\varepsilon$ for all

$$ $K\geq\frac{4BL\Delta}{\varepsilon}+\frac{8\sigma^{2}L\Delta}{\varepsilon^{2}}.$ $$

with step size $\gamma=\min\{\frac{1}{2BL},\frac{\varepsilon}{4\sigma^{2}L}\}.$

###### Proof.

Condition 1 is satisfied because $\{\eta^{k-\delta^{k}}_{i}\}$ are i.i.d., $x^{k}=w^{k}$ and $z^{k}=x^{k-\delta^{k}}$ do not depend on $\xi^{k}=\eta^{k-\delta^{k}}_{i}.$ Condition 2 is satisfied because $\textnormal{repr}(z^{k})=\textnormal{repr}(w^{k-\delta^{k}})\subseteq
\textnormal{repr}(w^{k})=\textnormal{repr}(x^{k}).$ Condition 3 is satisfied with $R=B-1$ because

$$ $\displaystyle\textnormal{dist}(x^{k},z^{k})=\textnormal{dist}(x^{k},x^{k- \delta^{k}})=\delta^{k}\leq B-1,$ $$

where the second equality due to the number of edges between $x^{k}$ and $x^{k-\delta^{k}}$ and the last inequality due to the fact that $\delta^{k}$ is bounded by $B$ in Algorithm [7](https://arxiv.org/html/2505.09218v2#alg7).
∎

###### Theorem E.4 .

###### Proof.

### E.5 Cycle SGD

We now present a new method, called Cycle SGD:

Figure: Algorithm 8 Cycle SGD

This method operates similarly to Local SGD, with workers performing local steps. However, a key difference is that only $s$ 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 of the corresponding computation tree is in Figure [16](https://arxiv.org/html/2505.09218v2#A5.F16). For this algorithm, the first $\sum_{i=1}^{n}M_{i}$ nodes of the main branch can be defined as

$$ $\displaystyle x^{1}$ $\displaystyle=x^{0}-\gamma\nabla f(z^{0}_{1};\eta^{0}_{1}),$ (16) $\displaystyle\vdots$ $\displaystyle x^{M_{1}}$ $\displaystyle=x^{M_{1}-1}-\gamma\nabla f(z^{M_{1}-1}_{1};\eta^{M_{1}-1}_{1}),$ $\displaystyle\vdots$ $\displaystyle x^{\sum_{i=1}^{s-1}M_{i}+1}$ $\displaystyle=x^{\sum_{i=1}^{s-1}M_{i}}-\gamma\nabla f(z^{0}_{s};\eta^{0}_{s}),$ $\displaystyle\vdots$ $\displaystyle x^{\sum_{i=1}^{s}M_{i}}$ $\displaystyle=x^{\sum_{i=1}^{s}M_{i}-1}-\gamma\nabla f(z^{M_{s}-1}_{s};\eta^{M _{s}-1}_{s}),$ $\displaystyle\vdots$ $$

Notice that $x^{\sum_{i=1}^{s}M_{i}}\equiv w^{1},$ where we capture and unroll all stochastic gradients from the first group. The next nodes of the main branch can be defined in a similar way going through all groups circularly.

Figure: Figure 16: An example of Cycle SGD computation tree.
Refer to caption: x35.png

###### Theorem E.5 .

Let Assumptions [1.1](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem1), [1.2](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem2), and [1.3](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem3) hold. Consider the computation tree of Cycle SGD (Alg. [8](https://arxiv.org/html/2505.09218v2#alg8)), then $\{x^{k}\}_{k\geq 0},$ defined in ([16](https://arxiv.org/html/2505.09218v2#A5.E16)), is a main branch
and $\frac{1}{K}\sum_{k=0}^{K-1}{\mathbb{E}}\left[\|\nabla f(x^{k})\|^{2}\right]\leq\varepsilon$ for all

$$ $K\geq\frac{8n^{2}L\Delta}{s\varepsilon}+\frac{8\sigma^{2}L\Delta}{\varepsilon^ {2}}.$ $$

with step size $\gamma=\min\{\frac{s}{4n^{2}L},\frac{\varepsilon}{4\sigma^{2}L}\}.$

###### Proof.

Once again, the proof is geometric. As an example, consider Figure [16](https://arxiv.org/html/2505.09218v2#A5.F16) together with Algorithm [8](https://arxiv.org/html/2505.09218v2#alg8). One can easily show that Conditions 1 and 2 are satisfied similarly to the proof of Theorem [5](https://arxiv.org/html/2505.09218v2#alg5). However, the maximum tree distance is different since we synchronize the workers in a circular manner.

First, the number of local steps $M_{i}\leq\left\lceil\frac{n}{s}\right\rceil\leq\frac{2n}{s}$ because each worker computes one stochastic gradient in the inner loop and synchronizes every $\left\lceil\frac{n}{s}\right\rceil$ loops.

Next, the maximum tree distance between a point $x^{k}$ on the main branch and the corresponding point of the auxiliary sequence $z^{k}$ is at most $\frac{2n^{2}}{s}$. Let us explain this step. Consider any $x^{k}$ and $z^{k}$, and their closest common ancestor $w^{k}$ (in Figure [16](https://arxiv.org/html/2505.09218v2#A5.F16), for instance, take $x^{5}$, $z^{2,2}_{2}$, and $x^{3}$ accordingly).

The number of edges from $z^{k}$ to $w^{k}$ never exceeds $\frac{2n}{s}$ due to the bound on the number of local steps. The number of edges from $x^{k}$ to $w^{k}$ never exceeds $\frac{2n^{2}}{s}$ because, while one worker performs local steps, other workers can grow the main branch by at most $\left\lceil\frac{n}{s}\right\rceil\times(n-1)\leq\frac{2n(n-1)}{s}$ points before the worker that computed $z^{k}$ is synchronized(^8^88For instance, see Figure [16](https://arxiv.org/html/2505.09218v2#A5.F16), where, before the algorithm applies $\nabla f(z^{2,1}_{2};\xi^{2,1}_{2})$ from the second worker, the main branch grows by two edges, from $x^{3}$ to $x^{5}$, due to gradients computed by the first worker.).

Thus, we can take $R=\frac{2n^{2}}{s}$ in Condition 3 of Theorem [2.4](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem4).
∎

###### Theorem E.5 .

###### Proof.

### E.6 Async-Local SGD

The following algorithm is a mixture of Asynchronous SGD and Local SGD, which we formalize in the following way.

Figure: Algorithm 9 Async-Local SGD

Figure: Algorithm 10 LocalSGDWorker($w,\gamma,M$) in worker $i$

If $M=1,$ then this method reduces to Ringmaster ASGD (Alg. [7](https://arxiv.org/html/2505.09218v2#alg7)). 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 a main branch as

$$ $\displaystyle x^{1}$ $\displaystyle=x^{0}-\gamma\nabla f(z^{0}_{i_{1}};\eta^{0}_{i_{1}}),$ (17) $\displaystyle\vdots$ $\displaystyle x^{M}$ $\displaystyle=x^{M-1}-\gamma\nabla f(z^{M-1}_{i_{1}};\eta^{M-1}_{i_{1}}),$ $\displaystyle\vdots$ $\displaystyle x^{M(k-1)+1}$ $\displaystyle=x^{M(k-1)}-\gamma\nabla f(z^{0}_{i_{k}};\eta^{0}_{i_{k}}),$ $\displaystyle\vdots,$ $\displaystyle x^{Mk}$ $\displaystyle=x^{Mk-1}-\gamma\nabla f(z^{M-1}_{i_{k}};\eta^{M-1}_{i_{k}}),$ $\displaystyle\vdots$ $$

and so on. Notice that $x^{0}\equiv w^{0},x^{M}\equiv w^{1},$ etc.

###### Theorem E.6 .

Let Assumptions [1.1](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem1), [1.2](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem2), and [1.3](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem3) hold. Consider the computation tree of Async-Local SGD (Alg. [9](https://arxiv.org/html/2505.09218v2#alg9)), then $\{x^{k}\}_{k\geq 0},$ defined in ([17](https://arxiv.org/html/2505.09218v2#A5.E17)), is a main branch
and $\frac{1}{K}\sum_{k=0}^{K-1}{\mathbb{E}}\left[\|\nabla f(x^{k})\|^{2}\right]\leq\varepsilon$ for all

$$ $K\geq\frac{4(B+M-1)L\Delta}{\varepsilon}+\frac{8\sigma^{2}L\Delta}{\varepsilon ^{2}}.$ $$

with step size $\gamma=\min\{\frac{1}{4(B+M-1)L},\frac{\varepsilon}{4\sigma^{2}L}\}.$

###### Proof.

Similar to the previous proofs, Condition 1 is satisfied for the main branch $\{x^{k}\}_{k\geq 0}$ because all random variables $\{\eta^{i}_{j}\}$ in ([17](https://arxiv.org/html/2505.09218v2#A5.E17)) are i.i.d., and $x^{0}$ and $z^{0}_{i_{1}}$ do not depend on $\eta^{0}_{i_{1}}.$ Points $x^{M-1}$ and $z^{M-1}_{i_{1}}$ do not depend on $\eta^{M-1}_{i_{1}},$ and so on. Conditions 2 is satisfied because all stochastic gradients used to compute $z^{p}_{i_{k}}$ are also used to compute the corresponding point on the main branch for all $p\in\{0,\dots,M-1\}$ and $k\geq 0$ (see Figure [5](https://arxiv.org/html/2505.09218v2#S3.F5)). Condition 3 is satisfied with $R=B-1+M-1=B+M-2$ due to the inequality $\delta^{k}=\textnormal{dist}(w^{k},z^{0}_{i_{k}})<B$ in Algorithm [9](https://arxiv.org/html/2505.09218v2#alg9) and the fact every worker calculates $M$ stochastic gradients, which ensures that the tree distance between $z^{0}_{i_{k}}$ and the corresponding point from the main brain branch is at most $B-1,$ the tree distance between $z^{1}_{i_{k}}$ and the corresponding point from the main brain branch is at most $B-2,$ $\dots,$ the tree distance between $z^{M-1}_{i_{k}}$ and the corresponding point from the main brain branch is at most $B+M-2.$
∎

###### Theorem E.6 .

###### Proof.

### 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:

Figure: Algorithm 11 BatchSGDWorker($w,\gamma,M$) in worker $i$

One can easily show that these methods share the same theoretical guarantees (Sections [E.6](https://arxiv.org/html/2505.09218v2#A5.SS6), [F](https://arxiv.org/html/2505.09218v2#A6), and [G](https://arxiv.org/html/2505.09218v2#A7)) as Async-Local SGD.

### 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, at certain points, all workers synchronize, and start running Asynchronous SGD at a new point. One of the important novelties here is the condition $\sum_{g=1}^{s}m_{g}=B,$ which, with a proper $B,$ leads to the optimal computational time complexity (Section [F](https://arxiv.org/html/2505.09218v2#A6)).

Figure: Algorithm 12 Local-Async SGD

Figure: Algorithm 13 AsynchronousSGDGroup($w,\gamma$) in group $g$

For this method, it is natural to take a main branch of the computation tree as

$$ $\displaystyle x^{1}$ $\displaystyle=x^{0}-\gamma\nabla f(v^{0-\delta^{0}}_{1};\eta^{0}_{1}),$ (18) $\displaystyle\vdots$ $\displaystyle x^{m_{1}}$ $\displaystyle=x^{m_{1}-1}-\gamma\nabla f(v^{m_{1}-1-\delta^{m_{1}-1}}_{1};\eta ^{m_{1}-1}_{1}),$ $\displaystyle\vdots$ $\displaystyle x^{\sum_{g=1}^{s-1}m_{i}+1}$ $\displaystyle=x^{\sum_{g=1}^{s-1}m_{i}}-\gamma\nabla f(v^{0-\delta^{0}}_{s}; \eta^{0}_{s}),$ $\displaystyle\vdots,$ $\displaystyle x^{\sum_{g=1}^{s}m_{i}}$ $\displaystyle=x^{\sum_{g=1}^{s}m_{i}-1}-\gamma\nabla f(v^{m_{s}-1-\delta^{m_{s }-1}}_{s};\eta^{m_{s}-1}_{s})$ $\displaystyle\vdots,$ $$

where one can see that $x^{\sum_{g=1}^{s}m_{i}}\equiv x^{B}\equiv w^{1},$ and $\{v^{j}_{g}\}$ is defined in Algorithm [13](https://arxiv.org/html/2505.09218v2#alg13).

Figure: Figure 17: An example of a Local-Async SGD computation tree with two groups and $B=5$. One group performs $m_{1}=3$ steps of Asynchronous SGD, while the other performs $m_{2}=2$ steps. Note that the maximum tree distance is $\textnormal{dist}(x^{4},v^{1-\delta^{1}}_{1})$ when applying $\nabla f(v^{1-\delta^{1}}_{1};\eta^{1}_{1})$ to $x^{4}$, and it equals $B-1=m_{1}+m_{2}-1=4$. Then, the groups synchronize and continue from $x^{5}.$
Refer to caption: x36.png

###### Theorem E.7 .

Let Assumptions [1.1](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem1), [1.2](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem2), and [1.3](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem3) hold. Consider the computation tree of Local-Async SGD (Alg. [12](https://arxiv.org/html/2505.09218v2#alg12)), then $\{x^{k}\}_{k\geq 0},$ defined in ([18](https://arxiv.org/html/2505.09218v2#A5.E18)), is a main branch
and $\frac{1}{K}\sum_{k=0}^{K-1}{\mathbb{E}}\left[\|\nabla f(x^{k})\|^{2}\right]\leq\varepsilon$ for all

$$ $K\geq\frac{4BL\Delta}{\varepsilon}+\frac{8\sigma^{2}L\Delta}{\varepsilon^{2}}.$ $$

with step size $\gamma=\min\{\frac{1}{4BL},\frac{\varepsilon}{4\sigma^{2}L}\}.$

###### Proof.

The proof closely follows that of Theorem [E.3](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem3), with the only difference being that the *auxiliary branches* in Algorithm [13](https://arxiv.org/html/2505.09218v2#alg13) are constructed using asynchronous steps rather than local steps (compare Figure [4](https://arxiv.org/html/2505.09218v2#S3.F4) and Figure [17](https://arxiv.org/html/2505.09218v2#A5.F17)). As in Theorem [E.3](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem3), the condition $\sum_{g=1}^{s}m_{g}=B$ ensures that $\sup_{k\geq 0}\textnormal{dist}(x^{k},z^{k})\leq B-1.$
∎

###### Theorem E.7 .

###### Proof.

### E.9 Nested Local-Async SGD

In this section, we formalize a hierarchical version of Algorithm [12](https://arxiv.org/html/2505.09218v2#alg12). Our framework, Theorem [2.4](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem4), is flexible enough to support such a 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 $\{G_{ij}\}$ groups, where $i$ is the cluster index and $j$ is the server index within the cluster. The set $G_{ij}$ contains the indices of the workers (GPUs).

Figure: Algorithm 14 Nested Local-Async SGD

Figure: Algorithm 15 AsynchronousSGDGroup($w,\gamma$) in group $G_{ij}$

We believe that analyzing this algorithm directly using classical optimization tools would be challenging due to heavy notations. However, using our framework and geometrical graph reasoning, we can easily prove the iteration rate of this algorithm. As in all previous cases, a main branch ${x^{k}}$ can be defined by taking each component of the sum $\sum_{i}\sum_{k=0}^{p_{i}-1}\sum_{j}\sum_{\ell=0}^{m_{ijk}-1}\nabla f(v^{{\ell
}-\delta^{{\ell}}}_{ijk};\eta^{{\ell}}_{ijk})$ and applying each stochastic gradient to $x^{0},x^{1}=x^{0}-\gamma\nabla f(v^{0}_{110};\eta^{0}_{110}),$ and so on.

###### Theorem E.8 .

Let Assumptions [1.1](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem1), [1.2](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem2), and [1.3](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem3) hold. Consider the computation tree of Nested Local-Async SGD (Alg. [14](https://arxiv.org/html/2505.09218v2#alg14)), then $\frac{1}{K}\sum_{k=0}^{K-1}{\mathbb{E}}\left[\|\nabla f(x^{k})\|^{2}\right]\leq\varepsilon$ for all

$$ $K\geq\frac{4BL\Delta}{\varepsilon}+\frac{8\sigma^{2}L\Delta}{\varepsilon^{2}}.$ $$

with step size $\gamma=\min\{\frac{1}{4BL},\frac{\varepsilon}{4\sigma^{2}L}\}$ for the main branch $\{x^{k}\}$ (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 $R\leq 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^{\cdot}_{\cdot}$ does not exceed $B$.
∎

###### Remark E.9 .

One can see that the converge rate does not depend on $\{B_{i}\}.$ Theoretically, it is sufficient to take $B_{i}=\infty.$ However, practically, it may be better to take $B_{i}<\infty$ to ensure that the GPUs synchronize more often and share information with others, but it can lead to communication overhead and less efficient utilization of the GPUs.

###### Theorem E.8 .

###### Proof.

###### Remark E.9 .

### E.10 Meta Local SGD

Compared to previous algorithms, Meta Local SGD is an abstract or meta-method, as it includes one abstract step: “Wait if needed and take any set of workers $S$.” This step is not explicitly defined, allowing users to apply any strategy they prefer. It may be random, where the algorithm chooses a uniformly random subset; it may follow a condition as in Local SGD, where the algorithm waits until $\sum_{i=1}^{n}M_{i}=B$; or it 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 is why we check the condition $\max_{j\in[n]}d_{j}+\sum_{i=1}^{n}M_{i}<B$ in the algorithm, where $\{d_{i}\}$ are the current distances to the head of the main branch and $\{M_{i}\}$ 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\in[n]\,|\,d_{j}+\sum_{i=1}^{n}M_{i}=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.

Figure: Algorithm 16 Meta Local SGD

Figure: Algorithm 17 LocalSGDWorker($w,\gamma$) in worker $i$

A main branch in the computation tree can be defined as follows. Assume that $S^{k}=\{i_{1},\dots,i_{p_{k}}\}$ is the set of workers participating in iteration $k$. Then, the computation tree with the main branch $\{x^{k}\}$ can be constructed as

$$ $\displaystyle x^{1}$ $\displaystyle=x^{0}-\gamma\nabla f(z^{0}_{i_{1}};\eta^{0}_{i_{1}}),$ (19) $\displaystyle x^{2}$ $\displaystyle=x^{1}-\gamma\nabla f(z^{1}_{i_{1}};\eta^{1}_{i_{1}}),$ $\displaystyle\vdots$ $\displaystyle x^{M_{i_{1}}}$ $\displaystyle=x^{M_{i_{1}}-1}-\gamma\nabla f(z^{M_{i_{1}}-1}_{i_{1}};\eta^{M_{ i_{1}}-1}_{i_{1}}),$ $\displaystyle\vdots$ $\displaystyle x^{\sum_{j=1}^{p_{k}-1}M_{i_{j}}+1}$ $\displaystyle=x^{\sum_{j=1}^{p_{k}-1}M_{i_{j}}}-\gamma\nabla f(z^{0}_{i_{p_{k} }};\eta^{0}_{i_{p_{k}}}),$ $\displaystyle\vdots$ $\displaystyle x^{\sum_{j=1}^{p_{k}}M_{i_{j}}}$ $\displaystyle=x^{\sum_{j=1}^{p_{k}}M_{i_{j}}-1}-\gamma\nabla f(z^{M_{i_{p_{k}} }-1}_{i_{p_{k}}};\eta^{M_{i_{p_{k}}}-1}_{i_{p_{k}}}),$ $\displaystyle\vdots$ $$

Notice that the end of each iteration block can be written as

$$ $\displaystyle w^{1}\equiv x^{\sum_{j=1}^{p_{0}}M_{i_{j}}},\quad w^{2}\equiv x^ {\sum_{j=1}^{p_{0}}M_{i_{j}}+\sum_{j=1}^{p_{1}}M_{i_{j}}},\quad\text{and so on}.$ $$

Figure: Figure 18: 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^{0}\rightarrow z^{1,1}_{2}\rightarrow z^{1,2}_{2}$, and sends the stochastic gradients, which are used to calculate $x^{1}$ and $x^{2}$. A similar sequence of steps is repeated by the first worker to produce $x^{2}\rightarrow z^{2,1}_{2}\rightarrow z^{2,2}_{2}$, followed by $x^{3}$ and $x^{4}$. At the same time, the second worker has only completed $x^{0}\rightarrow z^{1,1}_{1}\rightarrow z^{1,2}_{1}$ and has not yet synchronized or sent the corresponding stochastic gradients. At this moment in time, the number of local steps is $M_{2}=2$ and $d_{2}=4$, because $d_{2}$ is the number of edges between the current main branch head $x^{4}$ and the point $x^{0}$, where the local branch of the second worker started. At the same time, $M_{1}=0$ and $d_{1}=0$, because the first worker has just started the third set of local steps at $x^{4}$ and has not yet calculated local stochastic gradients.
Refer to caption: x37.png

###### Theorem E.10 .

Let Assumptions [1.1](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem1), [1.2](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem2), and [1.3](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem3) hold. Consider the computation tree of Meta Local SGD (Alg. [16](https://arxiv.org/html/2505.09218v2#alg16)), then $\{x^{k}\}_{k\geq 0},$ defined in ([19](https://arxiv.org/html/2505.09218v2#A5.E19)), is a main branch
and $\frac{1}{K}\sum_{k=0}^{K-1}{\mathbb{E}}\left[\|\nabla f(x^{k})\|^{2}\right]\leq\varepsilon$ for all

$$ $K\geq\frac{4BL\Delta}{\varepsilon}+\frac{8\sigma^{2}L\Delta}{\varepsilon^{2}}.$ $$

with step size $\gamma=\min\{\frac{1}{4BL},\frac{\varepsilon}{4\sigma^{2}L}\}.$

###### Proof.

Similarly to the previous proofs, it is clear that Conditions 1 and 2 from Theorem [2.4](https://arxiv.org/html/2505.09218v2#S2.Thmtheorem4) are satisfied for the main branch ([19](https://arxiv.org/html/2505.09218v2#A5.E19)).

It remains to show that $\textnormal{dist}(x^{k},z^{k})\leq B$ for all $k\geq 0$. In the algorithm, we track two key sets of variables: $\{d_{i}\}$ and $\{M_{i}\}$. The variable $M_{i}$ denotes the current number of local steps performed by worker $i$, while $d_{i}$ represents the number of edges between the current end of the main branch and the point where worker $i$ began its local updates. When worker $i\notin S$, the distance $d_{i}$ increases as follows: $d_{i}=d_{i}+\sum_{j\in S}M_{j},$ since the workers in $S$ extend the main branch with their accumulated local updates.

The algorithm is constructed so that the quantity $\max_{j\in[n]}d_{j}+\sum_{i=1}^{n}M_{i}$ remains bounded by $B$ throughout the entire optimization process, ensuring that Condition 3 is satisfied with $R=B$. To clarify, assume that $i\in S$ in Algorithm [16](https://arxiv.org/html/2505.09218v2#alg16). In the worst-case scenario, all other workers $j\in S$, with $j\neq i$, apply their local updates, increasing the tree distance from worker $i$’s branch to the main branch by at most $\sum_{j\in S,j\neq i}M_{j}$. Thus, the updated tree distance becomes at most $d_{i}+\sum_{j\in[n],j\neq i}M_{j}.$
Since worker $i$ has also performed $M_{i}$ local steps, the tree distance is bounded by $d_{i}+\sum_{j\in[n],j\neq i}M_{j}+M_{i}\leq B.$
∎

###### Theorem E.10 .

###### Proof.

### E.11 Dual-Process SGD

We now present a 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 sum 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 soon as possible.

Initially, each worker waits for the first stochastic gradients with index 0 0 and immediately sends them once available. Then, while these are being transmitted, the workers continue their local computations. After the server receives the gradients with index 0 0, the workers begin sending the next batch of stochastic gradients, starting from index $1$ up to 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](https://arxiv.org/html/2505.09218v2#alg19).

Figure: Algorithm 18 Dual-Process SGD

Figure: Algorithm 19 DualProcessLocalSGDWorker($w,\gamma$) in worker $i$ at round $k$

The computation tree of Dual-Process SGD defined in ([13](https://arxiv.org/html/2505.09218v2#A5.E13)) and ([14](https://arxiv.org/html/2505.09218v2#A5.E14)) is similar to Local SGD.

###### Theorem E.11 .

Let Assumptions [1.1](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem1), [1.2](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem2), and [1.3](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem3) hold. Consider the computation tree (([13](https://arxiv.org/html/2505.09218v2#A5.E13)) and ([14](https://arxiv.org/html/2505.09218v2#A5.E14))) of Dual-Process SGD, then $\{x^{k}\}_{k\geq 0}$ is a main branch
and $\frac{1}{K}\sum_{k=0}^{K-1}{\mathbb{E}}\left[\|\nabla f(x^{k})\|^{2}\right]\leq\varepsilon$ for all

$$ $K\geq\frac{4BL\Delta}{\varepsilon}+\frac{8\sigma^{2}L\Delta}{\varepsilon^{2}}.$ $$

with step size $\gamma=\min\{\frac{1}{2BL},\frac{\varepsilon}{4\sigma^{2}L}\}.$

###### Proof.

The proof is exactly the same as in Theorem [E.3](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem3) since the computation tree of Dual-Process SGD is similar to Local SGD.
∎

###### Theorem E.11 .

###### Proof.

## Appendix F Computational Time Complexities of Algorithms under h i subscript ℎ 𝑖 h_{i} italic_h start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT -Fixed Computation Model

To compare methods, we consider the *$h_{i}$-fixed computation model* (Mishchenko et al.,, 2022).
In this model, it is assumed that

$$ $\displaystyle\text{worker }i\text{ takes no more than }h_{i}\text{ seconds} \text{ to compute a single stochastic gradient}$ (20) $$

and

$$ $0<h_{1}\leq h_{2}\leq\cdots\leq h_{n},$ (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 *$h_{i}$-fixed computation model* may seem more restrictive, it turns out that all optimal methods (Maranjyan et al.,, 2025) in the *universal computation model* are also optimal in the *$h_{i}$-fixed computation model*. Thus, for simplicity, we stick to the *$h_{i}$-fixed computation model*.

### F.1 Rennala SGD

###### Theorem F.1 ( Rennala SGD ) .

Consider Theorem [E.2](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem2) and its conditions. Under the $h_{i}$-fixed computation model ([20](https://arxiv.org/html/2505.09218v2#A6.E20)), the computational time complexity of Rennala SGD (Alg. [4](https://arxiv.org/html/2505.09218v2#alg4)) is

$$ $\displaystyle\mathcal{O}\left(\min\limits_{m\in[n]}\left[\left(\frac{1}{m}\sum \limits_{i=1}^{m}\frac{1}{h_{i}}\right)^{-1}\left(\frac{L\Delta}{\varepsilon}+ \frac{\sigma^{2}L\Delta}{m\varepsilon^{2}}\right)\right]\right)$ (22) $$

with $B=\max\left\{\left\lceil\frac{\sigma^{2}}{\varepsilon}\right\rceil,1\right\}.$

We start with the following lemma.

###### Lemma F.2 .

Let us define

$$ $\displaystyle T_{\textnormal{R}}(B):=2\min_{m\in[n]}\left[\left(\sum_{i=1}^{m} \frac{1}{h_{i}}\right)^{-1}(B+m)\right]$ (23) $$

Under the $h_{i}$-fixed computation model ([20](https://arxiv.org/html/2505.09218v2#A6.E20)), the time required to calculate $x^{1},\dots,x^{B}$ of the main branch is at most $T_{\textnormal{R}}(B)$ seconds, the time required to calculate $x^{B+1},\dots,x^{2B}$ is at most $T_{\textnormal{R}}(B)$ seconds, and so on.

###### Proof.

The idea of Rennala SGD (Alg. [4](https://arxiv.org/html/2505.09218v2#alg4)) is pretty simple. Notice that all workers calculate stochastic gradients at the same point in parallel until the server collects a batch of size $B$ (condition $\delta=0$ ensures that). Since they work in parallel, under the fixed computational model, after $t$ seconds the workers will calculate

$$ $\displaystyle\sum_{i=1}^{n}\max\left\{\left\lfloor\frac{t}{h_{i}}\right\rfloor -1,0\right\}$ (24) $$

stochastic gradients because $\left\lfloor\frac{t}{h_{i}}\right\rfloor$ is the number of stochastic gradients computed by worker $i$ in $t$ seconds. We subtract $1$ because at most one stochastic gradient be can be ignored due to the condition $\delta=0$ in Alg. [4](https://arxiv.org/html/2505.09218v2#alg4).

Notice that

$$ $\displaystyle T_{\textnormal{R}}(B)=2\left(\sum_{i=1}^{m^{*}}\frac{1}{h_{i}} \right)^{-1}(B+m^{*})$ $$

for some $m^{*}\in[n].$ Substituting it to ([24](https://arxiv.org/html/2505.09218v2#A6.E24)), we get

$$ $\displaystyle\sum_{i=1}^{n}\max\left\{\left\lfloor\frac{T_{\textnormal{R}}(B)} {h_{i}}\right\rfloor-1,0\right\}$ $\displaystyle\geq\sum_{i=1}^{m^{*}}\max\left\{\left\lfloor\frac{T_{\textnormal {R}}(B)}{h_{i}}\right\rfloor-1,0\right\}\geq\sum_{i=1}^{m^{*}}\left\lfloor \frac{T_{\textnormal{R}}(B)}{h_{i}}\right\rfloor-m^{*}$ $\displaystyle\geq\sum_{i=1}^{m^{*}}\frac{T_{\textnormal{R}}(B)}{h_{i}}-2m^{*}= 2(B+m^{*})-2m^{*}\geq B.$ $$

Thus, after $T_{\textnormal{R}}(B)$ seconds, the server collects $B$ stochastic gradients, which is equivalent to calculating $x^{1},\dots,x^{B}$ of the main branch. The same argument can be applied to the next $B$ point of the main branch, and so on.
∎

###### Proof of Theorem F.1 .

Due to Theorem [E.2](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem2), we know that
$\frac{1}{K}\sum_{k=0}^{K-1}{\mathbb{E}}\left[\|\nabla f(x^{k})\|^{2}\right]\leq\varepsilon$ for

$$ $K=\left\lceil\frac{4BL\Delta}{\varepsilon}+\frac{8\sigma^{2}L\Delta}{ \varepsilon^{2}}\right\rceil.$ $$

From Lemma [F.2](https://arxiv.org/html/2505.09218v2#A6.Thmtheorem2), we know that the time required to calculate $x^{1},\dots,x^{B}$ of the main branch is at most $T_{\textnormal{R}}(B)$ seconds, the time required to calculate $x^{B+1},\dots,x^{2B}$ is at most $T_{\textnormal{R}}(B)$ seconds, and so on. Thus, the total time to find an $\varepsilon$–stationary point is

$$ $\displaystyle\mathcal{O}\left(T_{\textnormal{R}}(B)\times\frac{K}{B}\right)= \mathcal{O}\left(T_{\textnormal{R}}(B)\times\left(\frac{L\Delta}{\varepsilon}+ \frac{\sigma^{2}L\Delta}{B\varepsilon^{2}}\right)\right).$ $$

Using the choice of $B,$

$$ $\displaystyle\mathcal{O}\left(T_{\textnormal{R}}(B)\times\frac{K}{B}\right)$ $\displaystyle=\mathcal{O}\left(\min_{m\in[n]}\left[\left(\sum_{i=1}^{m}\frac{1 }{h_{i}}\right)^{-1}(B+m)\right]\times\frac{L\Delta}{\varepsilon}\right)$ $\displaystyle=\mathcal{O}\left(\min\limits_{m\in[n]}\left[\left(\frac{1}{m} \sum\limits_{i=1}^{m}\frac{1}{h_{i}}\right)^{-1}\left(\frac{L\Delta}{ \varepsilon}+\frac{\sigma^{2}L\Delta}{m\varepsilon^{2}}\right)\right]\right).$ $$

∎

###### Theorem F.1 ( Rennala SGD ) .

###### Lemma F.2 .

###### Proof.

###### Proof of Theorem F.1 .

### F.2 Ringmaster ASGD

###### Theorem F.3 ( Ringmaster ASGD ) .

Consider Theorem [E.4](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem4) and its conditions. Under the $h_{i}$-fixed computation model ([20](https://arxiv.org/html/2505.09218v2#A6.E20)), the computational time complexity of Ringmaster ASGD is

$$ $\displaystyle\mathcal{O}\left(\min\limits_{m\in[n]}\left[\left(\frac{1}{m}\sum \limits_{i=1}^{m}\frac{1}{h_{i}}\right)^{-1}\left(\frac{L\Delta}{\varepsilon}+ \frac{\sigma^{2}L\Delta}{m\varepsilon^{2}}\right)\right]\right)$ $$

with $B=\max\left\{\left\lceil\frac{\sigma^{2}}{\varepsilon}\right\rceil,1\right\}.$

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_{i}$-fixed computation model* (([20](https://arxiv.org/html/2505.09218v2#A6.E20)) and ([21](https://arxiv.org/html/2505.09218v2#A6.E21))).
Let $B$ be the delay threshold of Alg. [7](https://arxiv.org/html/2505.09218v2#alg7).
The time required to complete any $B$ consecutive iterate updates of Alg. [7](https://arxiv.org/html/2505.09218v2#alg7) is at most

$$ $T_{A}(B):=2\min\limits_{m\in[n]}\left[\left(\frac{1}{m}\sum\limits_{i=1}^{m} \frac{1}{\tau_{i}}\right)^{-1}\left(1+\frac{R}{m}\right)\right].$ (25) $$

###### Corollary F.5 .

In view of Lemma [F.4](https://arxiv.org/html/2505.09218v2#A6.Thmtheorem4), Under the $h_{i}$-fixed computation model ([20](https://arxiv.org/html/2505.09218v2#A6.E20)), the time required to calculate $x^{1},\dots,x^{B}$ of the main branch is at most $T_{A}(B)$ seconds, the time required to calculate $x^{B+1},\dots,x^{2B}$ is at most $T_{A}(B)$ seconds, and so on.

###### Proof of Theorem F.3 .

The proof of Theorem [F.3](https://arxiv.org/html/2505.09218v2#A6.Thmtheorem3) is similar to the proof of Theorem [F.1](https://arxiv.org/html/2505.09218v2#A6.Thmtheorem1). From Corollary [F.5](https://arxiv.org/html/2505.09218v2#A6.Thmtheorem5), we know that the time required to calculate $x^{1},\dots,x^{B}$ of the main branch is at most $T_{\textnormal{A}}(B)$ seconds, the time required to calculate $x^{B+1},\dots,x^{2B}$ is at most $T_{\textnormal{A}}(B)$ seconds, and so on. Thus, the total time to find an $\varepsilon$–stationary point is

$$ $\displaystyle\mathcal{O}\left(T_{\textnormal{A}}(B)\times\frac{K}{B}\right)= \mathcal{O}\left(\min\limits_{m\in[n]}\left[\left(\frac{1}{m}\sum\limits_{i=1} ^{m}\frac{1}{h_{i}}\right)^{-1}\left(\frac{L\Delta}{\varepsilon}+\frac{\sigma^ {2}L\Delta}{m\varepsilon^{2}}\right)\right]\right).$ $$

∎

###### Theorem F.3 ( Ringmaster ASGD ) .

###### Lemma F.4 .

###### Corollary F.5 .

###### Proof of Theorem F.3 .

### F.3 Local SGD

###### Theorem F.6 ( Local SGD ) .

Consider Theorem [E.3](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem3) and its conditions. Under the $h_{i}$-fixed computation model ([20](https://arxiv.org/html/2505.09218v2#A6.E20)), the computational time complexity of Local SGD (Alg. [5](https://arxiv.org/html/2505.09218v2#alg5)) is

$$ $\displaystyle\mathcal{O}\left(\min\limits_{m\in[n]}\left[\left(\frac{1}{m}\sum \limits_{i=1}^{m}\frac{1}{h_{i}}\right)^{-1}\left(\frac{L\Delta}{\varepsilon}+ \frac{\sigma^{2}L\Delta}{m\varepsilon^{2}}\right)\right]\right)$ $$

with $B=\max\left\{\left\lceil\frac{\sigma^{2}}{\varepsilon}\right\rceil,1\right\}.$

###### Lemma F.7 .

Let us define

$$ $\displaystyle T_{\textnormal{L}}(B):=2\min_{m\in[n]}\left[\left(\sum_{i=1}^{m} \frac{1}{h_{i}}\right)^{-1}(B+m)\right]$ (26) $$

Under the $h_{i}$-fixed computation model ([20](https://arxiv.org/html/2505.09218v2#A6.E20)), the time required to calculate $x^{1},\dots,x^{B}$ of the main branch is at most $T_{\textnormal{L}}(B)$ seconds, the time required to calculate $x^{B+1},\dots,x^{2B}$ is at most $T_{\textnormal{L}}(B)$ seconds, and so on.

###### Proof.

The idea is the same as in Lemma [F.2](https://arxiv.org/html/2505.09218v2#A6.Thmtheorem2). 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. If the server can stop the workers, then after $t$ seconds it is possible to collect

$$ $\displaystyle\sum_{i=1}^{n}\left\lfloor\frac{t}{h_{i}}\right\rfloor$ (27) $$

stochastic gradients. If it is infeasible to stop the calculations (see footnote [7](https://arxiv.org/html/2505.09218v2#footnote7)), then after $t$ seconds it is possible to collect

$$ $\displaystyle\sum_{i=1}^{n}\max\left\{\left\lfloor\frac{t}{h_{i}}\right\rfloor -1,0\right\},$ (28) $$

where we subtract $1$ because at most one stochastic gradient can be ignored if it is nonrelevant. Similarly to Lemma [F.2](https://arxiv.org/html/2505.09218v2#A6.Thmtheorem2), substituting $T_{\textnormal{L}}(B)$ into ([27](https://arxiv.org/html/2505.09218v2#A6.E27)) and ([28](https://arxiv.org/html/2505.09218v2#A6.E28)), one can show that $T_{\textnormal{L}}(B)$ is sufficient to collect $B=\sum_{i=1}^{n}M_{i}$ stochastic gradients, or, in other words, to calculate $x^{1},\dots,x^{B}$ of the main branch. The same argument can be applied to the next $B$ points of the main branch, and so on.
∎

###### Proof of Theorem F.6 .

The proof essentially the same as the proof of Theorem [F.1](https://arxiv.org/html/2505.09218v2#A6.Thmtheorem1).
∎

###### Theorem F.6 ( Local SGD ) .

###### Lemma F.7 .

###### Proof.

###### Proof of Theorem F.6 .

### F.4 Local-Async SGD

###### Theorem F.8 ( Local-Async SGD ) .

Consider Theorem [E.7](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem7) and its conditions. Under the $h_{i}$-fixed computation model ([20](https://arxiv.org/html/2505.09218v2#A6.E20)), the computational time complexity of Local-Async SGD (Alg. [12](https://arxiv.org/html/2505.09218v2#alg12)) is

$$ $\displaystyle\mathcal{O}\left(\min\limits_{m\in[n]}\left[\left(\frac{1}{m}\sum \limits_{i=1}^{m}\frac{1}{h_{i}}\right)^{-1}\left(\frac{L\Delta}{\varepsilon}+ \frac{\sigma^{2}L\Delta}{m\varepsilon^{2}}\right)\right]\right)$ $$

with $B=\max\left\{\left\lceil\frac{\sigma^{2}}{\varepsilon}\right\rceil,1\right\}.$

###### Lemma F.9 .

Let us define

$$ $\displaystyle T_{\textnormal{LA}}(B):=2\min_{m\in[n]}\left[\left(\sum_{i=1}^{m }\frac{1}{h_{i}}\right)^{-1}(B+m)\right]$ (29) $$

Under the $h_{i}$-fixed computation model ([20](https://arxiv.org/html/2505.09218v2#A6.E20)), the time required to calculate $x^{1},\dots,x^{B}$ of the main branch is at most $T_{\textnormal{LA}}(B)$ seconds, the time required to calculate $x^{B+1},\dots,x^{2B}$ is at most $T_{\textnormal{LA}}(B)$ seconds, and so on.

###### Proof.

The idea is the same as in Lemmas [F.2](https://arxiv.org/html/2505.09218v2#A6.Thmtheorem2) and [F.7](https://arxiv.org/html/2505.09218v2#A6.Thmtheorem7). 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, one can show that $T_{\textnormal{LA}}(B)$ is sufficient time to calculate $B=\sum_{g=1}^{s}m_{g}$ stochastic gradients in Algorithm [12](https://arxiv.org/html/2505.09218v2#alg12), or, equivalently, to calculate $x^{1},\dots,x^{B}$ of the main branch. The same argument can be applied to the next $B$ point of the main branch.
∎

###### Proof of Theorem F.8 .

The proof essentially the same as the proof of Theorem [F.1](https://arxiv.org/html/2505.09218v2#A6.Thmtheorem1).
∎

###### Theorem F.8 ( Local-Async SGD ) .

###### Lemma F.9 .

###### Proof.

###### Proof of Theorem F.8 .

### F.5 Nested Local-Async SGD

###### Theorem F.10 ( Nested Local-Async SGD ) .

Consider Theorem [E.8](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem8) and its conditions. Under the $h_{i}$-fixed computation model ([20](https://arxiv.org/html/2505.09218v2#A6.E20)), the computational time complexity of Nested Local-Async SGD (Alg. [14](https://arxiv.org/html/2505.09218v2#alg14)) is

$$ $\displaystyle\mathcal{O}\left(\min\limits_{m\in[n]}\left[\left(\frac{1}{m}\sum \limits_{i=1}^{m}\frac{1}{h_{i}}\right)^{-1}\left(\frac{L\Delta}{\varepsilon}+ \frac{\sigma^{2}L\Delta}{m\varepsilon^{2}}\right)\right]\right)$ $$

with $B=\max\left\{\left\lceil\frac{\sigma^{2}}{\varepsilon}\right\rceil,1\right\}$ and $B_{i}=\infty$(^10^1010It is possible to take $B_{i}<\infty$, but the computational time complexity may decrease due to less utilization of workers. For simplicity, in this theorem, we take $B_{i}=\infty$. See also Remark [E.9](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem9).) for all $i\in[n].$

###### Proof.

The proof essentially the same as the proof of Theorem [F.1](https://arxiv.org/html/2505.09218v2#A6.Thmtheorem1).
∎

###### Theorem F.10 ( Nested Local-Async SGD ) .

###### Proof.

### F.6 Async-Local SGD

###### Theorem F.11 ( Async-Local SGD ) .

Consider Theorem [E.6](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem6) and its conditions. Under the $h_{i}$-fixed computation model ([20](https://arxiv.org/html/2505.09218v2#A6.E20)), the computational time complexity of Async-Local SGD (Alg. [9](https://arxiv.org/html/2505.09218v2#alg9)) is

$$ $\displaystyle\mathcal{O}\left(\min\limits_{m\in[n]}\left[\left(\frac{1}{m}\sum \limits_{i=1}^{m}\frac{1}{h_{i}}\right)^{-1}\left(\frac{L\Delta}{\varepsilon}+ \frac{\sigma^{2}L\Delta}{m\varepsilon^{2}}\right)\right]\right)$ $$

with $B=\max\left\{\left\lceil\frac{\sigma^{2}}{\varepsilon}\right\rceil,1\right\}$ and $M=\max\left\{\left\lceil\frac{\sigma^{2}}{n\varepsilon}\right\rceil,1\right\}.$

###### Lemma F.12 .

Let us define

$$ $\displaystyle T_{\textnormal{AL}}(B,M):=2\min_{m\in[n]}\left[\left(\sum_{i=1}^ {m}\frac{1}{h_{i}}\right)^{-1}(B+Mm)\right]$ (30) $$

Under the $h_{i}$-fixed computation model ([20](https://arxiv.org/html/2505.09218v2#A6.E20)), the time required to calculate $x^{1},\dots,x^{B}$ of the main branch is at most $T_{\textnormal{AL}}(B,M)$ seconds, the time required to calculate $x^{B+1},\dots,x^{2B}$ is at most $T_{\textnormal{AL}}(B,M)$ seconds, and so on.

###### Proof.

Let us fix $B$ and $M\geq 1.$ Note that

$$ $\displaystyle T_{\textnormal{AL}}(B,M):=2\min_{m\in[n]}\left[\left(\sum_{i=1}^ {m}\frac{1}{h_{i}}\right)^{-1}(B+Mm)\right]=2\left(\sum_{i=1}^{m^{*}}\frac{1}{ h_{i}}\right)^{-1}(B+Mm^{*})$ (31) $$

for some $m^{*}\in[n],$ which depends on $B$ and $M.$

For any $k\geq 1$, consider the sequence $x^{k},\dots,x^{k+B}$ on the main branch. Using a proof by contradiction, assume that it requires more than $T_{\textnormal{AL}}(B,M)$ seconds to calculate $x^{k+1},\dots,x^{k+B}.$ Thus, the algorithm can progress up to $x^{k+B-1}$ after $T_{\textnormal{AL}}(B,M)$ seconds.

In Algorithm [9](https://arxiv.org/html/2505.09218v2#alg9), each worker computes $M$ stochastic gradients and sends their sum to the server. The server then performs the update $w^{k+1}=w^{k}-\gamma\sum_{p=0}^{M-1}\nabla f(z^{p}_{i_{k}};\eta^{p}_{i_{k}}),$ which is equivalent to extending the main branch by $M$ points. Therefore, after $t$ seconds, the main branch will have progressed by at least

$$ $\displaystyle\sum_{i=1}^{n}\max\left\{M\left\lfloor\frac{t}{Mh_{i}}\right \rfloor-M,0\right\},$ (32) $$

points (which is less than $B$ by assumption). This is because worker $i$ requires at most $Mh_{i}$ seconds to compute $M$ stochastic gradients before sending them to the server. Note that during any $B-1$ consecutive updates on the main branch, the server may ignore $M$ gradients from each worker at most once, because $\delta^{k}$ can be $\geq B$ at most once during $B-1$ consecutive updates. This explains the subtraction of $M$ in the formula.

Substituting $T_{\textnormal{AL}}(B,M)$ to ([32](https://arxiv.org/html/2505.09218v2#A6.E32)),

$$ $\displaystyle\sum_{i=1}^{n}\max\left\{M\left\lfloor\frac{T_{\textnormal{AL}}(B ,M)}{Mh_{i}}\right\rfloor-M,0\right\}\geq\sum_{i=1}^{m^{*}}\max\left\{M\left \lfloor\frac{T_{\textnormal{AL}}(B,M)}{Mh_{i}}\right\rfloor-M,0\right\}$ $\displaystyle\geq\sum_{i=1}^{m^{*}}M\left\lfloor\frac{T_{\textnormal{AL}}(B,M) }{Mh_{i}}\right\rfloor-Mm^{*}\geq\sum_{i=1}^{m^{*}}\frac{T_{\textnormal{AL}}(B ,M)}{h_{i}}-2Mm^{*}$ $$

because $\left\lfloor x\right\rfloor\geq x-1$ for all $x\in\mathbb{R}.$ Using ([31](https://arxiv.org/html/2505.09218v2#A6.E31)),

$$ $\displaystyle\sum_{i=1}^{n}\max\left\{M\left\lfloor\frac{T_{\textnormal{AL}}(B ,M)}{Mh_{i}}\right\rfloor-M,0\right\}\geq 2(B+Mm^{*})-2Mm^{*}\geq B.$ $$

Thus, after $T_{\textnormal{AL}}(B,M)$ seconds, the server collects $B$ stochastic gradients. It is equivalent to calculating $x^{k+1},\dots,x^{k+B},$ which contradicts the assumption.
∎

###### Proof of Theorem F.11 .

Due to Theorem [E.6](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem6), we know that
$\frac{1}{K}\sum_{k=0}^{K-1}{\mathbb{E}}\left[\|\nabla f(x^{k})\|^{2}\right]\leq\varepsilon$ for

$$ $K=\left\lceil\frac{4(B+M-1)L\Delta}{\varepsilon}+\frac{8\sigma^{2}L\Delta}{ \varepsilon^{2}}\right\rceil.$ $$

From Lemma [F.2](https://arxiv.org/html/2505.09218v2#A6.Thmtheorem2), we know that the time required to calculate $x^{1},\dots,x^{B}$ of the main branch is at most $T_{\textnormal{AL}}(B,M)$ seconds, the time required to calculate $x^{B+1},\dots,x^{2B}$ is at most $T_{\textnormal{AL}}(B,M)$ seconds, and so on. Thus, the total time to find an $\varepsilon$–stationary point is

$$ $\displaystyle\mathcal{O}\left(T_{\textnormal{AL}}(B,M)\times\frac{K}{B}\right) =\mathcal{O}\left(T_{\textnormal{AL}}(B,M)\times\left(\frac{L\Delta(B+M)}{B \varepsilon}+\frac{\sigma^{2}L\Delta}{B\varepsilon^{2}}\right)\right).$ $$

Using the choice of $B$ and $M,$ we obtain $M\leq B$ and

$$ $\displaystyle\mathcal{O}\left(T_{\textnormal{R}}(B)\times\frac{K}{B}\right)$ $\displaystyle=\mathcal{O}\left(T_{\textnormal{AL}}(B,M)\times\left(\frac{L \Delta}{\varepsilon}+\frac{\sigma^{2}L\Delta}{B\varepsilon^{2}}\right)\right)$ $\displaystyle=\mathcal{O}\left(\min_{m\in[n]}\left[\left(\sum_{i=1}^{m}\frac{1 }{h_{i}}\right)^{-1}(B+Mm)\right]\times\left(\frac{L\Delta}{\varepsilon}+\frac {\sigma^{2}L\Delta}{B\varepsilon^{2}}\right)\right)$ $\displaystyle=\mathcal{O}\left(\min_{m\in[n]}\left[\left(\sum_{i=1}^{m}\frac{1 }{h_{i}}\right)^{-1}(B+Mm)\right]\times\frac{L\Delta}{\varepsilon}\right)$ $$

because $B\geq\frac{\sigma^{2}}{\varepsilon}.$ Since $M\leq\frac{\sigma^{2}}{n\varepsilon}+1$ and $B\leq\frac{\sigma^{2}}{\varepsilon}+1,$

$$ $\displaystyle\mathcal{O}\left(T_{\textnormal{R}}(B)\times\frac{K}{B}\right)$ $\displaystyle=\mathcal{O}\left(\min_{m\in[n]}\left[\left(\sum_{i=1}^{m}\frac{1 }{h_{i}}\right)^{-1}\left(1+\frac{\sigma^{2}}{\varepsilon}+m+\frac{m\sigma^{2} }{n\varepsilon}\right)\right]\times\frac{L\Delta}{\varepsilon}\right)$ $\displaystyle=\mathcal{O}\left(\min_{m\in[n]}\left[\left(\sum_{i=1}^{m}\frac{1 }{h_{i}}\right)^{-1}\left(\frac{\sigma^{2}}{\varepsilon}+m\right)\right]\times \frac{L\Delta}{\varepsilon}\right)$ $\displaystyle=\mathcal{O}\left(\min_{m\in[n]}\left[\left(\frac{1}{m}\sum_{i=1} ^{m}\frac{1}{h_{i}}\right)^{-1}\left(\frac{L\Delta}{\varepsilon}+\frac{\sigma^ {2}L\Delta}{m\varepsilon^{2}}\right)\right]\right),$ $$

where we use that $m\leq n$ for all $m\in[n].$
∎

###### Theorem F.11 ( Async-Local SGD ) .

###### Lemma F.12 .

###### Proof.

###### Proof of Theorem F.11 .

### F.7 Cycle SGD

###### Theorem F.13 ( Cycle SGD ) .

Consider Theorem [E.5](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem5) and its conditions. Under the $h_{i}$-fixed computation model ([20](https://arxiv.org/html/2505.09218v2#A6.E20)), the computational time complexity of Cycle SGD (Alg. [8](https://arxiv.org/html/2505.09218v2#alg8)) is

$$ $\displaystyle\mathcal{O}\left(\max\limits_{i\in[n]}h_{i}\left(\frac{L\Delta}{ \varepsilon}+\frac{\sigma^{2}L\Delta}{m\varepsilon^{2}}\right)\right)$ $$

with $s=\min\left\{\max\left\{\left\lceil\frac{n^{2}\varepsilon}{\sigma^{2}}\right
\rceil,1\right\},n\right\}.$

###### Proof.

According to Theorem [E.5](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem5),
$\frac{1}{K}\sum_{k=0}^{K-1}{\mathbb{E}}\left[\|\nabla f(x^{k})\|^{2}\right]\leq\varepsilon$ for

$$ $K=\left\lceil\frac{8n^{2}L\Delta}{s\varepsilon}+\frac{8\sigma^{2}L\Delta}{ \varepsilon^{2}}\right\rceil.$ $$

In the beginning, the algorithm has “warm-up”, where, in the first iteration of the inner loop, the server collects $s$ stochastic gradients from $s$ workers, which is equivalent to calculating $x^{1},\dots,x^{s}$ of the main branch. Then, the server collects $2s$ stochastic gradients from the next group of $s$ workers because they calculated $s$ stochastic in the previous iteration. Starting from the $\left\lceil\frac{n}{s}\right\rceil$^th iteration, each group of $s$ workers will return $s\times\left\lceil\frac{n}{s}\right\rceil$ stochastic gradients in every subsequent iteration. Every iterations takes at most $\max\limits_{i\in[n]}h_{i}$ seconds, because they work in parallel and calculate one stochastic gradient.

Thus, the total time to calculate $x^{1},\dots,x^{K}$ and find an $\varepsilon$–stationary point is

$$ $\displaystyle\mathcal{O}\left(\underbrace{\max\limits_{i\in[n]}h_{i}\times \left\lceil\frac{n}{s}\right\rceil}_{\textnormal{``warm-up'' phase}}+\max \limits_{i\in[n]}h_{i}\times\frac{K}{\left(s\times\left\lceil\frac{n}{s}\right \rceil\right)}\right)$ $\displaystyle=\mathcal{O}\left(\max\limits_{i\in[n]}h_{i}\times\frac{n}{s}+ \max\limits_{i\in[n]}h_{i}\times\left(\frac{nL\Delta}{s\varepsilon}+\frac{ \sigma^{2}L\Delta}{n\varepsilon^{2}}\right)\right)$ $\displaystyle=\mathcal{O}\left(\max\limits_{i\in[n]}h_{i}\times\left(\frac{nL \Delta}{s\varepsilon}+\frac{\sigma^{2}L\Delta}{n\varepsilon^{2}}\right)\right).$ $$

because $\frac{L\Delta}{\varepsilon}\geq\frac{1}{2}$ without loss of generality (if $\frac{L\Delta}{\varepsilon}<\frac{1}{2},$ then $x^{0}$ is an $\varepsilon$–stationary point). Finally,

$$ $\displaystyle\mathcal{O}\left(\max\limits_{i\in[n]}h_{i}\times\left(\frac{nL \Delta}{s\varepsilon}+\frac{\sigma^{2}L\Delta}{n\varepsilon^{2}}\right)\right) =\mathcal{O}\left(\max\limits_{i\in[n]}h_{i}\times\left(\frac{L\Delta}{ \varepsilon}+\frac{\sigma^{2}L\Delta}{n\varepsilon^{2}}\right)\right)$ $$

due to the choice of $s.$

∎

###### Theorem F.13 ( Cycle SGD ) .

###### Proof.

### F.8 Dual-Process SGD

###### Theorem F.14 ( Dual-Process SGD ) .

Consider Theorem [E.11](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem11) and its conditions. Under the $h_{i}$-fixed computation model ([20](https://arxiv.org/html/2505.09218v2#A6.E20)), the computational time complexity of Dual-Process SGD (Alg. [18](https://arxiv.org/html/2505.09218v2#alg18)) is

$$ $\displaystyle\mathcal{O}\left(\min\limits_{m\in[n]}\left[\left(\frac{1}{m}\sum \limits_{i=1}^{m}\frac{1}{h_{i}}\right)^{-1}\left(\frac{L\Delta}{\varepsilon}+ \frac{\sigma^{2}L\Delta}{m\varepsilon^{2}}\right)\right]\right)$ $$

with $B=\max\left\{\left\lceil\frac{\sigma^{2}}{\varepsilon}\right\rceil,1\right\}.$

###### Proof.

The proof is essentially the same as the proof of Theorem [F.6](https://arxiv.org/html/2505.09218v2#A6.Thmtheorem6) since Dual-Process SGD is equivalent to Local SGD if the communication times are ignored.
∎

###### Theorem F.14 ( Dual-Process SGD ) .

###### Proof.

## Appendix G Total Time Complexities of Algorithms under ( h , τ ) ℎ 𝜏 (h,\tau) ( italic_h , italic_τ ) -Fixed Computation Model

To compare the communication complexities and the total time complexities of the methods, we now assume that it takes $\tau$ seconds to send a vector from a worker to a parameter server and $\tau$ seconds to send a vector from the server to the workers in the centralized setting. Alternatively, it takes $\tau$ seconds to send a vector to all other workers in the decentralized setting. Moreover, we assume that all workers have the same computational performance: worker $i$ takes $h$ seconds to compute a single stochastic gradient for all $i\in[n]$. We refer to this as the *$(h,\tau)$-fixed computation model*.

Note that it is possible to assume that each worker has its own communication time bound $\tau_{i}$ and computation time bound $h_{i}$ and consider *$(h_{i},\tau_{i})$-fixed computation model* (Tyurin et al.,, 2024). However, for simplicity, we assume $\tau_{i}=\tau$ and $h_{i}=h$ for all $i\in[n].$ See Section [H](https://arxiv.org/html/2505.09218v2#A8) for a more general case *$(h_{i},\tau_{i})$-fixed computation model*.

### G.1 Rennala SGD

###### Theorem G.1 .

Consider Theorem [E.2](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem2) and its conditions. Under $(h,\tau)$-fixed computation model, the total time complexity of Rennala SGD (Alg. [4](https://arxiv.org/html/2505.09218v2#alg4)) is

$$ $\displaystyle\mathcal{O}\left(\tau\times\frac{L\Delta}{\varepsilon}+h\times \left(\frac{L\Delta}{\varepsilon}+\frac{\sigma^{2}L\Delta}{n\varepsilon^{2}} \right)\right)$ $$

with $B=\max\left\{\left\lceil\frac{\sigma^{2}}{\varepsilon}\right\rceil,1\right\}.$

###### Proof.

Note that the communication between of vectors happens every $B$ calculated stochastic gradients, which is equivalent to every $B$ updates of the main branch. Thus the total number of communications is

$$ $\displaystyle\mathcal{O}\left(\frac{K}{B}\right),$ $$

where $K=\Theta\left(\frac{BL\Delta}{\varepsilon}+\frac{\sigma^{2}L\Delta}{
\varepsilon^{2}}\right)$ due to Theorem [E.2](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem2). The total communication complexity is

$$ $\displaystyle\mathcal{O}\left(\tau\times\frac{K}{B}\right)=\mathcal{O}\left( \frac{\tau}{B}\times\left(\frac{BL\Delta}{\varepsilon}+\frac{\sigma^{2}L\Delta }{\varepsilon^{2}}\right)\right)=\mathcal{O}\left(\tau\times\frac{L\Delta}{ \varepsilon}\right),$ $$

where we use the choice of $B.$ It left to take into account the computation factor, which is the same as in Theorem [F.1](https://arxiv.org/html/2505.09218v2#A6.Thmtheorem1).

$$ $\displaystyle\eqref{eq:MFvzCXtfgWSefbzZ}=\mathcal{O}\left(h\times\left(\frac{L \Delta}{\varepsilon}+\frac{\sigma^{2}L\Delta}{n\varepsilon^{2}}\right)\right)$ $$

under the $(h,\tau)$-fixed computation model.
∎

###### Theorem G.1 .

###### Proof.

### G.2 Local SGD

###### Theorem G.2 .

Consider Theorem [E.3](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem3) and its conditions. Under $(h,\tau)$-fixed computation model, the total time complexity of Local SGD (Alg. [5](https://arxiv.org/html/2505.09218v2#alg5)) is

$$ $\displaystyle\mathcal{O}\left(\tau\times\frac{L\Delta}{\varepsilon}+h\times \left(\frac{L\Delta}{\varepsilon}+\frac{\sigma^{2}L\Delta}{n\varepsilon^{2}} \right)\right)$ $$

with $B=\max\left\{\left\lceil\frac{\sigma^{2}}{\varepsilon}\right\rceil,1\right\}.$

###### Proof.

The proof essentially the same as the proof of Theorem [G.1](https://arxiv.org/html/2505.09218v2#A7.Thmtheorem1).
∎

###### Theorem G.2 .

###### Proof.

### G.3 Cycle SGD

###### Theorem G.3 .

Consider Theorem [E.5](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem5) and its conditions. Under $(h,\tau)$-fixed computation model, the total time complexity of Cycle SGD (Alg. [8](https://arxiv.org/html/2505.09218v2#alg8)) is

$$ $\displaystyle\mathcal{O}\left(\tau\times\left(\frac{L\Delta}{\varepsilon}+ \frac{\sigma^{2}L\Delta}{n\varepsilon^{2}}\right)+h\times\left(\frac{L\Delta}{ \varepsilon}+\frac{\sigma^{2}L\Delta}{n\varepsilon^{2}}\right)\right)$ $$

with $s=\min\left\{\max\left\{\left\lceil\frac{n^{2}\varepsilon}{\sigma^{2}}\right
\rceil,1\right\},n\right\}.$

###### Proof.

Similarly to the proof of Theorem [F.13](https://arxiv.org/html/2505.09218v2#A6.Thmtheorem13), one can show that the total time complexity is

$$ $\displaystyle\mathcal{O}\left(\underbrace{(\tau+h)\times\left\lceil\frac{n}{s} \right\rceil}_{\textnormal{``warm-up'' phase}}+(\tau+h)\times\frac{K}{\left(s \times\left\lceil\frac{n}{s}\right\rceil\right)}\right)$ $$

because every worker from group $s$ sends one vector $\sum_{j=1}^{M_{i}}\nabla f(z^{j}_{i};\eta^{j}_{i})$ to the server in the inner loop.
Substituting the choice of $s,$ one can get the final result.
∎

###### Theorem G.3 .

###### Proof.

### G.4 Async-Local SGD

###### Theorem G.4 .

Consider Theorem [E.6](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem6) and its conditions. Under $(h,\tau)$-fixed computation model, the total time complexity of Async-Local SGD (Alg. [9](https://arxiv.org/html/2505.09218v2#alg9)) is

$$ $\displaystyle\mathcal{O}\left(\tau\times\frac{L\Delta}{\varepsilon}+h\times \left(\frac{L\Delta}{\varepsilon}+\frac{\sigma^{2}L\Delta}{n\varepsilon^{2}} \right)\right)$ $$

with $B=\max\left\{\left\lceil\frac{\sigma^{2}}{\varepsilon}\right\rceil,1\right\}$ and $M=\max\left\{\left\lceil\frac{\sigma^{2}}{n\varepsilon}\right\rceil,1\right\}.$

###### Proof.

Under $(h,\tau)$-fixed computation model, all workers send the sums of $M$ stochastic gradients at the same time. According to Theorem [E.6](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem6), the server should collect

$$ $\displaystyle\mathcal{O}\left(\frac{(B+M-1)L\Delta}{\varepsilon}+\frac{\sigma^ {2}L\Delta}{\varepsilon^{2}}\right)=\mathcal{O}\left(\frac{L\Delta}{ \varepsilon}+\frac{\sigma^{2}L\Delta}{\varepsilon^{2}}\right)$ $$

stochastic gradients, where the last equality due to the choice of $B$ and due to $B\geq M.$ Since the workers work in parallel and have the equal performance, only $\Theta\left(\min\left\{\frac{B}{M},n\right\}\right)=\Theta\left(\min\left\{
\max\left\{1,\frac{\sigma^{2}}{M\varepsilon}\right\},n\right\}\right)$ workers will participate in optimization. Thus, every worker, which participates in optimization, has to send

$$ $\displaystyle\mathcal{O}\left(\frac{L\Delta}{\min\left\{\frac{B}{M},n\right\} \varepsilon}+\frac{\sigma^{2}L\Delta}{\min\left\{\frac{B}{M},n\right\} \varepsilon^{2}}\right)=\mathcal{O}\left(\frac{L\Delta}{\varepsilon}+\frac{ \sigma^{2}L\Delta}{n\varepsilon^{2}}+\frac{ML\Delta}{\varepsilon}\right)$ $$

stochastic gradients. Such a worker calculates $M$ stochastic gradients and only then sends the sum; thus, the maximum number of communications by one worker is

$$ $\displaystyle\mathcal{O}\left(\frac{L\Delta}{M\varepsilon}+\frac{\sigma^{2}L \Delta}{Mn\varepsilon^{2}}+\frac{L\Delta}{\varepsilon}\right).$ $$

For every communication, the worker needs to send $M$ stochastic gradients, which takes $h$ seconds, and sends a sum, which takes $\tau$ seconds. Thus, the total time complexity is

$$ $\displaystyle\mathcal{O}\left(\left(\tau+Mh\right)\left(\frac{L\Delta}{M \varepsilon}+\frac{\sigma^{2}L\Delta}{Mn\varepsilon^{2}}+\frac{L\Delta}{ \varepsilon}\right)\right).$ (33) $$

Substituting the choice of $M,$ we get the final result.
∎

###### Theorem G.4 .

###### Proof.

### G.5 Ringmaster ASGD

###### Theorem G.5 .

Consider Theorem [E.4](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem4) and its conditions. Under $(h,\tau)$-fixed computation model, the total time complexity of Ringmaster ASGD is

$$ $\displaystyle\mathcal{O}\left(\tau\times\left(\frac{L\Delta}{\varepsilon}+ \frac{\sigma^{2}L\Delta}{n\varepsilon^{2}}\right)+h\times\left(\frac{L\Delta}{ \varepsilon}+\frac{\sigma^{2}L\Delta}{n\varepsilon^{2}}\right)\right)$ (34) $$

with $B=\max\left\{\left\lceil\frac{\sigma^{2}}{\varepsilon}\right\rceil,1\right\}.$

###### Proof.

The proof repeats the proof of Theorem [G.4](https://arxiv.org/html/2505.09218v2#A7.Thmtheorem4). The only difference is that the workers send $M=1$ stochastic gradients. Substituting $M=1$ to ([33](https://arxiv.org/html/2505.09218v2#A7.E33)), we get the final result.
∎

###### Remark G.6 .

While ([34](https://arxiv.org/html/2505.09218v2#A7.E34)) is only an upper bound, using the same steps as in the proof of Theorem [G.4](https://arxiv.org/html/2505.09218v2#A7.Thmtheorem4), one can easily show that the total time complexity of Ringmaster ASGD is lower bounded by

$$ $\displaystyle\Omega\left(\tau\times\left(\frac{L\Delta}{\varepsilon}+\frac{ \sigma^{2}L\Delta}{n\varepsilon^{2}}\right)+h\times\left(\frac{L\Delta}{ \varepsilon}+\frac{\sigma^{2}L\Delta}{n\varepsilon^{2}}\right)\right),$ (35) $$

assuming that the iteration rate $\Theta\left(\frac{BL\Delta}{\varepsilon}+\frac{\sigma^{2}L\Delta}{\varepsilon^
{2}}\right)$ from Theorem [E.4](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem4) is tight. As far as we know, this is the current state-of-the-art iteration rate of an Asynchronous SGD-like method (Maranjyan et al.,, 2025; Mishchenko et al.,, 2022; Koloskova et al.,, 2022; Cohen et al.,, 2021).

###### Theorem G.5 .

###### Proof.

###### Remark G.6 .

## Appendix H Total Time Complexities of Algorithms under ( h i , τ i ) subscript ℎ 𝑖 subscript 𝜏 𝑖 (h_{i},\tau_{i}) ( italic_h start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT , italic_τ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) -Fixed Computation Model

We now assume that each worker has its own communication time bound $\tau_{i}$ and computation time bound $h_{i}$ and consider *the $(h_{i},\tau_{i})$-fixed computation model* (Tyurin et al.,, 2024). It takes $\tau_{i}$ seconds to send a vector from worker $i$ to a parameter server and $\tau_{i}$ seconds to send a vector from the server to worker $i$ in the centralized setting. Alternatively, it takes $\tau_{i}$ seconds to send a vector to all other workers in the decentralized setting.

This setting reduces to $h_{i}$-fixed computation model when $\tau_{i}=0$ for all $i\in[n],$ and reduces to $(h,\tau)$-fixed computation model when $h_{i}=h$ and $\tau_{i}=\tau$ for all $i\in[n].$ Without loss of generality, we assume that $\max\{h_{1},\tau_{1}\}\leq\dots\leq\max\{h_{n},\tau_{n}\}.$ 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 $\max_{i\in[n]}\tau_{i}\to\infty,$ then their total complexity tends to $\infty.$ Thus, they are suboptimal under the $(h_{i},\tau_{i})$-fixed computation model. Ringmaster ASGD is suboptimal even under the $(h,\tau)$-fixed computation model. Async-Local SGD and Async-Batch SGD are optimal under the $(h,\tau)$-fixed computation model, but we conjecture that they are suboptimal under the $(h_{i},\tau_{i})$-fixed computation model.

We now prove that Dual-Process SGD is optimal under the $(h_{i},\tau_{i})$-fixed computation model.

### H.1 Dual-Process SGD

###### Theorem H.1 ( Dual-Process SGD ) .

Consider Theorem [E.11](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem11) and its conditions. Under the $(h_{i},\tau_{i})$-fixed computation model, the total time complexity of Dual-Process SGD (Alg. [18](https://arxiv.org/html/2505.09218v2#alg18)) is

$$ $\displaystyle\mathcal{O}\left(\min\limits_{m\in[n]}\left[\max\left\{\max\{h_{m },\tau_{m}\},\left(\sum\limits_{i=1}^{m}\frac{1}{h_{i}}\right)^{-1}\frac{ \sigma^{2}}{\varepsilon}\right\}\right]\frac{L\Delta}{\varepsilon}\right)$ $$

with $B=\max\left\{\left\lceil\frac{\sigma^{2}}{\varepsilon}\right\rceil,1\right\}.$

This complexity is optimal for methods without compression (Tyurin et al.,, 2024; Tyurin and Richtárik,, 2024). Notice that it is robust to slow communications. Indeed, if $\tau_{n}\to\infty,$ then this complexity will ignore worker $n$ due to the $\min\limits_{m\in[n]}$ operation.

###### Lemma H.2 .

Let us define

$$ $\displaystyle T(B):=4\min\limits_{m\in[n]}\left[\max\left\{\max\{h_{m},\tau_{m }\},\left(\sum\limits_{i=1}^{m}\frac{1}{h_{i}}\right)^{-1}B\right\}\right].$ (36) $$

Under the $(h_{i},\tau_{i})$-fixed computation model, the time required to calculate $x^{1},\dots,x^{B}$ of the main branch is at most $3T(B)$ seconds, the time required to calculate $x^{B+1},\dots,x^{2B}$ is at most $3T(B)$ seconds, and so on.

###### Proof.

Notice that

$$ $\displaystyle T(B)=4\max\left\{\max\{h_{m^{*}},\tau_{m^{*}}\},\left(\sum \limits_{i=1}^{{m^{*}}}\frac{1}{h_{i}}\right)^{-1}B\right\}.$ $$

for some $m^{*}\in[n].$
The idea is similar as in Lemmas [F.2](https://arxiv.org/html/2505.09218v2#A6.Thmtheorem2) and [F.7](https://arxiv.org/html/2505.09218v2#A6.Thmtheorem7). All workers calculate stochastic gradients in parallel. For all $t\geq 0,$ after $t$ seconds the first $m^{*}$ workers can calculate at at least

$$ $\displaystyle\sum_{i=1}^{m^{*}}\max\left\{\left\lfloor\frac{t}{h_{i}}\right \rfloor-1,0\right\},$ (37) $$

stochastic gradients, where we subtract $1$ because at most one stochastic gradient can be ignored.
Substituting $T(B)$ into ([37](https://arxiv.org/html/2505.09218v2#A8.E37)), we have

$$ $\displaystyle\sum_{i=1}^{m^{*}}\max\left\{\left\lfloor\frac{T(B)}{h_{i}}\right \rfloor-1,0\right\}\geq\sum_{i=1}^{m^{*}}\left\lfloor\frac{T(B)}{h_{i}}\right \rfloor-m^{*}\geq\sum_{i=1}^{m^{*}}\frac{T(B)}{h_{i}}-2m^{*}.$ $$

Recall that $\max\{h_{1},\tau_{1}\}\leq\dots\leq\max\{h_{m^{*}},\tau_{m^{*}}\}.$ Thus,

$$ $\displaystyle T(B)\geq 2\max\{h_{m^{*}},\tau_{m^{*}}\}+2\left(\sum\limits_{i=1 }^{{m^{*}}}\frac{1}{h_{i}}\right)^{-1}B\geq 2h_{i}+2\left(\sum\limits_{i=1}^{{ m^{*}}}\frac{1}{h_{i}}\right)^{-1}B$ $$

for all $i\leq m^{*},$ and

$$ $\displaystyle\sum_{i=1}^{m^{*}}\max\left\{\left\lfloor\frac{T(B)}{h_{i}}\right \rfloor-1,0\right\}\geq\sum_{i=1}^{m^{*}}\left(2+\frac{2}{h_{i}}\left(\sum \limits_{i=1}^{{m^{*}}}\frac{1}{h_{i}}\right)^{-1}B\right)-2m^{*}\geq B.$ $$

Thus, by the time $T(B),$ the first $m^{*}$ workers can calculate $B$ stochastic gradients.

Next, we need to estimate the communication time. It takes at most $\max_{i\in[m^{*}]}\tau_{i}\leq\max\{h_{m^{*}},\tau_{m^{*}}\}\leq T(B)$ seconds to receive a vector from the server (in the decentralized setting, we do not account this time). Similarly, it takes at most $\max_{i\in[m^{*}]}\tau_{i}\leq T(B)$ seconds to send a vector to the server (in the decentralized setting, to send a vector to other workers). Thus, one round in Alg [18](https://arxiv.org/html/2505.09218v2#alg18) takes at most $3\times T(B)$ seconds, which is equivalent to calculating $x^{1},\dots,x^{B}$ of the main branch. The same argument can be applied to the next $B$ point of the main branch, and so on.
∎

###### Proof of Theorem H.1 .

The proof is similar to the proof of Lemma [F.2](https://arxiv.org/html/2505.09218v2#A6.Thmtheorem2). Due to Theorem [E.2](https://arxiv.org/html/2505.09218v2#A5.Thmtheorem2), we know that
$\frac{1}{K}\sum_{k=0}^{K-1}{\mathbb{E}}\left[\|\nabla f(x^{k})\|^{2}\right]\leq\varepsilon$ for

$$ $K=\left\lceil\frac{4BL\Delta}{\varepsilon}+\frac{8\sigma^{2}L\Delta}{ \varepsilon^{2}}\right\rceil.$ $$

Using Lemma [H.2](https://arxiv.org/html/2505.09218v2#A8.Thmtheorem2), the total time to find an $\varepsilon$–stationary point is

$$ $\displaystyle\mathcal{O}\left(T(B)\times\frac{K}{B}\right)=\mathcal{O}\left(T( B)\times\left(\frac{L\Delta}{\varepsilon}+\frac{\sigma^{2}L\Delta}{B \varepsilon^{2}}\right)\right).$ $$

Using the choice of $B,$

$$ $\displaystyle\mathcal{O}\left(T(B)\times\frac{K}{B}\right)$ $\displaystyle=\mathcal{O}\left(\min\limits_{m\in[n]}\left[\max\left\{\max\{h_{ m},\tau_{m}\},\left(\sum\limits_{i=1}^{m}\frac{1}{h_{i}}\right)^{-1}\frac{ \sigma^{2}}{\varepsilon}\right\}\right]\times\frac{L\Delta}{\varepsilon}\right).$ $$

∎

###### Theorem H.1 ( Dual-Process SGD ) .

###### Lemma H.2 .

###### Proof.

###### Proof of Theorem H.1 .

## Appendix I Performance of Rennala SGD and Ringmaster ASGD on a Quadratic Function

In this section, we formally prove that the convergence of Ringmaster ASGD can be provably faster than Rennala SGD due to the frequent model updates.

###### Theorem I.1 .

Consider Rennala SGD (Alg. [4](https://arxiv.org/html/2505.09218v2#alg4)) and Ringmaster ASGD (Alg. [7](https://arxiv.org/html/2505.09218v2#alg7)) with the optimal parameters $B$ from Sec. [F](https://arxiv.org/html/2505.09218v2#A6).
Then, there exists a $\mu$-strongly convex function and corresponding stochastic gradients that satisfy Assumptions [1.1](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem1), [1.2](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem2), and [1.3](https://arxiv.org/html/2505.09218v2#S1.Thmtheorem3) with $\nicefrac{{\sigma^{2}}}{{\varepsilon}}\geq n$, such that Rennala SGD, with any step size $\gamma,$ requires

$$ $\displaystyle\widetilde{\Theta}\left({\color[rgb]{1,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{1,0,0}\frac{\sigma^{2}}{n\varepsilon}}\times h\times\frac {L}{\mu}\right)$ $$

seconds to find $\varepsilon$-stationary point under the $h_{i}$-fixed computation model ([20](https://arxiv.org/html/2505.09218v2#A6.E20)) with $h_{i}=h$ for all $i\in[n].$ At the same time, there exists a step size for Ringmaster ASGD such that it requires at most

$$ $\displaystyle\widetilde{\mathcal{O}}\left(h\times\frac{L}{\mu}\right)$ $$

seconds to find $\varepsilon$-stationary point.

###### Proof.

In this construction, we take $f:\mathbb{R}^{2}\to\mathbb{R}$ such that

$$ $\displaystyle f(w\equiv(x,y))=\frac{\mu x^{2}}{2}+\frac{Ly^{2}}{2}$ (38) $$

for all $x,y\in\mathbb{R}$. Moreover, we assume that the stochastic gradients $\nabla f(w;\xi)$ are equal to the true gradient $\nabla f(w)$; thus, there is no randomness. Note that *a priori*, both methods do not have this information and therefore must choose $B=\Theta\left(\frac{\sigma^{2}}{\varepsilon}\right),$ even though the effective variance is zero.

By the design of Rennala SGD, its algorithm is equivalent to the following steps:

$$ $\displaystyle w^{t+1}=w^{t}-\gamma B\nabla f(w^{t})$ (39) $$

because the workers calculate $B$ gradients in every global round. Each round takes

$$ $\displaystyle\Theta\left(h\times\frac{B}{n}\right)=\Theta\left(h\frac{\sigma^{ 2}}{n\varepsilon}\right)$ $$

seconds, because the workers have the computation speed $h$ and $B=\Theta\left(\frac{\sigma^{2}}{\varepsilon}\right)$ in Theorem [F.1](https://arxiv.org/html/2505.09218v2#A6.Thmtheorem1).

It is well known that the sequence ([39](https://arxiv.org/html/2505.09218v2#A9.E39)) requires

$$ $\displaystyle\widetilde{\Theta}\left(\frac{L}{\mu}\right)$ $$

iterations (up to logarithmic factors) to find an $\varepsilon$-solution or $\varepsilon$-stationary point with the function ([38](https://arxiv.org/html/2505.09218v2#A9.E38)), even when the step size $\gamma$ can be tuned. Thus, the computational time complexity of Rennala SGD is

$$ $\displaystyle\widetilde{\Theta}\left(\frac{\sigma^{2}}{n\varepsilon}\times h \times\frac{L}{\mu}\right)$ $$

seconds.

Consider now the steps of Ringmaster ASGD w.r.t. the first argument $x$. In this algorithm, we take $\gamma=\frac{1}{2Ln}.$ In the case when the computation time is equal for all workers, the first $n$ steps are

$$ $\displaystyle x^{1}=x^{0}-\gamma\mu x^{0}=(1-\gamma\mu)x^{0},$ $\displaystyle x^{2}=x^{1}-\gamma\mu x^{0}=(1-2\gamma\mu)x^{0},$ $\displaystyle\vdots$ $\displaystyle x^{n}=x^{n-1}-\gamma\mu x^{0}=(1-n\gamma\mu)x^{0},$ $$

because the workers start calculating at the same point and return the gradients at the same time. Notice that $0\leq x^{n}\leq\dots\leq x^{2}\leq x^{1}.$ Then, the first worker starts calculating at $x^{1},$ the seconds worker starts calculating at $x^{2},$ and so on. Therefore, the next steps are

$$ $\displaystyle x^{n+1}$ $\displaystyle=x^{n}-\gamma\mu x^{1}$ $\displaystyle=(1-n\gamma\mu)x^{0}-\gamma\mu(1-\gamma\mu)x^{0}=(1-(n+1)\gamma \mu+\gamma^{2}\mu^{2})x^{0},$ $\displaystyle x^{n+2}$ $\displaystyle=x^{n+1}-\gamma\mu x^{2}$ $\displaystyle=(1-(n+1)\gamma\mu+\gamma^{2}\mu^{2})x^{0}-\gamma\mu(1-2\gamma\mu )x^{0}=(1-(n+2)\gamma\mu+3\gamma^{2}\mu^{2})x^{0},$ $\displaystyle\vdots$ $\displaystyle x^{2n}$ $\displaystyle=x^{2n-1}-\gamma\mu x^{n}=\left(1-2n\gamma\mu+\frac{n(n+1)}{2} \gamma^{2}\mu^{2}\right)x^{0}\leq\left(1-n\gamma\mu\right)^{2}x^{0}.$ $$

For $\gamma=\nicefrac{{1}}{{2Ln}},$ we have $0\leq x^{2n}\leq\dots\leq x^{n+1}\leq x^{n}\leq\dots\leq x^{2}\leq x^{1}.$
Using mathematical induction, assume that $0\leq x^{kn}\leq\dots\leq x^{1}$ for some $k\geq 1$ and $x^{pn}\leq\left(1-n\gamma\mu\right)^{p}x^{0}$ for all $p\leq k,$ which is true for $k=2$ (base case). We now prove it for $k+1.$ Ringmaster ASGD calculates $x^{kn+1}$ as follows:

$$ $\displaystyle x^{kn+1}$ $\displaystyle=x^{kn}-\gamma\mu x^{(k-1)n+1},$ $$

which ensures that $x^{kn+1}\leq(1-\gamma\mu)x^{kn}\leq x^{kn}$ and $x^{kn+1}\geq x^{(k-1)n+1}-\gamma\mu x^{(k-1)n+1}\geq 0$ for $\gamma=\nicefrac{{1}}{{2Ln}}.$ We can continue:

$$ $\displaystyle x^{kn+2}$ $\displaystyle=x^{kn+1}-\gamma\mu x^{(k-1)n+2},$ $$

which ensures that

$$ $\displaystyle x^{kn+2}$ $\displaystyle\leq x^{kn+1}-\gamma\mu x^{kn}\leq(1-\gamma\mu)x^{kn}-\gamma\mu x ^{kn}=(1-2\gamma\mu)x^{kn}$ $$

and $x^{kn+2}\geq x^{(k-1)n+2}-\gamma\mu x^{(k-1)n+2}.$ Continuing, we have

$$ $\displaystyle x^{(k+1)n}=x^{(k+1)n-1}-\gamma\mu x^{kn}.$ $$

One can show that

$$ $\displaystyle x^{(k+1)n}\leq(1-(n-1)\gamma\mu)x^{kn}-\gamma\mu x^{kn}\leq(1-n \gamma\mu)x^{kn},$ $$

and $x^{(k+1)n}\geq x^{kn}-\gamma\mu x^{kn}\geq 0.$ We have proved the next case, $k+1,$ of the mathematical induction.

Thus, the sequence $\{x^{pn}\}_{p\geq 2}$ monotonically decreases with the rate

$$ $\displaystyle x^{pn}\leq\left(1-n\gamma\mu\right)^{p}x^{0}.$ $$

Using the same reasoning, we one can show the similar result holds for the second argument $y$ of the function but with $L$ instead of $\mu.$

Recall that it takes $h$ seconds to calculate $x^{n}$ because $n$ workers work in parallel, it takes $h$ seconds to calculate $x^{2n},$ and so on. Thus, the computational time complexity of Ringmaster ASGD is

$$ $\displaystyle\widetilde{\mathcal{O}}\left(h\times\frac{L}{\mu}\right)$ $$

with step size $\gamma=\frac{1}{2Ln}.$
∎

###### Theorem I.1 .

###### Proof.

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 4
presentation: 2
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).
2. 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.
3. In table 1, why does local SGD listed as new? It is not a new algorithm.
soundness: 2
strengths: - The idea of framing distributed SGD algorithms as a directed tree is very novel and interesting.
- The unified convergence analysis is also solid and clean.
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.
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).

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 4
questions: What about non-iid data? Could we add a measure of heterogeneity in the analysis?
soundness: 4
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.
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.
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.

It 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). 

Some 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.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
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?

- 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?

- 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.

- 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?
soundness: 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.
- 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.
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.
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?

- 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.

- 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.

- 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.

- 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.


Decision: Accept (Poster)