Federated Submodel Optimization for Hot and Cold Data Features
Authors: Yucheng Ding
Chaoyue Niu
Fan Wu
Shaojie Tang
Chengfei Lyu
yanghe feng
Guihai Chen
Venue: NeurIPS 2022 Accept (2022)
Keywords: federated learning
optimization
recommender system
natural language processing

Abstract: We focus on federated learning in practical recommender systems and natural language processing scenarios. The global model for federated optimization typically contains a large and sparse embedding layer, while each client’s local data tend to interact with part of features, updating only a small submodel with the feature-related embedding vectors. We identify a new and important issue that distinct data features normally involve different numbers of clients, generating the differentiation of hot and cold features. We further reveal that the classical federated averaging algorithm (FedAvg) or its variants, which randomly selects clients to participate and uniformly averages their submodel updates, will be severely slowed down, because different parameters of the global model are optimized at different speeds. More specifically, the model parameters related to hot (resp., cold) features will be updated quickly (resp., slowly). We thus propose federated submodel averaging (FedSubAvg), which introduces the number of feature-related clients as the metric of feature heat to correct the aggregation of submodel updates. We prove that due to the dispersion of feature heat, the global objective is ill-conditioned, and FedSubAvg works as a suitable diagonal preconditioner. We also rigorously analyze FedSubAvg’s convergence rate to stationary points. We finally evaluate FedSubAvg over several public and industrial datasets. The evaluation results demonstrate that FedSubAvg significantly outperforms FedAvg and its variants.

