Every Parameter Matters: Ensuring the Convergence of Federated Learning with Dynamic Heterogeneous Models Reduction
Authors: Hanhan Zhou
Tian Lan
Guru Prasadh Venkataramani
Wenbo Ding
Venue: NeurIPS 2023 poster (2023)
Keywords: Federated Learning
Optimization
Deep Learning
TL;DR: We present a unifying framework for heterogeneous Federated Learning algorithms and provide a general convergence analysis with numerical validation.

Abstract: Cross-device Federated Learning (FL) faces significant challenges where low-end clients that could potentially make unique contributions are excluded from training large models due to their resource bottlenecks. Recent research efforts have focused on model-heterogeneous FL, by extracting reduced-size models from the global model and applying them to local clients accordingly. Despite the empirical success, general theoretical guarantees of convergence on this method remain an open question. 
This paper presents a unifying framework for heterogeneous FL algorithms with online model extraction and provides a general convergence analysis for the first time. 
In particular, we prove that under certain sufficient conditions and for both IID and non-IID data, these algorithms converge to a stationary point of standard FL for general smooth cost functions. Moreover, we introduce the concept of minimum coverage index, together with model reduction noise, which will determine the convergence of heterogeneous federated learning, and therefore we advocate for a holistic approach that considers both factors to enhance the efficiency of heterogeneous federated learning.

