Tighter Performance Theory of FedExProx
Authors: Wojciech Anyszka
Kaja Gruntkowska
Alexander Tyurin
Peter Richtárik
Venue: ICLR 2026 Poster (2026)
Keywords: distributed optimization
extrapolation
Primary area: optimization

Abstract: We revisit FedExProx -- a recently proposed distributed optimization method designed to enhance convergence properties of parallel proximal algorithms via extrapolation. In the process, we uncover a surprising flaw: its known theoretical guarantees on quadratic optimization tasks are no better than those offered by the vanilla Gradient Descent (GD) method. Motivated by this observation, we develop a novel analysis framework, establishing a tighter linear convergence rate for non-strongly convex quadratic problems. By incorporating both computation and communication costs, we demonstrate that FedExProx can indeed provably outperform GD, in stark contrast to the original analysis. Furthermore, we consider partial participation scenarios and analyze two adaptive extrapolation strategies -- based on gradient diversity and Polyak stepsizes -- again significantly outperforming previous results. Moving beyond quadratics, we extend the applicability of our analysis to general functions satisfying the Polyak-Łojasiewicz condition, outperforming the previous strongly convex analysis while operating under weaker assumptions. Backed by empirical results, our findings point to a new and stronger potential of FedExProx, paving the way for further exploration of the benefits of extrapolation in federated learning.

Published as a conference paper at ICLR 2026
TIGHTER PERFORMANCE THEORY OF FEDExPROX
Wojciech Anyszka" Kaja Gruntkowska Alexander
Alexxnde Tyurin 3.4 & Peter Richtárik?
Princeton University, Princeton, United States
2 King Abdullah University of Science and Technology, Thuwal, Saudi Arabia
3 AXXX, Moscow, Russia Applied Al Institute, Moscow, Russia
ABSTRACT
We revisit FedExProx-a recently proposed distributed optimization method de- signed to enhance convergence properties of parallel proximal algorithms via ex- trapolation. In the process, we uncover a surprising flaw: its known theoretical guarantees on quadratic optimization tasks are no better than those offered by the vanilla Gradient Descent (GD) method. Motivated by this observation, we develop novel analysis framework, establishing tighter linear convergence rate for non- strongly convex quadratic problems. By incorporating both computation and com- munication costs, we demonstrate that FedExProx indeed provably outperform GD, in stark contrast to the original analysis. Furthermore, we consider partial par- ticipation scenarios and analyze two adaptive extrapolation strategies-based on gradient diversity and Polyak stepsizes- significantly outperforming previ- ous results. Moving beyond quadraties, we extend the applicability of our analysis to general functions satisfying the Sojyak--jjsiiwiizz condition, outperforming the previous strongly convex analysis while operating under weaker assumptions. Backed by empirical results, our findings point to new and stronger potential of FedExProx, paving the way for further exploration of the benefits of extrapolation in federated learning.
INTRODUCTION
Federated Learning (FL) (Konečný et al., 2016; McMahan al., 2017) is a distributed machine learning paradigm where multiple edge devices collaboratively train a global model without the need for centralized data collection. Instead transmitting raw data, each client computes updates based their local datasets, and these are then aggregated central server to update the global model. This approach ensures that no sensitive information is shared with the server or other clients, making it particularly useful in privacy-sensitiv domains, such as healthcare (Ricke et al., 2020) and recommendation systems (Hard et al., 2018). Formally, FL solves the optimization problem
min nERd
where /; RRd + R represents the empirical risk associated with the local dataset stored on client i e [n]. Despite its advantages, FL introduces several nontrivial challenges, including communication delays caused by limited network bandwidth, and partial participation of clients due to random outages (Kairouz al., 2021). Addressing these issues essential making FL efficient and reliable in real-world applications.
1.1 RELATED WORK
Let us briefly review several existing methods used to solve problem (1) in FL scenarios. For a detailed overview of the notation used, please refer to Table 1.
Gradient descent. The simplest and most naive approach is the Gradient Descent (GD) method (Nesterov, 2018), iterating Ft-1
z (x²()) Fy 71 Σ Vf(()),, where 2p is
"The work of Wojeiech Anyszka conducted during VSRP internship KAUST.

---