Federated Submodel Optimization for Hot and Cold Data Features
Yucheng Ding'
Chaoyue Niu
Fan Wu'
Shaojie Tang² Guihai Chen
Chengfei Ly
Yanghe Feng'
Shanghai Jiao Tong University
University Texas at Dallas
Alibaba Group
National University of Defense Technology
Abstract
We focus federated learning in practical recommender systems and natural language processing scenarios. The global model for federated optimization typi- cally contains large and sparse embedding layer, while each client's local data tend to interact with part features, updating only a small submodel with the feature-related embedding vectors. We identify new and important issue that distinct data features normally involve different numbers clients, generating the differentiation of hot and cold features. We further reveal that the classical feder- ated averaging algorithm (FedAvg) or its variants, which randomly selects clients to participate and uniformly averages their submodel updates, will be severely slowed down, because different parameters of the global model are optimized at different speeds. More specifically, the model parameters related to hot (resp., cold) features will be updated quickly (resp., slowly). We thus propose federated submodel averaging (FedSubAvg), which introduces the number of feature-related clients the metric of feature heat to correct the aggregation of submodel updates. We prove that due to the dispersion of feature heat, the global objective is ill-conditioned, and FedSubAvg works as a suitable diagonal preconditioner. We also rigorously analyze FedSubAvg's convergence rate stationary points. We finally evaluate FedSubAvg over several public and industrial datasets. The evaluation results demonstrate that FedSubAvg significantly outperforms FedAvg and its variants.
Introduction
Federated learning (FL) [1] allows large number of clients (e.g., millions of smartphone users) to collaborate the training of a global machine learning (ML) model under the coordination of a cloud server without sharing raw data. For the production
the top. Google has deployed FL among Android keyboard, called Gboard, to polish language models [2]. As the default
the users optimization algorithm of Fl. the bottom, federated averaging (FedAvg) averages the participating clients' local new models to update the global model. Much effort existing work was devoted to proving the convergence of FedAvg, and the key challenge is that the clients' local data normally non-independent and identically distributed (non-i.i.d.) established an ( O(I/VNT) convergence, where N denotes the total number of clients and 7 denotes the total number of iterations. However, these work required all the clients participant in each round of FL, which is not practical in cross-device FL. Another line of work [2
One line of work
9
L3
14 BS
[6]
allowed partial client participation and proved an O(1/ (LT/VKT) convergence of FedAvg, where K denotes the number of chosen clients in each round. Some other work proposed variants of FedAvg
to better deal with data heterogeneity. For example, Li et al. [ proposed FedProx by adding
Chaoyue Niu
is the corresponding author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

proximal term to local objective; and Karimireddy et al. 18 proposed Scaffold by adding a control variate for each client to control local training.
Besides non-i.i.d. from data distribution, the interactions between the data features and the clients mutual, partial, and differentiated, especially in practical recommender systems (RS) and natural language processing (NLP) scenarios. First, distinct data features are normally involved by different numbers of clients. For example, the differentiation of popular and unpopular items in RS or hot and cold words in NLP is common. We call such an observation, feature heat dispersion. Second, a certain client's s local data tend to involve small subspace of the full feature space, which further implies that the client needs to download and update only the feature-relate part of the full global model, called submodel in [. For example, deep recommendation and language models are normally stacked with a large and sparse embedding layer and some other dense layers, while client's 's submodel comprises the full dense layers and the embedding vectors for the client's few local items or words rather than the full and huge embedding layer.
The existing work on FL has not studied the issue of feature heat dispersion yet. However, different parameters of the global model involve distinct features and will be optimized by different numbers of clients and at different speeds, severely deteriorating the performance of Aed and its variants. We take an extreme example in RS for illustration. For an unpopular item that appears only in 1% of the clients' (denoted as client group G₂) local datasets, the corresponding embedding vector for item is involved in the submodels of those clients in G1. Using conventional FedAvg and its variants, only the clients in G2 will upload non-zero updates, and the update of the embedding vector for item 1 will be slowed down 100 times. In contrast, for popular item 2 that appears in all the clients' local datasets, the update of the corresponding embedding vector will not be slowed down.
To deal with feature heat dispersion, we propose federated submodel averaging (FedSubAvg), which first averages the local updates of the chosen clients, just like FedAvg, but then multiplies the aggregated update of each model parameter with the ratio between the total number of clients and the number of clients who involve this model parameter. Such a small correction ensures that the expectation of each model parameter's 's global update is equal to the average of the local updates of the clients who involve this parameter. We theoretically demonstrate the advantage of FedSubAvg over FedAvg and analyze the convergence of FedSubAvg. We first prove that the global objective is ill- conditioned, leading to the slow convergence of FedAvg, and FedSubAvg works as suitable diagonal preconditioner. We also obtain an O( N/NN///miii KT)) convergence with respect to stationary points, where Amin denotes the minimum of the number of clients who involve each individual parameter.
We summarize the key contributions of this work as follows:
To the best of our knowledge, we are the first to make an in-depth study of FL from the differentia- tion of hot and cold data features, which is common in practice.
We identify the defect of FedAvg and its variants in handling feature heat dispersion and propose novel, effective, and efficient FedSubAvg algorithm.
We theoretically show that the the global objective ill-conditioned, and FedSubAvg essentially works as a preconditioner for acceleration. We also give the convergence rate of FedSubAvg in the general non-convex case.
Using the public MovieLens, Sentiment140 40, and Amazon datasets, as well as an industrial dataset from Alibaba, we extensively evaluate FedSubAvg and FedAdam. The evaluation results reveal the superiority of FedSubAvg from faster convergence and smaller train loss.
Ff and compare it with FedAvg, FedProx, Scaffold,
2 Problem Formulation
In this section, we formulate the federated submodel optimization problem with feature heat dispersion in RS and NLP scenarios.
2 The code is available on whtps//ghhhhbooonnsi..//ceteeees

---

Optimization Objective. We consider distributed optimization setting, in which N clients collabo- ratively solve the following consensus optimization problem:
f (X) 1 Σ BE [F
Σ f(X).
where D; denotes client i's local empirical distribution and & D; denotes the local training data; X is the full global model; F(X, E:) is the train loss X over the local data &s; and fx(X) is the local empirical error, taking expectation over the randomness of the local data.
Model Structure and Submodel. The full recommendation or language model X normally adopts the network structure of an embedding layer plus some other dense layers, where sparse input features are mapped into embedding vectors, concatenated, and fed into the upper layers. In practice, client's s local data involve only part of the full global model, namely, submodel, which is related to RS (resp., NLP) scenario, client can use the data
the client's 's local data features. For example, collected in the previous week as its local training set D,, and retrieve the submodel in a key-value lookup way, typically, by retrieving a few embedding vectors based on the local item ids (resp., word ids) and directly taking the other dense network layers. Considering the full embedding layer is far beyond any mobile device's capacity, such a submodel design makes FL these industrial scenarios possible. Formally,
M) to index the parameters of the full model X E RM and call the full index set. We let (() E S denote the index set of client i"s submodel Xs())- In other words, the full model excluding the submodel (i.e., ss)) does not affect the model output, and the local gradient of ss)s(()) will always be zero. This further implies that we can rewrite the global objective function in distributed submodel way:
use S = {1, 2.
1 N 1=1
f(X)
Σ f (Xs()).
The gradient of f is
1 N
VX(X) =
Σ
V (Xs()),
N
and the Hessian is
1 N H (
v (Xs()
N Σ H
Note that when doing any operation (e.g., summation) over multiple submodels, gradients, and Hessians, they will be automatically aligned according to the indices.
Feature/Parameter Heat Dispersion. We finally introduce the metric of feature heat dispersion (resp., the resulting parameter heat dispersion), which is defined as the ratio between the maximum and the minimum of the number of clients who involve each individual feature (resp., parameter). Considering the fact that parameter may involve one multiple data features in RS and NLF the feature heat dispersion is a lower bound the parameter heat dispersion. In other words, high feature heat dispersion inevitably leads to high parameter heat dispersion. For convenience and clarity in the submodel-level analysis, we mainly take the metric of parameter heat dispersion. We let n. denote the number of clients involving the parameter with index E S and set Ramax msxmes n, Amin minmes Rm- Then, the parameter heat dispersion is Rmax Amiu-
Algorithm Design
In this section, we first show that FedAvg suffers from high parameter heat dispersion in distributed submodel optimization and then propose FedSubAvg to remedy the defect.
Forr example, an embedding vector corresponds to an item in RS or certain word in NLP, while the dense layers are related to all the items words.
3

---

Ntotal
19"
Hinvolved clients
(Nice, Bob)
of Globaa Model
Bob
X
aggregale model update
element-wise correction
final aggregale update
1073
PaoAiy (10.11
local model updates
FedSubAug with yn1
Fedtig with nw0.
FedAug
PeeSubAng with yeg.5
FedSubAvg
20
Number of Communication Rounds
Figure FedAvg vs. FedSubAvg with N clients in total and clients involving the first model parameter. The dashed line indicates that the client does download the parameter and upload no update.
Figure 2: FedAvg (learning rate 1)) vs. FedSubAvg (learning rate 7) for Example [ with the parameter heat dispersion of 100.
3.1 Slow Convergence of FedAvg
Example 1. We consider special distributed convex optimization problem with two model parame- ters, denoted as wi and w2. Each client i's local data & ~ D; are with mean e; E[e = O. In addition, wi involves only client 1, while w2 involves all the N clients. Then, the parameter heat dispersion is n2/n1 N. We formulate this learning problem as minimizing the mean square enror:
f((w1, (()))w)))= 1 Σ fs ((w1, w2)s(1)
where fi ((w), w2)s(1)) = EEI~D. [I] (W), W2) - E1 | = w + w + BEI D.ll E1 - ei || and
for = 2.3...... ,,, N, Js ((w), w2 (2))(())))))))))))))))))))))(()) = BE D. [w2 3 = = RE [[[ - e
For this example, the optimal model is (wi, w5) (0, 0). We leverage FedAvg with only one local iteration and let each client compute the exact (not stochastic) gradient. The learning rate denoted as 7, and the model is initialized as (wf, wy). After rounds, the model will become
(wi, wh))
2n
O
(w) w.)
1 2m
By choosing 7 0.5, (wf, wx) ((1 1/N)" 0), we can find that in the FL scenario with high parameter heat dispersion N, wi will converge at a quite low speed. We also depict the optimization process of FedAvg in Figure
3.2 Federated Submodel Averaging
To mitigate parameter heat dispersion, we propose FedSubAvg. As shown in Figure | compared with FedAvg, the key principle of FedSubAvg model parameter with the ratio between the total number of clients and the number of clients who involve this model paramete[]ii.e. (i.e., for the model parameter with index m, the correction coefficient is N N/Tm). We still examine Example [ for illustration. FedSubAvg will multiply the aggregated update of wi and u2 with N and 1, respectively. By correction, the model at the r-th round is:
further multiply the aggregated update of each
(wi, w.)
- 2y
0
(wf, w.2)
1 1-2
where y is the learning rate FedSubAvg. Therefore, FedSubAvg converges quickly to the optimal model (0. O). We also depict the optimization processes of FedSubAvg and FedAvg for Example in Figure 2 when the parameter heat dispersion is 100. We can observe that FedSubAvg greatly outperforms FedAvg from convergence speed and loss.
'With some privacy preserving methods, we can obtain R... without revealing the real index set of any client's submodel. Please refer to Appendix for details.

---

Algorithm Federated Submodel Averaging (FeddubAvg)
Require:
The total number of clients N, the number of local iterations 7, the number of clients
involving the m-th model parameter 7mm, the number of selected clients K per round.
/* Cloud server's process */
1: Initializes the global model X
2: for each communication round 1, ,,,,...,
3: Randomly selects K clients, denoted as Cr:
4: for each client E C, do
5:
Receives the index set S(i), returns the submodel X Sts) and receives the submodel update Ax!:
6: end for
7: X + X";
8:
for each index m Uiec S(i) do
9: X < X(m) (m) + N
mm. Eiec, Ax (m)}
{m)
10: end for
11: end for
/+ Client i's process */
12: Determines its index set (i)) based on the local data;
13: Uses S(i) to download the submodel (s))) from the cloud server;
14: Initializes the local submodel x X ((1)
15: for local iteration j = 1,2, .... / do
17: end for ->VE(x Ei) for & D4;
x xJ++ x T-
Uploads Ax; xx+++1 x the cloud server.
We now present the design details of FedSubAvg in Algorithm T In each round r of FL., the cloud server first selects K clients to participate (Line 3), denoted as C,,. Each selected client C, determines its index set S(i) of submodel based on the local training set (Line 12). Then, client i uses (i) download the submodel Xs()) from the cloud server and initializes the local submodel
x (Lines13 1-4) Client locally trains its submodel by doing iterations of stochastic gradient descent (SGD) (Lines 15-17) and uploads the submodel update Ax (Line 18). After receiving the submodel updates from the selected clients, the cloud server performs aggregation for each index in the union of the participating clients' index and updates the global full model (Lines 7-10). In particular, for the global model parameter with index m, namely, X [m) its expected update, after being corrected with the coefficient N/nm= is
N
N
Ec.
AXI
[m)
N
Σ
Ax
{m)
Pun (i)mES(i)
Σ
Ax {m))
1=1
which is equal to the average of the local updates of the clients involving it, as required.
Theoretical Analysis
In this section, we first prove that in FL with high parameter heat dispersion, the global objective is ill-conditioned. We then prove that optimizing f with FedSubAvg approximates to optimizing a preconditioning objective if with gradient descent (GD), thereby remedying ill conditioning. In particular, the diagonal preconditioning matrix comprises of the correction coefficients (N/r.,, im S} in FedSubAvg and can be obtained without needing to access any client's 's local raw data and without any expensive computing, which keeps the tenet of FL.. Further by analyzing the Hessian of f. we demonstrate that the superiority of optimizing i over f. We also obtain the convergence guarantee for FedSubAvg.
4.1 FedAvg with Il-Conditioned Global Objective
We first make assumption about the eigenvalues of each client's local Hessian.