Every Parameter Matters: Ensuring the Convergence of Federated Learning with Dynamic Heterogeneous Models Reduction
Hanhan Zhou
Tian Lan The George Washington University tlan@gwu. edu
The George Washington University banhan@gwu. edu
Guru Venkataramani
Wenbo Ding
The George Washington University guruvēgwu. edu
Tsinghua- Berkeley Shenzhen Institute ding. wenboösz. tsinghua edu.
Abstract
Cross-device Federated Learning (FL) faces significant challenges where low- end clients that could potentially make unique contributions are excluded from training large models due to their resource bottlenecks. Recent research efforts have focused on mooel--eteeogeeeenn
FL, by extracting arduced-size models from the global model and applying them to local clients accordingly. Despite the empirical success, general theoretical guarantees of convergence on this method remain open question. This paper presents a unifying framework for heterogeneous FI. algorithms with online model extraction and provides general convergence analysis for the first time. In particular, we prove that under certain sufficient conditions and for both IID and non-IID data, these algorithms converge to a stationary point of standard FL for general smooth cost functions. Morcover, we introduce the concept of minimum coverage index, together with model reduction noise, which will determine the convergence of heterogeneous federated learning, and therefore we advocate for a holistic approach that considers both factors to enhance the efficiency of heterogeneous federated learning.
Introduction
Federated Learning (FL) a machine learning paradigm that enables a massive number of distributed clients to collaborate and train a centralized global model without exposing their local data [I] Heterogeneous FL is confronted with two fundamental challenges: (1) mobile and edge devices that are equipped with drastically different computation and communication capabilities are becoming the dominant source for [2] also known as device heterogeneity; (2) state-of-the-art machine learning model sizes have grown significantly over the years, limiting the participation of certain devices in training. This has prompted significant recent attention to a family of FL. algorithms relying on training reduced-size heterogencous local models (often obtained through extracting subnet or pruning a shared global model) for global aggregation. It includes algorithms such as HeteroFL []] that employ fixed heterogencous local models, as well as algorithms like PruncFL 4 and FedRolex
[ that adaptively select and train pruned or partial models dynamically during training. However, the success of these algorithms has only been demonstrated empirically (e.g.. 2 3].. Unlike standard FL that has received rigorous analysis 6 algorithms is still an open question.
the convergence of heterogeneous FL
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

This paper aims to answer the following questions: Given heterogeneous FL algorithm that trains shared global model through sequence of time-varying and client-dependers local models, what conditions can guarantee its convergence? And intrinsically how do the resulting models compare to that of standard FL.2 There have been many existing efforts in establishing convergence guarantees for FL. algorithms, such as the popular FedAvg [1. on both IID (independent and identically distributed data) and non-IID[9) data distributions, but all rely on the assumption that local models share the same uniform structure as the global model Training heterogeneous local models, which could change both over time and across clients FL is desirable due to its ability to adapt to resource constraints and training (utcomes[10].
For general smooth cost functions and under standard FL assumptions, we prove that hetero- geneous FI. algorithms satisfying certain suffi- cient conditions can indeed converge to a neigh- borhood of stationary point of standard FL. (with a small optimality gap that is character- ized in our analysis), at a rate of O (o) in Q communication rounds. Moreover, we show not only that FL algorithms involving local clients training different subnets (pruned or extracted from the global model) will converge, but also that the more they cover the parameters space in the global model, the faster the training will converge. Thus. local clients should be encour- aged to train with reduced-size models that are of different subnets of the global model rather than pruning greedily. The work extends pre- vious analysis single-model adaptive prun- ing and subnetwork training [[]] [2] to the FL context, where fundamental challenge arises from FL's local update steps that cause hetero- geneous local models (obtained by pruning the same global model or extracting a submodel) to diverge before the next aggregation. We prove a new upperbound and show that the optimality gap (between heterogeneous and standard FL) is affected by both model-reduction noise and a new notion of minimum coverage index in FL (i.e., any parameters in the global model are included in at least N min local models).
Uloaal Model
Round D24
ScModel
Ia Madeb
4cModela
Emall-cpacity
Stali-cppchhy
Iegeecapaity
Figure I: pruning small parameters greedily, local clients when applied with different local models not only will converge under certain conditions, might even converge faster.
In this paper we show that instead of
The key contribution of this paper is to establish convergence conditions for federated learning algorithms that employ heterogeneous arbitrarily-prunct time-varying, and client-dependent local models to converge to a stationary point of standard FL. Numerical evaluations validate the sufficient conditions established in our analysis. The results demonstrate the benefit of designing new model reduction strategies with respect to both model reduction noise and minimum coverage index.
Background
Standard Federated Learning A standard FL problem considers distributed optimization for N clients:
N
min
F(0) &
Σ P.F with F(O,) (E,,,,((E,
(I)
where 0 is as set of trainable weights/parameters, (0) is a cost function defined on data set D; with respect to user specified loss function ((x, 0), and p: is the weight for the i-th client such that
p; 2 0 and Σ NPP =
Throughout this paper, "non-IID data" means that the data among local clients are not independent and identically distributed. "Heterogeneous" means each client model obtained by model reduction from a global model can be different from the global model and other clients. "Dynamic" means vare-ng, i.c. the model for one local client could change between each round.

---

The FL procedure, e.g., FedAvg M., typically consists of a sequence of stochastic gradient descent steps performed distributedly on each local objective, followed by a central step collecting the workers' updated local parameters and computing aggregated global parameter. For the q-th round of training, first, the central server broadcasts the latest global model parameters 0g to clients I,...,N, N, who perform local updates as follows:
gg q. V. (.:00m..:1::..-11 with yg.n.u 0g
where 7 is the local learning rate. After all available clients have concluded their local updates (in T' epochs), the server will aggregate parameters from them and generate the new global model for the next round, i.e., ap+1 = = p,0 The formulation captures FL with both IID and non-III data distributions.
3 Related Work
Federated Averaging and Related Convergence Analysis. FedAvg [ is consi dered the first and
the most commonly used federated learning algorithm. Several works have shown the convergence of
FedAvg under several different settings with both homogeneous (IID) data [ and heterogeneous
(non-IID) data [9] 7 even with partial clients participation [14]. Specifically, [8] demonstrated
LocalSGD achieves O D(vNq)
convergence for non-convex optimization and [9] established a conver-
gence rate of O(+) for strongly convex problems on FedAvg, where Q is the number of SGDs and N is the number of participated clients.
Efficient and Heterogeneous FL through Neural Network Pruning and Sparsification. Several
works [1_ 16
17
18
19
20 are proposed to further reduce communication costs in FL. One
direction is
data compression such quantization 21] 7 22 23), sketching (24 25 split
learning [26). learning with gradient sparsity (27) and sending the parameters selectively 28 This
type of work does not consider computation efficiency. There are also works that address the reduction of both computation and communication costs, including one way to utilize lossy compression and dropout techniques 29 30 Although early works mainly assume that all local models share the same architecture as the global model [31], recent works have empirically demonstrated that federated learning with heterogeneous client models to save both computation and communication is feasible. PruneFL[] proposed an approach with adaptive parameter pruming during FL. 33 proposed FL with a personalized and structured sparse mask. FjORD [33 and Hetro proposed to generate heterogeneous local models as a subnet of the global network by extracting a static sub-models, Hermes (34] finds the small sub-network by applying the structured pruning. There are also researches on extracting a subnetwork dynamically, e.g. Federated Dropout 29] extracts submodels randomly and (5) applies a rolling sub-model extraction.
Despite their empirical success, they either lack theoretical convergence analysis or are specific to their own work. PruneFL only shows a convergence of the proposed algorithm and does not ensure convergence to solution of standard FL. Mcanwhile, static subnet extraction like Hermes does not allow the pruned local networks to change over time nor develop general convergence conditions. Following Theorem [ works like Hermes can now employ time-varying subnet extractions, rather than static subnets, while still guaranteeing the convergence to standard FL. The convergence of HeteroFL. and FedRolex- which was not available now follows directly from Theorem 1. Once PruneFL. satisfies the conditions established in our Theorem I, convergence to a solution standard FL can be achieved, rather than simply converging some point. In summary, conditions in Theorem can provide support to existing FL algorithms that employ heterogeneous local models, ensuring convergence to standard FL. It also enables the design of optimized pruning masks/models to improve the minimum coverage index and thus the resulting gap to standard FL.
general convergence
4 Methodology
4.1
Problem Formulation for FL with Heterogeneous Local models
Given an FL algorithm that trains heterogeneous local models for global aggregation, our goal to analyze its convergence with respect to a stationary point of standard FL. We consider general formulation where the heterogeneous local models can be obtained using any model reduction
3

---

strategies that are both (i) time-varying to enable online adjustment of reduced local models during the entire training process and (ii) different across FL clients with respect their individual heterogeneous computing resource and network conditions. More formally, we denote the sequence of local models used by heterogeneous FL algorithm by masks M, E {0, 13 which can vary at any round q and for any client n. Let 0g denote the global model at the beginning of round g and O be the element- product. Thus, Og @ mygn defines the trainable parameters of the reduced local mode for client n in round 9. Our goal is to find sufficient conditions on such masks mg.. Vg. for the convergence of heterogeneous FL.
Here, we describe one around (say the gth) of the heterogeneous FL algorithm. First, the central server employs given model reduction strategy P(-) reduce the latest global model 0g and broadcast the resulting local models to clients:
gg. 0g My... with mmg. = P(0g: n. g), Vn.
We note that the model reduction strategy P(Og, q) can vary over time q and across clients n in heterogeneous FL. Each client n then trains the reduced local model by performing T local updates (in T epochs): 0g 0 -....-1-~--V
- > (0..../0....11....... Sn,-1)) mg.:: for 1 1...
where y the learning rate and f are independent samples uniformly drawn from local data D, at client n. We note that (f, E,,--1) @ Myn is a local stochastic gradient evaluated using only local parameters in ng,,,-1 (available to the heterogeneous local model) and that only locally trainable parameters are updated by the stochastic gradient (via element-wist product with m..n).
Finally, the central server aggregates the local models fn.g.7 Yn and produces an updated global model 4 Due to the use of heterogeneous local models, each global parameter is included in (potentially) different subset of the local models. Let Let be the set of clients, whose local models contain the äth modeling parameter in round q. That is n .N1 if mg.h = 1 and & .A if (2) My.n O. Global update of the ith parameter is performed by aggregating local models with the parameter available, i.e.,
Vi,
REND
where (N((0) is the number of local models containing the ith parameter. We summarize the algorithm details in Algorithm 1 and the explanation of the notations the Appendix.
The fundamental challenge of convergence analysis mainly stems from the local updates in Eq.(3) While the heterogeneous models n. provided to local clients at the beginning of round q are obtained from the same global model lgp performing T' local updates causes these heterogeneous local models diverge before the next aggregation. In addition, each parameter is (potentially) aggregated over different subset of local models in (3. These make existing convergence analysis intended for single-mode adaptive pruning 1I non-applicable to heterogeneous FL. The impact of local model divergence and the global aggregation of heterogeneous models must be characterized order to establish convergence.
The formulation proposed above captures heterogeneous FL with any model pruning or sub-model extraction strategies since the resulting masks my.. Vg, n change over time q and across clients n. It incorporates many model reduction strategies (such as pruning. sparsification, and sub-model extraction) into heterogeneous FL, allowing the convergence results to be broadly applicable. recovers many important FL algorithms recently proposed, including HeteroFL [3] that uses fixed masks my, PruneFL. 4 that periodically trains a full-size local model with mn.g 1, Prune-and- Grow [12] that can be viewed as single-client version, well as FedAvg [1] that employs full-size local models with m,,g = at all clients. Our analysis establishes general conditions for any heterogeneous FL with arbitrary online model reduction that may vary over communication rounds to converge to standard FL.
"While reduced local model has smaller number of parameters than the global model. adopt the notations in [4| 12 and use 6g @ my.. with an element wise product to denote the pruned local model or the extracted submodel only parameter corresponding to 1-value in the mask is accessible and trainable in the local model.

---

Our paper establishes convergence conditions in the general form, which apply to both static and dynamically changing masks. With dynamically changing masks, we denote the reduced model- s/networks as ygn,.t which means that the model structure (with its corresponding mask) can change between each round of communications and during each local training epoch, and can be different from other local clients. We show that as long as the dynamic heterogenous FL framework can be framed as the setting above, our convergence analysis this paper applics.
4.2 Notations and Assumptions
We make the following assumptions that are routinely employed in FL convergence analysis. In particular, Assumption is standard and common setting assuming Lipschitz continuous gradients. Assumption 2 follows from [2 (which is for a single-worker case) and implies the noise introduced by model reduction is bounded and quantified. This assumption is required for heterogeneous FL to converge to a stationary point of standard FL. Assumptions 3 and 4 are standard for FL convergence and assume the stochastic gradients be bounded and unbiased.
analysis following from [36. 37 & 9
Assumption 1. (Smoothness). Cost functions Fi,..., FN are all L-smooth: v0, Φ E Rd and any n,
we assume that there exists L > 0:
(0) (.)()))l S L110- +1|.
Assumption 2. (Model Reduction Noise). We assume that for some 82 10) and any q, the model reduction error is bounded by
00g 0g 3 mm < 1
(5)
Assumption 3. (Bounded Gradient). The expected squared norm of stochastic gradients is bounded uniformly, i.e., for constant G O and any n, n.q,t:
Beg [VV (0 (a S G.
(6)
Assumption 4. (Gradient Noise for IID data). Under IID data distribution, Vq, L, we assume gradient estimate with bounded variance:
Egg,,
- (F o²
4.3 Convergence Analysis
We now analyze the convergence of heterogeneous FL for general smooth cost functions. We begin with introducing new notion of minimum covering index, defined in this paper by
min (N((') 9.5
min
where Timin measures the minimum occurrence of the parameter in the local models in all rounds, considering (N is the number of heterogeneous local models containing the ith parameter. In- tuitively, if parameter is never included in any local models, it is impossible to update it. Thus conditions based on the covering index would be necessary for the convergence toward standard FL (with the same global model). All proofs for theorems and lemmas collected in the Appendix with a brief proof outline provided here.
Theorem 1. Under Assumptions 1-4 and for arbitrary musks satisfying m 2 1, when choosing y 1/(6LT) < 1/(TVQ heterogeneous FL converges to small neighborhood of a stationary point of standard FL as follows:
Go VQ
Vo
Ho
1o
E V
<
E 1
TVQ
Q
q=1
where Go = (Go)] Vo 6LNo2 (T Hg = NG/ and In 3I222N N are constants depending on the initial model parameters and the gradient noise.
We refer to 1 for all equations and derivations.
5

---

An obvious case here is that when I min 0, where there exists at least one parameter that is not covered by any of the local clients and all the client models can not cover the entire global model, we can consider the union of all local model parameters, the "largest common model" among them, as new equivalent global model 0 (which have smaller size than 0). Then, each parameter in is covered in at least one local model. Thus Theorem holds for 0 instead and the convergence is proven - stationary point of Ô rather than 0
Assumption 5. (Gradient Noise for non non-llD data). Let 9 w EnENYo VF V (0 Sn,)). Under non-llD data distribution, we assume Vi, 9, gradient estimate with bounded variance:
Eg Igm.t
V (0,,..))
s0²
Theorem 2. Under Assumptions 1-3 and 5, heterogeneous FL satisfying I min 2 L, when choosing Y 1/VTQ and y 1/LT),, heterogeneous FL converges a small neighborhood of stationary point of standard FL as follows:
Q
Q
G1 VTQ
Vo
lo
1
BIVF(00))
+
+
R
1011'
(9)
VQ
r
Q
where G1 = (0.) 6LKo
Proof outline. There are number of challenges in delivering main theorems. We begin the proof by analyzing the change of loss function in one round as the model goes from 8g to 0y+1. i.e., F(0g+1) F(O,). includes three major steps: reducing the global model to obtain heterogeneous local models 0g.n.0 = 0g @ mygn. training local models a distributed fashion to update fg,n,t and parameter aggregation update the global model 4-+1-
Due to the use of heterogeneous local models whose masks mg.n both vary over rounds and change for different workers, we first characterize the difference between local model 0 n. at any epoch t and global model 0, at the beginning of the current round. easy to see that this can be factorized into two parts: model reduction error ||0g...0 o 1/112 and local training |10 - O 0l. which will be analyzed in Lemma
Lemma 1. Under Assumplion and Assumption 3, for any q, we have:
T
N
Σ
B10 - 0,l1 = 2G
0/1
(10)
t=n==
We characterize the impact of heterogencous local models on global parameter updates. Specifically, we use an ideal local gradient F, (0,) as reference point and quantify the difference between aggregated local gradients and the ideal gradient. This will be presented in Lemma]
Lemma 2. Under Assumptions 1-3, for any g, we have:
K
1222TNG
128 +
Σ DENC)
VFO (B.,,,
r E
r
where we relax the inequality by choosing the smallest I min,,4 1 We also quantify the norm difference between a gradient and a stochastic gradient (with respect to the global update step) using the gradient noise assumptions, in Lemma
"To better illustrate scenario min 0 we will introduce an illustrative simplified example as follows: A global model =< 0,, 02, 0g > where there will be two local models 6, =< 01 > and 0, =< 0g >. Although I min. 0 regarding the global model 0, but for their largest common model. the union of 9, and 0, which is < 0,, 0s > will become the new conceptual global model 6, where I wwn regarding this conceptual global model. Thus the convergence still stands, but it will converge to stationary point of FL with a different global model.

---

Since IID and non- IID data distributions in our model differ in the gradient noise assumption (i.e., Assumption 4 and Assumption 5), we present unified proof for both cases. We will explicitly state III) and non-III data distributions only if the two cases require different treatments (when the gradient noise assumptions are needed). Otherwise, the derivations and proofs are identical for both cases.
Lemma 3. For IID data distribution under Assumptions 4, for any we have:
K
T
No² T(Tx)2
E
Σ
(
nEN!
For non-IID data distribution under Assumplion 5, for any we have:
K
Ko²
Σ DEN
(f - VF (0mmo-))) T
Finally, under assumption 1, we have F(0++1) - F(O,) S (V,(),), 0g+1 - -0g) +0)+5 110 0 and use the preceding lemmas obtain two upperbounds for the two terms. Combining these results we prove the desired convergence result in theorem and theorem 2
Theorem 1 shows the convergence of heterogenous FL to neighborhood of stationary point of standard FL albeit a small optimality gap due to model reduction noise, as long as I min 2 1. The result is bit surprising since I min 2 only requires each parameter to be included in at least one local model which is obviously necessary for all parameters to be updated during training. But we show that this is also sufficient condition for convergence. Moreover, we also establish for arbitrary model reduction strategies satisfying the condition. When the cost function is strongly convex (e.g., for softmax classifier, logistic regression, and linear regression with no-normalization, the stationary point becomes the global optimum. Thus, Theorem shows convergence to small neighborhood of the global optimum of standard FL for strongly convex cost functions.
convergence rate of O 7
Interpreting and Applying the Unified Framework
Discussion on the Impact of model reduction noise. In Assumption assume the model reduc- tion noise is relatively small and bounded with respect to the global model: ||0,, 0g mg 1| s 8² 10, This is satisfied in practice since most pruning strategies tend to focus on eliminating weights/neurons that are insignificant, therefore keeping 52 indeed small. We note that similar observations are made on the convergence of single-model adaptive pruning [1], but the analysis does not extend FL problems where the fundamental challenge comes from local updates causing heterogeneous local models to diverge before the next global aggregation. We note that for hetero-
geneous FL., reducing model will incur an optimality gap 82 q E B||00]| in our convergence analysis, which is proportional to 8² and the average model norm (averaged over Q). It implies that more aggressive model reduction in heterogeneous FL may lead larger error, deviating from standard FL at speed quantified by 8². We note that this error is affected by both d² and I min-
Discussion on the Impact of minimum covering index l The minimum number of occurrences of any parameter in the local models is another key factor in deciding convergence in heterogeneous FL. As I min increases. both constants Go, Vo. and the optimality gap decrease. Recall that our analysis shows the convergence of all parameters in 0, with respect to a stationary point of standard FL (rather than for subset of parameters to a random point). The more times parameter is covered by local models, the sooner it gets updated and convergences to the desired target. This is quantified in analysis by showing that the optimality gap due to model reduction noise decreases at the rate of T min-
Connections between model reduction noise and minimum covering index. In this paper, we introduced the concept of minimum coverage index for the first time, where we show that only model compression alone is not enough to allow unified convergence analysis/framework for
7

---

heterogeneous federated learning. The minimum coverage index, together with pruning/compression noises, determines convergence in heterogeneous FL. Our results show that heterogeneous FL algorithms satisfying certain sufficient conditions can indeed converge to neighborhood of stationary point of standard FI.. This a stronger result as shows convergence to standard FI., rather than simply converging somewhere. A minimum coverage index of T min 0 means that the model would never updated, which is meaningless even still converges.
Discussion for non-lID case. We note that Assumption S is required to show convergence with respect standard FL and general convergence may reply on weaker conditions. We also notice that I min no longer plays a role in the optimality gap. This is because the stochastic gradients computed by different clients in Mg now based different datasets and jointly provide unbiased estimate, no longer resulting in smaller statistical noise.
Applying the main theoretical findings. Theorem 1 also inspires new design criteria for designing adaptive model-reducing strategies in heterogeneous FL. Since the optimality gap is affected by both model model-reduction noise 8 and minimum covering index I min, may prefer strategies with small 8² and large I min. in order to minimize the optimality gap to standard FL.
The example shown in Figure Tillustrates alternative model reduction strategies in heterogeneous FL for N 10 clients. Suppose all low-capacities clients are using the reduced-size model by pruning greedily, which covers the same region of the global model, scenarios like this will only produce a maximum min = 4; however when applying low-capacities local clients with models covering different regions of the global model, I min can be increased, as example show how to design local models so I min is increased to without increasing any computation and communication cost. The optimal strategy corresponds to lower noise 52 while reaching higher covering index. Using these insights, We present numerical examples with optimized designs in Section
6 Experiments
6.1 Experiment settings
In this section, we evaluate heterogeneous FL with different model reduction strategies and aim to validate our theory. We focus on two key points in our experiments: (i) whether heterogencous FL will converge with different local models and (ii) the impacts of key factors the FL performances including minimum coverage index I min and model-reduction noise 52.
0.45
FullMdd
Medel
0.43
Pruting Medium
0.0
Pruning Medium
Pruning Medlum-Gg
Suonct Med um
0.35
Medium
Submeb-Hed ump
0.30
Clozall
9.4
020
815
0.2
20
40
100
40
Communiction Round
Communication
Round
(a) MLP trained MNIST with IID data
(b) MLP trained MNIST with non-IID data
Figure 2: Selected experimental results for MNIST with IID (a) and Non-lID (b) with high data heterogeneity data on medium model reduction level. "Opt" stands for optimized local model distribution covering more regions for higher I min, others do pruning greedily. As the shallow MLP is already at a small size, applying medium level of model reduction will bring high model reduction loss for subnet extraction method.
Datasets and Models. We examine the theoretical results on the following three commonly-used image classification datasets: MNIST 38 with shallow multilayer perception (MLP), CIFAR-10 with Wide ResNer28x2 39). and CIFAR100 40 with Wide ResNer28x8 [9] The first setting where using MI.P models closer to the theoretical assumptions and settings, and the latter two settings are closer to the woal-world application scenarios. We prepare N 100 workers with IID and non-IID

---

Model
MNIST
CIFAR-TO
CIFARTOD
Reduction
Model Setting
Timis
Non. ITD
Non HD
Non-
IDD
Level
L=5
L=2
L=5
L=2
L=50
L=20
TullMrdel
Tomogenous Full
10
98.08
97.70
93.59
70.63
65.12
61.08
67.34
66.74
64.38
Pruning Greedy
98.18
97.60
93.15
72,66
62.49
57.17
67.41
65.67
65.06
Low
Pruning Optiiseed
98.53
98.25
95.85
76.26
66.25
59.98
67.47
66.56
67.47
Model
Static Subnet Subtraction
97.62
95.12
92.33
73.20
61.25
56.09
66.60
65.24
65.79
Reduction
Subeet Subtraction Optimised
97.76
94.41
93.60
73.78
64.17
58.09
67.81
66.66
67.23
Homogenous-Laage
97.52
96.08
93.23
69.05
63.72
57.42
66.81
65.57
63.90
Pruning-Groodd
97.51
95.05
91.86
66.85
60.93
56.98
52.92
45.88
45.68
Medium
Pruning- meiinn--pimieed
98.39
98.02
71.43
66.94
56.93
55.32
46.81
Model
Static Subnet Subtraction
95.56
92.31
92.05
61.87
58.08
46.03
50.59
44.22
45.25
Reduction
Subnet Subtraction Optimised
97.96
94.05
93.36
63,96
$2.95
Homogenous-Modee
10
97.05
92.71
90.82
59.21
$7.61
53.43
52.19
36.08
34,06
Pruning Cireedy
86.83
67.35
56.75
39.29
26.14
25.97
High Model Reduction
Pruning-Optie Siaiing-Opimised
95.32
91.88
81.66
67.74
$7.33
27.97
40.78
29.63
26.63
Static Subnet Subtraction
95.88
81 64
71.64
68.78
56.88
30.61
41.18
27.55
26.23
Suhnet Suhtraction - Optimised
94.41
90.70
85.82
69.15
57. 98
33.46
37.42
24.98
22.40
Homogenous Small
93.79
85.66
75.23
66.87
51.90
30.61
37.40
27.16
26.20
Table 1: Global model accuracy comparison between baselines and their optimized versions suggested
by our theory. We observe improved performance on almost all optimized results, especially on subnet-extraction -based methods on high model reduction levels.
data with participation ratio 0.1 which will include 10 random active clients per communication round. Please see the appendix for other experiment details.
Data Heterogeneity. We follow previous works [ S to model non-lID data distribution by limiting the maximum number of labels L as each client is accessing. We consider two levels of data heterogeneity: for MNIST and CIFAR-10 10 consider T. low data heterogeneity as used in [9. For CIFAR-100 we consider T, = 20 as high data heterogeneity and L. 50 as low data heterogeneity. This will correspond to an approximate setting of Dirk (a) with a = 0.1 for MNIST, a = 0.1 for CIFAR-10, and a = 0.5 for CIFAR-100 respectively in Drichhet-diistrbutton--aas data heterogeneity.
high data heterogeneity and T. 5 as
Model Heterogeneity, In our evaluation, we consider the following client model reduction levels: 3 = {1, 1: 1} for MLP and 3 {1, 2: 1: } for ResNet, where each fraction represents its model capacity ratio to the largest client model (full model). To generate these client models, for MLP we reduce the number of nodes in each hidden layer, for WResNet reduce the number of kernels in convolution layers while keeping the nodes in the output layer as the original.
Baselines and Testcase Notations. As this experiment is mainly to validate the proposed theory and gather empirical findings, we choose the standard federated learning algorithm, i.e. FedAvg [. with several different heterogeneous FL model settings. Since this experiment section is to verify the impact our proposed theory rather than chasing a SOTA accuracy, no further tuning or tricks for training were used to demonstrate the impacts of key factors from the main theorems.
We consider 3 levels of model reduction through pruning and static subnet Extraction: which will reduce the model by only keeping the largest or leading 3 percentile of the parameters per layer. We show 4 homogeneous settings with the full model and the models with levels of model reduction, each with at least one full model so that m'mn > 1 is achieved. Finally, we consider manually increasing the minimum coverage index and present one possible case denoted as "optimized", by applying local models covering different regions of the global model as illustrated in Fig
Note that even when given specific model reduction level and the minimum coverage index, there could be infinite combinations of local model reduction solutions; at the same time model reduction will inevitably lead to an increased model reduction noise, by conducting only weights pruning will bring the lowest model reduction noise for a certain model reduction level. How to manage the trade-off between increasing I mán while keeping 8² low is non-tre non-trivial and will be left for future works on designing effective model reduction policies for heterogeneous FL.
6.2 Numerical Results and Further Discussion
We summarize the testing results with one optimized version for comparison Table We plot the training results of Heterogeneous FL with IID and non-III data on the MNIST dataset in Figure 2a and Figure since the model and its reduction are closer to the theoretical setup and its assumptions. We only present training results of medium-level model reduction (where deploy 4 clients with

---

fullmodel and 6 clients with models) in the figure at the main paper due to page limit and simplicity, We leave further details and more results in the appendix.
General Results. Overall, we observe improved performance on almost all optimized results, especially subnet-extraationnbaase methods on high model reduction levels. In most cases, performances will be lower compared to the global model due to model-reduction noise.
Impact of model-reduction noise. As our analysis suggests, one key factor affecting convergence model-reduction noise 8². When a model is reduced, inevitably the model-reduction noise 8² will affect convergence and model accuracy. Yet, our analysis shows that increasing local epochs or communication rounds cannot mitigate such noise. To minimize the convergence gap in the upperbounds, it is necessary to design model reduction strategies in heterogeneous FL with respect to both model-reduction noise and minimum coverage index, e.g., by considering a joint objective of preserving large parameters while sufficiently covering all parameters.
Impact of minimum coverage index. Our theory suggests that for given model reduction noise, the minimum coverage index I' min is inversely proportional to the convergence gap as the bound in Theorem I indicates. Then for a given model reduction level, a model reduction strategy in heterogeneous FL with higher minimum coverage index may result in better training performance. Note that existing heterogeneous FL algorithms with pruning often focus on removing the small model parameters that are believed to have an insignificant impact on model performance, while being oblivious to the coverage of parameters in pruned local models, and the model ceneell-xttaction-beee method will only keep the leading subnet. Our analysis in this paper highlights this important design for model reduction strategies in heterogeneous FL that parameter coverages matter.
More discussions and empirical findings. For the trade-off between minimum coverage index and model reduction noise, it's nearly impossible to fix one and investigate the impact of the other. In addition, we found: (1) Large models hold more potential to be reduced while maintaining generally acceptable accuracy. (2) Smaller models tend to be affected more by 5² while the larger model is more influenced by I min. which suggests that it's more suitable to apply pruning small networks and apply subnet extraction on large networks.
Limitations In this work we consider full device participation, where arbitrary partial participation scenario not considered. Also, the optimal design of model extraction maintaining balance between a low 8² and a high mimn is highly non-trivial which would be left for future work.
7 Conclusion
In this paper, we present a unifying framework and establish sufficient conditions for FL with dynamic heterogeneous client-dependent local models to converge to a small neighborhood of a stationary point of standard FL. The optimality gap is characterized and depends on model reduction noise and new concept of minimum coverage index. The result recovers a number of state-of-the-art FL algorithms as special cases. It also provides new insights on designing optimized model reduction strategies in heterogeneous FL, with respect to both minimum coverage index T min and model reduction noise 52. We empirically demonstrated the correctness of the theory and the design insights. Our work contributes to a deeper theoretical comprehension of heterogeneous FL with adaptive local model reduction and offers valuable insights for the development of new FL algorithms in future research.
References
[1] Brendan McMahan, Eider Moore. Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. communication-efficiee learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1288 1282. PMLR, 2017.
[2] Wei Yang Bryan Lim, Nguyen Cong Luong, Dinh Thai Hoang, Yutao Jiao, Ying-Chang Liang, Qiang Yang, Dusit Niyato, and Chunyan Miao. Federated learning mobile edge networks: A comprehensive survey. IEEE Communications Surveys & Tutorials, 22(3):203-2063, 2020.
[3 Enmao Diao, Jie Ding, and Vahid Tarokh. Heterofl: Computation and communication efficient federated learning for heterogeneous clients, 2021.
10

---

[4] Yuang Jiang. Shiqiang Wang, Victor Valls. Bong Jun Ko, Wei-Han Lee. Kin K. Leung. and Leandros Tassiulas. Model pruning enables efficient federated learning on edge devices, 2020.
[5] Samiul Alam, Luyang Liu, Ming Yan, and Mi Zhang. Fedrolex: Model hettroogetoo federated learning with rolling sub- uub-model extraction. arXiv preprint arXiv:2212.01548, 2022.
[6] Jianyu Wang and Gauri Joshi. Cooperative sgd: unified framework for the design and analysis of conmunication-effiieee sgd algorithms. arXiv preprint 18X8::8000007770 2018
[7] Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp. Dzmitry Huba, Alex Ingerman. Vladimir Ivanov, Chloe Kiddon, Jakub Konečný. Stefano Mazzocchi, H Brendan McMahan, et al. Towards federated learning at scale: System design. arXiv preprint 1xXiv:192.001445 2019.
[8] Hao Yu, Sen Yang, and Shenghuo Zhu, Parallel restarted sgd with faster convergence and less communica- tion: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 5693-5700, 2019.
[9] Xiang Li. Kaixuan Huang. Wenhao Yang. Shusen Wang. and Zhihua Zhang. On the convergence of fedavg on non-iid data, 2020.
[10] Hanhan Zhou, Tian Lan, Guru Prasadh Venkataramani, Wenbo Ding. Federated learning with online adaptive heterogeneous local models. Workshop on Federated Learning: Recent Advances and New Challenges (in Conjunction with NewrlPS 2022), 2022.
[11] Tao Lin, Sebastian U Stich, Luis Barba, Daniil Dmitriev, and Martin Jaggi. Dynamic model pruning with feedback. arXiv preprint arXiv:2006.0722 07253, 2020.
[12] Xiaolong Ma, Minghai Qin, Fei Sun, Zejiang Hou, Kun Yuan, Yi Xu, Yanzhi Wang. Yen-Kuang Chen, Rong Jin, and Yuan Xie. Effective model sparsification by scheduled grow-and prune methods, arXiv preprint 2xXiv:2/06. 09857, 2021.
[13] Blake Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, and Nathan Srebro. Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. arXiv preprint arXiv: 10222. 2018.
[14] Shiqiang Wang and Mingyue Ji. A unified analysis of federated learning with arbitrary client participation. arXiv preprint arXiv:2205. 13648, 2022.
[15] Shiqiang Wang, Tiffany Tuor, Theodoros Salonidis, Kin K. Leung, Christian Makaya, Ting He, and Kevin Chan. Adaptive federated learning in resource constrained edge computing systems, 2019.
[16] Jianyu Wang and Gauri Joshi. Adaptive communication strategies to achieve the best error-runtime trade-off' in local-update sgd, 2019.
[17] Sai Praneeth Karimireddy, Satyen Kale, Mchryar Mohri, Sashank Reddi, Scbastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In Inter- national Conference on Machine Learning, pages 5132-5143. PMLR, 2020.
[18] Bing Luo. Xiang Li. Shiqiang Wang, Jianwei Huang, and Leandros Tassiulas Cost-effective federated learning design. In IEEE INFOCOM 2021 IEEE Conference on Computer Communications, pages 1-10, 2021.
[19] Runxue Bao, Xidong Wu, Wenhan Xian, and Heng Huang. Doubly sparse asynchronous learning for stochastic composite optimization. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI, pages 1916-1922, 2022.
[20] Xidong Wu, Feihu Huang, Hu Zhengmian, and Huang Heng. Faster adaptive federated learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2023.
[21] Jakub Konečný, Brendan McMahan, Felix Yu. Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint 1111v.6110005492, 2016.
[22] Yuzhu Mao, Zihao Zhao, Guangfeng Yan, Yang Liu, Tian Lan, Linqi Song, and Wenbo Ding. Communica- tion efficient federated learning with adaptive quantization, 2021.
[23] Dezhong Yao, Wanning Pan, Yao Wan, Hai Jin, and Lichao Sun. Fedhm: Efficient federated learning for heterogeneous models via lonk factorization, 2021.

---

[24] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication- efficient sgd via gradient quantization and encoding. Advances in Neural Information Processing Systems, 30:1709-1720, 2017.
[25] Nikita Ivkin, Daniel Rothchild, Enayat Ullah, Vladimir Braverman, lon Stoica, and Raman Arora. Communication-effcei distributed sgd with sketching. arXiv preprint (1XXiv:903304443000 2019.
[26] Chandra Thapa, Mahawaga Arachchige Pathum Chamikara, Seyit Camtepe, and Lichao Sun. Splitfed: When federated learning meets split learning, arXiv preprint arXiv:2004. 12088, 2020.
[27] Pengchao Han, Shiqiang Wang, and Kin K Leung. Adaptive gradient sparsification for efficient federated learning: An online learning approach. In 2020 IEEE 40th International Conference on Distributed Computing Systems (ICDCS), pages 300-310. IEEE, 2020.
[28] Zachary Charles, Kallista Bonawitz, Stanislav Chiknavaryan, Brendan McMahan, al. Federated select: A primitive for communication-ant memory-efficienn federated learning, arXiv preprint (xXXv:2208.004333
2022.
[29] Sebastian Caldas, Jakub Konečny, H Brendan McMahan, and Ameet Talwalkar, Expanding the reach of federated learning by reducing client resource requirements. arXiv preprint arXiv:1812.0722 2018.
[30] Zirui Xu, Zhao Yang. Jinjun Xiong, Janlei Yang. and Xiang Chen. Elfish: Resource-aware federated learning on heterogeneous edge devices. Ratio, 2(rl) 2019.
[31] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50 60, 2020.
[32] Ang Li, Jingwei Sun, Xiao Zeng, Mi Zhang, Hai Li, and Yiran Chen. Fedmask: Joint computation and communication--ffiiieet personalized federated learning via heterogeneous masking. In Proceedings of the 19th ACM Conference Embedded Networked Sensor Systems, pages 42 55, 2021.
[33] Samuel Horvath, Stefanos Laskaridis, Mario Almeida, Ilias Leontiadis. Stylianos Venieris, and Nicholas Lane. Fjord: Fair and accurate federated learning under heterogeneous targets with ordered dropout. Advances in Neural Information Processing Systems, 128766 12889. 2021.
[34] Ang Li. Jingwei Sun, Pengeheng Li, Yu Pu, Hai Li, and Yiran Chen. Hermes: efficient federated learning framework for heterogeneous mobile clients. Proceedings of the 27th Annual International Conference on Mobile Computing and Networking, pages 420 437, 2021.
[35] Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state neural network pruning?, 2020.
[36] Yuchen Zhang, John Duchi, and Martin Wainwright. Communication algorithms for statistical optimization. The Journal of Machine Learning Research, 14(1):3321-3363 2013.
[37] Sebastian U Stich. Local sgd converges fast and communicates little, arXiv preprint arXiv:1805.0976: 2018.
[38] Yann LeCun. Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 11:227822222244 1998.
[39] Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint arXiv: arXiv: 1605.00766. 2016.
[40] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers features from tiny images. 2009.
12


Reviews:
[{"review_id": "9RALUChRJA", "reviewer": "Reviewer_9LDk", "summary": "In this work, the authors provide a general theoretical framework to analyze the convergence of Federated training schemes conducted over local models of heterogeneous network structures. Such structures can usually be obtained through different model reduction methods, such as model pruning/sparsification or model extraction. The proposed framework introduces the minimum covering index concept to conduct the analysis, representing the number of local models concurrently updating the same set of parameter indices. The paper is well written, but a couple of clarifications are necessary.\n", "questions": "From my understanding, your framework seems to consider reduced model structures when these structures are obtained when the global model is reduced (pruned). Will your analysis hold even in the case of local model reduction, i.e., client-side reduction, not server-side? Will the model reduction noise (assumption 2) and bounded gradient (assumption 3) still hold? Your analysis shows that local model training is performed over the entire network. How would that affect your analysis if you were to enforce training over the parameters of the reduced model (enforce masks during training)?\n\nThe proof outline does not clarify how the mask is constructed. Is it always static, or can it be dynamically changing? In PruneFL, masks can periodically increase to accommodate model regrowth. Similarly, FedDST[1] performs local model regrowth with a fixed pruning degree during model communication. Analogously, FedSparsify[2] performs progressive model reduction (progressive sparsification), where the global or local model is progressively pruned. Can your framework capture such dynamic mask construction? Please expand your related work and discuss whether your framework can also accommodate such dynamic pruning approaches. \n\nThe model settings through which the model reduction level is obtained in Table 1 are not clear. Can you please elaborate on what are the methods you used to perform the greedy pruning, pruning-optimized, static subnet subtraction, and homogeneous methods? Did you use structured or unstructured pruning? Random weight magnitude or based on magnitude? Can you report the noise reduction (percentage-wise) in the models learned at every model reduction level? Such an analysis could lead to key insights with respect to the index coverage vs. noise reduction tradeoff.\n\nCan your analysis be extended to activations and/or neuron pruning as part of your future work? Also, have you considered extending your framework for asynchronous federated settings?\n\n[1] Federated Dynamic Sparse Training: Computing Less, Communicating Less, Yet Learning Better Sameer Bibikar, Haris Vikalo, Zhangyang Wang, Xiaohan Chen. https://ojs.aaai.org/index.php/AAAI/article/view/20555/20314\n\n[2] Federated Progressive Sparsification (Purge-Merge-Tune)+. Dimitris Stripelis, Umang Gupta, Greg Ver Steeg, Jose Luis Ambite. https://openreview.net/pdf?id=GLQqPTRrQMx", "limitations": "No.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Very well-written paper with clear objectives and contributions.\n\nGeneralized framework to encapsulate different model reduction algorithms.\n\nThe introduction of the minimum coverage index concept and its interplay with model reduction noise can lead to very promising and interesting insights.", "weaknesses": "Further elaboration is needed on terms and concepts used during the theoretical analysis.\n\nEmpirical evaluation needs improvement.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review!\n\n> Q1. From my understanding, your framework seems to consider reduced model structures when these structures are obtained when the global model is reduced (pruned). Will your analysis hold even in the case of local model reduction ... How would that affect your analysis if you were to enforce training over the parameters of the reduced model?\n\nWe would like to clarify that our framework indeed considers local model training over the reduced networks (i.e., the masks are always enforced during the training of local models). It is shown in Eq.(2) at line 131 and the equation at line 134 how the local models are obtained by pruning and then trained as reduced networks. A pseudocode example is provided in Algorithm 1 (page 1) in the appendix, showing the training of local models with fixed masks and their aggregation to the global model. If we understand the comment correctly, this is the client-side reduction and reduced local model training, as the reviewer pointed out. This problem formulation makes convergence difficult to analyze, which is the main contribution of this paper. Our analysis shows that under Assumptions 2  and 3 (both of which relate to reduced local models), convergence (to standard FL) will stand for as long as certain conditions are met, that is, every parameter is included and updated at least once throughout the training, which is the key idea of this paper: every parameter matters. Further, our experiment section results are generated in a way that local model training is done on reduced-size models. \n\n> Q2. The proof outline does not clarify how the mask is constructed. Is it always static, or can it be dynamically changing? .... Can your framework capture such dynamic mask construction? Please expand your related work and discuss whether your framework can also accommodate such dynamic pruning approaches.\n\nOur paper establishes convergence conditions in the general form, which apply to both static and dynamically changing masks. With dynamically changing masks, we denote the reduced models/networks as  $\\theta_{q,n,t}$, which means that the model structure (with its corresponding mask) can change between each round of communications $q$ and during each local training epoch $t$, and can be different from other local clients. We show that as long as the dynamic heterogenous FL framework can be framed as the setting above, our convergence analysis in this paper applies. Thus, our results establish the general convergence condition covering cases of static model pruning, dynamic model reduction, and grow-and-prune type of training, e.g. [1-4]. However, indeed the current description of mask generation can be improved by expanding to more related works for better understanding. We will make such changes in the revision as the reviewer suggested.\n\n> Q3. The model settings through which the model reduction level is obtained in Table 1 are not clear. Can you please elaborate on what are the methods you used to perform the greedy pruning, pruning-optimized, static subnet subtraction, and homogeneous methods?  .....  Such an analysis could lead to key insights with respect to the index coverage vs. noise reduction tradeoff.\n\nDue to page limitations, we summarized the key findings in the main paper and presented detailed settings of each model reduction method in the appendix. Specifically, we listed how local models are generated (how we define greedy pruning, pruning-optimized, static subnet subtraction, and how masks are generated, etc) and their respective coverage index and each of their reduction levels in percentage-wise (which leads to the initial model reduction noise). \n\nFor instance, we explained that \"Pruning-Optimised\" works at a low model reduction level and is made up with 10 local models consisting of 4 full-size models, 6 reduced-size models at 75% size of the global model that covers 3 different regions (with each setting applied to 2 models) as  {$S_{1},S_{3},S_{4}$},  {$S_{1},S_{2},S_{4}$},  {$S_{1},S_{2},S_{3}$}, where $S_1$ represents the region consists of the top 25% largest-magnitude parameters and $S_4$ the smallest, and   {$S_{1},S_{2},S_{3},S_{4} $} as the full model. We considered both structured and unstructured pruning including unstructured weights pruning, structured neuron pruning, and leading subnet extraction. We will add a brief summary to further clarify this in the revised paper. \n\n> Q4. Can your analysis be extended to activations and/or neuron pruning as part of your future work? Have you considered extending your framework for asynchronous federated settings?\n\nThe current setting of model reduction considers both structured and unstructured model reduction, which includes neuron pruning. In fact, in the experiment section and appendix, we have results for neuron pruning. In Table 1 of the main paper, we used “pruning” to demonstrate unstructured pruning and “static subnet subtraction” to demonstrate structured neuron pruning (continuous neuron pruning), and due to page limits, we have in the appendix results for (unstructured) neuron pruning in table 2 and table 3 and their illustrations in Figure 1.\n\nWe agree extending the framework to asynchronous federated settings would be an interesting direction for future work. We will include some discussions in the revised paper.\n\n[1] Bibikar, Sameer, et al. \"Federated dynamic sparse training: Computing less, communicating less, yet learning better.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 36. No. 6. 2022.\n\n[2]  Stripelis, Dimitris, et al. \"Federated progressive sparsification (purge, merge, tune)+.\" arXiv preprint arXiv:2204.12430 (2022).\n\n[3] Tao Lin, et al. \"Dynamic Model Pruning with Feedback.\" International Conference on Learning Representations. 2020.\n\n[4] Alam, Samiul, et al. \"Fedrolex: Model-heterogeneous federated learning with rolling sub-model extraction.\" Advances in Neural Information Processing Systems 35 (2022): 29677-29690."}, {"review_id": "KsBanO0P4s", "reviewer": "Reviewer_oYBg", "summary": "This paper focuses on the cross-device federated learning setting. The authors introduce a general theoretical framework for analyzing FedAvg with masks on local pruned models. This analysis is particularly valuable in establishing the convergence of federated schemes when the global model is distributed across multiple edge clients. Furthermore, the paper includes numerical illustrations of their algorithm, providing practical insights on its performance.", "questions": "The article is interesting, could you address the following points so that I can raise my score?\n\n* It is unclear whether $\\Gamma_q^{(i)}$ is defined or if it refers to $N_{q}^{(i)}$ mentioned on line 177. Similarly, does $\\Gamma^*$ denote the same quantity as $\\Gamma_{min}$?\n\n* The proposed update in the equation on line 134 is not exactly the same implemented in the \"Update.py\" script. I think the mask is not applied to the gradient.\n\n* I haven't looked at the supplementary paper, but it seems to me that an expectation is missing on Eq.(20).\n\n* Is it necessary to use $\\delta<1$ in assumption 2? Since I don't see $1/(1-\\delta)$ in your bounds, I wonder if this constraint is useful.\n\n**Requested Changes:**\n\n* Line 59: \"will it converge\" inside Figure 1 legend.\n\n* Line 75: client is denoted by $i$, then latter by $n$ at the end of page 2.\n\n* Line 95: \"models are to share\".\n\n* Lines 108: \"works like Hermes can\".\n\n* Definition of $I_0$ in Theorem 1 and Theorem 2 is different, there is maybe an additional $\\delta^2$.\n\n* Some punctuation is missing, e.g., Eq. (9).\n\n* Conclusion seems little heavy.", "limitations": "The authors did not address the potential negative societal implications of their research, but this does not seem critical for this particular theoretical and numerical study.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is well-written and easy to understand, but with few points that might be improved (see \"Questions\" part).\n\n* The paper conducts a thorough theoretical investigation on federated learning with reduced-size models. Specifically, the authors provide novel tools to study the convergence of FL pruned models.", "weaknesses": "* Although interesting, some parts may seem to have been rushed. For example, assumptions and lemmas should be referred with ref{}. Further, I also spotted a few errors on the supplement, even though I haven't read the supplementary in detail. It's important to review and correct these typos.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and for confirming the contributions of our paper. We provide clarification to your questions and concerns as below.\n\n> Q1. It is unclear whether $ \\Gamma_q^{(i)}$  is defined or if it refers to $N_{q}^{(i)}$  mentioned on line 177. Similarly, does $\\Gamma^*$  denote the same quantity as $\\Gamma_{min}$?\n\n* Yes, $ \\Gamma_q^{(i)}$ is defined according to Eq(8) on line 177. Essentially $\\Gamma^*$ and $\\Gamma_{min}$ are the same thing. $\\Gamma_{min}$  is introduced as a main concept of the paper, and  $\\Gamma^*$ is used during the derivation for simplicity. We will clarify this in the revision.\n\n> Q2. The proposed update in the equation on line 134 is not exactly the same implemented in the \"Update.py\" script. I think the mask is not applied to the gradient.\n\n* Thanks for checking our code implementation! In this proof-of-concept experiment, we did not apply masks to the gradients, as this would cause an error if we directly modify the gradients since PyTorch autograd framework is responsible for handling gradients. Instead, for each batch of training, we directly apply the mask to the weights and biases before calculating the loss and after the back-propagation (e.g. the use of “get_sub_paras” helper function at Line 22 in main_fed_20N_AVGALL.py). This is equivalent to applying the mask to the gradients and has been used as a workaround in previous work for more easily obtaining proof-of-concept implementations.\n\n> Q3. I haven't looked at the supplementary paper, but it seems to me that an expectation is missing on Eq.(20).\n\n* Thanks for examining the appendix section and pointing this out, indeed there should be an expectation sign in Eq.(20). We have carefully proofread the supplementary document again and fixed the typos.\n\n> Q4. Is it necessary to use $\\delta<1$  in assumption 2? Since I don't see  $1/(1-\\delta)$ in your bounds, I wonder if this constraint is useful.\n\n* It is necessary and useful to have this condition. In fact, $\\delta<1$ holds by definition and directly follows from Assumption 2. Since the local model is extracted from the global model, it has to be smaller than the global model (as some parameters are pruned). According to Eq.(11) to quantify the difference/noise resulting from applying a mask, $\\delta$ must be smaller than 1 by definition. That’s why we listed it in the assumption. We will add a footnote to clarify this in the revised paper. \n\n> Definition of $I_0$  in Theorem 1 and Theorem 2 is different, there is maybe an additional $\\delta^2$\n\n* Thanks for pointing this typo out. The definition of $I_0$ in Theorem 2 should be exactly the same as that in Theorem 1 (thus the additional $\\delta^2$ is absorbed into $I_0$ in Theorem 2 as well). This is a type introduced when we were trying to simplify the auxiliary variables in both theorems. Full equations and their derivations are presented in the appendix.\n\n\n> Requested Changes: \nSome punctuation is missing, e.g., Eq. (9).\nLine 59: \"will it converge\" inside Figure 1 legend.\nLine 75: client is denoted by $i$, then latter by $n$  at the end of page 2.\nLine 95: \"models are to share\".\nLines 108: \"works like Hermes can\". \nConclusion seems little heavy.\n* Thanks for pointing out the typos, grammar, format issues, and writing suggestions, they will be addressed in the revision.\n\n\n\n"}, {"review_id": "VHlHVJRYz6", "reviewer": "Reviewer_mRuV", "summary": "This paper studies federated learning with heterogeneous client models and non-iid client data. By assuming that the client models are pruned versions of a common global model and using the notion of minimum covering index, the paper provides the convergence of FedAvg under client model pruning. Theoretical results show that pruning techniques that more evenly update the parameters and result in smaller model distortion are preferable to aggressive pruning. Such result is also verified through the numerical results on MNIST and Cifar-10, and Cifar-100 datasets.\n", "questions": "Please address the above weaknesses.", "limitations": "The authors have discussed the limitation of the paper, that partial client participation is not considered, and how the theoretical result guides the design of an optimal model pruning strategy is also limited.\n\n", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Novelty: this paper provides a first convergence analysis to FedAvg with model pruning. The theoretical proof is sound and clear. \n\nClarity: the paper thoroughly discusses the convergence result in theorems 1 and 2 and verifies the results through numerical experiments.", "weaknesses": "1. Term $E\\Vert \\theta_q\\Vert^2$ in the bound. This term appears in all theorems and lemmas in the main paper. However, it is unclear how large this term can be. Neither theoretical discussion nor numerical justification of this term is provided. This undermines the strength of the theoretical results.\n\n2. The connection between the theorem to the general convergence result of FedAvg under the same assumption. When $\\delta = 0, \\Gamma_{min} = T$, the convergence should recover the rate of standard FedAvg. However, such a discussion is missing, weakening the paper's clarity.\n\n3. The connection between the proof of pruning and lossy compression. Assumption 2 takes the standard assumption of model compression in compressed FL (e.g., [19, 21, 22]). Yet there is a critical difference in the minimum covering index. The connection and difference between the proof technique should be discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the constructive comments. We will follow these helpful comments in our revised version. Following are our responses to your questions and concerns.\n\n> Q1. Term $E\\Vert \\theta_q\\Vert^2$  in the bound. This term appears in all theorems and lemmas in the main paper. However, it is unclear how large this term can be. Neither theoretical discussion nor numerical justification of this term is provided. This undermines the strength of the theoretical results.\n\n* Indeed it is hard to directly quantify the term  $E\\Vert \\theta_q\\Vert^2$, since it depends on the exact FL problem setup. We note that this term $E\\Vert \\theta_q\\Vert^2$ should be examined together with its coefficients in the convergence bound, i.e., $\\frac{\\delta^2}{\\Gamma_{min}} E\\Vert \\theta_q\\Vert^2$. In particular, considering the coefficient $\\delta^2$ together with $E\\Vert \\theta_q\\Vert^2$, we have $E\\Vert \\delta \\theta_q\\Vert^2$, which relates to the pruning noise introduced in Assumption 2 and is equivalent to the bounded model reduction noise, i.e., $\\|\\theta_{q}-\\theta_{q} \\odot m_{q,n}\\|^{2} \\leq \\delta^{2}\\|\\theta_{q}\\|^{2}$. We also note that it is common to have such a bounded model norms term in heterogeneous federated learning, such as [1][2]; or a similar term of $|w_1-w_*|^2 $  in works e.g. [3]. Our analysis shows that to reduce this term $\\frac{\\delta^2}{\\Gamma_{min}} E\\Vert \\theta_q\\Vert^2$, we can either increase $\\Gamma_{min}$ (by designing pruning strategies) or decrease mask noise $\\delta$ (by adjusting pruning level). We will add these discussions to the revised paper.\n\n\n* Although it is hard to directly tell how large this $E\\Vert \\theta_q\\Vert^2$ is, our evaluation results demonstrate how this term affects learning performance. For instance, in the main results (Table 1 in main paper) we can compare “Pruning-Greedy” and “Pruning-Optimised”: the former has a larger $E\\Vert \\theta_q\\Vert^2$ and the latter has a larger $\\Gamma_{min}$, and as a result the latter one comes with a lower loss and converges at a faster convergence rate. Similar results can be found in other cases in the main results (e.g. by comparing  “Pruning-Medium (Greedy)” and “Pruning-Medium-Optimised” in Fig2 (a,b)) and additional results in the appendix. \n\n\n\n\n> Q2. The connection between the theorem to the general convergence result of FedAvg under the same assumption. When $\\delta = 0, \\Gamma_{min} = T$, the convergence should recover the rate of standard FedAvg. However, such a discussion is missing, weakening the paper's clarity.\n\n* This is a good point.  While $\\delta = 0, \\Gamma_{min} = T$ reduces the system model to standard FedAvg, our proof approach here is quite different due to additional steps (i.e., Lemma 1,2,3 in appendix) that are required to bound the training of heterogeneous local models, their differences at the end of each round, and the impact on global aggregation. Thus, we may not exactly recover the same convergence result as FedAvg. Nevertheless, as shown in Theorems 1 and 2: “We prove that heterogeneous FL algorithms satisfying certain sufficient conditions can indeed converge to a neighborhood of a stationary point of standard FL (with a small optimality gap that is characterized in our analysis)”.  When $\\delta = 0, \\Gamma_{min} = T$, the radius of the error ball (i.e., the last term in the convergence bounds) indeed becomes zero, implying convergence to standard FedAvg. This discussion will be added to in the revised paper. \n\n\n> Q3. The connection between the proof of pruning and lossy compression. Assumption 2 takes the standard assumption of model compression in compressed FL (e.g., [19, 21, 22]). Yet there is a critical difference in the minimum covering index. The connection and difference between the proof technique should be discussed.\n\n* There are three key differences: (1) In this paper, we introduced the concept of minimum coverage index for the first time, where we show that only model compression alone is not enough to allow a unified convergence analysis/framework for heterogeneous federated learning. Minimum coverage index, together with pruning/compression noises, determines convergence in heterogeneous FL.  (2) Our results show that heterogeneous FL algorithms satisfying certain sufficient conditions can indeed converge to a neighborhood of a stationary point of standard FL. This is a stronger result as it shows convergence to standard FL, rather than simply conversing to somewhere. A minimum coverage index of $\\Gamma_{min}=0$ means that the model would never be updated, which is meaningless even if it still converges. (3) In terms of the proof techniques, additional steps (i.e., Lemma 1,2,3 in appendix) are required to bound the training of heterogeneous local models, quantify their differences at the end of each round, and analyze the impact on global aggregation. These make the proof much more complicated than convergence analysis of standard FL.  We will add more discussions on these in the revised paper.\n\n\n[1] Jiang, Zhida, et al. \"Fedmp: Federated learning through adaptive model pruning in heterogeneous edge computing.\" 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 2022.\n\n[2] Xiaolong Ma, et al. \"Effective Model Sparsification by Scheduled Grow-and-Prune Methods.\" International Conference on Learning Representations. 2022.\n\n[3]Xiang Li, et al. \"On the Convergence of FedAvg on Non-IID Data.\" International Conference on Learning Representations. 2020.\n"}, {"review_id": "heVa5J9Xt9", "reviewer": "Reviewer_dR1n", "summary": "This work establishes a general convergence analysis for a heterogeneous federated learning (FL) algorithm that trains a shared global model using a sequence of time-varying and client-dependent local models. In particular, this work establishes sufficient conditions for the convergence of such a heterogeneous FL algorithm to the neighborhood of a stationary point of the standard FL. Based on the theoretical results, the authors propose practical suggestions for designing heterogeneous FL algorithms and conduct thorough experiments to support their claims.", "questions": "Can the authors provide additional discussions regarding the last term in Theorem 1 (and Theorem 2)? Specifically, it would be helpful to explore whether this term is tight or under what circumstances it can be considered small.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Overall, this paper is well-written. It is the first to provide a general convergence result to the neighborhood of a stationary point for the standard federated learning (FL) framework, specifically for a heterogeneous FL algorithm that trains a shared global model through a sequence of time-varying and client-dependent local models. This result provides a convergence guarantee for several previously proposed heterogeneous FL algorithms. The optimality gap in the result depends on two important parameters: the minimum coverage index and the model reduction noise. These parameters offer valuable insights for designing practical heterogeneous FL algorithms. The experimental results align well with the theoretical findings presented in the paper.", "weaknesses": "The last term on the right-hand side of the inequality in Theorem 1 (and similarly for Theorem 2) corresponds to the average of the norms of the global parameters encountered during the optimization process. This term is not necessarily small in a straightforward manner.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive and insightful comments and suggestions. Following are our responses to your questions and concerns.\n\n> Q1. The last term on the right-hand side of the inequality in Theorem 1 (and similarly for Theorem 2) corresponds to the average of the norms of the global parameters encountered during the optimization process. This term is not necessarily small in a straightforward manner.\n\n* It is true that it might be hard to directly quantify the term  $E\\Vert \\theta_q\\Vert^2$, since it depends on the exact FL problem setup. We note that this term $E\\Vert \\theta_q\\Vert^2$ is bounded and should be examined together with its coefficients in the convergence bound, i.e., $\\frac{\\delta^2}{\\Gamma^*} E\\Vert \\theta_q\\Vert^2$. In particular, considering the coefficient $\\delta^2$ together with $E\\Vert \\theta_q\\Vert^2$, we have $E\\Vert \\delta \\theta_q\\Vert^2$, which relates to the pruning noise introduced in Assumption 2 and is equivalent to the bounded model reduction noise, i.e., $\\|\\theta_{q}-\\theta_{q} \\odot m_{q,n}\\|^{2} \\leq \\delta^{2}\\|\\theta_{q}\\|^{2}$. We also note that it is common to have a bounded model norms term in heterogeneous federated learning such as [1][2]; or a similar term of $|w_1-w_*|^2$ in works e.g. [3]. Our analysis shows that to reduce this term $\\frac{\\delta^2}{\\Gamma^*} E\\Vert \\theta_q\\Vert^2$, we can either increase $\\Gamma_{min}$ (by designing pruning strategies) or decrease mask noise $\\delta$ (by adjusting pruning level). We will add these discussions to the revised paper.\n\n>Q2. Can the authors provide additional discussions regarding the last term in Theorem 1 (and Theorem 2)? Specifically, it would be helpful to explore whether this term is tight or under what circumstances it can be considered small.\n\n* We will add more discussion on this term in the revision. Although it is hard to directly tell how large this $E\\Vert \\theta_q\\Vert^2$ is, our evaluation results demonstrate how this term affects learning performance. For instance, in the main results (Table 1 in main paper) we can compare “Pruning-Greedy” and “Pruning-Optimised”: the former has a larger $E\\Vert \\theta_q\\Vert^2$ and the latter has a larger $\\Gamma_{min}$, and as a result the latter one comes with a lower loss and converges with a faster convergency rate. Similar results can be found in other cases in the main results (e.g. by comparing  “Pruning-Medium (Greedy)” and “Pruning-Medium-Optimised” in Fig2 (a,b)) and additional results in the appendix. We will add these explanations and more insights in the revised paper. \n\n[1] Jiang, Zhida, et al. \"Fedmp: Federated learning through adaptive model pruning in heterogeneous edge computing.\" 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 2022.\n\n[2] Xiaolong Ma, et al. \"Effective Model Sparsification by Scheduled Grow-and-Prune Methods.\" International Conference on Learning Representations. 2022.\n\n[3]Xiang Li, et al. \"On the Convergence of FedAvg on Non-IID Data.\" International Conference on Learning Representations. 2020."}]

Author rebuttal:
Dear reviewers, thank you all again for your valuable time and positive suggestions that will definitely make our paper stronger. We have provided each reviewer with our responses in a Q&A format. We are happy to answer further questions if any.

Meta-review: The paper Introduces a general theoretical framework for analyzing the convergence of Federated training schemes over local models of heterogeneous network structures. The paper will be interesting for the community since it presents a more generalized federated pruning framework. The paper is technically solid and offers convergence guarantees for various heterogeneous federated learning algorithms, while numerical illustrations provide practical insights on performance. Experimental results align well with theoretical findings.

That said, the reviewers point out a number of things that need to be clarified in the final version of the paper. Please take into considerations the comments made by reviewers that will improve the quality of the paper.
Decision: Accept (poster)