Non-Convex Federated Optimization under Cost-Aware Client Selection
Authors: Xiaowen Jiang
Anton Rodomanov
Sebastian U Stich
Venue: ICLR 2026 Oral (2026)
Keywords: Client Sampling
SAGA
Second-order Similarity
Composite Gradient Method
Variance Reduction
Primary area: optimization
TL;DR: We propose a composite gradient method with SAGA and recursive gradient estimator for non-convex federated optimization that can exploit second-order similarity and achieve high communication and local computation efficiency.

Abstract: Different federated optimization algorithms typically employ distinct client-selection strategies: some methods communicate only with a randomly sampled subset of clients at each round, while others need to periodically communicate with all clients or use a hybrid scheme that combines both strategies. However, existing metrics for comparing optimization methods typically do not distinguish between these strategies, which often incur different communication costs in practice. To address this disparity, we introduce a simple and natural model of federated optimization that quantifies communication and local computation complexities. This new model allows for several commonly used client-selection strategies and explicitly associates each with a distinct cost. Within this setting, we propose a new algorithm that achieves the best-known communication and local complexities among existing federated optimization methods for non-convex optimization. This algorithm is based on the inexact composite gradient method with a carefully constructed gradient estimator and a special procedure for solving the auxiliary subproblem at each iteration. The gradient estimator is based on SAGA, a popular variance-reduced gradient estimator. We first derive a new variance bound for it, showing that SAGA can exploit functional similarity. We then introduce the Recursive-Gradient technique as a general way to potentially improve the error bound of a given conditionally unbiased gradient estimator, including both SAGA and SVRG. By applying this technique to SAGA, we obtain a new estimator, RG-SAGA, which has an improved error bound compared to the original one.

Published as a conference paper at ICLR 2026
NON-CONVEX FEDERATED OPTIMIZATION UNDER COST-AWARE CLIENT SELECTION
Xiaowen Jiang
Anton Rodomanov
Sebastian U. Stich CISPA
Saarland University & CISPA
CISPA
x aowen. fineenniingggl jiangeci spa. de
anton. rodomanoveci spa apa.dd. de
st ch@c spa de
ABSTRACT
Different federated optimization algorithms typically employ distinct client- selection strategies: some methods communicate only with a randomly sampled subset of clients at each round, while others need to periodically communicate with all clients or use a hybrid scheme that combines both strategies. However, existing metries for comparing optimization methods typically do not distinguish between these strategies, which often incur different communication costs in prac- tice. To address this disparity, we introduce simple and natural model of federated optimization that quantifies communication and local computation complexities. This new model allows for several commonly used client-selection strategies and explicitly associates each with a distinct cost. Within this setting, we propose a new algorithm that achieves the best-known communication and local complexities among existing federated optimization methods for non-cone con-coneex optimization. This algorithm is based on the inexact composite gradient method with a carefully constructed gradient estimator and special procedure for solving the auxiliary subproblem at each iteration. The gradient estimator is based on SAGA, a popular aariance-reducee gradient estimator. We first derive new variance bound for it, showing that SAGA can exploit functional similarity. We then introduce the Recursive- -rrdiiett technique general way potentially improve the error bound of a given conditionally unbiased gradient estimator, including both SAGA and SVRG. By applying this technique SAGA, we obtain new estimator, RG-SAGA, which has an improved error bound compared to the original one.
INTRODUCTION
Motivation. Federated Learning (FL) is a distributed training paradigm in which a central server coordinates model updates across multiple remote clients -such mobile devices or hospitals- without requiring access to their local data (McMahan et al.) 2017] Kairouz et al. (022). This framework enables collaborative learning on decentralized data, but introduces new algorithmic challenges due to the distributed nature of optimization.
key issue in FL is the high cost of communication between the clients and the server. Clients may be intermittently available (Konečný et a (2016) and connected over slow or unreliable networks. These constraints make it critical to design optimization algorithms that minimize communication costs, particularly in settings with partial client participation.
Various federated optimization algorithms have been proposed to address communication efficiency, each often relying distinct client-sclection strategies. Some methods communicate only with a randomly sampled subset of clients at each round, while others need to select the set of partici- pating clients more carefully employ hybrid schemes that combine both strategies. While prior works (Woodworth et al. 2018 Korhonen & Alistarh 2021 Patel et al., 2022) Zhang et al.) 2013 Davies al.] [0200] Scaman et al.) 2019) introduced few models for federated optimization, they do not account for the varying costs of each client-selection strategy, which can in practice differ due to factors such as client reliability, device heterogeneity, and network conditions. Consequently, existing metrics such as the number of communication rounds are not entirely fair for comparing methods such scenario.
"CISPA Helmholtz Center for Information Security, Saarbrücken, Germany.

---

