Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable
Authors: Bicheng Ying
Zhe Li
Haibo Yang
Venue: NeurIPS 2025 poster ()
Keywords: Federated Learning
Arbitrary Client Participation
Graph
Stochastic Matrix
Decentralized Optimization
Primary area: optimization
TL;DR: We proposed Federated Optimization with Exact Convergence via Push-pull Strategy (FOCUS) that can converge exactly with a linear rate even under arbitrary client participation scenario.

Abstract: This work tackles the fundamental challenges in Federated Learning (FL) posed by arbitrary client participation and data heterogeneity, prevalent characteristics in practical FL settings.  It is well-established that popular FedAvg-style algorithms struggle with exact convergence and can suffer from slow convergence rates since a decaying learning rate is required to mitigate these scenarios. To address these issues, we introduce the concept of stochastic matrix and the corresponding time-varying graphs as a novel modeling tool to accurately capture the dynamics of arbitrary client participation and the local update procedure. Leveraging this approach, we offer a fresh perspective on designing FL algorithms, provide a rigorous quantitative analysis of the limitations inherent in the FedAvg algorithm, and present FOCUS, Federated Optimization with Exact Convergence via Push-pull Strategy, a provably convergent algorithm designed to effectively overcome the previously mentioned two challenges. More specifically, we provide a rigorous proof demonstrating that FOCUS achieves exact convergence with a linear rate regardless of the arbitrary client participation, establishing it as the first work to demonstrate this significant result.

Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable
Bicheng Ying'
Zhe Li
Haibo Yang?
Gooole Rochester Institute of Technology
ybcogoogle. com, {214063, hbycis)errii Grit edu
Abstract
This work tackles the fundamental challenges in Federated Learning (FL) posed by arbitrary client participation and data heterogeneity, prevalent characteristics practical FI. settings. It is well-established that popular FedAvg-style algorithms struggle with exact convergence and can suffer from slow convergence rates since decaying learning rate is required to mitigate these scenarios. To address these issues, we introduce the concept of stochastic matrix and the corresponding time- varying graphs as novel modeling tool to accurately capture the dynamics of arbitrary client participation and the local update procedure. Leveraging this approach, offer fresh decentralized perspective and present FOCUS, Federated Optimization with Exact Convergence via Push-pull Strategy, a provably convergent algorithm designed to effectively overcome the previously mentioned two challenges. More specifically, we provide a rigorous proof demonstrating that FOCUS achieves exact convergence with linear rate regardless of the arbitrary client participation, establishing it as the first work to demonstrate this significant result.
designing FL algorithms
Introduction
Federated Learning (FL) has emerged powerful paradigm for distributed learning, enabling multiple clients to collaboratively train models without sharing raw data. Yet, a central challenge in FL is the arbitrary and unpredictable nature of client participation. In real-world FL, clients may join or leave at will, participate intermittently. or drop out due to connectivity or resource constraints.
Recall the goal of the FL problem is to minimize the following sum-of-loss function:
F(x) = N Σ fa(x), ==(=)=== E(o,)=E(-
where x Rd represents the d-dimensional model parameter and fn stands for the local cost function. It is well established that when clients perform multiple local updates on non-i.i.d data, their local models tend to diverge. This leads to client drift from the optimal solution of problem (T). phenomenon that persists even under the often impractical uniform client sampling assumption KKarimrredy et al. 2020 Li et al. 2020]. Moreover, arbitrary client participation introduces another objective bias: instead of converging to the global optimum, the global model converges
objective [Wang et al. 2020 Wang and Ji 2022]. To mitigate this persistent error, existing methods typically require decaying the learning rate asymptotically to zero, at least theory. While this strategy can reduce the bias in the limit, it often leads to slower convergence. Hence, key question naturally arises:
stationary point of a distorted, participation-weighee
Question: Is it possible achieve exact convergence under both arbitrary client participation and multiple local updates without decaying the learning rate?
We will provide an affirmative answer this question in this paper. We begin by introducing a novel analytical framework that reformulates the core operations of - client participation, local updates,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