Published as a conference paper at ICLR 2026
starting point and y > 0 is the stepsize. Let introduce the key assumptions typically employed in the analysis of GD in the convex world.
Assumption 1.1. The functions fi are proper, closed and convex for all i E [nz] and the function f attains a minimum at some (potentially non-unique) point x E IRd Assumption 1.2. The function f is L-smooth, i.e. VV Vf(wi) - L || yll Vz, y Rd. Additionally, each ft. E [n]] is differentaible and smooth,, with Lmax == max Li.
Under these assumptions, classical optimization theory guarantees that GD solves problem (1) and finds I E R2 such that f(ā) f(x.) S in (sLRf/s iterations, where It2 := ||,, zoll² In
an FL setting, finding a solution to the main problem requires each client to participate in every communication round, and thus to communicate with the server
LR
(2)
times, transmitting the local gradient ((( at each iteration k. While this approach is conceptu- ally simple, its direct application distributed environments leads several challenges related to communication overhead and scalability.
Partial participation. real-world FL scenarios, not all clients remain active for the entire duration of training. Instead, a subset of clients is chosen at each iteration, typically based on practical factors such as device availability (e.g., battery life or network conditions) or statistical considerations (e.g.. data heterogeneity) (Kairouz et al., 2021; Tyurin & Richtárik, 2023).
Communication bottleneck. Another key problem in distributed training is the communication bottleneck (Ramesh et al., 2021; Kairouz al., 2021). Since the overall performance of distributed algorithm is the product of the number of communication rounds K needed to find a solution and the cost C of one such round, there exist two main strategies addressing this issue: (i) minimizing C' and/or (ii) minimizing K. Objective (i) is typically achieved via compression of the information transmitted between the clients and the server (Beznosikov et al., 2020; Gruntkowska et al., 2024). Objective (ii) can be accomplished by increasing the amount of local computation performed by clients between rounds, allowing for less frequent communication.
FedAvg and modern local methods. A common strategy for ensuring communication efficiency that falls into category (ii) is local training. The idea is simple: allow clients to do more work before transmitting the results to the server. If executed with care, this approach leads to each communication round providing more "informative" updates, ultimately resulting in more effective changes to the global model. One of the most popular methods in this class is Federated Averaging (FedAvg), introduced by McMahan et al. (2017). Within this framework, a subset of clients se- lected in each round to perform local training using wradient-based method of their choice (e.g.. GD). This is followed by an averaging step on the server, where the local updates are aggregated. Despite its popularity. the theoretical properties of FedAvg are somewhat limited (Khaled et al., 2019; Koloskova et al., 2020). A major issue is client drift,, which can lead to slower convergence (Karimireddy et al., 2020). This problem can be mitigated using modern drift correction techniques (Karimireddy et al., 2020; Gorbunov et al., 2021; Mishchenko et al., 2022). One notable advance- ment in this area is FedExP, introduced by Jhunjhunwala et al. (2023), which extends FedAvg by leveraging extrapolation to better control server updates.
FedProx and proximal methods. All methods discussed so far assume that clients have access to the gradients fi of local functions. The class of proximal methods (Bertsekas, 2011; I; Ryu & Boyd, 2014; Khaled & Jin, 2022; Richtárik al., 2024) relies on a different, more powerful oracle-the the proximal operator prox., .Rdd + Rd, defined by
prox,, (x) arg min sERd
(f(=) + 2, 1|= - m||]]
x1=]-]]]
Here, f is convex function and 7 0 plays rule of regularization parameter. It is important to note that computing prox,, (-) is an optimization problem on its own. However, the analyses of such methods typically do not consider how this subproblem should be solved, and instead assume that computing prox..(() is computationally cheap and can be performed using any iterative solver, e.g., GD, Newton's method or LBFGS (Nesterov, 2018; Liu & Nocedal, 1989).
There exist numerous proximal methods addressing the single-node case. A classic approach is the Proximal Point Method (PPM) by Rockafellar (1976), which iterates Fx+1 prox (TR)-
2

---

Published as a conference paper at ICLR 2026
Stochastic versions of PPM have also been studied (Ryu & Boyd, 2014; Bianchi, 2016; Patrascu & Necoara, 2018). Recently, interest in stochastic proximal methods has surged, with promising results from several works (Condat & Richtárik, 2023; Traoré al., 2024; Sadiev al., 2024; Combettes & Madariaga, 2024). In the context of distributed learning, one relevant work by Li et al. (2020) builds the principles of FedAvg to introduce its proximal variant-FedProx. The method replaces local gradient-bascl updates with proximal operator computations, leading to the update rule
Tk+ n Σ prox (Ix))
By leveraging proximal operators, FedProx addresses some of the limitations of traditional GD in FL. However, simply averaging local updates at the server remains suboptimal and can be improved.
FedExProx. A recent advancement, and the main focus of this paper, is FedExProx, introduced by Li et al. (2024). This method improves FedProx by employing the technique of extrapolation' (Combettes, 1997; Necoara et al., 2019). The algorithm operates under the interpolation regime:
Assumption 1.3. There exists v, E Id such that V fxx.) for all [n]]. We denote the set of such minimizers by X. == {z E RR fz((z) = 0} and the projection of x onto X. by IT(x))
This assumption is relatively mild and is often met in practice, e.g., for over-parameterized models (Ma et al., 2018). Instead of (4), FedExProx introduces the extrapolated update
Fk+1 Tk + Ork
prox (II) 2k
(5)
where ag serves the extrapolation parameter. The algorithm is analyzed by reformulating step (5) in terms of Moreau envelopes (Moreau, 1965): the update rule can be expressed equivalently as
Øk+1 = m
a 1 Σ VM7 (zz).
(6)
where the Moreau envelope M7 Rd + R of a convex function f is defined as
M) = min {(t)) +
Va IRd.
zERd
Notably, when og: 1, (5) reduces to (4). However, this choice is not optimal, and choosing og yields better complexity. If ar set to be constant across iterations of the algorithm, then using the optimal value ag 7I.
1
guarantees that FedExProx converges after
o J.. [I. R
(8)
communication rounds in the convex case, where T. is the smoothness constant of the function (x) - M7 (x). Li al. (2024) show that (8) is not larger than O (<=) and can be significantly smaller in practical scenarios. Thus, FedExProx offers provably better iteration complexity compared to both FedProx and FedExP (I.i et al., 2020; Jhunjhunwala et al., 2023).
2 CONTRIBUTIONS
1. Although the iteration complexity (8) of FedExProx outperforms both FedProx and FedExP, we find that it is not superior that of the simplest baseline, GD, on quadratic optimization tasks (see Remark 3.3), This raises a critical question regarding the utility of employing the proximal oracle in the first place.
2. Motivated by these pessimistic findings, we revisit the analysis of FedProx and prove signifi- cantly more optimistic iteration complexity result. We establish linear convergence rate for solving non-strongly convex quadratic distributed optimization problems of the form (1) (see Theorem 4.1) and demonstrate that our new result does indeed lead to the conclusion that FedExProx can signif- icantly outperform GD. Our analysis assumes realistic model that accounts for both computation
Notably, the idea of extrapolation explored by Jhunjhunwala al. (2023) developing FedExP.
3

---

Published as a conference paper at ICLR 2026
and communication times critical factors in real-world distributed optimization. We show that the total time complexity of FedExProx is never worse than that of GD, and can be strictly better when communication time dominates computation time (see Theorem 4.3), which is typically the case in FI. scenarios. This stands in stark contrast to the previous analysis by Li et al. (2024), underscoring the superiority of our new findings.
3. To account for the stochastic setting that involves partial participation of clients, we complement the above results with client sampling (see Theorems 5.1, 5.2, 7.5 and F.I).
4. Beyond constant extrapolation, we establish two novel results (Theorems 6.1 and F.1) that incor- porate smoothness-adaptive strategies, based gradient diversity (FedExProx-GraDS) and Polyak stepsize SIDExPPox-StoPSS again significantly improving upon the result previously established by Li al. (2024) in the quadratic case.
5. We extend the analysis beyond quadratics to arbitrary convex functions satisfying the Polyak- Eojasiewicz (PL) condition, obtaining linear convergence rate (see Theorems 7.2 and 7.5). In contrast, Li et al. (2024) derived a linear rate under strong convexity for the function f. Our ap- proach is not only more general, as it relies on weaker assumptions, but also demonstrates improved dependence on problem-specifie constants. Additionally, we establish a result in the Pł. setting that accounts for inexact computations of the proximal mappings (Theorem F,
6. The theoretical findings are validated with empirical experiments, which demonstrate the robust- ness and applicability our framework.
NOT BETTER THAN GD ON QUADRATICS
Let us take closer look at the complexity result (8). Suppose for now that we solve (3) using GD. Then, the number of iterations needed find prox,,, (ar) with accuracy &
L,+1 log ! = ((7 + !) 1/-
||2 - x 21 is (L; + 1/-) smooth and s/y-stroggyy convex. Hence, ? controls the difficulty of calculating the proximal operator: the larger it is, the more difficult the problem. Therefore, to accelerate local computations, possible. We can formalize this intuition by letting x(+) be the time per one iteration of FedExProx and making the following reasonable assumption:
since the function f((x) + 2n
would prefer choose y as small as
Assumption 3.1. The time complexity >()) of FedExProx step a non-decreasing function of
Combining it with the iteration complexity result (8) established by Li et al. (2024), the total time required by FedExProx with 0% 1/7L. find F such that [zf f(xx) < <
T(x) == (>>) x L. [
With this definition in place, we can now translate the main result of Li et al. (2024) (Theorem 1) to quadratic optimization problems, yielding the following pessimistic outcome:
Theorem 3.2. Let Assumptions 1.3 and 3.1 hold. Consider solving a non-strongly convex quadratic optimization problem of the form (1), where f((z)= 1 A,r b. for all [n], with A, e Sym and b, Rdd. Then the assumptions of Theorem 1 by Li et (2024) hold, and
T(r) =(())= x Lm 2 (0) LRº
(9)
for all >> O. Moreover, when Y + 0, then ((7) x (1+7 R effectively reduces to GD.
+ (0) X LR and FedExProx
Remark 3.3. In light of Theorem 3.2, GD performs no worse than FedExProx by Li et al. (2024), even if the time complexity (ty) of one FedExProx step does not depend on y. Indeed, it holds that
(1 R² LA
for all y > 0 (see the proof of Theorem 3.2).
These results, based on the original analysis of FedExProx, lead us to a rather disappointing con- clusion: from theoretical time complexity perspective, the optimal strategy appears to be using vanilla GD, disregarding proximal oracles entirely. The question that remains is: is this an inherent limitation of the method itself or merely consequence of suboptimal analysis by Li et al. (2024)?

---

Published as a conference paper at ICLR 2026
4 TIGHTER AND MORE OPTIMISTIC RESULTS
Our refined analysis of FedExProx demonstrates that a tighter iteration complexity bound can be derived, leading to significantly more optimistic results. In the following sections, present novel analysis that provides an improved complexity result for FedExProx and sheds light on its true capabilities. To ensure clarity and build intuition, begin with quadratic optimization tasks, where all relevant quantities can be explicitly derived. In Section 7, we extend these advancements general convex functions satisfying the PL condition.
Theorem 4.1. Fix any y and consider solving non-strongly convex quadratic optimization problem (1) where f((z) 2 3xxAA, A₁ by x for all E [n], with A, E Sym and b; E R.. Under Assumption 1.3, FedExProx with a = 1/71, finds x. such that [x) f(x.) S e after
log log
(10)
Myy
iterations, where Ly, is a smoothness constant of M and p.z is the smallest non-zero eigenvalue of the matrix RM
Remark 4.2. To the best of our knowledge, under the assumptions of Theorem 4.1, GD requires
jut log
(11)
iterations to solve the quadratic optimization problem, where y is the smallest non-zero eigenvalue of the matrix A J. >m> A; (Richtárik & Takáč, 2020).
Let now demonstrate that conclusion that FedExProx can in fact outperform GD.
result does indeed provide tighter bound, leading to the
4.1 ONE STEP TIME COMPLEXITY ((>) IS + (7 Iymxx + 1)
As introduced Section the time per one global iteration of FedExProx has two main sources:
1. Local computation: In large-scale problems, each step (5) requires clients to compute prox fi (I&) iteratively. One of the simplest solvers is GD, which returns a solution of subproblem after O (74, 1) local iterations" (see Section 3). If each gradient calculation takes seconds, the total time required for all clients to calculate prox, (2&) is Ô (7 (yLmax + 1)) since the process is gated by the "slowest" client, associated with the problem with the highest smoothness constant.
Once the local computations are completed, clients must communicate their results before the server can execute the global step (5). We assume this communication takes seconds, which can be huge in FL. environments (Kairouz al., 2021).
Communication:
Consequently, the total time per global iteration, T77). is proportional to r7 + T Ly + 1) (thus satisfying Assumption 3.1), and the total time complexity of FedExProx is
(7(7) Ō (11 T (T/max +1)
4 m
(12)
Note that the total time complexity of GD is
TeD = T,(0)) = ( +t).
Our next goal is to determine the value of that minimizes (7(7), with the hope that this time the optimal choice does not result in y - 0. This is indeed the case whenever 17 > т.
Theorem 4.3. Consider the non-strongly convex quadratic optimization problem from Theorem 4.1. Up to a constant factor, the time complexity (12) minimized by some
E
MAX Arayy A.) min
maX Amaz
min
A lternatively, accelerated method could be employed, reducing the iteration count to Ô (V7T. +1 Our analysis can he extended accommodate these faster solvers well.
5

---

Published as a conference paper at ICLR 2026
if 7 2 2 and by some
1-1 Amax(A.) (A:)* (e
Y E 0, max
0, min
mnno (A.)
? 2. Moreover, TT(2)= S TGD.
The theorem above establishes that the total time complexity of FedExProx is no worse than that of GD, and can be strictly better when communication time dominates computation time, highlighting the superiority of our new analysis. Notably, this was not the case for the previous analysis by
Li et al. (2024) (Theorem 3.2). The following example, where (T( < TGD for some > 0, highlights how complexity can significantly outperform that of GD.
Example 4.4. Let the matrices {A,} be diagonal, i.c., A, diag (a.1...., ata) for all E [n]. and
ag > for all E [n], E [d]. Then, according to (25) and (26), we get
Amase( A (7)
slld
max
1479
min jel
70 14795
where Amax(1) and Ami (7) are the largest and the smallest non-zero eigenvalues of the matrix M : Ei= ; - (r + I) ") respectively (see Section C). Taking y = 1/ minneem) ag
and using the fact that 2 T+ 2 2 for all x 2 1, we can conclude that l- S Thus,
n4y
H ME(n as (7, = Ō +
mitt 1EMM)aE
Suppose that communication is slow. Formally, let 17 2 T maaxejn)jjjia aij/ minje(n),je(d] atj Then (7) = Ön)) while the total time complexity of GD is
TED =ì (2 -m 1+ = Ω
SEL
Σ
min Σ SEdd 1m1
which is least max Σ atj/ min E.e aij times worse!
similar improvement can be observed in the general case. However, the derivation significantly more complex, so maintain clarity, the example focuses diagonal matrices only.
PARTIAL PARTICIPATION
Thus far, we have concentrated on the full participation scenario. However, as outlined in Sec- tion 1.1, practical FL settings often involve only subset of clients participating in each training round. To address this, we supplement our theory with a convergence result in the stochastic set- ting. For illustration, we consider nice sampling (see Section A.2), where at each iteration, sub- set S C [n]] of clients is selected uniformly at random from all subsets of size S. Although we use this sampling strategy as an example, other client selection methods can also be employed. this context, we can formulate the following complexity result:
Theorem 5.1. Fix any 7 > 0 and consider solving non-strongly convex quadratic optimization problem (1), where f((x) = 2 A₁r A x for all i E [n], with A; E Sym", and by E Rd. Under Assumption 1.3, FedExProx with nice sampling (Algorithm 2) with a 1/7bn, finds such that B[S(²)) f(x.) S e after
o 0
Sرا log!!
(13)
iterations, where LygS == S Lmax n(S-1) Lyp La is the smoothness constant of M
5(n-1) 147hasx 8(n-1)
and piç is the smallest non-zero eigenvalue of the matrix 72M?.

---

Published as a conference paper at ICLR 2026
Assuming the same time complexity model in Section 4.1, the total time complexity of FedExProx with nice sampling is given by
Ty S) ( + 1)) x
17.8
(14)
As it turns out, the optimal stepsize for the stochastic setting aligns with the one used in the deter- ministic scenario (see Theorem 4.3).
Theorem 5.2. Up to a constant factor, the time complexity (14) is minimized by
E
max (E(m)
Amnux (A.) min
max xe(ms
Amax ( (A))
man (A.)
if 2 and by
E O, max
0, min
Amax A:)
min
(A.)
i/ < 2.
Consequently, the conclusions from the previous section apply equally to the partial participation scenario: FedExProx performs least well as GD and can be strictly better when communication time exceeds computation time.
ADAPTIVITY
We now turn to adaptive extrapolation strategies: gradient diversity (GraDS) and a variant of the classical Polyak stepsize (StoPS). Both were first introduced by Horváth et al. (2022) and later adapted for proximal methods by Li al. (2024). As in the case constant extrapolation, we refine the analysis by Li al. (2024) for quadratic problems. Although Theorem 6.1 refers the full participation setting, the approach can be extended to the stochastic case (see Section F.2).
Theorem 6.1. Fix any ? > and consider solving non-strongly convex quadratic optimization problem (1), where fi(x) = _ T A, - bj æ for all E [n], with A, E Sym and b; E Rdd. Let Assumption 1.3 hold and consider adaptive extrapolation strategies:
1. (FedExProx-GraDSS Set
Σm VM7, (wx)
0g 0k
GraDS (xx))
2 1.
| mm VM7 (sw)
Then, the iterates of Algorithum satisfy
| I1(xx)]1 s (1 Cc)* | - [1(x011
(15)
where Cc := min
247 au 147lemax u.j.
2. (FedExProx-StoPS) Set
Er A (12) M7 2 2zbn
= a (aTe) =
StoPS
E V.r7. (mw]
Then, the iterates of Algorithum satisfy
|| [1(xx)] (1- |1a0 11xx0)11
(16)
where Cs
min AKYIT.
Remark 6.2. Similar to the observations by Li et al. (2024), we see that, unlike in the constant extrapolation case (see Theorem 4.1), FedExProx with adaptive extrapolation benefits from semi- adaptivity to the smoothness constant. Specifically, it converges for any > 0. and since yut is bounded above (see (26)), it suffices to choose large enough y to achieve the optimal performance.

---

Published as a conference paper at ICLR 2026
Remark 6.3. Bounding oin Oik by 24 inequality (16) implies that
| [[xx))l (1- 2
| 1 - I
K
and hence Theorem 6.1 guarantees convergence of FedExProx-StoPS in (L./ul x log 1/2) itera- tions, regardless of the choice of the stepsize y. This matches the guarantee from Theorem 4.1, I, but without requiring prior knowledge the optimal extrapolation parameter a = 1/72.. The benefit comes with the trade-off of needing know the minimum of the average of Moreau envelopes.
7 BETTER THEORY WITH PE CONDITION
The result from Section 4 can be extended to solving problem (1) for general functions that satisfy the Polyak-Lojasiewicz (PL) condition.
Assumption 7.1. The function M satisfies PÉ-condition, i.e., there exists p.j such that
[V p4 (MT(x) (xx))
Væ E Rd.
This assumption holds with n= 2 M² (4((+)7)))))))) if the function f satisfies PE. condition with constant f (Lemma A.11). However, the choice p.t x ((4(++<<ma))) is loose and leads to problems described in Theorem 3.2. With this assumption in place, we can present the theorem.
Theorem 7.2. Let Assumptions 1.1, 1.2, 1.3, and 7.1 hold. For all y > 0, FedExProx (Algorithm 1) with a = finds I such that [ff f(x,) I in
log log
iterations, where L,y is a smoothness constant of M and p.j is the PL constant.
Remark 7.3. In practice, solving the local problems exactly often infeasible. Instead, we can only calculate an inexact proximal operator that approximates the desired quantity within certain accu- racy budget. accommodate this, we extend the above analysis the scenario where the clients can only compute updates prox f. (x) such that | (x) , (x)]l < 5 (see Section E). Remark 7.4. Li al. (2024) also establish a linear rate for FedExProx. However, their result relies on the assumption that the function ʃ is strongly convex, and hence that (1) has unique solution. In contrast, our theorem more general, as it allows for possibility of multiple solutions.
similar result can be established the partial participation scenario.
Theorem 7.5. Let Assumptions 1.1, 1.2, 1.3, and 7.1 hold. For all y > 0, FedExProx with nice sampling (Algorithm 2) and a = 1/yb, finds I such that [[f()) fxx,) S s in
ا log Mr
iterations, where L,y3 == n-S Lmaax s(n-1) 147Teaax
+
n(S-1) 8(n-1) I.r), Lay smoothness constant of M
and pzz is the PL constant.
Note that the complexities in Theorems 7.2 and 7.5 entirely analogous those in Theorems 4.1 and 5.1, with the only distinction being the substitution of the smallest non-zero eigenvalue of M M with the PL constant.
7.1 WHY DO GET TIGHTER ANALYSIS?
The story behind our theoretical improvements is no less important than the improvements them- selves, as offers valuable insights and can be instructive for future research. To understand why the new analysis yields stronger guarantees, we need to examine the reasoning behind Theorem 3.2. When proving the result, we noticed that the main reason why (9) was true was the dependence of the Lmax factor. At the same time, the complexity of GD depends only L,
the complexity and there exist many examples when Lmax > L. The question was: why does the original anal- ysis of FedExProx involve Temax: and
circumvent this dependency? The reason behind it
8

---

Published as a conference paper at ICLR 2026
2 1-0000
(1 10000.0
d
theende atbwer beard caerai supper Bound
bocediia boad
ineeriaa hexe teast cmsrrtic upper 2oand
Theende basrt upper bound
theontica uppa bonnd
1-12
1230
Figure 1: Empirical time complexities of FedExProx on a quadratic optimization task.
the reliance of the proof' by Li et al. (2024) on Lemma A.9, which establishes the inequality (z) - M7 (x..) Z I+yLmax (f(z) (zx)). This result appears to be essential for deriving the convergence result [[ -f fax)) S (where F E IR is the output of FedExProx). Our main idea is to instead obtain convergence in terms of distances, i.c., to establish that E xx11""] [1]]]] S and then translate to [x)] - -f(x.) S E using the L-smoothness of the function f. In this way, one can avoid using Lemma A.9, ultimately obtaining much more favourable convergence guarantees.
8 EXPERIMENTAL HIGHLIGHTS
This section presents highlights from illustrative experiments; additional details and results- including those on the ARCENE dataset (Guyon et al., 2000) are provided in Section G. We consider quadratic objectives of the form f(z) = 1 -' A Aja, where A, Sym E [n]] are random positive semidefinite matrices with minimum eigenvalue equal to zero. Each worker i E [14] com- putes proximal mappings using GD with stepsize I/L., The extrapolation parameter a is set to its optimal value from Theorem 4. To validate our theory, we study the empirical time complexity of FedExProx as function of y. In accordance with the setup described in Section 4.1, we assume that one local iteration of GD takes seconds (without loss of generality, by worker to find prox,,, (#x) at global iteration is proportional to X Ylkk, where 7i is the num- ber of GD iterations needed to find grox,f((TM to a given accuracy. In the full participation case,
1). Thus, the time needed
the total empirical time complexity is Σk-1 (1 T maxig[s nes), where is the number of global iterations needed for FedExProx to converge to the desired accuracy and 17 is the communication time. The results are presented Figure 1. The dashed lines represent the theoretical bounds from Theorem 4.3, within which the optimal is expected to lie. One can see that when is relatively small (n) x 100), the best choice of y is near 0. However, as the communication cost 7j increases, the best y shifts to values greater than 0.1. A distinctive U-shape emerges, indicating the nontrivial optimal choice of y. These observations are fully consistent with our theoretical predictions.
CONCLUSION
In this work, we revisit the extrapolated parallel proximal method FedExProx, an algorithm that has shown strong empirical performance but whose theoretical guarantees have far lagged be- hind practice. Upon re-examining the state-of-the-ar analysis, we find that its guarantees are overly pessimistic and that significantly stronger results achievable. To address this gap, develop novel analytical framework for non-strongly convex quadratic and Pt. cases, yielding substantially improved convergence guarantees and a clearer picture of the method's true performance. To put these findings in context, we compare FedExProx with vanilla GD. This comparison is primarily pedagogical but reveals a striking insight: previous analyses could not even show an advantage over this simplest baseline. In contrast, our work is the first to rigorously demonstrate that FedExProx can outperform GD, bridging key gap between empirical observations and theoretical understand- ing. Although our focus is on relatively simple quadratic problems, experiments suggest that the phenomena we describe extend well beyond this setting. These results indicate that the benefits of extrapolation in FL hold in broader optimization scenarios, motivating future research to relax assumptions and establish similar guarantees in more general and practical settings. We view this work as a foundational stepping stone toward deeper understanding of extrapolation in FL, paving the way for advancing both the theory and practice of federated optimization.

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
The research reported in this publication was supported by funding from King Abdullah University of Science and Technology (KAUST): i) KAUST Baseline Research Scheme, ii) CRG Grant ORFS- CRG12-2024-6460, and iii) Center of Excellence for Generative AI, under award number 5940.
REFERENCES
Amir Beck. First-Order Methods in Optimization. SIAM-Society for Industrial and Applied Math- ematies, Philadelphia, PA, USA, 2017. ISBN 161 1974984. (Cited on page 15)
Dimitri P Bertsekas. Incremental proximal methods for large scale convex optimization. Mathemat- ical programming, 12,,,, 2011. (Cited on page 2)
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compres- sion for distributed learning. arXiv preprint arXiv:2002. /2410, 2020. (Cited on page 2)
Bianchi. Ergodic convergence of stochastic proximal point algorithm. SIAM Journal on Opti- mization, 26(4):2235-226) 2260, 2016. (Cited on page 3)
L.. Combettes and J. I. Madariaga. Randomly activated proximal methods for nonsmooth convex minimization. preprint arXiv:2403.10673, 2024. (Cited page 3)
Patrick L Combettes. Convex set theoretic image recovery by extrapolated iterations of parallel
subgradient projections. IEEE Transactions Image Processing, 6(4):493-506, 1997. (Cited page 3)
L. Condat and Richtárik. RandProx: Primal-dual optimization algorithms with randomized prox- imal updates. In Proc. of Int. Conf. Learning Representations (ICLR), 2023, (Cited on page 3)
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local SGD: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics, pp. 3556-3564. PMLR, 2021. (Cited on page 2)
Kaja Gruntkowska, Alexander Tyurin, and Peter Richtárik. Improving the worst-case bidirec- tional communication complexity for nonconvex distributed optimization under function simi- larity. arXiv preprint arXiv:2402.0666 2024. (Cited page
Isabelle Guyon, Steve Gunn, Asa Ben-Hur, and Gideon Dror. Repository, 2004. DOI: https://0o..rrg/102444/2/553
Arcene. UCI Machine Learning (Cited on page and 44)
Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy, Françoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage. Federated learning for mobile keyboard prediction. arXiv preprint arXiv: /8/ 1.03604, 2018. (Cited page 1)
Samuel Horváth, Konstantin Mishchenko, and Peter Richtárik. Adaptive learning rates for faster stochastic gradient methods. arXiv preprint arXiv:2208. 05287, 2022. (Cited page and 37)
Divyansh Jhunjhunwala, Shiqiang Wang, and Gauri Joshi. FedExP: Speeding up federated averaging via extrapolation. arXiv preprint arXiv:2301.090m 2023. (Cited page and 3)
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, al. Ad- vances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1 1200, 2021. (Cited on page 1, and 5)
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the
condition. In Machine Learning and Knowl- edge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part 16. pp. 191-811. Springer, 2016. (Cited on page 16 and 17)
10

---

Published as a conference paper at ICLR 2026
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International conference machine learning, pp. 5132-5143, PMLR, 2020. (Cited page 2)
Ahmed Khaled and Chi Jin. Faster federated optimization under second-order similarity. arXiv preprint arXiv:2209.0222 02257, 2022. (Cited on page 2)
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First analysis of local GD on hetero- geneous data. arXiv preprint arXiv: /00.047,0 2019. (Cited on page 2)
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sehastian Stich. unified theory of decentralized SGD with changing topology and local updates. In International Confer- ence on Machine Learning, pp. 5381-5393. PMLR, 2020. (Cited on page 2)
Jakub Konečný, Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:/610.05449 2016. (Cited on page I)
Hanmin Li, Kirill Acharya, and Peter Richtarik.
The power of extrapolation in federated learning. arXiv preprint 1366 2024. (Cited on page 3, 4. 6, 7. 8, 9, 20, 21, and 32)
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Sys- lems, 2:429-455 2020. (Cited on page 3)
Dong Liu and Jorge Nocedal. On the limited memory BFGS method for large scale optimization. Mathematical programming, 45(1):503-5522 1989. (Cited on page
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of SGD in modern wer-parametrized learning. In International Conference on Machine Learning, pp. 3325-3334. PMLR, 2018. (Cited on page 3)
Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effcceenn learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017. (Cited on page and 2)
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. ProxSkip: Yes! local gradient steps provably lead to communication acceleration! Finally! In International Conference on Machine Learning, pp. 15750-15769. PMLR, 2022. (Cited on page 2)
J.J. Moreau. Proximité et dualité dans un espace hilbertien. Bulletin de la Société Mathématique de France, 93:273-299, 1965. (Cited on page 3)
Ion Necoara, Peter Richtárík, and Andrei Patrascu. Randomized projection methods for convex feasibility: Conditioning and convergence rates. SIAM Journal on Optimization, 29(4):2814 2852, 2019. (Cited on page 3)
Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018. (Cited on page 1, 2, and 17)
A. Patrascu and I. Necoara. Nonasymptotic convergence of stochastic proximal point methods for constrained convex optimization. Journal of Machine Learning Research, 18:1-42, 2018. (Cited on page? 3)
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford. Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. In International Conference on Machine Learning, pp.
PMLR, 2021. (Cited on page 2)
Peter Richtárik and Martin Takáč. Parallel coordinate descent methods for big data optimization. Mathematical Programming, 156:433-483 2016. (Cited page 16)
Peter Richtárik and Martin Takáč. Stochastic reformulations of linear systems: algorithms and convergence theory. SIAM Journal on Matrix Analysis and Applications, 41(2):487-524, 2020. (Cited on page
11

---

Published as a conference paper at ICLR 2026
Peter Richtárik, Abdurakhmon Sadiev, and Yury Demidovich. A unified theory of stochastic proxi- mal point methods without smoothness. arXiv preprint arXiv:2405. 2024. (Cited on page 2)
Nicola Rieke, Jonny Hancox, Wenqi Li, Fausto Milletari, Holger R Roth, Shadi Albarqouni, Spyri- don Bakas, Mathieu N Galtier, Bennett A Landman, Klaus Maier-Hein, al. The future of digital health with federated learning. NPJ digital medicine, 3(1):1-7, 2020. (Cited on page 1)
R. Tymell Rockafellar. Monotone operators and the proximal point algorithm. SIAM J. Control Optim,, 14(5)887-889, 1976. (Cited on page 2)
R. Tyrrell Rockafellar and Roger J-B Wets. Variational Analysis. Grundlehren der mathematischen Wissenschaften. Springer Berlin, Heidelberg, 1998. (Cited page 22)
Ernest K Ryu and Stephen Boyd. Stochastic proximal iteration: non-asymptotic improvement upon stochastic gradient descent. Author website, early draft, 2014. (Cited on page and 3)
Abdurakhmon Sadiev, Laurent Condat, and Peter Richtárik. Stochastic proximal point methods for monotone inclusions under expected similarity. arXiv preprint arXiv:2405. 14255, 2024. (Cited on page 3)
Cheik Traoré, Vassilis Apidopoulos, Saverio Salzo, and Silvia Villa. Variance reduction techniques for stochastic proximal point algorithms. Journal of Optimization Theory and Applications, pp- 1-30, 2024. (Cited page 3)
Alexander Tyurin and Peter Richtárik. A computation and communication efficient method for dis- tributed nonconvex problems in the partial participation setting. Advances in Neural Information Processing Systems, 2023. (Cited on page 2)
Alexander Tyurin, Lukang Sun, Konstantin Burlachenko, and Peter Richtárik. Sharper rates and flexible framework for nonconvex SGD with client and data sampling. arXiv preprint arXiv:2206.0222 02275, 2022. (Cited on page 17)
12

---

Published as a conference paper at ICLR 2026
APPENDIX CONTENTS
1 Introduction
1.1 Related Work
2 Contributions
3 Not Better than GD on Quadratics
4 Tighter and More Optimistic Results
4.1 One step time complexity :(>) is + 7 (yTmax + 1)
5 Partial Participation
6
Adaptivity
7
Better Theory with PL Condition
7.1
Why do we get tighter analysis?
8 Experimental Highlights
9
Conclusion
A Background
15
A.1 Useful Facts about Moreau Envelope
15
A.2 Nice Sampling
16
A.3 Note on Other Sampling Strategies
17
A.4 Useful Lemmas
17
FedExProx as (S)GD Moreau Envelope Reformulation
18
C FedExProx for Quadratics
19
C.I Properties of the Hessian
20
C.2 Proofs for Section
21
C.3 Tighter Analysis....
23
C.3.1 Full Participation Case
23
C.3.2 Partial Participation Case
26
C.4 Lemmas
30
FedExProx under PE Condition
32
FeoxxProx with Inexact Computations
34
13

---

Published as a conference paper at ICLR 2026
F
Adaptive Extrapolation
37
F.1 Full Participation Case
37
F.2 Partial Participation Case
39
Experiments
42
G.1
Experimental Setup
42
G.2 Experiments with Quadratic Optimization Problems
42
G.3 Experiments with Smooth Hinge Loss
43
G.3.1 Synthetic Data
43
G.3.2 Real Data
44
Notation
45
14

---

Published as a conference paper at ICLR 2026
A BACKGROUND
Before discussing the contributions of this work, we provide formal definitions and essential facts that will be repeatedly referenced in the proofs. A summary of the commonly used notation is provided in Table 1.
Definition A.1 (Proximal operator). The proximal operator prox,s R² + IR of f defined by
,rox, (z) (x) = arg min f(z) + - || x1 27
=ER4
where ||-|| is the standard Euclidean norm.
Definition A.2 (Moreau envelope). The Moreau envelope of an extended-reall-vaueed function f
Rd I U {oo) with stepsize is the function M2 IRd Rdd such that
M²(x) = min yER4
f(v) + 2y
11y xx1
for all x E Rd.
A.1
USEFUL FACTS ABOUT MOREAU ENVELOPE
We will often rely on several useful properties of the Moreau envelopes, summarized below. In what follows, we denote
(7
M7. (z).
Lemma A.3 (Beck (2017) Theorem 6.60). Let Rdd R U {+oo} be proper, closed and convex. Then its Moreau envelope Mj satisfies
VM7(x)
-(x prox, (x))
7
for all x E TRd, for any > 0.
Lemma A.4 ((Li et al., 2024) Lemma 4). Let f Rd R be convex and L-smooth. Then M2 is
J. I47L smooth.
Lemma A.5 ((Li et al., 2024) Lemma 5). Let f. :Rd + (+xc)) be proper, closed and convex function. Then, for all 0, f and M7 (x) have the same set of minimizers and minimum.
Lemma A.6 ((Beck, 2017) Theorem 6.55). Let f R PRRR RURU {+00} be a proper, closed and convex convexfunction function. Then Mÿ is also convex function.
Lemma A.7 (LLi et al., 2024) Lemma 7). Let the functions Rdd R E [n], be proper, closed, convex and Smooth. Then M is convex and L, L--smooth with
Σ n
n
L
S
L.
T1
1+
Lemma A.8 ((Li et al., 2024) Lemma 8). Let the functions Si Rdd (U i [n], be proper, closed and convex, and suppose that Assumption 1.3 holds. Then, for all 7 (0, co), the function f(z) = - f((x) has the same set of minimizers and minimum as the function (*)...
Lemma A.9. [Li et al. (2024) Lemma 10] Let Assumptions 1.1, 1.2 and 1.3 hold. Then, for any I. X, and for all Rd, it holds that
1 -((x)-f((z)))
M7,(x) (7.
1+ 714
Consequently,
M7xx) M7xx))) 2 1 1 Lmax
(f(z) f(x.))
15

---

Published as a conference paper at ICLR 2026
The next lemma will play role in the analysis of the method when assuming the Polyak- Eojasiewiez (PL) condition.
Assumption A.10 (Polayk-Looassewwicz condition). The function / satisfies condition, i.e., there exists > 0 such that
1 [Vf(z)] (f(x)) f(x.))
2
for all x Rd. Lemma A.11. Let the function f satisfy Assumption A. with parameter ptt, and suppose that Assumptions 1.1, 1.2 and 1.3 hold. Then, Assumption 7.1 holds with parameter
M
Lmmax
Proof. If f satisfies Assumption A.10, then under Assumption 1.1, Polayk-E.jjsiewwiz condition implies
f(x) f(r.)
x
[=))
Va E Rd
(17)
(Karimi et al., 2016), where (Tx)) is the projection of x onto the solution set X, of f and a, E X.
Then, using Lemma A.9, we get
(x) (x.)
TLmax ((())-((x.)) 2(1 + LLmax)
| [xx))
Due to Lemma A.8, MY and f share the set of minimizers. Thus, [Tx)) is the projection of onto the solution set X, of M Using convexity, we get
(T[((x)) 2 (x + (VMT(.), =x)
and
(((())) (VM - II(x)) S VV | I[xI]
2(1 + 7Lmax)
< V
(T(()) Mx(I(())..
1et
Therefore
1c+
(M (I(((())) - [
4(1 Lmmxx)
2
meaning that M satisfies PE condition with parameter
+ 4(1+ylmox)
A.2
NICE SAMPLING
Let us formally introduce the sampling strategy used. Fix a minibatch size S E [m]] and let S random subset [n] size S, chosen uniformly at random from all (3) subsets of [n] of this size. Such random set S is known in the literature under the name S-nice sampling (Richtárik & Takáč, 2016).
In the proofs, will rely the following useful lemma:
Lemma A.12. Fix BI...., B, Rexxl and let S be an S-nice sampling of the indices [n]. Then
E
1 Σ
B
Σ B S SES
5
BES
=
S(n - 1)
-
B. B,
n(S - 1) ( 1
S(n 1)
Σ B;
1
Σ
B
i=1
i=l
16

---

Published as a conference paper at ICLR 2026
Proof. Define
[1 ies,
X
0 i S.
Then
1 Σ B:
($
E
8
IES
iES
X:B: )
( n
15_xa x:B.
E
5 1m1
i=l
Σ
x B B +
Σ
Xi B)
5
ifj
1
Σ
E X B B
+
Σ [xxx B, B)
S
igj
1
S
B B
S(S
Σ
B B,
52
11
n(n 1) itj
n1
S-1
Σ
n
B B
B;
Σ
B;
> B B:
S
n(n 1))
i=1
n n-S S 1
B. B, + n(S 11)
1
B:
B
S(n - 1)
-1n-1)
1=1
A.3 NOTE ON OTHER SAMPLING STRATEGIES
As discussed in Section 5, Algorithm 2 can handle virtually any (unbiased) sampling technique, with nice sampling used here an illustrative example. For a comprehensive overview of other potential sampling strategies, we direct the reader to Tyurin et al. (2022), which offers a general framework for analyzing a broad range of sampling mechanisms.
A.4 USEFUL LEMMAS
Lemma A.13 ((Kaiimi et al., 2016) Theorem 2). Assume that the function f is convex, L-smooth, and satisfies the Polyak-Lojasiewicz condition with parameter n, Then
" || I[x))1?
f(x) - f(x))
2
for all x E Rdd, where I1(x) is the projection of x onto the solution set X. and x. E X.. Lemma A.14 ((Nesterov, 2018)). Let Dy == f(x) f(y) - [V)) xx be the Bregman divergence of the function f. If f is convex, T.smooth and differentiable, then
1 T [[(x)- s DD(a, + 2)(u,x)
for any x. E Rdd
17

---

Published as a conference paper at ICLR 2026
Algorithm FedExProx
Parameters: stepsize 7 > 0, extrapolation parameter at > 0, starting point zn Rd
2: for k = 0. 1, 2,2.... do
3: Tk+1 Ty ork 4 E prox Tf. (fx) - x*))
4: end for
B FEDEXPROX AS (S)GD ON MOREAU ENVELOPE REFORMULATION
The key idea behind the original analysis of FedExProx is to rewrite the step
1k+1
Tk + OCk
pr (atk) - Ik
in terms of the Moreau envelopes of the local functions. Indeed, the functions fa are proper, closed and convex for all i (ni.. by Lemma A.3, the update rule of Algorithm 1 can be rewritten
Tk+1
VMJ (Tx).
(xx)
2=1
Analogously, in the partial participation case (Algorithm 2), we have
Σ
VMJ (zx).
Fk+1 24.
IES
follows that Algorithms and are equivalent to GD and minibatch SGD for minimizing
M' = Σ M (x)
with stepsize ag?
18

---

Published as a conference paper at ICLR 2026
C FEDEXPROX FOR QUADRATICS
We begin by formally introducing the problem setup and the notation used throughout the proofs.
We are interested in solving the quadratic optimization problem
[(x)=
[(x) = 1 Σ
A -,,= }
min DER"
(18)
1=1
where A, Sym" (X E Rdxd x X x 0} and b; Rd, assuming the interpolation regime (Assumption 1.3), which in this case states that there exists Vs such that A,T. = b, for all i E [m].
(Art - b.) = 0} and let [[()) be the We denote the set of minimizers by X, == fo E IRd 1 Ei=n( projection onto X::
1 - Σ [A (Aco-bb)
[(x) = x
A
(19)
1=1
where i denotes the Moore- Penrose pseudoinverse.
Using eigendecomposition, each matrix A., i [n] can be decomposed as A; = Q.A.Q, where Q: Iq....... Qi,a] E Rdxd is the orthogonal matrix whose columns are eigenvectors of A; and A; E Raxd is a diagonal matrix whose diagonal elements are the corresponding eigenvalues of A,, i.e., A, diag (A1,A)).... (A)),) where 0 (A.) I A2(A,) S ... I (A,).. Let minn(A (A,) denote the smallest non-zero eigenvalue of A, and Amax Amax(A) (A,) the largest eigenvalue of A.
In general, the largest eigenvalue, smallest eigenvalue, and smallest positive eigenvalue of any ma- trix B will be denoted by Amax (B), Amin (B) and X (B), respectively.
The proximal operators in this setting are
Prox y, (x) (7 + 1) (x + 7b;).
(20)
Thus, by Lemma A.3,
(a7 = 7 (
11- +)
{b.)) 1
(x 1) I-) xx))
(21)
7
for any v. E X,, where we use the fact that A, = b, Furthermore, it can easily be shown that
M7 TxT [I A7 1) )) 2-bb (r + I)- 10--2211 2b, (7 + bb)
27
= 27
((x - (xa=x=)²0 )I (rA, + ()) - A,o.)
(22)
and hence
T
1
Σ 1
(I - (1A, (, -1- x-
1)) + (r + (1,
(x) = xT
2
i=1 7
n
6% (7 + +I) 'b
2n 1=1
(1 1
T
1 I M
Σ (r -
of (,
+ -
(23)
2
11 i=1
2m
where M : 1 En (I
(rA, + 1)-1 is the Hessian matrix of the function M This can
equivalently be written as
(x)==
1 2
M( xx) of
1 a x+
+ A
(24)
2n
for any x. E X. We shall denote by x (7) and Amax(?) the smallest zon-zero eigenvalue and the largest eigenvalue of M, respectively.
19

---

Published as a conference paper at ICLR 2026
C.I PROPERTIES OF THE HESSIAN
Next, we introduce several important properties of the matrix M, which will be repeatedly used in the proofs that follow.
In the main part of the paper, we stick to the notation T,, and pay for easier comparison with the results by Li et al. (2024). However, in the proofs concerning the quadratic case, we adopt a more intuitive cigenvalue-based notation.
Fact Since M M? it holds that L., Amax(7) and p.t Ax (7).
Proof. The result is immediate consequence of (23).
Fact 2. Let mmx (7) and X (7) be the smallest non-zero eigenvalue and the largest eigenvalue of the matrix
M
[I
(7A,+
n
respectively. Then
(A,
Amax (7)
max 1
Σ TTQ
Q2
Q
(25)
1+ 7 (A:)
jj
and
n
(((A))
min (7)
min
Σ
Q
Q.
(26)
||||||
1.kor A)+
(+
where := := Σm A, and [bylis the diagonal matrix with by as the jth entry.
Proof. Using the eigendecompositiin, we write M
M = 1 T
,A( 1 Q..
Qi
[+.))(A))
n
The result follows from the identities
Amax (7)
max x Mæ |
and
x miu (7) =
min x. M.
||ek|=1.0E(krr A)
(see Lemma C.7).
Fact For any y 2 0, holds that Amax (7) S Amax(() and Xt (7) S A (A).
Proof. From Fact 2, we have
n
(AA)))
Amax (7)
125
max
Q:
Q''xr
10 n
1+
and similarly
n
Amax (A)
max
T QAlA( O.
|0 n
Since it always holds that
A.(A,) 1+TAş(A:)
I (Ay(),), we get
Amax S Amax (A).
The proof of the second inequality is analogous.
20

---

Published as a conference paper at ICLR 2026
C.2 PROOFS FOR SECTION 3
Theorem 3.2. Let Assumplions 1.3 and 3.1 hold. Consider solving a non-strongly convex quadratic optimization problem of the form (1), where fe(x) 1/20 _ A, by a for all [n], with A, Sym and bj E I.d. Then the assumptions of Theorem 1 by Li et al. (2024) hold, and
I 2 (0) LR T(y) = =(() x
(9)
for all y > Moreover, when 7 - O, then T(7)) L )R effectively reduces to GD.
+ (()) x LB and FedExProx
Proof.
We first prove that (1 + 7 >L
I. Amax ( A.) for all y 2 0. Since
_
1 (1 1- (7A, + +1) +1)
(z)
7
we have
111 1
Σ 1 [I (74: (1-+++++=1))
L Amax
71
Therefore, using the fact that Lmax = max, Amax ( (A:), we obtain
{ " ( (1 (-
(1 + 7bbxa) = (1 (1+7 max Amax (Ai) Amaax
(27)
im1
+ maxx Amax
(1-(AA++)
Amax
and hence, it is sufficient to show that
y max, Amax (Ai) (1A,++)))))))) A,.
(28)
?
Using the eigenvalue decomposition of A,, the expression be rewritten as
+ y max; Amax (Ai) (I (7A, (-(AA;++)))
1 + max; Amax (Ai)
(1 (I-(?Q:A,0) + +1)-1)
1 + max; Amax (Ai)
Qi (I- (11,+1))))))) Q..
Now, letting Bl; be the jth diagonal element of matrix B, we have
1 + max; Amax (Ai) (I- (I-()A++1)))
1 + y max; Amaax (Ai)
I- [- + 1)-1,
?
1 + max, Amax (Ai)
(1- 7A., +1
+ y max, Amax Amax(A))
(A,(A))
IA 2Ay(A.),
?
and hence
(1 max; Amaax Amax((A))
(I (7A; (1-(AA++ +1)+
A..
?
Multiplying by Q: from the left and by Q from the right, we see that (28) holds, and we can conclude that
1 n
- A
(1 + I Ly 2 Amax
i=1
for all 7 2 0. Inequality (9) follows form Assumption 3.1.
21

---

Published as a conference paper at ICLR 2026
We now turn to the second part of the theorem and show that x<>) 4m(177 RR² y 0. The idea behind the proof is that for small enough y, it holds that
- =(())) x LR
(1 + 7 La
(1
max Aunax (Ai)
(aimx(AA))
Amax
I (7A,
(+AA+
?
i=1
Amax
7A,
Amax
Σ A
L.
i=1
More formally, we have
8 Σ
I II -
-2 +7
(11) A.
k=
so that
(1 + Lmax) = +++ max Amax Amax(Ai) (Ai)
ΣΣ>
n (-1))t2 A
Amax
k=1
By applying the dominated convergence theorem to exchange the limit operation and summation, obtain
lim (1 + + lim 7-00
(1+ (1+7maxx max Amax)(A)) Amax
n
80
(1))
))
7-0
n
k=
-maxx
lim (-1) k k-1 200
A
Amax
Σ A L,
n
n
as required.
Lastly, letting + O, we have M7 (x) - f((x) for all and consequently (x) + f(x)
(see, e.g., (Rockafellar & Wets, 1998)). Since Algorithm is equivalent to GD for minimizing (x) with stepsize o7 1/E, follows that its iterates converge those of vanilla GD with stepsize 1/r.
22

---

Published as a conference paper at ICLR 2026
C.3 TIGHTER ANALYSIS
C.3.1 FULL PARTICIPATION CASE
Iteration complexity. We first establish the convergence rate of the algorithm.
Theorem C.I. Let Assumption 1.3 hold and let Py be the iterates of FedExProx (Algorithm 1) applied to problem (18). Then
a1 | M(xx)]l S (1- or (2 (my)mmxxx)))) Xmi (7)) K
|20 [[x=))]²
where )mna((7) (7) and min (7) are the largest and the smallest positive eigenvalues of the matrix A,AA112 + I)= respectively.
M == - (YA,
The optimal choice of stepsize y and extrapolation parameter is ary )mmx((7) in which case the rate becomes
Amax (7) (1--Ainn)))
A (7)
K
| 11(x))11
1120 11
Hence, the number of iterations needed to reach e-solution is
Amax (7) log
||:00 11(x0011
K
Xmi (7)
Proof of Theorem C.I.
The update rule of FedExProx can be written as
Fk-1 Ik +
prox x (Ix) 3h
5
9
(20)
Tk + a
(7A; 1x + 7bb) Ikk
5
i=1
8
( E ((7A, ((7 + [((rA++--11)) I[(x)))
+
((yA:
11- Dx -
S
1=1
i=1
where we use the fact that A, = b; for all E No. Therefore, using symmetry of A;
| [[xx+1)]l < || - 11
a:) + Σ (TA; (1))+1)-1) (sr [((x)))
7
- a
Σe
[I (14--44:10))) (74,+1)-1)
(ox - -[(x)))
i=1
(x [T(x))T (I M² (I My (Irg [[(x)))
= (ok [(Ix)) (I 20-2M + 22) (xt - [((x)))
Since 2 3 >maxx (7) it follows that
[|0+1 M(x++1)]l )]1 < (#r I(xx))) (I -I-20714 M + Amay (7)a²?2M) (Ix IT(x)))
= | [T(x))11 an(2 > (max()))7))(
[T(x)))) M (xx [Txx))
< |a - II(x+)]12 ar(2 - Amax (7) ) ) (7) || [(xx))
for any ay such that 2 Amax(7)ar 2 O. where the last inequality follows from the fact that Th - I1((x)) E range( M) (see Lemma C.6). Consequently,
| (T (1 a2 ardmax ( (7)) ||a [(
23

---

Published as a conference paper at ICLR 2026
It remains to unroll the recurrence and substitute the optimal step size an Amox(7) rate
to obtain the
|a++1 [1(++11)] $ s x11
X (7) mmax (7) | 1xx2))1
Theorem 4.1. Fix any y > 0 and consider solving non-strongly convex quadratic optimization problem (1) where f((x) 1x A, bā x for all E [n], with A, E Sym and b; E R.. Under Assumption 1.3, FedExProx with a 1/7b, finds such that E[f f(xx) after
4 log :
(10)
iterations, where Ly is smoothness constant of M and ptt is the smallest non-zero eigenvalue of the matrix MT.
Proof. The result follows directly from Theorem C.I, smoothness of f. and Fact by substituting Amax (7) Amax X Ly and X (7) Ain (V² = p.j.
Remark C.2. Recall from the proof of Fact that
(AA Q
Σ Q
M
1=1
where A,(A,)
(A())))
if ,yla.
Consequently, for 7 c|x Amar we
[A.)
have
M = Qi
Q -
Σ Q (1, of 4 A,
7d (A))
Y=1
ij
t=1
1=1
and analogously, M = 2
A. Using (25) and (26) gives
Max (A) max x Ax S Amax(?) max x Mx max x' _ Ax Amax Amax(A) |
|||||||
||
and similarly
min min (A) S Strin(7) 1e A)
Mæ X (A).
Noting that L., = Amax(7) uct X x (7), L = Amax (A) and /+ min (A), it follows that the rates (10) of FedExxrox and (30) of GD coincide up constant factor when y sufficiently small. This should come as no surprise, as Theorem 3.2 shows that FedExProx effectively reduces to GD as y 0.
Time complexity. Let us now prove the result from Section 4.1. We assume that each worker i computes the proximal operator using an iterative method, with the running time proportional to the condition number of the subproblem. Given that Amiu (A.) 0 for all i E [n] (otherwise the problem becomes trivial), the time required for all clients to compute prox, (Ix) at each global iteration & is
1 (1+7 max Amax (aaxxxmaxxx)))) (A:) iE(m]
seconds, where the time per one iteration of solving the subproblem. Then, takes 7) seconds to aggregate the updates at the server and move on the next step. Since, according to Theorem C.I. number of iterations needed to reach an e-solution
Amax (7)
| - [(xo)l1
K
log
X (7)
the total time required to solve the global problem is
Tr TT(1)= = Amaa log
||:00 - -1(20)1
x ( (1+ ++ max Amax Amex(Ai)) (E(n)
(29)
X (7)
24

---

Published as a conference paper at ICLR 2026
Theorem 4.3. Consider the non-strongly convex quadratic optimization problem from Theorem 4. Up to a constant factor, the time complexity (12) minimized by some
E
Aunax (A:)
min
Amax (A:))
Anin (A.)
if 7 2 2 and by some
7 0, max
min
--1
max
Amax (A.)
min F1
Anin (A.)
if Moreover, (7) S TGD.
Proof. Recall that Amax (7) and A (7) are the eigenvalues of the matrix
Σ Q (A,
M
(7
I+ Q.
Since y 2 A,( and (A,) > 0, then +)y(A.) 1+1dy(Ag)
E 2 1). and 7 S xy(1,) then -Az(As)
1+,25(A,) E
(A,) 2 (Ai) follows that
(A(A)) (A,))(A,) (A))
(+
72 2
(30)
? x,(!
Moreover, the identities (25) and (26) from Fact 2 tell us that
X (A,)
Amax (7) = max
Σ S
Q
72g A:)
and
(y
X (7)
min | (eeer A)
Q
Q. x,
1 1+
i=1
where A = E A,. Due to (25), (26) and (30), the function (7) is approximately constant
2-1
for all 5 ma Amar (A)) If max (A,) then 7(1 + maxse[n] Amax Amax(A.)) 2 17, and consequently,
(2( = Amax (1) log Amin (7)
|I-0 1(xa)11
x 11+T(1+))
max Amax (Ai) KE(p)
< 2T Amnax (7) x (7)
||:0 M(ao)ll
x (1++7mpp xE|m)
log
maxxxxx Amax (A)) = 2g(7).
Hence, g(>) S (T( S 2g(7). and the term to be minimized
Amaax (7)x x
(,)
max Amna (Ai) xE[m]
x (7)
Using (25) and (26), this can be written
T2(7) max| Σr TQ:
14 maxie(o) Amar (A:) (A,)
X1
Q,x
min /l
Σn Q
(A) (A.)s
Q, x
where the numerator is non-decreasing and the denominator is non-increasing as a function y. 2-1
follows that g(7) is non-decreasing for ? 2 maxicet) (A,) Hence, when _ > 2, the optimal (up multiplicative factor) 7 belongs the interval
(31)
max;e[m] Amnax (A))* mmx; Amnaxe (Ai)
25

---

Published as a conference paper at ICLR 2026
Algorithm 2 FedExProx with partial participation
1: Parameters: stepsize 7 0, extrapolation parameter o* 0, starting point ag RRd, batch size S
2: for == 0, 0,,, do
3: Sample minibatch S₃ S [n] uniformly from all subsets of cardinality $
4: 2k+11 = 2g 0ik (3 Lies, prox, (Tx) Fx)
5: end for
2
When 7 2, the time-complexity is non-decreasing for y max Amar ( and approximately constant otherwise, so the choice
0, max)e(m) Amax (A,)
E
0, max
(32)
is optimal (again, up to constant factor).
Now, suppose that 2 minzein] Alaia (A.)* In this case, the diagonal entries the matrix
are either to 0 (when (A,) = 0) or lie within the interval [ 1). Therefore, (A.))(A.)
(A,)
the ratio
1 1 EE Qi
7A,(A,)
Q,x
Amax (7)
[+7d,(A))
min m Σ T
Qi
(A,)
Q
(A.))
approximately constant in 7. Consequently, the time
T2(1) = Amaxe (2) log
||00 - [1xx))11
x
17 ( +
1 [1 max Amax (Ai)
A (7)
sE(n)
an increasing function of y for minge(ed A (A.)* and the optimal range for y can be tightened from the previously established bounds (31) and (32) to
1
min
maxie[n] Amax (A,)
max;e|n| Amax (A,) mingg[m] [m] Amin (A:)
when 2 2 and
7 max 0. min
maxxe(() Amax (A,) minse[m] Ait (A:)
when 2.
C.3.2 PARTIAL PARTICIPATION CASE
Iteration complexity. We again start with establishing the iteration complexity of the algorithm.
Theorem C.3. Let Assumption 1.3 hold and let be the iterates of minibatch FedExProx (Algo- rithm applied problem (18). Then
E. ||T [[*x)1? (1- on In,s)) At (x)) 11:0 1T
where
x (7) is the smallest positive eigenvalue of the matrix M x(S-1)
(I EE.(AA + r)-1) and L,y.s
n S
max, , [u) Amax (A.) + S(n-If Amax (7).
S[n Ity max Amazi (A.) J.
1 in which case the The optimal choice of stepsize y and extrapolation parameter is ar Ly rate becomes
|| - [xxx 5 <<1
K 1 - 1(x0))1
L
26

---

Published as a conference paper at ICLR 2026
Hence, the number of iterations needed to reach an e-solution is
L log Amin (7)
[xx))ll
KZ
(33)
Remark C.4. Similar to the proof of Theorem 4.1, the result of Theorem 5.1 follows directly from
Theorem C.3, smoothness of f, and Fact by noting that )max(?) = Amax (V2M7) = bn and
Atiin (7) min! (V²M)) = uut.
Proof of Theorem C.3.
The update rule of FedExProx be written
Tk+1 = Ikk +
Σ
prox 3/: (3x)
Tk
5
VESx
T&k ta
(yA, + 1) 1 7bbb)= - Ik
S
iES
E ((TA) 1)-1 -1 I(xx))
Σ
((>A; + 11) xx xa-a
= Tk +
S
VES.
FESL
where we use the fact that A, = b, for all x. X.. Therefore
| 1(1++1)1
< 1 - 11
( a)) =ag Σ (TA, + +1-1
1
(Ix - ((xx)))))
iESt
= 1z - 1(x+)11 20(x - [((x)))²
I 1- Σ (rA: + +1)-1 (xx ((xx))
S
iES
+ - -I((x)))
1-3 5 Σ (74, (14
I 1 (1A,+1)) [(AA+11-1)
(Ix - -I((a))))
EE
iES
= -100 - [Ixx)))1 200 [Ixx)))
- (((x))
+a2?2(xx - {I( 7' M M& (#/ [I(())),
(34)
where M2 == 1 (I - 5 Eies, (7A: + +1) 1)- Next, using the fact that M J Amax M and
applying Lemma A.12 with Bi = 1/4 (I - 177A: 1) 1)- the expectation M M is
n 8 n
(I (1 +1++))11) (I- (7 + + n(S - 1)
M M&]
M T M
72 5(n 1) i=1
S(n - 1)
n 1
1--77,, +1)1))
n(S 1) M
77 5(n 1)n
S(n -1) 1)
1 n S
max Amax (7- +1 iE(n)
Σ
1
(I - (+A:+
7 S(n - 1)
1=1
n(S - 1)
Amax (7)M
5(n - 1)
n S S
damax (A))
M + n(S - 1)
max iE(n]
> (7)
7 S(n 1)
+ 7 Auuas (Ai)
S(n 1)
n 5 5
max;e(m) Amaax (A))
n(S - 1)
S(n 1) \maxx (7) M.
(35)
S(n 1) 1 1+ 7 max in] Amax (A.)
L
27

---

Published as a conference paper at ICLR 2026
Hence, taking expectation conditioned 24. in (34) gives
Es ||0++] - [1(xx+1)]2
Ik [1 a²22(xxxx (I(xx))) [M Ma] (xx II(x)))
-207 (xxx [I(()=)) Ex [MR]] (Ix [I(xxa))
35)
[x [I( )11 7²² s [T(x)))) (
20 - )) M M(x
[I(x)))
I II(x))]I an (2 ,,, (#x [((x))
II(xx))
S I - [T(()))l]= on (2 - - X (7) - [xx=))
(oox)))((x (æx - I(xx)),
where the last inequality follows from the fact that Iy l1((x)) E range(M) (see Lemma C.6). Taking expectation again,
|| [((++11)l? [I (1- ay (2 a2 A (7)) E || - H(xw))
E
remains unroll the recurrence.
Time complexity. Let us consider the same setup as in Section C.3.1, i.e., at each iteration k each client computes a proximal operator prox,,, (Ixx) at most
x
I (
++1 max Amax (A:) REln]
seconds, where 7 is the time per one iteration of solving the subproblem, and it takes y seconds to aggregate the updates at the server and move on to the next step. According to Theorem C.3, the number of iterations needed to reach an e-solution is
L
I 11
K
log
Xmin (7)
where Ly.s solve the global problem is at most
1 max A (s))
n(S-1)
)mnax(?). Hence, the total time required to 5(n-1)
S(n 1+- maxiein] Amau (Ai)
L log (
| (xzo)l²)
(1+Tx
(147xx++7mm max Xmaxx (Ai))) (36)
TT, S) =
rE(n]
Theorem 5.2. Up to a constant factor, the time complexity (14) is minimized by
E
Amay (A.]
min
Amax
min 16 (E(
mnio (Ai)
if 3 2 and by
7 E
0. max
min
Amax (A:)* sc|m)
max
21
min #1
Amana (A:)
3 2.
Proof. Fix some S E [n]. Then, we are interested minimizing
1 S
max A (A:)
1,(1) S(n - 1) A min (7) 1 7 maxie(n) Amax (A:)
17 17+
max Amax (A,) vE(n)
n 1)
Xunax (7)
11 11+ 1 + 7 max Amax (Ai) vE(x)
S(n 1)
A (7)
:=9a(7)
28

---

Published as a conference paper at ICLR 2026
S Sn - 1)
91(7)
Snn 1) 92 92(7).
We know from Theorem 4.3 that the second term of this expression, F2(7), is minimized by
maXie[[] Amax (As) minee(n) Amin (Ai) ]
1
maxie[m] (A.)) min
when 2 and
O, max (o m.n min maXie(n] Amax AA,) minje(n] Amin (A,) }}1
E
when
The same argument can be applied to the term (1().. To be more precise, due to (25), (26), and (30), the function ÿ1 (7) approximately constant for y S max.eja] AA.)((A)) For y >
2-1 [a (A,), have 7 + max;e[n] Amax (A:) 2(1 + maxie|m] Amax (A:)). Conse-
quently, letting 9(7)= := 27 mmx (Ai) (1) can be bounded
A (x)
(()) < gn() < 9(7).
Since A (7) is non-increasing function of g(7) is non-decreasing. It follows that for 7 max:e(n] AA.) (1(7) is non-decreasing in (up to a constant factor), and we arrive at the same conclusions as in the case of 92(1): øn (1()) is minimized by ? 1-1
4-1
ma Amax (A.)* maxie[n] (A.) if 1 2 2 and by y E [0. max 0, max,eln] Amax (1:) <2
2-1 (1,)
On the other hand, by following a similar argument as in the proof of Theorem 4.3, the expression
y maxie((l [n] Ammace
maxie[n] Amax (Ai)
147 max,g(m)) Amaaa (A.)
min (7) 1 1 y maxie[n] Amax (A,) min J (keer)) EE x Q2
(A,) 1+TA;(A:)
Q,T x
approximately constant for 7 minje[m] At (A.)
This implies that T1 (7) is increasing, and hence
the intervals can be bounded above by min [m] Ati (A.)"
The conclusion follows from the fact that the minimum of a convex combination of 91(7) and 72( must lie within the same interval.
Remark C.5. The only term (33) and (36) that depends on
- S maX Amaxe (A,)
n(8 - 1)
Ly.s S(n - 1) + maxxe[n] Amax (A,)
>maax (7).
5(n - 1)
Recall that Amax (7) is the largest eigenvalue of the matrix M 1 En 23 1 (I- (I--II+740
11 Amax (Aily
max Amax ( (A,)
Amax(?) <
?
Amaxe +1
maXie[n] Amax (Ai)y +1
As result, since 3(n-13 is decreasing, and n(S-1) is increasing S, both the iteration and time complexities are increasing functions of S. This underscores the advantage of involving a larger number of clients in the training process.
3[n-1]
29

---

Published as a conference paper at ICLR 2026
C.4 LEMMAS
Lemma C.6. Let
be
the iterates of SGD applied to the problem
min, {f(x) = Li=1 (2x²
B,r of + d.)) where the matrices B, are symmetric. Then
Ik - -1((xx) E range Li=1
Bi) all k.
Proof. By definition of II, have
( a
[
[xx) Σ B:
B
n
Hence, using the identity A (AAT)* = At,
I 11(xx))
B;
Σ
BRx +a)
i=1
i=1
T
B
Σ
B:
+ B
E
B.E [Tx]] - Co
1=1
and so, by symmetry of B;, we get Fy. 11(xx)) E range( 1 Ei= B,).
Lemma C.7. Let M = E. (rA: + 1) where 7 O and A; E Sym for all
i [n]. The smallest positive eigenvalue of M is given by
(( (1+7A(
tiin (7)
min
ΣE QQ:
Q:
QTa,,
DE(er A) n
where A = + A; and (bylر denotes diagonal matrix with by as the jth entry.
Proof. First, observe that the matrices I (yA; ry-1 symmetric, and their eigenvalues given by
(A.) 1+ (A,))
(A,);(A.)
Consequently, M is of symmetric positive definite matrices and is therefore also symmetric positive definite. We now claim that
min x² Mæ. Xtin (7) 1= M)
First, choosing æ to be a multiple of the eigenvector of M corresponding to A (7), we see that
x (7) 2 min x Mx.
M)
To establish the reverse inequality, let {ei} be an orthonormal eigenbasis of M and let be such that ||^|| Then we can write >d age4, and since æ (ker M) L all coefficients corresponding to an eigenvalue 0 vanish. Thus
TM Σ affe A (r) Σ a Xt (7) ||0||
X (7).
This proves that
X (7)
min
x² Mæ.
|| (ker M)
30

---

Published as a conference paper at ICLR 2026
Now, each matrix I - (7-A, + I) can be decomposed as Q2 [+.A;(A.)
(.(A.)
Q Therefore what
remains to be proven is that ker(M) ker(A), (A). To this end, take ker Then Ma 0, and since 7 > O, we have
A1 +1)
(37)
Next, observe that
mh +E
1 π 1=1
Amax
<
Amax ((7A, + +1)+))))
+ 7dmin (A.)
1=1
Now consider two cases.
First, if there exists j E [n] such that Amin(A) > 0, the above upper bound is strictly less than 1. This implies that there exists no nonzero x that satisfies equation (37), and so (er(M) - {0}. But Amin (Aj) also implies that
Amnin
A;
Amin (A:) > O.
1=1 n
As result, ker(M) {0) kerkkrr (A).
Now, let us suppose that Amin (A,) 0 for all [ns]. In this case, Amax ((7A, + 1)- for all [n]. Since all matrices (yA; I) symmetric positive definite with maximum eigenvalue equal to 1, it follows that equation (37) holds if and only
(7 + =
for all i [n]. This is equivalent AAr 0 for all [n]]. Since 7 0 and A; are symmetric positive definite, we can, in turn, equivalently express it as Ax Ei=1 A₂ O.
Consequently, (37) holds (i.e., ker(M)) if and only if ker(A) (A) and hence ker(A) ker(M).
The final expression in the statement of the Lemma follows from eigendecomposition (see Fact
31

---

Published as a conference paper at ICLR 2026
D FEDEXPROX UNDER PL CONDITION
Theorem D.1. Let Assumptions I.I, 1.2, 1.3, and 7.1 hold, and assume that ocy S T. iterates of Algorithm 2 satisfy
2
Then the
E BIIIEK [[xx)]] S (1 (2 -0)),,))))
(
IR |1000 - m(x00))))
2
and hence
B[f(xx) ((I(x))] $ (
Mi E - m(22))))
K
1 - an
2
where Ly,s: =
n-8 ((n-1) 1ty 8(n-1)
n(S-1) Iny). For the optimal choice of stepsize and extrapola-
tion parameter on 1/s, these rates become
E [|aX Mxxx)1 s (1
K
E
1:00
[(xo)1??]
2
and
E (f(xx)) - f(U(()))) L (1
M
E [1:0 11xx0)1]
2
Remark D.2. The above theorem proves Theorem 7.5. Furthermore, by setting S = n1 we recover the result from Theorem 7.2.
Proof. The proof closely follows the proof of Theorem 3 from Li et al. (2024), Recall from Sec- tion that Algorithm 2 is equivalent SGD for minimizing (x) == A Ei= VM2,(a) with stepsize an, and its updates can be written as
Fk+1 I6 a7z Σ VM7,(ox).
iES
Then, for any x. E X.
Eg [| x=11?
1)
27
| - x=-l" 211 20n =
Ih To. Ex
Σ
VM (Ixx)
+ 222
1S5 Σ
(M7((E))
5
SES
27
(A.8) ||are - 12112 207 (xt - Fn, VM VM + 2T?
Σ
VM
(TTE)
5
1ESt
=11 - 2 2ary (Das (zg, (xx,, + a
Σ FES
VM (Ix)
(38)
where Das (x, y) = (x) - M7 (VM v). Next, applying Lemma A.12 with
B. -MM, (It) VM7 (x.) E Rdxi, the last term in the above inequality can be written
Ex
1 Σ VM7 (mx) (Ix)
(1.5) E&
Σ
(vM
VM7
S
SES
VES
(A.12)
n - S 1
VM (xx) - VMM /
/
S(n 1) t=1
VMM (xx) - VM (MT)( 2
n(S-1) -
Σ
S(n 11
32

---

Published as a conference paper at ICLR 2026
Looking the first term of the inequality above, using convexity and smoothness of the functions M. (Lemmas A.4 and A.6), we have
(A.14)
Li
(Dary, (I)) xx) + Dars, (Zx: (21: mx))
VMJ - VM17((a.))
S
n
Lmaxx
Σ
(Dary, (Ik, x.,) + Darz, (x))
S 1 Yymax 1=1
Lmmxx
(Dar (Ix, + DM (x))
1 y
Next, since by Lemma A.7, the function M convex and smooth, the second term can be bounded as
1
M. (2x)
[[V VVM'(x))I
71
(A.14) Ly (DM, DM (xx,
Applying these bounds in (38) gives
Ex
|
=2112]
$ ||
x=.12-2000 - -
2.) + Dar (x,, (x,)
11 S Linax
n(S 1) Lry
(DMM(ZR) + DMr
S(n - 1) 1 7mmax
S(n -
=L,,8
= =|1> a (2- (DMr (Ik: + DMr (zx,)))).
By Lemma A.7, M convex and smooth, so DM (Ix, 2 0, and by Assumption 7.1 and Lemma A.13, we have
Dun (IK, (.aa))==((())) (xx))
Therefore, for L 2
Es || - -10,1+1-2011 < 1|:0x= v.I. - - ( L,,,, (Dis (IK, + (x.,
14
< | x.11 3 ary (2 ,,,,
110 I(xx))1
2
Taking expectation and letting x, l1(xx)) gives
E || 111
< EE
| 11(xx)11
1 |1 1(tw]l]
EE | [1(x))11
- aay agby,s)
Unrolling the recurrence, we obtain the first result
Het
K
R [Ix - [xxx]]]] < 1 (2- ony In.ss)
|1:00
2
Lastly, using L-smoothness of f, it follows that
E [f(xk)] - f[1((x))] < E | - 11(2x)11
1tt ?
k
- ar (2 LnL,,
E ||200 - ((z0)
2
Substituting any 1/Ly,s, which minimizes the expression ary (2 acy Ly,,,,s) s), finishes the proof.
0
33

---

Published as a conference paper at ICLR 2026
E FEDEXPROX WITH INEXACT COMPUTATIONS
In practice, solving (3) exactly is often infeasible, and we can only find vector prox, (x) such that
prox f (x) prox,, (1) (x))= م
where ó represents the accuracy of the approximate solution to (3). As a result, we can only calculate inexact gradient of the Moreau envelope, defined
VM (x) = 1 prox (x)))
One can easily show that
-t) S 72-
With these inexact updates, Algorithm iterates
Tk+1 Ik ax
prox (Ir) 2k
2k 0k
V M (xk),
(39)
where
n
(M
(x)
VM7. v.T
(prox, (z) - prox, (x))
n1
||prox (x) - prox (x)), _ 5 72
<
(40)
With this in mind, we proceed to our analysis.
Theorem F.1. Consider the inexact FedExProx method in the full participation setting defined (39). Les Assumptions 1.1, 1.2, 1.3, and 7.1 hold, and set ary 2L," Then, the iterates of the algorithm satisfy
- 1[(xx)] < (1-
K | - 11xx0)1)+
208
|I
8Lm )
(1t) 2
and hence
K
L 2 ST.
10L6
((xx) ((I(x)))
<
||:0 11xx0)1
(41)
(ut)²
2
Remark E.2. Note that the price one has to pay for inexactness is minimal. To illustrate this, suppose that clients solve the local problems using GD. Then, taking
(m+) 7 ?
20L
we ensure that the last term in (41) is small:
10L8
(ut)²² 2 72
2
Since problem (3) is strongly convex, the local complexity is proportional to
o 0(~
(kx x log 5 =o A x log
20L
(wt)
72
where x > 1 is the condition number. practice, this logarithmic factor can be ignored and treated constant.
34

---

Published as a conference paper at ICLR 2026
Proof of Theorem E.I. The updates can be written
J&+1 = ary V
Thus
|| (((+++1) )|
< | - [I(xx))1 )1²
I - 11(xx)11 - -2a7 (Ix - (1(x)), (x. + +a²n² VM
1 [Ixx)]| ?1 - 20 (It - [Ix))) (xx))
-2ary (ox- (1),,) VM - vx*()
+ [ (VM7 Vx
Using Jensen's 's inequality, we get
|| - [Tx++())]++++ < || - [[(x))]] 11² - 2ar (otx - ((x))) (
-207 (IX- (xxx)) VM (mx) - V=*()))
+ +2027² (1 + 20² VM (.M
(42)
Following the same steps as in the proof of Theorem D.I gives
| [1(x,)11 200 (i (xxx), (xx)) + 2a²2² [
< (1 ar(1 - ( |::0 [xxx]]
< 1 az P
||0 11(=x)11
for ar S 1 and hence
22,"
(42) || 1((2++1))
1 1 (n U1 ||00 - I1(xx)112
S
22n (1x - [1(x)), (M)) (M)()))
22222² V (xx) (xM(I=
Young's inequality yields
on7 pbt
|| Mxx++1)1 < 1 - 10_a7"
||=6 - [(+))11 + -
2
ar V. (xx) - (x) + 2 1 (x)")))
m1 we obtain
where À > O is free parameter. Taking x
[xx41 - 11(x++1111 & (1 (1- an M+t
100 11(xx)11++ + 4ay - - (x) nt
4
+ 2a²2² / - VM (1
1 1 an
11-aa
H4
4 1 12xx))1++ + 5
|| - (MH()
where the last inequality due ary S بtt and La 2 wct. Lastly, due (40), we have
1h | I[x++) I| (1- 11:e - [[xx))) +
5ad
Unrolling the recursion, one can show that
||* - 12xx) < (1 (1- az
K
208
||l0 - 1I(00)1
4
(nt)² 72²
35

---

Published as a conference paper at ICLR 2026
and hence
L
f(xx) ((I((x)) - | [I(xx)]l
I, (1 ar 4
1016 (u 72
120 1xx00
36

---

Published as a conference paper at ICLR 2026
F ADAPTIVE EXTRAPOLATION
The optimal extrapolation parameter values in Theorems 4.1, 5.1, 7.2 and 7.5 depend on L., s, This dependency can be avoided by employing adaptive extrapolation strategies (Horváth et al., 2022). Specifically, we analyze methods based on gradient diversity FredExProx-GraDS and the Polyak stepsize FredExPrx--StoP5
F.1 FULL PARTICIPATION CASE
Theorem 6.1. Fix any ? and consider solving non-strongly convex quadratic optimization
problem (1), where f((x) 1/=² T Aa by z for all E [n], with A, Sym and b, Rd. Let
Assumption 1.3 hold and consider two adaptive extrapolation strategies:
1. (FedExProx-GraDS) Set
GraDS 0g ag (Ix) = ト V.M. (1x)
2
Σ VMJ. (ww)
Then, the iterates of Algorithm / satisfy
|x [T*x)]l S (1- Cc) |150 [
(15)
where C5 min a 1+7 117.
247kmaa
k=
2. (FedExProx-StoPS)ea Ser
1 Er (2r7, (ww)-inf M.7
06 = a
StoPS (xL) =
2 2nbn"
Er val7, (sw)
Then, the iterates of Algorithm 1 satisfy
| [[xxx) (1-Css) 1100
(16)
where Cs ;=
min ax74C.
k=0 k=O.... R-1
Proof. We start with the standard decomposition
| M[x++1)) < || [(xxx)11
1
= |
11(xx)11-- 2000
V V. (xz), - -[((x)) (1))))
i=1
1 Σ
ta 2n
VMy (xxx)
n2 i=1
| - II(xx))11 2 7 - II(xx))) M(xx [I(xw))
tag
VM (xx)
(43)
Now, us consider the two adaptive extrapolation strategies.
(FedExProx-GraDS) In this case, the last term of (43) can be rewritten as
V M (Tx)
1=1
VM (Ix) 2 |
=ar
37

---

Published as a conference paper at ICLR 2026
+ +1)- (oxk M(xx)) 2
21) OUT
(7A,
au - -I((a))
- Σ (1 (1- T
1
(1- (1-(1A,+ (
(ox (ox-
" i=1
I aq max Amax sE(n]
(I (I- (7A++1))
(c(x)((xx))
n Н ( (1-(6A++1)))) (ox -1(()))))
L
Y [ Amaxx (Ai)
- (I((x)) M(x [Ta))))
7 1+ y [aX Amax
(A,) (A,)
Substituting this in (43) gives
| [xx+++1]]
$ ||= - [T(==)))=== 7 - 20 (T(x)))) T "M (xx))
7 mmax4e|n] Amax (A:)
+ax7 + 7 maxie[m1 Amax (A:) (I - [I(xx))) M(xx - [1(xx))
2 + maxie[m] Amaax (Ai)
= =1108 - [Txx2)11 - 0067 maxiE(n) Amax (A,) (Ix - (I(x)))) M - IT(x)))
+ (maiie()) Amax (Aii)
7 1 max4e(x) Amaxe (A,) Xtiin (1) ||:0 - [Ixx))
ax7
where the last inequality follows from the fact that - [I(xx)) E range(M) (see Lemma C.6). Applying this bound iteratively for 0, O,...,K K gives
| - [1(
$ (1 min OK
k=D....KK 1 maxig[n) Amnax A,)) min (1) K
2 maxie[m] Amax (As)
|1:00 - 1(
2. (FedExProx-StoPS) First, note that -mooohhhssss of M implies that
(7xxx inf M 2 2Lm
and hence (H,)( 2 2744
Now, the last term of (43) is
n
n -inf
ag
Σ
VM
F, (Ix)
= ax? Σ 1=1
MM] (x)) - inf M7,)) -infA7))
= a#? (x6) - (I(((()))))
24
1
ax xx7(1x [(xx))) M (xx))).
2
Therefore, using Lemma C.6, get
(43)
|
11(#++1)11
Ia
2|(xw|12- -207 11(xx)) (((ax)))((r)))))
M - -I((x))
1
u - ( (T [T(x)))
2
(1
au (t) 100 - -I(xx)11
Applying this bound iteratively for = 0, O,..., K gives
||0 M[xx)]1 5 1- 3 min an>dmisa()) (1)) K ||:0 - I(x00)1
2 k=U...K-1
38

---

Published as a conference paper at ICLR 2026
F.2 PARTIAL PARTICIPATION CASE
Theorem F.I. Fix any Y > and consider solving non-strongly convex quadratic optimization
problem (1), where Si(x) = 2x. Arr - by x for all E [n], with A, E Sym and by E TR.. Let
Assumption 1.3 hold and consider two adaptive extrapolation strategies:
1. (FedExProx-GraDS) Set
12
$ Eiest VMJ. (2rx)
GraDS ag,S (IR: =
2 1.
| Erest VMG (xx(
Then, the iterates of Algorithum 2 satissy
||EK [xxx) $ ((1-0(111111 (1-inf ini ou
2 yLmax
K
A (7)
||:00 I(x))ll (44)
+ L
where
inf anfaz: *ER inf s
a (z) S).
GraDS
2. (FedExProx-StoPS) Set
1 Eiesy (M7,(x)) - inf M7)
StoPS 03,5 (Ik, Sx)
8
Ork
| Eiess VMJ (rx)
Then, the iterates of Algorithum 2 satisfy
E ||1 11 [[<x))]]]]
< (1-3
3
inf ax 2 (ttn K
||l0 11(x0)113
(45)
where
inf ar ==
inf sCR ((
StoPS
(x, S).
Remark F.2. In the single node setting (S= 1),
inf *ER4 s1 0g11
GraDS
(I, = 1.
However, as more clients participate, the extrapolation parameter may exceed resulting im- proved performance of FedExProx- GraDS. Remark F.3. In the single node setting (S 1), Lemma A.4 implies that
(z, 11 7 0
inf SEMMSCCi
StoPS
74max
As the number of participating clients increases, the extrapolation parameter may exceed this bound, leading to better performance of FedExProx-StoPS.
Proof of Theorem F.l. As in the full batch case, we start with the decomposition
|| 11(xx+1)11 < || 11(xx)11
| - 11 2007 -207
VMJ VM7 (xk), -M(xx)
iEs*
VM7 (xx)
S
iES*
39

---

Published as a conference paper at ICLR 2026
2 10
[xxx)]1
(x [Txx)))
MM(xx - IT(x))))
=ap?
VMJ (Ixx)
(46)
VES*
where M2 : (I -I- Eies, (74, + + Now, let us consider the two adaptive extrapolation
strategies.
1. (FedExProx-GraDS) In this case, the last term of (46) be rewritten
ag??
Σ
VMJ
(xxa)
S
iESk
1
VM f. (Ixx) 1
Σ
5
iES*
21)
1
Σ
I
(7 + + 1)- (ox (mx-)(xx)
0
5
iES
a1(xx - [I(x)))
Σ
I - -1A, +1)++) (1- (14, (1(TAA++)))) (xx (=x-I((x)) [((x))))
s
iESt
I Or max Amax I (7 + 1)-1) (7- sE(m]
(06-
((xx))
Σ
I 17 (1-(74 (ox - -I(()))
iESt
Y max Amaax (A:)
1 [aX Amax (A,) (Ix- - -I(()))) Mx IIxx))).
Substituting this in (46) gives
| - 11(
< <||TA - [I(x)) (I= - I((xa)) M2 - I[(x)))
+ax7 maxse[m] Amnax (Ai)
maxse(m] Amax (A.) (xx II(xx)) MA - II(xk))
2 + y maXie(1) Amaa (Ai)
= =||= - 11xx)]11= -xx7
+ y maxie(n] Amax ( Aii) (20s - II(xx))) Ma - II((x))
2 + y maXie(m] Amax (Ai)
< $| [T(xx)) inf ow?
1 maxie(m] Amax (A,) (#1 [T())) Ma - IT(x)))
where view ag function of S. Taking expectation conditioned Fs, obtain
E, || [[
I | - [I(
2 + max Amax ( (Ai)
iins ox 7n 1 max;e(m) Amax A,)
(Ix - -I(())) Ex [M&] (ox - IT(x)))
2 + max:e|m] Amax (Ai)
-1 -I((I=)1 -inf inf ou
+ 7 maxxe(n) Amax (A,) (II II(xx)) M M II(x)))
2+ maxxe[n] Amax (As)
< (1- ax? + maxie(m) Amax (A,) min (1)
|| - -I(xx)11
where the last inequality follows from the fact that 24 I(xx) range(MM (see Lemma C.6). Taking full expectation and applying this bound iteratively for =
0. K gives the final result.
40

---

Published as a conference paper at ICLR 2026
2. (FedExProx-StoPS) In this case, the last term of (46) is
0
Σ
(mE))
S
iES*
1
Σ
MM. (Tx) - -inf -inf
au7
5
$ESt
(2)
akk 5
Σ
(ax
-1 l1(xx)))
iES"
au7(1x (xxx)) M [Txx)))
Therefore, (46) gives
[x++1 - 11(xx+1111 = || - 11(xx)11 2007(2x - 11(xx)) Ma( - -1(xx))
$ (x= =1(xx))) M& II(xx))
< || 11xx)|1 inf a IIxx))) M& (x II(x))).
2
Taking full expectation and applying Lemma C.6, we obtain
< (1 inf or ou (rtin (1)) ||arx - -I(x))
[| - [[ [1][
N|F]
and hence
E | - [(<x))] $ 31-3
3 2
K inf az a
11:00 - [Tx0)))
41

---

Published as a conference paper at ICLR 2026
1=0000.
TOU MEREOO
Figure 2: Empirical time complexities of FedExProx with partial client participation on a quadratic optimization task for S {1, 7, 14] clients participating in each round.
G EXPERIMENTS
G.1 EXPERIMENTAL SETUP
To verify our theoretical results, we assess the empirical time complexity of FedExProx function of y. We consider two types of optimization problems: synthetic quadratic optimization tasks and classification problems with a smooth hinge loss function. In both cases, local updates are computed using GD. Below, we first outline the methodology common to both experiments, followed by detailed description of the specific settings and their corresponding results.
Total empirical time complexity. As described in Section 4.1, we assume that one local iteration of GD takes seconds. Thus, the time needed by worker to find prox,,, (Irs at global iteration proportional ngke where n, is the number of GD iterations needed to find prox,,, (2x) to a given fixed accuracy. In the full participation case, the total empirical time complexity is given by
K-1
max TIAi sE(m!
(47)
where K is the number of global iterations needed for FedExProx to converge to the desired accu- racy and 17 is the communication cost. experiments involving client sampling, we consider the complexity
Σ
n1
max Tiki iES,
(48)
instead, where St is the random subset of clients sampled at global iteration k. Notice that take the maximum over n. because the overall time is determined by the slowest client. In all experiments, fix 1 and vary 77, effectively considering the ratio n//..
To ensure robust experiments, we count the number of GD steps and communications K and apply formula (47) (or (48)). This proxy for real wall-clock time is robust, reliable, reflects reality, and allows controlled experiments. The plots report the empirical time complexity required to find o such that f(**) infzer f(x) < 10-3
One of experimental tasks is to verify that this empirical complexity aligns with the theoretical complexity derived in (14) (see Section G.3.1).
G.2 EXPERIMENTS WITH QUADRATIC OPTIMIZATION PROBLEMS
In the first set of experiments, consider quadratic optimization problems of the form
f(x) = T1
T A,æ,
where A, E Symī, í E [n] are random positive semidefinite matrices with the smallest eigenvalue equal to zero. In particular, each worker's matrix is generated A, Q.D where Q, is random orthogonal matrix from QR decomposition of a d x matrix with standard normal entries. The diagonal matrix D is constructed by uniformly sampling eigenvalues between 0 and a maximum
42

---

Published as a conference paper at ICLR 2026
100.0
10000000
10000.2
0- 1-10000.0
1180
Figure 3: Empirical time complexities of FedExProx on synthetic classification task with smooth hinge loss.
1=1000.0
f1
mamporayy
THes ingiiial meeyotty
3--17
Figure 4: Comparison of thcoretical time complexity (12) and empirical time complexity (47).
drawn from the interval [5, 10). Each worker i computes the proximal mappings using GD with stepsize of I/L., where L, = Amax (A,) is the smoothness constant the local subproblem (3). The extrapolation parameter is computed value of Ly. The data is distributed across n = 14 workers.
its optimal value from Theorem 4.1, using explicitly
Figures 1 and 2 display the results for the full and partial participation settings, respectively. The dashed lines indicate the theoretical bounds derived in Theorems 4.3 and 5.2, within which the v is relatively low (n x 100),
optimal value of is expected to lie. When the communication the optimal is close to zero. However, as 1 increases, the optimal y shifts to values exceeding 0.1. This results characteristic U-shaped curve. reflecting the nontrivial optimal choice of 7. These observations are fully consistent with our theoretical predictions.
G.3 EXPERIMENTS WITH SMOOTH HINGE Loss
G.3.1 SYNTHETIC DATA
We now turn to classification problem involving linearly separable data {(raj, Yis) heeni, helnlejemm suring the interpolation regime. Specifically, we construct a synthetic binary classification problem by independently sampling X data points Ziy IRd and ground-truth weight vector w" Rd from the standard normal distribution. Labels are then assigned yig sign (ee(=""""")
The function f Rd IR is defined
1 n n1
m
f(w)
[(w)
(n((w)
1
m
where (Zij, Vir) E R 1, for all i [n].j E [m]] and lij is the smooth hinge loss, defined by
0,
if wa xıj 2 1, if yiyw zig 1, wijw" Dúj 5.
(w
(1
Vij T ray)
2
Virw Tajs
Each client E [n]] computes the local proximal mappings using GD with stepsize I/L., where L, = 1 Σy || 2 is an upper bound on the smoothness constant of the function fi. The extrapolation m parameter a is determined via grid search within the theoretical range given by Lemma A.7. We use workers, each holding 4 datapoints, and the number of parameters is d = 3.
43

---

Published as a conference paper at ICLR 2026
100.0
10000.000
20000
Figure 5: Empirical time complexities of FedExProx on the ARCENE classification task with smooth hinge loss.
The results are presented in Figure 3. As in Section G.2, these experiments again suggest non-zero optimal choice of y when communication is slow. Indeed, the values of y minimizing the U-shapes in the last three plots are around 1. These experiments provide further support for our theory.
Comparing theoretical and empirical time complexities. Next, we compare the theoretical and empirical time complexities (12) and (47). Both are plotted the same scale in Figure We that our theoretical model reflects the empirical dependencies (up to multiplicative factor).
G.3.2 REAL DATA
We further validate our findings on real-world data by repeating the experiment on the ARCENE dataset (Guyon et al., 2004). We subsample 20 random data points and restrict attention 30 randomly chosen features. The resulting plot in Figure 5 again exhibits the characteristic U-shape behavior as the communication cost increases, mirroring the synthetic case and reinforcing the bustness of our observations
44

---

Published as a conference paper at ICLR 2026
H NOTATION
Notation
II-II
Standard Euclidean norm
(+))
Standard Euclidean inner product
[k]
{1,...,k)
E2 []]
Expectation conditioned on the first iterations
n
Number of workersinndexcllensdvvieee
d
Dimensionality of the problem
7
Stepsize
Okk
Extrapolation parameter
Tai Taaax
Smoothness constants (Assumption 1.2)
prox, (x)
Proximal operator the function f with parameter (see (3))
M7
Moreau envelope of the function f with parameter (see (7))
M
= E M7,
T,
Smoothness constant of M
The smallest non-zero eigenvalue the matrix V² (see Theorems 4.1, 5.1)
PL constant (see Theorems 7.2, 7.5)
x())
Total time per global iteration of Algorithm 1/2
Ty())
Time complexity of Algorithm
T2(7,)
Time complexity of Algorithm = {i R4 (z)) 0}
X.
(T))
Projection x onto solution set
n²
= ||.- - _=
(y(,,)
Bregman divergence between and associated with function / R² - R
Identity matrix
A;
Local data matrix stored on worker with spectral decomposition A. Q.A.Q.
= D A.
Sym
= (X E Raxd
x=
XT X 2 0} the set of symmetric positive semidefinite
matrices
ker A
Kernel of matrix A
M
= - E (7 + 1)-1)
M
= 1 (74, + 1)-
Amaxi B
The largest eigenvalue of matrix B
Amin (B)
The smallest eigenvalue of matrix B
t (B)
The smallest positive eigenvalue of matrix B
[B],
The jth diagonal element of diagonal matrix
[bylet
diagonal matrix with by as the jth entry
Table Frequently used notation.
Note LLM Usage. Large Language Models were used to assist in polishing the writing of the manuscript. LLM assistance did not contribute to the scientific content the paper.
45


Reviews:
[{"review_id": "35O5sspqs0", "reviewer": "Reviewer_uVfr", "summary": "This paper improves the existing convergence results of FedExProx in several regimes. The authors first demonstrate that FedExProx can outperform gradient descent when minimizing non–strongly convex quadratic objectives, under both full and partial client participation. They further propose two adaptive strategies for selecting the extrapolation parameter and analyze the convergence of the resulting methods under the same settings. Finally, the theoretical results are extended to general smooth convex functions that satisfy the PL condition.", "questions": "1. It seems that FedExProx can potentially perform well when $\\frac{L_{\\gamma}}{\\mu_{\\gamma}^+}$ is relatively small. Since you provide one example of optimizing diagonal quadratic matrices, I am wondering in general, when this quantity can become small, e.g., separable functions? \n\n2. Is it possible to further consider acceleration for FedExProx, i.e., to get $\\sqrt{\\frac{L_{\\gamma}}{\\mu_{\\gamma}^+}}$?\n\n3. Is there any regime when $\\eta \\approx \\gamma$, FedExProx is still faster than GD by a large margin?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is clearly written.\n2. The improvements of the theoretical results are interesting and novel, showing the potential benefits of doing the extrapolation step under interpolation and the PL condition, when communication is much more expensive than local computation.\n3. The paper extends the analysis by allowing the use of adaptive stepsize.", "weaknesses": "The scope of the experiments is a bit limited, without comparisons with other commonly used FL optimization methods.", "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": "KPQOpjow7i", "reviewer": "Reviewer_HREj", "summary": "The authors revisit FedExProx, an extrapolated proximal algorithm for federated learning (FL), and find that its prior theoretical guarantees don’t offer any improvement over vanilla Gradient Descent (GD) for quadratic problems. They develop a tighter performance analysis showing that FedExProx achieves a linear convergence rate and can provably outperform GD when communication costs dominate computation—a crucial scenario in FL. Additionally, they extend the analysis to partial participation scenarios, introduce adaptive extrapolation strategies based on gradient diversity and Polyak step sizes, and generalize the results to functions satisfying the Polyak–Łojasiewicz (PŁ) condition, thereby relaxing the requirement for strong convexity.", "questions": "- How critical is the interpolation assumption (Assumption 1.3) for FedExProx’s performance? In realistic non-interpolating scenarios (where clients’ objectives have different minimizers), would FedExProx still converge or provide benefits, or does the theory break down completely?\n\n- The theoretical advantage of FedExProx is clear when communication latency dominates. Can the authors provide intuition or examples of real-world settings where the time savings from FedExProx are significant?\n\n- The paper proposes adaptive extrapolation strategies (FedExProx-GraDS, FedExProx-StoPS). What is the overhead or complexity of implementing these strategies in practice?\n\n- The empirical results were mentioned only briefly. Could the authors elaborate on the experimental setup and findings?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The paper pinpoints a flaw in prior analysis, which suggested FedExProx had no advantage over vanilla GD on quadratic tasks. It then resolves this by presenting a refined analysis that overturns that pessimistic result. This corrects our understanding and is a valuable theoretical insight.\n\n-  Using a novel analysis framework, the authors prove tighter convergence rates. The work also extends FedExProx’s theory to more challenging scenarios.\n\n-   The analysis explicitly incorporates communication vs. computation trade-offs, reflecting real federated learning conditions. The paper shows that FedExProx’s total time can be lower than GD’s when network latency is the bottleneck, which is a practical strength. It’s valuable that the theory isn’t purely iteration-count based, but considers wall-clock time under FL constraints.", "weaknesses": "- The tighter theoretical results, while impressive, apply under specific assumptions that may limit practical generality. For example, the analysis assumes an interpolation condition (existence of a common minimizer across clients), which may not hold in real federated data (where different clients might not share an exact global optimum).\n\n- FedExProx, introduced by Li et al., is not a novel algorithm. This submission primarily contributes an improved analysis of it. While the advances are mostly theoretical, they don’t propose a fundamentally new approach. Therefore, the novelty may be perceived as incremental, as it refines our understanding of an existing method rather than introducing a brand-new algorithm.\n\n- The paper’s presentation leans heavily on theoretical derivations and dense mathematical details. Readers with only a moderate background might find it challenging to follow some parts. For instance, understanding the implications of constants like $L_γ$ or $μ^+_γ$ in Theorem 4.1 requires significant effort. Important concepts (e.g., the PL condition or Moreau envelopes) are used somewhat tersely. Overall, the exposition could be clearer with more intuition or examples.", "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": "XTpnwzQLSM", "reviewer": "Reviewer_1Qc8", "summary": "This paper first identifies a limitation in the original analysis of FedExProx that its known guarantees are no better than vanilla GD. To address this issue, the authors proposed a tighter linear convergence analysis for FedExProx for non-strongly convex quadratic optimization problems. The main result shows that FedExProx outperforms GD when accounting for computation/communication costs. Further, the paper analyzes partial participation and two adaptive extrapolation strategies, and extends the results to more general settings under the Polyak-Łojasiewicz (PL) condition. Some illustrative experiments are provided to validate the theoretical findings, highlighting the potential of extrapolation in federated learning.", "questions": "1. Can the Assumption 1.3 be relaxed, at least in the quadratic case?\n\n 2. What are the main technical challenges faced by the analysis of FedExProx in the considered settings?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The work is well motivated and clearly presented in general.\n\n2. The theoretical analysis is technically sound and comprehensive, with sufficient details provided in appendix. The results demonstrate that FedExProx is superior when communication dominates local computation (which is common in FL), and thus are potentially applicable to heterogeneous FL environments.", "weaknesses": "1. The theoretical analysis focuses primarily on niche scenarios like quadratic programs or functions satisfying the PL condition. This narrows its applicability to practical non-convex FL tasks. Moreover, the Assumption 1.3 essentially requires all the clients to share the same minimizer, which is an extremely unrealistic setting: If each individual client is already able to find the common global mimimizer based on their own data, then why should we bother to do FL from the very beginning? \n\n2. While the linear convergence rates are refined for FedExProx in the quadratic case, the novelty of analysis looks incremental with relatively straightfoward proof techniques.\n\n3. The empirical results highlighted in the main paper are somewhat supportive of theory verification. However, the experimental study still falls short in testing on benchmark FL datasets with heterogeneous client setups or real network latency.", "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 (Poster)