On Sample Optimality in Personalized Collaborative and Federated Learning
Authors: Mathieu Even
Laurent Massoulié
Kevin Scaman
Venue: NeurIPS 2022 Accept (2022)
Keywords: Stochastic optimization
personalization
collaborative
federated

Abstract: In personalized federated learning, each member of a potentially large set of agents aims to train a model minimizing its loss function averaged over its local data distribution. We study this problem under the lens of stochastic optimization, focusing on a scenario with a large number of agents, that each possess very few data samples from their local data distribution. Specifically, we prove novel matching lower and upper bounds on the number of samples required from all agents to approximately minimize the generalization error of a fixed agent. We provide strategies matching these lower bounds, based on a gradient filtering approach: given prior knowledge on some notion of distance between local data distributions, agents filter and aggregate stochastic gradients received from other agents, in order to achieve an optimal bias-variance trade-off. Finally, we quantify the impact of using rough estimations of the distances between local distributions of agents, based on a very small number of local samples.

gradient filtering On Sample Optimality in Personalized Collaborative and Federated Learning
Mathieu Even', Laurent Massoulié 1.2, Kevin Scaman'
Inria Paris Département l'informatquee de I'ENS, PSL Research University
Microsoft- Innros Joint Center
Abstract
In personalized federated learning, each member a potentially large set of agents aims train model minimizing its loss function averaged over its local data distribution. We study this problem under the lens of stochastic optimization, focusing scenario with large number of agents, that each possess very few data samples from their local data distribution. Specifically, we prove novel matching lower and upper bounds on the number of samples required from all agents to approximately minimize the generalization error of a fixed agent. We provide strategies matching these lower bounds, based approach: given prior knowledge on some notion of distance between local data distributions, agents filter and aggregate stochastic gradients received from other agents, in order to achieve an optimal bias-variance trade-off. Finally, we quantify the impact of using rough estimations of the distances between local distributions of agents, based on a very small number of local samples.
1 Introduction
central task in federated learning [31, 40] is the training of common model from local data sets held by individual agents. A typical application is when users (e.g. mobile phones, hospitals) want to make predictions (e.g. next-word prediction, treatment prescriptions), but each has access to very few data samples, hence the need for collaboration. As highlighted by many recent works (e.g. Hanzely et al. [28], Mansour et al. [39]), while training a global model yields better statistical efficiency on combined datasets of all agents by increasing the number of samples linearly in the number of agents, this approach can suffer from a dramatically poor generalization eтror on local datasets. A solution to this generalization issue is the training of personalized models, a midway between shared model between agents and models trained locally without any coordination.
An ideal approach would take the best of both worlds: increased statistical efficiency by using more samples, while keeping local generalization errors low. This raises the fundamental question: what is the optimal bias/variance tradeoff between personalization and coordination, and how can it be achieved?
We formulate the personalized federated learning problem as follows, studying it under the lens of stochastic optimization [5]. Consider e No agents denoted by integers & & N, each desiring to minimize its own local function f. R2 + I. while sharing their stochastic gradients. Since only limited number of samples are locally available. we focus on stochastic gradient descent-like algorithms, where agents each sequentially compute stochastic gradients o such that E lot V,, In order to reduce the sample complexity, i.e. the number of samples or stochastic gradients required to reach small generalization error, agents thus need to use stochastic gradients from other agents, that are biased since in general E [g]]] A V. Our algorithms are based on gradient filtering approach:
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