and model aggregation over time-varying graphs as sequence of stochastic matrix multiplications (Hom and Johnson 2012]. Next, with this tool, we develop a new algorithm FOCUS, Federated Optimization with Exact Convergence via Push-pull Strategy, which is inspired by decentralized optimization algorithms [Nedic and Ozdaglar 2009 Sayed et all, 2014 Lian et al. 2017 .an et al.
2020]. More specifically, we leverage the sush-pull technique [ and Khan, [20 8 Pu et al. 2020] with the time-varying graphs [Nedic et al. 2017 Ying et al. 2021 Nguyen et al. [025 instead of commonly used static or strongly connected communication graphs since FOCUS is designed for
the FL setting. Compared to the variance reduction technique [Johnson and Zhang 2013 Defazio al., 2014] or the adaptively learning participation probabilities, the push-pull approach handles the unknown client participation scenario much better both empirically and theoretically.
Our main contributions are summarized as follows:
We provide a systematic approach reformulate all core processes of FL client participation, local updating, and model aggregation through the stochastic matrix multiplication.
We proposed Federated Optimization with Exact Convergence via Push-pull Strategy (FOCUS), which is designed based on the optimization principle instead of heuristic design.
Even under arbitrary client participation, FOCUS exhibits linear convergence (exponential decay) for both strongly convex and non-convex (with PL condition) scenarios without assuming the bounded heterogeneity decaying the learning rates.
We also introduce a stochastic gradient variant, SG-FOCUS, which demonstrates faster conver- gence and higher accuracy, both thcoretically and empirically.
Algorithm
Exact Converg.
Strongly-Convex Complexity"
Non-Convex Complexity
Participation
Hetero. Grad.
ssumptions
Extra Comment
FedAvg al 2020
X
O(
O(1)
Uniform
Bounded
Bounded gradicut assumption
X
o
Uniform
Bounded
Doubly stochastic matris
Koloskova
2020
X
((4)
Arbitrary
Bounded
Bounded global gradicat
Wang and Ji 2024
Xiang 2024
FedAWE
X
((1)
Arbitrary
Bounded
Doubly stochastic
Karimireddy ci al
XCAFFFOLD
2020
o (og(()
o(
Uniform
None
Comm, 25 vector round"
Mishchenko et al. 2022
X
o ((ug()))
Full
None
Comm. 2d vector per round
((2)
Arbitrrry
Bounded
Server stores each client model
Bounded delay
(This paper)
PU802
((he(()))
O( (()))()))
Arhirary
None
No need learn partici. prob.
Table 1: Comparison of multiple algorithms. Exact convergence refers to the algorithm's 's ability to converge the exact solution under arbitrary sampling, without requiring decaying learning rate. Complexity refers to the number of iterations required for the algorithm to achieve an error within e the optimal solution. have removed the impact of the stochastic gradient variance in all rates. There is no convergence proof of SCAFFOLD under arbitrary client participation scenario. Empirically, we observed it may be possible. This rate established with PL condition. Arbitrary participation refers Assumption I and the bounded heterogeneous gradient are the assumptions that ( eG. It possible to reduce the uplink communication into d while downlink one is still 2d (Huang et al. 2024
2 Related Work
FedAvg McMahan et al. 2017 is the most widely adopted algorithm in FL.. It roughly consists of three steps: 1) the server activates a subset of clients, which then retrieves the server's current model. 2) Each activated client independently updates the model by training on its local dataset. 3) Finally, the server aggregates the updated models received from the clients, computing their average. This process can be represented mathematically as:
(r) 20.1 + Tr. Vi E S, For t= 0, 1.. T-1: (r) (r)
(Pull Model)
(2a)
(Local Update)
1 2 f)
Vi S, in parallel
(2b)
Er41 + S JT
(r)
(Aggregate Model)
(2c)
seS.

---

where the set S, represents the indices of the sampled clients at the communication round r. The (r) notation 2r E Rd stands for the server's model parameters at r-th round, while x stands for the client i's model at the t-th local update step in the r-th round. We use + to indicate that communication has happened between clients and the server.
Because of the data heterogeneity and multiple local update steps. Li et al. (2020) has shown that the fixed point of FedAvg is not the same the minimizer of in the convex scenario. More specifically, they quantified that --11= 2(( - 1)n)|
(3)
where x is the fixed point of the FedAvg algorithm and x² is the optimal point. This phenomenon, commonly referred to client drift [Karimireddy et al.) 2020]. can be mitigated by introducing control variate during the local update step, an approach inspired by variance reduction techniques
[Johnson and Zhang 2013]. Prominent examples of this strategy, including SCAFFOLD (Kariirredy
et al. [020] and ProxSkip Mishehenko et al.) 2022], can further circumvent the need for a bounded heterogeneity assumption. Yet, this approach incurs increased communication costs, doubling them due to the transmission of a control variate with the same dimensionality as the model parameters.
Many analytical studies on FL assume that the sampled clients are drawn from a uniform distribution, an assumption shared by the literature cited in the preceding paragraph, but this is almost impractical in
reality [Kairouz et al. [021 Xiang et al.) [024 Li et al. 2025). Wang and Ji (2022) shows that FedAvg might fail to converge to x= under non- non- uniform sampling distributions, even with a decreasing learning rate 17. To address the challenges posed by non-uniformity, common approach involves either explicitly knowing or adaptively learning the client participation probabilities during the iterative process and subsequently modifying the averaging weights accordingly (Wang and Ji 2024 Wang
et al. 2024 Xiang et al. 2024). Yet, neither of them can achieve exact convergence, and the learning process may slow down the convergence. An alternative approach is to Variance Reduction (VR) techniques, as seen in methods like MIFA Gu et al.) [2021] and Fed Jhunjhunwala et al. [2022] Yet, the heuristic integration of VR with FL often fails to jointly address the client drift issue. This results, once again, in inexact convergence when a constant learning rate is used.
FcdVARPJUunjhuunall
It is known that FL and decentralized optimization are closely related [Lalitha al. 2018 Koloskoval ctt al., 2020 Kairouz et al.) 2002]]. and this work is closely related to the tools introduced in the decentralized optimization society. We leave detailed decentralized literature review in Appendix A
3 Graph, Stochastic Matrix, and Arbitrary Client Participation
FL algorithms are commonly expressed in a per-client style, as exemplified by the previously highlighted FedAvg formulation (2)-(2c). While this representation offers ease of understanding and facilitates straightforward programming implementation, a stacked vector-matrix representation can unlock more powerful mathematical tools for the design and analysis of FL algorithms.
To illustrate the concept, let us consider two toy examples of vector-matrix multiplication:
[
0
x
[a
0
0.5
0.5
[oo
[x] + x2)
W Wassign T
1
0
x1
Zu
W
avg
x
0
1
0
Σ1
.1
1
[22
0
0
I2
While the calculations themselves are straightforward, their significance lies in the appropriate interpretation of the matrices and vectors within the FL context. We interpret x; E Rixd as the model parameter stored in the worker i. Index O is assigned for the server, and the result indices are for clients. Then, the first W asssign can be viewed as the server assigning its value zo client while the value of client 2 is unchanged as the same as not participated scenario. The second Wavg can be viewed as the server setting its own value the average of the value of worker 1 and worker 2. These two toy matrices reflect the pull and aggregate model two key steps in the FedAvg algorithm.
More formally, given a sampled client indices set S,,, subscript for the r-th round, we define the model-assign matrix R(S,)) and the model-average matrix A(S,) as
{1
if E S, and j = 0 if $ S, and j otherwise
1
if if==i00
R(S,)
1/15.1 A(S.)(i.1
if E S, and j 0 (4)
otherswise
While the mathematical notation of the matrix may not be immediately apparent, its structure should be clear to see the illustration provided in Figure I In the figure, we utilize the graph language to
3

---

Model
0
Pash Model
style)
Push Model (columnn style)
Bi di-direcctionll
Row Stochastic Matrix
Row Stochastic Matrix
Columa Stochastic Matrix
Daubly Stochustic Matrix
0
1
0
0
1 0
Ginocal
0
0
1 0
1
0
0
0 0 0
0
0
0
R
0
0
A
0
0
1
0
0
C-
1
0
0
W
0
1
0
0
1 0
0
0
1
0
0
0
0
0
0
0
0
1
0
Figure 1: The graph representation of the communication pattern of 5 nodes and its possible corresponding stochastic matrices. For clearness, the self-loop is not drawn. If the node is treated server and node to as clients, the leftmost a typical pull-model step, i.e. client and 3 are participated: the model average step in the FedAvg; the third graph is a same graph but using column-stochastic matrix, which is uncommon in the FL literature; The last one is typical (symmetric) doubly stochastic matrix case used in the decentralized optimization algorithm.
second graph depicts
visualize the matrix W. We can treat W as a weighted adjacency matrix; the nen-zero value entry W[.,j] implies a link from node j to node i. Hence, W is also commonly referred as the mixing matrix. Suppose S, = {1,3}, then the matrices R(S,) and A(S,) correspond to the leftmost and second leftmost matrices and graphs depicted in the figure, respectively.
The weights are selected to ensure the resulting matrix is stochastic matrix. Specifically, matrix W is called row stochastic if W1 11 = 1, where is a all-one vector; it is called column stochastic if 1' = 1 ; and it is doubly stochastic if satisfies both row and column stochastic properties [Horn] and Johnson 2012, Meyer 2023]. It is straightforward to verify that the above two matrices both are row-stochastic matrices. Analogously, for the participation set, we can define a corresponding column stochastic matrix C(S,) and a doubly stochastic matrix W(S)).
1/1SAI
if E S, and j = 0 if E S, and i = 0 if - otherswise
{1
i E S, and i =0 if S, and = [( >, W 0 otherswise
1/1SH
C(S.)
Suppose S, = [1, then the matrices (S,) and C(S,) correspond to the rightmost and second rightmost ones depicted in the figure. These four matrices will play the critical role in the following algorithm design and convergence proof section. In contrast to decentralized algorithms, where assumptions are directly imposed on the mixing matrix, we do not make any assumption about them in this paper since we utilize them to model the client participation process. For completeness, a brief review of stochastic matrices and their properties provided in the Appendix
3.1 Arbitrary Client Participation Modeling
FL focuses the process of generating the arbitrary client participation set S,.. Inspired by Wang and Ji 2202). in this paper, we model the arbitrary client participation by the following assumption.
Assumption (Arbitrary Client Participation). In each communication round, the participation of the i-th worker is indicated by the event D,. which occurs with unknown probability pt E (0. 1). I = indicates that the i-th worker is activated while 0, = O indicates not. The corresponding averaging weights are denoted by qi where = E [[4/()) N 1,)]
Assumption iss general one covering multiple cases:
Case 1: Full Client Participation. This is simply as p; and q: = v for all client indices i.
Case 2: Active Arbitrary Participation. Each client i independently determines they will participate in the communication round. The event I follows the Berouulii distribution ps, where I. are close to each other, then q; ~ pz/(E, Pý).
P; E (0, 1]. (Note E.p. * 1.) If [
Case Passive Arbitrary Participation. The server randomly samples m clients each round. Each client is randomly selected without replacement according to the category distribution with the

---

normalized weights 91, 92, 9N, where Σ, 1.9: > 0. ps does not have simple closed form. But if is sampled with replacement, then p; (1 9:)m
Case 3a: Uniform Sampling. This is special case of case 3, where p; m/= and q: 1/m.
Passive arbitrary participation is often referred to as arbitrary client sampling. We also use "sampling" and "client participation" interchangeably throughout this paper. Now. considering that S, is generated according Assumption [ it can be readily verified that the corresponding assigning matrix and averaging matrix possess the following property:
partion
1
n
2N
Q1
1
91
0
= E E(()))
E(S)
=
(5)
LQN
qNd
The bolumm-sttocasstee matrix equals (Č= E[C(S,) RT) by definition. While doubly stochastic matrices are prevalent in the decentralized literature, they are not often applicable to FL-style algorithms, and therefore we do not discuss them further. With this approach, transform the problem of arbitrary client participation probabilities into an analysis of the matrix properties of R(S,), A(S,), and C(S,) which will exploit in the subsequent section.
effectively
From Interpretation to Correction: A New Federated Optimization with Exact Convergence via Push-pull Strategy FOCUS
In this section, we demonstrate how leveraging the graph and stochastic matrix can facilitate the development of more powerful FL algorithms.
4.1 Interpret FedAvg Decentralized Algorithm with Time- Varying Graphs
A direct application of the above mixing matrix is that we can concisely represent the FL algorithm vector-matrix form, similar to decentralized algorithms [Li et al. 2020
Koloskova al. 2020).
First, let 2g vstack [=x.0 TA,1:". : ] E IN++1)xd denote the state at iteration k. This matrix
is formed by vertically stacking the server's model parameters Zæ,0 Rd and the model parameters
Tkii E Rd from the N workers. Similarly, let V f (xxx) vstack (0; V ( R (x++)x represent the corresponding stacked vector of local gradients at iteration &. Note that the first component of the stacked gradient is 0 because the server holds no data. This implies that server's 's local loss function is identically zero, fo(x) = O, and consequently. V fo(x,.))) 0. This also ensures that including the server's term fo does not alter the original loss function defined (L)
VN
Next, observe that during the local update phase of FedAvg, nodes compute updates independently without communication. the context of our stochastic matrix, this corresponds using the identity matrix, T. To represent the algorithm with single iteration index k, we map the t-th local update in the r-th communication into the k-th iteration, where k = PT + t. Using the tools previously introduced, we can now reformulate FedAvg (2a)-2c) as the following one-index iterative form:
y: Ry
(Pull model)
(6a)
y = y 7, DR Vf(yk)
(Local update)
(6b)
0h+ Auyt
(Agg. model)
(6c)
where the time-varying matrices RE. As. and D3 are defined as
(RSS))
k=r7+1
A A-- [--A(A A(S,)) (r
{
ifi=jes, otherswise
RR
Duli.j]
1
otherwise
otherwise
This diagonal matrix D3 serves to deactivate unparticipated workers and the server during local updates. S, is the set of participated clients" indices at round r, which can be determined by the iteration k i.e., rT < k < + 1)r. An illustration of this process using graphs is shown in Figure
In the decentralized optimization literature, is common represent parameters and gradients V (z()) row vectors (dimension 1 d). This allows the graph mixing operation, defined by a matrix W E R (N+1) be concisely expressed as W we.
5

---

Update r times
Model (row style)
Pull Model
2
2
2
Iteration è = r7 +1
Iteration rT ... PT
Iteration k (r + 1)r
(Finish round and make sample for round)
Figure 2: Represent FedAvg using graphs. The dashed line means communication.
Mixing Matrices in FedAvg, feasible to further condense (6a)-6c 66 into single-line form
Ik+1 =W fxx))
(8)
The specific selection of Wa detailed in the Appendix. But WR cannot be doubly stochastic matrix unless it is full client participation case. Consequently, the theorem presented in Koloskova al. 2020] is not directly applicable FedAvg this context.
Convergence Result of FedAvg with Arbitrary Participations. In the appendix D we provide a new proof of FedAvg under the arbitrary participation scenario through this decentralized optimization formulation. When the algorithm - oo, the limiting point of FedAvg is around an irreducible neighborhood depending the local update steps т, data heterogeneity og and the extra bias 8? introduced due to non-uniform participation probabilities. This motivates us to develop a new FL algorithm capable of addressing and eliminating all aforementioned errors and biases.
Local Update y) times
Push Gradients y (column style)
Pull Model
3
Iteration +1
Iteration kt rr 2,
lteration (r+ 1)r
(Finish round
new sample round)
Figure 3: Illustration of our new FOCUS algorithm. There are two key differences from FedAvg style algorithm. One is it pulls the model variable æ but pushes the gradient variable and another is the push matrix the column stochastic matrix instead of the row stochastic.
4.2 FOCUS Corrects Arbitrary Client Participation and Local-Update Bias
4.2.1 Push-Pull Strategy for FL Settings
To eliminate the biases introduced by arbitrary client participation, we move beyond heuristic designs and adopt formal optimization framework. This involves reformulating the FL problem as constrained optimization task, structure commonly employed decentralized algorithms:
min (Ro.P 3N F(x) = En f((x,)
(9)
s.t.
R(S,)æ= V S,
(10)
Note a minor but critical difference from the formulation IT) is that there are + model parameters I; applied in each local cost function f. instead of single To see the equivalence between this and ( notice R(S,)æ w = æ implics z; = Zo, Vi E S,. Consequently, the union of all sampled client sets {5,) covers the entire client population, then all individual client models and the server model are constrained to converge to the same state.
This formulation motivated us to explore a primal-dual approach to solve this constrained problem. Among the various primal-dual-bast decentralized algorithms, the push-pull algorithm aligns particularly well with the Fl. setting. It is characterized by the following formulation:
#b++ = R(xx T)&3k)
(11)
MR+1 = =C( (x(++t)) - vf(x))),
(12)

---

Algorithm 1 FOCUS: Federated Optimization with Exact Convergence via Push-pull Strategy
1: Notation: 2, and Yr are the server's 's values while o2,3 and yis are clients' values.
2: Initialize: Choose learning rate 7 and local update т. Server randomly chooses zy and sets
Uo = 0. All clients initiate with V (=x = Vo.i
3: for o......: R- R-1 do
....,
4: Get S, an arbitrary client participation index set
5: for in S, parallel do
6:
T0.i = Ir: yo. +
Pull xy (No need to pull yr)
7:
1 do for t 0,...
8:
Vi+1, Vi.;
Vf((()))) V
b See ff((( around 22
(t) (.))) WiFL,
9:
s 14,1
end for
11:
end for
12: Ur+1 < yr + Eies, v
b Push V (Not Averaged)
13: Tr+11 = 1/8+++
14:
end for
where Yu V f (2)), and R and C represent row-stochastic and column-stochastic matrices, respectively. The algorithm name "push-pull" arises from the intuitive interpretation of these matrices. The row-stochastic matrix R can be interpreted as governing the "pull" operation, where each node aggregates information from its neighbors. Conversely, the column-stochastoe matrix C' governs the "push" operation, where each node disseminates its local gradient information to its neighbors. Moreover, recalling the definition of row and column stochastic matrices R1 and 1 1CC = 1", push-pull algorithm has the following interesting properties:
Ra" T yv = f (mx), Vk:
(consensus property)
(tracking property)
where x² is the fixed point of the algorithm under some mild conditions on the static graph R and C. The first property, consensus, implies that all workers' model parameters eventually converge to common value. The second property, tracking, indicates that the sum the variables (aggregated across workers) approximates the global gradient, ensuring the algorithm's 's iterates move in a direction that minimizes the global loss function. It is worth pointing out that when consensus is reached such that all relevant local models in æ equal some the sum of the local gradients 1L ((gg) becomes
exactly NV (Z). For more details, we refer the readers to Pu et al. 22020). Xin and Khan 2018
We are interested in solving the optimization problem with multiple constraints problem (9-(10) The original push-pull algorithm is not sufficient. Analogous to the approach taken the FedAvg section, Here, extend it the time-varying matrices R₂ and Cn model the client sampling and local update processes, respectively. These modifications lead to the following algorithmic formulation:
(10).
1k++1 = R4 DD)y))
(13)
2k+1 CC Vf vf(x))),
(14)
where the definition of Rs is the same as the one in FedAvg and Cs = R. while Dr is slightly different from 7 about the server's s entry. D* [0.00 representation of this algorithm is shown in Figure
lifk = rT + otherwise O. The graph
4.2.2 Convert Vector-Matrix Form Back To FL-Style Algorithm
Substituting the definition of the mixing matrix into (1) and 14). we will get concrete FL algorithm as listed in Algorithm I with non-trivial transformations. The steps to establish this new FL algorithm effectively reverses the process outlined in the previous subsection. Here we provide a few key steps. First, it is straightforward to verify that T& and yk, are not moved if the client is not participating in the corresponding round, so we will ignore them in the next derivation. At the beginning of the r-th round, i.c. k + becomes
Th+ 1,0 T 7/31.0
(server updates)
(15)
"The code is available at hhtpps:: / //g thub. com/ Bi named Federated Learning for Arbitrary Sampling and Local Update (FedASL). The acronym ASL also stands for the Adaptation System Laboratory UCLA and EPFL, where Dr. Ying completed his Ph.D.
The algorithm was originally
7

---

2k+1, & 100 Vi E Sr
(client pulls model)
(16)
While at the end of the r-th round, ie. (r + 1)T,
14] becomes
3/411 Uh V[((I++1,1) V (srk,)))
Vi S
(17)
yk+1, = yk.o Σ Vetia
(server collects info)
(18)
E,
Mk+1, - 0, ViES S,
(client resets yks)
(19)
Note that we introduce temporary variable 14 because the matrix multiplication Cß is applied on the updated value v instead of yı: directly. During local updates, the server does not update the value while the client executes the local update in the gradient tracking style:
1k+1, - 1iyk,
(20)
1/++,, yk. + V (((TKL1))) V (z(aa))
(21)
Next, we revert the standard two-level indexing used in FL by mapping the single iteration index k = rT + to the r-th iteration and i-th local update step and replacing 1k+1, by 2t,
Finally, assembling all the above equations together and switching the order of x and y. we arrive at the FOCUS shown Algorithm T k rT, the y-update becomes
Because of the switched order, at the beginning of each round, i.e.
1 - (a())) (.((al)))))
(22)
Note that in the original update rule 21.. the gradient V (xxx.)) is computed in the preceding step and then reused, thus avoiding redundant computation at the current step. This principle of gradient reuse carries over directly to the two-level index notation. Recall that si, will not change the
worker does not participate. Hence, we can establish, by induction, that (= corresponds to the stored gradient from the end of the most recent round in which the worker participated.
Performance Analysis
Now ready present the necessary assumptions and convergence property for FOCUS. Due to limited space, all proofs are deferred to Appendix E
Assumption 2 (L Smoothness). All local cost functions f, are L L-smooth, i.e. f((x) S f(()) (x y. (v))
|| 2/12.
Assumption 3 (trong Convexity). All local cost functions Si are p-strongly convex, that is, [i(x) 2 (w) (x - y, V(((v)) + - 1-|l-~1 10l--ll"" y||².
Assumption 4 Conditio... The global loss function F satisfies the Polyak-Lojasiewin condition [[V(()]] 2 (F(z) - F*), Vx, where 3 > and F the optimal function value.
Theorem Under arbitrary participation assumption 7 and L L-moohhhsssss assumption proved that FOCUS converges at the following rates with various extra assumptions on fü:
can be
3/2
μ Strongly Convex: Under extra assumption
in S min 27N 31(5-1) 8L
4ma
[ xx
< VR S (1 muN/2) "
(23)
3/2
3 3-PL Condition: Under extra assumption if < min
3quin 32N
goni
Qmin
guin BLVN
128N
161
E F(
F* S Φ2 - (1 - 11 R 2
(24)
3/2
General Nonconvex: Under no extra assumption, if S minf 21(
9min BLVN
Puin
16L 41.
R-1
8(f(z))-f*)
Σ
(25)
R P=0
nNR
x+1 + 81T 15 Ø 11 where the Lyapunov funntions V, = E Trr+1
Φ = F(ārr4))) - Ft (1 4nL2)
E
Xrr 2 and qmin min, qi
8

---

Remark. Note the top two error terms are exponentially decayed, which implies the iteration complexity is (1log(1/e) /c)). For the general non-convex case, we improve the typical 1 1/v R rate into 1/R thanks to the exact convergence property. See the comparison of our proposed algorithm with other common FL algorithms in Table 1 (1/2²) > ((1/c) > ((log(1/c) in terms of communication and computation complexity. Table I highlights the superior performance of FOCUS, which achieves the fastest convergence rate in all scenarios without particular sampling or heterogeneous gradients assumption.
Numerical Validation. To validate our claims, we conducted numerical experiment using synthetic data since this is the common approach to verify the exact convergence property. The results, presented in Figure 4 were obtained by applying the algorithms to a simple ridge regression problem with the parameters d 100, N 16, K = 100, X 0.01, and т
The loss function is F(x) - 인े E Ex= ||[_ x - b,,e + \||=||/ 2 All algorithms employed the same learning rate, " = 2e 4. Three distinct sampling scenarios were examined: full client participation, uniform participation, and arbitrary participation. Notably, our FOCUS exhibits linear convergence and outperforms the other algorithms in all scenarios, particularly under arbitrary participation.
10"
Full Client Particpation
Unfoom Particiption
Artiraary Partic pation
10
0.1
10²
10
16
0.0
10¹
10"
10"
clent Itent_Index Index
FOCUS
10
FOCUS
10"
FOCUS.
Fadffgg
Fadheg
Faeting
10
SKA FOLD
FodAU
10
FidhU
FOLF
10"
Fedhi
SCA
10"0
Pronthip
Prodias
Practiop
MFA
MITA
MIFA
80 100
190
200
250
120
200
330
400
500
100
200
300
400
500
Communication per Model Sizw
Commuricaioo Cost per Model S.m
Communication Cood per Model Suw
Figure 4: Convergence performance comparison of various FL algorithms. Under full client participation. FedAvg, FedAU, and MIFA exhibit identical performance, as do SCAFFOLD and ProxSkip. due to their theoretical equivalence this setting. FedAvg and FedAU fail converge to the optimal solution across all scenarios because their inherent error and bias cannot be climinated using fixed learning rate. Prox diverges under uniform and arbitrary participation, as it is not designed for these conditions. We do not understand why MIFA diverges but it works in ML applications. While SCAFFOLD converges in all cases, our proposed algorithm, FOCUS, demonstrates faster convergence, especially under arbitrary participation.
5.1 Why FOCUS Can Converge Exactly for Arbitrary Participation Probabilitie?
At first glance, the ability of FOCUS to achieve exact convergence under arbitrary client sampling prob- abilities may appear counterintuitive. Unlike other approaches, FOCUS neither requires knowledge of the specific participation probabilities nor necessitates adaptively learning these rates. The sole prerequisite for convergence is that each client maintains non-zero probability of participation. Plus, the push-pull algorithm was never designed to solve the arbitrary sampling problem.
From an algorithmic perspective, FOCUS closely resembles the delayed/asynchrroous gradient descent algorithm even though it is derived from push-pull algorithm to fit the FL scenario. To see that, leveraging the tracking property of the variable yı. and special construction of matrix Cs. we can establish that the server's yr+1 Ei (((aaa+ Due to arbitrary client participation, at the iteration k TR+1, may hold some old version of the server's model if it does not participate. Thus, we arrive at an insightful conclusion: FOCUS effectively transforms arbitrary participation probabilities into an arbitrary delay in gradient updates. Hence, any client participation scheme, as long as each client participates with a non-zero probability, will still guarantee exact convergence.
5.2 Extension to Stochastic Gradients and ML Applications
In practical machine learning scenarios, computing full gradients is often computationally prohibitive. Therefore, stochastic gradient methods commonly employed. Our proposed algorithm can be readily extended to incorporate stochastic gradients, resulting in the variant SG-FOCUS. However, due to space constraints, we focus on the deterministic setting in the main body of this paper. A comprehensive description of SG-FOCUS, along with its convergence analysis, is provided in Appendix [F The appendix also benchmarks SG-FOCUS's 's performance on the CIFAR-10 10 classification task, highTighting its faster convergence and improved accuracy over other FL. algorithms. This performance trend echoes that of its deterministic counterpart.

---

Theorem 2 (Informal Convergence Theorem of SG-FOCUS). Under arbitrary participation assump- tion] 7 L-Smoothness assumption 2 and unbiased and bounded variance assumption on stochastic gradient (See assumption O in appendix F.. it can be proved that SC-FOCUS converges at the following rates with various extra assumptions on f;: - u-Strongly Convex: Under extra assumption 3 for sufficiently small learning rate TJ, we have
I'R S (1 (1- (1-222
7uN 2
R To
+ 4(9min + 2
110
(26)
J.N Umin
where the Lyapunov functions := ==
x²12 [|
(1 8n S/1)2 ( 1)++1
2 ( I and is the variance upper bound of the stochastic gradient noise.
3-PL Condition: Under extra assumption 4 for sufficient small learning rate n, we have
L + 32(T 1)2 +
QR 511- - 1n.3)332282 +
(27)
2
Umin
3
where 2r == F(ār++1) - F* + 4, E | (T( 1)r-1)r
General Nonconvex: Under no extra assumption, for sufficient small learning rate n,, we have
R-1
8(F(3)) F*)
8N2
Σ EI
22N + (N - (-8))))mmi
1"002
(28)
R Y=U
nNR
See the formal statement and the proof in Appendix
Remarks on Linear Speedup. A common expectation in FL theory is the demonstration of linear speedup in the convergence rate, where the rate scales proportionally with the number of clients, N. By inspecting the general non-convex convergence rate in Theorem [ we see the error residual term is ((1(())RR) Yet, the stability of FOCUS necessitates a learning rate ry that restricted by (1/NN) This N dependence cancels out. We want to highlight that this result is expected. The linear speedup typically holds when is used to average out stochastic noise (like Stochastic Gradient Descent variants). Since FOCUS is exact algorithm, it does not introduce this stochasticity, and therefore, is natural that the linear speedup benefit from increasing the number of clients is not reflected in the convergence bound. In contrast to the analysis of FOCUS, the convergence rate of SG-FOCUS in the general non-convex setting does indeed reflect the benefits of client aggregation. Specifically, by setting the learning rate 7) to (1/N), the stochastic variance term diminishes proportionally to (L/NN), which confirms the presence of the linear speedup.
6 Conclusion
This work addresses the critical challenges of arbitrary client participation and client drift in Fed- erated Learning, two factors that prevent traditional algorithms from achieving exact convergence. By introducing a novel framework based on stochastic matrices and tmeevaryinng graphs, we model these dynamics and reformulate the FL problem constrained optimization task. This principled approach, moving beyond simple heuristics, led to the development of FOCUS, an algorithm derived from the push-pull optimization strategy. Our theoretical analysis and numerical experiments demon- strate that FOCUS can achieve exact linear convergence under any client participation scheme, without needing to know learn participation probabilities. The extension to stochastic gradient setting, SG-FOCUS, further validates its practical effectiveness.
Limitations The arbitrary client participation modeling used in the proof of this paper did not consider the Markov process, i.c., the client participation probabilities depend on the participation status in the last round. We believe that FOCUS still converges exactly under this scenario since the stochastic matrix modeling and push-pull strategy still hold for any realizations. However, the extension of the proof is non-trive non-trivial due to the correlation between stochastic matrices. We leave this and a more general arbitrary participation scenario for future research directions.
Future Works. The framework of stochastic matrices and time-varying graphs provides novel tool for modeling arbitrary client participation and local update dynamics in FL. By leveraging this approach, we establish formal connection between FL and the rich field of decentralized optimization. While this paper focused on FedAvg and the Push-Pull algorithm as initial examples, a promising avenue for future research is to adapt other sophisticated decentralized algorithms.
10

---

Acknowledgement
The authors gratefully acknowledge Edward Duc Hien Nguyen and Xin Jiang for the discussion that inspired the connection between time-varying graphs and client sampling. Research reported in this publication was supported by the National Institute Of General Medical Sciences of the National Institutes of Health under Award Number (6GM159671) The content is solely the responsibility of the authors and does not necessarily represent the official views of the National Institutes of Health.
References
M. Assran, N. Loizou, N. Ballas, and M. Rabbat. Stochastic gradient push for distrihuted deep learning. In International Conference on Machine Learning, pages 344-353, PMIR, 2019.
T. M. Beltrán, M. Q. Pérez, P. M. Sánchez, S. Bernal, G. Bovet, G. Pérez, G. M. Pérez, and A. Celdrán. Decentralized federated leaming: Fundamentals, state of the art, frameworks, trends, and challenges. IEEE Communications Surveys & Tutorials, 2023.
F. S. Cattivelli, C. G. Lopes, and A. H. Sayed. Diffusion recursive least-squares for distributed estimation over adaptive networks. IEEE Transactions on Signal Processing. 56(5):1865-1885) 1877, 2008
J. Chen and A. H. Sayed. Diffusion adaptation strategies for distributed optimization and learning over networks. IEEE Transactions on Signal Processing, 4308):428944305, 2012. 2012.
A. Defazio, F. Bach, and S. Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in neural information processing systems, 27, 2014.
M. Fang. Z. Zhang, Hairi, P. Khanduri, J. Liu, S. Lu, Y. Liu, and N. Gong. Byzantine-robust decentralized feder- ated learning, In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, pages 1874-2888, 2024.
X. Gu, K. Huang. Zhang, and L. Huang. Fast federated learning in the presence of arbitrary device unavailability. Advances Neural Information Processing Systems, 34: 10522-12064, 2021.
R. A. Horn and C. R. Johnson. Matrix analysis. Cambridge university press, 2012.
X. Huang, P. Li, and X. Li. Stochastic controlled averaging for federated learning with communication compression. In The Twelfth International Conference on Learning Representations, 2024. URL https //openreview. net (otd//orrmddddd/2pp
D. Jhunjhunwala, P. Sharma, A. Nagarkatti, and G. Joshi. Fedvarp: Tackling the variance due to partial client participation in federated learning. In Uncertainty in Artificial Intelligence, pages 906-916. PMLR, 2022.
R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26, 2013.
P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. Bhagoji. K. Bonawitz, Z. Charles, G. Cormode, R. Cummings. et al. Advances and open problems in federated learning, Foundations and trendy@ in machine learning, 14(1-2):1 11111)211211,, 2021.
S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. T. Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International conference on machine learning, pages 5132-5143. PMIRR 2020.
A. Koloskova, N. Loizou, Borciri, M. Jaggi, and S. Stich. unified theory of decentralized sgd with changing topology and local updates. International Conference on Machine Learning, pages 5381-5393, PMLR, 2020.
A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. 2009.
A. Lalitha, S. Shekhar, Javidi, and Koushanfar. Fully decentralized federated learning. In Third workshop on bayesian deep learning (NeurIPS), volume 2, 2018.
G. Lan, S. Lec, and Y. Zhou. Communication-cffiiti algorithms for decentralized and stochastic optimization. Mathematical Programming, 180(1):237-284, 2020.
X. Li. K. Huang, W. Yang. S. Wang. and Z. Zhang, On the convergence of fedavg on non-iid data. In International Conference on Learning Representations, 2020. URL https: http::::/ppp///e///eee net/forum? id=H>xNAnVEDS

---

Z. Li, W. Shi, and M. Yan. A decentralized proximal-gradien method with network independent step-sizes and separated convergence rates. IEEE Transactions on Signal Processing, 65517))44444500 2019.
Z. Li, S. Nabavirazavi, B. Ying, S. Iyengar, and H. Yang. Fast: A lightweight mechanism unleashing arbitrary client participation in federated learning. In Proceedings of Internatioonal Joint Conference Artificial Intelligence, pages 5644-5652, 2025. httpp://pp/
10 http1/0022993/jaaa... 2025/628
X. Lian, C. Zhang, H. Zhang. C.J. Hsieh, W. Zhang, and J. Liu. Can decentralized algorithms outperform centralized algorithms?
study for decentralized parallel stochastic gradient descent. Advances neural information processing systems. 30, 2017.
B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communication-effine learning of deep networks from decentralized data, Artificial intelligence and statisties, pages 1273-1282. PMLR, 2017.
C. D. Meyer. Matrix analysis and applied linear algebra. SIAM, 2023.
K. Mishchenko, G. Malinovsky, S. Stich, and Richtárik. Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally! In International Conference on Machine Learning, pages 19750-15700 PMLR. 2022.
A. Nedić and A. Olshevsky. Distributed optimization over time-varying directed graphs. IEEE Transactions on Automatic Control, 60(3):601-615, 2014.
A. Nedic and A. Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48-6 61, 2009.
A. Nedic, A. Olshevsky, and W. Shi. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27(4))2597-2633, 2017.
D. H. Nguyen, Jiang, B. Ying, and A. Uribe. On graphs with finite-time consensus and their use in gradient tracking. SIAM Journal on Optimization, 35(2):872-898, 2025.
Pu, Shi, J. Xu, and A. Nedić. Push-pull gradient methods for distributed optimization in networks. IEEE Transactions on Automatic Control, 66(1);1-16, 2020.
E. K. Ryu and W. Yin. Large-scale convex optimization: algorithms & analyses via monotone operators. Cambridge University Press, 2022.
F. Saadatniaki, R. Xin, and U. A. Khan. Decentralized optimization time-varying directed graphs with row and aallum--ttccastti matrices. IEEE Transactions on Automatic Control, 65(11):4769 4780, 2020.
A. H. Sayed al. Adaptation, learning, and optimization networks. Foundations and Trends in Machine Learning, 7(4-5):311-88) 2014.
W. Shi, Q. Ling, G. Wu, and W. Yin. Extra: An exact first-order algorithm for decentralized consensus optimization. SIAM Journal Optimization, 25(2):944 966, 2015.
Y. Shi, L. Shen, K. Wei, Y. Sun, B. Yuan, X. Wang, and D. Tao. Improving the model consistency of decentralized PMLR, 2023.
federated learning. In International Conference on Machine Learning, pages
J. Wang, Q. Liu, H. Liang, G. Joshi, and H. V. Poor. Tackling the objective inconsistency problem in het- erogeneous federated optimization. Advances in neural information processing xystems, 33:761 1-7623, 2020.
L. Wang. Y. Guo, T. Lin, and X. Tang. Delta: Diverse client sampling for fasting federated learning. Advances in Neural Information Processing Systems, 36, 2024.
S. Wang and M. Ji. A unified analysis of federated learning with arbitrary client participation. Advances in Neural Information Processing Systems, 35:19124-19137 2022.
S. Wang and M. Ji. A lightweight method for tackling unknown participation statistics in federated averaging. In The Twelfth International Conference on Learning Representations, 2024, URL htttttt///p/eereeeeet 2KEFKKKKK
M. Xiang, S. loannidis, E. Ych, C. Joc-Wong, and L. Su. Efficient federated learning against heterogeneous and non-stationary client unavailability. Advances in Neural Information Processing Systems. 17:108211-04432, 2024.
R. Xin and U. A. Khan. A linear algorithm for optimization over directed graphs with geometric convergence. IEEE Control Systems Letters, 23))315-320, 2018
12

---

B. Ying, K. Yuan, Y. Chen, H. Hu, P. Pan, and W. Yin. Exponential graph is provably efficient for decentralized deep training. Advances in Neural Information Processing Systems, 34:13975-13987, 2021.
K. Yuan, Q. Ling, and W. Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3):1835-188 2016.
K. Yuan, B. Ying, X. Zhao, and A. H. Sayed. Exact diffusion for distributed optimization and learning- i: Algorithm development. IEEE Transactions Signal Processing, 67(3):708-723, 2018.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
This is theoretical paper and all the claims are provided with rigorous proof.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We add a limitation subsection at the end of this paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
All assumptions clearly stated and referenced in the statement of all theorems.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide the source code to verify the algorithm.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [Yes]
Justification:
We provide the source code to verify the algorithm.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/
sttpaiisssooooiocyyy. for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have appendix to disclose the experiment details and provide the source code to verify the algorithm.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: eтror.
We focus on the optimization problem and it can converge exactly without any
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
16

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: This is a theoretical oriented paper. The experiment is quite easy to be reproduced by any CPU or GPU resources.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
The authors have made sure to preserve anonymity.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cited the original paper that produced the code package or dataset in the end of appendix.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [No]
Justification: We don't 't have any LLM in this paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy fattps://neurd/: httppp////////oofeeeeee///////// for what should or should not be described.
20

---

Appendix
Review Decentralized Algorithms
21
B Conventions and Notations
22
Brief Review about Stochastic Matrices and their Properties
23
D Proof of the Convergence of FedAvg under Arbitrary Client Participation
24
D.1 Reformation and Mixing Matrices
25
D.2 Convergence Proof
26
D.2.1
Descent Lemma
27
D.2.2 Consensus Lemma
28
D.2.3 Proof of Convergence Theorem
29
E
Proof of the Convergence of FOCUS
30
Reformulate the Recursion
30
Useful Observations
................................
30
3 Descent Lemma for FOCUS
31
Consensus Lemma for FOCUS
33
Proof of the Convergence of FOCUS (μ-Strong Convexity)
34
E.6 Proof of the Convergence of FOCUS (Non-Convexity with PL Assumption)
35
E.7 Proof of the Convergence of FOCUS (General Non-Convyxity)
36
Extensions to Stochastic Gradient Case (SG-FOCUS)
38
Descent Lemma for FO-UUCUS
38
F2
Consensus Lemma for SG-FOCUS
40
Proof of the Convergence of FOCUS (j--Strong Convexity)
42
Proof of the Convergence of SG-FOCUS (Non-Convexity with PL Assumption)
42
F.5
Proof of the Convergence of SG-FOCUS (General Non-Convexity)
44
Supplementary Experiments for SG-FOCUS
45
G.1
Experiment Setup
45
G.2
Experiment Results of SG-FOCUS
46
A
Review of Decentralized Algorithms
The most widely adopted decentralized algorithm is decentralized gradient descent (DGD) [Nedic and Ozdaglar lar 2009, Yuan et al.) [2016). along with its adapt-then-combing version diffusion algorithm [Cattivelli et al., 2008 Chen and Sayed| 2012). It is also a distributed algorithm where multiple workers collaboratively train a model without sharing local data. In contrast FedAvg, DGD has three key distinctions. First, it operates without a central server, instead, workers communicate directly with their neighbors according to predefined network topology [Nedic and Ozdaglar 2009 [Sayed et al. 2014 Lian et al. 2017). Second, rather than relying on server for model aggregation and synchronizing models, workers keep their local models, which differ (slightly) from each other typically. In each iteration, they exchange and combine model parameters with their
21

---

neighbors through linear combinations dictated by the network structure. This process can be formally expressed as
k -kki - V (
(Local Update)
(29)
1 Σ wa
(Graph Combination)
(30)
JENS
where a stands for the i-th worker's parameters at the k-th iteration, the set Mv represents the neighbor's indices of worker i, and the non-negative weights wx,i satisfy Ejev, W.jj for all i. Third, the algorithm is typically written as a single for-loop style instead of a two-level for-loop representation. is straightforward to incorporate the multi-local-update concept into decentralized algorithms. However, it is not popular in the decentralized community.
14+111
Σ SEAG
Wi Wiy(ank (V(()())))
Mi = (1.3)
Figure 5: An illustration of Decentralized Gradient Descent.
It is well-known that the DGD with fixed step size only converges to (((r)-sizee neighborhood
of the solution the original algorithm (Yuan et al. 2016). This resembles the FedAvg algorithm exactly. Subsequently, several extract decentralized optimization algorithms have been proposed, such as Extra (Shi et al., 2013), exact-diffusionNNIDS Yuaan et al. 2018 Li et al. 2019]. DIGing/Gradinn tracking [Nedic et al. 2017), etc. The key advancement of these algorithms is their capability to achieve extra convergence under a fixed step size. They formulate the original sum-of-cos problem into a constrained optimization problem and then apply the primal-dual style approach to solve the constrained problem Ryu and Yin 2022].
While it is common in the analysis of decentralized algorithms to assume a static and strongly connected underlying graph structure, significant body of research also investigates varying graph topologies [Lan et al. 2020 (Saadatniaki et al.) 2020 Assran et al. 2019 Ying al. 2021 Nguyen et al. 2025]. These studies often adopt one of two common assumptions regarding the dynamics of such graphs: either the union of graphs over any consecutive iterations the expected graph strongly connected (Nedić and Olshevsky 2014 Koloskova et al. 2020). Whereas previous research time-varying topologies often relies specific graph assumptions, this paper takes different approach. We model client sampling and local updates using a graph representation, thereby avoiding any presuppositions about the underlying graph structure.
Lastly, we want to point out that this work focuses quite differently from the decentralized FL work [Beltrán et al. 2023 Shi et al. [2033] Fang et al. 2024], which is more closely related to decentralized algorithms instead of FL settings.
B Conventions and Notations
Under the decentralized framework, it is common to matrix notation. We adopt the convention that the bold symbol, such as æ, is the stacked vector and the normal symbol, such as æ, is the vector. With slight abuse of notation, we adopt the row vector convention and denote that
fo(IK.0) V (
I
Ik.1
N+ixd Vf(*x)= =
N+Ixd
N
V VFN(F))))
Vo((ā)) fā()
ff(
N+1xd
(Tx))))
22

---

where 1 is an all-one vector. Note that in Vf(x;), each entry uses different f; and Tk,i- Similar usage for y& as well. Except for æ, y. and f,, other vectors are standard column vectors. Unlike most matrix conventions, the index of the matrix element starts from 0 instead of I in this paper since we set the index represent the server. Another common identity we used in the proof
NVF = (1v))
(31)
This be easily verified when substituting the definition of F. The rest usage of symbols is summarized in 2
Table 2: Notations in this paper
Notation
Meaning
Index of clients
k
Index of iterations
r
Index of communication round and r |k/T]T
T
The number of local update steps Indices set of clients sampled at r-thh round Model parameter dimension
S
d
U.
q
Uniform / Arbitrary weighted averaging vector
fi,
F
Local and global loss function
R.
V
Some row stochastic matrix
C
Some column stochastic matrix
In this paper, || denotes (induced) & norm for both vector and matrix usage while the Frobenius norm.
||
||| denotes
C Brief Review about Stochastic Matrices and their Properties
Before applying the formalism of stochastic matrices to FL algorithm, review the key properties of row- and column-stochastic matrices, as a clear understanding of these concepts essential for the analysis that follows. There are three different types of stochastic matrices.
1. A row stochastic matrix, also called right stochastic matrix, is square matrix of nonnegative real numbers denoted R E R2X", with each summing i.e., R1 1, where denotes the all-ones vector of size
2. A column stochastic matrix, also called left stochastic matrix, is square matrix of nonnega- tive real numbers denoted as C' E Raxn with each column summing to i.e., 1 1T.
3. A doubly stochastic matrix is square matrix W E |R that is both stochastic and column stochastic, i.e., P1 = 1 and TW=1"
A row-stochastic matrix exhibits consensus property. By the definition of row stochastic matrix Rt we know R1 = 1. the matrix R is also primitive, the strictly less than Consequently, the recursion
Consensus property of Row Stochastic matrix
theorem guarantees that all its other eigenvalues have magnitude
1k+1 Rock where vo R.Nx
(32)
converges to consensus vector, Do == lim The where all elements of 2xo are identical. However, unlike the doubly stochastic matrix case, &xo + 111 T 2o in general. Suppose that the corresponding left eigenvector of R with eigenvalue is that is. p = p.. Then, is easy to show that
= lim R R= = T Ø0
(33)
In general, the Perron vector p not a uniform vector 1 Hence, the recursion row stochastic matrix typically converges to the consensus value of some weighted average of initial values.
23

---