Published as a conference paper at ICLR 2026
For instance, optimization methods based on SARAH Nguyen et al. 2017: Li et al. 202 have been shown to be communication-efiin
in finding an approximate stationary point (Mishchenko) et al.] 2024; Khaled & Jin 2023). This efficiency arises from the method's ability to exploit dissimilarity (d) between local and global objectives. In many practical scenarios- concrros--ucch -such as statistical
or semi-supervvisd learning (Chayti & Karimireddy [002 Karimireddy et al.) 202T] Khaled & Jin
2023) is often small, leading to substantial theoretical gains in communication cost. However, SARAH-based methods require periodic full synchronization with all clients in order to compute full gradients. This can be impractical in real-world large-scale federated systems, where clients may be intermittently unavailable due to energy constraints, network issues, or user behavior.
In contrast to SARAH, methods such as SAG (Schmidt et al. 2017) and SAGA (Defazio et al. 2014) are naturally better suited to the partial participation setting in FL.. These methods update the model by sampling a small subset of clients at each round and using locally stored gradients. As result, they avoid the need for periodic full synchronization, which makes them more compatible with federated systems where only a fraction of clients may be available at any given time. Despite this advantage, the existing communication complexity of such methods depends on the individual smoothness constant Lmax (Reddi et al. 2016 Li et al. 2021b Karimireddy et al. 2020), which can be significantly larger than the dissimilarity constant 8. Consequently, it remains unclear whether such methods are more communication-effiiii fundamentally different client-selection strategies with different constant dependencies.
than SARAH-based methods, since they rely on
Contributions. In this work, we aim to develop optimization algorithms that are efficient both communication and local computation in the setting where client-selection strategies incur different costs. Our main contributions are as follows:
We propose new model formalizing the concept of federated optimization algorithms and defining information- based notions of communication and local complexities. This model associates the non-uniform costs with different client-selection strategies, enabling fair comparisons across optimization algorithms. (Section
Within our new model, we propose a new gradient method that achieves the best communication and local complexities among existing first-order methods for non-convex optimization. This method is based on the inexact composite gradient method (I-CGM) with a carefully constructed gradient estimator and a special procedure for solving auxiliary subproblem at each iteration. (Section(
Specifically, we first study the convergence of I-CGM for arbitrary gradient estimators and present an efficient technique for solving the auxiliary subproblem. Our technique is based on running the classical composite gradient method locally for random number of iterations following
geometrical distribution with a carefully chosen parameter. (Section 3
We then analyze the SAGA estimator and establish new variance bound for it that only depends on without requiring individual smoothness, improving upon previous results showing that SAGA exploit functional similarity. We also study SVRG as another example that can be incorporated into I-CGM. (Section 4
Finally, introduce the Sesturiie--rradien (RG) technique general way to potentially improve the error bound for a given conditionally unbiased gradient estimator, including both SAGA and SVRG. Applying this technique to SAGA and SVRG, obtain new RG-SAGA and RG-SVRG gradient estimators with better error bounds compared to the original ones. (Section 5)
We discuss our results in detail in the context of related work in Appendix and summarize them in Table
PROBLEM FORMULATION
We consider the following distributed minimization problem:
{ [[xx)==]]] ((xx)=-1 x2
[ }
min XER
where each f:: Rd - is a differentiable function which can be directly accessed only by client Notation. We abbreviate [n] := (1.2.....ni) n). For a finite set A and an integer 1 S m < AA] (AA) denotes the power comprised of all m-element subsets of A. ||-|| denotes the standard Fuclidean
2

---

Vf(y) which Published as a conference paper at ICLR 2026
Table 1: Summary of efficiency guarantees (in BigO-notation for finding e-stationary point. 1-CGM-RE RG- SAGA achieves the communication and local complexities. the precise description of the problem classes, notations, as well as the discussions of the methods, see Appendix
Communication complexity
Assumption
complexity
type
Centralized
CAR
F8
None
FedRed
Jiang
2024a
Calti A
2.1 2.3
None
FedAvg
McMaahan al.
2017
Cal Lag
Kinguus liney"))
15, BGD
None
FedDyn
Acar al 2021
Castn Cyrres frery" P
18
unknown
None
MimeMVR Karimireddy et
Bugg
IS, BGD,
Lor Landenee
CB-LGI Pitel
2022
Ca( Ca(Sigh Sandaarr
Prany
IS, BGD,
Sandian
None
Scaffold (Kariiroddy al
2020
Catti CA LeyssP
IS
SAG
SABER full Mishhhenko et al 2024
CAPm Cj bbronbi
SD
unknown
PAGE
SABER-portial (Mishchenko et al.
2024
Cattin Cy C.
Auy
SD, BGD
unknownn
SARAH
I-OGM-RG-SVR (ours)
Catti (Ondi byy Sordiitty/ttttttta (aatemmte)
Thep
(1 d.
RG-SVRG
I-CGM-RG-SAGA (ours)
CaRi Cx (Arb
2.1
2.2 2.3
RG-SAGA
norm in IRd. We use B[-] to denote the standard (full) expectation. We write Eg[-] for the expectation taken w.r.t. E. We assume that the objective function in problem (I) is bounded from below and denote its infimum by f". We denote F f(x") f" where x" is the initial point.
2.1 FEDERATED OPTIMIZATION ALGORIHMM AND THEIR COMPLEXITY
Due to space limitations, we defer the whole definitions of federated optimizaton algorithms and their complexity metrics to Appendix C
which is encouraged to read before proceeding.
2.2 PROBLEM CLASS
We study optimization problem | in which the client objectives exhibit an underlying similarity structure. Specificallyy we use the following two assumptions that relax standard smoothness assump- tions. The first quantifies the deviation between the delegate function fi and f. For an index i E [m]. we use h2 := f ft to denote the difference function.
Assumption 2.1. There exists A > 0 such that for any x, E Rd, we have:
Vh1 (y) < A X -yll
Alternatively, one may define a uniform dissimilarity constant Amax Karimireddy et al. 2020 Jiang et al. 2024a) such that for any E [m)] it holds that (x) [h, S max
y||- In this
work, we focus on A₁ since it can be much smaller than Amax-
The second assumption characterizes the average dissimilarity among all local functions.
Assumption 2.2 (Khaled & Jin (023) Jiang et al. (202bb): Lin et al. (024): Jiing et al. (202aa):
Takezawa et al. (203))) There exists > O such that for any x, y E T we have:
Vha(x) - vha & 82 X 2
(3)
The left-hand side of (3) is equal to 1 can be interpreted as the variance of each fi has -ipschi gradient, then we have A < 2T and 5 & Iynax- Therefore, both conditions are weaker than assuming each fr is Lipschitz-smooth. We refer discussions in (Jang let al. 2024b) for more properties and details.
(z) Vz()) where is selected uniformly random. If
The previous two quantities ò and A will only affect the communication complexity of our algorithms, while the local complexity additionally depends on L1 which is defined as follows.
Assumption 2.3. There exists L1 > 0 such that for any x, y Rdd, we have:
V (x) - V)i(y)) < L ||x - yll
(4)
3

---

Published as a conference paper at ICLR 2026
3 INEXACT COMPOSITE GRADIENT METHOD
Inexact Composite Gradient Method. We first introduce the Inexact Composite Gradient Method (I-CGM), which serves as the backbone of our approach. Consider the composite reformulation of the problem f = fi + [f fi] fi + h1 Let À > 0 and x" E IR be the initial point. At each iteration t 0, I-CGM computes approximation of the gradient g' V fxxx) and defines the
next iterate as:
x
arg min [((x) = f1 (x) + (1 (g' - Vx((x'),xx - x") ブタ x x
:-
x11
xER
(I-CGM)
where both the imaccuracy in solving the subproblem and the approximation error (defined below) are assumed to be sufficiently small (to be specified later):
1x S (x := [[VF(( II,
E = -
(5)
In the following statement, we provide the general convergence guarantee for I-CGM. The proof can be found in Section F.I in the Appendíx.
Theorem 3.1. Let I-CGM be applied to Problem ① Suppose Assumption 2.1 and condition are
satisfied. Let X > A.. Then for any T 1, we have:
[V(x2)1 (A+
112
12(A + A1) F A-A A
12(X+ A1)
T-
A,) +
+4
c
1=
1=0
We see that each subproblem can be solved inexactly without affecting the convergence rate (up to absolute constants), provided that the error term E/ ei is of the same order as the first two terms on the right-hand side. Moreover, if the approximation errors T Σ can also be bounded by the first two terms on the left-hand side, then the convergence of the gradient norm is guaranteed. If there exists randomness either in solving the subproblems or in constructing the estimators, then these conditions are required to hold in expectation. Specifically, we obtain the following corollary.
Corollary 3.2. Following the same settings as in Theorem 3.1 subproblems satisfy:
If the inaccuracies in solving the
T-1 Σ BEel <
(A + 21) FOr Σ Σ
T-1
F S Fix'',,
(6)
A A t=0
1=0
and the approximation errors satisfy:
12(A+ + 12 A1-
T-1
T
+
Σ
2
G + (A+A 2
X1
(7)
t=1
then for any T 2 have:
32(A + ,1 pd
E | <
X A T
where G = (xIV 12 x2 = El||** - x11 Σ = Blllg* V)((')] and xT is
uniformly sampled from (x') )=)==
When g is the exact gradient V (x(x') for all 1 0. then I-CGM is reduced to CGM that is widely
used for solving Problem (I), particularly because of its ability to exploit functional similarity and
reduce communication costs (Hendrikx et al., 2020 Jiang et al. 2024a Lin et al. 2024 Khaled &
Jin 2023: Jiang et al. 2024b Mishchenko et al. 2024 Kovalev et al. 2022). Indeed, if A
and the accuracy condition 6 is satisfied, then E V
[P
62 after T 0 A, iterations.
4

---

Published as a conference paper at ICLR 2026
In contrast, the iteration complexity of Gradient Descent depends on L, which can be larger than A1 (2.1) when fi is similar to f. However, CGM has sub-optimal communication complexity in terms of n. Indeed, let assume, for simplicity, that m = 1. Then each iteration involves: 1) computing the full gradient fxx),, which requires n sequential communication rounds using A-CSS, and 2) additional round using D-CSS for solving the subproblem. Consequently, the total number of communication rounds with A-CSS and D-CSS is N = nI' and ND = T respectively. O(Can'))
The communication complexity of CGM thus: CANA ND CAnit
O(CA " A This linear dependency on can be prohibitive in large-scale federated learning settings and worse than the complexity of stochastic methods such PROXSARAH (Pham et al. 2020), SPIDERBOOST (Wang et al. (019)) and PAGE (Li et al. 2021a), each of them achieving:
although they rely on a slightly different assumption of average smoothness Moreover, the dependence on Ç can become much larger in scenarios where using A-CSS is costly.
O VoLF"
Solving Auxiliary Subproblems. In this section, assume that is L -smooth and study how to achieve the accuracy condition (6). Recall that each subproblem Fr consists of a smooth function
<xx) (x) and a quadratic regularizer (x) = (g' - V fi(xx) x') + À ||x x²11². Let us solve it using the standard composite gradient method (CGM), which proceeds as follows: For
k 0, 1,.,, Kr
Yk+1 arg min f ((y)) + (Vo(y)). -yt) + yER"
L1 ||y -illl v((r))
2
(8)
1 (Liv + Ax' Vf(()) - -g' -f-((tt)
X+L
Each CGM step monotonically decreases the function value of Fi (see Lemma F22. Therefore, we can initialize yij x' and choose x-+1 to be a certain iterate of (y*) Then the condition on Fi(x++1)= < (x') is satisfied. We next study the number of local steps K₁ required to achieve the second inequality in condition (6)
Fixed Number of Local Steps. Let K, = K 2 1 be a constant number and let x**1 be the iterate with the minimum gradient norm of F, among (yr) We use the notation x++1 CGMconst (x, K, x", for this process.
The goal is to upper bound ΣTs of where e, FIVF + D)I For each 2 0, have: ef R (L(( F((yk)) L1(f("))/(yX)+HH x" are not necessarily the same, we cannot telescope f(x") fly when we sum up e?- Instead, the
(see Lemma F22 and F.1pp However, since y'x and
K
"best" we can do is to upper bound f(x') - f(y')) by f(x') - f Then by further upper-bounding
the summation of Σt= local steps to achieve the desired accuracy condition (6). The proof can be found in Section F.2.
= [f(xx) f*] in terms of F and E2 can be shown that we need K
Lemma 3.3. Consider Seciider--CGAA [-CGM with x*+1 CGMoonet (A, x,,',g .g)) under Assumption 2.1 and 2.3
Let T 2 be the fixed number in condition (6). Then by choosing X D and K KT == X-A1
the accuracy condition (6) is satisfied.
Random Number of Local Steps. We now allow the number of local steps K₃ to follow geometric
distribution a common technique used to derive last-iterate recurrences (Allen-Zhi (0088)). When applied to solve the subproblems in I-GM this approach yields algorithm that is efficient in local computation.
Let us consider CGM 8 with K, = K, + 1 iterations where K, ~ Gcom (p). that is P,K, = k) = (1 pp for each k (0, 1,,,,....... The solution is be x+1 YK,- We the notation +++ CGM (), K2, x² ,')) for this process.
In contrast to the convergence rate of using deterministic K, we can now show that Ex [ef] S Lep
Li+X Eg [F(('t) (1)) Using ER, [F((x') Fx(x++1) & Ex, [xx fxx+11 + + N
we get the telescoping term (x'( f(x +1)] after passing to the full expectation, which allows to improve the total amount of local computations.
Yx,y y E Rdd holds that Ei_ [VV(()) vflly)) < 1? xx y112 and have & T..
5

---

Published as a conference paper at ICLR 2026
Lemma 3.4. Consider I-CGM with x²+ CGM (A, K,, g') where K, Geom(p) under
Assumption 2.1 2.3 Let T 2 1 be the fixed number in condition (6). Then by choosing > A
and p A- 8(+++A) 1, the accuracy condition (6) is satisfied.
To achieve the accuracy condition (6). the number of local first-order oracle queries required by using the random K, at each iteration in expectation is Ex, [ = 1 ~ f., p X which improves upon the
previous result of T obtained by using fixed number of K.
So far, we have studied how to solve the subproblems I I-CGM such that the accuracy condition (6) satisfied. We now turn to constructing the gradient estimator g' that has the desired approximation error (7). Meanwhile, we aim to improve both the dependence on and CA in the communication complexity of CGM. The main strategy design gradient estimator whose approximation error depends only on the similarity constant while avoiding periodic full synchronizations.
4 BASIC APPLICATION EXAMPLES: SAGA SVRG
In this section, we present two algorithms that maintain an approximation of the gradient, G R
v (xx) for 2 Each algorithm starts with an initial point x", Then each iteration 2 0, G is computed first, after which the next iterate x is computed. In what follows, for set S E [m]) and we use fs= == Eies fi to denote the average function over this set.
m E [n].
For convenience of presentation, we use the following notations throughout the rest of the paper.
n2
71 m
and 8% == 4m 6²
pl
SAGA Estimator. SAGA estimator is variance- variance-reduction technique based on incremental gradient updates. originally designed for centralized finite-sum sumt minimization (Defazio et al.) (2014). In this section, we adapt this estimator to the federated optimization scenario and study its properties.
The SAGA estimator defines:
G fx("). G'=Vf(x') G' b's,
b S.
+ b
2
(SAGA)
where S: E ((m) is uniformly sampled at random without replacement, b'g == Eies, b by. m Eies, bj b' == E/= and for any i [n], by is recurrently defined as:
(x") if St. b
byd = V)(("), bj (x()), bf
12 2.
otherwise,"
We have the following recurrence for b' (the derivation can be found in Lemma R.3
b' = b'=b'-14 +
7m [Vs, (x') -b, t 2
(10)
Implementation. At the beginning, when t = 0 and 1, each client i = 1,..., n computes (x*) and initializes bj and sends the result the server; the server then aggregates these results computing fx(x') to initialize G and b'. This requires two full synchronizations (2[mm communications rounds using A- A-CSS).
each iteration 2 2, the server contacts the randomly selected set of
clients S, using R-CSS and sends xf to them. Each client E S, computes by (f(('') and sends
by- 88-bo b back to the server. The server then updates b' according to (T0) and constructs the gradient estimator G' using the stored b'-1 according to (SAGA).
Each client i thus needs to store single vector bj. On the server side, only the aggregated vector b' and the iterate x* need to be maintained. The memory overhead of the SAGA estimator is thus very small in the federated learning setting, similarly to the SAG estimator (Schmidt et al. 2017) used in SCAFFOLD (Karimireddy et (020).
Properties of SAGA. It is not difficult to show that G is conditionally unbiased estimator of Vx(x'), namely, Es, [ Vx(x'). We next present a new variance bound for SAGA that is controlled by the constant 6. The proof can be found in Section F.3.

---

Published as a conference paper at ICLR 2026
Lemma 4.1. Consider the SAGA estimator (SAAA)
under Assumption 2.2
Then for any t 2 2,
Bs' = fx(')) and for any T 2 1, we have
Σ
T
of
2m G7 + nm 1+ v n Σ
7m
T-1
G + 4n
8
Σ
T
2
(n 1)
1=0
1=2
1=2
where of : Esg I| (G'-VS((X)) VS((
Of = Es [I | Xi
= Es s |||
-x
x
11] and
S/y St))
Note that this variance bound depends on G Gb.....,y.... G4 and X² X2. 1². which aligns with the terms on the right-hand side of the desired error bound 7 However, the coefficient in front of G3 in this bound can be larger than 1, whereas 7 requires it to be strictly less than 1. Consequently, the requirement is not met and we cannot directly incorporate the SAGA estimator into [-CGM by setting g' = G We will show in Section 5 that this error bound can be significantly improved by using the recursive gradient estimation technique.
Remark 4.2. Instead of computing the exact gradients (=x) and (x((') at the beginning which requires full synchronizations, requires only one communication round using R-CSS. The resulting communication-complle estimate will now additionally depend on the inexactness of the initial approximation but this strategy often works well in practice (Figure J.1). See Appendix for detailed discussions.
possible start with an approximation G ff(x)). This
SVRG Estimator. Another possible choice of the gradient estimator is the SVRG estimator Johnson Zhang 2013). There are different variants of SVRG, and here we consider the so-called loopless- SVRG estimator (Kovalev et al. 2020) for simplicity.
The SVRG estimator defines:
G vf(x'),
G = Vs, (x') Vf(w") Vfs, (w"). t t
(SVRG)
where S, E ((n)) is uniformly sampled at random without replacement,
x if = 1, w w w'
t t2 1
otherwise,
and Wi is Bernoulli random variable with parameter PB, i.e., Plus, = 1) = PB E (0.
Properties: It is not difficult to show that the SVRG estimator G is conditionally unbiased estimator of fx*)). namely, Es, [ = f(('') Moreover, the variance controlled by d. The proof can be found in Section F.3.2 where the implementation of the estimator is also provided.
Lemma 4.3. Consider the SVRG estimator (SVRG) under Assumption 2.2
Then for any t 2
1, Es, [G'] (x()) and for any T 2 1, we have: Σn of S
162
Et=l
X2. where of
Es |||G' [((x') Xi Eug 1/ ||||x* - x' 113), and Wlo] (W), ...,w)) We).
We can incorporate the SVRG estimator into I-CGM by setting g' = G This requires setting PB 1. and X = A + 7m to achieve the error condition 7 The resulting communication Am
complexity of the method is OCA.n. + (CxA)+ +C Can... ) ) ) which still has linear dependence am (See Theorem with the proof that the reader can inspect if interested). Note that unbiasedness needed to incorporate SVRG directly into I-CGM. However, becomes necessary later for the recursive gradient technique, which we discuss in the next section.
=²
5 RECURSIVE GRADIENT ESTIMATOR + EXAMPLES (SAGA AND SVRG)
In this section, we present a general formular of the recursive gradient estimator that can potentially improve the eгror bound for a given conditionally unbiased gradient estimator Gt fx(('). Formally. we consider the following setting.
Assumption 5.1. For any t 2 0, it holds that: 1) St is independent of x2 xo...... ,,...,,," +1, Go ......, G!-1; 2) Es, G (x(x).
7

---

Published as a conference paper at ICLR 2026
The recursive gradient estimator (RG) defines:
g = v)((x), g" g+ = (1- 3)g' + 3G' + Vss fss t t2 0
(RG)
where 3 E (0, 1] and S. E ((m)) is uniformly sampled at random without replacement.
Note that the indexing here differs from the previous ones. The algorithm starts with an initial point x². At each iteration 2 0, the estimator g' R fxxx is computed first and it depends only on G and 1, After that, the next iterate x is computed. Therefore, x is independent from S, while previously was dependent on it (if we use the SAGA/SVRG estimator).
Inspired by previous works, the expression of g incorporates both recursive gradient update and momentum (Chayti et al. 2025] Gao et al. 2024). This expression unifies several existing methods: When 8 0, the estimator reduces to the SARAH update rule (Nguyen al. 2017). When G is replaced with the SAGA estimator, then g' recovers the structure of ZEROSARAH (Li et al.
2021b). When G Vis, (x(+1) and V fss, (x*+1)- fss, (x') is multiplied by 5, then it becomes STORM (Cutkosky & Orabona 2019). In our formulation, G is a general similarity-aware
estimator of V fxx) that satisfies Assumption 5.1 allowing us to flexibly instantiate the framework
with various variance-reduction techniques.
For instance, can combine RG with SAGA SVRG
We refer the resulting estimators as RG SAGA and (VRG) Note that S, in the formulas for SAGA and and SVRGlis exactly the same random index set that is used in the RG they share the same randomness for the sake of efficiency,
Implementation. At the beginning, each client i = I,..., computes V (x") and sends the result to the server; the server then aggregates these results, computing f((x") to initialize go. This requires one full synchronization. Then x' is computed based on g" At each iteration t 2 0. the server uses R- CSS which generates random subset S,, For RG SAGA the server sends x--1, x'
to the clients in S,. Each client E S, updates bf V x²) and sends [x((x+1) along with 1) to the server. For RG SVRG the server sends x'-1,x x" and w' to the clients which then return the gradients evaluated at these three points. wf = 1, the server additionally computes the new gradient V f(w") performing one full synchronization. After receiving all the vectors, the server can compute fs, (x* xxf+1) I). ffs, (x"), G' and g+11_
by 25-bb-1 bb-1 (when i 2 2) or by (when
For RG SAGA each client i needs to store a single vector by and the server needs to maintain two points x F1 and x", and two vectors b' and g'. For | SVRG clients are stateless and the server is required to maintain three points x x', w' and one vector V f(w").
Lemma 5.2 (Error bound for RG). Consider the RG estimator
(RG) under Assumptions 5.1 and 2.2 282
Then for any T 2 1, we have: Σt E < 2-8
28
Et=
T-11
of +
I1'
x² where Σ
=t=
23-8
Es,- Illg' [x(x))]3) of == E G (S.....,S)) S.).
[x*)
X² = Esp [|xx*
11111 and Sig :=
The proof can be found in Section F441 We next show that the error bound of both SAGA and SVRG can be improved by combining them with and adjusting the parameter B3 For instance, by combining Lemma 5.2 and Lemma 4.1 I
we obtain the following result for RG SAGA
Corollary 5.3. Consider the RG SAGA estimator under Assumptions
5.1 and 2.2
Then for any
T 2 1, it holds that:
4 4. Im G2 +
2.( - 1 + v n2 Pkm
8, 82 + 282 2
D2
2 Bm
(2 (3)
G
2, ,32
Xi
t=0
t=
[=1
where D = p |||g*
vf(xt) Of = ES
x2 E ESp |||x
x - ||2]
and Sig = (So, S0.......... S.).
By choosing 3 ~ وا
n.m we get
T
2
4m Gf
+ ΣL X². Compared with the bound with RG achieves improvement by
Σ
m
the original variance bound for SAGA a factor of nmm
(Lemma
The error bound for the SVRGG can be improved in similar way.
8

---

Published as a conference paper at ICLR 2026
Corollary 5.4. Consider the
RG SVRG
estimator under Assumptions 5.7 and 2.2
Then for any T 2
1, it holds that: Et
- 83"6
26
>i=1 Xi, where Σ == Es -
Ill'' - Vf [1%
28 8
x² - x x x
11
S/ (So. .... Se) and W|d] == (wi, (wi,-..,,4 Wt).
Compared with the original variance bound for SVRG (Lemma 4.3 the new bound achieves an improvement by a factor of 1/pB by choosing 3 pB.
We can now incorporate both enhanced estimators into I-CGM
It can be shown that the iterates
{x" Lo 1t generated by [-CGM
or [-CGM RG SVRG and the corresponding sequence
{G Tt= satisfy Assumption 5.1 (See Lemma F.5 and F.6.
COMMUNICATION AND LOCAL COMPLEXITY OF I-CGM-RG
We ready establish the complexity of estimator. We first present the result for RG-SAGA. The proof can be found in Section F.5.1
with the RG SAGA and RG
Theorem 6.1 (I-CGM-RG-SAGA), LeiT-CGM be applied to Problem 7 under Assumptions 2./
2.2
and 2.3 where x = CaM (A, K2, x', g²) with K2 ~ Gcom(p) and g¹ is generated by the RG
SAGA estimator. Then by choosing X = 3 + 113 / 6m. 3 = 112m and S[L1+X].
>-A, after T
(256 (A, +38 1388, (mmBB)) 1 iterations, we have B|IV ) E², where x" is is uniformly sampled
from (x* )T The communication complexity is at most 2C [mm (CC (256(A) +338, +388./mmm
/m 5m
2²
11+28 A1428/mm and the local complexity is bounded by 14 + 2n 512(7A, +283, / +2L,)
+
82
The communication complexity of RGGGM-RG-SAAN is of order CAnA + OR A1+((v the local complexity is of order n'm + (Antynmmm when (Art/mmmm)e )
and
2 1. The 7'm term
comes from 7ym sequential rounds with A- A-CSSie for computing the full gradients in the beginning.
Comparison: RG SVRG Estimator. The communication complexity of I-CGM-RG-SVRGiN is O(CATi + (CrA, + +VC A where C^ also affects the term involving e (see Appendix F6 for details and the result of the local complexity).
7 NUMERICAL EXPERIMENTS
In this section, we verify the theory of the proposed methods in numerical experiments. We set CA= = CR = 1 in the definition of communication complexity for all the experiments. We choose this case to demonstrate that even when A-CSS and R-CSS are equally cheap, our proposed methods already outperform several commonly used algorithms. (The study of the scenario when CA > Cr can be found in Appendix III.T)
I.
Quadratic minimization with log-sum penalty. Consider the problem of f(x) = (((x)
with f((x := Σ ! (A.,(x bb,), x- bb,))+E log (og(1++|xx)) where a > 0, b,j E Rd. Ai, E R ddd is a diagonal matrix, and is an indexing operation of a vector. We set a = 10, = 5, 100 and
1000. Each coordinate of b,,, is uniformly sampled from [0, 10). To generate Ai,. we first sample diagonal matrix À with entries uniformly distributed in [0, 110), and then add bn diagonal noise matrices whose entries are sampled from [0, 18). Each resulting A.,; is clipped to the interval [1, 100] on the diagonal, and some eigenvalues are further set close to zero. Consequently, the dataset satisfies 0 Z Aij A 1001 for any i,J, with A RJ ô Rs 5 and Lmax Re 100. We set m vn.
For I-CGM-RG, we set p 7. A 5 A., 77 = 2T and G = vt We compare two proposed algorithms against SCAFFOLD (Karimireddy et al., 2020)) FEDAVG (McMahan et al.) (017) (with sampling), SABER-FULL (Mishchenko et al., (2224) (with PAGE), SABER-PARTIAL Mishchenko et al. 2024) (only compute full gradient once) and GD (running directly on f). For SVRG-based methods, the expected number of communication rounds at each iteration is roughly m. n + m, which is twice as large other methods. From Figure | we observe that: 1) I-CGM-RGC -R-R---GGGG is the most efficient in both communication and local computation. 2) SCAFFOLD cannot fully exploit O-similarity as its local complexity is comparable GD (the theoretical local complexity of both

---

Published as a conference paper at ICLR 2026
100
109
200
107
100
10-
101
305
107
100
200
300
100
500
6.00
700
2000
4030
6200
5500
10000
12005
16300
Commmantaaann BXR
complenty
Junt
SAGER
Figure Comparisons different algorithms solving quadratic minimization problems with non-convex log-sum penalty.
1."
344
10-4
389
350
200
255
300
355
200
300
170
200
LOGM.RG tours)
SGM-RRGSVRG (ours)
Fockvg
SABER
Figure 2: Comparisons different algorithms on two LIBSVM datasets using logistic loss with non-convex regularizer.
methods depends on Lmax). Finally, J-CGM-RG----AAAAA SAGA with different initialization strategics can be found in Figure I.I
Logistic regression with nonconvex regularizer. We now experiment with the binary clas- sification task two real-world LIBSVM datasets (Chang & Lin 2011).
We use the
standard regularized logistic loss: f(x) n - with f((x) == M Σド log(1
[x]] exp(-Mt Vi (ai,,)))) + Ed= I+[*] where
0. (a.j. Bi.)) E Rd+1 feature and la-
1 and bels and M = Ei= is the total number of data points. We use -x5xx" x and 10. We plot the local In and 8 by computing (x') - (i((++))]] |xx
EE [x,x(x') (x,+))) /|x+* - along the iterates of I-CGM-RG-SAGA.
x++1|²
From Figure 2. we observe that 5 is much smaller than L2 for the mushrooms dataset, while being comparable for the duke dataset. However, for both cases, I-CGM-RG-SAGA remains the most efficient in communication complexity.
Deep learning tasks. We defer the study of neural network training to Appendix where more experiments and details can be found.
CONCLUSION
We introduced a new simple model for comparing centralized distributed optimization algorithms, where different client-selection strategies are associated with non non-uniform costs. Within this model, we developed new family of algorithm based on inexact composite gradient method with recursive gradient estimator. This design enables us to exploit functional similarity among clients while supporting partial client participation-2 a key requirement in practical FL. systems. It is efficient when full synchronizations (requiring sequential communications with clients) are costly compared to client sampling. The key technical contribution of this work is a variance bound for the SAGA estimator, which depends on the functional similarity constant rather than individual smoothness. This allows the SAGA-based variant of I-CGM-RG outperform the previously best- known communication complexity SARAH bassed methods. Limitations and future extensions are discussed at the end of the Appendix.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Durmus Alp Emre Acar, Yue Zhao, Ramon Matas Navarro, Matthew Mattina, Paul N Whatmough, and Venkatesh Saligrama. Federated Learning Based on Dynamic Regularization. arXiv preprint urXiv:2111.04263. 2021.
Zeyuan Allen-Zhu. Katyusha Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization. arXiv preprint /802iv:/002.03300 03866, 8a.
Zeyuan Allen-Zhu. Katyusha x: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization. arXiv preprint arXiv:8802.0 03866, 2018b.
Yossi Arjevani and Ohad Shamir. Communication Complexity of Distributed Convex Learning and Optimization. Advances in neural information processing systems, 28, 2015.
Yossi Arjevani, Amit Daniely, Stefanie Jegelka. and Hongzhou Lin. On the complexity of minimizing convex finite sums without using the indices of the individual functions. arXiv preprint arXiv:2002.032733 2020.
Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, and David P Woodruff. Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality. In Proceedings of the firth- annual ACM symposium on Theory of Computing, pp. 1011-1020, 2016.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: Library for Support Vector Machines. ACM Trans-
actions on Intelligent Systems and Technology, 2:27:1-27:27, 2011. Software available at http://
EI Mahdi Chayti and Sai Pranceth Karimireddy, Optimization with Access to Auxiliary Information. arXiv preprint arXiv:2206. 00395, 2022.
Mahdi Chayti, Nikita Doikov, and Martin Jaggi. Improving Stochastic Cubic Newton with Momentum. In Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learning Research, 1441-1449, PMLR, 03-05 May 2025. URLhttps https
//proseedings.ml wttp./g..........e/ee.eeee...e.. htwp2/5555/ccay1y2.hhhh..
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. EMNIST: Extending MNIST to Handwritten Letters. In 2017 international joint conference neural networks (IJCNN), pp. 2921-2926. IEEE, 2017.
Ashok Cutkosky and Francesco Orabona. Momentum- Bassd Variance Reduction in Non-Convex SGD, Advances in neural information processing systems, 32, 2019.
Peter Davies, Vijaykrishna Gurunathan, Niusha Moshrefi, Salch Ashkboos, and Dan Alistarh. New Bounds for Distributed Mcan Estimation and Variance Reduction. arXiv preprint arXiv:2002 2020.
Aaron Defazio, Francis Bach, Simon Lacoste-Julien, SAGA: Fast Incremental Gradient Method with Support for Non-Strongly Convex Composite Objectives. Advances in neural information processing systems, 27, 2014.
Yuan Gao, Anton Rodomanov, and Sebastian Stich. Non-Convex Stochastic Composite Optimization with Polyak Momentum. In Proceedings of the 41st International Conference on Machine Learning, 1CML'24. JMLR.org. 2024.
Yuan Gao, Yuki Takezawa, and Sebastian Stich. A Bias Correction Mechanism for Distributed Asynchronous Optimization. Transactions on Machine Learning Research, 2025. ISSN 2835-8856. URL httpp
//ppenreview.nett for.:/ormmmmmm Sddomaaddddd
Ankit Garg, Tengyu Ma, and Huy L Nguyen. On Communication Cost of Distributed Statistical Estimation and Dimensionality, Advances in Neural Information Processing Systems, 27, 2014.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016. doi: 10.1 1009/.....200..99.
Hadrien Hendrikx, Lin Xiao, Sehastien Bubeck, Francis Bach, and Laurent Massoulie. Statistically Precondi- tioned Accelerated Gradient Method for Distributed Optimization. In International conference on machine learning, pp. 2207-4227, PMLR, 2020.
Xiaowen Jiang, Anton Rodomanov, and Sebastian U Stich. Federated Optimization with Doubly Regularized Drift Correction. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine leaming Research, pp. 21912-21945. PMLR, 21-27 Jul 2024a. URL. https:: hetps://prrceeddingg ngs.m http:/ss.w..rr.s//2233 faaps//22233//a222.2eeemm
11

---

Published as a conference paper at ICLR 2026
Xiaowen Jiang, Anton Rodomanov, and Sebastian U Stich. Stabilized Proximal-Point Methods for Federated Optimization. In The eightt Anmual Conference Neural Information Processing Systems, 2024b.
Rie Johnson and Tong Zhang. Accelerating Stochastic Gradient Descent using Predictive Variance Re- duction. In Advances in Neural Information Processing Systems, volume 26. Curran Associates. Inc., 2013. URL https::/proceed wgw. www.nuurr...e............ wwwp:eerrrrrppppppppp..pp /tsppr/eeisee//pper//211333
ac cslocUUscccssuuaaeg29996ee333-33
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles. Graham Cormode, Rachel Cummings, Rafael G. L. D D'Oliveira, Salim EI Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie Hc, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi. Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sammi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi. Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Schastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramer, Praneeth Vepakomma, Jianyu Wang, Xiong, Zheng Xu, Qiang Yang, Felix Yu, Han Yu, and Sen Zhao. Advances and Open Problems in Federated Learning. Foundations and Trends@ in Machine Learning, 14(1-2):1 2021. URL https://arxiv.orr
Sai Praneeth Karimireddy, Satyen Kale, Mchryar Mohri, Sashank Reddi, Scbastian U. Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic Controlled Averaging for Federated Learning. Interna- tional conference on machine learning, pp. 5132-5143, PMLR, 2020.
Sai Pranceth Karimireddy, Martin Jaggi. Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. Breaking the Centralized Barrier for Cross-Device Federated Learning. In Advances in Neural Information Processing Systems, 2021.
Ahmed Khaled and Chi Jin. Faster Federated Optimization under Second-Ordes Similarity. In The Eleventh International Conference on Learning Representations, 2023. URL [ttpp:://opnrsrvsswness
forum? 11
Jakub Konečný, H Brendan MeMahan, Felix X Yu, Peter Richtárík, Ananda Theertha Suresh, and Dave Bacon. Federated Learning: Strategies for Improving Communication Efficiency. arXiv preprint 17X00:16.. 2016.
Janne H Korhonen and Dan Alistarh. Towards Tight Communication Lower Bounds for Distributed Optimisation. Advances in Neural Information Processing Systems, 34:7254 776667766,, 2021.
Dmitry Kovalev, Samuel Horváth, and Peter Richtárik. Don't 't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop. Proceedings of the 31st International Conference on Algorithmic Learning Theory, volume 117 of Proceedings of Machine Learning Research, pp. 451-467 1174 PMLR, 2020.
Dmitry Kovalev, Aleksandr Beznosikov, Ekaterina Borodich, Alexander Gasnikov, and Gesualdo Scutari. Optimal Gradient Sliding and its Application Optimal Distributed Optimization under Similarity. Advances in Neural Information Processing Systems, 35:33494-33555 2022.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. CIFAR-IO (Canadian Institute for Advanced Research). URL
ficcffat far.html
Jason D. Lee, Qihang Lin, Tengyu Ma, and Tianbao Yang. Distributed Stochastic Variance Reduced Gradient Methods by Sampling Extra Data with Replacement. Journal of Machine Learning Research, 18( 11222):1-43, 2017.
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization. In International conference on machine learning, pp. 6286-6295. PMLR, 2021a.
Zhize Li, Slavomár Hanzely, and Peter Richtárik. ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation. arXiv preprint 1rXiv:2103.01444 2021b.
Dachao Lin. Yuze Han, Haishan Ye, and Zhihua Zhang. Stochastic Distributed Optimization under Average Recond-Order Similarity: Algorithms and Analysis. Advonces in Neural Information Processing Systems, 36, 2024.
12

---

Published as a conference paper at ICLR 2026
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication- Efficient Learning of Deep Networks from Decentralized Data. Artificial intelligence and statisties, pp. 1273-1282, PMLR, 2017.
Konstantin Mishchenko. Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally! International Conference on Machine Learning, pp. 35750-15769. PMLR, 2022.
Konstantin Mishchenko, Rui Li, Hongxiang Fan, and Stylianos Venieris, Federated Learning Under Second- Order Data Heterogeneity, 2024.
A. S. Nemirovsky. Information Based Complexity of Convex Programming. 1994,
A. S. Nemirovsky and B. Yudin. Problem Complexity and Method Efficiency Optimization. 1983.
Yurii Nesterov. Lectures on Conver Optimization. Springer Publishing Company, Incorporated, 2nd edition, 2018. ISBN 3319915770.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. SARAH: A Novel Method for Machine Learning Problems using Stochastic Recursive Gradient. In International conference on machine learning. pp. 2613-2621. PMLR, 2017.
Kumar Kshitij Patel, Lingxiao Wang. Blake Woodworth, Brian Bullins, and Nati Srebro. Towards Optimal Communication Complexity in Distributed Non- Convex Optimization. In Advances in Neural Information Processing Systems, volume 35, 2022. URL ottp://www..aaaaaaoooooaooo-ooar
paper_ siles/
Nhan H Pham. Lam M Nguyen, Dzung T Phan, and Quoe Tran-Dinh. ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization. Journal of Machine Learning Research, 21 (110):1 48, 2020.
Sashank J Reddi, Suvrit Sra, Barnabás Póczos, and Alex Smola. Fast Incremental Method for Nonconvex Optimization. arXiv preprint 663 2016.
Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal Convergence Rates for Convex Distributed Optimization in Networks. Journal of Machine Learning Research, 20(159)) 1-31, 2019. URL http: http://mmm..or.aapaaa..apepa httpp/err///////////// v20019- 5-3.4354mmm
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing Finite Sums with the Stochastic Average Gradient, Mathematical Programming, 162:83-112, 2017.
Ohad Shamir, Nati Srebro, and Tong Zhang- Communication Efficient Distributed Optimization using an Approximate Newton-Type Method. In International conference on machine learning, pp. 1000-1008. PMLR, 2014.
Yuki Takezawa, Xiaowen Jiang, Anton Rodomanov, and Sebastian U Stich. Exploiting Similarity for Computa- tion and Communication Efficient Decentralized Optimization. arXiv preprint arXiv:2506.0579), 2025.
Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. SpiderBoost and Momentum: Faster Variance Reduction Algorithms. Advances in Neural Information Processing Systems, 32, 2019.
Blake Woodworth. The Minimax Complexity of Distributed Optimization. arXiv preprint arXiv:2109.00534, 2021.
Blake E Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, and Nati Srebro. Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization. Advances in neural information processing systems, 31, 2018.
Yida Yin, Zhiqiu Xu, Zhiyuan Li, Trevor Darrell, and Zhuang Liu. A Coefficient Makes SVRG Effec- tive. In The Thirteenth International Conference on Learning Representations, 2025. URL httpa
//ppenreview.ne//eee how.e://oooomm.m.etttttttl
Yuchen Zhang, John Duchi, Michael I Jordan, and Martin J Wainwright. Information- Theoretic Lower Bounds for Distributed Statistical Estimation with Communication Constraints. In Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
13

---

Published as a conference paper at ICLR 2026
Appendix
CONTENTS
Ethics statement
15
B LLM usage
15
Federated Optimization Algorithms and their Complexity
16
D Related Work
17
D.I Formalization Federated Optimization Algorthms Their Complexity
17
D.2 Comparison with Existing Federated Optimization Methods
18
Technical Preliminaries
21
Proofs for I-CGM
23
Prool for Theorem
23
F:2
Prools of Local CGM for Solving the Subproblems
24
F2.1
Proof of Lemma
................................
25
F2.2
Prool of Lemma
................................
25
Prools of Properties
SAGA and SVRG Estimators
26
Proof of Lemma
26
33.
Proof of Lemma 4.3
27
R4
Properties of the RG Estimator
28
F4.1
Proof of Lemma 5.2
28
F.4.
Proof of Corollary 5.3
................................
29
F.4.3
Proof of Corollary
29
Prools forl CGM with SAGA
30
F55
Proof of Theorem
30
:66
Prools for -CG with RG SVRG
31
-CGM-RG-SAGA with Inxacc Initialization
32
Solving the Subprohlems with Local Stochastic CGM
37
Discussion on the SAG estimator
38
Additional details and experiments
39
J.1
Quadratic minimization with log-sum penalty.
39
U.I.I Ablation studies of I-CGMRRG-SAG
39
22 Logistic regression with nonconvex regularizer,
40
FMNIST Residual CNN
CIFARIO with ResNet18
42
14

---

Published as a conference paper at ICLR 2026
A ETHICS STATEMENT
This paper presents work that aims advance the field of Distributed Machine Learning. There many potential societal consequences our work, none which feel must be specifically highlighted here.
B
LLM USAGE
We used LLM only for polishing the text.
15

---

Published as a conference paper at ICLR 2026
C FEDERATED OPTIMIZATION ALGRITHTS AND THEIR COMPLEXITY
Federated Optimization Algorithm. We consider the standard federated optimization setting with a central server and clients. The server is the main entity that implements the optimization algorithm, but cannot directly access any of the local functions (ft))=.. Instead, interacts with problem ① through communications with the clients, allowing certain information to be exchanged between them. Each client E [r] has access to the information provided by the server and can interact with its own local function fi. but only through the oracle
O An oracle standard notion in optimization (Nemirvssky 1994 Nemirovsky & Yudin, 1983), which is procedure that takes as input a point and returns certain information about the function at this point. The most commonly used oracle is the first-order oracle, which returns the function value and its gradient. In general, an oracle can be stochastic; however, in this work, we mainly consider the standard deterministic first-order oracle Oro, (x) := (f((x), V (x)).. Throughout the paper. we assume that the server can communicate with up to m E [nx] clients simultaneously in parallel. We formalize optimization algorithms in this setting as follows.
Given the oracles Of,,..., Sn a federated optimization algoritlun for problem class F is procedure that proceeds across communication rounds. A problem class is the collection of all problems of form ( satisfying certain assumptions. (We will introduce a specific problem class considered in this work in Section 2.2] At the beginning, the server and each client E [ro] initialize the empty information sets I and H. respectively. At each round r 2 0, the server chooses subset of clients S, S [r]] with most m elements (to be discussed later). The server then communicates with the clients in Sr. providing each client i E S, with certain information Σ; constructed from the server's ' information set Z". Then it specifies a certain method M; (often called a local method) for each client E S, to run locally. The method M starts with the initial information (I," H,),, and iteratively queries the oracle fg obtaining a response RT. which is then sent back to the server. (The details of this procedure are discussed in the next paragraph.) The server collects the output responses and updates the information set I=+1 = (I', (R. sts..) ). At each round 2 O, the server also performs a termination test. based on the current information set Z". After the algorithm terminates at certain round R 2 0, the server then constructs and outputs an approximate solution x* to problem ① based on I using certain rule specified by the algorithm. To summarize, a federated optimization algorithm is collection of rules prescribing what do each communication round r: 1) how to select clients, 2) how to compute the information Σद that is sent to each selected client, 3) which local method each selected client runs, 4) when to terminate, and S) how to form the approximate solution. We allow cach of these rules to be randomized. See Figure D.I for an illustration summarizing the procedures described above.
At the beginning of each round r, each selected client E S, receives the information Σद from the server. Using this new information, it enriches its information set Hi, == (H2 7,') and runs the specified method M At each step A 2 O. this method first computes a point x based on H. queries the oracle at this point, and then updates its local information: He = (H,,k, Oy, (X",,)) At the beginning of each step k, the method also performs termination test T,,,, (PC,,) ): Once this test is satistied a certain step KJ. the method terminates and constructs the output R2 from the final information H[,xy. The information sets are then updated as H,5 := Hi,,,, and remain the same (HG+1 : HD) for cach non-selected client $ S,, To summarize, a local method Mf a collection of 3 rules: 1) how compute the next point each step, when terminate, and 3) how to form the result. We allow each of these rules to randomized (resulting in a randomized local method); if all the rules are deterministic, the local method is called deterministic.
Note that the above definition of distributed optimization algorithm is rather general and only constrains how the algorithm accesses information about the optimization problem. In particular, do not impose any restrictions on the arithmetic or memory complexity of cach step of the algorithm, nor on the size of the data transmitted between the server and the clients. This general definition is sufficient to introduce the two information-bost notions of complexity that we focus on in this work: communication and local complexities (defined below). In practice, however, both memory storage and information usage should be implemented efficiently. Typically, the accumulated information sets maintained by the clients and the server, as well as the information exchanged between them, are simply a collection of few vectors and scalars.
Client-Selection Strategies. We next introduce three commonly used selentt-e strategics and associate them with different costs. The distinction among them lies in how the set S, is selected.
Arbitrary Client Selection Strategy (A-CSS), The set S, can be chosen in any way from (In) We define the cost of this operation Ca.
Random Client Selection Strategy (R-CSS): The set S, is sampled uniformly at random from (Im)). We
define the cost of this operation as Cg-
Delegated Client Selection Strutegy (D-CSS): The set S, is chosen to be Sp. where Sp is a fixed set of so-called delegate clients (to be discussed later) with |Sp] S m. We define the cost of this operation as 1.
Clearly, A-CSS is the most powerful among the three strategies, the other two could be easily implemented in terms of A-CSS. Further, this strategy allows the server to collect information from any subset of clients. This
16

---

Published as a conference paper at ICLR 2026
lexibility enables the implementation full synchronization, where the algorithm needs certain information be collected from all clients. This feature appears in many algorithms, the most basic example being the usual gradient deseent (GD), Specifically, if an algorithm requires computing the full gradient fx) at a point x, the server can split [n] into m disjoint sets and repeatedly use A- A-CSS to make [ sequential communications with each set of clients, sending to each client the point x and asking it to compute and return the gradient (x( (this corresponds to the simplest one-step local first-order method M;).
However, when clients are unreliable or slow respond, using A-CSS can become costly. cross cross-devics device settings, it is often more efficient to communicate only with a randomly sampled subset of clients at each communication round- which is modeled by the R-CSS. Therefore, treat R-CSS as a cheaper strategy compared with A- A-CSS. Unlike A-CSS, the full-gradient computation cannot be directly implemented with R-CSS. (But it be recovered with high probability by using R-CSS multiple times (Arjevani et al.) 2020).)
strategy commonly known as partial client participation (McMahan et al. 2017),
In addition to the previous two strategies, there are scenarios where there exist so-called delegate clients that are always reliable and efficient both in communication and performing local computations. Sometimes. it is sufficient-or even preferablc-ta interact with these clients. With D-CSS, the server can always query information about the specific functions in the delegate set. In this work, focus the setting where there one delegate client (number 1), i.c., So {1}-
Based on the properties of each strategy discussed above, we assume that the above costs satisfy the following natural relations:
S Ca S CA
Communication-ann Local Complexities. Consider a fedcrated optimization algorithm A for solving a problem f from the problem class F. Let R be the (possibly random) number of communication rounds made by on f' and let x" be the corresponding output of A. We define the accuracy of the algorithm A at the problem f' as:
Accur(A, f) Ell (**))
Further, let NA Nu, and Np be the (possibly random) total number of times that the client-selection strategies A-CSS, R-CSS, and D-CSS are used by A during the communication rounds, respectively. We define communication complexity of A on f as:
N₂ ECCANA CnNR No
and the local complexity A on f as:
R Σ K
Ky = B
where K,, == max.es, KJ and KT 2 0 is the number of queries to the oracle O, by the client at round r. We next define the worst-case complexities of A over the entire problem class F. The communication complexity of A for solving the problem class F up to accuracy is defined
N*(x) = sup Ny) Accur(A, S
fef
and the corresponding local complexity is defined as:
K K> sup Accur(A))) {
JeF
there exists some f E F such that A fails to reach Accur(A, f) S e², then both complexities () and KF(E) are defined as +00.
consider only federated optimization algorithms that can achieve Accur(AA, (A,, J) x s² for all / F. Among these algorithms, we say that the with smaller communication complexity Nz(E) is more efficient. two algorithms have the same communication complexity, the one with lower local complexity Kx(E) is preferable.
After fixing the desired accuracy
D RELATED WORK
D.I FORMALIZATION OF FEDERATED OPTIMIZATION ALGORITIMSS AND THEIR COMPLEXITY
Several prior works have proposed oracle models and complexity metrics for distributed and federated opti- mization. These works typically consider solving the same problem as in (T). where each of the clients
17

---

Published as a conference paper at ICLR 2026
Client
Client 1
Informattion
[
H = ?6
send
run
send
Server Infortatioon: I
client selection
Client E S.
run_Mr
Client E S. H
send
Server
send Z
Information: RC
Ki,
send...
(27 (Riisss
run
oo
...
Client
Client no
Information: N.
7 M%
Local method (M 77)
Tix: (Hi stop
output
Og( K (Hig. (2()))
Ogfa5)
74hp (74) 271
Mix (M Ouls
R
Figure D.I:
Illustration of the sequence of procodures performed by a centralized distributed optimization algorithm at each communication round r.
workers only has access to its own local function. The primary distinctions among these models lie in how communication and computation formalized. One line of work focuses on the settings where each worker can compute arbitrary information about its local objective. but only a limited number of bits is allowed to transmitted during each communication round (Braverman et al.] [016]] [Garg et al.] [014] 77hang et al.] (203)). In this setting, complexity is often defined as the numher of rounds required to reach target accuracy. Alternative models remove this constraint and instead measure the total number of bits communicated over the entire opti- mization process (Korhonen & Alistarh 202T). Other works impose structural restrictions the communicated information, such as requiring exchanged vectors to in a certain subspace (e.g., linear combinations of local gradients) (Arjevani & Shamir 2015 Lee et al. (017).
The closest related model to ours is the Graph Oracle Model (GOM) (Woodworth et al. 2018 Patel et al. 2022 Woodworth T) GOM introduces computation and communication graph that determines how each device queris local oracle and how the computed information propagates through the devices during optimization. Once the oracle and the graph structure are fixed, we obtain specific model that allows to define the corresponding optimization algorithms. A commonly studied setting is the intermittent communication model, where devices work in parallel and synchronize after every K local oracle queries. This setting becomes conceptually equivalent to model when 1) all clients participate in every round, 2) the number of local oracle queries K, is uniformly bounded across communication rounds, and 3) the server and clients are allowed to send its entire accumulated information.
Beyond this scenario, there are several main differences between GOM and our proposed model. 1) GOM does not distinguish between different client- selettselection strategies that might have non non-uniform associated costs. 2) Even when all the strategies have the same cost, GOM fixes the maximum number of local oracle queries for each round, whereas our model allows Kr to vary across rounds. This flexibility enables modeling algorithms such as DANE (Shamir et al. 2014 Diang et al. (2224), which needs to solve each local subproblem sufficiently accurately, making K, dependent on the round 3) While partial client participation can be modeled in GOM by generating random graph, the resulting algorithms clients at each round. This effectively enforces offline client-selection strategy for GOM, since may not account for the need to know the past responses of specific clients before deciding which clients contact next. In contrast, our model fully supports online and adaptive client-selection strategies.
generally restricted to using pre-specified groups of
We believe that our model is reasonably simple and it appears to sufficiently capture how federated optimization algorithms work in practice. Even in the cases where our model is mathematically equivalent to existing oncs, model could still be more convenient be used.
D.2 COMPARISON WITH EXISTING FEDERATED OPTIMIZATION METHODS
Notations in Table 1 We denote FO = f(x²)= f", nm 82
2 and S Cn & CA respectively.
the costs of communicating with a random of clients and specific set of en
this section, we compare our proposed methods with several popular federated optimization algorithms in terms of their communication and local complexities (Section For simplicity and to ensure fair comparisons across algorithms. we assume that all methods use the deterministic first-order oracle locally, i.e O2, = Opo.- for all i E n)). We first state and discuss the assumptions under which each algorithm was analyzed in the literature. The abhreviations used in Tare defined as follows.
18

---

Published as a conference paper at ICLR 2026
Assumption D.1 (FS (Function Smoothness)). There exists L, such that for any x. y E IR we have:
[V Vf(y)) S L ||x yll.
Assumption D.2 (IS (Individual Smoothness)). There exists Lmax such that for any x, E R and any
i e [ra]. we have: [V) Vfi(y)) S Imax||> yl|.
2024a Gao et al. 2025 ). There exists Amax such that for any x, 12t and any n// we have: Vh. (yl
Assumption D.3 (SD (Second-orde order Dissimilarity) (Karimireddy et al. 2020 Jiang al.
A max X y/l.
Assumption D.4 (BGD (Bounded Gradient Dissimilarity)). There exists Ç >> 0 such that for any E R we
have: E [x) - Vf( | <²
Note that the problem class of IS belong to SD, and SD implics Assumption 2.1 and 2.2 Moreover, any functions
that satisfy Assumption 2.1 and 2.3 and problem class defined by Assumptions [.1 and 2.2 In Table[] the assumption under which Centralized GD analyzed is most general one, and those for I-CGM-RG are the second most general. Finally, the smoothness constants satisfy the following relations:
belong the class of FS. Finally, the class of FS partially overlaps with the
8, max Lmax, L5, Lmax
We next briefly describe each method in Table lnd computed for each method. There are two operations that are commonly used in these methods. We describe them here to avoid repetition later. Denote Tim := n/m.. The first operation is compute the full gradient V the
and discuss how communication local complexities are
certain point As discussed in Section C this can be implemented with [nm successive communication rounds, cach involving the use of A-CSS and one local gradient computation. Each such operation adds therefore Nv == Ca(rm to the total communication complexity and Kv, = [n.,] to the total local complexity of an algorithm.
Another commonly used operation is to compute several mini-batch gradients V.s at b 2 1 points where E (*)) is sampled uniformly at random. This requires one communication round using R-CSS. The communication complexity of this operation is f == CR and the local complexity is Kvfs. :=
In what follows, we omit the subscript F in the notation for the complexities N=(E) and K>(s); the correspond- ing problem class specified in Table|Tfor each method.
Centralized GD. The method iterates:
1 Lg
V(((')
The iteration complexity of is 01 50 N(s) / OCC F and the local complexity is K(s) TKv, O( L, PD
Nesterov 2018 implying that the communication complexity
FEDRED
Jiang et al. 2024a). We consider FEDRED-GD, which initializes šn x. and iterates:
X1+1 arg min [i(x)) (x)((x)) + (x.)) Vi x) XER
| x
|x xe xx11
where Re+1 Xe+1 w.p. P and Re+1 w.p. 1 p. The solution of the subproblem can be computed in a closed-form. For ~ 3 I.+A. 71 = L, and À ~ A the iteration complexity of the method is T =
O (i Jiang al. 2024a). expectation, once every 1/p iterations, the server computes full gradient (x(x)) Vf(x.), which adds Nv, to the total communication complexity and Kv, the total local complexity. Then the server makes another communication round with D-CSS, sends f((xx) client 1 which then performs 1/p local steps in expectation and sends result back to server. The expected number of
times the full gradient V (Xa) is computed is pT' = O (( The expected number of communication rounds where D-CSS is used is E[ND] = pf'. Therefore, the communication complexity is
A
(e) = E + Np] = O(yTT + pT) = (CAvmm
2²
The local complexity is bounded by
+ +T) = 0 7m
A
I
(()) = +T)
g²
FEDAVG (McMahan et al. 2017). At each communication round r 2 0, the server uses R-CSS to select clients, sends x" to each client S., which then returns an approximation solution x"+ arg mig, fx(x by
19

---

Published as a conference paper at ICLR 2026
running local GD starting x' for K2 steps. Then the next iterate is defined x" =+1
Lics, x When
using local-GD, the optimal number of local steps is of order (Karimireddy et al. 2020 Therefore, the local
complexity is of the same order as the iteration complexity T == O Sm. +
VTeaax + Arma
Karimireddy
et al. 2020), and the communication complexity is CR2'.
MIMEMVR (Karimireddy al. 2021) At each iteration 1 > 0. the server first uses R-CSS to get random
client set S. and computes the mimi-hatch gradient ffs, (xx). Then the server uses A-CSS to establish communication with the same set of clients St, sends V fs, (x') to them which then updates:
Rs arg min [f(() + V fs (x') Vf((x').))
X;
XER
by running momentum-based first-order methods locally for O Liax steps. The next iterate is defined as:
x x*+1_ +/2 Eies, x
1+1
The communication complexity is thus ((5) B = (CA + Cr)T,
where T= 0 S.
fm Amararf Pd)
Amay F0
is the iteration complexity (Karimireddy ct al. 2021). J. The local
complexity is O
Lmax T).
Amax
CE-LGD (Patel et al. 2022). The method piitiaaizeesx--1
and v E Rd. At each iteration f 2 0, the
server first uses R-CSS to select clients St, sends x"=1 and x" to the client i St which then computes V fxxx)))
and V (((('=)) and sends them back to the server. The server computes v Vss, (x') (1 p)(
V.s. (x" ()) where p E [0. 1]. Then the server uses R-CSS again to communicate with a random client. The
client returns x by running the local SARAH method using v' for O Limxx) local steps. The iteration
complexity is T O
Si Ammnggg sd Amyy ("))
(Patel et al. 2022). The communication complexity is
(e)) = OCC)T) and the local complexity ((e)
O
Lemay T). Amax
SCAFFOLD Karimireddy et al. 2020). the beginning, each client L...., n computes by (x(") and sends the result to the server; the server then computes b" = (x")). which adds N and Kv to the total communication and local complexities. respectively. At each iteration / 2 O, the server uses R-CSS to generate the client set St and sends x' to each client i E S,, which then computes by ff((x') and sends
bj - bb-1 back to the server. The server then updates by (SAG (Schmidt et al. 2017 ) according to (IO) (for t 12 1). Then the server uses A-CSS to contact the clients in St again and sends b to them. Each client i E St computes
Xi
se arg min (f(() + (b' vf((x'),)) XERd
by running local GD for
steps and sends the result back to the server. The server computes the
next iterate as x [+1
m Eves, x 1+1 The iteration complexity is T ((( 5 LmayF") (Karimiredly 2.20 The communication complexity N(e) OCCa [n.]] + (CA + CR)T). The local complexity Tmmm
al.
[
KJT O(nm + +T).
The final three algorithms do not strictly satisfy our dcfinition of an algorithm because they do not clearly specify when to terminate the local method. However, we still present the conceptual methods and their communication complexity estimates, assuming (rather informally) that certain "local" operations can be implemented by running certain local method for sufficiently long time.
FEDDYN (Acar from all clients. Therefore, the communication complexity of this operation CA [mm]. At each communication round r 2 0, the server uses R-CSS to select clients S, and sends x" to each client E S, which then sends
2021 During initialization, the server needs to collect x that satisfics ( =
arg min f((x) - (V
||x - x1,,,, i Sr,
back to the server, For i E Sr, x +1 x..
Then the next iterate is updated as:
h+
h1
Σ
m E.
SES
The iteration complexity is T Om Lringg pa (s)) = OCCami + Cn
Acar et al. 2021 and the communication complexity is
SABER-FULL Mishchenno et al. 2024p. The method initializes x-1 = x" and v = v = (x()). At each iteration 2 O. w.p.
the server updates v² = vf(x") which adds Ney and K to the total communication and local complexity, respectively. With probability 1 -- the server uses R-CSS, obtains the random set St, and computes two mini-hatch gradients fss, (x') and V fs, (x--1). This operation adds N2 NGts, and K2 K2 the communication and local complexity, respectively. Then the server updates
20

---

if each subproblem is Published as a conference paper at ICLR 2026
==v's v- Vx,, Viss, (x* (The original method samples single index mt. Here extend it to
S..) After the computation of v', the server uses R-CSS, samples random index m, E [n], and sends v² and
x" to the client Meg which then returns
R3 arg min fin (x) + (v' - ( + A ||x x xERu
x1²}}
back to the server. The iteration complexity of the method is 'T' = O y Ammmme p0 solved exactly. The total communication complexity is
((e) = BICANA+ = =O(CaRm
1
CaTnn + (1- 7.m
1 (CRT+CKT) = OCCAmm + +CTT).
Pm
SABER-PARTIAL [Mishchenko et al., 2024). We refer to Algorithm 2 in the original paper as SABER- PARTIAL. By Theorem 3 in that paper. the best is 1. The algorithm initializes v = V which adds N and / to the total communication and local complexities, respectively. At each iteration / 1. the method also needs to compute mini-batch gradient v² = Eies Vf((x') where Sy sampled uniformly
at random with replacement and |S|| = 8 where s is a parameter of the method. Since we assume that the server can communicate with at most m clients at each round, implementing this operation requires [s/m] sequential communication rounds with R-CSS. After that, the method needs to choose another random set Se with |Sa| = 8. This adds C& ss/m] to the total communication complexity. The server sends x' and v' to the client S,, which then computes
A ||x -x(1x x'1²]
arg min + (v' Vx((x')) -V + xCR
and sends the result back to the server. The next iterate is updated as x = Eies, x S E n and s
chosen as O {2) ), then the method can output e-approximate stationary point after T O Amax po
iterations
if each subproblem solved exactly. The communication complexity is N(e) BlCRNN + CANA)
T + CANm)-
Discussions. FEDDYN, SABER-FULL and SABER-PARTIAL do not strictly satisfy our definition of an algorithm since they do not precisely specify when to terminate the local methods. The problem class for which FEDAVG, MIMEMVR, CE-LGD. and SABER-PARTIAL PARTIAL analyzed is the smallest among all methods. Specifically, in addition to they also assume BGD, which can be restrictive and exclude simple quadratics. Among these four, MIMEMVR and CE-LGD improve upon FEDAVG and SA BERR-AARTIAL in terms of their dependence on the target accuracy s. Except for FEDAVG, the remaining three methods replace the dependence on Timax with Aaa in the communication complexity. Furthermore, compared to MIMEMVR, CE-L.GD achieves better dependence on in the term involving 3
For the remaining methods, SCAFFOLD improves the dependence n from Tim (as in FEDDYN) 2/3 SAVER-FULL further reduces the dependence n to Tim and simultaneously improves the smoothness dependence from Lmax to Amax. CCGM--RG-SVPE achieves a tighter bound of CR + Crmmn & Cayan Amax. Finally, I-CGM-RGE RG-SAGA improves the communication cost constant from CA to CR. compared to CCGM-RG-SVRRE while maintaining the same local complexity the best among all existing methods.
Remark D.S. According to Arjevani et al. (2020) one may alternatively compute the full gradient using only R-CSS. Let m = for simplicity. Lemma in (Arjevani et al. 2020) shows that w.p. 1- - 5. we can recover the full gradient (x) at given point x by making 2n log( 2 communication rounds with R-CSS. This can be helpful when the cost CA is extremely large. Indeed, the current communication complexity of 1- 1-CGM- RG-SAGA is of order Can CR((AI
CA 2 Ca((A, 1 vTt) 1 / /e²)/n. the complexity dominated by CAn. This term arises from 2n sequential communication rounds with A-CSS for computing the full gradients. Now if we replace these operations with 4n log( 2m) sequential rounds with R- B-CS the total complexity might be reduced to C2 (n² log(n) + (Ar + //n)) F /e2). We leave a full theoretical development of this direction as interesting future work.
/ 0 /e²). As
E TECHNICAL PRELIMINARIES
We frequently use the following lemmas for the proofs.
Lemma F.1. For any x, y E Rdd and any & > 0, we have:
k>y' - ? ||x|| 27 11y11?
(E.I)
Ixx + yl1 < + 7) || + (1 (1+2)) 2) 11yl2
(E.2)
21

---

Published as a conference paper at ICLR 2026
Lemma E.2 (Jiang al. 2024b). Lemma 13). Let {B:) be vectors in I2 with 2. Let m [n]
and let S E (m) be sampled uniformly at random without replacement. Let
1 E 22 18 o²
+E i=1 gg gll and g:
Ljes Ey. Then,
o² m
Es gs
and
Esilgg -11
(E.3)
Lemma E.3 ((Allen-Zhu 201 Saj, Fact 2.3). Let Ao, AI,.. be reals and let K ~ Geom(p) with p E (0, 1). that is PP(K = k) (1 p) p. for each E {0, 1, 2, ..... Then it holds that: B[K] = and
E[Ax] = (1 p) E[Ax+1] + pAo
(E.4)
Proof. Using the identity Σx kg"
9 for any |4| we have: (I-9)²
[ = Σ
k(1 p)*
p 1
p p2 p
k20
To prove the second part, using the definition of K.
E E'Ak+1] Σ
Akt1(1 p)*
P
Au(1 p)*
1
(B[AK] -PAo).
1-P
1
k:20
Rearranging gives the claim.
Lemma E.4. Let (A.) (B:) and be two non-negative sequences such that
A4t1 $ (1 - A, + B,
for any i 2 0 with a E (0, 1). Then for any t 2 1,
A S (1 a)'An
(1 -i''iB-11
1=1
and for any
Σ A. < (1 - a1 (1
T
Ao
+
(1
T-1 B
1-a
Ao
Σ B
Proof. When a = 1, the claim clearly holds. Let 0 < a < 1. Dividing both sides of the main recurrence by a we have for any 2 0:
A1+1
A
B,
S (1 (1-a)
+
(1 a)+t1
(1 a)it1
Summing up from i i we get, for any 2
(1 o) S Ao
A:
1 aj+t = Ao + Σ
B,
B
a}
This proves the first claim. To prove the second part, we up the first claim from / = 1 1 =
Σ A. $ Σ
A)'An
Ao
'Bi
1=1
1=1
(1 (1-a)(1= - (1-a)²) ))
Aa
(1 a)
Bi
a
(1 (1-a)(1= - (1 (1-))²)
(1
T-4+1
Ag
B
a
(1 a)(1 (1 a) A
a)
T-
B.
1=
Lemma E.5. Let E (0, The minimizer of the problem min,
X is attained at
Proof.
Differentiate f(x), we have f'(2) 2 Setting f(()) = 0 with 7 E (0, 1) gives 7"
(11-))
Since f(7) 0o as 7 0+ ory + 11, the critical point >" is the minimizer over (0, 1).
22

---

Published as a conference paper at ICLR 2026
F PROOFS FOR 1-CGM
Lemma F.I. Let LeAl-CGM be applied to Problem ① under Assumption 2.1
Let A Dr. Then for any 2 0.
[[V s (A + A1)8041 5.t tee
where &i ||x' -x''-'111
x/ For any RR have:
Σ
Fe(x)) - F.(x) = - s(x) + 2(A - -1)
Suppose the iterates satisfy S then the fanction value decreases as:
f(x () > x - A
5
Xi+1 + 2 A
4
Proof. By the definition of Fi, we have:
VF((x = Vx1(x())) 1 + g" V(((x')) + +1xx - xx))
= Vf + (g' VV((x)) + (VhI(x') - V)x(xxt))) + (xxxt1-x))
follows that:
| S Au++ + (x - Vha(( || + Σ, + a
(A + A1)++ + E. cs.
which proves the first inequality. Using the definition of Fe, for any x E R", we have: Fx(x') - (xx)
= =fi(x'+ + h1 (x') - (x) - (x)) - (g' VXx())xx xx) 11x x²11
= =f(x²)- - f(x) + f(x)= fi(x) - hi(x') - (g' - -Vf(('),, xx) - - x 1|
= =f(x') (xx) + (x) - (x') - (Vhi (x')xx x マタ ||x xx11 - (g - VV(x'),x
f(x')-
2 ||x x'1 11 (g' vf((' ) x x-x)
Using E..Ip. we can bound the last two terms by: le -
which proves the second claim. Substituting
2(A-A.)
x x and using 5 we get:
A- A:
f(x f(x')
Xi41 (88-v(((''.. x ++1 x*)
A .2
f(x²)
Xt+1 +
4
7- Ai
F.1 PROOF FOR THEOREM 3.1
Proof. Let 2 O. By Lemma
we have:
$22 x S s(x') - (1) + 1 A
Using the first claim of Lemma F.1 have:
< (> + A1) + Ex + ex) < 2(2 + A1) k2+1 + 2(E, + ex)²
Adding (A A1) X241 both sides of this inequality and substituting the first display, we have:
[[v )|2 + (A + x2
< 3(A + A1)²
A A (f(x)- - -(xx + - A, A A + 2(i + +()²
4
4
S
< 12(A + )1 2
4 (f(x') - -((x(t)) + 12(1+ + A
(A - (1- + +4) + 4e²
Summing up from f to T we get the claim.
23

---

Published as a conference paper at ICLR 2026
F.2
PROOFS OF LOCAL CGM FOR SOLVING THE SUBPROBLEMS
Lemma (Composite gradient method). Consider composite problem:
min xERd
{ F(x) = ((x) + x
where is La-smooth and à 0 strongyy convex and simple with Xv O. Let Li- Consider the
composite gradient method:
arg mui (x(x)) == o(xx) + (Vó(xa): x xx) + T I| x+112 +x)))
X++1 =
xERd
Then for any & 2 0, F(x++1) & F(xx). For any K 2 1, it holds that:
|VF((K))] = 8T. [((o) F(xx)
(Ls + Aa)
where xx- = min (xx)
[V Furthermore, if ~ Geom(p) with p E (0, 1), then we also have:
Eg [ - SLiP [((x)) - Eg [F(x((x++]]]]
Lo + X
Proof. Let By (Lo + >s)) convexity of Lx, any x E Rd, we have,
Lx(x) 2 (xx+11) + Lo + do 1|x xa+1ll..
2
Substituting x Xs. follows that,
F(xx)= 2 ((xx) + (Ve(x))) Xx+1 Xx) Lo ||xe+1 Xx (x(++))) Lo + 2o
||xt11 Xx
2 (((+)) + (x++1) + Las + Au ||x4+1 xull² F(xx+1) +
Too + Au
||x441 - Xx 11?
2
2
This proves that the function value of I' monotinically decreases. By the definition of x we get:
Vo(xx) + La(x++1 - xx) Vib(xe+1)=
It follows that:
VF(**+1) = Vo((x+1) + Vip(x++1) Vo(xE+1) - Vo(xx) + T xx+1),
and hence,
Xxll S 2Ls ||x+1 Xall [V < [[V - V + lxxx+1
Substituting this inequality into the second display, we get, for any k 2 0:
8L3
|F((x++)11 Lo + Ao [F(x)) F(xx+1)]
Summing up from = 0 to 1, we have:
K
8L3 Lo + 2
Σ [VF(x))|
[F(x)) F(xx)]
Dividing both sides by K. we get the first claim.
For the second claim, substituting & K with R Geom(p) into the last second display, passing to the have:
expectations and applying Lemmal
8L3
Ex(F(x)) F(xx+1)]
To A
812
< L + Xo
((1 - Eg + BR (F(xn)))
8L2p
[F(xo) B [Fx(x))))
Lo Xx
24

---

Published as a conference paper at ICLR 2026
F.2.1 PROOF OF LEMMA
3.3
Proof. Applying Lemma F22 (with ((xx = fi( and xx() = (5' - ff((x"), x²) + x x'1]3)
have for any t 0:
(LF(F)(x*) Pi)
é = Vx
(L1 A)K
where F7 == xin (F((x)). Applying Lemma F.I we get:
Σ
Fx(x') F S f(xx) f" A1)
It follows that:
T-1
8L8
Σ
2 S
(f(x))-
Σ
(I11 + X)
2(1
We next upper bound Df=0(((x') - f¹). Applying Lemma F2 have for any 2 0:
1(x S fxx) + 2(A A1)
Summing up from i to tti=tt10 we have:
Σ
f(x²) S f(x
2(x A1)
Hence,
T-16-1 シ
T-2
$2
() -f
ΣΣ
((A-A)) TTF +
2(2
A
1=0
follows that:
T-1 Σ
7L?
T-1
TTF
(T + 1)
(L +
A)K
2(^ A1)
==0
t=0
To achieve the accuracy condition 6 by the choice of K, have
SLi
SLT
(A+ A
817
(1+1) 8L.
<
and
[A 1-) S1.
(L1 A)K K
(Li (Li+A)K' 2(x A.)
Passing to the full expectation, we get the claim.
F.2.2 PROOF OF LEMMA H.2
Proof. Applying Lemma
F2 and F1
have for any t2 0:
8LiP
8L3p
$ 2(1 Ai)
E (ef)
Rx
(F())
Fi }] <
Li + X (xx, -f(x)) ((x+t)]]
-
+
L1
+
Taking the full expectation and summing up from i == to
= T - 1, we have:
SLiP (f(x9- - 8 + 2(2 - A1) Σ M
Σ Elej) S
Li +
By the choice of p, it holds that:
8L3P = 17(1- - -Ai)
21)
<A-A 5 A
L + (L1 + X)2
and
4Lip
L
1
(L + A)(2 - A1)
2(I, + X)2
Hence, accuracy condition d is satisfied.
25

---

Published as a conference paper at ICLR 2026
F.3 PROOFS OF PROPERTIES OF THE SAGA AND SVRG ESTIMATORS
Lemma F.3, Consider the SAGA estimator. Then for any tz 2, holds that:
b' bb=bb-1
(x's bs,
70m
Proof. Indeed,
b b.-14 + EV((')
= 1 1 b
-
n
77
S68.
VV fs, (x') bss
7km
F.3.1
PROOF OF LEMMA 4.1
1/ independent from x' and (b;-))==1 Therefore, according to Lemma B.2
Proof. Let & 2 2. By definition, G = Dies, G) where G: ffi(x') - bb + +bb-1
and S. is
we have:
1 n Es, [G'] = G = vs(x') and [ll Vx('
1- 1 -2
11 m 1,1
where 0ř,1 := + fi - b - (VS(x') b1 Taking the expectation w.r.t. S on both sides, we get:
oi n Es₁ 10--1110 11=7,11 Qm oi,
1
We next derive the recurrence for o.. Denote Xr == ||x x" -11 For any a > 0, we oblain:
014 1 Σ IVV bb) - (Vf(x*+) - b'
(V'( b9) (V/(x)) b9) + (x)) - )]](
(V/(()) by) (V)(x) bi) (1+ 1 82 82
(1 1++a a)
a1++a)
[x')') - bj - -/ | [|b]
(1+ - a x²
= (1 a1++) -
[x(())) |2 + Σ V((x)) b - 2 - [b'lp] + + x2m1,
7hm
rgS.
where the last second equality follows from the identity IV -b: -Vx(x') = bb, and the last cquality follows from the definition of bj. Further note that
Es. Tt
Vf((') by_ v)('01 =
P(i S.)) - -b--
LESL
-1- [+(('' -b:
(1--) 7mm
Jo? + |bb-
Taking the expectation w.r.t. St on both sides the last second display and plugeing in this identity, we obtain:
Es, 16 + (1 a1+ b s (1 + +a)
1 Toî.2 + | (1 + a) Tu
|Vf(('))
Tim
(1 +(1
1 8² Es, 1x2+11.
+
+ α
Taking the expectation w.r.t. Sp-11 both sides and denoting B = (1 +1 a) Espy |l| [1|b we get:
24, + B < (1+ 1mm
1 )o?,
+ B²_ + 1 a G - (1 + a
18 xē+1
nm
26

---

Published as a conference paper at ICLR 2026
Let 1 7/mm (1 + a1((1 1/nm) (1 1/mm. 1). We then have: y (0,1), + Pmm
8m and
1
1-7 2m= The previous display can thus he reformulated as:
11111 B -
Toî. + B +
Thm
G² + 7m 7782
Xi+11
70m
nmm (m0m - 1)
1 1-9
Let T 2 3. Applying Lemma E.4 (starting from & = 2), we have:
Elo + B 1- 1-7/um 102. + Bi] 7/ 7/nm t-2
Mmm 7 G
Am 7 8 82itt]]
7/nm
Am (nm -
1 1-9
2m3
Adding 2i.1 to both sides and dropping the non-negative Bi, we obtain:
T-1
Pim (Am -2) 7-1
Σ pii 7
Am
7m 7 Bi 7m
Σ
G
8
222
?
7(1m 1)
7(1 ?)
Xi+1
1=
1=
Recall that by- = fi(xx) for all i E [n]. It holds that:
22 0,1
82 = x2x2, B
nm
G
7mm
It follows that:
Σ oi S
(Am - 7) 711m 1)
G + Rum Σ
T-1
ct
+
nm (nem - -))
am
6²
T-1
Σ X
7mmm
1) t=2
7(1 - 7)
Let choose y which minimizes the coefficient in front T-1 Xē+ı over (0,1). By Lemma E.5
we get
VTL. Substituting 7", we have:
T
T
oी S (V
(V ni nm + mm (1 v Mm
Σ
Gt nmm (VTm + Vnm 1)20²
Σ
X24
Vnm
t=2
2
T-1
T-1 Xi+1
S 2m Gt + (1
v R'
Σ
G
+ 4m
Multiplying both sides by am substituting the identity of
4m o2, and
2m m
(1+
+
Vrm -1
mmm
a-
we obtain:
m(n-1
T
Σ
of
27 G# + Thm 1 + / un (n 1)
Thm Σ G
4m 0m
Σ Xi
m
Adding of = 0 and
of 0 to both sides, prove the variance bound for T 2 3, since Go fx(x))
and G (x(xx) The same incquality also holds for T and 2, since of of and
02 3m 02,1 Om X2.
F.3.2 PROOF OF LEMMA
Prouf. Let 2 1. By definition, G' - E.es. G. where G := V/((x') - V/((w") VS((') and S,
is independent from x" and w'. Therefore, according to Lemma E.2 have:
Es, [G 1 n G = Vs(x') and Es, [|
1
Txx
02.1
n1 m
Since we+1 independent x and w we have for any where 0f,1 == - (x') (h:(w") )12
a > 0:
1 1
B B |0 = (1 pB)
Σ
Vh,((((1) (Vh,(w')1
1=1
(1-p + 2)0 (1 - pe) (1+ d)) 82x..
27

---

Published as a conference paper at ICLR 2026
where xe+1 : |x 1 x'I. Let 7PB (1 pb) + a) E (1 pB,1). We then have y E (0, 1) and
1 1/a= 1-2p7
Therefore, the previous display can be reformulated as:
p2(1-)
B [0 s (1 XPB)0ř, + (1 - P1) pB1) 6² Xi+1
p - 7)
Taking the expectation w.r.t Wir on both sides and denoting 0²,1 : Bujyy (2/1). we have:
F S (1 --pa)oo (1 - pB) pB7)
8' 5xxt+1
p 7)
Let 2 2. Applying Lemma
E.4 (starting from = 1), obtain:
Σ
T
YPB
0i, + (1 - p1) pB7)
8²
T-1
Σ Xi+1
Pp
p1 - 7)
1=1
Adding oi, to both sides and using oi, = Eun [oî S (1 pa)0 xi = (1 - pn pn)) xi, we obtain:
xi.
Σ
T
2
(1 1lp-330 p2)0"" x2 1+
(1 pa) pa7)
8² Σ
T-1
7PB
p - 7)
Xi+1
1=1
1=1
(1 pa) - pB7)
T-1
8²
Xi+1
71 7)
According to Lemma E.5 yy = y", we get:
the minimizer of (1-pe)(1-pe) over y E i0, Pn
l-vi-ra
Substituting
x32(1-7)
(1 -1- pa)82
ΣdI (1 v1 pB)
2
Multiplying both sides by Im and using the identity of = Es oi, we have:
|||
[((x*)
=
4m m
Enge [o7.]] =
m
Σ
T of
(1
PB)0
T Σ X
T
Xt
VI pa) 1=1
PB
t=1
(=1
Adding oa G
vx(x")1 2 to both sides, get the variance bound for T > The same hound holds for since o = and of 4m oî, - (1 pa) )
D
Theorem F.4. Let T-CGM be applied to Problem 7 with the SVRG estimator under Assumption 2.7 and 2.2
Suppose the inaccuracies in solving the subproblems satisfy (6p. Then by choosing X = 33,, + T65m PB. after T 466.
iterations, we have E|[l f )17) 2², where x" uniformly sampled Ca The communication complexity at most CA [mm + (2Cn +
from (x() (x=)Er- By choosing pB Ca mm
1) (256(A) 4-6hm Co [wm]] 1/C2)0
The proof strategy the same the for Theorem
Implementation of SVRG. At the beginning when L = 0. each client = 1..... n computes V (x(x)) and sends the result to the server; the server then aggregates these results, computing V f(x") to initialize G This requires one full synchronization. At cach iteration t 2 1, the server uses R-CSS and sends w' and x' to the clients in St and then receives the gradient difference V (x') ff((") from them. If we= 1, the server computes the new gradient f((w') performing one full synchronization and stores in memory; otherwise, it continues with V f[(w") = ( which already stored in memory. In total, the server needs maintain two points x' and w' and one vector ff(w') and the clients are so-called stateless.
F.4 PROPERTIES THE RG ESTIMATOR
F.4.1 PROOF OF LEMMA 5.2
Proof.
Let 2 0. By the definition of RG
we obtain:
||g +1 (x(x** ")
= ||(1 - Ag + 3G' fx, - (x') v/(
= -I(11 - (E' - vS(x')) + 3 - Vf(x') + (x') - Vhs, (x
(1 - -3 + +| -V((x)) (Vhs, (x') (xtt)))
+ (2(1-8) (g' 1/(x'),((C* vf(x')) (Vhs, (x*t(*)111)
28

---

Published as a conference paper at ICLR 2026
By Assumption 5.1
St is independent of x', x1* and G Furthermore, since g' is deterministic function
of G x x
S and g g' by induction, S, is also independent g'. Hence, holds that:
Es, lgg - vf(x') (1xx",,8 3( vf((')) + Vhs, (x') Vhs, (x (x*+))]
vf(x',, Es, VV/(x'] + Es. Vhs, (x') Vho, (x {)
By Assumption Vhs, (x
we have Es, G') fx(x'), Using Lemma E.2 we have Es, (hs,(x)) [xtx(x') Vh((x 0 and
Es, Vhs. (x') - Vhs, (x ++
qm
VVh((x')) Vhi(x ( 11
8m 8mxi+1
VIL
Taking the expectation w.r.t. St on both sides of the first display, we get:
Rss [+++]]
= (1 2) + Es, [II v)((')) + (Vhs.(x)) - Vhs, (x (x)+)))) 1)
- (1 3) + 233 Es, ||| V/((')111) 28
Taking the expectation w.r.t 11-1 on both sides and substituting the notations, we get:
14 S (1 (1- (1-18)550 3) 2,3 o + +22 X2+1
Applying Lemma
D.4
we get for any T 2 1:
T Σ>'
(1 3)²
D/
23
T-1 Σ
di
28 T-1
Σ
Xi+1
(F.I)
28 82
3 1-0
28 8²
1mD
This proves the claim since g ff(x") and Eg = 0.
F.4.2 PROOF OF COROLLARY 5.3
Proof. Let T 2 1. Note that, under Assumption
5.1 we have Bs l|lx
11.2
Es 1|x
I|1 = xi and [/ = Esp a/ V (x') ||1 = G¹. Applying Lemma
we have:
Σ of 2m G + Thm 1 1 Vnz.
G + 4n 6m
(n - 1)
Applying Lemma
5.2
we obtain:
T
23
T-1 Σ
25
T
Σ
Σ
S 2
0i
29
g3
Xi
t=
t=0
Combining the previous two displays, we have:
9m G² 2m(mm 1+ nh Tim
T-1
8
n2 82
28
T
G²
Um (2- 8ym
(2 B) 1)
28
32
1m2
1=1
F.4.3 PROOF OF COROLLARY
Proof. Let T 2 1. Applying Lemma
we get:
4 |
Σ
Bs -
E
[| - x111
Note that, under Assumption depend on wt-1 is +11 since g" is computed using x' and G which is a function of w; Therefore, Wt-1 is also independent of x' and x Hence, we have Es Bsp-r |||x' -x² = Es [X = xi-
S independent of x' and -- Moreover, the first iterate that might
Taking the expectation w.r.t. S 9p-1 on both sides of the first display, we get:
T
482
T
2
Xx
P3
0=
29

---

Published as a conference paper at ICLR 2026
where of
[m |l| [](x')] Applying
Applyyng Lemma
5.2 taking the expectation w.r.t. wi() and substitut-
ing the identity Es we obtain:
[5]]
= Bsy
[
Σ and Bstr-a) mi [Xi]
Es = = xi.
23
26
Σ
ト - 2
3
+
23
8
Xt
twb
Combining the previous two displays, we have:
T
8
/PB
28
2/3
32
F.5 PROOFS FOR [-CGM WITH SAGA
Lemma F5. Let x' be the iterates of I-CGM RG SAGA and let G* be theA estimator for all t 2 Let Cr
denote the randomness generated during the process of solving the subproblem F:-1 inII-CGM for any L 2 1.
Assume that { are mutually independent across I. Then the iterates [x" ) [m and the estimators {G' t=
satisfy Assumption 5.1
Proof. The equation IG' fx(x") has been proved in Lemma 4.1 We next verify the dependency of randomness. Iet f 2 1 and denote Stg == (Sa.... St) and Stq = (Ci,...,Sh Ge). Assume that is a
deterministic function (S|=22). Ste)). Then G' a deterministic function of (S[+) ((t)) since G' depends only on [ := (x",*² ",.x"..... x') and St. Next observe that g' is function of St-2. x <f-1, x== G and g' Therefore, g² is a deterministic function of Si--2] and CJ--1]- Finally, from the update rule offI-CGM x" is a deterministic function of g <i and x" x' Therefore, the assumption that x" is determinsitic conditioned on (S(-2), (1n) is satisfied. This implics that Se is independent of X((+)). Gt >..., Go.
F.5.1 PROOF OF THEOREM
Proof. According to Lemma
H.2 by choosing p B[L, the accuracy condition c for solving the
subproblems is satisfied. Applying Corollary
5.3 and taking the full expectation, for any T' 2 we have:
T Σ
434m1mm Gt (2 83
2mm + v ne. Tim
T-1
G
8
n2 62 + 26
T
(2 (m 1)
28 32
X
1=0
1=1
where x7, G7 and x² are defined in Corollary Vnh -mm n-1
3.2
Using I B
1,
S 1,
1m n
S 1 S
Tmm and
< 7m as n we get:
T Σ
x s 48
T-1
Σ t=1
G. + (83n dzn
28
T
Xt
3
0
Let \ = bb/Dmmm + constants should satisfy:
and 3
1 where 0 <a < 1 and b,c > O. To achieve the error condition 7 the
12(A + A,)
()-A1)3 + +8)18mm S
12(1 + (1 (T1-a)² a)²
(1(1++)) a)²
4 S 2 +8)
+
and
(2((A 41)2
(A (A-AA)) +8) (88nim0 +
282
8/)
s
(22(1 a2) a)²
(1 a)² +8) 22)m 2t Sbn (A+Ai))
which gives:
12 + o)² (1 - a)z
+
S c 2. +
8
(12(1+a)² + (8/0 Sb.
12(1 + 0)2
(F2)
(1 a)²
Let a, b, o satisfy F2
We can apply Corollary 3.2 and obtain:
32(A + A )a F
32(1 + a)² 1-a
pd (1 A1 + by 6m
A- A
a
T
Minimizing the coefficient in front of Ai gives a' satisfied and we have:
Choosing b = 113 and e 112, the condition
F2
256( Ai
38 /tmmdmm))
B||| {("))()))
T
30

---

Published as a conference paper at ICLR 2026
Therefore, to achieve ||]] [[IVV((""I1"] < we need at most T = [ 4 F iterations. We next compute the communication and local complexity. At the beginning when t = 0 and f = 1, we need 2| (mmm communication rounds with A-CSS to compute two full gradients and the associated local complexity is for each round. Additionally, 2 communication rounds with D-CSS are needed to compute x' and x², where the local complexity for each round. For subsequent iterations 2 2, one communication round with R- C-CSS
is needed for updating g' and its associated local complexity is 2 since each client in S needs to compute V fx"") and f((x*"1) Then another round with D-CSS is required to compute the next iterate, where the local complexity is Therefore, the total communication complexity is at most:
[() = B + CRNR + ND]
< 2CA Rmm + CRT +T
(256(A: + /m8mnmmm) F
=2CA [mm] + (CR + 1)
g²
The local complexity bounded by:
((e) = E[Na+ + ND/p + 2N
$ 2 2mmmm + p
T'+
(2+ 8(L1 + X)
2m +
T
D
28A; + 1130 nm /1100/mmm 8m 8L1 (256(A) (1) + 3mmmmmmm F
< 2m +
+ +1)
2 + 113
8²
512(7A, + 283 2833/mm 8m + =2
4h1
$ 2 +
D1 + 28m/nmmm 14+
F.6 PROOFS FOR [-CGM WITH SVRG
Lemma F6. Let x be iterates of I-CGM RG SVRG and let G' be the SVRG estimator for all denote the randomness generated during the process of solving the subproblem Fe-1 in in[--GGM for any / 2 1.
Assume that 1e are mutually independent across t. Then the iterates {x" Tema and the estimators |G' 100
Jt=o
satisfy Assumption 5.1
Proof. The equation Es, randomness. Let t 2 and denote X[1] (x", ...,.. ..,''),,, ). w[]] = (wi,..., We) and (i) (L....., (t). Assume that x² is deterministic function of ($p-2) 2]c-2), (n)). (Sio-2) (p Sta) since w' depends only on x", w'-l and wi. Then G' is deterministic conditioned on Wij. Qn)) since G' a function x,, w. S.. Next observe that g" x!=?, G and g-- Hence, g' deterministic function of (S(=2)) W[r St-1j). Finally, from the update rule I-GM x' is deterministic function of g'-1, Ç. and x f-1 Therefore, the assumption that xf is deterministic conditioned (5(1-2),00e-))) <te) is satisfied. This implies that S, is independent of X(++))-
has been proved in Lemma 4.3 We next verify the dependency of
(in)) ). It follows that w" is a deterministic function of
a function S,-2, x
G
Lerl-CGMDb be applied Troblem[undde Assumptions 2. 2. and 2.3 where x 1+1 = CGM (A, Kr, x g²) with K, ~ Geomlp) and g' is generated by the RG SVRG estimator. x- Then by choosing À = 3A, + 226../ /pg. B pn and +(L++>)' after T (2561a, +85m/ /Pn)r" iterations, we have TR. [ 1l7] S s², where x" is uniformly sampled from (x' )x= Further let let pB CA CAlmm The communication complexity is at most Ca [nm] (2CR+1) (280(1) +88m /CA nm l/ and
Theorem F.7 (1-CGM-RG-SVRE)
CR
the local complexity bounded by 16+ [nmm] 1024(1, 4 441 33 / CA nm l/CR&m)
4hg
Proof. According to Lemma H.2 by choosing p
8[L, + the accuracy condition e for solving the 5.4 and taking the full expectation, for any T we have:
subproblems is satisfied. Applying Corollary
T
x
8,3 52
23
Pp
g2
28
T
X1
8,882
P1
28
B
T
X1
2
A=1
31

---

Published as a conference paper at ICLR 2026
Let A bdm/vpD and B constants should satisfy:
2n where 0 a and c 0. To achieve the error condition 7 the
41)
8/38
26th
12(1 + aa²
+8)
(1 a)² (8))8//22))0m S 2b6 S (A+ A,)²,
(A - 21)3 (1
pB
B
which gives:
12 + a)²
a)² + (8/C+
(F.3
Let a, b, satisfy
F3
We apply Corollary 3.2 and obtain:
32(A + A ) pd 32(1 + a)? (- + 6dm / /PB
F
B /
S 1
A A T
T
Minimizing the coefficient in front of A gives satisfied and we have:
1 Choosing 22 and c condition 3'
H
256(A) A1 + 86m / A E {()))
T
Therefore, achieve [x]V)((>*)1 22, need most T
[256(A) +88m (P)
iterations. We next
compute the communication and local complexity. At iteration O. the full gradient V fx(") is computed which requires [nw, communication rounds with A-CSS. each iteration t 2 1. with probability pa. full gradient is computed, which requires [rem rounds with A-CSS. The expected total number of rounds where A-CSS is used is thus bounded by: [m 1 [n 1pm_ TThe
The associated local complexity for each round with A-CSS is always 1. For t 2 1, one communication round with R-CSS is needed for updating and its associated local complexity 3 since the client i S.-1 needs compute fxxx''')) f.w ") and (x(''). Then another round with D-CSS established, which has the local complexity 1/p. Therefore, the communication complexity is bounded by:
(e) B[C.NN+CCNNN & (emp)Hn)npeee2)C+ CA CA[nm ++ [m 1ps +
Let CA ([[nm, fm 1pa CR. We have
N(e) S Ca + (2CR + +1) (256(A) + 86m / /Aa mmm 1/CR) F00
The local complexity K(e) is bounded by:
E[NA + ND/p 3NR] [nmi + [mm 1E&T + T/p 3T
8(T=1 + +))
[nml] +
+ 1)T
2 An
8Ta + 32A1 2648mm VpR (256(A) 86m/ (Bm//DR)FF F
[nml +
+1)
2A1 + 226m / /PB
(8L, 32A, + 2645m )
4L1
[nm] + 128
+16 + A
g²
118m/ vps
G I-CGM-RG-SAGA WITH INEXACT INITIALIZATION
In the main paper, consider the RG SAGA This allows to satisfy the desired discuss the case where only one or no full gradient is computed this estimator. Let introduce the parameter to E {0, 1, 2} to determine how many times the full gradient is computed at the beginning. We have the following definition for the general SAGA estimator:
estimator with two full gradient computation during initialization. condition ( without incurring additional error. this section,
G V (x)),
G¹ = vx('), 05t5 G' bbs b'. +b' 12 max(ta, 1)
(G.I)
where St E ((m)) is uniformly sampled at random without replacement, bb, 1 Eses, e,, bj. b Eies, b Di for all t max(to, 1), and for any i (r)). by is recurrently defined as:
vx((x)) if Sp. otherwise,
6
to
by Vf(('') 05t5 to 1, e [n),
0
32

---

Published as a conference paper at ICLR 2026
and
b = fx(')) i Se:
1 2 max(to: 1).
b
otherwise,
We have the following recurrence for b':
bD
VSso if = O: 1 D otherwise,
b'=
1
(x))
- bbs
12 max(lo, 1).
Rm
Lemma G.I. Consider the SAGA estimator
G.
under Assumption 2.2 Let 10,1).
Then for any t 2
Es,
G') = f(x')) and for any T 2 1, we have
Σ o
T
mm |V
Rim
1 vnn
1em
G
4m 8
T
X
(to- 1)
(n
1=0
T
di
2
S (12v
n².
nm
qm
)8 + +8 +/8
Mmm |)(x")]1
m
10
+ n'm
1 + vm
Pym Σ ct + An 8m
Σx [=1
T
x2. (to = 0)
(n-1) 1)
where of Essy [|| {x()))]
C? Esg
[|V[(())1]] x² = Es₁ 1n ,||lx x11_ Sig =
(Stg:..,))) S.) and Co = 1 E [(x))
Proof. When to = O. we have Es, [sp[G'] = Es, [/ = V)(x)) When to = 1, we have G
(xx)).
For 2 L, G = b',, b²,²' + b² and the unbiasedness has been proven in Lemma 4.1 variance bound. Following the proof Section F.3I we have for any 2
We next study the
22H1 BB S (1 7mm
2 102, + BB + Num 7 1)
G²
Om 2 82x2 X
Mmm (11m (mm
1 7
where o2,1 Es 1 I by (Vf(x)) b' bb-1) [1].
Bi
nm mm
B8p [b'11a]
and
y E (0. 1). Let T 2 2. Applying Lemma
E.4 (starting from t 1), we have:
Σ Lo + 1 - mmmmm
foi,
+ B
7/nmm Σ
Tmm -7 Ge +
nm 77
82xet1
7/nm, n'
mmm(mm -
1-y
Adding o., to both sides and dropping the non-negative B we obtain:
Σ oं γ σi, Thm 7 B + Am 7
Tim
T-
Σ ct
Tem (nom - 7) 8²
T-1
X
(G.2)
7 7mm 1)
7(1 ()
1=1
Suppose to 1. Then we have bi- -V)((x)) for all i E [n]. It holds that:
o., Σ [V(()()))) -((V)())-V((((()) (V)(x)) Vf(x 1
-
8²x2, Xi,
B²
Am - [V][(2)))
Tim
It follows that:
T Σ
of
(Am - 7)
)1(x"))²
Tmm 7 (nm
Σ G Thm Tm (nm 7)
T-1
8²
T-1
Σ Xet1
7(1m
1)
7(1 - 7)
Substituting 7 = 7- nm re R. that minimizes the coefficient in front of Et= xē+1 over (0, 1).
multiplying both sides by qu, substituting the identity of 2m oi, 1. we have:
T of 2mm Jm [V](x)11 Ne Σ
T
n nm Σ
Gt 4n 02
Σ
2
Xi
(n
t=1
Adding ob = 0 to both sides, prove the variance bound for T 2 2, since Go Vf(x²). The same incquality also holds for T since of 2m oñ, S am x²x2
33

---

Published as a conference paper at ICLR 2026
We next prove the case for to 0. Going back to G.2 substituting 7 = Nm Vnch Tom that
minimizes the coefficient in front of ET-1 Xi+1 over (0, 1), multiplying both sides by substituting the identity of Im ti we have:
m
o? S
2mm7mm
oi. +
2qm Am B +
1 1+ v nm
C² + 4n 8m
Σ x
m
m
(n 1)
Let a be such that (1 +1+00 a:(1 - 1/mm)) = 1 72 /no as specified in Lemma 4.1 By the definition of b.. we have:
ii,1 (VV1((x)) - b,) (VI(x)) 1²
TFC
AIC
(1 a)
1 Σ
[(([(())) b,) (VS(x)) ( bb)11 (1+ o
1=1
= a1+ 1 Σ |V V)5o(x)111 + Σ |V/((²) - V {[5o(()11) + (1+ 2
ie50
1g
az [Vf((x) [x,011 + Σ [V - (1s60x)) (x))(x)))
+ +n - 2/) [x) |||] + (1+ 8x8
It follows that:
o Es, [=].]]
LBb
(1+ a)
9m + (n m){3 ml V/ + (n 2m)]l (n 2m)
pm co
+ 1
m
(1+
1 9m
4m 1
c + (1 (1 1// + (1+ 2) 8²x2
m n
nm
7mm 7-'
(1 1/mm
qm /mm qm // 11 ||
+ nm - 0²
1
I-
7lm
(1 1/mm + 2m 4m/m qm nn (1 1 (1-
2tm 8²x
1pm
By the definition of Bi, we get:
B Ron 7
Rs, |
[VF(("))
Om c3]
1
Substituting the bound of of.1 and B we have:
1 + VnHt
1m T-1
< auco + bu + 7m
Σ
2
4n Om
Xi 2
(n 12-11 1)
where do
20m 1m
(1 1/nm + 2m - gm/n)) and bo
20m
(2 1 1/rem) ). Using
24m Paas
Thm
2n n-1
Am < 4 n nm since n 2 2, we have ao
S 12 n nom and by S
8 B/
Tmm By the definition og. we have:
[1 f(((")l Es, Vfs, (x") Vf(x")
4m m
Adding of to both sides of the previous display, we conclude the proof.
We next consider the RG estimator with inexact initialization.
(x g
(1
3)g + 8G' + VSss(xx+)) (x,,)'), 1 12 0,
(G.3)
Let now combine RG
G.3 and SAGA
G..
They share the same randomness S, starting from 2 0.
34

---

Published as a conference paper at ICLR 2026
Lemma G.2. Consider the RG-SAGA estimator G.3
G.1
under Assumptions 3.1 and
2.2
Let T 2 1.
Suppose to L, by setting g" = G VV(("),, we have:
4m
[f((x))1
(m 1+ mmm 1m
T-1
G
n.
62
28
Σx
T
x2
(to=
8)m
(2- 1)
28
8
1=
1=1
If to = O, then by setting g replacement, we have:
V ()=_((²) where S-1 E (In)) is sampled uniformly at random without
Σ 3 <
(1 B)
+ +1+
2
4m
+
249
n 1bm
2 + 2
16/
1m Gr
28 - 132
2 2-8
m
2- 8
8
28(nm 1 Vnn 1mm
T-1
G
8
Rim
2 om
+ +228
T
2
(2 - (1
28 B2
1=1
[=1
where E? = Esp 1) Allg' vf(x))1 G. == Esp 2
|||| V || xa = Esp 2) p1lxx - x
S/1 ==
So......... S1) and C == 1/2 (VV1lVV(((X) Vx(x")
Proef. Suppose to = 1. Then gº = =v)(x". Applying Lemma 5.2 independent of 1|- we have for any T 2 1:
and using the assumption that x" is
Σ
T
c S 2 3
23
Σ
T-1
26
T
Xt
23
82
t=0
t=0
1=1
Applying Lemma G.I with to = 1. we have:
of
2ma
|I*+
1 + Vns. (n 10-1) 1)
G
4m pm
xe
m
Combining the previous two displays, we get the first claim.
We next prove the case for to = 0. Since Es, [s, = fx(x)) for any 2 0 and Assumption 5.1 is assumed, inequality (5.1) is thus satisfied. Taking the expectation w.r.t. S-1 on both sides of [..] we have for any T 2 1:
(1-
23
28
23 - 32
20
2
3
Σ
29
3
X1+1
Adding E = Es_, [lle ff(x = =3 to both sides and applying Lemma
G.1 with to = 0, we
conclude the proof.
Theorem G.3. T-CG be applied to Problem with RA-SAGA G.3
estimator under Assumption 2
and 2.2 Let g = f((x") if 1 and gd Vis (xx) to = O, where S_1 (Inl) uniformly sampled
at random without replacement. Suppose the inaccurucies in solving the subproblems satisfy (6) Then by
choosing x = 3A1 1116mm/ppp and 3 112mm the total communication complexity N(e) required to find an s-approximate stationary point is most:
256(AI + 38 //m E
8qm me²
Ca(Rm) (CR + 1)
(to 1),
g²
and
(CR + 1) 256(A, + 38 3888// mmmmmm))) Fd
+ (112gm/ m + 28 - 1/nm K2 + 11611-111mm Gb (to =
8²
where
GĀ := [Vx((')]1 and G = Σ [V((x)) - ((
Proof. Let T 2 1. Applying Theorem 3.1 taking the full expectation and using condition 6
we have:
T G + (A+
Σ x2 < 16(A + A F +
12(() + A
T-1
+8
M
A
(A A,)²
35

---

Published as a conference paper at ICLR 2026
where Ci. x² and Vi are defined in Corollary 3.2
Let first assume to 1. Applying Lemma G.2
with
1, we get:
Σ
T
2
(2 3)m
mm Jmn
[V](22)]|
2m - 1 + V Am Rm
(2 (2-B)(re (1 - -1)
T-1
G
8,5 8m +
2
B2
28
T
X
A=
4m qm
G + 48 Σ Ct + (88 o2 +
28
Xi
m
where we used 2-3 I 1, 2m S -m S S Tmm and
S 7m as ni 2 2. Using the same choice
E-I
n-1
of parameters as used in Theorem
6.1
it holds that:
+ 12(A+ (A 11) + 8) 43mm
12(A
12(A + A1)²
+ (8BnTOm +
26th
S SA+
(A D1)²
It follows that:
Σ c Σ
16(A + A1)²
12(2 12(A+A1)
+
4m GB
A A1
(A A.)2
1/b
4qm G
< 128(A1 + 38 dm)) F
Therefore, to achieve B[Il ((*)) e², we need at most T
250( + +38/nmmmm)m
84m CB iterations.
We next compute the communication complexity. At the beginning when = O, we need [ communication rounds with A-CSS to compute one full gradient and the associated local complexity is 1. Additionally, one communication round with D-CSS is needed to compute x². For subsequent iterations 1 2 1, one communication round with R-CSS is needed for updating g'. Then another round with D-CSS is required compute the next itcrate. Therefore, the total communication complexity at most:
N(E) = N + CR Nn] s CA mm + C&T +
We next consider the case where to = 0. We follow the same reasoning strategy as for to = 1. Applying Lemma G.2 with 40 = 0, we get:
E <
(1 8)2
+ 1
2/
4m
248 ni.
S
+ 2 - B
163
V n - n. nm
2B - ga
2- 8
m
2- B
28 (mm
1 + v vnh.
1mm
G
88 n
pm
++28
(2 (m - 1)
28
Xi
(=1
282
T
S (Agm/ / + 24B ni.
m 163 ng.
Gg + 4,mm
Σ
Gt (88 +
x
1=1
Using the same choice of parameters as used in Theorem 6.1 it follows that:
16(A 16(A+ +
+1)2 FO + (12 A,)
((1gm// 218 ni. Tm kd + 16, nih Tem Gb)
(1 A1)²
128(Ai A1 + 38 388/mmmm 5m ) (56gm/m f00gm//mm/ + 14 1/mm) 3 + 8 1/mm
Therefore, to achieve B[IV
(112gm/ mm + 2I-II1/mm + 16 1/mmm C81 iterations. We next compute the communication complexity. At the beginning when = 0, we need one communication round with R-CSS to compute g" V , (x") and the associated local complexity is Additionally, one communication round with D-CSS is needed to compute x'. For subsequent iterations 2 1, one communication round with R-CSS is needed for updating g'. Then another round with D-CSS is required to compute the next iterate. Therefore, the total communication complexity is at most:
< e², we need at most T | 256 (mmmm)) )
N(E) E(CANA + CnNa + No) S CRT+T. +T
Summary. The communication complexity 1-CGM-MGRCC RG-AAA with one full gradient computation (to 1) is (e) S CAnm + Cr (Am- )
+ Cr
9m o3
Compared to the case where ig = 2. this complexity has
an additional error term depending on || V
|P. Furthermore, to = 0 (no full synchomization is needed),
(ee) X CR (AL+vmmmm ) CR(sm/ m + vI - rtm) 2 +
the resulting communication complexity is
CRVI - G8. This quantity does not depend on CA but has two additional error terms depending on + ff(x)) f(("") and [|V 12, due to inexact initialization. Note that when m + these
error terms eventually disappear.
36

---

Published as a conference paper at ICLR 2026
H SOLVING THE SUBPROBLEMS WITH LOCAL STOCHASTIC CGM
In this section, discuss how to achieve the inaccuracy condition ( by running stochastic CGM locally.
Lemma H.l (Stochastic composite gradient method), Consider the composite problem:
min F(x): = ((x) + +xx))
where @ is La-smoone and xxx) == | x12 where & E R" is a fixed point and X 2 O. Suppose we have
access to an unbiased stochastic gradient oracle g" for V such that:
Eclg"(x: S)] = Vo(x), Exlllg"
= VX E
Consider the stochastic composite gradient method:
Xk+1 arg min (x) 6(xx) (xus (x)x xu) + 21xxxx xx + xERd
Let 1) Lo and K Geom(p) with p (0, 1]. Then have:
2(1 >o)pD B[((x
I.p do d². 2n Lo + Xv
(1 p) 100
2n- Lo + X
Proof.
Let & 2 0 and denote = (xL: St). By (n + sttong convexity of Lt, for any x E 18d we
have:
(x(x) (x(x++1) 7 As
||x x
2
Substituting x = Xx. follows that,
xx| 2 (xx+1)) + do
F(xx) 2 ((x)) + (gu, Xx+1 X4) +
||x+1
||xx=] - xxll
2
2
21 La + Ao
((x++1) + (xxx++1) +
||x - x + (B: Vo((x), xx+1 xXA)
2
=((x++1) 21- T.S de ||x++]
Xx.
(gx Vo(x)), X4+1 xx)
2
Let 1) 2 Lg. By the definition of XE+1, we get:
g + (xxx+1 Xx) + (N =0 + Xx41 Xk 7 A (-Vp(x)) - ga)
It follows that:
(ga Vo((c), X6+1 xx)
(gA- VV((x)), - -V - (gi - vv(xx)))
17 + An
and that:
Ig+ vo(x=)+ (F(x))1 VF(x.))
| Xu
(n+ )
Substituting these identities into the second display and taking the expectation w.r.t. Gk. we have: Lo + A 2(1 + Ax)²
2n - Lo + Xu
17 7 1
F(x:)= Bec [F(x+1)]
1xp Ece lllEs vo((x))
[VF(())]
2(n + )n))a
21 Lg + Au
Lg + do (VF((x)) 2(n + Au)
Be, (P(x
2(n Xx.)2
Let (To] = (Go...., (c). Taking the expectation w.r.t. C(k-1] and rearranging, we get:
E Ex [II < 2(17 + Xp)²
Lg + Ax
2n Tos A (F(u-)(F(xx))) Esgy) [F(xe+1))) +
2n T.6 A
Substituting k: k with K- Geom(p). taking expectation w.r.t A and applying Lemma
E.3 have:
ER [IV = (1 (1- (1) BR Gi [[V )11) pll FXx))]
2(n Ax)
Lo + As
$ 2n Ls + Ax [E (x(x)] ER.SpO [F(x)+1))) + 2n Ls Ax
o²
2(n + )x
Lss + Av o².
$ 2n La + Ag
((1 - p) ER [F(* + pF(xx) - -B BR [F(x++1)]) +
((1-p)
2n Lg + Xoo
Taking the full expectation both sides, we get the claim.
37

---

Published as a conference paper at ICLR 2026
Let now apply SCGM to solve the subproblem of (L-CGM) with x(x) [1(x) and vx(x)
(g' VVi(x'), x') +
x11 For ls 0, L, Ke
v1+1 = arg min p(y + (v() si) + 7 ||x - vill" + b((r))
2
YERU
(HII)
(nyr + Xx' Vf((') - (y A 1)
where gi is the unbiased gradient estimator of V with bounded variance o², Ki Kr + 1 where K₁ Ge) The solution is set to be x YK., We use the notation x*+1 SCGMrand (A, Ke,x', gg) for this process.
Lemma H.2. Consider I-CGM with x SCGMeand (A, ry, Re x', gg))
where K. ~ Geom(p) under Then by choosing X > Ai,
Assumption (27 and 2. Let T
2 1 be the fixed number in condition c
L1 + 2(a+1,))
À- 20+
< 1. the accuracy condition E Eleī]
(A+.,)) + -EE > Tc²
A-
satisfied where is the target accuracy for achiving B[IV
S
Proof. Applying Lemma H.T and Lemma F.
we have for any 2 0:
(1 Ele + Ele - 2(n + 2)
L1 + X
21j L1 + E[F((x') Fi(x ++ }]
+
21 L1 +
2(n 2)2p
Σ
L +
< 2n- 1,1 + (BIf(x') - f(x
2(A-
2n 11 +
where e²1 = | [x)x("")]"" Summiin up from / = 0 to L = T and dropping the non-negative E(e+] and ea1.
we have:
Σ Eleal <
2n - L1 + (f(x") - Σ 2(2
2(17 + 2)3P
2n L1 x To
L +
A1)
< 2 + X)p(f(x)) -ft)+ + (1 + X)p
11 TO²
Σマ
D
By the choice of 1 and A, we have:
(A + 41)²
L+ To La +
2(1+ A)p ー- A
A p -22 <1,
To
=TE² /2.
x A
(Ia Xy20 /62
To ensure convergence I-CGM, the expected number of local steps by using stochastic CGM thus + 2tyi When  0, recovers the result of deterministic CGM with randomized local steps.
I DISCUSSION ON THE SAG ESTIMATOR
SAG is another incremental gradient method (Schmidt et al. 2017). SCAFFOLD has successfully applied it to the FL settings. Specifically, the local update rule of device at outer iteration (assuming stochasticity for simplicity) is:
yi = (V +b' vf(('))
7
Compared with the local CGM (3. Scaffold sets À = 0 and uses b' (SA) instcad of G' (SAGA) in the control variate. we next show that the variance of b' cannot be controlled by 5. Let 2, t = 1.
by (x") and by fx((x"). Then we get: b' (V + ff((x))). if Si {1} and
ba (Vfa(x*) )x) if S (2). Then the variance can he computed as:
Es, [ -)(())))1
Σ
[/(x9) - vS(x'))
While for SAGA, we have:
Es, G -
Σ Vhx vh.(x+)]1*
where h; := f= f- ft. Therefore, the SAG estimator cannot fully exploit functional similarity as efficiently as SAGA in the worse case from theoretical perspective. Nevertheless, SCAFFOLD can still perform well empirically on some problems, as shown Figure J.7
38

---

Published as a conference paper at ICLR 2026
Quadratics minimviation with logosmm penally (M 10,0 100)
104
10f
101
101
101
109
107
181
10
200
400
Communication complecity
complecity
Iterations
- 1000
10
02
Figure J.1: Comparisons of different initialization strategies of minimization problems with non-convex log sum penalty.
for solving the quadratic
log-sum
Quadrattes minimrlatioo with log sum penaliy (m 10,0 100)
10"
30*
100
304
1.0
107
102
10"
307
10-1
10-1
10:1
75000 2000000000000000
Communication comptetity
complexit
Iterations
pm..05
pn0.5
p=0.005
Figure J.2: Comparisons of different p (number of local steps) used in local CGM for I-CGM-RG-SAGA when solving quadratic minimization problems with non-convex log-sum penalty.
J ADDITIONAL DETAILS AND EXPERIMENTS
We simulate the deep learning experiments on one NVIDIA DGX A 1000 the other experiments are run on MacBook Pro laptop.
J.1 QUADRATIC MINIMIZATION WITH LOG-SUM PENALTY.
Everywhere in the paper,
the first choice of the control variate for SCAFFOLD (Karimireddy al. 2020
We set the number of local steps K be 20 and the local learning rate be 0.003 (0.005 diverges the beginning) for FEDAYG and SCAFFOLD. For S solver and set K to be 20, local learning rate to be 0.005 and the probability for computing the full gradient to be 0. matching I-CGM-RG-SVER gradient computations of other algorithms. Finally, the comparisons of different initialization strategies for
we use the standard gradient method as the local
For GD, we run 14000
20 700 iterations to match the local
1-CGM-RG-SA can found Figure J.I (to = 0, 1, correspond to computing the full gradient 1,2 times at the beginning).
J.1.1 ABLATION STUDIES I-CGM-RRG-SGA
Initialization strategics. The comparisons of different initialization strategies for I-CGM-RG-SAGA be found in Figure I.T (to = 0, 1, 2 correspond to computing the gradient 0, 1, times the beginning. See Section G for the details). The result shows that the method works well without any full gradient computations.
Local steps. We now compare the performance of I- I-CGM-RGE RG-GAGA under different choices of the parameter which is defined in Local CGM Theoretically, = X- Since the expected number of local steps per
local computations. In the previous experiments, used the 100 0.05. We now vary p (0.5, 0.05, 0.005). From Figure J.2 we observe that Large p 0.5 results in worse communication complexity since the local accuracy condition is not fully satisfied; Small p 0.005 achieves similar performance p 0.05 in terms of communication complexity. This is expected, since communication complexity is determined hy the fixed parameter However, the local complexity becomes worse, as the total number local steps increase and becomes unnecessarily large.
iteration is 1 smaller corresponds
default value p
Constant X. We now study the impact of the constant À on the performance of I-CGM-RG RG-SAGA. Note that directly determines the iteration complexity. Theoretically the best À A + 6. In the previous experiments, used the default value V 15. We vary X {1, 10, 100). From Figure J.3
39

---

Published as a conference paper at ICLR 2026
Quadratic leg-som penalty (M
100)
(000411
101
10a
10
20"
107
101
10"
15000
Communication
Iterations
lambda=]
lmmbdaa10 10
lum Idde1000
Figure J.3: Comparisons of different À used I-CGM-RG-SAGA for solving the quadratic minimization problems with non-convex log-sum penalty.
minimeiation
100)
10P
102
105
10
10"
10A
10-
102
10a
10a
10'
10r
10
200
400
5GB
5000
10000
15000
200
400
600
Communication complesiyy
Local complecky
beta-0.01
beta-0.005
beta-0.00
Figure J.4: Comparisons different used (CGM-RG-SAGE for solving the quadratic minimization problems with non-convex log-sum penalty.
we observe that: 1) Large À = 100 results in worse communication complexity since it does not fully use the similarity structure; 2) Small À 1 does not converge the theory requires À 2 A /Tem all matching the theory.
Constant B. We now test the effect of used the RG estimator. Both larger or smaller 8 can the- orctically increase the variance bound (Lemma 5.2 hhooreicallly, the best B = ___ We now vary {0.5, 0.1, 0.05, 0.01, 0.005, 0.001 }. From Figure we see that / E [0.05, 0.5] results relatively better performance as complexity.
0.1 and the values that tall outside this range lead to worse communication
Ratio of CA In the main text, report results under the extreme setting where CA Cs 1. Now Cg we test how increasing the ratio CA/CR affects the performance. Specifically, we vary CA 5,,5, 10, 20} while keeping Ca = 1, and repeat the same experiments. From Figure J.5] observe that the performance 1-CGM-RG-SVEE degrades
increases since each use of A-CSS becomes more costly. contrast, I-CGM-RG-SAGA remains largely unaffected, as ASS only used during initialization. This result further confirms the advantage of I-CGM-RG-SAGA in settings where full synchronization is costly.
Ratio Finally, we examine how the ratio influences the performance of our method. Theorctically, both the communication and local complexities scale with vr,, 13 /e2. We fix m = 1 and vary E (10, 100, 1000)- The datascts are generated in consistent manner so that the values of 5 and Lmax remain approximately n. From Figure we observe that increasing Tém indeed leads to higher communication complexity. However, the growth is moderate: the additional scales by roughly //10/v100 /1000/ /100 rather than linearly 100/10 = 100/10- = 10, confirming that the dependence on /nm instead 7mm-
unchanged, We set À 6 s 5//mm.
Tay. and p X L+Lmmn z X+100 with
J.2 LOGISTIC REGRESSION WITH NONCONVEX REGULARIZER.
For both datasets, we set p = 0.1 in Local GD for CGM-RG RG methods and SCAFENEW. and use A = 10 local steps for the other algorithms. We select the best local learning rate for each method from (0.1, 0.2, 0.5, 1.0] for Mushroom and (0.002, 0.001, 0.0005) for Duke. For proximal-point methods, choose the best À from (10, 0.1, 0.01) } on both datasets. We 8 for both I-CGM-RG methods.
40

---

Published as a conference paper at ICLR 2026
1,
100
101
107
107
107
-24
107
207
107
107
1.0
18
207
201
500
1000
1509
2003
4:07
5202
10900
5005
15000 15000
Communication complestt
Cimmun-ciiin compleilty
Commuricat complesty
Communccation complesity
1-G54RG-SAA Jeurst
Figure J.5: Comparisons of I-CGM-RG-SAGA against I-CGM-RG-SVRG under different CA/Cn for solving the quadratic minimization prohlems with non-convex log-sum penalty.
Quadratics minimstation with log sam penalty (m 1]
100
10"
107
10"
10"
20*
107
10
101
101
10f
109
10²
4000
6000
5000
19000
15000
Communication complastyy
Local complecky
iterrtions
000
Figure J.6: Comparisons of I-CGM-RG-SAGA under different 7mm for solving the quadratic minimization problems with non-convex log-sum penally.
J.3 EMNIST WITH RESIDUAL CNN
We now extend our study to neural network training. Specifically, we train a 6-layer Residual CNN on the EMNIST dataset (Cohen el al. 2017). which consists of a collection of 26 letter classes. We use n = 26 and m 5 23 /n, and split the dataset according to the Dirichlet distribution with = 0.1 (the smaller batch size of 128 for
the a, the higher the heterogeneity, a 0.1 is highly heterogeneous). We computing both the local stochastic gradient and the control variates. For all the methods that use control variates, including I-CGM-RCE RG. SCAFFOLD, SABER and SCAFFNEW, we add a damping factor g in front of the control variate to enhance their empirical performance, i.c., on line 5 of Algorithm we use yi+1
arg millyeR (x())= (g) (yí2 + -gi (x')) - + yy +
where y E (0. tuned parameter and gi is the stochastic mini-batch gradient of V f1. This approach is suggested by Yin al. (2025). We report the best local stepsize 7 among {0.05, 0.02, 0.01, 0.001 and the best among
1.0001,0.01.. 0.1, 1). The final choices of the parameters be found in Table J.I The convergence behaviours
can found in Figure J.7 best validation accuracy can be found in Table J.2 where performs the best.
optimizers
hyper-parameterss used for multi-classsfication tasks
I-CGM-RG-SAC
0.02, A 0.01. 0.01. 0.2. 0.001, fo
I-CGM-RG-SVRG
1 0.02, = 0
0.2, 0.001
"
SCAFFOLD
Karimireddy al. 2020
0.02, K 100. 0.001
FEDAYG
McMahan el al. 2017
- K 100
SCAFFNEW
Mishchenko
2022
0.02. 0.01, 9 0.001
SABER
Mishchenko ct al.
2024
0.02, = p 0.01, 8 0.2, q 0.001
Table J.1: Hyper-paramects of the considered optimizers used in the multi-classification task for the EMNIST
dataset.
Optimizers
I-CGM-RG-SVRG
SABER-FULL FULL
SCAFFOLD
SCAFENEW
FEDAVG
Accuracy 86.2
86.0
85.3
85,9
84,9
85.6
Table J.2: Comparisons of validation accuracy for different optimizers used in the multi-classifictiinn task for the EMNIST dataset within 100 outer iterations.
41

---

Published as a conference paper at ICLR 2026
6-layer
0.5
arcurry
$1n.00
2x.107
2X117
102
20
5.
25
100
25
120
2500
5:c0 7500 10020
2503 5003 7505 10005
Commuriccioo complraty
Commurioon www.rriaiinnncooo CNTIEbSITy
Local complestt
(008 compresiy
CCN NG SAGA lours)
.CO MC SVIG lourd
Scatfodd
Scathnow
SASER
Figure J.7: Comparisons different algorithms on EMNIST dataset using a 6-layer residual CNN.
CIFAR10-Resmet18 (m=3, n-10, 0.1, batch sizee122)
Second-order Similarity
0.8
MAMAAA Y
Validation accuracy
0.7
0.6
value
Valication
0.5
0.5
10a
0.4
0.3
0.3
local smoothness
average dissimillaily
0.2
10000
Communication complexity
Local complexity
iterations
-COM-RG-SAGA (ours)
ICGM-RG-SVRG (ours)
Scaffold
Scaffrew
FodAvg
SABER-full
Figure J.8: Comparisons of different algorithms on the CIFARIO dataset using ResNet18.
J.4 CIFARIO WITH RESNET18
We now consider multi multi-class class classification tasks with CIFARIO Krizhevsky al.) using ResNet18 (He 2016). use n and m = vn, and split dataset according to the Dirichlet distribution with 0.1 (highly heterogeneous). We use a batch size of 128 for computing both the local stochastic gradient and the control variates m. We report the best. local stepsize among (0.1, 0.05, 0.01, 0.001) and the best X among (0.001, 0.01, 0.1, 1}. The final choices of the parameters can be found in Table J.3 The convergence behaviours can be found in Figure J.8 The best validation accuracy within 100 outer iterations can be found in Table
CIFARO--Resnt18 (m=3, n=10, batch sibe=128)
Veldston acconso
0.5
101.
0.6
cal Emootnncco
20
40
90
90
100
2500
5000
7500 10000
40
60
80
100
Communicaatio compleoryy
Local complexity
Rerations
Figure J.9; Performance of 1-CGM LLGG--GG-SAAA RG-SAGA on the CIFARIO dataset using ResNet18.
42

---

Published as a conference paper at ICLR 2026
optimizers
hyper-parameters used for multi-chassificationn tasks
I-CGM-RG-SAGA
0.05, A 0... y= 0.001, fo =
I-CGM-RG-SVRG
0.05, A 0.01, p 0.2, = 0.001
SCAFFOLD
Karimireddy et al.
2020
= 0.05, K 100, 0.001
FEDAVG
McMahun al.
2017
: = 0.05,
100
SCAFFNEW
Mishchenko et al.
2022
0.05, p = 0.01, 4 = 0.001
SABER
Mishchenko al.
2024
0.05, 0.01, p= = 0.01, / 0.2, 0.001
Table J.3: Hyper-paramettrs of the considered optimizers used in the multi-classification task for the CIFARIO
dataset.
Optimizers
I-CGM-RG RAGSAGA I-COM-RG RG-SVRG
SABER- FULL-
SCAFFOLD
SCAFFNEW
FEDAVG
Accuracy
76.1
77.0
74.5
72.3
74,2
74.3
Table J.4: Comparisons of validation accuracy for different optimizers used in the multi-classffictioon the CIFAR10 dataset within 100 outer iterations.
task for
Algorithm 1 1-CGM-RG-SAGA with CGM rand
1: Input: x" E R m E [n], A 0, 3 (0.1), 0.g =V/(x)
2: for f = 0, 1,2.....
3: K;- Geom(p)
4: yó = xx'
5: for = =0 =..1,2.....
6:
Y2+1 T+b (nyl + Axt vn((') - vV(())
7:
x++1_ =yk.tl
8: Sample S. (in)) uniformly at random without replacement
Update G according (SAGA)
Update g+ using G' according to RG
Limitations and Future Extensions. 1) In this work, we have assumed that there exists one delegated
client that is reliable for communication. If we modify the setting and remove this delegated client, then we still guarantee similar complexity with minor modifications. Specifically, instead of fixing the index in [-CMM
we can sample is E [rx] uniformly random and define the updates as =+1 & arg min { (x)
fi, (x) + ha, (x') (g' ff, (x'),x= x') + 2 1|x-xx'1' This variant uses R-CSS instead of D- C-CSS
each iteration. To ensure the convergence rate of APO "7, we need to choose À A max (Jiang al. 2024a),
where Amax X A₁ defined in D.3 However, suppose there exists more than one delegated chent, then it interesting to check we can further improve the current complexity. 2) We have shown that the variance of the SAGA estimator is bounded by the function similarity constant An interesting question is whether something similar can be done for another closely related popular gradient estimator, SAG (Schmidt et al. 2017). used in Scaffold (Karimireddy et al. 2020). turns that the answer is negative (see Section (). Our analysis focuses on the deterministic first-order oracle O,, Opo, is interesting to develop effiient algorithms with stochastic, zero-orde -oder, or higher-order oracles. 4) The current model does not impose constraints on the size of information that is transmitted between the server and clients. A promising direction is to incorporate communication compression and study how such constraints affect the algorithm design and overall complexity.
43


Reviews:
[{"review_id": "n54c33YMCe", "reviewer": "Reviewer_MDyq", "summary": "Second-order similarity is an assumption under which we can reduce the amount of communication needed in distributed optimization problems by leveraging more local work, typically done through (approximate) proximal point operations on clients and using some sort of variance reduction. Prior work mostly relied on SVRG-style variance reduction, as it lends itself well to leveraging second-order similarity, see e.g. [1]. This paper introduces a way to use SAGA-style estimators for variance-reduction, which allows us to do away with having to compute full gradients  after the first iteration (which we need to do for SVRG-style variance reduction) at the cost of additional memory. In fact, the paper introduces a general framework that subsumes both SAGA-style, SVRG-style, and even SARAH-style (recursive)  estimators; The latter kind is the best for nonconvex optimization. Combining this framework with the SARAH estimators gives the best-known convergence rates under second-order similarity compared to prior work.", "questions": "- Please address my concerns in the weaknesses section.\n- The use of Big-O notation in lines 235-237 is very handwavy. You actually need it to be bounded by a constant smaller than 1. If the variance were bounded by, say, 100 times the left hand side, the guarantee becomes vacuous. Can you fix this?\n- Why do you call Definition 2.2 \"Second-order Dissimilarity\" when prior work calls it second-order similarity? We call \\( L \\) the smoothness constant even though the higher L is, the less smooth the function is. We should keep the same convention for \\( \\delta \\) (since it is related to \\( L \\)).\n- Is there any novelty in Section E.2.3 compared to prior work? It seems SVRG-style estimators have already been studied well.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "- The proofs incorporating the SAGA estimator are quite nice, the notion of variance the authors define in the line right under (E.9) is different from the notion of variance used in the SVRG estimator (which is also used by prior work). This is quite novel and I believe to be a very useful insight.\n- The paper explicitly includes details on how to solve the local problems. Even though the stopping criterion requires knowing many problem parameters, this is still appreciated as much prior work ignores this aspect or assumes perfectly solved inner problems.\n\nOverall, I believe the paper makes a strong theoretical contribution but the experimental evaluation is limited (which is fine, it is not the main point) and the presentation could use significantly better work. I lean towards acceptance and can improve my score if my concerns (below) are addressed.", "weaknesses": "- It is quite surprising that the algorithm just chooses the first function at each timestep to calculate the prox with respect to it. This seems suboptimal (e.g. what if that first function is just extra dissimilar? The avg similarity can be low and this one function could just be an outlier).\n- The accuracy of CIFAR10 in the experiments section is far too low. 77%? A three minute run with SGD can reach 96% (see https://github.com/KellerJordan/cifar10-airbench). I suggest the baselines should be better tuned with grid searches and using the latest techniques. This is not expensive.\n- The main advantage of this work is obtained under the regime where the cost constants \\( C_A, C_R \\) differ significantly. The paper makes the claim that \"In large-scale federated systems, ACO is more expensive than RCO\" but this is not really substantiated by any numbers or analysis. Furthermore, the difference between the ACO and the RCO reminds me of the work (Arjevani et al., On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions, 2020). I think using their formulation can automatically lead to an algorithm where only the RCO is needed. I believe this could actually perform better than the rate you give depending on the relation of \\( C_{R} \\) to \\( C_A \\)? (In fact, their oracle is even weaker than the RCO, since it does not even give them the indices of the functions). They do not use second-order similarity but it seems possible to modify their algorithm to use that, as it's just SVRG based?\n- The paper is difficult to read, in part because many important details on the communication model are relegated to the appendix. It would be better to defer more of the technical discussions (and even Table 1) to the appendix and instead focus on introducing this background material.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DliRDIvZsV", "reviewer": "Reviewer_8ScQ", "summary": "This paper introduces a novel framework for non-convex federated optimization called Similarity-Aware Non-Convex Federated Optimization. The primary goal is to reduce communication costs, a major bottleneck in FL, especially in settings with partial and intermittent client participation. The authors focus on bridging the gap between SARAH-type and SAGA-type methods. The paper demonstrates for the first time that SAGA-type estimators can also leverage functional similarity to achieve state-of-the-art communication complexity, rivaling SARAH-type methods, without the need for frequent full client synchronization. The proposed framework CGM-RG unifies these ideas and provides a practical algorithm that outperforms existing methods in both communication and local computation complexity under certain conditions.", "questions": "I have several questions and suggestions.\n\nHow the method performance degrades as $\\delta$ increases? Is it possible to characterize it theoretically and empirically?\n\nHow much of the performance gain comes from the recursive gradient component versus the base SAGA estimator with the new analysis?\n\nHow sensitive is the algorithm to its hyperparameters $\\lambda, \\beta$ and local step parameters? What is the intuition behind setting these parameters?\n\nThe SAGA estimator requires an initial full gradient computation to initialize the gradient table querying all clients. You briefly mention an alternative in Remark E.12 initializing only on a sampled subset. What is the theoretical and practical impact of this inexact initialization?\n\nYou state that the memory cost of SAGA is moderate. Can you provide a more concrete quantification of the memory overhead? How does it compare to other stateful methods like SCAFFOLD?\n\nTable 1 is extremely informative but also very dense and contains a lot of notation.\n\nWhile the components are described, a single, clear algorithm box for the final proposed method would be very helpful.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The work demonstrates that SAGA-type methods can exploit second-order similarity, which is a novel theoretical contribution. The work designs a method that does not require frequent full synchronization, relevant to practical applications. The paper provides a thorough theoretical analysis, including a new framework for comparing algorithm complexities. The theoretical claims are well-supported by numerical experiments on both synthetic and real-world datasets (LIBSVM, EMNIST, CIFAR-10). The proposed CGM-RG-SAGA method outperforms a range of strong baselines, including FedAvg, SCAFFOLD, and SABER. The metric is communication complexity.", "weaknesses": "The authors mention scenarios where the second-order dissimilarity constant $\\delta$ is smaller than $L_{\\max}.$ However, in many practical FL settings with highly distinct data distributions client data can be dissimilar.\n\nThe analysis does not extend to the stochastic setting, which limits its direct applicability to problems involving online learning at the client level.\n\nThe proposed method CGM-RG-SAGA is a combination of well known techniques such as Composite Gradient Method, SAGA variance reduction estimator, recursive gradient updates related to SARAH. The contribution is primarily in the novel analysis of a clever combination of existing tools, rather than in the invention of a new algorithmic principle.\n\nThe experiments are conducted on datasets with a relatively small number of clients. This scale is not representative of large-scale cross-device FL. The experiments use standard, relatively small models.\n\nThe paper lacks an ablation study to isolate the impact of each component of CGM-RG framework.\n\nThe paper is technically dense and can be complicated for a broader audience.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "o5viCqTXd6", "reviewer": "Reviewer_cpvm", "summary": "The paper studies non-convex federated optimization under partial participation and proposes CGM-RG-SAGA/CGM-RG-SVRG—Composite Gradient Method (CGM) variants that plug a “recursive gradient” (RG) variance-reduced estimator into SAGA/SVRG to exploit a second-order similarity condition ($\\delta$-SOD) alongside first-order dissimilarity ($\\Delta_1$-ED). The core technical idea is a new multi-round variance bound for SAGA tightened by a factor of $ns$ via a tunable memory parameter $\\beta=\\Theta(1/ns)$, which then yields improved iteration and communication complexities for CGM with partial participation size $s$ (Theorem 3.8, Cor. 3.9). Under the proposed oracle model with costs $C_A$ (arbitrary/active) and $C_R$ (random), the authors claim communication $\\tilde O(C_A nm + C_R(\\Delta_1+\\sqrt{ns}\\,\\delta_s)F_0/\\varepsilon^2)$ for RG-SAGA, minimized at $s^\\star=m$ and argued to be best among existing methods in the studied regime. :", "questions": "1. **Necessity of two full synchronizations.** Can you prove Theorem 3.8 (or a slightly weaker version) without the initial $\\Theta(ns)$ ACO calls—e.g., with a statistically warm-started memory (random mini-batch initialization) and one composite step only? If not, what failure mode appears? \n2. **Tightness of the $ns$ improvement.** Is the $ns$ factor in Cor. 3.7 minimax-optimal under $\\delta$-SOD, or could a SARAH/PAGE-style recursion match it without SAGA’s memory (thus avoiding ACO entirely)? A direct theorem-level comparison against SABER under identical $(\\Delta_1,\\delta_s)$ would clarify. \n3. **Regime demarcation.** The text highlights an “interesting regime” $m\\ge \\sqrt n$, $\\delta\\lesssim \\Delta_1$ where oracle complexity matches full-gradient CGM (while sampling only $s=\\sqrt n$). Can you characterize the largest regime (in $m,\\Delta_1,\\delta$) where your method strictly dominates SABER/SCAFFOLD in both $C_A$ and $C_R$ usage? A plotted phase diagram would help.\n4. **Local solver accuracy.** What concrete inner solver and stopping rule (measurable on devices) guarantee the subproblem accuracy term in Theorem 3.8, and how many local steps (or gradient calls) does this imply as a function of $\\lambda,\\Delta_1,\\delta_s$? Any mismatch with the empirical inner tolerances?   \n5. **Empirics under stronger heterogeneity.** Can you include experiments with larger $n$, varying $s$ (e.g., $s\\in\\{\\sqrt n,\\,m\\}$), and tasks where $\\delta\\approx L$ to test the boundary where similarity gives little advantage? Also add multiple seeds and error bars.\n6.  The primary theoretical communication gain depends on $C_R \\ll C_A$, but the experiments (line 424) use $C_R = C_A = 1$. This setting does not validate the theoretical claim. Can you provide experiments in a simulated environment where $C_A$ is set to be significantly larger than $C_R$ (e.g., $C_A = C_R \\cdot n/m$) to demonstrate the practical benefit of your $C_R$-dependent bound?\n7.  Could you clarify the initialization requirements in Theorem 3.8? It appears to require computing $g^0=\\nabla f(x^0)$, $g^1=\\nabla f(x^1)$, and $b_{i,0}=\\nabla f_i(x^1)$. How many full-client synchronization rounds does this entail? How does this heavy initialization align with the core motivation of avoiding the full-participation burden of SARAH?\n8.  The paper argues that SAG (used by SCAFFOLD) cannot exploit functional similarity $\\delta$ (Appendix H). However, in the deep learning experiments (Tables I.2, I.4), SCAFFOLD performs almost identically to your $\\delta$-aware method. How do you reconcile this theoretical limitation of SAG with its strong empirical performance?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- **Originality.** Introduces an RG-SAGA/SVRG estimator composition inside CGM that explicitly leverages $\\delta$-SOD; the variance recursion is sharpened by a factor $ns$ relative to classic SAGA analyses (Cor. 3.7), which is technically neat and nontrivial. \n- **Quality.** Theory is stated with clear assumptions ($\\delta$-SOD, $\\Delta_1$-ED) and tracks the impact of estimator error and subproblem accuracy on iteration complexity (Theorem 3.8). The communication model (ACO/RCO/DCO) is formalized and tied to partial-participation costs, enabling proper comparisons. \n- **Clarity.** The CGM subproblem and its use of $\\Delta_1$ are clearly exposed; the proof sketch for controlling $\\|\\nabla f(x_{r+1})\\|^2$ via function decrease plus estimator error is transparent (Eq. (2) and subsequent inequalities). \n- **Significance.** If the stated bounds hold, the work sharpens the communication-vs-computation frontier for similarity-aware FL under partial participation, highlighting when $s<m$ suffices to reach the “full-gradient” rate (discussion after Cor. 3.9).", "weaknesses": "- **Novelty gaps vs. prior variance-reduced FL.** The “recursive” flavor has strong parallels to PAGE/SARAH-type recursions used in SABER and related CGM variants; several ingredients (e.g., plugging VR gradient trackers into CGM, periodic/full-grad syncs) exist in recent work. The paper’s comparison table is helpful, but the “best known” claim would benefit from a tighter, side-by-side theorem-level comparison against SABER’s second-order-aware CGM under matching assumptions and oracles\n- **Assumption realism/tightness.** Core results require both $\\delta$-SOD and $\\Delta_1$-ED, and solving each CGM subproblem so that $\\sum_{r}\\|\\nabla F_r(x_{r+1})\\|^2=O(\\varepsilon^2 R+\\lambda F_0+\\sum_r \\Sigma_r^2)$ (Theorem 3.8), which is strong and hides nontrivial inner accuracy. The paper argues CGM can ensure this, but the constants are heavy (e.g., $\\lambda\\ge 5\\Delta_1$ plus terms in $\\sqrt{ns}\\delta_s$), and the practicality of meeting the aggregate subproblem condition under stochastic local solvers is not empirically validated. \n- **Initialization costs and partial-participation realism.** RG-SAGA needs two full synchronizations (one to initialize the table, one composite step) incurring $\\Theta(ns)$ ACO calls; while the text notes a heuristic “no-sync” variant often works, guarantees rely on the expensive path. In truly cross-device settings where ACO is much costlier than RCO, this may erase the asymptotic advantage for moderate accuracy. \n- **Proof-level concerns.** (i) The claimed $ns$ improvement relies on choosing $\\beta=\\Theta(1/ns)$; however, sensitivity of constants to $\\beta$ and to client sampling variance is only partially exposed (Cor. 3.7 cites (E.8) but hides constants). (ii) The jump from Lemma-level recursion to Theorem 3.8 aggregates several bounds (58, 24, etc.); while Appendix F spells them out, the dependence on $L$ vs. $\\Delta_1$ and $\\delta_s$ could be more explicitly tracked in-text to make the gain scenarios unmistakable. \n- **Experimental scope.** Main-text experiments are small-scale: one synthetic quadratic with nonconvex penalty and two LIBSVM datasets with $n=10$, $s=m=1$; deep-learning tasks are deferred to the appendix. There are no error bars/seeds, limited heterogeneity controls, and no ablations on $s$ or the two required synchronizations; baselines like CE-LSGD/FedRed or stabilized proximal-point variants are not included empirically. \n- **Comparisons.** The paper presents a textual complexity accounting for SABER (App. D) but does not provide a single theorem/table that places the proposed and competing bounds under the same $\\{\\Delta_1,\\delta_s\\}$ regime and the same cost model ($C_A,C_R$), making it hard to verify the “best among all existing” statement unambiguously. \n- **Clarity/notation.** The roles of $\\Delta_{\\max}$ vs. $\\Delta_1$ (and when each baseline is analyzed under which) are easy to lose; some constants and definitions (e.g., Assumption 3.5, (E.8) quantities $\\sigma_r,\\Sigma_r,\\chi_r$) are only in the appendix while being central to Cor. 3.7/Theorem 3.8. A concise in-main-text summary table of symbols would help. \n- **Claim on Partial Participation:** The central motivation is to avoid the full participation requirement of SARAH. However, the theoretical analysis for CGM-RG-SAGA (Theorem 3.8, Corollary F.5) requires a heavy initialization phase: $g^0=\\nabla f(x^0)$, $g^1=\\nabla f(x^1)$, and $b_{i,0}=\\nabla f_i(x^1)$. This appears to require *at least two* (and possibly three) full-gradient-equivalent synchronization rounds involving all $n$ clients. This is a significantly stronger requirement than standard SAGA (which needs one) and substantially weakens the practical claim of being a true \"partial participation\" method that avoids full synchronization.\n- **Disconnect Between Theory and Experiments:** The main theoretical communication benefit (Corollary 3.9) hinges on the assumption that the random oracle is much cheaper than the arbitrary one ($C_R \\ll C_A$). However, all experiments explicitly state (Sec 4, line 424) that they set $C_A = C_R = 1$. This experimental setup completely neutralizes the key theoretical advantage of the method. If $C_A = C_R$, the SAGA variant's communication complexity is no better than the SVRG variant (Corollary F.7), which the authors claim is \"worse\". This is a major gap in the paper's validation.\n- **Weak Empirical Validation (Deep Learning):** In the deep learning experiments (EMNIST, CIFAR-10), the performance of the proposed CGM-RG-SAGA is only marginally better than baselines. For example, in Table I.2, CGM-RG-SAGA achieves 86.2% accuracy, while SCAFFOLD achieves 85.9% and CGM-RG-SVRG achieves 86.0%. These minor gains do not provide strong empirical evidence for the superiority of the method, especially given its increased complexity and number of hyperparameters ($\\lambda, p, \\beta, q$ in Table I.1).\n- **Experimental Comparisons:** In the non-convex quadratic experiment (Figure 1), several key baselines, particularly SABER-partial, are plotted for a very small number of communication steps before terminating. This makes a direct comparison difficult and may present an overly favorable view of the proposed methods, which are run for a much larger budget.\n- **Method Complexity:** The final method is a complex composition of three distinct algorithms. This introduces numerous hyperparameters (e.g., $\\lambda$ from CGM, $\\beta$ from RG, $p$ and $\\eta$ from the local solver) that require careful tuning, as evidenced by Tables I.1 and I.3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "p15KyHz8wc", "reviewer": "Reviewer_RxwZ", "summary": "This paper proposes CGM-RG (Composite Gradient Method with Recursive Gradient Estimators), a framework for communication-efficient federated optimization that exploits functional similarity among client objectives without requiring frequent full-client participation. The key contribution is showing that SAGA-type variance-reduced estimators can exploit second-order dissimilarity, traditionally thought to require SARAH-type methods with full synchronization. By combining SAGA with recursive gradient updates and a composite gradient method, the authors establish state-of-the-art communication complexity bounds that match or exceed SARAH-based methods while supporting partial client participation.", "questions": "Refer to the weaknesses above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper makes a genuine algorithmic and theoretical advance. The central insight, that SAGA estimators can be analyzed to depend on $\\delta$ rather than individual smoothness $L_{\\max}$, is novel and non-obvious. \n- The introduction of three communication oracles (ACO, RCO, DCO) with associated costs (C_A, C_R) is a methodologically sound contribution.\n- The paper is technically rigorous. The proofs appear sound (though I have not verified every detail). The generality of the framework, incorporating both SAGA and SVRG as instances of the same recursive gradient estimator approach, demonstrates good mathematical design. \n- Table 1 shows CGM-RG-SAGA achieves state-of-the-art communication complexity while avoiding periodic full synchronization.", "weaknesses": "- The experimental section is underdeveloped for a paper making strong theoretical claims: The quadratic with log-sum penalty (Section 4, Figure 1) is a well-controlled synthetic problem where theory-practice alignment is most likely.  Experiments use $n \\in (10, 26)$ clients. Real federated learning involves thousands to millions of clients. It's unclear whether the proposed method scales and whether the theoretical constants are practical.\n- EMNIST and CIFAR-10 experiments (Appendix I.3-I.4) are crucial for demonstrating practical relevance but are deferred and treated briefly.\n- Missing practical insights: No wall-clock time comparisons, no investigation of parameter sensitivity (how to choose $\\beta, \\lambda, p$ in practice?).\n- The damping factor $\\alpha$ is added \"to enhance empirical performance\" (I.3), suggesting the base algorithm needed modification. This raises questions about whether the theory-driven design actually works well in practice or requires ad-hoc tuning. Why does the algorithm require adding a damping factor $\\alpha$ in Section I.3? This suggests the base theory-driven design needs tuning. How sensitive are results to this choice?\n- The paper assumes $\\delta$ is small enough to provide benefits. However, no guidance on when $\\delta ≪ L_{\\max}$ in practice. No empirical method for estimating $\\delta$ a priori.\n- The CGM subproblem solver (Section 3.4) is referenced as CGM_const and CGM_rand, but the actual algorithms are not presented in the main paper.\n- The discussion of SAG vs. SAGA could be clearer. The paper defers to Appendix H, but the main text should give readers intuition for why SAG fails.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)