Communication-Efficient Heterogeneous Federated Learning with Generalized Heavy-Ball Momentum
Authors: Riccardo Zaccone
Sai Praneeth Karimireddy
Carlo Masone
Marco Ciccone
Venue: Accepted by TMLR ()

Abstract: Federated Learning (FL) has emerged as the state-of-the-art approach for learning from decentralized data in privacy-constrained scenarios. However, system and statistical challenges hinder its real-world applicability, requiring efficient learning from edge devices and robustness to data heterogeneity. Despite significant research efforts, existing approaches often degrade severely due to the joint effect of heterogeneity and partial client participation. In particular, while momentum appears as a promising approach for overcoming statistical heterogeneity, in current approaches its update is biased towards the most recently sampled clients. As we show in this work, this is the reason why it fails to outperform FedAvg, preventing its effective use in real-world large-scale scenarios.
In this work, we propose a novel Generalized Heavy-Ball Momentum (GHBM) and theoretically prove it enables convergence under unbounded data heterogeneity in cyclic partial participation, thereby advancing the understanding of momentum's effectiveness in FL.
We then introduce adaptive and communication-efficient variants of GHBM that match the communication complexity of FedAvg in settings where clients can be stateful.
Extensive experiments on vision and language tasks confirm our theoretical findings, demonstrating that GHBM substantially improves state-of-the-art performance under random uniform client sampling, particularly in large-scale settings with high data heterogeneity and low client participation.

Published in Transactions on Machine Learning Research (06/2025)
Communication-Efficeel Heuuuo Federated Learning with Generalized Heavy-Ball Momentum
Riccardo "accone"
Politecnico di Torino riceardo. saccome Spolito..f.
Sai Praneeth Karimireddy
USC Viterbi School of Engineering karimire @rscc edu
Carlo Masone
Politecnico di Torino
carlo. masone Spolito.5t
Marco Ciccone
Vector Insiiuute
marro.cicome@uvotorinsiitn
Reviewed on OpenReview: https: // openreview. net/ forum? id= JNoFjcLyub
Abstract
Federated Learning (FL) has emerged as the statc-of-the-art approach for learning from decentralized data in privacy-constrainee, scenarios. However, system and statistical chal- lenges hinder its real-world applicability, requiring efficient learning from edge devices and robustness to data heterogeneity. Despite significant rescarch efforts, existing approaches often degrade severely due the joint effect of hetcrogeneity and partial client participation. In particular, while momentum appears heterogeneity, in current approaches its update is biased towards the most recently sampled clients. As we show in this work, this is the reason why it fails to outperform FEDAVG, preventing its effective use in real-world large-scale scenarios. In this work, we propose a novel Generalized Heavy-Ball Ball Momentum (GHBM) and theoretically prove enables convergence under unbounded data heterogeneity in cyclic portial participation, thereby advancing the understanding momentum's effectiveness in FL. We then introduce adaptive and communcationn-ffiiient variants of GHBM that match the communication complexity of FEDAVG in settings where clients can be stateful. Extensive experiments on vision and language lasks confirm our theoretical findings, demonstrating that GHBM substantially improves state-of thett-r performance under random uniform client sampling, particularly in large-scale settings with high data heterogeneity and low client participation
promising approach for overcoming statistical
1 Introduction
Federated Learning (FT.) (MeMahan al. 2017] is paradigm to learn from decentralized data in which central server orchestrates iterative two-step training process that involves 1) local training, potentially large number of clients, each with its own private data, and 2) the aggregation of these updated local models on the server into a single, shared global model. This process is repeated over several communication rounds. While the inherent preeeeciireeevinggggg nature of FL makes it well-suited for decentralized applications with
* *Corresponding author
1 Code is available http:://gtthbb..m//tttteaall

---

