Local Coefficient Optimization in Federated Learning
Authors: Congliang Chen
Chi Zhang
Bingzhe Wu
Yatao Bian
Zhi-Quan Luo
Peilin Zhao
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated Learning
Bilevel optimization

Abstract: Federated learning emerges as a promising approach to build a large-scale cooperative learning system among multiple clients without sharing their raw data. However, given a specific global objective, finding the optimal sampling weights for each client remains largely unexplored. This is particularly challenging when clients' data distributions are non-i.i.d. and clients partially participate.

In this paper, we model the above task as a bi-level optimization problem which takes the correlations among different clients into account. We present a double-loop primal-dual-based algorithm to solve the bi-level optimization problem. We further provide rigorous convergence analysis for our algorithm under mild assumptions. Finally, we perform extensive empirical studies under both toy examples and learning models from real datasets to verify the effectiveness of the proposed method. 

Under review as a conference paper at ICLR 2023
LOCAL COEFFICIENT OPTIMIZATION IN FEDERATED LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Federated learning emerges as promising approach to build a large-scale co- operative learning system among multiple clients without sharing their raw data. However, given a specific global objective, finding the optimal sampling weights for each client remains largely unexplored. This is particularly challenging when clients' data distributions are non-i.i.d. and clients partially participant.
In this paper, we model the above task bi-level optimization problem which takes correlations among different clients into account. We present a double- loop primal-dual-baase
algorithm to solve the bi-level optimization problem. We further provide rigorous convergence analysis for our algorithm under mild assump- tions. Finally, perform extensive empirical studies under both toy examples and learning models from real datasets to verify the effectiveness of the proposed method.
INTRODUCTION
Federated learning has achieved high success in the large-scale cooperative learning system without sharing raw data. However, due the large number of devices involved in the learning system, is hard to check data quality (e.g., noise level) for individual devices. Further, it will degrade the model's ability when it is trained with bad-quality data. To eliminate the influence of the 'bad" devices, is natural to reduce the weight of those devices. In most popular federated training algorithms (e.g., FedAvg (Li al. 2019)), devices are weighted the same or with respect to the number of data points it holds. Borrowing the formulation of federated algorithms, we introduce to control the weight of each device which is the coefficient of each local objective. We introduce validation set in the server to validate whether coefficients improve the model. We formulate the whole problem as a bi-level optimization state in the following:
variable
min fo(w"(a (x))
s.t. w" (x) E arg min
(0) f(w
(1)
w
X (
0,
|-|||| 1},
To solve problem a directly, i.e.,
① Kolstad & Lasdon (1990) propose an algorithm that calculates the gradient of
OSo(w" Ox(()
- vo (x))
Σ Vil((("
V (w
But, due to the large parameter dimension of w, is impossible to take the inverse of the Hessian or solve the linear system related the Hessian. Meanwhile, due to a large amount of data in the local device, it is hard to directly estimate the gradient or the Hessian of the local function fa
Only stochastic gradient and stochastic hessian can be accessed. Thus, Ghadimi & Wang (2018) propose the BSA algorithm where the inverse of Hessian is approximated by series of the power
of Hessian (using Eke n/ to approximate H with certain 7)). Khanduri et al. 2021
propose SUSTAIN algorithm for solving stochastic bi-level optimization problems with smaller

---

Under review as a conference paper at ICLR 2023
sample complexity. Similar to Ghadimi & Wang 2018), they need an extra loop of the Hessian- -vector product to approximate the product of the Hessian inverse with some vector.
However, it is known that for constraint optimization, with the descent direction, the algorithm will not converge to the optimal point or even to the first-order stationary point, where the inner product between the descent direction and gradient is larger than 0 (Bertsekas 2009). Therefore, getting an accurate approximation of the hessian inverse is essential. With the series of the power, it has to start with k and apply several iterations to get an accurate approximation, increasing the computation and communication in federated learning. Fortunately, by noticing the KKT condition, information of the hessian inverse can be embedded into dual variables. Based on the smoothness of the objective, we can give good initialization of dual variables rather than start with the same initialization in each iteration (like 7 in the series approximation). Thus, we propose a primal-dual caama--dull-baseee -baed algorithm to solve problem
Further, to solve constrained optimization with non-linear equality constraints, adding the norm square of the equality constraint Lagrange function. As a result, it is hard for the min-max optimization algorithm to find the stationary point. Instead, with the assumption in Ghadimi & Wang (2018) 18, the function Si 's are assumed to be strongly convex, adding function f. 's as the augmented term can help introduce convexity and it will not change the stationary point of the min-max problem. Based this new augmented Lagrange function, we prove that with stochastic gradient descent and ascent, to and À can converge to the KKT point. Meanwhile, by the implicit function theorem, when and À are closed to the stationary point of min-max, the bias of estimating the gradient of x can be reduced to O. Thus, with the primal-dual algorithm on w and À and stochastic projected gradient descent on I, show the convergence of our algorithm.
augmented term may not give the convexity to the augmented
Finally, we compare our algorithm with other algorithms on a toy example and real datasets (MNIST and F-MNIST with Network LeNet-5). The experimental results show that the proposed algorithm can perform well in strongly convex cases and even in some non-convex cases (Neural Networks).
We summarize our contributions as follows:
In Federated Learning, we formulate the local coefficient learning problem as a bi-level optimization problem, which gives way to identify the dataset quality in each local client for some specific task (where a small validation set is given).
In bi-level optimization, we introduce primal-dual framework and show the convergence of the whole algorithm in the constrained and stochastic setting.
For some specific optimization problems with non-linear constraints, we give a new aug- mented term. With the new augmented term, the primal variable and dual variable can converge to the KKT point of the original problems.
2 RELATED WORK
2.1
PERSONALIZED FEDERATED LEARNING
The most related work in federated learning tasks will be personalized federated learning. A well- trained local personalized personalized model is needed for each local device in personalized federated learning. Jiang et al. (2019); : Deng et al. (202)) propose a method that they train a global model and then fine-tune the trained global model to get the local model. T Dinh et al. (2020); Fallah et al. (2020) change the local objective function to make each local has the ability to be different and handle individual local tasks. [i et al. (202T) introduces two-level optimization problem for seeking the best local model from great global models. All of these works do not involve a validation set as a reference, but they use few gradient steps or simple modifications and hope the local model can both fit the local training data and use information from the global model (other local devices). Different from these works, we explicitly formulate a bi-level optimization problem. By adding a validation set, it can be more clearly identified the correlation of information from the other devices and from its own.
2.2 STOCHASTIC BI-LEVEL OPTIMIZATION
Bi-level optimization problem has been studied for a long time. One of the simplest cases in bi-level optimization is the singleton case, where the lower-level optimization has unique global optimal
2

---

Under review as a conference paper at ICLR 2023
point. Without calculating the inversion of the Hessian matrix of the lower level optimization problem,
there are two major algorithms. Franceschi et (0177) approximates Ow- (w)
8z by OWT where wr Bar
the iterate after T steps gradient descent for the lower optimization problem. Using this method, in each iteration, we need communicate N (number of local devices) vectors among the server and local devices which is not communication efficient. The other method Ghadimi & Wang (2018) is to by Σ - gg where g is the objective function of lower- level optimization problem. Although Khanduri et al. (2021) point out that to approximate gradient for upper optimization function, can get rid of taking the optimal point for lower optimization in each upper-level update optimization, which seems to get rid of double-loop approximation, it still needs loop for approximating Hessian inverse with series. Guo & Yang 2021 uses SVRG to reduce the noise level of estimating stochastic gradient and Hessian to get better performance. Besides, all of the above works assume smoothness of the local Hessian, but none of them will apply the property directly into the algorithm. Different from the above works, we introduce a primal-dual framework into bi-level optimization, where the dual variable can record the information of Hessian. Also, (Shi al. (2005); Hansen et al. (1992) introduce the primal-dual framework, but they stay in quadratic regime or mix integer programming, which non-trivial to extend the results to federated learning settings.
approximate
ALGORITHM DESIGN
Assume that each function of Si a strongly convex function. Then, the optimal solution to the lower optimization problem becomes only single point. Thus, with the implicit function theorem, we can calculate the gradient of fo(w" (z)) with respect to x as follows.
Proposition 1. Suppose Je's s are strongly convex functions. Then for each a E X, it holds that Vo
(fo(we Bat = - voff(w
vwff(w"(x))
With the proposition 1 one can calculate the gradient of when w (x) and the inverse of Hessian are given. However, for large scale problems, none of these can be easily obtained. Fortunately, by noticing the convexity of each function St. we can replace the first constraint w" (æ) arg min >,,, f(()) with V VΣEn 201) f(w) O. For given x, formulate the following constrained optimization problem:
min fo(w)
(2)
s.t.
f((w) 0,
By introducing the dual variable X, we can easily get the Lagrange function. To solve the Lagrange function efficiently, propose the following augmented Lagrange function.
Teg (w. A) = fo(w) T
Σ f((w).
Different from the standard augmented terms, where the norm square of equality constraints is added to achieve strong convexity of the primal problem, we add the summation of fi's with coefficient 's. ss If we use the norm square of the gradient constraint for general strongly convex functions, it will not be strongly convex. Thus, we can not directly adopt the gradient descent ascent algorithm. With the definition, we can obtain the following two propositions directly.
Proposition 2. Suppose f; 's strongly convex functions for 1,2.... N,, x(1) { 2 0 for all and ||]||| = 1. Then, Problem 2 satisfies Linear Independence Constraint Qualification and its KKT conditions can be written as follows:
V VeJo(w)
f(())==
3

---

Under review as a conference paper at ICLR 2023
Proposition 3. Suppose f& strongly conext for i = 1,2, ..... .N, x(0) 0 for all i
and | = Then, the stationary point of min max Lg (w, X) is unique and satisfies the KKT conditions of problem (2).
Let (10" (x)) be the stationary point of ming max La (w, A). From proposition that ú (z) w* (x) and
2
holds
ffa(w" (x) Vafs(w (x))
(4)
Oxl()
Thus, with the KKT poiont wt (x) and X (x)), we can estimate the gradient of without estimating the inverse of Hessian. However, as A Ei=1 v. can be highly non-convex function, which can be harmful to the optimization process. We add an additional constraint on the norm of X
and define the constraint set A. Thus, the problem (2) becomes
min max Lw fo(w)+ + W AEA
Fufi(w) +
x fi(w).
(5)
We propose double loop algorithm for solving problem We show the algorithm in the Algorithm D and In inner loop, we solve the augmented Lagrange for K steps. In each step, local client will receive the iterates wr.k and Ae, After that, each local client will calculate V (w(,,, and (((,..)) based on the back propagation through two independent batches. The term V f((,,, Ar, is calculated with auto-differentiable framework (i.e. Pytorch, TensorFlow) with the closed-form multiplication. Then the local device sends gradient estimation V. (u.,kk and the estimated product the server.
of Hessian and (V2 fo (w,,,)),,
For the server, in each step, the server will first send the primal variable (wx,, .. and dual variable (At, k) all local clients. Then, the server will receive the estimated gradients and estimated product from some local clients. Because not all devices will stay online in each step, we define a set Active, which records the clients that participant the optimization
(t, k) step. With the vectors collected from local clients, the server will calculate the gradient estimator of Wr.A and λe,k with respect to function T.r,, (w+,k; A., ). And then, Wr.& will be updated by gradient descent step and At, will be updated by gradient ascent step. Different from local devices, after K inner loop update steps, based on the λt.K and gradient estimated each local client, the server will calculate the gradient of based on equation 4 and perform projected gradient descent step In addition, if the in agent is not in Active, we set the gradient of (+) to be zero.
Algorithm The li-le primal dual algorithm on local device
1: for = 2, ... . do
2: for k = 1,. .K do
3: Receive Wr,k, Ae, from the server;
4: Sample mini-batch and calculate f (w),k);
5: Sample mini-batch and calculate fi (Wa,));
6: Calculate (e Dr, with back propagation on scalar V (wo,k)
7: Send 2 f )e and V f((,,,)) to the server;
8: end for
9:
end for
Remark 1. Iλta can be calculated in the i-th device and sent the server, which reduce the computation in the server and will increase one-round communication with one real number between the server and devices. The rest of the analysis will remain to be the same.
THEORETICAL ANALYSIS
In this section, we analyze the convergence property of the proposed algorithm. First, we state some assumptions used in the analysis.
(A1) for fo,f..... IN are lower bounded by and fo. f1, fN have Tn Lipschitz gradient.
(A2) f1 fNN p-sttroggly convex functions.
4

---

Under review as a conference paper at ICLR 2023
Algorithm 2 The Bi-level primal dual algorithm on the Server
Input: Initial ø1, W1.1, A1.1, total iterations: K, I and step size: Teus T) The 2: for ē ===, 1, ... .T do do 4: Send Wr,,. A to each local device;
3: for k = 1.2,
5: Receive () and Ve "..S((un from Activet,:
6: Dhe {o(we,,)) + Activer,a EieActionn, 22 (edi(me)))) + IV (((Wa))::
7:
W1,++1 = WA,K - Mhowii N
ErEActives 24 V
8:
9A = ActivoL,
9:
A1,++1 = ATA (De, + nAgx);
10:
end for
11:
9x(1) A N. (wf((wrk)) for E Activer
12:
9e 0 for i Active
13:
2t+1 Px(xx Tagx);
14:
11+1,1 A,++1;
15:
W++111 = Wt,++
end for
17: Output: IT, WT,
(A3) f..... fN has L2 Lipschitz Hessian.
(A4) (0, .N) max f $ Dw-
(A5) Each local estimation unbiased with bounded variance o².
(A6) Active,, independent and sampled from the set of nonempty subset of (1,2, NN, where P(i Actives,x) p for all i E
,N.
Remark 2. (A2)32))3) are commonly used in the convergence analysis for bi-level optimization problems (Ji er al. 2021 Chen al. 2021 Khanduri et al. 2021). Unlike Ji al.) (2027); Chen et al. 2021g, where they need to assume for JI. :NN to be Lo Lipschitz, we assume the gradient norm are bounded at optimal solution. Because for machine learning models, regularization will be add into objective function, makes the norm of the optimal solution not be large. When w" (x) can be bounded by some constant. (A4) is reasonable in practice. Moreover, the Lipschitz assumption on function directly infer (A4) with D Lo. (A5) is common assumption used for stochastic gradient methods (Ghadimi et al. (016)) and (A6) extend the assumption in Karimireddy et al. (2020) by giving the probability that local devices will be chosen instead of uniformly sampling.
Remark 3. With (A4), Dx max ||x (x)]l is upper bounded by Dw/p.
Proposition 4. When A = (A |A S Dx}, then the stationary point of problem 5 is the KKT point of problem
With proposition and the stationary point of problem (5) is unique and we denote the stationary point as (w" (x). (x)). To give the convergence of the whole algorithm, firstly, we give the convergence guarantee for the inner loop.
Theorem 1. For given x E X, when (AI) to (A6) holds, r>
DaLg+Ly and Tues TA = O(I/KK),
when randomly choose & E {1,2, ,, with equal probability it holds that
afo(w(())) Oz(()
[]]
E
A (i
O(/VKK)
Thus, with theorem I the gradient of x can be "well" estimated through the inner gradient descent ascent method when the number of inner loop steps is large enough. Then, we can obtain the following convergence result of the outer loop.
Theorem 2.
Suppose (Al) (A6) holds, >> DrIgth, no n (1/VK)) 7 0 and #
randomly choosing & E (1,2, K} with equal probability approximate gradient of Define
5

---

Under review as a conference paper at ICLR 2023
arg mig (fo(((" (v)) + E1ly y z=13) and V p = pl for large p. holds that
1 Σ E V Affofoow" (2) 1)) =
Remark 4. To achieve e-stationary point (E) pf ( c). ((1/c*) samples are needed in each local client and in the server. Different from the previous works on bilevel optimizationi e.g. Ghadimi & Wang (2018), Khanduri et al.) (2021) and Franceschi et al. (2017)), we prove the convergence when optimization variable x has a convex constraint.
4.1 PROOF SKETCH OF THEOREM II
To show the convergence of inner loop, we first construct a potential function for inner loop objective. Define P>(w, A) = (w A) 2d(A), A). where d(A) = min (w, A) for given x. The intuition of defining this potential function is that La (w, A) is not necessarily decreasing in each iteration, À is performing gradient ascent step. Meanwhile, gradient taken is an approximation of gradient of obtain that & will decrease during iterations. Therefore, the
d(A). Thus, by subtracting d(A), first thing is to show the lower bound function 4
Lemma (Lower bound of 4). Suppose (A1)-(A4) hold. It holds that P2(w,, X) is bounded below by [-
The proof of this lemma is basically due to the definition of 4x (w: A) and d(A). Then, similar to the proof of gradient descent, we give a lemma that shows the descent potential function under certain choices of hyperparameters.
Lemma 2 (Potential function descent, proof can be found in Lemma Appendix). Suppose (A1)-(A6) hold. In addition, we assume DaLa+h1 it holds that
1
E (wi,k) de,1)) 2 (
& C/ V L. (Wy, d C2
where X [A, + Vd(A.)), C1 O - 1 vス 7x). C2 = O(TA) and C3 0 +
Thus, when choosing sufficient small Th and na. we can achieve positive C1 and C2. Together with the lower bound of the function 4 the convergence of the inner algorithm can be shown. Because of the uniqueness of the KKT point, by choosing The and 17 in order of 1/vK, can be shown that
K
Σ El wie w =(I/VK)))))))))
1 K
EE
- w (xx)) O(IVKK).
K
Therefore, with the convergence rate of We,k and Ae and equation 4 we can easily prove theorem
4.2 PROOF SKETCH OF THEOREM
To apply stochastic gradient descent analysis on although we have smoothness for function fo: fi, ... .N on w, we need to verify the smoothness of fo(w"(( fo(w((x)) (x)) with respect to x.
Lemma (Convergence of stochastic gradient descent with biased gradient estimation, proof can be found in Lemma 14 in Appendix). Suppose function fxx is lower bounded by f with L-Lisshitz gradient. g(x) is an unbiased gradient estimator of V fx) satisfying that expected norm of g(x) are bounded by G in domain X for function f. Then with update rule I1+1 Ixx(x; ne (g(r)) + {.) where 1/2 Q(1 ((//VT), X is convex set and El < 2. By defining & arg min (f())
flly x 2) and V px) = p(x 2), where p 2L, then it holds that
1
+ E
As Lemma 3 suggests, when fo(w" (x)) satisfying T.-L-ipschizz gradient, bounded estimation error and bounded gradient norm, the convergence rate can achieve O(1/VT) with a error term related to estimation error. Theorem 1 shows the estimation error can be bounded by ((1/VK). Combining this two results prove Theorem 2

---

Under review as a conference paper at ICLR 2023
5 EXPERIMENTAL RESULTS
In this section, we compare our algorithm with other bi-level optimization algorithms (BSA (Ghadimi & Wang 2018). SUSTAIN (Khanduri al. 202T) and RFHO (Franceschi al. 2017 in two cases: the toy example and two vision Furks.F in vision tasks, agnostic federated learning (AFL) is tested (Mohri et al. 2019). When k local steps are used in each algorithm, BSA, RFHO, and our algorithm will perform 2kd real number transmission, where d is the dimension of optimization. SUSTAIN will perform (A 1)d real number transmission. In the vision tasks, they perform the same real number of transmissions as k 1.
Figure 1: The figure shows the result of the toy example where all clients participate the opti- mization process in each iteration, and all gradient and hessian are estimated without noise. The above line shows the stationary of x in each iteration, and the second row shows the function value of x (f(w" (z))). The left column shows the results when the number of local steps is I; the middle column shows the results of 5 local steps, and the right column gives the results of 10 local steps. The shadow part of the function value corresponds to the 0.1 standard error area, and the shadow part in stationary corresponds to the 0.5 standard error area.
5.1 TOY EXAMPLE
In this section, we apply algorithms to solve problem (I) with fi as follows:
1
fi(w)= - 1 Bill² + cos(a, w bz),
where A, E 300020 B, E R330 aa E 2R and b; E IR are all generated from Gaussian distribution. The variance of each component in A, and a; is 1/v20 and the variance of each component in B, is 1/v30 and variance of by is 1. When generated function Ja is not 0. -stronnyy convex, we randomly generate new one until we get strongly convex La whose modular is not less than 0.1. Three local steps (K=1,5,10) are tested. Here, the local steps are used for w update for algorithm BSA, RFHO, and our algorithm, and the local steps are used for Hessian estimation for algorithm BSA and SUSTAIN, Because for this toy example, we can easily compute the Hessian matrix and its inverse, we test the algorithm using the inverse of estimated Hessian to compute the gradient of named GD. We test two settings of the toy example. One is the deterministic setting, where no estimation noise or client disconnection will occur. In the other setting, we add white Gaussian noise with noise level of 0.5 in each estimation (including gradient estimation and Hessian estimation). Also, each client has 0.5 probability of connecting with the server.
To evaluate the performance of different algorithms, we calculate the function value of fo(w" (a)) and the stationary of x, i.c. x - 11x (a 0.001 =.foow"" (z))). where w* w²(x) (z) is approximate by 200 gradient steps. We take N 15 and 20 times and get the results of different algorithms. The
results of deterministic setting are shown in Figure [] and results of noise setting are shown in Figure
2
As is shown in Figure [ with local steps getting larger and larger, the performance of BSA, RFHO, and SUSTAIN is getting close to GD, while the performance of the dual method is similar to
7

---

Under review as a conference paper at ICLR 2023
Figure 2: The figure shows the result of the toy example where the active rate is 0.5 in each iteration, and all gradient and hessian estimated with Phite-Gaussian noise with noise level of 0.5. The above line shows the stationary of x in each iteration, and the second row shows the function value of x (f(w" (x))). The left column shows the results when the number of local steps is I; the middle column shows the results of 5 local steps, and the right column gives the results of 10 local steps. The shadow part of the function value corresponds the 0.1 standard error area, and the shadow part in stationary corresponds to the 0.5 standard error area.
GD whatever local step used in the algorithm the Hessian, directly inverse may cause the biased estimation. Thus, the performance of GD gets much worse than it in the deterministic setting shown in Figure Also, in Figure 2 our algorithm can perform better than other algorithms when the local step is small. When local steps increase to 10, BSA and our algorithm have competitive results.
with only single step. When noise is added in
5.2 VISION TASKS
Table 1: Test Accuracy and output of Training LeNet 5 on MNIST. "AP" represents Active Probability, and Accuracy stands for Test Accuracy.
AP
RFHO
BSA
SUSTAIN 99.02% = 0.15%
Ours
Accuracy
98.34% + 0.18%
98.15% E 0.23%
98.43% 1 0.17%
x(1)
0.488 = 0.104
0.425 = 0.081
0.411 + 0.069
0.455 + 0.016
(2())
0.311 = 0.104
0.245 = 0.133
0.305 + 0.045
0.334 + 0.020
(3)
0.197 0.031
0.294 = 0.176
0.282 + 0.029
0.212 + 0.026
~6 4
~ -3
~ 3e 98.85% 0.29%
2e -
Accuracy
98.07% + 0.4%
98.09% = 0.21%
98.43% = 0.19%
(1(1)
0.407 + 0.040
0.395 = 0.136
0.386 + 0.058
0.449 1 0.046
0.9
(=())
0.281 = 0.065
0.314 = 0.045
0.345 = 0.028
0.333 + 0.050
(3)
0.291 + 0.018
0.239 = 0.085
0.265 0.038
0.217 + 0.024
(4))
~ 4e 3
~ 8e 3
~ Te 7e-
2e 4
Accuracy
97.86% 0.36%
95.37% 4.100%
97.60% = 0.49%
98.24% = 0.23%
x01)
0.449 0.090
0.539 = 0.076
0.365 = 0.015
0.468 + 0.052
0.5
(2(2)
0.276 0.075
0.217 = 0.059
0.329 + 0.013
0.372 + 0.053
(1(3)
0.271 0.129
0.210 = 0.039
0.292 = 0.015
0.16 + 0.035
z ((1)
6 4
6E 3
2e 3
2e
In this section, we apply algorithms to train LeNeett et al.
1998) on dataset MNIST(LeCing
al. 1998) and MashioonMNIST(XXX (Xiao al. 2017). To construct non-iid datasets on different local clients and the global server's 's validation set, we randomly pick 20 samples per label out of the whole training dataset and form the validation set. Then, the rest of the training data are divided into sets, and each set will be assigned to a local client. The first client contains samples labeled 1,2,,,3,4 the second client contains samples labeled as 5,6,7, and the third client contains samples labeled as 8,9 for all two datasets. To test the algorithm's 's ability to choose the proper coefficient of local clients, we add 7 noise nodes containing 5000 samples with random labels. We set the learning rate of uo to be constant learning rate without any decay selected from (0.1, 0.01, 0.001) } for all training
8

---

Under review as a conference paper at ICLR 2023
methods, and the learning rate of is selected from {0.1, 0.01, 0.001, 0.0001]. The batch size for all three training cases is set to 64. I used in the proposed algorithm is set to be 1. For simplicity. we set the local step 1. We run 2000 iterations for MNIST and 6000 iterations for Fashion-MNIST Active probability is set in {0.5, 0.9, 1). We compare the test accuracy among different methods. As baseline, we report the test accuracy for training with the validation set only named val, training with the average loss of each client named avg, and training with r = (0.5, 0.3, 0.2, 0, ... 0) named
opt. All experiments run on V100 with Pytorch (Paszke et al. 2019). Results are shown in Figure 3 Figure 4 Table I
Al
Figure 3: Test accuracy of training LeNet 5 on MNIST dataset. The left curve shows the result when the active probability is I; the middle curve shows the result when the active probability is 0.9, and the right curve shows the result with the active probability of 0.5.
Figure 3 shows the test accuracy of the MNIST dataset with different active probabilities. Although SUSTAIN works better than the primal-dual algorithm when all local devices participate in the optimization process, when clients' participant rate decreases to 0.5, SUSTAIN works worse than ours method. Primal-dual become slower than SUSTAIN may be because of the initialization of the dual variable. When the dual variable is far from its real value needs more time to get a good enough point. Other than SUSTAIN, our algorithm can converge faster and more stable to a high accuracy point. Further, we list the output of x and standard error of test accuracy for 5 different experiments for different algorithms in Table [ According to Table I our algorithm can achieve more stable output with respect to z, and the output is more close to 0.5, 0.3, 0.2, which is related to the number of labels the first three clients holds.
Figure 4 gives the test accuracy of training LeNet 5 on the MaSHIon-MNIST Dataset. Similar to the results of the MNIST dataset, when the clients' participant high (0.9,1), SUSTAIN works slightly better than the primal-dual algorithm. But when more local devices disconnect to the server, the performance of SUSTAIN drops, while the primal dual algorithm remains fast convergence speed and high test accuracy.
Figure 4: Test accuracy of training LeNet 5 on the Pashion-MNIST datasct. The left curve shows the result when the active probability is I; the middle curve shows the result when the active probability is 0.9, and the right curve shows the result with 0.5 active probability.
CONCLUSION
In this paper, we proposed a primal-dual-basee method for solving bi-level optimization problem based a federated learning tasking (local coefficient learning). We give theoretical analysis that shows the convergence of the proposed algorithm. Though the analysis shows needs more iterations for the algorithm to converge number of local steps in both toy case and neural network training. Other than that convergence rate can be improved (perhaps it should be in the order ((IvTT) instead of O(1/VT + 1/VK)), the initialization of dual variable affects the speed for convergence, which leave as the future work.
c-stationary point, it works well with a pretty small
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Dimitri Bertsekas. Convex optimization theory, volume 1. Athena Scientific, 2009.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. A single-timescale stochastic bilevel optimization method. 2021.
arXiv preprint
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 with theoretical guarantees: A model-agnostic meta-learning approach. Advances in Neural Information Processing Systems, 33:3557-3568,, 2020.
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient- hyperparameter optimization. In International Conference on Machine Learning, pp. 11365-117.. PMLR. 2017.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXivv1802.02246. 2018
Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini batch stochastic approximation methods for nonconvex stochastic composite optimization. Muthematicul Programming, 155(1):267-305
2016.
Zhishuai Guo and Tianbao Yang. Randomized stochastic variance-reduced methods for stochastic bilevel optimization. arXiv e-prints, pp. arXiv-2105, 2021.
Pierre Hansen, Brigitte Jaumard, and Gilles Savard. New branch-and-hound rules for linear bilevel programming. SIAM Journal on scientific and Statistical Computing, 13(5):1194-1211 1992.
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pp.
PMLR, 2021.
Yihan Jiang, Jakub Konečný, Keith Rush, and Sreeram Kannan. Improving federated learning personalization via model agnostic meta learning, arXiv preprint 1eXiv:1909.124450 2019.
Sai Pranceth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning, pp. 5132-5143. PMLR, 2020.
Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A near-optimal algorithm for stochastic bilevel optimization via double-momentum. Advances in Neural Information Processing Systems, 34, 2021.
Charles D Kolstad and Leon S Lasdon. Derivative evaluation and computational experience with large bilevel mathematical programs. Journal of optimization theory and applications, 65(3): 485-499, 1990.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86( (6(11):2278-233) 1998.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In International Conference on Machine Learning, pp. 6357-6368. PMLR, 2021.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. arXiv preprint arXiv:1907.02// 2019.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Interna- tional Conference on Machine Learning, pp. 4615-4625. PMLR, 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-peeffrmance deep learning library. Advances in neural information processing systems, 32, 2019.
10

---

Under review as a conference paper at ICLR 2023
Chenggen Shi, Jie Lu, and Guangquan Zhang. An extended kuhn-tucker approach for linear bilevel programming. Applied Mathematics and Computation, 162(1):51 63, 2005.
Canh T Dinh, Nguyen Tran, and Josh Nguyen. Personalized federated learning with moreau envelopes. Advances in Neural Information Processing Systems, 33:21394 21405, 2020.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arX1n:1708.07777,,0000 2017.
A CONVERGENCE OF INNER LOOP
For simplicity, in this section we simplified the inner loop problem as the following:
min g(w)
w
s.t. Vh(w) = 0.
Besides, the algorithm for solving the inner loop problem can be simplified as
W++1 = Wi 7u (gg(w)) + ( (elii))+++VVVVV +IVh(w)) = w, - The (WW,,
A411 = II (A+ + TA Vh(w))
Furthermore, the assumptions are as the following:
(A1) g and h are differentiable strongly convex function with modular μu, -i-isschitzz gradient and lower bounded by f-
(A2) à has Lz-Lipschitz Hessian.
(A3) A [All S Dx), where D Z (V"h("))~ VV(w")) and w² arg min h(w).
(A4) Given W4, (w:) (wo,,, Vh(w)) and Vh(w:) are independent to each other. Besides, all of them unbiased estimators with bounded variance with respect mean value and bounded constant o,, i.c.
E
(g(w))
|
we = Vg(w)),
E
Vg(wee) Vo(1o))
w/
S pll V
+ oo²
E
(h((w) = (Ph(wz),
E
(2h(we)) - vPh(w))
splV> (w:))) +
E (h(w))) wi Vh(we),
E
()(wz)) Vh(we>)('
$ <1]]b((w>)] +
Thus,
it is easy show
E
V L(ws, Ae) we, No]
VoL(wr, and
E & Le Ae) - vn Lwee, de)
we,,
First, give some notations that will be used in this section.
Definition 1. Let L(w, X) g(w) + AT Vhh(w) + Th(w), d(A) = min L(w, A), (²) min, L(w, A), X = (A + TX Vh(w:))) and L. = +1+T) + Dx
Define potential function (ww, Ae) L(w,, A²) 2d(x)).
Lemma 4 (Descent of Lagrange function), For the function L, it holds that
E [[([w1+ (441) L(w,, Ac)]
E Co(nw))l V., L. 12 Lini (1 + + (Det1 Ao) T Vh(werz))
where Co(ni)) Leni Le p(14- ne-

---

Under review as a conference paper at ICLR 2023
Proof. Because L(w, X) has Ly Lipschitz gradient, it holds that
LL M[ A,) S T(wr, Xe) + Vw.L(wr At), w1+1 wx) + 11 well?.
By taking expectations with respect to wy and d on both side of the above inequality, we obtain that (W((1, Ar) - L(wee Ar) Wt, Xe]
LL |0++1 well? |we, de)
E
Vn Ae); w++1 - wee + 2
V u [(u,, Ae); Tho Vn Iwre, Ar)) + LI || V (ooe,e
E
I.
Lw Ax) - VwL(wr. xe)1( We, Ne
+
2
L 2 2
LL 1 +=+D3 +D2) 1/(e mmn) ([s, + L + D2)0²
E
W2 An
2
2
(6)
Meanwhile, it holds that
E [L(u441 A441) L(we+1: I Ad] E [Av+1 - Ao) VV) Ad]
(7)
Combining 6 and taking expectation on the conditional expectation, we can obtain desired result.
Lemma 5. Suppose Ip DxL2 L1, it holds that
|| (M1) - w (A2)ll SB111>1 Azll
for all X1, X2 E A, where 31 = Tp-DALa-L1
L1
Proof. Note that L(w, A) is a strongly convex function with respect to the w in the domain À E A with the modular (1 + T)p- D2L2- Thus, it holds that
Tμ DxL2
L1 (A1) (A1) w" (22))
L(w" (A1), A2) - L(w" (12),
2
On the other hand, we have
L(w 22) L( (22)
-(ww" (A1) A2) - L(w" (A1), A1) + (w"(A1),)) - L(w" -LL
+ ((ww((22) (>)) - L(w" (22);
< (A1 ( (A2)) - Vh(w (A1))) Tμ DxL2 - L1 1|00 (A1) w" (X2))l?
2
Thus, by combining the above two inequalities, with Cauchy-Schweee inequality, we can obtain
(T' DxL2 L w" (A2))12 < || A2ll Vhwl (Ai)) vh(w)(22))
< L L1llA1 - >21lll (A1) - w" (A2)ll-
Hence, we get the desired result.
Lemma (Ascent of dual function). It holds that
La 2
[(d(A(1)) d(xa) E (Je11 No Vh(w" (Ae))
Di++1 - Xrll2
Proof. It can be calculated by the implicit function theorem that
Vxd(A) Vh(w" (A))-
Thus, we can obtain that for all Å1, A2 E
(vd(A)) - vd(Aa))l [h(w" (A1)) Vh(wo (12))) & T.8:1IA1 AzIl-
12

---

Under review as a conference paper at ICLR 2023
Therefore, d(x) is differentiable function with La L1 Lipsships gradient. With the definition of d(A), we have
Ld |1 - del12 (d(A++1) d(Ac)) 2 ( des (M(ww((ee))
Lemma 7. With the strongly convexity of L and h, it holds that
1 Vh(w" (2))
||0* (Xe) =w0l
and
1
ww w (N=)ll
V (wr
Tp DxL2 L1
Proof. Because of the u-strongly convexity of the incquality pmllr w2 s Vh(wi) Vh(w2)] holds for all W1, W2.
With the Vh(w") O, get the result.
Similar to h, because of Tp DxL2 L1 stronlyy convexity of L, we can prove the second inequality.
Lemma 8 (Descent of one step local SGD). It holds that S E [1 (1 + v)llV L(w,, 2r)]1 o2
El we Wz+1
Proof.
E l0: we+1l12 =E Mil V.. (c)) S SE [1 V. dx)11 + 0²
Lemma 9. d(A) tir -strnngyy contaio We define pdd t
Proof. Let Yu be the largest eigenvalue of V2d(A), 72 be the largest eigenvalue of holds that 7 < pt
Ow*()) ax Then,
Meanwhile, 8w (A) 8x
V ( Thus, 71 S 14
Therefore, d(A) a E -trongly concave funtion.
Lemma 10. holds that
LinAA ps
B|JA++ - >x11
E
11
PATIA
N2002 + 22 + p)
E
Blw
w (Xee)
16
Proof. With the update rule of Aeti, it holds that
E Dlee - 2012
= EI (A+ + TA Vh(wa)) 11
< E|AA, + MA Vh(w.) 2
E [IA+ - 2-12 27/ (de X², vh(w))) + 7 (
(8)
= E [[Ar - 1-12 + 27A - X", vh(w"(A)))
+2 - X3, Vh(w;) - Vh(w (A+)) + +
where the last equality is because Vh(w) unbiased estimator.
13

---

Under review as a conference paper at ICLR 2023
Meanwhile, because d()) is strongly concave function, it holds that
nA(A - X", Vh(w" (Ar)) & -nxMall>s - 1-1
(9)
Further, it holds that
E vh(ww)ll = (l) -
-
S 0² B(1 V))
I < E2(1 [x) + VV (Ae) vh(we))1 (10)
3 0² + E2(1 + p) [x) + p) (A. -wrl
0 E2(1 +
+ p) (Ae)- well
For (A. - x3, Vh(w:) - Vh(w" (Ax))). it holds that
(Ae-X - X3, Vh(w:) - Vh(w" (Ae))) -
Pd 1 --11 +
1 |[h((w)) - Vh(w" (he)1
2
2pd
(11)
Pd 1 x=112 +
L?
1 w (Ae)l1
2
2pd
Combining 8 1.. 10 and (TT)
it holds that
E1 11
17nx Nd
$ (1 -aMs + 2(1 + 1) X + 1200
22 + p)
Ellw, w= (Ae)l1
When 7IA S
Ad 4(1+p)2g
it holds that
PaTA E -x 11/10+1/000-- (20R(1 + +D)L
Linx pd
2 X112 5
E Bl(., w² (Ax)11
(12)
holds that
El|Ae+1 xell2
-El/e41 22 x- ~xel?
=E [[lA++1 - 2=112 + 1|2- - >xel22 + 2-2e+11 -,,,-~ -x)] -x))
-
(13)
2 E (1 -1)llA+41 - 2 + 1 - 5 || | --ellll ,VE>
Let 1 + Hama/4 (1- - <) (1 mana) + (1 (1- 1) {
2 /26 combining 12) and 13) it holds
that
El 2ee+1 -xel2
(1 (1) {) (1- Malli
+ (1 (1-1) 11A - + 1200+ + (1 +p)
LinA Ma
El Eller - w (A:))12
2
n2002 + ( (17-- Dxl2 Ii
21 +p)
Li7TA
EE de - X3 111
MalA
Blluc w" (20)11)
16
4
MaI'u DxL2 Ln
Thus, get the desired result.
Define potential function P(w,, A1) L(wi, A1) 2d((2). According to the definition have
L(w,, Xx) > d(Ax). Then, D(w, Xx) 2 -d(x,) 2 -in g(w) + +T((w) 2 -(1+ + r)ff for all w, and d E A.
14

---

Under review as a conference paper at ICLR 2023
Lemma 11 (Descent of potential funetion). It holds that ( de+1) ( Ax)]
s E Vo xx)11 -2 11ll7 + +C3
where
C1 Tle + L (1 D2)
+ +4LinAni (1 p)
2
4IZyA
17nA pd
+
Ad
22 + p)
(Tu -DxL2 - L1}
16
C2
64
C3 TL (1 + +T2 + D2)0²
2LP + +2?00² +
2
16
Proof. With Lemma and Lemma 6 it holds that
E [ (Wi+1, )ct1) - 2 (we, Ac]]
E (Co(nw))lV Ww 1ll + (de+1 - VV((w++) 2(A++1 do, Vh(w" (Ac))) + LallAe+1 Xxl13)
L r + D2)0²
We deal with each term as follows. For the second term and the third term, it holds that
(A++1 Ad) Vh(wi+1) 2(Ac+11 do, Vh(w" (Ae)))
=2(Ac+1 - X,, Vh((w+1) - Vh(w"" - (A++1 ->x) Th)TThi Vh(we+))
1
$ 2L, 1 Alllwwe+1 - - (Ax)ll - || - -eel?
77
1 - |1++1 - Aell2
S 22/ - dell (Ilw: w² (A+)))ll -| -wiell wwell)
77
1) ||t+1 2 4T2y 1|u: w (A.))l1 + 4T.7 Al 10x 112
2Ta TA
By taking the expectation on the both side of incquality, it holds that (A.-1 - No) T Vi(we++1) 2(A++1 de, Vh(w" (Ac)))
E
- (Ae))l + 4L3 || well 2npx Ilett1 Xx11 -wa)))"
4L7nA
[|A441 - X.11 4L V A.)1 + (Tp DaLe L1)2 11 ( + +2L2n2200?
<
2tpx
Meanwhile, with Lemma and Lemma it holds that
El1A++1
Xell?
19/12 BlIA+ - 11
T.71AA
PaTTA
2 +
2n p)
Bllw: w- (Ae)l1
16
4
Hd
P BlIA+ 11122
PalA
nAO²
2 (1 p) +
(W 2011
16
Hd
Further, when 7 < 1/((4.a)) it holds that
|ee+1 Xel12 TaalAeet - 2el12 S 4m
2nx
Thus, it holds that
E (W(Ww+1. det1) - +b (w,,, Ac)]
E (o V x0 2 (de+1- - Vh(we+t) - 2(x+41 de, (h(w((Ae))) Tall>et1 Ax.17]
T (1 r 02)
$ E C1 V (ws, A2) C2llA, - 2112 + Ca.
15

---

Under review as a conference paper at ICLR 2023
where
Lr. LI +1= D2))
C1 = - t/o +
+
+ +4T,TaATe + +p)
2
2
+ (Tμ DxL2 {1)2
4L7NA
+
Pd
2 + pp
Li7A
16
pd
C2 7A12
64
C3 T (1 + T2 T2 D2)
+217nnm 2 +2n00=2
16
Proof. Proof of the Inner Convergence
By the definition of db it holds that (ww, A) d(()) f. Thus, with Lemma by summing up T terms, it holds that
MALi 8pt
D(w1, -
1e 2
L( A0]1
1 2r11
+ C33
K
K
1=1
Then, let The ((1/VK) and π = ((1/V it holds that
A X =01/VK)
K
[w - w
On the other hand, it holds that
|l V X ( 2- +I -
< 2D Ar 2- - ==12
Therefore, holds that
K
2 K
E K
B PROOF OF OUTER LOOP CONVERGENCE
In this section, we give the proof of the outer loop convergence.
Lemma 12. Suppose (A1)-(A4) holds. Then, for all z x2 X, it holds that
VND + VND
[[w0(zn) w (x2))l
|
32
n22
Proof. Because MN 222 fi(w) is is strongly convex function, it holds that
(6)
N
(0 (f((w (w=222 2 "
2 |w= - w" (x2))12.
16

---

Under review as a conference paper at ICLR 2023
On the other hand, we have
N
N
2 f((w"(z)))
Σ 2 fx(w + Σ o 1 (x1)
1 fi (22)) + fi(w (x2)) - Σ
(2) (zz))
22
1=1
am1
Σ (fi(w filw" fi(w"((1))) b 11=2(x2) w (x1))]
Meanwhile, we have
L1
[f((w"
(a))) (x))) (0=))())))1
I| (22) - (x1))l
With strongly convexity, holds that
(x2) w (x1))l S - 2D
Thus, it holds that
f(2w (x1)) s D1 + L1/1)](w(xz)) w0 (x1))l-
Combining the above inequalities, it holds that (x1)- w (I² "x]l"(x1)-v < 1| (maa))/llm (s)) S V (x)))
(x1)-w" - (x22 )|
Lemma 13. Suppose (A1)-(A4) holds, then fo(w" (x)) has Lipschitz gradient with Lipschitz constant
21 VN D. pt ND
a²
Proof.
0fo(w(())) Or(9
N
(xf
Σ
00 ve
(f)( V
Vufi(w((2))
By the smoothness and strongly convexity it holds that
( 22 Vf
2
(1)
V
2
v
(w (22))
N
(
V f3 (10 (x1))
(
22 (
J2
1=1
$ max || 2 V fz (w (Ix) - (5z(w((22)))
222 j
w
L2
ww=" (x1) " (*2)))
2
17

---

Under review as a conference paper at ICLR 2023
where the first inequality is due to ||A(A-) 1AA(A''---)1 -B=B) ||A Then, holds that
B|| for all invertible matrices A, B.
N
N
① 2 w
V vwli(((( (x1)) -
1 V2 V5z(10 (xxa))
V (
11
/=1
2 2 V
fz (w)
V2 w V (x2)))
Vufe(w
22
+
Σ
22
(i) 2 V fy (x2))
(zi((w((1)) (x
Dw
- (1w00()) w" (x2)l1-
[w=((i) (x1) w² (22)
Thus, combining with the definition of gradient, it holds that (fo(m((xz))
Ofo(w (x1))
Oz vz(()
[
N V Vuli(w
fow
V
Vull("(<i))
[
N
+ (wfolw"(<1)) V folw (x2)"((x)))
2
()
Vi V5 (1/www(xx) (xx)))
Fuff(ww((2)))
L1 S Dmm Dz 22 (Iww((a) w/ (x>))l I| (m1) wt (az)l)) + Duti (1o0 - w (x2)ll
Therefore, combine with Lemma 12
obtain the result.
Lemma 14. Suppose function fxx is lower bounded by with L-Lipshitz gradient. g(z) is
an unbiased gradient estimator of V f(x satisfying that expected norm of g(x) are bounded by G in domain X for function f. Then with update rule 24+1 = xx - (g(e)) {))), where
Th = =01/vVT) X is convex set and and E|| < 2. By defining = arg m (f()) + f1ly==11²
and (x:) = p(x 1), where = 2I, then holds that
T
T
Proof. It holds that
E (f(kz+)
+ L
|+41 - 12)
2
< (s(#)) +
| 13
E (f(a.) +
x (xt (g( + +.)) =t.l(²)
< E (f(&.) + 10 (g(x)))) +5+ 10-- =..l3)
= E (f(*)) + |2, - 12 + pn (x))) + Ex12
nuplare - Er, g(x)) - "oplix - 2e, Ex)
< E (S(*)) + 6 |0 - 11 + (C2 + - mmaE (s(zz) (((c))
L -1,0 - Eell?
1
+ F.
11122 12 +
21
18

---

Under review as a conference paper at ICLR 2023
Then summing up the above inequality, it holds that
T
E (f(1e) f(a,) L||> =Ell9)
/1,00 - -i112 (f( -1101+1- -Br+113)] TG + Tpn e
S
E
[(b))
2
f(1)) + 2 ||| a - f) + T Tp (G² +2+ Tp e²
2L
On the other hand, because a. arg y (f(v) + =11l,,, - yll²) and function f(y) f1,,, - yyl? is strongly convex with modular L, it holds that
f(x)) [(ae) -1| 1|²
= -((x)) + -1lez - =ze122 - (f(xt) + 2 11lee =x + P L - -1
2 1 12,11 112
2
2p 3L.
L
2 |x, iz 2.12 = - || - 2ell ?1?
2
Thus, combining the above inequalities, it holds that
art 1111
2p²
<
E. - (((t) - L1|2s - =
TT.
pf({)) 1 :1:01 -J1ll pf) + +p² 1 (C))
+ p²
Tmk
2T.
Therefore, when 1/2 O1I/V//VT....
-EST [.)(()) = 4. E Eli - =
2).
Proof of Theorem 2 With Lemma 13 X.
we can obtain fo(w" (x)) has Lipschitz gradient on domain
Define g(0) X2 (()
-
When we use λe, and wi, with random k, as it suggests in Theorem the expected norm of E can be bounded by O(1/VK)
Let (3)
241/2 zt (6)
nh (g(x)) + XT V (.f((wn))) x f(
Then, holds that
(g( = E
(II - xx) X V V = VV(x.)"V..l"'"
The
and
E (9(2,) <
Wwfi = 2 202
Thus, together with Lemma 14, we can directly get the result.
C ADDITIONAL EXPERIMENTAL RESULTS ON MNIST AND FASHION MNIST WITH LENET5
We 10 clients in this experiment. The first 5 clients contains i..d. 9000 samples, the last clients contains 9000 samples with random label. The rest setting is the same as it in the main text. The results shown in Figure 5 and Figure 6
19

---

Under review as a conference paper at ICLR 2023
Figure 5: Test accuracy of training LeNet5 on MNIST dataset in iid case. The left curve shows the result when active probability is I, and the right figure shows the result when active probability is 0.5.
Figure 6: Test accuracy of training LeNet5 on Fashion-MNIST dataset iid case. The left curve shows the result when active probability is 1, and the right figure shows the result when active probability 0.5.
20


Reviews:
[{"review_id": "qXG8s5cAAX", "reviewer": "Reviewer_Yrj6", "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 author(s) formulated the objective of the federated learning problem as a bi-level optimization problem. The author(s) proposed an algorithm that solve the bi-level optimization problems with stochastic gradient oracle. Convergence analysis of the proposed algorithm is given and experiments on toy and real-world datasets are conducted to evaluate the proposed method.", "summary_of_the_review": "The writing and presentation of the paper should be improved. It is not clear if the bi-level formulation is important, evidences (either theoretical or empirical) for the problem formualtion is not given. The current version of the manuscript seems not good enough to appear in ICLR.", "strength_and_weaknesses": "The major issue of this paper is the writing and presentation, I list some writing issues I found when reading the paper:\n- The first sentence is exactly the same as the first sentence of the abstract.\n- The citation format is not very careful, should use \\citep in some places, for example in Remark 1.\n- What is $w$ and $x$ in equation 1? Although these information can be recovered in the following context, it is still better to explain equation more clearly after equation 1.\n- Second paragraph of introduction: propose and algorithm -> propose an algorithm\n- Second paragraph of introduction: gradient calculate -> gradient calculation\n- Second paragraph of introduction: will involved -> will involve\n- Section 2.2, One Franceschi et al.., the sentence is informal\n- Section 2.2, Different from above work -> works\n- The paragraph below Proposition 1, For given x -> For given $x$.\n- What is \"LICQ\" in Proposition 2.\n- The paragraph below Proposition 3, constraint set ad $\\Lambda$ -> constraint set $\\Lambda$.\n- (A1), should be $f_0, \\ldots, f_N$ have $L_1$ gradient and are lower bounded by $\\underline{f}$.\n- (A4) looks weird, it looks like a conclustion instead of an assumption.\n- (A5) Better to express it with a math formula.\n- Proposition 4, when ..., then the stationary point....\n- The paragraph below Theorem 1, theorem1 -> theorem 1, Then, We -> Then, we\n- Remark 2, bilevel works, too informal, should be previous works on bilevel optimization.\n....\n\nSome other issues:\n- It is not clear to me why the bilevel formulation (problem 1) is important. Seem like an intuitive problem formulation without much theory behind it?\n- The author(s) stated that $f_0$ depends on the validation set, which is weird. In ML, validation set usually used for hyper-parameter tunning and should not be involved in the training.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "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": "h1vmPyWLmZ", "reviewer": "Reviewer_BDrt", "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 considers training a global model on the server using updates receive from clients. The paper proposes that clients and the server collaborate to solve a bi-level optimization problem. This enables the server to learn the global model using the optimal parameter and combination of the local objectives.", "summary_of_the_review": "In summary, the paper proposes a novel federated learning algorithm with theoretical guarantees. However, the empirical study in the paper is not enough to show its effectiveness.", "strength_and_weaknesses": "Strength:\n\n1. The paper proposes a new bi-level optimization algorithm for federated learning to find the optimal parameter with respect to local objectives.\n2. The paper provides the convergence guarantees for the proposed algorithm.\n\nWeaknesses:\n\n1. Using the proposed algorithm, the server has to perform more computations than other well-known existing algorithms. One of the benefits of federated learning is to push the computations from central servers to edge devices with good computational capability. This can adversely affect the applicability of the proposed algorithm compared to fedavg-based existing ones especially when the number of clients is large.\n2. Experimental results presented in the paper is not enough to show the effectiveness of the proposed algorithm. The paper mainly compares the proposed algorithm with bi-level optimization methods. However, I believe that it is better to compare the proposed algorithm with other fedavg-based algorithms in terms of both training time and test data accuracy. Also agnostic federated learning and personalized federated learning are closely connected to the study of the paper and it would be interesting if the paper compares the proposed algorithm with some personalized algorithms as well as agnostic federated learning.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "XrJpna1FVH", "reviewer": "Reviewer_KXgD", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 deals with a specific setting of Federated Learning where the goal is to find an optimal weight between all the local objectives so that the learned parameter can be optimal for some different global task. To do so, this paper first formulates the above setting as a bi-level optimization problem over the weight parameter and the model parameter. Then, to solve this bi-level optimization problem, the paper reformulates the bi-level problem into an optimization problem with equality constraint using convexity assumption. Then the paper introduces a primal-dual algorithm and gives convergence guarantee under the case where each local objective function is strongly convex. Since it is possible to encounter a constrained optimization problem with non-linear equality constraints, the paper proposes a new Lagrangian formulation with an augmented Lagrangian term. They shows that due to this new term, the primal-dual optimizer can converge to the KKT point of the original bi-level optimization problem.", "summary_of_the_review": "My current recommendation is reject. \nMy reasons are the following:\n\n1. The paper has some good theoretical results and empirical results. However, the current paper seems more like a rough composition of these results and does not have a very clear story for me to follow. I did not see a very clear motivation of the problem.\n\n2. I do not think problem 1 is a novel problem formulation. Therefore the paper should discuss its relation with some closely related problems like meta-learning. \n\n3. Technical novelty is not clear to me.\n\nOverall, I think the current draft requires a big amount of modifications to make it reaching the acceptance level. \n", "strength_and_weaknesses": "Strength:\n\n1. The presentation is good and easy to follow.\n\n2. The mathematics seems correct (though I did not check all the proof details).\n\n3. The problem itself (i.e. equation 1) is meaningful.\n\n4. Extensive experiments are conducted to support the theory. \n\n---\nWeakness: \n\nNot well-motivated: I indeed believe problem eq (1) is a very meaningful problem. But I do not think there is enough motivation in this paper. \n\ni) the original motivation is that one would like to train a model parameter that is good for some global task $f_0$. This makes sense but why not directly optimize for $f_0$? The reason is (my understanding) there is not enough data for optimization w.r.t. $f_0$ directly and therefore we need some pre-training using all local clients’ data. Motivation like this should be emphasized. \n\nii) under the same motivation, equation 1 is only one of the many ways to formulate the problem. It would be necessary to discuss alternative problem formulation as well. For example, why not first pretrain on local clients data using federated learning and then fine-tuning on few-shot data from task $f_0$? \n\niii) When I first read, it was not immediately unclear to me why the estimation of Hessian in the previous methods is hard to implement under this paper’s setting due to the large amount of data. My understanding is one cannot get an unbiased estimator of the Hessian. Issues like this should also be discussed in more depth because it motivates the paper. \n\n2. The paper considers the case where all the $f_i$’s are strongly convex, which is the most simplified case. That is fine. But the paper did not explicitly discuss the unique technical challenges under this setting. It is hard to justify the technical novelty given the current writing. I do believe the augmented Lagrangian term is novel but it is hard to judge given the current writing. Besides, the algorithmic design section is also hard for me to spot what is the novelty. I think the authors should emphasize the technical challenges and novelty. \n\n---\nQuestions: \n\n1. Motivate problem formulation given by equation (1). Especially, what is the relation between this problem and meta-learning? In Meta-learning, one would like to find a model parameter that is good for (possibly unseen) downstream tasks. This is clearly very related with this problem considered in this paper. \n\n2. In the paragraph below equation 5, the paper mentions that the term $\\tilde{\\nabla}^2 f_i(w_{t,k})$ is calculated with auto-differentiation. Explain why we need to calculate this term and why it is easier than the calculation of Hessian in previous approaches. \n\n---\nMinor comments/suggestions/typos:\n1. Typo in Alg 1 line 7.\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": "IvRcLeDmCF", "reviewer": "Reviewer_Ycsn", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 paper focuses on solving the local coefficient learning in federated learning as a bi-level optimization problem. Instead of directly solving the bi-level problem, they reformulate it as a convex-concave problem where they propose a double loop algorithm to solve it. The authors show that the proposed algorithm achieves the sample complexity of $\\mathcal{O}(\\varepsilon^{-4})$ to arrive at a $\\varepsilon$-stationary point. Experiments on synthetic and vision datasets are conducted to illustrate the performance of the new primal-dual appoach versus existing bi-level algorithms.", "summary_of_the_review": "As mentioned above, I believe the paper does have contribution in algorithmic design to solve the bi-level optimization but it is not clear whether the new algorithm is suitable for federated learning. Also, the comparison metric using performance in iteration may not be fair as the communication payload is different among the algorithms used in Section 5.", "strength_and_weaknesses": "Strengths:\n- The primal-dual approach presented in the paper appears to be new compared to existing work.\n- Theretical analyses are provided. I have gone through the key steps in the proof and find no problem but there's a chance I miss something.\n- Numerical experiments on synthetic and vision datasets show that the new appoach obtain promising performance.\n\nWeaknesses:\n- I have one major concerns which is the applicability of the proposed method in federated learning. I am not sure if the authors design the new primal-dual algorithm as a federated learning algorithm or not. If it is, then the local devices should send back their local models instead of the stochastic gradient/hessian. Therefore, I believe their algorithm instead is somewhat a distributed learning algorithm, not specifically for federated learning. I notice that only in this paper the bi-level optimization is applied to federated learning while others do not mention it.\n- Another concern is about the metric of evaluation. In federated learning, the main challenge is the communication efficiency (or the number of bits communicated between clients and server). As a results, other federated learning methods use performance over communication round or communicated bits as the metric of comparison. I think the metric in section 5 should be adjusted to illustrate this. Also, the payload of the primal-dual apporach can be twice as much as others such as BSA in 1 iteration so it might not be fair to use iteration as in the current paper.\n\nMinor comment:\n- Typo on page 9: when all local devices participant in -> participate in\n\nSuggestion for improvement:\n- I think it would be good to discuss the convergence rate obtained by the primal-dual approach vs existing work as I need to go back to their original paper to retrieve their rates.\n- I hope to see clarification whether the new algorithm is for federated learning since it does not follow federated learning framework where clients only send back local model instead of local gradients.\n- The metric of comparison for numerical experiments may need to be revised to match standard comparison in federated learning.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject