On the Data Heterogeneity in Adaptive Federated Learning
Authors: Yujia Wang
Jinghui Chen
Venue: Accepted by TMLR ()

Abstract: Adaptive federated learning, which benefits from the characteristic of both adaptive optimizer and federated training paradigm, has recently gained lots of attention. Despite achieving outstanding performances on tasks with heavy-tail stochastic gradient noise distributions, adaptive federated learning also suffers from the same data heterogeneity issue as standard federated learning: heterogeneous data distribution across the clients can largely deteriorate the convergence of adaptive federated learning. In this paper, we propose a novel adaptive federated learning framework with local gossip averaging to address this issue. Particularly, we introduce a client re-sampling mechanism and peer-to-peer gossip communications between local clients to mitigate the data heterogeneity without requiring additional gradient computation costs. We theoretically prove the fast convergence for our proposed method under non-convex stochastic settings and empirically demonstrate its superior performances over vanilla adaptive federated learning with client sampling. Moreover, we extend our framework to a communication-efficient variant, in which clients are divided into disjoint clusters determined by their connectivity or communication capabilities. We exclusively perform local gossip averaging within these clusters, leading to an enhancement in network communication efficiency for our proposed method.

Published in Transactions on Machine Learning Research (08/2024)
On the Data Heterogeneity in Adaptive Federated Learning
Yujia Wang
yju5427@ppuu.cmm edu
College of Information Sciences and Technology Pennsylvania State University
Jinghui Chen
jac5917@psu edu
College of Information Sciences and Technology Pennsylvania State University
Reviewed on OpenReview: https: // openreview. net/ formf id= hw 4BE
Abstract
Adaptive federated learning, which benefits from the characteristic of both adaptive op- timizer and federated training paradigm, has recently gained lots of attention. Despite achieving outstanding performances on tasks with heavy-tail stochastic gradient noise dis- tributions, adaptive federated learning also suffers from the same data heterogeneity issue as standard federated learning: heterogencous data distribution across the clients can largely deteriorate the convergence of adaptive federated learning. In this paper, we propose a novel adaptive federated learning framework with local gossip averaging to address this issuc. Particularly, we introduce client ro-sampling mechanism and peer-to-peer gossip communications between local clients to mitigate the data heterogeneity without requiring additional gradient computation costs. We theoretically prove the fast convergence for our proposed method under non-convex stochastic settings and empirically demonstrate its perior performances over vanilla adaptive federated learning with client sampling. Morcover, we extend our framework lo a into disjoint clusters determined by their connectivity or communication capabilities. We exclusively perform local gossip averaging within these clusters, leading to an enhancement in network communication efficiency for our proposed method.
variant, in which clients are divided
1 Introduction
Federated learning (FL) |MMMahan et al. 2017) has gained tons of attraction recently with the development of edge computing and edge devices such as IoT devices and smartphones, It enables clients to collaboratively learn machine learning model by iteratively synchronizing with the central server without sharing their local
private data. Standard SGD-based federated learning methods such as FedAvg (MeMahan et al. 2017 work by aggregating the local-updated models via stochastic gradient descent. Recently, as the demand for training large-scale models such as BERT (Devlin et al.) 2018), GPT-3 [Brown et al. 2020), and ViT (Dosovitskiy et al. 2021). adaptive optimizations such as Adam (Kingma & Ba 2014) and AMSGrad (Reddi et al. 2018)
show their efficiency compared to stochastic gradient descent. (SGD). ). This led the development of adaptive foderated learning mothods such as Fed (Reddi et al., 2020 and FedAMS (Wang al. 2022b) which take the advantage of efficient iterative synchronization and stable adaptive optimization methods.
Despite achieving superior model training performances tasks with heavy-tail stochastic gradient noise distributions, adaptive federated learning still suffers from the same data heterogencity issuc as standard SGD-based lederated learning. Specifically, the stotistical helerogeneily of data distribution across clients can lead to overfitting issues of local models and degradation of global model convergence for adaptive federated lcarning. This data heterogeneity issuc becomes noticeable, especially in practical cases where clients are not able to participate each local training iteration due system heterogeneity such as computational capabilities. Despite that various attempts have been made in solving the data heterogeneity issue for

---

Published in Transactions on Machine Learning Research (08/2024)
standard federated learning (Karimiredyy et al., 2020b Khanduri et al. 2021), few studies are tackling this issue in adaptive federated learning, especially for partial participation case where only selected clients have participated in each round of the training process.
In this work, we aim to develop a novel federated learning framework, Adaptive Federated learning with local Gossip A veraging (AFGA), that addresses the challenges of statistical heterogeneity in the adaptive federated learning setting. AFGA introduces a client re-sampling strategy and peer-to-peer gossip communication between clients during local training steps to reduce the dissimilarity between local models, thus tackling the data heterogeneity issue. Note that AFGA does not incur extra communication between the central server and the sampled clients, and it also does not result in extra local gradient computations. Our contributions can be summarized as follows:
We propose novel adaptive federated optimization method, which benefits from both the client re- sampling strategy and decentralized gossip averaging, to mitigate the impact of data heterogeneity in adaptive federated optimization methods.
We thcoretically provide convergence guarantees of our proposed method in the stochastic non- convex settings with data heterogeneity under partial client participation cases. Specifically, we prove that our proposed method can achieve faster convergence rate than FedAMSGrad (Wang ct al. 2022b) in partial participation scttings.
Moreover, we also extend our framework to communication-effiiine variant, CAFGA, where clients are divided into disjoint clusters and the local gossip commuications are only performed within the clusters, thus leading to an overall efficient communication network. We demonstrate that CAFGA can achieve comparable performance and final accuracy to AFGA while simultaneously enhancing overall communication efficiency.
Extensive experiments on several benchmark datasets demonstrate the proposed AFGA and CAFGA achieving outstanding performance with heterogeneous data in low client participation ratios.
2 Related Work
Federated learning. Federated learning (Končný et al. 2016) play a critical role in collaboratively
training models at edge devices with potential privacy protections. Basic optimization methods for federated learning include SGD-based global optimizer, e.g., FedAvg (McMahan et al. 2017) (a.k.a. Local SGD (Stich
2018) and its variants (Li et al. 2019a Yang et al.] (021), adaptive gradient optimization based global optimizer such as FedAdam, FedAdagrad, Fed (Reddi al.) 2020), FedAGM (Tong et al. 2020 and FedAMS (Wang et al. (022b)). While these optinization methods for federated learning show their ability achieving stable results when data are beterogeneously distributed, they rarely study data heterogeneity itself. Recently, several works address the data heterogencity issue through several aspects. For example, FedProx {Li et al. 2020a adds proximate term to align the local model with the global one, and FedDyn (Acar et al. 2021 involves dynamic regularization term for local and global model consistency. FedNova (Wang et al. 2020b) proposes a normalized averaging mechanism that reduces objective inconsistency with heterogencous data. Morcover, several works study to climinate the client drift caused by data heterogeneity from the aspect of variance reduction such as Karimireddy et. al. 2020b(a); Khanduri al. 22021); p Cutkosky
& Orabona (0019). They introduce additional control variables to track and correct the local model shift during local training, but they require extra communication costs for synchronizing these control variables. Besides, FedDC (Gao et al. 2022 involves both dynamic regularization terms and local drift variables for model correction.
Recent studies extend the decentralized training paradigm to federated learning with various adaption. For example, Guo et al. (2021) considered heterogeneous communications for modern communication networks that improve communication efficiency, and hierarchical federated learning algorithms (Liu et al. 2020 Abad
et al. 2020 Castiglia et al.) 2020) develop frameworks by aggregating client models to edge servers first before synchronizing them to the central server.
DDue to space limitations, we leave the detailed related work for decentralized learning Appendix.
2

---

Published in Transactions on Machine Learning Research (08/2024)
3 Proposed Method
3.1 Preliminaries
In federated learning, we aim to minimize the following objective through N local clients:
1 Σ [(()) - N Σ Li, min f(x) = N #ER4
1
(1)
==1
where æ denotes the model parameters, d denotes the dimension of model parameters æ, fi(z) = Ji Er) is the local loss function corresponding to client i and let D, denotes the local data dis- tribution associated with client i. In this work, we focus on the non-convex optimization problem with heterogeneous data distributions, i.e,, fi are non-convex and the local data distribution D, are non-ii.d. dis- tributed among clients. FedAvg (McMahan et al. 2017) is a basic optimization algorithm to solve equation with the sequential implementation of local SGD updates and global averaging.
Adaptive federated optimizations. Adaptive federated learning is proposed to incorporate adaptive optimization methods (such as Adam (Kingma & Ba, 2014) and AMSGrad (Reddi et al. 2018)) to global
optimizer by replacing the global averaging step in FedAvg. Reddi et al. (2020) summarizes several adaptive
federated learning algorithms, and Jin et al. (2022) proposed FedDA, a momentum decoupling adaptive
optimization method from the perspective of the dynamics of ODEs. FAFED (Wu et al., 2022 also studied
adaptive federated learning but in the context of full participation. FedAMSGrad (Tong et al., 2020 Wang
et al. 2022b) considers local SGD updates and global AMSGrad (Reddi et al., 2018) update on the central server. Specifically, at global round r E [R], the server broadcasts the model æ, to selected clients in the set S,.. The selected client conducts I steps of local SGD updales with local learning rate y and oblains the local model o Then for the selected client i, it obtains a model difference A o 2, and sends to the server. The server aggregates A then updates the global model 24+1 by taking A, as pseudo gradient for calculating momentum m, and variance U, for AMSGrad optimizer, and performs one step AMSGrad update with global learning rate i.e.,
m. 61 m- (1-311)Ar Vr -20 (2)
m.
0, max faxx(0,110 0,- 1r}, x,+1 3r + 17 Vū, +E
(2)
the server finally obtains model x by global round r. It's worth mentioning that if the set of selected clients S, contains all clients, i.e., |8,1 N, it is known as full participation without client sampling, and if |S,] = .M < N, we denote it partial participation or with client sampling.
Heterogeneous and inconsistency. Previous works show that FedAvg suffers from convergence degra- dation when data is non-i.i.d. distributed on local clients (Karimireddy et al. 2020b a Wang et al.) (020b). Several works on adaptive federated lcarning (Reddi et al. 2020; Wang et al. 2022b empirically demon- strate that. the unbalanced data distributtion across clients may lead to worse performance, which implies these adaptive federated methods, unfortunately, do not escape from the convergence degradation as well, Theoretically, it has been shown that when the local data are heterogeneously distributed among clients, FedAMS/ FedAMS/FedAMER /eddAMGra (Wang et al.) 2022b) under partial participation setting is proved with convergence rate D(VI/VRM. w.r.t. global communication rounds R, local update iterations I and the number of participated clients M which has a certain gap between the desired rate O(I/VRIM). Although several works apply variance reduction techniques to show their ability to reduce the effect of data heterogencity in federated learning (Karimireddy et al., 2020a b), they are less compatible with the global adaptive opti- mizer. This motivates us to develop a now framework for mitigating the model inconsistency caused by data heterogeneity in adaptive federated learning.
3.2 AFGA: Adaptive Federated Learning with Local Gossip Averaging
To reduce the inconsistency between local models and achieve a better convergence rate under heterogeneous data in partial participation settings, we proposed a novel Adaptive Federated Learning with Local Gossip
3

---

Published in Transactions on Machine Learning Research (08/2024)
Averaging (AFGA) method with peer-to-peer gossip communication and client ro-sampling framework. The peer-to-peer gossip communication implies that clients are able to communicate their local model without help from the server. Suppose there are in total N clients, we study the same objective function as other adaptive federated learning methods with a similar global framework but a different local updating process.
Algorithm AFGA:
Adaptive Foderated Learning with Local Gossip Averaging
Input: initial point æ1, local step size yn and global step size 7,, optimizer hyperparameter $1, e, doubly stochastic mixing matrix W
mg 0, vo for == to R do
Randomly sample subset of clients S, for collecting local updates in round r
4:
Clients Init: clients in S, receive 2, from the server and broadcast to all clients with local communi- cations
5: for f= 0 do
Randomly re-sample a subset of clients Sr, for gradient computation for each client i E [N] in parallel do if E Sr then Compute gi. = (F
8:
9:
10:
ot ox ng. else
11:
12: a x
13: end if
14:
Gossip: F,,,-1 (W)):(WWsarr)
15: end for
16: end for
17: Clients i E S, send A प I, to the server
18:
Aggregate model updates: A, = [&, Eiss, 4
19:
m, - + (1 A
20:
e, 320,-1 (1-32)44 A2)
21:
6, = max max(ū,-1, v.) and V, = diag(t; (7r +c)
22: Server update Ir+1 xr + 1) V vo,te
m.
23: end for
If we take a deeper look at the local update steps (Lines 5-16), the major difference between AFGA and FedAMMS/FeAAMSCral the re-sample step (Tine 5) and the gossip communication step (Line 14), which we will discuss in detail in the following.
Client re-sampling. Note that for each global training round, have already sampled subset of participating clients S,. Normally (e.g., in FedAMS FedAMM/FedAMMGGA (MSSGGad)) this will be the fixed chosen subset of clients who actually performs local gradient computations throughout this global training round. Yet for AFGA, we perform client re-sampling at each local iteration to obtain a new subset Sr and only the selected clients in the subset. Sp,, are active for gradient computation in that local iteration, while the other clients will stay idle. Note that such a design does not incur extra local gradient computations as the size of S,, is the same as S,.
Gossip communications. After finishing the local gradient computations and model update with respect to the selected subset of clients, AFGA introduces gossip communication step that allow each client to communicate their model weights with their connected neighbors (the selected subset of clients are connected in a graph G with a corresponding mixing matrix W). This gossip communication step conducted by all local clients despite being selected Sr or not. While in practice, clients are not required to know the whole mixing matrix W. Instead, client only needs maintain the weights corresponding those it receives from other clients.
4

---

Published in Transactions on Machine Learning Research (08/2024)
It's important to note that AFGA does not necessitate the sampling of every client in specific rounds iterations. In practical cases, if a client is unavailable, then it would not be sampled during local steps. Tf we remove the re-sampling step by setting S,, = St and remove the gossip communication step by setting x F1,4+1 " AFGA will reduce to standard FedAMSGrad algorithm.
Remark 3.1. Our AFGA algorithm benefits from both gossip communications and client re-sampling while preserving the stable behavior of adaptive gradient methods. The steps of re-sampling in each local iteration help reduce the impact of data heterogeneity. It. allows more clients to be included and participate in local training, which results in training global model with a more balanced data distribution than without re- sampling. The peer-to-peer gossip communication is inspired by the recent advancement in decentralized optimization (Lian et al.) 2017 Koloskova et al. 2020 Chen et al. 2021b), which has shown the ability to reduce the data heterogencity issucs between clients. By involving gossip communications in adaptive lederated learning, it enables local models to average with their neighbors, thus preventing over-fitting on local data. The frequent re-sampling and gossip communications make AFGA effectively reduce the inconsistency between local clients, thus accelerating the overall convergence especially when the number of local steps increases. AFGA is also crucial to practical scenarios as it is compatible with low client participation ratios and limited local gradient computation capability while addressing the challenge of statistical heterogeneity in adaptive federated methods.
4 Convergence Analysis
In this section, we provide the theoretical convergence analysis of the proposed AFGA method. Before starting with the main theoretical results, let us first state the following assumptions based on stochastic optimization and adaptive gradient methods. For vector x and matrix A, we let || = || and ||A|| = a. and ||Al| represents the spectral norm A. We denote 1 as vector with all elements equal to 1, and as the identity matrix, with appropriate dimension.
Assumption 4.1. Each local objective function is L-smooth, i.e., Væ, y E R [
(V)((), - fi())
< L x y Vi E [N]. This also implies the L-gradient Lipschitz condition, i..,, [V V.(li)l S L|
2
L
y
A Assumption 4.2. The stochastic gradient on each client has bounded local variance, i.e., Vo E IR i [M],
there is [V[ f(x, {) [[ o².
Assumption to 4.2 are standard assumptions in centralized and federated non-convex stochastic opti-
mization problems Kingma & Ba 2014 Li et al. 2019a Yang et al. 2021 Reddi et al. 2020).
Assumption 4.3. Each local objective function fi(x:) has G-bounded stochastic gradient on l2, i.e., for all E, we have | fx Il < [ [N].
Note that Assumption 4.3 is a standard assumption in non-convex adaptive optimization problems for under
centralized and federated learning settings (Kingma & Ba 2014 Reddi et al. 2018 Chen et al. 2020 Reddi
ct al. 2020 Wang et al. 2022a 2024b)
Assumption 4.4. The dissimilarity between client's objective function and the global objective function is bounded, i.c., Vz E Rdd, there is 1 E [VV f=) soz
Assumption 4.4 captures the objective dissimilarity between the local and global objectives. Similar data heterogeneity assumption, which considers the variance between local clients, is common in federated learning
[Reddi et al.
2020 Yang et al.] 2021 Wang et al. 2022b 2024a) and decentralized learning (Lian et al.
2017 Li et al. 2019b Koloskova et al. 2020).
Assumption 4.5 (Spectral gap). For the gossip communications, clients are connected in the graph G, and the corresponding weighting matrix W is a doubly slochastic matrix: W E [0. 1|mXn, W1 = 1, T = 1 and null(I W) span(1). We assume the spectral gap p of matrix W satisfies: there exists p E [0,1) 1) such that ||W n -11 S.P.
Assumption 1.5 highly related to the gossip communication update process and is usually assumed for decentralized learning framework (Koloskova al. 2020 Chen et al. 2021b Guo et al. 2021p. For doubly
5

---

Published in Transactions on Machine Learning Research (08/2024)
- 222 S naturally established and the spectral gap p E [0, 1) describes the connectivity of the clients: a smaller spectral gap indicates denser connectivity between clients. Specifically, p = 0 indicates that all elements in the matrix W are ". and this means that each client would be connected and communicated with other clients in the network with a mixing weight of 1 ". p +1 means the matrix W lends to be elements with either 0 or 1, corresponding lo a graph that nearly disconnected. We assume that there exists p E [0, 1) to satisfy ||W 1W-1111 1|2 S p since our proposed method is contributed by gossip communications between clients. Several works (Lian al.) 2017 Li al. 2019b) alternatively assume the spectral gap p of weighting matrix W the second largest eigenvalue of doubly stochastic matrix W, i.e., p = >,(W),, and this spectral gap holds the same role for revealing the connectivity of the graph.
stochastic matrix W, |W - 1
Theorem 4.6 (Convergence analysis for Algorithm D. Under Assumptions 4.1 if the local learning rute
" = CONVIIMM and n 6(1 (0/0///R)))) RI²), and the network spectral gap satisfies p M+N. of Algorithm satisfy
M
then the iterales
1
E f(xx)))
Af As+ L(o² A + ( + +12(-00)00 ++ )
1 R3/2
(3)
v RIM
I
where Af fo- far Ö()) hides all the absolute constants and problem dependent constonts including P,O,0 I. M,N,G.
Corollary 4.7. Theorem 4.6 suggests that with sufficient amounts of global communication rounds R, i.e., R 2 IM, our proposed method achieves a convergence rate of O( ( This improves the rate O vI
VRM
of adaptive federated optimization methods under partial client participation (Wang et al, 20226), which suggests that AFGA con indeed bring accelerated convergence through local gossip commmuiications..
Remark 4.8. The sufficient amounts of global communication rounds that R 2 IM is a commonly-used condition to obtain the convergence rate in FL (Wang el al., 2022b Yang el al., 2021. This condition is also practical as the algorithm usually converges after sufficient global rounds.
Remark 4.9. The impact of data heterogeneity is reflected in the variance dg within the convergence rate. From equation the variance 0g appears in O VRIM and smaller order terms w.r.t. R, I, and M for AFGA. The partially participated FedAvg in Yang el al. (2021) and adaptive FL models like FedAMS (Wang vI
et al.
2022b) obtain the rate of O VRM ), and the dominant O
VRM term directly relates to the variance
gg. T his demonstrates improvements over partially participated adaptive FL models like FedAMS (Wang
ct al.
2022b).
B contains terms with spectral gap p of the gossip communication network. A larger value of p corresponds to a sparser network, which results in a larger variance term in the convergence rate, indicating that the dissimilarity variance has not been completely eliminated.
Remark 4.10. The second term of the convergence rate in equation
5 Communication-efficienny Clustered-clients AFGA and Further Adaptation
CAFGA. While the frequent gossip communications enhance the overall performance of heterogencous federated learning, it indeed involves extra peer-to-peer communication overhead, which makes our proposed AFGA less efficient in communication especially when clients densely connected. Recent studies (Guo et al. 2021 Yuan et al. 2020) show that clients can be gathered into neighboring clusters based on locations or network capabilities, in which gossip communications are less expensive than communicating with the whole network. A similar idea of dividing clients into clusters has recently been studied in federated learning Guo et al.) 2021 Malinovsky et al., 2022 Long et al. 2022) and receives a lot of attention. Note that under a cluster-clients design, part of the network clients are grouped in a cluster, and clients within the
Thhooeticaal analysis provided the Appendix C
6

---

Published in Transactions on Machine Learning Research (08/2024)
Algorithm 2 CAFGA: Clustered- Adaptive Federated Learning with Local Gossip Averaging
Input: initial point æ1, local step size nn and global step size 7,, optimizer hyperparameter B1, $2, doubly stochastic mixing matrix W
1: my f 0, Vo +-0 0 for r= to R do
for cach cluster E [K] in parallel do
Randomly sample subset S for collecting local updates in round r Init: clients in S. receive 2, from the server and broadcast æt to all local neighbors for t 0, - do
6:
7:
Randomly re-sample a subset of clients S for gradient computation
for each client i V& in parallel do if E S then Compute gh (a
10:
11:
2 = - m.
12:
else
13:
F F. xt end if
14:
15:
Gossip Comm: 27,+1 = (W)x
16:
end for end for
17:
18:
Clients i E S. send A = x - Dr to the server
19: end for
20:
|st| EiEst A Server update follows Lines 19-22, Algorithm
K Aggregate: - 1 EkEjK]
21:
22:
end for
cluster can connected through high-bandwidth peer-to-peer communications, leading to an efficient gossip communication network and a relatively smaller spectral gap. This leverages the communication efficiency for applying gossip communications while maintaining comparable performance for our proposed AFGA.
Suppose there are still in total N clients, study the same objective Eq. equation [ but we partition the clients into K disjoint clusters where each of them has n clients (N = Kn)
3 We denote Vy as the set of
local clients in cluster k, k E [K] and denote the neighbors for client i E V/ as Ni. Similar to Algorithm [ we denote the weighted matrix of gossip averaging as We, and the corresponding spectral gap Pa- We then refer Pmax as the maximum spectral gap among all clusters to represent the overall density in the network.
Algorithm 2 summarizes the proposed Clustered-clients paradigm AFGA (CAFGA). At the beginning of global round r, the server sample total M clients (for convenience, uniformly sampled clients in each cluster) for global synchronization. The update rule inside each cluster follows the similar local update rule as Algorithm [ with clients re-sampling and gossip communications in each local iteration, all clusters perform the training process parallelly. To be specific, al the 1-th local iteration in cluster k; clients in the re-sampled subset S are active for gradient computation, while the unselcted clients stay idle. All clients in cluster i then perform a gossip communication step with mixing matrix W.. The leftover global update process of the clustered-client framework the same Algorithm and FedAMS.
We also provide complete theoretical convergence analysis for the Clustered-clients paradigm of AFGA (CAFGA); due to space limits, we referred interested readers to Appendix D for more details. In a nutshell, our icaa analysis suggests that the convergence of CAFGA is related to Pmax which aligns with the convergence rate of Algorithm 1 and implies that more densely connected gossip communications can help reduce the impact of data heterogeneity. Empirically we observe that under the same gossip communica- tion structure (e.g., ring topology), the clustered-clentt paradigm obtains performance improvement since
We omit the clustering process the algorithm for simplicity. The algorithm compatible with various clustering methods, including clustering based on locations and network conditions, clustering based on client similarities, and random clustering.
7

---

Published in Transactions on Machine Learning Research (08/2024)
grouping the whole network into disjoint clusters making the local clients more densely connected thus have smaller p values. The clustered-clients paradigm enables efficient and dense connections for adequate model averaging, which keeps the benefits of further mitigating the effects of data heterogeneity.
Communictiion-adapeed reduce the communccttio frequency. Despite AFGA achieves a faster convergence rate, one noticeable drawback that it requires all clients to stay online to conduct frequent gossip averaging, even if some of the clients do not participate in local training (gradient computation). We want to emphasize that this design is mainly for the case of theoretical analysis. In practice, we can avoid this issue by enforcing gossip communications only on selected clients in each round As shown in the next Scction, such a communicttion-adape compared to the original AFGA algorithm without requiring dense gossip communications for all clients. Also, note that this communication adapttd can also be applied here to CAFGA for further improving communication efficiency while achieving similar model performanccs.
AFGA actually enjoys similar model training performances
6 Experiments
Datascts and models. We conduct experiments on CIFAR-10 (Krizhevsky et al., 2009), CIFAR-100 (Krizhevsky et al.] 2009) and Shakespeare (Caldas et al., 2018) dataset with various data sampling levels and client participation settings. We evaluate experiments on non-ii.d. data distributions by Dirichlet distribution partitioned strategy with parameter = 0.6 similar to Waag et al. (2020a For image clas- sification tasks on CIFAR-10 and CIFAR-100 datasets, we adopt a ConvMixer-228 256-8 network (Trockman & Kolter 2022), which shares similar ideas to vision transformer (Dosovitskiy et al.) 2021) to use patch embeddings to preserve locality and similarly, and is trained via adaptive gradient methods by default. For the next-character prediction task on Shakospeare, we adopt a 2-layer LSTM network, with 80-dimensional word embedding and 256 hidden units per layer, and follow dropout layer with dropout rale 0.05.
Baselines and methods. We compare our method with several federated learning and adaptive feder- ated learning baselines including FedAvg (McMahan et al., 2017). FedAdam (Reddi et al. 2020 FS et al. 2022b SCAFFOLD KKrimireedy et al. 2020b) FedProx (Li et al. 2020b and FedDyn
(Acar et al. 2021
Implementation overview. The number of local training iterations I on each client is set to 24 for ex- periments on CIFAR-10 and CIFAR-100 datasets, and I = 100 for experiments on the Shakespeare dataset, and the batch size is set to 50 for all experiments by default. We report 500 rounds (denoted as #R or # Rounds in tables and figures) for the CIFAR 10 and the Shakespeare datasets and 600 rounds for the CIFAR-100 dataset. For each dataset and setting, the number of local training iterations I and the total rounds of training #R are fixed across all baseline methods to ensure fair comparison. For local update, we use the SGD optimizer with a learning rate from {0.1, 1} for SGD-based global optimization methods (FedArg, SCAFFOLD, FedProx, and FedDyn), and use SGD optimizer with a lcarning rate from {1,2,10} for adaptive global optimization methods. For fair comparison, the local SGD updates apply no momentum and no gradient clipping steps for all methods. We set the global learning rate as for SGD-based global update, and set the global learning rate 0.01 for global adaptive optimization, FodAdam, FedAMSGrad, and our proposed AFGA. See Appendix B for more details about the experimental setup including datasets, models, and hyperparameter details.
6.1 Main Results
We summarize the performance of our proposed methods and other federated learning baselines in Table 1
Table 3. Due to space limits, we leave the lcarning curves and most ablation studies in Appendix B Our experiments based on two settings, Setting 1: 100 clients with 5% participation ratio and Setting 2: 50 clients with 10% participation ratio. For the Clustered-clients AGFA (CAFGA), we evenly partition clients into clusters for both scttings, i.c., for Setting 1: there are 20 clients in each cluster with participate
Forr example, suppose we train AFGA with ring topology and select M out of N clients to participate in each round. We can form new ring topology over the M sclected clients and only ask them to communicate over the new ring topology. In this way, the gossip communications only include these active clients while other unselected clients do not need to stay online and participate in the training process.
8 Fed MSGrad is one of the variants of the FedAMS algorithm introduced in Wang al. 2022b
8

---

Published in Transactions on Machine Learning Research (08/2024)
Table 1:
The test accuracy of different methods on CTFAR-10 datasets. Setting 100 clients, 5% partici- pation. Setting 2: clients, 10% participation. We report the average and the standard derivation over runs with different random seeds.
Setting 1
Setting 2
Method
Acc. & std
R# (78%)
Acc.& std
R# (78%)
FodAvg
75.57 1.10
313
76.85 1.69
180
FedAdam
77.07 0.05
425
78.46 = 0.19
157
FedAMSGrad
77.53 = 0.60
388
79.59 = 0.76
154
SCAFFOLD
76.94 + 1.17
273
76.46 + 3.95
146
FedProx
75.63 + 1.24
500+
76.91 = 1.39
180
FedDyn
77.68 + 0.06
297
78.55 + 0.36
160
AFGA
78.45 + 0.58
302
80.02 + 2.00
152
CAFGA
79.18 + 1.02
233
82.10 + 0.67
112
Table 2: The test accuracy of different methods on CIFAR-100 datasets. Setting 1: 100 clients, 5%
participation. Setting 2: 50 clients, 10% participation. We report the average and the standard derivation over runs with different random seeds.
Setting
Setting 2
Method
Acc. & std
R# (52%)
Acc.& std
R# (52%)
FodAvg
49.88 0.33
600+
51.21 0.23
600+
FedAdam
50.40 0.53
600+
51.99 = 0.81
375
FedAMSGrad
50.58 + 0.99
600+
52.15 = 0.58
278
SCAFFOLD
51.71 + 0.21
396
55.12 + 1.01
235
FedProx
49.75 + 0.13
600+
51.28 = 0.10
600+
FedDyn
49.93 + 0.22
396
51.93 + 0.52
600+
AFGA
52.08 0.17
436
53.87 + 0.68
369
CAFGA
53.08 + 0.72
380
54.41 = 0.24
230
ratio 5%, and for Setting 2: there are 10 clients in each cluster with participate ratio 10%. We set ring topology as the default gossip communicaion topology.
Results on CIFAR-10 and CIFAR-100. Table D and Table show the overall performance on training CIFAR-10 and CIFAR-100 datasets with Conv model. We observe that AFGA shows improve- ment upon other baselines, and the proposed CAFGA achieves better performance than AFGA.
For Setting 1 on CIFAR-10, based on the results on three random seeds, AFGA shows average 1.5% improvement in accuracy compared to SCAFFOLD, nearly 0.8% improvement compared to FedDyn, and nearly 1% improvement compared to FedAMSGrad, The proposed CAFGA, our extension on clustered- clients setting, further improves 0.7% accuracy based over AFGA. For Setting 2 on CIFAR-10, CAFGA demonstrated around 3.5% incrcase accuracy over FedDyn and 2% incrcase over FedAMSGrad. Note that in both settings, AFGA and CAFGA show their superior performance in achieving desired test accuracy. This demonstrates our proposed AFGA and CAFGA achieve overall better performance than adaptive federated learning methods and other federated learning basclines in both settings.
Table 2 shows that in experiments on CIFAR-100, for Setting 1, AFGA and CAPGA obtain higher test accuracy among other baselines including SCAFFOLD and FedDyn. Specifically, CAFGA significantly outperforms all basclines with more than 1.3% increase over SCAFFOLD and more than 2% increase over FedAdam and FedAMSGrad. For Setting 2, our proposed AFGA and CAFGA still outperform other federated learning baselines expect for SCAFFOLD.

---

Published in Transactions on Machine Learning Research (08/2024)
Table 3: The test accuracy of different methods on Shakespeare datasets. Setting 100 clients, 5%
participation. Setting 2: 50 clients, 10% participation. We report the average and the standard derivation over runs with different random seeds.
Setting 1
Setting 2
Method
Acc.
(52%)
Acc.
R# (52%)
FodAvg
48.66 0.01
500+
49.59 0.56
500+
Adam
52.35 + 0.10
391
52.23 + 0.08
189
FedAMSGrad
52.09 = 0.23
239
51.96 + 0.06
220
SCAFFOLD
51.39 = 0.02
500+
52.76 = 0.06
166
FedProx
48.55 + 0.01
252
49.33 = 0.48
229
FodDyn
51.87 + 0.03
500+
50.81 - 0.08
500+
AFGA
53.08 + 0.08
121
53.13 = 0.04
108
CAFGA
53.20 + 0.05
152
53.57 + 0.02
91
Results Shakespeare. Table shows the overall performance of training the Shakespeare dataset with 2-layee LSTM network. For Setting 1 on Shakespeare, AFGA shows approximately 2.5% improvement in accuracy compared to SCAFFOLD, and 0.5% improvement compared to FedAMSGrad. The proposed CAFGA achieves even higher final accuracy than AFGA and siguificantly outperforms other baselines. For Setting 2 on Shakespeare, AFGA addresses increasing in accuracy over FedAMSGrad, while CAFGA outperforms AFGA final results. In both settings, AFGA or CAFGA show their superior performance achieving desired test accuracy.
6.2 Ablation Studies
Sensitivity of gossip averaging and client re-sampling. We conduct experiments studying how the individual components, gossip averaging and re-sampling, and the clustered-clients framework contribute to the proposed AFGA and CAFGA. Table g presents the ablation study of the contribution of individual components, which indicates that the gossip averaging and client re-sampling simultaneously contribute to the accuracy improvements of AFGA. Furthermore, by the results from Table (also with the observation of the learning curves in Appendix B). it shows that the clustered-clients paradigm further improves overall accuracy. These results show our intuition of utilizing gossip averaging and client ro-sampling can effectively mitigate data heterogeneity, and also address the benefit of the clustered-client framework that consistently helps improve the performance. In addition to the aforementioned ablation studies, we have also conducted further ablation studies to investigate the effect of data heterogeneity, examine different gossip averaging topologies to understand the impact of the spectral gap on model performance, and explore the effects of varying the number local iterations. Due to constraints on space, we provide detailed ablation studies and results in Appendix.
Table 4: Ablation of components at the last 5 rounds (in total 500 rounds) in training CIFAR-10 on ConvMixer-2564 model.
Methods (FedAMSGrad)
Acc.
FedAMSGrad Only
79.59 + 0.76
Gossip
77.39 + 0.01
Gossip + Re-sampling (AFGA)
80.02 + 2.00
Gossip + Re-sampling + Clustered (CAFGA)
82.10 + 0.67
Ablation of gossip averaging topology. We also conduct ablation studics on how the gossip averaging topology affects the overall performance in AFAA Figure shows the ablation study on (a) spectral gap in AFGA and (b) clusters' maximum spectral gap p for 5 clusters in CAFGA.
10

---

Published in Transactions on Machine Learning Research (08/2024)
0.00
Plo =0
+3453
Pro 00.35
= +3.55
Accuracy
Towe Lnde.
Pro 0.755
Prax 0.573
Tost Accuracy
0.70
0.335
3.55
#Hoourds
0Ho un
#ounds
# Hounds
AFGA
(b) CAFGA
Figure 1: Ablation study with different heterogeneity degree of (C)AFGA in training CTFAR-10 on ConvMixer-2564 model.
We follow the Setting 2 in Table 1 i.c., 50 clients with a participation ratio of 0.1. For AFGA, we compare various of p from p {0, 0.455, 0.995} calculated by balanced fully-connected, random, and ring typologies correspondingly. We observe that the balanced fully-conmected topology with p = 0 contributes to faster convergence, which aligns with the theoretical result that smaller p can help reduce the impact of data heterogeneity. Similar to CAFGA, we compare various of Pmax from Puax = {0, 0.335, 0.766, 0.873) calculated by balanced fully-connected, unbalanced fully-comecctdd random, and ring typologies correspondingly It shows that the fully-connected topology (relatively small Puax value) results in faster convergence as well.
A Alatioo on data heterogeneity.
We further conduct experiments to investigate the impact of data
10
0.0
Training Loss
2.0.3
Tost
10
18-1
055
0.5.66
01
#Rounds
Rounds
(a) ARGA
(b) CAFGA
Figure 2: Ablation study with different helerogeneity degree of AFGA and CAPGA in training CIFAR-10 on ConvMixer 256-8 model.
heterogeneity as theoretically the proposed (C)AFGA show that the convergence rate is highly related to the model dissimilarity. We use Dirichlet(a) distribution for data partitioned in experiments, where represents the degree of heterogeneity (smaller a implics more heterogencous data distribution), and we choose from {0.3, 0.6} together with the i.i.d. data partitioned setting for ablation study. The rest of the experimental setup is the same as Setting 2 in Table 1 Figure 2 shows the learning curves for different non-i.i.d. degrees. We observe that the data heterogeneity across clients still significantly affects the convergence and gencralization performance for our proposed (C)AFGA, as a more balanced data distribution attains faster convergence and higher accuracy.
6.3 Communication Adapted AFGA and CAFGA
Table 5 shows the test accuracy and the total global round to reach target test accuracy of communication- adapted AFGA and commmication-adaptter CAFGA which have discussed in the previous Section. We can observe that both communication-alapues methods achieve similar test accuracy compared with their original version. This suggests that in practice we can still solve the data heterogeneity issue without requiring all clients to participate in gossip communications, Due to space limitations, we left additional results the CIFAR-100 dataset in Appendix B
6Thhi means that clients the cluster are connected with their neighbors with random weighted averaging elements.
11

---

Published in Transactions on Machine Learning Research (08/2024)
The test accuracy (Acc.) and the total global rounds (R#) to reach 78% test accuracy of different methods when training ConvMixcr-2556 model on CIFAR-10 dataset, where (a) denotes the communccttion adaplive version. Setting 100 clients, 5% participation. Setting 2: 50 clients, 10% participation. Setting 3: 100 clients, 10% participation. Setting 4: 50 clients, 20% participation. To mitigate the effect of randomness and fluctuation of the accuracy, we take the average of the last 5 global rounds to represent final accuracy.
Table 5:
Setting
Setting Acc.
Method
Acc.
R#
R
AFGA AFGA (a)
78.80
302
82.61
152
76.59
419
81.51
259
Setting 3
Setting 4
Method
Acc.
R#
Acc.
R
CAFGA
81.56
142
83.15
69
CAFGA (a)
81.15
194
82.99
136
7 Conclusions and Future Works
In this paper, we propose a novel adaptive federated optimization algorithm, AFGA, that addresses data heterogencity across clients and mitigates local model inconsistency by introducing gossip commuicctionss and client re-sampling during local training steps. We present a completed theoretical convergence analysis for the proposed AFGA. We prove that AFGA achieves a faster convergence rate than the previous adaptive federated optimization method for partial participation scenarios with heterogeneous data under non-convex stochastic settings. We extend AFGA to more communictiion-effiiae clients are divided into disjoint clusters and we only perform local gossip averaging within the clusters. The extended CAFGA algorithm is aimed at reducing the communication overhead introduced by gossip communications while maintaining the benefits of client re-sampling and gossip communications under hel- erogeneous data. Experiments on several benchmarks and ablation studies backup our theory.
clustered-cleents paradigm, where
Despite successfully tackling the data heterogeneity issue among clients by introducing gossip communica- tions and client re-sampling, our current proposed methods also have certain limitations. First, exlending the theoretical analysis to the communication aaaamiicaioon-ddaatedd versions is challenging and highly non-trivial. More- over, gossip communications also incur extra challenges if attempting to further apply secure aggregation schemes to our method. Also if not all clients are trusted and there exist malicions clients, the frequent gossip communications between clients may increase the risks of model poisoning or privacy attacks. We leave those new challenges as future works.
Acknowledgments
We thank the anonymous reviewers for their helpful comments. This work is partially supported by the National Science Foundation under Grant No. 2348541. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
References
Mchdi Salehi Heydar Abad, Emre Ozfatura, Deniz Gunduz, and Ozgur Ercetin. Hierarchical federated learning across heterogeneous cellular networks. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8866-8870. IEFE, 2020.
Durmus Alp Emre Acar, Yue Zhao, Ramon Matas, Matthew Mattina, Paul Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. In International Conference on Learning Representations, 2021. URL http::///ppaaaeeee..eee/////r/ep
12

---

Published in Transactions on Machine Learning Research (08/2024)
Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. 1EEE transactions on informalion theory, 52(6))2508-22555 2530, 2006.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. arXiv preprint ar arX:::2005.14 14166, 2020.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint 1rXiv:1812.010090 2018.
Timothy Castiglia, Anirban Das, and Stacy Patterson. Multi-level local sgd: Distributed sgd for heteroge- neous hierarchical networks. In International Conference on Learning Representations, 2020.
Jinghui Chen, Dongruo Zhou, Yiqi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. Closing the generaliza- tion gap of adaptive gradient methods in training deep neural networks. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2020.
Xiangyi Chen, Belhal Karimi, Weijie Zhao, and Ping Li. On the convergence of decentralized adaptive gradient methods. Xixi preprint or arxiv:2009 09.03194, 2021a.
Yiming Chen, Kun Yuan, Yingya Zhang, Pan Pan, Yinghui Xu, and Wotao Yin. Accelerating gossip sgd with periodic global averaging. In International Conference on Machine Learning, pp. 1791-1802. PMIRR, 2021b.
Ashok Cutkosky and Francesco Orabona. Momentun--ased variance reduction in non-convex sgd. Advances in neural information processing systems, 32, 2019.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding, orXiv preprint arXiv:1810.04500 2018
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Un- terthiner, 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 International Conference on Learning Representations, 2021.
Liang Gao, Huazhu Fu, Li Li, Yingwen Chen, Ming Xu, and Cheng- Zhonng Xu. Fedde: Federated learning with non-iid data via local drift decoupling and correction. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 10112-10121, 2022.
Yuanxiong Guo, Ying Sun, Rui Hu, and Yanmin Gong. Hybrid local sgd for federated learning with hetero- geneous communications. In International Conference on Learning Representations, 2021.
Jiayin Jin, Jiaxiang Ren, Yang Zhou, Lingjuan Lyu, Ji Liu, and Dejing Dou. Accelerated federated learning with decoupled adaptive optimization. In International Conference on Machine Learning, pp. 10298 10322. PMLR, 2022.
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint arXi::2008..083 03606, 2020a.
Sai Pranceth Karimireddy, Satyen Kale, Mchryar Mohri, Sashank Reddi, Scbastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic rolled averaging for federated learning. In International Conference Machine Learning, pp. 5132 5143. PMLR, 2020b.
Prashant Khanduri, Pranay Sharma, Haibo Yang, Mingyi Hong, Jia Liu, Ketan Rajawat, and Pramod Varshncy. Stem: A stochastic two-sided momentum algorithm achieving near-optimal sample and com- munication complexities for federated learning. Advances in Neural Information Processing Systems, 34: 6050-6061, 2021.
13

---

Published in Transactions on Machine Learning Research (08/2024)
Diederik P. Kingma and Jimmy Ba. arXiv:142.66900 2014.
Adam: A method for stochastic optimization. arXiv preprint
Anastasia Koloskova, Nicolas Loizon, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory decentralized sgd with changing topology and local updates. International Conference on Machine Learning, pp. 5381-5393. PMLR, 2020.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprinl orXiv:1610.055 05,92, 2016.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Tian Li, Anit Kunar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, (7(3):50-0)) 60, 2020a.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429-4555 4500, 2020b.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data, Viviv preprint drXic:1907.02189, 2019a.
Xiang Li, Wenhao Yang, Shusen Wang, and Zhihua Zhang, Communication--ffiienn local decentralized sgd methods. Xiv preprint ar Xiv: 091.0009.6.,..... 2019b.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsich, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
Lumin Liu, Jun Zhang, SH Song, and Khaled B Letaief. Client-odge-cloud hicrarchical federated learning. In ICC 2020-2020 IEEE International Conference Communications (ICC), pp. 1 6. IEEE, 2020.
Guodong Long, Ming Xie, Tao Shen, Tianyi Zhou, Xianzhi Wang, and Jing Jiang. Multi-center federated learning: clients clustering for better personalization. World Wide Web, pp. 1-20, 2022.
Yucheng Lu and Christopher De Sa. Optimal complexity in decentralized training, In International Confer- ence Machine Learning, pp. 7111-7123. PMLR, 2021.
Grigory Malinovsky, Kai Yi, and Peter Richtárik. Variance reduced proxskip: Algorithm, theory and appli- cation to federated learning. Xiviv preprint #xXix2207.04333, 2022.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effen efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp. 1273-1282 PMLR, 2017.
Parvin Nazari, Davoud Atace Tarzanagh, and George Michailidis. Dadam: A consensus-based based distributed adaptive gradient method for online optimization. arXiv preprint 1rXix:1901.000 09109, 2019.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXio preprint arXiv:2003.00295, 2020.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.
Sebastian Stich. Local sgd converges fast and commincattss little. arXiv preprint
09767, 2018
Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. d2: Decentralized training over decentralized data. In International Conference on Machine Learning, pp. 4848 4856. PMLRR 2018.
14

---

Published in Transactions on Machine Learning Research (08/2024)
Yunfei Teng, Wenbo Gao, Francois Chalus, Anna E Choromanska, Donald Goldfarb, and Adrian Weller. Leader stochastic gradient descent. for distributed training of deep learning models. Advances in Neural Information Processing Systems, 32, 2019.
Qianqian Tong, Guannan Liang, and Jinbo Bi. Effective federated adaptive gradient methods with non-iid decentralized data, arXiv preprint (rXit:2009006533 2020.
Asher Trockman and Zico Kolter. Patches are all you need? arXiv preprint orXi::2201.097 2022.
John Nikolas Tsitsiklis. Problems in decentralized decision making and computation. Technical report, Massachusetts Inst of Tech Cambridge Lab for Information and Decision Systems, 1984.
Hongyi Wang, Mikhail Yurochkin, Yuckai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni. Federated learning with matched averaging. In International Conference Learning Representations, 2020a. URL
https://openreviiet wtwpeerrriiw..n/forrrrr///ee
Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of local-
update sgd algorithms. Journal of Machine Learning Research, 22(213):1-50, 2021. URL http::/jmmrr
org/papprrs/222/0011 .hmml
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. arXie preprint 2Xkv:2007.07481. 2020b.
Yujia Wang, Lu Lin, and Jinghui Chen. Communication-coppsssd adaptive gradient method for distributed nonconvex optimization. In International Conference on Artificial Intelligence and Statistics, pp. 6292 6320. PMLR, 2022a.
Yujia Wang, Lu Lin, and Jinghui Chen. Commuiccttion-fficintt adaptive federated learning. In Proceedings of the 39th International Conference on Machine Learning, pp. 22802-22022222 -28388. PMLR, 2022b.
Yujia Wang, Yuanpu Cao, Jingcheng Wu, Ruoyu Chen, and Jinghui Chen. Tackling the data heterogencity in asynchronous federated learning with cached update calibration. In The Twelfth International Conference on Learning Representations, 2024a. URL hatpp:://opareviee..eese het//torrmm?dt=44yymmbb1771
Yujia Wang, Shiqiang Wang, Songtao Lu, and Jinghui Chen. Fadas: Towards federated adaptive asyn- chronous optimization. arXiv preprint arXiv:2407.1888 18365, 2024b.
Xidong Wu, Feihu Huang, Zhengmian Hu, and Heng Huang. Faster adaptive federated learning. arXiv preprint arXi::2212.000 009774, 2022.
Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker participation in non-iid federated learning. arXiv preprint arXiv:2101.11203, 2021.
Jinliang Yuan, Mengwei Xu, Xiao Ma, Ao Zhou, Xuanzhe Liu, and Shangguang Wang. Hierarchical federated learning through lan-wan orchestration. arXiv preprint arXiv:2010. 11612, 2020.
Dongruo Zhou, Jinghui Chen, Yuan Cao, Yiqi Tang, Ziyan Yang, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint arXi::1808 05671, 2018.
A Related Work
Federated learning. Federated learning (Knečný et al. 2016) play critical role in collaboratively training models at edge devices with potential privacy protections. Basic optimization methods for federated lcarning include SGD-based global optimizer, e.g., FedAvg (McMahan et al. 2017) (a.k.a. Local SGD (Stich) 2018) and its variants (Li et al. 2019a, Yang et al. 2021), adaptive gradient optimization based global optimizer such as FedAdam, Adagrag FodYogi (Reddi et al., (2020). FedAGM (Tong et al. (0200) and FedAMS- Grad (Wang et al. 2002bpp. While these optimization methods for federated learning show their ability on achieving stable results when data are heterogeneously distributed, they rarely study data heterogeneity
15

---

Published in Transactions on Machine Learning Research (08/2024)
itself. Recently, several works address the data heterogeneity issue through several aspects. For example, FedProx [Li et al.
2020al adds proximate term to align the local model with the global one, and FedDyn (Acar et al., 2021 involves dynamic regularization term for local and global model consistency. FedNova (Wang et al. 2020b) proposes a normalized averaging mechanism that reduces objective inconsistency with
heterogeneous data. Moreover, several works study to eliminate the client drift caused by data heterogeneity from the aspect of variance reduction such as (Karimireddy al. 2020b a Khanduri et al., 2021 Cutkosky
& Orabona 2019 They introduce additional control variables to track and correct the local model shift during local training, but they require extra communication costs for synchronizing these control variables. Besides, FedDC (Gao et al. 2022) involves both dynamic regularization terms and local drift variables for model correction.
Decentralized learning and beyond. Decentralized learning studies a distributed machine learning paradigm without central server. can been tracked back from gossip averaging tochniques (Tsitsiklis. 1984
Boyd et al., 2006). Decentralized (gossip) SGD algorithms (Lian et al.) 2017 Li et al.) 2019b; Boyd
et al. 2006 Tang et 2018) are then proposed that consider client-to-client communications after each step
of SGD update on the client for decentralized learning. Lu & De Sa (2021) proves tight lower bound for decontralized training under the non-convex setting. Teng et al. (2019) proposes a leader-distributed SGD algorithm that pulls workers to the currently west-performing model among all models. There are recent studies generalized various distributed SGD algorithms under unified frameworks, where Wang & Joshi (2021h included reducing communication costs and decentralized training in i.i.d. settings, and Koloskova et al. (2020) studied a general network topology-changing gossip SGD methods that summarize several algorithms in distributed and federated learning.
Recent studies extend the decentralized training paradigm to federated learning with various adaption. For example, Guo et al. (021)) considered heterogeneons communications for modern communication networks
that improve communicttion efficiency, and hierarchical federated learning algorithms (Liu et al.) 2020 Abad
ct al. 2020 Castiglia et al., 2020) develop frameworks by aggrogating client models to edge servers first before synchronizing them to the central server.
B Additional Experiments
In this section, we present additional empirical results for our proposed algorithm AFGA and CAFGA in training ConvMixer- 256-8 model (Trockman & Kolter 2022) on CIFAR-10/100 (Krizhevsky et al. 2009) datasets, and in training LSTM model on Shakespeare (Caldas et al. 2018 dataset. All experiments this paper are conducted on 4 NVIDIA RTX A6000 GPUs.
B.1 Additional Experimental Results
Additional Experimental Results on CIFAR-10. Figure 8 shows the overall test accuracy curves of experiments on CIFAR-10. It demonstrates that our proposed AFGA and CAFGA achieve overall bet- ter performance than adaptive federated learning methods and other federated learning baselines in both settings.
Additional Experimental Results on training ResNet-18 on CIFAR-10. Table presents the empirical result for our proposed AFGA and CAFGA logether with several federated learning baselines on training CIFAR-10 with ResNet-18 model. It shows that the proposed CAFGA outperforms other federated learning baselines, achieving 0.4% improvement over FedAMSGrad and an enhancement of more than 1% compared to other baselines.
Additional Experimental Results on CIFAR-100. BigureAshows the empirical result for our proposed AFGA and CAFGA together with several foderated lcarning basclines on training CIFAR-100 ConvMixer- 256-8 model. They demonstrate that our proposed AFGA and CAFGA achieve overall better performance than adaptive federated learning methods and other federated learning baselines in both settings.
16

---

Published in Transactions on Machine Learning Research (08/2024)
0.85
0.50
0.80
Test Accuracy
lest Accuracy
6./0
Festig Festddmm FosAMSGrod
Fubheg
0.65
Frethdwm
FodAMB5
Fretyyn
0.55
0.50
100
200
309
500
0.60
100
300
400
500
Rnunds
#F Rounds
(a) CIFAR-10 10 100 clients 5%
(b) CIFAR-10 50 clients 10%
Figure The test accuracy for AFGA and CAFGA with several federated learning baselines in training CIFAR-10 data ConvMixer-25668 model.
Table 6: The test accuracy of training ResNet-18 18 model on CIEAR-10 datasets considering 50 clients and 10% participation ratio.
Method
Acc. & std.
FedAvg
70.32 + 0.44
FedAdam
73.80 = 0.58
FedAMSGrad
75.59 + 0.73
SCAFFOLD
74.60 + 0.67
FedProx
70.26 = 0.45
FedDyn
74.15 + 2.23
AFGA
74.72 + 0.32
CAFGA
75.96 0.67
B.1.1 Ablation Studies and Other Comparisons
Ablation of local iteration. We further study how the local ileration affects the convergence of our pro- posed CAFGA algorithm. Figure 0 shows the ablation study about local iterations, we compare the number of local iterations I from I = {12, 24, 48). We observe that larger indeed helps accelerate convergence on training loss and helps to obtain a higher test accuracy. This result backs up our theory that the increasing number of local steps would help the overall performance.
Communication run-time simulations. Table presents a simulation study substitution of the real- world measurement similar to Guo et al. (2021). Consider a limited bandwidth setting where the average time of client-to-client communication cost 1.8 seconds, and the average time of client-to-server communication cost is 18 seconds. Table 7 suggests that even when considering client-to-client communication costs, our proposed AFGA and CAFGA can still efficiently achieve high accuracy with less overall communication costs. This implies that though proposed methods incur extra local gossip communcations, helps mitigate the impact of data heterogencity thus improve the overall performance.
Table 7: The communication time under for CIFAR-10. Setting 1: 100 clients, 5%
participation ratio.
Test Accuracy
70%
75%
78%
80%
FedAMSGrad time (h)
76.0
128.0
194.0
281.0
AFGA time (l)
91.76
130.98
223.48
250.86
CAFGA time (h)
76.22
102.86
172.42
179.82
We have briefly discussed dccentralized learning in the related work the main paper, here we provide more discussion about our proposed methods and the decentralized algorithms. Decentralized learning can certainly prevent single point failure without central
Comparisons to Decentralized Methods.
17

---

Published in Transactions on Machine Learning Research (08/2024)
0.55
0.5
0,50
0.50
Test Accuracy
Test Accuracy
Feskug Teskdam RodM5GGrd
FudAug
Fedkdam
FosAM5Grod
0.30
100
200
300
400
500
600
0.30
100
2.00
300
4.00
500
600
Rounds
Rounds
(a) CIFAR-10U 100 clients
(b) CIFAR-100 50 clients 10%
Figure The test accuracy for AFGA and CAFGA with several federated learning baselines in training CIFAR-100 data ConvMixer-256-8 model.
Test Accuracy
lest Accuracy
0.45
0.45
Festug Feshdam
Fudiug
0.40
TesAbescied
9.40
Scaffold d
Scaffeld
Festrox
Fudifrox
0.35
FedDyn
0.35
Fwiliyn
AFCC
AFGA
CAPGA
CARGA
1.00
200
450
0.50
500
Roundds
# Rounds
(a) Shakespeare 100 clients 5%
(b) Shakespeare 50 clients 10%
Figure 5: The test accuracy for AFGA and CAFGA with several lederated learning baselines in training Shakespeare data on LSTM model.
server, its performance is not par with the conventional server-client FL setup, especially when data are heterogeneous distributed. In sharp contrast, the periodic synchronization between server and clients in our proposed method can help align local models for better convergence and ease the data heterogeneity issue in adaptive fedcrated learning, which is mainly focus of this paper. Morcover, the central server sctting allow us to easily apply adaptive optimizer for stable performances, while decentralized learning methods are mostly limited to SGD-based update the adaptive optimizer needs the alignment of gradient update, otherwise suffers from some divergence issue (Chen
2021a).
We provide some experimental results comparing proposed methods with decentralized algorithms in- cluding DSGD [Tian et al. 2017), DAdam (Nazari et al. 2019 Chen et al. 2021a) and PGA (Chen et al. 2021b) under the same training settings. The following table shows the comparison result for several decen- tralized methods and our proposed AFGA and CAFGA. It shows that our proposed AFGA and CAFGA indeed attains better test accuracy results comparing other decentralized baselines.
Table 8: Comparison to decentralized algorithms.
Mothod
Test Accuracy(%)
Rounds (78%)
DSGD
80.23
50
DAdam
70.37
227
PGA
80.93
210
AFGA
82.16
152
CAFGA
83.03
112
18

---

Published in Transactions on Machine Learning Research (08/2024)
I 12
0.80
107
Training Loss
lest Accuracu
0.75
0.65
10
0.55
2 24
150
200
0.50
500
Rounds
# Rounds
Figure 6: Ablation study with different heterogeneity degree of CAFGA in training CIFAR-10 on ConvMixer- 256-8 model.
B.2 Hyper-pen Hyper-parament parameters Details
Hyper-parameter Settings. We conduct detailed hyper-parameter searches to find the best hyper- parameter for each baseline. We grid over the local learning rate nn E {0.001, 0.01, 0.1, 1.0), and the global learning rate 7 E (0.001, 0.01, 0.1, 1.0, 5.0, 10.0} for each method. For the global AMSGrad optimizer, we set 81 0.9, 31 = 0.99, and we search the best e from {10-10, 10-5, 10-6, 10-1)- Table summarizes
the hyper-parameter details in our experiments.
Experiments are set up with Setting 1: 100 total clients, and Setting 2: 50 total clients in the network. For CAFGA, clients equally divided into 5 clusters. The partial participation ratio set to p 0.05 for Setting 1 and p 0.1 for Setting 2, and the gossip communication topology is ring topology by default. For each method, conduct I = 24 iterations of local training with batch size of 50 by default.
Table 9: param-paramettes details.
Setting (100 clients participation)
FedAvg
FedAAdm
FedAMSGrad
SCAFFOLD
FedProx
FedDyn
AFGA
CAFGA
Data
CIFAR-10
0.1
1.0
1.0
0.01
1.0
1.0
0.1
1.0
0.1
1.0
0.1
1.0
0.01
2.0
0.01
2.0
CIFAR-100
0.1
1.0
1.0
0.01
1.0
0.1
1.0
0.1
1.0
0.1
1.0
0.01
1.0
0.01
1.0
Shakespeare
1.0
1.0
1.0
0.01
1.0
0.1
1.0
1.0
0.1
1.0
0.01
10.0
0.01
10.0
Setting (50 clients 10% participation)
FedAvg
FedAdam
FedAMSGrad
SCAFFOLD
FedProx
FedDyn
AFGA
CAFGA
Model
9
11
CIFAR-10
0.1
1.0
1.0
0.01
1.0
1.0
0.1
1.0
0.1
1.0
0.1
1.0
0.01
2.0
0.01
2.0
CIFAR-100
1.0
1.0
0.01
Shakespeare
1.0
1.0
1.0
0.01
1.0
1.0
0.1
1.0
0.1
1.0
0.1
1.0
0.01
10.0
0.01
10.0
C Preliminaries
About weighted matrix:
mull(1n - W&) sxan E R" (In x 0)
(4)
If we have mull(I, Ws) span (),, that means the following equation holds
Wi1
W12
Win
F1
W22
1 W22
U2n
12
(5)
W.1
Wnn
Zn
19

---

Published in Transactions on Machine Learning Research (08/2024)
if and only if 21 22
Zn- Since we assume wiy [0, 1], there is a counter-cxample if Wa
(W2, 0;O, 0, /n-2), then we have
W11
W112
21
W21
W22
22
0,
(6)
nn-2
En
then (2.,2))..,, = (a1 C2 O,... () + 0) can be solution to the equation.
For the eigenvalues and eigenvectors of matrix W3 (1/n)11², we have
W - (1/n)11" = W -J,
(W& J)(Wx - -J) =W - J.
Ab = (Wx- - -J)b= (Wx - -J)(Wx Jjb (W4 - J]Ab X²b,
(A² л/6 0, == or X =.
(7)
The eigenvectors of W₁ - J are (1,-1,0, 0), (1.0, - ....., O).... (1, 1).
The maximum || W - (1/m)117Tl 112 obtained when W₂ equivalent to Ins and we have max W (1/n)112112 = which implies |[& - (1/m))11 I.
Convergence Analysis for flustered-cliente framework
We re-state two cluster related assumptions, the assumption of inter-client dissimilarity and the assumption of gossip mixing spectral gap, and the theorem in the following. First, we denote the local objective function of cluster k, i.c., f& (xx 1/ Eiev, f((x), then state the following assumptions.
Assumption D.1. The dissimilarity between client's objective function and corresponding cluster's objec- tive function is bounded, i.e. for all æ, k [K], there is 1 Eier [lVf((=) - v fu(=))1 < of Similarly, clusters' objective function the global objective has bounded dissimilarity variance: for a 2 1 and a. O, there is K K <²> +
connected in the graph A Assumption D.2 (Intra-cluster spectral gap). Local clients in cluster k E [K]
GR with weighting matrix Wa satisfies same characteristic Assumption 4.5
We assume the spectral gap
Pv satisfies: there exists Pk E 1) such that [ - 111 ll2 S Pk.
We further denote o7 = 1 Ex= of as the average dissimilarity between local clients in the same cluster, K
and denote Pmax = max Pk as the maximum spectral gap among all K clusters.
Note that Assumption D.1 and Assumption D.2 are general assumptions for the clustered-client AFGA (CAFGA) framework. Specifically, if K 1, i.c., there is only one cluster containing all clients [N] in the network:
Assumption D.I reduces Assumption 4.4 the cluster's objective function in Assumption D.1 is ex-
actly the global objective, thus a. = 0, and there is bounded dissimilarity between client's 's objective and global objective: 1. ErEiN] V [[) og. which is consistent with Assumption 4.4
Assumption D.2 reduces to Assumption
4.5 the only cluster contains all i E [N], clients E NN] are connected the graph with weighting matrix W and there exists p E [0, such that IW 111 1l2 < p, which is consistent with Assumption 4.5
In the following, we state the convergence rate for Algorithm 2 (CAFGA).
Thcorem D.3. Under Assumptions 4.1 4.3 D.1 and D.2. if the local learning rate satisfies specific con- straints, and the marimum spectral gap satisfies Pmax I m
min then the iterates of Algorithm in portial
parlicipation scenarios salisfy
20

---

Published in Transactions on Machine Learning Research (08/2024)
/ =0
1 [/o -
so]
o²
Pinax
G² G² 17 + (1 Pinax
)ofl
(8)
I
R3/2
where O(-) hides all the absobule conslunts and problem dependent conslants including p,o, o of, M, N, and additionally we denote 0² =²² + of oo as the variance summation.
E Proof of Theorem D.3 and Theorem 4.6
Preliminaries for the proof. We define the following auxiliary sequences, w.r.t. Br,t, aha Firstly, we denote the average model on cluster as
at. ni
(9)
r1+1
where Jh:: - t/ Eiev, Fizs where gh. = 0 as a virtual gradient if client in Ve has not been selected in the set St,,, and gr,, is equal to the real gradient Fr. if St, We also define the global average model
1 1r, Fy 1 N
Σ Tee
(10)
We next define sequences related to model differences, we denote the average model difference on cluster k as Ar and the average global model difference A, without sampling consideration.
I-1
I-1
Σ
A
1
Σ
( xx) = IT Er
Fr.t
Cr
- Σ
gr.
TI
1EV2
LEV
t=
1=0
A
Σ kE(K]
x
22)
- = -1I - - gr. Σ kE(K]
(11)
K
71
SEV
t=o RE(K] SEV2
Since we have two sampling process: sampling clients for global communication per global round r, and sampling selected clients for local gradient update per local iteration L. Thus we state the following auxiliary equations
Est (gt,,
Esst
1
Σ
9ir
Σ
gh.
St
71
n
iEV
iest
,r
I-1
I-1
s [A,)] = Rgg.
171
* It.r
=
E
St.
111 Σ
Σ
gind
t=0
t= iESt
K
K
I-1 Σ
Es. [ = Es.
A
1 K k=1
Est
Est
7
Σ
gi.
K
n
k=1
tmo SESt
K
St
Σ
111
E
St
Σ
gi.r
Es, [Ar].
(12)
m
72
KESt
t=0
iESt
Thus A, is the unbiased estimate of A,.
Proof of Theorem D.3. Similar to previous works Zhou et al. 2018
Chen et al. 2020).
introduce
Lyapunov sequence Z, assume 4p 31, for each r 2 1, we have
B (x, xx-1) - B1 2r
31
2, = Fr + 1 31
1 - B1 2.
(13)
21

---

Published in Transactions on Machine Learning Research (08/2024)
For the difference of two adjacent element in sequence 2r, we have
1
B1
2,41 2, =
(I++1 - x,) - 1 11
(r, x1- 1)
B1
1
(1
(.V,1/2m,,))
B1
11 1,,-1 V/.-1?? m
B1
1 B1
1
///--1/2
3,mm-- + (1 -1)),,
B1 V,
1/2
m
1 B1
1 B1
31
V-1/2 V. 1/2
11
m1-11
1 B1
By Assumption 4.1 with the property of L-smoothness, for E [R] taking conditional expectation at global round r, we have
E)f( E((F)(E) 2,+1 - - + _/2 B1llz+41 - 2..1
2
s n
(V[(z,,, p.-1/2,,) >> - 7 ( (V](E.))
31
r-1 - -1,1//
m.- )
1- B1
n²L L
1/-1/2 D
B1
(V.-1/2 1/-1/2) mp-1
2
1- 31
nB
(Zx)), V.-1/2 4,)
n
(()(z))
31
(V/-12
V m
1- B1
11
17 L
1-1122 A,
B1
(D/-1/2
V,-1/2
2
1- 31
r-1
r
m
111
+ n
(V)(x)) - vx(,)), (,-1/2A)
(14)
IV
E.1 Bounding
I
We have
= 7
V fx(r)
V ff(x))
)1
y/
0, +
1
3 gne I
--
Vo, +e Kn
1=0 kE[K]
VEVe
(. 1
gi )
Σ
Σ
Σ
Vo, te Kn
1=0 ke []
iESt,
N gr.
mm
f((x,)
E
e +e N
1=1
177
IE
(xx) 1
V (((att)))
(15)
71.
Ver +e N
22

---

Published in Transactions on Machine Learning Research (08/2024)
where the first equation in equation 15 holds by A, 2h A = - - Σizo g...- The last equation
above holds by the unbiasedness of stochastic gradient, then we have
V f(( x
N 0r +E N Σ
v Filatt)
18
1
f (
1
Σ v
2
U, t N
E
f(x))
1 N
Vf((),))))
+
Σ
K
V v
2
N
K
k=1
V (xxr)
N
Vii(act.)) )
1
2
Vo, + Vo +
N
==1
Vf(x))
1 Σ (i(ttt
1
Σ
K
V Vul )
(16)
V0, + Vr +6
Since we have inequalities, (a.b) = ||a||2 + |bb|2 - ||a bb12 and (a. b) S 2/aaa11+ + +11001 then we have
V f(x))
1 N
E
Vor + N
V f (xx)
2
N
E
+
V [[( (
V0 +e
Vo, + N 1=1
1
11
V ff (xx)
(f(zz)
E
VÜ +e
Ve, +e
v Fa (2 )(²1
+
(E
(Vf(z,)
V0, +e K
Vo, +e
K
km
+
E
V (x²)
+
E
1
1 N
Σ
K
(a
4
+
4
+e E
N
K
i=1
k=1
1
N
-
1 E
K
V f(x,
11
E
V fa (o+t
4C
4Co
4Co
k=1
N
19
K
2
+
1
1
Σ
((r(
+ 4
1
E
1
Σ
N
K
k=1
N
K
17.
+
1
E
f((
1
Σ
v
(17)
AVe
N
K
where the second incquality with Co V2fI²2² + After applying the property of L-smoothness, the last three terms above are highly related to bound the inter-cluster consensus error ||a.- # and intra-cluster consensus error | mfal
+ innuuaaiittttttyt holds by the property of variance 8,. || s [| < 2//2
23

---

Published in Transactions on Machine Learning Research (08/2024)
Thus by Assumption 4.1 we have the following result for bounding I
1
1= nB
V)(z))
1 N
K
17t1 m 4Co n2
V (x,
v
fia (x
K
k=1
N
+ mM
B
1
(a
+
V (ax,)
1
v
AVE
N
K
k=1
fa (a |1}
E
(
K
1 N
K
mI m 4Co
E|| V T.
11
V (
K
k=1
1 K
m
f( =
fi(
1
fi
)
AVE π
K
N
N
22
+ E
V5(x.))
1 Σ
((a((t))))
+
E
Σ
K k=1
K A=
N
K
17
mi m
E|| Vf )1
E
1
V
Σ
V fr (2+t..)
4Co
N
K km
1=1
m
222
E 1|||,,
17| +
2L K
E[[ =| 1:,
4VEn n
K
N
k= 1
+ L K
I K
B||
k
| +
E| B||
* ,,
111
K k=
N
N
K K
M m
E|| x., ||
v fa (xt+
4Co T
k=
+ MM m
3T.22 K
B11
+
31,2
K
E E||
m 112
4/C n
K
N
A=
MI m
V )1)
1
2
K
V (xttt)
N
4C T
1=0
k=
+ M m
31'22 + Pmax H Blll V f(x,)) )1²
+ +z)) + +3322 C1 mn of
4Ve
02 + m(n - m) Io? ].
+ 33L2I"Cnp002 m + +3L'C (I² + H Pmnax)
(18)
n(n 1)
where the last inequality holds by Lemma F.1 and F.2
24

---

Published in Transactions on Machine Learning Research (08/2024)
E.2 Bounding II
Bounding TI mainly follows by the update rule and definition of virtual sequence er,
11 -n ( V.((z))
31 31
(V,-122 V.- 1/2) 1/21 1/2mmmm-1)
mm-1))
- (((z)))
(2(xx) + v.(())),
B1
(V,112 -V.1122
m
1-31
S nB fx 11
B1
(V,-1 V/-1/3)
112) m,-1
1 31
nLB
||
-
B1
(v--1/2
1/2 V- 1/2
m
1- B1
nB
f1
(V,-1/²-
1/2
V/-1/2)
1/2)
m,-1
1-31
LE
1
B1
B1
(V. V.-1/2) m,
+
31
m
1- 31
$1
m
I
E
1/2
17-1/111,
88
m
Lm L G2 1/2
V-1222 1/1
(19)
B1
(1-
B1)2
n²
where the first iequality holds by Assumption 4.1 and the last one holds by Assumption 4.3 and Lemma F.8 about bounding (xxr and m,.
E.3 Bounding III
For bounding ITI, use the similar way for bounding II,
111
L E3
1/2 A.
81
(V. 1/2 V. m,
|]
27
1 1- 31
B1
S LE [||
V. 1/2 Ar 1111 + +1 L
(V.-1/2 17-12)) m,
1 B1
< L "1IA,, (1 3,) n²
87 m²
np
G
LI
1/2 - 1/-1/113
(20)
where the first incquality holds by Canchy-Schwarz incquality, and the second one follows by Assumption
4.3 and Lemma F.S about bounding VI(x,, and m..
E.4
Bounding IV
Similarly, we bound the last term in equation
14
TV TV F V (z(z)) Vf(..), VV 1/)
E (zz)
v((+))]
1/2 //Al||]
< LE
||2,
2,
2
E
81
V.
27
+
L E
V.1 1/2 A, 1
2
B1
2
L
87
1)2
E
m,
112]
+
[1|| 17,
(21)
2c
(1
3
2c
25

---

Published in Transactions on Machine Learning Research (08/2024)
where the first incquality holds due to Young's inequality, and the second one follows from Assumption 4.1 and the definition of virtual sequence z,. By Lemma
F.7
we have
R Σ
R 1.1.%
E m, 1131 S
Σ
EI|
(22)
Therefore, the summation of IV term is bounded by
R
1/2 89
1
R BI||
IV S
+
1|2).
(23)
2e (1 - B1)²
2c
Merging& I to IV together, we obtain the following result for bounding equation
14
[[f(z++1) - f(21)
< 77 m { - -IB[IV Σ
N
11
1 Σ
K
17}
4Co {
E
V
v
(a
+ mM m
3I.2 (I + Pmnxx Ha [
V [x, || + + + II2 IC HI, p1i or
4/C
+ 3L I
Punxx +3L2 ,, (I² + H22 Punx)
_ +
0²2
m(n - m))
n(n 1) Ioi )
n1
+
11 1 31
81
II + +17
m²
Laj 0Z
E B||| 1/2 17-1/21111]
(1-3))
n²
+ 17 L
m
I G2E
1 1/2 V. 1/2 1
(1 31)2 n²
L
L
IL
+
+
+
c
11..
2c (1 B1)
2c
then substituting the bound of ||= in Lemma
F.5
and by applying Lemma F.4 then we have
R
n
- -((1
Y
R
R
I-1
N
<
MiI
B[ll
1/7h
ΣΣ
E
Σ
v v
4Co
4Co
r=1
K
177
E
1
Σ
4Co
K
m
31 (I + Prnce Hr.e) (a (a (a2B[[///////// [[,[l/((xx))11 + +00)
+3LLI2 HJ of
V
0² +
m(n m)
n(n - 1) Iof )
3L'I-Cuni0" pmax + CI" + +H Pi ) +
n
31
87 m
R
+
17
IIG +1² (1-
II G2 1/2
E V 1/2 - 2
B1
$7 m
2 (1- ) n
G2
2
E V 1/2 V. 1/11
26

---

Published in Transactions on Machine Learning Research (08/2024)
12L B
+ L2
L
R
2
0² + 64njI(n - m)
+
+
(0] + o².
2c (1 - -1)
2c
N
n(n - 1)
r=1
(2n(n= m)
GA - m²
+ +4m (I + +1)213)
[Cink HI, max (a +o2)
+
+
m² (n 1)
n(n 1
H7
002
m) m(n -m)
+ ICmI H pPax o7
+ IC P maxx" 0² + ICi
Pmaxx
+ -
n(n - 1) Imp
I
n
64n 1m m)
0²
m(n m))
n(n - 1) Io? |
D'Cn Vf + o..) + Cam
+
nnn-1) 1)
n
16n (m - 1) +
Σ
I-1
N
17
8m I-1
K
E
E
V fa
(24)
(n 1))
K
1=
Rmm
1
we need the certain constraint on local learning rate
16n (m 1)
+ 2(I + 2)nf
1 1771
CB.n
N2 (n
1)
N
4Co
4
(m - 1)
2( + 2)m
+ S 40nC3.n
+
(25)
N2 (n 1)
N2n
where Cp.n = -m²
nZ 83
(1-9)²² + 3nL = ( (n,, 11), we further need the requirement of m, which is same as
the requirement in full participation settings
m111 31.2 Cin Pmaxx Hz,))²² AVC"
22n(n - m)
32n Lz m)
CaamI H HI 2
m2(n (n-1)
n(nn 10-1 1)
32n 1.2(n m) n(n 1)
Mi
8Cu²
31. 3T."ICinn(1 + Pinax Hz,p)a² + 2nnnn - m) Ave
32 L2 ml) nin - 1)
Can ppax max
m 1)
32n I.2(n= - m)) n(n -
" <
(26)
8Co"
V
+ m S
(27)
CI +
P HI )a
thus we have
MII R
SCAR
< Rm
- -
+ M
Σ
31 (I + Praxx Hz, + I2..IICIIP HI.p"R 2-2
4R
o
m(n m) Im?
Bi
MIIG d RVC
CT Pmax + +31.2 (I² + HH
2
P nr
n2
n(n
1)
31
88
LI c2
(12L.
B
1
{
2n7 0² N
+2 2 (1 11)3 n
r th
26 (1 (1-11)²
2e
22n(n= - m)
64n (L' m)
+ 441 (I + +1)212)
[Ciin HI.pp o
+
mn -
n(n 1)
Hz.p
o2
m(n m))
+ I0mn HT.pPP o, + IC Puax 0² + ICinh
T2 Pmax
+
n(n 1) Iop
n2
6,2 (n- m) ntn 1)
0² Ccn Pann 2
(0=
0²
m(n- m)
64 I(n m)
n(n - 1) Im?
[0? + 02)
(28)
n
n(n 1(n-1)
27

---

Published in Transactions on Machine Learning Research (08/2024)
since there is HI.p min Pmmox IJ S I and Pmax I 1,
R
R [ [
80
1=1
(11=++1)---(e - + 4VE
C. II + HI,
1Mhh RIm
+C- -C-L211 PmaxIHI,po + m(n- m)
Iof + o² Pmax (1+ [1+H))] + CgG2 d
RVe +20% m LmmaGaa
n(n - 1)
nL
87
n
{
np
2111 0² +
22n(n - ml)
+ 64 -m)
+ 4n (I + 1)21.2 m(n m) n(n- - Ioi
2c (1 (1-12)2
+
2c
+
N
(n 1)
n(n 1
H7,p
0²
of o² T
Cimpmaax 0² Ciili
-maxx
T
64(n- ml
n(n - 1) CILLIi C,L3T1 +C
q²
m(n m) Iof
+ mof + mo?
(29)
n
n(n - 1)
where C a constant irrelevant to parameters and Pmax maX Pk. HI.p min and 02 = k Σ of This concludes the proof.
1-pmaxx II, C3
1-
If we further apply the constraint of
n(n m)) m² (n 1)
1 n1
HI PP max S
(30)
where the condition Eq. 30 implies that the spectral gap Puax satisfies
Prixx
m
(31)
1 Pmax
n1.2
with the condition of Eq.
31
then we assume there is Pmax <
mtn which satisfies
n(n m) m2 m2(n 1)
n(n m)
P
n(n m)
m
1
H HI.p
(32)
m2(n 1) Pinx
m2(n 1) (m + n n)m
n
28

---

Published in Transactions on Machine Learning Research (08/2024)
Also by choosing constant Č we have
n
B B f |19]
R
n
(z0)
1
CgG Ve
3m dm
$ 8Co
+
+
m/ RIm
R
en
7i
CLL3TL m A
I(I HI.)D + [Ipinxx HI,
n
Io" Iooppmx
+
m(n m) I'09
n
n(n 1)
12
7L
3
CTT
1L
3nL
2 +
10] + +
N
31
n1
(1
31
T4
C2m
nL
8
3
o²
m(n m) HI oz
2
+ oî 0² + H 0
0
(1 - B1)2
I'
n(n 1) I
CaI21nI
nL
B
3nL
(1 B1)²
To
II + HI. 0²² + HI, HI. of + n n
Punax 02 + 0² +
m(n - m
Ioi
n(n 1)
C1 + 112
11
87
3
σ² 0. + of + 0² + HI. I'n
m(n mm) HI
+
+
I 01
(33)
n
(1 B1)
n(n - n(n-1)
By adopting learning rates 17 = (n m
and mp = 0
Vit
1
)
then we have
n
f(20))
CCaPd
203mII.G
Ti
+
+
1/11 RIm
R
Ve
[l + f(20)
CoGPd
LC3LGZdVIm
+
+
v VRIm
R
Ve
eVR
[E [[((Zz+))) - (20) -((
G
+
+ Ö
VRIm
R
R3/2
T-
CL2'M
I(I HI,D) + IPmnntlI,pp
+
n IIo2
n pmxx
+ n(n 1)
m(n m) I I2o? ]
4VE
CL2
I(I + HT.p)o² + [IPhaxHHr,p
+
n n Io²
pa
+ min - 17s) x22 ]
4RT Te
n
n(n2 1)
CI2
(pi Pi + n n 1 2² Pa +
m(n - m)) Io?
(I + Hz,p)o? +
/
nnn
CL2
2Io² ( Piaxxoo
nl +
+ m Io? ]
o² p
4RI fe
=
p2
T,2 T.2 (1 122mxx
)o?)
I
29

---

Published in Transactions on Machine Learning Research (08/2024)
where the incquality holds by the definition of HI.p min { pimpmax" II, and the big-O holds because S
?L
B7
3nL
1
(
L 13
3L
T3 e (1-31)2
0²
0²
e
N
RRmm e (1-31)²
v VRIm
nL
O
d²
=0
o²)
(34)
NVRLm
KVLLm
The simplification of T1 very similar to that T3:
CST 4b Ta
3
=0(1
+
|o to = (VRIm ( + o
(1 31)2
The simplification of the first half of T3 is very similar to that of T3 and T4.
Cmm
7L
3/L
[ -ee + of + +o² + HI I2n + m(n m) HI
o²
T3
+
11
(1 - 31
n(n - 1)
C2
n
B
n
3L
0² + of + t + HI. I2
o²
+
m(n - m) HT. of
/RIm= <(1 (1- - 31)
VRIm
nin 1) I
1 L
37
1
3L
o. of + of + + d²
S C2
Fot
VRIm= (1 (1- -1)2
VRIm
In
L
lo2 + oî + +
=0
VRIm
The simplification of T3 is very similar to that of T3 and T4 well, that
CaL311i
nL B
E (1-3)² + 3rL
Te
n
0011
1
L
lot + oz o2) =
RI
VRIm
R3/2
We bound To Tr together. since we previously have the bound for Top then
n+1 P 0²
o²
m(n - m)
Tg Ty To
(I + H P 0o² + HI o7 +
Pmax
Io
n(n
++ 1
σ²
To
2Io + Io²
0²
+ Io²
n
Ō
R3/2
The simplificatinn of the first half of T3 very similar to that of T3 and TT,
TB = C₁(I + 1) m
87
3nL
m(n - m) HI o?
+
0- + oî + 00 + HI I2n
n2
c (1
31)
c
n(n - 1) I
Ca(I + +1)mm m
MiL
87
3
m(n m) HI. 2
00 +
0, + δ² + H
+
(1-3
31)2
I2
n(n 1)
I
CI(I + 1)
n
L
87
n
3L
0 σ +
2 2
+
||I,
g²
+
m(n m) H -2
RI
VRIm (1
81)2
/RIm
I'm
n(n 1)
I
CI + 11
n L
3
n
3L
0 σ2
+
0²
o
RI2n 1
VRIm e (1
31)2
VRIm
In
=
R3/2
30

---

Published in Transactions on Machine Learning Research (08/2024)
Therefore, merging terms from T1 to T&, equation 33 should be
R
E1 V (2, )1 +
+
T4
+
Tb To +
R
(2] - ((z))
G²
1
Pinax
o
+ 0
12 + (1 + Pinxx ) +
v RIm
R
R
I
+
L
+
oo + o
+ +0
L
0
o
+000
+
(35)
K RIIm
RIm
RRm
R8/2
T3
T5
Ta 17.33
note that N = Kn, re-organizing them, have
R
E [
-0
[So - so] (10 (62+0p 22
+
0²
I.
R
RRIm
K
Munx 0²
+ 0
G² + +2 + (1+ pinax) )op
+
(36)
R
I
R3/2
Based on the theoretical analysis above, we obtain the general convergence bound for (C)AFGA. Here we conclude the proof for Theorem D.3
Note that the proof for AFGA is a special case of the proof for CAFGA. When there is only one cluster containing all clients [N] in the CAFGA framework, it reduces to AFGA. Therefore, for the convergence analysis AFGA, we replace the Assumption D.1 with Assumption 4.4 and replace Assumption D.2 with Assumption
Proof of Theorem 4.0
4.5 This results in m = M,n N,K Pmax = p, G. = and
0g ok oi, and then we have
R Bil V (x
+ + )
= -
[o - f.l+ Lio²
+ )
(37)
VRIM
R3/2
hence we conclude the proof for Thcorem 4.6
F
Supporting Lemmas
Lemma F.1 (Inter-clusted consensus error). For local learning rate which satisfying the condition mi S &IL. denote ===1+ I recall the definition for in Eq. 9 the inter-cluster model difference after s local
steps satisfies
K 2..1 (22
0²
2 <
CT
Blla
o²) +
(38)
K
K
k=1
31

---

Published in Transactions on Machine Learning Research (08/2024)
Proof. Note that the following proof is similar to Lemma 3 in (Reddi et al. sequences, we have
2020 By definition and auxiliary
E||| k ,, - xx,11% = Elllet 21 - -m.g",111))
= EE Tyet 20 m Trit F n
F n
Va (x = "Vii (a(r))))
iESt.
Σ V(((a+ || + + + Mnス
< (1 + *1 - x., 10.111] + ザ3
gr.t
Σ
[ - V vi((at)))))
n
SES
&ESE.
1/ | | - -V.
-4(1+>-1)) Σ (.
-v
m v fa
+4(1+ (1 " 11ll V [x)
0²
n2
< (1+ + +1)1i111** 2., 13
+ 1//
((1 + >'') L BB[1 2x, + 441 +1 "n?2"
Blll ==,,11])
n
7
m(n m)
+4(1+ + )m Ju (z. |1}]
n(n - 1) 4(1 + +, ")
1
+ <11++>> + +4(1 +111+~~ 11 Bll xx 1 4(1 + 1 1,2
Bilaot, - #h,,11
n i=1
m(n m)
+ 4(1 4(1 [
n(n 1) 4(1 - m2
(39)
n
where the first equality holds by Eq. 10 The first inequality holds due to gi is an unbiased estimator of V (a=t)) and Young's incquality. The second incquality holds by Assumption 4.1 and 4.2 also the property of sampling in the cluster (see details in Lemma F.6), i.e.
E
1
m (f n
E
Σ LEVE
Mii E 8t (V - |
1'1
iES.A
m(n m)
m(m 1)
1 Σ Vi((tt))))))) (E
Σ ( - (..
E
n(n 1) n²
n(n - 1)
n
iEVi
iEVE
m(n- m)
OK.
n(n 1)
Averaging Eq. 39
over h: = 1,... K clusters, we have
K
r.1+1 - 1.,1
K km
1 K
< (1+ + 4(1 + + )n 1
Σ
El|
E
x, 171 101+4(0 4(1 + 1n 2
E l1 15.1191
K
N
R
2
m(n m)
14(1+ mm
(x.)
||
+
ग n
+
4(1 + ? 11mm oo
n(n - 1)
k
K N
< [(1 + +7) + 4(1 + ) T.2
1
E
xx 11 + 4(1 + 1 1,? 1.2
E Bllaat 22.
K
k=
k=1 1=1
0²
m(n m)
+4(1 + M (a 20 [< 0.)
4(1 + 7 1
(40)
n
a 1)
32

---

Published in Transactions on Machine Learning Research (08/2024)
where the second incquality holds by Assumption 4.4 and incorporates the previously defined term of K Ek=1 of Choosing 7 zz-1 with the condition of 1y S M7L we have
K
E T r,1+1 -2,11
K
k=1
1
Bll -
xr11%] + 16I L
1
B Bll
x;,,11
47 -
2(4I 1) K
N
k=
iEV.
0
m(n - m)
+
|[²] - + n
16In/'0
n(n 1)
k
1
K
C3
||| xr - 11 + 16I L2
Blllot,
K
N
k=1
1EV
+ 1/1 -²
m(n m)
16
(41)
n
n(n 1)
where C7 11
This concludes the proof.
F.1 Lemma for intra-cluster consensus error
Lemma F.2. The intra-cluster consensus error En= || .ttell also known |x 1| has the fol- lowing upper bound,
K
1 r.+++1
[12
N
k=1
Pk kE(K]
max
2 (1 + 2) + U 4L2
max (p (1 + [k)}
1 N
Σ
EI|l
7,t
||3!
kE[K]
-=
rk max {pk(1 1: +cx)3 -4L - 1, 11
max kE[K]
fpt (1
o
KE(K]
K
+ n
p + Ck )4 + 2
(42)
K
where is some constant related to the Young's incquality, and it could be uniformly chosen. for all k 1. K.
Proof. By definition we have X (x) x%,.' and xx. X2, J), where J = n 1, 1/-- Thus
have
k 21,11 = ||(x [1 x. (I, - -J) In (In (,,,.....,
| pit (In - J) (In, - J)x
-|x -..-' -xk+ ||
=11x// ||?,
(43)
33

---

Published in Transactions on Machine Learning Research (08/2024)
Recall the update rule of AFGA and CAFGA, there is x (Wi. - -x,, -,...,), then we have
1 [12a1 E(E(II(WW - J)(X - -
E(E(II(WV - J)X
=(EECI((WV - ()x - -VF
+ +n B(ECIWW. -
(VFF(( - B-MBBB(IWW--VV/F(C
$ BlllWW (x) - -x Pi
s p1 1) -|I1x,1-111111 21 ( n non
(44)
where the (X+(X*) E Raxd x is associated to cluster by stacking Vf((=') for i E V&, row-wise. The third equality is due to the unbiasedness of stochastic gradient. The first. inequality holds by Assumption 4.2 and
[VP((*)) - 1l = =E= ( I. For the Frobenius norm, there is ||AB| ||A| ||4
B F.
The second incquality holds by Young's incquality with some paramcter Çx > and ||AB|] well. For (x by definition, we have
2
B
IV Σ [[((,))))
SEV2
Σ [V)((( V.((t))) + V.A(( - V)( V(L()))) V/, Vf
KEV
Σ
4llV..((').)) - + -
leV
(x,))1
(
viu 4L 4L21| 12 112 + ALL 4L21|
x, + (z.))(
VeW.
< 4 x 1| +4L'n|EE
2111² 4n
4 Ano
(45)
where the first incquality holds by Cauchy inequality, the second incquality holds by Assumption 4.1 and the last inequality holds by Assumption 4.4 Averaging Eq. 45 over k: 1,... K, we have the following
34

---

Published in Transactions on Machine Learning Research (08/2024)
iteration
K
||||X
r,++1 ||
N
K
1
(1 + 5k ).
||| E 11
1
Σ
+1+
n 0²
1
PK
N
N
K
k=1
K
K
+ -
v
N
k=1
K
K
Pk + (k)
B xr 12] + IIl
2 1
Σ
p +
K
K
k=1
k=1
K
"1 K
1
Σ
P + (k)
40 0² pmax
K
max {pE(1 (1 + (k)) 1
max K)
p + 5e + +n 4L
Σ E1|IX
kE[K]
N
+ V
max (p + [c)) .1I.B11 arr1171 + vr max kE(K]
(p2 + (.) 44 A(a2E\1I/((r,))11 +
kE(K]
K "
1
(1 + (1 40 + o² Pmaxx.
(46)
This concludes the proof.
F.2 Lemma for summation of intra-cluster and inter-cluster consensus errors
Lemma F.3. If the local learning rate satisfies the condition: n S 1. STL: the for all local round = O,..., I 1,
there is
E
113]
N k=1
K k=1
s (t + 1)C 1 (I + Pinex H p)
(I+
[[ + + (1+ 1) HI, H7.p
0² 0²
m(n m2)
+ (t + 1)Cini 02 Prux (t + 1)C1
1+
Pmax
th
+
n(n 1) Ioi
(47)
I2
n
where C₁ is a constant independent to parameters.
Proof. Denote auxiliary vector
Σ E - xz,111 1111 T
Mr.
E x rit
113)
(48)
K
From Lemma F.1 and
F2 we have the following inequality which is defined element wise for 0..,, I
Mrs41 G. G.Mra Br
(49)
where
maaxee|]] (1 (1+ 6 + tr pt. 4L2 Tp 412
G
(50)
16Im; 1
C1
Appa
+ 0.)
+ 4pr o + 11f 02 p2
(b())
B
16In/
+ 0
m
2 o²
16m m3) Inj oz
(())
(51)
m(n
35

---

Published in Transactions on Machine Learning Research (08/2024)
Consider the eigen-decomposition of matrix G.
(11-Cz CT
22
(u. 2) (-16ZTf
-X2 + Cr
G 16In 13(11 - X2)
(52)
16 L6
Oz
where we assume A1 S 22. thus we have
(A1-Cr d2 22-CT
( 2) ( 16 L.
-X2 + Cz
\ -r (brb)
GB 16Inf )2)
16In 166TT)
-16In 1
1
(A1--z))
Oz) (x L2
11 + 0z)6(1) + -
Cz) - 12 + 1 -2)6(21)
( 16In/ L2 12
16Tn - 22)
11(-22 (7)((0) + 16-16 +1((Ar -C7)((0)
(53)
Therefore the sum of two elements has the following result
X/ X
=2 + (gb(2)
1, + PL
A2 A1
A/2 X
S xg((0 + b())
+
1,I + Pr
(54)
A2 X
Therefore, we have the following result
1g 1 + b + X2 - X1
(16In) + 4n pr. p..Le))))
(55)
A2 A1
0=0
j=0
Since A2 2 CT > 1, we have
\/1 - x
d22 \1
2
1-1
A1
Ao
S N22
min
A2 d1 o S Mgiin
A2
min { (12 X1 (.
(56)
0=0
thus we have
Σ (1,1)Gb Bra_j S Σ 1=0
(g(0
(1)
+
+
Xa min
1 122 d1 1 {
(16Im + 4n PLL222))
5=0
1m0
(57)
By the definition of pr. = max (1 + (k) and by the Gershgorin's theorem, since vp > 0, we have the upper bound for X2.
A2 S max
max p + 55 + tH PL kE[K]
SL²,CI + 16I 1
< max
P + C5 + kE[K]
max
Pr.
1 1+
(58)
(4I - 1)21
4T -
where the last inequality holds by the bound of ni S Gal-L3 < 161(41-1)2
Define a distance constant
HI,p min {I, }- Next we consider two cases: small or dense communication network with Pmax
1 - z and large and sparse communcattio network with Pmax 1 T.
Case 1: For Pinax < 1 - 1; i.e,, I-pmax < I, thus we have HI,p = I-paax:
Let Sa = I-ps then we have
Prnxx
max Pk (1 + 1 Pmaxi kE[M]
PL max kE(k]
Pk
Prnxx HI,
(59)
Pk
1
Pmax
36

---

Published in Transactions on Machine Learning Research (08/2024)
where the middle part of the second equality holds by the monotonically increasing of 1-z- for 22 is formalized as
Then the bound
Pinxx
A S max
Pmax +
1
(1 -
Pinax)
2I 4I
1)
2(4I - 1)
7
3
S max
1 + 2(4I 1 1)
I
2 1)
3
(60)
4I
where the second inequality holds by Pmax - Then by 8 S and X2 2 (just by the definition of matrix G can get this result), we can obtain the following bound
Σ No 1=0
-1 (11+z2-1)
2 4I
---111
Σ f=0
33
500h 33
Σ 0
(61)
j=0
We also have
1 (1 21-
Pmax + n Pr. S Pmax +
(1 Pmax) (4I 1)4I
Pmax
I
+
4(1I-1) S Cz.
(62)
where the second inequality holds by the upper bound for Pmax- By the definition of matrix G, bound the difference of X2- X1,
A a = Cr - Pmax PT.,2
Pmax
2 Cz
|mmx + (1- Pmax (4I 1)47
Cr
Pmnxx + Pmaxx
4(4I - 1)
1
1 47
Pmax + Pinax
4I
Pmma)) )
(1+ 4I 4I-1
2 -Pmax-
(63)
where the first and second incquality hold by the defined notations. Then we have
X/ min { A2 - A1 . (16In) 1 + 4n PL
Σ G1,1) Brd,, $ Σ
(2))
Σ
1=0
1=0
j=0
30b + +b9) + Σ
3md (16II2 + +p1 (ppl) min { (e -x.x)11]]
1
1=0
1=0
3( + + + Σ
3m (16IL>0 + p L (2)(2))
0=0
0=
HI.P
3(6 + (2) + Σ
(48I6 + 12 o Puas (22)
16I 1)
0=
H²
$
Σ
400 mg
+ (2) +
P (2)
p
(64)
T
1=
1=
37

---

Published in Transactions on Machine Learning Research (08/2024)
Then by the definition of b()) and b(2) we have
Σ (1,
Bre-s
1=0
(4PLM) + 110 + 4p + +no o2 + mh - + 16
m(n - m)
4
n(n 1) Im o7
H
+ nt o + 16 m(n m) Ini of
+ Σ
Pimax
(102R((2B
I
n
n(n 16-1 1)
1=0
= (1 + 1)
10((4Appsst + +16Int) +
H
Pmax 16I
|| + of²) + 16
T
12,0
(c=
0²
m(n m - -m) m)
+ 16n 2 0² 2.2 Pmmmxx
+ (4n2 +
+ 16
n(n 1) Io?
I
< (1 + 10( ( 16pinex HT. + 64I + 161 HT.p
Pinxx
+ +0.) [a²
+ 16pmmax Hr of
H2
Pruxx" vp )
+ 16 (
m(n m)
- Io? ) nin - 1)
+ +167 0² Praaxxx + (nn + I
S (1 + 1)Cini (I + Panax HI. (a2 ((x,) + o..) + (1+ + 1)C Pmxx HI.p of
+ (t+ 1) Pruxx + (t + 1)C1
1+
H
I.P
Piaxx
mi
0² +
m(n m) Iof
(65)
I2
n(n 1)
where Cj is some universal constant. The inequality holds by PL = pluax Hz.p and HI.p S I.
Case 2: In this case we have Pmax > 7: which means HI.p = I. Let Ca- = (4I - 1), thus we have
max RE[R]
p
(1 + C5 = Pinax (1 + - (4I-1)-1) pr. = 4I HT.p-
(66)
The upper bound for X2 has the form of
{
A S max
max kE(K]
pb(1 + 555 + npp 8L2, CI
2
3 2(4I 1)
< max
Pinax (1 + (4I - -1)-1) +
1 +
4I 1
3
$ 1 +
(67)
4I 1
By the fact of min
1 1 < I = -HI we have
1
N/ min { 1 1 fni 40r 422L (,,5 .
Σ (L,1) Bra_, S Σ
12(0 7,1- + (2))
+ Σ
A22 - 21
1=0
1=0
1=0
Σ
300 + +1/) Σ
v1² 16 H 1,20?) -HHT
< Σ 3(110 + +0g
16pmax Hr. b(
(2)
3 HT.,
16 T2
==0
1=0
H2
Σ 1=
3(6 +b(9)
Σ
3pmax (22
(68)
I
1=0
where the above inequalities hold by the fact that PL- 4I mp- Thus we can get similar upper bound as Eq.
1Hr and the constraint on step size This concludes the proof.
65 in Case 1.
38

---

Published in Transactions on Machine Learning Research (08/2024)
Lemma F.4. With the similar condition in Lemma F.3 we have the corresponding bound for the intra-
cluster consensus error ||x*+111 1
K
rit [1 - (t + 1)C HT, of B/ + + (t
1)Cini HI.pp
k=1
11
o²
+ 1+C m m) 11
+ + 1 + ( 1)C1
T
max
n - 1) n Paax of
I
n
(69)
Proof. With the same definition of the auxiliary vector My. and the matrix G and Brd in the proof of there is
Lemma
F3
K
K
T - 2 2T.111)
My =
E|
N
rut
K
1=1
1=1
My3
G Gr,tMr,o + Σ
GP Bratj
Σ
G Bra-is
(70)
j=0
3=0
hence we have
B
Mr.: -(,0) Σ
GO Bra-j
N
3=0
16 + \/- - X1
4m PL. 2,,3
A2 - X1
X/1 - X1
4m 4n1 PL 1.133
A2 d1
N/ X
$
+
An PL. 1.21
(71)
22 A1
with the similar proof techniques as in Lemma
there is
E
3b H2 of
(1)
12PL oi (a
(1 )()0)))) +12p=)+ + 3n? Pmax
0=0 0
+ H2 1.
+ 16 16n m(n - ml Imj o0 + m
0²
T
n(n 1)
< (t 1)0 oi H4 pI max (a 1 +
+ (t + 1)C1n/ 2 H HI,p of
+ (1 + 1)Cnn P
o² + (1 + 1)Crn) 1
H
2
d² + (1 + 1
m (n m
111
H²
I.P
max
of.
T
n
n(n 1)
I
(72)
This concludes the proof.
0
F.3 Lemmas for model difference A,
There is corresponding Lemma about model difference A, for the partial participation settings.
39

---

Published in Transactions on Machine Learning Research (08/2024)
Lemma F.5.
The global model difference A, Ek=1 Eiecs, A in partial participation settings satisfies
B[| 112]
I o² + (I -
I-1
N
17
1 K
Σ
E2
N
Σ
f((2)))))
+
+nf
f 2 x
N
K
1=0
21110²
+ 8
n1 - m
+ 1²
+
m
P
(73)
m(n 1)
N
k=1
Proof. Recall the definition of ž,,,, there is Trit 1 sampling) and the intra-cluster average /² ",, zh mā ,, where _² Th,41 1 Eveve g For the model difference Ar, we have
N Eim z²,, (here we don't need to consider of client
2
B||A,117
a
By
m
K
1 प. T
Ir,I F TT,I-1 T ... T Łr,1 2r
KKKK
m
K
27
1
- 2E
Ir
+ 2E
xr F x F
F xr Ir
(74)
Np
A
iE
where the inequality holds by Cauchy-Schwarz inequality. For the first. term in Eq. 74 by the probability of the sampling strategy (see details in Lemma F.6 we have
K
27
K
1 Zn '1
ZrII 2
Np
(Np)²
k= 1 iESt
k= ie
m(m - 1)
K
Km(n m) n(n 1)
E
Z Zr.
|
(Np)²
12(n2
k= V V4
k= ieV.
m(n m)
K
Ell Zr.2
(75)
(Np)²
n(n 1)
k= 1eV
40

---

Published in Transactions on Machine Learning Research (08/2024)
For the second part in Eq. 74
we have
E
Br, 1
+
Tr,1
I
111
g
K
k= KES
K
27
ge + ((((ot()))
k=l
K
111 I-1
E
g - v)(
+
ΣΣΣΣ
N
1= k= iES!
1= k=
ie
(I 1)M
I-1 K ΣΣ
a² E
(76)
N2
N
1=0 k= iESt
where
I-1
E
k= ke
m
m
M.M V)(E
F
Σ
v f((ttt)) ){'
N2
iES!
$ 2E
7
(((
M
N2
k= iest
I-1
K
- 1
+E
mmm
+ 44
Σ
(V
N
k=l
I-1
K
RM N
1
2 3
E
NN
Σ
Vi
No
0=
k=
1est
1=1
V (ar 1/
I-1
1 M
+4
Σ
+ +4([I- - 1) Σ
Σ Σ
B Blllot -
(77)
N2
1=
k=liest
41

---

Published in Transactions on Machine Learning Research (08/2024)
therefore,
I-1
K
Vilaod 11
Σ
k= sest
I-1
K
N
<
Σ
+
+
R
v
(i(aa
N2
0
1=1
I-1
K
17]
M
I-1 K
+4
fa(
+4(I - 1)1,
B 11
N
N²
-=
k=
1ESt
M
(i((ttt))) 1'1
Σ
4I
E
Σ
N2
1=
k= EESt
1)22 +4(I- +4(I-1)12")
nf
M I 1
Bl|
E
19
N
list
I-1
m M N N Σ
+ 47
fi (TttT))
2=
1= EE
of M
T-1 K
+ 4(I + 1)L
ΣΣ Σ
Blllet - -2,,,11
(78)
N2
t=0 kliis
where the last inequality follows
K
E
Σ
(ork)))))
0=
1 SE
K
Σ
(f((zt))) F V
K
17
I-1
K
8
f(((
+ >
E
V fl V (i
k= iE
1=0
k= je
17
M
T-1 Σ
<
+
L
B[llot - =1,,1111
(79)
N2
t=0 ksl
and we use the characteristic of conditional expectation, where we use the characteristic of conditional
expectation, ie., Es, 1 E Eiesy Vf( E M ΣK Ever, vf( Update the expectation
K term, that is ES, 1 DK Eies: V/( " M V )]] and Vr # 8, i Sh is independent
42

---

Published in Transactions on Machine Learning Research (08/2024)
with i E S.:. Then we have
K
1
34
EE
Σ No
|"]
84 K m(n- m)
(z,,, 113]
N
k= VeV.
Sn m(m 1)
K
V fi :
N n(n -
1= VEV.
81 K min m)
Σ
I-1 N
8 m(m -
Σ
T-1
Σ
N
v (
(80)
N2 nnn -
N2 n(n 1)
where the inequality holds by Lemma F.6
T-1 N
E Vl (x).)) ( fa(t.) F fx.
E[4L"| r.t 2|2 4L 2 + 4m fz + 4no
[4L ||3] + 4L 4L
2. + 4na 4na²B[1V//a,)]] + Ano + 4no
(81)
k=1
43

---

Published in Transactions on Machine Learning Research (08/2024)
Then combining the previous terms, we have
111
3
2-
Σ Σ
$ 2E
F ZT
+ 2E
Tr.I F Dr.I-1 F
T Lt,1 Er
Np 1 i.
2K m(n m)
K
2n 0²
$ (Np)2
B B1|l2 1.
n(n - 1)
N
1m LEV
I-1 K
2E
m
Σ
N
iESt
2K m(n m)
K
2n IMI o²
5 (Np)²
Blllo
n(n - 1)
N2
KEV
V 1'1
(x 22
16
Σ
E
8I
E
m
v
==
k=liEst
t=0
MT.
I-1
+8 +
E p rd
-x/t,111
N2
IES,
2K
m(n m))
K
2n IM N2
B BIIK
x 12
o2
(Np)² n(n 1)
16 K m(n m))
I-1
N
167 m(m
1)
I-1
N
E
E
fa (or
N
n2nn 1)
ntnn - 1) N²
t=0
t=0
I-1
K
|
ML I-1
87
mum
V
Je k
+8 +1)
Blllat 11
N
N2
(=0
t=0 k=liES,
2K
m(n m)
K
21FIM
E
[ r.
119]
( n(n - 1)
N2
1=1
16n K m(n m)
K
AL X
k. 122] + 4L
4L 11 21
N2 n(n 1)
t=0 Am
16 m(m 1)
T-1
4na 4na V of (xx, || + 4no + 4no
Σ E
((
N2 n(n - 1)
mm K
f((( 19
1 M2 I-1 K
+ +(II+1)
|| - 11,,
(82)
N
N² t= kel
44

---

Published in Transactions on Machine Learning Research (08/2024)
where we have
16 K m(n m.)
K
Σ1
Σ
41'B1IIX +1]]+ 4L 412 nE[1 xr 2.-121
N 1(n2 1011 1)
ł=0
16n K m(n m7)
T-1 1
AL [1 + 4L ALL T - 22-199
N n(n - 1)
1=
64n 2 m(n m)) I
K
64n L2
m(n m)
I-1 K
B
Σ
B Bl| x211
N
n²
K
n²
1)
t=0 1=1
1= k=1
64n L2 m(n ml)
B Blla,, 2x.119]
n² - 1)
< <64n m(n ml)
I²C ni +
H (a 2 + o.)) + I+ Pran
n²(n -)
+ 120 Pmax + I-c (+
H2
Praxx
- (
m - m) Io? )} n(n - 1)
m(n-m)
(83)
I
n
we have
2K
m(n m)
+1||**1111
(Np)² nin 1)
k=1
2 (n - m)
K
Kn m(n 1)
k=1
2(n m))
IOini H P
[|| + +o?) + +Cinn HI HI
m(n -
112
0² +
m(n m)
n(n - 1) Io? ].
+ IC ou + IImm
P Punax
(84)
I
n2
and
V ML
8(Z + 1)
| xt,, [/2]
N2
seS,
T 2 2
I-1
K
< <8(++1) 1)
Ellle 7 11
N2
t=0
k=
1 N
Th mL
I-1
K
8(I + 1)
r 1I21 1=
n
h mL2 I-1
= 8(I + 1)
(t+ (++1)C H ( (f, + (++ (1++1)mmm Hz 1) p
H2
Piax o²
+ (1 + 1)Cmnh P 0² (1 + 1)C
I.p
I
n
=4(I + 1)2 mm
ICinf H Hi
V oZ.) + ICmn pr of
H2 1.
022
min m)
n(n- - Ia ].
+ICni 2 2² IICii
Punxx
-
(85)
T
n
45

---

Published in Transactions on Machine Learning Research (08/2024)
Then by merging pieces together, we have
E1 1121
IMPIM
(2nn (2(n-m) m)
4(I + 1)2 mLL
$ N
o²
ICin HI. (F + IC Hz pp
m((n -1
n
HH.
Pinax 0² +
m(n m) n(n 1) Iot) )
II1 Pmax
0² + II
I2
-64n mmmm ml
fxx,)) I'i + Panax HI (a V f
o²))
n²(n - 1)
H²
(-=
m(n m)
Iof ]
+I-C HT, o oř + o pmax + I=Cini
1+
Pmax
T
n(n - 1)
16 K m(n m)) I-1 k
Ano + 4moza
N2 n(n
1)
k=1
16m m(m 1)
I
E
N
V
8m Im 2
I-1
E
1
v
Ja ( 7,1)
N2 n(n 1)
n
K
[=Ul
i=1
k=
IM d² +
64nfIImnn m)
$
[o] + 021
N2
n²(n - 1)
((nn - 1) + 64n m(n m)
2(n m)
4(I 1)
I
IC pr
+
n²(n - 1)
n
H2
02 +
m(n m)
ICCn HT. HT.p max oी + IC u/ p max 0² + IC
2
n(n 1) Ioa
I Pmax
+64n 1.2 m(n m)
0² m(n m)
I C'nn E[
).)
I'Cnn
n(n - 1) Im?
n² (
16nfm(mm 1)
N
1
8 Im2 I-1
E
Σ
(86)
n(n ((n--)
n
Thus it concludes the proof.
F.4 Additional Supporting Lemmas
Lemma F.6 (Cluster sampling). For model weights y Vk E [K] E Vk,r E t E [Z], there is
B Σ Σ kE[K]
Hi
2
< R
m(m m
1)
K
kid yr
+
Kmin - m)
| 1
(87)
nnn
1)
n(nn 1) k= LEVE
==1
A= 1eV
46

---

Published in Transactions on Machine Learning Research (08/2024)
Proof.
K Σ
Hi E 1o 11
Σ
VEV
K
P(i E 5
Σ
|, 11
+P(i*j S
Σ
Σ
(v ((f-)t)))))
+ +Piic E j E Sikk
# E [K]E
ΣΣ
Σ
(1),t)) (1ff1)
kil ie JEV
K
K
E
m
11
m(m 1)
Σ
Σ
n
n(n-11 1)
k= iEVa
k= tæ
m²
(3**) (x*"))
n
kydl VEVE JEV
m(m 1)
8 2
m(n m))
E
+
n(n 1)
n(n2 1)
k=lieV
k= =ive
m(n - m
(3 ((x?
n² 1)
kel VEV, JEN
m(m 1)
m(n m))
K
11
E
+
n(n - 1)
n(n - 1)
KEV
1= iEV
m(n - m)
ΣΣΣ lel VEV JEM
G1loat11 + 2 ||be
(88)
n2(n 1)
where the third equation holds by the probability of random sampling with replacement, i.e., P(i E 8
n. PPP و E 5 = mfm-1) m)n-1) .Pf E Skij E S k +
LE
E [K]]
m² The forth equation holds by (a, b)
|llall + |b|| - ||a - b1 2 Eiijy |a: a= ni - all?, and I Σier, 112
Σ Erev, / + Ex Eier Ejen (g. ). The last incquality holds by a'b < || + b|bl
Re-organize the last item,
m(n m n n²(n-11 1)
ΣEΣ
ト 1| + 1 -10
m(n - m)) n2(n 1)
K (K- 1)m
(89)
legfl ie Va JEMi
k= V
then we have
Mi E S. 11 Ait [7]
E
Σ
kE[K]
1=1
mm(m= 1)
K
m(n
m) nn 1)
K
< E
2
nnnn 1)
Am 1 V
+
m(n m²)
(K - 1)m
will?
n²(n - 1)
km 1 1
E
m(m - 1)
Σ Σ
K
yr
Km(n- - m)) nann - 1)
K
| 11
(90)
n(n 1)
k=1 3
k= iE
This concludes the proof.
47

---

Published in Transactions on Machine Learning Research (08/2024)
Lemma F.7 (Lemma for momentum term in the update rule). The first order momentum terms m, in Algorithm 7 hold the following relationship w.r.t. model difference Ar:
R
E
m
11
E A
11
(91)
Proof. By the updating rule, we have
E
1 E
(1
B1)
B1
A.
Au.s "
$
31)
Σ E
i=1
(1 31)3 Σ E
Au..))
1=1
$ (1 - 31) Σ 81
E
101,
(92)
aml
summing over t= I,..., T yields
R
E mr |=] =1 B1)
3 E ||AA|
P=
(1 31)
31 EE A. [1
R
S (1 31)
Σ
E B1 11
1- 31
R
B|||A,|
121
(93)
This concludes the proof.
Lemma F.8. Under Assumptions
4.3 for AFGA and CAFGA, we have [Vf(2)] S G, | S
mm.IG
||m/|| < IQ ||0, I m²
G² and | < m² G²
n²
Proof. Since f has G-bounded stochastic gradients, for any and &, we have [V E)I S G, we have
|[]f(=)] = [ (f(x,
For AFGA and CAFGA, the model difference A on cluster satisfics,
I-1
I-1
I-1 =
Σ
Σ
Σ
Σ
gi iES
Σ
9
t=0
1=0
icV
t=
therefore,
I-1
7-1 Σ
A = m
Σ
= m
Σ
gi
-
man
IG
1=0
t=
SE
48

---

Published in Transactions on Machine Learning Research (08/2024)
for the global model difference Ar,
1 K
mmZG
A
||
&
kE[K]
Thus we can obtain the bound for momentum my and variance Vr.
mmZG
m I²
m (1 31)
31 A
|
82)
82
A
n²
==1
By the updating rule of Gr there exists j [r] such that 0, Ug. Then
G2
(94)
n²
This concludes the proof.
Lemma F.9. For the variance difference sequence r-1 V.
1/2 1/2
we have
Σ
1/2
S
d Ve
Σ
V
1/2
S
d
(95)
Proof. The proof of Lemma
F.9
exactly the same as the proof of Lemma C.2 in (Wang et al. 2022b
7
49


Reviews:
[{"review_id": "OGOlCxtdFC", "reviewer": "Reviewer_i2Nk", "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 has a fairly comprehensive discussion existing methods\n+ the paper has most of the basic components including the theoretical discussion and ablation studies. \n\nWeakness:\n- The theoretical discussion introduces several new assumptions, some assumptions might not be so realistic. \n- It's unclear why the authors choose ConvMixer as the main experimental architecture, instead of more population choices (typically used in Federated Learning)", "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 introduces a novel adaptive federated learning framework, Adaptive Federated learning with Local Gossip Averaging (AFGA), aimed at addressing the data heterogeneity problem prevalent in adaptive federated learning. The proposed framework incorporates a client re-sampling strategy and decentralized peer-to-peer gossip communications to mitigate the dissimilarity in data distribution across clients, thus enhancing model convergence without requiring additional communication or gradient computation costs. The paper also includes a theoretical discussion and emprical evidence.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The paper reports \"the average of the last 5 global rounds to represent final accuracy\", please be more explicit about the rationales or the customs behind it. \n\n2. Given the fact that the experimental setting might be too specific (due to the nature of Federated learning), it is a good idea to include error bar (std) in the reported tables. \n\n3. The theoretical results relies on several assumption, in particular, please offer more dicussions on how realistic the Assumption 4.5 is, in theory and experimental (through simulations). Otherwise, it will be hard to evaluate the theoretical contributions. In addition, it seems graph G is never mentioned ahead of Assumption 4.5. \n\n4. minor: Table 5 formatting issues.", "broader_impact_concerns": "none noted.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "A033G2hdrJ", "reviewer": "Reviewer_Zydi", "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 work comes with provable convergence guarantees.\n- The paper is generally well-written and easy to understand.\n- Empirical results seems solid.\n\nWeaknesses:\n- Having an entire gossip matrix that is shared across clients is a very strong assumption and does not seem practical.\n- From the appendix it seems that setting $\\rho=0$ defaults the best performance? Or am I missing anything? Relation between $\\rho$ and utility is missing.\n- The convergence bound seems worse than the author claimed. Equation 3 is only dominated by $O\\left(\\frac{1}{\\sqrt{R\\mathcal{I}M}}\\right)$ if $R>\\sqrt{R\\mathcal{I}M}$. Otherwise it is at least $O\\left(\\frac{1}{\\sqrt{R\\mathcal{I}M}}\\right)+O\\left(\\frac{1}{R}\\right)$. And this is given $\\rho=0$. Also, I don't think omitting parameters such as $M,N,L$ is good in order to understand the bound. I suggest the authors to clean up the bound so that it only contains $R, L, N$ and subsampling rate $q=M/N$ or $M$ itself.\n- Explanation of 'R#' is missing. Is that the number of rounds? How is this selected as this number is different for different methods.\n- Table 5 adjust the spacing.", "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": "In this work, the authors propose a new method for adaptive optimization in federated learning. The method is based on peer-to-peer gossip communications between local clients. With this additional step of local averaging, the authors show that the proposed method outperforms prior baselines for adaptive optimization in FL.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Explanation of 'R#' is missing.\n- How is hyperparameter, for example $W$ is tuned?\n- Clean up convergence bound, as I mentioned in the weakness part above.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Vhn4t0k2gj", "reviewer": "Reviewer_DE59", "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": "The strengths of this paper include a clear presentation of the proposed algorithms and comparative analysis with existing federated learning (FL) algorithms, highlighting improvements in accuracy and convergence speed.\n\nHowever, the paper falls short in its discussion of data heterogeneity impacts. It lacks a thorough analysis of how the proposed algorithm performs under varying degrees of data heterogeneity, which is crucial for validating the effectiveness of any FL algorithm.", "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 introduces AFGA, an enhanced version of the FedAMSGrad algorithm, which incorporates adaptive federated learning techniques. AFGA integrates two novel components: client re-sampling and gossip communications. Client re-sampling involves selecting a new subset of clients for gradient computation during each local iteration, whereas gossip communications enable clients to exchange weights with their connected peers. To mitigate the additional communication overhead introduced by gossip communications, the authors propose a variant, clustered-clients AFGA, where clients are grouped into clusters to restrict re-sampling and communications within each cluster.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The rationale behind client re-sampling is unclear, given the inherent nature of partial participation in FL due to varying client availability. The method assumes control over client selection, which may not reflect practical scenarios where available clients can fluctuate unpredictably.\n\n2. Could you clarify the relationship between $S_{r,t}$ and $S_r$? It's important to understand how these selections differ across iterations and rounds.\n\n3. What are the variance or deviation measures for the mean values presented in Table 1? This information would help assess the statistical significance of the reported results.\n\n4. The term R# (representing the total number of rounds to achieve a specified accuracy level) used in Tables 1 and 2 is not defined until the caption of Table 5. This should be clarified earlier in the document for better reader comprehension.\n\n5. Regarding the clustered-clients AFGA (CAFGA), is the clustering of clients into equal-sized groups based on randomness, or is there a specific metric assessing client similarity that influences cluster composition? Understanding this clustering basis is essential for evaluating the algorithm's practical applicability and performance efficiency.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the convergence behavior of adaptive methods in federated optimization. It is stated that the convergence of earlier proposed methods, such as FedAMSGrad, can be slowed down in the presence of data heterogeneity. To alleviate this, two changes are proposed to FedAMSGrad: a subsampling strategy among the active clients and global gossip averaging to improve mixing. Experiments have shown that the proposed method can enhance convergence.

The reviewers found that the contribution is well within the scope of TMLR. Additionally, the authors have thoroughly addressed all comments and suggestions provided during the review process in their revisions. 

Although the convergence theorems have a weaker dependence on data heterogeneity measures than similar statements for the referenced baselines, the paper does not discuss the tightness of the theoretical results. This is a minor limitation of the work.
Decision: Accept (poster)