upon reception of stochastic gradients (o");; agent i filters these gradients and aggregates them using some weights X3 into Σ; ^gol. in order to achieve some bias/variance trade-off.
1.1 Contributions and outline of the paper
In this paper, we consider an oracle model where at each step k = 1.2...., sample according to their local distribution. We aim computing the number of stochastic gradients sampled from all agents, required to reach small generalization error, in terms of biases (distances between functions or distributions), regularity, and noise assumptions. The oracle model, main assumptions and problem formulations are given in Section 2. Our main contributions are then as follows.
.,, all agents may draw
(i) In Section 3 we prove information theoretic lower bounds: to reach a target generalization error E > for fixed agent no algorithm can achieve a reduction in the number of oracle calls by a factor larger than the total number of agents E-close -in suitable sense- to agent i.
(ii) We next study a naive strategy based weighted gradient averaging algorithms, coined all-for- one, that matches this lower bound, at the cost of high communication and storage requirements.
(iii) We then propose in Section 5 parallel extension of the simple weighted gradient averaging algorithm that yields an efficient algorithm for collaborative generalization error minimization problems. In this algorithm, agents compute stochastic gradients at their local estimate, and broadcast to other agents who may use these to update their own estimates. For x (a4,-.. .,. .xy where at is the local estimate of agent at iteration k, updates of the ALL-FOR-ALL algorithm write as:
x x² - n
where g²= (9" ...., gxx for an unbiased stochastic gradient of of function fi, a step size 1), and a carefully chosen symmetric matrix W. Agent thus uses stochastic gradients that are doubly biased, as gradients of a "wrong function" fy instead of fa computed at a "wrong location" = instead of x... Interestingly, note that the ALL-FOR- ALL algorithm is not gossip algorithm per se (see e.g. [45]), since the matrix W is not doubly-stochastic: gradients are not aggregated with weights that sum to 1. Moreover, W/ depends on the distance between local agents distributions, and thus requires either prior information on the local distributions, or estimating these distances as a pre-processing step.
(gf
(iv) We finally study in Section 6 the impact of estimating, based very limited number of samples, the matrix W to use in the ALL-FOR-ALL ALL algorithm. Under a mixture model assumption on the agents, we obtain that for bounded - up logarithmic factors number of samples per agent, any arbitrary small generalization can be reached, with an optimal collaboration speedup in terms of the number of agents in each mixture of the mixture model.
1.2 Related works
Federated Learning is a paradigm in machine learning where training is done collaboratively among several agents, taking into account privacy constraints [31, 36, 40, 51]. A central task is the training of a common model for all agents, for which both centralized approaches orchestrated by a server and decentralized approaches with no central coordinator [44] have been considered. The algorithms we propose in this paper are well suited for decentralized implementation.
As observed in Hanzely et al. [28], training a common model for all users can lead to poor general- ization on certain tasks such as e.g. next-word prediction. To improve both accuracy and fairness, personalized models thus need to be learnt for each agent [38, 43, 54). Approaches to personalization include fine-tuning [10, 34], transfer learning techniques [19, 49, 51], using shared-represee reiredddrppreentationn models [11]. Personalization in FL can also be formulated
the training of local models with
regularization term that enforces collaboration between users [28] or with meta- metaa-earning approach [9, 25, 30J. We refer the interested reader to Kulkarni et al. [37] for broader survey of Personalized Federated Learning.
While the goal of personalization is to minimize local generalization errors, the above cited works do not provide theoretical guarantees over the sample complexity to obtain small local errors, but instead control errors on regularized problem, in terms of communication rounds or full gradients used, and not in terms of samples used. Deng al. [14], Mansour et al. [39] among others provide generalization errors under statistical learning framework that depend on VC-dimensions and

---

on distances between each local data distribution and the mixture of all datasets. Donahue and Kleinberg [16, 17] study the biri-nariance trade-off between collaboration and personalization for mean estimation in game-theoretic framework. Beaussart et al. [3], Chayti et al. [8], Grimberg et al. [27] also concurrently frame personalization as a stochastic optimization problem with biased gradients and are the works closest to ours. They consider the training of a single agent with biased gradients from another group of agents dedicated to this agent, and obtain performance guarantees in terms of distance between individual function fi and the average N N fz. In contrast, we obtain more general performance bounds based on distance bounds between all pairs of functions fi, S3 (or equivalently, pairs of local distributions), the case where all agents desire to minimize their local objective; our "bias assumption" is also milder. In addition, prove matching lower bounds, and study under a mixture model the statistical efficiency of our approach.
Concurrently, [15] use similar dissimilarity notions (Integral Probability Metrics, albeit with respect to different function spaces) to show upper-boune that closely resemble ours of Theorem 3, when training over mixtures of distributions (without algorithmic solutions as the all-for-all algorithm), together with insights on who collaborate with for agents. These results, obtained in a different framework than ours (hypothesis and VC-dimension bounds, rather than our stochastic optimization framework), fall into the frame of our lower bound (and match it up to constant factors), form an orthogonal line of work.
Finally, data-heterogeneity has long been a challenge Federated optimization, for instance noted in the analyses and performances of the Local SGD algorithm [33, 53]. Many algorithmic solutions have been proposed to counterweight this effect [32, 42] (non-exhaustive list). Yet this line of work studies the effect of hata-hhterogeeeitty on the convergence guarantees of FL algorithms that train one global model, irrespectively of the local generalization property of this trained global model. Our work is orthogonal, and focuses on data-heterogeneity as a challenge for statistical meaning (local generalization) of the model(s) trained, as opposed to related works that study data- hata-heterogeneity as challenge in distributed or federated learning to design fast and scalable algorithms. Putting into perspective these two views on the challenge data-heterogeneity FL. seems however necessary, and stresses its importance.
2
Problem Statement and Assumptions
We now detail our objectives and the necessary technical assumptions. We consider general stochastic gradient methods and formulate problem, assumptions and algorithms accordingly.
2.1 Problem setting
Let D; for < N be probability distribution on set E (agent i's local distribution, not its empirical distribution), e: Rd x = - I loss function. We assume that the function fa that agent i aims at minimizing is the generalization error on agent i's local distribution:
f(() = E,,-D, [f(x,
x E
We coin this problem as collaborative generalization error minimization (GEM). every iteration k 1,2,... agent may access unbiased i.i.d. estimates g: (x: f((x):
(x)
= V,((x, e DD, ZER 1
Counting the number of stochastic gradients used in the whole of agents reach precision 8 for f; thus reduces to computing the number of samples required from all agents to obtain local generalization error for agent i. To specify the information shared between agents via access to stochastic gradients, we define the following oracle, that lets at every iteration all agents sample a stochastic gradient. After K oracle queries, each agent will have sampled K stochastic gradients for a total of N K in the whole set of agents. Let { {EE) ..... ck k > 0 sequence of i.i.d. random variables of law D2 ... D Given the initial shared knowledge So. at iterations 1,2.....
1. For all < < N, agent samples E/ chooses some U/ E .Rd as a - function.
The shared memory is extended: St = S (o) <<jEN N).
3. Agent j outputs z S4-measurable function.
3

---

For fixed target precision E >> O, the objective is to find, using T& samples from all agents in total corresponding K T oracle calls ,, models with local generalization error E. Throughout the paper, we assume that each functiion fü minimized over E2 and denote by x such minimizer. We further consider the following two standard assumptions.
Assumption (Noise). There exists o² > such that for all <i< N and x E R
ES,-D, [ve(z. V d².
Assumption 2 (Regularity). Functions Ia ju-strongly convex and L-smooth [7].
2.2 Distribution-based distances
We first introduce extensions classical Integral Probability Metrics (IPMs, [47]) to multivariate functions, i.e. pseudo-distances the set of probability measures parameterized by set H of functions, fixed the sequel.
Definition 1. For H a of functions from E to Rd and D, D' two probability distributions on we define:
dn(D, sup REH
where & ~ D and L D'. du is pseudo-distanee on the set of probability measures on
This family of pseudo-distances contains a large number of standard distances between distributions, including total variation (with the set of 1-locally bounded functions, functions that send any ball of radius 1 in a ball of radius 1), the Wassertein distance (with the set of I-Lipschitz functions), maximum mean discrepancies (with the unit ball of a RKHS), or even simple distance between means of the distributions (with the set of 1-Lipschitz affine functions), developed further in Section 6.
Assumption 3 (Distribution-ben basedd dissimilarities). For some non-negative weights (bij) we have dH (D,, D2) & big for all 1 & i,j & N. We further assume that either of the following holds.
1. (Weak dissimilarities). For all 1 < EiEN, E ( ()) H.
2. (Strong dissimilarities) For all E Rd, RREERREEEEEEEE (EEE V E H.
The "weak dissimilarities" assumption is of course easier satisfy than the "strong" version, and our results will ultimately depend only on the weak assumption. Under Assumption 3 (weak version) and Assumption 2, we have (x;)) ) fz < /2p)) which motivates our use of distribution- based dissimilarity assumptions.
Notation: in the rest of the paper, variables T denote the number of stochastic gradients o sampled (or data item sampled from personal distribution) from all agents, while variables k or K denote the iterates of the algorithms (or equivalently the number of oracle calls made).
3 Information-theoreti lower bound on the sample complexity
In this section, we prove lower bounds on the total number of stochastic gradients required from all agents, reach e-generalization for given agent. Our lower bounds apply collaborative GEM, i.c. functions (fi)ieieN of the form (1), for shared loss function and user distributions DI...., .....,,yy Dx.
An oracle ø IR Xxd + I random function that answers some d(x) where is an information set, for every query æ E Nxd We adapt the definitions of Agarwal et [1] of sample complexity for SGI) to our personalization problem. Formally, the first-order oracle we defined in Section 2 and that we write as (((D)) (D,,)==..... E) for shared loss function and user distributions Di...., Dx. returns for r E Nxd,
1 ((.)),, = (1, Es. E(x, Ei), of (2:)) 1
where & ~ D;, Given distributions and a loss function ((D:):, f), we denote by M the set of all methods M = (Mx) for any K > 0, MM makes K oracle calls from oracle ((D))). (while using T = NK stochastic gradient samples from all agents), and returns -. E gd for agent

---

i as a measurable function of the K oracle calls. For set D of couples of distributions and loss function (D) defining functions (fi)SSiNN, we are interested in lower-bounding:
inf sup MEM (P)),
K (M. ((D)))))
where Xi (M, ((D)), is the number of oracle calls required to reach generalization error 0 for agent i, and writes as:
K (M, (())).)) inf K E N'' such that E [((aa) min f((x)
& <E)
zER"
We now define the set D we consider for our lower bounds. Let (b.y) be non-neganiee non-negative weights that verify the triangle inequality namely, biy & + for all i, k and let r, μl, L, O. (r, b, a)) is the set of all ((D)) f), such that the functions parameterized by these tuples of distributions and shared loss function verify Assumptions 2 and 3 for o², J. > 0 and b, such that | < for all 1 & i & N, and such that f((2)) - f((;;) & (2p). We use the notation a(-) = (2(((-)) for 3C > 0 such that a(-) > Cb(-).
Theorem (IT lower bound). Let (0, 1/16), (biz) verifying the triangle inequality, T,0 > Assume that the function set H contains the all 1-Lipschitz affine functions and that du & drv. For any E [N.....N::
(M, =Ω (120
{=
inf MEM
sup ((D)), (DD)),,))D) w=1/ (r.bo))
N
where ( = E, 1 (0] (4nz) is the number of agents verifying big &
The proof of this lower bound (Appendix B) builds on lower bounds based on Fano's 's inequality [21] for stochastic gradient descent [1] or for information limited statistical estimation [20, 555, adapted to personalization. Theorem states that, given the knowledge of (b:y). o² f = and
1, there exist difficult instances of the problem that satisfy all three Assumptions 1, 2 and 3, such that the number of oracle calls needed to obtain a generalization error of a for an agent is lower-bounded by the right hand side of the equation in Theorem 1.
The factor -o is reminiscent of stochastic gradient descent, and is present Agarwal et al. [1]: without cooperation, this is the sample complexity of SGD for fixed agent. Cooperation appears in the factor (b//(b/// /4: the sample complexity inversely proportional j that have distributions similar to that of i. One cannot hope for better than a linear collaboration speedup proportional to agents 4yuc-llose to in terms of the distance du- Theorem 1 worst-case lower bound, so that a collaboration speedup could be leveraged even for small but this would require making stronger additional assumptions.
the number of agents
The ALL-FOR-ONE algorithm: parallel weighted gradient averagings
After providing lower complexity bounds in Theorem I, we present in this section a naive algorithmic approach based on weighted gradient averagings (WGA), that proves be sample-optinee agent keeps N shared local models of. ....,.,,,,, .xx.. where 24 estimates x² at iteration k (the knowledge of a needs be shared by all agents). At each iteration k. when sample <5 is obtained at agent j. it is used by that agent to compute unbiased estimates of (zy(= for all E [N]. The iterates the WGA algorithm write as, where Xij > 0 are such that E, Aij 1 for all 1 & & N:
Each
N
k+1 = x 7 Σ a
Ang (x,)
j=1
for some step size 7/ > O. We call this algorithm that consists in performing N parallel WGA algorithms ALL-FOR-ONE (AFO), since every iteration of each gradient averaging for a given node i requires all the other nodes to compute one stochastic gradient for i. WGA is thus equivalent to training models on the mixture of distributions (D,), with weights (Ni)); ) for all i.
5

---

Theorem 2. Let (EEEN, k20 be generated with (2), and assume that Assumptions 1, 2 and 3 (strong version) hold. For any K > 0 and 1 & i & N, and for n, as in Equation (6),
& (fi(a) f((xt)) K +
KO²
Σ
2
Σ
Xis
μk
EEJEN
LEjEN
1. 103,5er7 (26)
Lete >> O. For a specific choice of Xig for a number of oracle calls of:
WGA (2) satisfies E
(Filo
fi(ot)) &
K((e) Ö (
(No²
1O02
1 ue N2(222
where No is previously defined in Theorem I.
Since the oracle complexity of the WGA algorithm matches that of our lower bound, this proves that our lower bound optimal. However, this algorithm may be difficult to use in practice: (i) the choice of Ài is an explicit function of distribution distances (biz) (defined in Assumption 3) that can be (statistically speaking) as hard to compute as solving our optimization problem; and (ti) the memory requirements and computaiion/communiatiii
costs of WGA can be prohibitive for large N and large E (they scale with Ao for agent i). Note that the strong version of Assumption used in Theorem 2 can be replaced by more classical uniform bound of the form [/ Vfill & bij.
We first begin by solving this latter issue an algorithmic one in the next section, by introducing and studying the ALL-FOR-ALL algorithm. We discuss (i) in Section 6, where we provide scenarii over which statistical theoretical guarantees can be derived on the error made by estimating these distribution distances using only few samples.
The ALL-FOR-ALL algorithm
Algorithm 1 All-for--ll algorithm algoorthh
1: Step size 7) > 0, matrix W E BNNN initialization x9 =.. x E Rd (xf at agent i).
2: for k = 0, 1, ....... K 1 do
3: Agents < j & N compute of (x/) and broadcast it to all agents i such that Wij > 0.
4: For 1,... N, update:
k+1 2 11 Σ
Wiyg(
J: J:Wi>>0
5: end for Return xf for agent
In this section, we present the ALL-FOR-ALL algorithm (AFA), an adaptation of the weighted gradient averaging algorithm. For 1 < i < N, initialize x = To E Rd. At iteration k, let xf E Rd be agent i's current estimate of at, and denote x² = ( E Nx For a step size vi >> 0 and a matrix W E N with non-negative entries (remarkably and as discussed later, W will not necessarily verify E, Wi 1), iterates of the all-for-all algorithm are generated with Algorithm 1. In Theorem 3, control the averaged local generalization error amongst all agents:
1 N N
1k
Σ
- f((z)) k20.
Theorem 3 (ALL-FOR-ALL algorithm), Let K > 0, 1) > and W matrix of the form W AAT for some stochastic matrix A = (Aig) Assume that Assumptions 1, and 3 (weak version) hold. The iterates (x 1ggnN generated with Algorithm verify, for v as in Equation (7):
RO²
E K
F
+
Σ
+
Σ
A 24
KpN
N
EEUEN
EELJEN
'Ö hides logarithmic and constant factors

---

As for the AFO algorithm, we can deduce from this result the number of oracle calls required by the ALL-FOR-ALL algorithm reach an averaged E-generalization, under the idealistic setting where the distribution-based distances bij are accessible.
Corollary 1. Let E > Under the same assumptions as in Theorem 3, for a choice of matrix (0ggnee)
W = AAT where Aoj= = N; ((((F1))) the ALL--FOR-ALL algorithm (Algorithm 1) returns (a IEiN
satisfying + Ei f) - fi(at)= & for a number of oracle calls satisfying:
N
KO
Kg < 2 max
x) In
EU N
NF(P)N))
Denoting K (i) the oracle complexity of the WGA algorithm that matches the lower bound +, observe that the ALI.-FOR-AA ALI. algorithm reaches an averaged e-generalization with an number of oracle calls Kg, of K2 < N E, (t). The speedup in comparison with a no-collaboration strategy (all agents locally performing SGD) is IV E. ( the mean of all local speedups.
Remark 1. In Theorem 3, as its proof shows, the quantities /2// (2p) in the last term can in fact be replaced by the quantities fı(at) - fi(xt), that control how well the optimal model for generalizes for i, and the bias induced by ALL-FOR-ALL iterations is a weighted average of these quantities. Note that in our lower bound (Theorem 1), we enforce that the fanctions considered are required to satisfy Ja(af)) - [((;)) & 12 (2p). We believe this notion of function proximity that we leverage to be the weakest achievable in our setting; no prior work uses such a mild proximity assumption.
Perhaps surprisingly, matrix W is in general not gossip matrix (i.e. such that W1 = 1): agent i does not aggregate a convex combination of stochastic gradients, but combination with scalars that do not necessarily sum to 1. We thus cannot say that the ALI.-FOR-AA -.... algorithm acts as if, in parallel, each agent i trains model the mixture of distributions D, with weights Woy- In fact, as the analysis shows below, agent trains model on the mixture of distributions, with weights Xij. if A is a stochastic square root of matrix W (AAT = W), as in the AFO algorithm. In order to account for dnterdeependences between agents that do not directly share information, the all-for-all gradient filtering uses weights Wi to aggregate information, instead of Xrj. Propagating information using a matrix W, that induces similarity graph Gw on {l..... NN. such that (ij) E Ew if Wiy > O, is quite natural [4, 50]; yet, ours is the first analysis to give such precise generalization error bounds, through the use of stochastic optimization framework.
In comparison to Theorem 3, the classical personalized FL approaches that consider personalized local models of the form 2; E- 5,, where F is some global quantity shared by all agents, perturbed (and personalized) by some local quantity 5; (e.g. averaging between local and a global models), can be seen the special instances where, for all we have AE 1 Or and Xij N if + for some a;, and leads to bias terms of the form N Σ, a. N Σj bug [14, 25, 391. Full and naive collaboration (a single model trained for all users) corresponds to Xz = 1/N for all j,j, and leads to a bias term of N Eis bij. The degrees of freedom offered by our matrix W (and by coefficients Aiz) enable pairwise agent adaptation, and tighter generalization guarantees and bias/variance tradeoffs.
Proof sketch of Theorem 3. Since brutally analyzing convergence of the iterates (x*) generated with gk+1 -² - WG seems impossible due to both gradient biases and model biases between agents, we study these iterates through the introduction of a different but related problem. This approach is in fact similar to some decentralized optimization ones, where a dual problem related energy function is often introduced [23, 45], upon which well-studied algorithms are applied. The related problem we formulate is different from and more flexible than all the different personalized FL problems in the literature [28, 48], that consider regularization terms that enforce consensus. For A = (Nis) (ij))ei stochastic matrix (such that for all 1 < i & N, we have M/ Xij = 1), let fa be defined as:
E HERNA Nxd
where f 1 Ft Gradient descent fm writes g y N (f(''"), where
N
fx(x) 1/ (VI( LEEEN for any x E Nxd Importantly, notice that denoting x² Ay and since W AAT, we have the recursion 2² ++1 x² -nWVf(( making analysis of the iterates
7

---

(x*))
possible. In our case, we however use stochastic gradients given by our oracle. The full gradient V (x) is thus replaced by (o,) (z,)), Defining (y²)s ) with the recursion: y yv ( ).)),) initialized at yf = 21 = _... = && = z we have x* = Ay", for all & > O, where (x*) ) is generated using Algorithm As a consequence, controlling in Theorem the function values N Ex (( is
equivalent to controlling (y)) (these two quantities are equal). The bias-variance trade-off thus writes as, where yd minimizes f and x²' (ZiEN.
F (2)) - f(x))+
Biax term
Optimization and variance terms
The rest of the proof, deferred to Appendix D, consists in relating these two terms to A and 6.
After providing the optimization tools and results to answer for the shortcomings of weighted gradient averagings, we now turn to quantifying the impact the use of estimated values bi of by. in order to close the loop.
6 Estimation of (D, Dj) as a pre-processing step
The sample complexity of estimating the distances dz Dj) depends on the complexity of the function space H. While the estimation of Wassertein or total variation distances are usually hard (in ((1/51/d) where is the ambient dimension and S the number of samples available for the estimation, see e.g. [52]), maximum mean discrepancy (MMD) distances often exhibit lower sample complexities in ((IvVS) [47]. Moreover, explicit assumptions the loss function can also provide low sample complexities, as shown below for quadratic loss functions. Yet. the results presented in this section can be generalized beyond linear models with squared losses, as long as concentration inequalities for controlling how far empirical distributions are from the true distribution in terms of distance dx.
In order to formulate statistical results for the estimation of the pairwise distribution- based distances dz (D;, Dj). we need to make additional structural assumptions, on both H and the distributions. Inspired by Collins et al. [1]], we focus on analyzing an instance of our general GEM setting for quadratic losses and linear models, under which the generalization error of given agent writes as:
f(xx) - E (a]
E Rd
where 2; (0;, b,) is random variable Idd x R. The stochastic gradients thus write as
(ar = (a. x b:)a; for 2; (a;, b.). and are thus linear functions of & =,,ęT Hence, Assumption (weak version) is satisfied for H the set of D -iisschhittz and affine functions, where D* bounds all || for < i < N, leading to:
dx((D,,) D,) & D* [c.] - [2,]ll-
We make the following assumption on the law D; of the random variables &:: they are non-isotropic subgaussian random variables, that thus benefit from concentration inequalities that are dimension- independent [22, 35].
Assumption 4. For some non-negative symetric matrix E and all 1 < < N, Ea are centered and E-subgaussian:
PCT P(GTT> y 1 < exp
Vy E R(d+1)
Vu > 0,
2y Eyy
and we denote as v² the largest eigenvalue of E, and des
|| its effective dimension.
Importantly, note that deet can be arbitrarily smaller than the ambient dimension for the MNIST dataset, def is less than 3, while the ambient dimension is 712 [22]. Depending on a smaller dimension also an assumption that Collins et al. [11] use in their work by exploiting shared representations.
We now formulate a structural assumption on the set of agents: there are M clusters CI.... . of C agents each (to ease notations, with a total number of agents = .MC.. Within each cluster, agents distributions share the same objective, and clusters are "well-separated" These models are popular for modelling population heterogeneity and provide formal framework for clustering problems; we refer the interested reader Melnykov and Maitra [41] for detailed survey on the subject.

---

Assumption 5 (Well-separated clusters of agents), For M, C N writes as N = MC and there exists {C...... Carl a partition of {l..... N. Pi..... .............................. Pm such that for all & m M. |Cml C
and for all i, j. E Cm. we have E [ci] = E [Ey) = Pmn We denote A minmmnu Pl |um || and assume that A O.
When distribution-baser distances were given (as in Corollary 1), Algorithm I achieved the optimal collaboration speedup, linear 1/C under Assumption 5 and for small enough target precision e. The cluster model is thus the natural baseline for our problem. In the case where agents estimate with whom collaborate as we in the sequel, reaching this collaboration speedup of 1/C will hence prove the effectiveness of the approach.
We assume that agents possess limited number of samples. More precisely, for < i N and S, K > 1, agent possesses K + S i..d samples of drawn from D;, S of which are dedicated to estimating who to collaborate with, the remaining dedicated the optimization process i.e. to running ALL-FOR-AFE ALL iterations for number K of oracle calls.
For < N, let ù. be an estimation of E [&.] made with S i.i.d. samples E,,,,... Ei,s, and for
1 & i E N let byj be the following estimation of (D, D));
1
i
Σ E.. by = 11 A S
Computing these distances be done using only Ó(N) communications (rather than the N2 communications of a naive approach) by performing randomized gossip communications [6] on the complete graph.
Theorem 4. Under Assumptions 1,2,3 and S, and for > O. the ALL-FOR-ALL algorithm with estimated biases as just described reaches an averaged generalization error of e as long as the number of pre-used samples S and of oracle calls K satisfy:
S S=
((ott) A
C=12
(ddHt)
KC KC= (2(
1K0 (
K Ō
E/
Theorem 5 (ALL-FOR-ALL with estimated biases). Assume that Assumptions 1, 3 (for some unknown biases biz). 4 and hold, Under the setting described, let & be the stochastic matrix with entries
(og Eu
do
for some u > that verifies durdem The ALL-FOR-AAE ALL algorithm with W AÂT outputs (x. JIEEEN verifying, where bmax = max,, bij:
S maxiaa? 2u.2
[F F K + +0(POt K₁
( +Ce - )
ROO²
2D* U
Su2
+ 4u (2n3A)
where the mean is taken over both biases estimates (bis) and gradient estimates (gf):
Corollary 2. Under the same assumptions Theorem 5 and for >> O, the ALL-FOR-ALL algorithm with estimated biases as described above reaches an averaged generalization error of e as long as:
S= 5=0(
/2" A
C == (
KC
180" 52
K k=Ū(k).
E/
Forgetting about the logarithmic factors, only a bounded number of local samples for each user (S and K) are required to reach an averaged arbitrarily small generalization error > 0, in the limit with an arbitrary large number agents (N and C). Indeed, due to our regularity assumptions, K the number of samples kept for the optimization problem is required only to be of order x, the condition number of the problem. The number of samples S used for estimating the biases is required to be of order vdd 2 the "signal-to-noise" ratio of our mixture model [41, 46), natural quantity to depend on. Corollary 2 hence shows that the optimal collaboration speedup achieved, up to logarithmic factors: in order reach an arbitrary small generalization error 0, only required

---

constant orders for S and K (the number of samples locally available) if the number of agents is large enough i.e. if N = /E), where M is the number of clusters i.e. we have a linear speedup in the clusters population. We numerically illustrate our theory in Appendix on synthetic datasets, with clustered agents (as in this section), as well as in a setting where agents are distributed according to more general "distribution of agent".
A closely related work [26] also studies a model where agents verify a cluster structure as described in Assumption 5 for quadratic losses and linear models. Yet, we highlight several differences between their approach and ours. First, Ghosh et al. [26] perform an online clustering of the agents, as opposed to our pre-training hierarchical approach. While the results we obtain in Theorem and Corollary and those of Ghosh et al. [26] have the same linear speedup in the number of agents. ours require no initialization condition. Finally, our algorithm is decentralized, thus leading to improved scalability (especially in terms of the number of clusters) and privacy [13], if of interest. Finally, not being restricted to clusters in the analysis of the ALL- COLL-ALL-A algorithm leads a better collaboration speedup and faimess (in the sense that performance does not impact few agents) in non-clustered scenario, where an approach based on clusters would be highly non-optimal for agents that are at the border of the inferred clusters.
Conclusion
In this paper, we quantified in terms of function and distribution biases, stochastic gradient noise, target precision & > and functions regularity parameters, the benefit of collaboration between agents for shared minimization using stochastic gradient algorithms. Our lower bound (Theorem I) states that, under prior knowledge on the distances between local distributions, the collaborative speedup can be linear only in the first phase of the optimization when the generalization error is large compared to the distances between distributions. More specifically, for a given agent i, the collaboration speedup is linear in the number of agents that are E-close to i. Moreover, we show that the ALL-FOR-ON algorithm allows such a speedup and is thus sample optimal. However, this algorithm requires high computation and communication capacities, drawback that can be mitigated by the use of a novel algorithm called ALL--FO--LL. that benefits from the same collaboration speedup while being cheaper to deploy. Finally, we studied the impact of estimating distances between distributions as a pre-processing step to the optimization phase; under a mixture model assumptions on the agents, we obtain an optimal collaboration speedup. Extending our results lower and upper complexity bounds- - to other regularity assumptions and Section 6 to more general settings, as well as incorporating local steps in the ALL-FOR-ALL algorithm (even though lighten communications, unbiased compressors could here be used, as our analysis encompasses these) are interesting questions left for future work. See [24] for extensions to convex-smie smooth functions (not necessarily strongly convex), convex-Lipschiee functions, and to asynchronous gradient oracles.
This work was supported by ANR-19- 111-------AA-00PPAAAI 3IA Institute). We also acknowledge support from the MSR-INRIA joint centre.
Aknowledgments
References
[1] Alekh Agarwal, Peter L. Bartlett, Pradeep Ravikumar, and Martin J. Wainwright. Information- theoretic lower bounds on the oracle complexity of stochastic convex optimization. IEEE Transactions on Information Theory. 5855):3235332444 2012.
[2] Heinz H. Bauschke, Jérôme Bolte, and Mare Teboulle. A descent lemma beyond lipschitz gradient continuity: First-order methods revisited and applications. Mathematics of Operations Research, 4302))330-348, 2017.
[3] Martin Beaussart, Felix Grimberg, Mary-Anne Hartley and Martin Jaggi. WAFFLE: Weighted Averaging for Personalized Federated Learning. arXiv:21 1 10.06978 [cs], October 2021.
[4] Aurélien Bellet, Rachid Guerraoui, Mahsa Taziki, and Marc Tommasi. Personalized and private peer-to-peer machine learning. In Proceedings of the Twenty- First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 473-481, 2018.
10

---

[5] Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-31 3113,11,,11 January 2018.
[6] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Randomized gossip algorithms. IEEE Transactions Information Theory, 52(6):2508- June 2006. ISSN 0018-9448. doi: 10.1 0..1009/TT12200.87455511 URL
ieweelorreeeeee...........eeeee. org/ pocument//63885//
[7] Sébastien Bubeck. Convex optimization: Algorithms and complexity, 2015.
[8] El Mahdi Chayti, Sai Praneeth Karimireddy, Sebastian U. Stich, Nicolas Flammarion, and Martin Jaggi. Linear speedup in personalized collaborative learning, 2021.
[9] Fei Chen, Mi Luo, Zhenhua Dong, Zhenguo Li, and Xiuqiang He. Federated meta-learning with fast convergence and efficient communication, 2018. URL https:///axxa org/ abs/ 1802.07876.
[10] Gary Cheng, Karan Chadha, and John Duchi. Fine-tuning is Fine in Federated Learning. arXiv:2108.07311 [cs, math, stat], August 2021.
[11] Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared representations for personalized federated learning. In Marina Meila and Tong Zhang, edi- tors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learming Research, pages 2089-2099, PMLR, 18-24 Jul 2021. URL cetts://proceedingg
mlr press/ prressvv39/// c html.
[12] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley, April 2005.
[13] Edwige Cyffers, Mathieu Even, Aurélien Bellet, and Laurent Massoulié. Muffliato: Peer-to-pece privacy amplification for decentralized optimization and averaging. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https: /ttttps:/opperreieee
[14] Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Adaptive Personalized Federated Learning. arXiv:2003. /346/ [cs, stat], November 2020. arXiv: 2003.1344
[15] Shu Ding and Wei Wang. Collaborative learning by detecting collaboration partners. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https: / /ttp::///ppeeeeeeeeeeeeee net/forumffdieeee fkiFqG-min muu.
[16] Kate Donahue and Jon Kleinberg. Model-sharing games: Analyzing federated learning under voluntary participation. Proceedings of the AAAI Conference on Artificial Intelligence, 35(6); 5303-5311, May 2021.
[17] Kate Donahue and Jon Kleinberg. Optimality and stability in federated learning: game- theoretic approach. In Advances in Neural Information Processing Systems, 2021.
[18] Radu Alexandru Dragomir, Mathieu Even, and Hadrien Hendrikx. Fast stochastic bregman gra- dient methods: Sharp analysis and variance reduction. In Proceedings of the 38th International Conference on Machine Learning, volume 139 Proceedings of Machine Learning Research, pages 2815-2825. PMLR, 18-24 Jul 2021.
[19] Simon Shaolei Du. Wei Hu, Sham M. Kakade, Jason Lee, and Qi Lei. Few-shot learning via learning the representation, provably. In Intermational Conference on Learning Representations, 2021. URL https: http:/:://////eveeeeeeeeee wwt atte/foormmm1aap222221www
[20] John Duchi and Ryan Rogers. Lower bounds for locally private estimation via communication complexity. In Proceedings of the Thirty-Seoond Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1 1161-1191, Phoenix, USA, June 2019. PMLR.
[21] John C. Duchi and Martin Wainwright. Distance-based and continuum fano inequalities with applications to statistical estimation. 2013.

---

[22] Mathieu Even and Laurent Massoulié. Concentration of Non-Isotropic Random Tensors with Applications Learning and Empirical Risk Minimization, arXiv:2102.0 00000042599/ [cs, math, stat], February 2021. URL.
24220.00.9. 04259. arXiv: 2102.04259.
[23] Mathieu Even, Raphaël Berthier, Francis Bach, Nicolas Flammarion, Hadrien Hendrikx, Pierre Gaillard, Laurent Massoulié, and Adrien Taylor. Continuized accelerations of deterministic and stochastic gradient descents, and of gossip algorithms. In Advances in Neural Information Processing Systems, 2021.
[24] Mathieu Even, Laurent Massoulié, and Kevin Scaman. Sample optimality and all-for-all strategies in personalized federated and collaborative learning. arXiv, 2022.
[25] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized Federated Learning with Theoretical Guarantees: Model-Agnostic Meta-Learning Approach. Advances in Neural Information Processing Systems, 33:3557-3568, 2020.
[26] Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ramchandran. An efficient framework for clustered federated learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 19586- 19597. Curran Associates, Inc., 2020. URL https: httpttt/////ooet p/proceed/// inw.uuurdnnnn.s.uuiipip........s pdf.
neurips....... cc/paper/
[27] Felix Grimberg, Mary-Anne Hartley, Sai P. Karimireddy, and Martin Jaggi. Optimal Model Averaging: Towards Personalized Collaborative Learning. arXiv:2110. 12946 [cs, stat], October 2021. arxiv: 2110.12946.
[28] Filip Hanzely, Slavomír Hanzely, Samuel Horváth, and Peter Richtarik. Lower Bounds and Optimal Algorithms for Personalized Federated Learning. In Advances in Neural Information Processing Systems, volume 33, pages 2304-2315. Curran Associates, Inc., 2020.
[29] Daniel Hsu, Sham Kakade, and Tong Zhang. A tail inequality for quadratic forms of subgaussian random vectors. Electronic Communications in Probability, 17(none): - 6, 2012. doi: 10.
214//CPPv17-2079 URL https://doi. /ttp:::///oooor/11000/ 10. 1214/1C1 (tt...vv7--.. v17720799.
[30] Yihan Jiang, Jakub Konečný, Keith Rush, and Sreeram Kannan. Improving federated learning personalization via model agnostic meta learning, 2019. URL https://arxiv. org/ abs/ 1909. 12488.
[31] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný. Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo. Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür. Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang. Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and Open Problems in Federated Learning. 1912.0477 [cs, stat], December 2019. arXiv: 1912.04977.
[32] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic Controlled Averaging for Federated Learning. In Proceedings of the 37th International Conference on Machine Learning, pages 5132-5143. PMLR, November 2020. ISSN: 2640-3498.
[33] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtarik. Tighter theory for local sgd on identical and heterogeneous data. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 4519-4529, PMLR, 26-28 Aug 2020. URL https:/ http///rreeeee..ee/////// mlr, .trrrppes////eeo. /asess/vvv0 v108/ wwlvvv0000vuu bayoumi aaayomii2a.... html.
12

---

[34] Mikhail Khodak, Maria-Florina F Balcan, and Ameet S Talwalkar. Adaptive Gradient- Based Meta-Learning Methods. Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[35]
Vladimir Koltchinskii and Karim Lounici. Concentration inequalities and moment bounds for sample covariance operators. Bernoulli, 23(1):110 133, 2017. doi: 10.3150/15-BEJ730. URL https://doi. org/ 10. 3150/15-BEJ
[36] Jakub Konečný, H. Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated Optimization: Distributed Machine Learning for On-Device Intelligence. arXiv:6610.02527 [cs], October 2016. arXiv: 1610.02527.
[37] Viraj Kulkarni, Milind Kulkamni, and Aniruddha Pant. Survey of Personalization Techniques for Federated Learning. arXiv:2003.0868 [cs, stat], March 2020. arXiv: 2003.08677
[38] Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. In International Conference on Learning Representations, 2020.
[39] Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. Three Approaches for Personalization with Applications to Federated Learning. arXiv:2002.10619 [cs, stat], July 2020. arviv: 2002.10619.
[40] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-Effice. Learning of Deep Networks from Decentralized Data. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 1282. PMLR, 20-22 Apr 2017.
[41] Melnyko and Ranjan Maitra. Finite mixture models and model-based clustering. Statistics Surveys, 4(none):80 116, 2010. doi: 10.1214/09-$5053 URL httph:ttt/:dlte //oi:i///////// org/ 10. 1011124499-SS55
Melnykov
[42] Aritra Mitra, Rayana Jaafar, George Pappas, and Hamed Hassani. Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. In M. Ran- zato, A. Beygelzimer, Y. Dauphin. P.S. Liang, and J. Wortman Vaughan, editors, Ad- vances in Neural Information Processing Systems, volume 34, pages 14606-14619, Cur- ran Associates, Inc., 2021. URL https: pttpe//dioooccnsssso netriis...ppp.. paturips.cc/pppp///000// sc/paperr/021//tlee/ pdf.
[43] Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic Federated Learning. In Proceedings of the 36th International Conference on Machine Learning, pages 4615-4625.
PMLR, May 2019. ISSN: 2640-3498.
[44] Angelia Nedich, Alex Olshevsky, and Michael G. Rabbat. Network topology and communication-computtiie tradeoffs decentralized optimization. Proceedings of the IEEE, 106(5):953-976, May 2018.
[45] Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal convergence rates for convex distributed optimization networks. Journal of Machine Learning Research, 20(159):1-31, 2019.
[46) Nathan Srebro, Gregory Shakhnarovich, and Sam Roweis. An investigation of computational and informational limits gaussian mixture clustering. In Proceedings of the 23rd International Conference Machine Learning, ICML '06, page 865-872, New York, NY, USA, 2006. Association for Computing Machinery. ISBN 1595933832. doi: 11111//11134441144444 URL https://doii orgg 10. 11.11.1.11.0 1111/1144384 1143953.
[47] Bharath K. Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Bernhard Schölkopf, and Gert R.G. Lanckriet. Hilbert space embeddings and metrics on probability measures. Journal of Ma- chine Learning Research, 11(50) 2010. URL sr sriperumbudur Oa. html.
[48] Canh T. Dinh, Nguyen Tran, and Josh Nguyen. Personalized Federated Learning with Moreau Envelopes. Advances in Neural Information Processing Systems, 33:21394-21400 2020.
13

---

[49] Nilesh Tripuraneni. Michael Jordan, and Chi Jin. On the theory of transfer learning: The importance of task diversity. In H. Larochelle, M. Ranzato, Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 7852-7862. Curran Associates, Inc., 2020.
[50] Paul Vanhaesebrouck, Aurélien Bellet, and Mare Tommasi. Decentralized Collaborative Learn- ing of Personalized Models over Networks. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings Machine Learning Research, pages 509-517. PMLR, 20-22 Apr 2017.
[51] Kangkang Wang, Rajiv Mathews, Chloé Kiddon, Hubert Eichner, Françoise Beaufays, and Daniel Ramage. Federated Evaluation of On-device Personalization. arXiv: 10252 [cs, stat], October 2019. arXiv: 1910.10252.
[52] Jonathan Weed and Francis Bach. Sharp asymptotic and finite- sample rates of convergence of empirical measures in Wasserstein distance. Bernoulli, 25(4A):2620 2648, 2019. doi: 10.3150/18-B8 B-EJ1166. URL https://doi. org/10 10 3150/15511 18- BEJ1065.
[53] Blake Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs local sgd for heteroge- neous distributed learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 6281-6292 Curran Associates, Inc., 2020. URL https /ttp::///rrocoa http:///pooocco..../// wew.eeeeennnnnnnenn....e..ee cc/paper/2020.. 1511//6877300f111111c12222222223 Paper pdf.
[54] Tao Yu, Eugene Bagdasaryan, and Vitaly Shmatikov. Salvaging Federated Learning by Local Adaptation. arXiv:2002.04758 [cs, stat], October 2021. arXiv: 2002.04758.
[55] Yuchen Zhang, John Duchi, Michael Jordan, and Martin Wainwright. Information-thhoortiic lower bounds for distributed statistical estimation with communication constraints. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
14


Reviews:
[{"review_id": "HjRuJ5t8jD-", "reviewer": "Reviewer_g22N", "summary": "This paper studies the sample complexity of personalized federated learning with a large number of users (each holding a few samples). The authors investigate the benefit of collaborative learning via stochastic gradient descent in terms of distribution biases, noise variance, and regularity of function classes (strongly convex and smooth optimization). Based on known distances between local distributions, the authors propose a lower bound on the sample complexity of all users in order to minimize the generalization error of one user. They also present the All-For-One algorithm, which achieves the linear speedup shown in the lower bound and propose a second modified algorithm to address the communication and computation costs associated with this method.", "questions": ".", "limitations": ".", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The mathematics in this paper appear to be correct, and the topic is interesting. The organization and writing of this paper are generally very good. Moreover, the authors have provided an experimental result to support their theoretical findings. A limitation of this study is that it does not compare with seminal work on personalized federated learning. A comparison of the two proposed algorithms (All-For-One and All-For-All) has not been conducted with other techniques for personalization.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "D2v9V8XBo3j", "reviewer": "Reviewer_WfLi", "summary": "The paper shows an information-theoretic lower bound on the number of oracle calls for collaborative training on clients. Two optimal collaborative training algorithms (gradient filtering algorithms) are proposed, and convergence rates are presented. ", "questions": "The paper in several sections is out of my area of expertise. My questions are as follows:\n\n1. Theorem 2: given $\\lambda_{ij} \\geq 0$ and they sum up to 1, the 3rd term in the right-hand side of the inequality is lower bounded by $a_i := min_j \\frac{b_{ij}^2}{\\mu}$. The first two terms are at least zero. Does the theorem allow $\\varepsilon$ to be less than $a_i$?\n\n2. Why should the matrix $W$ in the equation between lines 53 and 54 be symmetric?", "limitations": "Limited experiments. ", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths. The paper develops a strong theory proving a lower bound on the sample complexity and proposing algorithms with matching upper bounds. \n\nWeaknesses. The limited experimental support of the theory.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6nzYTLRKtKE", "reviewer": "Reviewer_teu2", "summary": "This paper studies the issue of personalization in federated learning - a very timely topic. While several works have introduced a variety of techniques (e.g., clustering, representation learning, MAML, etc.,) to promote personalization in FL, this paper takes a different approach. It explores the idea of aggregating gradients by carefully adjusting the weights of such aggregation based on pairwise client similarities. An information-theoretic lower bound is established that reveals how much a client participating in the FL process can hope to benefit from collaboration. Furthermore, it is shown that the weighted aggregation scheme can achieve such a lower bound. \n\n", "questions": "I don't have any questions beyond the clarifying comments I raised earlier.", "limitations": "I don't foresee any negative societal impacts of this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I think this is a very well-written paper. I summarize my main comments below.\n\n*Strengths* \n- The main contribution of the paper, in my opinion, is Theorem 1. It is very informative in that it reveals how much a client can reduce its local generalization error by using the data from other \"similar\" clients. In this context, the notions of similarity introduced in Assumption 3 are both novel and intuitive. \n\n-  The All-For-All algorithm achieves the lower bound in Theorem 1 by employing a filtering protocol - while updating its model via gradient aggregation, a client only uses the gradients of other clients that are close to it in a suitable sense. As a result, the weight matrix $W$ used in the aggregation rule is no longer a standard Markov matrix used for studying consensus/distributed optimization. This makes the analysis of the algorithm a bit different from the standard analyses. \n\nOne key point to note here is that the algorithm assumes prior knowledge of the client similarity indices, which can be very prohibitive in practice. Fortunately, in Section 6, the authors show how one can use a small number of samples initially to figure out such similarity indices and accordingly cluster the agents. \n\nCoupled with the fundamental limit in Theorem 1, the All-For-All algorithm and the initial similarity-index estimation protocol in Section 6 lead to a strong theoretical contribution. I do have a few clarifying comments that are outlined below.\n\n*Comments*\n\n- Other than being a conceptual tool, is there any practical utility of the All-For-One Algorithm? In particular, in addition to the stringent communication overhead it imposes, it seems that at each round, every client needs to evaluate the gradient of its loss function at the models of *all* clients. This is in stark contrast to existing FL algorithms, where every client computes gradients at just its own model/iterate. As such, the All-For-One algorithm seems to require significantly more oracle calls than standard FL algorithms. Is this a fair assessment?\n\n- The approach outlined in Section 6 seems to be valid for simple quadratic loss functions. This is fine for now as it lends some credibility to the overall approach proposed in this paper. But is there hope that the results in Section 6 can be generalized beyond quadratic losses? \n\n- At the end of the day, the overall technique boils down to clustering clients initially, and running a parallel gradient descent algorithm within each cluster; the benefits of collaboration are then limited to each cluster. In this sense, I am curious to know how this high-level idea compares with some other well-established clustering-based methods in FL. See, for instance, ref [R1] below.\n\n[R0] *An Efficient Framework for Clustered Federated Learning*, Ghosh et al.., NeurIPS 20.\n\nIn [R0], the authors develop a strategy that involves alternatively refining the cluster identities and solving the supervised learning problem. That is, the clustering and learning processes are interleaved, as opposed to the hierarchical approach suggested in the current work. I would like the authors to comment on this further.\n\n- The aspect of personalization stems from the fact that the data-generating distributions of the clients are non-identical in practice, leading to loss functions with different minima (indeed, if all clients saw data from identical distributions, the global model would also serve well as a personalized model). As such, a very rich body of work has explored the angle of objective/statistical heterogeneity, improving our understanding of this fundamental challenge in the context of FL. However, the authors in this paper completely ignore this line of work, which I find unsatisfactory. I would like to see a better representation (and discussion) of this literature in the authors' related work section. Some notable papers in this regard are mentioned below, but this is by no means an exhaustive list.\n\n[R1] *Tighter Theory for Local SGD on Identical and Heterogeneous Data*, Mischenko et al., AISTATS 20.\n\n[R2] *SCAFFOLD: Stochastic Controlled Averaging for Federated Learning*, Karimireddy et al., ICML 20.\n\n[R3] *Minibatch vs local sgd for heterogeneous distributed learning*, Woodworth et al., NeurIPS 20.\n\n[R4] *FedSplit: An algorithmic framework for fast federated optimization*, Pathak and Wainwright, NeurIPS 20.\n\n[R5] *Convergence and accuracy trade-offs in federated learning and meta-learning*, Charles and Konecny, AISTATS 21.\n\n[R6] *Federated Learning Based on Dynamic Regularization*, Acar et al., ICLR 21.\n\n[R7] *Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients*, Mitra et al., NeurIPS 21.\n\n[R8] *Local SGD: Unified Theory and New Efficient Methods*, Gorbunov et al., AISTATS 21.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2RX56siE3Q", "reviewer": "Reviewer_tnmx", "summary": "The paper studies the personalized federated learning and makes a few contributions. First, it proves an information-theoretic lower bound on the sample complexity. Second, it proposes an all-for-one algorithm that matches the lower bound but needs a high communication cost for broadcasting stochastic gradients between agents. Third, it further proposes a communication-efficient all-for-all algorithm via the gradient-filtering method. ", "questions": "In Line 179, how does the factor epsilon/4 come?\n\nIn Line 203, large epsilon?", "limitations": "see above", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "originality: theoretical contributions to FL. It leverages the distribution-based distance to analyze the sample complexity.\n\nquality: technical depth looks sufficient.  \n\nclarity: good except that it is unclear how the analysis differs from existing works that is closest to this work.\n\nsignificance: gradient filtering seems to be a good technique for both communication reduction and personalization promotion.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept