Personalized federated composite learning with forward-backward envelopes
Authors: Jiang Hu
Jinhyun Ahn
Na Li
Quanzheng Li
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated composite optimization
personalization
forward-backward envelopes

Abstract: Federated composite optimization (FCO) is an optimization problem in federated learning whose loss function  contains a non-smooth regularizer. It arises naturally in the applications of federated learning (FL) that involve  requirements such as sparsity, low rankness, and monotonicity. In this study, we propose a personalization method, called pFedFBE, for FCO by using forward-backward envelope (FBE) as clients’ loss functions. With FBE, we not only decouple the personalized model from the global model, but also allow personalized models to be smooth and easily optimized. In spite of the nonsmoothness of FCO, pFedFBE shows the same convergence complexity results as FedAvg for FL with unconstrained smooth objectives. Numerical experiments are shown to demonstrate the effectiveness of our proposed method.

Under review as a conference paper at ICLR 2023
PERSONALIZED FEDERATED COMPOSITE LEARNING WITH FORWARD-BACKWARD ENVELOPES
Anonymous authors Paper under double-blind review
ABSTRACT
Federated composite optimization (FCO) is an optimization problem in federated learning whose loss function contains non-smooth regularizer. It arises naturally in the applications of federated learning (FL) that involve requirements such as sparsity, low rankness, and monotonicity. In this study, propose personal- ization method, called pFedFBE, for FCO by using (FBE) as clients' loss functions. With FBE, we not only decouple the personalized model from the global model, but also allow personalized models to be smooth and easily optimized. In spite of the nonsmoothness of FCO, pFedFBE shows the same convergence complexity results as FedAvg for FL with unconstrained smooth objectives. Numerical experiments are shown to demonstrate the effectiveness our proposed method.
barkward envelope
INTRODUCTION
Federated learning (FL) is originally proposed by (McMahan et al. 2016) to solve learning tasks with decentralized data arising in various applications. For example, data generated from medical institutions which can not share its data to each other due to confidentiality or legal constraints. Instead of accessing all the data sets, different institutions clients under the coordination of central server and the central server aggregates the local information to train a global model. Similar methodologies have been investigated in the literature of decentralized optimization (Colorni et al.) 1991; Boyd et al., 1 Yang et al., 2019). For more introductions and open problems in the field of federated optimization, we refer to the review articles (Kairouz al. 202 Wang et al. 2021).
The local loss functions of FL can be nonsmooth. In particular, it is a summation of a smooth function and nonsmooth regularizer, where the regularizer is used to promote certain structure of the optimal parameters such as sparisity, low rankness, total variation, and additional constraints on the parameters. This has motivated the recent study of the federated setting of composite optimization (Yuan et al., 2021). The mathematical formulation of FCO is to optimize
1 Σ (fi(w) + h(w)), N 1
min WERd
f(w)
(1)
where fi(w) f. (.) or its empirical version f((w) = (Dy EEED: fiW,, Ei) is a smooth function with local dataset D', and h Rd -> R is nonsmooth but convex regularizer. Besides, we assume that the proximal operator of h, prox,, (w) == arg min h(u) + 2 closed-form expressions and is easy to compute. The difference to the centralized setting is that D is local data of client and the data distribution of each client may not be the same. Optimizing FL with unconstrained smooth objectives, i.c., problem ( with h 0, has been extensively studied in the literature, e.g., FedAvg MMcMahan et al. 2016), FedProx (Li al. 2020). SCAFFOLD (Karimireddy et al. 2020b) and MIME ( (Karimireddy et al. 2020a), to name a few. When h a O. FedDual (Yuan itt al. 2021), FedDR (Tran Dinh et al. 2021 and FedADMM (Wang et al. 2022) are developed. One of the challenges of these algorithms is the heterogeneity of the local dataset Di, where the distribution of D' is none-identical. The model parameter w learned by minimizing f(w) may perform poorly for each client. If each client learns its parameter by its own data, the local model parameters may not generalize well due to the insufficient data. For the case = O, in order to learn the global parameter and the local parameters jointly, the concept of the personalized FL has been
1 ||u w||2 has

---

Under review as a conference paper at ICLR 2023
studied, e.g., (Smith et al. 2017 7 Hanzely and Richtárik, 2020: Hanzely et al. 2020 Fallah et al. 2020b] |Massor et al. 2020: Chen and Chao [021] T Dinh et al. 2020). To our best knowledge, there is paper which directly investigating the personalization techniques to FCO, although the above personalized methods may be generalized.
Our Contributions. In this paper, we consider constructing the personalized model for the FCO ① while existing methods mentioned above all conduct personalizations to FL with unconstrained smooth objectives, i.e., h O. Although their approaches may be generalized to (T) by replacing gradients with subgradients, the computational results could be worse due to the slow convergence of subgradient methods. The main contributions are summarized as follows.
We present personalized model by utilizing forward-backward envelope (FBE) for FCO (.) called PFedFBE. As a generalized of the Moreau envelope of the Moreau envelope under the Bregman distance (Liu and Pong 2017), FBE is smooth and has explicit forms of gradients, which is a crucial benefit compared to the Moreau envelope. Analogous to the personalized method by the Moreau envelope (T Dinh et al. 2020), proposed method is able to obtain both global parameters for generalization and local parameters for personalization. To our best knowledge, this is the first work to investigate personalizations FCO.
Based on FBE, the local loss functions and global loss function are smooth and hence FedAvg can be used to solve the resulting model. By applying FedAvg, the optimization process of our proposed personalized model can be regarded several local variable-metrie proximal gradient updates followed by a global aggregated parameter. The variable-metric proximal gradient steps able to protect the local information, and the aggregation steps guarantee the total loss is minimized at the aggregated parameter. A proper choice of parameter of FBE allows local parameter move towards their own models and not to go far away from the global parameter. An algorithm, called PFedFBE, is proposed. We show its convergence for the nonconvex f; under mild assumptions. The complexity result matches the standard results of FedAvg for unconstrained smooth FL.
Based on the properties of FBE, the convergence rate of PFedFBE match with the standard analysis of applying FedAvg under standard assumptions over f. and the stochasticity. Numerical experiments on various applications are performed to demonstrate the effectiveness of our proposed personalized model.
Notations. For vector E Rd or matrix H E Raxd we use ||l||| and ||]]| to denote its & norm and Frobenius norm, respectively. For a smooth function f F + R, V and f represent its gradient and Hessian at æ, respectively. For a nonsmooth and convex function h, we denote by (b())) its subgradients at æ. We use [D] to denote the cardinality of a set D.
2 PERSONALIZED FEDERATED LEARNING WITH FORWARD-BACKWER ENVELOPE (PFEDFBE)
The personalized FedAvg (Per-FedAve) Fallah et al. 2020b) and personalized FL with Moreau envelope (pFedMe) (T Dinh et al. 2020) are proposed to deal with the data heterogeneity for the smooth setting, i.e., h = O. For Me, the local model is constructed based on the Moreau envelope of fú namely,
(w) min fi(0.) 2 116, w|l2.
(2)
0.ERd
Then, the resulting personalized model is a bi-level problem:
1 N N
min f(w)
Σ (ww)
(3)
Solving 3 will give both the global parameter and local personalized parameter (,(w) = prox /// = arg mill, f.(O.) + A |10, - w|l2. A crucial benefit of optimizing with the Moreau envelope F,'s lies on the flexible choices of A. When = oc, we have (((w) = f((w) and (((w) = w. which means no personalization is introduced. If X = 0, (((w) is a constant function taking value / (w)(w with (w)) = arg ming ft(O.). In this case, there is only personalization
2

---

Under review as a conference paper at ICLR 2023
and no federation. Hence, they claim that proper À (0, oo) will introduce both federation and personalization.
Since there is no explicit solution of the inner problems, it is proposed to multiple gradient steps to get an estimation of gradient V (w)) X(w 5ro (w)). (:))()). For the convergence, they need this estimation satisfying certain accuracy. Once the gradient of (w:) is available, the existing federated optimization algorithms can be adopted obtain global parameter w and locally personalized parameters 0, (w)).
We note that the Moreau envelope for nonsmooth function also exists (Rockafellar and Wets 2009) and PFedMe can be applied to our setting ( However, obtaining the Moreau envelope needs to solve nonsmooth problem, which may be costly due to the absence of explicit expressions. Note that the inner problem (3) should be solved to certain accuracy guarantee the convergence (T Dinh ct al. 2020). The bi-level model (3) will be time-consuming to solve and may not be ideal in this setting.
2.1 PROBLEM FORMULATION
Since the Moreau envelope does not obey explicit expressions, we aim to find efficient envelopes not only enjoying simpler formulation, but also sharing similar properties of both federations and personalizations. For composite optimization, famous generalization of Moreau envelope is called FBE (Stella et al. 2017 Liu and Pong 2017). Specifically, the FBE of fa + h is defined as
X
F((w)= = min
f((w) + (Vf((), 0, w) + h(0)) + 100 - wll
(4)
0,ER
When the proximal operator of has a closed-form solution, the above envelope can equivalently written as (Stella et al. 2017)
1 [w)(())] + H(w Vi(w)).
1
F((w) (ww
(5)
2
X
where (w) := minøeRs h(0)+ w|12 hpprox (w)) (w))+ (w) w Assuming
the gradient of fs is Lipschitz continuous with modulus L, i.c., [V) - (w) s LIle
well, V0, w, i, the function (w( is continuously differentiable for any À >> L, with gradients
VF((w) = A(I A V - prox groxgalee (w (w))).
(6)
Compared with the Moreau envelope, the gradient of FBE is of closed form and can be calculated with much less computational costs. Furthermore, when L, the set of global minimizers of F,
equals to that of f: + h.
With the definition of FBE our personalized model for FCO is
N
min weRd
F(w) =
(())).
Similar to PFedMe, one can obtain both global parameter w and local personalized parameter
(x(w) = prox in n vf((w))
(8)
by solving When 0c, F((w) (w) h(w). (,(w) w. That is to say, problem
7 reduces to the original problem (1) and there is no personalization. If X = 0, then (w) = arg ming, Vf((w) (0, - w) + ((.)), which is not constant function if f.((()) (w) depends on w. In the extreme case of linear f., (.(w) will be a constant function taking value arg ming, fi(O,) + h(O)). Then, (w(w) will be the best personalization parameter and no federation introduced. As = oo results in only federation, we claim À (0, oo) will allow both federations and personalizations. Other than the linear case, if ft is a quadratic function with Hessian matrix being \ (Ao > 0), then setting À= Ao will result in the perfect personalization and no federation. In this case, a À (Ao oo) will guarantee both federations and personalizations. We also note that > 0 is needed for the smoothness. Otherwise, problem is not strongly convex and F; will not be smooth.
3

---

Under review as a conference paper at ICLR 2023
Besides, compared with original model [ i..., À oc, the objective function of our model (7) is smooth and hence easier to optimize. Basically, our new model takes the solution of (7 as an initial point and slightly update it with respect to their own data by performing proximal gradient step. The benefits compared with the original Moreau envelope lie on the explicit expressions of 0c (w) and V (ww),, given in (8) and (6), respectively.
To summarize, our proposed model
has the following advantages:
The flexible choice of À allows the user-defined trade-off between FL and personalization.
Fi is smooth while shares the same optimizers with the nonsmooth function f: + h.
Although the Moreau envelope of fa + h is smooth, the calculations of gradients are expensive compared with FBE Fi. Both the gradients (w)) and local personalized parameters (w))
has explicit expressions whenever prox, has simple and closed-form solution.
2.2 PFEDFBE: ALGORITHM
In this subsection, we conduct an algorithm, called pFedFBE, to solve our proposed model (7). Since Fi(w) smooth and its gradient is with explicit expression, solving (7) falls into the classic FL setting. One may utilize the existing methods (McMahan et al. 2016 al. 2020 Karimireddy
itt al. 2020b a).
We now describe how use FedAvg solve our proposed model 7 At k-th step, the server randomly select a subset of clients, denoted by Sg. Each selected client is initialized with wo and optimized by R local updates. By collecting all local parameters {wt, hes the server updates its model by Wk+1 = [3.] Eies, Wh, Let us introduce the details of local updates. Since the full batch gradient costly, we take minibatch Dí D' and calculate the unbiased minibatch gradient
Vf((w),)) Vilkk,, Dk,))=
Σ
Villwh E.).
ID
ELEDİ,
From the expression of (w), need to compute the Hessian of as well. By using another minibatch Di C D', the unbiased estimated Hessian
v (l = V V (w Dj) = [Diae
Σ Vill(h En)-
E.EDE
Plugging the estimations into 6 we obtain the estimated gradient
(F(())))) x g((w)))) X(I 2 fe(wh,e (wrk, prox proxya(uhe ( Di,)))
Note that (w is biased due the nonlinearity of prox 1 h. After obtaining the estimated gradient of F,, we do R-step stochastic gradient descent with fixed step size rj > 0, namely,
who = Wk, wi,r-1 wh. (wg. i = 0, ....., R The detailed algorithm is presented Algorithm T Note that the computations of Hessian may be costly. The approximations to the Hessian are developed in (Finn et al., 2017 Nichol et al. 2018 Fallah et al. 2020a). To make the computations afordable, we use the following approximations in numerical experiments:
f'f(w)[u] (Vf(w + tu) f(w))/t
where / is a small positive number. Hence, two mini-hatch gradient evaluations of fú are needed for estimating V.. Similar to Fallah al. 2020b Section 5), the proximal gradient (wf.r
prox 44 (wi, VVllk,e D),))) can also serve as an efficient estimate of V F when À > L.
3 CONVERGENCE
In this section, we present the convergence results of the proposed PFedFBE. i.c., Algorithm Let start with the following necessary assumptions.
4

---

Under review as a conference paper at ICLR 2023
Algorithm 1: pFedFBE for solving
input: Initial point wn. personalization parameter and learning rate r).
for k ..... K - do
Sample subset Ss of clients for client i E Sş. in parallel do Initialize local model w1.0 wkk
for t = 0, ,,,.,,,..... R do
,
Sample two minibatches D and Di,e from D
Calculate the personalized parameter 0g (w = prox (n VVi(wkkee (),))
Compute local stochastic gradient (;( by following (9)
Perform local update w W Wh,t (1g
Aggregate local parameters and set wk+1
[S Eies, w
Assumption Let fi = .,,, N and h be the local functions in FCO (
(A1) Functions fú, = 1,2,..., N are smooth, h is proper, closed, convex with cheap proximity operator, and and functions h, i ..2 are coercive (i.e., lim inf |-100 ||=||
fi(w))h(a) 0).
(A2) The functions fi, i = 2...... are twice continuously differentiable and L-smooth, and the gradients v (ww) and subgrdients δh(w) @h(w) are bounded by positive constant B in compact ball C containing bkk.e generated by Algorithm 7 namely, for all
[V((w) V fi('ll
I L|| u|1, Vw,uE E...
[w))
||
_ B, Vw EC,
[hh((w) - B, Vie EC, Ōhg(w) E @h,(w))
(A3) For each i E (I....,N) N). the Hessian of the function fo is p-Lipschitz contimuous, i.e.,
[()) v S pllw ull. Vw, u E R
(A4) For any E Rdd, the stochastic gradient V f(w, Es) and Hessian V2 feW. E.), computed with respect to single data point & E DD have bounded variance, i.e., for all and w,
Eg:
v -
Egg
v2 fiw -V"
S o
(A5) For any E R2, the gradient and Hessian of local functions fi(w) and the global function f(w) = EN fi(w) satisfy the following conditions
[V]((w) (w)) -6. || [(w) V [ww)]] < 7 Vi,w.
The smoothness of f; and cheap proximity operator property of h are standard assumptions in FCO (Yuan et al., (202T). The assumptions (A2) and (A3) hold for sufficiently smooth f. which are satisfied by many problems arising from machine learning, such as the federated Lasso problem and the federated matrix completion problem in Section 4 These two assumptions are used for the Lipschitz continuous property of F, The bounded variance condition (A4) and bounded diversity condition (A5) are crucial to control the bias introduced by the randomness and the heterogeneity of the local clients. Conditions on fi in Assumption 1 are also made in (Fallah al. 2020b)), and the conditions on is standard in decentralized composite optimization, see (Zeng and Yin 2018). Compared with the analysis of PFedMe (T Dinh al. 2020), do not need additional assumption on the exactness of solving the Moreau envelope since the closed-form solutions is avaliable for the FBE.
Based Assumption
FBE F; has the following desired properties.

---

Under review as a conference paper at ICLR 2023
Proposition 1 (Liu and Pong 2017 Theorem 3.1) If Assumption (A1) holds, then F, is smooth and hovee-bounded for all X > L. Here, we say a functioo ip is level-bounded if {w E R :((w) S >} is bounded for all y E R.
The level boundedness and the smoothness ensure the existence of the minimizer of F. The next lemma establishes the gradient Lipschitz continuous property of F; and F.
Lemma Suppose that Assumptions (A1)-(A2) hold. If x > L, the gradient F.F is Lipschitz continuous with modulus Lp := 2pB 2pB-(A+L](A++)) over the set C.
X
The assumption (A5) gives the bounded divergence between fi and f. We show that the divergence of the local gradient of FBE is also bounded.
Lemma Suppose that the assumptions (A2) and (A5) hold. Then, for L, we have
N
12B 2
[F((W) - VF(w)] S TF == 2472 +
N
X² 7H
With the variance assumptions (A4) of fú. we show the estimations on F; in the following lemma.
Lemma Let Dj, D2 C DD be the sample set and independent to each other. Suppose that (A4)
holds. Then for any X L, it holds
|Di|
E [w, D1, - (F((w)] 5
OG.
[D] -
12
12B
1
E [lla: D1, D2) V S o
[ 0
D21 oF
|DiI a
The above lemma tells us the error the stochastic gradient of F; can be controlled by the variances of the stochastic gradient and Hessian of fi. Note that the estimated gradient of F; is biased unless using the full batch D.
Lemma Let {wk,t} } be the iterates generated by Algorithm
1
Suppose that Assumption
holds.
Assume that X > L and 17 <
IoL we have
E
N
==
w Wk.t
< Anl (ar + TF),
(10)
E
N
1
Wk,t - Wkee
< (8 +00
(11)
where Wk,t =
1i=1 w
The above lemma presents the consensus error induced by the local stochastic gradient updates, which is proportional the local step size 17. With the above preparations, show the following convergence of Algorithm T
Theorem Consider the objective function F, defined 4 for the case that X> L. Suppose that Assumption is satisfied, and recall the definitions of LF, "I and or, from Lemmas D 2 and 3
respectively. Consider running Algorithm for rounds with local updates in each round and with 17 S TO Then, the following first-order stationary condition holds
4 (( -F 1600n)" 407)
Σ
E
|VF
(w++1,)))1
RK
yRK
K=0
0
N
+ 8LFN
S(N 1) 7 7 + +00%) 16ro
where W2+11
Eies, wh41. with W2+1.0
wy and Wx+1,R = Wk+b and
maxe,e (1
(D] 1|11 /IDi.el [211-T

---

Under review as a conference paper at ICLR 2023
Remark. Theorem presents the results of using fixed step size. One easily extend to the setting of diminishing step size. Due to the bias of the estimated gradient of F,. the squared norm of F at 2g will converge ball of center and radius 16rog. When full-batch gradients
used, this radius diminishes. By taking 7) = 1/v RK. the convergence speed of the squared norm of expected gradient is O | which is similar to (Deng et al.
2020: Reddi et al. 2021). Since F; is
smooth, the advanced algorithms, such as FedProx (Li et al.
2020) and SCAFFOLD (Karimireddy
et al. 2020b) can also be adopted for better complexity results.
4 NUMERICAL EXPERIMENTS
4.1 FEDERATED LASSO
Federated Lasso was considered (Yuan et al., 2021), which is to recover the sparse ground-truth signal from observations. The mathematical formulation is
Σ Σ (o)))) 130133 A|[w||1,,
min WERe, DER N
where N is the number of clients and client j has n2 observation pairs {(x})) ( )2 We set 0.1 in our numerical experiments.
Synthetic Dataset Descriptions. We consider both i.i.d. setting and non-i.i.d. setting.
(I) We generate the ground truth Wheat E TR. 1024 with d1 -99 ones and dg = 32 zeros, namely,
Wheal [1 07,]",
and ground truth breal 0. The observations (I, 3) generated follows to simulate the heterogeneity among clients. Let [x)] " denotes the i-th observation of the j-th client. For
each client j, we first generate and fix the mean 14y ~ N (0, Taxa). Then, we sample n, pairs of observations following
3 = M1 + 6600
(4)
where 589) N N.WNOO. (0,, Taxa) are i.i.d., for i 1, I,...,
+ E where e( (O i.i.d., for i I,... ny. We generate y = 30 training clients where each client possesses 128 pairs of samples. There are 3840 training samples total.
(6) w weal 2 (
(II) The ground truth w, R1021 of each client are constructed follows:
Wreal [1 0, 0, 0.5 x 1,, o,... 0.5 x Liag 0, O,....OJJ, OoT,
where i1, id, are uniformly drawn from the {d1 + 1, + 2..... 1024] for each client. We set di = 8 and do Using the same data generalization process as in (I), 30 training clients where each client possesses 128 pairs of samples are constructed.
The numerical results for settings (I) and (II) are presented in Figures recall, density, and F1 indexes calculated by measuring the difference between the ground truth Wreal and the obtained parameters by the algorithms (where any element with absolute value less than 0.01 is regraded
and The precision,
0). We compare with the baseline algorithms, FedAvg (McMahan al. 2016), Fedmirror (Yuan et al.) 2021). FedDual (Yuan et al.) (021). pFedMe (T Dinh et al.) (020). and pFedditto (Li et al. (021). For all algorithms, we set the maximum number of rounds 200. each round, we sample 10 clients and run 20 local iterations with batch size 50. For all algorithms, we tune to get the best clients' learning rate and keep the remaining parameters as their default values. For both settings (I) and (II), we set the learning rate 0.0005 and À 2000 for pFedFBE. From I [ 2 we see that our proposed pFedFBE and Fedmirror give the best performances among all algorithms for setting (I). The poor performance of FedDual compared with Fedmirror may be from the multiple local iterations while the number of the local iteration is set to in (Yuan et al. 2021). For the non-i.i.d. setting (II), Figures 3 and show the results with respect to the personalized
Figure
7

---

Under review as a conference paper at ICLR 2023
parameters. For those algorithms without personalization, directly set the personalized parameter as the global parameters. From the test precision and recall, our proposed pFedFBE is able to find all nonzero elements of Weal and do not introduce extra nonzero elements. Although the personalized algorithm pFedditto can recognize all nonzero elements, the zero entries are mistaken as nonzero as well. pFedFBB gives the best F1 score, the test aceuracy, and the train loss.
LASSO
1.00
0.95
Mozzion
Tost Recall
0.85
0.6
0.0
Nedwg pPedf se
FedAug
RedAug
0.75
0.4
p"earat
0.4
fedmiror
Fedmirrr
Fedmirror
RedDua
Dediual
0.65
0.2
pfodike
0.2
sheddito
p"edditto
pr edditto
0.0
100 rounds
Figure 1: Results for federated Lasso with setting (I).
1.0
0.9
Teat Cansit
0.4
AcCuracy
0.8
0.3
TedAvg
FedAng
FedAug
0.5
6.2
fedmirar
Pedimimo
TediDual
TedDua
0.1
RedDual
@FecMee
pFedile
PeddMe
pFecdittt
0.4
pFadditto
Fedditto
6.0
203
150
100
150
200
Global
Global rounds
Global rouncs
Figure 2: Results (cont.) for federated Lasso with setting (I).
LASSO
1.00
10
0.95
0.3
0.8
0.50
Proztion
Thtt Recall
0.85
0.5
0.6
0.30
Nddwg sPedf se
RedArg
0.4
RedAug
0.75
fedmirrr
Fedmirror
Fedmirro
FedDua
RedDuol
0.70
pFedlke
sreddito
0.0
p"edditto
gf edditto
100
15C
Figure 3: Results for federated Lasso with setting (II).
LASSO
LASSO
LASSO
0.8
Test Density
Text Accuracy
0.10
#fwofRt
ptedFar
0.06
FedAug
pFodFBE
Redmirror
0.5
Fedmimor
Fedminar
FedDual
RedDual
MPociMe
0.5
pFedMo
0.02
PFodMa
of Fecditto
preddito
predditu
0.4
203
150
200
100
150
200
Glebal reuurds
munds
Global rounds
Figure 4: Results (cont.) for federated Lasso with setting (II).
8

---

Under review as a conference paper at ICLR 2023
4.2 FEDERATED MATRIX COMPLETION
Federated matrix completion Yuan et al. 2021 can be mathematically formulated as
min WER bER
1 N ==1
Σ [x)] w) +
v:)2 + W|Iei
where N is the number of clients, client has nj observation pairs {(X))) (3) :9; )) IIW Ilne is
the nuclear norm of W, and À > 0 is parameter to control the rank of W. We set À 0.1 in our numerical experiments.
We only present the numerical results for a non-i.i.d. setting to exhibit the importance of personaliza- tion. The setting is as follows. We set the number of clients to 30 and generate a vector wy E R of the form
wy [1] 04..0...,00..
0, 0.25 x lo 0, O,.....OT,
where dg uniformly drawn from (5, .,..,....3 32} for each client, After getting Wj. we set the diagonal matrix W diag(w; with diagonal elements w, as the local ground truth. For each client we first generate and fix the mean p4j N (0, laxa). Then we sample n; pairs observations following
5 - 560) where of0) N (0g, Taxa) are i..dd., for i 1,....
v) 0 (w,, (W),x)') +ej (9) generated for each client.
ny. tej where o ~ (0, 1) are i.i.d., for inii= 1 1....,ng.. 128 pairs of samples
The numerical results are presented in Figure Since FedDual is not comparable to Fedmirror in the case of multiple local iterations, we omit it and add comparisons with pFedprox (Li et al., 2020). Analogous to the Federated Lasso, the total number of global rounds is set to 200. In each round, we randomly select 10 clients and perform 20 local iterations with batch size 50. We only tune to get the best step sizes for each algorithm. The learning rate and the parameter À used for pFedFBE are 0.0005 and 2000, respectively. From Figure 5 the personalized parameters PFedFBE are able to recover the ground truth rank 5, while all other algorithms fail. Moreover, pFedFBE converges fastest to better training loss, training MSE, and recovery error (which is defined as the Euclidean distance between the local ground truth and the obtained personalized parameters).
MATRIX
MATRIX
MATRIX
MATRIX
Tach MC
15
modaa (FeeTE
sodmirror
Tedrensr
stecile
sfecile
10
pheddtt
Pedppro
50
100
150
200
0.5
Global Tourcss
Global Glubal rouncs.
Gobbal rounds
Siobal munds
Figure 5: Results for federated matrix completion.
4.3 NEURAL NETWORK WITH NONSMOOTH REGULARIZATION
Consider two-layer deep neural network with hidden layer of size 100, the ReLU activation, and softmax layer at the end. The numerical results are performed on the Mnist dataset, which consists of 7000 handwritten digit images from 10 classes. We distribute the complete dataset N 20 clients. To model heterogeneous setting in terms of local data sizes and classes, each client is allocated a different local data size in the range of 11165, 3834) and only has of the 10 labels. A similar setting is used in (T Dinh et al. 2020). The loss function is sum of the cross-entropy loss and the nonsmooth Eg norm function on the weights. Therefore, the resulting problem takes the composite form
For the numerical tests, we set the total number of global rounds to 100. In each round, we randomly select 10 clients and perform 10 local iterations with batch size 20. For all algorithms, the best clients' learning rate and keep the remaining parameters as their default values. We use the learning rate 7 0.005 and À 200 for PFedFBE. The results are presented in Figure 6 where the
tune get

---

Under review as a conference paper at ICLR 2023
global accuracies are based on the global parameters, and personalized accuracies computed from the local parameters. We see the algorithms taking the composite structures, pFedFBE, Fedmirror, and FedDual, converge faster than the other algorithms in terms of the global accuracies. Moreover, pFedFBE outperforms Fedmirror and FedDual. For the personalized accuracies, our pFedFBE performs the best although the personalized algorithms could achieve better accuracies.
MNIST
NNIST
0.10
0.85
0.60
Peclag
phear0: Fodmire
Fodiig
Peckog
0.75
Reelg
PecDual
PecCial
pFeches
piedhes
Fidila
(eodd t2
prodd tb
proddi
23
pFedprox
(Podo
0.3
piedp
350
40
20
100
Figure Results for non-iid Mnist dataset
CONCLUSION
In this paper, we propose a novel personalized method for FCO. The idea is to use the forward- backward envelope arising from the composite optimization. We then utilize the FedAvg algorithm solve the resulted Federated learning problem with smooth objective functions. Convergence results of the proposed algorithm are shown under standrad assumptions. Numerical experiments on federated lasso, federated matrix completion, and nonsmooth deep neural network outperforms the existing methods.
REFERENCES
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends@ in Machine learning, 3(1):1-122, 2011.
Hong- You Chen and Wei-Lun Chao. On bridging generic and personalized federated learning. arXiv preprint S.t.::2007.00778.. 2021.
Alberto Colorni, Marco Dorigo, Vittorio Maniezzo, et al. Distributed optimization by ant colonies. In Proceedings of the first European conference on artificial life, volume 142, pages 134-142, Paris, France, 1991.
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Adaptive personalized federated learning, arXiv preprint urXiv:2003.13461 2020.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. On the convergence theory of gradient-based model-agnostic meta-learning algorithms. In International Conference on Artificial Intelligence and Statistics, pages 1082- 1092. PMLR, 2020a.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning: A meta- learning approach. arXiv preprint arXiv:2002.0799 079448 2020b.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International conference on machine learning, pages 1126-1135... PML., 2017.
Filip Hanzely and Peter Richtárik. Federated learning of mixture of global and local models. arXiv preprint N..iv:2002.055//2/ 2020.
Filip Hanzely, Slavomír Hanzely, Samuel Horváth, and Peter Richtárik. Lower bounds and optimal algorithms for personalized federated learning. Advances in Neural Information Processing Systems, 33:2304-2315 2020.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends@ in Machine Learning. 14(1-2):1-210, 2021.
10

---

Under review as a conference paper at ICLR 2023
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning, arXiv preprint arXi::2008.0300 2020a.
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, pages 5132-5143. PMLR, 2020b.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429-450, 2020.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In International Conference Machine Learning, pages 6357-6368. PMLR, 2021.
Tianxiang Liu and Ting Kei Pong- Further properties of the applications to difference-of-convex programming. Computational Optimization and Applications, 67(3)489-520, 2017.
envelope with
Yishay Mansour, Mehryar Mohri, Jac Ro, and Ananda Theertha Suresh. Three approaches for personalization with applications federated learning. arXiv preprint arXiv:2002.10619, 2020.
H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication-e cient learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), hp://arxiv. org/abs/1602.05629, 2016.
Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-learning algorithms. arXiv preprint arXiv: 180300990, 2018.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Brendan McMahan. Adaptive federated optimization. International Conference on Learning Representations, 2021.
Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science Business Media, 2009,
Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet Talwalkar. Federated multi-task learning, Advances in neural information processing systems, 30, 2017.
Lorenzo Stella, Andreas Themelis, and Panagiotis Patrinos. forward-backward quasi-newton methods for nonsmooth optimization problems. Computational Optimization and Applications, 67 (3):443-487, 2017.
Canh T Dinh, Nguyen Tran, and Josh Nguyen. Personalized federated learning with moreau envelopes. Advances in Neural Information Processing Systems, 33:2 19:1339--24055 2020.
Quoc Tran Dinh, Nhan H Pham, Dzung Phan, and Lam Nguyen. Feddr-randomized douglas- rachford splitting algorithms for nonconvex federated composite optimization. Advances Neural Information Processing Systems, 34:30326-3033 2021.
Han Wang, Siddartha Marella, and James Anderson. Fedadmm: A federated primal-dual algorithm allowing partial participation. arXiv preprint 2rXiv:2203.15104 2022.
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, Brendan McMahan, Maruan AI-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly. Deepesh Data, et al. A field guide to federated optimization. arXiv preprint arXiv:2107.06911 2021.
Tao Yang, Xinlei Yi, Junfeng Wu, Ye Yuan, Di Wu, Ziyang Meng, Yiguang Hong, Hong Wang, Zongli Lin, and Karl H Johansson. survey of distributed optimization. Annual Reviews in Control, 47:278-305. 2019.
11

---

Under review as a conference paper at ICLR 2023
Honglin Yuan, Manzil Zaheer, and Sashank Reddi. Federated composite optimization. In International Conference on Machine Learning, pages 1 PMLR, 2021.
Jinshan Zeng and Wotao Yin. On nonconvex decentralized gradient descent. IEEE Transactions signal processing, 66(1 (111112224488888 2848, 2018.
A
APPENDIX
A.I PROOF OF LEMMA
Note that VB(w) = X(I - - [iw))
pr VV[(w)))
It holds for wi, W2 E C that
[V VF((w2)
-> (1 N v2 (' - prox (n(1 V.((w))))
1 V f((w2))(w prox A (w2
-(I À
V ffff(w)))))
=> > - - V f((w))) - (1 1 V2 (((2))) (w) proxoox An (w) vf((w))))
x
1
+(I A 22 f((22))
W1 - proxxa proox Vfi(wr)) u2 + prox in (w2 Vf((wz))
V (((w) - V2 ((w2))l11 prox
v Vi((w)))
+ A||k
vz f()2) [|11 will + 1|wa
V f(((w) - -w0 + V Vf((w2]]]
<plwwi 1a || [m prox 1 Vf((w))) )) + (1 4) (2+ ++ x) |10| 1 w2ll
Vf((wi))
+ 1 max. BEON (w: (
1011 +
(A L)2
||w| w2
X
2pB +A+ (A+
|| - wzll.
A
where the first inequality is due triangle inequality, the second inequality is from (A3) and the nonexpansive property of prox the third inequality is from w - prox (n(u) and the last inequality is due to (A2).
proxx*(u) E @Ol(prox44) (u)).
A.2 PROOF OF LEMMA 2
1 (w))) that follows from (F()w) X(I fiw)( - prox
> (1 1 ] (()((1)) 1.+AEE(u prox 1 Vf(w))) + +Egrs
1
- VF(w))
where E, X (V2 V fi))) and r; = prox - prox (
Due to (A5), holds
1 | S x TH-
(12)
Using the nonexpansive property of prox we have
||: < x
[f((w) - f(w)11
x2 2210. T0.
(13)
12

---

Under review as a conference paper at ICLR 2023
Combining 12 and (3)
it holds
1
(w)
VF(3)]?
N
231²
(1+
Ie
Σ
|r 2
4B
Σ
N
|ill +
1 N
Σ
E& 11|111:11.
X
1=1
i=1
1
1 x2
53
(A+ L)²
X2
41²
X2 72
+ x2
max
Ei|
2
4ha + 4B²
<3
A2 711 472
12B²
244 + X2 7H.
where the first inequality from - f(w]] S 11+ and ||w- proxproxxp in (V - 28
the second inequality is due to 12 and 13). and the last inequality is based on || S 2h and X
L.
A.3 PROOF OF LEMMA 3
From the definition of g: (w) in (9) with the sample set Dj for the gradient and the sample set D2 for the Hessian, we have
ge (w) - VF = dei(w f - v((ww))) + X(1 1 v2 f((w))e2 + Ae1e2
1
where el = [() vii(w, D2)) and e2 = prox (w VV/(w)) - prox (w
1 fV D.)). Let us estimate ej and e2 first. Due to (A4), we have
Eie,1 = 0, |
(14)
where [D2] is the number of samples. For eg, it follows from the nonexpansive property of prox that
!
E|ee]l|| < E
IVf((w) - fw, DiJl
[D DD DG.
(15)
Av
Dii
where the second inequality is from (A4) and the variance of ssmmllin without replacement, Similarly, the second-order moment can be bounded by
Ellee2 1
E
X
V(((w) - Vf(W,,D)) <
x
GG.
(16)
Combining [4
[5] and (6)..
we have
E [g: VF(()) s AI[(1 1 B(e))
2
D
<
0G.
VDD
[
Furthermore, it holds
E [I (w) [
$31²
E
||al [eal|"1((u - prox (n( prox)a(u
V
Vi(w)))) + || - v2
X
<3X²
[D2|X² "
1
4B²
X2
+
|+
x
L
12 a +
of
D 1
1
00
12
12B²
3
D O
2 +
[Dz X2
H
2 +
D D2 X2 G.
2
where the first equality is from the Cauchy-Schward inequality, the second inequality is from 14 and (16). We complete the proof.
|| prox tn (w [V(())) < 28
13

---

Under review as a conference paper at ICLR 2023
A.4 PROOF OF LEMMA 4
Note that the local update of Algorithm
1 is
w Wk,44 Whet (1)(
(17)
where se(wf,t) is the estimated gradient of F; at whe Define C. = We have So 0 since wh, wy for any i. It follows from the local update scheme
wa.
117) that
C.+1
E
w wk, ww,r+1
E
w
199i (wkk,)
Σ
1995
(wh).)
N
j=1
(18)
NV
C. + 17
E
9i
(w)tt)
1
Σ
(wk.e)
N
=:b,
For bi, it holds
N
N VI,
n N
b
7
(
Σ N j=1
Vj (wh.e)
+
Σ
||| V (wf.)) - (wk,+))
N
N
+
17
E
1
F3
(w/k.) 9o
(w2h1))
N
j=1
7
E
F. (wk.))
Σ
VF wk,1)
+ 2no
(19)
where the first inequality is due to the triangle inequality and the last inequality from Lemma Combining (18) and (19) and defining a; ;= VFF
F. (wk,e), we have
N
N
C+11 SC, + 2NOF +
E
VF, (w))))
VF,
N
N
1=1
j=1
NN
1 N
=C + 2n0F +
"
Σ> E
F (Wk.t)
Σ
Vi (Wk,e)
(20)
N
N
i=1
1=1
17
1
+
a4
aj
N
N
j=1
follows from Lemma that ||a:|||
LF
w
wk.t
Consequently,
Ellaa|ll s LpC..
Plugging the above inequality into 20
leads to
N E
C++1 $ (1 + 2T C. + 2nor +
VR, (wX..)
V
(WE.)
N
N
(21)
t=1
j=1
S (1 + 2LLF) Co + 2n (OF 7F)
14

---

Under review as a conference paper at ICLR 2023
where the last inequality is due to Lemma
2 From the recursion 21 we have
C++1
Σ (1 2gLF)² 21/ (or + TF)
(22)
s 2n(t + 1) (1 + 21L (or + 7F)
2n(t + 1)(1 + 5R' ( YF) 4n(t + 1) YF),
which the third inequality is from 7 I0 and the last inequality is due to (1 + 511 ) e
<
27
We finish the proof of (TO). For the proof of (TT). let us define D, == N
E
w Wk.t
;=1
Since " = Wk: Vi 1,..., N, it holds Do = 0. Following 17
we have
N
D2+1
E
|| - wil++1ll
N
N
N
E
wh.t
799s (wh,))
(w k
795 (m²
N
N
Y=1
j=1
N
N
E
Wkit
W
N
1=1
j=1
(23)
N
1 + 1/v
Σ
E
gi
(wkk)
1 Σ
9
w
N
1 + 1/v N
$1++v)D, + n/²
E
9i
(wkre)
Σ
96
(wbse)
N
N
m:bg
where the first equality is from ||a + b112 < (1+ 0)|aa|2 + (1 + 1/0) for any v > O. For bg. holds that
N E
1
52 22n
VF. (wkke)
Σ
F
k
N
n
j=1
+2E
(gs (wkr)
VF, (wk.))
+
Σ
VFF, (w/k.)
94 (wk.)) ))
j=1
+ 1/v
22n
E
VF: (wke)
Σ v w
N
+4E
|1ss (wir))
- V (1
+
1
(whtt)
(wh.)) 1|2
N
12
1 + 1/v
N
N
<4n²
E
FFF (Wkke)
Σ
VF, (war+)
+
a;
+ 4
N
N
N
1=1
j=1
15

---

Under review as a conference paper at ICLR 2023
1/v
<4n
TF 2
E [[lwk - ww
E
wn,ell
2|
+ 1o
<4n + 1/v) [0 + 4 + 40
(24)
where the first inequality the second inequality are due to the inequality from Lemma the Cauchy-Schwarz inequality and a; VF((w),) - VF (w..e). the fourth inquuality from Lemma I and the last inequality obtained using the definition of D..
inequality. the third
Plugging (24 into 23 yields
Det1 =(++)) + 41 +1+ 1/2) 11? + +LL + 40
(1+ 16 16+++)((+++))))
41 + 1/v))1 +407)
(25)
1=0
< 4t + (1+ 16 + (1 +47))
Taking v = 2nt
1 and 17 5 10 give
1 161 22))p T.7
(1+++160) 1/u\n1 2
2R
1
1 R
1 +
16(1 + 2R)
1 +
S 4,
2R
100R
where the first inequality is due to <5 10 the second inequality is from 1 + 2R S 3R, and the
last inequality is based on the fact (1 ) S E. Plugging the above incquality into (25). we have
D1+1 S 447² (t 1)-1)-4 -4 4. 3R( + 407)) I 48(t + 1) (1 + 40
We complete the proof.
A.5 PROOF OF THEOREM II
Denote by F% the o-field generated by { ww J ) Define the averaged iterate Wh,t = 1/2 Eies, whe
Then,
M441641 =
(wf+1, - (gg = 0k+1,1
"7
Σ
(26)
S VESt
S
iES
From the Lipschitz continuous property of the gradient of F,
we have
F (Wi+1,1+1
LF
<F (W + V (7++1,) (0++1,411 wx+1.e) +
| - 1x+11e
2
(27)
2
=F(WE).)) V (W
1
Σ gs (w1++11)
LF
Σ 9: (wi++1))
55
1/²
2
$ESx
SESt
where the inequality is from the Lipschitz gradient property of F' and the equality is due 26). By taking expectation on (7). we obtain
F (+x+1,441 [ (1++1,) mE
VF (wk
(w++
Σ 9s (w
(wkk11))
S
165x
=:g
(28)
27
LF +
2
Σ
g (w (wFk11)))
2
S
iES.
=102
16

---

Under review as a conference paper at ICLR 2023
The sketch of the proof is estimate the difference between the stochastic gradient 3 Eiss, (wi+1.)) and VF( and derive a decrease of F with respect to [ Once one-step decrease is obtained, the complexity result is obtained by summing over all iterates. Firstly, we use the following split on (w k+1,,) namely,
Σ 96 (w1+1,) SES
X
VF (F(@x+1.).
(29)
S
where
X = 5
Σ
(gi (wk+1,1) - VF; (w)+1,))
iESu
Y Σ
1
(VF: (1f+2,)) VF (wx+1e)
S
iES#
1
Z
(VF, (w++1,))
VF; (wx+1.))
S
iESt
1
Σ
VF (10+1.1) F((
iES,
Next, we bound the moments of N,Y.2 7 and Q.
It follows from the Cauchy-Schwand inequality that
|
S
1
Σ
|99 (wk+1,)) - VF; (1))
S
SESr
By the tower rule, we have
E
=
S oz.
(30)
Note that
| <
Σ
VFF (wk+1,)) VF; (wx+1,))l
S
iESt
L
(31)
|
V
< 1)m + 407),
where the first inequality from the Cauchy-Schwar -chwwrz inequality, the second inequality is due to the Lipschitz gradient of F; given in Lemma I and the last inequality is based on (II and R
Using the variance of sampling without replacement, we have
E [|
W.+1ee 11
<E
|
WR41,
S
SES
(32)
N
(1-
S
||
WetL 12
SN
N
By the gradient Lipschitz property of F, given in Lemma
we obtain
I S
2
E
E
Wk+ 11
SES
L2
||
w.t1.el2. (1
S-1
(33)
SN
N-
48(N S)R(R - 1) 40
S(N 1)
where the second inequality is due 32 and the last inequality is from
17

---

Under review as a conference paper at ICLR 2023
From Lemma
2 and similar derivations
32
we have
N S
E [|
< E
E S
VF(WA+L)))I
7/. (34)
S(N 1)
kESt
addition, using the tower rule, it holds that
[ E E
V
VF( O.
(35)
With the above estimates, we have
S V ((( + Q+ VF (F(
E
V V (QQ + (f( ))) " V (1++11)) x
" E
)| - BBlly =
1 [I] ( - V 1+++ T
x
" E (VV((++11))1
[ + 2
4
(36)
where the second inequality is due to the Cauchy-Schwand inequality and the last equality is from For the second term in (36). we have
FF (1x+1.)
x]
E
(1)+111)
F
E
(w++1,1)
E
X
Fitt1l
(37)
E
|VF
(w++1+1))
E
E
[
]1"
< E
|VF
(,++
+ Aroō.
| |Pi,1-1) |
where r maxk,ti
//D in the last inequality follows from Lemma 3 For the
last term of (36 it holds that
Y + z
EE | ||| + E [|
< 96R( - 1) 12 +00) (1+ N S(N - 1)
(38)
< 1))
40
where the first inequality is from the Cauchy-Schwaee Schwarz inequality, the second inequality due to and 333. Plugging (37) and (38) (36) yields
31
l1
" E
VV (1+11)))
1 + 40²) 4rmpo
(39)
The remaining term in 28 needs to be bounded is q2. follows from the that
inequality
Σ gs (w (wk+1e)
< 2 + 2 Q VF (F
(40)
iESt
< <01IX] + 100
By
30
38
34
and 40p. we have
192R(R - 1 2 + + N - S
< 2Lp2²
oz
S(N 1) 2 + V 11++111)12
N
<
2
4000
1) ( + 40 + 2
S(N - 1) 7 +
(41)
18

---

Under review as a conference paper at ICLR 2023
Plugging 36) and
into 28 gives
E F (*x+1,(+1)
S FF (xx+1,t) - (1/2 2nLp) B VF (wx+ (wx+1.))l?
N
+ 200 (1 + 2nL
1) (7 + 407) + +L S(N 1) 70 00²
+ 4rnoo
<E F (wx+1,,)
E
| (wx+1,))1 + 400m R2 +
4
- S(N 1) 7p o%: + Arno
+ 2Lm
(42)
where the last inequality is due 1) S 10RL t 0, R 1 and k = 0,..., K yields
Note that WE,R wh. Summing over (42) for all
K-18-1
nRK
VF (FT1))11] + 4007/² R (P(??? + 407)
F (wK) )1 SF (wo)
4
RK
N
S
2RKLF
2/ + +0%
+ 4RKKroo
S(N 1)
Therefore.
R-1
Σ
E
VF (w)+
4
(F (wo) (wo) EEF n(KKot)
RK
nRK
t=0
4 (F (wo) F*)
1600ry R² 2
407)
nRK
+ 8L
S(N 1) 77 + +0/ + +16r0a
N
which F* the minimal value of F, This completes the proof.
19


Reviews:
[{"review_id": "d9kAlkR7e5", "reviewer": "Reviewer_4Vq3", "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 proposed a personalization federated learning method (i.e., pFedFBE) by using forward-backward envelope as clients’ loss functions. It provided the convergence analysis  of the proposed method, which shows the same convergence complexity results as FedAvg for FL with unconstrained smooth objectives. Numerical experimental results demonstrate the effectiveness of the proposed pFedFBE method.", "summary_of_the_review": "This paper proposed a personalization federated learning method (i.e., pFedFBE)  by using forward-backward envelope as clients’ loss functions. It provided the convergence analysis  of the proposed method, which shows the same convergence complexity results as FedAvg for FL with unconstrained smooth objectives. Numerical experimental results demonstrate the effectiveness of the proposed pFedFBE method.\n\nSome Comments:\n\n1. Assumption 1-(A3) is stronger than the basic assumptions in the existing FL methods such as FedAvg.\n\n2. It would be great if the authors would detail the tuning parameters in the experiments.\n\n\n------------------------------------------------------------------------------------------------------------------------------------------\n--------------------------------------------------------------------------------------------------------------------------------------------\n\nThe authors still did not solve my main concern: the limited novelty of this paper. So I support to reject this paper.", "strength_and_weaknesses": "Strength:\n\nThis paper proposed a personalization federated learning method (i.e., pFedFBE) by using forward-backward envelope as clients’ loss functions. It provided the convergence analysis of the proposed method, which shows the same convergence complexity results as FedAvg for FL with unconstrained smooth objectives.\n\nWeakness:\n\nThe novelty of this paper is limited. This paper basically follows the existing methods and  theoretical analysis such as in (https://arxiv.org/pdf/2011.08474.pdf).", "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": "V-HpowXYQPX", "reviewer": "Reviewer_bfG5", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "In this paper, the authors propose a novel personalized method for FCO via the forward-backward envelope. Personalized models are firstly updated, then the local models are updated with Second-order optimization. After the local update, the global update is done via FedAVG. Convergence results of the proposed algorithm are shown under similar assumptions in pFedMe. Numerical experiments on the federated lasso, federated matrix completion, and nonsmooth deep neural network were done.", "summary_of_the_review": "Generally speaking, the topic of the paper is of importance and interest. However, the authors can improve the work by addressing the above-mentioned concerns, especially about the computational efficiency and the ablation studies in the second-order info in the optimization.", "strength_and_weaknesses": "Strength:\nthe topic is important for distributed learning and federated learning. This paper proposed an interesting method to obtain explicit forms of gradients. A convergence proof is performed to justify the algorithm's efficacy. The paper is not hard to follow.\nWeaknesses:\nMy major concern is the novelty. It seems that the proposed method uses the framework of pFedMe but estimates the local gradient using an explicit form, plus additional computation on the Hessian matrix. Although the experimental result of FedFBE shows faster convergence over other methods, it is not fully convincing to say that FedFBE has higher efficiency. Estimating the Hessian matrix definitely helps with convergence, but it also leads to the consumption of much more computation. pFedMe doesn't use the explicit form partly because it can save computational power by avoiding that Hessian matrix. Therefore, I am not sure that the problem will be solved without creating another bigger problem. Thus, the novelty in terms of the solution technique is thus limited.\nI wonder about the influence of hessian components of the proposed method on the final results. Some ablation studies can be done to justify the efficacy of FBE.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "O37U9sB20y", "reviewer": "Reviewer_3u8w", "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 proposes federated composite optimization, i.e., the nonconvex minimization of sum_i f_i + h in a federated setting. Here, f_i is smooth, h is not smooth but proximable. Note that the f_i are not assumed to be equal to each other (heterogeneous data).\n\nThe Forward Backward Envelope (FBE) of f_i + h is a function F_i s.t. one gradient step on F_i is roughly equivalent to one Forward Backward step for f_i + h (it involves the Hessian though). Similarly to the Moreau envelope, the FBE is smooth and depends on a parameter lambda. The paper proposes to minimize F = sum F_i. Tuning lambda allows for more federation or more personalization.\n\nTo minimize F, one can use basically any Federated Learning algorithm since the F_i are smooth. \nThe main theorem upper bounds the squared norm of the gradient of F evaluated at the federated iterate, along the algorithm.", "summary_of_the_review": "This paper proposes a meta algorithm to solve composite problems in a federated setting. This meta algorithm relies on minimizing the sum of the FBEs with any FL algorithm, because the FBEs are smooth. Once the approximated problem with FBEs is formed, the paper forgets about the original problem (except in the numerical experiment section).", "strength_and_weaknesses": "Weaknesses\n\n- The gradient of the FBE is actually not a FB step, because it requires the Hessian of the smooth function. So the methods based on the FBE require the Hessian.\n\n-I think that the assumptions A2 and A3 are too strong. They basically say that the first second and third derivatives are bounded. Usually, the smooth term is gradient Lipschitz and we do not assume Lipschitzness of the nonsmooth term. The third derivatives are needed because the Hessian appears in the algo.\n\n- The approach based on the FBE is not justified. Is it a good model to minimize F instead of the true loss f? Why won't we apply a federated version of the Forward Backward algorithm for example? (and then take one additional FB step for personalisation?)\n\n\nStrength\n\n- Numerical exp show the superiority of the approach over concurrent methods in several contexts.\n\n- The F_i is smooth, so the model can be solved by any FL algorithm which gives a lot of flexibility. ", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KaKv29W2NK", "reviewer": "Reviewer_WBRe", "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 author(s) extends the Moreu-envelop based personalized FL to the composite problems. Convergence analysis under certain assumptions are developed. Experiments on synethtic data and MNIST are conducted to evaluate the proposed algorithm.", "summary_of_the_review": "The presentation of the paper should be improved. On the theory side, the contribution of the paper is kind of marginal compared with the exiting Moreu-envelop based personalized FL; on the empirical side, the experiments are mostly on synthetic and tiny datasets. The author(s) should consider improving either from the theory or the empirical aspect.", "strength_and_weaknesses": "Pros:\n- The story line of the paper is clear and related works are well-addressed to my knowledge.\n\nCons:\n- The presentation of this paper should be improved: (1) the author(s) should use \\citep in many places, for example in the first paragraph. (ii) Figure 1,2,3,4,5,6 are not properly cropped. (3) Notations are kind of heavy, it is better to include a subsection for notations.\n- From the perspective of personalized FL, the paper seems to be a direct extension of [1] to composite problems. However, generalizing [1] to the composite problem does not seem to be a challenging task.\n- The author(s) spent much space for the theoretical analysis (page 5 and page 6). However, Theorem 1 does not seem to be a particularly strong results, the algorithm uses second order information and does not coverge faster.\n- Using second order information (the Hessian matrix) is expensive in practice, this issue is only briefly mentioned above Section 3. It is better to discuss more on how to efficiently leverage the second order information, i.e., how to do the Hessian-vector product efficiently and what is the time complexity of the proposed algorithm.\n- Experiments are also not very convincing, the datasets are mostly aftifically generated, the only real dataset is the MNIST dataset. It is more convincing the evaluate the proposed algorithm on more real-world datasets.\n\n\n[1] Canh T Dinh, Nguyen Tran, and Josh Nguyen. Personalized federated learning with moreau envelopes. Advances in Neural Information Processing Systems, 33:21394–21405, 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": {}}]

Author rebuttal:

Decision: Reject