A Bias Correction Mechanism for Distributed Asynchronous Optimization
Authors: Yuan Gao
Yuki Takezawa
Sebastian U Stich
Venue: Accepted by TMLR ()

Abstract: We develop an asynchronous gradient method for training Machine Learning models with asynchronous distributed workers, each with its own communication and computation pace, and its own local data distribution. In the modern distributed machine learning training process, local data distribution across workers is often heterogeneous (a.k.a. client bias), which is a significant limiting factor in the analysis of most existing distributed asynchronous optimization methods. In this work, we propose AsyncBC, a distributed asynchronous variant of the SARAH method, and show that this is an effective Bias Correction mechanism for distributed asynchronous optimization. We show that AsyncBC can effectively manage arbitrary data heterogeneity, as well as handle gradient updates that arrive in an uncoordinated manner and with delays. As a byproduct of our analysis, we also provide a deeper understanding of the impacts of different stochasticity models on the convergence of the SARAH method.

Published in Transactions on Machine Learning Research (10/2025)
A Bias Correction Mechanism for Distributed Asynchronous Optimization
Yuan Gao
paan-gao@icispa
CISPA Helmholtz Center for Information Security Universität des Suorlandes
Yuki Takezawa
yuki-ttakezawoo@mi.. ist. ist. wtt..ii..oo.oooa......
Kyoto University
OIST
Sebastian Stich
stich@cispa.de de
CISPA Helmholtz Center for Information Security
Reviewed on OpenReview: https: // wwwnreview.ned net/forumm
forum? id=
8doMb
Abstract
We develop an asynchronous gradient method for training Machine Learning models with asynchronous distributed workers, each with its own commmicatiin and computation pace, and its own local data distribution. In the modern distribuled machine learning training process, local data distribution across workers often heterogeneous (a.k.a. client bias), which is significant limiting factor in the analysis of most existing distributed asynchronous optimization methods. In this work, propose AsyncBC, distributed asynchronous variant of the SARAH (Nguyen et al., 2017) method, and show that this is effective Bias Correction mechanism for distributed asynchronous optimization. We show that AsyncBC can effectively manage arbitrary data heterogencity, as well as handle gradient updates that arrive an uncoordinated manner and with delays. As a byproduct of our analysis, we also provide deeper understanding of the impacts of different stochasticity models on the convergence of the SARAH method.
1 INTRODUCTION
Modern machine learning relies heavily on gradient descent and its many variants (Kingma and Ba 2017 As the size of modern machine learning models grows dramatically, the data required to train such models also becomes huge, making it infeasible to collect all the data single machine. Therefore, it is often necessary to perform the training of modern machine learning models (e.g. large language models (Shocybi et al. 2019), generative models (Ramesh et al. 2021 2022), and others (Wang et al. (020)) in a distributed fashion (Bekkerman et al.] 2011), where data are distributed across different machines
and updates are coordinated by a parameter server. Another important setting is the federated learning setting (Konččý al. 2016 Kairouz al. 2019), where clients (c.g., edge devices or hospitals) jointly train model without sharing their local data.
Performing gradient methods for large models in this data-distributed setting faces many practical challenges, and there is a long line of rescarch attempting to resolve some practical obstacles in distributed training,
including communication compression (Seide et al. 201 4 Stich et. al. 2018 Koloskova el. al. 2020a Patkhullin
et al.
2023 Gao et al. 2024 2025), decentralization (Lian et al. 2017), local steps (Stich 2018 Mishchenko ct al. 2022c Jiang et al. 2024a] and their combinations (Condat
al. 2024 Huang al. 2024). An
implicit assumption made in all of these methods is that all workers' computations and commmnccatioss are synchronized, where all workers and the server wait for the slowest node before starting the next round

---

Published in Transactions on Machine Learning Research (10/2025)
of computations. In practice, there are several possible sources for delays, including network latency and hardware heterogeneity (Horvath et al.) 2021 Kairoux et al.] 2019), and slower "straggler" nodes might significantly hinder the performance of the distributed training process.
A natural approach to mitigate the negative impact of the straggler nodes is the asynchronous optimization paradigm. the asynchronous setting, the server and workers do not wait for the straggler nodes, and when the server receives gradient from any worker, immediately takes step to compute the next point and assigns it to some workers. There is long line of research studying asynchronous methods (Nodié et al.
2001
McDonald et al.) 2010 Agarwal and Duchi 2011 Arjevani et al. 2020 Stich et al. 2021 Nguyen et al. 2022 Among them, Nguyen et al. (2022) proposed the FedBuff method that demonstrated the practical relevance and superiority of asynchronous methods in the distributed setting that we focus on in this paper. Notably, several recent works attempt to improve the analysis of asynchronous methods in this setting: Koloskova et al. (202)) provided a sharper analysis using the empirical average delay of the workers, Mishchenko et al. (2022a) analyzed the convergence under arbitrary delay patterns, and Islamov et al. (0023) provided a unifiod analysis of several different asynchronous paradigms.
However, the convergence analysis in these works relies on the bounded gradient dissimilarity assumption, i.c., the distance between the gradient of the local function and the gradient of the global function is upper bounded by some value Ç. The convergence rates of these methods depend on the value of Ñ, and therefore their performances would degrade severely when Ç is large, and when there no finite value Ç that satisfies the gradient dissimilarity bound, the algorithu does not converge. In practice, the value of Ç typically unknown, making algorithms that depend on this value less robust. The case where gradient dissimilarity is close to 0 is referred to the data homogeneous setting, but it is often unrealistic in many modern distributed optimization scenarios, especially the cross-device Federated Learning setting (Kairouz et al., 2019: Karimireddy et al.; 2020a). To make asynchronous methods applicable to training beyond the data centers where the data is shuffled across all workers, it is crucial to design an asynchronous method that is not affected by data heterogencity.
1.1 Contribution
In this work, we investigate the distributed asynchronous gradient method under arbitrary data heterogeneity.
We propose and analyze AsyncBC, a distributed asynchronous variant of SARAH, and show that it an effective bias correction mechanism for distributed asynchronous optimization. While most existing works on distributed asynchronous optimization rely on gradient dissimilarity assumptions to obtain their convergence rate, our method provably converges without any such assumptions, and it is therefore more robust in the practical setting where data heterogeneity might be large.
We provide convergence analysis of our method in the stochastic setting under a mildly stronger structural assumption of the local functions, and we provide some insights into the necessity of the assumption. As byproduct, we also demonstrate that SARAH (Nguyen et al., 2017) might fail to converge in the presence of independent stochastic noise.
We also conduct numerical experiments to corroborate our theoretical findings.
1.2 Related Work
Asynchronous Parallel Optimization. There is vast amount of literature in the field of asynchronous optimizations, dating back to the late 1989 (Bertsekas and Tsitsiklis 2015). Earlier works asynchronous methods deal with coordinate-wise asynchronicity and the parallel setting, with the Hogwild! method being one of the most known works (Recht et al.) 2011]. There is a line of works exlending the methodology of Hogwild!, either improving the analysis (Nguyen et al. 2018) or proposing new variants of the method, including variancc-roducciion-tyy variants (Reddi et al., [2015] Zhao and Li, 2016 Mania et al., 2017 Leblond lt al. 2017 2018). These earlier works typically assume that the data is shared across all workers and rely the sparsity assumption on the local functions (i.e., each local function only affects a small number of
2

---

Published in Transactions on Machine Learning Research (10/2025)
Table 1: Theoretical comparison of our proposed method with asynchronous gradient methods without bias correction. We compare the rates in terms of the number of communications the server
Algorithm
BG
BGD (b)
Rate (c)
Gs Koloskova et al.
2022
No
Yes
Lemaxe Fa Feaax
I
+
Loca
vT
+
Limxx Fores 2/3
I
AsGrad
Yes
Yes
Leny Lore Fore
+ / Fos
+ Lumor ForeG 2/3
Islamov et al.] 2023
VT
AsyncBC-GD Ours
No
No
Imwax Fox To Twas +
Foy Dlmas
VT
BG stands for bounded gradient assumption: [x(x]] Ga for all [n].
BGD stands for bounded gradient dissimilarity sesumption: [ - V/z(i)1 s 5² for all 6,j [n].
(c) We present the best-known rates under the most relevant set assumptions as we use in the analysis. f is assumed to be
L-mooohh and each local function fi is assumed to be Lmax smooth. We omit the initializations that are independent of the target error.
coordinates). In the parallel settings, asynchronicity is typically quantified in terms of bounded overlaps of the update, which is not applicable in the distributed setting.
Asynchronous Distributed Optimization. In this work, we do not pursue the parallel direction, which might not fit the practical setting of modern machine learning, where each local function typically affects the entire model, and data distributed across different workers a potentially heterogencous manner (Nguyen et al. 2022). Instead, we consider the distributed optimization setting. In this setting, there is a parameter server that handles the updates, and the asynchronieity is therefore quantified in terms of the delay (or staleness) of the client's s state. In recent years, there has been surge of interest in the distributed setting due to its closer relevance to the modern machine lcarning practice, especially in the federated lcarning paradigm (Kairouz et al. 2019). Arjevani et al. (2020) and (Stch and Karimireddy (2020) provided the first tight convergence analysis for constant delays, while Koloskova et al.J (2022), Mishchenko et al. (2022a) and Islamov et al. (2023) improved various aspects of the analysis of the distributed asynchronous gradient methods. Nguyen et al. (2022) proposed the FedBuff method, which utilized a server buffer to balance the trade-off between the asynchronicity and update quality in practical settings. Such a technique is orthogonal to our method, and might be used in conjunction with our method. Recently, asynchronous reinforcement learning methods have also been sludied in (Lan et al.) 2024
In Table [ we compare our method to recent works on asynchronous gradient methods without bias correction. As is standard in the literature, we measure the complexity of the asynchronous methods in terms of the number of communications on the server side. This is asymptoticall, equivalent to the total number of finished local gradient oracle calls. We omit the computation of the initial inputs that are independent of the target error.
Bias Correction. The seminal work SCAFFOLD of Karimireddy et al. (2020b) introduced the concept of client bias (or client drift) and the idea of bias correction (or drift control) to the distributed and federated learning community. Following SCAFFOLD, there is a large body of works studying the bias correction mechanism for various distributed optimization settings, including distributed or decentralized optimization with communication compression (Mishchenko et al.] 2019 Stich 2020 Richtárik al., 2021 Gao al.
2024
Islamov et al.
2024), local updates with infrequent communication (Stichh 2018 Mishchenko al.
b022b
Jiang et al.)
2024a b), and the combination of these settings (Condat et al. 2023
Grudzień et al.
2023
Huang et al.
2024). Many existing works on bias correction apply global or local control variates
that draw inspiration from varianco-reduction--e
methods (Johnsso and Zhang 2013 Defazio et al. 2014
Nguyen et al. 2017). We are only aware of one concurrent work that studies bias correction in the distributed asynchronous setting (Wang et al., 2025). Their bias correction mechanism is based on the SAG/SAGA style variance reduction methods (Schhiidt et al.) 2017 Defazio et al., (2014) and is different from ours. We further point out that, while SCAFFOLD style bias correction mechanism the building block for many existing bias correction methods in other settings, it is not directly applicable to the asynchronous setting, since
3

---

Published in Transactions on Machine Learning Research (10/2025)
SCAFFOLD requires the server to collect full gradients in epoch-wise manner, which requires epoch-wise synchronizations of the workers.
2 PROBLEM FORMULATION
We consider the distributed optimization problem of the form
min f(x) = (x)
(1)
where the global objective function RR R is defined as the sum of local objective functions fi: IR R, [n]. represents the parameters of the model. Each worker (client) i E [n|] can only access the local function fJ and its gradient V... As is standard in the analysis of non-convex optimization algorithms, we assume that there exists some f such that f(x) 2 f for all x E R4. The problem (L) covers a wide range of optimization problems arising in the training process of Machine Learning models in distributed (Stich 2018
or federated (guuyen et al. 2022 fashion.
We make the following smoothness assumption on the global function f:
Assumption We say that is L-smooth, i.c. has L-Lipschitz gradient, such that for all x,y E Rd
[v) V S L|x
Note that the smoothness assumption is standard in the non-convex optimization literature. While recent works on asynchronous optimization (Koloskova et al.] 2022 Islamov et al., 2023 Mishchenko et al. 2022a make the stronger assumption that each local function Ja also L-smooth, we instead make the following weaker Hessian dissimilarity assumption on the local functions ft=
Assumption We assume that there erists some d 0 such that for each fi, we have:
Vf(y) (V Vf((y)))l S 8 yll-
Note that even though this is called a dissimilarity assumption, this should not be confused as a mere replacement of the usual additional gradient dissimilarity assumption used in prior works (Koloskova et al., 2022 Islamov al. 2023). Instead, this is more fine-grained characterization of the L--smoothness assumption for the local functions, and our results still hold when Assumption 2 is replaced by the usual smoothness assumption of the local functions. In particular, we have the following simple fact:
Fact 1. If each Jt is 14-smooth, then there must exist 0 < < (I++T.) such that f and Ji salisfies Assumplion with parameter 8.
The proof of Fact is straightforward, and we omit it here. Interested readers can refer to Definition 1 in (Jiang et al. 2024a or (Khaled and Jin 2022) and the discussions therein. The main advantage of using this weaker Hessian dissimilarity assumption instead of the usual L.-smoothness assumption for fi is that it allows us to more clearly characterize the effect of each smoothness parameter. Existing works studied the convergence in terms of Lmax = maxig(a] L; (by assuming that each L; Lmax). Note that L S 1 ExeeJ L, which is at most, but can potentially be much smaller than, Lmax In other words, we have the following chain of inequalities, where the gaps might. be large:
0 8 < L Lmax S 2Lmax
By considering the global smoothness and the local smoothness separately via Hossian dissimilarity, we obtain more fine-grained understanding of the convergence rate's dependency on the smoothness parameters. Finally, we discuss the assumptions related to asynchronicity and concurrency.
I Consider the simple case where (x) 2||2/2 and fi(x) E Jn 1].Jmax// n.
4

---

Published in Transactions on Machine Learning Research (10/2025)
Algorithm 1 AsyncBC-GD
Input: X1, m. fx(o) and concurrency To. Set X1 Xo 7mmy
2: sever selects u.a.r. a set of active clients of size re and sends them x1 and xo
3: each active client k computes gì (V fxx))))
4: for t = 1, do
server receives Bi- from client Jr
6: server updates m, = m B
server updates momentum > server updates parameters
7: server updates X(+1 = X 7/m,
8: server selects u.a.r. a new client k4+1 [n] and sends Xx+1 and
client k441 starts computing 8c+1 fkke (X4+1) Vik (xx) D computes next gradient difference
Assumption 3. We assume that the staleness of the local states at the clients is at most Tmax. In other words, when a client's 's output is received by the server at time i, the client's 's state is at a time t 1 Tr 2 1- Tmax
The assumption that the local gradients computed by each worker are delayed by at most Tmax rounds is standard in the distributed asynchronous optimization literature (Stich and Karimireddy 2020 Nguyen et al. 2022 Koloskova al. 2022 Islamov et al., 2023). There exist works that do not make any assumptions on the delay pattern (Mishchenko al. 2022a) However, Mishhhenko et al. (2022a) was only able to prove the convergence in the data- hata-homooenneuu regime. Under the data- heterogeneous setting without any assumption on the delay pattern, it is fundamentally impossible to obtain any meaningful convergence beyond the gradient dissimilarity: suppose that client 1 never responds, then one can only hope to minimize f f fi/n,, instead of the true global objective ʃ. We also point out that, under certain conditions on the objective function (e.g., variational coherence), one can prove convergence of certain asynchronous methods even when the delay grows polynomially (Zhou et al.) 2018).
Definition 1. Throughout the poper, we write Te as the concurrency, the number of active works at each ileration.
In practice, to best utilize available resources, the concurrency te would typically be set to n, the number of workers. We note that when the concurrency тe equals 1, the asynchronous method reduces to synchronized method. Such a connection might be useful for understanding the limitations of the asynchronous methods. See also our discussion on the basic asynchronous gradient method's dependence on gradient dissimilarity assumptions the next section.
3 BIAS CORRECTION FOR ASYNC OPTIMIZATION
As discussed earlier, the convergence rate of the basic asynchronous gradient method (Koloskova et al., 2022 Islamov al. 2023) depends on bounded gradient dissimilarity, more precisely, the assumption that [V)((x) Vx(x)ll S 2² for all E [n] and x E Rdd This We point out that this undesirable dependency on Ç not simply a technical deficiency in the analysis, instead, it is limitation of the method itself. Consider the simplest setting where the number of workers is n n>>> 1 while the concurrency is one. Then the basic asynchronous method reduces to SGD for finite sum optimization of batch size one. It is well-known that the convergence of SGD is dependent on (Lan 2020 Garrigos and Gower 2023 Therefore, a bias correction mechanism specialized for distributed asynchronous optimization is necessary to address the algorithm'' convergence in the hatta-htterogeneouu regime.
very restrictive assumption of the objective.
In this scction, we propose AsyncBC-GD that provides bias correction mechanism for asynchronous optimization. At an intuitive level, each local client only contributes the difference between their local gradients at the current point and the previous point, which cancels out the heterogeneity in the local data distribution, while we apply a server-side momentum to ensure sufficient progress. This mechanism is inspired by the SARAH variance reduction mechanism (guuen et al. 2017 More preciscly, AsyncBC-GD maintains a server-side momentum term m,- When the server receives the gradients from client jr. whose gradients might.
2The analysis might improved to only depend on the gradient dissimilarity the optimum in some cases Garrigos and Gower 2023
5

---

Published in Transactions on Machine Learning Research (10/2025)
be computed at stale points Xt-7 and x1- 1,, the server updates its momentum term and takes step in the direction of the new momentum. We highlight the key update steps of AsyncBC-GD below:
m - V.J.( (x.,(xx
(2)
X++1 - --m
The server then selects another worker k and sends the updated x,-1 and X to the worker. In this algorithm, the server selects the next worker uniformly at random out of all workers. Such sampling can typically be replaced by more greedy one where only inactive workers are sampled in the data- homogeneous regime. In the data heterogencous regime, the greedy sampling might incur bias error and lead to non- convergence (Mishchenko et al. 2022a Islamov et al.) 2023). but Wang et al. 2025 recently proposed different approach that claims to support greedy sampling.
Note that on the client side, at Line-3, we reweight the gradient difference of the initial points. Intuitively, this reweighting at the initial points is important to keep all the computed gradients in balance, since the initial points x1 and Xy are the only points at which the gradient. differences are computed by Te workers.
We summarize AsyncBC-GD in Algorithm D
Remark 1 (Communication cost and scalability). At each iteration of AsyncBC, the server receives one message from a client, performs an update and immmediately sends two parameter vectors to chosen client. Therefore the communication cost is not affected by the number of clients n, and scaling up with more clients will not incrense the communicaatin workload in each ileration. While as the model size d increases, the cost of communicating a full porameter or gradient vector will increase, there are compression techniques that can be applied to reduce the communication cost (Slich and Karimirreddy 2020: Gao et al.) 2024). We leave it for future work to investigate the possibility of applying these techniques to AsyncBC. In addition, as the reumber of clients n increases, the purely asynchronous setting where the server updates the model immediately after receiving a message from client might not be practical, as the server would have to go through at least n updates before seeing a message from all clients, which might be inefficient as n increases. To address this in practice, we might consider a semt-asynen cont-asynchronous setting where the server buffers some amount of messages from ckients before performing one update, simülar the FedBuff setting (Nguyen al., 2022). We also leave it for fulure work.
3.1 Convergence Analysis of AsyncBC-GD
In this section, we sketch the convergence analysis of Algorithm D All missing proofs can be found in the supplement. The main ingredient of our analysis is the virtual iteration technique introduced by Mania et al. (2017). The main difference is that we define the virtual iterates x, in terms of another virtual iterates m,, the virtual momentums. The analysis is based on carefully bounding the errors between both the virtual momentum and the true momentum, and the virtual iterate and the true iterate. Variants of virtual iteration techniques that involve multiple virtual iterates have been considered in the literature (Leblond et al., 2018), but our formulation in terms of virtual momentum scems to be novel and might be of independent interest.
But first, it would be handy to also define the set of active workers (and its corresponding timestamp) at each time precisely: we let C := 1kk,1) : k + ji is an initial active worker) be the set of active workers at time 1 (after the first worker h1 has communicated its output), and define C++1 == C. \ ((141, + T++1)} U ((k+11, + })} for / 2 1. Tn the asynchronous optimization literature (Koloskova et al. 2022), the active worker set is often simply defined via the worker only. We use the torker-timestamp notation to more conveniently handle the initialization phase of the algorithum as the initial states (timestamp 1) are assigned to te workers. For t 1, there is a one-to-one correspondence between the timestamp and the assigned worker h,, and we do not need the pair notation.
With the active worker set defined, we can now define our virtual iterate and virtual momentum. We set Xo = Xo. X1 = X1 and mo = my and the following update rules:
x = Xt rym,, 1
(3)
and
m mi + EONDEECUGGHDD gt
(4)
m := m + g.
At 2
6

---

Published in Transactions on Machine Learning Research (10/2025)
One of the key limiting factors in existing works (Koloskova et al. 2022 Islamov et al, 2023 is in the upper bound of the errors between the virtual and true iterates, where gradient dissimilarity assumption or a bounded gradient assumption has to be introduced to control the error. In our work, the error is controlled in terms of local gradient differences, instead of local gradients themselves, and we can therefore bypass the gradient dissimilarity assumption. particular, we have the following upper bound on the errors:
Lemma 1. Given Assumptions and the sequences {Kth {xx], {m+} and {me} satisfy the following:
m; mill s Tc + 122
Σ
Im=-1l1.
(K,,)EC,
(5)
| - x11² 211 1) + r max
m |m=-11
Note that indeed the upper bound is independent of the data heterogeneity. Now can state the convergence rate of Algorithm !
Theorem 1. Given Assumptions
and 2 for the sequence {xi} generated by Algorithm 1 if Tj
min 6(6+ L) Temmss L(6+L)) then we have:
(6 + L) FeTmax
VL(ō + Tmax Fo
E V [(xx)))
o
T
T
VT
where Fo = f(xo) - fr is the initial suboptimality gap.
Here see the advantage of using the H-Hessian dissimilarity assumption instead of a universal Liaxx smoothness assumption. The Lmax assumption for both the global f and the local fi made in existing works [Kloskova et al., 2022 Islamov et al. 2023) would lead to Lmax dependency in the second term, which might be worse than the /L68 + I.) dependency that we have now. In the worst case that L = Imax and + Fuxe
2Lmaxi our convergence rate becomes O
Now comparing the best rates known for Asyne-GD without bias correction (Koloskova et al., 2022 (see Table 1 we see that method in the worst case obtains the same higher-order term T.maa Fo Te Tmax/T For the 1/vT term, our method obtains Fo 'T which is independent of the data heterogeneity. On the other hand, the rate in Koloskova et al. (2022) is VLmaeFo33// which depends on the gradient dissimilarity ς Note that in the data homogencous case (52 0), the basic asynchronous gradient descent converges at I rate which is asymptotically faster than ours, while in the data heterogeneous case, our method converges faster when ç² 2 Toao. There also exist simple objectives for which the gradient dissimilarity assumption does not hold for any finite Ç, rendering the basic asynchronous gradient descent non-convergent [ While our method inspired by variance reduction /incremental gradient mechanisms, there exist incremental gradient methods (e.g. SAG (Schmidt et al. (017) and SAGA (Deaaioo al., 2014)) that achieve ((1/T) convergence rate the synchronized setting. Our method's ((/VT) rate scems to be inherent to the algorithm design (as it is also present in the analysis of the synchronized single-loop SARAH method (Nguyen al. 2017 in the synchronized setting).
We leave for future work to analyze our algorithm in the convex case. Directly transferring our proofs to the convex case seems non-trivial. In particular, it seems unlikely to obtain a tight result. by simply plugging our error analysis into a common descent lemma with respect to the primal distance to the optimizer. One can see that, the analysis of SARAH mechanism, the base method underlying our bias-correction mochanism, employs a specific analysis framework in the convex setting. Its convergence is analyzed with respect to the gradient norm, not the usual primal objective gap Nguyen et al. (2017)

---

Published in Transactions on Machine Learning Research (10/2025)
Algorithm 2 AsyncBC-SGD
Input: Xg, x1; mo = (Xn) and concurrency Te. Set X1 X 1/mp
sever selects u.a.r. a set of active clients of size te and sends them x, and X each active client k computes = (V)) (xx(xx {1)
4: for t = 1, do
5: server receives = from client Je
6: server updates m; = m + gg-
7: server updates Xx+1 = 1/m;;
server selects u.a.r. a new client kt41 [n] and sends x and X₁ fki (8+41,14+1) - V (X,, 5(+1)
1e+1
9: client k441 starts computing gt+1
In Section 4.1 we analyze the convergence of the algorithm under the assumption that the stochastic oracle at X and x; share the same raudomness f++1. This is natural when the randomness comes from sampling a mini-batch of the local data, In most cases, this should be default setup. In Section [.2 we demonstrate why such an assumption on the randomness is crucial, by constructing a lower bound where the algorithu does not converge when this assumption is violated.
4 STOCHASTIC ORACLE AND STOCHASTICITY ASSUMPTIONS
In the previous sections, we mostly considered the deterministic setting, where each client computed the local gradients exactly. The cross device Federated Learning setting (Kairouz et al., 2019 Karimiroddy et al. 2020a) encompasses distributed optimization scenario where there might be an extremely large number of clients while each client is resource-poor. In such setting, the local objectives might be highly heterogeneous, and the local gradients might be computed exactly. However, another important setting of Federated Learning is the cross-silo setting, where there a smaller number of clients that might be resource-rich. In such a case, local gradients are often only approximated stochastically. In this section, we briefly discuss the stochastic variant Algorithm 2 and the stochasticity assumptions that are suitable for our method. As is common in the literabure, we will always assume that the stochastic gradients are unbiased:
Assumption 4. For each client E [n], the stochastic gradient V fi( is unbiased, i.e. [ V (x)..
4.1 Convergence of AsyncBC-SGD with Sean-Spuared-Smootnness Smoothness
In this section, first show that if make slightly stronger structural assumption on the smoothness of the local functions, Algorithm 2
converges. In particular, we introduce the following assumption:
Assumption 5. We say that fa(.) = Bgg [c) is E-mean--quarrd--maon if:
E
[V)(xE)) - VAGr,))) < 11x-=-11
Further, we also assume that Algoritim 2 access the stochastic oracle for all pairs (x++1, x:) with the same manomness Ert1.
This assumption is sometimes referred to as mean-ssquardd-smootttess in the literature Xu and Xu and it can also be seen as a stochastic strengthening of the smoothness assumption for each local function. In particular, if for each g. fxx, {) is Lmax-smooth, then & < Lmaxx. It is a popular stochasticity assumption in the literature of SGD, especially for variance reduction methods (Fang et al., 2018: Cutkosky and Orabona 2019 Tran-Dinh et al. 2022 Wang al.) 2019 Xu and Xu (002).. The mean-squarede mean--sqaared-smoothme relaxes the individual smoothness assumption with respect each randomness E. When each local function f is logistic regression loss and each randomness & represents mini-batel of the local data, then f((: {) is indivually smooth and fi is therefore mean-squared-smooth.
2022
assumption
In Assumption 5 we also assume that we can sample the local gradient at different points with the same randomness. This natural when, say, the randomness comes from sampling a batch of the local
We omit the initial computation of mg Vf(x)), which incurs additional term that does not depend on the target error.
4 Consider fx(x) = x21
8

---

Published in Transactions on Machine Learning Research (10/2025)
With this assumption, it is easy to have the following convergence statement, independent of any heterogeneity assumption:
data.
Theorem 2. Given Assumplions
and for the sequence {xx) generaled by Algorithm then we have:
iJ =
min
7max 10EVT' 2 2LLermaa
T E |V So (AVteTmarlo (
(E + v VLlTmux)
T +
VT
4.2 Unconvergence of AsyncBC-SGD with Independent Noise
4.1 showed the convergence of AsyncBC-SGD under Assumption 5 This assumption implies that the noise of the stochastic local gradient is structurally dependent on the local objective. This is natural in many settings, including the popular empirical risk minimization paradigm in most machine learning training procosses. In this section, we further illustrate why such a dependence between the noise and the local objective seems necessary for the convergence of AsyncBC-SGD.
In Section
In the following, we show that without Assumption 5 if the outputs of each client i are injected with a when the concurrency is 1. As we have noted in Section 2. when TC 1, the algorithm reduces to syuchronized method. We remark that in this case our Algorithm 2 recovers stochastic version of SARAH variance reduction method (Nguyen et al. 2017) where for each fi the gradient difference oracle g¹ = (x)(x.E) V)((y,))) = Vf(x) - Vf((y) + 5" with E [5"] = 0 and IE ||5"|]]] = Note that, unlike Assumption 5 here we do not assume that the oracle accesses at and y need to share the same randomness, but rather, we only quantify the expectation and the variance of g'. Our next theorem shows that when o² 0 Algorithm 2 (and hence SARAH) does not converge to the stationary point.
large independence noise, then the algorithm does not converge
Theorem 3 (Lower bound with independent noise). Consider the single concurency setting, where fi(x) = |x+b.ll/2 for any b, and Xo is not a stationary point of f. If each gi output of client i is given by where & NV oI) is an independent Gaussian noise, then the sequence {xi) generaled by Algorithm 2 does not converge to the stationary point of J for any 1 1.
gi = (x(x-)))
In words, we show that when the gradient difference oracle of Algorithm 22 is injected with independent noise with nonzero variance o² > 0, then depending on the stepsize, the algorithm either diverges to infinity or does not make enough progress to the stationary point. We verify Theorem 3 with mumerical results in Appendix C In the following we also briefly explain why Theorem 3 doess not refute Theorem
2
Remark 2. We point out that the oracle gi violates Assumption 5 in the following sense: is V (i(e, +.)+
(x) where V (x (e) and V f((xx-1,6) (i) both satisfy Assumption then the variance of the oracle becomes:
Bq. [IVA(())))) Vf((x- (Vf((x;) Vf((x-))) S (I² + 10_1 x11
Therefore, oracles that follow Assumption 5 will have variance dependent on the distance ||x-- whereas in Theorem 3 the variance is a constant o².
- x1-11
5 EXPERIMENTS
In this section, we conduct numerical experiments to validate the theoretical results of our algorithms. All experiments were run on an Inte Xeon(R) CPU E7-8890 v4 @ 2.20GHz chip. All our code can be accessed at here and here All additional details of the experiments can be found in Appendix D
Synthetic Least Squares Problem We first consider a simple synthetic least squares problem and verify our algorithm's 's independence of data heterogeneity. We study the following problem as in (Koloskova et al.) 2020bl: Fach worker i has access to fx(x) = 1 ||A, ball where A == ? Ia and each b; is sampled from

---

Published in Transactions on Machine Learning Research (10/2025)
r= 10
10,
20. 10
127
30'
30"
104
304
309
1:
10"1
10
10"2
16
10
102
10'
10'
10?
10a
Iteration
Iteration
Iteration
Figure Convergence of AsyncBC-GD and Async- GD under different data heterogeneity. We see that the performance of Async-GD deteriorates the data heterogeneity increases, while AsyncBC-GD is unaffected.
0-1.==3 30
0.01 T=
C 01.001 T= 50
3.50
0.80
0.80
Accuracy
Accuracy
Accuracy
0.55
0.05
AtyrcBC-SCD 9G0
0.65
Syne-SGn
Symce500
3.30
2000
AD0D lteration
6000
0300
10000
0.60
2000
4000
6200
0000
18000
0.40
7000
A005
6000
5000
16200
Iteration
Iteration
Figure 2: Performance AsyncBC-SGD, Async-SGD and Sync-SGD for the Fashion MNIST datasct under different data heterogeneily. Decreasing a means increasing data heterogeneily. We see that AsyncBC-SGD's performance is smooth and robust against increasing a. It outperforms both Async-SGD and Sync-SGD.
N(0,, La) for some parameter Ç. is easy to see that the Ç parameter controls the gradient dissimilarity (at the optimun In particular, when Ç = 0, (x*))) Vi. The detailed setting of the synthetic experiment can be found in Appendix D.I.
In Figure investigate the effect of Ç on the convergence of AsyncBC-GD and Async-GD, To simulate the different computation speeds of the workers, we set each worker i's computation time for each task to ixt/n, where v controls the asynchronicity. We set 7 10. We perform a grid search for the best r) parameter for both algorithms. We observe that AsyncBC-GD's performance consistent for different Ç values, as predicted by our theory, while Async-GD takes longer converge when Ç increases. Note that in the data homogeneous case (C = 0), Async-GD converges faster than AsyncBC-GD, which is consistent with the theory.
Regularized Logistic Regression For Fashion MNIST Classification Now consider a regularized logistic regression problem for the opensourced Fashion MNIST dataset (Xiao et al. 2017 We use nonconvex regularizer following (Zhao et al. 2022 The objective function over a pair of data (a. b) is given as the following:
x²
f(x: (xx b)) = log(1 + exp(- ba x)) +
1 1+x
where the last term a nonconvex regularizer and p 0.05 the regularization parameter. We distributo the training dataset to clients using the Dirichlet distribution with parameter a control the data het- erogeneity (Hsu et al., 2019h. In particular, the datasets held by the clients get more heterogeneous approaches zero. Additional details can be found in Appendix D.2.
In Figure 2 we summarize the performance of AsyncBC-SGD, Async-SGD and Sync-SGD for the Fashion MNIST dataset. The compare the performance in terms of the number iterations. We observe that, as data heterogeneity increases, the performance of Async-SGD deteriorates and becomes highly unstable, while AsyncBC-SGD is robust against data. heterogeneity and outperforms Async-SGD. Morcover, AsyncBC-SGD
Thiis somewhat more relaxed notion gradient dissimilarity than the considered in Koloskova al.
2022
Islamov
2023
10

---

Published in Transactions on Machine Learning Research (10/2025)
attains much smoother curve consistently. The stability of the accuracy curve for AsyncBC-SGD verifies the robustness of our method against stochastic noise in a practical setting. We also observer that Sync-SGD is, as expected, unaffected by data heterogeneity. But it is outperformed by AsyncBC-SGD, which might be due to the fact taht AsyncBC-SGD is inherently a varianco-roduced method.
6 CONCLUSION AND OUTLOOKS
In this work, we investigate the distributed asynchronous gradient methods and address their convergence analysis in the arbitrarily tata-heterogeneous setting. We propose and analyze AsyncBC-GD, distributed asynchronous variant of SARAH. We prove that it is an effective Bias Correction mechanism in that it converges without the restrictive bounded gradient
bounded gradient dissimilarity condition, and is therefore superior in the high data hederogeneous regime than the basic asynchronous methods without bais correction (Nguyen et al. 2022 Koloskova et al. 2022 Mishchenko et al., 2022a Islamov et al. 2023). We also study the suitable stochasticity assumptions for our mothod and prove the method's convergence under the mean-squaredd of the popular SARAH variance reduction method the presence of independent gradient noise. Future works can investigate the possibility of obtaining ((/rr) rate for distributed asynchronous optimization with either bias correction mechanism other methods. Another important theoretical challenge is to further understand the delay dependence of the convergence of bias-corrected asynchronous methods. In particular, future work can investigate the possibility of improving the dependence on Tuax to Tavg: refute such possibility with lower bound construction.
assumption. As a byproduct our analysis, we also prove the non non-convergence
Acknowledgments
YT supported by JSPS KAKENHI Grant Number 23K.J1336.
References
Alekh Agarwal and John C Duchi. Distributed delayed stochastic optimization. In Advances in Newral Information Processing Systems, 2011.
Yossi Arjevani, Ohad Shamir, and Nathan Srebro. A light convergence analysis for stochastic gradient descent. with delayed updates. In Algorithmác Learning Theory, 2020.
Ron Bekkerman, Mikhail Bilenko, and John Langford. Scaling up machine learning: Parallel and distributed approaches. Tn Association for Computing Machinery, 2011.
Dimitri Bertsekas and John Tsitsiklis. Parallel and distributed computation: numerical methods. In Athena Scientífie, 2015.
Laurent Condat, Ivan Agarsky, Grigory Malinovsky, and Peter Richtárik. Tamuna Doubly accelerated federated learning with local training, compression, and partial participation. In arXiv, 2023.
Laurent Condat, Ivan Agarský, and Peter Richtárik. Provably doubly accelerated federated learning: The first theoretically successful combination of local training and communication compression. In Openreview, 2024.
Ashok Cutkosky and Francesco Orabona. Momentum based variance reduction in non-convex sgd. In Aduances Newral Information Processing Systems, 2019.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Information Processing Systems, 2014.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic aath-integrated differential estimator. In Advances Neural Information Processing Systems, 2018.
11

---

Published in Transactions on Machine Learning Research (10/2025)
Iyas Fatkhullin, Alexander Tyurin, and Peter Richtárik. Momentum provably improves error feedback! In aru, 2023.
Yuan Gao, Rustem Islamov, and Sebastian Stich. EControl: and error control. In International Conference Learning Representations, 2024.
Fast distributed optimization with compression
Yuan Gao, Anton Rodomanov; Jeremy Rack, and Sebastian U Stich. Accelerated distributed optimization with compression and error feedback. In arXin, 2025.
Guillaume Garrigos and Robert M Gower. Handbook of convergence theorems for (stochastic) gradient methods. In arXiu, 2023.
Michal Grudzien, Grigory Malinovsky, and Peter Richtárik. Can 5th generation local training methods support client sampling? yes! In International Conference on Artificial Intelligence and Statistics, 2023.
Samuel Horvath, Stefanos Laskaridis, Mario Almeida, Îlis Loontiadis, Stylianos Venieris, and Nicholas Lane. Fjord: Fair and accurate federated learning under heterogeneous targets with ordered dropout. In Advances in Newral Information Processing Systems, 2021.
Tzu-Ming Harry Hsu, Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classífication. In Xiv, 2019.
Xinmeng Huang, Ping Li, and Xiaoyun Li. Stochastic controlled averaging for federated learning with communication compression. In International Conference on Learning Representations, 2024.
Rustem Islamov, Mher Safaryan, and Dan Alistarh. Asgrad: A sharp unified analysis of asynchronous-sgd algorithms. In Xiv, 2023.
Rustem Islamov, Yuan Gao, and Sebastian U Stich. Towards faster decentralized stochastic optimization with communication compression. In arviv, 2024.
Xiaowen Jiang, Anton Rodomanov, and Sebastian U Stich. Federated optimization with doubly regularized drift correction. In International Conference Machine Learning, 2024a.
Xiaowen Jiang, Anton Rodomanov, and Sebastian U Stich. Stabilized proximal-poin methods for foderatod optimization. Advances in Neural Information Processing Systems, 37, 2024b.
Ric Johnson and Tong Zhang. Accolerating stochastic gradient descont using predictive variance reduction. Advances in Neural Information Processing Systems, 2013.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mchdi Bennis, Arjun Nitin Bhagoji, Kallista A. Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramer, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in foderated learning. In Xrv, 2019.
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. In arXiu, 2020a.
Sai Pranceth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scalfold: Stochastic controlled averaging for federated learning. In Inter- national Conference on Machine Learning, 2020b.
Ahmed Khaled and Chi Jin. Faster federated optimization under second-order similarity. In or Xiv, 2022.
12

---

Published in Transactions on Machine Learning Research (10/2025)
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In arXiv, 2017.
Anastasia Koloskova, Tao Lin, Sebastian Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. In International Conference on Learning Representations, 2020a.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, 2020b.
Anastasia Koloskova, Scbastian U. Stich, and Martin Jaggi. Sharper convergence guarantees for asynchronous sgd for distributed and federated learning. In arxi 2022.
Jakub Konečný, H. Brendan McMahan, Felix Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: strategies for improving communication efficiency. In NIPS Private Multi-Party Machine Learning Workshop, 2016.
Guangehen Lan, Dong-Jun Han, Abolfazl Hashomi, Vaneet Aggarwal, and Christopher G Brinton. Asyn- chronous federated reinforcement learning with policy gradient updates: Algorithm design and convergence analysis. In Xix, 2024.
Guanghui Lan. First-order and stochastic optimization methods for machine learning. In Springer, 2020.
Rémi Leblond, Fabian Pedregosa, and Simon Lacoste-Julien. Improved asynchronous parallel optimization analysis for stochastic incremental methods. In Journal of Machine Learning Research, 2018.
Rémi Leblond, Fabian Pedregosa, and Simon Lacoste-Julien. ASAGA: Asynchronous Parallel SAGA. In International Conference on Artificial Intelligence and Statistics, 2017.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Advances Newral Information Processing Systems, 2017.
Horia Mania, Xinghao Pan, Dimitris Papailioponlos, Benjamin Recht, Kannan Ramchandran, and Michael Jordan. Perturbed iterate analysis for asynchronous stochastic optimization. In SIAM Journal Optimization, 2017.
Ryan McDonald, Keith Hall, and Gideon Mann. Distributed training strategies for the structured perceptron. In North American Chapter of the Association for Computational Linguisties, 2010.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. In arXiv, 2019.
Konstantin Mishchenko, Francis Bach, Mathicu Even, and Blake E Woodworth. Asynchronous sgd beats minibatch sgd under arbitrary delays. In Advonces Neural Information Processing Systems, 2022a.
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally! In International Conference Machine Learning, 2022b.
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtarik. ProxSkip: Yes! Local
gradient steps provably lead communcation acceleration! Finally! In International Conference on Machine Learning, 2022c.
Angelia Nedić, Dimitri P Bertsekas, and Vivek S Borkar. Distributed asynchronous incremental subgradient methods. In Studies in Computational Mathematics, 2001.
John Nguyen, Kshitiz Malik, Hongyuan Zhan, Ashkan Yousefpour, Mike Rabbat, Mani Malek, and Dzmitry Huba. Federated learning with buffered asynchronous aggregation. In International Conference on Artificial Intelligence and Statislics, 2022.
13

---

Published in Transactions on Machine Learning Research (10/2025)
Lam Nguyen, Phuong Ha Nguyen, Marten Dijk, Peter Richtárik, Katya Scheinberg, and Martin Takác. Sgd and hogwild! convergence without the bounded gradients assumption. In International Conference on Machine Learning, 2018.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: novel method for machine learning problems using stochastic recursive gradient. In International Conference Machine Learning, 2017.
Aditya Ramesh, Mikhail Pavlov, Gabricl Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot lext-lo-image generation. International Conference on Machine Learning, 2021.
Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text-conditional image generation with clip latents. In Xin, 2022.
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild!: A lock-free approach parallelizing stochastic gradient descent. In Advances in Neural Information Processing Systems, 2011.
Sashank J Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alexander J Smola. On variance reduction in stochastic gradient descent and its asynchronous variants. In Advances in Neural Information Processing Systems, 2015.
Peter Richtárik, Igor Sokolov, and llyas Fatkhullin. E121: A new, simpler, theoretically better, and practically faster error feedback. In Advances in Neural Information Processing Systems, 2021.
Mark Schmidt,, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162:83 112, 2017.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns. In International Speech Communication Association, 2014.
Mohammad Shoeybi, Mostofa Patwary Raul Puri, Patrick Le Gresley, Jared Casper, and Bryan Catanzaro. Megatron-Im: Training multi-billion parameter language models using model parallelism. In arXiv, 2019.
Sebastian Stich, Amirkeivan Mohtashami,, and Martin Jaggi. Critical parameters for scalable distributed learning with large batches and asynchronous updates. In International Conference on Artificial Intelligence and Statistics, 2021.
Sebastian U Stich. Local sgd converges fast and communicates little. In International Conference on Learning Representations, 2018.
Sebastian U. Stich. On communication compression for distributed optimization on heterogeneous data. In Xrx, 2020.
Sebastian Stich and Sai Pranceth Karimireddy. The error-foedback framework: Better rates for sgd with
delayed gradients and compressed updates. In Journal of Machine Learning Reseorch, 2020.
Sebastian U Stich, Jean- -aatisat Cordonnier, and Martin Jaggi. Sparsified sgd with memory. Advances in neural information processing systems, 31, 2018.
Quoc Tran-Dinh, Nhan H Pham, Dzung T Phan, and Lam M Nguyen. A hybrid stochastic optimization framework for composite nonconvex optimization. In Mathematical Programming, 2022.
Meng Wang, Weijie Fu, Xiangnan He, Shijie Hao, and Xindong Wu. A survey on large-scale machine learning. In IEEE Transactions on Knowledge and Data Engineering, 2020.
Xiaolu Wang, Yuchang Sun, Hoi To Wai, and Jun Zhang. Incremental aggregated asynchronous SGD for arbitrarily heterogeneous data, 2025. URL http::///oggoooorrrrree///o//sss
Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost and momentum: Faster variance reduction algorithms. Tn Advances in Neural Information. Processing Systems, 2019.
14

---

Published in Transactions on Machine Learning Research (10/2025)
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mmist: novel image dataset for benchmarking machine learning algorithms. In Xin, 2017.
Yangyang Xu and Yibo Xu. Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization. In arXiv, 2022.
Haoyu Zhao, Boyue Li, Zhize Li, Peter Richtárik, and Yuejic Chi. Beer: Fast o(//t) rate for decentralized nonconvex optimization with communication compression. Advances Neural Information Processing Systems, 2022.
Shen-Yi Zhao and Wu-Jun Li. Fast asynchronous parallel stochastic gradient descent: A lock-free approach with convergence guarantee. In Association for the Advancement of Artificial Intelligence, 2016.
Zhengyuan Zhou, Panayolis Mertikopoulos, Nicholas Bambos, Peter Glynn, Yinyu Ye, Li-Jia Li, and Li Fei-Fei. Distributed asynchronous optimization with unbounded delays: How slow can you go? In International Conference on Machine Learning, 2018.
A ANALYSIS OF AsyncBC-GD
Recall that we consider the following virtual iterates:
Xt+1 X; ryme,
and
m = mg + E(.)) gf may1 m.
g:
121
For convergence analysis, we also consider the following virtual optimality gap:
= E((()) - f*]
(6)
We first give complete analysis of the error of the virtual iterate and virtual momentum:
Lemma Let (xe), (m²), (3t) and (m:} be defined by Algorithm Equation have:
3 and Equation
Then
m m Σ
9
Vt
(k,1)EC,
(7)
X1 Xe
Σ
k
gi
Vt > 2
(1.1)EC1
where Th is defined to be the number of times that g is delayed until time and T k,b-1 the number of times g is delayed until lime 1-
Proof. We first prove the first equation in Equation via induction. By Algorithm and Equation (4) one
can casily verify that it holds for m mi. For t 2, we have:
m,
m m m + g/ B1-7. g.
Σ
g + / kt- Σ oi.
(
(K.D)C.
where the last equality follows from the definition of C,-
15

---

Published in Transactions on Machine Learning Research (10/2025)
It remains to prove the error of the virtual iterate. For the second equation in Equation have for 2 2:
X, X -1
m m.
11
(k,
Σ
7 - 81
(b,1)EC1
where in the last term treat the gî and k. i > 2 separately since the time stamp 1 is the only timestamp that corresponds to multiple workers.
Now we upper bound the error between the virtual iterates and the true iterates, using Lemma 2
Lemma 1. Given Assumptions and 2 the sequences {x,). (xe), {me} and {m,) satisfy the following:
m: mil s Tc + L23 Σ Im,-11?
(A,
t-1
(5)
[xx x.1l
s 21 1) + LT Σ
Proof. Consider any worker-time pair (k that was active, we first give a simple upper bound on |g If
1 2 1, we have:
|| = fx,,) - (V((s)
(8)
$ f2 Vf((x(1)) -V -V/=))//// +2 vf(x-=))1
(6)
< 2(8 + L23 -
where in (1) used the Young's inequality and in (ii) we Assumption 1 and Assumption something similar for t = with an improvement of : for any (k, 1) C1 have:
2
We can prove
2 (02 L3) ||x| xol1 2 s
ig
We first upper bound the error ||m
mill
rt 1:
m,
2
Σ g
(A.))
S TC
Σ
Ig
(MN))E,,
< 2 + +12)
Σ
||x; - -xx-x-111 x1-111
(N,))
Tc + L2)
Σ |mm-111
(K,1)C,,
16

---

Published in Transactions on Machine Learning Research (10/2025)
Similarly, we can upper bound ||x; - xel? 24 2 2:
xx xx11² = x=11==1f 172
Σ
k
1
81
(k,1)EC1
snn(t 1) Σ
)
k
+ 1 (TCT-11 Σ ( ||g
gi
(R.1)EC;
[-1
221
Σ
(2 112)11x; -x1-11?
1=2
(T1 1.
+ 2172(t - TT 1)²
(62 + L2) ||x| - -xoll
(R,1)
1
2t7 - 1)(0²= - L²²)
( 1mm + 277 1) +12)
Σ
mo |?
TC
2m2
(k.1)EC
S 2n - 1)(02= - 1²2)=2 max
ml
We can also give a simple corollary of Lemma that lower bounds |mml| in terms of ||m,]] 1|
Corollary 1. Given Assumplion and Assumplion 2 we have:
|mm|] 11? Te + L2)
Σ
m |l|
m
iEC,
This is a simple application of Lemma 1 and Young's inequality and we omit the proof here.
Next we get a descent lemma on the descent of Fe
Lemma 3. Given Assumption the sequences (Kt), {xi), (m+} and {m,} satisfy the following:
Fis1 & F. - " [[V - 1 2
Tnp²
E
[2]
EE [V - mirl + +nL2B [15t - xx|]]]
(8)
2
Proof. By Assumption
we have:
Lnp | ||
f(x++1) S f(x)) (V (xx,)
m.) +
Laj²
-xx,) 7 V
(Vf(xx Vxx,)) m.) +
2 |m, ||
-(x,) 1 [x)(x
|m
[xxx)) m.l
2
Ln7 | 2
+ (V/1 V)()),
(8)
f(x)) 2/5 [+((2|1
|m 12 2
| f(xx)) - m, 2
2
2
+n/l/ {)(
!
| Laj² |mm 2
-(x))) - 1/4 [x - -24 Laj²
||
+ 17
フ/ V fxx)) - mi + [ - (x()))1
(80)
< ((x)) 2/5 [V((x))]] - 2
Ln?
|m
||
+ 1
[V(x)) mi|l² + nL | x=112
2
17

---

Published in Transactions on Machine Learning Research (10/2025)
where in (1) used Assumption 1 in (ti) used Young's inequality, and in (it) we used Assumption again. Subtracking I* and taking expectation on both sides, we get the desired results.
Next we bound the gradient error term E [V - m.ll" recursively
Lemma 4. Given Assumption for all 2 1, the sequences (xe), {mi} and {me} satisfy the following:
[Vf(x,) m. s E [V m 1|] 8 ||m,-11] [1²)
Proof. We first consider the case 1. Observe that, since hs is sampled uniformly at random, have:
E [x,) V/(xx1)) (V (x.) Vin, (x:-)))
Therefore:
E V [
mmll
V fxx:) m (V, fx.
E
V [x
m + (V)(x) V - [V (x,) (x
E
V (V
m |2]
+ [V(()x) - V ( (x,) - (x,-1)))
+
E [(V m
fx(x)) - Vff(x - (V (0,,,xx000 (xx) - V/h (xx-())
E
V [X (x+
m
|2]
+ E
|| - V 444 (x,) VJa, (x,,(x))))
(
[ 1) m
+ 8 ||x: x 11
E [V
m [2]
28
|m [2]
where in (i) we used Assumption The case can be handled similarly with a slightly improved bound, but the looser bound is sufficient for our purpose. However, note that key point in the proof is the unbiasedness of m- mñ, which is guaranteed by the reweighting of the initial gradient differences in Algorithm 1
Corollary 2. Given Assumption for all t 2 1, the sequences (xt), {m.} and {m.} satisfy the following:
E
[V((x) -m.l?? S Σ 8 |m: [|]]
Proof. We sum over 1 to & on both sides of Equation 9 and get:
E [xx) -m.l'mm""" mi.l?] < E
[V mom +
Σ 2
|m 112
2 _ ||m,-111
where for (i) used the fact that mo mo (x(x)).
Now are ready to derive the convergence rate of Algorithm and prove Theorem
Theorem 1. Given Assumptions and 2 for the sequence (x+} generated by Algorithm 1 Rif =
min
then we have:
600 L0++) L(
1
E [V((x)))
o
(5 L) Te Fo
V [[ō + L) Timxx Fo
T
T
VT
where Fo f(xo) f is the initial suboptimalily gap.
18

---

Published in Transactions on Machine Learning Research (10/2025)
Proof. We plug Lemma
1
Corollary
1 and Corollary
2 into Equation
8 and get for all t 0:
E m |
V - -(2 - Ln²²
F11 s F.
2
E
2n/ TO + L2)
E
m; 11
2
2
iEC.
+
87882
17
2
|m 12] + 2n 182 + y
t-1
| 11
m
2
Assume that 77 S 4 we get:
E
mm ||
Fi+1 S F. E
V
21/² + +12
Σ E
m
2
iEC,
17202
+
E |
12]
2
(8
m 1
Now we sum over to on both sides and get:
T- 1
T-1
1
To + -2
T
[
5o
Σ
E
me
+
m
16 1=
A=
(= VEC.
+ 87882
T 1
m
t=1 i=1
B
T-1
+ 2n 27 13 + +
1) T
Taxx
We first bound the third term A on the right-hand side. Note that each of the E most Tmax rounds, and hence appears at most Tmax times in A, therefore:
||m 11]]
delayed by
Te (8 + 2
A <
EE
m ||]
We simply bound B by:
88T T-2
B
Σ E
m,
1|2
1=0
Similarly, we bound C' by:
T-2
C 27 (2 + - (T-1) 1)2
Σ
E
|
1=0
Therefore, if
< min
6(6 + TT
108 8T668 L)
19

---

Published in Transactions on Machine Learning Research (10/2025)
Then we must have that A ++B+CS
ET- E
|| |1
Hence,
16
T
2Fo
2Fo T/L
[V
-
T
r/
Note that by Fact 1 it sufficos to set
min
6(6 + TTTxx 12 + L L) T
For such a choice v,, we get:
12(6 + L) TCTmax Fo 24 L(d + L) Timx
E
|V
<
T t=
T
VT
B ANALYSIS OF AsyncBC-SGD
The convergence analysis of Algorithm under Assumption very similar to its deterministic counterpart. We point out that most of the differences are due the application of Assumption 5 Note that Lemma 2 remains the samc.
Lemma 5. Given Assumptions and the sequences {xt}; {xt], {m.} and {me} satisfy the following:
E m, m=
I re E(K.)EC.
E
[|m [?]
(10)
E
||x
x111
1t T) max E
||m
Proof. The proof of Lemma is very similar to that of Lemma instead of Assumption bound ||
except that we need to use Assumption 5
E
||
||
|| (xe: (xx &))
|x
x1- 11 || 11
Again, we first uppper bound the E
[lm
mi|l3]
14 2
E
[m
mill
=E
Σ g
(k.)))C
I Σ
||g.
(k,)))C,
I Tcl2
Σ
E
||x: - x
(M,i)E,,
TC
|m
(H,))C,
20

---

Published in Transactions on Machine Learning Research (10/2025)
Now for E |x: - & 12 44 2 2:
E ||x, - x112 = Bi
Σ (R,1)EC1
kit
1
g1
Stp(t 1) Σ
(T
)
2
gi
2
+
+ - 1) 1) Σ
(or
||Isf|
1=2
(K.1)EC,
t-1
1tp(t 1)
Σ
||x: 112
i=2
+ +t 1) - 1)²
E ||x;| - xx013)
(1:1)
1t 1) Σ
1-1
(T+
(T--))
|mm--111 112]
+ tn 1) Σ
(T
R.t
12
m
1=2
(),1)
1-1
S 1 1)
m
max
We also have the following simple corollary of Lemma 5 that lower bounds [m.]]²] in terms of E
[m [m/l]]] [
Corollary Given Assumption we have for all 2
E
[mm
112
E
m
|?]
2
1)²
E m 11
11
2
iEC,
Proof. Again, this is a simple application of Lemma 5 and Young's incquality and we omit the proof here.
Note that Lomma 3 still holds, and it remains to give a stochastic version of Lemma
Lemma 6. Given Assumptions and 5 for all t 2 1, the sequences {xr}, {mi} and {mi} satisfy the following:
[V](x)) - m. 12| < [Vx((x-)) m. mm-1 + 1 EE [|mm- 112]
(11)
21

---

Published in Transactions on Machine Learning Research (10/2025)
Proof.
E
[ -m.11]
E IIV - (V/k, (x Et) (x,, vike (x(-))))
E [V m (V)(()) V (V.ia,
E | [|V](xx)) 1) - i [1]] + E V)((x)) - V v
+E |IV (xe: [1) V (x,-1, =1]
+ 21E ((V ((x 1) 1 Vf((x) [[((x,1))]]
2E (V(((x-1) -m,-1, fkk (xe, Ex) V fki (x,-1, Et)}
2E (VV](x)) - Vf(xx-1), Vik, (t) - Víh, (x 6t)
E [[V [IV[(xx))) mm-111 E [ vx(x+-1)1'
+E [ (xe, Ec) v/k (x,-1, Ei]
(18)
[V 1) - m.
+ e ||x, - x 112
E [V]((--1) - M m.111 1|
+ +
||m,-1|1
where in (1) used E [V fi, (x) - fx, vf(x,) -- f((xx-1), and in (ii) we used Assumption 5
Therefore, we also have the following corollary:
Corollary 4. Given Assumptions and 5 for all t 2 1, the sequences {xx], (m.) and {m.) satisfy the following:
[IV m S Σ E ||m 11
Now we can prove the convergence of Algorithm under Assumption
Theorem 2. Given Assumptions and for the sequence {xi} generated by Algorithm if
min Tamxs 10 2 2LL then we have:
(T
E [V so (NVTeTmur (
T + (& + VLlTmax)
VT
Proof. Now we plug Lemma and corollaries and to Equation
g
Tnp
E
m
Frn
<
Fr
|
fxx))
-
17
1el2
E
I 11]
2
2
2
Ec
2222
+
E
11m,-112
+ t
22,
m
2
max
i=1
22

---

Published in Transactions on Machine Learning Research (10/2025)
Assume that 17 4, we get:
m
Fra1 S F.
"E [xx)]
1i Tc 62
E
m;
11
88
2
iEC,
R +
||m--11
||
[1]]
+ tn - 12
m
m
2
max
1=1
Now we over 0 to T 1 on both sides and get:
Σ E
[V
F
"
2
E
|
12]
+
E m
2
16
8
t=1 iEC,
82
T
E
[
+
L2
(1 1) T)
max
2
i=
We first bound the third term A on the fight-hand side. Note that each of the IE' ||m [12] is delayed by at most max rounds, and hence appears at most Tmax times in A, therefore:
1 mmaxx 12
T-
A <
m
8
1=
We simply bound B by:
12T T-2
S
E
m
Similarly, we bound C by:
T-2
C' S 12 max
(T - 1)3
Σ
|| 11
t=
Therefore, if
min
T 10E 2 2LLmma
(T
Then we must have that A+ B + C <
ET- IE |m 11]
Hence,
T-1 Σ
2F. 2Fo n/T
[V}(())
<
T
T/T
For such choice of n,, we get:
28 6TTTmmm Fo
(206
2222LtTmm Fo
T Σ E
T
VT
Finally, we give the lower bound construction for when the gradient oracles are injected noise with bounded variances:
23

---

Published in Transactions on Machine Learning Research (10/2025)
Theorem 3 (Lower bound with independent noise). Consider the single concurrency setting, where fi(x) |x+b.ll//2 for any b, and is not stalionary point of f. IJ each gi oulput of client i is given by gi = VV((x) ( + &e where & ~ NO ol) is an independent Gaussian noise, then the sequence {xc} generated by Algorithm 2 does not converge to the stationary point of f for any n <1
Proof. For any Xt, Xt-1, we have that Vf((x)) Vf((x(-1) =x, - xx-1. Therefore, m, = my + > aml g
mo + X0 + E==1 Ex-
Now we can write down X recursively:
X++1 Xx 17m; = (1 - n)(x+ 17(m0 - xo) -1 Σ
E.
8=1
Divide both sides by (1 - r))+,, we have:
Xt+1
X 77 - xo)
(1-1) n)+t) (1 (1-
(1 - n)+
(1 n) 1+
==1
Summing both sides from t = to T 1, we have:
T-1
7-1
XT = (1 - m)
X1
(mo - Xo)
Σ (11)
g. 7)
1 -
t=1
Now we multiply both sides by (1 17) and get:
T-1
T-1 Σ T-
XT (1 1) -xxx x1 mmo xo)
Σ
11
T-
1=1
For the last term we have:
T-1T-1
\1-
Σ Σ
(1
T-1-1g E.
[=8
11-1 E
Now by the above equation and the independence of &., we have:
T-1
1 (1 T-
E
|xx||
2
0²
17
T-1
= 2
(1 11) T-
For step sizes 27 $ 1 I 1, we have (1 TT-
<
v - x
For $ S T. we have (1 (1- (T-
S 7.
I+(7-s)m
Therefore,
T/21
E
|xx|| 2]
2 0² Σ
(1 - (1 - -0--
s=1
0² [T(2/2]
25
24

---

Published in Transactions on Machine Learning Research (10/2025)
Cm 0
0.1
SANAY -2x-1
SARMI Ivm:
109
10
106
20"
10
10"
30
20
Iteration
Figure 3: Convergence of SARAH the synthetic least squares problem with independent noisc. We that the algorithm fails to converge with any of the stepsize choices.
which goes to infinity as T + OC.
On the other hand, for 77 S 27: wC show that even under the data homogencous (b; = 0) and noiseless regime (o² = 0), we cannot reach stalionarity if the starting point is not stationary point. Note that when b; and 0² 0, the only stationary point is O. If mo f Xo, have XT (1 n)) - (1 17) Xo. Therefore,
|x||2 =1 17)² |1x
2 (1 Tn) ||x0|
|xol1
2
Therefore, xy cannot converge to 0 when 1) S 27
C SYNTHETIC LEAST SQUARES EXPERIMENT WITH INDEPENDENT NOISE
In this section, we provide an additional experiment verifying Theorem 3 We consider the synthetic least
squares problem introduced in Section 5 where we set 4, Ç = and concurrency 1, i.e, there is only one active worker. In this case, our algorithm AsyncBC-SGD reduces to SARAH. For each output of the client, we add independent, zero-mean, Gaussian noise with variance g² 0.01, i.c, the client outputs gi fx(,)) (x((x(-)) & where & (O, We run the algorithm for stepsizes 1) E {10 2, 10-00-,,00 10 10166-6.1 10 10 10-100 and we see that the algorithm fails to converge for any of the stepsizes. This verifies the lower bound in Theorem 3
D ADDITIONAL EXPERIMENTAL DETAILS
D.1 Synthetic Least Squares Problem
For the synthetic least squares problem, we set the number of clients 4, problem dimension d = 10, and target error (the average of the last 20 iterations) at 0.01. is searched over {1.0x 10-10, 10010,5.00 10-1).
10 10-10 -0....... 110x 5.00
D.2 Regularized Logistic Regression For Fashion MNIST Classification
We use 20% of the training dataset for the validation dataset. We set the number of clients n = 64, set the batch size to 32, and simulate the different computation speeds as in the previous section, where we set T == 50. We perform a grid search over (0.5, 0.1, 0.05, 0.01,0.005) for the best parameter, and select the step size with the best average accuracy at the last 10 iterations. For a = 0.1, 0.01 and 0.001, the selected n for AsyncBC-SGD are 0.01, 0.005, 0.005 respoctively, and for SSD are 0.01, 0.1, 0.05 respectively.
25


Reviews:
[{"review_id": "CNF8SEoz83", "reviewer": "Reviewer_2Ve8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- It is important to study realistic distributed optimization settings involving asynchronous workers. The authors provide a new method by incorporating previous gradient difference as a momentum into the update, effectively removing heterogeneous effects. \n\n- Theoretically, the authors prove that the new method converges in deterministic and stochastic settings, under smoothness and dissimilarity assumptions.  \n\nWeaknesses:\n\n- Although the focus of this paper is general non-convex problems, it would be helpful if the authors can specialize to convex problems. This can be very useful to evaluate the tightness of the bound in terms of heterogeneous effects and convergence rates. \n\n- The current analysis assumes that the delay is bounded by a constant. This might not be true in some cases like failed workers. It would be useful if the authors could relax this assumption. \n\n- The experiments could benefit by demonstrating the scalability in terms of the number of workers.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies distributed machine learning problems with distributed asynchronous workers, where each local worker has access to a local data distribution. The authors build on an existing distributed asynchronous algorithm: SARAH, to introduce a bias correction mechanism. With this new mechanism, the authors prove that this variant can converge under data heterogeneity, avoiding classical gradient dissimilarity assumptions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See comments in Weaknesses.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7C8lLEiXJ2", "reviewer": "Reviewer_dCXw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Pros:**\n\n- This paper applies a SARAH-style technique to eliminate the variance of client selection. It can be extended to the stochastic gradient setting without a significant modification.\n    \n- This paper relaxes the $L$-smooth assumption to a weaker Hessian dissimilarity assumption.\n    \n\n**Cons:**\n\n- The proposed algorithm can not reach comparable performance with Async-GD when the data is homogeneous (Fig 1).\n    \n- The Experiments section lacks a comparison with synchronous algorithms.\n    \n- In Table 1, the dependence of $F_0$ in the $O(1/T)$ term is $\\sqrt{F_0}$ in this work, while the dependence is $F_0$ in existing work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the challenge of data heterogeneity in distributed asynchronous optimization for large-scale machine learning models. Traditional asynchronous gradient methods often rely on a restrictive bounded gradient dissimilarity assumption, which leads to performance degradation or non-convergence when data distribution across workers is highly heterogeneous. To overcome this, the authors propose AsyncBC, a distributed asynchronous variant of the SARAH method. AsyncBC functions as a bias correction mechanism by having local clients contribute only the difference between their local gradients at current and previous points, effectively canceling out data heterogeneity. The server maintains a momentum term, updated with these gradient differences, and orchestrates the parameter updates. The paper provides theoretical convergence guarantees under a milder mean-squared-smoothness assumption for stochastic settings and empirically validates its performance and robustness against varying data heterogeneity compared to existing asynchronous methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Why is the dominating term in Theorem 1 proportional to $\\sqrt{\\tau_C}$?\n    \n2. The equation $\\nabla f_i(x,\\xi)-\\nabla f_i(y,\\xi)=\\nabla f_i(x)-\\nabla f_i(y)+\\xi$ in Sec 4.2 seems to be incorrect. If $x=y$, the left-hand side becomes 0 while the right-hand side is $\\xi$. Based on this formulation, the claim in Theorem 3 is problematic.", "broader_impact_concerns": "This paper focuses on developing algorithms for distributed computing systems. We do not identify any specific societal risks that need to be highlighted in this context.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "S8foXtnFPJ", "reviewer": "Reviewer_LYnB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Strong Theoretical Contributions.\n\n2. Novel Analytical Technique.\n\n3. Robustness to Data Heterogeneity.\n\n4. Stochastic Analysis and Negative Result.\n\n5. Clear Empirical Validation.\n\n---\n\nWeaknesses:\n\n1. Limited Baselines or Related Work Discussions: The evaluation could be strengthened by including more recent or practical baselines or having some discussions (comparisons) for asynchronous federated optimization, such as FedBuff with drift correction, other SCAFFOLD-inspired variants, and AFedRL with momentum methods [1].\n\n2. Convergence Rate: While the method avoids dependence on gradient dissimilarity, the convergence rate is still $O(1/\\sqrt{T})$, which is slower than the $O(1/T)$ rate achievable by some synchronous or homogeneous methods.\n\n3. Assumption Clarification: The mean-squared-smoothness assumption used in the stochastic analysis may not be standard to all readers. A more detailed discussion or examples of its practical relevance would be helpful.\n\n4. Scalability Discussion: While the method targets asynchronous scenarios, the paper does not discuss communication overhead, practical deployment, or scalability across a large number of workers.\n\n5. Typos: Minor typos are present (e.g., \"bais correction\" instead of \"bias correction\"), which should be corrected for clarity and polish.\n\n[1] Asynchronous federated reinforcement learning with policy gradient updates: Algorithm design and convergence analysis. ICLR 2025.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes AsyncBC, a distributed asynchronous variant of the SARAH algorithm designed to address the challenge of data heterogeneity in asynchronous distributed optimization. \n\nThe key contributions are:\n\n1. Bias Correction Without Gradient Dissimilarity Assumption: AsyncBC achieves provable convergence under arbitrary data heterogeneity, removing the common and often impractical assumption of bounded gradient dissimilarity used in prior works.\n\n2. New Convergence Analysis with Virtual Momentum: It introduces a convergence analysis based on a virtual momentum technique, which helps bound the error between true and virtual iterates without requiring assumptions that scale poorly with data heterogeneity.\n\n3. Robustness in Stochastic Settings: The authors extend AsyncBC to stochastic settings (AsyncBC-SGD) and show convergence under the mean-squared-smoothness assumption. They further demonstrate that SARAH-type methods may fail under independent noise, motivating their chosen stochasticity model.\n\n4. Empirical Validation: Experiments on several datasets (Fashion MNIST) show that AsyncBC significantly outperforms baseline asynchronous methods under increasing data heterogeneity, confirming its theoretical robustness and practical effectiveness.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See Weaknesses 1, 3, 4, and 5. (Weakness 2 is not necessarily required.)", "broader_impact_concerns": "There is no Broader Impact Concern from me.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)