---

Assumption (Bounded Hessian). For any model X, the global Hessian is non-singular, and for each client i, the Hessian of satisfies:
-p21, 3 V fi s()) 3 pp1, or pIl; = ((Xs() 1 p211, with p1 < p2-
Further, X is in a locally convex area of foror each parameter m, more than of the related clients satisfies pıl; V (X((()))) I P24 where is a constant with (1 a) ap2 > 0.
Assumption 1 bounds the eigenvalues of fX s()) and ensures that when X is in locally convex area of f. X is also a locally convex area of fü for most of the clients, which helps to obtain the bounds of the global Hessian. Under Assumption
analyze the condition number of H: <(H) - max (H) min (H), where maax (H) and m (H) denote the biggest and smallest singular values of H. respectively.
[
Theorem 1. Under Assumption for any model X a locally convex area, the condition number of the global Hessian of J satisfies:
Temax (p1 a(p1 + P2))
HH)
Omin(2
Proof. Please refer to Appendix
Theorem reveals that when the parameter heat dispersion F' / is high, then the global objective is ill-conditioned. Specifically, in the large-scale RS and NLP scenarios, since the fully connected layer involves all the N clients, while the embedding vector of a cold item or word normally involves a few clients, we have x(H) 2 θ (N). This further implies with a large N in practice, the global objective extremely ill-conditioned. Therefore, the conventional FedAvg and its variants, which are the approximations to GD, will converge at a quite slow speed, even when the global model is in a locally convex area.
AvdSubAvg as Preconditioner Better than FedAvg
For brevity, we introduce /. to denote the global iteration index, thus replacing the round index and the local iteration index j, where = (r - 1) I + We consider a single iteration of FedSubAvg:
x = x D
v(i(()) x -DV(()))(X',
(1)
N
where X D EN1 x() is defined as the global model at iteration 1, and = .N/MM.. By treating a preconditioning matrix 20 we can con-
(iag(N/n1, /N/n,,N/22. N/n2....
struct new objective f(x) f(D1X) = f(X) with variable X-D- x The gradient and the Hessiar of are:
ví(x) = (!V)(X)
Dauphin et al. 20 showed that one SGD update for f corresponds to equation Therefore, we can compare FedSubAvg and FedAvg by comparing the characteristics of f and f.
Theorem 2. Under Assumption 7 for any X, the upper bound of the condition number of the corresponding Hessian, i 22 f(X), is always smaller than that of H:
P2Temax
_ K. (H) Omin (H)
A k with & S k.
(H) <
No (H)
Further, if X in a locally convex area, the condition number of 2 f(X), satisfies:
(A)) < (p1 (p1- a(p + p2))
P2
with H v()().
'The gradient and the Hessian of are with respect to X.

---

Proof. Please refer to Appendix
Theorem 2 indicates that H always has smaller condition number upper bound compared with H. Further, locally convex area, the proposed FedSubAvg significantly reduces the condition number: H well-conditioned with x(H) S ( Therefore, the proposed FedSubAvg, which an approximation to GD for objective f. will maintain the efficiency of FedAvg in any case and converge much faster than FedAvg in a locally convex of /.
4.3 Convergence Guarantee for FedSubAvg
In this section, we analyze the convergence rate of FedSubAvg in the general non-convex case based on some standard assumptions. We use || V - fx() DV f (XX) rather than V I? to characterize the convergence rate. This is because the curvature of the original global objective has been severely "diluted". In particular, most model parameters involve only a small number of clients, while the gradients contributed by many non-involved clients are inaccurately counted in when computing the global gradien
We next make the following assumptions about the objective functions, as well as the variance and the feasible space of the stochastic gradients.
Assumption 2 (Smoothness). f((-) is L-smooth
I Vx,y, fo (y) S fo (x) (y-xx ( 1x-
Assumption (Bounded Variance). During local training, the variance of stochastic gradients on each client bounded by a²: Vi Eg []] f. (xt) - VF (xt |12] 0
Assumption 4 (Bounded Gradient Norm). During local training, the expected 12-norm of the stochastic gradients is bounded by constant G2; Vi,t: Eg,DD []] VF (xf, 5.)
[1a] G
Assumption is standard. Assumptions and were widely made in the literature
g 9
Under these assumptions, we can bound the gradient norm.
Theorem 3. Under Assumptions and we can bound the expected average of the squared gradient norm
2 (x²) - ((X))
LyTa²
AN
NT
E
VVX(X)
<
TT
Amiin
Pmiin
A K
When T > mmni K3/N and r 10 (
Pmink
we have
V((X)) s0
<0((
N
E T
KT
Proof. Please refer to Appendix
Evaluation
In this section, extensively evaluate the performance of FedSubAvg over several datasets with different feature heat dispersion.
5.1 Experimental Setups
We choose the following tasks and models for evaluation. The statistics about clients and samples, as well as the feature heat dispersion are shown in Table
LR for Rating Classification. We perform rating classification task over the MovieLens- IM dataset 22), which contains 6,040 clients, 3,883 movies, and 1,000,209 samples. We preprocess the
'Please refer to Appendix C for detailed explanation.

---

Table 1: Statistics of four datasets.
# Clients
# Samples
# Samples Per Client
Feature Heat Dispersion
MovieLens
6,040
1,000,209
165
4,33
44nt140
1,473
79,050
54
1,451
Amazon 1,870
123,147
66
232
Alibaba 49,023
16,864,641
344
3,142
dataset be suitable for binary classification. In particular, the original user ratings of movies range from O to 5. We label the samples with the ratings of 4 and 5 to be positive and label the rest to be negative. We randomly select 20% of the samples as the test dataset and leave the remaining 80% as the training dataset for FL. The task is to predict whether users will rate given movie to be positive based on the user's gender and age and on the movie ID. We first encode gender, age, movie, gender cross movie, and age cross movie, based on the one-hot encoder. Next, the features are input into a logistic regression (LR) model to predict the label.
LSTM for Sentiment Analysis. We perform a text sentiment classification task on the Sentiment 400 dataset 2 which comprises 1,600,000 tweets collected from 659,775 twitter users. In this task, we use a two-layer long short-term memory (LSTM) network with 100 hidden units and an embedding layer as the binary classifier, where the embedding dimension is set to 25. We naturally partition this dataset by letting each Twitter account correspond to a client. We keep only the clients who hold more than 40 samples and get 1.473 clients in total. We randomly select 20% of the samples as the test dataset and leave the remaining 80% as the training set for FL.
DIN for CTR Prediction. We perform a click-through rate (CTR) prediction task on the Amazon electronics dataset and an Alibaba industrial dataset. The Amazon dataset contains 1, 1,689,188 reviews contributed by 192,403 users for 63,001 items. The ratings range from 0 to 5. We label the samples with the rating of 5 to be positive and label the rest to be negative. We naturally partition this dataset by letting each Amazon user correspond to a client. For each client, we take the user ID, the historical sequence of positively rated product as the input to predict the label. We keep only the clients who hold more than 40 samples and get 1,870 clients in total. We select samples with the timestamps more than 1,385,000,000 as the test dataset and leave the remaining samples as the training set. The Alibaba dataset built from 30-day impression and click logs of 49,023 Taobao clients from June 15, 2019 to July 15, 2019. For a certain Taobao user, we leverage its click behaviors in previous 14 days as historical data to predict its click and non-click behaviors in the following day. We leave out the behaviors within the last day as the target items of the test set while putting the other samples into the training set. For both datasets, we take the deployed deep interest network (DIN) 24 in Alibaba as the model, where the embedding dimension is set to 18.
We use the following five baselines for comparison.
FedAvg averages the local model updates from the participating clients to update the global model.
FedProx is the first variant of FedAvg. The main difference from FedAvg is that FedProx adds quadratic proximal term to explicitly limit the local model updates. We set the coefficient of the proximal term to 0.01.
Scaffold is another important variant of FedAvg. The key difference from FedAvg is that each client keeps variate to control the local model updates in Scaffold. However, the size of the control variate is equal to size of the full model, which is prohibitively inefficient for the learning tasks with large-scale full models. Therefore, for the CTR prediction tasks, we make an approximation Scaffold. In particular, the cloud server performs the controlled update step every round by weighted averaging the historical updates. Please refer to Appendix D.2 for details.
FedAdam is also an important FL algorithm, which adopts an adaptive optimizer more comparisons and discussions in Appendix
25
We make
CentralSGD runs the standard SGD algorithm to train the global model using the whole dataset, sets the number of iterations in each round as 1, and sets the batch size to the sum of the selected clients' local batch sizes in each round. This ensures the same amount of data per round with the distributed algorithms.
8

---

Soaftid
Testig
tedeno
Number Communication Rounds
Number Communization Rounds
Number Communication Rounds
Number of Commurication Rounds
(a) MovieLenns
(b) Sentiment|44 140
(C) Amazon
(d) Alibaba
Figure 3:
Train losses or test AUCs of FedSubAvg and the baselines on different datasets.
Table 2: Number of communication rounds to reach the target train loss or test AUC with different algorithms. # indicates that the target not reached even after # rounds.
CentralSGD
FedAvg
FedProx
Scaffold
FedAdam
FedSubAvg
Movielenss
180
170
170
180
170
100
Sent140
980
1,000+
1,000+
1,000+
1000+
260
Amazon
20
200+
200+
200+
16
53
Alibaba
265
5,000+
5,000+
5,000+
5000+
610
Regarding the experimental settings, we choose mini- batch SGD as the optimization algorithm. For the tasks of rating classification and sentiment analysis, K 50 clients randomly chosen per round as default; and for the CTR prediction tasks, K is set to 100 as default. The settings of the other hyperparameters are deferred Appendix D.3
5.2 Evaluation Results
We first present the results of FedSubAvg and the baselines under the default K. We then vary K to show impact.
FedSubAvg vs. Baselines. For the rating classification on the Movielens dataset and the sentiment analysis the Sent140 dataset, plot the train loss in Figure 3(a] and Figure 3(b and for the CTR prediction on Amazon and the Alibaba dataset, we plot the test area under the curve (AUC)
Figure 3(c and ((d) In addition, we measure the convergence rates of different algorithms by counting the communication rounds to reach a target train loss or test AUC. We set the target loss in the rating classification (resp., the sentiment analysis) be the minimum loss of CentralSGD, which is 0.325 (resp., 0.380); and we set the target test AUC to be 0.6 in two CTR prediction tasks. The results are listed in Table 2
From Figure 3 and Table 2 we observe that FedSubAvg consistently outperforms FedAvg and its variants. Specifically, (1) in the rating classification, FedSubAvg always has the smallest train loss during Fl. and reaches the target at the 100-th communication round, 1.7 faster than FedAvg, FedProx, and FedAdam, and 1.8x faster than Scaffold and CentralSGD; (2) in the sentiment analysis, FedSubAvg still has the smallest train loss during FL and reaches the target at the 260-th round, 3.77x faster than CentralSGD, while FedAvg, FedProx, Scaffold, and FedAdam cannot reach the target even in 1,000 rounds; (3) in the CTR prediction on the Amazon dataset, FedSubAvg achieves the highest AUC while FedAdam achieves the target AUC first among all the FL algorithms. FedSubAvg achieves the highest AUC of 0.641 in 200 rounds, decreasing by 0.013 in terms of AUC compared with the ideal CentralSGD. contrast, FedAvg achieves the highest AUC 0.523, FedProx achieves the highest AUC of 0.519, Scaffold achieves the highest AUC of 0.514, and FedAdam achieves the highest AUC 0.633. In addition, FedSubAvg reaches the target test AUC at the 53-th round, while FedAvg, FedProx, and Scaffold cannot reach the target even after 200 rounds; and (4) in the CTR prediction on the Alibaba dataset, FedSubAvg still outperforms all the other FL algorithms. FedSubAvg achieves the highest AUC of 0.626 in 5,000 rounds, decreasing by 0.016 compared with
"The positive and negative samples in CTR datasets (especially the Alibaba dataset) are extremely uneven. Even if all the samples are predicted to be negative (or positive), the train loss is very small. As a result, the train losses of different algorithms hard to distinguish, and we choose plot the test AUC' instead.

---

Do or oven Moco Meddl
Conas Necde
Number Communication Rounds
Number Communizaiinn Rounds
Number Communccttio Rounds
Number of Communication Rounds
(a) MovieLenns
(b) Sentiment|44 140
(c)
Amazon
(d) Alibaba
Figure 4:
Train losses or test AUCs of FedSubAvg on different datasets with the varying number of selected clients per round K.
Table 3:
Number of communication rounds for FedSubAvg to reach the target train loss test AUC with the varying number of selected clients per round K.
MovieLens
Sent 40
Amazon
Alibaba
K
10
30
50
10
30
50
20
60
100
20
60
100
Rounds
100
110
100
420
270
260
95
57
53
3,469
1,030
610
CentralSGID. In contrast, FedProx achieves the highest AUC of 04,14, FedAvg achieves the highest AUC of 0.509, Scaffold achieves the highest AUC of 0.507, and FedAdam achieves the highest AUC of 0.554. Moreover, FedSubAvg reaches the target test AUC the 610-th round, whereas the other FL algorithms cannot reach the target even after 5,000 rounds.
Impact of participating clients. We next evaluate the impact of the number of selected clients K per round on FedSubAvg. We set K =10, 30, and 50 for the rating classification and the sentiment analysis, and set K 20, 60, and 100 for the CTR prediction. We plot the results in Figure 4 and record the minimum number of rounds to reach the target in Table We observe that FedSubAvg with larger K generally converges much faster, which validates the speedup with respect to K. (1) In the rating classification, FedSubAvg with different K behaves somewhat uniformly. This is because larger K improves the convergence by reducing the variance of the global model update, while for such a simple convex optimization scenario, the variance is already small enough with K 10; (2) in the sentiment analysis, FodSubAvg with
50 reaches the target train loss 1.62x faster than FedSubAvg with K = 10; (3) in the CTR prediction on the Amazon dataset FedSubAvg with K 100 reaches the target test AUC 1.79x faster than FedSubAvg with K 20; and (4) in the CTR prediction on the Alibaba dataset, FedSubAvg with K = 100 reaches the target test AUC 5.69x faster than FedSubAvg with K 20.
Conclusion
In this work, we studied federated submodel optimization over non-i.i.d. data with feature heat dispersion. We proposed FedSubAvg, which ensures the expectation of the global update of each model parameter to be equal to the average of the local updates of the clients who involve it. We also proved that FedSubAvg works as preconditioner to improve collaborative optimization and thoroughly analyzed the convergence. Empirical studies demonstrated the remarkable superiority of FedSubAvg over FedAvg and its variants.
Acknowledgment
This work was supported in part by National Key R&D Program of China No. 2019YFB2102200, in part by China NSF grant No. 62202296, 62025204, 62072303, 61972252, 61972254, and 61832005, part by Alibaba Group through Alibaba Innovation Research (AIR) Program, and in part by Tencent Rhino Bird Key Research Project. The opinions, findings, conclusions, and recommendations expressed in this paper are those the authors and do necessarily reflect the views of the funding agencies or the government.
10

---

References
[1] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüier y Arcas. Communication-efinn learning of deep networks from decentralized data. In AISTATS, Proceedings of Machine Learning Research, pages 1273-1282. PMLR, 2017.
[2] Kallista A. Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloé Kiddon, Jakub Konečný, Stefano Mazzocchi, Brendan McMahan, Timon Van Overveldt, David Petrou, Daniel Ramage, and Jason Roselander. Towards federated learning at scale: System design. In MLSys. mlsys.org, 2019.
[3] Mu Li, David G. Andersen, Jun Woo Park, Alexander Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene J. Shekita, and Bor- Yiing Su. Scaling distributed machine learning with the parameter server. In OSDI, pages 583-598. USENIX Association, 2014.
[4] Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu, Asynchronous decentralized parallel stochastic gradient descent. In ICML, Proceedings of Machine Learning Research, pages 3049-3058. PMLR, 2018.
[5] Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. D2: Decentralized training over decentralized data. In ICML, Proceedings of Machine Learning Research, pages 4855-4863. PMLR, 2018
[6] Hao Yu and Rong Jin. On the computation and communication complexity of parallel SGD with dynamic batch sizes for stochastic non-convex optimization. In ICML, Proceedings of Machine Learning Research, pages 7174-7183. PMLR, 2019.
[7] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First analysis of local GD on heterogeneous data. CoRR, abss/199..04755 2019.
[8] Sebastian U. Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication. CoRR, abs/1909.05350, 2019.
[9] Sebastian U. Stich. Local SGD converges fast and communicates little. In ICLR. OpenRe- view.net, 2019.
[10] Jianyu Wang and Gauri Joshi. Cooperative SGD: unified framework for the design and analysis of local-update SGD algorithms. J. Mach. Learn. Res., 22:213:1-213:50, 2021.
[11] Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning. In AAAI, pages 5693-5700. AAAI Press, 2019.
[12] Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Client selection in federated learning: Convergence analysis and power-of-choice selection strategies. CoRR, abs/2010.01244 2020.
[13] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In ICLR. OpenReview.net, 2020.
[14] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U, Stich, and Ananda Theertha Suresh. SCAFFOLD: stochastic controlled averaging for federated learning. In JCML, Proceedings Machine Learning Research, pages 5132-5143, PMLR, 2020.
[15] Dmitrii Avdiukhin and Shiva Prasad Kasiviswanathan. Federated learning under arbitrary communication patterns. In ICML, Proceedings of Machine Learning Research, pages 425-435. PMLR, 2021.
[16] Yann Fraboni, Richard Vidal. Lactitia Kameni, and Marco Lorenzi. Clustered sampling: Low- variance and improved representativity for clients selection in federated learning. In ICML, Proceedings of Machine Learning Research, pages 3407-3416. PMLR, 2021.
[17] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In MLSys. misys.org. 2020.

---

[18] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. SCAFFOLD: stochastic controlled averaging for federated learning. In ICML,, Proceedings of Machine Learning Research, pages 5132-5143, PMLR, 2020.
[19] Chaoyue Niu, Fan Wu, Shaojie Tang, Lifeng Hua, Rongfei Jia, Chengfei Lv, Zhihua Wu, and Guihai Chen. Billion-scale federated learning mobile clients: submodel design with tunable privacy. In MobiCom, pages 31:1-31:14. ACM, 2020.
[20] Yann N. Dauphin, Harm de Vries, and Yoshua Bengio. Equilibrated adaptive learning rates for non-convex optimization. In NeurIPS, pages 1504-1512, 2015.
[21] Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization. In ICML, Proceedings of Machine Learning Research, pages 189-7113. PMLR, 2019.
[22] Maxwell Harper and Joseph Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst., 19:11999,,, 2016.
[23] Tapan Sahni, Chinmay Chandak, Naveen Reddy Chedeti, and Manish Singh. Efficient twitter sentiment classification using subjective distant supervision. In COMSNETS, pages 548-553.
IEEE, 2017.
[24] Guorui Zhou, Xiaoqiang Zhu, Chengru Song, Ying Fan, Han Zhu, Xiao Ma, Yanghui Yan, Junqi Jin, Han Li, and Kun Gai. Deep interest network for click-through rate prediction. In KDD, pages 1059-1068. ACM, 2018.
[25] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In ICLR. OpenReview.net, 2020.
[26] Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer bias. J. Am. Stat. Assoc., 60(309):63-66 69, 1965.
[27] Kallista A. Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMa- han, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy-preserving machine learning. In CCS, pages 1175-1191, ACM, 2017.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? limited RS and NLP tasks.
[Yes] The proposed algorithm is
(c) Did you discuss any potential negative societal impacts of your work? [Yes] The societal impact of this work is consistent with that of the federated learning framework.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We include the code and but the industrial data is not included yet.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A] tune the optimal hyperparameters for the baselines as well as our algorithm, and report only the best results.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [Yes] Please refer to the introduction about the datasets.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [Yes] Please refer to the introduction about the datasets.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "uPoFHtGXLh7", "reviewer": "Reviewer_wqvK", "summary": "The manuscript considers a specific use case of federated learning in a recommender system or NLP scenario and proposes to scale the model update per coordinate through the ratio between the total number of clients and the number of clients who involve this model parameter coordinate. Some theoretical results are provided to motivate and justify the necessity of design choices.", "questions": "Check Weaknesses part.", "limitations": "Check Weaknesses part.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n* The considered scenario is interesting and important to the community. The proposed method is simple yet (intuitively) effective in alleviating the identified limitation.\n* The entire manuscript is generally well-structured, and most claims are well-supported.\n* Extensive numerical results are provided for some aspects.\n\n# Weaknesses\n1. The index set $S(i)$ determines the sub-model of $X S(i)r$. However, for the four considered datasets, the exact distribution of features (hot vs. cold features) is still unknown, and some specific treatments (line 211- line 212, line 226 - line 227) may require some justifications, such as \"we label the samples with the ratings of 4 and 5 to be positive and label the rest to be negative\". Will these treatments magnify the large imbalance phenomenon between hot and cold features?\n2. Given the considered challenges and proposed coordinate-wise scaling solution, one strong competitor should be considered, i.e., using an adaptive optimizer on the server as in [1].\n3. The client's index set must be sent to the server, and a clustering-based FL technique can utilize this information naturally. The reviewer is also interested in how cluster-based FL approaches perform, as these algorithms may have already addressed the issue of hot vs. cold features.\n\n# Reference\n1. Adaptive Federated Optimization\n\n---\n\n# Post rebuttal\nThe reviewer acknowledged the authors' feedback and checked other reviews. \n\nThe response has addressed concerns #2 and (partially) #3. However, the reviewer still believes that the manuscript needs some revisions to polish its text (e.g., make it self-contained, well-structured, precise, etc).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Xaj8pBNeZDd", "reviewer": "Reviewer_XsFL", "summary": "This paper proposes a submodel optimization technique in federated learning in the presence of diverse data feature distributions across clients. Heterogenity in features of local data leads to distinct update speed for individual feature-related parameters, degenerating convergence of the model. The paper claims that the global objective function of typical federated learning framework is ill-conditioned when each client updates and communicate only subset of the total model (submodel).\nThis paper handles the problem by compensating the amount of parameter updates based on the feature heat dispersion. It also provides formal analysis for the convergence of the proposed method. It demonstrates the effectiveness of the proposed method over baselines on three benchmarks; rating classification, text sentiment classification, click-through rate prediction.\n\n", "questions": "- Comparison with the typical FedAvg (participating clients update all parameters of server model then aggregate them) in terms of total communicated parameters would validate the efficiency of the proposed method. \n\n", "limitations": "- As mentioned above, the proposed algorithm is incompatible with modern deep learning architectures (CNN, MLP), the more compatible approach should be proposed without using prior knowledge that the feature dispersion is known and feature-related parameters are predefined. \n\n- The writing is hard to follow, and some details (e.g. implementation details) were not explained well.\n", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n### Strengths\n\n- The submodel optimization setup where each client updates the subset parameters of the central server is realistic and would be the proper extension with clear motivation. In real-world applications edge devices are likely to have limited capacity in memory, computation, and communication bandwidth.\n\n- Experimental results are quite compelling. Figure 3 presents that FedSubAvg converges fast and shows similar tendency with centralized training (CentralSGD)\n\n### Weakness\n\n- The assumption that server knows indexes for the feature-related parameters of all clients is unrealistic. \nDue to the assumption, the proposed algorithm is not compatible with deep models (e.g. DNN, MLP) with multiple non-linear layers.\n\n- In the similar vein, The proposed method needs to calculate data feature dispersion, which can bring about privacy concerns.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "X5U6NsQgrsX", "reviewer": "Reviewer_9rr3", "summary": "The authors point out the fact that (in the context of federated learning) client’s local data normally involve a small subspace of the full feature space. Especially in the case of models that contain large sparse embeddings, this would mean that each client downloads and updates only a small part of the full global model (I.e., a submodel). \n\nAs some features are more popular than others (e.g., words in a vocabulary), some embedding will then be averaged by a larger fraction of clients than others. The authors then show that this discrepancy (called heat dispersion) might result in slower convergence of algorithms like FedAvg. \n\nThey then propose a new method where each weight essentially has a different learning rate, based on how many clients participate in its update. They show both analytically and through an evaluation that this method improves the convergence speed. \n\n\n", "questions": "Overall this is a great method to address sparse feature dispersion in FL. \n\n- Practically this algorithm works by providing a different averaging coefficient for each parameter, based on the \"popularity\" of each feature amongst the clients. As a result, the resulting overall (average) learning rate might be affected.  While this shows faster convergence on the empirical evaluation, it is unclear if this is due to using a default learning rate (and the same learning rate) across each method. A more fair experiment would be to make sure that a hyper-parameter search is conducted for each baseline and the proposed method. I am mentioning this because practically, by changing the averaging coefficient, FedAvg might be more tolerant to higher LR (thus improving convergence speed) than FedSubAvg before convergence is affected. It would be great if the authors revised their experiments and show that FedSubAvg is able to beat the other methods when each method is using hyperparams that are searched independently.\n\n- The second question is wrt to the number of clients (K) vs other methods. The authors show that as the number of clients increase, FedSubAvg converges faster. As in many real-world FL deployed systems K = thousands of devices, it would be great to be able to also include the results from the baselines (or at least fedAvg) and possibly show for values > 100. Its unclear if the convergence of FedSubAvg is much better that the SOTA only for small K or if this algorithm would actually improve convergence in real-world scenarios. \n\n- The third question is about combining this method with privacy-preserving mechanisms. There were many approaches where secure embedding retrieval's were used, and local DP noise is added to the model to make sure that user privacy and regulations are respected. It would be great if the authors comment on the compatibility of their approach with such privacy-preserving approaches, especially as they have to be able to identify the exact features that the clients used to update the model. ", "limitations": "Please see above (questions)", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ The authors address an interesting problem on training FL models with sparse embeddings: the fact that not all of them are equally popular. \n\n+ The authors conducted a theoretical analysis of their model\n\n+ They compared with 4 baselines, some of them designed to speed up convergence on non-iid data. \n\n+ The results show that their methodology is promising\n\n- There are some assumptions in the evaluation (see below in questions for details)\n\n- It is unclear how well this methodology would work with privacy-preserving mechanisms (e.g., local DP noise)\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NPfquCVal7Y", "reviewer": "Reviewer_Me5H", "summary": "The authors consider a specific federated learning scenario where different data features ‘involve’ different clients. For some features, a large number of clients can be involved while other features might involve only limited clients. The authors show that in this case, the classical FedAvg can suffer from slow convergence. In the proposed new algorithm, the aggregations of parameter updates are weighted per parameter by the ratios of the local clients involved. The authors prove that by reweighting the parameter updates in this way, the condition numbers of the Hessian of the learning objectives become smaller than the original Hessian. In the experiments with four real-world datasets, the authors demonstrated that the proposed algorithm (FedSubAvg) offers faster convergence than existing alternatives.\n", "questions": "Please see Strengths And Weaknesses section.", "limitations": "The limitations and potential negative societal impact were not discussed.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nImproving the convergence of federated learning is an important and active area of research. The authors contribute a new algorithm that can potentially improve the convergence of the federated averaging algorithm. The experiments were conducted on large-scale real-world datasets.\n\nLimitations:\n- The paper would need a thorough rewriting. For example, the example illustration of feature heat dispersion in recommender systems at L45-50 is difficult to comprehend. What does ‘less than 1% of the average’ mean? Please formally define ‘involvement‘. L122 ‘the number of clients who involve this model parameter’: How is this number determined in general?\n- The proposed algorithm seems applicable only when ‘submodels‘ are well-defined, i.e., the individual clients do not have to update the full model parameters but instead, can download and update only the required small parts (submodel) of the complete model. On the other hand, typical local learning steps tend to require simultaneous updates of all model parameters, unless the model is linear. The authors should provide a detailed discussion as to when such submodels are well-defined and how the index set S(i) is determined in practice. Can this algorithm be applied to the standard MLPs?\n\nMinor comments\n- The proposed algorithm can be considered as diagonal preconditioning on stochastic gradient descent (SGD) (L167). The authors could discuss connections to existing SGD preconditioning methods, e.g., AdaGrad: AdaGrad preconditions the SGD update based on the magnitudes of individual parameter updates. Extending AdaGrad to the federated learning setting can be straightforward.\n- Please enlarge the plots in figures 3 and 4.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept