Federated Learning on Adaptively Weighted Nodes by Bilevel Optimization
Authors: Yankun Huang
Qihang Lin
Nick Street
Stephen Baek
Venue: Submitted to ICLR 2023 (2023)
Keywords: federated learning
bilevel optimization
distributed optimization
generalization performance

Abstract: We propose a federated learning method with weighted nodes in which the weights can be modified to optimize the model’s performance on a separate validation set. The problem is formulated as a bilevel optimization problem where the inner problem is a federated learning problem with weighted nodes and the outer problem focuses on optimizing the weights based on the validation performance of the model returned from the inner problem. A communication-efficient federated optimization algorithm is designed to solve this bilevel optimization problem. We analyze the generalization performance of the output model and identify the scenarios when our method is in theory superior to training a model locally and superior to federated learning with static and evenly distributed weights. 

Under review as a conference paper at ICLR 2023
FEDERATED LEARNING ON ADAPTIVELY WEIGHTED NODES BY BILEVEL OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
We propose federated learning method with weighted nodes in which the weights can be modified to optimize the model's performance set. The problem is formulated as a bilevel optimization problem where the in- ner problem is a federated learning problem with weighted nodes and the outer problem focuses on optimizing the weights based on the validation performance of the model returned from the inner problem. communication-efiinn ated optimization algorithm is designed to solve this bilevel optimization problem. We analyze the generalization performance of the output model and identify the scenarios when our method is in theory superior to training model locally and superior to federated learning with static and evenly distributed weights.
separate validation
feder-
INTRODUCTION
Federated learning (FL) is emerging technique for training model using data distributed over network of nodes without sharing data between nodes (Konečný et al., 2016; McMahan et al., 2017). In this paper, focus the case where data distributions across nodes are heterogeneous and each node aims at a model with an optimal local generalization performance. In the classical setting of FL., a globally shared model is learned by minimizing weighted average loss across all nodes. However, given the heterogeneity of data distributions, a global model is likely to be sub-optimal for some node (Fallah et al., 2020). Alternatively, each node can train a model only using its local data, but such local model may not generalize well neither when the volume of local data is small.
To achieve a good local generalization performance, each node can still exploit global training data through FL but, at the same time. identify and collaborate only with the nodes whose data distri- butions are similar or identical to its local distribution. One way implement this strategy to allow each node to solve its own weighted average loss minimization problem with weights de- signed based on the performance on separate set of local (validation) data. Ideally, each node can learn better model by allocating more weights its peers whose data distribution is similar to its local distribution.
this paper, we formulate the choice of the weights as a bilevel optimization (BO) problem (Colson et al., 2005; Vicente & Calamai, 1994), which can be solved by federated bilevel optimization algorithm, and analyze the generalization performances of the resulting model.
We consider standard learning problem where the goal is to Iearn vector of model parameters 0 from a set that minimizes a generalization loss. This problem can be formulated as
0" arg min {Lo( == Eg-pp [1(0;))]3
BEe
where 1(0; 2) is the loss of 0 on a data point from a space Z, and Eg-po represents the expectation taken over when follows an unknown ground truth distribution Po-
Directly solving (P) is challenging as Pe unknown, and, typically, training data sampled from Po is needed for learning an approximation of 6* In this paper, we consider the scenario where the amount of data sampled directly from Po may not sufficient to learn a good approximation of 0*, but there exist external data distributed on K nodes that can potentially help the learning on 0*. In
particular, we denote the set of nodes by == (1,..., , K} and assume a training set D stored
in node k. We also define Durii
( Durin) x= and assume Ditain ng and D [=6 Je
(6) where =k E 2 is i.i.d. sample from unknown distribution pk for l E K.

---

Under review as a conference paper at ICLR 2023
We assume node k is weighted by wp and the vector of weights w (W1, ...,,........................... ,,k) E [0, is located on the capped simplex 4 defined as
A = w (wi..... wx) El wh 1,0 wn S <b,
1] is user-defined parameter. The FL weighted nodes can be formulated as where b E IR.
(w) arg min Ek=1 wx Lo),
where La (0) is the empirical loss of on D namely,
(0)
1 ny E 100;2 EEK.
(2)
When some Pæ 's are different from to in (1) must be chosen adaptively to ensure (ww is good approximation of l in (P). To do so, we assume that there validation dataset D Dvalid with [Dvalid] = no rlvalid and v {2(0) no i=--" where 2 E Z is an i..dd. sample from Po- We assume valld is stored in node called node 0 or center, which may or may not be a node in K. Set Dvalid alone may not be sufficient for learning 0* precisely but can be used to assist the selection of w. We then propose to estimate the generalization loss of ((w) using the loss on Dvalid i.e.
To(0) == +. E. 1(0;
and this validation loss to guide the procedure for updating Presumably, when both the training and validation sets are large enough, the weights in w will be shifted towards the nodes where the data helpful for learning 0*, Following this idea, formulate the federated learning problem on adaptively weighted nodey as the following bilevel optimization (BO) problem:
W E arg min { (((w)=Io000
s.t. Ō(w) is defined in (i)
wEA*
In Section 4, we will present a federated optimization algorithm for solving (P). Suppose an al- gorithm can find the optimal solution of (P) and the corresponding model parameter (ww). We are interested in the optimality gap of the generalization loss of ((w), namely, ()))))) Lo())), where To is defined as in (P). The main contribution of this paper is to establish a high-probability bound of this gap as a function of the sizes of Dirain and Dvalid as well as statistical distance between Po and pk s. Moreover, we compare our generalization bound with the bound achieved by learning only locally from D and the bound achieved by solving (1) with evenly distributed weights, and identify the parameter regimes where our method is preferred in theory.
RELATED WORK
The work most related to ours is Chen et al. (2021a) in which the authors proposed a target-aware weighted training algorithm for cross-task learning. Although their problem is completely different from FL, the bilevel optimization model they studied contains (P) special case. In fact, some steps in the proofs of the generalization bounds in the current work are borrowed from Chen et al. (2021a) with some modifications. However, rections. First, the generalization bound in Chen et al. (2021a) is shown for any weight w without any small or zero components, which is not necessarily the case for the optimal solution @ of (P). Second, their generalization bound contains term of task distance whose convergence rate is not characterized. On the contrary, we show the convergence of the entire generalization bound for @ without any conditions on its components. Third, the generalization bound in Chen et al. (202 1a) has a dominating term O(1/ /Twali)), which is the same as the generalization bound obtained by directly training with the local data valld, However, we show that, when there exist identical neighbors and an error bound condition holds (Assumptions 2' and 3), the model learned by (P) be superior to a model trained locally when the Pk 's are similar enough to (but still different from) Po. providing an insight when node with insufficient data should actively seek collaboration with others.
work extends their results in several valuable di-
FL has become a prominent machine learning paradigm for training models with distributed data Konečný et al. (2016); McMahan et al. (2017). Many federated optimization algorithms have been
2

---

Under review as a conference paper at ICLR 2023
developed for solving (1) or its expectation form (with L& replaced by Lς). A well-known method is the federated averaging (FedAvg) method (McMahan et al., 2017), which applies a local optimiza- tion method (e.g,, stochastic gradient descend (Robbins & Monro, 1951)) to La or L& in each node and periodically aggregates the solutions from all nodes by averaging. Many variants of FedAvg and other federated learning methods have been proposed to reduce the computation and commu- nication complexity. A partial list includes Gorbunov et al. (2021); Lee al. (2017); Karimireddy et al. (2020); Liang et al. (2019); Li et al. (2020); Yuan & Ma (2020); Wu & Wang (2021); Zhao et al. (2021). In our setting, (1) is a sub-problem we need to solve multiple times with different w's. s. We then apply the Local-SVRG method by Gorbunov et al. (2021) to (1) because it has the lowest communication complexity for finite-sum problems like (1).
Most FL methods produce a globally-sharee model which may not perform well each node when data is heterogeneous across nodes. To address this challenge, many personalized FL methods, including but not limited to Smith et al. (2017); Tan et al. (2022); Fallah et al. (2020); Li & Wang (2019); Deng et al. (2020); Li et al. (2021), have been developed, where a global model is tailored using local data for good local performance. However, many personalized FL methods use fixed weight in (1) to obtain the global model. Such global model may be dominated by the majority of the data distributions in the network and is hard to personalize for a minority group with unique data patterns. On the contrary, our method can produce a personalized weight so a node from the minority group can still find and collaborate with its peers.
BO recently has also been studied actively by the machine learning community. Many efficient optimization algorithms have been developed recently for BO, including but not limited to Chen et al. (202 lc:);; Ghadimi & Wang (2018); Hong et al. (2020); Guo et al. (2021); Ji et al. (2021); Grazzi et al. (2020). However, these algorithms are designed for a single-machine setting and may not be communication efficient if implemented directly in a distributed environment. There are much fewer studies on BO in a distributed setting. The recent works (Li et al., 2022; Tarzanagh et al., 2022) consider BO where both the outer and inner problems are defined with the expectation over data distributed across nodes. They analyze the communication complexity of their methods in non-convex setting. We propose different FL. algorithm based Local-SVRG because our problem (P) has finite-sum structure that allows periodically going through all the data points in each node to obtain exact gradient information and achieving lower communication complexity than Li al. (2022); Tarzanagh et al. (2022). (Chen al., 2022) consider decentralized BO problem and their algorithm for the deterministic case can be applied to our problem and achieve the same communication complexity in the non-convex case. However, we include the results for the convex case and focus more on the generalization performance of the federated learning based on BO.
GENERALIZATION PERFORMANCE
The following assumption on (P) is made for analyzing the generalization performance of ((w) in (P) and the convergence property of the optimization algorithm for solving (P) in Section 4.
Assumption 1 (Well-behaved function). The following statements hold. (1) I(0;=) E [0. and (1(0;2) is Ei-Lipschitz continuous in 6 for any E Z. (2) Lx(() and (0) are to and b Lipschitz, continuous, respectively, for k K. (3) Ta (0) is je-strongly convex k E K.
These are standard regularity assumptions recent literature on bilevel optimization (e.g. Ghadimi & Wang (2018)). Assuming the strong convexity in the lower-level problem, (1) has unique solu- tion so that the inclusion there can be replaced by equality. Similar to Lo in (P), we define
(0) == E Ex-pa [1(6; 2)] for le E K.
and we consider the following auxiliary problem
W arg min WEAt k
F(w) (o(w)) s.t. ((w) E arg
argmin min Σx wLLL(0))
(P.)
Problem (P) can be viewed as an empirical approximation of (P.) in both inner and outer problems.
Even if all p 's are different from Po, it is still possible to learn 0* correctly by solving (P.). A simple example mean estimation is min E(((w)) =0 s.t. ((w) arg orgming Σ wg 2x )2
3

---

Under review as a conference paper at ICLR 2023
where 20, and 22 follow normal distributions (N 1), (a,, 1) and (((a, 1), respectively, for any a * O. Obviously, w* = (0.5, 0.5) is the optimal weight and ((w") = 0 = 8". Throughout the paper, we assume 0* can be learned by solving (P.), .). which is stated formally below.
Assumption (Learnability of 8" by (P.)). ((w)) = 6" for any w E WW, where 6* satsifes (P).
Besides the situation like the aforementioned simple example, Assumption 2 holds obviously when Pk = Po for at least one k E K. In fact, the latter case happens when node 0 is a node in K, so equal to a refined generalization performance analysis for the latter case, so we state the latter case as a separate assumption below.
that node and zero others is optimal. Moreover, will later on provide
Assumption 2' (Existence of identical neighbors). There exists a strict subset I C K. with |J| such that pk = for & E J. Moreover,
w w E Ak wx = 0 EX
The first statement in Assumption 2' implies that the right-hand side of (4) is contained by the left-hand side. The second statement further assumes that they are equal. Assumption 2' implies Assumption 2 because Σ W/ L (0) (o) for any 0 E O and any E W satisfying (4). Assumption (Error bound condition). There exist C, > 0 and r 2 1 such that
1/r
Dist(w, w*)
min 'W
Iew- w'll S C. F(w) min F(w) tEak
(5)
Inequality (5) means problem (P.) satisfies the error bound condition, which has impact on the convergence property of many optimization algorithms (Johnstone & Moulin, 2020; Yang & Lin, 2018; Lewis & Pang, 1998; Pang, 1997; Lin et al., 2020). Due to the limit of space, we refer readers to Appendix B for practical example satisfying Assumption 3.
We are interested in the generalization performance of ((w). represented by the gap Lo (o(()) LO()") , as both D and Durin grow. For simplicity of notation, we assume ni Rarain for any k E IC for some integer Rarin > Tevaldd To facilitate the analysis. we need to introduce few notations. Given probability measure Q on 2, let H. = {1(0:-) : E θ} be pseudometric metric space equipped with the pseudometric metric pQ. which is the L.2 distance metric with respect Q. i... Po( = V ([2((() - PdQ()) for 1,1 E H. The ball with radius e > centered at I H is defined as B.))) == {!' H|po(l, S e]. Let (HH; pO, e) be the e-covering number of H. with respect to pq, i.c., NNH e) == min ml..m. Im E H. H c B.
Following Chen et al. (2021a), we make the following assumption on ((H; pq, e). which is impor- tant for analyzing the generalization performance (Koltchinski,, 2006; Kakade et al., 2008).
Assumption 4. There exist CH and VH > such that, for any probability measure Q on Z.
N(H: < (CH/c)TM
Ve >>
With the these assumptions, we obtain the following theorems whose proofs are in Appendix D. Theorem (Bound independent of statistical distance). Suppose Assumptions 2 and 4 hold. There exists a universal constant* C > 0 such that, with probability of at least 1 - 5,
La Lo(ā( Lo S C, (MH + log(1/8)
7 + CC
Co vi
+ K log(1/6) ("M
(7)
nivatid
Teruin/ (Kb2)
Under the same assumptions, the generalization bound by Chen et al. (2021a) becomes
Lo(0(w)) - Lo(0)) sc, PH + log(1/0)
V
(Nw + K log(K)) + (1/())
1
C
Thvalid
K Kriesin
Lo(((w)) (o'
(8)
We define a universal constant as constant that does depend any parameter of the problem except Cn and C,. This definition is made only to simply the constant factors our bounds.
A (p. Cp transfeareee assumption is needed in Chen et al. (2021a), which also holds in our case with p 2 because of the Lipschitz continuity and strong convexity assumed in Assumption I.
4

---

Under review as a conference paper at ICLR 2023
for universal constant C. and any satisfying 3 I wk/w; I with k * j for some 3 0. However, it is likely that the optimal solution w" has zero components (c.g., when Pk = Po for some k). so, 3 on the right-hand side of (8) needs to be arbitrarily large for T( w²) in (P) to satisty the aforementioned condition. Moreover, when w w, the convergence Lo(O(w)) - Lo (0*) in (8) is not characterized in Chen et al. (2021a). On the contrary, Theorem holds without any assumption on i (zero components are allowed), does not depend on and provides a generalization bound converging in every term. 3 When b c/ K with a constant c 2 1, the right-hand side of (7) improves the first two terms on the right-hand side of (8) by a log( K)) term.
the last term
The bounds (7) and (8) may both dominated by the O(1/ /Tvalii) term, which is the same as the generalization bound achieved simply by learning locally with D (see Proposition 1 in Ap- pendix E). However, if Assumption 3 holds and Assumption 2 is strengthened to Assumption 2', we can establish generalization bound different from Theorem which suggests that (P) can still outperform local training when the following statistical distance between Po and p& 's is small:
G maxage ΣtEK (Lo(0) (x))²
Theorem 2 (Bound dependent on statistical distance). Suppose Assumptions 1, 2', and 4 hold. There exists universal constants C. > 0 and C > such that, with a probability of at least 1 - 36,
C.. V/H + log(1/0) 2
( VVH + K log(1/6) d
Eu V
Dist( W*) S EVioolid Hemai))
Cw
(10)
Thyatid
Thanii (K62)
and
un + J log(1/6)
@(hroliid Teyain ) (K J)
Lu(O(w)) Lo(0") S CCp
C.
bv + 22 2e(Pnatids Perain G, (11)
N
Murii where No = 3²J+ (K-J and G is defined in (9).
Note that Ng- (nrrinn) Based on the decreasing rate of E( Perain) in (10), simplify (11) by only showing the bounds in terms of Twvlid, Temin and G for a clear comparison with local training. Corollary 1. Suppose the assumptions of Theorem 2 hold and Roalid and Thrain are large enough such that (nvalid, Derain) defined in (10) satisfies (Moralidd Terain)
I
With probability of at least K-J-
byJ
1 35, we have Lo Lo(O()) Lo(0r)= SO 01/1/11 (1/mirain + G (1/n valid
1/n 1/mmaun)
3 3- and G = o /myliia). the bound in Corollary becomes oLL/T meaning that method (P) has better generalization guarantee than training locally. Since G is small in this case, a natural question is whether optimizing the weight in (P) still needed because the FL with equally weighted nodes may already have a good performance with respect to po- However, we show in Proposition 2 in Appendix E that (P) is still preferred to FL with equally weighted nodes for any G. We show the impacts of and K through Corollary in Appendix D.
When G = o(1/n
FEDERATED BILEVEL OPTIMIZATION ALGORITHM
Although our main focus the generalization performance of (P), we present a federated optimiza- tion algorithm for (P) based on the existing techniques by Gorbunov et al. (2021) and Ghadimi & Wang (2018). Different from a single-level optimization problem, the outer objective F(w) in (P) depends implicitly on through the inner optimal solution 0(w), which makes the exact gradient V F(:)) difficult compute. A commonly used solution is to exploit implicit function shown in the following lemma, which is from Lemma 2.1 and 2.2 in Ghadimi & Wang (2018).
Lemma 1. Under Assumption I, V is L--Lipschitz continuous with
E (280h
/ K
K&
(12)
4aa
"s by-product of our analysis, we show (38) that To (0(()))) Lo(0") also satisfies (7).
5

---

Under review as a conference paper at ICLR 2023
Algorithm 1: Local-SVRG method for (16): Local-3VRG((fui) w, x00) ,,, YY, T,T,q.22
Input: functions {fk,i), weight initial vector (0)) R learning rate 7, communication period т 2 1, probabilityy y of updating reference point, and the total number of iterations T 4 (0) = x1( 3/ x²(), k l K K
for t 0.1.....
do
for k = l..... K in parallel do
Choose is from (1,.... n&} uniformly at random
9p. Sk (0g (0) V Sn (yk (2) + V (v((k) (0))
(1)
Ve
(1+1) (2)
4 with probability q and Vk ((+1) Uk
with probability 1
if + mod+ T = 0 then
Jk (1+1) (1+11) 2km1 wk [k 79k
(t) (2)
else
(1+1) (1) - -9
(e)
11
1/
end
13
end
14
end
Return: (77) UT ΣT ua)l with ut (1 minffy4./44)) (++1) -(++1) and Ur Σt ur
15
and =V& where V ((w) is the partial derivative of F w.r.t we and v+F(w)= = - ((w))
EE wy v (Q(w))) Vio(((w)).
(13)
By Lemma 1, computing V ((w) requires solving (1) exactly and taking the inverse of the Hessian matrix in (13), both of which are challenging. Hence, for given w, we will find an approximate
solution of (1), denoted by ((w)(<> 0(w)). and approximate the matrix inversion (13) by solving strongly convex quadratic program. In particular, we will approximate V ( by
vf(w)= =
with v+F(w) == -(ww) h arg min, hht (IK W wxLzLx h VLo(O()
(14)
where
,
(15)
Both (1) and (15) can be written as distributed finite-sum sum minimization K weighted nodes:
mingeRs f(x) = Σt=1 wxfx(z), where fa(z) = nu Σn fx,(z)) k L....,, K. (16)
When (0) = 1(0:2 (0)) (16) becomes (1). When (k)( + (0))
TT (T (((w)), (16) becomes (15).
With this observation, apply Local-SVRG by Gorbunov et al. (2021) to the aforementioned two instances (16) to obtain (ww) and h, which are used to construct the approximate gradient F in (14). Then we update w using V F(w) based on the accelerated bilevel approximation method (ABA) by Ghadimi & Wang (2018). We choose the combination of Local-SVRG and the ABA methods because it leads to the lowest communication complexity in literature for solving (P). We formally present this approach in Algorithms and 2. Recall that we have assumed Dvalid stored in node 0. which is called center in Algorithm 2.
In each iteration of Algorithm 2, in addition to the communication within Local-SVRG, constantly many rounds of communication are needed to exchange ((*), (=) (o.(o) and VL (0(=)) be- tween the center and node k. We present the communication complexity of Algorithm which can be proved by adapting the analysis in Gorbunov et al. (2021) and Ghadimi & Wang (2018) to our setting. The proofs are deferred to Sections F.I and F.2.
Theorem 3. Suppose Assumption I holds and F F(w)) Lei = max [θ(w)] and
min
1
9
(17)
806, 4 21/50lr 1)] 16/(1-
4

---

Under review as a conference paper at ICLR 2023
Algorithm 2:
Federated Learning Method for Bilevel Optimization (P)
Input:
initial weight w(), learning rate training data ia for &o E K., validation data D the number of outer iterations S, parameters (7's T,9) for Loca SVRG, and the number of inner iterations T5 for O
Set Wag
(0)
(()
for
0,
...... 5-1--11 15-11 do
udd
(e)
#+2 #42
2 (() (6]
w
Wag
(e)
Compute ( follows:
Set (0) (0 )
i= -,.,..,, nk, k -=,,...,
Compute ((+) = Locall SVRCIf- w md ((+-1),, 7, q, q,,) and send it to each
node.
Compute (I. at center and send it to each node.
Set (h. = / (((()) 2 (2) hh - h (o(e)), i= 1= nk. == 1......AA
Compute (+) Local 1 1- SaaaalsssRGG...c. (IR,i) (a) (T)()())), r, T,) and send it to each node.
10
Each node computes (((+)) in parallel and send it to the center.
11
Set Vú ((
V T4 (0(+)) (()) for k ....., K
w( (++11) arg min WE
v F ), w + m(++1) | w())
13
(a+1) arg wiag we
<v (a) w + 2n w -
14
Wag
15
end
(9) Return: Wag
Suppose 1) 36f in Algorithm 2 with E defined as in (12). There exist constants A A₂ and As that only depend to. E,, Bz, μ1, R. q and K but not T such that the following statements hold.
In (Ar(st1)") Suppose 1, 7 % and T, Tap
Algorithm 2 finds an c-optimal solution of
(P) with Ô (e 0.5) rounds of communication.
Suppose 1, =
1 M,
and T. = - M In (M2), where
M. max 11700. (s 1)² VTA + A2(T 1) As(T - 1)91 0, 0.1.....
(18)
Algorithm 2 finds an e-optimal solution of (P) with Ô (c-1.5) rounds of communication.
When F. in (P) is non-convex, we aim at finding an e-stationary point of (P). Following Ghadimi & Wang (2018), we apply a standard proximal gradient method to (P) based on the approximate gradient (ww in (14). This method and its analysis are standard and we include them in Sec- tion F.3 due to the limit of space. In Remark 1 in Section F.3, also show that the complexity of our method is lower than those of Li et al. (2022) and Tarzanagh et al. (2022).
NUMERICAL EXPERIMENT
In this section, we demonstrate the performance our methods on image classification tasks. We compare our method, denoted by Bi-level, against four baselines, including (1) Local-train, which solves minøge (o) locally; (2) FedAvg (McMahan al., 2017), which solves (1) with wa 1/K; (3) Ditto (Li et al., 2021); and (4) PFedMe (T Dinh et al., 2020). Ditto and PFedMe are two personalized FL methods. We apply all methods to train convolutional neural network (CNN) on multiple image datasets: Fashion-MNNIL (Xiao et al., 2017), MNIST (Deng, 2012), CIFAR- 10 (Krizhevsky et al., 2009) and downsampled 32 32 ImageNet (Chrabaszez et al., 2017). We

---

Under review as a conference paper at ICLR 2023
F-MNIST
MNIST
CIFAR-10
DS- DS-ImageNet
1.
0.5
0.29
04
Setting
5.0
14-
Lecakerah
Lock-ran erah
Lock erai
0.15
0.10
protme
Citss
preaeee
CRts
preceic
0:05
phore
233
of
Narker of Sync
Setting
Leak-ma
0.15
Fashug
Fackeg
0.10
faclog
02
Cits
12
Ceto
Dito
0:93
253 500
2007
253 500
2005
155
200
135
2000
135
520
130
2000
Setting
2.0
trai. Dats
Lockl main
Lock miin
main
Cets
Dito
pladme
pladee
plecms
placmn
253
2011
500
6.0g
150
Nunter Syndesriziio
Numier Syndesniuuiii
Murterr of Synorontaettte
Number Syrcrontaiioe
Setting 4
0.0
0.0
0.5
2.
0.20
14
deee resta)
6.15
reeta)
6.10
02
64
153
500
753
355 500
755
2005
200 411 203
000 1000
250
530
126
1006
Figure 1: Comparison in test accuracy for the minority group vs number of synchronizations.
denote Fashion-MNIST and downsampled ImageNet by F-MNist and DS-ImageNet, respectively. See Appendix G for more details on the CNN and the computing environment we use.
We use mini batch of size 50 to construct the stochastic gradients in all methods. In the Bi-level method, Algorithm 3 is applied to (P) with b 1/3 and five epochs are performed within each call of Local-SVRG (i.e.. T. = 750m. We set 1/50, choose y from {0.05, 0.02, 0.01} when solving (1) and from {0.0005, 0.0002, 0.0001} when solving (15), choose T from {10, 20), and n from f0.025, 0.02, 0.015). We choose the combination that produces the highest validation accuracy after five outer iterations. SVRG is applied to minøge (o)) in Local-train and Local-SVRG is applied to (1) with wi = 1/ K in FedAvg. Parameters т, q. and in FedAvg and Local-train are set the same in our method. Ditto is implemented by setting S. = K., r T, 8 25 and fl m ? in Algorithm 2 in Li et al. (2021), where and 7 are set the same as in our method. Similar to Li et al. (2021), we choose À in Ditto from {0.05, 0.1, 0.2) to maximize the validation accuracy after five outer iterations. pFedMe is implemented by setting 3 = 1, 6 0.005, Rt = t and 1j y in Algorithm in T Dinh et al. (2020) with 7 and 7 set the same as in our method. Each subproblem in PFedMe is solved by gradient descend with a maximum iterations of 20. Like Li et al. (2021), we choose À in PFedMe from (5, 10, 15) to maximize the validation accuracy after five outer iterations.
We set K. = f1,.... 15} (i.e., K = 15) and partition it into two groups, minority group Jm (1..... 5) and a majority group JM = (6...., 15).. We then generate Dimin for k E K. by randomly sampling data from the training sets with some artificial distributions, such that the data distributions (i.e., Pk 's) are the same within each group but different between groups. In particular, we create the data distributions of Jm and Jas under four different settings. In Setting 1, create two different distributions over the classes and use them to sample Dimin with k E Im and & E JM. respectively. In Setting 2. Setting 3 and Setting 4, we first sample data in the same way as Setting 1 and, additionally, we permute the class labels among a few classes in Dimain with k E Jas under Setting 2, rotate each image in Dimin with & E JM by 90 degrees in the same but random direction under Setting 3. and do both under Setting 4. This creates nodes with different levels of heterogeneity.
To compare the performances of the methods on both groups, we conduct two sets of experiments under each setting, one with po being the distribution of Jm (i.e., I Tm.) and the other with
8

---

Under review as a conference paper at ICLR 2023
F-MNIST
MNIST
CIFAR-10 110
DS- -ms-maeeNet
0.20
Pa Minority
8.19
6.15
Smilrr locka
Sindar lecia
Cantar Modea
Similar Hode boxl woggl
110
6:30
0.10
tser ways
Essul ledys
Exsal waggi
1.00
0.00
6:05
1.00
2:00
LS0
6.00
6:93
Narker bytc coseeaattiin
Pa is Majority
1.10
0.10
6.10
0.10
1.00
1.00
5:00
6:03
Simler Vodks
mii Neees
Simiarr Modes
ss for Neees
0:00
Stnnirr Nodes
siseea Socee
6:30
Stedla Nodes
Dasive Modes
wayet
ledgye
wegee
woghl
5:00
0:00
0:00
SE0 sumver Sysirrriooiiee
1993
500 Marber Suncwennarers
Aurker Spsiierronna
Marver of Sanovennssaass
Figure 2: How w evolves during the Bi-level method under Setting 1.
Po being the distribution of JM (i.c., J JM). D is then sampled from po. For out-of- sample evaluation, we generate testing data by sampling from the testing set of cach dataset using distribution Po described above under each setting. We denote the testing set by Dies and let Ries |Deat] We repeat all experiments five times using different random seeds. The values of Rivaidd Parain Nest and the details of data generation are presented in Sections G.1, G.2 and G.3.
We plot the test (top-1) accuracy each method obtains during iterations for the minority group in Figure 1, where the horizontal axis represents the number of synchronizations, i.e., the rounds of communications the method performs. Since Local-train does not require any communication, we just plot horizontal line positioned at its final accuracy. Due to space limit, we present the accuracy for the majority group in Figure 7 in Section G.4. We also report the same results in Figure 8 and Figure but the horizontal axis there represents the cumulative number of data points each method processes in parallel. In each figure, we show the confidence intervals of the curves as shaded areas.
According to Figure 1, our Bi-level method performs better than the four benchmarks on the minority group on all datasets under all settings. Local-train does not perform well because it only gets access to a small amount of data. The poor performance of FedAvg is because of the heterogeneity we created across nodes. In fact, FedAvg is even worse than Local-train in many cases, especially in Settings 2, and where the heterogeneity is high. This is consistent with the findings in literature. Although Ditto and pFedMe are designed for heterogeneous nodes, they still use fixed weight on each node to train a global model, which may not provide a good starting point for personalization due to the high heterogeneity. In fact, their performances drop more or less as the data heterogeneity increases from Setting to Settings 2, 3 and 4. On the contrary, by updating the weights, our method filters the information in the network and help the node in the minority group find its similar peers and produce a good model through gnora-group collaboration. Comparing Figure 1 with Figure 7, we find that the performances of FedAvg. Ditto and PFedMe are improved on the majority group. This is again because they utilize the information aggregated from all nodes, which is in favor of the majority. However, our method perform similarly on both groups and is still overall the best for the majority group. Similar phenomena are found in Figure 8 and Figure 9.
In addition, we also plot in Figure 2 how the weight wa for each node evolves during the Bi-level method under Setting 1. We show the results when Po is the distribution of the majority and the minority groups separately. In each case, we call the nodes in J similar nodes (to node 0) and call the others dissimilar nodes. According to Figure 2, method successfully detects similar nodes in both cases and increases their weights but decreases the weights of dissimilar nodes. We present the weights under Settings 2, and 4 in Section G.4. Similar phenomenons observed.
CONCLUSION
We propose FL approach on a network with weighted nodes and develop a federated bilevel op- timization algorithm to optimize the weights based on the model's performance
validation set. We analyze the generalization performance of the resulting model and identify the scenarios where method theoretically outperforms training with local data and FL with even weights.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Jock Blackard and Denis J Dean. Comparative accuracies of artificial neural networks and dis- criminant analysis predicting forest cover types from cartographic variables. Computers and electronics in agriculture, 24(351131151, 1999.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymp- totic theory of independence. Oxford university press. 2013.
Shuxiao Chen, Koby Crammer, Hangfeng He, Dan Roth, and Weijie Su. Weighted training for cross-task learning. arXiv preprini urXiv:2105. 14095, 2021a.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Advances Neural Information Processing Systems, 34, 2021b.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. A tinll-ttimescale stochastic bilevel optimization method. arXiv preprint Sitiv:2002.046777 2021c.
Xuxing Chen, Minhui Huang, and Shiqian Ma. Decentralized bilevel optimization. arXiv preprint (rXiv:2206006670, 2022.
Patryk Chrabaszez, Hya Loshchilov, and Frank Hutter. A downsampled variant of imagenet as an alternative to the cifar datasets. arXiv preprint arXiv: 2017.
Benoît Colson, Patrice Marcotte, and Gilles Savard. Bilevel programming: A survey. 4or, 3(2): 87-107, 2005.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- hi- erarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255. leee, 2009.
Li Deng. The mnist datahase of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-142) 2012.
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Adaptive personalized federated learning. arXiv preprint arXiv:2003. 13461, 2020.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning: A meta- learning approach. arXiv preprint arXiv:2002.07944 2020.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint /002.02800222244 2018
Pinghua Gong and Jieping Ye. Linear convergence of variance-reduced stochastic gradient without strong convexity. arXiv preprint arXiv: arXiv:/406.1 102, 2014.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local sgd: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics, pp. 3556-3564.
PMLR, 2021.
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration com- plexity of hypergradient computation. In International Conference on Machine Learning, pp- 3748 3758. PMLR, 2020.
Bin Gu, De Wang, Zhouyuan Huo, and Heng Huang. Inexact proximal gradient methods for non- convex and non-smooth optimization. In Proceedings of the AAAI Conference Artificial Intel- ligence, volume 32, 2018
Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. On stochastic moving-averas estimators for non-convex optimization. arXiv preprint arXiv:2104.148/ 2021.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. arXiv preprint arXiv:2007.051/70 2020.
10

---

Under review as a conference paper at ICLR 2023
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pp. 4882 4892. PMLR, 2021.
Patrick R Johnstone and Pierre Moulin. Faster subgradient methods for functions with hölderian growth. Mathematical Programming, 180(1):417-450 2020.
Sham M Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction:
Risk bounds, margin bounds, and regularization. Advances in neural information processing systems, 21, 2008.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pp. 5132-5143, PMLR, 2020.
Vladimir Koltchinskii. Local rademacher complexities and oracle inequalities in risk minimization. The Amnals of Statistics, 34(6):2593-266) 2006.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:/610.05492 2016.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Jason D Lee, Qihang Lin, Tengyu Ma, and Tianbao Yang. Distributed stochastic variance reduced gradient methods by sampling extra data with replacement. The Journal of Machine Learning Research, (81)):44044446, 2017.
Adrian S Lewis and Jong-Shi Pang. Error bounds for convex inequality systems. In Generalized convexity, generalized monotonicity: recent results, pp. 75-110. Springer, 1998.
Daliang Li and Junpu Wang. Fedmd: Heterogenous federated learning via model distillation. arXiv
preprint arXiv:/910.0355 2019.
Junyi Li, Feihu Huang, and Heng Huang. Local stochastic bilevel optimization with momentum- based variance reduction. arXiv preprint arXivv2205.01600 2022.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Sys- tems, 2:429-450, 2020.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. International Conference on Machine Learning, pp. 6357- 6368. PMLR. 2021.
Xianfeng Liang, Shuheng Shen, Jingchang Liu, Zhen Pan, Enhong Chen, and Yifei Cheng. Variance reduced local sgd with lower communication complexity. arXiv preprint arXiv: 1ete. 12844, 2019.
Qihang Lin, Runchao Ma, Selvaprabu Nadarajah, and Negar Soheili. First-order methods for convex constrained optimization under error bound conditions with unknown growth parameters. arXiv preprint wwXiv:20100152661 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficiii learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1288 PMLR, 2017.
Jong-Shi Pang. Error bounds in mathematical programming. Mathematical Programming, 79(1): 299-332, 1997.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemati- cal statistics, pp. 400-407, 1951.
Virginia Smith, Chao Kai Chiang, Maziar Sanjabi, and Ameet S Talwalkar. Federated multi-task learning. Advances neural information processing systems, 30, 2017.
11

---

Under review as a conference paper at ICLR 2023
Canh T Dinh, Nguyen Tran, and Josh Nguyen. Personalized federated learning with moreau velopes. Advances in Neural Information Processing Systems, 13:21394-21111 2020.
Alysa Ziying Tan, Han Yu, Lizhen Cui, and Qiang Yang. Towards personalized federated learning.
IEEE Transactions Neural Networks and Learning Systems, 2022.
Davoud Ataee Tarzanagh, Mingchen Li, Christos Thrampoulidis, and Samet Oymak. Fednest: Fed- erated bilevel, minimax, and compositional optimization. arXiv preprint arXiv:2205.02225, 2022.
Luis N Vicente and Paul H Calamai. Bilevel and multilevel programming: A bibliography review.
Journal of Global optimization, 5(3):291-306, 1994.
Hongda Wu and Ping Wang. Fast-convergent federated learning with adaptive weighting. /EEE
Transactions Cognitive Communications and Networking, 7(4):1078-108S 2021.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmark- ing machine learning algorithms. arXiv preprint arXiv:1708.07741 2017.
Tianbao Yang and Qihang Lin. Rsg: Beating subgradient method without smoothness and strong convexity. The Journal of Machine Learning Research, 19(1):236-268, 2018.
Honglin Yuan and Tengyu Ma. Federated accelerated stochastic gradient descent. Advances in Neural Information Processing Systems, 33:5332-5344 2020.
Haoyu Zhao, Zhize Li, and Peter Richtárik. Fedpage: fast local stochastic gradient method for communication efficiient federated learning. arXiv preprint 00814 2021.
12

---

Under review as a conference paper at ICLR 2023
A
SUMMARY OF NOTATIONS
Symbol
Definition
Z
Sample space
Po
An unknown ground truth distribution on Z
D
Validation set i.i.d. sampled from Pn and stored in node 0 (or called center)
no
Size of validation set also denoted by Avalid Set of nodes defined by {L....,K} A strict subset of K.
K
J
J
Size of J
Pk
The distribution on 2 in node k, k = 1..... K Training set i.i.d. sampled from pæ and stored in node k, k 1,....
k
Size of training set Dirain
ng
Vector of weights defined by (W1, (w1,..., wx) E [0, 1]K
b
A user-defined parameter in [ 1] Capped simplex where comes from
A
0
Vector of model parameters
θ
Set where & comes from Loss of 9 on data point from the space Z Empirical loss on D
100; 2)
(o
(x)
Empirical loss of on Di k == I,...,K K
()
Generalization loss of on Po
())
K Lipschitz constant of [(0; z) E [0, and VI(O; 2) for any =
Generalization loss of 0 on Pa, k 1.....K ..K
l
to
Lipschitz constant of all (0) for k E
Lipschitz constant of all v2 (0) for k E
parameter of strong convexity of La (0) for k K.
p
G
Statistical distance between po and pk 's defined in (9)
F(w)
The objective in the bilevel optimization problem (P)
F(w)
The objective in the auxiliary problem (P.)
0 w)
Optimal solution of FL on weighted nodes formulated (1)
g"
Optimal solution of the learning problem (P)
W
Optimal solution set of the auxiliary problem (P,)
@
Optimal solution of the bilevel optimization problem (P)
y
Learning rate Communication period
r
q
Probability updating reference point in the Local-SVRG method
S
Number of stages
T.
Number of iterations stage E ,
Table 1: Notations used throughout the paper.
B EXAMPLES SATISFYING ASSUMPTION
We consider (P.) ) in the setting of linear regression. Consider data z (x, v). where RRd is feature vector and E IR is a continuous target variable, and consider the quadratic loss 1(0; z) = 2) We assume x in all nodes, including node (center) and the nodes in IC, follows the same distribution, and matrix E. [[xxx T] is non-singular. Moreover, we assume that there is vector 0% E ad associated to node kt and in node is generated as y = x 0% + c for = 0, 1..... K, where eg is zero-mean random noise indepedent of x. In this problem, we have
] 0x -0-----2
(0) [x 0 - y) 1 (xx - r IT 0 )x = } 0%) TE rx (0 0 + [
We can easily show that ((w) in (P.) has the closed form (ww) = Σk= w which means
F(w) (o)(ww) KK wn 0%) Ixe
K k=
O 0 [
13

---

Under review as a conference paper at ICLR 2023
This is quadratic function of over the polyhedral set A and thus satisfies the error bound condition (5) with r = 2 according to Lemma in Gong & Ye (2014).
C TECHNICAL LEMMAS
In this section, we provide some technical lemmas with proofs which are necessary for establishing the main theorems. The main steps in the proofs of Lemma and 3 are borrowed from Chen al. (2021a). However, the generalization bound in Theorem satisfying 8-1 I ws/w; / 3 with k * for some 3 > O, and their bound increases with 3. When applied to w = with zero or nearly zero components (that happens when pk = Po for some k), such a 3 is very large equals infinity. Therefore, to extend the results for a generic w and a w that is E-away from W (see Lemma 3) where the components can be nearly zero. These extensions are important for proofing our main theorems.
in Chen al. (2021a) is for
make necessary changes in the proofs
Lemma 2. Suppose Assumptions and 4 hold. There exists universal constant Co > 0 such that, with probability of at least -, 6,
Vu + log(1/6)
sup Lo(0) Lo(0) E
(o()) S Coy
Toyalid
Proof. For simplicity of notation, we write Revalid as n in this proof. Let
Gvalia (Dvalid) sup Lo( - Io(0)] and Gyyaial (Dvalid) AE
[o(0) Lo(0)]
sup BEE
Consider any 21,2,.... ...., n... Let Dyalid be the another data point 21() sampled from po. Recall (3). We have
Dvalid except that 200) is replaced by
Gvalid (vvalid) - Gvalia (D
Lo( - to(0)] sup AE
Lo(0) Lo(0)+ -
1 -10
- n.
sup AEB
where the inequality is because the loss is [0, 1] (Assumption 1). This inequality means we can apply the McDiarmid's inequality to obtain that, for any <>> O,
(Grali ( 2 IE[Gvatia (Dvalid) + +) & exp(-22 222 or equivalently, with probability of least 1- 8,
log(1/8)
Gvalid Gvalid (Dvalid) s E[Givald (Dvalidy]
2n
Next, we apply the standard symmetrization argument by introducing ghost dataset
Valid
ghost
i=1
which is independent of Dalldd and sampled from po- Let {o,) be Rademacher random variables. We have
E|G D Dralid))
=E
sup
(o( - Faceo] = E
sup
E
[L:((:
phhost) - I(0; D Dvalid)
AE0
AE0
E
sup
L(0: Dralid) - L(0; Drald))
= E
sup
-
1
Σ (1(0:2(00) - ((0 -((00))))(()))) ((0:2(0)) 1=1
DE
OE
<2E
sup
azl( 200)
22E,,
AE
i=1
where (H) = E
sup 1 Σn (0))0
Dvalid and 7 (1(00-) 0).
AEE
14

---

Under review as a conference paper at ICLR 2023
Let Mo JR Ei=1 a,1(0; for A E e. By Hoeffding's Lemma, have for any 0,0 8' O
exp (A(MB - Mer)) pralid
-(00== -1(0:)()))((0)=00))))
D
E
exp
vn oi
i=1
X²
(1(0==(0) - -1(0;=
X2 exp ( dP()))))
exp
2n
where
d(0,0') =
((0::(())((((;=(0)))) S
the Le-distance between mappings (0;-) and ((0":-) with respect to the empirical distribution over D and is pseudometric in H. Hence, by Dudley's entropy integral inequality (see Corollary 13.2 in Boucheron et al. (2013)), there exists universal constant Cd such that
(H)
E sup Me Dvatia
S
Cd V
lo
Vlog (N(H; d: d))dde
Vn
Lage
According to Assumption 4, we have
2Ca
vn (''
CC
Griin
< 22)n(H) -
/
/uylog
de
Hence, with probability of at least 1 6,
2Cd
CH de +
log(1/6)
Gvalia vallid I Vn
/ Vou log
2n
Applying the same argument to ('vaiia
(Dralid), we can show that, with probability of at least 1 - 6
2Ca
log(1/8)
I
V log log
de
Vn
2n
By union bound, we have, with probability of at least 1 -
sup
Lo( - Eo(0)
2Cd Vn
S'')
You yuulog log
CC
de
V
log(2/8)
2n
which completes the proof.
Given 0, we define
W = {w E & Dist(w, w. W*) S
(19)
Terain
N: 62 b2
(20)
Lemma 3. Suppose Assumptions 1,2 and 4 hold. There exists universal constant C. 0 such that, with a probability of least 1-8. 8,
sup BE WEA
Σ R=1
K
wk
[n,(0)
S sCap
VH + K + log(1/0)
(21)
Terriin / (Kb?)
Suppose Assumptions 1, 2', and 4 hold. There exists universal constant Cy O such that, with a probability of least 1 8.
sup wE
Σ Wk k=1
[x(0)) - Lx(O)]
SC, (V
(Von
Vn + J log (1/6)
E(K
[(K-J) J]
bvNo )
(22)
No
15

---

Under review as a conference paper at ICLR 2023
Proof. We prove (22) first. Suppose Assumptions 1, 2', 3 and 4 hold. By Assumptions 2', have w = O for w E W and E K,,, which means wy S VKKee w s Dist(w, W S e for any w E W and j E KAJJ.
Let
K (4(0))Ix((0)
Guain D ttriin
sup BEe
(23)
Giran ( Duriia
sup WE
Wkk [Tx(0) -
(24)
Consider an index j E (1,2...., K and i E {1,2,.... n2}. Let Diain be the same as Dtrain except that 2)
(9) is replaced by another data point 2)
(()
sampled from Pj. Recall (2). We have
Grain (D)rain))
Guain Graain (D
Wk [x(0) - En(o)]
sup WEE
K
(1((:1))) -
(n) -2((0]
+ Wij n2
-1 (0:2300
sup DEO,EEW;
k=1
b
jEJ jE KNJJ
(25)
flj
ny
With this inequality, we can apply the McDiarmid's inequality to show that, for any > O,
-2 -
I Graii (Dirain) 2 m (triii)) ] exp
12 + =
which implies that, with probability of at least 1 8,
log(1/5)
Girain (Dtrain) S
Grain (Dirain) }
(26)
N
Next, we apply the standard symmetrization strategy by introducing ghost dataset Draiin ghost
Dimin ghost k=1
K
where
Dirain R.ghost
{
((8) ni 2/
Ji for k I...,, K
is a dataset independent of Diain sampled from ps. Let ( for k: == 1, I,.., K be Rademacher random variables. We have
wk [L((0) - [x{( }
E(Gurain [iraann]]
E sup OE
E [u(( Disinoaa -Lx(0) }
sup
Wk
AE W
K wkk
- Ex(()) }
<
E
sup
Lu(0; Disin
k=1
TkiiWk
(1(0; (101) (100)=10;==11
1(0;=1 (00
E
sup
0E0, W k=l
K nk
Tk uk I(0) (00) = R W,),),, (27)
<
2E
sup
@EB,
km
16

---

Under review as a conference paper at ICLR 2023
K
where Rmmm (H, W:) = E
sup
Σ
(0;; Dusin and H - {100::)0E0}
BEE WEW
k=
K
Let Mo
== VN=
" I(0; 2x for A E θ and wo E W Hence, by Hoeffding's Lemma,
we have
E
exp
(A(M
Mgg ser,,wr) D
D
K
Tkes AVN
(ua((0:2k)) (11) w/(l(b' (2) D
E
exp
No nk
k= k=1==1 1=1
me
N2
IIII exp
(yyl (ox(((:2(k)) w//(('; =
2n
k=1im1 1=1
X2 exp
2
(0, w. "'',)")
(28)
where
a(00, w. 8'0,'.. w')
K
n2
N (0: (0) w/((0'
= (2))
Naba
NrE²
1
Tumain
Thrin
KEJ
KEK
pseudo distance metric between (1(0; -), w) and (1(0';)), :)), w') in H W Hence, by Dudley's entropy integral inequality (see Corollary 13.2 in Boucheron et al. (2013)), there exists a universal constant Ca such that
S VNe ('' Vlog (N(H x d;;d;
Ca
Rami (H, W²) = VNe
sup NEW
Mg.
Diraia
where N(H x W"; d; e) the e-ooerrngg number of H x W w.r.t. We next need to bound N(H x W d; c). Note that
d² (0, w. 0', ww)
my
No
WKl (0; (0) (0'1((0;= )
n
12
2N
wk (1002k)) (0)) - -(0''=21)) 2
K
2N
- (0'; (0)
(wk
km
i=1
2N 132 (1(0) 2k -1 10)
2
2N
(1(0: (0)) 1(0';
+
ny
ni
KEJ
AEK
K n1
2N
(wk w/)2
n
A=1 1=1
2N
62
(1(0:2 (10 - 1(0';=()))
Viyiin
)
- 1(0': (1()==())) 2
+
Dumain
Dumin
Tirrain
KET
REKT
2.V
||l
w/ w01112
(29)
Merain
We then define a probability measure
N₂
12
Σ
(0)
8 8,09
(30)
Marain
Durain
Mirain
NET
1=1
KEA
17

---

Under review as a conference paper at ICLR 2023
(6)
on 2, where a4 is a point mass 2k Then, can construct e-cover for H x W w.r.t. d by taking the Cartesian product of an 5-cover for H w.r.t distance metric po(l, Puii NN 2 c-vover for W. w.r. the Euclidean dis- tance. According Assumption 4, the former has a cardinality of (2Cn/e) To construct the latter, we create
((=)) ((2)) for 1, H. and a V
(J41JN, --cover for [0, b] corresponding to coordinate in I and create [K- [K-J][J+)N; cover for [0, corresponding a coordinate K'J. (Recall that wy S E for J E (...) Then we take the Cartesian product of these one-dimensional covers and project it to W This provides
V N. 2-cover for W with cardinality of
(i +V VTtrain
()((
([
[eVik J) I)
))
K-J
2
K-J
(31)
V
V
Vitain
be
where the inequality is because N₂
by the definition of Ng- This implies
2Ca
L'' VlogN(H W5; d
E Gurain (Ditain)] S 2mnm (H, W
VN.
(un J] 1) (1) + (K JJ
22 [2oVK= -J
((n++J)
)de
VN
MH + J N₂
22 -J (OKKK-JEVK--
=0
-0-
-0
I/H + J
+0
E((K - -J) b/No
(32)
N₂
where the first equality is because
N(H Wi:d;e) 2CC
V8 x
( ((2EVR
[2vK-- K-J
according to Assumption 4 and (31) and the second equality is by changing variable to 2evK in the integral and the fact that 1 = 0 when 1.
be
Combining (32) with (26), have that, with probability of at least 1 - 5,
(V VN + J + log(1/8)
G Guain (Dtrai)) so
(c(K-J))
[<(K J)
+
N₂
bVN.
Applying the same argument to G for Grain (Dinai)) with probability at least 6. By a union bound, we have, with a probability of at least 6
Glana( (Dvnlid), we can show that the same inequality as above holds
LA(O)] 50 (/ UA + J + log(1/5)
Σ wk [Lx(0) ([x(0)-L((0))
K
+0 1 (e(K-))
((((K-))))
sup wEW
Ne
which completes the proof (22).
Next we prove (21). Since the proof is similar to (22), we will mainly elaborate the parts that are different. Suppose Assumptions 1,2 and 4 hold. We define Grain (Dtrain) and G'ram (" (Dirin) the same
as in (23) and (24) except that W is replaced by the entire domain k- Following the same proof of (25), we have
Guaina (nainnDiriin (Dirain) Guain (Dirain)
Wy < n nij
b for all i E (1,2,.... and j E K.
Then the McDiarmid's inequality implies that, with probability of least 6,
Kb² log(1/8)
Guain (rainnnutainn <
ElGrrain ( (Daring)
(33)
2n
18

---

Under review as a conference paper at ICLR 2023
By replacing W3 with A in the proof of (27), we can show that
E[Guain
D timin) S 2ER (H, Axk)
where Rmam (H, Ak) =3 sup
T 1(0; (3) D
i=1 nx
Let No
defined
as (20) with replaced by b, i.e. No Mumin/ (Kb?). Let M
K
ny
ok. ns
2k (0) for 0 O and E A With J replaced by and No replaced
by N₂ in the proof of (28), we have
x² a² (0 w,,', 0' (,)')) exp
E Tep (A(Ma,0 Mor,w )) Duning
2
where
No wn; (0)) =0x((0
Ngb2
a(0, 0' w')
1
Plrrain
REK
pseudo distance metric between (, w) and (1(0)))), ), w') in H A Hence, by Dudley's entropy integral inequality (see Corollary 13.2 in Boucheron et al. (2013)), there exists a universal constant Ca such that
Remni (H,
E
sup (EO,
Mo. n0 Dirain
S
Ca
Vlog (N(H Aki d; ee)
VNb
VNb
where (HH x Aki d;e) t) is the e-ooerrnng number of H x K w.r.t. d.
Next, we just need bound N(H ; d; Similar to (29), we show that
d2) w. 0' w/)
2NN Perriin
Thran
b2 (1(0: (00)
1(0"; (1))
2.N
w|
w/11
Parain
Parai
MEK
Similar to (30), we define probability measure
No.
6² 8 on E, where 8
Tlasin
Musis
kEK
is point mass at 4 Then, only need to construct an é-cover for H x A by taking the Cartesian product of an _ cover for H. w.r.t. distance metric pa and a v Digan
2 cover for 4 w.r.t the Euclidean distance. According Assumption 4, the former has a cardinality of (2CH/e)uM, To construct a / Tinis
Rimi No 2 cover for A k. we first construct KNN c-cover for [0, b). take its K-fold
Cartesian product, and project it to Ag. This provides
Papit No
2 -cover for 4 with a cardinality
of by byKN Pmnnt
K
[11K This implies (Mp x A diid;e)
20n
UM
[1]
K and thus
E Gurain (Drrain)] < 22 (H, - VNo
2Cd
('
Viog.N x Ak: d; c)de
VNo I' / uu log ( ( K log
-0
WH + K No
(34)
Combining (34) with (33), have that, with probability of at least 1 5,
UH K + log(1/6)
Girain (Dirain) $0
No
19

---

Under review as a conference paper at ICLR 2023
Applying the same argument to G'aaia ( )Dvali),, show that the same inequality above holds for Grrai (Dtrain) with probability of at least - 5. By taking a union bound, we have that, with probability of at least 8,
Σ wh [x((0) -800)-x(00 Ln(o)] So (1
V/ + K + log(1/6)
sup WEB,EEAK
No.
which completes the proof of (21) as N₂ = Merain/ / (Kb2).
D PROOFS OF MAIN THEOREMS AND COROLLARIES
In this section, we provide the proofs Theorem 1, Theorem and Corollary 1.
Proof of Theorem 1. By the strong convexity of the loss function and the optimality of ((w) and (ww in the inner problems in (P+) and (P), have, for any w E Ak.
K
K
1 (10) ((w) 1
S
Σ
we Lx (0()))
Σ
Wk (f(w))
(35)
2
k=
2 ((w) ((w)
2
14
wy (O(w))
Σ
wx (0(w)).
(36)
Adding (35) and (36) both sides leads with probability of at least 1 8,
[(w) - [w)|
K w. k=1
K
Wp La ((())) - Σ we (o + Σ
Σ
wx L (0(w))
vn + K + log(1/))
< 2Ca/
Vw e A
(37)
Terain/ (K62)
where the second inequality is because the first conclusion in Lemma 3. Let w" Projw- (w). Then we have, with a probability of 26, that
F (m)
min F(w)) (o()) [)()("))
WEA k
()))) La(O(w))) (u) ((w)] foll0(w*) -(ww))]
+ log(1/0)
<T)()(()) Lo (0(w") |C0
Thyalid
+ + ((w) + Co (owl((w) -O(w")ll
VH + 1og(1/8)
2Ca [/N K + log(1/8)
52Co1
200 V
(38)
Tivalid
/ Pirain/ (Kb2)
where the first inequality is because of Assumption the second is due to Lemma 2, and the last is due to (37) and the optimality of क for problem (P). Therefore, we can show that, with probability of 26,
Lo (0()) - To( =I ()))))(()))))))))))))))))))))( To (0( ()) + (o())) Lo(O(w)))
<Loll ()) ((0))l (0())) - Lo(O(w"))
log 1/0)
2Ca (Hx + K log(1/0)
$20o
3l0
Memain/ (Kb2)
Ayvalid
where the equality is because Assumption 2, the first inequality by Assumption and the second by (37) and (38). This completes the proof.
20

---

Under review as a conference paper at ICLR 2023
Proof of Theorem 2. Since Assumption 2' implies Assumption 2, the proof and the conclusion of Theorem also hold under the assumptions of Theorem 2. In particular, inequality (38) holds with probability of 1 28. According Assumption 3 and (38), we have with probability of - 26 that
Ux + log(1/0) (1/6)
2aa 1
(UH K + log(1/0)
(i WJ]] - <20o
260
Thyalid
Purain (K62)
Applying the fact that + (s# + t for any s and 0 to the right-hand side of the inequality above, we obtain (10) with an appropriately defined C..-
Suppose Dös W < Prain), which happens with probability of 1 - 25 according to the proof above. We have w E W. with & = <(Dvalid, Phminn) according to the definition in (19). We then decompose the optimality gap of the generalization loss follows
Lo(O(T)) Lo(d))
K Ty ()(
K Wr La (0(
Lo()(T))
Σ
wn Lx
T
T2
K
K
+
Th Tu (T)
Σ
Tr T.(Tx(((0)) +
Wh (0(
Σ
We Ix (0(w))
Ta
K
K
K
+
Ty (((())
Σ
SK La (f(w")
i Lx - (0
(39)
Ts
To
It is clear that T3 I 0 and T3 S 0 by the optimality of (()) and (()) in (P) and (P.), respectively. Moreover, by Assumption 2', we have wj 0 for w E W and E KN... Using the fact that
w E W we have ΣKERYT tf < ( W*) < E², which implies
T
Wk
(To(O(T)) La (((0))
Σ wk (Io(O(T)) (0(( KER
max BEE kEKV
Σ
(Lo(0) (x(1))2
S
max Σ (Lo(0) ² AED
k
kERiS
Using similar argument, we can also show
To
max
Σ
(Lo(0) La (0))²
BEO
KERAT
According to Lemma and the fact that w E W we have that, with probability of at least 1 - ō,
(Von
log(1/8)
+ e(K e(K-J)
T2. Ta s C.
N
b/No
Note that G maxice EkERAo (To(0) (0)) under Assumption 2'. Applying the upper bounds of the six terms (39) and taking union bound, we can show that
(/
PH + J + log(1/5)
+ E(K - -J)
-100())) < 20,
+ 2e (Fivallid Terain G
N₂
b/N:
with probability of at least 1 36, which completes the proof.
21

---

Under review as a conference paper at ICLR 2023
Before prove Corollary 1, we first present another corollary of Theorem 2 where the impact more clearly.
Corollary 2. Suppose the assumptions of Theorem 2 hold and Rovald and Terain are large enough such that E va Prraii) defined in (10) satisfies (Tivaldd: Tiuaii))
by With probability of at least
1 36, have
Lo(O(m)) - Lo(0") s0 (1
PH J + log(1/6)
Thraiin/ (Jb²)
log(1/0)
VH K log(1/6) +
G..
(40)
Poudid
Ravin/ (Kb2)
Proof. Theorem 2 guarantees that (11) holds with a high probability. When s (Tvalid: Rerain) S bvJJ
K-J-
the second term on the right-haud hand side of (11) can be merged with the first term. Also, we have Finit,
Pigin Ne (F (K-) Z [3]46J/((K Jj(K-J)
262 where the last inequality is because
K J 2 1. As result, the first two terms in (11) together has the order of
o
o(
Vu J log(1/5)
Teemin/ (Jbb)
Then (40) is proved by applying the definition of (Nralidd, Ammin) the third term the right-hand side of (11).
Suppose Trrain > Thvalid The first term on the right-hand side of (40) is smaller than the entire right-
hand side of (7). If, in addition, G o(1/m vald (40) are also smaller than the two terms in (7), respectively, so the bound in (40) is tighter than (7),
- *) and G o(1 / - ), the other two terms in
Proof of Corollary Corollary is directly from Corollary (2) by only keeping G, Maman and Thestt in the order of magnitude given in (40).
E GENERALIZATION PERFORMANCE BY TRAINING LOCALLY AND TRAINING WITH EQUALLY WEIGHTED NODES
In this section, we first consider model locally trained only with data D in node namely,
Ovalid E arg min (0)
(41)
AE
where Lo given (3). The generalization bound of Q is well-known, so we omit the proof but directly give the result.
Proposition Suppose Assumptions and 4 hold. There exists a universal constant Co > such that, with probability of least 1 -5
Lo(Oaaia) Lo(O") s 2C0 VH + log(1/5)
Peyalid
For the purpose of theoretical comparison, we also consider model trained only with data Drain distributed over equally weighted nodes, namely,
Dequal E arg min
Σ (.).
(42)
leB
where bg is defined as (2). It is easy to construct an example where each Pk with & E KC is significantly different from that Lo (oegua))) does not convergence to Lo(0*) as Perain goes to infinity. Motivated by Corollary and the discussion afterwards, it will be interesting show the
generalization bound of 0 eequal when each Pk with E KC,JT similar to po with a small G defined in (9).
22

---

Under review as a conference paper at ICLR 2023
Suppose Assumptions 2' and 4 hold. There exists universal constant C. such that, with a probability of at least 36,
Proposition 2.
Lo Lo(Oequa)) - Lo((0) 20,y
Vn
K log(1/6) 2V G.
K Knaaai
K
where G is defined in (9).
Proof. We first define
O Oquual E arg min lee
(0).
(43)
K
1=1
We first decompose the optimality gap of the generalization loss follows
Lo (000quua))) La(0*)
K
1 K
K
Lo (Qequll
1
La (Begual)
La (oqual)))
Σ
(P
K
K
K
km
km1
km
Ti
T2
Ty (Pequa))
1
T.p [. (Bequul) +
1
T (eequu))))
1
Σ
La Lx((euug (Oequal)
K
K
K
K
P3
Ta
K La())) Lo(
L (Poqual))
1
Σ
1 (+*)
(44)
K
13
To
is clear that T3 I 0 and T3 < by the optimality of Dequal and Oequal in (42) and (43), respectively. Moreover, we have
Lo LQquuu)))) - Lu (Qequa))
Σ BEKINT
1
(Lo(Oequai) - La (Oequal)
T
K
1=
K
Σ
Ln - (0))
max DEG
K2
NEAT
Using similar argument, we can also show
To <
K K2
max DEB
Σ
K (Lo(0) - Lz))))
kERVN
Since Assumption implies Assumption 2, by the first statement of Lemma 3 with 1 have, with probability of at least 1 6, that
we
UH + K + log(118)
T2. T4 C.
K K'aizain
Applying the upper bounds of the six terms to (44) and a taking union bound, we have
Logueguat) Lu((") < 2C, VH + K log((()))
2 -
G
K
K
with probability of at least 1 36, which completes the proof.
Note that the bound in Proposition 2 is strictly worse than the one we showed in Corollary for any value of G. In fact, the former is (11/ /Terain + G) and the latter is 0 /Trran))))) o(G)
23

---

Under review as a conference paper at ICLR 2023
F COMMUNICATION COMPLEXITY OF ALGORITHM 2 AND EXTENSION TO NON-CONVE CASE
In this section, we present the communication complexity of Algorithm 2 for convex problems as well as the corresponding algorithm and complexity for non-convex problems. To do so, we first present the convergence property of Algorithm 1, which is originally established by Gorbunov et al. (2021). Then, we combine the analysis by Gorbunov ct al. (2021) 1) and Ghadimi & Wang (2018) with some minor but necessary modifications, for example, to allow for generic weight instead of the uniform weight in Gorbunov et al. (2021), and to handle the approximation error between V F((w and V FF(w), which is a little different from the one considered in Ghadimi & Wang (2018).
F.1 CONVERGENCE PROPERTY OF ALGORITHM 1
As mentioned in Section 4, we need to solve subproblems (1) and (15) in Algorithm 2, both of which are instances of (16). Because of Assumption I, problem (16) in these two cases satisfies the following assumption with & and μ exactly the same as the & and μ in Assumption 1. Assumption 5. [L,((T) is convex, V. (x) is & -ipishhhitzz continuous and J [1((2r is ju-strongly con- vex for 1,..., ng and k = ..2.....K K.
A unified analysis is provided in Gorbunov et al. (2021) for a large class of FL methods including Local-SVRG given in Algorithm 1. The following proposition is obtained by applying Theorem 2. in Gorbunov et al. (2021) Local-SVRG under our setting after minor modifications. It character- izes the convergence property of Algorithm 1. We omit its proof because it is the almost the same as the proof of Theorem G.7 in Gorbunov et al. (2021).
Proposition 3. Suppose Assumption holds for (16) and y S 7/ with yo defined in (17). Algorithm
guarantees
[[((T()) - f(x))] <-(11 (1-111)
T+1
22>26
+ 30e7 ( 1) 2 2+9
1| - x x=1
4+
34
K
45c
e1 2 1)²
Σ
wk [[x (1*)
(45)
2
k=1
where x" be the optimal solution of (16).
F.2 COMMUNICATION COMPLEXITY OF ALGORITHM?
To analyze the complexity of Algorithm 2, we needs to bound the error of the approximate gradient of F, namely, the quantity
( v (w ||
s= 0,
and then the convergence analysis in Ghadimi & Wang (2018) can be directly applied. This error depends the suboptimality of g(s) and h(() in iteration s of Algorithm which can be characterized using Proposition 3. To do so, we first bound || f (x²) || and [|a:(0) -x*1 appearing in Proposition for these two instances. For simplicity, we assume Local-SVRG is initialized at (0) 0 when applied to any instance of (16).
Suppose (0) = I(0: 2/ ), 1, 1.... n2. k 1...., K and x² is the optimal solution of (16), namely, x¹ = O(w). Because of Assumption 1, we have that [[+))( < Eo for any l in any iteration s of Algorithm and x= = (ww) is a continuous of w on Ag. which means ||r:(0) - x:
| < max & [1((w))) 2 in any iteration of Algorithm 2.
Suppose (h. = !n (1((()))
(
yh T (L)((())), I,..., nk. h = 1,... K. The optimal
2k
solution of (16) in this case
K
Σ
(5) (
(5)
((o())
x²
w
24

---

Under review as a conference paper at ICLR 2023
which means 1|=110)-=*11 = =1|x*1
because of Assumption 1. Moreover,
Vfu((")- ('Ix(((s)
Σ (e)
L (((l))
-
w
so V < b + to for any k and s by Assumption 1.
1
Since f is justtrongly convex, we have e ([|b(() - x=1 I f(x(T) - f(xx). With this inequality and the discussion observations, we can derive from (45) that
E ( x²
119 - 7p
(1- (1-
4+
22
+ 300y 2 11 2
-max R² B l
39
g
R2
45e + 117 - 1)²
l + 1)
(46)
1
/
with = max [0()]] when Local-SVRG is applied either (1) or (15) any iteration of Algorithm 2.
The following lemma bounds the error of the approximate gradient for F. Lemma 4. Suppose Assumption 5 holds and 7 S "/0 with "o defined (17). We have
E (w)) V F 1
Ci - (1- 7
To-1
C2 Ca+
CLT 1)2, (47)
where Or C2 and C3 are constants that depend on la eu lz μ. R. q and K but not t, T, and y.
Consequently,
when T = 1 == 7o and T, = 1 In (CCx(e+1)*) To1l
OR
70
when
y M.
and T. = 1 M, In (M?).
where
M. max
_ (s + 1)2 () Cat C,(T
1
%0
have B
A (( लमम.
Moreover,
when T = y and T, = 1 In CxC2(e+1)*)
OR
7011
70
when
> 1, -= My and T = - 1 M2 In (M?.),
where
M max {
70"
we have V v (w || s र.मा...
Proof.
Let (((w)))) F
)) ((nF(u(()))
where
vxF(w(()) - -
Σ w md
V2 veLn
Vio(o())).
(48)
Recall that
V ((o(()) (O(o))
25

---

Under review as a conference paper at ICLR 2023
We then obtained from (46) that
E
(w
(
VF
(w
(2)
11
K
-1
SKEEE
(+)
Σ
w
(s)
V (
k
A=1
2KL
T++1
4 32/069
+ +30e70 -1) 1
{ RR2
1 1-714
7/11
max
7/
34
ạ
112
K5cKly
l + 1)
( 1)²(
(49)
According to Lemma 2.2 in Ghadimi & Wang (2018) and (46), we have
E
w
(1)
Fw
F
11
26081
<K
B[11((e)
-(win))) [1=]
11
112
28081
E
2
2
(1 734)
Ti+1
3278
-1)2+0 22
E R2
<K
4+
max
11
112
7/4
39
9
n12
E26
2
45e
2 - -)8( f + 1)
+ K
+
(50)
1
1.2
Combining (49) and (50) by the triangle inequity leads to (47).
When 7 1, 7 to and T,
1 In (
(CICof+t!")
it is easy to show that B[] V F (w
70p4
701
(5) ||2 I 13+
1
Suppose T > 1, = M
1 and T' = p -M In (M²). We have
V -
- ||
FF
- Ci (1 (1- (1- To+1
(C)+ C4p()
S Sexp (- HiT.'
M, M,Ci(C2- +C2 - 1)) + C4(T- 1)2
M2
< exp (nI((M))) M.C, (C2 + C3(T - 1)) + C4(T 1)2
M3
Ci (C2 + Ca(T 1)) Ca(T - 1)²
M3
M2
(8 + 1)T
The conclusion with E. V (w)(c)
V Fz (5)
- can be proved in the same way except
that (s + 1)a must be changed to (s + 2)², and thus we omit the proof.
The complexity of Algorithm 2 when F(w) is convex can be showed using the proof in Ghadimi & Wang (2018) with their gradient approximation error replaced by the one in Lemma 4.
Proof of Theorem 3. According to Lemma 2.2 in Ghadimi & Wang (2018), F(w) is em-soooth with
er defined in (12). Let F, | (1) V F [((d))] According (2.51) in Ghadimi & Wang
26

---

Under review as a conference paper at ICLR 2023
(2018), have
((wlet)))
8
F
(
(8)
2
(
+
16
(l (l0- w00)11 11 w2(
+ 2
$ 2
n(s () + +2)
+
2
w
(++ 11
E2g
+
"
F
8 +
2
s
(w
(8)
16
- (10-w()) || 112
8 +
ag
8 2
7
() + 2)
4
E,
E
8
where the second inequality because | w S as both @ and w(++1) are on a simplex. Subtracting F(w) from both sides of the inequality above and dividing both sides by (++1)(+42)' we
have
(s + () + 2)
F(w((t1)) ug
- F(mi)
2
8(8 + 1)
(((u(())
- [(0) + 8
[10 - w()) 11 11)
mg
2
1) + 175s + 1) + +2
+ 2(s
Summing up this inequality for = ,.. - gives
S(S 1)
2 (F(w1g) F())
16
+ Σ
S-1
2(s + 1)
E E
7ss + 1) + 2)
E EEFE?
"
4
which, when E E[Eş] < (++2]T implies
E
(8)) [())
32 S) +1)
4log(S)
π n
S(S + +1
125(S
+1)
This means, as long as E E? < (s+2)4, Algorithm 2 finds an c-optimal solution of (P) in Ō 0.5) iterations.
Let Ai = CC =2 = C₁C3 and A3 = C₁C4 with C1, Cz. C3 and C4 defined in Lemma 4.
Suppose 7 1 "Yo and T, 1 In
(A((++))*) 70
By Lemma 4, we have E [[]]] I (++2)= In
7op
iteration 8 of Algorithm 2, the total number of rounds of communication needed in Local-SVRR is O(T.) = (In(s)) so that means the total number of rounds is Ō 0..5).
Suppose 7 1, 7 M, and T, μ MM In (M?). By Lemma 4, we have E E iteration 5 of Algorithm 2, the total number of rounds of communication needed in Local-SVRG is O(T./T) = ((²²) so that means the total number of rounds 0(651.)).
S [s+2)4 In
F.3
ALGORITHM AND COMMUNICATION COMPLEXITY FOR NON-CONVEX F
When F in (P) is non-convex, we no long expect any algorithm to find an e-optimal solution and change our goal to finding an c-stationary point of (P), which is defined as solution w E 4% satisfying
m- 1 Proja (w (nn-nVV(())l (VF(w)
for some > O. There exist multiple numerical techniques for finding an e-stationary, among which the proximal gradient method the simplest one. When the gradient can only be computed inexactly. there exist studies on the iteration complexity of the proximal gradient method for finding an e-stationary point, including Ghadimi & Wang (2018) for bilevel optimization and Gu et al. (2018) for a general problem. We will simply apply the proximal gradient method to (P) using the approximate gradient F in (14). We formally present this approach in Algorithm 3. Again, the center is node 0, i.e., the node where Daalid is stored.
27

---

Under review as a conference paper at ICLR 2023
Algorithm 3:
Federated Learning Method for Bilevel Optimization (P) (Non-Convex Case)
Input:
initial weight w()) learning rate training data ka for &o E K, validation data D the number of outer iterations S, parameters (7's T,9) for Loca SVRG, and the number of inner iterations T, for o,...,
for 8 = 0, ..................... do
Compute ()( as follows:
Set (0) = [0; 2 ) -,.,... The k ==l...,,,
Compute (( = Local SVRGG w(s), o(o-1), 7, T, Ts)) and send to each
node.
Compute (0(+)) at center and send it to each node.
Set fh, = 1/h ([((() (0) ( - (o(()))), i= i=
, K
Compute (+) Local--VVcee (ffR.s) w(s), (L)()))), 7, TT) and send it to each node.
Each node computes (f(e)) in parallel and send it to the center.
10
1 1,....K K (e+1)) = arrg mig (VF(w(()) w) + 21 1
Set (()()) = (0(s)) (((()) for k =
11
12 end
Return: (*) with ø sampled randomly from {0. 1, , S 1 1}.
13
The convergence result of Algorithm be proved in standard way (e.g., see Theorem 2.1 in Ghadimi & Wang (2018)). We present it below only for the sake of completeness.
Theorem 4. Suppose Assumption holds. Let in (12) and (17). Suppose 32p in Algorithm 3. There exist constants Ad, A2 and Ag that only depend on fo, l, 82, u. R, q and K but not such that the following statements hold.
wax 10(w)) and f and to defined as
Suppose = 7, "to and T,
1 In (Ar(st12)
Algorithm 3 finds an e-stationary solution
70k4
(P) with Ô (c-2) rounds of communication.
Suppose 1, 7 My
and =p" 1 In (MT), where
{
(s A2(T 1) + Az(T - A-[3-1)3]
M = max
00,00, 0,
(51)
7o
Algorithm 3 finds an e-statiioaayy solution of (P) with Ô (E-4) rounds of communication.
Proof. Let E, = | - [((w())] Since (++1) = -Projag (no(*) 1/ ((w(+))), by the
property of projection mapping, we have
(() -Proj (w(+) (vVl(wl))))
$ 2 (x) r0(+1111
+ PPoooooj (wl ( -Projag (10()) - (W()((())))
2 (+) w((+1)/
+ 2n 2
(52)
By the definition of (=(1)) and the -trong convexity function v (F(w(()) w ( we have, for any w E A
V ((w(t)), (((+1) - w(+)) ) + _-]l_l(we -
w)) + - w|w (
2n
2n
(VF(u(()), a- -
+ ||w 20()) 112
1
(53)
27
28

---

Under review as a conference paper at ICLR 2023
Taking w(() in (53) gives
(VF(w))), w(+l1) m0(1)) [1-1ll((tt)) 10(0
- S 0.
1
(54)
Since F' is Ep-Lipschite continuous and S
1 Fx we have
F(wwlot))- F(w!")) s (Vπ(w)l)), wl(tt) - mlll) + -
1
- (55)
2n
Adding (54) and(55) gives us
1( - (()( + 2n - w
x (F(()()) - < -/ (w(())), w - -w(())
s Felll((+11) - w|()|| s 2F.s,
which, together with (52), implies
(s) Projay (/) S ((w(t)) - F(w(st1)) + +F,, + nE
4n
Summing this inequality and taking expectation give
S-1
2 8-1
2
(0))) Projag (w [w(+))]]]+ s
4 ns
+
8
Σ
E F2g
Σ
F
R
ns
5 ==0
5=0
When E[E?] I (st1yz, the inequality above implies
E ((()) Projap (w( 12
4 S
(0)
F(())
8 (log(S) x²
+
S
38
This means, as long as E [E?] S [a+1)z. Algorithm 3 finds an e-stationary solution of (P) On iterations.
Note that Lemma 4 still holds with w replaced by w=()) in Algorithm 3. Let A C2 A2 CiC' and A3 = C₁C, with C1. C22, C3 and C₁ defined in Lemma 4.
By Lemma 4, we have E E[E²] < [s+2]z In iteration 8 of Algorithm 3, the total number of rounds of communication needed in Local-SVRR is
Suppose T = 1, Tr and T, = ---1- In (A+ Top
OTT.) = ((n(s)) (s) so that means the total number of rounds is Ō( -))
Suppose 7 > 1, 7 = My and T, = م - In (M3). By Lemma 4, we have E E iteration 8 of Algorithm's 3, the total number of rounds of communication needed in Local-SVRG is O(T./T) = Os)) so that means the total number of rounds is Ō(c=4).
S (s+2)4 In
The federated bilevel optimization methods by Li et al. (2022) and Tarzanagh et al. (2022) can find an e-stationary point within Ō(E-)) and Ō(E-A) rounds of communication, respec- tively. the first setting of Theorem 4 (T = 1), Algorithm has complexity of Ô(e-)), which is better than Li et al. (2022) and Tarzanagh et al. (2022). We want to point out that the lower complexity of Algorithum 3 is because it utilizes the finite-sum structure in (P), which allows comput- ing a deterministic gradient infrequently to accelerate the convergence. However, Li et al. (2022) and Tarzanagh et al. (2022) both consider objective functions given in expectation, which does not allow computing a deterministic gradient in general. One can check the following Table 2 for comparison.
Remark 1.
G ADDITIONAL MATERIALS FOR NUMERICAL EXPERIMENTS
In this section, present additional details and results of our numerical experiments in Section 5. The CNN we train in the experiments consists of two layers of 2D convolution, each equipped with 2D batch normalization and ReI.U activation, and followed by fully connected layer to generate
29

---

Under review as a conference paper at ICLR 2023
Table 2: Comparison in Remark 1.
Paper
Structure
Case
Number of Rounds
This work
Finite-sum
Convex
(
This work
Finite-sum
Non-convex
0(e
Chen et al. (2022)
Deterministic
Non-convex
2)
Li et al. (2022)
Expectation
Non-convex
Chen et al. (2022)
Expectation
Non-convex
Tarzanagh al. (2022)
Expectation
Non-convex
Ō
predictions. The first convolution layer is set output the same number of channels as the input, and uses kernels with size of 4, stride of 4 and one padding. The second convolution layer returns two output channels for Fashion-MNIST and MNIST and five for CIFAR- and ImageNet, and uses kernels with size of 2, stride of 2 and one padding. All experiments are conducted with PyTorch 1.9.0 and CUDA 1 11.1 computing platform on a computer with the CPU Intel Xeon Gold 6330@2.0GHz (Turbo up 3. 3.1) and the GPU NVIDIA GeForce RTX 2080 Ti.
G.1 DATA GENERATION WITH DIFFERENT CLASS DISTRIBUTIONS (SETTING
In this section, we describe in details how we generate D Durann and Diest from each original dataset for our experiments under Setting
G.1.1 FASHION-NNSTT
Fashion-MNIST (Xiao et al., 2017) contains a training set of 60,000 images and a testing set of 10,000 images. Each image is in grayscale, has size of 28 28, and is associated with label from ten classes: 0: T-shirt/top,, 1: Trouser, 2: Pullover, 3: Dress, 4: Coat, 5: Sandal, 6: Shirt, 7: Sneaker, 8: Bag and Ankle boot. We merge the classes into four classes as follows:
Cl: Classes 2, and 6 which include long-sleeve upper-body clothes;
C2: Classes 0 and 3 which include short-sleeve upper-body clothes;
C3: Classes 1 and 8 which include pants and bags;
C4: Classes 5, 7 and which include only shoes.
Note that these four merged classes are only used for generating data. In the classification task, we still have ten classes. This the same for the other three datasets. We set Al 4000, Alaiid 500 and neest 5000. Each image is sampled from one of the four merged classes with probability distribution (P1, P2, Pa, P4). Once a merged class chosen, each image in that merged class has an equal chance to be sampled. For Drain with h E J, we sample data from the training set with P. 0.42, Pg 0.08, P3 0.38 and P4 0.12. For Drain for k E JM, we sample data with Pt 0.12, P3 0.38, P3 0.08 and P4 = 0.42. Depending on Po is the distribution of Jm or JM. Dvalid and Diest are sampled from po the corresponding distribution. Note that D and Distt are sampled from the training set and testing set of the original data, respectively, although they have the same probability distribution over the four merged classes. Since Dvalid and Distt are generated in the similar way for the other three datasets, we will only discuss the generation of Dimin's in the subsequent sections.
G.1.2 MNIST
MNIST (Deng, 2012) contains a training set of 60,000 images and testing of 10,000 images. Each image is a handwritten digit in grayscale and has a size of 28 x 28. Since MNIST has the same number of classes, same class distribution, and same data size Fashion-MNIST, we directly apply the same procedure in Section G. 1 to sample data. In particular, we merge the ten digits into four classes follows:
C1: Digits 2, and 6;
C2: Digits and 3;
30

---

Under review as a conference paper at ICLR 2023
C3: Digits and 8;
C4: Digits 5, and 9.
We set Terain 4000, flaaid 500 and flst 5000. Following Section G.I.I. for Di with k E Jm. we sample data from the four merged classes with P1 = 0.42, P3 = 0.08. P3 = 0.38 and
P1 0.12. For Dirin with JM. we sample data with P1 0.12, P2 = 0.38, P3 0.08 and
P4 = 0.42.
G.1.3 CIFAR-10
CIFAR-10 10 (Krizhevsky et al., 2009) contains training set 50,000 images and testing set of 10,000 images. Each image is in color, has a size of 32 x 32, and is associated with a label from ten classes: airplane, automobile, 2: bird, 3: cat, 4: deer, dog, 6: frog, horse, 8: ship and 9: truck. We merge the ten classes into four classes as follows:
Cl: Classes and 9 which are related to ground transportation;
C2: Classes and 8 which related to non-ground transportation;
C3: Classes 2, and which form set of animals;
C4: Classes 5, and which form another set of animals.
We set Reain = 4000, 12valid = 500 and Reest = 5000. Similar to the procedure with Fashion- -MNIST, for D with Jm. we sample data from the four merged classes with Pi 0.36, P2 0.04, P3 0.54 and P1 0.06. For Diain with &t E JMa we sample data with 0.04, P2 0.36,
P3 = 0.06 and P1 = 0.54.
G.1.4 DOWNSAMPLED IMAGENET
Downsampled ImageNet (Chrabaszez al., 2017) is created by downsampling each image Im- ageNet (Deng et al., 2009) to 32 x 32 pixels without changing the class labels. Just as ImageNet, downsampled ImageNet has 1000 classes and we choose ten classes and merge them into four classes as follows. (The class labels listed below are consistent with ImageNet.)
C1: Classes 7,9, 10, 29, 54, 75, 84 and 189, which are cats or animals similar to cat; C2: Classes 61, 66, 68, 101, 114, 124, 131 and 148, which dogs animals similar cat;
C2: Classes 383, 397, 403, 404, 405, 406, 412, 414, 420, 426, 433 and 434, which are all birds;
C3: Classes 224, 441, 442, 443, 444, 445, 449, 453, 454, 498, 499 and 500, which are either fishes frogs.
We Plrnin 4000, Thaaid 1500, The 1000. For D for E Jm. we sample data from the four merged classes with P 0.36, P2 0.04, P3 0.54 and P4 0.06. For Drain with k E JM. we sample data with Pi = 0.04, P2 = 0.36, P3 = 0.06 and Pa = 0.54.
G.1.5 COVTYPE
Covtype (Blackard & Dean, 1999) is imbalanced dataset of 581,012 instances. Each instance records ten features in integer value and two categorical features one-hot encoded into 44 binary values, and associated with a label from seven classes: 1: Spruce/Fir, 2: Lodgepole Pine, 3: Ponderosa Pine, 4: Cottonwood/Willlww 5: Aspen, 6: Douglas-fin fir, 7: Krummholz. According to the imbalance on class labels, we merge the seven classes into four classes follows:
C1: Classes which consists of approximately 36.5% of the raw data;
C2: Classes which consists of approximately 48.8% of the raw data;
C3: Classes 3 which consists of approximately 6.2% of the raw data;
C4: Classes 4, 5, 6 and 7 which consist of the rest.
31

---

Under review as a conference paper at ICLR 2023
We set Parain 40000, nlalid 5000 and Rieat 50000. Similar to the procedure with Fashion- MNIST. for D with & E Jm. we sample data from the four merged classes with P1 = 0.72, P2 = 0.14, P3 = 0.12 and P1 = 0.02. For D with & E JM, we sample data with P1 = 0.10,
P2 = 0.82, P3 0.06 and Pa = 0.02.
We train a liner multi-class logistic regression model using the same computing platform in this experiment as before. We use mini batch of size 400 to construct the stochastic gradients in all methods. In the Bi-level method, Algorithm 3 is applied to (P) with b = 1/3 and five epochs performed within each call of Local-SVRG (i.e., T. = / 400).. We set q = 1/100. Other parameters are the same as our choice in Section 5. We only run Setting with one random seed on this dataset. The results are shown in Figure 3.
G.2 DATA GENERATION WITH DIFFERENT CLASS DISTRIBUTIONS AND LABEL PERMUTATION (SETTING 2)
In this section, we discuss in details how Darin D and Diest are generated from each original dataset for our experiments under Setting 2. For each dataset, we first sample data Dtrain D and Dist in the same way Setting 1 described in Section G.I. Then we permute the class labels in Di with & E JM. For each dataset, the class labels in Disin with E Jm are unchanged. If po the distribution of JAr, the labels of Dvalid and Diest are permuted the same way as Di with k E JM- If Po is the distribution of Jm. the labels of Dyalid and Drest are unchanged.
We then describe how the class labels in Dirin for lo E JM are permuted for each dataset. For FaShion-MNIST and MNIST, we permute the class labels in Drain for k E JM by changing label 2 to O, 0 to 1, 1 to 5, and 5 to 2. For CIFAR-10, 10, we permute the class labels in Digain for k E JM by changing label 1 to 0, 0 to 2, to 5, and 5 to For downsampled ImageNet, we permute the class labels in Disin for lo E JM by changing label 7 to 61, 61 to 383, 383 to 224, 224 to 9, 9 to 66, 66 to 397, 397 to 441, 441 to 10, 10 to 68, 68 to 403, 403 to 442, and 442 to 7.
G.3 DATA GENERATION WITH DIFFERENT CLASS DISTRIBUTIONS, LABEL PERMUTATION AND/OR RANDOM ROTATION (SETTINGS 3 AND 4)
In this section, we discuss in details how we generate D Dimin and Diest from each original dataset for our experiments under Settings and 4.
Under Setting 3, we first generate data in the same way as in Setting described in Section G. Then, randomly choose a rotation direction, clockwise anti-clockwise, and rotate each image in Diain with & E JM toward that direction for 90 degrees. Under Setting 4, we first generate data in the same way as in Setting described in Section G.2. Then, we apply the same rotation procedure as we do in Setting 3.
G.4 ADDITIONAL NUMERICAL RESULTS
In this section, we first plot how the weight w% for each node evolves during the Bi-level method under Setting 2, 3 and 4 respectively in Figure 4, Figure 5 and Figure 6. We show the results when Po the distribution of the majority and the minority groups separately.
Since the performance of an algorithm may fluctuate during training, we are interested in comparing the methods in the best performance they achieved during training. To do so, we save the model generated by each method at the iteration where the highest accuracy is achieved on the validation data. Then, we report the performance of the saved model's 's by each method on the testing set in Table 3. Again, we show the results when po is the distribution of the majority and the minority groups separately. Our method outperforms the basclines in most of the cases.
Next, we plot the test (top-1) accuracy each method obtains during iterations for the minority group and the majority group in Figure 8 and Figure 9, respectively, where the horizontal axis represents the cumulative number of data points each method processes in parallel.
At last, we give the results of the ablation study. We choose the case of Setting Seed 1, and consider four choices the size of the validation dataset Dvalid, i.e. ngg The choices are 100, 200,
32

---

Under review as a conference paper at ICLR 2023
500 and 1000 for Fashion- MNIST and CIFAR- 10, and 1000, 1200, 1500 and 2000 for the downsampled 32 x 32 ImageNet. Similarly, we save the model generated by our Bi-level method at the iteration where the highest accuracy is achieved on the respective validation data. Then, we report the test (top-1) accuracy each method obtains during iterations for the minority group in Table 4 and the majority group in Table 5.
How w evolves
Test Accuracy
0.20
0.8
0.8
Pu is Minority
0.15
Far Nodes
0.6
0.6
Near Nodes
Bidevel
Bi-eeel
weight
0.4
Locaitrrin
0.4
Local train
FedAvg
Dilto
Ditto
0.2
PFedme
0.2
200 400 600 1000
200
600
800
1000
Number of Synchronizztions
Number of Synchrenizziions
Number of Paints Procesced
0.8
0.8
Pn is Majority
Near Nodes
0.6
Nodes
Bi-leell
Bi-ievel
0.04
Equal weight
0.1
Locai-train
0.4
Local train
FodAug
FecAvy
0.02
0.2
Ditto
0.2
Ditto
PFddme
FFedma
0.00
200
400
600
1000
0
Synchronizations
Number Synchroniastins
Number of Points Processed
Figure 3: Results for Covtype.
F-MNIST
MNIST
CIFAR- 10
DS- DS--mageNeet
pn is Minority
130
120
0.20
0:27
Sisilar Modes
Sincker Modes
Simcier Modes
Shniler Noder D D Modee Eoust weight
1.3
me Noose
bir far Necee
8:30
D ettrr licce Ezcal weiget
6.10
Exas weigh
velge
5.00
6:0G
6:35
255 500
Syndeenicatioo
1250
255 500 750 1000 1250 Syndeenization
350 500 750 1000 1250 Syeovenication
250 500
750 1000 1250 Syrcventietenn
Pn is Majority
5.10
0.10
0.10
Similr Nocia waiit
Simdlrr Nocies
Sinilrr Modes
Sinilar Hodes
1.04
5:00
Eccal weight
0:34
Equal weight
1.00
2.00
0.02
6:22
1.00
6.00
6:00
U20
Sumeer Syndeerictiion
Morbbrr of Iyeoronncatioo
Number Syrceontattory
Figure 4: How w evolves during the Bi-level method under Setting 2.
F-MNIST
MNIST
CIFAR-10
DS- DS-ImaeeNet
Aa is Minority
8.20
6:20
6.35
0.15
Sincke Modes
Sinday Novies
Sinilor Nodes
Boccibrreie heses
Diriniar bor Necee
eravib Neciee
6.10
Dietii Medie
Equn weigt
Ezanl velggn
Ezsal leiign
Exuat weight
5.0
6:G
6:09
8.0
0:00
155
206
150 1006 1250 Syndrrroeess
352 200
750
1000 1250
250
300
750 1000 1250
250
500
753 1000 1253 Concvenbeetine
Po is Majority
8.100
0.19
Sindar Modes
Sinckr Nocis
Saniker Modes Eccal
Sinilar Nodes
3.000
weigtt
2,00
0.04
0:44
Coual weight
E.00
5/02
0:22
0.00
6:00
1000 1250
1000
Number Syndeerrasaaa
Momrer Syndeernaataa
Murzer of d'S0noooeaatsss
Number Synccooeetttt
Figure 5: How evolves during the Bi-level method under Setting 3.
33

---

Under review as a conference paper at ICLR 2023
F-MNIST
MNIST
CIFAR- 10
DS- ImageNet
Po is Minority
8200
Simiarr Nocke waget
815
Sin Noces
6:35
Siniarr Modes
6.15
Similar Hodea Eool woghh
E10
0:30
0.10
Excal legght
E.0
8:95
0.00
1.00
2.00
0.00
6:00
Suatzo Syrdecsiciion
Murss Syndecnicaiinr
Murbier el Syecreeicatioss
Narber Syrceontaaiory
Pu is Majority
0:30
6:10
6.00
6.34
5AM
mir Necee
Siiler Vodes
5.00
Similrr Modes
to for Necee
5:00
Stmieer Modes
suirr for locks
0:30
Striler Hodes
Dasire Medes
Exsd wagst
2.0
Exsal ledgy
Excal leiget
Eoual waigh
5.09
0.00
255 100
Sysdecricsoor
1866 1750
Mumber Spsdecrionnns
500
1000 1750
5en 750 1000 1290 Murser Ipnovennations
300 Marter
750 1000
Figure 6: How w evolves during the Bi-level method under Setting 4.
Table 3: Test accuracy when reaching the highest validation accuracy.
Setting
Minccity Madel
Majority Model
Methodi, Duta
F-MNIST
MNIST
CIFAR
DS ImageNet
F-NNIST
MNIST
CIFAR 10
DS ImageNer
level
0.775811.00599
0,8924
0.5175100.065
0.2669
0.834410.0121
0.844320.0000
0.5928-0.006
0.2630 00901
Local-tmin
0.6026+000175
0.7850=00000
0.3036+0.0102
0.1102+003122
0.7427-00110
0,7550=6.00P
0.356--0.0144
0.150000.007
0.750710.007
0.2965 0.809710.0177
0.200110.00117
0.832710.0119
0.8484.0.0125
0.705L0.0052
0.2612.00001
07299360.016
0.22580000001
0.15
0.80666001111
05021
0.1844=0.0122
PFodMe
0.741840.0255
0.85880000004
0.450000.066
0.2064-0.0088
0.827700:0700
08330-0.0162
0.5888000110
0.224-0.0087
Sening
Minerity Model
Majority Model
Datt
F-NNIST
MNIST
CIFAR-10
DS-Imaga/Na
F-MNIST
MNIST
CIFAR-10
DS-ImogoNet
Bi-level
0.7754+0.0022
0,5500-
0.5148-000051
0.2734-0.005
0.8332-0.063
0.8344-0.0196
0.5979-0.0044
0.2694 0.0104
train
0677331000016
0.757410.0129
0.315910.0110
0.126010.0003
0.7343L000004
0.765010.0146
0.1276_0.011
FalAvg
0.5686+000021
0.5009000440
012670=00006
2.1666-0.0044
B:7N3440:0003
0.776600.012
0545)=008857
0.2522-0.008 0089
Disso
0.224400.009
100041
10.0111
0.156600.0178
0,788910.000
0.784120,0899
0.9166:000131
0.1724 0068
pPodide
100071000130
0.7006200024
0.4022000111
0.1930110:113
0.80911000044
0.79122002233
0.557420.0104
02106:00.0081
Setting
Minccity Model
Majonity Model
Methodi
F.NNITT
MNIST
CHFAR-UU
ImageNNet
F-MNIST
MNIST
CIEAR-10 10
ImageNer
Bi-level
0,7766200170
0.0036
0.019
0.5661000064
0.018
Local train
069621000126
0.70051000004
0.305111.0107
0.116210.0085
0.7262L0.00P4
0.769500.0100
0.3632-0.0081
0.0083
0.0231
FolAng
0.994044-02211
1.62550000195
0.3064+11.009
0.1756+00.008
0.770--00113
0.763-00.0711
05225-0.0123
0.267-00.017 0074
Disto
0.745210.0160
0.415410.0149
0.16261000009
0,762810.011
0.77421000167
0.096
0.0922000133
PFedMe
031228600239
0.7203000200
0.195820031144
0.7002000544
0.50030000188
0.2188:001122
Setting 4
Mincrity Model
Majority Model
Methodi Data
F-NNIST
MNIST
CIFAR-I0
DS-InugeNNe
F-MNIST
MNIIST
CIFAR-10
DS DS-ImggeNet
Bidevel
0.765N:100117
0.5172:00.0107
0.2699:000115
0.816000.0011
0.8455-0.006
0.5935-000654
0.2678-0.0062
Local-tmin
0.8099000009
0.7645--00270
0. 0.5086+0000022
0.1148-00.005
0.099
0:2012-0.0066
0.7476+0.023
0 0.3709-0.0079
0 0087
FedAvg
0.561811004881
0.547510:0205
0.3612100.181
0.172210.0000
0.761410:0288
0.757710.0129
0.852910.0077
0.000
Dima
02074400010
0.7176=00.0885
0.3970+HL.000
0.1538=0:007
0. 0.76085-0.093 0.7646--0:005
0.98K=0.0002
01744=0.0199
PFedMe
0.0051000187
0.6012.0.0140
0,054800.0099
0.179410.0114
6.71000000100
0.0687
1.089000.0000
0.2232-00.006
Table 4: Test accuracy's of the minority model by the Bi-level method using validation sets of different sizes.
Alaaid
F-MNIST
MNIST
CIFAR-10
Aiaaldd
DS-ImageNet
100
0.7782
0.8444
0.5226
1000
0.2850
200
0.7830
0.8778
0,5170
1200
0.2700
Test Accuracy
500
0.7756
0.8108
0.5100
1500
0.2740
1000
0.7842
0.8852
0.5292
2000
0.2930
Table 5: Test accuracy's of the majority model by the Bi-level method using validation sets of different sizes.
Phalid
F-MNIST
MNIST
CIFAR-10 10
Aivalid
DS- DS-ImageNet
100
0.8286
0.7946
0,5664
1000
0.2600
200
0.8362
0.8480
0.5620
1200
0.2710
Test Accuracy
500
0.8216
0.8044
0.5920
1500
0.2920
1000
0.8394
0.8514
0.5890
2000
0.2640
34

---

Under review as a conference paper at ICLR 2023
F-MNIST
MNIST
CIFAR-10
Dmeleneeeet
0:25
Setting
044
0.2
0.27
Disse
Slave
0.15
04-
Lockktreh
0.-
Loca-tren
Leca-triit
loce drah
6.2
(Peane
preaine
0.85
precrs
355
500
126
ounoer Syndestoution
Murtzar of Sgronsstuiiae
Murber of Sprcronsaions
0.0
0.5
0.5
0.23
Setting
0.4
Feshig
Tedtig
5.3
044
Slace Tectag
0.15
6.10
Feetlgg
02
preame
Ctts
preame
6:35
Dito
353
540 263
1885
255
500
355
1865
355
500
355
1666
355
533
156 1666
0.0
Setting 3
1.
Bileee lock minn
Look- inin
Look mi
lecs onih
Festvp
Fadtig
Teetlog
6.2
predte
6:1
Murser Sendroricyiio
Murbee of bynooeniiaiisss
Sumber of Sprcvonuaties
Setting 4
0.0
0.25
3.0
6:20
1.4
lied
Fid
62
Demo
pfadme
p'adee
s'scme
0.0
255
500
752
2382
253 500
750
1000
355 500
750
2000
250 530
110
1000
Figure 7: Comparison in test accuracy for the majority group vs number of synchronizations.
F-MNIST
MNIST
CIFAR-10
DS- DSs-engeNeet
0.25
Setting
6.00
6.3
0.19
0.4
Feata)
0.10
feello
12
0.2
of Focessed
Number Portss Fockued
Numberol Ponts frocuued
Number Potto Propassed
0.25
Setting
26
5.0
0:30
44
gllced
Local
Bilve
Bileve
teto
prediw
piecess
Murberor Froceesed
Nu
Setting 3
0.2
Bileve Locs irsin
Local triin
LA
Local trin
Locs lrsin
Paskig
tecley
protine
presine
p"erme
of Foraosed
Rumbor of Peline
1.0
0.25
Setting
16
5.5
6.6
6:20
6:5
Local
Fadtug
Fedkig
Tedtug
0.10
Teclog
02
Clts
02
6.0
5.2
of Focessdd
of Precsses
Numberio Points Pricoset
Number of Paints Pricesse
Figure 8: Comparison in test accuracy for the minority group vs number of points processed.
35

---

Under review as a conference paper at ICLR 2023
F-MNIST
MNIST
CIFAR-10
DS-ImageNet
Setting 1
04
0.20
6:15
0.
0.4
Lncal
Pelkyy
92
02
Pf Foceseed
of Foceuse
Number of Poiie Proceseed
Number of Points Processed
6.0
0:
Setting 2
0:5
54
0.15
Poskig
6.10
Pooley
42
Diix
12
6:33
Delo
of Foceseed
Marber Poines
535 -2
23
55
05.
12
23
1.
25
20
0.3
Setting 3
60
54
Blowe
Loca-ina
Loca iman
Clts
Cito
protie
pretee
p'csm
plamms
Setting 4
Looktnn
Locil tpnn
Lock mpi
0.15
can
redkvg
0.20
piodme
6:33
of Foccaod
Na Phnt Focksee
of Frocused
Number of NNR Pricossss
25
Figure 9: Comparison in test accuracy for the majority group number of points processed.
36


Reviews:
[{"review_id": "xQoZ3Vibbd", "reviewer": "Reviewer_Caqk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper focuses on Federated learning (FL) with heterogeneous data distributions. In this case, a globally shared model may not achieve a good local generalization performance. So, the author put forward a method that each node can still exploit global data through FL but, at the same time identify and collaborate only with the nodes whose data distributions are similar or identical to its local distribution. Furthermore, the author mentioned, it is also a bilevel optimization (BO) problem where the inner problem is federated learning with weighted nodes, and the outer problem optimizes the weights. In addition, the theorem also shows the bound on the statistical distance, dominated by the $O(1/\\sqrt{N_{valid}})$, which is the same as the generalization bound achieved by leaning locally. Finally, the algorithm in this article is well-consistent with the analysis of BO since it solves the inner problem before the outer problem. As a result, the algorithm performs better than the baseline when the data is heterogeneously distributed where higher test accuracy can be reached. ", "summary_of_the_review": "Overall, this paper provides an interesting bilevel formulation, which is shown to improve the local generalization performance. The analysis involves several new treatments. However, I have some concerns regarding analysis, related work and writing. I think this is a borderline work, and my evaluation will be adjusted based on the other reviewers’ comments and the authors’ response. ", "strength_and_weaknesses": "Pros:\n\n1. Motivation of this paper is reasonable to me and the weighted node formulation seems new in the literature of federated learning although it is not new in other multi-task or device applications such as meta-learning or life-long learning (Chen et al., 2021). In addition, the bilevel optimization based formulation provides a principled way to improve the generalization. \n\n2. Generalization performance of the proposed weighted node is provided, with several modifications of the analysis in Chen et al., 2021. Some new characterizations such as identical neighbors and error bound conditions are also included. \n\n3. Convergence analysis is also provided under local-svrg and some accelerated bilevel methods as in Ghadimi & Wang, 2018. \n\nCons:\n\n1. There are too many notations and it is a little hard to find the definition among words. I recommend having a brief summary of all notations, which is helpful for reading both the article and the proof. \n\n2. The discussion of communication rounds is not conspicuous although the author strengthened the algorithm is communication-efficient as this is important in FL. I recommend having a table or a figure to show the communication rounds of different algorithms so that readers can intuitively get this. \n\n3. For the generalization analysis, Assumption 2 is strong although some simple examples and Assumption 2’ are provided. This assumption requires $p_0$ is identical to at least one distribution in $p_1,…,p_K$. First, for the practical consideration,  the training-validation separation trick does not hold here, and the generalization may be affected as well. In addition, in terms of the technical novelties, the improved analysis by the error bound condition and the  identical neighbors (Assumption 2’) seems to be not that significant given the framework in Chen et al., 2021, and no tightness results are provided. \n\n4. The algorithm seems not to be new enough. For example, it seems to be a combination of local-SVRG, accelerated bilevel update in  Ghadimi & Wang 2018, and FedAvg types of aggregations. The algorithm also looks complicated with many hyperparameters, and its application may have some difficulty in more complex ML applications. I wonder if the acceleration step truly provides practical acceleration? Could you please include such an illustration in the experiments? \n\n5. Some important related works are missing:\n\nDistributed bilevel optimization: \n\n1. Ataee Tarzanagh, Davoud, et al. \"FEDNEST: Federated Bilevel, Minimax, and Compositional Optimization.\" arXiv e-prints (2022): arXiv-2205.\n2. Chen, Xuxing, Minhui Huang, and Shiqian Ma. \"Decentralized bilevel optimization.\" arXiv preprint arXiv:2206.05670 (2022).\n\n3. Li, Junyi, Feihu Huang, and Heng Huang. \"Local Stochastic Bilevel Optimization with Momentum-Based Variance Reduction.\" arXiv preprint arXiv:2205.01608 (2022).\n\nBilevel optimization and analysis:\n\n4. Ji, Kaiyi, Junjie Yang, and Yingbin Liang. \"Bilevel optimization: Convergence analysis and enhanced design.\" International Conference on Machine Learning. PMLR, 2021.\n\n5. Grazzi, Riccardo, et al. \"On the iteration complexity of hypergradient computation.\" International Conference on Machine Learning. PMLR, 2020.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Nt02eofxYG", "reviewer": "Reviewer_gCZG", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The authors have considered the problem of designing weights for federated learning problem via bilevel optimization. The problem is interesting and analyzed theoretically with extensive experiments. But there are certain limitations as provided next. ", "summary_of_the_review": "The problem is interesting, but the contribution is incremental. ", "strength_and_weaknesses": "*Strength*\nThe problem is interesting, paper is well written withe extensive experiments. \n\n*Weakness*\n\n- The contribution is limited and incremental. \n- Once the problem is formulated in the form of P*, I cannot see any additional challenge to solve it. There are multiple algorithms already existing in the literature which can directly solve this problem. \n- It is limited to consider the lower level problem as strongly convex, because even the simplest FL problem where we train NN would be non-convex. For instance, all the experiments are definitely considering non-convex lower level, therefore theoretical results are not consistent with the experiments. \n- Assuming the lower level to be strongly convex makes the setting quite straightforward to analyze and provide guarantees. It would be nice to specifically discuss the additional challenges, theoretically, authors had to address to do the analysis.\n-  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "K_fRyBMVPu2", "reviewer": "Reviewer_9pHr", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper presents a bilevel optimization-based federated learning method that can assign different nodes different weights to optimize the performance on a validation dataset. The authors present thorough theoretical analysis of the problem and verify that learning dynamic weights is better than using evenly distributed weights. Experimental analysis also shows the superiority of the proposed method over several baseline methods.", "summary_of_the_review": "This paper has good contributions and the paper is clearly written, but the experiments are not very solid and certain claims are not fully verified. Thus, my recommendation is a weak accept.", "strength_and_weaknesses": "Strengths:\n- The proposed method is interesting.\n- The theoretical analysis provides additional guarantees.\n- The results show the effectiveness of the proposed method.\n\nWeaknesses:\n- The bilevel optimization highly depends on the size, quality, and distribution of the validation dataset. In many real-world scenarios, high-quality validation data is not available on local devices (e.g., personal computers or smartphones).\n- Since this paper aims to bolster local model performance, it is required to compare several more baseline methods for personalized federated learning. \n- The experiments are conducted only on image classification datasets. I suggest the authors consider using some recommendation datasets (e.g., Movielens) since the user data in these datasets are naturally heterogeneous (and more realistic than simulated data).\n- The real communication costs of the proposed method and existing methods are not reported. It is suggested to include the results to confirm that the proposed method is \"communication-efficient\".", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IEt8gEJzK02", "reviewer": "Reviewer_F6ZM", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper introduces a node reweighting strategy for federated learning based on bilevel optimization. Specifically, this the proposed adaptive reweight method learns the weight assigned to each node by considering the “weighted aggregation” on the server as the inner problem, and minimizes the empirical risk on an in-distribution validation dataset. Theoretical results are given to verify the effectiveness of the bilevel method.", "summary_of_the_review": "This paper has certain contribution, but I do not think it is enough for getting accepted by ICLR. Some major limitations need to be addressed for the applicability of the proposed method.", "strength_and_weaknesses": "Strength:\n\nThe paper seems to be the first one to formulate node reweighting for FL into a bi-level optimization problem, and theoretical results are given to support the superiority of training a model locally and to federated learning with static and evenly distributed weights.\n\nWeaknesses:\n\n1. It is not surprising that FL with properly learnt reweighting performs better than local training and evenly distributed weights, which is the main theoretical contribution of this paper.\n2. The proposed bi-level reweighting method does not seem to be applicable in practice. The algorithm needs S X T global communication rounds, just to acquire the properly learnt node reweighting. This is obviously not acceptable, since global communication is often the main bottleneck in the application of FL. In addition, in the inner loop of Local-SVRG, the model seems to be re-initialized every time, this does not seem to match the real scenario, since we cannot ask the clients to re-initialize their models now and then.\n3. It seems that the weights are assigned to each specific client node, will it be problematic when the participation ratio is not 1 when running FL? This is often the case in practice, and this paper does not discuss about it.\n4. The bilevel method needs an in-distribution validation set,  and the size of such a dataset will affect the performance. An ablation study is required to clarify this.\n5. The algorithm is built based on Local-SVRG, which should serve as a baseline method in the experiment, so that we can see how much performance gain the reweighting actually brings.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject