Personalized Federated Learning: A Unified Framework and Universal Optimization Techniques
Authors: Filip Hanzely
Boxin Zhao
mladen kolar
Venue: Accepted by TMLR ()

Abstract: We investigate the optimization aspects of personalized Federated Learning (FL). We propose general optimizers that can be applied to numerous existing personalized FL objectives, specifically a tailored variant of Local SGD and variants of accelerated coordinate descent/accelerated SVRCD. By examining a general personalized objective capable of recovering many existing personalized FL objectives as special cases, we develop a comprehensive optimization theory applicable to a wide range of strongly convex personalized FL models in the literature. We showcase the practicality and/or optimality of our methods in terms of communication and local computation. Remarkably, our general optimization solvers and theory can recover the best-known communication and computation guarantees for addressing specific personalized FL objectives. Consequently, our proposed methods can serve as universal optimizers, rendering the design of task-specific optimizers unnecessary in many instances.

Published in Transactions on Machine Learning Research (May/2023)
Personalized Federated Learning: A Unified Framework and Universal Optimization Techniques
Filip Hanzely*
fhansely@gmail.cmm com
Toyota Technological Institute at Chicago Chicago, 60637, USA
Boxin Zhao"
bozina Cwwchicago...... edu mkolar@chicagoooeee edu
Mladen Kolar
The University of Chicago Booth School of Business Chicago, IL 60637, USA
Reviewed on OpenReview: https:// openreviee. net/ forum? id= LHM311XC
Abstract
We investigate the optimization aspects of personalized Federated Learning (FL). We pro- pose general optimizers that can be applied to numerous existing personalized FL objec- lives, specifically a tailored variant of Local SGD and variants of accelerated coordinate aescent/acceleraat SVRCD. By examining a general personalized objective capable of re- covering many existing personalized FL objectives as special cases, develop compre- hensive optimization theory applicable to wide range of strongly convex personalized FL models in the literature. We showcase the practicality and/or optimality of our methods in terms of communication and local computation. Remarkably, our general optimization solvers and theory can recover the best-known communication and computation guarantees for addressing specific personalized FL objectives. Consequently, our proposed methods can serve as universal optimizers, rendering the design of task-specific optimizers unnecessary in many instances.
1 Introduction
Modern personal electronic devices, such as mobile phones, wearable devices, and home assistants, col- lectively generate and store vast amounts of user data. This data is essential for training and improving state-of-the-art machine learning models for tasks ranging from natural language processing to computer vision. Traditionally, the training process was performed by first collecting all the data into a data con- ter (Dean et al.) 2012), raising serious concerns about user privacy and placing a considerable burden on the storage capabilities of server suppliers. To address these issues, novel paradigm Federated Learning (FL. (MeMahan et al.) 2017 Kairouz et al. 2021) has been proposed. Informally, the main idea of FL is to train model locally on individual's device, rather than revealing their data, while communicating the model updates using private and secure protocols.
While the original goal of FL was to search for a single model to be deployed on each device, this objective has been recently questioned. As the distribution of user data can vary greatly across devices, a single model might not serve all devices simultaneously (Hard et al. 2018). Consequently, data heterogeneity has become the main challenge in the search for efficient federated learning models. Recently, range of personalized FL approaches has been proposed to address data heterogeneity (Kulkarni et al., 2020 wherein different local models are used to fit user-specific data while also capturing the common knowledge distilled from data of other devices.
"equal contribution

---

Published in Transactions on Machine Learning Research (May/2023)
Since the motivation and goals of each of these personalized approaches vary greatly, examining them sep- arately can only provide us with an understanding of a specific model. Fortunately, many personalized FT, models in the literature are trained by minimizing a specially structured optimization program. In this paper, we analyze the general propertios of such an optimization program, which in turn provides us with high-lovel principles for training personalized FL models. We aim to solve the following optimization problem
min 2
F(w,))=
1 Σ Sm(w, = M m=1
Im(w:,Bm) Bm)) Rm))
(1)
where w E Iddo corresponds to the shared parameters, 3 = (31,..., 32) with 3m E Rdm, vm E [M] corresponds to the local parameters, M is the mumber devicos, and fm : Roo - R is the objective that depends on the local data at the m-th client.
By carefully designing the local loss fm (w, Bm), the objective can recover many existing personalized FL approaches as special cases. The local objective fm does not need to correspond the empirical loss of given model on the m-th device's data. See Section 2 for details. Consequently, (L) serves objective that encompassee numerous existing personalized FL approaches as special cases. The primary goal of our work is to explore the problem ① from an optimization perspective. By doing so, we develop a universal convex optimization theory that applics to many personalized FL approaches.
unified
1.1 Contributions
We outline the main contributions of this work.
Single personalized FL objective. We propose a single objective (1) capable of recovering many existing
convex personalized FL approaches by carefully constructing the local loss (m, 8m)). Consequently, training different personalized FL models is equivalent to solving a particular instance of (1).
Recovering best-known complexity and novel guarantees. We develop algorithms for solving I and prove sharp convergence rates for strongly convex objectives. Specializing our rates from the general setting to the individual personalized FL objectives, we recover the best-known optimization guarantees from the literature or advance beyond the state-of-the-art with single exception: objective 111] with À L'. Therefore, our results often render optimization tailored to solve specific personalized FL unnecessary in many cases.
Universal (convex) optimization methods and theory for personalized FL. To develop optimiza- tion theory for solving (1. we impose particular assumptions on the objective: u-strong convexity of F and convexity and (I.", .MM (."")-mmot of fm for all m E [M] (see Assumptions 2 These assumptions are naturally satisfied for the vast majority of personalized FL objectives in the literature, with the exception of personalizod FL approaches that are inherently nonconvex, such as MAML (Finn al. 2017). Under these assumptions, we propose three algorithms for solving the general personalized FL objective ( i) Local Stochastic Gradient Descent for Personalized FL (LSGD-PFL.). ii) Accelerated Block Coordinate Descent for Personalized FL (ACD-PFL), and iii) Accelerated Stochastic Variance Reduced Coordinate Descent for Personalized FL (ASVRCD-PFL). The convergence rates of these methods are summarized in Table [ We emphasize that these optimizers can be used to solve many (conver) personalized FL objectives from the lit- erature by casting a given objective as a special case of 1 oftentimes matching or outperforming algorithms originally designed for the particular scenario.
Minimax optimal rates. We provide lower complexity bounds for solving ( Using the construction of Hendrikx et al. (2021), show that to solve { one requires at least O (VL commu- nication rounds. Note that communication is often the bottleneck when training distributed and person- alized FL models. Furthermore, one needs at least O (VLL) //Lm//lloe=" evaluations of V. and at least o D//llgg evaluations of VgF. Given the n-finite sum structure of fm with (C", C. components, we show that one requires at least O (n + /nC /Hloge= stochastic gradient evaluations with respect to ve-parameeers and at least O (n + VnL ///C///u / loge stochastic gradient evaluations with
2

---

Published in Transactions on Machine Learning Research (May/2023)
Alg.
Communication
# V w max LL
# V/3
max (1--)1,)))
max (L (
LSGD-PFL
d²
M
IM Buc 1. (C
MB L (C2 2
+1
1. [C"(C3+o2
ACD-PFL
VT./P
VIPIP
ASVRCD-PFL
n VnL"
VnL"/n
n VnC*/u
Table 1: Complexity guarantees of the proposed methods when ignoring constant and log factors. #Vw/#VP number of (stochastic) gradient calls with respect to the w/ B-paramcteers. Symbol *, indicates the minimax optimal complexity. Local Stochastic Gradient Descent (LSGD): Local access to B-minibatches of stochastic gradients, each with ož-bounded variance. Each device takes (T - 1) local steps in between the communication rounds. Accelerated Coordinate Descent (ACD): Access to the full local gradient, yielding both the optimal communication complexity and the optimal computational complexity (both in terms of Va and VB). ASVRCD: Assuming that ft is an n-finite sum, the oracle provides access to a single stochastic gradient with respect that sum. The corresponding local computation is either optimal with respect to V. or with respect to V,. Achioving both optimal rates simultancously remains open problem.
respect 3-parameters. We show that ACD-PFL is always optimal in terms of communication and local computation when the full gradients are available, while ASVRCD- PFF PFL can be optimal either in terms of the number of evaluations of the w-stochastic gradient or the ß-stochastic gradient. However, note that ASVRCI-PFL cannot achieve optimal rate for both evaluations of the w-stochastic gradient and the P- stochastic gradient simultaneously, which we leave for future research.
Personalization and communication complexity. Given that a specific FL objective contains pa- ramoter that determines the amount of personalization, we observe that the value of /L always a non-increasing function of this parameter. Since the communication complexity of 1 is equal to /I. up to constant and log factors, we conclude that personalization has a positive effect on the communication complexity of training an FL model.
New personalized FL objectives. The universal personalized FL objective 1 enables us obtain range of novel personalized FL formulations as special cases. While we study various (parametric) extensions of known models, we believe that the objective [I] can lead to casier development of brand new objectives as well. However, we stress that proposing novel personalized FL models is not the main focus of our work; the paper's primary focus is on providing universal optimization guarantecs for (convex) personalized FL.
Despite the aforementioned benefits of our proposed unified framework, we acknowledge that this is neither the only nor the universally best approach for personalized federated learning, However, providing a general framework that can include many existing methods as special cases can help us gain clear understanding and motivate us to propose new personalized methods.
1.2 Assumptions and Notations
Complexity Notations. For two sequences {az} and {ba}, an = Obb,) if there exists C > such that [am//b]] S C for all n large enough; an (bb,) if on (br)) and bn (an)) simultancously. Similarly, On O(b)) if a, Obb, log" b,)) for some k 2 0; a2 = Ō(b.) if a, = Ö(b.) and b, = Ō(a,) simultaneously.
Local Objective. We assume three different ways to access the gradient of the local objective fm- The first, and the simplest case, corresponds to having access to the full gradient of fm with respect to either w or B. for all m E [M] simultancously. The second case corresponds to situation where V.m(w, 3m) is the expectation itself, i.e,
(m, Bm) = EEEDI. Vim(W,
(2)
3

---

Published in Transactions on Machine Learning Research (May/2023)
while having access to stochastic gradients with respect to either or im simultancously for all M, where I' represents the loss function on single data point. The third case corresponds to finite sum fm:
fm Bm) - Σ fm, Bm),
(3)
having access to Wwsmmsuu, Bm) to ( for all [M] and i e [n] selected uniformly at random.
Assumptions. We argue that the objective (1 is capable of recovering virtually any (convex) personalized FL objective. Since the structure of the individual personalized FL objectives varies greatly, it is important to impose reasonable assumptions on the problem (1) in order to obtain meaningful rales in the special cases.
Assumption 1. The function F(w, B3 is jointly pustrongly convea for μ 2 O, wheile for all m E [M], function I' (w, (m)) is jointhy conver, -moothothh w.r.t. parameter w and (Mmoh) w.r.t. parameter 8m. In the case when μ = 0, assume additionally that has unique solution, denoted as w and 3 = (3i...., BM)
When fm is finite sum we require the smoothness of the finite sum components.
Assumption 2. Suppose that for all m [M] E [n], function fm,(w, Bm) (m)) is jointly conver, C" smoooh w.r.l. parameter w and (Ms")-smooth w.r.t. parameter (mm !
In Section 2 we justify Assumptions 1 and 2 and characterize the constants ,1, L L.P. L L for special cases of Table 2 summarizes these parameters.
Price of generality. Since Assumption D is the only structural assumption we impose on one cannot hope to recover the minimax optimal rates, that is, the rates that match the lower complexity bounds, for all individual personalized FL objectives as a special case of our general guarantees. Note that any given instance of ① has structure that is not covered by Assumption [ but can be exploited by an optimization algorithm to improve either communication or local computation. Therefore, our convergence guarantees are optimal in light of Assumption only. Despite this, general rates specialize surprisingly well we show in Section 2 our complexities are slate-of-the-art in all scenarios with single exception: the communication/ compuuation complexity of [I].
Individual treatment of w and B. Throughout this work, we allow differont smoothness of the objective with respect to global parameters w and local parameters B. At the same time, our algorithm is allowed to exploit the separate access to gradients with respect to w and B, given that these gradients can be efficiently computed separately. Without such a distinction, one might not hope for the communication complexity better than Ô (max{L", Log/ploge" ("), which is suboptimal in the special cases. Similarly, the computational guarantees would be suboptimal as well. See Section 2 for more details.
Data heterogeneity. While the convergence rate of LSGD-PFL relies on data heterogeneily (See The- orem D. we allow for an arbitrary dissimilarity among the individual clients for analyzing ACD-PFL and ASVRCI-PFL (see Theorem 7 and Theorem S). Our experimental results also support that ASCD-PFL (ACD-PFL with stochastic gradient to reduce computation) and ASVRCD-PFL are more robust to data heterogeneity compared to the widely used Local SGD.
The rest of the paper is organized as follows. In Section 2 we show how [ can be used to recover various personalized federated learning objectives in the literature. In Section 3 we propose a local-SGD based algorithm, LSGD-PFT. for solving [ We further establish computational upper bounds for LSGD-PFT. in strongly convex, weakly convex, and nonconvex cases. In Section 4 we discuss the minimax optimal algorithms for solving [1] We first show the minimax lower bounds in terms the number of communication rounds, number of evaluations of the gradient of global parameters, and number of evaluations of the gradient of local parameters, respectively. We subsequently propose two coordinate-descent based algorithms, ACD- PFL and ASVRCD-PFL, which can match the lower bounds. In Section 5 and Section D we use experiments on synthetic and real data to illustrate the performance of the proposed algorithms and empirically validate the theorems. Finally, we conclude the paper with Section? 7 Technical proofs are deferred to the Appendix.
It. easy see that L 2 1 2 6 and L 2 1 c2
4

---

Published in Transactions on Machine Learning Research (May/2023)
2 Personalized FL objectives
We recover a range of known personalized FL approaches as special cases of U In this section, we detail the optimization challenges that arisc each one of the special cases. We discuss the relation to our results, particularly locusing on how Assumptions in the special cases. Table 2 presents the smoothness and strong convexity constants with respect (1) for the special cases, while Table provides the corresponding convergence rates for our methods when applied to these specific objectives. For the sake of convenience, define
and our general rates (presented Sections and behave
Fi(W = M
Σ m=1
(m, 9m)-
in the case when functions fm have finite structure
3
2.1
Traditional FL
The traditional, non-personalized FL objective (McMahan al. 2017
is given as
M Σ (w),
min (ww)
(4)
WERd
M
where fmm corresponds to the loss on the m-th client's data. Assume that f L'-smooth and μ²- strongly convex for all m E [M]. The minimax optimal communication to solve 4 up to e-neighborhood of the optimum is é ((VL'/ul loge (Scaman et al. 2018). When fh (mm is n-finite sum with convex and C' - smoothh components. the minimax optimal local stochastic gradient complexity is v /n log
Hendrikx et al. 2021). The FL objective (4 is a special case of 1 with
dj
dm- 0 and our theory recovers the atorementioned rates.
2.2 Fully Personalized FL
At the other end of the spectrum lies the fully personalized FL where the meth client trains their own model without any inffuence from other clicnts:
1 M Σ (3m)
min P1 ERd
Fiuut (B)
(5)
The above objective is special of 1 with dg 0. As the objective is separable in 3,,..., BMs do not require any communication to train it. At the same time, need é ((n+ vnL loge local stochastic oracle calls to solve it (Lan & Zhou 2018 which is what our algorithms achieve.
2.3 Multi- Task FL of Li et al. (0020)
The objective is given as
>
min
(M = M Σ (3mm + 1118m (w0')(11)
(6)
8 Bs
where (w/) is a solution of the traditional FL in and À > 0. Assuming that (w")* is known (which Li
et al. 2020) does), the problem 6 is particular instance of 5 thus our approach achieves the optimal
complexity.
A more challenging objective (in terms of optimization) the following relaxed version of
M Σ
min w.3
(Aft (w) + fra (9m) )= + A1|wo- Bm 1²),
(7)
M
m=1

---

Published in Transactions on Machine Learning Research (May/2023 2023)
Table 2: Parameters in Assumptions Tnn 2 for personalizes FT. objectives, with note about the rate: we either recover the best best-known known rate for given objoctive, or provide novel rate that the best under the given assumptions. 4: Rate for the novel personalized FI. objective (extension of a known one). : Best-known communication complexity recovered only for X = O(L)).
(fifth and sixth column)
n m(1-Omtt) D Dm
nic X)
-mnos
recovered
recovered
recovered
# V3F,
A
ne 2
nco p
Rate?
new N
new
new
new
0
+ V
V
V
2 (second, third, and fourth column) and 3
n +
m + V
(1
+
Te +
n
n +
Ommmn 1
C
247
2+
31
L'
n(Aohhaa )C Omaan PM
mAC
# V.
+ V n
(A+o mi )
+
n + V
+ V (1
n +
Ae'43
L
C'
2M
A/4
C'
ammm (1- -max) A
(1 (mmma 1
# V
1'4
V
V
1
L
0
4
1+
2M
M
M1
L'
L
V
Table 3: Complexity of solving personalized FL objectives by Algorithmss Constant and log factors are ignored.
(A+a W
(A+a )L
(1- O Omnas / u
A/+2
# V
L
L'
2M
3/4
L
A
V n
D V a
0
V
A++a L LT
V (1 Omma W
1
A
237
#
337
1
# Comm
V I
AL'
V2 1
V 1
0
V
McMMaha al. 2017
FL
Traditional FL (4)
Smith et al. 2017
DDng al. 2020
Liang al. 2020
2020
F 3)
Fully Personalizel
MT2 8
Li ct al. 2020
(11)
APFL2 (14)
WS2 (16)
Fed Resichal
18
Agarwal et al.
Traditional (4)
McMahan et al. 2017)
Fully Personalinn wedddallidddddoooo FL
Li et al. 2020
Smith et al. 2017
APFL2 (114)
Deng et al. 2020)
Linng et al. 2020
18
2020
5
MX2
F(w, 3)
MT2 (8
MX2 (11))
WS2 (16)
Fed Residnal Agaarwal al.
(

---

Published in Transactions on Machine Learning Research (May/202) 2023)
where A 2 is the relaxation parameter, recovering the original objective for A Note that, since A - oo, finding minimax optimal method for the optimization of 6 is straight forward. First, one has to compute a minimizer (w') of the classical FL objective 4 which can be done with a minimax optimal complexity. Next, one needs to compute the local solution 3 = arg g, f' (5m) + Al|w" Bmll?, which only depends on the local data and thus can also be optimized with a minimax optimal algorithm.
A more interesting scenario is obtained when we do not A oo in 7 but rather consider finite A that is sufficiently large. To obtain the right poathhess/sttongg convexity parameter (according to Assumption L scale the global parameter by factor of M and arrive at the following objective:
min DME.
FM
1 M
Σ
ful 9m),
(8)
where
fm fw, = Afm (M (M- w)+ + fm (8m) + 15m - M wil
2
The next lemma determines parameters μ. L L L L in Assumption See the proof in Appendix B.1
Lemma 1. Let A 2 32/(2/(). Then, the objective ( is jointly (2/(2 (112M))-strongff) strongly convex, while the function fm is jointly conver, ((AL' + X)/M))-mooth w.r.t. and (L' X)-smooth w.r.t. 8m- Similarly, the function fm.j is jointly convex, ((AC' + X)/ w.r.l. and (L' + A)-smoolh u.r.l. 8m.
Evaluating gradients. Note that evaluating Wwfm(x, Pm) under the objective S can be perfectly de- coupled from evaluating V (x, (x, 9m). Therefore, we can make full use of our theory and take advantage of different complexities w.r.t. V. and V,s. Resulting communication and computation complexities for solving are presented in Table
2.4 Multi Task Personalized FL and Implicit MAML
In its simplest form, the multi-task personalized objective Smithh et al.
2017
Wang et al. 2018 is given as
M
M
A
min BM..... ERd
(B)
fn (8m)
+
1
Amll?
(9)
M
2M
where 3
M m 8m and A 2 0 Hanzely & Richtárik 2020). On the other hand, the goal of implicit
MAML, (Rajeswaran et al. 2019 Dinh et al. 2020 is to minimize
1
M Σ
(Fh( + " ~11e0 (amn-mmll' 8mll1) ) Bm. ERd
min FME(W)= wERd
min
(10)
M i=1
By reparametrizing we recover objective that is simultaneously equivalent to both (9 and (10 In particular, by setting
[m( 9m.) = (3m) + AlI - bw - Bm
the objective i becomes
M
M
min
FMx2(W, 8) = M m=1
Σ
Pr (Bm)
Σ
||
8m lx2
(11)
w.B U.B. e
2M
m=1
It is simple exercise to notice the equivalence of 11 to both (9) and mize (11) in w, arriving at w² = M B, and thus recovering the solution of Similarly, by minimizing [1]
10
Indeed, can always mini-
in B we arrive at 110
Next, we establish the parameters in Assumptions and
2To the best knowledge, we the first notice the equivalence of

---

A more interesting case (in terms of optimization) is when considcring a relaxed variant of 12 given as Published in Transactions on Machine Learning Research (May/2023)
Lemma 2. Let p' & 2/2. Then the objective smooth w.r.l. w and (T/ X)-smooth w.r.l. $. The function
11 is jointly (1l (u.((3 convez, whill fm is (A/M)-
fm,(w, (m) (3m) (A/2) - Bm 1|2
is jointly convex, (A/M)- w.r.t. w and (C' + X)-smooth w.r.t. 3.
The proof given in Appendix
B.2 Hanzely et al. 2020a showed that the minimax optimal communication
log ' complexity solve (9) (and therefore to solve 110 and is θ (Vmin(I', p)/p'
Furthermore,
they showed that the minimax optimal number of gradients w.r.t. I' is Ô (o(6(((()))) ((VD/M)) log and proposed
method that has the complexity e ((n+ V + +\/p') loge w.r.t. the number of f graddienss.. We match the aforementioned communication guaranlees when X OL')) and computation guarantees when L' = OAA) Furthermore, when À = O(L), our complexity guarantees strictly better compared to the guarantecs for solving the implicit MAML objective [10) directly (Rajeswaran et al. 2019 Dinh et al. 2020
2.5 Adaptive Personalized FL (Deng et al. 2020
The objective is given as
1 = M
min FAP Bs....arr
Σ fm ((1 ammmm + am (mm(w")))
(12)
m=l
where (w')* = arg min wsRd Fww) is solution to 4 and 0 < 01,....a aa < Assuming that (w")* is known, as was done in Deng et al. (2020), the problem optimal complexity.
12 is an instance of 55 thus our approach achieves the
M Σ
min WiD
(Af fla((1 am + am w))
(13)
M
where A the relaxation parameter that allows recovering the original objective when A co. Such choice, alongside with the usual rescaling of the parameter results in the following objective:
M
min W. ERd FAPFIZ(W, B)
1 M
Σ
fwu, Bm)s
(14)
where
fw,, 3m) = (M 2w) + H' ((1 - am 3m + Om M kw))
Lemma 3. Let Ouiin minlgmgM Omm and O'nax maxigg Om- If
A 2
(3az + (1 Orm) )/m))
1sm
then the function FAPFL2 is jointly (1d(1 amax) )/M) -strongly conver, ((A o' -moothh w.r.t. and ((1 L -smoohh -smooth w.r.t. B.
The proof is given in Appendix B.3
2.6 Personalized FL with Explicit Weight Sharing
The most typical example of the weight sharing setting is when parameters w,9 correspond different layers of the same neural network. For example, 81..... Ba could be the weights of first few layers of a neural network, while are the weights of the remaining layers (Liang et al. 2020). Or, alternatively, each
8

---

Published in Transactions on Machine Learning Research (May/2023)
of BI....,Pa correspond to the weights of last few layers, while the remaining weights are included in the global parameter (Arivazhagan et al. 2019). Overall, we can write the objective as follows:
M
min Fws(u, 3)
Σ m=1
Fm((u 9m));
(15)
W E Rd
M
B Par E R
where dn + d3 d. Using an equivalent reparameteriiztiio of the w-space, we aim to minimize
M
min Fwsz(w,8) W E dd
Σ m=1
fm ([,- Bm.))
(16)
M
,
BM E ER
which is an instance of ①1) with sm(w, 3m) I'n [[M--w: Bml)).
Lemma 4.
The function Fws2 is jointly pl -strongly convex,
LL' M
-soooh w.r.t. and L'-smooth w.r.t. B.
Similarly, the function Jm is jointly conver,
x7 -smooth w.r.l. w and C'-smooth w.r.l. B.
The proof is straightforward and, therefore, omitted. A distinctive characteristic the explicit weight sharing paradigm is that evaluating a gradient w.r.t. w-parameters automatically grants cither free or highly cost-effective access to the gradient w.r.t. B-parameters (and vice versa).
2.7
Federated Residual Learning (Agarwal al., 2020)
Agarwal al. 2020 proposed federated residual learning:
min Rd
FR(W, 3)
1 M
Σ 4m (A (w, A (13m2zj =ma)),
(17)
, BM E Rd
where (xm 2 is local feature vector (there may be overlap between xy and ag A (w, a%) represents the model prodiction using global parameters/featunt parameters/ features, and I(.,)) -) is a loss function. Clearly, we can recover [1 with
(B, denotes the model prediction using local
fm (w, Bm) (A ". A (8 "n))
(18)
Unlike the other objectives, here cannot relate constants j L' L' to FR. since do not write fm function of f'm. However, it seems natural to assume L (or L smoothhss of I(At (w, x)),, a (or [a A xBmm)))))) ))) a function of (or 3) for any a xa am x Let define Cy C analogously, given that 1 has n-finite sum structure. Assuming, furthermore, that F is p-strongly convex and fm is convex (for each M), we apply our theory.
2.8
MAML Based Approaches
Meta-learnin has recently been employed for personalization (Chen et al. 2018 Khodak et al. 2019 J Jiang
et al.
2019
Fallah et al. 2020 Lin et al.] 2020). Notably, the model-agnostio meta-learning (MAMT.) Finn
et al.
2017
based personalized FL objective is given as
M Σ
min (MAML((W) = M mK=1
(19)
wERd
Although we can recover 11 as a special case of ① by setting fm(w, 3m) = (w- (w)), our (convex) convergence theory does not apply due the inherent non-convex structure of (19). Specifically, objective FMAML non-convex even if function f convex. In this scenario, only our non-convex rates of Local
SGD apply.
9

---

Published in Transactions on Machine Learning Research (May/2023)
Algorithm LSGD-PFL
input Stepsizes {mh )20 E ls, starting point w E RRdo f E Rdm for all m E [M], communication period т. for == 0, 2,,.... do
if k mod = 0 then Send all w 's to server, let w = MT >m= w Send w to each device, set w = w" Vm E [M]
end if
for m = 1,,,. in parallel do
Sample Si.m ck ~ Dm independently
Compute thh Li=1 Update the iterates (wh+1 1/t11) = (w ):r) - gm end for end for
2 ck Sj,
3 Local SGD
The most popular optimizer to train non-personalized FL models is the local SGD SGD/ /FedAvg MMcMahan et al. 2016 Stich, 2019). We devise a local SGD variant tailored to solve the personalized FL objective 11 LSGD- PFL. See the detailed description of local SGD applied on global parameters and SGD applied on local parameters 3. To mimic the non- personalized setup of local SGD, we assume access the local objective fm (w, Bm) in the form of an unbiased stochastic gradient with bounded variance.
Algorithm [ Specifically, LSGD-PFL can seen as a combination
Admittedly, L.SGD-PL. was already proposed by Arivazhagan et al. (2099) and Liang et al. 2020)) to solve
particular instance of ( However, no optimization guarantees were provided. In contrast, we provide convergence guarantees for LSGD-PFL that recover the convergence rate of LSGD when d1 = d2
dM and the rate of SGD when do 0. Next, we demonstrate that LSGD-PFI. works best when applied an objective with rescaled w-space, unlike what was proposed in the aforementioned papers.
We will need the following assumption the stochastic gradients.
Assumption 3. Assume that the stochastic gradients fm S) and Vofm(w, (w, 5) satisfy the fol- lowing conditions for all m E [M], E Rd, and Bm E BR
EV mn (w,,,,mm Bm, 5) = (w, Bm),
EV f (w, Bm V Vpfm(u, Pm),
E V in I' (w, Bm, () V (w, Bm |1 < o², and
M
E
-affmu Bm) Mo²
m=1
Let
-1 k
(w 3²)=
Σ m1)
(1 np) k- 1 gh).
-
k=
We are now ready state the convergence rate of LSGI-PFL.
Theorem 1. Suppose that Assumptions and 3 hold. Let mh n for all 0, where satisfies
7 min
413 8/3e(T 1
10

---

Published in Transactions on Machine Learning Research (May/2023
M Σ " be the data helerogeneity parameter at the optimau.. The ileration com- Let 3 = M m=1
plerity of Algorithm to ochieve Ef(w" , f(w", e
δ max (I,,, (1O,
o² M Bue
L +
+
The iteration complexity of LSGD-PFL can be seen sum of two complexities the complexity of minibatch SGD to minimize a problem with condition number L y and the complexity of local SGD to minimize a problem with a condition number L" /p. Note that the key reason why we were able to obtain such a rate for LSGD-PFL the rescaling of the w-space by a constant M- Arivazhagan et al. (019) and Liang ett al. (2020), where LSGD-PFL. was introduced without optimization guaranlees, did not consider such a reparametrization.
We also have the following result for weakly convex objectives.
Theorem 2. Suppose that the conditions of Theorem
1
hold. Let μ 0.
The iteration complerity of
Algorithm to achieve B.(kK, ,3th f(w', S
Ô max TD") o²
LV +
c
M
The proofs of Theorem and Theorem can be found in Section 3.2 The reparametrization of w plays key role in proving the iteration complexity bound. Unlike the convergence guarantees for ACD-PFL and ASVRCD-PFL, which are introduced in Section ! we do not claim any optimality properties for the rates obtained Theorem [ and Theorem 2
However, given the popularity of Local SGD as an optimizer for non-personalized FL models, Algorithm ! is natural extension of Local SGD to personalized FL models, and the corresponding convergence rate is an important contribution.
3.1 Nonconvex Theory for LSGD-PFL
To demonstrate that LSGD-PFL works in the nonconvex setting as well, we develop a non-convex theory for it. Therefore, the algorithm also applicable, for example, for solving the explicit, MAML objective. Note that we do not claim the optimality of our results.
Before stating the results, we need to make the following assumptions, which are slightly different from the rest of the paper. First, we need a smoothness assumption on local objective functions.
Assumption 4. The local objective function fm(() is differentiable and L-smooth, that is, [m (u)ll S L|ju - vll for all u, E ddm and m E [M].
This condition is slightly different compared to the smoothness assumption on the objective stated in As- sumption | Next, we need local stochastic gradients to have bounded variance.
Assumption 5. The stochastic gradients V Vafm (w, Bms {) V Volm(w, Pms 9) salisfy for all m [M], w e Rd:,
8m E RRdm:
of
E5 | f. (w, (w, Bm.s) V Vwfm(w, (m))) < C1 C V (w, Bm,)l
B
o
E | (w.
C2 V Byn) Vafm(w, (m. 11
for all m [M], where C1, C2 of, 0z are all positive constants.
This assumption common in the literature. See, for example, Assumption Haddadpour Mahdavi (2019h. Note that this assumption weaker than Assumption 3 We also need an assumption on data heterogeneity.
11

---

Published in Transactions on Machine Learning Research (May/202)
Assumption 6 (Bounded Dissimilarity). There is positive constant À such that for all R and 3m E 1m E [M, we have
Σ (mm)l S M
1
1 M
V Vm Bm)
o day.
This way of characterizing data heterogeneity was used in Haddadpour & Mahdavi 2019 see Definition therein. Given the above assumptions, we can establish the following convergence rate LSGD-PFI. for general non-convex objectives.
for all & 2 0, where is small enough to Theorem 3. Suppose that Assumptions 40 hold. Let satisfy
C1 + C22 +1)+11 An 1)7(C1 + s O.
-1+ -I+
(20)
We have
27
fm (w )
M
k=0
2E
M
Dmml
M
Jm Sm(w (w
+ inLA
{(@
(M + + +1
0 +
o
o3
n
MB
B
+ 1) + +1) "
- 1)²
B
where w 1 M wh is a sequence of so-called virtual iterates.
The following assumption is commonly used to characterize non-convex objectives in the literature. Assumption 7 (p=Polyak-oojasiewiee (PL)). There exists posilive conslant p > 0, such that for all w E Rdo and 8. E Bdm, [M], we have
M Sm(w, 3m) -
Σ
V Pmm)
2 1
1 M
M
When the local objective functions satisfy the PL-condition, we obtain a faster convergence rate stated in the theorem below.
Theorem 4. Suppose that Assumplions hold. Suppose nh = 11/(u(k + Br + 1)), where B is posilive constant satisfying
2XL C + C2+ C2+1) 2, 2T,2 + +1)
B> max
M
12
and is large enough such that
max ( + 1)/12)e11118 -
22
02-1212( + 11)
Then
M Σ
E
fm
K K ,1hh) 1r
M
1=
b3 (K + BT)3
M
fm (w ,Pm) 8r + (T - (1)((++1)++
of
<
E
Σ m=1
11+
M
13(K BT)3
B
LK(K + 2,T +2)
C2 (00++1=
oi
+ 03
41²(K B7)3
M
MB
B
The proofs of Theorem 3 and Theorem can be found in Appendix
B.7
12

---

Published in Transactions on Machine Learning Research (May/2023)
3.2 Proof of Theorem 1 and Theorem 2
The main idea consists of invoking the framework for analyzing local SGD methods introduced in Gorbunov et al. 2021 with several minor modifications. In particular, Algorithm | is an intriguing method that runs a local SGD on w-parameters and SGD on 3-parameters. Therefore, we shall treat these parameter sets differently. Define V2= = M Σ I w I where w = Σm=1 w is defined as in Theorem
The first step towards the convergence rate to figure out the parameters of Assumption 2.3 from Gorbunov ett al. 2021p. The following lemma is an analog of Lemma G.1 in Gorbunov et al. 2021
Lemma 5. Let Assumplions and
hold. Let = max (L", L Then, we have:
M
1
V Vw Wl)l < 6L (S(w", (m))
+ +3(L 3
(21)
M m=1
and
M (
M
V
gl Pm
V Wefmmu |/)ll S 4L (f(w", (.h) - f(w", (2)
(22)
M m==1
m.
M
The proof is given in Appendix B.4 2.3 from Gorbunov et al. [2021).
Using Lemma 5 we recover a set of crucial parameters of Assumption
Lemma 6. Let g = (g and gg.m = (do +): Then
M
E I mll 11? & 6L (((w,,sh) - f(w0, + 3( + a²
+ +
(23)
M
B
m
and
M M
M M
g ? < 4L (f(w*, ( - f(w", + 2( +
20
m
+
BM
(24)
m=1
The proof is given in Appendix B.5 Finally, the following lemma is an analog of Lemma E.1 in Gorbunov et al. 2021)) and gives us the remaining parameters of Assumption 2.3 therein.
Lemma Suppose that Assumptions
and hold and
5 8/Be(T 1
Then
K
2L" 1
np)
EV2 S
Σ
m14
EF g f'w,,8" 2L Σ mp)
"
(25)
0=0
0=
k=
where
02
D = 20(7 - 1)r 35 +
B
The proof is given Appendix B.6 With these preliminary results, we are ready to state the main conver- gence result for Algorithm [
Theorem 5. Suppose that Assumptions ond hold and the stepsize n salisfies
n min 4L3 8/3e(T 1
13

---

Published in Transactions on Machine Learning Research (May/2023)
Define
K
w k
3 K
Σ (1 mH11 k-1
(1 m
k-
(w 3k
=
k=0
k=0
2 21100 w0 1|2 + ΣM
11
B 11?
Φ0 =
and
11
20²
0²
wº = BM
+ 8L" ne(e - 1)7
352 +
B
Then, if p > 0, we have
Ef(w K 3") f(w","")))) (8)) -mu)** Φ0 + t,400
(26)
while, in the case when O, have
1 Bf(w" B²) f(w", ,8) S K n
(27)
The proof follows directly from Theorem 2.1 of Gorbunov et al. 2021 once the conditions are verified, as has been done in Temmal Lemma and Lemma Theorem and Theorem 2 then follow from Corollary D.1 and Corollary D.2 of Gorbunov al. (2021).
4 Minimax Optimal Methods
We discuss the complexity of solving ( in terms of the number of communication rounds required to reach e-solution and the amount of local computation, both in terms of the number of (stochastic) gradients with respect to global u-parameters and local p-parameters.
4.1 Lower Complexity Bounds
We provide lower complexity bounds for solving [ when fm is a finite sum 3
We show that any algorithm
with access to the communication oracle and local (stochastic) gradient oracle with respect to the or B parameters requires at least a certain number oracle calls to approximately solve (1.
Oracle. The considered oracle allows us any iteration to compute either:
Fw.fmaa pm) on each device for randomly selected E [n] and any Wm: Sm or Vafm, (Wm (Wm, (m) each device for randomly selected i E [r]] and any Wms Bmi
the average of wm 's alongside broadcasting the average back to clients (communication step).
Our lower bound is provided for iterative algorithms whose iterates lie in the span of historical oracle queries only. Let us denote such a class of algorithms as A. In particular, for each m, & we must have
8th E Lin (Bn, ( sim..... Vafm k-1 11
and
wht E Lin (w²,
Bon) s...... (w k-1 ,,00' (()())
where
M
Q²= = U 1 (ul. (h))...... Ww ((K) 3
m==1
with 1(k) being the index of the last communication round until iteration k. While such a restriction is
widespread in the classical optimization literature (Nesterov) 2018 Scaman et al. 2018 Hendrikx el al.
2021 Hanzely et al. 2020a) it can avoided by more complex arguments (Nemirovskij Yudin 1983
Woodworth Srebro 2016 Woodworth et al. 2018).
We then have the following theorem regarding the minimal calls of oracles for solving
14

---

Published in Transactions on Machine Learning Research (May/2023)
Algorithm 2 ACD-PFL
input 0< 0 1, 71, v > O, uy = w E Rdd, gg.m 2. E Rdd for 1 S m S M.
for 0, 1,...... do
w (1 f) Aw
for 1,..., M in parallel do
8 = (1 0) 0) ym + 03 sm
end for
1,
with probability Pw
VL"
VT.+
0,
with probability pp VL"+VL"
VT.
if g then
w wh+1
ΣM V (m "
1 M
w
k+I 1tme
[ + mow
VL (Io(VE=+VDr) M
1 EM Vufm(utt,,
for m l...., M in parallel do
gh+1 It (0 + mp
end for
else
for m = 1, 1,....M, M in parallel do
3h-11 = Bk+1
1
am In w ,1/ht2)
y.m
a.m
I
end for
gh+1
(3em + np
v VDF VI V am
7
1-ne
end Itnu
wz
s+1
[w= + x
end for
Then, any algovillom from the class A re- quires at least Q(VL LM /ploge communication rounds, Ω (n /nL//ploge=") calls to V V and Ω (n /nLs//loog calls to a--oralle to reach the e-solution.
Theorem 6. Lel F sulisfy Assumplions 7 and
The proof given in Appendix B.8 In the special case where n == 1, Theorem provides a lower complexity bound for solving ! complexity and local gradient complexity with respect to w-variables of the order Ω (v LM log :)) and the
with access to the full gradient locally. Specifically, it shows both the communication
local gradient complexity with respect to 8-variables the order Q (V log t).
4.2 Accelerated Coordinate Descent for PFL
We apply Acceleratod Block Coordinate Descent (ACD) (Allen-Zhu et al. 2016: Nesterov & Stich 2017
Hanzely Richtárik 2019) to solve [ We separate the domain into two blocks of coordinates to sample from: the first one corresponding to parameters and the second corresponding to B [B1, ..,.... BM)) Specifically, every iteration, we toss an unfair coin. With probability P.. = VL" + VL²), we com- pute Fww (3) and update block w. Alternatively, with probability ps and update block B. Plugging the described sampling of coordinate blocks into ACD, we arrive at Algo- rithun 2 Note that ACD from Allen-Zhu et al. (2016) only allows for subsampling individual coordinates and does not allow for "blocks." A variant of ACD that provides the right convergence guarantees for block sampling was proposed in Nesterov & Stich
Pw, we compute VaF(w, B)
2017) and Hanzely & Richtárik (2019).
We provide an optimization guarantee for Algorithm 2 in the following theorem.
Theorem 7. Suppose that Assumption holds. Let
VV2 + 4v and n 0-!
0
(VD" + VL
2
15

---

Published in Transactions on Machine Learning Research (May/2023)
The iteration complerity of ACD-PFL is
o (V(1
(I.0 + 1.0) //og/
The proof follows directly from Theorem 4.2 of Hanzely & Richtárik 2019 Since V.F(w,,3) B) is evaluated on average once every 1/Pw iterations, ACD-PFL requires O
loge communication rounds and
o (VT.//lloe"" ) gradient evaluations with respect to w, thus matching the lower bound. Similarly, V VgF(w, (3) is evaluated on average once every 1/ps iterations, require O (VI*/ulloe" evaluations of (u, B) to reach an e-solution; again matching the lower bound. Consequently, ACD-PFL, is minimax optimal in terms of all three quantities of interest simultaneously.
We are not the first to propose a variant of coordinate descent (Nesterov) 2012) for personalized FL. Wu et al. (2021) introduced block coordinate descent solve a variant of (11) formulated over network. However, they do not argue about any form of optimality for their approach, which is also less general as only covers single personalized FL objective.
4.3 Accelerated SVRCD for PFL
Despite being minimax optimal, the main drawback of ACD-PFL the necessity of having access to the full gradient of local loss fm with respect to either w or B each iteration. Specifically, computing the full gradient with respect to fm might be very expensive when fm is finite sum 3 Ideally, one would desire algorithm that is i) subsampling the global/local variables w and / just ACD-PFL, ii) subsampling the local finite sum, iii) employing control variates to reduce the variance of the local stochastic gradient (Johnson
& Zhang 2013 Defazio et al. 2014), and iv) accelerated in the sense Nesterov (1983)
We propose a method ASVRCD-PFL that satisfies all four conditions above, by carefully designing an instance of ASVRCD (Accelerated proximal Stochastic Variance Reduced Coordinate Descent) (Hanzely et al. 2020b) applied minimize an objective in lifted space that is equivalent to We are not aware of any other algorithm capable of satisfying i)-iv) simultancously.
The construction of ASVRCD-PFL, involves four main ingredients. First, we rewrite the original problem in lifted space, which corresponds to the problem form discussed in Hanzely et al. (2020b). Second, we construct an unbiased stochastic gradient estimator by sampling coordinate blocks. Next, we enrich the stochastic gradient by control variales as in SVRG. Finally, we incorporate Nesterov's momentum. We explain the construction of ASVRCD-PFL. in detail below.
Lifting the problem space. ASVRCD-PFL is an instance of ASVRCD applied to objective in lifted space. We have that
min WERR B.n Eddm Varee MM]
F(w, 1)
min x|I:d é M
(P(X) F(X) (X)),
X(2. m. gaddm vm EM
where
M
1
F(X) =
Sm (X), m.jl)
M
1=1
and
0 if m. m.m [M].j.j' [n] X[1, X.1.m. X[1, m'] X(2 m. X12, m,J'l
v(x) =
otherwise.
Variables X X11, m. correspond to for all m [M] and E [n). while variables X m. correspond 3m for all [n). The equivalence between the objective and the objective in the lifted space is ensured with
16

---

Published in Transactions on Machine Learning Research (May/2023
the indicator function (X),, which forces different X variables to take the same values. We apply ASVRCD with a carefully chosen non-uniform sampling of coordinate blocks to minimize P(X).
Sampling of coordinate blocks. The key component of ASVRCD-PFL is the construction of the unbiased stochastic gradient estimator (X(X), which we describe here. We consider two independent sources of randomness when sampling the coordinate blocks.
First, we toss an unfair coin Ç. With probability Pus we have < = 1. In such case, we ignore the local variables and update the global variables only, corresponding to x[1] in our current notation. Alternatively, Ç= with probability p3 == 1 Pac- In such case, we ignore the global variables and update local variables only, corresponding to 3 or [2] in our current notation.
Second, we consider local subsampling, At each iteration, the stochastic gradient is constructed using VF, NJ 2m=1 fm.[ 3m) and j is selected uniformly at random from [n]. For the sake of
only, where (w, 3) 1 M simplicity, we assume that all clients sample the same index, i... the randomness is synchronized. A similar rate can be obtained without shared randomness,
With these sources randomness, we arrive at the following construction of G(X), which is an unbiased stochastic estimator of VF(X):
p [X], m', Rd
i - and j =
G(X)(1,m,31
otherwise;
if Ç = 2 and j' = j:
m,,'
0 E Rdm
otherwisc.
Control variates and acceleration. We enrich the stochastic gradient by incorporating control variates, resulting in an SVRG-style stochastic gradient estimator. In particular, the resulting stochastic gradient will take the form of G(X) G(Y) + VF((), where Y is another point that is updated upon a successful toss of a p-coin. The last. ingredient of the method is to incorporate Nesterov's momentum.
Combining the above ingredients, we arrive at the ASVRCD-PFL procedure, which is detailed in Algorithm 3 in the lifted notation. Algorithm details ASVRCD-PFL in the notation consistent with the rest of the paper.
The following theorem provides convergence guarantees for ASVRCD-PFL.
Theorem 8. Suppose Assumptions 1 and
2 hold. The iteration complerity of ASVRCD-PFL with
02 =
= max (2μ, 401/n}
4C
2'
1
[1 02
L
7/4
0, = min
2'
I1 max
{
2 p
wnd Pw LB L
is
o
((p'+ViCu= (3)(()))))) loget))
where is the frequency of updating the control variates.
The communication complexity and the local stochastic gradient complexity with respect w-parameters of order O ((n n / log l)) is obtained by setting p L" ((C" + mm). Analogously, setting P C//L )n) yields the local stochastic gradient complexity with respect to 3-parameters of order ((nn+ VnC*/ loge-)). In contrast with Theorem 6 this result shows that ASVRCD-PFL. can be optimal in terms of the local computation either with respect to d-variables or in terms the w-variables. Unfortumately, these bounds are not achieved simultancously unless L _ are similar order, which we leave for future rescarch. The proof is given in Appendix B.9 Additional discussion on how choose the tuning parameters is given in Theorem
17

---

Published in Transactions on Machine Learning Research (May/2023)
Algorithm 3 ASVRCD-PFL (lifted notation)
input 0 < 01, 02 < 1, 1,7,7 > 0, p (0,1), 1), y = 70 = -xo
for = =0,12,.. 2,,,,... do
X 01 + +22V* 1 + (1 01 -
g G(X*) G(V*) + VF(Vk)
yk+ prox (X* )
zt+l vZth + +(1 x**
k + [ Y
vh+ yk, with probability P
vk, with probability 1- p
end for
5 Simulations
We present an extensive numerical evaluation to verify and support the theoretical claims. We perform experiments on both synthetic and real data, with a range of different objectives and methods (both ours and the baselines from the literature). The experiments are designed to shed light on various aspects of the theory. In this section, we present the results on synthetic data, while in the next section, we illustrate the performance of different methods on real data. The code to reproduce the experiments publicly available at
The experiments synthetic data were conducted personal laptop with CPU (Intel(R) Core(TM) 17-9750H CPU@2.60GHН). The results are summarized over 30 independent runs.
5.1 Multi-Task Personalized FL and Implicit MAML Objective
In this section, we focus on the performance of different methods when solving the objective implement three proposed algorithms LSGD-PFL, ASCD-PFI and ASVRCD-PFL and compare them with two baselines - L2SGD+ (Hanzely & Richtárik, 2020) and PFedMe (Dinh et al. 2020). As both L2SGD+ and Me were designed specifically to solve 11], the aim of this experiment to demonstrate that our universal approach is competitive with these specifically designed methods.
We
Data and model. We perform this experiment syuthetically generated data which allows us to properly control the data heterogeneity level. As a model, we choose logistic regression. We generate w" E IRd with i..dd entries from Uniform[0.49 0.51], and set 8% = w" + ABt E IR,, where entries of A are generated ii.d. from Uniform/4m 0.01, Pm + 0.01] and pm ~ N(0, for all m = 1.2...., M. Thus, σh can be regarded as a measure of heterogeneity level, with a large on corresponding to large heterogeneity. Finally, for each device m 1, 2, ........ M,, we generate Xm,i E Rd with entrics i.i.d. from Uniform (0.2, 0.5] for all ..,, n, and ym..i Bernoulli(pms), where pm, = 1/(1 + exp( xm,))) We set d 15, n 1000, M 20, and let σr E {0.1, 0.3, 1.0} to explore different levels of heterogeneity.
Objective function. We use objective 11 with (9m) being the cross-cntropy loss function. We set X = o1 10-2, so that larger helerogeneity level will induce a larger penalty, which will further encourage parameters on each device to be closer to their geometric center. In addition to the training loss, we also record the estimation error in the training process, defined as ||:0 w0 DM ||3 - 12
Tuning parameters of proposed algorithms. For LSGD-PFL (Algorithm I we set the batch size compute the stochastic gradient B 1, the average period 5, and the learning rate " 0.01. For Pw and pg in ASCD-PFL (Algorithm 5) and ASVRCD-PFL (Algorithm 4 we set them Pw = - /CC L") and p3 = 1 - Pw, where _ = X/M and 2 = (L' + A)/M. We set
|| //4 For w where L = 2 max C /Pw, L /psh:
17, 02.7, 7, and 0, in ASVRCD-PFL, we set them according to Theorem p Pw/n, and μ p² (3M). We let μí be the smallest cigenvalue of RM ΣM E exp(B" xm, /)
PFSCD-PFL. ASVRCD-PFI without control variates. See the detailed description in Appendix
18

---

Published in Transactions on Machine Learning Research (May/2023)
Algorithm 4 ASVRCD-PFL
input < 01, < 1, 11,,, > O, p E (0, Pv (0, 1), ps = Piv: wy w w E
RRdo
30 -30
8o E Rdm for 1 1 m S M.
for = 0,1,2...... 2,. do
w w 02 + - 01 - u
for m l,..,, M in parallel do
3 0133 z. 2 + (1 81 822 Dg.
end for
1,
with probability Pi
Sample random j E (1,2...., mn and & -=
2
with probability ps
M
M
w Sm (1 gl (t.m)
E
V vn Cusmmslu W (mm)) + V Fl (+))
if
Pw
M
M
m=1
m=11
V w F F( (5))
if if =
w 1
_ - ng
u vw (1 v)w (w wx)
w wk+ wy:
with probability P
w with probability 1
for 1..... M in parallel do
V fm ( pl.m)
if =
38.m.
(Vzfm, Bt.m) ) V V (we, Vofm(wt. pt.m)
=
PaM
8k+1
1k a.m
79
9,m
3 2.m + (1
v) a.m + (3 BL.m)
5,m
gh Bg.
with probability p
gk+1
2,00
Bbm with probability
end for end for
exp(3 Xm, 3), .). xm, The N,U,Y in ASCD-PFL the min 1/1}. In addition, initialize all iterates at zero for all algorithms.
in ASVRCD-PFL, and we let 0
Tuning Parameters of pFedMe. For PFedMe (Algorithm 1 in Dinh et al. (0200)) ), we set all parameters according to the suggestions in Section 5.2 Dinh et al. (2220) Specifically, we set the local computation rounds to R = 20, computation complexity to
5, Mini-Batch size to |D] = 5, and = 0.005. We also
set S M 20. To solve the objective (7) in Dinh et al. (2020), we use gradient descent, as suggested the paper. Additionally, initialize all iterates at zero.
set the stepsize 7) (the parameter in Hanzely & Richtárik (2020)) and the probability of averaging Pw to be the same in ASRVCD-PFL, and ASCD-PFL. We also initialize all iterates at zero.
Tuning Parameters of L2SGD+. For L2SGD+ +
4 "Algorithm Hanzely & Richtárik 2020
19

---

Published in Transactions on Machine Learning Research (May/2023)
LSGD PFL
ASVRCD-
L25GD+
ASCD-PFL
PFedMe
0.7
0.7
0.6
Training Loss
MX2
0..
0.5
0.4
0.4
0.4
0.3
300
1000
0
500
1000
0
500
1000
80
60
200
Estimation Error
60
MX2
40
150
40-
20-
50
500 1000
0
500
1000
0
500
1000
Communication Rounds dh 0.1
Communication Rounds
Communication Rounds
d 1.0
Figure 1: Comparison of various methods for minimizing [1 Each experiment was repeated 30 times, and the solid line represents the average performance, while the shaded region indicates the mean + standard error. We set the communication period of LSGD-PFL at 5, while other methods synchronize based on the corresponding theory. The first row shows the training loss, and the second row shows the estimation error. The different columns correspond to varying heterogeneity levels, which are parameterized by dh. As σ increases, the heterogeneity level also increases.
Oh
0.1
0.3
1.0
Algorithm
LSGD
260.98
256.16
237.18
ASCD
28.79
51.71
142.59
ASVRCD
47.94
97.61
274.60
PFedMe
399.33
370.42
370.35
L2SGDplus
25.83
47.59
182.29
Table 4: The average wall-clock running time in seconds over 30 independent runs when solving the objec- tive 11 Each entry in the table reports the average time for 1,000 communccttio rounds. We ignore any additional communication costs that might occur in practice.
Results. The results are summarized in Figure I We observe that general-purpose optimizers are competitive with L2SGD+ and pFedMe. In particular, both ASVRCD-PFL. and L2SGD+ consistently achieve the same training error as the other methods, which is well predicted by our theory. Although L2SGD+ is slightly faster terms of convergence due to the specific parameter setting, it is not as general as the methods we propose. Furthermore, we note that the widely used LSSDD-PLL suffers from data heterogeneity on different devices, whereas ASVRCD-PFL not affected by this heterogeneity, predicted by theory. The average running time 30 independent runs is reported in Table 4
20

---

Published in Transactions on Machine Learning Research (May/2023)
LSGD-PFL
ASCD-PFL
ASVRCD-PFI
0.70
0.7
0.08
0.65
Training Loss
0.6
EWS
0.64
0.35
0.02
0.50
0.4
0.445
500
1000
500
1000
500
1000
300
EWS Estimation Error
600
200
40
100
200
20
0
500
1000
500
1000
500
1000
Communication Rounds
Communication Rounds
Communication Rounds
0% 5.0
0% 10.0
0% 15.0
Figure 2: Comparison of the three proposed algorithms LSGI-PFL, ASCD-PFL, and ASVRCI-PFL when minimizing (16). Each experiment is repeated 30 times; the solid line represents the mcan performance, and the shaded region covers the mean = standard error. We set the communication period of LSGD-PFL to 5, while other methods synchronize according to their respective theories. The first row represents the training loss, and the second row corresponds to the estimation error. Different columns indicate various heterogeneity levels, parameterized by σn- The heterogeneity level increases with on-
5.2 Explicit Weight Sharing Objective
In this section, we present another experiment on synthetic data that aims to optimize the explicit weight sharing objective (16). Since there is no good baseline algorithm for this objective, the purpose of this experiment to compare the three proposed algorithms: LSGD-PFL, ASCD-PFL, and ASVRCD-PFL.
Data and Model. As a model, we choose logistic regression. We generate w² E Rdd, with i.i.d. entries from N (0, 1), and 3%, E gd with i.id. entries from Uniform|um 0.01, pm + 0.01], where um N o for all m M. Thus, oh can be regarded corresponding to high degree of heterogeneity. Finally, for each device X,na E +d with entries i..d. from Uniform(0.0 (0.0,, 0.1] for all i = 1,2, where Pm,i = 1/(1 + exp((w*T T )xm,i)). We set d 10, di = 5, n 1000, M = 20, and let σ E (5.0, 10.0, 15.0] to explore different levels of heterogeneity.
measure of the heterogeneity level, with large
......,,, M, we generate and Vm., Bernoullí(m..))
1,2,...,
Objective function. We use objective 11 with f'n (5m) representing the cross-entropy loss function. We set À σ₁ 10-2, so smaller heterogeneity levels will induce larger penalty, eucouraging parameters on each device to be closer to their geometric center. In addition to the training loss, also record the estimation error during the training process, defined as |
-w"l" - || 3/,11
The results are sunmarized in Figure 2 When examining the training loss, we observe that ASCD- PFL drives the loss down quickly initially, while ASVRCD-PFL ultimately achieves a better optimum. This suggests that we can apply ASCD-PFL. at the beginning of training and add control variates to reduce the variance at a later stage of training, thus combining the benefits of both algorithms. Both ASCD-PFL and ASVRCD-PFL, perform much better than the widely used LSGD-PFL. When analyzing the estimation
Results.
21

---

Model. Given grayscale picture with a label y E (1,2,..., C). we unroll its pixel matrix into vector E R?. Then, given paramcter matrix θ RoxC, the function f/, (.) in and 14 is defined as Published in Transactions on Machine Learning Research (May/2023)
0h
5.0
10.0
15.0
Algorithms
LSGD
238.01
237.67
234.33
ASCD
17.00
16.55
16.46
ASVRCD
23.35
22.12
23.51
The average wall-clock running time in seconds over 30 independent runs when solving the objec- tive (66 is presented. Each entry of the table reports the average time for 1,000 communication rounds. We ignore any additional communication costs that might occur in practice.
Table 5:
error, we observe that when the heterogeneity level small, there is a tendency for overfitting, especially for ASCD-PFL; and when the heterogeneity level increases, there less concern for overfitting. general, however, ASCD-PFL and ASVRCD-PFL still achieve better estimation error than LSGD-PFL. The average running time over 30 independent is reported in Table
6 Real Data Experiment Results
In this section, we use real data to illustrate the performance and various properties the proposed methods. In Section 6.1 we compare the performance the three proposed algorithms. Section 6.2 we illustraae the effect of commuication frequency of global parameters for ASCD-PFL and demonstrate that the theoretical choice based on Theorem g can generate the best communication complexity. Finally, in Section 6.3 we show the effect of reparametrizing w for ASCD-PFL.
6.1 Performance of the Proposed Methods on Real Data
We compare the three proposed algorithms LSGD-PFL, ASCD-PFL (ASVRCD-PFL without control variates), and ASVRCD-PFL. across four image classification datasets MNIST (Deng) 2012), KMIN- IST (Clanuwat et al. 2018 FMINST (Xiao et al. 2017). and CIFAR-10 (Krizhevsky] 2009) with three objective functions { layer fully counected neural network combined with a softmax function and cross-entropy loss. Experiments were conducted on a personal laptop (Intel(R) Core(TM) 17-9750H CPU@2.60GH2) with GPU (NVIDIA Gelfore RTX 2070 with Max-Q Design).
and (1). As a model, we use a multiclass logistic regression, which is a single-
Data preparation. We set the number of devices M = 20. We focus non-i.id. setting of McMahn et al. 2017) and [iang et al. (020)) by assigning K classes out of ten to each device. We let K = 2, 4, 8 to generate different levels of heterogeneity. A larger K means a more balanced data distribution and thus smaller data heterogeneity. We then randomly select n = 100 samples for each device based on its class assignment for training and n' = 300 samples for testing. We normalize each dataset in two steps: first, we normalize the columns (features) have mean zero and unit variance; next, we normalize the rows (samples) that every input vector has a unit norm.
fr (+) IcE (s(Ox):
where <(-) K + R the softmax function and (CB(.) is the cross-entropy loss function. In this setting, the function f% (.) is convex.
22

---

Published in Transactions on Machine Learning Research (May/2023)
LSGD-PFL
ASCD-PFL
ASVRCD-PFL
0.00
MT2
LoSs
0.08
0.09
0.07
0.07
0.07
0.00
0.08
500
1000
500
1000
500
1000
1000
0.04
0.04
0.04
0.04
0.04
MX2
LOSS
0.04
0.00
0.03
0.04
0.02
0.03
0.02
0.03
500
1000
0
500
1000
500
1000
500
1000
0.00
0.08
0.08
LOSS
0.06
0.05
0.04
0.04
0.06
0.04
0.05
0.02
Communication Rounds MNIST
Communication
Communication
Communication
Rounds KMNIST
Rounds FMNIST
Rounds CIFAR10
(a) Training Loss
LSGD-PFL
ASCD-PFL
ASVRCD-PFL
1.00
1.00
3.00
3.00
Accuracy
0.75
0.75
0.75
0.75
MT2
0.50
0.50
0.30
0.50
0.25
0.25
0.25
0.25
0.00
1002
1000
1000
1.00
Accuracy
MX2
0.50
0.50
0.30
0.25
0.25
0.25
0.25
0.00
500
1000
0,00
500
1008
00
500
1000
00
500
1000
2.00
11000
1.00
3.00
Accuracy
0.75
0.75
0.75
0.75
0.50
0.50
0.50
0.50
1000
Communication Rounds MNIST
Communication Rounds KMNIST
Communication Rounds FMNIST
Communication Rounds CIFAR10
(b) Validation Accuracy
Figure 3: The real data experiment results for K = 2. Different rows correspond to different objective functions, and columns correspond to different datasets.
23

---

Published in Transactions on Machine Learning Research (May/2023)
LSGD-PFL
ASCD-PFL
ASVRCD-PFL
0.09
0.09
MT2
LoSS
0.08
0.08
0.00
0.07
0.07
0.00
0.06
500
1000
500
1000
500
1000
1000
0.04
0.04
0.00
0.04
0.04
0.04
MX2
LOSS
0.04
0.03
0.03
0.02
0.04
0.03
0.04
0.02
0.02
0.02
500
1000
0
500
1000
500
1000
500
1000
0.09
0.08
0.08
0.08
0.00
LOSS
0.07
0.04
0.04
0.06
Communication
Communication
Communication
Communication
Rounds MNIST
Rounds KMNIST
Rounds FMNIST
Rounds CIFAR10
(a) Training Loss
LSGD-PFL
ASCD-PFL
ASVRCD-PFL
1.00
1.00
3.00
3.00
Accuracy
0.75
0.75
0.75
0.75
MT2
0.50
0.50
0.30
0.50
0.25
0.25
0.25
0.25
0.00
1000
1000
1000
1.00
Accuracy
MX2
0.50
0.30
0.25
0.25
0.25
0.25
0.00
500
1000
500
1000
00
500
1008
00
500
1000
2.00
1.00
1.00
3.00
Accuracy
0.75
0.75
0.75
0.75
0.50
0.50
0.50
1000
Communication Rounds MNIST
Communication Rounds KMNIST
Communication Rounds FMNIST
Communication Rounds CIFAR10
(b) Validation Accuracy
Figure 4: The real data experiment results for K = 4. Different rows orrespond to different objective functions, and columns correspond to different datasets.
24

---

Published in Transactions on Machine Learning Research (May/2023)
LSGD-PFL
ASCD-PFL
ASVRCD-PFL
0.09
0.09
0.00
MT2
LOSS
0.07
0.06
0.08
500
1000
500
1000
500
1000
1000
0.05
0.04
0.04
0.04
MX2
LO5
0.03
0.03
0.04
0.02
0.02
0.02
0.04
0.03
500
1000
0
500
1000
0
500
1000
500
1000
0.09
0.00
0.08
LOSS
0.08
0.06
0.08
0.04
0.04
0.02
Communication Rounds MNIST
Communication
Communication
Communication
Rounds KMNIST
Rounds FMNIST
Rounds CIFAR10
(a) Training Loss
LSGD-PFL
ASCD-PFL
ASVRCD-PFL
1.00
1.00
1.00
3.00
Accuracy
0.75
0.75
0.75
0.75
MT2
0.50
0.50
0.30
0.50
0.25
0.25
0.25
0.25
0.00
1000
1000
1000
1.00
Accuracy
MX2
0.50
0.30
0.25
0.25
0.25
0.25
0.00
500
1000
500
1008
00
500
1008
00
500
1000
1.00
1.00
1.00
3.00
Accuracy
0.75
0.75
0.75
0.75
0.50
0.50
0.50
1000
1000
Communication Rounds MNIST
Communication Rounds KMNIST
Communication Rounds FMNIST
Communication Rounds CIFAR10
(b) Validation Accuracy
Figure 5: The real data experiment results for K =ー 8. Different rows correspond to different objective functions, and columns correspond to different datasets.
25

---

Published in Transactions on Machine Learning Research MMa/2223)
Personalized FL objectives.
We consider three different objectives:
the multitask FL objective 8 with A = 1.0 and = 1.0/K;
2. the mixture FL objective 11 with X 1.0/K; and
3. the adaptive personalized FL objective
14). with A 1.0 and am 0.05 K for all m E [M],
where K' is the number of labels for cach device. When computing the testing accuracy, we only use the local parameters. Note that the choices of hyperparameters in the chosen objectives are purely heuristic. Our purpose is to demonstrate the convergence properties of the proposed algorithms on the training loss. Thus, it is possible that smaller training loss does not necessarily imply better testing accuracy (or generalization ability). How to choose hyperparameters optimally is not the focus of this paper and requires further research.
we set the batch size to compute the stochastic gradient B = and set the average period J = 5. For Pv in ASCD-PFL. (A [Algorithm G
Tuning parameters of proposed algorithms. For LSGD-PFL (Algorithm
and ASVRCD-PFL (Algorithm 7 we set it as Pu = (CB + (W). ). For the objective F FMT2 in
(8 we set
LT (AL' + A)/M and L C A; for the objective FMX2 x2 in [1]. we set L A/M and L C
+ X; for
the objective FAPFL2 in [4), we set L (A+ maxism a C/M and L = (1 maxisms am ) C We set L' = 1.0 for all objectives. We set p Pw// for ASCD-PFL and ASVRCD-PFL. For 17. 02 7, and O, in ASVRCD-PFL, we set them according to Theorem g where L 2 max (L /Dm,, L (0,.C///pp/ /pp), p pw/n,
and = = (3MM. We let μ' = 0.01. Since the dimension of the iterates is larger than the sample size, the objective is weakly convex and, thus, / = 0. Therefore, our choice of jı' is aimed at improving the numerical behavior of algorithms. The 17, T.P in ASCD-PFL are the same as in ASVRCD-PFL, and we let 0 m 1/n]- In addition, we initialize all iterates at zero for all algorithms.
Results. The results are summarized in Figure Figure 1 and Figure for K 2,8,8 respectively, We observe that ASCD-PFL outperforms the widely-used LSGD-PFL. We also observe that ASVRCD-PFL converges slowly when minimizing the training loss. As we are working in the over parametrivation regimes, which makes μ² = O, the assumptions of our theory are violated. As a result, it is more advisable to use ASCD-PFL during the initial phase of training and use ASVRCD-PFL when the iterates gel closer to the optimum.
6.2 Subsampling of the Global and Local Parameters
g specifically setting Pw: = L (C results the best communication complexity of ASCD-PFL. More precisely, based on Theorem D we set the learning rate 7 1/(4C), where L = 2 max {L" / Pur, L /pa). The expressions of _ and L for FMT2, FMxx2, and FAPFL2 are stated in Lemma | Lemma 2 Lemma 3] and also restated in the previous section, where L' is 1 after normalization. We set م = Pn. We compare the performance of ASCD-PFI, using the theoretically suggested Pw with other choices of Pa E 10.1,00 0.3, 0.5, 0.7, 0.9). We fix those parameters that are independent of Puc- See more details about the choice of tuning parameters in the previous section.
We demonstrate that the choice of Pw based on Theorem
We plot the loss against the number of communication rounds, which illustrates the communication com- plexity. The number of classes for each device is K 2. The results are summarized in Figure 6 which also includes the test accuracy. We observe that choosing pw based on theoretical considerations leads to the best communication complexity.
6.3 Effect of Reparametrization in ASCD-PFL.
We demonstrate the importance of reparametrization of the global parameter w by rescaling by a factor of M We run reparameterized and non-reparamcttriiee ASCD-PFL across different objectives and datasets. We set the number of classes for each device K = 2. The results are summarized in Figure 7 For the training loss, we observe that reparametrization improves the convergence of ASCD-PFL, except for the APFL2 objective (1h, where the non-roparamctrized variant performs slightly better in three of the four datasets. On the other hand, when considering the testing accuracy, reparametrization always helps improve the results, indicating that reparametrization can help prevent. overfitting. Based the experiment, we
26

---

Published in Transactions on Machine Learning Research (May/2023)
P_w=0.1
P_W=0.5
P_w=0.9
p P_w=0.3
P_w=0.7
p. >_w=theory
0.09
0.09
0.00
0.09
0.08
MT2
LO55
0.08
0.09
0.07
0.07
0.06
0.06
0.08
1000
1000
0.04
0.04
0.04
0.04
0.04
MXX
LOSS
0.04
00.03
0.03
0.03
0.04
0.05
0.03
500
1000
0
500
1000
0
5000
1000
500
1000
0.09
0.08
0.08
0.08
LosS
0.06
0.07
0.04
0.04
0.06
0.05
0.02
Communication Rounds MNIST
Communication Rounds KMNIST
Communication Rounds FMNIST
Communication
Rounds CIFAR10
(a) Training Loss
P_W=0.5
P_w=0.9 p p_w=theory
p_ W.3
P_w=0.7
1.00
1.00
1.00
1.00
Accuracy
0.75
0.75
0.75
0.75
MT2
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
1000
1000
1000
Accuracy
0.75
MX2
0.50
0.50
0.50
0.50
0.25
0.25
0:25
0.25
0.00
1000 00
1000
00
1000
00
1000
1.00
1.00
3.00
Accuracy
0.75
0.75
APPL2
0.00
300 Communication Rounds MNIST
Loo 00
500
1000 00
500
1000 00
500 1000
Communication Rounds KMNIST
Communication Rounds FMNIST
Communication Rounds
CIFAR10
(b) Validation Accuracy
Figure 6: Communication complexity for different choices of pw- The theoretical choice based Theorem 9 provide the best communication complexity. Specifically, the theoretical choice of Pm results in Pa, 0.5
for FMrT2, Pe 0.25 for FMX2, and Pv, = 0.55 for FAPPL2- Different rows correspond to different objectivve functions, and columns correspond to different datasets.
27

---

Published in Transactions on Machine Learning Research (May/2023)
Reparam
Non-Reparam
0.09
0.09
0.09
0.08
MT2
LOSS
0.08
0.09
0.07
0.07
0.06
0.06
0.08
1000
1000
0.04
0.04
0.04
0.04
0.04
MX2
LOSS
0.04
00.03
0.03
0.03
0.04
0.03
0.03
300
1000
0
500
1000
0
5:00
1000
500
1000
0.09
0.00
0.06
0.08
0.08
LOSS
0.00
0.06
0.07
0.04
0.04
0.04
0.06
0.02
p.02
0.05
Communication Rounds
Communication
Communication
Communication
Rounds KMNIST
Rounds FMNIST
Rounds CIFAR10
MNIST
(a) Training Loss
Reparam
Non-Reparam
1.00
1.00
.00
1.0
Accuracy
0.75
0.75
0.75
0.75
MT2
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
1008-00
1000
1000
My FAA A
Accuracy
MX2
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
0.00
1000 00
1003
00
1000
00
1000
1.00
3.00
Accuracy
0.75
APPL2
0.00
300 Communication Rounds
Lool 00
500
1008 00
500
1000 00
500
1000
Communication Rounds KMNIST
Communication Rounds FMNIST
Communication Rounds
MNIST
CIFAR10
(b) Validation Accuracy
Figure 7: Effect of reparametrization of global space in ASCD-PFL. Reparametrization generally helps achieve faster convergence in minimizing training loss and consistently improves testing accuracy. Different rows correspond to different objective functions, and columns correspond to different datasets.
28

---

Published in Transactions on Machine Learning Research (May/2023)
1.0
A 10.0
100.0
1.00
1.00
1.00
1.00
0.75
0.75
0.75-
Test Accuracy
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
0.00
0.00
10000.00
0.00
0.00
250
500
750
1000
500 Communication Rounds KMNIST
250
750
1000
250
500
750
1000
250
500
750
1000
Communication Rounds MNIST
Communication Rounds FMNIST
Communication Rounds
CIFAR10
Figure Empirical exploration of the effect of A on the performance of the objective in
suggest always using reparametrization to ensure the scale of the learning rate is appropriate for both global and local parameters.
6.4 Potential Benefits of Extended Objectives
We empirically justify the potential benefits of our extended objectives. More specifically, we vary the relaxation parameter in (7) to show the change in performance. Since the multitask objective proposed main interest is to explore whether larger A always implies better performance. We set K = 4, 30, n' = 100, M 20, and X = 0.1. The remaining settings are the same as in Section 6.1 We vary A over the values {1.0, 10.0, 100.0), and the resulting performance is shown in Figure 10.0, but then drops when A = 100.0. This result suggests that by selecting an appropriate A, is possible achiove better empirical performance. Furthermore, although proposing new personalized FL objectives is not the main focus of this paper, the above empirical result suggests the potential benefits of a general framework.
by Li al. (2020) is equivalent to setting A 0o,
The plot shows that the performance slightly improves as increases from 1.0 to
7 Conclusions and Directions for Future Research
We proposed general convex optimization theory for personalized FL. While work answers range of important questions, there are many directions in which our work can be extended in the future, such partial participation, minimax optimal rates for specific personalized FL objectives, brand new personalized FL objectives, and non-convex theory.
Partial participation and client sampling. An essential aspect of FT. that is not covered this work is the partial participation or client sampling when one has access to only a subset of devices cach itcration. While we did not cover partial participation and focused answering orthogonal questions, we believe that partial participation should be considered when extending our results in the future. Typically, when one chooses clients uniformly, the theorems in this paper should be extended casily; however, more interesting question is how to sample clients with a non-uniform distribution to speed up the convergence. We leave this problem for future study.
Minimax optimal rates for specific personalized FL objectives. As outlined in Soction 1.2 one cannot hope for the general optimization framework to be minimax optimal in every single special case. Consequently, there is still need to keep exploring the optimization aspects of individual personalized FT.
29

---

Published in Transactions on Machine Learning Research (May/202) 2023)
objectives might come up with more efficient optimizer that exploits the specific structure not covered by Assumption or Assumption 2
Brand new personalized FL objectives. While in this work we propose a couple of novel personalized FL objectives obtained as an extension of known objectives, we believe that seeing personalized FL as an instance of might lead to the development of brand new approaches for personalized FT..
Non-convex theory. In this work, we have focused on general convex optimization theory for person- alized FL. Our convex rates meaningful they are minimax optimal and correspond to the empirical convergence. However, an inherent drawback of such an approach is the inability to cover non-convex FI, approaches, such as MAML (see Section 2.8), or non-convex FL models. We believe that obtaining minimax optimal rates in the non-convex world would be very valuable.
30

---

Published in Transactions on Machine Learning Research (May/2023)
References
A. Agarwal, J. Langford, and C.-Y. Wei. Federated residual learning. arXiv preprint 1rXXi:2003.12890 2020.
Z. Allen-Zhu, Z. Qu, P. Richtárik, and Y. Yuan. Even faster accelerated coordinate descent using non-uniform sampling. In International Conference on Machine Learning, 2016.
M. G. Arivazhagan, V. Aggarwal, A. K. Singh, and S. Choudhary. Federated learning with personalization layers. arXiv preprint arxiv: 19X.::9112000000 008188, 2019.
F. Chen, M. Luo, Dong, Z. Li, and X. He. Federated meta-learning with fast convergence and efficient communication. arXiv preprint arXiv:1802, 07876, 2018.
T. Clanuwat, M. Bober-Irizar, A. Kitamoto, A. Lamb, K. Yamamoto, and D. Ha. Deep learning for classical japanese literature. arXiv preprint or arXiv.1812.0174. 2018.
J. Dean, G. Corrado, R. Monga, K. Chen, M. Devin, Q. Le, M. Z. Mao, M. Ranzato, A. W. Senior, P. A. Tucker, K. Yang, and A. Y. Ng. Large scale distributed deep networks. In Advances in Neural Information Processing Systems, 2012.
A. Defazio, F. R. Bach, and S. Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Information Processing Systems, 2014.
L. Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-142, 2012.
Y. Deng, M. M. Kamani, and M. Mahdavi. Adaptive personalized federated learning. ar preprinl arXiv:2003. 2020.
C. T. Dinh, N. H. Tran, and T. D. Nguyen. Personalized federated learning with moreau envelopes. Tn Advances in Newral Information Processing Systems, 2020.
A. Fallah, A. Mokhtari, and A. Ozdaglar. Personalized federated learning: A meta-learning approach. arXiv preprint trXiv:2002.079) 079488 2020.
C. Finn, P. Abbeel, and S. Levine. Modcl-agnostic meta-learning for fast adaptation of deep networks. In International Conference on Machine Learning, 2017.
E. Gorbunov, F. Hanzely, and P. Richtárik. Local SGD: unified theory and new efficient methods. International Conference on Artificial Intelligence and Statisties, 2021.
F. Haddadpour and M. Mahdavi. On the convergence of local descent methods in federated learning. anXiv preprint Xio::1910..1 1414.445,,, 2019.
F. Hanzely and P. Richtárik. Accelerated coordinate descent with arbitrary sampling and best rates for minibatches. In International Conference on Artificial Intelligence and Statisties, 2019.
F. Hanzely and P. Richtárik. Federated learning of mixture of global and local models. arXiv preprint arXiv:2002.0551 2020.
F. Hanzely, S. Hanzely, S. Horváth, and Richtárik. Lower bounds and optimal algorithms for personalized federated learning. In Advances Neural Information Processing Systems, 2020a.
F. Hanzely, D. Kovalev, and P. Richtárik. Variance reduced coordinate descent with acceleration: New method with surprising application to finite-sum problems. In International Conference on Machine Learning, 2020b.
A. Hard, Rao, R. Mathews, S. Ramaswamy, F. Beaufays, S. Augenstein, H. Eichner, C. Kiddon, and D. Ramage. Federated learning for mobile keyboard prediction. arXiv preprint ar 1111 1.0000644, 2018.
31

---

Published in Transactions on Machine Learning Research (May/2023
H. Hendrikx, F. Bach, and L. Massoulie. An optimal algorithm for decentralized finite-sum optimization. SIAM Journal on Oplimization, 31 (4):2753-22)) 27833,2773--2 2021.
Y. Jiang, Konečný, K. Rush, and S. Kannan. Improving federated learning personalization via model agnostic meta learning. Xiv preprint arXiu:1909. 12488, 2019.
Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances Neural Information Processing Systems, 2013.
P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, et al. Advances and open problems in federated learning. Foundations and Trendol in Machine Learning, 14(1 2):1 210, 2021.
M. Khodak, M. Balcan, and A. Talwalkar. Adaptive gradient- meta-learning methods. In Advances in Newral Information. Processing Systems, 2019.
A. Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
V. Kulkarni, M. Kulkarni, and A. Pant. Survey of personalization techniques for federated learning. In 2020 Fourth World Conference on Smart Trends in Systems, Security and Sustainability (World54), pp- 794 797, 2020.
G. Lan and Y. Zhou. An optimal randomized incremental gradient method. Mathematical programming, 171(1-2):167 215, 2018
T. Li, S. Hu, A. Beirami, and V. Smith. Federated multi-task learning for competing constraints. arXiv preprint Xiv: 04221, 2020.
P. P. Liang T. Liu, L. Ziyin, R. Salakhutdinov, and L.-P. Morency. Think locally, act globally: Federated learning with local and global representations. arXiv preprint arXiw:2001.01525 2020.
S. Lin, G. Yang, and J. Zhang. A collaborative learning framework via federated meta-learning. In Interna- tional Conference Distributed Computing Systems, 2020.
B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Commmicationn-ffiioen learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statistics, 2017.
B. McMahan, Moore, D. Ramage, and B. A. y Arcas. Federated learning deep networks using model averaging. arXiv preprint 1012::6602056222 2016.
A. S. Nemirovskij and D. B. Yudin. Problem complerity and method efficiency in optimization. Wiley- Interscionce, 1983.
Y. Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341-362 2012.
Y. Nesterov. A method for solving the convex programming problem with convergence rate o(1/k2). In Doklady Akademii Nauk, volume 269, pp. 543-547, 1983.
Y. Nesterov. Lectures on Conver Optimization. Springer, 2018
Y. Nesterov and S. U. Stich. Efficioncy of the accelerated coordinate descent method on structured opti- mization problems. SIAM Journal on Oplimizalion, 27(1):110-L 123, 2017.
A. Rajeswaran, C. Finn, S. M. Kakade, and S. Levine. Meta-learning with implicit gradients. In Advances in Neural Information Processing Systems, 2019.
K. Scaman, F. R. Bach, S. Bubeck, Massoulié, and Y. T. Lee. Optimal algorithms for non-smooth distributed optimization in networks. In Advances in Neural Information Processing Systems, 2018.
32

---

Published in Transactions on Machine Learning Research (May/2023)
V. Smith, C. Chiang, M. Sanjabi, and A. Talwalkar. Federated multi-task learning. In Advonces in Neural Information. Processing Systems, 2017.
S. U. Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations, 2019.
W. Wang, J. Wang, M. Kolar, and N. Srebro. Distributed stochastic multi-task learning with graph regu- larization. arXiv preprint arXi:: 03830, 2018.
B. E. Woodworth and N. Srebro. Tight complexity bounds for optimizing composite objectives. In Aduances in Neural Information Processing Systems, 2016.
B. Woodworth, J. Wang, A. D. Smith, B. McMahan, and N. Srebro. Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. In Advances in Neural Information Processing Systems, 2018.
Wu, A. Scaglione, H. Wai, N. Karakoç, K. Hreinsson, and W. Ma. Federated block coordinate descent scheme for learning global and personalized models. In AAAI Conference on Artificial Intelligence, 2021.
H. Xiao, K. Rasul, and R. Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint 07Xi:11008.07747, 2017.
33

---

Published in Transactions on Machine Learning Research (May/202)
A Additional Algorithms Used in Simulations
In this section, we detail algorithms that are used in Section 5 We detail ASCD-PFL in Algorithm ASCD-PFL is simplified version of ASVRCD-PFL that does not incorporate control variates. SCD-PFL is detailed in Algorithm 0 SCD-PFL. is a simplified version of ASCD-PFL, that does not incorporate the control variates or Nesterov's acceleration. SVRCI-PFL detailed Algorithm SVRCD-PFL simplified version of ASVRCD-PFL that does not incorporate Nesterov's acceleration.
Algorithm 5 ASCD-PFL
input < 8 1, 7, O, pE (0.1), Pw E (0,1), P3 Pw: w u E Rdd, Sy. P2 E Im for
1 1 m < ..
for 1,1 2....... do
- fw + (1 O)
for m = l,..., M in parallel do
3 = 033 a,m + (1 - 8) ym
end for
{
with probability Pu
Sample random j E 21,2,.... nn and ( s=
2 with probability Pa
if then
- PuM Em Vurmij(utt gle gtem)
wk+1 _ ng
wh v + +1 v) + 2/ (w w
w with probability P
wk+t
w with probability 1
else
for m = ,,...,M. M in parallel do
g 3.m PaM
V Vefm.s (5..)
g 5 3m
9.m
88+11
v
+ (1 (1 z.m + ( 3k p
s.m
y.m
gk+1 Dy.m
with probability P
Bkm
with probability 1 1-0 -p
end for end
end for
34

---

Published in Transactions on Machine Learning Research (May/2023)
Algorithm 6 SCD-PFL
input 1i > 0, Pw E (0, Ps for 1, K do
Pws w0 E IRdd 3 E IRd for m S M.
{1 with probability Pio
1
Sample random Jm E {1,2,.... nm for 1 S m S M and ( =
$=12 -2 with probability Pa
Em=1 Valmin (w
gw
=
Pu
0
if = 2
w
k++
ng
for m
1,..., M parallel do
if ç =
f3.m
V Valmiin (w Bhh)
if ( 2
P
88+1
Bt. n/
end for end for output K 9 for S m S M.
Algorithm 7 SVRCD-PFL
input 17 0, Pw (0,1), ps for h = 0. K - 1 do
Dws P E (0, w w E Rdd, ggm Bum 12d for m M.
(1 with probability Pio
Sample random Jm E (1,2,..., nm for 1S m & M and <=
2
with probability ps
M Em=1
Vufm.sm (uy, 3 my.m) + V. F Bt)
if { ç=1
Pu
V. F(utt wi -ng*
if Ç = 2
w with probability
w
k++
wh
with probability 1-p p
for m
M in parallel do
V Im (w (b.m) V ammmann (ut, gk m))) + M V (mm
C
o/3m
M3
if ( =
P
g8+1
p.m
n
g8+1
8k
g.m.
with probability
Bb Bb.m
with probability p
end for end for
output K 3K
for S m S M.
y a.m
35

---

Published in Transactions on Machine Learning Research (May/2023)
B
Technical Proofs
Throughout this section, we use L to denote the d' x d' identity matrix, Op2 xdz to denote the di x dg zero matrix, and 1/2 E Rdd to denote the vector of ones.
B.1 Proof of Lemma 1
To show the strong convexity, we shall verify the positive definiteness of
A
V=Farr2(w, 3)
2M la(M+))
M7 (F'(w) (w) + MM la
(1 8 I2) M (I Ia) Diag( 2 (1()),..... (((())...VV((((90
A
M
I((M+1)
M (IM & Ia)
(2
2M
Au'
+ A la
Mt (1 2 Ia)
M
2M
(1as & Ia)
2M +
(Im & Ia)
Ap' +
-AA -11 MM
1
M2
&la.
M
A 1M
(2 + 2p() Im
M
M
Note that M can be written a sum of M matrices, each of them having
Au' au'+ A
Mm
M7 ( + 2n¹)
MF
as (m++) (m + 1) submatrix and zeros everywhere else. To verify positive semidefiniteness of Mn: we shall prove that the determinant is positive:
de)( 1 M ((>r' (
(5+ 2p
xP)
2 M (21)
> -22
2 +22')
2
as desired. Verifying the smoothness constants is straightforward.
B.2 Proof of Lemma
We have
4 (MFFIAWW,B)
3M Ta(M+1)
La
M M Ta)
3M Ia(M+1)
(IM 2 Ia)
(Im @ I2) + Diag( 2 f1((), V (((3),..,,,3$((((a)))
M
M
1/' Ia
- [1 & Ia)
M
(IM & Ia)
2y¹
(Im @ Ia)
M
K
1
3
M7
M
@la-
M
M
1M
(x
3
Im
M
n¹ Note that M can be written as sum of M matrices, each them having 3/ 337 at the position (1, 1), at positions m1, (m, 1) and
+
2n
at the position (m, m). Using the assumption μ² < 3
Mi
M
3M
36

---

Published in Transactions on Machine Learning Research (May/202)
it is easy to see that each of these matrices is positive semidefintte, and thus is M. Consequently, '' VFMFLa(W, 8) 3M +1) is positive semidefinite and thus FMFL2 is jointly 5h strongly convex. Verifying the smoothness constants is straightforward.
B.3 Proof of Lemma
Let 2m = 3m + am M w for notational simplicity. We have
22 (M + o
22 2 (2m))
am am(1-am]
72 f' (Fm)
2 5m,( 3m)
M
Mr
Om (1 aam] 2 (2m)
(1 - am) 2 f' (Im)
M
f' ww)
Odxd Odxd
M
an am M
2 V2 (Im)
Odxd
M
am(1-am)
(1 - am )²
M 2
Au' 3I
La
Oaxd Odxd
am (1 (1-am)
+
M
@ (p'Ia)
Odxd
Omm (1 am)
(1 0.m )
M
Ata?
an (1mm)
M
M
Eld.
@mll am
- amm
M
Mm
Next, show that
(1 (1-am)²
0 [1 cm.. 12
Mm 2
2M
(28)
2
For that, suffices to show that
(1 (I=a..) )2
det
Mm
2M
2 0,
(1-0m²
2
which holds since
(1 (1-am) )
0
+ 0
(1 (1-0m)²
(1 am)
a2 amamm am)
det
Mm
2
0
(1-am)
M
2
M
(1
0m)
2
2 (1111
0m )2
2 m M
0.
2
M
Finally, using 28 M times, it is easy to see that
v FAPFLALW 3) 2 21
(mmaa) I((M+1)
M
as desired. Verifying the smoothness constants is straight
B.4 Proof of Lemma 5
We have
M
3
V
(w
11 5
Σ
| m sm (w 3 - fm 3/)2
M
M
3
V Vwlmmuu 3 Vanmm(" ,8")1
M
m=1
37

---

Published in Transactions on Machine Learning Research (May/2023
3 M M
Σ ww 18' m=1
Then, using Assumption I the above display is bounded
3L M
6L
M
11 +
Σ m=1
Dym (ww Bh), ,²)) 3
M
M
m=1
= 6L (f(w", f(w", ((w")8)) + 3) + +32.
which shows
21
To establish
22
we have
M
M
w Fm fm mi )
+
V fm (w 3th ||?
M
M
m=11
m=1
V v fm (w 3:m) - V vwfm(w" 11?
M
2
V Vasm FaSmmuu (u ptm) Vasm(u" 33*) , 1|2
M
(w V (wm ( ,1?
M
Then, using Assumption
I the above display is bounded as
)(
4L
Σ w
Dmm (ww*, (th), (w", ,B)) (0r, 4L (f(w", Bth) ((w", 2(L
M
This completes the proof.
B.5 Proof of Lemma
Let us start with establishing
23
We have
M
E
2
EBlls - -w t 3hh |I Vmmfm (w 3thh 112)
M
V ww cooffmuiii (w 12.
B
Now 23
follows from an application of 21 Similarly, to show 24 we have
M
M
| 1|²
E
M
Furm
M m==
m==
M
M
E
(gw.m
V Vwfue (w
gli
+
Σ
V vwfm fu Bhh
M
MMM
m=1
m=1
M
+
Vofm(ut 31 +
+|| V (wt 3th
M
m==1
0²
M
+
Σ
nr I'
tn gk )
MB
M
m=
38

---

Published in Transactions on Machine Learning Research (May/2023)
o²
M VaSm(un p!)ll
Σ
+
MB
M m=1
Now
24
follows from
22 which completes the proof.
B.6 Proof of Lemma
The proof identical the proof of Lemma E.1 from (Gorbunov et al. 2021] with single difference
using inequality (23 instead of Assumption E.1 from (Gorbunov al. 2021 We omit the details.
B.7 Proof of Theorem 3 and Theorem
We start by introducing additional notation. We set kp =. T, where N+ is the length of the averaging kp+1 1 = Up- Denote the total number of iterations as K and assume that K= kp for some p E N+. The final result is set to be that = w and Bm. = 3 for all m E [M]. We assume that the solution to 11) is w", " ,,.,..,,,8 and that the optimal value is f Let w M 2m=1 w for all k. Note that this quantity will not be actually computed in practice unless At = kp for some E N, where we ck 5B.. S and e
period. Let kp pr +
have whv with for all m [M]. In addition, let eh { et
.......
Let Om ((wm) (8m) TTT 0 = ((w)) T ((B)) 0r = (B7)) and 0* = ((=*)T, (( (T). Let
gt 1 f (w Bhh eth).
(29)
where
B Σ j=l
v fm (w B stn
V Fum(wm Pmm mimmiijua m).)).
gl
We assune that the gradient is unbiased, that is,
E [
V fm (wom 8th
Let
1
gm.. V. to fm (w 3 sth
gm.
Bmm fmn (um Shh el
(30)
B
that ohh ((oth)) (
We update the parameters by
(w (gg = (w 3thh - m7 mm
In addition, we define
M
M
h
1
Σ
Im.1
Σ
|| 1
&
M
M
mm
Then wb+1 w h for all k.
We denote the Bregman divergence associated with fm for Om and Om as
Dim (0 0m.)= = (0m) f(0m)) (V Im (0m), 0m - 0m))
Finally, we define the sum of residnals as
M Σ
p = 1/
w 112
11
1:.11
1
Σ 1 0% 112
(31)
M
M
and let 0 = + MM V V 11.
The following proposition states some useful results that will be used in the proof below. The results are are standard and can be found in, for example, Nesterov (0188)
39

---

Published in Transactions on Machine Learning Research May/2023)
Proposition 1. If the function f is differentiable and L-smooth, then
L || y11..
f(x) - (V
(32)
If is also convex, then
- VV/()) - 2LD2(
(33)
for all z.y. For all vectors z, y, we have
2(x, v) $ <|1== + + v4 > 0,
(34)
- -(,, v) = --211e1f ز
llll +
2 || y/12.
1
(35)
For vectors 01; U2,..., Uny by the Jensen's inequality and the converity of the map: ++ ||]|| we have
n
12
|
(36)
71
n
Next, establish few technical results.
Lemma 8. Suppose Assumption 4 holds. Given {0th ImE(M), we have
M
Eg
1
fm
(bk+1)
fm (0th)
M
M
mm
V fm f
M Σ V ww (0
M
Uk
Jm (000) (0mh); ; V Bmm I' (0
B.n
M
Th.
m L
M
+
Eg
[1I
Ees
211
2
2M
m=m
where the expectation is taken only with respect to the randomness in g*.
Proof. By the L-smoothness assumption on fm (.) and 32 we have
I 1100t1 0 11.11.
fm (m fm (0t)) (V fm (bth gh+1 0h -
2
Thus, we have
nEL 11
++ v
fm (0 fm (0%)) 5 7h (V fm (Oth), h,*) The (V (V Am fm (0%h
1
which further implies that
M
M
1
Σ
Jm (0+++++))
Sm (Ot)
M m=1
M
m=1
M
n2L 11
V
fm 1, t
m
Σ VV
Bm f' 16%h
s/..2) +
M
M
2
m=
m L
fm 11
2M
The result follows by taking the expectation with respect the randomness in gh while keeping the other quantities fixed.
40

---

Published in Transactions on Machine Learning Research (May/2023
Lemma 9. Suppose Assumptions and 6
hold. Given { MmmMM, we have
Be
[11b
Ees.
[llo,m.21
M
C1 M
C2 02+1)
Σ
(0th))
of
+ o3
M
MB
B
S (Gr M
C1 + +2 CC2+11
111
Σ
V
fm (6
+ + (M+C++11
of
of
M
MB
B
where the expectation is taken only with respect to the randomness in g*
Proof. Note that
M
Egg
[1]4
Egg
m
M
m=l
1
Eeg=
(gm,1
10 (m
+
V J m (
M
M
Egg
|1 vnnsm (0th
V
n0 m (0th
M
M
(18)
fm 1113 of +
V w fm (0t)
M
M
m=1
m=1
C1
(ft + of
1
Σ
V W )l1
M
MB
M
where (i) is due to gm being unbiased, (ii) by the fact that eh ek are independent, (iii) is by Assumption 5 and (iv) is by (36). Similarly, have
M
M
M
1
1
Egk [119h,21
Eek [llgtn. - Vem fm (Bth) [
+
V Bm fm (Ah 11
M
M
M
m=1
m=1
m==
C2
of
1
I (eth ||
+
9m fm (6 (oth))) )112
M
B
M
m=1
m=1
The lemma follows by combining the two inequalities.
Lemma 10. Under Assumption 4 we have
M
7K
V
(@t
(6k m)
1
Σ
V
fm (ett)
Σ
V Bm fm (0*), V
Bm (m
M
M m=1
M
m=1
m=1
m7
M
V
fm
(0%
1
V
fm (0t)
+
MmL2
Vk
2
M
M
2
m=1
m==
Proof. By
35
we have
M
1 M
Σ
V
Im (bt)
Σ
V Van (0th
M
M
m=l
m=l
41

---

Published in Transactions on Machine Learning Research (May/2023)
M
Σ
(0th
7
1
Σ
w m (f
w
2
M
M
+
?
Σ
V
fm
)
w frre (mm((0m)))
2
Σ
no Iw.f (O
1jk
1
Σ
V w (0
2
M
M
U
V Vnn (0m)
V Sm 1|2
+
2M
where the last inequality follows from M) (V Bm Sm (0t), V.n.. Sm (0tm))
36
We also have
Uk
V fm (0=)
Th 2
Th V Bm fm (0m))1
V Sm fm (0 - Ben fm (0 11?
2
Thus,
M (V 9m fm (8%),, V 9m fm
V Bm fm (0th))1
9m fmn )1 V
2M
2M
M
+
fJk
VI 8m fm (0(t))
V
9m fm (0% (9t))l I1
2M
7
1
Bm fm (0th)
1
V Bm fm (O
M
M
M
+
7]
V
fm (0 - Vam fm 11?
2M
m=1
Combining the above equations, we have
M
M
-7k
fm
(0
m)
1
V
fm
(0t)
Σ m=1
V
Bm fm (0%h). V Pm (6th)
M
M
M
m=
M
M
1]
2
M
Fm
(6t
m
2
M
V Sm (BE
m=1
m=1
v Sm (0t 1|²
Vm
2.M
1
V
fm (0+)
The
1
V
fm (0k
I1-L2 L
20 11?
M
2
M
2M
7
M
V
fm
(0th
1
V
fm (o
+
L2
2
M
M
2
m=1
where (i) is by Assumption
Lemma 11. Under Assumptions
4 and we have
M
M
M
V
v Sn (0t))
V wwfm (0tt)
Tk
Σ
V Bm fm (0+), V Vin I' (0 (
M
M m=1
M
m=!
1=
42

---

Published in Transactions on Machine Learning Research (May/2023)
-
1 M
fm 6%
8r
7/
1
Σ
fm (6th
+
V
M
2
Proof. The proof follows directly from Lemma 10 and Assumption
Lemma 12. Suppose Assumptions and hold. For Kp
Upr we have
M Σ
[ I A(T - 1)(C +
Σ
n
V
Vmn (
M
t ky
m==
R-1
of( 1
R-
+ odghT 10(-1)((1111 + 1)
Σ
2
+
Σ
B
k=
Note that Vkz 0.
Proof. Note that whr = wm for all m E [M]. Thus, for kp + S k S upr
we have
k-1
k-1
1 - w011 =
M:mm,
w
Σ
nihi'
Σ
n
t= kp
t=
1=
1=kp
Since
# k-1
M1.m11
Σ
nah
M
m=
t=kp
k=
we have
M
1
w²
m9
neh
M
M
k=
2
M
k-1
M
m
Σ
neh
I
Σ
n n
(37)
M
M
Neg
M
R
M
k-1
mh
llg. 11
7
2 11..... 11?
M
M
1==1
m=1
k= kp
Given (m we have
1
Egg
Egg [ [1
M
M
M
M
Σ
Ees [llst
(8t ||2]
+
Σ m=
V fm (8t)
M
M
m=1
M
of B
M
Σ
(C1 + (c1+
|| fm (mk ||
M m=1
M m=1
C1 +1
M
of
V (e*) |1 +
M
B'
43

---

Published in Transactions on Machine Learning Research (May/202)
where the expectation is taken with respect to the randomness in 5 Thus, by the independence of g()), g(8) , and taking unconditional expectation both sides of 37 we have
R-1
M
[ = (T-11 10-1)
Eee
!|?
M
t=kp
m=
k-1
M
k-1 (T o)
< 1) + +1)
Σ
E
V Sm (0 1l
M
B
k=
m=m
t= kp
1-1
- - ()(C++ +1)
Σ
1/E
sm
(Bt
M
t=
k-1
(T 1)
k-1
+ OT 1)
Σ
n
+
B
I=
t= kp
where the last inequality follows Assumption
With these preliminaries, we are ready to prove Theorem and Theorem
B.7.1
Proof of Theorem
Under Assumptions
given {0th Im( it follows from Lemmas 10 that
M fm (
1
E
g+
fm (
M
m
!
fm
(0%)
17
1
fm
(8
nT2
V
2
M
M
M
5" LA
C1
Σ
Jm (0th)
M
M
{
of
0
+ C2 +1
Jdit +
M
MB
B
where the expectation (aken with respect to the randomness in gh. Thus, taking the unconditional expectation on both sides of the equation above, we have
M
M
E
Fm (B+++)
Σ
fm (
M
M
m==1
m==1
M
27
M
27
nI.2
x 7 E
fm
(6k ml
E
Σ
fm (et
+
[v
2
M
2
M
2
m=1
m==1
C1
+ I
+ C2 +
Σ
fm
(f+
M
M
m==
of
+ "
+ C2 +1
M
MB
B
which implics that
44

---

Published in Transactions on Machine Learning Research (May/2023)
M
M
E
fm(O 11
fm
1
Σ
fm (0%))
M
M
m=11
m==
E
Jm (0
1
fm (0th
M
M
k=
172=1
m==
M
27
<
E
1
fm (
(38)
2
M
k=kp
m=l
+
7
(
{
+ nLL
Ci M
+ C2 +
Σ
Up
M Σ
fm
(0
2
M
k=
m=1
+
2
Up
E
[v]]
1 マタ LA {
{G
+
C2 +2+++
dai
+
o MB
+
Up
2
M
B
k=
k=
By Lemma 12 for all kp S k S Ups we have that
1
E [V s - +1)
E
v
sm
(Oth)
M
k= pp
m=l
1)
+ +1j00ail7 1)(C' + 1)(k:
kp)
(k kp)
B
A7 - 1) Σ
E
1
mm
(Bth )
M
A=
m=1
1)²
+ + - ()? + 1)+
B
Therefore, we have
122 Pp
Up -T 11)
M
[ S
Σ E
Σ
m
(0t ml
2
M
k=
k=kp
m==1
Up
17
PTP -1)2 1/
+ 2
3 L' a 1)
Σ
1+
Σ
2B
k= kp
k= k
Combined with (38)
we have
M
E
Sm (0tp+1)
Σ
Jm Enn00 (kk
M
7/ Up
M
27
$
E
fm (6th)
k=kp
+
17 { 1 + 1
(C
+ C2 +1
up Σ
E
1
1
Σ
fm (O+
.M
M
k=
1 PTA {
(Ci
of MB
M +C C22 C2+1
Σ
B
k=kp
Up
1/²
(T
1)2
" T. 2 1)²(C + 11)
Σ
1+
Σ 1.
2B
k=
k=kp
45

---

Published in Transactions on Machine Learning Research (May/2023)
Since we require that
Ci + C2 C22+1 + (T 1)7(1)
1 1+nLX
the equation above implies that
M
E
Σ
Jm (0%)11)
1
Σ
Sm (0%)
M
M
E
Σ
M
Jm (n(0m))
+ 2222L> LA
1
{
{
C2 +02+1) oait
of MB
o2
Σ
M
MM
k=kp
k=
Up
11 1.2 1 (T
1)2
Up
12 - +1)
Σ
1
1.
2B
k=
k=kp
Since we have assumed that K = ki for some p E N+, we further have
M
M
fm (6th) - )
Σ
5m fm (0m)) 8r)
M
M
m=1
M
M
1
fm (0%)
Σ
Sm (6mm)
K
M
M
m==1
m=1
M
1
E
fm (0hh 11)
1
fm (0%
K
M
M
p=0
1==1
m==
D-1
Up
M
S
E
fm (6th)
2K
p=0 k=kØ
m=1
LL {
(Gi M
+ C2
C2++1 +1
odir +
of
Σ1
MB
B
k=0
8-1
Up
17 "' - 1)2
$-1 Up
1 312 - 11)(( +
Σ1
2
2B
K
p=0 kpp
p=0 k=
K-1
M Σ
{
of
02 B
fm (0th)
2 T LA {
+ C2 +1
J +
2K
M
M
MB
k=
m=1
LO - 1)²
L2 L'OounnT () + 1)+
""
2B
This implies that
fm (0th)
M
21E
M
1 DM
sm (00.) {d)
+ nLL {(E) + C2 +1
dut + of of
nn
MB
B
n"
L2 - 1)2
+ 1 2 - + 1)
B
and the proof is complete.
46

---

Published in Transactions on Machine Learning Research (May/2023)
B.7.2
Proof of Theorem
4
By Lemmas
and
12 for kp + +1 k S Up, we have
M
E
Σ
Im
(0+t2)
lr
M
M
A B
Σ m=1
Sm (0 - 5
M
C1 M
C2 + +1 1
M
- 1
E
fm (8
2
k-1
M
BR
Σ k=
E
Fm (0
Ck:
where
AS = 1 THH,
1 mh T.2 - 1 + 1), and
B&
MLL
ddeel 1)(Ci 1)
h-1
oT
1)
Σ
(39)
Ck 2
M
b
k
DEL
C
022+1
of
of
dif
+
C2
+
M
MB
Let
E
1
fm
(0 8rd
M
m=1
C1
D XL
+ C2 +1
and
M
M
= E
V fm (
M m==1
and denote
1p-1 1
Σ mee = O,
k=
0/
C
of MB
o2
+ C2 +1+
Ch2
dif
2
M
Then
a&+1 < Apas + (-1+ Dna)er + BB
Σ
ee +
2
t=
for all kp S s Up. Under the conditions on and t, by Lemmas 13 and
14
we have
au S
II k=
Ds
ak,
+
II
A
Cup
(40)
k=
47

---

Published in Transactions on Machine Learning Research (May/2023)
Let 2 (k: + b)3, where b b= Br + 1. Then
2k (1 ( + 6)8 (1
1
Ju(k 6)3
u(k
1)(k: 6)2 2 u(k:
b- 1)3
2k 1
b
1k
+
7K
and, thus,
Up
Up Pp-1 II vimb++1
Up -1
Z0p
II
A
Z0p Dos
A
20p-1
II
A
S
2k
up
Mop
Mop
Mop
T]/
kmm++1
vin
Note that Up + 1 = kp+1.
Plugging the above inequality into
40
we then get
Zep 0Rp11
2kp
2k ?
Ck-
ny
T]kp
k=kp
Since we have assumed that K kp, thus have
Up-1
K-1
2 1
OK
Zop-1 akg S 2kp-1 akg-
0g
Ck-
(41)
785-11
1/
1/c
130
k=0
Since, for hp S S Up, we have
oT
22 - + +1)
Σ
Σ
Ck 2
Th
kmk
k
L
(
+ C2+1)++
of
of
+
dif
2
M
MB
B
(T 1)2
|
11) + of
Ca
2
B
m T
CCi
CC2 +C2+1)
of
of B
+
Oii
+
2
M
MB
we also have
K-1
[T - 1)2
{
a K-1
Σ
Ck
5
coueCC 1)
Σ
z 2
7/k
2
B
k=0
k=0
I
/ C1
+ C2 +1)
of
of K
+
dif
+
Σ
T (42)
M
MB
B
Assume that k pr + r, where 0 05rsT-1 1. Then
t
r ++ b+ ++
as we have assumed that B > 1. Thus
((1
2
T +
2 2
T
and
K
K-1 1 112
k ++
)
4K
[ T + b
k=0
k=o
48

---

Published in Transactions on Machine Learning Research (May/2023)
Next, note that
K-
K-1 1 Σ
K(K + 26)
(k + b) -
(43)
# k=
24
Combining equations
we have
M
(
E
fm
M
$
B3
1
Σ
fm (mm) 8r
2T (T 1)2K
2 (air(C + + of
KK + 3T)3
M
1 + 3T)3
B
LK(K +2) +
(C
+ C2 +1)
+ of
02
4n²(K + BT)3
di
M
MB
B
which completes the proof.
B.7.3 Auxiliary Results
We give two technical lemmas that used to prove Theorem 4
Lemma 13. Consider the sequence {au}a, Skyss,, in the proof of Theorem that salisfies
ak+1 S Apas
Th (-1+ Dnkee + Bk
Σ
nee + ck.
t=
where De. Bk, and es are defined in
39
Suppose the sequence of learning rates (ma} satisfies
Mp D-1
(44)
2Br Di,
Thpp -1
D+
(45)
:
2 (Bop
Σ Up-1 -1
-1 By BBliEsH
k
Map S
D+
(46)
T Ai
Then
14.
aep+15 <
II
Ds
akp
+
A
Cup'
kmm Ky
femm ky
Lim R++
Proof. We start by noting that
ar,+1 S Do avp
ney (-1+ Depp 2
Bep
Σ
n ck + Cup
nec
k=
#--1
$ Ao avp
+ B k-
meen + Copt
where the last inequality is due to
44
Thus, we have
01p+1 S Av, + Bug
Σ
me + Cap
k=
49

---

Published in Transactions on Machine Learning Research (May/2023)
2p-2
any on + Bup
Σ
eE + 110-1111111 + Cop
k=
< A
1,,-11 (-1 + Dmp 11op-11ee e)vv-11 Bo,-1 - Σ Avp-1 a0p 11
ne Cua-1
k=
+ Boy
es Vog 11 Cup
T1pp-1 A Up
BB 1/:-11
Dup pp-1 Avp
-1 DMu 1 +
c
Dup
Up -
+ (Ar, -1 + BuG,)
Σ
2 + (4 Cr,- + cop.
k=
By 45
we have
2B 2B, 50
-1 + Dmu
11pp-1
Dvp Up.
Therefore,
Pp-2
0pp+1 E A.,
A avp-1 + (A B + Boy))
Σ
nee + (Ar, + Cup)
k=
Under the assumptions on Tık, repeating the process above, we have
M/
0upt1
II
A
akp+1
+1
A; Bep+1 +
II
A
Bip+2 + .... + Doy Bug-1 + Bup
2
ekp
k= +2
kkpp
Up
II
A
Ck
k=
M=*+1
Since
Mkp (-1+ DiTK, + Chp'
akp+1
< Dkp axp
+
2
combining with 466. the final result follows.
Lemma 14. Let 7 (u(k Br + 1))- where
12LL
C1
+ +++++1 2, 2L2 + 1) M
3 max
P
112
and
max ((2 - -4,0}
T >
f 32- 1)/
Then the conditions in Lemma 15 are satisfied for Ty for all k 2 0.
Proof. Let Ag and By be defined as in hand side of 146 we have
39
Since A < 1 for all k, after p-th communication, for the right
2 Brp + "0 kj=k, +1 By Ii 4, -1
D
- A;
50

---

Published in Transactions on Machine Learning Research (May/202)
-1
2 (Bp + + B3 1111
D
I1 Ai
2 (Bop +
2 B3 I1 A.)
Upp- 11
D+
k2 Ai
Thus, by induction, we have
BB,, Bu, + +z By B1112 41)
2
D +
11 Ai
2 (B, + Σ 1-1
2zb B3 Il A.)
+
11 A:
(47)
....
2B D
-1
< D) +
<
D-
As k increases, we have that 7h decreases, A increases, and B₁ decreases. Thus, for 1 S k: K, we have
nK S 7T--1 S ..... m.. On the other hand, we can lower bound the right hand side of (66
D+ + (Bn, Ba, +
1pp- Lj=k,tt By B1IT 4.)
-1
1 A;
2 2B1 + + 5
Lj=kpt1 B1 IT= Ax)
2
D+
I A
2B1
(1 Σソ 1= A
(48)
D
+
11-1
2B1
1 Σ 1p-1 jj= 1
2
D+ +
1--1
D 2B (T 1) -1
A T-1
1f
111 2
(49)
D +
(7-11
then the conditions on stepsizes in Lemma 13 are satisfied for all me by combining 47 need to show that 44 is satisfied to complete the proof.
49 Thus, we only
To that end, we need to have
2B (7 - 1) D+
TI 511
A
C1 M
+ C2 C2+1) + ML - -))(( +1)
m1 1
(1 (1-711)
51

---

Published in Transactions on Machine Learning Research (May/2023
C M
+ C2 C2 (1 (1 - (1 [1-mu))-
- xL
To satisfy the above equation, we need
[L + C +22+))11-mm)))
< (2m1) (1 7111)
(50)
1)
S (2m)) (1 11114)=-11
Note that 1/ = 1/(m(3r + 2)). Thus, to satisfy the first inequality in 50 we need
[G ++++++)
Ci
1 - = 2).
2AL
Since + 2 113 + 2), the condition above follows
2AL
C1 M
B 2
C2 +1+ -2
(51)
Next, to satisfy the second inequality in
50 we need
s (1 m/1)-1
2T22((11 +1)
7 T-
2
Br +2
r-1
S1.
122
Br + 2
B7 +
Since
BT +2 r-1
= -11
T-1
(T- - 1)/(3r + 1)
7-1
T 1
1
S Sexp
< e
Br +1
3r+1
T-1
Br +
need
2L2X(CI 11
T--1
e 1
112
+
Let 222 1)/x2. Then the above equation is equivalent to
(3² - - + 2(B + ve F) + (4 - ved 2 0.
First, we let 32 - ver > 0 or equivalently
32
2L 2L2 + 1)
(52)
42
Then we need to be large enough such that
2(3 + vet) + v A(B + vett2 max 4633 vet ((1 ve )
2 vve)
Since va² + < la| + |bb for any a. b E R, the left hand side is smaller or equal to
max 1/e 4,07
max {(2L2A(C + 1)/13))1/A 4.0]
B - vev
8 (2 11/
Therefore, we need
max
4,0}
(53)
- -2T2XC +1)
The final result follows from the combination of
51
53
52

---

Published in Transactions on Machine Learning Research (May/2023)
B.8 Proof of Theorem 6
Let N' TR - R be the Nesterov's worst case objective (see), i.e. h'(y) プリ Ay - E y with tridiagonal A having diagonal elements equal to c (for some 0) and offdiagonal elements equal to 1 1 The proof rationale is to show that k-th iterate of any first order method must satisfy ll s l and consequently
Nesterov's worst case objective. (Nesterov 2018
VK -1 +
11 1²12
||
(54)
where y" = arg yER h1(v),
Amax((A Amin (A)
Finite worst sum objective h - + R, h(2) وÿ= hz(2) is such that hj corresponds only j-th block of the coordinates; in particular if = = [21, #2, ..........,.................... Zn]i 21, ,,, E g we set h,(z) = h'(z)). It was shown that to reach 2 < ==*===
objective. (Lan & Zhou 2018) The construction of the worst finite-
requires at least Ω ((n nf log !)
iterations for L-smooth functions hy and
m-strongly convex h.
Distributed worst case objective. (Scaman et al. 2018 Define
dx(2) 1
(4 [=|1=112 + 0 (c]2+ M1²))
1
g3(2) = ....))....
= -.. = = 2(M - 1)
(c1ll2|f
+ + M2²)
1
1
0
1 0
1
where Mi is an infinite block diagonal matrix with blocks
and M2
0
and
0
1
0
M₁
0
C1, > 0 are some constants determining the smoothness and strong convexity of the objective. The worst case objective of Scamaan et al. (2018) is now g(z) = M Em= (2).
Distributed worst case objective with local finite sum. (Hendrikx et al., 2021) The given con- struction is obtained from the one of |caaaa et al. 2018 in the same way as the worst case finite sum objective (Lan & Zhou, 2018) was obtained from the construction of Nesterov (2018). In particular, one shown that such a construction with properly chosen C1 C2 yields a lower bound on the commuicatiio complexity of order 2 (V and where C a smoothness constant
would set gm.. Im (z)) where = [ ,,)...,,n]] Next,
the lower bound on the local computation of order St ((1 of 9m.j L is a smoothness constant of 9m(2)= = Σ 1 (2) and is the strong convexity constant of g(=) = M Em=190 (z).
D. log )
Our construction and sketch of the proof. Now, our construction is straightforward we set g(w) h(8m) with g, h scaled appropriately such that the strong convexity ratio is per Clearly, to minimize the global part g(w), we require at least 5 (v 4" log log iterations
fm (w, Bm))
Assumption
1
and at least.
Q ((n+
!) stochastic gradients of g. Similarly, minimize h, we require at least stochastic gradients of h. Therefore, Theorem 6 is established.
Q (n
nus
log!
8This is for the strongly case; do similarly. We have lifted their construction the dnfintte-limensionall space for sake simplicity. can get similar finite- dimensional results.
53

---

Published in Transactions on Machine Learning Research (May/2023)
B.9 Proof of Theorem 8
Taking the stochastic gradient step followed by the proximal step with respect to v, both with stepsize 1). is equivalent to (Hanzely et al. 2020b):
M
M
w w 1) Pw
Σ
V Jw (wr, (w, Bm)
1
Σ
V Vw Jm. (
M
w.p.
V F (w ())),
3
3m
di fm (w/ .
(55)
wt V F ,3)),
w.p. ps:
8 = 8m
/ 1
(VDsm. (w, 9m) Volm,suu ( ,B,)) Volm(w' (
Let x = [w, .2...., BMl, x² = [w', ,'....,,rr.l. The update rule 55 can be rewritten as
x = x - -(()) VF(z))
where g(z) corresponds the described unbiased stochastic gradient obtained by subsampling both the space and the finite sum simultancously. To give the rate of the aforementioned method, we shall determine the expected smoothness constant. To achieve that, we introduce the following two lemmas.
Lemma 15. Suppose that Assumptions 1
hold. Then 2
El((((>) - -()") VF(=)) - VF(x)) < 2CDr(z,))
where L = 2 max
C" C* Pw
Proof. Let d3 = 2m dm- We have:
(x(() g(x²) + -
S Bl]g(=)) - g(x')11
M
2
= B
Pw
1
Σ
(V w (w, - Vwrmmsl ( 15=1 =1
M
m=1
M
+ M
Elp 1 V VmmJ(W 3m) Pa V Smms , 1
m=1
M
P. E
(V Var Amm V (w Bmm)) 15=1
M
m==1
A
+ PB
B V Sm (w, (w, v Sms 11 (== c=
M
P pdoxdo
((F((z) - (F)(
(Fj(z) - (F)()'))
0
P Idoxdd
L L
EA max
Dr)(x,z1))
Pie pa
L L3
4 max
DF(x,z'),
PB
where (+) holds due to the (L"h -mmommothsssss of F3 (from Assumption and Lemma 16
54

---

Published in Transactions on Machine Learning Research (May/202)
Lemma 16. Let (x, y) Bdatdy R be (jointly) convex function such that
((, I and (aH v) Tyg
Then
v2H(2,0) 2 111 Lyb
(56)
and
Dn((2,u),, (x'v/)
(H) (H(I')/)
( vH('',))) (57)
Proof. To show
56
observe that
2 L 0
2L - V2 ((.
-V B.y H
( xz, v)
(HH(I,
L
H(,,(
2L V2. (
R.a (z,
V.a H (x,
V2 ((r,)
H(x,
0.
Finally, we note that 57 is a direct consequence of 56 and joint convexity H.
We are now ready to state the convergence rate AFV.CD.PFL Theorem 9. Iteration complezity of Algorithm with
1
1
4C
02
2' 7
max (211, 401/n}'
0g
V mp,
and 01 min
2
nu max
2
is
C"
L
max
Pi
1
log
Setting Pa 20 yields the complexity
((:
o
Lw
+ L3
1
+
log -
PM
Proof. The proof follows from Lemma
15 and Theorem 4.1 of Hanzely et al. (022b)), thus is omitted.
Overall, the algorithm requires
o
L +
C
[og (pn pw)
PM
55

---

Published in Transactions on Machine Learning Research (May/200
communication rounds and the same number of gradient calls w.r.t. parameter Setting
have
1
LH + L
[ogg !) (on + +ww) =
L
L3
[log =) pm
p
P
pu
(Lw + LO)
log 1
2
+
14
nLw
log -
2 11 +
which shows that Algorithm
3 enjoys both communication complexity and the global gradient complexity of Pa yields personalized/loca llcal gradient complexity of
order O n +
nc
log
Analogously, setting p
order O
n +
log!
56


Reviews:
[{"review_id": "ZGj99jkdaN", "reviewer": "Reviewer_AYaN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The unified personalized federated learning (PFL) framework is clear. Given there are many PFL works, it is nice to have such a unified framework. \n2. Although the proposed algorithms are not new, I appreciate that the authors spent time proving that they can recover the best-known convergence rates. \n3. The derivation of the lower complexity bound is also very important, and it is interesting to see that the Accelerated block Coordinate Descent algorithm is actually already optimal. \n\nWeakness:\nI think compared with the theoretical results, the numerical experiments are relatively weak. For example, the authors only use tiny real-data sets (MNIST, KMNIST, FMNIST). Also, although the authors have theoretically proven that they can recover best-known optimization guarantees, it would be great if they could provide numerical comparisons. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this work, the authors suggest a unified framework for personalized federated learning, i.e., an empirical risk minimization problem with local variables. They show that many existing works in personalized federated learning satisfy this framework. They further adapt three existing optimization algorithms to solve this personalized federated learning problem. Moreover, under strong assumptions on the objective (strong convexity and smoothness), they show that their adapted algorithms can recover best-known optimization guarantees, i.e. bound on the communication rounds. Some numerical experiments are provided to support their claims. \n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Based on the weakness points listed above, I have the following suggestions:\n1. use larger data sets such as CIFAR10\n2. compare with some existing personalized federated learning algorithms", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3syd3gnvOl", "reviewer": "Reviewer_D89j", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \nThis paper is generally well-written and easy to follow. The proposed framework provides a unified view for FL optimization and analysis, which covers many existing problems as special cases. Moreover, it also leads to several new problems, which may of independent interests. The algorithms proposed in this paper, such as LSGD-PFL, although are variants of existing algorithms, are novel and significant enough to me, as it is not obvious (for me) that the right convergence rate can be obtained easily by simply minimizing the parameters simultaneously. The authors also did a very solid work in the experiment section and many results are provided. \n\nWeakness:\n\nPrevious work focus on optimizing local parameters or global parameters separately, and it is not very surprising to me that we can come up with a general framework which tries to optimize all parameters and thus can recover previous problems as special cases. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "1. This paper proposes a general objective function for personalized federated learning, and the main idea is to optimize the global parameters and local parameters simultaneously, while most of the previous work only focus on some parts of the problem. The proposed general objective function can recover various existing FL problems as special cases, and it also leads to several new/more challenging problems.\n\n2. The authors develop several optimization methods for the proposed general objective function. The first algorithm, LSGD-PFL, is a variant of LSGD, and the main difference is that the local servers also optimize the local parameters via SGD. The authors prove that this algorithm enjoys minimax optimal bound. The then propose accelerated algorithms based on variance reduction. \n\n\n3. Finally, the authors provide experimental results to demonstrate the effectiveness of the proposed objective function and algorithms. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Equation 8, 12, 15, 16, 17, 19: I wonder if it should be sum_{m=1} instead of sum_{i=1}, or I missed something here?\n\nFor the new personalized FL objectives, it would be great if the authors can add more discussion and justify why they are meaningful with some real-world applications.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "vd6wklgnAn", "reviewer": "Reviewer_qSw9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper is largely clearly written and a good amount of research is done into finding algorithms and formulations that fit well within the proposed framework.\n2. The calculation of the global and local smoothness constants for different formulations is clear and places the previous work very well in context of this framework.\n3. Convergence guarantees are provided for the proposed algorithms and it is made explicit when they are or are not minimax optimal.\n\nWeaknesses:\n1. Most of the theorems are simple modifications to previous work, and the key contribution seems to be observing the similarity in a lot of previous work and proposing a natural generalization which encompasses a lot of the work. Although it leads to a clearer understanding, I find this contribution to be more pedagogical rather than it being research.\n2. Some conditions are just stated as complex equations, and no example values are provided after the theorem illustrating reasonable values for the variable where these assumptions may be satisfied (e.g. eqn 20 of Theorem 3, and in Theorem 4). I think this is a major weakness for two reasons - one cannot easily verify whether there is any setting of parameters which satisfies the conditions and still gives reasonable convergence and other, while implementing the algorithm, it is important to know what you can set the algorithm parameters as which is hard to check with complicated equations.\n3. For SVRCD type algorithms, the setting of all hyperparameters is not defined in the main body and it is only set in the proof. It is important to know what hyperparameters get the rates without combing through the proof both for a reader to implement these algorithms and run sanity checks.\n4. ASVRCD achieves minimax optimal rates in terms of gradient complexity for shared variables and personalized variables for different parameter settings, thus claiming it is minimax optimal is misleading because its two *different* algorithms that are minimax optimal in different aspects.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a unified framework for studying optimization aspects of many personalized federated learning objectives and corresponding algorithms. They work under the formulation where each users' objective function depends on two sets of variables --- shared variables ($w$) and personal variables ($\\beta$), and the global objective is to minimize the average of each users' objectives. Many of the proposed personalized FL algorithms fit in this framework. The main contributions of this paper are to recover known guarantees of these algorithms which fit in this framework and obtain (as a corollary to the guarantees of their framework) a few new guarantees for previous work where optimization guarantees were not provided. They also provide lower bounds on the number of gradients required for both the personal and shared variables and on the communication complexity, by a simple combination of previous results to construct the hard instance. Lastly, they provide an accelerated and variance reduced version of the basic local SGD type algorithm to achieve minimax optimal sample complexity both in terms of number of gradients of the shared and the personal variables, though not both simultaneously.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Minor points:\n1. \\hat{f} is not defined in page 3 section 1.2, under local objectives.\n2. In table 2, instead of writing equation 4,5, etc. it would be more fruitful to write algorithm names and paper references. Same with table 3.\n\nMajor points:\n1. The weakness points 2 and 3 mentioned above, I would like to understand the theorem statements clearly to evaluate this work. Not just the parameters settings but examples showing when they are reasonable would be helpful.\n2. I think the claim that this is a unified framework for all of personalized FL is a bit too strong, equation 1 is one way to combine all the objectives of all the users, certainly not the only or the best way. I'd recommend changing the title to make it more realistic, currently it sounds like it is the paper which encompasses all of personalized FL.\n3. Weakness 4 mentioned above, I don't expect technical changes, but upfrontness in writing in the earlier parts of the paper.\n\nA point I didn't fully understand, maybe I missed it:\nThere is a lot of mention about reparameterization of w space being important to make LSGD work, but I don't see where the reparameterization is happening in the algorithm. Can you shed some light on where this is happening?\n", "broader_impact_concerns": "No concerns for broader impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This main contribution of this work is to proposes a unified framework for studying optimization aspects of many personalized federated learning objectives and corresponding algorithms. Many of the proposed personalized FL algorithms fit in this framework. The paper recovers known guarantees of these algorithms which fit in this framework and obtain a few new guarantees for previous work where optimization guarantees were not provided. They also provide some lower bounds. They further provide accelerated and variance reduced versions. 

The reviewers found the paper well written and correct. Reviewers also appreciated the proposal of the unifying framework which helps the community. The reviewers found limited novelty though and found the experiments a little weak but were all overall supportive of acceptance. 
Decision: Accept (poster)