Published in Transactions on Machine Learning Research (06/2025)
restricted data sharing, it also introduces significant challenges. Since local data reflects unique characteristics of individual clients, limiting the optimization to a client's 's personal data can lead to issues caused by stalistionl heterogeneity, This becomes particularly problematic when multiple optimization steps are performed before model synchronization, causing clients to drift from the idcal global updates (Karimireddy et al.) 2020
Indeed, heterogeneity has been shown to hinder the convergence of FVD (Hsu et al. 2019), increasing the number of communication rounds nceded to achieve a target model quality (Reddi et al. 2021 and negatively impacting final performance.
Several studies have proposed solutions to miligate the effects of heterogeneity, For instance, SCAF- FOLD (Karimireddy et al. 2020 relies on additional control variables to correct the local client's updates, while FEDDYN 4Acar et al. 2021 uses ADMM to align the global and local client solutions. Albeit theoreti- cally grounded, experimentally these methods are not sufficiently robust to handle extreme heterogeneity, low client participation, or large-scale problems, exhibiting slow convergence and instabilities (Varno et al. 2022
Momentum-based FL methods show promise in addressing these challenges. By accumulating past update directions, momentum can help clients overcome the inconsistencies of local objectives introduced by heteroge- neous data. Several works explored incorporating momentum in FL, either at the server (Hsu et al. 2019) or at client-level to correct local updates Ozfatura et al. (2021): |s Xu et al. (2021). Notably, MIME (Karimireddy ct al. p021 has been proposed as a framework to make clients mimic the updates of a centralized model trained on i.i.d. data by leveraging extra server statistics at the client side. While the theoretical advantages of momentum in FL have been demonstrated under full participation Cheng et al. (2024), it has been shown, both theorctically and experimentally, that its effectiveness is limited when client participation varies across training rounds. Indeed, the only momentun-based FL method that operates under partial participation and does not rely on assumptions on bounded gradient heterogeneity, SCAFFOLDDMM (Cheng et al.) (024), still relies on variance reduction- similarly to SCAFFOLD - to contrast heterogeneity. As a result, it inherits both the limitations of variance reduction in deep learning (Defazio & Bottou 2019) and the drawbacks of SCAFFOLDD in FL, as highlighted by Reddi et al. (202T). In practice, as our work shows, existing momentum- based FL methods exhibit significant limitations in settings with low participation, high heterogeneity, and real-world large-scale problems. Moreover, current approaches often incur increased communication costs due to the additional information exchanged to correct local updates (Karimireddy et al. 2020 2021 Xu et al. environments,
2021 Ozfatura et al. 2021). This can be significant drawback in communication-cons. further hindering the practical adoption of FL in real-world applications and highlighting the critical need for more robust, effective, and cammmication-effiieen FL algorithms. In this work, we provide a theoretical justification for the ineffectiveness of classical momentum in FL demonstrating that due to the interplay of data hetcrogencity and partial participation, the momentum term updated with biasod estimate of the global gradient, reducing its effectiveness in correcting client drift. To address these challenges, we propose novel Generalized Heavy-Ball Ball (GHBM) formulation, which computes momentum average of the past momentum terms. This design reduces bias toward the most recently selected clients, enabling convergence under arbitrary heterogeneity, not only in full participation but also in cyclic partial participation. We then propose FRDHBM, an adaptive and communicaiion-eficin and experimentally demonstrate its significantly improved performance over state-of-the- methods.
decayed
instantiation of GHBM,
Contributions. We summarize our main results below.
We present a novel formulation of momentum called Generalized Heavy- Ball (GHBM) momentum, which extends the classical heavy-ball (Polyak) 1964), and propose variants that are robust to heterogencity and communieatonn-elleeen by design.
We establish the theoretical convergence rate of GHBM for non-convex functions, extending the previous result of [Cenng et al. (2024) of classical momentum, showing that GHBM converges under arbitrary heterogeneity even (and most notably) in cyclic partial participation.
We empirically show that existing FL algorithms suffer severe limitations in extreme non-iid scenarios and real-world settings. In contrast, GHBM is extremely robust and achieves higher model quality with significantly faster convergence spcods than other client-drift correction methods.
2

---

Published in Transactions on Machine Learning Research (06/2025)
2
Related works
The Problem of Statistical Hetcrogencity. The detrimental effects of non-iid data in FL were first observed by (Zhao et al. 2018), who proposed mitigating performance loss by broadeasting small portion of public data to reduce the divergence between clients' distributions. Alternatively, {Li & Wang 2019) uses server-side public data for knowledge distillation. Both approaches rely on the strong assumption of readily available and suitable data. Recognizing weight divergence as a source of performance loss, FEDPROX (Li 2020) adds a regularization term to penalize divergence from the global model. Nevertheless, this was proved ineffective in addressing data heterogeneity Calddrola et al. (0022) Other works (Kopparapu & Lin 2020: Zaccone et al., 2022 Zeng et al., 2022 Caldarola et al., [021] explored grouping clients basod on their
et al.
data distribution to mitigate the challen thallengeso of aggregating divergent models.
Stochastic Variance Reduction in FL. Stochastic variance reduction techniques have been applied in FL (Chen et al. 2021 Li et al., 2019) with SCAFFOLD Karimireddy et al. (2020) providing for the first time convergence guarantees for arbitrarily heterogeneous data. The authors also shed light on the drift of local optimization, which results in slow and unstable convergence. SCAFFOLD uses control variates to estimate the direction of the server model and clients' models and to correct the local update. This approach requires double the communication to exchange the control variates, and it is not robust enough to handle large-scale scenarios akin to cross-device FL (Reddi et al. 2021 Karimireddy et al. 2021]. Similarly, SCAFFOLD-M (Cheng et al. 2024 integrates classical momentum into SCAFFOLD to attain a slightly better convergence rate and maintain robustness to unbounded heterogeneity in partial participation. However, it still relies on variance reduction to tackle heterogeneity, inheriting and the same limitations of SCAFFOLD, as the ineffectiveness of variance reduction in deep learning (Defazio & Bottou 2019).
ADMM and Adaptivity. Other methods are based on the Alternating Direction Method of Multipliers
(Chen et al. 2022 Gong et al. 2022 Wang et al. 2022). In particular, FEDDYN (Acar et al.) 2021 dynamically modifics the loss function such that the model paramoters converge to stationary points of the global empirical loss. Although technically enjoys the same convergence properties of SCAFFOLD without suffering from
its increased communication cost, in practical cases it has displayed problems in dealing with pathological non-iid settings (Varno et al. 2022). Other works explored the use of adaptivity to speed up the convergence of FodAvg and reduce the communication overhead (Xie et al.
2019 Reddi et al. 2021
Use of Momentum as Local Correction. As a first attempt, Hsu et al. (019 adopted momentum at server-side reduce the impact of heterogeneity. With a similar idea, Kim et al. (2024) use the Nesterov Accelerated Gradient (NAG) to broadcast a lookahead global model and adds a proximal local penalty similar to FEDPROX (additional details in Appendix A.1]). However, server-side momentum has been proven of limited elfectiveness under high heterogeneily, because the drift happens at the client level. This motivated later approaches that apply server momentum at each local step (Oxfatura et al. 2021 Xu et al. 2021 and the more general approach by |Karmireddy et al. (2021) to adapt any centralized optimizer to device FL. It employs a combination of control variates and server optimizer state (c.g. momentum) at each client step, which lead to increased communication bandwidth and frequency. A recent similar approach (Das et al. 2022) employs quantized updates, still requiring significantly more computation client-side. Rather differently from previous works, we propose novel formulation of momentum specifically designed to take incorporate the descent information of clients selected at past rounds, which generalizes the classical heavy- (Polyak, 1964). Most notably, we prove that our GHBM algorithm converges under arbitrary heterogeneity in cyclic partial participation - the first mmmentum method achieving this result without relying on other mechanisms like variance reduction.
Lowering Communication Requirements in FL. Researchers have studied methods to reduce the memory needed for exchanging gradients in the distributed setting, for example by quantization (Alistarh ct al. 2017) or by compression (Mishchenko et al., 2019 Koloskova et al. 2020). In the context of FL, such ideas have been developed to meet the communication and scalability constraints (Resizadeh et al. 20200), and to take into account heterogeneity (Sattler et al. 2020). Our work focuses on a novel formulation of momentum that takes into account the joint effects of heterogeneity and partial participation, and that has a heavy-ball structure allowing efficient use of the information already being sent in vanilla FEDAVG, so additional techniques to compress that information remain orthogonal to our approach.
3

---

Published in Transactions on Machine Learning Research (06/2025)
3 Method
3.1 Setup
In FL server and set S of clients collaboratively solve learning problem, with [S] K E N+. At each round & e [T],
fraction of C E (0, clients from S is selected to participate to the learning process: we denote this portion as S - S. Each client i E s receives the server model 0: = = and performs J local optimization steps, using stochastic gradients /. evaluated on local parameters 0:3-1 and batch di sampled from its local dataset D.. During local training, 0. is the model of client at round t after the j-th optimization step, while 0 = ft. is the model sent back to the server. The server then aggregates the client updates / = (0'-1 - 0,), building aseudo-gradient ÿ' that are used to update the model (Reddi et al. 2021
In this work we formalize the learning objective finite-sum optimization problem, where each function is the local clients' loss function with only access to that client's 's stochastic samples:
arg min f(0) = S BERM
Σ (f:(0) = Ed,wD, (f.(0 ES
(1)
The analysis we provide in Sec. 4.3 is based on the above formalization of the learning problem, which is commonly used to model cross-silo FL settings, hence our theoretical results apply to that kind of scenarios. In this context, we prove that GHBM converges under unbounded heterogeneity relying solely on momentum, expanding the understanding of its effectiveness compared to other methods that rely on variance reduction
ADMM to achieve this result. (Karimireddy et al., 2020 Cheng et. al. 2024 Acar et al. 2021). On the other hand, it has been proved that it is not possible to guarantee convergence under arbitrary heterogeneity in the "stochastic" or "streamingg" context which is commonly used for modeling cross-device FL (see the lower bound in Theorem 3.4 of Patel et al. (2022)), ) so considering it in our formal analysis would be of limited usefulness. Hence, we focus the theoretical analysis on the former case. Nevertheless, we also provide large-scale experimental validation on settings that adhore to the characteristics of cross-device FL to demonstrate that GHBM suitable for such real-world scenarios (see Sec. 3.4.
3.2 Addressing Client Drift with Momentum
One of the core propositions of federated optimization is to take advantage of local clients' work, by running multiple optimization steps on local parameters before synchronization. This has been proven effective for speeding up convergence when local datasets are i.i.d. with respect to a global distribution (Stich) 2019 Lin
let al. 2020 McMahan et al. 2017). and is particularly important for improving communication efficiency, which is the bottleneck when learning in decentralized settings. However, the statistical heterogeneity of clients' local datasets causes local models to drift from the ideal trajectory of server parameters. One way of addressing such drift is to use momentum during local optimization, based the idea that a moving average of past server pseudo-gradients can correct local optimization towards the solution of the global problem. At each round, FL methods based on momentum typically use the gradients of the selected clients, whether computed at local (Xu et al. 2021 Ozfatura et al. 2021h or global (Karimireddy et al. 2021 paramcters, to update the momentum termn server-side.
Partial Participation and Biased Momentum. We claim that existing momentum based methods overlook critical aspect of federatod Icarning: partial client porticipation. Indeed, when only a portion of clients participate in the training rounds, the server pseudo-gradient used to update the momentum estimate can be biased towards the previously selected clients, hampering its corrective benefit to local optimization. This effect is particularly pronounced in settings with high data heterogeneity and low client participation (common in cross-device FL), where, as our experiments demonstrate, conventional momentum fails to correct the drift and improve over vanilla FedAvg.
Main Contribution. To address the challenges posed by partial participation, we propose a novel momentum-baseee approach that explicitly accounts for client sampling. Our key idea is to update the momentum term using a psoudo-gradient that approximates the true global gradient over all clients, including those not participating in the current round. By integrating the descent directions from past rounds into local updates, our method effectively mitigates the bias introduced by partial participation, resulting in
4

---

Published in Transactions on Machine Learning Research (06/2025)
0.7
0.7
0.5
- 0.3
0.1
0.1
2500
5000
7500 10000
2500
5000
7500
10000
round
round
Figure Reusing old gradients is beneficial, despite the introduced lag. The plot shows the empirical measure of the deviation between (i) the average of the last server pscudo-gradient (at different parameters) and (ii) the server-pseudo gradient calculated
all the clients (at. the same parameters), varying CIFAR-100 with RESNET-20, in non-iid (a 0, left) and iid (a 10.000, right) settings.
more accurate and robust momentum estimate. Notably, momentun formulation retains heavy-ball structure similar to classical momentum, enabling it to be used in FL without requiring to send additional data from server to clients, thus maintaining the same communication complexity as FedAvg.
3.3 Generalized Heavy-Ball Momentum (GHBM)
In this section, introduce novel formulation for momentum, which call Generalized Heavy-Bale Momenlum (GHBM). First, recall that classical moment um consists of a moving average of past gradients, and it is commonly expressed as in Eq. (2. which can be equivalently expressed in a version commonly
referred to as heavy-ball momentum in Eq. 13 (see Lemma B.1::
Heavy-Ball Momentum (HBM)
m' + 3m 1- + (0'-),'')
(2)
m' + -0--1-8' 2)-2)
(3)
g¹ + g - -ng' 700 g0-1:1") + Sm
0¹ - 0.~1~ 1y12
Let us notice that, when applied to FL optimization, the gradient referred to above as gf is built from updates of clients St (and so on dataset D' := Di), which are usually a small portion of the clients participating the training. Consequently, at each round the momentum updated using a direction biased towards the distribution of clients selected in that round. Indeed, the prerequisites for this update reflect the objectives of the other clients (i) iidness of local datasets or (ii) high client participation. Both conditions are rarely met in practice, and lead to inelfectiveness of existing momentun-based FL methods in realistic scenarios. Our objective is to update the momentum term at each round with reliable estimate of the gradient w.r.t. the global data distribution of all clients. In practice the desired update rule for momentum would use the average gradient of all clients selected in the last T rounds at current parameters 0--1, as in Eq.. 4
Desired Momentum Update
Practical Momentum Update
m' + a0'-Bmi-- -1 +- Σ 30(00-1; (4)
m' + Bm
Σ k=t-T41
(5)
k=t-r41
While Eq. (4 cannot be implemented in partial participation because clients selected in rounds k E [t-r+11, do not have access to model parameters 06-1, is possible to reuse old gradients calculated at parameters O as their approximation, as shown in Eq. 5 This introduces a lag due to using outdated gradients. However, as we show Fig. [ the benefits of reducing heterogeneity greatly compensate for this lag, as increasing 7 leads reduction in the deviation from the gradient calculatod over all the clients.
With this idea in mind, our proposed formulation consists of calculating the momentum term as the decayed average of past - momentum terms, instead of explicitly using the server pseudo-gradients at the last 7 rounds, as shown in Eq. (6) This formulation is close to the update rule sketched in Eq. (5) and has the
additional advantage of enjoying a heavy-ball form similar to Eq. ( (see Lemma B.2 which will be usefull for deriving communication-cffiee
FL algorithms. In practice, the difference w.r.t. Eq. 3 consists in
considering delta > 1:
5

---

Published in Transactions on Machine Learning Research (06/2025)
Generalized Heavy-Ball Momentum (GHBM)
T m - 3m + + (0"-1, D') 0 t 0 -
(6)
m, t (60-- 0¹ 0'-1 (0"-1, + Bm,
0 g1-
(7)
1=1
As trivial to notice, GHBM with == recovers the classical momentum, hence it can be considered as a generalized formulation. The GHBM term is then embedded into local updates using the heavy-ball form shown in Eq. 7 leading to the following update rule:
+ B JJ (0 0f 0
CLIENT STEP:
0.21 - --02--1 - -10 "0,2" (
:d
(8)
GHGB
Discussion on т. The т hyperparameter in GHBM plays a crucial role, since it controls the mumber of server pscudo-gradients to average when estimating the update to the momentum term. Intuitively, when considering only the effect on heterogeneity reduction, the optimal value would be the one that provides the average over all clients. Under proper assumptions on client sampling (see Sec. 4.1). this optimal value is I 1/c, which is the inverse of the client participation rate. As we demonstrate, this property the key factor that allows GHBM to converge under arbitrary hetcrogencity, achieving the same convergence rate in cyclic partial participolion as methods based on classical momentun attain in full parlicipalion (see Sec. 4.3) However, because GHBM reuses old gradients, it introduces lag that grows with т. Therefore, the optimal choice of T comes with an inevitable trade-off between the heterogeneity reduction effect and other sources of error, which we discuss in Sec. 4.2
3.4 Communication Complexity of GHBM and Efficient Variants
As it is possible to notice from Algorithm GHBM requires the server to additionally send the past model 0 which is used to calculate the momentum term Eq. Alternatively, the server could send the momentum term m in both cases, this introduces communication overhead of 1.5x w.r.t. FEDAVG, as momentum is usually applied to all model parameters. However, this overhead can be avoided by leveraging the obser- vation that the choice of r = 1/c is expected to be optimal. Indeed, it is sufficient to notice that, if clients participate cyclically, i.e., the period be- tween each subsequent sampling is equal for all clients, and the frequency at which each client is selected for training is exactly 1/c. Notice that this is still true on average under uniform client sampling, i.e., calling тÜ the sampling period for client i, E [T.] = ===/=
A Algorithm 1: GHBM, LOCALGHBM and FEDAVG
Require: initial model 60, K clients, C participation ratio, T number of total round, and learning rates, E N*
for = T do
S t- subset of clients ~ U(S max(1, K -C)
Send (t-1, 00-00-rv-- to all clients St
for i E St in parallel do
g0.0. --t-1
6:
Retrieve 0' 1 from local storage
i + (8'
m J, (0 0 if -1-1--1 is else 0
9:
for j == 1o do
10:
sample a mini-batch dz from D;
0.3 + 0 8:0 m.. 3m) +Bmi
11:
12:
end
13:
Save model gt-1 into local storage
14:
end
ze + 1841 Σ lest (gt-1 - ((())
15:
16. 0r + 01-1 y
17: end for
Leveraging those observations and exploiting the fact that GHBM has equivalent heavy-ball form, the additional requirement on communication can be traded for a requirement on persistent storage at the clients, allowing them to keep the model received by the server across rounds, as shown in Algorithm [ In this algorithm, which we call LocaIGHBM, т, is adaptive and determined stochastically by client participation. The space complexity is constant in the size of model parameters for the clients and the communication complexity is the same as FVDAVG. We empirically found that performance can be further improved by considcring ff instcad of gt and 0:-1 instcad of gt-r.-1 when calculating m.. This final communication-eficient update rule named FedHBM.

---

Published in Transactions on Machine Learning Research (06/2025)
Table 1: Comparison of convergence rates of FL algorithms. GHBM improves the state-of-art by attaining, in cyclic partial participation, the same rate of classical momentum in full participation. Remind that L is the smoothness constant of objective functions, A = [(0") ming (()) is the initialization gap, o² is the clients' gradient variance, |S| is the number of clients, C is the participation ratio, J is the number of local sleps per round, and T is the number of communication rounds. Ç= sup, || [[)]] and G are uniform bounds of gradient norm and dissimilarity.
Algorithm
Convergence Rate + + B [IV) x
Additional Assumptions
Partial participation?
FEDAVG
Yang et al.
2021
(LA0T)
[SJT
1/2
+
LA
Bounded hetero. 1
x
Yang et al.
2021
[AJA"
[5TCT
1/2
+
T
Bounded hetero. 1
FEDCM
LA(o*+15 C
1/2
L.Blo/V++VBa 1
Bounded grad.
Xu et al.
2021
[S|CJT
+
VisICT
Bounded hetero.
Cheng et al.
2024
LAo"
1/2
+ LA
[STJ
SCAFFOLD-M
Cheng et al.
2024
[SCTT
LAn
1/2
+
1
BTC
2/5
GHBM (Thm. 4.11
LAg"
JT
1/2
+
LA
Cyclic participation
The local learning rate vanishes to zero when gradient dissimilarity is unbounded, ke., G - co.
Applicability of GHBM-based Algorithms in FL Scenarios. Although based on the same principle, our algorithms are suitable for different scenarios. Similarly to algorithms proposed for cross-device FL (Karmireddy et al. 2021 GHBM uses stateless clients, with the main + hyperparameter controlled by the server. This ensures that clients always apply a momentum term consistent with the GHBM update rule, differently from algorithus that require clients participating in nultiple rounds to adhere to their formulation, such as SCAFFOLD and FEDDyN. This is particularly important when the number of clients large and a small portion of them participates in cach round, and it is why, in our large-scale sctting, these methods fail to converge. These desigu choices make our algorithm in practice suitable for cross-device FL, where it offers significant advantages, as experimentally validated in Sec. [.3 On the other hand, FEDHBM and LOCALGHBM take advantage of the fact that clients participate multiple times in the training process to remove the need to send the momentum term from the server, recovering the same communication complexity of AVDAVG. As a result, clients in these methods are stateful requiring to maintain variables across rounds Kairouz et al. 2021 and are therefore best suited for scenarios akin cross-silo FL.
4 Theoretical Discussion
In this section, we establish the theoretical foundations of our algorithms. Our analysis reveals that: (i) the momentum update rule implemented by GHBM in Eq. (5) approximates an update with global gradient, with 7 controlling the trade-off between heterogeneity reduction and the log due to using old gradients; (ii) thanks to this algorithmic design choice, GHBM converges under arbitrary heterogencity even in (cyclic) partial participation. The proofs are deferred to Appendix B
4.1 Assumptions
To prove our results we rely on notions of stochastic gradient with bounded variance (4.1 and the smoothness of the clients' objective functions [.22 which are common in deep learning. Additionally to facilitate comparisons with other algorithms that require it, we introduce the Bounded Gradient Dissimilarity (BGD) (Assumption 4.3 This assumption, commonly used in FL literature, provides upper bound the dissimilarity of clients' objectives. While our main result in Thm. 4.11 does not require this assumption, we use it to demonstrate the heterogeneity reduction effect of GHBM, and to show that, under the proper choice of t, BGD is not necessary. Finally, we introduce the additional assumption that clients participate following a cyclic pattern (Assumption 4.4). Notably, this assumption is only required for obtaining our convergence rate and serves as a technical detail needed deterministically quantify the contributions of the clients to the GHBM momentum term (see Fig. t in the Appendix for illustration of cyclic participation).
7

---

Published in Transactions on Machine Learning Research (06/2025)
Assumption 4.1 (Unbiasedness and bounded variance of stochastic gradient).
Assumption 4.2 (Smoothness of client's objectives).
Tet. it be a constant I. 0, then for any i, 01, O2 the following holds:
Bd,-D. [0: d,)] (;;
(0)((0)) - (12))) < L22 110 8211
Ed.nD. (l: (.) - ( (0: < 0²
Assumption 4.3 (Bounded Gradient Dissimi- larity). There exist constant G' 2 0 such that, vi,
Assumption 4.4 (Cyclic Participation). Let St be the set of clients sampled at any round t. A sampling strategy is "cyclic* with period 1/c if:
S Σ (9.(0) -(())) S G²
S' S' vt>p A s
(t
[S]
Remark 4.5. Our main result (Thm. 4.11) does not require the BGD assumption: indeed show that, under proper choice of T, the effect of heterogeneity is completely removed from the convergence rate.
Remark 4.6, While Thm. 4.11 relies on Assumption 4.4 cyclic participation not enforced in the experiments, where we select clients randomly and uniformly, ensuring fair comparison with algorithms that do not need this assumption in their analysis. For a more comprehensive discussion on the role of the cyclic participation assumption in our work, we refer the reader to Sec. 4.3
4.2 Overcoming Bounded Gradient Dissimilarity in Partial Participation
In this section, we explain the core elements used in our theory to guarantee convergence under arbitrary heterogeneity for GHBM.
Bounding the Participation-indueeed Heterogeneity. Tet recall the main idea behind GHBM: because of partial participation, at each round classical momentum is updated using direction biased towards the distribution of clients selected in that round. As result, recalling that GHBM recovers classical momentum when T = 1, we begin by bounding the effect of heterogeneity induced by partial client participation on the momentum estimate as a function of r. To this end, let us provisionally adopt Assumption 4.3 and assume we perform federated optimization with a single full gradient step in partial participation and consider the momentum update in Eq. (4. In this setup, the following lemma holds:
Lemma 4.7 (Deviation of r-averaged gradient from true gradient). Define S == - as the set of clients selected in the last T rounds, and g"r := 1/18/1 ! (0t-11 as the average server pseudo-gradiens The approcimation of gradient over the last T rounds ger w.r.t. the true gradient quantified by the following:
E |19 v 11 SE
( (1
S ( S
-5:1
|] (
Lemma. 4.7 shows that, increases, the effect of heterogeneity reduces quadratically as the difference between the |S'| and [S]] approaches to zero. The deviation is exactly zero when S = S, i.e. the set of clients selected in the last 7 rounds includes all the clients. While under uniform sampling it unlikely to realize this condition because of the non-zcro probability of sampling the same clients over consecutive rounds, under cyclic participation is possible to make the above error exactly equal to zero
Corollary 4.8. Consider Lemma 4.7 and further assume that, at each round of FL training, clients are sampled according a rule satisfying Assumption 4-4 Then, for any T E (0, d]:
[ - VS 111 < 8 -0)² (c +|V
Remark 4.9. Under Assumption 4.4 and 7 1/c, the BGD assumption (4.3) is not necessary, as the two terms in the left-hand side (LHS) of the above inequality are the same by definition.
An alternative approach could keep track of gradients of each client and then compute g such that it includes the latest gradients of all clients. In that case, cyclic participation not necessary, but calculating the needed is instance of the Batched Coupons Collector problem (Stadje 1990 Perrante & Frigo 2012 Ferrante & Saltalamaachhia 2014), for which closed form solution unknown. That approach would unrealistic implement 8o, motivated by the strong empirical success of GHRM, our analysis we prefer adopting an additional assumption, and providing guarantees under cyelic client participation
8

---

Published in Transactions on Machine Learning Research (06/2025)
Bounding the Overall Error in Momentum Update. In the previous paragraph, we established the role of in GHBM for counteracting heterogeneity and derived its optimal value w.r.t. partial client participation. However, our analysis assumed that all clients selected in the last T rounds compute full gradient on the same server parameters. As discussed in Sec. 3.3, a more realistic update rule for momentum would reuse past gradients as in Eq. ( computed al local parameters. This is because clients selected in rounds E [t - + 1, do not have access to model parameters 6t-1, As result, incrcasing 7 introduces additional sources of error to the momentum term,, which we quantify in the following lemma.
Lemma 4.10 (Bounded Error of Momentum Update). Consider the update rule in Eq.
5 and call
8" + [SST] E 1" the server stochastic average -rruddetgr over the last global steps and the average server pseudo-gradient at current porameters as g" := 1 st1 E 91(0-1).. El - 00-2112 and the error of server update E. == it holds that:
Let also define the client drift Ur == [ -
15|
1
[[0D -000-""mm=[11 12 Under Assumptions
4.2 and
4.4
E |10 - g*r 112] <3
L
Us + 22
Σ (B(IVS(O~>)) E
St
k=1--+1
k=1-T41
(a) Noise
(b) Client drift.
(6) Gradient tag
Lemma. 4.10 shows that the error affecting the GHBM momentum update rule can be decomposed into three main components: the first term (a) is caused by clients taking stochastic gradients mini-batches of data. The dependency indicates that increasing has a positive effect until the gradients of all clients participate to the estimate (i.e. S = S). The second term (b) represents the average client drift over the last T rounds, arising from clients performing multiple local steps. The lemma shows this term has a benign dependency, as increasing т does not increase the overall error due to this component. The last term (c) is the gradient lag, which reflects the error introduced by using pseudo-gradients from clients based on old parameters. While this may be the main source of error (since linearly increases with r), it depends on Ek, which is the deviation of server update from the true gradient. If momentum succceds in correcting local optimization (i.e. & is small), this term will also be small and not hinder the optinization. We verily experimentally that this is indeed the case: the heterogeneity reduction achieved by increasing т outweights the overall error bounded in Lemma 4.10 as showed in Fig. 1
4.3 Convergence Guarantees
We can now state the convergence result for GHBM for non-conver functions in (cyclic) partial participation. Comparison with recent related algorithms is provided in Tab. [
Theorem 4.11. Under Assumptions 4.1 4.2 and then GHBM with r 3/c converges as:
4-4
if we take m = 0, and B, n and ni as in Eq. 120
T T
|
1 S T
LA + V |S/JT
LAOZ
where A = f(0)) - ming f(0), S (1/F) (see Eq.
120 and S absorbs numeric constants.
Discussion. The rate of GHBM shows two major improvements: (i) it does not rely on the BGD assumption (43 and (ii) the dominant term on the right-hand side (RHS) scales with the size of all client population [S], instead of the clients selected in a single round |S|C, thanks to incorporating old gradients. While under the assumptions of Thm. 4.11 any == & vk E N+ will lead to similar conclusions, considering larger interval increases the error due to using old gradients (see Sec. 4.2 so we would like to choose 7 as the minimum allowing convergence under unbounded heterogencity. Indeed, a larger imposes stricter bound the client. learning rate y S O (1/v+) in Eq. (20). Since Thm. 4.11 also imposes 1/c, the bound on "p is explicitly related to the participation ratio C.
9

---

Published in Transactions on Machine Learning Research (06/2025)
Comparison with FedCM. The best-known rate for FEDCM in partial participation (Xu et al. 2021) relies both on bounded gradients and bounded gradient dissimilarity and it is asymptotically weaker than ours. For the case of full participation, Cheng et al. (2024) proved that FEDCM converges without requiring bounded client dissimilarity. Our results extend theirs in that we prove that GHBM can achieve the same convergence rate even in cyclic partial participation. This follows from the fact that in this setting GHBM update rule approximates the one of classical momentum in full participation. Indeed, to validate this theoretical finding, in Figure 2 we simulate a cyelic participation setting and show the train loss of GHBM across rounds, comparing with FEDCM, both when selecting a subset of clients and when selecting them all. As it shown, the curve of GHBM with as prescribed by Thm. 4.11 approaches the one of FEDCM in full participation.
2.5
FwiCM C-0.2
TedCM C-1
2.0
CHIBM C-02
FodAvg 0-0.2
train loss
1.5
1.0
0.5
0.0
0
250
500
760
1000
round
Figure 2:
Comparison between
FedCM and GHBM in cyclic partic- ipation on a linear regression problem, non-iid setting, with = local steps and K 10 clients. GHBM with T = 1/C in cyclic participation (C 0.2) performs similarly FEDCM in full parlicipation (C'=)).
Comparison with SCAFFOLD-M. Recently Cheng et al. (2024) proved that momentum accelerates SCAFFOLD, preserving strong guarantees against heterogeneity in partial participation. However, the resulting SCAFFOLD-M method is still based on variance reduction, i.e., it converges under arbitrary heterogeneity thanks to variance reduction, not because it. uses momentum. Our rate additionally requires Assumption 4.4 but is faster and, most importantly, shows that momentum, when modified according to our formulation, can by itself provide similar guarantees even when not all clients participate.
Advantage of Local Steps and Connections to Incremental Gradient Methods. Thm. does not show an explicit. benefit. from the local steps, similar to the best-known theory for momentum based FL methods (Cheng et al. 2024). However, GHBM offers a clear advantage w.r.t. centralized methods for finite-sum optimization applied in FL (where clients represent functions), referred to as incremental gradient methods. One algorithm of this family, the Incremental Aggregated Gradient (IAG), removes the effect of functions heterogeneity by approximating a full gradient with an aggregate of past gradients, assuming cyclic participation (Gürbüzballaaa et al. 2015). However, this holds only in standard distributed mini-batch optimization, where J = 1. GHBM shares a similar intuition, but applying this logic to the momentum update rather than the gradient estimate is crucial when local steps are involved. Simply extending IAG with local steps would not mitigate client drift-induced heterogencity as GHBM does. In fact, its convergence rate would be bounded by that of FEDAVG in full participation, whose lower bound is known to be alfected by heterogeneity (see Thm. Il of Karimireddy et al. (2020))
On the Use of Cyclic Participation Assumption. The use of eyclic participation in the proof of Thm. 4.11 allows precise control over the clients' contributions to the average of the last pseudo-gradients. This ensures that the r-averaged pseudo-gradient used to update the momentum is unaffected by heterogeneity, which is the important point behind the proof of Thm. 4.11 Under random uniform, due to the non-zero probability of sampling the same client within 7 rounds, this condition is hardly verified. Although one could technically enforce this condition without cyclic sampling by explicitly tracking each client's pseudo-gradient and computing a uniform average across the most recent one from each client- - this would be impractical. Such design would not be compliant with protocols like Secure Aggregation, widely adopted in real-world FL systems, thus posing a significant practical limitation.
Please note that in our analysis convergence under unbounded heterogeneity is not simple byproduct of the assumption, but comes explicitly from the algorithmic structure of GHBM (é.c. setting 7= &. Vk E N+ is necessary). The best-known analysis of FEDAVG under eyclic participation is provided by Cho el al. (022)), which proves that in certain situations (e.g. clients run GD instead of SGD) there can be an asymptotic advantage in the case we prospect with Assumption 4.4 However, it is important to notice that all the results presented in Cho et al. (2023) rely on forms of bounded heterogeneity, and with this respect, the results presented in this work are novel and advance state of the art.
10

---

Published in Transactions on Machine Learning Research (06/2025)
accuracy (96)
85
85
82
75
75
Aecuracy (%6
78
65
accuracy
65
74
55
55
70
45
45
35
35
62
2000
4000
6000
8000
10000
2000
4000
6000 8000
10000
5
10
20
100
round
round
Figure 3: GHBM effectively counteracts the effects of heterogeneity: our momentum formulation
(T > 1) is crucial for superior performance, with an optimal value T = l/C = 10, as predicted in theory. Results on CIFAR-10 with CNN (left) and RESNET-20 (right), under worst-case heterogencity.
5 Experimental Results
We present evidence both in controlled and real-world scenarios, showing that: (i) the GHBM formulation is pivotal to enable momentum to provide an effective correction even in extreme heterogeneity, (ii) our adaptive LOCALGHBM effectively exploits client participation to enhance communication efficiency and (ii) GHBM is suitable for cross-device scenarios, with stark improvement on large datasets and architect
5.1 Setup
Scenarios, Datasets and Models. For the controlled scenarios, we employ CIPAR-10/100 as computer vision tasks, with RESNET-20 and the same CNN similar to a LeNet-ō commonly used in FL works (Hsu et al. 2020), and SHAKESPEARE dataset as NLP task following (Reddi et al. 2021 Karimireddy et al. 2021
For CIFAR-10/100 we follow the common practice of Hsu et al. (2020), sampling local datasets according to a Dirichlet distribution with concentration parameter a, denoting as NON-IID and IID respectively the splits corresponding to a and a = 10.000 (additional details in Appendix C.2). For SHAKESPEARE we use instead the predefined splits (Caldas et al., 2019). The datasets selecting portion C' 10% of them at each round. The training round budget T is set to be big enough for all algorithms to reach convergence in the worst-case scenario (a = 0), constrained by a time budget for the simulations. Being our proposed algorithm always faster, this ensures fair comparison with competitors.
partitioned among K 100 clients,
For simulating real-world scenarios, we adopt the large-scale GLDv2 and INATURALIST datasets as CV tasks, with both a VrT-B 16 (Dosovitskiy et al.] 2021 and a MOBILENETS E2 (Sandler et al. 2018) pretrained on LetgeNet, and STACKÖVERFLOW dataset as NLP task, following Reddi et al. (2021): ; Karimireddy et al. (2021). These settings are particularly challenging, because the learning tasks are complex, the number of client is high (i.e. on the order of 10--10º) and the client participation (for convenience directly reported in Tab. 3 is scarce (see details in Tab. 60. As is, those settings are akin to cross-device FL.
Metrics and Experimental protocol. As metrics, we consider final model quality, as the average top-1 accuracy over the last 100 rounds of training (Tabs. and 3), and commmnniention/ccmppaaaa this is evaluated by measuring the total amount of exchanged bytes (i.e. considering both the downlink and uplink communication) and the wall-clock time spent by algorithm to reach the performance of FVD (Tab. 4.. We also provide full convergence curves for a subset of the experiments in Fig. 5 Results are always reported as the average over independent runs, performed on the best-performing hyperparameters extensively searched separately for all competitor algorithmn.. All the experiments are conducted under random uniform client sampling, as it standard practice. Further details on datasets, splits, models and hyperparameters are in Appendix C
efficiency:
5.2 The Effectiveness of GHBM Compared to Classical Momentum
We provide evidence of the effectiveness of GHBM under worst-case heterogeneity (i.e. 0) by comparing the impact of our generalized heavy-ball momentum formulation to the classical momentum approach, which corresponds to selecting 7 >>1 in the update rule in Eq. (8) As shown in Fig, 3 prior momentum-bassd methods (Xu et al., 2021 Ozfatura et al., 202I) fail to improve upon FEDAVG. In contrast, as 7 increases, GHBM exhibits a significant enhancement both convergence speod and final model quality. The optimal value of 7 is experimentally determined to be 7 x 1/c 10, with larger sub-optimal values only slightly affecting performance (rightmost plot.).
11

---

Published in Transactions on Machine Learning Research (06/2025)
44
40
COLPPOLD
25
70
17
15
10000
70D
round
2009d
7ound
Figure 5: GHBM largely outperforms state-of-the-art methods: the plots show the test accuracy (%) over rounds, with RESNET-20 on CIFAR-100, both in NON-II (left) and IID (middle) settings, and on STACKOVERFLOW (right). GHBM always displays much faster convergence and higher accuracy, even when distributions are IID, confirming robustness w.r.t. heterogeneity and better dependency on stochastic noise.
This experiment demonstrates that, while complete heterogeneity reduction theoretically proven only under cyelic participation (i.e. Thm. 4.11 holds under Assumption 4.4p. GHBM empirically achieves strong heterogeneity reduction even with random uniform client sampling. In particular, the theoretical prescription the optimal value T = 1/c also holds in this setting. Moreover, our communication-llleeen variants always match surpass the best-tuned GHBM, confirming that their adaptive estimate of each client's momentum positively contributes in scenario of stochastic client participation (sce Sec. 4.2
5.3 Comparison with the State-of-art art
Results in Controlled Scenario. We compare GHBM with the most common FL methods, and particular with other momentun-based FL algorithms, including the recently proposed SCAFFOLD-M CCeng al.] 2024), which which uses both the control variates of SCAFFOLD and the momentum of FEDCM (and consequently incurs in a communication overhead of 2.5x w.r.t. FEDAVG). Our results in Tab. 2 underscore that methods based on classical momentum fail at improving FEDAVG in scenarios with high heterogeneity and partial participation, confirming that in those cases they should not be expected to provide a significant advantage over heterogeneity. The general ineffectiveness of classical momentum also holds for SCAFFOL.D-M: as it possible to notice, its performance not significantly better than SCAFFOLD's, and this well aligus with the theory, where the guarantees against heterogeneity come from the use of control variates, while momentum only brings acceleration. In that our results align with previous findings in literature suggesting that variance reduction, besides theoretically strong, is often not effective empirically in deep learning (Defazio & Bottou 2019). Conversoly, our algorithms outperform FEDAVG with an impressive margin of +20.6% and +14.4% on RESNET-20 and CNN under worst-case heterogeneity, and consistently over less severe conditions (higher values of a in Fig. 4 In particular, as shown in Fig. GHBM improves over competitor methods also in IID scenarios: this relates to our convergence rate improving not only w.r.t. heterogencity, but also displaying better dependency on the stochastic noise.
Table 2: Comparison with state-of-the-art in controlled setting (ace@10ke 10000000-2200 20A rounds for RESNET- RESNET-20/CNNN NON-
accenmaee (%%
80
IID (a = 0) and IID (a = 10.000). Best result in bold, second best underlined X indicates covveonvee.e.ce.
72
68
METROD
ChPAR-100 (1rsNer
C1PAR-100 (CX00)
SHAKESPEARE
84
NON-IID
ITD
NON-IID
ITD
NON-II
ITD
0.3
FxnAyG
23.
58.6.0.4
38.3.0a
49.7
47.3
47.1
FRuPROx
24.8 11.1
58.5 10.3
40.6 an2
49.9 10.2
47.3 10.1
47.1
28
SCAFFOLD
30.7
45.5
49.4
2.
FEDDYN
6.0
60..8
51.9.902
50.7
50.8 202
&
ADABEST
35.6
an2
MIME
26.8+2.1
50.0
45.3 20.4
50.9
18.3
0.3
FanAvaM
14.
58.7
42.1
50.7 10.3
50.0
10.
FEDAGG
25.7
18.7 18.3
43.5 10.4
51.3
M0.9
g1.0
SCAFFOLD-M
10.9
60.1
45.7
50.1
50.8
11.0
FEDCM (
22.2+10
53.1 20.2
36.0
50.2
49.2
50.4
Figure 4: Final model quality at differ- ent values of a (lower a + higher hetero- geneity) on CIFAR-10, with CNN (lop) and RESNET-20 (bottom).
FEDADC (0BBM
22.
53.2
37.9 20.
50.2
50.1
MIMeMoa
21.3
60.5
48.2 20.7
50.6
48.5
46.9 an2
MIMELTEMOO
21.2
59.2
46.0
50.7
19.1
LocalCHIM (ours)
38.2 13.0
62.0
31.1 1o.5
51.9 1..4
51.2
$1.1 183
FedHBM (ours)
42.5
62.5 50.55
50.4 20.5
52.00 22.0
51.5 3 as.
61.6 20.
12

---

Published in Transactions on Machine Learning Research (06/2025)
Results in Real-world Large-scale Scenarios. Extending the experimentation to settings characterized by extremely low client participation, we test both our GHBM with 7 tuned via grid-search and our adaptive FEDHBM, which exploits client participation to keep the same communication complexity of FEDAVG. As discussed in Sees. 3.3 and 4.2 under such extreme client participation patterns GHBM performs better because the trade-ofT between helerogeneity reduction and gradient lag is explicitly tuned by the choice of the best performing T, while FEDHBM will likely adopt a suboptimal value. However, results in Tab. 3 show a stark improvement over the state-of-art for both our algorithms, indicating that the design principle of our momentum formulation is remarkably robust and provides effective improvement even when client participation is very low (e.g. C < 1%).
Table 3: Test accuracy (%) comparison of best SOTA FL algorithms on large-scale and realistic settings. GHBM is the best algorithm when client participation is extremely low, while FEDHBM still improves the other competitors by a large margin. X means that the algorithm did not converge.
MOBILENETV2
VIT-B\16
METHOD
GLDv2
INATURALIST
GLDv2
INATURALIST
STACKOVERFLOW
C = 0,79%
C 0.1%
C=
C= 1%
C 0.79%
0.1%%
C= 0.5%
C= 0.12%
FEDAVG
60.3
38.0
40.2 X
47.59 #0.1
68.5 #0.5
65.6
70.7
24.0 #3.4
SCAFFOLD
61.0
X
x
67.5 13.3
X
X
24.8 a9.4
FEDAvGM
61.5 #0.2 X
41.3 X
46.0 10.1
48.4 20.1
70.0 #0.5 X
66.0
71.4 X
24.1 #0.3
MIMEMOM
x
X
24.9 #3.6
CIIBM best T (ours)
65.9
41.8 10.1
48.7 10.1
50.5 20.1
74.3 20.0
68.8 8 10:3
73.5 10.4
27.0
FedHIBM (ours)
65.4 20.2
41.6 40.2
47.3 40.0
49.8 +0.0
73.1
40.9
66.7
10.7
72.1 20.5
24.5
Communication Efficiency. Results in Tab. 1 reveal that our proposed algorithms lead to a dramatic reduction in both communication and computational cost, with an average saving of respectively +55.9% and +61.5%. In practice, while FEDHBM has the same communication complexity of FEDAVGM and GHBM slightly higher, both our algorithms much show faster convergence and higher final model quality, which ultimately lead to significant reduction of the total communication and computational cost. In particular, in settings with extremely low client participation (e.g. GLDv2 and INATURALIST), GHBM is more suitable for best accuracy, while FEDHBM is the best at lowering the communication cost.
Table 4: Total communication and computational cost for reaching the final model quality of FedAvg across academic and real-world large-scale datasets (details in Appendix C.3 The coloured arrows indicate respoctively a reduction (4) and an increase (t) of communication/ www.icatiiiiooouutaatttiio /computational cost.
TOTAL COMMUNIIION CosT (invo s0COROR111)
TOYAL COMPUTATIONAL COST (Wau--aame Tue musza))
METROD
Coars: OVEnnEAD
CHARR-10 (o 00)
GLDv2
C 100 (o - 0)
GLDv2
CNN
RisNNer--20
MoBLIeNerV2
VIT-B116
CNN
Ras-Ner1-20
MounLNNerY'
VIT-B;16
FILAvI
30.9 CB
10.3 GB
GB
483.7
02:05
03:36
13:51
13.56
SCAFFOLD
2x
40.5 GB+ 30.0%
14.2 GB 1ara
51.2 GB 45.0%
967-4 GB 100
01:23
1.34 14
02:30 196.4%
08:26
30
15:15 1..4%
AEDAVOM
1x
21.0 GB. c1.
9.1 GB 13
73.6 GB 18.0%
403.1 GB 16
01:25
1.22 03
05:10
12.00
11:22
18.0%)
11:37
10.75
MisEMMM
3x
21.5 GB
30.9 GB
209.4 GB 200
1.417 TB
01:27
4M
10:42
41:07
41:30
CHBM (anes)
1.6x
8.5 GB
99.89
7.0 as
48.5 GB m8
314
055
00:24
0183
FedHBM (ours)
1x
5.2 GB e5
4.2 GB 20.
29.6 GB 6777.00 usd
2344.
GB
51 80
00:22
82 msc
01:29
59 59.0%
06:21
84.0%%
07:51
48.0%
6 Conclusions
In this work, we propose Generalized Heavy- Ball Momentum (GHBM), a novel momentum-based optimization method for Federated Learning (FL) that effectively mitigates the joint effect of statistical heterogeneity and partial participation. We theoretically prove that GHBM converges under arbitrary heterogeneity in cyclic partial participation, achieving the same rate classical momentum enjoys in full participation. Additionally, we introduce FEDHBM, a communication-eficae maintaining the same communication complexity as FEDAVG. Extensive experiments, conducted under standard random uniform client sampling, confirm that GHBM significantly outperforms stato-of-tho-art. FL methods in both convergence speed and final model quality, demonstrating its robustness in large-scale, real-world heterogeneous FL scenarios.
variant that retains the benefits of moment un while
13

---

Published in Transactions on Machine Learning Research (06/2025)
Acknowledgements
The authors would like to thank Carlo Ciliberto for fruitful initial discussions the theoretical aspects of GHBM and for his valuable feedback about the presentation of the method.
Funding
The author(s) declare that financial support was received for the rescarch, authorship, and/or publication of this article. This study carried out within the project FA Future Artificial Intelligence Research and received funding from the European Union U [PLANO NAZIONALE DI RIPRESA E RESILIENZA (PNRR) MISSIONE 4 COMPONENTE 2, INVESTIMENTO 1.3 D.D. 1555 11/10/2022, PE00000013 - CUP: E13C22001 800001]. This manuscript reflects only the authors' views and opinions, neither the European Union nor the European Commission can be considered responsible for them. A part of the computational resources for this work was provided by hpcopolito, which is a Project of Academic Computing within the Department of Control and Computer Engineering at the Politecnico di Torino www.::hhpp..li....tt... We acknowledge the CINECA award under the ISCRA initiative for the availability of high-performance computing resources. This work was supported by CIN1.
References
Durmus Alp Emre Acar, Yuc Zhao, Ramon Matas Navarro, Matthew Mattina, Paul Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. In ICLR, 2021.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Commuication--fffciatt sgd via gradient quantization and encoding. In NewrIPS, 2017.
Debora Caldarola, Massimiliano Mancini, Fabio Galasso, Marco Ciccone, Emanuele Rodola, and Barbara Caputo. Cluster-driven graph federated learning over multiple domains. In CVPR Workshop, 2021.
Debora Caldarola, Barbara Caputo, and Marco Ciccone. Improving generalization in federated learning by seeking flat minima. In ECCV, 2022.
Scbastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Koncčný, H. Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. ar preprinl arXiv:1812. 110009991, 2019.
Dawei Chen, Choong Seon Hong, Yiyong Zha, Yunfei Zhang, Xin Liu, and Zhu Han. Fedsvrg based communication efficient scheme for foderated learning in mec networks. IEEE Transactions on Vehicular Technology, 2021.
Yicheng Chen, Rick S. Blum, and Brian M. Sadler. Communication efficient federated learning via ordered admm in fully decentralized setting. In CTSS, 2022.
Ziheng Cheng, Xinmeng Huang, Pengfei Wu, and Kun Yuan. Momentum benefits non-iid federated learning simply and provably. In JCLR, 2024.
Yae Jee Cho, Pranay Sharma, Gauri Joshi, Zheng Xu, Satyen Kale, and Tong Zhang. On the convergence of federated averaging with cyclic client participation. In ICML, 2023.
Rudrajit Das, Anish Acharya, Abolfazl Hashemi, sujay sanghavi, Inderjit Dhillon, and ufuk topcu. Faster non-convex federated learning via global and local momentum. In The 38th Conference on Uncerlaindy in Artificial Intelligence, 2022.
Aaron Defazio and Leon Bottou. On the ineffectiveness of variance reduced optimization for deep learning. In NewrIPS, 2019.
Alexcy Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In ICLR, 2021.
14

---

Published in Transactions on Machine Learning Research (06/2025)
Marco Ferrante and Nadia Frigo. A note on the coupon-collector's problem with multiple arrivals and the random sampling. arXie preprint or 1rXiv:209.2266 2012.
Marco Ferrante and Monica Saltalamacchia. The coupon collector's problem. Materials malemålics, 2014.
Yonghai Gong, Yichuan Li, and Nikolaos M. Freris. Fodadmm: robust federated deep learning framework with adaplivity to system heterogeneity. arxie preprinl arXiv:2204.03522 03529, 2022.
Mert Gürbüzbalaban, Asu Ozdaglar, and Pablo Parrilo. Convergence rate of incremental gradient and newton methods. SIAM Journal on Optimization, 2015.
Kaiming Hc, Xiangyu Zhang, Shaoqing Ron, and Jian Sun. Deep residual learning for image recognition. arXiv preprinl ar wxXx:1512.03320 2015.
Kevin Hsieh, Amar Phanishayee, Onur Mutlu, and Phillip Gibbons. The non-IID data quagmire of decentral- ized machine learning. In ICML, 2020.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Mcasuring the effects of non-identical data distribution for federated visual elassification. arXiv preprint arXiv: 10X:::90000000 009906335, 2019.
Tru-Ming Harry Hsu, Hang Qi, and Matthew Brown. Federated visual classification with real-workd data distribution. In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm (eds.), ECCV, 2020.
Yerlan Idelbayev. Proper ResNet implementation for CIFAR10/ CIFARIO/CIFARI00 CIIFAR10 in PyTorch, 2021.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In ICML, 2015.
Peter Kairouz et al. Advances and open problems in federated learning. Found. Trends Mach. Learn., 2021.
Avetik Karagulyan, Egor Shulgin, Abdurakhmon Sadiev, and Peter Richtárik. Spam: Stochastic proximal point method with momentum variance reduction for non-convex cross-device foderated learning. arXic preprinl ar 2rxiv22405.20122 2024.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In ICML, 2020.
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Breaking the centralized barrier for cross-device federated learning. NewrIPS, 2021.
Gecho Kim, Jinkyu Kim, and Bohyung Han. Commmicatiinn-fffcicnnt federated lcarning with accelcrated client gradient. In CVPR, 2024.
Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. In ICLR, 2020.
Kavya Kopparapu and Eric Lin. Fodfme: Sequential efficient federated learning on non-iid data. arXiv preprinl ar Xiv:20006. 10937, 2020.
Daliang Li and Junpu Wang. Fedmd: Heterogenous federated learning via model distillation. arXiv preprint arXiv:1900.088 03581, 2019.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Feddanc: A federated newton-type method. Asilomar Conference on Signals, Syslems, and Compulers, 2019.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In MLSys, 2020.
Tao Lin, Sebastian U. Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-ban hani-s use local sgd. In ICLR, 2020.
15

---

Published in Transactions on Machine Learning Research (06/2025)
Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. In Newr/PS, 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication- efficient learning of deep networks from decentralized data. In Artificial intelligence and stalistics, 2017.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXic preprint arXiv:1901.09266 2019.
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtarik. ProxSkip: Yes! Local gradient steps provably lead to communication accelcration! Finally! In ICML, 2022.
Konstantin Mishchenko, Rui Li, Hongxiang Fan, and Stylianos Venieris, Federated learning under second-order data heterogeneity, 2024. URL
Emre Ozfatura, Kerem Ozfatura, and Deniz Gündüz. Fedadc: Accelcrated federated learning with drift control. 2021 IEEE International Symposium on Information Theory (ISIT), 2021.
Kumar Kshitij Patel, Lingxiao Wang, Blake E Woodworth, Brian Bullins, and Nati Srebro. Towards optimal communication complexity in distributed non-convex optimization. In NewrIPS, 2022.
Boris Polyak. Some methods of speeding up the convergence of iteration methods. Ussr Compulational Mathematics and Mathematical Physics, 1964.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. In ICLR, 2021.
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Fedpaq: A communicttion-cffiicett fedcrated learning method with periodic averaging and quantization. In AISTATS, 2020.
Mark Sandler, Andrew G. Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chieh Chen. Mobilenetv2: Inverted residuals and linear bottlenecks. In CVPR, 2018
Felix Sattler, Simon Wiedemann, Klaus-Robert Müller, and Wojeiech Samek. Robust and communication- efficient. federated learning from non-i.idd data. IEFE Transactions on Neural Networks and Learning Systems, 2020.
Wolfgang Stadje. The collector's problem with group drawings. Advances in Applied Probability, 1990.
Andreas Peter Steiner, Alexander Kolesnikov, Xiaohua Zhai, Ross Wightman, Jakob Uszkoreit, and Lucas Beyer. How to train your vit? data, augmentation, and regularization in vision transformers. TMLR, 2022.
Scbastian U. Stich. Local SGD converges fast and communicates little. In ICML, 2019.
Farshid Varno, Marzie Saghayi, Laya Rafice Sevyeri, Sharut Gupta, Stan Matwin, and Mohammad Havaci. Adabest: Minimizing client drift in federated learning via adaptive bias estimation. In ECCV, 2022.
Han Wang, Siddartha Marella, and James Anderson. Fedadmm: A federated primal-dual algorithm allowing partial participation. arXiv preprint arXiv:220s.15: 2022.
Yuxin Wu and Kaiming He. Group normalization. In ECCV, 2018.
Cong Xie, Oluwasanmi Koyejo, Indranil Gupta, and Haibin Lin. Local adaalter: Commmication--ffciintt stochastic gradient descent with adaptive learning rates. CoRR, 2019.
Jing Xu, Sen Wang, Liwei Wang, and Andrew Chi-Chih Yao. Fedem: Federated learning with client-level momentum. arXiv preprint 211:22106.10874 2021.
Haibo Yang, Minghong Fang. and Jia Liu. Achieving linear speedup with partial worker participation in non-III) federated learning. In ICLR, 2021.
16

---

Published in Transactions on Machine Learning Research (06/2025)
Riccardo Zaccone, Andrea Rizzardi, Debora Caldarola, Marco Ciccone, and Barbara Caputo. Speeding up heterogeneous federated learning with sequentially trained superclients. In TCPR, 2022.
Shenglai Zeng, Zonghang Li, Hongfang Yu, Yihong He, Zenglin Xu, Dusit Niyato, and Han Yu. Heterogeneous federated learning via grouped sequential-oo-parallel training. In Arnah Bhattacharya, Janice Tee Mong Li, Divyakant Agrawal, P. Krishna Reddy, Mukesh Mohania, Anirban Mondal, Vikram Goyal, and Rage Uday Kiran (eds.), Dulabase Systems for Advanced Applications, 2022.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. arxiv preprinl 1806:800.0055 2018.
17

---

Published in Transactions on Machine Learning Research (06/2025)
A Additional Discussion
A.1 Extended Related Works
Recently, similarly based variance reduction SCAFFOLD, (Mishchenko et al. 2022 propose SCAFFNEW to achieve accelerated communication complexity in heterogeneous settings through control variates, guaran- teeing convergence under arbitrary heterogeneity in full participation. The work by Mishchenko et al. 2024). under the assumption of second-order data heterogeneity, proposes an algorithm which can reduce client drift. by estimating the global update direction as well as employing regularization. The proposed algorithm can be seen as combination of FEDPROX with SCAFFOLD /SCAPP/N/ and similarly relies on additional server control variates to correct the drift, the underlying principle is still variance reduction. Quite differently, CHBM is based on momentum, properly modified to tackle heterogencity and partial participation in FI. Similarly to the already discussed MIME (Karimireddy et al. 2021 Karagulyan et al. (2024) propose the SPAM algorithm and leverage momentum as a local correction term to benefit from second-order similarity.
Comparison with FedACG (Kim et al., 2024). We provide comparison with the FedACG algorithm based on: algorithmic design, theoretical guarantees and empirical results. Algorithmically, it has two modifications w.r.t. FED (i) it uses the Nesterov Accelerated Gradient (NAG) to broadcast lookahead global model and (ii) adds a proximal local penalty similar to FEDPROX w.r.t. this transmitted global model. The method has the same communccation complexity as FedAvg, because it does not exchange additional information. Our work proposes instead novel formulation of momentum, explicitly designed to provide an advantage in heterogencous FL with partial client participation. We propose both the main algorithm (GHBM), which has stateless clients but has 1.5x the communication complexity of FedAvg, and communication efficient versions (e.g. FEDHBM), that preserve the communication complexity as FedAvg, the cost of using local storage. From theoretical perspective, the convergence rate of FedACG does not prove any advantage w.r.t. hetcrogencity, since it still relies the bounded hetcrogencity assumption. GHBM is proven to converge under arbitrary heterogeneity in cyclic partial participation, recovering the same convergence rate that Cheng et al. (2024) proved for FEDCM when in full participation. This is a significant advantage that then reffocts in significantly improved performance. From an empirical perspective, simulation results are presented in Fig. 5 While it faster than FedAvgM, it still falls short behind our algorithms heterogeneous scenarios. This consequence of the same issue we showed Sec. 3.3 for classical momentum.
Cyclic participation with period p=3 for any round k s.t. k mod = 0
Round t=0
Round t=1
Round t=2
Round t=
Round tak+1
Round t=k+2
Figure 6: Illustration of cyclic client participation with total of K - 9 clients. Thm. 4.11 holds under the assumption of cyclic participation, which simply states that there is any fixed order (so client shuffling methods like Shuffle-Once are compliant with the assumption) in which clients appear across rounds с rounds. In the above image, K C = clients are selected for training, i.e. each client selected exactly once every p = rounds.
in the training, É.e. cach client is sampled every p 1
A.2 Notes on Failure Cases of SOTA Algorithms
In this paper, we evaluated our approach using the large-scale FL datasets proposed by Hss et al. 2020 Notably, several recent statc-of-the-art FL algorithms failed to converge on these datascts. For SCAFFOLD this result aligns with prior works (Reddi al. 2022 Karimireddy et al. 2021), since it is unsuitable for cross-device FL with thousands of devices. Indeed, the client. control variates become stale, and
18

---

Published in Transactions on Machine Learning Research (06/2025)
may consequently degrade the performance. For MIMEMOM (arrmireddy et al., 2021 : despite extensive hyperparameter tuning using the authors' original code, we were unable to achieve convergence. This finding is surprising since the approach has been proposed to tackle cross-device FL. To our knowledge, this is the first work to report these failure cases, likely due to the lack of prior evaluations on such challenging datasets. We believe these findings underscore the need for further investigation into the factors contributing algorithm performance in large-scale, heterogencous FI. scttings.
B Proofs
Algorithms
To handle the proof, analyze simpler version of our algorithm, in which use the update rule in Eq. 5 instead of the one described in Eq. (6) The resulting Algorithm 3 we analyze is reported along the plain
GHBM (Algorithm 2 we used in the experiments. Both algorithms enjoy the same underlying idea: use the gradients of a larger portion of the clients to estimate the momentum term.
Algorithm 2: GHBM (PRACTICAL VERSION)
Require: initial model 09, K clients, C participation ratio, T number of total round, and learuing rates, E N+. for f to T do S <- subset of clients ~ U(S, max(1, K C))
for i St in parallel do
0..00 - (t-
for j= do
sample mini-batch di,j from D;
(t +- V di.)) + Brig
0. + 81501 mp
6-
end for
end for
u' f 1ST
Σ igst (g--1 - -P(
0 +- gt y
m + (0--r 81)
14: end for
Algorithm 3: GHBM (THEORY VERSION)
Require: initial model 80, clients, C participation ratio, number total round, 1 and m learning rates, 7 E N
1: for f = to do
2: S +- subset clients ~ 24(5, max(1, K CC))
3: for E St in parallel do
gr.0 - gr
for j= to J do sample a mini-batch dey from D;
7:
u. + SV f16.5 -1
di.)) + (1 p
8 8 nu
end for
10:
end
11:
u' f-
m | J
Σ iest (0--1_ -
12.
0e +- 0t-1-
(1 8)
mit1
$ @--r gc)
0r 4- gr-1
end for
In the following, we list the differences between the two:
Explicit use of r-averaged gradients when updating the momentum term (line 13). This can be implemented by keeping server-side an auxiliary sequence of models Ø², in which the momentum added client side subtracted server-side (line 12), such that taking the difference of two models gives the sum of pseudo-grads
Use of convex sum in local updates (line 7). This is done align with the formulation of momentum methods in Cheng al. (2024), and more in general with the formulation of momentum commonly
19

---

Published in Transactions on Machine Learning Research (06/2025)
analyzed in literature. There is no theoretical difference between the two versions, they only differ by constant scaling (Liu et al. 2020
3. Use of gradients averaged over local steps (line 11). This done to align with the analysis of Cheng et al. (2024; ; Xu et al. (2021). and it is equivalent to coupling server and client learning rates (i.e. setting = JJ in Algorithm where is the server learning rate we would use in Algorithm
The two algorithms have similar performances, which reported in Fig.
90
75
acc1lracy (%)
accuracy (%)
75
60
60
45
45
30
30
15
CHIBM
CHeM-theory
15
CHBB
CHBM-theory
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
round
round
60
accILracy (%)
32
accuracy (%
45
24
30
16
15
CHBB
GHBM-theory
CHBM
CHBM-theory
0
2000
4000
6000
8000
10000
2000
4000
6000 8000 10000
round
round
Figure 7: Comparing the GHBM implementation analyzed in theory (Algorithm with the one proposed in the main paper (Algorithm 2) The plots show the convergence rate CIFAR-10 (top) and CIPAR-100 (bottom), in NON-IID (left) and IID (right) scenarios with RESNET-20 architecture.
Preliminaries
Our convergence proof for GHBM based on the recent work of Cheng et al, (2024). which offers new proof techniques for momentum-based FL algorithms. Throughout the proofs we use the following auxiliary variables to facilitate the presentation:
IS
4: = |S Σ
E
(9)
im1
f(0) 2)
m 113]
11
(10)
~ = 015+1 0.
(11)
E = 1 [s]
E (
[S]
1s
A = E
k- 10
-9¹
(12)
S
k=t-r+1
N = E -6|1
-f ||| )||]]
(13)
20

---

Published in Transactions on Machine Learning Research (06/2025)
Additionally, here report the bounded gradient heterogeneity assumption. It is used to quantify the heterogeneity reduction effect of GHBM varying its т hyperparameter. Notice that our main claim does not depend on this assumption, as for the optimal value of T = 1/C the assumption is not needed (see Lemma 4.7
B.1 Momentum Expressions
In this section report the derivation of the momentum expressions in Eq. (3] and 7 from the main paper. Lemma B.1 (Heavy-Ball Formulation of Classical Momentum). Let consider the following classical formulation of momentum:
m' Bm 1- + g0(0011) 0¹ = 0 nyñ"
(14)
(15)
The same update rule can be equivalently expressed with the following, known as heavy-ball formulation:
0' 0- 3(00 -100--100-- (0"(0"
(16)
Proof. First derive the expression of m. from Eq. both for time and t
m 0 8r)
(0r ((-1)
m
r
Now plug these expressions into Eq.
14 to obtain 16
0 0*) (0--2 (0--2-0t 0C-1)
(80-11
7
(0' g²-1) = (8--1 2) - "8" (8"-1)
l¹ g'-1 + 3 (0--1 2) - n (0"-1)
Lemma B.2 (Heavy-Bal formulation of generalized momentum). Let us consider the following generalized formulation of momentum:
m Bi + of (0'-1)
(17)
0--1 mm
(18)
The same update rule can be equivalently expressed in an heavy ball form, which we call as Generalized Heavy-Bal Ball momentum (GHBM):
0' 0r-1 B (00-1 00-01-0---11 0-- -00-1-0---11
(0--1)
(19)
Proof. First derive the expression of m. from Eq. 18 both for time i and
m (01-1 0²)
(0'
gr-
m
17
21

---

Published in Transactions on Machine Learning Research (06/2025)
Now plug these expressions into Eq.
17
0 - )
3
(0--k-1 k)-
(0(-"11)
7
T
11
B
(0' - 8
0
0 (0-R-1) 11/
T
k=1
8
0 1
+
B
Σ
(gi - -0i-h-1) (0'1(111)
k=1
B (0
0'
0²
01- -0--100--11 ng¹((0" (0'-1)
Where the last equality
19
comes from telescoping the summation on the rhs.
B.2
Technical Lemmas
Now cover some technical lemmas which useful for computations later on. These are known results that are reported here for the convenience of the reader. Lemma B.3 (relaxed triangle inequality). Let {uI...., Un be n vectors in IRd, Then, the following is true:
Σ
v; ?
Proof. By Jensen's inequality, given convex function d, series of n vectors (0i,..., vn) and series of non-negative coefficients A with E A = 1, it results that
S
Σ
A (1:)
1=1
Since the function - //0/12 convex, can use this inequality with coefficients \ =... An 1/n, with Ei d and obtain that
2
1
U
n
2
71
n
n
0
B.3 Proofs of Main Lemmas
In this section we provide the proofs of the main theoretical results presented the main paper.
Proof of Lemma 4.7
(Deviation of r-averaged gradient from true gradient)
Let define : St and S, := S.s. Let us note that when all clients participate, i.e. S, = 0, the claim is trivially true. For S2 0, we expand the terms at the left-hand side using their definitions follows:
22

---

Published in Transactions on Machine Learning Research (06/2025)
18|
1
1
7t
E
91
92
(20)
SST
S
1
= E
9
(21)
8
|8|
S
FES.
KES d
leuma B.3
2
E
Σ
gl
(22)
St
S
S
iES.
KES
73
T4
Let us consider first Tg. We have:
T3 = E
E
1
Σ
9
(23)
[8]
|S]
iES,
Jemma 1+3
1
SS
||
(24)
S
[S
iES:
|6g v + v 1
1
E
Σ
(25)
S
[S]
IES,
lemma 33
2 |s Σ (111 4 + +
1 (
21E
(26)
[St
[S]
|S |s + Σ -[ [ 
assumption
4.3
1
2E
(27)
SSH
(S]
1ES;
Since the term (l( does not depend on the index i, we get
|s.Ic++ + Σ 1 1eeeeee---.
T-dlic
1
2E
|
(28)
|S
|S|
)
+ 10//1
1
2E
(29)
|8
|8]
2E
(1 |S
1
(o= (
(30)
(S]
Now, note that S S
|8,1 = 1. Therefore,
1
18,1 (o2 ([ )
Ta < 2F
(31)
|SH
|S|
(1S) (18) - |S+
| (G² |V
27
2E
(32)
|S|
23

---

Published in Transactions on Machine Learning Research (06/2025)
Moving now to Ta, we have:
2
T = E
E
Σ MES,
g
(33)
[|]
S
RES a
lemma 183
E
S
>
||bb11
(34)
[S]]
S
2
= E
S
119h V5(60'1) +
F 11?
(35)
|
(11t 1 11(00~1111 11 11 1 
lemma B33
1
21
|
Σ
(36)
RESH
assumptton 4.3
2
-prssl lSSl
2E
+
Σ
(37)
[5)
-2
1
| (|///1) 1isi
(38)
(S))
((15)
27
=2E
-G (
(39)
(40)
Observing that [S |S| - | we obtain:
S S
27
(a² + V ||(00))))))))))))))))>>)))))}))) = E
((5))=111) 27 (c² + [((00)1)))
-18
Ti S 2E
(41)
|S|
Finally, by plugging
31 and
in 22 we obtain
[1()|= |
|] (oe + (I1)(1)1))
00000000 -V](0)] (Eg()))
SS]
which concludes the proof.
Proof of Corollary 4.8
This corollary follows from Lemma
4.7 which states that
1100-100- -v < (E
(
(SS- [
S
S
| (G + +IVS(1))))
ESTN
To prove the results, we use (i) Assumption 4.4 (ii) the fact that |S = |S|C vt and (iii) S is union of T
disjoint St sets. Using points (i)-(ii), and assuming 7 E [0, dl, it follows that:
- (0)-0))v((01) s 8 (1-
(o++
+ ++[1((1)1*)
24

---

Published in Transactions on Machine Learning Research (06/2025)
Proof of Lemma 4.10
(Bounded error of delayed gradients)
Note that, by Assumption 4.4
S
|S|C Vt, and that |S|CT= =S+|:
| |Sk]
A E
9
kij (0%:5-2) gx*
(42)
|J
km 1
2m jml
|s$1 |Sh|
9, (8h15-1) - 31(0111)
(43)
-=1-++]
im j=1
|st
1
ch (0=h 1- - 9.(0, + 9.(0 - 11(00-1) + 1 - (0(00
SSk
k=t-r+1
j=1
(44)
37 + +T)
(45)
1st
T = E
go (0 - (0(
(46)
S
k=1-T+1
02 a²
(47)
7 S
|8:
1st
Ta T2= B
Σ
9: 9:(00=1))
(48)
J
15
I
||10::511
- 00-
(49)
JS kmt-r4 7+1 i=1 j=1
1
Uk
(50)
kst-T+1
1 J
Ta EE
(9:(8h - (01-1)
(51)
|
JJ
k=1-T41
j=1
Σ
|110k -0
(52)
1S|T
1
Σ
E 100-1-0--
-
(53)
k=1-+41
17
Σ (t- k)) E ||0t - ot-
(54)
< 2
Σ
(E
(8|1v/(0t-)1}} + Ex)
(55)
k=
25

---

Published in Transactions on Machine Learning Research (06/2025)
So, combining with lemma Lemmas B.5 and B.6 we have:
T
To
T
A
<
+ L
Ut
+ 22 17
1)
Σ ( [| +
(56)
|5:|J
1=1
B.5
To?
+ (T- Σ
T-1
E | ||||| + E.)
(57)
|8
L'T (1 21+
+2.J
E1)
14
To²
T-1
lemma B00
+2L2 (- Σ
( |||]] + +33
E
(58)
|5:|J
T4 + 22 (4n) ((1 - 3)2 + e(BnLT))))
Σ
& + E [|V5(0-)))1)
2 2 L (2ent STTG,)
T6
To²
+ Ta +
(a1 + 2/ 1))
E
V vf(0"=))|1" ||1" + +E,) To
(59)
|
02
B.4 Convergence Proof
Lemma B.4 (Bounded variance of server updates). Under Assumplions 4-1 and 4.2 it holds that:
T
Σ E
En
3
E
213 T+ |8:1 + 63
|19]
(60)
53
5
1=1
T=
448
(mJ
+
7
5
Proof.
& = E [V - 11
(61)
B [[(1 ( + (VV - g1
(62)
= a [[(1 - 30(4 -mm)m))) 11] + 8 ||(11(11)) - -
(63)
+ 28B (1111111 (3) m.), v((0-11) 1 Σ s
15*
(
(64)
26

---

Published in Transactions on Machine Learning Research (06/2025)
Using the AM-GM incquality and Lemma
B.
s 1 + 2
E
| 233 (7t + +AO+ +
- B)
+ 4,8 + 88
L2 Σ
Us + 22L?7
Σ (E (B(1v5(0-)))) ||1] + +Ex)
[-1
(65)
k=t--+1
k=
lemma 1.10
1+
E
[|(1 (V 1(00
m ||]]
+ (2 + 43) i + -632 0²
+
(66)
[5:1
L2 Σ
+ (6.3- 88)
Uu + +222'7²
Σ
E
| [| 11 +Ex)
k=1-++1
b=t-T+1
TI
S (1- - 3)2 (1 (1+ 2 E V - m + - +
(67)
d²
+ 6,8
+ 63% + 14ST
|
Applying the AM-GM inequality again:
S (1- 1+ 2) 111 (1+ E [1 |I - 11] +
(68)
(1+ 1 3 E | ((0 - 3| + 6.0 0²
+ 6.8 + 1487
|8||]
assumption 12
1 2) [ 3 E
B)3
(69)
(1+ 1
LE [100-1 - ]-2118
+632 0²
+
+
+ +68% + 1487
3
S
[1+ (2) [ [ + [ EI-1+
< (1-181 -)2
(70)
4
+ [+ 1 }) 13,1 (E || 3|1] + Ei.1)
]
+ 6.3² o²
+ +63% + 1487i
|
Where in the last inequality we used the fact that:
|000 - or -p- s 2n² (1V 2 | -
-mili 1²)
Now notice that (1 B)2 (1 + -)) (1+ 4) $ (1 - ()) and that 2(1- -
B)2 (1 + () (1+ 1 s $
& 5 (1- +
2 1z7 [
|| |
+ (111 + 6882 o²
+ 6.9% 149T
(71)
18:11 + 6,3
= 11 B +
2 121p2)
2
0²
E-11
+ 6,3% 143T
(72)
3
S
Define:
T= 3===23-13300 (1 + 1
Ta = 22 (2en)
01 = 2. (Ani ((1 3)2 + e(BnI.T))) + 2 - 1)
27

---

Published in Transactions on Machine Learning Research (06/2025)
Summing up over T and substituting into Ti the expression for Ue:
T
T-1
2 122 + 14,8a1
Σ
& $
1 1- 3-3- 3
(73)
B
2
122 14881
||| +
B
03
143 (T2 TTa) T + 6,3 o²
T
+ 6,3
Σ Y
|
1=1
We now have that:
02: =
1 3 3+ 1,212 + 148 148 (4 ((1 - 3) + =((3).TT))) + (T 1)]
(1
(74)
1 B + 12² +43 B1) + e(BnLT)²) + (T
(75)
8
2 1,2 + 11236 [1 - B)² + (BTII.T) + (r - 1)]
< 1 - B +
(76)
(77)
Now impose (n:J) S (3T/FBnLTe)- and 1) <
8
We have that:
V8L
02 - 1
23
+
= 1
(1-8
5,9
(78)
8
8
8
33
03 S 8
(79)
1487 = 1481 T 32 (1 (1+
11+201183313)
(80)
(nJ
[ + 2( 2
(81)
I 7882 o² T
(82)
|
Where in the last inequality we apply:
2D) () ((mIL)))))
1
<
[l:si
Plugging all the terms together we have:
Σ & S (1
T
T-1
33 T-1
13/32 o²
Σ
& +
Σ
E [|
+
T+
(83)
8,
8
S
t=
1=
+ (c) (e
+ 63
7
tm/
Rearranging the terms completes the proof.
Lemma B.5. Under Assumplions
4.1 and
4.2 for Eq.
g
il holds thal:
u 2 25
Jn
3
2 12
(84)
T
T Σ =
Σ u 3
2
+2
(85)
28

---

Published in Transactions on Machine Learning Research (06/2025)
Proof.
I
0000 - 0- 0-
S 2
Σ
+ +2j
(86)
lemma B3
2j E
[3]
c
- 32
(87)
For any 1 1 - 1- using nT - 3J
1
S B(5+1) we have:
1
27
k ||
(1+ + j) ||55 cha-111
17
E
(88)
3
1
E
k
+ +1+ 32
12 +
| 121)
(89)
5
1+ 1
1
E
+ +1 (1++)m
1 E
|
5.
-1 |1]
(90)
1+1
1+ 2
E
|| ||²
+ +1++)m331120
(91)
3
(1+))' sea
e
[1.000]]
- L2
(92)
So it holds that:
E
10.0 - 0--11]]
S 22²
E²B ||<:00
+ +452m/ +2jnn0²
(93)
22 2E ||5-0013
+ 2jm 02 82 18
(94)
So, summing up over i and j:
1 |S|
(..001121 + +1
U <
2c j²B
(95)
|S|
i= 1=
< 22
Jn
82 02 21
(96)
Finally, summing up over T:
T
Σ u. < STITI
23'h 0 +2.22²² Σn =
(97)
mm1
T + 222222
(11 B)² (c(BLTT) Σ
E E [IV)(0-))1(1)) + 20n BTTGG,
(98)
To
T-1
< Ti + 01
E + E [| + T2
(99)
Lemma B.6. Under Assumptions il holds for & 2 0 that:
4.1
4.2 and 4.4 if 224c(m)LL) ((1 (11-) + e(BnLT)?) 1, for Eq. 11
E + E [| + 2en TTG,
E,
(100)
J2
t=
29

---

Published in Transactions on Machine Learning Research (06/2025)
Proof. Note that 5:00
-1 ((1 B)m + (9:(0"-1)),
|s|
|s|
1
1 s 2n
(1-3) || ||
00
1)²
(101)
S
[
For any a > O, considering each client participates to the train every T t rounds:
|1 E [00=((0=1) (0000=111) 10-1=~1
(102)
Jemma [36]
(1 + a)B 10 111--111111 |1/ +
(103)
1 + -)
(o=(0-=1) g 2/00-~11>11 |1
$ (1 a)E
(1
(104)
1 !)
L'B -10--1-0
11-
(105)
$ (1 a)E
(1
(106)
+2 1+ !
1² Σ
(80++ + E (10)((---))))))
(107)
k=1
$ (1+ a}$E |119(00--))11)) +
(108)
+2 1+
1,212²
EST + E [||00~))))))) (1 + a)
k=1
$ (1 =)= (1ax(8+=1))1) 111 +
(109) (
+2 2 (1+ L L'T
Σ
[-1
Ex + E || ++)+
k=1
Where t, == mingery s.t. i E S²). Now take a = f:
[119:(00=1))1 s eE
(110) (
E + E | (ll
+ 2072 LZT (++1)
Σ
So:
1
11.. [1..00-1))11] 1
T
2 2(1-9) 3)2 ( ( ( 1 +
g² [8] S
(m)
3 S
Σ E
1=1
T
< Σ
4n/ (1 - -3)2 (1-1 + ( -)) +
(112) (112)
1=1
Ex + E L
T
isI
( +
(1+11) Σ
+ 2n 82
Σ
E
E
t=1
i=1
E7-1 + E 1
T
(81)) ST1)
S 41 3)8
Σ
+
[=]
T-1 Σ
+ 82
CT
G + Ce 2
E
B -
00

---

Published in Transactions on Machine Learning Research (06/2025)
Let us define G, == mL, Gt: with G₁ == [St
Σ
We have that:
Σ E S 4np ((1 B)²
3)² + e(B
E + E
[ 1
+ STGG,
(114)
Applying the upper bound of in completes the proof.
Lemma B.7 (Cheng al. (2024) ) Under Assumption 4.2 if nn S 1. the following holds for all 2
24'
E [f()'] S [
11m 24
E
[| >11² |1|
13m &
(115)
24
Proof. Since f is L-smooth, we have:
L
11-1) f(0') S +(00)) -0000001110-)
0³ - 10-211
(116)
2
Inp²
-(00-1)- 1 10- (V5(0'11) 1, v f((0011)
--
- 11
|| 1
(117)
Since -f n using Young's
i incquality and imposing n, - 24 we further have:
1(0') - ((0) |
J ( +
(118)
Li (|]1((~))11) + 1 11)
$ 1(00-1)- - 11
24 | 1)1
137
|V]((t-1)
(119)
24
0
Proof of Theorem 4.11
(Convergence rate of GHBM for non-convex functions)
Under Assumptions
4.1
4.2 and 4.4 if we take:
SIJLA
1 B
m O,
8 min
1 min
(120)
0²T
244.
V8L
L.A B
JL S min
1, BNLVFT' V
VBS
S3|
then GHBM with optimal
+ converges as:
LA
LAo2
Σ E
(121)
T
|
Proof. Combining the results of Lemmas
B.4 and
B.7
we have that:
T
T
131 T
[f(0] -E [f((0=)]]
11
Σ E.
(122)
24
24
1=1
T
1 [f(0--1-11)
<
26
Eo
Σ
E
|| 113]
+ +28
T+
(123)
77
303
15
|
t=1
T
448
+
(m. 63
(124)
5
[=1
31

---

Published in Transactions on Machine Learning Research (06/2025)
Imposing == c. by Corollary 4.8 we have that 7 0 and S = S vt. Also, noticing that m. 0 implies & < 2T. (I(0") )r) 2TA,, we have that:
T
LA
E
(NJLL))TG, + o²
V
2
+
(125)
T
nLT
ST
|S|J
LA
2LA
+m.JLB) TG+ + + 0²
+
+
(126)
T
3T
|S|J
LA
2LA
LA
TG, o²
+
B
(127)
T
3T
BOGGT
|8|J
LA
LA
(128)
T
BT
S
LA
L.Q22
24
+
(129)
T
|S|JT
where the fourth incquality follows from applying the upper bound n S v
LA BrG,T on the third term of
Eq.
126).
Experimental Setting
C.1 Datasets and Models
Cifar-10/100. We consider CIFAR-10 10 and CIFAR-100 to experiment with image classification tasks, each one respectively having 10 and 100 classes. For all methods, training images are preprocessed by applying random crops, followed by random horizontal flips. Both training and test images are finally normalized according to their mcan and standard deviation. As the main model for experimentation, we used a model similar to LENET-5 as proposed in (Hsu al. 2020). To further validate our findings, we also employed RESNET-20 20 described in (He et | 2015). following the implementation provided in (Idelbayev 2021 Since batch normalization Toffe & Szegedy (2015) layers have been shown to hamper performance in learning from decentralized data with skewed label distribution (Hsieh et al. 2020), we replaced them with group normalization (Wu & He 2018), using two groups in each layer. For a fair comparison, we used the same modified network also in centralized training. We report the result of centralized training for reference in Table as per the hyperparameters, we use 64 for the batch size, 0.01 and 0.1 for the learning rate respectively for the LENET and the RESNET-20 and 0.9 for momentum. We trained both models on both datasets for 150 epochs using a cosine annealing learning rate scheduler.
Shakespeare. The Shakespeare language model- ing dataset is created by collating the collective works of William Shakespeare and originally comprises 715 clients, with each client denoting speaking role. However, for this study, a different approach was used, adopting the LEAF (Caldas et al. 2019) frame- work split the dataset among 100 devices and restrict the number of data points per device 2000. The non-IID dataset is formed by assigning each device to a specific role, and the local dataset for each device contains the sentences from that role. Conversely, the IID dataset is created by randomly distributing sentences from all roles across the de- vices.
Table Test accuracy (%) of centralized train- ing over datasets and models used. Results are reported in term of mean top-1 accuracy over the last 10 epochs, averaged over 5 independent runs.
DATASET
Acc. CENTRALIZED (%)
CIFAR- 10 W/ LENET
86.48 20 22
CIFAR- 10 W/ RESNET-20
89.05 20.44
CIFAR- 100 W/ LENET
57.00 10.09
CIFAR- 100 W/ RESNET-20
62.21 20.85
SHAKESPEARE
52.00 22.00 10
STACKÖVERFLOW
28.50 +0.25
GL.vv2
71.03
For this task, we have employed a two-layer Long Short- Memory (LSTM) classifier, consisting of 100
hidden units and an 8-dimensional embedding layer. Our objective is predict the next character in a
sequence, where there are total of 80 possible character classes. The model takes in a sequence of 80
32

---

Published in Transactions on Machine Learning Research (06/2025)
characters as imput, and for each character, it learns an 8-dimensional representation. The final output of the model is single character prediction for each training example, achieved through the use of 2 LSTM layers and a densely-connected layer followed by a softmax. This model architecture is the same used by (Li et al. 2020
Acar et al. 2021
We report the result of centralized training for reference in Table 5 we train for 75 epochs with constant learning rate, using as hyperparameters 100 for the batch size, for the learning rate, 0.0001 for the weight decay and no momentum.
StackOverflow. The Stack Overflow dataset is a language modcling corpus that comprises questions and answers from the popular Q&A website, StackOverflow. Initially, the dataset consists of 342477 unique users but for, practical reasons, we limit our analysis to a subset of 40k users. Our goal is perform the next-word prediction on these text sequences. To achieve this, we utilize Recurrent Neural Network (RNN) that first learns 96-dimensional representation for each word in sentence and then processes them through a single LSTM layer with a hidden dimension of 670. Finally, the model generates predictions using a densely connected softmax output layer. The model and the preprocessing steps are the same as in (Reddi et al.) 2021). We report the result of centralized training for reference in Table 5 as per the hyperparameters, we use 16 for the batch size, 10-1/2 for the learning rate and no momentum or weight decay. We train for 50 epochs with a constant learning rate. Given the size of the test datasct, testing is conducted on a subset of them made by 10000 randomly chosen lest. examples, selected at the beginming of training.
Large-scale Real-world Datascts. As largo-scale real-world datasets for our experimentation, we follow Hsu al. (2020). GLDv2 is composed of zs 164k images belonging z 2000 classes, realistically split among 1262 clients. INATURALIST is composed of as 120k images belonging to z 1200 classes, split among 9275 clients. These datasets are challenging to train not only because of their inherent complexity (size of images, mumber of classes) but also because usually at each round very small portion of clients is selected. In particular, for GLDv2 we sample 10 clients per round, while for INATURALIST we experiment with different. participation rates, sampling 10, 50, or 100 clients per round. In the main paper, we choose to report the participation rate instead of the number of sampled clients to better highlight that the tested scenarios are closer to a cross-device setting, which is the most challenging for algorithms based on client participation, like SCAFFOLD and ours. As per the model, for both datasets,
MobileNet V2 pretrained ImageNet.
Details on the Experiment. in Fig. 7 In the main text (see Sec. 4.3) we provide an experiment to illustrate the couvergence rate of GHBM (see Fig. 77 The learning problem consists in a linear regression of the coefficients (a, b, c) E R of a quadratic function f(x) ax² + dxr + The synthetic dataset is made of 6400 observations of the above function (with 10, b 5, c 1) in the range x E 1-10, 10). The datasel is split among K- = 50 clients each one having 128 samples, and non-iidness is simulated by splitting the domain into equally big disjoint subsets, and having each client the observation of that domain.
Table 6: Details about datasets' split used for our experiments
CIFAR-10
CIFAR-100
SHAKESPEARE
STACKOVERFLOW
GLDv2
INATURALIST
Clients
100
100
100
40.000
1262
9275
Number of clients per round
10
10
50
10
(10, 50, 100}
Number of classes
10
100
80
10004
2028
1203
Avg, examples per client
500
500
2000
428
130
13
Number of local steps
27
13
Average part participation iou (round no.)
1.5
{5, {5,27, 54]
C.2 Simulating Heterogeneity
For CIPAR-10/100 we simulate arbitrary heterogencity by splitting the total datascts according to Dirichlet distribution with concentration parameter a, following Hsu et al. (2020). In practice, we draw a multinomial q: (ap(ap) from a Dirichlet distribution, where describes a prior class distribution over N classes, and a controls the heterogeneity among all clients: the greater a the more homogencous the clients' data distributions will be. After drawing the class distributions qe, for every client i, we sample training examples for each class according to do without replacement.
33

---

Published in Transactions on Machine Learning Research (06/2025)
search grid for each combination of method and dataset (for a = 0). The best values are indicated in bold.
Table 7:
METHoN
HPARAM
ChPAR-10/100
SHAKBSPEARE
STACKOVERFFLOW
LaNET
REsNeT-20
Ata. FL
wd
[0.001, 0.0008, 0.000
[0.0001, 0.00001
[0, 0.0001, 0.00001] 100
[0. 0,0001, 0.00001]
64
61
16
[2, 1.5, 1, U.5, 0.1] [0.1, 0.05, 0.01, 0.005)
[1.5. 0.1] [L. 0.5. 0.1, 0.01]
[1.5, 1, 0.5, 0.]]
[1.5, 1, 0.5. 0.1 1. 0.5. 0.3, 0.1
FEDAvG
[L.5, 1, 0.5, 0.1
[2, 1.5, 1. D.5, 0.1) [0.11 0.05, 0.01, 0.005)
[1.5. 0.1]
[1.5, 1, 0.5. 0.1]
[1.5, 1, 0.5. 0.1
FEDPROX
0.5, 0.1. 0.01]
[L.5, 1, 0.5, 0.1]
I. 0.5. 0.3, 0.1)
[1. 0.1, 0.01, 0.001"
[1. 0.1, 0.01, 0.001]
[o.1, 0.01, 0.001, 0.0001, 0.00001]
[o.1. 0.01, 0.001, 0.0001]
[1.5, 0.3, 0.1]
[1.5, 0.1]
[1.3, 1, 0.5. 0.1]
[1.5, 1. 0.5. 0.1
SCAFFOLD
[0.11 0.05, 0.01, 0.005)
(o.5. 0.1, 0.01)
[L.5, 1, 0.5, 0.1]
1. 0.5. 0.3, 0.1)
[1.5. 0.5, 0.1
[1.5. 0.1]
[L.5, 1. 0.5, 0.1
[1.5, 1. 0.5. 0.1
FEDDYN
[0.1, 0.05, 0.01, 0.005)
[0.1, 0.01, 8.005]
[1.5, 1, 0.5. 0.1]
1, 0.5, 0.3, 0.1)
[0.1, 0.01, 0.001, 0.0001)
1..1. 0.01, 0.001. 0.0011
(0.1. 0.009, 0.001]
[0.1. 0.009, 0.001]
[1.5. n.5, 0.1)
[1.5, 1, 0.5, 0.1)
[L.5, 1, 0.5. 0.1]
[1.5, 1, 0.5. 0.1]
ADABIST
[0.1, 0.05, 0.01, 0.005)
[0.1. 0.05, 0.01, 0.005]
[1.5, 1, 0.5. 0.1]
0.5. 0.3, 0.1)
[0.1. 0.01, 0.001, 0.0001]
0..1 0.01, 0.001, 0.0001]
[0.1. 0.009, 0.001]
0..1, 0.009, 0,001]
[2. 1.5, 1, n.5, 0.1)
[2. 1.5, 1. 0.1]
[L.5, 1. 0.5, 0.1]
[1.5, 1. 0.5. 0.1
MIME
10.1, 0.05, 0.01, 0.005)
0.5. 0.1, 0.01)
[1.5, 1, 0.5. 0.1]
1. 0.5, 0.3, 0.1)
1. 0.5, 0.1. 0.05, 6.01]
[I. 0.1. 0.05]
[1, 0.5, 0.1]
[1.5, 1, 0.5. 0.1
FEDAVGM
0..5. 0.1. 0.05, 0.01. 0.005]
[L. 0.5, 0.1. 0.01]
[L5,, 1, 0.5. 0.1]
0.5, 0.3, 0.1
[0.99, 0.9, 0.85, 0.8)
0.999, 0.9, 0,85, 0.8)
(0.99, 0.9, 0.85]
[0.99, 0.9, 0.85
1. 0.5, 0.1, 0.05, 0.01]
[1. 0.1, 0.05]
[o.5, 0.1, 0.05)
[L.5, 1, 0.5. 0.1
FEDACG
00.5. 0.1. 0.05, 0.01, 0.005]
1..5. 0.1, 0.01
[1.5, 1, 0.5, 0.1
0.5, 0.3, 0.1)
[0.99, 0.9, 0.85
(0.99, 0.9, 0.85]
(0.90, 0.9. 0.85]
[0.99, 0,9. 0.85
10.1, 0.01, 0.001]
[0.1, 0.01, 0.001]
10.1, 0.01, 0,001, 0.0001, 0.00001]
j0.1. 0.01, 0.001, 0.0001]
[1. 0.5, 0.1, 0.05]
11.5, 0.5. 0.3, 0.1, 0.06)
[1, 0.5, 0.1, 0.08)
[1.5, 1, 0.5, 0.1] [1. 0.5, 0.3. 0.1, 0.05)
MiMeMoss
10.1, 0.05, 0.01, 0.005)
[o.5. 0.1, 0.05, 0.63, 0,01, 0.006)
[L55, 1, 0.5. 0.1]
(0.99, 0.95, 0.9, 0.85, 0.8]
[0.99, 0.85, 0.9, 0.85, 0.8)
0.99, 0.9. 0.85
[0.99, 0.9. 0.85]
0.5, 0.1, 0.05] [0.11 0.05, 0.01, 0.00s)
[1.5,
0.3, 0.1]
[1. 0.5, 0.1, 0.05)
[1.5, 1, 0.5. 0d] [1. 0.5, 0.3, 0.1, 0.05)
MimeLvrMMo
0..1. 0.05, n.0S, 0,01, 0.005]
[L.5, 1, 0.5. 0.1]
[0.99, 0.9, 0.85, 0.8]
[0.99, 0,95, 0.9, 0,85, 0.8)
0.99, 0.9, 0.85
[0.99, 0.9, 0.85]
I. 0.5, 0.1, 0.05)
[1.5, 1, 0.5, 0.1)
I. 0.5, 0.1, 0.05)
FEDCM
[1. 0.5. 0.1, 0.05
0.5. 0.1, 0.5]
[L.5, 1, 0.5. 0.1]
(0.05, 0.1, 0.5]
(0.05, 0.1, 0.5)
10.05, 0.1, 0.5]
[1. 0.5, 0.1
[1. 0.1]
11. 0.5, 0.1]
[a. 0.5, 0.1|
GHBM (ours)
10.1, 0.05, 0.01)
(0.1, 0.01]
[1. 0.5. 0.1]
1. n.5, 0.3, 0.1] [0.9]
[0.9]
[0.9)
[0.9]
[s, 10, 20, 4n)
1s, 10, 20, 40
[s, 10, 20, 40]
[s. 10, 20, 40]
[1. 0.5, 0.1
[1. 0.1]
[1, 0.5, 0.1]
[R. n.5. 0.1
(odlIBM(ours))
1, 0.05, 0.01)
jo.1, 0.01]
11, 0.5, 0.1
[.. 0.5, 0.3, 0.1)
[1. 0.99, 0.9)
[1. 0.99, 0.9)
0.99, 0.9
[1. 0.99, 0.9]
C.3 Evaluating Communication and Computational Cost
In the main paper showed comparison in commmnccttin and computational cost of state-of-art FL algorithms compared to our solutions GHBM and FEDHBM: in this section we detail how those results in table Tab. g have been obtained. We follow a three-step procedure:
1. For each algorithm a, we calculate the minimum number of rounds тa to reach the performance of FEDAVG, the total amount of bytes exchanged b, in the whole training budget (number of rounds, as described in Appendix C.3) and the measure the corresponding total training time t.. In this way, the different requirements in communication and computation of each algorithm are taken into account for the next steps.
2.
We calculate the actual communication and computational requirements as (tb, b2 Sa. tt, Sa), where s, It is the speedup of the algorithm w.r.t. FEDAVG. For those competitor algorithms that did not reach the target performance (e.g. MIMEMOM) in the training budget T, conservatively consider Fa = T. In this way, the convergence speed of each algorithm is taken into account for determining the actual amount of computation needed.
3. We complement the above information with with a reduction /increase factor w.r.t. FEDAVG, calculated as rlbe
tb, TopanAvo
and rila (1
Ha Hy
and expressed as a percentage. A cost reduction
34

---

Published in Transactions on Machine Learning Research (06/2025)
(i.e. rtb, > 0 or rtte > 0) is indicated with 4, while cost increase (i.e. rtb < 0 or rtt <0 is indicated with 1. This gives a practical indication of how much communication communicatio/ccompttaaii /computation have been saved in choosing the algorithm at hand as an alternative for FEDAVG.
C.4 Hyperparameters
For ease of consultation, report the seper-parameters grids as well the chosen values in Table 7 For GLDv2 and ANTURALIIT only test the best SOTA algorithms: FEDAVG and FEDAVGM baselines, SCAFFOLD and MIMEMOM.
MobileNet For all algorithms we perform E' = 5 local epochs, and searched E {0.1, and m E {0.01, 0.1}, and found rj 0.1, n = 0.1 works best for FEDAVGM, while 7 = 1, m = 0.1 works best for the others. For INATORALIST, we had to enlarge the grid for SCAFFOLD and MIMEMOM: for both we searched 7 E (10-3/2 3/2 10-1 10/2,01 11 and y E (10 10 3/2 111 10-1/.0
16. For all algorithms we perform E 5 local epochs, and searched 17 E {0.1,1} and m E {0.03, 0.01} following (Steiner al. 2022), and found 17 0.1, 1p 0.03 works best for FEDAvGM, while 1, 0.03 works best for the others.
C.5 Implementation Details
We implemented all the tested algorithms and training procedures in single codebase, using PYTORCH 1.10 framework, compiled with CUDA 10.2. The federated learning setup is simulated by using a single node equipped with 11 Intel(R) Core(TM) i7-6850K CPUs and 4 NVIDIA GeForce GTX 1070 GPUs. For the large-scale experiments we used the computing capabilities offered by LEONARDO cluster of CINECA-HPC, employing nodes equipped with I CPU Intel(R) Xeon 8358 32 core, 2,6 GHz CPUs and 4 NVIDIA A100 SXM6 64GB (VRAM) GPUs. The simulation always runs in a sequential manner (on a single GPU) the parallel client training and the following aggregation by the central server.
Practicality Experiments. Under the above conditions, a single FEDAVG experiment on CIFAR-100 takes 02:05 hours (CNN, with T 20.000) and 03:36 hours (RESNET-20, with T 10.000). For SCAFFOLD always the "option II" of their algorithm (Karimireddy et al. 2020) to calculate the client controls, incurring almost overhead in our simulations. We found that using "option I" usually degrades both final model quality and requires almost double the training time, due to the additional borward+backward passes. Conversely, all MIME's methods incur a significant overhead due to the additional round nooded to calculate the full-batch gradients, taking = 10:40 hours for CIFAR-100 with RESNET-20. On SHAKESPEARE and STECKOVERFLOW, FEDAVG takes Rs 22 minutes and A 3.5 hours to run respectively T 250 and T 1500 rounds.
C.6 Additional Experiments
Experiments on Cifar-10 Table S reports the results of experiments analogous to the ones presented in Tab. 2 For the main paper, we report experiments on CIFAR-100, as it is a more complex dataset and often a more reli- able testing ground for FL algorithms. Indeed, sometimes algorithms perform well on CIFAR- 10 but worse on CIFAR-100 (as for the already discussed case of FEDDYN). Results in Tab. g confirm the findings the main paper: under extreme heterogeneity, some algorithms behave inconsistently across CNN and RESNET-20 (notice that FEDDYN and MIMELITEMOM only with CNN improve FED AvG. Conversely, Lo- CALGHBM and FEDHBM both consistently improve the statc-of-art by a large margin.
Table 8: Test accuracy (%) comparison of SOTA FL algorithms a controlled setting. Best result is in bold, second best is underlined.
CIFAR- (ReaNer-20)
CIFAR-10 10 (CNN)
METHOD
NON-IID
HID
NON-IID
HDD
FED
61.0
86.4
66.1 20.3
83. #0.3
FEDPROX
61.0
86.7 40.2
66.1 10.3
83. 10.3
SCAFFOLD
71.8 #1.
86.8
74.8 20.2
82.9 #0.2
FEDDyN
60.2
87.0
70.9
83.5 10.1
ADABEST
73.6
80.7
66.1
83.1 +0.4
MIME
53.7
86.7
75.1
83.1 +0.2
AVGM
66.0 42.2
87.7 2003
67.6 :00.3
83.6 83.6.20.
FEDCM
65.2 =3.2
87.1 +0.3
69.0 20.3
83.4 #0.3
FEDA DC:ADD()
65.7 13.0
87.1 1:0.2
66.1 10.33
83.4 10.3
MIMEMOM
69.2
88.0 10..1
80.9 10.4
83.1 10.2
MIMELITEMOM
57.0=0.9
88.0
78.8
83.2 #0.3
LocaIGHBM (ours)
80.6
88.8 20.
81.1 81.1 11.0
FedHBM (ours)
83.4 40.3
89.2 40.1
81.7 4.01
83.8 #0.1
35


Reviews:
[{"review_id": "kAQeZvUxlP", "reviewer": "Reviewer_1iVb", "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. The introduction of GHBM is conceptually straightforward and builds upon existing momentum-based methods, making it relatively easy to implement.\n\n2. Theoretical analysis provides some insights into why classical momentum fails under partial participation and how GHBM mitigates this issue.\n\n3. Extensive experiments are conducted on vision (CIFAR-10/100, GLDv2, INaturalist) and NLP (Shakespeare, StackOverflow) tasks, covering both controlled and real-world FL scenarios.\n\n\n**Weaknesses:**\n\n1. The core idea of GHBM is overly simplistic—essentially just applying a moving average over multiple past gradients, which is a well-known technique in optimization. It is unclear whether this warrants a standalone contribution.\n\n2. The paper lacks comparisons with recent advances, such as [1], which also focus on momentum and communication efficiency in federated learning.\n\n3. The claim that FedHBM is communication-efficient is questionable:\n\n   - Compared to FedAvgM (server momentum), FedHBM does not provide significant communication savings, as FedAvgM already avoids sending extra momentum information.\n\n   - FedHBM requires clients to store past model states, which may be impractical in scenarios where client devices have limited memory (e.g., mobile or edge devices).\n\n\n[1] Communication-Efficient Federated Learning with Accelerated Client Gradient. CVPR 2024", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 Generalized Heavy-Ball Momentum (GHBM), a variant of momentum designed for Federated Learning (FL) to mitigate the effects of statistical heterogeneity and partial client participation. The key idea is to compute the momentum term by averaging past updates over multiple rounds, rather than relying solely on the most recent gradient information. The authors provide a theoretical analysis demonstrating that GHBM converges under arbitrary heterogeneity, particularly in cyclic partial participation settings. Additionally, they introduce FedHBM, a communication-efficient variant that retains the momentum benefits while maintaining the same communication complexity as FedAvg. Experimental results suggest that GHBM and FedHBM outperform existing FL algorithms, particularly in scenarios with extreme non-IID data and low client participation.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "1. The paper should compare against more recent methods, especially those that target both momentum and communication efficiency, such as Communication-Efficient Federated Learning with Accelerated Client Gradient [1], to ensure a fair baseline comparison.\n\n2. The authors should clarify that FedHBM’s communication advantage is only relative to FedCM (client momentum) and does not provide meaningful gains over FedAvgM (server momentum). The authors should also discuss the trade-off of requiring clients to store past model states, which could be a practical limitation in real FL deployments.", "broader_impact_concerns": "The paper does not raise significant ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "kog9GexFpZ", "reviewer": "Reviewer_5YNc", "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- The proposed generalization of Heavy-Ball Momentum (GHBM) introduces a novel and interesting approach with potential applications beyond federated learning. The convergence of GHBM is analyzed under relatively mild assumptions, with the exception of the cyclic participation assumption.\n\n- The paper is well-structured and clearly presented, making it easier to understand the proposed method and its theoretical foundations.\n\n- The experimental study is extensive, covering a range of practical federated learning benchmarks and providing strong empirical evidence for the method’s efficacy. This is a significant strength compared to many purely theoretical contributions in the field.\n\n## Weaknesses\n\n1. Table 8 indicates that, for many method-problem pairs, several hyperparameters appear to be \"undertuned,\" as the highlighted (bold) best-performing values are often at the boundary of the search grid. This raises concerns about the fairness of comparisons and the reliability of the reported results.\n\n2. The choice of \"final model quality,\" measured over the last 100 rounds of training, is questionable. Full convergence curves would provide a more comprehensive understanding of training dynamics and ensure that the chosen metric accurately represents overall performance.\n\n3. The approach to controlling heterogeneity using a parametrized Dirichlet distribution might limit the generalization of results, as it accounts only for label heterogeneity. This makes results for different values of $\\alpha$ difficult to compare meaningfully.\n\n4. > \"The BGD assumption (4.3) is not necessary, as the two terms on the left-hand side (LHS) of the above inequality are the same by definition.\"\n\nThis sentence is ambiguous. Does this imply that one can show the right-hand side (RHS) of the inequality is effectively zero without relying on the BGD assumption, or is the assumption still required for the proof?\n\n More generally, illustrating this effect from a purely distributed SGD perspective would be insightful. If I understand correctly, results such as Lemma 4.7 stem primarily from the sampling strategy rather than the use of momentum. Is this interpretation correct?\n\n5. The condition on $\\eta_l$ in Equation (120) requires the local step size to decrease proportionally to the number of local steps. This hinders the benefits of performing local updates, unlike methods such as ProxSkip or SPPM. How does Theorem 4.11 compare to standard distributed (mini-batch) SGD in this regard?\n\n### Minor\n\n- The discussion of related work, particularly Mishchenko et al. (2022), lacks sufficient detail. Since their method is stateless and supports partial participation, further clarification of the differences would help contextualize the contribution.\n\n- The presentation could be improved by providing a simplified explanation or illustration of core concepts, such as cyclic participation.\n\n- There is an incorrect reference to Karimireddy et al. (2020) at the beginning of page 2.", "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 federated optimization in cross-silo (finite-sum) settings, particularly focusing on scenarios with a large number of clients where methods relying on control variates (such as SCAFFOLD) struggle or are impractical. To this end, the authors propose a novel Generalized Heavy-Ball Momentum (GHBM) approach, which, when combined with local steps, results in a new federated optimization method. The paper provides a theoretical analysis of GHBM under a cyclic partial participation assumption, demonstrating its convergence irrespective of data heterogeneity. The work then introduces practical modifications to GHBM, along with extensive experimental results on several federated learning benchmarks, highlighting the benefits of the proposed approach.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Critical Changes\n\n- The hyperparameter tuning in Table 8 appears insufficient, as many best-performing values are at the edge of the search grid. A more thorough tuning process or justification for the current choices is needed to ensure fair comparisons.  \n\n- The choice of measuring \"final model quality\" over the last 100 rounds of training is questionable. Full convergence curves should be provided to better illustrate the training dynamics and justify this metric.  \n\n- The convergence rate table (Table 1) does not include a heterogeneity bound for GHBM, which might create the misleading impression that it does not provide convergence advantages. This should be addressed.  \n\n- The term \"uniform sampling\" needs to be explicitly defined. Does it refer to independent/Poisson sampling of clients, or mini-batch sampling with or without replacement?  \n\n- The condition on $\\eta_l$ in Equation (120) requires decreasing the local step size proportionally to the number of local steps. This hinders the benefits of local updates compared to methods like ProxSkip/SPPM. The authors should clarify how Theorem 4.11 compares to standard distributed (mini-batch) SGD.  \n\n- The concept of cyclic participation should be explained in more detail. Are schemes like Random Reshuffling or Shuffle-once considered instances of cyclic participation? The assumptions and implications need clarification.  \n\n### Recommended Improvements\n\n- Figure 1 appears to be unreferenced in the text. Additionally, it lacks details about the experimental setup, such as which method is used and what the heterogeneity notation $k$ refers to.  \n\n- The experiments presented in Figure 2 lack setup details, making it difficult to interpret the results. A clear description should be added. Similarly, for Table 8, explicit information on the tuning process should be provided.  \n\n- The meaning of \"compressed updates\" after the reference to (Das et al., 2022) on page 3 is unclear. The authors should specify what type of compression is being referred to.  \n\n- A brief review of the benefits of momentum in the centralized setting would be useful for context.  \n\n- The inequality in Corollary 4.8 appears to be missing an expectation on the left-hand side. This should be checked and corrected if necessary.  \n\n- The term $g^{t_\\tau}$ in Lemma 4.10 is not defined. It should be explicitly introduced to improve readability.  \n\n- The paper should clarify whether the communication cost model considers only client-to-server communication or a bidirectional model.  \n\n- The authors should discuss the compatibility of the proposed methods with FedOpt and adaptive local optimizers.  \n\n- The statement that the work \"has not been published in peer-reviewed venues\" seems unnecessary. Many influential federated learning papers remain unpublished on arXiv. The authors should either remove this comment or clarify its intent.", "broader_impact_concerns": "No concerns for this kind of work", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "aJtUgbDkMf", "reviewer": "Reviewer_SJ4g", "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- The paper is overall very well written. \n- The prior momentum-based federated learning paper (Cheng et al. 2024) proposed Fed-M and Scaffold-M, where the former only supports full client participation and the latter requires additional communication for control variates. This paper makes significant progress by effectively combining partial client participation and momentum without relying on control variates.\n- The proposed method preserves the unbounded data heterogeneity property of momentum techniques.\n\nWeaknesses:\n- The partial participation scheme analyzed in the paper is limited to cyclic participation, which is an idealized scenario and may not reflect practical federated learning setups.\n- The partial participation ratio $C$ should be explicitly defined. Additionally, the impact of $C$ and $\\tau$ on the convergence results should be discussed in more depth. In its current form, Theorem 4.11 suggests that the convergence rate is independent of $C$ and $\\tau$, which requires clarification or further justification.", "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 submission introduces a novel momentum-based method named GHBM for federated learning that addresses data heterogeneity and partial client participation. GHBM ensures convergence under unbounded heterogeneity, and its communication-efficient variant, FedHBM, matches FedAvg's communication cost while retaining momentum benefits. Theoretical guarantees and extensive experiments demonstrate GHBM's superior performance, faster convergence, and robustness compared to SOTA methods, offering new insights into momentum's role in federated learning.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weakness above.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers give positive final recommendations (two leaning accept and one accept). After author response and revision, all major concerns raised by the reviewers have been properly addressed, including the metric of communication (as well as arguments around reduced communication), comparing with additional existing works, heterogeneity simulation, and clarification questions. Therefore, I recommend accept as is (after fixing some minor presentation issues throughout the paper, examples listed below).

Some example possible changes: 
* assumption x -> Assumption x
* eq. (x) -> Eq. (x)
* make the uppercase/lowercase of the first characters of section/paragraph headers consistent
* Kim et al. (2024) uses -> Kim et al. (2024) use
Decision: Accept (poster)