To provide some concrete examples, consider the following row stochastic matrix:
0
1
07
0
0
0
1
0
R
10
(34)
2
0
2
0
1
0
0
1
1
0
1
0]
That is p- [0.5, 0, 0.5, 0j in this case.
Mass preservation property of Column Stochastic matrix A column-stochastic matrix exhibits properties markedly different from a row-stochastic matrix. While repeatedly multiplying a vector by row-stochastic matrix leads to consensus, this is generally not true for a column-stochasto matrix.
Instead, column-stochastic matrices possess crucial property we call mass (or information) preser- vation. To understand this property, consider the following recursion:
(35) Note the subscript in Cg indicates that a different column-stochastic matrix can be applied at each step k of the recursion. If we imagine that each element #o(1) represents the mass of the i-th object, then the recursion Ø++1 Cg can be interpreted as a mass redistribution process where the total mass is conserved at every step. To see that, left multiplying the to both sides of above equation we get
Fk++1 = CgaFE where 20 E R
1 1 1+1+1 Cha = 1
(36)
By induction, can conclude 1 1 1 1xx Vk.
Finally, since a stochssttochastic matrix both row- and column-stochasse it automatically inherits both of the properties discussed above. Combining the consensus consensus-driving property (from being row-stochastic) with the mass-preservation property (from being column-stochastic) allows us to recover (unbiased) average consensus. The recursion converges an average consensus, where every element of the final vector is equal to the average of the elements in the initial vector.
D Proof of the Convergence of FedAvg under Arbitrary Client Participation
This section presents a convergence analysis of the FedAvg algorithm with an arbitrary sam- pling/participation scheme. We focus the strongly-convex case with a constant step size since this setting best illustrates the impact of client drift induced by local updates and bias introduced by non-uniform sampling. The following proof draws inspiration from and synthesizes several existing works [Wang and Ji. 2022 Koloskova et al. 2020 Li et al., 2020). adapting their insights decentralized framework. Leveraging this framework, we are able to present more concise proof and provide a clearer conclusion. Unlike FOCUS, most FL algorithms require an extra bounded heterogeneity assumptions:
Assumption 5 (Bounded Heterogeneity). For any x and the local cost function Ji [V Fx)) < GG.
We further introduce a quantity, denoted as 62. to bound the discrepancy between the unbiased gradient average and that resulting from arbitrary distribution.
Vf(=))=)u)) v)V)())) $ 5 Vz.
(37)
where TI is uniform distribution vector: + 1, 1, 1] and gJ [0, Qı 92. Nv]. the one
introduced in Assumption
1 This quantity 5² must exist because 8² S o due Jensen's 's inequality
N VF(x) E q. (f())) VF(Ex)) o.. If u. i.c. the uniform
sampling case, 44
Theorem 3 (Convergence of FedAvg Under Arbitrary Activation). Under the assumption $ when the learning rate satisfies min 37. 1)-E) the limiting point of FedAvg satisfies:
and 5
lim sup E E| x=1 80nî x² L2 ( (5 + + K0000
10s8
+ +1677² //(// o%),
client drift by local update biased sampling
data heterogeneity
where To g xx. x² is the optimal point of [I and k L/ p is the condition number.
24

---

Remark of Theorem 3, Each of these three terms possesses a distinct interpretation. Notably, when I, indicating a single local update step, the first term, representing client drift introduced by local updates, vanishes. Both the first and third terms are scaled by the step size, 1,, implying that their magnitudes can be controlled and reduced below an arbitrary threshold, 6, by employing sufficiently small step size. The second term, however, is constant related to the non-uniform sampling distribution and is, therefore, independent of the learning rate. This term underscores the significant impact of non-uniform sampling the convergence behavior. Even under the simplified conditions of T = 1 and uniform sampling, FedAvg fails to converge to the optimal solution unless the objective functions are homogeneous. This observation aligns with previous findings that diminishing learning rate is necessary for FedAvg to achieve exact convergence.
D.1 Reformation and Mixing Matrices
First, we rewrite the FedAvg algorithm using the decentralized matrix notation as introduced before:
yx+1 =R
(38)
x++1 A4
(39)
where both Rg and Ag are row-stochastic matrices, and they are some realizations of random matrices representing the arbitrary sampling and D3 the diagonal matrices with value 0 or 1 control the turning on and off of clients. For r local update, it satisfies
Rr R(S,), if =T=
A 1 ( k
((S,), I, otherwsie.
(40)
I, otherwsie.
See the definition of R(S,) and (S,)) in main context and example in Figure 6 A noteworthy observation from [L al. 2020 that FedAvg can be equivalently reformulated without altering the trajectory of the server s model. This reformulation considers activating all devices, where each device pulls the model from the server and performs local update, while maintaining the same of contributing clients for averaging, See Figure 7 as an illustration. Swap the order of x and y update, we arrive at
yx+1 0 - f)(x(())
(41)
0t+1 = Wk
(42)
where Wa row-stochastic matrix:
W₂ {
I, k rr. Yr W(S)), = =r= 1,2,
(43)
To better understand the property of WS,).. we provide few concrete examples of WS,)) Suppose there are clients. Under the arbitrary participation case, each round the number of participated clients is not fixed. Maybe in one round, client and 3 are sampled while in another round, clients 2, and 4 are sampled. The corresponding matrices are
0
1/2
1/2
07
0
1/3
1/3
1/3
0
1/2
0
1/2
0
0
0
1/3
1/3
1/3
W (1.3
=
0
1/2
0
1/2
W(2.3,4)
1/3
1/3
1/3
(44)
0
1/2
0
1/2
0
1/3
1/3
1/3
1/2
1/2
0
1/3
1/3
1/3
It is crucial to observe that Ws. has identical rows for any possible subset Sp. compute the expected value of the entries in any single row.
Thus, it suffices to
Now, we can state the property of W (SS)). ). As the consequence of arbitrary participation assumption show that
1 and previous single row observation,
[- q'
q1
Q2
9N
0
Q
42
UN
W = F =
(45)
...
q"
4 42
[Nd
where the values ys value defined in the assumption. It follows directly that this row vector also left eigenvector of E Ws., i.c. q Ws. = since E; 9, 1.
25

---

0
0
0 1 1 0
Pull Model:
(133))
0
1000
A
0 1 0
0
0
4
1000
1
0
0
T 0
000
000
Push Model:
0
0
0
0000
0
R(133)
0
A(1.3)
0
0
0
2
0
1
1
Figure 6: Illustration of federated learning using graph and mixing matrix. The top row depicts the pull model step, while the bottom row shows the push model and subsequent averaging step.
1
0
0
0
0
0
0
07
Pull Model:
0
0
0
0
0
Rall
0
0
A(1.3)
0
1 0 0
0 1 0
0
0
0
0
2
3
4
0
0
0
O
O
1
0
0
0
07
000
T
2
000
0
Push Model:
0
Rall
0
1 0
A(i,a)
0
0
0
0
1
0
Figure 7: An equivalent FedAvg algorithm as Figure 6 terms of the server model. The difference is that all clients (virtually) pull the model and run the local update but server run the partially average.
D.2
Convergence Proof
As previously discussed, will analyze FedAvg in its decentralized form using the following simplified representation:
yk+1 = V((kk)
(46)
36+1 -ka3
(47)
To start with, define the virtual weighted iterates 3y := g xx. recalling that vector q is the averaging weights introduced in [ssumption[] The crucial observation is that conditional expectation 1v. 2x q " E Ways 9-' yy holds for any k. including both local update step and model average step. When there is no ambiguity, we will just use E for conditional expectation instead of E In..
Expanding the conditional expectation of E [T - x² 1|? we have
Tx++ - x=1 =E | Eū + E8k+1 - x²1
=E Bb+1 Ežs+1ll + [[ - x²
| 7q V - -x*
k k rt
(48)
E | - 4. y 2 || - nu V ( - ==1 k rt,
where the first equality is because the cross term is zero and the second equality holds because E E| - y || = 0 during the local update iterations (k: rT).
The subsequent proof follows a standard framework for analyzing decentralized algorithms. It initially establishes a descent lemma, showing that virtual weighted iterates 7h progressively approach neighborhood of the optimal solution in each iteration. Subsequently, consensus lemma is established, showing that the individual client iterates, T8,i gradually converge towards this weighted iterate Ft. Finally, by combining these two lemmas, will derive the overall convergence theorem.
26

---

D.2.1 Descent Lemma
Lemma (Descent Lemma of FedAvg). Under the assumption 7 holds when the learning rate satisfies 1) S 1
and the following inequality
3L'
Ixx 111 V (ats) - x*1| 5(1
mu
x²11
5
Σ q: T Tx 21
N
+
57
8
(49)
2
Proof: To bound the common descent term
| - "7 f(xx))
x² 11? we have
- r7 V (ax)) - x² 11
-1|08 x=' || r 1 V fa=x)) )1 2n(5a x vf((z))
<||æg - x =01 + 37
v)(x)) - (f ))
+ +37 q (ff(1))) - u ((LE)))
33 VF || 2
27 - -I'
v -f'
<1 11
317
2 L
9 g:ll =x112 + 3n + (n)) F(x*)) -27(Tx x² / fxxx))
(50)
where the first inequality results from Jensen's 's inequality, and the second inequality utilizes (37 and the consequence of L- Lipschitz smooth condition with convex function, we have F(z) F (x
27 [VF((=)]] Yx.
1
Next, an upper bound for the cross term can be given by
2n(āx x².9 V f(x))
-n x², V (x))) + (m - xx, , u [V(())) - (f(()))
S 2fn(F(Fx)) Fxx') + 1 || x= x=1 + ?! T x² 112+ + 2/ Vf()) - fxxx)]
2
/
< NH [ - x= x=112 27 (#x) F(x*))
+ 4n 11 v (T+)
T v v
2
41 || T ( q [vf(=x)))
4n,.2 P
4n
| x² 2 F(x'))
Σ
4:
2
82
(51)
2
where the first inequality is obtained from Young's incquality 2(a, b) S E|la||² + 1|bbl with 1/2. the second incquality is due to Jensen's 's incquality, and the third inequality is obtained by (37). Combining
(50g and
5
we have
1 114 VF(x)) x01"
nj <(1 / 1| - x x0112 + (AL.2 +3n1?
4m
Σ 1=1
qi [+
+
+ 37/
82
1
+ (6n 2n) (F((x)) - -F(z*)
(52)
Letting 17 S min(
31. 3z4 = stz we further have
1
I -ig-ng-Tffaa x11 5(1
TH ||
1=1 +
5nL
Σ
5n +
52
(53)
2
P
where we discarded the (672 2n) - F(x*)) term since it is always negative.
27

---

D.2.2 Consensus Lemma
Lemma 2 (Consensus Error of FedAvg). Under the assumption 7 2 and the following two (weighted) consensus errors hold for any iteration when the learning rate satisfies nj S 1(r-1)1;
Σ
go g TR,ill <81 + Vk
(54)
N
gillex - mu.ll <8n + +Z), Vk Σ
(55)
Proof: To evaluate the consensus error, the key observation is at the model average iteration, i.c., k rT that all clients' model parameters TK,i are the same. Hence, we can express the consensus error by referring back to that point:
N
N
Σ qell R
TK,ill
qi
I
7
q [V - Tko + n
k'=ko
k
k-1
ST 11) 1)
Σ
Σ qi 111 V - vf(
(56)
where kn is the iteration that model averaging is performed, which can be calculated via hi = - The above inequality utilizes Jensen's is inequality and observation that k: Ko S 1. Then, we have
11 T v fx(w)> vf((=
< 4 1/ V)([(((())))))))))) - [ + 4llg"v//(1 - - (
+4 4 | [V - a T ( 2 + 4 1I Vf - {)(()==)))|l ?
4v VSe v)((x)) 12 11. , + 18 + 40
S 4L
ge || 3y 1|2 4L cx I ,112 46 + 402
(57)
where we plus and minus q f(( a T (1(T)) and T [ ,) then apply Jensen's in- equality. Plugging (57) back to (6) we have
k-1
N Zi |zw, - 11 + 48 + 40% -
Ealaa- - II. < 1)
Σ
SL
(58)
k k'=
i=1
Finally, we can establish a uniform bound for the consensus error using mathematical induction.
Initially, note that Σ di aillTa, #2o0.il2= = O. Now, assume that N d:|.Tx x2,,|1² < A for any S Ko + 1, then
Σ 4 Txtt 2kotT, 4n² 17)((22) 1)2 + 5 + =A
(59)
2 (K))
holds when the uniform upper bound of consensus error is
in S 4(r-1)Z then A < STp((T 1) + oz)) Hence,
1- S --
Σ qglla - 11, < -
1)2 17 +
(60)
This upper bound holds for Ts and yk. similarly with only one difference that yı, has more inner iteration before applying the We compared to Zg.
ge gellan - ne. < 76) + +
(61)
28

---

D.2.3 Proof of Convergence Theorem 3
Proof: Combining the above two lemmas, we conclude that for k # rt
T - 1=1 - (1 71/22 - 1=1 401 ( 1, - 1)2
( + 5
(62)
To establish the case l = rT, we need to consider the variance after the local update is done. Through previous established the consensus lemma, it is easy verify that
E [k+1 -9" yk+1 l| =E |1
W -
Mk+1 9 3x++ 11
E W.W,, . [0. :1544111 y'yatall
Σ 9 |1 q 2T
<81)² (6p + oZ)
where the first equality holds because any row in the Ws., is the same, the first inequality applies Jensen's inequality and the last inequality utilizes the consensus lemma. Substituting back (48).
we have for k # FT
Tx-1 - x x012 & - nn/2))/l - ==1 40n 2 (T 1)² (62 + +z) +
5n 02 8n)
(2, + o
K2
1
(63)
We can simplify above two recursion as
Ak+1 <(1 0) Av + B
k x IT
(64)
Ak+1 { - Ax + B +
k = rt
(65)
where A₂ = E E| - x= 1|2 B 10n L2 112 (6)+
5n q'
and = 877² (62 + +z6). Making
it a K-sttep recursion together, we have
[K/T]
Ax S (1-a) Ao + (1- B
Σ (1
(66)
k==0
k'=0
Letting K + oo and substituting back, we conclude
lim supp E |īx 1=1 < x0n22'²' ( 1)' + oZ) 10k8 biased sampling
16172//166 + ad)
K-000
client drift by local update
data heterogeneity
(67)
where we introduce the conditional number x = LL/p-
As we discussed in the main context, these three terms have their own meanings. We can easily establish the following corollaries. Note 8 = 0 under the uniform sampling case. We have Corollary 1 (FedAvg Under the Uniform Sampling). Under the same conditions and assumptions as theorem the convergence of FedAvg with uniform sampling satisfies
lim E || 1²1 < 80n² x² L2 - 1)2 161r /oo
(68)
K-00
Corollary 2 (FedAvg Under the Uniform Sampling and Single Local Update). Under the same conditions and assumptions as theorem satisfies
3 the convergence of FedAvg with uniform sampling and
lim sup E [x
x=112 < 166n72/1ot
(69)
K
Lastly, if the function is homogencous among fú. it implics of = O. Further notice 8 Corollary 3 (FedAvg with Homogeneous Functions). Under the same conditions of theorem 3 FedAvg can converge exactly when fo homogeneous
- 0
lim E | - K
2 =0
(70)
Notably, Corollary 3 hoolds without requiring the assumptions of - = 1 or uniform sampling. This intuitive because arbitrary sampling becomes irrelevant in the case of homogencous functions.
29

---

E Proof of the Convergence of FOCUS
E.1
Reformulate the Recursion
Similar to the proof of FedAvg under arbitrary client participation, we first rewrite the recursion of FOCUS that it is easier to show the proof. Recall that the original matrix-vector recursion is
2k+1 = (æ DDyy
(71)
k =Cx (yv Vf(+++1)) f
(72)
This form is not easy to analyze when noticing the following pattern on the mixing matrix choices:
Iter.
0
T T+1
TT
TT
FT
FT + 1
R&
Init.
R(S1)
R(S2)
R(S,)
C
Init.
C(S))
C(S
R(S,) and C(S,)) are not applied at the same iteration. Even worse, R(S,,) and (Sy)) are random variables and depend on each other. To avoid these difficulties, we switch the order of r- and y updaee and get the following equivalent form:
yk+1 CC
(73)
#k+1 -R yD
(74)
Notice the subscript's modification. The initial condition becomes yo which can be any values. Now, the matrices follow this new pattern
Vf(x=
and æ-1
Iter. Cs R2
2
++1
PT
FT
PT +
Init. R(S.) I
I
C(S R(2
I
C(S--1 R(S,) I
Init.
1
1
With this shift, both the row stochastic matrix (R) and column stochastic matrix (C) operations applied within the same iteration. However, it is crucial to note that these operations do not correspond the same indices of sampled clients, i.e. S, versus S, To further simplify the analysis, we can leverage a technique similar to the one used in the FedAvg proof: considering the collecting full of client y rather than just a subset. This is valid because the yk, of non-participated clients effectively zero. Consequently, we no longer need to take care about the correlation between R and C, significantly simplifying the analysis.
yk+1 =Ck,all yk + Vf(()))) (x(x)))))
(75)
0++1 R4 - DDB
(76)
where the definition of Ck. are
if k: + rt
[
Ck
(77)
if k:
0
0
The rest of proof will use this new form 75
76).
E.2 Useful Observations
Before we proceed with the proof, there are a few critical observations.
Introducing server index selecting vector uR = 0, ... .0,, it is straightforward to verify that the left-eigenvector of R4 for all k:
T
gg Vk.
(78)
We do really need to caleulate the value of yo since will be canceled out in the first iteration.
30

---

Now we denote the F5 parameters and gradient tracker. Utilizing the eigenvector properties and definition of Rg and Da. we obtain
u and Vs = uggis which can be interpreted as the server's model
Z [
k * TT k
yk (1
# rt k rt
1k+1
Uk+1
(79)
mp +11
where Brr+1
1 V ( (rr)) is due the tracking property that
(xxe), and the client's Mrr+1, = for any clients. The main difficulty of the analysis lies in the iteration ST to + 1, ie., the gradient collecting and model pulling step. Given the information before step it can be easily verified that
1 Ml+ Cy Vf(zs) (f(==-)))
(80)
Err+1
3rr Ter 1P
q: Brr+1 - Irr,all = [[Err++ xrr
(81)
N
E 11 xrr+1lll
(1 - 2r Irr,ll? = ||ā xrrl11
(82)
where the first equation means the difference between the model before pulling and the server's s model, and the second equation means the difference between the clients' models after pulling and the server's model. The last observation is the difference between model update
if i S,
T(r+1)r, Trr+ld
(r+1)7
(83)
Vk. if S
k=r++2
if i $ S, if S,
Oer W+1.
fe Vi((Tr)))
(84)
Using the client-only notation: du 1ik,1,0k,277 ;RH,N] E R.xdd have the compact form
(r+1)r
a (r+1)r
2r =D,
Σ
U%
(85)
k=rT+2
100p1==,,- =D, (Vf - vf(()))
(86)
E.3 Descent Lemma for FOCUS
Lemma 3 (Descent Lemma for FOCUS). Under assumptions (arbitrary client participation).
(L-smooth) and (p-strongly convex), if the learning rate 1) S 3L(r-Ij the conditional expectation of server's 's error can be bounded as
Err+1 [+++1)+11 - x"
2 muN)
[1ār++--x' -2 2n F(x*))
8nL2N
(87)
where x² is the optimal point.
Note that this lemma can only be used for the strongly-convex case, which is the most complicated case. Non-convex proof is simpler than the strongly convex one, and similar idea can be applied there, so we make this lemma outstanding here.
Proof of Lemma
The server's error recursion from the (r + 1)-th round to the r-th round is
E [ x=1]
31

---

=F | x² -, V ((++))>)]
-113rr41 x² x=11²=- 1-12--210 112-21EE (Trr+1 - x² (z + |1 |
V ( (--)))
5118r++1 x' -/ylE (Frr+1 x², V (x + 2 | V (x()))) 1 (1 ++++)||
+ +21 2 || VV (T++1)] ?
<| r111 x5 112 2nylE (Trr+1 xx,, (+ 2n (++())))))
1 (1 ||
F F(x)))
(88)
where the first inequality is obtained by Jensen's inequality and the second inequality utilizes the Lipschitz condition with convexity 1 [F(x)]] < F(x) - F(x*). The cross term can be bounded 25
as
2ny (Trr+1 x², V (I((1111))))
- 2" (Trr(())+)) - 21/E (īrr+1 - x², ((((())))))))))-)))))))))))))))) - Vf || - x x²1 + nellarr+11 - x111
S (FFT((((T)Ttt) - F(x") + /
2
+ "
V f [1 2 11)
e
Mun
2 [[VV)()(+ (1
S (P
| - x12
(89)
where the first inequality utilizes Young's inequality with 6, and set n/2 in the second inequality.
Plugging
89 into
88
we have
MuN
E (
x²
| x-11- 2n 2/ F(x)))
2
( +n)) E E (VV((( - (V(
+ 2n
(90)
Next, we focus on this gradient difference term:
E [v (1)+) VV
<L <L NE 17 1T, 1(++
(r- l)r
= 2
Lā - Brr+1 +1
Σ
D
k=r++2
F
2
(++1)r
<2L - -x 2
" Σ DaY
k=rT+2
(r+1)r Σ
22I2N[1E,T+1 Brr+1 + 2 - L)n
DDayall
(91)
k=1T+2
where the above two inequalities use Jensen's inequality || || | S N
N N ||a/112.
Lastly, we need to bound yk by using L-Lipschitz assumption and Jensen's inequality. We just need focus on the index that is the index among the sampled clients otherwise yk, 0, Vi S..
|| 2 = [ - (f((Er))))l
<2 V f (1( v (((x)r41.))1 + 2 (( fi(err)))
| <21.2|
1.1- + 1 2
12n -rr -) Σ
Iluer 2 |, 2
k M=
32

---

(++
<2
Σ
|
1rr41. Erz
(92)
K'rr+22
where, in the last inequality, we just expand the non-negative term the maximum difference cases. Hence, taking another summation of k from rT + 2 to (r 1)T, we obtain
(r+1)r
(1 2
Σ
ll,,,11 S 1)L2 1rr+1,1 - 2r7,el?
(93)
1=
When 7) S 2LV7-1' we conclude
(r+1)r
Σ
1B, S 4(T - 1 - 2rr,il
4(T 1 Drr,el?
(94)
k=r++2
Plugging
94 back to 91.. we obtain
E 1f 1'v (=
S 22 - 2,, -)
(95)
where the first equation means the difference between the model before pulling and the server's model, and the second equation means the difference between the clients' models after pulling and the server's model. The weighted Q and - Q (ref. (81)-(82) are strictly smaller than 1, which can make the convergence proof tighter. But for simplicity, we just loosen it to and got
E||1 ( - f (x)+))))) <2L , a 11 (T) 1
<3L Fr++1 Ørr|
(96)
where the last inequality holds when 1) S IyT.
E.4
Consensus Lemma for FOCUS
Lemma 4 (Consensus Lemma for FOCUS). Under assumptions [nnd 2
if the learning rate n S the difference between the server's global model and the client's local model
3/2
3/2
min
Amin
8LVN
8T((T-1) S.
can be bounded as
N2
(97) Note that this consensus lemma is not related to any convex strongly convex properties, so it can also be applied in nonconvex cases.
[ xr- S
Amin
)
(rr-1)) +
[VF
3
3qmin
Proof of Lemma 4
Here, focus how different the server's model at the r-round and the client's model just before pulling the model from the server. Taking the conditional expectation, we have
E
1 - xrr
r7
1 18 1((--17++1 n10r+1 ((-1))141 EE
Σ
DRYK
k=(r-1)++2
27²
27²² E
E 11 Z((-1))++1 1-
-
E 1
11
Σ DAYI
(98)
P
$1 1- p
k=(r-1)++2
where the inequality above uses Jensen's inequality ||a + b112 < ||lal1 any value between 0 and (exclusively). For each term, we know
- 1b112 and here be
E E1 - x(1-1)7+11
q
11
1),11
33

---

(1 - (miu) | (r()+) 1(r-1))11
(99)
and the second term
|1 52 ( V
2
- <2N 1
2 + 2 2 [VF
(100)
and the third term
(r+1)r
Σ
Dayt
<(T - 1)E
Σ
D
(1-1))+2
k=r++2
N
<4(T 1)²
q T Xrr
1=1
<4(T - 1, Trr+1 Drrl" 1|
(101)
Putting 99
100)
IOT back to (8) and selecting p =
1-9min
Amin 2
we obtain
Immina/
1 xrr 11
Umin
4n N Amin) |1 xrr11?
| (r- 1)++1 - 2(- 1)r
2
amin
4n N2 - 9min)
877 1)2 qmin)
VF (F((rr++1)1
11 xrrl 1
Amin
Jmin
Nr22 | Errlll 11
Qmin
| 1)++1 ((--1)7
1)r 1
2 817" N
Qmin
(T 12
VF (Trr+1)ll
11 - Irr|1
(102)
4miu
Amin
If 17 S min
9min 8LVN
8L(r-1) Jo we have
Smin
8r
Tmin
E E| - 11 S <(1 Umin
11 - Bor- (0r-1j//
IV (F
Quin
(103)
Simplifying it further, obtain
E
xrr
2
qmin
| (1+41114+11
1(y-1)r 11
[F((T++))|
(104)
30min
E.5 Proof of the Convergence of FOCUS (μ-Strong Convexity)
Proof of Theorem
(uSttronlly Convex Case):
By Lemmas and we have two recursions
MaN 2
E |
x= 1|
E Trr+1 - - -2n 21 - F(x*))
8 N
+
[16 2rr11
(105)
/
E E||1,27741
11, < <(1
Umin
1
1)(--1)+1111 (x
167/ N2
IVF )|(
3
3qqiin
(106)
34

---

<(1 Amin
(1)- + 32nr (F(Br41)) F(x*))
30min
(107)
To lighten the notation, we let Ar41 = E ((++)))++ - ==11 and B. = E 11 - 1. Therefore, have
Art1 < (1 11- Muu
81L2N
A, 2n
21) F(x"))
B,
(108)
1
32 (F(3r++1)- F(x)))
Br S <(1 (1- Qmin
1
(109)
30min
After summing up them, the term about (F(Brr+1) F(x*)) is negative, so we directly remove in the upper bound. Then, we get
Ar+1 + (1-BILiN))
8
MuN
Ar + (1-
quin
Br
Br-1
2
3
Muu
(A (1
8
BB.-))
(110)
2
where (T10) holds when 1)
S
2qmin
3N
SL2
Hence, we conclude that FOCUS achieves the linear convergence of nH-nH//22 under the strongly-convex condition.
E.6 Proof of the Convergence of FOCUS (Non-Convexity with PL Assumption)
Proof of Theorem I Nonconvex Case with PL Assumption):
Using the I, I.-Lipschitz condition, we have
F(3(++1)r41)
+ TL
<F(E(++1)r) n (V (((((()))))))) 1 I' (2
1 (f
(1)r))))) + L
=F(ārr-1)
|| T ( (1))))
<F(i (V V (( + 1/ NVF (Z)+11) V (
+ *
(111)
where the last inequality uses Jensen's inequality.
Using the parallelogram identity to bound the cross term, have
(VF((ET++)) 11 V (#(++1))) N
" (NVF 1 V fZ
17. [[
T (
nN 2
[F
7
2N
2N
1
(1
(112)
2N 2N
2
where we discard the non-positive term in the last step. Substituting back, we have
((
<F(Grr-1) + 17
+ 1721) [|
- -,2N2T.) [[F((1+4))|1
-(2 n,N
2N
<F() + 1) -
35

---

! <F(Trr-1)+ N
[1 - -1 - nBN (F(Err+1) - F*) 17.N
2
(113)
where the second inequality follows 1) v min TI, L { and the last inequality we split F into two parts and applying Pl-condition for one part. Next, we minus F on the both sides to obtain:
F P(#(++1)r+1) F
nN IV (Tr++) Il(
<(1 - ((1-)N](F(Brrt)) FT) N
2
(114)
Recalling the previous result 955
E | ( - 1' (f s(2 (1 - xr 11
(115)
Putting (115) back to 114 we have
nN
F(1((+1)441)
(1 n)N) - F*) + 4, 1 - 2,,11
V F (Z
2
(116)
Recalling the Lemma we know
E| 1 2,-11i S Qmin (1((-1))741 1)--1)r 16
[[
3qmin
(117)
With condition v) S min
Amin 16L
denote A, F(ārr+1) F and B,
32N 33N ---iinn) )
E [ār++1 2 and then we have
A,+1 + (1 4 B, - 13) + (1 Jmiu
Br-1
3
=(1 n3NN A,+ + 1 Qmin
nBN Br-1
<(1 3N (A, + (1 Imin
B,-
4
<(1 3N (A, (1-44) 41 B,-1)
(118)
Therefore, we conclude that FOCUS achieves the linear convergence rate of (1 3)NN) in the nonconvex case with PI. condition.
O
E.7 Proof of the Convergence of FOCUS (General Non-Convexity)
Proof of Theorem 7 General Nonconvex Case):
We begin with L Lipschitz condition:
I
F(0(r+1)++1) SF(Tr++1) - (VF (V(( 1/F
| [
2
<F((rr41) 1 (VF 1V
+ | 11 1 (2 I|(
+ (119)
where the last inequality utilizes the Jensen's inequality. Then, we deal with the cross term:
7 (V (V (V((((+1))))
= =- V= + ( (VF( - IVf((
36

---

(f Il
[1 (aapiiii)i11/(/iii 1V
(120)
2N
Substituting (10 back to 119 we have
n/N
(1 - 11--21NN)
2
<F( - EF +
17
+ L2
E |[ 1V (121)
2N
To bound the term | (xrr+1) (V we can directly use the result (55 so we
will obtain:
N
(1 - 2 VF
2
- - EF ((( + 2N + L) (212N -)
- 2r,7l 11
(122)
Then, when 7 S min( IIN 2 we can get 1/2 (1-2)ND)) 12 S n/2N and 81/
4LN:
1) & N. Thus, simplify the coefficients further as follows:
E| V
(F(E.+41) - F ((((+4))+1) nN
+
16I.2
E ||
21T11
(123)
N
Recalling the Lemma
we know
16 3quin
E [ - Frr 11 S (1 qmin
Fir 11--1))1 || [0((-1))
IVF [T
(124)
We denote that A, V (T
1) +
B, F(Err+1) and
= = 1ē, - x,,11
Through
124 and
123 we have the following two recursions:
4
B, Br+1) 8B,-B++] + 16I.
A, v n.N
N C
(125)
quin
C + 16n N
C <
Ar
(126)
3
3
Taking the summation from r = 0 to R - 1, we have
R-1
1 R-1
R-1
1677 N2 1
R-1
Σ
C
C, < Amin
C,-1+
Σ
Ap
R
3Rqmin R
0=
r=1
r=1
r=1
Amin
R
C
161/2
N2 N2
Σ
R-1
Ar
(127)
R
3. r=0
r=0
Note Cu 0 and shift the subscripts in the second inequation since adding non-negative term always holds. Therefore,
1
16
R-1 N2
C,
Ar
(128)
Rq
r=0
Lastly, noting
1 R-1
4
161 R-1
A,
<
(Bo BR) +
Σ Cr
R r=0
NR
r=0
25672 L2N N
R-1
A,
<
(Bo Bs)
Amin
R
n
T=0
(F((m) - F(
1
<
(129)
R
n R
where the last inequality follows 17 S
Juin
16L/2N
37

---

Extensions to Stochastic Gradient Case (SG-FOCUS)
When applying the optimization algorithm to the machine learning problem, need to use stochastic gradients instead of gradient oracle. Only one line change of FOCUS is required to support the stochastic gradient case, which is highlighted in Algorithm 2
Notably, the past stochastic gradient is V (I {k-1) instead of V fi ( Ex) This choice preserves the crucial tracking property. Furthermore, this approach offers a computational advantage by allowing us store and reuse the prior stochastic gradient, thus avoiding redundant computations.
Algorithm 2 SG-FOCUS (Stochastic Gradient Version of FOCUS)
1: Initialize: Choose learning rate 7 and local update т. At server, set a random 20, Yo = 0 and set Vo. all clients.
2: for r 0, .... R - 1 do
3: Arbitrarily sample client index set S,
4: for in S, parallel do
(r)
5:
Vo.i < Zr: yo. = 0
D Pull model Ty from server while yr NOT pulled
6: fort 0,....T
do
7:
11+1.1 = Vi, + Vi(( -
(r)
Di Current and last stochastic grad.
8:
1,+ It,s 1,1
9:
end for
end for
11: Ur+1 yr + Lies, Vr
Pushing Vi,r to server (Not averaging)
12:
2r+1 = 178++1
> Client model x is NEVER pushed.
13:
end for
Before showing the lemmas and proof of SG-FOCUS, we introduce an assumption of unbiased stochastic gradients with bounded variance as follows. Assumption 6 (Unbiased Stochastic Gradients with Bounded Variance). The stochastic gradient computed by clients or the server is unbiased with bounded variance:
E
((())) and EE (V](()) - V)((0))
so?
(130)
where& & the data sample.
F.1 Descent Lemma for SG-FOCUS
Lemma 5. Under assumption 2 if S min 128(7-1)= 2/2(r-1) ). the expectation of server's error be bounded
3 and
MaN
E [8641)411- <
E [Tr+1 - -2111- [112-2nn([1 2n (F((mrt)))) F(x*))
2 N
[1
11 - 2 2n?
P
where x² is the optimal point. Note that this lemma can only be used for strongly convex cases.
Proof of Lemma 5
The server's error recursion from the (r + 1)-th round to the r-th round is
E |
x+1 -
-E |[rr+] - x²- 111 I (
-I|ārr+1 -x" - [rr+1 - x², TV ( + E I E(-
-x" - +180
+ 2n²
- -
2 221
38

---

E11 x²11²
- -" (x(++))==)))) + 12o0
+ +2n
- -
(F - F(x")) ('vf(1ū,++)) 2 + (
(131)
where the first inequality is obtained by Jensen's 's inequality and the second inequality utilizes the Lipschitz condition 21. [VF(()]] & F(x) F(x*). The cross term can be bounded as
(T x², V'VV v((((++1))))
=- -21(Err-1 - x², NVV
2n Trr+1 x², 1 (+)((()))))))))))))))))))(())))) 1 ('
S -- (F F(x*) 11 | xx013) + re|1 1=1
2
+ + - (1
S (F(r)((( -(x')) nun 1Er+11=x"
I ( 1 IV +
2n
(132)
where the first inequality utilizes Young's inequality with and we set u/2 in the second inequality.
Plugging 132 into 131. we have
MuN
E (
1ārr-1-
2-12 2n (F())) FF(x)
1 +1
+ 2n
-
11
(133)
Now, we focus on this gradient difference term:
( 1 V
( (+++1)))|
NE 1 ((++1rr
(r+1)r
=LENE
Lirr+1 Brr+1 17 Σ D
k=r++2
(r+1)r
<2L²N | 2rr+1 2 2 NNE
Σ
Days
k=rT+2
(1+1)T Σ
2 Brr+1 12 L2
(134)
k=rT+2
where the last two inequalities use the Jensen's inequality
E a S N NEW ||..11
Next, we need to bound yk.,; by using L- Lipshitz assumption and Jensen's 's inequality. Assume is the index among the sampled clients:
| =F f (x:
4E
V (I4-1, - 4 (f(rr++1,)))1
+ 4E f
(i( VV ((((trr.s
<AL?|| - 2r + 4L || - I 1| + 80²
L - - 2)
Σ
| 12 + 4L || Irr.all + 80²
M=rT+2
(r+1)7
SAnRI3(T- - Σ
| 4L
| FrTaal2 80²
M=rT+2
39

---

where, in the last inequality, we just expand the non-negative term to the maximum difference cases. Hence, taking another summation of & from rT + (r 1)T, we obtain
(r+1)r
(1 (1- 1))
Σ
El <4(T - 1) 4 11 - Irr, 1 - 1)o²
k=
When 1/25 41-41 (,221,((7
1)) i.e.,
21 2( we conclude
(n+1)r
E
Σ
|| <8(T - 1)L | 1rr+1,1 2rr,ill + 16(T 1)o²
kmrr+2
-8(7 - 1) -
- Irr,ll + 16(T 1)o²
(135)
Plugging 135 back to
134
we obtain
V 1T (V
+ 16
(136)
Plugging (36) into 133
we obtain
MuN
(6+1))+11 - -
E [ -211 (2
+ 21
+11
(21.2 + (21.2+1667) (7 11) ( -0,71
|1
| + (T 1T)
+ 02202 2m
11
<
M.N
E | x²112 N - (F((())) F(x*))
16
|1 - -xr-1==--2--- +2120000
/
where the last inequality follows:
S minf "¹ 128(T - 1) 2/2(1 1)T
1
min
11
128(T 1) 2/2(T 1)T.
F.2
Consensus Lemma for SG-FOCUS
Lemma (Consensus Lemma for SG-FOCUS). Under ussumptions 7 6 if the learning rate
3/2
3/2
" min AL.VN 1
the difference between the server's global model and the client's
local model can be bounded as
E E
2rrll 111--1 4min
|1
-
1)r-1)r|1
Nr
8 N
Jmin
Jmin
Note that this consensus lemma is not related to any convex strongly convex properties, so it can also be applied in nonconvex cases.
Proof of Lemmal 6
Here, focus how different the server's model at the r-round and the client's model just before pulling the model from the server. Taking the conditional expectation, we have
E [1 Err 12
FT
=F
10 17 1((-1))++1 +
Σ
DaYK
k= (r 1)
40

---

2x²² 1 p
2x/
E (+(+-1)++1 (r 1)++1
+
E 1 yrr
|| + 1-
E
Σ
DaVK
(==++1))+2
(137)
where the inequality above uses Jensen's 's inequality |la + bll2 - / ||ll| any value between 0 and (exclusive). For each term, we know
+ 1 1-p 11b1 and here can be
N
E 1 2(r-1174111
Σ (1 - () I(r 1),,1l
$ (1 (min)
(+(r-)))++ - 2((-1)r|1
(138)
and
10r++1
+3 - (f - 2
+ + 331I/FF(
<3No² + 3NL 1T - E.r |/ + (\
(139)
and
(r+1)7
E
Σ
DaYK
S(T 1)E Σ
D
k=(r-1)r+2
kmrT42
N <4(T 1) Σ
Trr+1 2rriil?
<4(7 1) F,r+1 Err 1|2
(140)
Putting 138
139).
140)
back to 137 and selecting p
Umin I- gmin/
Omin
we obtain
2 Suntn
17 r xrrli 12
Amin
6n L Amin) 11 - 2rr
( - 1)
2
Jmin
6n/² 22 (2- (min)
N2 mmin)
Qmin
Juin
8np² (r 1)2 9min)
1 Brr 1|2
Qmin
26 201-1) 1)T 11 12n ||1Err+1 xrr 11:
Gmin
2
Juii
N2
12r d²
16n 1)
IVF
115 2rr11
Juin
Gmin
Quin
3/2
If 1) S min
we have
4LVGN
B
amnn
E
1
Ey 12
12n N2
12n N 0² Amin
Zmin
(VF(arr+1)) 2
<
2 20 13-
2
quin
Simplifying further, we obtain
LE 2rrll
S (1 Amin
|| [ - DCr- 1)r
N2 qmin
VV
8 N 4min
σ²
3
41

---

F33 Proof of the Convergence of SG-FOCUS (1-Strong Convexity)
Theorem (Convergence of SG-FOCUS for Strongly Convex Functions). Under assumption
and 6 if the learning rate n S min
24min
Omin
Amin
3N
1822
+4)
ALVGN
8/21(r-1) 1)² 11-LAN
Tn - 1 MniliN
R
To + 4(Amin + N2) no?
2
PNggin
where r, =- E (f(++1)r-1---- - x" 2²12 + +11- 81,L2NN11 [1 (10 (((-1))111
Proof of Theorem
By Lemmas and
we have two recursions the average iterate one:
nuN
E [00+1)+41- x
E [Tr+1 -==12 2
2n/N (1 2) -F((")
1 N IF |8rr+1 11 227²0²
(141)
1
and the consensus one:
|| [+r++1 Err 112-
[ - (((--))7 1)r 11 8nj² N2
8 o²
qmin
V (Trr+1)]1
3
4min
Amin
qmin
167² N2
(F (((rr+1)- + 81 o²
<
[ - -0(y-1)711
3
Qmin
Umin
To lighten the notation, we let Ar41 = E [| - x012 and B, = E E|1 - Err 11 Therefore, we have
MuN
A, - 21/ 21 ((((rr))))))))) F(x*)) 167
A, S
B, + 221200
2
16, (F(Tr++1) - F(x*)) + 81 N2 B
B, S
Qmin 3
o²
Qmin
Quin
After summing up them, the term about (F(Err+1) F(x*)) is negative, so we directly remove it in the upper bound. Then, we get
Art1 + (1- 16 N
Br S
MuN
Ar+ + (1 1-uuin)
qmin
B, +
2n)² +
N
0²
2
3
Amin
nuN
(A, (1
16111.2N
Br- + 227² +
8r72 N2
0²,
2
Gmin
(142)
where (122) holds when -
24min 1842 2
Denoting Ip; Ap + ++1111111 (1- 16 N.
Bp- 142)
will be
3N
+4)
r T < (1
MuNN
8N2
MT,.N) 1
4(1min + +22
r,
+
2+
1²002
To +
no²
2
qmin
2
p.N pNqmin qmin
Hence, we conclude that FOCUS achieves the linear convergence rate of (1 (1-nuN/2) to Onvel neighborhood of the optimal solution.
F.4 Proof of the Convergence of SC-FOCUS (Non-Convexity with PL Assumption)
Theorem (Convergence of FG-FOCUS for Nonconvex Functions with the PL Condition). Under
3/2
3/2
assumptions / 2 6 if the learning rate 17 S min
Qunin
quan 161.
Bain
Quin
3 (4N44iinnn)
4Lv6N'
8
8/2L(T-1)
2R 5(1 - n) 22 + 1/ + 32(T - 1)2
8
n n
Omin
B
42

---

where Sr = F(0rr+1) F* + (1 (1- 4nL2) E 1 1)+11 Prr-1)rll and F is the optimal
value.
Proof of Theorem
Using the T--Lipschitz condition, have E [ (1
r24L
<F(F(+1)))) - t DV +
E || ((
2
LL
LL
-
V
2
1)+)
)1
o²
2
L
L
=F( - 1 VV
|
20
||
2
<F(Irr-1) - 7i (VF + (
f
L
+ +f
where the last inequality uses Jensen's incquality. Using the parallelogram identity to address the term, have
- (V 11 V
1 ((NTT((TT+))... v x (++1)))
N
" (1
NN [VF( V[
7
2N
2
2N
Substituting back, have
E E|
<F(T + 2N [1 - 1 nN
[V
|
2
2N
T INVF( - - + LN
2 o²
<F(Err-1) +
+ n²²1)
- -1
2N
N N² |VF 11
12 0²
2
<F(ir--1) + ! [1 Vf - L2
2 d²
N
< <F(Trr-1) + !)
- VV (V
+ (F* F(Err+1))
N
v/V 2 (IF
1P 0
2
where the third inequality follows 7) min JNN: - }. Next, we minus 5* the both sides to obtain:
F(G(++)7+1) F" =1111
nBN) F*) " -
(2
V 2 VF 7 I.N
o²
(143)
2
Recalling the previous result (36 and putting it into 143). we have:
nN
F( - F* -01- (F11-)3)(F(Frrae - F²)) + + 4n - 2,r -
V FF (1r++1)12
2
L + 32(T 1)31.22) 1280
43

---

Recalling the Lemma 6 we know
E| E| - Errll =
Muin
|
[r 1jr+1 2(r 1)r
812
V F (T,r+1)ll
81p2 N
3
Imin
Amiu
With condition 7) 5 min 3dmin
Jmin 16L
J. denote A, F( F² and Br
32N
32N(4-qmun)
E| 1 2rr 31 and then we have
Ap+1 + (1- (1-4 B,
5(1 - ABN)A, + (1- Amin
B +
LN
+ +2(TT - 118 +
8N
11²02
2
Unnn
LN
8N
n8N) (A, + (1 - -177L2 Br-1) +
+ 32(T 1) +
n²o²
(144)
Qmin
Denoting Ωr == A, + (1 - L²) B,-1,
144
will be
LN
8N
2 S(1 113N),, +
+ +2(TT 1 +
1)00²
2
Tmin
8
<(1 - (1-- Roo +
+
- - +
3 0
2
Amin
Therefore, we conclude that SG-FOCUS achieves the linear convergence rate of (1 - N) to 0(r)-
level neighborhood of the optimal solution in the nonconvex with PL condition.
F.5 Proof of the Convergence of SG-FOCUS (General Non-Convexity)
Theorem (Convergence SG-FOCUS for General Nonconvex Functions). Under assumptions
g/2
3/2
and 6 if the learning rate 1j S min
4LVGN BV2L(T-1) TLN IL(T-1I
Qmin
R
F(r1) F(**)
8N2
(
+ 22N + (N -822 Amin 1²02
R
N
-8L2))min
T=0
Proof of Theorem
We begin with L Lipschit condition:
E [[((((+1)++)))
n E V (a
<F((rr+1) TnE (VF( "V ((+1)))))
<F((rr+1) 17 (V 1 + L
1 0²
|| V (Z)
2
<F((rr+1) - 77 (V VV + n² NVV -VV
+ + L
(145)
where the last inequality utilizes the Jensen's inequality. Then, we deal with the cross term:
(VF((T++1), 1 TV V ((((())))
nNo VF 12 + ( (VFF( (V
I (((
N
VF
1212
2N [V)(12,41)
- [V
(146)
Substituting 116) back to 145 we have
nN
LN x²
(1 L1 VV (5.
(E(F(2
F(36+1)+11
2
44

---

+
+ 11 2N
+ +nPL)
( (f
To bound the term (f
(V we can directly use the result (36 we
will obtain:
Ty.V
LN
(1
2n
< -
+
+
+ L 1/002
2
2
2N
+ (2L + + 1)a L E 1ž x,,
22
When 17 S m 1
4LN+ 41(r-11). ). we can simplify further as follows:
TN ((( F F( + 81.2
E| 1
E 1ārr+1 3rr 1 22NN1
Recalling the Lemma
6 we know
LE Ir _
qmin
) [r P(--1)=16 +
81/2N2
I (2,,+)1+))
81f2N Qmin
o²
3
Qmin
When 1/2N' we have
E V F (F
R
((T)) F(**))
16I
[
Amin
R
xoll? + 2LN + (N- - (-82L) |121
8N2
1722
NNR
NH R
3
If the initial models of clients and the server are the same, then | xoll? = 0. The final convergence rate is simply
R-1
( F(F*))
8N2
E (
+ 2LN + (N 8L2 Auni
1202
R
N
-8L2))mii
G Supplementary Experiments for SG-FOCUS
G.1 Experiment Setup
To examine SG-FDCUS's performance under arbitrary client participation and the highly non-iid conditions, we compare SG-FOCUS with FedAU (Wang and Jil (2024) and SCAFFOLD Karimireddy
al. 2020) on the image classification task by using the CIFARIO Krizhevsky al. 2009 dataset. The model we used is a three-layer convolutional neural network. As for our baselines, FedAU is typical FL algorithm designed to tackle unknown client participation, and SCAFFOLD a classic Fl. algorithm designed to deal with data heterogeneity. Therefore, it is reasonable to select these two FL algorithms as our basclines.
The source code for the implementation is provided in the attached supplementary material. Our hyperparameter settings are: learning rate 77 2e-3, 3, local update 3. the number of clients N 32, total communication rounds r = 10000. To ensure totally arbitrary client participation, we do not restrict the number of participating clients in each round. To simulate highly non-iid data distribution, we use Dirichlet distribution and use a 0.05 to model that. Note that a smaller represents higher data heterogeneity. We illustrate the highly heterogeneous data distribution we used across 32 clients in our experiments in Figure 8 The size of the bubble reflects the number of data points the particular class used in that client. From Figure g we can roughly observe that the data of each client mainly covers 1-2 classes, the degree of non-iid data is quite high.
45

---

Bubble Plot of Data bistribution (Dirichlet, e=0.05)
Truck
3Mp
Frog
Data class
Cal
Brd
Ai Aiplana
0
10
11
13
14
15
17
70
21
70
78
Cninttnnex
Figure 8: Dirichlet Data Distribution (a 0.05)
G.2 Experiment Results of SG-FOCUS
From Figure 9 we observe that under highly heterogeneous data distribution (a = 0.05) and arbitrary client petttiippationssmallnnggg our SG-F SG-FOCUS shows the best performance convergence speed and test accuracy, compared to FedAU, MIFA, and SCAFFOLD. These results echo the view in our main paper: SG-FOCUS can jointly handle both data heterogeneity and arbitrary client participation.
Active Arbitrary Client Participation
Passive Arbitrary Client Participation
0.8
Test Accuracy
0.6
Test Accuracy
0.4
0.3
FOCUS
0.3
FOCUS
FedAU
0.2
SCAFFOLD
0.2
SCAFFOLD
0.1
MIFA
MIFA
6000
8000
10000
2000
4000
10000
Communication Round
Communication Round
Figure 9: Performance Comparison of SC- FOCUS and Baselines on CIFARIO Dataset under Arbitrary Client Participation and High Data Heterogeneity.
46


Reviews:
[{"review_id": "YKaWdzMepR", "reviewer": "Reviewer_yWqo", "summary": "This paper tackles the arbitrary client participation problem in federated learning, where clients may join or leave at will during FL training. To address this, the authors propose a new analysis framework from the time-varying graph perspective. The theoretical analysis shows that exact and linear convergence for federated learning is achievable.", "questions": "1. Can the authors elaborate more on the intuition behind exact convergence gradient tracking?\n2. Can the authors provide more experiments\n * under more arbitrary client participation settings?\n * on MIFA and FedVARP algorithms?\n3. Are there any connections with the push-sum algorithm in the fully decentralized learning literature, for example, in [R3]?\n\n[R3] Olshevsky, A., Paschalidis, I. C., & Spiridonoff, A. (2018, June). Fully asynchronous push-sum with growing intercommunication intervals. In 2018 Annual American Control Conference (ACC) (pp. 591-596). IEEE.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "### Strengths\n1. The paper is well written. I enjoy reading the paper.\n2. The proposed approach is novel and outperforms the state-of-the-art.\n3. I appreciate the beauty of applying insights from stochastic matrix theory to the analysis of the federated learning algorithm.\n\n### Weaknesses\n1. FOCUS combines insights from a fully decentralized algorithm and a federated learning algorithm with a server. In particular, it is partially inspired by the gradient tracking algorithm. It is a pity that the authors did not provide much intuition to help the readers understand.\n2.  In the experiment section, only one case of arbitrary participation is provided.\n3. To deal with client participation, we also have algorithms based on variance reduction techniques, including MIFA [R1] and FedVARP [R2]. \n\n**References:**\n[R1] Gu, X., Huang, K., Zhang, J., & Huang, L. (2021). Fast federated learning in the presence of arbitrary device unavailability. Advances in Neural Information Processing Systems, 34, 12052-12064.\n\n[R2] Jhunjhunwala, D., Sharma, P., Nagarkatti, A., & Joshi, G. (2022, August). Fedvarp: Tackling the variance due to partial client participation in federated learning. In Uncertainty in Artificial Intelligence (pp. 906-916). PMLR.", "was_revised": true, "final_justification": "The authors have addressed all of my concerns. Since this is a solid theoretical paper, the extra experiments will be a bonus to their contributions as the current experiments can already illustrate their points. I believe the authors would include the results in their final revision for a better numerical understanding of their method.", "rebuttal": "We sincerely thank the reviewer for the thoughtful comments and meaningful questions. This valuable feedback has allowed us to improve the manuscript. Our detailed responses to each point are provided below.\n\n> Weakness 1 & Q1. The intuition behind exact convergence gradient tracking?\n\n**Our response:** Thank you for raising this important question. We are happy to elaborate here and will add a detailed explanation to the appendix to make the manuscript more self-contained. \n\nThe intuition behind push-pull algorithms can be understood through three core concepts: the property of the column stochastic matrix ($C$), the property of the row stochastic matrix ($R$), and the gradient tracking mechanism.\n\n- **Column Stochastic Matrix ($C$): Mass Conservation**. Imagine a vector $y$ where each element $y_{i}$ represent some mass of the $i-$th object. In the operation $y^+ = Cy$ , the total sum of these masses, $\\sum_{i} y_{i}$ is preserved. (The average is preserved as well). This is because of the column stochatic definition, $\\mathbb{1}^T C=\\mathbb{1}^T$, so the sum remains unchanged:\n$$\n\\bar{y}^+ := \\mathbb{1}^T y^+ = \\mathbb{1}^T C y = \\mathbb{1}^Ty := \\bar{y}\n$$\nIn our algorithm, $y_{i}$ is analogous to the local gradient information at client $i$. Using a column stochastic matrix ensures that the sum of these local quantities, which represents the global gradient (server-side), is not arbitrarily altered during aggregation for the next tracking one.\n\n- **Row Stochastic Matrix ($R$): Reaching Consensus**. A row stochastic matrix, $R$, drives the system toward consensus. Under mild conditions on $R$, repeating the process that $y^+ = Ry$, i.e. $y^{\\infty} = \\lim_{n\\to\\infty} R^n y$, causes all elements of the vector to converge to a single, common value. This is also commonly referred as the reaching the consensus. This property is crucial for the model parameters, $x$, as we require all clients to eventually agree on the same model.\n\n- **The Tracking Trick: Telescoping Sum**. The tracking mechanism functions like a telescoping sum to ensure sum of the gradient estimator is unbiased to the sum of desired global gradient. Consider a simplified update for the tracking variable $y$\n$$\n y^+ = C(y + \\nabla f(x) - \\nabla f(x'))\n$$\nLeft multiplying $ \\mathbb{1}^T$, we get:\n$$\n \\mathbb{1}^T y^+ = \\mathbb{1}^Ty + \\mathbb{1}^T\\nabla f(x) - \\mathbb{1}^T \\nabla f(x')\n$$\nIf we initialize the tracker such that its sum matches the sum of the gradients $\\mathbb{1}^Ty = \\mathbb{1}^T \\nabla f(x')$, the update ensures that the tracker's sum will perfectly match the sum of the new gradients $\\mathbb{1}^T y^+ = \\mathbb{1}^T\\nabla f(x)$. By induction, the tracker sum correctly follows the true global gradient sum at every step.\n\nBy adding this detailed breakdown to the appendix, we hope that the explanation in the main text (lines 192-204) will be crystal clear, allowing readers to understand how the push-pull algorithm elegantly satisfies both the consensus and gradient tracking requirements.\n\nLastly, we want to highlight that the gradient tracking technique used in our work is just one possible method to achieve exact convergence within our proposed framework. One of the key contribution and the core idea of this paper is to present a general methodology that 1. We use stochastic matrices as a tool to model the decentralized learning process. 2.We reformulate the original unconstrained problem (1) into the equivalent constrained problems (9) and (10). Once the problem is expressed in this constrained form, a variety of optimization algorithms can be applied. **Crucially, from pure optimization perspective, this formulation implies that we need the primal-dual method instead of primal-only method to achieve the exact, linear convergence in FL problem.** Our work with the push-pull algorithm is one such example. Other promising approaches could also be adapted within this framework, including methods like push-sum (from reference [R3], which the reviewer helpfully provided) and algorithms like EXTRA and Exact Diffusion. **Ultimately, we believe that this framework-based methodology, rather than relying on algorithm-specific heuristics, is what opens the door to a broader class of efficient and provably exact convergence FL algorithms.**\n\n> Weakness 2. In the experiment section, only one case of arbitrary participation is provided.\n\n**Our response:** We thank the reviewer for highlighting the experiments, but **we would like to respectfully point out that the appendix already contains experiments on both active arbitrary client participation (Case 2) and passive client participation (Case 3).**\n\nWe agree that more extensive experiments are valuable and will add a broader suite of results for different participation scenarios to the revised manuscript. While we cannot include new figures in this rebuttal, we have already conducted these experiments and can summarize our key observations\n \n- Low Participation Probability: When some clients participate very infrequently, the convergence rate is, as expected, slower. The loss curve sometimes exhibits temporary plateaus for several rounds before resuming its downward trend. This confirms the algorithm's robustness, as it still converges correctly even with sparse client contributions.\n\n- High Participation Probability: Conversely, as the client participation probability increases, the convergence curve becomes smoother and more closely approaches the linear convergence rate shown in the full-participation case (Figure 1).\n\n\n> Weakness 3 & Question 2. To deal with client participation, we also have algorithms based on variance reduction techniques, including MIFA [R1] and FedVARP [R2].\n\n**Our response:** Thank you for raising this important point. We were aware of many variance reduction (VR) methods developed for federated learning, including MIFA [R1], FedVARP [R2], SCAFFOLD, Anarchic FL, and FedBuff.\n\nHowever, our work differs from these methods in design philosophy, problem setting, and theoretical foundation. \nExisting VR-based algorithms rely on heuristic construction of variance-reducing control variates.\nIn contrast, **our method (FOCUS) is systematically derived by reformulating the federated learning objective as a constrained optimization problem and applying a principled primal-dual analysis.**\n\nAs a result, prior VR methods require strong assumptions on client participation, such as bounded delay in MIFA (Assumption 4 in [R1]) or uniform client sampling in FedVARP (line 3 in algorithm [R2]), which are not realistic in practical federated systems where client participation is dynamic and unknown. In contrast, our method is explicitly designed to operate under arbitrary client participation, a significantly more challenging and general setting not addressed by the aforementioned works.\n\nMore importantly, achieving exact convergence under arbitrary client participation remains an open challenge. Prior works [Wang and Ji, 2022; Wang et al., 2020] have shown that such participation introduces an inherent bias, leading models to converge to stationary points of a distorted, participation-weighted objective rather than the true global one. To the best of our knowledge, our work is the first to provide a rigorous framework that enables exact convergence in this challenging setting. This is achieved through a novel constrained optimization problem reformulation with a principled primal-dual analysis, new analytical framework via stochastic matrix analysis, and new algorithmic insights into mitigating client participation bias. it would be nearly impossible to arrive at FOCUS through heuristic design.\n\nIn summary, while there is a rich body of work on VR methods in federated learning, **our approach introduces a new formulation, methodology, and theory tailored for the realistic and challenging setting of arbitrary client participation,** which together constitute a significant and novel contribution. \n\nIn our paper, we selected SCAFFOLD as a representative VR method for detailed comparison. Following the reviewer’s suggestion, we have conducted additional experiments with MIFA and FedVARP. The results show performance comparable to SCAFFOLD but consistently underperformed compared to our FOCUS algorithm. This is expected, given their shared reliance on heuristically constructed variance control variates. We will include these results in the revision.\n\n> Question 3: Are there any connections with the push-sum algorithm in the fully decentralized learning literature, for example, in [R3]?\n\n**Our response:** Thank you for providing this excellent reference. The answer is yes -- both shared the some common traits.\n\nFirst, to clarify the terminology, the push-sum technique is designed to achieve an unbiased consensus using only a column stochastic matrix, avoiding the more restrictive requirement of a doubly stochastic matrix. When this is combined with a gradient oracle, it results in algorithms like (Sub)gradient-Push.\n\nThe similarities with FOCUS are: both rely on a column stochastic matrix and a gradient tracking mechanism to ensure the gradient estimator remains unbiased.\n\n**The difference lies in the mechanism used to achieve model consensus:**\n\n- Our push-pull method uses a row stochastic matrix ($R$) to explicitly \"pull\" the model parameters ($x$) towards a common average.\n\n- The push-sum method, in contrast, maintains an additional iterated scalar that propagates alongside the model parameters using the same column stochastic matrix. It then achieves consensus by normalizing the model state with this scalar (i.e., by calculating the ratio $z=x/y$, as shown in Eq. 7 of [R3]).\n\nUltimately, both push-pull and push-sum are valid paths to exact convergence. This suggests that a novel FL algorithm could be developed by applying the push-sum technique within the optimization framework presented in our paper, highlighting a promising direction for future work."}, {"review_id": "Pr8EofxRvQ", "reviewer": "Reviewer_AKZy", "summary": "This paper studies the problem of partial participation in federated learning, in the particular context where clients participate with (fixed) arbitrary probabilities.\nFirst, an interpretation of the properties of FedAvg-like algorithm as a decentralized algorithm with time-varying graphs is proposed, allowing to express the updates through a sequence of stochastic matrix products.\nBased on this interpretation, a novel method, coined FOCUS, is proposed, which is built on a primal-dual approach, and recovers gradient-tracking-type ideas.\nThe proposed method is shown to achieve good empirical performance in comparison with existing methods.", "questions": "1. What would the convergence rate look like if removing the artifical dependence in $N$ in the rate? Is it possible to fully state communication and sample complexity results, with full dependency on the constants and on the probability of communication?\n2. In particular, $q_i$ seem to appear in Theorem 1 only through its minimal value $\\min_i q_i$. Is it possible to obtain something better, like on the average of the $q_i$'s, or is it in some sens optimal?\n3. Although the matrix interpretation of the algorithm helps in the design of the new method FOCUS, it seems that it results in unusual conditions on the step size ($\\eta \\le \\mu^2 / L$). Is it because the matrix method is limited? Or because this is not the best matrix decomposition possible? Could it be improved or is there another more profound reason for these conditions to show up?", "limitations": "Yes limitations have been properly discussed.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n1. The interpertation of FedAvg with partial participation as a decentralized algorithm with time-varying graph is interesting, and allows for representation of algorithms as a product of stochastic matrices, which is often a fruitful approach. This is directly applied to the development of a novel FL method that outperforms many of the existing ones, which is very interesting.\n2. The propsed method is the first to achieve linear convergence under arbitrary participation, with without relying on tricks like almost-surely bounded time between successive participation of clients.\n3. Theoretical convergence rates are provided, together with numerical evaluation that shows the superiority of the proposed methods on some problems.\n\n\n**Weaknesses**\n1. The convergence rates rely on conditions on the step size like $\\eta \\le \\mu^2 / L$, which are way worse than the typical $\\eta \\le 1/L$. Moreover, they require the step size to scale with the smallest participation rate $q_i$, which is unknwon and may prevent the algorithm from converging.\n2. Convergence rates are somewhat misleading, as they seem to claim that the convergence is faster as the number of clients grow, but at the same time the step size is small than $1/N$. Contrarily to what is written in Theorem 1, there is thus no acceleration with the number of clients $N$ in the convergence rate (which is to be expected in FL).\n3. Overall, it is not clear how the convergence speed is affected by the probability of communication, although one could expect this to play a major role in the algorithm's properties.\n4. The method is only applied to deterministic gradients, although it borrows analysis techniques that are typical from stochastic approximation (using stochastic matrices).\n\n\nTypos:\n- In Equation (3), the left-hand term should not be the square of the norm, but rather the norm.\n- In Equation (18), it seems it should be $\\Leftarrow$ since it involves communication.", "was_revised": true, "final_justification": "I was already positive about this paper, and remain positive about it after the authors' response.\n\nI think the way they describe the algortihms using product of stochastic matrices is interesting to the NeurIPS community, which to me justifies acceptance of the paper.\n\nI would appreciate it if the authors could comment on the following two points in the revised manuscript: \n- I am a bit surprised by the presentation of their convergence results, which show an explicit dependence on the number of clients $N$ in the convergence rate, which is unusual in FL: this is in fact an artefact of the presentation, since they also decrease the step size with this same value, which may be a bit misleading.\n- The stochastic setting is only presented in appendix, while I believe it is important enough to be put in the main text, taking advantage of the additional page for the camera-ready.", "rebuttal": "We are very grateful for your thorough review and insightful comments. We have carefully considered all your suggestions and believe it can helped us strengthen the manuscript. Our point-by-point responses to your feedback are as follows. \n\n> Weaknesses 1 & Q1. The convergence rates rely on conditions on the step size like $\\eta \\leq \\mu^2/L$, which are way worse than the typical $\\eta \\leq 1/L$. Moreover, they require the step size to scale with the smallest participation rate $q_i$, which is unknwon and may prevent the algorithm from converging. \n\nWe thank the reviewer for this insightful question. We believe it refers to the first term in our step-size condition for the strongly convex case, which is on the order of $\\mu/L^2$ instead of $\\mu^2/L$.\n\nWe first want to clarify this term and its context. Using the condition number $\\kappa =L/\\mu$, this term can be written as $1/(\\kappa L)$. We acknowledge that this bound is not as tight as the optimal rate for standard Gradient Descent, which is $O(2/(\\mu+L))$. Our bound matches the optimal one only in the specific quadratic case where $\\mu=L$ and is sub-optimal otherwise.\n\nThe source of this sub-optimality is not inherent to our matrix-based method, but rather stems from the analytical tools used in the proof. Here is the key reason:\n\nIn standard GD, **the tight bound is often derived using the co-coercivity property, which elegantly captures the joint relationship between the smoothness constant $L$ and the strong convexity constant $\\mu$. However, due to the increased complexity of the FOCUS algorithm, directly applying the co-coercivity property is not straightforward.** Instead, to handle the complex cross-terms in our analysis (see Equation 81), we use Young's inequality. While effective, this inequality is looser and separates the effects of $\\mu$ and $L$, which introduces the slack that leads to the sub-optimal bound.\n\n> Weakness 2 & Question 3. Convergence rates are somewhat misleading, as they seem to claim that the convergence is faster as the number of clients grow, but at the same time the step size is small than $1/N$. Contrarily to what is written in Theorem 1, there is thus no acceleration with the number of clients $N$ in the convergence rate (which is to be expected in FL). \n\nWe thank the reviewer for this insightful observation. The reviewer correctly notes that in our deterministic analysis, the coeffient $(1-\\eta O(N))$ term in the convergence term is offset by the $O(1/N)$ dependency in the step-size constraint.\n\n**It is actually expected and impossible to improve this rate.** Before we give a detailed reason. Let's give an example to illustrate it. Suppose $f(x) = \\frac{1}{N}\\sum_i f_i(x_i) =  \\frac{1}{N}\\sum_{i}\\|x\\|^2 \\equiv \\|x\\|^2$. Clearly, no first-order FL method can exhibit a convergence rate that accelerates with $N$ for this problem, because adding more identical clients doesn't make the problem fundamentally easier to solve. FOCUS, being an exact algorithm in its primary analysis, correctly reflects this reality.\n\n**This apparent contradiction with the common sense of linear speedup in FL arises because FOCUS is an exact algorithm.** The typical \"linear speedup\" in federated learning is a feature of stochastic settings. It's a direct result of variance reduction; by averaging stochastic gradients from $N$ clients, the variance of the gradient estimate is reduced, leading to a diminishing error term, often on the order of $O(\\eta^2\\sigma^2/N)$. However, as an exact algorithm, FOCUS has no such stochastic noise term to average out. Its convergence rate is determined by the deterministic properties of the objective function. As the previous toy example illustrates, simply adding more clients to a deterministic problem does not make it fundamentally easier or faster to solve or improve the rate of descent.\n\n\n**Crucially, our framework is fully consistent with the standard notion of linear speedup when stochastic noise is introduced.**\nAs demonstrated in our Theorem 5, the analysis for the SG-FOCUS applied to general non-convex problems with stochastic gradients—reveals the expected linear speedup with respect to the number of agents, $N$. The part of our error bound dependent on variance scales as $O(N)\\eta^2\\sigma$. By selecting the step-size appropriately, with $\\eta \\propto 1/N$, this term reduces to the familiar $O(\\sigma^2/N)$ rate.\n\n\n> Weakness 3 & Q2. Overall, it is not clear how the convergence speed is affected by the probability of communication, although one could expect this to play a major role in the algorithm's properties.\n\nThis is an excellent and important question. We agree with the reviewer's sharp intuition that the bound involving $q_{\\min}$ is likely not tight, and a more refined analysis would be a valuable contribution. Given that the primary message of this paper is the algorithm's design and the existing convergence proof is already quite involved, we believe a deep investigation into tightening this bound is best suited for future work.\n\nHowever, we are happy to share our perspective on a potential path forward. The $q_{\\min}$ term is introduced in our consensus analysis (Lemma 4, specifically Eq. 91) to establish a clear recursion for the total (unweighted) consensus error. A promising approach to achieve a tighter bound would be to define a weighted consensus error term, analogous to the technique used in the FedAvg analysis (referenced in Eq. 29). This would likely involve adapting the method from our proof (between Eqs. 54 and 55), where the vector q is handled collectively via Jensen's inequality, thus avoiding the simplification to its minimum element.\n\n\n> Weakness 4. The method is only applied to deterministic gradients, although it borrows analysis techniques that are typical from stochastic approximation (using stochastic matrices).\n\nWe thank the reviewer for this point. We believe it only refers to our analysis of FOCUS in the deterministic setting, and we'd like to clarify that **we also provide a full analysis for the stochastic gradient setting. Our proposed SG-FOCUS variant is designed specifically for this case.** Due to page limitations, the detailed algorithm and its convergence analysis were placed in Appendix E and F. We included pointers to this material in the main text, both in our list of contributions and in Section 5.2. When there are more space for the revised version, we will move the key results of SG-FOCUS into the main body of the paper to improve its visibility. \n\n> Typos:\n(1) In Equation (3), the left-hand term should not be the square of the norm, but rather the norm.\n(2) In Equation (18), it seems it should be $\\Leftarrow$ since it involves communication. \n\nWe are grateful to the reviewer for your meticulous reading and for catching these typos. We will correct them in the revised manuscript."}, {"review_id": "qZBHnpSDSh", "reviewer": "Reviewer_PLZ6", "summary": "This paper propose FOCUS via push-pull strategy to address the arbitrary participation problem in federated learning.", "questions": "**Questions**:\n\n1. It is unclear whether $x$ (or $y$) is a row or column vector. See $x$ in Equation (1) and $\\boldsymbol{x}$ in Line 152; see $\\boldsymbol{x}$ between Lines 444 and 445 and Line 446.\n\n2. Lines 549-550: Why we say $\\boldsymbol{y}_k$ has one more inner iteration?\n\n3. Equation (67) and (68): Why is only $C_{k,all}$ defined ($R_{k,all}$ is not defined)?\n\n4. Line 607:\n\n   > the client's $y_{r\\tau+1,i} = 0$ for any clients.\n\n   Is this right?\n\n5. Line 610:\n\n   > the first equation means the difference between the model before pulling ...\n\n   Does \"the model\" represents \"the clients' model\"?\n\n6. Line 667:\n\n   > (102) holds when $\\eta \\leq \\frac{2q_\\min}{3N \\left( \\frac{8L^2}{\\mu}+\\frac{\\mu}{2}\\right)}$.\n\n   Does this cause an additional constraint $\\eta \\lesssim \\frac{\\mu q_min}{NL^2}$ for the strongly convex case in Theorem 1?\n\n**Suggestions**:\n\n1. Figures: It would be better to use the PDF format for the figures.\n\n2. Theorem 1. It seems that the convergence of FOCUS is affected by $p_\\min$. The convergence of FOCUS can be slow when $p_\\min$ is very small (e.g., $p_\\min = \\frac{1}{R}$). I think this limitation can be added to Section 5.3.\n\n3. Missing references. The following paper gave a similar conclusion to Wang and Ji [2023]. \n\n   Federated Learning Under Heterogeneous and Correlated Client Availability, IEEE/ACM Transaction on Networking, 2024.\n\n4. Table 1:\n\n   > There is no convergence proof of SCAFFOLD under arbitary client participation scenario.\n\n   The following paper can be relevant.\n\n   Federated Learning under Periodic Client Participation and Heterogeneous Data A New Communication-Efficient Algorithm and Analysis, NeurIPS, 2024.\n\n5. Line 74, Section 2:\n\n   > Yet, this approach incurs increased communication costs, doubling them due to the transmission of a control variate with the same dimensionality as the model parameters.\n\n   This sentence can be misleading. See Appendix A.1 in the following paper for the efficient implementation of SCAFFOLD.\n\n   TCT Convexifying Federated Learning using Bootstrapped Neural Tangent Kernels, NeurIPS, 2022.\n\n6. Section 3.1: Could you kindly give detailed explanation (or proofs) for the conclusions in the special cases. For example, explain why $q_i \\approx p_i/(\\sum_j p_j)$ when $p_i$ are close to each other in Case 2, and explain why $p_i = 1-(1-q_i)^m$ when it is sampled with replacement in Case 3. I think this would make the cases easier to understand for the readers.\n\n7. Section 3.1: Could you kindly give some practical FL scenarios (or give some simple and illustrative examples) for these cases, just like Appendix B.2 in the following paper?\n\n   A Unified Analysis of Federated Learning with Arbitrary Client Participation, NeurIPS, 2022.\n\n8. Lines 272-273.\n\n   > To see that, leveraging the tracking property of the variable $y_k$ and special construction of matrix $C_k$, we can establish that the server's $y_{r+1} = \\sum_{i=1}^N \\nabla f_i(x_{k+1},i)$.\n\n   Could you kindly add the proof for this?\n\n9. Lines 275-276:\n\n   > FOCUS effectively transforms arbitrary participation probabilities into an arbitrary delay in gradient updates.\n\n   This interpretation is interesting. This sounds like MIFA in the following paper. Could you kindly add some comparison with respect to the convergence rates.\n\n   Fast Federated Learning in the Presence of Arbitrary Device Unavailability, NeurIPS, 2021.\n\n10. References. There are some papers which are cited as preprint, but have been published. For example, Wang and Ji [2023] has been published in ICLR, Xiang et al. [2024] has been published in NeurIPS.\n\n11. Figure 9: Please add the results of FedAvg.\n\nIf the problems (weaknesses, suggestions, questions) I raised above are wrong, please free free to point them out.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n\n1. This paper finds the relation between distributed optimization over directed graphs and federated learning with arbitrary participation.\n2. This paper proposes FOCUS via push-pull strategy, which shows faster convergence than FedAvg.\n3. The theory seems solid and rigorous.\n4. The paper is well-written, well-organized.\n\n**Weaknesses**:\n\n**The motivation for constructing the matrices**. The constructions of the assign matrix ($R$), average matrices ($A$) and other matrices ($C$ and $W$) are interesting. However, the motivation for constructing these matrices **in this paper** is not strong or convincing. In my opinion, all the content can be presented clearly even without these constructions: (i) The model of arbitrary client participation relies on Assumption 1, instead of these constructions. (ii) The convergence analysis of FedAvg has been established in Wang and Ji [2022] without the constructed matrices. (iii) FOCUS can also be interpreted without these constructions (see Section 4.2.2). (iv) After checking the proofs of Theorem 1, I think the proofs can also be written without these constructions.\n\nUsing the matrices can increase the workload of reading this paper. For example, when checking the proofs, I need to revisit the definitions of some matrices (e.g., Appendices B, C.1). Some definitions of them are not straightforward, e.g., $\\nabla \\boldsymbol{f}(\\boldsymbol{x}\\_k) = [\\nabla f_0(x\\_{k,0}),\\nabla f_1(x\\_{k,1}),\\ldots,\\nabla f_N(x\\_{k,N})]^T$ and $\\nabla \\boldsymbol{f}(1\\bar x\\_k) = [\\nabla f_0(\\bar x\\_k),\\nabla f_1(\\bar x\\_k),\\ldots,\\nabla f_N(\\bar x\\_k)]^T$ in Appendix B.\n\nOne example where the use of matrix notation is necessary: The construction of the mixing matrix in decentralized federated learning (or decentralized SGD) is necessary, as the assumptions relies on the mixing matrix. See Koloskova et al. [2020].", "was_revised": true, "final_justification": "I agree with other reviewers that this paper is over the bar.\n\nThe main concern in my initial review is that the main contents of this paper do not depend on the matrices, and the motivation of this paper is not so clear. The authors claimed that the framework (associated with the matrices) is also a contribution of this paper. This justification seems reasonable for me.\n\nThus, I decide to raise the rating to 5. Given the high overall evaluation of this paper, my expectations for it are correspondingly higher.\n\nI hope that the authors discuss more about their framework: why the framework is important, how the framework help design new algorithms, which scenario the framework applies to. For the current version, the motivation for this framework and matrices is not quite clear. In addition, the authors can consider whether the framework can include the existing works for FL with arbitrary client participation, like FedAU [Wang and Ji, 2023], FedAWE [Xiang et al., 2024], MIFA [Gu et al., 2021]. If not, the authors can provide the reasons of the failure.\n\nTransforming a simple federated learning problem into a complex decentralized federated learning problem still feels unnatural to me. More discussion is still required for this transformation. The authors could consider whether there is a scenario in which such a transformation becomes indispensable.", "rebuttal": "We are sincerely grateful to the reviewer for providing such detailed and practical suggestions. Your thoughtful feedback has been quite helpful and has provided us with a clear path for improving our manuscript. We truly appreciate the time and effort you dedicated to the review. Our detailed responses to each point are provided below.\n\n## Weakness: \n\n> 1. The motivation for constructing the matrices.. \n\n**Our response:** We sincerely appreciate the reviewer's thoughtful suggestions on the paper's presentation. While we acknowledge that the suggested structure offers a valid alternative, we believe our current organization is essential for conveying the paper's core message for the following reasons:\n\n**Beyond presenting FOCUS as a standalone algorithm, our primary contribution is the introduction of a general and systematic framework for designing federated learning algorithms based on principled optimization rather than heuristics.**\n\nIn this context, stochastic matrices are not merely a notational choice but the foundational modeling tool that makes this framework possible. They are crucial for several reasons:\n\n- They allow us to reformulate the communication process as an explicit mathematical constraint. This step is what enables the shift from heuristic design to formal optimization; without it, deriving an algorithm like FOCUS would be nearly impossible.\n    - For example, Sec 4.2.2 will be unmotivated without introducing column stochastic matrix. See eq. 18 and 19. Taking sum and reseting the variable $y=0$ are not arbitrary heuristics but principled steps justified by the column stochastic matrix.\n- This matrix-based formulation leads to more concise and elegant proofs.\n- Most importantly, it establishes a versatile framework that can serve as a foundation for developing other novel FL algorithms simply by employing different primal-dual solvers.\n\nOur manuscript is therefore structured to walk the reader through this exact methodology:\n\n1. First, we use stochastic matrices to model communication patterns as explicit constraints.\n2. Next, we reformulate the decentralized objective as a constrained optimization problem.\n3. Finally, we apply a known optimization technique (a primal-dual method) to derive the final algorithm.\n\nWe chose this explicit presentation because we believe the framework itself is as significant a contribution as the FOCUS algorithm—a point the other reviewers have kindly acknowledged. **We are confident that this transparent, first-principles approach provides a valuable new perspective and a generalizable tool for the federated learning community.**\n\n> 2. Using the matrices can increase the workload of reading this paper. \n\n**Our response:** We understand the reviewer's concern. Our matrix-based notation is indeed less common in federated learning literature, and we recognize it may present an initial hurdle. However, we chose it deliberately for several key advantages:\n\n- Conciseness: It allows us to avoid cumbersome summation notation ($\\sum$) and express complex decentralized operations compactly. When combined with tools like the Frobenius norm, it makes the proofs more streamlined.\n- Geometric Intuition: We believe that reasoning about the null-space of matrices provides a more intuitive geometric perspective than manipulating long chains of element-wise inequalities.\n\nIn the revision, we will add a dedicated subsection explaining our notational choices. To briefly illustrate why this notation is natural, recall the global objective $f(X) = \\sum_i f_i(x_{i})$, taking the gradient with respect to each element we have $\\nabla_{x_i} f(x) = \\nabla f_i(X)$, \nlet $\\nabla f(X)= {\\rm vstack}[\\nabla_{x_0}, \\cdots, \\nabla_{x_N}] f(X)$. For $\\mathbb{1}^T \\bar{x}_k$, notice $f(\\mathbb{1}^T \\bar{x}_k) = \\sum_i f_i(\\bar{x}_k)$ so that the notation is consistent. We believe these notations, once grasped, offers a more elegant way to analyze the algorithm. \n\n**Due to space limitation, for question 1 and 5,  suggestion 1, 3, 5, 7, 10, and 11, we omit detailed response. We agree with these and will update the paper to reflect it.**\n\n## Questions: \n\n> 2. Lines 549-550: Why we say $\\mathbf{y}_k$ has one more inner iteration?\n\nThis is a subtle but crucial point in our analysis, as it distinguishes the error introduced by local updates from the error due to data heterogeneity (Note $\\tau$ versus $\\tau-1$). Notice eq (38) and eq(39), under the same iteration $k$, $x_{k+1}=W_{k}y_{k+1}$ that an extra $W_k$ is applied to get $x_{k+1}$. When $W_{k}$ is not identical matrix(inner iteration/local update), $x_{k+1}$ will become some common value while $y_{k+1}$ is still some value varying among different agents.\n\n> 3. Equation (67) and (68): Why is only $C_{k, all}$ defined ($R_{k, all}$ is not defined)?\n\nIt is the special feature of FL. The downlink communication (modeled by $C_k$) is pulling model, i.e., the server's model is overriding the client's model at the begin of iteration. Hence, we can virtually think the client is always pulling the server's model at all iterations no matter the client is active or not. Meanwhile, the uplink communication (modeled by $R_k$) doesn't have such properties. If we replace the $R_{k}$ by $R_{k, all}$, it change the behavior of algorithm, i.e., we average more client's model than necessary. You can refer the appendix line 488 and 492 and figure 6-7 in the appendix that we have some discussion there.\n\n> 4. Line 607: the client's $y_{r \\tau+1, i}=0$ for any clients. \n\nYes, it is because of the line 6 in algorithm 1. This very special behavior is induced by the properties column matrix $C_k$. When the client $i$ is sampled, it will reset the $y_k=0$ because all elements in the $i$-th row of $C_k$ are zero. Also see equation (17)-(19) and equation (69) for the virtual participation form. Lastly, combining the initial condition, we can conclude $y_{r \\tau+1, i}=0$ for any clients. \n\n> 6. Line 667: .. Does this cause an additional stepsize constraint for the strongly convex case in Theorem 1?\n\nThanks for the careful proof reading! We indeed missed this extra condition.\n\n## Suggestions:\n\n> 2: FOCUS is affected by $p_\\min$ or $q_\\min$.\n\nOn one side, it is intuitive that for a very sparsely participated client, the algorithm performance is deteriorated. On the other side, this bound might be further improved. Please refer our response to Reviewer AKZy, Weakness 3 & Q2 for more details. (Sorry we don't have enough space to expand this point here).\n\n> 4: convergence proof of SCAFFOLD under arbitrary participation\n\nThanks for providing this reference! It is a very relevant one that we should include it. Based on our reading of this paper, it is still not the same scenario as we listed in our table. First, it provides the convergence theorem for Amplified SCAFFOLD, which requires the server to store the gradient information for all client at the server. Second, the proof is provided based on the cyclic particiation or regular participation. In Section 6, the limitation stated, \"Our framework requires that all clients have an equal chance of participation across well-defined windows of time that are known to the algorithm\nimplementer, which may not always hold.\" In our arbitrary participation setup, we do not require this equal participation assumption. \n\n> 6: give detailed explanation (or proofs) for the conclusions in the special cases.\n\nSpecial Case 2: Active Arbitrary Participation -- If $p_i$ is close to each other, we can denote it as $p_i = p + \\epsilon_i$, where $\\epsilon_i$ is a very small number.\n\nSpecial Case 3 Passive Arbitrary Participation -- we sample the $m$ client with replacement. If a client $i$ is not participated, it means it is not selected by all $m$ times, i.e., $(1-q_i)^m$. Hence, the participation probability $p_i$ is $1-(1-q_i)^m$.\n\n\n> 8: Add proof about Lines 272-273.\n\nWe are happy to provide it. First recall the column stochastic matrix definition that $\\mathbb{1}^T C = \\mathbb{1}^T$. Left multiplying $\\mathbb{1}^T$ to equation (12), we have (Because of display system, we use capital instead of boldsymbol representing the vstacked vectors)\n\n$$\n\\mathbb{1}^T Y_{k+1} =  \\mathbb{1}^T C(Y_k + \\nabla f(X_{k+1}) - \\nabla f(X_{k})) = \\mathbb{1}^TY_{k} + \\mathbb{1}^T\\nabla f(X_{k+1}) - \\mathbb{1}^T \\nabla f(X_{k})\n$$ \n\nRecalling the initial condition $\\mathbb{1}^TY_{0} = \\mathbb{1}^T \\nabla f(X_{0})$, we can conclude $\\mathbb{1}^TY_{k} = \\mathbb{1}^T \\nabla f(x_{k})$ for any $k$ by induction. Lastly, noticing all client's $y$ is reset to $0$ at end of local update, hence, the server's value $y_r = \\mathbb{1}^T Y_{k}$.\n\n> 9: Add comparison with MIFA.\n\nWe thank the reviewer for bringing the MIFA paper to our attention; it is indeed a relevant and interesting comparison.\n\nThe core idea of MIFA is to correct gradient bias using memorized client updates, a technique inspired by the SAGA algorithm. This approach achieves convergence rates of $O(1/T)$ for (general) convex case and $O(1/\\sqrt{T})$ for non-convex case. While the mechanism of using memorized updates is conceptually similar to ours, FOCUS achieves significantly stronger theoretical guarantees, including a linear convergence rate of $O(\\exp^{-T})$ for strongly convex and $O(1/T)$ for nonconvex.\n\nThe key difference—and the reason for this performance gap—stems from the design philosophy. \n- MIFA is presented as a heuristic combination of FedAvg and SAGA. This design effectively mitigates the effects of data heterogeneity but does not fundamentally resolve the client drift introduced by local client updates.\n- FOCUS, in contrast, is not a heuristic algorithm. It is systematically derived from a formal optimization formulation where communication and local updates are modeled as constraints.\n\n**This principled, optimization-based derivation is precisely why FOCUS can jointly resolve, arbitrary client participation, data heterogeneity, and client drift, leading to its superior convergence guarantees.**"}, {"review_id": "sS25kvdAK4", "reviewer": "Reviewer_DDXi", "summary": "This paper addresses a fundamental problem in Federated Learning (FL): achieving exact convergence under arbitrary client participation and data heterogeneity without resorting to diminishing learning rates. The authors propose a new algorithm, FOCUS, inspired by decentralized optimization techniques, especially push-pull gradient tracking. The paper makes strong theoretical contributions; in particular, it models client participation using stochastic matrices and establishes sound convergence guarantees, with no bounded heterogeneity or participation bias assumptions. I believe this paper provides new insights into federated learning algorithms and has the potential to inspire further research in the field.", "questions": "This part collects some minor concerns on the paper, mainly in presentation and writing.\n\n1. In line 6, the article states that \"we introduce the concept of stochastic matrix ...\". This wording may create the impression that the concept of stochastic matrix is being introduced by this work.\n\n2. In line 52, the authors claim that FOCUS exhibits linear convergence for both **convex** and non-convex scenarios. I suggest to replace _convex_ with _strongly convex_.\n\n3. In lines 54-55, the authors claim that SG-FOCUS demonstrates **faster** convergence and **higher** accuracy. It is recommended to clarify the other side of the comparison. It is weird that a stochastic-gradient variant converges faster than its deterministic counterpart.\n\n4. In (2c), the authors may need to double check whether $x_{\\tau+1,i}^{(r)}$ should be $x_{\\tau,i}^{(r)}$.\n\n5. In lines 74-75, the authors state that \"Yet, this approach incurs increased communication costs, doubling them\ndue to the transmission of a control variate with the same dimensionality as the model parameters.\" However, [1, Sec. 4.2] shows that SCAFFOLD can be implemented with a single communicated variable. So this claim should be revisited and clarified.\n\n6. In Assumption 1, \"which occurs with **a** unknown probability\" should be \"which occurs with **an** unknown probability\".\n\n7. In the paragraph in lines 152-158, the authors use both $\\mathbb 0$ and $\\mathbf 0$. Are they the same?\n\n8. In line 184, \"equivalency\" should be \"equivalence\".\n\n[1] X. Huang, P. Li, X. Li. Stochastic controlled averaging for federated learning with communication compression. ICLR 2024.", "limitations": "yes", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strength**\n\nTo me, the idea in the paper is innovative and departs meaningfully from prior work. I believe the key contribution is a novel viewpoint to understand federated learning algorithms. Previous work often states that optimization methods in FL are special cases with decentralized algorithms with the communication network being the fully-connected graph, or equivalently, $W = (1/N) \\mathbf{1} \\mathbf{1}^T$. This paper departs from the mainstream and introduces a novel analytical framework grounded in the push-pull strategy in decentralized optimization.\n\n**Areas to improve**\n\n1. Is it possible to compare FOCUS with SCAFFOLD? I understand that they are just different. But I wonder whether the authors have any intuition behind the distinction of update rules.\n\n2. Do the authors have an intuition why pushing gradient $\\boldsymbol{y}$ requires column style rather than row style?  In other words, why does the update of $y_{r+1}$ requires the **sum** of $y_{\\tau, i}^{(r)}$ rather than the **average**?", "was_revised": true, "final_justification": "The authors have addressed all my concerns and I remain very positive on the article. To reiterate, I believe the key idea is innovative and departs meaningfully from prior work.", "rebuttal": "We sincerely thank the reviewer for their positive evaluation and encouraging feedback. We also appreciate the thoughtful comments and helpful corrections, which have allowed us to further improve the manuscript. Our detailed responses to each point are provided below.\n\n## Two main questions:\n\n> Area to improve 1:  Is it possible to compare FOCUS with SCAFFOLD?\n\nThis is an excellent and thought-provoking question. Actually, it prompts us to ask a broader, more fundamental question: **What is the connection between the gradient tracking technique in FOCUS and the variance reduction technique in SCAFFOLD?**\n\nPondering on this, in conjunction with helpful suggestions from other reviewers to compare with MIFA, has led us to some new insights. We get a preliminary conclusion: **in a simplified distributed computation scenario, the server-side update rules of SCAFFOLD, MIFA, and our proposed FOCUS can all be interpreted as distinct variants of the distributed SAGA algorithm.**\n\nTo illustrate this, we analyze a simplified scenario. We consider only a single local update per round and focus on the server-side update mechanism. In FL setting , the noise from stochastic gradient estimation is equivalent to the noise introduced by only sampling a subset of clients \\$S\\$. The global gradient and the average of sampled gradients has the following relation:\n\n$$\n\\nabla f(x) = \\frac{1}{N}\\sum_{i=0}^{N-1} \\nabla f_i(x) = \\frac{1}{|S|}\\sum_{i\\in S} \\nabla f_i(x) + {\\rm stochastic\\ noise}\n$$\n\nTo achieve exact convergence, an algorithm's update direction must asymptotically approach the true global gradient. But the client sampling restriction implies that we can only access the part of local gradient: $\\{\\nabla f_i(x)\\}_{i\\in S}$. The main idea of SAGA algorithm is that accomplishes this by maintaining an auxiliary memory of the most recent gradient computed for each client. With some slightly modifications, we adopt the following notation $g_i = \\nabla f_i (x'_i)$, where $x'_i$ is the last access time of computing the gradient, or equivalently the last participation time in FL setting. The SAGA update is \n\n$$\n\\hat{g} = \\frac{1}{|S|}\\sum_{i\\in S} (\\nabla f_i(x) - g_i) + \\frac{1}{N}\\sum_{i=0}^{N-1} g_i\n$$\n\nWhile gradient tracking (used in FOCUS) and variance reduction (used in SCAFFOLD/MIFA) are generally distinct techniques, they become analogous in our specific federated learning setting. The core idea on the server side is the same: the tracking variable $y_r$ is used to asymptotically track the true global gradient.\n\nTo see this clearly, consider the update rule for the tracker $y_r$ in FOCUS (simplified for this analysis):\n$$\ny_r = y_{r-1} + \\frac{1}{|S|}\\sum_{i\\in S} (\\nabla f_i(x_{r,i}) - \\nabla f_i(x_{r',i})) \n$$\nBy comparing these two update equations, the parallel becomes evident. The historical tracker $y_r$ in FOCUS plays the same role as the full historical gradient average $\\frac{1}{N}\\sum_{i=0}^{N-1} g_i$ in SAGA. The incremental update to the tracker in FOCUS is analogous to the correction term in the SAGA estimator. This observation reinforces our discussion in Section 5.2 regarding delayed gradient interpolation, showing that our tracking mechanism functions as a SAGA-like scheme in this context.\n\n\nSCAFFOLD and MIFA also fit this SAGA-like framework. They both use control variates (global $c$ and local $c_i$) to correct for the client sampling noise. As noted in the SCAFFOLD paper, their approach is SAGA-like in that it tracks this correction term incrementally, differing from SVRG, which requires periodic full gradient computations. The primary architectural difference between them is that SCAFFOLD maintains its control variates on the client-side, while MIFA stores them on the server-side.\n \nHowever, this analogy becomes less direct on the client-side, especially when multiple local updates are performed, as this introduces client drift dynamics not captured by the basic SAGA model. We will add a new section to the appendix to formalize this discussion and elaborate on these connections. We thank the reviewers again for stimulating this valuable thought and are happy to discuss more on this.\n\n\n> Area to improve 2:  why pushing gradient $\\mathbf{y}$ requires column style rather than row style?\n\nThis is another excellent and important question. It directly touches upon one of the central messages of our paper: that an unexplored family of Federated Learning algorithms might be systematically designed using column-stochastic updates. . \n\nFirst, we'd like to clarify that **an averaging-based approach is possible, but only under the specific condition that the number of participating clients, when  $|S_r|$ is fixed for all $r$.** Because we can rescale $y' = \\frac{1}{S} y$ for all $y$, where $S \\equiv |S_{r}|,\\forall r$, the algorithm will be equivalent upto some scaling factor on step size. Conversely, and more importantly, this implies that when the number of participating clients varies over time—a common scenario in practical federated learning—a simple averaging-style algorithm is no longer equivalent and cannot replicate our method's dynamics.\n\nA key intuition behind our design comes from the distinct properties of column and row stochastic matrices. **The column stochastic matrix, C, provides a \"mass conservation\" property.** Imagine a column vector $y$ where each element $y_{i}$ represent some mass of the $i-$th object. In the operation $y^+ = Cy$  ,the total sum of these masses, $\\sum_{i} y_{i}$ is preserved (to see that, left multiplying $\\mathbb{1}^T$). In our algorithm, $y_{i}$ is analogous to the local gradient information at client $i$. Using a column stochastic matrix ensures that the sum of these local quantities, which represents the global gradient (server-side), is not arbitrarily altered during aggregation.\n\nIn contrast, a row stochastic matrix, $R$, drives the system toward consensus. Under mild conditions on $R$, repeated the process that $y^+ = Ry$, i.e. $y^{\\infty} = \\lim_{n\\to\\infty} R^n y$. causes all elements of the vector to converge to a single value. However, **this consensus value is a weighted average of the initial elements.** In the context of our optimization problem, converging to a weighted average of gradients would introduce a bias. This bias would prevent the algorithm from converging to the true minimum of the original problem, thereby destroying the exactness and linear convergence properties we aim to achieve.\n\nWe hope this explanation sheds more light on our algorithm design and are happy to engage in further discussion on this topic.\n\n## Other Minor Questions:\n\nWe sincerely thank the reviewer for the careful proofreading and for identifying typos and ambiguities in the writing. We agree with all the points raised in questions 2, 4, 6, 7, and 8 and will incorporate these corrections into the revised manuscript. To keep our response concise, we provide detailed answers below for the remaining questions.\n\n> Q1:  we introduce the concept of stochastic matrix ...\"\n\n We appreciate the thorough thought of the reviewer. \"First, we review the concept of stochastic matrix ...\" should be a better wording.\n\n> Q3: ...  claim that SG-FOCUS demonstrates faster convergence and higher accuracy,\n\nThanks for pointing this out! We agree that we should modify this contribution point as follows: \"We also introduce a stochastic gradient variant, SG-FOCUS, which demonstrates faster convergence and higher accuracy than the other baselines (e.g., FedAU, SCAFFOLD), both theoretically and empirically.\"\n\n>  Q5: .. SCAFFOLD can be implemented with a single communicated variable...\n\nWe thank the reviewer for this precise reference and for pointing out the need for clarification. Our initial statement was imprecise, and we will revise it. Just one point to clarify that in [1, Sec 4.2] the uplink (client-to-server) communication in SCAFFOLD can be optimized to a single variable. However, the downlink (server-to-client) communication still requires transmitting two variables: the global model and the server control variate (per Algorithm 4, line 5 in [1])."}]

Author rebuttal:

Meta-review: The paper presents a new algorithm for Federated Learning (FL) under arbitrary client participation and data heterogeneity. Past algorithms with guarantees in this setting suffer from slow convergence due to a decaying learning rate. The authors propose a novel algorithm, termed FOCUS, with improved convergence guarantees. Strengths of the paper include both the new algorithm but also a new proof technique, that approaches the analysis of the algorithm's performance through a decentralized algorithm over time-varying graph, and allows for the representation of FOCUS but possibly other algorithms as products of stochastic matrices. Several reviewers found this connection/point of view interesting and insightful, and worth reporting to the NeurIPS community. Reviewers also found the theoretical contribution to be solid, meaningfully departing from prior art.

Reviewers have asked for several potential improvements that could improve the camera ready version of the paper:

1. Additional experiments including more varied participation settings as well as comparisons to competitors such as MIFA and FedVARP.

2.   One reviewer remained concerned about the artificiality of the dependence of the convergence guarantee on the number of clients, and remains convinced that it is an artifact of the decreasing  (as $1/N$) step size, rather than the linear speadup that the authors allude to in their response. This should be clarified, ideally via contrasting to how bounds are presented in other papers, ensuring a correct "apples-to-apples" comparison.

3. Several reviewers requested that the stochastic setting, being a main technical contribution, to not be relegated in the appendix, but it has a more prominent position in the main text. Perhaps this can be done by taking advantage of the additional page for the camera-ready version of the paper.

4. The same is true about the overall proof-by-stochastic matrices framework: one reviewer wanted to see a discussion on why this framework is important, how it informed the design of SGFOCUS/FOCUS, and whether it has other applications. Could it, for example be applied to other FL algorithms with arbitrary client participation, like FedAU [Wang and Ji, 2023], FedAWE [Xiang et al., 2024], MIFA [Gu et al., 2021]. If not, it would be great if the paper indicated why/what is the key challenge/point of failure.

5. Finally, several of the smaller issues (typos, questions regarding intuition) raised and addressed during the rebuttal/discussion phase should also be addressed in the final version.
Decision: Accept (poster)